. 61
( 87 .)



Figure 11.5. Relay region. For transmitter i and relay node r at unit distance (di,j = 1), the relay re-
gion Ri(r) is shown for several values of (k = 1) (left), and of k ( = 4) (right).

11.5.2 Minimum-Energy Routing
The minimum-energy routing problem is to minimize the total energy consumed in for-
warding a packet from source to destination. Minimum-energy routing can exploit expo-
nential path loss by forwarding traffic using a sequence of low power transmissions rather
than a single direct transmission, as in Figure 11.5.
For successful transmission, the signal-to-noise plus interference ratio (SNIR) at the
receiver must be greater than some threshold, which depends on the target bit error rate. In
a basic path-loss model, received signal strength decreases exponentially with distance.
The minimum transmit power required to transmit from node i to node j is

Pminij di,j 2 4

where exponent depends on the environment.
The measurement data presented earlier show that it is necessary to account for energy
consumed in both transmitting and receiving when evaluating the energy cost of a path.
The former depends on the transmit power used at each hop, whereas the latter is roughly
constant. If a relay node is added to a minimum-hop-count path, the energy saved though
reduced transmit power must compensate for the energy consumed by the overhead of the
extra transmit and receive operations. The cost of transmitting a packet over link (ij) is
modeled as

ei,j = d i,j + k

It is important to emphasize that in this context, the “distance” d, must be treated as no-
tional for observed gain. The variable k reflects the fixed overhead.5 Wireless propagation
is very complex to model, due to effects of terrain and other obstacles. In general, it is not
possible for a node to determine the transmit-power level required for nodes to communi-
cate based on their positions. At a given transmit-power level, a node may be able to suc-
cessfully transmit further in some directions (e.g., along an open corridor) than in others
(e.g., through wall), as shown in Figure 11.6.

Details of the MAC protocol can vary, for example, the receiver may transmit control traffic, but it is only im-
portant that all overhead factors are included. (For simplicity, a fixed packet length is assumed throughout.)




Figure 11.6. Here, ei,j / d i,j due to obstacles. Relay r2 is the best candidate, despite its distant posi-

The two examples of minimum-energy-routing techniques presented below are some-
what analogous to the proactive and reactive approaches to the ad hoc routing problem.
The first is topology-driven and finds routes for all nodes. Because the minimum-energy
route can change more frequently than a route requiring only connectivity, such solutions
are appropriate for static or slowly changing networks. The second, which is more in the
spirit of reactive routing protocols, assesses the energy efficiency of ongoing flows to im-
prove their energy efficiency, adapting to the effects of node mobility. Relay Regions. The minimum energy routing technique presented in [30,
19, 22] is based on the concept of a relay region, shown in Figure 11.5. For a given trans-
mitter i and relay node r, the relay region Ri(r) contains the set of receivers for which
transmitting via relay node r reduces the total energy consumption. By combining the
boundaries of the relay regions defined by taking each of its neighbors as a relay node, the
transmitting node determines its “enclosure” region.
Any node that is in the set defined by the union of the relay regions is outside the en-
closure: It can be more efficiently reached via some relay node. Nodes inside the enclo-
sure are not in the relay region of any other node: Only these nodes are one-hop neighbors
of the transmitting node in the minimum-energy topology. The neighbor sets defined by
the enclosure of each transmitter define the minimum energy topology. Minimum-energy
routes in this topology can be obtained using, for example, the distributed Bellman“Ford
algorithm to find minimum-cost routes. They can also be approximated by running a rout-
ing protocol such as AODV over the minimum-energy topology.
Implementing this technique is apparently straightforward. Each node broadcasts
neighbor discovery messages with increasing transmit-power levels, accumulating ACKs
containing the positions of its neighbors. As new nodes are discovered, nodes that are not
in the relay region of any other node are added to the neighbor set and nodes that are
found to be in the relay region of another node are eliminated from it. This strategy is
found to significantly reduce energy consumption in simulation environments providing
uniform, deterministic transmit-power calculations. In practice, transmit power cannot be
easily calculated from position information. To select minimum-energy routes, nodes
must evaluate relay nodes based on the actual transmit-power levels required on the direct
path and on both hops of the relay path. These issues emphasize the importance of incor-
porating realistic propagation behavior into simulation environments to study its impact

