謝永，吳黎兵，何炎祥,3，范靜，劉冰藝

?

無間隙的車聯(lián)網(wǎng)協(xié)助下載方法

謝永1,2，吳黎兵1，何炎祥1,3，范靜1，劉冰藝1

(1. 武漢大學(xué)計算機學(xué)院，湖北武漢 430072；2. 景德鎮(zhèn)陶瓷學(xué)院信息工程學(xué)院，江西景德鎮(zhèn) 333403； 3. 武漢大學(xué)軟件工程國家重點實驗室，湖北武漢 430072)

車輛通過AP(access points)接入Internet具有低費用、高帶寬以及低時延等優(yōu)點，然而AP間的通信盲區(qū)(DA, dark area)使車輛只能間歇式接入Internet，造成網(wǎng)絡(luò)的QoS難以得到保障。為了解決這一問題，提出一種面向高速公路場景的無間隙協(xié)助下載方法(NICDM, non-intermittent cooperative downloading method)。在NICDM中，目標(biāo)車輛未完成的下載任務(wù)依據(jù)車速、任務(wù)大小以及DA距離等信息進行分解，并分別委托行駛方向上的最近2個AP協(xié)助下載；一組經(jīng)過優(yōu)化選擇的協(xié)助車輛從AP獲得數(shù)據(jù)，并在DA區(qū)轉(zhuǎn)交給相遇的目標(biāo)車輛；同時針對傳輸沖突提出了-副本的沖突解決策略，進一步提高協(xié)助下載的穩(wěn)定性。仿真結(jié)果表明，NICDM實現(xiàn)了目標(biāo)車輛在整個DA區(qū)無間隙地獲得數(shù)據(jù)，與相類似的方法相比，進一步提高了系統(tǒng)的QoS與吞吐量。

車聯(lián)網(wǎng)；協(xié)助下載方法；間歇式接入；沖突處理；車輛選擇策略

1 引言

車聯(lián)網(wǎng)已被看成下一代移動互聯(lián)網(wǎng)絡(luò)的重要組成部分[1]。車聯(lián)網(wǎng)中，V2I(vehicle-to-infrastructure)以及V2V(vehicle-to-vehicle)通信已在一些重要應(yīng)用中發(fā)揮作用，如交通擁塞避免與危險警告等[2]。人們對Internet的依賴越來越高，希望車輛(裝配WiMAX/LTE或WiFi接口)能夠如同在室內(nèi)一樣連接Internet，可隨時隨地通過Internet進行工作、學(xué)習(xí)或者娛樂。目前，車輛與Internet連接的方法主要有2類，通過3G/4G基站和通過路邊WiFi接入點(AP, access point)。與3G/4G接入相比，通過AP接入具有低費用、高帶寬以及低時延的特點，因而AP接入網(wǎng)絡(luò)更具有發(fā)展?jié)摿ΑＨ欢?，AP的通信范圍與部署數(shù)量是有限的，同時車輛的高速運動使車輛在AP通信覆蓋區(qū)的時間有限。車輛行駛在AP間的通信盲區(qū)(DA, dark area)時與網(wǎng)絡(luò)失去了聯(lián)系，造成了車輛只能間歇性接入網(wǎng)絡(luò)。因而，車聯(lián)網(wǎng)用戶只能在AP通信范圍內(nèi)使用一些輕量級的網(wǎng)絡(luò)服務(wù)，如瀏覽網(wǎng)頁、電子郵件等，對于資源密集型服務(wù)，如大文件下載、視頻服務(wù)等則受到很大限制。為了使車聯(lián)網(wǎng)用戶能夠隨時隨地使用資源密集型服務(wù)，研究者開始深入研究車聯(lián)網(wǎng)接入Internet的優(yōu)化策略，提出了一些解決方案，如在車聯(lián)網(wǎng)中建立P2P架構(gòu)[3]提供相似資源發(fā)現(xiàn)與共享機制來增加數(shù)據(jù)接收機會，通過多副本轉(zhuǎn)發(fā)的時延容忍路由協(xié)議[4]提高數(shù)據(jù)傳輸可靠性，以及建立車輛間的協(xié)助機制[5~9]等。

文獻[10]提出在雙向高速場景下的DSRelay協(xié)助下載模型。在該模型中，一個有文件下載需求的目標(biāo)車輛(target vehicle，后文簡稱為“目標(biāo)車輛”)進入AP通信范圍內(nèi)時，向AP請求數(shù)據(jù)下載。AP計算出目標(biāo)車輛通過時能下載的最大數(shù)據(jù)量，若大于需求量，則將數(shù)據(jù)直接下載到目標(biāo)車輛；否則，將未能完成的部分交給行駛方向上最近的AP下載。AP收到請求后，將數(shù)據(jù)下載到一組與目標(biāo)車輛對向行駛的協(xié)助車輛(assistant vehicle)上。當(dāng)協(xié)助車輛與目標(biāo)車輛相遇時將協(xié)助下載的數(shù)據(jù)交付給目標(biāo)車輛，實現(xiàn)了在DA區(qū)延伸用戶下載區(qū)域，從而提高下載的吞吐量。針對因?qū)嶋H相遇時間與預(yù)測相遇時間產(chǎn)生偏差造成的通信沖突，作者提出了補償模型[11]，進一步提高了下載的吞吐量。

