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

作者：Gao, Xiaofeng^*; Zhu, Xudong; Li, Jun; Wu, Fan; Chen, Guihai; Du, Ding-Zhu; Tang, Shaojie

来源：IEEE/ACM Transactions on Networking, 2017, 25(4): 2223-2234.

DOI：10.1109/TNET.2017.2690359

• Wireless networks
• clustering
• distributed algorithm
• approximation
• connected dominating set

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 d-hop dominating set (d-MCDS) problem, which is proved to be NP-complete. In this paper, we propose a distributed approximation named CS-Cluster to address the d-MCDS problem under unit disk graph. 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+ 1)lambda, where lambda 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 results demonstrate the outstanding performance of our algorithm compared with previous works.

• 出版日期2017-8
• 单位上海交通大学