《无线传感器网络若干中继器放置问题研究》由会员分享，可在线阅读，更多相关《无线传感器网络若干中继器放置问题研究（48页珍藏版）》请在金锄头文库上搜索。
1、杭州电子科技大学 硕士学位论文 无线传感器网络若干中继器放置问题研究 姓名：崔素辉 申请学位级别：硕士 专业：运筹学与控制论 指导教师：陈光亭 20091001 杭州电子科技大学硕士学位论文 I 摘 要 节能是无线传感器网络研究的核心问题。传感器随机分布在恶劣环境中，能量由电池提 供，电池不能够随意更换。但是长距离通讯中能量消耗以距离指数形式增长，因此放置功能 强大的中继器成为了减少能量损耗的重要方法。本文主要研究在不同类型的无线传感器网络 中放置最少数目的中继器达到一定的覆盖和连通要求。 首先从图与网络及组合优化的基本理论知识入手，为后续章节作铺垫。 第 2 章阐述无线传感器网络相关知识背景
2、和研究进展，主要针对重要文献，介绍常用的 数学模型和典型方法、算法，并对其优缺点进行比较、分析。 第 3 章至第 5 章为本文重点内容，这里讨论的问题均为 NP-hard 问题，故针对每个问题 设计了相应的近似算法。 第 3 章首先讨论含有基站的单层无线传感器网络放置问题，根据传感器和中继器传输半 径的不同情况，分别设计了性能比为 3 和 7 的近似算法，并且对于后者，给出了算法的下界 估计。继而在双层无线传感器网络中引入基站，设计了性能比为5+的近似算法，为第 4 章 的研究奠定基础。 传感器节点很容易被破坏，在任何情况下都可能由于能量损耗、环境侵蚀或是受到恶意 攻击而失效，因此有关容错性的
3、设计至关重要。第4章分别研究了含有基站的单层和双层无线 传感器网络的容错性。对于单层无线传感器网络，研究k-连通问题；对于双层无线传感器网 络，首先对双覆盖双连通问题设计近似算法，并将其容错性推广到k -覆盖2-连通，给出算法 及性能比。 随着定位系统的日益发展，二维空间的研究渐渐不能够满足人们的需求。第 5 章中研究 三维无线传感器网络的中继器放置问题，主要针对双层无线传感器网络上的单覆盖单连通和 容错性问题，根据算法因子的取值不同，设计相应的算法，给出常数性能比。因此拓宽了无 线传感器网络的研究及应用领域。 最后在第6章中对本文进行总结与展望， 并指出有关无线传感器网络放置问题中的一些有
4、待继续研究的问题。 关键词：中继器放置，基站，单层无线传感器网络，双层无线传感器网络，容错性，三维无 线传感器网络，混合无线传感器网络 杭州电子科技大学硕士学位论文 II ABSTRACT Energy saving is the key problem in wireless sensor networks. Since sensor nodes are powered by batteries and are randomly deployed in harsh environment, it is impossible to replace a battery. But long dis
5、tance commuciation is very costly, because energy consumption is proportional to exponential time of transmitting distance, one important approach to reduce energy depletion is to place some more powerful relay nodes. In this dissertation, we focus on deploying a minimum number of relay nodes in dif
6、ferent types of wireless sensor networks to achieve certain coverage and connectivity requirements. First, we start with the basic theoretical knowledge of graph, network and combinatorial optimization as the preliminary of the dissertation. In chapter 2, we present the background and a survey of wi
7、reless sensor networks, introduce common mathematical models and typical methods and algorithms. Further more, we compare and analyze their advantages and disadvantages. The main contents of this dissertation are from chapter 3 to 5. Due to the problems are NP-hard, so we design approximation algori
8、thm for every considered problem. In chapter 3, we first dissuss relay nodes placement in single-tiered wireless sensor networks with basestations, according to the different case between sensor and relay nodes transmission radius, we present two polynomial time approximation algorithms with perform
9、ance ratio 3 and 7, for the later algorithm, we give the lower bound of the performance ratio. Further more, we introduce basestations in two-tiered wireless sensor networks, and design approximation algorithm with performance ratio5+. Sensor nodes are very vulnerable to failures, they may lose func
10、tionalities at any time because of energy depletion, harsh environment factor or malicious attack, so it is important to consider fault-tolerant in wireless sensor networks. In chapter 4, we study the fault-tolerant in single and two tiered wireless sensor networks with basestations. For the single-
11、tiered situation, k-connectivity is the issue. For the two-tierd wireless sensor networks, we first design approximation algorithm for 2-coverage 2-connectivity problem, then extend to k-coverage 2-connectivity, we give its algorithm and performance ratio. With the coming of the advanced positioning
12、 system, the study of wireless sensor networks in three dimensional space is important. In chapter 5, we first research the relay nodes placement in three dimensional wireless sensor networks, according to the different value of algorithm factor, mainly for the single-coverage single-connectivity an
13、d fault-tolerant in two-tierd wireless sensor 杭州电子科技大学硕士学位论文 III networks, we design the corresponding algorithm, give constant performance ratio. Finally, in chapter 6, we summarize the research, and look forward to the future in wireless sensor networks, show some open problems in the relay nodes
14、placement problems. Keywords：relay nodes placement, basestations, single-tierd wireless sensor networks, two-tierd wireless sensor networks, fault-tolerant, three dimensional wireless sensor networks, heterogeneous wireless sensor networks 杭州电子科技大学杭州电子科技大学杭州电子科技大学杭州电子科技大学 学位论文原创性声明和使用授权说明学位论文原创性声明和使
15、用授权说明学位论文原创性声明和使用授权说明学位论文原创性声明和使用授权说明 原创性声明原创性声明原创性声明原创性声明 本人郑重声明： 所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得 的成果。除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过 的作品或成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名： 日期： 年 月 日 学位论文使用授权说明学位论文使用授权说明学位论文使用授权说明学位论文使用授权说明 本人完全了解杭州电子科技大学关于保留和使用学位论文的规定，即：研究生在校攻读 学位期间论文工作的知识产权单位属杭州电子科技大学。本人保证毕业离校后，发表论文或 使用论文工作成果时署名单位仍然为杭州电子科技大学。学校有权保留送
