基于多時(shí)間段優(yōu)化貝葉斯網(wǎng)絡(luò)的車載容遲網(wǎng)絡(luò)路由算法

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

（1.南京郵電大學(xué)計(jì)算機(jī)學(xué)院，江蘇 南京 210023；2.江蘇省大數(shù)據(jù)安全與智能處理重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210023）

1 引言

傳統(tǒng)網(wǎng)絡(luò)需要依靠端到端的鏈路以及傳輸控制協(xié)議/網(wǎng)際協(xié)議（TCP/IP,transmission control protocol/Internet protocol）等來保證數(shù)據(jù)傳輸?shù)牡蜁r(shí)延與可靠性，然而當(dāng)?shù)卣稹⒑[等突發(fā)災(zāi)難導(dǎo)致端到端鏈路故障時(shí)，傳統(tǒng)的基于“存儲(chǔ)?轉(zhuǎn)發(fā)”的路由模式將不再有效。因此，Jain 等[1]提出了延遲容忍網(wǎng)絡(luò)（DTN,delay tolerant network）概念，并已廣泛應(yīng)用于星際網(wǎng)絡(luò)[2]、水下傳感網(wǎng)絡(luò)[3]、移動(dòng)自組織網(wǎng)絡(luò)[4]、無線傳感網(wǎng)絡(luò)[5]、車載網(wǎng)絡(luò)[6]等領(lǐng)域。其中，車載容遲網(wǎng)絡(luò)（VDTN,vehicular delay tolerant network）將車載網(wǎng)絡(luò)與容遲網(wǎng)絡(luò)相結(jié)合，能為未來的自動(dòng)駕駛和智能交通系統(tǒng)提供新的解決方案。DTN 采用新的基于“存儲(chǔ)?攜帶?轉(zhuǎn)發(fā)”的路由模式[7]，消息需要通過節(jié)點(diǎn)的移動(dòng)和相遇進(jìn)行轉(zhuǎn)發(fā)。但是，由于車輛的高速運(yùn)動(dòng)，可用于消息轉(zhuǎn)發(fā)的車輛間的相遇接觸時(shí)間非常有限。因此，對VDTN 路由算法的性能提出了更高的要求。

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

1) 提出了新的多時(shí)間段BN 模型。引入了更多與節(jié)點(diǎn)移動(dòng)模式相關(guān)的屬性，包括剩余緩存比、平均時(shí)延、行駛距離等屬性，以更準(zhǔn)確地描述車輛的移動(dòng)模式；同時(shí)，提出了新的節(jié)點(diǎn)分類動(dòng)態(tài)獎(jiǎng)勵(lì)機(jī)制，使相遇和投遞獎(jiǎng)勵(lì)的分配更合理，保證獎(jiǎng)勵(lì)值與節(jié)點(diǎn)實(shí)際的類別相一致。

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

3) 提出了基于多時(shí)間段優(yōu)化BN 的VDTN 路由算法，仿真實(shí)驗(yàn)結(jié)果表明，通過優(yōu)化后的多時(shí)間段BN 模型能夠準(zhǔn)確地描述車輛的移動(dòng)模式，顯著提高消息的投遞率，并降低消息的投遞時(shí)延。

2 系統(tǒng)模型

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

設(shè)在VDTN 中，源節(jié)點(diǎn)ns產(chǎn)生了一個(gè)目的節(jié)點(diǎn)為nd的消息，該消息可以經(jīng)過一系列的中繼節(jié)點(diǎn)最終被轉(zhuǎn)發(fā)到達(dá)nd，問題的關(guān)鍵在于如何找到一條較優(yōu)的傳輸路徑。因此，本文提出了一種優(yōu)化的BN分類器模型用于估計(jì)VDTN 傳輸路徑中車輛中繼節(jié)點(diǎn)的消息投遞能力。

