基于地理位置预测的adhoc网络洪泛控制路由协议研究大学本科毕业论文.doc

《基于地理位置预测的adhoc网络洪泛控制路由协议研究大学本科毕业论文.doc》由会员分享，可在线阅读，更多相关《基于地理位置预测的adhoc网络洪泛控制路由协议研究大学本科毕业论文.doc（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分类号 密级 UDC 学 位 论 文基于地理位置预测的Ad Hoc网络洪泛控制路由协议研究作者姓名：熊 为指导教师：沙 毅 副教授东北大学信息科学与工程学院申请学位级别：硕士学科类别：工程学科专业名称：电子与通信工程论文提交日期：2013年6月论文答辩日期：2013年6月学位授予日期：答辩委员会主席：评 阅 人 ： 东 北 大 学2013年6月A Thesis in Communications and Information SystemThe Research of Flooding Control Routing Protocol based on Location Prediction

2、 in Ad Hoc NetworkBy XIONG WeiSupervisor: Associate Professor SHA YiNortheastern UniversityJune 2013独创性声明本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 日 期：学位论文版权使用授权书本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论文的规定：即学校有权保

3、留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部或部分内容编入有关数据库进行检索、交流。作者和导师同意网上交流的时间为作者获得学位后：半年 一年 一年半 两年学位论文作者签名： 导师签名：签字日期： 签字日期- I -东北大学硕士学位论文摘 要基于地理位置预测的Ad Hoc网络洪泛控制路由协议研究摘 要Ad Hoc网络是一个无线多跳的临时性自治系统。由于它不依靠任何固定基础设施，并且具有组网迅速、灵活等特点，在军事和民用领域有广泛应用。针对这些特点，Ad Hoc网络也逐渐成为人们的重点研究对象。它的路由协议更是其中的重点和难点，许多学者

4、专家都对它进行了大量的研究。Ad Hoc网络中广播是一项基本的通信手段，所以大多数按需路由协议都采用广播即洪泛路由请求的方式来寻找路由。虽然盲目洪泛方式具有简单且可靠的覆盖率，但在移动节点密集的网络中会造成大量重复的报文而消耗大量的网络资源。盲目泛洪可能会造成网络中极为严重的冗余、竞争与碰撞，这一现象称为广播风暴。为了减轻广播风暴的问题，转发节点的数目应该被限制。本文在分析目前提出的抑制广播风暴的算法基础上提出一种适应移动Ad Hoc网络环境的基于GPS定位技术的洪泛受限的广播算法。算法中，每个节点通过计算自己与其邻居节点当前的相对位置关系来判断是否转发请求包，而不转发的节点采取流言（Goss

5、ip）机制中的缓存等待算法，即在缓存时间内统计所接收到的来自邻居节点的相同的请求包的数目来判断是否转发路由请求包。为了验证这种广播受限的算法的性能，我们将其应用于AODV路由协议的路由请求过程中并形成LA-AODV-Gossip（Location-Aided）路由协议。为了能使算法能够适应某些特定的区域或者某个特定的场合本文又提出一种基于ARIMA模型来预测节点下一时刻的地理位置信息，形成了LP-AODV-Gossip（Location-Prediction）来提高寻路效率同时增强链路的稳定性。在NS2仿真平台上，分别改变节点个数与最大移动速度两个场景参数对传统的AODV路由协议、LA-AOD

6、V-Gossip路由协议和基于地理位置预测的LP-AODV-Gossip路由协议进行仿真和性能分析。仿真结果表明，改进后的LA-AODV-Gossip路由协议在路由开销、路由寿命和报文投递率都要优于传统的AODV，并且在一些特殊的网络场景下，具有预测功能的LP-AODV-Gossip协议能更加有效地减少网络中广播冗余、降低路由发现延迟的同时保证数据传输的可靠性。关键词：Ad Hoc网络；路由；GPS；ARIMA；预测；NS2仿真- VII -东北大学硕士学位论文The Research of Flooding Control Routing Protocol based on Location

7、 Prediction in Ad Hoc NetworkAbstractThe Research of Flooding Control Routing Protocol based on Location Prediction in Ad Hoc NetworkAbstractThe Ad Hoc network is a wireless multi-hop autonomous system. It does not rely on any fixed infrastructure, also can build network rapidly and flexibly, so are

