A CDS-based topology control algorithm in energy efficient Clustering

Topology management is crucial to the efficiency of a wireless communication network in which all nodes are energy constraint. Clustering is a kind of energy efficient algorithm, while using a virtual backbone constructed by Connected Dominating Set (CDS) to organize the nodes is a better way. Wepropose an energy efficient Clustering algorithm based on Local CDS construction (CLCDS) to form the CDS-based backbone with local information exchanges. In this algorithm, each node builds its local spanning tree independently and computes its degree flag to determine whether to act as a dominating node. As we elect the dominating nodes first and then connect them by a RNG [13] based algorithm, the number of border nodes and dominating nodes obtained by our algorithm is greatly reduced compared with previous researches. The correctness of the algorithm is proven and the efficiency is compared with other clustering heuristics using simulations. As the cluster balance will have a significant impact on the network performance, we also provide with a tunable scheme to achieve a fairly balanced cluster distribution across the networks.