車載自組織網(wǎng)絡中停放車輛合作的多媒體內(nèi)容分發(fā)

朱金奇，孫華志，劉念伯，馬春梅

(1.天津師范大學計算機與信息工程學院 天津 西青區(qū) 300387；2.電子科技大學計算機科學與工程學院 成都 611731)

車載自組織網(wǎng)絡的數(shù)據(jù)分發(fā)分為簡單、輕量級的文本消息和多媒體內(nèi)容分發(fā)(簡稱內(nèi)容分發(fā))兩類，后者主要針對可以圖像化、多媒體化的交通安全信息、娛樂信息和商業(yè)信息。近年隨著智能交通中對安全和舒適駕駛的需求逐漸提高，在VANETs中實現(xiàn)車輛之間的內(nèi)容分發(fā)是非常必要的。如移動車輛可以把所經(jīng)道路上發(fā)生的交通事故圖片分發(fā)給附近車輛，使其提前避開交通問題路段；又如駕駛者可以通過內(nèi)容分發(fā)在車輛行駛過程中下載相遇車輛中自己感興趣的音視頻信息，提高駕駛過程中的舒適度。然而由于車輛高速運動、網(wǎng)絡拓撲結(jié)構(gòu)變化快以及車輛的間歇連通性等問題，車輛間可用于數(shù)據(jù)傳遞的有效接觸時間非常短暫，車輛間較大內(nèi)容多媒體數(shù)據(jù)分發(fā)較其他自組織網(wǎng)絡困難得多，如何在車輛之間進行高效內(nèi)容分發(fā)成為研究挑戰(zhàn)。針對這一問題，文獻[1-2]采用P2P文件共享和網(wǎng)絡編碼技術提高內(nèi)容分發(fā)性能，但車輛間內(nèi)容分發(fā)效率仍然有限[3]。此外文獻[4-5]提出增加路邊基礎設施的策略來協(xié)助車輛完成內(nèi)容分發(fā)，然而存在如下問題：1)路邊基礎設施的傳輸范圍有限。2)性能受基礎設施節(jié)點影響大。當基礎設施節(jié)點數(shù)目較多時車輛與路邊節(jié)點的相遇概率較高，內(nèi)容傳輸?shù)男阅芫驮胶?。相反則內(nèi)容分發(fā)的性能越差。3)建設和維護基礎設施需要額外開銷，且多數(shù)路邊設施并不是免費的。4)固定基礎設施節(jié)點在災害發(fā)生時容易失效。

基于城市范圍內(nèi)長期存在大量路邊及非路邊停放車輛這一事實，本文提出城市車載自組織網(wǎng)絡中停放車輛合作的內(nèi)容分發(fā)策略(CPVC)，不需要安裝任何基礎設施節(jié)點，而是把地面停放車輛作為天然基礎設施和免費的數(shù)據(jù)中心來輔助VANETs中移動車輛完成內(nèi)容分發(fā)。由于城市區(qū)域中停放車輛數(shù)目眾多，分布廣泛且平均停放時間較長[6]，停放車輛相互合作延長了與移動車輛的接觸時間，從而使車輛間成功傳輸數(shù)據(jù)的概率大大增加。調(diào)查和仿真模擬驗證，相比于現(xiàn)有的內(nèi)容分發(fā)算法，CPVC具有較高內(nèi)容分發(fā)成功率，尤其是在低交通流量密度及多下載請求的條件下。

1 相關工作

目前車輛間的內(nèi)容分發(fā)研究可以分為以下3類：

1)基于車輛間的相遇：文獻[7]認為移動車輛間的無線連接隨機且不可靠，為此提出移動車輛間需要合作而進行數(shù)據(jù)傳輸。文獻[8]提出基于布隆濾波器的分級算法(HBFR)來實現(xiàn)主動數(shù)據(jù)分發(fā)。HBFR基于地理位置把城市分為不同區(qū)域，之后內(nèi)容分發(fā)按照區(qū)域序號進行。文獻[9]提出實時動態(tài)的內(nèi)容分發(fā)系統(tǒng)(RTAD)，每輛車輛根據(jù)所在道路的車輛密度和拓撲信息自動選擇最佳的內(nèi)容分發(fā)機制。

