3D-VANET中基于模糊逻辑和Q学习的拓扑感知路由协议*

郑泽涛，何荣希，周 宇

(大连海事大学 信息科学技术学院，辽宁 大连 116026)

0 引 言

随着汽车保有量不断增长，为提高人们出行的高效性与安全性，智能交通系统(Intelligent Transport System，ITS)应运而生。车载自组网(Vehicular Ad-hoc Network，VANET)由车辆与路边单元(Road Side Unit，RSU)组成，是实现ITS数据可靠交互的关键支撑技术。车辆的快速运动，导致VANET拓扑变化频繁，通信链路更易中断。由于拓扑路由协议在传输数据包前需建立完整路径，因此在VANET中性能较差[1]。与之不同，地理位置路由协议不需预先建立路径，节点可根据本地信息进行路由转发，在VANET中具有较好的性能，已引起业界极大关注。

贪婪周边无状态路由协议(Greedy Perimeter Stateless Routing，GPSR)[1]是经典的位置路由协议，通过选择距离目的节点最近的邻节点进行数据转发。文献[2-4]中的位置路由协议都是针对城市二维场景设计，也称为平面路由协议。伴随着城市现代化建设的不断推进，越来越多地涌现高架桥、立交桥等立体式交通格局。在上述多层道路场景中，由于道路遮挡造成信号衰减，不同层间车辆的传输半径各异，同时不同层的车辆间运动状态差异也较大。而已有平面路由协议并未涉及跨层间节点传输问题，不宜直接用于立体交通场景[5]，因此，很有必要针对网络拓扑变化更频繁的三维场景VANET(3D-VANET)特点，重新设计位置路由协议。

由于城市3D-VANET中往往包含多种道路场景，每种道路场景的网络拓扑都具有不同的特点，不同道路场景之间节点分布和运动差异较大。3D-VANET中应依据道路场景自适应调整信标间隔。

本文针对城市三维场景提出了一种基于模糊逻辑和Q学习的拓扑感知路由协议(Topology Aware Routing Protocol Based on Fuzzy Logic and Q-learning，TARP-FQ)。该协议采用模糊逻辑方法综合考虑网络拓扑与负载信息判断网络情况，动态地调整信标间隔，以平衡邻节点信息准确性与控制开销成本，提高后续路由决策的正确性和有效性。在此基础上，采用Q学习算法对VANET网络进行建模，通过获取的本地信息计算链路质量以及链路质量变化，根据节点间的拓扑变化调整Q学习参数，并结合未来奖励函数灵活选择下一跳转发节点，保证转发链路的可靠性，避免局部最优问题的发生。

1 网络模型

与已有研究[6-8]仅针对单一场景进行路由设计不同，本文所构建的城市三维场景由单层道路、高架道路、立交桥等多种道路构成。假设车辆随机分布在道路上，按照交通规则沿道路行进，而且每种道路上车辆的分布和运动状态呈现不同特点。由于多层道路的存在，车辆拥有两种数据包转发模式，分别为层内转发模式和层间转发模式[9]。层内转发指发送数据包和接收数据包的车辆位于同层道路，而层间转发是指位于不同层道路的车辆进行数据包的收发。由于多层道路之间存在遮挡造成信号衰减，层内转发模式的传输距离r要大于层间转发模式的传输距离r′。所有车辆均配备GPS设备获取自身实时位置信息，装配有符合IEEE 802.11p车联网无线接入标准的车载单元设备(On Board Unit，OBU)进行数据包传输。网络中每个节点通过周期性交换HELLO包获取邻节点信息，并且可以判断其所在的道路。每个交叉路口配备与车辆具有相同通信能力的RSU，每辆车以及RSU均有唯一标识。

2 TARP-FQ协议描述

TARP-FQ主要由基于模糊逻辑的动态信标间隔调整和基于Q学习的路由选择两个模块组成。动态信标间隔调整模块根据收集的节点速度、方向、邻节点数和网络负载信息，通过模糊逻辑处理数据，感知网络拓扑变化情况与网络状态，进而选择合适的信标间隔，为路由选择提供准确的邻节点信息和良好的网络环境。路由选择模块根据链路质量和节点间拓扑变化情况作出最佳路由决策，并完成数据包转发。当车辆携带数据包时，选择抵达临时目的节点最大Q值车辆进行转发。当车辆产生新的数据需要发送或数据包转发至RSU时，结合Q值和RSU信息选取下一个临时目的节点，并继续通过Q值选择节点进行转发。

