无线传感器网络最小连通覆盖的节能算法.pdf

《无线传感器网络最小连通覆盖的节能算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第3期计算机仿真2014年3月文章编号：1006—9348(2014)03—0324—04无线传感器网络最小连通覆盖的节能算法陈业纲．徐则同(1．长江师范学院数学与计算机学院，重庆408100；2．中国科学院数学研究所，北京100190)摘要：网络的生存期是WSN发展的一个障碍，降低能耗是WSN设计的一个方向，在性能得以保障的前提下，用最少的节点投入工作是节能的有效方法。在目标区域中寻找最小连通覆盖集(MCCS)是一个NP问题，设计了通过CVT+MST构造MCCS的节能算法．当节点的通讯半径大于等于感知圆盘2倍时，CYT求得的就是MCCS，否则需要用MST算法计算WSN的最大独立子

2、集添加辅助节点使之成为MCCS，通过仿真和性能分析，上述节能算法具有时间复杂度低，满足节点均匀环境的要求，为延长网络生存期的研究提供了依据。关键词：最小连通覆盖集：最大独立子集；无线传感器网络中图分类号：TP393文献标识码：B’EnergySavingAlgorithmforMCCSinWSNCHENYe-gang．XUZe—tong2(1．MathematicsandComputerCollege，YangtzeNormalUniversity，Chongqing408100，China；2．InstituteofMathematics，ChineseAcademyofSciences

3、，Beijing100190，China)ABSTRACT：ThedrawbackinthedevelopmentofWSNisitsnetworklifecycle．OneoftheaimsofWSNdesignistoreduceenergyconsumption，i．e．，toapplytheminimumnodeswithoutsacrificingefficiencyisavalidmethodtosaveenergy．SearchingforMCCSinthetargetareaisanNPproblem，whichprovidesanenergy-savingalgorith

4、mbasedonCVT+MSTstructure．Whenthecommunicationradiusofthenodeistwiceaslongasthatoftheperceptiondisc，theresultofCVTisMCCS，otherwise，theMSTalgorithmshouldbe印pliedtocalculatethemaximumindependentsub—setsofWSNappendingauxiliarynodes，thustogetMCCS．Throughthesimulationandthepe~ormaneeanalysis，theenergy-s

5、avingalgorithmprovidestherationalesforthestudyofprolongingthenetworklifecyclewiththeadvantageoflowtimecomplexityandmeetingtheneedsofwell—distributedconditionofthenodes．KEYWORDS：MCCS；Maximumindependentsets；WSN1引言行优化部署和对节点进行合理调度等手段，并且有效合理的网络覆盖是WSN应用的基础，它直接影响网络的性能。利用传感器网络的极其有限的节点资源，最后达到改善传感网络中节点数量多．分

6、布自由且密集、其能量、通信、计算和器网络监控服务质量的目的。存储能力受限和无人职守、环境的恶劣给网络覆盖带来了极大的挑战。网络覆盖体现了WSN网络对物理世界的感知能2相关网络覆盖问题力，WSN网络的覆盖效果与每个传感器节点的覆盖类型及网络覆盖是WSN研究的基本问题，其从网络感知物理其位置密切相关，作为基于传感器节点地理位置分布的网络世界的角度，关注通过网络节点的位置分布完成满足应用需服务质量的量度。网络覆盖算法的优劣直接影响着网络的求的被监测区域物理信息的采集。国内外的学者在目标覆感知质量。不同的应用中网络覆盖算法设计的目标和关注盖、栅栏覆盖和区域覆盖方面作了广泛的研究。内容不同，通常根据

7、不同的条件假设、环境限制和研究目标目标覆盖也叫点覆盖，对被监测区域中位置确定的目标而提出具体的覆盖方案。所以，覆盖控制的问题，就是在节点进行数据的采集和监测，其要求满足覆盖要求的同时考虑点所携带的能量、节点的计算存储能力和网络通信带宽等这节能，在文献[1—5]中，采用“活动”和“休眠”节点方案来提些资源受到严重约束的条件下，通过对网络中传感器节点进高网络的生存时间。栅栏覆盖也叫线覆盖．它研究了目标穿越WSN时被检基金项目