多信道车联网V2R/V2V数据传输调度算法

2019-03-28彭鑫邓清勇田淑娟刘昊霖谢文武李仁发

通信学报 2019年3期

彭鑫，邓清勇，田淑娟，刘昊霖，谢文武，李仁发

彭鑫1,2，邓清勇3,4，田淑娟4，刘昊霖4，谢文武1，李仁发2

（1. 湖南理工学院复杂工业物流系统智能控制与优化湖南省重点实验室，湖南岳阳 414000；2. 湖南大学嵌入式与网络计算湖南省重点实验室，湖南长沙 410082；3. 北京邮电大学信息与通信工程学院，北京 100876；4. 湘潭大学信息工程学院，湖南湘潭 411105）

针对多信道车联网的数据传输需求，提出了V2R/V2V数据传输调度算法。算法首先根据车辆的数据传输请求生成初始调度操作，依初始调度操作之间的冲突关系构建初始调度冲突图和冲突矩阵。其次，在证明冲突矩阵具有半正定性的基础上，采用半定规划方法进行信道分配并完善调度冲突图。最后，根据车辆在服务区域的滞留时间和请求传输的数据量赋予其不同的服务权重，依据调度冲突图，结合V2R/V2V协作传输的方式分时完成调度。交通仿真实验表明，所提算法可以有效利用车联网的多信道特性，通过V2R/V2V协作传输调度改善了网络服务容量。

车联网；数据传输；信道分配；调度；半定规划

1 引言

车联网（VANET, vehicular ad hoc network）[1]是由具备无线通信和计算能力的智能网联车辆以及路边单元（RSU, road side unit）组成的异构网络，具备碰撞避免、事故预警、交通信息发布、Internet接入、辅助驾驶等基本功能[2-3]，还可依托传感器网络提供有效的位置服务[4]，已吸引汽车企业和学术界的广泛参与。国际电气电子工程师学会（IEEE）根据美国联邦通信委员会（FCC）为车联网分配了75 MHz的带宽，制定了由IEEE802.11p和IEEE1609协议构成的车联网专用短距通信（DSRC, dedicated short range communication）的组网标准[5]，为车联网提供了6个服务信道和一个控制信道，实现车辆与车辆（V2V, vehicle to vehicle）之间及车辆与路边单元（V2R, vehicle to roadside unit）之间的数据传输[6-8]。

由于车辆行驶速度快，网络拓扑的动态变化给V2R/V2V数据传输带来巨大挑战。尤其是交通事故预警等时延敏感的应用，需要让消息尽快扩散至兴趣车辆，对V2R和V2V数据传输的可靠性提出了更高的要求[9]。

针对上述问题，本文提出多信道环境下车联网V2R/V2V数据传输调度算法（MCV-DTS, multi-channel VANET-data transmission scheduling）。该算法根据车辆的数据传输请求和可能的调度操作建立初始调度冲突图，在此基础上通过多信道分配和传输调度，构建调度冲突图，然后通过V2R和V2V协作通信方式满足车辆的数据传输需要，可有效利用多信道特性拓展V2R/V2V数据传输的服务容量。

2 车联网数据传输机制

对于车联网数据传输机制的研究主要有2个方面的考虑：一方面侧重于信道访问控制协议，另一方面则侧重于多跳路由协议。本节对其分别进行阐述。

文献[10]提出了时隙共享安全消息访问控制（SS-MAC, slot-sharing media access control）协议，通过记录通信时隙的占用情况和分布式时隙共享算法为车联网安全消息的发送提供了无冲突的广播机制。文献[11]提出了在无RSU支持的情况下，自组织V2V通信的协调MAC协议，通过应用层数据调度和多信道协调机制支持安全和非安全业务。文献[12]提出了车载协作访问控制（VC-MAC, vehicular cooperative media access control）协议，当部分车辆在RSU覆盖区域内无法通过V2R链路完成数据下载时，可借助V2V链路在其他车辆的协助下进行数据访问，扩展了RSU的实际覆盖范围。