2.1 基于模糊逻辑的动态信标间隔调整

2.1.1 动态信标间隔

位置路由协议进行路由决策的基础是邻节点列表的准确性，但是拓扑结构的频繁变化将导致邻节点状态信息经常发生改变。节点间周期性交换信标消息是维护邻节点信息的常用方法，VANET采用HELLO包作为信标消息进行交互，节点通过HELLO包获取需要的邻节点信息。

平面场景中由于道路限制与相互约束，车辆之间运动差异较小，采用固定信标间隔策略即可满足网络的需求。而在城市三维场景中，不同道路中的网络拓扑变化情况截然不同，采用较大的固定信标间隔无法保证拓扑快速变化时邻节点列表的准确性，而采用较小的固定信标间隔，由于无线链路资源有限，当网络中存在大量HELLO包时会增加与用户数据包碰撞的概率，造成数据包丢失。因此在城市三维场景中采用固定信标间隔策略会存在一些问题，下面以图1为例加以说明。图中车辆A、B位于S3道路的同向车道，C位于A、B的反向车道，D位于环形高架S4道路，E和F位于单向S1道路，其中A、E有数据包将要发送。图1分别给出了t0、t1时刻的情况。

图1 信标间隔大小对邻节点信息准确性的影响

(1)假设t0时刻所有车辆第一次广播HELLO包，当选取较小的固定信标间隔t2-t0时，可以捕获C、D即将离开A通信范围的信息，进而降低其转发权重，而当选取较大的固定信标间隔t3-t0时，实际上t3时刻C、D已离开A通信范围，但仍作为潜在的下一跳转发节点存在于A的邻节点列表中，不能精准捕获网络拓扑的变化，会导致次优甚至错误的路由决策。

(2)在S1道路中，受道路和车辆间的相互约束，网络拓扑变化较慢，此时较长的固定信标间隔即可保证E邻节点信息的有效性。如果选择较短的固定信标间隔，则会引入较大的网络开销，浪费信道资源。

可见3D-VANET中采用固定信标间隔策略无法满足高性能路由需求，因此本节设计了动态信标间隔调整策略，引入模糊逻辑方法，可根据局部网络拓扑变化以及网络负载情况动态调整信标间隔。

由于3D-VANET是一种动态变化的网络，很难通过具体的数学公式来描述网络的变化情况，而模糊逻辑作为一种类似于人类推理的方法，采用非数字语言变量进行描述，可以更精确、动态地自适应优化参数，因此本节通过模糊逻辑方法处理不精确的信息，改善决策，提高性能。模糊逻辑一般包括三个步骤：模糊化输入、模糊化处理和解模糊。输入步骤将数值转化为模糊语言，采用IF/THEN的模糊规则对其进行处理，最后通过解模糊以数值形式输出。

2.1.2 模糊化输入与处理

TARP-FQ的模糊化输入考虑4个评价指标，即速度标准差、行进方向数、邻节点数量变化率和网络负载得分。速度标准差和行进方向数可以反映出车辆运动状态的差异，邻节点数量变化率则可以看出当前信标间隔是否可以准确捕获网络拓扑的变化，最后根据当前网络负载情况衡量可接受的网络开销，当网络负载较大时增大信标间隔以减轻网络负载压力，实现信息准确与网络开销之间的平衡。

当节点启动HELLO包广播机制时，首先通过模糊逻辑方法处理节点速度标准差、行进方向数、邻节点数量变化率、网络负载得分4个参数以确定信标间隔，并将计算出的下一次发送时间写入即将发送的HELLO包中。

(1)速度标准差

在平面场景中，位于相同道路的车辆，其运动相互影响，相对速度往往较小，网络拓扑较为稳定。在三维场景中VANET具有层间转发模式，因此还需要考虑当前层道路之外的车辆。由于不同道路中交通灯设置、车流量大小等因素不同，跨层车辆之间相对速度较大，网络拓扑变化较快，为反映车辆之间运动速度的差异性，采用速度标准差来衡量相对移动性大小。网络中车辆速度标准差Sc定义为

