（计算机科学与技术专业论文）基于区域划分的无线传感器网络路由算法研究.pdf

r e s e a r c ho nr e g i o n a ld i v i s i o nb a s e dr o u t i n ga l g o r i t h mi n w i r e l e s ss e n s o rn e t w o r k b y g o n gj u n l i b e ( t i a n j i nu n i v e r s i t yo fs c i e n c e & t e c h n o l o g y ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n c o m p u t e rs c i e n c ea n dt e c h n o l o g y i nt h e g r a d u a t es c h o o l o f h u n a n u n i v e r s i t y s u p e r v i s o r a s s o c i a t ep r o f e s s o rw u r e n y o n g m a y ，2 0 1 1 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名：璇幕确 日期：扫1 年s 月弓fe t 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇 编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：袭幕两 导师签名：7 五秀 日期：加1 1 年上月季1 日 日期：2 0 1 1 年g - 月弓1 日 基于区域划分的无线传感器网络路由算泫研究 摘要 无线传感器网络是由大量微型传感器节点通过多跳方式形成的特殊自组织网 络，其主要任务是进行数据收集，即将监测数据由源节点以多跳的方式传输到基 站。“空洞 是传感器网络数据收集过程中固有的一种现象，它涉及多个方面，包 括网络中节点能量消耗不均衡、部署空洞、路由空洞、事件空洞、环境障碍等， 这些现象都会导致能量空洞的出现。因此如何解决空洞问题，均衡网络负载以及 延长网络生命周期是无线传感器网络路由协议设计的主要目标。 本文研究了现有的典型路由协议以及空洞处理策略，针对大多数路由协议能 量效率低、生命周期短以及空洞处理复杂的缺点，提出了一种高能效负载均衡的 区域划分路由算法。该算法采用区域内与区域间两种方式进行数据传输，在网络 初始阶段有效的避免了路由空洞，并且区域间根据子区域生命周期的不同使用不 同的路由更新时间，通过均衡网络能量消耗来延长网络的生命周期。 本文具体研究内容如下： 。1 概述无线传感器网络的特点及当前的一些路由协议，比较三种基于地理位 置信息的路由算法，并分析算法存在的问题和不足，总结本文传感器网络路由协 议设计的主要目的。 2 本文引入了均衡节点负载的区域划分思想对网络进行划分。首先给每个节 点设置一个权值，该权值综合考虑了节点的剩余能量和节点到s i n k 节点的距离。 然后使用吸收策略确定节点所在的区域，网络中节点权值越大，节点的吸收能力 就越强，所承担的负载也就越多，相反权值小的节点承担的负载少，因此吸收策 略可以有效的均衡节点负载。最后，得到一个负载均衡的森林树拓扑结构，每棵 子树为一个子区域。 3 采用区域内与区域间两种方式进行数据传输。在子区域内使用常规传输方 式进行数据传输，不存在路由空洞问题。子区域间则通过寻找关键节点，将数据 传输到离s i n k 节点较近的相邻子区域，减少空洞出现的可能。 4 本文根据每个子区域中生命周期的不同，使用动态路由更新时间对网络进 行路由更新，均衡了子区域间的能量消耗。仿真结果表明新算法在节点负载均衡、 能量有效性、能耗均衡、延长网络生命周期以及丢包率等方面都比之前的两个算 法好。 关键词：无线传感器网络；数据收集；区域划分；生命周期；空洞；负载均衡 i i ab s t r a c t w 1 r e j e s ss e n s o rn e t w o r k ，a sas p e c i a lk i n do f a d h o cn e t w o r k ，i sm a d eu po fa l a r g en u m b e ro fm i c r o s e n s o r si nm u l t i h o p sw a y t h em a j o r t a s ko fw s ni st oc o l l e c t d a t af o r mm o n i t o r i n ga r e a ，t h a ti st os a y ，i ts e n d sd a t af r o m s o u r c en o d et ot h es i n k h o w e v e r , a sa ni 1 1 t r i n s i c d e f i c i e n c y ，“h o l e ”e x i s t i n gi nd a t ac o i l e c t i n gw h i c hr e s u l t f r o mt h eu n b a l a n c e dc o n s u m p t i o no fe n e r g y , d e p l o y m e n t v o i d ，r o u t i n gv o i d ，e v e n t v o i d , e n v i r o n m e n t a lb a r r i e ra n ds o f o r t h t h u s ，h o wt os o l v et h eh o l e sp r o b l e m ， b a l a n c et h el o a do fn o d e sa n dp r o l o n g t h en e t w o r kl i f e t i m ei st h em a i n l y t a r g e to ft h i s l nt n l s p a p e r ，w es t u d i e ds o m e t y p i c a lr o u t i n gp r o t o c o l sa n d e n e r g yh o l e p r o c e s s l n gs t r a t e g i e s i no r d e rt oo v e r c o m et h es h o r t c o m i n g so f l o we n e r g ye f f i c i e n c y s h o r tl i f e t i m ea sw e j l a st h e s o p h i s t i c a t i o nt h a t e x i s t i n gi nm o s to ft h er o u t i n g p r o t o c o l s ， al o a d b a l a n c e r e g i o n a ld i v i s i o n r o u t i n ga l g o r i t h mw i t hh i g h e n e r g y 。e f f i c l e mw a sp r o p o s e d t h i sa l g o r i t h ma d o p t e dt w o w a y st ot r a n s f e rd a t ab o t h l ni n t e ra n di n t r ar e g i o n sf o r a v o i d i n gr o u t i n gh o l ei nt h ei n i t i a ln e t w o r ks t a g e ，a n dt h e r o u t p d a t i n gt i m eo fe a c hs u b 。r e g i o nw a sd e t e r m i n e d b yt h el i f e t i m eo ft h i s s u b r e 9 1 0 n ，t h i sm e t h o dc a np r o l o n gn e t w o r kl i f e t i m et h r o u g h b a l a n c i n gt h ee n e r g y c o n s u m p t i o no fn e t w o r k t h em a i nw o r ko ft h i sp a p e ri sa sf o i l o w s ： i f oa n a i y z et h ec h a r a c t e r i s t i c so fw i r e l e s s s e n s o rn e t w o r ka n ds o m er o u t i n g p r o t o c o l s , a n dc o m p a r et h r e er o u t i n ga l g o r i t h m sb a s e do n g e o g r a p h i ci n f 0 珊a t i o n i t 士1 n d so u t e x i s t i n gp r o b l e m sa n dt h ei n s u f f i c i e n c yi nt h e s et h r e e a l g o r i t h m s ，s o m e g o a i sw e r eo b t a i n e df o r d e s i g n i n go u rr o u t i n ga l g o r i t h m z -ln l sp a p e ri n t r o d u c e sa ni d e ao fr e g i o n a ld i v i s i o nt od i v i d e t h en e t w o r ka n d b a l a n c et h en e t w o r kl o a d a t f i r s t ，aw e i g h tv a l u ef o re a c hi n d i v i d u a lw a ss e t u p ， w h l c hc o n c e r n e da b o u tt h er e s i d u a le n e r g yo f n o d e sa n d t h ed i s t a n c eb e t w e e nn o d e st o s i n k a 衔t h a t , w eu s e da b s o r p t i o ns t r a t e g y t od e t e r m i n et h er e g i o nw h i c hn o d e s e x l s t t h en o d ew i t hl a r g e rw e i g h tv a l u ew i l lh a v em o r e p o w e rt oa b s o r bt h en e i g h b o r n o d e sa n dm o r el o a d si nn o d e ，o nt h ec o n t r a r y ，t h e n o d ew i t hs m a l l e rw e i g h tv a l u e w il lh a v el e s so rn oi o a d si nn o d e ，t h e r e f o r e a b s o r p t i o ns t r a t e g yh a v eag o o dr o l ei n l o d eb a l a n c i n g f i n a l l y ，af o r e s tb a s e d t o p o l o g yw i t hl o a db a l a n c i n gw a so b t a i n e di n 1 1 1 l t i a ln e t w o r k s t a g ea n dw ec o n s i d e r e de a c hc h i l dt r e ei nf o r e s ta sa s u b - r e g i o n i i i i v 硕t 学位论文 目录 学位论文原创性声明和学位论文版权使用授权书i 摘要i i a b s t r a c t j i i i 插图索引一v i i 附表索引v i i i 第1 章绪论1 1 1 研究背景及意义1 1 2 国内外研究进展2 1 3 本文的研究内容与结构3 第2 章无线传感器网络路由协议相关研究5 2 1 无线传感器网络概述5 2 2 无线传感器网络路由算法介绍7 2 2 1 无线传感器网络路由协议设计要求8 2 2 2 无线传感器网络路由算法分类8 2 2 3 无线传感器网络路由算法的能量空洞问题1 1 2 3 无线传感器网络路由协议的数据收集与负载均衡1 7 2 3 1 无线传感器网络数据收集路由协议1 7 2 3 2 无线传感器网络的负载均衡问题综述1 9 2 4 小结2 l 第3 章基于区域划分的传感器网络数据收集路由算法2 2 3 1 算法设计背景2 2 3 2 无线传感器网络区域划分算法设计2 4 3 2 1 传感器网络区域划分思想一2 5 3 2 2 区域划分路由算法数据收集过程2 7 3 3 区域划分仿真结果与分析2 8 3 4 小结一3 0 第4 章d i v i s i o n 算法仿真和性能分析3 1 4 1 不同路由更新时间对区域划分算法的性能影响一3 l 4 2 区域间能量均衡的路由更新时间3 2 4 3 网络模型3 3 4 4 仿真环境与参数一3 4 v v l 硕i ：学位论文 插图索引 图2 1 无线传感器网络体系结构图一 图2 2 无线传感器网络节点结构图 图2 3r g n 平面图和g g 平面图 图2 4 用反向压力信标解决路由空洞问题 图2 5 沿空洞边界绕过空洞示例 图2 6 无线传感器网络数据收集的拓扑结构 图3 1 能量密度路由算法路径选择 图3 2 子树拆分路由算法空洞处理示意图 图3 3 区域划分路由算法伪代码 图3 4 区域划分数据传输总流程 图3 5d s 算法得到的初始拓扑结构 图3 6s u b t r e e 算法得到的初始拓扑结构 图3 7d i v i s i o n 算法得到的初始拓扑结构 图4 1 不同路由更新时间的数据传输情况 图4 2 传感器网络能量消耗模型 图4 3 不同节点死亡个数对应的传输数据总数 图4 4 节点不同死亡比例对应的网络丢包率 图4 5 传输一定总数据包时对应的节点死亡个数和节点平 图4 6 传输数据总数对应的网络平均路由跳数：_ v i i 基于区域划分的无线传感器网络路由算法研究 附表索引 表2 1 空洞避免与处理策略的比较1 7 表4 1 无线传感器网络信道能耗模型参数3 4 表4 2 无线传感器网络路由算法参数配置3 6 v i l i 硕士学位论文 1 1 研究背景及意义 第1 章绪论 无线传感器网络( 简称w s n ，w i r e l e s ss e n s o rn e t w o r k ) 是由部署在监测区 域内大量具有通信能力，感知能力和数据处理能力的廉价微型传感器节点通过无 线通信方式形成的多跳自组织网络【l 】。传感器网络依赖于物理世界中随机分布的 传感器节点监测到的传感数据，其目的是实现无所不在的感知。在传感器网络中， 不同形态的传感器处于灵活的网络架构中，以无线方式发送和接收信号，只要邻 居节点的距离不超过l o o 米，就不需要有线方式连接网络。w s n 具有多级冗余、 自组织性和自愈能力，即如果有任意一个或多个节点失效，剩余的节点将形成一 个新的通信网络。当这个或多个节点重新正常工作时，它能够自动融入先前的网 络中。这种特性为用户提供了随时添加或减少传感器网络中节点数目的功能，而 且不需要重新设置网络结构和路由。尽管w s n 为业界提供了巨大的想象空间， 但由于节点成本、功耗和体积等关键问题一直没有很好解决，过去很多年来，w s n 一直只用于科研机构和实验室的研究。随着微机电系统，片上系统，无线通信系 统以及嵌入式技术的飞速发展，无线传感器网络开始逐渐应用于商业活动中。无 线传感器网络低功耗，低成本，分布式和自组织的特点给信息化产业带来了空前 的影响，已经成为当前国际备受关注，多学科高度交叉发展的前沿热点研究领域。 传感器经历了微型化、智能化、多功能传感器到现在的无线传感器网络四个阶段， 作为当前国际上备受关注，由多学科高度交叉的新型技术前沿，无线传感器网络 分别被美国商业周刊和m i t 技术评测评为2 1 世纪最有影响的2 1 项技术之一以及 改变世界的l o 大技术之一【2 j 。 无线传感器网络通常运行在环境恶劣且人类无法接近的地带，无法随时对其 进行操作，网络中的传感器节点大都采用电池供电，通过更换电池的方式来补充 节点的能量在多数情况下是不现实的，因此，在无线传感器网络设计中，技术和 协议的设计实现都要以节能为前提i lj 。无线传感器网络的节能思想包括在了传感 器网络的各层设计工作中。在网络层，早期的路由协议节能策略的研究主要集中 于如何减少网络的总能量消耗，并没有考虑节点间的负载均衡问题。例如文献【3 ，4 】 论述了通过构造最小代价生成树，使整个网络总能耗最小。后来研究人员发现， 在此类节能算法中网络的总能量消耗是减少了，但是网络的生命周期并没有得到 相应的增加，文献【5 】的实验数据表明，当靠近s i n k 的节点由于要转发更多数据 而耗尽能量过早死亡时，远离s i n k 的节点剩余能量还为初始能量的9 0 以上，这 极大的影响了网络连通性，浪费了节点剩余能量。网络的生命周期通常定义为网 基于区域划分的无线传感器网络路由算法研究 路中第一个节点死亡时网络中传输的数据总量【6 】，为了延长网络生命周期，我们 必须最大化网络中第一个死亡节点的生命周期。因此，之后的研究开始试图寻找 那些将会过早死亡的节点，对其进行负载均衡，延长这些瓶颈节点的生命周期， 最大化整个网络生命周期。 由此可知，延长传感器网络的生命周期需要从两个方面着手：一是延长单个节 点的生命周期，二是均衡网络中节点间的能量使用水平，研究人员开始从降低网 络总体能量消耗与保持节点能量均衡消耗并重来提高网络性能，延长网络的生命 周期【7 9 1 。 1 2 国内外研究进展 无线传感器网络的研究起步于2 0 世纪7 0 年代末期，1 9 7 8 年卡耐基一梅隆大 学的分布式传感器网络研究被看成是现代传感器网络的雏形：1 9 9 6 年美国加利福 尼亚大学洛杉矶分校的一份“低能耗无线集成微型传感器”报告正式揭开了现代无 线传感器网络的序幕；自2 0 0 1 年起美国国防部高级研究所计划署每年投入上千万 美元进行传感器网络的研究；在美国自然科学基金委员会的推动下，美国众多著 名高校纷纷加入传感器网络的研究行列，进行了大量的基础理论和关键技术研究； 同是在2 0 0 1 年美国计算机学会( a c m ) 和电气电子工程师协会( i e e e ) 成立了第一 个传感器网络技术会议一一i p s n ，为传感器网络的学术研究奠定了基础， 2 0 0 3 2 0 0 4 年相继出现了许多类似的会议；2 0 0 4 年美国的一些大型商业技术公司 看到了传感器网络未来的发展前景，纷纷与众高校合作开展关于传感器网络的商 业研发计划；2 0 0 5 年美国计算机学会专门创刊a c mt r a n s a c t i o no ns e n s o rn e t w o r k 用于出版关于传感器网络研究方向的优秀学术文章；2 0 0 6 年在中国北京计算机学 会传感器网络专委会的成立标志着中国的传感器网络技术研究进入一个新的发展 阶段；2 0 0 8 年1 1 月i b m 公司董事长兼c e o 彭明盛提出了“智慧地球”的概念， 其目的是将传感器形成的物联网与传统互联网整合起来，完全实现人类社会与物 理世界的互联，标志着传感器网络正逐渐走向成熟。 无线传感器网络可以获取客观物理世界的相关信息，具有非常广泛的应用前 景【2 j 。在传感器网络中，传感器节点以无线连接的方式自组织成网络后的主要任 务是进行数据收集，然后按照一定的路由选择算法将数据传输给s i n k 节点，在这 个过程中使用的路由算法的好坏对网络的性能起着关键性作用。传感器网络是一 种新型自组织网络，能量严重受限、拓扑结构频繁变化等特点决定了传统的无线 网络路由协议并不适合它，所以设计新的、适应无线传感器网络特点的路由协议 具有重要的意义【3 l 】。 ( 1 ) 国外传感器网络路由协议研究现状 国外对传感器网络路由协议方面做了大量的研究工作，在美国，麻省理工学 2 硕上学位论文 院、哈佛大学、康奈尔大学、南加州大学等很多大学都开展了无线传感器网络通 信协议的研究，先后提出了s p i n 1 们、d i r e c t e dd i f f u s i o n i l l l 、s p e e d t l2 1 、l e a c h t l3 1 、 t e e n t l4 1 、p e g a s i s 1 5 1 、g p s r 16 1 、g e a r 1 7 】等经典路由协议。 ( 2 ) 国内传感器网络路由协议研究现状 我国无线传感器网络方面的研究工作较欧美国家晚，但也不乏许多经典优秀 的路由协议，例如关于最大化传感器网络生命周期的路由算法【1 8 2 0 1 、如何解决传 感器网络能量空洞的路由算法【2 1 2 5 1 、关于节点负载均衡的传感器网络路由算法【7 ， 8 ，2 0 , 2 6 1 、以及关于高能效的传感器网络路由算法【2 5 ，2 7 。2 9 1 等，后面将会对这些路由 协议进行详细介绍。 尽管国内外已经提出了许多的路由协议，但是没有一个路由协议是适合所有 应用场景的。因此研究传感器网络的路由协议，需要结合具体的应用环境进行具 体设计与分析。 一 1 3 本文的研究内容与结构 无线传感器网络路由协议是目前一个比较活跃的研究领域，不同的应用环境 需要设计不同的路由算法。本文通过对现有路由协议进行分析和介绍，重点分析 其在能量有效性、路由空洞处理、负载均衡、延长网络生命周期等方面采取的有 效措施及存在的不足，然后侧重介绍了传感器网络的空洞问题以及数据收集过程 中的负载均衡。借鉴已有的基于地理位置信息的路由算法设计，从网络路由空洞 处理，节点负载均衡和延长网络生命周期的角度对能量密度算法进行改进，提出 一个基于区域划分的无线传感器网络能量均衡路由算法，通过仿真实验验证协议 的可行性以及性能的提升。 具体工作主要有： ( 1 ) 阅读大量相关中英文文献，研究和分析现有的无线传感器网络路由算法， 从而提出本文路由协议设计的目标是解决基于位置地理路由协议的路由空洞问 题，均衡网络能量消耗，延长网络的生命周期。 ( 2 ) 侧重研究经典的地理位置信息路由协议g p s r ，及其后的改进算法一一 能量密度路由协议和子树拆分路由算法，对他们的优缺点进行比较和评述，针对 他们存在的问题寻求简单而有效的解决方案。 ( 3 ) 研究和分析无线传感器网络的小世界效应以及负载均衡思想，在此基础 上根据节点间的耦合度对网络进行区域划分，实现子区域内节点的负载均衡。 ( 4 ) 为了实现整个网络的能量消耗均衡，延长网络的生命周期，设计了一种 动态路由更新方法。针对不同的子区域网络负载，采用不同的路由更新时间，均 衡子区域间的能量消耗。 本文的结构安排如下： 基于区域划分的无线传感器网络路由算法研究 第1 章简要介绍了本文的研究背景及意义，国内外相关研究的发展现状，然 后阐述了本文的主要研究内容与结构。 第2 章简要介绍了无线传感器网络的体系结构和特点，然后对现有的经典路 由协议进行了简要介绍，重点介绍了无线传感器网络的空洞问题及目前采取的相 关策略，最后重点介绍了传感器网络的数据收集路由协议及其在负载均衡方面的 表现。 第3 章研究和分析三种基于地理位置信息路由协议的优点与缺点，针对它们 存在的问题从路由空洞处理，负载均衡和延长网络生命周期三个方面进行改进， 提出了一种基于区域划分的路由算法，并对其区域内节点负载均衡方面的性能与 其它两种算法进行比较。 第4 章中针对路由更新时间对路由算法性能的影响，为区域划分路由算法设 计了一种均衡区域间能量消耗的动态路由更新，并对整个算法进行系统仿真。从 负载均衡，能量有效性，网络生命周期，丢包率，平均传输路径长度等多个方面 考察算法的性能。 最后为结论部分，对全文工作进行总结和对未来工作进行展望。 4 硕士学位论文 第2 章无线传感器网络路由协议相关研究 无线传感器网络节点使用电池供电且部署在环境恶劣的无人区域，更换电池 是不现实的；另外无线传感器网络是一类以数据为中心的汇聚式、多跳、多对一 网络，空洞是传感器网络数据收集过程中不可避免的一个问题【3 0 1 。因此无线传感 器网络路由协议设计的主要目标是解决空洞问题，均衡网络能量消耗，延长网络 的生命周期。 2 1 无线传感器网络概述 无线传感器网_ 络( w i r e l e s s s e n s o rn e t w o r k s ，w s n ) 是由部署在监测区域内大 量廉价的微型传感器节点组成，通过无线通信的方式形成多跳自组织网络系统， 其目的是协作地感知、采集和处理网络覆盖范围内感知对象的信息，并传送到用 户终端；传感器、感知对象和观察者构成了传感器网络的三要素，其体系结构如 图2 1 所示【1 】： 图2 1 无线传感器网络体系结构图 传感器节点分为感知、数据处理、无线通信和能量供应四个单元，其结构如 图2 2 所示，其中感知单元分为传感器和模数转换装置两部分，传感器是一种监 测装置，感知周围环境信息并以一定规律的模拟信号输出，模数转换装置将收到 的模拟信号转换为数字信号然后发送给数据处理单元；数据处理单元分为处理器 和存储器两个部分，由于受成本和能量限制，传感器节点的处理和存储能量相对 薄弱，适合短距离数据传输，因此在传感器网络中通常采用多跳的方式进行数据 传输；无线通信单元分为发送模式和接收模式，传感器节点的主要能耗来源于数 据的发送和接收，因此传感器网络节能算法主要是节省数据发送和接收时的能量 5 基于区域划分的无线传感器网络路由算法研究 消耗；能量单元采用电池供电且更换电池是不现实的，所以传感器节点能量受限。 s i n k 节点主要负责传感器节点与外网的连接，具有无限的能量和较强的数据 处理与通信能力。一方面它收集监测区域内的数据，发布用户对传感器网络的控 制信息；另一方面它连接传感器网络和用户终端，转发收集到的数据信息到用户 终端上。因此，s i n k 节点既可以作为一个资源不受限的普通传感器节点，有足够 的能量和数据处理与通信资源，也可以是仅带无线通信接口而没有检测功能的特 殊网关设备。 图2 2 无线传感器网络节点结构图 与传统无线网络相比，无线传感器网络具有以下特征【1 ，2 】： ( 1 ) 与物理环境关系紧密 无线传感器网络部署在环境恶劣、无人看守的物理环境中，传感器节点监测 物理世界中的温度、湿度、速度等状况，将采集到的数据传输给网络终端。 ( 2 ) 传感器节点能量受限 传感器节点采用电池供电，并且更换电池是不现实的，因此能量有限是传感 器网络面临的最大问题。延长传感器节点寿命，最大化网络生命周期是设计传感 器网络路由协议的首要挑战。 ( 3 ) 传感器节点的计算能力、通信能力和存储容量有限 受经济成本，体积、功耗等限制，传感器节点的计算能力和存储容量有限。 也就意味着我们的路由协议设计应当简单，不能进行太复杂的操作。传感器节点 的通信能力有限，其能量消耗与通信距离成正比，距离增加，能量消耗急剧增加。 因此应当尽量使网络工作在常规传输模式下，节省网络能量。 ( 4 ) 网络拓扑结构变化快 无线传感器网络中节点死亡、部分节点移动或者有新节点加入都会使网络拓 扑结构发生变化，又由于无线传感器网络所处的应用环境具有不确定性，因此传 感器网络是一种动态变化的网络。 ( 5 ) 以数据为中心的网络 无线传感器网络是一种以数据为中心的网络，大量节点随机部署，不依赖于 6 硕十学位论文 统一的标识，感知区域的节点自动监测数据，将收集到的信息发送到s i n k 节点， 单个节点的失效不会影响网络中其他节点的数据传输。 ( 6 ) 应用相关的网络 无线传感器网络具有广阔的应用前景，不同的应用环境对传感器网络的要求 不同。可以说传感器网络是在特定应用背景下，以一定的网络模型形成的传感器 节点集合。 从无线传感器网络的特点可以看出传感器网络路由协议的复杂度和性能的优 劣与网络采用的拓扑结构密切相关，采用不同的拓扑结构将得到不同的路由协议 性能。按照其组网形态和方式来看，目前主要有集中式、分布式和层次式三种结 构。 ( 1 ) 集中式结构 传感器网络的集中式结构是指在网络中设置少量管理节点，网络中的其他节 点通过少量管理节点的集中管理实现对全网络的监测。这种结构的优点是实现难 度低，仅需要在网络中配置几个资源富余的节点即可实现对全网的管理，缺点是 在大规模或动态网络中，管理节点负载太重，会成为整个网络的瓶颈节点，一个 管理节点的失效会造成网络局部区域的瘫痪。 ( 2 ) 层次结构 传感器网络的层次结构同样在网络中设置若干个中间管理节点，但是每个管 理节点有自己的管辖范围，负责将该区域的监测数据上报给基站，且管理节点不 是固定的，网络会定期或不定期的重新选择子区域的管理节点，分担管理节点的 负载，管理节点间不相互进行通行。层次结构的优点是管理节点不固定，定期或 不定期的重新更换，避免了这些管理节点成为瓶颈节点，其扩展性和自适应性要 比集中式结构好。 ( 3 ) 分布式结构 传感器网络的分布式结构是指网络中的每个节点都具有管理控制功能，节点 地位平等，采用局部化的本地算法共同完成网络管理任务。它没有中心控制节点， 不会因个别节点的失效造成网络整体的崩溃。在分布式结构中，节点之间相互联 系，数据可以选择多跳路径传输，它的扩展性和自适应性都比上面两种结构好， 缺点是不利于集中管理，实现复杂。 本文设计的路由算法是针对大规模均匀分布的网络，将采用分布式的拓扑结 构，即每个节点在网络中的地位是平等的，都有管理控制功能。 2 2 无线传感器网络路由算法介绍 无线传感器网络路由协议的目的是完成数据收集，即周期性的将数据从源节 点发送到目的节点，路由协议主要包括两大功能：寻找数据传输路径和对传输路 基于区域划分的无线传感器网络路由算法研究 径进行维护1 3 。本小节将从路由算法的设计要求开始，简要介绍现有的三大主流 路由协议，接着重点介绍传感器网络空洞问题及采取的策略。 2 2 1 无线传感器网络路由协议设计要求 无线传感器网络是一种全新的信息获取和处理技术，基于自身的特性，具有 能量约束强，移动性差，网络节点数目大等特点，传统的a dh o c 网络路由协议并 不适用于无线传感器网络。因此需要设计专门针对传感器网络特性的路由协议， 协议不能太复杂、不能在节点中保存太多的状态信息和路由信息；同时应尽量避 免发送冗余信息和过多的控制信息，减少能量消耗。其要求具体如下【3 l 】： ( 1 ) 能量有效性。对于电池供电的传感器网络节点，利用有限的能量高效地 完成数据收集任务是传感器网络路由算法设计的关键。 ( 2 ) 网络生命周期。传感器网络能量受限的特点决定了均衡节点间的能量消 耗以延长网络生命周期是协议设计的首要目标。 ( 3 ) 负载均衡。传感器网络节点采用多对一模式进行数据传输，越靠近s i n k 的节点，网络负载越重，因此路由协议设计时应当考虑节点间的负载均衡，降低 关键节点的流量，均衡各个节点的数据转发量，避免“热区节点 的出现而导致 大面积数据阻塞。 ( 4 ) 较短的通信距离。由于无线通信的能量消耗跟距离的n 次方成正比，所 以减少相邻节点间的通信距离能有效的节约能量，提高能效比。 ( 5 ) 不必频繁更新路由表。传感器网络中节点一旦部署完毕，是很少再移动 的，所以节点的下一跳不需要频繁更换。 ( 6 ) 良好的扩展性。无线传感器网络的规模大，要求路由协议具有良好的可 扩展性，设计简单高效的可扩展路由协议是传感器网络的一个重要原则。 ( 7 ) 自适应能力。传感器网络会由于环境恶劣、节点发生故障或部分网络被 破坏，旧节点的失效和新节点的加入，节点位置变化等因素造成网络拓扑结构的 变化，因此设计的路由协议必须具有自适应性，能够自主的调整传输路径，保证 网络的连通性。 ( 8 ) 应用相关。传感器网络路由协议具有很强的应用相关性，不同的应用环 境需要设计不同的路由协议，没有一个路由协议是万能的，能够适合所有的应用 场景。 2 2 2 无线传感器网络路由算法分类 针对无线传感器网络数据传输的特点及不同的应用环境，目前已经提出了许 多不同的路由协议，其中三大主流路由协议分别是平面型路由协议、层次型路由 协议和基于地理位置信息的路由协议。平面型路由协议的关键技术是数据在节点 间的传输问题，以及数据冗余的处理；层次路由协议主要是通过簇头节点转发数 8 硕二i 二学化论文 据，网络的拓扑结构具有很好的扩展性；地理位置信息路由协议利用节点的地理 位置信息把数据转发到目的节点。 ( 1 ) 在平面型路由协议中，除汇聚节点外的所有节点具有相同的资源和功能， 节点地位相等，形成完全意义上的对等网络，节点间使用局部操作和信息反馈来 生成路由，执行数据收集和路由转发任务。平面路由协议以数据为中心，由汇聚 节点发出查询请求，节点收到查询请求后进行数据收集，将数据沿着接收消息的 路径以相应的路由协议转发回汇聚节点，网络中个别节点的失效不会对其他节点 的数据传输造成严重影响。 平面路由协议的优点是简单易操作、不需要维护网络结构，所有节点地位平 等，不会产生瓶颈效应，因此具有较好的健壮性。 平面型路由协议有基于协商的路由协议( s p i n ，s e n s o rp r o t o c o l sf o r i n f o r m a t i o nv i an e g o t i a t i o n ) t 1 0 】，定向路由( d d ，d i r e c t e dd i f f u s i o n ) t 1 ，能量感知 多路径路由协议【3 2 1 以及能量平衡链分布式算法( b e c ，e n e r g yb a l a n c e dc h a i n ) 3 3 】 植 号手o s p i n 协议是第一个以数据为中心的路由协议，该协议以抽象的元数据对数据 进行命名。当节点产生或收到数据后用包含元数据的a d v 消息向邻节点通告， 需要数据的邻节点用r e q 消息提出请求，数据通过d a t a 消息发送到请求节点。 该协议有效解决了信息爆炸和资源浪费等问题。 d d 定向路由引入梯度的概念，网络中的节点根据接收到的兴趣消息建立源 节点到汇聚节点的梯度，即源节点到汇聚节点数据传输的最优路径，当有数据经 过最优路径时，中间节点使用本地化算法进行数据融合，减少网络数据量，节省 网络能量。 后两种算法具体介绍参见2 3 2 。 ( 2 ) 层次型路由协议通常又称为分簇路由协议，其基本思想是算法采用一定 的规则选择一定数量的节点作为簇头节点，其他没被选中的节点作为簇内节点， 簇内结点按照就近原则寻找自己所在的簇及簇头节点，然后簇头节点收集簇内结 点的信息并加以处理后转发到s i n k 节点，簇头节点之间不进行数据转发，为了均 衡网络中的能量消耗，需要定期或不定期地重新选择簇头节点。 由此可知在分簇路由协议设计中通常包括三个阶段：一是设计簇头选择算法， 簇头的选择基于节点的剩余能量、节点到s i n k 节点的距离、节点的位置、簇内通 信代价等因素；二是簇的形成，当簇头节点产生后，将广播自身已成为簇头节点 的消息给周围的节点，收到消息的节点根据接收信号的强弱确定所要加入的簇； 最后一个阶段是簇的路由，即簇内节点将监测到的数据传输给簇头，经簇头汇聚 处理后转发给s i n k 节点。 分簇路由协议的优点有： 9 基于区域划分的无线传感器网络路由算法研究 ( 1 ) 在分簇路由协议中，其分布式的拓扑结构便于管理，能够对网络变化做 出快速反应，具有良好的可扩展性，适用于大规模的网络； ( 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 ) ”j 是最早被提出来的分簇路由协议，它以循环的方式随机选择簇头节点，将网络负 载平均分配到每个节点中以均衡网络能耗，延长网络的生命周期。其后提出的许 多分簇路由算法都是在l e a c h 基础上演化出来的，例如能量有效分布式层次路 由算法( h e e d ，h y b r i de n e r g y - e f f i c i e n td i s t r i b u t e dc l u s t e r i n g ) 3 4 】、基于能量有效的 门限感知路由算法( 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 k p r o t o c 0 1 ) t 14 1 、能量感知消息路f l j ( e c m r ，e n e r g y c o n s c i o u sm e s s a g er o u t i n g ) 3 5 1 等。 h e e d 协议的设计目标是通过高效成簇，均匀分簇以最大化网络生命周期。 它为网络设置了两个参数，主参数依赖于节点的剩余能量，用于随机选取初始簇 头节点集合，节点剩余能量越多，成为簇头的概率越大；次参数依赖于簇内通信 代价，用于确定落在多个簇范围内的节点最终属于哪个簇，以及平衡簇头之间的 负载。 t e e n 协议采用类似l e a c h 协议的成簇算法，只是在数据传输阶段为网络 设置了硬、软2 个阈值，当节点收集到的数据高于硬阀值或者节点感应到的数据 变化值大于软阀值时，节点必须打开发射机向簇头节点报告数据，其他时间节点 关闭它们的发射机，节省能量。 e c m r 是多跳分簇路由协议，算法假设簇头节点固定且能量不受限，能够与 簇内节点直接通信，簇内节点使用d i j k s t r a 算法选择路由下一跳，节点间的权值 定义不仅考虑了节点间的通信耗费，还考虑了节点的剩余能量，节点负载等因素。 ( 3 ) 在基于地理位置信息的路由协议中节点需要获取自己的地理位置信息以 及目的节点的地理位置信息，利用这些地理位置信息作为路由选择的依据，按照 一定的策略转发数据到目的节点。 基于地理位置信息的路由协议分为两类，一类是使用地理位置信息作为其他 路由算法的辅助。这类路由协议有最小能耗路由算法g l b d m e c r 3 6 j ，基于最优 化距离的地理位置路由协议( o d g r ，o p t i m a ld i s t a n c eg e o g r a p h i cr