龍 浩 張書奎 張 力

1(蘇州大學計算機科學與技術學院 江蘇 蘇州 215006)2(徐州工業(yè)職業(yè)技術學院信息與電氣工程學院 江蘇 徐州 221140)

0 引 言

隨著道路車輛的日益增多，車載機會網(wǎng)絡成為當前研究的熱點。但是它面臨著諸多挑戰(zhàn)，比如車輛節(jié)點高速變動、通信環(huán)境復雜多變、拓撲結構動態(tài)變化、傳輸節(jié)點密度不均等，這些都影響車載機會網(wǎng)絡的通信性能和數(shù)據(jù)傳輸[1]。

車載機會網(wǎng)絡的鏈路質量受到車輛頻繁移動和網(wǎng)絡拓撲結構改變的影響，鏈接質量不穩(wěn)定，如果數(shù)據(jù)包在傳輸過程中丟失，則無法重新組建原始數(shù)據(jù)。在這種情況下，只能重傳數(shù)據(jù)包，或者放棄整個文件。當數(shù)據(jù)包或文件傳輸所花費的時間大于鏈路持續(xù)時間，則無法成功傳輸文件，對當前鏈路資源造成浪費。因此，在節(jié)點傳輸文件時，應盡量避免傳輸在當前鏈接狀態(tài)下無法完成傳輸?shù)奈募Y源，盡量在鏈路持續(xù)時間內完成文件的傳輸[2]。

目前流行的機會網(wǎng)絡路由算法Epidemic算法及其變異算法利用節(jié)點與節(jié)點間的相遇實現(xiàn)多副本的復制，從而提高了數(shù)據(jù)傳輸?shù)某晒β?，但是?shù)據(jù)的多次復制勢必增加了節(jié)點緩存空間和帶寬的占用，增大了網(wǎng)絡資源的消耗[3]。另一個常用的算法是Spray and Wait算法，該算法嚴格控制消息副本的噴射次數(shù)，在提高數(shù)據(jù)傳輸成功率的同時降低了網(wǎng)絡開銷。但是消息在等待傳輸階段與目標節(jié)點的通信機會也會錯失，導致網(wǎng)絡資源的利用率降低[4]。因此這兩種路由算法都達不到最高的傳輸效率。

1 相關工作

在現(xiàn)實情況中，當前節(jié)點傳輸隊列中多個不同大小文件一般采用先進先出的策略[5]。該策略看似比較公平，但在機會網(wǎng)絡環(huán)境中，該策略無法根據(jù)當前的鏈路狀態(tài)靈活調度文件，從而造成較多鏈路資源浪費。另外一種基于擁塞的機會調度算法OCCS[6]，車輛發(fā)送文件時指向目標接收車輛，發(fā)送車輛根據(jù)文件的擁塞程度按某種特定概率采用多拷貝方式發(fā)送文件，但是這種傳輸方法增加了網(wǎng)絡資源的消耗。因此，發(fā)送原則限制了網(wǎng)絡性能的進一步提升。

在目前的數(shù)據(jù)傳輸算法中，諸多路由算法通過歷史信息來計算節(jié)點間的傳輸概率。當節(jié)點相遇時，消息被發(fā)送給傳輸概率高于其自身的節(jié)點或匯聚點。文獻[7]提出了基于歷史記錄的數(shù)據(jù)轉發(fā)算法，通過計算節(jié)點到基站的概率值，當節(jié)點和匯聚點相遇時，概率值增加，否則隨時間減小。當節(jié)點相遇時，根據(jù)從低到高的概率值在節(jié)點之間傳輸文件。然而由于節(jié)點與基站之間的相遇次數(shù)較少，因此大多數(shù)節(jié)點到基站的概率值較小，傳輸可靠性較低。PROPHET算法[8]根據(jù)歷史相遇信息計算節(jié)點間的傳輸概率。當節(jié)點相遇時，兩者之間的傳輸概率增加，否則概率值隨時間減小。然而由于持續(xù)時間非常短暫而引起的無效相遇，導致計算的相遇概率值偏離實際的概率值。HiBop算法[9，13]存儲的節(jié)點附加屬性信息(例如工作地點、住宅地址等)，并結合節(jié)點相遇歷史計算節(jié)點間的傳輸概率。然而該算法需要增加空間存儲附加信息，且相應的計算會增加網(wǎng)絡資源的消耗。文獻[10，14]根據(jù)歷史相遇的持續(xù)時間確定直接傳輸概率，然后通過直接傳輸概率確定多跳傳輸概率。節(jié)點之間的傳輸概率被定義為多跳傳輸概率的加權和。然而，機會網(wǎng)絡環(huán)境中多跳(n>2)傳輸幾乎沒有實際意義并且易于誤差累積。