在VDTN 中，車輛節(jié)點(diǎn)的移動(dòng)模式受人們生活習(xí)慣影響具有時(shí)段性的特點(diǎn)?；谡鎸?shí)數(shù)據(jù)集的實(shí)驗(yàn)表明節(jié)點(diǎn)的活躍度呈現(xiàn)出規(guī)律性的分布[22]。在早晚高峰期，節(jié)點(diǎn)活躍度持續(xù)上升；在其他時(shí)間段，活躍度明顯下降。由此可見，單一結(jié)構(gòu)的BN模型顯然無法描述所有時(shí)間段車輛的移動(dòng)規(guī)律。因此，本文針對一天內(nèi)的不同時(shí)間段構(gòu)建不同的BN 模型，以更好地表達(dá)車輛的真實(shí)移動(dòng)模式。如圖1 所示，將一整天劃分為σ個(gè)時(shí)間段，根據(jù)各個(gè)時(shí)間段的數(shù)據(jù)集來學(xué)習(xí)構(gòu)造多個(gè)BN，這樣的多時(shí)間段BN 模型能更加準(zhǔn)確地描述車輛節(jié)點(diǎn)的移動(dòng)行為。接下來，如何確定最優(yōu)的時(shí)間段劃分方案和各時(shí)間段對應(yīng)的BN 結(jié)構(gòu)則是本文要解決的首要問題。

圖1 多時(shí)間段貝葉斯網(wǎng)絡(luò)示意

圖2 是本文的基于多時(shí)間段優(yōu)化BN 的VDTN路由算法框架，主要包含4 個(gè)部分：屬性選擇、分類標(biāo)準(zhǔn)、結(jié)構(gòu)學(xué)習(xí)、推理與消息轉(zhuǎn)發(fā)策略。下面，先詳細(xì)介紹VDTN 的節(jié)點(diǎn)屬性選擇和分類標(biāo)準(zhǔn)，有關(guān)BN 結(jié)構(gòu)優(yōu)化學(xué)習(xí)、推理與消息轉(zhuǎn)發(fā)策略的內(nèi)容將在第3 節(jié)中論述。

圖2 基于多時(shí)間段優(yōu)化BN 的VDTN 路由算法框架

2.1 屬性選擇

用于構(gòu)建BN 的隨機(jī)變量是與消息轉(zhuǎn)發(fā)密切相關(guān)的車輛節(jié)點(diǎn)的屬性。本文用向量X=＜X1,X2,X3,X4,X5,X6,X7,X8,X9,X10＞對其進(jìn)行描述。

X1為區(qū)域碼，表示VDTN中的節(jié)點(diǎn)在轉(zhuǎn)發(fā)消息時(shí)所處的區(qū)域。整張地圖被劃分為k1個(gè)矩形區(qū)域，每個(gè)區(qū)域有相同的長寬和唯一的標(biāo)識(shí)符。在本文中，整個(gè)區(qū)域的大小為35 km×25 km，被劃分為35 個(gè)小矩形區(qū)域，每個(gè)矩形的尺寸為5 km×5 km。

X2為時(shí)隙，表示VDTN中的節(jié)點(diǎn)在轉(zhuǎn)發(fā)消息時(shí)所處的時(shí)隙。選取這個(gè)屬性是因?yàn)檐囕v在一天中不同的時(shí)間段有不同的移動(dòng)模式，根據(jù)車輛軌跡歷史數(shù)據(jù)集，車輛的移動(dòng)主要集中在上午7 點(diǎn)到下午7 點(diǎn)。本文將粒度設(shè)置為15 min來離散化時(shí)間，因此共劃分為k2=48 個(gè)時(shí)隙。

X3為運(yùn)動(dòng)方向，表示VDTN 中的節(jié)點(diǎn)在轉(zhuǎn)發(fā)消息時(shí)的運(yùn)動(dòng)方向。本文將方向角粒度設(shè)置為π/4，車輛的運(yùn)動(dòng)角度可以離散化為k3=8 個(gè)方向，即東、西、南、北、東南、東北、西南、西北。

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

X5為速度表示VDTN中節(jié)點(diǎn)的移動(dòng)速度。根據(jù)車輛軌跡歷史數(shù)據(jù)集，VDTN 中車輛的最大速度為120 km/h，離散化粒度為24 km/h，因此速度被劃分為k5=5 個(gè)級(jí)別。

