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 traﬃc.
• 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 eﬃcient techniques
We can identify five main classes of energy eﬃcient techniques, namely, data reduction, protocol overhead reduction, energy eﬃcient 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 oﬀ [Goel 2001, Gedik 2007, Goel 2006]. In the processing and communication step, diﬀerent 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 eﬃciency by reducing the overhead. Diﬀerent 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 eﬃcient 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 oﬀ (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.
Energy eﬃcient 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 eﬃcient routing protocols. Our classification of energy eﬃcient 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 Diﬀusion (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 traﬃc 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 diﬀerent 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 suﬀer from scal-ability and eﬃciency 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 eﬃciency 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 eﬃciency.
• 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 oﬀers 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 eﬃciently 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 diﬀerent locations, and a routing problem in order to deliver the collected data to the sink in an energy eﬃcient 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, buﬀer it, and drop oﬀ 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.
Issues in multichannel communications and specificities of WSNs
The tremendous attraction of multichannel communication is the capacity to operate on multiple channels in order to 1) avoid interferences, specially high in dense networks or 2) increase network throughput. Multichannel communications in WSNs are challenging. On the one hand, they must be implemented in devices that have reduced resources (processing, storage, energy). On the other hand, sensor nodes are small devices whose cost per unit should remain small. For these reasons, sensor nodes are usually equipped with a single radio and simple multichannel protocols will be favored.
Compared to single channel communication, multichannel communication rises new prob-lems or makes existing ones more complex. Some of them are shared by any wireless network:
I1) Multichannel deaf node: A transmitter wrongly considers a destination node as un-reachable because it does not get any response to its requests. This occurs when the destination node is tuned to another channel while the transmitter is trying to commu-nicate with it.
I2) Multichannel hidden node: In a single channel condition, a hidden node problem may occur in a configuration with at least three nodes, where at least two nodes are out of each other radio range. In a multichannel environment, the hidden node problem occurs when the node misses an RTS/CTS exchanged on one channel while listening on another, causing the hidden terminal problem despite the use of RTS/CTS signaling [So 2004b].
I3) Internal interferences: Due to the broadcast nature of the wireless medium, the per-formance of a multichannel wireless network is drastically limited by interferences due to concurrent transmissions on the same or adjacent channels in the same network [Raman 2009]. Within a WSN, we can distinguish two types of internal interferences:
• inter-channel interferences: where there exists at least one node in the WSN where two transmissions on two diﬀerent (but partially overlapping) channels interfere with each other.
• intra-channel interferences: where there exists at least one node in the WSN where two transmissions on the same channel interfere with each other. Notice that such interferences also exist in single channel communications.
I4) External interferences: 802.15.4 is not the only wireless network operating in the un-licensed band 2.4 GHz. There are WiFi, Bluetooth to name a few. Furthermore, external electromagnetic sources may create perturbations in this frequency band, like for instance electric appliance causing microwave radiation, radar polluting the 802.15.4 band. As depicted in Figure 3.1, only four channels of 802.15.4 do not overlap with WiFi channels.
Table of contents :
1 General Introduction
1.1 Background and motivations
1.2 Main contributions
1.3 Manuscript organization
2 EnergyEfficientTechniques inWSNs
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
3 Multi channel Assignment Protocols inWSNs
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.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.7 Cross-layer design for multichannel allocation and routing
3.8 Taxonomy proposed
II Joint Multipath Routing and Scheduling in Multichannel 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.4 Modeling interferences for data gathering
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
5 MODESA: an Optimized Multichannel Slot Assignment for Raw Converge- cast in WSNs
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.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
6 MUSIKA: a MUlti-SInk Slot Assignment for Convergecast in Multichannel WSNs
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.5 Illustrative example
6.6 Performance evaluation
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.2 State of the art
7.3 Adaptive multichannel slot assignment
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
8 A Distributed Joint Channel and Time Slot Assignment for Convergecast in Multichannel WSNs
8.2 State of the art
8.3 WAVE: a distributed time slot and channel assignment for convergecast in WSNs
8.3.1 WAVE in centralized mode
8.3.2 WAVE in distributed mode
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.2 DiSCA distributed algorithm
8.5 Comparative performance evaluation of WAVE and DiSCA
8.5.1 Homogeneous traffic
8.5.2 Heterogeneous traffic
9 Conclusion and Perspectives
A List of Publications
B.1 Contexte et motivations
B.2 Allocation conjointe de slot et canaux dans les RCsF
B.2.1 Bornes théoriques
B.3 MODESA: algorithme optimisé pour l’allocation conjointe de slots temporels et canaux
B.3.1 Optimalité de MODESA
B.3.2 Evaluation de performances
B.4 MUSIKA: algorithme d’allocation conjointe de slots et de canaux pour les RCsF multicanaux multi-puits
B.5 Adaptabilité et passage à l’échelle pour l’allocation conjointe des slots temporels et canaux
B.5.1 Stratégie adaptative pour l’allocation conjointe de slot temporel et canaux174
B.6 Allocation distribuée conjointe de slots et canaux pour les applications collecte de données
B.6.1 WAVE: algorithme distribué d’allocation conjointe de slots temporels
et canaux pour les applications de collecte de données
B.6.2 DiSCA: Une version optimisée de WAVE
B.6.3 Evaluation comparative de WAVE et DiSCA
B.7 Conclusion et perspectives