A connected dominating set-based weighted clustering algorithm for wireless sensor networks

Grouping of sensor nodes into clusters is the most popular approach to support scalability in Wireless Sensor Networks (WSN). The performance of WSNs can be improved suitably by selecting the qualified nodes to form a stable backbone structure with guaranteed network coverage. In this paper, we propose a centralized and weighted algorithm for dynamic sensor networks which require reliable data gathering. The solution is based on a (k, r) - Connected Dominating Set, which is suitable for cluster-based hierarchical routing. This improves reliability, provides variable degree of clusterhead redundancy and reduces route searching space in WSN. To create a stable and efficient backbone structure, backbone sensor nodes are selected based on quality, which is a function of the residual battery power, node degree, transmission range and mobility of the sensor nodes. Performance of the algorithm is evaluated through simulation. It is observed that the proposed algorithm performs well in terms of number of elements in the backbone structure, load balancing and the number of re-affiliations