Strong barrier coverage of wireless sensor networks

ABSTRACT

Constructing sensor barriers to detect intruders crossing a randomly-deployed sensor network is an important problem. Early results have shown how to construct sensor barriers to detect intruders moving along restricted crossing paths in rectangular areas. We present a complete solution to this problem for sensors that are distributed according to a Poisson point process. In particular, we present an efficient distributed algorithm to construct sensor barriers on long strip areas of irregular shape without any constraint on crossing paths. Our approach is as follows: We first show that in a rectangular area of width w and length l with w = Ω(log l), if the sensor density reaches a certain value, then there exist, with high probability, multiple disjoint sensor barriers across the entire length of the area such that intruders cannot cross the area undetected. On the other hand, if w = o(log l), then with high probability there is a crossing path not covered by any sensor regardless of the sensor density. We then devise, based on this result, an efficient distributed algorithm to construct multiple disjoint barriers in a large sensor network to cover a long boundary area of an irregular shape. Our algorithm approximates the area by dividing it into horizontal rectangular segments interleaved by vertical thin strips. Each segment and vertical strip independently computes the barriers in its own area. Constructing "horizontal" barriers in each segment connected by "vertical" barriers in neighboring vertical strips, we achieve continuous barrier coverage for the whole region. Our approach significantly reduces delay, communication overhead, and computation costs compared to centralized approaches. Finally, we implement our algorithm and carry out a number of experiments to demonstrate the effectiveness of constructing barrier coverage.

REFERENCES

• 1: Ai Chen , Santosh Kumar , Ten H. Lai, Designing localized algorithms for barrier coverage, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287862]
• 2: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 3: M. Franceschetti, O. Dousse, D. Tse, and P. Thiran. Closing the gap in the capacity of random wireless networks. In Proc. of Information Theory Symposium (ISIT), 2004.
• 4: D. Gage. Command control for many-robot systems. In Proc. of the Nineteenth Annual AUVS Technical Symposium (AUVS-92), 1992.
• 5: G. R. Grimmett. Percolation. Springer, 1999.
• 6: 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]
• 7: X.-Y. Li, P.-J. Wan, and O. Frieder. Coverage in wireless ad-hoc sensor networks. IEEE Transactions on Computers, 52(6):753--763, June 2003.
• 8: B. Liu and D. Towsley. A study on the coverage of large-scale sensor networks. In The 1st IEEE International Conference on Mobile Ad-hoc and Sensor Systems, 2004.
• 9: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. In Proc. IEEE Infocom, pages 1380--1387, 2001.
• 10: 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]
• 11: A. Schrijver. Combinatorial Optimization. Springer, 2003.
• 12: 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]

INDEX TERMS

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

General Terms:
Performance, Theory

Keywords:
algorithm, coverage, sensor networks