（计算机应用技术专业论文）无线传感器网络地理位置路由和空洞处理机制研究.pdf

无线传感器网络地理位置路由和窄洞处理机制研究 摘要 无线传感器网络中的地理位置路由算法通常采用贪婪转发机制，选择更加接 近目的节点的邻接节点作为数据转发的下一跳节点。在传感器节点密度较高且节 点能量充足的情况下，算法效率较高，路由接近最优或次优。但是当节点部署不 均匀或部分节点能量耗尽导致节点密度下降时就容易出现路由空洞现象，即节点 需要转发数据，却发现不存在更加接近目的节点的邻接节点这种现象。路由空洞 的存在破坏了网络的连通性，可能导致数据传输的失败。由于节点只需根据本地 局部信息做出路由抉择，这类算法能够适应拓扑变化较快的网络，可扩展性较好。 然而，对路由空洞的处理通常需要全局网络信息，不能做到真正局部化，影响到 路由算法的实用性。 为了尽可能避免路由通向空洞，论文首先提出一种具有预测功能的邻居节点 反馈机制。该机制通过将空洞信息反馈给数据流的上游节点，通知上游节点避开 向路由空洞方向转发数据，降低数据到达空洞节点的次数。该机制也能避免剩余 能量水平较低的节点由于转发其他节点的数据而耗尽能量，尽可能延缓新的路由 空洞的形成。 为处理路由空洞，论文提出一种孤立子树重路由算法，基本思想是将遭遇路 由空洞的部分节点看成一棵孤立子树。算法利用子树对应的局部网络信息，选择 子树中关键节点作为子树成员节点数据发送的目标节点，并利用关键节点的关键 链路建立起到达汇聚节点的通路。进而，论文又提出一种分布式的孤立子树拆分 算法，查找并利用子树中存在的多个关键节点。论文中，子树成员节点根据就近 整合的原则选择距离最近的关键节点作为其数据发送的目标节点。整个孤立子树 被拆分为多个更小规模的子树，使得关键节点的通信负载得到均衡。 关键词：无线传感器网络；地理位置路由；路由空洞；孤立子树；邻居反馈； i l 硕i ：学位论文 a b s t r a c t g e o g r a p h i cr o u t i n ga l g o r i t h m sf o rw i r e l e s ss e n s o rn e t w o r k su s u a l l yu s eg r e e d y i d e at os e l e c ta na d ja c e n tn o d e ，w h i c hi sc l o s e s tt ot h ed e s t i n a t i o nn o d e ，a st h en e x t h o pn o d e ，a n dt h e nf 1 0 r w a r dd a t at oi t w h e nt h es e n s o rn o d e s d e n s i t yi sr e l a t i v e l y h i g ha n dt h en o d e s r e s i d u a le n e r g yi sg e n e r a l l ys u f f i c i e n t ，t h ea l g o r i t h mi se m c i e n t e n o u g ha n dt h er o u t i n gp a t hn e a r l yi st h es h o r t e s tp a t h b u tw h e nt h en o d e s d e n s i t y b e c o m e s1 0 w e rd u et ou n e v e nn o d ep l a c e m e n to rp a r to fn o d e s f a i l u r e ，i tl e a d st ot h e a p p e a r a n c eo fr o u t i n gv o i d s t h a ti s ，an o d ec a nn o tf i n da na d ja c e n tn o d ec l o s e rt o t h ed e s t i n a t i o n n o d e ， t of o 刑a r dd a t ag r e e d i l y t h ee x i s t e n c eo fr o u t i n gv o i d s u n d e m l i n e st h en e t w o r kc o n n e c t i v i t y a n de v e nm a yl e a dt ot h ef a i l u r eo fd a t a t r a n s m i s s i o n b e c a u s ee a c hn o d em a k e s r o u t i n gd e c i s i o na c c o r d i n gt ot h el o c a l i n f 6 r n l a t i o n ， t h e s ea l g o r i t h m sa r es c a l a b l ea n dc a na d a p tt on e t w o r k sw i t h r a p i d c h a n g e si nt o p 0 1 0 9 y h o w e v e r ，s i n c et h er o u t i n gv o i d sh a n d l i n gt e c h n i q u e so n e n r e q u i r e9 1 0 b a li n f o r m a t i o nt og e n e r a t eap l a n a r g r a p ho ft h ew h o l en e t w o r k ， c o n s e q u e n t l yt h e s et e c h n i q u e sa r en o tt r u l y1 0 c a l i z e d ，a n dw i l l a f f e c tt h er o u t i n g a l g o r i t h m s p r a c t i c a l i t y t oa v o i dr o u t i n gv o i d s ，t h ep a p e rp r o p o s e sap r e d i c t i v en e i g h b o r h o o df e e d b a c k m e c h a n i s m o n c ean o d ee n c o u n t e r sar o u t i n g v o i d ，i tw i l ln o t i f yt h e i ru p s t r e a mn o d e s a b o u tt h er o u t i n gv o i d t h eu p s t r e a mn o d e st h e na d j u s tt h er o u t i n gi n f o r m a t i o nt o a v o i df 0 r w a r d i n gd a t at ot h i sd i r e c t i o n ，t h u sr e s u l t i n gi nal o w e rf r e q u e n c yo ft h e s t a r t u po fv o i dh a n d l i n gt e c h n i q u e s t h em e c h a n i s ma l s oc a np r e v e n tt h en o d e sw i t h l o w e rr e s i d u a le n e r g yf - r o md e p l e t i n gt h e i re n e r g yr a p i d l yd u et of o r w a r d i n go t h e r n o d e s d a t a ，s l o wt h ef b m a t i o no ft h en e wr o u t i n gv o i da sm u c ha sp o s s i b l e i no r d e rt oh a n d l i n gt h ea i b o v ep r o b l e m ，t h i sp a p e rp r o p o s e sa ni s 0 1 a t e ds u b t r e e r e r o u t i n ga l g o r i t h mb a s e do nt h ei d e ao fl o o k i n gu p o nt h en o d e s ，w h i c hw i l lr o u t e d a t at oar o u t i n gv o i d ，a sa ni s o l a t e ds u b t r e e t h ea l g o r i t h mo n l yu s e st h el o c a l i n f b r m a t i o nc o r r e s p o n d i n gt ot h es u b t r e et o6 n dt h ek e yn o d eo ft h es u b t r e e a l l m e m b e rn o d e so ft h es u b t r e es e l e c tt h ek e yn o d ea st h e i rl o c a lt a r g e tn o d e ，a n du s et h e k e yl i n k st oe s t a b l i s hn e wp a t h st ot h es i n kn o d e t h e n ，t h ep a p e ra d d i t i o n a l l y p r o p o s e sad i s t r i b u t e di s o l a t e ds u b t r e es p l i ta l g o r i t h mt o6 n da n du s em u l t i p l ek e y n o d e so ft h es u b t r e e i nt h ea l g o r i t h m ，e a c hm e m b e rn o d eo ft h es u b t r e es e l e c t st h e c l o s e s tk e yn o d ea si t s1 0 c a l t a r g e tn o d ea c c o r d i n gt ot h ep r i n c i p l eo fp r o x i m a l i n t e g r a t i o n a sar e s u l t ，t h ei s o l a t e ds u b t r e ei ss p l i t t e di n t om u l t i p l es m a l l e rs u b t r e e s i i l 无线传感器网络地理位置路巾和窄涧处理机制研究 t h ec o m m u n i c a t i o nb u r d e no ft h ek e yn o d e si sb a l a n c e d k e yw o r d s ：w i r e l e s ss e n s o rn e t w o r k s ；g e o g r a p h i cr o u t i n g ；r o u t i n gv o i d s ；i s o l a t e d s u b t r e e ；n e i g h b o r h o o df e e d b a c k ； i v 硕l ：学位论文 插图索引 图1 1 路由空洞示例一2 图2 1 无线传感器网络体系结构5 图2 2 贪婪转发示例8 图2 3 绕过路由空洞的路径示例8 图2 4r g n 平面图和g g 平面图1 1 图2 5 凸面遍历示例1 2 图2 6 节点代价增加示例1 4 图2 7 节点代价降低示例1 4 图3 1 空洞传输反馈机制示例1 8 图3 2 能量密度路由算法示例1 9 图3 3 不同比例节点正常死亡时传输成功数据量2 3 图3 4 不同比例节点正常死亡时丢包率2 4 图3 5 不同路径长度对应的传输成功的数据量2 4 图3 6 三种不同的节点部署方案2 6 图3 7 节点死亡一定比例时传输成功数据量2 7 图3 8 节点死亡一定比例时的丢包率2 7 图3 9 传输成功一定数量数据包时死亡节点数2 8 图3 1 0 传输成功的数据包中采用长距传输的数量2 8 图3 1 1 节点剩余能量水平2 9 图4 1 孤立子树示例一3 2 图4 2 孤立子树重路由示例3 2 图4 3 发现孤立子树的消息传递和处理过程3 3 图4 4 选择孤立子树关键节点的过程3 4 图4 5 孤立子树成员节点更新目标节点的过程3 5 图4 6 网络路由拓扑图3 8 图4 7 不同比例节点正常死亡时传输成功数据量3 8 图4 8 不同比例节点正常死亡时丢包率3 9 图4 9 不同路径长度对应的传输成功的数据量3 9 图4 1 0 成功传输一定数据量时的平均路径长度4 0 图5 1 孤立子树示例二4 2 图5 2 孤立子树拆分示例4 2 图5 3 孤立子树拆分算法中子树成员节点路由更新过程4 4 v i i 无线传感器网络地理位置路| l j 和窄洞处理机制研究 图5 4 两种子树优化算法形成的路由拓扑图4 7 图5 5 不同比例节点正常死亡时传输成功数据量4 8 图5 6 不同比例节点正常死亡时丢包率一4 8 图5 7 传输成功的数据包中采用长距传输的数量4 9 图5 8 成功传输一定数据量时的平均路径长度4 9 v i 硕1 ：学位论文 附表索引 表3 1 仿真实验参数列表2 2 i x 硕i ：学位论文 第l 章绪论 1 1 课题研究背景和意义 随着科学技术的不断发展和进步，集传感器技术、微机电系统( m i c r oe l e c t r o m e c h a n i s ms y s t e m ，m e m s ) 、片上系统( s y s t e mo nc h i p ，s o c ) 、无线通信技术、数 据存储和处理等技术于一体的无线传感器网络( w i r e l e s ss e n s o rn e t w o r k s ，w s n s ) 是一种全新的信心获取和处理技术，它被认为是2 1 世纪最重要的技术之一【1 1 。 t e c h n o l o g yr e v i e w 杂志将无线传感器网络列为未来改变人类世界的十大新兴技 术之首，无线传感器网路的重要性由此可见一斑。 无线传感器网路由大量微型的传感器节点通过随机抛洒或者人工部署的方式 分布于感兴趣的目标区域内部或附近，通过多跳、自组织的方式快速形成一个无 线网络并覆盖目标区域，从而实现对目标区域的实时监测。传感器节点利用内置 的各种传感器实时地采集目标区域内的各种环境信息或者监测对象的状态信息， 并将数据通过多跳中继方式传送到对这些信息感兴趣的用户。在这个过程中，网 络中的传感器节点不仅感知和采集数据，而且参与数据的传递【2 】。 无线传感器网络正是凭借其低成本、快速部署、自组成网、可扩展性强等特 点【3 】，越来越多地受到了各界的重视，目前正广泛应用于社会生活的各个领域。 无线传感器网络路由协议【4 】是无线传感器网络中一项关键的支撑技术，一直 以来都是研究的热点之一，其主要任务包括两个方面：第一，建立数据源节点和 目的节点之间的通路；第二，沿着通路可靠地传输监测数据。由于传感器节点通 常计算和存储能力以及能量供应十分有限，研究人员提出了多种路由协议旨在保 证路由算法效率的同时节省能量消耗。 近年来，随着全球定位系统( g 1 0 b a lp o s i t i o n i n gs y s t e m ，g p s ) 6 】的广泛应用以 及定位机制【。7 】的发展进步，地理位置路由协议【9 】逐渐成为研究的热点。与基于网 络拓扑转发数据的路由协议不同，地理位置路由协议利用地理位置信息转发数据。 大多数地理位置路由协议通常只需要一跳范围内的邻接节点的地理位置信息，不 需要建立和维护从数据源节点到达目的节点的整个路由。传感器节点不需要存储 路由信息表，并且也不需要为了更新路由状态而传递路由信息。这种只需进行局 部运算以及无状态的特征使得地理位置路由操作非常简单，并且具备良好的可扩 展性。 在地理位置路由协议中，节点在转发数据时主要采用的是原理简单的贪婪转 发策略】，总是将数据转发给局部最优的下一跳节点，即更加接近目的节点的邻 无线传感器列络地理位冒路由和窄洲处理机制研究 接节点。因为如果允许将数据转发给距目的节点更远的节点，就可能形成路由回 路，数据将永远不能到达目的节点。但是即便如此，贪婪转发也存在失效的情况。 如果一个节点需要转发数据，但是却发现其邻接节点距目的节点的距离比自身更 远，也就是说，不存在贪婪转发策略要求的更加接近目的节点的邻接节点。这种 现象就称为路由空洞【】，如图1 1 所示。图中节点x 需要转发数据，但是节点x 的邻接节点w 和y 距目的节点d 的欧式距离比其自身更远，不存在距离更近的 邻接节点，那么节点x 遇到了路由空洞，节点x 成为空洞节点，图中不包含任何 节点的斜线区域即为一个路由空洞。 图1 1 路由空洞示例 路由空洞现象既有可能是因为受到环境因素( 如湖泊，建筑物等) 的影响，网 络覆盖区域内的传感器节点部署不均匀所导致，也有可能是由于网络中部分传感 器节点发生故障或者能量耗尽而退出网络导致节点密度下降所引起。前者形成的 路由空洞通常不可避免，并且贯穿网络运行的始终。后者则由于无线传感器网络 本身拓扑随时间动态变换较快的特点而不能准确预测。尽管在网络区域部署较高 密度的传感器节点能够降低路由空洞出现的可能性，但是由于障碍物的存在、节 点存在发生故障的可能性或者在网络边缘地带，路由空洞依然可能出现。这时如 果只采用贪婪转发策略，就会出现丢包现象，尽管实际上可能存在到达目的节点 的通路。路由空洞问题对于地理位置路由协议是一个挑战。缺乏一个适当的路由 空洞处理机制，网络中的一些数据可能会丢失，这不仅浪费了有限的网络资源， 而且使得网络中的部分节点被隔离开来，破坏了网络对目标区域的有效覆盖和网 络的连通性。对于无线传感器网络这种面向特定应用的任务型网络，更加不希望 这种情况的发生，因为部分监测数据不能成功传输可能导致整个监测任务的失败。 因此，有必要为地理位置路由协议设计一个高效的路由空洞处理机制。 2 硕j j 学位论文 1 2 本文的研究内容 地理位置路由算法采用贪婪转发机制传递数据，非常适合无线传感器网络没 有固定中心节点的特点。但是贪婪地追求局部最优化的方式导致不可避免地会出 现路由空洞，破坏了传感器网络对监测区域的有效覆盖以及网络的连通性。为处 理路由空洞，这类算法通常需要首先生成整个网络的平面图，之后再采用右手准 则等遍历算法绕过空洞传输数据。由于需要网络中所有节点的位置信息，这就影 响到算法的可扩展性，而且平面图生成算法过于复杂，时空和能量开销较大，从 而影响到算法的效率和实用性。路由空洞的出现原因有两个：其一，节点部署不 均匀导致某些区域节点密度较低；其二，部分位置关键的传感器节点频繁转发其 他节点的数据而快速耗尽能量造成附近区域节点密度下降。 本文从路由空洞成因的角度出发，对路由空洞及其处理机制进行了研究，主 要包括以下几个方面的工作： ( 1 ) 提出一种应用于无线传感器网络的邻居节点反馈机制。该机制能够在节点 遇到路由空洞之后，将空洞信息反馈给数据流的上游节点，通知上游节点选择其 他的下一跳节点转发数据，尽量避丌往路由空洞方向传输数据，降低空洞节点启 动空洞处理机制的频率，节省网络能耗。而且该算法能够避免能量水平较低的节 点由于转发其他节点的数据而快速耗尽能量，从而延缓新的路由空洞的形成并尽 可能保证网络对监测区域的有效覆盖。 ( 2 ) 由于越靠近汇聚节点的传感器节点死亡越快，那么在部署节点时使得离汇 聚节点较近的区域节点密度更大一些，在部分节点由于频繁转发其他节点的数据 而死亡之后，区域内还可能有足够的节点密度以保证网络的连通性。因此，从节 点部署方案的角度出发，本文在几种不同的节点部署方案下对地理位置路由算法 进行仿真分析，以衡量不同节点部署方案对路由空洞出现频率和路由算法性能的 影响。 ( 3 ) 提出一种处理路由空洞的孤立子树重路由算法。路由空洞的存在意味着网 络路由拓扑图中存在一个以空洞节点为根孤立子树。该子树上所有节点都将数据 传输至遭遇空洞的节点，并且该子树与以s i n k 节点( 数据收集节点) 为根的树并不 连通。孤立子树重路由算法利用子树对应的局部网络信息，查找子树的关键节点 作为子树成员节点数据发送的目标节点，并利用关键节点的关键路径( 连接至以 s i n k 节点为根的树的链路) 建立起到达s i n k 节点的通路，尽可能地保证网络的连 通性。 ( 4 ) 针对孤立子树重路由算法存在的问题和不足之处，提出一种分布式的孤立 子树拆分算法，查找并利用子树中存在的多个关键节点作为数据发送的目的节点。 子树成员节点根据就近整合的原则，独立地选择距离最近的关键节点作为其数据 无线传感器网络地理位置路由和窄洞处理机制研究 发送的目标节点。整个孤立子树因此被拆分为多个更小规模的子树，关键节点的 通信负担随之得到缓解和均衡，并且子树产生的数据能够快速地传至其他子树。 1 3 本文的组织结构 论文的结构如下： 第l 章：简要介绍了本课题研究的背景、意义以及研究的主要内容。 第2 章：简要介绍了无线传感器网络的相关知识，包括体系结构、具体应用 等。然后简要介绍了无线传感器网络路由协议的概念和分类。最后阐述了地理位 置路由协议的基本思想及特点，并详细地对路由空洞处理机制进行分类介绍。 第3 章：详细介绍了一种邻居节点反馈机制，包括邻居节点空洞传输反馈机 制和剩余能量反馈机制。阐述了空洞传输反馈机制如何有效预测及避免路由通向 空洞，以及剩余能量反馈机制如何减少路由更新和重传、提高转发成功率。并通 过仿真实验进行了验证。另外，为了衡量不同的节点部署方案对传感器网络路由 算法的性能影响，仿真实现了三种节点部署服从不同分布的传感器网络。 第4 章：详细介绍了孤立子树重路由算法处理路由空洞的基本思想和详细定 义，以及孤立子树重路由算法与一种地理位置路由算法如何结合在一起形成一种 新的无线传感器网络空洞规避路由算法。最后通过仿真实验证明孤立子树重路由 算法能够有效提高网络的吞吐量，降低丢包率，并延长网络生命时间。 第5 章：通过分析孤立子树重路由算法的两个不足之处，提出一种分布式的 孤立子树拆分算法，并详细阐述了算法的定义。最后通过仿真实验证明孤立子树 拆分算法的性能的确较孤立子树重路由算法更优。 最后，对本文所完成的工作进行了总结，并指出了路由空洞处理机制以后研 究的方向。 4 硕十学位论文 第2 章地理位置路由及空洞处理机制相关研究 2 1 无线传感器网络简介 无线传感器网络由大量部署在目标区域内部或附近的传感器节点通过多跳、 自组织方式组成，目的是实现对目标区域和对象的监测。传感器节点采集到的大 量数据最终都需要通过多跳方式传送给对这些信息感兴趣的用户，以此来体现监 测数据的价值。无线传感器网络体系结构【3 】如图2 1 所示，它包括三个组成部分： 传感器节点、汇聚节点和用户。 图2 1 无线传感器网络体系结构 传感器节点是构成无线传感器网络的基本单元，具有体积微小、成本低，计 算、处理和通信能力有限，并且能量不易供给等特点。它们负责实时地采集本地 数据并将数据发送出去，同时也充当转发其他节点数据的中继节点，起到路由的 作用。多个传感器节点互相配合，通过多跳中继方式将监测数据从数据源节点传 送至数据收集节点，即汇聚节点。在无线传感器网络中，所有的传感器节点具有 同等重要性，在网络中的地位是相互平等的。 汇聚节点的存储、计算和通信能力相对普通传感器节点要强很多，并且能量 供给不受限制。它负责收集传感器节点采集到的数据，以及发送监测任务对应的 指令给传感器节点。此外，它还能够对收集到的监测数据进行初步加工，剔除其 中的冗余信息等。 用户负责配置和管理网络，能够下达指定的监测任务以及接收有效的监测数 据，从而实现对目标区域的监测。 无线传感器网络由于其快速部署、自组成网、可扩展性强等特点【1 2 】，具有极 其广阔的应用前景。作为普适计算【1 6 】的一个典型应用，无线传感器网络可以使用 无线传感器网络地理化置路由和窄i | | 4 处理机制研究 户不受时间、地点和环境条件的限制而获取感兴趣的信息，在环境监测、智能家 居、医疗诊断、目标追踪与定位、国防等领域得到广泛地应用【i 引。 近年来快速发展的车载网络也是无线传感器网络的一种特殊应用，它包括两 层含义。其一，它是指车辆与车辆之间的车载自组织网络( v 曲i c l ea d - h o cn e t w o r k s ， v a n e t ) 【2 4 1 。车辆是作为网络中的一个节点的形式存在，每个节点具有数据采集 模块用于采集信息，然后通过无线通信模块与其他节点或者路边节点分享这些信 息。由于其在交通管理、车辆跟踪、路况导航等方面的优势，能够为驾驶员提供 更加舒适的驾驶体验，并且降低发生事故的概率，因此在智能交通系统 ( 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 ) 中扮演着重要角色【2 8 】。其二，它是指车辆 内部的c a n ( c o n t r 0 1 l e ra r e an e t w o r k ) 总线网络【29 1 。大量各种类型的电子控制单元 ( e l e c t r o n i cc o n t r o lu n i t ，e c u ) 和传感器被安装在车辆内部，它们以有线方式或有 线与无线相结合的方式自组成网，用于实时监测车辆内部各功能部件的运行状况， 并且通过总线在各部件之间传递和交换数据。通过对各部件的工作状态信息进行 分析，预测部件可能发生的故障，并对故障进行诊断和恢复等操作，从而提高车 辆的整体性能。 2 2 无线传感器网络路由协议概述 无线传感器网络路由协议足无线传感器网络的研究热点之一，其主要任务包 括两个方面：第一，建立数据源节点和汇聚节点之间的通路；第二，沿着通路可 靠地传输监测数据【4 】。在无线传感器网络中，通常只有一个汇聚节点位于网络内 部或者边缘，大多数传感器节点都不能直接和汇聚节点直接通信，数据的传输需 要通过网络中的其他传感器节点进行转发，即多跳路由。由于传感器节点能量受 限，采集数据、处理数据和传输数据等操作都需要耗费能量，因此设计路由协议 时的首要考虑因素是节省能量。这就要求设计出的路由协议复杂度不能太高，负 载不能太重，空时开销不能太大，协议控制信息不能太多。另外，无线传感器网 络节点规模较大，拓扑变化较快，节点通常只维护局部网络拓扑信息，因此路由 协议需要尽可能根据局部网络拓扑信息进行路由选择。作为无线传感器网络中的 一项关键支撑技术，路由协议性能的优劣会直接对传感器网络的性能产生重大影 响。节省能量、追求高能效的要求导致应用于传统计算机网络的路由协议不能直 接应用于无线传感器网络之中【3 0 1 。 为此，研究人员根据无线传感器网络的特殊性提出了多种路由协议旨在保证 算法效率的同时节省节点能量消耗，包括分层路由协议、以数据位中心的路由协 议、地理位置路由协议、服务质量路由协议和能量感知路由协议等几大类 4 j 。 ( 1 ) 分层路由协议 分层路由协议通常将整个传感器网络中的节点按照某种规则划分为一个个区 6 硕上学位论文 域，称之为簇，并为每个簇选定一个簇头节点。普通节点负责采集数据并通过多 跳方式传输至簇头节点。簇头节点负责将数据传送给汇聚节点，它要么直接发送 要么通过其他簇头节点进行转发。该类路由协议通常采用数据融合技术，能够减 少网络中的数据通信量，起到节省网络能量的作用。分簇的方式也使得其可扩展 性较好，能够适用于大规模网络。该类协议代表性算法有l e a c h 【33 1 、p e g a s i s 【3 4 1 、 t e e n 【3 5 】和a p t e e n 【3 6 】等。 ( 2 ) 以数据位中心的路由协议 该类协议的基本思想是利用特定的命名机制对网络中的数据进行命名，数据 的请求和发送都根据该命名机制进行，不再依赖网络中节点的位置。比如d i r e c t e d d i f h s i o n 【3 7 1 利用属性值对对数据进行命名，s p l n 3 8 1 利用元数据对数据进行命名。 此外，还有对d i r e c t e dd i f f u s i o n 进行改进的r u m o r 算法【3 9 】。 ( 3 ) 地理位置路由协议 地理位置路由通常利用其携带的定位模块获取地理位置信息，然后利用位置 信息对数据传输的导向性，协助路由发现和维护【9 1 。由于利用了节点之间的位置 信息，数据能够尽量朝着目的节点的方向传输，传输路径较优。但是该类算法也 有自己的问题，即路由空洞。该类算法包括经典的g p s “l l 】、g p s r s 【4 0 1 、g e a r 4 1 1 、 p p v r 4 2 1 、e p g r 【4 3 1 、t b f 【4 4 】等。 ( 4 ) 服务质量路由协议 服务质量路由协议着重在于提高网络的服务质量，包括确保响应的实时性、 数据传输的可靠性、容错性等。为此，需要预先进行路由发现并定期维护质量较 优的路径。由于无线传感器网络拓扑动态变换频繁，因此需要经常启动路由发现 和维护的过程，而且为了实现可靠传输，通常采用多路径机制，这些都导致开销 的急剧增加。s a r 【4 5 】是第一个保证服务质量的路由协议，此外还有保证端到端传 输时延的s p e e d 协议【4 6 】等。 ( 5 ) 能量感知路由协议 能量感知路由协议的主要目标是发现网络中消耗能量尽可能小的路径，节省 节点能量。此外，为了均衡整个网络的能量消耗，算法动态调节网络中的数据通 信量，能够起到负载均衡的作用，从而延长网络的生命时间。代表性算法包括 e n e r g ya w a r er o u t i n g 【47 1 、e b m r 【4 8 1 等。 2 3 无线传感器网络地理位置路由协议 在地理位置路由中，节点通过g p s 6 】或者定位 7 1 算法获知自己的位置信息， 并通过与邻接节点的交互获取邻近节点以及目标节点的位置信息。当有数据需要 转发时，节点根据其掌握的局部网络信息，选择位置更加接近目标节点的一跳邻 接节点作为下一跳转发节点，尽可能地将数据往更加接近目标节点的方向传输。 无线传感器网络地理位置路由和卒洞处理机制研究 这种方式即贪婪转发方式，它能够以较小的代价，沿着较短的路径传输数据。如 图2 2 所示，节点y 是x 的所有邻接节点中距目的节点d 最近的一个，因此节点 x 会将数据转发给节点y 。 图2 2 贪婪转发示例 但是地理位置路由利用局部网络信息追求局部最优化的方式导致路由空洞这 种特殊现象的出现。因此，地理位置路由在转发数据时也就分为两个阶段：贪婪 转发阶段和空洞处理阶段。 当一个节点需要转发数据而又找不到比自身更加接近目标节点的下一跳邻接 节点时，路由算法就会从贪婪转发阶段切换到空洞处理阶段。在空洞处理阶段， 节点尝试沿着路由空洞的边缘转发数据，因为可能存在通往目标节点的有效路径。 如图2 3 所示，d 是目标节点，s 是一个空洞节点，节点s 的数据不能通过贪婪 思想转发至节点d ，但是存在一条从节点s 通向节点d 的通路：s a b c d 。 图2 3 绕过路由空洞的路径示例 泛洪算法【4 9 1 是一个简单的空洞处理算法，它由空洞节点发起，任何节点都转 发收到的数据。该算法的优点是能够保证只要网络中存在到达目的节点的通路， 硕十学位论文 数据就一定能够成功传送到目的节点。但是所有节点都参与转发数据，目的节点 可能收到从不同路径传送过来的同一份数据，这无疑是对网络资源的浪费。较早 的研究在节点遇到路由空洞后，退让求其次，将邻接节点中距目的节点最近的一 个作为数据转发的下一跳节点。然而，它很可能导致数据围绕空洞打转的现象。 此外，一些研究建议不要将数据转发给空洞节点或者干脆部署更多节点从而彻底 避开路由空洞问题。 高效的路由空洞处理机制对于地理位置路由乃至整个无线传感器网络来说都 是至关重要的，以下列出了在设计路由空洞处理机制时应该尽可能达到的目标： ( 1 ) 参与处理空洞的传感器节点应尽可能地少，最好空洞节点自身就能完成对 空洞的处理： ( 2 ) 路由空洞处理机制带来的额外的时空和能量开销应尽可能地少，资源利用 率应尽可能地高； ( 3 ) 只需利用少量局部网络信息就能完成对空洞的处理，从而不对路由算法的 可扩展性产生影响； ( 4 ) 沿着空洞传输数据的路径不能比网络中存在的最优路径太差，要尽可能地 接近最短路径。 路由空洞处理机制是在数据到达空洞节点之后，由空洞节点发起空洞处理的 过程。一旦数据绕过空洞，或者数据到达一个距目的节点更近的节点时，则恢复 贪婪转发机制。目前，地理位置路由中的路由空洞处理机制可以分为基于泛洪的 空洞处理机制、基于平面图的空洞处理机制、基于代价的空洞处理机制、启发式 空洞处理机制和混合型空洞处理机制几类，下一节将分类介绍这些机制。 2 4 无线传感器网络路由空洞处理机制 2 4 1 基于泛洪的路由空洞处理机制 基于泛洪的路由空洞处理机制利用原理最简单的泛洪方式传输数据，能够成 功地绕过路由空洞，并且在网络连通的情况下这类算法能够保证数据的成功传输。 最原始的泛洪算法中的所有节点都参与转发数据，是一种简单有效的空洞处理技 术，缺点是在资源利用方面效率低下。尽管研究者提出了一些改进的泛洪算法 5 0 】 以尽可能地提高算法效率，但是由于只有目的节点才期望收到空洞节点发送的数 据，因此处理路由空洞的代价还是的太大。为此，应该尽量控制泛洪的范围，以 及尽量降低在空洞节点启动泛洪算法的频率，从而削减泛洪的代价并提高处理空 洞的效率。这样的泛洪机制被称为受限泛洪和局部泛洪【5 1 】。 一跳泛洪 5 2 】是一种受限泛洪，思想很简单，即空洞节点仅仅泛洪数据包给其 一跳邻接节点，而不像完全泛洪那样所有节点都会收到数据包的拷贝。在泛洪数 9 无线传感器网络地理位置路由和窄涧处理机制研究 据包给其邻接节点后，空洞节点会记录数据包的l d 和与之对应的目的节点，并 拒绝接收任何邻接节点发送过来的相同数据包。每个邻接节点收到数据包之后， 利用贪婪转发算法继续转发数据的拷贝。如果一个邻接节点根据贪婪算法选择的 下一跳节点是空洞节点，那么空洞节点在接收到数据包后会返回一个拒绝消息， 通知该邻接节点重新选择除空洞节点之外更优的下一跳节点。一旦不存在其他更 加合适的下一跳节点，那么该邻接节点也成为空洞节点，一跳泛洪在新的空洞节 点处继续执行。 g r a 【5 3 1 在没有遇到路由空洞的时候同样采用贪婪转发将数据传输到目的节 点。一旦数据到达一个空洞节点，就启动路由发现过程，按需查找从空洞节点到 达目的节点的路径，并更新位于该路径上的所有节点的路由信息。路由发现过程 成功完成之后，通过局部多跳路由的方式将数据从空洞节点传输至目的节点。路 由发现阶段g r a 利用的是宽度优先遍历，属于泛洪的范畴。泛洪的效率取决于 空洞节点和目的节点之间通信的持续时间。通信时间越长，空洞节点启动泛洪算 法的频率越低，查找路径的代价可以抵消。不同于泛洪，有研究者提出采用深度 优先遍历的路由发现技术 5 4 】发现更高质量的路径。 p sr 【5 5 】是一种按需和无状态的空洞处理机制。空洞节点可以直接转发数据包 给目的节点，或者转发数据给距离目的节点更近的节点。该算法包括两个阶段： 局部路径发现阶段和数据转发阶段。在局部路径发现阶段，空洞节点使用类似于 文献【5 6 】中的方法查找从空洞节点起始的路径。首先空洞节点通过泛洪用于路由发 现的消息包给所有的两跳邻接节点。如果成功发现路由，该阶段结束。否则空洞 节点发起另一次路由发现过程，扩大泛洪消息包的范围为三跳邻接节点。重复执 行以上操作要么找到目标节点，要么达到协议设定的最大跳数值时丢弃数据包。 有研究【5 7 】显示四跳以内能够绕过绝大多数路由空洞。如果存在通向目的节点或者 通向某个位置更好的节点的局部路径，在数据转发阶段空洞节点已经获知至少一 条这样的路径。这时，空洞节点将路径信息写入数据包头，并转发数据给指定的 下一跳节点。p s r 中只有空洞节点存储和维护数据包头部的路径信息，中间节点 在转发数据时的依据即为数据包头中的路径信息。类似于局部多跳路由，p s r 采 用泛洪算法发现局部路径的代价也会由于相对持久的通信而抵消。 2 4 2 基于平面图的路由空洞处理机制 基于平面图的路由空洞处理机制涉及到分布式平面化算法和平面图遍历算 法。理论上只要网络中存在一条有效通路它就能找到，从而保证数据的成功传输 【5 引。无线传感器网络可以被看作是一个图，其中传感器节点可以看作是图中的顶 点。如果一个节点位于另一个节点的通信范围之内，即这两个节点能够直接通信， 那么就认为这两个节点之间存在一条边。 1 0 硕l j 学位论文 在图论中，。如果一个图不存在相互交叉的边，那么该图被定义为一个平面图。 对平面图进行遍历( 比如右手准则) 就能够找到一条通向目的节点的路径。由于传 感器节点形成的原始图通常不是一个平面图，所以需要平面化算法从原始图中提 取出平面子图。否则，就可能出现路由环路。因此，基于平面图的空洞处理机制 的性能不仅取决于平面图遍历算法，同时也取决于分布式的平面化算法。前者主 要考虑遍历算法找到的路径的质量，即路径是否最优。后者不仅考虑算法的效率， 而且考虑平面图最优路径质量与原始图最优路径质量的差异。 ( 1 ) 分布式平面化算法 r n g 和g g 【是目前较为常用的两种分布式平面化技术，它们只需了解局部 网络的拓扑信息就能完成平面化工作。其主要思想是：如果顶点x 和y 相交的区 域内没有其他顶点，则保留边( x ，y ) 。一条边属于r n g 图的条件是两个节点通信 范围相交的区域内不包含任何节点，如图2 3 ( a ) 所示。一条边属于g g 图的条件 是以这条边为直径的圆形区域内不包含任何节点，如图2 3 ( b ) 所示。很显然，r n g 图实际上是g g 图的子图。 ( a ) r g n 平面图( b ) g g 平面图 图2 4r g n 平面图和g g 平面图 ( 2 ) 平面化算法 凸面( c o n v e xf a c e ) 遍历算法【5 9 】假设任一节点都知道其邻接节点的循环次序， 并且除了外部边界所对应的面之外，平面图中所有的面都是凸面。该算法从源节 点开始，按照逐渐接近目的节点的原则逐个遍历平面图中的面。图2 4 显示了执 行遍历的过程。从节点s 所属的距离节点d 最近的面开始，沿着线段s d ，对与 线段s d 相交的面逐个进行顺时针或者逆时针遍历。值得注意的是一旦确定了面 遍历的方向( 比如逆时针) ，在整个遍历过程中该遍历方向将不再改变。在遍历过 程中，如果将要遍历的某条边与线段s d 相交时，就切换到下一个面继续进行遍 历，到达节点d 的时候遍历完成。 无线传感器网络地理位置路由和窄洞处理机制研究 图2 5 凸面遍历示例 f a c e 2 算法【5 8 】采用的遍历算法与凸面遍历相似，但是在某一个节点处，可能 有两条以上的边与上图中线段s d 相交的情况。这时就需要算法找到所有与s d 相交的边，并选择距离节点s 更远的边所在的面继续进行遍历。 ( 3 ) 基于平面图的路由空洞处理算法 g p s r 【】是一个经典的地理位置路由协议，在贪婪转发阶段总是选择邻接节 点中距目的节点最近的一个作为数据转发的下一跳节点，当数据到达空洞节点后， 启动周边转发算法，利用右手准则( 类似于f a c e 2 的平面图遍历算法) 围绕路由空 洞继续传输数据。但是在这之前，g p s r 首先要利用r n g 或者g g 平面化技术从 网络原始图中提取出平面子图。采用周边转发算法转发的数据包的头部通常会包 含空洞节点的位置、面切换时的交叉点以及当前遍历面的第一条边等信息，从而 为节点在本地进行路由抉择提供信息。利用这些信息，节点能够在适当的时候停 止平面图遍历算法。例如在图2 4 中，如果节点s 不能到达目的节点d ，那么数 据将沿着平面图中的某个面打转。这时，