Associativity based clustering and query stride for on-demand routing protocols in ad hoc networks

An ad hoc network is a collection of wireless mobile nodes without the support of a stationary infrastructure. In ad hoc networks, each node acts as a router to support multiple hops to overcome limited range of packet radios. While a variety of routing protocols have been developed recently, a class of routing schemes called on-demand protocols have attracted a lot of attentions due to their low routing overhead. However, their efficiency is limited by the enormous query flooding overhead and the route acquisition latency. In this paper, we propose two new schemes — Associativity Based Clustering (ABC) and Query Stride (QS) — which offer benefits to on-demand protocols by surmounting those limitations. First, ABC provides a proactive routing information on associatively-stable nodes in the network. Thus, nodes can communicate immediately with a node in ABC without any query-reply exchange. Second, QS enables a query to be flooded to the whole network with a minimum number of broadcasts. While ABC reduces the route acquisition latency, QS saves the bandwidth in flooding. Although ABC and QS can be used independently, the combined effect is even greater since they provide complementary benefits sharing common overhead.