一种基于SDN的车联网协作传输算法

王 雄 唐 亮 卜智勇 ,3 俞 凯

1(中国科学院上海微系统与信息技术研究所 上海 200050) 2(中国科学院大学 北京 100049) 3(上海瀚讯无线技术有限公司 上海 200335)

一种基于SDN的车联网协作传输算法

王 雄1,2唐 亮1,3卜智勇1,2,3俞 凯1,3

1(中国科学院上海微系统与信息技术研究所 上海 200050)2(中国科学院大学 北京 100049)3(上海瀚讯无线技术有限公司 上海 200335)

在车联网中，利用车与车协作传输可以提高车与基础设施的传输速率。针对车联网中协作传输的中继选择和资源复用问题，提出一种基于SDN的中心式协作传输算法。首先，车辆通过控制信道发送传输请求和状态信息到基站；然后，基站根据收集的车辆信息选择中继车辆和分配资源，并将调度结果通过控制信道广播；资源调度过程采用启发式算法求解，有效地降低了运算复杂度。仿真结果表明所提出的算法可以大幅度提高数据传输速率，提升网络吞吐量。

SDN 协作传输 资源调度 车与车通信 车与基础设施通信

0 引 言

车联网VANET(Vehicular Ad-hoc NETwork)技术作为智能交通系统中的关键技术成为近年来学术界和工业界的研究热点[1-2]。利用车联网中的车与车V2V(Vehicle to Vehicle)和车与基础设施V2I(Vehicle to Infrastructure)通信可以提供包括智能驾驶、交通调度等在内的应用，为人们出行提供更好的体验。随着LTE-A、802.11p，以及WiMAX等通信技术的普及，使得泛在地为车辆提供互联网接入成为可能。但是当车辆与基础设施距离较远时，V2I通信的链路速率将大幅度下降。而协作传输技术可以减小链路的通信距离，以提升系统容量。因此不少研究者提出使用V2V协作V2I的数据传输[3]。

车联网的网络拓扑往往是动态变换的，因此在车联网中使用协作传输，需要实时地选择中继和分配时频资源。不少文献针对车联网中协作传输的中继选择问题做出了研究[4-6]。文献[4]提出使用欧几里得和曼哈顿距离确定中继选择的行为空间，再利用马尔科夫决策过程的动态优化模型得到选车方案。文献[5]设计了一种分布式的协作传输MAC协议，利用最大独立加权图理论从待选中继车辆集合中选出最优中继。文献[6]针对传统中继选择技术复杂度过高问题，提出一种仅利用源节点和各中继节点之间的信道状态信息选择最佳中继的算法，从而降低了系统开销和运算复杂度。

文献[7-10]对协作传输中的资源分配做出了研究。文献[7]将中继集合和目的车辆集合划分为二分图，再利用Kuhn-Munkres算法获得V2V和V2I的链路分配方案。文献[8]将协作传输中的链路调度和资源管理建模为二维多决策背包问题。文献[9]针对V2V复用V2I资源场景，提出两个基于干扰图的算法解决系统的资源复用问题。文献[10]借鉴了LTE中的D2D技术用于V2V资源复用，将带延时和可靠性限制的车联网资源调度建模为混合整数线性规划问题。

上述关于车联网协作传输的文献，多数侧重于单独研究中继选择或资源分配，文献[7-8]同时考虑了中继选择和资源分配，但是资源分配时并未考虑资源复用。而资源复用可以进一步提升系统容量和频谱效率，与中继选择相互影响，只有同时考虑两者才能最大化系统容量。同时由于在5G未来场景中包含LTE-A和VANET等异构网络，在核心网侧通过SDN可以完成网络管理和资源分配。因此为了进一步提升车联网系统容量，本文联合考虑中继选择和资源复用，基于SDN[11]架构提出了一种中心式车联网协作传输算法。

1 系统模型和问题定义

本文参考了文献[7]中所描述的车联网协作传输场景，并且考虑资源复用，重新定义了系统模型和资源调度问题。

