A review of cluster formation mechanism for clustering routing protocols

Clustering routing protocols have prominent advantages over flat routing protocols in terms of scalability, which is very useful for wireless mesh network with dense nodes distribution. However, clustering schemes will add large extra overhead in order to select cluster-heads and collect neighbor nodes information during the phase of cluster construction. At present, there exist a lot of excellent clustering schemes, and in this paper, we propose different classification criteria according to clustering charateristics. Then, we present a comprehensive review of several representatives, and especially focus on cluster formation mechanism. At last, we sum up with three typical problems we have to seriously consider when analyzing or design a clustering routing protocol.