基于公交節(jié)點(diǎn)的VANET路由算法研究

王永福

摘要：城市公交車具有遍布街區(qū)道路、行駛線路固定等特點(diǎn)，VANET網(wǎng)絡(luò)中的數(shù)據(jù)分組傳輸可通過公交車自組織網(wǎng)絡(luò)實(shí)現(xiàn)，但公交車網(wǎng)絡(luò)能否在數(shù)據(jù)傳輸中發(fā)揮作用取決于對公交車運(yùn)行規(guī)律的利用程度。提出一種公交車自組織網(wǎng)絡(luò)路由算法，該算法建立了公交節(jié)點(diǎn)數(shù)據(jù)傳輸模式，給出了路由選擇優(yōu)化準(zhǔn)則。與已有研究相比，該路由算法具有很好的數(shù)據(jù)分組投遞率和可靠性，能獲得高質(zhì)量的數(shù)據(jù)傳輸路徑。實(shí)驗(yàn)結(jié)果表明，該路由算法提高了數(shù)據(jù)分組投遞率，降低了數(shù)據(jù)分組傳輸延遲，具有較強(qiáng)的可伸縮性。

關(guān)鍵詞：VANET；路由算法；平均時(shí)延

DOIDOI：10.11907/rjdk.171668

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：16727800（2017）010007203

0引言

車載自組織網(wǎng)絡(luò)（Vehicular adhoc Network，VANET）是一種特殊的移動(dòng)自組織網(wǎng)絡(luò)。VANET有兩種通信方式：車輛節(jié)點(diǎn)與路邊基礎(chǔ)設(shè)施（V2I）通信和車輛節(jié)點(diǎn)與車輛節(jié)點(diǎn)（V2V）間的通信[12]。車輛通信時(shí)路由選擇是VANET網(wǎng)絡(luò)的關(guān)鍵問題之一，其目的是找到源節(jié)點(diǎn)與目的節(jié)點(diǎn)間傳輸數(shù)據(jù)包的有效路徑。

本文提出一種基于拓?fù)浣Y(jié)構(gòu)的路由算法（BCR），該路由算法將公共汽車總線作為移動(dòng)骨干網(wǎng)。公共汽車作為城市環(huán)境下的特殊節(jié)點(diǎn)具有獨(dú)特優(yōu)勢：①與普通汽車相比具有較低的運(yùn)行速度；②城市環(huán)境下公共汽車數(shù)量有限；③公共汽車的運(yùn)行線路固定，其運(yùn)行軌跡可循[34]。本文路由算法將公交總線作為網(wǎng)絡(luò)的移動(dòng)骨干網(wǎng)，采用MIVANET架構(gòu)[5]，選擇具有最少節(jié)點(diǎn)數(shù)的路徑，減少了端到端的平均時(shí)延，增加了網(wǎng)絡(luò)中數(shù)據(jù)包投遞率，同時(shí)減少了目的節(jié)點(diǎn)數(shù)量。與傳統(tǒng)的基于距離矢量（AODV）路由協(xié)議[6]相比，本文算法減少了傳輸數(shù)據(jù)時(shí)控制分組的數(shù)量，提高了城市環(huán)境下路由的整體性能。采用仿真軟件NS2模擬實(shí)驗(yàn)表明，相比于VANET中現(xiàn)有的AODV路由協(xié)議算法，本算法在數(shù)據(jù)投遞率和平均延遲方面都得到顯著改善。

1相關(guān)工作

VANET路由協(xié)議通常分為3類：基于拓?fù)浣Y(jié)構(gòu)的路由協(xié)議、基于地理位置的路由協(xié)議以及基于簇的路由協(xié)議，此外還有將幾種路由方案綜合在一起的混合路由算法[79]。對于一般的VANET路由協(xié)議，請參考文獻(xiàn)[10]。這里僅簡要闡述使用公交總線轉(zhuǎn)發(fā)數(shù)據(jù)包的算法。

文獻(xiàn)[11]提出了基于上海地圖的公交網(wǎng)絡(luò)方案。通過使用公交線路時(shí)間表、公交線路信息等，對其進(jìn)行時(shí)空模式建模。公交網(wǎng)絡(luò)路由算法類似于VANET中的混合路由算法[1213]。文獻(xiàn)[14]對AODV路由協(xié)議進(jìn)行了修改，提出一種公交車AODV路由協(xié)議（BCR）。BCR路由協(xié)議選擇的公交線路數(shù)相對較少，但由于周期性廣播消息而導(dǎo)致額外的帶寬消耗。文獻(xiàn)[15]中，將公交車作為所有道路的中繼節(jié)點(diǎn)，研究了公交車輔助車載自組織網(wǎng)絡(luò)的組播能力。

