多信道車聯網V2R/V2V數據傳輸調度算法

彭鑫，鄧清勇，田淑娟，劉昊霖，謝文武，李仁發

?

多信道車聯網V2R/V2V數據傳輸調度算法

彭鑫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

A

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? ），男，湖南岳陽人，博士，湖南理工學院副教授，主要研究方向為車聯網和云計算。

鄧清勇（1981? ），男，湖南武岡人，北京郵電大學博士生，主要研究方向為物聯網與認知網絡。

田淑娟（1982? ），女，湖南攸縣人，博士，湘潭大學副教授，主要研究方向為物聯網和CPS。

劉昊霖（1988? ），男，湖南寧鄉人，博士，湘潭大學講師，主要研究方向為物聯網和無線傳感器網絡。

謝文武（1979? ），男，湖北監利人，博士，湖南理工學院講師，主要研究方向為物聯網與大數據。

李仁發（1957? ），男，湖南郴州人，博士，湖南大學教授、博士生導師，主要研究方向為物聯網與CPS。