A novel clustering algorithm by using mobile gateways in densely deployed sensor networks

Clustering is an efficient and important method to facilitate energy conservation. Aiming to alleviate the high overheads of migrating management information in the re-clustering process of a clustering algorithm, an energy efficient, Complete Graph-based Clustering Algorithm (CGCA) is proposed in a densely deployed sensor network. CGCA divides the network into a few complete graphs, each complete graph independently being a cluster. 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, which incurs greatly reduced communication and computation overheads. Another contribution of our work is to add some mobile nodes to act as gateways so as to join the disconnected cluster heads, which puts the heavy inter-cluster traffic burden on the resource-rich mobile nodes thus saving much energy in the energy constrained sensor nodes. Extensive simulation experiments demonstrate that the number of exchanged messages produced by CGCA is only about 20% that of the traditional identifier based clustering algorithm in a densely deployed case. Furthermore, our proposed achieves an improvement in system lifetime of factor 2 that of the LEACH in a dense sensor network.