数据路由问题也是车联网的研究热点。文献[13]提出了基于共享的消息分发策略，将车辆按请求的消息类型进行分类，每个类别以分组接收率和传输时延为指标甄选中继节点，并形成树形结构分发数据。文献[14]提出了合作多跳传输（PCMR, path-based cooperative multihop relaying）协议，降低了路由过程的链路中断概率。当数据传输过程发生链路中断时，协议将根据网络拓扑和信道条件重新建立传输路径。文献[15]提出了车联网混合路由策略（HRV, hybrid routing in VANET），HRV包含在线可用RSU位置获取算法HRVretrival和基于网络编码的多播协议HRVmulticast，能提升数据传输的顽健性。文献[16]提出了无间隙协助下载方法（NICDM, non-intermittent cooperative downloading method），委托行使方向上的最近2个AP进行协助下载，并选择合适的协助车辆将数据传送给下载车辆，实现在信号盲区的下载服务。文献[17]提出了针对单播路由的V2R和V2V传输协议切换决策算法，根据车辆密度、消息传播方向、网络连通度等参数进行路径决策。

车联网数据传输通常需要RSU的支持，参与数据传输的车辆存在V2V和V2R这2种传输模式，因而已有工作研究了在2种传输模式下的数据传输调度问题。文献[18]提出了最大自由持续时间（MFL, maximum freedom last）协议，该协议针对RSU的文件传输服务，通过最小化V2R链路的切换率扩展RSU的有效覆盖范围。文献[19]为提升车联网数据传输的顽健性，采用动态分簇的数据分发方案。方案将数据传输调度建模为最大最小流问题，并分解为主、子问题求解。文献[20]利用出租车作为移动网关为路边单元和车辆提供数据转发服务，出租车有相对稳定的城市行驶模式，通过马尔可夫链模型估计出租车的形势轨迹，选择最合适的车辆转发数据，降低数据转发时延。文献[21]提出了基于信道预测的车联网消息传输调度方案，该方案通过递归最小二乘算法对信道状态进行预测，从而降低数据传输时延，提升吞吐量。文献[22]针对V2R通信的实时数据传输应用提出了在线调度算法，算法考虑了数据传输的时延要求和数据更新的时效性，可实现周期性数据更新和实时业务请求之间的平衡。文献[23]提出了V2V和V2R协作数据传输（CDD, cooperative data dissemination）协议，考虑控制与服务信道分离的情况，采用分时调度机制，将数据传输调度分为V2V广播、RSU广播和V2V/V2R混合数据传输3个阶段。

当前，对车联网数据传输机制的研究主要针对RSU覆盖范围内的信道访问控制和数据路由策略，网络传输调度问题的研究主要局限于V2R通信的链路调度机制，而多信道条件下V2R/V2V协作传输已成为车联网数据传输的常态，针对该内容的研究仍不多见。

3 车联网数据传输模型

本文研究RSU支持下的V2R/V2V数据传输调度。假设车辆仅配备一个无线接口，其不能同时处于发送或接收状态，而且不能同时处于V2V和V2R模式。组网环境参照IEEE802.11p，使用一个控制信道和6个服务信道。控制信道用于发送管理消息和服务广播，服务信道用于数据通信。车辆在同一时刻只能使用一个信道。在调度过程中，所有车辆首先处于V2V模式，通过控制信道获取邻居列表；然后进入V2R模式，利用控制信道向RSU上传自身位置、邻居列表及服务请求，RSU将服务请求加入任务队列，进行信道分配和调度决策；最后每辆车根据调度决策进入V2R或V2V模式，使用特定信道进行数据传输。

数据传输过程中处于V2R模式的车辆可以与RSU通信，获取数据后在后续调度周期可转入V2V模式，作为发送方将数据分组转发给自己的邻居车辆。V2R/V2V混合数据传输示意如图1所示。处于V2R模式的车辆在RSU覆盖范围内可以从RSU接收数据，1、2和3这3辆车处于V2R模式。图中的细线方块表示数据分组，粗线方块表示车辆已提交传输请求，但还未传输完成的数据分组。RSU广播数据分组，由于1、2、3处于V2R模式，可以收到数据，而4、5、6、7处于V2V模式，只能接收其他车辆发送的数据。4已经从RSU获取数据，可以作为发送方将数据发送给车辆6。同理，5已获取数据和，可以作为发送方将数据发送给7。在数据发送过程中，由于无线信道的开放特性，如果发送方使用同一信道，并且同时发送数据，则会在接收方造成冲突，无法正常接收。图中4、5、6、7距离较近，如果（4,6）和（5,7）使用同一信道发送数据，将造成6无法正常接收，此外，RSU的广播信道也会对V2V通信造成干扰，因而有必要采用多信道传输调度机制。

