基于地理位置改进的动态源路由协议

戴箎

武汉理工大学计算机科学与技术学院 湖北 430063

0 前言

DSR(动态源路由协议)协议是一种基于源路由的按需路由协议。设计DSR的目的在于创建开销非常低同时又能快速响应网络变化的路由协议，以高度反应式的服务确保数据分组在节点移动或者其他网络条件变化的情况下仍然能够正确地提交。DSR使用源路由算法，每一个给定路线的数据分组都在报头带有完整、有序的此分组必经的节点列表。使用源路由可以保证无环路，转发或者侦听分组的节点可以缓存分组中的路由信息以备后用，而且由于要传输的数据分组已含有必要的路由信息，中间节点不必保存路由信息。图1说明了一个应用源路由在自组网中传输数据分组的例子。网络(图1)中共8个节点，节点S向节点D发送数据分组，节点S建立路由之后，其路由路径中的转发节点信息将存入节点 S的路由缓存器中。发送数据分组时，将路由信息写到数据分组报头中，源节点按照该路径转发直到目的节点，图中节点S按照S-＞B-＞E-＞F-＞D转发，中间节点按照数据分组报头的路由信息转发分组，当到达节点F时各转发节点的示意图如图中虚线所示。转发路径一直存在数据分组的报头中直至到达目的节点D。

图1 标准DSR协议路由过程图

1 基于地理位置的路由思想

为了引入网络中移动节点的地理位置信息，每个节点需要配置GPS接收装置。如图2中当节点S需要向节点D发送或者转发一个数据分组时，它首先在自己的所有邻节点中，选择一个距离目的节点D最近的节点，作为数据分组的下一跳，然后将数据分组传送给它。该过程一直重复，直到数据分组到达目的节点D或者某个最佳主机。为使网络中的所有节点能获得邻节点的地理位置信息，采用一种简单的信标发送机制(beaconing)，该机制规定每个节点利用 MAC广播地址，周期性地向所有邻节点发送信标(beacon)信号，该信号中包含了节点的身份标识(如 MAC地址)和当前的位置信息。节点的位置用一对4Byte的浮点数来表示，分别代表节点的x, y坐标值。对于某一个节点而言，它可能有多个邻节点，这些节点之间发送的信标信号有可能发生冲突。为了避免这一机制，采用一种随机选取信标发送时间间隔的策略。

图2 基于地理位置定位的路由过程图

在一定时间间隔内，如果节点没有收到某一个邻节点发送的信标信号，则认为该邻节点已经失效或不在自己的一跳范围之内，于是将其从自己的邻居列表中删除。

2 DSR协议的综合改进算法

2.1 最优下一跳转发节点的定义

对路由协议的缓存用路径缓存和连接缓存来实现。总体思想是：全局拓扑采用路径缓存，局部拓扑采用连接缓存，网络中每个节点维护一个局部连接表，让路由所经过的中间节点掌握半径为几跳范围的局部网络拓扑结构，局部范围内的节点分为中心节点、边界节点。对每条全局路由来说，只让路由上的每个边界节点维护整条路由。边界节点到下一跳边界节点间的局部路由采用以下办法：

