A Survey on Energy Efficient Routing in Wireless Networks

Jinjing Jiang

Abstract

In this paper, we present a survey on the art of energy efficient routing for wireless networks, including both protocols and analytical frameworks for energy efficient routing. Moreover, the latest development and industry effort are discussed.

Keywords:

Energy efficiency, Topology control, Power aware routing, Sleep scheduling, Optimization framework, Data aggregation, Network coding

Table of Contents:

1 Introduction

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

2 How to Define the Energy Efficiency

2.1 Definition of Energy Efficiency

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.

[Def]

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.

2.2 Routing Algorithms and Energy Efficiency

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

3 Energy Efficient Routing Algorithms

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.

[Def]

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 Ptx(SNR(d)), Prx, Pid, and Ps, where SNR(d) is the signal to noise ratio for certain reliable transmission over some communication range. Therefore P_tx is the function of d, which is the transmission range such as the distance between A and B, or C. Also, the energy consumed is the function of the data rates over the channel. Therefore, there are two possible ways to communicate between A and B. One is to directly transmit date from A to B; or we can relay with Node B. However, these two different methods lead to two different level of energy consumption, in which one must be better. Assume that the power consumed is linear with the data rate sent over the links. Then the two different methods have two levels of power consumption. Assume the link bandwidth is W. The first transmits data directly from A to B, with

[Def]


If sending data through C, then

[Def]


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.

3.1 Topology Control

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 Pu,v consumed by two nodes are defined as Pu,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.

3.2 Power Aware Routing

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:

Then the authors used them as the new power aware metric for determining the routes, which shows that the per packet cost is reduced by 40-70% and mean time node failure increase significantly. Assuming the lifetime for each node is inversely proportional to the information going through that node, the authors in [JC04][ZL04] use the optimal lifetime as the key metric, trying to maximize the minimum lifetime for individual nodes under the constraints of information flows at each nodes. In order to solve this problem, the authors proposed distributed algorithms using bisection search. One is the heuristic flow redirection algorithm[JC04], whose basic idea is to start from a feasible routing strategy, then redirect the flows from nodes with low lifetimes to nodes with higher lifetimes. Another algorithm in [ZL04] uses bisection search for successive feasible routing strategies.

3.3 Sleep Scheduling

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.

3.4 Globalized Approach

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(si,tj) within G' for each traffic (si, tj, ri,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

4 Unified Frameworks for Energy Efficiency Optimization

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.

4.1 Flow Optimization Framework

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 Ei and maximum source rate of Ri. The models consider fij and Pij 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 fmin is the pre-specified minimal information that must be transmitted over the link.

[Eqn1]


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.

4.2 Cross-Layer Optimization Framework

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 ri,i&isin S is the rate for session i. The flow rates f is the flow rate vectors showing the flow routing strategy. pmax is the power constraints for nodes in V. C(pmax) is the achievable rates c on the link. The the optimization problem is formulated as:

[Eqn2]


where constraint (a) models the inter-dependence of achievable throughput r and data flow routing strategy f. (b) and (c) are capacity and flow rate constraints as described in the flow optimization framework. Using this framework, the authors jointly consider data routing, wireless interference and so on to achieve the overall optimal performance.

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

5 Latest Developments

5.1 Revisit on Energy Efficiency

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.

[NC]

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 some

5.2 Source, Intermediate Node and Sink

Recently, 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.

5.3 Network Coding

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.

[NC]

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

6 A Brief Summary on Industry Standards

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

Summary

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

Reference

[JC00]J.H. Chang and L. Tassiulas, "Energy conserving routing in wireless Ad-hoc networks," IEEE INFOCOM, 2000

[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