. 60
( 87 .)


each node in a grid square is within transmission range of every node in each adjacent

grid square, implying a grid size of R/ 5, where R is the node transmission range. This
grid structure ensures that all the nodes in a grid square are equivalent with respect to pro-
viding connectivity to any adjacent grid square. One nonsleeping node in each grid square
is sufficient to maintain the connectivity of the original network.
Because connectivity is defined by the grid, selecting the active node for each grid
square does not require explicit exchange of connectivity information. Each node transi-
tions independently among three states: sleep, discovery, and active. Nodes periodically
wake up from the sleep state and transition to the discovery state. In the discovery state, a
node listens for other nodes™ announcements and can announce its own grid position ID
and residual energy status. If the node hears no “higher ranking” announcement, it transi-
tions to the active state, otherwise it transitions back to the sleep state. A node in the active
state is responsible for maintaining network connectivity on behalf of its grid square, peri-
odically announcing its state. After spending some time in the active state, a node transi-
tions back to the discovery state, allowing the active role to be rotated among the nodes in
the grid square.
The ranking function and state timeouts can be used to tune GAF, trading energy con-
sumption against the risk that there will be no active node in a grid square. The ranking
function is used to balance energy consumption among nodes, by preferring nodes with
the longest “expected node active time,” which is based on the node™s residual energy and
the length of time it is projected to remain in its current grid square. The sleep intervals
are calculated such that nodes are likely to transition from the sleep state to the discovery
state in time to replace an active node, if needed.
Currently, the ad hoc routing protocol operates independently of GAF. This makes it
possible to isolate the impact of GAF power saving on routing-protocol performance. It
imposes some burden on GAF, because when the active node in a grid square changes, the
routing protocol interprets this as a route failure from which it must recover. Alternatively,
GAF might be more closely coupled with an ad hoc routing protocol by using preemptive
route recovery or grid-based forwarding.
The effect of GAF on the energy consumption and performance of AODV routing pro-
tocol has been studied in ns-2 packet-level simulation. In general, AODV and AODV/GAF
have similar data delivery ratios and transfer delays, whereas the mean energy consump-
tion per node is reduced by 40“50%. As discussed earlier, increasing node density pro-
vides proportional increases in network lifetime (defined as 80% data delivery ratio).
Similar results were obtained using DSR [17] as the routing protocol.
One must be cautious, however, when dealing with geographic protocols, especially
when position information is not used only for directional forwarding. In general, it is not
possible to rely on a strong deterministic relationship between position and connectivity.
Buildings, foliage, and terrain all have a dramatic effect on path loss, even between nodes
which are geographically close together. In a real network, there may exist grids in which
no single node (and possibly even no combination of nodes) has connectivity with every
node in an adjacent grid.
The appropriate selection of the grid size helps to ensure the expected connectivity; an
overly conservative choice reduces energy savings. Within a grid, the announcement
mechanism can adjust somewhat to actual connectivity. If connectivity is poor, some
nodes in the grid square may not receive an announcement. More than one node may
choose to take on the role of an active node in the grid square, providing increased robust-
ness, as well as increased energy consumption. Moreover, even if there are grids that are
disconnected from one or more adjacent grids, the routing protocol may be able to route

around these “holes” and maintain connectivity between source and destination. This is
clearly an issue that emphasizes the importance of having good terrain and propagation
models for use in evaluating such protocols.

