一種基于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?？梢钥闯鯦RRS的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