基于網絡編碼的車載網數據傳輸性能的研究

馬 寧，張義兵，束永安

(安徽大學 計算機科學與技術學院，安徽 合肥 230601)

基于網絡編碼的車載網數據傳輸性能的研究

馬 寧，張義兵，束永安

(安徽大學 計算機科學與技術學院，安徽 合肥 230601)

車載網通過車輛與車輛(Vehicle to Vehicle，V2V)或車輛與路側單元(Vehicle to Infrastructure,V2I)之間的數據傳輸實現通信。車載網絡不同于傳統無線網絡，具有網絡拓撲變化快、節點受限、網絡間斷性聯通等特點。由于車輛高速移動以及街道障礙物阻擋等原因,車載網絡分割現象更加嚴重,路由問題更加復雜。因此車載網中數據傳輸性能面臨著信道負載大、傳輸延時高、帶寬利用率低等的挑戰。為了提高車載網數據傳輸的效率并降低轉發延時，文中在混合通信結構(V2V&V2I)中，提出了一種改進的隨機線性網絡編碼(Optimized Random Linear Network Coding，ORLNC)技術，同時采用車輛路徑近似度來確定下一轉發車輛節點。NS-3和MOVE仿真實驗表明，ORLNC與現有的DDR協議算法相比，明顯降低了轉發延時，提高了傳輸效率，同時該協議算法不僅適用于密集車載網，也適用于稀疏場景中數據的傳輸。

車載網；車輛與車輛；車輛與路側單元；混合通信結構；改進的隨機線性網絡編碼

0 引 言

車載自組織網絡(VANET)不同于無線Mesh網，它具有能量足、計算能力強、網絡拓撲變化快、網絡間斷連通性、節點受限運動等特點。因此車輛間數據傳輸性能面臨較大的挑戰。

諸多學者基于隨機線性網絡編碼提出了多種新協議算法[1-3]。其中,Mirani F利用隨機線性網絡編碼結合基于延時中樞機制協議提出了基于延時的機會網絡編碼協議—DONC[4]，基于延時廣播機制是建立在發送方與接收方之間距離的基礎上。實驗已證明DONC協議的數據傳輸性能優于傳統的基于延時的廣播協議，但轉發延時高和傳輸效率低等仍是車載網數據傳輸性能的主要影響因素。文獻[5]提出了基于網絡編碼與分簇的分發算法—DDR，利用粒子群算法優化簇頭的選舉，其中周期性動態選舉簇頭需花費大量時間，延時性較高。

文中對適用于無線Mesh網中的隨機線性網絡編碼進行了改進，在混合通信結構中提出了ORLNC算法并且采用基于車輛路徑近似度的車輛選擇協議。該協議算法可以進一步降低轉發延時并提高傳輸效率。

1 隨機線性網絡編碼

隨機線性網絡編碼[6-7]：對信源節點要廣播的數據包進行線性編碼處理，其中編碼系數從最小有限域GF(2n)中隨機取得。

圖1中，假設源節點S將要轉發的數據分成X1,X2，在有限域中分別選取ε1,ε2和ε3,ε4。向節點A廣播的數據可表示為Y1=ε1X1+ε2X2，向節點B廣播的數據可表示為Y2=ε3X1+ε4X2。節點C分別接收到A,B廣播的數據包Y1,Y2，再對Y1,Y2進行編碼處理，可表示為：

Y3=ε5Y1+ε6Y2=ε5(ε1X1+ε2X2)+ε6(ε3X1+ε4X2)

圖1 隨機線性網絡編碼原理圖

由于節點D,E已經分別接收到Y2,Y1，通過解碼分別得到X1和X2，因此可以達到理論上的最大流和最小割的上限，實現數據傳輸在轉發延時、系統容量和均衡負載方面的性能提高。

車載網絡：車載網是最近興起的自組織網絡結構，它廣泛應用于交通運輸類、交通安全類和信息服務類。車載網不同于傳統的無線網絡，具有網絡拓撲變化快、節點運動受限、網絡間斷連通性、能量足、計算能力強、自組織和自管理的特點，可以實時廣播道路交通狀況，有效提高交通安全。車載網作為新型的通信網絡，可以實現車輛與車輛(V2V)的通信、車輛與基礎設施(V2I)的通信和混合通信(V2V&V2I)。但其傳輸效率和傳輸延時不能滿足日益增大的數據傳輸量。文中是在混合通信結構中基于改進的隨機線性網絡編碼對數據傳輸性能的研究，達到提高傳輸速率和降低轉發延時的目的。

