Quantile models for the threshold range for k-connectivity

ABSTRACT

This study addresses the problem of k-connectivity of a wireless multihop network consisting of randomly placed nodes with a common transmission range, by utilizing empirical regression models for the threshold range for k-connectivity when the nodes are uniformly distributed in a square region. The cases k =1,2,3 are considered: with $k=1$, the models are based on known asymptotic results to assure correct limiting behavior; with k =2,3, an attempt is made to generalize these results and the models are built accordingly. Verification with independent simulation data shows all the models to be able to predict k-connectivity with good accuracy under this network model.

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: R. D'Souza, S. Ramanathan, and D. Lang. Measuring performance of ad hoc networks using timescales for information flow. In Proc. The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2003), Apr. 2003.
• 3: H. Koskinen. A simulation-based method for predicting connectivity in wireless multihop networks. Telecommunication Systems, 26(2-4):321--338, June 2004.
• 4: M. D. Penrose. The longest edge of the random minimal spanning tree. Annals of Applied Probability, 7(2):340--361, 1997.
• 5: M. D. Penrose. Extremes for the minimal spanning tree on normally distributed points. Advances in Applied Probability, 30(3):628--639, 1998.
• 6: 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]
• 7: T. K. Philips, S. S. Panwar, and A. N. Tantawi. Connectivity properties of a packet radio network model. IEEE Transactions on Information Theory, 35(5):1044--1047, Sept. 1989.
• 8: M. Sánchez, P. Manzoni, and Z. J. Haas. Determination of critical transmission range in Ad-Hoc Networks. In Proceedings of Multiaccess Mobility and Teletraffic for Wireless Communications 1999 Workshop (MMT'99), Oct. 1999.
• 9: Peng-Jun Wan , Chih-Wei Yi, Asymptotic critical transmission radius and critical neighbor number for k-connectivity in wireless ad hoc 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.989461]

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: Distributed networks; Network topology

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
  G.3 PROBABILITY AND STATISTICS
      Subjects: Correlation and regression analysis; Distribution functions

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Design, Performance, Reliability, Theory

Keywords:
Boolean model, ad hoc networks, connectivity, empirical models, geometric random graphs, sensor networks