王廣彧，劉春鳳，2，趙增華，舒炎泰

(1.天津大學計算機科學與技術學院，天津 300072;2.天津市認知計算與應用重點實驗室，天津 300072)

1 概述

車載自組織網絡(Vehicular Ad Hoc Network，VANET)依靠安裝無線通信設備的車輛進行數據傳輸，能夠提供互聯網移動接入、輔助駕駛、事故預警等應用［1-2］，是智能交通系統(tǒng)的重要組成部分，近年來受到工業(yè)界和國內外科研院所的普遍關注。作為一種特殊的移動自組織網絡(Mobile Ad Hoc Networks，MANET)，VANET 節(jié)點受道路狀況、交通機制的影響，具有高速移動、分布不均等特征［3-5］，造成通信時間短、鏈路頻繁斷裂、鏈路容量受限，使得車輛之間的高效數據傳輸面臨極大的挑戰(zhàn)。

現有的VANET 路由算法大致分為2 類:地理位置路由和容遲網絡(Delay Tolerant Network，DTN)路由。GPSR (Greedy Perimeter Stateless Routing)［6］是一種典型的地理位置路由算法，將分組轉發(fā)給在地理位置上更靠近目的節(jié)點的鄰居。在連通性較好的網絡中，地理位置路由的分組投遞率較高且時延較低，但在連通性較差的網絡中，分組在多跳之后往往找不到合適的轉發(fā)節(jié)點而被丟棄，網絡的整體投遞率很低。另一類路由算法，如文獻［3］算法，借助于DTN 網絡存儲-攜帶-轉發(fā)的思想，來實現非連通區(qū)域的數據傳輸，解決車載網絡在間歇連通和低密度情況下的數據傳輸問題。這類算法在稀疏網絡中可以提升分組投遞率，但分組的端到端時延一般較高。混合路由算法如Geo+DTN［7］結合了地理位置路由在連通性較好網絡中低時延和DTN 路由在連通性較差網絡中高投遞率的特點。但Geo+DTN 完全依賴導航系統(tǒng)提供車輛位置或軌跡信息，靈活性較差，其DTN 模式只是簡單的存儲-攜帶，直到可以轉回貪婪轉發(fā)模式，未充分利用位置信息做出更優(yōu)的轉發(fā)決策。

本文針對城市車載自組織網絡場景中地理位置路由和DTN 路由的不足，及車載網絡路由算法在獲取車輛位置信息方面的局限性，提出一種適用于城市場景的、基于卡爾曼預測的混合路由算法KPHR。該算法利用卡爾曼濾波對車輛位置進行實時預測來輔助路由計算。在GPSR 算法的基礎上，結合容遲網絡(DTN)路由存儲-攜帶-轉發(fā)的思想，在貪婪模式或邊緣模式中，當無轉發(fā)節(jié)點時，切換至DTN 模式存儲攜帶分組;在DTN 模式中，利用位置信息選擇合適的轉發(fā)節(jié)點，當網絡連通時，切換至貪婪轉發(fā)模式。

2 基于卡爾曼濾波的車輛實時位置預測

車輛實時位置在VANET 數據傳輸協議設計中扮演著重要角色。地理位置路由通常面臨轉發(fā)決策所使用的位置信息時效性較低的問題［8］。如圖1 所示(白色節(jié)點表示節(jié)點S 記錄的鄰居節(jié)點的歷史位置，黑色節(jié)點表示節(jié)點的實際位置)，S 根據歷史位置信息選擇A 節(jié)點作為目的為D 的下一跳節(jié)點，但A 此時已離開S 的通信范圍移動至A'。S 將選擇B 作為下一跳，但實際上C 為當前距離D 最近的節(jié)點。

圖1 地理位置路由中位置信息示意圖

目前在VANET 路由算法中，常用2 種方法獲取車輛位置信息:(1)利用導航系統(tǒng)獲知一條預先設定好的車輛運行軌跡，如Geo +DTN 和GeOpps［9］。這種方法的缺陷是，導航系統(tǒng)給出的行進路線通常不是最優(yōu)路線，而且司機必須沿著該固定線路行駛。另外，GPS 的可用性和精度問題往往被忽視［10］。(2)基于一定的運動模型進行假設或推測，如AGF［11］。由于運動模型的固有缺陷，這種方法得到的預測精度往往很低，對路由決策的幫助有限，因此使用卡爾曼預測器進行高精度車輛位置預測的方法輔助路由協議。

