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

·· 通信学报 第29卷
第11期 李克清等：基于定向扩散的最小连通支配集构造算法 ··

第29卷第11期 通信学报 Vol.29No.11
2008年11月 JournalonCommunications November2008

基于定向扩散的最小连通支配集构造算法
李克清，常晋义，王加年
（常熟理工学院计算机科学与工程学院，江苏苏州215500）
摘要：针对区域覆盖算法未考虑节点的通信梯度问题，利用定向扩散路由在构造以sink节点为根的有向路由树时形成的递增梯度序列，提出了一种基于定向扩散的最小连通支配集构造算法。在路由信息扩散的同时逐级挑选出互不相邻的传感器节点构造出一个最大支撑集，然后在相邻层次的支撑集节点间寻找中间节点将独立集节点连通起来，最终得到一个近似的最小连通支配集。理论及仿真实验结果表明，该算法构造的连通支配集最小且计算耗时少，能多重有效覆盖热点区域，从而延长无线传感器网络的寿命。
关键词：无线传感器网络；区域覆盖；最小连通支配集；定向扩散；轮换调度
中图分类号：TN953文献标识码：A文章编号：1000-436X(2008)11-0091-07
Minimumconnecteddominatingsetalgorithmbasedondirecteddiffusion
LIKe-qing,CHANGJin-yi,WANGJia-nian
(SchoolofComputerScienceandEngineering,ChangshuInstituteofScienceandTechnology,Suzhou215500,China)
Abstract:AnewminimumconnecteddominatingsetalgorithmbasedondirecteddiffusionMCDSDDwasproposed,whichattemptedtoimprovetheexistedareacoveragealgorithmsthroughintroducingnode’sgradientinwirelesssensornetworks.Duringbuiltadirectedtreerootedfromsinknodeusingdirecteddiffusionroutingalgorithm,anascendingnode’sgradientseriescouldbeconstructed.Non-adjacentsensornodeswerepickedoutandmadeupamaximumdominatorsetduringroutinginformationdiffusiongradientbygradient,andthensomeintermediatenodesaresoughtfromthosenodes,whichwereadjacenttobothnodesunconnectedinmaximumdominatorsetandtheirgradientsjustbetweenthemyet,to“glue”thenon-adjacenttwonodesinmaximumdominatorset,andlast,anapproximateminimumconnecteddominatorsetwasconstructed.SimulationresultsshowthatMCDSDDcansavetimeandmultiplecovershotspotinthesurveillancearea,andprolongthelifetimeoftheWSN.
Keywords:wirelesssensornetworks;areacoverage;minimumconnecteddominatorset;directeddiffusion;round-robinscheduling

1引言
收稿日期：2008-06-21；修回日期：2008-10-20
基金项目：江苏省教育厅高校自然科学基础研究自筹经费项目（08KJD520012）
FoundationItem:TheNaturalScienceFoundationoftheJiangsuHigherEducationInstitutionsofChina(08KJD520012)
无线传感器网络（WSN,wirelesssensornetwork）由大量的具有网络自组织能力的微型传感器组成，实时监测、感知和采集监测对象的各种参数，以多跳中继的方式将信息传送到管理者，实现“无处不在的计算”理念[1,2]。无线传感器网络与传统网络（包括WLAN、adhoc网络和蜂窝移动电话网络）有着不同的设计目标。基于TCP/IP协议栈的Intern