23-02-2011, 02:28 PM
Minimizing Delay and Maximizing Lifetime forWireless Sensor Networks With Anycast
Abstract
In this paper, we are interested in minimizing thedelay and maximizing the lifetime of event-driven wireless sensornetworks for which events occur infrequently. In such systems,most of the energy is consumed when the radios are on, waitingfor a packet to arrive. Sleep–wake scheduling is an effective mechanismto prolong the lifetime of these energy-constrained wirelesssensor networks. However, sleep–wake scheduling could result insubstantial delays because a transmitting node needs to wait forits next-hop relay node to wake up. An interesting line of workattempts to reduce these delays by developing “anycast”-basedpacket forwarding schemes, where each node opportunisticallyforwards a packet to the first neighboring node that wakes upamong multiple candidate nodes. In this paper, we first study howto optimize the anycast forwarding schemes for minimizing theexpected packet-delivery delays from the sensor nodes to the sink.Based on this result, we then provide a solution to the joint controlproblem of how to optimally control the system parameters ofthe sleep–wake scheduling protocol and the anycast packet-forwardingprotocol to maximize the network lifetime, subject toa constraint on the expected end-to-end packet-delivery delay.Our numerical results indicate that the proposed solution canoutperform prior heuristic solutions in the literature, especiallyunder practical scenarios where there are obstructions, e.g., a lakeor a mountain, in the coverage area of the wireless sensor network.Index Terms—Anycast, delay, energy-efficiency, sensor network,sleep–wake scheduling.
I. INTRODUCTION
RECENT advances in wireless sensor networks have resultedin a unique capability to remotely sense the environment.These systems are often deployed in remote or hard-toreachareas. Hence, it is critical that such networks operate unattendedfor long durations. Therefore, extending network lifetimethrough the efficient use of energy has been a key issue inthe development of wireless sensor networks. In this paper, wefocus on event-driven asynchronous sensor networks with lowdata rates, where events occur rarely. This is an important classof sensor networks that has many applications such as environmentalmonitoring, intrusion detection, etc. In such systems,there are four main sources of energy consumption: energy requiredto keep the communication radios on; energy requiredfor the transmission and reception of control packets; energyrequired to keep sensors on; and energy required for data transmissionand reception. The fraction of total energy consumptionfor data transmission and reception is relatively small in thesesystems because events occur so rarely. The energy requiredto sense events is usually a constant and cannot be controlled.Hence, the energy expended to keep the communication systemon (for listening to the medium and for control packets) is thedominant component of energy consumption, which can be controlledto extend the network lifetime. Thus, sleep–wake schedulingbecomes an effective mechanism to prolong the lifetimeof energy-constrained event-driven sensor networks. By puttingnodes to sleep when there are no events, the energy consumptionof the sensor nodes can be significantly reduced.Various kinds of sleep–wake scheduling protocols have beenproposed in the literature. Synchronized sleep–wake schedulingprotocols have been proposed in [2]–[6]. In these protocols,sensor nodes periodically or aperiodically exchange synchronizationinformation with neighboring nodes. However, suchsynchronization procedures could incur additional communicationoverhead and consume a considerable amount of energy.On-demand sleep–wake scheduling protocols have been proposedin [7] and [8], where nodes turn off most of their circuitryand always turn on a secondary low-powered receiver to listento “wake-up” calls from neighboring nodes when there is a needfor relaying packets. However, this on-demand sleep–wakescheduling can significantly increase the cost of sensor motesdue to the additional receiver. In this paper, we are interested inasynchronous sleep–wake scheduling protocols such as thoseproposed in [9]–[11]. In these protocols, each node wakes upindependently of neighboring nodes in order to save energy.However, due to the independence of the wake-up processes,additional delays are incurred at each node along the path tothe sink because each node needs to wait for its next-hop nodeto wake up before it can transmit the packet. This delay couldbe unacceptable for delay-sensitive applications, such as firedetection or a tsunami alarm, which require the event reportingdelay to be small.Prior work in the literature has proposed the use of anycastpacket-forwarding schemes (also called opportunistic forwardingschemes) to reduce this event reporting delay [12]–[20].Under traditional packet-forwarding schemes, every node hasone designated next-hop relaying node in the neighborhood, and it has to wait for the next-hop node to wake up when it needs toforward a packet. In contrast, under anycast packet-forwardingschemes, each node has multiple next-hop relaying nodes in acandidate set (we call this set the forwarding set) and forwardsthe packet to the first node that wakes up in the forwarding set.It is easy to see that, compared to the basic scheme in [9]–[11],anycast clearly reduces the expected one-hop delay. For example,assuming that there are nodes in the forwarding set, andthat each node wakes up independently according to the Poissonprocess with the same rate, then anycast can result in a -foldreduction in the expected one-hop delay.However, anycast does not necessarily lead to the minimumexpected end-to-end delay because a packet can still be relayedthrough a time-consuming routing path. Therefore, the firstchallenge for minimizing the expected end-to-end delay isto determine how each node should choose its anycast forwardingpolicy (e.g., the forwarding set) carefully. The work in[12]–[14] proposes heuristic anycast protocols that exploit thegeographical distance to the sink node. The work in [15] and[16] considers MAC-layer anycast protocols that work with theseparate routing protocols in the network layer. However, thesesolutions are heuristic in nature and do not directly minimizethe expected end-to-end delay. The algorithms in [17]–[20] usethe hop-count information (i.e., the number of hops for eachnode to reach the sink) to minimize some state-dependent cost(delay) metric along the possible routing paths. However, thesealgorithms do not directly apply to asynchronous sleep–wakescheduling, where each node does not know the wake-upschedule of neighboring nodes when it has a packet to forward.(In Section V, we will introduce another hop-count-basedalgorithm inspired by the idea in [19] and [20].)The second challenge stems from the fact that good performancecannot be obtained by studying the anycast forwardingpolicy in isolation. Rather, it should be jointly controlled withthe parameters of sleep–wake scheduling (e.g., the wake-up rateof each node). Note that the latter will directly impact bothnetwork lifetime and the packet-delivery delay. Hence, to optimallytradeoff network lifetime and delay, both the wake-uprates and the anycast packet-forwarding policy should be jointlycontrolled. However, such interactions have not been systematicallystudied in the literature [12]–[20].In this paper, we address these challenges. We first investigatethe delay-minimization problem: given the wake-uprates of the sensor nodes, how to optimally choose the anycastforwarding policy to minimize the expected end-to-end delayfrom all sensor nodes to the sink.We develop a low-complexityand distributed solution to this problem. We then formulatethe lifetime maximization problem: given a constraint on theexpected end-to-end delay, how to maximize the network lifetimeby jointly controlling the wake-up rates and the anycastpacket-forwarding policy. We show how to use the solutionto the delay-minimization problem to construct an optimalsolution to the lifetime-maximization problem for a specificdefinition of network lifetime.Before we present the details of our problem formulationand the solution, we make a note regarding when the anycastprotocols and the above optimization algorithms are applied.We can view the lifetime of an event-driven sensor network asconsisting of two phases: the configuration phase and the operationphase. When nodes are deployed, the configuration phasebegins, during which nodes optimize the control parametersof the anycast forwarding policy and their wake-up rates. It isduring this phase that the optimization algorithms discussedin the last paragraph will be executed. In this phase, sensornodes do not even need to follow asynchronous sleep–wakepatterns. After the configuration phase, the operation phasefollows. In the operation phase, each node alternates betweentwo subphases, i.e., the sleeping subphase and the event-reportingsubphase. In the sleeping subphase, each node simplyfollows the sleep–wake pattern determined in the configurationphase, waiting for events to occur. Note that since we areinterested in asynchronous sleep–wake scheduling protocols,the sensor nodes do not exchange synchronization messagesin this sleeping subphase. Finally, when an event occurs, theinformation needs to be passed on to the sink as soon as possible,which becomes the event-reporting subphase. It is in thisevent reporting subphase when the anycast forwarding protocolis actually applied, using the control parameters chosen duringthe configuration phase. Note that the configuration phaseonly needs to be executed once because we assume that thefraction of energy consumed due to the transmission of datais negligible. However, if this is not the case, the transmissionenergy will play a bigger role in reducing the residual energyat each node in the network. In this case, as long as the fractionof energy consumed due to data transmission is still small (butnot negligible), the practical approach would be for the sink toinitiate a new configuration phase after a long time has passed.The rest of this paper is organized as follows. In Section II, wedescribe the system model and introduce the delay-minimizationproblem and the lifetime-maximization problem that we intendto solve. In Section III, we develop a distributed algorithmthat solves the delay-minimization problem. In Section IV, wesolve the lifetime-maximization problem using the precedingresults. In Section V, we provide simulation results that illustratethe performance of our proposed algorithm compared toother heuristic algorithms in the literature.
II. SYSTEM MODEL
We consider a wireless sensor network with nodes. Letdenote the set of all nodes in the network. Each sensor node is incharge of both detecting events and relaying packets. If a nodedetects an event, the node packs the event information into apacket and delivers the packet to a sink via multihop relaying.We assume that every node has at least one such multihop pathto the sink.We also assume that there is a single sink. However,the analysis can be generalized to the case with multiple sinks(see [21, Subsection III-D]).We assume that the sensor network employs asynchronoussleep–wake scheduling to improve energy efficiency, andnodes choose the next-hop node and forward the packet to thechosen node using the following basic sleep–wake schedulingprotocol. This basic protocol generalizes typical asynchronoussleep–wake scheduling protocols in [9]–[11] to account foranycast. For ease of exposition, in this basic protocol, weassume that there is a single source that sends out event-reportingpackets to the sink. This is the most likely operatingmode because when nodes wake up asynchronously and withlow duty-cycles, the chance of multiple sources generatingevent-reporting packets simultaneously is small. Furthermore,this basic protocol ignores the detailed effects of collision (We can extend this basic protocol to account for the case ofcollisions by multiple senders (including hidden terminals)or by multiple receivers. The detailed protocol is providedin Section V of our online technical report [21].) The sensornodes sleep for most of the time and occasionally wake up fora short period of time . When a node has a packet fornode to relay, it will send a beacon signal and an ID signal(carrying the sender information) for time periods and ,respectively, and then hear the medium for time period .If the node does not hear any acknowledgment signal fromneighboring nodes, it repeats this signaling procedure. When aneighboring node wakes up and senses the beacon signal, itkeeps awake, waiting for the following ID signal to recognizethe sender. When node wakes up in the middle of an IDsignal, it keeps awake, waiting for the next ID signal. If nodesuccessfully recognizes the sender, and it is a next-hop nodeof node , it then communicates with node to receive thepacket. Node can then use a similar procedure to wake up itsown next-hop node. If a node wakes up and does not sense abeacon signal or ID signal, it will then go back to sleep. In thispaper, we assume that the time instants that a node wakes upfollow a Poisson random process with rate . We also assumethat the wake-up processes of different nodes are independent.The independence assumption is suitable for the scenario inwhich the nodes do not synchronize their wake-up times, whichis easier to implement than the schemes that require globalsynchronization [3]–[5]. The advantage of Poisson sleep–wakescheduling is that, due to its memoryless property, sensor nodesare able to use a time-invariant optimal policy to maximize thenetwork lifetime (see the discussion at the end of Section III-B).While the analysis in this paper focuses on the case when thewake-up times follow a Poisson process, we expect that themethodology in the paper can also be extended to the casewith non-Poisson wake-up processes, with more technicallyinvolved analysis.A well-known problem of using sleep–wake scheduling insensor networks is the additional delay incurred in transmittinga packet from source to sink because each node along the transmissionpath has to wait for its next-hop node to wake up. Toreduce this delay, we use an anycast forwarding scheme as describedin Fig. 1. Let denote the set of nodes in the transmissionrange of node . Suppose that node has a packet, andit needs to pick up a node in its transmission range to relaythe packet. Each node maintains a list of nodes that node intendsto use as a forwarder. We call the set of such nodes theforwarding set, which is denoted by for node . In addition,each node is also assumed to maintain a list of nodes that usenode as a forwarder (i.e., ). As shown in Fig. 1, nodestarts sending a beacon signal and an ID signal successively. Allnodes in can hear these signals, regardless of whom these signalsare intended for. A node that wakes up during the beaconsignal or the ID signal will check if it is in the forwarding setof node . If it is, node sends one acknowledgment after theID signal ends. After each ID signal, node checks whetherthere is any acknowledgment from the nodes in . If no acknowledgmentis detected, node repeats the beacon-ID-signalingand acknowledgment-detection processes until it hearsone. On the other hand, if there is an acknowledgment, it maytake additional time for node to identify which node acknowledgesthe beacon-ID signals, especially when there are multiple nodes thatwake up at the same time. Let denote the resolutionperiod, during which time node identifies which nodes havesent acknowledgments. If there are multiple awake nodes, nodechooses one node among them that will forward the packet.After the resolution period, the chosen node receives the packetfrom node during the packet transmission period , and thenstarts the beacon-ID-signaling and acknowledgment-detectionprocesses to find the next forwarder. Since nodes consume energywhen awake, should be as small as possible. However,if is too small, a node that wakes up right after an IDsignal could return to sleep before the following beacon signal.In order to avoid this case, we set , whereis a small amount of time required for a node to detectsignal in the wireless medium. In the rest of the paper, we assumethat is negligible compared to .
download full report
http://cobweb.ecn.purdue.edu/~linx/paper...-sleep.pdf
