車(chē)載自組織網(wǎng)中基于蟻群算法的延遲感知路由協(xié)議*

吳　敏，章國(guó)安，蔡　蓉

(南通大學(xué) 電子信息學(xué)院，江蘇 南通 226019)

?

車(chē)載自組織網(wǎng)中基于蟻群算法的延遲感知路由協(xié)議*

吳敏，章國(guó)安**，蔡蓉

(南通大學(xué) 電子信息學(xué)院，江蘇 南通 226019)

針對(duì)城市道路環(huán)境下車(chē)載自組織網(wǎng)(VANETs)中通信性能下降以及數(shù)據(jù)傳輸失敗的問(wèn)題，提出了一種基于蟻群算法的延遲感知路由(ACDR)協(xié)議。首先，建立雙向車(chē)道的數(shù)學(xué)延遲模型；然后，根據(jù)提出的端點(diǎn)十字路口(EI)的概念，ACDR利用蟻群優(yōu)化(ACO)尋找最佳路線，其中前向螞蟻根據(jù)本地路段延遲以及當(dāng)前十字路口與目的節(jié)點(diǎn)的端點(diǎn)十字路口之間的全局時(shí)延來(lái)選擇路徑，后向螞蟻則負(fù)責(zé)在返回路徑時(shí)更新信息素，同時(shí)，相鄰十字路口之間利用貪婪轉(zhuǎn)發(fā)算法進(jìn)行數(shù)據(jù)包的傳遞。最后仿真比較了ACDR協(xié)議與連通性感知路由(CAR)協(xié)議的性能，結(jié)果表明提出的ACDR協(xié)議的數(shù)據(jù)包的傳輸延遲小，丟包率低，通信性能好。

車(chē)載自組織網(wǎng)絡(luò)；路由協(xié)議；延遲感知；蟻群優(yōu)化算法

1　引　言

車(chē)載自組織網(wǎng)(Vehicular Ad Hoc Network，VANET)是一種特殊的移動(dòng)自組織網(wǎng)絡(luò)(Mobile Ad Hoc Network,MANET)，是智能交通系統(tǒng)(Intelligent Transportation Systems,ITS)的重要部分，可以幫助駕駛員預(yù)測(cè)危險(xiǎn)事故和避免交通堵塞，網(wǎng)絡(luò)中車(chē)輛可以作為路由節(jié)點(diǎn)進(jìn)行數(shù)據(jù)交換[1]。VANET路由協(xié)議根據(jù)數(shù)據(jù)包的目的節(jié)點(diǎn)數(shù)目不同分為單播、廣播和多播路由，本文主要研究單播路由協(xié)議，內(nèi)容主要分為兩類(lèi)，即基于網(wǎng)絡(luò)拓?fù)涞穆酚蓞f(xié)議和基于地理位置信息的路由協(xié)議[2]。當(dāng)確定路由路徑時(shí)，基于網(wǎng)絡(luò)拓?fù)涞穆酚蓞f(xié)議需要整個(gè)網(wǎng)絡(luò)的拓?fù)湫畔?lái)作出決策；而基于地理位置信息的路由協(xié)議只需要通過(guò)GPS獲得車(chē)載的位置來(lái)做出數(shù)據(jù)遞交的決策，因此這類(lèi)協(xié)議對(duì)于頻繁變化的網(wǎng)絡(luò)結(jié)構(gòu)更具有靈活性[3]，但此類(lèi)協(xié)議仍然面臨許多挑戰(zhàn)，比如：不具備實(shí)時(shí)性與準(zhǔn)確性、開(kāi)銷(xiāo)大、應(yīng)用成本增加等。其中，地理源路由(Geographic Source Routing，GSR)是一種基于靜態(tài)地圖的路由，利用Dijkstra最短路徑算法進(jìn)行路由決策，尋找源點(diǎn)與目的節(jié)點(diǎn)的最短路徑，但忽略節(jié)點(diǎn)的動(dòng)態(tài)分布[4]；CAR(Connectivity Aware Routing)是一種基于連通性感知路由，源點(diǎn)利用廣播信息探索路徑，最終獲得一條固定的路由路徑，因此無(wú)法應(yīng)對(duì)VANETs快速變化的拓?fù)浣Y(jié)構(gòu)[5]；GyTAR(Greedy Traffic Aware Routing)是一種利用局部街道動(dòng)態(tài)信息的路由協(xié)議，利用車(chē)輛密度和前進(jìn)方向進(jìn)行路由決策，但是并未考慮全局信息，因此在數(shù)據(jù)轉(zhuǎn)發(fā)過(guò)程中可能會(huì)導(dǎo)致網(wǎng)絡(luò)分區(qū)[6]。

