Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc networks

ABSTRACT

A range assignment to the nodes in a wireless ad hoc network induces a topology in which there is an edge between two nodes if and only if both of them are within each other's transmission range. The critical transmission radius for k-connectivity is the smallest r such that if all nodes have the transmission radius r,the induce topology is k-connected. The critical neighbor number for k-connectivity is the smallest integer l such that if every node sets its transmission radius equal to the distance between itself an its l-th nearest neighbor, the induce topology is k-connecte. In this paper, we study the asymptotic critical transmission radius for k-connectivity an asymptotic critical neighbor number for k-connectivity in a wireless ad hoc network whose nodes are uniformly an independently distribute in a unit-area square or disk. We provide a precise asymptotic distribution of the critical transmission radius for k-connectivity and an improve asymptotic almost sure upper bound on the critical neighbor number for k-connectivity.

REFERENCES

• 1: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 2: Cheng, Y.-C., and Robertazzi, T. G. Critical connectivity phenomena in multihop radio models. IEEE Transactions on Communications 37, 7 (July 1989), 770--777.
• 3: Dette, H., and Henze, N. The limit distribution of the largest nearest-neighbour link in the unit d-cube. Journal of Applied Probability 26 (1989), 67--80.
• 4: Dette, H., and Henze, N. Some peculiar boundary phenomena for extremes of rth nearest neighbor links. Statistics & Probability Letters 10 (1990), 381--390.
• 5: Dousse, O., Thiran, P., and Hasler, M. Connectivity in ad-hoc and hybrid networks. In Proceedings of the 21st Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE INFOCOM 2002) (June 23-27 2002), vol. 2, pp. 1079--1088.
• 6: Gupta, P., and Kumar, P. R. Critical power for asymptotic connectivity in wireless networks. In Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming (March 1998), W. M. McEneaney, G. Yin, and Q. Zhang, Eds., Birkhauser, pp. 547--566.
• 7: Hajek, B. Adaptive transmission strategies and routing in mobile radio networks. In Proceedings of the Conference Information Sciences and Systems (March 1983), pp. 373--378.
• 8: Hou, T.-C., and Li, V. O. Transmission range control in multihop packet radio networks. IEEE Transactions on Communications COM-34, 1 (January 1986), 38--44.
• 9: Kleinrock, L., and Silvester, J. A. Optimum transmission radii for packet radio networks or why six is a magic number. In IEEE Nat. Telecommun. Conf. (December 1978), pp. 4.3.1--4.3.5.
• 10: Krishnamachari, B., Wicker, S. B., and Béjar, R. Phase transition phenomena in wireless ad hoc networks. In IEEE Global Telecommunications Conference (GLOBECOM '01) (Nov. 25-29 2001), vol. 5, pp. 2921--2925.
• 11: Mathar, R., and Mattfeldt, J. Analyzing routing strategy NFP in multihop packet radio networks on a line. IEEE Transactions on Communications 43, 234 (February/March/April 1995), 977--988.
• 12: Ni, J., and Chandler, S. Connectivity properties of a random radio network. In Proceedings of the IEE proceedings - Communications (August 1994), vol. 141, pp. 289--296.
• 13: Penrose, M. D. The longest edge of the random minimal spanning tree. The annals of applied probability 7, 2 (1997), 340--361.
• 14: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G]
• 15: Piret, P. On the connectivity of radio networks. IEEE Transactions on Information Theory 37, 5 (September 1991), 1490--1492.
• 16: Paolo Santi , Douglas M. Blough, An Evaluation of Connectivity in Mobile Wireless Ad Hoc Networks, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.89-102, June 23-26, 2002
• 17: Silvester, J. A. On the spatial capacity of packet radio networks. Tech. Rep. Eng. Rep. UCLA-ENG-8021, Dept. Comput. Sci., School Eng. Appl. Sci., Univ. California, Los Angeles, May 1980.
• 18: Takagi, H., and Kleinrock, L. Optimal transmission ranges for randomly distributed packet radio terminals. IEEE Transactions on Communications COM-32, 3 (March 1984), 246--257.
• 19: Wang, J. L., and Silvester, J. A. Maximum number of independent paths and radio connectivity. IEEE Transactions on Communications 41, 10 (October 1993), 1482--1493.
• 20: Feng Xue , P. R. Kumar, The number of neighbors needed for connectivity of wireless networks, Wireless Networks, v.10 n.2, p.169-181, March 2004 [doi>10.1023/B:WINE.0000013081.09837.c0]

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Network topology
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Reliability, availability, and serviceability; Fault tolerance

General Terms:
Performance, Reliability, Theory

Keywords:
asymptotic distribution, critical neighbor number, critical transmission radius, random geometric graph