11.4.4 Asynchronous Power-Save Protocols
Asynchronous power-save protocols allow nodes to maintain independent, possibly even
dissimilar, schedules. The scheduling rules are defined such that neighboring nodes™
awake intervals eventually overlap and retransmission rules are defined such that neigh-
bors can eventually exchange traffic. Because initiating communication at each hop can
take some time, this approach has the disadvantage of introducing latency, with broadcast
traffic and route latency being particularly affected. BECA/AFECA. The BECA/AFECA protocol [44, 43], a predecessor of
GAF, does not rely on position information. Like GAF, it is intended for use in sensor net-
works. It is designed to be integrated with an on-demand ad hoc routing protocol, which
discovers routes by means of broadcast flooding. BECA/AFECA operates asynchronous-
ly, maintaining network connectivity through strong timing dependencies with the associ-
ated routing protocol.
In the basic energy conservation algorithm (BECA), each node independently transi-
tions between the sleep state and one of two logical idle states: listening and active. In the
absence of traffic, a node alternates between the sleep state and the listening state. Once a
node transmits or receives traffic, it transitions to the active state. Nodes in the active state
return to the sleep state only after they have been not received traffic for some time.
Because nodes make these transitions independently, there is no guarantee that there is
a live path to the destination, or even that the destination itself is awake at the time a route
request (RREQ) is generated. In order to ensure that a RREQ reaches its destination, there
must be a careful relationship among the various timing parameters of the power-save pro-
tocol and the route discovery protocol.
The fundamental unit is the listening interval, which is matched to the RREQ retry in-
terval for the routing protocol. If the sleep interval is some integral multiple k of the lis-
tening/retry interval, then it will take at most k + 1 broadcasts for every neighbor to re-
ceive the RREQ. Once a node receives the RREQ, it transitions to the active state. As long
as the timeout for the active interval is greater than the RREQ retry interval, the interme-
diate nodes will remain awake until the route discovery process has completed, taking at
most D(k + 1) route discoveries, where D is the path length.
Once the route has been established, only the nodes that forward traffic will remain ac-
tive. The other nodes will not forward traffic, and once their active intervals have timed
out, they will return to the low-energy-consumption sleep“listen cycle. Once traffic along
the route ceases, the nodes on the route also time out and return to sleep“listen cycle.
This probabilistic approach requires that broadcast flooding of the RREQ be repeated
several times, with increasing redundancy each time. As long as route discovery and re-
pair are relatively rare operations, this is a minor drawback. If not, or if the network sup-
ports other services that also rely on broadcast, then this overhead becomes more of an is-
sue. Moreover, because “logical broadcast” occurs over a relatively long interval, there is
a risk of synchronization problems for higher-layer protocols and applications.
The adaptive fidelity energy conservation algorithm (AFECA) is an extension of
BECA in which nodes adapt their sleep interval depending on the estimated network den-

sity. The more nodes, the smaller the proportion that must be awake to achieve the con-
nectivity needed to forward traffic.
The performance of BECA/AFECA has been studied using ns-2 simulation packet-
level simulation, with AODV as the routing protocol. Overall energy saving was on the or-
der of 35%“45%, across a range of traffic loads, with a minimum sleep interval of 10 sec-
onds. There was a significant increase in route latency, which averaged well under one
second for unmodified AODV but averaged between six and ten seconds using AFECA.
AFECA also exhibited slightly higher loss rates than unmodified AODV .
AFECA makes no attempt to rotate forwarding functionality among nodes or to other-
wise balance energy consumption across the network. In fact, because nodes that have re-
cently forwarded traffic remain awake, they are more likely to participate early in the
route discovery process and may therefore be more likely to be designated as forwarding
node for additional routes. Depending on traffic patterns, this feedback can lead to un-
equal distribution of routing load and poorly distributed energy consumption. This is re-
flected in the simulation results. The network half-life increases by as much as 50%, but
there is almost no increase in time to first node failure.

11.4.5 MAC Layer Power-Save Protocols
CSMA MAC layer power-save protocols use information derived from the media-access
control process to find intervals during which the network interface does not need to be
awake. While a packet is being transmitted, nearby nodes whose transmissions might in-
terfere with the ongoing transmission must remain silent. These nodes can sleep, with lit-
tle or no impact on throughput. Figure 11.3 shows an example based on the IEEE 802.11
MAC. PAMAS. The PAMAS [33] protocol is based on this principle. PAMAS uses
an RTS/CTS-style mechanism with a separate control signaling channel. A node that is
waiting to initiate a transmission or is in the process of receiving a transmission causes
other nodes to defer their transmissions by generating a busy tone on the control channel.
A PAMAS node turns itself off if a neighbor is transmitting and it has no packets to
transmit or if it has a packet to transmit, but a neighbor is receiving. The node can deter-

a c

s d

Figure 11.3. When s transmits to d, a hears the RTS and b hears the CTS, so a and b cannot trans-
mit. (If c is outside the carrier sensing range of s, c can broadcast, with b as a potential recipient.
Given the increased risk of collision at b and unreliable nature of broadcast, the potential loss is as-
sumed to be small.)

