H. Sreenivas and H.H. Ali (USA)
Routing, Ad-Hoc Networks, Virtual Backbones
Connected Dominating Sets, Simulation, Genetic
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.