吳芬芬+王嫣

摘 要： 將路側(cè)設(shè)備RSUs作為車載網(wǎng)絡(luò)VANETs的緩沖點，可緩解車與車V2V之間連通的間歇性問題。然而，由于車輛的快速移動以及RSU短的傳輸距離，車輛駐留同一個RSU的時間很短。盡管廣播技術(shù)能夠有效地提高廣播帶寬利用率以及系統(tǒng)響應(yīng)時間。但RSU采用廣播技術(shù)前需要獲取車輛緩存數(shù)據(jù)項的先驗知識。因此，車輛需要向RSU服務(wù)器上傳緩存信息，浪費了帶寬。為此，針對基于RSUs的VANETs，提出基于網(wǎng)絡(luò)編碼的車與路邊設(shè)施V2R通信的數(shù)據(jù)傳輸算法NCDD。NCDD算法允許車輛不必向RSU服務(wù)器上傳它們的緩沖信息，并利用網(wǎng)絡(luò)編碼提高RSU的廣播性能，仿真結(jié)果也證實了NCDD算法能夠有效地降低截止期錯失率和系統(tǒng)響應(yīng)時間。

關(guān)鍵詞： 車載網(wǎng)絡(luò)； 路側(cè)設(shè)備； 數(shù)據(jù)傳輸； 網(wǎng)絡(luò)編碼； 截止期錯失率

中圖分類號： TN919.3+1?34； TP393 文獻標識碼： A 文章編號： 1004?373X（2017）11?0127?05

Research on V2R data transmission performance optimization based on network coding

WU Fenfen1， WANG Yan2

（1. Department of Traffic Information Engineering， Henan Communication Vocational Technology College， Zhengzhou 450000， China；

2. School of Information Engineering， Zhongzhou University， Zhengzhou 450044， China）

Abstract： The road side units （RSUs） acting as a buffer point of VANETs （vehicular Ad Hoc networks） can alleviate the intermittent connectivity issue of vehicle?to?vehicle （V2V）. The vehicle spends short time on stopping at the same RSU due to the fast vehicle mobility and short RSU transmission range. Although the broadcast technology can improve the broadcast ban?dwidth usage efficiency and system response time effectively， but the RSU before using broadcast technology needs to acquire the prior knowledge of vehicle′s cached data items. Therefore， the vehicle needs to upload the cache information to the RSU server， which wastes the bandwidth. Aiming at VANETs based on RSUs， a network coding?based data dissemination （NCDD） algorithm of V2R is proposed. The NCDD algorithm allows vehicles not to upload their cache information to RSU server. The network coding is used to improve the RSU broadcast performance. The simulation results verify that the NCDD algorithm can reduce the deadline miss ratio and system response time.

Keywords： vehicular Ad Hoc network； road side unit； data transmission； network coding； deadline miss ratio

0 引 言

作為智能交通系統(tǒng)ITS（Intelligent Transportation System）最有前景的技術(shù)，車載網(wǎng)絡(luò)VANETs（Vehicular Ad Hoc Networks）受到廣泛關(guān)注。VANETs屬于移動自組織網(wǎng)絡(luò)的特例，其能夠提供多類服務(wù)，包括安全、交通管理、舒適駕駛以及娛樂[1?3]。典型的VANETs結(jié)構(gòu)如圖1所示，車與車之間構(gòu)成車間通信V2V（Vehicle?to?Vehicle），車與路邊設(shè)施之間構(gòu)成V2R（Vehicle?to?RoadSide）通信。

然而，與移動自組織網(wǎng)絡(luò)不同，VANETs存在鮮明的特性。首先，車輛的快速移動，加劇了網(wǎng)絡(luò)拓撲變化；其次，VANETs采用基于IEEE 802.p無線通信技術(shù)[4]。短的通信距離導(dǎo)致車間連通時間非常短。

為此，在路邊部署RSU，將其作為靜態(tài)單元，起到通信緩沖作用。在這種情況下，在RSU與車輛間完成有效的數(shù)據(jù)傳輸是非常必要的，否則車輛將不能及時獲取其所需的數(shù)據(jù)，這也違背了部署VANETs的目的。為此，本文以V2R通信為對象，研究V2R的數(shù)據(jù)傳輸。