2 ORLNC協議算法

2.1 場景描述

隨著3G網的全覆蓋和4G網的普及，無論在城市車輛密集地區還是在車輛稀疏的偏僻區域，保證數據傳輸的實時性和準確性都是比較難實現的。傳統的實現方法主要通過基站的覆蓋，由于成本太高，因此很多地方很難覆蓋，數據很難得到高效傳輸。網絡編碼的應用可以有效解決網絡負載和延時等問題。但隨著數據信息量不斷的增加，高延時性和低傳輸效率等問題還是存在。可借助路側單元(RSU)[8]結合改進的隨機線性網絡編碼進行數據轉發。文中在車輛密集場景下研究數據傳輸性能。

將整個區域劃分成若干個小區域，每個小區域由多個路側單元負責該區域內車輛的運行軌跡的跟蹤。整個區域內的路側單元由一個控制中心控制，從而控制該區域里的車輛間的數據傳輸。當車輛轉發數據給另一車輛，若都在控制中心A區域內，區域內的車輛將自己的運動狀態(車輛ID、運動方向、運動速度、所在位置)發送到RSU，RSU可根據車輛的運動狀態，采用車輛路徑近似度確定下一個轉發車輛節點。當中間車輛節點接收到多個編碼數據則根據目標車輛的軌跡選擇進行再編碼處理或者直接轉發，直至目標車輛接收到編碼數據包。如果目標車輛已經離開A區域，則RSU將車輛的運動狀態發送到控制中心，由各控制中心通過衛星GPS相互交換信息，從而指導各區域的RSU，進而控制車輛間數據的傳輸，保證數據傳輸的時效性和安全性。

2.2 ORLNC協議算法描述

可以將數據的傳輸過程分為三個階段:

(1)編碼數據包階段。

首先將源數據X分成n份，即X=(X1,X2,…,Xn)，每一份數據包有m個數據，則第i個數據包可以表示為：Xi=(xi,1,xi,2,…,xi,m)。為了防止數據在傳輸過程中被破壞丟失，建立一個多元函數h(x,y)對源數據包進行初始化處理[9-10]。以第一個數據xi,1作為初始隨機數,處理過程如下：

(1)

其中，h(x,y)為多元函數。

考慮到多元函數的計算復雜度，文中建立二元隨機函數h(x,y)=x+y+c，其中c為隨機常數。則式(1)中Yi可以進一步表示為：

(2)

其中i∈[1,n]，將二元函數h(x,y)同編碼數據包一起轉發給下一車輛節點。

(2)中繼車輛節點選取階段。

該協議算法采用路徑近似度[12-13]確定下一轉發車輛節點，各車輛以“hello”的會話消息形式周期性將自己的運動狀態廣播給該區域的RSU，RSU根據附近車輛的運動狀態(車輛ID、所在位置、運動方向、運動速度)建立局部動態坐標軸，見圖2。

圖2 基于路徑近似度的車輛運動坐標示意圖

中間車輛節點的路徑近似度可表示為：

(3)

其中：i為中繼車輛；obj為目標車輛；s為源車輛；TTL為車輛向RSU發送消息的周期時間；dmin(i,obj)為中間車輛與目標車輛最短路徑近似度。

(4)

(5)

式(4)、(5)分別是求初始時刻源車輛與目標車輛的近似距離和t時刻中繼車輛與目標車輛的近似距離。

圖2中，車輛的路徑近似度越高表示它經過目標車輛附近的概率就越大，將中繼車輛中路徑近似度最大的車輛作為下一轉發車輛節點。在路徑近似度相同的情況下，考慮將時間效率高的車輛選擇為下一轉發車輛節點，即達到路徑近似度最高時最短時間的車輛，時間效率可表示為：

(6)

RSU根據式(3)計算結果確定下一轉發車輛節點，在轉發中繼車輛節點中又接收到多個有效編碼數據包的車輛，則再進行編碼處理。此時編碼系數不需再從最小有限域中隨機選取，而是使用源車輛選取的編碼系數。若在選擇下一轉發節點時，出現相同的路徑近似度的兩輛車，根據式(6)計算出車輛與目標車輛近似度最大時，選擇時間效率較高的車輛為下一轉發車輛節點。

(3)解碼數據包階段。

ORLNC實現數據傳輸步驟如下：

①源車輛對要轉發的數據進行拆分和線性編碼處理，同時將自己的運動狀態廣播給附近RSU，進入步驟②。

