Abstract
Unlike wired networks, wireless networks do not come with links. Rather, links have to be fashioned out of the ether by nodes choosing neighbors to connect to. Moreover the location of the nodes may be random.
The question that we resolve is: How many neighbors should each node be connected to in order that the overall network is connected in a multi-hop fashion? We show that in a network with n randomly placed nodes, each node should be connected to Θ(log n) nearest neighbors. If each node is connected to less than 0.074log n nearest neighbors then the network is asymptotically disconnected with probability one as n increases, while if each node is connected to more than 5.1774log n nearest neighbors then the network is asymptotically connected with probability approaching one as n increases. It appears that the critical constant may be close to one, but that remains an open problem.
These results should be contrasted with some works in the 1970s and 1980s which suggested that the “magic number” of nearest neighbors should be six or eight.
Similar content being viewed by others
References
L. Kleinrock and J.A. Silvester, Optimum transmission radii for packet radio networks or why six is a magic number, in: Proc. of IEEE Nat. Telecommun. Conf. (December 1978) pp. 4.3.1-4.3.5.
R. Mathar and J. Mattfeldt, Analyzing routing strategy NFP in multihop packet radio network on a line, IEEE Transactions on Communications 43(2–4) (1995) 977-988.
J. Ni and S. Chandler, Connectivity properties of a random radio network, Proceedings of the IEE - Communications 141 (August 1994) 289-296.
J.A. Silvester, On the spatial capacity of packet radio networks, Eng. Rep. UCLA-ENG-8021, Dept. Comput. Sci., School Eng. Appl. Sci., Univ. California, Los Angeles (March 1980).
H. Takagi and L. Kleinrock, Optimal transmission ranges for randomly distributed packet radio terminals, IEEE Trans. Commun. 32 (1984) 246-257.
T. Hou and V. Li, Transmission range control in multihop packet radio networks, IEEE Trans. Commun. 34 (January 1986) 38-44.
B. Hajek, Adaptive transmission strategies and routing in mobile radio networks, in: Proceedings of the Conference on Information Sciences and Systems (March 1983) pp. 373-378.
P. Gupta and P. Kumar, The capacity of wireless networks, IEEE Transactions on Information Theory 46 (March 2000) 388-404.
T.K. Philips, S.S. Panwar and A.N. Tantawi, Connectivity properties of a packet radio network model, IEEE Transactions on Information Theory 35 (September 1989) 1044-1047.
P. Gupta and P.R. Kumar, Critical power for asymptotic connectivity in wireless networks, in: Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming, eds W.M. McEneany, G. Yin and Q. Zhang (Birkhauser, Boston, MA, 1998) pp. 547-566.
M.D. Penrose, The longest edge of the random minimal spanning tree, The Annals of Applied Probability 7(2) (1997) 340-361.
B. Bollobas, Random Graphs (Academic Press, Orlando, FL, 1985).
R. Meester and R. Roy, Continuum Percolation (Cambridge University Press, Cambridge, UK, 1996).
H. Kesten, Percolation Theory for Mathematicians (Birkhauser, Boston, MA, 1982).
L. Booth, J. Bruck, M. Franceschetti and R. Meester, Covering algorithms, continuum percolation and the geometry of wireless networks, Preprint, http://www.paradise.caltech.edu/ETR.html (2001).
M. Franceschetti, M. Cook and J. Bruck, A geometric theorem for approximate disk covering algorithms, Preprint, http://www.paradise.caltech.edu/ETR.html (2001).
F. Avram and D. Bertsimas, On central limit theorems in geometrical probability, Annals of Applied Probability 3(4) (1993) 1033-1046.
O. Haggstrom and R. Meester, Nearest neighbor and hard sphere models in continuum percolation, Random Structures and Algorithms 9 (1996) 295-315.
S. Narayanaswamy, V. Kawadia, R.S. Sreenivas and P.R. Kumar, Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the COMPOW protocol, in: European Wireless Conference - Next Generation Wireless Networks: Technologies, Protocols, Services and Applications, Florence, Italy (25–28 February 2002).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Xue, F., Kumar, P. The Number of Neighbors Needed for Connectivity of Wireless Networks. Wireless Networks 10, 169–181 (2004). https://doi.org/10.1023/B:WINE.0000013081.09837.c0
Issue Date:
DOI: https://doi.org/10.1023/B:WINE.0000013081.09837.c0