Project topics and materials
Get Complete Project Material File(s) Now! »
Polygon based approaches
In [35, 52, 53, 54], the Voronoi diagram was used to detect boundary nodes. The Voronoi diagram of a collection of nodes partitions the space into polygons called Voronoi polygons. Every point in a given polygon is closer to the node in this polygon than to any other node. So if some portion of a Voronoi polygon is not covered by the node inside this polygon, it will not be covered by any other node, which implies a coverage hole. However, it is known from computational geometry that the Voronoi polygon of boundary nodes can not be locally computed in general [55]. Realising such a problem, the authors in [56, 57] proposed to use localized Voronoi polygons for boundary node detection. In the scheme, each node constructs its localized Voronoi polygon. If its localized Voronoi polygon is infinite or it is finite but with some vertices uncovered by the node, then the node must be a boundary node.
Perimeter based approaches
Different from polygon based approaches, perimeter based approaches detect boundary nodes by checking whether the perimeter of the node’s sensing disk is covered by its neighbours or not. In [58], it is proved that a sensor node does not border a coverage hole if its sensing border is entirely covered by the sensing ranges of its neighbours. Another boundary node detection approach proposed in [59, 60] simplifies the previous border checking approach by only checking intersection points on the sensing border. A point is called an intersection point between nodes u and v if it is an intersection point of the sensing borders of u and v. A node is a boundary node if and only if there exists at least one intersection point which is not covered by any other neighbours. Based on that criterion, some other algorithms were proposed in [47, 61] to discover boundary nodes. Furthermore, the authors also proposed a distributed algorithm to discover the exact boundary cycles of coverage holes in [47].
Range based approaches
The range based approaches attempt to identify boundary nodes based on relative distance between neighbouring nodes. They also follow the ideas of either polygon based or perimeter based approaches. In [62, 63], a localized Voronoi polygon based boundary node detection algorithm was proposed, which is similar as that in [56, 57]. The difference lies in that the localized Voronoi polygon is constructed using location information of nodes in [56, 57] while it is constructed based on directional and distance information between neighbouring nodes in [62, 63]. In [44], the author followed the idea of perimeter based approaches. He proposed a coverage verification algorithm based on distances between neighbouring nodes. In the algorithm, each node first calculates a set of segments. Each segment is a part of its sensing border that is covered by one of its intersecting neighbours. After that, the node verifies whether its entire sensing border is covered by the set of segments. If yes, it implies the node is not a boundary node. Otherwise, it is a boundary node. Recently, in [64], the same author proposed another simpler algorithm for coverage verification. He assumed that the transmission radius of each sensor is at least four times larger than its sensing radius. The assumption implies that for any node, every pair of its intersecting neighbours are also neighbours of each other. The algorithm uses this property to determine the relative locations of all the intersecting neighbours of any node and uses it to verify coverage. But if the assumption is not satisfied, the algorithm will not work. In addition, a more general scheme was proposed in [65] for verifying k-coverage of a d-dimensional target field for an arbitrary positive integer k and d ∈ {1, 2, 3}. The scheme transforms the k-coverage verification problem in d dimension to a number of coverage verification problems in (d − 1) dimension by dimension reduction technique. It then uses the same ideas as that in [44, 64] to verify k-coverage in one dimension.
Table of contents :
Acknowledgements
Abstract
Résumé
Publications
Contents
List of Figures
List of Tables
0 Résumé long en français
1 Introduction
1.1 Motivations
1.2 Objectives and contributions
1.2.1 Objectives
1.2.2 Contributions
1.3 Organization
2 Related Work and Mathematical Background
2.1 Traditional approaches
2.1.1 Location based approaches
2.1.2 Range based approaches
2.1.3 Graph based approaches
2.1.4 Remarks on these approaches
2.2 Homology based approaches
2.2.1 Mathematical background
2.2.2 Homology based approaches
3 Accuracy of Homology based Coverage Hole Detection on Plane
3.1 Introduction
3.2 Models and definitions
3.3 Bounds on proportion of triangular holes
3.3.1 Preliminary
3.3.2 Case 0 < γ ≤ √3
3.3.3 Case √3 < γ ≤ 2
3.3.4 Case γ > 2
3.4 Performance evaluation
3.4.1 Simulation settings
3.4.2 Performance evaluation
3.4.3 Discussions on applications
3.5 Chapter summary
4 Accuracy of Homology based Coverage Hole Detection on Sphere
4.1 Introduction
4.2 Models and definitions
4.3 Bounds on proportion of spherical triangular holes
4.3.1 Preliminary
4.3.2 Case 0 < Rc ≤ Rarccos([3 cos2(Rs/R) − 1]/2)
4.3.3 Case Rarccos([3 cos2(Rs/R) − 1]/2) < Rc ≤ 2Rs
4.3.4 Case Rc > 2Rs
4.3.5 Case R → ∞
4.4 Performance evaluation
4.4.1 Simulation settings
4.4.2 Impact of Rs and Rc
4.4.3 Impact of R
4.4.4 Discussions on applications
4.5 Chapter summary
5 Graph based Distributed Coverage Hole Detection
5.1 Introduction
5.2 Models and assumptions
5.3 Graph based distributed algorithm
5.3.1 Neighbour discovery
5.3.2 Boundary nodes discovery
5.3.3 Boundary cycles discovery
5.3.4 Cycles selection
5.4 Simulations and performance evaluation
5.4.1 Simulation settings
5.4.2 Probability of boundary nodes detection
5.4.3 Probability of boundary cycles detection
5.5 Chapter summary
6 Homology based Distributed Coverage Hole Detection
6.1 Introduction
6.2 Models and definitions
6.3 Homology based distributed algorithm
6.3.1 Weight computation
6.3.2 Vertex and edge deletion
6.3.3 Boundary edge detection
6.3.4 Coarse boundary cycles discovery
6.3.5 Boundary cycles minimization
6.4 Performance evaluation
6.4.1 Simulation settings
6.4.2 Complexity
6.4.3 Comparison with boundary recognition algorithm
6.4.4 Comparison with location based algorithm
6.5 Chapter summary
7 Conclusions and Future Work
7.1 Major contributions
7.2 Future research directions
A Computation of Area |S−(r0, r1, ϕ1)|
A.1 Area |S−(r0, r1, ϕ1)| in case √3 < γ ≤ 2
A.2 Area |S−(r0, r1, ϕ1)| in case γ > 2
B Detailed Values of Simulation Results and Bounds on Sphere
References
