<<

. 62
( 87 .)



>>

ance the objectives of maximizing energy reserves and minimizing forwarding cost. Ex-
amples include cij = eij/Ei and its normalized counterpart eij(Einit/Ei), which reflect the
amount of traffic node i can forward if the route includes link (ij) with energy cost eij. Ex-
amples of capacity-cost functions that estimate the total cost of a route using only position
and local cost information are found in [36].
These routing metrics have been widely studied in simulation [4, 5, 38]. With the ex-
ception of minimum energy and pure residual cost metrics, all of them appear to perform
well. The results are roughly summarized in Table 11.2 and discussed in a little more de-
tail below. It is not clear whether they would continue to hold true in more realistic simu-
lation environments, which could produce networks with vulnerable routing bottlenecks
and greater variability in route length and energy cost.
Simulations [4, 5] of a twenty node static network systematically compared total cost
and max“min metrics for a variety of capacity and residual energy cost functions. In gen-
eral, total normalized capacity was the most effective metric, especially if the residual en-
ergy is somewhat overweighted. Max“min metrics for both residual energy and capacity
performed nearly as well. All these metrics obtained 84“96% of the optimum lifetime in
the average case and 66“90% in the worst case. On average, minimum energy routing and
total residual energy metrics performed poorly, achieving 30“50% of the optimum life-
time.
A capacity-based cost function is one way of jointly optimizing communication energy
and residual energy. An alternative is to explicitly balance the minimum energy and
max“min approaches, as in two protocols discussed below.
A conditional strategy, CMMBCR, is proposed in [38]. For each destination, if there is
at least one route such that the residual energy of each node is greater than some thresh-


Table 11.2. Effectiveness of Various Route Metrics (Primarily from [5, 4]). Performance
Differences Among the Better Metrics are Small
Normal residual Capacity
Transmit Residual Normal capacity
Ei eij
cost eij energy Ei energy eij (Einit/Ei)
Einit Ei
Max“min ” good good good good
Total cost very bad bad bad good very good
(minimum energy)
322 ENERGY-EFFICIENT COMMUNICATION IN AD HOC WIRELESS NETWORKS


old, the minimum energy route is chosen. If there is no such route, the route that maxi-
mizes the minimum residual energy is selected. Simulation results for a 30-node mobile
network with fixed transmit power (i.e., the minimum-energy route is shortest path)
shows how the choice of threshold value determines the expiration sequence. A max“min
metric (i.e., a high threshold) gives the longest time to first node failure, whereas mini-
mum-energy routing (i.e., a low threshold) gives the longest half-life. An intermediate
value gives balanced behavior. This is precisely as expected: Because the max“min
schemes use longer routes to avoid early node failure, the overall energy consumption in-
creases and the average node lifetime is decreased. Overall, the differences among the
metrics were only around 10-20%, as in the previous results. (Minimum-energy routing
performed relatively better, perhaps because it is equivalent to shortest-path routing in this
environment.)
An adaptive scheme, max-minzPmin, is presented in [23]. In this case, a route that max-
imizes the minimum residual energy on the route is selected, as long as it consumes no
more than zPmin energy, where Pmin is the energy consumed by the minimum-energy
route. Periodically, the estimated lifetime of each node is calculated based on its energy
reserves and current rate of change. If the minimum node lifetime of the network has in-
creased, z is increased, preferring max“min routes; otherwise z is decreased. Simulation
results for static networks of up to 40 nodes indicate that the adaptive technique consis-
tently achieves over 80% of the optimal lifetime.