在MIVANET結(jié)構(gòu)[5]中，公交車起到數(shù)據(jù)傳輸?shù)墓歉勺饔?。提出了一種兩層的MIVANET模型結(jié)構(gòu)，將公共汽車作為消息傳播的移動(dòng)骨干網(wǎng)。

定義1每個(gè)公交車配備有兩種無線接口。低層用于與普通節(jié)點(diǎn)間通信。用于公交車節(jié)點(diǎn)內(nèi)部專用通信，信道上具有較大的傳輸范圍。

定義2普通節(jié)點(diǎn)構(gòu)成MIVANET模型的低層結(jié)構(gòu)。當(dāng)車輛節(jié)點(diǎn)要發(fā)送消息時(shí)，必須在一輛公交車節(jié)點(diǎn)上注冊。

在MIVANET模型中，路由機(jī)制是一種基于位置的算法，它假設(shè)車輛節(jié)點(diǎn)均勻分布在道路上，每條公交車線路都有一條包含所有公交線路信息的數(shù)字街道地圖。本文提出的方法即基于這種模型，但路由卻是基于拓?fù)浣Y(jié)構(gòu)的算法。

2城市交通特點(diǎn)

城市交通環(huán)境下車輛節(jié)點(diǎn)特征：普通車輛約占全部汽車的80%，公交車所占不到20%。公共汽車路線規(guī)則，與出租車和私家車相比，其運(yùn)行速度較慢，它們之間很容易建立通信。

選擇5條公交線路的區(qū)域路段研究公交線路特征。每條線路的公交車發(fā)車時(shí)間間隔約為10min。每條道路有兩個(gè)方向，兩條相鄰公交車之間的平均時(shí)間約為10/5/2=1min。假設(shè)隨機(jī)乘坐10輛公交車，公交車的最高行駛速度約為40km/h。由于公交車站臺(tái)和交通信號(hào)燈的頻繁變化，其平均車速僅為15km/h，因而網(wǎng)絡(luò)中的公共汽車可以保持良好連通狀態(tài)。

3BCR路由方案

本文提出一種基于表驅(qū)動(dòng)的路由協(xié)議算法，將公共汽車作為移動(dòng)主干網(wǎng)來轉(zhuǎn)發(fā)消息，稱為BCR，下面闡述具體步驟。

3.1鄰居節(jié)點(diǎn)發(fā)現(xiàn)過程

周期性廣播Hello消息，收到Hello消息的節(jié)點(diǎn)把發(fā)送節(jié)點(diǎn)注冊為其鄰居節(jié)點(diǎn)。在節(jié)點(diǎn)表中設(shè)置一個(gè)超時(shí)參數(shù)值并記錄相關(guān)鄰居節(jié)點(diǎn)信息。如果節(jié)點(diǎn)在一個(gè)超時(shí)周期內(nèi)沒有收到從鄰居發(fā)來的任何Hello消息，就將該鄰居節(jié)點(diǎn)從列表中刪除。

3.2消息傳播機(jī)制

消息傳播過程中，包含鄰居鏈路信息的鏈路狀態(tài)分組（Link State Packet，LSP）將發(fā)送給網(wǎng)絡(luò)中的其它節(jié)點(diǎn)。該過程由兩部分組成：①處理LSP的完整性。當(dāng)一個(gè)節(jié)點(diǎn)生成新的LSP后，必須通過廣播機(jī)制將其發(fā)送給所有節(jié)點(diǎn)。節(jié)點(diǎn)接收到該數(shù)據(jù)分組后，將其發(fā)送到除該分組的源節(jié)點(diǎn)之外的所有鄰居節(jié)點(diǎn)；②當(dāng)節(jié)點(diǎn)檢測到鏈路發(fā)生變更時(shí)，每個(gè)離開鏈路的節(jié)點(diǎn)通過鏈路狀態(tài)數(shù)據(jù)包（LSP）將其離開的消息廣播到所有其它節(jié)點(diǎn)。這些LSP被洪泛到網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。當(dāng)每個(gè)節(jié)點(diǎn)接收到該信息時(shí)，將更新自己的網(wǎng)絡(luò)視圖。

3.3路由算法

該算法靈感來源于人工智能領(lǐng)域的規(guī)劃方法，具體闡述如下。

路線選擇4條準(zhǔn)則：

準(zhǔn)則1：如果網(wǎng)絡(luò)中的兩個(gè)節(jié)點(diǎn)B和節(jié)點(diǎn)C具有相同的鏈接，且鏈路狀態(tài)表也相似，則刪除兩個(gè)節(jié)點(diǎn)中的一個(gè)，如圖1所示。

