基于蟻群算法的延時感知VANET 路由協(xié)議

吉 祥， 虞慧群， 范貴生， 孫懷英

（1. 華東理工大學計算機科學與工程系，上海 200237；2. 上海市計算機軟件評測重點實驗室，上海 201112）

車載自組網(wǎng)絡（VANET）作為智能交通系統(tǒng)中的關鍵技術[1]，近年來已經(jīng)成為車聯(lián)網(wǎng)領域的研究熱點。VANET 技術通過全球定位系統(tǒng)（GPS）、傳感設備等實現(xiàn)車輛狀況以及周邊交通路況信息的采集；使用車載單元（On Board Unit, OBU）設備實現(xiàn)車輛與外界的信息交互；通過路邊單元（Roadside Unit, RSU）或基站等道路基礎設施實現(xiàn)車與外部網(wǎng)絡的連接，從而提供車載導航、實時預警等綜合服務。

VANET 具有自組織、高傳輸速率、易擴展性等優(yōu)點，然而，車輛節(jié)點的高速移動會造成通信鏈路的不穩(wěn)定，這給VANET 路由協(xié)議的設計帶來了極大的挑戰(zhàn)。如何為高度動態(tài)的VANET 系統(tǒng)設計高效、可靠的傳輸技術，成為一項緊迫而又具有挑戰(zhàn)性的課題。

已經(jīng)有一些研究將蟻群算法運用到VANET 中[2-4]，試圖通過蟻群在源節(jié)點與目標節(jié)點間建立完整的路由路徑。Correia 等[5]提出了一種基于移動感知與蟻群優(yōu)化的MAR-DYMO 路由協(xié)議，利用車輛位置及速度信息預測其運動軌跡，并尋找生命周期最長的路徑，但MAR-DYMO 性能會隨著車輛數(shù)量的增加明顯下降，具有可擴展性方面的問題。Rana 等[6]提出了一種基于ACO 的移動性感知區(qū)域路由協(xié)議，將網(wǎng)絡劃分為多個區(qū)域，跨區(qū)域路由采用主動式路由方式，而區(qū)域內采用按需路由。Li 等[7-8]運用蟻群算法來評估各路段的數(shù)據(jù)包轉發(fā)延遲、帶寬和投遞率，提出了VACO 主動式路由算法。假設在每個路口處有一個RSU 來尋找并保存路由信息，但RSU 的代價非常昂貴，尤其是在VANET 部署初期。

由于蟻群算法具有良好的適應性、自組織性、魯棒性以及容錯能力等特點，非常適用于解決VANET中的路由問題，但同時也存在擴展性差、部署成本高等問題。

本文提出了一種基于蟻群算法的延時感知路由算法（ACDAP），將節(jié)點間的路由問題轉化為交叉路口間的路由問題，可以提高路由路徑的復用，減少路由發(fā)現(xiàn)開銷。ACDAP 通過蟻群算法策略來探測各路段的網(wǎng)絡延時和連通性情況，并在交叉路口設置橋節(jié)點解析螞蟻探測包數(shù)據(jù)，計算區(qū)域性路由信息，即路段權重信息；橋節(jié)點通過獲取的路段權重表信息可以直接或間接地構建源節(jié)點與目標節(jié)點間的路由路徑。仿真實驗結果表明，ACDAP 的性能優(yōu)于傳統(tǒng)的GPSR[9]以及GSR[10]算法，且優(yōu)于同樣采用蟻群策略的VACO 算法。

1 基于ACO 的延時感知路由算法

1.1 概述

城市場景中VANET 的路由路徑遵循城市道路網(wǎng)絡拓撲，并且只會在十字路口改變方向，本文將VANET 路由過程分為直路模式與路口模式。在直路模式下，數(shù)據(jù)傳輸采用貪婪轉發(fā)的方式；而對于路口模式，通過在十字路口選擇特殊節(jié)點充當橋節(jié)點的方式連接各分段道路網(wǎng)絡，并利用橋節(jié)點進行路由決策。

