基于多時間段優化貝葉斯網絡的車載容遲網絡路由算法

吳家皋，郭亞航，蔡沈磊，劉林峰

（1.南京郵電大學計算機學院，江蘇 南京 210023；2.江蘇省大數據安全與智能處理重點實驗室，江蘇 南京 210023）

1 引言

傳統網絡需要依靠端到端的鏈路以及傳輸控制協議/網際協議（TCP/IP,transmission control protocol/Internet protocol）等來保證數據傳輸的低時延與可靠性，然而當地震、海嘯等突發災難導致端到端鏈路故障時，傳統的基于“存儲?轉發”的路由模式將不再有效。因此，Jain 等[1]提出了延遲容忍網絡（DTN,delay tolerant network）概念，并已廣泛應用于星際網絡[2]、水下傳感網絡[3]、移動自組織網絡[4]、無線傳感網絡[5]、車載網絡[6]等領域。其中，車載容遲網絡（VDTN,vehicular delay tolerant network）將車載網絡與容遲網絡相結合，能為未來的自動駕駛和智能交通系統提供新的解決方案。DTN 采用新的基于“存儲?攜帶?轉發”的路由模式[7]，消息需要通過節點的移動和相遇進行轉發。但是，由于車輛的高速運動，可用于消息轉發的車輛間的相遇接觸時間非常有限。因此，對VDTN 路由算法的性能提出了更高的要求。

DTN 路由算法已有大量研究工作[8]，其中，較著名的有Epidemic[9]、Spray and Wait[10]和Prophet[11]等。Epidemic 是基于泛洪策略的路由算法，通常具有最小的消息傳輸時延，但泛洪往往會導致網絡擁塞。Spray and Wait 路由算法則通過限制消息副本的數目來解決消息泛洪問題。Prophet 路由算法則利用節點相遇的歷史信息估計不同節點與消息目的節點之間的相遇概率，以此決定消息轉發策略。然而，在VDTN 中，車輛的移動通常具有特定的模式，例如公交車遵循固定的路線和時刻表，私家車的移動傾向于有規律的軌跡，出租車的移動行為則體現了人流的熱區等。Prophet 路由算法并沒有很好地考慮車輛的這些移動模式。近年來，隨著機器學習和人工智能技術的興起，許多機器學習算法被應用到DTN 路由算法中，例如決策樹[12]、強化學習[13]、人工神經網絡[14]和樸素貝葉斯分類器[15-16]等。然而，決策樹和人工神經網絡容易出現過擬合問題，強化學習收斂速度較慢且容易導致額外的網絡路由開銷，樸素貝葉斯分類器則無法表達出屬性間的依賴關系。貝葉斯網絡（BN,Bayesian network）利用概率圖模型表示屬性間的依賴關系，能顯著提高VDTN 中節點移動模式預測的準確性[17]。BN 結構學習是BN 模型的核心問題之一，已提出的算法包括基于依賴關系的互信息算法[18]、基于評分搜索策略的K2 算法[19]以及基于遺傳算法的K2（K2GA,K2 based on genetic algorithm）算法[20]等。然而，VDTN中車輛節點的移動由于受到人類行為和生活習慣的影響有著明顯的時段性、周期性的特點。因此，單一的BN 結構無法準確地表達車輛移動模式的時段性特點。雖然文獻[21]也研究了基于多時間段BN的VDTN 路由算法，但其采用人工經驗的時間段劃分方案并非是最優劃分。針對上述問題，本文開展了基于多時間段BN 的VDTN 路由算法研究。本文主要的研究工作如下。

1) 提出了新的多時間段BN 模型。引入了更多與節點移動模式相關的屬性，包括剩余緩存比、平均時延、行駛距離等屬性，以更準確地描述車輛的移動模式；同時，提出了新的節點分類動態獎勵機制，使相遇和投遞獎勵的分配更合理，保證獎勵值與節點實際的類別相一致。

2) 提出了2 種新的BN 時間段的優化劃分算法：二分搜索 K2GA（BS-K2GA,binary search K2GA）算法和模擬退火K2GA（SA-K2GA,simulated annealing K2GA）算法。BS-K2GA 算法以二分貪心策略優化BN 的時間段劃分和網絡結構，具有簡單高效優勢；SA-K2GA 算法則將模擬退火算法和K2GA 算法相結合，能克服貪心算法容易陷入局部最優的缺點，進一步優化解的性能。

