基于地理位置预测的Ad Hoc网络洪泛控制路由协议研究

东北大学硕士学位论文 第 3 章 基于地理位置的LA-AODV-Gossip路由协议的设计

第 3 章 基于地理位置的LA-AODV-Gossip路由

协议的设计

为了判断一种路由协议的好坏，需要一些性能指标。这些指标要独立于任何该给定的路由协议。关于路由协议的评价标准，在RFC2501中有明确的说明，这给研究路由协议的人员提供了很好的参考。下面是Ad Hoc 网络中理想路由协议的特征[44]:

表3.1 理想路由特征

Table 3.1 The hypothetical routing performance

路由协议性能指标

分布式控制 由于Ad hoc网络无中心等特点，路由协议更适合采用分布式控制方式 支持单向性 在无线通信中，路由反向不可取，应支持单向性链路 无环路由 带宽效率 收敛迅速 能源节约 QoS保障 安全

尽可能防止路由环路的产生，并且能消除路由环路

减少控制消息，提高网络资源利用率，改善整个网络的传输性能 Ad hoc网络的特殊性要求节点能对特殊情况和突发事件尽快的反应，并能迅速收敛

路由协议应节能，并能分担负责，以避免能源耗尽导致路径失效 由于网络具有信息更新快，拓扑结构变化等原因，QoS应有所保障 由于无线网络会遇到干扰、窃听等安全问题，所以需要进行安全设计

3.1 Ad hoc网络路由协议评价标准

为了判断一种路由协议的好坏，需要一些性能指标。这些指标要独立于任何该给定的路由协议。关于路由协议的评价标准，在RFC2501中有明确的说明，这给研究路由协议的人员提供了很好的参考。Ad hoc路由协议的优劣主要考察以下几个方面的指标[45]：

（1） 端到端平均时延：源节点发送数据到目的节点的时间，包括路由发现、排队等待、数据发送和传播等。该参数反映网络是否畅通，延时越小网络越畅通。

- 16 -

东北大学硕士学位论文 第 3 章 基于地理位置的LA-AODV-Gossip路由协议的设计

（2） 路由协议的效率：即归一化路由开销，控制信息与用户数据信息的比例。 （3） 路由负载：每投递一个数据包分组到目的节点需要发送路由分组数。 （4） 路由失效数：衡量路由协议的健壮性。

（5） 吞吐量：单位时间内网络通过的数据分组数，单位为 kbits/s。

分组投递率：（6）统计投递到目的节点的分组与源节点产生业务流分组的比率，单位为%。

（7） 路径的获取时间：对于按需路由的算法而言，在需要的时侯路径的建立时间反映了它的一种端到端的外部效率，也就是使用该路由协议的外部实体所看到的协议的性能。不同路由协议在不同环境中，其性能好坏有很大差异。即使是同一个路由协议，在不同的网络环境中，其性能指标也有很大差异。在投入实际应用之前通过仿真测试出更适合网络环境的路由协议对实际工作具有指导意义。

3.2 LA-AODV-Gossip路由协议设计思想

本章提出一种简单而高效的Ad hoc广播算法，它利用中间节点的位置信息，节点收报数量反映出的节点密度等信息独立判断节点的转发状态。本文提出的广播算法可以广泛应用于Ad hoc网络的广播服务中,如主动路由协议中对链路状态变化信息的广播,被动路由协议的路由请求操作。本文中假定提出的算法应用于Ad hoc网络中传统的按需路由协议AODV协议的路由请求过程，取名为LA-AODV-Gossip（Location-Aided）路由协议。

3.2.1 AODV协议分析

1.AODV原理概述

AODV算法旨在多个移动节点中建立和维护一个动态的，自启动的，多跳路由的专属网络。AODV使得移动节点能快速获得通向新的目的节点的路由，并且节点仅需要维护通向它信号所及范围内的节点的路由，更远的节点的路由信息则不需要维护。网络中连接的断开和异动会使得网络拓扑结构发生变化，AODV使得移动节点能适时对这种变化做出响应。AODV的操作是无自环的，并且由于解决了Bellman-Ford“无穷计数”的问题，使得该算法在网络拓扑变化时能够快速收敛。当一个连接断开时，AODV会告知所有受到影响的节点，这些节点会让用到这个连接的路由失效。

- 17 -

东北大学硕士学位论文 第 3 章 基于地理位置的LA-AODV-Gossip路由协议的设计

