- 1. Introduction
- 2. How to Define Energy Efficiency
- 3. Energy Efficient Routing Algorithms
- 4. Unified Frameworks for Energy Efficiency Optimization
- 5. Latest Developments
- 6. A Brief Summary on Industry Standards
- Summary
- References

Since the primitive data network came into the history, routing has been one important issue for a long time. Routing algorithms or protocols, such as the well known Shortest Path Routing, have been regarded as the network layer protocols that lead packets through routers, gateways, and switches to the desired destination.

Typically, Routing in a network depends on complicated functionality of network devices, such as switches, to exchange information and provide certain services. The functions can either be independent on individual devices or be in a cooperative fashion, which leads to a rather high complexity. For example, network routing needs the coordination among all the nodes in the network, rather than just a contrary, it depends on the physical, data link and transport layer protocols. Furthermore, the network is highly dynamic, not static. There could be link or node failures, or the network can be congested somewhere, so the routing protocol should be able to modify the routes, redirect the traffic and maintain the databases with the latest information.

However, with the wide implementation of wireless networks, routing [KN02][CS05][MP04][SM05] [WL05][PK06][SS04]. For example, for ad hoc network or sensor networks, the devices used in these networks are all lightweight, and battery operated. Then how to conserve the energy to maintain the network functionality and connectivity is a key issue so that battery life is maximized[BK05].

In this paper, we will mainly describe the techniques used in energy
efficient routing in wireless ad hoc networks and sensor networks as
well. The remaining parts of this paper are organized as follows. In
Section 2, we will describe the definition of energy efficiency.
Then we discuss the routing types and the corresponding detailed
considerations. In Section 3, we will summarize the current
results on energy efficient routing protocols, including topology
control, power aware routing, sleep scheduling and so on. Section 4
will talk about the unified optimization frameworks that have been developed recently
to characterize and analyze the energy efficient routing method. In Section 5, the latest developments will be
presented, which are the hot topics in the research community. Then follows the industry development,
and at last comes the conclusion.

Back to Table of Contents

For a wireless networks, the devices operating on battery try to pursue the energy efficiency heuristically by reducing the energy they consumed, while maintaining acceptable performance of certain tasks. However, for multi-hop routing, which is typical for ad hoc and sensor networks, this is not the optimal strategy. Take the following network as an example[RM04]. In Fig.1 (a), the energy consumption for transmitting one bit over each link is labeled right beside the link. Now we want to transmit data from nodes 1, 2, 3, and 4 with rate r1, r2, r3, and r4 respectively to node 5. To minimize the whole power consumed, the routing is shown in Fig.1 (b). However, we show in Fig.1 (c) another routing strategy, where the numbers adjacent to the link are the fractional data rates going through the route. By simple calculations, the strategy in (c) outperforms (b) because node 1 can function 33% longer time.

Fig 1. Maximum Lifetime and Minimum Energy Consumption

From the above example, it is obvious that using the power consumption is not a good enough metric for energy efficiency. Actually, energy efficiency can be measured by the duration of the time over which the network can maintain a certain performance level, which is usually called as the network lifetime. Hence routing to maximize the lifetime of the network is different from minimum energy routing.

The underlying reason why the strategy in Fig.1(c) is better is because minimum energy routes sometimes attracts more flows, and the nodes in these routes exhaust their energy very soon; hence the whole network cannot perform any task due to the failure on these nodes. In other words, the energy consumed is balanced consumed among nodes in the networks. Routing with maximum lifetime balances all the routes and nodes globally so that the network maintains certain performance level for a longer time. In the following algorithms, generally the results described in the following are aimed to maximize the lifetime of the wireless networks.

There are lots of ways to categorize routing algorithms. However, now we classify them into 3 types. One is flooding and broadcast routing, which is often necessary during the operation of the wireless network, such as to discover node failure and broadcast some information. The second kind is multicast routing, which is very common in wireless networks, to communicate in a one-to-group fashion. The last is unicast, which is always in an end-to-end fashion and the most common kind of routing in networks.

It goes without saying that node failure is very possible in the wireless network. Hence saving energy when broadcasting in order to recover from the node failure or to re-routing around the failed nodes is essential. By the same token, multicast has the same challenge to achieve the energy efficiency. For unicast, it is highly related to the node and link status, which require a wise way to do routing as well. Sometimes, shortest path routing is possibly not the best choice from the energy efficiency point of view.

