Energy Efficient Techniques in WSNs 

Get Complete Project Material File(s) Now! »

Network lifetime definition

The most challenging concern in WSN design is how to save node energy while maintaining the desirable network behavior. Any WSN can only fulfill its mission as long as it is considered alive, but not after that. As a consequence, the goal of any energy efficient technique is to maximize network lifetime. This latter depends drastically on the lifetime of any single node. However, in the literature, there is no consensus for the definition of network lifetime. The majority of authors use a definition suitable for the context of their work. This situation has driven toward a plethora of coexisting definitions. Based on the previous works on WSNs [Minet 2009, Dietrich 2009], we give an overview of the most common definitions.

Network lifetime based on the number of alive nodes

The definition found most frequently in the literature is the time during which all sensors are alive (also called n out of n in [Dietrich 2009], where n is the total number of sensors). The sink nodes are excluded from the set of nodes to reflect the assumption that sink nodes are more sophisticated and powerful devices. This lifetime is easy to compute since it does not take into account the topology changes. However, in dense networks where redundancy is present, this metric does not represent actually the lifetime evaluation. Therefore, the only case in which this metric can be reasonably used is if all nodes are of equal of importance and critical to network application.
A variant defines the network lifetime as the time until the fraction of alive nodes falls below a predefined threshold β [Tian 2002]. While this definition takes redundancy into account unlike the former, it does not accurately describe the correct running of data gathering applications where the failure of at most β % of sensors near the sink can prevent the sink to receive collected data.
In the context of clustering [Soro 2005, Blough 2002], authors define the network life-time as the time to failure of the first cluster head. However, in most works, researchers change cluster head dynamically to balance energy consumption.

Network lifetime based on coverage

Coverage reflects how well the network can detect an event in the monitored area. Therefore some works define the lifetime as the time during which the area of interest is covered by sensor nodes. However, even an 100% coverage is not sufficient when it does not ensure that collected data are delivered to the sink.

Network lifetime based on connectivity

This definition is based on the ability of the network to transmit data to a sink. This definition is similar to what has been proposed in context of ad hoc networks. In [Chiasserini 2002] authors define the lifetime as the minimum time when either the percentage of alive nodes or the size of the largest connected component of the network drops below a specific threshold.

Network lifetime based on application requirements

Some authors consider that network is alive as long as application functionalities are ensured. Kumar et al. [Kumar 2005] state « we define the lifetime of a WSN to be the time period during which the network continually satisfies the application require-ments ». Tian and Georganas [Tian 2002] suggest another definition: It is the time until « the network no longer provides an acceptable event detection ratio. » However, if no connectivity is guaranteed to report the event, this definition becomes irrelevant.
As a conclusion, network lifetime must take into account connectivity and coverage if needed by the application supported by WSN. Knowledge of the application requirements will enable WSN designers to refine the definition of network lifetime, leading to an evaluation more realistic and more pertinent for the application users.

Taxonomy of energy efficient techniques

We detail in this section the reasons of potential energy waste in a WSN. We then propose a taxonomy of existing energy efficient solutions, keeping in mind the resource constraint nature of sensors.

Reasons of energy waste

In WSNs, sensors dissipate energy while sensing, processing, transmitting or receiving data to fulfill the mission required by the application. The sensing subsystem is devoted to data acquisition. It is obvious that minimizing data generated will save energy of very constrained sensors. Redundancy inherent to WSNs will produce huge similar reporting that the net-work is in charge of routing to the sink. Experimental results confirm that communication subsystem is a greedy source of energy dissipation.
With regard to communication, there is also a great amount of energy wasted in states that are useless from the application point of view, such as [Minet 2009]:
• Collision: when a node receives more than one packet at the same time, these packets collide. All packets that cause the collision have to be discarded and the retransmission of these packets is required.
• Overhearing: when a sender transmits a packet, all nodes in its transmission range receive this packet even if they are not the intended destination. Thus, energy is wasted when a node receives packets that are destined to other nodes.
• Control packet overhead : a minimal number of control packets should be used to enable data transmissions.
• Idle listening: is one of the major sources of energy dissipation. It happens when a node is listening to an idle channel in order to receive possible traffic.
• Interference: each node located between transmission range and interference range receives a packet but cannot decode it.
As network lifetime has become the key characteristic for evaluating WSN, a panoply of techniques aimed at minimizing energy consumption and improving network lifetime, are proposed. We now give a taxonomy of these techniques.

Classification of energy efficient techniques