一般情況下，城市環(huán)境下的交通復(fù)雜多變，因此會(huì)造成重復(fù)開(kāi)銷(xiāo)和路由探索時(shí)間長(zhǎng)等問(wèn)題，為此，我們提出一種基于蟻群算法的延遲感知路由(Ant Colony Based Delay Routing,ACDR)協(xié)議。與上述協(xié)議不同的是，通信車(chē)輛首先尋找端點(diǎn)十字路口(Endpoint Intersection，EI)，將車(chē)輛之間的通信路由探索轉(zhuǎn)化成對(duì)應(yīng)十字路口之間的通信路由探索，這樣有效地避免重復(fù)開(kāi)銷(xiāo)，并且相應(yīng)地減少探索時(shí)間。但是，隨著城市道路的不斷變化，VANETs的拓?fù)浣Y(jié)構(gòu)也在快速變化，可能導(dǎo)致路由協(xié)議獲取不準(zhǔn)確的信息，無(wú)法獲得可用路徑。

蟻群優(yōu)化(Ant Colony Optimization，ACO)算法可以解決組合優(yōu)化問(wèn)題，包括二次分配問(wèn)題、車(chē)間任務(wù)調(diào)度問(wèn)題、車(chē)輛路線問(wèn)題和學(xué)習(xí)模糊規(guī)則問(wèn)題。本文則利用ACO算法根據(jù)全局信息靈活地探索路徑，并且尋找最優(yōu)路徑。

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

2.1延遲模型

城市環(huán)境下的道路模型可以簡(jiǎn)化為m×n的十字道路模型。圖1為3×3十字路口道路模型，共有9個(gè)十字路口I1～I(xiàn)9，12個(gè)路段，每條路段的路況皆隨機(jī)分布。

圖1　3×3十字路口道路模型

路段模型主要是根據(jù)城市環(huán)境下雙向車(chē)道的多鏈路轉(zhuǎn)發(fā)延遲而建立，假設(shè)兩個(gè)十字路口Ii、Ij之間的直線車(chē)道方向相反且Ii、Ij之間的路段長(zhǎng)度為L(zhǎng)，數(shù)據(jù)包傳輸方向是向東；同時(shí)路段上車(chē)輛的無(wú)線通信傳輸范圍為R，車(chē)輛的數(shù)目服從泊松分布[7]，向東的道路和向西的道路上車(chē)輛空間密度分別為λ1和λ2，車(chē)輛平均速度分別為v1和v2。

模型分析時(shí)，相鄰十字路口之間的數(shù)據(jù)包利用貪婪攜帶-轉(zhuǎn)發(fā)算法進(jìn)行傳輸。另外，由于城市環(huán)境中交通燈的規(guī)則，車(chē)輛成簇移動(dòng)，簇內(nèi)的車(chē)輛相互連接，因此根據(jù)車(chē)輛簇群的規(guī)模大小，可以將車(chē)輛狀況劃分為如下3種不同的情況。

(1)全部連通狀態(tài)

簇群范圍超出路段邊界，如圖2所示，路段上的所有鏈路完全連通，兩個(gè)十字路口之間的數(shù)據(jù)包利用跳與跳之間的貪婪算法進(jìn)行轉(zhuǎn)發(fā)。

(2)全部斷開(kāi)狀態(tài)

車(chē)輛無(wú)法形成簇群，如圖3所示，鏈路全部中斷，且沒(méi)有可用車(chē)輛轉(zhuǎn)發(fā)數(shù)據(jù)包，因此十字路口之間的數(shù)據(jù)包只能通過(guò)車(chē)輛攜帶進(jìn)行傳輸。

