Home > Published Issues > 2016 > Volume 11, No. 1, January 2016 >

Connected Dominating Set Construction Algorithm for Wireless Networks Based on Connected Subset

Qiang Tang 1,2, Yuan-Sheng Luo 1,2, Ming-Zhong Xie 1,2, and Ping Li 1,2
1. Hunan Provincial Key Laboratory of Intelligent Processing of Big Data on Transportation, Changsha University of Science and Technology, Changsha, China
2. School of Computer and Communication Engineering, Changsha University of Science and Technology, Changsha, China

Abstract—In this paper, a Connected Dominating Set (CDS) construction algorithm CSCDS (Connected Subset based CDS) is proposed, which is based on the connected subset concept. The CSCDS contains two main stages, which are dominating set construction stage and connected dominating set construction stage respectively. In the first stage, the dominators are proposed based on the one hop white neighbor information, and the redundant dominators are reduce to obtain the minimum number of dominators. In the second stage, the CDS is constructed based on the connected subset, which is used as the basis to select the connectors. The message complexity is O(Δ2) (O(Δ2) is a linear relationship function with Δ2, and Δ is the maximum one hop neighbor degree), Simulation results show that CSCDS has smaller size compared with the classical algorithms.

Index Terms—Connected dominating set, connected subset, wireless networks, dominating set construction stage, connected dominating set construction stage

Cite: Qiang Tang, Yuan-Sheng Luo, Ming-Zhong Xie, and Ping Li, “Connected Dominating Set Construction Algorithm for Wireless Networks Based on Connected Subset," Journal of Communications, vol. 11, no. 1, pp. 50-57, 2016. Doi: 10.12720/jcm.11.1.50-57

PREVIOUS PAPER
Cooperative Caching Placement in Cognitive Device-to-Device Networks
NEXT PAPER
Cryptanalysis of Kim Jiye et al.’s Two-Factor Mutual Authentication with Key Agreement in WSNs