（计算机系统结构专业论文）wsn网络中基于分簇实时传输算法研究.pdf

ar e a l t i m e a n s m l s s l o n a l g o r i t h m b a s e do n c l u s t e r i n g s t r u c t u r ei nw s n at h e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t f o rt h em s d e g r e ei nc o m p u t e rs c i e n c e b y z h e n r o n gl u o p o s t g r a d u a t ep r o g r a m d e p a r t m e n to fc o m p u t e r s c i e n c e c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：l i u y u h u a a c a d e m i ct i t l e ：p r o f e s s o rs i g n a t u r e a p p r o v e d m a y 2 0 1 1 mml 川川4 i哪2m 8 9咖8ii-y 硕士学位论支 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 日期：少“年6 月卜 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。同时授权 中国科学技术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 作者签名： 日期加 孙弛刻璐 导师签名：弘l 孕 日期：沙r f 年6 月p 本人已经认真阅读“c a l l s 高校学位论文全文数据库发布章程 ，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库 中全文发布，并可按“章程 中的 规定享受相关权益。回重论塞提交盾溢厦i 旦圭生；旦= 生；旦三生蕉查! 储挑硷穆象 日期砂f f 年角f 日 孙签名：l 磁导师签名：留l 御 日期少【f 年6 月f 日 切乔p 乡 终“ 中文摘要 传感器节点由于体积和处理能力的限制，节能成为无线传感器网络技术研究的 关键点。据研究发现，在网络工作过程中节点之间的信息的收发消耗了网络的大量 能耗，而节点信息的处理与各个协议层是密不可分的，因此如何设计节能高效的算 法成为无线传感器网络的重点。 本文根据无线传感器网络的研究现状，介绍了现有的路由算法和传输算法，通 过分析比较发现目前的节能算法仅仅考虑了网络层的节能或者传输层的节能，其实 将网络层和传输层结合起来考虑，能更有效的均衡网络的能量消耗。为了弥补现有 算法的不足，本文提出了基于节点分布度的路由算法l e a c h d 和基于分簇实时传 输算法r t b c 。 l e a c h d 是基于l e a c h 提出的路由算法，该算法综合考虑节点的分布密度， 通过引入节点连通度修改簇头阀值和设定成簇的半径来均衡节点能量的消耗，并在 簇头之间采用多跳通讯机制防止簇头节点过度耗能。在l e a c h d 算法仿真分析过 程中，主要从网络节点死亡时间、网络传送等量信息消耗的能量值和相同能量下节 点存活个数三个方面对两种算法进行比较分析，实验表明l e a c h - d 能够更有效的 降低了簇头节点的能量消耗，降低网络的整体能耗，延长簇的生命周期。 r t b c 的主要思想是采用跨层技术，在l e a c h d 的基础上结合传输层技术来 进行数据传送。在w s n 网络中先找出簇头到基站的多条优化路径，然后结合基于 平均队列长度的拥塞控制方法，在多条优化路径中找出一条耗能最小并且实时性最 优的路径，最后沿着这条路径将数据传送到基站，以此来实现数据的实时传输。在 r t b c 算法仿真分析过程中，主要从网络时延、汇聚节点收包率和传输等量数据能 量消耗值来进行比较，实验表明r t b c 能够满足网络的实时性需求，能有效进行拥 塞控制，减少网络的能量消耗，从而达到提高网络性能的目的。 关键词：w s n 网络；连通度；分簇算法；实时传输；跨层技术 a b s t r a c t 1 1 1 es e n s o rn o d el i m i t e db yi t ss i z ea n dp r o c e s s i n gp o w e r ，s oe n e r g y s a v i n gi sak e y t e c h n o l o g yi nt h ew i r e l e s ss e n s o rn e t w o r k a c c o r d i n gt ot h ei n v e s t i g a t o r y , i ti st h a tt h e p r o c e s so fd a t at r a n s m i s s i o nc o n s u n l et h em o s te n e r g yo ft h en o d e s i no r d e rt os a v i n g t h ee n e r g yo ft h en e t w o r k , w ec a nc u tb a c kt h es i z eo ft h ed a t aa n dr e d u c e dt h ed i s t a n c e o ft r a n s m i s s i o n h o wt od e s i g ne f f i c i e n tr o u t i n ga l g o r i t h ma n dt r a n s m i s s i o na l g o r i t h mi s t h ek e yt e c h n o l o g yp o i n t so fw i r e l e s ss e n s o rn e t w o r k s i nt h ep a p e rw ei n t r o d u c e dt h ec u r r e n tr o u t i n ga l g o r i t h m sa n dt h et r a n s f e r a l g o r i t h m si nt h ew i r e l e s ss e n s o rn e t w o r k s w ef o u n dt l l a tt h ec u r r e n tm e t h o d s j u s t c o n s i d e rt h en e t w o r kl a y e ro rt r a n s p o r tl a y e ri nt h ee n e r g y - s a v i n gt e c h n o l o g y i nf a c t , t h e w a yw h i c hc o m b i n e dt h et r a n s p o r tl a y e rt e c h n o l o g yw i t ht h er o u t i n gl a y e rt e c h n o l o g y c a nb a l a n c et h en e t w o r ke n e r g yc o n s u m p t i o nm o r ee f f e c t i v e l y i no r d e rt om a k eu pt h e l a c ko fe x i s t i n ga l g o r i t h m s ，t h ep a p e rp r e s e n tt h el e a c h - da l g o r i t h ma n dt h er t b c a l g o r i t h m l e a c h dc o m b i n e st h ei d e a so fa d j u s t i n gt h et h r e s h o l df u n c t i o na b o u tt h en o d e s ，a f i x e dr a d i u so ft h ec l u s t e r i n ga n dam u l t i h o pc o m m u n i c a t i o nm e c h a n i s ma m o n gt h e c l u s t e rh e a d s i nt h es i m u l a t i o n , w ec o m p a r et h er e s u l t so fl e a c ha l g o r i t h ma n d l e a c h da l g o r i t h mf r o mc o m p a r i s o no fn e t w o r k1 i f e t i m ei nt h ev i e wo ff n d ，h n a a n du 、d t h et o t a le n e r g yc o n s u m p t i o ni no n er o u n di nt h es a m ea m o u n to fi n f o r m a t i o n a n dt h en u m b e ro fa l i v en o d e sa n dt h er o u n d so fs u r v i v a ln e t w o r k s i m u l a t i o nr e s u l t s s h o wt h a tt h el e a c h dp r o t o c o lc a ne f f e c t i v ee x t e n dt h en e t w o r kl i f e t i m em u c hm o r e t h a nl e a c hp r o t o c o l ，a n di m p r o v et h en e t w o r k sl i f e t i m ee f f e c t i v e l y i 汀b cc o m b i n e dt h et r a n s p o r tl a y e rt e c h n o l o g yw i t ht h er o u t i n gl a y e rt e c h n o l o g yt o a c h i e v er e a l t i m et r a n s m i s s i o no fd a t a f i r s t , w eu s ed i j k s t r aa l g o r i t h mt oi d e n t i f y m o r et h a no n eo p t i m a lp a t h sf o re a c hc l u s t e rh e a dt ot h eb a s es t a t i o n t h e ns e l e c t e da o p t i m a lp a t hf r o mt h ep a t h s 、析mc o n g e s t i o nc o n t r o lm e t h o d f i n a l l y , t h ed a t aw i l ls e n d d a t at ot h es i n ka l o n gt h i sp a t h i nt h es i m u l a ：t i o n w ec o m p a r et h er e s u l t sf r o mt h e n e t w o r kd e l a y , d a t et r a n s m i s s i o nr a t ea n de n e r g yc o n s u m p t i o no ft h es a m ea m o u n to f d a t a s i m u l a t i o na n a l y s i ss h o w st h a tt h ea l g o r i t h mp r o v i d e sr e a l - t i m et r a n s m i s s i o na n d g u a r a n t e e sr e l i a b i l i t y k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k ；d e g r e eo fc o n n e c t i v i t y ；c l u s t e r i n ga l g o r i t h m ； r e a l - t i m et r a n s m i s s i o n ；c r o s s l a y e r 硕士学位论文 m a s t e r st h e s i s 目录 中文摘要i a b s t r a c t i i 第1 章绪论1 1 1 无线传感器网络概述1 1 2w s n 技术热点4 1 3 本文的主要内容和组织结构6 第2 章无线传感器网络的路由和传输算法研究现状8 2 1 路由算法的研究现状8 2 2 典型路由算法的性能分析与比较1 2 2 3 传输算法研究现状。13 2 4 典型传输算法性能分析与比较1 5 2 5 本章小结1 6 第3 章改进的分簇算法l e a c h d 的设计与实现。 3 1l e a c h d 的提出1 7 3 2l e a c h d 的实现1 8 3 2 1 簇头阈值的选取1 8 3 2 2 成簇半径的选择2 0 3 2 - 3 簇间多跳机制2 1 3 3 仿真实验分析2 2 3 4 本章小结2 5 第4 章基于分簇实时传输算法的设计与实现2 7 4 1 分簇实时传输算法的提出2 7 4 2 分簇实时传输算法实现2 8 4 2 1 网络层与传输层的结合2 8 4 2 2 拥塞控制及丢包恢复机制的实现3 0 4 3 仿真结果分析3 0 4 4 本章小结3 3 第5 章总结和展望3 5 5 1 总结3 5 5 2 展望3 5 参考文献3 7 在校期间所发表的论文 致谢 4 2 硕士学位论文 m a s t e r st h e s i s 1 1 无线传感器网络概述 第1 章绪论 在当今信息技术飞速发展的时代，无线传感器网络逐渐进入我们的视野。正如 因特网将全球的计算机连接起来，实现了不同民族不同区域的人的交流一样。无线 传感器网络将计算机与人类世界联系了起来，实现了人与现实世界之间的交互。无 线传感器网络以其低功耗、低成本、分布式和自组织的特点带来了信息感知的变革， 被称为一种全新类型的计算机系统，美国商业周刊评选出的未来三大高科技产业中 传感器网络位居其一，具有极强的发展前剽。 随着微电子技术、计算机技术和通讯技术的发展，集数据采集、数据传输和数 据处理的无线传感器网络得到了极大发展。无线传感器网络是一种由大量微型智能 传感节点播散到监测区域形成的新型网络，其采用自组织的方式配置传感器节点， 通过节点的协同工作采集和处理网络覆盖区域中的信息1 2 j 。无线传感器网络是一种 全新的信息获取平台，能够实现复杂的指定范围内目标检测与跟踪，有着广阔的应 用前景，广泛应用于军事演习或实时对战、环境污染度监控和濒临灭绝物种生态环 境、医疗监控和监控护理、智能家居和智能幼儿园、桥梁公路等建筑物状态监控和 外太空探索等领域【8 】。 1 1 1 无线传感器网络的特点 无线传感器网络是集监测，采集及通信为一体的网络，由于体积的限制，节点 的存储能力、处理能力、通信能力和能量等都十分有限，不同于其他的网络，有其 自身的特点，主要特点如下【3 】： ( 1 ) 大规模性 无线传感器网络的大规模性主要体现在以下两个方面。一是在某些特定的应用 中，需要大范围的撒播传感器节点，如在监测森林火灾的应用中，传感器节点要覆 盖整个森林，以保证监测到森林的每个角落；另一方面是为了监测到精确的数据， 需要布置大量的、密集的传感器节点，以此来弥补网络动态变化的影响【4 】。 ( 2 ) 自组织性 由于传感器节点一般布置在没有基础结构的地方，各个节点的位置具有很大的 随机性，因此要求无线传感器网络具有自组织性。传感器节点具有自组织和自主配 置管理能力，网络通过拓扑控制和网络协议来协同管理节点进行任务发布和网络监 硕士学位论文 m a s t e r st h e s i s 测【5 1 。无线传感器网络的自组织性还要求网络能够适应由于节点的失效和通讯中断 等问题引起网络的动态变化。 ( 3 ) 动态性 在无线感器网络中，网络的拓扑结构由于节点失效、节点通信环境受到影响、 新节点的加入等因素而发生改变，因此要求无线传感器网络具有动态的系统可重构 性，能够适应各种变化1 6 。 “) 可靠性 传感器节点一般部署在环境恶劣的地理位置并且数目庞大，节点容易受到环境 的破坏或者无关人员的损害，人工无法维护到每个节点，也不可能进行系统的网络 维护，因此要求无线传感器网络的具有良好的容错性和鲁棒性 7 1 。 ( 5 ) 应用相关性 无线传感器网络的应用广泛，不同的应用背景对网络的要求不同，因此无线传 感器网络没有统一的硬件平台和软件系统，对无线传感器网络的设计主要根据实际 的应用来研究，这就是无线传感器网络与普通网络最显著的差别之一【8 】。 ( 6 ) v a 数据为中心 相对于传统的以地址为标识的因特网，无线传感器网络是以数据为中心的网 络。在网络中节点采用节点编号标示，节点随机部署，编号与节点的地理位置没有 必然的联系【9 】。汇聚节点发布查询任务，拥有该数据的传感器节点将消息传输给汇 聚节点，这种以数据为中心的思想更接近自然语言的交流，更能得到充足的发展。 1 1 2 无线传感器网络的体系结构 无线传感器网络结构主要由传感器节点，汇聚节点和管理节点组成【1 0 1 ，如下图 1 所示。 o 幢医簟o 图1 1 传感器网络结构 2 硕士学位论文 m a s t e r st h e s i s 传感器节点由飞机播撒或者大炮发射等方式随机部署在某个监测区域内，网络 自组织形成之后，节点进行信息监测和数据采集最终将数据反馈到汇聚节点，汇聚 节点通过互联网或卫星将数据传送到管理节点【1 1 1 。传感器节点是一种微型的嵌入式 节点，其在网络中兼具本地信息采集和异地信息转发、融合等功能；汇聚节点的处 理、通讯、存储等能力比传感器节点较强，在网络中起到中介的作用，同时发布管 理节点的监测任务和收集网络监测的信息；管理节点是管理终端，用户通过管理节 点对网络进行配置和管理i l 引。 由于应用背景的不同，传感器节点的组成了不尽相同，但一般由传感单元、处 理单元、通信单元和电源四部分组成，如下图1 2 所示。 阳 z 1 蔓 叵岫 ff ifi 电源 图1 2 传感器节点体系结构 传感单元主要负责信息的采集和转换，处理单元负责数据的融合、存储和转发， 通信单元负责节点之间无线通信，电源为整个节点提供能量【9 】。目前应用的传感器 节点主要有s m a r td u s t 、m i c a 、t e l o s 等系列节点，其中由加州大学伯克利分校研制 的用于传感器网络研究的m i c a 节点在学术应用中最为广泛。传感器节点的处理器 一般采用m o t l r o l a 公司的6 8 h c1 6 和i n t e l 公司的8 0 8 6 等嵌入式处理器，传 输芯片一般使用r f m 的t r l 0 0 和c h i p o n 公司的c c l 0 0 0 芯片【8 】。加州大学伯克 利分校的研究人员针对无线传感器网络的特点专门设计了t i n y o s 操作系统，它是 种开放源代码的嵌入式操作系统，具有高度的模块化特征，能够快速实现各种应 用【1 3 1 。 无线传感器网络的五层协议栈，如图1 3 所示，从横向角度来看无线传感器网 络由五层构成：物理层、数据链路层、网络层、传输层以及应用层，与传统的网络 硕士学位论文 m a s t e r st h e s i s t c p i p 协议栈相对应，从纵向角度来看主要包括能量管理平台、移动管理平台和任 务管理平台【1 4 】。 窒望星f 能 堡笪星 l 喜 网络层l 理 平 数据链路层l 二 物理层 l ， 移 动 管 理 亚 厶 r - 1 任 务 管 理 平 台 图1 3 传感器网络层次协议栈 各层协议如下： ( 1 ) 物理层的功能包括数据信号的调制和无线电的收发； ( 2 ) 数据链路层的功能主要包括数据帧的封装和检测、m a c 访问控制和差错控 制； ( 3 ) 网络层的功能主要包括路由的生成和路由的选择； ( 4 ) 传输层的功能主要包括传输过程中数据的流向、数据的拥塞控制机制和数 据丢包恢复机制等传输控制； ( 5 ) 应用层的功能主要包括基于特定应用的各种应用软件。 各平台功能如下： ( 1 ) 能量管理平台主要管理整个传感器节点的能量使用问题； ( 2 ) 移动管理平台主要监测节点的移动，动态更新邻居节点的位置，维护路由。 ( 3 ) 任务管理平台主要负责调度监测任务。 1 2w s n 技术热点 最早提出无线传感器网络研究的是美国u c l a 大学的w i l lj a mjk a i s e r 教授， 1 9 9 6 年他向d a r p a 提交的“低能耗无线集成微型传感器 报告，揭开了现代无线传 感器网络的序幕。无线传感器网络以其低功耗、低成本、高效率等特点，得到学术 界、工业界乃至政府的广泛关注，各国相续启动了无线传感器网络的研究计划，特 别是美国通过多种渠道投入巨大资金进行传感器网络的研究n 朝。无线传感器网络中 有许多的关键技术，下面对此进行简单的介绍。 ( 1 ) 网络拓扑控制 在无线传感器网络中，网络拓扑结构至关重要，好的拓扑可以提高网络的工作 4 硕士学位论文 m a s t e r st h e s i s 效率，减少能量的消耗，当前拓扑控制研究取得了一系列成果u6 】。 无线传感器网络拓扑控制研究有两个方面：节点功率控制和层次型拓扑控制。 前者通过调节节点的通信功率，减少节点的发送功率，同时考虑网络的连通度。目 前已经提出了c o m p o w 、l i n t l i l t 、l m n l m a 、d l s s 、l m s t 、r n g 和d r n g 等节点功率控制算法【1 6 1 。层次型拓扑控制主要利用分簇机制，将网络区域划分为一 个个簇结构，簇头实时监控网络环境，承担簇内数据处理和簇间数据传输的任务， 非簇头节点完成指定监测任务后进入休眠状态以节省能量。目前已经提出的分簇算 法有l e a c h 、l e a c h c 、h e e d 和d h c s 等层次分簇算法。 随着网络拓扑控制机制的研究，研究人员还提出了启发机制、数据捎带机制和 两种或两种以上控制机制结合使用，以达到节省节点能量和延长网络生命周期的目 的【1 6 1 。总而言之，网络拓扑控制机制研究应该结合实际应用背景，在满足网络连通 度的前提下，提高网络通信效率，延长网络生命周期。 ( 2 ) 网络时间同步 随着无线传感器网络在交通管理方面的应用，时间同步机制成为网络研究中的 重点。无线传感器网络节点数目多，节点资源有限，这都要求时间同步算法具有良 好的扩展性、低能耗性和简易性等特性。 在2 0 0 2 年8 月的h o t n e t s i 国际会议上，j e r e m ye l s o n 和k a yr o m e r 创造性的 提出了无线传感器网络时间同步算法的研究，并提出了r b s 时间同步机制。r b s 是基于接收者接收者模式的时间同步机制，主要利用无线数据链路层的广播信道特 性，当一个节点发送时间广播信息时，其他节点通过比较各自接受广播消息的本地 时刻来实现全网节点的时间同步【i7 1 。另外，t i n y s y n c 和t p s n 也是目前最常用 的时间同步机制。t i n y s y n c 的工作原理是在每次获得新的数据点时，首先与以 前的数据点比较，如果新的数据点计算出的误差大于以前数据点计算的误差，则抛 弃新的数据点，否则用新的数据点代替旧的数据点。t p s n 时间同步机制是基于发 送者接收者的同步模式，主要采用层次型网络结构，首先将所有的节点按照层次结 构进行分级，然后每个节点与上一级的一个节点进行时间同步，以此类推直到全网 的节点同步到同一个时间。 总之，无线传感器网络是应用相关的网络，每个不同的应用对时间同步有不同 的研究，因此对网络时间同步机制应结合特定的应用，以提高网络的性能。 ( 3 ) 节点定位 确定事件的地理位置和监测目的地点的信息是无线传感器网络的基本功能之 一，对网络的实际应用具有重要的意义，因此节点定位技术是无线传感器网络的关 硕士学位论文 m a s t e r st h e s i s 键技术之一【1 8 1 。传感器节点随机部署在地理区域内，节点能量，带宽和处理能力等 都很有限，因此要求定位算法具有容错性、鲁棒性和能量高效性。 随着无线传感器网络的广泛应用，对定位算法的研究也越来越深入，目前的算 法的研究大多数集中在对能耗、成本和精度等方面的研究。由于传感器网络是应用 相关的网络，各种应用的差别比较大，没有普遍适用的定位算法，对无线传感器网 络定位算法的研究应该从不同的应用着手，综合考虑节点的规模，成本以及系统对 定位精度的要求，来选择最适合的定位算法。 ( 4 ) 数据融合 在无线传感器网络中，根据研究发现节点的能量大部分消耗在信息的接收和发 送过程中。为了节省传感器节点的能量，延长网络的生命周期，在收集信息的过程 中，我们可以利用节点的本地计算和存储能力，对数据进行融合处理，去除冗余的 数据，减少数据量，从而提高数据的收集效率，节省网络的能量。 在无线传感器网络的各个协议层的设计中，协同考虑数据融合技术，也是当下 广泛使用的一种数据融合方式。在应用层设计中，利用数据分布存储的特点，逐步 的筛选数据，以此来去除冗余信息。在网络层路由算法设计中，将数据融合考虑到 节点的路由选取中，节点边传输数据边进行数据融合，以此来减少传输信息量，从 而节省节点能量【1 6 1 。另外，有些人还提出了独立的数据融合协议层，处于网络层和 数据链路层之间，通过减少m a c 层的发送冲突和头部开销来节省能量【1 9 1 。总之， 无线传感器网络是应用相关的网络，在无线传感器网络的设计中结合针对应用的数 据融合方法才能得到更好的发展。 ( 5 ) 应用层技术 应用层的任务是根据实际应用需要发布相关的监测任务，由多种实时应用的软 组成【2 们。无线传感器网络应用层的研究主要集中在不同应用系统的开发上，由于无 线传感器网络是以具体应用为背景的网络，因此在应用层的设计中将实际应用与网 络监控结合起来具有重大的意义。 1 3 本文的主要内容和组织结构 无线传感器网络的研究热点集中在如何有效的减少能耗，延长网络生命周期。 本文拟结合改进的路由算法和传输算法，利用跨层技术来提高网络的性能。最后对 该算法进行仿真实验，分析评估其有效性。主要章节安排如下： 第1 章绪论，介绍了本文的选题背景和课题意义，介绍无线传感器网络的结构、 特点和技术热点，并介绍了本文的主要工作及研究目标。 6 硕士学位论文 m a s t e r st h e s i s 第2 章无线传感器网络的路由和传输算法研究，主要介绍目前已有的路由算法 和传输算法，比较分析其优劣，为后面的研究做理论铺垫。 第3 章改进的分簇算法l e a c h d 的设计与实现，在经典分簇算法l e a c h 的 基础上提出了l e a c h d 。该算法考虑节点的分布密度，通过引入节点连通度、设 定成簇半径来均衡簇头节点的能量消耗，并在簇头之间采用多跳通讯机制来均衡网 络能量消耗。 第4 章基于分簇实时传输算法r t b c 的设计与实现，本章采用跨层技术将网络 层和传输层结合起来考虑网络的节能，提出分簇实时传输算法r t b c 。该算法采用 d i j k s t r a 算法找出簇头到基站的多条优化路径，综合路径拥塞情况在这些路径中找 到一条耗能最低并且实时性最优的路径，实现数据的实时传输。 第5 章总结，在上述研究的基础上总结全文，并提出进一步的研究思路和方向。 7 硕士学位论文 m a s t e r st h e s i s 第2 章无线传感器网络的路由和传输算法研究现状 传感节点由于体积和处理能力的限制，节能成为无线传感器网络技术研究的关 键点。据研究人员研究发现节点的能量大多数消耗在数据的传送过程中，因此整个 网络能量的节省可以从减少数据的传输时间和距离着手，如何设计高效的路由算法 和传输算法成为无线传感器网络的重点。目前的节能算法仅仅考虑网络层的节能或 者传输层的节能，其实将网络层和传输层结合起来考虑，能更有效的均衡网络的能 量消耗，更好的延长网络的生命周期【2 l j 。 2 1 路由算法的研究现状 根据国内外的研究现状，目前的无线传感器网络路由算法主要分为平面路由算 法和分层路由算法。典型的平面路由算法有泛洪路由算法( f l o o d i n gr o u t i n g ) 口2 1 、谣 传路由算 法( r u m o rr o u t i n g ) r 2 4 1 、定向扩散路由算 法( d i r e c t e dd i f f u s i o nr o u t i n g ) t 2 3 】和 g e a 算法( g e o g r a p h i c a la n de n e r g ya w a r er o u t i n g ) 2 5 1 ，典型的分层路由算法有 l e a c h l 2 6 、l e a c h c t 2 7 1 、d h c s l 2 7 和h e e d 2 引。 这些路由算法有其优缺点，并且针对不同的具体应用表现出不同的效果，他们 为无线传感器网络路由算法的发展方向提供了不同的思路，对后来的路由算法起到 了重要的启示作用。下面我们来进行简单的介绍。 2 1 1 泛洪路由算法( f l o o d i n gr o u t i n g ) 泛洪路由算法属于传统洪泛式路由算法，不需要维护网络拓扑和路由。节点在 收到消息后将数据包广播给邻居节点，反复执行直到消息到达目标区域或者消息跳 数达到最大值瞄】。 泛洪算法实现简单，数据随机传播，不需要任何机制来维护路由。正因为如此， 网络中的数据存在严重的重叠和内爆问题，损耗了大量的能量，影响了网络的生命 周期。 2 1 2 定向扩散路由算法( d i r e c t e dd i f f u s i o nr o u t i n g ) 定向扩散路由算法是一种典型的以数据为中心的基于数据查询的路由机制，其 工作原理图如下图2 1 所示，分为兴趣扩散、梯度建立和路径加强三个阶段，首先 s i n k 节点发布包含查询信息的兴趣消息，然后兴趣消息采用洪泛的方法在全网范围 内进行扩散发布查询任务，在兴趣消息传播的过程中，建立从数据源节点到汇聚节 8 硕士学位论文 m a s t e r st h e s i s 点的传输梯度，传感节点将采集到的数据沿传输梯度传送到汇聚节点 2 3 】。 oo 汇聚节点 滚( ) _ _ ，( ) _ - - - - - 3 汇聚节点 oo 图2 1 定向扩散路由机制 定向扩散路由算法主要以查询驱动网络，汇聚节点根据不同的应用需求指定不 同的查询任务，其独创性是平面路由算法的一个里程碑。但是在定向扩散路由算法 中为了适应网络的拓扑变化情况，周期性的进行兴趣扩散、梯度建立和路径加强操 作，在全网范围内进行兴趣泛洪传播，时间和能量上的消耗都是比较大的，而且在 数据持续传送的环境监测类型应用中得不到很好的发展。 2 1 3 谣传路由算法( r u m o rr o u t i n g ) 谣传路由算法也是以数据查询为驱动的平面路由算法。定向扩散算法需要经过 耗能的全网消息扩散才能确定一条高效的路径，因此在数据传送量较小或者已知事 情区域的网络中定向扩散算法就显得不经济，于是b o u l i s 等人提出了适合数据传送 量较小或者已知事件区域的谣传路由算法 2 4 1 。 谣传路由算法的基本原理如下图2 2 所示，代理消息沿随机路径向外扩散传播， 这些代理消息是由事件区域中的传感器节点产生的，与此同时由汇聚节点发送的查 询消息也沿随机路径传播，当这两种消息在传播过程中相遇时，也就形成了从事件 源节点到汇聚节点的传输路径 2 4 1 。 。 o 图2 2 谣传路由工作原理图 谣传路由算法实现简单，路由建立开销小，但是其随机生成传输路径，很可能 9 硕士学位论文 m a s t e r st h e s i s 不是最优传输路径，并且在路径的生成过程中有可以产生路由空洞。 2 1 4g e a r 路由算法( g e o g r a p h i c a la n de n e r g ya w a r er o u t i n g ) g e a r 路由算法是基于地理位置的数据查询驱动路由算法，其根据事件区域的 地理位置，采用估计代价值和实际代价值相结合的方法选择最优路径将查询信息传 送到目标区域，在目标区域中传播查询任务并采集任务数据【2 5 】。 g e a r 路由算法很好的利用节点已知地理位置的优势来制定路由机制，通过估 计代价值和实际能量值相结合的方法选择出最优的传输路径，很好的节省了网络的 能量消耗，是一种高效的路由算法。但是其需要节点进行g p s 定位，传感器节点价 格高，而且在传播查询信息过程中采用贪婪算法来寻找最优路径，有可能因为陷入 路由空洞而降低了路由效率。 2 1 5l e a c h 算法 l e a c h 算法是一种经典的路由算法，开启了分层路由算法的先河，后来的分层 算法都是在它的基础上发展起来的。其基本思想是通过随机循环选择簇首，将整个 网络的能量负载均衡地分配到每个传感器节点中，从而达到降低网络能量消耗的目 的。l e a c h 算法的工作过程分为初始化和数据传输两个阶段。 在初始化阶段，l e a c h 协议随机地选取若干个传感器节点作为簇首。选取的原 则是：传感器节点生成一个0 至l 之间的随机数，如果生成的随机数小于阀值t ( n ) ，则 该节点当选为簇首 2 6 1 。阀值t ( n ) 按公式2 2 计算： 7 _ ( 门) ： ? 7 ( 1 一p 【，m o d ( 1 p ) 】) ，”g( 2 1 ) 【o ，o t h e r w i s e 、。 其中p 表示簇头节点占所有节点的百分比，为当前循环次数，m o d ( 1 p ) 代表当 前一轮循环当中曾经当选过簇首的节点个数，g 是未当选过簇首的节点集合【2 6 1 。 在数据传输阶段，节点当选簇头后，通过广播方式传播自己成为簇头的消息， 非簇头节点根据收到的信息的强弱计算自己离簇头节点之间的距离，选择距离较小 的簇头节点作为自己的簇管理节点。簇内的所有节点按照t d m a 时隙向簇头发送数 据，簇头将数据融合后直接发送给汇聚节点( s i n k ) 。持续工作一段时间后，重新进 入新一轮的簇建立阶段和数据传输阶段。 l e a c h 算法是分层路由算法的里程碑，为无线传感器网络路由算法开辟了一个 新的研究思路。但是其采用随机选择簇头的方法，有可能将能量值较低的节点当选 为簇头，导致整个簇的信息丢失，而且其没有考虑成簇的均匀性，使网络区域中的 1 0 硕士学位论文 m a s t e r st h e s i s 簇头分布不均匀。后续的分层算法逐渐的考虑了以上这些问题。 2 1 6l e a c h c 算法 l e a c h c 算法是为了解决l e a c h 簇头分布不均匀而提出的分层路由算法。 其采用与l e a c h 算法相同的原理，它的改进之处在于采用集中式算法选择簇头。 在成簇阶段，每个节点将自身的地理位置和剩余能量汇报给汇聚节点，汇聚节点根 据节点的剩余能量值和地理位置等指标进行优化计算，选出合适的簇头，通过全网 广播的方式宣布哪些节点成为簇头节点【2 7 】。 l e a c h c 算法不仅促进了传感节点能量的均衡，而且改善了簇头分布不均匀 的现象。但是采用汇聚节点集中管理的方法对汇聚节点的能力有较大的要求，传感 器节点直接向汇聚节点发送自身信息需要消耗一定的通信能量。 2 1 7d c h s 算法 d c h s 算法是一种分布式的分簇算法。由于l e a c h 没有考虑簇头节点剩余能 量的问题，有可能将能量值较小的节点选取为簇头，影响网络的性能，于是h a n d y 等人提出了d c h s 算法，其簇头的选取中考虑了节点剩余能量因素，改进后的阀值 公式如下所示【2 7 】： t ( n ) = k n k r m o d ( n 七) 】) ( k ) ( 2 - 2 ) 其中删是节点的剩余能量值，邑懈是节点初始化时的能量值，为当前循 环次数。改进后的d c h s 算法虽然增加了能量值大的节点成为簇头的概率，均匀了 网络能量的消耗，但是其仍然采取随机选择簇头的策略，不能保证簇之间能量的负 载均衡，即各个簇由于簇内节点的分布密度不同而在能量消耗上有很大的差异。 2 1 8h e e d 算法 h e e d 算法是针对l e a c h 算法簇头分布不均匀而提出的分层路由算法。它利 用节点剩余能量和簇内平均可达能量两个标准来选取簇头节点，主要过程分为以下 三个阶段。 在初始化阶段，节点以不同的概率发送竞争消息，所有的节点设置一个初始化 概率c p , 竹b ，并按如下公式2 - 4 计算自身的概率明砌【2 明。 凹砌( ，0 ) = m a x c 胛b k ，) ( 2 - 3 ) 硕士学位论文 m a s t e r st h e s i s 其中明砌( ，0 ) 为节点在第r 轮第0 次迭代中成为簇首的概率，如删纠是节点 的剩余能量值，厶织是节点初始化时的能量值， 加是概率底线值。 在迭代阶段，节点按照以下公式2 - 5 进行迭代直到c 日砌( ，) = 1 ，迭代结束后 节点广播自己成为簇头的消息，其他普通节点收到消息后停止迭代【2 8 1 。 c 日删( ，j ) = 2 c h p 砌( r ，歹一1 ) ( 2 - 4 ) 在形成簇阶段，普通节点根据竞争阶段收集到的平均可达能量选择加入某簇。 h e e d 算法引入节点剩余能量和簇内平均可达能量两个标准来选取簇头节点， 一方面使能量值大的节点承担数据转发的任务，延长了簇的生命周期，另一方面考 虑了成簇后簇内的通讯开销问题，均衡了全网的能量消耗。 2 2 典型路由算法的性能分析与比较 定向扩散、g e a r 、l e a c h 和h e e d 等路由算法各有其优点和缺点，大多数 是针对特定的应用而设计的，有其特色和优势，因此我们不能绝对的判断孰优孰劣。 我们主要从生命周期和路由健壮性等多个方面对他们的特点进行了比较，如下表2 1 所示。 表2 1 路由算法性能比较表 泛 拓扑数据发路径选路由健算法复网络生 算法 机制送模式择壮性杂度命周期 f o o l d平面连续多跳好简单 较好 d d平面驱动多跳好较复杂好 r u m e r 平面连续多跳较好简单较好 g e a r 平面驱动多跳较好简单好 l e a c h 层