圖3　全部斷開(kāi)狀態(tài)的路段

(3)部分連通狀態(tài)

簇群范圍小于路段規(guī)模，如圖4所示，路段上的車(chē)輛部分連通，因此連通路段上的數(shù)據(jù)包進(jìn)行貪婪轉(zhuǎn)發(fā)，而斷開(kāi)路段上的數(shù)據(jù)包進(jìn)行貪婪攜帶傳輸。

圖4　部分連通狀態(tài)的路段

2.2蟻群算法

螞蟻在尋找食物時(shí)會(huì)在所經(jīng)過(guò)的路徑上釋放出一種特殊的分泌物(信息素)，當(dāng)下一個(gè)路口時(shí)，隨機(jī)挑選一條路徑釋放信息素，螞蟻?zhàn)叩穆窂皆介L(zhǎng)，則釋放的信息素越小，當(dāng)后來(lái)的螞蟻再次碰到這個(gè)路口時(shí)，選擇信息素濃度大的路徑，則經(jīng)過(guò)此路口的螞蟻更多，因而形成一個(gè)正反饋機(jī)制[8]。

根據(jù)螞蟻的多樣性與正反饋以及個(gè)體之間的相互協(xié)作與信息交流，20世紀(jì)90年代Dorigo最早提出了基本螞蟻系統(tǒng)，并應(yīng)用于解決經(jīng)典的旅行商問(wèn)題等優(yōu)化問(wèn)題。

令G=(V，E)為n十字路口的加權(quán)有向圖，其中V表示有向圖頂點(diǎn)的集合，E表示邊的集合，n=|V|，蟻群優(yōu)化用于尋找圖G中源節(jié)點(diǎn)的端點(diǎn)十字路口(Endpoint Intersection source,EIS)到目的節(jié)點(diǎn)的端點(diǎn)十字路口(Endpoint Intersection destination,EID)的最佳路徑，每條邊e(i,j)∈E表示一個(gè)路段，i、j分別表示相鄰的兩個(gè)十字路口，每條邊上存在一個(gè)信息素變量τij和啟發(fā)式信息ηij，當(dāng)探索螞蟻k訪問(wèn)當(dāng)前十字路口i時(shí)，則選擇十字路口j作為下一個(gè)訪問(wèn)的十字路口的概率：

(1)

隨著探索螞蟻的移動(dòng)，路段上的信息素也在發(fā)生變化，因此當(dāng)探索螞蟻到達(dá)EID時(shí)，產(chǎn)生后向螞蟻沿對(duì)應(yīng)的路徑返回EIS，進(jìn)行信息素的更新，更新公式如下：

τij←(1-δ)·τij+δ·Δτij。

(2)

式中：j是i的下一個(gè)十字路口；(1-δ)·τij表示信息素的揮發(fā)；δ·Δτij表示信息素的增量；δ為揮發(fā)系數(shù)，δ∈[0,1]。

本文假設(shè)每個(gè)十字路口設(shè)置一個(gè)靜態(tài)節(jié)點(diǎn)用于存儲(chǔ)信息素。

2.3路由協(xié)議

ACDR路由算法通過(guò)尋找端點(diǎn)十字路口之間的路由代替尋找車(chē)輛之間的路由，有利于避免重復(fù)探索且節(jié)約時(shí)間，并且利用蟻群優(yōu)化算法探索最佳路由路徑，另外兩個(gè)相鄰十字路口之間利用貪婪攜帶-轉(zhuǎn)發(fā)算法轉(zhuǎn)發(fā)數(shù)據(jù)包[9-10]。主要步驟如下：首先，源節(jié)點(diǎn)車(chē)輛S發(fā)送路由請(qǐng)求數(shù)據(jù)包(RREQ)給其端點(diǎn)十字路口EIS，檢查EIS是否有到目的節(jié)點(diǎn)的端點(diǎn)十字路口EID的可用路由信息，若有，EIS發(fā)送路由回復(fù)數(shù)據(jù)包(RREP)給S；然后，S直接將數(shù)據(jù)包轉(zhuǎn)發(fā)給EIS，EIS可以為數(shù)據(jù)包動(dòng)態(tài)地選擇下一個(gè)優(yōu)化十字路口，否則S啟動(dòng)探索螞蟻進(jìn)程，根據(jù)狀態(tài)轉(zhuǎn)移概率和信息素的更新選擇下一跳十字路口，尋找EIS和EID之間的可用路徑，進(jìn)行路徑優(yōu)化，最終得到最優(yōu)路徑[11]。協(xié)議流程如圖5所示。

