基于隐马尔科夫模型的高速公路场景SDVN路由算法

袁 学 松

(1. 安徽机电职业技术学院 互联网与通信学院, 安徽 芜湖 241001；2. 菲律宾科技大学， 马尼拉 0900)

0 前 言

近年来，智能交通系统(intelligent transportation system，ITS)在交通信息化建设中起着越来越重要的作用[1]。车联网(vehicular ad-hoc network，VANET)是ITS的重要组成部分[2-3]，它使用无线通信技术把车载设备、路侧装置(rode side unit，RSU)和Internet连接在一起，实现了交通单元的互联互通。在VANET中，由于车辆终端设备的通信半径有限，导致通过一跳或者多跳将有限车辆连接起来的V2V(vehicle to vehicle)通信范围有限。随着科学技术的发展，V2I(vehicle to infrastructure)通信被广泛应用于城市交通环境中。但在市郊或高速公路场景下，由于融合型RSU较为昂贵，不可能大量部署，导致车辆和RSU的距离较远，超出了通信范围。因此，很多学者研究了V2V和V2I混合通信技术在公路交通管理网络中的应用，使网络的可靠性在一定程度上得以提升[3-4]。

在高速公路场景下，车辆节点和通信设备均采用专用短程通信协议(DSRC)作为标准传输协议。在数据传输过程中，由于车辆节点移动速度快，VANET网络拓扑变化频繁，容易出现隐藏终端或终端失效的情况，导致链路中断。为了顺利通信需要重新发现拓扑，从而导致网络资源被大量消耗，加大了端到端时延。很多文献已对高速公路场景下的车辆协同通信和车辆借助基础设施辅助通信进行了研究。当车辆节点计算路由方案并传输数据时，目标节点可能已经超出传输范围，从而导致节点失效。基于地理位置的路由协议(GPSR)均采用只考虑欧氏距离的贪婪算法，大大减少了路由发现时间。大多数基于多跳广播或单播技术的数据传输均采用该算法进行改进[5]。文献[6]提出了Turbo的转发机制，充分考虑到城郊场景下稀疏网络和稠密网络的情况，分别采用存储转发和偏好转发的方式提高数据传输效率。文献[7]使用曼哈顿距离确定车辆中继传输节点的运动空间，利用马尔科夫决策优化传输路径。文献[8]使用二分图法区分中继节点和目的节点，采用Kuhn-Munkers经典算法进行链路资源分配，解决了资源冲突问题。文献[9]使用LTE技术进行V2V网络资源分配，减少了传输时延，提高了网络的可靠性。文献[10]使用了基于软件定义车载网络(software defined vehicular network，SDVN)的分布式和集中式算法。

上述文献使用各种技术对中继节点进行选择和规划，同时考虑到整个拓扑的资源分配问题。随着5G应用场景的普及，RSU与5G技术相融合，使传输速度加快、带宽逐步加大。但5G融合型RSU的布设成本很高，信号覆盖范围比传统通信小，因此如何在异构网络中选取最优路径是当前的研究热点。本次研究引入SDVN[11]技术，提出了一种基于隐马尔科夫模型(hidden markov model, HMM)的高速公路场景SDVN路由算法。

1 高速公路场景的数据协同传输问题

本次研究假设所有车辆节点都有能够获取地理位置信息的GPS或北斗系统，以及获取车辆自身状态的传感器，统称为车载单元(on board unit，OBU)。

1.1 SDVN环境架构

SDVN环境架构是一种基于SDN思想的VANET通信解决方案，SDVN环境架构如图1所示。网络分为数据面和控制面，其中数据面包括车辆节点、RSU和路侧基站(BS)等。网络中的每个节点周期性地和区域中央控制器交换状态信息。控制器根据获得的状态信息进行转发决策，并将计算出来的路由信息下发给各车辆节点；车辆节点根据决策信息进行数据转发和广播。在SDVN环境架构中，数据面和控制面是完全分离的。车辆节点只需传输2种数据流，一种是周期性的自身状态流，称为上传流；另一种是V2V和V2I的业务数据流，称为业务流。这样车辆节点和RSU就不必维护路由，只需关注业务数据的传输即可。

图1 SDVN环境架构

