中国科学院大学学报  2023, Vol. 40 Issue (5): 710-719   PDF    
基于洪泛约束的移动自组网多径路由协议
王筱翔1,2, 汪明亮1,2, 徐慧慧1,2, 覃荣华1     
1. 中国科学院上海微系统与信息技术研究所 微系统技术重点实验室, 上海 201800;
2. 中国科学院大学, 北京 100049
摘要: 移动自组网因其网络能够动态重组而广泛应用于紧急救援等场景之中, 但其拓扑结构的动态特性导致路由容易断裂, 而路由重建将占用较多网络资源。针对该问题提出一种新的基于洪泛约束和多函数度量的多路径路由协议FLMP, 利用基于节点移动性的洪泛约束机制, 结合局部最优和全局最优思想构建路由, 并利用多个路由度量函数选出最优主路由和备份路由用于数据传输。仿真结果表明, FLMP路由协议可以保证数据可靠传输, 有效减少路由断裂次数, 同时明显地降低路由控制开销。
关键词: 移动自组网    多径路由    洪泛约束    局部最优    全局最优    
Multipath routing protocol for MANET based on flooding limiting
WANG Xiaoxiang1,2, WANG Mingliang1,2, XU Huihui1,2, QIN Ronghua1     
1. Key Laboratory of Microsystem Technology, Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 201800, China;
2. University of Chinese Academy of Sciences, Beijing 100049, China
Abstract: Mobile ad hoc network (MANET) is widely used in emergency rescue scenarios because of its dynamic network reconfiguration. However, the dynamic topology of MANET causes routes to be easily broken and route reconstruction will occupy more network resources. To solve this problem, this paper proposed a new multipath routing protocol FLMP based on flooding limiting and multiple measurement functions. It uses the flooding limiting mechanism based on node mobility, combines local and global optimal ideas to construct routs, and uses multiple route measurement functions to select the optimal main route and backup route for data transmission. The simulation results show that the FLMP routing protocol can effectively reduce the number of routing breaks, ensure reliable data transmission, and significantly reduce overhead.
Keywords: MANET    multipath routing    flooding limiting    local optimization    global optimization    

移动自组织网络(mobile Ad hoc networks,MANET)是一种由移动节点组成的暂态性自治系统,支持在无固定网络基础设施的环境中迅速组网,并能根据网络环境的变化动态重组[1],它的自治性、分布式网络控制和可扩展性为其网络部署和现实应用带来了巨大的灵活性和便捷性,所以MANET不仅在灾难救援,而且在军事通信、临时通信等许多其他场景中也具有不容小觑的发展前景。然而,由于MANET中节点根据一定的移动模型在网络中移动,导致网络拓扑结构变化频繁,当有数据需要传输时,已有的通信路由可能因为节点移动已经失效,频繁进行路由修复或路由重建,造成较多数据分组丢失和网络时延,消耗大量网络资源,影响了网络性能。因此,近年来MANET路由协议成为一个研究热点,路由协议的主要设计目标之一就是在能够保证数据传递可靠性和传输时效性的同时,减少通信过程中的资源消耗,提高网络QoS性能和资源利用率。

现有路由协议根据路由构建数量可分为单路径路由协议和多路径路由协议。单路径路由协议,如AODV[2]等,只在网络中构建一条从源节点到目的节点的有效路径,当路径失效后进行路由重建,寻找新的有效路径。而多路径路由协议由单路径路由协议衍生而来,如AOMDV[3],通过选出多条从源节点到目的节点的路径,将其分为主传输路径和备份路径,在主传输路径失效后切换备份路径进行数据传输,以减少路由发现次数及路由发现引起的网络时延。针对MANET,单路径路由协议路由构建快,控制开销较小,但拓扑变化较快时,网络稳定性较差,数据传输可靠性低,而且无法均衡网络负载;多路径路由协议能提高网络稳定性,减少路由失效及数据分组丢失,但其控制开销较大,在网络节点较少时,因无法构建多条路由而退化为单路径路由协议,同时消耗了更多的资源。因此,需要一种低开销高稳定的移动自组网路由协议。

1 相关工作

多年来,学者在MANET路由稳定性差和控制开销大的问题上分别进行了大量研究。

