稀疏場景下基于網絡編碼和RSU數據傳輸的研究

章圓圓 馬 寧 束永安

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

稀疏場景下基于網絡編碼和RSU數據傳輸的研究

章圓圓 馬 寧 束永安

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

車載自組織網中數據傳輸的場景主要包括車輛密集的城市道路場景和車輛稀疏的偏遠地區，目前大多數研究針對的是車輛密集場景下數據傳輸。在車輛稀疏的車載自組織網中，車輛節點間相遇的概率受限，因此數據傳輸面臨信道負載大、傳輸延時高、帶寬利用率低等挑戰。為了提高數據包在稀疏場景下傳輸性能，提出了基于代間漸進編碼技術和RSU的傳輸策略RORLNC，通過各個編碼代之間的漸進編碼操作，可有效防止因丟包引起編碼數據包無法被解碼。另外借助RSU尋找最佳轉發車輛節點，可有效避免編碼數據包長期無法被轉發。用NS-2和MOVE軟件進行仿真實驗。實驗結果證明RORLNC比現有的DDR算法具有較高的吞吐率和較低的平均轉發延遲。

車載自組織網 數據傳輸 代間漸進網絡編碼 路側單元

0 引 言

車載自組織網的網絡拓撲變化快、間斷性連接、車輛節點分布不均勻等特點，使得傳統的自組網轉發算法[1]并不適用。在車輛密集場景中，前人從不同方面改進數據包的傳輸性能[2-4]，并取得了較大的成果。然而在車輛稀疏場景中，車輛節點間的距離遠大于車輛節點的通信范圍，從而無法直接將數據包轉發給下一車輛節點，近年來學者對該場景的研究進展較為緩慢。本文提出了基于代間漸進編碼和RSU的數據傳輸算法RORLNC，改進傳統代內隨機線性編碼，采用代間漸進編碼方式，即后一代數據包與前一代已編碼的數據包再做線性處理，即使前一代編碼丟失，也可以被目的車輛節點根據后一編碼代恢復，借助RSU將編碼數據包轉發給可適度值最大的下一車輛節點，從而降低轉發次數和提高數據傳輸的可靠性。

1 隨機線性網絡編碼

隨機線性網絡編碼[5]：從最小有限域GF(2)隨機選擇編碼系數對信源節點要廣播的數據包進行線性編碼處理，圖1展示了傳統隨機線性編碼的過程。

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

在圖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)，由于節點D1、D2已經分別接收到Y1、Y2，通過解碼分別得到X1和X2，因此可以達到理論上的最大流和最小割的上限。

2 RORLNC策略設計

2.1 基本思想

RORLNC算法在源車輛節點采用代間漸進編碼對數據包線性處理，在車輛稀疏的高速路上的每段道路建有路側單元RSU，RSU與通信范圍內的車輛節點組成一個集群，由RSU管理集群內的車輛，掌握車輛的運動狀態(速度、方向、位置、攜帶的編碼數據包)。在RSU緩存中換分兩個固定區域S1、S2，其中S1區域用來存儲車輛節點轉發來的編碼數據包，并根據編碼數據包的數量和重復轉發的次數建立一個編碼數據包優先級列表，S2區域建立一個車輛節點優先級列表，計算經過群集中各個車輛節點的可適度值，可適度值越大優先級越高。RSU將編碼數據包及時轉發給可適度值最大的車輛節點，進而提高數據包在車輛稀疏場景中傳輸效率和降低轉發延遲。

2.2RSU群集建立

RSU定時廣播Rreq消息，周圍車輛節點接收到Rreq消息，立即發送Rres消息，并通過該消息建立通信連接，并且由RSU管理周圍各車輛節點的運動狀態，其中Rreq消息和Rres消息的主要內容如下：

Rreq {

Rreq_ID;

//RSU的ID

Rreq_addr;

//RSU的位置

Rreq_snum;

//RSU緩存中數據包的數量

Rreq_iaddr；

//請求RSU通信范圍內車輛節點的位置

Rreq_ive;

//請求RSU通信范圍內車輛節點的速度

Rreq_idir; //請求RSU通信范圍內車輛節點的運動方向

}

