Deluge: Data Dissemination for Network Reprogrammingat Scale∗Adam Chlipala, Jonathan Hui, Gilman Tolle†University of California at BerkeleyComputer Science DivisionBerkeley, CA 94720{adamc,jwhui,get}@cs.berkeley.eduABSTRACTIn this paper, we present Deluge, a reliable data dissemi-nation protocol for propagating large amounts of data (i.e.more than can fit in RAM) from one or more source nodesto all other nodes over a multihop, wireless sensor network.To achieve robustness to lossy communication and node fail-ures, we adopt an epidemic approach. Representing the dataobject as a set of fixed-sized pages provides a manageableunit of transfer which supports spatial multiplexing and pro-visions for incremental upgrades. Due to the large data size,we identify a set of possible optimizations and evaluate theireffectiveness.We demonstrate that the Deluge algorithm reliably dis-tributes data across an increasingly sized multi-hop networkwhile maintaining a constant amount of local state. We alsodemonstrate that the energy required to distribute this datais within the allowable per-mote energy budget. Future di-rections include new methods for contention managementand more effective power scheduling.KeywordsSensor Networks, Data Dissemination, Network Reprogram-ming1. INTRODUCTIONWireless sensor networks show great promise in their abil-ity to provide extensive, unobtrusive monitoring for extendedperiods of time. These networks are composed of large num-bers of small, inexpensive nodes that integrate sensing, com-putation, and wireless communication. In general, sensornodes have multiple resource constraints including limitedmemory and computational power, low bandwidth commu-nication, and scarce energy resources.One of the proclaimed advantages of sensor networks istheir ability to operate for extended periods of time with-out physical intervention by humans. For example, sensornetworks may be used in remote or hostile locations too dan-gerous for humans to enter. In environmental applications,sensor networks can be used where the mere presence of hu-mans during the study may disturb results. The very natureof these applications makes physical interaction with nodesfor maintenance purposes unacceptable. Furthermore, thesheer number of nodes can make physical maintenance a∗CS262/CS294-1, Fall 2003 Class Project†Authors are listed in alphabetical order.daunting task. Nevertheless, users must be able to add orchange the functionality of a deployed network to fully uti-lize its capabilities.It is clear that network reprogramming is required for thesuccess of wireless sensor networks. In many cases, completeknowledge of an environment is not known and makes pre-dicting what actions to perform and when to perform thema difficult, if not impossible, task when developing a sensornetwork application. Additionally, requirements and envi-ronments may evolve over time, making the ability to addor change functionality of a deployed network imperative.Developers face a more immediate problem. As sensornetwork research matures, the number of nodes used in testbeds and deployments continues to grow. Test beds sizedat tens of thousands of nodes are now on the horizon, mak-ing manual reprogramming of nodes no longer sufficient toprovide the productivity required by developers. Instead,they are faced with a problem where the network needs toprovide greater support for debugging and testing by au-tomating the reprogramming of nodes. To support networkreprogramming, a protocol for the reliable distribution of aprogram image to nodes is required. In general, the programimage is too large to fit in RAM and is much larger thanexisting protocols are designed to support. A typical sen-sor node may only have 4 kilobytes of RAM while programimages may reach sizes up to 128 kilobytes.While wireless sensor networks have attracted increas-ing research attention, protocols designed for wireless sen-sor networks have generally focused on the processing andcommunication of relatively small data objects, though notwithout reason. In general, data generated by individualnodes, such as temperature values, usually have representa-tion sizes on the order of bytes. Additionally, the resourcelimitations of nodes have encouraged greater focus on de-signing for small data objects. For example, the low band-width of the radio has kept communication packets smallwith a typical size around tens of bytes. Small packets, com-bined with limited memory and computation capabilities,have provided little reason to consider large data objects onthe order of kilobytes.With the pressing need for network reprogramming, thedesign of protocols to support large data objects can nolonger be ignored. We consider the problem of reliably dis-seminating large amounts of data to many nodes in a wire-less sensor network. Because of the resource constrainednature of nodes, an effective algorithm should attempt tominimize the amount of energy required. Additionally, the1length of time required to distribute the data should be min-imized. While time may not be important for many deploy-ments, it is useful for the purposes of debugging and testingduring development. Sufficient support for incremental up-grades should also be provided since program data oftenevolves slowly.In this paper, we present Deluge, a reliable data dissemi-nation protocol for propagating large amounts of data (i.e.more than can fit in RAM) from one or more source nodesto all other nodes over a multihop, wireless sensor network.To achieve robustness to lossy communication and node fail-ures, we adopt an epidemic approach. Representing the dataobject as a set of fixed-sized pages provides a manageableunit of transfer which supports spatial multiplexing and pro-visions for incremental upgrades. In Section 2 of this paper,we review related work. In Section 3 we formally definethe problem we address, state our assumptions, and iden-tify metrics for evaluation. We describe the basic protocol inSection 4 and identify a set of possible optimizations in Sec-tion 5. We provide simulation results and evaluate the basicprotocol along with our proposed optimizations in Section6, list future work in Section 7, and conclude with Section8.2. RELATED WORKThe problem we address can be considered a special caseof reliable data dissemination. The main difference is theneed to distribute relatively large amounts of data to manynodes. We build on a body of work on both wired andwireless