TY - GEN
T1 - A hierarchical virtual-backbone routing approach in Ad hoc networks
AU - Sreenivas, Hiranmayi
AU - Ali, Hesham H.
PY - 2005
Y1 - 2005
N2 - 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.
AB - 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.
KW - Ad-hoc networks
KW - Genetic algorithms
KW - Routing
KW - Simulation
KW - Virtual backbones connected dominating sets
UR - http://www.scopus.com/inward/record.url?scp=33244494201&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33244494201&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:33244494201
SN - 0889865469
SN - 9780889865464
T3 - Proceedings of the Third IASTED International Conference on Communications and Computer Networks, CCN 2005
SP - 81
EP - 87
BT - Third IASTED International Conference on Communications and Computer Networks, CCN 2005
A2 - Sanadidi, M.Y.
T2 - Proceedings of the Third IASTED International Conference on Communications and Computer Networks, CCN 2005
Y2 - 24 October 2005 through 26 October 2005
ER -