A Constant Factor Approximation for d-Hop Connected Dominating Set in 3-Dimensional Wireless Network

Keyword: Wireless Sensor Network, d-CDS, Spanning Tree, Cluster, Distributed Algorithm

In the past few years, wireless sensor networks (WSNs) have been widely used in many areas. In these applications, sensors are remotely deployed to gather related environmental information for further analysis. To support higher scalability and better data aggregation, sensor nodes are often grouped into disjoint and mostly non-overlapping clusters. All nodes in a cluster can send their data to the cluster head within d-hop distance, and the head should communicate with other cluster heads and pass all data to base station. For better communication between these cluster heads, lower maintenance cost, and easier management, it is necessary to make the number of the clusters as small as possible. Moreover, in many environments such as mountainous area or underwater monitoring, node deployment is often not flat, resulting in a high dimensional network. In this paper, we focus on proposing a scheme to select cluster heads for a homogeneous network in three-dimensional situation. The scheme meets two requirements: the number of cluster heads is minimum and the head nodes can communicate with each other. These requirements can be formed as an NP-complete problem named d-hop connected dominating set. Correspondingly, we proposed a distributed approximation algorithm and proved its approximation ratio as (d+1)β, where β is a calculated parameter with respect to d. We also analyzed the performance of our algorithm with corresponding numerical experiments.