X6為路線編號(hào)，表示VDTN 中節(jié)點(diǎn)在轉(zhuǎn)發(fā)消息時(shí)的路線編號(hào)。VDTN 中的車輛移動(dòng)具有一定的模式，而且通常會(huì)在固定的路線上行駛，例如公交路線。不同的車輛也可能在同一條道路上行駛，因此這些車輛具有相同的路線編號(hào)。本文主要以公交車編號(hào)作為線路編號(hào)，這個(gè)屬性可以較好地反映車輛的移動(dòng)行為。

X7為剩余緩存比，表示VDTN 中節(jié)點(diǎn)剩余可用緩存大小占總緩存的比率。VDTN 節(jié)點(diǎn)攜帶的消息都需要存儲(chǔ)在緩存中進(jìn)行轉(zhuǎn)發(fā)。本文將剩余可用緩存占比的離散化粒度設(shè)置為0.1，將其劃分為k6=10 個(gè)比率。

X8為平均時(shí)延表示消息從該節(jié)點(diǎn)轉(zhuǎn)發(fā)到消息的目的節(jié)點(diǎn)所經(jīng)過的平均時(shí)間。平均時(shí)延越小，說明該節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的效率越高。根據(jù)車輛軌跡歷史數(shù)據(jù)集，VDTN 中消息的最大平均時(shí)延為7 000 s，離散化粒度為1 000 s，因此平均時(shí)延被劃分為k8=7 個(gè)值。

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

X10為投遞等級(jí)，表示節(jié)點(diǎn)轉(zhuǎn)發(fā)消息到消息目的節(jié)點(diǎn)的能力。投遞等級(jí)越高，表示該節(jié)點(diǎn)擁有越大的可能性將消息成功轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。

在上述的屬性變量中，X1～X9均易觀測獲得，可當(dāng)作證據(jù)變量；X10則不能直接得到，故作為查詢變量。為了訓(xùn)練BN 模型，本文提出了一種基于動(dòng)態(tài)獎(jiǎng)勵(lì)機(jī)制的節(jié)點(diǎn)分類標(biāo)準(zhǔn)，用獎(jiǎng)勵(lì)值的離散化來表示X10并對訓(xùn)練數(shù)據(jù)集進(jìn)行標(biāo)注。當(dāng)BN模型訓(xùn)練完成后，X10便可由證據(jù)變量X1～X9經(jīng)BN 推理預(yù)測得到。

2.2 分類標(biāo)準(zhǔn)

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

通過上述方法，可以得到節(jié)點(diǎn)ni在t+1 時(shí)隙的獎(jiǎng)勵(lì)值即

其中，ρ∈[0,1]表示獎(jiǎng)勵(lì)值的老化系數(shù)，該系數(shù)使消息的獎(jiǎng)勵(lì)值隨著時(shí)間不斷老化表示節(jié)點(diǎn)ni在t時(shí)隙內(nèi)獲得的相遇獎(jiǎng)勵(lì)值表示節(jié)點(diǎn)ni在t時(shí)隙內(nèi)獲得的投遞獎(jiǎng)勵(lì)值。

相遇獎(jiǎng)勵(lì)值的計(jì)算式為