In the following section, we are mainly considering the protocols for
unicast routing if not noted otherwise.

Back to Table of Contents

In the literature, intensive research has been done in energy efficient communication to achieve power efficient, multi-hop communications in ad hoc networks. Generally they can be classified into four types, which are described in detail in the following. First let us look at an simple example. Considering the multi-hop communication channels from A to B, and the intermediate node C between them, see Fig. 2.

Fig 2. A Simple Scenario for Energy Consumption in Multi-hop Networks

The possible working states for the wireless modules (including transmitter or receiver) could be transmitting, receiving, idle, sleeping. The corresponding power consumed in these states can be represented by PIf sending data through C, then

Based on this observation, generally, in the literature, there are four kinds of ways to deal with this issue. First we show some protocols that only consider the control of transmission range. Then the sleep scheduling methods are described. Finally, a unified approach is proposed.

The motivation here is that both energy and bandwidth are limited in wireless ad hoc or sensor networks. So reducing the energy consumption and increasing network capacity is a rewarding goal for engineers. Topology control[VR99][VK03] [PS05][BK05] dynamically chooses the transmit range of each node in such a way that energy consumption is reduced and to some extent the connectivity of the network is maintained.

In a typical wireless ad hoc network, assume d(u,v) is the
distance between a pair of nodes u and v, &beta is the
parameter representing the reliability of communications between them. So
generally the power P_{u,v} consumed by two nodes are defined as
P_{u,v}&le &beta d(u,v)^{&alpha}, where &alpha is the
power-distance gradient. The transmission range is defined for node
u as a function R(u). Given the node position and range
assignment, if R(u)&le d(u,v), then the two nodes are connected.
Therefore, given the parameter &beta and communication networks,
we can minimize the energy consumption with possible range
assignments. Note that for a mobile network, there could be a
sequence of range assignment at different time. A detailed survey on
topology control protocols can be find in [PS05]. In
this paper, basic ideas and drawbacks of the protocols are presented.

Just as its name implies, power aware routing[SS98] is to choose appropriate transmission range and routes to save energy for multihop packet delivery[ZL04].

In [SS98], the author first discusses the five metrics for power aware routing:

- Minimize Energy consumed per packet: the most intuitive metric, however not optimal for maximum lifetime;
- Maximize Time to Network Partition: important for mission critical applications, hard to maintain low delay and high throughput simultaneously;
- Minimize Variance in node power levels: balance the power consumption for all the node in the network, i.e., all nodes in the network have the same importance;
- Minimize Cost per packets: try to maximize the life of all the nodes;
- Minimize Maximum Node Cost: try to delay the node failures.

Actually, sleep scheduling has little relation with routing. However, in a wireless network, not all the nodes should be kept active for selection as relays in the routes. So reducing the energy wasted in an idle state can also contribute to the energy consumption, where too many sleeping nodes will cause routing difficulties and shorter network lifetime, or even routing failure.

In [GX05] and its reference therein, the protocols maintain network connectivity and
coverage. A sleep schedule algorithm is proposed in [TM05] to
maximize the lifetime of network clustering.

However, none of the above three kinds of protocols optimize the energy consumption for all network states showed for Fig.2. All of them only consider a special state of the network. For example, topology control and power aware routing aim to reduce the transmission power but do not consider the idle state for each node. Sleep scheduling decrease the idle power, but does not worry about the transmission state. Obviously, from a global viewpoint, these approaches are only suboptimal for the dynamic networks. Power aware routing and topology control are effective only when the network workload is so high that the transmission power dominates the overall power consumption of the network. Similarly, sleep scheduling works only when the idle power dominates the overall power consumption. In [GX05], the authors proposed a globalized minimum power configuration approach for wireless sensor networks to eliminate the drawbacks.

Generally, given network topology and the traffic demands, to find the way to minimize the total power
consumption is not very easy. It is equivalent to the minimum-weight steiner tree problem, which is NP hard.
Therefore approximation algorithms are necessary. In [GX05], the authors proposed several kinds
of such algorithms. Given the network represented as a graph G(V,E), and traffic demands I, now we try to find
a subgraph G'(V', E')(V'&sube V, E'&sube E) and the route f(s_{i},t_{j}) within G' for each traffic
(s_{i}, t_{j}, r_{i,j})&isin I so that the total power is minimized. Four algorithms are described in the paper, which are
(a)Matching based Algorithm,(b)Shortest-Path Tree Heuristic,(c)Incremental Shortest-path Tree Heuristic and (d)
Constant-ration Approximation Algorithm.