按需廣播技術(shù)廣泛應(yīng)用于無線環(huán)境[5]，用于大面積的傳輸數(shù)據(jù)。然而，由于傳統(tǒng)廣播技術(shù)每次廣播時，僅廣播一條數(shù)據(jù)項DAIT（Data Item）。這種廣播策略不能最大化廣播信道帶寬，可能也無法保持截止期錯失率DMR（Deadline Miss Ratio）和系統(tǒng)響應(yīng)時間的性能。而網(wǎng)絡(luò)編碼是解決此問題的可行辦法之一。

利用網(wǎng)絡(luò)編碼技術(shù)，將多個DAIT編碼成一個廣播包，然后再廣播[6]。然而，RSU服務(wù)器在應(yīng)用網(wǎng)絡(luò)編碼時，需要獲取車輛的請求和緩沖區(qū)內(nèi)的DAIT所有信息[7?8]。將車輛緩存信息上傳至服務(wù)器，增加了額外開銷，也降低了RSU服務(wù)器的帶寬資源。

為此，本文引用網(wǎng)絡(luò)編碼技術(shù)，致使車輛不必上傳它們的緩存信息。RSU服務(wù)器跟蹤車輛請求的DAIT，并利用主干連接[9]向鄰居RSU發(fā)送緩存更新。此外，假定RSU能夠維持在其通信覆蓋內(nèi)的車輛以及它們的位置[10]。本文提出NCDD算法的目的就是減少DMR，并降低系統(tǒng)響應(yīng)時間。

1 系統(tǒng)模型及約束條件

系統(tǒng)模型如圖2所示。每個RSU由請求信道ReqCH（Request CHannel）和響應(yīng)信道ResCH（Respone CHannel）兩個信道組成。當(dāng)一車輛駛?cè)隦SU覆蓋范圍內(nèi)，若該車輛在其局部緩沖區(qū)內(nèi)未找到其所需的數(shù)據(jù)項DAIT（Data Item），它就通過RSU的信道ReqCH發(fā)送請求DAIT。

此外，每個RSU為請求包設(shè)定了一個服務(wù)隊列。當(dāng)不能滿足車輛所請求的請求包時，RSU就將該請求包從服務(wù)隊列中移除。依據(jù)調(diào)度算法[11]，RSU先選擇一個合適的DAIT，然后根據(jù)這些被選的DAIT，利用低開銷的XOR操作編碼，將這些DAIT編碼成一個數(shù)據(jù)包，最后，通過ResCH信道廣播該已編碼的數(shù)據(jù)包。

一旦接收了已編碼數(shù)據(jù)包，車輛就利用自己緩存區(qū)內(nèi)的DAIT進行解碼，獲取自己所需的DAIT，并再存入緩存區(qū)。此外，RSU能夠知道是哪輛車接收了哪個DAIT。

系統(tǒng)采用文獻[12]的LRU（Least Recently Used）緩存替代政策。若已滿足請求，就從服務(wù)隊列移除。此外，若車輛移出當(dāng)前RSU覆蓋范圍，進入新的RSU覆蓋范圍內(nèi)時，當(dāng)前RSU就向新RSU發(fā)送相應(yīng)的緩存信息。

2 NCDD算法

2.1 請求包的格式

假定網(wǎng)絡(luò)內(nèi)輛車，即個RSU，即若車輛向遞交一個請求，且表示為。請求的格式如下所示：

（1）

式中：為的ID號；表示請求的數(shù)據(jù)DAIT號；表示產(chǎn)生的時間。

假定服從均勻分布：

（2）

式中：表示駐留在RSU內(nèi)的最長時間，定義如下：

（3）

式中：表示RSU通信覆蓋的半徑；表示的移動速度。

式（2）中，表示需求的服務(wù)時間；表示的截止時間。一旦到達RSU就把從服務(wù)隊列中移出。而表示移動的方向。

2.2 網(wǎng)絡(luò)編碼

