A Novel Approximation for Multi-hop Connected Clustering Problem in Wireless Sensor Networks

Wireless sensor networks (WSNs) have been widely used in plenty of applications. To achieve higher efficiency for data collection, WSNs are often partitioned into several disjointed clusters, each with a representative cluster head in charge of the data gathering and routing process. Such a partition is balanced and effective if the distance between each node and its cluster head can be bounded within a constant number of hops, and any two cluster heads are connected. Finding such a cluster partition with minimum number of clusters and connectors between cluster heads is defined as minimum connected d-hop dominating set (d-MCDS) problem, which is proved to be NP-complete. In this paper, we propose a distributed approximation algorithm, named CS-Cluster, to address the d-MCDS problem. CS-Cluster constructs a sparser d-hop maximal independent set (d-MIS), connects the d-MIS and finally checks and removes redundant nodes. We prove the approximation ratio of CS-Cluster is (2d + l)λ, where λ is a parameter related with d but is no more than 18.4. Compared with the previous best result O(d2), our approximation ratio is a great improvement. Our evaluation results demonstrate the outstanding performance of our algorithm compared with previous works.