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

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

《无线传感器网络中分簇路由算法的研究.docx》由会员分享，可在线阅读，更多相关《无线传感器网络中分簇路由算法的研究.docx（18页珍藏版）》请在冰点文库上搜索。

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

摘要

近年来，传感器技术、电子技术和无线通信技术的日趋成熟和发展，为无线传感器网络（WirelessSensorNetwork,WSN）的快速发展奠定了基础，使得WSN已经逐步成为计算机科学技术中一个新的研究领域。

无线传感器网络具有成本低、体积小、自组织和无线通信等诸多优点，但WSN也有它不可忽视的缺点，其中一个最关键的就是资源受限，节点的计算能力、存储能力和能量都十分有限，而通信模块是能量消耗的主要部分，为了尽可能延长网络的生命周期，设计高效的路由协议成为当前WSN研究的一项关键技术，也是目前WSN领域研究的一个重要课题。

为了设计高效可靠的WSN分簇路由协议，本文的研究内容如下：

（1）介绍了无线传感器网络及路由协议的相关背景知识，并重点从网络拓扑结构的不同出发，分析说明了目前比较经典的几种平面路由协议和分簇路由协议的主要思想和研究成果，同时指出了分簇路由相对于平面路由协议的几大优势。

（2）在分析传统和改进LEACH路由协议之后，提出了一种新的均匀分簇改进LEACH算法。

该算法采用一种基于时间的簇头选择机制，该机制将节点的剩余能量考虑进内，不仅降低了低能量的节点成为簇头的可能性，且改善了簇头产生的随机性和分布的不均匀性；在路由建立阶段，利用蚁群的动态适应性和寻优能力将蚁群优化算法应用于簇间路由机制中，使数据以多跳形式传输给Sink节点，从而减小节点能量消耗进而提高网络寿命。

并通过实验仿真和性能分析，说明了所提算法在生成簇头数、平均能量消耗和节点存活数三个方面相对于LEACH算法的优越性。

（3）在对EEUC协议分析之后，提出了一种能量优化的WSN非均匀分簇路由协议（EOUCR）。

对于均匀分簇算法来说，虽然采用多跳路由可以从某种程度上降低网络能耗，但同时也带来了“热区”问题，基于蚁群优化的改进LEACH算法就属于此类算法。

针对“热区”问题及典型非均匀分簇路由EEUC算法的不足，本文提出了EOUCR协议，该协议在簇形成阶段以候选簇头的剩余能量、其邻居节点的平均剩余能量和该候选簇头与Sink节点的距离作为竞选簇头的参数，且簇头竞争半径的选取考虑了成簇能耗，在此基础上形成了不同几何尺寸的簇，可减少“热区”内簇的簇头轮换次数，均衡网络负载。

EOUCR在簇间多跳路由通信中引入了唯一与Sink节点通信的根节点，其他簇头则通过中继节点或直接与根节点通信，克服了EEUC能耗大且不均衡的不足，从而有效地解决临近Sink节点的“热区”问题。

经仿真实验对比和理论分析可知，EOUCR与EEUC和LEACH协议相比能够更有效地节约节点能量、均衡全网能量消耗、延长网络寿命。

最后指出了EOUCR协议的应用场景。

关键词：

无线传感器网络，分簇路由,LEACH，EEUC，网络生命周期

Abstract

Inrecentyears,thematuringanddevelopmentofsensortechnology,electronictechnologyandwirelesscommunicationtechnologyhavelaidfoundationfortherapiddevelopmentofWirelessSensorNetworks（WSN）,andWSNhasgraduallybecomeanewresearchareaofcomputerscienceandtechnology.Wirelesssensornetworkhasmanyadvantages,suchaslow-cost,smallvolume,self-organizationandwirelesscommunicationsandsoon.However,WSNalsohasitsunignoredshortcomingsandthebiggestweaknessofWSNisthatsensornodeshaslimitedresourceandcommunicationmoduleisthemajorpartoftheenergyconsumption.Therefore,designinganefficientroutingprotocolbecomesakeytechnologyandanimportissueinwirelesssensornetworkresearch.

Inordertodesignefficientandreliableclusteringroutingprotocolsforwirelesssensornetwork,themainresearchworkisasfollows:

（1）ThisthesisintroducesroutingprotocolsandrelevantbackgroundknowledgeofWSN,andthenanalysisandillustratesthemainideasandresearchresultsofseveralclassicflatroutingandclusteringroutingprotocolsfromthedifferenceofnetworktopology,andindicatestheadvantagesofclusteringroutingprotocolrelativetotheflatroutingprotocol.

