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

?

多信道車聯(lián)網(wǎng)V2R/V2V數(shù)據(jù)傳輸調(diào)度算法

彭鑫1,2，鄧清勇3,4，田淑娟4，劉昊霖4，謝文武1，李仁發(fā)2

（1. 湖南理工學(xué)院復(fù)雜工業(yè)物流系統(tǒng)智能控制與優(yōu)化湖南省重點實驗室，湖南 岳陽 414000；2. 湖南大學(xué)嵌入式與網(wǎng)絡(luò)計算湖南省重點實驗室，湖南 長沙 410082；3. 北京郵電大學(xué)信息與通信工程學(xué)院，北京 100876；4. 湘潭大學(xué)信息工程學(xué)院，湖南 湘潭 411105）

針對多信道車聯(lián)網(wǎng)的數(shù)據(jù)傳輸需求，提出了V2R/V2V數(shù)據(jù)傳輸調(diào)度算法。算法首先根據(jù)車輛的數(shù)據(jù)傳輸請求生成初始調(diào)度操作，依初始調(diào)度操作之間的沖突關(guān)系構(gòu)建初始調(diào)度沖突圖和沖突矩陣。其次，在證明沖突矩陣具有半正定性的基礎(chǔ)上，采用半定規(guī)劃方法進行信道分配并完善調(diào)度沖突圖。最后，根據(jù)車輛在服務(wù)區(qū)域的滯留時間和請求傳輸?shù)臄?shù)據(jù)量賦予其不同的服務(wù)權(quán)重，依據(jù)調(diào)度沖突圖，結(jié)合V2R/V2V協(xié)作傳輸?shù)姆绞椒謺r完成調(diào)度。交通仿真實驗表明，所提算法可以有效利用車聯(lián)網(wǎng)的多信道特性，通過V2R/V2V協(xié)作傳輸調(diào)度改善了網(wǎng)絡(luò)服務(wù)容量。

車聯(lián)網(wǎng)；數(shù)據(jù)傳輸；信道分配；調(diào)度；半定規(guī)劃

1 引言

車聯(lián)網(wǎng)（VANET, vehicular ad hoc network）[1]是由具備無線通信和計算能力的智能網(wǎng)聯(lián)車輛以及路邊單元（RSU, road side unit）組成的異構(gòu)網(wǎng)絡(luò)，具備碰撞避免、事故預(yù)警、交通信息發(fā)布、Internet接入、輔助駕駛等基本功能[2-3]，還可依托傳感器網(wǎng)絡(luò)提供有效的位置服務(wù)[4]，已吸引汽車企業(yè)和學(xué)術(shù)界的廣泛參與。國際電氣電子工程師學(xué)會（IEEE）根據(jù)美國聯(lián)邦通信委員會（FCC）為車聯(lián)網(wǎng)分配了75 MHz的帶寬，制定了由IEEE802.11p和IEEE1609協(xié)議構(gòu)成的車聯(lián)網(wǎng)專用短距通信（DSRC, dedicated short range communication）的組網(wǎng)標準[5]，為車聯(lián)網(wǎng)提供了6個服務(wù)信道和一個控制信道，實現(xiàn)車輛與車輛（V2V, vehicle to vehicle）之間及車輛與路邊單元（V2R, vehicle to roadside unit）之間的數(shù)據(jù)傳輸[6-8]。

由于車輛行駛速度快，網(wǎng)絡(luò)拓撲的動態(tài)變化給V2R/V2V數(shù)據(jù)傳輸帶來巨大挑戰(zhàn)。尤其是交通事故預(yù)警等時延敏感的應(yīng)用，需要讓消息盡快擴散至興趣車輛，對V2R和V2V數(shù)據(jù)傳輸?shù)目煽啃蕴岢隽烁叩囊骩9]。