2)基于基礎設施節(jié)點：文獻[4]提出將多媒體數(shù)據(jù)存放到路邊緩存節(jié)點的內(nèi)容分發(fā)機制。文獻[10]介紹了運行于基礎設施接入點組成網(wǎng)絡之上的CCDSV系統(tǒng)用于移動車輛之間相互協(xié)作發(fā)布多媒體內(nèi)容。文獻[11]提出基于類型的內(nèi)容分發(fā)，內(nèi)容首先發(fā)布給距離對此內(nèi)容感興趣車輛較近的RSUs節(jié)點，這些RSUs節(jié)點再周期性地把該內(nèi)容廣播給路過車輛。

3)基于地面停放車輛：該類思想的典型代表為Parkcast算法[6]。

相比Parkcast，CPVC算法的優(yōu)越性為：

1)支持多用戶下載。

2)支持剩余內(nèi)容下載。CPVC通過建立車輛移動軌跡，結(jié)合移動預測選擇車輛將要經(jīng)過的停車簇繼續(xù)剩余內(nèi)容下載以提高內(nèi)容分發(fā)的傳輸成功率。

3)強調(diào)了停車簇間的合作，為內(nèi)容分發(fā)提供協(xié)同發(fā)布。

2 基于停車簇的內(nèi)容分發(fā)

2.1 停車簇管理

把一條城市道路路邊和非路邊的停放車輛組織成停車簇。一個典型的停車簇如圖1所示，其中H1和為該簇的兩個簇頭，M1～M10為成員節(jié)點。停車簇的建立過程如下：首先，位于道路最盡頭的兩個路邊節(jié)點被選舉為簇頭，這樣進入或離開該道路的移動車輛必會遇到其中的一個簇頭?？紤]到簇頭隨時都有可能離開，規(guī)定兩個備用簇頭如圖中和備用簇頭為同一停車簇中緊鄰簇頭的停放車輛，備用簇頭始終保持簇頭收集信息的副本。當簇頭要離開停車簇時，會觸發(fā)新簇頭的選舉以及舊簇頭把收集的簇信息轉(zhuǎn)發(fā)給新簇頭。簇成立后簇成員周期性報告自己的位置、ID號、需求內(nèi)容報告、擁有內(nèi)容的名字和剩余存儲空間到兩個簇頭，由簇頭維護整個簇。

圖1 停車簇結(jié)構(gòu)

2.2 內(nèi)容分發(fā)的方式

CPVC中基于停放車輛合作的多媒體內(nèi)容分發(fā)具有3種分發(fā)方式：

1)上傳：移動車輛駛過停車簇時，它與簇頭交互攜帶的資源名稱，若簇頭發(fā)現(xiàn)移動車輛中有簇成員的需求信息時，移動車輛可以將攜帶的文件連續(xù)地發(fā)布給停車簇中的停放車輛。

2)下載：當移動車輛駛過停車簇時，如果停車簇中有該移動車輛感興趣的資源，則停放車輛可以將存儲的相應資源連續(xù)發(fā)布給行駛的移動車輛。

3)停車簇間交換優(yōu)化存儲資源：停車簇能夠發(fā)送消息給鄰居停車簇請求需要的資源，以優(yōu)化自己的存儲。

3 內(nèi)容上傳

通常移動車輛s與停車簇i的接觸時長為：

式中，L為停車簇的長度；r為車輛的通信半徑；Hloc為接收內(nèi)容上傳請求簇頭的位置；Sloc和Vs分別是移動車輛s的當前位置和速度，可以從GPS獲得。在接觸時長內(nèi)移動車輛s可以上傳的總數(shù)據(jù)量滿足：

式中，R是MAC層的數(shù)據(jù)吞吐量。若移動車輛s上傳的內(nèi)容大小C滿足：

就能夠在移動車輛與停車簇接觸時間內(nèi)完成上傳，否則請求的內(nèi)容不能被完全上傳。對于上傳的總數(shù)據(jù)量As，應把As分成若干文件塊分發(fā)到多個停車簇成員車輛上，之后再經(jīng)停車簇內(nèi)部的數(shù)據(jù)傳輸把上傳的文件塊最終傳輸給需求車輛。

