基于鱼群优化的车载自组织网络路由算法

罗 龙，胡凯文，盛 丽，孙 罡*，曹可建，虞红芳

(1. 电子科技大学光纤传感与通信教育部重点实验室 成都 611731；2. 国家计算机网络应急技术处理协调中心 北京 海淀区 100089)

车载自组织网络(vehicular Ad Hoc networks,VANET)是由车辆和路边基础设备(road side units,RSU)组成的新一代移动多跳自组织网络。VANET[1]中的各节点通过信息交互，为系统提供包括道路状况(车祸、道路损坏、车辆拥堵等)、可用资源(可充电电源、空闲停车位等)、周期信标(车辆节点基本必要通信消息)等在内的多种消息。近年来，车载自组织网络得到了快速发展，已成为智能交通系统的关键技术之一[2]。

VANET在安全、运输效率和信息娱乐方面都存在大量潜在的应用[3]。VANET的早期应用大多是为了提高交通安全。近年来，在专用短程通信技术[4](dedicated short range communication, DSRC)频谱上，美国联邦通信委员会(federal communications commission, FCC)预留的频段在被交通安全相关应用使用后仍有大量剩余，于是许多其他应用相继出现[5]。如VANET在交通控制和道路维护系统中的实时数据收集[6]、自动化控制、智能收费、增强导航[7]以及一些特定的位置服务、音视频传输、各种移动端的娱乐服务[5]等各方面都发挥了至关重要的作用。因此，优化VANET通信技术对更安全、更方便智能的交通具有重要意义。

然而，VANET中的节点具有高速移动的特性，网络拓扑时变性强，使用传统路由方法将导致极低的数据包传输成功率[8-9]。如文献[10]已经证实在车辆通信半径为250 m、平均速度为100 km/h的道路上，节点间的通信链路存在15 s的概率仅为57%。此外，在发生交通事故、路面损坏等紧急情况时，消息无法及时传输将带来非常严重的后果[11]。因此，研究适用于VANET的可靠高效路由算法很有必要。

针对VANET中对时延敏感的消息的传输需求，本文提出一种基于鱼群优化的车载自组织网络路由算法。面对VANET动态变化的网络拓扑和网络拥塞情况，节点通过及时感知邻居节点当前发送队列是否拥塞、邻居节点是否可靠、邻居节点位置等周围环境的变化进行判断，选择消息传输的最优中继。

1 相关工作

随着万物智联的发展，VANET的需求越来越多[12]，其路由算法研究成为了近年来网络领域的热点话题。在早期的移动自组织网络(mobile Ad Hoc network, MANET)研究中，研究者们提出了基于位置的路由算法GPSR[13]、动态源路由算法DSR[14]、源驱动路由算法AODV[15]等经典协议。近年来，越来越多的研究者将仿生学模型应用到VANET中，提出了基于蛛网模型的路由算法[16-17]、基于蚁群优化模型的路由算法[18]、基于微生物的启发式路由算法[19]等很多性能优越的算法。

文献[16]提出以源节点所在路口为中心建立蛛网模型，在消息传输前发送探测消息探索蛛网，找到通往目的地的最优路径。在此基础上，文献[17]使用路边停驻车辆作为辅助进一步优化了蛛网模型的性能。文献[18]利用蚁群优化模型，通过蚁群探测消息让网络中的节点能够及时感知到周围路段情况，从而选出到达目的地的最优路径。文献[19]基于微生物模型对传输的历史反馈消息进行学习。文献[13]提出了VANET中一种经典的路由算法，该算法主要以贪心思想让当前节点在选择下一跳中继时总是选择距离目的节点最近的邻居节点作为中继。目前，很多研究工作仍以该算法为基准进行对比和参考。

在最近的研究中，研究者们考虑了VANET拓扑动态变化的特征，并针对该特征设计出了许多模型来提升路由性能。本文基于鱼群优化这一仿生模型，面向VANET中时延敏感类消息的传输提出一种新颖的路由算法，能够在保证消息传输成功率的同时，进一步优化传输时延，提升VANET的路由性能。

