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

摘要

Wireless sensor networks (WSNs) have been widely used in a 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 -hop dominating set ( -MCDS) problem, which is proved to be NP-complete. In this paper, we propose a distributed approximation named CS-Cluster to address the -MCDS problem under unit disk graph. CS-Cluster constructs a sparser -hop maximal independent set ( -MIS), connects the -MIS, and finally checks and removes redundant nodes. We prove the approximation ratio of CS-Cluster is , where is a parameter related with but is no more than 18.4. Compared with the previous best result , our approximation ratio is a great improvement. Our evaluation results demonstrate the outstanding performance of our algorithm compared with previous works.