A hierarchical virtual-backbone routing approach in Ad hoc networks

Hiranmayi Sreenivas, Hesham H. Ali

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

This paper presents a hierarchical approach to routing in ad-hoc wireless networks using graph theoretic concepts. Ad hoc wireless networks provide a flexible and quick means of establishing wireless peer-to-peer communications. However, routing remains a challenging problem in an ad hoc network due to its multihop nature and dynamic network topology. In previous work, we have proposed an evolutionary approach, employing genetic algorithms, to constructing a stable connected dominating set that serves as a virtual backbone in an ad hoc wireless network. In this work, we present a two-level hierarchical routing strategy that serves to further improve the efficiency of the evolutionary virtual-backbone-based routing approach. The network is divided into groups of nodes called clusters. Within each cluster, there exists a self-organizing, dynamic virtual backbone that is constructed using a heuristic based on genetic algorithms. Between clusters, information is routed through gateway nodes. The overhead of computing and refreshing the virtual backbone for the entire network would be greatly reduced, particularly as the network size increases. This, in turn, improves the routing performance significantly. Through extensive simulations, we demonstrate the importance of clustering by showing that the clustered protocol outperforms the non-clustered evolutionary protocol especially for large networks.

Original languageEnglish (US)
Title of host publicationThird IASTED International Conference on Communications and Computer Networks, CCN 2005
EditorsM.Y. Sanadidi
Pages81-87
Number of pages7
StatePublished - 2005
EventProceedings of the Third IASTED International Conference on Communications and Computer Networks, CCN 2005 - Marina del Rey, CA, United States
Duration: Oct 24 2005Oct 26 2005

Publication series

NameProceedings of the Third IASTED International Conference on Communications and Computer Networks, CCN 2005

Conference

ConferenceProceedings of the Third IASTED International Conference on Communications and Computer Networks, CCN 2005
CountryUnited States
CityMarina del Rey, CA
Period10/24/0510/26/05

Keywords

  • Ad-hoc networks
  • Genetic algorithms
  • Routing
  • Simulation
  • Virtual backbones connected dominating sets

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'A hierarchical virtual-backbone routing approach in Ad hoc networks'. Together they form a unique fingerprint.

  • Cite this

    Sreenivas, H., & Ali, H. H. (2005). A hierarchical virtual-backbone routing approach in Ad hoc networks. In M. Y. Sanadidi (Ed.), Third IASTED International Conference on Communications and Computer Networks, CCN 2005 (pp. 81-87). (Proceedings of the Third IASTED International Conference on Communications and Computer Networks, CCN 2005).