on minimum-energy routing and to evaluate the effectiveness of various methods of esti-
mating transmit-power levels. Adaptive Minimum-Energy Routing. The power-aware routing opti-
mization (PARO) protocol [11] represents a different approach to minimum-energy rout-
ing. Rather than exchanging connectivity information to determine a minimum-energy
topology, nodes observe ongoing transmissions and nominate themselves as relay nodes
for any pair of endpoints for which they provide more energy-efficient connectivity. This
means that PARO uses observed gain rather than position information to evaluate routes.
The protocol™s adaptive operation also makes it natural to support nonstatic networks and
reactive routing protocols.
In PARO, nodes eavesdrop on ongoing transmissions, using the advertised transmit-
power level and observed signal strength to estimate the minimum transmit power re-
quired to communicate with each node that it overhears. If a node hears traffic from both
endpoints of a link, it can compare the advertised transmit power being used to send the
packet directly with its estimate of total transmit power required to send the packet using
itself as a relay. If the energy savings is sufficiently high, the node sends a redirect mes-
sage to each of the endpoints, updating their routing tables to use itself as a relay. To pre-
vent several intermediate nodes from issuing redirect messages simultaneously, the mes-
sage is sent using an adaptive backoff timeout that is inversely proportional to the
optimization value of using the node as a redirector. This greedy selection of the redirec-
tor at each hop may not lead to an optimal route. In practice, however, most of the energy
savings is gained in the first iteration of the protocol, especially if a realistic view is taken
of the fixed receive costs.
Simulation studies of PARO reduces per-packet energy consumption by between one-
and two-thirds compared to fixed power transmissions. The delivery ratio also remains
good, except in the case where high mobility (i.e., short-lived links) is combined with low
data rates (i.e., few opportunities to redirect). PARO also performed well compared to a
simple link-state routing algorithm selecting minimum energy paths, due to the high rout-
ing protocol overhead. Experiments performed using nodes equipped with the Aironet 4800
IEEE 802.11 card were inconclusive. The authors suggest this may be due to the transmit-
power granularity of the Aironet card, which only supports a few transmit-power levels.
A potential problem is that PARO requires that nodes eavesdrop to find opportunities
for route optimization. Power-save protocols, by contrast, attempt to maximize the amount
of time that nodes spend in the sleep state. In fully evaluating these protocols, it is impor-
tant to consider the interaction between these aspects.

11.5.3 Problem of Multiple Transmit Powers
The presence of multiple transmit-power levels in a network poses a nontrivial problem,
particularly in the CSMA case. Consider the example in Figure 11.7. If node a is transmit-
ting a packet to nearby node b using low transmit power, the ongoing transmission may
not be detected at node A. When node A begins transmitting a packet to more distant node
B, it interferes with the transmission from a to b.
This problem can be mitigated by transmitting control traffic at the maximum power
permitted in the network, as is suggested in [11] for the PARO protocol. Unfortunately,
this reduces both the energy savings and the opportunity for increased network capacity
from improved spatial reuse. Some alternative approaches are discussed below.

a b A B

Figure 11.7. Problem of multiple transmit ranges (assuming carrier sense is equivalent to receive).

11.5.4 Adaptive Power Control
One approach to this problem is to use an adaptive power-control loop, similar to that
found in CDMA systems. Adaptive power control for the IEEE 802.11 MAC is proposed
in [1]. Each node maintains for each destination a weighted history of the received signal
strength for successful transmissions and the threshold at which packet loss occurs. If the
received signal strength indication is larger than this threshold, the transmission power is
reduced (subject to the constraints of the control loop). If the MAC layer times out waiting
for a response, it records this threshold signal strength and retransmits using a higher
transmit power. (In the example above, nodes a and b, experiencing loss due to interfer-
ence, would increase their transmit power until their control traffic properly suppressed
interfering transmissions from node A.)
Simulation results show that adaptive power control is only moderately effective in a
group-mobility environment. Energy consumed in transmitting and receiving traffic is re-
duced 10“20% and throughput is increased by about 15%, compared to an unmodified
IEEE 802.11 MAC. Lesser savings are observed in a randomized environment. This is not
unexpected: In group-mobility environments, power-control techniques can take advan-
tage of the fact that most traffic is exchanged locally.
Because this technique cannot be used for broadcast transmissions, broadcast packets
must be transmitted at full power. This means that the route discovery process (DSR [17]
in these experiments), continues to discover routes with the smallest hop count, rather
than minimum-energy routes. But because no additional hops are introduced by adaptive
power control, the only source of overhead is the duplicate transmissions used for power-
level adaptation.

