1、面向拓扑信息感知无线传感器网络路由技术的研究上海海洋大学学位论文原创性声明本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经明确注明和引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对所写的内容负责，并完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期： 年 月 日上海海洋大学学位论文版权使用授权书学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权上海海洋大学可以将
2、本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。保密 ，在 年解密后适用本版权书。本学位论文属于不保密 学位论文作者签名： 指导教师签名：日期： 年 月 日 日期： 年 月 日上上海海海海洋洋大大学学 硕士学位论文 答辩委员会成员名单姓名 工作单位 职称 备注刘广钟 上海海事大学 教授 主席袁红春 上海海洋大学 教授 委员池涛 上海海洋大学 教授 委员郑永德 上海海洋大学 研究员 秘书答辩地点上海海洋大学信息学院 306 室答辩日期 2012.1.5上海海洋大学硕士学位论文面向拓扑信息感知的无线传感器网络路由技术研究摘 要无线传感器网络
3、技术作为新兴技术之一，近年来得到了迅速发展。无线传感器网络主要由布置在监测区域中大量的廉价微型传感器节点组成，实时监测传感器网络中的环境信息，在当今军事、医疗、养殖、商业等各个领域得到广泛的应用。因此无线传感器网络具有巨大的应用价值和广阔的发展前景，并且受到国内外学者的高度重视。无线传感器网络节点能量有限，因此能量高效性是路由设计的首要目标。网络拓扑是路由设计的主要依据，然而网络拓扑的动态性给路由协议的设计带来了一定困难。拓扑边缘（包括外部边缘和内部边缘洞）是网络拓扑的突出特征，因此本文研究热点是通过节点自组织算法得到明确的边缘拓扑信息，设计出高效的路由策略。国内外学者已经提出了一些边缘检测算
4、法，但是这些算法仅仅针对边缘信息的获取，没有将拓扑边缘信息加以区分，得到的拓扑边缘信息不够明确，因此不能够很好的应用在路由协议的性能改善方面。并且网络主要依靠 GPS 设备得到节点的位置信息，在大规模部署的网络中带来巨大的成本和能量开销，不适用于低功耗的无线传感器网络。因此本文从边缘信息的获取，边缘信息的区分以及节点坐标的确定等着手，分别提出模糊边缘检测算法、基于梯度域的拓扑识别算法，从而得到明确的边缘拓扑信息，最终结合网络拓扑信息，提出能量高效的路由策略。 文章首先通过分析拓扑边缘信息给路由带来的影响，提出模糊边缘检测算法，该算法利用一跳邻居节点信息，通过分布式计算得到拓扑边缘信息，相对于其
5、它边缘检测算法复杂度更低并且能够动态调整边缘宽度。为了能够得到更加明确的地理信息，提出基于梯度域的拓扑识别算法，通过选择两个信源节点将监测区域划分为梯度域，根据梯度环被拓扑边缘分割的特点来区分拓扑边缘信息，不仅能够识别内外边缘而且能够区分不同的边缘洞，从而得到更加明确的拓扑信息。 根据网络的拓扑边缘结构特点，本文提出基于拓扑边缘的层次树路由，首先依据拓扑信息将网络进行划，分为多个梯度环，并且计算出各梯度环的最优树节点，然后进入路由建立阶段。路由的建立分为层次路由树的建立阶段和数据传输 阶段。在层次路由树建立阶段首先确定各梯度环的树节点，建立上层路由树，并I上海海洋大学硕士学位论文且每个树节点自
6、立为下层路由树的根节点；网络中非树节点选择加入最近的根节点并建立下层路由树，至此完成层次路由树的建立。无线传感器网络路由建立之后进入数据传输阶段，节点根据分配的时隙稳定传输数据到根节点，最终汇聚到Sink 节点。两个阶段为一个轮，每一轮要重新选择树节点。利用 VC6.0 以及 Matlab 对路由算法进行仿真，首先对比 LEACH 和 PEGASIS分析路由延迟，其次对梯度环的大小进行分析，最后将本文提出的路由算法与LEACH 与 LEACH-C 以及 GAF 路由算法进行比较，分别在无边缘洞和有边缘洞的情况下进行分析，最终得出结论：本文提出的基于拓扑边缘的层次树路由延迟比较小，节点负载比较均
7、衡，延长了网络生命期。最后对论文进行了总结与展望。对本文提出的拓扑控制策略进行了终结，并针对本文提出的拓扑获取算法以及路由算法进行分析，提出今后需要做的工作。关键词：无线传感器网络，拓扑边缘，路由树II上海海洋大学硕士学位论文Wireless Sensor Network Routing Research based onTopology Information PerceptionABSTRACTAs an emerging technology, wireless sensor networks have been developingrapidly in recent years. Su
8、ch networks consist of large numbers of low-cost microsensor nodes distributed in target area in charge of real-time environmental Monitoring.There are many different applications including military, medicine, agriculture andtransportation applications. More and more domestic and foreign scholars an
9、dspecialists pay highly attention to it. Generally, Wireless sensor networks have greatapplication value and broad development prospects.The energy of wireless sensor nodes is limited, therefore energy efficiency is themain goal of routing design. Network topology is the main basis of routing design
10、, atthe same time dynamic network topology increases the difficulties on the design. Thesalient features of the network topology are that topology boundary includes externaland internal boundary. This paper mainly describes explicit boundary topologyinformation acquisition by self organizing algorit
11、hm, thereby efficient routing protocolis proposed.Scholars at home and abroad have raised a number of boundary detectionalgorithms, but these algorithms are just intended primarily for accessing to boundaryinformation, there is no distinction between boundary topology information, boundarytopology i
12、nformation are not clear enough to improve routing performance. Andnetworks rely mainly on the GPS device to obtain nodes location information, this leadsto a huge cost of funds and energy in large scale network, so it doesnt apply to low -power wireless sensor networks. From the three dimensions of
13、 boundary topologyinformation acquisition, boundary information distinguish, and determine the nodecoordinates, this paper respectively proposes innovative ways to get the clear boundarytopology information. Ultimately combined with network topology information, chapter5 proposes energy efficient ro
14、uting strategy.First of all, this article analyzes the impact of edge information on routing topology,proposes fuzzy edge detection algorithm which gets topological boundary informationby distributed computing using one hop node information. This algorithm is relativelower complexity than other boun
15、dary detection algorithm and could adjust the edgewidth. Aim to get more specific geographical information, this article proposedtopology recognition algorithm based on gradient domain which divides monitoringIII上海海洋大学硕士学位论文areas into multiple gradient domain by selecting two source node, and distin
16、guishesboundary topology information according to the characteristic that gradient rings aredivided by topological edges, thus distinguishes inside and outside boundary to getmore clear topology information.This article proposes minimum energy consumption tree routing topology edgebased on boundary
17、information. First of all, divides the network into multiple gradientrings according to the topology information, and calculates best tree node of gradientrings, and enters the stage of routing establishment. The stage is divided intohierarchical routing tree establishment phase and the data transmi
18、ssion phase.In hierarchical routing tree establishment stage, first determines the tree nodes ofthe gradient rings, establishes upper - level routing tree, and each tree node stand for theroot node of lower levels; non - root nodes add on the nearest root node to establish theunderlying routing tree
19、, so completed establishment of hierarchical routing tree.After routing established the whole network goes into the data transmission phase,the nodes transfer data to root node according to its allocated time slots, eventuallyconverge to sink nodes. For one round in two phases, each round must selec
20、t the treenode again.Chapter 6 using VC6.0 and Matlab for algorithm simulation , first comparesrouting delay between LEACH and PEGASIS, analyzes on the size of gradient ring , atlast make comparison among routing algorithm in this article, LEACH and LEACH-Cand GAF routing algorithm respectively in t
21、he situation of none boundary hole andboundary hole . Eventually conclusions : minimum energy consumption tree routingbased on topology boundary has low transmission delay , balanced node load andextendes the network life period .Finally, gives a summary about analysis topology acquisition algorithm
22、 androuting algorithm in this article, and prospects about next -stage work need to be donein the future.KEY WORDS： wireless sensor networks, topological boundary, routing treeIV上海海洋大学硕士学位论文摘 要.I第一章 引 言.1 1.1 背景及意义.1 1.2 国内外研究现状.2 1.3 问题的提出及组织结构.3第二章 无线传感器网路由协议研究.6 2.1 无线传感器网络路由协议特点及设计要求.6 2.2 无线传感器
23、网络路由协议的分类.8 2.3 无线传感器网路地理位置路由分析.10第三章 模糊拓扑边缘检测算法.13 3.1 拓扑边缘检测算法.13 3.2 模糊拓扑边缘检测算法.15 3.2.1 理论基础及定义.15 3.2.2 算法设计.16 3.2.3 算法流程.18 3.3 算法仿真.19第四章 基于梯度域的拓扑洞识别算法.21 4.1 问题提出.21 4.2 算法设计.22 4.2.1 信源节点的选择.22 4.2.2 算法流程.23 4.3 应用及仿真分析.24第五章 基于拓扑边缘的层次树路由.27 5.1 传统的路由树.27 5.2 层次路由树.29 5.2.1 网络模型.29 5.2.2 层次树的建立.30 5.3 基于边缘的区域划分.31 5.3.1 无线传感器网络分环模型.31 5.3.2 最优树节点的选择.32第六章 仿真分析.35 6.1 时延分析.