11.6.2 Algorithms and Protocols
Maximum-lifetime routing is a difficult problem, even formulated in an abstract context.
Given a set of known, constant rate flows and a fixed network topology, maximum-life-
time routing can be specified as a linear programming problem [4]; specifically, maximiz-
ing the minimum node lifetime, subject to multicommodity flow conservation. This life-
time is generally used as the optimum against which various approaches are compared.
Given fixed per-node transmit power, maximum-lifetime routing is equivalent to maxi-
mum flow with node capacities. In [23], however, it is shown that for message sequences
that are not known in advance, maximum-lifetime routing is an NP-hard problem. More-
over, there is no online algorithm having a constant competitive ratio with respect to an
optimal offline algorithm.
The simulation results summarized in Table 11.2 generally indicate that there is rela-
tively little difference in performance among the various metrics. But by themselves, met-
rics for selecting the optimal route do not provide maximum-lifetime routing. There must
be some means by which candidate paths are identified, metrics computed, and flow di-
rected to the appropriate path.
Because ad hoc routing protocols must support decentralized operation, maintaining
up-to-date residual-energy information at all nodes for table-driven or distance-vector
route calculations may not be a viable approach. In practice, it may also be difficult to iso-
late maximum-lifetime metrics from other aspects of ad hoc routing. Metrics such as
route stability and QoS considerations for delay-sensitive flows are also important. Some
approaches to these issues are discussed below.
In the simplest case, evaluation of route metrics can be incorporated into the route dis-
covery phase of an on-demand routing protocol. Total or max“min values for the metric
are accumulated as the route request traverses the network, and the optimal route is select-
ed by the destination. However, route discovery techniques are usually optimized to mini-
323
11.6 MAXIMUM-LIFETIME ROUTINGS


mize the bandwidth-intensive broadcast flooding operation and therefore only present a
small subset of possible routes to the destination. Routes for long-lived flows may need to
be periodically recomputed in order to respond to changes in residual capacity.
A flow-augmentation algorithm is presented in [4]. At each source, the shortest-cost
path is recomputed for each unit of flow, , in order to respond to changes in battery ca-
pacity, with smaller giving best performance. Selecting the shortest-cost route for the
chosen metric can, in principle, be done using some variant of the distributed
Bellman“Ford algorithm. This may result in significant overhead in a dynamic, asynchro-
nous network, however.
For networks with a known set of constant rate flows, flow redirection [4] is based on
the observation that if network lifetime is maximized, then each path has the same life-
time. Otherwise, some flow could be redirected from the shortest lifetime path onto some
other path. The algorithm uses feasible descent to determine the shortest lifetime path and
redirect flow from that path to another one. Like max“min, this approach can exhibit arbi-
trarily poor performance, becoming trapped in a local minimum. In simulation, its perfor-
mance lags somewhat behind the other approaches, especially in worst-case performance.
A hierarchical, zone-based variant of max“minzPmin is described in [23]. The nodes in
each geographic zone estimate the capacity of the region, assuming max“min$ z
P_{min}$ routing for traffic through the zone. This substantially reduces the overhead of
distributing each node™s energy status though the network. Moreover, the energy distribu-
tion within a zone changes more slowly than that of individual nodes. Traffic is routed us-
ing geographic forwarding, preferring high capacity zones rather than high-capacity
nodes. The performance is comparable to that of max-minzPmin, while supporting much
larger networks.
In [36], route metrics are computed at each forwarding node based on local residual
energy and link-cost information and extrapolated costs based on the distance from the
forwarding node to the destination. This eliminates the need to distribute residual-energy
information.

11.6.3 Alternative Approaches
Two alternative approaches to energy-aware routing integrate other important aspects of
the system into the cost metrics used for route selection.

11.6.3.1 Battery-Efficient Routing. A routing scheme based on battery efficiency
is presented in [7]. Batteries exhibit two electrochemical behaviors that can be exploited
by a routing protocol. The first is the recovery effect, such that a bursty discharge pattern
is more efficient than a constant-current discharge. The second is the rate-capacity effect,
such that drawing even a small percentage of current impulses that exceed the rated cur-
rent capacity of the battery significantly degrades battery performance. Battery-energy-
efficient (BEE) routing uses a cost function that includes both a conventional max“min
component and a penalty factor proportional to amount by which the transmit energy for a
link exceeds the node mean. Simulation experiments that model battery discharge suggest
that the time to network failure with BEE can be almost twice that obtained with mini-
mum-energy routing.

11.6.3.2 Reliable Energy-Aware Routes. In addition to realistic energy consump-
tion models, it is also important to use realistic models of channel error. The routing met-
324 ENERGY-EFFICIENT COMMUNICATION IN AD HOC WIRELESS NETWORKS