3) 提出了基于多時間段優化BN 的VDTN 路由算法，仿真實驗結果表明，通過優化后的多時間段BN 模型能夠準確地描述車輛的移動模式，顯著提高消息的投遞率，并降低消息的投遞時延。

2 系統模型

BN 由有向無環圖（DAG,directed acyclic graph）和條件概率表（CPT,conditional probability table）組成。令G=(V,E)為任意BN，其中，V是DAG的節點集，表示隨機變量；E是節點間的有向邊，表示隨機變量之間的直接依賴關系。CPT 表示隨機變量的聯合概率分布，可以定量地描述變量之間的依賴關系。

設在VDTN 中，源節點ns產生了一個目的節點為nd的消息，該消息可以經過一系列的中繼節點最終被轉發到達nd，問題的關鍵在于如何找到一條較優的傳輸路徑。因此，本文提出了一種優化的BN分類器模型用于估計VDTN 傳輸路徑中車輛中繼節點的消息投遞能力。

在VDTN 中，車輛節點的移動模式受人們生活習慣影響具有時段性的特點。基于真實數據集的實驗表明節點的活躍度呈現出規律性的分布[22]。在早晚高峰期，節點活躍度持續上升；在其他時間段，活躍度明顯下降。由此可見，單一結構的BN模型顯然無法描述所有時間段車輛的移動規律。因此，本文針對一天內的不同時間段構建不同的BN 模型，以更好地表達車輛的真實移動模式。如圖1 所示，將一整天劃分為σ個時間段，根據各個時間段的數據集來學習構造多個BN，這樣的多時間段BN 模型能更加準確地描述車輛節點的移動行為。接下來，如何確定最優的時間段劃分方案和各時間段對應的BN 結構則是本文要解決的首要問題。

圖1 多時間段貝葉斯網絡示意

圖2 是本文的基于多時間段優化BN 的VDTN路由算法框架，主要包含4 個部分：屬性選擇、分類標準、結構學習、推理與消息轉發策略。下面，先詳細介紹VDTN 的節點屬性選擇和分類標準，有關BN 結構優化學習、推理與消息轉發策略的內容將在第3 節中論述。

圖2 基于多時間段優化BN 的VDTN 路由算法框架

2.1 屬性選擇

用于構建BN 的隨機變量是與消息轉發密切相關的車輛節點的屬性。本文用向量X=＜X1,X2,X3,X4,X5,X6,X7,X8,X9,X10＞對其進行描述。

X1為區域碼，表示VDTN中的節點在轉發消息時所處的區域。整張地圖被劃分為k1個矩形區域，每個區域有相同的長寬和唯一的標識符。在本文中，整個區域的大小為35 km×25 km，被劃分為35 個小矩形區域，每個矩形的尺寸為5 km×5 km。

X2為時隙，表示VDTN中的節點在轉發消息時所處的時隙。選取這個屬性是因為車輛在一天中不同的時間段有不同的移動模式，根據車輛軌跡歷史數據集，車輛的移動主要集中在上午7 點到下午7 點。本文將粒度設置為15 min來離散化時間，因此共劃分為k2=48 個時隙。

X3為運動方向，表示VDTN 中的節點在轉發消息時的運動方向。本文將方向角粒度設置為π/4，車輛的運動角度可以離散化為k3=8 個方向，即東、西、南、北、東南、東北、西南、西北。

X4為平均接觸時間間隔，表示VDTN 中的節點遇見其他節點需要的平均時間。該值越小，說明車輛遇見其他車輛的概率越大，消息的投遞能力也越好。根據車輛軌跡歷史數據集，如公交車之間的平均相遇時間統計分布，本文設置平均接觸時間間隔的最大值為3 000 s，離散化粒度為300 s，因此平均接觸時間間隔被劃分為k4=10 個時間間隔。

X5為速度表示VDTN中節點的移動速度。根據車輛軌跡歷史數據集，VDTN 中車輛的最大速度為120 km/h，離散化粒度為24 km/h，因此速度被劃分為k5=5 個級別。

X6為路線編號，表示VDTN 中節點在轉發消息時的路線編號。VDTN 中的車輛移動具有一定的模式，而且通常會在固定的路線上行駛，例如公交路線。不同的車輛也可能在同一條道路上行駛，因此這些車輛具有相同的路線編號。本文主要以公交車編號作為線路編號，這個屬性可以較好地反映車輛的移動行為。