卡爾曼預測器是Kalman 提出的遞歸預測器［12］，用于從一系列噪聲中遞歸地估計線性離散系統(tǒng)的狀態(tài)［13］?？柭A測器無需考慮多個過去的輸出信號，其原理是通過現時狀態(tài)觀測值Yk修正現時狀態(tài)預測值，根據修正結果來預測下一時刻狀態(tài)預測值Xk+1，保證其同下一時刻狀態(tài)實際值的均方誤差最小。

考慮一個給定初始狀態(tài)為X0的離散時間動態(tài)系統(tǒng):

其中，wk和vk是獨立白噪聲過程，在k 時刻對應的協方差矩陣為Qk和Rk。

遞歸的卡爾曼預測方程為:

預測修正系數為:

預測均方誤差為:

為預測車輛位置，假設網絡中的每一輛車都裝備了GPS 接收器，從而可知自身當前的位置。車輛運動可以描述為由二維位置Pos=［x y］T和速度向量Vel=［vxvy］T組成的狀態(tài)向量X=［x y vxvy］T?？梢钥闯觯瑒討B(tài)狀態(tài)方程即是一個航位推演過程，預測器用同一時刻GPS 接收值即觀測值來對推演結果進行修正。在實際計算中，由于動態(tài)模型不夠精確描述真實運動過程、隨時間累積增加的取整誤差等原因，狀態(tài)預測誤差可能會變得很大。卡爾曼預測的結果可以認為是觀測模型新測量值和基于先前所有舊測量值的預測之間的權重調節(jié)值。為提高預測精度，達到降低舊信息的權重、提高新測量值的權重，采用記憶衰減法，給預測均方差矩陣P 乘以一個衰減因子S ＞1。

為驗證卡爾曼預測車輛位置的精度，利用真實車輛軌跡計算其預測位置，并衡量預測位置與真實位置的誤差。實驗結果如表1 所示。約有99%的預測誤差小于30 m，遠小于車輛的通信范圍距離，這保證了基于卡爾曼預測的位置信息的可用性。

表1 卡爾曼預測精確度測試結果

3 基于卡爾曼預測的混合路由

在地理位置路由GPSR 的基礎上，結合DTN 路由在稀疏網絡中數據傳輸的優(yōu)點，提出一種基于位置預測的混合路由算法KPHR。KPHR 是一種地理位置路由和DTN 路由的混合路由算法，可以在城市場景中高效的工作。KPHR 有和GPSR 類似的貪婪模式和邊緣模式。除此之外，基于卡爾曼預測器的車輛位置預測和鏈路調度感知緩存保證了KPHR 在城市場景中具有高效性。

3.1 假設

假設每一個節(jié)點都裝備了導航系統(tǒng)來獲取自己的位置和速度，發(fā)送節(jié)點可以通過位置服務獲知目的節(jié)點的位置和速度，節(jié)點會周期性廣播HELLO 分組發(fā)現鄰居節(jié)點。

3.2 車輛實時位置預測

網絡中每個節(jié)點設置如第2 節(jié)所述的卡爾曼預測器。源節(jié)點通過位置發(fā)現服務獲得目的節(jié)點的位置信息Pos 和速度信息Vel。節(jié)點發(fā)送的數據分組和HELLO 分組中帶有本節(jié)點的位置信息、速度信息以及發(fā)送時間。每個節(jié)點上的卡爾曼預測器利用這些信息，周期性地計算其目標節(jié)點和鄰居節(jié)點在當前時刻的預測位置和速度向量。在接下來的轉發(fā)決策中，任何要求位置和速度信息的計算，都使用卡爾曼預測器計算結果，這樣可以有效解決節(jié)點運動信息在路由決策中時效性低的問題。

3.3 鏈路調度感知的分組緩存

城市場景中節(jié)點分布極其不均，發(fā)送節(jié)點和目的節(jié)點常處于不同網絡劃分中，造成數據不可達，可以借助于DTN 網絡存儲-攜帶-轉發(fā)的概念克服該問題。在每個節(jié)點設置一個FIFO 隊列來緩存那些由于缺乏合適轉發(fā)鄰居而將要被丟棄的分組。每個分組維護一個計時器來標明在隊列中的生存時間。緩存隊列會周期性檢查分組計時器并丟棄超時分組。

