PROJECT TITLE :

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

ABSTRACT:

Wireless Sensor Networks (WSNs) have been widely utilized in a masses of applications. To attain higher efficiency for data assortment, WSNs are usually partitioned into many disjointed clusters, every with a representative cluster head answerable for the data gathering and routing method. Such a partition is balanced and effective, if the gap between each node and its cluster head can be bounded within a continuing number of hops, and any two cluster heads are connected. Finding such a cluster partition with minimum variety 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. During this paper, we propose a distributed approximation named CS-Cluster to address the d-MCDS downside below unit disk graph. CS-Cluster constructs a sparser d-hop maximal independent set (d-MIS), connects the d-MIS, and eventually checks and removes redundant nodes. We tend to prove the approximation ratio of CS-Cluster is (second + 1)?, where ? may be a parameter related with d but is not more than eighteen.four. Compared with the previous best result O(d2), our approximation ratio may be a great improvement. Our analysis results demonstrate the outstanding performance of our algorithm compared with previous works.