8、 widely applied in military and civil fields. According to these characteristics, the Ad Hoc network gradually becomes the focus of study. Routing protocol is the key point appealing many experts to do a lot of research.Broadcasting communication is a basic kind in Ad Hoc network, and most on-demand

9、 routing protocols flood route request to find route. Although blind flooding is simple and has a reliable coverage, it brings a large number of duplicate packets and cases waste of cyber source in a dense network.Blind flooding may cause serious redundancy, contention and collision in the network,

10、which is called the broadcast storm. In order to reduce the broadcast storm problem, the number of forwarding nodes should be limited.This paper proposes a limited flooding scheme using GPS positioning technology to adapt the mobile environment in Ad Hoc network.In the algorithm, each node calculate

11、 relative position between themselves and their neighbor nodes to decide whether forwarding the route request. Those nodes who didnt forward the requests take gossip (Gossip) mechanism to cache the request and wait for a reasonable time, which is to determine forwarding the RREQ or not depending on

12、the number of the same RREQ the node received from its neighbor nodes in the waiting time. In order to confirm the performance of this broadcast limited algorithm, we apply it to the routing request process of AODV routing protocol and the form the LA-AODV-Gossip (Location-Aided) routing protocol. I

13、n order to make the algorithm adapt to some specific area or a particular occasion, this paper also proposes a new protocol using the ARIMA model to predict the location information of next time, which is called the LP-AODV-Gossip (Location-Prediction) to improve routing efficiency and enhance the l

14、ink stability.In the NS2 platform, compare the performance of traditional AODV routing protocols, LA-AODV-Gossip routing protocol and LP-AODV-Gossip routing protocol with the changing the number of nodes and nodes max speed. The simulation results show that the LA-AODV-Gossip routing protocol perfor

15、ms better than traditional AODV in the routing overhead, the routing life and the delivery rate. And some special network occasion, the predicted LP-AODV-Gossip protocol can further reduce the broadcast redundancy and the routing discovery delay, also ensure the reliability of data transmission.Keyw

16、ords：Ad Hoc network; Routing protocol; GPS; ARIMA; Location prediction; NS2东北大学硕士学位论文目 录目 录独创性声明I摘 要IIAbstractIII目 录V第 1 章 绪论11.1 Ad Hoc网络概述11.2 课题来源及相关技术发展现状21.3 论文主要工作及创新41.4 论文主要组成结构4第 2 章 Ad Hoc网络路由协议分析62.1 Ad Hoc网络路由协议特点62.2 Ad Hoc网络路由协议的分类72.2.1 基于拓扑的路由协议72.2.2 基于位置的路由协议92.3 Ad hoc网络广播风暴问题112.

17、3.1 冗余112.3.2 竞争122.3.3 碰撞122.4 洪泛机制的几种优化方法122.4.1 基于概率的方法(Probabilistic Based Methods)132.4.2 基于面积的方法(Area Based Methods)132.4.3 基于邻居信息的方法(Neighbor knowledge Methods)142.4.4 几种算法比较15第 3 章 基于地理位置的LA-AODV-Gossip路由协议的设计163.1 Ad hoc网络路由协议评价标准163.2 LA-AODV-Gossip路由协议设计思想173.2.1 AODV协议分析173.2.2 流言（Gossip

18、）机制分析233.2.3 位置辅助路由协议LAR分析243.2.4 LA-AODV-Gossip算法描述293.3 LA-AODV-Gossip算法实现313.3.1 广播包格式313.3.2 路由请求处理过程323.4 LA-AODV-Gossip协议仿真333.4.1 仿真平台简介343.4.2 仿真模型建立353.5 仿真结果分析373.5.1 仿真环境及参数设置373.5.2 性能度量标准373.5.3 仿真性能分析38第 4 章 地理位置信息预测模型的建立444.1 ARIMA模型介绍444.2 ARIMA 模型建立过程464.2.1 预处理474.2.2 模式识别474.2.3 模

19、型的参数估计504.2.4 模型预测分析514.3 下一时刻地理位置的预测524.3.1 应用ARIMA模型预测地理位置的具体思路524.3.2 地理位置的预测过程及结果分析53第 5 章 基于地理位置预测的LP-AODV-Gossip路由协议设计565.1 LP-AODV-Gossip协议设计目的及思想565.2 下一时刻地理位置的获取585.3 LP-AODV-Gossip路由协议的实现595.3.1 广播包格式605.3.2 路由请求处理过程615.4 仿真及性能分析625.4.1 仿真环境设置625.4.2 仿真性能分析62第 6 章 结束语696.1 本文工作总结696.2 未来工作