4 內(nèi)容下載

4.1 源車輛到源停車簇的下載

多媒體內(nèi)容以文件塊的形式存儲在停車簇成員中，當源車輛s與停車簇i相遇時，它首先發(fā)送包括部分的消息和停車簇的簇頭進行信息交互，其中ID為車輛s的ID號，Sloc和分別為車輛s的當前位置和運動速度。Cn表示需求內(nèi)容的名字，xs為車輛s與簇頭交互的時間戳，是該車輛駛?cè)敫魍＼嚧貢r間的歷史記錄。車輛s從源停車簇下載內(nèi)容信息的時長分兩種情況計算：若存放s請求下載內(nèi)容的停車簇成員(設它們組成的集合為S)能夠直接連通，即S中任意兩個地理位置最近節(jié)點間的距離小于等于2r，則源車輛能夠從停車簇i下載數(shù)據(jù)的時長為：

式中，L′是S中地理位置最遠的兩成員的距離。否則源車輛從停車簇i下載數(shù)據(jù)的時長為：

式中，n是S中滿足距離大于2r的相鄰兩成員節(jié)點的對數(shù)；Maloc和Mbloc表示距離大于2r的相鄰兩成員節(jié)點的地理位置，可以從簇頭獲得。

CPVC中簇內(nèi)停放車輛按照先來先服務原則為移動車輛提供內(nèi)容下載服務。當初始簇空閑時，源車輛的真正有效內(nèi)容傳輸時間等于它能夠從源停車簇下載數(shù)據(jù)的時長。隨著簇中下載請求的不斷到來，對于新到來的下載請求：1)若它所請求的所有文件塊所在的停放車輛與之前到達的請求沒有重疊，真正有效內(nèi)容分發(fā)時間也等于源車輛能夠從源停車簇下載數(shù)據(jù)的時長，由式(4)或式(5)獲得。2)若請求的文件塊所在的簇成員被先到的請求占有，真正有效的內(nèi)容傳輸時間等于車輛從源停車簇下載數(shù)據(jù)的時長減去等待之前下載請求完畢的等待時延。對于簇i的任一成員車輛Mk，假設車輛s下載請求Mk的次序為j，則它等待Mk提供服務的等待傳輸時延為：

式中，tj為無請求從Mk下載時車輛s的下載請求服務開始時間點；τj-1表示Mk有請求服務時前面所有請求結(jié)束服務的時間點。對于成員車輛Mk，tj和滿足：

式中，t1是Mk第1個到達請求服務的開始時間，可以根據(jù)式(7)獲得；Mkloc表示Mk的地理位置；設初始時τ0=0，jχ是第j個到達請求與停車簇i的簇頭交互時的時間戳；分別是第1次、第2次直到第j-1次請求Mk內(nèi)容的大小。把式(7)和式(8)代入式(6)即得分別求得源車輛等待S中每個停放車輛提供服務的等待傳輸延遲之后，真正有效的內(nèi)容分發(fā)時間為：

式中，K為請求S中成員的數(shù)量；要求獲得真正有效內(nèi)容分發(fā)時間后帶入式(2)即得從源停車簇下載的總數(shù)據(jù)量。計算真正有效內(nèi)容分發(fā)時間的算法如算法1所示。

算法1 有效內(nèi)容傳輸時間計算。

輸入：源車輛的ID、速度Vs、當前位置Sloc和與停車簇i的交互時間戳jχ，車輛傳輸半徑r，MAC層吞吐量R，集合S中所有成員的位置和ID號，本次的下載請求次序j，所有之前j-1次請求和停車簇i的交互時間戳

輸出：源停車簇為車輛s提供的有效內(nèi)容傳輸時間Tsreal。

1)根據(jù)S中成員車輛的位置關系，按照式(4)或式(5)計算源車輛從停車簇i下載數(shù)據(jù)的時長Ts；

4)else

6)根據(jù)式(7)計算前面無請求時本次請求的開始時間；