rics presented in [2, 25] reflect the potential cost of retransmissions required to recover
from link errors and achieve reliable end-to-end delivery. For example, minimum-energy
routes can increase the probability of transmission error along the end-to-end path, due to
the increased number of hops.
To find minimum-energy reliable routes, the cost function must reflect the expected
cost of retransmissions at each link. Assuming the transmit power is fixed and bit-error
failures on link (ij) are independent, the probability of retransmission is given as pij. If
hop-by-hop retransmission is supported, the expected cost cij = (eij/1 “ pij). If hop-by-hop
retransmission is not supported, the cost cij is approximated by ei, j/(1 “ pi, j)L, where L is
the average path length in the network. In the case of fixed transmit power ei, the received
signal strength and the error probability pij, vary with link distance. Alternatively, a vari-
able transmit power eij can be chosen such that the received signal strength, and thus the
error probability p, are fixed.
The simulation study presented in [2] uses this retransmission-aware cost function to
find minimum-energy routes. For hop-by-hop retransmissions and fixed transmit power,
and for end-to-end retransmission and variable transmit power, retransmission-aware rout-
ing saves significant energy compared to minimum-energy or shortest-hop routing. In all
cases, the TCP throughput also increased significantly.
From here, the development is analogous to that in the section above. In addition to
computing minimum-energy routes, the link energy function can also be combined with
residual energy Ei to define a capacity-cost function

ei, j
ci,j =
Ei(1 “ pi, j)L

The simulation study presented in [25] uses this cost function to define max“min and
conditional metrics MRPC and CMRPC, analogous to MMBCR and CMMBCR above.
For a maximum error rate of 0.25, reliability-aware routing performed significantly better
than its residual-energy counterpart, especially in dense networks. The conditional strate-
gy shows little gain because, unlike MMBCR, the MRPC max“min metric already in-
cludes a minimum-energy routing element because the cost function includes the link en-
ergy.


11.7 CONCLUSION

This chapter has examined three current areas of research in energy-efficient communica-
tion in ad hoc networks. Power-save protocols attack the problem of high idle-state energy
consumption by maximizing the amount of time nodes spend in the sleep state. Power
control increases network capacity and reduces energy consumption by allowing nodes to
determine the minimum transmit-power level required to maintain network connectivity
and forward traffic with least energy cost. Maximum-lifetime routing selects paths that
maximize network lifetime by balancing energy consumption across the nodes of the net-
work.
In assessing the work that appears in this chapter, there are two themes that appear re-
peatedly. The first is the extent to which energy-efficient communication is a multifaceted
problem. Attention to only one aspect of the problem, or to optimizing a single element of
the protocol stack can lead to suboptimal performance with respect to the goal of maxi-
325
REFERENCES


mizing node and battery lifetime. The limitations of minimum-energy routing and the im-
portance of considering end-to-end reliability are examples of this. Moreover, it is not
clear how the various approaches outlined here might interact if they were applied in the
same network. For example, power-save protocols are most effective in a dense network,
in which a small proportion of nodes remain awake to forward traffic. In minimum-ener-
gy topologies, on the other hand, it is precisely the network density that is reduced. Inter-
actions with system- and application-level energy management techniques are also largely
an open question [21].
The second theme is the central role that energy consumption and wireless propagation
models play in the design and evaluation of energy-efficient systems. Direct measure-
ments of wireless systems have been shown to provide energy consumption models that
are useful in designing and evaluating energy management techniques. It is also shown
that, due to the complex dependence of wireless propagation on terrain and other features,
protocols must not rely on a predictive relationship between distance, transmit power, and
connectivity.
Almost all of the results presented here are based on simulation, rather than direct ex-
periment. This means that the results depend significantly on the wireless propagation and
energy consumption models incorporated into the simulations. Often, the same models
are used in both the design and evaluation of a protocol, which can be a source of confu-
sion in interpreting results. This problem highlights the importance of developing simula-
tion techniques (and even testbed environments [24]) that support complex and realistic
analysis of techniques currently being developed for energy-efficient communication in
wireless ad hoc networks.


