基于多生成树和子网-节点度联合权重的MCDS构造算法

J4 ›› 2016, Vol. 38 ›› Issue (06): 1103-1110.

基于多生成树和子网-节点度联合权重的MCDS构造算法

汤强，谢明中，罗元盛

（长沙理工大学计算机与通信工程学院,湖南长沙 410114）

收稿日期:2015-05-14 修回日期:2015-08-27 出版日期:2016-06-25 发布日期:2016-06-25
基金资助:
国家自然科学基金（61303043）；湖南省自然科学（13JJ4052）；湖南省教育厅资助科研项目（13C1022，13C1023）

A minimum connected dominating set construction
algorithm based on multiple panning trees and
sub networknode degree united weight

TANG Qiang，XIE Mingzhong，LUO Yuansheng

（School of Computer and Communication Engineering,Changsha University of Science and Technology,Changsha 410114,China）

Received:2015-05-14 Revised:2015-08-27 Online:2016-06-25 Published:2016-06-25

摘要/Abstract

摘要：

提出了一种基于多生成树和子网节点度联合权重的静态无线网络极小连通支配集MCDS构造算法SWNMCDS。算法首先设定一个概率p，每个节点随机生成一个概率并与p对比后决定是否成为候选根节点。两跳范围内的候选根节点相互交换信息，确定最终的根节点。每个根节点基于节点权重的连通树生成算法生成多棵连通树。最后基于子网节点度联合权重选择连通节点，将多棵连通树连成极小连通支配集。经分析，SWNMCDS算法近似比上限为2β(2+H(Δ))，时间复杂度为O(Δ2)，消息复杂度为O(Δ2)(Δ为最大一跳邻居节点集合的大小，β为生成树数目)。仿真实验表明，与经典MCDS算法比较，SWNMCDS所构造的连通支配集具有较小的规模。

关键词: 多生成树, 子网节点度联合权重, 极小连通支配集, 静态无线网络

Abstract:

We propose a minimum connected dominating set (MCDS) construction algorithm called static wireless networks’ minimum connected dominating set (SWNMCDS) based on multiple spanning trees and sub networknode degree united weight for static wireless networks. At first, a probability p is set, and every node randomly generates a probability. The nodes whose generated probability is less than p become root node candidates. The root node candidates within two hops exchange information with each other to determine the final root nodes. Based on the node weight, the root nodes generate multiple connected trees respectively. All the connected trees are connected with each other into a minimum connected dominating set based on the selected connected nodes according to the sub networknode degree weight. Analysis results show that the upper bound of the performance ratio is 2β(2+H(Δ)), and the time complexity as well as the message complexity is O(Δ2), where Δ is the size of the biggest one hop neighbor set, and β is the number of spanning trees. Compared with the traditional algorithm MCDS, the SWNMCDS has a smaller connected dominating set.

Key words: multiple spanning trees;sub network-node degree united weight;minimum connected dominating set;static wireless network

汤强，谢明中，罗元盛. 基于多生成树和子网-节点度联合权重的MCDS构造算法[J]. J4, 2016, 38(06): 1103-1110.

TANG Qiang，XIE Mingzhong，LUO Yuansheng. A minimum connected dominating set construction
algorithm based on multiple panning trees and
sub networknode degree united weight [J]. J4, 2016, 38(06): 1103-1110.