Topology of wireless networks

Apart from “looking at the picture” and pinpointing the coverage “holes”, it seems rather mysterious that some mathematical theory can help, but it is the case and this is called topological algebra! The basics are very well explained is the above mentioned paper. Roughly speaking, it consists in constructing a combinatorial object (the Cech complex) from the geometry, adding an algebraic structure on it, making some simple computations and then interpreting them geometrically. One of the conclusions we can draw is whether or not, the domain is fully covered. At a most basic level, it can also says if the network of sensors is connected, i.e. if a message can go through one sensor to any other though the network. This is of critical importance, since sensors are small and cheap devices, aiming to work autonomously without the help of an impotent central server, and thus should be able to communicate with their siblings at any time.

That’s where the adventure began: That’s how with my colleague P. Martins, we began to investigate how such tools could be applied to wireless systems in general and not only to sensor networks…

• The very first work on topological algebra was the computations of the moments (mainly expectation and variance) of the number of simplices for a random configuration of points based on an homogeneous Poisson process. Decreusefond2014 The main tool is the so-called chaos decomposition which comes from the Malliavin calculus theory.
• We then tried to evaluate the error which is made in relying on the Rips complex instead of the Cech complex. We showed that still on Poisson configurations, the expectation of the second Betti number \(\beta_1\), i.e. the number of coverage holes, differs in the two situations from at most 10\(\%\). The computations were made on the plane in Feng2012 and on the sphere in Feng2014
• Deviating from the usual way of thinking in topological algebra which is concentrated on the Betti numbers, we used the information contained in the Cech complex to derive an innovative algorithm for power saving in wireless networks. Vergne2013 It has been further improved using simulated annealing to allow intermediate power reduction at each base station 7247173
• Spiced with a little bit of advanced stochastic geometry, we define an optimal way to reconstruct a wireless network partially destroyed by whatever sort of disaster which may happen : earthquake, tsunami, etc. Vergne2014
• The main part of all that stuff is summarized in these slides

Bibliography

• [Decreusefond2014] Decreusefond, Ferraz, Randriambololona & Vergne, Simplicial Homology of Random Configurations, Advances in Applied Probability., 46, 1-23 (2014).
• [Feng2012] Feng, Martins & Decreusefond, Accuracy of Homology based Approaches for Coverage Hole Detection in Wireless Sensor Networks, in edited by Springer-Verlag (2012)
• [Feng2014] Feng, Martins & Decreusefond, Accuracy of Homology based Coverage Hole Detection for Wireless Sensor Networks on Sphere, IEEE Transactions on mobile computing, 17(4), 423-433 (2014).
• [Vergne2013] Vergne, Decreusefond & Martins, Reduction algorithm for simplicial complexes, 475-479, in in: 2013 Proceedings IEEE INFOCOM, edited by (2013)
• [7247173] Le, Martins, Decreusefond & Vergne, Simplicial homology based energy saving algorithms for wireless networks, 166-172, in in: 2015 IEEE International Conference on Communication Workshop (ICCW), edited by (2015)
• [Vergne2014] Vergne, Flint, Decreusefond & Martins, Disaster recovery in wireless networks: A homology-based algorithm, in in: 2014 21st International Conference on Telecommunications, ICT 2014, edited by (2014)