（计算机应用技术专业论文）无线传感网路由协议算法设计及应用研究.pdf

浙江大学硕士学位论文摘要 摘要 近十年来，国内外学者掀起了一股针对无线传感器网络的研究热潮。研究指 出无线传感网具有广阔的应用前景，但这些应用都需要建立在数据可靠传输的基 础之上，因此，基于具体应用的传感网路由协议设计是重点研究方向之一。本文 首先概述了静态传感网、移动传感网以及车载移动传感网三个领域的典型路由协 议算法，指出车载移动传感网是目前一个新的研究热点：然后提出了一种基于分 组转发状况的车载自组织网络路由协议算法，旨在根据分组在网络中的实际转发 状况来选择最优路径，该算法直接以分组的转发延迟及转发成功率为表征因素来 选择最优转发路径，n s 2 仿真结果显示，此协议可实现充分利用当前路况信息转 发分组，在平均延迟时间、分组丢失率、转发成功率等方面优于g p s r 、g p s r - l 协议算法；最后在对上述理论研究的基础上，分析了z i g b e e 协议栈采用的路由协 议，并对其进行了修改，然后设计了一个基于z i g b e e 传感网的智能照明控制系统， 测试结果表明该系统可以稳定工作于全自动状态，根据室内场景变化自动调整照 明模式。 关键词：无线传感网，移动传感网，路由算法，智能照明控制系统，z i g b e e 浙江大学硕士学位论文 a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，w i r e l e s ss e n s o rn e t w o r k ( w s n ) h a se m e r g e da sap r o m i s i n g f i e l do fr e s e a r c h ，l e a d i n gt oag r e a ta p p l i c a t i o np o t e n t i a l b u ta l lo ft h e s ea p p l i c a t i o n s h a v et or e l yo nr e l i a b l ed a t at r a n s m i s s i o n ，s ot h er o u t i n gp r o t o c o lf o rw s nb a s e do n s p e c i f i ca p p l i c a t i o n sh a sb e e nah o tr e s e a r c hf i e l d i nt h i st h e s i s ，a no v e r v i e wo ft h e r o u t i n ga l g o r i t h mf o rs t a t i cs e n s o rn e t w o r k s ，m o b i l es e n s o rn e t w o r k s ，a n dv e h i c u l a r m o b i l es e n s o rn e t w o r ki sg i v e nf i r s t ，a n dt h ea u t h o rp r o p o s e sap a c k e t d e l i v e r y c o n d i t i o na w a r er o u t i n g ( p c a r ) a l g o r i t h mf o rv e h i c u l a rm o b i l es e n s o rn e t w o r kw i t h t h ep u r p o s et ou s ed i r e c tm e t r i c st ob u i l dah i 曲q u a l i t yr o u t e i tu s e sp a c k e td e l i v e r y r a t i oa n da v e r a g ep a c k e td e l a yt i m ea st h em e t r i c sf o rc a l c u l a t i n go p t i m a lr o u t e s i m u l a t i o n sb a s e do nn s 2p l a t f o r ma r ea l s oc o n d u c t e d ，a n dt h er e s u l t sd e m o n s t r a t e t h a tp c a rs c h e m eo u t p e r f o r m sg p s ra n dg p s r - l ，i nt e r m so fa v e r a g ep a c k e td e l a y t i m e ，p a c k e tl o s sr a t i o ，a n dp a c k e td e l i v e r yr a t i o f i n a l l y , b a s e do nt h ep r e v i o u s t h e o r e t i c a lr e s e a r c h ，t h ea u t h o ra n a l y z e sa n dm o d i f i e st h er o u t i n gp r o t o c o li nz i g b e e p r o t o c o ls t a c k ，a n dt h e np r e s e n t sa ni n t e l l i g e n ti n d o o rl i g h tc o n t r o ls y s t e mb a s e do n z i g b e es e n s o rn e t w o r k ，t h ee x p e r i m e n ts h o w st h a tt h es y s t e mc a nw o r ka u t o m a t i c a l l y , a d j u s t i n gl i g h t i n gm o d ea c c o r d i n gt oi n d o o rs c e n ec h a n g e s 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 ，m o b i l ew i r e l e s ss e n s o rn e t w o r k ，r o u t i n g a l g o r i t h r n ，i n t e l l i g e n tl i g h tc o n t r o ls y s t e m ，z i g b e e 浙江大学硕士学位论文图目录 图目录 图2 1 一个m a s t e r - s i n k 的m g e o c a s t 路由一1 0 图3 1 移动节点和静态节点广播h e l l o 包示意图1 6 图3 2 分组格式图1 6 图3 3 移动节点进入新路段示意图1 7 图3 4 一个h e l l o 包广播周期内移动节点移动示意图1 9 图3 5 静态节点计算方向靠近目的静态节点的相邻路段示意图2 1 图3 6 图3 5 中路由静态节点r 2 的路段转发表2 3 图3 7 仿真地图( 杭州西湖附近) 2 5 图3 8 分组丢失率2 6 图3 9 分组平均延迟时间2 7 图3 1 0 分组转发成功率2 8 图4 1 系统层次结构图3 2 图4 2 房间自主控制子系统节点布置模型图3 3 图4 3 基于p i c l 8 f 4 6 2 0 单片机的调光电路原理图3 4 图4 4 系统控制流程图3 5 图4 5 判断人进出房间的控制流程图3 7 图4 6 照明灯以7 5 亮度点亮时各信号的波形示意图。3 8 图4 7 路由节点控制逻辑示意图4 0 图4 8p c 机用户界面图示4 1 图4 9 用户交互界面控制流程图。4 2 图4 1 0p c 机用户界面显示1 1 0 6 房间网络拓扑结构图示4 3 图4 1 11 1 0 6 号房间照明模式测试结果图4 4 图4 1 2 系统节点欠压、故障测试结果图4 5 i i i 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得逝姿盘堂或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：签字日期： 跏年弓月今日 浙江大学硕士学位论文第1 章绪论 1 1 课程背景 第1 章绪论 由众多传感器节点构成的无线传感器网络【”】( w i r e l e s ss e n s o rn e t w o r k s ， w s n ) 具有数据采集、通信、计算能力，通过无线方式连接，相互协作，与物理 世界交互，共同完成特定的应用任务。与传统的传感器相比，无线传感器网络节 点易于部署，即节点位置不需要事先确定或精心设计，允许任意放置，部署维护 成本低且具有较高的灵活性；并且可以放置在物理现象作用范围内，从而获得较 高的观察精度，具有较高的性价比；另外还具有计算能力，可进行相互协作，完 成传统传感器所不能完成的任务。传感器网络具有大量冗余节点，即使部分节点 失效，也不会影响整个系统的功能，因而具有较好的健壮性。 随着传感器技术、嵌入式计算技术、现代网络及无线通信技术、分布式信息 处理技术等的发展，具有无线通信能力、计算能力、存储能力和电池电源的无线 传感器节点变得越来越廉价。无线传感器网络开始被广泛配置在各种不同级别的 应用中，如医疗监护，农作物土壤监测、边境保护、航海航空探索、战场和敌方 环境侦察，以及各种各样的培训和监视应用如紧急预备和响应【4 】。无线传感器网 络作为一种多学科交叉的技术，已成为国内外科研学者关注的热点研究领域。 1 2 主要研究内容 上述无线传感网络的应用都是建立在数据可靠传输的基础之上，因此，路由 协议设计的优劣将直接影响无线传感器网络的性能。由于无线传感器网络节点具 有能量有限、计算能力有限和存储能力有限等特点，因此路由协议设计要求考虑 节省能源、具备数据融合能力、鲁棒性和可扩展性，节点不能执行太复杂的计算、 不能在节点保存太多的状态信息、节点间不能交换太多的路由信息【5 1 。目前，尚 未有通用的无线传感网路由协议，大部分协议都是针对具体的应用环境提出的， 如l e a c h 6 1 、g e a r 7 】等是适用于静态传感器网络的协议，d j e ae ta 1 改进的 浙江大学硕士学位论文第1 苹绪论 d d ( d i r e c t e dd i f f u s i o n ) 协议【8 1 是支持多个s i n k 节点移动的传感器网络协议， l y n nc h o ie ta 1 提出的m - g e o c a s t 协议 9 1 是支持所有节点移动的传感网路由协 议，以及v a l e r yn a u m o v e ta 1 提出的c a r 协议【1o 】则是适用于车载移动传感器网络 的路由协议。本文通过对当前无线传感器网络的路由协议进行分析总结，提出一 种新的基于分组转发状况的车载移动传感网路由协议，其特征是直接根据分组的 转发延迟时间及转发成功率来选择最优转发路径，n s 2 仿真结果显示其性能优于 对比协议，最后还分析了一个基于无线传感网的应用设计。 1 3 文章组织结构 本文的组织结构如下：第二章综述传感器网络路由协议算法，分别概述静态 传感器网络、移动传感器网络以及车载移动传感器网络三个领域的一些典型路由 协议算法；第三章提出一种新的车载移动传感器网络路由算法，分析该算法的设 计思想，并对其进行仿真验证；第四章描述传感器网络的一个应用示例，在对传 感网理论研究的基础之上，设计一个基于无线传感器网络的室内智能照明控制系 统；第五章总结全文。 1 4 本章小结 本章首先描述了课程的研究背景，阐述了无线传感器网络的发展现状；然后 提出了本文研究的主要内容：最后给出了文章的组织结构。 2 浙江大学硕士学位论文 第2 章无线传感网路由协议算法研究综述 第2 章无线传感网路由协议算法研究综述 学术界对无线传感器网络的研究首先起于静态传感器网络，随后是少量节点 ， 一 ， 移动( 通常是s i n k 节点或a n c h o r 节点) 的传感器网络，接着是所有节点移动的传 感器网络，近年来又兴起了车载移动传感器网络。上述每一类传感网都需要特定 的路由协议来保证数据可靠传输。本章将分别概述静态传感器网络、移动传感器 网络以及车载移动传感器网络各自领域内的典型路由算法。 2 1 静态传感器网络路由协议算法概况 早期提出的传感网路由协议基本上都属于静态传感器网络，如s p i n 1 1 】协议、 d d ( d i r e c t e dd i f f u s i o n ) 1 2 】协议、l e a c h 6 】协议、t e e n 1 3 】协议、g e a r 7 协 议、s a r 1 4 】协议以及s p e e d 1 5 】协议等。根据每种协议的特点，可将上述协议分 为四类：以数据为中心的路由协议，基于集群方式的路由协议，基于地理位置信 息的路由协议以及基于服务质量( q o s ) 的路由协议。 2 1 1 以数据为中心的路由协议 s p i n 协议是首个基于数据的路由协议。该协议为了提高网络带宽的利用率， 使用元数据( 即对原始感知数据的抽象描述) 交换节点感知事件的信息，而不是 直接使用原始感知数据。协议主要包括三种控制报文：a d v 、r _ e q 以及d a t a ， 其中a d v 报文用于广播元数据，r e q 报文用于向感知数据的节点发送开始传输 原始数据指示，d a t a 报文包含感知原始数据。当某节点感知到某事件以后，便 主动向邻居节点广播该事件的a d v 报文，网络中的其它节点查询保存的a d v 报 文，如有自己感兴趣的事件时，便广播r e q 报文，待源事件感知节点收到该报 文后，开始广播d a t a 报文。该协议通过使用元数据提高了网络带宽利用效率， 节约了部分能量，但是当源节点周围的邻居节点都不需要源节点的感知数据时， 将导致数据不能继续向外围转发，使得较远处感兴趣的节点无法得到数据。 浙江大学硕士学位论文 第2 章无线传感网路由协议算法研究综述 和s p i n 一样，d d 协议也是一种以数据为中心的路由协议。它的特点是运用 基于属性值对的命名机制来描述原始数据，相对s p i n 中用于广播元数据的a d v 报文，本协议利用i n t e r e s t 报文来广播由属性值对描述的数据。除了属性值对列 表外，i n t e r e s t 报文还包括原始数据上报间隔、持续传输时间以及节点的地理位置 等信息。当某s i n k 节点感知到事件后，它会广播包含描述事件的属性值对的 i n t e r e s t 报文，中间节点根据i n t e r e s t 报文包含的信息，创建包含数据上报率以及 下一跳节点等信息的梯度，建立多条指向s i n k 节点的路径。梯度建立完成后，通 过路径增强策略在源和s i n k 节点之间寻找一条梯度值最大的路径用于数据传输， 而其他路径可以作为备选路径，用来增加网络的健壮性。该协议使用查询驱动数 据传输方式及数据汇集减少了网络中的冗余数据流量，避免了保存全局网络信 息，但是它不适合需要数据连续传输的场合，如环境监测等。 2 1 2 基于集群方式的路由协议 基于集群方式的路由协议核心思想是将网络中节点按照不同的方法分成多 个簇，每个簇中选择一个簇头节点，通过簇头节点汇聚整合本簇内节点的数据， 并且通过簇头间直接通信，可以减少信息的发送频次，增加网络的生存时间。 l e a c h ( 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 ) 是一种典型的基于分簇方 式的路由协议，它通过采用机会均等循环选择簇头的方式，将整个网络中的能量 负荷较为均衡的分配到各个节点，从而避免了某单个节点能量过快消耗殆尽的现 象，延长了网络的生命周期。l e a c h 是一种完全分布式的路由协议，数据传输 延迟时间较小，但是由于假定每个簇头都能直接和s i n k 节点通信，使得其只能应 用于节点分布范围较小的场合。 t e e n 是一种偏向实时性的分簇路由协议，它是从l e a c h 协议的基础上改 进而来。相比l e a c h 协议，t e e n 选择好簇头以后，簇头节点还向簇内的节点 广播相关数据的绝对阀值( h a r dt h r e s h o l d ) 和相对阎值( s o f tt h r e s h o l d ) ，当某节 点检查到相应数据属性值高于绝对阀值时，便开始转发数据，另外，当再次检测 到数据属性值大于绝对阀值和相对阀值之和时，也启动数据转发过程。绝对阀值 4 浙江大学硕士学位论文第2 牵无线传感网路由协议算法研究综述 和相对阀值的引入显著减少了数据的传输次数，并且能够满足一些适时应用系统 的需求，但是如果某数据属性值总是低于绝对阀值，那么相应节点便不会启动数 据转发，一些感兴趣的节点便得不到此数据。 2 1 - 3 基于地理位置信息的路由协议 当知道网络中目的节点的地理位置信息时，便可以直接根据该信息进行数据 转发，并且可以选择合适的转发路径，避免了为寻找目的节点向整个网络中发送 广播包的现象。y uy e ta 1 等提出的g e a r 协议便是一种基于地理位置信息的路由 协议，它从d d 协议改进而来，d d 协议在路由建立过程中通过洪泛( f l o o d i n g ) 方式向整个网络发送查询命令，造成很大的路由开销，g e a r 根据特定的位置区 域按相应的方向传输查询命令，避免了洪泛广播。g e a r 协议要求每个节点都知 道自己的地理位置信息及剩余能量，并且能够通过h e l l o 包交换获取邻居节点 的地理位置及剩余能量，另外，还假定知道目的节点的地理位置信息。g e a r 协 议首先将查询命令向s i n k 节点的地理位置区域转发，s i n k 节点随后按照查询命令 的反向路径向查询节点转发数据。g e a r 避免了全网络报文广播，节省了网络带 宽，降低了节点能耗。 2 1 4 基于服务质量的路由协议 k s o h r a b ie ta 1 提出的s a r ( 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 ) 协议首次引入 了服务质量( q o s ) 的概念。该协议的主要思想是以s i n k 节点的邻节点为根，将 网络中的节点组合成多个树结构，当需要转发分组时，根据节点剩余能量、分组 优先级以及q o s 参数选择一条到目的节点的直达路径。该协议的特点是传输延迟 较小，能耗较低，但是需要维护节点的路由表和状态信息，网络的扩展性较差。 s p e e d 协议是另一种基于服务质量的路由协议。该协议主要由四部分组成： ( 1 ) 计算与邻居节点的通信延迟，主要是根据a c k 报文时间标志计算得到与邻 居节点的通信延迟时间，表示局部网络的负载状况，同时判断网络是否出现拥塞 现象；( 2 ) 使用s n g f ( g e o g r a p h i cn o n - d e t e r m i n i s t i cf o r w a r d i n g ) 算法寻找转发 路径，需要转发分组的节点首先根据与目的位置的距离将邻居节点分成比自己离 浙江大学硕士学位论文第2 章无线传感网路由协议算法研究综述 目标位置更近的节点集合和比自己离目标位置更远的节点集合，其中前者称为备 选转发节点集合( f c s ) ，然后根据节点的传输速率将f c s 中的节点再分为大于 预定传输速率阀值的节点集和小于预定传输速率阀值的节点集，最后按照一定的 选择机率在大于预定传输速率阀值盟节点集中选择一个为下一跳转发节点，如找 不到需要的转发节点，则执行第( 3 ) 步：( 3 ) 邻居信息反馈步骤，该步骤主要 是当邻居节点的传输速率都小于预定阀值时，计算邻居节点的分组转发率，为 s n g f 算法提供路径选择依据：( 4 ) 路由重选机制，用于通知源节点重新计算转 发路径。 通过对以上协议的分析，节点的能耗问题是静态传感器网络重点关注的问 题，多数协议通过减少网络中数据流量来节约能耗，另一方面，数据融合与汇聚 策略也出现在多个静态路由协议中，如l e a c h 、t e e n 等协议，但是上述静态传 感器网络协议并没有考虑安全机制，以及网络的可扩展性。 2 2 移动传感器网络路由协议算法概况 尽管早在1 9 9 1 年就有人提出了这个移动无线传感器网络( m o b i l ew i t l e s s s e n s o rn e t w o r k ，m w s n ) 的概念【1 6 】，相对于已经广泛应用的传统静态传感器网 络，移动无线传感器网络引起人们的广泛关注的时间并不长。移动传感器网络由 分散的移动节点组成，每个节点除了具有传统静态节点的传感、计算和通信能力 外，还具有一定的机动能力。对于一些危险场合和动态环境对象，如灾难现场紧 急救援、建筑物内危险品泄漏等，传统的无线传感器网络部署方法实现起来将十 分困难甚至失效。而利用移动传感器网络的机动能力，问题将会迎刃而解。配备 相关传感器的移动节点可以自动地在现场部署开来，按预定的程序取得一个合适 的分布密度和网络覆盖，及时传回实时数据。 节点移动使得移动传感器网络比传统静态传感器网络拓扑结构变化更为频 繁，假设节点以连续随机方式的移动，整个网络拓扑结构随时会发生变化，进而 导致通信联系变得不稳定，使得原来用于静态传感器网络的路由协议和m a c 层 协议不能直接用于移动传感器网络。 6 浙江大学硕士学位论文第2 章无线传感网路由协议算法研究综述 移动传感器网络根据节点的移动性可分为两类：只有单个或者少数节点移动 的传感网和所有传感器节点都移动的传感网。下面分别概况针对这两类网络的路 由协议【4 1 。 2 2 1 支持单个或者多个s i n k 移动的路卣协议 这类协议多是在原有静态传感器网络协议基础上加以改进以适应s i n k 的移 动。典型的应用就是对定向扩散d d ( d i r e c t e dd i f f u s i o n ) 协议的改进 8 , 1 7 1 。c i n t a n a g o n w i w ae ta 1 在d d 协议的基础上，提出了一种基于单个s i n k 移动的路由 算法【1 7 1 。当s i n k 通过直线移动的时候，它向邻居节点广播兴趣消息。传感器节点 接收到兴趣消息，并有可能把消息再发给它们自己的邻居节点。当节点采集的数 据与s i n k 的兴趣消息匹配时，每个传感器节点将开始向移动s i n k 转发数据。在节 点数据转发时，移动节点有可能已经移出了该节点的传输范围，这就会导致数据 包丢失。解决方案就是采用回执来确保s i n k 已经成功收到了数据包，传感器节点 只有在收到来自s i n k 的回执消息时才发送其他的数据包。d j e ae ta 1 对d d 协议 进行了扩展【8 】，提出了一个支持多个移动s i n k ( 在文献 8 】中把移动s i n k 称为d a t a m u l e ) 移动的路由算法。无论是单个移动s i n k 还是多个移动s i n k ，以上文献都是 应用于对时间延迟不敏感的场合中。为了收集数据，传感器节点必须等待移动s i n k 到达它的传输范围之内时才能发送数据，所以以上协议延迟时间较长。 s h u a ig a oe ta 1 提出了一种基于数据平衡的能量有效通信协议【1 8 】。该协议针 对大范围内的无线传感器网络，并且节点密度高，只有一个移动s i n k ，移动s i n k 周期性的按照固定的路径和速度运动，并且移动s i n k 的能量、存储空间和计算资 源不受限。在该算法中，数据平衡信息被扩散到监视区域用来控制从传感器收集 到的数据总量以避免能量浪费。仿真结果显示，该协议在数据平衡率、网络生命 周期和能量消耗平衡率方面有较好的表现。 a k i n a l i se ta 1 提出了三个用于收集w s n 移动数据的协议1 9 1 。第一个是简 单的被动数据收集算法，也就是说，节点一直等待，直到收到来自移动s i n k 的信 标消息才发送数据，这种技术显然可以减少能量消耗，因为只需要单跳即可把数 7 浙江大学硕士学位论文第2 章无线传感网路由协议算法研究综述 据转发给移动s i n k 。由于节点等待移动s i n k 到达它的传输范围内可能需要较长时 间，所以这种办法不适用于一些有实时性要求的应用；第二个协议考虑m w s n 中同时存在移动s i n k 和静态s i n k ，为了收集数据，建立一个以s i n k 为根的有限传 播树，每个s i n k 广播信标消息，收到信标的节点将根据预先设定的规则来决定是 否更新它的父节点，每个节点沿着传播树把数据传送到对应s i n k ，当一个节点停 止接收信标时，它将缓存所有的数据并等待另一个信标消息，否则，当定时时间 到时，传感器节点将初始化进入新的树；第三个方案目的是在多个s i n k 之间协调， 以更好的在网络中分布移动s i n k ，基本上，每个s i n k 都要通过检查是否存在其他 s i n k 来修正自己的移动轨迹，避免靠近其他s i n k ，因此在整个网络中移动s i n k 可 以更好的分布。 以上文献描述的基于移动s i n k 的路由协议原理基本是一致的，即移动s i n k 在整个网络中移动时连续的广播信标消息，传感器节点周期性的监听无线通道来 检查有无移动s i n k 在附近。在第一个周期中，传感器节点只是检查移动s i n k 进入 传送范围内的频率和滞留时间；在第二个周期，当s i n k 已经广播了信标消息，每 个在传输范围的节点开始进行冲突监测，然后把包含有节点位置和在第一个周期 中收集的测量值的数据包发送给s i n k 。移动s i n k 将获得整个网络的全局图，当在 s i n k 的传输范围内有多个节点时，它用这条消息建立一个通信优先权。之后，移 动s i n k 给所有它已知的在传输范围内的节点发送一个唤醒信号。较高的优先权将 先给那些快要离开s i n k 的传输范围内的节点。而且，节点可以预测什么时候s i n k 有可能在附近并开始监听无线通道。这种基于移动s i n k 的路由协议在节省能量方 面显然是非常有效的，因为当节点不在移动s i n k 的传输范围内时，它会保持睡眠 状态，缺点就是假设移动s i n k 经过整个网络时每次路径都是固定的。因此需要较 长的延时时间，不适用于对实时性要求高的场合。 一些对实时性要求较高的场合，如紧急预备和敌方环境侦察，对w s n 的路 由协议提出了新的挑战。路由协议必须为数据传播提供快速和可靠的技术。 r i c h a r dw ne ta 1 针对实时性要求高的应用提出了采用移动s i n k 的解决方案 ( m d c p e q 协议) 1 2 0 。m d c p e q 协议应用多个移动数据收集器( m d c ，m o b i l e 8 浙江大学硕士学位论文第2 章无线传感网路由协议算法研究综述 d a t ac o l l e c t o r s ) 周期性的广播信标。接收到信标的传感器节点将加入m d c 的簇， 并且为了转发数据包到m d c 而更新它们的路由信息。同样建立根在s i n k 的传播 树，不同于a k i n a l i se ta 1 提出的采用跳数的方法【1 9 1 ，m d c p e q 协议传感器节点 用信标信号的强度来实现简单且有效的路由重建( 切换) 。网络中同时拥有静态 s i n k 和移动s i n k ，当一个节点传输数据时，首先路由到移动s i n k 。如果附近没有 移动s i n k ，将采用到静态s i n k 的路由代替。这样可以确保总是存在有效的路由， 避免了传感器节点必须等待移动s i n k 到达的问题。因此，该协议几乎不需要额外 的延时，具有良好的实时性。仿真结果表明引入m d c 可以显著降低网络中流量 负荷和节点能量消耗。 2 2 2 支持所有传感器节点移动的路由协议 同支持移动s i n k 的路由协议相比，支持所有传感器节点都移动的路由协议很 少，因为所有节点都无规律的移动，导致网络的拓扑结构实时动态变化，拓扑结 构难以预测，路由转发必须考虑节点的位置变化。 l y n nc h o ie ta 1 针对m w s n 中任意节点在任意时间都可以移动的网络情况， 提出了一个新的几何路由协议( m g e o c a s t ) 【9 1 。m g e o c a s t 可以很好的支持节点 移动和定位服务，并可以消除出现路由空洞的可能性。在有多个移动s i n k 的情况 下，m g e o c a s t 选择其中一个作为m a s t e rs i n k ，m a s t e rs i n k 的任务是收集数据、提 供定位服务、向所有节点传播服务器信息。只有m a s t e rs i n k 需要向所有节点广播 它的位置。所有的节点都可以用简单的几何转发向m a s t e rs i n k 发送消息。 m g e o c a s t 采用两种办法来解决路由空洞问题：首先，通过从定位更新中得到的 历史路径发现一个新的路径，这称为p a t hh i s t o r yf o r w a r d i n g ，其次，如果几何路 由和路径历史转发都不行，m g e o c a s t 还可以通过广播对砸q 消息来找到一条到 达目的地的新路径。因此，m g e o c a s t 可以完全解决空洞问题。如图2 1 所示，有 三个源节点和两个目的地，每个源节点用贪心转发法向m a s t e rs i n k 直接发送消息， m a s t e rs i n k 从这些源收集所有的消息并把他们转发到其它的s i n k 。为了完成转发 给其它s i n k 的任务，m a s t e rs i n k 需要跟踪其它s i n k 的位置。 9 浙江大学硕士学位论文 第2 章无线传感网路由协议算法研究综述 分组转发路径 位置信息更新路径 图2 1 一个m a s t e r - s i n k 的m - g e o c a s t 路由 y a n r e ne ta l 。提出的协作能量有效的拓扑控制协议( c o e t c ) 【2 l 】，目的是 在移动传感器网络( m w s n ) 中取得能量效率。( t c ) 拓扑控制技术是指维持这 样一种结构，即支持能量效率路由和改进整个网络性能前提下，允许每个无线节 点在它的传输范围内局部调节，选择特定的邻居进行通信。移动性对t c ( 拓扑 控制) 的影响是双重的：增加了消息开销( 尤其是移动性较高的场景中) 和非均 匀的节点空间分布。c o e t c 协议采用计算几何理论技术，具有以下特性：能 量效率。可以确保计算得到的路由离能量利用最佳的路由相差最多只是一个常数 因子。节点稀疏性。在给定网络中，有一个边界的线性数值，可以使得在节 点移动情况下，找到路径和维护路由路径的任务变得简单，并且能够减少通信开 销。约束节点度。该特点可减少网络瓶颈和邻居信号干扰。运行在分布式 模式下。每个接点可利用邻居节点提供的信息进行协作的计算可扩展的路由表。 适应移动环境。该特性可以确保移动环境下，拓扑结构只需较少维护。该算 法在网络生命周期和和支持移动性方面胜过其它现有算法和协议。存在的缺点就 是假设每个节点的通信范围是一个圆形的区域，而在实际网络应用中，通信范围 1 0 浙江大学硕士学位论文 第2 章无线传感网路由协议算法研究综述 是各式各样的。 t a i j u n gc h a n g e ta 1 提出的c e e r ( c o l o r - t h e o r yb a s e de n e r g ye f f i c i e n tr o u t i n g ) 算法【2 2 】，通过比较临近传感器节点的r g b 颜色值，选择一条基于能量感知的较 优路径，而且，c e e r - 没有拓扑空洞问题。该算法是基于c d l ( ar a n g e - f r e e c o l o r - t h e o r y b a s e dd y n a m i cl o c a l i z a t i o na l g o r i t h m ) 【2 3 1 定位算法的，在c d l 算法中， 一个传感器节点的位置用一组r g b 值表示。用已知节点的r g b 颜色值，通过服 务器上传感器节点位置数据库表可以找到一个节点的最可能在的位置。为了跟踪 传感器节点的位置，需要经常更新每个节点的r g b 颜色值并且把更新内容传递 到服务器。用电池供电的节点经常的更新并且报告自己的位置，能量消耗很快并 且浪费网络带宽。c e e r 算法中，通过比较r g b 值，选择距离锚点( a n c h o r ) 较 近的簇成员作为路由选择可能的下一跳。在所选的簇成员中，拥有最高能量层次 的传感器节点被选择为下一跳。 y o u n g b a ek o n ge ta 1 提出一种采用贝叶斯规则( b a y e s r u l e ) 的簇算法【2 4 1 ， 基于传输能量层次的最优化，该算法可以通过软件计算统计来确定节点传输能量 层次，可以有效的节省能量。适用于节点分布不均匀的网络，包括移动传感器网 络。 需要指出的是，以上文献研究中，路由协议基本都只针对低速移动的节点， 当节点处于高速运动时，如在道路上奔驰的汽车，这些协议都会出现相应的不足， 因此，针对节点高速移动的w s n 路由协议还有待进一步研究。 2 3 车载移动传感器网络路由协议算法概况 车载移动传感器网络又称为车载自组织网络( v e h i c u l a ra dh o cn e t w o r k 蝌e t ) ，它将行驶在道路上的每一个车辆看成是集成了各种传感器件的移动节 点。作为智能交通系统( i n t e l l i g e n tt r a n s p o r t a t i o ns y s t e m ，i t s ) 中的一项关键技术， v a n e t 有助于改善车辆行驶过程中的安全性；能够减少道路拥塞，方便驾驶员 寻找到更优的行驶路径：还便于实现信息的共享，比如驾驶员可以查询某一机构 当前是否开放，该处是否有停车位等信息。其次，由于上述应用都需要建立在车 浙江大学硕士学位论文第2 章无线传感网路由协议算法研究综述 辆之间，或者车辆与路边设施之间通信的基础之上，因此，怎样寻找并维护一条 高质量的传输路径是对v a n e t 路由协议的根本要求。 由于车辆高速移动性、分布不均匀、运动行为受交通环境的限制等因素， v a e n t 具有网络拓扑结构变化频繁、传输信号受干扰大、网络易于断裂等固有 特性。不过，v a e n t 也有一些好的特性，如不受能源供给、信息存储空间以及 设备计算能力等限制，可以应用全球定位系统( g p s ) 、数字地图等一些辅助设备。 这些特性对v a n e t 路由协议的设计有着重要影响。本节将概述当前典型的 v a n e t 路由协议。 在所有基于v a e n t 研究的路由协议当中，g p s r t 2 5 】是较早提出的，它的局限 性在于未考虑道路交叉口处高大建筑物等障碍物对射频信号的干扰，以及贪婪转 发进入局部最优时自动转换到边界转发模式并不适合v a n e t 。随后，在g p s r 协议的基础上，r 。s 。a d i t y ae ta 1 提出了g p s r - l t 2 6 1 协议，根据两个邻居节点移动 速度，计算得到它们在射频信号覆盖范围内的有效存在时间，并以此时间设置定 时器，然后和h e l l o 包广播定时器一起来判断分组转发时邻居节点的位置，例 如当h e l l o 包广播定时器超时时，如果有效存在时间定时器也超时，表示两个 节点已经脱离了射频信号覆盖范围，该协议改进了g p s r 邻居节点的选择策略， 但并没有改进路由进入到局部最优时的策略：l o c h e r tce ta 1 提出的g p c r l 2 7 】 协议要求将分组转发到道路交叉口处的节点，协议给出两种判断节点是否位于交 叉口方法，一是每个节点定期广播自身位置和所有邻居节点的位置，如果某个节 点的两个邻居节点，在它们各自的邻居表中并没有将对方列为邻居节点，则认为 此节点位于交叉口附近；二是计算所有邻居节点位置的相关因子，如果有某两个 邻居节点位置相关因子接近于0 ，则认为此节点位于交叉口附近，该协议采用受 限有贪婪转发策略，优先选择位于交叉口附件的节点为下一跳转发节点，当进入 局部最优时，首先将分组转发到交叉口附近的节点，然后采用右手规则选择新的 转发路段，因此，g p c r 的核心思想并没有脱离g p s r 协议；j e r b ie ta 1 提出的 g y t a r t 2 8 】协议也是通过将分组转发到道路交叉口来解决g p s r 边界转发的问题， 它根据相邻交叉口之间的车流量密度及交叉口离目的节点的距离来综合计算下 1 2 浙江大学硕士学位论文第2 章无线传感网路由协议算法研究综述 一跳目的交叉口，但是如何有效跟踪车流量的密度，以及两个交叉口之间的车辆 是否较均匀分布、有无出现网络断裂等问题并不能准确表示。 g s r 【2 9 1 和a s t a r 3 0 协议根据d i j k s t r a 算法选择最优路径，前者直接根据节 点所带交通地图计算一条源到目的节点的最短路径，后者根据道路中公交车的运 行线路数为每一条道路赋一权重值，权重值越大表示该路段运行的公交线路越 多，然后应用d i j k s t r a 算法计算源到目的节点的最优路径。然而，在v a n e t 中， g s r 采用最短路径表示最优转发路径并不准确，而a s t a r 总是选择那些公交线 路较多的路径，忽略了公交线路不多的路径，造成网络负载不均衡。 g v g r i d 【3 1 】与h a i a g r i d e 3 2 】是两个基于网格的v a n e t 路由协议，通过将源到 目的节点之间的区域划分成网格来改进贪婪转发策略。g v g r i d 根据节点的移动 情况及交通信号灯的变换规律，选择节点能够以相似速度行驶的系列网格为最优 路径，认为这样的路径出现网络断裂的可能性最小，该协议根据节点的移动信息 选择最优路径，随着节点的移动，源和目的节点之间可能出现新的最优路径，但 是协议在路由修复过程中并没有重新计算最优路径，而是认定第一次计算的路径 一直是源到目的节点的最优路径。h a r p i a g r i d 以源到目的节点间的道路交叉口为 基准划分网格，然后由源节点在所有相邻的且位于源到目的节点之间的网格中选 择离目的节点最近的节点为下一跳转发节点，当节点较为稀疏时，某节点在相邻 网格中找不到下一跳转发节点时，自动回退到和当前网格不在同一行、同一列的 先前转发过的网格，由该网格重新计算下一跳转发节点，这种路由修复方法会增 大分组转发延迟时间，因为v a n e t 中节点的高速移动性，遇到问题的网格可能 很快就有了合适了转发节点，将分组回退到较远处的网格开销过大。 v a l e r yn a u m o ve ta l 。提出的c a r ( 1 0 】协议的特点是将目的节点位置发现和寻找 源到目的节点之间的连通路径接合起来，并且提出了哨兵节点的概念，用于告知 邻居节点目的节点的移动状态，接收到通知的邻居节点被选为转发节点时，将分 组头中目的节点的地址修改为最新状态，另外，该协议h e l l o 包广播周期可以 根据相邻节点的个数动态变化，不足之处是会将一些不必要的节点加入到转发路 径中，增加了分组转发跳数。a c a r 3 3 1 协议根据路段传输质量及每个节点的分组 浙江大学硕士学位论文第2 章无线传感网路由协议算法研究综述 错误率( p a c k e te r r o rr a t e ，p e r ) 来选择转发路径，其中路段传输质量由车流量密 度及交通信号灯变换周期来评估，其n s 2 t 3 4 】仿真结果显示，在分组转发成功率、 吞吐量及分组延迟时间等性能指标上优于c a r 协议。 以上路由协议有一个共同特性，即都是根据一些间接表征因素( 如源到目的 节点的最短距离、车流量密度等) 来判断最优转发路径，但是这些表征因素还都 停留在理论假设阶段，能否反应真实的路况、表示实事上最优的路径并无定论。 因此，本文提出了一种基于分组转发状况的车载自组织网络路由协议( a p a c k e t d e l i v e r yc o n d i t i o na w a r er o u t i n ga l g o r i t h m f o rv e h i c u l a rm o b i l es e n s o r n e t w o r k ，p c a r ) ，旨在根据分组在网络中的实