D-cluster formation and routing in mobile ad hoc networks.

摘要

A mobile ad hoc network may be logically represented as a set of clusters. The clusterheads form a dominating set, and can be used to perform a variety of functions for nodes in their cluster like channels access, routing, etc. Previous heuristics restricted themselves to 1-hop clusters and were sequential in nature. This paper generalizes 1-hop clustering to a d-hop clustering problem. The value of d, a constant, is a parameter of the heuristic and governs the size of the clusters. First, we present a distributed and concurrent heuristic which allows all nodes to form d-clusters in a wireless mobile ad hoc network. When the heuristic terminates, a node either becomes a clusterhead, or is at most d wireless hops away from its clusterhead. An inherent characteristic of the heuristic is that it tries to generate clusters that are roughly the same size, thereby evenly distributing the load on the clusterheads (load-balancing). The heuristic also tends to re-elect existing clusterheads even when the network configuration changes (stability). This helps to reduce the communication overhead associated with transitions from old clusterheads to new clusterheads. The heuristic can be run either at regular intervals, or whenever the network configuration changes. Next, we propose a load-balancing heuristic that allows all nodes in the network to become clusterheads in time. Thus, the heuristic is fair and stable. Then we present a multi-hop routing protocol to be used with this clustering heuristic. Simulation experiments demonstrate that the proposed heuristic generates exactly the same number of clusterheads as [7], in fewer rounds of messages: O( d) rounds for the proposed heuristic compared to O( n) time slots for [7], where n is the number of nodes in the network.