本文設計了一種車載機會網(wǎng)絡文件調度與數(shù)據(jù)傳輸算法解決了車載機會網(wǎng)絡中網(wǎng)絡拓撲結果隨時發(fā)生改變、鏈路持續(xù)時間短等問題。我們根據(jù)車輛的當前狀態(tài)和歷史記錄估測出鏈路的持續(xù)時間，并計算出文件調度序列，從而完成節(jié)點間的數(shù)據(jù)傳輸。具體創(chuàng)新有4個方面：

(1) 基于鏈路狀態(tài)估計，鏈路持續(xù)時間受車速和行駛方向等因素的影響。根據(jù)這些因素可以計算出鏈路的持續(xù)時間。

(2) 計算出鏈路持續(xù)時間后，盡量調度那些在當前鏈路持續(xù)時間能夠完成傳輸?shù)奈募?。根?jù)文件的傳輸時耗和鏈路持續(xù)時間計算節(jié)點在發(fā)送隊列中文件的傳輸順序，改變先進先出傳輸機制。

(3) 通過節(jié)點間單跳交互式協(xié)作，每個節(jié)點可以根據(jù)節(jié)點間的共享信息完成算法的計算，避免了集中式的全網(wǎng)信息調度。

(4) 通過算法分析車輛的運行軌跡，計算車輛之間的相遇概率，得出車輛節(jié)點相遇的數(shù)據(jù)傳輸策略，避免消息副本過度復制的同時也提高了消息轉發(fā)的機會。

2 文件調度算法設計

由于車載機會網(wǎng)絡的局限性，無法實現(xiàn)節(jié)點之間全局信息共享，因此每個節(jié)點只能控制各自傳輸隊列中發(fā)送文件的順序，算法的輸入是當前節(jié)點待傳輸?shù)奈募斜?，同時預先計算當前t時刻文件的傳輸耗時集合T，算法的輸出是優(yōu)化后的文件傳輸調度序列。因此，算法需要解決的問題是使每個節(jié)點對自己的隊列文件的傳輸順序進行排序，并對其進行調度，以最小的網(wǎng)絡負載獲得最大的文件傳輸成功率。算法詳細過程描述如下：

第一步每個節(jié)點維護自己的文件序列F，并且各自初始化一個列表S，將要發(fā)送的文件順序放入S中，然后所有節(jié)點依次驗證自己隊列中的每個文件，計算每個文件的傳輸耗時，即文件的大小和傳輸速率的比值。

第二步每個節(jié)點列表S中的文件采用貪婪思想進行排序。根據(jù)傳輸耗時遞增的原則對列表S中的文件進行重排序，然后根據(jù)計算的鏈路持續(xù)時間遍歷序列，查找與該時間最相近的文件發(fā)送。

第三步根據(jù)鏈路持續(xù)時間發(fā)送文件。如果文件發(fā)送截至時間最接近鏈路持續(xù)時間，將列表S中的文件發(fā)送到序列Y中。如果文件發(fā)送截至時間大于鏈路持續(xù)時間，則延遲該文件的發(fā)送，等待下一個鏈路的建立。在這種傳輸機制下，每個節(jié)點將優(yōu)先傳輸文件傳輸時耗與鏈路持續(xù)時間最接近的文件，那么將會有更多的文件傳遞成功。