然而，經(jīng)過深入研究DSRelay模型及補償模型，發(fā)現(xiàn)該模型的目標(biāo)車輛所得到的協(xié)助數(shù)據(jù)絕大部分是行駛在DA區(qū)的后半程才接收到的，而在DA前半程時卻很少能接收到數(shù)據(jù)；文獻[11]提出的補償模型未涉及到協(xié)助車輛從高速出口駛出造成協(xié)助下載數(shù)據(jù)丟失等意外情況。針對這些不足，本文提出了無間隙協(xié)助下載方法(NICDM，non-intermittent cooperative downloading method)。在NICDM方法中，AP協(xié)助請求策略是面向目標(biāo)車輛行駛方向上的最近2個AP。如圖1所示，當(dāng)目標(biāo)車輛(圖中標(biāo)識“T”的車輛)進入AP1時，向AP1請求數(shù)據(jù)下載，AP2與AP3參與協(xié)助下載。AP2將協(xié)助下載的數(shù)據(jù)交付給一組由優(yōu)選策略選出的對向行駛的協(xié)助車輛(圖中標(biāo)識“A”的車輛)，這些協(xié)助車輛將在DA1區(qū)的后半程(圖中LDA1區(qū))與目標(biāo)車輛相遇，并將協(xié)助下載數(shù)據(jù)交付目標(biāo)車輛。同理，AP3協(xié)助下載數(shù)據(jù)將由協(xié)助車輛在DA2區(qū)的前半程(圖中FDA2區(qū))交付給目標(biāo)車輛。而目標(biāo)車輛在DA1區(qū)的前半程(圖中DA1的FDA區(qū))也可以獲得數(shù)據(jù)，這些數(shù)據(jù)是目標(biāo)車輛行駛到AP1的前一個AP請求協(xié)助下載時由AP2協(xié)助下載的數(shù)據(jù)。目標(biāo)車輛在DA2區(qū)的后半程獲得數(shù)據(jù)，是目標(biāo)車輛行駛到AP2請求協(xié)助下載時由AP3協(xié)助下載的數(shù)據(jù)。這樣，NICDM方法可使目標(biāo)車輛在整個DA區(qū)中都能夠獲取數(shù)據(jù)，有效地解決間歇式接入AP帶來下載受限問題。NICDM同時設(shè)計了沖突解決策略，進一步提高系統(tǒng)穩(wěn)定性與吞吐量。

2 相關(guān)工作

目前車聯(lián)網(wǎng)的協(xié)助下載模型一般具有鮮明的場景特征。文獻[5]提出了高速場景下車聯(lián)網(wǎng)中協(xié)助下載(cooperative downloading)的概念，“協(xié)助下載”概念的提出為在車聯(lián)網(wǎng)中實現(xiàn)數(shù)據(jù)高速下載開辟了一個新的研究方向。該文獻的SPAWN協(xié)議是假定了高速公路的P2P應(yīng)用場景并且目標(biāo)車輛與協(xié)助車輛都在下載同一資源，然而2輛下載同一資源的車輛相遇的概率較小。文獻[6]針對車聯(lián)網(wǎng)提出一種MChord方案，提高P2P下載效率。文獻[7]提出一種高速公路的協(xié)助下載模型，主要分析同向車輛協(xié)助分組丟失的問題，通過對向車輛協(xié)助傳輸來提高系統(tǒng)總的吞吐量，但沒有涉及協(xié)助規(guī)劃方案，在穩(wěn)定性方面沒有保障。文獻[10]依據(jù)高速場景下車輛的運行軌跡具有可預(yù)測性的特征，提出了DSRelay模型。該模型利用對向行駛的車輛在AP區(qū)為目標(biāo)車輛協(xié)助下載來提高系統(tǒng)的吞吐量，后來作者在文獻[11]中提出了DSRelay的補償模型，進一步提高了系統(tǒng)的吞吐量。但目標(biāo)車輛行駛在DA區(qū)過程中，只在部分時間內(nèi)可以獲得協(xié)助下載數(shù)據(jù)，同時補償模型未涉及到協(xié)助車輛從高速出口駛出，造成協(xié)助下載數(shù)據(jù)丟失等意外情況。

在復(fù)雜的城市場景下，一些研究者提出新穎協(xié)助下載模型。文獻[12]提出針對城市場景的車輛協(xié)助下載模型，該模型通過分析經(jīng)過AP車輛的速度等相關(guān)信息來預(yù)測車輛的行駛路線以及與目標(biāo)車輛相遇的時刻，并確定協(xié)助車輛與其所協(xié)助下載的數(shù)據(jù)。文獻[1]通過對歷史數(shù)據(jù)進行分析獲得“相遇地圖”來決策車輛選擇與數(shù)據(jù)塊調(diào)度。也有研究者采用輔助設(shè)備等方式來研究協(xié)助下載，如文獻[8]提出了WWAN通知AP尋找協(xié)助下載車輛的方案，但條件是車輛都要安裝GPS以及WWAN功能，因而該方案的實施受到較大的限制。文獻[9]提出了一種間接擴展通信范圍的方法，該方法將路邊停靠的車輛與室內(nèi)AP保持連接，并作為其他車輛與AP通信的中繼器，間接擴展了AP的通信范圍。文獻[13]也提出了利用V2V通信方式延伸AP的通信范圍，目標(biāo)車輛能在更大范圍內(nèi)間接通過AP接入Internet。文獻[14]提出了Cabernet模型，該模型優(yōu)化移動客戶端到WiFi連接時間，并提出CTP的傳輸協(xié)議可大幅度提高傳輸效率。文獻[15]提出了一種將視頻內(nèi)容進行優(yōu)化分發(fā)到AP的策略，提高了用戶下載視頻的體驗。文獻[16]以最大流理論來研究車聯(lián)網(wǎng)中內(nèi)容下載性能的關(guān)鍵因素，指出AP部署密度是最大的影響因素，過多跳數(shù)(大于兩跳)的V2V數(shù)據(jù)轉(zhuǎn)發(fā)反而影響數(shù)據(jù)下載的性能。

3 無間隙協(xié)助下載方法

3.1 系統(tǒng)模型

本文提出的協(xié)助下載系統(tǒng)模型如圖1所示。系統(tǒng)場景與文獻[10]相似，設(shè)定在雙向的高速公路場景中，在距離相隔大致相等的地方設(shè)置AP服務(wù)區(qū)。為了符合高速公路實際情況，本文在DA區(qū)增加了高速公路出入口，如圖1中的“OUT_IN”，協(xié)助車輛中途從出口駛出高速公路會對協(xié)助下載產(chǎn)生一定影響。每一個AP都通過高速有線網(wǎng)絡(luò)接入Internet，并與中心服務(wù)器(center server)相連接，AP有固定的通信范圍(CR, communication rang)，在AP的通信范圍內(nèi)可與多輛車同時進行通信。每一輛車都配備有與AP通信以及與其他車輛通信的無線接口(WiFi)，并且有唯一的ID標(biāo)識。標(biāo)識“T”的車輛為目標(biāo)車輛，標(biāo)識“A”的車輛為協(xié)助車輛，與目標(biāo)車輛對向行駛，標(biāo)識“R”的車輛為其他車輛，與目標(biāo)車輛同向行駛。在本場景中，對向行駛的協(xié)助車輛與目標(biāo)車輛相遇概率非常高，除非中途從高速路的出入口離開高速，因而是目標(biāo)車輛最佳的協(xié)助下載車輛。

