（计算机科学与技术专业论文）基于边界检测的无线传感器网络能量密度路由算法研究.pdf

r e s e a r c ho ne n e r g y d e n s i t yr o u t i n ga l g o r i t h mf o rw i r e l e s ss e n s o r n e t w o r k sb a s e do nb o u n d a r yr e c o g n i t i o n b y l u oj i a n h u i b e ( s c h o o lo fc o m p u t e rs c i e n c e ，n a t i o n a lu n i v e r s i t yo fd e f e n s et e c h n o l o g y ) 2 0 0 5 a t 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 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 nu 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 ur e n y o n g m a y , 2 0 1 1 0叭ml驯06 09iiiiiy 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得 的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人 和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由 本人承担。 作者签名： 罗蕴搏 日期：0 引年d 珀岁日日期：0 7 l 年d 歹月岁日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校 保留并向国家有关部门或机构送交论义的复印件和电子版，允许论义被查阅 和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论 文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“) 作者签名： 导师签名： 弓瑾强 位仁彰 日期：2 口1 年啄月；7 日 日期： 知，j 年j 月弓1 日 摘要 无线传感器网络是一种在没有固定基础设施的环境下构建的由传感器节点临 时组成的自组织无线网络，节点的能量供应、计算能力和通信能力等资源都非常 有限，所以如何延长网络的生存周期以及提高网络的工作效率足无线传感器网络 的关键。 由于无线传感网络的这些特性和要求，网络的拓扑识别就成为了无线传感器 网络研究中的霞要问题，而边界识别是核心问题。更重要的是，无线传感器网络 对信息的采集、处理和传输都需要有效的路由算法作为基本保障，而与边界识别 的结合可以提供更好的路由效率。 本文首先对现有的边界识别算法和无线传感器网络经典路由算法进行了深入 的研究和分析，结合物理学上密度的概念，定义了一个新的能餐密度的概念，即 能量密度的取值大小是与节点的剩余能量成j 下比，与节点到s i n k 节点的距离的平 方成反比。在此基础上，提出了一种新的无线传感器网络路由算法一一无线传感 器网络基于边界检测的无线传感器网络能量密度路由算法。 在基于边界检测的无线传感器网络的能量密度路由算法中，网络首先进行边 界识别，标记边界节点，网络中的节点总是把数据转发给下一个比自己离s i n k 节 点更近而且能量密度是节点常规传输方式所到达的除了边界标记节点以外的所有 邻接节点中的最大者。当所有满足比：常点自身离s i n k 节点更近的节点都是已经标 记的节点时，则当前节点将数据回传给上一跳节点，同时将自己标记成边界节点。 在此基础上，本文还讨论了另外一种的基于边界检测的预处理能量密度路由 算法，即在网络边界识别的过程中，当边界节点都被标记后，边界节点会触发一 个节点自我发现的过程，边界周边的节点会自动检测是否能找到满足路由条件的 下一跳节点，如果能则不作处理，如果不能则将自己也标记成边界节点，并通知 邻接节点。 接下来，论文介绍了用j a v a 语言来实现本文算法的仿真过程，对其仿真结果 进行了分析，对基于边界检测的能量密度路由算法的关键参数进行了探讨和研究， 并得出了其变化对算法性能影响的规律。 最后，论文对全文进行了总结和对未来的研究工作进行了展望，并指出了未 来研究工作的方向和重点。 关键词：无线传感器网络；边界识别；路由算法；能量密度 i l a bs t r a c t w i r e l e s ss e n s o rn e t w o r ki sak i n do fs e lf - o r g a n i z e dt e m p o r a r y w i r e l e s sn e t w o r k c o n s t r u c t e db ys e n s o rn o d e su n d e rt h ee n v i r o n m e n to fn of i x e di n f r a s t r u c t u r e t h e e n e r g ys u p p l y ，c o m p u t i n g a n dc o m m u n i c a t i o np o w e ro f t h en o d e sa r es e r l o u s l y l i m i t e d s oh o wt oe x t e n dt h el i f e t i m e o ft h en e t w o r k sa n d o rl n c r e a s e n e t w o r k e f f i c i e n c ya r et h ek e yt or e a l i z et h e m b e c a u s eo ft h e s ef e a t u r e sa n dr e q u i r e m e n t s ，t h en e t w o r kr o u t i n ga l g o r i t h ma n d t o p o i o g yr e c o g n i t i o n h a v eb e c o m ei m p o r t a n t r e s e a r c hi s s u e s h e r eb o u n d a r y r e c o g n i t i o ni st h ec o r eo ft o p o l o g yr e c o g n i t i o ni nw i r e l e s s s e n s o rn e t w o r k s am o r e i m p o r t a n ti s s u ei s ，t h ei n f o r m a t i o nc o l l e c t i n g ，p r o c e s s i n ga n d t r a n s m i s s i o nmw l r e l e s s s e n s o rn e t w o r kr e q u i r ee f f e c t i v er o u t i n ga l g o r i t h ma s t h eb a s i cg u a r a n t e e ，w h l l et h e c o m b i n a t i o no fr o u t i n ga l g o r i t h m w i t hb o u n d a r yr e c o g n i t i o nc a np r o v l d e b e t t e r r o u t i n ge f f i c i e n c y i nt h i sp a p e r ，c o n s i d e r i n gt h ee x i s t i n gb o u n d a r yr e c o g n i t i o na n dc l a s s l cr o u t m g a i g o r i t h mf o rw i r e l e s ss e n s o rn e t w o r k s ，an o v e ls t a t e p a r a m e t e r ，e n e r g yd e n s l t y ，l s d e f t n e df o re a c hn o d eb a s e d o nt h ep h y s i c a lc o n c e p td e n s i t y e n e r g yd e n s i t y 1 s d e s i g n e dt ob ep o s i t i v ep r o p o r t i o nt o t h er e m a i n i n ge n e r g yo fn o d ea n df a l lo f fa st h e s q u a r eo ft h ed i s t a n c eb e t w e e ni t s e l fa n dt h es i n kn o d e a c c o r d i n g l y ，an e wr o u t l n g a i g o r i t h m b o u n d a r yr e c o g n i t i o n - b a s e de n e r g yd e n s i t yr o u t i n ga l g o r i t h m ，l sp r o p o s e d f o rw i r e l e s ss e n s o rn e t w o r k s i nb o u n d a r yr e c o g n i t i o n b a s e de n e r g yd e n s i t yr o u t i n ga l g o r i t h m ，t h e n e t w o r k n r s t l yr e c o g n i z et h eb o u n d a r yo ft h en e t w o r ka n dm a r kt h eb o u n d a r y n o d e s e a c h n o d ei nt h en e t w o r kt r a n s m i t sd a t at oo n l yo n eo ft h e i ra d j a c e n tn o d e si nt h ec o m m o n t r a n s m i t t a n c er a d i u s t h ea d j a c e n tn o d ei ss e l e c t e db yt w o c o n d i t i o n s o n ei st h a i t s d i s t a n c et os i n kn o d eb e c o m e ss m a l l e r ，t h eo t h e ri st h a ti t se n e r g yd e n s i t y 1 s1 a r g e s to f t h ea d j a c e n tn o d e st h a ts a t i s f yt h ef i r s tc o n d i t i o ne x c e p tt h em a r k e dn o d e s w h e n a l l t h en o d e ss a t i s f yt h ef i r s tc o n d i t i o na r em a r k e dn o d e s ，t h er e c e n tn o d et r a n s m l t s 1 t s d a t ab a c kt oi t sl a s tn o d ea n dm a r ki t s e l fa sb o u n d a r y o nt h eb a s i so ft h ea b o v ea l g o r i t h m ，t h i sp a p e rd i s c u s s e sa n o t h e rt y p eo fp r l o r b o u n d a r yr e c o g n i t i o n b a s e de n e r g yd e n s i t yr o u t i n g a l g o r i t h m ，i nw h i c ha f i t e r t h e n o d e si nt h eb o u n d a r ya r em a r k e d ，t h e yw o u l ds t a r t as e l f - d e t e c t i n gp r o c e s s lh e n o d e sa r o u n dt h eb o u n d a r yw i l la u t o m a t i c a l l y r o u t i n gc o n d i t i o n sc a nb ef o u n d i ft h en o d e s i i i d e t e c tw h e t h e rt h en o d e ss a t i s f y i n gt h e c a nb ef o u n d ，t h e nn o t h i n gi sd i s p o s e d 彤! l 。 f t 论文 i ft h en o d e sc a nn o tb ef o u n d ，t h e nt h er e c e n tn o d em a r k si t s e l fa st h eb o u n d a r yn o d e s a n di n f o r m st h ea d j a c e n tn o d e s n e x t ，t h i sp a p e ri n t r o d u c e st h es i m u l a t i o np r o c e s sb yu s i n gt h ej a v al a n g u a g et o r e a l i z et h er o u t i n ga l g o r i t h ma n da n a l y z e st h er e s u l t so ft h es i m u l a t i o n f u r t h e r m o r e ， t h ep a p e re x p l o r e st h ei n f lu e n c eo fs o m ek e yp a r a m e t e r su s e di nt h eb o u n d a r y r e c o g n i t i o n b a s e de n e r g yd e n s i t yr o u t i n ga l g o r i t h ma n dg e t st h er e g u l a r i t y o ft h e p a r a m e t e r s c h a n g ei m p a c t i n go nt h ep e r f o r m a n c eo fa l g o r i t h m f i n a l l y ，t h ep a p e rm a k e s as u m m a r ya n dd r a w st h ep r o s p e c to fr e s e a r c h e s p e c i a l l y ，i tp o i n t so u tt h ef o c u sa n dd i r e c t i o ni nt h ef u t u r er e s e a r c h 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 ，b o u n d a r yr e c o g n i t i o n ，r o u t i n ga l g o r i t h m ， e n e r g yd e n s i t y i v j 占卜边抖 令洲的t 线f 感器l t q 络能譬密度路l f l 算法研。充 目录 摘要一i i a b s t r a c t - - - i i i 插图索引v i i 第l 章绪论l 1 1 课题研究背景和意义1 1 2 本论文主要工作概述2 1 3 论文基本结构3 第2 章无线传感器网络路由算法概述4 2 1 无线传感器网络概述4 2 2 无线传感网络路由协议设计的要求5 2 3 无线传感器网络路由协议概述6 2 3 1g p s r 算法7 2 3 2g r i d 算法9 2 3 3g l b d m e c r 路由算法”9 2 3 4g e a r 路由算法- l o 2 3 5t b f 算法1 1 2 3 6e p g r 算法l l 2 3 7g e m 算法1 2 2 4 基于位置信息的分布式路由协议的研究1 3 2 5 空洞规避以及处理1 3 2 5 1 空洞规避方法1 4 2 5 2 空洞处理方法1 6 2 6 边界识别l7 2 7 小结2 1 第3 章基于边界检测的能量密度路由算法2 2 3 1 引。言2 2 3 2 问题描述2 3 3 3 边界识别算法2 4 3 3 1 骨干图的抽取2 4 3 3 2 基本边界环的生成一2 5 3 3 3 内边界优化2 5 3 3 4 外边界优化2 6 v 顺卜f z 论艾 3 4 基于边界检测的能量密度路由算法2 7 3 4 1 能量密度的概念2 7 3 4 2 基于边界检测的能量密度路由算法的定义2 8 3 4 3 特殊边界图的处理3 0 3 5 小结31 第4 章基于边界检测的预处理能量密度路由算法与仿真实验分析3 2 4 1 基于边界检测的预处理能量密度路由算法3 2 4 2 仿真环境3 4 4 3 仿真结果比较3 5 4 4 小结3 9 结论4 0 参考文献4 3 致谢4 8 附录a 攻读学位期间发表的论文4 9 附录b攻读学位期间参与的项目5 0 v i 皋j ：边抖伶洲的丘线f 感揖h 络能量南瞍路d 1 铮法究 插图索引 图2 1 无线传感器网络系统构架一4 图2 2 传感器节点的结构5 图2 3 贪婪算法传输示例一8 图2 4 “空洞”处理8 图2 5g r i d 算法示例9 图2 6g e m 路由带有环结构的虚拟角度12 图2 7v o r o n o i 图2 0 图3 1f g p 变换示例2 4 图3 2 边界检测示意图2 9 图3 3 能量密度路由算法实例3 0 图3 4 特殊边界形状示例3 1 图3 5s i n k 节点特殊位置示例3 1 图4 1 边界检测的初始结果示意图3 3 图4 2 边界谚 别算法的最终结果示意图3 4 图4 3 不同比例节点正常死亡时传输成功的数据量3 6 图4 4 不同比例节点正常死亡时的丢包率3 7 图4 5 不同比例节点正常死亡时的单个节点平均剩余能量3 8 图4 6 不同比例节点正常死亡时的平均跳数3 8 v i i 硕上学位论文 1 1 课题研究背景和意义 第1 章绪论 随着现代科学技术的不断进步，传感器技术、微机电系统、现代网络和无线 通信等技术都有了飞速的发展，这些都推动了无线传感器网络 1 - 3 j ( w i r e l e s s s e n s o rn e t w o r k s ，w s n s ) 的产生和发展。无线传感器网络是目前国内外的研究热 点，拥有广阔的应用前景，是未来社会应用最广的网络形态之一，其建立在各类 传感器网络节点平台上，面向海陆空全方位应用需求的项目更是数不胜数、层出 不穷。无线传感器网络以其低功耗、低成本、分布式和自组织的特点带来了信息 感知的一场革命。 无线传感器网络是由大量的密集部署在监控区域的智能传感器节点构成的一 种网络应用系统，通过节点间的协作完成对物理环境的监控。传感器节点数量很 多，大多采用随机投放的方式部署，不能预先确定传感器节点的状态，节点间通 过无线信道连接，采用多跳、对等通信方式，自组织网络拓扑结构。 无线传感器网络与传统的有线和无线网络有些共同的地方，因此许多应用于 现有网络的方法被移植到无线传感器网络中。但是节点的空间部署、感知能力、 自组织通信等特性使得传感器网络和传统的有线网络有很大的不同，并且其应用 方式也决定了无线传感器网络和传统的无线网络有着不同的设计目标。后者的设 计目标是在无线或移动的环境中通过优化路由和资源管理策略，来最大化带宽的 利用率，从而为用户提供有一定质量保证的服务。而在无线传感器网络通常运行 在人无法接近的恶劣或者危险的远程环境中，采用电池等设备提供节点运行所需 要的能量，能源无法更换。除了少数节点需要移动以外，大部分节点是静止的。 无线传感器网络的节点无线通信带宽经常变化，通信覆盖范围不大，通信能 力很有限，并且网络节点常因为电源能量耗尽而被废弃，节点具有的嵌入式处理 器和存储器的计算能力也很有限。但是无线传感器网络节点的分布范围很广，数 量巨大，网络的动态性很强，感知数据流很大，所以无线传感器网络的路由算法 是无线传感器网络中的关键核心技术，是学术研究的一个重要方向。设计一个优 秀的路由算法对于无线传感器网络有着至关重要的作用。 当前，随着全球定位系统的广泛应用和定位方法的技术进步，地理位置路由 协议1 4 _ 6 l 已经成为研究的新热点。基于位置信息的无线传感网络路由算法具有原 理简单、实现容易、可以和很多已有算法相互结合和易于节省能量等特点，使其 能够有效的满足无线传感器网络应用的特点和需求，得到了很快的发展。 j 目 邻 基于边界检测的无线传感器网络能量密度路由算法研究 在地理位置路由协议中，每个节点以贪婪的方式【7 】将数据包传给自己的一跳 接节点中与目标距离最近的节点。在节点分布比较稠密并且节点分布比较均匀 的网络中，地理位置路由协议的工作效率比较高。但是当网络节点比较稀疏，节 点的分布情况比较复杂的情况下，就会使得路由空洞在网络中出现，就是不存在 地理位置路由协议中的贪婪转发策略要求的更加接近汇聚节点的下一跳邻居节 点，这样就会导致地理位置路由协议的贪婪路由失效。地理位置路由协议规避空 洞的主要方法是遇到路由空洞的时候抽取平面子图，使用面路由策略。但是如果 网络中有包含较多小空洞或者形状不规则的边界这些比较复杂的几何特征图形的 时候，地理位置路由中的绕面操作就会频繁进行操作，这种操作需要很大的能量 消耗来建立平面图消除链路，并且这种操作还会使得使空洞边缘上的节点负载过 重而提早死亡，这就会造成路由空洞越来越大。形成这种局面的主要是因为在网 络几何特征比较复杂的时候，网络图上的节点之间的几何距离并不能准确地反应 实际网络中的节点之间的连通距离，实际地理位置上接近的两个点在网络几何结 构中它们的跳数距离可能很大。良好的路由拓扑结构能够抽象几何上的局部邻近 性，也能更好的反应整个网络的拓扑特征。网络边界结构的识别能够更好地反应 网络的连通结构，可以检测和定位网络中的空洞，通过网络的边界识别就可以对 路由策略的选择进行相应的调整，从而使得地理位置路由协议中的贪婪路由算法 有更高的工作效率。 在无线传感器网络的应用当中，边界识别能够反映网络的覆盖质量，同时也 为覆盖调度和路由算法提供必要的信息，对改善网络的健康状况有重要帮助。 1 2 本论文主要工作概述 目前，无线传感器网络的的研究基本上还处于理论探索和应用初级阶段，只 有不断地将现有的传感器网络的理论知识应用到实际当中去，才能发挥出其巨大 的现实意义和作用，同时也能推动无线传感器网络的理论研究的进一步发展。 本文首先对无线传感器网络的体系结构、基本概念还有其特点及应用进行了 简要的介绍，并对传感器网络路由协议的概念和分类进行了相关的探讨。主要描 述了基于地理位置路由协议的基本思想和特点，同时还阐述了边界识别在路由协 议等方面的可能应用。 本文的重点工作在于：在研究和分析现有的边界识别算法和无线传感器网络 经典路由算法的基础上，结合物理学上密度的概念，定义了一个新的能量密度的 概念，在此基础上，提出了一种新的无线传感器网络路由算法一一无线传感器网 络基于边界识别的能量密度路由算法，并讨论了该算法的两种实现方式。 接下来，本文介绍了自己用j a v a 语言来实现了基于边界识别的能量密度路由 算法仿真的过程，分析和比较新算法与改进的g p s r 算法的实验仿真结果，得出 2 硕十学位论文 了基于边界识别的能量密度路由算法更加有效。同时，对基于边界识别的能量密 度路由算法的各个关键参数进行了分析和讨论，并得出了其变化对算法性能的影 响。 1 3 论文基本结构 论文的结构如下： 第1 章：简要介绍了本课题研究的背景和意义以及研究的主要内容。 第2 章：概述了无线传感器网络的体系结构、特点及应用，简要介绍了无线 传感器网络路由协议的概念和分类以及地理位置路由协议的基本思想和特点，并 阐述了边界识别的应用。 第3 章：主要介绍了边界识别算法以及基于边界检测的能量密度路由算法， 详细描述了算法的原理和实现步骤，以及适用的环境。 第4 章：本章节提出了一种基于边界检测的能量密度路由算法的改进，使用 预处理的方案对网络进行初始化，其中主要包括算法的原理以及对两种方案的讨 论。并且对新提出的路由算法进行了实验仿真以及性能分析。 最后对全文进行了总结，并对未来的工作进行了展望。 3 基于边界检测的无线传感器网络能量密度路由算法研究 第2 章无线传感器网络路由算法概述 路由算法和拓扑问题中的边界识别都是无线传感器网络研究中的重要问题。 无线传感器网络对信息的采集、处理和传输都需要有效的路由算法作为基本保障， 而与边界识别的结合可以提供更好的路由效率。本章首先概述了无线传感器网络 的体系结构、特点及应用，然后简要地介绍了无线传感器网络路由协议的概念和 分类以及地理位置路由协议的基本思想和特点，并且从拓扑结构的角度对边界识 别的应用进行了分析和阐述。 2 1 无线传感器网络概述 在无线传感器网络中，由于传感器的廉价性，传感器节点可以使用飞机撒布 或者人工预先布置等方式来部署在需要监控的对象内部或者附近。无线传感器网 络的系统构架如下图，通常包括传感器节点、汇聚节点和管理节点，即无线传感 器网络的三个要素是传感器、感知对象和观察者。 图2 1 无线传感器网络系统构架 如图2 1 所示【8 】，这些传感器节点通过自组织方式构建无线网络，以相互协 作的方式实施监控、数据采集以及处理网络覆盖区域中的信息。传感器节点监测 的数据沿着其他传感器节点逐跳的进行传输，在传输过程中监测数据可能被多个 节点处理，经过多跳后到达汇聚节点，最后通过互联网或卫星等其他方式到达管 理节点。远程管理中心节点可以根据实际的需要，对网络节点进行操纵、控制、 发布监测任务以及收集监测数据。 传感器节点是构成无线传感器网络的基本单元，它的特性主要是成本比较低、 体积比较小，其通信能力、感应能力和计算能力都很有限，并且它的能量不易供 4 硕士学位论文 给。所有的传感器节点在网络中的地位是相互平等的，都具有同等重要性。 汇聚节点的能量是不受限制的，相对普通的传感器节点而言，汇聚节点的存 储能力、计算能力和通信能力都要强得多。汇聚节点负责发送监测任务的指令给 其他的传感器节点，并且还要收集普通节点监测到的数据，并进行初步加工，删 除冗余信息，将最后整理出来的信息发送给管理节点。 传感器节点是一个具有信息收集和处理能力的为系统，它由传感器模块、处 理器模块、无线通信模块和能量供应模块四部分组成，如图2 2 所示【8 j 。 图2 2 传感器节点的结构 传感器模块负责监测区域内信息的采集和转换；处理器模块负责管理整个传 感器节点，存储和处理自身采集的数据和其他节点发来的数据；无线通信模块负 责与其他传感器节点进行通信；能量供应模块负责为传感器节点提供运行所需的 能量。传感器节点能量消耗的模块主要是传感器模块，处理器模块和无线通信模 块，绝大部分能量消耗在无线通信模块上。 由于传感器节点是使用电池供电的，所以一旦携带的电池电能耗尽，节点就 将无法继续工作。为了尽可能节约电能，在硬件方面应该尽量采用低功耗器件， 在没有通信任务的时候，使用睡眠调度方法，关闭发射器件；在软件方面，所有 的通信协议都要以节约电能为中心，必要时可以牺牲一些其他的一些网络性能指 标，以获得更高的电源效率，来延长网络的生命周期。 2 2 无线传感网络路由协议设计的要求 无线传感器网络是目前自组织网络中的一个研究热点，但是无线传感器网络 节点的通信能力有限，能量无法补给，移动性能比较差，网络节点数目很多，其 传感器的廉价性而常常随机部署，因为无线传感器网络有这些自身特性的限制， 传统的自组织网络路由协议并不能应用于无线传感器网络，所以我们需要设计专 门针对传感器网络特性的路由协议，该路由协议不能太复杂，因为传感器节点能 5 基于边界检测的无线传感器网络能量密度路由算法研究 量有限，所以不能在节点中保存太多的信息，并且应该尽可能避免发送冗余信息 和过多的控制信息，减少能量消耗。延长网络的生存周期， 与传统网络的路由协议相比较，无线传感器网络的路由协议的具体要求如下 【9 1 ： ( 1 ) 能量优先性。在传统的网络中，路由协议很少考虑能量消耗多少的问题， 但是对于无线传感器网络电池供电的特点，要使用有限的能量相对高效率地完成 数据收集的任务是传感器网络路由算法设计的关键。 ( 2 ) 延长网络生命周期。由于无线传感器网络能量无法补给并且携带有限的 特点，所以平衡节点之间的能量消耗，通过延长节点的生存周期来延长网络生命 周期是设计路由协议的第一目标。 ( 3 ) 流量负载均衡。在无线传感器网络中，因为所有的数据都要传输给目的 节点，越靠近目的的节点的传感器节点所承担的中继负载流量就越重，因此路由 协议设计时应当考虑节点间的负载均衡，均衡各个节点的数据转发量，不能让瓶 颈节点出现，使得大面积数据阻塞，并且导致瓶颈节点过早死亡。 ( 4 ) 通信距离比较短。因为无线通信中的能量消耗跟距离的n 次方成正比， 所以尽可能地减少相邻节点间的通信距离，就可以有效地节约能量，数据传输的 效率。 ( 5 ) 避免频繁更新路由表。传感器网络中节点一旦部署完毕，节点几乎不再 移动，网络初始化结束之后，网络路由路径频繁更新会导致能量消耗过快，所以 节点的下一跳要避免频繁更换。 ( 6 ) 可扩展性。无线传感器网络的节点数目很多，规模很大，所以要求网络 的路由协议具有良好的可扩展性，使用简单而高效的可扩展的路由协议是传感器 网络的一个重要原则。 ( 7 ) 鲁棒性。传感器网络常常部署在人迹罕至的环境或者敌方环境中，所以 网络经常会由于环境恶劣、节点发生故障而导致部分网络被破坏，旧节点的失效 和新节点的加入，周围的环境还会影响到网络的通信质量，所以这就要求网络的 路由协议必须具有自适应性，网络要有一定的容错能力，能够自主的调整数据路 由的路径，保证无线网络的连通性。 ( 8 ) 应用相关。无线传感器网络的应用环境有很丰富的多样性，所以传感器 网络路由协议具有很强的应用相关性，不同的应用环境就要使用不同的路由协议， 没有一个路由机制能够适应所有的应用环境。 2 3 无线传感器网络路由协议概述 无线传感器网络由大量能量、存储和计算能力有限的传感器节点通过多跳中 继、自组织方式构成，可以快速部署以实现对特定区域进行感知【1 0 以1 1 。在缺乏固 6 硕十学位论文 定基础设施提供通信支持的情况下，节点既是传感器，还需要提供网络中继传送 功能。无线传感器网络路由协议用于确保将传感数据从源节点通过多跳中继方式 转发到目的节点1 1 0 】。 从目前文献可以看出人们对无线传感器路由协议的认识是一个不断深入的过 程。最初还是从传统网络路由理论出发，根据节点在网络中的地位和功能不同， 将无线传感网络路由协议分为平面路由协议和分层路由协议1 1 0 以3 】两类，前者如 d i r e c t e df l o o d i n g 1 引、g o s s i p i n g 1 5 1 、s p i n 16 1 、d i r e c t e dd i f f u s i o n 1 7 1 、s e q u e n c e d d i r e c t e dd i f f u s i o n 1 8 j 等，基本上是在传统有线网络路由协议的基础上提出，基 本理论基础是泛洪( f l o o d i n g ) 和d i j k s t r a 的最短路径算法；后者如l e a c h ”】、 t e e n 2 0 l 等，是平面路由协议的扩展，实质对网络实行“分而治之”，并在划分、 调整簇的时候综合考虑节点剩余能量等要素。上述路由协议往往不能完全适应无 线传感器网络以“数据为中心的应用模式。鉴于此，近来人们提出了一些新的 路由策略，比如基于位置信息的路由 2 1 - 2 2 】、能量感知路由【2 3 1 、能量密度路由【2 4 1 、 机会路由【2 5 】等，这些协议主要根据本地信息自主做出路由判决，节点的地位和功 能完全是临时的、动态变化的，对后续节点传送的可能情况也并没有太多考虑。 用到的本地状态信息包括节点位置( 坐标) 信息、节点间相对位置或信号到达角 度( 方向) 信息、节点剩余能量和消耗模式、链路质量等。显然，在这种缺乏端 到端全局状态信息的完全分布式路由算法情况下，要保证数据最终成功传送，需 要利用节点位置信息，下文我们主要以基于节点位置信息分布式路由协议为例进 行阐述。 本文中所讨论的基于地理位置信息的路由协议，是无线传感器网络路由协议 的一个重要组成部分。这种路由协议在适应性、可扩展性以及能量优先性等方面 都蕴藏着巨大的优势。基于地理位置的路由算法在实现的过程中，节点需要获得 三种的地理位置的信息，首先是节点本身的位置，还有节点全部下一跳邻居节点 的位置以及目的节点的位置，这些地理位置信息是通过g p s 或者各种定位算法来 获得的。所以，在选择下一跳节点的过程中，节点利用这些获得的地理位置信息 来进行路由，这种地理位置信息在整个路由选择中起着辅助性或确定性的作用。 下面将介绍几种典型的基于地理位置信息的路由方法。 2 3 1g p s r 算法 在基于地理位置信息的路由算法中，g p s r 算法是其中的一个典型性算法， 假设全部的传感器节点都知道自己的地理位置信息，使用贪婪算法来建立路由， 从而实现统一的编址。在网络系统中，如果目标节点是静止的，那么在网络的初 始阶段可以通过s i n k 节点的一次性泛洪广播来通知全部节点自己的位置信息，这 样全部的节点就都知道s i n k 节点的位置信息。当节点上产生或者收到数据，我们 7 基于边界检测的无线传感器网络能量密度路由算法研究 采用贪婪算法，此时我们只需做少量的数据存储，然后算法选择离s i n k 节点最近 的一跳的邻居节点作为它的下一跳，依次直到数据传输到s i n k 节点为止。如图 2 3 所示： 图2 3 贪婪算法传输示例 上图中，节点s 为要将发送数据的节点，节点d 为s i n k 节点，节点s 的一 跳邻居节点有节点a 、b 、c 、e 和节点f 。根据上述贪婪路由算法，为了使到达 s i n k 节点之前的跳数最少，那么节点b 即为下一跳节点，从而减少了在路由时的 节点中因排队和处理到来的时延。该路由算法的好处是不必维护网络的链路状态， 每个节点只要直到周围邻居节点的位置信息，每一次的转发数据都是局部路由选 择，不需要储存路由信息表，这样就节省了能量的消耗，并且还降低了节点的内 存和处理要求，使得网络具有了良好的可扩展性和鲁棒性。 不幸的是基于这种机制的路由算法会带来另外一个问题，我们称之为“空洞” 问题，这种“空洞”问题就是如果节点的所有邻居节点都比节点本身倒s i n k 节点的 距离要远，那么按照原有的路由机制就无法继续选择下一跳，这时就需要处理“空 洞”的算法。 g p s r 的“空洞”算法是使用右手法则，如图2 4 所示【z l j ： 图2 4 “空洞”处理 右手法则的具体内容是，当算法在初始化的时候，要计算所有遇到“空洞”的 节点的右手法则绕行路径，并且储存在节点里，考虑到节点容易失效的这个因素， 8 硕上学位论文 我们必须要周期性地计算这个右手法则绕行的线路。 但是这种“空洞”处理方法缺点是太过于复杂，对于无线传感器网络来说，其 存储的能量和计算能力都是有限的，所以对于“空洞 处理方法是不适用的。 2 3 2g r i d 算法 g r i d 是一种在自组织网络中重要的路由机制，这种机制使用地理栅格来构 建分层网络的结构。在这种路由机制中，整个网络由一些一定大小的方格组成， 其中一个方格代表一个区域，每个区域有一个节点承担在不同方格之间传输中继 转发数据包，这个节点就是该区域的l e a d e r 节点。整个网络在划分成不同的方格 的时候，将方格赋予了不同的编码。如图2 5 中1 2 6 】节点a 、d 所在方格的编码分 别为( 1 ，o ) 、( 4 ，2 ) ，方格中的所有节点共享所在方格在划分的时候被赋予的这个 编码，当在方格之间有数据分组需要中继传递的时候，就先查询不同的方格编码，。 按照方格的编码顺序反应的对应的位置关系来在方格之间中继需要转发的数据 包，一直到该数据包转发到目的节点，整个算法过程结束。 2 1 o 方 ，o oo 彳c 一。 o 旭 o o f o o a o l e a d e r 1 ，点 。 普通节点 叫分组转发方向 o1234 图2 5g r i d 算法示例 g r i d 网络结构简化和优化了很多路由问题，因为方格之间的节点距离都很 近，所以让不是l e a d e r 的节点也参与中继转发数据包显然是多余的，在网络进行 洪泛的过程中，只有方格中的l e a d e r 节点才参与中继数据包；因为在网络的路由 过程中，方格在划分的时候其编码反应了空间的位置信息，所以路由路径的选择 也可以完全基于相邻方格之间的拓扑关系信息进行。而且非l e a d e r 的普通节点仅 仅需维护联系到自己所属方格的l e a d e r 路由路径就可以，每个方格的l e a d e r 节点 也只需维护到其它方格的