算法偽代碼如下：

1: function input(Fi, T, t)

//根據(jù)文件的傳輸耗時準備好發(fā)送文件序列

2: for file Fi(i from 1 to n) do

//n為文件序列F的長度

3: t=t+TFi, S= S U {Fi}

4: if t>EFithen

5: t=t-TFi, S=S-{Fi}

6: end if

7: end for

8: return S

9: S=input(Fi,T,t)

10: for file Fi(i from 1 to |S|) do

11: ifTFi

//根據(jù)鏈路持續(xù)時間對應發(fā)送文件

12： Y=Y U {Si}, i++

13： else

14: wait next C

15： end if

16： end for

算法的核心問題是如何計算鏈路持續(xù)時間集合C。在DSRC標準中規(guī)定，車輛節(jié)點要向自己的鄰居節(jié)點周期性地廣播自身狀態(tài)信息，而自身狀態(tài)信息包括：當前車輛位置、方向、行駛速度和加速度等。同時假設每個節(jié)點在發(fā)布狀態(tài)信息時，一并發(fā)布自己在未來一段時間內的行駛路線，也就是說以上信息可以在鄰居節(jié)點間實現(xiàn)共享[15]。因此每個節(jié)點能夠估算出自身同鄰居節(jié)點間的鏈路持續(xù)時間。具體方法如下：

以圖1中節(jié)點運動情況為例，估測鏈路持續(xù)時間。由于未來的車輛行駛信息在節(jié)點間共享，在一定的時間周期內兩車速度基本保持穩(wěn)定，設其間距為d，并建立通信鏈路，車輛行駛可能有如圖1所示的四種情況：兩車一直在同一方向行駛之后鏈路斷開，如圖1(a)和圖1(b)；拐入相反方向后鏈路斷開如圖1(c)，拐入垂直方向后鏈路斷開如圖1(d)。設在圖1(c)和圖1(d)中建立鏈路時，B車距離拐彎路口距離為s1，B車距離拐彎路口距離為s2。節(jié)點通信半徑為r, A車在前，速度為v1, B車在后速度為v2。

圖1 車輛相遇運行示意圖

當v1>v2時，三種情況的鏈路持續(xù)時間C的計算公式為:

(1)

當v1

(2)

當v1=v2時,三種情況的鏈路持續(xù)時間C的計算公式為:

(3)

3 基于節(jié)點相遇概率的數(shù)據(jù)傳輸策略

文件調度到發(fā)送序列Y后，接下來我們主要研究如何與目標節(jié)點實現(xiàn)數(shù)據(jù)傳輸。在車載機會網(wǎng)絡中傳輸性能與車輛和中間節(jié)點之間的通信距離r有著直接的關系。文獻[8-9]通過仿真分析的方式在車載機會網(wǎng)絡中研究通信距離r對數(shù)據(jù)傳輸性能的影響但并沒有具體給出車輛和節(jié)點間通信距離的具體計算模型和公式[10]。本文通過大量的實測數(shù)據(jù)的驗證，得出一個車輛間建立鏈路通信的通信距離計算公式，建立一個基于速度差和時間間隔的相遇概率數(shù)據(jù)傳輸?shù)睦碚摲治瞿Ｐ?，為車輛和中間節(jié)點之間選擇合適的通信距離完成數(shù)據(jù)傳輸提供有效的理論分析工具。圖2描述的是車載機會網(wǎng)絡中車輛和中間節(jié)點間的通信。

圖2 車輛和中間節(jié)點的通信