（2）AnewevenclusteringroutingalgorithmbasedonimprovedLEACHisproposedinthisthesisafterresearchingontraditionalandimprovedLEACHroutingprotocol.Thealgorithmusesatime-basedclusterheadselectionmechanismwhichconsidersthenode’sresidualenergy,thismechanismnotonlyreducesthepossibilityoflow-energynodebecomingclusterhead,butalsosolvestheproblemofclusterheads’generatingrandomnessandunevendistribution.Whilebuildingroutingstage,theAntColonyOptimization（ACO）algorithmisappliedtointer-clusterroutingmechanism,thedynamicadaptabilityandoptimizationcapabilitiesoftheantcolonyareutilizedtotransportdatabetweennodesandSinkwithmulti-hoptransmission,thusreducingenergyconsumptionofnodesandextendinglifecycleofthenetwork.Theexperimentalsimulationresultsshowsthattheproposedalgorithmdoesbetteringeneratingclusterhead,averageenergyconsumptionandthenumberofsurvivingnodescomparedwithLEACHalgorithm.

（3）AnenergyoptimizedunevenclusteringroutingprotocolinWirelessSensorNetwork（EOUCR）isgiveninthisthesisafterresearchingonEEUCprotocol.Althoughevenclusteringroutingalgorithmcanreducenetworkenergyconsumptionbymulti-hoptransmission,italsobrings‘hotspot’problem,however,theclusteringroutingalgorithmbasedonantcolonyoptimizationjustbelongstothisalgorithm.Inordertosolvethe‘hotspot’probleminmulti-hoproutingprotocolofwirelesssensornetwork,EOUCRwasproposedafterresearchingonEEUC.Inthisroutingprotocol,threeparameters,i.e.,thecandidateclusterhead’sresidualenergy,itsneighbor’saverageresidualenergyandthedistanceofthecandidateclusterheadtoSink,wasconsideredintheclusterformationphase.Meanwhile,EOUCRpartitionsallnodesintoclustersofunequalsize,andtakesenergyconsumptionintoaccountwhilecalculatingcompetitiveradius.Inthisway,theclusterheadrotationfrequencycanbereducedwhenclusterisin"hotspot",andthenetworkloadingisbalanced.Furthermore,auniquerootnodeisintroduced,thisrootnodecommunicateswiththeSinknodesolelyinclusteringmulti-hoprouting,otherclusterheadscommunicatewiththerootnodethroughtherelaynodeordirectly.Thus,the“hotspot”problemneartheSinknodecanbesolvedeffectivelythroughEOUCRbyovercomingEEUC’sdeficiencyoflargerandunbalancedenergyconsumption.SimulationresultsshowthatEOUCRcanmoreefficientlysaveenergyofnodes,balancetheenergydissipationofallnodes,andprolongthenetworklifetimecomparedwithEEUCandLEACHprotocol.Finally,theEOUCR’sapplicationofsceneisindicatedinthisthesis.

Keywords:

wirelesssensornetworks,clusteringrouting,LEACH,EEUC,networklifetime

目录

摘要I

AbstractII

目录IV

第一章绪论1

1.1研究背景及意义1

1.2国内外的研究现状1

1.3本文的研究内容2

1.4本文的结构安排3

第二章无线传感器网络概述4

2.1无线传感器网络体系结构4

2.1.1无线传感器网络结构4

2.1.2传感器节点结构5

2.1.3无线传感器网络协议栈结构6

2.2无线传感器网络的特点7

2.3无线传感器网络的技术挑战8

2.4无线传感器网络的应用与发展领域9

2.5本章小结10

第三章无线传感器网络路由协议的分析11

3.1无线传感器网络路由协议概述11

3.2无线传感器网络路由协议的特点和设计要求11

3.2.1路由协议的特点11

3.2.2路由协议的设计要求11

3.3现有的无线传感器网络路由协议分析12

3.3.1平面路由算法12

3.3.2分簇路由算法14

3.4分簇路由算法的优势分析16

3.5本章小结17

第四章一种新的均匀分簇改进LEACH算法18

4.1蚁群算法分析18

4.1.1蚁群算法基本原理18

4.1.2算法描述18

4.1.3蚁群算法在无线传感器网络中的应用20

4.2LEACH路由协议分析21

4.2.1LEACH算法描述21

4.2.2LEACH算法分析及缺陷22

4.3一种新的均匀分簇改进LEACH算法22

4.3.1网络模型与能量模型22

4.3.2簇的形成阶段23

4.3.3稳定的数据传输阶段25

4.4仿真结果与分析26

4.4.1仿真参数26

4.4.2仿真结果分析26

4.5本章小结29

第五章一种能量优化的非均匀分簇路由算法（EOUCR）30

5.1引言30

5.2EEUC路由协议分析30

5.3EOUCR协议描述31

5.3.1网络模型与能量模型32

5.3.2簇形成阶段33

5.3.3簇间多跳路径的建立35

5.3.4稳定的数据传输阶段36

5.4协议分析与仿真36

5.4.1网络消息复杂度分析36