X7為剩余緩存比，表示VDTN 中節點剩余可用緩存大小占總緩存的比率。VDTN 節點攜帶的消息都需要存儲在緩存中進行轉發。本文將剩余可用緩存占比的離散化粒度設置為0.1，將其劃分為k6=10 個比率。

X8為平均時延表示消息從該節點轉發到消息的目的節點所經過的平均時間。平均時延越小，說明該節點轉發消息的效率越高。根據車輛軌跡歷史數據集，VDTN 中消息的最大平均時延為7 000 s，離散化粒度為1 000 s，因此平均時延被劃分為k8=7 個值。

X9為行駛距離表示VDTN 中車輛在轉發消息時距離上次車輛相遇所行駛的距離。根據車輛軌跡歷史數據集，VDTN 中車輛的最大行駛距離為35 km，離散化粒度為5 km，因此行駛距離可以離散化為k9=7 個值。

X10為投遞等級，表示節點轉發消息到消息目的節點的能力。投遞等級越高，表示該節點擁有越大的可能性將消息成功轉發到目的節點。

在上述的屬性變量中，X1～X9均易觀測獲得，可當作證據變量；X10則不能直接得到，故作為查詢變量。為了訓練BN 模型，本文提出了一種基于動態獎勵機制的節點分類標準，用獎勵值的離散化來表示X10并對訓練數據集進行標注。當BN模型訓練完成后，X10便可由證據變量X1～X9經BN 推理預測得到。

2.2 分類標準

本節詳細介紹基于蟻群優化算法的動態獎勵機制及其改進方案，以此作為節點投遞等級的分類標準。蟻群優化算法是一種尋找最優路徑的概率算法[23]，其路徑上的信息素會隨著時間的推移而揮發。同樣，節點獲得的獎勵值也應隨著時間的推移動態變化。在前期工作的基礎上[20-21]，本文提出新的VDTN 節點的動態獎勵分配機制。首先，節點間的相遇有利于消息的轉發，如果節點遇見一個消息投遞能力更強的中繼節點，那么該節點的消息投遞能力也會較高，因此本文定義了新的相遇獎勵值。其次，投遞時延和跳數都是重要的路由性能指標，因此本文在跳數投遞獎勵值的基礎上進一步加入了時延獎勵值。當某一消息經過一系列中繼節點，最終被投遞到目的節點時，該消息的目的節點將廣播一個小的確認（ACK,acknowledgement）數據包，該數據包包含該消息投遞路徑上的所有中繼節點的標識（ID，identification）以及從各個中繼節點到目的節點的時延，一旦某個中繼節點接收到了該報文，該節點將會被分配一定的跳數獎勵值和時延獎勵值。

通過上述方法，可以得到節點ni在t+1 時隙的獎勵值即

其中，ρ∈[0,1]表示獎勵值的老化系數，該系數使消息的獎勵值隨著時間不斷老化表示節點ni在t時隙內獲得的相遇獎勵值表示節點ni在t時隙內獲得的投遞獎勵值。

相遇獎勵值的計算式為

其中，Δψij(t)表示在t時隙相遇節點ni和nj的獎勵值之差；ψc（Δψij(t)）表示節點ni與節點nj相遇時，節點ni應分配的相遇獎勵值；R表示基礎相遇獎勵值；R c表示增量相遇獎勵值；γ表示超參數。因此，相遇獎勵值不再以固定值分配，而是根據相遇節點的獎勵值之差來決定。低獎勵值節點與高獎勵值節點相遇表明該低獎勵值節點有機會將消息轉發給投遞能力更強的中繼節點，有利于提高消息的投遞率，因此低獎勵值節點應當得到較高的相遇獎勵值。另外表示節點ni在t時隙內相遇節點的集合，因此表達了節點ni在t時隙內獲得的累計相遇獎勵值。

令m表示第m個經過節點ni成功投遞的消息，Om表示消息m的投遞路徑，則投遞獎勵值的計算式為

綜上所述，節點的獎勵值將隨著節點的相遇頻率、消息的成功投遞數、投遞跳數和等動態更新。為了將該獎勵機制應用于BN 模型作為節點的分類標準，本文將獎勵值按相同的間隔離散化為k10個等級分別對應投遞等級X10的等級越高，表明節點有更大的概率將消息轉發到目的節點，因此使用該動態獎勵機制當作節點的分類標準可以幫助路由算法做出正確的路由決策。在進行路由決策時，攜帶消息的節點可以通過BN 模型推理并預測其鄰居節點的投遞等級，由此來決定是否將消息轉發到鄰居節點。

