吳芬芬+王嫣

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

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

中圖分類號(hào)： TN919.3+1?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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ù)，車(chē)載網(wǎng)絡(luò)VANETs（Vehicular Ad Hoc Networks）受到廣泛關(guān)注。VANETs屬于移動(dòng)自組織網(wǎng)絡(luò)的特例，其能夠提供多類服務(wù)，包括安全、交通管理、舒適駕駛以及娛樂(lè)[1?3]。典型的VANETs結(jié)構(gòu)如圖1所示，車(chē)與車(chē)之間構(gòu)成車(chē)間通信V2V（Vehicle?to?Vehicle），車(chē)與路邊設(shè)施之間構(gòu)成V2R（Vehicle?to?RoadSide）通信。

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

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

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

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

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

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

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

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

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

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

2 NCDD算法

2.1 請(qǐng)求包的格式

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

（1）

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

假定服從均勻分布：

（2）

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

（3）

式中：表示RSU通信覆蓋的半徑；表示的移動(dòng)速度。

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

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

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

對(duì)于任意兩個(gè)頂點(diǎn)如果滿足以下兩個(gè)條件中的任何一個(gè)條件，就存在有向邊。

（1） 如果且，即兩輛不同的車(chē)請(qǐng)求相同的DAIT，則在和間存在邊；

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

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

（4）

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

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

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

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

2.3 最大化

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

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

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

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

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

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

2.5 NCDD算法流程

NCDD算法流程如圖6所示。

NCDD算法流程的步驟如下：

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

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

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

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

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

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

步驟7：判斷車(chē)輛是否離開(kāi)的覆蓋范圍。如果沒(méi)有，回到步驟2；否則就將車(chē)輛的緩存信息傳輸至車(chē)輛的下一個(gè)RSU（）。

3 性能分析

3.1 仿真平臺(tái)

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

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

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

3.2 仿真結(jié)果

3.2.1 截止期錯(cuò)失率DMR

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

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

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

3.2.3 帶寬節(jié)省率SBR

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

3.2.4 平均編碼長(zhǎng)度AEL

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

圖11 平均編碼長(zhǎng)度

4 結(jié) 語(yǔ)

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

參考文獻(xiàn)

[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.