图1 V2R/V2V混合数据传输示意

用RRN(·)表示V2R模式下RSU的数据接收车辆集合，其定义如下。

根据定义3，VSN()中的车辆准备发送的数据集合为(VSN())，处于V2V模式的接收车辆集合可表示为

在上述集合的基础上，建立调度算法的服务容量定义，具体如下。

定义4 加权服务容量SC()。W()表示调度周期中车辆N的服务权值。加权调度容量SC()定义为调度周期内，被服务的车辆权值之和。

调度过程可总结为以下阶段步骤。

步骤2 判断调度冲突。初始调度操作必须满足以下4个条件，否则将产生调度冲突。

步骤3 构建初始冲突图。根据上述条件1~条件4，可以构造调度操作的初始冲突图。初始冲突图的顶点对应调度操作，将数据接收车辆的权值作为顶点的权值，初始冲突图的边表示相连的2个顶点对应的调度操作相互冲突，图中不相邻的2个顶点说明其对应的调度操作不冲突。对于因同道干扰（条件3）造成的冲突，可以通过多信道分配进行化解。所以需要在初始冲突图的基础上完成信道分配，得到调度冲突图。调度冲突图顶点的加权调度容量的累加即代表调度过程的整体加权调度容量。

初始冲突图的信道分配以是否存在同道干扰为冲突的判定依据，因而可以等效为二维装箱问题。调度冲突图中所有不相邻的顶点正好构成冲突图的加权独立集，本文调度过程的目标则是最大化整体加权调度容量，因而可以等效为求解调度冲突图的最大加权独立集问题。综上，数据传输调度为NP-hard问题。

4 数据传输调度算法

本节在数据传输调度模型的基础上，以最大化加权调度容量为优化目标构建调度算法。首先，查找ISV2R()和ISV2V()中所有存在冲突的调度操作，计算每个调度操作的优先级作为调度权值，以此构建初始冲突图；其次，根据初始冲突图进行信道分配，构建调度冲突图；然后，将调度方案的构造过程建模为最大加权独立集问题；最后，给出RSU传输的数据分组d()及其接收车辆集合RN(d())，V2V模式下发送车辆集合VSN()，发送数据分组集合(VSN())、接收车辆集合VRN((VSN()))以及各条链路所使用的信道CH。下面分项阐述各部分内容。

4.1 调度优先级

4.2 初始冲突图的构建

构建初始冲突图的前提是判断初始调度操作的冲突关系。首先确定V2R模式的车辆集合RSU()，构建初始调度操作集合ISV2R()和ISV2V()，并判断初始调度操作的冲突关系，然后计算每一个操作的权值。

4.3 信道分配与数据传输调度

本节在初始冲突图的基础上分配信道，得到调度冲突图。假设有冲突图G，信道分配过程考虑由同道干扰造成的冲突，仅针对冲突边集合E()。为简单起见，用v表示冲突图的每个顶点，用表示可用信道个数，则信道分配过程可表示为

(v)=ch, 1≤≤(3)

信道分配映射必须满足如下条件。

定理1 对于信道映射(v)=ch(1≤≤)和矩阵，如果(v) =(v)，则α=，否则α=−2。那么当2(−1)时，矩阵具有半正定性。

为确定矩阵的元素，根据定理1可建立求解矩阵的半定规划模型为

在求解上述模型的过程中，难以严格保证的元素σ=−2或σ=，通常是σ≈或σ≈−2。这里采用逐项迭代近似处理的方案解决这一问题，过程如算法1所示。

算法1 基于半定规划的信道分配算法

输入G((),(),E(),ω())

输出G((),E(),ω())

1) ∀v∈(),(v)=null;

2) ifE()=Ø, then

3) ∀v∈(),(v)←ch,∀∈{1, 2, …,};

4)E()=E()+();

5) return

6) else

7) 令=0,=0,0=Ø,0(0(),E0())=((),E());

8) do

9) {用内点法解G(V(),E())的模型(5)，得,λ=max(σ, 1≤,≤|()|)+1);