7)按照式(8)計算前面第j-1次請求結(jié)束傳輸?shù)臅r間點；

9)End for

12)returnTsreal。

4.2 剩余內(nèi)容的分發(fā)

當車輛s未能從源停車簇下載完請求的內(nèi)容時，如果輔停車簇中沒有未完成請求下載內(nèi)容的存儲，CPVD提出剩余下載內(nèi)容分發(fā)給經(jīng)過源停車簇的輔車輛，再由輔車輛利用移動車輛間的通信將這些內(nèi)容轉(zhuǎn)發(fā)到輔停車簇繼續(xù)下載。令C為請求下載內(nèi)容的大小，As為從源停車簇下載內(nèi)容的數(shù)據(jù)量，則剩余內(nèi)容表示為成功分發(fā)rs所需輔車輛的數(shù)量滿足：

設t時間內(nèi)到達源停車簇的停放車輛數(shù)目為N(t)，它服從參數(shù)為λ的泊松分布[12]。假設變量wi代表第i個輔車輛與源車輛到達源停車簇的時間間隔，根據(jù)泊松過程的性質(zhì)，WN的概率密度函數(shù)為：

輔車輛到達概率如圖2所示。第N個輔車輛能在時間(0,t]內(nèi)到達源停車簇的概率為：

圖2 輔車輛到達概率

4.3 輔停車簇的選擇

為選擇輔停車簇，本文利用車輛運動過程中遇到的停車簇歷史記錄描述車輛的移動軌跡。采用簡化的方法將時間表示以周為單位的時間和以天為單位的時間。車輛移動過程中每遇到一個停車簇，車載設備就記錄當前相遇時間和相遇停車簇的編號。為了減少數(shù)據(jù)量，便于存儲和處理，車載設備定期合并相同的行車路線，并用均值和方差表示相遇時間的波動。如某車輛一段時間的移動軌跡記錄如表1所示。設某車輛經(jīng)過停車簇2的時間為8：10，為預測輔停車簇，以停車簇2為源節(jié)點建立有向圖G(V,E)，如圖3所示，其中頂點V為將來可能要經(jīng)過的停車簇集合，E為路徑上任一停車簇到下一跳停車簇邊的集合，對于任意的權(quán)重wij表示通過停車簇i時下一時刻經(jīng)過停車簇j的概率。

表1 車輛歷史軌跡記錄

式中，Ntotal為歷史記錄中源車輛將要經(jīng)過的下一跳停車簇的總數(shù)量；是此剩余下載內(nèi)容傳輸前t時間段內(nèi)源停車簇及其鄰居停車簇需要向外傳輸?shù)氖Ｓ嘞螺d內(nèi)容總量，用于衡量這段時間內(nèi)停車簇間的網(wǎng)絡開銷；表示每個輔車輛最多能夠從停車簇攜帶的內(nèi)容大??；L′是源停車簇及其鄰居停車簇的平均長度；v是車輛經(jīng)過這幾個停車簇的平均速度，根據(jù)交通流量統(tǒng)計數(shù)據(jù)獲得。

圖3 以停車簇2為源停車簇的移動預測

4.4 停車簇間的協(xié)作

停車簇協(xié)作是內(nèi)容分發(fā)的主要部分，通過鄰居停車簇間的協(xié)作：1)可以實現(xiàn)鄰居簇的協(xié)同內(nèi)容發(fā)布；2)各停車簇能夠及時了解鄰居停車簇的存儲資源情況；3)鄰居停車簇間能彼此交換熱門存儲內(nèi)容，以優(yōu)化存儲。為此，每個停車簇首先發(fā)起一個鄰居發(fā)現(xiàn)過程。如停車簇i的簇頭把一個帶有簇頭地理位置、該簇ID號信息的Nei.REQ消息廣播給簇外2跳或3跳內(nèi)的停車簇。另一個停車簇收到此消息Nei.REQ后把停車簇i設為自己的鄰居簇。經(jīng)過一段時間的鄰居發(fā)現(xiàn)，每個停車簇均知道自己周圍一定范圍內(nèi)的鄰居停車簇情況。之后各停車簇周期性的向自己的鄰居簇廣播ID號和擁有資源的名字。

