The first paper of the thesis proposes a distributed BFS tree construction scheme based on a sink node for crash-tolerant sensor network data collection. The proposed theory was substantiated by analyzing the worst possible calculation of the sensor network.
Background
Sensory Data Collection
Data collection or convergence [18, 123] is one of the most used applications in sensor network, where sensory data is sent from the sensor nodes to the base station for statistical analysis. Whether event-triggered or query-driven, the generated sensory data is sent from each node to the base station through a multi-hop path.
Data Gathering Tree
Some other applications may require latency and reliability constraints to be met for efficient data collection. For latency-coupled applications, the spanning tree must support the shortest path distance from all nodes to the sink.
Motivation
As discussed, border area networks require strong area coverage, whereas strip-length coverage is sufficient for road sensor networks. Sensory data must be forwarded to the base station with minimal processing and forwarding delay.
Objectives
Solution Approach : An Overview
The tree management activities of the proposed TMM include both tree construction and tree maintenance against random node failure. The performance of the proposed scheme has been compared with existing schemes in the literature, together with the scheme proposed in the first contribution of this thesis.
Organization of the Thesis
Energy-Latency Trade-off Analysis
In another work [113], the authors proposed a hierarchical scheme to reduce the energy x delay metric for data collection. However, in all the above works, the focus was limited to the analysis of data collection performance in terms of energy and delay.
Data Gathering and Topology Control
They proposed a tree structure called DB-MDST (minimum spanning tree with delay) to achieve efficient data collection in terms of fairness of energy consumption per node and delay constraint. The goal of the proposed tree structure is to reduce the height and at the same time increase the grade.
BFS Tree for Data Gathering
A routing tree is constructed on demand, rooted at each source node, for efficient congestion control using resource control technique. There can be multiple trees rooted in different sources with one final destination as the sink node, so multiple options exist for choosing a data forwarding path.
Fault-tolerance
Tree Maintenance from Node Failure
58] proposed a scheme where a spanning tree is constructed based on the weighted average of hop count and weight of the tree edges. A collection tree is built on the fly with minimum cost for each of the nodes that advertise themselves as the root of the tree.
Supporting Failure in Hierarchical Network Framework
When a routing path fault is detected, a new routing path is established using a resource-based path discovery mechanism. Both CTP and back pressure routing protocol calculate a new path when a fault is detected in the routing path.
Wireless Sensor Network: Theory and Practice
- Network Connectivity and Sensing Coverage
- Sensor Deployment Strategy
- Sensor Power Management
- Delay Sensitive Applications
A series of works have been proposed to deploy the sensor nodes in the network in such a way that some predefined QoS requirements are met. The proposed scheme does not consider the traffic load pattern in the sensor network which is important for forwarding delay-sensitive tree-based data.
Application Specific Customization
Intelligent Transport System
In [111], the authors have developed a multi-hop data distribution protocol for vehicle sensor network based on absolute positioning information obtained from GPS server. In [106], the authors designed an optimization problem to reduce the communication cost in a road sensor network.
Critical Infrastructure Information System
In [66], the authors have proposed the use of multipath data distribution in sensor network to improve reliability in data distribution. As discussed, for applications in CI monitoring, reliability in data delivery must be ensured along with network connectivity and maintenance of sensor coverage.
Summary
Most of the notable works in the literature have focused on analyzing data collection performance in terms of energy and delay as discussed in Chapter 2. Executing the proposed TMM at each node constructs a spanning tree rooted at the sink.
Topology Management Module
TMM Initialization : A Distributed Tree Construction
Every time a node u receives a Token message from a node v, it stores parent(v) and levelv, as stated in lines 1-2 of Algorithm 3.1, which are required during the precomputation phase. On a timeout from the LazyTimer, the switchP arent procedure of Algorithm 3.2 is triggered to change its parent to a node with a better level.
Alternate Parent Precomputation
Let the node declare itself a power node if it satisfies the conditions of line 5 and line 6 of Algorithm 3.5, and then it will not be a power node. So altp on each node is correctly set to the powerP arent or deboostP arent.
Proof of Correctness
Once all the nodes in V reach the stable state, no further node receives any of the Sign, Add or Remove messages. Letx2 chose x1 as its parent upon receiving a Token message from x1 at time tj.
Tree Repairing from Arbitrary Node Crash
First Phase of Tree Repairing : Proactive Approach
Therefore, upon receiving a Booster message from v at time tj > ti, you reset its power and become a Booster node, according to lines 1-5 of Algorithm 3.6. Lemma 3.6. According to Algorithm 3.6, you select only one as an alternate parent so that it provides the shortest path from the root.
Second Phase of Tree Repairing : Reactive Approach
Otherwise, w broadcasts an urgent message in the 1-hop environment with the updated UrgList, according to lines 18-26 of Algorithm 3.13. Upon receiving an UrgentAck, each node updates its neighborhood information according to lines 1-5 of Algorithm 3.14.
Application Message Controller
Simulation Results
Phase I : Extreme Case Scenario
This is the simplest case, since node 4 is a Power node, and it sets its parent to node 2. Each of the nodes, from node 5 to node 8, does not change its parent; neither because of the parental invalidation nor because of the level improvement.
Phase II : Regular Grid Topology
As the grid size increases, the percentage of packets received at the sink decreases linearly as shown in Figure 3.18. From Figure 3.19 and Figure 3.20, when the timer value is small, the convergence time is large.
Phase III : Random Topology
Due to the failure of node 19, nodes 20 and 29 set the parent to their respective alternate parent. It can be observed that the repair time for victim nodes increases along a walk in the subtree rooted at the crashed node, from the root to the leaves.
Summary
The framework of the data collection tree management protocol based on the proposed deployment technique is provided in the next chapter. Thus, energy dissipation from the leaf nodes is significantly less compared to the nodes near the sink.
Deployment Strategy : Background
The area of redundancy of a node u, denoted by Ψ(u), can be defined as the area such that u is the only active node within Ψ(u), and all other nodes within the Ψ(u) operate as the dedicated set redundant for that area. To ensure that the area Ψ(u) is always observation-covered, and the network connectivity is maintained upon failure of the primary node and for all subsequent active nodes v∈R(u) replacing the faulty node, R(v) is set on R(u).
Estimation of Deployment Density
Estimating Average Number of Children
Nodev can be placed at any point on line segmentBE, bounded bydmin todM AX. The child of node u can be placed at any position within the region bounded by F, R, G\ and F, H, G.
Estimating Average Energy Dissipation Factor
Since the child node can be uniformly placed in the region bounded by the arcsF, R, G\ and F, H, G\ for the parent node u at position E,ξ can be calculated as,.
Estimating the Gradient of Node Density
Theoretical Analysis
Redundancy Analysis
Estimated EDF: Figure 4.11 shows the percentage of redundancy relative to the level in the data collection tree. The figures show that although the percentage of redundancy varies with respect to levels, regardless of site size, the average percentage of redundancy in a site is almost constant at 67.258%.
Probability of Sensing Coverage based on Deployment Strategy
Let the probability that each primary node has enough redundant nodes to supply (which is the EDF function at that node) be represented by P{suf f Red(EDF)}. The figure shows that the probability of complete coverage is very high.
Simulation Results
Data rate (kbps in logarithmic scale) Proposed Framework Framework by Liao et al., 2011 Framework by Yun et al., 2010 Percentage of Node Failed Proposed Framework Framework by Liao et al., 2011 Framework by Yun et al.
Summary
Any failure of an intermediate node in the data collection tree affects both connectivity and record coverage in the network. Furthermore, the amount of redundancy also depends on the nature of the data collection tree.
First Phase of Tree Management
Active Nodes Selection Procedure
The Bcast messages are propagated from the sink towards the periphery of the terrain so that each node in the network becomes either a primary tree member or a redundant one. Upon receiving a Bcast message from a node v, node u compares the RSSI with SSd, where SSd indicates the strength of the received signal from d distance.
Load-Balanced BFS Tree Construction
If u receives a token from w, it changes the parent from v to w according to lines 10-13 of Algorithm 5.2 and Algorithm 5.3. Therefore, according to Algorithm 5.8, node w sends an AddMe message tov (where v ∈altpSet(w) by assumption).
Post Tree Construction Activities
Second Phase of Tree Management
Maintenance Scheme for Single Node Failure
So if the parent node fails due to aging or crash, the child can repair the parent to T+ 2Ω at worst. The slave node and the parent node with the error send a total of 3 messages (1Leave + 1J oin + 1J oinAck) to repair their parent due to the failure of the parent.
Maintenance Scheme for Multiple Node Failures
Since the Leave message is broadcast, the exchange of Join and JoinAck messages between each pair of nodes with respect to node u can be assumed to be parallel, and thus they can cumulatively introduce a 2Ω amount of delay in the worst case. However, the worst possible event is a rare event, so the implementation cost can be afforded depending on the usage requirement.
Application Message Controller
Simulation Results
- Effect of Load Balancing on Energy Dissipation
- Time to Fail: Comparison with “Online Repairing”
- Amount of Sensory Packets Received
- Comparison with Gradient based Deployment without Redundancy . 148
When node 1 fails, all data traffic from part A of the terrain goes through nodes 5 and 2. In the proposed scheme in this chapter, the density of primary nodes is uniform over the entire terrain.
Summary
Furthermore, the reliability of the delivery of sensory data to the roadsides is low for these schemes due to the mobility of the vehicles. The ADCROSS protocol proposes the concept of k-strip length coverage, which ensures that any passing vehicle is detected by at least k active sensors along the length of the road segment.
Problem Definition and Objectives
Centralized Scheduling
- Coverage Interval Stabbing
- Construction of the Set of Feasible Solutions for the L-chain
- Optimal Solution of the B-chains
- Optimal Solution of the CSLC Graph
This helps to reduce the complexity of the greedy approximation heuristic for solving the optimal CSLC graph. The second step of the CSLC graph optimality problem determines the optimal B chains for all ui ∈ χ.
Distributed Approach : Active Node Selection
Basics
Back-off Computation
Scheduling Strategy
Initialization
Adjusting SYN-DATA Intervals
Tree based Data Collection