準(zhǔn)則2：如圖2所示，如果在一個(gè)節(jié)點(diǎn)的LS表中呈現(xiàn)的節(jié)點(diǎn)也呈現(xiàn)在另一個(gè)節(jié)點(diǎn)的LS表中，則刪除不會(huì)擴(kuò)展任何新路由的那個(gè)節(jié)點(diǎn)。endprint

準(zhǔn)則3：如果一個(gè)節(jié)點(diǎn)可從其它節(jié)點(diǎn)的LS表中組合生成其LS表，則將從LS表中刪除冗余的那個(gè)節(jié)點(diǎn)。如圖3所示，節(jié)點(diǎn)B可以與節(jié)點(diǎn)E和F通信，同時(shí)這兩個(gè)節(jié)點(diǎn)可通過A和C連通，所以刪除節(jié)點(diǎn)B不會(huì)影響路由。

準(zhǔn)則4：如果一個(gè)節(jié)點(diǎn)只有一個(gè)鏈接節(jié)點(diǎn)，那么該節(jié)點(diǎn)將自動(dòng)從LS表中刪除，這將簡化促進(jìn)路由。如圖4所示，節(jié)點(diǎn)B將從LS表中刪除，因?yàn)樗挥幸粋€(gè)節(jié)點(diǎn)。

算法步驟如下：定義S表示源節(jié)點(diǎn)，D表示目的節(jié)點(diǎn)，表示節(jié)點(diǎn)S的LS表，為路由表。在初始狀態(tài)下，W=，C=φ，路徑長度為零，節(jié)點(diǎn)S的路由表中無其它節(jié)點(diǎn)信息。假設(shè)D∈，則當(dāng)Di時(shí)，對于W里面的每個(gè)節(jié)點(diǎn)Ni，如果Ni是Nj的鄰居節(jié)點(diǎn)，同時(shí)Ni且Nj∈，則有C=C∪{Ni}，此時(shí)W=W-C。對于C中的每個(gè)節(jié)點(diǎn)Ni，C=C-Ni。如果Ni沒被準(zhǔn)則1、準(zhǔn)則2及準(zhǔn)則3刪除，則將Ni節(jié)點(diǎn)添加到中，并將網(wǎng)絡(luò)路徑長度k加1。k表示路徑長度，當(dāng)k>0、Ni可從中刪除時(shí)，則通過刪除Ni更新，同時(shí)路徑長度k減1。

4路由性能評估

4.1仿真參數(shù)設(shè)置

仿真實(shí)驗(yàn)使用NS2.35[18]。為了更好地評估本文所提算法性能，在相同的仿真場景下對經(jīng)典的路由算法AODV和GSR算法加以實(shí)現(xiàn)，仿真環(huán)境設(shè)置如表1所示。對網(wǎng)絡(luò)拓?fù)溥M(jìn)行多組實(shí)驗(yàn)，抽取其中10次仿真結(jié)果并生成其平均值。

本文算法性能評估實(shí)驗(yàn)，主要對數(shù)據(jù)包投遞率、端到端平均時(shí)延及平均鏈路持續(xù)時(shí)間進(jìn)行分析比較。

4.2仿真結(jié)果分析

初始階段沒有路由表信息，致使開始過程中會(huì)有數(shù)據(jù)包丟失。如圖5所示，所有路由算法投遞率都低于60%，在節(jié)點(diǎn)數(shù)量較低時(shí)，網(wǎng)絡(luò)會(huì)出現(xiàn)分離現(xiàn)象，導(dǎo)致大量的數(shù)據(jù)包不能成功交付，故數(shù)據(jù)包投遞率最低。其中基于拓?fù)浣Y(jié)構(gòu)的AODV路由算法數(shù)據(jù)丟失率最高，因?yàn)锳ODV路由算法只考慮了城市環(huán)境中網(wǎng)絡(luò)的拓?fù)渥兓?，沒有考慮VANET網(wǎng)絡(luò)節(jié)點(diǎn)特性。采用Dijkstra最短路徑算法進(jìn)行路由選擇，隨著節(jié)點(diǎn)數(shù)量的增大，其數(shù)據(jù)投遞率也明顯下降。BCR則實(shí)現(xiàn)了最高的分組投遞率，因其考慮了VANET特征，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)密度增加時(shí)，借助公交車輛節(jié)點(diǎn)，明顯減少了網(wǎng)絡(luò)中參與路由節(jié)點(diǎn)數(shù)目，所以該算法在數(shù)據(jù)投遞率方面表現(xiàn)優(yōu)異。

圖5數(shù)據(jù)投遞率

如圖6所示，與其它路由算法相比，BCR呈現(xiàn)最低的延遲，主要原因是與普通車輛節(jié)點(diǎn)相比，公交車的通信半徑范圍較大。此外，BCR的控制分組開銷較小，因?yàn)橹挥泄卉嚢l(fā)送數(shù)據(jù)包。當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)從100增加到500時(shí)，其端到端平均時(shí)延從47ms增長到103ms。相比其它兩種路由算法，其性能表現(xiàn)最佳。

