稀疏場景下基于網(wǎng)絡(luò)編碼和RSU數(shù)據(jù)傳輸?shù)难芯?/h1>
2017-07-10 10:27:26章圓圓束永安
計算機(jī)應(yīng)用與軟件 2017年6期
章圓圓 馬 寧 束永安
(安徽大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)
稀疏場景下基于網(wǎng)絡(luò)編碼和RSU數(shù)據(jù)傳輸?shù)难芯?/p>
章圓圓 馬 寧 束永安
(安徽大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)
車載自組織網(wǎng)中數(shù)據(jù)傳輸?shù)膱鼍爸饕ㄜ囕v密集的城市道路場景和車輛稀疏的偏遠(yuǎn)地區(qū)，目前大多數(shù)研究針對的是車輛密集場景下數(shù)據(jù)傳輸。在車輛稀疏的車載自組織網(wǎng)中，車輛節(jié)點間相遇的概率受限，因此數(shù)據(jù)傳輸面臨信道負(fù)載大、傳輸延時高、帶寬利用率低等挑戰(zhàn)。為了提高數(shù)據(jù)包在稀疏場景下傳輸性能，提出了基于代間漸進(jìn)編碼技術(shù)和RSU的傳輸策略RORLNC，通過各個編碼代之間的漸進(jìn)編碼操作，可有效防止因丟包引起編碼數(shù)據(jù)包無法被解碼。另外借助RSU尋找最佳轉(zhuǎn)發(fā)車輛節(jié)點，可有效避免編碼數(shù)據(jù)包長期無法被轉(zhuǎn)發(fā)。用NS-2和MOVE軟件進(jìn)行仿真實驗。實驗結(jié)果證明RORLNC比現(xiàn)有的DDR算法具有較高的吞吐率和較低的平均轉(zhuǎn)發(fā)延遲。
車載自組織網(wǎng) 數(shù)據(jù)傳輸 代間漸進(jìn)網(wǎng)絡(luò)編碼 路側(cè)單元
0 引 言
車載自組織網(wǎng)的網(wǎng)絡(luò)拓?fù)渥兓臁㈤g斷性連接、車輛節(jié)點分布不均勻等特點，使得傳統(tǒng)的自組網(wǎng)轉(zhuǎn)發(fā)算法[1]并不適用。在車輛密集場景中，前人從不同方面改進(jìn)數(shù)據(jù)包的傳輸性能[2-4]，并取得了較大的成果。然而在車輛稀疏場景中，車輛節(jié)點間的距離遠(yuǎn)大于車輛節(jié)點的通信范圍，從而無法直接將數(shù)據(jù)包轉(zhuǎn)發(fā)給下一車輛節(jié)點，近年來學(xué)者對該場景的研究進(jìn)展較為緩慢。本文提出了基于代間漸進(jìn)編碼和RSU的數(shù)據(jù)傳輸算法RORLNC，改進(jìn)傳統(tǒng)代內(nèi)隨機(jī)線性編碼，采用代間漸進(jìn)編碼方式，即后一代數(shù)據(jù)包與前一代已編碼的數(shù)據(jù)包再做線性處理，即使前一代編碼丟失，也可以被目的車輛節(jié)點根據(jù)后一編碼代恢復(fù)，借助RSU將編碼數(shù)據(jù)包轉(zhuǎn)發(fā)給可適度值最大的下一車輛節(jié)點，從而降低轉(zhuǎn)發(fā)次數(shù)和提高數(shù)據(jù)傳輸?shù)目煽啃浴?/p>
1 隨機(jī)線性網(wǎng)絡(luò)編碼
隨機(jī)線性網(wǎng)絡(luò)編碼[5]：從最小有限域GF(2)隨機(jī)選擇編碼系數(shù)對信源節(jié)點要廣播的數(shù)據(jù)包進(jìn)行線性編碼處理，圖1展示了傳統(tǒng)隨機(jī)線性編碼的過程。
圖1 隨機(jī)線性網(wǎng)絡(luò)編碼原理圖
在圖1中，假設(shè)源節(jié)點S將要轉(zhuǎn)發(fā)的數(shù)據(jù)分成X1、X2，在有限域中分別選取ε1、ε2和ε3、ε4。向A節(jié)點廣播的數(shù)據(jù)可表示為：Y1=ε1X1+ε2X2，向節(jié)點B廣播的數(shù)據(jù)可表示為：Y2=ε3X1+ε4X2。節(jié)點C分別接收到A、B廣播的數(shù)據(jù)包Y1、Y2，再對Y1、Y2編碼處理，可表示為：Y3=ε5Y1+ε6Y2=ε5(ε1X1+ε2X2)+ε6(ε3X1+ε4X2)，由于節(jié)點D1、D2已經(jīng)分別接收到Y(jié)1、Y2，通過解碼分別得到X1和X2，因此可以達(dá)到理論上的最大流和最小割的上限。
2 RORLNC策略設(shè)計
2.1 基本思想
RORLNC算法在源車輛節(jié)點采用代間漸進(jìn)編碼對數(shù)據(jù)包線性處理，在車輛稀疏的高速路上的每段道路建有路側(cè)單元RSU，RSU與通信范圍內(nèi)的車輛節(jié)點組成一個集群，由RSU管理集群內(nèi)的車輛，掌握車輛的運(yùn)動狀態(tài)(速度、方向、位置、攜帶的編碼數(shù)據(jù)包)。在RSU緩存中換分兩個固定區(qū)域S1、S2，其中S1區(qū)域用來存儲車輛節(jié)點轉(zhuǎn)發(fā)來的編碼數(shù)據(jù)包，并根據(jù)編碼數(shù)據(jù)包的數(shù)量和重復(fù)轉(zhuǎn)發(fā)的次數(shù)建立一個編碼數(shù)據(jù)包優(yōu)先級列表，S2區(qū)域建立一個車輛節(jié)點優(yōu)先級列表，計算經(jīng)過群集中各個車輛節(jié)點的可適度值，可適度值越大優(yōu)先級越高。RSU將編碼數(shù)據(jù)包及時轉(zhuǎn)發(fā)給可適度值最大的車輛節(jié)點，進(jìn)而提高數(shù)據(jù)包在車輛稀疏場景中傳輸效率和降低轉(zhuǎn)發(fā)延遲。
2.2RSU群集建立
RSU定時廣播Rreq消息，周圍車輛節(jié)點接收到Rreq消息，立即發(fā)送Rres消息，并通過該消息建立通信連接，并且由RSU管理周圍各車輛節(jié)點的運(yùn)動狀態(tài)，其中Rreq消息和Rres消息的主要內(nèi)容如下：
Rreq {
Rreq_ID;
//RSU的ID
Rreq_addr;
//RSU的位置
Rreq_snum;
//RSU緩存中數(shù)據(jù)包的數(shù)量
Rreq_iaddr；
//請求RSU通信范圍內(nèi)車輛節(jié)點的位置
Rreq_ive;
//請求RSU通信范圍內(nèi)車輛節(jié)點的速度
Rreq_idir; //請求RSU通信范圍內(nèi)車輛節(jié)點的運(yùn)動方向
}
Rres {
Rres_ID;
//與RSU通信的車輛節(jié)點ID
Rres_RSUaddr;
//與車輛節(jié)點通信的RSU位置
Rres_addr;
//與RSU通信的車輛節(jié)點位置
Rres_ve;
//與RSU通信的車輛節(jié)點速度
Rres_snum;
//車輛節(jié)點攜帶數(shù)據(jù)包的數(shù)量
Rres_mnum;
//車輛節(jié)點間相遇的次數(shù)
Rres_mdir;
//車輛節(jié)點的運(yùn)動方向
}
2.3 源車輛節(jié)點的代間漸進(jìn)式編碼
建立一個簡單的隨機(jī)函數(shù)h(x)[6]對源數(shù)據(jù)包做初始化處理，主要目的是防止中間節(jié)點故意破壞數(shù)據(jù)包。設(shè)隨機(jī)函數(shù)為h(x)=x+c，其中c為隨機(jī)數(shù)，隨機(jī)函數(shù)h(x)將與編碼數(shù)據(jù)包一起被轉(zhuǎn)發(fā)，由目的車輛節(jié)點根據(jù)接收到的h(x)和編碼數(shù)據(jù)包還原出源數(shù)據(jù)包，有效提高編碼數(shù)據(jù)包的可靠性。對每個編碼代數(shù)據(jù)包編號，編碼代源數(shù)據(jù)包表示為I=(I0,I1,…,IK-1)。令c為第1編碼代數(shù)據(jù)包I0，則第i個編碼代數(shù)據(jù)包的初始化表示如下：
(1)
源車輛節(jié)點不再是簡單對每個編碼代數(shù)據(jù)包單獨(dú)進(jìn)行線性編碼操作，而是采用代間漸進(jìn)式編碼方式。具體編碼過程如下：
(4) 同理后面編碼代的數(shù)據(jù)包依次做代間編碼操作，直至各個編碼代的數(shù)據(jù)包都被線性編碼處理，第k代數(shù)據(jù)包的編碼結(jié)果表示為:
(2)
源車輛節(jié)點中各個編碼代的編碼數(shù)據(jù)包與編碼系數(shù)存在線性組合關(guān)系，對應(yīng)的編碼矩陣可以表示為：
(3)
2.4 下一轉(zhuǎn)發(fā)車輛節(jié)點的選擇
車輛與附近的RSU建立了群集，保證了RSU可以管理其群集內(nèi)的車輛節(jié)點。如圖2所示，混合車載網(wǎng)中數(shù)據(jù)傳輸有兩種方式，一種是車輛與車輛通信，另一種是車輛與RSU通信，通過RSU將編碼數(shù)據(jù)包轉(zhuǎn)發(fā)給最佳轉(zhuǎn)發(fā)節(jié)點。受文獻(xiàn)[7]的啟發(fā)，本文提出了車輛節(jié)點運(yùn)動狀態(tài)相似度MS(Motion Similarity)的計算方法，通過車輛節(jié)點MS的值計算出各車輛節(jié)點的可適度VS(Vehicle Suitability)。在RSU中，以TTL為時間周期定時更新群集內(nèi)各車輛節(jié)點的可適度值VSnew，同時根據(jù)車輛節(jié)點的可適度值建立一個車輛節(jié)點優(yōu)先級列表PL(PriorityList)來顯示每個周期中車輛節(jié)點轉(zhuǎn)發(fā)編碼數(shù)據(jù)包的優(yōu)先順序，車輛節(jié)點的可適度越大，其優(yōu)先級越高，反之越低。
圖2 車輛與RSU建立群集
當(dāng)攜帶有編碼數(shù)據(jù)包的轉(zhuǎn)發(fā)車輛節(jié)點i與附近有車輛節(jié)點j相遇，則通過“hello”消息建立通信連接，車輛節(jié)點i根據(jù)“hello”消息中車輛j的運(yùn)動方向做出判斷。由于高速路上車輛節(jié)點間相對運(yùn)動方向只存在相同或是相反，如果車輛節(jié)點j與i運(yùn)動方向相同，這兩個車輛相遇其他車輛是基本相同的，說明車輛節(jié)點j將編碼數(shù)據(jù)包擴(kuò)散到遠(yuǎn)處目的節(jié)點的機(jī)會較小，反之車輛節(jié)點i將編碼數(shù)據(jù)包轉(zhuǎn)發(fā)給車輛節(jié)點j。當(dāng)轉(zhuǎn)發(fā)車輛節(jié)點i周圍不存在與之通信的車輛節(jié)點或存在車輛節(jié)點，但車與自己運(yùn)動方向相同，車輛節(jié)點i則選擇與所屬群集的RSU建立連接。根據(jù)式(4)計算群集內(nèi)車輛節(jié)點的運(yùn)動狀態(tài)相似度MS，RSU采用式(5)更新各車輛節(jié)點的可適度值。
(4)
(5)
在式(5)中，EN表示車輛節(jié)點與其他車輛節(jié)點相遇的次數(shù)，den表示車輛節(jié)點間相遇時運(yùn)動方向不相同的次數(shù)。MS越大，車輛節(jié)點間運(yùn)動方向相同的概率越大，此時編碼數(shù)據(jù)包更不易被轉(zhuǎn)發(fā)到遠(yuǎn)處的目的節(jié)點。在式(5)中，VSold表示車輛節(jié)點之前的可適度，初始值為0。其中參數(shù)α和β滿足α+β=1(α∈(0,1),β∈(0,1))，α和β反映的是可適度VS和車輛節(jié)點運(yùn)動狀態(tài)相似度MS的相關(guān)程度，α的值越大，VS的值與車輛節(jié)點的運(yùn)動狀態(tài)相似度相關(guān)性越大，此時α和β的值是人工設(shè)置的。
2.5 目的車輛節(jié)點的解碼
(6)
(7)
由于r(Z′)=k，根據(jù)可逆矩陣定理，滿秩矩陣可逆。目的車輛節(jié)點根據(jù)解碼式(8)解碼出所有編碼代的數(shù)據(jù)包。
(8)
?
3 仿真實驗與結(jié)果分析
3.1 仿真場景描述
本文采用NS-2和MOVE仿真軟件[9]在車輛稀疏模擬場景下對RORLNC進(jìn)行仿真實驗。本節(jié)采用MOVE仿真軟件對某個區(qū)域的地圖建立車輛節(jié)點移動模型，利用NS-2提供完整的網(wǎng)絡(luò)模擬環(huán)境，因此網(wǎng)絡(luò)模擬軟件NS-2中的節(jié)點可以根據(jù)MOVE設(shè)置的車輛運(yùn)動軌跡的方式運(yùn)動，此時MOVE和NS-2是一種協(xié)作關(guān)系。將RORLNC和DDR在平均轉(zhuǎn)發(fā)延遲、吞吐率、傳輸效率三個方面[10]比較分析。仿真試驗區(qū)域為5 000 m×4 000 m的長方形，道路寬度和長度分別為20 m和5 000 m，并且道路采用雙車道雙向通行。車輛的通信范圍為半徑R=300 m的圓形區(qū)域，車輛運(yùn)動速度為10～20 m/s隨機(jī)變化，區(qū)域中的車輛的數(shù)量為0～120不等，并且車輛的密度隨著場景的變化而改變，服從指數(shù)分布。本文建立的動態(tài)坐標(biāo)軸的橫軸長5 000 m,縱軸長4 000 m，坐標(biāo)軸內(nèi)單元格為10 m×10 m的矩形，車輛在該坐標(biāo)軸內(nèi)的運(yùn)動方向有上、下、左、右。應(yīng)用層生成大小為10 KB源數(shù)據(jù)，在傳輸層被分成10個編碼代數(shù)據(jù)包，并采用UDP協(xié)議將數(shù)據(jù)包發(fā)送到網(wǎng)絡(luò)層，編碼系數(shù)從最小有限域GF(2)中隨機(jī)選擇。采用IEEE802.11b的MAC協(xié)議，車輛向附近車輛廣播“hello”消息的周期TTL=0.5s。哈希函數(shù)為h(x)=x+c，其中c為隨機(jī)常數(shù)，該函數(shù)隨編碼數(shù)據(jù)包一起轉(zhuǎn)發(fā)給下一轉(zhuǎn)發(fā)車輛節(jié)點，將此次仿真時間設(shè)置為400s。為了保證實驗結(jié)果的客觀性，在同一場景下進(jìn)行10次仿真實驗，并取其平均值作為本次試驗結(jié)果。
3.2 實驗結(jié)果分析
1) 吞吐率
如圖3所示，在車輛節(jié)點數(shù)量為0時，在車載自組織網(wǎng)中只有路側(cè)單元RSU，數(shù)據(jù)包無法進(jìn)行傳輸。隨著車輛節(jié)點數(shù)量的增多，RORLNC算法明顯要優(yōu)于DDR。在車輛數(shù)量為100時，本章提出的RORLNC算法吞吐率與DDR算法相比，提高了近60%。分析認(rèn)為，DDR算法只是采用車輛節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，但在車輛稀疏場景下，車輛節(jié)點間大部分時間不能建立完整的數(shù)據(jù)傳輸路徑，導(dǎo)致了車輛節(jié)點的吞吐率較低。而RORLNC算法首先借助RSU作為轉(zhuǎn)發(fā)節(jié)點，并且對接收的編碼數(shù)據(jù)包和經(jīng)過群集中的車輛節(jié)點分別建立了優(yōu)先級列表，在盡可能短的時間內(nèi)將編碼數(shù)據(jù)包轉(zhuǎn)發(fā)給車輛節(jié)點，有效提高了吞吐率。另外在MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略較于DDR協(xié)議明顯提高了吞吐率。
圖3 車輛節(jié)點數(shù)量對吞吐率的影響情況
2) 轉(zhuǎn)發(fā)平均時延
圖4顯示了兩種算法的數(shù)據(jù)包平均轉(zhuǎn)發(fā)延遲隨車輛節(jié)點數(shù)量變化的曲線。從圖中可知，當(dāng)車輛節(jié)點數(shù)量極少時，由于車輛節(jié)點間相遇的機(jī)會有限，數(shù)據(jù)包轉(zhuǎn)發(fā)的概率較低，兩種算法的平均延遲都較高。隨著車輛節(jié)點數(shù)量的增加，兩種算法都有明顯降低，但與車輛密集的場景相比，該場景下車輛節(jié)點的數(shù)量仍不能使數(shù)據(jù)包在車輛節(jié)點間直接進(jìn)行傳輸。由于RORLNC借助了RSU，由RSU以TTL為周期選擇本地群集中可適度最高的車輛節(jié)點(優(yōu)先級最高)作為下一轉(zhuǎn)發(fā)車輛節(jié)點，因此RORLNC算法的平均延遲整體上要低于DDR。MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略較于DDR協(xié)議，轉(zhuǎn)發(fā)平均時延得到了降低。
圖4 車輛節(jié)點數(shù)量對平均轉(zhuǎn)發(fā)時延的影響情況
3) 數(shù)據(jù)傳輸效率
圖5描述了數(shù)據(jù)傳輸效率與車輛節(jié)點數(shù)量的關(guān)系。從圖中可以看出，兩種算法的效率隨車輛節(jié)點數(shù)量的增加，總體上呈上升趨勢，原因是基于分簇和基于車輛路徑近似度的思想都是與車輛建立連接，尋找最佳的轉(zhuǎn)發(fā)車輛節(jié)點，可在車輛稀疏場景中，車輛間的連接機(jī)會較少，無法建立有效的連接進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。RORLNC算法的效率明顯較高，是因其設(shè)置了多個判斷，當(dāng)攜帶編碼數(shù)據(jù)的車輛節(jié)點附近存在通信機(jī)會的車輛節(jié)點，則將編碼數(shù)據(jù)包發(fā)送給行駛方向相反的下一車輛節(jié)點，否則與附近的RSU建立連接，由RSU將編碼數(shù)據(jù)包在合適的時間轉(zhuǎn)發(fā)給在時間TTL內(nèi)優(yōu)先級最高的車輛節(jié)點，從而提高數(shù)據(jù)的傳輸效率。MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略提高了數(shù)據(jù)包的傳輸效率。
圖5 車輛節(jié)點數(shù)量對傳輸效率的影響情況
4 結(jié) 語
為進(jìn)一步提高數(shù)據(jù)包在車輛稀疏場景下傳輸性能，本文首先在傳統(tǒng)的隨機(jī)線性網(wǎng)絡(luò)編碼基礎(chǔ)上，提出了一種的基于RSU的代間漸進(jìn)式網(wǎng)絡(luò)編碼RORLNC。在RORLNC中，首先建立一個哈希函數(shù)對源數(shù)據(jù)包初始化，防止數(shù)據(jù)包被竊聽，然后依次對每個代間數(shù)據(jù)包做漸進(jìn)編碼操作，有效提高了編碼數(shù)據(jù)包的可靠性傳輸，保證了編碼數(shù)據(jù)包能被解碼。關(guān)于轉(zhuǎn)發(fā)車輛節(jié)點的選擇，本文則借助RSU計算周圍車輛節(jié)點的可適度值。通過MOVE和NS-2仿真軟件對DDR和RORLNC的數(shù)據(jù)傳輸性能進(jìn)行比較和分析，MOVE和NS-2仿真實驗結(jié)果驗證了ORLNC算法在整體性能上要優(yōu)于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] 盧怡睿,俞研,吳家順.基于網(wǎng)絡(luò)編碼與分簇的車載自組網(wǎng)數(shù)據(jù)分發(fā)算法[J].計算機(jī)應(yīng)用,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] 胡皓.容遲網(wǎng)絡(luò)的路由技術(shù)研究[D].北京:北京理工大學(xué),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。安徽省自然科學(xué)基金項目(1408085MF125)。章圓圓，碩士生，主研領(lǐng)域：無線網(wǎng)絡(luò)。馬寧，碩士生。束永安，教授。
TP393
A
10.3969/j.issn.1000-386x.2017.06.048
章圓圓 馬 寧 束永安
(安徽大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)
稀疏場景下基于網(wǎng)絡(luò)編碼和RSU數(shù)據(jù)傳輸?shù)难芯?/p>
章圓圓 馬 寧 束永安
(安徽大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)
車載自組織網(wǎng)中數(shù)據(jù)傳輸?shù)膱鼍爸饕ㄜ囕v密集的城市道路場景和車輛稀疏的偏遠(yuǎn)地區(qū)，目前大多數(shù)研究針對的是車輛密集場景下數(shù)據(jù)傳輸。在車輛稀疏的車載自組織網(wǎng)中，車輛節(jié)點間相遇的概率受限，因此數(shù)據(jù)傳輸面臨信道負(fù)載大、傳輸延時高、帶寬利用率低等挑戰(zhàn)。為了提高數(shù)據(jù)包在稀疏場景下傳輸性能，提出了基于代間漸進(jìn)編碼技術(shù)和RSU的傳輸策略RORLNC，通過各個編碼代之間的漸進(jìn)編碼操作，可有效防止因丟包引起編碼數(shù)據(jù)包無法被解碼。另外借助RSU尋找最佳轉(zhuǎn)發(fā)車輛節(jié)點，可有效避免編碼數(shù)據(jù)包長期無法被轉(zhuǎn)發(fā)。用NS-2和MOVE軟件進(jìn)行仿真實驗。實驗結(jié)果證明RORLNC比現(xiàn)有的DDR算法具有較高的吞吐率和較低的平均轉(zhuǎn)發(fā)延遲。
車載自組織網(wǎng) 數(shù)據(jù)傳輸 代間漸進(jìn)網(wǎng)絡(luò)編碼 路側(cè)單元
0 引 言
車載自組織網(wǎng)的網(wǎng)絡(luò)拓?fù)渥兓臁㈤g斷性連接、車輛節(jié)點分布不均勻等特點，使得傳統(tǒng)的自組網(wǎng)轉(zhuǎn)發(fā)算法[1]并不適用。在車輛密集場景中，前人從不同方面改進(jìn)數(shù)據(jù)包的傳輸性能[2-4]，并取得了較大的成果。然而在車輛稀疏場景中，車輛節(jié)點間的距離遠(yuǎn)大于車輛節(jié)點的通信范圍，從而無法直接將數(shù)據(jù)包轉(zhuǎn)發(fā)給下一車輛節(jié)點，近年來學(xué)者對該場景的研究進(jìn)展較為緩慢。本文提出了基于代間漸進(jìn)編碼和RSU的數(shù)據(jù)傳輸算法RORLNC，改進(jìn)傳統(tǒng)代內(nèi)隨機(jī)線性編碼，采用代間漸進(jìn)編碼方式，即后一代數(shù)據(jù)包與前一代已編碼的數(shù)據(jù)包再做線性處理，即使前一代編碼丟失，也可以被目的車輛節(jié)點根據(jù)后一編碼代恢復(fù)，借助RSU將編碼數(shù)據(jù)包轉(zhuǎn)發(fā)給可適度值最大的下一車輛節(jié)點，從而降低轉(zhuǎn)發(fā)次數(shù)和提高數(shù)據(jù)傳輸?shù)目煽啃浴?/p>
1 隨機(jī)線性網(wǎng)絡(luò)編碼
隨機(jī)線性網(wǎng)絡(luò)編碼[5]：從最小有限域GF(2)隨機(jī)選擇編碼系數(shù)對信源節(jié)點要廣播的數(shù)據(jù)包進(jìn)行線性編碼處理，圖1展示了傳統(tǒng)隨機(jī)線性編碼的過程。
圖1 隨機(jī)線性網(wǎng)絡(luò)編碼原理圖
在圖1中，假設(shè)源節(jié)點S將要轉(zhuǎn)發(fā)的數(shù)據(jù)分成X1、X2，在有限域中分別選取ε1、ε2和ε3、ε4。向A節(jié)點廣播的數(shù)據(jù)可表示為：Y1=ε1X1+ε2X2，向節(jié)點B廣播的數(shù)據(jù)可表示為：Y2=ε3X1+ε4X2。節(jié)點C分別接收到A、B廣播的數(shù)據(jù)包Y1、Y2，再對Y1、Y2編碼處理，可表示為：Y3=ε5Y1+ε6Y2=ε5(ε1X1+ε2X2)+ε6(ε3X1+ε4X2)，由于節(jié)點D1、D2已經(jīng)分別接收到Y(jié)1、Y2，通過解碼分別得到X1和X2，因此可以達(dá)到理論上的最大流和最小割的上限。
2 RORLNC策略設(shè)計
2.1 基本思想
RORLNC算法在源車輛節(jié)點采用代間漸進(jìn)編碼對數(shù)據(jù)包線性處理，在車輛稀疏的高速路上的每段道路建有路側(cè)單元RSU，RSU與通信范圍內(nèi)的車輛節(jié)點組成一個集群，由RSU管理集群內(nèi)的車輛，掌握車輛的運(yùn)動狀態(tài)(速度、方向、位置、攜帶的編碼數(shù)據(jù)包)。在RSU緩存中換分兩個固定區(qū)域S1、S2，其中S1區(qū)域用來存儲車輛節(jié)點轉(zhuǎn)發(fā)來的編碼數(shù)據(jù)包，并根據(jù)編碼數(shù)據(jù)包的數(shù)量和重復(fù)轉(zhuǎn)發(fā)的次數(shù)建立一個編碼數(shù)據(jù)包優(yōu)先級列表，S2區(qū)域建立一個車輛節(jié)點優(yōu)先級列表，計算經(jīng)過群集中各個車輛節(jié)點的可適度值，可適度值越大優(yōu)先級越高。RSU將編碼數(shù)據(jù)包及時轉(zhuǎn)發(fā)給可適度值最大的車輛節(jié)點，進(jìn)而提高數(shù)據(jù)包在車輛稀疏場景中傳輸效率和降低轉(zhuǎn)發(fā)延遲。
2.2RSU群集建立
RSU定時廣播Rreq消息，周圍車輛節(jié)點接收到Rreq消息，立即發(fā)送Rres消息，并通過該消息建立通信連接，并且由RSU管理周圍各車輛節(jié)點的運(yùn)動狀態(tài)，其中Rreq消息和Rres消息的主要內(nèi)容如下：
Rreq {
Rreq_ID;
//RSU的ID
Rreq_addr;
//RSU的位置
Rreq_snum;
//RSU緩存中數(shù)據(jù)包的數(shù)量
Rreq_iaddr；
//請求RSU通信范圍內(nèi)車輛節(jié)點的位置
Rreq_ive;
//請求RSU通信范圍內(nèi)車輛節(jié)點的速度
Rreq_idir; //請求RSU通信范圍內(nèi)車輛節(jié)點的運(yùn)動方向
}
Rres {
Rres_ID;
//與RSU通信的車輛節(jié)點ID
Rres_RSUaddr;
//與車輛節(jié)點通信的RSU位置
Rres_addr;
//與RSU通信的車輛節(jié)點位置
Rres_ve;
//與RSU通信的車輛節(jié)點速度
Rres_snum;
//車輛節(jié)點攜帶數(shù)據(jù)包的數(shù)量
Rres_mnum;
//車輛節(jié)點間相遇的次數(shù)
Rres_mdir;
//車輛節(jié)點的運(yùn)動方向
}
2.3 源車輛節(jié)點的代間漸進(jìn)式編碼
建立一個簡單的隨機(jī)函數(shù)h(x)[6]對源數(shù)據(jù)包做初始化處理，主要目的是防止中間節(jié)點故意破壞數(shù)據(jù)包。設(shè)隨機(jī)函數(shù)為h(x)=x+c，其中c為隨機(jī)數(shù)，隨機(jī)函數(shù)h(x)將與編碼數(shù)據(jù)包一起被轉(zhuǎn)發(fā)，由目的車輛節(jié)點根據(jù)接收到的h(x)和編碼數(shù)據(jù)包還原出源數(shù)據(jù)包，有效提高編碼數(shù)據(jù)包的可靠性。對每個編碼代數(shù)據(jù)包編號，編碼代源數(shù)據(jù)包表示為I=(I0,I1,…,IK-1)。令c為第1編碼代數(shù)據(jù)包I0，則第i個編碼代數(shù)據(jù)包的初始化表示如下：
(1)
源車輛節(jié)點不再是簡單對每個編碼代數(shù)據(jù)包單獨(dú)進(jìn)行線性編碼操作，而是采用代間漸進(jìn)式編碼方式。具體編碼過程如下：
(4) 同理后面編碼代的數(shù)據(jù)包依次做代間編碼操作，直至各個編碼代的數(shù)據(jù)包都被線性編碼處理，第k代數(shù)據(jù)包的編碼結(jié)果表示為:
(2)
源車輛節(jié)點中各個編碼代的編碼數(shù)據(jù)包與編碼系數(shù)存在線性組合關(guān)系，對應(yīng)的編碼矩陣可以表示為：
(3)
2.4 下一轉(zhuǎn)發(fā)車輛節(jié)點的選擇
車輛與附近的RSU建立了群集，保證了RSU可以管理其群集內(nèi)的車輛節(jié)點。如圖2所示，混合車載網(wǎng)中數(shù)據(jù)傳輸有兩種方式，一種是車輛與車輛通信，另一種是車輛與RSU通信，通過RSU將編碼數(shù)據(jù)包轉(zhuǎn)發(fā)給最佳轉(zhuǎn)發(fā)節(jié)點。受文獻(xiàn)[7]的啟發(fā)，本文提出了車輛節(jié)點運(yùn)動狀態(tài)相似度MS(Motion Similarity)的計算方法，通過車輛節(jié)點MS的值計算出各車輛節(jié)點的可適度VS(Vehicle Suitability)。在RSU中，以TTL為時間周期定時更新群集內(nèi)各車輛節(jié)點的可適度值VSnew，同時根據(jù)車輛節(jié)點的可適度值建立一個車輛節(jié)點優(yōu)先級列表PL(PriorityList)來顯示每個周期中車輛節(jié)點轉(zhuǎn)發(fā)編碼數(shù)據(jù)包的優(yōu)先順序，車輛節(jié)點的可適度越大，其優(yōu)先級越高，反之越低。
圖2 車輛與RSU建立群集
當(dāng)攜帶有編碼數(shù)據(jù)包的轉(zhuǎn)發(fā)車輛節(jié)點i與附近有車輛節(jié)點j相遇，則通過“hello”消息建立通信連接，車輛節(jié)點i根據(jù)“hello”消息中車輛j的運(yùn)動方向做出判斷。由于高速路上車輛節(jié)點間相對運(yùn)動方向只存在相同或是相反，如果車輛節(jié)點j與i運(yùn)動方向相同，這兩個車輛相遇其他車輛是基本相同的，說明車輛節(jié)點j將編碼數(shù)據(jù)包擴(kuò)散到遠(yuǎn)處目的節(jié)點的機(jī)會較小，反之車輛節(jié)點i將編碼數(shù)據(jù)包轉(zhuǎn)發(fā)給車輛節(jié)點j。當(dāng)轉(zhuǎn)發(fā)車輛節(jié)點i周圍不存在與之通信的車輛節(jié)點或存在車輛節(jié)點，但車與自己運(yùn)動方向相同，車輛節(jié)點i則選擇與所屬群集的RSU建立連接。根據(jù)式(4)計算群集內(nèi)車輛節(jié)點的運(yùn)動狀態(tài)相似度MS，RSU采用式(5)更新各車輛節(jié)點的可適度值。
(4)
(5)
在式(5)中，EN表示車輛節(jié)點與其他車輛節(jié)點相遇的次數(shù)，den表示車輛節(jié)點間相遇時運(yùn)動方向不相同的次數(shù)。MS越大，車輛節(jié)點間運(yùn)動方向相同的概率越大，此時編碼數(shù)據(jù)包更不易被轉(zhuǎn)發(fā)到遠(yuǎn)處的目的節(jié)點。在式(5)中，VSold表示車輛節(jié)點之前的可適度，初始值為0。其中參數(shù)α和β滿足α+β=1(α∈(0,1),β∈(0,1))，α和β反映的是可適度VS和車輛節(jié)點運(yùn)動狀態(tài)相似度MS的相關(guān)程度，α的值越大，VS的值與車輛節(jié)點的運(yùn)動狀態(tài)相似度相關(guān)性越大，此時α和β的值是人工設(shè)置的。
2.5 目的車輛節(jié)點的解碼
(6)
(7)
由于r(Z′)=k，根據(jù)可逆矩陣定理，滿秩矩陣可逆。目的車輛節(jié)點根據(jù)解碼式(8)解碼出所有編碼代的數(shù)據(jù)包。
(8)
?
3 仿真實驗與結(jié)果分析
3.1 仿真場景描述
本文采用NS-2和MOVE仿真軟件[9]在車輛稀疏模擬場景下對RORLNC進(jìn)行仿真實驗。本節(jié)采用MOVE仿真軟件對某個區(qū)域的地圖建立車輛節(jié)點移動模型，利用NS-2提供完整的網(wǎng)絡(luò)模擬環(huán)境，因此網(wǎng)絡(luò)模擬軟件NS-2中的節(jié)點可以根據(jù)MOVE設(shè)置的車輛運(yùn)動軌跡的方式運(yùn)動，此時MOVE和NS-2是一種協(xié)作關(guān)系。將RORLNC和DDR在平均轉(zhuǎn)發(fā)延遲、吞吐率、傳輸效率三個方面[10]比較分析。仿真試驗區(qū)域為5 000 m×4 000 m的長方形，道路寬度和長度分別為20 m和5 000 m，并且道路采用雙車道雙向通行。車輛的通信范圍為半徑R=300 m的圓形區(qū)域，車輛運(yùn)動速度為10～20 m/s隨機(jī)變化，區(qū)域中的車輛的數(shù)量為0～120不等，并且車輛的密度隨著場景的變化而改變，服從指數(shù)分布。本文建立的動態(tài)坐標(biāo)軸的橫軸長5 000 m,縱軸長4 000 m，坐標(biāo)軸內(nèi)單元格為10 m×10 m的矩形，車輛在該坐標(biāo)軸內(nèi)的運(yùn)動方向有上、下、左、右。應(yīng)用層生成大小為10 KB源數(shù)據(jù)，在傳輸層被分成10個編碼代數(shù)據(jù)包，并采用UDP協(xié)議將數(shù)據(jù)包發(fā)送到網(wǎng)絡(luò)層，編碼系數(shù)從最小有限域GF(2)中隨機(jī)選擇。采用IEEE802.11b的MAC協(xié)議，車輛向附近車輛廣播“hello”消息的周期TTL=0.5s。哈希函數(shù)為h(x)=x+c，其中c為隨機(jī)常數(shù)，該函數(shù)隨編碼數(shù)據(jù)包一起轉(zhuǎn)發(fā)給下一轉(zhuǎn)發(fā)車輛節(jié)點，將此次仿真時間設(shè)置為400s。為了保證實驗結(jié)果的客觀性，在同一場景下進(jìn)行10次仿真實驗，并取其平均值作為本次試驗結(jié)果。
3.2 實驗結(jié)果分析
1) 吞吐率
如圖3所示，在車輛節(jié)點數(shù)量為0時，在車載自組織網(wǎng)中只有路側(cè)單元RSU，數(shù)據(jù)包無法進(jìn)行傳輸。隨著車輛節(jié)點數(shù)量的增多，RORLNC算法明顯要優(yōu)于DDR。在車輛數(shù)量為100時，本章提出的RORLNC算法吞吐率與DDR算法相比，提高了近60%。分析認(rèn)為，DDR算法只是采用車輛節(jié)點作為轉(zhuǎn)發(fā)節(jié)點，但在車輛稀疏場景下，車輛節(jié)點間大部分時間不能建立完整的數(shù)據(jù)傳輸路徑，導(dǎo)致了車輛節(jié)點的吞吐率較低。而RORLNC算法首先借助RSU作為轉(zhuǎn)發(fā)節(jié)點，并且對接收的編碼數(shù)據(jù)包和經(jīng)過群集中的車輛節(jié)點分別建立了優(yōu)先級列表，在盡可能短的時間內(nèi)將編碼數(shù)據(jù)包轉(zhuǎn)發(fā)給車輛節(jié)點，有效提高了吞吐率。另外在MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略較于DDR協(xié)議明顯提高了吞吐率。
圖3 車輛節(jié)點數(shù)量對吞吐率的影響情況
2) 轉(zhuǎn)發(fā)平均時延
圖4顯示了兩種算法的數(shù)據(jù)包平均轉(zhuǎn)發(fā)延遲隨車輛節(jié)點數(shù)量變化的曲線。從圖中可知，當(dāng)車輛節(jié)點數(shù)量極少時，由于車輛節(jié)點間相遇的機(jī)會有限，數(shù)據(jù)包轉(zhuǎn)發(fā)的概率較低，兩種算法的平均延遲都較高。隨著車輛節(jié)點數(shù)量的增加，兩種算法都有明顯降低，但與車輛密集的場景相比，該場景下車輛節(jié)點的數(shù)量仍不能使數(shù)據(jù)包在車輛節(jié)點間直接進(jìn)行傳輸。由于RORLNC借助了RSU，由RSU以TTL為周期選擇本地群集中可適度最高的車輛節(jié)點(優(yōu)先級最高)作為下一轉(zhuǎn)發(fā)車輛節(jié)點，因此RORLNC算法的平均延遲整體上要低于DDR。MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略較于DDR協(xié)議，轉(zhuǎn)發(fā)平均時延得到了降低。
圖4 車輛節(jié)點數(shù)量對平均轉(zhuǎn)發(fā)時延的影響情況
3) 數(shù)據(jù)傳輸效率
圖5描述了數(shù)據(jù)傳輸效率與車輛節(jié)點數(shù)量的關(guān)系。從圖中可以看出，兩種算法的效率隨車輛節(jié)點數(shù)量的增加，總體上呈上升趨勢，原因是基于分簇和基于車輛路徑近似度的思想都是與車輛建立連接，尋找最佳的轉(zhuǎn)發(fā)車輛節(jié)點，可在車輛稀疏場景中，車輛間的連接機(jī)會較少，無法建立有效的連接進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)。RORLNC算法的效率明顯較高，是因其設(shè)置了多個判斷，當(dāng)攜帶編碼數(shù)據(jù)的車輛節(jié)點附近存在通信機(jī)會的車輛節(jié)點，則將編碼數(shù)據(jù)包發(fā)送給行駛方向相反的下一車輛節(jié)點，否則與附近的RSU建立連接，由RSU將編碼數(shù)據(jù)包在合適的時間轉(zhuǎn)發(fā)給在時間TTL內(nèi)優(yōu)先級最高的車輛節(jié)點，從而提高數(shù)據(jù)的傳輸效率。MOVE和NS-2兩個仿真軟件中的實驗表明該傳輸策略提高了數(shù)據(jù)包的傳輸效率。
圖5 車輛節(jié)點數(shù)量對傳輸效率的影響情況
4 結(jié) 語
為進(jìn)一步提高數(shù)據(jù)包在車輛稀疏場景下傳輸性能，本文首先在傳統(tǒng)的隨機(jī)線性網(wǎng)絡(luò)編碼基礎(chǔ)上，提出了一種的基于RSU的代間漸進(jìn)式網(wǎng)絡(luò)編碼RORLNC。在RORLNC中，首先建立一個哈希函數(shù)對源數(shù)據(jù)包初始化，防止數(shù)據(jù)包被竊聽，然后依次對每個代間數(shù)據(jù)包做漸進(jìn)編碼操作，有效提高了編碼數(shù)據(jù)包的可靠性傳輸，保證了編碼數(shù)據(jù)包能被解碼。關(guān)于轉(zhuǎn)發(fā)車輛節(jié)點的選擇，本文則借助RSU計算周圍車輛節(jié)點的可適度值。通過MOVE和NS-2仿真軟件對DDR和RORLNC的數(shù)據(jù)傳輸性能進(jìn)行比較和分析，MOVE和NS-2仿真實驗結(jié)果驗證了ORLNC算法在整體性能上要優(yōu)于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] 盧怡睿,俞研,吳家順.基于網(wǎng)絡(luò)編碼與分簇的車載自組網(wǎng)數(shù)據(jù)分發(fā)算法[J].計算機(jī)應(yīng)用,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] 胡皓.容遲網(wǎng)絡(luò)的路由技術(shù)研究[D].北京:北京理工大學(xué),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。安徽省自然科學(xué)基金項目(1408085MF125)。章圓圓，碩士生，主研領(lǐng)域：無線網(wǎng)絡(luò)。馬寧，碩士生。束永安，教授。
TP393
A
10.3969/j.issn.1000-386x.2017.06.048