當(dāng)目標(biāo)車輛進入AP通信范圍內(nèi)時，向AP注冊并提出下載請求。AP收到下載請求后，將未能完成的下載任務(wù)由中心服務(wù)器委托其他AP協(xié)助下載。中心服務(wù)器依據(jù)任務(wù)分解策略將協(xié)助下載任務(wù)進行分解，分解后的子任務(wù)分別委托目標(biāo)車輛行駛方向上的最近2個AP協(xié)助下載。協(xié)助AP從其通信范圍內(nèi)選擇一組合適的協(xié)助車輛，并將數(shù)據(jù)傳輸給這些協(xié)助車輛，協(xié)助車輛將數(shù)據(jù)暫存在緩沖區(qū)中，當(dāng)與目標(biāo)車輛相遇時，再將攜帶數(shù)據(jù)交付給目標(biāo)車輛。中心服務(wù)器為每一個AP建立3類列表：1) 任務(wù)列表(TL, task list)，記錄當(dāng)前AP中已有的協(xié)助下載任務(wù)；2) 候選協(xié)助車輛列表(AL, assistant list)，記錄當(dāng)前AP已注冊的候選協(xié)助車輛；3) 已參與服務(wù)的車輛列表(SL, selected list)，記錄當(dāng)前已參與服務(wù)與獲得協(xié)助下載數(shù)據(jù)的車輛。這些列表是任務(wù)分配、協(xié)助車輛選擇算法以及沖突解決策略的重要依據(jù)。

實際應(yīng)用中，影響車聯(lián)網(wǎng)協(xié)助下載的因素很多，為了使研究更有針對性，本文對部分過程與因素進行相應(yīng)假設(shè)來簡化模型，相關(guān)假設(shè)如下。

1) AP在其通信范圍內(nèi)可以同時與多個車輛通信；車輛只有一個通信接口，在同一時刻只能與一個對象(車輛或AP)進行通信[17]。

2) 車輛都能自行計算出自身的平均速度，同時有較大的存儲空間，足夠存儲所有協(xié)助下載的數(shù)據(jù)分組。

3) 當(dāng)目標(biāo)車輛進入AP通信范圍內(nèi)時，向AP注冊自身ID、行駛方向、進入AP通信區(qū)的時間、平均速度以及所要下載的數(shù)據(jù)。

4) 一輛協(xié)助下載車輛進入AP通信范圍時，立即向AP注冊自身ID、方向、進入AP通信區(qū)的時間以及自身平均速度。

3.2 任務(wù)動態(tài)分解策略

定義1 下載周期。目標(biāo)車輛向AP請求數(shù)據(jù)下載的開始時刻記為起始時刻，目標(biāo)車輛進入下一個AP通信區(qū)的時刻記為結(jié)束時刻，此時刻同時也是離開下一個DA區(qū)的時刻，此2個時刻之間的時間段定義為一個下載周期。

每一個下載周期的開始時刻，目標(biāo)車輛向當(dāng)前AP進行注冊并提出新的下載請求。為了便于理解，本文若無特別說明，文中的分析都以AP1為當(dāng)前注冊的AP。同時目標(biāo)車輛在DA1區(qū)前半程所接收的數(shù)據(jù)是在前一個下載周期中委托AP2協(xié)助下載的數(shù)據(jù)。因而，同一下載周期內(nèi)的任務(wù)分解策略涉及到的下載數(shù)據(jù)分組包括車輛行駛在DA1區(qū)后半程、AP2通信區(qū)以及DA2區(qū)的前半程所下載到的數(shù)據(jù)。

從文獻[10]的DSRelay方案可看出，當(dāng)僅有一個相鄰的AP為目標(biāo)車輛協(xié)助下載數(shù)據(jù)時，由車輛運動規(guī)律可計算出協(xié)助車輛與目標(biāo)車輛相遇的位置大部分位于DA區(qū)的后半程。為了使目標(biāo)車輛在整個DA區(qū)都能夠接收到協(xié)助數(shù)據(jù)，本文將每一個DA區(qū)分為前半程與后半程，目標(biāo)車輛在這2個半程所接收的協(xié)助數(shù)據(jù)是同一個AP分2次連續(xù)的協(xié)助任務(wù)下載的數(shù)據(jù)。如圖1的 DA2區(qū)，目標(biāo)車輛在前半程(FDA2區(qū))接收的數(shù)據(jù)，是由目標(biāo)車輛在AP1注冊與下載請求過程中，AP3依據(jù)分配的協(xié)助下載任務(wù)下載的數(shù)據(jù)；目標(biāo)車輛在后半程(LDA2區(qū))接收的數(shù)據(jù)，是在下一個下載周期，即在AP2注冊時的下載周期，由AP3依據(jù)新分配的協(xié)助下載任務(wù)所下載的數(shù)據(jù)。

每一次新下載請求中，協(xié)助下載的子任務(wù)分為2部分：DA1區(qū)后半程協(xié)助下載任務(wù)與 DA2區(qū)的前半程協(xié)助下載任務(wù)。在這2部分之間，目標(biāo)車輛還可以從AP2直接下載數(shù)據(jù)。為了讓下載數(shù)據(jù)滿足服務(wù)需求的先后次序，提高用戶的下載體驗，本文依據(jù)車速、DA距離和AP的CR等信息，將下載任務(wù)按照數(shù)據(jù)的時序分解成4部分：1)DA1區(qū)后半程協(xié)助下載的子任務(wù)；2)AP2直接下載的子任務(wù)；3)DA2區(qū)前半程協(xié)助下載的子任務(wù)；4)剩余任務(wù)。然后將前2個子任務(wù)分配給AP2，第3個子任務(wù)分配給AP3，第4個剩余任務(wù)則由目標(biāo)車輛在下一次下載請求時，即行駛到AP2請求協(xié)助下載時，重新分配。

當(dāng)目標(biāo)車輛進入AP1通信區(qū)時，向AP1提交注冊信息，其中各參數(shù)依次表示目標(biāo)車輛ID、目標(biāo)車輛注冊時間、平均速度與行駛方向。目標(biāo)車輛通過DA1區(qū)下半程的起止時間是AP2進行協(xié)助車輛選擇的重要依據(jù)。設(shè)預(yù)計起始時刻為，結(jié)束時刻為，分別用以下2個公式計算