现有MANET路由协议中,为提高路由稳定性,许多学者在路由度量方式上进行了优化。文献[4]提出一种基于多因素转发决策的动态路由协议MF-DR,该协议设计了基于地理信息的动态预测机制,同时提出转发决策中的邻域连通度参数,并融合多因素参数改进的链路评估方法。文献[5]提出一种EV-AODV协议算法,综合考虑节点的剩余能量和节点间的相对移动性定义衡量路由稳定性的参数EV,通过选择EV值最低的链路稳定路由,但是因其计算复杂度较大,不合适网络规模较大的场景。此外,传统多径路由协议上也有许多改进,文献[6]提出一种基于期望传输时间的多径OLSR路由算法,通过计算出节点间链路的期望传输次数值和带宽值进行路由选择,改善传统多径路由协议MP-OLSR中的路由丢包问题。文献[7]提出基于AOMDV的路由协议ERL-AOMDV,在此协议中,充分考虑能耗和链路稳定问题,利用节点剩余能量对路径的预期剩余寿命进行估计,保证构建的路径剩余寿命长,但是其路由剩余寿命预测考虑的因素较为单一。文献[8]的TA-AOMDV路由算法同样也是在AOMDV协议的基础上优化而来,它综合节点剩余能量、节点的可用带宽和队列长度作为路径选择参数,引入了链路稳定性概率。还有一些路由协议结合了智能优化算法,例如文献[9],在AODV协议上结合改进的蚁群算法提出一种多路径路由协议,该路由算法将生存时间、距离进展最大化和传输距离、时延最小化作为选择路由的标准,有效提高了分组投递率。

现有MANET路由协议中,为减少路由控制开销,针对控制消息洪泛(Flooding)提出的受限洪泛大致可分为以下几种:基于地理位置、基于节点度、基于邻节点。文献[10]提出基于地理位置信息的能量辅助路由协议LEAODV,该协议在AODV基础上,增加稳定二维前程值概念和能量分级辅助路由,减少路由请求开销,限制低能量节点参与路由,从而提高路由稳定性,但是该算法未考虑节点移动引起的路由失效问题。文献[11]针对高动态移动自组网,在RGR协议基础上增加移动预测机制,为基于地理位置的洪泛约束机制提供了更精准的位置信息,提高了数据分组投递率,降低路由开销和平均端到端时延。文献[12]提出基于按区路由发现机制的ZRDM协议,该协议在路由请求洪泛过程中,根据发送节点的节点度选择洪泛区域,但为满足贪婪传播策略,该算法倾向于选择可通信范围内最远的邻节点作为下一跳节点,链路较容易因节点移动而失效,影响路由稳定性。文献[13]通过引入路径延伸比参数控制洪泛的范围,从而减少控制开销。文献[14]则提出一种基于邻节点的控制开销减少方法ECHO,该协议中将洪泛过程分为全局洪泛和精简洪泛,在全局洪泛选出关键节点,之后利用关键节点进行局部洪泛并更新关键节点。精简洪泛相比于全局洪泛,能明显降低控制开销,但是该算法不利于负载均衡,关键节点负载大较易死亡,从而影响整体网络的性能。

结合以上分析,本文提出一种基于洪泛约束的多度量函数多径路由协议(flooding limiting multipath routing protocol, FLMP),FLMP协议在保证数据分组传输可靠性和传输时效的同时,降低了整体的控制开销。FLMP协议具有以下特点:首先,根据节点位置信息和移动性信息约束路由发现过程中控制消息洪泛范围,以减少控制开销;其次,根据局部最优中继节点选择建立路由,利用中继选择度量函数选择局部最优节点加入路由,建立多条源节点至目的节点的路由;最后,根据数据传输时对路由需求的不同,利用不同的路由度量函数,选出全局最优主传输路径和备份路径,以提高路由稳定性和备份路径的有效性。通过大量仿真与现有路由协议进行对比实验,仿真结果表明,FLMP协议可有效降低网络控制开销,提高分组投递率。

2 协议设计 2.1 网络模型

本文基于以下网络假设,网络场景如图 1所示。

Download:
图 1 网络场景示例 Fig. 1 Network scenario

