車載自組織網絡VANETs(Vehicular Ad Hoc Networks)具有節點密度分布不均、拓撲變化劇烈、鏈路間歇性中斷等特點。未來智能停車、無需交通燈、智能咨詢服務、車載視頻會議等將會頻頻出現，有廣泛應用前景。

      本文研究VANET地理機會路由，盡可能動態選擇沿著節點密度高、速度大的道路并利用無線傳輸，需要發送數據的節點積極與頻繁接觸、質量好、社會活躍性大的節點建立關系。為獲得良好的自適應效果，應該加強路口節點的預測計算能力、路由每一跳決策和學習實時網絡拓撲知識的能力。
1 相關工作
    參考文獻[1]提出GPSR(Greedy Perimeter Stateless Routing)，在路口無法處理路段節點密度大小問題，若沒有后續轉發節點則貪婪轉發失敗。
    參考文獻[2]提出 GeoDTN+Nav(Geographic DTN Routing with Navigator Prediction routing),通過三個指標計算節點的得分，判斷繼續邊界模式還是切換到攜帶模式，彌補了時斷網絡中GPSR協議節點空洞，但忽視了交通實時信息，路口的傳輸沒有很好的說明。
    參考文獻[3]提出GyTAR(Improved Greedy Traffic-aware Routing Protocol)，根據到目的地的剩余距離和車流量的變化動態序列化地選擇路口。
    參考文獻[4]提出MOVE(The Motion Vector Scheme)，仿真表明節點密度對算法性能影響明顯。
    參考文獻[5]使用信標探測機制感知報文存儲車輛節點周圍鏈路信息,以此為根據預測傳輸路徑性能并決定報文的轉發決策。
    參考文獻[6]提出根據節點的活躍度和相似度兩個指標得出綜合效用值，選擇節點傳輸數據包。
    參考文獻[7]提出VADD(Vehicle-Assisted Data Delivery)，在路口有兩種選路模式：L-VADD優先選取位置更靠近目的車輛；D-VADD優先選取朝目的方向移動的車輛。
    以往算法較少考慮車輛社會性規律(如節點接觸歷史和移動模式)的問題。城市中，熱點路段車輛密度較大、鄰居頻繁改變，節點質量Q用在一段時間T內在網絡中遇到不同節點的歷史平均數表示，數目越多表明節點質量越好，同時也間接反映節點所在路段密度。

3 路口各個指標計算和路由算法流程
    路由協議關鍵在一些參數決定路徑。本文在路口利用綜合效用值實時選擇高車流量的道路，有助于路由性能的提升。
3.1選路效用值的計算
    (1)距離因子D的計算方法
    鄰居列表保存著一跳范圍內的節點信息(位置、速度、方向)，并通過周期性發送HELLO消息來構建和更新。下式中Di是鄰居節點距離目的的距離，Dc是本節點到目的的距離,如圖3所示,鄰居距離目的越近，D越大。
　    
    (1)路口節點通過GPS獲取自己和鄰居的位置并根據式(1)計算距離D。
    (2)每個鄰居根據式(2)計算質量Q，并通過HELLO消息傳回路口節點。
    (3)路口節點獲取鄰居的Q并根據式(3)計算U。
    (4)在鄰居列表中查找是否有U大于當前節點的鄰居,
有，則將數據分組發送到具有最大U的鄰居節點。詳細過程如圖5所示。

