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: Paul Balister , Béla Bollobás_aff1n2 , Mark Walters_aff1n2, Continuum percolation with steps in the square or the disc, Random Structures & Algorithms, v.26 n.4, p.392-403, July 2005 [doi>10.1002/rsa.v26:4]
• 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: Olivier Dousse , François Baccelli , Patrick Thiran, Impact of interferences on connectivity in ad hoc networks, IEEE/ACM Transactions on Networking (TON), v.13 n.2, p.425-436, April 2005 [doi>10.1109/TNET.2005.845546]
• 8: O. Dousse, P. Thiran, and M. Hasler. Connectivity in ad-hoc and hybrid networks. In IEEE Infocom, 2002.
• 9: Robert B. Ellis , Xingde Jia , Catherine Yan, On random points in the unit disk, Random Structures & Algorithms, v.29 n.1, p.14-25, August 2006 [doi>10.1002/rsa.v29:1]
• 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: Santosh Kumar , Ten H. Lai , Anish Arora, Barrier coverage with wireless sensors, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080859]
• 15: Santosh Kumar , Ten H. Lai , József Balogh, On k-coverage in a mostly sleeping sensor network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023735]
• 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: Xiang-Yang Li , Peng-Jun Wan , Yu Wang , Chih-Wei Yi, Fault tolerant deployment and topology control in wireless networks, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778431]
• 18: M. D. Penrose. Random Geometric Graphs. Oxford University Press, 2003.
• 19: Enoch Peserico , Larry Rudolph, Robust network connectivity: when it's the big picture that matters, ACM SIGMETRICS Performance Evaluation Review, v.34 n.1, June 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: Paolo Santi, The Critical Transmitting Range for Connectivity in Mobile Ad Hoc Networks, IEEE Transactions on Mobile Computing, v.4 n.3, p.310-317, May 2005 [doi>10.1109/TMC.2005.45]
• 22: S. Slijepcevic and M. Potkonjak. Power efficient organization of wireless sensor networks. In ICC, 2001.
• 23: Peng-Jun Wan , Chih-Wei Yi, Coverage by randomly deployed wireless sensor networks, IEEE/ACM Transactions on Networking (TON), v.14 n.SI, p.2658-2669, June 2006 [doi>10.1109/TIT.2005.862092]
• 24: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]
• 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: Honghai Zhang , Jennifer Hou, On deriving the upper bound of α-lifetime for large sensor networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989475]
• 27: Gang Zhou , Tian He , Sudha Krishnamurthy , John A. Stankovic, Impact of radio irregularity on wireless sensor networks, Proceedings of the 2nd international conference on Mobile systems, applications, and services, June 06-09, 2004, Boston, MA, USA [doi>10.1145/990064.990081]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Stochastic processes

General Terms:
Theory

Keywords:
barrier coverage, connectivity, coverage, critical, deployment, network topology, random geometric graphs, wireless sensor networks