Skip to main content
SpringerLink
Log in

Coverage rate calculation in wireless sensor networks

  • Published:
Computing Aims and scope Submit manuscript

Abstract

The deployment of sensors without enough coverage can result in unreliable outputs in wireless sensor networks (WSNs). Thus sensing coverage is one of the most important quality of service factors in WSNs. A useful metric for quantifying the coverage reliability is the coverage rate that is the area covered by sensor nodes in a region of interest. The network sink can be informed about locations of all nodes and calculate the coverage rate centrally. However, this approach creates huge load on the network nodes that had to send their location information to the sink. Thus, a distributed approach is required to calculate the coverage rate. This paper is among the very first to provide a localized approach to calculate the coverage rate. We provide two coverage rate calculation (CRC) protocols, namely distributed exact coverage rate calculation (DECRC) and distributed probabilistic coverage rate calculation (DPCRC). DECRC calculates the coverage rate precisely using the idealized disk graph model. Precise calculation of the coverage rate is a unique property of DECRC compared to similar works that have used the disk graph model. In contrast, DPCRC uses a more realistic model that is probabilistic coverage model to determine an approximate coverage rate. DPCRC is in fact an extended version of DECRC that uses a set of localized techniques to make it a low cost protocol. Simulation results show significant overall performance improvement of CRC protocols compared to related works.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Yick J, Mukherjee B, Ghosal D (2008) Wireless sensor network survey. Comput Netw 52(12): 2292–2330

    Article  Google Scholar 

  2. Jaworski J, Ren M, Rybarczyk K (2009) Random key predistribution for wireless sensor networks using deployment knowledge. Computing 85(1): 57–76

    Article  MathSciNet  MATH  Google Scholar 

  3. Pashazadeh S, Sharifi M (2009) A geometric modelling approach to determining the best sensing coverage for 3-dimensional acoustic target tracking in wireless sensor networks. Sensors 9(9): 6764–6794

    Article  Google Scholar 

  4. Aziz N, Mohemmed AW, Sagar D (2007) Particle swarm optimization and Voronoi diagram for wireless sensor networks coverage optimization. In: International conference on intelligent and advanced systems, Kuala Lumpur, Malaysia, pp 961–965

  5. Zhang C, Zhang YC, Fang YG (2009) Localized algorithms for coverage boundary detection in wireless sensor networks. Wirel Netw 15(1): 3–20

    Article  Google Scholar 

  6. Argany M, Mostafavi MA, Karimipour F (2010) Voronoi-based approaches for geosensor networks coverage determination and optimisation: a survey. In: International symposium on Voronoi diagrams in science and engineering, Quebec, Canada, pp 115–123

  7. Hughes B, Cahill V (2003) Towards real-time event-based communication in mobile ad hoc wireless networks. In: International workshop on real-time LANs in the internet age, Porto, Portugal, pp 77–80

  8. Shen X, Chen J, Sun Y (2006) Grid scan: a simple and effective approach for coverage issue in wireless sensor networks. In: IEEE international conference on communications, Istanbul, Turkey, pp 3480–3484

  9. Sheu JP, Chang GY, Chen YT (2008) A novel approach for k-coverage rate evaluation and re-deployment in wireless sensor networks. In: IEEE global telecommunications conference, New Orleans, LA, USA, pp 1–5

  10. Tan H, Wang Y, Hao X, Hua QS, Lau F (2010) Arbitrary obstacles constrained full coverage in wireless sensor networks. In: International conference on wireless algorithms, systems, and applications, Beijing, China, pp 1–10

  11. Balister B, Zheng Z, Kumar S, Sinha P (2009) Trap coverage: allowing coverage holes of bounded diameter in wireless sensor networks. In: IEEE international conference on computer communications, Rio de Janeiro, Brazil, pp 136–144

  12. Pashazadeh S, Sharifi M (2009) Determining the best sensing coverage for 2-dimensional acoustic target tracking. Sensors 9(5): 3405–3436

    Article  Google Scholar 

  13. Watfa MK, Commuri S (2009) Energy-efficient approaches to coverage holes detection in wireless sensor networks. In: IEEE multi-conference on systems and control, Saint Petersburg, Russia, pp 131–136

  14. Garetto M, Gribaudo M, Chiasserini C, Leonardi E (2007) A distributed sensor relocation scheme for environmental control. In: international conference on mobile ad hoc and sensor systems, Pisa, Italy, pp 1–10

  15. Bartolini N, Calamoneri T, Fusco E, Massini A, Silvestri S (2009) Push and pull: autonomous deployment of mobile sensors for a complete coverage. Wirel Netw 16(3): 607–625

    Article  Google Scholar 

  16. Cheng T, Savkin A (2010) Decentralized control of mobile sensor networks for triangular blanket coverage. In: American control conference, Baltimore, MA, USA, pp 2903–2908

  17. Fang Q, Gao H, Guibas LJ (2004) Locating and bypassing routing holes in sensor networks. In: Annual joint conference of the IEEE computer and communications societies, Hong Kong, China, pp 2458–2468

  18. Frey H, Görgen D (2005) Planar graph routing on geographical clusters. Ad Hoc Netw 3(5): 560–574

    Article  Google Scholar 

  19. Huang C, Tseng Y (2005) A survey of solutions to the coverage problems in wireless sensor networks. J Internet Technol 6(1): 1–8

    Google Scholar 

  20. Ghosh A, Das SK (2008) Coverage and connectivity issues in wireless sensor networks: a survey. Pervasive Mob Comput 4(3): 303–334

    Article  MathSciNet  Google Scholar 

  21. Stojmenovic I, Nayak A (2010) Wireless sensor and actuator networks: algorithms and protocols for scalable coordination and data communication. Wiley-Interscience, New York

    MATH  Google Scholar 

  22. Liu B, Towsley D (2004) A study of the coverage of large-scale sensor networks. In: International conference on mobile ad hoc and sensor systems, FL, USA, pp 475–483

  23. Chen J, Li S, Sun Y (2007) Novel deployment schemes for mobile sensor networks. Sensors 7(11): 2907–2919

    Article  Google Scholar 

  24. Aziz NAA, Aziz KA, Ismail WZW (2009) Coverage strategies for wireless sensor networks. World Acad Sci Eng Tech 50: 145–150

    Google Scholar 

  25. Li JS, Kao HC (2010) Distributed k-coverage self-location estimation scheme based on Voronoi diagram. IET Commun 4(2): 167–177

    Article  MathSciNet  Google Scholar 

  26. Jin Y, Jo JY, Wang L, Kim Y, Yang X (2008) ECCRA: an energy-efficient coverage and connectivity preserving routing algorithm under border effects in wireless sensor networks. Comput Commun 31(10): 2398–2407

    Article  Google Scholar 

  27. Cai YL, Li ML, Shu W, Wu MY (2007) ACOS: an area-based collaborative sleeping protocol for wireless sensor networks. Ad Hoc Sens Wirel Netw 3(1): 77–97

    Google Scholar 

  28. Lazos L, Poovendran R, Ritcey JA (2007) On the deployment of heterogeneous sensor networks for detection of mobile targets. In: IEEE international symposium on modeling and optimization in mobile, ad hoc and wireless networks, Limassol, Cyprus, pp 1–10

  29. Killijian MO, Cunningham R, Meier R, Mazare L, Cahill V (2001) Towards group communication for mobile participants. In: Workshop on principles of mobile computing, RI, USA, pp 75–82

  30. Shen F, Sun MT, Liu C, Salazar A (2009) Coverage-aware sleep scheduling for cluster-based sensor networks. In: IEEE wireless communications and networking conference, Budapest, Hungary, pp 1–6

  31. Zou Y, Chakrabarty K (2003) Sensor deployment and target localization based on virtual forces. In: Annual joint conference of the IEEE computer and communications, San Franciso, USA, pp 1293–1303

  32. Lambrou TP, Panayiotou CG (2009) Collaborative area monitoring using wireless sensor networks with stationary and mobile nodes. J Adv Signal Proc 750657:750651–750657:750616

    Google Scholar 

  33. Wan Ismail W (2010) Study on coverage in wireless sensor network using grid based strategy and particle swarm optimization. In: IEEE Asia Pacific conference on circuits and systems, Kuala Lumpur, Malaysia, pp 1175–1178

  34. Akshay N, Kumar MP, Harish B, Dhanorkar S (2010) An efficient approach for sensor deployments in wireless sensor network. In: International conference on emerging trends in robotics and communication technologies, Chennai, India, pp 350–355

  35. Ghosh A (2004) Estimating coverage holes and enhancing coverage in mixed sensor networks. In: IEEE international conference on local computer networks, Tampa, USA, pp 68–76

  36. Wang G, Cao GH, Berman P, La Porta TF (2007) Bidding protocols for deploying mobile sensors. IEEE T Mobile Comput 6((5): 515–528

    Google Scholar 

  37. Wang B (2010) Coverage control in sensor networks. Springer, Berlin

    Book  MATH  Google Scholar 

  38. Alsalih W, Islam K, Rodriguez YN, Xiao H (2008) Distributed Voronoi diagram computation in wireless sensor networks. In: ACM symposium on parallelism in algorithms and architectures, Munich, Germany, p 364

  39. Boukerche A, Fei X (2007) A Voronoi approach for coverage protocols in wireless sensor networks. In: IEEE global communications conference, Washington, DC, USA, pp 5190–5194

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

    Article  MathSciNet  Google Scholar 

  41. Zhang H, Hou JC (2005) Maintaining sensing coverage and connectivity in large sensor networks. Wirel Ad hoc Sensor Netw 1(1–2): 89–123

    Google Scholar 

  42. Ahmed N, Kanhere SS, Jha S (2005) Probabilistic coverage in wireless sensor networks. In: IEEE conference on local computer networks, Sydney, Australia, pp 672–681

  43. Hefeeda M, Ahmadi H (2007) A probabilistic coverage protocol for wireless sensor networks. In: IEEE international conference on network protocols, Beijing, China, pp 41–50

  44. Mao G, Fidan B, Anderson BDO (2007) Wireless sensor network localization techniques. Comput Netw 51(10): 2529–2553

    Article  MATH  Google Scholar 

  45. Karp B, Kung HT (2000) GPSR: greedy perimeter stateless routing for wireless networks. In: International conference on mobile computing and networking, Boston, USA, pp 243–254

  46. Khan I, Mokhtar H, Merabti M (2008) A survey of boundary detection algorithms for sensor networks. In: Annual postgraduate symposium on the convergence of telecommunications, networking and broadcasting, Liverpool John Moores University, Liverpool, UK

  47. Braden B (1986) The surveyor’s area formula. Coll Math J 17(4): 326–337

    Article  Google Scholar 

  48. Solovay RM (1970) A model of set-theory in which every set of reals is Lebesgue measurable. Ann Math 92(1): 1–56

    Article  MathSciNet  MATH  Google Scholar 

  49. Zou Y, Chakrabarty K (2004) Sensor deployment and target localization in distributed sensor networks. ACM Trans Embed Comput Syst 3(1): 61–91

    Article  Google Scholar 

  50. Zou Y, Chakrabarty K (2005) A distributed coverage- and connectivity-centric technique for selecting active nodes in wireless sensor networks. IEEE Trans Comput 54(8): 978–991

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Iran University of Science and Technology, Tehran, Iran

    Saeed Sedighian Kashi & Mohsen Sharifi

Authors
  1. Saeed Sedighian Kashi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mohsen Sharifi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Mohsen Sharifi.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Sedighian Kashi, S., Sharifi, M. Coverage rate calculation in wireless sensor networks. Computing 94, 833–856 (2012). https://doi.org/10.1007/s00607-012-0192-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00607-012-0192-1

Keywords

Search

Navigation