Sun Xuemei, Yang Yongxin, Ma Maode
School of Computer Science and Technology, Tianjin Polytechnic University, Tianjin 300387, China.
School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore 639798, Singapore.
Sensors (Basel). 2019 Apr 23;19(8):1919. doi: 10.3390/s19081919.
To achieve effective communication in ad hoc sensor networks, researchers have been working on finding a minimum connected dominating set (MCDS) as a virtual backbone network in practice. Presently, many approximate algorithms have been proposed to construct MCDS, the best among which is adopting the two-stage idea, that is, to construct a maximum independent set (MIS) firstly and then realize the connectivity through the Steiner tree construction algorithm. For the first stage, this paper proposes an improved collaborative coverage algorithm for solving maximum independent set (IC-MIS), which expands the selection of the dominating point from two-hop neighbor to three-hop neighbor. The coverage efficiency has been improved under the condition of complete coverage. For the second stage, this paper respectively proposes an improved Kruskal-Steiner tree construction algorithm (IK-ST) and a maximum leaf nodes Steiner tree construction algorithm (ML-ST), both of which can make the result closer to the optimal solution. Finally, the simulation results show that the algorithm proposed in this paper is a great improvement over the previous algorithm in optimizing the scale of the connected dominating set (CDS).
为了在自组织传感器网络中实现有效通信，研究人员一直在努力寻找最小连通支配集（MCDS）作为实际中的虚拟骨干网络。目前，已经提出了许多近似算法来构建MCDS，其中最好的是采用两阶段思想，即首先构建最大独立集（MIS），然后通过Steiner树构造算法实现连通性。对于第一阶段，本文提出了一种改进的协同覆盖算法来求解最大独立集（IC-MIS），该算法将支配点的选择范围从两跳邻居扩展到三跳邻居。在完全覆盖的条件下，覆盖效率得到了提高。对于第二阶段，本文分别提出了一种改进的Kruskal-Steiner树构造算法（IK-ST）和一种最大叶节点Steiner树构造算法（ML-ST），这两种算法都能使结果更接近最优解。最后，仿真结果表明，本文提出的算法在优化连通支配集（CDS）规模方面比先前算法有很大改进。
