基于节点邻居关系的MCDS构造算法  

Nodes Neighborhood Relation-based Construction Algorithm for Minimum Connected Domination Set

作　　者：王楠楠[1] 禹继国[1] 齐迎迎[1] 

机构地区：[1]曲阜师范大学计算机科学学院,日照276826

出　　处：《计算机工程》2010年第13期105-107,110,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(10471078);山东省中青年科学家奖励基金资助项目(2005BS01016);山东省科技攻关计划基金资助项目(2009GG10001014);山东省教育厅科研基金资助项目(J07WH05)

摘　　要：针对连通控制集在无线传感器网络中的重要作用,提出一种基于节点邻居关系的最小连通控制集(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.

关 键 词：无线传感器网络 最小连通控制集 STEINER树 闭邻居 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]