2 鱼群优化模型

人工鱼群算法(artificial fish swarm algorithm，AFSA)[20]是通过模仿鱼类觅食、跟随、聚集行为的智能优化算法，具有收敛速度快、效率高等优点。

觅食行为(prey)：如图1所示，鱼类通过视觉感知水中食物浓度决定移动方向进行觅食行为。

图1 鱼类觅食示意图

在觅食行为中，假设某条鱼所在环境当前状态为Xi，食物浓度为F(Xi)，在其视野范围(Di,j＜Visual)内随机寻找环境状态为Xj：

如果F(Xi)＜F(Xj)，则按照式(2)朝Xj的方向前进一步。

否则，重新随机选择状态Xj，并判断是否满足前进条件。如果多次搜索后仍未找到合适的Xj，则按照式(3)随机移动一步。

跟随行为(follow)：在鱼类觅食的过程中，当一条鱼或者几条鱼找到食物时，其他伙伴会跟随而来。假设当前一条鱼所在环境状态为Xi，在其视野范围内(Di,j＜Visual)探索邻域伙伴所在位置Xj的食物浓度F(Xj)，寻找使得F(Xj)最大的Xj(即该伙伴已找到食物浓度较高的区域)。如果F(Xj)＜F(Xi)且Nj/Ni＜δ(Nj为Xj区域内鱼的数量，N为鱼的总数，δ为拥挤因子)，表示Xj食物浓度较高且不太拥挤，鱼将按照式(2)向位置Xj前进一步；否则找寻次优的Xj，多次尝试后仍无法找到时，执行觅食行为。

聚集行为(swarm)：描述了鱼群会聚集在食物附近的现象。设鱼当前所在环境为Xi，在其视野范围内(Di,j＜Visual)探索伙伴数量Nc及其中心位置Xc。如果Xc所在位置的食物浓度F(Xc)＜F(Xi)且Nc/Ni＜δ，表示该伙伴群中心食物浓度较高且不太拥挤，鱼将按照式(4)向位置Xc前进一步；否则找寻次优的Xc，当多次尝试后仍无法找到时，执行觅食行为。

随机行为(random)：当鱼群无法找到食物浓度较高的邻域时会在视野内随机移动，是觅食行为的一个缺省行为。

3 系统模型及路由算法设计

3.1 VANET系统建模

本模型将一片区域内由车辆组成的自组织网络类比作一片水域，并将负载较轻、传输成功率高的车辆视为食物。网络中车辆会定时产生包含通信范围的消息，这些消息看作鱼群辅助消息 (fish message, FM)。鱼类前进的每一步视作FM从当前节点到下一个节点之间的一跳传输。每辆车有设备负载状态θ和传输成功率μ两个状态参数。食物浓度可以由式(5)计算得到，其中α和β分别为设备负载情况和设备传输成功率的权重。

当F(Si)大于阈值γ时，车辆Si为食物车辆。

3.1.1 觅食行为

当网络中各车辆设备状态空闲、传输成功率高时，如图2所示，以S1为例，根据鱼群算法，FM在S1处执行觅食行为。根据其邻居状态表1：θ2=θ3，μ2=μ3。在S1处，根 据 式(5)得 到F(S2)=F(S3)＞γ，S2和S3均为食物节点。S1处的FM认为找到了两个食物节点，将S2和S3添加到优先集合P当中。

图2 网络空闲时道路车辆情况

表1 S1邻居状态表

此时，FM会以式(6)给出的概率游向找到的某一食物节点：

式中，N为所有满足F(Sj)＞γ的邻居车辆组成的集合；Np为优先集合；δi为Si对应的拥挤因子，δi由式(7)计算得到：

FM在到达食物节点后会判断当前区域是否拥挤。若不拥挤，则停留在此处；反之，执行随机行为，并携带当前车辆是食物节点的消息，随机游向任意邻居。概率由均匀分布的概率密度函数式给出：