圖2中，由于在道路上行駛車輛運行速度差和車輛相距時間間隔是隨機的，且其值并不能確定，因此車輛運行速度差和車輛相距時間間隔滿足連續(xù)性隨機變量概率分布。一段時間內車輛的行駛速度差為Δv，Δv的概率分布函數(shù)為FΔv(x)，概率密度函數(shù)為fV(t)。任意兩輛相鄰車輛進入某區(qū)域的時間間隔為Δt，Δt概率分布函數(shù)為FΔt(x)，概率密度函數(shù)為ft(t)。本文將得到一個通用的理論模型，對于不同實際道路情況，可以將車輛對應的Δv和Δt代入通用模型計算得到相應的概率分布函數(shù)值。

圖1描述了兩輛車A和B在道路中的行駛情況，設A車的速度為VA，B車的速度為VB，主要考慮VB和VA速度接近的情況，因為在這種情況下兩車才能保持通信鏈路。由于節(jié)點在相遇時共享車輛行駛狀態(tài)信息，且兩車速度在一定時間內保持穩(wěn)定，因此兩車能夠建立通信鏈路。

車輛進入某區(qū)域，從開始建立鏈路形成通信到鏈路斷開，車輛在該區(qū)域道路行駛的交通狀況都比較接近。因此在一段時間內，可以計算出車輛Δv和Δt對應的分布概率。tA和tB分別表示車輛A和車輛B進入該區(qū)域的時間，則Δt可以表示為：

Δt=tA-tB

(4)

由于道路上行駛車輛是相互獨立的，且進入某區(qū)域的時間也是獨立隨機的，因此Δt的概率分布函數(shù)FΔt(t)可以表示為：

(5)

根據(jù)實測相鄰車輛在道路行駛的時間間隔Δt為介于0～50 s之間的隨機變量，其ft(t)函數(shù)為：

ft(t)=n×mt0

(6)

式中：n=0.28,m=0.83是仿真常量。

由于車輛速度是相互獨立的，那么1/VA和1/VB也相互獨立，令Δv=1/VA-1/VB，則其概率分布函數(shù)FΔv(x)為：

(7)

通過實測車輛通行的數(shù)據(jù)分析得到行駛速度差Δv介于0～60 km/h之間，其fV(v)函數(shù)為：

(8)

式中：常系數(shù)k=4.35，根據(jù)實測數(shù)據(jù)統(tǒng)計分析得到；μ=10.8為實測數(shù)據(jù)的統(tǒng)計均值；σ=5.19為統(tǒng)計方差。

由于車輛A和車輛B的速度分別為VA和VB，兩車的間距為r，那么車輛B在該道路與車輛A進入通信鏈路需要滿足的條件為：

(9)

轉換后車輛間進行通信的距離r為：

(10)

基于節(jié)點相遇概率的數(shù)據(jù)傳輸策略判定兩節(jié)點相遇的條件是：通過式(6)和式(8)分別計算車輛與目標車輛的基于時間間隔和速度差的相遇概率范圍，并根據(jù)式(10)計算節(jié)點間通信距離r，首先根據(jù)時間間隔和速度差的概率分布判斷車輛與節(jié)點間是否能達到通信距離r，并且計算鏈路的持續(xù)時間從而完成數(shù)據(jù)的傳輸。

4 仿真及性能分析

