Detecting gaps and voids in WSNs and IoT networks: the minimum x-coordinate based method

ABSTRACT

When we deal with the deployment structure of Wireless Sensor Networks (WSNs) used in applications where the zone-of-interest is not accessible by humans, like forest fire detection, military applications, etc., random deployment is often the main or even the only practical solution that can be chosen. One of the main issues in this deployment is that it can lead to a formation of gaps or voids, which represent non-covered zones in the network. This can be very problematic, since it is not possible to detect some serious and dangerous problems, like a starting fire, the presence of non-desired persons or cyber-security attacks, etc. Therefore, detecting non-covered zones is of high importance. In this paper, we present a new method that allows to detect gaps and voids in WSNs and IoT networks after executing the D-LPCN algorithm and using some characteristics related to the value of the angle formed by the node of the gap having the minimum x-coordinate.¹

References

1. Mohammad Hammoudeh. 2015. Applying Wireless Sensor Networks to Solve Real-world Problems. In Proceedings of the International Conference on Intelligent Information Processing, Security and Advanced Communication (IPAC'15), Djallel Eddine Boubiche, Faouzi Hidoussi, and Homero Toral Cruz (Eds.). ACM, New York, NY, USA.
2. Papadimitratos, P., and Haas, Z. J. Secure routing for mobile ad hoc networks. In SCS Communication Networks and Distributed Systems Modeling and Simulation Conference (CNDS 2002), vol. 31, San Antonio, TX.
3. Wang, W., and Bhargava, B. Visualization of wormholes in sensor networks. In Proceedings of the 3rd ACM workshop on Wireless security (2004), ACM, pp. 51--60.
4. Andrew Carlin, Mohammad Hammoudeh and Omar Aldabbas, Intrusion detection and countermeasure of virtual cloud systems-state of the art and current challenges, International Journal of Advanced Computer Science and Applications, 2015, 6(6), 1--15.
5. Cardei, M., MacCallum, D., Cheng, M. X., Min, M., Jia, X., Li, D., and Du, D. Z. Wireless sensor networks with energy efficient organization. Journal of Interconnection Networks, 3(03n04), 2002, 213--229.
6. Cardei, M., and Du, D. Z. Improving wireless sensor network lifetime through power aware organization. Wireless Networks, 11(3), 2005, 333--340.
7. Carle, J., and Simplot-Ryl, D. Energy-efficient area monitoring for sensor networks. Computer, 37(2), 2004, 40--46.
8. Zhou, Z., Das, S., and Gupta, H. (2004, October). Connected k-coverage problem in sensor networks. In Proceedings of the 13th IEEE International Conference on Computer Communications and Networks (ICCCN), 2004, pp. 373--378.
9. Aissani, M., Mellouk, A., Badache, N., and Djebbar, M. A preventive rerouting scheme for avoiding voids in wireless sensor networks. In Global Telecommunications Conference, 2009. GLOBECOM 2009. IEEE (2009), IEEE, pp. 1--5.
10. Balister, P., Zheng, Z., Kumar, S., and Sinha, P. Trap coverage: Allowing coverage holes of bounded diameter in wireless sensor networks. In INFOCOM 2009, IEEE (2009), IEEE, pp. 136--144.
11. Bouk, S. H., Ahmed, S. H., Park, K.-J., and Eun, Y. Edove: Energy and depth variance-based opportunistic void avoidance scheme for underwater acoustic sensor networks. Sensors 17, 10 (2017), 2212.
12. Dong, D., Li, M., Liu, Y., Li, X.-Y., and Liao, X. Topological detection on wormholes in wireless ad hoc and sensor networks. IEEE/ACM Transactions on Networking (TON) 19, 6 (2011), 1787--1796.
13. Jia, W., Wang, T., Wang, G., and Guo, M. Hole avoiding in ad- vance routing in wireless sensor networks. In Wireless Communications and Networking Conference, 2007. WCNC 2007. IEEE (2007), IEEE, pp. 3519--3523.
14. Lu, C., Blum, B. M., Abdelzaher, T. F., Stankovic, J. A., and He, T. Rap: A real-time communication architecture for large-scale wireless sensor networks. In Real-Time and Embedded Technology and Applications Symposium, 2002. Proceedings. Eighth IEEE (2002), IEEE, pp. 55--66.
15. Zhang, D., and Dong, E. An efficient bypassing void routing protocol based on virtual coordinate for WSNs. IEEE Communications Letters 19, 4 (2015), 653--656.
16. Yuzhen Liu and Weifa Liang, Approximate coverage in wireless sensor networks, The 30th Anniversary of the IEEE Conference on Local Computer Networks (LCN'05), Sydney, NSW, 2005, pp. 68--75.
17. W. J. Liu and K. T. Feng, Greedy Routing with Anti-Void Traversal for Wireless Sensor Networks, in IEEE Transactions on Mobile Computing, vol. 8, no. 7, pp. 910--922, July 2009.
18. Lu Hong, Mobile agent based topology control algorithms for wireless sensor networks, 2013 IEEE Wireless Communications and Networking Conference Workshops (WCNCW), Shanghai, 2013, pp. 195--199.
19. Shigang Chen, Guangbin Fan, and Jun-Hong Cui. Avoid 'void' in geographic routing for data aggregation in sensor networks. International Journal of Ad Hoc and Ubiquitous Computing. Vol. 1, Issue. 4, July 2006, 169--178.
20. Gustavo Weber Denardin, Carlos Henrique Barriquello, Alexandre Campos, Ricardo Nederson do Prado, A geographic routing hybrid approach for void resolution in wireless sensor networks, Journal of Systems and Software, Volume 84, Issue 10, 2011, Pages 1577--1590.
21. A. Bounceur, R. Euler, A. Benzerbadj, F. Lalem, M. Saoudi, T. Kechadi, M. Sevaux, Finding a polygon hull in wireless sensor networks, in: European Conference on Operational Research, University of Strathclyde, Glasgow, UK, Invited talk, EURO 2015, July 2015.
22. F. Lalem, A. Bounceur, M. Bezoui, M. Saoudi, R. Euler, and M. Sevaux. LPCN: Least Polar-angle Connected Node Algorithm to Find a Polygon Hull in a Connected Euclidean Graph, Journal of Network and Computer Applications (JNCA), Elsevier, 93 (2017), pp. 38--50.
23. M. Saoudi, F. Lalem, A. Bounceur, R. Euler, A. Laouid, M. Bezoui, and M. Sevaux, D-LPCN: A Distributed Least Polar-angle Connected Node Algorithm for Finding the Boundary of a Wireless Sensor Network, Ad Hoc Networks, Elsevier, Volume 56, 1 March 2017, Pages 56--71.
24. A. Bounceur, M. Bezoui, R. Euler, R. Lalem, A Wait-Before-Starting Algorithm for Fast, Fault-Tolerant and Low Energy Leader Election in WSNs Dedicated to Smart-Cities and IoT. In the IEEE Sensors conference, Oct 2017, Glasgow, United Kingdom.
25. K. Mehdi, M. Lounis, A. Bounceur. CupCarbon: A Multi-Agent and Discrete Event Wireless Sensor Network Design and Simulation Tool, In IEEE 7th International Conference on Simulation Tools and Techniques (SIMUTools'14), Lisbon, Portugal, 2014.
26. A. Bounceur, CupCarbon: A New Platform for Designing and Simulating Smart-City and IoT Wireless Sensor Networks (SCI-WSN), In the International Conference on Internet of things and Cloud Computing (ICC 2016), The Moller Center Churchill College, University of Cambridge, United Kingdom, 22--23 March 2016.
27. CupCarbon simulator, http://www.cupcarbon.com

Index Terms

• Computing methodologies

  • Distributed computing methodologies

    • Distributed algorithms

• Mathematics of computing

  • Discrete mathematics

    • Graph theory

      • Graph algorithms

• Networks

  • Network algorithms

• Theory of computation

  • Randomness, geometry and discrete structures

    • Computational geometry