A randomized clustering of anonymous wireless ad hoc networks with an application to the initialization problem
The Distributed Mobility-Adaptive Clustering (DMAC) due to Basagni partitions the nodes of a mobile ad hoc network into clusters, thus giving the network a hierarchical organization. This algorithm supports the mobility of the nodes, even during the cluster formation. The main feature of DMAC is that in a weighted network (in which two or more nodes cannot have the same weight), nodes have to choose the clusterheads taking into account only the node weight, i.e. the mobility when a node weight is the inverse of its speed. In our approach many nodes may have the same speed and hence the same weight. We assume that nodes have no identities and the number of nodes, say n, is the only known parameter of the network. After the randomized clustering, we show that the initialization problem can be solved in a multi-hop ad hoc wireless network of n stations in O(k (1/2)log (1/2) k)+D (b) -1+O(log (max (P (i) )+log (2)max (P (i) )) broadcast rounds with high probability, where k is the number of clusters, D (b) is the blocking diameter and max (P (i) ), 1a parts per thousand currency signia parts per thousand currency signk, is the maximum number of nodes in a cluster. Thus the initialization protocol presented here uses less broadcast rounds than the one in Ravelemanana (IEEE Trans. Parallel Distributed Syst. 18(1):17-28 2007).
clustering initialization problem multi-hop wireless ad hoc networks