4 仿真分析
    本文采用NS2.35[10]作為網絡仿真平臺，VanetMobiSim[11-12]模擬真實車輛行駛軌跡，如圖6所示，生成的腳本文件導入到NS-2搭建的網絡仿真場景中實現了聯合仿真。
    在1 000×1 000的拓撲內，固定節點數量為9，并部署路口靜態節點。隨機運動節點由6個開始，以步長5增加,在統計節點密度對性能影響時,節點速度分布為2 m/s~17 m/s(平均速度9.5 m/s)；在統計不同平均速度對協議影響時，拓撲節點數固定為25。在參數a、b分別取0.5時,QAOR與加入攜帶轉發機制的GPSR(buffer)協議進行對比，每次產生10次隨機場景取平均值。仿真參數配置如表1所示。

    圖6對比了QAOR和GPSR(buffer)的數據投遞率和時延。隨著節點數量的增加，協議數據投遞率均增加，圖6(a)顯示QAOR投遞率高于GPSR，因為它根據節點先前相遇節點數目多少預測路段的密度，讓數據包沿著鏈路質量好的路段傳輸，投遞率增加。從圖6(b)可以看出，隨著節點數量增加，道路車流密度增大，鏈路連接的概率增大，數據包傳輸時延減小,QAOR比GPSR(buffer)時延更低，因為選擇了車流密度大的道路減少了攜帶轉發的數據包的個數，而在路口GPSR根據距離無狀態地選擇下一跳，并不總是最優的。
    圖7是節點數一定的情況下(固定25個節點)平均速度對時延的影響, GPSR(buffer)選擇的路段節點密度小，缺少后續轉發節點，時延較大。相反QAOR時延卻顯著降低，因為它選擇了節點密度大的路段。同時,隨著平均速度越快，節點有更多機會遇到合適的下一跳，也縮短了通過車輛攜帶的時間。

     隨節點移動速度增加，投遞率增加，但受場景限制QAOR和GPSR(buffer)區別不明顯。仿真說明車輛速度大的路段能提高數據投遞率和降低時延。
    VANET道路拓撲的限制和時斷性給路由協議的設計帶來了挑戰，本文提出了攜帶轉發機制的GPSR在路口選擇下一跳的方法，利用反向車輛的歷史平均相遇節點數量間接提供路段車流密度，解決了GPSR這種無狀態協議在路口選擇下一跳時沒有后續節點的情況。仿真顯示QAOR具有較高的數據投遞率和較低的時延。后續將引入更加真實的交通信息流情況并對進一步結合道路全局信息計算連接度,加入鏈路斷裂預警機制，路口節點發送探測包等，選擇通信能力強的道路，并在大型拓撲場景協議中考察協議的性能表現。
參考文獻
[1] KARP B, KUNG H T. GPSR: greedy perimeterstateless routing for wireless networks[C].International Conference on Mobile Computing and Networking, New York:ACM Press,2000:243-254.
[2] CHENG P C,LEE K C, GERLA M, et al. GeoDTN+Nav:geographic DTN routing with navigator prediction for urban vehicular environments[J]. Mobile Networks and Applications, 2010,15(1):61-82.
[3] JERBI M, SENOUCI S M, RASHEED T, et al. Towards efficient geographic routing in urban vehicular networks[J]. IEEE Transactions on Vehicular Technology, 2009,58(9): 5048-5059.
[4] 肖德貴，彭李翔. 真實城市模擬環境下車載自組織網絡路由算法仿真研究[J]. 通信學報，2010,31(9A):68-72.
[5] 沈虎，王曉東, 周興銘,等.一種基于鏈路感知的VANET路由協議[J].軟件學報，2011,22(Suppl.(1)):157-164.
[6] 舒堅,董海星,劉琳嵐,等.機會網絡中基于移動特征的效用轉發協議[J]. 計算機應用研究，2012，29(4):1489-1492.
[7] ZHAO Jing, Cao Guohong.VADD:vehicle_assisted data delivery in vehicular Ad Hoc networks[J]. IEEE Transactions  on Vehicular Technology, 2008,57(3):1910-1922.
[8] 劉婧,王新華,王朕,等. VANET環境下基于歷史行為的消息路由方案[J].計算機應用,2012,2(32):359-362,366.
[9] Wang Guizhu, Wang Bingting, Gao Yongzhi. Dynamic spray and wait routing algorithm with auality of node in delay tolerant network[C].2010 International Conference on Communications and Mobile Computing(CMC),2010.4:452-456.
[10] TheNetworkSimulator-ns2.http://www.isi.edu/nsnam/ns/.
[11] Härri J, Fiore M, Fethi F, et al. VanetMobiSim: generating realistic mobility patterns for VANETs.[2006-09-26].http://vanet.eurecom.fr/.
[12] HEARRI J, FILALI F， BONEET C, et.al. Vanet Mobi  Sim:generating realistic mobility patternsfor vanets[C].Proceedings of the 3rdinternational workshop on Vehicular Ad  Hoc networks. ACM Press, 2006:96-97.