為了編碼決策，RSU服務(wù)器需要獲取車輛的請求和緩沖DAIT信息[7]。因此，引用圖論理論[8]。假定，其中頂點集表示車輛產(chǎn)生的請求DAIT集合，具體而言，表示車輛產(chǎn)生的DAIT 同時，利用邊集反映內(nèi)兩頂點間關(guān)系。

對于任意兩個頂點如果滿足以下兩個條件中的任何一個條件，就存在有向邊。

（1） 如果且，即兩輛不同的車請求相同的DAIT，則在和間存在邊；

（2） 如果且車輛在其緩存區(qū)內(nèi)有DAIT 同時車輛在請求DAIT 而車輛在其緩存區(qū)內(nèi)有DAIT 同時車輛在請求DAIT 換而言之，這兩個車輛緩存彼此所請求的DAIT。在這種情況下，在和間也存在邊。RSU服務(wù)器只要廣播車輛通過簡單的XOR操作分別可提取DAIT。

針對圖，定義一個子圖，致使該子圖內(nèi)每兩個頂點均有邊連通。假定是內(nèi)的任意一個子圖，即相應(yīng)地，在內(nèi)請求數(shù)據(jù)DAIT集表示為

（4）

相應(yīng)地，假定內(nèi)所包含的車輛集表示為。

如圖3，圖4所示，其描述一個圖論示例。首先，圖2顯示了一個RSU包含了5個車輛所請求的DAIT。如車輛請求DAIT為，而車輛請求DAIT為。相應(yīng)地，圖3的右邊顯示了各車輛的緩存DAIT，如車輛緩存區(qū)域存有。

將圖3所示5個車輛轉(zhuǎn)化成圖，如圖4所示。依據(jù)各個車輛所請求的DAIT關(guān)系，構(gòu)建車輛的邊。其中，黑粗線構(gòu)成了子圖。

令表示一個編碼包。在子圖內(nèi)，每個頂點代表一輛車。依據(jù)子圖的特性對任何車輛如果它便能夠從編碼包內(nèi)提出自己所需的DAIT 。因此，只要在內(nèi)廣播編碼包，就能使得各相應(yīng)車輛獲取自己所需的數(shù)據(jù)。

2.3 最大化

接下來，需要討論的是將多少個DAIT編碼成一個數(shù)據(jù)包。從編碼的角度，每個已編碼的數(shù)據(jù)包包含DAIT的個數(shù)越多越好，即最大化問題。該問題等價于最大化子圖。

對于任意頂點（車輛請求的DAIT為），從圖中尋找最大子圖。然后，再將中的DAIT集產(chǎn)生一個編碼包最后廣播此編碼包。如圖4所示，黑色粗線表示一個最大子圖。從圖4可知，相應(yīng)地，最后，RSU服務(wù)器就編碼內(nèi)的數(shù)據(jù)，即然后廣播編碼數(shù)據(jù)包。

在圖中尋找最大化子圖是個NP問題[13]。據(jù)此，研究人員提出不同的近似算法。本文采納文獻[14]提出的近似算法求解。

2.4 緩存區(qū)域信息更新

由于車輛是非靜態(tài)的，沿著道路移動。為此，本文引用Manhattan 移動模型[4]模擬車輛移動。NCDD算法利用RSU管理車輛緩存區(qū)內(nèi)的信息，而不是每次在決策編碼前，由RSU向車輛申請，并由車輛上傳緩存區(qū)域信息。如圖5所示，最初，沒有關(guān)于車輛的緩存區(qū)域信息。當(dāng)車輛進入的通信范圍內(nèi)，就產(chǎn)生請求再等待是否能滿足其需求。一旦滿足，就更新和的緩存區(qū)域信息。

當(dāng)離開的覆蓋區(qū)域時，RSUi就利用主干連接，先聯(lián)系到覆蓋的下一RSU（RSUj），然后再向其傳輸車輛的緩存區(qū)域信息。注意到，RSUi能夠利用知道將駛?cè)胄碌腞SU（RSUj）。隨著時間的推移，車輛越來越靠近。

2.5 NCDD算法流程

NCDD算法流程如圖6所示。