1.2 橋節(jié)點的選擇

首先，十字路口區(qū)域內的所有車輛都是候選節(jié)點，選取那些在路口處逗留時間盡可能長的車輛作為橋節(jié)點[11]。因此當有候選車輛因紅燈而在路口區(qū)域停留時，優(yōu)先選擇這些由于紅燈而等候在路口的節(jié)點，且紅燈的剩余等候時間越長優(yōu)先級越高；如果剩余等候時間最長的車輛只有一輛，那么直接選擇該車輛擔任橋節(jié)點；如果有多輛車輛符合橋節(jié)點競爭條件時，為了簡單起見，隨機選擇其中一輛車作為橋節(jié)點。如果沒有車輛在路口區(qū)域停留，考慮到經(jīng)過十字路口中心的車輛正駛離路口，應當優(yōu)先選擇那些行駛方向朝路口區(qū)域中心且速度較低的節(jié)點。

圖 1 橋節(jié)點選擇機制Fig. 1 Bridge node selection at intersections

圖1 通過具體示例展示了橋節(jié)點選擇過程。圖中的圈代表了路口區(qū)域的限定范圍，橋節(jié)點候選車輛集合為ζ={V0,V1,V2,V3,V4,V5}，其中V0因紅燈而停留等候，其余車輛均處于行駛狀態(tài)。顯然，在這種情況下，V0將被選為橋節(jié)點。假設V0節(jié)點不存在，那么候選車輛集合為ζ={V1,V2,V3,V4,V5}?？梢钥闯?，V2、V3、V4正向中心靠近，而V1和V5正駛離路口區(qū)域，因而{V1,V5}被排除出候選行列，此時最終的候選車輛集合為ζ={V2,V3,V4}，選擇其中速度最慢的車輛作為橋節(jié)點。

當橋節(jié)點即將駛出路口區(qū)域時，將觸發(fā)新的橋節(jié)點選擇過程，并且舊的橋節(jié)點會將橋節(jié)點角色所有的相關信息交付給新的橋節(jié)點，這樣可以保證車載網(wǎng)絡在交叉路口場景中的持續(xù)連通。

1.3 基于延時感知的路段權重計算

1.3.1 螞蟻探測包PAnt位于十字路口處的橋節(jié)點持續(xù)間斷性產生輕量級控制包（稱為螞蟻探測包，PAnt）用于探測路段連通性情況，并將PAnt發(fā)送至相鄰路段中，PAnt產生的時間間隔記作TAnt。PAnt在直路階段通過單播方式向前轉發(fā)，直至抵達下一個交叉路口的橋節(jié)點。

圖2 示出了螞蟻探測包轉發(fā)過程。在交叉路口I1處，V1被選中為橋節(jié)點，其產生一個新的PAnt并發(fā)送至下一個路口，例如I2；在選擇中繼節(jié)點時，采用貪婪轉發(fā)策略，V1選擇鄰居范圍內離I2最近的節(jié)點V3作為下一跳的轉發(fā)節(jié)點；當PAnt被路口I2處的橋節(jié)點V2接收時，I2將被記錄到PAnt中，然后V2從{S23,S24,S25}路段（Sij表示路口Ii與Ij之間的路段）中選擇一個路徑繼續(xù)轉發(fā)PAnt，且信息素高的路段被選中的概率更高。對于一般情況，假設Ii有K 個相鄰交叉路口，分別記為 I1, I2,…, IK，當PAnt到達Ii處時，根據(jù)式（1）選擇概率pij最高的路段作為PAnt的下一個方向路徑。

圖 2 螞蟻探測包轉發(fā)過程Fig. 2 Forwarding process of ant packets

其中：ψij表示路段Sij的信息素值；f 表示PAnt剛經(jīng)過的路口ID；pR(Sij)表示選擇路段Sij的隨機概率，pR∈(0,1)。