1) 在L×L的网络区域内,随机分布N个同构移动节点,节点移动速度、方向随机。

2) 目的节点为位置固定的场外指挥中心,所有节点已知目的节点位置信息。

3) 所有移动节点配备GPS或其他可感知自身位置信息与移动信息的设备。

2.2 洪泛约束策略

在路由发现过程中,源节点利用路由请求信息(route request, RREQ)洪泛广播,建立到目的节点的有效路径,RREQ在整个网络中洪泛会造成较大的资源损耗,因此提出洪泛约束机制,机制可分为基于地理位置的可洪泛角度约束和基于移动信息的可洪泛半径约束两部分。

1) 洪泛角度约束

根据贪婪转发思想,转发节点会优先选择靠近目的节点的邻节点作为下一跳节点[15],而在转发节点的节点度较大时,位于远离目的节点方向上的邻节点收到的RREQ包是冗余的,因此节点可根据自身位置信息以及目的节点位置信息,确定可洪泛角度。

根据欧式距离公式,转发节点i位于(xi, yi),与目的节点(xd, yd)之间的距离Did计算为

$D_{i d}=\sqrt{\left(x_i-x_d\right)^2+\left(y_i-y_d\right)^2} . $ (1)

以转发节点i为原点建立直角坐标系,可确定转发节点与目的节点所在直线与x轴夹角εid,计算公式如下

$\begin{gathered}\varepsilon_{i d}^{\prime}=\cos ^{-1} \frac{\left|x_d-x_i\right|}{D_{i d}}, \\ \varepsilon_{i d}=\left\{\begin{array}{cl}\varepsilon_{i d}^{\prime}, & y_d-y_i \geqslant 0 . \\ 2 \pi-\varepsilon_{i d}^{\prime}, & y_d-y_i<0 .\end{array}\right.\end{gathered}$ (2)

因此,角度区间$\left[\varepsilon_{i d}-\frac{\pi}{2}, \varepsilon_{i d}+\frac{\pi}{2}\right]$内的邻节点位于趋近目的节点的方向上,同时考虑节点移动方向的影响以及防止路由空洞,得到转发节点i的可洪泛角度φi如下

① 角度区间$\left[\varepsilon_{i d}-\frac{3 \pi}{4}, \varepsilon_{i d}+\frac{3 \pi}{4}\right]$为可洪泛角度,即$\varphi_i=\left[\varepsilon_{i d}-\frac{3 \pi}{4}, \varepsilon_{i d}+\frac{3 \pi}{4}\right]$

$\left[\varepsilon_{i d}-\pi, \varepsilon_{i d}-\frac{3 \pi}{4}\right]$$\left[\varepsilon_{i d}+\frac{3 \pi}{4}, \varepsilon_{i d}+\pi\right]$为不可洪泛角度区间。示意图见图 2(a)

Download:
图 2 洪泛约束策略示例 Fig. 2 Illustration of flooding limiting strategy

2) 洪泛半径约束

由于节点移动性会影响节点间单跳链路的稳定性,所以选择位于转发节点移动方向上的邻节点作为下一跳节点时,通信链路更稳定。而位于通信范围边缘的邻节点较易因节点移动而链路失效,因此,转发节点利用自身移动信息,确定可洪泛半径r,示意图见图 2(b)

转发节点i移动速度大小为vi, 移动方向角度为θi,网络中所有节点的可通信范围半径为R,转发节点的邻节点存在两种情况:

① 当邻节点位于区间$\left[\theta_i-\frac{\pi}{3}, \theta_i+\frac{\pi}{3}\right]$,转发节点与邻节点之间的通信距离随着转发节点移动而缩小,为链路稳定性增强区域,因此,可洪泛半径等于转发节点可通信半径, 即r=R

② 当邻节点位于区间$\left[\theta_i-\pi, \theta_i-\frac{\pi}{3}\right]$$\left[\theta_i+\frac{\pi}{3}, \theta_i+\pi\right]$,转发节点与邻节点之间的通信距离随转发节点移动增加,为链路稳定性减弱区域,且链路稳定时长受节点移动速度影响,因此,可洪泛半径r计算方式如下