其中，Δψij(t)表示在t時(shí)隙相遇節(jié)點(diǎn)ni和nj的獎(jiǎng)勵(lì)值之差；ψc（Δψij(t)）表示節(jié)點(diǎn)ni與節(jié)點(diǎn)nj相遇時(shí)，節(jié)點(diǎn)ni應(yīng)分配的相遇獎(jiǎng)勵(lì)值；R表示基礎(chǔ)相遇獎(jiǎng)勵(lì)值；R c表示增量相遇獎(jiǎng)勵(lì)值；γ表示超參數(shù)。因此，相遇獎(jiǎng)勵(lì)值不再以固定值分配，而是根據(jù)相遇節(jié)點(diǎn)的獎(jiǎng)勵(lì)值之差來決定。低獎(jiǎng)勵(lì)值節(jié)點(diǎn)與高獎(jiǎng)勵(lì)值節(jié)點(diǎn)相遇表明該低獎(jiǎng)勵(lì)值節(jié)點(diǎn)有機(jī)會(huì)將消息轉(zhuǎn)發(fā)給投遞能力更強(qiáng)的中繼節(jié)點(diǎn)，有利于提高消息的投遞率，因此低獎(jiǎng)勵(lì)值節(jié)點(diǎn)應(yīng)當(dāng)?shù)玫捷^高的相遇獎(jiǎng)勵(lì)值。另外表示節(jié)點(diǎn)ni在t時(shí)隙內(nèi)相遇節(jié)點(diǎn)的集合，因此表達(dá)了節(jié)點(diǎn)ni在t時(shí)隙內(nèi)獲得的累計(jì)相遇獎(jiǎng)勵(lì)值。

令m表示第m個(gè)經(jīng)過節(jié)點(diǎn)ni成功投遞的消息，Om表示消息m的投遞路徑，則投遞獎(jiǎng)勵(lì)值的計(jì)算式為

綜上所述，節(jié)點(diǎn)的獎(jiǎng)勵(lì)值將隨著節(jié)點(diǎn)的相遇頻率、消息的成功投遞數(shù)、投遞跳數(shù)和等動(dòng)態(tài)更新。為了將該獎(jiǎng)勵(lì)機(jī)制應(yīng)用于BN 模型作為節(jié)點(diǎn)的分類標(biāo)準(zhǔn)，本文將獎(jiǎng)勵(lì)值按相同的間隔離散化為k10個(gè)等級(jí)分別對應(yīng)投遞等級(jí)X10的等級(jí)越高，表明節(jié)點(diǎn)有更大的概率將消息轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)，因此使用該動(dòng)態(tài)獎(jiǎng)勵(lì)機(jī)制當(dāng)作節(jié)點(diǎn)的分類標(biāo)準(zhǔn)可以幫助路由算法做出正確的路由決策。在進(jìn)行路由決策時(shí)，攜帶消息的節(jié)點(diǎn)可以通過BN 模型推理并預(yù)測其鄰居節(jié)點(diǎn)的投遞等級(jí)，由此來決定是否將消息轉(zhuǎn)發(fā)到鄰居節(jié)點(diǎn)。

3 結(jié)構(gòu)學(xué)習(xí)及消息轉(zhuǎn)發(fā)

當(dāng)基于屬性向量X的訓(xùn)練數(shù)據(jù)集收集完成后，接下來的任務(wù)就是進(jìn)行BN 結(jié)構(gòu)的訓(xùn)練和學(xué)習(xí)。本節(jié)將在K2GA算法的基礎(chǔ)上研究多時(shí)間段的最優(yōu)劃分和各時(shí)間段對應(yīng)的BN 結(jié)構(gòu)學(xué)習(xí)問題。

3.1 優(yōu)化問題

設(shè)D表示時(shí)間范圍為[0,τ)的全部訓(xùn)練數(shù)據(jù)集?，F(xiàn)要將總時(shí)間范圍劃分成多個(gè)時(shí)間段；令σ表示要?jiǎng)澐值臅r(shí)間段個(gè)數(shù)表示第k個(gè)時(shí)間段，其中，分別表示該時(shí)間段的起始時(shí)間和終止時(shí)間，且。根據(jù)時(shí)間段將數(shù)據(jù)集D劃分為σ個(gè)子集，Dk表示在數(shù)據(jù)集D中處于第k個(gè)時(shí)間段的數(shù)據(jù)集。利用K2GA 算法，可以優(yōu)化得到數(shù)據(jù)集Dk對應(yīng)BN 結(jié)構(gòu)Gk及其CH（Cooper-Herskovits）評分函數(shù)值Fk。這里，K2GA 算法采用的CH 評分函數(shù)是BN 結(jié)構(gòu)學(xué)習(xí)中用來判斷學(xué)習(xí)結(jié)果優(yōu)劣的常用指標(biāo)之一[24]。故上述過程可表示為

