Energy conservation in wireless sensor networks: A survey
`Giuseppe Anastasia, Marco Contib,*, Mario Di Francescoa,*, Andrea Passarellab
`a Department of Information Engineering, University of Pisa, via Diotisalvi 1, 56122 Pisa, Italy
`b Institute for Informatics and Telematics (IIT), National Research Council (CNR), via G. Moruzzi 1, 56124 Pisa, Italy
`article info
`Article history:
`Received 26 February 2008
`Accepted 30 June 2008
`Available online 29 July 2008
`Keywords:
`Wireless sensor networks
`Survey
`Energy efficiency
`Power management
`abstract
`In the last years, wireless sensor networks (WSNs) have gained increasing attention from
`both the research community and actual users. As sensor nodes are generally battery-pow-
`ered devices, the critical aspects to face concern how to reduce the energy consumption of
`nodes, so that the network lifetime can be extended to reasonable times. In this paper we
`first break down the energy consumption for the components of a typical sensor node, and
`discuss the main directions to energy conservation in WSNs. Then, we present a systematic
`and comprehensive taxonomy of the energy conservation schemes, which are subse-
`quently discussed in depth. Special attention has been devoted to promising solutions
`which have not yet obtained a wide attention in the literature, such as techniques for
`energy efficient data acquisition. Finally we conclude the paper with insights for research
`directions about energy conservation in WSNs.
`/C2112008 Elsevier B.V. All rights reserved.
`1. Introduction
`A wireless sensor network consists of sensor nodes de-
`ployed over a geographical area for monitoring physical
`phenomena like temperature, humidity, vibrations, seismic
`events, and so on [5]. Typically, a sensor node is a tiny
`device that includes three basic components: a sensing
`subsystem for data acquisition from the physical surround-
`ing environment, a processing subsystem for local data
`processing and storage, and a wireless communication
`subsystem for data transmission. In addition, a power
`source supplies the energy needed by the device to
`perform the programmed task. This power source often
`consists of a battery with a limited energy budget. In addi-
`tion, it could be impossible or inconvenient to recharge the
`battery, because nodes may be deployed in a hostile or
`unpractical environment. On the other hand, the sensor
`network should have a lifetime long enough to fulfill the
`application requirements. In many cases a lifetime in the
`order of several months, or even years, may be required.
`Therefore, the crucial question is: ‘‘how to prolong the net-
`work lifetime to such a long time?”
`In some cases it is possible to scavenge energy from the
`external environment [59] (e.g., by using solar cells as
`power source). However, external power supply sources
`often exhibit a non-continuous behavior so that an energy
`buffer (a battery) is needed as well. In any case, energy is a
`very critical resource and must be used very sparingly.
`Therefore, energy conservation is a key issue in the design
`of systems based on wireless sensor networks.
`In this paper we will refer mainly to the sensor network
`model depicted inFig. 1and consisting of onesink node(or
`base station) and a (large) number of sensor nodes de-
`ployed over a large geographic area (sensing field).Data
`are transferred from sensor nodes to the sink through a
`multi-hop communication paradigm[5]. We will consider
`first the case in which both the sink and the sensor nodes
`are static (static sensor network). Then, we will also dis-
`cuss energy conservation schemes for sensor networks
`with mobile elements in Section6, in which a sparse sen-
`sor network architecture – where continuous end-to-end
`paths between sensor nodes and the sink might not be
`available – will be accounted as well.
`1570-8705/$ - see front matter/C2112008 Elsevier B.V. All rights reserved.
`doi:10.1016/j.adhoc.2008.06.003
`* Corresponding authors. Tel.: +39 050 315 3062; fax: +39 050 315
`2593 (M. Conti).
`E-mail addresses: giuseppe.anastasi@iet.unipi.it (G. Anastasi),
`marco.conti@iit.cnr.it (M. Conti), mario.difrancesco@iet.unipi.it
`(M. Di Francesco),andrea.passarella@iit.cnr.it (A. Passarella).
`Ad Hoc Networks 7 (2009) 537–568
`Contents lists available atScienceDirect
`Ad Hoc Networks
`journal homepage: www.else vier.com/locate/adhoc
`SCT Exhibit 2025
`IPR2025-01183
`
`
`
`
`
`
`
`Experimental measurements have shown that generally
`data transmission is very expensive in terms of energy con-
`sumption, while data processing consumes significantly
`less [108]. The energy cost of transmitting a single bit of
`information is approximately the same as that needed for
`processing a thousand operations in a typical sensor node
`[103]. The energy consumption of the sensing subsystem
`depends on the specific sensor type. In many cases it is
`negligible with respect to the energy consumed by the pro-
`cessing and, above all, the communication subsystems. In
`other cases, the energy expenditure for data sensing may
`be comparable to, or even greater than, the energy needed
`for data transmission. In general, energy-saving techniques
`focus on two subsystems: the networking subsystem (i.e.,
`energy management is taken into account in the opera-
`tions of each single node, as well as in the design of net-
`working protocols), and the sensing subsystem (i.e.,
`techniques are used to reduce the amount or frequency
`of energy-expensive samples).
`The lifetime of a sensor network can be extended by
`jointly applying different techniques[10]. For example, en-
`ergy efficient protocols are aimed at minimizing the energy
`consumption during network activities. However, a large
`amount of energy is consumed by node components
`(CPU, radio, etc.) even if they are idle. Power management
`schemes are thus used for switching off node components
`that are not temporarily needed.
`In this paper we will survey the main enabling tech-
`niques used for energy conservation in wireless sensor net-
`works. Specifically, we focus primarily on the networking
`subsystem by considering duty cycling. Furthermore, we
`will also survey the main techniques suitable to reduce the
`energy consumption of sensors when the energy cost for
`data acquisition (i.e. sampling) cannot be neglected. Finally,
`we will introduce mobility as a new energy conservation
`paradigm with the purpose of prolonging the network life-
`time. These techniques are the basis for any networking pro-
`tocol and solution optimized from an energy-saving point of
`view. Due to the fundamental role of these enabling tech-
`niques, we will stress the design principles behind them
`and their features instead of presenting a complete set of
`networking protocols for wireless sensor networks. For a
`survey on these aspects, the reader is referred to[39 and 99].
`The rest of the paper is organized as follows. Section2
`discusses the general approaches to energy conservation
`in sensor nodes, and introduces the three main approaches
`(duty-cycling, data-driven, and mobility). In Section3 we
`break down this high-level classification, and highlight
`the schemes that will be then described in detail in the fol-
`lowing sections. Specifically, Section4 deals with schemes
`related to the data-driven approach. Section5 presents ap-
`proaches related to the data-driven approach. Section6
`discusses schemes related to the mobility-based approach.
`Finally, conclusions and open issues are discussed in Sec-
`tion 7.
`2. General approaches to energy conservation
`Before discussing the high-level classification of energy
`conservation proposals, it is worth presenting the net-
`work- and node-level architecture we will refer to.
`From a sensor network standpoint, we mainly consider
`the model depicted in Fig. 1, which is the most widely
`Sink
`Internet
`Remote
`Controller
`Sensor
`Field Sensor
`NodeUser
`Fig. 1. Sensor network architecture.
`ADCSensors Radio
`Memory
`MCU
`DC-DCBattery
`Mobilizer Location Finding SystemPower Generator
`Power Supply Subsystem Sensing Subsystem
`Processing
`Subsystem
`Communication
`Subsystem
`Fig. 2. Architecture of a typical wireless sensor node.
`538 G. Anastasi et al. / Ad Hoc Networks 7 (2009) 537–568
`SCT Exhibit 2025
`IPR2025-01183
`
`
`
`
`
`
`
`adopted model in the literature. On the other side,Fig. 2
`shows the architecture of a typical wireless sensor node,
`as usually assumed in the literature. It consists of four
`main components: (i) a sensing subsystem including one
`or more sensors (with associated analog-to-digital con-
`verters) for data acquisition; (ii) a processing subsystem
`including a micro-controller and memory for local data
`processing; (iii) aradio subsystem for wireless data com-
`munication; and (iv) a power supply unit. Depending on
`the specific application, sensor nodes may also include
`additional components such as a location finding system
`to determine their position, a mobilizer to change their
`location or configuration (e.g., antenna’s orientation), and
`so on. However, as the latter components are optional,
`and only occasionally used, we will not take them into ac-
`count in the following discussion.
`Obviously, the power breakdown heavily depends on
`the specific node. In[108] it is shown that the power char-
`acteristics of a Mote-class node are completely different
`from those of a Stargate node. However, the following re-
`marks generally hold[108].
`/C15 The communication subsystem has an energy consump-
`tion much higher than the computation subsystem. It
`has been shown that transmitting one bit may consume
`as much as executing a few thousands instructions
`[103]. Therefore, communication should be traded for
`computation.
`/C15 The radio energy consumption is of the same order of
`magnitude in the reception, transmission, and idle
`states, while the power consumption drops of at least
`one order of magnitude in the sleep state. Therefore,
`the radio should be put to sleep (or turned off) whenever
`possible.
`/C15 Depending on the specific application, the sensing sub-
`system might be another significant source of energy
`consumption, so its power consumption has to be
`reduced as well.
`Based on the above architecture and power breakdown,
`several approaches have to be exploited, even simulta-
`neously, to reduce power consumption in wireless sensor
`networks. At a very general level, we identify three main
`enabling techniques, namely,duty cycling, data-driven ap-
`proaches, andmobility.
`Duty cyclingis mainly focused on the networking subsys-
`tem. The most effective energy-conserving operation is
`putting the radio transceiver in the (low-power) sleep mode
`whenever communication is not required. Ideally, the radio
`should be switched off as soon as there is no more data to
`send/receive, and should be resumed as soon as a new data
`packet becomes ready. In this way nodes alternate between
`active and sleep periods depending on network activity. This
`behavior is usually referred to asduty cycling, andduty cycle
`is defined as the fraction of time nodes are active during their
`lifetime. As sensor nodes perform a cooperative task, they
`need to coordinate their sleep/wakeup times. Asleep/wake-
`up scheduling algorithmthus accompanies any duty cycling
`scheme. It is typically a distributed algorithm based on
`which sensor nodes decide when to transition from active
`to sleep, and back. It allows neighboring nodes to be active
`at the same time, thus making packet exchange feasible even
`when nodes operate with a low duty cycle (i.e., they sleep for
`most of the time).
`Duty-cycling schemes are typically oblivious to data
`that are sampled by sensor nodes. Hence,data-driven ap-
`proaches can be used to improve the energy efficiency even
`more. In fact, data sensing impacts on sensor nodes’ energy
`consumption in two ways:
`/C15 Unneeded samples. Sampled data
` generally have strong
`spatial and/or temporal correlations [137], so there is
`no need to communicate the redundant information to
`the sink.
`/C15 Power consumption of the sensing subsystem. Reducing
`communication is not enough when the sensor itself is
`power hungry.
`In the first case unneeded samples result in useless en-
`ergy consumption, even if the cost of sampling is negligi-
`ble, because they result in unneeded communications.
`The second issue arises whenever the consumption of the
`sensing subsystem is not negligible. Data driven tech-
`niques presented in the following are designed to reduce
`the amount of sampled data by keeping the sensing accu-
`racy within an acceptable level for the application.
`In case some of the sensor nodes are mobile,mobility
`can finally be used as a tool for reducing energy consump-
`tion (beyond duty cycling and data-driven techniques). In a
`static sensor network packets coming from sensor nodes
`follow a multi-hop path towards the sink(s). Thus, a few
`paths can be more loaded than others, and nodes closer
`to the sink have to relay more packets so that they are
`more subject to premature energy depletion (funneling ef-
`fect) [83]. If some of the nodes (including, possibly, the
`sink) are mobile, the traffic flow can be altered if mobile
`devices are responsible for data collection directly from
`static nodes. Ordinary nodes wait for the passage of the
`mobile device and route messages towards it, so that
`communication takes place in proximity (directly or at most
`with a limited multi-hop traversal). As a consequence, or-
`dinary nodes can save energy because path length, conten-
`tion and forwarding overheads are reduced as well. In
`addition, the mobile device can visit the network in order
`to spread more uniformly the energy consumption due to
`communications. When the cost of mobilizing sensor
`nodes is prohibitive, the usual approach is to ‘‘attach” sen-
`sor nodes to entities that will be roaming in the sensing
`field anyway, such as buses or animals.
`All of the schemes we will describe in the following fall
`under one of the three general approaches we have pre-
`sented. Specifically, we provide the complete taxonomy
`of the schemes we will describe hereafter inFig. 3. As this
`taxonomy is fairly rich, the remainder of the survey ana-
`lyzes it using a top-down approach.
`3. High-level taxonomy
`In this section we discuss the breakdown at the first lev-
`els of the taxonomy inFig. 3. The rest of the taxonomy,
`along with concrete examples proposed in the literature,
`is presented in the next sections.
`G. Anastasi et al. / Ad Hoc Networks 7 (2009) 537–568 539
`SCT Exhibit 2025
`IPR2025-01183
`
`
`
`
`
`
`
`On-demand Scheduled
`rendezvous Asynchronous TDMA Contention-
`based Hybrid Stochastic
`Approaches
`Time Series
`forecasting
`Algorithmic
`Approaches
`Energy Conservation
`Schemes
`Topology
`Control
`Power
`Management Data reduction Energy-efficent
`Data Acquisition
`Sleep/Wakeup
`Protocols
`MAC Protocols
`with Low Duty-
`Cycle
`Connection-
`drivenLocation-driven Adaptive
`Sampling
`Hierarchical
`Sampling
`Model-driven
`Active
`Sampling
`In-network
`Processing
`Data
`Compression
`Data
`Prediction
`Data-driven Mobility-basedDuty Cycling
`Mobile-sink Mobile-relay
`Fig. 3. Taxonomy of approaches to energy saving in sensor networks.
`540 G. Anastasi et al. / Ad Hoc Networks 7 (2009) 537–568
`SCT Exhibit 2025
`IPR2025-01183
`
`
`
`
`
`
`
`3.1. Duty-cycling
`As shown inFig. 4, duty cyclingcan be achieved through
`two different and complementary approaches. From one
`side it is possible to exploit node redundancy, which is typ-
`ical in sensor networks, and adaptively select only a mini-
`mum subset of nodes to remain active for maintaining
`connectivity. Nodes that are not currently needed for
`ensuring connectivity can go to sleep and save energy.
`Finding the optimal subset of nodes that guarantee con-
`nectivity is referred to astopology control1. Therefore, the
`basic idea behind topology control is to exploit the network
`redundancy to prolong the network longevity, typically
`increasing the network lifetime by a factor of 2–3 with re-
`spect to a network with all nodes always on[41,92,140].
`On the other hand, active nodes (i.e., nodes selected by the
`topology control protocol) do not need to maintain their
`radio continuously on. They can switch off the radio (i.e.,
`put it in the low-power sleep mode) when there is no net-
`work activity, thus alternating between sleep and wakeup
`periods. Throughout we will refer to duty cycling operated
`on active nodes aspower management. Therefore, topology
`control and power management are complementary tech-
`niques that implement duty cycling with different granular-
`ity. Power management techniques can be further
`subdivided into two broad categories depending on the layer
`of the network architecture they are implemented at. As
`shown inFig. 4, power management protocols can be imple-
`mented either as independent sleep/wakeup protocols run-
`ning on top of a MAC protocol (typically at the network or
`application layer), or strictly integrated with the MAC proto-
`col itself. The latter approach permits to optimize medium
`access functions based on the specific sleep/wakeup pattern
`used for power management. On the other hand, indepen-
`dent sleep/wakeup protocols permit a greater flexibility as
`they can be tailored to the application needs, and, in princi-
`ple, can be used withany MAC protocol.
`The following breakdowns for topology-control
`schemes, independent sleep/wakeup schedules and MAC
`protocols with low duty cycle are presented in Sections
`4.1, 4.2 and 4.3, respectively.
`3.2. Data-driven approaches
`Data-driven approaches (see Fig. 5) can be divided
`according to the problem they address. Specifically, data-
`reduction schemes address the case of unneeded samples,
`while energy-efficient data acquisition schemes are mainly
`aimed at reducing the energy spent by the sensing subsys-
`tem. However, some of them can reduce the energy spent
`for communication as well. Also in this case, it is worth dis-
`cussing here one more classification level related to data-
`reduction schemes, as shown inFig. 5. All these techniques
`aim at reducing the amount of data to be delivered to the
`sink node. However the principles behind them are rather
`different. In-network processingconsists in performing data
`aggregation (e.g., computing average of some values) at
`intermediate nodes between the sources and the sink. In
`this way, the amount of data is reduced while traversing
`the network towards the sink. The most appropriate in-
`network processing technique depends on the specific
`application and must be tailored to it. As data aggregation
`is application-specific, in the following we will not discuss
`it. The interested reader can refer to[39] for a comprehen-
`sive and up-to-date survey about in-network processing
`techniques. Data compression can be applied to reduce
`the amount of information sent by source nodes. This
`scheme involves encoding information at nodes which
`generate data, and decoding it at the sink. There are
`different methods to compress data (see, e.g.,
`[105,129,143,144]). As compression techniques are general
`(i.e. not necessarily related to WSNs), we will omit a de-
`tailed discussion of them to focus on other approaches spe-
`cifically tailored to WSNs. Data prediction consists in
`building an abstraction of a sensed phenomenon, i.e. a
`model describing data evolution. The model can predict
`the values sensed by sensor nodes within certain error
`bounds, and resides both at the sensors and at the sink. If
`the needed accuracy is satisfied, queries issued by users
`Duty Cycling
`Sleep/Wakeup
`Protocols
`MAC Protocols with
`Low Duty-Cycle
`Topology Control Power Management
`Fig. 4. Taxonomy of duty cycling schemes.
`1 Before proceeding on, it may be worthwhile to point out that the term
`‘‘topology control” has been used with a larger scope than that defined
`above. Some authors include in topology control also techniques that are
`aimed at super-imposing a hierarchy on the network organization (e.g.,
`clustering techniques) to reduce energy consumption. In addition, the
`terms ‘‘topology control” and ‘‘power control” are often confused. However,
`power control refers to techniques that adapt the transmission power level
`to optimize a single wireless transmission. Even if the above techniques are
`related with topology control, in accordance with[115], we believe that
`they cannot be classified as topology control techniques. Therefore, in the
`following we will refer to topology control as one of the means to reduce
`energy consumption by exploiting node redundancy.
`Data-driven
`Approaches
`Data reduction Energy-efficent
`Data Acquisition
`In-network
`Processing
`Data
`Compression Data Prediction
`Fig. 5. Taxonomy of data-driven approaches to energy conservation.
`G. Anastasi et al. / Ad Hoc Networks 7 (2009) 537–568 541
`SCT Exhibit 2025
`IPR2025-01183
`
`
`
`
`
`
`
`can be evaluated at the sink through the model without the
`need to get the exact data from nodes. On the other side,
`explicit communication between sensor nodes and the
`sink is needed when the model is not accurate enough,
`i.e. the actual sample has to be retrieved and/or the model
`has to be updated. On the whole, data prediction reduces
`the number of information sent by source nodes and the
`energy needed for communication as well.
`The following levels in the classification for data-pre-
`diction and energy-efficient data acquisition techniques
`are presented in Sections5.1 and 5.2, respectively.
`3.3. Mobility-based schemes
`As shown inFig. 6, mobility-based schemes can be clas-
`sified as mobile-sink and mobile-relay schemes, depending
`on the type of the mobile entity. They will be directly dis-
`cussed in Section 6. It is worth pointing out here that,
`when considering mobile schemes, an important issue is
`the type of control the sensor-network designer has on
`the mobility of nodes. A detailed discussion on this point
`is presented in[12 and 68]. Mobile nodes can be divided
`into two broad categories: they can be specifically de-
`signed aspart of the network infrastructure, or they can be
`part of the environment. When they are part of the infra-
`structure, their mobility can be fully controlled as they
`are, in general, robotized. When mobile nodes are part of
`the environment they might be not controllable. If they fol-
`low a strict schedule, then they have a completely predict-
`able mobility (e.g., a shuttle for public transportation[23]).
`Otherwise they may have a random behavior so that no
`reliable assumption can be made on their mobility. Finally,
`they may follow a mobility pattern that is neither predict-
`able nor completely random. For example, this is the case
`of a bus moving in a city, whose speed is subject to large
`variation due to traffic conditions. In such a case, mobility
`patterns can be learned based on successive observations
`and estimated with some accuracy.
`4. Duty-cycling
`In this section we will discuss the duty-cycling ap-
`proaches as defined in the previous section. For conve-
`nience, we report in Fig. 7 an excerpt of the taxonomy
`referred to duty-cycling.
`4.1. Topology control protocols
`The concept of topology control is strictly associated
`with that of network redundancy. Dense sensor networks
`typically have some degree of redundancy. In many cases
`network deployment is done at random, e.g., by dropping
`a large number of sensor nodes from an airplane. There-
`fore, it may be convenient to deploy a number of nodes
`greater than necessary to cope with possible node failures
`occurring during or after the deployment. In many con-
`texts it is much easier to deploy initially a greater number
`of nodes than re-deploying additional nodes when needed.
`For the same reason, a redundant deployment may be con-
`venient even when nodes are placed by hand[41]. Topol-
`ogy control protocols are thus aimed at dynamically
`adapting the network topology, based on the application
`needs, so as to allow network operations while minimizing
`the number of active nodes (and, hence, prolonging the
`network lifetime).
`Several criterions can be used to decide which nodes to
`activate/deactivate, and when. In this regard, topology con-
`trol protocols can be broadly classified in the following two
`categories (Fig. 7). Location driven protocols define which
`node to turn on and when, based on the location of sensor
`nodes which is assumed to be known.Connectivity driven
`protocols, dynamically activate/deactivate sensor nodes
`so that network connectivity, or complete sensing cover-
`age [78], are fulfilled.
`A detailed survey on topology control in wireless ad hoc
`and sensor networks is available in[72 and 115]. In the fol-
`lowing subsections we only review the main proposals for
`topology control in wireless sensor networks according to
`the above classification.
`4.1.1. Location-driven
`Geographical
`Adaptive Fidelity (GAF) [145] is a loca-
`tion-driven protocol that reduces energy consumption
`while keeping a constant level of routing fidelity. The sens-
`ing area where nodes are distributed is divided into small
`virtual grids. Each virtual grid is defined such that, for any
`two adjacent grids A and B, all nodes in A are able to com-
`municate with nodes in B, and vice-versa (seeFig. 8). All
`nodes within the same virtual grid are equivalent for rout-
`ing, and just one node at time need to be active. Therefore,
`nodes have to coordinate with each other to decide which
`one can sleep and how long.
`Initially a node starts in the discovery state where it ex-
`changes discovery messages with other nodes. After broad-
`casting the message, the node enters the active state.
`While active, it periodically re-broadcasts its discovery
`message. A node in the discovery or active state can change
`its state to sleeping when it detects that some other equiv-
`alent node will handle routing. Nodes in the sleeping state
`wake up after a sleeping time and go back to the discovery
`state. In GAF load balancing is achieved through a periodic
`re-election of the leader, i.e., the node that will remain ac-
`tive to manage routing in the virtual grid. The leader is
`chosen through a rank-based election algorithm which
`considers the nodes’ residual energy, thus allowing the
`network lifetime to increase in proportion to node density
`[145]. GAF is independent of the routing protocol, so that it
`can be used along with any existing solution of that kind.
`In addition, GAF does not significantly affect the perfor-
`mance of the routing protocol in terms of packet loss and
`message latency. However, the structure imposed over
`Mobility-based
`Schemes
`Mobile-sink Mobile-relay
`Fig. 6. Taxonomy of mobility-based energy conservation schemes.
`542 G. Anastasi et al. / Ad Hoc Networks 7 (2009) 537–568
`SCT Exhibit 2025
`IPR2025-01183
`
`
`
`
`
`
`
`the network may lead to an underutilization of the radio
`coverage areas. In fact, as all nodes within a virtual grid
`must be able to reach any node in an adjacent virtual grid,
`actually nodes are forced to cover less than half the dis-
`tance allowed by the radio range.
`Although being defined as a geographic routing proto-
`col, Geographic Random Forwarding (GeRaF)[21,153,154]
`actually presents features which are in the direction of
`location-driven duty-cycled operations, which make use
`of both node position and redundancy. Nodes follow a gi-
`ven duty cycle to switch between awake (active) and sleep
`(inactive) states. Nodes periodically switch to the active
`state, starting with a listening time, so that they can partic-
`ipate to routing if needed. Data forwarding starts as soon
`as a node has a packet to send. In this case, the node be-
`comes active and broadcasts a packet containing its own
`location and the location of the intended receiver. Then a
`receiver-initiated forwarding phase takes place. As a result,
`one of the active neighbors of the sender will be selected to
`relay the packet towards the destination. To this end, the
`main idea is that each active node has a priority which de-
`pends on its closeness to the intended destination of the
`packet. In addition to priority, a distributed randomization
`scheme is also used, in order to reduce the probability that
`many neighboring nodes are simultaneously sleeping. Spe-
`cifically, the portion of the coverage area of the sender
`which is closer to the intended destination is split into a
`number of regions. Each region has its associated priority,
`and regions are chosen so that all nodes within a region
`are closer to the destination than any other node in a re-
`gion with a lower priority (Fig. 9).
`After the broadcast, nodes in the region with the higher
`priority contend for forwarding. If only one node gets the
`channel, it simply forwards the packet and the process
`ends. Otherwise, multiple nodes may transmit simulta-
`neously, resulting in a collision. In this case, a resolution
`technique (i.e. a backoff) is applied in order to select a sin-
`gle forwarder. There may also be the case in which no node
`can forward the packet, because all nodes in the region are
`On-demand Scheduled
`rendezvous Asynchronous TDMA Contention-
`based Hybrid
`Energy Conservation
`Schemes
`Topology
`Control
`Power
`Management
`Sleep/Wakeup
`Protocols
`MAC Protocols
`with Low Duty-
`Cycle
`Connection-
`drivenLocation-driven
`Data-driven Mobility-basedDuty-cycling
`Fig. 7. Detailed taxonomy of duty cycling schemes.
`1
`2
`3
`4
`5
`r
`ABC
`r
`Fig. 8. Virtual grids in GAF.
`G. Anastasi et al. / Ad Hoc Networks 7 (2009) 537–568 543
`SCT Exhibit 2025
`IPR2025-01183
`
`
`
`
`
`
`
`sleeping. To this end, in the next transmission attempt, the
`forwarder will be chosen among nodes in the second high-
`est-priority region and so on. Every time the relay selection
`phase will be repeated until a maximum number of retries
`will be reached. Eventually, after a hop-by-hop forwarding,
`the packet will reach the intended destination. Note that,
`as the relay selection is done a posteriori, GeRaF merely re-
`quires position information, thus it does not need topolog-
`ical knowledge nor routing tables.
`4.1.2. Connectivity-driven
`Span [26] is a connectivity-driven protocol that adap-
`tively elects ‘‘coordinators” of all nodes in the network.
`Coordinators stay awake continuously and perform mul-
`ti-hop routing, while the other nodes stay in sleeping mode
`and periodically check if it is needed to wake up and be-
`come a coordinator. To guarantee a sufficient number of
`coordinators Span uses the followingcoordinator eligibility
`rule: if two neighbors of a non-coordinator node cannot
`reach each other, either directly or via one or more coordi-
`nators, that node should become a coordinator. However, it
`may happen that several nodes discover the lack of a coor-
`dinator at the same time and, thus, they all decide to be-
`come a coordinator. To avoid such cases nodes that
`decide to become a coordinator defer their announcement
`by a randombackoff delay. Each node uses a function that
`generates a random time by taking into account both the
`number of neighbors that can be connected by a potential
`coordinator node, and its residual energy. The fundamental
`ideas are that (i). nodes with a higher expected lifetime
`should be more likely to volunteer to become a coordina-
`tor; and (ii). coordinators should be selected in such a
`way to minimize their number. Each coordinator periodi-
`cally checks if it can stop being a coordinator. In detail, a
`node should withdraw as a coordinator if every pair of its
`neighbors can communicate directly, or through some
`other coordinator. To avoid loss of connectivity, during
`the transient phase the old coordinator continues its ser-
`vice until the new one is available. The Span election algo-
`rithm requires to know neighbor and connectivity
`information to decide whether a node should become a
`coordinator or not. Such information is provided by the
`routing protocol, hence SPAN depends on it and may re-
`quire modification in the routing lookup process.
`Adaptive Self-Configuring sEnsor Networks Topologies
`(ASCENT [22]) is a connectivity-driven protocol that, un-
`like Span, does not depend on the routing protocol. In AS-
`CENT a node decides whether to join the network or
`continue to sleep based on information about connectivity
`and packet loss that aremeasured locallyby the node itself.
`The basic idea of ASCENT is that initially only some nodes
`are active, while all other ones arepassive, i.e., they listen
`to packets but do not transmit. If the number of active
`nodes is not large enough, the sink node may experience
`a high message loss from sources. The sink then starts
`sending help messages to solicit neighboring nodes that
`are in the passive state (passive neighbors) to join the net-
`work by changing their state from passive to active (active
`neighbors). Passive neighbors have their radio on and lis-
`ten to all packets transmitted by their active neighbors.
`However, they do not cooperate to forward data packets
`or exchange routing control information – they only
`collect information about the network status without
`interfering with other nodes. On the contrary, active
`neighbors forward data and routing (control) messages
`until they run out of energy. Act