3 結構學習及消息轉發

當基于屬性向量X的訓練數據集收集完成后，接下來的任務就是進行BN 結構的訓練和學習。本節將在K2GA算法的基礎上研究多時間段的最優劃分和各時間段對應的BN 結構學習問題。

3.1 優化問題

設D表示時間范圍為[0,τ)的全部訓練數據集。現要將總時間范圍劃分成多個時間段；令σ表示要劃分的時間段個數表示第k個時間段，其中，分別表示該時間段的起始時間和終止時間，且。根據時間段將數據集D劃分為σ個子集，Dk表示在數據集D中處于第k個時間段的數據集。利用K2GA 算法，可以優化得到數據集Dk對應BN 結構Gk及其CH（Cooper-Herskovits）評分函數值Fk。這里，K2GA 算法采用的CH 評分函數是BN 結構學習中用來判斷學習結果優劣的常用指標之一[24]。故上述過程可表示為

對于多時間段BN 結構學習，本文定義σ段BN的平均CH 評分值為F，以最大化F作為問題的優化目標，即

為了求解上述問題，需要尋找一個使F值最大化的時間段劃分方案及相應的BN 結構。當σ較小時，可以采用遍歷算法來搜索；但是當σ較大時，遍歷算法的開銷將呈指數上升。為了降低算法的時間復雜度同時提高優化效率，本文提出了2 種多時間段BN結構學習算法：BS-K2GA算法和SA-K2GA算法。

3.2 BS-K2GA 算法

BS-K2GA 算法以二分搜索方式進行多時間段BN 結構的學習和優化。該算法首先尋找最佳分割點，將整個時間范圍分成2 個時間段；然后對這2 個時間段分別進行二分搜索；如此迭代，直到達到所需要的時間段劃分個數。

算法1 給出BS-K2GA 的偽代碼，其輸入為需要的時間段劃分個數σ和訓練數據集D，輸出為表示第k個時間段的解（包括時間段的劃分、BN結構和評分等）。步驟1)～步驟3)利用K2GA 算法獲得在全部數據集D下的初始解u1。步驟4)～步驟9)通過循環迭代從集合U中取出uk并利用BSplit算法求得最佳的二分方案，并將結果并入集合U中。由于評分較低的uk可能具有更大的優化空間，因此步驟5)每次都選取評分最低的uk進行二分。最后，步驟10)返回結果集U。BSplit 算法的偽代碼由算法2 給出，該算法對輸入的當前解uk進一步劃分，得到最佳二分方案ul和ur。步驟1)以tc為分割點將數據集Dk二分為Dl和Dr；步驟2)～步驟3)調用K2GA 算法分別求得數據集Dl和Dr對應的BN 結構及其評分；步驟4)求最佳平均評分最高的最佳分割點步驟5)～步驟7)生成并返回最佳的二分解。由于將數據集Dk二分所生成的BN 能更好地描述實際規律，因此BSplit 算法總能找到一個較優的二分方案。

下面，簡要分析BS-K2GA 算法的時間復雜度。先根據K2 算法[25]，得到K2GA 算法的時間復雜度為O(wzhg2)，其中，w為遺傳算法的迭代次數，z為遺傳算法的種群數，h為數據集中的樣本數，g為用于構建BN 的屬性個數。對于BS-K2GA 算法，設Δτ表示搜索的時間段步長，則每次最佳分割點的計算時間復雜度為O(τ/ Δτ)，而總的時間段劃分個數為σ。由此，得到BS-K2GA 的時間復雜度為O(στwzhg2/Δτ)。BS-K2GA 算法以貪心策略進行時間段劃分，時間復雜度較低，但是該算法容易陷入局部最優，無法找到最優的時間段劃分方案。

3.3 SA-K2GA 算法

模擬退火（SA,simulated annealing）算法[26]是一種通用的隨機搜索算法，其基本思想為從某一較高初溫出發，以熱力學統計概率在解空間中隨機尋找目標函數的最優解，使算法能概率性地從局部最優解中跳出，并隨著溫度參數的不斷降低最終趨于全局最優。在SA-K2GA 算法中，設溫度參數為C0，目標函數值為多時間段BN 的平均評分F。首先隨機將整個時間范圍[0,τ)劃分為σ個時間段，通過K2GA 算法求得該劃分下多時間段BN 結構及其平均評分F的解；根據當前溫度和該解的評分值以一定概率接收其作為當前解；降低溫度并對當前的時間劃分做隨機擾動得到新的劃分方案，重復上述過程，直到溫度降低為最低值。此時，算法的當前解即最優解。

