Project Topics
Get Complete Project Material File(s) Now! »
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 efficient 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 efficiency.
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 consists 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 traffic 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 traffic 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 efficiency 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 eception 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 different slots. This randomized algorithm has the advantage of not depending on the number of network nodes but at the cost of an asymptotic convergence.
In the following, wa present the third energy efficient strategy which deals with topology control.
Topology control by tuning node transmission power
Topology control algorithms have been proposed to reduce energy consumption and improve network capacity, while maintaining network connectivity. The key idea of topology control is that instead of transmitting using the maximal power, each node adjusts its power transmission. Thus, energy dissipated in transmission is reduced and a new network topology is created. Topology control algorithms can have several goals:
Reduce energy consumption (power grows at least quadratically with distance).
Reduce interference.
Improve spacial reuse and mitigate the MAC-level medium contention.
The solutions are generally based on one of the three following algorithms minimizing the number of edges in the network graph while ensuring connectivity:
RNG, Relative Neighborhood Graph, [40], removes any edge directly connecting two nodes if there exists a path of two hops or more between them.
MST, Minimum Spanning Tree, [41], transforms the network graph in a minimum energy broadcast tree rooted at a given source node giving the shortest path to any other node; only the energy dissipated in transmission is taken into account.
LMST, Local Minimum Spanning Tree, [42], is a localized algorithm where each node computes its own MST in its neighborhood and only retains those one-hop neighbors on the tree as its neighbors in the final topology. The network topology under LMST is all nodes with their individually perceived neighbors relations.
In [2], the idea is to reduce the transmission range d of every node to minimize the energy dissipated
in transmission while keeping a connected topology. It is shown that there exists an optimal transmission range which minimizes energy consumption. But this range depends on the communication type (broadcast or unicast). This solution is localized and distributed, but it does not take into account energy dissipated by reception.
In [3], the TCH (Topology Control with Hitch-hiking) problem is addressed. Hitch-hiking takes advantage of a physical layer that allows combining partial messages containing the same information to decode a complete message. The goal of TCH is to obtain a strongly connected topology minimizing the energy dissipated in transmission. The TCH problem is NP-complete. To resolve this problem, a distributed solution DTCH (distributed TCH) based on 2-hop neighbors information is proposed: each node i increases its transmission power to contribute to the coverage of its 2-hop neighbors j using hitch-hiking. Thus, the i’s 1-hop neighbors can reduce their transmission power while keeping a strongly connected network. This solution reduces the complexity of TCH to a polynomial complexity.
An Adaptive Transmission Power Control (ATPC) is proposed in [43]. The goal of ATPC is to achieve energy efficiency and guarantee link quality between neighbors. ATPC allows each node to know the optimal transmission power level to use for each neighbor while maintaining a good link quality. This power is adjusted adapting to spatial and temporal factors by collecting the link quality history. Results show that this protocol is more reliable and energy efficient than the one the maximum transmission power level protocol and also the one using the minimum transmission power level that allows them to reach their neighbors.
In the next section, we will the last energy efficient strategy which reduces the amount of information transferred to spare energy.
Reduce the amount of information transferred
The last energy efficient strategy consists in aggregating information (e.g.; in a data gathering application, a node sends to its parent a single message containing the values transmitted by its children), reducing wasteful transmissions (e.g.; transmission of an information that is already known by the receiver or in which it has no interest) or tuning the refreshment period of control messages (e.g.; neighborhood discovery, topology dissemination, data gathering tree structure). These solutions can be classified in three classes:
Information aggregation.
Optimized flooding.
Tuning the information refreshment frequency.
In the following, we present each class by quoting some works focusing in each class.
Tuning the information refreshment frequency
Energy can also be spared by decreasing the frequency of information refreshment in the network. As a counterpart, the information maintained in the network is less accurate. An interesting tradeoff has been found with the fish eye principle: a fish sees very clearly only what is close, its view strongly decreases with distance. In the Fish eye routing protocol, [44], the information associated with far nodes is refreshed less frequently than this associated with close nodes. This principle has also been applied to scalable extensions of OLSR, [45].
Cross layering optimization
We can notice that whatever the category of energy efficient strategy considered, solutions can be generic and applied whatever the application (e.g. TRAMA) but not optimal for a given application, or on the contrary be optimized for a specific application (e.g. FLAMA) but of limited applicability. In between these two types of solutions, cross-layering, [64], can help to design generic solutions able to take into account application specificities to maximize network lifetime.
The specificities of wireless ad hoc and sensor networks include:
dynamically changing network conditions due to mobility or versatility of the propagation conditions on the physical medium.
network resources of limited capacity: limited bandwidth, limited amount of energy for battery operated nodes, limited processing capability, limited memory, etc.
radio interferences, etc.
bring new constraints in designing protocols for wireless sensor networks. These protocols must be energy efficient and dynamically adaptive. Moreover, they must satisfy the quality of service desired by the applications. To meet these requirements a cross-layer protocol design that supports adaptivity and optimization across multiple layers of the protocol stack is needed.
In [53], using a cross layer approach, authors study the tradeoff between network lifetime maximization and rate allocation problem by formulating these two problems as a constrained maximization problem. Using Lagrange dual decomposition, the original problem is vertically decomposed into three subproblems: 1) a rate control problem at the transport layer, 2) a contention resolution problem at the MAC Layer, and 3) a cross-layer energy conservation problem. Two fully distributed algorithms are derived for the first two subproblems. For the third subproblem, first they directly derive a partially distributed algorithm, and then propose a fully distributed approximation algorithm using network utility maximization framework.
Nama et al. [54, 55] characterized the tradeoff between maximizing the application performance and lifetime by considering a cross-layer design problem in a wireless sensor network with orthogonal link transmissions, which jointly maximized the network utility and lifetime. The idea is to compute an optimal set of source rates, network flows, and radio resources at the transport, network, and radio resource layers respectively, while jointly maximizing the network utility and lifetime. They show that the cross-layer optimization problem decomposes both horizontally (across nodes) and vertically (across different layers in the protocol stack) into simpler subproblems allowing a fully distributed solution.
Analysis of node energy consumption distribution
We focus on the distribution of the node energy consumption in a wireless ad hoc network, in order to highlight the main energy costs and then to propose a strategy for improving the network energy efficiency.
In the following we will analyze the node energy consumption distribution in wireless ad hoc and sensor networks. In other words, we will quantify the energy dissipated in transmitting, receiving, overhearing, idle listening and interference during network lifetime. The network lifetime is defined as the time of the first network partition. In other words, it is the time when a flow can no longer reach its destination.
Table of contents :
LIST OF FIGURES
LIST OF TABLES
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
