Abstract
We define, for an overlay built on top of an ad hoc network, 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 derive a necessary and sufficient condition on R to achieve asymptotic connectivity of the overlay almost surely, i.e. connectivity with probability 1 when the number of overlay nodes tends to infinity, under the hypothesis that the underlying ad hoc network is itself asymptotically almost surely connected.
This condition, though asymptotic, sheds some light on the relation linking the critical R to the number of nodes n, the normalized radio transmission range r and the overlay density D (i.e., the proportion of overlay nodes). This condition can be considered as an approximation when the number of nodes is large enough. Since r is considered as a function of n, we are able to study the impact of topology control mechanisms, by showing how the shape of this function impacts the critical R.
Chapter PDF
Similar content being viewed by others
References
Bollobas, B. (1985). Random Graphs. Academic Press, London, England.
Calomme, S. and Leduc, G. (2004). Performance study of an overlay approach to active routing in ad hoc networks. In Proc. of the Third annual Mediterranean Ad Hoc Networking Workshop (Med-Hoc-Net’04), Bodrum, Turkey.
Calomme, S. and Leduc, G. (2006). The critical neighbourhood range for asymptotic overlay connectivity in ad hoc networks. To appear in Ad Hoc and Sensor Wireless Networks.
Desai, M. and Manjunath, D. (2002). On the connectivity in finite ad hoc networks. IEEE Commun. Lett., 10(6):437–490.
Erdos, P. and Rényi, A. (1960). On the evolution of random graphs. Hungarian Academy of Science, 5:17–61.
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), pages 580–586. Chicago, IL.
Gupta, P. and Kumar, P. (1999). Critical power for asymptotic connectivity in wireless networks. In McEneaney, W.M., Yin, G., and Zhang, Q., editors, Stochastic Analysis, Control, Optimization and Applications, A Volume in Honor of W. H. Fleming. Birkhäuser, Boston.
Kawadia, V. and Kumar, P.R. (2005). Principles and protocols for power control in wireless ad hoc networks. IEEE J. Select. Areas Commun., 23(1):76–88.
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.
Mohapatra, P., Gui, C., and Li, J. (2004). Group communications in mobile ad hoc networks. IEEE Computer, 37(2):52–59.
Narayanaswamy, S., Kawadia, V., Sreenivas, R.S., 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, pages 156–162, Florence, Italy.
Penrose, M. (2003). Random Geometric Graphs. Oxford University Press, England.
Penrose, M. D. (1997). The longest edge of the random minimal spanning tree. The Annals of Applied Probability, 7(2):340–361.
Penrose, M. D. (1999). On the k-connectivity for a geometric random graph. Random Structures and Algorithms, 15(2):145–164.
Santi, P. and Blough, D. M. (2003). The critical transmitting range for connectivity in sparse wireless ad hoc networks. IEEE Trans. Mobile Comput., pages 25–39.
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.
Wang, K. H. and Li, B. (2002). Efficient and guaranteed service coverage in partitionable mobile ad-hoc networks. In Proc. Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02), New York, NY.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 International Federation for Information Processing
About this paper
Cite this paper
Calomme, S., Leduc, G. (2006). The Critical Neighbourhood Range for Asymptotic Overlay Connectivity in Dense Ad Hoc Networks. In: Al Agha, K., Guérin Lassous, I., Pujolle, G. (eds) Challenges in Ad Hoc Networking. Med-Hoc-Net 2005. IFIP International Federation for Information Processing, vol 197. Springer, Boston, MA. https://doi.org/10.1007/0-387-31173-4_20
Download citation
DOI: https://doi.org/10.1007/0-387-31173-4_20
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-31171-5
Online ISBN: 978-0-387-31173-9
eBook Packages: Computer ScienceComputer Science (R0)