(2)

(4)

目標(biāo)車輛通過與對向行駛的協(xié)助車輛進行V2V通信來獲得協(xié)助下載數(shù)據(jù)。設(shè)V2V通信半徑為定值，對向通信的數(shù)據(jù)交付速率為，已選為目標(biāo)車輛的協(xié)助車輛的集合為，第輛協(xié)助車輛與目標(biāo)車輛通信時間的起止區(qū)間為，其中，表示協(xié)助車輛與目標(biāo)車輛通信開始時刻，為通信結(jié)束時刻，表示時長。則在區(qū)間內(nèi)的最大數(shù)據(jù)交付量滿足

s.t.

其中，式5(a)表示在已選協(xié)助車輛中，任意兩協(xié)助車輛與目標(biāo)車輛的通信時間不會相互沖突；式5(b)表示協(xié)助車輛與目標(biāo)車輛通信時間的總和不能大于目標(biāo)車輛行駛在盲區(qū)的時間；式5(c)表示兩車數(shù)據(jù)交付的時長小于或等于相遇的可通信時長，表示車輛速度范圍，表示目標(biāo)車輛的速度，表示協(xié)助車輛的速度，表示協(xié)助車輛與目標(biāo)車輛進行數(shù)據(jù)交付最短時間的閾值。

在式(5)中，為定值，因而有

Input:output:, , 1) 2) Compute, by式(6)3) If < then4), , 5) Assign Task() to AP26) Else If 7) AssignTask() to AP2, Task() to AP38) Else if 9) 10) Assign Task() to AP2, Task() to AP311) End if12) Return,,

中心服務(wù)器將分解的新任務(wù)分配到對應(yīng)AP的任務(wù)列表TL中，，其中，參數(shù)分別表示目標(biāo)車輛ID、AP的ID、注冊時間、平均速度、方向、預(yù)交付的起止時間段、數(shù)據(jù)塊編號以及最小未完成協(xié)助下載的數(shù)據(jù)塊序號。協(xié)助下載的數(shù)據(jù)時，從當(dāng)前序號最小數(shù)據(jù)塊開始，依據(jù)序號從小到大進行下載，并在任務(wù)列表中記錄當(dāng)前未完成協(xié)助下載的最小編號，初始狀態(tài)時，協(xié)作下載任務(wù)完成時。

3.3 協(xié)作車輛選擇策略

協(xié)助車輛進入AP通信范圍內(nèi)時，向AP提交注冊信息并發(fā)送至中心服務(wù)器。中心服務(wù)器為AP建立候選協(xié)助車輛列表(AL, assistant list),其中，表示協(xié)助車輛ID，表示協(xié)助車輛在當(dāng)前AP的注冊時間，是平均車速。候選協(xié)助車輛列表以注冊時間升序進行排列，當(dāng)有新的協(xié)助車輛進入AP通信范圍內(nèi)時，AP則將該信息報告中心服務(wù)器，中心服務(wù)器將該車輛按注冊時間插入在候選協(xié)助車輛列表中。

當(dāng)AL中的協(xié)作車輛被選為某一任務(wù)的協(xié)作車輛時，從AP下載到相應(yīng)數(shù)據(jù)，并記錄車輛信息，其中，與分別為預(yù)計的通信開始時間與結(jié)束時間，與分別為協(xié)助下載的起止序號。中心服務(wù)器將車輛信息加入到已選車輛列表(SL, selected list)中，其中，SL以的升序排列，并從AL中刪除該車輛。當(dāng)未得到協(xié)助下載任務(wù)的協(xié)助車輛離開AP通信區(qū)時，AP通知服務(wù)器從列表AL中刪除該車輛。

3.4 沖突解決策略

協(xié)作車輛從AP下載數(shù)據(jù)到把數(shù)據(jù)交付給目標(biāo)車輛過程中，受到眾多因素影響，可能造成數(shù)據(jù)無法按照預(yù)期成功交付給目標(biāo)車輛，如因非預(yù)期相遇造成通信沖突或者因協(xié)助車輛從中途離開高速造成下載數(shù)據(jù)丟失。傳統(tǒng)的解決方法是通過AP下載同一數(shù)據(jù)傳給多輛協(xié)助車輛來建立多個副本，增加該數(shù)據(jù)交付給目標(biāo)車輛的機會，減少通信沖突對數(shù)據(jù)交付的影響。然而，在AP下載多次下載同一數(shù)據(jù)來創(chuàng)建副本，一方面會占用本來有限的AP資源，另一方面造成系統(tǒng)吞吐量下降[10]。文獻[11]提出一種下載補償模型，該模型通過車輛間廣播的方式來告知即將發(fā)生或已發(fā)生的沖突，然后再從周邊車輛選擇其一作為副本的載體，以彌補此次沖突造成數(shù)據(jù)接收機會的損失。但該副本創(chuàng)建方法在很大程度上依賴沖突時刻的周邊場景，如正好周邊有無協(xié)助任務(wù)且無通信沖突的協(xié)助車輛。該方法也無法預(yù)測協(xié)助車輛中途從出站口離開高速事件，無法補救因此造成的協(xié)助數(shù)據(jù)丟失。

Input: AL,SLoutput: SL1) If AL is not empty then2) for each in AL do 3) for each in SL do4) If and then5) 6) 7) download data to 8) delete from AL and add to SL 9)end if10) end for 11) end for12) end if

為了解決因通信沖突或數(shù)據(jù)丟失等造成協(xié)助數(shù)據(jù)無法交付到目標(biāo)車輛的問題，本文提出了一種在DA區(qū)創(chuàng)建數(shù)據(jù)副本的“-副本”解決策略。表示同一協(xié)助數(shù)據(jù)所創(chuàng)建的副本的總個數(shù)，是一個動態(tài)值，可依據(jù)實際應(yīng)用場景動態(tài)設(shè)置，如依據(jù)系統(tǒng)中協(xié)助下載數(shù)據(jù)的交付成功率及其相關(guān)參數(shù)的歷史數(shù)據(jù)進行動態(tài)調(diào)整，也可以依據(jù)用戶需求級別進行設(shè)置。