(1)

(2)行进方向数

在平面场景路由协议的研究中，相邻车辆仅沿着道路双向运动，而在城市三维场景中由于高架、立交桥等道路形式的存在，相邻车辆可能存在多个行进方向。当相邻车辆行进方向越多时，网络拓扑的变化将越频繁。为便于计算，定义8个车辆行进方向，如图2所示。图中c为车辆当前位置，cc′为当前车辆的行进方向。

图2 节点行进方向

节点的邻节点列表中车辆节点行进方向数dirnum计算如下：

(2)

当邻节点列表中有节点行进方向为diri时，将diri值置1，否则为0。

(3)邻节点数量变化率

在平面场景中，网络较为稳定，车辆邻节点列表变动较小，而在三维场景中，除单层道路外，还包含多种道路结构，不同的道路中网络拓扑变化情况截然不同。因此引入邻节点数量变化率来表示当前信标间隔捕获拓扑变化的能力。邻节点数量变化率Nio定义为

(3)

式中：Nneighbour为邻节点列表中当前邻节点数,Nin和Nout分别为一个信标间隔时间内新增节点数和离开节点数。当邻节点数量变化率较大时，说明当前信标间隔设置过长，不能及时捕获网络拓扑的变化；反之则说明当前网络较为稳定，可以适当增大信标间隔以减少网络开销。

(4)网络负载得分

大量HELLO包的广播会增大网络负载，导致无线共享信道更加拥塞，降低了数据包传输效率。因此在网络负载较重时，可以通过增大信标间隔来减少节点广播HELLO包的数量。为此，引入平均负载得分Laverage来衡量网络负载状态，其定义为

(4)

式中：n为当前车辆邻节点数，Lscore-i为通过式(16)计算得到节点i的负载得分，i=0表示当前车辆节点。

在模糊化过程中，需要借助模糊隶属函数对输入因子进行处理。模糊隶属函数是一种用于表征模糊集合的数学工具，可以利用模糊集合根据实际网络情况对指标间的相似程度进行度量。利用模糊集定义四个指标：速度标准差Sc{小、中、大}、行进方向数dirnum{少、多}、邻节点数量变化率Nio{低、中、高}和网络负载得分Laverage{低、中、高}。隶属函数采用三角形函数和梯形函数，如图3所示。

图3 模糊逻辑输入参数隶属函数

2.1.3 解模糊输出信标间隔

对输入因子进行模糊处理之后，需要根据模糊逻辑准则使用IF/THEN规则进行模糊逻辑推理，TARP-FQ的模糊逻辑部分准则如表1所示，其中模糊评价分为{很长、长、较长、中等偏长、中等偏短、较短、短、很短}8个等级。

表1 模糊逻辑部分准则示例

以表1中第一条规则为例，IF车辆速度标准差大，行进方向数多，邻节点变化率高，网络负载得分高，THEN采用很短的信标间隔。为得到确切的解模糊输出值，需要利用输出隶属函数对得到的若干模糊评价进行转换，TARP-FQ采用的输出隶属函数如图4所示，使用重心法求出解模糊的输出值。定义得到的输出值为信标间隔因子σbeacon，由式(5)计算得出信标间隔大小ΔtB。

图4 模糊逻辑输出隶属函数

ΔtB=Δtmax-(Δtmax-Δtmin)×σbeacon。

(5)

式中:Δtmax、Δtmin分别表示网络内设置的最大信标间隔和最小信标间隔。

2.2 基于Q学习的路由选择

2.2.1 Q学习算法建模

学习环境G：整个网络作为智能体的学习环境。

主体智能体Agent：传输数据包的节点。

状态空间S：除当前智能体节点之外的所有节点组成状态空间。

瞬时奖励R：当前智能体节点通过一次动作从环境中获得的瞬时奖励。

动作Actions：选择一个邻节点转发数据包。

