（46页19043字+图+程序）摘要：移动Ad hoc网络是一种不需要基础设施的无线自组织网络，它适用于抢险救灾等无基础设施的临时通信场合。目前对移动Ad hoc网络研究最多的是路由协议。OLSR路由协议是其中的一种表驱动路由协议。本文根据OLSR路由协议的规范，提出和实现了相应的原理性算法。剖析了OLSR路由协议算法的原理：链路侦听、邻居探测、多点中继MPR的选择、拓扑控制分组的扩散、计算路由表。根据OLSR路由协议规范，结合Linux操作系统平台，实现了OLSR关键算法的设计方案。编译了适合实验设备的Linux内核，组建了一个基于OLSR路由协议的自组织网络。实验结果的分析证明了设计的OLSR路由协议达到了传输过程中传送数据速度快、占用传输带宽小且在节点移动后仍可迅速建立新路由的要求，保证了数据传输的质量。
关键词：移动Ad hoc网络；OLSR路由协议；Linux；路由
OLSR Routing Protocol algorithm Design in Ad hoc Networks
Abstract： Mobile Ad hoc network is a wireless multi-hop network without pre-established infrastructure. It can be used for temporary communication in emergency environments. The main research in the mobile ad hoc network is routing protocol, in which OLSR (Optimum link State Routing Protocol) is a standardized table-driven routing protocol. According to the OLSR routing protocol specification, this paper proposes and realizes the corresponding implementation of principle algorithm and analyses the OLSR routing protocol algorithm core principles such as detection of link, detection of neighbors, choice of MPR, extend of topology control, routing table calculation. According to the OLSR routing protocol specification, the OLSR routing protocol algorithm is achieved on Linux operating system platforms. After compiling the Linux kernel for experimental equipment, a routing protocol based on OLSR is formed. The experimental results showed that the OLSR routing protocol designed in this paper, has satisfied the requirement that fast transmission, low occupation on bandwidth and fast establishment new routing after node moving. And the transmission quality has been assured also.
Key words： Mobile Ad hoc wireless network, Optimized Link State Routing, Linux, Route
目 录
第1章 绪 论 1
1.1 设计目的与意义 1
1.2 研究内容及重要问题 1
第2章 OLSR路由协议算法介绍 3
2.1 OLSR路由协议中的表结构 5
2.2 OLSR路由协议分组格式 7
2.3 OLSR路由协议算法基本操作 9
第3章 OLSR路由协议算法设计 11
3.1 OLSR路由协议算法流程 11
3.2 OLSR路由协议的关键算法 11
3.2.1 链路侦听 11
3.2.2 邻居探测 15
3.2.3 多点中继站MPR的选择 18
3.2.4 拓扑控制分组的扩散 20
3.2.5 计算路由表 22
3.2.6 有效时间的计算方法 24
第4章 OLSR路由协议算法实验研究 26
4.1 Linux实验平台的介绍 26
4.2 Linux内核编译 26
4.3 实验硬件与软件 28
4.4 实验一 30
4.4.1 实验描述 30
4.4.2 实验结果及分析 30
4.5 实验二 31
4.5.1 实验描述 31
4.5.2 实验结果分析 32
4.6 实验三 33
4.6.1 实验描述 33
4.6.2 实验结果分析 33
4.7 OLSR路由协议占用带宽比较 33
4.7.1 实验一 33
4.7.2 实验二 34
4.7.3 实验三 34
4.7.4 小结 34
结论 36
致谢 37
参考文献 38
附录 40
第1章 绪 论
1.1 设计目的与意义
移动网络的概念出现于20世纪70年代，近年来由于便携式设备在移动性、储存能力和无线通信能力等方面的迅速发展，使得移动网络得到了广泛应用。无线Ad hoc网可以在不能利用或不便利用固定网络基础设施的情况下提供一种移动通信环境。
无线移动Ad Hoc网是以分组无线网技术为基础的互联的无线电台、计算机硬件和软件的集合。无线移动Ad Hoc网可以广泛地应用于警察与医疗部门的抢险救灾、传感器网络、课堂教育等众多领域。
无线移动Ad Hoc网由移动的无线路由器组成，不需要提供固定的骨干设施，没有中心节点，组网更加快速、有效,无线移动Ad Hoc网具有高度变化的拓扑结构，各节点可以任意移动，节点之间利用无线技术传送数据包，由于无线传输范围的限制，网络中任意两个节点之间可能不存在直接的通信链路，因此分组需要中间节点的中转才能实现通信，这使得网络中各节点在功能上有别于常规网络的节点，即在Ad Hoc网中节点需要同时扮演主机和路由器双重角色，因此，对路由协议的研究在Ad Hoc网络系统中显得格外重要，满足无线移动Ad Hoc网要求的路由协议的目标是快速、准确、高效、可扩展性好[1]。
1.2 研究内容及重要问题
在无线Ad hoc网络中，传输质量是人们广泛关注的问题，这就引起了人们对新的路由技术的研究。现有的无线移动Ad Hoc网路由协议大致可以分为先应式(proactive)和反应式(reactive)两种[2]。
先应式路由协议又被称为表驱动路由协议(Table-driven Routing Protocol)，是基于路由表的路由协议。先应式路由协议的路由发现策略与传统路由协议类似，节点通过周期性的广播路由信息分组，交换路由信息，主动发现路由。网络中节点必须维护到达全网所有节点的路由, 每个节点维护一张或多张表格，这些表格包含到达网络中所有节点的路由信息。先应式路由的优点是，当节点需要发送数据分组时，只要去往目的节点的路由存在，所需的延时就很小。缺点是先应式路由需要花费较大的开销，尽可能使得路由更新能够紧随当前网络拓扑结构的变化。然而，快速动态变化的拓扑结构可能使得这些路由更新变成过时信息，导致路由协议始终处于不收敛状态。典型的先应式无线移动路由协议有：OLSR、DSDV、WRP、STARA。
反应式路由协议，又称为按需路由协议(On-demand Routing Protocol)，是当节点需要发送报文分组时才查找路由的路由选择方式。节点并不保存及时准确的路由信息。当源节点要向目的节点发送报文时，源节点通过在网络中发起路由查找过程，找到相应的路由后，才开始发送报文，为了提高效率，节点可以将找到的路由保存在缓存中供后续发送使用。因此，拓扑结构和路由表内容是按需建立的，它可能仅仅是整个网络拓扑结构信息的一部分。它的优点是不需要周期性的路由信息广播，节省了一定的网络资源。缺点是发送数据分组时，如果没有去往目的节点的路由，数据分组需要等待因路由发现而引起的延时。典型的反应式无线移动路由协议有：AODV、DSR、TORA。
在众多的表驱动路由协议中，OLSR和WRP(Wireless Routing Protocol)是比较具有代表性的。OLSR协议可以通过缩短周期性发送控制信息的最大间隔时间来优化对拓扑变化的反应。OLSR协议特别适用于规模大，节点密度高的网络，由于采用了MPR，对比经典的链路状态算法，网络规模越大，节点密度越高，MPR的优化效果越好。
在技术方面，OLSR要解决的问题是当节点数量较多，移动速度，移动方向随机的情况下，对OLSR的路由表的维护速度，以及如何发送控制信息来降低网络开销，防止网络中洪泛的发生。
| 