在经典的GPSR路由协议中，车辆节点通过周期性地发送Hello数据包进行邻居发现。当发现邻居后，进行拓扑规划并传输数据，耗费时间为Δt。在Δt内，由于车辆节点高速运动，导致源节点和目的节点不在通信范围内，进而出现节点路由黑洞问题。根据GPSR改进协议，节点一旦传输失败就会重新发现邻居，如果没有合适的邻居节点便携带转发。使用SDVN技术后，车辆节点只需要根据控制器决策进行数据传输，使Δt大大减少；但由于节点的运动速度和方向不可控，仍会出现隐藏终端和节点路由黑洞问题。SDVN模型下T时刻的数据传输场景如图2a所示。T时刻时，车辆节点A将单播数据传输给车辆节点C的流程为：首先默认本区域内节点已周期性地将自身相关信息传输给RSU，然后RSU通过网络将信息传输给控制器，控制器再计算出本区域的相关拓扑，接着RSU把A的数据发送请求传输给控制器，最后控制器将A到C的数据传输路径(A->B->C)转发给A。这个过程花费的时间为ΔT，SDVN模型下T+ΔT时刻的数据传输场景如图2b所示。由于C超出了A、B甚至RSU的通信范围，导致车辆节点传输失败。当车辆节点发送数据失败时，A会重新发送请求给RSU，进而出现节点路由黑洞问题。因此，控制器要确保节点在数据传输过程中不失效。

图2 SDVN模型下不同时刻的数据传输场景

1.3 SDVN环境下无基础设施情况的节点失效问题

在高速公路场景下，由于基础环境的部署设计和稀疏车阵等问题，节点传输数据时找不到RSU和中继节点，导致数据传输失败。在这种情况下，GPSR协议及其扩展协议使用携带转发技术，节点将携带转发数据直到找到新的RSU或中继节点。SDVN模型下无基础设施情况的T时刻数据传输场景如图3a所示。在稀疏车阵和无RSU的情况下，没有控制器为车辆节点A提供相关拓扑和路由信息，它需要根据传统的GPSR协议进行数据转发，数据被传输至当前通信范围内最远的车辆节点B，A通过中继节点B与D进行通信。A通过发送Hello数据包构建网络拓扑，花费的时间为ΔT，SDVN模型下无基础设施情况的T+ΔT时刻数据传输场景如图3b所示。一旦B超出了A的通信范围，A就会重新发现拓扑，选择路由，甚至进行携带转发，这更增大了网络负担，从而导致节点失效。

图3 SDVN模型下无基础设施下不同时刻的数据传输场景

为了避免出现SDVN环境下的节点隐藏和节点失效等问题，本次研究基于控制器和RSU的强大算力特点，采用HMM预测目的节点位置，加大了端到端的传输效率，减少了网络开销。

2 系统模型与算法描述

车辆可以同时进行V2V和V2I通信。首先，车辆节点A把位置信息(x，y)、速度VA和加速度等信息周期性地发送给RSU；然后，RSU通过光纤链路将数据传输至控制器；最后，控制器汇总所有车辆信息，创建简单拓扑。A按照RSU规划的路线将数据传输给其他节点。当A需要传输的是优先等级较低的数据时，RSU直接将数据发送至控制器，再由其链接到运营商网络。当A需要紧急单播或域内广播时，则需要控制器快速给出回应。

2.1 使用HMM预测车辆节点位置信息

HMM是由一个隐藏的马尔科夫链随机生成的不可观测的运动序列[12]。车辆节点将状态数据周期性地传送至控制器，控制器进行建模，任何视口的车辆状态只与前一时刻的状态有关。

为了预测车辆节点下一时刻的位置信息，假设任何一个车辆节点的状态集合G={g1，g2，…，gN}，时序特征的观测序列W={w1,w2,…,wM}，其中，N为可能状态数，M为可能观测数。 长度为r的状态序列S={s1，s2，…，sr}，对应的观测序列O={o1，o2，…，or}。

节点的状态转移概率矩阵如式(1)所示：

A=[aij]N×N

(1)

aij=P(st+1=gj|st=gi),i,j=1,2,…,N

式中：aij表示在t时刻处于状态gi的条件下，t+1时刻转移到状态gj的概率。

观测概率矩阵如式(2)所示：

B=[bj(k)]N×M

(2)

bj(k)=P(ot=wk|st=gj),k=1,2,…,M,j=1,2,…,N

式中：bj(k)表示在t时刻，处于gj状态下观测到wk的概率。

初始状态概率向量π=[π(i)]N，π(i)表示在时刻t=1时，处于状态gi的概率。因此，HMM可以用三元符号表示为：γ=(A,B,π)。

使用HMM对训练好的数据进行求解，求出最优节点位置序列，预测过程如图4所示，其中αmax(T)表示节点移动概率的分布。

图4 HMM预测示意图

2.2 CMR-SDVN路由算法

集中管理下发路由算法(CMR-SDVN)的核心是首先收集各RSU覆盖范围内所有车辆节点的状态信息，并采用有线光纤等传输方式将信息传输至控制器；再由控制器创建网络拓扑。当车辆节点需要传输信息时，首先将请求发送至控制器，再由控制器计算出安全链路并下发至车辆节点，最后车辆节点根据链路进行数据传输。