針對上述問題，本文提出多信道環(huán)境下車聯(lián)網(wǎng)V2R/V2V數(shù)據(jù)傳輸調(diào)度算法（MCV-DTS, multi-channel VANET-data transmission scheduling）。該算法根據(jù)車輛的數(shù)據(jù)傳輸請求和可能的調(diào)度操作建立初始調(diào)度沖突圖，在此基礎(chǔ)上通過多信道分配和傳輸調(diào)度，構(gòu)建調(diào)度沖突圖，然后通過V2R和V2V協(xié)作通信方式滿足車輛的數(shù)據(jù)傳輸需要，可有效利用多信道特性拓展V2R/V2V數(shù)據(jù)傳輸?shù)姆?wù)容量。

2 車聯(lián)網(wǎng)數(shù)據(jù)傳輸機制

對于車聯(lián)網(wǎng)數(shù)據(jù)傳輸機制的研究主要有2個方面的考慮：一方面?zhèn)戎赜谛诺涝L問控制協(xié)議，另一方面則側(cè)重于多跳路由協(xié)議。本節(jié)對其分別進行闡述。

文獻[10]提出了時隙共享安全消息訪問控制（SS-MAC, slot-sharing media access control）協(xié)議，通過記錄通信時隙的占用情況和分布式時隙共享算法為車聯(lián)網(wǎng)安全消息的發(fā)送提供了無沖突的廣播機制。文獻[11]提出了在無RSU支持的情況下，自組織V2V通信的協(xié)調(diào)MAC協(xié)議，通過應(yīng)用層數(shù)據(jù)調(diào)度和多信道協(xié)調(diào)機制支持安全和非安全業(yè)務(wù)。文獻[12]提出了車載協(xié)作訪問控制（VC-MAC, vehicular cooperative media access control）協(xié)議，當部分車輛在RSU覆蓋區(qū)域內(nèi)無法通過V2R鏈路完成數(shù)據(jù)下載時，可借助V2V鏈路在其他車輛的協(xié)助下進行數(shù)據(jù)訪問，擴展了RSU的實際覆蓋范圍。

數(shù)據(jù)路由問題也是車聯(lián)網(wǎng)的研究熱點。文獻[13]提出了基于共享的消息分發(fā)策略，將車輛按請求的消息類型進行分類，每個類別以分組接收率和傳輸時延為指標甄選中繼節(jié)點，并形成樹形結(jié)構(gòu)分發(fā)數(shù)據(jù)。文獻[14]提出了合作多跳傳輸（PCMR, path-based cooperative multihop relaying）協(xié)議，降低了路由過程的鏈路中斷概率。當數(shù)據(jù)傳輸過程發(fā)生鏈路中斷時，協(xié)議將根據(jù)網(wǎng)絡(luò)拓撲和信道條件重新建立傳輸路徑。文獻[15]提出了車聯(lián)網(wǎng)混合路由策略（HRV, hybrid routing in VANET），HRV包含在線可用RSU位置獲取算法HRVretrival和基于網(wǎng)絡(luò)編碼的多播協(xié)議HRVmulticast，能提升數(shù)據(jù)傳輸?shù)念B健性。文獻[16]提出了無間隙協(xié)助下載方法（NICDM, non-intermittent cooperative downloading method），委托行使方向上的最近2個AP進行協(xié)助下載，并選擇合適的協(xié)助車輛將數(shù)據(jù)傳送給下載車輛，實現(xiàn)在信號盲區(qū)的下載服務(wù)。文獻[17]提出了針對單播路由的V2R和V2V傳輸協(xié)議切換決策算法，根據(jù)車輛密度、消息傳播方向、網(wǎng)絡(luò)連通度等參數(shù)進行路徑?jīng)Q策。