10)σ=max{σ|1≤,≤e,≠,e=dim()};

11)=+1;

13) {=+1;

15)E()={<v,v>∈E−1()|v,v∉{v,v}}{<v,v> |v∉{v,v},<v,v>∈E−1(),v∈{v,v}};

16) else ifΓ, {v,v}∉Γ, 1≤≤,then

17) {v,v}→Γ;

18) end if

19) end if }

20) while (|V()|=0)

21)=0;

22) for eachΓ, 1≤≤

23) ∀v∈Γ,(v)=null;

24) end for

25)=1;

26) do

27) {ifω()=max∀∈(t)(ω()), then

28) ifv∈Γ, then

29) ∀v∈Γ,(v)=ch;

30)++;

31)()=()−Γ;

32) end if

33) end if }

34) while(≤6∧()≠null)

35) for each <v,v>∈E()

36) if(v)≠null∧(v)≠null, then

37)E()=E()−{<v,v>};

38) end if

39) end for

40) E()=E()+();

41) end if

算法1使用了内点法求解半定规划模型式(5)，依次确定矩阵各元素的值，从而解出冲突矩阵（算法1第8)~20)行）。冲突矩阵反映了各操作间的同道冲突关系，据此通过贪心着色过程可完成信道分配。完成信道分配的顶点之间的冲突边从集合E()中去除，形成调度冲突图（算法1第21)~34)行）。如果可用信道不够，则冲突边仍保留（算法1第35)~39)行），最终得到调度冲突图G。G中没能分配信道的操作则需要通过操作调度算法解决数据传输问题。

算法2在G的基础上，选择最大加权独立集对应的操作，并根据选择的操作进行调度决策，包括确定d()、RRN(d())、VSN()、(VSN())、VRN((VSN()))。然后根据车辆的加入和离开，更新服务队列，具体介绍如下。

算法2 数据传输调度

步骤1 通过逐项检索调度冲突图G顶点v的权值和连接关系确定最大加权独立集ind()。

步骤2 逐项解析并判断最大加权独立集的每一项操作v的类型。

步骤2.1如果传输操作属于V2R模式，即∀RδN∈ind()，由于一个周期内RSU只能发送一个数据，因此数据都是相同的。RSU确定发送数据，从而确定d()。每个调度操作RδN的接收车辆N的集合构成RRN(d())。

步骤2.2如果传输操作属于V2V模式，即∀NδN∈ind()，N形成发送车辆的集合，从而确定VSN()，操作中的数据构成V2V通信传输数据的集合(VSN())，操作中的接收车辆N构成接收车辆集合VRN()。

步骤3维护服务队列，将新进入服务区域的车辆添加到服务车辆集合()，并将离开服务区域的车辆所对应的数据项从服务车辆集合()中删除。

4.4 算法开销分析

5 仿真分析

5.1 实验环境

本文采用SUMO+NS2耦合仿真平台对所提调度算法进行仿真验证。由于本文主要研究RSU服务范围内的数据传输调度，因此仿真场景采用设置单一RSU的直线路段。道路采用双向6车道。逐步增加车流密度，降低相应车速，对称车道参数相同，模拟6种不同的交通环境，如表1所示。在SUMO中，车辆的行驶速度设为平均值后，引入5%的标准差。

表1 交通仿真参数

RSU的覆盖范围为500 m，车辆通信半径为150 m。车辆在驶过RSU服务区时，发起数据传输请求的位置服从均匀分布，数据请求的次数不超过10次。调度周期为1 s。RSU数据队列长度为100，数据项d被访问的概率服从均匀分布。本文将所提MCV-DTS算法与文献[23]的CDD算法和文献[24-25]的IF广播算法在车联网中的应用形式进行了对比。CDD算法支持数据传输调度，IF算法是可用于多跳无线网络的广播机制，本文在IF中采用最多请求的数据广播策略[26]。

仿真过程验证了3种算法的平均加权服务容量（weighted service capacity）、服务比率（service proportion）、请求完成度（completion probability）和服务时延（service delay）。服务容量是调度周期内服务的车辆数目；将已完成的数据请求分为直接由RSU服务的请求和通过邻居车辆完成服务的请求2个部分，服务比率是这2个部分完成的请求数之比；请求完成度是已完成的服务请求与总体数据请求数之比；服务时延是从数据请求提交到数据服务完成所需的时长，单位为s。