网络中车辆之间通过HELLO包交互状态信息，在每一个状态和可能的动作之间建立一张Q值表，维护每一个“状态-动作”对的评价值——Q值，实现智能体节点在环境中不断地试错并调整最优动作。Q值表记录着当前节点通过邻节点抵达所维护目的节点的Q值大小。

根据文献[10]可将Q学习算法更新公式表示为

(6)

式中：c为当前节点，x为c的邻节点，d为目的节点，N(x)为x邻节点的集合，y为x邻节点集中的一个节点，α(0<α<1)为学习率，γ(0<γ<1)表示折扣因子。车辆在转发数据包时将每个相邻的RSU作为候选的临时目的节点，因此Q值表中维护的是通过邻节点抵达每个相邻RSU的Q值大小。

2.2.2 Q学习参数设计

本小节根据VANET中链路质量、链路质量变化以及是否可以抵达目的节点三个方面对Q学习算法中参数进行设计。

当前节点接收到邻节点的HELLO包时，首先计算折扣因子γ，其值为

γ=γpreγscore。

(7)

式中：γpre为预设常数(0<γpre<1)，根据多次仿真实验，将γpre设置为0.85；γscore表示链路质量得分，通过可替代度、链路维持时间和邻节点负载状态来衡量节点间传输数据包的可靠性。在选择下一跳节点进行转发时，要尽量避免选择可替代度低、即将离开通信范围或者负载过大的节点。本节采用调和平均数计算链路质量，调和平均数相较于算数平均数可以更灵敏地反映较小值的影响，避免某个网络参数过差而产生的瓶颈效应。γscore的计算公式为

(8)

式中：AL、SLET和Lscore分别代表可替代度、链路维持时间得分和邻节点负载得分。

(1)可替代度

在数据包转发过程中，如果当前链路失效，则需要由备用链路对数据进行转发。因此，有效的候选链路数量是影响链路稳定性的重要因素之一。在三维场景中，由于跨层传输半径减小以及邻节点所处道路的不同，拥有的候选链路也会随着所选择转发节点的改变而改变。为此，本节引入有效候选节点与可替代度两个概念。

有效候选节点定义为所选择转发节点的邻节点列表中可以进一步抵达目标RSU的节点。可替代度则表示拥有的有效候选节点数量可以确保数据转发可靠性的程度，定义为

(9)

式中：N表示所选择转发节点的邻节点数；当节点j为有效候选节点时，ali=1，否则为0；h为常数，根据多次仿真设置为3，即当有3个及以上有效候选节点时有充足的候选链路用于数据转发。

(2)链路维持时间

基于距离贪婪的转发策略倾向于选取距离目的节点最近的节点转发数据包，但所选节点往往位于通信距离边缘。在数据包进行传输时，所选节点可能已经离开通信范围，造成链路断开。VANET中车辆节点运动会受到道路和交通规则等限制，在短时间内的运动状态具有一定的可预测性。因此可以通过车辆运动状态预测节点之间链路维持时间，从而选择一条更稳定的链路进行数据包转发。

文献[11]设置的场景中船舶可以朝任意方向运动，通过传输距离、速度、位置和运动方向预测船舶之间的链路维持时间，因此可借助其方法进行计算。值得注意的是，跨层传输时由于道路遮挡，最大传输半径会减小。由于道路高度对最大传输距离产生的影响远小于信号衰减，可忽略不计。假定节点i与节点j在彼此通信距离Rij之内，(xi,yi)、(xj,yi)，vi、vj与θi、θj分别表示节点位置坐标、行进速度与前进方向，节点间链路维持时间LETij可以表示为

(10)

式中:

a=vicosθi-vjcosθj，

(11)

b=xi-xj，

(12)

c=visinθi-vjsinθj，

(13)

d=yi-yj。

(14)

较长的链路维持时间对链路稳定性影响较小；反之，链路发生断开的可能性大大增加。因此本文采用链路维持时间得分SLET来直观衡量链路维持时间对链路质量的影响。链路维持时间得分SLET表示为

(15)

式中：m和k为常数，m越小，得分SLET上升越快。链路维持时间得分SLET将范围在(0,+∞)的链路维持时间映射到[0,1]的得分之上。链路维持时间越长，得分变化越小且越接近1；但当链路维持时间较小时，得分随链路维持时间的改变有明显变化。当链路维持时间小于常数k时，得分为0，即认为链路维持时间小于k时链路将十分不稳定。根据多次仿真实验，本文设置m=10，k为邻节点的信标间隔。