對于多時(shí)間段BN 結(jié)構(gòu)學(xué)習(xí)，本文定義σ段BN的平均CH 評分值為F，以最大化F作為問題的優(yōu)化目標(biāo)，即

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

3.2 BS-K2GA 算法

BS-K2GA 算法以二分搜索方式進(jìn)行多時(shí)間段BN 結(jié)構(gòu)的學(xué)習(xí)和優(yōu)化。該算法首先尋找最佳分割點(diǎn)，將整個(gè)時(shí)間范圍分成2 個(gè)時(shí)間段；然后對這2 個(gè)時(shí)間段分別進(jìn)行二分搜索；如此迭代，直到達(dá)到所需要的時(shí)間段劃分個(gè)數(shù)。

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

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

3.3 SA-K2GA 算法

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

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

由于SA-K2GA 算法在溫度變化率λ的控制下由初始溫度C0降至最低溫度Cmin所需要執(zhí)行的輪數(shù)為且在每輪循環(huán)中利用K2GA 算法計(jì)算σ個(gè)時(shí)間段BN 結(jié)構(gòu)的評分，因此SA-K2GA算法的時(shí)間復(fù)雜度為。與BS-K2GA 算法相比，SA-K2GA 的算法復(fù)雜度略高，但后續(xù)仿真實(shí)驗(yàn)結(jié)果表明，SA-K2GA 的性能要優(yōu)于前者。

3.4 消息轉(zhuǎn)發(fā)策略

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

由此，本文提出基于多時(shí)間段優(yōu)化BN 的VDTN 路由算法，其消息轉(zhuǎn)發(fā)策略如下。

設(shè)攜帶消息的當(dāng)前車輛節(jié)點(diǎn)與另一車輛節(jié)點(diǎn)相遇，則當(dāng)且僅當(dāng)滿足以下2 種情況時(shí)，當(dāng)前車輛節(jié)點(diǎn)才會(huì)把消息轉(zhuǎn)發(fā)給相遇車輛節(jié)點(diǎn)。

1) 相遇節(jié)點(diǎn)為消息的目的節(jié)點(diǎn)時(shí)，消息將被直接投遞到目的節(jié)點(diǎn)。

2) 當(dāng)相遇節(jié)點(diǎn)非消息的目的節(jié)點(diǎn)時(shí)，兩車將根據(jù)所處的時(shí)刻，選擇相應(yīng)時(shí)間段的BN 模型，并利用式(6)推理得到各自的投遞等級(jí)X10。若當(dāng)前節(jié)點(diǎn)的X10低于相遇節(jié)點(diǎn)的X10，則將消息轉(zhuǎn)發(fā)給相遇節(jié)點(diǎn)；否則當(dāng)前節(jié)點(diǎn)不進(jìn)行消息轉(zhuǎn)發(fā)，繼續(xù)攜帶消息移動(dòng)，直到遇見目的節(jié)點(diǎn)或投遞等級(jí)更高的相遇節(jié)點(diǎn)。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 移動(dòng)軌跡與仿真參數(shù)

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

本文中的多時(shí)間段優(yōu)化BN 結(jié)構(gòu)學(xué)習(xí)算法以及團(tuán)樹構(gòu)造算法是使用MATLAB[30]軟件來實(shí)現(xiàn)的，同時(shí)該算法調(diào)用了BN 工具箱獲取BN 的CH 評分值。當(dāng)離線完成BN 學(xué)習(xí)以及團(tuán)樹構(gòu)造后，使用DTN仿真軟件THE ONE（the opportunistic network environment simulator）[31]對本文提出的路由算法進(jìn)行仿真實(shí)驗(yàn)。仿真參數(shù)如表1 所示。

表1 仿真參數(shù)

4.2 生成訓(xùn)練數(shù)據(jù)集

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

4.3 性能指標(biāo)

為了評價(jià)VDTN 路由算法的有效性，通常采用以下3 個(gè)指標(biāo)來衡量路由協(xié)議性能的好壞。