5.4.2仿真结果分析37

5.5EOUCR协议的应用场景39

5.6本章小结39

第六章总结与展望40

6.1总结40

6.2展望40

致谢42

参考文献43

附录：

作者在攻读硕士学位期间发表的论文46

第一章绪论

1.1研究背景及意义

19世纪末期，传感技术、无线通信技术和电子技术等技术的不断发展和日趋成熟，促进了集信息采集、信息处理和信息无线传输等功能于一体的无线传感器网络的迅猛发展。

无线传感器网络（WirelessSensorNetwork，WSN）[1]是由大量传感器节点组成的网络监控系统，它的目的是节点间相互协作地采集处理监控区域内的信息，并将它们发送给观察者[2-4]。

无线传感器网络被认为是21世纪最具影响力的改变世界的十大技术之一。

WSN中的节点的通常部署在高危或野外的环境区域中，且分布区域十分宽广，节点数量通常庞大，而自身所带电池能量是有限的，所以没有现实妥善的办法及时为传感器节点补充能量。

因此WSN中节点能量受限是制约无线传感器网络设计、发展和应用的最棘手问题。

目前解决无线传感器网络的能耗问题大体有两类办法：

一是增大传感器节点的能量携带能力，二是降低全网能耗。

而采用增加节点自身携带能量的措施，必将带来整个网络成本高开销大的困扰，目前主要是通过高效利用节点能量、降低节点能量消耗来延长整个网络生存时间。

作为WSN研究领域中的一项关键技术和重要课题，设计节能、良好的路由协议能够有效节省节点的能量，降低网络能耗，提升网络生存时间。

所以对无线传感器网络中的路由协议展开研究很有必要，其价值和影响不言而喻。

1.2国内外的研究现状

无线传感器网络因体积小、功耗低、自适应、自组织及多跳性等优势，被广泛地应用到人类社会生活的各个领域，具有极其强大的生命活力，无论它哪一方面的创新和发展，都将给人类的生活带来不可预知和想象的全新变化。

正是由于WSN技术蕴藏的巨大商业价值，世界各国为了促进各国经济等因素的发展，纷纷成立了WSN技术的相关研究项目，并取得了相当丰硕的研究成果[5-8]。

国内WSN的研究稍微落后了一点，近几年才得到政府和商业人士的普遍关注和重视[9]，但在这方面投入力度大，大力推动了无线传感器网络的科研和实践。

近些年在国家政府相关部门的支持和鼓励下，国家重点研究所和大学纷纷展开了对无线传感器网络相关技术的研究，并取得了很多初步的研究成果，但目前国内的研究缺乏创新性，因此国内对WSN领域的研究还需要一段时间的积累和努力。

目前，关于分簇路由算法的研究仍十分热门。

Heinzelman等人提出LEACH[11]（LowEnergyAdaptiveClusteringHierarchy）分簇路由协议，单个簇内含有一个簇头和多个簇内普通节点，簇头每轮都要进行更换，使每个节点成为簇头的概率完全相同，每个节点消耗的能量也大致相同，进而延长网络生命周期。

Younis等提出了一种完全分布式的HEED[12]协议，该算法根据节点的剩余能量选择一些候选簇头，并根据簇的通信代价（CAMP）来选择最终簇头。

但该分簇算法在迭代过程的集簇范围内需要多个信息，并且通信消耗是极其显著的。

在EECS[13]分簇协议中，靠近Sink节点的簇头簇内普通成员节点数目较多，而远离Sink节点的簇头簇内普通成员节点数目较少，这样有益于平衡各簇头间能耗。

但EECS协议的缺陷在于只能部分解决簇头间能量不平衡问题，而不能从整体上实现全网节点的能量均衡。

以上提到的路由协议都是簇头直接以单跳形式将信息传递给Sink节点的路由协议，但如果在大型网络中簇头采用同样的方式传输数据必将消耗大量能量，因为此时簇头一般离Sink节点较远，而就如后面章节介绍的一样，能量消耗与距离的大小是指数倍数比例的关系。

因此，为了最大化网络生命周期，分簇和多跳的路由算法被大量提出。

但是Sink节点附近的簇头由于要转发大量较远距离的簇收集来的消息，过早消耗了自身的能量，导致网络的能量不均衡，出现“热区”问题[14]。

UCS[15]第一次指出使用非均匀分簇的思想来解决簇头节点能耗及全网负载不均衡问题，且簇间以多跳路由的方式传输数据。

但是它考虑的是一个异构网络，簇头为超级节点，而且位置是事先计算好的，不适合随机部署的网络。

在文献[16,17]中李成法等人提出了EEUC算法，该算法以非均匀的竞争半径作为成簇的关键和依据，使得靠近Sink节点的簇具有较少的簇内成员和较小的规模，以此来节约Sink节点附近的簇头能量并使之用于簇间传输信息，从而实现全网能耗均衡。