圖5　ACDR路由協(xié)議流程圖

3　延遲分析

根據(jù)2.1節(jié)的模型可以得出3種情況的路段，接下來(lái)主要分析這3種路況的延遲、連通性以及跳數(shù)。

(1)全部連通狀態(tài)

如圖2所示，數(shù)據(jù)包在十字路口Ii與十字路口Ij之間進(jìn)行傳輸，轉(zhuǎn)發(fā)鏈路長(zhǎng)度Lf定義為數(shù)據(jù)包在路段上進(jìn)行跳與跳轉(zhuǎn)發(fā)所經(jīng)過(guò)的距離，此時(shí)Lf=L。

根據(jù)上述分析，Ii與Ij之間的傳輸延遲表示為

Dfc=Hfc·Tp。

(3)

連通性概率[12]可以表示為

Pfc=(1-e-(λ1+2λ2)·R)N-1。

(4)

式中：N表示路段上向東道路上車(chē)輛的數(shù)目，且N=L·λ1。

(2)全部斷開(kāi)狀態(tài)

如圖3所示，車(chē)輛Cv攜帶數(shù)據(jù)包穿過(guò)路段，此時(shí)攜帶鏈路長(zhǎng)度Lc定義為車(chē)輛穿過(guò)路段的長(zhǎng)度，此時(shí)Lc=L-R。

根據(jù)上述分析，傳輸延遲表示如下：

(5)

式中:V1表示與數(shù)據(jù)包轉(zhuǎn)發(fā)方向相同的車(chē)輛的速度。

假設(shè)K是一個(gè)隨機(jī)變量，表示雙向道上R內(nèi)車(chē)輛的數(shù)目，顯然K滿(mǎn)足泊松分布，概率質(zhì)量函數(shù)(Probability Mass Function,PMF)表示為

(6)

因此，全部中斷的概率Pfb表示為

Pfb=P(K=0)=e-(λ1+λ2)·R。

(7)

(3)部分連通狀態(tài)

如圖4所示，從車(chē)輛Cm到車(chē)輛C1的鏈路是完全連通的，但是路段剩下的鏈路部分是完全斷開(kāi)的，因此數(shù)據(jù)包只能從Cm到C1之間進(jìn)行跳與跳的轉(zhuǎn)發(fā)，然后車(chē)輛C1攜帶數(shù)據(jù)包傳輸直到進(jìn)入十字路口Ij的傳輸范圍，此時(shí)，轉(zhuǎn)發(fā)鏈路的長(zhǎng)度Lf等于十字路口Ii到車(chē)輛C1之間的距離，攜帶鏈路長(zhǎng)度Lc=L-R-Lf，且部分連通性的概率Ppc=1-Pfc-Pfb。

在上述分析的基礎(chǔ)上，傳輸延遲為

(8)

基于上述分析，因此相鄰兩個(gè)十字路口i、j之間的平均傳輸延遲和延遲方差分別為

Dij=Dfc·Pfc+Dfb·Pfb+Dpc·Ppc，

(9)

(10)

另外，路段上數(shù)據(jù)包轉(zhuǎn)發(fā)的平均跳數(shù)為

Hij=Hfc·Pfc+Hfb·Pfb+Hpc·Ppc。

(11)

其中，由于全部中斷的情況下，不存在轉(zhuǎn)發(fā)跳數(shù)，因此Hfb=0。

