1、 工程硕士学位论文基于位置预测的 Ad hoc 网络路由协议研究学位申请人姓名 培 养 单 位 计算机与通信学院导师姓名及职称 学 科 专 业 计算机科学与技术 研 究 方 向 无线 Ad hoc 网络的路由协议论 文 提 交 日 期 工程硕士学位论文学位论文原创性摘 要Ad Hoc 网络是一个复杂的分布式系统，具有动态变化的拓扑结构。Ad Hoc 网络没有任何中心和固定基础设施，每个节点都具有主机与路由器的双重功能，形成一个多跳分布式网络。如何找到快速稳定的路由是 Ad Hoc 网络研究的关键问题，目前 Ad Hoc 路由协议基于不同的出发点和机制，尚无比较完善的性能都比较优越的 Ad Ho
2、c 路由协议，特别是具有 QoS 保障的路由技术，仍处于探索阶段，尚无成熟的协议标准，还有待于进一步的深入研究。本文首先介绍了 Ad Hoc 网络的基本概念，对 Ad Hoc 网络的路由协议进行了详细的分析研究。通过 OMNeT+仿真，比较分析了几种常见路由协议在不同环境下的性能变化，包括：移动性、网络负载和网络环境等。仿真结果表明，随网络负载的增加数据分组成功发送率下降、路由包开销增大、端到端传输时延增长。仿真分析表明，目前路由算法存路由包开销大、端到端传输时延长等问题。因此，本文提出了一种基于位置预测的 LAODV 路由协议 (Ad hoc On Demand Distance Vecto
3、r routing Based On The position prediction ) 。设计了节点定位的自适应定位算法，在网络定位系统中配置一些位置己知的信标节点，一旦信标节点不够，低级节点自动吸纳高级节点作为补充“信标”节点参与该节点的定位。在得到基本位置信息后，通过对节点的位置进行预测，确定节点的位置和基本方向，选择最稳定路径进行数据传输，降低了路由破裂与重构次数，提高了数据成功传送率。仿真结果表明，通过对节点的位置进行预测，采用定向洪泛的路由算法和资源预留机制为数据的传输提供了可靠的QoS 保障，降低了路由开销。关键字:Ad Hoc 网络；地理位置路由；定位；OMNeT+基于位置预测
4、的 Ad hoc 网络路由协议研究AbstractAd Hoc network is a complicated distribute system, which has dynamic topology. There is no infrastructure in Ad Hoc network, while every node can be router and host, then form a multi-hop distributed network.How to rapidly find a stable route is the key problemin Ad Hoc netw
5、ork. There is no excellent performance Ad Hoc routing now, especially for QoS routing, which still in the initial stage and there is no industry standard. So it need do further research in Ad Hoc routing. First some basic concept of Ad Hoc network was introduced, then analysed Ad Hoc routing protoco
6、ls. We analyzed and compared the performance of several Ad Hoc routing protocols in different network environment via OMNeT+, such as mobility, network load and environment. The simulation shows along with network load ,send out rate decline, the cost of routing increase and the delay of end to end
7、extend. Network simulation shows these routing protocols have some weakless such as big cost and long delay. So an LAODV (Ad hoc On Demand Distance Vector routing Based On the position prediction) is proposed. We designed an adaptive localization algorithm for locating node. Set some beacon node tha
8、t known there location, once there is no enough beacon node in the network, the senior node will be alternated node for beacon and join the localization stage. When get there location, via the prediction of the new position to confirm the position and direction of the node, then choose the best rout
9、e to transmit. It will decrease the numbers of break route and re-route, and increase the data transmition rate. The simulation shows, through the prediction of position, using the directional flooding and resourse reserve to ensure the QoS, the cost of routing is decreased.Key words: Ad Hoc Network
10、; Routing base Geography; Localization; OMNeT+工程硕士学位论文目 录摘 要 .IIAbstract.III插图索引 .VI附表索引 .VII第 1 章 绪 论.11.1 课题的研究背景及意义.11.1.1 移动 Ad hoc 网络概述 .11.1.2 Ad Hoc 网络中路由协议问题 .21.1.3 论文研究的意义.31.2 Ad Hoc 网络路由协议的研究现状 .41.3 研究内容.51.4 论文结构.51.5 本章小结.5第 2 章 Ad Hoc 网络路由协议 .62.1 Ad Hoc 路由协议概述 .62.2 Ad Hoc 路由协议分类性能研
11、究 .62.2.1 按路由建立时间分类.72.2.2 按路由算法类型分类.92.2.3 按网络拓扑结构分类.102.2.4 按路由协议的功能分类.112.3 几种常见的典型的路由协议.122.3.1 表驱动路由协议.122.3.2 按需驱动路由协议.142.3.3 混合路由协议.152.3.4 实现机制比较.162.4 本章小结.17第 3 章 Ad Hoc 路由协议的 OMNeT+仿真与性能分析 .183.1 OMNeT+仿真的基本原理 .183.2 Ad Hoc 路由协议的 OMNeT+仿真 .203.2.1 Ad Hoc 路由协议的 OMNeT+仿真流程 .203.2.2 仿真参数设置与
12、性能评价.22基于位置预测的 Ad hoc 网络路由协议研究3.2.3 不同负载下 Ad Hoc 路由协议的 OMNeT+仿真 .233.3 本章小结.28第 4 章 基于位置预测的 LAODV 路由协议 .294.1 基于位置预测的 Ad Hoc 路由协议研究 .294.1.1 基于位置预测的 Ad Hoc 路由协议研究 .294.1.2 位置信息路由协议的分析与优化.304.2 节点定位算法.314.2.1 节点定位算法基本原理.314.2.2 节点定位算法误差模型及误差消除技术.324.2.3 自适应节点定位算法具体内容及定位过程.334.3 基于位置预测的路由协议 LAODV.364.
13、3.1 LAODV 路由协议描述 .364.3.2 算法描述与实现.394.3.3 LAODV 性能分析 .424.3.4 LAODV 仿真分析 .424.4 本章小结.46第 5 章 总结与展望.47参考文献.49致 谢.52工程硕士学位论文插图索引图 1.1 简单的移动 Ad hoc 网络示例 .2图 2.1 按需驱动路由的路由建立示意图.8图 2.2 分级结构路由算法示意图.10图 2.3 CGSR 路由协议的路由机制 .16图 3.1 OMNeT+仿真程序的体系结构 .19图 3.2 数据包成功发送率 1.24图 3.3 数据包成功发送率 2.25图 3.4 网络路由包开销 1.26图
14、 3.5 网络路由包开销 2.26图 3.6 端到端的平均时延 1.27图 3.7 端到端的平均时延 2.27图 4.1 圆周定位模型.32图 4-2 节点分类 .34图 4.3 定位流程.35图 4.4 位置管理方案.37图 4.5 最小路径生存时间的计算.37图 4.6 定向路由洪泛机制.38图 4.7 中间节点处理 RREQ 报文的过程 .40图 4.8 中间节点处理 RREP 报文的过程 .41图 4.9 数据包成功发送率 1.43图 4.10 数据包成功发送率 2.44图 4.11 网络路由包开销 1.44图 4.12 网络路由包开销 2.45图 4.13 端到端的平均时延 1.45
15、图 4.14 端到端的平均时延 2.46基于位置预测的 Ad hoc 网络路由协议研究附表索引表 2.1 路由协议性能比较（按路由建立时间分类）.8表 2.2 路由协议性能比较（按逻辑组织机构分类）.11表 2.3 典型 Ad hoc 路由协议实现机制比较 .17工程硕士学位论文- 1 -第 1 章 绪 论随着通信技术和计算机技术的不断发展，计算机网络正快速进入到商业、工业、教育和科研等领域，进入到人们的日常生活中，深深影响和改变着我们的生活和工作方式。移动通信网（如 GSM 和 CDMA 等）在我们周围广泛存在，它们需要有有线网络或存在固定基站，对于原来没有有线网络的区域或者有线网络已经被破
16、坏的区域，例如在荒芜人间的沙漠中，浩瀚无边的大海上，以及被火灾或其它灾难所毁坏的城市，战场等特殊场所，以前的移动通信网络就不能满足要求。在某些特殊情况下，需要快速、临时地建立一个新的移动通信网络，来实现信息的传输。为了满足这种需求，一种新的移动通信网（移动 ad hoc 网络）应运而生。移动 ad hoc 网络(MANET)是一个复杂的分布式系统，它由很多自由移动的无线节点，动态地自组织成一个任意网络拓扑结构系统。它使各设备之间不需要固定基础设施就可以进行相互通信，并且能很好地连接到 Internet 等网络。在战争和日常生活上美好的应用前景渐渐成为人们的研究中心之一，也使 ad hoc 网络
17、逐渐成为下一代网络的重要分支。1.1 课题的研究背景及意义1.1.1 移动 Ad hoc 网络概述Ad hoc1-5来源于拉丁语，是“专门地，特别地，随机地，随时地为即将发生的特定事件或情况”的意思。这里的 Ad hoc 网络是指一种特定的、多跳、自组织、无中心的无线网络。目前国内很多专家将 Ad hoc 网络称为“自组网” ，或者“多跳网络”等等。移动 ad hoc 网络是由许多动态节点（带有无线收发装置）自组织成一个临时性的多跳的无中心的分布式系统。在任意时刻，每个节点可以向不同方向以不同速度移动，在网络中每个节点可以完全自由的运动，因此无法预测网络的拓扑结构发生怎样变化。移动 ad ho
18、c 网络是一个多跳 (Multi-hop)的无线移动网络 6-9，当网络中两个移动节点在彼此的数据传输范围内时，可以直接进行无线通信；而当两个移动节点不在彼此的数据传输范围内时，两个移动节点必须经过其它中间移动节点转发进行无线通信。这里，我们描述了一个简单的由三个移动节点组成的 ad hoc 网络，如图 1-1。在该网络中，移动节点 A 和 C 都不在彼此的数据传输范围内，但是它们都在移动节点 B 的数据传输范围内，因此如果移动节点 A 要向移动节点 C 进行数据通信，必须通过移动节点 B 进行数据转发。这是移动 ad hoc 网络的一个基本特征多跳性，也是路由设计的一个难点。基于位置预测的
19、Ad hoc 网络路由协议研究- 2 -A B C图 1.1 简单的移动 Ad hoc 网络示例在 ad hoc 网络中，移动节点既作为主机，又具有路由器的功能。一方面，移动节点作为主机运行相关的协同应用程序；另一方面，移动节点作为路由器运行相关的路由协议，实现路由发现、路由维护等路由操作，如果接收到的数据不是给自己的数据分组即进行数据转发。1.1.2 Ad Hoc 网络中路由协议问题当前 Internet 网络中主要使用的路由协议 10 11是基于距离矢量的路由协议和基于链路状态的路由协议。这两类路由协议都是针对有线或固定网络而设计，由于 Ad Hoc网络的动态拓扑结构、数据转发的多跳性等特
20、点，使得实用于 Internet 网络的路由协议并不适合 Ad Hoc 网络。目前 Ad Hoc 路由协议基于不同的出发点和机制，尚无比较完善的性能都比较优越的路由协议。各种路由协议都存在或多或少的问题，主要表现在以下几个方面：（1）动态的网络拓扑结构Ad hoc 网络中，移动节点可以以任意速度和方向移动、电源用尽 /关机或损毁、同时节点发送功率的变化、无线信道之间相互干扰、地理环境等因素的影响，网络拓扑结构随时都会发生变化，若在 Ad hoc 网络中直接运行 Internet 网络的路由协议，一旦拓扑结构变化，Internet 网络的路由协议需要花费很长的时间和很大的代价才能完成收敛。（2）
21、有限的无线传输带宽、链路容量动态变化无线信道通信环境比较恶劣，信号的干扰、衰落、噪声等因素的影响以及信道的共享与竞争，使无线链路的状态随时间的变化而变化，另外，由于移动节点在网络中以任意的方式移动，Ad Hoc 网络的拓扑结构变化频繁，为了能够最快、最精确地反映网络拓扑结构的变化，因此，与固定网络相比，需要在节点间不断地交互控制报文。由于无线传输信道带宽有限，路由协议只有尽量减少节点间信息交互，才能减少路由协议开销，提高信道效率。（3）移动终端能力的有限性Ad hoc 网络中终端节点内存小、CPU 处理能力低、所带电源和发射功率十分有限。网络中节点既要作为主机又要作为路由器，节点能量一旦耗尽将会改变网络拓扑结构，
