Barrier coverage with wireless sensors

ABSTRACT

In old times, castles were surrounded by moats (deep trenches filled with water, and even alligators) to thwart or discourage intrusion attempts. One can now replace such barriers with stealthy and wireless sensors. In this paper, we develop theoretical foundations for laying barriers of wireless sensors. We define the notion of k-barrier coverage of a belt region using wireless sensors. We propose efficient algorithms using which one can quickly determine, after deploying the sensors, whether a region is k-barrier covered. Next, we establish the optimal deployment pattern to achieve k-barrier coverage when deploying sensors deterministically. Finally, we consider barrier coverage with high probability when sensors are deployed randomly. We introduce two notions of probabilistic barrier coverage in a belt region -- weak and strong barrier coverage. While weak barrier-coverage with high probability guarantees the detection of intruders as they cross a barrier of stealthy sensors, a sensor network providing strong barrier-coverage with high probability (at the expense of more sensors) guarantees the detection of all intruders crossing a barrier of sensors, even when the sensors are not stealthy. Both types of barrier coverage require significantly less number of sensors than full-coverage, where every point in the region needs to be covered. We derive critical conditions for weak k-barrier coverage, using which one can compute the minimum number of sensors needed to provide weak k-barrier coverage with high probability in a given belt region. Deriving critical conditions for strong k-barrier coverage for a belt region is still an open problem.

REFERENCES

• 1: Extreme scale wireless sensor networking. Technical report, http://www.cse.ohio-state.edu/exscal, 2004.
• 2: N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley & Sons, 2000.
• 3: A. Arora , P. Dutta , S. Bapat , V. Kulathumani , H. Zhang , V. Naik , V. Mittal , H. Cao , M. Demirbas , M. Gouda , Y. Choi , T. Herman , S. Kulkarni , U. Arumugam , M. Nesterenko , A. Vora , M. Miyashita, A line in the sand: a wireless sensor network for target detection, classification, and tracking, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.46 n.5, p.605-634, 5 December 2004 [doi>10.1016/j.comnet.2004.06.007]
• 4: K. Boroczky. Finite Packing and Covering. Cambridge University Press, 2004.
• 5: H. S. M. Coxeter. Introduction to Geometry. New York, Wiley, 1969.
• 6: D. W. Gage. Command control for many-robot systems. In AUVS-92, 1992.
• 7: Chao Gui , Prasant Mohapatra, Power conservation and quality of surveillance in target tracking sensor networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023734]
• 8: P. Hall. Introduction to the Theory of Coverage Processes. John Wiley & Sons, 1988.
• 9: Chi-Fu Huang , Yu-Chee Tseng, The coverage problem in a wireless sensor network, Proceedings of the 2nd ACM international conference on Wireless sensor networks and applications, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/941350.941367]
• 10: S. Hynes. Multi-agent simulations (mas) for assessing massive sensor coverage and deployment. Technical report, Master's Thesis, Naval Postgraduate School, 2003.
• 11: S. Kumar and A. Arora. Echelon topology for node deployment. Technical report, ExScal Note Series: ExScal-OSU-EN00-2004-01-30, The Ohio State University, 2004.
• 12: 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]
• 13: R. P. Langlands, C. Pichet, P. Pouliot, and Y. Saint-Aubin. On the universality of crossing probabilities in two-domensional percolation. Journal of Statistical Physics, 67(3/4):553--574, 1992.
• 14: B. Liu and D. Towsley. On the coverage and detectability of large-scale wireless sensor networks. In Modeling and Optimization in Mobile, Ad-Hoc and Wireless Networks, 2003.
• 15: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In IEEE INFOCOM, 2001.
• 16: Seapahn Meguerdichian , Farinaz Koushanfar , Gang Qu , Miodrag Potkonjak, Exposure in wireless Ad-Hoc sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.139-150, July 2001, Rome, Italy [doi>10.1145/381677.381691]
• 17: Bojan Mohar , Neil Robertson, Disjoint essential cycles, Journal of Combinatorial Theory Series B, v.68 n.2, p.324-349, Nov. 1996 [doi>10.1006/jctb.1996.0073]
• 18: B. Mohar and C. Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.
• 19: David Peleg, Distributed computing: a locality-sensitive approach, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 20: S. M. Ross. Introduction to Probability Models. Academic Press, 2000.
• 21: A. Schrijver. Combinatorial Optimization. Springer, 2003.
• 22: Giacomino Veltri , Qingfeng Huang , Gang Qu , Miodrag Potkonjak, Minimal and maximal exposure path algorithms for wireless embedded sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958497]
• 23: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958496]
• 24: D. B. West. Introduction to Graph Theory. Prentice Hall, 2001.
• 25: 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]

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:
Algorithms, Theory

Keywords:
barrier coverage, coverage, critical conditions, localized algorithms, network topology, random geometric graphs, wireless sensor networks