Nothing Special   »   [go: up one dir, main page]
Skip to main content

Advertisement

Advertisement
Springer Nature Link
Account
Menu
Find a journal Publish with us Track your research
Search
Cart
  1. Home
  2. International Journal of Networked and Distributed Computing
  3. Article

CHEAP: An Efficient Localized Area Coverage Maintenance Protocol for Wireless Sensor Networks

  • Research Article
  • Open access
  • Published: 18 January 2021
  • Volume 9, pages 33–51, (2021)
  • Cite this article
Download PDF

You have full access to this open access article

International Journal of Networked and Distributed Computing Aims and scope Submit manuscript
CHEAP: An Efficient Localized Area Coverage Maintenance Protocol for Wireless Sensor Networks
Download PDF
  • Gokou Hervé Fabrice Diédié1,
  • Boko Aka2 &
  • Michel Babri3 

  • 89 Accesses

  • Explore all metrics

Abstract

Over the course of operation, a wireless sensor network can experience failures that are detrimental to the underlying application’s objectives. In this paper, we address the problem of restoring coverage ratio of a damaged area (hole) using only the neighboring nodes. Most existing solutions fail to simultaneously prevent new holes formation, collisions, oscillations, cascaded movements, and overlapped areas. To do this, we propose an intersection points-based strategy to properly locate and characterize any type of coverage hole. Then, we allow nodes, whether or not redundant, to coordinate their movements and ranges in order to effectively eliminate the detected hole. We suggest for that purpose, a tabu search based optimization scheme along with a location-allocation model through a mixed integer linear program. Simulation results show that our protocol significantly increases the network’s resilience.

Article PDF

Download to read the full article text

Use our pre-submission checklist

Avoid common mistakes on your manuscript.

