一種車載機會網絡文件調度與數據傳輸算法

龍 浩 張書奎 張 力

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

0 引 言

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

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

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

1 相關工作

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

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

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

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

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

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

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

2 文件調度算法設計

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

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

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

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

算法偽代碼如下：

1: function input(Fi, T, t)

//根據文件的傳輸耗時準備好發送文件序列

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

//根據鏈路持續時間對應發送文件

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

13： else

14: wait next C

15： end if

16： end for

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

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

圖1 車輛相遇運行示意圖

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

(1)

當v1

(2)

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

(3)

3 基于節點相遇概率的數據傳輸策略

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

圖2 車輛和中間節點的通信

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

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

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

Δt=tA-tB

(4)

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

(5)

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

ft(t)=n×mt0

(6)

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

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

(7)

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

(8)

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

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

(9)

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

(10)

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

4 仿真及性能分析

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

表1 仿真參數設置

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

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

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

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

圖4 不同緩存容量的網絡平均時延

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

圖5 不同緩存容量的網絡負載率

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

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

圖6 不同數據包對傳輸成功率的影響

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

圖7 不同數據包對文件轉發次數的影響

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

圖8 不同數據包對網絡開銷的影響

5 結 語

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