定義2 擁有關(guān)系：,)表示已擁有的協(xié)助下載數(shù)據(jù)。

定義3 相遇關(guān)系：,)表示與之間的相遇機率。

定義4 沖突關(guān)系：(x,,)表示若同時為任務(wù)與攜帶數(shù)據(jù),則會產(chǎn)生數(shù)據(jù)交付時間沖突。

定義5 委托關(guān)系：(,,)表示委托備份的的協(xié)助數(shù)據(jù)，并在與相遇時完成交付。

為了更有效地提高副本的交付成功率與增強協(xié)助下載的穩(wěn)定性，副本載體，即協(xié)助車輛應(yīng)滿足如下規(guī)則。

規(guī)則1 若副本備選載體中已有目標(biāo)車輛的協(xié)助數(shù)據(jù)，則不再作為該目標(biāo)車輛的數(shù)據(jù)備份載體，即

規(guī)則2 若副本備選載體中已有協(xié)助數(shù)據(jù)的預(yù)測交付時間與目標(biāo)車輛的協(xié)助數(shù)據(jù)交付時間有交集，則不再作為該目標(biāo)車輛的數(shù)據(jù)備份載體，即

在高速公路場景中，對向行駛的車輛與目標(biāo)車輛相遇的機率很大，同向車輛與目標(biāo)車輛相遇的機率較小，因此，對向行駛車輛是副本的主要載體。同向行駛的車輛雖然不被選為直接交付給目標(biāo)車輛的副本載體，但可以作為副本創(chuàng)建時的過渡載體。副本載體選擇分為2類：1)數(shù)據(jù)的初始攜帶車輛(從AP接收數(shù)據(jù)的車輛)向通信范圍內(nèi)的與目標(biāo)車輛對向行駛的協(xié)助車輛請求創(chuàng)建數(shù)據(jù)副本，如圖4(a)所示，向其周邊通信范圍內(nèi)的協(xié)助車輛請求創(chuàng)建副本；2)初始攜帶車輛將數(shù)據(jù)傳遞給與目標(biāo)車輛同向行駛的車輛，由再尋找合適的協(xié)助車輛做副本載體，如圖4(b)所示的2個階段。階段1中向傳遞副本數(shù)據(jù)，階段2中向通信范圍內(nèi)對向行駛的請求創(chuàng)建副本。

4 實驗分析與性能評價

為了驗證本文協(xié)助下載方法NICDM的性能，本文采用OMNet++作為仿真平臺，仿真實驗場景的參數(shù)采用文獻[10,17]中的相關(guān)設(shè)置。場景設(shè)定為：高速公路每8 km左右設(shè)置一個AP，每一個AP的通信范圍為800 m，這一場景設(shè)置與當(dāng)前高速公路的服務(wù)區(qū)或加油站的設(shè)立情況相似。車輛的通信半徑設(shè)置為250 m，車輛在AP區(qū)下載的速率設(shè)為150 kbit/s，對向行駛車輛之間通信時的數(shù)據(jù)交付速率為50 kbit/s，同向車輛通信時的數(shù)據(jù)交付速率為200 kbit/s，V2V以及I2V建立連接時間采用1 s。車輛的速度由系統(tǒng)在90~130 km/h之中隨機產(chǎn)生，為了更符合實際高速情況，車輛從DA區(qū)出口離開高速公路的概率為3%，車輛速度變化率為，且變化過程符合正態(tài)分布。車流密度滿足泊松分布。

4.1 影響系統(tǒng)性能的因素分析

為了研究車流密度對系統(tǒng)的吞吐量影響的情況，設(shè)定了一組實驗：車輛初始速度為90 km/h，在=0.1的情況下，取車流密度=20、16、12、8分別進行實驗，并在相同的條件下也采用無協(xié)助下載方法(簡稱no-co)進行了對比實驗。實驗中記錄系統(tǒng)在一個下載周期內(nèi)目標(biāo)車輛所獲得的數(shù)據(jù)量，實驗結(jié)果如圖6所示。在前30多秒內(nèi)，目標(biāo)車輛還在AP通信范圍內(nèi)，從AP直接下載數(shù)據(jù)，5種方法所接收的數(shù)據(jù)量是相等的。到盲目區(qū)后無協(xié)助下載方法將不再收到數(shù)據(jù)，只能到下一個AP時才能下載到數(shù)據(jù)；=20時，目標(biāo)車輛能夠獲得一些協(xié)助下載的數(shù)據(jù)，但由于可選擇的協(xié)助車輛較少，所能協(xié)助下載的數(shù)據(jù)量較少，在一個下載周期內(nèi)總共可獲得的數(shù)據(jù)量為9 740 KB；=16時，協(xié)助AP可選的協(xié)助車輛增多，目標(biāo)車輛能夠獲得更多的協(xié)助下載的數(shù)據(jù)；當(dāng)=12時，協(xié)助AP可選擇的協(xié)助車輛增多可選擇更佳的協(xié)助車輛隊列，因而目標(biāo)車輛所得到的數(shù)據(jù)量明顯增多，總量達到15 050 KB；當(dāng)=8時，目標(biāo)車輛則能獲得更多的數(shù)據(jù)。從這一組實驗可以看出，當(dāng)協(xié)助車輛密度越大時，AP有更多可選擇的協(xié)助車輛來協(xié)助下載，因而目標(biāo)車輛獲得更多下載數(shù)據(jù)，進一步提高系統(tǒng)吞吐量。

4.1.2 不同車輛速度變化率對吞吐量影響

車輛平均速度是預(yù)測協(xié)助車輛與目標(biāo)車輛相遇時間的重要依據(jù)，是協(xié)助車輛隊列的選擇基礎(chǔ)。實際生活中，車輛的速度不變是幾乎不可能的，因而車輛相遇的位置與時間就可能與預(yù)測的有所不同，從而影響了協(xié)助數(shù)據(jù)的交付成功率。在協(xié)助下載模型設(shè)計時，必須考慮車速變化造成的影響。為了研究車輛速度的變化率對協(xié)助下載的影響，設(shè)計了一組實驗：車流密度=8，車輛初始速度為90 km/h，在車輛的變化率分別為0.1、0.2與0.4這3種情況下進行仿真實驗。實驗中記錄目標(biāo)車輛在一個下載周期所接收到的數(shù)據(jù)，最終的實驗結(jié)果如圖7所示。從圖7中可以看出，當(dāng)=0.4，由于車輛速度變化較大，協(xié)助車輛與目標(biāo)車輛實際相遇時間與預(yù)測的相遇時間相同的概率較低，因而造成通信沖突較多，目標(biāo)車輛所接收到的數(shù)據(jù)量受到較大影響，下載的總量僅有12 412 KB。當(dāng)車速變化率為0.2時，實際相遇時間與預(yù)測的相遇時間相同的概率提高了，通信沖突減少，目標(biāo)車輛接收到的數(shù)據(jù)有明顯提高，達到了15 597 KB。當(dāng)車速變化率為0.1時，目標(biāo)車輛接收到的協(xié)助下載數(shù)據(jù)進一步增多。

