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 NetworksThe 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
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.
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:
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(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
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
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.
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 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:
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 TopologyTo 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
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.
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
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
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