[en] We first motivate the use of ad hoc overlays. In particular, we argue that overlay routing could play a role in the spreading of ad hoc networks. We then define a simple criterion for neighbourhood: two overlay nodes are neighbours if and only if there exists a path between them of at most R hops, and R is called the (overlay) neighbourhood range. A small R may result in a disconnected overlay, while an unnecessarily large R would generate extra control traffic. We are interested in the minimum R ensuring overlay connectivity, the so-called critical R. We study conditions on R to achieve asymptotic connectivity of the overlay almost surely, i.e. connectivity with probability 1 when the number of nodes in the underlying ad hoc network tends to infinity (so-called dense networks) or when the size of the field tends to infinity (socalled sparse networks), under the hypothesis that the underlying ad hoc network is itself asymptotically almost surely connected. For dense networks, we derive a necessary and sufficient condition on R, and for sparse networks we derive distinct necessary and sufficient conditions that are however asymptotically tight. These conditions, though asymptotic, shed some light on the relation linking the critical R to the number of nodes n, the field size the radio transmission range r and the overlay density D (i.e., the proportion of overlay nodes). These conditions can be considered as approximations when the number of nodes (resp. the field) is large enough. Since r is considered as a function of n or l , we are able to study the impact of topology control mechanisms, by showing how the shape of this function impacts the critical R.
Disciplines :
Computer science
Author, co-author :
Calomme, Sandrine; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Leduc, Guy ; Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Réseaux informatiques
Language :
English
Title :
The Critical Neighbourhood Range for Asymptotic Overlay Connectivity in Ad Hoc Networks
Publication date :
2006
Journal title :
Ad Hoc and Sensor Wireless Networks
ISSN :
1551-9899
eISSN :
1552-0633
Publisher :
Old City Publishing, Inc., Philadelphia, United States - Pennsylvania
Wu, H., Qiao, C., De, S. and Tonguz, O. K. (2001). “Integrated cellular and ad hoc relaying systems: icar,” IEEE J. Select. Areas Commun., 19, 10,2105–2115.
Zadeh,A.,Jabbari,B.,Pickholtz,R. and Vojcic,B. (2002). “Self-organizing packet radio ad hoc networks with overlay (soprano),” IEEE Commun. Mag., 40, 6,149–157.
Chen K. and Nahrstedt, K. (2002). “Effective location-guided tree construction algorithms for small group multicast in manet,” in Proc. Annual Joint Conference of the IEEE Computer and Communications Societies (INFO-COM’02), New York, NY, June 1180–1189.
Xie, J., Talpade, R., Mcauley, A. and Liu, M. (2002). “Amroute: Ad hoc multicast routing protocol,” Mobile Networks and Applications, 7, 6,429–439.
Gui C. and Mohapatra,P. (2003). “Efficient overlay multicast for mobile ad hoc networks,” in Proc. IEEE Wireless Communications and Networking Con-ference (WCNC’03).
Xiao,L.,Patil,A.,Liu,Y.,Ni,L. and Esfahanian,A.-H. (2004). “Prioritized overlay multicast in mobile ad hoc environments,” IEEE Computer, 37, 2,67–74.
Ge, M., Krishnamurthy, S. and Faloutsos, M. (2004). “Overlay multicasting for ad hoc networks,” in Proc. of the Third annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net’04), Bodrum, Turkey.
Patil, A., Liu, Y., Xiao, L., Esfahanian, A.-H. and Ni, L. (2004). “Solonet: Sub-optimal location-aided overlay network for manets,” in Proc. of the First IEEE Int. Conf. on Mobile Ad hoc and Sensor Systems (MASS’04), Fort Lauderdale, FL.
Mohapatra,P.,Gui,C. and Li,J. (2004). “Group communications in mobile ad hoc networks,” IEEE Computer, 37, 2,52–59.
Wang K. H. and Li, B. (2002). “Efficient and guaranteed service coverage in par-titionable mobile ad-hoc networks,” in Proc. Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02), New York, NY.
Tang D. and Baker, M. (2000). “Analysis of a local-area wireless network,” in Proc. of the Sixth Annual International Conference on Mobile Computing and Networking (MOBICOM’00), Boston, MA.
Gupta P. and Kumar,P. (2000). “The capacity of wireless networks,” IEEE Trans. Inform. Theory, 46, 2,388–404.
Royer E. and Toh,C.-K. (1999). “A review of current routing protocols for ad hoc mobile wireless networks,” IEEE Personal Commun. Mag., 46–55.
Clark,D. (1988). “The design philosophy of the DARPA Internet protocols,” Computer Communication Review, 18, 4,106–114.
Bollobas,B. (1985). Random Graphs. London,England: Academic Press.
Erdos P. and Rényi,A. (1960). “On the evolution of random graphs,” Hungarian Academyof Science, 5, 17–61.
Penrose,M. (2003). Random Geometric Graphs. England: Oxford University Press.
Penrose,M. D. (1999). “On the k-connectivity for a geometric random graph,” Random Structures and Algorithms, 15, 2,145–164.
Krishnamachari, B., Wicker, S. and Bejar, R. (2001). “Phase transition phenomena in wireless ad-hoc networks,” in Proc. IEEE Global Conference on Telecommunications (Globecom’01), Symposium on Ad-Hoc Wireless Networks, San Antonio, TX.
Goel,A.,Rai,S. and Krishnamachari,B. (2004). “Sharp thresholds for monotone properties in random geometric graphs,” in Proc. of the thirty-sixth annual ACM symposium on Theory of computing (STOC’04), Chicago, IL,580–586.
Gupta P. and Kumar,P. (1999). “Critical power for asymptotic connectivity in wireless networks,” in Stochastic Analysis, Control, Optimization and Applications, A Volume in Honor of W. H. Fleming, W. McEneaney,G. Yin,and Q. Zhang,Eds. Boston: Birkhauser.
Li,X.-Y.,Wang,Y.,Wan,P.-J. and Yi,C.-W. (2004). “Fault tolerant deployment and topology control in wireless ad hoc networks,” Journal of Wireless Communications and Mobile Computing (WCMC), 4, 1,109–125.
Wan P.-J. and Yi, C.-W. (2005). “Asymptotic critical transmission ranges for connectivity in wireless ad hoc networks with Bernoulli nodes,” in Proc. of the 2005 IEEE Wireless Communications and Networking Conference (WCNC 2005), New Orleans, Louisiana.
Santi P. and Blough,D. M. (2003). “The critical transmitting range for connectivity in sparse wireless ad hoc networks,” IEEE Trans. Mobile Comput., 25–39.
Santi,P.,Blough,D.M. and Bostelmann,H. (2006). “A Comment on: the Critical Transmitting Range for Connectivity in Sparse Wireless Ad Hoc Networks,” IEEE Trans on Mobile Computing, 5, 7.
Kolchin, V. F., Sevast’yanov, B. and Chistyakov, V. P. (1978). Random Allocations. Washington D.C.: V.H. Winston and Sons.
Muthukrishnan S. and Pandurangan, G. (2005). “The Bin-Covering Technique for Thresholding Random Geometric Graph Properties,” Proc. of ACM-SIAM Sympossium on Discrete Algorithms (SODA 2005),” Vancouver, Canada,Tech. Rep.
Desai M. and Manjunath,D. (2002). “On the connectivity in finite ad hoc net-works,” IEEE Commun. Lett.,10, 6,437–490.
Kawadia V. and Kumar,P. (2005). “Principles and protocols for power control in wireless ad hoc networks,” IEEE J. Select. Areas Commun., 23, 1,76–88.
Narayanaswamy, S., Kawadia, V., Sreenivas, R. and Kumar, P. R. (2002). “Power control in ad-hoc networks: Theory, architecture, algorithm and implementation of the compow protocol,” in Proc. of European Wireless 2002. Next Generation Wireless Networks: Technologies, Protocols, Services and Applications, Florence, Italy 156–162.
Penrose,M. D. (1997). “The longest edge of the random minimal spanning tree,” The Annals of Applied Probability, 7, 2,340–361.
Weisstein, E. W. Circle-Circle Intersection, From MathWorld–A Wolfram Web Resource, 1999. [Online]. Available: http://mathworld.wolfram.com/Circle-CircleIntersection.html