車聯(lián)網(wǎng)數(shù)據(jù)傳輸通常需要RSU的支持，參與數(shù)據(jù)傳輸?shù)能囕v存在V2V和V2R這2種傳輸模式，因而已有工作研究了在2種傳輸模式下的數(shù)據(jù)傳輸調(diào)度問題。文獻[18]提出了最大自由持續(xù)時間（MFL, maximum freedom last）協(xié)議，該協(xié)議針對RSU的文件傳輸服務(wù)，通過最小化V2R鏈路的切換率擴展RSU的有效覆蓋范圍。文獻[19]為提升車聯(lián)網(wǎng)數(shù)據(jù)傳輸?shù)念B健性，采用動態(tài)分簇的數(shù)據(jù)分發(fā)方案。方案將數(shù)據(jù)傳輸調(diào)度建模為最大最小流問題，并分解為主、子問題求解。文獻[20]利用出租車作為移動網(wǎng)關(guān)為路邊單元和車輛提供數(shù)據(jù)轉(zhuǎn)發(fā)服務(wù)，出租車有相對穩(wěn)定的城市行駛模式，通過馬爾可夫鏈模型估計出租車的形勢軌跡，選擇最合適的車輛轉(zhuǎn)發(fā)數(shù)據(jù)，降低數(shù)據(jù)轉(zhuǎn)發(fā)時延。文獻[21]提出了基于信道預(yù)測的車聯(lián)網(wǎng)消息傳輸調(diào)度方案，該方案通過遞歸最小二乘算法對信道狀態(tài)進行預(yù)測，從而降低數(shù)據(jù)傳輸時延，提升吞吐量。文獻[22]針對V2R通信的實時數(shù)據(jù)傳輸應(yīng)用提出了在線調(diào)度算法，算法考慮了數(shù)據(jù)傳輸?shù)臅r延要求和數(shù)據(jù)更新的時效性，可實現(xiàn)周期性數(shù)據(jù)更新和實時業(yè)務(wù)請求之間的平衡。文獻[23]提出了V2V和V2R協(xié)作數(shù)據(jù)傳輸（CDD, cooperative data dissemination）協(xié)議，考慮控制與服務(wù)信道分離的情況，采用分時調(diào)度機制，將數(shù)據(jù)傳輸調(diào)度分為V2V廣播、RSU廣播和V2V/V2R混合數(shù)據(jù)傳輸3個階段。

當前，對車聯(lián)網(wǎng)數(shù)據(jù)傳輸機制的研究主要針對RSU覆蓋范圍內(nèi)的信道訪問控制和數(shù)據(jù)路由策略，網(wǎng)絡(luò)傳輸調(diào)度問題的研究主要局限于V2R通信的鏈路調(diào)度機制，而多信道條件下V2R/V2V協(xié)作傳輸已成為車聯(lián)網(wǎng)數(shù)據(jù)傳輸?shù)某B(tài)，針對該內(nèi)容的研究仍不多見。

3 車聯(lián)網(wǎng)數(shù)據(jù)傳輸模型

本文研究RSU支持下的V2R/V2V數(shù)據(jù)傳輸調(diào)度。假設(shè)車輛僅配備一個無線接口，其不能同時處于發(fā)送或接收狀態(tài)，而且不能同時處于V2V和V2R模式。組網(wǎng)環(huán)境參照IEEE802.11p，使用一個控制信道和6個服務(wù)信道?？刂菩诺烙糜诎l(fā)送管理消息和服務(wù)廣播，服務(wù)信道用于數(shù)據(jù)通信。車輛在同一時刻只能使用一個信道。在調(diào)度過程中，所有車輛首先處于V2V模式，通過控制信道獲取鄰居列表；然后進入V2R模式，利用控制信道向RSU上傳自身位置、鄰居列表及服務(wù)請求，RSU將服務(wù)請求加入任務(wù)隊列，進行信道分配和調(diào)度決策；最后每輛車根據(jù)調(diào)度決策進入V2R或V2V模式，使用特定信道進行數(shù)據(jù)傳輸。