因为局部连接表内缓存的节点信息带有地理位置坐标(x,y)，在当前节点的n跳范围(包括0跳、1跳、2跳…n跳)内找一个满足最小的值作为路由转发节点。其中，坐标(x1, y1）、(x2, y2)分别为正在考察的节点、目的节点的地理位置坐标。这个节点我们称之为当前节点相对于目的节点而取的最优节点。

2.2 协议改进的具体步骤

2.2.1 协议改进的主要数据结构

实现的原DSR协议中移动节点缓存的数据有：路由表缓存(RouteCache)，路由请求表(RequestTable)、分组发送缓存器(SendBuff)、无请求路由应答表等主要数据，要实现上述改进需要添加的主要数据结构如下：

struct Location

{

double x; //x坐标

double y; //y坐标

}

struct LimFlood

{

ID src_id; //节点标示符

ID mac_id; //节点mac值

int curHops; //分组所走过的跳数

Location loc_node; //节点地理位置

}

在系统中，每一个移动节点(MobileNode)能及时通过getLocation函数得到它当前的地理位置坐标值。

2.2.2 局部连接表的建立

在整个网络中的每个节点都维护着一张局部连接表，连接表通过定期发送maxHops跳范围内的洪泛包来建立，采用LimFlood结构体封装分组内容来传输节点间局部连接的信息，当节点收到其他节点的 LimFlood包时也就获得了以该节点为中心的maxHops跳范围内其他节点的信息。

2.3 路由算法改进过程

2.3.1 请求分组算法处理过程

（1）通过 findRoute函数搜索该节点的路由缓存器，尝试找出一条路由到达有该分组头中的目的节点地址域给出的地址。

（2）如果没有从其路由缓存器中找到所需路由，那么该节点执行路由寻找进程寻找到达整个目的节点地址路由。为了初始化一个路由寻找进程寻找这个目的节点地址，该节点在当前这个分组中的DSR选项头中增加一个路由请求选项，或者将当前这个分组放入其发送缓存器中，然后通过单独发送一个包含这个路由请求选项的分组来初始化路由寻找进程。

（3）如果该分组当前不包含路由请求选项，那么这个节点必须有一条路由到达该分组的目的节点地址。将该分组中的源路由初始化为所选定的到达该分组目的节点地址的路由。

（4）将该分组发送到所选源路由的第一跳节点地址，使用路由维护机制决定该跳的可达性。

2.3.2 路由寻找过程

（1）findRoute函数找不到可以到达目的节点的路径，源节点S须生成到目的节点D的路由请求表RequestTable，运用在S的局部连接表的“邻接节点”中找到距离D.location最近的节点T。

（2）节点T记录下S到T的转发序列当做路由表缓存。

（3）以T为新的源节点来重复步骤(1)直到可以得到到达目的节点 D的转发路径，如：发起节点 S、Address[1]、Address[2]… Address[n]、目的节点D。

2.3.3 改进后的协议应用

如图3所示网络拓扑结构中，以maxHops=2跳作为半径，A、C、B、E作为节点S的边界节点，由于局部范围内采用了连接缓存(如图4)，每个节点知道以自己为中心的2跳之内的能到达的最远距离。按照基于地理位置改进后的 DSR协议，因为我们知道节点S两跳范围内能到达的所有节点的地理位置坐标，用公式dist计算，取满足条件的最小值来作为下一跳的转发节点(当然路由缓存中存有可行的路由路径不在考虑之列)。当需要路由发现时，每个节点发送 RREQ前先查找自己的局部连接表，如果目的节点在表内则直接将RREQ发送目的节点；否则将RREQ通过该节点半径范围内的最优下一跳转发节点(选择的是物理位置上最短的路径)。当该转发节点收到RREQ后，再以自己为中心节点来查找自己的连接表，搜索其半径范围内是否有目的节点。重复上述过程直到RREQ到目的节点为止。产生的路由只记录所经过的边界转发节点。这样一直重复下去，可以得到可行的路由路径。如按原DSR协议从S到D缓存的路径为SACFGD，现在就有可能是SCGD。

图3 网络拓扑图举例

图4 路径缓存和局部连接缓存

3 协议分析与仿真

3.1 协议正确性分析

路由发现时，在半径范围内找最优下一跳转发节点，因为查找的过程中比较了当前节点半径为有限 maxHops跳范围内的所有节点，其中也包括1跳范围，1跳范围就是原DSR路由协议的实现了，所以按照改进的协议路由发现机制时一定可以找到存在于网络内的目的节点。

3.2 协议仿真验证

传输时延是指一个站点从开始发送数据帧到数据帧发送完毕所需要的全部时间，也可是接收站点接收一个数据帧的全部时间。影响因素有路由发现的次数和时间、路由失效次数等。因为每个移动节点用一块存储空间来缓存了maxHops跳范围内的拓扑结构——局部连接表，这样，当路由发现时，可以从缓存中快速地找到到达目的节点的最优下一跳转发节点，直至到达目的节点。这样依靠每个节点的少量物理空间来换取协议的运行时时间减少，可以使整个Ad Hoc网络的路由开销显著减少，因而在平均传输时延上改进的协议比原DSR协议会有一定的提高。尤其当节点移动速度变快时，因为原有路径的断路或路径绕远，原DSR协议适应快速变化的能力有限，这时改进的协议通过搜索局部连接表来替代断路路由的维护方法比直接向源节点返回一个路由出错分组RERR以让源节点启动新的路由发现的方法要高效很多，将使网络中的传输时延性能得到明显提高。

4 结束语

DSR是无线自组网络路由协议中性能比较优越的一种协议，但是对于快速变化的网络结构难以及时做出反应，造成网络路由开销比较大，针对该问题，本文在DSR的基础上改进全网洪泛的路由发现策略，提出以有限跳作为半径范围来洪泛路由请求报文，半径范围内节点缓存中保存局部连接拓扑结构，在全局范围内用地理位置最小值的原则来确定下一跳的最优中转节点，从而有效改进了路由发现的时延，减少了自组织网络中节点间端到端数据分组传输的平均时延，提高了网络性能。

[1]屠梓浩,吴荣泉,钱立群等.无线Ad Hoc网络DSR路由协议的优化设计[J].计算机工程.2009.

[2]于宏毅等著.无线移动自组织网[M].北京:人民邮电出版社.2005.

[3]陈林星,曾曦,曹毅等著.移动Ad Hoc网络[M].北京:电子工业出版社.2006.

[4]The Network Simulator-ns-2.Project web page available at http://www.isi.edu/nsnam/ns.

[5]郑少仁,王海涛,赵志峰.Ad Hoc 网络技术[M].北京:人民邮电出版社.2005.