基于多生成树和子网-节点度联合权重的MCDS构造算法
【出 处】:
【作 者】:
汤强
;
谢明中
;
罗元盛
【摘 要】
提出了一种基于多生成树和子网-节点度联合权重的静态无线网络极小连通支配集MCDS构造算法SWNMCDS。算法首先设定一个概率p,每个节点随机生成一个概率并与p对比后决定是否成为候选根节点。两跳范围内的候选根节点相互交换信息,确定最终的根节点。每个根节点基于节点权重的连通树生成算法生成多棵连通树。最后基于子网-节点度联合权重选择连通节点,将多棵连通树连成极小连通支配集。经分析,SWNMCDS算法近似比上限为2β(2+H(Δ)),时间复杂度为O(Δ^2),消息复杂度为O(Δ^2)(Δ为最大一跳邻居节点集合的大小,β为生成树数目)。仿真实验表明,与经典MCDS算法比较,SWNMCDS所构造的连通支配集具有较小的规模。
相关热词搜索: 多生成树 子网-节点度联合权重 极小连通支配集 静态无线网络 multiple spanning trees sub network-node degree united weight minimum connected dominating set static wireless network
上一篇:支撑产业链协同的公共服务平台研究综述
下一篇:一种改进的ElGamal数字签名方案