數(shù)據(jù)傳輸過程中處于V2R模式的車輛可以與RSU通信，獲取數(shù)據(jù)后在后續(xù)調(diào)度周期可轉(zhuǎn)入V2V模式，作為發(fā)送方將數(shù)據(jù)分組轉(zhuǎn)發(fā)給自己的鄰居車輛。V2R/V2V混合數(shù)據(jù)傳輸示意如圖1所示。處于V2R模式的車輛在RSU覆蓋范圍內(nèi)可以從RSU接收數(shù)據(jù)，1、2和3這3輛車處于V2R模式。圖中的細線方塊表示數(shù)據(jù)分組，粗線方塊表示車輛已提交傳輸請求，但還未傳輸完成的數(shù)據(jù)分組。RSU廣播數(shù)據(jù)分組，由于1、2、3處于V2R模式，可以收到數(shù)據(jù)，而4、5、6、7處于V2V模式，只能接收其他車輛發(fā)送的數(shù)據(jù)。4已經(jīng)從RSU獲取數(shù)據(jù)，可以作為發(fā)送方將數(shù)據(jù)發(fā)送給車輛6。同理，5已獲取數(shù)據(jù)和，可以作為發(fā)送方將數(shù)據(jù)發(fā)送給7。在數(shù)據(jù)發(fā)送過程中，由于無線信道的開放特性，如果發(fā)送方使用同一信道，并且同時發(fā)送數(shù)據(jù)，則會在接收方造成沖突，無法正常接收。圖中4、5、6、7距離較近，如果（4,6）和（5,7）使用同一信道發(fā)送數(shù)據(jù)，將造成6無法正常接收，此外，RSU的廣播信道也會對V2V通信造成干擾，因而有必要采用多信道傳輸調(diào)度機制。

圖1 V2R/V2V混合數(shù)據(jù)傳輸示意

用RRN(·)表示V2R模式下RSU的數(shù)據(jù)接收車輛集合，其定義如下。

根據(jù)定義3，VSN()中的車輛準備發(fā)送的數(shù)據(jù)集合為(VSN())，處于V2V模式的接收車輛集合可表示為

在上述集合的基礎(chǔ)上，建立調(diào)度算法的服務(wù)容量定義，具體如下。

定義4 加權(quán)服務(wù)容量SC()。W()表示調(diào)度周期中車輛N的服務(wù)權(quán)值。加權(quán)調(diào)度容量SC()定義為調(diào)度周期內(nèi)，被服務(wù)的車輛權(quán)值之和。

調(diào)度過程可總結(jié)為以下階段步驟。

步驟2 判斷調(diào)度沖突。初始調(diào)度操作必須滿足以下4個條件，否則將產(chǎn)生調(diào)度沖突。

步驟3 構(gòu)建初始沖突圖。根據(jù)上述條件1~條件4，可以構(gòu)造調(diào)度操作的初始沖突圖。初始沖突圖的頂點對應(yīng)調(diào)度操作，將數(shù)據(jù)接收車輛的權(quán)值作為頂點的權(quán)值，初始沖突圖的邊表示相連的2個頂點對應(yīng)的調(diào)度操作相互沖突，圖中不相鄰的2個頂點說明其對應(yīng)的調(diào)度操作不沖突。對于因同道干擾（條件3）造成的沖突，可以通過多信道分配進行化解。所以需要在初始沖突圖的基礎(chǔ)上完成信道分配，得到調(diào)度沖突圖。調(diào)度沖突圖頂點的加權(quán)調(diào)度容量的累加即代表調(diào)度過程的整體加權(quán)調(diào)度容量。

初始沖突圖的信道分配以是否存在同道干擾為沖突的判定依據(jù)，因而可以等效為二維裝箱問題。調(diào)度沖突圖中所有不相鄰的頂點正好構(gòu)成沖突圖的加權(quán)獨立集，本文調(diào)度過程的目標則是最大化整體加權(quán)調(diào)度容量，因而可以等效為求解調(diào)度沖突圖的最大加權(quán)獨立集問題。綜上，數(shù)據(jù)傳輸調(diào)度為NP-hard問題。

