A Novel Clustering Algorithm in the Densely Deployed Sensor Networks

Aiming to address the high overload problem in the re-clustering process in the clustering algorithm, an energy efficient, complete graph-based clustering algorithm is proposed（CGCA）. CGCA is employed to divide the network into a few complete graphs at the system activation time, each complete graph independently being a cluster. By using the property that the nodes are of equivalence each other in a complete graph, CGCA is only executed at the system activation time and the cluster head role needs only to be rotated among the internal nodes in each cluster at the subsequent re-clustering phase, while the previous clustering algorithms need a global trigger to re-elect cluster heads, which incurs greatly reduced communication and computation overheads. CGCA achieves a process and message complexity of O（1） at each node. Moreover, the preferred selection of nodes close to cluster heads into the cluster, not only reduces the intra-cluster communication energy of cluster heads and their inner cluster members, but leads to the even distribution of cluster heads in the deployment region. The simulation experiments demonstrate that the number of exchanged message produced by CGCA is much less than that of HEED clustering algorithm in the densely deployed case. Finally, CGCA significantly outperforms LEACH algorithm in terms of evenly distributing cluster heads.