式中，Nnei为邻居数量。

拥挤因子有助于避免所有FM聚集在一个食物节点上。如果车辆周边有多个食物节点，受拥挤因子的影响，FM会平衡地流向这些食物节点，为正常消息的传输提供更多选择，避免正常消息全部流向同一个食物节点，浪费其他食物节点的资源，造成算法的局限性。同时，在聚集了一定的FM后，食物节点会将后续FM携带其相关信息后随机转发出去，从而使周围的邻居都能感知到该食物节点，并将后续的业务消息交由该食物节点转发。

当网络发生拥塞时，如图3所示，假定车辆S3设备负载较高，FM在执行觅食行为时发现θ3＜θ2，F(S3)＜γ＜F(S2)。S1更新优先集合，S2仍为食物节点，S3退出优先集合。此时S1处的FM会游向S2。为了提升模型容错率，如果S1还有其他邻居的食物浓度比较高且大于γ，那么FM会以式(6)的概率来选择前进方向。

图3 网络拥塞时道路车辆情况

在网络拓扑发生变化时，如图4所示，车辆S5在行驶过程中导致S3-＞S5链路中断，S3的丢包率增加，此时μ2＞μ3，F(S2)＞γ＞F(S3)。更新优先集合，S2仍为食物节点，S3退出优先集合。如果在S1处还有其他邻居处的食物浓度大于γ，FM仍以式(6)的概率选择前进方向。

图4 网络拓扑变化时情况

算法1：FM的觅食行为

车辆S0、鱼群消息FM、优先集合P、S0邻居集合N(S1,S2,···,Sj)、拥挤因子δ、食物浓度和拥挤因子阈值γ、σ

3.1.2 跟随行为和聚集行为

跟随行为描述的是鱼类会跟随已找到食物的伙伴的轨迹的现象。聚集行为则是指鱼类会聚集在食物浓度较高的区域，其本质也是跟随行为导致的。因此，本模型将两种行为统一称作跟随行为。

如前文所述，FM在S1处通过觅食行为成功找到一个或多个食物节点后，会将食物节点添加到优先集合中并为其设置拥挤因子δ。对于后续到达S1处的FM，直接根据优先集合判断前进方向。在优先集合中，元素是伙伴已选择的方向，往往食物浓度比较高，且元素数量远小于邻居表，因此，跟随行为在提高搜索效率的同时，可以让后续FM更快地发现食物节点。如算法2所示，如果优先集合里有一个或者多个方向可供选择，FM会根据式(6)给出的概率来选择前进方向。如果优先集合中没有元素，表示之前没有伙伴找到食物，无法跟随，此时执行觅食行为。

算法2：FM的跟随行为

车辆S0、鱼群消息FM、优先集合P、S0邻居集合N(S1,S2,···,Sj)

if(P≠φ)

FM以式(6)给出的概率游向某一邻居Sj

else

执行觅食行为

end if

3.1.3 扩散行为

为更好地适应VANET动态变化的网络环境，本模型在鱼群优化的基础上增加一个仿生学行为：扩散行为。该行为描述的是在食物浓度较高的区域内，食物由于鱼群的聚集很快被消耗殆尽后，鱼群扩散并重新寻找食物的行为。本模型中，食物节点在未来一段时间内会承载当前区域内大部分的中继任务，导致设备负载增加和传输效率降低。另外，当网络拓扑改变时(邻居车辆驶离食物节点的通信范围)，食物节点在接收消息后无法转发，也会导致传输成功率降低。在这些情况下，聚集的FM认为食物被消耗殆尽，执行扩散行为并重新寻找食物。周围节点收到扩散的FM后获知该食物节点已失效，将更新自身优先集合并重新选择业务消息的中继。

算法3：FM的扩散行为

车辆S0、鱼群消息FM、优先集合P、食物浓度阈值γ

if(F(S0)＜γ)

