无线传感器网络中两类覆盖问题的算法研究

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

1、硕士学位论文题目:无线传感器网络中两类覆盖问题的算法研究研究生张斌权专业运筹学与控制论指导教师陈光亭教授完成日期2015年10月杭州电子科技大学硕士学位论文无线传感器网络中两类覆盖问题的算法研究研究生：张斌权指导教师：陈光亭教授2015年10月DissertationSubmittedtoHangzhouDianziUniversityfortheDegreeofMasterAnalgorithmicstudyontwokindsofcoveringproblemsintheWSNCandidate:BinQuanZhangSuper

2、visor:Prof.GuangTingChenOctober，2015抗州电子科技大学学位论文原创性声明和使用授权说明独创巧声明：所呈交的学位论文本人郑重声明，是本人在导师的指导下，独立进行研巧工作所取得的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中Ｗ明确方式标明。申请学位论文与资料若有不实之处一，本人承担切相关责任。论文作者签名：日期：年月Ｌ曰１ｆ学位论文使用授权说明本人完全了解杭州电子科技大学关

3、于保留和使用学位论文的规定，目Ｐ；研究生在校攻读学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论文或使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可Ｗ公布论文的全部或部分内容，可Ｗ允许采用影印、缩印或其它复制手段保存论文。（保密论文在解密后遵守此规定）＇＇＇论文作者签名：日期：年＾日７＾、月１＾＾＾＞＾／Ｖ｝＾＾指导教师签名；日期：年月＾曰（５杭州电子科技大学硕士学位论文摘要无线传感器网络作为一种全新的信息获取和处理技术

4、，能够广泛应用在反恐抗灾、国防军事、医疗卫生以及环境监测等诸多领域，被认为是二十一世纪最重要的技术之一。目标覆盖问题是传感器网络进行目标识别、监控、跟踪等众多应用的前提，也是无线传感器网络研究中的热点问题之一。现有的目标覆盖类型大致可分为三类：点覆盖、线覆盖以及区域覆盖。本文重点研究点覆盖和线段覆盖两类问题，论文结构主要包括以下三大部分。第一部分，预备知识介绍和问题引入。该部分给出了图论、组合优化、计算复杂性、近似算法等相关定义，并介绍了无线传感器网络中覆盖问题的背景、应用、发展历程以及国内外相关研究成果。第二部分，论文主要内容：对无

5、线传感器网络中的线段覆盖和点覆盖两类问题进行研究。第一类问题——线段覆盖问题，我们重点考虑目标线段处于水平放置或者竖直放置的情形。首先，讨论最大线段长度不超过传感器感应半径两倍的特殊情形，由于该问题是NP-困难的，我们主要从近似算法的角度来求解问题：利用平面分割的思想，设计了一个性能比为18、时间复杂度为(log)nn（n为线段数量）的多项式时间近似算法。其次，利用Java语言编程完成了算法仿真和稳定性检验，以图像形式形象地展示了算法结果，多组数据显示该算法基本稳定。最后，对该问题的一般情形进行了初步探讨。第二类问题——点覆盖问题，

6、重点考虑传感器部署位置不能越过某一条直线的情形（受地理环境或者其他因素的影响，传感器的部署位置可能存在一些禁区）。由于该问题也是NP-2困难的，我们设计了一个性能比为2、时间复杂度为(n)（n为点的数量）的多项式时间近似算法，且有实例表明该性能比是紧的。同样地，该部分也利用Java语言编程完成了算法仿真和稳定性检验，得到了多组算法解与最优解的图像示例，计算结果表明该算法也较为稳定。第三部分，论文的总结和拓展。最后对论文主要内容作了总结，并展望进一步的研究方向。关键词：无线传感器网络，覆盖问题，NP-困难，近似算法，性能比I杭州电子科

7、技大学硕士学位论文ABSTRACTAsanewinformationacquisitionandprocessingtechnology,Wirelesssensornetworkisoneofthemostimportanttechnologiesinthe21stcentury,whichiswidelyusedinmanyfieldssuchasanti-terrorismdisasterm,nationaldefense,healthcareandenvironmentalmonitoring.Thecoveringprobl

8、emisoneofthemostimportantresearchfocusesinwirelesssensornetworks,whichiswidelyusedintargetidentification,monit