Nodes Neighborhood Relation-based Construction Algorithm for Minimum Connected Domination Set
Nodes Neighborhood Relation-based Construction Algorithm for Minimum Connected Domination Set
复制标题
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
QI Ying-ying
中科院分区：
文献类型：
--
作者：
QI Ying-ying
连通支配集在无线传感器网络(WSN)中非常重要，作为节点间通信和路由的虚拟骨干网。本文提出一种基于节点邻域的算法来构造WSN中的最小连通支配集(MCDS)。时间复杂度和消息复杂度分别为O(nlogn)和O(n)。针对功率约束引起的拓扑变化，提出了一种修复算法来重构MCDS。理论分析和仿真均证明了该算法的正确性和有效性。算法的性能。
Connected dominating set is very important in Wireless Sensor Networks(WSN) as a virtual backbone for communication and routing between nodes.This paper proposes a nodes’ neighborhood based algorithm to construct a Minimum Connected Dominating Set(MCDS) in WSN.The complexities of time and message are O(nlogn) and O(n),respectively.Regarding to the topological changes due to power constraint,it presents a repair algorithm to reconstruct the MCDS.Theoretical analysis and simulations both demonstrate the correctness and performance of the algorithm.