Rres {

Rres_ID;

//與RSU通信的車輛節點ID

Rres_RSUaddr;

//與車輛節點通信的RSU位置

Rres_addr;

//與RSU通信的車輛節點位置

Rres_ve;

//與RSU通信的車輛節點速度

Rres_snum;

//車輛節點攜帶數據包的數量

Rres_mnum;

//車輛節點間相遇的次數

Rres_mdir;

//車輛節點的運動方向

}

2.3 源車輛節點的代間漸進式編碼

建立一個簡單的隨機函數h(x)[6]對源數據包做初始化處理，主要目的是防止中間節點故意破壞數據包。設隨機函數為h(x)=x+c，其中c為隨機數，隨機函數h(x)將與編碼數據包一起被轉發，由目的車輛節點根據接收到的h(x)和編碼數據包還原出源數據包，有效提高編碼數據包的可靠性。對每個編碼代數據包編號，編碼代源數據包表示為I=(I0,I1,…,IK-1)。令c為第1編碼代數據包I0，則第i個編碼代數據包的初始化表示如下：

(1)

源車輛節點不再是簡單對每個編碼代數據包單獨進行線性編碼操作，而是采用代間漸進式編碼方式。具體編碼過程如下：

(4) 同理后面編碼代的數據包依次做代間編碼操作，直至各個編碼代的數據包都被線性編碼處理，第k代數據包的編碼結果表示為:

(2)

源車輛節點中各個編碼代的編碼數據包與編碼系數存在線性組合關系，對應的編碼矩陣可以表示為：

(3)

2.4 下一轉發車輛節點的選擇

車輛與附近的RSU建立了群集，保證了RSU可以管理其群集內的車輛節點。如圖2所示，混合車載網中數據傳輸有兩種方式，一種是車輛與車輛通信，另一種是車輛與RSU通信，通過RSU將編碼數據包轉發給最佳轉發節點。受文獻[7]的啟發，本文提出了車輛節點運動狀態相似度MS(Motion Similarity)的計算方法，通過車輛節點MS的值計算出各車輛節點的可適度VS(Vehicle Suitability)。在RSU中，以TTL為時間周期定時更新群集內各車輛節點的可適度值VSnew，同時根據車輛節點的可適度值建立一個車輛節點優先級列表PL(PriorityList)來顯示每個周期中車輛節點轉發編碼數據包的優先順序，車輛節點的可適度越大，其優先級越高，反之越低。

圖2 車輛與RSU建立群集

當攜帶有編碼數據包的轉發車輛節點i與附近有車輛節點j相遇，則通過“hello”消息建立通信連接，車輛節點i根據“hello”消息中車輛j的運動方向做出判斷。由于高速路上車輛節點間相對運動方向只存在相同或是相反，如果車輛節點j與i運動方向相同，這兩個車輛相遇其他車輛是基本相同的，說明車輛節點j將編碼數據包擴散到遠處目的節點的機會較小，反之車輛節點i將編碼數據包轉發給車輛節點j。當轉發車輛節點i周圍不存在與之通信的車輛節點或存在車輛節點，但車與自己運動方向相同，車輛節點i則選擇與所屬群集的RSU建立連接。根據式(4)計算群集內車輛節點的運動狀態相似度MS，RSU采用式(5)更新各車輛節點的可適度值。

(4)

(5)

在式(5)中，EN表示車輛節點與其他車輛節點相遇的次數，den表示車輛節點間相遇時運動方向不相同的次數。MS越大，車輛節點間運動方向相同的概率越大，此時編碼數據包更不易被轉發到遠處的目的節點。在式(5)中，VSold表示車輛節點之前的可適度，初始值為0。其中參數α和β滿足α+β=1(α∈(0,1),β∈(0,1))，α和β反映的是可適度VS和車輛節點運動狀態相似度MS的相關程度，α的值越大，VS的值與車輛節點的運動狀態相似度相關性越大，此時α和β的值是人工設置的。

2.5 目的車輛節點的解碼

(6)

(7)

由于r(Z′)=k，根據可逆矩陣定理，滿秩矩陣可逆。目的車輛節點根據解碼式(8)解碼出所有編碼代的數據包。

(8)

?

3 仿真實驗與結果分析