4.1.3-副本的值對吞吐量的影響

車輛在行駛過程中，受到眾多因素影響，因而協(xié)助下載數(shù)據(jù)不可能完全按照預(yù)期方式交付給目標(biāo)車輛。為數(shù)據(jù)創(chuàng)建副本可提高數(shù)據(jù)交付的機率，提高數(shù)據(jù)交付的可靠性。本文設(shè)計了“-副本”策略。為了驗證副本的值對下載量的影響，分別設(shè)置為0、1、2、4進行對比實驗，副本數(shù)量與目標(biāo)車輛的數(shù)據(jù)下載量的關(guān)系如圖8所示。

當(dāng)=0時，由于車輛速度變化等因素引起數(shù)據(jù)交付沖突或數(shù)據(jù)丟失，因而目標(biāo)車輛所接收數(shù)據(jù)量并不高，而當(dāng)=1時，接收的數(shù)據(jù)量有所提升，當(dāng)為2、4時進一步的提升。副本數(shù)量越大就可以更有效提高目標(biāo)車輛接收協(xié)助下載數(shù)據(jù)的機會，提高目標(biāo)車輛的下載量與系統(tǒng)吞吐量，但是，從另一方面也增加了通信開銷，同時也會增加車間的其他通信沖突，因此，值可依據(jù)應(yīng)用的實際場景進行動態(tài)設(shè)置。

4.1.4 不同AP密度對吞吐量的影響

AP的密度是影響協(xié)助下載的另一個重要因素，稀疏的AP造成的更大長度的DA區(qū)間，影響了系統(tǒng)的吞吐量。為了驗證AP密度對下載量的影響，將DA長度分別設(shè)置為8 km、12 km以及16 km。目標(biāo)車輛在DA區(qū)前后半程所得到的數(shù)據(jù)量與DA長度的關(guān)系如表1所示。

表1 目標(biāo)車輛在不同長度DA區(qū)的數(shù)據(jù)下載量

注：D表示數(shù)據(jù)下載量，單位為KB，P表示平均每公里下載量，單位為KB/km。

由表1可以看出，目標(biāo)車輛在同一長度的DA區(qū)時，在FDA區(qū)所獲得的數(shù)據(jù)量略少于LDA區(qū)，主要是由于協(xié)助車輛的運載協(xié)助數(shù)據(jù)時間要長于LDA區(qū)的時間，因而增加了數(shù)據(jù)交付的沖突機率；目標(biāo)車輛在不同長度的DA區(qū)時，平均每千米下載的數(shù)據(jù)量隨著DA長度的增大有較小幅度的減小，這說明DA的長度對系統(tǒng)的吞吐量的影響還是存在，即DA距離越小，單位距離協(xié)助下載的數(shù)據(jù)量越多。

4.2 性能對比

4.2.1 協(xié)助下載方法的對比分析

為了驗證NICDM優(yōu)缺點，本文采用類似的協(xié)助下載方法進行對比實驗。設(shè)置DA距離為8 km，采用了no-co方法、隨機選車算法(簡稱ra-co，該下載方法隨機選擇車輛來參與協(xié)助下載)、DSRelay模型以及NICDM進行對比實驗。實驗中記錄一個下載周期內(nèi)目標(biāo)車輛所接收到的下載數(shù)據(jù)，實驗結(jié)果如圖9和圖10所示。

在圖9可以看出目標(biāo)車輛進入AP時到離開AP通信范圍內(nèi)的30多秒的時間內(nèi)，目標(biāo)車輛所接收到的數(shù)據(jù)是由AP下載的數(shù)據(jù)直接交付給目標(biāo)車輛，4種方案的下載時長與下載速率相等，因而目標(biāo)車輛獲得了相等的數(shù)據(jù)量。在離開通信區(qū)，無協(xié)助下載方法中的目標(biāo)車輛在DA不能收到其他車輛協(xié)助下載數(shù)據(jù)，在整個DA區(qū)都接收到數(shù)據(jù)量為0 KB，最后整個下載周期內(nèi)所接收的數(shù)據(jù)就只有在AP區(qū)直接下載的數(shù)據(jù)。隨機選車算法中，當(dāng)目標(biāo)車輛進入AP時會向下一個AP請求協(xié)助下載，協(xié)助AP隨機選擇協(xié)助車輛，因而造成較多的協(xié)助車輛通信沖突，導(dǎo)致數(shù)據(jù)交付失敗率高，但在盲區(qū)還是能夠接收到一些協(xié)助下載數(shù)據(jù)，因而整個下載周期內(nèi)得到的數(shù)據(jù)相比無協(xié)助方法有所提升，達到了7 900 KB。在DSRelay模型中，協(xié)助AP的車輛選擇過程是依據(jù)策略進行地，并在DA區(qū)采用防碰撞補償算法，因而系統(tǒng)的吞吐量有較大幅度地提升，目標(biāo)車輛在整個下載周期內(nèi)所接收到的數(shù)據(jù)平均達到12 360 KB。在NICDM中，采用了DA區(qū)的分段協(xié)助下載策略，目標(biāo)車輛可以在整個DA接收協(xié)助車輛下載的數(shù)據(jù)，因而NICDM的一個周期內(nèi)的總吞吐量可達到17 810 KB，與DSRelay模型相比有顯著提高。

