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/2log ^1/2 k)+D _b −1+O(log (max (P _i )+log ²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 ), 1≤i≤k, 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).