$r=\gamma_i R , $ (3)

其中:γi为节点i洪泛半径衰减因子,$\gamma_i=\left(1-\mathrm{e}^{-\frac{1}{v_i}}\right)$.

3) 约束融合

将两种洪泛约束结合,示意图如图 2(c)所示。

据式(1)和式(2),计算得转发节点i的邻节点j与转发节点i之间的距离Dij以及角度εij。当邻居节点个数小于5时,节点较稀疏,不进行洪泛约束;当邻节点个数大于5时,根据可洪泛角度φi和可洪泛半径r,邻节点j判断是否丢弃接收到的RREQ包,判断规则如下:

εijφi,邻节点j丢弃RREQ报文,不转发;

εijφi$\varepsilon_{i j} \in\left[\theta_i-\frac{\pi}{3}, \theta_i+\frac{\pi}{3}\right]$dijR,邻节点j转发RREQ报文;

εijφi$\varepsilon_{i j} \notin\left[\theta_i-\frac{\pi}{3}, \theta_i+\frac{\pi}{3}\right]$dijγiR,邻节点j转发RREQ报文;

εijφi$\varepsilon_{i j} \notin\left[\theta_i-\frac{\pi}{3}, \theta_i+\frac{\pi}{3}\right]$dij>γiR,邻节点j丢弃RREQ报文,不转发。

2.3 局部最优多路径建立策略

当目的节点收到RREQ包后,生成路由回复包(route replies packet,RREP),利用中继节点多跳传回源节点,源节点收到多个RREP包确定多条源节点至目的节点的路由。为减少多条路由间的相关度,FLMP路由协议建立的多条路由为链路不相交路由。链路不相交路由是指路由间拥有公共节点,但节点间不存在公共链路[16]

为保证数据传输时的通信质量,中继节点利用局部最优节点度量函数选择局部最优的邻居节点作为下一跳加入路径。

单跳路由生存时长SRETl是指组成单跳路由l的2个节点pq之间可通信时长,主要受单跳链路生存时长LETl和接收节点生存时长NETq影响,故单跳路由生存时长SRETl计算公式如下

$\mathrm{SRET}_l=\min \left(\mathrm{NET}_q, \mathrm{LET}_l\right) . $ (4)

① 对于单跳链路生存时长LETl,根据节点p和节点q移动信息,计算方式如下:

$\begin{gathered}\mathrm{LET}_l=\frac{-(a b+c d)+\sqrt{\left(a^2+c^2\right) r^{\prime 2}-(a d-b c)^2}}{\left(a^2+c^2\right)}, \\ \left\{\begin{array}{l}a=v_p \cos \theta_p-v_q \cos \theta_q, \\ b=x_p-x_q, \\ c=v_p \sin \theta_p-v_q \sin \theta_q, \\ d=y_p-y_q .\end{array}\right.\end{gathered}$ (5)

其中:(xp, yp)为节点p的位置坐标,vp为节点p的移动速度;(xq, yq)为节点q的位置坐标,vq为节点q的移动速度;r′为节点有效通信距离。

由于实际通信时易受环境等因素影响,故LETl计算公式中自由空间模型下,有效通信距离r′计算方式如下

$r^{\prime}=10^{\frac{\mathrm{MPL}-32.44-20 \log f}{20}}.$ (6)

其中:f为工作频率,最大路径损耗MPL为

$\text{MPL}=P_t-\text{ReceiverSensitivity}+ \text{Gain}- \text{Loss}_{\text{env}} .$ (7)

其中:Pt为发送功率,ReceiverSensitivity为接收灵敏度,Gain为天线增益,Lossenv为环境损耗。

② 对于节点生存时长NETq,计算公式如下

$\mathrm{NET}_q=\frac{\mathrm{e}_q^{\mathrm{res}}}{\operatorname{declay}_q^T}. $ (8)

其中:eqres为节点q的剩余能量,declayqT为节点q经过时间T的能量损耗系数,其计算公式如下

$\operatorname{declay}_j^T=\frac{\mathrm{e}_j^{\mathrm{init}}-\mathrm{e}_j^{\mathrm{res}}}{T}.$ (9)

其中eqinit为节点j初始能量。

因此,在建立路由时,选择剩余邻居节点中局部最优节点度量函数F(Nq)值最大的节点作为下一跳,公式如下

$F\left(N_q\right)=\frac{\alpha}{\operatorname{hop}_q}+\beta \frac{C_{\text{cap }}-\text{ cache }_q}{C_{\text{cap }}}+\mu \frac{\mathrm{SRET}_l}{\sum _n^N \mathrm{SRET}_n}.$ (10)

其中:hopq为源节点到节点q的跳数;Ccap为节点MAC层缓存队列容量;cacheq为节点q缓存队列数;N为可选的下一跳节点;$\sum\limits_n^N \operatorname{SRET}_n$为所有可选下一跳节点的单跳路由生存时长之和;αβμ分别为跳数、下一跳节点缓存队列数和单跳路由生存时长的权重系数,且α+β+μ=1。

2.4 基于多度量函数的路由选择策略

为提高备份路由有效性,减少路由维护过程中的资源损耗,提出一种基于多个度量函数的路由选择策略,选出全局最优主路由和备份路由。

1) 主传输路由度量函数