NCDD算法流程的步驟如下：

步驟1：當(dāng)RSU從鄰居RSU接收到車輛更新緩存信息時，就更新車輛的緩存信息；

步驟2：在RSU的服務(wù)隊列內(nèi)增添請求，然后再更新請求的DATI；

步驟3：確認每條請求的服務(wù)可行性，即判斷每條請求的剩余有效期，移除剩余有效期短于請求服務(wù)時間的數(shù)據(jù)請求；

步驟4：判斷RSU服務(wù)隊列是否為空，如果不為空就依據(jù)區(qū)域內(nèi)的DATI和緩沖區(qū)域信息構(gòu)建圖；

步驟5：通過調(diào)度算法從服務(wù)隊列中選擇DATI ；

步驟6：找到覆蓋的最大子圖再編碼成一個數(shù)據(jù)包 然后廣播編碼包；

步驟7：判斷車輛是否離開的覆蓋范圍。如果沒有，回到步驟2；否則就將車輛的緩存信息傳輸至車輛的下一個RSU（）。

3 性能分析

3.1 仿真平臺

本節(jié)分析在V2R通信中基于網(wǎng)絡(luò)編碼的數(shù)據(jù)傳輸性能，即分析網(wǎng)絡(luò)編碼對數(shù)據(jù)傳輸性能的影響。將NCDD算法應(yīng)用于文獻[5]的SIN方案中，記為SIN?NCDD，而沒有采用NCDD算法的記為SIN。

仿真場景如圖7所示，其中24個RSU，40～120輛車。每個RSU的通信距離為800 m，而車輛的通信范圍為300 m。每次獨立仿真重復(fù)10次，取平均值作為最終的仿真數(shù)據(jù)。

同時，選擇截止期錯失率DMR（Deadline Miss Ratio）、期望響應(yīng)時間ERT（Expected Response Time）、節(jié)省帶寬率SBR（Saved Bandwidth Ratio）以及平均編碼長度AEL（Average Encode Length）分析網(wǎng)絡(luò)編碼算法的性能。其中，DMR等于截止時期錯失的請求與總的請求數(shù)之比。提出NCDD算法的主要目的就是降低DMR。

3.2 仿真結(jié)果

3.2.1 截止期錯失率DMR

圖8為車輛數(shù)的變化對DMR性能的影響。從圖8可知，車輛數(shù)的增加，增加了截止期錯失率。原因在于車輛數(shù)的增加提高了網(wǎng)絡(luò)系統(tǒng)的負擔(dān)，進而提高了截止期錯失率。然而，將SIN?NCDD與SIN方案對比不難發(fā)現(xiàn)，SIN?NCDD具有更低的DMR，這說明通過網(wǎng)絡(luò)編碼能夠降低錯失率，進而提高數(shù)據(jù)傳輸性能。SIN?NCDD的平均DMR比SIN降低了近20%。

3.2.2 期望響應(yīng)時間ERT

期望響應(yīng)時間ERT隨車輛數(shù)的變化曲線如圖9所示。與截止期錯失率類似，期望響應(yīng)時間ERT隨車輛數(shù)的增加而上升。此外，不難發(fā)現(xiàn)，通過網(wǎng)絡(luò)編碼能夠有效地提高系統(tǒng)響應(yīng)速度，降低響應(yīng)時間。SIN?NCDD響應(yīng)時間比SIN降低約18%。

3.2.3 帶寬節(jié)省率SBR

圖10為帶寬節(jié)省率隨車輛數(shù)的變化情況。從圖10可知，車輛數(shù)的增加，提高了帶寬節(jié)省率。原因在于：車輛數(shù)的增加，加大了網(wǎng)絡(luò)負擔(dān)，增加了RSU服務(wù)隊列的請求數(shù)，相應(yīng)地也提高了滿足請求的概率。此外，從圖10可知，通過網(wǎng)絡(luò)編碼能夠有效地提高帶寬節(jié)省率。

3.2.4 平均編碼長度AEL