1.3.2 PAnt的設計 PAnt的設計如圖3 所示?？梢钥闯觯琍Ant由以下幾部分組成：

（1）Type：說明包的類型。

（2）Packet_ID：包的標識信息，由產生PAnt的路口ID 以及產生的序列編碼組成，中間通過“_”連接，如{Intersection_ID}_{Serial_Number}形式。

（3）Target_Intersection：PAnt將要發(fā)送至的交叉路口，包括路口的標識ID 以及位置（Position）信息。

（4）Intersection_Sequence：PAnt經(jīng)過并記錄的交叉路口序列，包括了路口的ID、Position 以及PAnt到達該路口時的時間戳（Timestamp），根據(jù)該時間戳可以計算出PAnt經(jīng)過路段的延時情況。

（5）Intersection_Count：初始值為0，PAnt每經(jīng)過一次交叉路口時值加1；超過一定閾值時，PAnt被丟棄，相當于lifetime 功能。

1.3.3 路段權重計算 螞蟻每經(jīng)過一個路段會沉積信息素（Pheromone）[12]，因此當橋節(jié)點接收到PAnt時，橋節(jié)點會計算相應路段的信息素。如果PAnt中的Intersection_Sequence 顯示其經(jīng)過了相鄰的交叉路口Ii與Ij，則說明這兩個路口間道路是連通的，則相應的信息素會被更新：

其中：ψij(t)與ψij(t+1)分別表示更新前與更新后路段Sij的信息素；Δψij表示螞蟻更新信息素，表示如下：

其中：dij表示PAnt從Ii傳輸至Ij所需延時； dMij表示橋節(jié)點所記錄的該路段螞蟻探測包的最低延時；ω 表示一個常量?？梢钥闯觯敠?設置為 ω∈(0,0.5)時，Δψij始終小于1，且dij越小，Δψij越大。

螞蟻所留下的信息素會隨著時間揮發(fā)，揮發(fā)過程定義如下：

其中：Teva表示信息素揮發(fā)過程的時間間隔；ηph表示信息素揮發(fā)因子，ηph∈(0,1)；τmin表示信息素的最低閾值。

結合式（2）、式（3）、式（4）可以看出，只要初始信息素值ψij(0)∈(0,1)，無論信息素如何更新，始終有ψij∈(0,1)；且ψij越大，代表路段Sij上網(wǎng)絡連通性越好。

路段信息素更新之后，橋節(jié)點將更新相應路段的權重值。對于路段Sij，路段長度表示為Lij，則路段權重定義為如下形式：

ωij越小代表路段傳輸延時越小，連通性越好。

1.4 路由建立

橋節(jié)點通過對PAnt包攜帶信息的分析以及路段權重的計算，可以獲取周圍一片區(qū)域內道路的連通性情況，為路由轉發(fā)提供全局性的視野，避免因貪婪轉發(fā)而容易陷入局部最優(yōu)的問題。圖4 示出了一片區(qū)域的地圖示例及相對應的道路權重矩陣。

在ACDAP 路由協(xié)議中，通過將車輛間路由的問題轉換為終端交叉路口間路由的問題，以減少路由的重復探索，簡化路由過程。當源節(jié)點Vsrc需要發(fā)送數(shù)據(jù)包時，其首先產生一個格式為＜Vsrc, Vdest, msg,Options＞的數(shù)據(jù)包Data_Packet，其中，Vdest表示數(shù)據(jù)包的目標車輛，msg 代表了具體的消息，Options 用于保存附加的路由信息。Vsrc與 Vdest之間數(shù)據(jù)傳輸?shù)膯栴}可以轉變?yōu)樵谂cVsrc、 Vdest分別相鄰的交叉路口Isrc、Idest間尋找合適的路由路徑的問題。

圖 3 PAnt 格式Fig. 3 Frame format of PAnt