算法3 給出了SA-K2GA 算法的偽代碼，其中，C0表示初始溫度，Cmin表示最低溫度，λ表示溫度的變化率，Δt表示時間段調整的步長。步驟1)～步驟7)生成初始化解。首先在整個時間范圍[0,τ)內隨機產生的σ-1個時間分割點其中根據Tc將數據集劃分成σ個子集{D1,D2,…,Dσ}，其中，Dk對應第k個時間段[t k-1,tk)，k∈[1,σ]，t0=0，tσ=τ。然后利用K2GA 算法計算Tc劃分下的BN 結構及其CH 評分產生當前解U。步驟9)～步驟10)以步長Δt對Tc中的分割點進行隨機擾動產生新的劃分。同理，步驟11)～步驟15)利用K2GA 算法計算劃分下的新解U′。步驟16)～步驟19)計算解U′和U的目標函數值之差ΔF。若ΔF>0，則直接將U′賦值給U，即接受新解為最優解當前解；否則，采用Metropolis準則[27]根據exp(-ΔF/C)＞rand以一定概率接收新解，其中，rand 為能產生[0,1]范圍實數的隨機函數。步驟20)用于降低當前溫度C，然后循環執行上述過程，直到C小于Cmin，步驟8)的循環條件不再滿足，循環結束。步驟22)返回的解即當前的最優解。

由于SA-K2GA 算法在溫度變化率λ的控制下由初始溫度C0降至最低溫度Cmin所需要執行的輪數為且在每輪循環中利用K2GA 算法計算σ個時間段BN 結構的評分，因此SA-K2GA算法的時間復雜度為。與BS-K2GA 算法相比，SA-K2GA 的算法復雜度略高，但后續仿真實驗結果表明，SA-K2GA 的性能要優于前者。

3.4 消息轉發策略

為了實現本文提出的VDTN 路由算法，首先需要收集所有車輛的歷史信息并生成訓練數據集。然后使用BS-K2GA 或SA-K2GA 算法訓練學習最優的時間段劃分方案和各時間段最優的BN 結構。然后，基于優化后的多時間段BN 模型，通過BN 推理預測VDTN 中車輛節點的消息投遞等級X10，由此決定消息的轉發策略。而對于某一確定時間段的BN 模型，X10推理方法如下。

由此，本文提出基于多時間段優化BN 的VDTN 路由算法，其消息轉發策略如下。

設攜帶消息的當前車輛節點與另一車輛節點相遇，則當且僅當滿足以下2 種情況時，當前車輛節點才會把消息轉發給相遇車輛節點。

1) 相遇節點為消息的目的節點時，消息將被直接投遞到目的節點。

2) 當相遇節點非消息的目的節點時，兩車將根據所處的時刻，選擇相應時間段的BN 模型，并利用式(6)推理得到各自的投遞等級X10。若當前節點的X10低于相遇節點的X10，則將消息轉發給相遇節點；否則當前節點不進行消息轉發，繼續攜帶消息移動，直到遇見目的節點或投遞等級更高的相遇節點。

4 實驗結果與分析

4.1 移動軌跡與仿真參數

本文進行仿真實驗所使用的數據來自巴西里約熱內盧公交系統所記錄的真實公交車運行軌跡。該數據是從CRAWDAD[29]獲得的，其中包含了覆蓋1 200 km2、涉及17 723 輛公交車的運動軌跡。盡管原始數據集提供了一天內完整的24 h 移動數據，但為了使實驗環境更接近真實的生活環境，這里選取其中98 輛車在上午7 點到下午7 點的數據，并將范圍縮小為35 km×25 km 的區域內，其中包含了這個城市較繁華的商業區。

本文中的多時間段優化BN 結構學習算法以及團樹構造算法是使用MATLAB[30]軟件來實現的，同時該算法調用了BN 工具箱獲取BN 的CH 評分值。當離線完成BN 學習以及團樹構造后，使用DTN仿真軟件THE ONE（the opportunistic network environment simulator）[31]對本文提出的路由算法進行仿真實驗。仿真參數如表1 所示。

表1 仿真參數

4.2 生成訓練數據集

