Project topics and materials
Get Complete Project Material File(s) Now! »
Protocol Stack Architecture for WSNs
[ASSC02a] and [OB06] show that the protocol architecture of WSNs consists of physical layer, data link layer, network layer, transport layer, application layer, task, mobility and power management planes as shown in Figure 2.2. Physical layer is responsible of the type modulation used and data communication. The network layer is responsible to route the data through the network and manages the network topology with the help of the transport layer [AFS09]. The data link layer is responsible of assigning communication channels between sensors [AFS09]. The MAC protocol includes in the data link layer helps to reduce the energy consumption of sensors. The transport layer is responsible of data flow depending on applications [OB06] and [AFS09]. The task management plane is responsible to manage and synchronize the activities among sensors [ASSC02a]. The mobility management plane is responsible to manage the mobility of sensors [OB06]. The power management plane manages the energy consumption of sensors among different activities. It uses the synchronization mechanisms to avoid implosion in order to reduce the energy consumption of sensors. More informations can be found in [AFS09].
In the following Section, 2.4, we present the state of the art and recent pro- posals for data aggregation schemes.
Data Aggregation in WSNs
The idea of data aggregation is to combine the data from various sensors more efficiently by eliminating redundant data. [FRWZ07] and [RV06] classify data aggregation techniques into tree, cluster, mesh, chain and hybrid mechanisms.
Tree-based mechanisms
In a tree-based, in which we focus in this thesis, a tree is built out from the sink by electing some special sensors to work as aggregation points. Data is aggregated at intermediate sensors level by level along the tree and forwarded towards the main sink. This mechanism is suitable for applications which involve in-network data aggregation, such as environmental monitoring, where the maximum data values received by the sink provide the most useful information [FRWZ07]. Tree-
based data aggregation has some limitations concerning its robustness and main- tenance cost. Whenever a packet is lost at a given level of the tree due to link or sensor failures, data coming from the subordinated levels of the tree is lost. A further issue is high cost of maintaining the tree in dynamic networks. Data aggregation using a tree structure has been well-studied in research. [CLRS01] present Breadth First Search (BFS) and Depth-First Search (DFS) as two algorithms to explore the graph by building a tree. DFS is a recursive algorithm that explores each branch of the graph to the greatest extent possible. After all links have been explored, it backtracks until it founds a sensor with an unexplored neighbour. In the BFS algorithm, sensor nodes are checked in the order that they are discovered, by maintaining a queue that stores all nodes that have been discovered but not yet processed. At each step, the node at the front of the queue is processed. For example, when the node S is processed, all newly-discovered reachable nodes are added to the end of the queue. At each step of DFS and BFS, the node with greater identifier is processed first. Recall that DFS and BFS explore each link and sensor in the graph exactly once, so the running time of both algorithms is O(S + E), where S and E are the number of sensors and links respectively. However, the memory usage of BFS depends on the density of the graph, while that of DFS depends on the depth of the graph. [CL02] propose Connected Dominating Set (CDS) to reduce the energy use in the routing by minimizing the number of dominating nodes (parents) necessary to transmit the data. A CDS builds a tree in the graph by locally electing a set of parents in order to minimize the transmission of routing data. The broadcast tree of CDS is constructed incrementally out from the sink via a beacon mes- sage, by electing parents and leaves based on Id of nodes. Thus, sensors with the highest identifier are elected as parents, and sensors with the lowest identi- fier are elected as leaves [GP09]. A CDS of the graph is a set of parents such that any two sensor nodes can communicate with each other via a series of adja- cent sensors in the set [FMLE11b]. The broadcast tree defined by the CDS can serve as the communication backbone in the graph. [FLS06] present an approach that uses a spatial aggregation (when the values generated by nearby sensors are similar), and temporal aggregation (when the data sensed by sensors changes slowly over time), to find correlation between sensed data in order to reduce its quantity and hence avoid congestion. [SBLC03] shows that these techniques are especially useful in monitoring applications. [CMT05] propose an additive stream cipher that allows efficient aggregation of encrypted data. The cipher is used to compute statistical values such as mean, variance and standard deviation of sensed data, while achieving significant bandwidth gain. However, they do not address the issue of CPU resource constraint. [PHS00] propose a distributed
architecture together with their Border Gateway Reservation Protocol (BGRP) for inter-domain resource reservation. BGRP builds a sink tree for each of the stub domains. This reduces control state memory requirements by aggregating reservations. Consequently, the amount of information that must be propagated between nodes is reduced, so conserving resources. [KEW02b] evaluate the impact of network density on the energy costs associated with data aggregation.
However, the time complexity remains unknown in the multi-hop case. [YLL09] propose the first distributed aggregation model based on maximal independent sets to minimize data latency. [GND+05] propose an approach based on the construction of CDSs. The sensors belonging to the broadcast are connected in such a that they can collect data from any sensor in the network. Other approaches can be found in [CLRS01; CL02; ZWS10; MF08].
Table of contents :
Contents
List of Figures
List of Tables
1 Introduction
1.1 Wireless Sensor Network (WSN)
1.2 Background and Motivation
1.3 Problem Statement and Contributions
1.3.1 Problem statement
1.3.2 Contributions
1.4 Thesis organization
2 The State of the Art
2.1 WSN applications
2.2 WSN Characteristics and Challenges
2.2.1 WSN characteristics
2.2.2 WSN challenges
2.2.3 Sensor node components
2.3 WSN Standards and Protocol Stack Architecture
2.3.1 WSN Standards
2.3.1.1 IEEE 802.15.4
2.3.1.2 Zig Bee
2.3.1.3 Wireless Hart
2.3.1.4 ISA100.11a
2.3.1.5 IETF 6LoWPAN
2.3.1.6 IEEE 802.15.3
2.3.1.7 Wibree
2.3.2 Protocol Stack Architecture for WSNs
2.4 Data Aggregation in WSNs
2.4.1 Tree-based mechanisms
2.4.2 Cluster-based mechanisms
2.4.3 Mesh-based mechanisms
2.4.4 Chain-based mechanisms
2.4.5 Hybrid-based mechanisms
2.5 Routing Protocols in WSNs
2.5.1 Data-centric
2.5.2 Hierarchical
2.5.3 Location-based
2.6 Mobility Models for WSNs
2.6.1 Memory-Based models
2.6.2 Memory-Less models
2.6.2.1 Random mobility
2.6.2.2 Controlled mobility
2.6.2.3 Fixed path mobility
2.7 Channel Assignment in WSNs
2.7.1 Static assignment
2.7.2 Dynamic assignment
2.7.3 Hybrid assignment
2.8 Summary
3 Tree-based Data Aggregation Schemes
3.1 Motivation
3.1.1 Problem statement
3.1.2 Tree-based Data Aggregation
3.1.3 Illustration
3.2 New Tree-based Data Aggregation Algorithms
3.2.1 Assumptions
3.2.2 Network model
3.2.3 Depth-First Search Aggregation (DFSA) algorithm
3.2.4 Flooding Aggregation (FA) algorithm
3.2.5 Well-Connected Dominating Set Aggregation (WCDSA) al- gorithm
3.3 Simulation set-up and Comparative results
3.3.1 Simulation set-up
3.3.1.1 Evaluation criteria
3.3.2 Comparative results
3.4 Summary
4 Efficient Tree-based Aggregation and Processing Time
4.1 Motivation
4.1.1 Related works
4.2 Problem statement and Proposition
4.2.1 Problem statement
4.2.2 Proposition: ETAPT algorithm
4.3 Network model and Notation
4.3.1 Network model
4.3.2 Assumptions
4.3.3 Notation
4.4 ETAPT description
4.4.1 MaxWPath and HopDistance of sensor determination
4.4.2 Determination of average waiting and aggregation times .
4.4.3 Illustration
4.5 Performance metrics and Comparative results
4.5.1 Performance metrics
4.5.1.1 Simulation set-up
4.5.2 Comparative results
4.6 Summary
5 Mobility of Mini-Sinks for Reducing Congestion
5.1 Motivation
5.1.1 Problem definition
5.1.2 Proposition
5.2 Model description
5.2.1 Assumptions
5.2.2 Network architecture
5.2.3 Network topology
5.2.4 Mini-Sink mobility model
5.2.5 Multipath Energy Conserving Routing Protocol (MECRP)
5.2.6 Multiple paths extraction
5.2.7 Controlled data aggregation
5.2.8 Energy model
5.2.9 Illustration
5.3 Performance metrics and Evaluation criteria
5.3.1 Performance metrics
5.3.2 Evaluation criteria
5.4 Simulation set-up and Comparison results
5.4.1 Simulation set-up
5.4.2 Comparison results
5.4.2.1 Multi-MS mode
5.4.2.2 Multiple routing paths MS mode
5.4.2.3 MS Point-to-point mode
5.5 Summary
6 Multi-Channel Assignment in Multi-Radio
6.1 Motivation
6.2 Problem statement and Proposition
6.2.1 Network topology and Assumptions
6.2.2 Problem statement
6.2.2.1 Contention graph
6.2.3 Proposition
6.3 Distributed hybrid channel assignment
6.3.1 Overview of WCDS-CA
6.4 Performance metrics
6.5 Simulation set-up and Comparative results
6.5.1 Simulation set-up
6.5.2 Comparative results
6.6 Summary
7 Conclusions and Perspectives
7.1 Conclusions
7.1.1 Tree-based Data Aggregation Schemes in WSNs
7.1.2 Efficient Tree-based Aggregation and Processing Time in WSNs
7.1.3 Mobility of Mini-Sinks for Reducing Congestion in WSNs .
7.1.4 Multi-Channel Assignment in Multi-Radio WSNs
7.2 Perspectives
Author’s Publications
Appendix
References