References

  1. Y. Wang, Y. Zhang, J. Liu, and R. Bhandari, Coverage, connectivity, and deployment in wireless sensor networks, in: S. Patnik, X. Li, Y.M. Yang (Eds.), Recent Development in Wireless Sensor and Ad-hoc Networks. Signals and Communication Technology, Springer, India, 2014, pp. 25–44.

    Google Scholar 

  2. T. Ojha, S. Misra, N.S. Raghuwanshi, Wireless sensor networks for agriculture: the state-of-the-art in practice and future challenges, Comput. Electron. Agric. 118 (2015), 66–84.

    Google Scholar 

  3. L. Muduli, D.P. Mishra, P.K. Jana, Application of wireless sensor network for environmental monitoring in underground coal mines: a systematic review, J. Netw. Comput. Appl. 106 (2018), 48–67.

    Google Scholar 

  4. S. Chouikhi, I.E. Korbi, Y. Ghamri-Doudane, L.A. Saidane, A survey on fault tolerance in small and large scale wireless sensor networks, Comput. Commun. 69 (2015), 22–37.

    Google Scholar 

  5. S. Abdollahzadeh, N.J. Navimipour, Deployment strategies in the wireless sensor network: a comprehensive review, Comput. Commun. 91–92 (2016), 1–16.

  6. H. Yetgin, K.T.K. Cheung, M. El-Hajjar, L.H. Hanzo, A survey of network lifetime maximization techniques in wireless sensor networks, IEEE Commun. Surv. Tutor. 19 (2017), 828–854.

    Google Scholar 

  7. N.D. Trong, N.P. Le, P.V. Hau, N.V. Khanh, A distributed protocol for detecting and updating hole boundary in wireless sensor networks, Proceedings of the Sixth International Symposium on Information and Communication Technology - SoICT 2015, ACM Press, New York, USA, 2015, pp. 171–178.

    Google Scholar 

  8. T. Amgoth, P.K. Jana, Coverage hole detection and restoration algorithm for wireless sensor networks, Peer-to-Peer Netw. Appl. 10 (2017), 66–78.

    Google Scholar 

  9. P.K. Sahoo, M.J. Chiang, S.L. Wu, An efficient distributed coverage hole detection protocol for wireless sensor networks, Sensors 16 (2016), 386.

    Google Scholar 

  10. G. Dai, H. Lv, L. Chen, B. Zhou, P. Xu, A novel coverage holes discovery algorithm based on voronoi diagram in wireless sensor networks, Int. J. Hybrid Inf. Technol. 9 (2016), 273–282.

    Google Scholar 

  11. D. Šoberl, N.M. Kosta, P. Škraba, Decentralized computation of homology in wireless sensor networks using spanning trees, in: A. Holzinger, P. Kieseberg, A. Tjoa, E. Weippl (Eds.), Machine Learning and Knowledge Extraction. Lecture Notes in Computer Science, Springer International Publishing, Cham, 2017, pp. 25–40.

    Google Scholar 

  12. S. Patra, B. Sau, Detecting hole boundary nodes in WSN under distributed environment, 2016 IEEE 6th International Conference on Advanced Computing (IACC), IEEE, Bhimavaram, India, 2016, pp. 716–721.

    Google Scholar 

  13. A. More, V. Raisinghani, A survey on energy efficient coverage protocols in wireless sensor networks, J. King Saud Univ. Comput. Inform. Sci. 29 (2017), 428–448.

    Google Scholar 

  14. B. Wang, Sensor activity scheduling, in: Coverage Control in Sensor Networks, Computer Communications and Networks, Springer, London, 2010, pp. 121–153.

    Google Scholar 

  15. F. Li, J. Luo, W. Wang, Y. He, Autonomous deployment for load balancing k-surface coverage in sensor networks, IEEE Trans. Wireless Commun. 14 (2015), 279–293.

    Google Scholar 

  16. D. Saha, A. Das, Coverage area maximization by heterogeneous sensor nodes with minimum displacement in mobile networks, 2015 IEEE International Conference on Advanced Networks and Telecommuncations Systems (ANTS), IEEE, Kolkata, India, 2015, pp. 1–6.

    Google Scholar 

  17. T.Y. Lin, H.A. Santoso, K.R. Wu, Global sensor deployment and local coverage-aware recovery schemes for smart environments, IEEE Trans. Mobile Comput. 14 (2015), 1382–1396.

    Google Scholar 

  18. K.P. Sharma, T.P. Sharma, ZBFR: zone based failure recovery in WSNs by utilizing mobility and coverage overlapping, Wireless Netw. 23 (2016), 2263–2280.

    Google Scholar 

  19. M. Amac Guvensan, A. Gokhan Yavuz, Hybrid movement strategy in self-orienting directional sensor networks, Ad Hoc Netw. 11 (2013), 1075–1090.

    Google Scholar 

  20. L. Cooper, Location-allocation problems, Oper. Res. 11 (1963), 331–343.

    Google Scholar 

  21. H.A. Eiselt, G. Laporte, Objectives in location problems, in Facility Location: A Survey of Applications and Methods, Springer Nature, New York, 1995, pp. 151–180.

    Google Scholar 

  22. R. Beghdad, A. Lamraoui, Boundary and holes recognition in wireless sensor networks, J. Innov. Dig. Ecosyst. 3 (2016), 1–14.

    Google Scholar 

  23. S. Das, M.K. DebBarma, Hole detection in wireless sensor network: a review, in: P. Sa, S. Bakshi, I. Hatzilygeroudis, M. Sahoo (Eds.), Recent Findings in Intelligent Computing Techniques. Advances in Intelligent Systems and Computing, Springer, Singapore, 2018, pp. 87–96.

    Google Scholar 

  24. W. An, N. Qu, F.M. Shao, X. Xiong, S. Ci, Coverage hole problem under sensing topology in flat wireless sensor networks, Wireless Commun. Mobile Comput. 16 (2014), 578–589.

    Google Scholar 

  25. Z. Kang, H. Yu, Q. Xiong, Detection and recovery of coverage holes in wireless sensor networks, J. Netw. 8 (2013), 822–828.

    Google Scholar 

  26. C.F. Huang, Y.C. Tseng, The coverage problem in a wireless sensor network, Mobile Netw. Appl. 10 (2005), 519–528.

    Google Scholar 

  27. Y. Bejerano, Coverage verification without location information, IEEE Trans. Mobile Comput. 11 (2012), 631–643.

    Google Scholar 

  28. C. Qiu, H. Shen, K. Chen, An energy-efficient and distributed cooperation mechanism for k-coverage hole detection and healing in WSNs, 2015 IEEE 12th International Conference on Mobile Ad Hoc and Sensor Systems, IEEE, Dallas, TX, USA, 2015, pp. 73–81.

    Google Scholar 

  29. W. Li, Y. Wu, Tree-based coverage hole detection and healing method in wireless sensor networks, Comput. Netw. 103 (2016), 33–43.

    Google Scholar 

  30. M.R. Senouci, A. Mellouk, K. Assnoune, Localized movement-assisted sensor deployment algorithm for hole detection and healing, IEEE Trans. Parallel Distrib. Syst. 25 (2014), 1267–1277.

    Google Scholar 

  31. Q. Fang, J. Gao, L.J. Guibas, Locating and bypassing holes in sensor networks, Mobile Netw. Appl. 11 (2006), 187–200.

    Google Scholar 

  32. W.C. Chu, K.F. Ssu, Location-free boundary detection in mobile wireless sensor networks with a distributed approach, Comput. Netw. 70 (2014), 96–112.

    Google Scholar 

  33. F. Yan, A. Vergne, P. Martins, L. Decreusefond, Homology-based distributed coverage hole detection in wireless sensor networks, IEEE/ACM Trans. Netw. 23 (2025), 1705–1718.

    Google Scholar 

  34. D. Diongue, O. Thiare, An energy efficient self-healing mechanism for long life wireless sensor networks, in: T. Sobh, K. Elleithy (Eds.), Innovations and Advances in Computing, Informatics, Systems Sciences, Networking and Engineering, Lecture Notes in Electrical Engineering, Springer, Cham, 2015, pp. 599–605.

    Google Scholar 

  35. G. Wang, G. Cao, T.F. La Porta, Movement-assisted sensor deployment, IEEE Trans. Mobile Comput. 5 (2006), 640–652.

    Google Scholar 

  36. Y. Wang, J. Gao, J.S.B. Mitchell, Boundary recognition in sensor networks by topological methods, Proceedings of the 12th Annual International Conference on Mobile Computing and Networking - MobiCom’06, ACM Press, New York, USA, 2006, pp. 122–133.

    Google Scholar 

  37. Y. Zou, K. Chakrabarty, Sensor deployment and target localization based on virtual forces, IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428), IEEE, San Francisco, CA, USA, 2003, pp. 1293–1303.

    Google Scholar 

  38. J. Habibi, H. Mahboubi, A.G. Aghdam, Distributed coverage control of mobile sensor networks subject to measurement error, IEEE Trans. Autom. Control 61 (2016), 3330–3343.

    Google Scholar 

  39. P.K. Sahoo, W.C. Liao, Hora: a distributed coverage hole repair algorithm for wireless sensor networks, IEEE Trans. Mobile Comput. 14 (2015), 1397–1410.

    Google Scholar 

  40. C. Qiu, H. Shen, A delaunay-based coordinate-free mechanism for full coverage in wireless sensor networks, IEEE Trans. Parallel Distrib. Syst. 25 (2014) 828–839.

  41. A. Khelil, R. Beghdad, ESA: an efficient self-deployment algorithm for coverage in wireless sensor networks, Proced. Comput. Sci. 98 (2016), 40–47.

    Google Scholar 

  42. M. Rout, R. Roy, Dynamic deployment of randomly deployed mobile sensor nodes in the presence of obstacles, Ad Hoc Netw. 46 (2016) 12–22.

  43. H. Zhao, Q. Zhang, L. Zhang, Y. Wang, A novel sensor deployment approach using fruit fly optimization algorithm in wireless sensor networks, 2015 IEEE Trustcom/BigDataSE/ISPA, IEEE, Helsinki, Finland, 2015, pp. 1292–1297.

    Google Scholar 

  44. A. Ray, D. De, An energy efficient sensor movement approach using multi-parameter reverse glowworm swarm optimization algorithm in mobile wireless sensor network, Simul. Modell. Pract. Theory 62 (2016), 117–136.

    Google Scholar 

  45. J. Wang, S. Medidi, M. Medidi, Energy-efficient k-coverage for wireless sensor networks with variable sensing radii, GLOBECOM 2009 - 2009 IEEE Global Telecommunications Conference, IEEE, Honolulu, HI, USA, 2009, pp. 1–6.

    Google Scholar 

  46. C.T. Vu, Y. Li, Delaunay-triangulation based complete coverage in wireless sensor networks, 2009 IEEE International Conference on Pervasive Computing and Communications, IEEE, Galveston, TX, USA, 2009, pp. 1–5.

    Google Scholar 

  47. Y. Qu, S.V. Georgakopoulos, A distributed area coverage algorithm for maintenance of randomly distributed sensors with adjustable sensing range, 2013 IEEE Global Communications Conference (GLOBECOM), IEEE, Atlanta, GA, USA, 2013, pp. 286–291.

    Google Scholar 

  48. M. Abolhasan, Y. Maali, A. Rafiei, W. Ni, Distributed hybrid coverage hole recovery in wireless sensor networks, IEEE Sens. J 16 (2016), 8640–8648.

    Google Scholar 

  49. K. Lakshmi Joshitha, S. Jayashri, A novel redundant hole identification and healing algorithm for a homogeneous distributed wireless sensor network, Wireless Personal Commun. 104 (2018), 1261–1282.

    Google Scholar 

  50. A.M. Khedr, W. Osamy, A. Salim, Distributed coverage hole detection and recovery scheme for heterogeneous wireless sensor networks, Comput. Commun. 124 (2018), 61–75.

    Google Scholar 

  51. H.G. Diédié, M. Babri, S. Oumtanaga, Redundancy detection protocol for area coverage control in heterogeneous wireless sensor networks, Int. J. Comput. Sci. Issues 12 (2015), 100–110.

    Google Scholar 

  52. H.G. Diédié, B. Aka, M. Babri, Area k-coverage optimization protocol for heterogeneous dense wireless sensor networks, Int. J. Adv. Comput. Sci. Appl. 8 (2017), 327–336.

    Google Scholar 

  53. J. Krarup, D. Pisinger, F. Plastria, Discrete location problems with push-pull objectives, Discrete Appl. Math. 123 (2002), 363–378.

    Google Scholar 

  54. R.Z. Farahani, M. SteadieSeifi, N. Asgari, Multiple criteria facility location problems: a survey, Appl. Math. Modell. 34 (2010), 1689–1709.

    Google Scholar 

  55. P. Brass, Geometric problems on coverage in sensor networks, in: I. Bárány, K.J. Böröczky, G.F. Tóth, J. Pach (Eds.), Geometry – Intuitive, Discrete, and Convex. Bolyai Society Mathematical Studies, Springer Nature, Berlin, Heidelberg, 2013, pp. 91–108.

    Google Scholar 

  56. S.M. Kwon, J.S. Kim, Coverage ratio in the wireless sensor networks using Monte Carlo simulation, 2008 Fourth International Conference on Networked Computing and Advanced Information Management, IEEE, Gyeongju, South Korea, 2008, pp. 235–238.

    Google Scholar 

  57. Y. Liu, L. Suo, D. Sun, A. Wang, A virtual square grid-based coverage algorithm of redundant node for wireless sensor network, J. Netw. Comput. Appl. 36 (2013), 811–817.

    Google Scholar 

  58. A.K. Idrees, K. Deschinkel, M. Salomon, R. Couturier, Distributed lifetime coverage optimization protocol in wireless sensor networks, J. Supercomput. 71 (2015), 4578–4593.

    Google Scholar 

  59. O. Kariv, S.L. Hakimi, An algorithmic approach to network location problems. II: the p-medians, SIAM J. Appl. Math. 37 (1979), 539–560.

    Google Scholar 

  60. R.J. Fowler, M.S. Paterson, S.L. Tanimoto, Optimal packing and covering in the plane are NP-complete, Inform. Process. Lett. 12 (1981), 133–137.

    Google Scholar 

  61. N. Megiddo, A. Tamir, On the complexity of locating linear facilities in the plane, Oper. Res. Lett. 1 (1982), 194–197.

    Google Scholar 

  62. F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res. 13 (1986), 533–549.

    Google Scholar 

  63. B.S. Panda, D.P. Shetty, Minimum range assignment problem for two connectivity in wireless sensor networks, in: R. Natarajan (Ed.), Distributed Computing and Internet Technology, ICDCIT 2014, Springer, Cham, 2014, pp. 122–133.

    Google Scholar 

  64. G.H.F. Diédié, B. Aka, M. Babri, Energy-efficient ant colony based k-hop clustering and transmission range assignment protocol for connectivity construction in dense wireless sensor networks, J. Comput. Sci. 14 (2018), 376–395.

    Google Scholar 

  65. G.H.F. Diédié, B. Aka, M. Babri, Self-stabilising hybrid connectivity control protocol for WSNs, IET Wireless Sens. Syst. 9 (2019), 6–24.

    Google Scholar 

  66. A. Varga, OMNeT++ Simulator, Available from: http://www.omnetpp.org (accessed on July 2016).

  67. W. Heinzelman, A.P. Chandrakasan, H. Balakrishnan, An application-specific protocol architecture for wireless microsensor networks, IEEE Trans. Wireless Commun. 1 (2002), 660–670.

    Google Scholar 

  68. M.N. Halgamuge, M. Zukerman, K. Ramamohanarao, H.L. Vu, An estimation of sensor energy consumption, Progr. Electromagn. Res. B 12 (2009), 259–295.

    Google Scholar 

  69. Society of Robots (SOR), Robot Energy, Available from: https://www.societyofrobots.com/mechanics_energy.shtml (accessed on July 2020).