(3)负载信息

邻节点的负载状态同样是影响链路质量的关键因素之一。当有数据包进行传输时，一旦网络中所有节点均使用相同的转发路径，一段时间后大量数据包在此条路径中传输会造成节点负载过大。当节点的负载较大时可能会导致较大的拥塞概率，降低网络吞吐量[12]。

信道闲时比率和自身节点缓存剩余容量情况可以反映出节点的负载状态，因而可定义节点负载得分Lscore为

Lscore=ηI+(1-η)Q。

(16)

式中：η∈(0,1)为权重因子，用于调节信道闲时比率和自身节点缓存剩余容量情况对节点负载得分的影响；I为信道闲时比率得分，可定义为

(17)

式中：φ为大于π的常数，l表示信道闲时比率。在VANET中，IEEE 802.11p协议基于CSMA/CD，可以通过对信道状态进行监听，获取信道的忙闲状态。信道闲时比率表示在给定时间T内节点感知信道为空闲状态时间所占的比例。假定信道每隔ε时间段进行一次监测，则信道闲时比率l的可定义为

(18)

节点缓存剩余容量得分Q定义为

(19)

式中：q表示节点自身节点缓存剩余容量情况，qmin、qmax分别为最小阈值与最大阈值。q越小，表明节点当前节点缓存剩余容量越少，即缓存队列占用越多，更容易造成拥塞，其值为

(20)

式中：qavg表示在一个信标间隔时间内节点平均缓存剩余容量，C为节点缓存列队的总容量大小。

(3)学习率

学习率决定更新函数的更新速度，反映了Q学习算法对动态环境的适应能力，过大的学习率可能会使Q值因为节点间较小变化产生很大波动；但如果学习率过小，则Q值不能及时反映节点间链路的真实状态。因此可以通过动态调整学习率适应节点间不同的拓扑变化情况，可定义α为

(21)

网络中每个节点都维护着通过邻节点可以抵达的RSU的Q值。当RSU在节点c通信范围内时，节点c的奖励值由瞬时奖励R组成，即

(22)

式中：NRSU表示RSU的一跳邻节点集。当节点c为RSU一跳邻节点时，瞬时奖励R为1，其余情况为0。

网络中每一个节点通过式(6)更新Q值，当距离目标RSU跳数越少、链路质量越高时，最终得到的Q值越大，节点通过选择最大Q值节点进行转发。

2.2.3 RSU选择

当源节点有数据包要发送或RSU接收到数据包时，需要选择下一个临时目的节点。下面以图5为例加以说明。

图5 RSU选择

S1、S2道路上的车辆均维护着抵达相邻RSU(RSUA、RSUB和RSUC)的Q值。假设车辆A有数据包要发送，首先在相邻RSU中选择得分S最高的作为第一临时目的节点，进而选择相应Q值最大的车辆转发数据包。当RSU接收到数据包时，根据得分S在其相邻的RSU中继续选择下一个临时目的节点。当目的车辆位于当前RSU与相邻RSU连通的路段上时，向相邻RSU转发数据包直至抵达目的车辆。得分S的表达式为

(23)

di=min[|yi-yj|+|xi-xj|]，j=0,1… 。

(24)

式中：(xi,yi)、(xj,yj)分别表示RSUi和RSUj的地理位置。当数据包位于RSU时，为保证数据包朝着距离目的节点更近的方向传输，di要满足

di=max[|ynow-yj|+|xnow-xj|]，j=0,1… 。

(25)

式中：(xnow,ynow)为当前RSU的地理位置。

根据式(23)可知，当Q值越大、曼哈顿距离越小时，得分S越大。

3 仿真与分析

3.1 仿真设置

利用VanetMobisim和OPNET平台搭建了3 000 m×4 000 m×10 m的城市3D-VANET仿真场景，对TARP-FQ、QTAR[4]、FL-DGR[3]、ITSR[9]、GPSR[2]五种路由协议性能进行仿真对比，MAC标准为IEEE 802.11p。仿真场景由单层单向车道、单层双向车道、双向高架车道以及环形高架车道组成，仿真性能指标包括包投递率(Packet Delivery Ratio，PDR)和平均端到端时延(Average End-to-end Delay，AED)。其余主要仿真参数如表2所示。