②RSU通過周圍車輛的運動狀態建立車輛局部動態坐標軸，該坐標軸是動態的，每隔一定的時間重新創建新的坐標軸。進入步驟③。

③RSU根據車輛的運動狀態計算出周圍車輛節點的路徑近似度，選擇下一轉發車輛節點。如果目標車輛節點與源車輛不在同一區域，則進入步驟④，否則進入步驟⑤。

④此時各區域中的控制中心通過衛星GPS通信，交換各區域車輛運動狀態。源車輛區域中的RSU根據控制中心反饋的另一區域的車輛運動狀態，計算各車輛的路徑近似度，選擇路徑近似度最大的車輛作為下一轉發車輛節點，進入步驟⑤。

⑤判斷編碼數據包是否已經被目標車輛成功接收，若是則進入步驟⑥，否則進入步驟③。

⑥目標車輛接收到足夠多的編碼數據包后，通過h(x,y)=x+y+c和Xi,k=Yi,k(εi,1,εi,2,…,εi,m)-1解碼出源數據包。

3 仿真實驗與結果分析

采用MOVE和NS-3[15-17]進行仿真實驗，評估文中提出的ORLNC協議算法性能。MOVE仿真軟件針對VANET快速構造車輛移動模型，NS-3則提供完整網絡模擬環境。因此網絡模擬軟件NS-3中的節點可以根據MOVE設置的車輛運動軌跡的方式運動。將仿真實驗的場景設置如下：

仿真實驗區域為5 000m×5 000m的正方形區域，并將正方形區域劃分成四個2 500m×2 500m的小正方形區域，每個小正方形區域分別有一個控制中心M和多個RSU控制著各區域車輛的數據傳輸。采用IEEE802.11的MAC協議，每個小區域的車輛分數目別為10,20,30,40，車輛運動速度在5～30m/s中隨機取值。數據包的大小設為2kB,1kB,512byte。車輛的通信范圍為半徑R=300m的圓形區域。車輛向附近RSU以“hello”方式通信的周期TTL=2s，最小有限域設置為GF(2n)。二元函數為h(x,y)=x+y+c，可傳遞重復使用。仿真時間設置為400s。

文中將ORLNC協議算法與DDR協議算法在傳輸延時、數據傳輸效率方面進行比較分析。

DDR算法通過速度矢量聚類算法對鄰近范圍內的車輛分簇，節點采用基于粒子群優化選舉算法周期性計算簇頭，由簇頭將編碼數據包廣播給簇內的目標車輛，這樣分簇和尋簇頭將花費較多的時間，導致車輛間數據轉發延時較大。

文中提出的ORLNC協議算法首先在隨機線性網絡編碼上做了改進，改變每次編碼時都在最小有限域中隨機選取編碼系數，而是在初始選擇的編碼系數中再次使用，可以有效減少選取系數的時間。并且采用基于車輛路徑近似度選擇下一轉發車輛節點，而這路徑近似度計算過程由車輛周圍的RSU完成，只需將計算結果反饋給車輛，比較結果如圖3所示。

圖3 轉發延時比較圖

由圖可見，ORLNC的轉發延時相較于DDR算法明顯降低了。

數據包在網絡傳輸中，會遇到各種外界的干擾，如黑客攻擊、數據包丟失等。DDR算法只是將源數據編碼處理再轉發，有可能編碼數據包在傳輸中發生丟失和破壞，而需再次重傳，無法保證數據的正確性和安全性。文中提出的ORLNC協議算法克服了DDR算法消極的保護數據的措施，創建二元函數h(x,y)=x+y+c對源數據包進行初始化處理，相當于對數據包進行加密處理，起到了較好的保密作用。比較結果如圖4所示。

由圖可見，編碼數據包的傳輸效率明顯高于DDR算法。

4 結束語

文中基于隨機線性網絡編碼，提出了一種改進的隨機線性網絡編碼—ORLNC，同時采用基于路徑近似度的車輛選擇協議。根據車輛能量充足、計算能力強等特點，為確保數據包的穩定性，ORLNC創建了一個二元函數h(x,y)對源數據做初始處理，進而提高車輛通信的準確性和安全性。同時也對初始處理后的數據包編碼也做了改進優化，下一次編碼時不再從最小有限域中隨機選取編碼系數，而是使用上一次編碼時選取的編碼系數。ORLNC協議算法是在車輛密集的場景下提出的，也適用于車輛稀疏場景。最后通過MOVE和NS-3仿真實驗，證明了ORLNC協議算法較于DDR可以進一步降低轉發延時，提高傳輸效率。