20、展望70参考文献71致 谢76东北大学硕士学位论文第 1 章 绪论第 1 章 绪论本章主要介绍了课题来源及相关技术发展现状，课题提出的背景和意义，还有论文的主要工作和创新以及论文的组成结构。1.1 Ad Hoc网络概述当今的通信界，无线通信与无线网络技术发展迅猛，各种无线通信设备得到了飞速地普及，其更新速度也在不断变快。无线通信的快速发展不断地影响着人们的生产、生活方式，越来越多的用户习惯并且依赖于无线通信与无线网络技术所提供的便利。但通常，人们提及和使用的无线通信网络一般都是指基于基础设施的、有中心的无线网络，如以蜂窝网为代表的星形网络。这类网络一般在有线骨干网络模式下工作，因此其无线通信仅

21、存在于移动节点和相应的基站（Base Station，BS）或接入点（Acess Point，AP）之间，而端到端的数据业务大多还是在于有线骨干网进行传输，这就要求有一个预先建立的通信骨干网。但是在某些特殊场合下，使用有中心的移动网络是不可行的，如战场上部队的快速展开与推进，水灾、火灾、地震等灾难后的迅速营救，以及在边远地区的搜索和救援行动等。在这种情况下，一种能够快速、临时自动组网的移动通信技术已成为大势所趋，因此Ad Hoc技术便应运而生。“Ad Hoc”的原始意思是“仅为此目的、特定的”。1972 年，为了满足战争领域的需要，美国的（DARPA2，Defense Advanced Res

22、earch Project Agency) 开始了分组无线网项目（PRNET3，Packet Radio Network)的研究，这个项目主要课题是战争环境中分组无线网络的数据通信问题。十一年后，它开始研究抗毁可适应性网络（SURAN4，Survivable Adaptive Network)，九年之后，“Ad Hoc 网络”一词诞生。又过了三年，同样是 DARPA 又开始了全球移动信息系统GloMo(Globle Mobile Information Systems)）的研究。之后，越来越多的专家学者意识到 Ad Hoc 具有非常广泛的应用而在此方面做了大量并且深入的研究，使我们拥有了非常宝

23、贵的研究成果。在Ad Hoc网络中，网络中的所有节点地位平等，无需设置任何的中心节点。网络中所有的节点不仅具有普通移动终端所拥有的功能，并且具有路由器的功能，能够发现和维护自身到其他节点之间的路由，并向其邻居节点发送或转发数据分组。节点在网络中可以随意地移动，若相互之间不在通信范围之内时，可以借助其他的中间节点的中继来实现多跳通信。因此，Ad Hoc网络通常是一种多跳网络5。由于 Ad hoc 网络的特殊特点，使得它在某些特定的领域有着广泛的应用。这些特殊的领域6包括军事通信、传感器网络7、灾后重建、临时会议等等，这些领域一般不能或者来不及铺设固定的基础设施，所以 Ad hoc 网络在这些领域

24、有着较强的优势。1.2 课题来源及相关技术发展现状Ad Hoc 网络本身具有特殊的拓扑结构，所以其路由问题就十分重要，路由协议的好坏直接影响到整个网络性能的优劣。Ad Hoc网络的路由协议已经成为无线通信的研究热点之一，对路由协议的讨论也越来越深入。良好的路由协议是建立Ad Hoc网络的首要问题，同时也是主要的研究热点和难点。传统的距离向量和链路状态路由协议并不适用于拓扑结构高度动态变化的Ad Hoc网络。理想的Ad Hoc网络的路由协议应该具有以下性能：分布式运行、无环路、按需运行、考虑安全性、高效地利用电池能量、支持单向链路、维护多条路由。Ad Hoc网络路由协议主要包括路由发现 (Pat

25、h Discovery)、路由维护 (Path Maintenance)两项核心功能。其中，路由发现是指网络节点根据节点间连接关系、链路特性等网络状态信息和用户业务需求生成路径，并选择最适当的路径传输数据；路由维护是指网络节点对所选择的路径进行维护。在传统的Ad Hoc网络路由发现过程中，通常采用洪泛路由请求消息的方式寻找到目的节点的路由，洪泛使分组像辐射波一样从源节点以波浪形式向外传播，每个中间节点收到路由请求包后都会盲目的转发。采用洪泛方式传递分组，具有很大的盲目性，并且消耗大量的带宽，这样的结果往往会造成较大的不必要的开销。而在路由维护过程中，由于移动 Ad hoc 网络的快速移动性，网

