（信息与通信工程专业论文）基于能量策略的无线传感器网络路由算法.pdf

摘要 摘要 无线传感器网络是一种新兴的信息获取和处理技术，具有广泛的应用前景。 通常，无线传感器网络由大量低成本、低功耗，具备感知、数据处理、存储和无 线通信能力的微型传感器节点通过自组织方式形成的网络。无线传感器节点作为 微小器件，通常只能配备电池供电。这使得传感器节点的寿命在很大程度上依赖 于电池的寿命，所以如何降低节点能量消耗，延长网络生命周期是无线传感器网 络设计所要考虑的重要问题。本文主要针对无线传感器网络中的节点成簇算法和 能量有效路由两个方面进行了深入研究。主要研究内容和成果如下： ( 1 ) 提出了两种层次型结构的成簇选择算法，集中式成簇选择算法和分布式 成簇选择算法。在集中式成簇选择算法中，提出了节点逻辑标识符的概念。通过 s i n k 节点的参与管理，传感器节点获得各自的逻辑标识符、簇头位置以及成簇半 径大小等信息，之后通过节点间消息的交互完成簇的组织建立。在分布式成簇选 择算法中，节点的剩余能量和节点周围未成簇节点数目将会影响到各自竞争成为 簇头的权利。具有较多剩余能量和未成簇邻居数目的节点可优先竞争簇头，组织 成簇。这种综合考虑了节点能量和网络连通性的竞争策略可以在满足网络覆盖度 的情况下，能够有效的减少网络中成簇的数量。 ( 2 ) 以本文的两种成簇选择算法为基础，采用簇头节点多跳通信的方式，提 出了种基于能量策略的无线传感器网络路由算法( e n e r g yb a s e do nr o u t 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 ，e b r a ) ，实现从路由建立、数据传输到路 由维护的整个过程。当簇头节点有数据需要向s i n k 节点发送时，节点根据路由表， 选择通信能量消耗最小的路由节点进行数据传送。同时，算法中给出了一种改进 的请求响应型的数据传输模式，通过增加数据连续发送标识位，增强了数据传输 性能和对突发数据的响应能力。 ( 3 ) 针对网络仿真工具n s 2 ( 2 2 8 ) ，分别实现了基于两种成簇算法的路由协 议仿真程序。在不同的测试场景中对路由协议进行仿真实验，并和l e a c h 协议的 仿真结果进行对比分析。仿真验证了本文提出的路由算法能够有效的节省网络能 量消耗，延长网络生命周期，提高了网络吞吐能力，具有较好的数据传输性能。 关键字：无线传感器网络，路由协议，成簇算法，逻辑标识符，e b r a a b s t r a c t a bs t r a c t w i r e l e s ss e n s o rn e t w o r k ( w s n ) i san o v e lt e c h n o l o g ya b o u ta c q u i r i n ga n d p r o c e s s i n gi n f o r m a t i o n ，i tw i l lb ea p p l i e dw i d e l y n o r m a l l y , t h ew i r e l e s ss e n s o rn e t w o r k c o n s i s t so fl a r g en u m b e r so fm i c r os e n s o rn o d e s ，w h i c ha r el o w c o s t ，l o w p o w e r c o n s u m p t i o na n dh a v i n gt h ea b i l i t yo fa p p e r c e i v i n g ，p r o c e s s i n ga n ds t o r i n gd a t a , a n d w i r e l e s sc o m m u n i c m i o n t h en e t w o r k sw i l lb es e l f - o r g a n i z e db yt h en o d e si n s i d e s i n c e t h en o d e sa r es m a l ld e v i c e s ，t l l e ya r et y p i c a l l ye q u i p p e dw i t l lb a t t e r y s ot h el i f eo f n o d e sm o s t l yd e p e n d so nt h eb a t t e r y h o wt or e d u c et h ee n e r g yc o n s u m p t i o na n de x t e n d t h el i f eo ft h en e t w o r ka sl o n ga sp o s s i b l ew i l lc o m ef o n l li nt h ef r o n to fn e t w o r k r e s e a r c h e r sw h e nt h e yc o n s i d e rt h er o u t i n gp r o t o c o l sf o rw i r e l e s ss e n s o rn e t w o r k s t h i s p a p e rf o c u s e so ns t u d y i n gt h ec l u s t e r i n ga l g o r i t h ma n dt h em e t h o d st ou s et h en o d e s e n e r g ye f f i c i e n t l y t h em a i nr e s e a r c ha n dr e s u l t sa r ea sf o l l o w s ： ( 1 ) t w ok i n d so fh i e r a r c h i c a lc l u s t e r i n ga l g o r i t h m sa r ep r o p o s e di nt h i sp a p e r t h a t i s ，c e n t r a l i z e dc l u s t e r i n ga l g o r i t h ma n dd i s t r i b u t e dc l u s t e r i n ga l g o r i t h m b o t ho ft h e m a r er e a l i z e di nt h et w oh i e r a r c h yt y p e t w oa l g o r i t h m sw i l lb ei n t r o d u c e ds e p a r a t e l y f o r t h ec e n t r a l i z e dc l u s t e r i n ga l g o r i t h m ，t h ec o n c e p to fl o g i c a ln o d ei d e n t i f i e ri sp u tf o r w a r d w i t ht h es i n kn o d e s ，t h es e n s o rn o d e sc o u l dg e tt h ei n f o r m a t i o na b o u tt h e i rl o g i c a ln o d e i d e n t i f i e r s ，h e a d e rl o c a t i o n sa n dt h ev a l u eo fr a d i u st oc l u s t e r i n g t h e n , t h en o d e sc o u l d e x c h a n g em e s s a g e st ot h en e i g h b o r i n gn o d e st om a k es u r ew h oa r eh e a d e r s ，w h oa r e m e m b e r s a n dt h ec l u s t e r sa r eo r g a n i z e de v e n t u a l l y f o rt h ed i s t r i b u t e dc l u s t e r i n g a l g o r i t h m , t h ep r i o r i t yo fan o d ei sd e c i d e db yt h er e s i d e n t i a le n e r g yi t s e l fh a sa n dt h e n u m b e ro fi t sn e i g h b o r i n gn o d e s t h en o d e st h a th a v em o r er e s i d u a le n e r g ya n dl a r g e r n e i g h b o r i n gn o d e sn u m b e r w i l lb r o a dt h em e s s a g et oc o m p e t et h ec l u s t e rh e a d e re a r l i e r t h a nt h eo t h e rn o d e s a n dt h e n , t h ep r o c e s s e st oo r g a n i z ec l u s t e r ss t a r t e d t h i sp o l i c y c o n s i d e r i n gb o t ht h en o d er e s i d u a le n e r g ya n dn e t w o r kc o n n e c t i v i t yc a l le f f e c t i v e l y r e d u c et h en u m b e ro fc l u s t e r so r g a n i z e d ( 2 ) an e we n e r g yb a s e do nr o u t 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 k s ( e b r a ) i sp r o p o s e di nt h i sp a p e rt h ee b r aa d o p t sm u l t i h o pc o m m u n i c a t i o nm o d e lt os e n do u t m e s s a g e s ，b a s e do nt h ec l u s t e rh e a d e r ss e l e c t e db yt h ec e n t r a l i z e dc l u s t e ra l g o r i t h mo r a b s t r a c t t h ed i s t r i b u t e dc l u s t e r i n ga l g o r i t h m 1 1 1 er e a l i z a t i o no ft h ee b r aw i l lt h r o u g ht h r e e m a i ns t e p s ，r o u t i n gb u i l d i n g ，d a t at r a n s m i s s i o na n dr o u t i n gm a i n t e n a n c e w h e nan o d e h a sd a t at os e n d ，i tw i l lc h e c ki t sr o u t i n gt a b l e ，c h o o s et h em i n i m a le n e r g yc o n s u m p t i o n f o rc o m m u n i c a t i o n , a n dt h e ns e n dt h ed a t a 1 1 1 en o d ew h or e c e i v e st h ed a t aw i l ld ot h e s a m eo p e r a t i o n ，u n t i lt h ed a t ai ss e n tt ot h es i n kn o d e a l s o ，t h ee b r ac o n t a i n sa n i m p r o v e dm e t h o df o rr e q u e s t r e s p o n s ed a t at r a n s m i s s i o nm o d e ac o n t i n u o u sf l a gi s i n t r o d u c e dt oi d e n t i f yw h e t h e ran o d ec o u l ds e n dd a t ac o n t i n u o u s l y s ot h ep e r f o r m a n c e o fd a t at r a n s m i s s i o nw i l lb ee n h a n c e d ，a n da ss a m ef o rt h er a p i dr e s p o n s ec a p a b i l i t yo f n o d e sf o re m e r g e n c yd a t aa p p e a r s ( 3 ) t w oc l u s t e r i n ga l g o r i t h ma r ei m p l e m e n t e dr e s p e c t i v e l ya c c o r d i n gt on e t w o r k s i m u l a t i o nt o o l sn s 2 2 8 t h es i m u l a t i o nr e s u l t st e s t e df o re b r ai nt h ed i f f e r e n t s c e n a r i o sa r er e c o r d e da n dc o m p a r e d 谢t l lt h o s ei nt h el e a c h a n dt h ea n a l y s i so ft h e r e s u l t si n d i c a t e st h a tt h ee b r ar o u t i n ga l g o r i t h mc a ns a v et h ee n e r g yc o n s u m p t i o n , e x t e n dt h en e t w o r kl i f e c y c l ee f f e c t i v e l y a tt h es a m et i m e ，i tc o u l di m p r o v et h e t h r o u g h p u to ft h en e t w o r ka n dt h ed a t at r a n s m i s s i o n k e y w o r d s ：w i r e l e s ss e n s o rn e t w o r k s ，r o u t i n gp r o t o c o l ，c l u s t e r i n ga l g o r i t h m ，l o g i c a l i d e n t i f i e r , e b r a i u 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 日期：川年f 月必日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：辎盘碡 导师签 日期： 第一章引言 1 1 研究背景 第一章引言 微电子、无线通信、微处理器以及微机系统等技术的飞速发展，促进了低成 本、低功耗、多功能的微型无线传感器的快速发展。由这些微型传感器构成的传 感器网络引起了人们极大的关注。这种无线传感器网络具有数据采集、信息处理、 协同合作等功能，并且不需要固定网络基础设施的支持，具有快速部署、抗毁性 强等特点，被广泛应用到军事、环境、气象监测和农田管理等领域。商业周刊和 m i t 技术评论在预测未来技术的发展报告中，分别将无线传感器网络列为2 1 世纪 最有的2 l 项技术和改变世界的1 0 大技术之一1 2 。 随着无线传感技术的不断发展和成熟，人们对无线传感器网络发展也投入了 越来越多的人力和物力资源。2 0 0 4 年的( i e e es p e c t r u m ) ) 杂志发表了一期专集： 传感器的国度。该专辑中详细论述了无线传感器网络将来可能的发展空间和和广 泛的应用领域。通常情况下，网络中的传感器节点大都采用电池供电，但是通过 更换电池的方式来补充节点的能源在多数情况下是不现实的，因此，在无线传感 器网络设计中，技术和协议的设计实现都要以节能为前提。如何设计有效的节能 策略，延长网络的生命周期成为无线传感器网络的重要问题【j 。路由技术是无线 传感器网络中的一项关键技术，良好的路由协议能够有效的节省传感器节点工作 时的能量消耗，从而延长网络的生命周期。因此，设计能量有效的路由协议对于 无线传感器网络是十分必要的。 1 2 无线传感器网络概述 1 2 1无线传感器网络的概念 无线传感器网络是一种由大量具有无线通信能力的节点自组形成的无中心、 无基础设施支持的无线网络。根据文献【5 - 7 1 对无线传感器网络的定义：无线传感器 网络是由部署在监测区域内的大量传感器节点，以无线通信的方式形成的自组织 的无线网络系统，其目的是协作地感知、采集和处理网络覆盖的地理区域内感知 电子科技大学硕士学位论文 对象的信息，并发送给观察者。通过上述定义可以看出，传感器节点、感知对象 和观察者是无线传感器网络中的三个基本要素。 无线传感器节点通常由能量供应模块、传感器模块、处理器模块和无线通信模 块四部分组成8 。9 1 。典型的无线传感器节点结构如图1 1 所示。 传感器模块处理器模块无线通信模块 图l - 1 无线传感器节点结构 能量供应模块通常采用微型电池，为传感器节点中其他模块的运行提供所需 的能量。传感器模块主要负责对监测区域进行信息采集，并对采集到的数据进行 转换：处理器模块负责协调节点各部分的工作；无线通信模块主要负责和其他传 感器节点进行无线通信，完成控制信息的交换和采集数据的收发等工作【1 0 - 1 1 】。 1 2 2 无线传感器网络体系结构 无线传感器网络系统通常包括传感器节点、汇聚节点( s i n k ) 和任务管理节点 三部分【1 2 】。一个典型的无线传感器网络系统体系结构如图1 2 所示。 c 7 监测区域 。 传感器节点 _ 数据交换 任务管理节点 图1 2 无线传感器网络体系结构 由于部署的传感器节点数量众多，较多采用随机投放的方式，导致传感器节 2 第一章引言 点的位置不能预先确定，节点通过无线自组织方式形成网络拓扑结构。传感器节 点通过局部传感器节点，采取多跳的通信方式将采集到的数据传送到s i n k 节点。 s i n k 节点是专门的数据接收节点，相对于一般节点具有较强的处理能力、存储能 力和通信能力；同时做为传感器网络和与外部网络进行连接的桥梁，需要具有不 同协议之间的通信格式的转换能力i l 3 1 。 1 2 3 无线传感器网络的特点 无线传感器网络具有以下特点： 1 ) 规模巨大 大规模网络主要表现在网络中传感器节点数目多，成百上千；分布区域广， 一般分布在面积较大的区域，协同完成监测任务。对于传感器网络来说，大规模 网络具有如下的优点【1 4 。7 】：众多的传感器节点能够增大覆盖的监测区域，减少监 测空洞和盲区；传感器节点通过不同区域中，信息的信噪比较大；分布式的处理 方式，能够提高监测数据的精确度等。 2 ) 自组织性 传感器节点通常被部署运行在无基础设施支持的区域，节点的位置及其能够 进行通信的邻居节点事先都不知道。在复杂的动态变化环境中，我们无法对网络 进行人工配置，这就需要传感器节点之间相互协调以建立连接【1 8 - 1 9 1 。 3 ) 动态性 随着网络的运行，网络中的节点可能由于自身能量不足或者外界因素影响而 失效，也有可能补充进新的传感器节点到网络，这样就会导致网络拓扑结构的动 态变化口0 1 。因此，传感器网络必须具有自动拓扑的能力，即通过相互协调组建新 的网络，维护网络的正常运行。 4 ) 电源能量有限 传感器节点通常采用电池供电，但是电池的能量有限。这些节点通常又运行 在近似恶劣甚至危险的远程环境中，更换或替代都很困难【2 1 】。 5 ) 应用相关性 客观世界的物理量多种多样，对于不同用途的应用系统，人们关心的物理量 也不尽相同。其节点的软硬件设计和网络运行的协议都和特定应用密切相关 2 2 - 2 3 。 6 ) 以数据为中心 不同于传统具有中央控制节点的网络系统，以数据为中心的基本思想是把传 电子科技大学硕士学位论文 感器节点视为数据流的感知源，把传感器网络视为感知数据空间，把数据管理作 为网络的应用目标f 2 4 1 。 1 2 4 无线传感器网络的关键技术 无线传感器网络作为当今信息领域的研究热点，涉及到许多的交叉学科。目 前研究涵盖了无线传感器网络的拓扑控制、路由协议、时间同步、数据融合、数 据管理、网络安全等方面【2 5 。3 0 1 。 1 ) 网络拓扑控制 网络拓扑控制的主要任务，是在满足整个网络系统覆盖度和连通度的前提下， 通过控制节点发射功率、选择网络骨干节点等方法建立高效的数据传送网络。 2 ) 路由协议 无线传感器节点本身资源受限的特点决定了无线传感器网络路由协议不能太 复杂。对于大规模的无线传感器网络应用，需要设计低功耗的路由机制与之相适 应。并且，无线传感器网络和传统网络之间存在很大差异，致使传统的路由协议 并不适用于无线传感器网络。 3 ) 时间同步 作为分布式网络，无线传感器网络的时间同步对协议运行及基于时间同步的 应用，比如记录数据采集时间、时隙的划分等应用来说是必不可少的。 4 ) 数据融合 由于传感器网络系统的能量有限，通过减少数据的传输量，可以有效的节省传 输数据消耗的能量。因此，传感器节点收集数据时，可利用节点的本地计算和存 储能力进行数据融合，去除冗余信息。 5 ) 数据管理 从数据存储的角度来看，传感器网络可被视为一种分布式数据库。它与传统的 分布式数据库在管理上存在很大差异。由于传感器节点能量有限而且容易失效， 对传感器网络使用的数据管理系统一方面尽可能的减少能量消耗，同时也要能够 提供有效的数据管理服务。而且，传感器网络中产生的数据是无限的，无法通过 传统的数据库管理技术进行管理。 6 ) 网络安全 无线传感器网络作为任务型的网络，不仅要进行数据的传输，而且要进行数 据的采集和融合、任务的协同控制等。如何保证传感器网络能够机密的执行监测 4 第一章引言 任务、产生可靠有效的数据以及保证数据在传输过程中的安全性已经成为无线传 感器网络需要考虑的内容。除此之外，为了确保数据融合后数据源消息的保留， 水印技术也成为无线传感器网络安全的研究的重要内容之一。 1 2 5 无线传感器网络的应用 随着人们对无线传感器网络的深入研究，无线传感器网络的的应用前景非常广 阔，其应用领域将会逐渐深入到人类生活的方方面面。例如在军事、医疗护理、 环境监测、智能家居、建筑物状态监测等方面都有广泛的应用( 3 卜3 4 j 。在军事应用 上，通过部署在战场区域中的传感器节点采集到十分准确的目标位置信息，通过 生物和化学传感器，准确的监测到生化武器的成分，及时提供情报信息等；在医 疗护理方面，可以给病人安装特殊用途的传感器节点，用来监测人体的各种生理 数据，人工视网膜工程就是一项传感器节点在生物医学的应用；在环境监测方面， 可以用来监测火山活动、生物栖息地的生态环境等，加州大学伯克利分校曾经和 大西洋学院联合，在大鸭岛部署了一个传感器网络监测系统，用来观察岛上海燕 的生活习性：在智能家居方面，可以在家居产品中嵌入传感器节点，通过无线通 信方式与外部i n t e r a c t 网络连接实现远程操控，给人们的生活带来更加方便、舒适 和人性化的家居环境；在建筑物状态监测方面，通过在建筑物安装传感器节点， 监测建筑物发生的些细小的变化，及时报告建筑物的健康状况，比如在大楼、桥 梁和其他建筑物上面安装传感器节点，使其能够自动监测并把监测结果报告给相 关管理部门，从而实现建筑物状态的自动实时监测等等。 1 3 论文研究的目的和意义 无线传感器网络处于新技术的最前沿。目前，国际上许多高校和研究机构从 2 0 0 0 年开始发表一些有关传感器网络研究结果的报道，但是，这些研究成果仍处 于起步阶段，距离实际应用的要求还相差甚远；国内在无线传感器网络方面的所 做的研究工作还不够。但是无线传感器网络做为一门应用广泛的新兴技术，及时 开展无线传感器网络相关领域的基础研究，对整个国家的技术进步和经济发展将 有重大的战略意义。 本文从网络拓扑控制和路由协议的角度出发，通过对网络能量均衡消耗方面 的深入研究，提出了两种不同的簇头选择算法和基于能量策略的无线传感器网络 路由算法。仿真结果显示，本文提出的路由算法具有较好的能量有效性和稳定的 电子科技大学硕士学位论文 数据传输性。这为无线传感器网络在拓扑控制和路由算法在均衡能量消耗、最大 化网络生命周期和提高系统工作效率方面提供了一种可行的研究思路和方法。 1 4 研究内容和本文所做的工作 无线传感器网络的研究领域主要有传感器网络体系结构、传感器网络的支撑 技术和传感器网络的应用技术等。就传感器网络体系结构方面来说，有m a c 协议、 路由协议、网络拓扑控制等；网络的支撑技术有定位技术、时间同步技术、数据 管理技术、数据融合技术和安全技术等；传感器网络的应用技术研究主要为传感 器网络的应用领域和方向，比如环境监测系统、目标跟踪系统等。 本文研究的主要内容是传感器网络体系结构中的网络拓扑控制和路由协议部 分。在深入研究了已有的拓扑控制算法的基础上，提出了两种无线传感器网络节 点成簇算法，即集中式成簇选择算法和分布式成簇选择算法。在集中式成簇选择 算法中，提出了节点逻辑标识符的概念，和以往的集中控制式算法相比，该算法 在网络的成簇选择过程、数据融合以及数据查询等方面提供了一种新的研究思路。 在分布式成簇选择算法中，充分考虑了节点当前剩余能量水平和节点在网络中的 连通性。在满足网络覆盖度的情况下，该算法能够有效的减少网络中成簇的数量， 扩大了网络能量使用的节省空间。 基于上述提出的两种成簇算法，本文又提出了一种基于能量策略的线传感器 网络路由算法；同时，在算法中通过增加数据连续发送标识位，增强了数据传输 性能和对突发数据的响应能力，从而改进了请求响应型的数据传输模式；最后通 过n s 2 仿真工具，分别实现了基于两种成簇算法的路由协议仿真程序，在多种测 试场景中对路由协议进行了仿真实验，并和经典l e a c h 算法得到的仿真结果做了 对比分析；结果显示本文提出的路由算法能够在有效的延长网络生命周期，提高 网络的吞吐能力，具有较好的能量有效性和稳定的数据传输性。 1 5 论文章节安排 第一章，引言。介绍课题的研究背景、无线传感器网络的概念、体系结构及 特点、关键技术和网络的应用领域，阐述了课题研究目的和意义以及本文的研究 内容和主要工作。 第二章，无线传感器网络路由协议。介绍了无线传感器网络和传统网络的区 6 第一章引言 别，无线传感器网络路由协议的特点和性能指标；对无线传感器网络路由协议进 行分类，并对几种典型的平面型和层次型路由协议进行详细的介绍和分析。 第三章，集中式成簇选择算法。简要描述了集中式成簇选择算法的实现过程， 算法应用的系统模型，并在算法中引入了节点逻辑标识符的概念；详细描述了十 一种消息的类型和格式；最后深入分析研究了通过拓扑发现、簇组织的建立和簇 自愈三个阶段实现集中式成簇算法的具体过程。 第四章，分布式成簇选择算法。对分布式成簇选择算法的实现进行简要描述； 指出了算法应用的系统模型和节点的表示方法，并详细描述了七种消息的类型和 格式；最后对分布式成簇算法的实现过程，即节点邻居发现、簇组织的建立和簇 自愈过程进行了详细的描述。 第五章，基于能量策略的无线传感器网络路由算法。简单分析了节点单跳和 多跳通信的能量消耗代价，简要描述路由算法的实现过程，并对消息类型和消息 格式进行了详细的描述。最后对路由协议实现过程，即路由的建立、数据传输和 路由维护进行了详细的描述。 第六章，路由算法的仿真实验和结果分析。介绍了网络仿真工具n s 2 和路由 算法的仿真环境和仿真参数：分别对集中式成簇、分布式成簇算法和路由算法进 行描述，并给出了仿真脚本程序，最后对路由算法进行仿真实验，并对结果进行 了比较和分析。 第七章，总结与展望。对本文的工作进行总结和下一步工作的展望。 7 电子科技大学硕士学位论文 第二章无线传感器网络路由协议 2 1无线传感器网络和传统网络的区别 在无线传感器网络的研究初期，人们曾一度认为成熟的因特网技术加上a dh o c 路由机制对传感器网络的设计是足够充分的。然而通过对这些协议进行深入的研 究发现，这些协议并不适用于无线传感器网络【”删。 首先，在无线传感器网络中，节点部署之后的拓扑结构是准静态的，一般不 具有移动性，这不像传统的a dh o c 网络中的节点一样具有快速移动的特征，因此 没有必要花费很大的代价去频繁地更新路由表信息。 其次，无线传感器网络中的所有节点都可以充当源节点，向全网唯一的目的 节点s i n k 节点发送数据；而在传统的网络中，节点大都采用点对点的通信方式。 第三，无线传感器网络是以数据为中心的。传统网络大都以数据传输为中心， 通过点对点的方式传输数据；而在无线传感器网络中，某些节点之间的路由是不 需要的，所以传感器网络的不能够采用传统网络的路由方式。 第四，在监测区域或观测对象内部署了大量的传感器节点，这些传感器节点 采集到的数据具有很大的相关性，存在大量的冗余信息。 最后，传感器节点通常只具备有限的电池、计算和存储能力，要尽可能的充 分使用这些资源，以确保整个系统能够长时间稳定的工作，这就需要更为有效的 能量使用管理机制。 2 2 无线传感器网络路由协议的特点和性能指标 2 2 1无线传感器网络路由协议的特点 在无线传感器网络的体系结构中，网络层的路由协议设计非常重要。与传统 网络由协议相比，无线传感器网络路由协议具有如下的特点： 1 ) 能量优先 传感器网络中节点的能量有限，延长网络的生命周期成为传感器网络路由协 议设计的重要目标。在设计路由协议的时候，不仅需要关心单个节点的能量消耗， 8 第二章无线传感器网络路由协议 而且更要考虑整个网络能量的均衡消耗。 2 ) 基于局部拓扑信息 传感器网络为了节省进行通信时的能量消耗，通常采用多跳的通信模式，而 节点的存储资源和计算资源有限，节点所能存储的路由信息不多。这就需要节点 能够在获取到局部拓扑信息的情况下，实现简单高效的路由机制。 3 ) 以数据为中心 传感器网络中大量的传感器节点被随机部署到监测区域，就用户来说，他们 所关注的只是监测区域的感知数据，一般都不需要知道传送来的信息是由哪一个 节点获取的。而且，数据在传输的过程中需要通过数据融合操作，把多个传感器 节点采集到得数据到融合之后传到汇聚节点。 4 ) 应用相关性 根据传感器网络的应用环境的不同，系统采取不同的数据通信模式。路由机 制的制定都是针对某个特定应用环境的，这是传感器网络应用相关性的体现。设 计者需要针对具体应用的需求，设计与之相适应的特定路由机制。 2 2 2 无线传感器网络路由协议的性能指标 针对传感器网络的路由机制的特点，在根据具体应用设计路由机制时，一般 需要考虑以下几方面的要求： 1 ) 能量高效性 无线传感器网络路由协议在选择消息传输路径的时候，不仅需要考虑节点的 能量消耗，而且还需要从全局网络的角度出发，选择能够使整个网络具有较低能 量消耗的传输路径。 2 ) 可扩展性 对于不同的无线传感器网络应用，监测区域的范围和节点的密度都存在较大 差异，网络规模也大不相同；而老节点死亡、新传感器节点的加入以及由于节点 的移动等都会导致网络拓扑结构发生变化，这就要求路由机制具有可扩展性，能 够适应网络结构的变化。 3 ) 鲁棒性 传感器节点能量用尽等因素会造成传感器节点的死亡、周围环境和无线链路 本身的缺点也会影响到无线链路通信的质量，由于这些因素的存在，就要求无线 传感器网络的路由机制需要具有一定的容错能力。 9 电子科技大学硕士学位论文 4 ) 快速收敛性 由于拓扑结构的动态变化，就需要传感器网络的路由机制能够快速的建立新 的路由路径，减小通信开销，确保无线传感器网络的正常运行。 5 ) 安全性 无线传感器网络是一个开放的网络环境，通信的安全性是值得人们关注的。 网络中节点众多，潜在的网络攻击会变得更有可能发生，而当前具有安全身份认 证的协议并不多见。在将来的网络路由协议中，安全性将逐渐引入进协议中来。 2 3 无线传感器网络路由协议的分类 针对不同的传感器网络应用，研究人员提出了不同的路由协议，但到目前为 止，仍然缺乏一个完整和清晰的路由协议分类。其中，文献 3 7 - 4 5 1 对现有的无线传 感器网络路由协议进行了大量的分析研究和总结工作。按照最终形成的拓扑结构， 可以划分为平面型路由协议和层次型路由协议。 2 3 1 平面型路由协议 2 3 1 1fio o din g 与g o s sipin g 协议 f l o o d i n g t 4 6 j 和g o s s i p i n g t 47 j 协议是两种传统的路由协议。在这两种协议当中， 数据的转发过程不需要网络拓扑结构的维护和路由算法的支撑。在f l o o d i n g 协议 中，每个节点接收到的广播的数据之后，再把该数据广播到它的所有邻居节点； 接收到该消息的节点继续广播该消息，直到消息达到目的传感器节点或者达到数 据报传送的最大跳数值。泛洪算法非常容易实现，而且具有较高的健壮性，但是 内爆和重叠问题是它固有的缺陷；而且泛洪算法并没有考虑节点当前能量的可用 状况问题，盲目资源使用，不能自适应选择路由。内爆是由于同一个数据的不同 副本在网络中被传输到同一节点而引起的；而重叠是由于监测同一区域的不同传 感器节点给网络中的同一节点发送了相似的监测数据。内爆和重叠如图2 1 所示。 g o s s i p i n g 协议就f l o o d i n g 协议的内爆问题做了改进，随机选取节点的一个邻近节 点进行数据包转发，避免了内爆问题的发生。然而，g o s s i p i n g 协议的这种解决方 式增加端到端的通信传输延迟。 1 0 第二章无线传感器网络路由协议 q 弋二 。么，。八压 图2 1 内爆与重叠 2 3 1 2 s pin 协议 s p i n 4 8 】( s e n s o rp r o t o c o lf o ri n f o r m a t i o nv i an e g o t i a t i o n ) 协议是最早的具有代 表性的无线传感器路由协议，它主要针对泛洪路由协议进行改进，其目标是通过 使用节点间的协商制度和资源自适应机制，解决泛洪算中存在的内爆和重叠问题； 同时，它也是一种以数据为中心的自适应路由协议。该协议考虑了无线传感器网 络中的数据冗余问题，即邻近的传感器节点所感知的数据具有相似性，节点通过 协商的方式减少网络传输的数据量，节点只广播其他节点所没有的数据以减少冗 余。 s p i n 协议提出了元素据( m e t , a - d a t a ) 的概念。元数据是原始感知数据的一个 映射，用来描述原始感知数据，而且元数据所需要的数据位比原始感知数据小， 采用这种变相的数据压缩策略可以进一步减少通信过程中的能量消耗。s p i n 采用 三次握手的方式来是实现数据的交互，协议在运行过程中使用三种报文数据： a d v 、i 冱q 和d a t a 。a d v 用于数据的广播，当某一个节点的数据可以共享时， 使用a d v 广播报文通知其邻居节点；r e q 报文用于发送请求数据，当某一个收到 a d v 的节点希望能收取d a t a 数据包时，发送r e q 数据包；d a t a 为原始感知数 据包，里面封装了感知的原始数据。s p i n 协议的工作流程如图2 2 所示。 电子科技大学硕士学位论文 ( 由 ( e ) ( f ) 图2 - 2s p i n 协议的工作流程 s p i n 协议下节点不需要维护邻居节点的信息，在一定程度上能够适应节点的 移动。根据协议的模拟结果显示，在能量消耗方面它比传统模式减少一半以上。 2 3 1 3d jr a c t e dd i f f u s i o f i 算法 d i r e c t e dd i f f u s i o n 4 9 】路由协议是以数据为中心的路由协议的一个重要里程碑， 由e s t r i n 等人专门为传感器网络设计的路由策略，协议中引入了三个基本概念：兴 趣、梯度和路径加强。s i n k 节点通过泛洪的方式周期性的广播“兴趣”消息，告 诉网络中的节点它需要收集的信息。“兴趣”在网络中扩散的同时也建立了路由路 径，那些采集到了和“兴趣 相关的数据的传感器节点，通过“兴趣”扩散阶段 建立的路径将采集到的数据传送到s i n k 节点。 定向扩散路由机制可以分为周期性的兴趣扩散、梯度建立以及路径加强三个 阶段。定向扩散模算法的工作流程如图2 3 所示。 1 2 第二章无线传感器网络路由协议 源节 源节 ( a ) 兴趣扩散 ( b ) 梯度建立 oo 貅- 一。当s i i l l 【 日o 园叫“ oo ( c ) 路径加强 图2 3 定向扩散路由机制 s i n k 节点周期性地向邻居节点广播兴趣消息。在“兴趣”消息传播的过程中， 协议逐跳的在每个传感器节点上建立反向的从数据源到s i n k 节点的梯度场，传感 器节点将采集到的数据沿着梯度场传送到s i n k 节点，梯度场的建立根据成本最小 化和能量自适应原则。“兴趣”扩散完成后，网络的梯度建立过程也就完成了。当 网络中的传感器节点采集到相关的匹配数据后，则向网络中所有对此数据感兴趣 的节点转发该数据。这样s i n k 节点会收到从不同路径上传送过来的相同数据。在 收到数据以后，s i n k 节点选择一条最优的路径作为强化路径，后续的数据就沿着 这条强化路径传送。 2 3 2 层次型路由协议 层次型路由协议是一种分层结构的路由协议。网络通常被划分为多个簇，每 电子科技大学硕士学位论文 个簇由一个簇头和多个簇成员组成。这些簇头形成高一级的网络，在这高一级的 网络中还可以继续进行分簇，形成更高一级的簇网络。簇头节点负责簇内成员节 点的管理，并且完成簇内节点信息的收集和融合，同时簇头节点还选哟负责簇间 数据的转发。典型的层次型路由协议有l e a c h 、h e e d 、t e e n 、a p t e e n 、p e g a s i s 和h i e r a r c h i c a l p e g a s i s 等。 2 3 2 1 l e a c h 协议 l e a c h 【5 0 】( l o w - e n e r g ya d a p t i v ec l u s t e r i n gh i e r a r c h y ) 是m i t 的c h a n d r a k a s a n 等人为无线传感器网络设计的低功耗自适应路由协议，也是最早提出的层次型路 由协议。其基本思想是网络周期性的随机选择簇头节点，其他的非簇头节点以就 近原则加入相应的簇头，形成虚拟簇。簇内节点将感知到的数据直接发送给簇头， 由簇头转发给s i n k 节点，簇头节点可以将簇内数据进行融合处理，用以减少网络 传输的数据量。 8 亩呲 御印 舀 石 图2 4l e a c h 协议网络结构图 l e a c h 协议定义了“轮( r o u n d ) 的概念，一轮由初始化阶段和稳定阶段两 个阶段组成。为了避免额外的处理开销，稳定阶段一般持续相对较长的时间。在 初始化阶段，簇头通过下面的机制产生的。传感器节点生成0 1 之间的随机数， 如果该随机值大于阈值删，则该节点成为簇头节点。删的计算方法如式( 2 - 1 ) 。 丁( 刀) = 星 胛g 1 一p 宰 r r o o d ( 1 p ) ( 2 1 ) 0其他 其中，p 为节点中成为簇头的百分数( k n ) ；，是当前的轮数；g 是在过去的 1 4 第二章无线传感器网络路由协议 1 p 轮中没有充当过簇头的节点的集合。在r = o 时，每个节点都以概率p 来做簇头； 在前r 轮中做过簇头的节点，在以后的( 1 p 一，) 轮中不能再次当选为簇头。簇头一 旦选定，簇头节点便主动向所有的节点广播这一消息。依据接收信号的强度，节 点选择它自己所要加入的簇，并告知相应的簇头。簇头采用基于时分复用的方式 为其成员分配通信时隙。簇形成之后，数据传输便可开始。成员节点持续采集监 测数据，在其分配的时隙阶段把数据发送给簇头。簇头接收数据后进行融合处理 再发送到s i n k 节点。持续一段时间以后，整个网络进入下一轮工作周期，重新选 择簇头。仿真试验证明，l e a c h 协议是一个能够有效地节