一种参考能量的最小连通支配集近似算法.pdf

《一种参考能量的最小连通支配集近似算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2015年第34卷第l期传感器与微系统(TransducerandMicrosystemTechnologies)145DOI：10．13873／J．1000--9787(2015)01--0145--03一种参考能量的最小连通支配集近似算法赵煜，降爱莲(太原理工大学计算机科学与技术学院，山西太原030024)摘要：在无线传感器网络中，能量效率问题至关重要，构造精简的虚拟骨干网可以节约有限资源，这等同于在图论中求解最小连通支配集(MCDS)问题。由此，提出一种构造MCDS的启发式算法。首先根据均值公式为顶点建立次序表，其次构造极大独立集(MIS)，再次连接MIS节点，

2、最后优化。仿真实验表明：该算法能够在短时间内找到规模较小的连通支配集(CDS)，并且有效地均衡了各节点能量，延长了网络生命周期。关键词：无线传感器网络；最小连通支配集；极大独立集；网络生命周期中图分类号：TP301．6文献标识码：A文章编号：1000-9787(2015)01-0145--03A^relnerenCeenergYapproxi‘mat-i■onalgori●t·hlmI^orml●nl●mUmconnecteddominatingsetZHA0Yu．JIANGAi—lian(SchoolofComputerScienceandTechnology，Ta

3、iyuanUniversityofTechnology，Taiyuan030024，China)Abstract：TomakeeficientuseoflimitedenergyresourcesissignificantinWSNs，amajorwaytosavelimitedenergyresourcesisconstructingasmallervirtualbackbone，whichisequivalenttofindtheminimumconnecteddominatingset(MCDS)ingraphtheory．Thus，aheuristicMgor

4、ithmtoconstructtheMCDSisproposed．Firstly，accordingtoaverageformula，establishorderedlistforvertex，thenconstructthemaximumindependentset(MIS)，andthenconnectnodesofMIS，finally，optimizeCDS．Simulationexperimentsshowthatthealgorithmcanfindsmallerconnecteddominatingsetinshorttime，andeffectivel

5、ybalancesenergyofeachnodetoextendlifetimeofnetwork．Keywords：wirelesssensornetworks(WSNs)；minimumconnecteddominatingset(MCDS)；maximumindependentset(MIS)；lifetimeofnetwork0引言网络。然而，求解一个网络图的MCDS是一个NP难题，无线传感器网络(wirelesssensornetworks，WSNs)广泛目前还没有成熟算法，因此，需要设计一种高效的近似算法应用在很多重点领域，如国防、环境监测、工农业控制等

6、，具来求解网络图的MCDS。有较高的应用价值。传感器节点由电池供电，电量有限，能1现有算法描述量一旦耗尽将不能继续正常工作，所以，在保证网络连通的目前求解MCDS的方法主要有两种：一是先找出一个前提下，如何能够更有效地提高能量使用效率，延长系统生CDS，然后逐步对进行CDS优化，减少其顶点总数从而得到命周期，是目前亟待解决的重要问题。MCDS；二是先找出一个极大独立集(MIS)，再寻找连接在无线传感器网络中，广播操作通常使用“泛洪(flop—点，将MIS中的顶点连接起来最终得到MCDS’。ding)”来完成，经过分析表明J，“泛洪”可能会带来广播文献[7]利用分布式算

7、法LeaderElection构建一棵有风暴问题。在保证覆盖和连通的前提下，使用连通支配集根树，接着找到MIS，最后在此基础上求解CDS。在文(CDS)算法可以构造一个临时转发数据的骨干网络。只有献[7]的基础上，文献[8，9]分别对连接MIS的顶点方式和网络中的骨干节点负责转发数据，而那些非骨干节点在不构造MIS的方式做出了改进。发送数据时，可关闭通信模块以节省能量。为了使网络寿文献[6]在文献[8，9]的基础上，提出首先通过BFS建命最大化，需要构造一个最小连通支配集(MCDS)的骨干立一棵有根树，获得顶点的等级和优先次序表，再次凭借优收稿日期：