但EEUC算法并没有完全解决“热区”问题。

文献[18]和文献[19]在EEUC非均匀分簇结构的基础上，都采用了基于时间驱动的簇头选择机制，虽然都取得了一定的改进效果，但还是存在“热区”问题，致使网络负载不均衡。

总之，为了高效利用节点的能量，提升网络生存时间，国内外研究学者就分簇路由协议做出了很多的改进和研究工作，但从均衡全网能耗角度出发设计的分簇路由协议的仍处于探索和研究阶段，需要后继学者们做进一步的研究。

1.3本文的研究内容

本文首先对无线传感器网络及其路由协议的相关知识进行了综合介绍及描述。

然后，重点从网络节点地位不同的角度对无线传感器网络中几个代表性平面路由和分簇路由协议的工作原理和优缺点做了分析研究说明，同时指出了分簇路由协议相对于平面路由协议的几大优势，最后提出了一种新的均匀分簇改进LEACH算法和一种能量优化WSN非均匀分簇路由算法，其中前者属基于均匀分簇的，后者则是非均匀的分簇结构。

本文具体的研究内容如下：

1、对无线传感器网络及其路由协议的相关背景知识进行了综合阐述。

并按照网络拓扑结构分类说明了当前几种无线传感器网络路由协议的主要思想和研究成果，并着重分析了分簇路由协议的优势和几种代表性分簇路由协议的优缺点。

2、提出了一种新的均匀分簇改进LEACH算法。

针对LEACH协议产生簇头数目比较随机，且簇头直接与基站通信导致能量消耗过快的缺陷，在对LEACH及其改进路由协议分析研究以后，本文提出了一种簇头数目固定的基于时间的簇头选择机制，该机制将节点的剩余能量考虑进内，既解决了簇头分布不均匀的问题，又降低了具有较低能量的节点成为簇头的可能性。

与此同时在路由建立的过程中，将蚁群优化算法应用于簇间路由机制中，使得全网在簇头与基站之间形成了一条最优通信路径，从而进一步节约节点能量，降低网络能耗，延长网络生命周期。

3、针对“热区”问题及EEUC算法的不足，提出了一种能量优化WSN非均匀分簇路由协议EOUCR（EnergyOptimizedUnequalClusteringRoutingProtocol），该协议采用基于时间的簇头竞争算法，以候选簇头的剩余能量、其邻居节点的剩余能量和该候选簇头与Sink节点的距离作为竞选簇头的参数，且簇头的竞争半径考虑成簇的能量消耗，在此基础上形成了不同几何尺寸的簇，可减少“热区”内簇的簇头轮换次数，均衡网络负载。

在簇间多跳路由通信中，本文将EEUC形成的拓扑结构重组，在簇头节点集合中选出一个根节点，只有该根节点与Sink节点通信，其他簇头则通过中继节点或直接与根节点通信，实现簇头间能耗负载均衡。

因此，EOUCR协议的通信节点少、能耗小且负载均衡，从而更有效地解决“热区”问题。

要完整文章毕业论文的+扣扣：

（1499-0883-24）去掉中间的横线

1.4本文的结构安排

本文章节安排如下：

第一章首先对WSN相关背景知识做简单介绍，其次对WSN的研究意义和现状也进行了论述，最后阐述了本文的主要研究内容和本文组织结构。

第二章研究了无线传感器网络，分析了包括网络系统结构、传感器节点结构和网络协议栈三个部分在内的传感器网络体系结构，随后对WSN独有的特点和技术挑战进行了阐述，并对WSN的应用和发展趋势做了相应介绍。

第三章首先对无线传感器路由协议做了简要概述，其次对WSN路由协议的特点和设计要求进行了阐述和分析，最后对WSN中几个经典的平面路由和分簇路由协议进行了性能和优缺点分析，并指出了分簇路由相对平面路由的极大优势。

第四章提出了一种新的均匀分簇改进LEACH算法，介绍了基本蚁群算法的运行过程并分析了将它应用到WSN的优越性，同时对LEACH算法进行了详细介绍，在对LEACH算法的优缺点进行详细分析的基础上，对所提算法的设计思想和具体实现过程进行了详细的描述。

最后通过实验仿真和性能分析，说明了所提算法在生成簇头数、平均能量消耗和节点存活数三个方面相对于LEACH算法的优越性。

第五章针对无线传感器网络中多跳路由协议的“热区”问题和EEUC协议的不足，提出了一种能量优化的非均匀分簇路由算法（EOUCR）。

首先简单介绍EEUC协议，其次分析EEUC协议优缺点，在此基础上，对提出的EOUCR协议具体实现过程进行了详细描述，从簇头产生过程、簇形成过程、路由发现和数据传输阶段几个方面详细的介绍了算法的具体