From eyh5@ee.cornell.edu Wed Sep 19 20:45:04 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 f8K0j4q17475 for ; Wed, 19 Sep 2001 20:45:04 -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 f8K0j3711245 for ; Wed, 19 Sep 2001 20:45:03 -0400 Date: Wed, 19 Sep 2001 20:44:30 -0400 (EDT) From: Edward Hua To: egs@CS.Cornell.EDU Subject: 615 Paper # 13 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper advocates the use of mobile node's power consumption as a metric in designing routing protocols for mobile ad hoc networks. To this end, the author proposes four power-efficient routing protocols, namely, Minimum Total Transmission Power Routing (MTPR), Minimum Battery Cost Routing (MBCR), Min-Max Battery Cost Routing (MMBCR), and Conditional Max-Min Battery Capacity Routing (CMMBCR). Although the objectives set by the author in this paper are to grant fair-share use of all nodes in the network and to minimize the overall transmission power of each route, he admits in the conlucsion that this is impossible to do, and some kind of trade-off is required to balance the two. The fundamental idea behind the proposed four routing algorithms based on nodal power consumption is that the source should choose the route with the least power consumption. In reality, whether this approach is suitable is questionable. Suppose a network carries a number of heterogeneous sessions, each requiring a different level of Quality of Service (QoS). Clearly, basing the choice of route on minimal power consumption is undesirable as, say, a multimedia stream of packets may have to do with less power along the route while a short message service (SMS) packet enjoys greater power consumption. The simulation results provide the performance evaluation by comparing the life expectancy of mobile nodes employing the proposed algorithms with that of the more traditional shortest-path and stability-based algorithms. It would be better, however, if the results also examined the effect of power-efficient routing algorithms on the end-to-end delay and the transmission success rate. The power consumption of each mobile node in an ad hoc network should be designed with as little reliance on the changing network topology as possible. As the author points out, if the power consumed by communication-related traffic is on the same order as the power consumed by non-communication-related overhead (e.g., internal functioning of a node), the supposed advantages of power-efficient routing algorithms are no more. On the other hand, as can be seen from Figure 3a and Figure 5, the performance of two of the proposed algorithms, MMBCR and CMMBCR, is barely on par with the traditional shortest-path and stability routing techniques. Given the results shown in the simulations, it appears much work needs to be done to address the issue of balancing power consumption and accessibility in a mobile ad hoc network. From wbell@CS.Cornell.EDU Wed Sep 19 22:29:37 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 f8K2Taq27965 for ; Wed, 19 Sep 2001 22:29:36 -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 WAA15196 for ; Wed, 19 Sep 2001 22:28:54 -0400 (EDT) Subject: 615 PAPER #13 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:32 -0400 Message-Id: <1000952969.6268.12.camel@brute> Mime-Version: 1.0 13) Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks This paper focuses on the idea that although optimality of routes and latency are large issues in ad-hoc networks, power consumption is a much larger issue that needs to be taken into account for routing. They outline the desirable properties of a routing algorithm including loop freedom, efficient bandwidth utilization and efficient batter usage, as well as unidirectional link support. They seemed to have a good grasp on the important issues in a heterogeneous network, such as the different transmission powers of different nodes [hence the unidirectional requirement] as well as variable usage of battery power. The proceed to concentrate on various routing schemes that optimize the power usage of various nodes, either in a minimum power usage model, or a maximum lifetime of hosts of the network model. This presents an important insight: optimizing for the minimum power usage does not provide the longest lifetime of hosts, as certain key hosts will be drained more quickly because of their position in the network. They conclude with simulations as to the use of their protocols with respect to the expiration sequence of the hosts in the network. The insight here was solid, although I felt the analysis and framework was somewhat weak. They begin with a good cross section of the issues of a routing protocol [catching things that are commonplace in actual environments, such as different transmission power for different nodes], but then proceed to show/describe algorithms that make harsh assumptions about the homogeneity of the underlying network. Although we are interested in ad-hoc networks, I don't feel it's unreasonable to make the assumption that different nodes will have different power consumptions [and some might even be not on batteries, and should be weighted more heavily.] Their protocol, since it was not described in great detail, should have left room for additional weighting terms in the routing decisions. The power discussion brings up a fundamental issue that's been neglected thus far except with respect to security issues; there's an incredible amount of trust going on that no one abuses another's resources [and in this case, the incredibly finite power resource.] Hence, we're all assuming that everyone plays fair. An important enhancement to these algorithms would be to make them more framed in the view that nodes are donating resources to the common good rather than explicitly forced to give them via always reacting to other nodes forwarding requests. This would provide a better framework for individual nodes to make decisions based on their own configuration [of available bandwidth or power] to make decisions on how much they want to aid the network. This would also be an appropriate framework to assess security issues [especially denial of service issues.] From mh97@cornell.edu Thu Sep 20 01:32:29 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 f8K5WTq14814 for ; Thu, 20 Sep 2001 01:32:29 -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 BAA02601 for ; Thu, 20 Sep 2001 01:32:26 -0400 (EDT) From: "ming hao" To: "'Emin Gun Sirer'" Subject: 615 PAPER 13 Date: Thu, 20 Sep 2001 01:31:57 -0400 Message-ID: <000301c14195$91abc310$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> Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks the algorithms proposed by the author is a variant of MMBCR and MBCR. in order to achieve the gold to maximize battery life of each node and use them fairly, the new algorithms introduce a threthold and switch to MBCR if each node along the route has a capacity bigger than the threshold, otherwise, switch to MMBCR. th algorithms proposed by this paper lacks creativity. but this paper greatly summarize the aspects in saving power for ad hoc network. there are many good points deserving mentioned here. good point; 1. unnecessary transmission power can interfere other nodes and make them increase the transmission power. 2. not eager to do retransmission or increasing power 3. overhearing(consume power) 4. distinguish communication power and non communication power -ming From viran@csl.cornell.edu Thu Sep 20 05:39:44 2001 Return-Path: Received: from cray.csl.cornell.edu (cray.csl.cornell.edu [132.236.71.70]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id f8K9dhq08620 for ; Thu, 20 Sep 2001 05:39:43 -0400 (EDT) Received: from localhost (viran@localhost) by cray.csl.cornell.edu (8.9.3/8.9.2) with ESMTP id FAA31879 for ; Thu, 20 Sep 2001 05:39:38 -0400 (EDT) (envelope-from viran@cray.csl.cornell.edu) X-Authentication-Warning: cray.csl.cornell.edu: viran owned process doing -bs Date: Thu, 20 Sep 2001 05:39:38 -0400 (EDT) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 13 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Maximum Battery Life Routing to ... This paper describes several modifications to routing protocols that take into account power considerations in ad-hoc wireless networks. Two tradeoffs are presented: The need to use each node's battery capacity fairly, and the need to maximize the lifetime of most nodes in the network. These are shown as mutually exclusive goals, as the first goal will result in longer routes being used (as opposed to shortest path which might exhaust a few critical nodes) and thus reducing the overall lifetime of the system due to the larger average number of hops. The previous algorithms described are: (a) Minimum Total Transmission Power Routing (MTPR) - finds the path with the least energy expenditure; this may result in unfair host utilization. (b) Minimum Battery Cost Routing(MBCR) - Uses routes with the largest remaining battery capacity ; It may still be unfair. (c) Min-Max Battery Cost Routing (MMBCR) - uses the route with the maximum lowest capacity node. This however may reduce the lifetime of the whole network. The new algorithm described is a hybrid of MTPR and MMBCR, which uses a threshold (gamma) of battery capacity to determine when to switch MMBCR from MTPR. The paper has a lot of filler material, describing ad-hoc networks and desirable properties in general. The simulations seem even more idealized than previous papers studied. THey assume a network of completely homogenous hosts. It's difficult to compare their algorithm's performance with the others, since it's shown in a different figure. I would've picked more threshold values in the center of the range (instead of just one) to see what the behavior is like. It seems like their scheme doesn't really contribute much new, since it's just a rather simple way to pick between two of the other schemes. However, they do bring out the point of the two trade-offs in designing for power efficiency using the above algorithms. From ramasv@CS.Cornell.EDU Thu Sep 20 09:24: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 f8KDOTq01050 for ; Thu, 20 Sep 2001 09:24:29 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: cs615 PAPER 13 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Date: Thu, 20 Sep 2001 09:24:29 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F270@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 13 Thread-Index: AcFB15H5xaeJ2qulEdWTbwCQJ5m7oA== 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 f8KDOTq01050 Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks This paper discusses the salient features of ad hoc networks, requirements of ideal routing protocols designed for such networks and details how different metrics could be used to prolong the lifetime of a nodes. The important contribution of the paper is in identifying the need for different meterics that conserve power in ad hoc networks. The need of the hour may vary from conserving the total power consuption, maximizing the lifetime of the network or homogenize power consumption at different nodes. The suitability of such metrics are then analyzed based on a simple simulation. The total power consumed in the network may be reduced by choosing routes that have minimum total power consumption. This can be done using a simple path propagation model. The first metric called MTPR is defined to do this. However this may cause excessive depletion of power at certain nodes. This problem can be alleviated by instead using inverse of remaining battery power as a metric. MBCR chooses routes which as minimum total cost (sum of inverse of battery time left.) MMBCR is a tweak to the same metric by considering only the node with least remaining battery time for each route. FInally a compromise between battery time left and total power consumption is made by the metric CMMBCR which chooses between MTPR and MMBCR depending on the total battery power left in each route. The threshold used to do that may be adjusted depending on the requirements. The paper also makes distinction between power consumed due to communication and non communicaton overheads. But tries to optimize only the former. The simulations discuss the suitability of these metrics. As expected the MMBCR and related metrics succeed in delaying the expiry of the first few nodes in the network. This paper does not specify any power conserving mechanisms to perform route discovery and route maintenance but only concerns with route selection metrics. From papadp@ece.cornell.edu Thu Sep 20 10:08:55 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 f8KE8tq06006 for ; Thu, 20 Sep 2001 10:08:55 -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 f8KE8s722037; Thu, 20 Sep 2001 10:08:54 -0400 Date: Thu, 20 Sep 2001 10:01:55 -0400 (EDT) From: "Panagiotis (Panos) Papadimitratos" X-Sender: papadp@mill.ee.cornell.edu To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 13 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of: "Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks," by C.-K. Toh. Panagiotis Papadimitratos papadp@ee.cornell.edu The paper primarily discusses methods to determine power-efficient routes over a mobile, wireless ad hoc network. The basic observation is that the usual minimum-number-of-hops routing strategy does not yield, in general, optimal routes with respect to the power consumption. As an alternative, a set of constrained shortest path algorithms is examined, in order to determine the potential benefits, through simulation. The used model assumes that the received power is inversely proportional to an exponential function of distance (the exponent depending on the environment), and power consumption at the node is also taken into consideration. In particular, it is assumed that nodes have a specific battery capacity and a fixed ratio of transceiver and local processing power consumption is used. This information, along with measurements of transmission/reception power and a battery capacity threshold, allows nodes to determine the power- efficient paths, as defined in this work. 1. The first algorithm is a classic distributed Bellman-Ford, which operates on a graph with link costs being the transmission power. The modification is that the local transceiver consumption is taken into consideration, added as a constant as nodes perform the local updates of their routing tables. This additional information (cost) counter-balances the possibility of determining very long, in terms of hops, paths. 2. The battery capacity information leads to the definition of a relevant cost function and the cost function for the entire route as the sum of the constituent node costs. The resultant algorithm determines the shortest path in terms of battery cost, and essentially provides the path with the higher battery capacity. 3. An additional constrain, placed on the required battery capacity, allows the determination of the 'shortest' route with some guaranteed lifetime, in terms of energy. It is required that the selected route battery capacity (the minimum over all nodes' capacities) exceeds some predefined threshold, and maximizes the aggregate capacity, over all routes. The simulation results are based on a rather abstract implementation, which does not explicitly consider technical issues such as collisions, re-transmissions, signaling overhead etc. Moreover, the determination of routes with DBF (or, some small modification) cannot be considered realistic for the MANET context (and, maybe, is the reason for the low, uniform mobility (2m/sec) in the simulation scenario). In addition, the definition of the network lifetime is not clearly defined and justified (e.g., it could simply be the point at which a sufficient percentage of nodes run out of battery, and network functionality cannot be farther supported). The presented results practically measure the 'expiration' times of all nodes and show a comparison of curves resulting from the 1.-3. algorithms and a merely mentioned stability algorithm (not, ABR). It is interesting that despite the initial intuition favoring multihop paths over single-hop routes and a simple pathological example (Fig. 4) for shortest path (minimum hop) routing, the graphs indicate that minimum hop routing is very competitive energy-wise. And, from Fig. 3a, almost two thirds of the network nodes run out of battery later than the ones using the best-performing energy-conscious algorithm. In conclusion, this work provides a adequate outline of the problem parameters, but does not succeed in proposing practical methods in a realistic setting. From daehyun@csl.cornell.edu Thu Sep 20 10:45:05 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 f8KEj5q10133 for ; Thu, 20 Sep 2001 10:45:05 -0400 (EDT) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id KAA26643 for egs@cs.cornell.edu; Thu, 20 Sep 2001 10:45:00 -0400 (EDT) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200109201445.KAA26643@wilkes.csl.cornell.edu> Subject: 615 PAPER 13 To: egs@CS.Cornell.EDU Date: Thu, 20 Sep 2001 10:44:59 -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 Conditional Battery Capacity Routing (CMMBCR), which satisfies two constraints simultaneously - fairness of power consumption over nodes and maximum power saving for each connection. This paper shows four power efficient routing algorithms. 1. Minimum Total Transmission Power Routing. (MTPR) This algorithm calculates the total transmission powers for all possible routes and choose the minimum power route. Basically, the idea is same as in PARO, so it has the same problem - long route. To overcome this problem, the transceiver power is also included in the cost function. 2. Minimum Battery Cost Routing. (MBCR) This algorithm uses the battery capacity as a cost instead of transmission power. Because MBCR considers only the summation of battery costs, there might be a fairness problem. 3. Min-Max Battery Cost Routing. (MMBCR) This algorithm is a modification of MBCR to solve the fairness problem. The battery cost function is modified so that no mode is overused. 4. Conditional Max-Min Battery Capacity Routing (CMMBCR) This algorithm switches two route selection criteria conditionally based on the battery capacity threshold. If no node has battery capacity less than the threshold, Maximum power saving is objective. Otherwise, fairness is considered. I'd like to point out the followings; 1. In my opinion, the main contribution of this paper is that it tries to achieve fairness as well as power saving and the proposed algorithm (CMMBCR) is enhanced from existing other algorithms. 2. As also mentioned in the PARO review, there seems to be a conflict between communication performance and power saving. Performance oriented routing algorithms usually try to find shorter paths, but power saving ones longer paths. So to find a optimal point in this trade-off looks very important. 3. Simulation results in this paper only shows the power saving performance. But, it would be better to show the communication performance such as the number of hops and compare algorithms based on this metric as well. 4. First part of this paper summarizes the characteristics and the desired properties of ad hoc networks, I think it is succinct and very informative. From gupta@CS.Cornell.EDU Thu Sep 20 10:52:43 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 f8KEqhq11083 for ; Thu, 20 Sep 2001 10:52:43 -0400 (EDT) From: Indranil Gupta Received: (from gupta@localhost) by ringding.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id f8KEqgi06825 for egs@cs.cornell.edu; Thu, 20 Sep 2001 10:52:42 -0400 (EDT) Message-Id: <200109201452.f8KEqgi06825@ringding.cs.cornell.edu> Subject: 615 PAPER 13 To: egs@CS.Cornell.EDU Date: Thu, 20 Sep 2001 10:52:42 -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----- Maximum battery life routing to support ubiquitous mobile computing in wireless ad hoc networks, C.-K. Toh. Reviewer: Indranil Gupta Summary: This papers addresses the problem of power-conserving routing in ad-hoc networks. The author focuses on simultaneously achieving minimum transmission power for each connection, and distributing the power consumption rate of connections across nodes (or maximizing node battery lifetimes). The author seems to conclude that striking a balance between the two is extremely difficult, if not impossible. The paper begins with an extended summary of the properties ad-hoc routing protocols should have - throughput, delay, shortest paths, power consumptions, load balancing, bandwidth utilization, loop-freedom, etc. The author then proposes four schemes for power aware routing: 1) Minimum Total transmission power routing (MTPR), that minimizes the total power consumed along the route by treating each link cost as the sum of the transmit and receive powers at the link, 2) minimum battery cost(MBCR), where each link cost is chosen inversely proportional to the remaining batter capacity at the transmitter, 3) min-max battery cost routing (MMBCR), where cost of each link depends on the transmitter's remaining battery capacity and 'best' route is that with the least maximum link cost (thus the path with the maximum minimum-capacity node), 4) conditional max-min battery capacity routing (CMMBCR), where routes that have an MMBCR cost below a threshold are eliminated, and the MTPR scheme is applied to the remaining paths. Simulations in the paper reveal that shortest route and ABR-based schemes have a shorter first-node-down lifetime and longer last-existing-node lifetime (thus higher standard deviation) than MBCR and MMBCR, with MBCR doing better among the latter two. A low value of threshold in MMBCR gives a shorter first-node-down lifetime and longer last-existing-node lifetime (thus higher average lifetime and higher standard deviation) than choosing a higher threshold. Smaller thresholds also lead to shorter routes. Comments: - The paper does address a very important question - can one have short and power-efficient routes, while also maximizing the lifetime of any network node ? The author seems to conclude in the negative but only from the schemes he has investigated. The question is not answered conclusively. - (Fairness of node lifetime) When it comes to maximizing node battery lifetimes, shouldn't nodes that are the origin of a lot of packets lose more lifetime compared to other nodes that are just routing these packets through for that node ? Typically, different nodes will have different utilizations (in terms of users sending email, browsing etc on the PDA) at different times - a node should have a shorter lifetime if its user 'uses' it more. The author does not seem to take this into account - his schemes will have the same battery lifetime for a a sender node and one that is otherwise dormant but just happens to be used for routing. To be fair to the paper though, the issue of Fairness does seem to be more general than the problem the author is targeting (the slogan of MBCR, MMBCR, CMMBCR is 'save the weak battery node'). - (A solution to Fairness) The above fairness could potentially be achieved by 1) having a lower cost for the sender-transmitting link, and 2) 'shifting' routes that are long-lived so that different intermediary nodes are used over time. Has this been tried ? - Is remaining battery capacity easy to measure (accurately) ? Battery discharge rates tend to be non-linear in the power usage, so batteries have to be 'probed' for remaining battery capacity. This probe needs to be fairly accurate for schemes like CMMBCR to work. - How do the algorithms in the paper perform when the sender-destination pairs are not random but follow a more realistic distribution (clustered...) ? - The authors algorithms do work well in the presence of a nearby base station (infinite power). - Figure 3: is the average lifetime of Shortest really smaller than MBCR ? (the areas under the two curves look similar). -----END----- From avneesh@csl.cornell.edu Thu Sep 20 11:07:01 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 f8KF71q12758 for ; Thu, 20 Sep 2001 11:07:01 -0400 (EDT) Content-Class: urn:content-classes:message Subject: 615 Paper 13 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Thu, 20 Sep 2001 11:11:45 -0400 X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Message-ID: <97C142C1212ED545B0023A177F5349C4053A94@capricorn.ds.csl.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper 13 Thread-Index: AcFB5pAe1KLD2bSxTxuJKe4A72rvZw== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id f8KF71q12758 Maximum Battery Life Routing to Suport Ubiquitous Mobile Computing Paper Summary/critique. This paper discusses on a broader level, the power management requirements of an adhoc mobile network. In particular it evaluates the MTPR, MBCR, MMBCR and CMMBCR approaches to reducing the battery requirements of nodes within the adhoc network. As with the PARO paper, the aim is to find a efficient power route. Simulation results take into account the ratio between the power for communication related component(PC) vs the power for the non-communication(PNC) related component, as well as a particular battery threshold for the nodes to transmit messages.Results show that when the PC/PNC ratio is 1, the above metrics do not show highly variable results, under 1, the nodes are effected in almost the same way since PNC is higher. Also an important observation is that it is not feasible to increase fairness of battery utilization while trying to maximaize lifetime of most nodes (value of threshold). Hence the threshold depends on network size and type of mobility. The CMMBCR scheme chooses the shortest path, if all nodes have capacity above a sufficient threshold. This was an interesting observation. I thought that the paper addressed some important issues and adequately pointed out the above tradeoff. Some of the introductory material on adhoc networks could have been condensed and more 'realistic' simulation studies should have been shown, including network density and mobility. There is also another issue that seems lacking in both PARO and this paper, and it is that they do not mention the type of data, etc that we would be transmitting. Sometimes it would be a good idea to sacrifice power for better performance, and how would a protocol like this take that into account? Maybe some help from upper layers might be required. From teifel@csl.cornell.edu Thu Sep 20 11:41:16 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 f8KFfFq16274 for ; Thu, 20 Sep 2001 11:41:15 -0400 (EDT) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id f8KFfA387352 for ; Thu, 20 Sep 2001 11:41:10 -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:41:10 -0400 (EDT) From: "John R. Teifel" To: Subject: 615 PAPER 13 Message-ID: <20010920110417.O70092-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Battery Life Routing: This paper present a routing protocol to maximize the lifetime of an _entire_ adhoc network by minimizing the transmission power between nodes and equalizing power distribution evenly across the network. It raises the interesting issue that in adhoc networks, the ultimate performance/connectivity of the network depends on the lifetime of individual network nodes. The energy-efficiency metric in this paper is more complicated than the one presented in PAPER 12, because in addition to transmission power, it includes constraints on battery capacity for each node. Toh also gives a nice summary of the many metrics that may be important for adhoc networks. The simulations presented in this paper, are perhaps the most interesting aspect. They show that (as in PAPER 12) that power-aware routing protocols tend to use more nodes along their routing paths (as compared to throughput metrics). This increases the amount of traffic nodes handle that is simply relay traffic, which increases node failure time. The main point of this paper is that we cannot both use nodes fairly and extend their life times. This is because some nodes will be excessively utilized simply for packet relaying, and their energy will be depleted more quickly. From c.tavoularis@utoronto.ca Thu Sep 20 11:42:44 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 f8KFgiq16665 for ; Thu, 20 Sep 2001 11:42:44 -0400 (EDT) Received: from webmail2.ns.utoronto.ca ([128.100.132.25] EHLO webmail2.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 55468]) by bureau6.utcc.utoronto.ca with ESMTP id <238811-21752>; Thu, 20 Sep 2001 11:41:01 -0400 Received: by webmail2.ns.utoronto.ca id <24410-13843>; Thu, 20 Sep 2001 11:40:45 -0400 To: COM S 615 Subject: 615 PAPER 13 Message-ID: <1001000435.3baa0df399fee@webmail.utoronto.ca> Date: Thu, 20 Sep 2001 11:40:35 -0400 (EDT) From: c.tavoularis@utoronto.ca MIME-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit User-Agent: IMP/PHP IMAP webmail program 2.2.3 This paper introduces the importance of power-aware routing when transmission power dominates over other power consumption in an ad hoc network of systems. The author starts by providing a thorough layout of the characteristics, requirements and desirable properties in ad hoc networks. Among the desirable properties, power efficiency is of focus, which can be dealt with at the physical, data link or network (routing protocol) layers. Two conditions, using nodes fairly and prolonging node lifetime, are attempted to be met. It turns out that these conditions cannot be met simultaneously. Four routing protocols are proposed to improve power efficiency. MTPR chooses the minimum transmission power route by having each node examine the possible costs leading to it, and choosing the minimum one, until the destination is reached. MTPR can be implemented using Dijkstra’s algorithm or Bellman-Ford which is preferred for stability. MBCR chooses the path such that sum of the nodes’ battery power is a maximum, to relieve weaker paths. This protocol may still quickly exhaust a weak node if the overall path is strong. MMBCR chooses the path with the ‘strongest-weakest’ node (relative to weakest nodes in other paths). While this may salvage a weak node temporarily, it may choose higher power-consuming paths reducing lifetime of nodes as a whole. CMMBCR combines the aforementioned protocols as follows: it chooses the shortest path when the all nodes’ battery power is above a threshold, gamma, otherwise, it implements MMBCR. Therefore, the performance depends entirely on gamma. The above protocols are simulated, and an association stability protocol is also simulated. The main conclusion from these results is that it is not possible to simultaneously balance the use of each node’s battery capacity fairly and maximize the lifetime of most of the nodes in the network. In CMMBCR, gamma can be adjusted to accommodate both goals as best as possible. In my opinion, this analysis proved that shortest path algorithms have the best overall performance, and increase the lifetime of nodes in general. The glitch is that a node will get depleted quickly if it frequently resides in shortest paths. CMMBCR seems to provide an enhanced solution, but the simulation results (i.e. expiration times) do not look any better compared to the other protocols. Can anyone explain this? From ranveer@CS.Cornell.EDU Thu Sep 20 11:53:35 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 f8KFrZq17851 for ; Thu, 20 Sep 2001 11:53:35 -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.4712.0 Date: Thu, 20 Sep 2001 11:53:35 -0400 Message-ID: X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 13 Thread-Index: AcFB7FuWi3dkqq3YEdW5awCQJ59Etw== 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 f8KFrZq17851 Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks This paper describes the desired properties of a routing protocol in an ad hoc network. It then proposes and analyses four route selection algorithms to conserve battery life, which is a scarce resource in ad hoc networks. The algorithms are simulated and the results presented. The main contribution of this paper is to present the idea of power conservation with the entire network in perspective but also laying emphasis on individual nodes. The graphs showing the battery life of nodes using the different schemes is interesting. PARO took a wholesome view of the network, while this paper suggests that it is equally important to look at the standard deviation. Especially striking were graphs 6(a) and (b), to see that the mean and standard deviation follow similar curves on changing the paramater of CMMBCR. The paper is interesting although some important points seem to be missing. For example, any routing strategy also involves a route maintenance phase. Nothing about route maintenance is mentioned in this paper. Besides, no results are presented with varying mobility. This should have an impact on changing routes and also battery life. Besides, in the simulation, nothing is mentioned about the mean duration of data sessions. Longer data sessions with mobility would give us interesting results. From gleason@CS.Cornell.EDU Thu Sep 20 12:28:52 2001 Return-Path: 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.7) with ESMTP id f8KGSpq21894 for ; Thu, 20 Sep 2001 12:28:52 -0400 (EDT) Received: from cypher.cs.cornell.edu (dhcp-147.rover.cornell.edu [128.84.24.147]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA00794 for ; Thu, 20 Sep 2001 12:28:46 -0400 (EDT) Message-Id: <5.0.2.1.2.20010920110439.00aa6898@postoffice.mail.cornell.edu> X-Sender: gleason@pop.cs.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.0.2 Date: Thu, 20 Sep 2001 12:28:38 -0400 To: egs@CS.Cornell.EDU From: Sunny Gleason Subject: 615 Paper #13 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks The Toh paper presents a nice overview of power considerations in ad-hoc routing, as well as four power-aware protocols: minimum total transmission power routing (MTPR), minimum battery cost routing (MBCR), min-max battery cost routing (MMBCR), and conditional max-min battery capacity routing (CMMBCR). MTPR seems like a good heuristic -- although for a homogeneous network, I am not sure where it would significantly out-perform a traditional shortest path algorithm. This battery-cost schemes give a loose delegation of responsibility within the network -- the more a node talks, the less it has to route, etc. The use of random communications patterns seems to imply a uniform distribution of services throughout the network -- it would be interesting to see how a non-uniform distribution would affect the routing and power consumption of nodes. It seems natural that nodes' battery life should be taken into consideration when routing -- I'm surprised that the authors didn't discuss QoS as an additional parameter. When there is limited connectivity between two clusters, it might be wise to preserve the link for as long as possible -- this becomes difficult under the assumption that all packets should be treated equally. Although many tradeoffs were mentioned casually in the paper, the results do not show any standard metrics such as throughput and latency. It would be useful to see how much these protocols differ from the other protocols in terms of path length / reachability. From jcb35@cornell.edu Thu Sep 20 12:30:00 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 f8KGTxq21934 for ; Thu, 20 Sep 2001 12:29:59 -0400 (EDT) Received: from localhost.localdomain (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 MAA29024 for ; Thu, 20 Sep 2001 12:29:56 -0400 (EDT) Received: from localhost (john@localhost) by localhost.localdomain (8.11.0/8.11.0) with ESMTP id f8KGWoB04298 for ; Thu, 20 Sep 2001 12:32:50 -0400 Date: Thu, 20 Sep 2001 12:32:44 -0400 (EDT) From: "John C. Bicket" To: egs@CS.Cornell.EDU Subject: 615 PAPER 13 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper discusses routing techniques using battery life as a metric to evaluate routes in ad-hoc networks. They begin with a characterization of ad-hoc networks, and point out that to maximize the lifetime of ad-hoc mobile networks the power consumption rate of each node must be evenly distributed along with the overall transmission power for each connection request. They then present four routing algorithms, including new one which they propose, and evaluate them through simulations and conclude that a algorithm which takes into account route battery consumption and node battery levels has the nicest characteristics of the algorithms they simulated. The paper discusses four algorithms: minimum total transmission power routing - this algorithm picks a route based on which one consumes the least battery power over the whole route. It does not take into account the lifetime of each host. minimum batter cost routing - this algorithm finds a route with the maximum remaining battery capacity. If all nodes have similar battery capacity, this metric will select a shortest-hop route. But it may select a route where a lot more power is consumed if the low-power route has a lot of nodes with a lower amount of battery power per node. min-max battery cost routing - this metric always tries to avoid the route with nodes having the least battery capacity among all nodes in all possible routes. It seems that the life time of all nodes will be longer; but there is no guarantee that the minimum total transmission power paths will always be selected, it could consume more power, and in turn reduce node lifetime. Their proposal - max-min batter capacity routing - use battery capacity instead of a cost function as a route selection metric. In simulation, the min battery cost and min-max battery cost metrics for evaluating routes help to ensure a longer period before the first node expired along with the last node expiring before the other algorithms. This seems to point to the nodes being used having a more equal power consumption rate. comments: I thought that this paper outlined some very important problems with ad-hoc networks, but spend a long time discussing ad-hoc networks and could have used more discussion and evaluation of algorithms. I did not feel that their algorithm performed significantly better than others such as the shortest path algorithm, and as with most of the other papers in this field, I wonder about their simulation technique and how realistic it is - I would expect that most ad hoc networks would be a lot more clustered before I would expect a random distribution.