无线传感器网络中覆盖与连通算法的研究

《无线传感器网络中覆盖与连通算法的研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、湖南大学硕士学位论文无线传感器网络中覆盖与连通算法的研究姓名：杜辉申请学位级别：硕士专业：计算机软件与理论指导教师：肖德贵20070319硕士学位论文摘要近年来，集成了传感器技术、微电子技术和无线通信技术的无线传感器网络已引起各国政府、研究机构和企业的高度关注，它在军事、环境科学、医疗健康和其他商业领域都有着广阔的应用前景。无线传感器网络发展至今，仍有许多可以应用的环境待开发，也仍有许多技术上的问题需要克服，值得各界学者及研究团队继续深入地研究。连通与覆盖是无线传感器网络的两个最基本的问题。覆盖是指利用网络中的传感器节点对整个目标区域进行监测，从

2、而达到信息采集的目的。为了反映无线传感器网络覆盖的质量，覆盖度通常是评价网络覆盖能力的QOS指标之一。通过引入节点“覆盖模板”的概念，本文提出一种覆盖模板扫描算法CTS(CoverageTemplateScan)求解无线传感器网络覆盖度，并克服传统算法中可变的节点感知半径以及节点覆盖圆边界效应的影响，更好地满足实际应用需求。无线传感器网络中，为节约能耗仅将高密度随机分布的传感器节点中尽可能少的节点投入活跃工作状态。如何求解能覆盖整个目标区域且工作节点个数最少的节点集合，是一个NP难问题。本文设计了一种基于遗传算法求解最小覆盖集的优化算法，求解覆盖

3、整个目标区域的最小节点覆盖集。仿真结果表明，算法能在节点数量和有效覆盖率中做出合理权衡，得到更适应实际应用要求的最小覆盖集。无线传感器网络的连通是指网络中任意两个节点之间都能够进行通信，这是节点自组织形成网络的前提。通过分析连通与覆盖之间的关系，文中给出了覆盖意味着连通的充分必要条件。当节点通信半径大于等于2倍感知半径时，由遗传算法构造的最小节点覆盖集是连通的；当节点通信半径小于2倍感知半径时，引入一种基于最小生成树(minimumspanningtree,简称MST)的连通算法来计算确保遗传算法构造的最小节点覆盖集连通所需的辅助节点，保证网络对

4、监视区域的覆盖与连通。通过上述对覆盖与连通问题的研究，最终可以得到覆盖整个目标区域且节点相互连通的最小连通覆盖集(MCCS)。关键词：无线传感器网络；遗传算法；覆盖度；最小连通覆盖集I无线传感器网络中覆盖与连通算法的研究AbstractRecenttechnologicaladvancesinmicro-electro-mechanicalsystems(MEMS)technology,wirelesscommunications,anddigitalelectronicshaveledtotheemergenceoflarge-scalesen

5、sornetworks.Ithasbeenpredictedtohaveawiderangeofapplicationsrelatedtonationalsecurity,military,environment,healthcare,homeandothercommercialareas.Manyresearchersarecurrentlyengagedindevelopingthetechnologiesneededfordifferentlayersofthesensornetworks.Twoofthemostfundamentalpr

6、oblemsinWSNareconnectivityandcoverage.Coveragemeansthatoverallareashouldbesensedbyallnodessothattheobservercanobtainthewholeinformation.Inthepaper,wecomputerthecoveragedegreeinthewirelesssensornetwork,andproposetheCTS(CoverageTemplateScan)algorithmbyintroducingtheconceptofCov

7、erageTemplate.TheCTSalgorithmtakesfullattentiontoboththedifferentsensingrangeofnodesandtheboundaryeffectofthecoveragerange,soitnotonlysolvesthekcoverageproblem,butalsostrengthenstheadaptationoftheactualapplication.Oneeffectiveapproachtoconservingsystemenergyinwirelesssensorne

8、tworksistokeeponlyaminimalnumberofsensorsactive.Theproblemofcomputin