无线传感器网络中最小连通传感器覆盖问题的研究

《无线传感器网络中最小连通传感器覆盖问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、硕士学位论文无线传感器网络中最小连通传感器覆盖问题的研究RESEARCHONCONNECTEDSENSORCOVERAGEPROBLEMINWIRELESSSENSORNETWORKS吕静哈尔滨工业大学2013年12月万方数据国内图书分类号：TP393.01学校代码：10213国际图书分类号：004.722.46密级：公开工程硕士学位论文无线传感器网络中最小连通传感器覆盖问题的研究硕士研究生：吕静导师：堵宏伟副教授申请学位：工程硕士学科：计算机技术所在单位：深圳研究生院答辩日期：2013年12月授予学位

2、单位：哈尔滨工业大学万方数据ClassifiedIndex:TP393.01U.D.C:004.722.46DissertationfortheMaster’sDegreeinEngineeringRESEARCHONCONNECTEDSENSORCOVERAGEPROBLEMINWIRELESSSENSORNETWORKSCandidate：JingLvSupervisor：AssociateProf.DUHongweiAcademicDegreeAppliedfor：Master’sDegreein

3、EngineeringSpecialty：ComputerTechnologyAffiliation：ShenzhenGraduateSchoolDateofDefence：December,2013Degree-Conferring-Institution：HarbinInstituteofTechnology万方数据哈尔滨工业大学工程硕士学位论文摘要近年来，随着各种微技术的迅速发展，具有感知、通信、数据处理、存储能力的传感器节点构成的无线传感器网络（WirelessSensorNetworks,WS

4、Ns）引起了社会各界学者的广泛关注。在WSN中，覆盖体现了该WSN对物理监测区域的感知程度，而连通则表明了WSN中节点间发送和接收数据的能力。覆盖和连通作为WSN中的两个基础问题，对网络的能量消耗与生存周期有着重要影响。在WSN执行监测任务时，选择尽量少的传感器节点参与，不仅可以降低网络能耗，提升网络能量的高效性，还能减少传感器节点间的通信开销，降低邻近传感器节点间感知数据的冗余度。基于此点，本文综合考虑WSN中的覆盖与连通问题，找到感知区域满足覆盖整个目标区域，且所诱导出的网络为一个连通网络的最小工作

5、传感器节点集，从而延长网络的生存周期。本文首先提出了一种能够满足网络覆盖与连通要求的基于ConnectedBenefit的节点选择算法。该算法首先通过计算节点对覆盖的贡献量，选择出满足覆盖条件的节点集合，然后根据节点的ConnectedBenefit值补充最少的节点到结果集，使之满足连通条件，从而选择出数目最少的节点执行监测任务。本文接着利用最小生成树（MST）的基本思想，提出了另一种新的节点选择算法。该算法在连通阶段，通过构造一棵权重之和最小的MST对节点进行选择，使之满足覆盖与连通条件。最后本文提出

6、了一种基于GroupSteinerTree与线性规划的节点选择算法。该算法通过构造GroupSteinerTree并用线性规划对其求解，计算出每个节点被选择的概率，为找到近似解提供正确的方向，然后利用求得的节点概率值与随机rounding技术选择出满足覆盖与连通的节点集合。基于ConnectedBenefit与基于MST的节点选择算法，均将覆盖和连通分开来考虑，而基于GroupSteinerTree与线性规划的节点选择算法将二者联合考虑。通过实验对比验证，本文提出的三种算法在不同的网络环境中，性能有所不

7、同，但能够保证得出数目最少的满足覆盖与连通条件的工作节点，从而大幅降低网络能耗，延长网络生存周期。关键词：无线传感器网络；覆盖；连通；最小连通传感器覆盖问题-I-万方数据哈尔滨工业大学工程硕士学位论文AbstractInrecentyears,withtherapiddevelopmentofmicrotechnologies,theemergenceofsensing,communication,dataprocessing,storagecapabilitiessensorshavebroughtr

8、esearchers'stronglyinterestinwirelesssensornetworks(WSNs).InaWSN,thecoveragereflectsthephysicalsensingqualityofthenetworkduringmonitoringthetargetarea,andtheconnectivityindicatesthecapabilityofsendingandreceivingdataintheW