REFERENCES

1. S. Agarwal, S. V. Krishnamurthy, R. H. Katz, and S. K. Dao. “Distributed power control in ad
hoc wireless networks,” in Personal and Indoor Mobile Radio Communication (PIMRC), 2001.
2. Suman Banerjee and Archan Misra. “Minimum energy paths for reliable communication in
multi-hop wireless networks,” in Proceedings of Workshop on Mobile and Ad Hoc Networking
and Computing (MobiHoc™02), June 2002.
3. Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun Hu, and Jorjeta Jetcheva. “A perfor-
mance comparison of multi-hop wireless ad hoc network routing protocols,” in Proceedings of
4th Annual International Conference on Mobile Computing and Networking (MobiCom™98),
1998.
4. Jae-Hwan Chang and Leandros Tassiulas. “Energy conserving routing in wireless ad-hoc net-
works,” in Proceedings of IEEE Infocom, vol. 1, pp. 22“31, March 2000.
5. Jae-Hwan Chang and Leandros Tassiulas. “Maximum lifetime routing in wireless sensor net-
works,” in Proceedings of Advanced Telecommunications and Information Distribution Re-
search Program (ATIRP™2000), March 2000.
6. Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris. Span: “An energy-ef_cient
coordination algorithm for topology maintenance in ad hoc wireless networks. ACM Wireless
Networks Journal, 8(5), 481“494, September 2002.
7. Carla-Fabiana Chiasserini and Ramesh R. Rao. “Routing protocols to maximize battery effi-
ciency,” in Proceedings of IEEE Milcom, October 2000.
8. Jean-Pierre Ebert, Brian Burns, and Adam Wolisz. “A trace-based approach for determining the
energy consumption of a WLAN network interface,” in Proceedings of European Wireless, pp.
230“236, February 2002.
326 ENERGY-EFFICIENT COMMUNICATION IN AD HOC WIRELESS NETWORKS


9. Laura Marie Feeney. “An energy-consumption model for performance analysis of routing pro-
tocols for mobile ad hoc networks.” Journal of Mobile Networks and Applications (MONET),
6(3), 239“250, June 2001.
10. Laura Marie Feeney and Martin Nilsson. “Investigating the energy consumption of a wireless
network interface in an ad hoc networking environment,” in Proceedings of IEEE Infocom,
April 2001.
11. Javier Gomez, Andrew T. Campbell, Mahmoud Naghshineh, and Chatschik Bisdikian. “Con-
serving transmission power in wireless ad hoc networks,” in Proceedings of IEEE Conference
on Network Protocols (ICNP™01), November 2001.
12. Bluetooth Special Interest Group. Specification of the Bluetooth system. http://www.blue-
tooth.org.
13. P. Gupta and P. R. Kumar. “The capacity of wireless networks.” IEEE Transactions on Informa-
tion Theory, 46(2), 388“404, March 2000.
14. Erik Guttman. “Autocon_guration for IP networking: Enabling local communication.” IEEE In-
ternet Computing, 5(3), 81“86, May 2001.
15. Z. J. Haas and M. R. Pearlman. “Providing ad-hoc connectivity with the reconfigurable wireless
networks,” in Ad Hoc Networking, Charles Perkins (Ed.), Addison-Wesley, 2000.
16. IEEE Computer Society LAN MAN Standards Committee. IEEE 802.11 Standard: Wireless
LAN Medium Access Control and Physical Layer Specifications, August 1999.
17. David B. Johnson, David A. Maltz, and Josh Broch. “DSR: The dynamic source routing proto-
col for multihop wireless ad hoc networks,” in Ad Hoc Networking, Charles Perkins (Ed.), Ad-
dison-Wesley, 2000.
18. Oliver Kasten and Marc Langheinrich. “First experiences with bluetooth in the smart-its dis-
tributed sensor network,” in Proceedings of 10th International Conference on Parallel Architec-
tures and Compilation Techniques (PACT™01) Workshop on Ubiquitous Computing and Commu-

<<

. 62
( 87 .)



>>