（电路与系统专业论文）一种基于蚁群算法的无线传感器网络分簇算法.pdf

dr口 iyiiiiiill75iiiillliiiiiillllll9lllll5llilll9llllll掣1 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他教育机 构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： i 臣盔r 期：型靠圣目爱旦 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保留并 向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借阅； 学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它复制 手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论文 注释：本学位论文不属于保密范围，适用本授权书。 本人签名： ! 醯盔 本人签名： ! 殴锺 导师签名：辱j 玺z 日期：卫蛸巨正堕 日期：掣掣p 耻，旦 ， #nrfe 0譬 o j 、 r ，含， i$。if；l唇，； 气 ， 一种 无线传感器网络是由大量具有无线通信和数据处理能力的传感 器节点通过特定协议构成的自组织网络。它作为一种新的信息获取方 式和处理模式，在环境监测、医疗监护、工业生产和军事侦查等领域 具有广阔的应用前景。伴随着“物联网 的兴起，无线传感器网络成 为当前研究的热点之一。 在无线传感器网络体系结构中，网络层的路由技术对无线传感器 网络性能的好坏有着重要影响。本文立意于无线传感器网络分簇路由 技术的研究。针对传统无线传感器网络分簇路由算法中网络节点的能 量消耗不均匀、簇头选择随机、簇结构不合理等问题，本文提出了基 于蚁群算法的无线传感器网络分簇路由算法：在簇头选择阶段，根据 节点的剩余能量与节点聚集度定义了节点能量信息素与距离信息素， 在此基础之上，利用蚁群算法对簇头进行选择；在簇形成阶段，定义 了成簇代价公式，节点依据与簇头之间成簇代价公式值的大小有选择 性地加入不同的网络簇，以此优化所形成的簇结构。仿真结果表明， 与传统的分簇路由算法相比，该算法不但能够有效地均衡网络节点的 能耗，而且能够显著地提高无线传感器网络的生命周期。 本文首先介绍了无线传感器网络的体系机构、特征及其应用；其 次对无线传感器网络分簇路由协议及其改进算法进行详细的叙述；之 后回顾了蚁群算法，阐述了它在无线传感网络路由协议中的应用；在 此基础之上，对本文的算法进行详细的说明，仿真结果表明本算法的 优越。 关键词：无线传感器网络；蚁群算法；路由协议；分簇算法 3 ，太 ，蔓 北京邮电大学研究生毕业论文 a na n tc o l o n y b a s e dc l u s t e r i n g a l g o r i t h mf o rw i r e l e s ss e n s o rn e t w o r k s a bs t r a c t w i r e l e s ss o n s o rn e t w o r ki ss e l f - o r g a n i z i n gn e t w o r k ，w h i c hi sm a d eu po f al a r g e o fn u m b e ro fs e n s o rn o d e sw i t hw i r e l e s sc o m m u n i c a t i o na n d d a t ap r o c e s s i n g c a p a b i l i t y i ts e r v e sa san e wi n f o r m a t i o na c q u i s i t i o nm o d ea n dp r o c e s s i n gm e t h o d ， a n dc a nb ea p p l i e dt om u l t i p l ea r e a ss u c ha se n v i r o n m e n t a lm o n i t o r i n g , m e d i c a lc a r e ， i n d u s t r i a lp r o d u c t i o na n dm i l i t a r yr e c o n n a i s s a n c e w i t ht h ed e v e l o p m e n to f i n t e m e t o ft 【l i n g s w i r e l e s ss e n s o rn e t w o r kb e c o m e so n eo f t h ef o c u s e so fc u r r e n tr e s e a r c h i nt h ew i r e l e s ss e n s o rn e t w o r ka r c h i t e c t u r e ，t h er o u t i n gt e c h n o l o g yo f t h en e t w o r k l a y e rh a sa ni m p o r t a n ti m p a c to nt h ep e r f o r m a n c ef o rt h ew i r e l e s ss e n s o rn e t w o r k t m st h e s i sf o c u s e s0 1 1t h er e s e a r c hi nd u s t e rr o u t i n gt e c h n o l o g yf o rw i r e l e s ss e n s o r n e t w o r k t os o l v ep r o b l e m ss u c ha st h eu n e v e ne n e r g yc o n s u m p t i o n o fs e n s o rn o d e s ， r a n d o mc l u s t e rh e a ds e l e c t i o na n di r r a t i o n a lc l u s t e rs t r u c t u r ei nt h et r a d i t i o n a lc l u s t e r i n g r o u t i n ga l g o r i t h m ，ac l u s t e r i n ga l g o r i t h mf o rw i r e l e s ss e n s o rn e t w o r kb a s e do na n t c o l o n ya l g o r i t h mi sp r o p o s e d i nt h ed u s t e rh e a ds e l e c t i o np h a s e ，t h ee n e r g ya n d d i s t a n c ep h e r o m o n e sb a s e do nt h er e s i d u a le n e r g ya n da g g r e g a t i o no f s e n s o rn o d e si s p r o v i d e d b a s e do nt h i s ，an e w c l u s t e rh e a ds e l e c t i o na l g o r i t h mi sp r o p o s e db a s e do n a n tc o l o n ya l g o r i t h m i nt h ec l u s t e rf o r m i n gp h a s e ，t h ec l u s t e rs t r u c t u r ei so p t i m i z e d a c c o r d i n gt ot h ed e f i n e dc o s tf o r m u l af o rc l u s t e r s 1 1 1 es e n s o rn o d e sj o i nt h ec l u s t e r h e a dt of o r mt h ed u s t e ra c c o r d i n gt ot h ev a l u eo fc o s tf o r m u l a s i m u l a t i o nr e s u l t s s h o wt h a tt h i sa l g o r i t h mc a ng e tab e t t e rb a l a n c eo ft h ee n e r g yc o n s u m p t i o na n dt h e n r e m a r k a b l yp r o l o n gt h el i f ec y c l eo f t h en e t w o r k i nt h i sp a p e r , t h ew i r e l e s ss e n s o rn e t w o r ka r c h i t e c t u r e , f e a t u r e a n dt h e i r a p p l i c a t i o na r ei n t r o d u c e d ；f o l l o w e db yc l u s t e r i n gr o u t i n gp r o t o c o lf o rw i r e l e s s s e n s o r n e t w o r ka n dt h ei m p r o v e da l g o r i t h mi sd e s c r i b e di nd e t a i l ；a f t e rt h er e v i e wo fa n t c o l o n ya l g o r i t h m ，t h ew i r e l e s ss e n s o rn e t w o r kr o u t i n gp r o t o c o lb a s e do na n tc o l o n y a l g o r i t h mi sp r e s e n t ；o nt h i sb a s i s ，t h ea l g o r i t h m i sf i n a l l ye l a b o r a t e da n dp r i o r i t y p e r f o r m a n c ei sp r o v e db ys i m u l a t i o n i l ， i i i 一；，；飞 ， 女0l-#i：zli941；l f， h，。- 哦 一种基丁蚁群算法 第一章引言 1 1研究的 1 2 研究的 1 2 1无线传感器网络路由协议2 1 2 2蚁群算法4 1 3本文的主要工作5 1 4本文的组织结构5 第二章无线传感器网络分簇路由协议7 2 1无线传感网络概述7 2 1 1无线传感器网络体系结构7 2 1 2无线传感器网络特征8 2 1 3无线传感器网络的应用9 2 2无线传感器网络路由协议概述9 2 3无线传感器网络分簇路由协议概述l o 2 4无线传感器网络分簇路由算法的性能评价标准1 1 2 5传统分簇算法l e a c h 协议研究1 2 2 6传统分簇算法l e a c h 协议的缺陷1 2 2 7传统分簇算法的改进算法分析研究1 3 2 7 1 簇头选择算法1 3 2 7 2 簇形成算法1 6 2 7 3 簇数据传输算法1 7 2 8本章小结1 8 第三章蚁群算法1 9 3 1蚁群算法概述1 9 3 1 1 蚁群算法基本原理1 9 3 1 - 2 基本蚁群算法的实现2 0 3 2蚁群算法应用于无线传感器网络路由协议的优势2 1 3 3蚁群算法在无线传感器网络路由协议中的应用2 2 3 3 1 蚁群算法应用于无线传感器网络平面路由2 2 3 3 2 蚁群算法应用于无线传感器网络分簇路由2 6 3 3 3 蚁群算法应用于无线传感器网络路由其他方面2 7 3 3 4 基于蚁群算法的路由协议比较分析2 7 3 4本章小结2 8 第四章基于蚁群的无线传感器网络分簇算法2 9 4 1蚁群分簇算法设计思想2 9 4 2蚁群分簇算法( b a c c a ) 相关的概念2 9 4 2 1 成簇代价公式2 9 4 2 2距离信息素3 0 4 2 3能量信息素3 1 4 2 4 簇头选择公式3 1 i v 生毕业论文 v 弛弘踮盯卯盯盯鹪如虬拍们钉铝砣鼹 气 北京邮电人学研究生毕业论文 1 1 研究的背景 第一章引言 在当今信息技术飞速发展的时代，微电子技术、计算机技术和无线通信等技 术的进步，推动了低功耗多功能传感器的快速发展。无线传感器网络i l l ( w i r e l e s s s e n s o rn e t w o r k , w s n ) 就是由部署在监测区域内大量的廉价微型传感器节点组 成，通过无线通信方式形成的一个多跳的自组织的网络系统，其目的是协作地感 知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。人们可以通 过传感器网络直接感知客观世界，从而极大地扩展现有网络的能力和人类认识世 界的能力。 无线传感器网络最早来源于军事领域。1 9 7 8 年，美国国防高级研究项目署 ( d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y , d a r p a 2 ) 的一个研究项目。当时为 了监测敌方潜艇的活动情况，需要在海洋中布置大量的传感器，使用这些传感器 所监测的信息来实时监测海水中潜艇的行动。但是由于当时技术条件的限制，使 得无线传感器网络的应用只能局限与军方的一些项目中，难以得到推广和发展。 近年来随着无线通信、微处理器等技术的发展，使得传感器网络的理想蓝图 能够得以实现，1 9 9 9 年在美国的移动计算和网络国际会议上，提出了无线传感 器网络是下一个世纪面临的发展机遇。2 0 0 3 年，美国技术评论杂志论述未 来新兴十大技术时，无线传感器网络被列为第一项未来新兴技术。同年，美国商 业周于i j 未来技术专版论述四大新技术时，无线传感器网络也列入其中。美国今 日防务杂志更认为无线传感器网络的应用和发展，将引起一场划时代的军事技 术革命和未来战争的变革。2 0 0 4 年( ( i e e es p e c t r u m ) ) 杂志发表一期专集传感 器的国度，论述无线传感器网络的发展和可能的广泛应用。而今年来比较大的 研究项目有：加州大学洛杉矶分校的w i n s 网络【3 】，它包含了网络协议研究的各 个方面；麻省理工学院的l a m p s 项目【4 】，它利用节点分簇算法来尽量降低能耗； 还有其它的研究项目如p i c o r a d i o 5 j 等。 我国现代意义的无线传感器网络及其应用研究几乎与发达国家同步启动，首 次正式出现与1 9 9 9 年中国科学院知识创新工程试点领域方向研究的“信息 与自动化领域研究报告中，作为该领域提出的五大重大项目之一。2 0 0 1 成立 了微系统研究与发展中心。近年来，在中国国家自然科学基金、国家“8 6 3 计 划基金的支持下，清华大学、北京邮电大学、中国科学技术大学、哈尔滨工业大 学等院校相继开展了无线传感器网络的研究，并陆续有许多院校和科研机构加入 l 理中心的数据采集，路由协议面向多对一的数据流和一对多的控制流，而非任意 源和目的地之间的数据传输；节点自身的能量有限；原始监测数据中有大量冗余 信息，路由协议需要合并数据，减少冗余性；虽然节点的移动性较低，但是网络 拓扑却表现出很强的时变性，因而，传统有线网络的路由协议很难适应这种高拓 扑变化。 我们需要针对无线传感器网络这些特点设计与其相适应的路由协议。设计路 由协议时需要满足以下条件【1 1 ： ( 1 ) 能量高效：路由时要选择能量消耗小的路径，并且要均衡网络的能耗，提 高网络的生存周期； ( 2 ) 鲁棒性：无线传感器网络的不可靠特性，如能量耗尽、环境变化对通信信 道造成影响，此时需要路由协议具有很强的容错能力； ( 3 ) 可扩展性：由于无线传感器网络的拓扑结构容易变化，所以要求路由协议 需要适应网络拓扑结构的变化； ( 4 ) 快速收敛：传感器网络的拓扑结构动态变化，节点能量和通信带宽等资源 2 一 r 毒 北京邮电人学研究生毕业论文 有限，因此要求路由机制能够快速收敛，以适应网络拓扑的变化。 针对传感器网络路由协议这些要求，许多路由协议被提了出来。从网络拓扑 结构的角度我们可以大体把它们分为两类：平面路由协议和分簇路由协议。 在平面路由协议中，所有网络节点的地位是平等的，节点通过相互之间的局 部操作和信息反馈来生成从源节点到目的节点的路由。经典的平面路由协议有定 向扩散【7 】( d i r e c t e dd i f f u s i o n ，d d ) 、s a r 【8 1 ( s e q u e n t i a la s s i g n m e n tr o u t i n g ) 、 s p i n 9 l ( s e n s o rp r o t o c o l sf o ri n f o r m a t i o nv i an e g o t i a t i o n ) 、r o m o rr o u t i n g 1 0 】等，平面 路由的优点是简单，无须进行过多的结构维护工作，而且不易产生瓶颈效应，因 此具有较好的鲁棒性。但是，平面路由存在很多缺点：其网络可扩展性差；由于 网络中没有管理节点，因而缺乏对通信资源的优化管理；对网络拓扑动态变化的 反应速度较慢等。 而在分簇路由协议中，网络被划分为多个簇( c l u s t e r ) ，这里的簇指的是有某 种公共特性的节点集合。簇由一个簇头( c l u s t e rh e a d ) 与多个簇内成员节点 ( c l u s t e rm e m b e r ) 组成。簇头用于控制与管理簇内成员节点，负责簇内信息的收 集、对这些数据进行融合处理以及簇之间的数据传输。典型的分簇路由协议，如 l e a c h 1 1 】等。由于分簇路由这些特点，它有效克服了平面路由的缺点，其具有 减少网络中数据通信量、减少网络中路由控制信息、利于分布式计算、对网络拓 扑变化快速反应的优点。它成为路由协议研究的重点，很多学者也从不同方面对 分簇路由协议进行改进，改进的方向可以归纳为三个方面：簇头选择算法；簇形 成算法：簇数据传输算法。 在簇头选择算法方面：簇头产生算法分为分布式和集中式两种：分布式指的 是节点根据某个阈值自主决定是否当选簇头；集中式指的是由基站基于网络信息 选择簇头。对于集中式簇头选择，它成簇的开销较大，而且限制了网络的扩展性， 分布式算法则有较好的扩展性、较好的收敛性以及能量高效。很多学者引入其它 的算法来选择簇头，如神经网络、模糊算法、博弈论等。此外，也有通过自定义 簇头选择函数的方法选择簇头。在这些簇头选择算法中，能量不是唯一考虑的因 素，同时还要考虑节点的位置、到基站的距离、计算能力以及簇内通信代价等因 素。仿真结果表明，通过其它算法的引入以及同时考虑多个因素，可以有效地选 择簇头，并能显著地延长网络的生存周期。 在簇形成算法方面：传统分簇算法的成簇方法是，节点依据接收到的簇头广 播信号的强弱决定加入哪个簇。这个机制比较简单，但是没有考虑节点的能量、 数量以及负载均衡，此外，还有簇形成时的控制报文开销。如何结合节点之间的 信息反馈以及传感器网络的分布式特点建立结构更加合理的簇，成为目前研究的 一个方向。 3 卜 北京邮电大学研究生毕业论文 在簇数据传输算法方面：很多学者也对其做了改进，如把分簇算法与平面路 由协议相结合、簇内或簇间的数据传输方式从单跳改为多跳、构建多级网络簇结 构，这些算法都取得了很好的成果，有效地延长了网络的生存周期。 另外，s h u g u a n gc u i 1 2 首次把m i m o 技术应用于无线传感器网络中，利用簇 结构实现虚m i m o 1 3 】技术，这种特定的“簇”称为“超级节点 ，簇头节点成为 超级节点的中心，簇内成员节点组成超级节点的“天线”，通过簇内节点相互协 作构成虚拟的天线阵列进行数据收发。组成簇的基本条件是簇内的通信距离远远 小于簇间的通信距离，超级节点与虚天线之间的通信称为“簇内通信”，超级节 点之间的通信称为“簇间通信”。算法的优势在于：在相同误码率要求下多天线 节点传输单位比特的总耗能优于单入单出模型( s i s o ) ，降低了网络的能耗，有效 地延长了网络的生存周期。在此基础之上，很多学者对此算法进行了改进，如通 过把簇内以及簇间的通信方式由单跳改为多跳等。 综上所述，通过把其它算法引入到分簇路由协议的三个阶段，有效地提高了 无线传感器网络分簇路由协议的性能，由此使无线传感器网络分簇路由协议成为 学术研究的重点与热点。 1 2 2蚁群算法 近年来，群智能l l4 1 ( s w a r mi n t e l l i g e n c e ，s 1 ) 是人工智能研究的一个热点课题， 它是基于群居性生物的觅食、筑巢等行为而设计的启发式优化算法，由于它提供 了解决传统优化问题的新方法，因而吸引了大量科研人员的目光。目前，群智能 理论研究领域有两种主要的算法：蚁群算法【1 5 i ( a c o - a n tc o l o n yo p t i m i z a t i o n ) 和 微粒群算法d 6 ( p s o p a r t i c l es w a r mo p t i m i z a t i o n ) 。蚁群算法通过对蚂蚁群体觅食 过程的模拟，已成功应用于诸多的离散优化问题。同样，微粒群算法通过对鸟群 觅食过程的模拟也是一种很好的优化工具。事实上，群智能方法能够被用于解决 大多数优化问题或者能够转化为优化求解的问题，其广泛应用于车间作业调度、 网络路由、机器人控制、电力系统、故障诊断、系统辨识、数据挖掘、图像处理、 化学工业等领域。 其中，蚁群算法是一种模拟蚂蚁群体智能行为的仿生优化算法，它作为通用 型随机优化方法，吸收了昆虫王国中蚂蚁的行为特性，通过其内在的搜索机制， 在一系列困难的组合优化问题求解中取得了成效。据昆虫学家的观察和研究，发 现生物世界中的蚂蚁有能力在没有任何可见提示下找出从其窝巢至食物源的最 短路径，并且能随环境的变化而变化，适应性地搜索新的路径。蚂蚁在寻找食物 源时，能在其走过的路径上释放一种蚂蚁特有的分泌物一信息素( p h e r o m o n e ) ， 使得一定范围内的其它蚂蚁能够察觉到并由此影响它们以后的行为。当一些路径 4 北京邮电大学研究生毕业论文 上通过的蚂蚁越来越多时，其留下的信息素轨迹( t r a i l ) 也越来越多，以致信息素 强度增大，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强 度，由此实现了一种正反馈机制。最优路径上的激素浓度越来越大，而其它的路 径上激素浓度却会随着时间的流逝而消减，最终整个蚁群会找出最优路径。不仅 如此，蚂蚁还能够适应环境的变化，当蚁群运动路线上突然出现障碍物时，蚂蚁 能够很快地重新找到最优路径，这个过程和前面所描述的过程是一致的。在整个 寻路过程中，虽然单个蚂蚁的选择能力有限，但是通过激素的作用以及整个蚁群 之间路径信息的交换，最终找出最优路径。 由于蚁群算法具有较强的鲁棒性、优良的分布式计算机制、易于与其他方法 相结合等优点，它已被应用到多个领域，由解决一维静态优化问题发展到解决多 维动态组合问题。该算法在车间作业调度问题、网络路由问题、车辆路径问题、 机器人领域、电力系统、故障诊断等若干领域内有典型的应用。此外，该算法已 初步应用于无线传感器网络路由协议的优化中，其在路由最优路径的选取、减少 数据的时延、提高路由的q o s 以及拥塞避免等方面有很好的应用，并取得了很 好理论研究成果。 1 3 本文的主要工作 本文对于无线传感器网络分簇路由协议、蚁群算法在无线传感器网络路由协 议的应用进行了分析研究工作，包括以下几个方面： ( 1 ) 搜集和阅读有关无线传感器网络、短距离无线通信协议等的资料文献，熟 悉无线传感器网络的基础理论以及无线通信基础知识； ( 2 ) 分析研究无线传感器网络的网络层特点以及现有的无线传感器网络路由 协议，将它们分类并进行研究分析，找到各类路由协议的优势以及它们存 在的问题，其中重点研究无线传感器网络分簇路由协议； ( 3 ) 在对蚁群算法、基于蚁群算法的无线传感器网络路由协议深入学习、研究 比较的基础上，将其应用于无线传感器网络分簇算法的设计当中，提出基 于蚁群算法的无线传感器网络分簇算法； ( 4 ) 对该分簇路由算法进行仿真，然后对仿真数据进行分析研究，同时对算法 的性能与其它算法进行比较评价。 1 4 本文的组织结构 第一章，介绍了论文课题的背景，阐述了无线传感器网络路由协议、蚁群算 法的研究现状，描述了论文的主要工作。 5 6 领域进 了传统 算法做 了蚁群 群算法 汲取它 真结果 传感器节点随机部署在监测区域( s e n s o rf i d d ) p 勺部或附近，能够通过自组织方式 构成网络。通过多跳中继方式将监测数据传送到汇聚节点，最后通过因特网或卫 星传送至管理节点和用户。同样的，用户可以通过管理节点对传感器网络进行配 置和管理，发布监测任务以及收集监测数据【1 1 。 管 传感器节点 图2 - 1 无线传感器网络体系结构 传感器节点由传感器模块、处理模块、无线通信模块和能量供应模块四部分 组成，如图( 2 2 ) 所示。 传感器模块处理器模块无线通信模块 处理器 阡丽 m c u 物理层 i s e n s o r a c d c 网络层 m a c r a d i o f 存储器i im e m o r yi 千 千 1 i 能量供应模块( 电池) 机播撒大量传感器节点到广阔的森林中，或放置到人不可到达或危险的区域。这 样要求传感器节点具有自组织的能力，能够自动进行配置和管理，通过拓扑控制 机制和网络协议自动形成转发监测数据的多跳无线网络系统。 2 1 2 3动态性的网络 传感器网络的拓扑结构可能因为下列因素而改变：环境因素或电能耗尽造成 的传感器节点出现故障或失效；环境条件变化可能造成无线通信链路带宽变化， 甚至时断时通；新节点的加入等。这要求传感器网络系统能够适应这种变化，具 有动态的系统可重构性。 2 1 2 4以数据为中心的网络 传感器网络中的节点采用节点编号标识，节点编号是否全网唯一取决于网络 通信协议的设计。由于传感器节点随机部署，构成的传感器网络与节点编号之间 的关系是完全动态的，表现为节点编号与节点位置没有必然的联系。用户使用传 感器网络查询事件时，直接将所关心的事件通告给网络，而不是通告给某个确定 编号的节点，网络在获得指定事件的信息后直接汇报给用户。所以通常说传感器 网络是一个以数据为中心的网络。 8 北京邮电大学研究生毕业论文 2 1 3无线传感器网络的应用 无线传感器网络在军事应用、环境监测、武器装备、工农业生产、日常生活 等领域具有非常广阔的应用前景【l 】。 2 1 3 1 军事应用 传感器网络具有可快速部署、可自组织、隐蔽性强和高容错性的特点，因此 非常适合在军事上应用。利用传感器网络能够实现对敌方兵力和装备的监控、战 场的实时监视、目标的定位、战场评估、核攻击和生物化学攻击的监测与搜索等 功能。 2 1 3 2 环境监测和预报系统 基于传感器网络的a l e r t 系统中就有利用传感器用来监测降雨量、河水水 位和土壤水分，并依次预测爆发山洪的可能性。类似地，传感器网络可实现对森 林环境监测和火灾报告，传感器节点被随机密布在森林中，平常状态下定期报告 森林环境数据，当发生火灾时，这些传感器节点通过协同合作会在很短的时间内 将火源的具体地点、火势的大小等信息传送至相关部门。 2 1 3 3 医疗监护 传感器网络在医疗系统和健康护理方面的应用包括监测人体的各种生理数 据，跟踪和监控医院内医生和患者的行动，医院的药物管理等。如果在住院病人 身上安装特殊用途的传感器节点，如心率和血压监测设备，医生利用传感器网络 就可以随时了解被监护病人的病情，发现异常能够迅速抢救。 2 1 3 4 其他方面的应用 传感器网络可以应用于空间搜索、智能家居等领域。在家电和家具中嵌入传 感器节点，通过无线网络与i n t e r n e t 连接在一起，将会为人们提供更加舒适、方 便和更具人性化的智能家居环境。利用远程监控系统，可完成对家电的远程监控， 例如可以在回家前半小时打开空调，这样回家的时候就可以直接享受适合的室温 等等。 2 2 无线传感器网络路由协议概述 无线传感器网络路由协议的任务是在传感器节点和基站之间建立路由，可靠 地传输数据。由于传感器网络的特殊性，需要针对不同的传感器网络应用，设计 不同的路由协议。从网络拓扑角度，我们可以把它们分为两大类：平面路由协议 与分簇路由协议。 9 北京邮电大学研究生毕业论文 在平面路由协议中，传感器节点将收集到的数据传送到汇聚节点，所有的节 点具有相同的地位和功能，节点之间相互协作完成感知和数据处理任务。典型的 平面路由协议有d d 7 、s a r 8 、s p i n 9 、r o m o rr o u t i n g 1 0 等。d d 是一种基 于查询的路由机制，汇聚节点周期性的向邻居节点广播兴趣消息，这个兴趣消息 包含属性列表、上报时间、地理位置等信息，沿途的节点按需对各兴趣消息进行 缓存和合并，并依据兴趣消息计算、创建包含数据上传率、下一跳信息的梯度 ( g r a d i e n t ) ，从而建立多条指向汇聚节点的路径。兴趣区域中地理区域内节点按 要求启动监测任务，并周期性的上报数据，途中各节点可对数据进行缓冲与聚合。 汇聚节点可在数据传输过程中通过对某条路径发送上报间隔更小或更大的兴趣 消息，以增强或减弱数据上报率，由此来加强和减弱路径。平面路由协议易于实 现，但是需要维护路由的开销大，可扩展性差，只适用于小规模的网络。而随着 网络规模的扩大，单层网络中传感器节点的密度增大，导致汇聚节点负载过重； 而且，由于传感器节点能量受限，不适宜长距离通信，只能通过多跳的方式到达 汇聚节点，由此耗费网络的能量。为了解决上述问题，很多路由协议的设计使用 了分簇的思想，由此引入了分簇路由。 2 3 无线传感器网络分簇路由协议概述 在无线传感器网络分艨路由协议中，网络通常被划分为若干个簇。每个簇由 一个簇头和多个簇内成员组成，由簇头与s i n k 节点( 基站) 通信。在每个簇内，簇 的节点。通过这种方式可以控制节点的接入请求，合理的分配带宽，并且可以减 少共享相同信道的节点数目，从而降低碰撞概率，同时簇头管理或控制整个簇内 成员节点，协调成员节点之间通信，负责簇内信息的收集和数据的融合处理以及 簇间数据的转发( 如图2 3 ) 。 转点 点 - 、 、。 图2 - 3 无线传感器网络分簇路由体系结构 分簇路由协议可以大大减少路由开销，克服了平面路由协议可扩展性差的缺 点，它还具有以下优点： 1 0 北京邮电大学研究生毕业论文 1 ) 成员节点大部分时间可以关闭通信模块，由簇头构成一个更上一层的连 通网络来负责数据的长距离路由转发，这样既保证了原有覆盖范围内的 数据通信，也在很大程度上节省了网络能量。 2 ) 簇头融合了成员节点的数据之后再进行转发，减少了数据通信量；成员 节点的功能比较简单，无须维护复杂的路由信息，大大减少了网络中路 由控制信息的数量。 3 ) 分簇拓扑结构便于管理，有利于分布式算法的应用，可以对系统变化做 出快速反应。 4 ) 从实施资源管理和提供服务质量保障的角度出发，分簇路由较平面路由 也具有较大的优势，更容易克服传感器节点移动带来的问题。 当然，分簇结构也存在缺点，例如，维护分簇结构需要节点执行复杂的簇头 选择算法，簇头节点可能会成为网络的瓶颈，而且簇间信息通过簇头路由，未必 是最佳路由。当然，可以通过设计合理的分簇算法来减少维护簇结构所需开销。 因此，无线传感器网络分簇路由协议在提高网络的整体性能、保障网络可靠 性、节约能量、控制拥塞和提供q o s 路由等各个方面有广泛的应用前景，设计 性能良好的分簇路由协议已成为无线传感器网络研究的重要内容和热点问题。 2 4 无线传感器网络分簇路由算法的性能评价标准 在无线传感器网络分簇算法中，建立合理和有效的网络分簇结构、维持网络 拓扑的相对稳定性、提高系统性能成为分簇算法的首要目标。在比较各种分簇算 法的性能时，主要采用以下几种性能指标【1 9 1 ： ( 1 ) 网络中簇头数目c ，它直接反映分簇网络的结构和特性。分簇算法中的 簇数目不能过多，也不能过少，应以满足系统要求和减少控制开销为准 则。 ( 2 ) 单位时间内簇头构成的簇更新的次数，也就是簇重构的频率。重新分簇 会导致较大的通信开销，该指标在很大程度上决定了分簇算法的性能。 ( 3 ) 簇重叠度，簇头处理负载的能力取决于它可以支持的节点数量。除了为 簇内节点分配资源外，簇头还需要维护簇间的路由，因此希望网络的负 载能够比较均匀地分配到各个簇，从而提高网络的整体性能。簇覆盖内 所有节点的数目之和与网络节点总数的比值作为网络的簇重叠度 vr c d = 譬，显然c d 越大，则处于重叠区域的节点数量越多。 n ( 4 ) 网络负载平衡因子：簇头的处理负载近似由该簇的大小表示，即簇 的大小的变化可以反映簇头负载分布。l b f 定义为簇内成员数( 不包括簇 1 1 北京邮电人学研究生毕业论文 头) 方差的倒数，即l b f =其中是簇的数量，坼是簇i 的成员节点数。材：翌二生表示网络中每个簇头的平均邻居节点数，表 他 示网络中所有节点的数目。显而易见，l b f 越大，网络的负载平衡程度 越好。 5传统分簇算法l e a c h 协议研究 无线传感器网络传统分簇算法l e a c h 主要包括簇头选择、簇形成与簇数据 传输三个阶段。算法的基本思想是：通过等概率地随机循环选择簇头，将整个网 络的能量负载平均分配到每个传感器节点，从而达到降低网络能量消耗、延长网 络生命周期的目的。l e a c h 的执行过程是周期性的，每轮循环的基本过程是： 在簇头选择阶段，每个节点选取个介于0 和l 之间的随机数，如果这个数小于 某个阈值删( 公式2 1 ) ，该节点成为簇头；在簇形成阶段，簇头向所有节点广 播自己成为簇头的消息。每个节点根据接收到广播信号的强弱来决定加入哪个 簇，并回复该簇簇头；在数据传输阶段，簇内的所有节点按照t d m a 时隙向簇 头发送数据，簇头将数据融合之后把结果发给基站，在持续工作一段时间之后， 网络重新进入启动阶段，进行下一轮的簇头选取并重新建立簇。 f 产1 甩g t ( n ) = l p lr m o d 亡l 式( 2 1 ) 【 l 0。砌西e 其中：p 是簇头占所有节点的百分比，即节点当选簇头的概率；，是目前循环 进行的轮数；g 是最近1 俨轮中还未当选过簇头的节点集合。从矸砂我们可以看 出，当选过簇头的节点在接下来的l 俨轮循环中将不能成为簇头，剩余节点当 选簇头的阈值删增大，节点产生小于删的随机数的概率随之增大，所以节点 当选簇头的概率增大。 2 6 传统分簇算法l e a c h 协议的缺陷 分析上述的l e a c h 协议，我们不难发现簇头是周期性按轮随机选举的，这 保证了网络各节点有平等的机会成为簇头，平衡了节点的能耗。但这是一个理想 化的结果，必须满足两个前提条件： a ) 每个节点初始能量均等。 b ) 每个节点在担任簇头期间消耗的能量均等。 1 2 j。j。j j。|，。in孙p j n 。秘 广 北京邮电大学研究生毕业论文 实际上，由于每个簇的大小以及簇头到基站的距离都不一样。条件( b ) 很 难达到，这就使得有些节点的能量消耗较快，有些节点的能量消耗较慢，经过一 段时间后，有些节点能量较少但却被选举为簇头，这就加速了节点的死亡，大大 减少了网络生存周期。 其次，簇头的分布由于完全依赖于随机数，容易产生簇头在某一区域特别集 中，某一区域又特别稀疏。簇头集中区域每个簇头分配的普通节点很少，失去了 分层路由的意义，簇头稀疏区域的簇头负责过多节点的数据，且节点离簇头距离 较远，传输信号能量消耗过大，而在网络规模较大时簇头之间必须采用多跳方式 将数据传送到基站，这就使得靠近基站的簇头因为承担了更多的转发任务，能量 消耗较快，影响了网络的生存周期。 2 7 传统分簇算法的改进算法分析研究 针对上述传统分簇算法l e a c h 协议的不足，众多学者对其做了改进，改进 的方向可以归纳为三个方面：簇头选择算法；簇形成算法；簇数据传输算法。改 进之后的算法有效地延长了网络的生存周期。 2 7 1 簇头选择算法 簇头的产生是簇形成的基础，分簇路由算法的第一步就是考虑怎样产生簇 头。根据簇头产生方式的不同，可以把簇头选择算法分为分布式和集中式两种。 分布式算法包括两类：一类是由节点根据某个阈值自主决定是否当选簇头，如 l e a c h ；另一类是通过节点之间的信息交互动态产生簇头，如h e e d 2 0 1 。集中 式算法是指由基站基于整个网络信息挑选簇头，如l e a c h c t 2 。目前的簇头选 择算法大多数基于以下准则：( 1 ) 节点的剩余能量；( 2 ) 簇头到基站的距离；( 3 ) 簇 头的位置；( 4 ) 簇内的通信代价，同时通过其它算法的引入，如神经网络、博弈 论、模糊算法，还有自定义簇头选择公式的方法，都能够有效地选择簇头，下面 详细阐述几种簇头选择算法，并且对算法进行研究，分析它们的优缺点。 2 7 1 1 t ( n ) 阈值修正 h a n d ym j 等人提出的d c h s 2 2 ( d e t e r m i n i s t i cc l u s t e r - h e a ds e l e c t