4 數(shù)據(jù)傳輸調(diào)度算法

本節(jié)在數(shù)據(jù)傳輸調(diào)度模型的基礎(chǔ)上，以最大化加權(quán)調(diào)度容量為優(yōu)化目標構(gòu)建調(diào)度算法。首先，查找ISV2R()和ISV2V()中所有存在沖突的調(diào)度操作，計算每個調(diào)度操作的優(yōu)先級作為調(diào)度權(quán)值，以此構(gòu)建初始沖突圖；其次，根據(jù)初始沖突圖進行信道分配，構(gòu)建調(diào)度沖突圖；然后，將調(diào)度方案的構(gòu)造過程建模為最大加權(quán)獨立集問題；最后，給出RSU傳輸?shù)臄?shù)據(jù)分組d()及其接收車輛集合RN(d())，V2V模式下發(fā)送車輛集合VSN()，發(fā)送數(shù)據(jù)分組集合(VSN())、接收車輛集合VRN((VSN()))以及各條鏈路所使用的信道CH。下面分項闡述各部分內(nèi)容。

4.1 調(diào)度優(yōu)先級

4.2 初始沖突圖的構(gòu)建

構(gòu)建初始沖突圖的前提是判斷初始調(diào)度操作的沖突關(guān)系。首先確定V2R模式的車輛集合RSU()，構(gòu)建初始調(diào)度操作集合ISV2R()和ISV2V()，并判斷初始調(diào)度操作的沖突關(guān)系，然后計算每一個操作的權(quán)值。

4.3 信道分配與數(shù)據(jù)傳輸調(diào)度

本節(jié)在初始沖突圖的基礎(chǔ)上分配信道，得到調(diào)度沖突圖。假設(shè)有沖突圖G，信道分配過程考慮由同道干擾造成的沖突，僅針對沖突邊集合E()。為簡單起見，用v表示沖突圖的每個頂點，用表示可用信道個數(shù)，則信道分配過程可表示為

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

信道分配映射必須滿足如下條件。

定理1 對于信道映射(v)=ch(1≤≤)和矩陣，如果(v) =(v)，則α=，否則α=?2。那么當2(?1)時，矩陣具有半正定性。

為確定矩陣的元素，根據(jù)定理1可建立求解矩陣的半定規(guī)劃模型為

在求解上述模型的過程中，難以嚴格保證的元素σ=?2或σ=，通常是σ≈或σ≈?2。這里采用逐項迭代近似處理的方案解決這一問題，過程如算法1所示。

算法1 基于半定規(guī)劃的信道分配算法

輸入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) {用內(nèi)點法解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使用了內(nèi)點法求解半定規(guī)劃模型式(5)，依次確定矩陣各元素的值，從而解出沖突矩陣（算法1第8)~20)行）。沖突矩陣反映了各操作間的同道沖突關(guān)系，據(jù)此通過貪心著色過程可完成信道分配。完成信道分配的頂點之間的沖突邊從集合E()中去除，形成調(diào)度沖突圖（算法1第21)~34)行）。如果可用信道不夠，則沖突邊仍保留（算法1第35)~39)行），最終得到調(diào)度沖突圖G。G中沒能分配信道的操作則需要通過操作調(diào)度算法解決數(shù)據(jù)傳輸問題。

算法2在G的基礎(chǔ)上，選擇最大加權(quán)獨立集對應(yīng)的操作，并根據(jù)選擇的操作進行調(diào)度決策，包括確定d()、RRN(d())、VSN()、(VSN())、VRN((VSN()))。然后根據(jù)車輛的加入和離開，更新服務(wù)隊列，具體介紹如下。

算法2 數(shù)據(jù)傳輸調(diào)度

步驟1 通過逐項檢索調(diào)度沖突圖G頂點v的權(quán)值和連接關(guān)系確定最大加權(quán)獨立集ind()。