文件調度算法(TTLD)和數(shù)據(jù)傳輸策略(EPDT)相關性能采用ONE(Opportunistic Network Environment)仿真平臺進行驗證[11]，為了驗證TTLD算法文件調度的效率，將TTLD算法與RSATA[12]與OCCS兩種算法進行對比實驗，并把三種算法應用于典型的機會網(wǎng)絡路由協(xié)議Spray and Wait中。將EPDT分別應用于典型的機會網(wǎng)絡Epidemic和Spray and Wait路由協(xié)議，并與這兩種路由協(xié)議的傳統(tǒng)方法進行對比實驗。模擬車載網(wǎng)絡中的車輛運動過程采用德國科隆市車輛軌跡數(shù)據(jù)集，隨機選取了數(shù)據(jù)集中800 m×800 m方形區(qū)域內的車輛軌跡數(shù)據(jù)，時間段為5分鐘，共包含 235 個節(jié)點的運動軌跡。為了不失一般性，文件的大小服從帕累托分布，文獻[11]通過對網(wǎng)絡流的統(tǒng)計分析可知，網(wǎng)絡中文件的大小服從雙帕累托對數(shù)正態(tài)分布，帕累托參數(shù)從1.2 增加到2.1。較低的帕累托參數(shù)表示文件分布廣泛，差異性較大；反之則文件集中在平均值附近，差異性較小。文件的傳輸速率根據(jù)源節(jié)點和目的節(jié)點的距離以及環(huán)境的信噪比來確定[11]。通信半徑在80～200 m之間，以20 m遞增的方式變換。仿真參數(shù)設置如表1所示。

表1 仿真參數(shù)設置

車輛可傳輸?shù)奈募?shù)量由車輛的緩存容量來決定，車載機會網(wǎng)絡中的車輛緩存容量雖然日益增大，但是目前還很有限，目前車載機會網(wǎng)絡文件傳輸策略的研究重點是如何利用有限的車輛緩存容量更有效地完成對文件的傳輸。因此本文主要分析車輛緩存容量的變化對TTLD文件調度算法的影響。

車輛緩存容量對TTLD、RSATA與OCCS三種算法消息成功投遞率的影響如圖3所示，消息投遞成功率=成功傳輸?shù)奈募€數(shù)/文件總數(shù)。3種算法的文件傳輸成功率隨著車輛緩存容量的逐漸增加而快速上升。緩存容量較為有限時，TTLD的文件發(fā)送成功率優(yōu)于RSATA和OCCS，緩存容量為10 MB時TTLD算法的文件傳輸成功率提高15.8%以上，隨著緩存容量的變大，TTLD算法的性能增益有所降低，三者的增速逐漸平穩(wěn)。

圖3 不同緩存容量的文件傳輸成功率

圖4描述了不同緩存容量對文件傳輸平均時延的影響，可以看出，RSATA算法文件發(fā)送的平均時延隨著車輛緩存容量的增加而迅速增大，而TTLD算法的時延增速較慢，其中，當緩存空間為10 MB時，TTLD算法的時延趨于穩(wěn)定，TTLD較RSATA、OCCS的平均時延減少了14.8%。隨著緩存容量的逐漸增大，文件傳輸數(shù)量和大小增加，OCCS的時延性能逐漸接近RSATA。最終TTLD與其他兩個算法相比，平均時延性能提高15.5%。

圖4 不同緩存容量的網(wǎng)絡平均時延

圖5描述了不同緩存容量對網(wǎng)絡負載率的影響。網(wǎng)絡負載率=(發(fā)送的文件數(shù)-成功發(fā)送的文件數(shù))/成功發(fā)送的文件數(shù)。可以看出，網(wǎng)絡負載率在緩存容量小于10 MB時，3種算法網(wǎng)絡負載率都有較快下降，但是本文算法要遠優(yōu)于其他兩種算法。當緩存容量逐漸增加10 MB以上時，車輛節(jié)點可以攜帶和發(fā)送的文件更多，可以排隊等待的文件更多，網(wǎng)絡負載率降低，但是當緩存容量持續(xù)增加的時候，3種算法的網(wǎng)絡負載率都趨于平穩(wěn)。TTLD算法中文件調度前有兩個條件的判定，減少了無效的文件傳遞，相比其他兩種算法網(wǎng)絡負載率有明顯降低，大約降低了13.8%。

圖5 不同緩存容量的網(wǎng)絡負載率

以表1參數(shù)設置為基礎，采用150節(jié)點，2小時數(shù)據(jù)包生存期，通過與Epidemic和Spray and Wait算法的傳統(tǒng)方法來進行算法性能評價，兩種算法都是目前機會網(wǎng)絡研究的熱點，能夠應用于各種不同的環(huán)境，在性能方面有明顯的特點，具有較高的可比性。將EPDT算法應用于目前機會網(wǎng)絡最流行的兩種路由算法，更能在性能上比較其優(yōu)越性。

