文獻(xiàn)標(biāo)識碼: A
文章編號: 0258-7998(2015)01-0094-05
0 引言
車聯(lián)網(wǎng)VANET(Vehicular Ad Hoc Network)是自組織網(wǎng)(Ad Hoc Network)的特例。VANET中的車輛可與鄰近的車輛或路邊設(shè)施(Road Side Units,,RSU)通信,。為此,VANET的通信可分為車間通信(Vehicle-to-Vehicle,,V2V)和車與基礎(chǔ)設(shè)施通信(Vehicle-to-Infrastructure,,V2I)。在V2V通信中,,車輛采用短距離無線技術(shù)實(shí)現(xiàn)車輛間信息的交換,,如Wi-Fi 和WAVE[1]。車輛通過特殊的電子設(shè)備使其能接收,、發(fā)送消息,。在V2I通信中,,道路上的車輛能與鄰近的RSU進(jìn)行連接并交互信息。本文,,主要針對V2V通信展開分析,。
在V2V中,車輛通過車載單元向其他車輛傳遞消息,。車輛的快速移動和其分布的不均勻,,為VANET的路由提出了挑戰(zhàn),。首先,,鏈路的使用壽命受車輛移動的影響;其次由于網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化,,每個車輛的路由表需不斷的更新,,這將會增加額外通信負(fù)擔(dān),甚至?xí)鸲氯鸞2-3],,使得數(shù)據(jù)包的傳輸變得更為艱難,。為此,本文,,提出多路徑路由算法,。
依據(jù)路由策略,路由可分為5類[4]:(1)基于拓?fù)渎酚?Topology-Based Routing),;(2)基于位置路由(Position-based Routing),;(3)分簇路由(Cluster-based Routing);(4)廣播路由(Broadcast Routing),;(5)組播路由(Geocast Routing),。在拓?fù)渎酚芍校帽泶鎯ν負(fù)湫畔⒉⑼ㄟ^請求更新,,如AODV[5],。在位置路由中,車輛通過系統(tǒng)獲取車輛的位置信息決策路由,,如GPSR[6],。分簇路由[7]是將節(jié)點(diǎn)分簇,構(gòu)成虛擬網(wǎng)絡(luò)結(jié)構(gòu),。地理區(qū)域被劃分為網(wǎng)格,,并在網(wǎng)格內(nèi)選取節(jié)點(diǎn)作為簇首(Cluster Head)。簇首負(fù)責(zé)簇間以及簇內(nèi)的協(xié)調(diào)工作,。廣播路由就是通過廣播分發(fā)數(shù)據(jù)包,,如BROADCOMM[8]。組播路由在地理區(qū)域內(nèi)傳遞數(shù)據(jù),,并限制區(qū)域內(nèi)泛洪,,如IVG[9],。每類路由具有各自的獨(dú)立的特點(diǎn)。本文提出的算法引用拓?fù)浜突谖恢寐酚蓛煞N策略理念,。
VANET的路由可描述成單路徑,、存儲轉(zhuǎn)發(fā)路徑和多路徑路由。現(xiàn)存有大量的多路徑路由,,如按需多路徑距離矢量路由[10](Ad hoc On-Demand Multi-path Distance Vector,,AOMDV),S-AOMDV[11],,AODVM[12],。這些路由是基于AODV的改進(jìn)版,屬于反應(yīng)式路由,,不具有可擴(kuò)展性,。例如,S-AOMDV通過額外的數(shù)據(jù)提高路由發(fā)現(xiàn)效率以及修復(fù)路由失敗,,這會引起通信擁塞,,降低帶寬利用率。
移動自組織網(wǎng)的研究工作[13-14]表明,,受昆蟲激勵的自然啟發(fā)算法被成功地引入路由機(jī)制,,如基于蟻群優(yōu)化(Ant Colony based Optimization,ACO),。與其他算法[15-16]相比,,此類算法表現(xiàn)良好的性能。如:通過共享局部信息,,減少路由負(fù)擔(dān),;提供多路徑路由,以防路由失敗,。
目前,,面向VANET的移動感知的蟻群優(yōu)化算法[17](Mobility-Aware Aant Colony Optimization,MARDYMO)是唯一受自然啟發(fā)的路由算法,。該算法屬于反應(yīng)式路由,,采用廣播機(jī)制向網(wǎng)絡(luò)內(nèi)車輛傳遞消息,這將占用大量的帶寬,,且不具有可擴(kuò)展性,。
本文提出了混合式的ACO算法。該算法將充分有效利用帶寬,,并具有可擴(kuò)展性,,對鏈路斷裂具有強(qiáng)健性。將車輛歸入?yún)^(qū)域,,每個車輛屬于一個或兩個重疊區(qū)域,。在區(qū)域內(nèi)通過先應(yīng)式算法尋找路由,。在區(qū)域間通過存儲于每個區(qū)域內(nèi)的局部信息,并采用反應(yīng)式算法尋找路由,。通過這種方式,,減少廣播和擁塞。充分利用車輛的移動模型,、車輛密度和車輛速度去構(gòu)建多路徑算法,,即(Mobility Aware Zone based Ant Colony Optimization Routing for VANET,MAZACORNET),。
車輛的移動使得車輛在短時間內(nèi)遠(yuǎn)離彼此的通信范圍,。為此,在設(shè)計(jì)路由時,,必須對車輛的位置以及車輛間連接進(jìn)行管理,。在MAZACORNET中,,通過全球定位系統(tǒng)(Global Positioning System,,GPS)獲取位置和速度信息。通過車輛間連接管理提高路由的穩(wěn)定性,,通過車輛的位置,、速度信息可計(jì)算鏈路的穩(wěn)定性。
1 蟻群優(yōu)化算法
從自然界得到解決問題的方法被稱為群體智慧(Swarm intelligence,,SI),。作為群體智慧之一的蟻群優(yōu)化算法就是被廣泛應(yīng)用于解決靜態(tài)和動態(tài)問題[18]。
Goss[19]研究了螞蟻的行為,,研究結(jié)果表明,,螞蟻能夠從食物源到自己巢穴之間找到最短路徑,而且能夠輕巧避開障礙物,。螞蟻在通往食物路徑上存儲化學(xué)物質(zhì),,將這種物質(zhì)稱為信息素。后續(xù)的螞蟻依據(jù)信息素沿著路徑移動,。螞蟻通常向信息素多的地方靠攏,。沿著信息素多的地方移動,就能以最短路徑找到食物,。這個過程就是間接通信的示例,。
2 MAZACORNET
2.1 鏈路的穩(wěn)定性
位置管理和連接管理對路由算法的性能起到非常關(guān)鍵的作用。通常,,通過GPS獲取車輛的位置和速度信息,。連接管理用于維持路由的穩(wěn)定性。
假定行駛道路上的兩個車輛i,、j,,通過GPS獲取的初始位置分別為(Xi0,,Yi0)和(Xj0,Yj0),,初始速度分別為Vi0和Vj0,。如果兩個車輛在同一個通信范圍內(nèi),則認(rèn)為它們是鄰居,。用D表示兩車間的距離,,R表示通信范圍。如果D>R,,鏈路斷裂,。車輛i、j間的鏈路的使用壽命?駐t表示從鏈路建立時t0到當(dāng)D=R時t1時間差,,即?駐t=t1-t0,。如果給定車輛的位置以及速度,鏈路的使用壽命?駐t可通過式(1)進(jìn)行計(jì)算[20],。
車輛i,、j間的鏈路的穩(wěn)定性LS(Link Stability)可通過式(2)進(jìn)行計(jì)算[21]:
其中,tmax為常數(shù),,表示路由表的有效期,。在本文提出的算法中,鏈路穩(wěn)定性將被用于決策路由,。
2.2 面向VANET的ACO模型
信息素是ACO算法中最為關(guān)鍵的參數(shù),。在蟻群中,信息素被存儲于地面上,,從而吸引更多的螞蟻沿著由信息素構(gòu)成的路由移動,。對于VANET,聚集在鏈路上的信息素的增加和減弱均表征了該鏈路的質(zhì)量,。為了獲取高質(zhì)量的鏈路,,應(yīng)尋找沿途沉積信息素大的路徑,即優(yōu)質(zhì)鏈路,。假定從源節(jié)點(diǎn)至目的節(jié)點(diǎn)鏈路Lij,,沉積的信息素量可表示為式(3):
其中,LS表示鏈路的質(zhì)量,,可由式(2)進(jìn)行計(jì)算,,PR表示成功接受消息的概率。
成功接受消息的概率PR取決于在同一個通信范圍內(nèi)車輛間的距離,,可通過Nakagami Fading Model[22]進(jìn)行估計(jì),。該模型結(jié)合了VANET的高速、城市環(huán)境的特點(diǎn),如式(4)所示,。
其中,,m表示衰減參數(shù)。例如,,當(dāng)m=3,,表示快速衰減環(huán)境。
通過式(3)和(4),,沉積在鏈路Lij上的信息素可通過式(5)進(jìn)行計(jì)算:
在ACO算法中,,信息素的蒸發(fā)率通常設(shè)定為常數(shù)[23]。然而,,在本文提出的算法中,,針對每條不同的鏈路,
的值不同,。每條鏈路Lij的蒸發(fā)率可通過式(6)計(jì)算,。
其中,k表示鏈路上至少沉積的信息素,。為蒸發(fā)時限的倒數(shù),。
以上分析了面向VANET的ACO路由算法,接下來將分析基于蟻群優(yōu)化的混合式移動感知路由算法,。該算法具有可擴(kuò)展性,,并結(jié)合了反應(yīng)式和先應(yīng)式路由的優(yōu)點(diǎn),。
2.3 基于蟻群的區(qū)域算法
在本文算法中,,網(wǎng)絡(luò)劃分為區(qū)域。在區(qū)域內(nèi)通過先應(yīng)式算法傳輸數(shù)據(jù)包,,區(qū)域與區(qū)域間采用反應(yīng)式算法,。通信跳數(shù)決定區(qū)域的尺寸大小。車輛可處于兩個重疊區(qū)域,,區(qū)域尺寸也可變動,。依據(jù)車輛所處區(qū)域的位置,可將車輛分為區(qū)內(nèi)車輛(Interior Vehicle),、區(qū)邊車輛(Boundary Vehicle)和區(qū)外車輛(Exterior Vehicle),。如圖1所示,源節(jié)點(diǎn)S,,區(qū)域半徑為2跳,,車輛A、D,、F處于邊界上,,稱為區(qū)邊車輛。車輛B、C,、E是區(qū)內(nèi)車輛,,其他的車輛屬區(qū)外車輛。
路由過程主要分為兩個階段:路由發(fā)現(xiàn)和路由維護(hù),。本文算法采用兩類路由表:區(qū)內(nèi)路由表(Intra Zone Routing)和區(qū)間路由表(Inter Zone Routing),。區(qū)內(nèi)路由表實(shí)時更新區(qū)域內(nèi)信息,而區(qū)間路由表按需追蹤區(qū)間信息,。在路由發(fā)現(xiàn)和路由維護(hù)階段,,使用五類蟻群,分別為區(qū)內(nèi)轉(zhuǎn)發(fā)蟻群(Internal Forward Ants),、區(qū)外轉(zhuǎn)發(fā)蟻群(External Forward Ants),、后向蟻群(Backward Ants)、通告蟻群(Notification Ants)以及錯誤蟻群(Error Ants),。
螞蟻用的數(shù)據(jù)表示格式如表1所示,。
其中,Source表示源節(jié)點(diǎn)地址,。Destination表示目的節(jié)點(diǎn)地址,,對于區(qū)內(nèi)轉(zhuǎn)發(fā)的蟻群,該區(qū)域?yàn)榭?。Sequence number表示每個螞蟻附身的序列號,。Type用于標(biāo)識不同類的螞蟻,區(qū)內(nèi)轉(zhuǎn)發(fā)蟻群,、區(qū)外轉(zhuǎn)發(fā)蟻群,、后向蟻群、通告蟻群以及錯誤蟻群分別用0,、1,、2、3,、4表示,。Hop表示節(jié)點(diǎn)與區(qū)域內(nèi)所有其他節(jié)點(diǎn)間的跳數(shù)。該區(qū)域的值用于辨別節(jié)點(diǎn)是屬于區(qū)內(nèi)節(jié)點(diǎn)或非區(qū)內(nèi)節(jié)點(diǎn),。Speed表示該節(jié)點(diǎn)的速度,。Position表示該節(jié)點(diǎn)當(dāng)前的位置。Path表示由一系列節(jié)點(diǎn)構(gòu)成的源節(jié)點(diǎn)至目的節(jié)點(diǎn)的路徑,。
(1)區(qū)域內(nèi)的路由發(fā)現(xiàn)
區(qū)內(nèi)路由表用于區(qū)域內(nèi)的路由發(fā)現(xiàn)階段,。該表包含了區(qū)域內(nèi)所有車輛的信息。區(qū)內(nèi)轉(zhuǎn)發(fā)的蟻群周期地更新表中的車輛信息,。表中的列表示區(qū)域內(nèi)所有車輛,,而行表示離其他車輛一跳距離的車輛。在路由表中,通過式(5)和式(6)增加和減弱信息素識別路由,。當(dāng)源節(jié)點(diǎn)需要向目的節(jié)點(diǎn)發(fā)送信息時,,首先查詢區(qū)內(nèi)路由表的列,如果目的節(jié)點(diǎn)在它的區(qū)域,,路由發(fā)現(xiàn)階段就完成了,,否則,就在區(qū)域間進(jìn)行路由發(fā)現(xiàn),,如下文所示,。
(2)區(qū)域間的路由發(fā)現(xiàn)階段
當(dāng)車輛在其區(qū)域內(nèi)不能找到目的節(jié)點(diǎn)時,區(qū)域間路由表就開始發(fā)揮作用,。通過區(qū)域間路由表尋找區(qū)邊車輛,,以構(gòu)建新的路由。區(qū)外轉(zhuǎn)發(fā)蟻群向區(qū)邊節(jié)點(diǎn)靠攏,,直到發(fā)現(xiàn)目的節(jié)點(diǎn),。一旦發(fā)現(xiàn)了目的節(jié)點(diǎn),后向蟻群將向源節(jié)點(diǎn)遍歷返回路線,。然而,,如果沒有發(fā)現(xiàn)目的節(jié)點(diǎn)或路徑的有效期已過期,則從當(dāng)前區(qū)域使用區(qū)邊節(jié)點(diǎn)重復(fù)進(jìn)行路由發(fā)現(xiàn),,直到發(fā)現(xiàn)目的節(jié)點(diǎn),。
(3)路由維護(hù)
由于網(wǎng)絡(luò)拓?fù)鋭討B(tài)變化,路由可能斷裂,。如果是在區(qū)域內(nèi)路由斷裂,,則按先應(yīng)式算法原則周期地修復(fù)。若是在區(qū)域間路由斷裂,,則該路由的上游車輛存儲數(shù)據(jù)包并選擇備用路由,。如果存在備用路由,則啟動備用路由并更新,。如果不存在,則通過錯誤蟻群向源節(jié)點(diǎn)發(fā)送路由失敗消息,。
3 系統(tǒng)仿真及分析
3.1 仿真場景建立
使用隨機(jī)街道的都市場景進(jìn)行仿真,。初始仿真區(qū)域?yàn)?00 m×500 m的區(qū)域,車輛數(shù)為25,,交通燈數(shù)為10,。隨后,區(qū)域變?yōu)? 500 m×1 500 m,,車輛數(shù)增加至100,。構(gòu)建NS2仿真參數(shù)如下:
(1)仿真時間設(shè)定為2 000 s,車輛于t=0 s時刻移動,于t=100 s開始傳輸,;
(2)車輛數(shù)目被設(shè)定為25,、50、75,、100,;
(3)數(shù)據(jù)包大小為512 B;
(4)采用PriQuenue隊(duì)列,;
(5)采用IEEE 802.11pw作為MAC協(xié)議,;
(6)采用Nagakami傳播模型;
(7)仿真的協(xié)議為:MAZCORNET,、AODV,、AMODV、GPSR,。
3.2 仿真結(jié)果
本小節(jié)分析MAZCORNET的路由性能,,并與其他路由協(xié)議比較。
3.2.1 車輛數(shù)目對端到端傳輸時延的影響
圖2 顯示了車輛數(shù)目對端到端傳輸時延的影響曲線,。與AODV,、AMODV和GPSR相比,MAZCORNET的端到端傳輸時延最低,。這主要?dú)w功于MAZCORNET采用了區(qū)域架構(gòu),、區(qū)內(nèi)路由表和區(qū)間路由表。在區(qū)域內(nèi),,通過先應(yīng)式路由維護(hù)區(qū)內(nèi)路由表,,而在區(qū)間存有由蟻群存儲的路徑。通過這些預(yù)先準(zhǔn)備的路徑信息有助于提高數(shù)據(jù)包端到端的快速傳輸,。使用式(6)調(diào)整鏈路上信息素的減弱率,,導(dǎo)致斷裂鏈路能及時被蟻群發(fā)現(xiàn)并丟棄。通過這些措施減輕了MAZACORNET端到端傳輸時延,。
3.2.2 車輛數(shù)目對數(shù)據(jù)包傳遞率的影響
圖3顯示了MAZACORNET以及其他路由算法AODV,、AMODV、GPSR的數(shù)據(jù)包傳遞率,。從圖3可知,,當(dāng)車輛數(shù)目較少時,MAZCORNET并不具有良好的數(shù)據(jù)包傳遞率,。這主要是由于沉積在鏈路上的信息素很少,,區(qū)邊車輛不能傳遞數(shù)據(jù)包。在這種情況下,,上游車輛緩存所有的數(shù)據(jù)包,,并啟動修復(fù)程序,,尋找通往目的節(jié)點(diǎn)的其他路徑。一旦發(fā)現(xiàn)了新的路徑,,將告知源節(jié)點(diǎn),。同時,緩存的數(shù)據(jù)包就依據(jù)這條新發(fā)現(xiàn)的路徑傳遞到目的節(jié)點(diǎn),。從圖3可知,,當(dāng)節(jié)點(diǎn)數(shù)目的增加,MAZACORNET數(shù)據(jù)包傳遞率優(yōu)于其他路由算法,。這主要是因?yàn)镸AZACORNET具有多條路徑選擇,,而AODV和GPSR的路徑選擇是單一的。
3.2.3 車輛數(shù)目對數(shù)據(jù)吞吐量的影響
吞吐量性能曲線如圖4所示,。當(dāng)車輛數(shù)目增加,,MAZACORNET的吞吐量性能最好。這是因?yàn)殡S著車輛數(shù)目的增加,,區(qū)域內(nèi)車輛數(shù)也隨之增加,,這會提高區(qū)域內(nèi)車輛的連接率,增加了路徑數(shù),,從而使數(shù)據(jù)傳輸更為流暢,,降低了數(shù)據(jù)包的丟失率,提高了數(shù)據(jù)包的傳輸率,,如圖3所示,。
3.2.4 車輛數(shù)目對路由開銷的影響
圖5顯示了MAZACORNET以及其他路由算法AODV、AOMDV,、GPSR的路由開銷性能曲線,。由于AODV和AOMDV是屬于反應(yīng)式路由,無區(qū)域概念,。而MAZACORNET在區(qū)域內(nèi)使用了先應(yīng)式路由理念,。通過周期地發(fā)送控制包維護(hù)區(qū)域內(nèi)路由,這是MAZACORNET路由開銷的主要來源,。
本節(jié),,通過仿真結(jié)果分析了文中提出算法的性能。結(jié)果表明,,MAZACORNET更適合城市場景即密集網(wǎng)絡(luò),。當(dāng)網(wǎng)絡(luò)密集時,該算法能獲取較高的數(shù)據(jù)傳遞率和較低的端到端傳輸時延,,與其他路由算法相比,由于MAZACORNET能夠提供多條路徑,,維持較高的通信連接率,,因此表現(xiàn)出更好的性能,。
4 結(jié)論
針對VANET的路由問題,提出MAZACORNET路由方案,。該方案是基于先應(yīng)式和反應(yīng)式兩種路由理念的混合多路徑路由算法,。在路由決策過程中,不廣播消息,,并提供多條可選路徑,。將網(wǎng)絡(luò)區(qū)域劃分為不同的區(qū)域。在區(qū)域內(nèi)通過先應(yīng)式路由方案建立路徑,,而在區(qū)域間采用反應(yīng)式路由方案尋找路由,,從而減少控制包廣播的次數(shù),降低了網(wǎng)絡(luò)擁塞率,。仿真結(jié)果表明,,提出的MAZACORNET在密集車輛區(qū)域表現(xiàn)出了良好的性能,有效地提高了數(shù)據(jù)包傳輸率,,降低了端到端傳輸時延,。
參考文獻(xiàn)
[1] Xiang Weidong,Shan Dan,,Yuan Jiaqi,,et al.A full func-tional wireless access for vehicular environments(WAVE) prototype upon the IEEE 802.11p standard for vehicular communications and networks. In Proceedings of IEEE Consumer Communications and Networking Conference[C], Las Vegas, NV, USA 2012:58-59.
[2] 王海鳳,何之棟,,黃文君.故障安全通信系統(tǒng)的研究與設(shè)計(jì)[J].電子技術(shù)應(yīng)用,,2014(1):115-119.
[3] KAKARLA J,SATHYA S S,,GOVINDA B,,et al.A survey on routing protocols and its issues in VANET[J].InternationalJournal of Computer Applications,2011,,28(4):38-44.
[4] JOHNSON D B,,MALTZ D A.Dynamic source routing in ad hoc wireless networks[J].Kluwer Academic Publishers,Boston,,1996,,5(353):153-181.
[5] Pei Guangyu,GERLA Mario,,Tsu-Wei Chen.Fisheye state routing:a routing scheme for ad hoc wireless networks[C].In Proceedings of IEEE International Conference on Comm-unications,,New Orleans,USA,,2000:70-74.
[6] KARP B,,KUNG H T.GPSR:Greedy Perimeter Stateless Routing for wireless networks[C].In Proceedings of the 6th Annual ACM International Conference on Mobile Computingand Networking, Boston, Massachusetts, United States, Aug.2000:243-254.
[7] LIN C R,GERLA M.Adaptive clustering for mobile wirelessnetworks[J].IEEE Journal on Selected Areas in Communi-cations, 1997,15(7):1265-1275.
[8] DURRESI M,,DURRESI A,,BAROLLI L.Emergency broad-cast protocol for inter-vehicle communications[C].In Pro-ceedings of 11th International Conference on Parallel and Distributed Systems, 2011,,2(3):402-406.
[9] BACHIR A,BENSLIMANE A.A multicast protocol in ad hoc networks inter-vehicle geocast[C].In Proceedings of 57th IEEE Semiannual Conference on Vehicular Technology, April 2013,4(4):2456-2460.
[10] MARINA M K,,DAS S R.On-demand multipath distance vector routing in ad hoc networks[C].In Proceedings of 9thIEEE International Conference on Network Protocols, pages14-23, California, USA, Nov. 2001.
[11] Chen Yufeng,,Xiang Zhengtao,Wei Jian,,et al.An improvedAOMDV routing protocol for V2V communication[C]. In Proceedings of the IEEE Intelligent Vehicles Symposium, 2011:1115-1120.
[12] Ye Zhenqiang,,KRISHNAMURTHY S V,TRIPATHI S K.A framework for reliable routing in mobile ad hoc net-works[C]. In Proceedings of the 22nd IEEE International Conference on Computer Communications), pages 270-280, San Francisco, USA, Mar. 2003:270-280.
[13] SCHOONDERWOERD Ruud,,BRUTEN J L,,HOLLAND O E,et al.Ant-based load balancing in telecommunications networks[J].Adaptive Behavior, 1996,5(2):169-207.
[14] PRASAD Sunita,,SINGH Y P,,RAI C S.Swarm based routing for MANETs[J]. International Journal of Recent Trends in Engineering,2011,1(1):153-158.
[15] CLAUSEN T H,JACQUET P.Optimized link state routing protocol(OLSR).Technical report, INRIA, Oct.2003.
[16] PERKINS C,,ROYER E M.Ad-hoc on-demand distance vector routing[C].In Proceedings of 2nd IEEE Conference on Mobile Computing Systems and Applications, February 1999:90-100.
[17] LUIS Sergio,,CORREIA O B,CELESTINO Joaquim,,et al.Mobility-aware ant colony optimization routing for vehicularad hoc networks[C]. In Proceedings of IEEE Conference 2011:1125-1130.
[18] BONABEAU E,,DORIGO M,THERAULAZ Guy.Swarm
Intelligence:From Natural to Artificial Systems[J].Oxford University Press, USA, Sep.1999:123-128.