（计算机应用技术专业论文）ad+hoc网络中基于地理位置的路由协议研究.pdf

i ， 0 题目：a dh o e 网络中基于地理位置的路由协议研究 舣舳：阳豳捌眦m g 0 c o m 融 n e t w o r k s 、 主题词：a dh o c 网络，基于位置路由，贪婪路由，转发漏洞，可扩展性 k e y w o r d s ：a dh o en e t w o r k s ，p o s i t i o n - b a s e dr o u t i n g ，g r e e d yr o u t i n g ， f o r w a r d i n gh o l e ，s c a l a b i l i t y 南京| i i i j i u 人学烦i ：研究生学位论义摘要 摘要 a dh o e 网络是由一组带有无线收发装置的移动终端组成的一个多跳临时性自治系统。 网络中的每个移动终端是主机也是路由器，根据路由算法参与路由的建立和分组转发工 作。基于位置的路由算法通过利用额外的位置信息消除了基于拓扑路由算法的局限性。基 于位置信息的路由协议不仅具有较高的可靠性及对动态拓扑有更好的适应性，而且具有低 丌销，高效率和可扩展性。 本文研究了基于网格位置服务的路i ：l d ( g l s ) 协议，分析了其优点和不足，然后在此基 础上改进得出了一种基于位置信息的路由协议h v s r 。该路由协议与g l s 路由协议相比具 有更低的开销，更高的效率和可靠性。h v s r 把网络区域划分为水平和竖直的带状区域， 每个结点的位置信息都会存储在它所在的带状域内的所有结点上。在位置更新时h v s r 使 用了同步聚合技术和位置服务器快速更新技术，在位置查询时使用了带状区域邻居节点信 息域和最远节点转发机制，既减少了更新和查询所需的时间，又提高了网络的可靠性。 此外，特别是针对基于网格的路由协议以及h v s r 路由协议中存在的转发漏洞问题， 本文提出了一种旁侧路由转发机制，重新定位目标节点的坐标位置信息及转发路径，有效 地提高了数据转发的成功率。 关键词：a dh o c 网络，基于位置路由，贪婪路由，转发漏洞，可扩展性 南京| i i i i i 也人学颂i ：t o d t 生学位论义a b s t r a c t a b s t r a c t a dh o cn e t w o r ki sam u l t i - h o pt e m p o r a r ys e l f - o r g a n i z e ds y s t e m ，w h i c hc o n s i s t so fas e to f m o b i l et e r m i n a lw i t ht h er a d i od e v i c e s e a c hm o b i l et e r m i n a li sb o t hah o s ta n dr o u t e r ， p e r f o r m i n gr o u t es e t u pa n dp a c k e tf o r w a r d i n ga c c o r d i n g t oa r o u t i n ga l g o r i t h m l o c a t i o n - b a s e d m u t i n ga l g o r i t h me l i m i n a t e st h el i m i t a t i o n so ft o p o l o g y b a s e dr o u t i n ga l g o r i t h mb yt h e a d d i t i o n a ll o c a t i o ni n f o r m a t i o n i tn o to n l yh a sh i g h e rr e l i a b i l i t ya n db e t t e ra d a p t a b i l i t yt h a n d y n a m i ct o p o l o g y , b u ta l s oh a sl o wo v e r h e a d ，h i g he f f i c i e n c ya n ds c a l a b i l i t y t h i sp a p e rs t u d i e dt h el o c a t i o n - b a s e ds e r v i c e so fg r i dr o u t i n gp r o t o c o l ( g l s ) ，a n da n a l y s e d i t s s t r e n g t h sa n dw e a k n e s s e s ，t h e np r o p o s e d al o c a t i o n - b a s e dr o u t i n g p r o t o c o l h v s r c o m p a r e i n g w i t ht h eg l s ，i th a sl o w e ro v e r h e a d ，h i g h e re f f i c i e n c ya n dr e l i a b i l i t y n l en e t w o r k r e g i o ni sd i v i d e di n t oh o r i z o n t a la n dv e r t i c a ls t r i p si nh v s r , t h el o c a t i o ni n f o r m a t i o no fe a c h n o d ew a ss t o r e di nt h es t r i p s a l ln o d e s w h e nl o c a t i o nu p d a t i n g ，i - i v s ru s e ds y n c h r o n o u s p o l y m e r i z a t i o na n ds e r v e rl o c a t i o nq u i c u yu p d a t et e c h n o l o g y , a n di nt h el o c a t i o nq u e r yi tu s e d n e i g h b o t si n f o r m a t i o no f t h es t r i pr e g i o na n dt h ef o r w a r d i n gm e c h a n i s mo ff a r t h e s tn o d e w h i c h n o to n l yr e d u c et h eu p d a t et i m e ，b u ta l s oi m p r o v et h er e l i a b i l i t yo ft h en e t w o r k i na d d i t i o n , p a r t i c u l a r l yf o r t h ef o r w a r d i n gh o l eo fg r i d - b a s e da n dh v s rr o u t i n gp r o t o c o l s , t h i sp a p e rp r o p o s e sam e c h a n i s mo fa l t e r n a t i v er o u t e ，r e l o c a t e st h el o c a t i o ni n f o r m a t i o na n d f o r w a r d i n gp a t ho ft h ed e s t i n a t i o nn o d e ，w h i c he f f e c t i v e l yi m p r o v e dt h es u c c e s sr a t eo fd a t a f o r w a r d i n g f k e y w o r d s ：a dh o cn e t w o r k s ，p o s i t i o n - b a s e dr o u t i n g ，g r e e d yr o u t i n g ，f o r w a r d i n gh o l e ， s c a l a b i l i t y 南京邮f u 人学倾i j 研究生学位论文 日录 目录 摘要i a b s t r a c t i i 目j i 2 ：i i i 第一章绪论1 1 1a dh o c 网络的研究背景和现状1 1 2a dh o c 网络的特点2 1 3 本文研究的主要内容3 1 4 章节安排4 第二章a dh o c 网络路由协议概述5 2 1a dh o e 网络路由算法及路由协议定义5 2 2 a dh o e 网络路由协议设计面临的问题及设计原则5 2 2 1a i dh o e 网络路由协议设计面临的问题5 2 2 2a dh o e 网络对路由协议的设计原则6 2 3a dh o e 网络路由协议的分类7 2 3 1 先应式路由协议和按需的路由协议8 2 3 2 平面结构路由协议和分层结构路由协议9 2 3 3 单播路由协议和多播路由协议l o 2 3 4 中小规模和大规模( 可扩展) 路由协议1 0 2 3 5 其他路由协议1 0 2 4 本章小结1 1 第三章基于地理位置信息的路由协议1 2 3 1 基于位置信息的路由协议实现原理1 2 3 2 基于位置信息的路由协议分类1 3 3 3 位置辅助的路由协议1 4 3 4 贪婪路由15 3 5 定向洪泛2 0 3 6 分层路由2 0 3 7 本章小结。2 1 第四章改进的基于g l s 的位置信息路由协议2 2 4 1 基于网格位置服务路由协议( g l s ) 2 2 4 1 1g l s 路由协议的工作原理2 2 4 1 2 基于网格的位置服务( g l s ) 算法分析2 3 4 1 3g l s 路由协议的缺陷和不足2 7 h i 塑室坐! 垫叁兰塑! ：型堕! 竺堂垡堡苎 一 望茎 4 2 对g l s 改进的路由算法h v s r 2 8 4 2 1 协议模型2 8 4 2 2 协议原理2 9 4 2 3 可扩展性分析4 3 4 3 本章小结4 4 第五章仿真试验4 5 5 1n s 2 网络模拟器4 5 5 1 1n s 2 仿真器介绍4 5 5 1 2n s 2 网络模拟过程分析4 7 5 2 参数设置及分析4 8 5 2 1 参数设置一4 8 5 2 2 参数分析一4 9 5 2 3 容错性分析4 9 5 3h v s r 与g l s 仿真结果比较5 2 5 3 1 查询成功率比较。5 2 5 3 2 开销比较一5 3 5 3 3 可靠性比较5 4 5 4 本章小结5 5 第六章总结和展望 6 1 文章总结5 6 6 2 未来展望5 7 参考文献一5 8 致谢6 l 作者在硕士研究生期间发表的论文6 2 作者在硕士研究生期间参加的项目6 3 i v 们r 常生活的方：疗面面。随着计算机网络技术与无线通信技术的快速发展，移动无线网络 正成为计算机通信领域中倍受注目的一环，成为互联网的最新发展方向。它为移动通信提 供了一个崭新的发展空间，同时使互联网有着更广阔的发展前景。与此同时，移动无线网 络也向互联网提出了新的挑战，它要求对传统网络技术从底层进行根本变革以适应这一新 的发展方向， 无线通信技术和计算机网络技术的快速发展为无线移动通信网络奠定了基础，移动a d h o e 网络正是在此环境下诞生的，并逐渐成为当前移动无线网络研究的重点。移动a dh o e 网络( m a n e t ) 是一个复杂的分布式系统，它由能自由移动和动态地自组织成任意网络拓扑 结构的无线节点组成。它不需要固定基础设施的支持，能够在不能或不便利用现有网络基 础设施的情况下提供一种通信平台，从而拓宽移动通信网络的应用场合，可广泛应用于国 防战备、抢险救灾、应对突发事件等无法得到有线网络支持或临时需要通信的环境，是下 一代网络的重要组成部分。 a dh o e 网络并不是一个新的概念，它已经以各种形式存在了3 0 多年。传统上军方的 移动网络是a dh o e 网络的唯一的通信网络应用。自a l o h a 网络( 1 9 6 8 ) 成功研制美军制定 和支助了若干a d h o e 网络相关技术研究计划。1 9 7 2 年，d a r p p r n e t ( p a c k e t r a d i o n e t w o r k ) 研究计划，丌始探索移动环境下的数据通信技术与应用问题，其研究成果p r n e t 网络也 是出现最早应用于军事移动通a dh o e 网络。1 9 8 3 年，d a r p a 制定了s u r a n ( s u r v i v a b l e a d a p t i v en e t w o r k ) 计划，其目的是进一步拓展p r n e t 的应用技术，以支持可生存与自适应 的无线网络的建立，重点研究了移动环境条件下网络拓扑动态变化的自适应网络和实现技 术。 二= 二十世纪9 0 年代以来，移动a dh o e 网络的研究在世界范围内方兴未艾，从无线通信 领域 ，的一个小分支逐渐扩大到相对较独立的领域。目前，无论国际上，还是在区域上( 欧、 南京f | | f f u 人学坝l j 研乡i 生学位论义第一常绪论 美和亚洲等地区) ，周期性的a dh o c 网络学术会议同益增多。总结国内外研究现状，a dh o c 网络成果主要在以下几个方面【2 】： 1 提出新的路由协议。a dh o e 路由面临的主要挑战是传统的保存在节点分布式路由 数据库如何适应网络拓扑的动态变化，目前，路由协议的研究仍然是移动a dh o e 网络成 果最集中最重要的部分。 2 提出基于a dh o e 网络的媒体接入控制( m a c ) 协议。 3 移动a dh o c 网络与移动通信中的蜂窝网络的互联互通。 4 基于a dh o e 网络的多播组播协议、t c p 协议、地址分配、功率( 节能) 安全性 问题、分布式算法、q o s 等方面有一些研究成果。 1 2a dh o e 网络的特点 与传统通信网络相比，a dh o c 网络是一个多跳的临时性的自组织网，a dh o e 网络节 点之间是通过多跳数据转发机制进行数据交换的，这就需要通过路由协议进行分组转发决 策。a dh o e 网络具有以下特剧。3 l ： ( 1 ) 无中心和自组织性 a dh o e 网络没有绝对的控制中心，所有节点地位平等，各节点通过网络协议和分稚式 算法协调工作，节点可以随时加入和离开网络，整个网络具有独立组网能力。 ( 2 ) 动态变化的网络拓扑 a dh o e 网络的移动节点能以任何速度和方向移动，加上无线信道的功率和干扰等因 素，因而网络拓扑结构随时变化并难以预测。 ( 3 ) 多跳路由和无线传输 由于节点发射功率的限制，节点的覆盖范围是有限的。当要与覆盖范围以外的节点通 信时，需要通过中间节点进行中继，因而信息往往经过多跳。a dh o e 网络采用无线传输 技术，而无线信道的质量相对较差，共享无线信道的冲突、信号衰减、噪音、信道之间的 干扰等等是必须考虑的问题。 ( 4 ) 移动终端的便携性和资源局限性 移动终端虽具有携带方便、轻便灵巧等优点，但也存在着固有的缺陷，如能源受限、 内存较少、c p u 处理能力较低等缺点，从而为应用程序设计的丌发带来一定的难度。 ( 5 ) 安全性较差 由于采用无线信道、有限电源、分布式控制等技术，a dh o c 网络的安全性较差，容易 2 南京邮il i 人学坝j j 研，e 生学位论义第一章绪论 受到被动窃听、主动入侵、拒绝服务、剥夺“睡眠”等网络入侵和攻击。 ( 6 ) 网络的可扩展性不强 由于采用t c p i p 协议中的子网技术使得i n t e m e t 具有网络的可扩展性，而a dh o c 网 络动态变化的网络拓扑结构使得子网技术所带来的网络可扩展性不能得到应用。 ( 7 ) 存在单向链路 在无线通信中，由于通信设备频率的强弱和地形环境因素的影响，使得实际应用中常 常存在单向链路。比如，车载台终端发送功率比手持终端大很多，所以有时手持终端可以 收到来自车载台的信号而车载台却无法接受到手持终端的信号，即存在一条从车载终端到 手持终端的单向信道。 ( 8 ) 生存时间短 a dh o c 网络通常是由于某些特定原因而临时创建的，在使用结束后，网络环境将会自 动消失。因此，a dh o c 网络的生存时间相对于固定网络而言是短暂的。 以上的这些特点使得a dh o c 网络在体系结构、网络组织、协议设计等方面都与普通 的蜂窝移动通信网络和固定通信网络有着比较显著的区别 1 3 本文研究的主要内容 由于a dh o c 网络目前处于研究阶段，在网络的各个层面都有许多技术难题值得研究 和解决，本文主要针对a dh o c 网络在网络层中基于地理位置信息的路由算法进行研究， 在现有的基于位置信息协议的基础上，改进了基于位置信息的路由协议。本文研究的内容 如下： 1 深入地分析了a dh o c 网络的特点和研究现状，对现存的a dh o c 网络路由协议进 行了分类，并对各部分作了较为深入的研究。 2 研究了常见的基于地理位置信息的路由协议及其实现原理，对这些算法协议进行 了分析和比较，深入探讨了这些协议存在的优点和不足。 3 对基于网格位置服务路由( g l s ) 协议进行了深入地分析和研究，然后在此基础上改 进得出一种具有低丌销、高效率和可扩展的基于位置信息的路由协议h v s r 。文章首先探 讨了h v s r 的协议模型，对协议的h e l l o 报文发送、位置更新、位置查询和数据转发几 个部分进行了深入地分析和研究。并对h v s r 的可靠性和可扩展性进行了探讨。特别针对 路由协议中转发漏洞问题进行了研究，并提出了旁侧路由转发机制，有效地提高了数据转 发的成功率。 南京i i i | j l u 人学颂i ：研究生学位论义第一章绪论 4 通过仿真实验将改进的h v s r 和g l s 路由协议进行性能分析和比较，在查询成功 率，字节丌销，和容错性方面显示了h v s r 路由协议具有更好的性能。 1 4 章节安排 本文共分为六章，各章节安排如下： 第一章介绍了a dh o c 网络的研究背景、发展历史及特点，介绍了本文研究的内容， 并对本文结构做出安排。 第二章根据不同的分类标准对传统的a dh o c 路由协议进行分类，并对该分类下的路 由协议进行深入的分析和研究。 第三章研究了常见的基于地理位置信息的路由协议实现原理和研究现状，并对这些 算法协议进行了探讨和比较。 第四章对基于网格位置服务路f 1 4 ( g l s ) 协议作了深入探讨，分析了该协议的优点和不 足，然后在此基础上改进得出了一种基于地理位置信息的路由协议h v s r ，并对该协议作 了深入的探讨和研究。 第五章对h v s r 的性能作了分析和研究，并通过仿真实验将h v s r 和g l s 进行了性 能比较。 第六章对本文的工作进行总结，并提出需要进一步研究的方向。 4 南京i l l l jo u 人学颂l j 研究生学位论义 第二帝a d h o c 网络路由协议概述 第二章a dh o e 网络路由协议概述 本章主要介绍a dh o e 网络路由协议的概况及分类，并对各部分进行分析和介绍。 2 1a dh o c 网络路由算法及路由协议定义 a dh o e 网络设计中的一个关键问题是开发出能够提供高效率和高可靠性的路由协议。 网络节点的移动性使得网络拓扑结构动态的变化，传统的基于因特网的路由协议无法适应 这些特性，需要有专门的应用于a dh o c 网络的路由协议。 1 路由算法 路由算法( r o u t i n g a l g o r i n l i l l ，i l l 可以理解为为了实现路由功能而设计的计算方法，它是 网络层软件的核心部分，负责确定所收到分组应传送的外出路线。路由算法可以根据多个 特性来加以区分。首先，算法设计者的特定目标影响了该路由算法的操作；其次，存在着 多种路由算法，每种算法对网络和路由器资源的影响都不同；最后，路由算法使用多种度 量机制 w 一 v 一 d 一 z 一 y 一 x 。 在参考文献【1 2 1 中提出在发送数据分组时利用右手法则绘制边界。边界转发的前提是需 要事先构造一个平面图来描述网络拓扑，该平面图的任意两条都不相交。 不含交叉的边的图就称为平面图。g p s r 构造平面图的关键是删除网络拓图中交叉的 边。对于网络中的所有节点，假设一跳通信范围的半径都为r 。如果节点n 和m 的距离d ( n ， m r ，则认为n 和m 之间有一条边( n ，m ) 。进一步假节点所处位置的高度相差不大，这样 可大致认为所有节点都位于同一平面内。 r n g ( r e l a t i v en e i g h b o r h o o dg r a p h ) 和g g ( g a b f i e lg r a p h ) 是两种常见的平面图。通过特 定的算法，将原图中不属于r n g 或g g 的边删除，就可以得到了不含交叉边的平面图。 在实际应用中，生成平面图需要采用分布式处理方式，每个网络节点都要运行该算法，它 仅仅需要知道附近的网络拓扑结构。为了确保样一个分布式策略的成功，需要有一个重要 前提：当删除图中的某些边使原图为r n g 或g g 时，必须保证不会引起网络分割。具体构 造过程我们这里不作详细介绍。 ( 3 ) 贪婪转发和边界转发的结合 g p s r 路由协议结合使用贪婪算法和边界算法来转发数据分组。在完整的拓扑图中采 用贪婪转发，当贪婪算法找不到下一跳节点时，则在平面图中采用边界转发算法决定下一 跳。网络中的所有节点都保存一跳邻节点列表，该列表提供了贪婪转发数据分组需要的所 有信息。当中间节点收到标记为贪婪模式的数据分组时，它首先在邻节点列表中选择离目 的节点最近的节点，如果选择的邻节点比自己距离目的节点更近，则采用贪婪算法将数据 分组转发给该邻节点：否则就标记该数据分组为边界转发模式，并进行边晃转发。 1 8 塑室些! 皇叁兰堡! 塑! 塑竺兰垡笙兰笙兰童苎丝些垡堡笪星箜堕虫坐坚 g p s r 根据简单的平面图对数据分组进行边界转发。在图3 8 中，平面图的边将整个 图划分成许多小的互不重叠的有界多边形和一些无界区域，这些有界多边形和无界区域统 称为f a c e 。其中，有界多边形称为内部f a c e ，无界区域称为外部f a c e 对于一个以d 为目的 节点的数据分组，如果在中间节点x 处采用贪婪转发失败，则改用边界转发模式。由于x 距离d 较远，数据分组在转发过程中需要经过多个f a c e ，这些f a c e 都被x 与d 之白j 的连 线分割，且距离d 越来越近。如图3 8 所示，数据分组从x 到d ，需要经过三个内部f a c e ( 前 两个和最后一个) 和一个外部f a c e ( 第三个) 。边界转发是指数据分组依次沿着这些f a c e 的边 界转发，在每个f a c e 中，依据右手法则选择下一条边。 g p s r 不足之处是它只适用于二维空间，要应用于三维空间，要做相应的改进和优化。 s 图3 8 边界转发示意图 2 g e d i r ( g e o g r a p h i cd i s t a n c er o u t i n g ) g e d i r 1 6 l 假设每个节点都知道它一跳节点的位置。与g p s r 类似，g e d i r 中节点事先 不建立路由，当收到数据分组时直接将分组转发至下一跳。g e d i r 采用贪婪转发的方式。 当中间节点收到数据分组时，首先比较它的各个邻节点到目的节点的距离，并且选择离目 的节点最近的邻节点作为下一跳。但是通过该方式选择的下一跳并不比当前节点距离目的 节点更近，g e d i r 也会出现局部最优化问题。 在g e d i r 中，一旦出现局部最优化问题，采用的策略是丢弃数据分组。当网络中局 部最优化问题出现较为频繁时，就会导致数据分组的大量丢失。为此又进一步提出了改进 的算法：f - g e d i r ( f 表示洪泛) 和c g e d i r ( 同时向c 个邻节点转发分组) ，以及2 - h o p g e d i r ，事实证明这些是可以改善g e d i r 的性能的。 3 g r a ( g e o g r a p h i c a lr o u t i n ga l g o r i t h m ) g r a 也是一种基于位置信息的路由协议，它采用贪婪算法选择下一跳节点。如果出现 局部最优化问题，g r a 启动路由发现机制( 洪泛机制) 搜索从最佳主机到目的节点的路由， 1 9 南京邮i 乜人学顾i j 研究生学位论义第三章基于地理位置信息的路由协议 当收到路由回复消息时，在路由表中保存该路由条目以减少将来可能发生的洪泛。 3 5 定向洪泛 在定向洪泛f 17 】的路由协议中，节点将向目的节点方向所有邻节点转发数据分组，该算 法具有很好的鲁棒性，但是它同时也加重了网络的负载。 d r e a m ( d i s t a n c er o u t i n ge f f e c ta l g o r i t h mf o rm o b i l i t y ) t 1 4 1 是种典型的定向洪泛路由 协议。在d r e a m 中，节点不需要保存路由表。源节点和每个中间节点分别计算自己到目 的节点的方向，基于节点的移动信息，可以确定一个夹角范围，称为转发域。中间节点将 数据分组转发给该转发域内的所有一跳节点，直到数据分组成功递交给目的节点。 d r e a m 算法有以下优点： 1 能保证无路由环路，数据分组的传播都是沿着目的节点的方向进行的。每次转发离 源节点都要远一些，且节点可以知道自己到最近收到过那些分组，当重发收到来自同一源 节点相同分组时，将丢弃重复的分组。从而避免了路由环路。 2 拥有较好的鲁棒性。每次转发都是发送给目的节点方向的多个节点。该机制类似于 提供了到目的节点的多条路径，且某条链路上分组的丢失不会影响其他链路上的分组。 3 节省带宽和节点能量。d r e a m 中控制分组只有位置更新分组和a c k 分组，这两 种分组携带的信息较少。并且节点根据自己的移动速度独立确定发送位置更新分组的周 期。因此，控制分组的数目和控制分组在网络中传播的范围可得到优化。从而d r e a m 可 以节省更多的带宽和能量以用于数据分组的传输。 d r e a m 虽然限制了到目的节点的洪泛范围，其本质还是基于洪泛的，因此，它不适 用域节点数目多和数据量大的网络。它比较适合于对可靠性要求高但数据传送不频繁的环 境。 3 6 分层路由 分层路由【”1 可以减少网络中节点处理时间的复杂度，他适用于较大规模网络的情形。 在传统的网络中，每个节点处理的复杂性可以通过建立某种形式的分层来大大减小。分层 路由允许这些网络可以扩展到拥有大量的节点，这在基于拓扑的网络中已经被证实是一种 非常有效的路由机制。下面我们介绍两个基于位置信息的分层路由协议：终端路由 ( t e r r n i n o d e sr o u t i n g ) 和网格路由( g r i dr o u t i n g ) 。这两个路由协议都基于两层的路由， 在一层采用基于位置信息的路由协议，而在另一层采用不基于位置信息的路由协议。 2 0 南京邮l u 人学坝i ：研究生学位论义第三币基于地理位置信息的路由协议 1 终端路由( t e r m i n o d e sr o u t i n g ) 终端路由( t e r m i n o d e sr o u t i n g ) 协议是一种将分层与位置信息的相结合的路由协议。 它结合了两种路由算法；t l r ( t e r m i n o d el o c a t i o nr o u t i n g ) 和t r r ( t e r m i n o d er e m o t e r o u t i n g ) 。t l r 基于距离矢量信息确定路由并转发数据分组，t r r 基于地理位置信息转发 数据分组。如果目的节点与发送者很近时，将采用t l r 算法转发数据分组来，如果转发节 点距离目的节点很远时，则使用t r r 算法转发数据分组。具体数据分组采用t l r 还是t r r 方式转发，可以通过分组头中的标记位标识。 使用t l r 和t r r 结合的方式，可以有效避免路由环路。由于每个节点在转发数据分 组时仅依靠本节点或其他少数节点的信息，所以该协议的扩展性较好。分组的递交成功率 和路由丌销都比以往的a dh o c 网络路由协议有所改进，而且该协议还能提供到目的节点 的多条路由，能很好地适应网络拓扑的动态变化。 2 g r i d ( g r i dr o u t i n g ) 大部分路由协议目的是解决如下三个问题，查找路由，转发数据分组和路由维护。 g r i d ! b 】协议利用位置信息解决以上三个问题，它是一个完全基于位置信息的路由协议。 该协议中，网络的覆盖区域被划分为小的方形区域，每个区域就是一个网格，每个网格选 择一个节点作为该网格作为该网格所有节点的l e a d e r ，负责转发数据分组。以往的路由协 议都是逐条查找路由，而g r i d 采用逐网格查找路由的方式。 g r i d 中的路由生存时间较长，路由对节点的移动不太敏感，而且路由控制分组的开 销与网络中节点密度的关系不大。在下一章中，文章在基于g r i d ( g r i dr o u t i n g ) 思想的 基础上改进g l s 路由协议使之具有较低的开销、更高的效率和可扩展性。 3 7 本章小结 本章介绍了几种常见的地理位置信息的路由协议，位置辅助的路由协议l a r 利用位 置信息限制了路由搜索范围，其开销明显小于传统的洪泛协议。贪婪路由中g p s r ，g e d i r 和g r _ a 针对贪婪算法固有的局部优化问题，分别提出了自己的解决方法。g p s r 引入了边 界转发算法；g e d i r 采用了丢弃局部优化问题的数据分组的方法；g r a 在遇到局部优化 问题时，采用启动路由寻找机制查找目的节点的方法。d r e a m 采用定向洪泛机制，从地 理范围上限制数据分组的传输，t e r m i n o d e s 和g r i d 属于分层路由算法，在t e r m i n o d e s 路由协议中，采用t l r 和t r r 两种转发方式；g r i d 采用划分网格的思想转发分组。 2 1 南京i i i i g i e 人学硕l ：研究生学位论文第p q 章改进的基于g l s 的位置信息路由协议 第四章改进的基于g l s 的位置信息路由协议 移动a dh o e 网络( m a n e t ) 是一种动态易失性的网络【2 4 l ，在信号被阻隔或有障碍物 的情况下，特别是节点数目急剧增多和节点间歇性的连接到网络中时，现有的a dh o e 路 由协议会出现可靠性急剧降低，性能急剧下降。由于节点的移动性、带宽有限、可获得的 能量有限等原因，对移动a dh o e 网络进行路由提出了具有挑战性的要求。i e t f 的m a n e t 工作组已经定义了多种基于拓扑的路由协议，如d s d v 、o l s r 、t b r p f 、d s r 、t o r a 、 a o d v 、z r p 、f s r 等。这些基于拓扑的路由协议要么主动的在节点中维持路由信息，要 么按需的利用一种洪泛的方法来探测路由。路由建立后需要大量的资源用于维护路由，随 着网络规模的增加，它会使得网络效率急剧下降，难以适应移动环境下网络拓扑快速变化 的情况，以及信息传递实时性要求。在移动a dh o e 网络中，正常的路由有可能因为节点 故障或者地形的限制而被中断，a dh o c 网络所使用的路由协议必须具有高的可靠性来保证 消息的传输。因此，设计低开销，高效率，高可靠性和可扩展的位置信息路由协议，对于 a dh o e 网络应用来说具有极大的现实意义。 本章就是在基于网格位置服务路f l q ( g l s ) 0 t 议的基础上改进得出了一种基于位置信息 的路由协议h v s r ，与g l s 相比h v s r 具有较的低开销，高效率，高可靠性和可扩展性 4 1 基于网格位置服务路由协议( g l s ) 4 1 1g l s 路由协议的工作原理 g l s ( g r i dl o c a t i o ns e r v i c e ) 1 9 】最早由j “提出，g l s 路由协议是一种基于位置信息的 路由协议，利用网格定位服务进行路由定位、分组转发、位置信息维护的路由协议。g l s 是利用一致性哈希技术将网络节点的当前位置信息存储在广泛分于网格的位置服务器上， 将负载分布到所有网格节点上，从而不依赖于某个或某些特定节点，该方法适用于大规模 网络。g l s 路由协议具有很好的路由健壮性。 g l s 的基本思想是每个节点在整个网络中维护多个位置服务器，这些位黄服务器不是 指定的，而是分布式选择算法。经过分布式选择算法后，每一个节点在离它近的地方服务 器数目较多，而在离它远的地方服务器数目少。这样一来位置服务器的数目会随着网格阶 数的增加而减少。每个节点都有可能作为其它节点的位置服务器，位置服务器的结构也和 普通的节点没有区别。 2 2 南京邮i u 人学颂i ：研究生学位论义第川章改进的基于g l s 的位置信息路由协议 g l s 是一种分层式的位置服务方法，并且首次将分格技术和位茕信息服务两者结合。 在g l s 中，其将网络拓扑分成如图4 1 所示的网格。在这个分层式架构中，第1 1 层的网格 包含4 个下一层( 即n 1 层) 的网格，在图4 1 中，每一个2 阶网格包含4 个1 阶网格，每 一个3 阶网格包含4 个2 阶网格。在每一个1 阶网格中的每一点定期以h e l l o 分组广播， 并在邻居节点表中存储该1 阶网格内所有的点的位置信息。 应该注意的是，并不是任意的4 个相邻的( n 1 ) 阶网格都能组成n 阶网格，每个n 阶 网格最左下角的坐标必须满足( a 2 n l , b 2 n - ! ) ，其中，a , b 为整数( 可以看作一个二维平面) ， n = l ，2 ，3 n 。同时，为了避免出现网格重叠，规定任意一个n 阶的网格能且只能属于一个 ( n + 1 ) 阶网格，而不能属于多个。 g 图4 1 四分法网格的位置服务器分布 4 1 2 基于网格的位置服务( g l s ) 算法分析 1 位置服务器的选择 g l s 路由协议中引入了一个位置服务器的概念，每个节点把它的位置信息分别存放在 网络中的多个位置服务器中，从而能够保障位置信息的快速查询。如果节点想查询其他节 点的位置信息，就可以通过节点的任意一个位置服务器得到节点的位置信息。 利用网格定位服务每个节点在每层网格中选择几个节点作为自己的位置服务器，位置 服务器分别分布在该节点所在网格的多个兄弟网格中，定期接收该节点发出的位置更新消 息。a dh o c 网络中的每个节点通过某种定位系统，如g p s 获得自己的当前位置信息，定 期发送h e l l o 消息通告同一网格中无线覆盖半径内的邻居节点自己的存在、网格标识i d 以及位置等信息。若采用正方形四分法划分网格，位置服务器的分布如图4 1 所示。其中，n 代表任意一个节点，s 代表该节点在各层网格中的位置服务器。因此，网络节点的当前位置 信息分布在整个网络的位置服务器上。 堕室业! 坠叁兰堡! 型! 壅竺堂篁堡竺至! ! 至塾丝堕苎鱼生兰箜篁堡笪皇堕虫塑坚 g l s 是利用一个预先定义的很强的哈希函数把节点的唯一标识( 如网络地址，m a c 地址甚至是位置信息等) 映射为一个随机的识别码，称为i d ，一般为一个整数，并定义a 的“最亲密节点”为大于a 的i d 号中最小的i d 号所标识的节点。下面以图4 2 为例，说明 位置服务器的选择算法。结点在网格结构图中，每一阶网格都需要选择3 个位置服务器， 选择策略是“最亲密结点”。各个节点都维护一个位置服务器列表，其中包含了各阶位置服 务器的i d ，位置和速度等，而其列表需要定时更新，当节点移动时也需要更新位置服务器。 如图中节点s 的i d 为9 ，它选择的一阶位置服务器的i d 分别为3 ，1 2 ，3 3 。二阶位置服务器 的i d 分别1 0 ，2 ，1 5 。三阶位置服务器的i d 分别1 3 ，2 1 ，2 5 。对于网格( 2 ，5 ，7 ) 由于都比9 小，这罩采用循环比较的方案，即把所有的数字排成一个环，从而就选取最小的2 作为其 位置服务器， 8 7 i r 8 7 1 3 8 5 4 3 1 8 5 2 1 s 0 衢 诣 笛 1 0 2 1 9 5 7 3 2 3 s 9 1 5 万 3 7 3 3 1 2 7 3 图4 2 位置服务器的选择算法 2 g l s 的位置更新 上述的位置服务器选择假设结点已经知道网络中所有结点的i d 和位置，从而把自己 的位置坐标发送给算法选择的位置服务器。实际上，结点发送自己的位置坐标时，不知道 它们的i d 。其位置更新过程如图4 3 所示。 ( 1 ) 每个结点进行2 跳受限的h e l l o 分组广播，h e l l o 报文中包括结点的i d 、 位 置、移动平均速度、单跳邻居列表和转发指针等。当邻居结点接收到h e l l o 报文，它更 新本地的邻居位置信息表。这样，结点可了解到2 跳内邻居内结点的i d 及位置信息的变 化。 ( 2 ) 实际中，结点只知道部分结点的标识及位置信息。图4 3 中，假设结点l 要在一个 n 阶栅格中更新其位置，该栅格的“最亲密结点”就是结点2 。但结点l 的u p d a t e 分组 通过地理路由转发只能到结点1 1 ，结点1 1 选择其位置表中的结点1 的“最亲密结点”为9 ， 2 4 南京i l i | j l u 人学颂t ：r o f 究生学位论义 第p q 章改进的基十g l s 的位置信息路由协议 转发u p d a t e 分组到9 ；结点9 选择其位置表中的结点1 的“最亲密结点”为2 ，转发u p d a t e 分组到2 ：结点2 成为最终的位置服务器，对结点l 的位置进行更新。 2 工上、1 、逸9 3 2 l 1 6 2 17 6 3 31 96 5 4 1 2 3 4 1 75 3 图4 3g l s 的位置更新 3 g l s 中的位置查询 g l s 服务器选择算法保证了位置查询的服务器与更新位置时选择的服务器是一致的。 如图4 4 所示，假设结点2 1 欲获取结点l 的位置。 ( 1 ) 检测