Abstract
Simplicial complex provides a precise and tractable representation of the topology of wireless sensor networks. In this paper, a coverage optimization algorithm based on Rips complex is given for the purpose of energy conservation of wireless sensor networks. Considering an area of interest which is covered by sensor nodes completely and even superfluously, our algorithm is performed to turn off redundant sensor nodes effectively in the network while maintaining the coverage consistently. Simulation results show that this distributed algorithm can remove more than 70% internal sensor nodes, and complexity analysis for our algorithm is given.
This work is supported in part by the National Natural Science Foundation of China (No. 61601122, 61871370 and U1805262), the Open Project of Key Laboratory of Wireless Sensor Network & Communication, Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences (No. 20190907), the Fundamental Research Funds for the Central Universities (No. 2242019K40188), the Natural Science Foundation of Shanghai, China under grant No. 18ZR1437500, the Hundred Talent Program of Chinese Academy of Sciences under grant No. Y86BRA1001.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Elhabyan, R., Shi, W., St-Hilaire, M.: Coverage protocols for wireless sensor networks: review and future directions. J. Commun. Netw. 21(1), 45–60 (2019)
Ma, H.C., Sahoo, P.K., Chen, Y.W.: Computational geometry based distributed coverage hole detection protocol for the wireless sensor networks. J. Netw. Comput. Appl. 34(5), 1743–1756 (2011)
Soundarya, A., Santhi, V.: An efficient algorithm for coverage hole detection and healing in wireless sensor networks. In: Proceedings of the 1st International Conference on Electronics, Materials Engineering and Nano-Technology, pp. 1–5. IEEE, Kolkata (2017)
Rachid, B., Amar, L.: Boundary and holes recognition in wireless sensor networks. J. Innovation Digital Ecosyst. 3(1), 1–14 (2016)
Novella, B., Tiziana, C., Tom, F.L.P., Simone, S.: Autonomous deployment of heterogeneous mobile sensors. IEEE Trans. Mobile Comput. 10(6), 753–766 (2011)
Zhang, Y., Zhang, X., Fu, W., Wang, Z., Liu, H.: HDRE: coverage hole detection with residual energy in wireless sensor networks. J. Commun. Netw. 16(5), 493–501 (2016)
Ghrist, R., Muhammad, A.: Coverage and hole-detection in sensor networks via homology. In: Proceedings of the 4th International Conference on Information Processing in Sensor Networks, pp. 254–260. IEEE, Boise (2005)
Silva, V.D., Ghrist, R.: Coordinate-free coverage in sensor networks with controlled boundaries via homology. Int. J. Robot. Res. 25(12), 1205–1222 (2006)
Tahbaz-Salehi, A., Jadbabaie, A.: Distributed coverage verification in sensor networks without location information. IEEE Trans. Autom. Control 55(8), 1837–1849 (2008)
Vergne, A., Decreusefond, L., Martins, P.: Reduction algorithm for simplicial complexes. In: 2013 Proceedings of IEEE INFOCOM, pp. 475–479. IEEE, Turin (2013)
Le, N.-K., Martins, P., Decreusefond, L., Vergne, A.: Simplicial homology based energy saving algorithms for wireless networks. In: 2015 IEEE International Conference on Communication Workshop (ICCW), pp. 166–172. IEEE, London (2015)
Dong, D., Liu, Y., Liao, X.,: Fine-grained boundary recognition in wireless ad hoc and sensor networks by topological methods. In: Proceedings of the 10th ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 135–144. MobiHoc, New Orleans (2009)
Yan, F., Vergne, A., Martins, P., Decreusefond, L.: Homology-based distributed coverage hole detection in wireless sensor networks. IEEE/ACM Trans. Netw. 23(6), 1705–1718 (2015)
Ma, W., Yan, F., Zuo, X., Hu, J., Xia, W., Shen, L.: Simplicial complex reduction algorithm for simplifying WSN’s topology. In: Zheng, J., Xiang, W., Lorenz, P., Mao, S., Yan, F. (eds.) ADHOCNETS 2018. LNICST, vol. 258, pp. 25–35. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-05888-3_3
Guvensan, M.A., Yavuz, A.G.: On coverage issues in directional sensor networks: a survey. Ad Hoc Netw. 9(7), 1238–1255 (2011)
Munkres, J.R.: Elements of Algebraic Topology, 2nd edn. Addison-Wesley, New Jersey (1993)
Edelsbrunner, H., Parsa, S.: On the computational complexity of betti numbers: reductions from matrix rank. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 152–160. SIAM, Portland (2014)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering
About this paper
Cite this paper
Xiang, L. et al. (2019). A Homology Based Coverage Optimization Algorithm for Wireless Sensor Networks. In: Zheng, J., Li, C., Chong, P., Meng, W., Yan, F. (eds) Ad Hoc Networks. ADHOCNETS 2019. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 306. Springer, Cham. https://doi.org/10.1007/978-3-030-37262-0_24
Download citation
DOI: https://doi.org/10.1007/978-3-030-37262-0_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-37261-3
Online ISBN: 978-3-030-37262-0
eBook Packages: Computer ScienceComputer Science (R0)