Project topics and materials
Get Complete Project Material File(s) Now! »
Wireless sensor network representation
Many approaches exist for the representation of wireless sensor networks. Since the connectivity and the coverage of a wireless sensor network define its quality of service, the topology have a key role in the choice of representation. The first kind of traditional approach we can mention is the regular pattern display. With this approach the sensors are considered to be deployed along a hexagonal, square or triangular lattice. In [10], the authors propose an optimal deployment pattern in order to achieve coverage and redundant connectivity. When sensors positions are not following a regular pattern, one has to consider a way to discover the sensor network topology. We can differentiate three different points of view.
The first one is a location-based approach. The exact positions of the sensors are known and the Voronoi diagram is build. Considering the set of vertices of the sensor positions, for each vertex v, there is a corresponding region, called the Voronoi cell of vertex v, consisting of all points closer to v than to any other vertex. The Voronoi cells can thus be build with the bisectors between every two vertices. This approach is used in [33, 88] to compute coverage. Indeed one only has to check if every point of a Voronoi cell is covered by the sensor located in v, for every cells. However, the Voronoi diagram is not locally computable in general. But in [93] the authors propose a way for each node to compute its localized Voronoi cell.
The second approach to coverage discovery for a random deployment of sensors is range-based. That is to say that the exact positions of the sensors is not needed, whereas the distance between neighboring sensors is used to identify coverage. In [92], the authors use the localized Voronoi cell computation to discover coverage as previously. Indeed the Voronoi diagram can be build by using distance information instead of position information. Another way to check the coverage of an area is for each sensor to check if the perimeter of its coverage disk is covered by its neighbors. This is used in [11] in a coverage verification algorithm. This is improved by the same author in [12]: considering the neighboring radius to be large enough compared to the coverage radius, each sensor can determine the relative locations of its neighbors.
In recent works, homology is used to discover the coverage of a wireless sensor network. This is what we can call a connectivity-based approach since only connectivity information between sensors is needed. Ghrist et al., [25, 37], introduced the ˘Cech simplicial complex which gives an exact mathematical representation of a network topology via homology groups.
Optimized order for the removal of vertices
The algorithm now removes vertices from the initial abstract simplicial complex following an optimized order. We begin by computing the first k0 Betti numbers via linear algebra. Then the degrees of all the k0-simplices and the indices of all the vertices are computed as explained in the previous section. The critical vertices of the input list are given a negative index, to flag them as unremovable. Then the indices give us an order for the removal of vertices: the greater the index of a vertex, the more likely it is superfluous for the k0-th homology of its simplicial complex. Therefore, the vertices with the greatest index are candidates for removal: one is chosen randomly. The removal of a vertex leads to the movaln of all its k-faces for every integer k ≥ 1.
At every vertex removal, we need to ensure that the homology is unchanged. We compute the first k0 Betti numbers thanks to the boundary maps every time a vertex is removed. This computation is instantaneous since the complex is already built, and only adjacency matrices defining the complex are needed. If the removal changes the homology, the vertex is put back in the simplicial complex. Moreover its index is assigned a temporary negative value so that the vertex is not candidate for the following draw. The temporary values are recalculated at the next effective removal of a vertex. Otherwise, if the removal does not change the homology, the removal is confirmed. And the modified degrees of the k0-simplices and the indices of the vertices are recalculated. We can note that only the vertices of maximum index can have their indices changed, as explained in Lemma 6. Moreover, in order to improve the algorithm performance it is possible to only compute the modified degrees of k0-simplices. It suffices to flag the k-simplices, k > k0, which are the largest cofaces of k0-simplices. Then when one of them is deleted, the degrees of its k0-faces have to be recalculated.
Mathematical properties
The first property of our algorithm is that the reached solution is optimal. It may not be the optimum solution if there are multiple optima but it is a local optimum. In game theory vocabulary that means that the algorithm reaches a Nash equilibrium as defined in [17].
Theorem 8 (Maximal solution). The reduction algorithm reaches a maximal number for the number of removed vertices: every vertex in the final simplicial complex is needed to maintain its homology. No further vertex can be removed without violating the constraints on the Betti numbers Proof In the final simplicial complex, every vertex is of index strictly smaller than k0 in the general case. By the definition of the indices, we then differentiate two types of vertices: vertices of index −1 and 0.
Table of contents :
Abstract
Résumé
List of publications
French detailed summary
1 Introduction
1.1 Motivation
1.2 Thesis contributions and outline
2 Related work and mathematical background
2.1 Related work
2.1.1 Wireless sensor network representation
2.1.2 Simplicial homology
2.1.3 Random configurations
2.2 Simplicial homology background
2.2.1 Definitions
2.2.2 Abstract simplicial complexes
I Simplicial complexes reduction algorithm
3 Reduction algorithm for energy savings in wireless sensor networks
3.1 Introduction
3.2 Reduction algorithm
3.2.1 Degree calculation
3.2.2 Index computation
3.2.3 Optimized order for the removal of vertices
3.3 Simulation results
3.4 Mathematical properties
4 Clique number of random geometric graphs
4.1 Introduction
4.2 Model
4.3 Asymptotical behavior
4.3.1 Subcritical regime
4.3.2 Critical regime
4.3.3 Supercritical regime
4.4 Other graph characteristics
4.4.1 Maximum vertex degree
4.4.2 Chromatic number
4.4.3 Independence number
II Applications to future cellular networks
5 Self-configuration frequency auto-planning algorithm
5.1 Introduction
5.2 Self-configuration in future cellular networks
5.3 Frequency auto-planning algorithm
5.3.1 Main idea
5.3.2 Algorithm description
5.4 Simulation results
5.4.1 Performance
5.4.2 Figures
6 Self-optimization energy conservation algorithm
6.1 Introduction
6.2 Self-optimization in future cellular networks
6.3 Energy conservation algorithm
6.3.1 Main idea
6.3.2 Algorithm description
6.4 Simulation results
6.4.1 Performance
6.4.2 Figures
7 Disaster recovery algorithm
7.1 Introduction
7.2 Recovery in future cellular networks
7.3 Main idea
7.4 Vertices addition methods
7.4.1 Grid
7.4.2 Uniform
7.4.3 Sobol sequence
7.4.4 Comparison
7.5 Determinantal addition method
7.5.1 Definitions
7.5.2 Simulation
7.5.3 Comparison
7.6 Performance comparisons
7.6.1 Complexity
7.6.2 Mean final number of added vertices
7.6.3 Smoothed robustness
8 Conclusion
8.1 Contributions
8.2 Future research directions
A Simplicial homology of random configurations [26]
L. Decreusefond, E. Ferraz, H. Randriambololona, A. Vergne
A.1 Poisson point process and Malliavin calculus
A.2 First order moments
A.3 Second order moments
A.4 Third order moments
B Efficient simulation of the Ginibre process [27]
L. Decreusefond, I. Flint, A. Vergne
B.1 Introduction
B.2 Notations and general results
B.3 Simulation of the Ginibre point process
References