26、络拓扑的快速变化，频繁的链路断开使得频繁的路由失效和路由重建。因此在设计路由时，减少路由发现和路由维护时的控制开销是关键问题。对于路由控制开销问题，目前国内外主要从以下两个大的方面着手进行研究：（1）减少路由重建的次数。从这个角度入手，主要的方法有稳定性路由、多径路由、负载均衡路由和基于历史信息的路由8。稳定性路由是选择一条路径生存期较长的路由，这样可以避免频繁的路由重建；多径路由可以建立到达目的节点的多条路径，提供一定的容错机制，能够对出错的路由快速做出响应并完成路由修复；负载均衡路由将网络流量分发到多条路径上，减少拥塞和热点带来的路由失效；基于历史信息的路由可以根据已经建立的路由信息，采取

27、局部修复策略，避免从源节点开始的整条路由的重建。（2）减少路由发现的开销。在高度移动性的网络中，由于节点的移动性，路由断开是不可避免，即使稳定性路由也无法保证路由不中断，多径路由也难以保证每条路由的有效性，负载均衡路由对于解决网络中的拥塞问题很有效，但是对于节点的移动性几乎没有效果，而拓扑的动态变化使得先验信息往往不可靠。因此，对于高度动态的网络，花费开销去减少路由重建的次数，往往仍然不能避免路由失效而进行路由重建，那么减少路由重建时的开销，使新的路由发现的开销足够小，就是一件很有意义的工作。在路由发现中，广播是一种基础而有效的数据扩散方法。在路由请求包（Route Request，RREQ）

28、到达目的节点以前，中间节点会盲目的转发收到的路由请求包，大量的重复广播会带来“广播风暴”问题。目前已有的减少路由发现中控制分组的方法有：对广播机制的优化、限制路由请求包的传播范围、基于 MCDS 的虚拟骨干策略、分簇机制等。综上所述，国内外学者为了优化路由请求包的洪泛广播过程，提出了很多新的思想。Williams将广播过程分为四个种类9：简单洪泛、基于概率机制、基于区域机制和基于邻居节点信息。因此在最近的研究成果中，多采用节点邻居信息、网络拓扑信息、节点移动性信息对广播或路由发现做优化，在降低路由控制开销的情况下，提高路由性能。所以本文主要围绕路由发现过程的洪泛方式进行优化，取上述几种优化洪泛

29、算法的优势，以传统的AODV算法为基础，综合基于概率Gossip机制中中间节点将请求包缓存等待的机制，借鉴基于地理位置信息路由协议中利用GPS定位功能，获取节点位置信息，划分路由请求区域，以每一个节点相对于其邻居节点的地理位置信息替换Gossip机制中的概率参量，缩小路由请求的传播范围，对洪泛节点进行限制，达到节约网络资源、提高网络路由效率的目的，为了能够更好地适应不同的网络环境，又提出了引入预测机制来进一步减少洪泛节点，并且提高所选链路的稳定度。1.3 论文主要工作及创新本课题主要研究优化传统按需路由协议中洪泛路由请求来寻找路由的方法。为了达到洪泛受限的目的，参考Gossip机制中节点接收到

30、请求包后的缓存等待功能，并借鉴LAR协议中划分请求域的思想，利用GPS获得节点自身的地理位置，通过计算与其邻居节点的相对位置关系这一确定值来替代Gossip机制中概率这一模糊值，来判断是否转发请求包，从而限制转发的节点数目。为了实现上述算法，将其应用于传统路由协议AODV中。并且为了使这种算法能够适应不同的网络密度和节点移动速度的网络，引入基于地理位置的预测机制，有效地改善网络节点分布不均和运动速度过快等不良的网络状况，提前淘汰掉不稳定的节点，确保所选链路的稳定性。本文的主要工作如下：(1) 研究Ad Hoc网络路由协议；(2) 研究LAR协议中划分请求域的方法；(3) 研究优化洪泛过程的流言