主路由需要保证数据传输时延小、数据投递率高,路由度量函数Fmain选取路由跳数hop、路由拥塞度Capacity作为度量指标,路径公式如下

$F_{\text{main }}=1-\mathrm{e}^{-\left(a \frac{1}{\text{ hop }}+b \text{ Capacity }\right)}.$ (11)

其中:ab分别为路由总跳数和路由拥塞度指标的权重系数,a+b=1。对于路由度量函数Fmain中的Capacity,其计算公式如下

$\text{Capacity}=1-\frac{\sum _{i=1}^{\text{Node}} \text{cache}_i}{\text{ Node } \times C_{\text{cap}}} \text.$ (12)

其中:Node为路由节点个数,cachei为节点i的缓存队列数,Ccap为MAC层缓存队列容量。

2) 备份传输路由度量函数

路径度量函数主要用于选取备份传输路由,为保证备份传输路由的生存时间长,选取路径生存时长RET作为度量指标,公式如下:

$\begin{gathered}F_{\text{spare }}=\max \left(\operatorname{RET}_r\right), \\ \operatorname{RET}_r=\min\nolimits_{l \in \operatorname{Link}}\left(\operatorname{SRET}_l\right) .\end{gathered}$ (13)

其中:RETr为路径r的预计生成时长,Link为路由上的单跳路由集合。

2.5 FLMP路由协议流程

FLMP协议整体可分为路由请求、路由建立、路由选择、数据传输4个部分。整体流程图见图 3

Download:
图 3 FLMP路由协议流程图 Fig. 3 Process of FLMP routing protocol

FLMP路由协议中,每个节点维护一个路由表,路径列表包含以下字段:下一跳ID、最后一跳ID、跳数hop、下一跳缓存数、单跳路由生存时长SRETl和路径编号。路由请求包RREQ是在原有基础上加入以下字段:转发节点位置信息、移动信息、半径衰减系数γi、有效角度φi、第一跳节点ID、节点缓存队列数cachei。路由回复包RREP是在原有基础上加入以下字段:第一跳节点ID、节点缓存队列数之和Capacity、路径生存时长RETr

路由请求  当有数据传输请求时,源节点检查路由表是否存在路由,若存在则直接进行数据传输,若不存在则生成RREQ包进行路由请求。邻居节点收到RREQ包后根据2.2节提出的洪泛约束策略判断是否丢弃RREQ包,若不丢弃,则此邻节点更新自身路由表以及RREQ数据包,并作为发送节点转发RREQ包给邻居节点。直至RREQ包传至目的节点。

路由建立  目的节点收到RREQ包后,生成RREP包传回源节点。中继节点收到RREP包后,根据2.3节提出的局部最优多径路由建立策略选择最优邻节点作为下一跳节点,同时更新自身节点路由表路由编号、RREP包中的节点缓存队列数之和Capacity、路径生存时长RETr并转发。源节点收到多个RREP报文确定多条源节点至目的节点的路由。