在AODV路由协议的运行机制中，每个节点都会周期性的向外发送Hello报文，所有位于该节点通信范围内的节点都会收到该报文，从而在两节点之间建立领接关系，两节点则互为邻居节点。AODV 使用路由请求、路由应答来建立路由。当有数据包需要传送但没有可用路由时，源节点广播一个路由请求(RREQ)分组，所有在源节点通信范围内的节点(也就是源节点的所有邻居节点)，都会收到源节点发送的RREQ报文，如果收到该报文的邻居节点也没有到达目的节点的有效路由的话，便会转发该RREQ报文(丢弃重复的 RREQ)，依此类推，直到目的节点或具有能够到达目的节点的最新路由的中间节点为止。所以，AODV协议是以一种广播泛洪的方式来寻找到达指定目的节点的路由的。

AODV 的一个显著特点就是利用序列号编码来确保所有的链路没有环路，并保证中间节点只应答最新的信息，每个节点保存该 RREQ 报文源节点的 IP 地址、当前的序列号以及源节点所知道的目的节点最新的序列号。收到 RREQ 的中间节点或者是目的节点，或者是该节点具有到目的节点的路由，其相应的序列号应大于或等于 RREQ 所包含的序列号，因此，它将向源节点发送路由应答(RREP)。在RREP 沿反向路径返回时，沿着该路径的节点在它们的路由表中建立前向路由记录以指向 RREP 来源的节点。如果不存在这样的路由，或者源节点移动，路由表必须重新初始化；如果中间节点移动，其上游邻近节点将注意到这个移动，并将链路断裂的信息通告给直到源节点的上游节点。

AODV定义了三种消息种类：路由请求（RREQ），路由回复（RREP）和路由错误（RRER）。这些消息通过UDP和通常的IP协议来接收。举个例子，发起请求的节点需要用它自己的IP地址作为消息中的Originator IP address（发起者IP）。对于广播，将采用IP协议指定的广播地址（255.255.255.255），这个地址意味着这种消息将不会被盲目转发。但是，AODV操作确实要求特定的消息（例如RREQ）得到广泛的散布，甚至有可能散布至整个专有网络。这些RREQ的散布的范围由IP头中的TTL来指定。作为一个特点，将不会采用IP协议中的分片传输。

只要一条通道连接的两个端点都有通向对方的正确路由，AODV是不工作的。当某节点需要连接到一个新的目的节点时，它将广播一个RREQ（路由请求消息来尝试找到一条到目的节点的路由。如果RREQ消息到达目的节点，这条路由将被找到。另外一种情况下，路由也可以找到，就是RREQ到达了一个中间节点，该中间节点拥有到目的节点的“足够新鲜”的路由。“足够新鲜”的路由首先要是一条到目的地的正确

- 18 -

东北大学硕士学位论文 第 3 章 基于地理位置的LA-AODV-Gossip路由协议的设计

路由，该路由还需要拥有一个足够大的序列号，该序列号不得小于RREQ 中的序列号（A‘fresh enough’ route is a valid route entry for the destination whose associated sequence number is at least as great as that contained in the RREQ.）。当朝发起RREQ的节点单播一个RREP后，这条路由就建立了。所有接到请求的节点都会缓存一条回到发起节点的路由，所以RREP就可以通过单播从目的节点返回到发起节点，或者从一个能够找到目的节点的中间节点返回到发起节点。

节点将相邻节点（next hops）的连接状态保存在活动路由表里（active routes）。当活动路由表里有一条连接断开时，一条RERR消息（路由错误消息）将被用来通知其RERR消息指出了不再能到达的目的节点他节点发生了连接断裂。（甚至是目的子网）。为了实现这种报告机制，每个节点还要维护一个“先驱表”（precursor list），表中包含了一些邻居的IP，这些邻居可能会将它用作达到目的地的下一跳节点。先驱表里的信息可以很轻易的从回传RREP的过程中获得，因为按照定义，RREP就该是传往先驱节点的。如果RREP有一个非零的前缀长度，那么RREQ的发起者将被包括在先驱表里作为子网的路由。（不是特定的某个精确目的地）。

AODV是一个路由协议，它的工作就是管理路由表。即使是短期的路由，也必须保留它在路由表里的信息。比如为RREQ临时存储的返回路径。AODV的每个路由表项将会包含下列的域：

-目的节点IP地址 -目的节点序列号

-目的节点序列号是否正确的标志

-其他状态和路由标志（比如，有效，无效，可修复，正在修复） -网络接口

-跳数（到达目的节点需要的跳数） -下一跳 -先驱表

-生命（路由过期或应当删除的时间）

管理序列号对避免路由回环至关重要，即使是当连接断裂，一个节点不再可达而无法提供他自己的序列号信息的时候也是如此。当一条链路断开或失效，导致一个节点不可达，当这种情况发生时，将通过对序列号的操作和标注路由表项为不正确来使得这条路由失效。

- 19 -