From eyh5@ee.cornell.edu Wed Nov 7 20:00:00 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA80xwR12474 for ; Wed, 7 Nov 2001 19:59:58 -0500 (EST) Received: from photon.ece.cornell.edu (photon.ece.cornell.edu [128.84.81.138]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fA80x4J16683 for ; Wed, 7 Nov 2001 19:59:04 -0500 Date: Wed, 7 Nov 2001 19:59:16 -0500 (EST) From: Edward Hua X-X-Sender: To: Subject: 615 Paper # 39 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris This paper proposes Span, an algorithm used in wireless ad hoc networks whose principal objective is to conserve the energy of nodes and therefore prolong their life span. The nodes in Span make periodic, local decisions on whether to sleep (power saving mode) or stay awake. A Span ad hoce network allows as many nodes to go to sleep mode as possible without compromising too much the network capacity. Also, the Span network may tolerate some time delay in delivering packets. That is, the route a node uses to transmit packets is not necessarily the route with the minimum number of hops. Span is implemented between the network layer and MAC layer, thus making it possible to take advantage of the power-saving features of the link layer while having influence over the routing process. The nodes that stay awake at any given time are called the coordinators, who form the backbone of the Span network when the majority of the nodes are in the sleep mode. These coordinators are elected on a rotational basis so as to give every node in the network a fair chance to take that responsibility. The authors of the paper propose a coordinator elgibility rule, following which the coordinator nodes are selected. It says that if two neighbors of a non-coordinator node cannot reach each other either directly or via one or two coordinators, the node should become a coordinator. Furthermore, a source and a destination are always coordinators as long as they are exchanging packets, and a non-coordinator node is a coordinator if it has received a large number of packets to route in the recent past. To ensure that not all eligible nodes who are in the same neighborhood become coordinators altogether at the same time, a back-off algorithm is implemented to elect but one of them to be the coordinator and to allow the rest to stay in sleep mode. Likewise, when in a concentrated region too many nodes appear to be serving as coordinators, a coordinator withdrawl routine allows some of them to retire to sleep mode. All this is to achieve the objective that there should only be a minimal number of coordinators at any given time to serve the whole ad hoc network without suffering too much in capacity and delivery latency. In addition, the authors also attempt to improve the current 802.11 power saving mode by incorporating their proposal into it. The three modifications made in the 802.11 power saving mode are: 1)No advertisements for packets between coordinators. 2)Individually advertise each broadcast message. 3)New advertised traffic window. The effects of these modifications are studied in the evaluation of the proposal. The performance evaluation is done by looking at several criteria: the preservation of capacity, the effect by the mobility, the (optimal) choosing of coordinators, the energy consumption, and the overall network lifetime. From the graphs presented, it seems that Span performs well when the nodes are constantly moving, has achieved a considerable reduction in power consumption, which in turn translates into a longer network lifespan. On the otherhand, the nodal density in the network does not seem to have a clear impact on its performance. However, the performance evaulation does not demonstrate Span's effect on the delivery latency. Understandably, in this proposal, latency takes a backseat, but it is nice to see some solid evidence to back up the authors' claim that latency is not sacrificed to a degree beyond the tolerance level. From wbell@CS.Cornell.EDU Wed Nov 7 23:02:32 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 fA842VR00659 for ; Wed, 7 Nov 2001 23:02:31 -0500 (EST) Received: from [192.168.1.105] (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 XAA25095 for ; Wed, 7 Nov 2001 23:02:29 -0500 (EST) Subject: 615 PAPER #39 From: Walter Bell To: egs@CS.Cornell.EDU Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: Evolution/0.16.99+cvs.2001.10.18.15.19 (Preview Release) Date: 07 Nov 2001 23:02:11 -0500 Message-Id: <1005192154.1231.2.camel@brute> Mime-Version: 1.0 39) Span: an Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad-Hoc Wireless Networks SPAN is a low level protocol that enables wireless nodes to reduce power and go into power saving modes in a coordinated fashion such that the overall capacity of the network backbone is not disturbed. The idea is that by electing coordinators to serve as the multihop routers for areas of the network, other nodes in the area that are idle can go to sleep and conserve power. They build upon the 802.11 power saving capabilities and present their own protocol that sits below the routing protocol that elects a local coordinators for multihop traffic and who queues packets for sleeping nodes in the nearby area that are asleep. Coordinators are chosen locally by periodic advertisements of battery capacity and a given coordinator relinquishes it's position as coordinator after a given amount of time, evening the load out onto the nearby nodes. They show that this ability to shutdown nodes conserves a great deal of power and can prolong the network lifetime by as much as three times. This is definitely useful work, but my main question revolves around how often wireless connections are actually idle and how reasonable it is to keep them idle. We've been looking at routing protocols such as DSR, that might not be sending, but are always receiving data as it's snooping on the traffic of nearby nodes. It's clear that there is some interaction between SPAN and the routing protocol that needs to be inspected, as the loss of information about routes could put a node at a greater penalty when it does try and transmit again. Another question is how often a wireless card sits idle on an average machine. Their simulations were crafted such that idle computers transmitted no packets, but from my own experience this is hardly true given the assortment of daemons on an otherwise idle machine. From ramasv@CS.Cornell.EDU Wed Nov 7 23:10:15 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 fA84ADR01597 for ; Wed, 7 Nov 2001 23:10:13 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: cs615 PAPER 39 Date: Wed, 7 Nov 2001 23:10:13 -0500 Message-ID: <706871B20764CD449DB0E8E3D81C4D4301E7F28E@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: cs615 PAPER 39 Thread-Index: AcFoC0OjrEWqM0psQIGU62loCqf7zw== 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 fA84ADR01597 Span: An Energy Efficient Co-ordination Algorithm for TOpology Maintenance in Ad Hoc Wireless Network. SPAN is a distributed algorithm that co-ordinates the sleep time of nodes in a region of ad hoc network such that load is evenly balanced and at the same time quite a lot of power is conserved. The fundamental assumption is that when nodes are allowed to go idle and turn off their transmitting and reception hardware for reasonable duration they could conserve a lot of power. This paper presents a protocol to do this in a distributed manner without loosing connectivity. Each region has a chosen node called co-ordinator that performs the role of routing in that region for a duration of time. Nodes in a region other than the co-ordinator that are neither sources not sensors can go to sleep. The co-ordinators are chosen so that minimum connectivity is maintained i.e, if a node knows that it is the only connection between two other nodes, it ought to be a co-ordinator. Co-ordinators relinquish their post volunterily and allow othe nodes to become co-ordinators. This is done by employing a random algorithm whereby each node decides to be a co-ordinator with a probablity. This probablity increases when a node has more reserve battery power or can potentially connect multiple nodes. Each node is required to posses certain data about its neighbors. This involves periodic messaging activity that might impair the efficiency of going to sleep-mode for long periods of time. The effectiveness of the scheme also depends on availability of enough co-ordinators in a region to share the routing load. Thus SPAN may not work very well in a sparse network. The paper also suggests certain modifications to be made to IEEE 802.11 to use SPAN more effectively. It appears that SPAN may not be as useful if the suggested modifications are not made to the MAC protocol. In essence, the distributed co-ordinator election algorithm with voluntary reqlinquishing is a nice idea that may have its uses elsewhere. I don't think sleep-mode operation is the right application for this idea although sleep-mode operations are very important for energy conservation in ad hoc networks. From papadp@ece.cornell.edu Thu Nov 8 01:30:14 2001 Return-Path: Received: from memphis.ece.cornell.edu (memphis.ece.cornell.edu [128.84.81.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA86UDR15484 for ; Thu, 8 Nov 2001 01:30:13 -0500 (EST) Received: from kiki.ece.cornell.edu (kiki.ece.cornell.edu [128.84.83.13]) by memphis.ece.cornell.edu (8.11.6/8.11.2) with ESMTP id fA86THJ22601; Thu, 8 Nov 2001 01:29:17 -0500 Date: Thu, 8 Nov 2001 01:33:18 -0500 (EST) From: "Panagiotis (Panos) Papadimitratos" To: Emin Gun Sirer cc: Panagiotis Papadimitratos Subject: 615 PAPER 39 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Review of:"Span: An energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks," B.Chen, K.Jamiesson, H.Balakrishnan, and R. Morris The proposed scheme selects a subset of the network nodes to provide the routing functionality, while the rest of the nodes switch to a sleep mode, thus saving energy. The goal of the scheme is to preserve energy and at the same time maintain the ability of the network to deliver data uncompromised. The distributed algorithm for the election of the coordinators, the nodes that are assigned the role of data forwarding, relies on the proactive exchange of HELLO messages, which contain the lists of neighbors and coordinators (neighbors that perticipate in the routing backbone) and the node's status(role). On one hand, a node has to become/remain a coordinator if the connectivity of two neighboring nodes is harmed, and on the other hand, factors such as the total number of to-be-connected nodes, the remaining energy and the number of nodes determine the eligibility and the selection of a node. In order to maintain the number of coordinators low, the election is based on a randomized delay, function of the above-mentioned factors. Moreover, the withdrawal of a cordinator is also possible, if connectivity is not affected. In any case, the number(density) of coordinators appears to heigher than the approximation of the optimal, although this is The point that nodes switch between the sleep and coordinator mode is not adequetely investigated since no specific strategy is given w.r.t the selection of the sleep time. This could aggravate the worst-case delays to reconnect nodes and also increase the contention over segments of the backbone. An additional relevant factor is the adaptation of the beaconing period. Furthermore, the use of geographical forwarding reduces dramatically the control overhead, in comparison with other MANET routing protocols, while factors such the cost of acquiring this information (e.g., location of destination) are not considered either. This, in conjunction with the relatively low traffic load, explain the astonishingly high data delivery ratios. From gupta@CS.Cornell.EDU Thu Nov 8 10:35:55 2001 Return-Path: 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.7) with ESMTP id fA8FZrR09845 for ; Thu, 8 Nov 2001 10:35:53 -0500 (EST) From: Indranil Gupta Received: (from gupta@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) id fA8FZrV26063 for egs@cs.cornell.edu; Thu, 8 Nov 2001 10:35:53 -0500 (EST) Message-Id: <200111081535.fA8FZrV26063@zinger.cs.cornell.edu> Subject: 615 PAPER 39 To: egs@CS.Cornell.EDU Date: Thu, 8 Nov 2001 10:35:53 -0500 (EST) X-Mailer: ELM [version 2.5 PL3] MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Span: an energy efficient coordination algorithm for topology maintenance in ad hoc wireless networks. Chen, Jamieson, Balakrishnan, Morris. This paper presents a CEDAR-like algorithm for maintaining a dominating set (called 'coordinators' in this paper). These coordinators are used as a "forwarding backbone". The maintenance of the coordinator set is distributed and randomized. Experimental results show that the Span algorithm gives better power savings than 802.11 or 802.11 with power saving mode (PSM). Comments: - The evaluation section is very disappointing - there is no reference to CEDAR or an evaluation against this protocol. The CEDAR protocol was published in a a journal back in 99 (and this paper is published in 2001), so are the authors unaware of this other work ? - To the authors' credit, this paper does seem to solve two main problems that the CEDAR project did not address - power-awareness and migration of the core node membership. From ranveer@CS.Cornell.EDU Thu Nov 8 11:39:49 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 fA8GdlR17437 for ; Thu, 8 Nov 2001 11:39:47 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 Subject: 615 PAPER 39 Date: Thu, 8 Nov 2001 11:39:47 -0500 Message-ID: <706871B20764CD449DB0E8E3D81C4D430232E6AB@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 39 Thread-Index: AcFoc/puVg3vcGXrR6SXLhqNejnlHg== From: "Ranveer Chandra" To: "Emin Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id fA8GdlR17437 Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks This paper presents Span, a protocol for reducing the power consumption of the overall network. Span builds and maintains a backbone of nodes that form a dominating set for all the nodes in the network. Nodes dynamically decide on becoming a co-ordinator based on connectivity and remaining power among nodes. The nodes that are not on the backbone can sleep in the power conserving node, and all the routing functionality is performed by the co-ordinator nodes along the backbone. The idea of only having nodes along a backbone in the non-saving mode is interesting and should perform good for most situations in ad hoc networks. Using remaining power while deciding on the co-ordinator nodes is an interesting idea. However, 1) No throughput results are presented. In the presence of multiple sessions, all the packets will be routed along the same path, severely affecting the throughput of the network. 2) Protocols that reply on a mesh or alternate paths for reliability will not function well with Span. 3) Mobility could hamper routing in such networks. 4) It seems that for Span to function efficiently nodes would need to have synchronized clocks. It has been shown in previous work that switching nodes from power saving sleep mode to transmitting or receiving modes is also very power intensive. The effect of this phenomenon on Span would be interesting. 5) Span also uses a specific beaconing protocol. This is itself very power intensive, and Span seems to be useful only for protocols that themselves use an underlying beaconing protocol. Hence the goodness of Span for protocols such as AODV is doubtful. From c.tavoularis@utoronto.ca Thu Nov 8 11:58:03 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 fA8Gw1R19586 for ; Thu, 8 Nov 2001 11:58:01 -0500 (EST) Received: from webmail2.ns.utoronto.ca ([128.100.132.25] EHLO webmail2.ns.utoronto.ca ident: IDENT-NOT-QUERIED [port 34050]) by bureau6.utcc.utoronto.ca with ESMTP id <238794-1614>; Thu, 8 Nov 2001 11:56:23 -0500 Received: by webmail2.ns.utoronto.ca id <24411-13842>; Thu, 8 Nov 2001 11:56:07 -0500 To: egs@CS.Cornell.EDU Subject: 615 PAPER 39 Message-ID: <1005238567.3beab92755129@webmail.utoronto.ca> Date: Thu, 08 Nov 2001 11:56:07 -0500 (EST) 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 SPAN is an energy conserving routing scheme for ad hoc networks that randomly elects a set of coordinators while letting other nodes sleep. The coordinators attempt to form a minimum backbone through the network to maintain connectivity. A node can go into sleep mode if it is not receiving and it is not needed for forwarding. SPAN adaptively elecs coordinators to stay awake and perform routing. Coordinators are randomly chosen and rotated to form a backbone, and contention during coordinator election is handled with random backoff. Coordinators broadcast hello messages periodically to maintain node status and state, and have the ability to withdraw if they are no longer needed. Sleeping nodes must always be in range of at least one coordinator, and periodically check if they should wake up. SPAN attempts to find a balance between forwarding with minimal delay, and energy conservation in the idle or “listening” state. Although SPAN is a good idea, the simulation results show that it requires a high node density to effectively reduce energy consumption without deteriorating performance. This is not a valid assumption in practice. Also, the effectiveness of SPAN relies on modifications to the 802.11 MAC layer standard. From avneesh@csl.cornell.edu Thu Nov 8 11:58:49 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 fA8GwmR19773 for ; Thu, 8 Nov 2001 11:58:48 -0500 (EST) content-class: urn:content-classes:message Subject: 615 Paper 39 MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Date: Thu, 8 Nov 2001 12:00:48 -0500 Message-ID: <97C142C1212ED545B0023A177F5349C40A09C7@capricorn.ds.csl.cornell.edu> X-MimeOLE: Produced By Microsoft Exchange V6.0.4712.0 X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 Paper 39 Thread-Index: AcFoduntMxpQcYAuQtibwrfybgWNxg== From: "Avneesh Bhatnagar" To: Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id fA8GwmR19773 SPAN: An energy efficient co-ordination algorithm for Topology maintenance in Ad Hoc Wireless Networks Summary/Critique This paper describes the implementation of SPAN, a power saving technique for adhoc wireless networks. The idea is to elect co-ordinators from all nodes in the network, and rotate them in time. The co-ordinators ensure that multihop routing is being performed, while nodes not labelled as co-ordinators would remain in a powersaving mode. These nodes however periodically wake up to check if they should become a co-ordinator. The membership information is mantained thorugh periodic broadcasts of HELLO messages, while using a random backoff delay to prevent highly correlated co-ordinator events from occuring and increasing contention in the channel. The authors then derive a delay equation based upon node utility. Another interesting aspect is that the co-ordinator node can withdraw if every pair of its neighbor nodes can reach each other via some other neighbors, however to reduce a temporary loss of connectivity there is a small delay between announcing withdrawal and final withdrawing. SPAN uses the information from the MAC layer (802.11) to support its power saving functions.A non-coordinator can be promoted to coordinator if it has received a large number of packets to route recently. The 802.11 layer is further optimized to have no advertisments for packets between co-ordinators, and to individually advertise each broadcast message. Furthermore, a new advertised window is mantained witha smaller beacon period. This reduces the chances that a node must remain awake for the rest of a beacon period after receiving a advertisment. Evaluation is done using capacity, the effect by the mobility, choice of coordinators,network lifetime as parameters. These issues remind me of the hierarchical protocol evaluation which were lacking in power comsiderations. However I wonder how much SPAN itself does, without depending upon MAClayer modifications? From viran@csl.cornell.edu Thu Nov 8 12:02:28 2001 Return-Path: Received: from moore.csl.cornell.edu (moore.csl.cornell.edu [132.236.71.83]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.7) with ESMTP id fA8H2QR20288 for ; Thu, 8 Nov 2001 12:02:26 -0500 (EST) Received: from localhost (viran@localhost) by moore.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id fA8H2Le70930 for ; Thu, 8 Nov 2001 12:02:21 -0500 (EST) (envelope-from viran@moore.csl.cornell.edu) X-Authentication-Warning: moore.csl.cornell.edu: viran owned process doing -bs Date: Thu, 8 Nov 2001 12:02:21 -0500 (EST) From: "Virantha N. Ekanayake" To: Subject: 615 Paper 39 Message-ID: <20011108120154.V70528-100000@moore.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII SPAN is a power saving algorithm for dense MANETs that can dynamically organize a routing backbone. The backbone membership is rotated to spread the energy usage among many nodes. The coordinators which form the backbone stay awake continuously, while the other nodes can remain in power-savings mode. This paper presents a good idea, that of organizing a MANET into a more hierarchical structure akin to the internet. It also takes into account energy consumption by providing a method to rotate membership within this backbone. The main contribution in this paper appears to be this voluntarily withdrawing from routing ability, since hierarchical routing schemes have been seen before. From andre@CS.Cornell.EDU Thu Nov 8 12:06: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 fA8H5wR20871; Thu, 8 Nov 2001 12:05:59 -0500 (EST) Received: from khaffy (d7a086.dialup.cornell.edu [128.253.49.86]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id MAA28141; Thu, 8 Nov 2001 12:05:56 -0500 (EST) Received: from andre by khaffy with local (Exim 3.31 #1 (Debian)) id 161n2H-0000Sv-00; Thu, 08 Nov 2001 12:07:53 +0100 Date: Thu, 8 Nov 2001 12:07:53 +0100 From: =?iso-8859-1?Q?Andr=E9?= Allavena To: =?iso-8859-1?B?R/xu?= Sirer Cc: andre@CS.Cornell.EDU Subject: 615 PAPER 39 Message-ID: <20011108120753.A1783@khaffy> Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit User-Agent: Mutt/1.3.20i Sender: =?iso-8859-1?Q?Andr=E9_Allavena?= Span, an Enrgy Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks This paper presents an advance scheme to save energy. Since there are many nodes, and only few of them can transmit at the same time, why keep them all awake? Better turn them off to sleep, since they won't be able to transmit anyway. Span elects coordinators (forwarding - awake nodes) from the set of all nodes, in order to preserve connectivity. (It two of my neighbours cannot reach themselves via 1 or 2 other nodes, I become a coordinator). There is a delay before adverstising itself as a coordinator, inversely proportional to its density of neighbors and to its remaining energy (+ a random delay). More useful and fresher node tend to be used. Time to time a coordinator withdraws. Improvment to 802.11 MAC with PM: there is a small window where are advertised the packets send to sleeping nodes (note, during this small window, all the nodes are awake) - the broadcast are also individually advertised. They are transmitted at the begining of the transmitting window. Non coordinators can go back to sleep as soon as they have received their stuff. Messages to coordinatos do not need to be advertised since those nodes are going to listen anyway. Simulations (Tr > Rx > Idle >> sleep) show that Span does very well (much better than 802.11 with PM): the energy distribution is evenly spread, the network stays alive for a much longer period (2 to 3 times) for the smae throughput. But these simulations were only simulations, and do not take into account the fact that it is likely that the network cards need a while to go to sleep and to wake up, and that this while cost them some enregy. How much? Is the cost of the transitions negligeable or not? Also, implementing Span in conjonction with some routing protocol such as DSDV can be difficult (since it is a source routing). I presume it shouldn't be to difficult for AODV. -- André Allavena (local) 154 A Valentine Place École Centrale Paris (France) Ithaca NY 14850 USA Cornell University (NY) (permanent) 879 Route de Beausoleil PhD in Computer Science 06320 La Turbie FRANCE From teifel@csl.cornell.edu Thu Nov 8 12:07:42 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 fA8H7eR20989 for ; Thu, 8 Nov 2001 12:07:40 -0500 (EST) Received: from localhost (teifel@localhost) by disney.csl.cornell.edu (8.11.3/8.9.2) with ESMTP id fA8H7ZK27640 for ; Thu, 8 Nov 2001 12:07:35 -0500 (EST) (envelope-from teifel@disney.csl.cornell.edu) X-Authentication-Warning: disney.csl.cornell.edu: teifel owned process doing -bs Date: Thu, 8 Nov 2001 12:07:35 -0500 (EST) From: "John R. Teifel" To: Subject: 615 PAPER 39 Message-ID: <20011108115631.N19858-100000@disney.csl.cornell.edu> MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII SPAN: This paper discusses SPAN, a power saving technique for adhoc networks that reduces energy consumption without diminishing the capacity or connectivity of the network. When an area contains a high-density of sensors, to conserve energy only a small portion of the sensors need to be actually active. SPAN uses a distributed, randomized algorithm where nodes make localized decisions to either sleep or be active and join a forwarding communication backbone. This requires each node to make an estimate of the number of nodes that are in its neighborhood... implying that backbone nodes will rotate over time as the randomized algorithm proceeds. They claim SPAN will integrate easily with 802.11, which is a nice practical extension for real world use, and it can save energy by a factor of two. So if we assume that sensor networks are useful for something, then SPAN is a viable method for reducing energy consumption in such networks. From daehyun@csl.cornell.edu Thu Nov 8 12:09:47 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 fA8H9kR21512 for ; Thu, 8 Nov 2001 12:09:46 -0500 (EST) Received: (from daehyun@localhost) by wilkes.csl.cornell.edu (8.9.3/8.9.2) id MAA43874 for egs@cs.cornell.edu; Thu, 8 Nov 2001 12:09:40 -0500 (EST) (envelope-from daehyun) From: Daehyun Kim Message-Id: <200111081709.MAA43874@wilkes.csl.cornell.edu> Subject: 615 PAPER 39 To: egs@CS.Cornell.EDU Date: Thu, 8 Nov 2001 12:09:40 -0500 (EST) 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 presented Span, which is a power saving technique for multi-hop wireless network. The main idea of Span is that when the density of nodes is enough high, only a small number of nodes need to be on to forward traffic and the others may be off to save power. Each node makes decision on whether to sleep or stay awake as a coordinator based on local estimation. If two of neighbors can not communicate, a node decide to be a coordinator. Otherwise, it sleeps. And randomized algorithm allows coordinators to rotate with time, which will prevents a node from being over-used. each node makes announcement with random delay that takes two factors - remaining energy and possible connectivity - into account. In this kind of techniques, performance degression should be minimized. But, in my opinion, there might be non-neglectable performance degression in some cases. I think Span only provides minimal connectivity - it will not scarify any connection between each nodes, but it will eliminate other redundant connections as many as possible. But, some routing algorithms use those redundant connections for supporting more reliable routing or solving network congestion problem. If those routing algorithms are used with Span, there might be significant performance degression. In my opinion, One strong point of this paper is that Span is a distributed algorithm. The decision of each node is local and randomized. So the scalability of Span seems very good. And the simulation results show that the decision is also close to global optimum. From mh97@cornell.edu Thu Nov 8 14:45:04 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 fA8Jj2R11373 for ; Thu, 8 Nov 2001 14:45:02 -0500 (EST) Received: from mars (dhcp7.csl.cornell.edu [132.236.71.54]) by postoffice.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id OAA15546 for ; Thu, 8 Nov 2001 14:45:01 -0500 (EST) From: "hao ming" To: Subject: 615 PAPER 39 Date: Thu, 8 Nov 2001 14:44:37 -0500 Message-ID: <000201c1688d$ccab2450$3647ec84@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.2627 Importance: Normal X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000 SPAN: an energy-efficient coordination algorithms for topology maintainence in ad hoc networks By Benjie Chen the main idea of this paper is truning off some nodes which are dile so that not only the connectivity of the whole networks are ensured but also energy of idle nodes are saved. turning off nodes comes from the fact that the node consumes much energy even when they are idle. the main challenge is that how to maintain the networks connectivity while turning off some nodes. the paper introduces the coordinator concept and proposes an coordinator algorithms which is based on local information. this algorithm works in the following way: 1. every node advitises hello messages periodically which include its neighbors and coordinator infomation. 2. node elects itself as coordinators based on: a. if its two neighbors can not be connected either directly or via one or two coordinators, the node should become a coordinator. b. the node which connects two network partitions always becomes an coordinator. c. senders and recievers are coordinators automatically. d. in order to avoid contention, a delay is introduced before the node anounces its willingness to become a coordinator. the delay is based on utility and energy consumption of the node. problems: 1. utility is based on ratio of additional pairs to the number of nodes. why not just considering the absolute number of additional pairs? 2. how quick the algorithm can respond to the change of coordinators? if it is slow, it is only usable for networks why there is little traffic. -ming From jcb35@cornell.edu Thu Nov 8 14:49:43 2001 Return-Path: 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.7) with ESMTP id fA8JnbR11934 for ; Thu, 8 Nov 2001 14:49:37 -0500 (EST) 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 OAA03666 for ; Thu, 8 Nov 2001 14:49:33 -0500 (EST) From: jcb35@cornell.edu Date: Thu, 8 Nov 2001 14:49:33 -0500 (EST) X-Sender: jcb35@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 39 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII This paper discusses span, an power saving technique for adhoc networks that aims to reduce energy consumption without significantly diminishing the capacity or connectivity of the network. Nodes in span elect "coordinators" form all the node in the network - the coordinators are the ones that will stay in "awake" mode and perform packet forwarding over the network. All the other nodes will remain in some power saving mode to reduce energy consumption. Span tries to ensure that the coordinators are selected so that the network is not partitioned, and it tries to balance the load out throughout the nodes in the network. It decides who becomes coordinators by determining if two neighbors of a non-coordinator node cannot reach each other directly or via one or two coordinators. If so, it will become a coordinator. After a period of time, the node can withdraw from being a coordinator, giving other nodes a chance to step up. It uses a "grace period" to ensure that the coordinators are transferred smoothly and that temporary loss of connectivity is minimized or eliminated. I thought this was a very interesting way to make local decisions about routing and energy consumption in ad hoc networks.