-
车载自组织网络(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动态变化的网络拓扑和网络拥塞情况,节点通过及时感知邻居节点当前发送队列是否拥塞、邻居节点是否可靠、邻居节点位置等周围环境的变化进行判断,选择消息传输的最优中继。
HTML
-
本模型将一片区域内由车辆组成的自组织网络类比作一片水域,并将负载较轻、传输成功率高的车辆视为食物。网络中车辆会定时产生包含通信范围的消息,这些消息看作鱼群辅助消息 (fish message, FM)。鱼类前进的每一步视作FM从当前节点到下一个节点之间的一跳传输。每辆车有设备负载状态θ和传输成功率μ两个状态参数。食物浓度可以由式(5)计算得到,其中α和β分别为设备负载情况和设备传输成功率的权重。
当F(Si)大于阈值γ时,车辆Si为食物车辆。
-
当网络中各车辆设备状态空闲、传输成功率高时,如图2所示,以S1为例,根据鱼群算法,FM在S1处执行觅食行为。根据其邻居状态表1:θ2=θ3,μ2=μ3。在S1处,根据式(5)得到F(S2)=F(S3)>γ,S2和S3均为食物节点。S1处的FM认为找到了两个食物节点,将S2和S3添加到优先集合P当中。
θ μ S2 θ2 μ1 S3 θ3 μ2 此时,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)的概率来选择前进方向。
在网络拓扑发生变化时,如图4所示,车辆S5在行驶过程中导致S3->S5链路中断,S3的丢包率增加,此时μ2>μ3,F(S2)>γ>F(S3)。更新优先集合,S2仍为食物节点,S3退出优先集合。如果在S1处还有其他邻居处的食物浓度大于γ,FM仍以式(6)的概率选择前进方向。
算法1:FM的觅食行为
车辆S0、鱼群消息FM、优先集合P、S0邻居集合N(
$S_1,S_2, \cdots,S_{\!j}$ )、拥挤因子δ、食物浓度和拥挤因子阈值γ、σfor(Sj∈N)
if(F(Sj)>F(S0)&&F(Sj)>γ)
Sj加入P
else if(F(Sj)<γ)
Sj退出P
end if
end for
if(P≠φ)
以式(6)给出的概率游向某一邻居Sj
else if(δ<σ)
停留在S0处
else
携带当前车辆信息,以式(8)给出的概率游向某一邻居Sj
end if
-
跟随行为描述的是鱼类会跟随已找到食物的伙伴的轨迹的现象。聚集行为则是指鱼类会聚集在食物浓度较高的区域,其本质也是跟随行为导致的。因此,本模型将两种行为统一称作跟随行为。
如前文所述,FM在S1处通过觅食行为成功找到一个或多个食物节点后,会将食物节点添加到优先集合中并为其设置拥挤因子δ。对于后续到达S1处的FM,直接根据优先集合判断前进方向。在优先集合中,元素是伙伴已选择的方向,往往食物浓度比较高,且元素数量远小于邻居表,因此,跟随行为在提高搜索效率的同时,可以让后续FM更快地发现食物节点。如算法2所示,如果优先集合里有一个或者多个方向可供选择,FM会根据式(6)给出的概率来选择前进方向。如果优先集合中没有元素,表示之前没有伙伴找到食物,无法跟随,此时执行觅食行为。
算法2:FM的跟随行为
车辆S0、鱼群消息FM、优先集合P、S0邻居集合N(
$ S\!_1,S\!_2, \cdots, S\!_j $ )if(P≠φ)
FM以式(6)给出的概率游向某一邻居Sj
else
执行觅食行为
end if
-
为更好地适应VANET动态变化的网络环境,本模型在鱼群优化的基础上增加一个仿生学行为:扩散行为。该行为描述的是在食物浓度较高的区域内,食物由于鱼群的聚集很快被消耗殆尽后,鱼群扩散并重新寻找食物的行为。本模型中,食物节点在未来一段时间内会承载当前区域内大部分的中继任务,导致设备负载增加和传输效率降低。另外,当网络拓扑改变时(邻居车辆驶离食物节点的通信范围),食物节点在接收消息后无法转发,也会导致传输成功率降低。在这些情况下,聚集的FM认为食物被消耗殆尽,执行扩散行为并重新寻找食物。周围节点收到扩散的FM后获知该食物节点已失效,将更新自身优先集合并重新选择业务消息的中继。
算法3:FM的扩散行为
车辆S0、鱼群消息FM、优先集合P、食物浓度阈值γ
if(F(S0)<γ)
聚集在S0处的所有FM携带S0的状态执行觅食行为并扩散
end if
-
基于3.1节中的VANET系统模型,本文的路由算法的主要步骤如下:当通信需求产生时,源车辆S0首先判断目的车辆D是否在通信范围内,若是,则直接将消息发给目的点,路由结束;反之,执行以下步骤进行路由。
1)选择第一代候选节点:为使消息每一跳传输都在向目的节点靠近的方向上进行,当某邻居节点Sj与目的节点之间的距离
${\rm{dis}}_{{{S}}_{{{j}}}{{\rm{D}}}}$ 小于源节点和目的节点之间的距离disSD时,将Sj添加到第一代候选节点集合Q($ S\!_1,S\!_2,\cdots $ )中。若Q为空,为避免消息向远离目的节点的方向传输而出现回传和成环的问题,将直接丢弃数据包;若Q不为空,执行步骤2)。2)选择第二代候选节点:为使消息传输经过的跳数尽量小,每次选择时应满足以下两个原则:1)邻居节点Sj和目的节点D之间的距离
$ {\rm{dis}}_{{{S}}_{{{j}}}{{\rm{D}}}} $ 尽量小。如图5所示,S0向D发送消息时将选择S2以避免增加不必要的跳数;2)源节点S0往邻居节点Sj的方向S0→Sj与源节点S0往目的节点D的方向S0→SD之间的夹角ω尽量小。如图6所示,S0在向目的车辆D发送消息时,将在通信半径范围内选择S2或者S3,从而避免传输方向扩散和偏离目标车辆。本文综合考虑
$ {\rm{dis}}_{{{S}}\!_{{{j}}}{{\rm{D}}}} $ 和ω两个因素,使用TOPSIS方法[21]从集合Q(S1,S2,···,Sm)中选出第二代候选节点集合T(S1,S2,···,Sn)(n<m)。TOPSIS是一种通过对现有的对象进行相对优劣评价而逼近理想解的排序法。假设集合Q中有m辆车,各车辆的距离夹角参数如表2所示。节点 距离 夹角 S1 ${\rm{dis}}_{S\!_1{\rm{D}}} $ ω1 S2 ${\rm{dis}}_{S\!_2{\rm{D}}} $ ω2 $\vdots $ $\vdots $ $\vdots $ Sm ${\rm{dis}}_{S\!_m{\rm{D}}} $ ωm 对于
${\rm{dis}}_{S\!_j{\rm{D}}} $ 和ω两个评价指标,建立如下特征矩阵:对特征矩阵进行规范化处理,利用式(9)计算得到规范化矩阵元素rij:
为以上两个评价指标分别设置权重τ1和τ2,由式(10)计算权重规范化矩阵元素:
式中,
$ {i = 1,2, \cdots ,m\text{;}j = 1,2} $ 。根据权重规范化矩阵,计算每个指标的最优解和最劣解。由于距离更短和夹角更小的目标更优,因此,权重规范化矩阵中各列的最小值即为最优解:
式中,
$ {i = 1,2, \cdots ,m} $ 。可以根据式(12)计算出集合Q中车辆的两个评价指标与其对应的最优解和最劣解的距离:
式中,
$ {a_i^* \in {A^*}\text{;}a_i^ - \in {A^ - }} $ 。集合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的通信半径内)
for(Sj∈N)
if(
${\rm{dis}}_{S\!_j{\rm{D}}} $ <${\rm{dis}}_{S\!_0{\rm{D}}} $ )将Sj加入集合Q
end if
end for
if(Q≠φ)
基于TOPSIS方法,从集合Q中选出候选节点集合T
else
丢弃MSG,算法结束
end if
if(T∩P≠φ)
在Si∈T∩P中选择F(Sj)max的邻居Sj作为MSG的中继
else
在所有邻居中选择F(Sj)max的邻居Sj作为MSG的中继
end if
else
将MSG直接交给目的车辆D
end if
3.1. VANET系统建模
3.1.1. 觅食行为
3.1.2. 跟随行为和聚集行为
3.1.3. 扩散行为
3.2. 路由算法描述
-
本文在SUMO[16, 22-23]上建立道路车辆模型,使用Veins[22-23]框架在网络仿真平台OMNET[22-23]上搭建实验环境。表3给出了实验中使用的主要参数。仿真实验采用图7中所示的2 km × 2 km地图[15]。
-
为了评估算法性能,实验将本文算法FSR与基于仿生学的VANET路由算法PASRP[17]、URAS[19]及经典的VANET路由算法GPSR[13]进行了对比。
-
图8展示了消息平均到达时延随车辆密度变化的结果。这部分实验中的控制业务消息产生速率为10(个/s)。仿真结果显示,本文算法FSR优于其他3种对比算法。总体而言,随着车辆密度增加,时延呈上升趋势。这是因为更多的消息能够到达目的点,不会在中途被丢弃。另外,在车辆密度低时,PASRP的平均到达时延略高于GPSR,这是因为PASRP需要等待探测消息的回馈才能为业务消息规划路由。
参数名 参数值 仿真范围/km 2×2 车辆通信半径/m 250 MAC协议 IEEE802.11p 仿真时间/s 4000 车辆移动速度/km·h−1 50 基础信标消息周期/Hz 2 信标消息大小/bytes 20 鱼群消息产生周期/Hz 5 鱼群生存周期/hops 20 鱼群消息大小/bytes 28 业务消息大小/bytes 128 业务消息流数/对 24 图9展示了消息平均到达时延随业务消息产生速率变化的结果。这部分实验中的控制车辆密度为75辆/km2。仿真结果显示,本文算法FSR优于其他3种对比算法。随着业务消息的增多,时延呈递增趋势。
以上两组实验结果都展示了FSR在降低VANET的消息传输时延方面的性能最优,这得益于基于鱼群优化的设计。
-
图10展示了控制业务消息产生速率为10个/s时,消息到达率随车辆密度改变的实验结果。FSR的消息到达率略高于其他对比算法。这是因为FSR引入了鱼群优化模型,节点可以动态找到周围传输成功率高的节点转发消息,从而更有效地保证了消息到达率。当车辆密度足够大的时候,FSR的性能略差于PASRP,这是因为PASRP建立了完整路由,能够更好地保证消息到达率。
图11展示的是控制车辆密度为75辆/km2时,消息到达率随业务消息产生速率变化的实验结果。以上两组仿真实验结果显示,FSR能够保证较高的消息传输成功率。
-
通信开销定义为传输一个业务消息所需辅助控制消息的平均字节数。图12展示了控制业务消息产生速率为10个/s时,通信开销随车辆密度变化的情况。总的来说,FSR和PASRP的通信开销高于GPSR和URAS。这是因为FSR需要网络中存在一定数量的鱼群消息,而PASRP则需要发送一定的蛛网探测消息以建立完备的路由。当车辆密度较低时,产生的辅助控制消息较少,成功到达的业务消息也较少。随着车辆密度增加,周期消息与辅助消息增加,成功到达的业务消息增加,此时通信开销会短暂上升。但随着车辆数量进一步增加,成功传输的业务消息增长速率将高于辅助控制消息的增长速率,此时通信开销会呈现递减趋势。
图13展示了控制车辆密度为75辆/km2时,通信开销随业务消息产生速率变化的情况。实验结果显示,FSR与PASRP的开销大致相当。当业务消息数量较少时,FSR的通信开销低于GPSR和PASRP,这是由于此时网络拥塞情况较少,需要的鱼群辅助消息较少。当业务消息数量增多时,网络拥塞情况随之变严重,为了保持传输性能需要的鱼群辅助消息也会增加,此时FSR的通信开销会高于GPSR和PASRP。
以上实验结果表明,本文所提的FSR算法能够在增加少量通信开销的前提下,显著改善VANET中消息到达的平均时延和消息到达率。