Cluster based routing using a k-tree core backbone for mobile ad hoc networks

Abstract

The problem of routing in Mobile Ad hoc Networks is non-trivial because of the dynamic nature of the network topology. In addition to computing shortest paths, as in wire-line networks, any routing scheme must consider that the topology of the network can vary while the packet is being routed.Cluster based schemes have been proposed which segregate the network into manageable sets for maintaining routing information. In this paper we propose a novel method of constructing the clusters and a backbone based on the concept of a k-tree core. We also propose an hierarchical routing scheme using this cluster information and evaluate its performance through extensive simulations.