Energy consumption in wireless networks

Get Complete Project Material File(s) Now! »

Energy eﬃciency: State of the art

Introduction

The diversity of the application supported by wireless ad hoc and sensor networks explain the success of these networks. However, nodes in such networks can have a limited amount of energy. This energy can be very expensive, diﬃcult or even impossible to renew. So saving energy to maximize network lifetime is one of the critical problems in wireless ad hoc and sensor networks. That is why algorithms and protocols operating in such networks should be energy eﬃcient. Several solutions are proposed to improve the network lifetime.
In this chapter, we start by giving diﬀerent definitions of the network lifetime. Then, we present the energy consumption model the most frequently used. We introduce the diﬀerent states that a wireless node can take and the diﬀerent reasons of energy consumption in the network. In next sec-tion, we give a review of energy eﬃcient solutions proposed for wireless ad hoc and sensor networks. We classify these solutions into four classes. We detail each class and give some examples. Then, we present some solutions that adopt cross layering to be energy eﬃcient. Finally, we analyze the node energy consumption distribution in wireless ad hoc and sensor networks and identify the states in which nodes consume the highest part of their energy.

Definition of network lifetime

All energy eﬃcient techniques share the same goal: to maximize network lifetime. Unfortunately, there is no definition of network lifetime commonly agreed in the literature. Several definitions of network lifetime exist, the most frequently used are:
Definition D1: Time to first node failure due to battery outage. As sensor redundancy is gener-ally used, a sensor failure can have no influence on the network and application functionalities. That is why, some authors prefer the time to the failure of a certain percentage of the sensors (e.g. 20%), in order to take into account possible redundancy.
Definition D2: Time to application failure: an application functionality is no longer ensured (e.g. a vital parameter of a patient is no longer monitored). Definition D1 diﬀers from definition D2 because of redundancy in sensor coverage. Indeed, if an area is covered by k sensors, the failure of k-1 of them is perfectly tolerated.
Definition D3: Time to first network partitioning. As soon as the network is no longer con-nected, vital information can no longer be transferred to its destination.
In the absence of knowledge of the application supported by the network, definitions D1 and D3 are the most useful ones to compare diﬀerent energy eﬃcient strategies. In all cases, an energy consumption model is needed to conclude in favor of an increase in network lifetime. In next section, we present the energy consumption model the most frequently used.

Energy consumption model

There are many energy consumption models proposed in the literature. We can unified [25] these models by the following one highlighting two components of the energy dissipated by the transmitter. The first component reflects the energy consumed by the radio. The second component presents the energy consumed by the amplifier and depends on the distance between the transmitter and the receiver.
Etransmit = C1(size) + C2(size; d) = C1 size + C2 size d = size(C1 + C2 d ); (2.1) with: C1: Energy consumed by the radio of the transmitter to transmit a bit,
C2: Energy consumed by the amplifier to send a bit at a distance of 1 meter, size: Packet size,
d: Distance between the transmitter and the receiver, and 0 < < 6 values of 2 or 4 are the most frequently used.
Many works about topology control focus on the component proportional to the distance. Equa-tion 2.1 becomes, when uniformed by the size of the transmitted packet: Etransmit = C1 + C2 d .
This formula points out the relation between energy consumption and distance. This relation is used in topology control to optimize energy consumption by tuning the transmission power taking into account the distance between the transmitter and the receiver.
Many other works suppose that the transmissions is done at the maximum power. In other words, the transmitter uses the transmission power such that any receiver at a distance equal to the transmission rage correctly receives the message. Consequently, we can consider the quantity (C1 + C2 d ) as a constant named C. Hence, the energy dissipated in a transmission by a transmitter is : Etransmit = C size where size denotes the packet size in bits.
In our work, we assume that: the transmission power is a constant and the same for all nodes in the network.
Concerning the receiver, it consumes energy to capture packets. this energy is expressed as follows: Ereceive = C1(size) = C1 size; (2.2)
with: C1: Energy consumed by the radio of the receiver to capture one bit,
size: Packet size.
We notice that this energy can not be neglected in the energy dissipated during transmissions.

In addition to the transmit and receive states a wireless node can be in the idle or sleep states.
In next section we present and explain each wireless node state.

Energy states

