Construction And Analysis For Multi-Hop Connected Clustering Problem In Wireless Sensor Networks

Wireless sensor networks(WSNs)have been widely used in plenty of applica-tions.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 dis-tance 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 in-dependent set(d-MIS),connects the d-MIS and finally checks and removes redundant nodes.We prove the approximation ratio of CS-Cluster is(2d+1)λ,whereλis a parameter related with d but is no more than 18.4.Compared with the previous best result O(d~2),our approximation ratio is a great improvement.Our evaluation result-s demonstrate the outstanding performance of our algorithm compared with previous works.