Back to Table of Contents

However, the above protocols all consider the energy or power
as static parameters that are somehow fixed over the optimization
period, which is not true. Since power is purely a physical layer
element, while routing is an upper layer issue, a cross layer
optimization over routing, link and MAC layers are preferred. In this
section, we survey two kinds of optimization frameworks: flow
optimization and cross-layer optimization.

Network flow optimization is originally established by the Operation Research community. This approach used for information routing in energy constraint wireless networks is introduced by [BK05]. The authors propose a non-linear optimization framework to minimize the energy usage and maximize the lifetime for the network.

Generally assume that there are n nodes, each with limited energy
E_{i} and maximum source rate of R_{i}. The models consider f_{ij}
and P_{ij} as the flow rate and transmission power on the link
between node i and j. Also assume the per bit rate reception
power as C. Then the problem to minimize the energy usage is
formulated as follows, note that f_{min} is the pre-specified
minimal information that must be transmitted over the link.

where (a) ensures for all nodes except the sink, the out-flow from each node is greater or equal to the in-flow, (b) ensures the maximum source rate is less than the sum of in-flow rate and the maximum rate of the node. (c) is the fairness constraint, where α_i is the faction parameters to ensure that the flow generated at the sink is not greater than the total flow in the network. (e) is the Shannon capacity constraint.

The key asset of this flow optimization based approach is to provide a close-formed
framework for the energy constrained networks, which is very useful for comparing the performance
of the existing protocols in the literature. In the paper, the authors verified
this through several examples.

In this section, cross-layer optimization framework for energy efficient routing is discussed. In the aforementioned protocols, the variation of the wireless links is considered as invariant during some period of time. However, it is not true in the real radio environment, since the signals are always enduring fades in the air. Thus, optimization over the physical layer variations is promising. In [JY06], a cross-layer optimization framework is proposed to maximize the utilization of the network under the constraints of link capacity. Compared with flow optimization, it is more general and easy to decompose into sub-problems corresponding to power allocation in physical layer and data routing in network layer. Also the authors claim that many existing protocols can be analyzed under the framework.

The model for network topology is a graph G=(V,E). Let
**r** be the data rates, N(**r**) be the set of flow
rates that needed to support **r**. S is the number of
sessions in the network, and r_{i},i&isin S is the rate for session
i. The flow rates **f** is the flow rate vectors showing
the flow routing strategy. **p**_{max} is the power
constraints for nodes in V. C(**p**_{max}) is the
achievable rates **c** on the link. The the optimization
problem is formulated as:

where constraint (a) models the inter-dependence of achievable throughput

In [JY06], the authors also show some examples on how to use this cross-layer optimization
framework such as maximization the multicast rate with energy constraint. The limitation and extensions
on this framework is also discussed.

Back to Table of Contents

In the former sections, we have described several kinds of energy efficient routing algorithms. Now, we dig a little deeper to the sources, sinks, and links. For example, see Fig. 3.

Fig 3. A Simple Topology

To save energy, intuitively, if we can send fewer messages at the sources, energy is conserved. By the same token, if we can do reliable computation at the sink and intermediate nodes, energy can also be further saved. For routes, it is better to find good path with diversity advantage from the intermediate nodes, not the shortest path. For example, the energy necessary for transmitting date from s to t using green routes could be much less than with in the red routes, although there are more hops for blue routes. Even more, if the nodes can cooperate between each other, energy can also be saved. In the following, based on these ideas, we will show someRecently, Belief Propagation attracts great research interest in the community, which aims to do the reliable computation on a graph or tree model. In [DB05], the authors propose a modified belief propagation algorithm targeting towards to reduce the communication cost of broadcast supporting networks. Belief propagation algorithm is a distributed inference algorithm, which calculates the marginal probability of the nodes. Then it is naturally feasible for the message delivery through the nodes with high marginal probability in the communication networks. Through computing the node beliefs (posterior probabilities), the algorithm can reliably exchange the messages over the networks. It is shown to be able to significantly reducing the number of transmitted messages, while at the same time achieve the identical computation results. So it is very useful too for the broadcast routing.

