Optimal Probabilistic Energy Aware Routing Protocol

Get Complete Project Material File(s) Now! »

Wireless Sensor Networks and Internet of Things

With the advance of numerous technologies including sensors, actuators, embedded computing and cloud computing, and the emergence of a new generation of cheaper, smaller wireless devices,many objects, or things in our daily lives are becoming wirelessly interoperable with attached miniature and low-powered or passive wireless devices. The Wireless World Research Forum predicts that by the end of 2017, there will be 7 trillion wireless devices serving 7 billion people [59] (i.e., 1000 devices/person). This ultra large number of connected things or devices will form the Internet of Things (IoT).
The IoT term has been dened in dierent ways by dierent authors. Vermesan et al. [57] dene the IoT as simply an interaction between the physical world and digital one. The digital world interacts with the physical world using a plethora of sensors and actuators. Another denition is proposed by Peña-López et al. [58] where the IoT is proposed to be a paradigm in which computing and networking capabilities are embedded in any kind of conceivable object. We use these capabilities to query the state of the object and to change its state if possible. Shortly, the IoT refers to a new kind of world where almost all the devices and appliances that we use are connected to a network. We can use them collaboratively to achieve complex tasks that require a high degree of intelligence.
While IoT does not assume a specic communication technology, wireless communication technologies play a major role, and in particular, WSNs are the key technologies for many applications and many industries. The small, rugged, inexpensive and low powered wireless sensors will bring the IoT even to the smaller objects installed in all kind of environments, at reasonable costs. So, WSNs are like the eyes and ears » of the IoT, being the bridge that connects the real world to the digital world.

The WSN Network Architecture

WSNs can be dened as a self-congured and infrastructure-less wireless network able to monitor physical or environmental conditions and to cooperatively pass their data through the network to a main location or sink where the data can be observed and analysed. A sink or base station acts like an interface between users and the network. A generic WSN architecture is depicted by Figure 2.2. WSN diers from the traditional wireless networks due to its limited resources (power, processing and memory), low node reliability and dynamic network topology. Thus, the routing between the sensors and the sink node, as well as the radio duty cycle play a very important role in WSNs. From a layered view, MAC determines the channel access delay and utilization and also the energy consumption (active-sleep mode timing) through a duty cycle mechanism.
On the other hand, the network layer should provide a protocol with low end-to-end multi-hop transmission time, which also reects the enery consumption. Thus, QoS in WSNs is provided through a set of measurable service parameters such as delay, jitter, available bandwidth, and packet loss. Beside these metrics, network lifetime is also to be included. Cross-layer design is adoped to achieve a joint optimization. It aims to improve the performace of a communication protocol by taking into account parameters of other layers.

Energy Ecient Techniques at MAC and Network Layers

From the view of upper layer protocols, the sensors are usually assumed to have four states and no cost for transition between the states [66]:
ˆ Transmission: processing for address determination, packetization, encoding, framing, queuing. ˆ Reception: Low-noise amplier, ltering, detection, decoding, error detection, address check, reception even if a node is not the intended receiver.
ˆ Idle listening: Similar to reception except that the signal processing chain stops at the detection. ˆ Sleeping: a low power level allowing the sensor node to stay alive.
Other researchers try to take more realistic factors into consideration [67] and some assume that since the nodes are expected to receive, transmit and listen at full power, for which current demands are approximately the same, two states can represent eciently the radio operation [68]: active and sleep mode.

Energy Saving Approaches

We can identify dierent energy saving mechanisms which are categorized as follows:
ˆ Energy ecient routing at Network layer : routing protocols can be designed with the target of maximizing network lifetime by minimizing the energy consumed by the endto- end transmission and to avoid using nodes with low residual energy. Some protocols consider energy as a metric for path selection. By doing so, routing algorithms can select the next hop by focusing not only on the shortest path but also on its residual energy [33], [34].
ˆ Duty cycling at MAC layer : duty cycling is 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 the specic application requirements. Duty cycle techniques can be further 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 (respectively when a communication involving this node may occur). They are highly related to the medium access protocol [23].
ˆ Multipath routing: single path routing rapidly drains energy of nodes on a selected path and when the node drains out of power, a new route must be reconstructed. Multipath routing in contrast, alternates forwarding nodes thereby balancing energy among the nodes. It enables the network to recover faster from failure and enhances the network reliability [18].
ˆ Relay node placement: the early stage depletion of nodes can be avoided by the even distribution of nodes by placing a few relay nodes, i.e. nodes that do not have sensor functions but they are used only for routing. This improves the energy equilibrium between nodes, coverage, and capacity and avoids sensor hot spots [77], [76].