路由选择  源节点收到多个RREP包确定多条由源节点至目的节点的路由,利用RREP包中的节点缓存队列数之和Capacity和路径生存时长RETr,结合2.4节的路由度量函数FmainFspare,选取Fmain数值最大的路由作为主传输路由,选取Fspare数值最大的路由作为备份传输路由。

数据传输  初始使用主传输路由传输数据,当主传输路由失效后使用备份传输路由进行数据传输,当所有路由都失效后,重新进行路由发现过程,直至所有数据传输完毕。

3 仿真与性能分析 3.1 仿真环境设置

采用MATLAB对FLMP路由协议的性能进行仿真评估。仿真实验区域大小为2 000 m×2 000 m,所有移动节点初始位置随机,移动速度和方向随机,移动模型为随机游走移动模型(random walk model,RWM),单次实验源节点待发送数据包1 500个,其他仿真参数见表 1,参数设置参考文献[8]。仿真结果性能曲线的取值为多次实验结果平均值。

表 1 仿真参数 Table 1 The simulation parameters

实验中,将FLMP路由协议与其他3个路由协议进行对比,第1个是按需单径路由协议AODV[2];第2个是基于按区路由发现的路由协议ZRDM[12],协议在路由维护阶段加入了链路故障检测机制,通过周期检测路由质量以确保在路由失效前,建立其他有效路由;第3个是多路径路由协议ERL-AOMDV[7],该协议利用预测路由生存时长以保证路由稳定性。实验对比算法结果为原文献算法思想在本实验场景中的复现结果。

仿真主要进行了节点移动速度、网络节点个数、数据包发送速率对网络性能的影响3个方面的实验。由于本文主要是针对MANET拓扑变化频繁、数据易丢失、控制开销大问题,因此仿真实验主要关注性能指标如下:

1) 数据包投递率(packet delivery ratio, PDR)

该指标是指目的节点接收的数据包(Pr)与源节点发送的数据包(Ps)的比值

$\mathrm{PDR}=\frac{P_{\mathrm{r}}}{P_{\mathrm{s}}} \times 100 \%.$ (14)

2) 路由开销(routing overhead, RO)

该指标是指所有节点转发的控制包(Ppf)占所有节点转发的总通信包的比值

$\mathrm{RO}=\frac{P_{\mathrm{pf}}}{P_{\mathrm{pf}}+P_{\mathrm{df}}} \times 100 \%.$ (15)

其中总通信数据是控制包和数据包(Pdf)之和,控制包是指路由发现包RREQ和路由回复包RREP。

3.2 节点移动速度对网络性能的影响

为研究节点移动速度对网络性能的影响,本实验将网络节点数量固定为64个节点,数据包发送速率为15 packet/s,节点最大移动速度从2 m/s增加到24 m/s,实验结果如图 4所示。

Download:
图 4 节点移动速度对网络性能的影响 Fig. 4 Network performance versus nodal velocity

图 4(a)可以看出,FLMP协议的PDR优于其他3种路由协议,而且随着节点移动速度增大,AODV、ZRDM协议PDR下降明显,而FLMP协议较稳定,可达98%,效果优势明显,说明FLMP协议的多度量函数路由选择能有效提高备份路由的有效性,针对高动态性移动自组网有一定作用。

图 4(b)可以看出,FLMP协议的控制开销明显优于ERL-AOMDV协议,大致降低15%,说明洪泛约束机制能够有效减少多径协议的控制开销。在节点移动速度较小时,FLMP控制开销稍大于单路径协议,而在节点移动速度大时,FLMP协议控制开销效果明显优于其他3种协议,相比AODV协议降低7%左右,原因是多径协议单次路由重构的控制开销大于单径协议,网络较稳定时路由重构次数少,多径路由协议控制开销相对较高,网络拓扑不稳定时,单径路由协议路由重构次数多,导致控制开销明显增加。

图 4(c)可以看出在节点移动速度较小时,4种路由协议的时延基本一致,随着速度增大,FLMP协议的时延略低于其他3种协议。分析原因可能是在节点移动速度较小时,网络拓扑更新较慢,路由构建造成了较大的网络时延,而当节点速度较大时,网络拓扑结构变化快,路由生存时长变短,FLMP使用备份路由,路由重构次数少,而其他3种协议在路由重构上产生较多网络时延。

