文档介绍：硕士学位论文
题目: 无线传感器网络中继器放置的容错性问题
与算法研究
研究生王云
专业运筹学与控制论
指导教师陈光亭教授
完成日期 2012 年 10 月
杭州电子科技大学
学位论文原创性声明和使用授权说明
原创性声明
本人郑重声明: 所呈交的学位论文,是本人在导师的指导下,独立进行研究工作所取得
的成果。除文中已经注明引用的内容外,本论文不含任何其他个人或集体已经发表或撰写过
的作品或成果。对本文的研究做出重要贡献的个人和集体,均已在文中以明确方式标明。
申请学位论文与资料若有不实之处,本人承担一切相关责任。
论文作者签名: 日期: 年月日
学位论文使用授权说明
本人完全了解杭州电子科技大学关于保留和使用学位论文的规定,即:研究生在校攻读
学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后,发表论文或
使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送交论文的复印件,
允许查阅和借阅论文;学校可以公布论文的全部或部分内容,可以允许采用影印、缩印或其
它复制手段保存论文。(保密论文在解密后遵守此规定)
论文作者签名: 日期: 年月日
指导教师签名: 日期: 年月日
杭州电子科技大学硕士学位论文
无线传感器网络中继器放置的容错性问题
与算法研究
研究生: 王云
指导教师: 陈光亭教授
2012 年 10 月
Dissertation Submitted to Hangzhou Dianzi University
for the Degree of Master
Fault-Tolerant Relay Node Placement in Wireless
works: Problem and Approximation
Candidate: Wang Yun
Supervisor: Prof. Chen Guangting
October,2012
杭州电子科技大学硕士学位论文
摘要
无线传感器网络是由基站和大量价格低廉、能量较少的传感器组成的。在无线传感器网
络中,传感器主要作用是感知周围的环境,并把收集到的信息传送给基站。传感器节点在恶
劣的环境中随机的分布,能量只能由不能随意更换的电池提供。但是能量消耗在长距离通讯
中却以距离指数的形式快速增加,所以研究者们提出了在无线传感网络中放置一定数目的中
继器的思路,这成为了减少能量损耗的重要方法。其中放置问题的容错性研究是无线传感器
网络中非常重要的问题。容错性就是当系统发生一些故障或错误时,仍然能够正常工作的能
力。如果某些节点遭到恶意攻击或受到损坏,那么无论在何种类型的无线传感器网络中,整
个系统都可能会崩溃,因此容错性研究对于放置问题是至关重要的。
本文的主要工作是讨论含有基站的单层和双层无线传感器网络上具有不同条件的中继器
放置问题。因为这些问题都是NP-hard,所以本文对每一个问题都设计了一个近似算法并且给
出其性能比。本文结构如下:
第1章绪论介绍图论及组合优化等基本理论知识,为后续章节作铺垫。
第2章介绍无线传感器网络的发展背景、中继器放置问题的相关研究成果以及进展,简单
描述了一些重要参考文献中常用的数学模型和典型的算法,并对其优缺点进行比较,以及对
相同类型问题不同算法的特点分析。
第3章和第4章为本文重点内容。第3章首先讨论含有基站的单层无线传感器网络放置问
题,对于2-连通问题,在 R r 的情形下给出了性能比为12的近似算法。继而在双层无线传感
器网络2-覆盖2-连通问题中引入基站,针对 R r 的情形设计了性能比为在16 的近似算法。
这两个算法为第4章的研究奠定基础。第4章研究了 k -连通问题,对于单层无线传感器网络,
研究 R r 的情形下的 k -连通和 k -全连通问题;对于双层无线传感器网络,讨论 R r 的情形
下的不含基站和含有基站的 k -覆盖 k -连通问题,并给出算法及性能比。
第5章是对论文内容进行的概括与对未来工作的展望,指出了一些有待我们进一步深入研
究的无线传感器网络问题。
关键词:中继器放置,基站,无线传感器网络,容错性,近似算法,性能比
I
杭州电子科技大学硕士学位论文
ABSTRACT