基于網絡編碼的優化V2R數據傳輸性能的研究

吳芬芬+王嫣

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

關鍵詞： 車載網絡； 路側設備； 數據傳輸； 網絡編碼； 截止期錯失率

中圖分類號： 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 引 言

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

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

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

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

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

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

1 系統模型及約束條件

系統模型如圖2所示。每個RSU由請求信道ReqCH（Request CHannel）和響應信道ResCH（Respone CHannel）兩個信道組成。當一車輛駛入RSU覆蓋范圍內，若該車輛在其局部緩沖區內未找到其所需的數據項DAIT（Data Item），它就通過RSU的信道ReqCH發送請求DAIT。

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

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

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

2 NCDD算法

2.1 請求包的格式

假定網絡內輛車，即個RSU，即若車輛向遞交一個請求，且表示為。請求的格式如下所示：

（1）

式中：為的ID號；表示請求的數據DAIT號；表示產生的時間。

假定服從均勻分布：

（2）

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

（3）

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

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

2.2 網絡編碼

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

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

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

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

針對圖，定義一個子圖，致使該子圖內每兩個頂點均有邊連通。假定是內的任意一個子圖，即相應地，在內請求數據DAIT集表示為

（4）

相應地，假定內所包含的車輛集表示為。

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

將圖3所示5個車輛轉化成圖，如圖4所示。依據各個車輛所請求的DAIT關系，構建車輛的邊。其中，黑粗線構成了子圖。

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

2.3 最大化

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

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

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

2.4 緩存區域信息更新

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

當離開的覆蓋區域時，RSUi就利用主干連接，先聯系到覆蓋的下一RSU（RSUj），然后再向其傳輸車輛的緩存區域信息。注意到，RSUi能夠利用知道將駛入新的RSU（RSUj）。隨著時間的推移，車輛越來越靠近。

2.5 NCDD算法流程

NCDD算法流程如圖6所示。

NCDD算法流程的步驟如下：

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

步驟2：在RSU的服務隊列內增添請求，然后再更新請求的DATI；

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

步驟4：判斷RSU服務隊列是否為空，如果不為空就依據區域內的DATI和緩沖區域信息構建圖；

步驟5：通過調度算法從服務隊列中選擇DATI ；

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

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

3 性能分析

3.1 仿真平臺

本節分析在V2R通信中基于網絡編碼的數據傳輸性能，即分析網絡編碼對數據傳輸性能的影響。將NCDD算法應用于文獻[5]的SIN方案中，記為SIN?NCDD，而沒有采用NCDD算法的記為SIN。

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

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

3.2 仿真結果

3.2.1 截止期錯失率DMR

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

3.2.2 期望響應時間ERT

期望響應時間ERT隨車輛數的變化曲線如圖9所示。與截止期錯失率類似，期望響應時間ERT隨車輛數的增加而上升。此外，不難發現，通過網絡編碼能夠有效地提高系統響應速度，降低響應時間。SIN?NCDD響應時間比SIN降低約18%。

3.2.3 帶寬節省率SBR

圖10為帶寬節省率隨車輛數的變化情況。從圖10可知，車輛數的增加，提高了帶寬節省率。原因在于：車輛數的增加，加大了網絡負擔，增加了RSU服務隊列的請求數，相應地也提高了滿足請求的概率。此外，從圖10可知，通過網絡編碼能夠有效地提高帶寬節省率。

3.2.4 平均編碼長度AEL

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

圖11 平均編碼長度

4 結 語

在傳統的基于多RSU的車載網絡中，一個RSU每廣播一個數據包只能傳輸一個數據項，這限制了廣播帶寬利用率，也約束了響應時間。為此，本文提出新的編碼算法。在編碼過程中，無需車輛向RSU上傳緩存區域信息，提高了帶寬利用率，也降低了響應時間。將NCDD算法應用于SIN方案進行實驗。實驗數據表明，通過融入網絡編碼算法，截止期錯失率下降了20%，帶寬節省率提高了近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.