Download references

Author information

Authors and Affiliations

  1. Laboratoire de Mathématiques et d’Informatique, Université Peleforo Gon Coulibaly, BP 1328, Korhogo, Côte d’Ivoire

    Gokou Hervé Fabrice Diédié

  2. Laboratoire de Mathématiques et d’Informatique, Université Nangui Abrogoua, 02 BP 801, Abidjan, Côte d’Ivoire

    Boko Aka

  3. Laboratoire de Recherche en Informatique et en Télécommunication, INPHB, BP 1093, Yamoussoukro, Côte d’Ivoire

    Michel Babri

Authors
  1. Gokou Hervé Fabrice Diédié
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Boko Aka
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Michel Babri
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Gokou Hervé Fabrice Diédié.

Additional information

Data availability statement: The data that support the findings of this study are available from the corresponding author [GHFD] upon reasonable request.

Rights and permissions

This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Diédié, G.H.F., Aka, B. & Babri, M. CHEAP: An Efficient Localized Area Coverage Maintenance Protocol for Wireless Sensor Networks. Int J Netw Distrib Comput 9, 33–51 (2021). https://doi.org/10.2991/ijndc.k.201218.001

Download citation

  • Received: 04 September 2020

  • Accepted: 18 November 2020

  • Published: 18 January 2021

  • Issue Date: January 2021

  • DOI: https://doi.org/10.2991/ijndc.k.201218.001

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

Keywords

  • Coverage hole
  • detection
  • recovery
  • location-allocation
  • tabu search
  • wireless sensor network
Use our pre-submission checklist

Avoid common mistakes on your manuscript.

Advertisement

Search

Navigation

  • Find a journal
  • Publish with us
  • Track your research

Discover content

  • Journals A-Z
  • Books A-Z

Publish with us

  • Journal finder
  • Publish your research
  • Open access publishing

Products and services

  • Our products
  • Librarians
  • Societies
  • Partners and advertisers

Our imprints

  • Springer
  • Nature Portfolio
  • BMC
  • Palgrave Macmillan
  • Apress
  • Your US state privacy rights
  • Accessibility statement
  • Terms and conditions
  • Privacy policy
  • Help and support
  • Legal notice
  • Cancel contracts here

Not affiliated

Springer Nature

© 2025 Springer Nature