Deluge Data Dissemination for Network Reprogramming at Scale Adam Chlipala Jonathan Hui Gilman Tolle University of California at Berkeley Computer Science Division Berkeley CA 94720 adamc jwhui get cs berkeley edu ABSTRACT daunting task Nevertheless users must be able to add or change the functionality of a deployed network to fully utilize its capabilities It is clear that network reprogramming is required for the success of wireless sensor networks In many cases complete knowledge of an environment is not known and makes predicting what actions to perform and when to perform them a difficult if not impossible task when developing a sensor network application Additionally requirements and environments may evolve over time making the ability to add or change functionality of a deployed network imperative Developers face a more immediate problem As sensor network research matures the number of nodes used in test beds and deployments continues to grow Test beds sized at tens of thousands of nodes are now on the horizon making manual reprogramming of nodes no longer sufficient to provide the productivity required by developers Instead they are faced with a problem where the network needs to provide greater support for debugging and testing by automating the reprogramming of nodes To support network reprogramming a protocol for the reliable distribution of a program image to nodes is required In general the program image is too large to fit in RAM and is much larger than existing protocols are designed to support A typical sensor node may only have 4 kilobytes of RAM while program images may reach sizes up to 128 kilobytes While wireless sensor networks have attracted increasing research attention protocols designed for wireless sensor networks have generally focused on the processing and communication of relatively small data objects though not without reason In general data generated by individual nodes such as temperature values usually have representation sizes on the order of bytes Additionally the resource limitations of nodes have encouraged greater focus on designing for small data objects For example the low bandwidth of the radio has kept communication packets small with a typical size around tens of bytes Small packets combined with limited memory and computation capabilities have provided little reason to consider large data objects on the order of kilobytes With the pressing need for network reprogramming the design of protocols to support large data objects can no longer be ignored We consider the problem of reliably disseminating large amounts of data to many nodes in a wireless sensor network Because of the resource constrained nature of nodes an effective algorithm should attempt to minimize the amount of energy required Additionally the In this paper we present Deluge a reliable data dissemination protocol for propagating large amounts of data i e more than can fit in RAM from one or more source nodes to all other nodes over a multihop wireless sensor network To achieve robustness to lossy communication and node failures we adopt an epidemic approach Representing the data object as a set of fixed sized pages provides a manageable unit of transfer which supports spatial multiplexing and provisions for incremental upgrades Due to the large data size we identify a set of possible optimizations and evaluate their effectiveness We demonstrate that the Deluge algorithm reliably distributes data across an increasingly sized multi hop network while maintaining a constant amount of local state We also demonstrate that the energy required to distribute this data is within the allowable per mote energy budget Future directions include new methods for contention management and more effective power scheduling Keywords Sensor Networks Data Dissemination Network Reprogramming 1 INTRODUCTION Wireless sensor networks show great promise in their ability to provide extensive unobtrusive monitoring for extended periods of time These networks are composed of large numbers of small inexpensive nodes that integrate sensing computation and wireless communication In general sensor nodes have multiple resource constraints including limited memory and computational power low bandwidth communication and scarce energy resources One of the proclaimed advantages of sensor networks is their ability to operate for extended periods of time without physical intervention by humans For example sensor networks may be used in remote or hostile locations too dangerous for humans to enter In environmental applications sensor networks can be used where the mere presence of humans during the study may disturb results The very nature of these applications makes physical interaction with nodes for maintenance purposes unacceptable Furthermore the sheer number of nodes can make physical maintenance a CS262 CS294 1 Fall 2003 Class Project Authors are listed in alphabetical order 1 medium when possible Deluge is similar to SPIN RL 12 in that it makes use of a three stage advertisement request data handshaking protocol SPIN RL is designed for broadcast network models and provides reliability in lossy networks by allowing nodes to make additional requests for lost data Trickle 14 builds upon this approach by proposing suppression mechanisms for control and data messages and methods for periodically broadcasting advertisements to increase reliability However because these approaches are targeted at the dissemination of small data objects various optimizations required for efficiently supporting large data objects are not considered For example methods for spatial multiplexing are not considered because the latency for transferring small data objects between nodes is low Other examples include intelligent sender selection and the possibility of forward error correction Other dissemination protocols use less ad hoc approaches by relying on an underlying topology A reliable broadcast protocol which makes use of a clustered topology has been proposed 17 Other approaches include the construction of minimum connected dominating sets 4 22 These approaches are advantageous in that fewer control messages are required for eliminating redundancies when actively disseminating the data However the construction of such topologies can be complex and makes protocols based on these topologies relatively inflexible to variations in connectivity length of time required to distribute the data should be minimized While time may not be