31、（Gossip）机制；(4) 研究ARIMA预测模型在运动轨迹预测方面的应用；(5) 应用ARIMA预测模型预测运动轨迹优化LA-AODV-Gossip路由协议，形成新的LP-AODV-Gossip路由协议(6) 在NS2上模拟仿真。本文主要创新如下：(1) 提出一种新的基于地理位置信息的洪泛受限的路由协议；(2) 利用ARIMA预测模型对新的协议进行优化；(3) 在NS2上实现改进后的路由协议，并进行仿真分析。1.4 论文主要组成结构本文所做的主要工作如下：第一章，介绍课题来源于背景。第二章，介绍Ad Hoc网络典型的路由协议和洪泛机制的问题及改进方式。第三章，介绍LA-AODV-Gossi

32、p路由协议的设计思想与在NS2中实现的具体过程，并进行仿真分析。第四章，介绍ARIMA预测模型与ARIMA预测模型在运动轨迹预测上的应用方法。第五章，描述基于地理位置预测的LP-AODV-Gossip协议的设计思想与在NS2中实现的具体过程，并进行仿真分析。第六章，对本文进行了一个全面的总结，并指出未来的工作方向。- 76 -东北大学硕士学位论文第 2 章Ad Hoc网络路由协议分析第 2 章 Ad Hoc网络路由协议分析2.1 Ad Hoc网络路由协议特点Ad Hoc网络中为了实现端到端通信，需要有路由协议的相应支持。传统的路由协议如RIP(选路信息协议)和OSPF(开放最短路径优先协议)是

33、为有线固定网络而设计的，它们的拓扑结构是固定的，不会出现大的网络结构变化，因此不需要考虑路由器的移动性，路由的更改主要是由于网络流量的变化，或发生网络拥塞的缘故，而Ad Hoc网络的节点是移动的，路由信息随时可能改变，所以必须对路由协议进行改进。美军曾经在Ad Hoc网络中采用OSPF路由协议与工CMP数据包结合的方式进行通信，但是效果并不理想，主要原因是数据包的丢失率较高。但由于Ad Hoc网络是由移动节点动态的构成，为实现端到端的通信，就不能直接采用已存在的有线网络中的路由算法，必须考虑诸如网络节点的移动性管理，冗余路由信息的处理，网络带宽和电源能量的节约问题。因此需要提出新的路由协议。A

34、d Hoc网络的路由协议应具有以下几个特点：(1) 分布式由于Ad Hoc网络的特殊性，其路由协议毫无疑问应该是分布式的，不依赖于任何基础设施的。(2) 提供无环路路由为了保证整体的性能，路由协议必须是无环的，以避免带宽和能量等资源的无谓消耗。(3) 迅速收敛Ad Hoc网络拓扑是动态的，这就要求路由协议必须对拓扑的变化具有快速反应能力，在计算路由时能够迅速收敛，及时获得有效的路由，避免出现目的节点不可到达的情况。(4) 避免无穷计算10经典的算法在某些链路失效时，有可能出现无穷计算的情况。而在Ad Hoc网络中，链路失效是经常发生的，这就要求在Ad Hoc网络中运行的路由协议必须能够避免无穷

35、计算，不使用会出现无穷计算的算法。(5) 支持单向信道在 Ad Hoc网络中，可能出现单向信道。因此要求路由协议支持单向信道。2.2 Ad Hoc网络路由协议的分类移动 Ad hoc 网络的路由协议有多种不同的分类方式。根据路由协议在执行过程中是否需要物理位置信息，路由协议可以分为基于拓扑的路由协议和基于位置的路由协议。基于拓扑的路由协议按照路由建立方式的不同，又可以分为表驱动（table-driven）路由协议、按需路由（on-demand）协议和混合（hybrid）路由协议11 12。不同的协议有不同的特点，其路由控制开销也有所不同。路由控制开销是衡量移动 Ad hoc 网络路由协议性能的

