## 2 Related Work  
Cluster-based self-organization is an important research topic for mobile ad-hoc networks since clustering allows to provide basic levels of system performance. A large variety of approaches for ad-hoc clustering have been proposed in literature [10; 11; 12; 13; 14; 15; 16; 17; 18; 19; 20; 21; 22; 23; 24; 25; 26; 27; 28; 29; 30; 31; 32; 33; 34; 35; 36; 37; 38; 39; 40; 41; 42; 43; 44; 45]. Most of these design approaches are heuristic protocols in which each sensor must maintain knowledge of the complete network or identify a subset of sensors with a clusterhead to partition the network into clusters in heuristic ways. Perhaps the earliest of the clustering methods is the identifier-based heuristic called the Linked Cluster Algorithm (LCA) [13], which elects sensor to be a clusterhead if the sensor has the highest identification number among all sensors within one hop of its neighbors. The connectivity-based heuristic of [14; 15] selects the sensors with the maximum number of 1-hop neighbors (i.e., highest degree) to be clusterheads. However, These algorithms suffer from dynamic network topology, which triggers frequent changes of clusterheads. The Max-Min D-cluster Algorithm [16] generates _d_-hop clusters with a complexity of \(O(d)\) without time synchronization. It provides load balancing among clusterheads in the network. Simulation results suggest that this heuristic is superior to the LCA and connectivity-based solutions. The Low-Energy Adaptive Clustering Hierarchy (LEACH) of [28] utilizes randomized rotation of clusterheads to balance the energy load among the sensors and uses localized coordination to enable scalability and robustness for cluster set-up and operation. LEACH-C (Centralized) [29] uses a centralized controller. The main drawbacks of this algorithm are nonautomatic clusterhead selection and the requirement that the position of all sensors must be known. LEACH's stochastic algorithm is extended in [30] with a deterministic clusterhead selection. Simulation results demonstrate that an increase of network lifetime can be achieved compared with the original LEACH protocol. In [31], the clustering is driven by minimizing the energy spent in wireless sensor networks. The authors adopt the energy model in [28] and use the Subtractive Clustering Algorithm and Fuzzy C-mean (FCM) algorithm to form clusters. Although the above algorithms carefully consider the energy required for clustering, they are not extensively analyzed (due to their complexity) and there is no way of estimating how many clusters will form in a given network. In [32], a mobility-aware clustering algorithm (MOBIC) is proposed. MOBIC presents an aggregate local mobility metric for the cluster formation process such that mobile nodes with low speed relative to their neighbors have the chance to become clusterheads. However, it neglects mobility manners in later cluster maintenance, which may not work well in a dynamic environment. The Weighted Clustering Algorithm (WCA) [33] considers the number of neighbors, transmission power, mobility, and battery usage in choosing clusters. It limits the number of sensors in a cluster so that clusterheads can handle the load without degradation in performance. These clustering methods rely on synchronous clocking for the exchange of information among sensors which typically limits these algorithms to smaller networks [34]. The authors in [35] characterize the different node parameters in terms of an information theoretic metric and use entropy as a measure of local and mutual information available to every node, such as mobility,energy, and degree in the clusterhead selection procedure. The results demonstrate that the mutual information captured through entropy is very effective in determining the most suitable clusterheads. [PERSON] _et al._[36] consider generic metrics (e.g., protocol duration, energy consumption, message overhead, route length, and backbone size) to generate ad-hoc clustering and backbone formation.