MLSRP：一种面向Ad Hoc网络的路由协议

2020-03-18赵洪岩谭小波

沈阳理工大学学报 2020年5期

赵洪岩，谭小波，徐飞

(沈阳理工大学信息科学与工程学院，沈阳 110159)

Ad Hoc 网络应用领域包含军事通信、灾后紧急救援、传感器网络、局域网与个域网、车辆通信、与蜂窝系统结合等[1]，因此成为网络研究领域的热门话题。Ad Hoc 网络应用层次管理对整个网络的移动节点分簇，实现网络结构分层，有助于对整个网络进行集中管理和提高网络的可扩展性[2]。在分簇网络结构中，由于簇间节点比较多且节点间相对移动性比较高，链路容易发生断裂，所以采用路由维护开销小的按需路由协议[3]。传统的按需路由协议如按需距离矢量路由协议(AODV)协议[4]在建立路由时只建立单一路径，使用此单一路径传输数据，在负载较大时容易产生拥塞，降低网络吞吐量。基于AODV协议的多径路由协议如按需多径距离矢量路由协议(AOMDV)协议[5]，使用的是在主路径失效后切换备份路径继续通信的策略，而不是使用负载分配、并行传输的策略，没有真正意义上起到负载均衡的作用。AOMDV 协议在寻找下一跳时没有考虑相邻节点间的综合移动性[6]，在分簇网络结构中建立的路由稳定度低，链路容易发生断裂。本文在 AODV 协议的基础上设计一种适用于分簇网络结构的簇间路由协议，该协议具有增大链路稳定性、均衡负载的特点。

1 分簇网络结构相关介绍

1.1 分簇结构的网络模型

Ad Hoc 的分簇结构的网路模型由簇首、普通簇成员和网关构成[7]。通信分为簇内通信与簇间通信[8]。网络模型如图1所示。

1.2 AODV 协议在分簇网络结构中的问题

图2为AODV协议路由回复报文(RREP)传输过程。

如图2所示，源节点S对目的节点D进行路由查找，在找到节点D后，节点D向节点S发送RREP报文。假设节点C的RREP报文先到节点A，节点B的RREP报文后到节点A，此时节点A在AODV协议中，如果满足以下两个条件中的任意一个将更新前向路由。

(1)此RREP报文中的序列号比自身现有表项中D节点的序列号大；

(2)此RREP报文中的序列号与自身现有表项中节点D的序列号相同，但是此RREP报文中到节点D的跳数比自身现有表项中到节点D的跳数小。

如果不满足以上两点，节点A将节点B的RREP报文直接丢弃。

根据上述可知，AODV协议在寻找下一跳节点时，仅根据序列号和跳数建立的前向路由不一定是最稳定的，而且路径单一，当链路发生断裂时，将会重新寻找路由或进行路由修复，将造成可靠性降低，端到端的时延增大，且骨干网中的每个节点参与簇内和簇外路由，簇首节点本身的负载很大，使用单一路径路由还会造成负载不均，容易造成网路拥塞，降低带宽利用率。

所以，本文在AODV协议的基础上提出多路径链路稳定路由协议(Multipath link stable routing protocol，MLSRP)。

2 多路径链路稳定路由协议设计

2.1 MLSRP的路由度量设计

MLSRP的路由度量需要考虑以下两种因素：

(1)链路综合稳定性：是指从目的节点到当前节点的综合稳定性。链路综合稳定性越大，说明该链路越不容易失效；

(2)节点负载：是指节点缓存队列中的数据长度。链路综合稳定性的定义为

(1)

式中：LCSsum表示链路综合稳定性；CSi表示两个相邻节点的综合稳定性。

对于一条由节点D到节点A的链路，综合稳定性为

(1)D→E→B→A

LCSsum=CSDE+CSEB+CSBA

(2)D→E→C→A

LCSsum=CSDE+CSEC+CSCA

使用节点负载系数来反映节点负载的高低，其定义如式(2)所示。

(2)

式中：Li表示节点负载系数；L(i)表示节点i的数据链路层缓冲队列中正在等待处理报文的实际长度；L_MAC表示节点i数据链路层缓冲队列能够支持的传输报文的最大长度。

从式(2)可知，Li的值越大，表明节点当前时刻缓冲队列中需要处理的报文数量越多，对应的节点负载程度也越高。

综上分析可以得出新的路由度量Metric的定义：对一条由节点i到节点j的链路Li，j，该链路的Metric值定义为

(3)

当LCSsum的值越大，表示这条链路越稳定，Metric的值也就越大。当负载较小时，对应的负载系数Li较小，Metric的值也就越大。

2.2 路由请求与路由应答

路由请求的过程与AODV协议一致，本文不做赘述。

MLSRP的路由应答流程如图3所示，流程描述如下。

