Project Topics
Get Complete Project Material File(s) Now! »
Intermittent connectivity
In some applications, it is not necessary to ensure full connectivity in the area considered. It is sucient to guarantee intermittent connectivity by using a mobile sink that moves and collects information from disconnected nodes. There are two types of intermittent connectivity: the rst one uses only one or several mobile sinks and the second uses a mobile sink and multiple throwboxes (Cluster heads).
Isolated nodes:
When the communication range, R, is less than the sensing range, r, full coverage can be achieved but without maintaining connectivity between neighboring nodes. Consequently, these nodes will be isolated. One solution to collect the information detected from isolated nodes is to use one or several mobile sinks. One or several nodes are in charge of visiting any sensor node that is not connected to the sink.
Connected components:
In any connected component, all sensor nodes of this component are connected to each other. However, they are disconnected from nodes in another connected component and they may also be disconnected from the sink. To take advantage of the connectivity within a connected component, a throwbox, illustrated in Figure 2.7 by green nodes, can be assigned to each connected component. A throwbox has the task of collecting the information from each node belonging to its component. Then, one or several nodes, also called mobile sinks (the blue node in Figure 2.7) are in charge of visiting the throwbox of each connected component.
In this section, we studied the dierent coverage and connectivity problems in WSNs. In the following section, we give a representative use case for each of those problems.
Representative use cases
Depending on the application requirements, we can distinguish the following use cases (UC) dealing with coverage and connectivity, and representative of most applications: UC1 monitoring of a temporary industrial worksite requires full area coverage, permanent network connectivity and a uniform deployment of sensor nodes to reduce data gathering delays and provide a better balancing of node energy. UC2 forest re detection requires full area coverage in dry seasons and only 80% in rainy seasons. Permanent connectivity is required in both cases so reghters can be alerted.
Coverage and connectivity problems with regard to R and r
Some deployment algorithms only work when a given relationship exists between the radio range R and the sensing range r. For instance, if R 2r, it is sucient to ensure full coverage, and connectivity will be provided as a consequence. In the following, we study the dierent cases considered in the literature.
Case R 2r: Full coverage implies connectivity:
In (1) and (2), the authors prove that when R 2r, the full coverage of a convex area implies full network connectivity. This result is extended to k-coverage and k-connectivity in (2). Then, using this assumption, it is sucient to ensure full coverage, and connectivity will be a consequence.
Case R 3r: Full coverage implies connectivity:
In (3), it is proved that when R p 3r, ensuring full coverage implies full connectivity. Moreover, the number of sensors needed is optimal when the triangular lattice is used as a deployment pattern. For instance, in (4), the authors propose a deployment algorithm where each sensor node should be placed in a vertex of an equilateral triangle of edge p 3r.
Case R = r:
An optimal deployment algorithm is proposed in (5) to ensure full coverage and 1-connectivity when R = r. In this algorithm, sensor nodes are deployed along a horizontal line, with each two neighboring nodes at a distance of r. Adjacent lines are at a distance of ( p 3 2 +1)r.
In such a deployment, full coverage is ensured, but only sensor nodes located on the same line are connected. That is why the authors propose adding a sensor node between each two adjacent lines in order to connect them, such that these nodes form a vertical line, thereby ensuring 1-connectivity. The optimality of this deployment in terms of the number of sensor nodes is proved in (3).
Coverage and connectivity with regard to regular optimal deployment
Sensor nodes can be deployed in a regular pattern. This pattern can be a triangular lattice, a square grid, a hexagonal grid or a rhomboid grid. For each pattern, the authors in (8) specify a condition that ensures coverage of the area and consequently guarantees network connectivity.
If R r and the hexagonal grid pattern is used, then full area coverage is ensured and the network is connected.
If R p 2r and the square grid or rhomboid pattern is used, then full area coverage is ensured and the network is connected.
if R p 3r and the triangular lattice pattern is used, then full area coverage is ensured and the network is connected. The triangular lattice is the optimal deployment pattern to ensure full area coverage and guarantee network connectivity.
Table of contents :
Acknowledgement
Abstract
1 General Introduction
1.1 Context and motivation
1.2 Main contributions
1.3 Manuscript organization
Part I : State of the art
2 Coverage and connectivity issues in WSNs
2.1 Introduction
2.2 Denition of coverage and connectivity problems in WSNs
2.2.1 Coverage problems
2.2.2 Connectivity problems
2.3 Representative use cases
2.4 Coverage and connectivity problems with regard to R and r
2.5 Coverage and connectivity with regard to regular optimal deployment .
2.6 Conclusion
3 Deployment algorithms in WSNs
3.1 Introduction
3.2 Analysis of the criteria of deployment algorithms
3.2.1 Factors impacting the deployment
3.2.2 Common assumptions and models
3.2.3 Criteria for performance evaluation
3.3 Area coverage and connectivity algorithms
3.3.1 Full coverage
3.3.2 Partial coverage
3.3.3 Intermittent connectivity
3.3.4 Summary
3.4 Barrier coverage and connectivity algorithms
3.4.1 Full barrier coverage
3.4.2 Partial barrier coverage
3.4.3 Summary
3.5 Point coverage and connectivity algorithms
3.5.1 Static PoI
3.5.2 Mobile PoIs
3.5.3 Summary
3.6 Node activity scheduling with regard to coverage
3.6.1 Node activity scheduling based on message exchanges between neighbors
3.6.2 Node activity scheduling based on implicit coordination
3.7 Guidelines for selecting a deployment algorithm
3.8 Conclusion
Part II : Models and theoretical computation for an optimized deployment in 2D and 3D
4 Models for an optimized deployment
4.1 Introduction
4.2 Models for 2D deployment
4.2.1 Sensing range and communication range in 2D
4.2.2 The area considered and obstacles in 2D
4.3 Models for 3D deployment
4.3.1 Sensing range and communication range in 3D
4.3.2 The area considered and obstacles in 3D
4.4 Conclusion
5 Theoretical computation of an optimized deployment in 2D and 3D
5.1 Introduction
5.2 Theoretical computation of an optimal 2D deployment
5.2.1 Target distance in the optimal deployment
5.2.2 Optimal number of sensors to cover a given area
5.2.3 Computation of the eective distance
5.3 Theoretical computation of an optimized 3D deployment
5.3.1 Best polyhedron tessellation for 3D space
5.3.2 Optimized number of nodes to cover 3D space
5.4 Conclusion
Part III : Autonomous deployment
6 Virtual forces based algorithms
6.1 Introduction
6.2 DVFA: Distributed Virtual Forces Algorithm
6.2.1 DVFA principles
6.2.2 Performance evaluation
6.2.3 Summary
6.3 How to cope with node oscillations
6.3.1 ADVFA: Adaptive Distributed Virtual Forces Algorithm
6.3.2 GDVFA: Grid Distributed Virtual Forces Algorithm
6.3.3 Summary
6.4 How to cope with the presence of known or unknown obstacles
6.4.1 Obstacles and deployment algorithms
6.4.2 OA-DVFA: Obstacles Avoidance Distributed Virtual Forces Algorithm
6.4.3 Summary
6.5 How to use virtual forces in 3D
6.5.1 3D-DVFA: 3D Distributed Virtual Forces Algorithm
6.6 Conclusion
Part IV : Assisted deployment
7 Optimized deployment in the presence of obstacles
7.1 Introduction
7.2 First problem: full area coverage and connectivity
7.2.1 Optimized deployment in an irregular area
7.2.2 Optimized deployment in an irregular area with opaque obstacles .
7.2.3 Summary
7.3 Second problem: PoI coverage and connectivity
7.3.1 Related work
7.3.2 Denition of relay node placement problems
7.3.3 Solution for Relay Node Placement: RNP
7.3.4 Solution for Fault-tolerant RNP: FT-RNP
7.3.5 Solution for Constrained fault-tolerant RNP: CFT-RNP
7.3.6 Summary
7.4 Conclusion
8 Optimization of Robot Trajectories
8.1 Introduction
8.2 Related work
8.3 Two-robot assisted deployment: based on a game theory approach
8.3.1 Assumptions and denitions
8.3.2 Deployment duration and obstacles
8.3.3 Problem formalization
8.3.4 Problem resolution
8.4 Multi-robot assisted deployment: based on a multi-objective optimization approach
8.4.1 Problem formalization
8.4.2 NSGA-II based approach for MRDS optimization
8.4.3 Hybrid algorithm for the MRDS problem
8.4.4 Problem resolution
8.5 Conclusion
Part V : Discussion and Conclusion
9 Conclusion and perspectives
9.1 Conclusion
9.1.1 Synthesis
9.1.2 Application to the Cluster Connexion project
9.2 Perspectives and Discussion
9.2.1 More realistic models
9.2.2 From 2D toward 3D
9.2.3 Implementation on real robots
9.2.4 Use of our algorithms to collect data
List of Publications
A A Robot Trajectory Optimization
A.1 Introduction and motivation
A.2 Formalization of the RDS problem
A.3 Proposed algorithms
A.3.1 The exact solution
A.3.2 2-Opt algorithm
A.3.3 Genetic algorithm
A.3.4 Hybrid algorithm
A.4 Comparative evaluation
A.5 Discussion
A.5.1 Obstacles
A.5.2 Capacity constraint
A.5.3 Energy constraint
A.6 Conclusion
B Résumé
B.1 Introduction
B.1.1 Les problèmes de couverture et de connectivité
B.1.2 Les problèmes de connectivité
B.2 Contraintes, hypothèses et modèles théoriques pour le déploiement en 2D et 3D
B.3 Déploiement autonome
B.4 Déploiement assisté par robots mobiles
B.4.1 Calcul du déploiement optimisé
B.4.2 Optimisation des trajectoires des robots
B.5 Conclusion et perspectives
B.5.1 Synthèse
B.5.2 Perpectives
Bibliography