5.2 实验结果

图2反映了3种算法在不同交通场景条件下的加权服务容量。3种算法都能利用直接广播和多跳传输这2种通信机制，服务容量不仅包含直接从RSU获取数据的车辆，还包含通过V2V信道从其他车辆获取数据的车辆。实验显示，随着车辆密度的增加，车辆在RSU服务区域内的时间延长，3种算法的加权服务容量逐步增加。IF和CDD算法没有考虑多信道环境，在单信道条件下的广播和多跳传输存在信道冲突，对服务容量造成一定影响。由于CDD算法采用了数据传输权重机制，优先调度服务权重更高的任务，在一定程度上缓解了信道冲突带来的时间开销，相比于IF算法的概率广播机制，有效提升了服务容量。本文MCV-DTS算法在多信道分配的基础上按任务的权重完成传输调度，进一步提升了服务容量。

图2 不同交通场景下3种算法的加权服务容量

图3反映了算法在6种交通场景下，通过RSU传输完成的服务容量。IF算法主要依赖广播通信，而且优先调度有最多请求的数据进行广播，当交通密度增加时，RSU服务容量具有显著提升。而CDD和MCV-DTS算法不仅要考虑RSU直接服务的车辆，还要考虑通过V2V通信的车辆，因为部分车辆的数据请求会通过V2V模式完成，所以调度机制的使用并未提升RSU的广播服务容量。实验结果显示，IF算法由于主要通过广播机制传输热度最高的数据，具有最好的广播服务容量，而CDD和MCV-DTS算法不能直接提升V2R广播容量，且两者的RSU服务容量并无显著区别。

图3 不同交通场景下3种算法的服务容量

图4反映了不同交通场景下3种算法的服务比率。从图4可以看出，IF算法在不同交通场景下具有稳定的服务比率，CDD和MCV-DTS算法在车辆密度增加时，服务比率呈下降趋势。在车辆密度较低时，3种算法服务比率均较高，说明多数车辆通过V2R广播直接获取数据。这是由于车辆密度较低时，V2V模式的数据传输较少，大量数据通过V2R广播完成传输。随着车辆密度的增加，网络连通度增大，CDD和MCV-DTS算法可以将部分数据请求通过调度由V2V通信完成，从而限制了V2R通信的服务容量，降低了服务比率。在V2V通信模式下，MCV-DTS算法通过多信道传输调度，可以满足更多的车辆数据请求，所以当网络密度增加时表现出更低的服务比率。由于RSU只能逐个对数据分组进行广播，因此IF算法通过V2R通信只能满足小部分的数据请求，总体服务比率较高且保持稳定。

图5显示了不同交通场景下3种算法的服务完成度。随着车辆密度的增加，服务完成度逐步上升。这是因为车辆密度较低时，车辆快速通过服务区，提交的服务请求较少。当车辆密度增加时，车辆提交的请求也开始增加，导致服务比率的下降。当车辆密度进一步增加时，车辆速度继续下降，在服务区域内滞留的时间较长，调度周期增加，所以数据请求完成度逐步增加。不难发现，MCV-DTS算法在各种交通场景下，尤其是在车辆密度较大的情况下能取得较好的服务完成度。

图4 不同交通场景下3种算法的服务比率

图5 不同交通场景下3种算法的请求完成度

图6表示了3种算法在不同交通场景下的服务时延。首先，3种算法在车辆密度较低时具有相近的性能表现，随着车辆密度的增大，3种算法服务时延逐步上升。这是因为当车辆密度较低时，服务比率较高，V2R通信占主导地位，数据主要通过RSU广播完成传输，时延较低；当车辆密度增大时，V2V通信承担了部分的数据请求服务，此时IF算法中的车辆只能排队等待V2R通信模式的广播，而CDD和MCV-DTS算法则可通过V2V通信扩展服务范围，实现V2R/V2V并发传输，因而具有相近的性能表现。其中，MCV-DTS算法通过多信道传输进一步提升了并发服务能力，可有效降低服务等待时间，提升服务完成度。

图6 不同交通场景下3种算法的服务时延

