基于公交節點的VANET路由算法研究

王永福

摘要：城市公交車具有遍布街區道路、行駛線路固定等特點，VANET網絡中的數據分組傳輸可通過公交車自組織網絡實現，但公交車網絡能否在數據傳輸中發揮作用取決于對公交車運行規律的利用程度。提出一種公交車自組織網絡路由算法，該算法建立了公交節點數據傳輸模式，給出了路由選擇優化準則。與已有研究相比，該路由算法具有很好的數據分組投遞率和可靠性，能獲得高質量的數據傳輸路徑。實驗結果表明，該路由算法提高了數據分組投遞率，降低了數據分組傳輸延遲，具有較強的可伸縮性。

關鍵詞：VANET；路由算法；平均時延

DOIDOI：10.11907/rjdk.171668

中圖分類號：TP312文獻標識碼：A文章編號：16727800（2017）010007203

0引言

車載自組織網絡（Vehicular adhoc Network，VANET）是一種特殊的移動自組織網絡。VANET有兩種通信方式：車輛節點與路邊基礎設施（V2I）通信和車輛節點與車輛節點（V2V）間的通信[12]。車輛通信時路由選擇是VANET網絡的關鍵問題之一，其目的是找到源節點與目的節點間傳輸數據包的有效路徑。

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

1相關工作

VANET路由協議通常分為3類：基于拓撲結構的路由協議、基于地理位置的路由協議以及基于簇的路由協議，此外還有將幾種路由方案綜合在一起的混合路由算法[79]。對于一般的VANET路由協議，請參考文獻[10]。這里僅簡要闡述使用公交總線轉發數據包的算法。

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

在MIVANET結構[5]中，公交車起到數據傳輸的骨干作用。提出了一種兩層的MIVANET模型結構，將公共汽車作為消息傳播的移動骨干網。

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

定義2普通節點構成MIVANET模型的低層結構。當車輛節點要發送消息時，必須在一輛公交車節點上注冊。

在MIVANET模型中，路由機制是一種基于位置的算法，它假設車輛節點均勻分布在道路上，每條公交車線路都有一條包含所有公交線路信息的數字街道地圖。本文提出的方法即基于這種模型，但路由卻是基于拓撲結構的算法。

2城市交通特點

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

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

3BCR路由方案

本文提出一種基于表驅動的路由協議算法，將公共汽車作為移動主干網來轉發消息，稱為BCR，下面闡述具體步驟。

3.1鄰居節點發現過程

周期性廣播Hello消息，收到Hello消息的節點把發送節點注冊為其鄰居節點。在節點表中設置一個超時參數值并記錄相關鄰居節點信息。如果節點在一個超時周期內沒有收到從鄰居發來的任何Hello消息，就將該鄰居節點從列表中刪除。

3.2消息傳播機制

消息傳播過程中，包含鄰居鏈路信息的鏈路狀態分組（Link State Packet，LSP）將發送給網絡中的其它節點。該過程由兩部分組成：①處理LSP的完整性。當一個節點生成新的LSP后，必須通過廣播機制將其發送給所有節點。節點接收到該數據分組后，將其發送到除該分組的源節點之外的所有鄰居節點；②當節點檢測到鏈路發生變更時，每個離開鏈路的節點通過鏈路狀態數據包（LSP）將其離開的消息廣播到所有其它節點。這些LSP被洪泛到網絡中的所有節點。當每個節點接收到該信息時，將更新自己的網絡視圖。

3.3路由算法

該算法靈感來源于人工智能領域的規劃方法，具體闡述如下。

路線選擇4條準則：

準則1：如果網絡中的兩個節點B和節點C具有相同的鏈接，且鏈路狀態表也相似，則刪除兩個節點中的一個，如圖1所示。

準則2：如圖2所示，如果在一個節點的LS表中呈現的節點也呈現在另一個節點的LS表中，則刪除不會擴展任何新路由的那個節點。endprint

準則3：如果一個節點可從其它節點的LS表中組合生成其LS表，則將從LS表中刪除冗余的那個節點。如圖3所示，節點B可以與節點E和F通信，同時這兩個節點可通過A和C連通，所以刪除節點B不會影響路由。

準則4：如果一個節點只有一個鏈接節點，那么該節點將自動從LS表中刪除，這將簡化促進路由。如圖4所示，節點B將從LS表中刪除，因為它只有一個節點。

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

4路由性能評估

4.1仿真參數設置

仿真實驗使用NS2.35[18]。為了更好地評估本文所提算法性能，在相同的仿真場景下對經典的路由算法AODV和GSR算法加以實現，仿真環境設置如表1所示。對網絡拓撲進行多組實驗，抽取其中10次仿真結果并生成其平均值。

本文算法性能評估實驗，主要對數據包投遞率、端到端平均時延及平均鏈路持續時間進行分析比較。

4.2仿真結果分析

初始階段沒有路由表信息，致使開始過程中會有數據包丟失。如圖5所示，所有路由算法投遞率都低于60%，在節點數量較低時，網絡會出現分離現象，導致大量的數據包不能成功交付，故數據包投遞率最低。其中基于拓撲結構的AODV路由算法數據丟失率最高，因為AODV路由算法只考慮了城市環境中網絡的拓撲變化，沒有考慮VANET網絡節點特性。采用Dijkstra最短路徑算法進行路由選擇，隨著節點數量的增大，其數據投遞率也明顯下降。BCR則實現了最高的分組投遞率，因其考慮了VANET特征，當網絡節點密度增加時，借助公交車輛節點，明顯減少了網絡中參與路由節點數目，所以該算法在數據投遞率方面表現優異。

圖5數據投遞率

如圖6所示，與其它路由算法相比，BCR呈現最低的延遲，主要原因是與普通車輛節點相比，公交車的通信半徑范圍較大。此外，BCR的控制分組開銷較小，因為只有公交車發送數據包。當網絡中的節點從100增加到500時，其端到端平均時延從47ms增長到103ms。相比其它兩種路由算法，其性能表現最佳。

圖6端到端平均時延

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

圖7鏈路持續有效時間

5結語

在網絡規模較小時，本文所提出的BCR路由協議性能與其它兩種算法相差不大，但當網絡規模較大且節點數較多時，性能有明顯提升，這表明本文所提路由協議具有良好的擴展性。本文算法降低了網絡中端到端平均延遲，提高了數據分組投遞率，同時減少了城市環境中選定路由時節點的數量。

參考文獻參考文獻：

[1]常促宇，向勇，史美林.車載自組網的現狀與發展[J].通信學報，2007，28（11）：116126.

[2]鄭少仁，王海濤，趙志峰.Ad Hoc網絡技術[M].北京：人民郵電出版社，2005.

[3]劉業，吳國新.基于802.11p/WAVE的車聯網連通性模型及其應用研究[J].通信學報，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中路由協議分析[J].通信學報，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.

責任編輯（責任編輯：杜能鋼）endprint