Abstract
Research on ad-hoc network connectivity has mainly focused on asymptotic results in the number of nodes in the network. For a one-dimensional ad-hoc network G 1, assuming all the nodes are independently uniform distributed in a closed interval [0, Z](z ∈ ℝ+), we derive a generic formula for the probability that the network is connected. The finite connected ad-hoc networks is analyzed. And we separately suggest necessary conditions to make the ad-hoc network to be connected in one and two dimensional cases, facing possible failed nodes (f-nodes). Based on the necessary condition and unit-disk assumption for the node transmission, we prove that the nodes of the connected two-dimensional ad-hoc networks (G 2) can be divided into at most five different groups. For an f-node n 0 in either of the five groups, we derive a close formula for the probability that there is at least one route between a pair of nodes in G 2 − {n 0}.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Philips T K, Pandwar S S, Tantawi A N. Connectivity properties of a packet radio network model, IEEE Trans Inf Theory, 1989, 35: 1044–1047
Cheng Y C, Robertazzi T G. Critical connectivity phenomena in multihop radio models. IEEE Trans Commu, 1989, 37: 770–777
Xue F, Kumar P R. The number of neighbors needed for connectivity of wireless networks. Wireless Networks, 2004, 10: 169–181
Gupta P, Kumar P R. Critical power for asymptotic connectivity in wireless networks. In: McEneaney W M, Yin G, Zhang Q, eds. Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W.H. Fleming. Birkhauser, 1998. 547–566
Dousse O, Thiran P, Hasler M. Connectivity in ad-hoc and hybrid networks. IEEE INFOCOM, 2002, 2: 1079–1088
Dousse O, Baccelli F, Thiran P. Impact of interferences on connectivity in ad hoc networks. IEEE Trans Network, 2005, 13: 425–436
Booth L, Bruck J, Franceschetti M, et al. Covering algorithms, continuum percolation and the geometry of wireless networks. Annal Appl Probabil, 2003, 13: 722–741
Santi P, Blough DM. The critical transmitting range for connectivity in sparse wireless ad hoc networks. IEEE Trans Mobile Comput, 2003, 2: 25–39
Hekmat R, Mieghem P V. Degree distribution and hopcount in wireless ad-hoc networks. In: IEEE ICON’03, Sydney, Australia, 2003. 603–609
Santi P, Blough D M, Vainstein F. A probabilistic analysis for the range assignment problem in ad hoc networks. ACM MobiHoc’02. Long Beach, 2001. 212–220
Santi P. The critical transmitting range for connectivity in mobile ad hoc networks. IEEE Trans Mobile Comput, 2005, 4: 310–317
Ferrari G, Tonguz O K. Minimum number of neighbors for fully connected uniform ad hoc wireless networks. IEEE ICC, Paris, France, 2004, 7: 4331–4335
Wei X H, Chen G L, Wan Y Y, et al. Longest lifetime path in mobile ad hoc networks. J Software, 2006, l(17): 498–508
Desai M, Manjunath D. On the connectivity in finite ad hoc networks. IEEE Commun Lett, 2002, 6: 437–439
Gore A D. On the connectivity in finite ad hoc networks. IEEE Commun Lett, 2006, 10: 88–90
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported partially by the National Natural Science Foundation of China (Grant No. 60572066), the Key Scientific Research Project of Shanghai Municipal Education Commission (Grant No. 06ZZ84), and the City U, Hong Kong, Applied R & D Funding (ARD) (Grant No. 9668009)
Rights and permissions
About this article
Cite this article
Wang, H., Lu, G., Jia, W. et al. Connectivity in finite ad-hoc networks. Sci. China Ser. F-Inf. Sci. 51, 417–424 (2008). https://doi.org/10.1007/s11432-008-0011-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11432-008-0011-7