36、主要指标，可以表现为网络拓扑变化率的函数13。在设计路由协议时，不仅要满足分组传输的各种性能要求，如分组投递率和端到端的延迟等，还要使路由控制开销足够的小。下面针对不同类型的路由协议，对其控制开销分别加以介绍。2.2.1 基于拓扑的路由协议1.表驱动（table-driven）路由协议表驱动路由协议又称先应式路由协议，这种协议中，每个节点无论是否需要发送数据，都要建立和维护路由表，路由表中包含到达网络中所有节点的路由信息。当节点检测到网络拓扑发生变化时，在网络中发送更新消息，收到更新消息的节点更新自己的路由表。典型的表驱动路由协议有：目的序列距离矢量路由（Destination-Sequenc

37、ed Distance-Vector Routing，DSDV）14、最优链路状态路由（Optimized Link State Routing Protocol，OLSR）15等。表驱动路由的优点是，当节点一旦要发送数据，节点能够再比较短时间内对接收到的数据请求做出反应，并建立正确路由路径。但是明显的不足之处在于，在一个拓扑总是不断变化的网络中，节点需要发送非常大量的控制报文，来对路由表进行维护，维护一个及时的更新的路由表将带来较大路由控制开销，因而需要消耗比较多的资源16，而限制表驱动路由协议的表现。尤其对于采用电池供电，能量、带宽等资源都十分有限的移动 Ad hoc 网络，为了维护根本就

38、用不到的路由是没有必要的。对于 DSDV 协议，无论网络负载如何以及是否有节点需要发送数据，DSDV 都要求节点定期地广播更新信息，这将使资源消耗增加，尤其是节点移动率较高的情况下，DSDV 协议的性能将急剧恶化。OLSR 采用了多点中继技术，减少了控制消息的洪泛范围，这样显著地减少了网络中的路由控制分组。但是多点中继集的计算及维护都需要额外的开销，对于高度动态的网络，计算出的多点中继集往往很快会失效。文献17从信息论的角度建立了一个通用的方法，对先验式路由协议的控制开销做了分析，并分析了先验式路由对内存需求和消息开销的下界。文献13为定量的分析先验式路由的控制开销，建立了一个数学框架，将路由

39、控制开销表示为拓扑稳定性的函数。综上而言，表驱动路由在移动性高的网络中性能较差。2.按需（on-demand）路由协议按需路由协议节点平时不需要对网络的拓扑结构进行维护，只有在需要发送数据时，才会开始对相应的目的节点查找路由，因此按需路由会节约非常大的网络开销，尤其是在当前网络并没有非常大的负荷时，所能节约的网络开销更加可观。但是再节点需要查找路由时，由于没有表路由的实时维护，会产生一定的时延，所以按需路由协议并不适合于对延时非常敏感的应用。典型的按需路由协议有：动态源路由协议DSR（Dynamic Source Routing）18、按需距离矢量路由AODV（Ad hoc On-Demand

40、 Distance Vector Routing）19等。按需路由协议包括“路由发现”和“路由维护”两部分，因而其路由控制开销包括路由发现的开销和路由维护的开销。DSR 协议还包括数据分组头部的源路由分组头带来的开销，当网络规模较大，路由的跳数较多而数据分组较小时，源路由开销的问题就更突出。但是 DSR 协议采用了路由缓存技术，并支持到目的节点的多条路由，因而一定程度上能减少控制开销。AODV 协议结合了 DSDV 协议和 DSR 协议的优点，并采用了“扩展环搜索”技术，可以减小路由请求包的传播范围，有较好的扩展性，但是“扩展环搜索”技术也使得路由建立的延迟比较大。DSR 和 AODV 协议的

41、路由维护阶段，都有各自的路由修复技术，也在一定程度上减少了路由控制开销。路由协议开销与协议自身以及应用场景有关，一般来说路由发现的开销更大一些。文献20为定量化研究反应式路由的控制开销，提出了一个新的数学框架，文中分别给出了在节点随机分布的网络中，路由请求包和路由回复包个数的期望值。文献21研究发现，对于 AODV协议，路由发现时的控制开销占了整个路由控制开销的90%。3.混合式（hybrid）路由协议当Ad hoc无线网络中单纯采用先验式或反应式路由协议都不能完全解决路由问题，因此，许多学者提出了结合先验式和反应式路由协议优点的混合式路由协议，如ZRP协议22。ZRP协议是一个分区路由协议，

