Low-connectivity and full-coverage three dimensional wireless sensor networks

ABSTRACT

Low-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, we design a set of patterns for these networks. In particular, we design and prove the optimality of 1- and 2-connectivity patterns under any value of the ratio of communication range r_c over sensing range r_s, among regular lattice deployment patterns. We further propose a set of patterns to achieve 3- and 4-connectivity patterns and investigate the evolutions among all the proposed low-connectivity patterns. Finally, we study the proposed patterns under several practical settings.

REFERENCES

• 1: M. Campbell, "Intelligence in three dimensions: we live in a 3-dworld, and so should computers," http://www.neptec.com/News2006/1Oct06-MilAero.html, 2006.
• 2: M.K. Watfa, "Practical applications and connectivity: Algorithmsin future wireless sensor networks," International Journal of Information Technolog, vol. 4, pp. 18--28, 2007.
• 3: "Aerial common sensor (acs)," http://www.global-security.org/intell/systems/acs.htm, 2007.
• 4: W. Tsujita, A. Yoshino, H. Ishida, T. Moriizumi, "Gas sensornetwork for air-pollution monitoring," Sensors and ActuatorsB: Chemical, Vol. 110, no. 2, pp. 304--311, 2005.
• 5: Jim Partan , Jim Kurose , Brian Neil Levine, A survey of practical issues in underwater networks, Proceedings of the 1st ACM international workshop on Underwater networks, September 25-25, 2006, Los Angeles, CA, USA [doi>10.1145/1161039.1161045]
• 6: J. Heidemann, W. Ye, J. Wills, A. Syed, and Y. Li, "Research challenges and applications for underwater sensor networking," in Proc. of IEEE Wireless Communications and Networking Conference (WCNC), 2006.
• 7: W. Cheng, A. Teymorian, L. Ma, X. Cheng, X. Lu, and Z. Lu, "Underwater localization in sparse 3d acoustic sensor networks," in Proc. of IEEE Annual Conference on Computer Communications (IEEE INFOCOM), 2008.
• 8: Thomson and S.W.L. Kelvin, "On the division of space with minimumpartition area," Philosophical Magazine, no. 24, pp. 503--514, 1887.
• 9: R.P. Bambah, "On lattice coverings by spheres," in Proc. of Nat. Sci. India, no. 10, pp. 25--52, 1954.
• 10: E.S. Barnes, "The covering of space by spheres," Canad. J.Math., no. 8, pp. 293--304, 1956.
• 11: L. Few, "Covering space by spheres," Mathematika, no. 3,pp. 136--139, 1956.
• 12: R.P. Bambah, "Lattice coverings with four-dimensional spheres," in Proc. Cambridge Phil. Soc., no. 50, pp. 203--208, 1954.
• 13: M.N. Bleicher, "Lattice coverings of n-space by spheres," Canad. J. Math., no. 14, pp. 632--650, 1962.
• 14: H.S.M. Coxeter, Introduction to Geometry. New York: John Wiley, 1961.
• 15: T.C. Hales, "A proof of the kepler conjecture," Annals of Mathematics, no. 162, pp. 1065--1185, 2005.
• 16: N. Sloane, "The proof of the packing," Nature, vol. 425, pp. 126--127, 2003.
• 17: G.G. Szpiro, Kepler's Conjecture: How Some of the Greatest Minds in History Helped Solve One of the Oldest Math Problems in the World. John Wiley Sons, Inc., 2003.
• 18: Xiaole Bai , Santosh Kumar , Dong Xuan , Ziqiu Yun , Ten H. Lai, Deploying wireless sensors to achieve both coverage and connectivity, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132921]
• 19: X. Bai, Z. Yun, D. Xuan, T.H. Lai, and W. Jia, "Deploying four-connectivity and full-coverage wireless sensor networks," in Proc. of IEEE Annual Conference on Computer Communications (IEEE INFOCOM), 2008.
• 20: Xiaole Bai , Dong Xuan , Ziqiu Yun , Ten H. Lai , Weijia Jia, Complete optimal deployment patterns for full-coverage and k-connectivity (k≤6) wireless sensor networks, Proceedings of the 9th ACM international symposium on Mobile ad hoc networking and computing, May 26-30, 2008, Hong Kong, Hong Kong, China [doi>10.1145/1374618.1374672]
• 21: S. M. Nazrul Alam , Zygmunt J. Haas, Coverage and connectivity in three-dimensional networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161128]
• 22: M.K. Watfa and S. Commuri, "A coverage algorithm in 3d wireless sensor networks," The 1st International Symposium on Wireless Pervasive Computing, 2006.
• 23: C.F. Huang, Y.C. Tseng, and L.C. Lo, "The coverage problem in three-dimensional wireless sensor networks," in Proc. of IEEE Global Communications Conference (Globecom), 2004.
• 24: H. Yan, Z. Shi, and J. Cui, "Dbr: Depth-based routing forunder water sensor networks," IFIP Networking, 2008.
• 25: Dario Pompili , Tommaso Melodia, Three-dimensional routing in underwater acoustic sensor networks, Proceedings of the 2nd ACM international workshop on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks, October 10-13, 2005, Montreal, Quebec, Canada [doi>10.1145/1089803.1089988]
• 26: Z. Zhou, J. Cui, and A. Bagtzoglou, "Scalable localization withmobility prediction for underwater sensor networks," in Proc. of IEEE Annual Conference on Computer Communications (IEEE INFOCOM), 2008.
• 27: Seapahn Megerian , Farinaz Koushanfar , Gang Qu , Giacomino Veltri , Miodrag Potkonjak, Exposure in wireless sensor networks: theory and practical solutions, Wireless Networks, v.8 n.5, p.443-454, September 2002 [doi>10.1023/A:1016586011473]
• 28: Y. Zhou and K. Charkrabarty, "Sensor deployment and target localization based on virtual force," in Proc. of IEEE Annual Conference on Computer Communications (IEEE INFOCOM), 2003.
• 29: Q. Cao, T. Yan, J.A. Stankovic, and T.F. Abdelzaher, "Analysis of target detection performance for wireless sensor networks," in Proc. of International Conference on Distributed Computing in Sensor Systems (DCOSS), 2005.
• 30: M. Zuniga and B. Krishnamachari, "Analyzing the transitional region in low power wireless links," Technical Report 04-823, University of Southen California, 2004.
• 31: X. Bai, C. Zhang, D. Xuan and W. Jia, "Full-Coverage and k-Connectivity (k=14, 6) Three Dimensional Networks," in Proc. of IEEE Annual Conference on Computer Communications (IEEE INFOCOM), 2009.

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, wireless sensor network topology