步驟2 逐項解析并判斷最大加權(quán)獨立集的每一項操作v的類型。

步驟2.1如果傳輸操作屬于V2R模式，即?RδN∈ind()，由于一個周期內(nèi)RSU只能發(fā)送一個數(shù)據(jù)，因此數(shù)據(jù)都是相同的。RSU確定發(fā)送數(shù)據(jù)，從而確定d()。每個調(diào)度操作RδN的接收車輛N的集合構(gòu)成RRN(d())。

步驟2.2如果傳輸操作屬于V2V模式，即?NδN∈ind()，N形成發(fā)送車輛的集合，從而確定VSN()，操作中的數(shù)據(jù)構(gòu)成V2V通信傳輸數(shù)據(jù)的集合(VSN())，操作中的接收車輛N構(gòu)成接收車輛集合VRN()。

步驟3維護服務(wù)隊列，將新進入服務(wù)區(qū)域的車輛添加到服務(wù)車輛集合()，并將離開服務(wù)區(qū)域的車輛所對應(yīng)的數(shù)據(jù)項從服務(wù)車輛集合()中刪除。

4.4 算法開銷分析

5 仿真分析

5.1 實驗環(huán)境

本文采用SUMO+NS2耦合仿真平臺對所提調(diào)度算法進行仿真驗證。由于本文主要研究RSU服務(wù)范圍內(nèi)的數(shù)據(jù)傳輸調(diào)度，因此仿真場景采用設(shè)置單一RSU的直線路段。道路采用雙向6車道。逐步增加車流密度，降低相應(yīng)車速，對稱車道參數(shù)相同，模擬6種不同的交通環(huán)境，如表1所示。在SUMO中，車輛的行駛速度設(shè)為平均值后，引入5%的標準差。

表1 交通仿真參數(shù)

RSU的覆蓋范圍為500 m，車輛通信半徑為150 m。車輛在駛過RSU服務(wù)區(qū)時，發(fā)起數(shù)據(jù)傳輸請求的位置服從均勻分布，數(shù)據(jù)請求的次數(shù)不超過10次。調(diào)度周期為1 s。RSU數(shù)據(jù)隊列長度為100，數(shù)據(jù)項d被訪問的概率服從均勻分布。本文將所提MCV-DTS算法與文獻[23]的CDD算法和文獻[24-25]的IF廣播算法在車聯(lián)網(wǎng)中的應(yīng)用形式進行了對比。CDD算法支持數(shù)據(jù)傳輸調(diào)度，IF算法是可用于多跳無線網(wǎng)絡(luò)的廣播機制，本文在IF中采用最多請求的數(shù)據(jù)廣播策略[26]。

仿真過程驗證了3種算法的平均加權(quán)服務(wù)容量（weighted service capacity）、服務(wù)比率（service proportion）、請求完成度（completion probability）和服務(wù)時延（service delay）。服務(wù)容量是調(diào)度周期內(nèi)服務(wù)的車輛數(shù)目；將已完成的數(shù)據(jù)請求分為直接由RSU服務(wù)的請求和通過鄰居車輛完成服務(wù)的請求2個部分，服務(wù)比率是這2個部分完成的請求數(shù)之比；請求完成度是已完成的服務(wù)請求與總體數(shù)據(jù)請求數(shù)之比；服務(wù)時延是從數(shù)據(jù)請求提交到數(shù)據(jù)服務(wù)完成所需的時長，單位為s。

5.2 實驗結(jié)果

