DuraNet Energy E cient Durable Slot Free Power Scheduling Terence Tong David Molnar and Alec Woo January 14 2004 Abstract Class project submission for CS262A Please do not cite or distribute beyond NEST Contact the authors for the latest version We present an e ective distributed power scheduling algorithm for xed low bandwidth many to one data collection sensor network applications DuraNet reduces energy consumption by avoiding collision and overhearing while having nodes sleep most of the time Because that it is hard to achieve global time synchronization while nodes are sleeping DuraNet avoids the traditional approach where global hard bound time slots are assigned to nodes for communication Instead there is no notion of global time in 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 signi cant energy savings Given a route tree topology DuraNet is also able to avoid congestion due to bu er queue over ow by careful scheduling We compare our algorithm to low power listening and classic CSMA through extensive simulation in TOSSIM 12 We nd that DuraNet achieves signi cant energy reduction over classic CSMA and low power listening while providing similar end to end reliability 1 Introduction Sensor networks are an emerging technology for collecting physical information about our environment A wireless sensor network consists of multiple nodes each out tted with a radio and sensors Data gathered by these sensors can support many di erent applications including earthquake monitoring habitat monitoring and hibernation studies Nodes can send data to a central location for storage allowing later processing and analysis One of the major challenges in sensor networks is the power limitations of sensor nodes Current battery technology can support a node for only a short amount of time without power management Because some applications place sensors in di cult to reach locations changing batteries can be impractical or even impossible 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 o the MAC layer and let the schedule itself manage media access This approach allows us to leverage information available from the application and routing layer to form a better schedule When designing a practical power scheduling mechanism we must consider the following requirements 1 A scheduling algorithm should turn o 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 a quiet medium or to handle a packet not addressed to the receiver 2 The number of transmissions should be minimized especially if transmission is comparatively expensive For example on the Berkeley mica2 mote platform it costs roughly fty percent more energy to 1 transmit a packet than to receive a packet Therefore a good protocol will have a few control packets and 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 of whether 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 same time 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 tight integration with the power scheduling layer time synchronization will result in extra transmissions incurring large energy costs 6 The schedule must respect queue bu ering A receiver bu er queue can be overwhelmed by a stream of messages from the transmitter s resulting in packet loss A protocol should be able to schedule the exact amount of packets to be sent to avoid over ow 7 The protocol itself should have a low memory footprint Limited memory may make it infeasible for each 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 consider for this work nodes may be placed in a static network with stable connectivity the protocol must detect and recover from catastrophic change We propose a protocol DuraNet that addresses these issues We focus speci cally on low data rate many to one data collection applications with rarely changing topologies and stable tra c patterns We leverage information available from these tra c patterns to derive schedules that are close to optimal and then re use these schedules for as long as possible DuraNet aggressively minimizes energy waste due to communication Because the tra c pattern is known overhearing and idle listening can be almost eliminated by carefully turning on o the radio at the right time Collisions due to a one hop hidden node problem are avoided by negotiating transmission times using exchanges of RTS and CTS Our schedule algorithm is slot free instead of dividing time periods into xed slots nodes are scheduled according to application tra c Each link wakes up for however long is necessary to handle its packet load and then sleeps Since there is no xed number of global hard bound time schedules DuraNet is able 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 for time synchronization Our synchronization can e ciently 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 tra c pattern nodes are able to allocate schedules based on knowledge of future bu er queue length In other words a schedule will not be allocated unless there is room in the