圖6～8分別是平均延遲與傳輸范圍、車(chē)輛速度和車(chē)輛密度三者之間的關(guān)系曲線。在圖6中平均延遲是關(guān)于傳輸范圍和車(chē)輛空間密度的函數(shù)，交通信息的參數(shù)設(shè)置如下：車(chē)輛速度V1設(shè)為15 m/s；路段長(zhǎng)度L為2 000 m；車(chē)輛空間密度λ1=λ2=λ分別為0.005 vehicle/m、0.015 vehicle/m、0.025 vehicle/m和0.035 vehicle/m。由圖可知：車(chē)輛空間密度相同時(shí)，傳輸范圍增大，數(shù)據(jù)包傳輸所需的延遲會(huì)減?。粋鬏敺秶欢〞r(shí)，車(chē)輛空間密度越大，傳輸延遲越小。在圖7中平均延遲是關(guān)于車(chē)輛速度和車(chē)輛空間密度的函數(shù)，傳輸范圍R為250 m，路段長(zhǎng)度L為2 000 m，車(chē)輛空間密度λ分別為0.005 vehicle/m、0.01 vehicle/m、0.015 vehicle/m和0.02 vehicle/m。由圖可知：車(chē)輛空間密度一定時(shí)，車(chē)輛速度越快，延遲會(huì)逐漸減??；車(chē)輛速度相同時(shí)，車(chē)輛空間密度增加，傳輸延遲會(huì)減少。在圖8中平均延遲是關(guān)于車(chē)輛空間密度和路段長(zhǎng)度的函數(shù)，車(chē)輛速度V1為15 m/s，傳輸范圍R為250 m，路段長(zhǎng)度L分別為500 m、1 000 m、1 500 m和2 000 m。由圖可知：路段長(zhǎng)度相同時(shí)，隨著車(chē)輛空間密度的增加，延遲逐漸減少；車(chē)輛空間密度一定時(shí)，路段長(zhǎng)度越長(zhǎng)，則延遲越高。

圖6　平均延遲與傳輸范圍的關(guān)系

圖7　平均延遲與車(chē)輛速度的關(guān)系

圖8　平均延遲與車(chē)輛密度的關(guān)系

圖9～10分別是平均跳數(shù)與傳輸范圍和車(chē)輛空間密度之間的關(guān)系。在圖9中，平均跳數(shù)是關(guān)于傳輸范圍和車(chē)輛空間密度的函數(shù)，交通信息的參數(shù)設(shè)置如下：車(chē)輛速度V1=15 m/s；路段長(zhǎng)度L=2 000 m，車(chē)輛空間密度λ1=λ2=λ分別為0.005 vehicle/m、0.015 vehicle/m、0.025 vehicle/m和0.035 vehicle/m。由圖可知：曲線先呈上升趨勢(shì)，當(dāng)?shù)竭_(dá)一個(gè)臨界點(diǎn)后呈下降趨勢(shì)，因?yàn)楫?dāng)傳輸范圍R小于臨界值時(shí)，部分路段可能處于斷開(kāi)狀態(tài)，則隨著R的增大，路段斷開(kāi)的長(zhǎng)度可能會(huì)減小，因而平均跳數(shù)會(huì)增加，當(dāng)達(dá)到臨界值時(shí)，隨著傳輸范圍的增加，數(shù)據(jù)包轉(zhuǎn)發(fā)的次數(shù)會(huì)減少，因此平均跳數(shù)減??；同樣，當(dāng)傳輸范圍一定時(shí)，車(chē)輛空間密度增加，則平均跳數(shù)增多。在圖10中，平均跳數(shù)是關(guān)于車(chē)輛空間密度和路段長(zhǎng)度的函數(shù)，車(chē)輛速度V1為15 m/s，傳輸范圍R為250 m，路段長(zhǎng)度L分別為500 m、1 000 m、1 500 m和2 000 m。由圖可知：當(dāng)車(chē)輛空間密度小于0.02 vehicle/m時(shí)，隨著車(chē)輛空間密度的增加，平均跳數(shù)逐漸增加，當(dāng)車(chē)輛空間密度大于0.02 vehicle/m時(shí)，平均跳數(shù)趨于穩(wěn)定；對(duì)于不同的路段長(zhǎng)度，路段長(zhǎng)度越長(zhǎng)，則平均跳數(shù)越多。