3.1 仿真場景描述

本文采用NS-2和MOVE仿真軟件[9]在車輛稀疏模擬場景下對RORLNC進行仿真實驗。本節采用MOVE仿真軟件對某個區域的地圖建立車輛節點移動模型，利用NS-2提供完整的網絡模擬環境，因此網絡模擬軟件NS-2中的節點可以根據MOVE設置的車輛運動軌跡的方式運動，此時MOVE和NS-2是一種協作關系。將RORLNC和DDR在平均轉發延遲、吞吐率、傳輸效率三個方面[10]比較分析。仿真試驗區域為5 000 m×4 000 m的長方形，道路寬度和長度分別為20 m和5 000 m，并且道路采用雙車道雙向通行。車輛的通信范圍為半徑R=300 m的圓形區域，車輛運動速度為10～20 m/s隨機變化，區域中的車輛的數量為0～120不等，并且車輛的密度隨著場景的變化而改變，服從指數分布。本文建立的動態坐標軸的橫軸長5 000 m,縱軸長4 000 m，坐標軸內單元格為10 m×10 m的矩形，車輛在該坐標軸內的運動方向有上、下、左、右。應用層生成大小為10 KB源數據，在傳輸層被分成10個編碼代數據包，并采用UDP協議將數據包發送到網絡層，編碼系數從最小有限域GF(2)中隨機選擇。采用IEEE802.11b的MAC協議，車輛向附近車輛廣播“hello”消息的周期TTL=0.5s。哈希函數為h(x)=x+c，其中c為隨機常數，該函數隨編碼數據包一起轉發給下一轉發車輛節點，將此次仿真時間設置為400s。為了保證實驗結果的客觀性，在同一場景下進行10次仿真實驗，并取其平均值作為本次試驗結果。

3.2 實驗結果分析

1) 吞吐率

如圖3所示，在車輛節點數量為0時，在車載自組織網中只有路側單元RSU，數據包無法進行傳輸。隨著車輛節點數量的增多，RORLNC算法明顯要優于DDR。在車輛數量為100時，本章提出的RORLNC算法吞吐率與DDR算法相比，提高了近60%。分析認為，DDR算法只是采用車輛節點作為轉發節點，但在車輛稀疏場景下，車輛節點間大部分時間不能建立完整的數據傳輸路徑，導致了車輛節點的吞吐率較低。而RORLNC算法首先借助RSU作為轉發節點，并且對接收的編碼數據包和經過群集中的車輛節點分別建立了優先級列表，在盡可能短的時間內將編碼數據包轉發給車輛節點，有效提高了吞吐率。另外在MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略較于DDR協議明顯提高了吞吐率。

圖3 車輛節點數量對吞吐率的影響情況

2) 轉發平均時延

圖4顯示了兩種算法的數據包平均轉發延遲隨車輛節點數量變化的曲線。從圖中可知，當車輛節點數量極少時，由于車輛節點間相遇的機會有限，數據包轉發的概率較低，兩種算法的平均延遲都較高。隨著車輛節點數量的增加，兩種算法都有明顯降低，但與車輛密集的場景相比，該場景下車輛節點的數量仍不能使數據包在車輛節點間直接進行傳輸。由于RORLNC借助了RSU，由RSU以TTL為周期選擇本地群集中可適度最高的車輛節點(優先級最高)作為下一轉發車輛節點，因此RORLNC算法的平均延遲整體上要低于DDR。MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略較于DDR協議，轉發平均時延得到了降低。

圖4 車輛節點數量對平均轉發時延的影響情況

3) 數據傳輸效率

圖5描述了數據傳輸效率與車輛節點數量的關系。從圖中可以看出，兩種算法的效率隨車輛節點數量的增加，總體上呈上升趨勢，原因是基于分簇和基于車輛路徑近似度的思想都是與車輛建立連接，尋找最佳的轉發車輛節點，可在車輛稀疏場景中，車輛間的連接機會較少，無法建立有效的連接進行數據的轉發。RORLNC算法的效率明顯較高，是因其設置了多個判斷，當攜帶編碼數據的車輛節點附近存在通信機會的車輛節點，則將編碼數據包發送給行駛方向相反的下一車輛節點，否則與附近的RSU建立連接，由RSU將編碼數據包在合適的時間轉發給在時間TTL內優先級最高的車輛節點，從而提高數據的傳輸效率。MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略提高了數據包的傳輸效率。