聚集在S0处的所有FM携带S0的状态执行觅食行为并扩散

end if

3.2 路由算法描述

基于3.1节中的VANET系统模型，本文的路由算法的主要步骤如下：当通信需求产生时，源车辆S0首先判断目的车辆D是否在通信范围内，若是，则直接将消息发给目的点，路由结束；反之，执行以下步骤进行路由。

1)选择第一代候选节点：为使消息每一跳传输都在向目的节点靠近的方向上进行，当某邻居节点Sj与目的节点之间的距离 d isSjD小于源节点和目的节点之间的距离disSD时，将Sj添加到第一代候选节点集合Q(S1,S2,···)中。若Q为空，为避免消息向远离目的节点的方向传输而出现回传和成环的问题，将直接丢弃数据包；若Q不为空，执行步骤2)。

2)选择第二代候选节点：为使消息传输经过的跳数尽量小，每次选择时应满足以下两个原则：1)邻居节点Sj和目的节点D之间的距离 d isSjD尽量小。如图5所示，S0向D发送消息时将选择S2以避免增加不必要的跳数；2)源节点S0往邻居节点Sj的方向S0→Sj与源节点S0往目的节点D的方向S0→SD之间的夹角ω尽量小。如图6所示，S0在向目的车辆D发送消息时，将在通信半径范围内选择S2或者S3，从而避免传输方向扩散和偏离目标车辆。

图5 原则1示意图

图6 原则2示意图

本文综合考虑d isSjD和ω两个因素，使用TOPSIS方法[21]从集合Q(S1,S2,···,Sm)中选出第二代候选节点集合T(S1,S2,···,Sn)(n＜m)。TOPSIS是一种通过对现有的对象进行相对优劣评价而逼近理想解的排序法。假设集合Q中有m辆车，各车辆的距离夹角参数如表2所示。

表2 距离夹角参数表

对于 disSjD和ω两个评价指标，建立如下特征矩阵：

对特征矩阵进行规范化处理，利用式(9)计算得到规范化矩阵元素rij：

为以上两个评价指标分别设置权重τ1和τ2，由式(10)计算权重规范化矩阵元素：

式中，i=1,2,···,m；j=1,2。

根据权重规范化矩阵，计算每个指标的最优解和最劣解。由于距离更短和夹角更小的目标更优，因此，权重规范化矩阵中各列的最小值即为最优解：

式中，i=1,2,···,m。

可以根据式(12)计算出集合Q中车辆的两个评价指标与其对应的最优解和最劣解的距离：

集合Q中每辆车的最终得分为：

将选择得分较大的前n位加入到第二代候选集合T(S1,S2,···,Sn)中。这些候选节点能够较好地避免消息传输中的无意义传输，同时保证每一次传输都尽量向目的节点靠近。

3)选择最优中继：引入鱼群优化模型后，算法得到优先集合P，通过选择T∩P中的元素可找到通往目的节点方向上的食物节点，将消息交给负载较轻、传输成功率高的食物节点进行中继，从而提升路由性能。若T∩P=φ，查询邻居状态表，根据式(5)计算邻居食物浓度，选出当前非食物节点中食物浓度最大的节点。若T∩P≠φ，计算Si∈T∩P，根据式(5)选出Si中食物浓度最大的节点。最后，将业务消息交给选出的邻居Sj，Sj收到消息后执行新一轮路由算法选择下一跳中继。

算法4：消息路由算法

车辆S0收到需要转发业务消息MSG

目的车辆D、优先集合P

S0邻居集合N(S1,S2,···,Sj)

if(D不在S0的通信半径内)

4 仿真实验与结果分析

4.1 仿真实验设计

本文在SUMO[16,22-23]上建立道路车辆模型，使用Veins[22-23]框架在网络仿真平台OMNET[22-23]上搭建实验环境。表3给出了实验中使用的主要参数。仿真实验采用图7中所示的2 km × 2 km地图[15]。