We can identify five main classes of energy efficient techniques, namely, data reduction, protocol overhead reduction, energy efficient routing, duty cycling and topology control.
1. Data reduction: focuses on reducing the amount of data produced, processed and trans-mitted. In the production step, sampling based and prediction based techniques are proposed. The former exploits the spatio-temporal correlation between samples to make data collection rate dynamic [Anastasi 2009, Willett 2004, Marbini 2003, Jain 2004]. The latter, given the past history of readings and based on the observation that sensors are capable of local computation, predicts the set of readings and so the sensing device can be turned off [Goel 2001, Gedik 2007, Goel 2006].
In the processing and communication step, different operations on collected data have been introduced during the processing step to handle the scarcity of energy resources in a WSN. For instance, data compression [Kimura 2005] and data aggregation are examples of such techniques. For data aggregation, we can distinguish Cluster based structure [Heinzelman 2000, Heinzelman 2002, Akkaya 2005], Tree based [Zhang 2004b, Zhang 2004a] and Structure-less solutions [Fan 2006a, Fan 2006b].
2. Protocol overhead reduction: the aim of this technique is to increase protocol efficiency by reducing the overhead. Different techniques exist. These techniques can be subdi-vided into 1) adaptive transmission period depending on WSN stability or distance to the information source [Mahfoudh 2008, Pei 2000]. Indeed, communication protocols often resort to periodic message exchanges. These periodic messages are sources of over-head in WSNs 2) cross-layering with the upper and lower layers to optimize network re-sources while meeting application requirements [van der Schaar 2005] and 3) optimized flooding to avoid unnecessary retransmissions [Wu 1999, Dai 2004, Ingelrest 2007]. In-deed, flooding is a widely used technique in WSNs for location discovery, route estab-lishments, querying, etc. Hence, it is a very expensive operation for battery powered sensors.
3. Energy efficient routing: routing protocols should be designed with the target of max-imizing network lifetime by minimizing the energy consumed by the end-to-end trans-mission and avoiding nodes with low residual energy. Some protocols are opportunistic, taking advantage of node mobility or the broadcast nature of wireless communications to reduce the energy consumed by a transmission to the sink. Others use geographical coordinates of nodes to build a route toward the destination. Others build a hierarchy of nodes to simplify routing and reduce its overhead. Multipath routing protocols use multiple routes to achieve load balancing and robustness against routes failures. Fi-nally, data centric protocols send data only to interested nodes in order to spare useless transmissions.
4. Duty cycling: duty cycling means the fraction of time nodes are active during their lifetime. The periods during which nodes sleep or are active should be coordinated and accommodated to specific applications requirements. These techniques can be fur-ther subdivided. High granularity techniques focus on selecting active nodes among all sensors deployed in the network. Low granularity techniques deal with switching off (respectively on) the radio of active nodes when no communication is required (respec-tively when a communication involving this node may occur). They are highly related to the medium access protocol.
5. Topology control : it focuses on reducing energy consumption by adjusting transmission power while maintaining network connectivity. A new reduced topology is created based on local information.
The taxonomy of energy efficient techniques is illustrated in Figure 2.1.
Figure 2.1: Taxonomy of energy efficient techniques
We now focus on energy efficient routing and duty cycling that are closer to our work.

Energy efficient routing protocols