42、将整个网络分成若干个以节点为中心、一定的跳数为半径的虚拟区。与一般的分级路由协议不同，区内的节点数与设定的区半径有关，因此ZRP的区重叠程度很高，许多节点可能同时属于多个区域，每个区域的半径长度由用户设定。虽然混合式路由协议虽然是一个非常好的创意，但是，实施混合路由也面临着很多困难，如族的选择和维护、先验式和反应式路由协议的合理选择以及网络工作的大流量等问题，所以目前技术限制它并不实用。由于表驱动型路由协议的最大优点是随时可以知道到目的节点的路由，而且路由信息经过处理，进行了优化。缺点是不考虑是否存在路由的变化和转发需求，都要定期更新路由表信息，会造成电池电量和网络带宽的浪费，这一点在通信量大

43、的时候特别明显。按需驱动型路由协议固有的缺陷是协议的实时性较差，而且也不能保证是最佳路由。但由于按需驱动型路由协议节省电源和带宽，非常适用于无线移动网络，因此目前成为研究Ad Hoc网络路由协议的主流。综上，表驱动型路由协议不考虑是否存在路由的变化和转发需求，都要定期更新路由表信息，会造成电池电量和网络带宽的浪费，这一点在通信量大的时候特别明显。而按需驱动型路由协议固然实时性较差，但由于按需驱动型路由协议节省电源和带宽，非常适用于无线移动网络，因此目前成为研究Ad Hoc网络路由协议的主流。但是对于按需路由协议，如 DSR 和 AODV，在进行路由发现时多采用 Flooding 机制。尽管 F

44、looding 是一种有效的数据扩展机制，但在网络拓扑频繁变化的时候，仍然会产生大量的控制流量，因而带来了大量的路由控制开销12。因此减少路由发现时的控制流量是降低控制开销的一个很好的选择，这也是本课题的研究重点。2.2.2 基于位置的路由协议1.位置信息辅助的路由协议这类协议在地理位置的辅助下，限制路由控制分组的发送范围，可以显著地减少控制分组的数量，这是对路由发现中 Flooding 的优化。此类路由的典型代表是位置辅助路由LAR（Location-Aided Routing）23。LAR 协议中，若源节点知道目的节点在t0时刻的位置及平均移动速度，就可以估算出目的节点在t1时刻的可能出现

45、的区域，该区域成为“期望域”（Expected Zone）。为了找到目的节点，源节点在一定范围内发送路由请求包，因此这属于范围受限的洪泛机制，这个范围称为“请求域”（Request Zone）。LAR 协议通过限制路由搜索范围，显著地减少了路由控制开销。LAR 很重要的一点是提出了一种利用地理位置限制路由搜索范围的思想。这种思想可以有多种不同的实现方法，甚至在没有地理位置的情况下，也有多种技术可以模拟这种思想，达到限制 Flooding 的目的。2.完全基于位置信息的路由协议这类协议在发送数据时直接根据地理位置信息转发数据分组。节点在转发数据分组时的策略主要有：贪婪转发和定向泛洪。贪婪转发（G

46、reedy Forwarding）是指中间节点根据某一个度量标准贪婪地选择下一跳节点。根据具体的度量标准的不同，主要有以下方式24：1）半径内最大转发（Most Forward within Radius，MFR），总是选择距离目的节点最近的邻居节点转发；2）最近转发前进（Nearest with Forward Progress，NFP），总是选择离自己最近的邻居节点；3）罗盘路由（Compass Routing，CF），总是选择与当前节点、目的节点构成的夹角最小的邻居节点。这三种方法都属于启发式的策略，都在多数情况下能较好的找到目的节点，但是仍然存在某种情况，即源节点和目的节点的路由存在，

47、但是采用这些贪婪地算法却不能找到到达目的节点的路由。这就是贪婪算法存在的“死端”（dead-end）问题，也就是一种“局部最优化”问题。针对局部最优化问题，提出了多种解决方案，如贪婪边界无状态路由（Greedy Perimeter Stateless Routing，GPSR）25，采用边界转发；地理距离路由（Geographical Distance Routing，GEDIR）26，丢弃数据分组；地理路由算法（Geographical Routing Algorithm，GRA）27，启动基于洪泛的路由发现机制。定向洪泛（Directed Flooding）是指节点向目的节点方向的所有邻居节点转发数据分组。典型的代表是“针对移动性的距离路由效应算法”（Distance Routing EffectAlgorithm for Mobility，DREAM）28。在这个算法中，源节点以及中间节点各自计算