(1)目的节点收到路由请求报文(RREQ)后，将Li的初始值设为0，将LCSsum的初始值设为CS，CS为与之对应的下游邻居节点的综合稳定性，生成对应的RREP报文，然后反向发送到对应的下游邻居节点。

(2)下游邻居节点收到RREP报文，判断该节点是否为源节点，如果是源节点则停止转发，准备发送数据；否则，为中间节点。每个中间节点只要接收到RREP报文后，就将与下游邻居节点的CS加上RREP报文中LCSsum，更新RREP报文中LCSsum，然后查看自身的Li；如果自身的Li大于RREP报文中的Li，更新RREP报文中Li，否则RREP报文中的Li不变，然后沿着反向路由广播出去，并建立前向路由，重复(2)。

2.3 负载分配

节点S向节点D发送数据的过程如图4所示。

负载分配的基本原理如下：

每个节点收到目的节点回复的多个RREP报文后，从每个收到的RREP报文中获取相应信息，计算出各条链路的Metric。根据所有Metric计算与下游相邻节点间链路的负载比例，并将负载比例记录在前向路由表中。在发送数据时，按照负载比例为每条链路分配负载。

负载比例为某条路径的Metric所占总Metric的比例，其定义为

(4)

式中：LAi表示链路的负载比例；Metrici表示每条链路的路由度量。

2.4 路由维护

在源节点第一次发送数据前，根据负载比例计算每条链路的总负载比例和路径修复标志位。发送数据时，将链路总负载比例放入IP包头中选项位置，发送数据时经过的每个节点都计算一次每条链路的总负载比例和路径修复标志位，并将路径修复标志位放入前向路由表中。

每条链路的总负载比例定义式为

(5)

式中TLA表示该链路的总负载比例。

路径修复标志位F，其定义式为

(6)

式中n表示从源节点到目的节点路径的个数。

如果某条链路失效，将执行如下操作进行动态调整负载。

(1)如果失效链路上游节点为源节点，源节点重新进行路由查找，广播RREQ报文；否则转(2)。

(2)查看前向路由表的路径修复标志位，如果路径修复标志位为1，说明此路径重要，断裂处的上游节点进行本地修复，转(3)；否则转(5)。

(3)如果修复成功，向源节点发送RREP报文，经过的每个节点都更新负载比例，重新为每条链路分配负载；否则转(4)。

(4)如果修复失败，向源节点发送路由错误(RERR)报文，源节点重新发起路由查找。

(5)如果路径修复标志位为0，说明此路径次要，不修复。

路由维护流程如图5所示。

2.5 相关报文与路由表设计

MLSRP的RREP报文与前向路由表设计如下。

(1)路由回复报文

为实现MLSRP，在AODV协议的RREP报文基础上增加了LCSsum字段和Li字段。RREP报文格式如图6所示。

(2)前向路由表

节点在接收RREP报文后建立前向路由表，在AODV协议的前向路由表基础上增加了负载比例LAi字段和路径修复标志位F字段。前向路由表格式如表1所示。

表1 前向路由表格式

3 仿真与验证

3.1 仿真场景与参数设置

采用NS-2平台[9]对提出的路由设计进行仿真。网络的仿真场景是20km×20km的自组织网络，生成100个节点。节点的最大通信半径设置为300m，每个节点的初始运动速度设置为2m/s，其中设置节点的最小移动速度为2m/s，最大移动速度为30m/s，并向同一方向移动，每个节点的间距为100m。网络负载以CBR[10]的形式生成。使用基于综合移动性预测的分簇算法[6]生成分簇网络结构。对多路径链路稳定路由协议(MLSRP)、传统的AODV及传统的AOMDV的端到端的时延和吞吐量进行仿真。

3.2 仿真结果分析

(1)对于多种协议的平均端到端时延仿真结果如图7所示。在低负载的情况下，时延都较小且呈上升后稳定的趋势，但MLSRP的端到端时延高于其它的两种协议；这是由于MLSRP考虑的因素很多，需要计算节点间综合稳定性和负载系数，从而带来更大的基础时延。随着负载逐渐增大，MLSRP的端到端时延小于其它两种路由协议；这是由于MLSRP在寻找下一跳节点时考虑节点间的综合稳定度，寻找到的下一跳节点稳定度高，链路不易断开，减少了触发路由维护机制的次数，从而减小了端到端的时延。

(2)对于多种协议的网络吞吐量仿真结果如图8所示，随着负载的增加，MLSRP与AOMDV协议的吞吐量都比AODV协议高，这是由于MLSRP与AODV协议都是多路径路由协议，降低了单位时间内重新建立路由的次数。MLSRP的吞吐量比AOMDV协议的吞吐量高；这是由于MLSRP使用负载分配和并行传输的策略，通过路由应答获取不同路径的拥塞程度信息，动态调整不同路径的负载，使网络负载均衡，提高了网络吞吐量和降低网络拥塞程度，实现网络资源利用率最大化。