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

第36卷第13期 计算机工程 2010年7月 2010 VoL36 July No．13 Engineering Computer 文献标识码：A 中图分类号：TP393 ·网络与通信· 文章编号：looo-_3428(20lo)13-一0los—03 基于节点邻居关系的MCDS构造算法 王楠槽，禹继国，齐迎迎 (曲阜师范大学计算机科学学院，日照276826) l要：针对连通控制集在无线传感器网络中的重要作用，提出一种基于节点邻居关系的最小连通拄制集(MCDS)的构造算法，该算法时 间和信息复杂度分别为0(nlogn)和q一)，且针对由于节点电池的耗尽等原因造成的网络拓扑改变的情况，提出一种局部的修复算法以得到 新网络的一个MCDS。理论分析和仿真实验都表明了算法的JE确性以及执行性能。 关健诩：无线传感器网络；最小连通控制集；Steiner树；闭邻居 for Nodes Relation—basedConstruction Neighborhood Algorithm MinimumContotedDq pminationet etcennDOmmationoteS WANG Nan-nan，YUJi-guo，QIYing-ying Normal (School Science，QufuUniversity,Rizhao276826) ofComputer setis inWirelessSensor avirtualbackboneforcommunicationand important routing IAbstract]Connecteddominatingvery Networks(WSN)as betweennodes．This a based toconstructaMinimumConnected WSN． paperproposesnodes’neighborhood DominatingSet(MCDS)in algorithm The and tothe dueto oftime ateD(nlogn)and powerconstraint，itpresents complexitiesmessage 0(n)，respectively．Regardingtopologicalchanges a toreconstructtheMCDS．Theoreticalandsimulationsbothdemonstratethecorrect