Cluster-based Approach for Routing in Ad-Hoc Networks

This paper presents a "cluster-based" approach to routing in ad-hoc networks. A cluster is defined by a subset of nodes which are `reachable' to each other. Ou r approach is motivated by our study of existence of clusters (size greater than 2) in random graphs. The basic idea behind the protocol is to divide the graph into number of overlapping clusters. A change in the network topology corresponds to a change in the cluster membership. Performance of the proposed routing protocol(reconvergence time, and update overhead) will hence be determined by the average cluster size in the network graph. The effectiveness of this approach lies in the fact that existing routing protocols can be directly applied to the network -- replacing the nodes by clusters. When the average cluster size is less than 2, the proposed approach does not perform any worse than the existing routing protocols. Generalization of the proposed approach is a subject of ongoing research.