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 rc/rs, where rc is the communication radius, and rs is the sensing radius. We also prove the optimality of a previously proposed deployment pattern for achieving both full coverage and 1-connectivity, when rc/rs < √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.
- A. Arora and et. al. ExScal: Elements of an Extreme Scale Wireless Sensor Network. In 11th IEEE International Conference on Real-Time Computing Systems and Applications (IEEE RTCSA), Hong Kong, 2005. Google ScholarDigital Library
- S. Bapat, V. Kulathumani, and A. Arora. Analyzing the Yield of ExScal, a Large Scale Wireless Sensor Network Experiment. In 13th IEEE International Conference on Network Protocols (ICNP), Boston, MA, 2005. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- F. S. Hillier and G. J. Lieberman. Introduction to Operations Research. McGraw-Hill, 2002. Google ScholarDigital Library
- R. Iyengar, K. Kar and S. Banerjee. Low-coordination Topologies for Redundancy in Sensor Networks. In the Sixth ACM Annual International Symposium on Mobile Ad-Hoc Networking and Computing (MobiHoc), pages 332--342, Urbana-Champaign, IL, 2005. Google ScholarDigital Library
- R. Kershner. The Number of Circles Covering a Set. American Journal of Mathematics, 61:665--671, 1939.Google ScholarCross Ref
- Y.-C. Wang, C.-C. Hu, and Y.-C. Tseng. Efficient Deployment Algorithms for Ensuring Coverage and Connectivity of Wireless Sensor Networks. In Wireless International Conference (WICON), Budapest, Hungary, 2005. Google ScholarDigital Library
- G. Xing, X. Wang, Y. Zhang, C. Lu, R. Pless, and C. Gill. Integrated Coverage and Connectivity Configuration in Wireless Sensor Networks. ACM Transactions on Sensor Networks, 1(1):36--72, 2005. Google ScholarDigital Library
- 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.Google Scholar
- J. Zhao and R. Govindan. Understanding Packet Delivery Performance in Dense Wireless Sensor Networks. In ACM Conference on Ebmedded Networked Sensor Systems (SenSys), pages 1--13, Los Angeles, CA, 2003. Google ScholarDigital Library
- G.Zhou, T. He, S. Krishnamurthy, and J. A. Stankovic. Impact of Radio Irregularity on Wireless Sensor Networks. In ACM MobiSys, pages 125--138, Boston, MA, 2004. Google ScholarDigital Library
Index Terms
- Deploying wireless sensors to achieve both coverage and connectivity
Recommendations
Connectivity preserving localized coverage algorithm for area monitoring using wireless sensor networks
Efficient network coverage and connectivity are the requisites for most Wireless Sensor Network (WSN) deployments, particularly those concerned with area monitoring. Due to the resource constraints of the sensor nodes, redundancy of coverage area must ...
Low-connectivity and full-coverage three dimensional wireless sensor networks
MobiHoc '09: Proceedings of the tenth ACM international symposium on Mobile ad hoc networking and computingLow-connectivity and full-coverage three dimensional Wireless Sensor Networks (WSNs) have many real-world applications. By low connectivity, we mean there are at least k disjoint paths between any two sensor nodes in a WSN, where k ≤ 4. In this paper, ...
Constructing low-connectivity and full-coverage three dimensional sensor networks
Special issue on simple wireless sensor networking solutionsLow-connectivity and full-coverage three dimensional Wireless Sensor Networks (WSNs) have many real-world applications. By low connectivity, we mean there are at least k disjoint paths between any two sensor nodes in a WSN, where k ≤ 4. In this paper, ...
Comments