A wireless node can be in one of the following four states: Transmit, Receive, Idle or Sleep. Each state corresponds to a diﬀerent power level (see Table 2.1):
Transmit: node is transmitting a frame with transmission power Ptransmit;
Receive: node is receiving a frame with reception power Preceive. This frame can be decoded by this node or not, it can be intended to this node or not;
Idle (listening): even when no messages are being transmitted over the medium, the nodes stay idle and keep listening the medium with Pidle;
Sleep: the radio is turned oﬀ, and the node is not capable of detecting signals: no commu-nication is possible. The node uses Psleep that is largely smaller than in any other state: the energy consumption is minimum;
In Table 2.1, we report the reference values of power consumption in each state taken from a Lucent silver wavelan PC card [58] implementing the IEEE 802.11b medium access [14] and a ZigBee node [59] implementing IEEE 802.15.4 [60] medium access. In both casees, we can notice that the least consuming state is the sleep state. However, the power used in transmit and receive state is close for the IEEE 802.15.4 medium access.

Reasons of energy consumption in the network

In wireless ad hoc and sensor networks, nodes dissipate energy in processing, transmitting and receiving messages. This energy is needed for correct working of the wireless networks. In addition to this energy, there is a great amount of energy wasted in states that are useless from the application point of view, such as:
idle listening: since a node does not know when it will receive a message it must permanently listen to the medium and so it remains in the idle state. As we can notice in Table 2.1 the power used in idle state is close to the power used in receive state.
overhearing: When a sender transmits one packet to next hop, because of the shared nature of wireless medium, all neighbors of the source receive this packet even if it is intended to only one of them. Thus the overhearing is the energy dissipated when the node is an one-hop neighbor of the sender and is not the destination.
interference: Each node situated between transmitter range and interference range receives this packet but it cannot decode it.
collision: In case of CSMA/CA medium access, When a collision occurs, the energy dissipated for the transmission and for the reception of colliding frames is wasted.
The energy constrained nature of wireless nodes requires the use of energy eﬃcient strategies to minimize the energy wasted in these useless states and so maximize network lifetime. In the next section, we describe and classify works aimed at minimizing energy consumption and improving network lifetime.

Classification of energy eﬃcient techniques

With the energy constrained nature of wireless networks, it is very important to use energy eﬃciently. Many researches address this issue in wireless networks. their goal is to maximize the network lifetime. We can classify these researches in four strategies.
1. Energy eﬃcient routing: the goal is to minimize the energy consumed by the end-to-end transmission of a packet, to avoid nodes with a low residual energy and reduce the number of unsuccessful transmissions, like [27], [28], [29], [30], [31], [32], [33];
2. Node activity scheduling: the idea of scheduling node activity is to alternate node states between sleeping and active to minimize energy consumption while ensuring the network and application functionalities, like [7], [8], [9];
3. Topology control by tuning node transmission power: these strategies find the op-timum node transmission power that minimizes energy consumption, while keeping network connectivity, like for instance [2, 3];
4. Reducing the volume of information transferred: These strategies consist in: aggregating information with the use of clusters, like [25, 26] or without, like [4], [5], [6]; decreasing the frequency of information refreshment with distance, like [45]; avoiding to transfer information to uninterested nodes.
optimizing the broadcast of messages throughout the network.
We now detail each of these four classes of energy eﬃcient strategies.

Energy eﬃcient routing