由于BN 結構學習需要VDTN 中車輛的屬性數據，因此需要先采集車輛的歷史數據構造訓練數據集。雖然數據集包含一個月的數據，但由于采集軌跡數據時的設備故障，導致期間有數天的軌跡數據不連續，因此本文使用了其中14 天的數據來進行仿真實驗。從14 天的軌跡數據中隨機選取10 天的數據作為訓練集，剩下4 天的數據作為測試集。在構造訓練數據集的仿真實驗中，VDTN中車輛的路由算法設置為基于泛洪方式的Epidemic 算法，這樣能獲得更全面的路由信息。而動態獎勵機制的參數設置為ψ d=600，ψ l=100，R=50，Rc=100，ρ=0.25。車輛的屬性數據表起初為空表，當車輛相遇時，車輛當前的屬性值（X1～X9）以及獎勵值就被記錄到屬性表內。當仿真結束時，就可以取出所有車輛本地存儲的屬性表合并成訓練數據集了。

4.3 性能指標

為了評價VDTN 路由算法的有效性，通常采用以下3 個指標來衡量路由協議性能的好壞。

投遞率：成功投遞到目的節點的消息數目與源節點產生的消息個數之比。

投遞時延：成功投遞到目的節點的消息所經過的平均時間。

開銷：在消息成功投遞到目的節點時，網絡中所產生的平均消息副本個數。

在實驗中，本文主要采用消息報文的生存時間（TTL,time to live）作為變量對上述性能指標進行評價，這是路由協議中的重要參數之一。

4.4 參數σ 取值分析

本節主要探討參數σ對多時間段貝葉斯網絡性能的影響。通過改變參數σ的取值，利用SA-K2GA 算法學習不同的BN 結構。根據學習獲得的BN 結構設計VDTN 路由算法，并對其性能進行對比實驗，如圖3 所示。

圖3 不同時間階段BN 路由算法性能比較

從圖3(a)可以看出，隨著σ的增大，多時間段貝葉斯網絡路由算法的投遞率不斷升高，σ=3 時的投遞率比σ=1 時的投遞率高5%，然而當σ=4 時，雖然在TTL<100 時，投遞率較高，但是隨著TTL 的增加，投遞率反而低于σ=3 時。這是因為較大的σ對時間段的劃分可能過細，容易造成BN 模型的“過擬合”問題。從圖3(b)可以看出，隨著σ的增大，消息投遞的平均時延不斷減小。同理，當σ=3 時，平均時延達到最低，而σ=4 的平均時延比σ=3 并未有所改進。從圖3(c)可以看出，隨著σ的增大，路由算法的網絡開銷不斷降低，當σ=3時，網絡開銷達到較低水平，而σ=4 的網絡開銷相比于σ=3 的改進并不明顯。綜上所述，三階段BN 路由算法可以更準確地學習到車輛的移動模式，在消息轉發上的性能也更好。本文在后續實驗中均取時間段個數σ=3。

4.5 BN 多時間段優化劃分算法的比較

本節主要比較不同的BN 多時間段優化劃分算法對VDTN 路由性能的影響。除了本文提出的BS-K2GA 和SA-K2GA 算法，實驗還比較了以下2 種算法。

Opt 算法：利用K2GA 算法通過全局遍歷得到評分F取值最高的σ階段BN 結構。

Avg 算法：將整個時間范圍等分為σ個階段，再利用K2GA 算法學習得到σ階段BN 結構。

圖4 給出了采用不同BN 多時間段優化劃分算法的VDTN 路由性能比較結果。從圖4(a)可以看出，采用Opt 的路由算法在投遞率上表現出了最優的性能，而SA-K2GA 的投遞率僅次于Opt。當 TTL=120 min 時，SA-K2GA 的投遞率比BS-K2GA 高3%，比Avg 高7%。由于采用Opt的三階段BN 是通過遍歷得到的，因此該網絡結構具有更高的評分，相應的投遞率也最高。SA-K2GA 的投遞率與Opt 相差不大，從側面說明了SA-K2GA 算法確實能獲得較優的多時間段BN劃分方案。BS-K2GA 的投遞率低于SA-K2GA，因為BS-K2GA 基于簡單的貪心算法進行求解，通常無法獲取最優的劃分方案。但BS-K2GA 算法采用了將評分最低的BN 所對應的時間段進行二分策略，因此其投遞率要明顯高于采用時間等分策略的Avg 算法。同理，如圖4(b)所示，投遞時延由低到高的算法依次仍為Opt、SA-K2GA、BS-K2GA 和Avg。這里，通過Avg 算法得到的BN 對節點投遞等級的預測效果最差，無法篩選出較優的中繼節點，導致消息傳遞的時延最高，而Opt 和SA-K2GA 的BN 則表現出了較強的節點投遞等級預測能力。