图7 仿真地图

表3 仿真实验参数设置

4.2 结果分析

为了评估算法性能，实验将本文算法FSR与基于仿生学的VANET路由算法PASRP[17]、URAS[19]及经典的VANET路由算法GPSR[13]进行了对比。

4.2.1 消息平均到达时延

图8展示了消息平均到达时延随车辆密度变化的结果。这部分实验中的控制业务消息产生速率为10(个/s)。仿真结果显示，本文算法FSR优于其他3种对比算法。总体而言，随着车辆密度增加，时延呈上升趋势。这是因为更多的消息能够到达目的点，不会在中途被丢弃。另外，在车辆密度低时，PASRP的平均到达时延略高于GPSR，这是因为PASRP需要等待探测消息的回馈才能为业务消息规划路由。

图8 消息平均到达时延对比

图9展示了消息平均到达时延随业务消息产生速率变化的结果。这部分实验中的控制车辆密度为75辆/km2。仿真结果显示，本文算法FSR优于其他3种对比算法。随着业务消息的增多，时延呈递增趋势。

图9 消息平均到达时延对比

以上两组实验结果都展示了FSR在降低VANET的消息传输时延方面的性能最优，这得益于基于鱼群优化的设计。

4.2.2 消息到达率

图10展示了控制业务消息产生速率为10个/s时，消息到达率随车辆密度改变的实验结果。FSR的消息到达率略高于其他对比算法。这是因为FSR引入了鱼群优化模型，节点可以动态找到周围传输成功率高的节点转发消息，从而更有效地保证了消息到达率。当车辆密度足够大的时候，FSR的性能略差于PASRP，这是因为PASRP建立了完整路由，能够更好地保证消息到达率。

图10 消息到达率对比

图11展示的是控制车辆密度为75辆/km2时，消息到达率随业务消息产生速率变化的实验结果。以上两组仿真实验结果显示，FSR能够保证较高的消息传输成功率。

图11 消息到达率对比

4.2.3 通信开销

通信开销定义为传输一个业务消息所需辅助控制消息的平均字节数。图12展示了控制业务消息产生速率为10个/s时，通信开销随车辆密度变化的情况。总的来说，FSR和PASRP的通信开销高于GPSR和URAS。这是因为FSR需要网络中存在一定数量的鱼群消息，而PASRP则需要发送一定的蛛网探测消息以建立完备的路由。当车辆密度较低时，产生的辅助控制消息较少，成功到达的业务消息也较少。随着车辆密度增加，周期消息与辅助消息增加，成功到达的业务消息增加，此时通信开销会短暂上升。但随着车辆数量进一步增加，成功传输的业务消息增长速率将高于辅助控制消息的增长速率，此时通信开销会呈现递减趋势。

图12 通信开销对比

图13展示了控制车辆密度为75辆/km2时，通信开销随业务消息产生速率变化的情况。实验结果显示，FSR与PASRP的开销大致相当。当业务消息数量较少时，FSR的通信开销低于GPSR和PASRP，这是由于此时网络拥塞情况较少，需要的鱼群辅助消息较少。当业务消息数量增多时，网络拥塞情况随之变严重，为了保持传输性能需要的鱼群辅助消息也会增加，此时FSR的通信开销会高于GPSR和PASRP。

图13 通信开销对比

以上实验结果表明，本文所提的FSR算法能够在增加少量通信开销的前提下，显著改善VANET中消息到达的平均时延和消息到达率。

5 结 束 语

本文将鱼群优化模型嵌入到车载自组织网络当中，提出了基于鱼群优化的VANET路由算法FSR。FSR通过鱼群快速搜索到节点附近区域内传输性能较好的邻居，在正常业务消息传输时及时利用这些节点提高传输性能。同时，在VANET网络情况和拓扑频繁改变下，鱼群优化模型也能够以较快的速度再次搜索到新的食物节点。本文提出的方案能够契合车载自组织网络的特点，提升路由性能。