Coverage and connectivity in three-dimensional networks

ABSTRACT

Although most wireless terrestrial networks are based on two-dimensional (2D) design, in reality, such networks operate in three-dimensions (3D). Since most often the size (i.e., the length and the width) of such terrestrial networks is significantly larger than the differences in the third dimension (i.e., the height) of the nodes, the 2D assumption is somewhat justified and usually it does not lead to major inaccuracies. However, in some environments, this is not the case; the underwater, atmospheric, or space communications being such apparent examples. In fact, recent interest in underwater acoustic ad hoc and sensor networks hints at the need to understand how to design networks in 3D. Unfortunately, the design of 3D networks is surprisingly more difficult than the design of 2D networks. For example, proofs of Kelvin's conjecture and Kepler's conjecture required centuries of research to achieve breakthroughs, whereas their 2D counterparts are trivial to solve. In this paper, we consider the coverage and connectivity issues of 3D networks, where the goal is to find a node placement strategy with 100% sensing coverage of a 3D space, while minimizing the number of nodes required for surveillance. Our results indicate that the use of the Voronoi tessellation of 3D space to create truncated octahedral cells results in the best strategy. In this truncated octahedron placement strategy, the transmission range must be at least 1.7889 times the sensing range in order to maintain connectivity among nodes. If the transmission range is between 1.4142 and 1.7889 times the sensing range, then a hexagonal prism placement strategy or a rhombic dodecahedron placement strategy should be used. Although the required number of nodes in the hexagonal prism and the rhombic dodecahedron placement strategies is the same, this number is 43.25% higher than the number of nodes required by the truncated octahedron placement strategy. We verify by simulation that our placement strategies indeed guarantee ubiquitous coverage. We believe that our approach and our results presented in this paper could be used for extending the processes of 2D network design to 3D networks.

REFERENCES