圖10表示4種下載方法在3個階段所接收的數(shù)據(jù)量情況。3個階段分別為：1) 在AP通信范圍內(nèi)直接下載數(shù)據(jù)；2) 在DA前半程所接收到的協(xié)助下載數(shù)據(jù)；3) 在DA后半程所接收到的數(shù)據(jù)。由圖10可看出，直接下載的數(shù)據(jù)量相等，說明4種下載方法在AP區(qū)所接收數(shù)據(jù)相等。由前面分析可知，no-co方法在整個DA區(qū)不會再接收數(shù)據(jù)，ra-co算法與DSRelay采用單一AP協(xié)助下載思路，下載到的大部分?jǐn)?shù)據(jù)是目標(biāo)車輛行駛到DA的后半程接收到的，前半程能夠接收到較少量的數(shù)據(jù)是由部分速度較高的協(xié)助車輛所交付的。在圖10中ra-co與DSRelay只有少量的前半程接收的數(shù)據(jù)驗證了這一分析正確性。本文的NICDM方法采用了DA區(qū)的分段協(xié)助下載策略，目標(biāo)車輛在DA的前半程與后半程所接收協(xié)助下載的數(shù)據(jù)大致相等，圖中的NICDM中的前半程接收的數(shù)據(jù)量與后半程接收的數(shù)據(jù)量大致相等，進一步驗證了NICDM有效地消除了DA的前后半程對協(xié)助下載的影響。

4.2.2 協(xié)助下載方法的用戶體驗分析

用戶在使用網(wǎng)絡(luò)服務(wù)過程中，處于通信暫盲或通信中斷的時間越長，用戶體驗則越不好。協(xié)助下載過程中，目標(biāo)車輛在DA區(qū)處于數(shù)據(jù)等待(WFD, waiting for data)狀態(tài)的時間長短是直接影響用戶體驗的重要指標(biāo)。本文設(shè)計一組實驗，DA長度分別為8 km、12 km與16 km，采用隨機選車算法(ra-co)、DSRelay模型以及NICDM方法。實驗中統(tǒng)計了目標(biāo)車輛在不同長度的DA區(qū)中的平均帶寬(AB, average bandwidth)以及處于WFD狀態(tài)的時長，用來分析在DA區(qū)下載時的用戶體驗。

圖11表示了采用3種協(xié)助下載方法過程中，目標(biāo)車輛在DA區(qū)獲得的平均帶寬。通過任務(wù)分解策略，NICDM實現(xiàn)了目標(biāo)車輛在DA區(qū)前后半程都可獲得大致相等的數(shù)據(jù)，因而DA區(qū)的平均帶寬最高，達到40 KB/s。在DSRelay方法中，雖然目標(biāo)車輛在DA后半程接收到的數(shù)據(jù)量與NICDM相近，但其前半程接收到的數(shù)據(jù)量很少，因而整個DA區(qū)的平均帶寬受到影響，只有NICDM的60%。隨機選擇算法接收到的數(shù)據(jù)量更少，在DA區(qū)的平均帶寬則更低。本實驗結(jié)果可以證實，通過NICDM方法，用戶能夠獲得更高的下載速度，提高下載時的用戶體驗。

表2表示的是目標(biāo)車輛在經(jīng)過DA區(qū)前半程與后半程時處于WFD狀態(tài)的時間統(tǒng)計結(jié)果。從表2結(jié)果可以看出：1) DA的后半程，DSRelay與NICDM的空閑時間總長基本相等，ra-co算法中目標(biāo)車輛的WFD狀態(tài)時間較多，是NICDM的16倍以上，DA區(qū)越長，ra-co算法中目標(biāo)車輛的WFD時間相比其他2種方法增長地更快；2) 在DA的前半程，ra-co算法與DSRelay中目標(biāo)所處于WFD狀態(tài)的時間很長，所占目標(biāo)車輛通過DA區(qū)時間的82%，結(jié)合圖10可分析出，這些WFD狀態(tài)基本上是屬于連續(xù)時間，這對于下載時的用戶體驗可是致命的。NICDM方法中產(chǎn)生WFD狀態(tài)的主要原因是車速變化引起通信沖突，但這些WFD狀態(tài)是離散不連續(xù)，且時間較短，僅占目標(biāo)車輛通過DA區(qū)時間的3%~6%，用戶在下載過程中基本上感覺不出來，獲得了較好的用戶體驗。

表2 目標(biāo)車輛在DA區(qū)的WFD狀態(tài)總時長（單位：s）

5 結(jié)束語

高速公路2個相鄰AP區(qū)有一段較長的通信盲區(qū)，造成了車輛較長時間的通信間歇期，在通信間歇期可通過車輛的協(xié)助下載，間接增加目標(biāo)車輛的下載時間，從而提高車輛的下載吞吐量。為了更充分利用通信間歇期，本文采用了將目標(biāo)車輛的下載任務(wù)委托其行駛方向上最近2個AP協(xié)助下載，實現(xiàn)目標(biāo)車輛在整個通信盲區(qū)可接收到協(xié)助車輛的下載數(shù)據(jù)。同時本文針對因通信沖突或車輛中途離開高速等影響數(shù)據(jù)無法正常交付的因素，設(shè)計了-副本策略來提高數(shù)據(jù)交付的成功率。通過仿真實驗，論證參數(shù)對系統(tǒng)性能的影響，同時也表明了NICDM實現(xiàn)的目標(biāo)車輛在整個DA區(qū)無間隙獲得協(xié)助下載數(shù)據(jù)，與相似下載方法相比顯著地提高了系統(tǒng)吞吐量。下一步研究工作的重點將針對不同場景下協(xié)作車輛的利用率進行定量分析。

[1] TRULLOLS-CRUCES O, FIORE M, BARCELO-ORDINAS J M. Cooperative download in vehicular environments[J]. IEEE Transactions on Mobile Computing, 2012, 11(4): 663-678.

[2] JOERER S, SEGATAM, BLOESSLB, et alA vehicular networking perspective on estimating vehicle collision probability at intersections[J]. IEEE Transactions on Vehicular Technology, 2014, 63(4): 1802-1812.

[3] LIN SH, HU J Y, CHOU C F, et al. A novel social cluster-based p2p framework for integrating VANETs with the Internet[C]//Wireless Communications and Networking Conference, WCNC 2009. Budapest, Hungary, c2009: 1-6.

[4] 姜海濤, 張宏, 李千目. 車載時延容忍網(wǎng)絡(luò)路由協(xié)議研究[J]. 通信學(xué)報, 2013, 34(3): 76-84.