圖 4 區(qū)域地圖示例及相應的權重矩陣Fig. 4 Map of a city area as an example and the corresponding adjacency matrix

為了方便表述，將Vsrc與Vdest統(tǒng)稱為終端車輛，Isrc與Idest統(tǒng)稱為終端路口。由于終端車輛有兩個相鄰的交叉路口，需要對其進行選擇。這里主要通過考慮終端車輛與路口之間的距離以及車輛行駛方向選擇合適的相鄰路口作為終端路口，具體的參數(shù)設計如下：

其中：Si表示相鄰交叉路口的選擇權重，值比較高的一方被選為終端路口；dti表示終端車輛與相鄰路口間的距離；Lt表示所在路段的總長度； χ 表示參數(shù)系數(shù)，本文設置為0.5；λdir(Vt)表示終端車輛的移動方向。

路由算法的具體步驟如下：

Step 1 源節(jié)點Vsrc首先將Data_Packet 發(fā)送至Isrc處的橋節(jié)點；

Step 2 橋節(jié)點解析路由包查看Idest是否包含在其權重矩陣中，如果是，則跳到Step 3；否則，橋節(jié)點找出權重矩陣中離Idest最近的交叉路口作為臨時目標終端Itd；

Step 3 橋節(jié)點通過Dijkstra 算法計算Isrc與 Idest（或Itd）之間的最短路徑，并將獲得的路口序列存放至Data_Packet 包頭之中，然后沿著所選路徑轉發(fā)Data_Packet，轉發(fā)過程采用貪婪轉發(fā)策略。

Step 4 如果Data_Packet 到達Itd，則重復Step 2～Step 4；否則，Data_Packet 到達Idest后，由Idest處的橋節(jié)點判斷Vdest所在的路段，并將Data_Packet 沿著該路段轉發(fā)至Vdest。

2 仿真實驗和討論

2.1 實驗環(huán)境

本文采用NS2（Network Simulation-2）進行仿真實驗。首先利用OpenStreetMap 地圖獲取真實的城市道路場景，并通過SUMO 生成道路網(wǎng)格文件和車輛節(jié)點運動軌跡作為NS2 的輸入文件。每組仿真實驗時長600 s，其中前100 s 讓生成的車輛節(jié)點在地圖環(huán)境中隨機運動，其后的500 s 再統(tǒng)計相關的性能指標數(shù)據(jù)。通過改變參數(shù)中的車輛密度以及最大車速來獲得不同的仿真場景，以考察不同因素對路由性能的影響。每組仿真實驗獨立重復20 次，并取其所得結果的平均值作為最終的實驗結果。仿真參數(shù)的具體設置如表1 所示。

表 1 仿真參數(shù)Table 1 Simulation parameters

2.2 對比算法

為了評估ACDAP 算法的性能，實驗中使用GPSR、GSR、VACO 算法作為對比方法。其中GPSR是一種基于貪婪轉發(fā)的路由策略；GSR 是一種經(jīng)典的基于地圖的路由算法；VACO 是一種基于蟻群算法的路由算法，它利用ACO 算法來衡量道路的網(wǎng)絡狀態(tài)，包括延時、帶寬以及分組投遞率，并借助RSU保存路由信息并進行主動式路由發(fā)現(xiàn)。這3 種方法及本文算法都采用貪婪轉發(fā)策略，但構建路由路徑的策略不同，因此選擇上述3 種算法作為對比算法具有可比性。

2.3 實驗結果與分析

為了評估ACDAP 算法的性能，從兩個方面對算法進行評估，分別為數(shù)據(jù)分組投遞率（Packet Delivery Ratio, PDR）和平均端到端延時（Average End-to-End Delay, E2ED）。

2.3.1 數(shù)據(jù)分組投遞率 數(shù)據(jù)分組投遞率是指被目標節(jié)點成功接收的數(shù)據(jù)分組數(shù)量與源節(jié)點所發(fā)出的數(shù)據(jù)分組數(shù)量的比值。