圖4 采用不同BN 多時間段優化劃分算法的路由性能比較

圖4(c)表明Opt 和SA-K2GA 的路由開銷都比較低。當TTL≤110 min 時，SA-K2GA 的開銷低于Opt；當TTL>110 min 時，Opt 的開銷更小。綜上所述，雖然采用Opt 算法的VDTN 路由性能總體最好，但其采用的遍歷算法復雜度太高，當σ較大時，該算法將無法在多項式時間內求得劃分方案。SA-K2GA算法將模擬退火與K2GA 算法相結合降低了時間復雜度，并且在路由性能上媲美Opt，因此SA-K2GA算法對求解多時間段劃分方案是可行有效的。

4.6 與經典路由算法的比較

本節將所提出的VDTN 路由算法與經典的Epidemic[9]、Prophet[11]以及基于樸素貝葉斯的（NB,naive Bayesian）路由算法[15]進行性能比較，其中，多時間段優化采用SA-K2GA 算法。

圖5 為各種路由算法在不同TTL 條件下的性能仿真結果。圖5(a)表明SA-K2GA 的投遞率高于Prophet 和NB。當TTL=100 min 時，SA-K2GA的投遞率比Prophet 高10%，比NB 高8%。因為SA-K2GA 不僅考慮到了消息傳遞的歷史信息，還可以學習到在不同時間段車輛的移動模式。NB在投遞率上的表現也優于Prophet，說明NB 也能較好地學習車輛的移動模式，但其條件獨立性假設限制了其性能。另外，由于Epidemic 采用泛洪策略進行消息轉發，因此其投遞率最高。在圖5(b)中，SA-K2GA 的投遞時延低于Prophet 和NB。這是因為在SA-K2GA 中節點的投遞等級是根據節點的獎勵值來劃分的，其中，在投遞獎勵值中，距離目的節點越近或傳輸時延越低的中繼節點都能得到較高的獎勵值，因此路由算法就選擇時延較低或跳數較少的傳輸路徑進行消息轉發。同理，Epidemic 的投遞時延也是最低的。從圖5(c)可以看出，隨著TTL 的增加，路由開銷總體上呈上升趨勢。但是與Epidemic、Prophet 和NB 相比，SA-K2GA 的開銷最低，因為SA-K2GA 只會將消息轉發給投遞等級較高的中繼節點。但是，Epidemic 的開銷卻明顯高于其他算法。

圖5 各種路由算法在不同TTL 條件下的性能比較

圖6 給出了各種路由算法在不同VDTN 節點緩存大小條件下的性能仿真結果。如圖6(a)所示，隨著節點緩存的不斷增加，消息的投遞率也在不斷上升。當節點緩存為17 MB 時，SA-K2GA 的投遞率比Prophet 高近7%，比NB 高4%。如圖6(b)所示，SA-K2GA 的投遞時延明顯低于Prophet 和NB，因為其改進的獎勵值機制將消息的投遞時延也考慮在內。如圖6(c)所示，隨著節點緩存的不斷增加，SA-K2GA 的網絡開銷不斷下降，而且相比Epidemic、Prophet 和NB，SA-K2GA 具有最低的路由開銷。

圖6 各種路由算法在不同節點緩存大小條件下的性能比較

5 結束語

本文研究VDTN 的消息轉發問題，根據車輛節點移動模式的時段性以及節點屬性之間的依賴關系，提出并建立了改進的多時間段BN 模型。為解決多時間段優化劃分和BN 結構學習問題，提出了BS-K2GA 和SA-K2GA 這2 種算法。在此基礎上，提出了基于多時間段優化BN 的VDTN 路由算法。仿真實驗結果驗證了多時間段BN 模型及其優化算法的可行性和有效性。同時，本文提出的VDTN路由算法也具有高投遞率、低時延和低開銷的性能表現。

在未來的工作中，筆者將繼續優化模型，如對車輛屬性的選擇及其離散化標準進行優化，進一步提高算法效率；同時，研究VDTN 的時變特征，建立基于時序概率的動態BN 模型等。