[1]YeF,RoyS,WangH.Efficientdatadisseminationinvehicularadhocnetworks[J].IEEEJournalonSelectedAreasinCommunications,2012,30(4):769-779.

[2]ZhangX,LiB.Optimizedmultipathnetworkcodinginlossywirelessnetworks[J].IEEEJournalonSelectedAreasinCommunications,2009,27(5):622-634.

[3]HassanabadiB,ValaeeS.ReliableperiodicsafetymessagebroadcastinginVANETsusingnetworkcoding[J].IEEETransactionsonWirelessCommunications,2014,13(3):1284-1297.

[4]MiraniF,BussonA,AdjihC.Improvingdelay-baseddatadisseminationprotocolinVANETswithnetworkcoding[J].REVJournalonElectronicsandCommunications,2013,2(3-4).

[5]HoT,KoetterR,MedardM,etal.Towardarandomoperationofnetworks[J].IEEETransactionsonInformationTheory,2004,50(3):532-537.

[6] Ho T,Médard M,Koetter R,et al.A random linear network coding approach to multicast[J].IEEE Transactions on Information Theory,2006,52(10):4413-4430.

[7] Kumar R,Dave M. DDDRC:decentralised data dissemination in VANET using raptor codes[J].International Journal of Electronics,2015,102(6):946-966.

[8] Guclu S S,Altilar D T.Downlink utilization with R2V2V communications in clustered vehicular networks[C]//Proc of 9th international symposium on communication systems,networks & digital signal processing.[s.l.]:IEEE,2014:99-104.

[9] 朱聞亞.數據加密技術在計算機網絡安全中的應用價值研究[J].制造業自動化,2012,34(6):35-36.

[10] 魏瑞良.計算機網絡通信安全中數據加密技術的研究與應用[D].北京:中國地質大學,2013.

[11] 楊 軍.網絡編碼的若干關鍵問題研究[D].武漢:華中科技大學,2013.

[12] Hult R,Campos G R,Falcone P,et al.Approximate solution to the optimal coordination problem for autonomous vehicles at intersections[R].Sweden:Chalmers University of Technology,2015.

[13] 丁 郁.基于機會通信的車載網絡路由關鍵技術研究[D].北京:北京郵電大學,2013.

[14] 臧新建.從一道證明題來看基礎解系的一般證法[J].數學學習與研究,2014(5):74-74.

[15] Henderson T R,Lacage M,Riley G F,et al.Network simulations with the NS-3 simulator[C]//Proc of SIGCOMM demonstration.[s.l.]:[s.n.],2008.

[16] Lan K,Chou C M.Realistic mobility models for vehicular ad hoc network (VANET) simulations[C]//Proc of 8th international conference on ITS telecommunications.[s.l.]:IEEE,2008:362-366.

[17] 陳 林,石林祥,孔亮亮.車輛自組織網絡的仿真研究[J].上海第二工業大學學報,2013(1):6-11.

Research on Data Transmission Performance in VANET Based on Network Coding

MA Ning,ZHANG Yi-bing,SHU Yong-an

(School of Computer Science and Technology,Anhui University,Hefei 230601,China)

Through data transmission between Vehicle to Vehicle (V2V) or Vehicles to Infrastructure (V2I) roadside units,vehicular network achieves communication.Vehicular network is different from traditional wireless networks,which has the unique characteristics,such as fast network topology changes,node constraints,intermittent network connectivity and so on.Due to the high speed of vehicle and the obstruction of the barrier in the streets,the vehicle network segmentation is more serious and the routing problem is more complex.Data transmission performance in vehicle network faces change,including channel load,high transmission delay,low bandwidth utilization and so on.In order to improve the efficiency of data transmission and reduce the forwarding delay，an Optimized Random Linear Network Coding (ORLNC) is proposed in the hybrid communication structure (V2V&V2I).Simulation experiments by NS-3 and MOVE show that ORLNC significantly reduces forwarding delay and improves transmission efficiency compared with the DDR.At the same time,this algorithm is not only applied in dense vehicular networks,but also suitable for the transmission of data in sparse scenario.

VANET;V2V;V2I;hybrid communication structure;ORLNC

2015-07-25

2015-10-27

時間：2016-03-22

安徽省自然科學基金項目(1408085MF125)

馬 寧(1990-)，男，碩士，研究方向為無線網絡；束永安，教授，研究方向為無線網絡、下一代網絡體系結構。

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1522.098.html

TP393

A

1673-629X(2016)05-0036-04

10.3969/j.issn.1673-629X.2016.05.008