ABSTRACT
In this paper, we propose deployment patterns to achieve full coverage and three-connectivity, and full coverage and five-connectivity under different ratios of sensor communication range (denoted by Rc) over sensing range (denoted by Rs) for wireless sensor networks (WSNs). We also discover that there exists a hexagon-based universally elemental pattern which can generate all known optimal patterns. The previously proposed Voronoi-based approach can not be applied to prove the optimality of the new patterns due to their special features. We propose a new deployment-polygon based methodology, and prove their optimality among regular patterns when Rc/Rs ≥ 1. We conjecture that our patterns are globally optimal to achieve full coverage and three-connectivity, and full coverage and five-connectivity, under all ranges of Rc/Rs. With these new results, the set of optimal patterns to achieve full coverage and k-connectivity (k≤6) is complete, for the first time.
- A. Arora, et. al. ExScal: Elements of an Extreme Scale Wireless Sensor Network. In 11th IEEE International Conference on Real-Time Computing Systems and Applications, 2005. Google ScholarDigital Library
- A. Arora, et. al. A Line in the Sand: A Wireless Sensor Network for Target Detection Classification and Tracking. Computer Networks, 2004. Google ScholarDigital Library
- X. Bai, S. Kumar, D. Xuan, Z. Yun and T. H. Lai. Deploying Wireless Sensors to Achieve Both Coverage and Connectivity, ACM Mobihoc, 2006. Google ScholarDigital Library
- X. Bai, Z. Yun, D. Xuan, T. H. Lai and W. Jia. Deploying Four-Connectivity And Full-Coverage Wireless Sensor Networks. IEEE INFOCOM, 2008.Google ScholarCross Ref
- Q. Cao, T. Yan, J. A. Stankovic, and T. F. Abdelzaher. Analysis of Target Detection Performance for Wireless Sensor Networks. International Conference on Distributed Computing in Sensor Networks, 2005. Google ScholarDigital Library
- R. Iyengar, K. Kar and S. Banerjee. Low-coordination Topologies for Redundancy in Sensor Networks. ACM Mobihoc, 2005. Google ScholarDigital Library
- R. Kershner. The Number of Circles Covering a Set. American Journal of Mathematics, 1939.Google ScholarCross Ref
- research.cens.ucla.edu/projects/2006/Contaminant/Multiscale Soil/default.htmGoogle Scholar
- R. Narayana Murty, et. al. www.eecs.harvard.edu/~mdw/papers/citysense-techrept07.pdf.Google Scholar
- T. Moscibroda, R. Wattenhofer and A. Zollinger, Topology Control Meets SINR: The Scheduling Complexity of Arbitrary Topologies, ACM Mobihoc, 2006. Google ScholarDigital Library
Index Terms
- Complete optimal deployment patterns for full-coverage and k-connectivity (k≤6) wireless sensor networks
Recommendations
Deploying wireless sensors to achieve both coverage and connectivity
MobiHoc '06: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computingIt 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 ...
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, ...
Optimal deployment patterns for full coverage and k- connectivity (k ≤ 6) wireless sensor networks
In this paper, we study deployment patterns to achieve full coverage and k-connectivity (k ≤ 6) under different ratios of the sensor communication range (denoted by Rc) to the sensing range (denoted by Rs) for homogeneous wireless sensor networks (WSNs)...
Comments