• 1: Akyildiz, I.F., Pompili, D., Melodia, T., Underwater Acoustic Sensor Networks: Research Challenges, Ad Hoc Networks Journal, (Elsevier), March 2005.
• 2: Aristotle, On the Heaven, Vol. 3, Chapt. 8, 350BC.
• 3: Stefano Basagni , Imrich Chlamtac , Violet R. Syrotiuk , Barry A. Woodward, A distance routing effect algorithm for mobility (DREAM), Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.76-84, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288254]
• 4: Prosenjit Bose , Pat Morin , Ivan Stojmenović , Jorge Urrutia, Routing with guaranteed delivery in ad hoc wireless networks, Wireless Networks, v.7 n.6, p.609-616, November 2001 [doi>10.1023/A:1012319418150]
• 5: Krishnendu Chakrabarty , S. Sitharama Iyengar , Hairong Qi , Eungchun Cho, Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks, IEEE Transactions on Computers, v.51 n.12, p.1448-1453, December 2002 [doi>10.1109/TC.2002.1146711]
• 6: Jean Carle , Jean-Frédéric Myoupo , David Semé, A Basis for 3-D Cellular Networks, Proceedings of the The 15th International Conference on Information Networking, p.631, January 31-February 02, 2001
• 7: Thomas Clouqueur , Veradej Phipatanasuphorn , Parameswaran Ramanathan , Kewal K. Saluja, Sensor deployment strategy for target detection, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570745]
• 8: Catherine Decayeux and David Semé: A New Model for 3-D Cellular Mobile Networks, ISPDC/HeteroPar 2004.
• 9: Gardner, M. The Sixth Book of Mathematical Games from Scientific American, Chicago, IL: University of Chicago Press, 1984.
• 10: Hales, T. C. A Proof of the Kepler Conjecture. Ann. Math. 162, 1065--1185, 2005
• 11: Hilbert, D. and Cohn-Vossen, S. Geometry and the Imagination. New York: Chelsea, 1999.
• 12: John Heidemann, Wei Ye, Jack Wills, Affan Syed, and Yuan Li. Research Challenges and Applications for Underwater Sensor Networking, IEEE Wireless Communications and Networking Conference, p. to appear. Las Vegas, Nevada, USA, IEEE. April, 2006.
• 13: Johnson, N. W. Uniform Polytopes. Cambridge, England: Cambridge University Press, 2000.
• 14: R. Jain, A. Puri, and R. Sengupta, Geographical routing using partial information for wireless ad hoc networks, IEEE Personal Communications, pp. 48--57, Feb. 2001.
• 15: Jiejun Kong, Jun-hong Cui, Dapeng Wu, Mario Gerla, Building Underwater Ad-hoc Networks and Sensor Networks for Large Scale Real-time Aquatic Applications, IEEE Military Communications Conference (MILCOM'05), October 17--20, 2005. Atlantic City, New Jersey, USA.
• 16: Brad Karp , H. T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proceedings of the 6th annual international conference on Mobile computing and networking, p.243-254, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345953]
• 17: Michal Křížek, Superconvergence phenomena on three-dimensional meshes, International Journal of Numerical Analysis and Modeling. Vol. 2, No. 1, 2005, pp. 43--56.
• 18: Young-Bae Ko , Nitin H. Vaidya, Location-aided routing (LAR) in mobile ad hoc networks, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.66-75, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288252]
• 19: D. Li, K. Wong, Y. H. Hu, and A. Sayeed. Detection, classification and tracking of targets in distributed sensor networks, IEEE Signal Processing Magazine, 19(2), Mar. 2002.
• 20: Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 21: S. Meguerdichian, F. Koushanfar, M. Potkonjak, and M. B. Srivastava. Coverage problems in wireless ad-hoc sensor networks. INFOCOM'01, pages 1380--1387, 2001.
• 22: Theodore Rappaport, Wireless Communications: Principles and Practice, Prentice Hall PTR, Upper Saddle River, NJ, 2001
• 23: Steinhaus, Hugo. Mathematical Snapshots, 3rd edition, Oxford University Press, 1969.
• 24: Di Tian , Nicolas D. Georganas, A coverage-preserving node scheduling scheme for large wireless sensor networks, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570744]
• 25: Thomson, Sir William (Lord Kelvin), On the division of space with minimum partition area. Philosophical Magazine, 24 (1887)503--514. Web: http://zapatopi.net/kelvin/papers/on_the_division_of_space.html
• 26: Pramod K. Varshney, Distributed Detection and Data Fusion, Springer-Verlag New York, Inc., Secaucus, NJ, 1996
• 27: I. Vasilescu , K. Kotay , D. Rus , M. Dunbabin , P. Corke, Data collection, storage, and retrieval with an underwater sensor network, Proceedings of the 3rd international conference on Embedded networked sensor systems, November 02-04, 2005, San Diego, California, USA [doi>10.1145/1098918.1098936]
• 28: Weaire, D. The Kelvin Problem: Foam Structures of Minimal Surface Area. London: Taylor and Francis, 1996.
• 29: Wells, D. The Penguin Dictionary of Curious and Interesting Geometry, London: Penguin, 1991.
• 30: Weyl, H. Symmetry. Princeton, NJ: Princeton University Press, 1952.
• 31: Weaire, D. and Phelan, R. A Counter-Example to Kelvin's Conjecture on Minimal Surfaces. Philosophical Magazine Letters, 69, 107--110, 1994
• 32: Xiaorui Wang , Guoliang Xing , Yuanfang Zhang , Chenyang Lu , Robert Pless , Christopher Gill, Integrated coverage and connectivity configuration in 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.958496]
• 33: Guoliang Xing , Chenyang Lu , Robert Pless , Qingfeng Huang, On greedy geographic routing algorithms in sensing-covered networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989465]
• 34: Ting Yan , Tian He , John A. Stankovic, Differentiated surveillance for 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.958498]
• 35: Fan Ye , Gary Zhong , Jesse Cheng , Songwu Lu , Lixia Zhang, PEAS: A Robust Energy Conserving Protocol for Long-lived Sensor Networks, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.28, May 19-22, 2003
• 36: H. Zhang and J. C. Hou, Maintaining sensing coverage and connectivity in large sensor networks, Wireless Ad Hoc and Sensor Networks: An International Journal, Vol. 1, No. 1-2, pp. 89--123, January 2005.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Design

Keywords:
3D networks, Kelvin's conjecture, connectivity, coverage, hexagonal prism, polyhedron, rhombic dodecahedron, three-dimensional networks, truncated octahedron, underwater networks, wireless networks