There exist many energy-aware routing protocols designed for wireless sensor networks. Our purpose is not to give an exhaustive list but rather to present a classification of these protocols. All of them aim at minimizing the energy consumed either in active communications, or in inactivity periods, or both. Some of them make assumptions on the application model (e.g. query of data meeting some attributes). Some build clusters to reduce the number of transmissions. Others use location based information to limit the broadcast of queries. Furthermore, some of them use multipath routing, in order to balance the energy consumption over the network nodes. They can also be distinguished according to the criteria used to select routes. Finally, we get the classification [15] of Table 2.2 and organized according to the following criteria: data centric, hierarchical, geographical, energy criteria used for route selection, multipath routing, support of sleeping nodes. In this table residual means that the residual energy of nodes is taken into account. Overhear means that the route minimizing the energy dissipated during a transmission is selected, taking into account the energy lost in overhearing. Interference means that the route minimizing the en-ergy dissipated during a transmission is selected, taking into account the energy lost in interferences.
A data centric routing protocol optimizes traﬃc by querying sensor nodes based on their data attributes or interests. It assumes a query driven model of data delivery and a routing based on data attributes. A generic routing protocol does not make such assumptions. Examples of data centric routing protocols are SPIN [6], and Directed Diﬀusion [16]. In SPIN, a node advertises the availability of data allowing interested nodes to query that data. However, this protocol does not ensure the end-to-end delivery of data if intermediate nodes are not interested in that data. In Directed Diﬀusion, the sink broadcasts an interest message to sensors, interested sensors reply with a gradient message. Both interest and gradient messages allow the sink to establish paths to sensor nodes. Then the sink reinforces the selected path to the sensor node. This protocol is eﬃcient only with on demand query.
A hierarchical routing protocol improves scalability and minimizes traﬃc by building clus-ters. Each sensor transmits its data to its cluster head that is in charge of aggregating them and sending them to the sink. On the contrary, in a flat protocol, all sensor nodes can forward data to the sink if they are in communication range. The most famous hierarchical routing protocol is LEACH [25], where the cluster head is chosen according to its signal strength. Energy consump-tion is balanced by a random change of cluster heads. Initially, LEACH supports only single hop routing between both a sensor node and its cluster head and between a cluster head and the sink. TEEN [17], is another example of hierarchical protocol. TEEN is also data centric. It builds clusters of diﬀerent levels until reaching the sink node. The cluster head broadcasts two thresholds to the nodes: only a value of the sensed attribute higher than the hard threshold can force the sensor node to transmit, and if this sensor was already transmitting only changes higher than the soft threshold should be transmitted. This mechanism considerably reduces the number of transmissions. How-ever, TEEN is not adapted to periodic queries. An extension called APTEEN [18] has been proposed.
A geographical routing protocol improves routing by using location information. Each sen-sor node is assumed to know its location (e.g. with GPS for instance). Hence, the broadcast of a query can be limited to a given region, as in GEAR [19]. In this protocol, a node forwards a packet to its neighbor that is the closest one to the destination. If all neighbors are at the same distance, some neighbor is randomly selected. GAF [20] is another example of geographical routing protocol energy aware. Indeed, each node uses the knowledge of its location provided by its GPS to determine its region in the virtual grid. Nodes located in the same region of the grid are considered equivalent from the routing point of view. Moreover, GAF allows nodes to sleep as long as the existence of an active node per region in the virtual grid is achieved.
Energy criteria taken into account for route selection enables to distinguish between protocols selecting (i) the minimum energy path like [30], (ii) the path avoiding nodes with low residual energy like REAR [32] and (iii) the path of minimum energy while avoiding nodes with low residual energy, like EOLSR [?]. This protocol will be presented in Chapter 3.
Multipath routing protocols maintain several paths for the same couple (source, destina-tion). As energy is taken into account, the path minimizing the energy consumed by an end-to-end transmission is usually selected as the primary path. Another path, called the secondary one, is used less frequently, with a probability inversely proportional to its energy cost. The source selects for each data packet to transmit, the path to use according to this probability. Source routing is generally used to force the data packet to follow the path selected by the source. Protocols described in [27] to [39] are multipath routing protocols. On the contrary, with a hop-by-hop routing protocol, a data packet does not contain its path and is routed to the next hop, at each visited node.
A routing protocol can support sleeping nodes. As the sleep state is the least consum-ing state, making nodes sleep during their inactivity period spares energy. Such protocols have to maintain both network connectivity and application functionalities. As examples, we can cite GAF [20], SPAN [21] and PEN [22]. In SPAN, nodes build a connected backbone such that only nodes belonging to this backbone are active. These nodes are called coordinators. A node decides to become a coordinator using a random backoﬀ delay, function of its residual energy and the number of neighbors it can bridge.
Other classifications exist, like for instance this given in [23] that does not take into account the support of sleeping nodes.
An energy-aware routing protocol can exhibit several criteria. For instance, EAP [24] is hier-archical and allows nodes to sleep, while ensuring the coverage of the monitored region as well as network connectivity.
In the next section, we present the second energy eﬃcient strategy: node activity scheduling.

READ INFORMATION PROVERTY AND SOCIAL JUSTICE

Node activity scheduling

As the energy consumed in sleeping state is smaller than the energy consumed in any other state as shown in Table 2.1, turning oﬀ the sensor radio when it does not receive or transmit data. Hence, keeping sensor nodes in the sleep state, is a good way to save energy. However, this must be accompanied by node activity scheduling to prevent network partition and message loss when some nodes are in sleep state. We can distinguish solutions that: are independent of the medium access, and build active node sets. depend on the medium access: CSMA/CA, TDMA or hybrid.

Solutions independent of the medium access

