From eyh5@ee.cornell.edu Wed Sep 19 21:11:02 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8K1B1q19922 for ; Wed, 19 Sep 2001 21:11:02 -0400 (EDT) Received: from hegel (hegel.ee.cornell.edu [128.84.236.63]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f8K1B0711628 for ; Wed, 19 Sep 2001 21:11:00 -0400 Date: Wed, 19 Sep 2001 21:10:27 -0400 (EDT) From: Edward Hua To: egs@CS.Cornell.EDU Subject: 615 Paper # 12 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper introduces a power-aware routing optimization (PARO) protocol that is intended to minimize the aggregated transmission power need to transmit packets from a source to a destination. What sets this protocol apart from the others is that it uses data packets, not route-query packets, to seek out an appropriate route to reach the destination, and the explicit route-query signaling is used only when no data transmission takes place. This approach may save a lot of bandwidth which would have otherwise been used on the overhead information, but it may have a negative impact on the end-to-end time delay, thus making it somewhat inappropriate for time-sensitive applications such as voice communications. Also, the implementation of this protocol is better suited in a static wireless network as opposed to a MANET. The optimization of transmission power, or rather, the minimization of required transmission power, of a path is achieved by using the so-called redirectors, intermediate nodes that measure transmission power levels of their neighbors and construct links to the nodes requring minimal transmission powers. This approach is based on the design philosophy that the more redirectors along the path, the less the consumption of overall transmission power. Therefore, the protocol may attempt to bring in as many nodes as possible along the route to serve as redirectors. The downside of this approach is that several paths may find one particular node located at an optimal location to provide data relay simultaneously for all of them. In such a situation, the power will be quickly drained from that node, the worst case of which is a partitioning of the ad hoc network. The authors emphasize on the importance of conserving power when transmitting data packets in an ad hoc network. However, there should be more performance metrics that need to be tested in order to verify that the conservation of transmission power does not come at a cost of prolong time delay. Unfortunately, in the simulation performance section, no results are given to this regard. In the simulation figure 5, not much improvement is made between 30 and 100 nodes given the area of the simulated environment. In the same interval, the number of hops a packet has to go through before reaching the destination increased by 83%. It can be deduced from the figure that an upper limit is reached when nodal density becomes too high, and it may result in a worsening of time delay incurred. This figure may serve as a reference to the design of such a network employing this algorithm, reminding the designer not to overpopulate an area with excessive nodes. A further research topic may be to understand the intricacy between the nodal speed and the its impact on redirecting routes in the given area. From wbell@CS.Cornell.EDU Wed Sep 19 22:30:57 2001 Return-Path: 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.7) with ESMTP id f8K2Uvq28004 for ; Wed, 19 Sep 2001 22:30:57 -0400 (EDT) Received: from [192.168.1.101] (syr-66-24-16-64.twcny.rr.com [66.24.16.64]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id WAA17022 for ; Wed, 19 Sep 2001 22:29:47 -0400 (EDT) Subject: 615 PAPER #12 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Evolution-Format: text/plain X-Mailer: Evolution/0.13.99+cvs.2001.09.19.21.54 (Preview Release) Date: 19 Sep 2001 22:28:46 -0400 Message-Id: <1000952994.6291.14.camel@brute> Mime-Version: 1.0 12) PARO: Conserving Transmission Power in Wireless Ad Hoc Networks In this paper we are introduced to PARO, a power aware routing protocol which tries to minimize power consumption of routing packets through the use of redirectors which forward packets if closer to the destination than the source. PARO assumes that every node in the network can reach every other node via a full-strength broadcast, and is therefore less flexible than some of the previous routing algorithms, but would be useful for use in dense clusters to optimize power usage. PARO assumes that nodes have the ability to vary their transmission power during transmits. To this end, they develop a simple metric for evaluating the amount of transmission power required to contact a node and scale back transmission power accordingly based on the recent strength rating to that node. This reduces the amount of power used to communicate with that node, as well as reduces the chances of contention. They also observe that several intermediate nodes forwarding packets at lower transmission powers is more energy efficient than a single node doing a stronger transmission, even including the reception power overhead. To use this idea, nodes can volunteer to become what they call redirector nodes if they overhear a transmission between two nodes in which they could be an intermediate node. Thus, as the network stabilizes, more and more redirectors volunteer to be intermediaries for packets, and less power is consumed in transmission. The idea of having redirectors offer their services to aid the network was interesting from a whole bunch of perspectives. We see the first place where a node is not bound by a routing protocol to do something that might not be in it's best interests; as it can choose to aid the rest of the network or not by being a redirector. This property has a large number of good properties, as lightweight and low power nodes could opt to not aid the overall network in order to lower resource usage and maximize node lifetimes. Nodes that are known to be highly mobile could not volunteer to be a redirector, as the overhead of updating routes would be uneconomical. One could also see a requirement for a redirector would be to be a node who has been stable for a certain period of time. This freedom to not aid the network also is useful from a security perspective, as a node can avoid being overused by removing itself from being a redirector. It would be useful to investigate a network where routing was not a distributed effort where everyone runs the same algorithm, but instead nodes making local policy decisions to help the network stability in ways that make sense for individual nodes. From c.tavoularis@utoronto.ca Wed Sep 19 23:53:32 2001 Return-Path: Received: from bureau6.utcc.utoronto.ca (bureau6.utcc.utoronto.ca [128.100.132.16]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8K3rVq05196 for ; Wed, 19 Sep 2001 23:53:31 -0400 (EDT) Received: from webmail3.ns.utoronto.ca ([128.100.132.26] EHLO webmail3 ident: IDENT-NOT-QUERIED [port 34903]) by bureau6.utcc.utoronto.ca with ESMTP id <239509-10516>; Wed, 19 Sep 2001 23:53:18 -0400 Received: by webmail3.ns.utoronto.ca id <414676-5765>; Wed, 19 Sep 2001 23:52:59 -0400 To: COM S 615 Subject: 615 PAPER 12 Message-ID: <1000957969.3ba96811b996e@webmail.utoronto.ca> Date: Wed, 19 Sep 2001 23:52:49 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7BIT User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper introduces the on-demand adhoc routing protocol PARO whose purpose is to minimize power consumed by packet transmission including route discovery. This is accomplished by routing data packets over multiple minimum-power hops even when a single high power hop is possible. This protocol does not exploit the broadcasting abilities of wireless networks, which are found to consume more energy. Instead, it transmits node to node, and assumes that each node can dynamically adjust and hence minimize transmission power. In practice, power can only be approximated therefore the power used should be padded to accommodate error as well as increases due to node mobility. If a path does not exist in its redirect or overhear tables, a source initiates a path by transmitting at full power directly to the destination. Intermediate nodes that can hear communication from the source and destination can advertise to become redirectors along the path. To ensure only one node is elected, nodes are delayed before transmitting based on the required power they would add to the path. The node with the least required power will transmit first, and will become the redirector. Upon this, other nodes will either cancel their message or be rejected at the source. With each subsequent data packet sent, intermediate nodes continue to add themselves to the path, until eventually the path converges. This algorithm functions effectively in fixed wireless networks but requires modification in the presence of node mobility (or low traffic scenarios). Specifically, the algorithm cannot rely on data packets for routing, and must add signaling packets to keep up with the rate of topological changes. Also, nodes may move out of range during communication, causing transmission failure and time delay. To account for potential motion, a sending node will increase its sending power by delta with each transmission. This protocol also performs node removal when a node is no longer beneficial. An intermediate node will be able to detect transmissions to and from the ineffectual node, and will notify the source and destination to remove it from the path. In simulation, PARO successfully reduces power transmission, but the analysis of QoS in this paper is insufficient. The challenge with this protocol is calculating the minimum power, which could weigh heavily as processing overhead. Time delays should also be evaluated. PARO fairs poorly in the event of high mobility because the algorithm cannot keep up with topological changes. There are many questions to be raised, here are a couple: how does PARO initiate a path with a node that cannot be reached in one hop (may need to combine PARO with another routing protocol)? Is there a point when too many redirectors have been added to a path? How is transmission power a function of packet size (RTS messages are frequent and always sent at maximum power)? The overall contribution of this paper is significant because it shows the power efficiency of node to node routing, while broadcasting is so often favored in adhoc routing. From daehyun@csl.cornell.edu Thu Sep 20 00:45:36 2001 Return-Path: Received: from wilkes.csl.cornell.edu (wilkes.csl.cornell.edu [132.236.71.69]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8K4jZq10646 for ; Thu, 20 Sep 2001 00:45:35 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id AAA25991 for egs@cs.cornell.edu; Thu, 20 Sep 2001 00:45:30 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109200445.AAA25991@wilkes.csl.cornell.edu> Subject: 615 PAPER 12 To: egs@CS.Cornell.EDU Date: Thu, 20 Sep 2001 00:45:30 -0400 (EDT) X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit This paper proposes a routing algorithm called Power-Aware Routing Optimization (PARO), which is designed to minimize the transmission power. The main idea of PARO is to use intermediate nodes called Redirectors which forward packets to reducing the aggregate transmission power. It is based on the principle that one long distance transmission takes higher power than multiple short transmissions. This approach is quite different from other routing algorithms we have discussed in the class. Those algorithms try to find the shortest path minimizing the number of intermediate nodes. But PARO tries to maximize the number of redirectors. The following is the three core algorithms. 1. Overhearing : Overheard packets are used to maintain the overhear table, which contains the information about the range of neighbors. The overhear table is used to determine the transmission power. 2. Redirecting : If a intermediate node is good for power savings, it becomes a redirector and updates the redirect table which is used for routing. Redirection is composed of two operations - Compute redirect and transmit redirect. 3. Route Maintenance : Data packets are used to communicate the routing information. But, explicit signaling packets may be used for the maintenance purpose, if required. In my opinion, the main contribution of this paper is that it tries to pay attention to the transmission power problem and proposes a algorithm to solve it. I'd like to point out the followings; 1. PARO maximizes the number of intermediate nodes. I think, though this might be good for the transmission power, it make the route maintenance worse. As a route is getting longer, the probability of link failures is also getting bigger, which means more maintenance overhead. And it will be much worse in mobile ad hoc networks. 2. Basically, PARO is a 2.5 layer algorithm, which lacks of route discovery method. Therefore, it needs to be integrated with other routing algorithm. In that case, the ideas in this paper might not be valid any more. for example, as I said above, increasing the route length doesn't help always. I think it is important to find out a optimal point in this trade-off. From mh97@cornell.edu Thu Sep 20 01:34:36 2001 Return-Path: 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.7) with ESMTP id f8K5Yaq14842 for ; Thu, 20 Sep 2001 01:34:36 -0400 (EDT) Received: from mars (syr-66-24-28-66.twcny.rr.com [66.24.28.66]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA05540 for ; Thu, 20 Sep 2001 01:34:33 -0400 (EDT) From: "ming hao" To: "'Emin Gun Sirer'" Subject: 615 PAPER 12 Date: Thu, 20 Sep 2001 01:34:05 -0400 Message-ID: <000401c14195$dd8b21e0$6c01a8c0@mars> MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit X-Priority: 3 (Normal) X-MSMail-Priority: Normal X-Mailer: Microsoft Outlook, Build 10.0.2616 X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 Importance: Normal In-Reply-To: <200109181320.f8IDKv601498@hoho.cs.cornell.edu> Conserving Transmission Power in Wireless Ad Hoc Networks this papers proposes a power awaring routing algorithms. the idea is that adding intermediate nodes to forward messages can save teh power. i think this is very interesting point. the assumption is that symmetric comunication model and nodes can overhear packets sends by other nodes. And they can all reach other. it works in three steps: 1. source node sends signal msg containing the power it needs. 2. other nodes who overhear the packet compute the power it needs to forward the packet based on a simple two-ray model. 3. if it can saves power, it sends redirect msg. then route is established. simulation results shows it indeed can save power and more than 3 redirectors does not help a lot. in order to support mobile nodes, several enhancements such as adding slice intervel, sending signal message and so on. but selecting slice intervel is hard and sending additional msg consumes power. further, moving nodes can results in sending failure. the paper gives simulation results about relationship between success ratio and interval of transmitting and node speed. it shows only when interval is high and speed is high at the same time, success ratio drops. but ti did not show how power saving performance of the algorithms. the implementation proves that adding redirector can save power. it would be better if measuring power saving when those notebooks runs the algorithms. this is a good and original paper. but one main drawback is that it has limited application range because it requires that each node can reach all the other nodes if using max transmission power. it is unclear how the route is dicovered if the assumption is violated. -ming From ramasv@CS.Cornell.EDU Thu Sep 20 09:08:29 2001 Return-Path: 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.7) with ESMTP id f8KD8Tq29206 for ; Thu, 20 Sep 2001 09:08:29 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: cs615 PAPER 12 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Date: Thu, 20 Sep 2001 09:08:28 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F26F@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 12 Thread-Index: AcFB1VVyxaeJ06ulEdWTbwCQJ5m7oA== From: "Venu Ramasubramanian" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8KD8Tq29206 PARO: Conserving Transmission Power in Wireless Ad Hoc Networks The protocol presented in this paper is an attempt to conserve power and extend the lifetime of a wireless ad hoc network by finding routes that have minimum total transmission power. The protocol assumes the ability of nodes to send each packet with a different transmission power. Under this assumption, it can be shown using path propagation models that using two transmissions through an intermediate node to reach a destination often consumes less power than directly reaching the destination. PARO is a protocol that starts with a one hop route and then increases the route length till the point transmission power could be saved. Each node in PARO is expected to overhear packets that are sent between different nodes. It then estimates based on the transmisson power of the sender (mentioned in the packet) and a suitable propagation model, the distance between the sender and itself and hence the optimal transmission power needed to reach the sender (assuming symmetry). Thus PARO always tries to estimate the optimal power to reach a node. If nodes are mobile, a safety factor is added to the estimated distance. PARO might sometimes force nodes to send dummy packets so that its estimation of distance could be accurate. Thus PARO may not work if the propagation is asymmetric due to obstructions or noise. Further, it assumes that each node can reach all other nodes by transmitting at a maximum power. This means PARO saves power only in small dense networks. Any intermediate node overhearing PARO also estimates the power consumption if the packet were routed to the destination using itself as a redirector. If this power is less, it sends redirect message to the source asking it to route packets through it. This is the core of the protocol. The intereseting aspect of this is that it converges quite quickly (depending on data rate) in static networks. However in mobile networks, the convergence may be affected by mobility. Also the possibility of a redirector moving out and hence no longer optimal needs to be considered. The suggestion to solve this probelm in the paper does not look very effective. The performance presented in the paper actually shows that PARO can save significantly in static networks. However the packet delivery drops significantly even in networks with reasonable mobility and when data rate is lower. Further PARO assumes that the transmission power is much higher than reception power. The difference between the two is not very high for many radios. Although PARO is a very elegant protocol, it makes several assumptions and hence its applicability in general ad hoc networks may be questionable. From papadp@ece.cornell.edu Thu Sep 20 10:09:43 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.239.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8KE9hq06048 for ; Thu, 20 Sep 2001 10:09:43 -0400 (EDT) Received: from mill (mill.ee.cornell.edu [128.84.236.64]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id f8KE9h722066; Thu, 20 Sep 2001 10:09:43 -0400 Date: Thu, 20 Sep 2001 10:02:44 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-Sender: papadp@mill.ee.cornell.edu To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 12 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "Conserving Transmission Power in Wireless Ad Hoc Networks," by J. Gomez, A.T. Campbell, M. Naghshineh, C. Bisdikian. Panagiotis Papadimitratos, papadp@ee.cornell.edu The proposed here routing protocol addresses the important, in the MANET context, issue of power conservation. The limitations imposed by the technical characteristics of the mobile nodes render data transmissions costly, while the functionality of the routing protocols themselves places a signaling overhead that not only consumes bandwidth but also reduces the node (and, consequently, the network) lifetime. Power-Aware Routing Optimization (PARO) goal is to tackle exactly this problem; it attempts to minimize the transmission power required for data forwarding. The minimization is relative to the total power consumed by all network devices, and it is performed, in approximation, by a distributed heuristic algorithm. The protocol, as it will become obvious by the following discussion, is designed for or targets at networking environments where full connectivity could be achieved (at the expense of power consumption, or waste). Examples are wireless local area networks (WLANs), (one-hop) personal-area, home, and sensor networks. The route discovery is performed on-demand, and is initiated by the source, which transmits at maximum power in order to reach the destination. After the first data transmission takes place, any intermediate node that can overhear both source and destination is capable of determining whether there is space for improvement. The basic idea is that the transmission over two hops may require less power than the single- hop one, and nodes can take advantage of this fact, assuming they are able to adjust their transmission power level. A simple illustration of the intuition behind this idea can be provided with the help of the log- normal propagation model, that relates received power and distance, and is in concert with the broadly used conceptual view of the multi-hop connectivity. Intermediate nodes overhear data packets, extract power-related information placed in the headers by the transmitting node, and estimate the minimum required power to reach the node in question (that transmitted the packet). If the minimum required power for the single hop is higher than the sum of the minimum power values for each of the two incident hops, the intermediate node sends a re-direct message. This message is addressed to the two nodes incident to the link to be replaced. The use of the two new hops allows more overhearing nodes to update their estimation, and, apparently, this procedure repeats itself recursively until no further improvement is possible. A similar approach is proposed in case of medium mobility, which requires supplemental explicit periodic signaling when no data transmissions are due. Furthermore, an increment of the transmission power by a constant, that depends on the average speed of nodes and the lastly measured beaconing (or transmission) interval, addresses the issue of route maintenance: the 'probability' of reaching the next hop node is increased accordingly. The increase of the number of hops yields an apparently decreasing, concave power consumption decrease function, which achieves the sought minimum only approximately. Moreover, the distributed execution and the absence of corrective 'moves' may result in a large distance from the actual optimum. Nonetheless, there is an indication that the few initial iterations yield, indeed, substantial improvements, without any further evaluation of the convergence properties of the algorithm. The issue of a storm of route-redirect messages is also significant, since it may result in spurious control traffic. Finally, the route maintenance evaluation indicates that the scheme is appropriate for quasi-static or 'walking' networks. In conclusion, the authors approach an important issue, but they present a scheme of ascertained applicability, they do not take into consideration other significant power consumption factors, such as receive or idle node states of the mobile nodes, and do not provide a clear comparison with competitive schemes. From avneesh@csl.cornell.edu Thu Sep 20 10:47:24 2001 Return-Path: Received: from capricorn.ds.csl.cornell.edu (capricorn.csl.cornell.edu [132.236.71.92]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8KElOq10529 for ; Thu, 20 Sep 2001 10:47:24 -0400 (EDT) Content-Class: urn:content-classes:message Subject: 615 Paper 12 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Thu, 20 Sep 2001 10:52:09 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Message-ID: <97C142C1212ED545B0023A177F5349C4053A93@capricorn.ds.csl.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper 12 Thread-Index: AcFB49LHxVjuQ3sFTfugKEZOrj9Ibw== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8KElOq10529 Conserving transmission power in Wireless Ad Hoc Networks: Summary/critique The paper describes the design of PARO, power aware routing optimization, where the main goal is to reduce the power requirements of the mobile device within the adhoc network, by increasing the number of intermediate devices (redirectors) to send a message from source to destination. This reduces the power required by a particular node to send a packet directly to a far off but reachable destination. Simulation studies done with this optimization bring the optimum number of redirectors to about 3, before the latency effects of the multiple hop solution start dominating the performance. PARO requires that : a. Radios are capable of dynamically adjusting the transmission power used to communicate with other nodes. b. Interference free MAC. c. The cost function chosen depends on the aggregate transmission power to forward a packet to a node as in an idealized communication device, other processing costs are ignored. The working of the protocol is fairly simple, it is an on demand protocol, and a node that hears both source and destination sends a route-redirect packet which implies that the listening node is willing to be a redirector and thus can provide a more power efficient route. The main operations are 'overhearing', redirecting and route maintenance. 'Overhearing' involves a two ray propagation model. Multiple redirects can be prevented by mediating upon the optimization percentage of adding the particular redirector before actually sending the route-redirect message. Finally, the low power route finding is an iterative process, which might not give a route with the minimum transmission power, unless an exhaustive search is used. Mobility issues are solved using a silence interval after which route-maintenance packets are sent to address the problems of a particular redirector moving out of the min power range. Similar optimizations are required to remove a sub optimal redirector from an existing route. PARO addresses a significant issue in adhoc network routing, and I think that paper was well written. Some comments: a. PARO assumes a fairly simplistic transmission model, and does not take into account within the cost function, other processing costs. I think that these may play an important part in the overall performance of the protocol, especially when the mobility of the nodes is high. There seems to be more work required when the mobility increases, which raises doubts about the performance. b. It is interesting to note that power savings are not really that high after 3 redirectors, which could get worse once the above mentioned factors come into play. c. Finally the algorithm seems to work very well for static networks, in terms of convergence etc.But when nodes are mobile there might be many situations especially in a dense network, where the transmitting power levels may be the same or nearly the same for many nodes. So here, the algorithm will start computing the opt values but there might not be a large difference within those opt values. Hence at this point it would have been interesting to see how the convergence properties worked. From gupta@CS.Cornell.EDU Thu Sep 20 10:52:26 2001 Return-Path: Received: from ringding.cs.cornell.edu (ringding.cs.cornell.edu [128.84.96.109]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8KEqPq11060 for ; Thu, 20 Sep 2001 10:52:26 -0400 (EDT) From: Indranil Gupta Received: (from gupta@localhost) by ringding.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8KEqPY06592 for egs@cs.cornell.edu; Thu, 20 Sep 2001 10:52:25 -0400 (EDT) Message-Id: <200109201452.f8KEqPY06592@ringding.cs.cornell.edu> Subject: 615 PAPER 12 To: egs@CS.Cornell.EDU Date: Thu, 20 Sep 2001 10:52:25 -0400 (EDT) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit -----START----- Conserving transmission power in wireless ad hoc networks. Gomez, Campbell, Naghshineh, Bisdikam. Reviewer: Indranil Gupta. Summary: This paper presents PARO (power aware routing optimization), an algorithm that attempts to minimize the power used along a route, without explicitly trying to maximize lifetime of nodes. The algorithm used is simple: the sender sends a broadcast at the highest possible power level, the receiver hears it directly and replies. Then, iteratively, intermediate lying nodes that overhear these conversations and realize that routing through them would conserve power, become "redirectors". The authors algorithms seem to target long lived connections that have lower (relative) cost for route set up. Some of the authors' algorithms for maintaining routes when nodes move etc. are rather ad-hoc (in a negative sense) or even questionable - examples include sections 4.2 and 4.3. Simulations reveal that that PARO algorithms do well when there is small mobility, or small inter-packet delay (as all control messages are piggybacked on data messages). The authors conclude PARO to be superior to link state routing protocols (MLSR), but the simulation plot is questionable. Comments: - For the authors setting of simulation parameters, MLSR is unstable (causes partitions) for transmission ranges of Dmax/4, while consuming as much power as PARO. For a different setting of simulation parameters (eg., higher node density), MLSR might easily be made to perform better than PARO. - One of the better properties of the PARO algorithms is that senders and receivers (nodes) typically spend more power (at least initially) compared to intermediary nodes. This does seem to be 'fair' in the sense that PDAs that are the origin of more packets should have to spend more power than other intermediary nodes. - The authors never explain what happens when a node cannot reach its destination in the 'first big broadcast'. This is entirely possible as nodes' maximum transmission ranges are limited. - Studies on battery life [Peukert 95, Chiasserini and Rao 99] show that battery life time reduction is not linear in the transmit power / drawn electric current. A doubling of power (thus electric current from the battery) results in a battery lifetime reduction by 2^h, where is a factor typically more than one (in the range 1.03-1.5). This means that transmitting at higher powers (at the sender and receiver of the route) will quickly deplete the battery at those nodes. A much better overall network lifetime (even individual node lifetime) could be obtained by using longer routes where all links are 'short'. - Senders and receivers broadcasting at large powers would cause contention at nodes very far in the network (consider the sender and receiver at two ends of the network area), thus defeating the effectiveness of power conserving algorithms. -----END----- From teifel@csl.cornell.edu Thu Sep 20 11:04:14 2001 Return-Path: Received: from disney.csl.cornell.edu (disney.csl.cornell.edu [132.236.71.87]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8KF4Dq12283 for ; Thu, 20 Sep 2001 11:04:13 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8KF48s86856 for ; Thu, 20 Sep 2001 11:04:08 -0400 (EDT) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Thu, 20 Sep 2001 11:04:08 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 12 Message-ID: <20010920105111.J70092-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII PARO: This paper presents routing protocols for power-aware applications. When energy is a design constraint in ad hoc networks, routing protocols that achieve high bandwidth are not necessarily _good_ from a energy efficiency standpoint. Rather than transmitting at full power, energy may be saved by transmitting at lower power levels and by using redirector nodes to propagate packets to the destination--rather than transmitting directly to the destination node. The PARO protocol attempts to insert redirector nodes into routes, so that the transmission power levels can be reduced. Energy-efficient routing protocols must consider energy dissipated in both packet transmission and route discovery. To facilitate this energy tradeoff, an energy metric is presented that attempts to minimize only routing power. Although I am not sure that this is the _best_ metric to use for all power-aware adhoc networks--some may be less energy-constrained then others and may justify a metric that weights bandwidth more. PARO is mainly a localized optimization, for routing protocols that operate across dense nodes. They study the density effect on this protocol in the paper, but I thought Figure 5 was a bit lacking--only 3 data points. The other simulations seemed to be more extensive than the one mentioned above. From ranveer@CS.Cornell.EDU Thu Sep 20 11:38:21 2001 Return-Path: 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.7) with ESMTP id f8KFcKq16127 for ; Thu, 20 Sep 2001 11:38:21 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 12 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Date: Thu, 20 Sep 2001 11:38:20 -0400 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 12 Thread-Index: AcFB6jqki3dkoq3YEdW5awCQJ59Etw== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8KFcKq16127 Conserving Transmission Power in Wireless Ad Hoc Networks This paper proposes a power aware routing algorithm(PARO) that is based on the idea that it is possible to conserve the net power of a transmission by having it go through intermediate nodes that are sending with lower power. So an intermediate node on hearing a transmission could decide whether it should include itself in the route as a redirector. Modifications are then proposed to handle mobility and simulation results are presented. The main contribution of this paper is the idea of using intermediate nodes in routes to conserve power. In fact the bigger contribution is that it highlights the use of another metric for routing. While most of the routing algorithms concentrate on the shortest distance and end-to-end delay, PARO introduces power as an important metric to be considered for routing. However, PARO has a few problems: (a) It assumes a per-packet transmission capability. This is not provided by most of the wavelan cards available in the market. The technique itself is flawed if you have a number of packets for different destinations, implying you constantly need to keep changing your transmission power and this in itself is an extra overhead. (b) For calculations at the nodes, a fixed bandwidth is assumed. This might not always be the case, as 802.11b has varying bandwidth depending on the strength of the signal, i.e. 11Mbps, 5.5Mbps, 2Mbps.. (c) The PARO model is based on a clique. This is unrealistic for most scenarios. However, PARO could be integrated with other distance-based routing protocols as an add-on to conserve power. The performance could be interesting. (d) PARO tries to minimize the overall power consumption of the network. This could result in a particular node becoming a redirector for a number of parallel sessions(although it was originally not a part of even a single one). So this node could be depleted of its battery power much earlier. (e) The caculations done by PARO do not take into account the control overhead. On the other hand they mention that that the RTS/CTS packets are sent at the maximum power. So if there are more redirectors, more RTS/CTS packets would be sent, and so the network would end up losing more power for sessions of short duration. (f) The simulations for the mobile case are incomplete. It shows how successful the transmissions are but does not show how much power is saved. With recovery also consuming a significant power, this measure would be interesting. In fact since PARO is based on power awareness, this metric is significantly important for a mobile environment. (g) There is no support for unidirectional links. Besides, listening in promiscuous mode is not very effective. It usually results in a relatively low percentage of packets received, since there is no RTS/CTS for its communication. Although PARO works without it, it may actually never converge on the best route. From viran@csl.cornell.edu Thu Sep 20 12:02:46 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8KG2kq19051 for ; Thu, 20 Sep 2001 12:02:46 -0400 (EDT) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8KG2e867963 for ; Thu, 20 Sep 2001 12:02:40 -0400 (EDT) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Thu, 20 Sep 2001 12:02:40 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 12 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII PARO The PARO paper describes power optimizations for on-demand ad-hoc networks based on maximizing the number of nodes along a path such that each node can transmit with lower power. It relies on the nodes being able to dynamically control their transmission power output, and computing distance and required transmission power by monitoring the data packet transmissions (promiscuous mode is necessary). If an intermediate node not on the current route hears the message, and it determines that it has a lower transmission cost, then it sends a route redirect request to the originator of the packet telling it to re-route through this new intermediate node. This is an iterative process, since only one leg can be added to the route per data packet. Their hardware implementation doesn't really address the issues here, since they don't mention what size network they used, and it seems just a feasability study on calculating transmission powers. In their simulation, there doesn't seem to be any detail about how many retransmits occurred (due to the lower power output). They don't take into account the fixed cost of how much power the node uses to implement this scheme, nor even total non-transmission power consumption. If this is a significant fraction of the power output, then this scheme may not be worth it. Also, it seems like this scheme would actually increase power consumption in networks with low utilization, since it needs to send route-maintenance packets if not enough data packets are being transmitted. I'm not convinced that their scheme of increasing the number of nodes just to decrease individual transmission powers will actually save power, since it seems like the total power consumption in the network goes up because many more nodes are active. From jcb35@cornell.edu Thu Sep 20 12:23:05 2001 Return-Path: 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.7) with ESMTP id f8KGN5q21305 for ; Thu, 20 Sep 2001 12:23:05 -0400 (EDT) Received: from kafka (syr-66-66-30-147.twcny.rr.com [66.66.30.147]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA06105; Thu, 20 Sep 2001 12:22:57 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f8KFq5P04265; Thu, 20 Sep 2001 11:52:06 -0400 Date: Thu, 20 Sep 2001 11:52:00 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU cc: jcb35@cornell.edu Subject: 615 paper 12 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper discusses PARO, a power aware routing optimization that helps to reduce the transmission power needed to forward packets over ad-hoc networks. They discuss the mechanisms of PARO, how it works as a routing protocol, and how it uses mac-level adjustments of power and reflector nodes to reduce the amount of power consumed over links. They discuss its effectiveness on static and mobile networks and end with an evaluation of a simulation and comparison to other power-aware routing algorithms. The basic idea behind PARO is that it is cheaper to send a message over a couple of hops, each using a low power setting, than it is to send the message once using a high power setting. The algorithm begins when a destination sends a message to a source directly - after this initial packet goes out, PARO will start to work to reduce the power required to keep the link up. PARO works through a few methods: - overhearing - the overhearing algorithm process packets that are received on the MAC layer to keep a cache about the nodes they hear and the minimum power required to communicate with them. - redirecting - when a node overhears a transmission request, it can determine from its routing table whether it is cheaper to act as a reflector" and forward messages along a path. If so, it sends a route-redirect message out. Multiple intermediate nodes may simultaneously vie to become redirectors - in this case, the source node picks the route with lowest power usage, and then the algorithm can begin again with the links along the new route. - route maintenance - if an node determines that by routing through it that the route can reduce power consumption, they will send out a route-redirect message out. Simulation revealed that this algorithm worked best with densely populated graphs. Also, comparisons against MSLR showed that PARO was effective in conserving power on ad-hoc networks. comments: The simulation results were interesting, but they showed only the results for power use - I would have liked to see more comparisons to other protocols such as DSR or AODV to see how much better this worked (at least to get a ballpark idea). But I wasn't quite clear if this was just an optimization to sit inside DSR or AODV, or a routing protocol itself. Along those lines, if this is supposed to stand by itself (ie it's own protocol), how does it handles disconnections - what happens if routes get cut off, or if a source can't contact a destination in the first place? And what about all the other things ad-hoc routing protocols worry about? I wonder about the assumptions that the paper makes about the mac layer are valid. Also, the paper mentions that the algorithm doesn't find the _optimal_ route, but instead just finds a route that does conserve power - I would have liked to see more justifications why this was a good decision. From andre@CS.Cornell.EDU Thu Sep 20 12:35:10 2001 Return-Path: Received: from sundown.cs.cornell.edu (sundown.cs.cornell.edu [128.84.96.20]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8KGZAq22581 for ; Thu, 20 Sep 2001 12:35:10 -0400 (EDT) Received: from khaffy (mail@dhcp99-178.cs.cornell.edu [128.84.99.178]) by sundown.cs.cornell.edu (8.11.3/8.11.3/R-3.6) with ESMTP id f8KGZ9i09336 for ; Thu, 20 Sep 2001 12:35:10 -0400 (EDT) Received: from andre by khaffy with local (Exim 3.32 #1 (Debian)) id 15k7g7-0005gY-00 for ; Thu, 20 Sep 2001 12:31:59 -0500 Date: Thu, 20 Sep 2001 12:31:59 -0500 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: egs@CS.Cornell.EDU Subject: 615 PAPER 12 Message-ID: <20010920123159.A21840@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.20i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= This paper (Conservating Transmission Power in Wireless Ad Hoc Networks) makes the point of reducing the power used for tranmitting messages by adding nodes to the route currently used. If a node in between 2 communicating hosts hears both sender and receiver, it computes how much energy a route using itself as an intermediary hop would consumme (the transmission are done at minimal possible power, and the power is in 1/d^n where n is between 2 or 4), and add itsefl to the route if better. The system is designed to that, if there are many nodes being better, those with the biggest improvment will anwser first. While the scheme saves some power, we need to realise that it converges towards a good route, which by no means is the optimal one (the paper tend to assume so, but doesn't proove it). They also assume that all nodes can reach any other node transmitting a full power. This is far from true in most of the ad hoc network out there. They say you can combine both, by letting their PARO adding some nodes once the overall route is found. This can miss huge gains (think of a circle, 3 nodes far appart on one side, 4 close on the other side). I think power aware are interesting schemes; if the issue is of importance, it should be considered at the top level, and be fair for the intermediary nodes, not only reduce the overall power consumption. -- André Allavena (local) 154 A Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE