无线传感器网络中分簇路由算法的研究.docx

1、无线传感器网络中分簇路由算法的研究摘要近年来，传感器技术、电子技术和无线通信技术的日趋成熟和发展，为无线传感器网络(Wireless Sensor Network,WSN)的快速发展奠定了基础，使得WSN已经逐步成为计算机科学技术中一个新的研究领域。无线传感器网络具有成本低、体积小、自组织和无线通信等诸多优点，但WSN也有它不可忽视的缺点，其中一个最关键的就是资源受限，节点的计算能力、存储能力和能量都十分有限，而通信模块是能量消耗的主要部分，为了尽可能延长网络的生命周期，设计高效的路由协议成为当前WSN研究的一项关键技术，也是目前WSN领域研究的一个重要课题。为了设计高效可靠的WSN分簇路由协

2、议，本文的研究内容如下：(1) 介绍了无线传感器网络及路由协议的相关背景知识，并重点从网络拓扑结构的不同出发，分析说明了目前比较经典的几种平面路由协议和分簇路由协议的主要思想和研究成果，同时指出了分簇路由相对于平面路由协议的几大优势。(2) 在分析传统和改进LEACH路由协议之后，提出了一种新的均匀分簇改进LEACH算法。该算法采用一种基于时间的簇头选择机制，该机制将节点的剩余能量考虑进内，不仅降低了低能量的节点成为簇头的可能性，且改善了簇头产生的随机性和分布的不均匀性；在路由建立阶段，利用蚁群的动态适应性和寻优能力将蚁群优化算法应用于簇间路由机制中，使数据以多跳形式传输给Sink节点，从而减

3、小节点能量消耗进而提高网络寿命。并通过实验仿真和性能分析，说明了所提算法在生成簇头数、平均能量消耗和节点存活数三个方面相对于LEACH算法的优越性。(3) 在对EEUC协议分析之后，提出了一种能量优化的WSN非均匀分簇路由协议(EOUCR)。对于均匀分簇算法来说，虽然采用多跳路由可以从某种程度上降低网络能耗，但同时也带来了“热区”问题，基于蚁群优化的改进LEACH算法就属于此类算法。针对“热区”问题及典型非均匀分簇路由EEUC算法的不足，本文提出了EOUCR协议，该协议在簇形成阶段以候选簇头的剩余能量、其邻居节点的平均剩余能量和该候选簇头与 Sink节点的距离作为竞选簇头的参数，且簇头竞争半径

4、的选取考虑了成簇能耗，在此基础上形成了不同几何尺寸的簇，可减少“热区”内簇的簇头轮换次数，均衡网络负载。EOUCR在簇间多跳路由通信中引入了唯一与 Sink节点通信的根节点，其他簇头则通过中继节点或直接与根节点通信，克服了EEUC能耗大且不均衡的不足，从而有效地解决临近Sink节点的“热区”问题。经仿真实验对比和理论分析可知，EOUCR与EEUC和LEACH协议相比能够更有效地节约节点能量、均衡全网能量消耗、延长网络寿命。最后指出了EOUCR协议的应用场景。关键词：无线传感器网络，分簇路由, LEACH，EEUC，网络生命周期AbstractIn recent years, the matur

5、ing and development of sensor technology, electronic technology and wireless communication technology have laid foundation for the rapid development of Wireless Sensor Networks (WSN), and WSN has gradually become a new research area of computer science and technology. Wireless sensor network has man

6、y advantages, such as low-cost, small volume, self-organization and wireless communications and so on. However, WSN also has its unignored shortcomings and the biggest weakness of WSN is that sensor nodes has limited resource and communication module is the major part of the energy consumption. Ther

7、efore, designing an efficient routing protocol becomes a key technology and an import issue in wireless sensor network research.In order to design efficient and reliable clustering routing protocols for wireless sensor network, the main research work is as follows: (1) This thesis introduces routing

8、 protocols and relevant background knowledge of WSN, and then analysis and illustrates the main ideas and research results of several classic flat routing and clustering routing protocols from the difference of network topology, and indicates the advantages of clustering routing protocol relative to

9、 the flat routing protocol.(2) A new even clustering routing algorithm based on improved LEACH is proposed in this thesis after researching on traditional and improved LEACH routing protocol. The algorithm uses a time-based cluster head selection mechanism which considers the nodes residual energy,

10、this mechanism not only reduces the possibility of low-energy node becoming cluster head, but also solves the problem of cluster heads generating randomness and uneven distribution. While building routing stage, the Ant Colony Optimization(ACO) algorithm is applied to inter-cluster routing mechanism

11、, the dynamic adaptability and optimization capabilities of the ant colony are utilized to transport data between nodes and Sink with multi-hop transmission, thus reducing energy consumption of nodes and extending life cycle of the network. The experimental simulation results shows that the proposed

12、 algorithm does better in generating cluster head, average energy consumption and the number of surviving nodes compared with LEACH algorithm.(3) An energy optimized uneven clustering routing protocol in Wireless Sensor Network (EOUCR) is given in this thesis after researching on EEUC protocol. Alth

13、ough even clustering routing algorithm can reduce network energy consumption by multi-hop transmission, it also brings hot spot problem, however, the clustering routing algorithm based on ant colony optimization just belongs to this algorithm. In order to solve the hot spot problem in multi-hop rout

14、ing protocol of wireless sensor network, EOUCR was proposed after researching on EEUC. In this routing protocol, three parameters, i.e., the candidate cluster heads residual energy, its neighbors average residual energy and the distance of the candidate cluster head to Sink, was considered in the cl

15、uster formation phase. Meanwhile, EOUCR partitions all nodes into clusters of unequal size, and takes energy consumption into account while calculating competitive radius. In this way, the cluster head rotation frequency can be reduced when cluster is in hot spot, and the network loading is balanced

16、. Furthermore, a unique root node is introduced, this root node communicates with the Sink node solely in clustering multi-hop routing, other cluster heads communicate with the root node through the relay node or directly. Thus, the “hot spot” problem near the Sink node can be solved effectively thr

17、ough EOUCR by overcoming EEUCs deficiency of larger and unbalanced energy consumption. Simulation results show that EOUCR can more efficiently save energy of nodes, balance the energy dissipation of all nodes, and prolong the network lifetime compared with EEUC and LEACH protocol. Finally, the EOUCR

18、s application of scene is indicated in this thesis.Keywords: wireless sensor networks, clustering routing, LEACH, EEUC, network lifetime目录摘要 IAbstract II目录 IV第一章 绪论 11.1 研究背景及意义 11.2 国内外的研究现状 11.3 本文的研究内容 21.4 本文的结构安排 3第二章 无线传感器网络概述 42.1 无线传感器网络体系结构 42.1.1 无线传感器网络结构 42.1.2 传感器节点结构 52.1.3 无线传感器网络协议栈结

19、构 62.2 无线传感器网络的特点 72.3 无线传感器网络的技术挑战 82.4 无线传感器网络的应用与发展领域 92.5 本章小结 10第三章 无线传感器网络路由协议的分析 113.1 无线传感器网络路由协议概述 113.2 无线传感器网络路由协议的特点和设计要求 113.2.1 路由协议的特点 113.2.2 路由协议的设计要求 113.3 现有的无线传感器网络路由协议分析 123.3.1 平面路由算法 123.3.2 分簇路由算法 143.4 分簇路由算法的优势分析 163.5 本章小结 17第四章 一种新的均匀分簇改进LEACH算法 184.1 蚁群算法分析 184.1.1 蚁群算法基

20、本原理 184.1.2 算法描述 184.1.3 蚁群算法在无线传感器网络中的应用 204.2 LEACH路由协议分析 214.2.1 LEACH算法描述 214.2.2 LEACH算法分析及缺陷 224.3 一种新的均匀分簇改进LEACH算法 224.3.1 网络模型与能量模型 224.3.2 簇的形成阶段 234.3.3 稳定的数据传输阶段 254.4 仿真结果与分析 264.4.1 仿真参数 264.4.2 仿真结果分析 264.5 本章小结 29第五章 一种能量优化的非均匀分簇路由算法(EOUCR) 305.1 引言 305.2 EEUC路由协议分析 305.3 EOUCR协议描述 3

21、15.3.1 网络模型与能量模型 325.3.2 簇形成阶段 335.3.3 簇间多跳路径的建立 355.3.4 稳定的数据传输阶段 365.4 协议分析与仿真 365.4.1 网络消息复杂度分析 365.4.2 仿真结果分析 375.5 EOUCR协议的应用场景 395.6 本章小结 39第六章 总结与展望 406.1 总结 406.2 展望 40致谢 42参考文献 43附录：作者在攻读硕士学位期间发表的论文 46第一章 绪论1.1 研究背景及意义19世纪末期，传感技术、无线通信技术和电子技术等技术的不断发展和日趋成熟，促进了集信息采集、信息处理和信息无线传输等功能于一体的无线传感器网络的迅

22、猛发展。无线传感器网络(Wireless Sensor Network，WSN) 1是由大量传感器节点组成的网络监控系统，它的目的是节点间相互协作地采集处理监控区域内的信息，并将它们发送给观察者2-4。无线传感器网络被认为是21世纪最具影响力的改变世界的十大技术之一。WSN中的节点的通常部署在高危或野外的环境区域中，且分布区域十分宽广，节点数量通常庞大，而自身所带电池能量是有限的，所以没有现实妥善的办法及时为传感器节点补充能量。因此WSN中节点能量受限是制约无线传感器网络设计、发展和应用的最棘手问题。目前解决无线传感器网络的能耗问题大体有两类办法：一是增大传感器节点的能量携带能力，二是降低全网

23、能耗。而采用增加节点自身携带能量的措施，必将带来整个网络成本高开销大的困扰，目前主要是通过高效利用节点能量、降低节点能量消耗来延长整个网络生存时间。作为WSN研究领域中的一项关键技术和重要课题，设计节能、良好的路由协议能够有效节省节点的能量，降低网络能耗，提升网络生存时间。所以对无线传感器网络中的路由协议展开研究很有必要，其价值和影响不言而喻。1.2 国内外的研究现状无线传感器网络因体积小、功耗低、自适应、自组织及多跳性等优势，被广泛地应用到人类社会生活的各个领域，具有极其强大的生命活力，无论它哪一方面的创新和发展，都将给人类的生活带来不可预知和想象的全新变化。正是由于WSN技术蕴藏的巨大商业

24、价值，世界各国为了促进各国经济等因素的发展，纷纷成立了WSN技术的相关研究项目，并取得了相当丰硕的研究成果5-8。国内WSN的研究稍微落后了一点，近几年才得到政府和商业人士的普遍关注和重视9，但在这方面投入力度大，大力推动了无线传感器网络的科研和实践。近些年在国家政府相关部门的支持和鼓励下，国家重点研究所和大学纷纷展开了对无线传感器网络相关技术的研究，并取得了很多初步的研究成果，但目前国内的研究缺乏创新性，因此国内对WSN领域的研究还需要一段时间的积累和努力。目前，关于分簇路由算法的研究仍十分热门。Heinzelman等人提出LEACH11(Low Energy Adaptive Cluste

25、ring Hierarchy)分簇路由协议，单个簇内含有一个簇头和多个簇内普通节点，簇头每轮都要进行更换，使每个节点成为簇头的概率完全相同，每个节点消耗的能量也大致相同，进而延长网络生命周期。Younis等提出了一种完全分布式的HEED12 协议，该算法根据节点的剩余能量选择一些候选簇头，并根据簇的通信代价(CAMP)来选择最终簇头。但该分簇算法在迭代过程的集簇范围内需要多个信息，并且通信消耗是极其显著的。在EECS13 分簇协议中，靠近Sink节点的簇头簇内普通成员节点数目较多，而远离Sink节点的簇头簇内普通成员节点数目较少，这样有益于平衡各簇头间能耗。但EECS协议的缺陷在于只能部分解决

26、簇头间能量不平衡问题，而不能从整体上实现全网节点的能量均衡。以上提到的路由协议都是簇头直接以单跳形式将信息传递给Sink节点的路由协议，但如果在大型网络中簇头采用同样的方式传输数据必将消耗大量能量，因为此时簇头一般离Sink节点较远，而就如后面章节介绍的一样，能量消耗与距离的大小是指数倍数比例的关系。因此，为了最大化网络生命周期，分簇和多跳的路由算法被大量提出。但是Sink节点附近的簇头由于要转发大量较远距离的簇收集来的消息，过早消耗了自身的能量，导致网络的能量不均衡，出现“热区”问题14。UCS15第一次指出使用非均匀分簇的思想来解决簇头节点能耗及全网负载不均衡问题，且簇间以多跳路由的方式传

27、输数据。但是它考虑的是一个异构网络，簇头为超级节点，而且位置是事先计算好的，不适合随机部署的网络。在文献16,17中李成法等人提出了EEUC 算法，该算法以非均匀的竞争半径作为成簇的关键和依据，使得靠近Sink节点的簇具有较少的簇内成员和较小的规模，以此来节约Sink节点附近的簇头能量并使之用于簇间传输信息，从而实现全网能耗均衡。但EEUC 算法并没有完全解决“热区”问题。文献18和文献19在EEUC 非均匀分簇结构的基础上，都采用了基于时间驱动的簇头选择机制，虽然都取得了一定的改进效果，但还是存在“热区”问题，致使网络负载不均衡。总之，为了高效利用节点的能量，提升网络生存时间，国内外研究学者