6 结束语

本文针对多信道车联网提出了V2R/V2V的数据传输调度算法。算法根据车辆的数据传输请求生成初始调度操作集，并建立调度操作之间的冲突条件，以此根据初始调度操作之间的冲突关系构建初始调度冲突图和冲突矩阵。本文证明了冲突矩阵的正半定性，从而采用半定规划方法进行信道分配，并建立调度冲突图。然后根据车辆在服务区域的滞留时间赋予其不同的服务权重。为了让权重较大的车辆优先获得传输调度服务，本文通过选取最大加权独立集的调度方案，利用V2R/V2V传输完成调度过程。交通仿真实验表明，所提算法可以有效利用车联网的多信道特性改善网络服务容量。

[1] XIAO Z, LI P,HAVYARIMANA V, et al. A novel design for vehicle positioning and trajectory prediction under urban environments[J]. IEEE Sensors Journal, 2018, 18(13): 5586-5594.

[2] XIAO Z, HAVYARIMANA V, LI T, et al. A nonlinear framework of delayed particle smoothing method for vehicle localization under non-gaussian environment[J]. Sensors, 2016, 16(5): 692-708.

[3] ZHAO J, LIU Y, GONG Y, et al. A dual-link soft handover scheme for C/U plane split network in high-speed railway[J]. IEEE Access, 2018(6): 12473-12482.

[4] XIAO F, LIU W, LI Z, et al. Noise-tolerant wireless sensor networks localization via multi-norms regularized matrix completion[J]. IEEE Transactions on Vehicular Technology, 2018, 67(3):2409-2419.

[5] YU R, DING J, HUANG X, et al. Optimal resource sharing in 5G-enabled vehicular networks: a matrix game approach[J]. IEEE Transactions on Vehicular Technology, 2016, 65(10): 7844-7856.

[6] GAO Z, CHEN D, CAI S, et al. OptDynLim: an optimal algorithm for the one-dimensional RSU deployment problem with non-uniform profit density[J]. IEEE Transactions on Industrial Informatics, 2018, 11(4): 1-10.

[7] GAO Z, CHEN D, SUN P, et al. KM-based efficient algorithms for optimal packet scheduling problem in cellular/infostation integrated networks[J]. Ad Hoc Networks, 2018, 77(8): 84-94.

[8] GAO Z, CHEN D, CAI S, et al. Optimal and efficient approximate algorithms for one-dimensional RSU deployment problem with new model[J]. IEEE Transactions on Vehicular Technology, 2018, 11(4): 1-14.

[9] YU R, DING J, HUANG X, et al. Optimal resource sharing in 5G-enabled vehicular networks: a matrix game approach [J]. IEEE Transactions on Vehicular Technology, 2016, 65(10): 7844-7856.

[10] LV F, ZHU H, ZHOU H, et al. SS-MAC: a novel time slot-sharing MAC for safety messages broadcasting in VANETs[J]. IEEE Transactions on Vehicular Technology, 2018, 67(4): 3586-3597.

[11] TONY K, LABERTEAUX K, SENGUPTA R. A multi-channel VANET providing concurrent safety and commercial services[C]//ACM International Workshop on Vehicular Ad Hoc Networks. 2005:1-9.

[12] 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.

