Designing localized algorithms for barrier coverage

ABSTRACT

Global barrier coverage that requires much fewer sensors than full coverage, is known to be an appropriate model of coverage for movement detection applications such as intrusion detection. However, it has been proved that given a sensor deployment, sensors can not locally determine whether the deployment provides global barrier coverage, making it impossible to develop localized algorithms, thus limiting its use in practice.

In this paper, we introduce the concept of local barrier coverage to address this limitation. Motivated by the observation that movements are likely to follow a shorter path in crossing a belt region, local barrier coverage guarantees the detection of all movements whose trajectory is confined to a slice of the belt region of deployment. We prove that it is possible for individual sensors to locally determine the existence of local barrier coverage, even when the region of deployment is arbitrarily curved. Although local barrier coverage does not always guarantee global barrier coverage, we show that for thin belt regions, local barrier coverage almost always provides global barrier coverage. To demonstrate that local barrier coverage can be used to design localized algorithms, we develop a novel sleep-wakeup algorithm for maximizing the network lifetime, called Localized Barrier Coverage Protocol (LBCP). We show that LBCP provides close to optimalenhancement in network lifetime, while providing global barrier coverage most of the time. It outperforms an existing algorithm called Randomized Independent Sleeping (RIS) by up to 6 times.

REFERENCES

• 1: Mica2 Datasheet. http://www.xbow.com/Products/Product_pdf_files/Wireless_pdf/MICA2_Datasheet.pdf.
• 2: Paul Balister , Béla Bollobas , Amites Sarkar , Santosh Kumar, Reliable density estimates for coverage and connectivity in thin strips of finite length, 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.1287863]
• 3: M. Cardei, M. Thai, and W. Wu. Energy-Efficient Target Coverage in Wireless Sensor Networks. In Proc. IEEE INFOCOM, 2005.
• 4: Tian He , Sudha Krishnamurthy , John A. Stankovic , Tarek Abdelzaher , Liqian Luo , Radu Stoleru , Ting Yan , Lin Gu , Jonathan Hui , Bruce Krogh, Energy-efficient surveillance system using 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.990096]
• 5: 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]
• 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: 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]
• 8: 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.
• 9: B. Kuris and T. Dishongh. SHIMMER Mote:Hardware Guide. Online at http://www.eecs.harvard.edu/~konrad/projects/shimmer/references/SHIMMER_HWGuide_REV1P3.pdf, 2006.
• 10: Joseph Polastre , Robert Szewczyk , David Culler, Telos: enabling ultra-low power wireless research, Proceedings of the 4th international symposium on Information processing in sensor networks, April 24-27, 2005, Los Angeles, California
• 11: A. Schrijver. Combinatorial Optimization. Springer, 2003.
• 12: S. Slijepcevic and M. Potkonjak. Power Efficient Organization of Wireless Sensor Networks. In ICC, Helsinki, Finland, 2001.
• 13: 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.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Theory

Keywords:
coverage, local barrier coverage, localized algorithms, network topology, wireless sensor networks