Another way to reduce total number of the messages to transmit is to take advantage of spatial
correlation on routing with compression, which can significantly
reduce the energy consumption. Typically, in sensor networks, data gathering applications in which data originates
at multiple correlated sources are very popular. When the data is routed to a single sink,
data aggregation would primarily involve in-network compression of the data.
In the literature, there are techniques such as distributed source doing techniques, joint source
coding and routing techniques, and opportunistic compression along the shortest path tree.
The intuitive idea here is to jointly
routing and in-network compression, i.e., data aggregation to reduce the
bit transmitted over the network. For details, the reader can refer
to [SP04] and the reference therein.

Network coding is another novel and promising technique to wisely
transmit the message in the network, especially for multicast and
broadcast. For example in Fig 4., nodes A and B want to exchange
packets via an intermediate node S. A [resp. B] sends a packet a
[resp. b] to B, which then broadcasts a xor b instead of a and b in
sequence. Both A and B can recover the packet of interest, while the
number of transmissions is reduced.

Fig 3. A Simple Example on Network Coding

In [CF05], the authors claim that the coded network only outperforms traditional routing tree-based approaches, but is also easily implemented in a dynamic system with limited mobility and energy. The practical usage of network coding in networks is shown in [CF06][JW05], whose results show that network coding achieves energy efficient multicast and broadcast. For example, for a circular topology, network coding can out perform the protocols without network coding with only one half of the messages if each node in the network can successfully broadcast information to its two nearest neighbors. And with a squared grid network, only 3/4 of the messages are needed for the protocols without networking coding to broadcasting. Generally for random networks, network coding also has better performance.

Back to Table of Contents

Since wireless ad hoc or sensor networks are not widely implemented in real world except military implementations, it is hard to find any industry products or standards that implement the energy efficient protocols.

However, IEEE standards such as 802.11 and 802.16 for wireless and mobile networks implement some energy efficient protocols. For example, in 802.11 standards, it is recommended to switch to sleep mode and inform the base station to conserve the power. Then the base station buffers packets received from other nodes in the network whose destination is the sleeping mobile. Moreover, the base station periodically transmits a beacon that contains information about such buffered packets. When the mobile wakes up, it listens for this beacon, and responds to the base station, and then the base station can forward the packets to the waked node. This approach conserves power but results in additional delays at the mobile that may affect the QoS. Similar sleep management is also recommended in IEEE802.16.

To the best knowledge of the author, there are few industry productions currently. It is still in the
incipient period. The MeshScape system, developed by the start up company--Millennial
Net, Inc[MB05], offers a power-efficient solution allowing all
nodes to be battery-operated, enabling networks to run on coin cell
batteries for years. The MeshScape protocol generates minimal packet
overhead for high power efficiency. End nodes and mesh nodes are both optimized to
be actively listening or transmitting for minimal time periods to conserve power.
Although end nodes of most solutions can sleep for power conservation,
MeshScape also enable mesh nodes to operate at sleep mode for complete, network-wide
power optimization.

Back to Table of Contents

In this paper, we have summarized both the literature and the cutting edge research on energy
efficient routing, including topology control, power aware routing,
sleep scheduling and so on. Flow optimization and cross layer optimization frameworks are reported to analyze the design and performance of
routing protocols. Furthermore, recent progress and
new method, using data aggregation, belief propagation and network coding to achieve energy efficient communications are also presented.
Then we talk a little bit about the effort from industry to realize
energy efficient communications.

Back to Table of Contents

[SG03]S. Gandham, M. Dawande, and R. Prakash, "Energy efficient routing in ad hoc disaster recovery networks," INFOCOM 2003, IEEE Volume 1, 30 March-3 April 2003 Page(s):682 - 691 vol.1

[JZ06]Jihui Zhang, Qian Zhang, Bo Li, Xiaonan Luo and Wenwu Zhu;"Energy-efficient routing in mobile ad hoc networks: mobility-assisted case," IEEE Transactions on Vehicular Technology, Volume 55, Issue 1, Jan. 2006 Page(s):369 - 379

[KN02]K. Nakano, S. Olariu and A.Y. Zomaya, "Energy-efficient routing in the broadcast communication model," IEEE Transactions on Parallel and Distributed Systems, Volume 13, Issue 12, Dec. 2002 Page(s):1201 - 1210

