A random scheme to implement m-connected k-covering wireless sensor networks

Ghasemi, V.; Ghanbari Sorkhi, A.

doi:10.22044/jadm.2022.11695.2319

Document Type : Original/Review Paper

Authors

V. Ghasemi ¹
A. Ghanbari Sorkhi ²

¹ Department of Computer Engineering, Faculty of Information Technology, Kermanshah University of Technology, Kermanshah, Iran

² Department of Computer Engineering, University of Science and Technology of Mazandaran, Behshahr, Iran.

https://doi.org/10.22044/jadm.2022.11695.2319

Abstract

Deploying m-connected k-covering (MK) wireless sensor networks (WSNs) is crucial for reliable packet delivery and target coverage. This paper proposes implementing random MK WSNs based on expected m-connected k-covering (EMK) WSNs. We define EMK WSNs as random WSNs mathematically expected to be both m-connected and k-covering. Deploying random EMK WSNs is conducted by deriving a relationship between m-connectivity and k-coverage, together with a lower bound for the required number of nodes. It is shown that EMK WSNs tend to be MK asymptotically. A polynomial worst-case and linear average-case complexity algorithm is presented to turn an EMK WSN into MK in non-asymptotic conditions. The m-connectivity is founded on the concept of support sets to strictly guarantee the existence of m disjoint paths between every node and the sink. The theoretical results are assessed via experiments, and several metaheuristic solutions have been benchmarked to reveal the appropriate size of the generated MK WSNs.

Keywords

20.1001.1.23225211.2022.10.3.12.4

References

[1] S. Messaoud, A. Bradai, S. H. R. Bukhari, P. T. A. Qung, O. B. Ahmed, and M. Atri, “A survey on machine learning in internet of things: Algorithms, strategies, and applications,” Internet of Things, p. 100314, 2020.

[2] C. Goumopoulos and I. Mavrommati, “A framework for pervasive computing applications based on smart objects and end user development,” Journal of Systems and Software, Vol. 162, p. 110496, 2020.

[3] H. Sharma, A. Haque, and F. Blaabjerg, “Machine Learning in Wireless Sensor Networks for Smart Cities: A Survey,” Electronics, Vol. 10, No. 9, p. 1012, 2021.

[4] H. Fouad, N. M. Mahmoud, M. S. El Issawi, and H. Al-Feel, “Distributed and scalable computing framework for improving request processing of wearable IoT assisted medical sensors on pervasive computing system,” Computer Communications, Vol. 151, pp. 257-265, 2020.

[5] A. Boulmaiz, N. Doghmane, S. Harize, N. Kouadria, and D. Messadeg, “The use of WSN (wireless sensor network) in the surveillance of endangered bird species,” in Advances in Ubiquitous Computing: Elsevier, 2020, pp. 261-306.

[6] G. P. Gupta and S. Jha, “Biogeography-based optimization scheme for solving the coverage and connected node placement problem for wireless sensor networks,” Wireless Networks, Vol. 25, No. 6, pp. 3167-3177, 2019.

[7] H. P. Gupta, P. K. Tyagi, and M. P. Singh, “Regular node deployment for $ k $-coverage in $ m $-connected wireless networks,” IEEE Sensors Journal, Vol. 15, Nno. 12, pp. 7126-7134, 2015.

[8] H. P. Gupta, S. V. Rao, and T. Venkatesh, “Analysis of stochastic coverage and connectivity in three-dimensional heterogeneous directional wireless sensor networks,” Pervasive and Mobile Computing, Vol. 29, pp. 38-56, 2016.

[9] Y. Wang, S. Wu, Z. Chen, X. Gao, and G. Chen, “Coverage problem with uncertain properties in wireless sensor networks: A survey,” Computer Networks, Vol. 123, pp. 200-232, 2017.

[10] M. Mansour and F. Jarray, “An iterative solution for the coverage and connectivity problem in wireless sensor network,” Procedia Computer Science, Vol. 63, pp. 494-498, 2015.

[11] W.-C. Ke, B.-H. Liu, and M.-J. Tsai, “Constructing a wireless sensor network to fully cover critical grids by deploying minimum sensors on grid points is NP-complete,” IEEE Transactions on Computers, Vol. 56, No. 5, pp. 710-715, 2007.

[12] S. Harizan and P. Kuila, “Nature-inspired algorithms for k-coverage and m-connectivity problems in wireless sensor networks,” in Design Frameworks for Wireless Networks: Springer, 2020, pp. 281-301.