圖9　平均跳數(shù)與傳輸范圍的關(guān)系

圖10　平均跳數(shù)與車(chē)輛空間密度的關(guān)系

4　ACDR路由分析

城市環(huán)境下車(chē)輛之間的通信頻繁發(fā)生，尤其是在高峰期，為了減少重復(fù)的路由探索和路由開(kāi)銷(xiāo)，因此提出了端點(diǎn)十字路口的概念，并且利用蟻群優(yōu)化算法根據(jù)當(dāng)前十字路口存儲(chǔ)的信息選擇下一個(gè)十字路口進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)，探索最佳路由。

4.1端點(diǎn)十字路口選擇

利用通信終端(例如源車(chē)輛和目的車(chē)輛)所在路段的車(chē)輛空間密度和其與鄰居十字路口的距離來(lái)選擇端點(diǎn)十字路口，對(duì)于每個(gè)候選十字路口i給定一個(gè)評(píng)分，評(píng)分最高的十字路口為端點(diǎn)十字路口。評(píng)分公式如下：

(12)

式中：d(i)表示通信終端到候選十字路口i的距離；χ為加權(quán)因子；L對(duì)應(yīng)當(dāng)前路段的距離；Navg表示當(dāng)前路段上車(chē)輛的平均數(shù)目；Ncon表示區(qū)域內(nèi)車(chē)輛的平均數(shù)目。

4.2路由發(fā)現(xiàn)

當(dāng)探索螞蟻進(jìn)行移動(dòng)時(shí)，根據(jù)路段的延遲模型，每條邊上對(duì)應(yīng)的啟發(fā)式信息ηij和信息素τij會(huì)發(fā)生相應(yīng)的變化，ηij表示i和j之間路段的本地延遲，并且可以幫助螞蟻探索新的路徑，表達(dá)式如下：

(13)

式中：Dij、Dvij分別表示十字路口i和j之間的延遲和延遲方差；Dth表示EIS和EID之間的延遲臨界值，定義如下：

(14)

式中：Distance(EIS,EID)表示EIS和EID之間的距離；v表示車(chē)輛速度。

τij反映從當(dāng)前十字路口i到EID(在這條路徑上，i的下一個(gè)十字路口是j)路徑的全局延遲，Δτij是反向螞蟻更新的信息素。Δτij的表示如下：

(15)

式中：Dj(i,EID)和Dvj(i,EID)分別表示從當(dāng)前十字路口i到EID且經(jīng)過(guò)十字路口j之間的路徑上的延遲和延遲方差。

一旦所有的反向螞蟻到達(dá)源節(jié)點(diǎn)時(shí)，EIS和EID之間信息素τ最大的路徑為最佳路由，為了應(yīng)對(duì)通信對(duì)的拓?fù)渥兓妥赃m應(yīng)地選擇最佳路由，一旦源節(jié)點(diǎn)或目的節(jié)點(diǎn)的端點(diǎn)十字路口EI改變，一個(gè)新的路由探索就會(huì)實(shí)現(xiàn)。

5　性能仿真

利用Matlab仿真軟件對(duì)ACDR的性能指標(biāo)進(jìn)行仿真分析，并且與CAR[4]協(xié)議進(jìn)行性能參數(shù)的比較。仿真環(huán)境選取4×4十字路口的城市道路進(jìn)行模擬，相關(guān)仿真參數(shù)如表1所示。

表1　仿真參數(shù)設(shè)置

圖11為平均延遲與累積分布函數(shù)的曲線，由圖可知ACDR的累積分布函數(shù)始終高于CAR，同時(shí)當(dāng)車(chē)輛速度較高時(shí)，兩種協(xié)議的累積分布函數(shù)皆高于速度低時(shí)，意味著ACDR具有較低的平均延遲。CAR協(xié)議是一種基于源點(diǎn)位置的路由協(xié)議，不能及時(shí)自適應(yīng)地處理拓?fù)涞淖兓?，但所提出的ACDR協(xié)議可以利用最新的路由信息動(dòng)態(tài)地進(jìn)行路由決策，尋找出最佳路由。

圖11　平均延遲的累積分布函數(shù)