3.3 网络节点个数对网络性能的影响

为研究网络节点个数对网络性能的影响,本文将节点最大移动速度固定为12 m/s,数据包发送速率为15 packet/s,网络节点数从32增加到128个,实验结果如图 5所示。

Download:
图 5 网络节点个数对网络性能的影响 Fig. 5 Network performance versus node number

图 5(a)可以看出,FLMP协议整体优于其他3种协议,相比AODV协议,PDR提升4%左右,而且随节点个数增加,多径路由协议ERL-AOMDV和FLMP的PDR呈上升趋势,而路由协议ZRDM和AODV的PDR却呈下降趋势,主要是多路径协议备份路径减少了数据丢失,提高了PDR。

图 5(b)可以看出,随着节点个数增加,AODV、ERL-AOMDV、ZRDM协议的控制开销呈上升趋势,原因是参与洪泛的节点增加,导致控制开销增加,而FLMP协议控制开销先上升后下降,分析原因是受路由发现次数和节点个数两方面因素影响,其中FLMP路由发现次数曲线图如图 6。当节点为32个时,FLMP路由开销为37%,相比多径协议ERL-AOMDV的39%稍低,但高于AODV协议的23%和ZRDM协议的25%,这是因为此时网络较稀疏,单次路由发现可能无法构建有效路由,所以路由发现次数多,而且此时路径单一,稳定性较差,所以FLMP开销较大。随着节点个数增加,在80个节点时FLMP控制开销为33%,相比ERL-AOMDV减少约27%,原因是FLMP洪泛约束机制减少了冗余的控制包,同时备份路由度量指标为路径生存时间长,路由重建次数少,从而降低了控制开销。当节点大于80个后,路由重构次数不再下降,同时网络中参与洪泛的节点个数增加,导致FLMP控制开销增大,但控制开销相比ERL-AOMDV还是下降34%左右。

Download:
图 6 FLMP协议路由发现次数变化图 Fig. 6 Number of FLMP routing discoveries

图 5(c)可以看出,4种路由协议的平均端到端时延都随节点个数增加呈现下降趋势,原因是在节点密集时减少了多次路由重构。此外,在节点密度较大时FLMP时延低于其他3种协议。说明FLMP协议中的多度量函数路径选择机制保证了主传输路径的QoS性能,同时提高了备份路径的有效性。

3.4 数据发送速率对网络性能的影响

为研究数据发送速率对网络性能的影响,本文将网络节点数量固定为64个节点,节点最大移动速度固定为12 m/s,数据包发送速率从5 packet/s到25 packet/s,实验结果如图 7所示。

Download:
图 7 数据发送速率对网络性能的影响 Fig. 7 Network performance versus data sending rate

图 7(a)可以看出,4种路由协议的PDR都随数据包发送速率的增加有轻微的下降趋势,主要是因为数据包发送速率较大时,单次路由断裂会造成更多的数据包丢失。整体上看,FLMP协议的PDR在99%左右,明显优于其他3种路由协议。

图 7(b)可以看出,4种路由协议的控制开销随着数据包发送速率的增加而降低,主要是因为数据包发送速率较快缩短了数据发送的整体时间,减少了路由重构的次数。整体上看,FLMP协议的RO明显优于其他3种协议,相比于多路径协议ERL-AOMDV协议提高20%左右。

4 结束语

本文针对移动自组网拓扑变化频繁,重建路由控制开销大的问题,设计了一个基于洪泛约束和多度量函数的多径路由协议FLMP。该协议将节点移动信息作为洪泛约束的条件之一,引入洪泛半径衰减因子,动态调节中继节点的可洪泛范围,在保证路由生存时长的同时有效地降低了路由控制开销。此外,将局部最优中继节点选择和多个度量函数全局最优路由选择相结合,在保证路由QoS性能的情况下减少了路由断裂次数,也提高了备份路由的有效性。通过大量的仿真实验与现有的前沿工作相比证明,FLMP协议在保证数据分组投递率和数据传输端到端时延的同时,有效地降低了路由控制开销,是一种适用于移动自组网的路由协议。