最后分析了平均編碼長度隨車輛數(shù)的變化情況。平均編碼長度越長，編碼性能越好，所傳輸?shù)木幋a數(shù)據(jù)包越少。從圖11可知，通過網(wǎng)絡(luò)編碼技術(shù)使得每廣播一個數(shù)據(jù)包，其包含更多的數(shù)據(jù)項DATI，反之，沒有采用網(wǎng)絡(luò)編碼技術(shù)，每次只廣播一個數(shù)據(jù)項，限制了帶寬利用率。

圖11 平均編碼長度

4 結(jié) 語

在傳統(tǒng)的基于多RSU的車載網(wǎng)絡(luò)中，一個RSU每廣播一個數(shù)據(jù)包只能傳輸一個數(shù)據(jù)項，這限制了廣播帶寬利用率，也約束了響應(yīng)時間。為此，本文提出新的編碼算法。在編碼過程中，無需車輛向RSU上傳緩存區(qū)域信息，提高了帶寬利用率，也降低了響應(yīng)時間。將NCDD算法應(yīng)用于SIN方案進行實驗。實驗數(shù)據(jù)表明，通過融入網(wǎng)絡(luò)編碼算法，截止期錯失率下降了20%，帶寬節(jié)省率提高了近30%。

參考文獻

[1] DING G， WANG J， WU Q， et al. Spectrum sensing in opportunity?heterogeneous cognitive sensor networks： how to cooperate [J]. IEEE sensors journal， 2013， 13（11）： 4247?4255.

[2] MALEKI S， PANDHARIPANDE A， LEUS G. Energy?efficient distributed spectrum sensing for cognitive sensor networks [J]. IEEE sensors journal， 2011， 11（3）： 565?573.

[3] SHARMA R K， WALLACE J W. Correlation?based sensing for cognitive radio networks： bounds and experimental assessment [J]. IEEE sensors journal， 2011， 11（3）： 657?666.

[4] BARBA C， MEZHER A M， IGARTUA M， et al. Available bandwidth?aware routing in urban vehicular Ad?Hoc networks [C]// Proceedings of 2012 IEEE Vehicular Technology Confe?rence. [S.l.]： IEEE， 2012： 1?5.

[5] XU J， TANG X， LEE W C. Time?critical on?demand data broadcast algorithms， analysis and performance evaluation [J]. IEEE transactions on parallel and distributed systems， 2016， 17（1）： 3?14.

[6] AHLSWEDE R， CAI N， LI S Y R， et al. Network information flow [J]. IEEE transactions on information theory， 2010， 46（4）： 1204?1216.

[7] BIRK Y， KOL T. Coding on demand by an informed source for efficient broadcast of different supplemental data to caching clients [J]. IEEE/ACM transactions on networking， 2015， 14（SI）： 2825?2830.

[8] CHEN J， LEE V C S， LIU K， et al. Efficient processing of requests with network coding in on?demand data broadcast environments [J]. Information sciences， 2013， 232（5）： 27?43.

[9] ALI G G M N， CHAN E， LI W Z. Supporting real?time multiple data items query in multi?RSU vehicular Ad Hoc networks [J]. Journal of systems and software， 2013， 86（8）： 2127?2142.

[10] LIU Z Y， ZHOU J G， ZHAO T， et al. An opportunistic approach to enhance the geographical source routing protocol for vehicular ad hoc networks [C]// Proceedings of 2009 IEEE 70th Vehicular Technology Conference. [S.l.]： IEEE， 2009： 1?5.

[11] ALI N， RAHMAN A， CHONG J， et al. On efficient data dissemination using network coding in multi?RSU vehicular Ad Hoc networks [J]. IEEE transactions on computer， 2016， 3（4）： 45?51.

[12] ZHAN C， LEE V C S， WANG J， et al. Coding?based data broadcast scheduling in on?demand broadcast [J]. IEEE tran?sactions on wireless communications， 2011， 10（11）： 3774?3783.

[13] KARP R. Reducibility among combination orial problems [J]. Complexity of computer computations， 2013（2）： 85?103.

[14] DHARWADKER A. The clique algorithm [EB/OL]. [2016?05?12]. http：//www.Dharwadker.org/clique/，2016.