圖12為車(chē)輛數(shù)目與數(shù)據(jù)包傳輸比值的曲線，由圖可知車(chē)輛越多，數(shù)據(jù)包丟失越少，同時(shí)針對(duì)不同的車(chē)輛數(shù)目，ACDR的數(shù)據(jù)包傳輸能力較優(yōu)，ACDR協(xié)議利用蟻群算法及時(shí)更新信息，適應(yīng)網(wǎng)絡(luò)拓?fù)涞目焖僮兓罱K尋找最優(yōu)路徑，避免網(wǎng)絡(luò)堵塞；CAR協(xié)議根據(jù)源點(diǎn)位置確定一條完整的路由路徑，但對(duì)于不斷變化的網(wǎng)絡(luò)結(jié)構(gòu)而言，固定的路徑會(huì)導(dǎo)致大量數(shù)據(jù)包的丟失。

圖12　數(shù)據(jù)包傳輸比值與車(chē)輛數(shù)目的關(guān)系

6　結(jié)束語(yǔ)

本文提出了一種基于蟻群優(yōu)化算法的車(chē)載自組織網(wǎng)絡(luò)路由協(xié)議，首先利用ACO解決延遲的最優(yōu)化問(wèn)題，接著利用探索螞蟻和反向螞蟻探索所有可用路徑，更新信息素表，最終選擇最佳路由，并且在兩個(gè)相鄰十字路口之間，利用貪婪攜帶-轉(zhuǎn)發(fā)算法進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)。仿真結(jié)果顯示，與CAR協(xié)議相比，所提出的ACDR協(xié)議延遲性能更優(yōu)，數(shù)據(jù)包傳輸性能更好，可以自適應(yīng)地處理網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)變化，更具有靈活性。但是蟻群算法復(fù)雜度比較高，搜索時(shí)間較長(zhǎng)，仿真過(guò)程中容易出現(xiàn)停滯現(xiàn)象，因此今后可以考慮將蟻群算法與其他啟發(fā)式仿生算法結(jié)合，優(yōu)勢(shì)互補(bǔ)，進(jìn)一步優(yōu)化系統(tǒng)性能。

[1]金婕,艾寶麗. 智能交通系統(tǒng)的無(wú)線信道建模[J].電訊技術(shù),2015,55(3):262-269.

JIN Jie,AI Baoli.Channelmodeling for intelligent transport system[J].Telecommunication Engineering,2015,55(3):262-269.(in Chinese)

[2]AL-RABAYAH M,MALANEY R.A new scalable hybrid routing protocol for VANETs[J].IEEE Transactions on Vehicular Technology,2012,61(6):2625-2635.

[3]RAJESH K,KARTHICK V R,RAJ G S.A new scalable reactive location based ad hoc routing protocol for VANETs[C]//Proceedings of 2014 International Conference on Information Communication and Embedded Systems(ICICES).Chennai,Indian:IEEE,2014:1-5.

[4]CHO K,RYU M.A survey of greedy routing protocols for vehicular ad hoc networks[J].Smartcr,2012,2(4):125-137.

[5]ALSHARIF N,SHEN X S. iCARII:intersection-based connectivity aware routing in vehicular networks[C]//Proceedings of 2014 IEEE International Conference on Communications(ICC). Sydney:IEEE,2014:2731-2735.

[6]JERBI M,RASHEED T,SENOUCI S M,et al.Towards efficient geographic routing in urban vehicular networks[J].IEEE Transactions on Vehicular Technology,2009,58(9):5048-5058.

[7]ATHANASIOS P,PETER M,SIMONE F,et al.On temporal stochastic modeling of precipitation,nesting models across scales[J].Advances in Water Resources,2014,63(2):152-166.

[8]KADONO D,IZUMI T,OOSHIT F,et al.An ant colony optimization routing based on robustness for ad hoc network with GPSs[J].Ad Hoc Networks,2010,8(1):63-67.

[9]WANG S,LIN C,HWANG Y,et al.A practical routing protocol for vehicle-formed mobile ad hoc networks on the roads[C]//Proceedings of 2005 IEEE Intelligent Transportation Systems. Vienna,Austria:IEEE,2005:161-166.