圖5 示出了數(shù)據(jù)分組投遞率與車輛節(jié)點數(shù)目的關系。可以看出，VANET 網(wǎng)絡中的節(jié)點密度直接影響了網(wǎng)絡的性能，且車輛節(jié)點密度越高，各算法的分組投遞率也越高。這是因為當節(jié)點數(shù)量過少時，網(wǎng)絡的分離狀況導致大量的數(shù)據(jù)分組不能被交付，導致數(shù)據(jù)分組投遞率較低。

圖 5 不同車輛節(jié)點密度下的分組投遞率Fig. 5 Packet delivery rates for varying number of vehicles

圖6 示出了數(shù)據(jù)分組投遞率與車輛移動速度的關系。實驗結果顯示，隨著車輛移動速度的增加，數(shù)據(jù)分組投遞率呈下降趨勢。這是因為車載網(wǎng)絡的拓撲結構受到節(jié)點移動性的影響，車速越快，網(wǎng)絡拓撲變化越頻繁，導致連接鏈路的頻繁斷開，造成分組數(shù)據(jù)丟包率的增加。

圖 6 不同車速下的分組投遞率Fig. 6 Packet delivery rates for vary vehicular velocity

在4 種算法中，GPSR 的分組投遞率始終最低。這是因為GPSR 采用貪婪策略，選擇離當前節(jié)點較遠的節(jié)點作為中繼節(jié)點，而距離越遠，信號衰弱越嚴重，鏈路質量也越差，因而丟包的情況也越嚴重。同樣采用貪婪轉發(fā)策略，GSR 利用地圖計算得到了源節(jié)點與目標節(jié)點間的最短路徑，但GSR 在計算最短路徑時，只考慮了距離因素，而沒有考慮網(wǎng)絡的實際情況，因此其網(wǎng)絡性能改進并不顯著。VACO 利用蟻群算法獲得了網(wǎng)絡質量的診斷信息，從而獲得了更為合理的路由轉發(fā)路徑，相比GPSR 算法有了明顯的性能提升。然而，VACO 采用的是主動式的路由發(fā)現(xiàn)過程。由于VANET 中節(jié)點的快速移動以及網(wǎng)絡拓撲的頻繁變化，主動式路由方式往往具有一定的遲滯性。同樣利用蟻群算法進行路段網(wǎng)絡性能的診斷，ACDAP 主要考慮網(wǎng)絡傳輸延時，延時越小意味著網(wǎng)絡的連通性越好。實驗結果表明，ACDAP 的數(shù)據(jù)分組投遞率始終高于其他3 種算法。盡管都是采用貪婪轉發(fā)，但不同的路由路徑選擇機制決定了各算法獲得了不同的性能結果。ACDAP 通過蟻群探測包采集各路段的連通性信息，獲得了所在區(qū)域的路段權重情況，選擇了連通性高的路段構成了路由路徑，避免了傳統(tǒng)貪婪策略所面臨的局部最優(yōu)問題。

2.3.2 平均端到端延時 平均端到端延時是指網(wǎng)絡中所有分組數(shù)據(jù)從源節(jié)點發(fā)出到被目標節(jié)點接收所需的平均時間間隔。

