Cluster-based Approach for Routing in Ad-Hoc Networks
P. Krishna, M. Chatterjee, N. H. Vaidya, D. K. Pradhan
Department of Computer Science
Texas A\&M University
College Station, TX 77843-3112
Email : pkrishna@cs.tamu.edu
Abstract
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.
Download the full text of this paper in
ASCII (43,446 bytes) and
POSTSCRIPT (229,319 bytes) form.
To Become a USENIX Member, please see our
Membership Information.