基于實時道路信息感知的VANET路由算法

陳潘航，周宏偉

(1.杭州電子科技大學 計算機學院，浙江 杭州 310018；2.泰瑞機器股份有限公司，浙江 杭州 310018)

0 引 言

車輛網是實驗智慧城市的重要研究領域，基于IEEE 802.11p的VANET[1,2]是車聯網的主要研究方向。VANET是由車載單元OBU(on board unit)、路邊單元RSU(road side unit)組成的自組織網絡，并支持在缺少基礎設施環境下建立通信網絡是VANET的特點。然而，由于車輛移動速度快、時空分布不均[3,4]，造成路由拓撲變化快、路由路役失效限制了VANET網絡的優勢[5]。

針對VANET網絡的客觀條件，研究者設計了多種VANET專用路由協議[5-7]，其中地理信息路由GRP(geographic routing protocols)由于無需進行源結點和目標結點間的路由建立與維護，較傳統的AODV等路徑路由有較大的優勢。進一步的發展中，研究者針對GRP路由斷裂后路由恢復操作開銷較大的問題，提出了分段感知路由協議[8]，協議將道路按交叉路口分割為道路段RS(road segment)，通過信息搜集報文ICP(information collector packet)搜集實時的RS網絡狀態作為路由規劃的依據。然而，由于缺少ICP報文生成頻率的調節機制，該類協議的維護開銷較大。

針對這一這問題，本文設計了一種地理路由算法，記為RSAR。該算法設計了有效期機制VPM(verity period mechanism)控制每個OBU的路由信息更新頻率以減少路由維護的開銷，量化的RS網絡狀態則用于路由規劃。仿真結果表明了RSAR的有效性。

1 系統建模

1.1 系統建模

考慮到支持IEEE 802.11p的基礎設施的鋪設成本及現有規模等問題，RSAR研究基于無RSU的車輛自組織網絡，如圖1所示。RASR對研究的車輛進行了若干合理假設：

(1)配備IEEE 802.11p的通信設備；

(2)配備GPS或北斗導航系統，可以獲取自身的經緯度并計算出當前的矢量速度；

(3)配備運算能力，可以維護鄰居表、RS信息表等數據。

圖1 RSAR的研究環境

圖1中源結點即當前ICP報文的發起者，由于802.11p的通信能力有限，故采用多個中繼結點進行ICP的轉發。

1.2 描述約定

本文中，對于車輛結點n有統一的參數定義：①坐標 (xn,yn)； ②行駛速度vn； ③行駛方向θn。

2 路由算法

2.1 路由有效期計算

(1)

LTD是結點間通過無線信號進行直接通信的最長有效時間估值，對于任意車輛s和n，據文獻[9]，LTD由式(2)計算給出。特別的，當s和n的矢量速度一致時，分母為0，即鏈路壽命為無限大，在實際編碼過程中須進行特殊判斷

(2)

SD是路段上運行的車輛數量的量化指標，對于VANET網絡，結點密度越大，就存在更多的備用鏈路以維持網絡的連接[10]。SD的計算由式(3)給出，其中Nv為當前ICP發送方向同向的車輛數量，Nov為與當前ICP傳輸方向反向的車輛數量

SD=Nv+Nov

(3)

SFRC是特定路段內的車流量在單位時間內的分差，如式(4)所示，Vt是計算路段t時刻車輛的平均速度

SFRC=SDt*Vt-SDt-1*Vt-1

(4)

2.2 路由質量計算

RSAR將特定RS的當前網絡狀態量化表示為Ss， 以作為路由規劃的依據。RS的網絡狀態則量化表示為段密度Sd、 段連接度Sc和段負載Sl。 為適應不同交通情況及方便后期調節，在本節公式中引入加權參數α、β、γ，以方便根據仿真或實際測試結果進行優化。