圖7 示出了平均端到端延時與車輛節(jié)點數(shù)目的關系。從實驗結果可以看出，隨著節(jié)點密度的增加，節(jié)點在轉發(fā)數(shù)據(jù)包時有更多的鄰居節(jié)點作為候選，且遇到路由空洞的概率降低，因此所有算法的端到端延時都隨著節(jié)點密度的增加而呈現(xiàn)下降趨勢。尤其當網(wǎng)絡中的節(jié)點數(shù)目小于900 時，可以看到GPSR與GSR 隨著節(jié)點數(shù)目增多，端到端延時大幅下降，VACO 與ACDAP 算法的延時也有明顯下降。這是因為網(wǎng)絡空洞對路由延時的影響很大，當路由轉發(fā)遇到網(wǎng)絡空洞時往往需要采用存儲-攜帶-轉發(fā)的方式進行轉發(fā)，而車輛攜帶行駛的速度顯然無法和無線信號的傳輸速率相提并論。當節(jié)點密度較稀疏時，網(wǎng)絡空洞數(shù)量較多，造成了傳輸延時較大。對于VACO 與ACDAP 算法，由于在選擇轉發(fā)路徑時考慮了網(wǎng)絡中各路段的實際網(wǎng)絡性能，在轉發(fā)過程中遭遇網(wǎng)絡空洞陷入局部最優(yōu)的概率大大降低，因此即使在稀疏場景下也具備一定的穩(wěn)定性。

圖 7 不同車輛節(jié)點密度下的平均端到端延時Fig. 7 Average end-to-end delay for varying number of vehicles

圖8 示出了平均端到端延時與車輛移動速度的關系。實驗結果顯示，隨著車輛速度的增加，所有算法的端到端延時呈上升趨勢。這是因為車輛節(jié)點移動性越強，車載網(wǎng)絡的拓撲結構變化越劇烈，網(wǎng)絡連通性和穩(wěn)定性下降，導致了傳輸延時的增加。

圖 8 不同車輛速度下的平均端到端延時Fig. 8 Average end-to-end delay for varying vehicular velocity

可以看出，GPSR 算法的端到端延時在4 種算法中最高，GSR 比GPSR 的延時略有降低，ACDAP 的延時最低。GSR 算法在GPSR 基礎上利用地圖信息獲取最短路由路徑，但只是考慮了靜態(tài)道路長度信息而沒有考慮實際的網(wǎng)絡狀況，因此性能的提升并不明顯。VACO 與ACDAP 都利用了蟻群算法獲取道路中實際的網(wǎng)絡性能，但VACO 采用主動式路由發(fā)現(xiàn)，而主動式路由發(fā)現(xiàn)過程需要消耗一定的時間，且VANET 中節(jié)點移動性較高，網(wǎng)絡環(huán)境隨時會改變；而ACDAP 利用橋節(jié)點保存區(qū)域路段權重信息，當有路由請求時，可以根據(jù)權重表通過最短路徑算法直接選擇出到目標節(jié)點或與目標節(jié)點較近的路口之間的最優(yōu)化路徑，因而ACDAP 獲得了更低的網(wǎng)絡延時。

3 結束語

本文提出了一種基于蟻群算法的延時感知路由策略。首先利用蟻群算法中信息素的更新機制以及蟻群對最優(yōu)化路徑的探索過程，提出了一種基于延時感知的分段網(wǎng)絡權重分析方法，并建立面向局部區(qū)域的路段權重矩陣，然后根據(jù)該權重矩陣，提出了一種區(qū)域路由算法，有效解決了現(xiàn)有路由算法容易陷入局部最優(yōu)的問題。實驗結果表明ACDAP 能夠保障VANET 數(shù)據(jù)傳輸?shù)目煽啃?，并提高傳輸效率?/p>

本文利用蟻群算法探索路段網(wǎng)絡的連通性情況，并構建了優(yōu)化路由轉發(fā)路徑，保障了VANET 中數(shù)據(jù)傳輸?shù)目煽啃院托省Ｈ欢?，ACDAP 在路由路徑上的轉發(fā)依然采用的是貪婪轉發(fā)策略，該策略雖然可以通過減少轉發(fā)跳數(shù)而降低傳輸延時，但同時也增加了數(shù)據(jù)包丟失的風險。未來將完善ACDAP算法中的轉發(fā)策略，在選擇中繼節(jié)點時考慮鏈路的穩(wěn)定性等因素，提高數(shù)據(jù)的分組投遞率。