表2 仿真参数

3.2 PDR性能

图6所示为三维场景中采用动态信标间隔和固定信标间隔(1 s、3 s和5 s)时TARP-FQ协议的PDR随节点数变化的情况，可以看出，动态信标策略的平均信标间隔始终大于3 s(信标间隔越大，控制开销越小)，但其PDR却远高于采用3 s固定信标间隔的PDR，接近于1 s固定信标间隔的PDR性能(节点数大于400时，动态信标策略的PDR还略优于1 s固定信标间隔)。这是因为采用基于模糊逻辑的动态信标间隔调整策略时，节点间拓扑变化较小时，采用较大的信标间隔即可保证数据的可靠传输，而当网络变化加剧时，通过缩小信标间隔来获得更精确的邻节点信息，提高包投递率，因此其整体性能优于采用固定信标间隔。

图6 不同信标策略的包投递率

图7对比了城市三维场景中五种路由协议的PDR性能，可看出，当车辆数小于350时，五种协议的PDR随车辆数增加明显增大，原因在于网络的连通性随着节点密度的增加而增高；但当节点数大于350时，随着节点数增多，网络分区现象减少，而信道发生冲突的可能性逐渐增大，五种协议的PDR趋于平缓甚至略有降低。同时从图7可以看出，GPSR、ITSR的PDR小于其他三种考虑链路质量的路由协议。这是因为基于距离贪婪转发的路由协议容易采用位于通信范围边缘和节点状态较差的车辆转发数据包，会造成数据包丢失。同时，从图中可看出采用Q学习算法的路由协议(TARP-FQ和QTAR)在网络连通性较低时也能够获得较高的PDR。这是因为Q-learning算法可以根据未来奖励选择全局最优策略，避免了跨层传输时局部最优问题的发生。另外，由于TARP-FQ协议根据链路变化情况动态调整学习率，根据网络拓扑变化调整信标间隔，因此以较低的网络开销成本获取了最高的PDR。

图7 不同路由协议的包投递率

3.3 AED性能

图8对比了不同路由协议的AED性能，可以看出五种协议的AED均随节点数增多不断增大。这是因为随着节点数增多，网络连通性增大，数据包可以传输到更远的节点。同时，节点数的增加可能会造成网络拥塞，也会增大网络时延。从图8中还可以看出ITSR与GPSR具有最小的AED，原因在于两个方面：首先两者为基于距离贪婪转发的路由协议，总是选择距离目的节点最近的邻节点转发数据包，所经过的中继节点数目最少；其次，由于在转发过程中，其丢失数据包的可能性高于其他三种协议，尤其是源节点与目的节点距离越远时，数据包成功接收的可能性越小。由于ITSR是针对三维场景设计的路由协议，考虑了跨层传输通信距离减少的特点，大多数情况下AED略优于GPSR。FL-DGR协议仅考虑了当前节点与邻节点之间的链路状态，而TARP-FQ、QTAR考虑了未来奖励做出全局最优决策，因此相比于FL-DGR拥有较低的AED。同时，TARP-FQ根据网络拓扑变化情况动态调整信标间隔，有利于获取更精准的邻节点信息，其AED小于QTAR。

图8 不同路由协议的平均端到端时延

4 结 论

本文针对城市3D-VANET中道路多样性的特点，设计了一种基于模糊逻辑和Q学习的拓扑感知路由(TARP-FQ)协议。该协议采用模糊逻辑方法判断网络拓扑变化情况以及网络负载状态，动态选择合适的信标间隔大小，解决了传统路由协议在网络频繁变化时节点信息不准确、网络拓扑稳定时浪费信道资源的问题。另外，还通过Q学习算法对VANET进行建模，在不同的网络环境中根据链路质量和链路变化调整路由决策，同时结合未来奖励避免发生局部最优问题。仿真结果表明，TARP-FQ协议有利于减少网络开销，降低平均端到端时延和提高包投递率。