段密度表示路段車輛的路由密度，表現為段中移動車輛的路由可用數量與ICP包中繼開銷的比值，具體公式見式(5)，其中Nh為參與ICP轉發的車輛結點數，Cm為常數度量，數值設置為12。由式(1)可知，同向車輛的LTD更高更有有利于維持路由，故算法中設置α=0.8，β=0.2，Sd的取值區間為[0,1]，若計算結果Sd大于1則設置Sd為1

(5)

段連接度是段中路由穩定的量化指標，其表示路中路由無故障的運行可能性。段連接度受設備故障概率、路由斷裂率等因素，通常無法直接獲取，故本文中段連接度的計算見式(6)，其為有效期和ICP每跳平均網絡延遲的比值，其中Ttime是CP包的傳輸時間，通過計算ICP生成時間與接收時間差獲得。SC的取值區間為[0,1]，SC值越高，網絡連通程序越好

(6)

段負載表示段內網絡負載的量化指標，計算方法見式(7)，其中ALv和ALov為通過CP包廣播中獲取的接收值，Cll為常數值表示網絡緩沖區隊列中容量上限，在IEEE 802.11p設置為50。同段密度的計算參數用值，α1=0.8，β1=0.2，Sl的取值區為[0,1]，段的數值越高其網絡負載越大

(7)

綜上，Ss的最終計算見式(8)，不失一般性的設置α2=β2=λ=0.33

Ss=(α2×Sd)+(β2×Sc)-(λ×Sl)

(8)

2.3 路由協議

路數包的路由決策較為簡單，與傳統分段感知路由協議[8]的策略相似，在分支路口通過式(8)獲取Ss進行選擇合適的RS進行路由即可。本章節主要闡述路由信息的維護流程，即ICP報文的生成、轉發及廣播。

2.3.1 ICP報文設計

ICP的報文是RSAR進行數據搜集的基礎，綜合2.1節和2.2節的計算需求，設計了圖2所示ICP報文。在計算所需要的基礎上增加了Vid和RSid字段以分別標識報文的源結點和當前RS， (Vid，RSid) 共同組成了對車輛Vid的路由路徑。VStime為ICP的生成時間戳，另外默認接收方可以直接獲得發送方的ID。

圖2 ICP的報文字段

2.3.2 ICP傳輸協議

ICP報文的段內組播流程如圖3所示，源結點Vid生成新的ICP報文，利用改進的貪婪算法計算出當前最有效的Vnext， 并將ICP交付于適當的鄰居結點Vnext，Vnext利用式(1)計算自有效值V′p并與接收到的ICP中Vp進行比較，取最小值并進行自身鄰居表的更新操作，再將ICP中的Nh加1后傳遞給一個鄰居直到RS的末端結點。

圖3 ICP的段內組播流

當ICP到RS的末端，即鄰居的交叉路口后，ICP的段內廣播結束，最后的結點Vend將按圖4進行處理。當Vend對Vid無記錄，即Vid第一次到達Vend時，若ICP的漫游時間在Vp有效期內，即當前時間T與所接收的ICP的時間戳滿足T-VStimeVp， 即上個ICP所對應的路由路徑失效則重新廣播當前路由信息，若否，即ICP包過度重傳，不進行廣播處理。當進行叉口廣播后，Vend都向源結點發送ICP-ACK確認報文。

圖4 ICP的路口廣播流程

3 仿真實驗

3.1 仿真環境及評估方法

仿真環境利用網絡仿真器OMNET++[11]和道路仿真器SUMO[11]聯合完成，參照相關研究[12]設置了一個邊長 2 km 的正方形網格模型，車輛的移動模型為經典的隨機旅游模型，具體參數設置見表1。作為對比，使用了iCAR[13]、TFOR[14]的公開PBR協議進行參照，部分的參數設置如下。針對車輛的移動速度、密度存在較大的時間差距，故使用低密度LOW(6veh/km/lane)和高密度HIGH(50veh/km/lane)兩種模型分別測試路由算法在兩種情況下的表現。

