一種基于鏈路質(zhì)量的蟻群優(yōu)化VANET路由算法

張家波，袁 凱，吳昌玉

(重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065)

0 引 言

車載自組織網(wǎng)絡(luò)(vehicular ad hoc network, VANET)是智能交通系統(tǒng)(intelligent transportation system, TIS)不可缺少的重要組成部分，越來越受到學(xué)術(shù)界和工業(yè)界的關(guān)注[1-3]。VANET中由于無線接入技術(shù)的支持不需要固定的基礎(chǔ)設(shè)施就能實(shí)現(xiàn)車到車和車到基礎(chǔ)設(shè)施的通信[4-5]。

復(fù)雜的交通環(huán)境對VANET的通信性能提出了更高的要求，而通信性能好壞一定程度上取決于路由協(xié)議的優(yōu)劣[6]。文獻(xiàn)[7]提出一種基于學(xué)習(xí)方法的決策樹理論的多副本VANET機(jī)會路由協(xié)議，在場景比較密集的情況下投遞率和延時(shí)有良好的表現(xiàn)?；诘貓D的路由協(xié)議，對于頻繁拓?fù)渥兓哂徐`活性，但開銷較大[8-9]。文獻(xiàn)[10]提出的路由協(xié)議可以快速應(yīng)對拓?fù)涞淖兓?，但其不能得到最佳路徑，?dǎo)致延時(shí)增加，數(shù)據(jù)包傳輸率下降。結(jié)合蟻群優(yōu)化算法的路由協(xié)議能較好適應(yīng)復(fù)雜多變的交通環(huán)境，找到最優(yōu)路徑[11-13]。文獻(xiàn)[11]是一種基于網(wǎng)絡(luò)連通性與蟻群算法相結(jié)合的高效路由協(xié)議，通過蟻群算法尋找源節(jié)點(diǎn)到目的節(jié)點(diǎn)最佳網(wǎng)絡(luò)連通性的路由，保證了信息傳輸?shù)木W(wǎng)絡(luò)穩(wěn)定性。文獻(xiàn)[12]提出一種延遲敏感的蟻群優(yōu)化車載路由協(xié)議，該算法在信息傳輸時(shí)延方面有較好的性能，并且能夠很好地適應(yīng)拓?fù)渥兓痆12]。以上2種路由協(xié)議雖然相比傳統(tǒng)的蟻群算法性能優(yōu)良，但其僅僅考慮了影響路由效果的單一影響因素。未考慮網(wǎng)絡(luò)連通概率、傳輸時(shí)延與分組投遞率等因素對路由協(xié)議的綜合影響，會導(dǎo)致傳輸鏈路的不穩(wěn)定，以及信息傳輸?shù)牟粶?zhǔn)確，無法保證信息可靠有效的傳輸。

基于上文的簡要分析，源節(jié)點(diǎn)到目的節(jié)點(diǎn)若要找到通信效果最優(yōu)的路徑，必須考慮整體的鏈路質(zhì)量。本文提出了一種基于鏈路質(zhì)量的蟻群VANET路由算法(ant colony optimization routing algorithm based on link quality for vanet, LACOR)尋找最優(yōu)路徑。通過建立鏈路質(zhì)量模型并進(jìn)行分析，得出道路環(huán)境對鏈路相關(guān)因素的影響，再結(jié)合改進(jìn)的蟻群算法路徑選擇公式，對所選擇的道路進(jìn)行優(yōu)化，最后得到最優(yōu)路徑。圖1為城市路網(wǎng)模型。

1 鏈路質(zhì)量研究

在本節(jié)中，我們假設(shè)車流比較稀疏，每輛車都裝配有全球定位系統(tǒng)(global positioning system, GPS)、電子地圖等設(shè)備，車輛均為活躍節(jié)點(diǎn)參與信息的轉(zhuǎn)發(fā)。通過分析道路的連通概率、傳輸時(shí)延、分組投遞率，建立鏈路質(zhì)量模型，進(jìn)行評估與分析。鏈路質(zhì)量函數(shù)為

L(y)=λ1CP(y)+λ2Delay(y)+λ3PDR(y)

(1)

(1)式中：CP(y)為路由y的網(wǎng)絡(luò)連通概率；Delay(y)為路由y的數(shù)據(jù)傳輸時(shí)延比率；PDR(y)為路由y的分組投遞率。其中，Delay(y)=(Dth-D(y))/Dth，Dth為路由延時(shí)的閾值；D(y)為路由y的延時(shí)，且λ1+λ2+λ3=1。由于傳輸性能更多的體現(xiàn)在時(shí)延與分組投遞率，因此，本文設(shè)置λ1=0.2；λ2=0.4；λ3=0.4。同時(shí)考慮無線信道的衰落、通信半徑、路段長度、車輛密度、數(shù)據(jù)包的大小等因素對鏈路的影響。本文先研究單個(gè)路段的鏈路質(zhì)量，進(jìn)而分析出整體路由的鏈路質(zhì)量。

1.1 連通概率研究與分析

根據(jù)本文情況定義路段連通概率：在道路中，2個(gè)車輛節(jié)點(diǎn)處于彼此的通信半徑之內(nèi)，它們之間能夠直接進(jìn)行通信，由于車流密度比較稀疏使得車輛下一跳通信范圍內(nèi)不一定有車輛而造成連通中斷，因此，路段連通概率便是道路中車輛之間連接的概率。

在車輛運(yùn)行的過程中只要車輛在彼此的通信范圍內(nèi)，就能直接進(jìn)行通信。由于車輛快速運(yùn)動使其拓?fù)渥兓l繁，很難得到確切的連通概率，根據(jù)參考文獻(xiàn)[14]將長度為L的道路劃分為多個(gè)單元格進(jìn)行分析。假定單元格的大小為車輛的通信半徑，即cs=R，則單元格的個(gè)數(shù)N=L/cs。

如圖2為雙向車道示意圖。假定信息以車輛的運(yùn)動方向優(yōu)先傳遞，當(dāng)運(yùn)動方向上的傳輸鏈路中斷，可以利用反向車道中的車輛進(jìn)行鏈路修復(fù)，增加連通的概率。N個(gè)單元格對應(yīng)有N-1個(gè)傳輸鏈路。在雙向車道上ke和kw分別表示東、西2個(gè)車道的單元格cs內(nèi)的車輛數(shù)，ρe和ρw分別為對應(yīng)單元格內(nèi)的車輛密度。根據(jù)交通流理論車輛速度服從正態(tài)分布，到達(dá)服從泊松分布[14-15]，則可以得到雙向車道的概率密度函數(shù)為

(2)

本文以向東的運(yùn)動方向?yàn)樾畔⒌膫鬟f方向，西行路段方向進(jìn)行鏈路修復(fù)，Pnr表示西行修復(fù)鏈路車道所在的單元格內(nèi)沒有車輛而造成的不可修復(fù)概率，計(jì)算公式為

Pnr=f(kw=0)=e-ρwcs

(3)

根據(jù)(3)式可以求得鏈路可修復(fù)的概率為1-Pnr，然而一條道路可能存在多條修復(fù)鏈路。設(shè)變量q為可修復(fù)鏈路的條數(shù)，且q∈{0,1,…,N-1}。由此可得q條可修復(fù)鏈路的概率為

PW|Q(q)=(1-Pnr)q=(1-e-ρwcs)q,N>1

(4)

為了得到路段上的連通概率，還需求得q條斷開鏈路的概率PQ(q)，根據(jù)相關(guān)定義，通信鏈路中斷，意味著相鄰單元格內(nèi)任意2個(gè)車輛之間的距離大于通信半徑R。車輛之間的距離S服從指數(shù)分布，則可求得鏈路斷開的概率為

Pb{S>R}=e-ρwR

(5)

對于有N-1條傳輸鏈路來說，鏈路是否斷開的情況滿足二項(xiàng)分布，得到q條斷開鏈路的概率為

(6)

因此，根據(jù)全概率公式得到雙車道的連通概率為

(7)

1.2 傳輸延時(shí)研究與分析

根據(jù)本文的情況，我們定義路段傳輸時(shí)延：指信息從進(jìn)入路段經(jīng)過車輛“攜帶—轉(zhuǎn)發(fā)”的方式離開當(dāng)前路段所花費(fèi)的時(shí)間。

道路中數(shù)據(jù)的傳輸方式分為2種：①逐跳轉(zhuǎn)發(fā)，所需的時(shí)間與跳數(shù)及單跳時(shí)延相關(guān)；②攜帶-轉(zhuǎn)發(fā)，當(dāng)車輛下一跳范圍內(nèi)沒有可以進(jìn)行傳遞信息的車輛，則需要先攜帶信息，直到遇見可以進(jìn)行轉(zhuǎn)發(fā)的車輛再進(jìn)行轉(zhuǎn)發(fā)，所需的時(shí)間為逐跳轉(zhuǎn)發(fā)時(shí)間加上攜帶時(shí)間。其中，單跳傳輸時(shí)延tp是車輛在其通信半徑內(nèi)通過單跳向中繼車輛傳輸信息，確認(rèn)接收所需要的時(shí)間，其影響因素有信道競爭、消息碰撞、競爭窗口等[16]。

當(dāng)?shù)缆烽L度遠(yuǎn)大于傳輸單元長度即N?1時(shí)，信息會通過多跳技術(shù)沿著道路進(jìn)行轉(zhuǎn)發(fā)，k表示在雙車道上傳輸單元格cs內(nèi)的車輛數(shù)。由車輛到達(dá)服從泊松分布可以得到，車輛數(shù)k的概率密度函數(shù)為

(8)

現(xiàn)在考慮當(dāng)雙車道的下一跳傳輸單元格內(nèi)沒有車輛，必須先進(jìn)行消息攜帶當(dāng)遇到車輛時(shí)再進(jìn)行轉(zhuǎn)發(fā)的情況。雙向傳輸單元格內(nèi)沒有車輛的情況即k=0時(shí)，得到其概率密度函數(shù)為

ft=f(k=0)=e-(ρw+ρe)cs

(9)

當(dāng)單元格個(gè)數(shù)N≤1時(shí)，傳輸延時(shí)為tp。當(dāng)N>1，一部分是車輛逐跳轉(zhuǎn)發(fā)信息花費(fèi)的時(shí)間，與單跳傳輸時(shí)延和跳數(shù)有關(guān)；另一部分是車輛攜帶信息花費(fèi)的時(shí)間，與攜帶運(yùn)行的長度和相對速度有關(guān)，如(10)式

(10)

1.3 分組投遞率研究與分析

假設(shè)數(shù)據(jù)在無線信道傳輸中采用請求發(fā)送/清除發(fā)送(request to send/clear to send, RTS/CTS)協(xié)議,可以減少由隱藏節(jié)點(diǎn)問題所造成的沖突機(jī)制。但信息在多跳傳輸過程中會存在數(shù)據(jù)丟失或者損壞，這種情況下導(dǎo)致道路的數(shù)據(jù)傳輸性能不可靠，影響鏈路性能。因此，先研究在瑞利衰落信道下，2個(gè)傳輸單元格內(nèi)車輛單跳情況下的誤碼率(bit error rate, BER)為

(11)

(11)式中：Pt是發(fā)射機(jī)功率；Gt和Gr是發(fā)射機(jī)和接收機(jī)的增益；fc是載波頻率；c是光速；s是發(fā)射車輛與接收車輛之間的距離；σf2是瑞利分布的方差；Ptherm是噪聲功率。其中，Ptherm=FkT0Rb，F(xiàn)是噪聲系數(shù)，k是玻爾茲曼常數(shù)，T0是室溫，Rb是數(shù)據(jù)發(fā)送速率。

(11)式是計(jì)算特定單跳長度的BER,實(shí)際中，車輛傳輸信息每一跳的長度是不固定隨機(jī)分布的，連續(xù)2個(gè)車輛之間的距離服從指數(shù)分布，因此，可以得出其概率密度函數(shù)為

(12)

由此，可以得到單跳情況下平均的鏈路BER為

(13)

根據(jù)誤碼率與分組投遞率之間的關(guān)系，可以求得單跳情況下的分組投遞率為

PDR1hop(s)=(1-(1-cr)E[BERs(s)])psize

(14)

(14)式中：psize表示數(shù)據(jù)包的大?。籧r代表錯(cuò)誤校正比率，結(jié)合1.2節(jié)傳輸延時(shí)中的分析得到傳輸?shù)奶鴶?shù)Hop=(N-1)(1-ft)，所以，求得路段上的分組投遞率為

PDRs=PDR1hop(s)Hop

(15)

2 LACOR算法

2.1 蟻群算法

蟻群算法是一種自適應(yīng)算法，適應(yīng)于動態(tài)組合優(yōu)化路由等問題的解決。最早是由Dorigo提出的并用于解決旅行商問題。蟻群初期隨機(jī)地選擇前往目的節(jié)點(diǎn)的路徑，每條路徑上都存在一個(gè)啟發(fā)函數(shù)τij和期望啟發(fā)函數(shù)ηij，α和β分別代表信息啟發(fā)因子、期望啟發(fā)因子。根據(jù)走過路徑上分泌的信息素濃度以及狀態(tài)轉(zhuǎn)移概率尋找路徑，形成一個(gè)正反饋機(jī)制，最后逐漸找到最優(yōu)路徑。當(dāng)螞蟻k到達(dá)當(dāng)前路段時(shí)，選擇下一個(gè)相鄰路段的概率為

(16)

2.2 基于鏈路質(zhì)量的蟻群路由算法

根據(jù)前文所分析的鏈路質(zhì)量，再結(jié)合蟻群算法的應(yīng)用原理，首先將鏈路質(zhì)量擴(kuò)展為2種類型：局部鏈路質(zhì)量LQ和全局鏈路質(zhì)量GQ，如(17)式，并且將局部鏈路質(zhì)量定義為局部信息素，全局鏈路質(zhì)量定義為全局信息素，以便與蟻群算法結(jié)合分析。

(17)

全局信息素路由y上的連通概率、傳輸延時(shí)、分組投遞率分別為

(18)

(18)式中：CP(ei)是路段ei的連通概率；PDR(ei)是路段ei的分組投遞率；Delay(ei)是路段ei的傳輸延時(shí)比率。結(jié)合鏈路質(zhì)量模型引入局部信息素和全局信息素，改進(jìn)后的蟻群狀態(tài)轉(zhuǎn)移概率為

(19)

LQij用于幫助螞蟻獲取最新路段信息，并探索出新的路由避免出現(xiàn)路由空洞和高負(fù)載的鏈路。GQij反映的是整條路由的鏈路質(zhì)量，有助于算法的快速收斂。通過調(diào)節(jié)α和β權(quán)重因子數(shù)值，使其既不影響新路徑的探索又能保持最優(yōu)路徑的選擇。

若前向螞蟻到達(dá)目的節(jié)點(diǎn)并且傳輸時(shí)延滿足路徑的要求，前向螞蟻便會轉(zhuǎn)變?yōu)楹笙蛭浵仯駝t直接丟棄。后向螞蟻便會攜帶由前向螞蟻記錄給出的路由表原路返到目的節(jié)點(diǎn)，此時(shí)便會得到最新的全局信息素(latest global link quality, LGQ),通過(20)式進(jìn)行全局信息素的更新。

GQij←(1-δ)·GQij+δ·LGQij

(20)

(20)式中：δ(0<δ<1)為是信息素?fù)]發(fā)系數(shù)，(1-δ)·GQij為揮發(fā)的全局信息素；δ·LGQij為增加的全局信息素。全局信息素的更新可以避免出現(xiàn)搜索停滯，一旦全部的后向螞蟻回到源節(jié)點(diǎn)，便會選出最大的全局路由鏈路質(zhì)量L(y)，并將此作為本次蟻群迭代的最優(yōu)路徑。

2.3 LACOR路由算法步驟

蟻群算法中數(shù)據(jù)包通過攜帶-轉(zhuǎn)發(fā)策略進(jìn)行傳輸，根據(jù)概率分布函數(shù)和信息素的更新選擇下一個(gè)路段，尋找源節(jié)點(diǎn)與目的節(jié)點(diǎn)之間的可用路徑，經(jīng)過路徑優(yōu)化，得到最優(yōu)路徑的集合。為了應(yīng)對車載自組織網(wǎng)頻繁的拓?fù)渥兓S護(hù)路由，當(dāng)路由集合中的道路信息改變時(shí)，LACOR算法就會重新建立一個(gè)新的路由。主要的算法步驟如下：首先，進(jìn)行信息的初始化，如鏈路信息、蟻群最大迭代次數(shù)、螞蟻總數(shù)、權(quán)重因子等，源節(jié)點(diǎn)向目的節(jié)點(diǎn)發(fā)送路由請求，若存在路由，則源節(jié)點(diǎn)直接發(fā)送信息給目的節(jié)點(diǎn)，否則，進(jìn)行蟻群路徑尋優(yōu)；然后開始蟻群迭代，螞蟻搜索路徑，通過判斷分析，再結(jié)合(19)式進(jìn)行路段的選擇，(20)式進(jìn)行全局鏈路質(zhì)量的更新；最后當(dāng)蟻群迭代完成后，整理迭代結(jié)果，獲取最優(yōu)的路徑集合。LACOR算法的具體步驟如下。

輸入:初始化道路和蟻群算法基本參數(shù)。

1 源車輛節(jié)點(diǎn)向目標(biāo)車輛節(jié)點(diǎn)發(fā)送信息

2 if 存在路由, then

3 發(fā)送信息

4 跳到行20

5 else

6 for k=1: K (迭代次數(shù))

7 for m=1: M (螞蟻數(shù)量)

8 if 前向螞蟻到達(dá)目標(biāo)車輛節(jié)點(diǎn), then

9 前向螞蟻?zhàn)優(yōu)楹笙蛭浵伔祷卦窜囕v節(jié)點(diǎn)，根據(jù)(20)式更新全局鏈路質(zhì)量

10 else

11 根據(jù)(19)式選擇下一條道路，返回行8

12 if m=M, then

13 選擇最優(yōu)的路徑并保存到路由表中

14 else

15 返回行7

16 if k=K, then

17 得到最優(yōu)路由

18 else

19 返回行6

20 結(jié)束

輸出: 傳輸時(shí)延和分組投遞率。

3 仿真分析與對比

本文通過Matlab仿真軟件對路段的鏈路質(zhì)量以及LACOR算法進(jìn)行仿真分析，并與文獻(xiàn)[11]算法，文獻(xiàn)[12]算法進(jìn)行對比。相關(guān)參數(shù)的設(shè)置如表2。

表2 仿真參數(shù)設(shè)置Tab.2 Simulation parameter settings

當(dāng)?shù)缆烽L度L=1 000 m時(shí)，車輛密度與路段連通概率的關(guān)系如圖3。隨著車輛密度從0.01～0.05 vehicle/m增大，雙向車道中存在的中斷鏈路被逐漸修復(fù)，使得整條道路處于較高的連通狀態(tài)，提高了網(wǎng)絡(luò)的連通概率。在車輛密度較小為0.01 vehicle/m的情況下，當(dāng)通信半徑R為250 m要比通信半徑為150 m的路段連通概率高出13%。通信半徑越大、單元格越大，包含的車輛就越多，2個(gè)相鄰單元格內(nèi)車輛進(jìn)行通信的概率就越大，連通性就越高。

圖4為車輛密度與路段傳輸時(shí)延的關(guān)系。在道路長度L=1 000 m情況下，當(dāng)車輛密度較小為0.01 vehicle/m，通信半徑為250 m時(shí)，車輛速度為10 m/s要比20 m/s的路段傳輸時(shí)延高出2.2 s。隨著車輛密度的增加傳輸時(shí)延逐漸減小，當(dāng)增加到0.03 vehicle/m后，通信半徑為200 m和250 m的傳輸時(shí)延分別減小到0.9 s和0.7 s,并且保持不變。由以上分析可知，當(dāng)車輛密度較小時(shí)車傳輸方式為攜帶-轉(zhuǎn)發(fā)，速度為影響傳輸時(shí)延的主要因素；當(dāng)車輛密度較大時(shí)，傳輸方式為逐跳轉(zhuǎn)發(fā)，車輛通信半徑為主要因素。

由圖5為道路長度與路段分組投遞率的關(guān)系，當(dāng)前的車輛密度為0.03 vehicle/m。通信半徑R=150 m時(shí)，256 Byte數(shù)據(jù)包的分組投遞率相較于128 Byte的數(shù)據(jù)包大約低6%。當(dāng)數(shù)據(jù)包大小為256 Byte時(shí)，通信半徑150 m要比180 m大約低2%。隨著道路長度的增加，分組投遞率呈遞減的趨勢，同時(shí)單元格的數(shù)值向上取整，所以會出現(xiàn)某個(gè)長度范圍內(nèi)的分組投遞率是相同的。數(shù)據(jù)包越大，信息傳輸過程中發(fā)生錯(cuò)誤丟失的概率就越大，導(dǎo)致分組投遞率越低，而車輛的通信半徑越大，信息轉(zhuǎn)發(fā)所需的跳數(shù)就越少，信息的丟失也就越少，分組投遞率越大。

圖6為蟻群迭代次數(shù)與傳輸時(shí)延的關(guān)系。隨著蟻群迭代次數(shù)的增加，3種算法的數(shù)據(jù)傳輸時(shí)延都在減少。文獻(xiàn)[12]算法是基于傳輸時(shí)延進(jìn)行最優(yōu)路由的選擇，因此，該算法最后迭代的時(shí)延最低，但是更容易產(chǎn)生長時(shí)間的搜索停滯現(xiàn)象。文獻(xiàn)[11]算法基于連通概率進(jìn)行路徑的選擇優(yōu)化，初期搜索較慢，并且也會造成搜索停滯使鏈路處于高負(fù)載狀態(tài)。而LACOR算法最后迭代的時(shí)延表現(xiàn)雖然略低于文獻(xiàn)[12]算法，但根據(jù)圖7可知，其分組投遞率遠(yuǎn)遠(yuǎn)高于文獻(xiàn)[12]算法，并且收斂速度最快，沒有出現(xiàn)搜索停滯的現(xiàn)象，最后的迭代整體效果最優(yōu)。

圖7為蟻群迭代次數(shù)與分組投遞率的關(guān)系。隨著蟻群迭代次數(shù)的增加3種算法的分組投遞率呈增長趨勢。LACOR算法不僅收斂速度快而且分組投遞率最高，沒有出現(xiàn)搜索停滯，在第74次迭代之后就到達(dá)了0.875的分組投遞率，并且增漲的幅度是文獻(xiàn)[12]算法的1.5倍，雖然文獻(xiàn)[11]算法的增長幅度也大，但最終的數(shù)值低于LACOR算法，并且根據(jù)圖6可知，文獻(xiàn)[11]算法的傳輸時(shí)延沒有LACOR算法表現(xiàn)優(yōu)良。綜上所述，2種對比算法僅僅考慮了單方面的鏈路性能，并未達(dá)到較好的效果，均出現(xiàn)不同程度的搜索停滯現(xiàn)象，整體效果低于本文算法。

4 總結(jié)與展望

文中提出了一種城市雙車道環(huán)境下的車載自組織網(wǎng)LACOR算法。該算法通過考慮道路中車輛密度、通信半徑等因素對連通概率、傳輸時(shí)延、分組投遞率的影響來研究鏈路質(zhì)量，再結(jié)合改進(jìn)后的蟻群算法路段選擇公式，以及信息素的更新，求得最優(yōu)路由。仿真結(jié)果表明，該算法收斂速度快、傳輸延時(shí)低、分組投遞率高，具有良好的通信性能，能夠保證信息的可靠穩(wěn)定傳輸。但對于鏈路質(zhì)量權(quán)值系數(shù)的取值方面過于主觀，不能根據(jù)具體傳輸性能要求自我調(diào)節(jié)，是本文接下來需要考慮研究的一個(gè)方面。另一方面，未來5G等新興技術(shù)的發(fā)展一定會推動車輛自動駕駛、道路安全及通信效率服務(wù)等相關(guān)V2X車載自組織網(wǎng)技術(shù)的研發(fā)與應(yīng)用。