圖2反映了3種算法在不同交通場景條件下的加權(quán)服務(wù)容量。3種算法都能利用直接廣播和多跳傳輸這2種通信機制，服務(wù)容量不僅包含直接從RSU獲取數(shù)據(jù)的車輛，還包含通過V2V信道從其他車輛獲取數(shù)據(jù)的車輛。實驗顯示，隨著車輛密度的增加，車輛在RSU服務(wù)區(qū)域內(nèi)的時間延長，3種算法的加權(quán)服務(wù)容量逐步增加。IF和CDD算法沒有考慮多信道環(huán)境，在單信道條件下的廣播和多跳傳輸存在信道沖突，對服務(wù)容量造成一定影響。由于CDD算法采用了數(shù)據(jù)傳輸權(quán)重機制，優(yōu)先調(diào)度服務(wù)權(quán)重更高的任務(wù)，在一定程度上緩解了信道沖突帶來的時間開銷，相比于IF算法的概率廣播機制，有效提升了服務(wù)容量。本文MCV-DTS算法在多信道分配的基礎(chǔ)上按任務(wù)的權(quán)重完成傳輸調(diào)度，進一步提升了服務(wù)容量。

圖2 不同交通場景下3種算法的加權(quán)服務(wù)容量

圖3反映了算法在6種交通場景下，通過RSU傳輸完成的服務(wù)容量。IF算法主要依賴廣播通信，而且優(yōu)先調(diào)度有最多請求的數(shù)據(jù)進行廣播，當交通密度增加時，RSU服務(wù)容量具有顯著提升。而CDD和MCV-DTS算法不僅要考慮RSU直接服務(wù)的車輛，還要考慮通過V2V通信的車輛，因為部分車輛的數(shù)據(jù)請求會通過V2V模式完成，所以調(diào)度機制的使用并未提升RSU的廣播服務(wù)容量。實驗結(jié)果顯示，IF算法由于主要通過廣播機制傳輸熱度最高的數(shù)據(jù)，具有最好的廣播服務(wù)容量，而CDD和MCV-DTS算法不能直接提升V2R廣播容量，且兩者的RSU服務(wù)容量并無顯著區(qū)別。

圖3 不同交通場景下3種算法的服務(wù)容量

圖4反映了不同交通場景下3種算法的服務(wù)比率。從圖4可以看出，IF算法在不同交通場景下具有穩(wěn)定的服務(wù)比率，CDD和MCV-DTS算法在車輛密度增加時，服務(wù)比率呈下降趨勢。在車輛密度較低時，3種算法服務(wù)比率均較高，說明多數(shù)車輛通過V2R廣播直接獲取數(shù)據(jù)。這是由于車輛密度較低時，V2V模式的數(shù)據(jù)傳輸較少，大量數(shù)據(jù)通過V2R廣播完成傳輸。隨著車輛密度的增加，網(wǎng)絡(luò)連通度增大，CDD和MCV-DTS算法可以將部分數(shù)據(jù)請求通過調(diào)度由V2V通信完成，從而限制了V2R通信的服務(wù)容量，降低了服務(wù)比率。在V2V通信模式下，MCV-DTS算法通過多信道傳輸調(diào)度，可以滿足更多的車輛數(shù)據(jù)請求，所以當網(wǎng)絡(luò)密度增加時表現(xiàn)出更低的服務(wù)比率。由于RSU只能逐個對數(shù)據(jù)分組進行廣播，因此IF算法通過V2R通信只能滿足小部分的數(shù)據(jù)請求，總體服務(wù)比率較高且保持穩(wěn)定。

圖5顯示了不同交通場景下3種算法的服務(wù)完成度。隨著車輛密度的增加，服務(wù)完成度逐步上升。這是因為車輛密度較低時，車輛快速通過服務(wù)區(qū)，提交的服務(wù)請求較少。當車輛密度增加時，車輛提交的請求也開始增加，導(dǎo)致服務(wù)比率的下降。當車輛密度進一步增加時，車輛速度繼續(xù)下降，在服務(wù)區(qū)域內(nèi)滯留的時間較長，調(diào)度周期增加，所以數(shù)據(jù)請求完成度逐步增加。不難發(fā)現(xiàn)，MCV-DTS算法在各種交通場景下，尤其是在車輛密度較大的情況下能取得較好的服務(wù)完成度。