鄰居簇間實現(xiàn)協(xié)同內(nèi)容發(fā)布的前提是鄰居簇的資源一致性。為保證資源信息的一致性，首先簇內(nèi)需要周期性維護更新存儲資源，如定時刪除不被車輛請求或較少有車輛請求的過時熱門資源，通過定時維護更新，停車簇能夠優(yōu)化和管理自己的存儲。其次，簇間周期性的對外內(nèi)容廣播通過設置一個超時限來保證廣播內(nèi)容的新鮮性。令該超時限等于簇內(nèi)定時維護更新的周期加上鄰居簇間的最大傳輸延遲。鄰居簇間的移動車輛收到簇的內(nèi)容廣播消息時根據(jù)超時限判斷資源的可用性，若超時限減為零，則丟棄該廣播消息。

5 仿真實驗與性能分析

5.1 調(diào)查

對中國成都的城市區(qū)域進行了為期6周的調(diào)查，如圖4所示，該區(qū)域大小1 600 m×1 400 m，包含10個十字路口(圖中編號為0～9)和14個長度總和為7 860 m的雙行道，該區(qū)域擁有大量路邊及非路邊停車簇。對區(qū)域內(nèi)所有路段于每周二、周四、周六的停車情況進行了調(diào)查，對所有沿路5 m內(nèi)停放的車輛按16：00、18：00和22：00分時段進行統(tǒng)計的調(diào)查結(jié)果如表2所示。調(diào)查統(tǒng)計發(fā)現(xiàn)，在一天不同時段各路段的停車數(shù)量相對穩(wěn)定，不同時間段的行駛車輛密度在300 輛/h和2 200 輛/h之間變化，區(qū)域內(nèi)行駛車輛的數(shù)目在60～400之間。

圖4 仿真采用的街道拓撲

表2 停車調(diào)查結(jié)果

5.2 輔停車簇預測分析

為分析輔停車簇選擇的準確性，根據(jù)從家到學校的3條行駛路線進行實測。這3條行駛路線中路線①經(jīng)過3個不同停車簇，路線②經(jīng)過5個停車簇，路線③經(jīng)過7個停車簇。令車速位于40～80 km/h之間，車輛行駛時同時打開手機GPS記錄經(jīng)過道路各簇的GPS坐標和相應時間。

實測中3條路線總共行駛30次，其中路線①10次，路線②12次和路線③8次。把20次行駛作為樣本，另外10次行駛作為測試數(shù)據(jù)，得準確率隨源停車簇及鄰居停車簇向外傳輸?shù)氖Ｓ嘞螺d內(nèi)容總量變化如圖5所示?？梢钥闯鲚o停車簇預測準確率隨著網(wǎng)絡中剩余下載內(nèi)容總量的增大而減小，這是因為當剩余下載內(nèi)容總量較小時，選擇的輔停車簇數(shù)量較多，能夠保證剩余下載內(nèi)容傳輸?shù)捷o停車簇及剩余下載內(nèi)容不丟失。反之則選擇的輔停車簇數(shù)量少，剩余內(nèi)容易丟失。

圖5 輔停車簇預測準確率變化

5.3 仿真環(huán)境

用NS-2.33實現(xiàn)仿真，使用開源軟件VanetMobiSim-1.1[13]生成真實城市車輛移動軌跡。默認情況下在仿真地圖上設置車輛的數(shù)量為200輛，車輛傳輸范圍設為250 m，初始時車輛隨機選擇一個移動方向，且車輛的平均移動速度在40～80 km/h。底層的MAC協(xié)議采用2M的802.11。仿真開始對于分布在路邊停車位的停放車輛，它們嚴格按照表2中的密度隨機分布于各道路。每輛車的平均停放時間約為41.40 min，標準差為27.17，停車簇簇頭廣播消息周期為5 s。仿真過程中設置所有移動車輛中10%的車輛收到停車簇簇頭廣播消息后發(fā)送內(nèi)容下載請求。假設停車簇在仿真之前已建立，并以60 s為周期進行維護。設置Nthred的時間段t=20 min，下載內(nèi)容的大小為10 MB。把CPVC與Parkcast、CodeTorrentlike[14]及PC-based[15]進行分析對比。

