（计算机系统结构专业论文）ad+hoc网络地理路由算法研究.pdf

硕士学位论丈 m a s t e r st h e s i s ar e s e a r c ho f g e o g r a p h i cr o u t i n g i na d h o cn e t w o r k s 4 砌e s i s s u b m i t t e di np a r t i a l f u l f i l l m e n to f t he r e q u i r e m e n t f o rt hem s d e g r e e 讯c o m p u t e rs y s t e ms t r u c t u r e b y z h a n gj i n f e n g p o s t g r a d u a t ep r o g r a m d e p a r t m e n to fc o m p u t e rs c i e n c e c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：l i a n s h e n gt a n a c a d e m i ct i t l e ：p r o f e s s o r s i g n a t u r e a p p r o v e d m a y , 2 0 1 1 硕士学位论文 m a s t e r st h e s l s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作所取得的研 究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过 的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本声明的法 律结果由本人承担。 作者签名：纭铆匀 日期：矽l l q - 多月主f 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国 家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅本人授权华中师范大 学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描 等复制手段保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收录到 中 国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名：蝴 日期：沙l | 年5b 弓| 日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库中全文发布，并可按“章程”中的 规定享受相关权益。回塞途室握童后溢蜃；旦堂生；旦二生；旦三生筮查! 作者签名：蹑岔问 日期：) o ig - 岁b ；7 日 导。俗名：弱眇从 功 日期：即年占bj 日 儿日 胗 ， ，月玄北 名 如 签 ： 师期 争日 硕士学位论文 m a s t e r st h e s i s 中文摘要 a dh o c 网络的研究已成为网络领域的一大热点，本文主要对无线、可移动的 a dh o c 网络地理路由算法进行了研究。a dh o e 网络中，所有的节点都同时具备普 通移动终端的功能和路由器的双重功能，并且网络中所有的节点都是可以自由移动 的，这些节点的移动导致了网络的拓扑结构的动态改变。a dh o c 网络对路由协议 的要求不同于有线网络，基于地理坐标的路由算法就是其中一个应用广泛的路由。 本文介绍的地理路由算法有三个前提假设点：网络节点知道自身的坐标，一跳 邻节点的坐标以及目的节点的坐标。d s r 有两个重要的组成部分：查找路由和维护 路由。在g r 算法中，分组发送节点能局部最优地选取网络中地理坐标距离目的节 点最近的一跳邻节点作为转发节点。g p s r 算法，是对g r 算法的一种改进，在g r 算法遇到“空洞 ，不能继续贪婪转发时，g p s r 开始沿着“空洞的边缘右手原则 往下转发分组，是一种结合贪心转发和边缘转发的路由算法，用比较距离远近的方 式判断“路由空洞一问题得到解决，g p s r 会及时返回到贪婪路由模式。 用网络仿真工具n s 2 对a d h o c 网络中的以上三种路由算法进行几种不同场景 的模拟仿真，得出各个路由算法在分组传输成功率、路由算法开销、分组选取路径 的节点数等方面的结果并对这些仿真数据进行分析。在高节点移动网络和高流量负 载的网络中，g p s r 有领先优势。g p s r 的特点和优势就在于维护路由信息成本低， 它只需要维护节点的相邻节点的路由信息。 g p s r 算法能保证路由路径的发现，避免存在路径而数据包不可达的情况。 g p s r 右手原则边缘转发数据包解决“路由空洞”问题，实际上所用的是一种迂回 的路由方法，它的平均路由路径长度不能达到到最优。本文对g p s r 算法进行改进， 在数据包报头中增加一个存储数据包传送跳数的字段，边缘转发模式下的节点本地 存储最近一次路由路径信息，比较邻节点接收数据包的路由跳数，得出最优路由路 径并进行存储。仿真数据分析表明，改进后的g p s r - p r o 算法达到了预期缩短平均 路由路径的效果。g p s r - p r o 算法对g p s r 改进的初衷就是缩短平均路由路径长度， 在路由空洞比较多且网络拓扑结构变化不是特别快的无线网络中，g p s r - p r o 算法 在缩短平均路由路径长度上表现得更明显。 关键字：a dh o e ；地理路由；g p s r ；g p s r - p r o ；模拟仿真 a b s t r a c t t h er e s e a r c ho fa dh o cn e t w o r kh a sb e c o m eah o t , t h i sp a p e rf o c u s e so ng e o g r a p h i c r o u t i n ga l g o r i t h mi na dh o en e t w o r k a l lt h en o d e si na dh o e n e t w o r ka r ea l s ow i t h d o u b l ef u n c t i o n b e c a u s eo ft h em o b i l i t y , s e l f - o r g a n i z a t i o no fn o d e si na dh o cn e t w o r k , t h er o u t i n ga l g o r i t h mi sd i f f e r e n tf r o mo t h e rn e t w o r kr o u t i n ga l g o r i t h m s r o 砸n gb a s e d o ng e o g r a p h i cp o s i t i o ni so n eo ft h ew i d e l yu s e dr o u t i n g na s s u m e st h a ta l ln o t e si na dh o en e t w o r kk n o wt h e i ro w np o s i t i o n s ，t h e i r1 - h o p n e i g h b o r s p o s i t i o n s 勰w e l la st h ed e s t i n a t i o n s d s ri s c o n s i s to fs e a r c h i n ga n d m a i n t a i n i n go fm u t i n g g ri sas i m p l eg r e e d yg e o g r a p h i cf o r w a r d i n ga l g o r i t h m , f o ra f o r w a r d i n gn o d e ，t h el o c a l l yo p t i m a lc h o i c eo fn e x th o pi st h en e i g h b o rg e o g r a p h i c a l l y c l o s e s tt ot h ep a c k e t sd e s t i n a t i o n g p s ri su p g r a d e dv e r s i o no fg r e e d yr o u t i n g , c a n s o l v et h ev o i do fg r t h ep a c k e ti sf o r w a r d e dg r e e d i l y , a n df o r w a r d e da l o n gt h e p e r i m e t e rw h e nt h e r ei sap r o b l e m ，r e t u r nt og r e e d ym o d ef li ti sp o s s i b l e t h i sw o r ks i m u l a t e dg g p s ra n dd s rw i t hn s - 2i ns e v e r a ld i f f e r e n ts c e n e s ，a n d s u m m a r i z e dt h e i ro w ns u p e r i o r i t yo np a c k e td e l i v e r ys u c c e s sr a t e ，r o u t i n gp r o t o c o l o v e r h e a da n dp a t hl e n g t h ，a n da n a l y s i so ft h e s es i m u l a t i o nd a t a g p s rc a ng u a r a n t e et h ed i s c o v e r yo fr o u t e ，a v o i du n r e a c h a b l eo fe x i s t i n gp a t h t h e r i g h tr u l eo fg p s rc a ns o l v et h ev o i do fg r , i ti sac i r c u i t o u sr o u t i n gm e t h o d , a v e r a g e r o u t i n gp a t hl e n g t hc a nn o tr e a c ht oo p t i m a l t h i sp a p e rm a k e ss o m e w o r ko ng p s r , a d d a p a c k e ts t o r a g e dt h eh o p so ft r a n s m i s s i o ni np a c k e th e a d e r , t h en o d e si np e r i m e t e rm o d e s t o r a g el a s tr o u t ei n f o r m a t i o n , c o m p a r a t i v er o u t i n gh o p s ，a n dg e tt h eb e s tr o u t e t h e s i m u l a t i o nd a t aa n a l y s i ss h o wt h a tt h eg p s r p r oa l g o r i t h mc a l la c h i e v et h ed e s i r e d e f f e c to ns h o r t e ra v e r a g er o u t e k e yw o r d s ：a dh o e , g e o g r a p h i cr o u t i n g ，g p s i lg p s r - p r o ，s i m u l a t i o n ：。? ? j ：。一。l | 一 。 中文摘要 硕士学位论文 m a s t e r st h e s i s 目录 i a b s t r a c t 第一章绪论l 1 1研究背景1 1 2研究内容及目标2 1 3论文基本框架3 第二章a dh o c 网络路由算法的研究5 2 1a dh o c 网络概述5 2 2路由协议分类6 2 3动态源路由算法( d s r ) 7 2 4贪婪路由算法( g r ) 7 2 5贪心边缘无状态路由算法( g p s r ) 9 2 6本章小结1 4 第三章g p s r 和d s r 路由的模拟与仿真1 5 3 1仿真环境。1 5 3 2分组发送成功率分析16 3 3平均路径长度分析2 1 3 4路由协议开销分析2 4 3 5本章小结。2 8 第四章g p s r 算法的改进2 9 4 1g p s r 路由2 9 4 2改进算法g p s r - p r o 描述3 0 4 3g p s r - p r o 算法的实现3 1 4 4g p s r - p r o 算法仿真数据分析。3 5 4 5路由算法的比较与分析3 6 4 6本章小结。3 8 第五章结论与展望3 9 5 1本文结论3 9 5 2研究展望3 9 参考 致谢 文献4 1 4 4 硕士学位论文 m a s t e r st h e s t s 1 1 研究背景 第一章绪论 互联网已成为当代人们日常生活中必不可少的一部分。通过互联网，人们在家 就可以及时知道社会最新资讯、零距离地与亲朋好友进行远程交流等，互联网确实 给人类当代的生活带来了不可思议的变化。 随着人类的进步、社会的发展，人们对网络的要求越来越高，已不再满足于有 线网络的使用，渴望摆脱这种有一定局限性网络的束缚，希望能随时随地自由地进 行通信，于是，a dh o e 网络1 7 1 ，一种不需要有线基础设备的支持、其中的主机可以 自由移动的网络应运而生。 由于a dh o e 网络的特性和广阔的应用前景，现阶段对a dh o e 网络的研究已然 成为网络领域的- 大热点，甚至延伸至多学科交叉的研究范围。总结学术界学者对 a dh o e 网络的研究现状，已经彰显出来的研究成果主要有： 路由协议设计一种新的a dh o e 网络路由协议【l5 1 ，主要障碍在于a dh o e 网络 的拓扑结构动态变化【1 6 1 ，传统的路由协议大部分是针对拓扑结构较稳定的网络( 如 有线网络) 而设计的。现阶段已有的、得到普遍研究人员认可并具有代表性的路由 协议有动态源路由算法( d s r ) 【l j 、贪心路由算法( g r ) 2 1 、贪心边缘无状态路由 算法( g p s r ) 3 1 、按需距离矢量路由算法( a o d v ) 4 1 、目的序列距离矢量路由算 法( d s d v ) 1 5 等。但这些路由协议的研究还处于理论状态，基本上都是在二维空 间进行设计的，离实际生活多维空间中的应用还有一定的距离。 多种网络的相互联通目前对a dh o e 网络的研究基本是处于一种理论阶段。 a dh o e 网络的安全隐患，传输方面不能保证成功传送率，所以，如果a dh o e 网络 独立地组网，纯粹单独的a dh o e 网络的商业价值并没有预期的那么大。由此可以 预见，在未来的接入网研究中， a dh o e 网络将会以小规模的形式作为整个网络体 系中的一个接入网，与其他多种网络系统整合组网是一个研究趋势。蜂窝网络是目 前比较成熟的一种无线的传感器网络【2 5 1 ，实现a dh o e 网络与i n t e r a c t 以及诸如蜂窝 网络的相互连通是a dh o e 网络领域的又一个研究热点。蜂窝系统中会有一些基站 覆盖不到或者信号比较弱的区域( 亦称为盲区) ，将a dh o c 网络的可移动节点的特 性结合起来，可以提高信号的覆盖范围。目前主要的研究成果有o d m a 、a g s m 、 s o p r a - n o 、i c a r 等。 1 硕士学位论文 m a s t e r st h e s i s 安全体系和安全技术a dh o e 网络是一种节点可以自由移动的无线路由网络， 比较容易受到不良分子的破坏( 如窃听、攻击等手段) 。研究a dh o e 网络当中的安 全相关课题具有重大意义，也受到一些学者的关注。 服务质量保证a dh o e 网络最初出现是准备用来传输数据信息的，但随着网络 发展的成熟，它更多地被用来传输多媒体数据。多媒体信息对网络宽带、时延等有 较高的要求，因此对a dh o e 网络提出需要一定服务质量保证的要求。多媒体以及 数据信息在网络体系中是逐层进行传输的，所以若要保障服务质量，不同的层次需 要有不同的保障机制，这是一个开放性的研究课题。 1 2 研究内容及目标 本文主要对无线的a dh o e 网络中的地理路由( 一种事先知道网络节点的地理 坐标的算法) 1 1 9 】进行介绍和研究。a dh o g 网络中的节点可移动性、自组织性等特 点使得a dh o e 网络的路由算法区别于其他网络的路由算法。地理路由是基于以下 几个假设点：网络节点自身的地理坐标已知；网络节点已知相邻节点的地理坐 标；网络节点已知目的节点的地理坐标。a dh o e 网络中的节点不仅具备普通移 动终端的功能，还具备路由转发分组的功能。 本文主要介绍和研究了三种a dh o g 网络路由算法：动态源路由算法( d y n a m i c s o u r t ? 冶r o u t i n g ，d s r ) , 贪心路由算法( g r e e d yr o u t i n g ，g 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 ，g p s r ) 。在网络模拟仿真工具n s 2 上模 拟仿真了这几类路由算法，并就分组传输成功率 2 2 1 、路由算法开销、分组选取路径 的节点数【2 7 】三种情况详细分析了仿真数据。 针对g p s r 路由中边缘转发抉择造成路径较长的情况，本文提出的g p s r - p r o ， 对g p s r 作出了改进，在g p s r 路由的报头中添加一个字段，专门用来记录进入边 缘转发模式的第一个节点到中间转发节点的跳数，默认初始值为o ；边缘转发模式 下的每个节点都引入了一个存储数组，暂时缓存最近一条路由路径信息，包括边缘 转发开始节点的地理位置，目的节点的地理位置，边缘转发时第一个节点到本节点 的跳数，可优化路径的下一跳地址以及邻居节点到本节点的跳数。基于这样的一个 改进，边缘转发时作出另一种选择，仿真数据证明，g p s r - p r o 在缩短路径长度等 方面有了一定的改善。， 2 硕士学位论文 m a s t e r st h e s i s 1 3 论文基本框架 本文研究的重点是a dh o e 网络中的基于地理坐标的路由算法。论文一共分为 五章： 第一章绪论。这一章主要介绍了研究a dh o e 网络的背景以及内容，包括a d h o c 网络概况、目前发展状况、已经研究的科研成果以及其应用，并对a dh o e 网 络中的地理路由算法作出简要介绍。 第二章a dh o e 网络路由算法的研究。这一章首先对a dh o e 网络的路由协议 做了大致分析，引入了基于地理坐标的路由算法的定义。d s r 算法是一种性能较优 的路由算法。贪心边缘无状态路由g p s r 是一种对g r 进行改进的路由算法，g p s r 在g r 的“空洞 外围选择能够转发分组至目的节点的邻居节点作为转发节点。 第三章三种路由算法的模拟与仿真。用网络仿真工具n s 一2 对a dh o e 网络中 的地理路由算法g p s r 和d s r 进行模拟仿真，并比较这两个路由算法在分组传输 成功率、路由算法开销、分组选取路径的节点数等方面的优越性。 第四章g p s r 算法的改进。g p s r 算法能保证路由路径的发现，但某些场景中 g p s r 算法的边缘转发所做出的路由抉择路径比较长，本文所提出的算法 g p s r - p r o 对g p s r 做出了改进，仿真数据证明了改进后的路由在缩短路径长度等 方面有一定的优越性。 第五章结论与展望。对所做的研究工作进行了总结，并对将来进一步的研究 工作进行了展望。 3 ?j、? “? 、 硕士学位论文 m a s t e r st h e s i s 第二章a dh o c 网络路由算法的研究 路由算法是a dh o c 网络研究领域中的热点，其中以地理坐标路由的研究为代 表。地理路由协议【2 0 】，在a dh o c 网络研究中演绎了重要角色。地理路由协议中， 假设网络中的每个节点都清楚地知道自己的地理坐标、一跳邻接节点的地理坐标以 及目的节点的地理坐标。 2 1a dh o c 网络概述 a dh o c 网络 t i 是一种新型的、无线的和节点可移动的网络 2 6 1 ，是一种不同于有 线网络的无线网络。a dh o c 网络中，所有的节点都同时具备普通移动终端的功能 ( 处理分组的能力) 和路由器的功能( 转发分组的能力) ，并且网络中所有的节点 都可自由移动，这些节点的移动导致了网络拓扑结构的动态改变。如果a dh o c 网 络中的两个节点在彼此的无线电波的覆盖范围之内，它们就可以直接通信，如图2 1 所示中，节点a 和节点c ，以及节点b 和节点c 都在彼此的无线电波的覆盖范围 之内( 节点周边的虚圆标识该节点的无线电波的覆盖范围) ，它们之间可以直接通 信，而节点a 和节点b ，则必须通过中间节点c 的转发才能达到相互通信的目的。 所以，a dh o c 网络一般也被称为多跳、无线网络。 图2 1a dh o c 网络节点之间的通信 a dh o c 网络有着非常广泛的的应用【8 】，能够应用在人们生活中的各个领域，其 应用前景非常广阔。 军事应用：a dh o c 网络技术的概念是应当时的军事需求而提出的，任何一场 ( 军事) 战争中，甲方军队的网络通信系统很容易成为乙方军队攻击的目标，因此 要求战争中的通信系统必须有一定的抗击毁能力。分布式a dh o c 网络，即使其中 的某个节点( 或者某些节点) 被摧毁，只是某些链路断开，不影响其他链路的工作， 硕士学位论文 m a s t e r st h e s i s 而且由于网络节点的自由移动性，断开的链路可以重新链接起来。 紧急应用：a dh o e 网络可用于灾难救助，在遭遇自然灾害或者其他各种灾难 后，原有的固定的通信网络设施大部分遭到破坏而无法正常使用，通过a dh o c 网 络可以在这些恶劣和特殊环境下快速地建立起新的临时通信系统，保障灾后的救援 工作顺利开展。 传感器网络：分散的传感器组成一个a dh o c 网络，可以实现传感器节点之间 和控制中心节点之间的通信。 家庭应用：给家庭电器装备a dh o e 收发装置，与随身带着的个人手持设备如 p a d 进行通信，可以远程地调控家中设备，如开关空调、开关灯等。 2 2 路由协议分类 路由协议是a dh o e 网络的重要组成部分。相比于其他网络路由协议，a dh o c 网络具有多跳、动态变化的拓扑结构、不依赖于固定链路传输等特点，a dh o e 网 络路由协议的研究更具有挑战性。 从路由发现策略的角度上来看，a dh o c 网络中的路由器可分为主动路由协议 ( p r o a c t i v er o u t i n gp r o t o c o l s ，又称表驱动路由协议) 和按需路由协议( r e a c t i v e r o u t i n gp r o t o c o l s ，又称反应式路由协议) 两种类型1 9 1 。 主动性质的路由协议通过时刻地侦查网络的拓扑结构及链路的变化及时地更 新路由表。网络中的节点都维护一张或一张以上的路由表，记录着此节点到网络中 其他节点的路由信息，发送分组时，节点通过查询路由表来作出转发路径的抉择。 一旦网络的拓扑结构发生变化时，节点会立即在网络中发送更新的消息，而收到更 新消息的节点会同步更新自己的路由表。这种协议适用于拓扑结构变化不大的网 络。协议代表有：d s d v ( d e s t i n a t i o w - - s e q u e n c e dd i s t a n c e - - 撇t o rr o u t i n g ) t 1 0 1 、c g s r ( c l u s t e rh e a dg a t e w a ys w i t c hr o u t i n g ) t il l 和w r p ( w i r e l e s sr o u t i n gp r o t o e o1 ) b 2 1 等。 按需性质的路由协议l l 刀是一种在网络节点需要通信时临时性地通过发送洪泛 请求来寻找路由路径的协议。按需性质的路由协议中，只有在始发节点需要向目的 节点发送分组的时候，始发节点才在网络上发送洪泛请求进而得到路由路径。这种 路由协议减少了维护路由表的额外开销，故在a dh o c 网络中得到广泛应用。协议 代表有：a o d v ( a dh o co n - - d e m a n dv e c t o rr o u t i n g ) 【4 、d s r ( d y n a m i cs o u r c e m u t i n g ) 、t o r a ( t e m p o r a l l yo r d e r e dr o u t i n ga l g o r i t h m ) j 等。 6 硕士学位论丈 m a s t e r st h e s i s 2 3 动态源路由算法( d s r ) 动态源路由协议( d s r ) 是众多按需路由协议中的一个，d s r 协议简单但路由 开销大，是a dh o e 网络中性能比较好的路由协议。在此作简要介绍，其目的是以 此作为衡量标准，衡量对于g p s r 等基于地理坐标的路由协议是否具有一定的实用 性，这些不断被提升的地理路由算法是否较d s r 更胜一筹。 d s r 路由协议中有两个主要组成部分：路由的查找和维护。 d s r 路由协议中，如果产生分组的最初发送节点的缓存中没有到达目的节点的 路由时，发送节点就需要进行第一步：查找路由。最初发送节点洪泛式地发送一条 信息至网络中的其他所有节点，所发出的查找路由信息会记录下被传输过程中的完 整路由路径，当目的节点接收到发送节点的路由请求信息时，会按路由请求信息中 所记录的路由路径逆序地发送路由应答至发送节点，发送节点由此获取路由路径， 并将这个完整的、按序排列的路由信息写入所要发送的分组头部，并按序发送分组。 中间的转发节点收到待转发的分组后，首先在分组的头部查找出下一跳，然后转发 分组，直至将分组转发到接收节点。 相反地，如果源节点已知到达目的节点的路由路径时，源节点需要采用相应的 路由维护机制对路由进行维护。路由维护可以辨别出因为网络拓扑结构变化所造成 的不能准确地到达目的节点的路由路径。发现原有的路由路径不能再使用后，为了 能有保障地传送分组至目的节点，源节点会重新查找路由。d s r 的路由维护也是一 个比较复杂的问题，目前，已有不少路由维护算法，并处于不断的优化中。 2 4 贪婪路由算法( g r ) 贪心路由( g r ) 是基于地理坐标的路由协议中最简单的一种。g r 中，分组发 送节点局部最优地从一跳邻居节点中选取地理坐标最接近目的节点作为转发节点 进行分组的转发。发送一个分组时，发送方节点已经知道了目的节点的地理坐标， 并将这个地理坐标编码到分组的报头中，与分组一起发送给中间的转发节点。接到 分组后，转发节点依据贪心算法将分组转发至地理坐标上离目的节点最近的一跳邻 节点，直至目的节点为止。 。 ( 1 ) 算法步骤 本节中，使用一个简单的分组发送过程来演示贪心路由转发的基本步骤。 假设网络中有一要发送至目的节点d 的分组到达节点s ，节点s 有三个一跳邻 7 ? 。”1 7 。 、 硕士学位论文 m a s t e r st h e s i s 居节点，分别是节点a 、节点b 和节点x ，如图2 2 所示，节点s 做出转发决策之 前，分别计算节点a 、节点b 、节点x 距离目的节点d 的欧几里得距离。 图2 2 贪心路由，节点s 的邻节点x 地理坐标上距离目的节点d 最近 节点s 有三个一跳邻居节点，经计算得出，地理坐标上( 欧几里得距离) 离目 的节点d 最近的是节点x ，按照贪心算法口1 1 转发过程中的最近原则，节点s 将分组 转发给节点x 。整个分组传递过程中，不断重复这种贪心转发，直至分组到达目的 节点d ，如图2 3 所示。最终路由路径为s - x - y 乙d 。 。 图2 3 贪心路由的路由路径，s 专x 专y 专z 专d ( 2 ) 贪心算法局限性 贪心路由算法很简单，转发抉择只依赖于分组发送节点的一跳邻居节点，算法 需要维护的状态信息基本上是可忽略的，从一定程度上来说，仅取决于整个网络中 节点的密度。 网络中存在这样一种拓扑结构，发送节点s 到目的节点d 的地理坐标局部最优， 即比它所有的一跳邻居节点地理坐标上距离目的节点d 都更近，如图2 4 所示，节 点s 周围的点弧标识的是s 的无线电波覆盖范围，节点d 周围的点弧是以线段i s d l 8 硕士学位论文 m a s t e r st h e s i s 为半径，节点s 与节点d 的距离小于节点s 的一跳节点a 和一跳节点b 到目的节 点d 的距离，因此，从源节点s 到目的节点d 即使有两条路由路径( s 专a 专y 专d ) 和( s 专b 专x 专d ) 但贪婪路由中的源节点s 局部最优，不能把分组发送给邻居节 点。源节点s 发送分组到目的节点d ，在有两条路由路径的前提下，找不到任何一 跳可以进行分组转发的邻居节点，形成一个“路由空洞 。 曼 s 图2 4 路由空洞 2 5 贪心边缘无状态路由算法( g p s r ) 贪心边缘无状态路由( g p s r ) 是一个典型的基于地理坐标的路由协议。g p s r 路由利用一跳邻居节点及目的节点的地理坐标实现分组的转发过程。贪心路由受 限，即分组到达一个中间节点，而此节点的一跳邻居节点中没有比它自身离目的节 点更近的节点，无法继续贪心转发分组，这样一个受限区域被称为“路由空洞 。 贪心边缘无状态路由是对贪心路由的一种改进，利用右手原则【2 8 l ，在贪心路由受限 区域进行边界转发，解决贪心路由中的“路由空洞困境。 ( 1 ) 信标机制 a dh o e 网络中的g p s r 协议是基于邻居节点和目的节点的地理坐标的路由协 议，要知道这些处于动态移动中的节点的地理坐标信息得益于g p s r 协议中比较特 殊的信标机制。 g p s r 协议【2 4 】会定期向网络中所有的节点发送信标信号，期望得到邻居节点的 地理坐标信息，其目的主要是侦察网络中是否有节点的离去或者是否有新的节点加 入。信标的发送方式是广播，收到信标信号的节点对这条消息进行回复，并在回复 的消息中附带加入自身的地理坐标信息，两邻居节点相互交换地理坐标。 信标机制中，前后两次信标信号的发送时间间隔是随机的，假设t 是发送信标 硕士学位论文 m a s t e r st h e s i s 信号的平均时间间隔，则一个节点先后两次发送信标信号的时间间隔在【o 5 t ，1 5 t 上服从均匀分布，这样的发送机制，可以降低网络中节点发送信标信号的冲突率。 ( 2 ) 路由空洞 如图2 4 所示，以节点d 为圆心，源节点s 和目的节点d 之间的距离i s d i 为半 径的画一个圆，与节点s 的一跳无线电波的覆盖范围有一定的重叠区域，该区域被 称为“路由空洞一。 节点s 在“空洞 区域找不到地理坐标上离目的节点d 比自己离目的节点d 更近的邻居节点，按照贪心路由的原则，节点s 无法继续发送分组。前文中介绍 过g p s r 算法可以解决g r 算法的“空洞”问题，解决方案的本质是节点s 将在“空 洞 外部选择能够转发分组至目的节点的邻居节点作为转发节点，即沿着“空洞 的边缘进行转发。 ( 3 ) 右手原则 贪心转发路由算法有局限性，源节点( 或中间的转发节点) 可能会遇到“空洞 。 如果要继续转发分组，保障分组的到达成功率，局部最优的发送节点需要其他的路 由方法，做出一种不同于贪心的路由抉择，即在“空洞 外部选择能够转发分组到 达目的节点的邻居节点作为转发节点，沿着“空洞 的边缘继续转发分组。 乞 y 图2 5 右手原则 如图2 5 所示，分组从节点y 转发到节点x 后( 路径1 ) ，依据右手原则，下一 跳遍历的边是，以x 为定点，沿边( x ，y ) 逆时针方向的第一条相邻边，即到节点z ( 路径2 ) 。右手法则遍历一个密闭区域( 平面区域) 内部时，按顺时针方向的边顺 序，遍历顺序为( y 专x 专z 专y ) 。 右手原则边缘转发，并不适用于所有无线网络中的密闭多边形。在有交叉边的 硕士学位论文 m a s t e r st h e s i s 无线网络拓扑结构中，按右手原则可能在还没有遍历完这个多边形时就产生了一个 循环圈。有交叉边的多边形图也称为非平面图。 如图2 6c a ) 所示，假设节点s 产生一分组要发送至目的节点d ，右手原则的 转发过程中，不仅分组到不了目的节点d ，转发过程中还形成了一个循环圈 ( s 专u z 专w 专u 专s ) 。原因就是网络拓扑结构图中存在一对交叉边( w ，z ) 和( u ， s ) ，如果删去边( w ，z ) ，如图2 6 ( b ) 所示，整个遍历过程变成( s u 专z 专d ) ， 分组成功到达目的节点。从有交叉边的网络拓扑结构中删除交叉的边的过程，被称 作为网络图的平面化团】。 z ( a )( b ) 图2 6 平面图的构造 ( 4 ) 平面图 平面图的定义是，二维空间中，图中任意两条边都不交叉。无线网络结构中， 每个节点都有着以r 为半径的无线电波覆盖范围，可以看成是一个图，每个节点作 为图中的一个顶点，如果两个节点之间的地理距离小于半径r ，则存在这样一条边 ( 路径) 。g p s r 协议利用从网络图中去除不属于平面图的边的算法可以构建出一个 没有交叉连接的网络。r n g 和g g 是两种常见的平面图，根据这两种平面图的定义 从原来的网络拓扑结构图中去除不属于r n g 或g g 图定义的边就可以构造出适用 于边缘转发的网络平面图。 相关邻接图( r e l a t i v en e i g h b o r h o o dg r a p h ，r n g ) 【2 9 】的定义如图2 7 所示： 1 1 硕士学位论文 m a s t e r st h e s l 8 ，。一。、，：一- 。一- 、 ， ，j 、， j ，7 。，：。x 、， 、 ， i。、 fa o ? b ： j !： ， 、 ；i 、。t ， t ，。 、。 ， ，。 、， 。 、 。 、，：，一7 。、，。_ - ，- - _ ， 图2 7r n g 图 节点a 和节点b 之间存在边的条件是：对于任一节点x ，节点a 和节点b 之 间的距离要不大于节点x 到节点a 或节点b 的距离的最大值，即，图2 7 中以| a b i 为半径，点a 、点b 为圆心的两圆的重叠区域内，不存在任意其他节点x 。用下列 表达式表示： v x 彳，b ：d ( a ，b ) s m a x d ( x ，a ) l d ( x ，b ) 】 ( 2 1 ) 加百利图( g a b r i e lg r a p h ，g g ) 【3 0 1 的定义如图2 8 所示： 图2 8g g 图 节点a 和节点b 之间存在边的条件是，图2 8 中以l g a l 为直径的圆中没有其他 节点x 。用下列表达式表示： v x 彳，b ：d 2 0 ，曰) k 2 似，彳) + d 2 ( x ，召) j ( 2 2 ) ( 5 ) 算法步骤 g p s r 算法是由贪心转发和平面边缘转发 2 1 相结合的算法。在整个网络图中首 先进行贪心转发，贪心算法不可用时( 进入空洞区域) ，再依据右手原则进入边缘 转发的模式，绕过空洞区域后，g p s r 会返回到贪心转发的模式。 a dh o e 网络中的所有节点都会维护一张邻居节点表，表中存储着该节点的一 硕士学位论文 m a s t e r st h e s l 8 跳邻居节点的地理坐标，同时含有g p s r 做转发决策所需的所有信息状态，如表2 1 所示，其中展示g p s r 协议中节点做转发抉择时所需的报头。 表2 1 边缘转发模式下，g p s r 所使用的报头 参数参数说明 t 目的节点的地理坐标 l p 贪心转发失败的节点位置 l f 两邻接面交线与s t 的交点( 节点s 为边缘转发模式 中的始发节点，节点t 则是目的节点) e o换面后，分组边缘转发时遍历的第一条边 m 分组转发的模式：贪心转发或边缘转发 对表2 1 中各参数解释说明： 参数l p 中记录的是g p s r 从贪心转发模式进入边缘转发模式的节点的地理坐 标，该参数用来衡量g p s r 什么时候能重新进入贪心转发模式。 参数l f 中记录的是，边缘转发模式下，两相邻面的交线与s t ( 节点s 为边缘 转发模式中的始发节点，节点t 则是目的节点) 的交点，如图2 9 所示，边缘转发 时，直线s t 与各个遍历的面均有相交的点。 参数e 0 中记录的是，边缘转发模式下，在一个新的遍历面中，分组被传送的第 一路径。 g p s r 分组的报头中含有一个标识区域m ，标记着这个被发送的分组是在贪心 模式还是边缘模式下进行转发的。所有分组的初始标识均为贪心模式。分组的最初 发送节点会把已知的目的节点的地理坐标添加至待发送的分组的报头中。对于中间 的转发节点来说，分组中的目的地址是可读不可写的。 边缘转发模式下，中间的转发节点x 受到一个标识域m 显示为边缘模式时， g p s r 会对参数h ( 贪心转发失败的节点位置，假设记录的是节点y 的地理坐标) 及本节点的地理坐标进行比较，如果i x t i i y t i ，g p s r 结束边缘模式，重新标记参数 l p ，进入贪心转发模式。 本节中，使用一个简单的分组发送过程来演示贪心边缘无状态路由转发的基本 步骤。 步骤1 贪婪转发 当接收到一个标志为贪婪模式( 最初默认转发模式) 的分组时，转发节点查询 1 3 硕士学位论文 m a s t e r st h e s i $ 自己的一跳邻居节点表，计算并找出地理坐标上距离目的节点最近的一跳邻居节 点，然后进行转发。直至邻居节点中没有比转发节点本身更接近目的节点的节点， 将分组的报头中的标识m 标记为边缘转发模式，并进入边缘转发模式。 步骤2 边缘转发 上面章节介绍过，从复杂的网络结构图中去除不属于平面图的边，可以构建出 一个没有交叉连接的平面网络结构图。 g p s r 进行边缘转发时，使用的是简单的平面图遍历方法。如图2 9 所示： 图2 96 p s r 边缘转发( 换遍历面之前) 假设分组在节点s 处进入边缘转发模式，节点t 为目的节点。直线s t 贯穿平 面图上相邻的三个面。依据右手法则对这些面进行遍历，当遍历到与直线s t 交叉 的边时，切换到同样被s t 贯穿的相邻的面，继续遍历。节点s 依据右手法则，将 分组转发给节点a 专节点b ，本应该继续转发至节点d ，单由于直线b d 与直线s t 交叉，故进行遍历面的切换，从面n 切换至面忽。 从面f 1 切换至面忽后，先比较节点b 与节点s 至目的节点t 的欧几里得距离 的远近。如果没有更接近目的节点t ，继续按照之前所介绍的转发抉择方法，节点 b 边缘转发分组至节点c ，如此反复，直至分组到达目的节点t 。 2 6 本章小结 本章主要是讨论了a dh o e 网络及其基于地理位置的路由算法。a dh o e 网络中 的路由协议分为两类：主动路由协议和按需路由协议，其中，按需路由协议占绝大 部分，如动态源路由d s r 和贪心边缘无状态路由g p s r 。动态源路由d s r 中有两 个主要组成部分：路由的