JIANG H T, ZHANG H, LI Q M. Research on routing protocol of vehicular delay-tolerant networks[J]. Journal on Communications,2013, 34(3): 76-84.

[5] NANDAN A, DAS S, PAU G, et alCo-operative downloading in vehicular ad-hoc wireless networks[C]//Wireless On-demand Network Systems and Services, 2005.St. Moritz, Switzerland. c2005: 32-41.

[6] LIU C L, WANG C Y, WEI H Y. Mobile chord: enhancing P2P application performance over vehicular ad hoc network[C]//IEEE GLOBECOM 2008.New Orleans, USA, c2008: 1-8.

[7] TRULLOLS-CRUCES O, MORILLO-POZO J, BARELO J M, et alA cooperative vehicular network framework[C]//Communications, IEEE International Conference on 2009. Dresden, Germany, c2009: 1-6.

[8] CHEN B B, CHAN M C. MobTorrent: a framework for mobile Internet access from vehicles[C]//IEEE INFOCOM 2009. Rio de Janeiro, Brazil, c2009: 1404-1412.

[9] CREPALDI R, BEAVERS R, EHRAT B, et alLoadingzones: leveraging street parking to enable vehicular internet access[C]//The Seventh ACM International Workshop on Challenged Networks. Istanbul, Turkey, c2012: 23-30.

[10] 劉建航, 孫江明, 畢經(jīng)平, 等. 基于動態(tài)時槽的車聯(lián)網(wǎng)協(xié)助下載方法研究[J]. 計算機學(xué)報, 2011, 34(8): 1378-1386.

LIU J H, SUN J M, BE J P, et al.VANET cooperative downloading approach study based on dynamic slot[J].Chinese Journal of Computers, 2011, 34(8): 1378-1386.

[11] 劉建航, 畢經(jīng)平, 徐鵬, 等. 一種提高系統(tǒng)吞吐量的協(xié)助下載補償模型[J]. 計算機學(xué)報, 2012, 35(7): 1390-1398.

LIU J H, BE J P, XU P, et alA compensation model of cooperative downloading improving system throughput[J]. Chinese Journal of Computers, 2012, 35(7): 1390-1398.

[12] FIORE M, BARCELO-ORDINAS J M. Cooperative download in urban vehicular networks[C]//Mobile Adhoc and Sensor Systems, IEEE 6th International Conference. Macau, China, c2009: 20-29.

[13] ZHAO J, ARNOLD T, ZHANG Y, et alExtending drive-thru data access by vehicle-to-vehicle relay[C]//The Fifth ACM International Workshop on Vehicular Inter-Networking.San Francisco, USA, c2008: 66-75.

[14] ERIKSSON J, BALAKRISHNAN H, MADDEN S. Cabernet: vehicular content delivery using WiFi[C]//The 14th ACM International Conference on Mobile Computing and Networking.San Francisco, USA, c2008: 199-210.

[15] DANDAPAT S K, JAIN S, CHOUDHURY R R, et alDistributed content storage for just-in-time streaming[J]. ACM SIGCOMM Computer Communication Review, 2012, 42(4): 77-78.

[16] MALANDRINO F, CASETTI C, CHIASSERINI C, et al. Content downloading in vehicular networks: What really matters[C]//IEEE INFOCOM 2011. Shanghai, China, c2011: 426-430.

[17] OTT J, KUTSCHER D. Drive-thru Internet: IEEE 802.11 b for automobile users[C]//IEEE INFOCOM2004. HongKong, China, c2004: 262-373.

Non-intermittent cooperative downloading approach for VANET

XIE Yong1,2, WU Li-bing1, HE Yan-xiang1,3, FAN Jing1, LIU Bing-yi1

(1. School of Computer Science, Wuhan University, Wuhan 430072, China; 2. School of Information and Engineering, Jingdezhen Ceramic Institute, Jingdezhen 333403, China; 3. State Key Laboratory of Software Engineering, Wuhan University, Wuhan 430072, China)

Internet access through access points (AP) for vehicles has the advantages of low cost, high-bandwidth and low latency. However,because of dark area (DA) around AP, vehicles have to take intermittent linking to Internet, resulting in the QoS of network is difficult to be guaranteed. A non-intermittent cooperative downloading method (NICDM)for highway was proposed. The unfinished download task of target vehicular in current AP was decomposed into several parts according to vehicle’s speed, the size of unfinished task and distance of DA, then commissioned to two nearest APs. A group of cooperative vehicles selected under selection strategy would get data from the APs and forward it to the target vehicle when theymeet in DA. And an-replicaconflict resolution strategy was used to improve the stability of cooperative downloading. Simulation results show that compared with similar cooperative methods, NICDM can uninterruptedly get cooperative download data through DAs and improve system’s QoS and throughput.

vehicular network, cooperative downloading approach, intermittent access, conflict resolution, vehicle selection strategy

TP393

A

10.11959/j.issn.1000-436x.2016022

2014-10-14；

2015-05-08

吳黎兵，wu@whu.edu.cn

國家自然科學(xué)基金資助項目（No.61272112, No.61472287）；湖北省科技支撐計劃基金資助項目（No.2013BAA004）

The National Natural Science Foundation of China (No.61272112, No.61472287), Science and Technology Support Program of Hubei Province (No.2013BAA004)

謝永（1978-），男，湖南郴州人，武漢大學(xué)博士生，主要研究方向為車聯(lián)網(wǎng)、下一代網(wǎng)絡(luò)與網(wǎng)絡(luò)安全。

吳黎兵（1972-），男，湖北黃梅人，博士，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向為分布式計算、網(wǎng)絡(luò)管理、網(wǎng)絡(luò)性能與服務(wù)質(zhì)量、可信軟件。

何炎祥（1952-），男，湖北應(yīng)城人，博士，武漢大學(xué)教授、博士生導(dǎo)師，主要研究方向為分布并行處理（含移動計算與Web服務(wù)）、自然語言處理、可信軟件、軟件工程等。

范靜（1988-），男，湖北宜昌人，武漢大學(xué)博士生，主要研究方向為無線網(wǎng)絡(luò)與下一代網(wǎng)絡(luò)。

劉冰藝（1990-），男，湖北麻城人，武漢大學(xué)博士生，主要研究方向分布式計算與網(wǎng)絡(luò)管理。