圖5 車輛節點數量對傳輸效率的影響情況

4 結 語

為進一步提高數據包在車輛稀疏場景下傳輸性能，本文首先在傳統的隨機線性網絡編碼基礎上，提出了一種的基于RSU的代間漸進式網絡編碼RORLNC。在RORLNC中，首先建立一個哈希函數對源數據包初始化，防止數據包被竊聽，然后依次對每個代間數據包做漸進編碼操作，有效提高了編碼數據包的可靠性傳輸，保證了編碼數據包能被解碼。關于轉發車輛節點的選擇，本文則借助RSU計算周圍車輛節點的可適度值。通過MOVE和NS-2仿真軟件對DDR和RORLNC的數據傳輸性能進行比較和分析，MOVE和NS-2仿真實驗結果驗證了ORLNC算法在整體性能上要優于DDR。

[1]IETF.MobileAdHocNetworks[OL].http://www.ietf.org/html.charters/manet-charter.html.

[2]ZhuH,ChangS,LiM,etal.Exploitingtemporaldependencyforopportunisticforwardinginurbanvehicularnetworks[C]//2011InternationalConferenceonComputerCommunications.IEEE,2011:2192-2200.

[3]ShafieeK,LeungVCM.Connectivity-awareminimum-delaygeographicroutingwithvehicletrackinginVANETs[J].AdHocNetworks,2011,9(2):131-141.

[4] 盧怡睿,俞研,吳家順.基于網絡編碼與分簇的車載自組網數據分發算法[J].計算機應用,2014,34(S1):9-11,14.

[5]KumarR,DaveM.DDDRC:decentraliseddatadisseminationinVANETusingraptorcodes[J].InternationalJournalofElectronics,2015,102(6):946-966.

[6]MakTK,LaberteauxKP,SenguptaR.Amulti-channelVANETprovidingconcurrentsafetyandcommercialservices[C]//Proceedingsofthe2ndACMInternationalWorkshoponVehicularAdHocNetworks.ACM,2005:1-9.

[7] 胡皓.容遲網絡的路由技術研究[D].北京:北京理工大學,2014.

[8] 俞美華.求逆矩陣的幾種方法[J].科技視界,2015(31):177-178,224.

[9]AhujaB,GohilA,KumarR,etal.SimulationofVANETusingVanetMobiSimandNS-2[J].WirelessCommunication,2013,5(9):381-384.

[10]MartelliF,RendaME,RestaG,etal.Ameasurement-basedstudyofbeaconingperformanceinIEEE802.11pvehicularnetworks[C]//2012InternationalConferenceonComputerCommunications.IEEE,2012:1503-1511.

RESEARCH ON DATA TRANSMISSION BASED ON NETWORK CODING AND RSU IN SPARSE SCENE

Zhang Yuanyuan Ma Ning Shu Yongan

(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

The scene of data transmission in VANET mainly includes vehicle intensive urban road scenes and vehicle sparsely in remote areas. Nowadays, most of the research is focused on the data transmission in the vehicle intensive scene. In the sparse VANET, the probability of meeting between the nodes of the vehicle is limited, so the data transmission faces the challenges of large channel load, high transmission delay and low bandwidth utilization. In order to improve the transmission performance of the packet in the sparse scene, a transmission strategy RORLNC based on the inter-generation gradual network coding and RSU is proposed. Through the coding between the various code generation operation, can effectively prevent packet loss caused by the encoded data packet can’t be decoded. In addition, the best forwarding node can be found by RSU, which can avoid the long-term failure to forward the encoded data packet. The simulation experiment is carried out with NS-2 and MOVE software, and the experimental results show that RORLNC has higher throughput and lower average forwarding delay than the existing DDR algorithm.

VANET Data transmission Inter-generation gradual network coding RSU

2016-04-08。安徽省自然科學基金項目(1408085MF125)。章圓圓，碩士生，主研領域：無線網絡。馬寧，碩士生。束永安，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.06.048