（计算机应用技术专业论文）能量均衡的传感器网络分簇路由协议研究.pdf

哈尔滨理工大学工学硕上学位论文 能量均衡的传感器网络分簇路由协议研究 摘要 无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n ) 是当前国际上备受关注的 由多学科交叉的前沿研究热点领域。由于无线传感器网络通常由大量密集的传 感器节点构成，节点的能源、计算能力和带宽都非常有限，传统的无线路由协 议不适合无线传感器网络。因此，设计出能够有效节约能源、延长网络生命周 期的路由协议成为了无线传感器网络研究中的热点。 本文通过对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 - b a s e dh i e r a r c h y ) 路由算法 的研究，对其簇头选择算法进行了改进。改进后的l e a c h 簇头选择算法，在 基于对节点的剩余能量感知的基础上，选举能量较充足的节点担当簇头，而且 通过对地理位置的感知，在传感器网络内较均匀地选择簇头。仿真结果显示， 改进后的算法较之l e a c h ，可以在节点间更有效地均衡能量的消耗，并且提 高了网络的生存时间。 在对l e a c h 算法改进的基础上，通过对现有传感器网络路由协议的分析 与研究，针对传感器网络中节点能量消耗不均衡致使无线传感器网络寿命缩短 的问题，提出了一种能量均衡的传感器网络分簇路由协议( e n e r g yb a l a n c i n g c l u s t e r i n gp r o t o c o lf o rw i r e l e s ss e n s o rn e t w o r k s ，e b c p ) 。e b c p 协议采用正交基 站的方法来构建均衡的网格，进而在网格中选举簇头，以使簇头均匀地分布在 网络内；并采用非均匀分簇的策略解决传感器网络中的热区问题，以平衡簇头 间的能量消耗：同时，e b c p 使用动态变化的阈值来衡量节点能量，采用多跳 的方式将数据传送给基站。 最后，本文在分析n s 2 仿真软件的结构、原理、仿真方法的基础上，在 n s 2 仿真平台上实现了e b c p 协议。仿真结果表明，e b c p 协议有效地提高了 能量负载的均衡度，与l e a c h 和h e e d 相比，它可以使网络被完全覆盖的时 间更长，同时e b c p 有效地延长了网络的存活时间。 关键词无线传感器网络；路由协议；分簇；能量均衡 哈尔滨理t 大学工学硕士学位论文 r e s e a r c ho ne n e r g y - b a l a n c e dc l u s t e r i n gr o u t i n g p r o t o c o lf 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 a tp r e s e n t ，w s n ( w i r e l e s ss e n s o rn e t w o r k s ) c r o s s e db ym a n ys u b j e c t sa r et h e a d v a n c e dr e s e a r c hh o t s p o tf i e l di nt h ei n t e r n a t i o n a la r e a t h en u m b e ro fs e n s o rn o d e s i nw s ni sn u m e r o u sa n das i n g l en o d ei se x t r a o r d i n a r i l yl i m i t e di nr e s o u r c e s ，s ot h e i m p o r t a n ta i mo fd e s i g n i n gr o u t i n gp r o t o c o lo fw s n i st or e d u c et h eo v e r a l le n e r g y d i s s i p a t i o ni nt h en e t w o r k sa n dt om a x i m i z et h el i f e t i m eo fw s n t h i st h e s i sa n a l y z e st h el e a c hr o u t i n gp r o t o c o l ，a n di m p r o v e st h ec l u s t e r h e m se l e c t i o na l g o r i t h m b a s e do na w a r e n e s so ft h er e s i d u a le n e r g ya n dt h el o c m i o n o fe a c hn o d e ，t h ei m p r o v e dl e a c hs e l e c t sc l u s t e rh e m sa c c o r d i n gt ot h e i rr e s i d u a l e n e r g ya n dd i s t r i b u t e st h e i rc l u s t e rh e a d se q u a l l yi nw s n t h es i m u l a t i o nr e s u l t s d e m o n s t r a t et h a tt h ei m p r o v e da l g o r i t h mi sc a p a b l eo f d i s t r i b u t i n ge n e r g yd i s s i p a t i o n m o r ee f f e c t i v e l ya n de n h a n c i n gt h en e t w o r kl i f e t i m ec o m p a r e dw i t hl e a c h b a s e do nt h ei m p r o v e da l g o r i t h mo fl 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 - b a s e dh i e r a r c h y ) a n dt h es t u d yo fe x i s t i n gr o u t i n gp r o t o c o l so fw s n ，t h i st h e s i s p r o p o s e sa ne n e r g yb a l a n c i n gc l u s t e r i n gp r o t o c o lt os o l v et h ep r o b l e mt h a te n e r g y c o n s u m p t i o na m o n g s e n s o rn o d e si sn o tb a l a n c e di nw s n t h ep r o t o c o ld i v i d e st h e w h o l ew s ni n t ob a l a n c e d 鲥d s ，w h e r ec l u s t e rh e a d sa r ee l e c t e d ，s oc l u s t e rh e m sc a n u n i f o r m l yb ed i s t r i b u t e di nt h ew h o l en e t w o r k s i ne b c p , u n e v e nc l u s t e r i n gs t r a t e g y i su s e dt os o l v e “h o tz o n e ”p r o b l e m a tt h es a m et i m e t h ed y n a m i cc h a n g et h r e s h o l d o fn o d e se n e r g yi su t i l i z e d e b c pe m p l o y sm u l t i h o pr o u t i n gs t r a t e g yt ot r a n s f e rd a t a t os i n k a tl a s t ，b a s e do nt h ea n a l y z i n go ft h ep r i n c i p l ea n ds t r u c t u r eo fn s 2 ，e b c pi s i m p l e m e n t e di nn s 2 t h es i m u l a t i o nr e s u l t sd e m o n s t r a t et h a te b c pi sc a p a b l eo f d i s t r i b u t i n ge n e r g yd i s s i p a t i o nm o r ee f f e c t i v e l ya m o n gt h es e n s o rn o d e sa n da c h i e v e s a ni m p r o v e m e n to nt h en e t w o r kl i f e t i m ec o m p a r e dw i t hl e a c ha n dh e e d 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 g ，e n e r g y - b a l a n c e d - 1 1 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文能量均衡的传感器网络分簇路 由协议研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立 进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人己 发表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中 以明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：歹两日期：a , , e 1 9 3b e 。日 哈尔滨理工大学硕士学位论文使用授权书 能量均衡的传感器网络分簇路由协议研究系本人在哈尔滨理工大学攻读 硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理 工大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔 滨理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论 文和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、 缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密口，在年解密后适用授权书。 不保密吝。 ( 请在以上相应方框内打) 作者签名：爹爹丽 导师签名： 衣灭 日期：0 d 听年了月a d 日 日期：a 。吖年j 月p 日 哈尔滨理t 大学t 学硕十学位论文 1 1 研究背景与意义 第1 章绪论 随着通信技术、嵌入式计算技术和传感器技术的飞速发展和日益成熟， 具有感知能力、计算能力和通信能力的微型传感器开始在世界范围内出现。 由这些微型传感器构成的传感器网络引起了人们的极大关注。传感器网络在 军事国防、工农业、城市管理、生物医疗、环境监测、抢险救灾、防恐反 恐、危险区域远程控制等许多重要领域都有潜在的使用价值，已经引起了许 多国家学术界和工业界的高度重视。美国商业周刊认为传感器网络是全球未 来四大高科技技术之一，是2 1 世纪世界上最具有影响力的2 1 项技术之一。 无线传感器网络已经成为2 1 世纪的一个新的研究领域，在很多方面向科技 工作者提出了挑战。无线传感器网络处于新技术的最前沿，目前i e e e 还 没有成立无线传感器网络的标准制定小组，国际上从2 0 0 0 年开始出现一些 有关传感器网络研究成果的报道。但是，这些研究成果处于起步阶段，距离 实际需求还相差甚远。总体而言，我国在无线传感器网络方面的研究工作还 很少。由于无线传感器网络是一门新兴技术，国内与国际水平的差距并不是 很大，及时开展这项对人类未来生活影响深远的前沿科技的研究，对国家将 有重大的战略意义瞳1 。 目前，对于无线传感器网络的研究主要集中在网络层和链路层b 1 。网络 数据传输离不开路由协议。研究初期，人们一度认为成熟的i n t e r n e t 技术加 上a dh o c 路由机制对无线传感器网络的路由设计是足够充分的，但深入的 研究表明：传感器网络与传统网络有明显不同的技术要求。前者以数据为中 心，且其路由设计的重要目标是降低节点能源损耗，提高网络生命周期；而 后者以传输数据为目的，且它的路由协议设计的首要任务是移动条件下高服 务质量的提供。这些不同导致了传统的无线a dh o c 网络路由协议不能直接 用于无线传感器网络中，一些新的适用于无线传感器网络的路由协议被提 出，它的研究已经成为无线传感器网络研究中的热点。本文参考目前国内外 关于无线传感器网络的最新资料，通过对现有的无线传感器网络路由协议的 深入研究与分析，设计出一种更适合无线传感器网络特点的节能效果较理想 的路由协议。本课题是自拟题目。 哈尔滨理t 大学工学硕l ：学位论文 1 2 国内外研究现状 在无线传感器网络中，对于路由协议的研究可以分为五类：基于聚簇的 路由协议、基于地理位置的路由协议、能量感知路由协议、以数据为中心的 路由协议、容错路由协议。 1 基于聚簇的路由协议这类协议根据某种规则把无线传感器网络节 点集划分为多个子集，每个子集成为一个簇，具有一个簇头。每个簇的簇头 节点负责全局路由，其他节点通过簇头接收或发送数据。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 ) 协议是第1 个基于聚簇的协议h 1 。 l e a c h 协议随机循环地为每个簇选择簇头节点。每个簇头收集本簇中所有 节点的数据，聚集后传送到s i n k 。l i n d s e y 等人针对l e a c h 协议的缺点提 出了p e g a s i s ( p o w e 卜e f f i c i e n tg a t h e r i n gi ns e n s o ri n f o r m a t i o ns y s t e m s ) 协 议。在该协议中，所有传感器节点被视为一个簇，所有传感器节点把数据传 送到簇头，簇头执行聚集操作并把结果传输到s i n k 。为了保证负载平衡， p e g a s i s 协议轮转地选择簇头嵋1 。l i n d s e y 等人改进了p e g a s i s 协议，减 少了簇头收集数据的时间延迟哺1 。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 ) 协议在l e a c h 协议的基础上通过抑制不必要的通信 来实现节省能量盯1 。t e e n 通过各簇头向整个网络下发两个阈值：硬阈值和 软阈值。在网络开始工作时，每个节点只在观测值超过硬阈值时才向簇头传 输观测值，并将观测值记录在名为s v 的变量中。以后，每个节点只在观测 值与s v 中的值之差超过软阈值时才向簇头传送观测值，并用该值替换s v 中 的值。卿利等人提出一种适应异构无线传感器网络的分布式能量有效的成簇 方案8 1 。此方案基于节点剩余能量与网络节点的平均能量的比例来选举簇头 节点。较高初始能量和剩余能量的节点比低能量节点拥有更多的机会成为簇 头节点，从而使网络能量均匀消耗，延长网络的生存时间。 2 基于地理位置的路由协议这类协议假定每个节点都知道自己的地 理位置以及目标节点的地理位置。b o s e 等人提出了基于地理位置的距离贪 心路由协议，当节点x 向目标位置d 转发数据时，首先从自己的所有一跳邻 居中选择距离目标位置最近的节点y ，然后向y 转发数据。当满足条件的y 不存在时会出现问题隋1 。g p s r ( g r e e d yp e r i m e t e rs t a t e l e s sr o u t i n g ) 协议采用 “右手规则”方法解决了这个问题训。k r a n a k i s 等人提出了基于地理位 置的角度贪心路由协议1 。当节点x 向目标位置d 转发数据时，它首先从自 哈尔滨理工人学工学硕士学位论文 t- - 己的所有一跳邻居中选择一个节点y ，使得x 、y 和d 构成的夹角z d x y 最 小，而且z d x y n ，然后向y 转发数据。g e m ( g r a p he m b e d d i n gf o rs e n s o r n e t w o r k ) 路由协议用虚拟极坐标系表示w s n 的拓扑结构，构造一个以s i n k 为 稂的有环树2 。每个节点由其到树根的跳步数和与根的角度来表示。数据路 由通过这个有环树进行。c a r u s o 等人提出了支持地理路由协议的虚拟坐 标系建立方法，不需要任何地理位置信息，采用基于跳步数的方法建立坐标 系，需要较小的通信代价和内存容量驯。b r u c k 等人利用m e d i a la x i s 对网 络的拓扑结构进行抽象，提出了一种抽象地理路由协议m a p ( am e d i a la x i s b a s e dn a m i n ga n dr o u t i n gp r o t o c 0 1 ) ，不需要节点的地理位置且可以根据节 点的局部信息进行路由，并实现负载平衡n 引。k i m 等人提出了地理路由方法 l c r ( l a z yc r o s s 1 i n kr e m o v a l ) 引。l c r 仅当网络中的某条边影响正常的基于 地理位置路由时，才被动地移除造成非平面化网络的边，有效地减少了事先 计算带来的能量开销。 3 以数据为中心的路由协议定向扩散路由协议是一种典型的以数据 为中心的路由协议n 引。与基于地址的路由协议不同，节点不再有全局惟一的 地址，而代之以此节点观测数据的属性。s i n k 采用洪泛方式传播用户兴趣消 息到整个或部分监测区域内的所有节点，用户兴趣消息表达用户感兴趣的监 测数据。在兴趣消息的传播过程中，协议逐跳地在每个传感器节点上建立反 向的从数据源到s i n k 的传输路径。传感器节点把采集到的数据沿着已确定的 路径向s i n k 传送。该协议在路由建立时需要洪泛传播，能量和时间开销较 大。r u m o r r o u t i n g 协议采用如下方法克服了定向扩散协议开销大这一问 题：当监测区域中的节点感知到事件后，沿随机路径向外扩散传播携带该事 件的代理消息，同时s i n k 发送的查询消息也沿随机路径在网络中传播n 利。当 代理消息和查询消息的传输路径交叉在一起时，就形成一条s i n k 到事件区域 的完整路径。m a d d e n 等人应用r u m o r r o u t i n g 协议的方法处理需要满足多 个条件的查询8 。n i c u l e s c u 等人扩展了r u m o r r o u t i n g 协议，给出了一般 化的r u m o r - r o u t i n g 协议引。t t d d ( t w o t i e rd a t ad i s s e m i n a t i o n ) 是支持移动 s i n k 的以数据为中心的协议心0 1 。在t t d d 中，发现事件的传感器在网络中建 立一个网格状的拓扑结构，把事件信息向网格发送。移动s i n k 发出的与该事 件相关的查询只需在局部范围内广播，当查询到达网格中的某个节点时查询 就得到了满足，同时形成了一条s i n k 到事件区域的完整路径。l i u 等人给出 了一个类似的协议瞳。b u r a g o h a i n 等人提出了支持查询的近似路由协议 算法幢别。模拟实验表明这些算法的性能接近最优。刘明等人提出了一种分布 哈尔滨理工大学工学硕十学位论文 ! 詈皇昌詈詈鼍昌薯置鼍皇毫皇鼍昌m n i 皇冒皇詈詈詈皇詈暑詈皇暑暑鲁穹= 茸詈詈皇鲁暑暑詈詈皇皇= 詈皇詈昌詈= 置詈詈暑皇鲁皇暑詈詈暑詈暑昌鼍盲盲目皇鲁_ 皇穹皇霉 式的高效节能的传感器网络数据收集和聚合协议d e e g 。此协议中的节点 自主地根据其剩余能量以及邻居节点的信号强度来竞争簇头，同时为了减小 簇头节点的能量开销，簇头之间以多跳方式将收集到的数据发送到指定的簇 头节点，然后通过该节点将整个网络收集的数据发送到基站。此外，该协议 还提出了一种简单的簇覆盖方法，使得当节点密度提高时，传感器网络寿命 相应于节点数量呈线性增长。谢志军等人结合传感器网络的节点特性和位置 信息，提出了一种基于连通支配集的传感器网络定向传播模型，以及一种基 于“域”的分布式数据汇聚模型d d a m ( d i s t r i b u t e dd a t aa g g r e g a t i o n m o d e l ) 堙引。d d a m 把传感器网络按“域 划分来构建连通核，传感节点只需 在连通核中寻径，因而可明显减少寻径时间复杂度并且具有更好的分布性。 4 能量感知路由协议s h a h 等人提出了一种能量感知路由协议瞳5 1 。 在该协议中，源节点和目的节点之间建立多条通信路径，每条路径都具有一 个与节点剩余能量相关的选择概率。当源节点需要向目的节点传输数据时， 协议根据路径的选择概率选择一条路径进行数据传输。g e a r ( g e o g r a p h i c a n de n e r g ya w a r er o u t i n g ) 协议根据地理位置信息，建立s i n k 到监测区域的 优化路径，支持s i n k 向监测区所有节点发送查询命令，避免了洪泛传播方 式，减少了路由建立的开销心引。g e a r 把节点到监测区域的距离和节点剩余 能量定义为估计路由代价，并利用捎带机制获取实际路由代价，进行数据传 输的路径优化，形成能量高效的传输路径。c e r p a 等人给出的协议通过尽 量多地选择节点使之处于睡眠状态来节省能量幢 。在这种协议中，节点一旦 进入活动状态就不能回到睡眠状态。c h e n 等人提出的方法则允许节点根据 需要从活动状态回到睡眠状态曙驯。x u 等人提出的协议在保证网络连通条件 下，令尽量多节点处于睡眠状态船引。林恺等人提出一种基于剩余能量预测的 地理位置路由算法e p g r ( e n e r g yp r e d i c t i o na n dg e o g r a p h i c a lr o u t i n g ) 1 。此 算法通过建立传感器网络节点运作模型，及相邻节点剩余能量预测机制，优 化路由选择。刘听等人提出了一种分布式的高效节能的传感器网络数据收集 和聚合协议，网络中节点根据与基站的远近划分成不同的层次阳1 1 。协议优先 选择能量充足并且距离基站最近的节点直接与基站通信，其他节点的数据则 通过邻接节点逐层聚合和转发，最后传送到该节点上。因为与基站通信的能 量代价太高，直接与基站通信的节点能量消耗很快。当距离基站近的节点能 量过低时，协议将选择距离基站较远的节点直接与基站通信。通过顶层节点 迁移机制。m t p 协议能够教好地将能量损耗均匀分布到所有节点上。 5 其他路由协议g a n e s a n 等人提出了利用多条路径来实现协议可 哈尔滨理工大学工学硕士学位论文 靠性的思想2 1 。该协议首先利用局部信息建立多通信路径。在传输数据时， 同一个数据包沿多条路径同时传输到目的节点。c u l p e p p e r 等人给出了根 据用户指定的可靠性要求计算冗余路径条数的方法引。d e b 等人提出了通 过重复传输数据包来保证传输可靠性的方法4 。c h a c h u l s k i 等人提出一 种基于编码的机会路由协议m o r e ( am a c i n d e p e n d e n to p p o r t u n i s t i c r o u t i n gp r o t o c 0 1 ) ，不需要严格的同步策略，并且提高了网络吞吐量b 引。由 于该协议严重依赖节点间的失效概率，不适于动态性高的无线传感器网络。 任彦等人采用计算几何与图论着色方法建立了三维空间的随机最佳覆盖数学 模型，给出了一种分布式启发算法，得到了完成最佳覆盖的低能量消耗路 径。并设计了一种可以实现无线传感器网络三维空间最佳覆盖的优化路由协 议阻6 。结果表明此协议的算法时间复杂度低，并具有可扩展性、有效性和鲁 棒性。闻英友等入利用v o r o n o i 图以及相关d e l a u n a y 三角网定义了传感器 网络中以s i n k 节点为中心的伸展树，并提出了基于遗传算法的感知节点分 布优化算法引。此算法能够以较小代价对传感器网络进行节点的分布优化， 从而有效提高网络整体的感知能力。 综上所述，在路由协议方面目前仍然有很多关键问题未解决，尤其是现 有的无线传感器网络路由协议普遍存在的能量均衡性不好以及节能效果不理 想的问题。 1 3 本文的研究内容 无线传感器网络路由协议设计的首要目标是，高效地利用传感器节点的 能量，从而延长整个网络的生命周期。本文结合无线传感器网络路由协议的 国内外研究现状，针对现有的无线传感器网络路由协议在节能方面的弱点， 其主要研究内容如下： 1 研究无线传感器网络路由协议的特点和性能要求无线传感器网络 是一门前沿的新兴技术，国内的研究还比较少，所以本文将对无线传感器网 络的相关概念以及其路由协议的特点、性能要求等问题进行详细地分析与研 究。 2 研究与分析典型的路由协议要想实现一个无线传感器网络的路由 协议，首先必须研究现有的无线传感器网络路由协议，并对其进行详细的分 析，本文总结了无线传感器网络路由协议的共同特点以及它们各自的优缺 点。 哈尔滨理t 大学t 学硕士学位论文 3 设计能量均衡性好且节能效果理想的路由协议无线传感器网络由 大量微型传感器节点组成，一旦布设后不再更换，且这种微型传感器节点能 量有限，所以如何节省能量就成为了无线传感器网络中一个亟待解决的问 题。本课题将具体地研究如何通过路由协议来均衡节点能量消耗，进而实现 节能的问题。并详细描述所提出路由协议的工作过程。 4 对所提出的无线传感器网络路由协议进行验证在n s 2 平台上对所 提出的方案进行仿真实验，并对实验结果进行比较分析。验证所提出路由协 议的可行性及其性能指标，并得出结论。 1 4 本文的组织结构 本文的内容共分五章，具体安排如下： 第1 章是绪论部分，主要介绍了本课题的研究背景与意义、以及国内外 对无线传感器网络路由协议的研究现状，并指出了本文的主要研究内容和结 构安排。 第2 章无线传感器网络路由协议的研究，介绍无线传感器网络路由协议 设计原则和考虑的因素，重点分析了现有的几种典型的路由协议，并对现有 的路由协议进行性能评估和比较。 第3 章通过对l e a c h 路由算法的研究，提出了对其簇头选择算法的改 进。改进后的算法在基于对节点的剩余能量感知的基础上，选举能量较充足 的节点担当簇头，而且通过对地理位置的感知，在传感器网络内较均匀地选 择簇头。仿真结果显示，改进后的算法较之l e a c h 可以在节点间更有效地 分布能量的消耗，并且提高了网络的生存时间。 第4 章在对l e a c h 改进的基础上，提出了一种高效节能且能量负载均 衡的无线传感器网络分簇路由协议e b c p 。在e b c p 中，整个网络根据节点 与基站的相对位置被划分成若干个网格，然后在网格中选取能量充足的节点 作为簇头，使簇头的地理位置分布较均衡。而且对于“热区 b 引问题，采用 非均匀分簇的方法，根据节点与基站距离选举不同数目的簇头。同时本协议 中簇头和基站的通信采取了多跳的路由策略，使簇头的路由节省能量。 第5 章是e b c p 的模拟仿真验证，本文在n s 2 仿真平台上实现了e b c p 协议。仿真结果表明，与l e a c h 及h e e d 训相比，e b c p 能更好地平衡节 点的能量消耗，有效延长网络的生命周期。 哈尔滨理工大学t 学硕l 学位论文 第2 章无线传感器网络路由协议分析 路由协议的设计是无线传感器网络研究中的热点与难点，各种路由协议 在不同的应用环境和性能评价指标下各有优缺点。由于无线传感器网络的特 殊性使得需要针对其设计不同的路由算法。本章简要介绍其中一些典型的路 由协议，分析这些协议的基本原理，以借鉴前人的设计思想，在结合无线传 感器网络的特点基础上，设计出新的更适合无线传感器网络的路由协议。 2 1 无线传感器网络路由协议特点 在传统的a dh o c 等无线网络中，网络协议设计的首要目标是提供高服 务的质量和公平高效的利用网络带宽，这类网络路由协议的主要任务是寻找 源节点到目的节点间通信时间延迟小的路径，避免产生通信拥塞并均衡网络 流量等，能量损耗并不是这类网络研究考虑的重点h 0 1 。而传感器网络中节点 能量有限，一般没有能量补充，因此路由协议需要提高节点的能源有效性， 同时，传感器网络节点数量大、分布广，每个节点只能获取局部拓扑信息， 路由协议必须能在局部网络拓扑信息的基础上选择出从源节点到达目的节点 的路径h 。一般来讲，和传统网络路由协议相比，传感器网络的路由协议具 有以下特点： ( 1 ) 传感器网络的节点能量有限，提高节点的能源有效性和网络的生命 周期是协议设计的首要目标。 ( 2 ) 传感器网络中的大部分节点在整个网络生命周期中基本保持静止， 无需频繁地更新路由表信息。在传统a dh o e 网络中，由于应用的要求，节 点频繁移动，拓扑结构动态变化，快速有效地达到路由协议收敛状态是其路 由协议的主要目标；而对于传感器网络，在很多情况下，除了原有节点失效 和新的节点加入外，网络拓扑结构基本不会发生变化，因此没有必要花费很 大的代价频繁地更新路由表信息。 ( 3 ) 为了提高网络的可扩展性，需要采用多跳通信的方式传送数据，而 节点有限的存储资源和计算资源，使其不能存储大量的路由信息，进行复杂 的路由计算。如何在只能获取局部拓扑信息和资源有限的条件下实现简单高 效的路由机制是传感器网络路由协议设计的一个基本问题。 ( 4 ) 传感器网络以数据为中一g , ( d a t ac e n t r i c ) 进行路由，不同于传统a d 哈尔滨理t 大学t 学硕士学位论文 h o c 网络以地址为中, l 二, ( a d d r e s sc e n t r i c ) 进行路由的模式，以数据为中心进行 路由是传感器网络网络层通信的一个显著特点。在传感器网络中，人们只关 心某个区域的某个观测指标的值，而不会去关心具体某个节点的观测数据， 比如说人们可能希望知道“某个监控区域的温度是多少 ，而不会关心“地 址为“1 的节点所探测到的温度值是多少。 ( 5 ) 传感器网络节点分布密集，邻近节点间采集的数据具有相似性，存 在大量冗余信息，为了减少节点的能量损耗，同时也为了提高节点采集数据 的精度，感知数据需经融合( d a t af u s i o n ) 处理后再进行路由。 2 2 无线传感器网络路由协议设计目标 无线传感器网络具有异于无线自组网的构成特性和应用特点，因此设计 传感器网络中的路由协议应实现以下几个方面的目标h 引： 1 低能耗节点的能量十分有限，要求算法尽可能地节能。 2 具有能量感知( e n e r g ya w a r e ) 功能由于节点能源无法补充，因此， 设计有效的路由策略以延长网络的生命周期成为传感器网络的核心问题。即 算法应尽可能地使网络中所有节点的能耗均衡，而不让部分节点因能耗过快 而失效，从而达到延长网络生命周期的目的。 3 鲁棒性算法应具备自适应性及容错性( f a u l tt o l e r a n t ) ，无需人干涉 可自行适应各种应用环境。 4 可扩展性由于传感器网络规模大且节点资源有限，节点不可能维 护任何全局性的信息，因此算法只能依赖局部信息进行路由。 5 低延时性算法必须满足应用的低延时要求，在人物所要求的时间 内及时地将数据传送给远程中心。 2 3 无线传感器网络路由协议分类 针对无线传感器网络路由协议的设计目标，人们设计了各种不同的路由 算法，各种路由协议在不同的应用环境和性能评价指标下各有千秋。依据网 络管理的逻辑结构，现有的传感器网络路由协议主要可分为平面路由与层次 路由两种。 在无线传感器网络体系结构中，网络层的路由技术对无线传感器网络的 性能好坏有着重要影响。随着国内外无线传感器网络的研究发展，许多路由 - 8 - 哈尔滨理t 大学t 学硕七学位论文 协议被提了出来，从网络拓扑结构的角度我们可以大体把它们分为两类：平 面路由协议和层次路由协议。 2 3 1 平面路由 平面结构是指网络中各节点在路由功能上地位相同，没有引入分层管理 机制。平面结构路由的优点是网络中没有特殊的节点，网络流量均匀地分散 在网络中，路由算法易于实现。缺点是可扩展性小，在一定程度上限制了网 络的规模h3 1 。下面介绍几种典型的平面路由协议。 1 扩散法( f l o o d i n g ) f l o o d i n g 算法是一种传统的网络通信路由协议。 如图2 1 所示，节点s 希望发送一块数据给节点d ，使用扩散法，节点s 首 先通过网络将数据副本传送给它的每一个邻居节点，每一个邻居节点又将其 传输给各自的每一个邻居节点，除了刚刚给它们发送数据副本的节点s 外。如此继续下去，直到将数据传输到目的节点d 为止或者所有节点拥有 此数据副本为止引。 图2 1 扩散法的信息爆炸问题 f i g 2 - li m p l o s i o no ff l o o d i n g 扩散法所具有的优点： ( 1 ) 实现简单； ( 2 ) 不需要为保持网络拓扑信息和实现复杂的路由发现算法而消耗计算 资源； ( 3 ) 适用于健壮性要求高的场合。 表现不足的地方主要有： ( 1 ) 存在信息爆炸( i m p l o s i o n ) 问题，即出现一个节点可能得到一个数据 多个副本的现象，如图2 1 所示。 ( 2 ) 出现部分重叠( o v e r l a p ) 现象，如果处于同一观测环境的两个相邻同 类传感器节点同时对一个事件做出反应，二者采集的数据性质相同，数值相 近，那么，这两个节点的邻居节点将收到双份数据副本。 ( 3 ) 盲目使用资源，即扩散法不考虑各节点数量可用状况因而无法做出 相应的自适应路由选择。 2 闲聊法( g o s s i p i n g ) 闲聊法是扩散法的改进版本。为节约能量，闲 聊法使用随机性原则。节点发送数据，不再像扩散法那样，给它的每一个邻 居节点发送数据副本，而是随机选择某一个邻居节点，向它发送一份数据副 本。如图2 2 所示，如果一个节点e 己收到它的邻居节点b 的数据副本， 若再次收到，那么，它将此数据发回它的邻居节点b 。 图2 2 闲聊法的数据重发现象 f i g 2 - 2d a t ao v e r l a po fg o s s i p i n g 喻尔滨理一 大学t 学硕士学位论文 尽管闲聊法可避免出现信息爆炸问题，但是仍然无法解决部分重叠现象 和盲目使用资源问题，而且数据传输平均时延拉长，传输速度变慢。 3 s a r 协议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 ) 协议算法创建多颗 树，每颗树的树根都是s i n k 的一跳邻居。在算法的初始阶段，树从根节点 开始，不断吸收新的节点加入。在树延伸的过程中，将避免那些q o s 不好 及能量已经消耗较多的节点。 初始阶段结束后，大多数节点都加入了某个树，各节点只需要知道自己 的上一跳邻居，以转发报文。在网络工作过程中，一些树可能由于中间节点 能量耗尽而断开，也可能有新的节点加入网络而使网络拓扑结构发生变化。 所以网关周期性的发起“重新建立路径的命令，以保证网络的连通性和最 优的服务质量。 4 s p i n 协议s p i n ( 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 有三种数据包类型，即a d v 、r e q 和d a 噙h 6 1 。 a d v 一用于新数据广播。当一个节点有数据可共享时，它可用a d v 数 据包( 包含元数据) 对外广播。 r e q 一用于请求发送数据。当一个节点希望接收d a t a 数据包时，发 送r e q 数据包。 d a r a 一包含附上元数据头( m e t a d a t ah e a d e r ) 的传感器采集的数据的数 据包。 在发送一个d a t a 数据包之前，一个传感器节点首先对外广播a d v 数 据包；如果一个邻居节点在收到a d v 后有意愿接收该d a t a 数据包，那么 它向该节点发送一个r e q 数据包，接着节点向该邻居节点发送d a t a 数据 哈尔滨理工大学t 学硕j ：学位论文 包。类似地进行下去，d a t a 数据包可被传输到远方汇聚节点或基站。图2 - 3 表示了s p i n 协议的工作过程。 a ) 广播a d v 信息b ) 返回r e q 信息c ) 传递数据信息 a ) b r o a da d vm e s s a g e b ) r e t u r nr e qm e s s a g ec ) t r a n s f e rd a t am e s s a g e 图2 - 3s p i n 协议工作过程 f i g 2 - 3w o r k i n gp r o c e s so fs p i np r o t o c o l s p i n 协议有四种不同的形式： ( 1 ) s p i n p p ：采用点到点的通信模式，并假定两节点间的通信不受其 他节点的干扰，分组不会丢失，功率没有任何限制。要发送数据的节点通过 a d v 向它的相邻节点广播消息，感兴趣的节点通过r e q 发送请求，数据源 向请求者发送数据。接收到数据的节点再向它的相邻节点广播a d v 消息， 如此重复，使所有节点都有机会接收到任何数据。 ( 2 ) s p i n e c ：在s p i n p p 的基础上考虑了节点的功耗，只有能够顺利 完成所有任务且能量不低于设定阈值的节点才可参与数据交换。 ( 3 ) s p i n b c ：设计了广播信道，使所有的有效半径内的节点可以同时 完成数据交换。为了防止产生重复的r e q 请求，节点在听到a d v 消息以 后，设定一个随机定时器来控制r e q 请求的发送，其他节点听到该请求， 主动放弃请求权利。 ( 4 ) s p i n r l ：它是对s p i n b c 的完善，主要考虑如何恢复无线链路引 入的分组差错与丢失。记录a d v 消息的相关状态，如果在确定时间间隔内 接收不到请求数据，则发送重传请求，重传请求的次数有一定的限制。 5 定向扩散定向扩散( d i r e c t e dd i f f u s i o n ) 路由协议是以数据为中心的 路由协议，与已有的路由协议有着截然不同的实现机制，其突出特点是引入 了梯度来描述网络中间节点对该方向继续搜索获得匹配数据的可能性h 利。 s i n k 节点向所有传感器节点发送其兴趣( i n t e r e s t ) ，即通过分配不同属性值来 表示不同任务的描述符，每个传感器节点在收到兴趣后保存在各自的c a c h e 中。每个兴趣项( i n t e r e s te n t r y ) 包含一个时间域( t i m e s t a m pf i e l d ) 和若干个梯 哈尔滨理工火学工学硕上学位论文 度域( g r a d i e n tf i e l d ) ，按成本最小化和能量自适应原则引导数据扩散的方 向。当一个兴趣传遍整个网络后，从源节点( 即兴趣所在区域的传感器节点) 到汇聚节点或基站之间的梯度就建立起来了。一旦源节点采集到兴趣所需的 数据，那么，源节点沿着该兴趣的梯度路径传输数据到汇聚节点或基站。其 中，源节点采集的数据首先在本地采用数据融合技术进行整合，然后在网络 中传输。定向扩散的缺点是没有形成到s i n k 节点的多条路由，路由健壮性 不够好。 定向扩散的特点是： ( 1 ) 定向扩散是以数据为中心的路由协议，所有通信都局限在邻居节点 之间，每个节点除了收集数据以外，还能够进行数据聚集和缓存数据，这既 减少了网络数据流也降低了数据传输延迟。 ( 2 ) 定向扩散允许灵活的路径创建和路径恢复的局部算法设计，使得这 些系统对于动态性更健壮。 ( 3 ) 按需驱动数据的数据传送模式和不需要维护全局网络拓扑结构，使 得定向扩散成为一种高能源有效性的协议。 2 3 2 层次路由 与平面路由协议相对应的是层次路由协议。层次路由协议采用簇的概念 对传感器节点进行层次划分。若干个相邻节点构成一个簇，每个簇有一个簇 头，簇与簇之间可以通过网关通