[13] S. M. Hosseinirad, “Multi-layer clustering topology design in densely deployed wireless sensor network using evolutionary algorithms,” Journal of AI and Data Mining, Vol. 6, NO. 2, pp.297-311, 2018.

[14] H. M. Ammari, “Connected k-coverage in two-dimensional wireless sensor networks using hexagonal slicing and area stretching,” Journal of Parallel and Distributed Computing, Vol. 153, pp. 89-109, 2021.

[15] H. Sheikhi and W. Barkhoda, “Solving the k-coverage and m-connected problem in wireless sensor networks through the imperialist competitive algorithm,” Journal of Interconnection Networks, Vol. 20, No. 01, p. 2050002, 2020.

[16] W. Barkhoda and H. Sheikhi, “Immigrant imperialist competitive algorithm to solve the multi-constraint node placement problem in target-based wireless sensor networks,” Ad Hoc Networks, Vol. 106, p. 102183, 2020.

[17] J. Chelliah and N. Kader, “Optimization for connectivity and coverage issue in target‐based wireless sensor networks using an effective multiobjective hybrid tunicate and salp swarm optimizer,” International Journal of Communication Systems, Vol. 34, No. 3, p. e4679, 2021.

[18] S. K. Gupta, P. Kuila, and P. K. Jana, “Genetic algorithm approach for k-coverage and m-connected node placement in target based wireless sensor networks,” Computers & Electrical Engineering, Vol. 56, pp. 544-556, 2016.

[19] C. Jehan and D. S. Punithavathani, “Potential position node placement approach via oppositional gravitational search for fulfill coverage and connectivity in target based wireless sensor networks,” Wireless Networks, Vol. 23, No. 6, pp. 1875-1888, 2017.

[20] P. Natarajan and L. Parthiban, “k-coverage m-connected node placement using shuffled frog leaping: Nelder–Mead algorithm in WSN,” Journal of Ambient Intelligence and Humanized Computing, pp. 1-16, 2020.

[21] V. K. Akram, O. Dagdeviren, and B. Tavli, "A Coverage-Aware Distributed k-Connectivity Maintenance Algorithm for Arbitrarily Large k in Mobile Sensor Networks," IEEE/ACM Transactions on Networking, 2021.

[22] V. Khalilpour Akram, Z. Akusta Dagdeviren, O. Dagdeviren, and M. Challenger, "PINC: Pickup Non-Critical Node Based k-Connectivity Restoration in Wireless Sensor Networks," Sensors, Vol. 21, No. 19, p. 6418, 2021.

[23] R. Ferrero, M. V. Bueno-Delgado, and F. Gandino, “In-and out-degree distributions of nodes and coverage in random sector graphs,” IEEE transactions on wireless communications, Vol. 13, No. 4, pp. 2074-2085, 2014.

[24] M. Khanjary, M. Sabaei, and M. R. Meybodi, “Critical density for coverage and connectivity in two-dimensional aligned-orientation directional sensor networks using continuum percolation,” IEEE Sensors Journal, Vol. 14, No. 8, pp. 2856-2863, 2014.

[25] M. Khanjary, M. Sabaei, and M. R. Meybodi, “Critical density for coverage and connectivity in two-dimensional fixed-orientation directional sensor networks using continuum percolation,” Journal of Network and Computer Applications, Vol. 57, pp. 169-181, 2015.

[26] H. P. Gupta, S. V. Rao, and T. Venkatesh, “Critical sensor density for partial coverage under border effects in wireless sensor networks,” IEEE transactions on wireless communications, Vol. 13, No. 5, pp. 2374-2382, 2014.

[27] Z. Yu, J. Teng, X. Li, and D. Xuan, “On wireless network coverage in bounded areas,” in 2013 Proceedings IEEE INFOCOM, 2013: IEEE, pp. 1195-1203.

[28] R. Tan, G. Xing, B. Liu, J. Wang, and X. Jia, “Exploiting data fusion to improve the coverage of wireless sensor networks,” IEEE/ACM Transactions on networking, Vol. 20, No. 2, pp. 450-462, 2011.

[29] T. Böhme, F. Göring, and J. Harant, "Menger's theorem," Journal of Graph Theory, Vol. 37, No. 1, pp. 35-36, 2001.

A random scheme to implement m-connected k-covering wireless sensor networks

References

References

Volume 10, Issue 3July 2022Pages 433-447

Volume 10, Issue 3
July 2022
Pages 433-447