The energy constraints of sensor nodes raise challenging issues on the design of routing proto-cols for WSNs. Proposed protocols aim at load balancing, minimizing the energy consumed by the end-to-end transmission of a packet and avoiding nodes with low residual of energy. In this section, we give a classification rather than an exhaustive list of energy efficient routing protocols. Our classification of energy efficient routing protocols generalizes the one given in [Akkaya 2005]: data centric protocols, hierarchical protocols, geographical and opportunistic protocols. We now describe each category in more details.
1. Data centric protocols: These protocols target energy saving by querying sensors based on their data attributes or interest. They make the assumptions that data deliv-ery is described by a query driven model. Nodes route any data packet by looking at its content. Mainly, two approaches were proposed for interest dissemination. The first is SPIN [Blass 2008] where any node advertises the availability of data and waits for requests from interested nodes. The second is Directed Diffusion (DD) [Akkaya 2005] in which sinks broadcast an interest message to sensors, only interested nodes reply with a gradient message. Hence, both interest and gradients establish paths between sink and interested sensors. Many other proposals have being made such as rumor rout-ing, gradient based routing, COUGAR, CADR. See [Akkaya 2005] for a comprehensive summary.
2. Hierarchical protocols: Clustering protocols have been developed in order to improve scalability and reduce the network traffic towards the sink. Cluster based protocols have shown lower energy consumption than flat protocols despite the overhead introduced by cluster construction and maintenance. One of the pioneering hierarchical routing protocol is LEACH [Akkaya 2005]. In this protocol, sensors organize themselves in local clusters with one node acting as a cluster head. To balance energy consumption, a ran-domized rotation of cluster head is used. PEGASIS is another example of hierarchical protocol [Akkaya 2005]. It enhances LEACH by organizing all nodes in a chain and letting nodes to alternate the head of the chain. TEEN is both data centric and hier-archical. It builds clusters of different levels until reaching the sink. The data centric aspect is outlined by using two thresholds for sensed attributes: hard threshold and soft threshold. The former will trigger the sensor node to transmit to its cluster head. Another transmission is only permitted when the attribute value becomes higher than the soft threshold. This mechanism can drastically reduce the number of transmissions and thus energy consumption. Since TEEN is not adaptive to periodic sensor data reporting, an extension called APTEEN [Akkaya 2005] has been proposed.
3. Geographical protocols: Many non geographical routing protocols suffer from scal-ability and efficiency restrictions because they depend on flooding for route discovery and updates. Geographical protocols take advantage of nodes location information to compute routes. In [Akkaya 2005], authors propose an energy-aware protocol called GEAR consisting of two phases. In the first phase, the message is forwarded to the target region. In the second phase, the message is forwarded to the destination within the region.
The basic idea behind GEAR is to enhance DD by sending the interests only to a certain region rather than the whole network. GAF [Akkaya 2005] ensures energy efficiency by building virtual grids based on location information of nodes. Only a single node needs to be turned on in each cell, other nodes are kept in sleeping state. SPEED [Akkaya 2005] ensures load balancing among multiple routes with its non de-terministic forwarding module.
4. Opportunistic protocols: The crucial idea of opportunistic routing is to exploit 1) the broadcast nature and space diversity provided by the wireless medium or 2) node mobility. We distinguish two subclasses of opportunistic routing:
• Medium broadcast nature and space diversity based protocols:
These techniques maintain multiple forwarding candidates and judiciously decide which sets of nodes are good and prioritized to form the forwarding candidate set. In [Zeng 2007], authors highlight how these protocols achieve better energy efficiency.
• Mobility based protocols:
By introducing mobility in WSN, network lifetime can be extended. Indeed, mobile nodes can move to isolated parts of the network and hence connectivity is again reached. Several works merging routing and mobility have demonstrated that this class of routing protocol exhibits smaller energy consumption when compared to classical techniques.
• Mobile sink based protocols: the authors of [Luo 2005] propose a framework where mobility of the sink and routing are joint. Their proposed routing strategy offers 500 % improvement of network lifetime by using combination of sink trajectory and shortest paths. In [Bhardwaj 2002, Čagalj 2002], a learning-based approach is proposed to efficiently and reliably route data to a mobile sink. Sensors in the vicinity of the sink learn its movement pattern over time and statistically characterize it as a probability distribution function. In [Papadimitriou 2006], authors demonstrate that maximum lifetime can be achieved by solving optimally two joint problems: a scheduling problem that determines the sojourn times of the sink at different locations, and a routing problem in order to deliver the collected data to the sink in an energy efficient way.
• Mobile relay based protocols: these techniques have been introduced in the context of opportunistic networks [Pelusi 2006] where the existence of an end-to-end rout-ing path is not usually ensured. Thus, any node can be used as an intermediate hop for forwarding data closer to the destination. In [Shah 2003], authors assume the existence of mobile entities (called mules) present in the monitored area. Mules pick up data from the sensors when in close range, buffer it, and drop off the data to wired access points. Their model integrates a random walk for mobility pattern and incorporates system variables such as the number of mules, sensors and access points respectively. In [Ou 2007] data mules accommodate their trajectories for data delivery based on only local information.
5. Multipath protocols: Multipath routing protocols use multiple paths to forward data packets to the sink. Thus, they alleviate congestion in comparison with single-path routing protocols. For instance, CBMPR [Zhang 2007], targets low interferences. It combines cluster-based routing and multipath routing. Each path routing just passes through cluster heads. Consequently, interferences caused by intermediate nodes are avoided. RPL [Winter ] is another multipath energy efficient routing protocol. The basic component of RPL is the Destination Oriented DAG which is a DAG oriented at a single sink. RPL supports only unicast traffic.

Table of contents :