11.5.5 Network Optimal Transmit Power
Another approach is to avoid the problems associated with per-node transmit powers alto-
gether by determining an optimal common transmit-power level for the network; specifi-
cally the lowest transmit power level that maintains network connectivity. In [13] and [26],
it is demonstrated analytically that a per-node throughput of O(1/ n log n) is obtained us-
ing a common network-optimal transmit-power level, as compared with an upper bound
of O(1/ n) with per-node optimal levels.
It is shown in [32] that the critical transmission power for a network is the transmission
power associated with the highest-cost link in the minimum spanning tree of the network.

Simulation shows that, independent of the mobility model, the variability of this critical
transmit power due to mobility is very high.
In practice, network interfaces usually provide a small number of fixed transmit-power
levels, making precise determination of the critical transmit power unnecessary. The
Common Power (COMPOW) Protocol [26], makes use of this fact. Each COMPOW node
runs multiple instances of a proactive ad hoc routing protocol (DSDV [27]), one at each of
the available transmit-power levels. The connectivity information is used to maintain the
corresponding set of parallel routing tables. The lowest-power routing table that still in-
cludes all of the destinations that are included in the highest-power routing table is used as
the default routing table and defines the common transmit power. An implementation of
COMPOW is reported in [26], but no performance results have been published. In nonsta-
tic networks, the overhead of multiple instances of the routing protocol may be large, as
reported in [3].


The discussion of power-save protocols earlier in this chapter emphasized not only the im-
portance of reducing idle-mode energy consumption, but also the importance of increas-
ing the network lifetime by balancing energy consumption across the network. This sec-
tion explores the problem of maximum-lifetime routing. The first part of this section
discusses a number of route metrics used in selecting energy-aware routes. The second
part briefly discusses some theoretical results before turning to issues involved in incor-
porating these metrics in practical routing protocols. The final part of this section pro-
vides an overview of some interesting alternative approaches, including one based on the
electrochemical behavior of the battery.

11.6.1 Route-Selection Metrics
There are three metrics that are commonly included in energy-aware routing mechanisms.
These are minimum-energy routing, max“min routing, and minimum-cost routing.
Minimum-energy routing, discussed in the previous section, minimizes the total ener-
gy consumed as a packet is forwarded on a route. (In [34], it is suggested that a minimum-
energy route metric can also take into account the energy cost of link contention, but it is
not clear how this could be done in practice.) Minimum-energy routing does not maxi-
mize network lifetime. Because the nodes™ residual energy (remaining battery capacity) is
not taken into account, nodes on the minimum-energy routes will suffer early failure due
to their heavy forwarding load.
The max“min metric explicitly avoids this problem by selecting the route that maxi-
mizes the minimum residual energy of any node on the route. Routes selected using
max“min metrics may be longer or have greater total energy consumption than the mini-
mum-energy route. This increase in per-packet energy consumption tends to reduce the
network lifetime, though max“min generally performs much better than minimum-energy

A (somewhat pathological) topology in which max“min performs arbitrarily badly compared to minimum ener-
gy is shown in [23].

Minimum-cost routing minimizes the total cost of forwarding the packet at each node,
selecting the route that minimizes the sum of the link costs cij. The shape of the cost func-
tion controls the extent to which the presence of a high-cost (i.e., low residual energy)
node on a route deflects traffic from that route.
In general, the cost function is a monotonically increasing function, reflecting a node™s
increasing “reluctance” to forward traffic as its residual energy decreases. A simple exam-
ple of a cost function for link (ij) is the reciprocal of the residual energy E at node i, cij =
1/Ei, or the normalized residual energy cij = Einit/Ei. In [34], the battery voltage zi is used
to define a cost function 1/zi “ zcrit, which grows rapidly as the voltage nears the critical
level. Alternatively, a residual energy-cost function can be based on a known discharge
curve for a particular battery.
A capacity-cost function incorporates both the communication-energy cost eij for link
(ij) and the residual energy at a node. One advantage of such a function is its ability to bal-


. 61
( 87 .)