圖4 不同交通場景下3種算法的服務(wù)比率

圖5 不同交通場景下3種算法的請求完成度

圖6表示了3種算法在不同交通場景下的服務(wù)時延。首先，3種算法在車輛密度較低時具有相近的性能表現(xiàn)，隨著車輛密度的增大，3種算法服務(wù)時延逐步上升。這是因為當車輛密度較低時，服務(wù)比率較高，V2R通信占主導(dǎo)地位，數(shù)據(jù)主要通過RSU廣播完成傳輸，時延較低；當車輛密度增大時，V2V通信承擔了部分的數(shù)據(jù)請求服務(wù)，此時IF算法中的車輛只能排隊等待V2R通信模式的廣播，而CDD和MCV-DTS算法則可通過V2V通信擴展服務(wù)范圍，實現(xiàn)V2R/V2V并發(fā)傳輸，因而具有相近的性能表現(xiàn)。其中，MCV-DTS算法通過多信道傳輸進一步提升了并發(fā)服務(wù)能力，可有效降低服務(wù)等待時間，提升服務(wù)完成度。

圖6 不同交通場景下3種算法的服務(wù)時延

6 結(jié)束語

本文針對多信道車聯(lián)網(wǎng)提出了V2R/V2V的數(shù)據(jù)傳輸調(diào)度算法。算法根據(jù)車輛的數(shù)據(jù)傳輸請求生成初始調(diào)度操作集，并建立調(diào)度操作之間的沖突條件，以此根據(jù)初始調(diào)度操作之間的沖突關(guān)系構(gòu)建初始調(diào)度沖突圖和沖突矩陣。本文證明了沖突矩陣的正半定性，從而采用半定規(guī)劃方法進行信道分配，并建立調(diào)度沖突圖。然后根據(jù)車輛在服務(wù)區(qū)域的滯留時間賦予其不同的服務(wù)權(quán)重。為了讓權(quán)重較大的車輛優(yōu)先獲得傳輸調(diào)度服務(wù)，本文通過選取最大加權(quán)獨立集的調(diào)度方案，利用V2R/V2V傳輸完成調(diào)度過程。交通仿真實驗表明，所提算法可以有效利用車聯(lián)網(wǎng)的多信道特性改善網(wǎng)絡(luò)服務(wù)容量。

[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

國家自然科學(xué)基金資助項目（No.61772195, No.61602398, No.61300039）；湖南省自然科學(xué)基金資助項目（No.2018JJ2156, No.2018JJ2154）；湖南省科技計劃基金資助項目（No.2016TP1021）；湖南省教育科學(xué)“十三五”規(guī)劃課題基金資助項目（No.XJK17BXX004）；計算機網(wǎng)絡(luò)和信息集成教育部重點實驗室（東南大學(xué)）開放基金資助項目（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? ），男，湖南岳陽人，博士，湖南理工學(xué)院副教授，主要研究方向為車聯(lián)網(wǎng)和云計算。

鄧清勇（1981? ），男，湖南武岡人，北京郵電大學(xué)博士生，主要研究方向為物聯(lián)網(wǎng)與認知網(wǎng)絡(luò)。

田淑娟（1982? ），女，湖南攸縣人，博士，湘潭大學(xué)副教授，主要研究方向為物聯(lián)網(wǎng)和CPS。

劉昊霖（1988? ），男，湖南寧鄉(xiāng)人，博士，湘潭大學(xué)講師，主要研究方向為物聯(lián)網(wǎng)和無線傳感器網(wǎng)絡(luò)。

謝文武（1979? ），男，湖北監(jiān)利人，博士，湖南理工學(xué)院講師，主要研究方向為物聯(lián)網(wǎng)與大數(shù)據(jù)。

李仁發(fā)（1957? ），男，湖南郴州人，博士，湖南大學(xué)教授、博士生導(dǎo)師，主要研究方向為物聯(lián)網(wǎng)與CPS。