In this type of solutions, the number of deployed nodes is supposed higher than the optimal number (i.e nodes are redundant). The goal of these protocols is to build a set of active nodes, such that only nodes belonging to this set must be active, all other nodes can sleep to keep their energy while network connectivity and application functionalities are still ensured.
In [7], the authors propose to divide the network nodes in disjoint sets, such that each node set satisfies the network function. These sets are activated successively, and at any time only the nodes of one set are active. All others nodes are in the sleep state. The problem consists in maximizing the number of disjoint sets. It has been shown NP-complete. The protocol proposed may increase network lifetime proportionally to the number of disjoint sets. However, this centralized protocol, assumes that all nodes are synchronized and does not take into account the real node energy con-sumption: it supposes that the energy consumption is uniform for all nodes belonging to the same set.
Authors in [9] propose to maximize network lifetime in dividing network nodes into non disjoint sets, unlike in [7]. Every set satisfies the network function. They prove that the node participation in several sets may improve network lifetime.
In [8], a distributed and localized solution is proposed. It consists in selecting a connected dominating set of sensor nodes (i.e. each node is either in this subset or is a neighbor of a node in this subset). Only the nodes of this set are active. All other nodes can change their state to sleep mode. A priority is assigned to each node, this priority depends on its residual energy. A node whose function is assured by the dominating set can sleep if and only if: the dominating set is connected, all its neighbors have at least one neighbor in this set, all nodes in the dominating set have a higher priority.
This protocol is localized: each node needs to know information about its one and two-hop neighbors only.

Solutions depending on the medium access

With these solutions, any node is allowed to sleep, whenever it is neither transmitting nor receiving. These solutions can be classified in three classes on depend of the medium access:
CSMA/CA. The RTS/CTS exchange preceding any unicast data transmission is used to enable the neighbors of the sender and the receiver to sleep during the communication. In [10], S-MAC, an energy eﬃcient MAC protocol for sensor networks is introduced. The main goal of S-MAC protocol is to reduce energy consumption by using a periodic sleep-wake up cycle, while supporting good scalability and collision avoidance. It consists of three major components:
1) periodic listen and sleep, 2) collision and overhearing avoidance, and 3) message passing. It is based on a CSMA/CA channel access and the RTS/CTS mechanism. Any two nodes exchanging RTS/CTS packets in the listen period need to keep in an active state and start an actual data transmission. Otherwise, all other nodes can enter the sleep mode in order to avoid any wasteful idle listening and overhearing problems. Many other variations of S-MAC are proposed like T-MAC [11] with an adaptive length of active state, D-MAC [12] to reduce the network latency, O-MAC [13] to improve the throughput, etc. However, the RTS/CTS mechanism is not adequate in case of short message which is usually case in wireless sensor networks. This increases the overhead and reduces the protocol eﬃciency.
TDMA. In TDMA, node transmissions are scheduled and no energy is wasted in collision. In [61], a deterministic solution based on slot assignment named TRAMA is proposed. It con-sists in three modules: 1) a neighborhood discovery protocol, 2) a schedule exchange protocol and 3) an adaptive election algorithm that selects the transmitter and receiver(s) for each time slot. Only nodes having data to send contend for a slot; notice however, that a node does not know which of its 1-hop and 2-hop neighbors have data to send. The node with the highest priority in its twohop neighborhood wins the right to transmit in the slot considered. Each node declares in advance its next schedule containing the list of its slots and for each slot its receiver(s). The adaptivity of TRAMA to the traﬃc rate comes at a price: its complexity. To reduce the complexity of TRAMA, FLAMA [62] is introduced. However, this protocol is designed only for data gathering applications in sensor networks based on tree structure. The protocol is simplified both in terms of message exchange and processing complexity. The number of slots allocated by FLAMA to a node with a given traﬃc rate highly depends on node priority computation.
Hybrid. Z-MAC [97] operates like CSMA under low contention and like TDMA under heavy contention, reducing collisions among two-hop neighbors by means of an initial slot assignment made by DRAND [80]. The goal of Z-MAC is to optimize the bandwidth eﬃciency of the MAC protocol, selecting CSMA/CA and TDMA when they exhibit the best performance. We can notice that Z-MAC does not allow an immediate acknowledgement of unicast messages. However this acknowledgement is important in wireless communication to confirm the correct reception of the packet. Moreover, since a slot that is unused by its owner can be used by one of its neighbors, the nodes must stay awake in order to be able to receive this message if they are the destination. From the energy point of view, Z-MAC reduces the activity period in the polling cycle enforced by the application but does not allow nodes to sleep during the activity period, what does SERENA (see Chapter 4) whose goal is to maximize network lifetime by scheduling node activity. DRAND [80] assigns slots to nodes in such a way that one-hop and two-hop neighbors have diﬀerent slots. This randomized algorithm has the advantage of not depending on the number of network nodes but at the cost of an asymptotic convergence.

