From mvp9@cornell.edu Wed Sep 18 21:11:48 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J1Bmh12001 for ; Wed, 18 Sep 2002 21:11:48 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id VAA11143; Wed, 18 Sep 2002 21:11:46 -0400 (EDT) Date: Wed, 18 Sep 2002 21:11:46 -0400 (EDT) From: mvp9@cornell.edu X-Sender: mvp9@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 13 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents a protocol for wireless ad-hoc mobile networks that focuses on minimizing power consumption both in data transmission and protocol messages. The new idea driving the protocol is that the maximum number of nodes should be used in a transmission to minimize overall used power. It is reactive, in that a "best" route is calculated only when some data is to be sent from some node. The algorithm for route discovery is greedy, so that the resulting route is not optimal even in a static network. The protocol seems to assume that source and destination are within range of each other. Presumably, if this is the case, PARO can be integrated with another network layer protocol, but the details of this are never described. More generally, power consumption is rarely the only concern, which means PARO would have to combine the power-based cost function with other costs, which can get arbitrarily complicated. Clearly, there are also circumstances where total power use for a route is increased by relieving a highly stressed node - which is certainly desirable - but this is not taken into account by PARO. Also, in a dynamic network it seems that nodes will often have to transmit at full power, destroying any advantages the protocol was hoping to offer. Although the paper's motivation is compelling, power consumption is rarely the sole factor in route determination. Combination with other metrics is probably the first extension to be pursued. However, the issues above would have to be addressed before further extensions can be profitably pursued. In a sensor network (or any other that is static) it is probably more efficient to use a link-state algorithm, which really does calculate optimal routes. Their comparison to MLSR is not convincing as in the long run, when no maintenance is necessary, the link-state must clearly win out. From mp98@cornell.edu Wed Sep 18 21:42:48 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J1gmh17308 for ; Wed, 18 Sep 2002 21:42:48 -0400 (EDT) Received: from Warren-Lapines-Computer.local. (r105572.resnet.cornell.edu [128.253.240.214]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id VAA05127 for ; Wed, 18 Sep 2002 21:42:46 -0400 (EDT) Date: Wed, 18 Sep 2002 21:42:51 -0400 Mime-Version: 1.0 (Apple Message framework v543) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 13 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <1C2F1A22-CB71-11D6-A16E-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.543) This paper designs a routing protocol motivated by a need to conserve power rather than minimize delay and bandwidth. The basic idea revolves around an eavesdropping node, call it R, listening to a conversation between S and T. If R calculates that it could lower the power consumption required in this travel by acting as an intermediate host (i.e. the total power cost from S to R to T is less than that directly from S to T) then R sends a packet to both S and T alerting them of R's candidacy as a forwarding host. S will now send packets to T's IP address, but with R's MAC address. All the nodes involved will of course have to maintain routing information for this route. This paper is notable because it is the first paper we have read that attempts to form a routing protocol with the goal of minimizing power consumption rather than, say, hopcount. They attempt to do extensive profiling of their performance which is laudable and characterize under what conditions the algorithm works best (packets send very rapidly or nodes remain mostly still). However, ultimately this algorithm is a simple idea which falls apart in a complex world. Their assumptions are unreasonable. The notion that all communicating nodes are within maximum transmission distance of each other, for example, is pretty unusual (it also breaks their redirecting technique). In none of their simulations do they provide the reader with bandwidth calculation (I would even settle for a 'goodput' measure), and their comparison to MLSR is done on static nodes, whereas the focus of the paper is on mobile hosts. They mention themselves that the route constructed by this algorithm may be sub-optimal. What this paper truly needs is a smaller scope. As it stands it is pretty poor routing algorithm. It's real use would be as a modification upon existing protocols--The notion of eavesdroppers nominating themselves as a more power efficient route could easily be imagined as a plugin to other protocols like AODV. It would be interesting to see, say, a comparison of the bandwidth, latency, and power consumption of AODV vs. the same metrics on AODV+PARO. From hs247@cornell.edu Wed Sep 18 21:49:48 2002 Received: from mailout5-0.nyroc.rr.com (mailout5-1.nyroc.rr.com [24.92.226.169]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J1nmh18301 for ; Wed, 18 Sep 2002 21:49:48 -0400 (EDT) Received: from hubby.cornell.edu (syr-24-58-42-130.twcny.rr.com [24.58.42.130]) by mailout5-0.nyroc.rr.com (8.11.6/RoadRunner 1.20) with ESMTP id g8J1nfo00619 for ; Wed, 18 Sep 2002 21:49:42 -0400 (EDT) Message-Id: <5.1.0.14.2.20020918214917.00b29798@postoffice2.mail.cornell.edu> X-Sender: hs247@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Wed, 18 Sep 2002 21:49:35 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 13 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed PARO (Power-aware routing optimization) was introduced in this paper. The creators of PARO looked at ad-hoc networks in a different way then we have in the previous papers. In general, it considers the optimal path route from node A to node B to be the route that requires the least amount of transmission power. This is good because in general, nodes in ad-hoc wants to save battery power, and the less power spent sending packets means more power for longer life or for other tasks. PARO has two main assumptions: the device used to transmit packets has an interface to control the transmission power, and that nodes can listen to packets (not intended for it) and gather information from those packets. The general idea is that if A has a route to B, it tries to send a message to B. If a node C in between A and B hears that message, it calculates whether or not it can overall transmitting power if it is used as a redirect node. If so, it sends a message to A telling A to redirect all packets to B through C. The calculation of transmission power is based on signal strength of a packet received. In a mobile network, because nodes can be moving, the signal strength may vary from packet to packet. Therefore the calculation of the minimal transmission power is crucial. If chosen too low, the packet may not reach any node. I find it sort of ironic that for the PARO to work efficiently and accurately, it needs packets to be sent in the network so information about transmission can be gathered. I can see why this algorithm might work for a static network, but i still need some convincing for ad-hoc networks. For the ad-hoc network, it just seems like the deltas and approximations in the algorithms are just increased to account for network movement and therefore maybe not even saving power. I don't think the example described in figure 4 of the paper, is entirely correct. If B was indeed a redirect node, A would only be using enough power to send packets to B, and therefore C shouldn't be able to hear what A is sending. Also PARO is based on too many assumptions. More work has to be done with choosing the correct parameters and simulations in the real world have to be done. In general, can an algorithm that relies on configuration parameters (which depend on network environment) be successful in an ad-hoc network? I ask this because the general nature of ad-hoc networks is that the environment is unpredictable and optimal parameters might have to be set on the fly dependent on network characteristic. Also, by just considering power, how much cost in performance will it give up? The importance of saving power and trade offs has to be looked at more closely. From mr228@cornell.edu Wed Sep 18 22:29:30 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J2TUh25925 for ; Wed, 18 Sep 2002 22:29:30 -0400 (EDT) Received: from cornell.edu (pptp-018.cs.cornell.edu [128.84.227.18]) by cornell.edu (8.9.3/8.9.3) with ESMTP id WAA14170 for ; Wed, 18 Sep 2002 22:29:29 -0400 (EDT) Message-ID: <3D89368C.EAE1FE42@cornell.edu> Date: Wed, 18 Sep 2002 22:29:32 -0400 From: Mark Robson X-Mailer: Mozilla 4.76 [en] (Windows NT 5.0; U) X-Accept-Language: en MIME-Version: 1.0 To: egs@CS.Cornell.EDU Subject: 615 PAPER 13 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper presents PARO, a power-aware routing optimization for wireless networks. Power is a key commodity in wireless networks and all efforts to conserve it should be made. Their goal is to identify paths through the network that will minimize network power usage by introducing additional nodes into a path. The protocol works as follows: If S wants to broadcast to D, it turns up its power such that it can. Since power is not a linear function distance, they argue it may be beneficial for another node to cut the path into two portions to reduce power consumption. After S talks to D, if any other node overhears the message and feels that it can save the network some power by introducing itself into the path, it tells both S and D to include it along their path for all future communication. This process continues until some steady state it reached. They make some gross and unrealistic assumptions. They assume a wireless network wherein all hosts can communicate with all other hosts (provided they turn up their power sufficiently high). They also assume links are bi-directional and equally "good" in both directions. Their results seemed somewhat concocted to highlight those areas this protocol is meant to address; they don't give any more "traditional" measurements such as bandwidth, latency, etc. Given their assumptions and limited results, the protocol seems useful. It certainly seems to save significant amounts of power, and that is what they set out to accomplish. Future work might consider a hybrid protocol; one that combines a modified version of PARO and some other protocol to try to conserve power in a network where all hosts are not necessarily reachable by (paraphasing) "sufficiently increasing one's transmission power." From xz56@cornell.edu Wed Sep 18 22:49:43 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J2ngh29663 for ; Wed, 18 Sep 2002 22:49:42 -0400 (EDT) Received: from XIN (dhcp-ece-167.ece.cornell.edu [132.236.232.167]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id WAA04800 for ; Wed, 18 Sep 2002 22:49:41 -0400 (EDT) Message-ID: <013301c25f87$33332a10$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 13 Date: Wed, 18 Sep 2002 22:49:03 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="Windows-1252" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 The paper as its title suggests, gives a routing protocol that optimizes power consuming. The way by which the protocol achieves this is: By overhearing the data packets from the source and acknowledgements from the destination, the intermediate nodes estimate the transmission power needed when acting as a redirector. By choosing the redirector with the lowest opt, the optimal 2-hop route is discovered. However, this may not result in the final optimal route. Iterating this process, the multihop route is discovered. By setting the alpha, the protocol effectively limits the number of hops, the increase of which will cause more delay and power consumed for computing and repeating. The algorithm seems quite feasible and the simulation results also confirm this. It may be planted into the wide-area routing protocols to act as a local optimization. But it doesn't handle the mobility well. The proactive approach is generally not as efficient in comm. networks where data are of a bursty nature as reactive ones. This makes one doubt whether in mobile ad hoc networks, energy conservation by introducing more hops really works, since more hops also makes the route more unstable and hence more overload need to update the route against the modes' mobility. Also, in reality, the power control levels must be discrete. Is it possible to take this into consideration in the transmit redirect, say when calculation the opt? From bd39@cornell.edu Thu Sep 19 00:06:55 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J46sh13884 for ; Thu, 19 Sep 2002 00:06:54 -0400 (EDT) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA23000 for ; Thu, 19 Sep 2002 00:06:54 -0400 (EDT) Message-Id: <5.1.0.14.2.20020919000535.00b93eb0@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 19 Sep 2002 00:05:57 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 13 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Paper 13 - PARO This paper identifies network activity, specifically transmissions, and transmission power as a key component in the longevity of MANET devices. The paper proposes that the focus of contemporary routing protocol do not take advantage of adjustments in transmission level. By using intermediary nodes to transmit at a lower power level to convey the message, MANET devices can extend their battery life. PARO describes a protocol in which intermediary nodes can detect and use potential transmissions that can be routed through them to save power. PARO is the first routing protocol to fully consider the implications of power consumption within the routing protocol itself. PARO seems to be a not a full routing protocol in of itself, i.e. such aspects as destination discovery and route maintenance as vague and unclear. (i.e. what if the destination is not within a transmission neighborhood?) PARO does seems to be a good method of fine tuning paths created by other routing protocols to become more power efficient. In general, failure conditions (node death, dropped packets) are not considered. The increased failure rate that occurs when path lengths are increased and transmission power decreased could be problematic. It would be nice if the paper included actual costs of transmission of a packet, which is not simply a function of transmission power. It is interesting to note that MAC level transmissions such as RTS/CTS are still sent at full power. What are the implications of this, given the high fixed energy cost of sending packets? Also, promiscuous listening on the ether means that adapters are not able to take advantage of fully powering down during other node transmissions. One big difference between this paper and the others we have read is the existence of simulation data and an actual implementation. Although the actual results aren't really anything astounding (or enlightening), a proof of concept is nice. The simulation graph is surprisingly sparse for data points. The comparison graph with MLSR only shows the difference between energy wasted by the initial startup costs. What about dynamic behavior of PARO, and say, another reactive protocol using the same metrics to obtain routes? One future direction would be incorporation of PARO as a feature of another protocol to fine-tune routes. An interesting topic would be adaptation of power level due to the density of surrounding neighborhood. This could cause other protocols to naturally adopt PARO-like routes. From ag75@cornell.edu Thu Sep 19 00:22:25 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J4MOh17061 for ; Thu, 19 Sep 2002 00:22:24 -0400 (EDT) Received: from sanya (r105361.resnet.cornell.edu [128.253.240.52]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with SMTP id AAA20619 for ; Thu, 19 Sep 2002 00:22:24 -0400 (EDT) Message-ID: <000d01c25f94$2775df30$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 13 Date: Thu, 19 Sep 2002 00:22:23 -0400 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 5.50.4807.1700 X-MimeOLE: Produced By Microsoft MimeOLE V5.50.4910.0300 In this paper we were presented with PARO, a power-aware routing protocol for wireless ad hoc networks. The goal of PARO is to minimize the transmission power consumed in the network. In order to do this, PARO tries to find a route for which the transmission power required is minimimal. It tries to do this using as little transmission power as possible. Finally, PARO is a kind of protocol that discovers routes on-demand and on a node-to-node basis. The algorithm makes some pretty big assumptions. First, PARO requires that nodes be able to dynamically adjust the transmission power used to communicate with other nodes. Second, PARO assumes that the transmission power required to transmit a packet between nodes A and B is similar to the transmission power required to transmit a packet between nodes B and A, which a lot of times is not the case. Finally, the protocol assumes that all nodes are within direct transmission range of each other (though it can perform power optimization as a layer 2.5 if this is not the case). PARO optimizes routes one step at a time, thus it requires several iterations to converge to an optimum route. Additionally, the protocol does not guarantee that the final route is the route that will need the minimum transmission power. On the other hand, during later iterations reductions in transmission power are much smaller than the ones obtained during the first few iterations. Thus, we obtain most of the benefits fast even with the caveats above. The simulations ran to test the protocol were not very impressive. The simulation for a network with 10/30/100 static nodes lasted for only 100 seconds with 10 flows transmitting 512 bytes packets every 3 seconds. This is not typical of a real network and it's hard to conclude anything about scalability and about how this protocol would perform on a real network. From shafat@CS.Cornell.EDU Thu Sep 19 00:53:30 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J4rMh22339 for ; Thu, 19 Sep 2002 00:53:25 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 13 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 19 Sep 2002 00:53:20 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D1507A8@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 13 Thread-Index: AcJfmHwke3svaXxKQSKJWVjCYBRdUA== From: "Syed Shafat Zaman" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8J4rMh22339 The motivation that worked behind developing a power-aware routing optimization (PARO) is the significance of conserving power in mobile ad hoc networks. As the paper points out, power resources is one of the most scarce resources in present day wireless networks. PARO attempts to minimize usage of power by reducing transmission power when packets are exchanged between nodes. And it does so, by increasing the number of intermediate nodes that the packet has to go through to reach its destination. This is in stark contrast to what most other routing protocols try to achieve (in other words, difference in the definition of optimality). PARO uses a reactive routing algorithm to establish the least power consuming route between a source and a destination. Routes are created and maintained in a strictly on-demand basis as any unnecessary transmission would defeat the purpose of the optimization. One of the biggest weaknesses of PARO is the assumption that both the source and the destination are within hearing range of each other. This raises serious questions about PARO's performance in large settings, and also the objective of the protocol itself. The authors could perhaps have addressed this issue in a more detailed fashion. The paper also offers an analysis of performance of the protocol in a simulated environment. From the results, it becomes rather evident that PARO would perform reasonably well in smaller networks but with not too much mobility. In fact, figure 6 in the paper is strongly indicative of its average performance in a highly dynamic environment. The comparison between PARO and MLSR also seemed like a cheap shot to convince the reader about PARO's effectiveness. MLSR, by virtue of being a proactive routing protocol, always has more packet transmission than PARO. A more realistic comparison with an efficient reactive protocol could serve the purpose better. Future enhancements should definitely include the scalability issue that the current version overlooks. Also, factors like load balancing, route-loops should be looked into. A better algorithm for reducing convergence time could also be developed. This would be particularly helpful in ameliorating PARO's performance in mobile wireless networks. From jsy6@cornell.edu Thu Sep 19 02:05:19 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J65Ih03387 for ; Thu, 19 Sep 2002 02:05:18 -0400 (EDT) Received: from Janet (syr-24-58-33-193.twcny.rr.com [24.58.33.193]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id CAA11315 for ; Thu, 19 Sep 2002 02:05:18 -0400 (EDT) Message-ID: <000f01c25fa2$76ea1c30$0600a8c0@Janet> From: "Janet Suzie Yoon" To: Subject: 615 PAPER 13 Date: Thu, 19 Sep 2002 02:04:49 -0400 MIME-Version: 1.0 X-Security: MIME headers sanitized on sundial.cs.cornell.edu See http://www.impsec.org/email-tools/sanitizer-intro.html for details. $Revision: 1.132 $Date: 2001-12-05 20:20:17-08 X-Security: The postmaster has not enabled quarantine of poisoned messages. Content-Type: multipart/alternative; boundary="----=_NextPart_000_000C_01C25F80.EF28DB40" X-Priority: 3 X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook Express 6.00.2600.0000 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 This is a multi-part message in MIME format. ------=_NextPart_000_000C_01C25F80.EF28DB40 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The conservation of transmission power is important in devices such as = notebook computers and cellular phones where transmission power plays a = significant role in power consumed. Reducing transmission power in such = situations can dramatically increase the device's operational lifetime. = The MANET protocols we have previously looked at have been inefficient = in terms of transmission power because their goal was to minimize the = number of hops between source-destination pairs. MANET protocols tend = to use the maximum transmission power in order to minimize the number of = forwarding nodes (redirectors) or they tend to use too many signaling = packets being generated at a lower transmission power. This paper = offers a protocol, the power-aware routing optimization (PARO), which = attempts to maximize the number of redirectors and thus minimize the = transmission power consumed in the network. PARO further deviates from = MANET protocols in that it is not broadcast-based but node-to-node = based. PARO consists of three main operations:=20 (1) Overhearing Algorithm - listens to packets sent in the MAC level = in order to learn the minimum transmission power towards neighboring = nodes (2) Redirecting Algorithm - computes whether power will be saved by = redirecting the source-destination route to include this intermediate = node (3) Route-Maintenance Algorithm - PARO is a protocol for both wired = and wireless network. Only wireless networks need to utilize the = Route-Maintenance Algorithm. PARO mainly relies on data packets as its = source of routing information. Signaling packets called = route-maintenance packets are sent when no data packets are available = within the specified interval route-timeout. =20 PARO relies on a few assumptions: - The transmission power used to communicate with other nodes = must be dynamically adjustable. This is not a far-reached assumption = since commercial radios that support IEEE 802.11 and Bluetooth have this = kind of power control - The transmission power needed to transmit a packet from A to B = is similar to that of B to A. This is a less reasonable assumption than = the one above since it requires an interference-free MAC. - Every data packet successfully received is acknowledged at the = link level - All nodes are located in transmission range of each other and = can overhear any transmission by other nodes. This is the biggest = assumption in the protocol, especially in reference to wireless ad-hoc = networks. =20 There are some flaws in PARO in convergence and scalability. Since only = one redirector can be added for each iteration, it takes several = iterations for the network to converge to a final route. In a highly = mobile network, convergence may never take place. Also, since only one = intermediate node can be added as a redirector node at a time, as the = network becomes denser, there is a greater increase in collision and = bandwidth waste. Finally, the optimal redirector added in the first = resolution might not lead to the optimal route. Even if the route = itself was optimal, the power consumption may not be evenly distributed = and thus a node in the network could end up with a considerably shorter = lifetime (even if it was not a source or destination node). Interesting = enough, simulation shows that more than 3 redirectors may not be optimal = (the original goal was to maximize the number of redirectors) due to = increase in end-to-end delay and signaling overhead needed to maintain = these routes. This protocol did not mention how it handled network = partition. Also, it would be useful to know the processing power needed = to implement PARO compared to the transmission power saved. Some of the = computations are difficult and complex, such as the computation of the = minimum transmission power necessary to communicate with the overhead = node. =20 ------=_NextPart_000_000C_01C25F80.EF28DB40 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

The conservation of transmission power is important in devices = such as=20 notebook computers and cellular phones where transmission power plays a=20 significant role in power consumed. =20 Reducing transmission power in such situations can dramatically = increase=20 the device=92s operational lifetime. =20 The MANET protocols we have previously looked at have been = inefficient in=20 terms of transmission power because their goal was to minimize the = number of=20 hops between source-destination pairs. =20 MANET protocols tend to use the maximum transmission power in = order to=20 minimize the number of forwarding nodes (redirectors) or they tend to = use too=20 many signaling packets being generated at a lower transmission = power.  This paper offers a protocol, = the=20 power-aware routing optimization (PARO), which attempts to maximize the = number=20 of redirectors and thus minimize the transmission power consumed in the=20 network.   PARO = further=20 deviates from MANET protocols in that it is not broadcast-based but = node-to-node=20 based.  PARO consists of = three main=20 operations:

(1)  =20 Overhearing Algorithm =96 listens to = packets sent in=20 the MAC level in order to learn the minimum transmission power towards=20 neighboring nodes

(2)  =20 Redirecting Algorithm =96 computes whether = power will=20 be saved by redirecting the source-destination route to include this=20 intermediate node

(3)  =20 Route-Maintenance Algorithm =96 PARO is a = protocol for=20 both wired and wireless network.  = Only wireless networks need to utilize the Route-Maintenance=20 Algorithm.  PARO mainly = relies on=20 data packets as its source of routing information.    Signaling packets = called=20 route-maintenance packets are sent when no data packets are available = within the=20 specified interval route-timeout. =20

PARO relies on a few assumptions:

-        =20 The transmission power used to communicate = with other=20 nodes must be dynamically adjustable. =20 This is not a far-reached assumption since commercial radios that = support=20 IEEE 802.11 and Bluetooth have this kind of power = control

-        =20 The transmission power needed to transmit a = packet=20 from A to B is similar to that of B to A.  This is a less reasonable = assumption than=20 the one above since it requires an interference-free = MAC.

-        =20 Every data packet successfully received is=20 acknowledged at the link level

-        =20 All nodes are located in transmission range = of each=20 other and can overhear any transmission by other nodes.  This is the biggest assumption = in the=20 protocol, especially in reference to wireless ad-hoc networks. 

There are some flaws in PARO in convergence and = scalability.  Since only = one=20 redirector can be added for each iteration, it takes several iterations = for the=20 network to converge to a final route. =20 In a highly mobile network, convergence may never take = place.  Also, since only one = intermediate node=20 can be added as a redirector node at a time, as the network becomes = denser,=20 there is a greater increase in collision and bandwidth waste.  Finally, the optimal = redirector added in=20 the first resolution might not lead to the optimal route.  Even if the route itself was = optimal,=20 the power consumption may not be evenly distributed and thus a node in = the=20 network could end up with a considerably shorter lifetime (even if it = was not a=20 source or destination node). =20 Interesting enough, simulation shows that more than 3 redirectors = may not=20 be optimal (the original goal was to maximize the number of redirectors) = due to=20 increase in end-to-end delay and signaling overhead needed to maintain = these=20 routes.  This protocol did = not=20 mention how it handled network partition. =20 Also, it would be useful to know the processing power needed to = implement=20 PARO compared to the transmission power saved.  Some of the computations are = difficult=20 and complex, such as the computation of the minimum transmission power = necessary=20 to communicate with the overhead node. =20

------=_NextPart_000_000C_01C25F80.EF28DB40-- From mtp22@cornell.edu Thu Sep 19 09:51:11 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JDpAh28740 for ; Thu, 19 Sep 2002 09:51:10 -0400 (EDT) Received: from narnia (syr-24-58-57-15.twcny.rr.com [24.58.57.15]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with SMTP id JAA11054 for ; Thu, 19 Sep 2002 09:51:10 -0400 (EDT) Content-Type: text/plain; charset="iso-8859-1" From: Matt Piotrowski Reply-To: mtp22@cornell.edu To: egs@CS.Cornell.EDU Subject: 615 Paper 13 Date: Thu, 19 Sep 2002 09:51:09 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02091909510900.00149@narnia> Content-Transfer-Encoding: 8bit The major contribution of this paper is the PARO protocol. This protocol is important because its main goal is to minimize power consumption. This is in contrast to prior protocols whose main goal is minimizing route length and/or convergence time. So instead of trying to find the minimum number of hops between two nodes, PARO tries to find the maximum number. A weakness of this paper is the assumption that all nodes are within range of each other. In many real networks this is certainly not the case. The authors realize this and say that perhaps PARO is better suited as a protocol between the link layer and the network layer instead of being "the" network layer protocol. Another weakness is the poorly suited nature of PARO in fairly mobile networks. This again, is not a realistic assumption in many cases. The work in this paper could be expanded upon by combining PARO with a routing protocol that does not assume that all nodes are within transmission range of each other. PARO could be used for local communications, while the other protocol is used for more wide-range communication. I suspect that if the interface to PARO were made clean enough, it would not be hard to code it into simulations of a number of different routing protocols. From nbs24@cornell.edu Thu Sep 19 10:04:17 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JE4Gh00933 for ; Thu, 19 Sep 2002 10:04:17 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id KAA28464; Thu, 19 Sep 2002 10:04:14 -0400 (EDT) Date: Thu, 19 Sep 2002 10:04:14 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209191404.KAA28464@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: nbs24@cornell.edu X-Originating-IP: 64.185.145.94 Subject: 615 PAPER 13 Conserving Transmission Power in Wireless Ad Hoc Networks Previous papers did not consider the need for power conserving algorithms in their routing protocols. This paper proposes a power-aware routing optimization, PARO. It focuses on minimizing overall power consumption in an ad-hoc network by maximizing the number of nodes used during transmission. This is achieved by allowing an intermediate node to overhear transmission between source and destination nodes. If the intermediate node thinks by its calculation a route through itself will conserve power, it elects to forward the packet from the source to the destination. There can be several intermediate nodes between source and destination. This optimization takes advantage of the ability to adjust power transmission levels. This paper assumes that source and destination nodes are within range of each other. This is very flawed. In introducing more nodes between source and destination, it is more likely that packets will be lost, but these were not considered. Since their algorithm requires several iterations to converge toward a final route, this might take incredibly long or if the network is very dense, convergence may never be reached. Their algorithm also focuses on transmission power only and neglects the cost of processing overhead packets and the cost of keeping the nodes in a listening mode. Their simulations did not consider a mobile network and therefore did not lend credence to their claims of better performance. To build on the research, PARO needs to be implemented in a real network to evaluate the convergence rate and comparisons made with other protocols apart from MLSR Nana B. Sam From kwalsh@CS.Cornell.EDU Thu Sep 19 10:11:32 2002 Received: from duke.cs.duke.edu (duke.cs.duke.edu [152.3.140.1]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JEBWh02915 for ; Thu, 19 Sep 2002 10:11:32 -0400 (EDT) Received: from localhost (larry.cs.duke.edu [152.3.140.75]) by duke.cs.duke.edu (8.9.3/8.9.3) with ESMTP id KAA06946 for ; Thu, 19 Sep 2002 10:11:31 -0400 (EDT) From: kwalsh@CS.Cornell.EDU Received: from 132.236.150.81 ( [132.236.150.81]) as user walsh@imap.cs.duke.edu by login.cs.duke.edu with HTTP; Thu, 19 Sep 2002 10:11:31 -0400 Message-ID: <1032444691.3d89db138c854@login.cs.duke.edu> Date: Thu, 19 Sep 2002 10:11:31 -0400 To: egs@CS.Cornell.EDU Subject: 615 PAPER 13 MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: Internet Messaging Program (IMP) 3.0 X-Originating-IP: 132.236.150.81 Conserving Transmission Power in Wireless Ad Hoc Networks PARO is a power-aware routing algirhtm based on the observation that many short hops are often more power efficient (in terms of transmission power only) than fewer long hops. Standard ad hoc routing protocols exarcerbate the power problems of mobile devices by using hop count, as opposed to power consumption, as the routing metric. In this paper, the authors assume that all nodes are within transmission range of each other under maximum transmission power. In networks where this is not the case, a heirarchical scheme might be adopted, with PARO conserving power locally, and a more traditional routing protocol ensuring long-range connectivity. This is not discussed in detail. The auhors further assume, for the purposes of estimating minimum transmission cost to nearby nodes, that links are bidirectional and are essentially symmetric in terms of power requirements. In PARO, the primary route discovery mechanism nodes overhear data transmissions of nearby hosts. Each transmitted packet contains the power level at which the packet was sent. Nearby nodes, upon overhearing the packet, can essentially "subtract" the local recieve power from the transmitted power (according to a propagation model), and thereby detirmine the power needed to send to the originating node. Using this method, each node builds a cost table for nearby nodes. During route initialization, a source will send directly to a destination at full power. Intermediate nodes, upon overhearing the transmission, can detirmine if it would be cost (power) efficient to insert themselves in the route. If so, then the node informs both sender and reciever of this fact. Source and dest can choose the most efficient neighbor as the next hop. This process is repeated until some threshold of improvement can no longer be met. The most critical weakness of this paper, as usual, is in the evaluation. A simple simulation compares PARO to a modification of LSR (using power as the cost metric, rather than hops). Here, the modified LSR appears to find identical (if not better) power-aware routes. The disadvantage, the authors claim, is that LSR takes more broadcasts, which are quite expensive, to do so. PARO's advantage might dissapear, however, by using a routing algorithm less costly than LSR. From sc329@cornell.edu Thu Sep 19 10:29:49 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JETnh07187 for ; Thu, 19 Sep 2002 10:29:49 -0400 (EDT) Received: from sangeeth.cornell.edu (syr-24-58-36-135.twcny.rr.com [24.58.36.135]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id KAA06091 for ; Thu, 19 Sep 2002 10:29:47 -0400 (EDT) Message-Id: <5.1.0.14.2.20020919102800.00b06438@postoffice2.mail.cornell.edu> X-Sender: sc329@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 19 Sep 2002 10:29:46 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 13 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth Chandrakumar Conserving Transmission Power in wireless Ad Hoc Networks This paper introduces PARO, a power-aware routing optimization that results in the reduction in power expended in transmissions from a source to destination among ad hoc networks. Developing efficient architectures and protocols that increase the operational lifetime of network enabled services. PARO uses a packet forwarding technique where intermediate nodes can elect to be "re-directors" between a source destination pair with the goal of reducing the transmission power required. PARO is a node-to-node based routing technique, thus geting rid of the inefficiencies of having to send out too many signalling packets as in a broadcast flooding technique. Efficient routes are discovered using data packets itself, other than using signalling packets. In this protocol, every nodes updates its packet header to indicate the power required to transmit the packet. Any node which overhears both source and destination can compute whether packet forwarding can result in power savings. If an intermediate node elects to become a re-director it sends a route-redirect message to source and destination informing them of the new node. If a node does not have information on power requirements to the destination, it just sends it out with the maximum power. Every node maintains a overhear cache where it stores the triple(ID, time, Power) required for each destination. In dense networks, multiple redirect messages could be generated, in which case the redirect request with the best power optimization is chosen. PARO deals with the mobility of nodes by transmitting at a power level slightly greater than the recorded value to increase the probability of reaching the next hop on the first attempt. The authors also present an evaluation of the protocol proving the fact it results in power reduction when there are sufficient number of re-directors. But these simulations also reveals much of the drawbacks of the protocol. Having more than three re-directors does not result in more saving of power and only results in creating a longer route, increasing the end-to-end delay. Though the simulation gives good results with static networks, ina more mobile environment data packets transmitted are likely to be lost. IN comparison to MLSR, the power savings achecived by PARO is significantly better. Comments: PARO addresses a significant issue with mobile ad hoc networks. But the main drawbacks of the paper are the strong assumptions it make. - It assumes dynamic power transmission power and interference-free MAC. - PARO does route optimization one step at a time. SO it would require several iterations before it would converge into the most optimal route. Also it is possible that the first iteration, which seemed optimal could result in a final route which is not the route achieving the minimum transmission power. - PARO tries to minimize the power by redirecting through intermediate routes. But a re-director could chose to be one for many transmissions, thus depleting its energy source much earlier. - Simulations does not take into account the effects of control packet overheads. This could have a significant impact on the power savings as the RTS/CTS packets are sent with maximum power. From vrg3@cornell.edu Thu Sep 19 10:53:50 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JErnh13026 for ; Thu, 19 Sep 2002 10:53:49 -0400 (EDT) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id KAA00025 for ; Thu, 19 Sep 2002 10:53:47 -0400 (EDT) Date: Thu, 19 Sep 2002 10:53:47 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 13 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper presents the Power-Aware Routing Optimization, PARO. PARO is an approach to routing which actually in a sense has a goal that is the reverse of others which we have examined; rather than trying to minimize the number of hops on a route, PARO attempts to increase them so that transmissions can be done at lower power. The basic idea behind PARO is that two nodes, A and B, can be communicating directly with each other when a third node, C, is between them. C can decide whether or not it can improve the overall power consumption, and, if so, negotiates a new route with A and B such that their packets travel through C. A (or B) then communicates with B (A) by sending a lower-power transmission to C, which forwards the transmission, also at low power, to B (A). There are a few strong assumptions made in the development of PARO. The one that concerns me most is that all the nodes should be able to communicate with each other, if they set their power levels high enough. This is simply not possible in a large-scale MANET. This points clearly to a future direction of work: incorporating PARO into another routing protocol. As its name suggests, PARO would likely be best used as an optimization on top of an existing protocol. The paper does not actually present PARO as a complete MANET routing protocol anyway; it does not really address problems such as link failures and limited bandwidth. From liuhz@CS.Cornell.EDU Thu Sep 19 11:06:50 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JF6nh16450 for ; Thu, 19 Sep 2002 11:06:49 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 13 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 19 Sep 2002 11:06:49 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE607@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 13 Thread-Index: AcJf7i28wcnqZsjwSu+ZzqHZgPE/hw== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8JF6nh16450 Conserving Transmission Power in Wireless Ad Hoc Networks This paper introduces PARO, a power-aware routing optimization that helps to minimize the transmission power needed to foward packets between wireless devices in ad hoc networkss. Due to its power conserving point-to-point on-demand design, PARO is capable of outperforming the traditional broadcast-based routing protocols(e.g., MANET routing protocols). The simulation result reveals an important fact that compared to the power consumed by the data and control packets transmitted before convergence of optimal routes, the consumption of later data transmission is less significant, thus suggests an important design principle for future power-aware routing protocols that is the avoidance of "blind" (e.g., broadcast) transmission at high power. The core algorithm of PARO consists of three parts: overhearing, redirecting and route-maintenance. The overhearing algorithm estimates the minimum power needed to send packets to the overheard node. The estimated value is stored and is used by the redirecting algorithm to decide if the adding of the overhearing node to the route will decrease the overall power consumption. If this is the case, the overhearing node becomes a potential "redirector" and sends a route-redirect message to the communicating nodes involved. PARO uses a clever scheme here to suppress duplicate route-redirect packets, that is priority route-redirector packets. Upon the reveival of this message, the original route will redirect itself to go through the overhearing node, thus a new route with less overall power consumption is achieved. However, this core algorithm only applies to static netwokrs. To make it suitable to mobile nodes, this paper suggests some enhencements to the core algorithm, such as: sending explicit signaling packets, using increasing transmission range to capture mobile nodes, and so on. However some details are missing here, like how to choose the value of route-timeout. Besides, the redirecting algorithm for mobile situation is describled in a informal way. I guess the authors have not come up with a complete PARO solution for mobile networks at that time, thus they can only evaluate and the performance of the protocol in static networks. No result about power efficiency in mobile networks is given in the paper. Thus, there is still some distance to make PARO applicable to networks with high mobility. PARO is not a "complete" routing protocol, because it's only applicable to the situation where all nodes are located within the maximum transmission range of each other. Thus given a sparsely populated network, PARO must be combined with some other traditional routing protocols to find a complete route with low power consumption. When designin PARO, the authors take power efficiency as the only metrics to make a good routing protocol, ignoring all the other important metrics like end-to-end throughput and delay. It's critical to take these metrcs into account and make some trade-off between them. Also it's very important to use the power capacity of each node fairly to prevent overloading some nodes and exhausting them, but this paper doesn't say any things about it. From smw17@cornell.edu Thu Sep 19 11:18:14 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JFIDh18886 for ; Thu, 19 Sep 2002 11:18:13 -0400 (EDT) Received: from cornell.edu ([128.84.84.84]) by cornell.edu (8.9.3/8.9.3) with ESMTP id LAA17566 for ; Thu, 19 Sep 2002 11:18:13 -0400 (EDT) Message-ID: <3D89ECBF.5030104@cornell.edu> Date: Thu, 19 Sep 2002 11:26:55 -0400 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 X-Accept-Language: en-us MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 13 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit PARO PARO (Power Aware Routing Optimization) is an algorithm designed to reduce the overll system power consumed in the process of routing. On the simplest level, PARO acts to insert an additional routing hop between two existing hops whenever the central node detects that there is a net power savings in doing so. The basic protocol operation is as follows. Each packets, in its transmission, includes the transmit power necessary for that node to reach the destination. Whenever a node overhears a packet, it checks the node's transmit power relative to the total power incurred by inserting the snooping node into the routing path. If the snooping node can provide a sufficient power savings in the route, and no other nearby node transmits a better route first, the overhearing node will transmit a redirect packet, instructing the sending node to route future traffic through the intermediate node. Only one node may be added into a route on any one iteration of the protocol. Extending PARO to mobile network is explained through the addition of a linear "silence interval" term to the transmission power, as well as a mechanism for upstream nodes to detect when a previous node is no longer the power-optimal route. PARO has some nice features. One of the most significant is that most of the power savings observed come from adding the first one to two nodes into the path. This suggests that moderate increases in delay can significantly reduce overall power consumption, and that while convergence may be a slow process, there is sufficient power savings from partial convergence to justify the effort. In fact, the decreasing rate of return for additional nodes suggests that there is a reasonable trade-off to be found between latency and power consumption. The paper also had a number of weaknesses. One of the more significant issues to me is the simulation results, and their method of presentation. Presenting in graph form (instead of, say, a bar graph) really requires more than three data points to give a useful picture of the tradeoffs involved. The adaptation of PARO to mobile systems is also fairly scant, and seems highly likely to suffer from a number of problems with respect to genuine node and link failures. The authors describe a node hand-off mechanism for removing a hop that is no longer power efficient, but give no consideration to the effects of the loss of a reflector node (or reflector link), and how such losses will interact with routing protocols used in conjunction with PARO. Finally, implementation of this protocol requires nodes to listen in on all communications traffic, which implies running the network interface in promiscious mode, increasing NIC power consumption. One recommendation I would make is to more closely examine the effects of quantized transmission power on performance. Both the research on how to maximize power efficiency given a set of power levels, and the research on how to select the optimal transmission power levels for power aware routing would be useful information, and could have a real impact on protocol design and performance. From pj39@cornell.edu Thu Sep 19 11:19:08 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JFJ7h19012 for ; Thu, 19 Sep 2002 11:19:07 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA17462; Thu, 19 Sep 2002 11:19:05 -0400 (EDT) Date: Thu, 19 Sep 2002 11:19:05 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200209191519.LAA17462@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: pj39@cornell.edu Reply-To: pj39@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: pj39@cornell.edu X-Originating-IP: 128.84.223.189 Subject: 615 PAPER 13 Conserving Transmission Power in wireless Ad Hoc Networks This paper addressed the one of most important and scarce resource for MANET i.e battery power. It considers conserving power in manet's as one of the most important part in optimizing the performance of manet's. Power aware routing optimization (PARO) assumes that transmitting a packet to a distant node consumes significantly more power than to one that is near. Hence PARO attempts to minimize power usage by a node by increasing the number of intermediate nodes that are near to it. It makes use of reactive routing algorith in order to establish the least power consuming route between a source and a destination. Routes are created and maintained whenever there is a demand and hence there are no signal messages. The major weakness of PARO is that it assumes that all the nodes are within hearing range of each other so any node can reach any other node in a single hop as in a LAN. This assumption limits the scalability of PARO to a great extent as the network would be confined to a very small range of distance. The author do describes communication between LAN's as a WAN but the protocol is not clear and is not described in detail. The paper gives simulation analysis of the protocol. From analysis it is clear that PARO would perform well in smaller networks with limited mobility. The comparison of PARO with the modified Link State routing algorithm MLSR does not give a better idea of the effectivity of the algorithm. As MLSR is a proactive algorithm with lots of signalling messges. It would have been better if the authors would have compared PARO with other reactive algorithms which have some power optimization. Future work could be directed towards a more scalable network using PARO. Also other general issues like routing loops, load balancing, security issues, higher layer protocols can be discussed. From ashieh@CS.Cornell.EDU Thu Sep 19 11:28:12 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JFSCh21238 for ; Thu, 19 Sep 2002 11:28:12 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8JFSC509064 for ; Thu, 19 Sep 2002 11:28:12 -0400 (EDT) Date: Thu, 19 Sep 2002 11:28:11 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 13 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII PARO This paper introduces PARO, a link-layer technique for reducing power consumption. Since transmission power increases superlinearly with range in all propagation models, subdividing a long path may result in power savings. PARO operates transparently under a standard routing algorithm (lowest hop count, for instance). If node notices a conversation between two other nodes, and believes that a route through it would require less power than the direct transmission (using some loss model), then it advertises a route through itself. Self-timing is combined with a use-first-heard scheme to provide collision avoidance and improved optimality. PARO continues iteratively, typically improving power consumption as time progresses. The PARO technique increases latency (increased hop count, not necessarily visible to the routing algorithm, and also requiring more time before detecting a network partition). It also provides suboptimal routes (greediness causes suboptimal selection when two communicating nodes can hear each other. once a node is selected as an intermediate node, it always remains an intermediate node until motion detection algorithm eliminates it; lack of global knowledge induces suboptimal behavior when the communicating nodes cannot hear each other, and so the algorithm falls victim to the triangle inequality). The power equations used in the paper do not take into account fixed transmission overheads. ** Future work - PARO always attempts to find a node as close to the bisector of two communicating nodes as possible. Once selected, a node will always (unless it moves away) redirect traffic between the endpoints. A consequence is that additional hops are likely to be used, with little improvement in power consumption. More hops are in fact likely to increase global power consumption due to second order terms ignored by PARO (e.g. receive power). Since many more intermediate nodes are likely to have sent out redirect advertisements than nodes that actually end up redirecting, perhaps remembering the old advertisements would allow intermediate nodes to build some idea of the local link state in the system, and determine a more optimal route. From adam@graphics.cornell.edu Thu Sep 19 11:28:46 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JFSkh21299 for ; Thu, 19 Sep 2002 11:28:46 -0400 (EDT) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id g8JFSe0k050935 for ; Thu, 19 Sep 2002 11:28:40 -0400 (EDT) Date: Thu, 19 Sep 2002 11:20:48 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 Paper 13 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII PARO identifies the problem that resources are limited w/ current day mobile devices and there needs to be some recognition of the importance of power consumption in ad-hoc networks. Basic idea is that if you can trade off some efficiency (not getting there in one hop) w/ a significant decrease in power consumption you should take it. Like the other paper for today, I ask if this is really a full routing algorithm? I doesn't seem that it will work very well w/ real network conditions (nodes coming or going, packet loss). PARO does get kudos for finally addressing the power consumption issue however, as it is the first to do so. The paper also has a simulation and implementation (albeit rudimentary, but at least its something) to demonstrate the work. From egs@CS.Cornell.EDU Thu Sep 19 11:29:28 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JFTRh21360 for ; Thu, 19 Sep 2002 11:29:28 -0400 (EDT) From: Emin Gun Sirer Received: (from egs@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id g8JFTRa11104 for egs; Thu, 19 Sep 2002 11:29:27 -0400 (EDT) Date: Thu, 19 Sep 2002 11:29:27 -0400 (EDT) Message-Id: <200209191529.g8JFTRa11104@zinger.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 13 >From linga@CS.Cornell.EDU Thu Sep 19 11:27:39 2002 >Date: Thu, 19 Sep 2002 11:27:39 -0400 (EDT) >From: Prakash Linga >To: Emin Gun Sirer >Subject: PAPER #13 > > > >Power-aware routing optimization (PARO) > >A power-aware routing protocol which tries to minimize the transmission power >requirements in a mobile adhoc network has been proposed in this paper. >Intermediate nodes (called redirectors) choose to forward packets on behalf of >source destination pairs to reduce the power requirements for transmission of >packets. This optimization works in case when the destination is within range >of the source. In case of wide-area networks, local-energy saving coupled with >wide-area routing is used to forward packets when source and destination are >not within transmission range of each other. >Some important assumptions are: Radios can dynamically adjust their >transmission power levels. Also, transmission power required to send a packet >from node A to node B is almost the same as that required to send the same >packet from node B to node A. Transmission is much more power consuming than >reception or listening (and hence optimize on transmission power.) >Protocol tries to maximize the number of redirectors on the path from source to >destination to minimize power requirements (unlike traditional algorithms which >try to minimize the number of hops required.) Routes are discovered on-demand >(reactive). Every node adds the power level used to transmit the packet to >the packet header. Any node which overhears the transmission then takes note of >the power level used and based on the reception level calculates the power >required to reach the transmitting node. >Basic algorithm: At first, source directly communicates with the destination >(say, by sending the transmission at maximum power level). Some node which >overhears this transmission will calculate if it could reduce the power >requirements if it acts as a redirector. If so, it will inform the source and >the destination that it will act as a redirector using a route-redirect message >(and adds appropriate entries in the redirect table). Nodes which can further >optimize the power requirements will add on as redirectors. >There is also the route maintenance part where the routes are adapted to the >changing topology. This is done using some small enhancements to the >overhearing and redirecting part. Transmission level to the next redirector >is now sum of old estimate and delta where delta depends on the average speed >of the nodes in the network and the time since the next redirector was >overheard. If a node does not transmit any packets to any destination for >route-timeout period it proactively sends route maintenance packets. >Also, other nodes in the network can overhear transmissions to redirector nodes >and if any of these move the new nodes can elect to act as redirectors if that >helps. >Preliminary performance evaluation results are presented which validate the >protocol > >Pros: >A power-aware reactive routing protocol has been proposed in this paper. >Initial simulation/experimental results show the efficacy of the protocol. >This protocol works in differenct communication environments like sensor n/ws, >home n/ws, MANETs. > >Cons: >Simplitic assumptions like transmission power required to send a packet >from node A to node B is almost the same as that required to send the same >packet from node B to node A. >No thorough evaluation of the work. >This is a local optimization. Not clear if this works well in a larger network. > >Future directions: >-More thorough evaluation of the protocol especially is large networks. >-Testing performance of different applications running on PARO. >-Saving reception and listening power inaddition to transmission power. > From yao@CS.Cornell.EDU Thu Sep 19 11:43:07 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JFh7h24703 for ; Thu, 19 Sep 2002 11:43:07 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 13 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 19 Sep 2002 11:43:06 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D43024797E8@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 13 Thread-Index: AcJf80GyeMD18s/OQrqDB6Ek/Atozw== From: "Yong Yao" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8JFh7h24703 This paper introduces PARO, an on-demand adhoc routing protocol, which purpose is qutie different from other MANET routing protocols. PARO tries to minimize power consumed by packet transmisssion including route discovery. It is accomplished by adding as more nodes as possible to a route, if the new route is more energy efficient than the old one. It assumes that each node can dynamically adjust its transmission power and compute the minimal power required to commuincate with any of its neighbors. The main observation of the paper is that to route a packet over multiple short hops is usually cheaper than over fewer long distance hops, given the energy model for ad-hoc networks. There are three core components of PARO: overhearing, redirecting and route maintenance. A node keeps overhearing packets and compute the exact power to communicate with its neighbors. An internal nodes may volunteer to redirect packets between two nodes if it finds out that the total energy consumption can be reduced. In case of node mobility and failures, explicit signaling packets may be used for the maintenance purpose, and routes may be updated to reflect topology changes. PARO addresses a significant issue in adhoc network routing, but it still has some weaknesses. First, it assumes a fairly simple transmission and energy model. It dose not take the power consumption during reception and listening modes into account. The assumption that all nodes are located with the maximum transmission range of each other is not reasonable in practice. Second, a route with more hops could introduce longer delay and become less reliable. Finally, the route maintenance algorithm is very expensive and complex, which may have extra overhead to the whole network. Yong Yao From aed13@cornell.edu Thu Sep 19 11:57:16 2002 Received: from postoffice.mail.cornell.edu (postoffice.mail.cornell.edu [132.236.56.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JFvGh28206 for ; Thu, 19 Sep 2002 11:57:16 -0400 (EDT) Received: from andyd-laptop.cornell.edu (syr-66-67-66-109.twcny.rr.com [66.67.66.109]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA00069 for ; Thu, 19 Sep 2002 11:57:14 -0400 (EDT) Message-Id: <5.1.0.14.2.20020919114131.02e8cd48@postoffice.mail.cornell.edu> X-Sender: aed13@postoffice.mail.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 19 Sep 2002 11:57:11 -0400 To: egs@CS.Cornell.EDU From: "Andrew E. Davis" Subject: 615 PAPER13 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed The paper "Conserving Power in Wireless Ad Hoc Networks" introduces power conservation as a design goal for ad-hoc networks. The paper evaluates ad-hoc networks in situations where transmission power is the overwhelming power cost and assumes the nodes goal is to reduce their collective power usage during transmission. The paper proposes that the optimal routing solution, when quantified in terms of power usage is not the shortest hop solution, and that it is more optimal to transmit via a route involving multiple hops with nodes operating at less then maximum power. This is based on the premise that power usage climbs disproportionately to the gain in range. The protocol Power aware routing optimization(PARO) can be either implemented as the routing layer or just below the routing layer inserted at layer 2.5 to provide power efficiency benefits to existing MANET protocols. The optimization has three phases, overhearing, computing redirection and route convergence. The protocol begins by transmitting directly from point A to point B, and includes in the packet the power usage. Other nodes overhear the packet and compute if they could offer a route using less power. If such a route exists they inform the source and destination, and the next packet sent over the route will use less power. The protocol then converges to its optimal solution iteratively as other nodes may now eavesdrop and insert themselves into these two hops. The protocol converges as a function of the packets sent by the application specific layer above. The authors implemented PARO using commercial 802.11b technology and showed that despite implementation limits of the Aironet cards limiting them to fixed number of power levels they were able to achieve significant aggregate power savings. From ks238@cornell.edu Thu Sep 19 11:58:59 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JFwwh28355 for ; Thu, 19 Sep 2002 11:58:58 -0400 (EDT) Received: from ks238.cornell.edu (syr-24-24-18-11.twcny.rr.com [24.24.18.11]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA24469 for ; Thu, 19 Sep 2002 11:58:57 -0400 (EDT) Message-Id: <5.1.0.14.2.20020919115753.01ce4720@postoffice2.mail.cornell.edu> X-Sender: ks238@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Thu, 19 Sep 2002 11:58:46 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 PAPER #13 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed In this paper a new energy efficient protocol for mobile ad-hoc networks is introduced. The paper assumes a network in which all nodes are within transmission range of every other node (i.e. a small, clustered network is ideal for PARO). The critical assumption the protocol is based on is that the less distance between communicating nodes, the less powerful the transmission, and hence the more power is conserved. The protocol, which is quite simple, includes three main processes: overhearing, redirecting and route-maintenance. Overhearing is the process through which nodes include themselves into routes between source and destination nodes. After the destination node sends a communication transmission to the source node, those nodes that overhear this transmission will be viable intermediary nodes for the route. This intermediary or "redirector" node assesses, through a mathematical equation included in the paper, if its participation in the route will make a more energy efficient route. Then, if it is possible to have a more energy efficient route, this redirector node sends a redirect message to both nodes and becomes an intermediary node in the route, which will forward packets from source to destination. This process is known as redirecting. Overhearing and redirecting are iterative processes and continue until no intermediary node exists which thinks it can create a more efficient route (i.e .route convergence). The final process is route maintenance, which is critical to preserving the existence of the routes while little traffic is being transmitted. This is done by sending periodic data signals from source to destination keeping the route active. The authors include a pretty comprehensive simulation (one of the best seen thus far). Many of the concerns that I had while reading the paper were answered by the simulation's results. For instance, I felt that PARO would show a substantial decrease in the success rate of data transmissions in an actively mobile network since this would entail an increase in the number of iterations seen in the network, which I felt would cause diminishing results as far as energy conservation was concerned. However, it seems that this was not the case since route-maintenance was more efficient than was previously assumed. One question, which was raised in the beginning of the paper which was not addressed in the simulation was the idea of having varying packet sizes being transmitted (they used 100-byte packets). It would seem that larger data packets would need greater transmission power. So, in addition, to distance between nodes, the effect of packet sizes on energy efficiency should be addressed. Another problem with this protocol that you see with the examples provided is that nodes in the "middle of the network" will always be active and nodes on the fringe of the network will be conserving the greatest amount of energy. This might have diminishing returns in a more static topology with large amounts of data transfer since "middle nodes" would lose a substantial amount of energy being redirector nodes rather than losing energy communicating as source nodes. They are in a pretty unfortunate position in the network and this may hurt them in the long run when they need to communicate. From vivi@CS.Cornell.EDU Thu Sep 19 12:00:18 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8JG0Ih28502 for ; Thu, 19 Sep 2002 12:00:18 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper13 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 19 Sep 2002 12:00:17 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF6D@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper13 Thread-Index: AcJf9ahXmb9NXZP0QJ+DMhDjMxPhdQ== From: "Vivek Vishnumurthy" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id g8JG0Ih28502 PARO: The paper presents the PARO (a Power-Aware Routing Optimization) protocol. It aims to minimize the power consumption of the network as a whole, thus maximizing battery life and minimizing node and link failures. The basic mechanism used by this protocol is: When node A is talking to node B, and node C overhears this conversation and sees that by participating in this conversation as an intermediate hop, it(C) can lead to a decrease in the power consumption, it does so, by sending a "route-redirect" message to A. A similar means is used when it is discovered that there is a redundant link in a path and the redundant link is dropped. The protocol also handles the scenario where more than one node discovers that power-saving is possible, by giving preference to the node that leads to the maximum reduction of power usage.We see that even with a limited number of increase in the intermediate hops, there is a substantial reduction in the power-usage. The weaknesses of the paper: - The extra cost of having transmitters and receviers able to work with variable power levels has not been discussed. - It assumes bi-directional links. - The communication between A and B depends on the active involvement of an (hitherto) uninvolved node: This makes security hard to implement. - The source node has to transmit explicit signalling packets when there is no traffic: This could lead to substantial overheads. - In a situation where there is a path A-B-C and C lies just outside the range of the transmission range of A, the fact that power could be saved by having A transmit its packets directly to C is never discovered. - Parameters other than power used has not been taken into account. The simulation should have compared performance of this protocol with others in terms of parameters such as end-end throughput, delay, etc. We cannot conclude that because the protocol has good performance wrt one parameter, it is applicable. - In the simulation results shown (Fig 6), the transmission success ratio is less than 0.7 for a significant portion of the domain. This is not acceptable in most scenarios. The paper can be improved by making the simulation more rigorous, and making the route-restructuring more pro-active(eg: take into account the case mentioned above).