1.1 系统模型

如图1所示，本文考虑在高速公路场景下，N个车辆在LTE-A基站BS(Base Station)覆盖范围内向BS请求数据。车与车之间可以通过V2V通信，同时车与BS之间可以通过V2I通信。考虑在V2I下行传输过程中，信道条件较差的车辆可以利用信道较好的车辆作为中继，通过V2V协作传输。因此车辆可以通过V2I直接传输和V2V协作传输两种方式从BS获取信息。

图1 高速公路下的V2I和V2V

(1) 直接传输

在LTE-A网络中，系统的时频资源被划分为资源块RB(Resource Block)，假设系统共有KB个RB，简化分析，采用轮询RR(Round-Robin)调度，则根据香农公式车辆i的V2I链路可实现速率为：

(1)

(2) 协作传输

当前车载设备往往具有多种网络接入能力，因此当车辆与BS之间信道条件较差时，可以利用另一个与BS具有较好信道的车辆作为中继，利用LTE-A带外频率转发数据。本文利用专用短程通信DSRC(Dedicated Short Range Communication)5.9 GHz的频段以广播的方式进行V2V协作传输。为了便于描述，将目的车辆标识为DV，中继车辆标识为RV。DV通过协作传输从BS获取数据，需要包含V2V和V2I通信链路。假设采用解码转发DF(Decode and Forward)方式中继，则协作传输的可实现数据速率为：

ηB,i,j=min{ηB,i,ηi,j} 1≤i,j≤Ni≠j

(2)

其中:ηi,j为第i个车辆到第j个车辆之间V2V链路速率。假设有KV个RB通过轮询方式分配给L条V2V链路，则ηi,j表示为：

(3)

为了高效合理地分配资源，本文基于SDN架构采用中心控制的方式进行调度。SDN是一种将控制层和数据层分离的技术，通过调度器集中管理和调度网络资源。本文利用基站作为调度器，具体调度过程如下：

(1) 车辆和基站通过控制信道发送探针信号，车辆根据接收的信号更新信道状态信息CSI(Channel State Information)。

(2) 车辆将传输请求、CSI以及GPS信息发送到基站，基站根据接收的信息执行调度算法以获取调度结果。

(3) 基站通过控制信道广播调度结果，车辆根据调度结果传输数据。

1.2 问题的形式化

在上述的车联网场景中同时存在直接传输和协作传输，因此增加了资源调度的复杂度。本小节针对上述场景中联合考虑中继选择和资源复用的调度问题进行形式化描述。

1) 相关定义和约束

首先定义车辆集合为V={V1,V2,…,VN}，V2I直接传输的车辆集合为VI={IV1,IV2,…,IV|I|}，中继车辆集合为VR={RV1,RV2,…,RV|R|}，目的车辆集合为VD={DV1,DV2,…,DV|D|}，集合间关系满足V=VI∪VD,VI⊇VR。

考虑车辆的负担和资源复用，对于车辆的协作方式作以下约束：

约束1一个RV只能服务于一个DV。

约束2一个DV只能选择其通信范围内的一个车辆作为其中继。

约束3同一车辆不能同时作为RV和DV。

约束4每个RV具有一个固定的干扰距离dInterfere，处于RV干扰距离外的V2V链路可以复用同一资源，属于同一独立非冲突子集。

约束5不同独立非冲突子集使用不同的V2V资源。

约束6当协作传输速率小于或等于直接传输的速率时，采用直接传输。

2) 问题形式化

1≤i,j≤Ni≠j|S|≤KV

(4)

(5)

定义系数矩阵A={ai,j|ai,j∈{0,1}}N×N，ai,j=1表示第i个车辆协作第j个车辆发送数据，矩阵B={bk|bk∈{0,1}}N，bk=1表示第k个车辆使用直接传输。则系统总的吞吐量可以表示为：

(6)

约束1-3可以表示为：

(7)

(8)

以最大化吞吐量为目标，最终可以得到联合考虑中继选择和资源复用问题的数学表达形式：