READ  Testing the presence of a deterministic signal in a subspace cone 

Multiple-Metric Routing Algorithms

Some routing algorithms handle the problem of having multiple metrics through the use of cost functions which regroup all metrics into a single function. This has the advantage of transforming the problem into a single-objective problem which is easier to solve. Nevertheless, this approach is not possible when the metrics have dierent natures. Moreover, if constraints are taken individually, using cost functions may lead to paths which violate some constraints.
Constraints are metrics with a threshold of upper/lower value and objectives are desired attributes of the network. QoS metrics can be either constraints or objectives. But, in many protocols there is a maximum threshold for certain metrics but the protocol works trying to minimize these metrics, so there is no guarantee that this constraint will be under a threshold.

Hop-Constrained Energy-Aware Routing

In [49] the authors propose a linear programming model to solve the hop-constraint energy-aware routing in WSNs. They split the lifetime into equal periods of time, named rounds and they solve the problem in each round. The objective function minimizes the maximum energy spent by any node. They propose a ow-based routing protocol which makes use of the ow information. The ow is translated as capacity on the links. Before every round, the base station solves the linear program and transmits the routing information to the sensor nodes.

Table of contents :

Chapter 1 General Introduction
1.1 Background and motivations
1.2 Main Contributions
1.3 Manuscript Organization
Partie I State of the Art
Chapter 2 Context
2.1 Wireless Sensor Networks and Internet of Things
2.2 Applications in WSNs
2.3 WSN Architecture and Protocols
2.3.1 The Sensor Architecture
2.3.2 The WSN Network Architecture
2.4 QoS Metrics in WSNs
2.4.1 Network Lifetime
2.4.2 Type of QoS Metrics
2.5 Energy Ecient Techniques at MAC and Network Layers
2.5.1 Energy Consumption Model
2.5.2 Sources of Energy Waste
2.5.3 Energy Saving Approaches
2.6 Conclusion
Chapter 3 Routing Protocols in WSNs
3.1 Introduction
3.2 Single-Metric Routing Protocols
3.2.1 Hop Count
3.2.2 Link Quality
3.2.3 Residual Energy
3.2.4 Geographical Routing: GPSR
3.2.5 Distance Progress
3.2.6 ETX
3.2.7 RPL
3.2.8 Discussion
3.3 Multiple-Metric Routing Algorithms
3.3.1 SAMCRA
3.3.2 A* Prune
3.4 Multiple-Metric Routing Protocols
3.4.1 Geographical Routing: GEAR, SPEED, RPAR
3.4.2 Single Aggregation of multiple metrics
3.4.3 Fuzzy Logic
3.4.4 Energy Aware Routing
3.4.5 Discussion
3.5 Network Flow-based Routing
3.5.1 Maximum lifetime energy routing
3.5.2 Maximum lifetime data gathering
3.5.3 Bounds of lifetime
3.5.4 Hop-Constrained Energy-Aware Routing
3.5.5 Discussion
3.6 Conclusion
Partie II Contributions
Chapter 4 Optimal Probabilistic Energy Aware Routing Protocol
4.1 Introduction
4.2 Problem description
4.2.1 Assumptions
4.3 System Modeling
4.3.1 Objective Function
4.4 OPEAR: An Optimal Probabilistic Energy-Aware Routing protocol
4.4.1 Optimal Probabilities
4.4.2 Energy Model
4.5 Experimental evaluation
4.5.1 Dataset design
4.5.2 Emulation Scenario
4.5.3 Results
4.6 Conclusion
Chapter 5 Operator Calculus based Routing Protocol
5.1 Introduction
5.2 Operator Calculus on Graphs
5.2.1 Motivating Example and Nilpotent Adjacency matrix
5.2.2 Constraint Algebra
5.3 Path selection algorithms
5.3.1 Centralized path selection algorithm
5.3.2 Complexity evaluation of OC algorithm and comparison with SAMCRA 60
5.3.3 Distributed path selection algorithm
5.4 Implementation of OCRP
5.4.1 General description of OCRP
5.4.2 Data broadcast protocol
5.4.3 Other implementation details
5.5 Performance analysis
5.5.1 First Experiment
5.5.2 Second Experiment
5.6 Conclusions
Chapter 6 Overall Conclusions and Future Work
6.1 Summary of the Results and Final Contributions
6.2 Future Work
Chapter 7 List of Publications


Related Posts