On the minimum node degree and connectivity of a wireless multihop network

ABSTRACT

This paper investigates two fundamental characteristics of a wireless multi -hop network: its minimum node degree and its k--connectivity. Both topology attributes depend on the spatial distribution of the nodes and their transmission range. Using typical modeling assumptions :--- :a random uniform distribution of the nodes and a simple link model :--- :we derive an analytical expression that enables the determination of the required range r0 that creates, for a given node density ρ, an almost surely k--connected network. Equivalently, if the maximum r0 of the nodes is given, we can find out how many nodes are needed to cover a certain area with a k--connected network. We also investigate these questions by various simulations and thereby verify our analytical expressions. Finally, the impact of mobility is discussed.The results of this paper are of practical value for researchers in this area, e.g., if they set the parameters in a network--level simulation of a mobile ad hoc network or if they design a wireless sensor network.

REFERENCES

• 1: B. M. Leiner, D. L. Nielson, and F. A. Tobagi, eds., Proceedings of the IEEE, Special issue on Packet Radio Networks, vol. 75, Jan. 1987.
• 2: Z. J. Haas, M. Gerla, D. B. Johnson, C. E. Perkins, M. B. Pursley, M. Steenstrup, and C.-K. Toh, eds., IEEE Journal on Sel. Areas in Comm., Special issue on Wireless Ad Hoc Networks, vol. 17, Aug. 1999.
• 3: P. Kermani and N. H. Vaidya, eds., IEEE Personal Comm., Special issue on Advances in Mobile Ad Hoc Networking, Feb. 2001.
• 4: C. E. Perkins, ed., Ad Hoc Networking. Addison--Wesley, 2001.
• 5: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 6: Y.-D. Lin and Y.-C. Hsu, "Multihop cellular: A new architecture for wireless communications," in Proc. IEEE Infocom, (Tel Aviv, Israel), Mar. 2000.
• 7: W. Kellerer, C. Bettstetter, C. Schwingenschlögl, P. Sties, K.-E. Steinberg, and H.-J. Vögel," (Auto)Mobile communication in a heterogeneous and converged world," IEEE Pers. Comm., Dec. 2001.
• 8: Hannes Hartenstein , Bernd Bochow , André Ebner , Matthias Lott , Markus Radimirsch , Dieter Vollmer, Position-aware ad hoc wireless networks for inter-vehicle communications: the Fleetnet project, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501449.501454]
• 9: R. Ramanathan and R. Rosales-Hain, "Topology control of multihop wireless networks using transmit power adjustment," in Proc. IEEE Infocom, (Tel Aviv, Israel), Mar. 2000.
• 10: R. Wattenhofer, L. Li, P. Bahl, and Y.-M. Wang, "Distributed topology control for power efficient operation in multihop wireless ad hoc networks," in Proc. IEEE Infocom, (Anchorage, Alaska), Apr. 2001.
• 11: Paolo Santi , Douglas M. Blough , Feodor Vainstein, A probabilistic analysis for the range assignment problem in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501445.501446]
• 12: R. Diestel, Graph Theory. Springer, 2nd ed., 2000.
• 13: B. Bollobás, Modern Graph Theory. Springer, 1998.
• 14: N. A. C. Cressie, Statistics for Spatial Data. John Wiley & Sons, 1991.
• 15: H. Takahi and L. Kleinrock, "Optimal transmission ranges for randomly distributed packet radio terminals," IEEE Trans. on Comm., Mar. 1984.
• 16: A. Papoulis, Probability, random variables, and stochastic processes. McGraw--Hill, 1984.
• 17: Makoto Matsumoto , Takuji Nishimura, Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.8 n.1, p.3-30, Jan. 1998 [doi>10.1145/272991.272995]
• 18: C. Bettstetter and O. Krause, "On border effects in modeling and simulation of wireless ad hoc networks," in Proc. IEEE Intern. Conf. on Mobile and Wireless Comm. Netw. (MWCN), (Recife, Brazil), Aug. 2001.
• 19: On-Demand Multi Path Distance Vector Routing in Ad Hoc Networks, Proceedings of the Ninth International Conference on Network Protocols, p.14, November 11-14, 2001
• 20: B. Bollobás, Random Graphs. Academic Press, 1985.
• 21: S. Janson, A. Rucinski, T. Luczak, and T. Uczak, Theory of Random Graphs. Wiley, May 2000.
• 22: Imrich Chlamtac , András Faragó, A new approach to the design and analysis of peer-to-peer mobile networks, Wireless Networks, v.5 n.3, p.149-156, May 1999 [doi>10.1023/A:1019186624837]
• 23: Josep Díaz , Mathew D. Penrose , Jordi Petit , María Serna, Convergence Theorems for Some Layout Measures on Random Lattice and Random Geometric Graphs, Combinatorics, Probability and Computing, v.9 n.6, p.489-511, November 2000 [doi>10.1017/S0963548300004454]
• 24: 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]
• 25: P. Erdüs and A. Rényi, "On the evolution of random graphs," Publ. Math. Inst. Hungar. Acad. Sci., vol. 5, pp. 17--61, 1960.
• 26: Christian Bettstetter, Mobility modeling in wireless networks: categorization, smooth movement, and border effects, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.3, p.55-66, July 2001 [doi>10.1145/584051.584056]
• 27: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 28: Elizabeth M. Royer , Charles E. Perkins, Multicast operation of the ad-hoc on-demand distance vector routing protocol, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.207-218, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313538]
• 29: S. R. Das, C. E. Perkins, and E. M. Royer, "Performance comparison of two on-demand routing protocols for ad hoc networks," in Proc. IEEE Infocom, (Tel Aviv, Israel), 2000.
• 30: Gavin Holland , Nitin Vaidya, Analysis of TCP performance over mobile ad hoc networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.219-230, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313540]
• 31: R. A. Guérin, "Channel occupancy time distribution in a cellular radio system," IEEE Trans. on Vehicular Technology, vol. 36, Aug. 1987.
• 32: Y.-C. Cheng and T. G. Robertazzi, "Critical connectivity phenomena in multihop radio models," IEEE Trans. on Communications, vol. 37, July 1989.
• 33: T. K. Philips, S. S. Panwar, and A. N. Tantawi, "Connectivity properties of a packet radio network model," IEEE Trans. on Inform. Theory, Sept. 1989.
• 34: P. Piret, "On the connectivity of radio networks," IEEE Trans. on Information Theory, Sept. 1991.
• 35: P. Gupta and P. R. Kumar, "Critical power for asymptotic connectivity in wireless networks," in Stochastic Analysis, Control, Optimization and Applications, pp. 547--566, Birkhauser, 1998.
• 36: M. J. B. Appel and R. P. Russo, "The minumum vertex degree of a graph on uniform points in {0,1d}," Adv. in Applied Probability, vol. 29, pp. 582--594, 1997.
• 37: J. G. Proakis, E. M. Sozer, J. A. Rice, and M. Stojanovic, "Shallow water acoustic networks," IEEE Personal Communications, Nov. 2001.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Design, Performance, Theory

Keywords:
ad hoc networking, analytical methods, connectivity, geometric random graphs, isolated nodes, minimum node degree, modeling, sensor networks