计算机工程与科学

作者：汤强，谢明中，罗元盛

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

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

基金：国家自然科学基金（61303043）；湖南省自然科学（13JJ4052）；湖南省教育厅资助科研项目（13C1022，13C1023）

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

来源：2016年第6期

《计算机工程与科学》期刊编辑部

查看计算机工程与科学杂志2016年第6期