圖6仿真結果表明，在不同數(shù)據(jù)包數(shù)量下基于EPDT算法的Epidemic和Spray and Wait路由協(xié)議傳輸成功率均優(yōu)于傳統(tǒng)的Epidemic和Spray and Wait路由協(xié)議。當數(shù)據(jù)包達到1 200個時，EPDT-Epidemic克服Epidemic的弱勢，傳輸成功率幾乎接近Spray And Wait，平均傳輸成功率相比Epidemic高出16.2%。EPDT-Spray And Wait和Spray And Wait算法相比，平均傳輸成功率高出13.4%。

圖6 不同數(shù)據(jù)包對傳輸成功率的影響

圖7描述的是不同數(shù)據(jù)包對文件轉發(fā)次數(shù)的影響，Epidemic和Spray and Wait路由協(xié)議對消息的多副本復制依賴較大，隨著數(shù)據(jù)包數(shù)量的不斷增加，其消息轉發(fā)次數(shù)也有較明顯的增加。尤其在數(shù)據(jù)包個數(shù)接近900個時，其轉發(fā)次數(shù)增長較明顯。由于Epidemic算法的特性，其轉發(fā)消息的次數(shù)與消息的拷貝數(shù)量有關。而EPDT-Epidemic路由方法通過對節(jié)點的概率估計來進行消息拷貝，使得其轉發(fā)次數(shù)明顯降低，幾乎與Spray and Wait路由協(xié)議的轉發(fā)次數(shù)重合。EPDT-Spray and Wait路由協(xié)議通過尋找概率更優(yōu)的節(jié)點，使得節(jié)點相遇概率增大，嚴格控制轉發(fā)條件，所以在轉發(fā)次數(shù)上明顯優(yōu)于其他算法，平均轉發(fā)次數(shù)較傳統(tǒng)方法降低了18.6%。

圖7 不同數(shù)據(jù)包對文件轉發(fā)次數(shù)的影響

圖8描述的是不同的數(shù)據(jù)包對網(wǎng)絡開銷的影響。Epidemic算法由于數(shù)據(jù)包的增加，其消息副本數(shù)增加迅速，而真正投遞成功的消息數(shù)卻不多，網(wǎng)絡開銷自然增長明顯。EPDT-Epidemic路由方法考慮到只要在合適的相遇概率下才向節(jié)點復制數(shù)據(jù)，大幅度降低了網(wǎng)絡開銷，平均網(wǎng)絡開銷較Epidemic算法降低了14.6%，幾乎接近Spray and Wait路由算法網(wǎng)絡開銷。EPDT-Spray and Wait路由算法考慮到在數(shù)據(jù)噴射過程中，尋找最合適相遇概率的節(jié)點完成數(shù)據(jù)轉發(fā)，在節(jié)點等待過程時也在尋找合適的節(jié)點，平均網(wǎng)絡開銷較其他算法降低了15.4%。

圖8 不同數(shù)據(jù)包對網(wǎng)絡開銷的影響

5 結 語

本文提出一種車載機會網(wǎng)絡文件調度與數(shù)據(jù)傳輸算法，與其他算法相比，避免了僅根據(jù)文件到達時間或文件大小發(fā)送文件，而是根據(jù)鏈路持續(xù)時間發(fā)送對應文件。數(shù)據(jù)傳輸策略根據(jù)節(jié)點相遇的概率密度函數(shù)轉發(fā)消息，解決了傳統(tǒng)算法消息副本的過度發(fā)送以及消息副本轉發(fā)等待。仿真結果表明，所提方法在文件傳輸成功率、網(wǎng)絡平均時延和網(wǎng)絡負載率等方面表現(xiàn)出較好的性能。