每當節(jié)點遇見一個新鄰居節(jié)點，就計算從該鄰居到目的節(jié)點的距離distnb和角度θnb，以及從本節(jié)點到目的節(jié)點的距離distn和角度θn。定義傳輸增益為θn與θnb之間的差和distn與distnb之間的差權重之后的和。較高的傳輸增益表明該分組有更高的概率傳輸至目的節(jié)點。節(jié)點按照傳輸增益將緩存中的分組按降序排序，并依次發(fā)送給鄰居節(jié)點直至傳輸增益為負。節(jié)點鄰居發(fā)現過程的偽代碼具體如下:

3.4 KPHR 轉發(fā)策略

當節(jié)點收到一個分組時，首先檢查該分組的目的節(jié)點是否在自己的鄰居表中。這會大大減輕目的節(jié)點離開初始位置的影響。然后節(jié)點會采用與GPSR 算法的貪婪模式和邊緣模式類似的規(guī)則處理該分組。該步驟所使用的節(jié)點位置和速度的計算都使用預測值，具體轉發(fā)策略如下:

(1)節(jié)點檢查自身是否是目的節(jié)點。如果是，則節(jié)點接收該分組。

(2)否則節(jié)點檢查該分組的目的節(jié)點是否是當前節(jié)點的一個鄰居。如果是，當前節(jié)點發(fā)送該分組至目的節(jié)點。

(3)否則節(jié)點檢查該分組的轉發(fā)模式(貪婪模式或邊緣模式)，并依照相應的轉發(fā)策略計算下一跳節(jié)點。如果下一跳節(jié)點存在，當前節(jié)點發(fā)送該分組至下一跳節(jié)點。

(4)否則將該分組存入緩存隊列。當遇見一個新的鄰居節(jié)點時，按照3.3 節(jié)所述的節(jié)點發(fā)現過程進行轉發(fā)。

4 性能分析

