Minimum-Energy Asynchronous Dissemination to MobileSinks in Wireless Sensor NetworksHyung Seok Kim∗School of ElectricalEngineeringSeoul National UniversitySeoul, Republic of [email protected] F. AbdelzaherDepartment of ComputerScienceUniversity of VirginiaCharlottesville, VA [email protected] Hyun KwonSchool of ElectricalEngineeringSeoul National UniversitySeoul, Republic of [email protected] dissemination from sources to sinks is one of the mainfunctions in sensor networks. In this paper, we proposeSEAD, a Scalable Energy-efficient Asynchronous Dissemi-nation protocol, to minimize energy consumption in bothbuilding the dissemination tree and disseminating data tomobile sinks. SEAD considers the distance and the packettraffic rate among nodes to create near-optimal dissemina-tion trees. The sinks can move without reporting their lo-cation to the tree while receiving data updates successfully.Our evaluation results illustrate that SEAD consumes lessenergy on building and maintaining a dissemination tree tomultiple mobile sinks compared to other approaches such asdirected diffusion, TTDD, and mobile ad hoc multicast.Categories and Subject DescriptorsC.2.1 [Computer-communication Networks]: NetworkArchitecture and Design—wireless communication, distributednetworks; D.2.8 [Software Engineering]: Metrics—per-formance measuresGeneral TermsDesignKeywordsSensor network, asynchronous dissemination, minimum en-ergy, mobility1. INTRODUCTIONA sensor network is a multi-hop ad hoc wireless networkof hundreds or thousands of unattended sensors. The sen-sor nodes collect useful information such as acoustic, light,∗Work on this paper was conducted when H.S.Kim was avisiting researcher at University of Virginia.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.SenSys’03, November 5–7, 2003, Los Angeles, California, USA.Copyright 2003 ACM 1-58113-707-9/03/0011 ...$5.00.and seismic measurements, and play a dual role as bothdata generators and routers. These sensor nodes communi-cate through wireless channels and are powered by limiteddisposable batteries. Data sources in sensor networks areusually locations where environmental activities of interesttake place [6, 12, 8]. The monitoring terminals, called sinks,gathering the sensor readings, may be mobile PDAs carriedby users or may be static access points. The sinks monitor-ing the sensor nodes may have different service requirementssuch as the desired data refresh rate and the end-to-end de-lay between the source and the sink. An example of a sensornetwork application is a group of mobile decontaminatingrobots or soldiers with wireless computing devices that usethe sensor network for monitoring the chemical or radioac-tive contamination level of some region.Energy is identified as the most crucial resource in sen-sor networks due to the difficulty of recharging batteries ofthousands of devices in remote or hostile environments. Theenergy consumption of each sensor node is dominated by thecost of transmitting and receiving messages [22]. The im-portance of optimizing communication energy is supportedby measurements from prototypes of sensor network devicessuch as MICA2 [7] and their predecessors [13]. When sinksare mobile in sensor networks, communication consists ofthree main parts: building the dissemination tree (d-tree),disseminating data, and maintaining linkage to mobile sinks.Our algorithm addresses energy savings at each of thesethree levels.We propose a Scalable Energy-efficient Asynchronous Dis-semination protocol (SEAD), a distributed self-organizingprotocol that saves communication energy. It extends priorwork [2] in that sinks are mobile and high network density isnot assumed. Unlike overlay multicast [5, 10] in mobile adhoc networks, SEAD does not use mobile sinks as intermedi-ate members of the tree. This precludes frequent changes ofthe dissemination path due to sink mobility. When mobilesinks join the tree, SEAD does not use flooding to find anentry to the tree, which is in contrast to approaches suchas [15] and [25]. A disadvantage of flooding is that it costsmuch energy and incurs unnecessary collisions. In SEAD,a stationary sensor node takes the mobile sink’s place forbuilding an optimal dissemination tree. Data disseminationpaths to these stationary terminals are selected to minimizeenergy cost. As sinks move away from their terminals, theforwarding delay to the sink increases. A trade-off existsbetween minimizing that delay and saving energy spent onreconfiguring the tree. In this paper, we show that it is pos-sible to achieve considerable savings in power consumptionexp ended on communication to mobile sinks at the expenseof a moderate increase in path delay. Exploration of thistrade-off is the main principle that underlies the design ofour protocol.The remainder of this paper is organized as follows. Sec-tion 2 presents the assumptions and basic service model.Sections 3 and 4 describe the SEAD protocols to constructand maintain the d-tree for mobile sinks and minimize en-ergy consumption. A comparative performance evaluationusing simulation is presented in Section 5. Section 6 reviewsrelated work. The paper concludes with Section 7.2. ASSUMPTIONS AND BASIC MODELThis section presents the basic model of the sensor net-work which SEAD targets, where multiple mobile sinks re-ceive sensor readings from the source at varying rates. Thenetwork model for SEAD makes the following basic assump-tions:• Each sensor node is assumed to be aware of its own ge-ographic location. The network can use location servicessuch as [4] and [1] to estimate the locations of the individ-ual nodes. The location estimation does not require GPS atevery node.• After having been deployed, sensor nodes remain station-ary at their initial locations.• The sensor nodes are homogeneous and wireless chan-nels are bidirectional. Each sensor node has a constrainedbattery energy.• Sensor nodes communicate with sinks by delivering dataacross multiple hops. That is to say, sources and sinks aretypically much further apart than a single radio radius.2.1