投遞率：成功投遞到目的節(jié)點(diǎn)的消息數(shù)目與源節(jié)點(diǎn)產(chǎn)生的消息個(gè)數(shù)之比。

投遞時(shí)延：成功投遞到目的節(jié)點(diǎn)的消息所經(jīng)過的平均時(shí)間。

開銷：在消息成功投遞到目的節(jié)點(diǎn)時(shí)，網(wǎng)絡(luò)中所產(chǎn)生的平均消息副本個(gè)數(shù)。

在實(shí)驗(yàn)中，本文主要采用消息報(bào)文的生存時(shí)間（TTL,time to live）作為變量對上述性能指標(biāo)進(jìn)行評價(jià)，這是路由協(xié)議中的重要參數(shù)之一。

4.4 參數(shù)σ 取值分析

本節(jié)主要探討參數(shù)σ對多時(shí)間段貝葉斯網(wǎng)絡(luò)性能的影響。通過改變參數(shù)σ的取值，利用SA-K2GA 算法學(xué)習(xí)不同的BN 結(jié)構(gòu)。根據(jù)學(xué)習(xí)獲得的BN 結(jié)構(gòu)設(shè)計(jì)VDTN 路由算法，并對其性能進(jìn)行對比實(shí)驗(yàn)，如圖3 所示。

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

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

4.5 BN 多時(shí)間段優(yōu)化劃分算法的比較

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

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

Avg 算法：將整個(gè)時(shí)間范圍等分為σ個(gè)階段，再利用K2GA 算法學(xué)習(xí)得到σ階段BN 結(jié)構(gòu)。

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

圖4 采用不同BN 多時(shí)間段優(yōu)化劃分算法的路由性能比較

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

4.6 與經(jīng)典路由算法的比較

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

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

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

圖6 給出了各種路由算法在不同VDTN 節(jié)點(diǎn)緩存大小條件下的性能仿真結(jié)果。如圖6(a)所示，隨著節(jié)點(diǎn)緩存的不斷增加，消息的投遞率也在不斷上升。當(dāng)節(jié)點(diǎn)緩存為17 MB 時(shí)，SA-K2GA 的投遞率比Prophet 高近7%，比NB 高4%。如圖6(b)所示，SA-K2GA 的投遞時(shí)延明顯低于Prophet 和NB，因?yàn)槠涓倪M(jìn)的獎(jiǎng)勵(lì)值機(jī)制將消息的投遞時(shí)延也考慮在內(nèi)。如圖6(c)所示，隨著節(jié)點(diǎn)緩存的不斷增加，SA-K2GA 的網(wǎng)絡(luò)開銷不斷下降，而且相比Epidemic、Prophet 和NB，SA-K2GA 具有最低的路由開銷。

圖6 各種路由算法在不同節(jié)點(diǎn)緩存大小條件下的性能比較

5 結(jié)束語

本文研究VDTN 的消息轉(zhuǎn)發(fā)問題，根據(jù)車輛節(jié)點(diǎn)移動(dòng)模式的時(shí)段性以及節(jié)點(diǎn)屬性之間的依賴關(guān)系，提出并建立了改進(jìn)的多時(shí)間段BN 模型。為解決多時(shí)間段優(yōu)化劃分和BN 結(jié)構(gòu)學(xué)習(xí)問題，提出了BS-K2GA 和SA-K2GA 這2 種算法。在此基礎(chǔ)上，提出了基于多時(shí)間段優(yōu)化BN 的VDTN 路由算法。仿真實(shí)驗(yàn)結(jié)果驗(yàn)證了多時(shí)間段BN 模型及其優(yōu)化算法的可行性和有效性。同時(shí)，本文提出的VDTN路由算法也具有高投遞率、低時(shí)延和低開銷的性能表現(xiàn)。

在未來的工作中，筆者將繼續(xù)優(yōu)化模型，如對車輛屬性的選擇及其離散化標(biāo)準(zhǔn)進(jìn)行優(yōu)化，進(jìn)一步提高算法效率；同時(shí)，研究VDTN 的時(shí)變特征，建立基于時(shí)序概率的動(dòng)態(tài)BN 模型等。