参考文献
[1]
刘晓莹. 移动自组织网络的拓扑组网与信息分发研究[D]. 上海: 上海交通大学, 2018. DOI: 10.27307/d.cnki.gsjtu.2018.000603.
[2]
Perkins C E, Royer E M. Ad-hoc on-demand distance vector routing[C]//Proceedings WMCSA′99. Second IEEE Workshop on Mobile Computing Systems and Applications. February 25-26, 1999, New Orleans, LA, USA. IEEE, 1999: 90-100. DOI: 10.1109/MCSA.1999.749281.
[3]
Marina M K, Das S R. Ad hoc on-demand multipath distance vector routing[J]. Wireless Communications and Mobile Computing, 2006, 6(7): 969-988. Doi:10.1002/wcm.432
[4]
黄鹏飞. 基于多因素融合转发决策的动态路由协议设计与实现[D]. 西安: 西安电子科技大学, 2019. DOI: 10.27389/d.cnki.gxadu.2019.002648.
[5]
Wu J Z, Shi S, Liu Z Y, et al. Optimization of AODV routing protocol in UAV ad hoc network[C]// Artificial Intelligence for Communications and Networks, 2019: 472-478. DOI: 10.1007/978-3-030-22968-9_43.
[6]
杨路, 朱显, 王诗言. 一种基于期望传输时间的多径OLSR路由协议[J]. 计算机工程, 2018, 44(11): 95-99, 104. Doi:10.19678/j.issn.1000-3428.0048961
[7]
Banerjee A, Chowdhury S. Expected residual lifetime based ad hoc on-demand multipath routing protocol (ERL-AOMDV) in mobile ad hoc networks[J]. International Journal of Information Technology, 2019, 11(4): 727-733. Doi:10.1007/s41870-018-0107-2
[8]
Chen Z, Zhou W L, Wu S, et al. An adaptive on-demand multipath routing protocol with QoS support for high-speed MANET[J]. IEEE Access, 2020, 8: 44760-44773. Doi:10.1109/ACCESS.2020.2978582
[9]
卢钊. 基于AdHoc网络的多机器人通信研究[D]. 南京: 南京邮电大学, 2019. DOI: 10.27251/d.cnki.gnjdc.2019.000430.
[10]
白媛, 宋焱, 栗晨亮, 等. 移动自组网基于地理位置信息的能量辅助路由协议[J]. 现代电子技术, 2021, 44(2): 69-74. Doi:10.16652/j.issn.1004-373x.2021.02.016
[11]
黄金科, 樊晓光, 向新, 等. 基于按需和贪婪转发的移动自组网路由协议[J]. 工程科学学报, 2017, 39(5): 778-785. Doi:10.13374/j.issn2095-9389.2017.05.017
[12]
Khudayer B H, Anbar M, Hanshi S M, et al. Efficient route discovery and link failure detection mechanisms for source routing protocol in mobile ad-hoc networks[J]. IEEE Access, 2020, 8: 24019-24032. Doi:10.1109/ACCESS.2020.2970279
[13]
余晟, 尚德重, 周猛, 等. 基于可调节局部洪泛更新的移动WSN路由协议[J]. 中国科学院大学学报, 2015, 32(2): 273-280. Doi:10.7523/j.issn.2095-6134.2015.02.018
[14]
Ramanathan R, Servaes C, Ramanathan W. ECHO: efficient zero-control network-wide broadcast for mobile multi-hop wireless networks[C]//MILCOM 2018 - 2018 IEEE Military Communications Conference (MILCOM). October 29-31, 2018, Los Angeles, CA, USA. IEEE, 2018: 1-6. DOI: 10.1109/MILCOM.2018.8599737.
[15]
Fu J S, Cui B J, Wang N, et al. A distributed position-based routing algorithm in 3-D wireless industrial Internet of Things[J]. IEEE Transactions on Industrial Informatics, 2019, 15(10): 5664-5673. Doi:10.1109/TII.2019.2908439
[16]
Yallouz J, Rottenstreich O, Babarczi P, et al. Minimum-weight link-disjoint node-"somewhat disjoint" paths[J]. IEEE/ACM Transactions on Networking, 2018, 26(3): 1110-1122. Doi:10.1109/TNET.2018.2823912