本算法选用在高速公路上行驶较为缓慢且车道相对固定的卡车作为辅助节点(伪节点、移动RSU)。首先，控制器收集域内RSU集合D={d1,d2,…,dn}；其次，RSU将域内OBU信息周期性地传送给控制器，形成车辆状态集合E={e1,e2,…,en}、移动RSU集合F={f1,f2,…,fn}。集合D映射集合E和F，形成动态数据库。集合E和集合F中的元素为每个OBU上传标识、速度、加速度、通信功率等车辆信息。CMR-SDVN路由算法中车辆节点周期性状态交流流程如图5所示，RSU处理请求流程如图6所示。

图5 车辆节点周期性状态交流流程图

图6 RSU处理请求流程图

(1) 当车辆节点或者移动RSU节点进入RSU通信范围内时，主动发送Hello包给RSU，当RSU收到Hello包时，记录车辆相关信息并通过光纤传送给当前控制器。控制器将所有信息存入数据库，并记录生存时间(默认值为传输直径与速度的比值)，当生存时间值为0时，自动删除数据库中的节点信息。

(2) 控制器获得数据库中所有值后，综合域内所有车辆节点、移动RSU、RSU来创建网络拓扑，收集信息和创建拓扑的时间为Δt。

(3) 当车辆节点传输非紧急数据时，采取V2I通信，车辆节点只能和当前RSU进行数据通信，并使用控制器连接网络。

(4) 当车辆节点传输紧急数据时，将紧急请求信息传输给当前RSU，由其判断目的节点是否在域内集合E、F中。如果在，则使用HMM预测目的节点下一时刻的位置信息，并判断其能否使用V2V通信；如果能，由于紧急通信不会传输大量数据，则优先使用一跳V2V通信；如果不能，则当判断其在RSU和伪RSU的通信范围内时，计算出最优路由并发送给节点。如果车辆节点超出当前RSU的通信范围，RSU则将请求信息交由控制器处理。

(5) 当控制器收到请求后，再次预测目的节点的位置信息，并使用最近一次创建的网络拓扑，将生成的跨RSU传输路由通过RSU发送给车辆节点。如果连控制器都不能找到一条可达路由，则表示目的节点不在所有RSU的覆盖范围内，请求应答失效。

3 场景仿真实验分析

CMR-SDVN算法的典型应用场景是高速公路稀疏车阵车流。本次研究使用NS-3和SUMO等仿真工具来模拟车辆在高速公路上的行驶状态，通过Matlab软件对CMR-SDVN算法、经典的GPSR算法和使用SDVN框架的改进JRRS[13]算法的性能进行比较分析。为了确保算法的普遍适用性，仿真场景设计了2段公路，第1段为5 km的RSU全覆盖公路，第2段为5 km的RSU半覆盖公路；车辆节点的最大速度为120 km/h。V2V的通信标准为IEEE802.11p(包括车辆与移动RSU的通信)，普通车辆节点的通信半径为150 m，卡车等移动RSU的通信半径为200 m。V2I的通信标准为LET-A，通信半径为500 m。仿真参数设置如表1所示。

表1 仿真参数设置

3种算法丢包率的对比如图7所示。由图7a可知，当车辆节点密度增加时，JRRS算法和CMR-SDVN算法的丢包率远低于GPSR算法。这是因为CMR-SDVN算法是由控制器构建网络拓扑，节点从控制器处获取传输路径，传输更加可靠、稳定，丢包率更低。由图7b可知，当车辆节点密度固定时，所有算法的丢包率都随着车辆节点速度的加快而增加，JRRS算法的丢包率最低。

图7 3种算法丢包率的对比

由3种算法端到端平均传输时延的对比(见图8)可知，由于CMR-SDVN算法采用了HMM对节点位置进行预测，免去了传统算法中每个节点都要通过维护邻居关系来发现拓扑的过程，大大降低了重传率，因此CMR-SDVN算法比GPSR算法和JRRS算法更优。

图8 3种算法端到端平均传输时延的对比

4 结 语

CMR-SDVN算法是一种基于SDVN框架的改进算法，采用HMM预测车辆节点信息，并传输至RSU和控制器，为其路由决策提供参考。仿真实验结果表明，在不同的车辆节点速度和车辆节点密度情况下，CMR-SDVN算法比GPSR算法和JRRS算法的丢包率和端到端平均传输时延更低。但CMR-SDVN算法的RSU布设只考虑到简单环境下的车辆数据传输，暂未考虑拥堵交通流、对向交通车流、立体交通车流等情况，下一步可重点研究这些场景下的车辆节点传输问题。