本節(jié)將KPHR 的性能和GPSR、帶緩存的GPSR(GPSR+buffer)進行比較，使用分組投遞率和平均端到端時延作為算法性能評價指標。GPSR 是一種典型的地理位置路由。GPSR+buffer 是在GPSR 的邊緣模式下加入緩存，在貪婪模式或邊緣模式下無法計算出下一跳節(jié)點時將分組存入緩存，直到能夠使用貪婪模式進行轉發(fā)為止，是一種簡單的混合路由算法。本文使用開源的真實車輛交通生成器VanetMobiSim 生成真實車輛移動軌跡。利用TIGER (U.S.Census Bureau's Topologically Integrated Geographic Encoding and Referencing)數據庫中的真實地圖拓撲，選取蒙哥馬利郡的一塊2 000 m ×1 000 m 的街區(qū)，使該拓撲可以在NS-2中使用。設置20 條CBR 流并隨機選取發(fā)送節(jié)點和目的節(jié)點。發(fā)送節(jié)點在仿真開始30 s 后開始持續(xù)發(fā)送60 s 數據。在所有分組發(fā)送后，仿真仍將運行一段時間避免出現因仿真時間結束而分組未達的狀況。對任一特定的網絡場景設置，均采用5 個不同的隨機種子進行仿真，最終結果取平均值，具體仿真參數設置如表2 所示。

表2 仿真參數設置

圖2 對比了節(jié)點移動速度為20 km/h～50 km/h時，不同節(jié)點數目下GPSR，GPSR +buffer 和KPHR的分組投遞率。3 種算法各自的分組投遞率開始都隨著節(jié)點數目的增加而增長，直到節(jié)點數目為150時出現下降。這是因為網絡的鏈路容量有限，節(jié)點之間的控制分組開銷過大，造成網絡擁塞。因為有分組緩存的存在，任意節(jié)點數目下KPHR 和GPSR+buffer 的分組投遞率都高于GPSR。但GPSR +buffer 在DTN 階段時只是簡單地按貪婪條件選取轉發(fā)節(jié)點;而KPHR 充分利用了節(jié)點位置信息計算投遞增益，可以選擇更合適的節(jié)點進行轉發(fā)，從而提升網絡整體效率，因而投遞率遠高于只有簡單緩存功能的GPSR+buffer。另外，KPHR 在每跳中都會判斷目的節(jié)點是否在當前節(jié)點的鄰居表內，從而減輕因目的節(jié)點移動遠離初始位置造成不可達的影響，也可以提升分組投遞率。

圖2 不同節(jié)點數量下的分組投遞率

圖3、圖4 分別對比了節(jié)點數目為100 時，不同節(jié)點運動速度下3 種算法的平均端到端時延和分組投遞率?？梢钥闯鲭S著節(jié)點運動速度的增加，3 種算法各自的平均端到端時延都有所增加，而分組投遞率都有所降低。與GPSR+buffer 相比，KPHR 的平均端到端時延相差不大，但增長更緩慢。而任意節(jié)點運動速度下，KPHR 的分組投遞率遠高于GPSR 和GPSR+buffer。

圖3 不同節(jié)點運動速度下的平均端到端時延

圖4 不同節(jié)點運動速度下的分組投遞率

5 結束語

本文針對VANET 城市場景中，道路拓撲限制和車輛高速移動導致的網絡間歇連通性給路由設計帶來的巨大挑戰(zhàn)，綜合考慮了地理位置路由在連通網絡中端到端時延較低、DTN 路由在稀疏網絡中投遞率較高的優(yōu)點，結合卡爾曼預測器的位置預測，充分利用車輛地理位置輔助轉發(fā)決策，在GPSR 的基礎上提出基于卡爾曼預測的混合路由算法KPHR。仿真結果表明，與GPSR 和GPSR +buffer 相比，KPHR在分組投遞率和端到端時延方面性能較好。下一步工作將考慮網絡連通性的影響，對網絡連通性進行建模研究分析，優(yōu)化地理位置路由模式和DTN 模式之間的切換點，進一步改善VANET 的傳輸性能。

［1］徐會彬，夏 超.VANETs 路由綜述［J］.計算機應用研究，2013，30(1):1-6.

［2］Gerla M，Kleinrock L.Vehicular Networks and the Future of the Mobile Internet［J］.Computer Networks，2011，55(2):457-469.

［3］Wu Yuchen，Zhu Yanmin，Li Bo.Trajectory Improves Data Delivery in Vehicular Networks［C］//Proceedings of INFOCOM'11.Shanghai，China:［s.n.］，2011:2183-2191.

［4］Lee K，Yi Yung，Jeong J，et al.Max-contribution:On Optimal Resource Allocation in Delay Tolerant Networks［C］// Proceedings of INFOCOM'10.［S.l.］:IEEE Press，2010:1-9.

［5］Zhu Hongzi，Chang Shan，Li Minglu，et al.Exploiting Temporal Dependency for Opportunistic Forwarding in Urban Vehicular Networks［C］//Proceedings of INFOCOM'11.［S.l.］:IEEE Press，2011:2192-2200.

［6］Karp B，Kung H T.GPSR:Greedy Perimeter Stateless Routing for Wireless Networks［C］//Proceedings of the 6th Annual International Conference on Mobile Computing and Networking.New York，USA:ACM Press，2000:243-254.

［7］Cheng P C，Weng J T，Tung L C，et al.GeoDTN +Nav:A Hybrid Geographic and DTN Routing with Navigation Assistance in Urban Vehicular Networks［J］.Mobile Networks and Applications，2010，15(1):61-82.

［8］Kim Y，Lee J J，Helmy A.Impact of Location Inconsistencies on Geographic Routing in Wireless Networks［C］//Proceedings of the 6th ACM International Workshop on Modeling Analysis and Simulation of Wireless and Mobile Systems.San Diego，USA:ACM Press，2003:124-127.

［9］Leontiadis I，Mascolo C.Geopps:Geographical Opportunistic Routing for Vehicular Networks［C］//Proceedings of IEEE International Symposium on World of Wireless，Mobile and Multimedia Networks.［S.l.］:IEEE Press，2007:1-6.

［10］Leontiadis I，Costa P，Mascolo C.Extending Access Point Connectivity Through Opportunistic Routing in Vehicular Networks［C］//Proceedings of INFOCOM'10.［S.l.］:IEEE Press，2010:1-5.

［11］Naumov V，Baumann R，Gross T.An Evaluation of Intervehicle Ad Hoc Networks Based on Realistic Vehicular Traces［C］//Proceedings of the 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing.Florence，Italy:ACM Press，2006:108-119.

［12］Kalman R E.A New Approach to Linear Filtering and Prediction Problems［J］.Journal of Basic Engineering，1960，82(1):35-45.

［13］Moghaddam B A，Haleh H，Ebrahimijam S.Forecasting Trend and Stock Price with Adaptive Extended Kalman Filter Data Fusion［C］//Proceedings of IEEE International Conference on Economics and Finance Research.Singapore:［s.n.］，2011:119-123.