5.4 交通流量密度對性能的影響

圖6a顯示隨著車輛密度增大CodeTorrent-like傳輸成功率顯著提高，這是因為CodeTorrent-like利用鄰居車輛的相遇完成內(nèi)容分發(fā)，而移動車輛密度增大可以使傳輸范圍內(nèi)遇到鄰居車輛的概率增大。當車輛密度較大時Parkcast的傳輸成功率反而降低，原因是Parkcast僅依靠源車輛與源停車簇的接觸完成內(nèi)容分發(fā)。隨著源停車簇收到內(nèi)容下載請求數(shù)量增大，當停車簇正為某下載請求服務時會拒絕其他車輛的下載請求，導致Parkcast傳輸成功率降低。車輛密度變化過程中，CPVC的傳輸成功率始終高于其他3個協(xié)議，尤其是當車輛密度稀疏時，CPVC仍能保持較高的傳輸成功率，主要因為CPVC依靠城市范圍內(nèi)廣泛且穩(wěn)定分布的地面停放車輛合作進行內(nèi)容分發(fā)。即使請求者數(shù)量較多，CPVC也不會拒絕下載請求。

圖6 交通流量密度對性能的影響

圖6b中車輛數(shù)量較多時會有更多的車輛協(xié)助內(nèi)容分發(fā)，導致CodeTorrent-like平均下載延遲下降。Parkcast只在源停車與源停車簇接觸時完成內(nèi)容分發(fā)，因此車輛密度變化對Parkcast的傳輸延遲影響不大。CPVC和PC-based的傳輸延遲在車輛密度增加時增大，這是由于請求內(nèi)容分發(fā)的車輛數(shù)量增多導致更多的下載請求只能在輔停車簇完成。圖6c中由于CPVC只有在輔停車簇中沒有存儲剩余下載內(nèi)容時才通過輔車輛往下遞交剩余下載，一定程度上比PC-based降低了網(wǎng)絡開銷。

5.5 請求下載的車輛比例對性能的影響

圖7 請求下載車輛比例的影響

圖7a中各協(xié)議的傳輸成功率隨請求下載內(nèi)容車輛比例的增大而降低。因為對于CodeTorrent-like，當請求下載的車輛數(shù)量增多時，在有限的車輛相遇時間內(nèi)未能完成下載的數(shù)量增多，這也同時加大了無線傳輸沖突的可能性。由于Parkcast在有限接觸時間內(nèi)無法完成請求下載的數(shù)量增多，因此Parkcast的傳輸成功率隨著請求下載車輛的增多而下降。CPVC和PC-based在請求下載車輛比例增多時把未能在源停車簇完成的請求轉(zhuǎn)移到輔停車簇，因此隨著請求下載車輛的增多傳輸成功率變化不大。圖7b中4種協(xié)議的平均傳輸延遲均隨著請求下載車輛比例增大而提升，由于CPVC選擇即將要通過的停車簇作為輔停車簇，且在輔停車簇中有剩余下載存儲時無需輔車輛傳輸，因此相比于PC-based降低了內(nèi)容分發(fā)的延遲。如圖7c所示，隨著請求下載車輛比例增加，CodeTorrent-like的傳輸開銷增長最大，因為需要頻繁的進行數(shù)據(jù)移交。由于CPVC需要進行源停車簇到輔停車簇的數(shù)據(jù)移交，所以傳輸開銷的增長較PC-based和Parkcast大。

6 結(jié)束語

針對城市范圍內(nèi)天然存在、廣泛分布且結(jié)構(gòu)穩(wěn)定的地面停車資源，本文提出停放車輛合作的內(nèi)容分發(fā)思想，利用鄰居停車簇間的協(xié)作發(fā)布和車輛與源停車簇及輔停車簇的接觸提供高效的本地數(shù)據(jù)分發(fā)。通過現(xiàn)實的停車調(diào)查和大量仿真實驗結(jié)果表明CPVC能夠以相對較低的傳輸延遲和網(wǎng)絡開銷獲得較高的傳輸成功率。