圖6端到端平均時(shí)延

圖7表明，在節(jié)點(diǎn)數(shù)量較少的情況下，AODV算法和GSR具有更長的鏈路持續(xù)時(shí)間，但是隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增加，AODV路由算法的鏈路有效時(shí)間急劇下降，而GSR基于地理位置，所以相對來說較為穩(wěn)定。本文的BCR雖不及前兩種算法，但隨著網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)量的增加，其變化平緩，性能穩(wěn)定，因而能更好地適應(yīng)車輛節(jié)點(diǎn)數(shù)目巨大的城市環(huán)境。

圖7鏈路持續(xù)有效時(shí)間

5結(jié)語

在網(wǎng)絡(luò)規(guī)模較小時(shí)，本文所提出的BCR路由協(xié)議性能與其它兩種算法相差不大，但當(dāng)網(wǎng)絡(luò)規(guī)模較大且節(jié)點(diǎn)數(shù)較多時(shí)，性能有明顯提升，這表明本文所提路由協(xié)議具有良好的擴(kuò)展性。本文算法降低了網(wǎng)絡(luò)中端到端平均延遲，提高了數(shù)據(jù)分組投遞率，同時(shí)減少了城市環(huán)境中選定路由時(shí)節(jié)點(diǎn)的數(shù)量。

參考文獻(xiàn)參考文獻(xiàn)：

[1]常促宇，向勇，史美林.車載自組網(wǎng)的現(xiàn)狀與發(fā)展[J].通信學(xué)報(bào)，2007，28（11）：116126.

[2]鄭少仁，王海濤，趙志峰.Ad Hoc網(wǎng)絡(luò)技術(shù)[M].北京：人民郵電出版社，2005.

[3]劉業(yè)，吳國新.基于802.11p/WAVE的車聯(lián)網(wǎng)連通性模型及其應(yīng)用研究[J].通信學(xué)報(bào)，2013，34（6）：8591.

[4]LUO J， GU X， Zhao T， et al.Mivanet： a new mobile infrastructure based vanet architecture for urban environment[C]. In： 2010 IEEE 72nd Vehicular Technology Conference Fall （VTC 2010Fall），2010：15.

[5]MOSTAFA A， VEGNI A M， AGRAWAL D P. A probabilistic routing by using multihop retransmission forecast with packet collisionaware constraints in vehicular networks[J]. Ad Hoc Networks，2014，14（3）：118129.

[6]PERKINS C， BELDINGROYER E， DAS S. Rfc 3561ad hoc ondemand distance vector （aodv） routing[C]. In： Internet RFCs，2003：138.

[7]CHENG P， WENG J， TUNG L， et al.GeoDTN+NAV： a hybrid geographic and dtn routing with navigation assistance in urban vehicular networks[C]. In： MobiQuitous/ISVCS，2008.

[8]LI F， ZHAO L， FAN X， et al.Hybrid positionbased and dtn forwarding for vehicular sensor networks[J]. International Journal of Distributed Sensor Networks，2012（6）：152158.endprint

[9]ZHAO L， LI F， WANG Y.Hybrid positionbased and dtn forwarding in vehicular ad hoc networks[C]. In： 2012 IEEE Vehicular Technology Conference （VTC Fall），2012：15.

[10]吳振華，胡鵬.VANET中路由協(xié)議分析[J].通信學(xué)報(bào)，2015，36（Z1）：7584.

[11]SEDE M， LI X， LI D， et al. Routing in largescale buses ad hoc networks[C]. In： IEEE Wireless Communications and Networking Conference，WCNC 2008：27112716.

[12]VAHDAT A， BECKER D.Epidemic routing for partially connected ad hoc networks[R]. Technical report， Technical Report CS200006， Duke University，2000.

[13]PARK H， JANG H， LEE S， et al.Positionbased dtn routing in metropolitan bus network[C]. In： 2012 International Conference on Systems and Informatics （ICSAI），2012：14491453.

[14]Al JANABI F， YASEEN Y， ASKWITHB.The bus ad hoc ondemand distance vector （BAODV） routing protocol[C]. In： Proc. of Annual Post Graduate Symposium on the Convergence of Telecommunications， Networking and Broadcasting， PGNet 2012.

[15]HUAN Y， GUAN X， CAI Z，et al.Multicast capacity analysis for socialproximity urban busassisted vanets[C]. In： 2013 IEEE International Conference on Communications （ICC），2013：61386142.

[16]The Network simulatorns2[EB/OL].http：//www.isi.edu/nsnam/ns.

責(zé)任編輯（責(zé)任編輯：杜能鋼）endprint