[CS05]Chih-Wei Shiou, Yeong-Sung Lin, Hsu-Chen Cheng and Yean-Fu Wen, "Optimal energy-efficient routing for wireless sensor networks," AINA 2005, Volume 1, 28-30 March 2005 Page(s):325 - 330

[MP04][6]M.B. Pursley, H.B. Russell and J.S. Wysocarski, "Energy-efficient routing in multimedia ad hoc networks," IEEE WCNC, Volume 3, 21-25 March 2004 Page(s):1311 - 1316

[SM05] S.D. Muruganathan, D.C.F. Ma, R.I. Bhasin, and A.O. Fapojuwo, "A centralized energy-efficient routing protocol for wireless sensor networks," IEEE Communications Magazine, Volume 43, Issue 3, March 2005 Page(s):S8 - 13

[WL05]Weifa Liang, "Minimizing energy and maximizing network lifetime multicasting in wireless ad hoc networks," IEEE International Conference on Communications, Volume 5, 16-20 May 2005 Page(s):3375 - 3379

[PK06]P.C. Kokkinos, C.A. Papageorgiou, and E.A. Varvarigos, "Energy-aware routing in wireless ad-hoc networks," IEEE Transactions on Vehicular Technology, Volume 55, Issue 1, Jan. 2006 Page(s):369 - 379

[SS04]S.-M. Senouci and G. Pujolle, "Energy efficient routing in wireless ad hoc networks," 2004 IEEE International Conference on Communications, Volume 7, Page(s):4057 - 4061

[BK05]B. Krishnamachari, "Networking Wireless Sensors," Cambridge University Press, December 2005

[CF05]C. Fragouli, J.-Y. Le Boudec and J. Widmer, "Network Coding: An Instant Primer," Technical Report, EPFL 2005

[GX05]G. Xing, C. Lu, Y. Zhang, Q. Huang, and R. Pless "Minimum Power Configuration for Wireless Communication in Sensor Networks," Technical Report, WUSTL 2005

[JY06]Jun Yuan, Zongpeng Li, Wei Yu and Baochun Li, "A Crosslayer Optimization Framework for Multihop Multicase in Wireless Mesh Networks", accepted in IEEE Journal on Selected Areas in Communications, 2006

[DB05]D. Bickson, D. Dolev and Y. Weiss, "Modified Belief Propagation Algorithm for Energy Saving in Wireless and Sensor Networks," eibniz Center TR-2005-85, School of Computer Science and Engineering, The Hebrew University, 2005

[SS98]S. Singh, M. Woo, and C.S. Raghavendra, "Power-Aware Routing in Mobile Ad Hoc Networks," ACM/IEEE MOBICOM 1998

[VR99]V. Rodoplu and T. H. Meng, "Minimum Energy Mobile Wireless Networks," IEEE J. Selected Areas in Communications 17(8), 1999

[ZL04]Z. Liu and A. Sankar, "Maximum lifetime routing in wireless ad-hoc networks," IEEE INFOCOM 2004

[VK03]V. Kauadia and P.R. Kumar, "Power Control and clustering in ad hoc networks," IEEE INFOCOM 2003

[PS05]P.Santi, "Topology Control in Wireless Ad Hoc and Sensor Networks," ACM Comp. Surveys, Vol. 37, n. 2, p. 164-194, June 2005

[RM04]Ritesh Madan, "Routing for maximizing the lifetime of energy Constrainted Sensor Networks," EE360 Course Report, Stanford University, March 2004

[TM05]T. Moscibroda and R. Wattenhofer, "Maximizing the lifetime of dominating sets", WMAN, 2005

[SP04]S. Pattem, B. Krishnamachari, and R. Govindan, "The Impact of Spatial Correlation on Routing with Compression in Wireless Sensor Networks," ACM/IEEE International Symposium on Information Processing in Sensor Networks (IPSN), April 26-27, Berkeley, CA 2004

[JW05]J. Widmer, C. Fragouli, and J.-Y. Le Boudec, "Low-complexity energy-efficient broadcasting in wireless ad-hoc networks using network coding, " 1st Network Coding Workshop 2005

[CF06]C. Fragouli, J. Widmer, and J.-Y. LeBoudec, "A Network Coding Approach to Energy Efficient Broadcasting: from Theory to Practice,"IEEE INFOCOM 2006

[MB05]Millennial Net,"MeshScape Brochure," http://www.millennial.net/resources/brochures/MeshScape_Brochure.pdf, 2005