Reliable density estimates for coverage and connectivity in thin strips of finite length

ABSTRACT

Deriving the critical density (which is equivalent to deriving the critical radius or power) to achieve coverage and/or connectivity for random deployments is a fundamental problem in the area of wireless networks. The probabilistic conditions normally derived, however, have limited appeal among practitioners because they areoften asymptotic, i.e., they only make high probability guarantees in the limit of large system sizes. Such conditions are not very useful in practice since deployment regions are always finite. Another major limitation of most existing work on coverage and connectivity is their focus on thick deployment regions (such as a square or a disk). There is no existing work (including traditional percolation theory) that derives critical densities for thin strips (or annuli).

In this paper, we address both of these shortcomings by introducing new techniques for deriving reliable density estimates for finite regions (including thin strips). We apply our techniques to solve the open problem of deriving reliable density estimates for achieving barrier coverage and connectivity in thin strips, where sensors are deployed as a barrier to detect moving objects and phenomena. We use simulations to show that our estimates are accurate even for small deployment regions. Our techniques bridge the gap between theory and practice in the area of coverage and connectivity, since the results can now be readily used in real-life deployments.

References

1. P. Balister, B. Bollobas, A. Sarkar, and S. Kumar. Reliable density estimates for coverage and connectivity in thin strips of finite length. Technical report, University of Memphis, Available at: https://umdrive.memphis.edu/pbalistr/public/ThinStripComplete.pdf, 2007.
2. P. Balister, B. Bollobás, A. Sarkar, and M. Walters. Connectivity of random k-nearest-neighbour graphs. Advances in Applied Probability, 37:1--24, 2005.
3. P. Balister, B. Bollobás, and M. Walters. Continuum percolation with steps in the square or the disk. Random Structures & Algorithms, 26:392--403, 2005.
4. B. Bollobás. Random Graphs. Camridge University Press, 2001.
5. Q. Cao, T. Yan, J. A. Stankovic, , and T. F. Abdelzaher. Analysis of target detection performance for wireless sensor networks. In DCOSS, 2005.
6. M. Cardei, M. Thai, and W. Wu. Energy-efficient target coverage in wireless sensor networks. In IEEE INFOCOM, 2005.
7. O. Dousse, F. Baccelli, and P. Thiran. Impact of interferences on connectivity in ad hoc networks. IEEE/ACM Transactions on Networking, 13(2):425--436, 2005.
8. O. Dousse, P. Thiran, and M. Hasler. Connectivity in ad-hoc and hybrid networks. In IEEE Infocom, 2002.
9. R. B. Ellis, X. Jia, and C. Yan. On random points in the unit disk. Random Structures and Algorithms, 29(1):14--35, 2006.
10. E. Gilbert. Random plane networks. Journal of the Society for Industrial Applied Mathematics, 9:533--543, 1961.
11. E. Gilbert. The probability of covering a sphere with n circular caps. Biometrika, 56:323--330, 1965.
12. P. Gupta and P. R. Kumar. Critical power for asymptotic connectivity in wireless networks. In IEEE 37th Conference on Decision and Control, pages 1106--1110, Tampa, FL, 1998.
13. P. Hall. On the Coverage of k-Dimensional Space by k-Dimensional Spheres. Annals of Probability, 13(3):991--1002, 1985.
14. S. Kumar, T. H. Lai, and A. Arora. Barrier coverage with wireless sensors. In ACM MobiCom, pages 284--298, Cologne, Germany, 2005.
15. S. Kumar, T. H. Lai, and J. Balogh. On k-coverage in a mostly sleeping sensor network. In ACM MobiCom, pages 144--158, Philadelphia, PA, 2004.
16. S. Kumar, T. H. Lai, M. E. Posner, and P. Sinha. Optimal Sleep Wakeup Algorithms for Barriers of Wireless Sensors. In Fourth International Conference on Broadband Communications, Networks, and Systems (IEEE BROADNETS), Raleigh, NC, 2007.
17. X. Y. Li, P. J. Wan, Y. Wang, and C. Yi. Fault tolerant deployment and topology control in wireless networks. In ACM MobiHoc, pages 117--28, Annapolis, MD, 2003.
18. M. D. Penrose. Random Geometric Graphs. Oxford University Press, 2003.
19. E. Peserico and L. Rudolph. Robust network connectivity: when it's the big picture that matters. SIGMETRICS Perform. Evaluation Review, 34(1):299--310, 2006.
20. S. Quintanilla, S. Torquato, and R. Ziff. Efficient measurement of the percolation threshold for fully penetrable discs. J. Phys. A: Math. Gen, 33(42):L399--L407, 2000.
21. P. Santi. The critical transmitting range for connectivity in mobile ad hoc networks. IEEE Transactions in Mobile Computing, 4(3):310--317, 2005.
22. S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In ICC, 2001.
23. P. Wan and C. Yi. Coverage by randomly deployed wireless sensor networks. IEEE Transactions on Information Theory, 52:2658--2669, 2006.
24. F. Xue and P. R. Kumar. The number of neighbors needed for connectivity of wireless networks. In Wireless Networks, volume 10, pages 169--181, March 2004.
25. H. Zhang and J. Hou. Maintaining sensing coverage and connectivity in large sensor networks. In NSF International Workshop on Theoretical and Algorithmic Aspects of Sensor, Ad Hoc Wirelsss, and Peer-to-Peer Networks, 2004.
26. H. Zhang and J. Hou. On deriving the upper bound of α-lifetime for large sensor networks. In ACM MobiHoc, pages 121--132, Tokyo, Japan, 2004.
27. G. Zhou, T. He, S. Krishnamurthy, and J. A. Stankovic. Impact of radio irregularity on wireless sensor networks. In ACM MobiSys, Boston, MA, 2004.

Index Terms

• Mathematics of computing

  • Probability and statistics

    • Stochastic processes

• Networks

  • Network properties

    • Network structure