1 General Introduction 
1.1 Background and motivations
1.2 Main contributions
1.3 Manuscript organization
I State of the Art 
2 Energy Efficient Techniques in WSNs 
2.1 Introduction
2.2 Network lifetime definition
2.3 Taxonomy of energy efficient techniques
2.3.1 Reasons of energy waste
2.3.2 Classification of energy efficient techniques
2.4 Energy efficient routing protocols
2.5 Duty cycling
2.6 Conclusion
3 Multi channel Assignment Protocols in WSNs 
3.1 Introduction
3.2 Issues in multichannel communications and specificities of WSNs
3.3 Particularities of channel assignment strategies in WSNs
3.3.1 Classification of mesh channel assignment strategies
3.3.2 Applicability of mesh channel assignment strategies
3.4 Network architecture for multichannel communication in WSN
3.4.1 A two-level architecture
3.4.2 A three-level architecture
3.4.3 A three-level mesh architecture
3.5 Network model for a multichannel WSN
3.5.1 Radio propagation
3.5.2 Interferences
3.5.3 Connectivity
3.6 Classification of existing multichannel assignment protocols in WSNs
3.6.1 Categories of channel assignment method
3.6.2 Channel selection policy
3.6.3 Channel assignment methods
3.6.4 Discussion
3.7 Cross-layer design for multichannel allocation and routing
3.8 Taxonomy proposed
3.9 Conclusion
II Joint Multi path Routing and Scheduling in Multi channel WSNs 
4 Lower Bounds for Convergecast: Theoretical Study 
4.1 Introduction and motivations
4.2 Network models and assumptions
4.2.1 System model
4.2.2 Definitions
4.2.3 Assumptions
4.2.4 Modeling interferences for data gathering
4.2.5 Notations
4.3 Theoretical bounds for homogeneous traffic
4.3.1 Linear networks
4.3.2 Tree networks
4.3.3 Optimal schedule
4.4 Theoretical bounds for heterogeneous traffic
4.4.1 Without immediate acknowledgment
4.4.2 With immediate acknowledgment
4.5 Conclusion
5 MODESA: an Optimized Multichannel Slot Assignment for Raw Converge-cast in WSNs 
5.1 Introduction
5.2 State of the art
5.3 Multichannel slot assignment problem
5.3.1 Formalization of the problem
5.3.2 Illustrative examples
5.4 MODESA: Multichannel Optimized DElay time Slot Assignment
5.4.1 Principles
5.4.2 The MODESA algorithm
5.4.3 Optimality of MODESA for homogeneous traffic
5.5 Performance evaluation of MODESA
5.5.1 MODESA with homogeneous traffic
5.5.2 MODESA with heterogeneous traffic
5.5.3 Impact of additional links
5.6 MODESA improvement
5.6.1 Channel allocation strategy
5.6.2 Multipath transmission scheduling
5.6.3 Different topologies on different channels
5.7 Conclusion
6 MUSIKA: a MUlti-SInk Slot Assignment for Convergecast in Multichannel WSNs 
6.1 Introduction
6.2 State of the art
6.3 Network model and problem formalization
6.3.1 Network model
6.3.2 Multi-sink multichannel convergecast problem formulation
6.4 MUSIKA: MUlti-SInK slot Assignment
6.4.1 Principles
6.4.2 Algorithm
6.5 Illustrative example
6.6 Performance evaluation
6.7 Conclusion
III Adaptivity and Scalability of Joint Time Slot and Channel Assignment 
7 An Adaptive Strategy for an Optimized Collision-Free Slot Assignment in Multichannel Wireless Sensor Networks 
7.1 Introduction
7.2 State of the art
7.3 Adaptive multichannel slot assignment
7.3.1 Definitions
7.3.2 Assumptions
7.3.3 Network model
7.3.4 Theoretical bounds on the number of extra slots for a raw data convergecast
7.3.5 AMSA: Proposed solution
7.3.6 Illustrative example
7.4 Performance evaluation
7.4.1 Retransmission oriented experiments
7.4.2 Temporary change in the application needs-oriented experiments
7.5 Conclusion
8 A Distributed Joint Channel and Time Slot Assignment for Convergecast in Multichannel WSNs
8.1 Introduction
8.2 State of the art
8.3 WAVE: a distributed time slot and channel assignment for convergecast in WSNs137
8.3.1 WAVE in centralized mode
8.3.2 WAVE in distributed mode
8.3.3 Properties
8.3.4 Equivalence of the two modes of WAVE
8.3.5 Message complexity in the two modes of WAVE
8.4 DiSCA: an optimized version of WAVE
8.4.1 Principles
8.4.2 DiSCA distributed algorithm
8.5 Comparative performance evaluation of WAVE and DiSCA
8.5.1 Homogeneous traffic
8.5.2 Heterogeneous traffic
8.6 Conclusion
9 Conclusion and Perspectives 
9.1 Synthesis
9.2 Perspectives
List of Publications

GET THE COMPLETE PROJECT