From hs247@cornell.edu Wed Sep 18 21:54:24 2002 Received: from mailout5-0.nyroc.rr.com (mailout5-0.nyroc.rr.com [24.92.226.122]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id g8J1sNh19130 for ; Wed, 18 Sep 2002 21:54:23 -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 g8J1sLo09207 for ; Wed, 18 Sep 2002 21:54:22 -0400 (EDT) Message-Id: <5.1.0.14.2.20020918215123.00b3dde0@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:54:20 -0400 To: egs@CS.Cornell.EDU From: Hubert Sun Subject: 615 Paper 15 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This papers main contribution is the introduction of Maximum Battery Life Routing. The idea is that in ad-hoc environments, nodes are assumed to run on battery, and the best way for the network function is for nodes to have a prolonged battery life. The authors of this paper did a very good job in analysing the characteristics of an Ad-hoc network. They have shown how ad-hoc networks differ from wired networks, with the main one being Power-efficiency. One wants to minimize power consumption in a ad-hoc network, and the introduction of this factor seems to contradict other factors (ie. Less power consumption can lead to lower end-to-end throughput in some cases). The paper concentrates on different methods of calculating routes: MTPR, MBCR, MMBCR, and CMMBCR. There final proposal is to use CMMBCR which chooses shortest routes but takes into account the battery power left of the nodes on the route. This paper serves as a good paper that enlightens the reader to what to look at when designing an ad-hoc protocol. They have shown that Power consumption is a property that must be considered (many previous protocols do not account for this). The simulation that they used (like many other papers) only views the nodes as randomly moving in a box, perhaps a better simulation should be used. This paper says that choosing routes based on transmission power (ie PARO) might not be good because if one node used was efficient in transmission power it could be chosen all the time, and therefore its battery could run out quickly. The next step would be to convert CMMBCR to an actual protocol. Things to look at are how to gather this information efficiently, process that information and store it. After this protocol has been established, an implementation in the real world to see how it works is needed. With a real implementation, optimal parameters for CMMBCR can be chosen. Like the last paper, more experiments have to be done on actually how important saving power is compared with other optimising other characteristics of an ad-hoc network. What are the tradeoffs and how costly can this be? From liuhz@CS.Cornell.EDU Wed Sep 18 22:25:12 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 g8J2PBh25129 for ; Wed, 18 Sep 2002 22:25:11 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Subject: 615 PAPER 15 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Wed, 18 Sep 2002 22:25:11 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE603@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 15 Thread-Index: AcJfg8ezLZLfCltcTaSSN+HYDTNiwQ== From: "Hongzhou Liu" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id g8J2PBh25129 The main idea of this paper is although performance metrics such as end-to-end throughput and delay are important, they are not the only metrics for good ad hoc routing protocol. Battery power capacity, transmission power consumption, stability of routes, and so on are also crucial for a good routing protocol. This paper focuses on power issues. The authors outline the characteristics of ad hoc mobile networks and show that power energy, as well as bandwidth, are precious resources in the ad hoc networks. Several previous power-aware routing protocols are introduced and compared. Due to their inabilities to achieve the goal to maximize the lifetime of each node and use the battery fairly, this paper suggests a new power-aware routing protocol that's proposed to be able to satify this goal. However, the simulation result shows it's impossible to use each node fairly and extend their lifetime simultaniouly, thus a trade-off must be made. the contribution: 1. This paper outline the characteristics of ad hoc mobile networks and the desirable properties of routing protocols for ad hoc networks 3. This paper outline some schemes to utilize battery power efficiently in different layers. 2. This paper makes a good summary of previous work on power-aware routing. 3. This paper reveal the incompatibility between average lifetime of each node and fair power consuption on each node. 4. This paper propose a new power-aware protocol that's highly flexible in face of the trade-off between the above mentioned two incompatible goals. Some assumptions used in the simulation, especially the one that assume all nodes will consume the same amount of energy when sending and receiving messages, are not reasonable. And it may be interesting to show the five protocols' performances in face of different level of mobility. 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 g8J2ngh29664 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 WAA04817 for ; Wed, 18 Sep 2002 22:49:42 -0400 (EDT) Message-ID: <013401c25f87$3354bbd0$a7e8ec84@XIN> From: "Xin Zhang" To: "Emin Gun Sirer" Subject: 615 PAPER 15 Date: Wed, 18 Sep 2002 22:49:34 -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 idea of this paper is very natural, but not attractive though. It treats the networks as a graph whose edges have costs as a function of transmission power and remaining battery power. The good point is that it recognized the two main issues in power problem in ad hoc network, namely transmission power (on route side) and battery power (on node side, for its longevity). In my opinion, PARO does better than CMMBCR (proposed in this paper, evolved from MTPR, MBCR and MMBCR). CMMBCR uses a metric depending on transmission power and remaining battery power, but it didn't mention how the transmission power between each pair of nodes is got and maintained by both ends. Also the Bellman-Ford seems much more complicated than alg used in PARO. So, it may be better to deal with transmission power using PARO and at the 'redirector election' stage, take the battery issue into consideration. Another good point in CMMBCR is defining a battery capacity threshold. It's quite intuitive and should be a good way dealing with the battery issue. A great portion of paper devoted to a summery on main networking issues in ad hoc. Not much to say on that. From mr228@cornell.edu Wed Sep 18 23:12:59 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 g8J3Cxh04284 for ; Wed, 18 Sep 2002 23:12:59 -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 XAA15773 for ; Wed, 18 Sep 2002 23:12:59 -0400 (EDT) Message-ID: <3D8940BD.EBA2E694@cornell.edu> Date: Wed, 18 Sep 2002 23:13:01 -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 15 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit This paper also highlights power issues in wireless networks. It clearly identifies why power is so important, and provides justification for why protocols need to be designed with power saving features built into them. It proposes two criteria for how to judge how well a network manages power. Their first goal is to route such that each node's power is used fairly (uniformly). Their second goal is to prolong the time until the first node runs out of power. They also examine how long it takes for enough nodes to run out of power such that the network becomes partitioned. This paper's primary contribution is to propose and experimentally examine 3 proposed metrics for determining routes that meet the above goals. Most prior work considers "shortest path" to be either the path with the least number of hops or the least "total distance traveled (lowest latency)" of a packet. They propose 3 new measurements of distance, which can then be inserted into a shortest path algorithm to produce power-optimal routes: 1.) Minimum Battery Cost Routing - a node's willingness to forward packets is a function of the inverse of its remaining power. 2.) Min-Max Battery Cost Routing - this scheme uses power more fairly by requiring nodes to route packets to the neighbor with the most remaining power. 3.) Max-Min Battery Capacity Routing - Their goal is to achieve 1 and 2 simultaneously, so they propose instead to choose MBCR if all neighbors have power above a certain threshold, otherwise use MMBCR. They conduct experiments using all these distance metrics and with many thresholds for CMMBCR and their simulations lead them to the conclusion that their two primary goals are incompatible. One must establish a trade-off between 1 and 2. Their solution is to use 3 with a situation-specific value for the threshold. The paper presents a lot results is able to draw worthwhile conclusions from them, however, it's not clear to me that things like latency aren't adversely affected by not choosing short routes. Also, they never mention how bad a simple shortest path distance metric really is. In some graphs, the SP metric even conserves power better than the other metrics whose goals were to do just that. Future work might explore ways to allow CMMBCR to route more optimally (in terms of distance) while still maintaining it's power-saving ability. From mvp9@cornell.edu Wed Sep 18 23:40:21 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 g8J3eLh08668 for ; Wed, 18 Sep 2002 23:40:21 -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 XAA16714 for ; Wed, 18 Sep 2002 23:40:18 -0400 (EDT) Date: Wed, 18 Sep 2002 23:40:18 -0400 (EDT) From: mvp9@cornell.edu X-Sender: mvp9@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 15 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The main focus of this paper is on presenting a metric for ad-hoc mobile networks that focuses on power-consumption and up-time of nodes. A considerable list of different metrics used in routing is presented, as are algorithms for creating routes that attempt to prolong either the time before the first node failure or the average up-time, or both. The CMMBCR algorithm suggested by the authors attempts to achieve both goals simultaneously, but a simulation shows the two can be balanced but not combined. In fact the most useful part of the report is the comparison (analytically and through simulation) of various metrics in routing, because the CMMBCR is little more than a simple combination of two other metrics. There are some weaknesses in the paper as a whole. Too much space is allocated to general discussion of the field and power-saving measures and physical and link layers that are not really relevant to the main contribution of the paper. The simulation is also questionable, not only because there are so many parameters whose varying value can lead to widely different results, but also as a result of concerns like apparently constant motion of the nodes and the continuing random choice of source and destination, both of which are unrealistic and the latter contributes to much more egalitarian power-use distribution across the nodes than would be expected. The paper outlines issues that are often ignored in pursuit of shortest paths or maximum throughput and gives reasonable techniques for addressing the questions of up-time. However, the suggestion is not in itself a routing protocol, since no explanation is given of how to obtain necessary information - moreover, how to do so while minimizing the power consumption. The next step is to integrate this into an actual protocol and then do further simulation and study, where both power and performance related measures are recorded. From shafat@CS.Cornell.EDU Thu Sep 19 00:54:32 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 g8J4sWh22415 for ; Thu, 19 Sep 2002 00:54:32 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 15 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 19 Sep 2002 00:54:31 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D1507A9@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 15 Thread-Index: AcJfmKYz5Lu9yzrBRACghx23ReexKQ== 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 g8J4sWh22415 This paper, also like the PARO paper, addresses the issue of power consumption in mobile wireless ad hoc networks. However, I feel that it does a much better job of motivating the reader about the importance of introducing a new metric like power consumption in routing protocol design. Having said that, the very basic approach to wireless networking could perhaps been avoided in the introduction. According to the paper, the main goals of a power consumption conscious protocol are: (1) to evenly distribute power consumption throughout the network, and (2) to maximize the longevity of nodes. Keeping these in view, the author highlights various ways in which power consumption can be reduced in the physical, data link and network layers and, presents four routing algorithms that propose different ways of minimizing power consumption. A lot of quantitative analysis, based on simulation results, is presented for each of the four algorithms. While the results display a definite improvement in the new metrics, the paper leaves out other important factors like convergence time, scalability, transmission delay etc. The simulation is also somewhat unrealistic in the sense that the nodes are always mobile. These could be worked upon in the future enhancements. One problem with the proposed CMMBCR protocol is that if all nodes on all possible routes are above the threshold 'gamma', it chooses the shortest route. This implicitly implies that in a somewhat non-dynamic network, the same route will be used more intensively until the battery power of the nodes on that route falls below the threshold, rendering the nodes pretty much dead. This I believe, did not show up in the simulation results, once again, due to the constant mobility of nodes and could otherwise have serious implications on the performance of the protocol. From mp98@cornell.edu Thu Sep 19 01:06:27 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 g8J56Rh24692 for ; Thu, 19 Sep 2002 01:06:27 -0400 (EDT) Received: from Warren-Lapines-Computer.local. ([128.253.240.252]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id BAA02899 for ; Thu, 19 Sep 2002 01:06:26 -0400 (EDT) Date: Thu, 19 Sep 2002 01:06:30 -0400 Mime-Version: 1.0 (Apple Message framework v543) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 15 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: <8F17F22A-CB8D-11D6-A16E-003065EE5F0A@cornell.edu> X-Mailer: Apple Mail (2.543) Coming from a magazine, this paper provides a lot of background information on MANET's in general and their routing algorithms. The focus of it, however, is on the inclusion of power efficency in the metrics of an ad-hoc protocol. The paper merges and modifies existing approaches to power efficiency to create the Conditional Max-Min Battery Capacity Routing for choosing between multiple routes. All routes are assigned a value based on the closest to death node along them. All routes whose value is higher than a cut off value are considered as possible candidates and fed to the minimum total transmission power routing algorithm (an algorithm that does exactly what it says--Chooses the path of minimum overall power consumption). If there is no such path, it chooses the one with the highest remaining battery capacity. In effect, the choice of gamma allows one to set a level of protection for routes with almost dead nodes nodes. The paper then goes on to present an impressive series of simulations considering how rapidly nodes will fail under various power management schemes (including some with no such management like shortest path) and the results of a simulation of the CMMBCR scheme with various levels of gamma. What is interesting here is that while certain schemes (such as shortest path or CMMBCR with low gamma) ensure that some nodes will remain up for a very long time, some nodes will fail right away. In effect, these algorithms slam the nodes along the most efficient routes. Although they provide an interesting scheme, it is not a fully functional protocol for routing: It lists how to choose between multiple routes, but does not detail how to set up and find routes. For that matter, very few protocols we have encountered so far contain explicit descriptions of how to maintain multiple routes. Also the simulation again suffers from not really modeling a real world situation. Like the previous paper, what is really needed is information on integrating this power management scheme with an existing routing protocol. From bd39@cornell.edu Thu Sep 19 01:08: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 g8J58Jh24742 for ; Thu, 19 Sep 2002 01:08:19 -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 BAA12434 for ; Thu, 19 Sep 2002 01:08:16 -0400 (EDT) Message-Id: <5.1.0.14.2.20020919010711.0229c2d0@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 01:07:21 -0400 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 15 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Paper 15 - Maximum Battery Life Essentially this paper introduces battery life in a network as a new metric with which to route packets. The preceding discussion is a nice breakdown of the properties of ad-hoc networks and the requirements of their routing protocols - dynamic, low and variable bandwidth, multihop routing, energy constrained, etc. that have been in common issues that have been in the protocols discussed previously. The main contribution of this paper is that of the battery life metric and balancing battery life load among all of the devices participating in the network. The paper also points out an important tradeoff, that battery conserving paths may be longer; that while balancing battery consumption load, the routing protocol may deplete more nodes faster. In order to balance these two, the authors propose a routing algorithm which behaves conditional on the remaining battery life of the nodes on the path. It is unfortunate that such a good overview of the characteristics of routing protocols (even including security!) would end with no specification of a protocol, only the introduction of a new metric with which to route packets. It is not apparent as to how this "protocol" would actually be implemented. It seems that the authors purpose is to introduce the battery routing metric agnostic of the actual routing protocol implementation. Future work would be implementation of this metric into a full protocol. One consideration that needs to be addressed is that the battery life of all nodes along a path needs to be known, which is information that needs to be propagated in some fashion. Overall, the idea is good, however, the details need to be worked in to a full protocol. From ag75@cornell.edu Thu Sep 19 01:46:49 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 g8J5knh00962 for ; Thu, 19 Sep 2002 01:46:49 -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 BAA11052 for ; Thu, 19 Sep 2002 01:46:44 -0400 (EDT) Message-ID: <000901c25f9f$f0901b50$34f0fd80@sanya> From: "Aleksandr Gilshteyn" To: Subject: 615 PAPER 15 Date: Thu, 19 Sep 2002 01:46:45 -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 This paper does not really concentrate on CMMBCR - the protocol that it proposes. It is much more about the kind of metric that should be used when doing routing in an ad hoc network. The authors claim that when doing routing in such a network we should concentrate more on saving power in order to keep the network running longer. In order to do this, the authors propose that the power consumption rate of each node must be evenly distributed, and the overall transmission power for each connection request must be minimized. The paper goes heavily into characteristics of mobile ad hoc networks and previous work on power-aware routing. The authors do a good simulation of those protocols and present us with some interesting results. While this give a reader a good overview of ad hoc networks and of other protocols, the authors' own protocol is merely a combination of two other protocols. Morover, they don't actually give details or implement their protocol. Rather, they draw theoretical conclusions from results based on simulations for the two protocols on which they base CMMBCR. A concrete protocol, an implementation and a simulation are definately needed to test their idea. From jsy6@cornell.edu Thu Sep 19 02:05:25 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 g8J65Ph03404 for ; Thu, 19 Sep 2002 02:05:25 -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 CAA11601 for ; Thu, 19 Sep 2002 02:05:25 -0400 (EDT) Message-ID: <001301c25fa2$789c3900$0600a8c0@Janet> From: "Janet Suzie Yoon" To: Subject: 615 PAPER 15 Date: Thu, 19 Sep 2002 02:04:51 -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_0010_01C25F80.F0990D10" 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_0010_01C25F80.F0990D10 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable The main goal and contribution of this paper is to formalize a protocol = that minimizes the overall transmission power while simultaneously = evenly distributing the power consumption among the nodes. The = reduction of power transmission can increase end-to-end throughput by = reducing contention and channel interference. Evenly distributing the = load among the nodes reduces the chance of network partition by = maximizing the lifetime of all the nodes in the network. =20 The paper first starts out with an overview of desired characteristics = of an ad-hoc network routing protocol, including a scheme to reduce = power consumption at each protocol layer. Then it introduces four route = selection schemes that achieve one or both of the goals mentioned above. = The first three protocols mentioned fail to achieve both goals. They = are the Minimum Total Transmission Power Routing (MTPR), the Minimum = Battery Cost Routing (MBCR), and the Min-Max Battery Cost Routing = (MMBCR). The last protocol is the proposed protocol to achieve both = goals: the Conditional Min-Max Battery Capacity Routing (CMMBCR). = This protocol introduces the notion of a remaining battery capacity = threshold. If all the nodes in some source-destination routes are above = this threshold, then the MTPR protocol is applied to find a route with = minimum total transmission power. If the routes include at nodes below = this battery threshold, then the MMBCR scheme is applied to find a route = that will avoid and thus extend the lifetime of such nodes. =20 The performance of CMMBCR depends on the value of the battery capacity = threshold, yet the paper fails to formalize a way of defining this = threshold. The higher the value of this threshold, the more fairly = distributed the power load will be among the nodes. But, as a tradeoff, = the average lifetime of all the nodes decrease with an increase in the = threshold since the probability of longer paths being selected = increases. Eventually, after several iterations of this protocol, all = of the routes will contain nodes whose battery capacities are below the = threshold and thus this protocol will have the same disadvantages as the = MMBCR protocol - the optimal power consumption is not guaranteed. It = might be advantageous to consider a threshold that varies over time and = network usage instead of one that is static. =20 ------=_NextPart_000_0010_01C25F80.F0990D10 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

The main goal and contribution = of this paper=20 is to formalize a protocol that minimizes the overall transmission power = while=20 simultaneously evenly distributing the power consumption among the = nodes.  The reduction of power = transmission can=20 increase end-to-end throughput by reducing contention and channel=20 interference.  Evenly = distributing=20 the load among the nodes reduces the chance of network partition by = maximizing=20 the lifetime of all the nodes in the network. 

The paper first starts out with = an overview=20 of desired characteristics of an ad-hoc network routing protocol, = including a=20 scheme to reduce power consumption at each protocol layer.  Then it introduces four route = selection=20 schemes that achieve one or both of the goals mentioned above.  The first three protocols = mentioned fail=20 to achieve both goals.  = They are the=20 Minimum Total Transmission Power Routing (MTPR), the Minimum Battery = Cost=20 Routing (MBCR), and the Min-Max Battery Cost Routing (MMBCR).  The last protocol is the = proposed=20 protocol to achieve both goals: the Conditional Min-Max Battery Capacity = Routing=20 (CMMBCR).    = This protocol=20 introduces the notion of a remaining battery capacity threshold.  If all the nodes in some=20 source-destination routes are above this threshold, then the MTPR = protocol is=20 applied to find a route with minimum total transmission power.  If the routes include at nodes = below=20 this battery threshold, then the MMBCR scheme is applied to find a route = that=20 will avoid and thus extend the lifetime of such nodes. 

The performance of CMMBCR = depends on the=20 value of the battery capacity threshold, yet the paper fails to = formalize a way=20 of defining this threshold. The higher the value of this threshold, the = more=20 fairly distributed the power load will be among the nodes.  But, as a tradeoff, the = average lifetime=20 of all the nodes decrease with an increase in the threshold since the=20 probability of longer paths being selected increases.  Eventually, after several = iterations of=20 this protocol, all of the routes will contain nodes  whose battery capacities are = below the=20 threshold and thus this protocol will have the same disadvantages as the = MMBCR=20 protocol =96 the optimal power consumption is not guaranteed.  It might be advantageous to = consider a=20 threshold that varies over time and network usage instead of one that is = static. =20

------=_NextPart_000_0010_01C25F80.F0990D10-- From kwalsh@CS.Cornell.EDU Thu Sep 19 10:36:29 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 g8JEaTh09187 for ; Thu, 19 Sep 2002 10:36:29 -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 KAA08245 for ; Thu, 19 Sep 2002 10:36:29 -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:36:28 -0400 Message-ID: <1032446188.3d89e0eccc597@login.cs.duke.edu> Date: Thu, 19 Sep 2002 10:36:28 -0400 To: egs@CS.Cornell.EDU Subject: 615 PAPER 15 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 Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks The authors begin by surveying several approaches to power conservation in ad hoc routing protocols. These include using transmission power or remaining battery power as cost metrics, and several variations using remaining battery power and route stability. The authors favor using battery power as the cost metric in a standard shortest-path selection algorithm, but note that this method has a tendency to deplete the power at certain hosts. In effect, by chosing the path with minimum total cost, one ignores the deviation from the mean along the path. As a rather simple improvement, the authors suggest adding a threshold: any paths utilizing a node falling above the cost threshold should not be used, if at all possible. The evaluation compares the various schemes mentioned in the paper, as well as the effect of chosing different threshholds for the proposed algorithm. I did not find the simulation setup convincing (transmission power fixed and no packet-level simulation), nor were the resulting data striking. In fairness, the authors do find an interesting conclusion. In each case simulated, the network is not able to simultaneously improve lifetime of individual nodes while also remaining fair (in the sense of evenly distributing power consumption across nodes). Since even distribution of power consuption typically dictates longer than optimal paths, total power consuption will be reduced. From ashieh@CS.Cornell.EDU Thu Sep 19 11:06: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 g8JF6Sh16389 for ; Thu, 19 Sep 2002 11:06:28 -0400 (EDT) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id g8JF6RE27344 for ; Thu, 19 Sep 2002 11:06:28 -0400 (EDT) Date: Thu, 19 Sep 2002 11:06:27 -0400 (EDT) From: Alan Shieh To: Subject: 615 PAPER 15 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper provides a survey of the evaluation axes and design considerations in ad hoc networks. It also explores some techniques for optimizing power consumption in the routing layer, both for the network as a whole, and for reducing unfair loading of certain nodes to reduce the probability of network partition. They observe that algorithms for avoiding shortest paths that involve overutilized devices (as measured by battery drain) tend to increase average hop count, and hence shorten the total lifetime of the network. An routing protocol is presented which uses thresholding on battery level to create a hybrid algorithm that trades off minimizing total power consumption and attempting to balance energy consumption between nodes. No algorithm was provided that implemented the presented routing protocol. The protocol can be efficiently implemented with a link-state approach; however, a distributed routing algorithm with reuse of computation is more respectable and interesting. The simulation suffers from the typical problems encountered so far in the class (random movement, placement, communications, not very large scale [more nodes => more power constraints for the same aggregate hardware budget]). ** Future work - Perhaps a good methodology for developing heuristics for this problem space is to test ideas on a simple (but inefficient) underlying algorithm (like link-state). For instance, the link-state approach provides obvious ways to detect potential bottlenecks in a network (bridges in the connectivity graph, articulation points, etc). - The hybrid technique presented in this paper has basically 2.5 phases of operation (MTPR, MTPR/CMMBCR, CMMBCR); with the assumption that batteries are not recharged and nodes don't move, the network moves monotonically towards the last state. (the latter assumpion is equivalent to a pessimistic assumption that nodes are very unlikely to move such that your connectivity redundancy increases significantly). A potentially better algorithm might use different phase change points (gamma) for more constrained portions of the network. - What's the hop count distribution for the various algorithms? Is the average hop increase due to a few degenerate cases (unlikely, but possible)? From vrg3@cornell.edu Thu Sep 19 11:14: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 g8JFEnh17895 for ; Thu, 19 Sep 2002 11:14:50 -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 LAA14208 for ; Thu, 19 Sep 2002 11:14:48 -0400 (EDT) Date: Thu, 19 Sep 2002 11:14:48 -0400 (EDT) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 15 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper is an analysis of the importance of power management in MANETs. It first quickly presents a variety of desired properties in the design of a MANET routing protocol, such as loop-freedom, efficient bandwidth use, distribution, and fast route convergence, and then focuses on efficient power usage. Several metrics by which a node can evaluate the efficiency of a transmission are presented, so that the most efficient next hop. Minimum Total Transmission Power Routing uses a cost function based on the sum of all the transmissions from source to destination. Minimum Battery Cost Routing chooses the hop with the minimum immediate power cost. MBCR in this way addresses the problem that MTPR has no local knowledge or commitment to individual nodes. Min-Max Battery Cost Routing chooses as the next node the one with the most remaining power. This is an attempt to address the problem where MBCR might allow one node to be used more than others in an uneven manner. This does reintroduce a kind of global perspective. Conditional Max-Min Battery Capacity Routing is an attempt to blend MBCR and MMBCR to allow for both local and global concerns to be addressed. CMMBCR would revert to MBCR if all potential next hop's battery levels are above a certain threshold, or revert to MMBCR otherwise. In this way, a node worries about itself until its neighbors seem to be low on power, at which point it worries about its neighbors. The suggestions made in this paper are interesting, and their simulation results do seem promising. It is important to note that there is no actual routing protocol presented, however; the simulation was simulating a general protocol which used CMMBCR. Future work on developing this protocol could be useful so that a real-life test could be done. From smw17@cornell.edu Thu Sep 19 11:19:24 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 g8JFJNh19050 for ; Thu, 19 Sep 2002 11:19:23 -0400 (EDT) Received: from cornell.edu ([128.84.84.84]) by cornell.edu (8.9.3/8.9.3) with ESMTP id LAA18405 for ; Thu, 19 Sep 2002 11:19:23 -0400 (EDT) Message-ID: <3D89ED06.7000107@cornell.edu> Date: Thu, 19 Sep 2002 11:28:06 -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 15 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit MBLR This paper combines a general laundry list of the desired characteristics of mobile wireless ad-hoc networks with a proposed protocol for power efficient routing. The authors present four different power-aware schemes. The first, MTPR, looks to reduce the total transmission power of the network, using a standard shortest path algorithm. The tendency of this scheme to choose power-efficient routes that are not optimal for other reasons can be somewhat mitigated by also including the reciever power in the optimization. MBCR (Minimum Battery Cost Routing) is an attempt to improve on MTPR by using the remaining battery power as a cost function rather than the total transmission power. The goal here is to deal with the cases where a small number of nodes are routing a large number of packets, even in the minimum power configuration. This may well lead to premature exhaustion of nodes in the network, and may even lead to serious topological upheaval. MMBCR (Min Max Battery Cost Routing) replaces the battery cost function with one that selects a route such that it selects the route that has the maximum battery capacity in the most discharged node. This seeks to preserve discharged nodes as much as possible. The final method is their proposed Conditional Max-Min Battery Capacity Routing (CMMBCR) protocol. In CMMBCR, a threshold value is defined. When there exists a routing path (or more) in which all nodes are above the given threshold, the MTPR protocol is used to minimize power consumption by selecting among the above threshold route. When all paths contain hosts below the threshold, the protocol switches to MMBCR to preserve the lifetime of individual hosts. The investigations and simulations performed by the authors are quite interesting. They clearly show that non power aware routing can have a significant effect on node uptime, and that popular or well positioned nodes may deplete their batteries significantly earlier than the network average. The authors also present a comparison between the different power-aware routing techniques, showing the differing performance of the various schemes relative to host lifetime. Finally, they acknowledge and attempt to work with the inherent tradeoffs in the system - one must reach an acceptable tradeoff between routing latency, overall host longevity, and individual host longevity, and this tradeoff may vary based on the particular application. A dissapointing feature of this analysis for me was the details of the simulation. The authors did not seem to consider (or did not present here) the effects of node failures on the network itself, and how the loss of critical nodes may cause network partitions, or other such failures even more significant than the loss of an individual node. In addition, they make use of a parameter sigma to represent the ratio of communication dependent power to non-communication dependent power. While they do mention that differences between routing schemes are reduced as sigma is reduced, they make no mention of common (even estimated) values of sigma for real-life situations. From adam@graphics.cornell.edu Thu Sep 19 11:22:00 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 g8JFM0h20018 for ; Thu, 19 Sep 2002 11:22:00 -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 g8JFLs0k050895 for ; Thu, 19 Sep 2002 11:21:54 -0400 (EDT) Date: Thu, 19 Sep 2002 11:14:02 -0400 (EDT) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 Paper 15 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper's main contribution is to introduce maximum battery life techniques in ad-hoc networks. It explores how to reduce power consumption at the physical layer, data link layer, and routing layers. For routing there are a few different techniques presented: MTPR, MBCR, MMBCR and another Min-Max implementation called CMMBCR. There is a significant amount of time and effort in this paper spent on qualitatively trying to determine the better techniques. The large number of tests let us compare, at least what they determine to important, features of each of the power consumption algs. This however (like TORA) doesn't seem to do any routing and isn't a full alg for it. It just has found a good way to minimize power usage but needs a bit of tweaking to get this to fully work in a dynamic net. From nbs24@cornell.edu Thu Sep 19 11:22:02 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 g8JFM2h20033 for ; Thu, 19 Sep 2002 11:22:02 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA19681; Thu, 19 Sep 2002 11:22:00 -0400 (EDT) Date: Thu, 19 Sep 2002 11:22:00 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209191522.LAA19681@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 15 Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Networks This paper presents a nice summary on the characteristics of a good routing protocol of an ad hoc network. It provides a summary of schemes used to reduce power consumption at the physical, data link and network layers. It also provides a comparison of previous power-aware routing schemes and proposes a scheme, Conditional Max-Min Battery Capacity Routing, whose goal is to select the best path that minimizes the total power needed to route packets on the network and maximize the lifetime of all the nodes. The idea behind CMMBCR is that given all nodes within some possible routes between a source and a destination which have remaining battery capacity above a set threshold, the route with the minimum total transmission power among these routes is chosen. They mention that paths that minimize power consumption may be longer. The author assumes that all nodes consume the same fixed amount of energy for transmission and receipt of packets. This is not practical. How routes are created and maintained by this protocol is not discussed in detail. The simulations are narrow and do not model a real network environment. What happens if all routes nodes along the path from source to destination have their battery power falling below the threshold? Can the threshold be adjusted dynamically? To build on the research, implementing the algorithm in different real networks would be good to determine the optimal battery capacity threshold in each kind of network. Nana B. Sam From pj39@cornell.edu Thu Sep 19 11:54:05 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 g8JFs5h27245 for ; Thu, 19 Sep 2002 11:54:05 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA15651; Thu, 19 Sep 2002 11:54:02 -0400 (EDT) Date: Thu, 19 Sep 2002 11:54:02 -0400 (EDT) From: pj39@cornell.edu Message-Id: <200209191554.LAA15651@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 15 Maximum Battery Life Routing to Support Ubiquitous Mobile Computing in Wireless Ad Hoc Netwokrks This paper introduces Conditional Min Max Battery Cost Routing (CMMBCR). The author argues that power consumption rate of each node must be evenly distributed along with minimizing the overall transmission power. In order to reach at CMMBCR author first talks about other power efficient routing protocols namely MTPR, MBCR and MMBCR. The author argues that to acheive both the above stated goals MTPR or MMBCR schemes are inappropriate and MBCR can fulfill both only sometimes. It prposes use of batter power instead of cost function as a metric for selecting routes. It proposes that of all possible between a source and destination routes with nodes with lowest battery power should be avoided to extend the lifetime of these nodes. The paper presents a lot of simulation results for each of the four power efficient algorithms. By simulation results it is found that by adjusting the value of r (roe) we can maximize the time when the first node powers down or the life time of most nodes in the network. The major weaknesses are the simulation is performed using only 30 nodes so scalablity issues are not touched. This paper again does not talk about other general issues such as route convergence, routing loops, higher layer protocol, security issues etc. In simulation the host are assumed to be always mobile with is a little bit unrealistic. Future work could be directed towards using a more battery power balanced route from the start. This algorithm chooses an optimal route until the batter power in that route falls below a threshold, thus this same route is chosen until it fall below the threshold. It is essential that the batter power of all the nodes are used more evenly . Hence this is something on wich future work could be directed. From ks238@cornell.edu Thu Sep 19 11:59:23 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 g8JFxNh28391 for ; Thu, 19 Sep 2002 11:59:23 -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 LAA26135 for ; Thu, 19 Sep 2002 11:59:22 -0400 (EDT) Message-Id: <5.1.0.14.2.20020919115849.01ce7a80@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:59:19 -0400 To: egs@CS.Cornell.EDU From: Karan Suri Subject: 615 PAPER #15 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed This paper's primary goal is to propose "power aware" protocols for ad hoc networks that preserve battery life by limiting the amount of power consumed by each mobile node. The author begins with a discussion of some of the primary attributes of ad hoc networks and includes some of the qualities that make mobile networks ideal (i.e. efficient bandwidth, efficient battery usage, optimization of metrics, fast route convergence, etc.). The authors address power conservation at the physical layer (hardware and circuit power efficiency), data link layer (efficient retransmission of data), and network layer (end-to-end communication in a network). The four protocols used to optimize power usage at the network layer are Minimum Total Transmission Power Routing (MTPR), Minimum Battery Cost Routing (MBCR), Min-Max Battery Cost Routing (MMBCR) and Max-Min Battery Capacity Routing. MTPR is a protocol that relies on minimizing the total transmission power by limiting the amount of noise in the network path, the distance between nodes and the bit error rate of the transmitted signals. MBCR aims at limiting the tendency to exhaust the battery life of specific nodes in the network, by choosing routes, which use those nodes with the "minimum battery cost." MMBCR is a variation on MBCR, which requires nodes to transport data through those nodes that have the most battery life. Finally, Max-Min Battery Capacity Routing (CMMBCR) will use a MTPR approach if there is sufficient battery life (i.e. above a threshold) in all the network nodes. However, if there is not sufficient life then those nodes with battery life below a certain threshold will not be used in the routes. These protocols are tested through a simulation and the analysis concludes that the final approach of CMMBCR is ideal. Unfortunately, the simulation is quite flawed. It assumes a small network of only thirty nodes which is hardly scalable. Also, the battery life of the nodes are the only metric analyzed in the simulation's results. Never does the analysis cover the success rate of data transmissions in the network using a given protocol. Also, the author addresses a major weakness in the paper when they discuss the inherent tradeoff between extending the lifetime of each node while not using optimal paths (which also inherently are exhausting energy). This is a big problem and the authors need to address which conserves more energy (i.e their protocols or using shortest and optimal paths) by making both of them metrics that are measured in their results. From that a strong conclusion could be drawn. From mtp22@cornell.edu Thu Sep 19 11:59:39 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 g8JFxch28415 for ; Thu, 19 Sep 2002 11:59:38 -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 LAA27052 for ; Thu, 19 Sep 2002 11:59:38 -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 15 Date: Thu, 19 Sep 2002 11:59:38 -0400 X-Mailer: KMail [version 1.2] MIME-Version: 1.0 Message-Id: <02091911593801.00149@narnia> Content-Transfer-Encoding: 8bit A major contribution of this paper is an analysis of current cost metrics in routing protocols and how these metrics affect battery life. This is important because battery life is a scarce resource in many mobile ad hoc networks, and the loss of power not only affects the node that goes down, but also the entire network in that the network could be partitioned by a node failure. With this in mind, the authors attempt to synthesize a protocol that will simultaneously evenly distribute the power consumption rate and minimize the power used for each connection. The authors find that they must compromise and either do one or the other at any given time. A weakness of this paper is that the authors say they are developing a new routing protocol but never fully flesh out how it is to work. Also, it would have been nice if the simulations compared a few of the popular non-power-aware protocols instead of just a representative shortest path and route stability algorithm, as I suspect these protocols vary widely in their power consumption. The work in this paper could be expanded upon similar to the work in the PARO paper. That is, one could take the power wins learned in this paper and combine them with a well-established ad hoc routing protocol. Simulations could then be performed to show the possible advantages of power-awareness and the possible trade-offs. From vivi@CS.Cornell.EDU Thu Sep 19 12:01:09 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 g8JG19h29224 for ; Thu, 19 Sep 2002 12:01:09 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615paper15 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 19 Sep 2002 12:01:09 -0400 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AF6E@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper15 Thread-Index: AcJf9ccMl4qMY781Sc+AdIPHzxugmA== 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 g8JG19h29224 This paper looks at ways to minimize power utilization of the network as a whole, and evenly distribute power consumption across all the nodes so that lifetime of the network is maximized. It examines various routing mechanisms to achieve two different goals: minimum overall power consumption, and minimum battery cost, and then proposes a Conditional Max-Min Battery Capacity Routing (CMMBCR) protocol that aims to achieve both of this goals. CMMBCR provides a route that has the least total power consumption among all routes that have sufficient remaining battery capacity. It then concludes that the two goals are not compatible, and a trade-off is needed. This is one of the few papers that have considered battery capacity as an issue in routing. One main strength of the paper is its introduction to ad-hoc networks and the issues involved. It helps readers new to the topic understand the paper clearly. Weaknesses: - Route Maintenance has not been discussed at all. - Battery capacities change during communication, and a route that was safe (in terms of battery capacity) at the beginning of a conversation might not be safe as the conversation proceeds. - Simulations consider only the life-times of the nodes. They do not consider other parameters like delay, throughput, etc. Also the protocol performance has not been compared with other protocols. From yao@CS.Cornell.EDU Thu Sep 19 12:16:55 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 g8JGGsh02912 for ; Thu, 19 Sep 2002 12:16:54 -0400 (EDT) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Subject: 615 PAPER 15 X-MimeOLE: Produced By Microsoft Exchange V6.0.5762.3 Date: Thu, 19 Sep 2002 12:16:54 -0400 Message-ID: <706871B20764CD449DB0E8E3D81C4D43024797E9@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 15 Thread-Index: AcJf9/ouachf3byzT/24O8mseujghA== 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 g8JGGsh02912 This paper starts with a complete description of characteristics of ad hoc moble wireless networks, desired properties of ad hoc routing protocols, and power efficient ad hoc mobile networks. Then it proposes that it is important to design a power efficient ad hoc routing protocol, and discusses alternative models and metrics to evaluate the cost of a route. The authors also introduce several different power efficient routing protocols, including MTPR, MBCR and MMBCR, and compare their performance through simulations. All three algorithms try to minimize the energy consumption, but have different evaluation functions. One main difference between this paper and PARO is that the authors takes the power consumption during the reception mode, and the total packet delay into account, which are neglected by PARO. So a route with minimum energy is not always the best candidate. I think this is a more realistic model than PARO. The introduction part of this paper is well written, and involves lots of important issues of ad-hoc networks. It also has a good classification on how to save energy at different layers. The energy model is straightforward and reasonable. However, the algorithm part is a little weak. All three algorithms are very simple, and derived from Bellman-Ford algorithm, with different evalutaion functions. As a result, they suffer from the same hard problem as Bellman-Ford algorithm has, requiring a node to have global knowledge to compute the best route. This problem has been discussed several times in previous papers. It limits the scalability of the algorithm, especially if the network topology is not stable, which is a basic property of ad hoc networks from the conclusion of the first part of the paper. Yong Yao From egs@CS.Cornell.EDU Thu Sep 19 13:08:24 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 g8JH8Oh14706 for ; Thu, 19 Sep 2002 13:08:24 -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 g8JH8Op05593 for egs; Thu, 19 Sep 2002 13:08:24 -0400 (EDT) Date: Thu, 19 Sep 2002 13:08:24 -0400 (EDT) Message-Id: <200209191708.g8JH8Op05593@zinger.cs.cornell.edu> To: egs@CS.Cornell.EDU Subject: 615 PAPER 15 >From linga@CS.Cornell.EDU Thu Sep 19 12:28:39 2002 >Date: Thu, 19 Sep 2002 12:28:38 -0400 (EDT) >From: Prakash Linga >To: Emin Gun Sirer >Subject: PAPER #15 > > > > >Maximum Battery Life Routing > >Minimizing transmission power for routing packets around in the network and >increasing the life time of node by evenly distributing the power consumption >rate of each node are two important objectives to increase the life time of an >adhoc network. The protocol proposed in this paper one of the first which tries >to achieve both the objectives simultaneously. >Power required by a mobile host can be mainly classified under two headings: >communication related and non-communication related. Communication related can >be further split as processing power and transceiver power (transmission power >is a dominant part of the this.) In this paper we look at reducing the power >consumption at the network layer by looking at four different routing schemes >(fourth of which is the new one!). >-Minimum total Tranmission Power Routing (MTPR): Here, transmission power is >used as a metric to obtain a route with minimum total power requirements. >Transmission power is modelled as 1/d^n where d is the distance between the >nodes (n=2 for short distance and n=4 for long distance). Standard >shortest-path algorithms can be used to find the path with minimum total >transmission power which will be used as an approximation to the path with >minimum total power requirement. This will normally result in a route with >a lot of hops which is potentially unstable. So in addtion to the transmission >power, the reception power is also used. This yields routes with lesser no. of >hops and hence are stable with higher probability. >-Minimum Battery Cost Routing (MBCR): Remaining battery power of a node is >used a metric to increase the lifetime of the nodes. This is a more >appropriate metric than transmission power as a lot of minimum transmission >routes through a certain host can drain the node out of battery power. >Since only the sum of the battery powers of the nodes in the route is important >we could still select a node with very low battery power. >-Min-Max Battery Cost Routing (MMBCR): Here routes are chosen so that it always >tries to avoid the route with nodes having the least battery capacity among all >nodes in all possible routes. But this does not guarantee a minimum total >transmission path. >-Conditional Max-Min Battery Capacity Routing: Here, among all routes with all >nodes having a minimal battery power (above a certain threshold) we choose the >one with minimum total transmission power. This reduces the total power to >forward packets and hence relaying load for most nodes is reduced (increasing >their life time.) >Simulation results have been presented which show the tradeoff between >attaining required performance levels and the lifetime of the whole network. > >Pros: >A novel approach which incorporates both the metrics of power(batter power and >transmission power) has been proposed in this paper. >Simulation results show how the power-aware routing algorithms proposed in the >paper can be used to ensure that nodes are not unwisely overused. >Tradeoff between using the nodes fairly (and efficiently) and increasing the >lifetime of nodes has been illustrated. > >Cons: >-Simulation experiments were performed with only 30 nodes in a small area with >random distribution. More realistic topologies with realistic workloads should >be used for the simulations. >-It is not clear that CMMBCR does the best possible given a threshold gamma. > From sc329@cornell.edu Thu Sep 19 13:14:12 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 g8JHECh16435 for ; Thu, 19 Sep 2002 13:14:12 -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 NAA06984 for ; Thu, 19 Sep 2002 13:14:12 -0400 (EDT) Message-Id: <5.1.0.14.2.20020919131213.00afb6f8@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 13:14:11 -0400 To: egs@CS.Cornell.EDU From: Sangeeth Chandrakumar Subject: 615 PAPER 15 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Submitted by - Sangeeth Chandrakumar Maximum battery life Rouitng to support ubiquitous mobile computing in wireless ad hoc networks This paper proposes the use of mobile node's power consumption as a metric in designing routing protocols for mobile ad hoc networks. The author prposes the following protocols in this regard: 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). The author focusses on achieving minimum power transmission for each node, and at the same time effective distribution between nodes. 1. Minimum Total Transmission Power Routing. (MTPR) This algorithm calculates the total transmission powers for all possible routes and choose the minimum power route. But the route can end up being lengthy. So the individual power saved could be offset with the multiple hops it need to take. 2. Minimum Battery Cost Routing. (MBCR) This algorithm uses the battery capacity as a cost instead of transmission power. But this could lead to a few nodes getting deleted of charge faster than others. 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. 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. This paper do bring out the important aspects of transmission power in an ad hoc networks.But as the author rightly points out, if the power consumed by communication-related traffic is on the same order as the power consumed by non-communication-related overhead, the supposed advantages of power-efficient routing algorithms are no more.So i believe more work needs to be done in this regard to attain parity between power consumption and accessibility in an ad hoc environment. From nbs24@cornell.edu Tue Sep 24 11:27:41 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 g8OFReh26297 for ; Tue, 24 Sep 2002 11:27:41 -0400 (EDT) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA06821; Tue, 24 Sep 2002 11:27:38 -0400 (EDT) Date: Tue, 24 Sep 2002 11:27:38 -0400 (EDT) From: nbs24@cornell.edu Message-Id: <200209241527.LAA06821@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: 132.236.71.82 Subject: 615 PAPER 15 CEDAR This paper presents a core-extraction distributed ad hoc routing algorithm whose goal is to provide quality of service routing in small- to medium-sized ad hoc networks by computing unicast routes that satisfy minimum bandwidth requirements from source to destination. They present a cluster-based algorithm, which uses core nodes, elected by neighbors, for state management and route computation. They use the concept of increasing and decreasing waves to establish the core paths. Non-core nodes only have to keep localized knowledge about their neighbors. They sacrifice optimality in order to compute good routes quickly and react to topology changes with only small amounts of state propagation. Even though they present simulation results, there is no evaluation of mobility, congestion or collision. Also the core nodes have a higher responsibility and therefore would have higher power requirements but this is not factored into their analysis. There was no discussion on failure rate and recovery mechanisms. I think their simulation network was too small. How about scalability? Their algorithm assumes that if A can hear B, then the opposite is true which is not necessarily true in a real implementation. Their algorithm is also based on the expectation that each core node would have few nearby nodes. How is this guaranteed? A build to the research would involve a real implementation of the algorithm and further analyses to include the concerns mentioned in the previous paragraph. Nana B. Sam