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

Published in IEEE Transactions on Wireless Communications (TWC), 2019

Recommended citation: Ke Li, Xiaofeng Gao, Fan Wu and Guihai Chen. (2019). "A Constant Factor Approximation for d-Hop Connected Dominating Set in 3-Dimensional Wireless Network." IEEE Transactions on Wireless Communications (TWC). 18(9): pp. 4357-4367. http://keli97.github.io/files/A-Constant-Factor-Approximation-for-d-Hop-Connected-Dominating-Set-in-3-Dimensional-Wireless-Networks.pdf

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

  • Designed a scheme to select cluster heads for a homogeneous network in a three-dimensional situation based on the concept of d-hop connected dominating set.
  • Proposed a distributed approximation algorithm and proved its approximation ratio.
  • Conducted numerical experiments with 100 nodes randomly distributed in a three-dimensional Wireless Sensor Network (WSN) to analyze and prove the efficiency of the algorithm.

Download paper here

Recommended citation: Ke Li, Xiaofeng Gao, Fan Wu and Guihai Chen. (2019). "A Constant Factor Approximation for d-Hop Connected Dominating Set in 3-Dimensional Wireless Network." IEEE Transactions on Wireless Communications (TWC). 18(9): pp. 4357-4367.