(9)

据目前所知，要获得式(9)问题的最优解，仅能通过遍历搜索。具体的遍历方法如下：

最终可以得到，获取最优解的遍历次数上界为：

(10)

由式(10)可知，通过遍历搜索求解问题式(9)的最优解需要非确定性多项式NP(Non-deterministic Polynomial)的运算复杂度。因此，本文提出一种启发式的求解方法，大幅度降低了运算复杂度。

2 协作传输资源分配算法

针对问题式(9)的超高复杂度问题，本文提出了一个启发式算法，该算法大幅度减小了求解复杂度。

2.1 算法过程描述

本文提出了一个联合中继选择和资源复用的资源调度JRRS(Joint Relay selection and Resource reuse Schedule)算法。JRRS算法核心主要包括集合划分和集合调整两个步骤。

首先是集合划分，迭代地选取当前车辆集合V中信道最差的车辆Vtmp，从当前可选中继集合Vc中获取Vtmp通信范围内距离BS最近的车辆Vnearest作为中继添加至当前V2V子集Si，并从Vc和V中分别删除Vtmp和Vnearest的干扰集合，将Vnearest的干扰集合添加到当前不可用集合Vuseless中，保证本次迭代得到的Si中的链路独立非冲突。重复上述的过程，直到V=∅，若Vuseless≠∅，则Vuseless→V，V→Vc，∅→Vuseless保存Si，继续迭代获取Si+1；否则，结束集合划分，获得V2V非冲突子集的集合S。

然后是集合调整，根据获得的S，分别取前n(1≤n≤i)个非冲突V2V子集组成Sn，计算Sn内所有协作链路的速率，将协作传输速率小于直接传输速率的链路修改为直接传输，并删除该V2V链路，合并元素为空的非冲突子集，计算并记录获得最大系统吞吐量时的链路分配方案。

JRRS具体过程的描述如下：

1) 车辆通过控制信道，将CSI、GPS位置信息以及传输请求发送给BS。BS根据请求，初始化可选中继集合和车辆集合Vc=V={V1,V2,…,VN}，并初始化第一个V2V独立子集Si=∅,i=1，初始化当前不可用集合Vuseless=∅。

2) 从V中选择信道条件最差的车辆Vtmp，根据Vtmp的位置信息，BS从Vc获取Vtmp的邻居车辆集合NB(Vtmp)。若NB(Vtmp)中没有比Vtmp距离BS更近的车辆，若Vuseless=∅，则将Vtmp添加到V2I集合VI，并从V删除Vtmp，重新执行2)；若Vuseless≠∅，则将Vtmp添加到Vuseless，重新执行2)。选择NB(Vtmp)中距离BS最近的车辆Vnearest作为协作车辆与Vtmp组成V2V链路。

3) 将得到的V2V链路添加到集合Si中，并从V中删除Vtmp和Vnearest，将Vnearest添加到VI和VR，将Vtmp添加到VD。

4) 将处于Vtmp和Vnearest干扰范围内的车辆集合I(Vtmp)和I(Vnearest)分别从Vc和V中删去。

5) 若V=∅，判断Vuseless是否为空集，若Vuseless≠∅，则Vuseless→V，V→Vc，∅→Vuseless，保存Si，i=i+1，回到2)。

6) 重复步骤2)-步骤5)直到V=Vuseless=∅，得到包含i组V2V非冲突子集的集合S。

7) 分别取前n(1≤n≤i)个非冲突V2V子集组成Sn，计算Sn内所有协作链路的速率，将协作传输速率小于直接传输速率的链路修改为直接传输，并删除该V2V链路，合并元素为空的子集，计算并记录获得最大系统吞吐量时的链路分配方案。

8) BS在控制信道广播链路分配方案，车辆利用分配的资源传输数据。

2.2 算法复杂度分析

