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

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

（1. 華東理工大學(xué)計(jì)算機(jī)科學(xué)與工程系，上海 200237；2. 上海市計(jì)算機(jī)軟件評(píng)測重點(diǎn)實(shí)驗(yàn)室，上海 201112）

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

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

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

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

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

1 基于ACO 的延時(shí)感知路由算法

1.1 概述

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

1.2 橋節(jié)點(diǎn)的選擇

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

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

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

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

1.3 基于延時(shí)感知的路段權(quán)重計(jì)算

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

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

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

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

1.3.2 PAnt的設(shè)計(jì) PAnt的設(shè)計(jì)如圖3 所示?？梢钥闯?，PAnt由以下幾部分組成：

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 路由建立

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

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

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

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

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

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

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

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

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

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

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

2 仿真實(shí)驗(yàn)和討論

2.1 實(shí)驗(yàn)環(huán)境

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

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

2.2 對(duì)比算法

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

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

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

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

圖5 示出了數(shù)據(jù)分組投遞率與車輛節(jié)點(diǎn)數(shù)目的關(guān)系?？梢钥闯觯琕ANET 網(wǎng)絡(luò)中的節(jié)點(diǎn)密度直接影響了網(wǎng)絡(luò)的性能，且車輛節(jié)點(diǎn)密度越高，各算法的分組投遞率也越高。這是因?yàn)楫?dāng)節(jié)點(diǎn)數(shù)量過少時(shí)，網(wǎng)絡(luò)的分離狀況導(dǎo)致大量的數(shù)據(jù)分組不能被交付，導(dǎo)致數(shù)據(jù)分組投遞率較低。

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

圖6 示出了數(shù)據(jù)分組投遞率與車輛移動(dòng)速度的關(guān)系。實(shí)驗(yàn)結(jié)果顯示，隨著車輛移動(dòng)速度的增加，數(shù)據(jù)分組投遞率呈下降趨勢。這是因?yàn)檐囕d網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)受到節(jié)點(diǎn)移動(dòng)性的影響，車速越快，網(wǎng)絡(luò)拓?fù)渥兓筋l繁，導(dǎo)致連接鏈路的頻繁斷開，造成分組數(shù)據(jù)丟包率的增加。

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

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

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

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

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

圖8 示出了平均端到端延時(shí)與車輛移動(dòng)速度的關(guān)系。實(shí)驗(yàn)結(jié)果顯示，隨著車輛速度的增加，所有算法的端到端延時(shí)呈上升趨勢。這是因?yàn)檐囕v節(jié)點(diǎn)移動(dòng)性越強(qiáng)，車載網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化越劇烈，網(wǎng)絡(luò)連通性和穩(wěn)定性下降，導(dǎo)致了傳輸延時(shí)的增加。

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

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

3 結(jié)束語

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

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