Table of contents :

1 Introduction
1.1 Motivation
1.1.1 Specificities of wireless ad hoc and sensor networks
1.1.2 Differences between wireless ad hoc and sensor networks
1.2 Problem Statement
1.3 Contributions
1.4 Thesis organization
2 Energy efficiency: State of the art
2.1 Introduction
2.2 Definition of network lifetime
2.3 Energy consumption model
2.4 Energy consumption in wireless networks
2.4.1 Energy states
2.4.2 Reasons of energy consumption in the network
2.5 Classification of energy efficient techniques
2.5.1 Energy efficient routing
2.5.2 Node activity scheduling
2.5.3 Topology control by tuning node transmission power
2.5.4 Reduce the amount of information transferred
2.6 Cross layering optimization
2.7 Analysis of node energy consumption distribution
2.8 Discussion
2.9 Conclusion
3 Energy efficient routing
3.1 Introduction
3.2 Related work
3.2.1 Multipath routing protocols
3.2.2 Adaptive hop-by-hop routing protocols
3.3 EOLSR: Energy efficient extension of OLSR
3.3.1 OLSR functioning overview
3.3.2 Why OLSR is not energy efficient?
3.3.3 Principles of EOLSR
3.3.4 Energy consumption model
3.3.5 Energy efficient selection of MPRs
3.3.6 Routing algorithm for EOLSR
3.3.7 Optimized broadcasts
3.3.8 EOLSR design
3.4 Performance evaluation of EOLSR
3.4.1 Comparison of EOLSR with MinEnergy and MaxPacket
3.4.2 Comparative performance evaluation of EOLSR with multipath routing strategies
3.4.3 Energy consumption distribution
3.5 EOLSR for data gathering applications
3.5.1 Maintaining routes only to strategic nodes
3.5.2 Applicability of this optimization
3.6 Conclusion
4 Node activity scheduling
4.1 Introduction
4.2 Graph coloring: state of the art
4.2.1 Vertex coloring
4.2.2 Edge coloring
4.2.3 Graph coloring applied to wireless sensor networks
4.3 SERENA: Scheduling Router Node Activity
4.3.1 Two hop coloring algorithm
4.3.2 Slot assignment algorithm
4.3.3 Message exchanged and information maintained in SERENA
4.3.4 Performance evaluation of SERENA
4.3.5 Comparison with TDMA and USAP
4.4 SERENA in a real wireless network environment
4.4.1 Support of immediate acknowledgement: Extension to three-hop coloring algorithm
4.4.2 Coloring algorithm with unidirectional links
4.5 Color conflict detection and resolution
4.5.1 Causes of a color conflict
4.5.2 Principles of detection and resolution of color conflict
4.6 Synchronization
4.7 Conclusion
5 Node activity scheduling for data gathering applications
5.1 Motivations
5.2 SERENA adaptation to data gathering applications
5.2.1 Principle
5.2.2 Messages exchanged Information maintained by each node
5.2.3 Algorithm
5.2.4 Computation of the number of colors
5.2.5 Comparison with another tree coloring algorithm
5.2.6 Performance evaluation
5.2.7 Benefit brought by coloring
5.2.8 Adaptivity of the coloring algorithm
5.3 The optimized coloring algorithm for tree topologies
5.3.1 General principles
5.3.2 Comparison with TDMA-ASAP
5.4 Generalization
5.5 Network dimensioning with network calculus
5.5.1 Network calculus
5.5.2 Comparison of our algorithm with ZigBee
5.6 Conclusion
6 Cross layering and integration of energy efficient techniques
6.1 Introduction
6.2 State of the art
6.3 Cross layering with EOLSR
6.3.1 Routing and application cross layering
6.3.2 Routing and MAC cross layering
6.3.3 Routing and energy management cross layering
6.4 Cross layering with SERENA
6.4.1 SERENA and application layer cross layering
6.4.2 SERENA and MAC layer cross layering
6.5 Synthesis
6.6 Application to the OCARI project
6.6.1 Project description
6.6.2 The OCARI network and its architecture
6.6.3 NwCARI: Energy efficient network layer
6.7 Conclusion
7 Conclusion and perspectives
7.1 Conclusion
7.2 Perspectives