[13] DAS B, MISRA S, ROY U. Coalition formation for cooperative service-based message sharing in vehicular ad hoc networks[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(1):144-156.

[14] SHAN H, ZHUANG W. Multihop cooperative communication for vehicular ad hoc networks[C]// International ICST Conference on Communications and Networking in China. 2011:614-619.

[15] WU D, ZHANG Y, BAO L, et al. Location-based crowdsourcing for vehicular communication in hybrid networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(2):837-846.

[16] LIU B, JIA D, LU K, et al. Infrastructure-assisted message dissemination for supporting heterogeneous driving patterns[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(10): 2865-2876.

[17] VEGNI A, LITTLE T. Hybrid vehicular communications based on V2V-V2I protocol switching[J]. International Journal of Vehicle Information & Communication Systems, 2011, 2(3/4):213-231.

[18] CHANG C, CHENG R, SHIH H, et al. Maximum freedom last scheduling algorithm for downlinks of DSRC networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2007, 8(2):223-232.

[19] AZIZIAN M, CHERKAOUI S, HAFID A, et al. A distributed cluster based transmission scheduling in VANET[C]// IEEE International Conference on Communication. 2016: 1-6.

[20] WANG Y, YANG E, ZHENG W, et al. A realistic and optimized V2V communication system for taxicabs[C]// International Conference on Distributed Computing Systems. 2016:139-148.

[21] ZENG F, ZHANG R, CHENG X, et al. Channel prediction based scheduling for data dissemination in VANETs[J]. IEEE Communications Letters, 2017, 21(6):1409-1412.

[22] LIU K, LEE V, NG K, et al. Temporal data dissemination in vehicular cyber-physical systems[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(6):2419-2431.

[23] LIU K, NG J, LEE V, et al. Cooperative data scheduling in hybrid vehicular ad hoc networks: VANET as a software defined network[J]. IEEE/ACM Transactions on Networking, 2016, 24(3):1759-1773.

[24] BUSANELLI S, FERRARI G, GIORGIO V. On the effects of mobility for efficient broadcast data dissemination in I2V networks[C]// GLOBECOM Workshops. 2011:38-42.

[25] BUSANELLI S, FERRARI G, PANICHPAPIBOON S. Efficient broadcasting in IEEE 802.11 networks through irresponsible forwarding[C]// Global Telecommunications Conference. 2009:1-6.

[26] WONG J. Broadcast delivery[J]. Proceedings of the IEEE, 1988, 76(12):1566-1577.

Data dissemination scheduling algorithm for V2R/V2V in multi-channel VANET

PENG Xin1,2, DENG Qingyong3,4, TIAN Shujuan4, LIU Haolin4, XIE Wenwu1, LI Renfa2

1. Key Laboratory of Hunan Province on Intelligent Control and Optimization of Complex Industrial Logistics System, Hunan Institute of Science and Technology, Yueyang 414000, China 2. Key Laboratory for Embedded and Network Computing of Hunan Province, Hunan University, Changsha 410082, China 3. School of Information and Communication Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China 4. College of Information Engineering, Xiangtan University, Xiangtan 411105, China

Considering that the data dissemination in multi-channel VANET (vehicular ad hoc network), a cooperative data dissemination scheduling algorithm was introduced for V2R(vehicle to roadside unit) and V2V(vehicle to vehicle). The algorithm created initial scheduling operators according to data requisition of vehicles. Then, initial collision graph and collision matrix were generated based on the conflict among initial scheduling operators. After proving the positive semidefinite of collision matrix, SDP (semidefinite programming) was used to channel allocation and collision graph creation. The algorithm then assigned weights for each data requisition according to dwell time and data volume of vehicles in RSU service region. Furthermore, it selected maximum weighted independent set of collision graph. The goal was to satisfy the most urgent data requisitions by V2R/V2V cooperate transmission. Transportation simulation results demonstrate that the proposed solution effectively promotes the service capacity by utilizes the multichannel of VANET and V2R/V2V transmission scheduling.

vehicular ad hoc network, data dissemination, channel allocation, scheduling, semidefinite programming

TP393

10.11959/j.issn.1000−436x.2019060

2018−03−13；

2018−07−02

邓清勇，dengqingyong@xtu.edu.cn

国家自然科学基金资助项目（No.61772195, No.61602398, No.61300039）；湖南省自然科学基金资助项目（No.2018JJ2156, No.2018JJ2154）；湖南省科技计划基金资助项目（No.2016TP1021）；湖南省教育科学“十三五”规划课题基金资助项目（No.XJK17BXX004）；计算机网络和信息集成教育部重点实验室（东南大学）开放基金资助项目（No.K93-9-2016-09）

The National Natural Science Foundation of China (No.61772195, No.61602398, No.61300039), The Natural Science Foundation of Hunan Province(No.2018JJ2156, No.2018JJ2154), The Science and Technology Program of Hunan Province (No.2016TP1021), The 13th Five-Years Plan of Education Science Program of Hunan Province(No.XJK17BXX004), Key Laboratory of Computer Networks and Information Integration of Ministry of Education Research Foundation (No.K93-9-2016-09)

彭鑫（1981− ），男，湖南岳阳人，博士，湖南理工学院副教授，主要研究方向为车联网和云计算。