28、就分簇路由协议做出了很多的改进和研究工作，但从均衡全网能耗角度出发设计的分簇路由协议的仍处于探索和研究阶段，需要后继学者们做进一步的研究。1.3 本文的研究内容本文首先对无线传感器网络及其路由协议的相关知识进行了综合介绍及描述。然后，重点从网络节点地位不同的角度对无线传感器网络中几个代表性平面路由和分簇路由协议的工作原理和优缺点做了分析研究说明，同时指出了分簇路由协议相对于平面路由协议的几大优势，最后提出了一种新的均匀分簇改进LEACH算法和一种能量优化WSN非均匀分簇路由算法，其中前者属基于均匀分簇的，后者则是非均匀的分簇结构。本文具体的研究内容如下：1、对无线传感器网络及其路由协议的相关背

29、景知识进行了综合阐述。并按照网络拓扑结构分类说明了当前几种无线传感器网络路由协议的主要思想和研究成果，并着重分析了分簇路由协议的优势和几种代表性分簇路由协议的优缺点。2、提出了一种新的均匀分簇改进LEACH算法。针对LEACH协议产生簇头数目比较随机，且簇头直接与基站通信导致能量消耗过快的缺陷，在对LEACH及其改进路由协议分析研究以后，本文提出了一种簇头数目固定的基于时间的簇头选择机制，该机制将节点的剩余能量考虑进内，既解决了簇头分布不均匀的问题，又降低了具有较低能量的节点成为簇头的可能性。与此同时在路由建立的过程中，将蚁群优化算法应用于簇间路由机制中，使得全网在簇头与基站之间形成了一条最优

30、通信路径，从而进一步节约节点能量，降低网络能耗，延长网络生命周期。3、针对“热区”问题及 EEUC 算法的不足，提出了一种能量优化WSN非均匀分簇路由协议 EOUCR (Energy Optimized Unequal Clustering Routing Protocol)，该协议采用基于时间的簇头竞争算法，以候选簇头的剩余能量、其邻居节点的剩余能量和该候选簇头与Sink节点的距离作为竞选簇头的参数，且簇头的竞争半径考虑成簇的能量消耗，在此基础上形成了不同几何尺寸的簇，可减少“热区”内簇的簇头轮换次数，均衡网络负载。在簇间多跳路由通信中，本文将EEUC形成的拓扑结构重组，在簇头节点集合中选出

31、一个根节点，只有该根节点与 Sink节点通信，其他簇头则通过中继节点或直接与根节点通信，实现簇头间能耗负载均衡。因此，EOUCR协议的通信节点少、能耗小且负载均衡，从而更有效地解决“热区”问题。要完整文章毕业论文的+扣扣：（1499-0883-24）去掉中间的横线1.4 本文的结构安排本文章节安排如下：第一章首先对WSN相关背景知识做简单介绍，其次对WSN的研究意义和现状也进行了论述，最后阐述了本文的主要研究内容和本文组织结构。第二章研究了无线传感器网络，分析了包括网络系统结构、传感器节点结构和网络协议栈三个部分在内的传感器网络体系结构，随后对WSN独有的特点和技术挑战进行了阐述，并对WSN的

32、应用和发展趋势做了相应介绍。第三章首先对无线传感器路由协议做了简要概述，其次对WSN路由协议的特点和设计要求进行了阐述和分析，最后对WSN中几个经典的平面路由和分簇路由协议进行了性能和优缺点分析，并指出了分簇路由相对平面路由的极大优势。第四章提出了一种新的均匀分簇改进LEACH算法，介绍了基本蚁群算法的运行过程并分析了将它应用到 WSN 的优越性，同时对LEACH算法进行了详细介绍，在对LEACH算法的优缺点进行详细分析的基础上，对所提算法的设计思想和具体实现过程进行了详细的描述。最后通过实验仿真和性能分析，说明了所提算法在生成簇头数、平均能量消耗和节点存活数三个方面相对于LEACH算法的优越性。第五章针对无线传感器网络中多跳路由协议的“热区”问题和EEUC协议的不足，提出了一种能量优化的非均匀分簇路由算法(EOUCR)。首先简单介绍EEUC协议，其次分析EEUC协议优缺点，在此基础上，对提出的EOUCR协议具体实现过程进行了详细描述，从簇头产生过程、簇形成过程、路由发现和数据传输阶段几个方面详细的介绍了算法的具体