mine the duration of the current transmission from information in the control traffic and
sleep until the end of the transmission. When the node wakes up, however, it does not have
information about the state of the channel. For example, another neighbor may have be-
gun a transmission, in which case the node should go back to sleep. In order to determine
the duration of the current transmission, the node transmits a sequence of probe messages
and awaits a response on the control channel. Similarly, if the node wishes to transmit, but
another neighbor is now receiving, the node™s RTS will evoke a busy tone response indi-
cating the duration of the ongoing transmission. PAMAS is inherently conservative; a
node sleeps only if it determines that it is possible to do so without affecting network ca-
Simulation results suggest that PAMAS provides 10“70% reduction in the amount of
energy a node spends receiving, assuming a 2:1 send-to-receive power consumption ratio.
PAMAS is most effective in networks with high density and traffic load. It has no effect at
all on the energy consumption of a quiescent network.
This technique is less applicable to network interfaces with high data transmission
rates. If the time required for data transmission is short, then the time and energy required
for the network interface to transition to the sleep state and back to the idle state outweigh
the possible savings. Examples of low-power, low-data-rate transmitters are most often
found in sensor network scenarios, where transmission rates of a few Kbps are not un-


The next class of techniques considered in this chapter allow nodes to modify their trans-
mit power to increase network capacity and reduce energy consumption. Figure 11.4
shows an example of how the network topology is defined by the nodes™ transmission ra-
dius. Low-power transmissions reduce contention and increase network capacity, while at
the same time consuming less energy. This suggests that a route with a larger number of
low-power hops may be more energy-efficient than one with fewer high-power hops.
However, a route that contains more hops may experience a higher probability of network
route failure or link-layer packet retransmission. These are further examples of the impor-
tance of cross-layer interaction in energy-efficient communication.
When evaluating the effectiveness of power-control techniques, it is important to con-
sider whether the energy consumption model is realistic, particularly in its treatment of re-
ceiving. The extent to which the protocol operation depends the assumptions and accuracy
of a particular radio propagation model is also extremely important and often difficult to
evaluate in simulation.
The first two subsections below discuss the topology control problem briefly and the
minimum energy routing problem in detail. The third subsection discusses problems that
occur when multiple transmit powers are used in a network and describes some proposed

11.5.1 Topology Control
The topology-control problem is to assign per-node transmit powers that minimize the
maximum transmit power used in the network, while still maintaining network connectiv-
ity. These methods are generally focused on increasing throughput by reducing interfer-

c b c
e e
a a


b b c

a a

Figure 11.4. Transmit range determines the topology and capacity of this five-node network. (For

simplicity, transmission and carrier sense range are assumed equal.) With ei,j di,j , a relay, e.g. a
b c may consume less energy than a direct route, for example, a c.

ence, with the associated reduction in energy consumption as a beneficial side effect. For
that reason, this chapter will not emphasize the topic. Some simple topology control
strategies are briefly discussed below.
In [29], link state topology information is used maintain a connected (or biconnect-
ed) topology. If a route update indicates that a link failure has occurred such that the
network is no longer connected, the appropriate nodes increase their transmit power (us-
ing slotted backoff) until it is connected. This technique depends heavily on routing pro-
tocol performance, because changes in network connectivity can trigger further routing
Alternatively, a variety of heuristics can be used. In [29], each node increases its trans-
mit power until its node degree is sufficiently large, based on estimated node density, that
the network is likely to be connected. In [39], each node modifies its transmit power until
it has discovered at least one neighbor “in every direction,” specifically in each cone of
angle 2 /3. Assuming an unobstructed and homogeneous environment, these neigh-
bors™ combined wireless coverage provides connectivity such that the node is guaranteed
to be connected to the network.
Another variant of this problem is presented in [40]. Given a broadcast source node,
the minimum-energy broadcast problem is to select a set of rebroadcasters and transmit
powers such that the message is distributed to all nodes with minimum total energy cost.
Unlike the topology-control problem, which has an optimal centralized solution, mini-
mum-energy broadcast is believed to be NP-complete.



. 60
( 87 .)