上述算法过程的复杂度主要由集合划分部分决定。对于集合划分，每次迭代运行步骤2)-步骤5)至少能划分一个车辆，因此最大迭代次数为O(N)。迭代内部搜索信道最差的车辆复杂度O(N)，对每个信道最差的车辆需要获取其邻居车辆和干扰车辆集合，复杂度为O(N)，因此迭代内部复杂度为O(N2)。因此JRRS算法的复杂度为O(N3)。相对于最优解的遍历复杂度，大幅度降低了运算复杂度。

3 仿真结果与分析

为了验证本文提出的协作传输方法的有效性，采用MATLAB作为仿真平台，通过实验分别对比了不使用协作传输(Non-cooperation)，文献[7]中基于二分图BG(Bipartite Graph)的方法和遍历最优解MSR(Maximum Sum Rate)方法的性能。

仿真场景参考文献[13]如图1所示的场景下，车辆沿高速直线行驶。一个高30 m的基站安装在距离道路15 m远处。V2I通信使用LTE-A链路，带宽40 MHz，工作频率为2 GHz，发射功率52 dBm。V2V通信使用DSRC的5.9 GHz频段，带宽5 MHz，发射功率为20 dBm，调度周期为1 s。其余仿真参数如表1所示。

表1 仿真参数

图2显示在不同车辆数量情况下车辆平均速率随着车辆数量而变化，可以看出，三种方法的平均速率均随着车辆数量增加而减小，JRRS相对于BG算法和非协作传输，实现更高的平均速率。这是由于传输的平均速率主要由V2I的带宽限制，当带宽一定时，平均速率基本上与V2I总带宽呈反比关系。而通过协作传输可以提升一定的传输平均速率，JRRS考虑了资源复用可以为V2V提供更多RB，带来更大的速率增益。

图2 平均速率随车辆数量的变化

图3显示在不同车辆数量情况下频谱效率随着车辆数量而变化。可以看出，当车辆数量较少的情况，由于协作传输车辆较少，协作传输占用了更高的带宽，所以使用协作传输的频率效率略低于不使用协作传输的频谱效率。而随着车辆数量的增加，协作传输车辆也增加，使用协作传输的频谱效率增加，而非协作传输的频谱效率主要由接收车辆的信噪比决定，几乎保持不变。同时，由于JRRS方法考虑了资源复用，可以服务更多V2V，提供更多的RB，带来更高的频谱效率增益，使得JRRS的频谱效率高于BG算法。

图3 频谱效率随车辆数量的变化

图4对比了不同车辆数量下JRRS算法与遍历的MSR算法的车辆速率CDF。由于MSR复杂度过高，因此只计算了20～40辆车情况下的CDF。可以看出JRRS的CDF与MSR相近，总体CDF性能MSR略好于JRRS，而对低数据速率的车辆JRRS算法的性能更好。这是因为JRRS优先提升信道条件最差的车辆，而MSR是以系统总容量最大化为目标调度。

图4 JRRS和MSR传输速率的CDF

4 结 语

本文针对车联网中V2I下行传输过程中，部分车辆信道条件较差的问题，基于SDN架构提出了一种中心式的协作传输算法。所提出的方法利用V2V协作V2I传输，并联合考虑了中继选择和资源复用进行资源调度；此外，为了计算调度结果，本文设计了一个启发式的算法，大幅度降低了求解复杂度。仿真结果表明所提出的协作传输方法改善了处于较差信道条件下车辆的性能，并大幅度提升了系统容量，可用于实际的车联网通信系统。

[1] Willke T L,Tientrakool P,Maxemchuk N F.A survey of inter-vehicle communication protocols and their applications[J].IEEE Communications Surveys & Tutorials,2009,11(2):3-20.

[2] Noori H,Olyaei B B.A novel study on beaconing for VANET-based vehicle to vehicle communication:Probability of beacon delivery in realistic large-scale urban area using 802.11p[C]//Smart Communications in Network Technologies (SaCoNeT),2013 International Conference on.IEEE,2013,1:1-6.

