Deploying wireless sensors to achieve both coverage and connectivity

ABSTRACT

It is well-known that placing disks in the triangular lattice pattern is optimal for achieving full coverage on a plane. With the emergence of wireless sensor networks, however, it is now no longer enough to consider coverage alone when deploying a wireless sensor network; connectivity must also be con-sidered. While moderate loss in coverage can be tolerated by applications of wireless sensor networks, loss in connectivity can be fatal. Moreover, since sensors are subject to unanticipated failures after deployment, it is not enough to have a wireless sensor network just connected, it should be k-connected (for k > 1 ). In this paper, we propose an optimal deployment pattern to achieve both full coverage and 2-connectivity, and prove its optimality for all values of r_c/r_s, where r_c is the communication radius, and r_s is the sensing radius. We also prove the optimality of a previously proposed deployment pattern for achieving both full coverage and 1-connectivity, when r_c/r_s < √3 .Finally, we compare the efficiency of some popular regular deployment patterns such as the square grid and triangular lattice, in terms of the number of sensors needed to provide coverage and connectivity.

REFERENCES

• 1: Anish Arora , Rajiv Ramnath , Emre Ertin , Prasun Sinha , Sandip Bapat , Vinayak Naik , Vinod Kulathumani , Hongwei Zhang , Hui Cao , Mukundan Sridharan , Santosh Kumar , Nick Seddon , Chris Anderson , Ted Herman , Nishank Trivedi , Chen Zhang , Mikhail Nesterenko , Romil Shah , Sandeep Kulkarni , Mahesh Aramugam , Limin Wang , Mohamed Gouda , Young-ri Choi , David Culler , Prabal Dutta , Cory Sharp , Gilman Tolle , Mike Grimmer , Bill Ferriera , Ken Parker, ExScal: Elements of an Extreme Scale Wireless Sensor Network, Proceedings of the 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), p.102-108, August 17-19, 2005 [doi>10.1109/RTCSA.2005.47]
• 2: Sandip Bapat , Vinodkrishnan Kulathumani , Anish Arora, Analyzing the Yield of ExScal, a Large-Scale Wireless Sensor Network Experiment, Proceedings of the 13TH IEEE International Conference on Network Protocols (ICNP'05), p.53-62, November 06-09, 2005 [doi>10.1109/ICNP.2005.7]
• 3: Q. Cao, T. Yan, J.A. Stankovic,and T. F. Abdelzaher. Analysis of Target Detection Performance for Wireless Sensor Networks. In International Conference on Distributed Computing in Sensor Networks (DCOSS), 2005.
• 4: Frederick S. Hillier , Gerald J. Lieberman, Introduction to operations research, 4th ed., Holden-Day, Inc., San Francisco, CA, 1986
• 5: Rajagopal Iyengar , Koushik Kar , Suman Banerjee, Low-coordination topologies for redundancy in sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062732]
• 6: R. Kershner. The Number of Circles Covering a Set. American Journal of Mathematics, 61:665--671, 1939.
• 7: You-Chiun Wang , Chun-Chi Hu , Yu-Chee Tseng, Efficient Deployment Algorithms for Ensuring Coverage and Connectivity ofWireless Sensor Networks, Proceedings of the First International Conference on Wireless Internet, p.114-121, July 10-15, 2005 [doi>10.1109/WICON.2005.13]
• 8: Guoliang Xing , Xiaorui Wang , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration for energy conservation in sensor networks, ACM Transactions on Sensor Networks (TOSN), v.1 n.1, p.36-72, August 2005 [doi>10.1145/1077391.1077394]
• 9: 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.
• 10: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense 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.958493]
• 11: 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

General Terms:
Theory

Keywords:
connectivity, coverage, optimal deployment pattern