（通信与信息系统专业论文）无线传感器网络路由技术的研究.pdf

南京邮电大学硕士研究生学位论文 摘要 摘要 由传感器、微处理器和无线通信接口组成的无线传感器网络( w s n ) 是- 1 7 日益引起 人们研究兴趣的技术，它广阔的应用前景更使得它在医疗卫生、环境监测和军事等领域得 到了飞速发展。传统的计算机网络技术中业已成熟的解决方案可以借鉴到无线传感器网络 中来，但是基于无线传感器网络自身的用途和优点，开发专用的通信协议和路由算法已经 成为了当前无线传感器网络领域内急待研究的课题。 本文主要讨论了w s n 路由协议的特点，集中研究了分层路由协议的典型算法：低功耗 自适应集群分层路由( l e a c h ) 。通过分析其原理和优缺点，使用o m n e t + + 软件对其原 算法仿真的基础上进行一些改进，然后比较原始路由算法与改进后的仿真结果并得出结 论。 本文分为五个部分：第一章是绪论，主要阐述无线传感网络的基本知识，引出其路由 协议的概述以及与其他无线网络的比较；第二章是对无线传感网络的路由协议的原理阐 述、分类比较并选定l e a c h 协议进行仿真；第三章说明了原始l e a c h 算法的两种实现 ( 分布式和集中式) 存在的弊端，提出仿真改进的策略，包括s o l a r - a w a r e 算法、簇头增减 算法、五算法、t l l e a c h 算法等，分别阐述了它们的原理和改进的目的；第四章介绍了 仿真平台o m n e t + + 软件的构架和仿真实现的过程，并主要介绍路由协议仿真模型的建立 和流程。对每种改进策略分别进行仿真，再根据仿真运行生成的图表数据比较原始算法和 添加改进策略后的变化，从而得出结论并分析是否符合该算法的理论期望值；第五章是结 束语。本文中对无线传感网络的发展方向，路由技术与其他关键技术的结合、z i g b e e 协议 下路由的实现等进行了讨论。最后总结了论文工作，提出下一步的工作方向。 南京邮电大学 硕士学位论文摘要 学科、专业： 工学通信与信息系统 研究方向： i p 与宽带网络 作者：2 0 0 4 级研究生 杨婷婷指导教师叶玲 题目：无线传感器网络路由技术的研究 英文题目：t h er e s e a r c ho fw i r e l e s ss e n s o rn e t w o r kr o u t i n g t e c h n o l o g y 主题词： k e y w o r d s ： 无线传感器网络路由算法l e a c h 算法 分布式和集中式l e a c h w i r e l e s ss e n s o rn e t w o r k r o u t i n ga l g o r i t h m l o we 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 d i s t r i b u t e da n dc e n t r a l i z e dl e a c h a b s t r a c t t h et e c h n o l o g yo fw i r e l e s ss e n s o rn e t w o r k ( w s n ) w h i c hi sc o m p o s e db ys e n s o r ，m i c r oc h i p a n dw i r e l e s st r a n s m i s s i o ni n t e r f a c eh a sa r o s et h ep e o p l e i n t e r e s t ，s oi ti sd e v e l o p i n gr a p i d l yi n t h ef i e l do fm e d i c a l ，e n v i r o n m e n ti n s p e c ta n dm i l i t a r ya f f a i r s i nt h e o r y ，t h et r a d i t i o n a ln e t w o r k t e c h n o l o g yc o u l db eu s e d i nt h ew s n b u tb a s e do nt h eu s ea n ds t r o n g p o i n to fw s n ， r e s e a r c h i n go ni t so w n t r a n s m i s s i o np r o t o c o la n dr o u t i n ga r i t h m e t i ci sb e c o m i n gm o r ea n dm o r e u r g e n t t h ep a p e rd i s c u s s e st h ec h a r a c t e r i s t i c so fw s nr o u t i n gp r o t o c o l ，e s p e c i a l l yt h et y p i c a l a r i t h m e t i co fm u l t i 1 a y e rr o u t i n gp r o t o c o l ：l o we 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 b y a n a l y z i n gi t st h e o r ya n dc h a r a c t e r i s t i c ，t h ep a p e ru s e ss o f t w a r eo m n e t + + t os i m u l a t et h e a r i t h m e t i ca n dd o e ss o m ei m p r o v e m e n t a tl a s ti tc o m p a r e st h er e s u l t so fb e f o r ea n da f t e rt h e i m p r o v e m e n t ，a n dm a k e st h ec o n c l u s i o n t h i sp a p e ri sm a d eu po ff i v ep a r t s ：t h ef i r s tc h a p t e ri st h ei n t r o d u c t i o n ，i tm a i n l ye x p o u n d s t h eb a s i ck n o w l e d g eo ft h ew i r e l e s ss e n s o rn e t w o r k ，t h e ns u m m a r i z e sw s nr o u t i n gp r o t o c o la n d c o m p a r e sw i t ho t h e rw i r e l e s sn e t w o r k s ；t h es e c o n dc h a p t e rd e s c r i b e s t h et h e o r yo fr o u t i n g p r o t o c o l si nd e t a i l ，s o r t st h e ma n dc o m p a r et h e ma n dc h o o s et h el e a c h t ob es i m u l a t e d t h e t h i r dc h a p t e re x p l a i n st h ed e f i c i e n c i e so ft h et w oo r i g i n a la l g o r i t h m so fl e a c h ( d i s t r i b u t e d l e a c ha n dc e n t r a l i z e dl e a c h ) ，a n db r i n g sf o r w a r dt h em e t h o dt oc h a n g eo ri m p r o v e t h e b e r e r m e n t sa r e i n c l u d i n g s o l a r - a w a r e a l g o r i t h m ，t h e c l u s t e ri n c r e a s ea n dd e c r e a s e ， a r i t h m e t i c ，t l l e a c ha n ds oo n i nt h i sp a r t ，t h ep a p e rm a k e su sc l e a ra b o u t t h ep r i n c i p l ea n d p u r p o s eo ft h e s ea l g o r i t h m s ，t h ef o r t hc h a p t e ri sa b o u tt h es i m u l a t i o n a tf i r s t ，t h es o f t - w a r e o m n e t + + i si n t r o d u c e df r o mi t sa r c h i t e c t u r et ot h er e a l i z a t i o no fs i m u l a t i o n a n dt h e ni tm a k e s u sk n o wt h es i m u l a t i o nm o d u l e so fl e a c ha n dh o wt h e yc o u l db ei n t e g r a t e da n dt h ed e t a i l e d p r o c e s si ns i m u l a t i o n a tl a s t ，i ts i m u l a t e st h ei m p r o v e m e n ta r i t h m e t i c ss e p a r a t e l y ，a n d t h eb a s e d o nt h ec h a r t sc a m eo u tf r o mt h es i m u l a t i o n ，t h ep a p e ra n a l y s e st h ed i f f e r e n tm o v e m e n to ft h e l i n e sb e t w e e nb e f o r ea n da f t e rt h ei m p r o v e m e n ta n dt h e nc o m et ot h ef i n a lc o n c l u s i o n ，i n c l u d i n g i ft h er e s u l t sa c c o r dt ot h ep r e s u m e dt h e o r y t h ef i f t hc h a p t e ri st h ee n d i n g i nt h i sp a r tt h ep a p e r d i s c u s s e st h ed e v e l o p m e n to ft h ew s n ，t h ec o m b i n a t i o no fr o u t i n ga n do t h e rt e c h n o l o g i e s ，a n d t h er e a l i z a t i o no fr o u t i n ga r i t h m e t i ci nz i g b e ep r o t o c 0 1 i nt h ee n d ，t h i sp a p e rs u m m a r i z e st h e t h e s i sa n dp u tf o r w a r dt h en e x tw o r kt od o 1 1 南京邮电大学 硕士学位论文摘要 学科、专业： 工学通信与信息系统 研究方向： i p 与宽带网络 作者：2 0 0 4 级研究生 杨婷婷指导教师叶玲 题目：无线传感器网络路由技术的研究 英文题目：t h er e s e a r c ho fw i r e l e s ss e n s o rn e t w o r kr o u t i n g t e c h n o l o g y 主题词： k e y w o r d s ： 无线传感器网络路由算法l e a c h 算法 分布式和集中式l e a c h w i r e l e s ss e n s o rn e t w o r k r o u t i n ga l g o r i t h m l o we 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 d i s t r i b u t e da n dc e n t r a l i z e dl e a c h 南京邮电大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得南京邮电大学或其它教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示了谢意。 研究生签名：1 3 期： 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留 本人所送交学位论文的复印件和电子文档，可以采用影印、缩印或其 他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一 致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布 ( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权 南京邮电大学研究生部办理。 研究生签名：书驴嘻冬垂导师签名：立也日期： 南京邮电大学硕士研究生学位论文第一章w s n 基本知识 第一章w s n 基本知识 1 1 无线传感网络( w s n ) 简介 近年来随着微型制造技术、无线通信技术和电池技术的进步，促使低成本、低功耗的 微型无线传感器的大规模生产制造成为可能，这些微型无线传感器能同时具有数据采集、 无线通信和信息处理的能力。无线传感器网络就是将成百上千的此类传感器节点布置在一 个特定的区域内而形成的网络，它们通过特定的协议高效、稳定、正确的自组织起来，协 同工作完成某项应用任务。人们依靠无线传感器网络可以实时监测外部环境，实现大范围、 自动化的信息采集。它具有快速构建、部署方便的特点，不易受到目标环境的限制，特别 适合布置在电源供给困难的区域或人员不易到达( 环境恶劣地区、敌军阵地等) 的区域，可 应用在军事侦察、环境监测、医疗监护、空间探索、城市交通管理、仓储管理等领域，应 用前景非常巨大。 无线传感器网络研究最早来源于军事领域，1 9 7 8 年卡内基梅隆大学就在美国国防高 级研究项目署( d a r p a ) 的资助下成立了分布式传感器网络工作组( d i s t r i b u t e ds e n s o r n e t w o r ks h o p ) ，专门研究以无线传感器网络为基础的军事监视系统。但是由于当时技术条 件的限制，研究和应用的范围十分有限。进入到2 1 世纪，随着技术水平的大规模提高， 当前对无线传感器网络的研究与开发已成为目前信息领域的一个热点，有越来越多的研究 机构和公司正加入到这方面的研究工作中来。国际上的一些大型研究项目包括有：加州大 学洛杉矶分校w i n s 网络，几乎涵盖了从信号处理到网络协议的所有研究；加州大学伯克 利分校的p i c o r a d i o 项目，专注于信道选择、冲突避免的媒介访问层( m a c ) 协议；麻省理 工大学的l a m p s 项目，利用节点簇算法来尽量降低功耗。还有其它众多的研究项目如 t e r m i n o d e s ，m a n e t 等。国内的很多科研机构和企业也都介入到无线传感网络节点及关键 技术的研究中来，部分产品已应用到实际生活中。【l 】 南京邮电大学硕士研究生学位论文 第一章w s n 基本知识 1 2w s n 主要技术特点 1 2 1w s n 的网络结构及软硬件构成 所有的无线传感器网络的组织结构类似，一个早期的典型应用是军事上的侦测系统， 用来探测某一区域内的敌军行动。如。图1 1 所示，利用飞机投掷或其它合适手段按一定密 度布置传感器节点在所要侦测的范围。传感器节点自动启动，并采集周边的敌方情报( 温度、 湿度、声音强度、物体移动等) 。由于传感器节点功率的限制，一般传递的距离有限，因此 它会寻找临近的一个节点用来作为传输中继，如图1 1 中传感器a 将通过传感器b 、c 的 帮助将侦测数据传送至网关节点d 处。网关节点是一个较为特殊的节点，视侦测范围的大 小无线传感器网络可以有一个或多个网关。网关应该拥有相对较强的处理器和较大的存储 器空间，它的功能是首先对网络中普通节点( 如节点a 、b 、c ) 汇总过来的传感数据进行一 些初步的处理( 如计算、压缩、去除冗余等) ，然后与某- # 1 - 部网络( 如互联网) 相联，将侦 测的数据发送给我方指挥部的监控中心。通过这种手段，我方就可以远程精确掌握敌方情 报，而无需付出人员损失的代价。 明天节点 o1 冬感器诲点 图1 1 无线传感器网络的组织结构 无线传感器网络的传感器节点个数通常很多，它们不仅体积小、成本低，另外还要求 传感器节点功耗非常低，以满足用电池即可维持长时间的工作状态。因此这些特点决定了 对传感器节点的设计需要在尽可能简单的情况下满足应用需求。无线传感器节点是由硬件 层和软件层共同配合完成任务( 见图1 2 ) 。 硬件层一般都包括以下四个单元：供电单元、数据采集单元( 包括传感器和a d 模数 转换器件) 、数据处理单元( 包括存储器和微控制器) 、无线通信单元。微控制器作为传感器 2 南京邮电大学硕士研究生学位论文第一章w s n 基本知识 节点运转的“心脏 ，在上面运行着嵌入式系统软件，从而对另外三个单元的工作进行控 制。在硬件的选取上，尽量采用低功耗器件，还可以考虑在无数据采集和无数据通信的时 候命令微控制器进入“睡眠”状态并可切断无线通信单元的部分电源，从而降低功耗。 软件层用来控制硬件层，是整个传感器的“大脑”，除了最基本的数据采集和发送之 外，根据应用的场合，还需要实现关于网络拓扑、自组织、路由选择、能耗节约、错误处 理、可靠性保证等一系列的算法与设计。对于一些简单的应用可以使用单一循环逻辑的软 件来完成。而一些复杂性较高的应用场景就有必要使用针对无线传感器网络特点的嵌入式 操作系统。这类操作系统，除了要满足对于资源有限、可移植性、实时性等方面的需求外： 重点还要考虑节能性的需求，另外使用事件驱动的方式也可以适应无线传感器网络以数据 流为中心的特点。无线传感器网络的软件层会包括三个层次：硬件抽象层、系统服务层和 应用层。硬件抽象层实现对硬件平台( 供电、数据采集、数据处理和无线通信单元) 的抽象， 为上层屏蔽底层硬件细节，简化系统平台移植。系统服务层包括通信服务、传感服务、能 耗管理服务、实时内核四部分，在这个层次中除了实现操作系统如任务调度、信号量等内 核服务外，还将完成各种路由、安全算法的实现，并支持各类通信传输协议。应用层是由 用户根据具体应用的需要定义，利用系统服务层提供的接口，能方便的设计出上层软件。 1 1 ：二二二二二二二 麴酉互 二二二二 图1 - 2 传感器节点的组成 1 2 2w s n 的关键技术及难点 ( 1 ) 能源问题：一般认为短距离的无线低功率通信技术最适合传感器网络使用，其应用 包括用于商业、工业、军事的反馈控制系统和环境监视。在无线传感器网络中除了 少数节点需要移动之外大部分节点都是静止的。因为它们通常运行在人无法接近的 南京邮电大学硕士研究生学位论文第一章w s n 基本知识 恶劣甚至危险的远程环境中能源无法替代，采取有效的策略延长网络的生命周期就 成为无线传感器网络的核心问题。【2 】 ( 2 )网络控制和路由：网络需处理动态变化的各种资源，比如能量、带宽和处理功率等， 系统应根据需要自动改变其配置。由于通信链路的不可靠和信号衰减，软件和系统 设计应保证要求的可靠性。这就要研究网络的大小、链路和节点数量等以保证充足 的后备。通过配置充足的节点提供充足的路由，并由相应的算法发现正确的路由， 才能保证具有生存性和适应环境的网络。另外，设计网络也要调查其他参数，如网 络大小、节点密度等参数，这些参数影响延迟、可靠性和能量消耗等性能。【2 】 ( 3 ) 数据链路层：由于网络无线信道的特性，环境噪声、节点移动和多点冲突等现象在 所难免，能量问题又是传感器网络的核心性问题。数据越多能量损耗越多，影响了到 整个传感器网络的生存时间。所以该层除了要完成传统网络数据链路层的成帧、差 错校验、帧检测的功能外，最主要的是设计一个适合于传感器网络的介质访问控制 方法，以减少传感器网络的能耗。【2 】 ( 4 ) 数据融合：在w s n 的应用环境中，节点需要采集温度、湿度、光、压力等多种环 境参数，单个节点往往不能完成对环境目标的测量和识别，单一传感器获得的仅是 环境特征的局部、片面的信息，它的信息量是非常有限的。而且每个w s n 节点还 受到自身品质、性能及噪声的影响，采集到的信息往往是不完善的，带有较大的不 确定性，甚至是错误的。这就需要研究和开发一定的算法，使具有一定属性的多个 w s n 节点采用通过交换信息，对所获得的数据进行加工、汇总和过滤，以事件的形 式得到最终结果，即w s n 数据的汇聚。 ( 5 )网络节点必须明确自身位置才能详细说明“在什么位置或区域发生了特定事件 ， 实现对外部目标的定位和追踪。而且节点的位置信息还可用于提高路由效率，为网 络提供命名空间，向部署者报告网络的覆盖质量，实现网络的负载均衡和网络拓扑 的自配置。而人工部署和为所有网络节点安装接收器都会受到成本、功耗、扩展性 等问题的限制，必须采用其它方法实现自身定位。 1 2 3 w s n 的路由协议概述 在无线传感网络中，由于每个节点携带的能量都是有限的，因距离的关系不可能将采 集到的数据直接向控制台( 又称s i n k 节点或b s 基站) 传送，就需要路由的策略。 w s n 与传统固定网络有很大的不同。与w s n 最为相似的是移动自组织网络( m a n e t ： m o b i l ea dh o en e t w o r k s ) ，尽管二者都是无线自组织多跳网络，但差异很大：w s n 节点不移 4 南京邮电大学硕士研究生学位论文第一章w s n 基本知识 动或很少移动，而m a n e t 节点移动性强，节点的频繁移动造成网络拓扑结构的频繁变化： w s n 的数据包更小，因而数据传输开销更大；w s n 节点的计算、存储、通信能力更有限： w s n 节点因能量耗尽而易失效；w s n 节点通信高能耗，数据计算低能耗，而这种差异在 m a n e t 中并不重要：w s n 一般独立成网，主要用于监测功能，是以数据为中心的网络， m a n e t 则能为分布式应用提供互联、计算能力；w s n 节点可达上千，分布更密集，远大 于m a n e t 的几十个节点；w s n 网络流量具有m a n y t o o n e 和o n e t o m a n y 的特点；w s n 节点合作完成监测任务，与应用高度相关，数据相关性较大：w s n 节点一般没有统一编址 ( 在某些应用中可对节点编址) 。【3 】此外，传感器网络还具有以下主要的显著特征： _ 传感器网络是以数据为中心( d a t a c e n t r i c ) 的网络，整个网络相当于分布式的网络 数据库，要查询的数据分布在所有或部分节点中。传感器网络中每个传感器节点同时具有 终端系统和路由器两者的作用：传感器节点接收汇聚点的查询或控制命令，实现信息的采 集、处理和收发功能；同时，处理和转发收到的来自其他节点的数据，实现路由的功能。 由于传感器网络关注的是具有某种特性的数据，加之传感器节点数目巨大和节点放置的随 机性，传感器节点可以不采用与i p 地址类似的全局编址，而是使用仅在局部能够区分的 标号进行标识。 _ 传感器网络是与应用相关的网络。传统网络发展的趋势是电信网、计算机网以及电 视网的逐步融合，而传感器网络是针对某个或某些应用而专门设计的。传感器网络中邻居 节点的数据具有相似性，它们监测到的事件可能是同一个事件( 如火灾) ，从不同监测点 得到同一事件的相关数据，因此这些数据存在信息的冗余性。在数据传输路径上的中间传 感器节点需要针对具体应用，对收到其他节点转发来的数据以及本身采集的数据进行融 合、缓存和转发，减少冗余数据的发送，以求有效地节省网络资源，特别是能源。【4 】 传感器节点的能量支持和通信带宽都是受限的，而且网络中部署的节点数量巨大。这 给传感器网络的设计和管理提出了许多重大的挑战，而路由协议的设计是其重中之重。然 而对于传感器网，路由协议设计是很具挑战性的。首先，节点没有全球唯一的标识符，传 统的互联网路由协议无法应用在传感器网络中；第二，传感器网络中的所有节点都是源节 点，向唯一的目的节点s i n k 发送数据：第三，由于在被测对象内部或附近部署了大量的节 点，它们采集到的数据是相同或相近的。这就需要路由协议具有数据融合能力，以节约电 能，提高带宽利用率；第四，节点具备的处理能力，电能和存储能力是很有限的，需要强 大的资源管理和任务调度能力。 南京邮电大学硕士研究生学位论文第一章w s n 基本知识 1 3 本论文的主要工作 ( 1 ) 对无线传感网络基本原理进行阐述的基础上，详细研究各种无线传感网的路由 算法，并分析它们的优缺点。 ( 2 ) 以一种典型的路由算法( l e a c h ) 为研究重点，分析其原理，提出改进的几种策 略和具体算法。 ( 3 ) 本文在0 m n e t + + 仿真平台上建立无线传感网模型，实现了l e a c h 路由协议和对它 的两类改进，并分析仿真结果，得出结论；最后结合z i g b e e 标准，提出下一步的工作方 向。 6 南京邮电大学硕士研究生学位论文 第二章w s n 路由协议的分类和比较 第二章w s n 路由协议的分类和比较 2 1 路由的作用和分类 w s n 路由协议负责在s i n k 节点和其余节点间提供数据传输路径。由于w s n 与应用高 度相关，单一的路由协议不能满足各种应用需求，因而人们研究了众多的路由协议。为揭 示协议特点，我们根据路由协议采用的通信模式、路由结构、路由建立时机、状态维护、 节点标识和投递方式等策略，运用多种分类方法对其进行了分类。由于研究人员组合多种 策略来实现路由机制，故同一路由协议可分属不同类别。 ( 1 ) 根据传输过程中采用路径的多少，可分为单路径路由协议和多路径路由协议。单路径 路由节约存储空间，数据通信量少；多路径路由容错性强，健壮性好，且可从众多路由中 选择一条最优路由。 ( 2 ) 根据路由建立时机与数据发送的关系，可分为主动路由协议、按需路由协议和混合 路由协议。主动路由建立、维护路由的开销大，资源要求高：按需路由在传输前需计算路 由，时延大；混合路由则综合利用这两种方式。 ( 3 ) 根据是否以地理位置来标识目的地、路由计算中是否利用地理位置信息，可分为基 于位置的路由协议和非基于位置的路由协议。有大量w s n 应用需要知道突发事件的地理 位置，这是基于位置的路由协议的应用基础，但需要g p s 定位系统或者其他定位方法协助 节点计算位置信息，成本较高。 ( 4 ) 根据是否以数据来标识目的地，可分为基于数据的路由协议和非基于数据的路由协 议。有大量w s n 应用要求查询或上报具有某种类型的数据，这是基于数据的路由协议的 应用基础，但需要分类机制对数据类型进行命名。 ( 5 ) 根据节点是否编址、是否以地址标识目的地，可分为基于地址的路由协议和非基于 地址的路由协议。基于地址的路由在传统路由协议中较常见，而在w s n 中一般不单独使 用而与其他策略结合使用。 ( 6 ) 根据路由选择是否考虑q o s 约束，可分为保证q o s 的路由协议和不保证q o s 的路 由协议。保证q o s 的路由协议是指在路由建立时，考虑时延、丢包率等q o s 参数，从众 多可行路由中选择一条最适合q o s 应用要求的路由。 7 南京邮电大学硕士研究生学位论文第二章w s n 路由协议的分类和比较 ( 7 ) 根据数据在传输过程中是否进行聚合处理，可分为数据聚合的路由协议和非数据聚 合的路由协议。数据聚合能减少通信量，但需要时间同步技术的支持，并使传输时延增加。 ( 8 ) 根据路由是否由源节点指定，可分为源站路由协议和非源站路由协议。源站路由协 议节点无须建立、维护路由信息，从而节约存储空间，减少通信开销。但如果网络规模较 大，数据包头的路由信息开销也大，而且如果网络拓扑变化频繁，将导致路由失败。 ( 9 ) 根据路由建立时机是否与查询有关，可分为查询驱动的路由协议和非查询驱动的路 由协议。查询驱动的路由协议能够节约节点存储空间，但数据时延较大，且不适合环境监 测等需紧急上报的应用。【3 】 由此可见，路由协议的种类非常多，每种协议的侧重点各有不同，在不同的网络应用 环境中各有利弊。重要的是根据研究的重点找到合适的路由协议，完成无线传感网络的 数据传输。 2 2 常用路由算法的原理分析 2 2 1 基于能量的路由 能量路由根据传感器节点的可用能量( p a ：p o w e ra v a i l a b l e ) 或传输路径上链路的能 量需求来选择传输路径。在图2 1 所示网络中，链路旁的a 表示在该链路上发送数据需要 的能量。下面列举从源节点到汇聚点的路径： 路径1 ：源节点b a - 汇聚点，路径上节点p a 之和为4 ，发送需要的能量之和为3 ； 路径2 ：源节点c b a - 汇聚点，路径上节点p a 之和为6 ，发送需要的能量之和为6 ； 路径3 ：源节点d 汇聚点，路径上节点p a 之和为3 ，发送需要的能量之和为4 ； 路径4 ：源节点f e 汇聚点，路径上节点p a 之和为5 ，发送需要的能量之和为6 ； 南京邮电大学硕士研究生学位论文 第二章w s n 路由协议的分类和比较 e ( p a 习】 即a = 舳 图2 1 能量路由算法示意图 目前提出的能量路由有以下方法： 一最大p a 路由：选取从数据源到汇聚点所有路径中节点p a 之和最大的路径。图2 1 中路径2 是最大的，但路径2 包含了路径1 ，因不是高效的而被排除，选择路径4 ； _ 最小耗能路由：选取从数据源到汇聚点所有路径中节点耗能之和最少的路径，图2 1 中为路径l ； 最少跳数路由：选取从数据源到汇聚点跳数最少的路径，图2 1 中为路径3 ； 一最小节点可用功率值最大的路由：即使所选取的路由里节点的最小可用功率有最大值， 图2 1 中为路径3 。 以上能量路由算法需要节点知道网络的全局信息，而传感器网络的能源约束使得节点 只能获取局部信息，因此它们只是理想情况下的路由方法。【4 】 2 2 2 基于协商的路由 路由协商协议( s p i n ：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 ) 假设所有传感 器节点都可能是希望获得数据的汇聚节点，每个传感器节点知道自己是否需要数据或是否 在数据源到汇聚节点的路径上。s p i n 路由是对传统洪泛( f l o o d i n g ) 路由的改进。为了减 少节点的能量消耗，传感器节点在发送数据前先进行协商，仅把数据发送到需要的相邻节 点，同时采用称为“元数据”( m e t a d a t a ) 的描述符减少冗余信息。 s p i n 协议使用a d v 、r e q 和d a t a 三种类型的消息( 图2 2 ) 。s p i n 采用三次握 手方式，当节点有新的数据时，向其所有邻居广播简短的a d v 消息，其中包括d a t a 的 描述符( s t e p l ) ；当邻居节点收到这个广播消息时，如果对这个数据感兴趣，先检查自己 是否已经有该数据，没有就发送r e q 消息请求新的数据( s t e p2 ) ；源节点在收到r e q 消 息后，发送数据给请求节点( s t e p3 ) 。这些邻居节点重复以上过程( s t e p4 , 5 ，6 ) ，从而 可以使网络中所有对该数据感兴趣的传感器节点都能获得它。该协议的优点在于简单，节 9 南京邮电大学硕士研究生学位论文第二章w s n 路由协议的分类和比较 点仅需要知道它的邻居节点，无需其他拓扑信息。【4 】 n o r e q u d 呐 o o c 2 ) o r e q o 飞o o ， o t 【3 n o o a t & v o h o o o j t t h 国a t h 0 、0 。o 。6 ， 图2 2 ：s p i n 协议基本操作 、 这是第一个基于数据的路由协议。该协议以抽象的元数据对数据进行命名，命名方式 没有统一标准。和洪泛的路由协议相比，有效地节约了能量。但其缺点是：当产生或收到 数据的节点的所有邻节点都不需要该数据时，将导致数据不能继续转发，以致较远节点无 法得到数据，当网络中大多节点都是潜在s i n k 点时，问题并不严重，但当s i n k 点较少时， 则是一个很严重的问题；且当某s i n k 点对任何数据都需要时，其周围节点的能量容易耗尽。 2 2 3 基于层次的路由 l e a c h ( 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 - 低能耗自适应分簇结构) 的核心思 想是基于分簇的路由，它包括周期性的循环过程。每轮循环分为簇建立阶段和稳定的数据 通信阶段，后者所用的时间较长。在簇建立阶段，相邻节点动态地自动形成簇，随机地产 生簇首。在数据通信阶段，簇内节点把数据发给簇首，簇首进行数据融合并把结果发送给 汇聚点。由于簇首需要完成数据融合、与汇聚点通信等工作，因此簇首的能量消耗非常高。 各节点需要等概率地轮流担任簇首，这样才能使网络中所有节点比较均衡地消耗能量，有 利于延长整个网络的生存期。l e a c h 协议的特点是分层和数据融合。分层利于网络的扩 展性，数据融合能够减少通信量。 基于能量效率的阈值敏感传感器网络协议( t e e n ：t h r e s h o l ds e n s i t i v ee n e r g ye f f i c i e n t s e n s o rn e t w o r kp r o t o c 0 1 ) 把传感器网络分为节点周期性发送信息的主动网络( p r o a c t i v e n e t w o r k ) 和及时监测突发事件的反应网络( r e a c t i v en e t w o r k ) 。在反应网络中，人们只对 属性值高于给定阂值的数据感兴趣。t e e n 协议是应用于反应网络的对l e a c h 协议的改 进，其核心操作过程为：在簇首选举以后，簇首会把绝对阈值和相对阈值两个参数广播给 其他成员。传感器节点持续地采集数据，当采集的数据第一次大于绝对阈值，节点把数据 记录下来，同时发送给簇首：在以后时间内，这个节点只有满足采集的数据大于绝对阈值， 而且与前一次记录结果之差大于相对阂值时，才对数据进行记录并发送给簇首。t e e n 协 1 0 a ， ， o “怕佴 澎谚 南京邮电大学硕士研究生学位论文 第二章w s n 路由协议的分类和比较 议的改进操作有两个好处：第一，对于突发事件能够及时响应；第二，对于持续的突发事 件，相邻两次数据之差在不大于阈值时，无需不断地发送数据，从而得以减少通信流量。 基于能量有效性的汇聚协议( p e g a s i s ：p o w e r e f f i c i e n tg a t h e r i n g i ns e n s o r i n f o r m a t i o ns y s t e m ) 是在l e a c h 的基础上发展而来。不同的是p e g a s i s 中节点只同距它最 近的相邻节点通信，而且每一轮只选一个节点作为聚类首领与接收器通信。节点通过发送 能量递减的测试信号发现距离自己最近的相邻节点，从而建立一条包含网络中所有节点的 “链 ( c h a i n ) 如图2 - 3 ： c l _ c 2 _ c 3 一c 4 卜c 5 1 l b s 图2 - 3 ：p e g a si s 数据传输链形成示意图 当聚类首领选定后，链两端的节点向链中的下一个节点发送数据，接收到数据的节点将自 己的数据和接收到的数据融合，然后将融合的数据发送到下一个节点，如此一直到聚类首 领，聚类首领把接收到的两组数据和自己的数据融合后发送给接收器节点。相比 l e a c h ，p e g a s i s 中的节点之间的平均通信距离较短，聚类首领最多只接收两个消息，而且每 一轮只有一个节点与接收器节点通信，因此p e g a s i s 比l e a c h 节能。 2 2 4 基于查询的路由定向扩散 定向扩散是一种基于查询的路由机制。汇聚点发出查询消息，形成反向的从数据源到 汇聚点的数据传输梯度。数据沿着梯度传送到汇聚点。其中的数据采用 方式进 行命名，所有节点都是应用感知( a p p l i c a t i o n a w a r e ) ，能够进行数据融合。定向扩散包括 以下周期性的基本操作过程( 参见图2 - 4 ) ： 镑镑 ( 1 ) 兴趣传播( 2 ) 梯度建立 oo ；| 乏点獗o时_ 占挈急 o0 ( 3 ) 增强路径 图2 4 ：定向扩散的基本操作 路径建立：汇聚点向网络中所有节点通过网络广播任务，任务用含有任务类型、数据 发送速率、时间戳等参数的兴趣包( i n t e r e s t ) 来描述。这些兴趣包是探测性的，对节点发 送数据速率的要求比较低。每个节点缓存接收的兴趣包，通过记录相应的发来兴趣包的邻 南京邮电大学硕士研究生学位论文第二章w s n 路由协议的分类和比较 居节点的兴趣包数据来建立梯度。随着兴趣包在整个网络的传播，就建立了从数据源节点 到汇聚点的数据传输梯度。 数据发送：当节点采集到匹配查询的数据时，通过梯度路径发向汇聚点。由于可能从 多个邻居节点收到兴趣包，( 中间) 节点会向多个邻居节点发送数据，汇聚点( 或中间节 点) 可能收到经过多个邻居节点发来的相同数据，中间节点需要实现数据融合并丢掉已发 送的信息。 增强路径：汇聚点在收到这些低速率数据后，向数据到达最快的邻居节点发送增强消 息，增强消息表示汇聚点要求高速率发送数据。相应邻居节点按照同样的方式，依次传递 增强信息给其邻居节点，直到到达数据源，这样将构建数据发送的增强路径。数据以后就 通过增强路径发送给汇聚点。定向扩散周期性的自动形成增强路径，由于节点能量或拓扑 结构等变化，在不同周期内的增强路径可能不同。源到汇聚点的多数数据通过增强路径传 送，从而减少非增强路径上的节点能量的消耗。【4 】 该协议采用多路径，健壮性好；使用数据聚合能减少数据通信量；s i n k 点根据实际情 况采取增强或减弱方式能有效利用能量；使用查询驱动机制按需建立路由，避免了保存全 网信息，但不适合环境监测等应用。而且，g r a d i e n t ( 梯度) 的建立开销很大，不适合多 s i n k 点网络；数据聚合过程采用时间同步技术，会带来较大开销和时延。 此外，还有多径路由、能量感知路由、q o s 路由等算法，实现起来较为复杂，在此不 作详细介绍。 2 3 选择l e a c h 协议的理论基础 由于w s n 资源有限且与应用高度相关，研究人员采用多种策略来设计路由协议。其 中好的协议具有以下特点：针对能量高度受限的特点，高效利用能量几乎是设计的第一策 略；针对包头开销大、通信耗能、节点有合作关系、数据有相关性、节点能量有限等特点， 采用数据聚合、过滤等技术；针对流量特征、通信耗能等特点，采用通信量负载平衡技术， 针对节点少移动的特点，不维护其移动性：针对网络相对封闭、不提供计算等特点，只在 s i n k 点考虑与其他网络互联；针对网络节点不常编址的特点，采用基于数据或基于位置的 通信机制；针对节点易失效的特点，采用多路径机制。通过对当前的各种路由协议进行分 析与总结，可以看出将来w s n 路由协议采用的某些研究策略与发展趋势： ( 1 ) 减少通信量以节约能量。由于w s n 中数据通信最为耗能，因此应在协议中尽量减少 数据通信量。例如，可在数据查询或者数据上报中采用某种过滤机制，抑制节点上传不必 1 2 南京邮电大学硕士研究生学位论文第二章w s n 路由协议的分类和比较 要的数据：采用数据聚合机制，在数据传输到s i n k 点前就完成可能的数据计算。 ( 2 ) 保持通信量负载平衡。通过更加灵活地使用路由策略让各个节点分担数据传输，平 衡节点的剩余能量，提高整个网络的生存时间。例如，可在层次路由中采用动态簇头；在 路由选择中采用随机路由而非稳定路由；在路径选择中考虑节点的剩余能量。 ( 3 ) 路由协议应具有容错性。由于w s n 节点容易发生故障，因此应尽量利用节点易获得 的网络信息计算路由，以确保在路由出现故障时能够尽快得到恢复；并可采用多路径传输 来提高数据传输的可靠性。 ( 4 ) 路由协议应具有安全机制。由于w s n 的固有特性，其路由协议极易受到安全威胁， 尤其是在军事应用中。目前的路由协议很少考虑安全问题，因此在一些应用中必须考虑设 计具有安全机制的路由协议。 ( 5 ) w s n 路由协议将继续向基于数据、基于位置的方向发展。这是由w s n 一般不统一 编址和以数据、位置为中心的特点决定的。 在本次研究中，主要以网络的能量消耗为侧重点评估无线传感网络的特性。 无线通信中，能量消耗e 与通信距离d 存在关系：e =