[3] Diao X X,Li J J,Hou K M,et al.Cooperative Inter-Vehicle Communication Protocol Dedicated to Intelligent Transport Systems[C]//Ntms 2008,International Conference on New Technologies,Mobility and Security,November 5-7,2008,Tangier,Morocco,2008:1-5.

[4] 刘建航,毕经平,葛雨明,等.一种基于协助下载方法的车联网选车策略[J].计算机学报,2016,39(5):919-930.

[5] Zhang J,Zhang Q,Jia W.VC-MAC:A cooperative MAC protocol in vehicular networks[J].IEEE Transactions on Vehicular Technology,2009,58(3):1561-1571.

[6] 孙黎.车联网中基于局部信道信息的低复杂度中继选择[J].计算机应用研究,2015,32(12):3786-3789.

[7] Zheng K,Liu F,Zheng Q,et al.A Graph-Based Cooperative Scheduling Scheme for Vehicular Networks[J].IEEE Transactions on Vehicular Technology,2013,62(4):1450-1458.

[8] Zheng Q,Zheng K,Chatzimisios P,et al.Joint optimization of link scheduling and resource allocation in cooperative vehicular networks[J].EURASIP Journal on Wireless Communications and Networking,2015,2015(1):1-14.

[9] Zhang R,Cheng X,Yao Q,et al.Interference Graph-Based Resource-Sharing Schemes for Vehicular Networks[J].IEEE Transactions on Vehicular Technology,2013,62(8):4028-4039.

[10] Sun W,Strom E G,Brannstrom F,et al.D2D-based V2V communications with latency and reliability constraints[C]//GLOBECOM Workshops.IEEE,2015:754-759.

[11] Foundation O N.Software-Defined Networking:The New Norm for Networks[R].April 13,2012.Open Network Foundation (2012) Software-Defined Networking:The New Norm for Networks White Paper 2012.

[12] 赵建容.第二类Stirling数的一些同余式[J].数学学报,2014,57(6):1161-1170.

[13] Zhang Y,Xiong K,Fan P,et al.Mobile Service-Based Cooperative Scheduling for High-Mobility Vehicular Networks[J].Mathematics,2015.

[14] 3GPP TR 36.814 V9.0.0.Further advancements for E-UTRA physical layer aspects (Release 9)[S].March 2010.

[15] Cheng L,Henty B,Stancil D D,et al.A Fully Mobile,GPS Enabled,Vehicle-to-Vehicle Measurement Platform for Characterization of the 5.9 GHz[C]//Antennas and Propagation Society International Symposium,2007 IEEE.IEEE,2007:2005-2008.

ANSDNBASEDALGORITHMOFCOOPERATIVECOMMUNICATIONINVANET

Wang Xiong1,2Tang Liang1,3Bu Zhiyong1,2,3Yu Kai1,3

1(ShanghaiInstituteofMicrosystemandInformationTechnology,ChineseAcademyofSciences,Shanghai200050,China)2(UniversityofChineseAcademyofSciences,Beijing100049,China)3(JushriTechnologies,Inc,Shanghai200335,China)

Vehicle-to-vehicle (V2V) based cooperative transmission is an efficient way to enhance capacity of vehicle-to-infrastructure (V2I) communications in vehicular ad-hoc networks. Focusing on the relay selection and resource reuse of V2V-based cooperative transmission, SDN based cooperative transmission algorithm is proposed in this paper. Each vehicle informed Base Station (BS) its data request and state information via the control channel. The BS then selected relay vehicles and allocated resources to communication links according to the collected information. A heuristic algorithm was used in the scheduling process to reduce the computational complexity. Simulation results indicate the proposed algorithm achieved a significant improvement of data transmission rate and network throughput.

SDN Cooperative transmission Resource allocation V2V V2I

2016-12-20。中国科学院青年创新促进会资助。王雄，硕士生，主研领域：宽带无线通信，车联网的协作传输机制。唐亮，副研究员。卜智勇，研究员。俞凯，研究员。

TP3

A

10.3969/j.issn.1000-386x.2017.11.031