[10]PANICHPAPIBOON S,PATTARA-ATIKOM W.Connectivity requirements for self-organizing traffic information systems[J].IEEE Transactions on Vehicular Technology,2008,57(6):3333-3340.

[11]LI G,BOUKHATEM L,MARTIN S.An intersection-based QoS routing in vehicular ad hoc networks[J].Mobile Networks & Applications,2014,20(2):268-284.

[12]SANTOS R A,EDWARDS A,EDWARDS R M,et al.Performance evaluation of routing protocols in vehicular ad hoc networks[J].International Journal of Ad Hoc and Ubiquitous Computing,2005,1(2):80-91.

吳敏(1992—)，女，江蘇如皋人，碩士研究生，主要研究方向?yàn)檐?chē)載自組織網(wǎng)絡(luò);

WU Min was born in Rugao,Jiangsu Province,in 1992. She is now a graduate student. Her research concerns vehicular ad hoc networks.

Email：125524853@qq.com

章國(guó)安(1965—)，男，江蘇如皋人，2001年于東南大學(xué)獲博士學(xué)位，現(xiàn)為教授、博士生導(dǎo)師，主要研究方向?yàn)闊o(wú)線通信網(wǎng)絡(luò)理論與技術(shù);

ZHANG Guoan was born in Rugao，Jiangsu Province,in 1965. He received the Ph.D.degree from Southeast University in 2001.He is now a professor and also the Ph.D. supervisor. His research concerns wireless communication network theory and technology.

Email：gzhang@ntll.edu.cn

蔡蓉(1991—)，女，江蘇鹽城人，碩士研究生，主要研究方向?yàn)檐?chē)載自組織網(wǎng)絡(luò)。

CAI Rong was born in Yancheng,Jiangsu Province,in 1991. She is now a graduate student. Her research concerns vehicular ad hoc networks.

The National Natural Science Foundation of China(No.61371113,61401241);Project of Ministry of Transport of the People′s Republic of China(2013-319-825-110)

A Delay Perception Routing Protocol Based on Ant Colony Algorithm in Vehicular Ad Hoc Networks

WU Min,ZHANG Guoan,CAI Rong

(School of Electronics and Information,Nantong University,Nantong 226019,China)

In order to solve the data transmission failure problem and improve the degradation of communication performance on city roads in vehicular ad hoc networks(VANETs),a delay perception routing protocol based on ant colony algorithm is proposed. Firstly,a two-way lanes model of delay is established. Then according to the concept of endpoint intersection(EI),the routing protocol uses ant colony optimization to find the best route.According to the local delay and global delay of a route between current intersection and the endpoint intersection of destination,path is selected by forward ants. Backward ants are responsible for updating pheromone in the return path.At the same time,packets are transmitted by greedy forwarding algorithm between the adjacent intersections. Finally,ant colony algorithm based delay perception routing protocol and connectivity aware routing protocol are compared by simulation. The simulation results show that the proposed routing protocol is superior in terms of packet transmission delay,packet loss rate and communication performance.

vehicular ad hoc network(VANET)；routing protocol；delay perception；ant colony optimization

10.3969/j.issn.1001-893x.2016.10.004

2016-03-02；

2016-06-03Received date:2016-03-02；Revised date：2016-06-03

國(guó)家自然科學(xué)基金資助項(xiàng)目(61371113,61401241);交通運(yùn)輸部應(yīng)用基礎(chǔ)研究基金資助項(xiàng)目(2013-319-825-110)

TN915.04;TP393

A

1001-893X(2016)10-1086-07

引用格式：吳敏，章國(guó)安，蔡蓉.車(chē)載自組織網(wǎng)中基于蟻群算法的延遲感知路由協(xié)議[J].電訊技術(shù)，2016,56(10):1086-1092.[WU Min,ZHANG Guoan,CAI Rong.A delay perception routing protocol based on ant colony algorithm in vehicular ad hoc networks[J].Telecommunication Engineering,2016,56(10):1086-1092.]

**通信作者：gzhang@ntu.edu.cnCorresponding author：gzhang@ntu.edu.cn