基于定向扩散的最小连通支配集构造算法

《基于定向扩散的最小连通支配集构造算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第11期李克清等：基于定向扩散的最小连通支配集构造算法·97·基于定向扩散的最小连通支配集构造算法李克清，常晋义，王加年（常熟理工学院计算机科学与工程学院，江苏苏州215500）摘要：针对区域覆盖算法未考虑节点的通信梯度问题，利用定向扩散路由在构造以sink节点为根的有向路由树时形成的递增梯度序列，提出了一种基于定向扩散的最小连通支配集构造算法。在路由信息扩散的同时逐级挑选出互不相邻的传感器节点构造出一个最大支撑集，然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来，最终得到一个近似的最小连通支配集。理论及仿真实验结果表明，该算法构造的连通支配集最小

2、且计算耗时少，能多重有效覆盖热点区域，从而延长无线传感器网络的寿命。关键词：无线传感器网络；区域覆盖；最小连通支配集；定向扩散；轮换调度中图分类号：TN953文献标识码：A文章编号：1000-436X(2008)11-0091-07MinimumconnecteddominatingsetalgorithmbasedondirecteddiffusionLIKe-qing,CHANGJin-yi,WANGJia-nian(SchoolofComputerScienceandEngineering,ChangshuInstituteofScienceandTec

3、hnology,Suzhou215500,China)Abstract:AnewminimumconnecteddominatingsetalgorithmbasedondirecteddiffusionMCDSDDwasproposed,whichattemptedtoimprovetheexistedareacoveragealgorithmsthroughintroducingnode’sgradientinwirelesssensornetworks.Duringbuiltadirectedtreerootedfromsinknodeusingdire

4、cteddiffusionroutingalgorithm,anascendingnode’sgradientseriescouldbeconstructed.Non-adjacentsensornodeswerepickedoutandmadeupamaximumdominatorsetduringroutinginformationdiffusiongradientbygradient,andthensomeintermediatenodesaresoughtfromthosenodes,whichwereadjacenttobothnodesunconn

5、ectedinmaximumdominatorsetandtheirgradientsjustbetweenthemyet,to“glue”thenon-adjacenttwonodesinmaximumdominatorset,andlast,anapproximateminimumconnecteddominatorsetwasconstructed.SimulationresultsshowthatMCDSDDcansavetimeandmultiplecovershotspotinthesurveillancearea,andprolongthelif

6、etimeoftheWSN.Keywords:wirelesssensornetworks;areacoverage;minimumconnecteddominatorset;directeddiffusion;round-robinscheduling第11期李克清等：基于定向扩散的最小连通支配集构造算法·97·1引言收稿日期：2008-06-21；修回日期：2008-10-20基金项目：江苏省教育厅高校自然科学基础研究自筹经费项目（08KJD520012）FoundationItem:TheNaturalScienceFoundationoftheJian

7、gsuHigherEducationInstitutionsofChina(08KJD520012)无线传感器网络（WSN,wirelesssensornetwork）由大量的具有网络自组织能力的微型传感器组成，实时监测、感知和采集监测对象的各种参数，以多跳中继的方式将信息传送到管理者，实现“无处不在的计算”理念[1,2]。无线传感器网络与传统网络（包括WLAN、adhoc网络和蜂窝移动电话网络）有着不同的设计目标。基于TCP/IP协议栈的Internet遵循“端到端”的边缘论设计思想[3~5]第11期李克清等：基于定向扩散的最小连通支配集构造算法·97·，将

8、一切与功能相关的处理都放在网络的端系统