DuraNet: Energy-Efficient Durable Slot-Free Power SchedulingTerence Tong, David Molnar, and Alec WooJanuary 14, 2004AbstractClass project submission for CS262A. Please do not cite or distribute beyond NEST.Contact the authors for the latest version.We present an effective distributed power scheduling algorithm for fixed, low bandwidth, many to onedata collection sensor network applications. DuraNet reduces energy consumption by avoiding collisionand overhearing while having nodes sleep most of the time. Because that it is hard to achieve global timesynchronization while nodes are sleeping, DuraNet avoids the traditional approach where global hardbound time slots are assigned to nodes for communication. Instead, there is no notion of global timein DuraNet. Nodes allocate schedules for each link based on contention in a schedule formation phase,then re-use these schedules for a long period of time. By doing so, DuraNet is able to adapt to density,while providing significant energy savings. Given a route tree topology, DuraNet is also able to avoidcongestion due to buffer queue overflow by careful scheduling.We compare our algorithm to low power listening and classic CSMA through extensive simulation inTOSSIM[12]. We find that DuraNet achieves significant energy reduction over classic CSMA and lowpower listening, while providing similar end-to-end reliability.1 IntroductionSensor networks are an emerging technology for collecting physical information about our environment. Awireless sensor network consists of multiple nodes, each outfitted with a radio and sensors. Data gathered bythese sensors can support many different applications, including earthquake monitoring, habitat monitoring,and hibernation studies. Nodes can send data to a central location for storage, allowing later processing andanalysis.One of the major challenges in sensor networks is the power limitations of sensor nodes. Current batterytechnology can support a node for only a short amount of time without power management. Becausesome applications place sensors in difficult-to-reach locations, changing batteries can be impractical or evenimpossible. Some mechanism for conserving power and extending battery life is necessary.We focus on a power scheduling mechanism that creates a sleep/wake schedule for the radio of each node.The schedule maximizes each node’s battery lifetime while meeting its network obligations. In particular,we perform scheduling above the MAC layer, an approach pioneered by Hohlt et al.[10] At the same time,during the execution of the schedule, we turn off the MAC layer and let the schedule itself manage mediaaccess. This approach allows us to leverage information available from the application and routing layer toform a better schedule.When designing a practical power scheduling mechanism, we must consider the following requirements.1. A scheduling algorithm should turn off radios whenever nodes are not involved with communication.Nodes should avoid idle listening and overhearing. It is a clear waste of energy to do sampling on aquiet medium or to handle a packet not addressed to the receiver.2. The number of transmissions should be minimized, especially if transmission is comparatively expen-sive. For example, on the Berkeley mica2 mote platform, it costs roughly fifty percent more energy to1transmit a packet than to receive a packet. Therefore a good protocol will have a few control packetsand will spend a minimum amount of energy to route packets to their destinations.3. The protocol should be able to work in any ad-hoc environment, adapting gracefully regardless ofwhether there are thousands of neighbors or only a few.4. The protocol must work gracefully in the presence of lossy links.5. Clock skew must be handled carefully. Otherwise, it is possible for nodes to communicate at the sametime, causing collisions. While global time synchronization has been done at microsecond resolution[7], it is not clear that these mechanisms work well in the power scheduling context. Without tightintegration with the power scheduling layer, time synchronization will result in extra transmissions,incurring large energy costs.6. The schedule must respect queue buffering. A receiver buffer queue can be overwhelmed by a streamof messages from the transmitter(s) resulting in packet loss. A protocol should be able to schedule theexact amount of packets to be sent to avoid overflow.7. The protocol itself should have a low memory footprint. Limited memory may make it infeasible foreach node to keep track of all neighbors in a dense network.8. The protocol should adapt to changing network conditions. While for the applications that we considerfor this work, nodes may be placed in a static network with stable connectivity, the protocol must detectand recover from catastrophic change.We propose a protocol, DuraNet, that addresses these issues. We focus specifically on low data rate,many-to-one data collection applications with rarely changing topologies and stable traffic patterns. Weleverage information available from these traffic patterns to derive schedules that are close to optimal andthen re-use these schedules for as long as possible.DuraNet aggressively minimizes energy waste due to communication. Because the traffic pattern isknown, overhearing and idle listening can be almost eliminated by carefully turning on / off the radio at theright time. Collisions due to a one-hop hidden node problem are avoided by negotiating transmission timesusing exchanges of RTS and CTS.Our schedule algorithm is slot-free: instead of dividing time periods into fixed slots, nodes are scheduledaccording to application traffic. Each link wakes up for however long is necessary to handle its packetload and then sleeps. Since there is no fixed number of global hard bound time schedules, DuraNet isable to dynamically allocate more schedules depending on the network density. To deal with clock drift,DuraNet incorporates a parent-child time synchronization algorithm into our schedule execution; however,this algorithm piggybacks on top of data ACK messages and so introduces minimal additional overhead fortime synchronization. Our synchronization can efficiently prevent schedules from drifting into each other,thereby avoiding packet loss. In addition, we use data ACKs as a command channel.Because DuraNet forms schedules based on the application traffic pattern, nodes are able to allocateschedules based on knowledge of