評估主要涉及兩方面，第一是路由維護開銷，第二是數據包傳輸質量。路由維護開銷量化表示為仿真時間內的ICP包生成數量，ICP的數量越少則路由的維護開銷越低，對數據包的影響越小。

表1 仿真參數設置

數據包傳輸質量的傳輸質量由數據包交付率和數據延遲量化表示，考慮到網絡負載對網絡傳輸的影響，采用恒定比特率(CBR)用戶數據報協議應用進行性能測試，該協議允許通過傳輸固定大小的分組以固定速率創建流量模式。實驗中通過控制OBU上CBR并發連接的數量，測試在負載下跟帖算法的效果。

3.2 分 析

圖5給出了3種路由協議的ICP生成數，其中縱軸用“算法名-密度類型”進行分類，如RSAR-LOW表示RSAR算法在低密度情況下的ICP生成數量。

圖5 ICP的生成數量統計

具體到數據對比，由于引入了VPM機制RSAR在高密度環境下較iCAR降低了70.5%的ICP報文生成量，但在低密度環境下只降低了47.3%，較TFOR亦有明顯的優秀。對于RSAR在低密度環境下表現劣于高密度環境，經過分析認為低密度環境下，網絡路由變化后缺少備用路線導致路由故障的概念更高即Vp數值較低，必需多次使用ICP報文發送以維護網絡質量。

圖6和圖7給出了3種算法在進行數據傳輸時的數據包交付率，可以看出RSAR在不同密度環境下有較好的表現。具體到數值，可以發現RSAR在CBR并發數小于8以內時有較好的絕對表現，數據包交付率始終維持在80%以上，較其它兩種路由提高了近5個百分點；在CBR并發數大于8后有較好的相對表現。RSAR綜合考慮了網絡負載，在數據傳輸量較多時可以選用負載較低的路經，除在CBR大量并發至整體網絡負載過高的情況下，其表現十分出色。

圖6 低密度環境下的數據包交付率

圖7 高密度環境下的數據包交付率

圖8和圖9給出了3種路由算法在進行數據傳輸時的平均分組延遲可以發現，在低密度環境下SRAR的表現是3種算法中最差的，其平均延遲比其在低數據通信時比其余兩種高11.3%和12.5%，而在高數據通信服務下，則皆大于50%；在密度環境下，RSAR的表現是三者中最好，尤其在高并發通信時，降低了50%以上的延遲。進一步研究后認為，由于RSAR高度依賴RS的通信質量，而沒有量化引入RS通信距離對延遲的影響，導致在低密度環境下以保證數據包交付率為代價增大了延遲，而在高密度結點情況下，由于充分使用了整體VANET網絡的通信能力，相對降低了特定RS上的網絡負載，間接保證了低延遲通信。

圖8 低密度環境下的數據包延遲

圖9 高密度環境下的數據包延遲

3.3 實驗小結

結合數據包交付率、網絡時延，認為RSAR可以較低的網絡維護開銷保證較高的數據包交付率，并在高車輛密度下有效降低了數據延遲，可以適用于大城市的VANET網絡路由服務。但RSAR在低車輛密度環境下數據延遲較大，不適用于緊急安全消息的應用，故RSAR仍存在較大的改進空間。

4 結束語

本文介紹了RSAR路由算法的系統建模、算法設計及仿真結果，這是一種主要針對城市交通環境下的分段感知路由算法。RSAR綜合考慮了影響道路網絡質量的因素，引入段密度、段連接度及段負載計算段網絡狀態，避開低質量路由路線；設計有效期機制有效控制了路由的維護代價。仿真結果表明，RSAR在網絡開銷、數據包交付率方面明顯優于現有算法，同時在高車輛密度下，RSAR亦能有效降低網絡延遲。不足之處主要在于，RSAR的延遲控制在低密度環境下表現欠佳，需要進一步完善。