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

陳潘航，周宏偉

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

0 引 言

車輛網(wǎng)是實驗智慧城市的重要研究領(lǐng)域，基于IEEE 802.11p的VANET[1,2]是車聯(lián)網(wǎng)的主要研究方向。VANET是由車載單元OBU(on board unit)、路邊單元RSU(road side unit)組成的自組織網(wǎng)絡(luò)，并支持在缺少基礎(chǔ)設(shè)施環(huán)境下建立通信網(wǎng)絡(luò)是VANET的特點。然而，由于車輛移動速度快、時空分布不均[3,4]，造成路由拓?fù)渥兓?、路由路役失效限制了VANET網(wǎng)絡(luò)的優(yōu)勢[5]。

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

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

1 系統(tǒng)建模

1.1 系統(tǒng)建模

考慮到支持IEEE 802.11p的基礎(chǔ)設(shè)施的鋪設(shè)成本及現(xiàn)有規(guī)模等問題，RSAR研究基于無RSU的車輛自組織網(wǎng)絡(luò)，如圖1所示。RASR對研究的車輛進(jìn)行了若干合理假設(shè)：

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

(2)配備GPS或北斗導(dǎo)航系統(tǒng)，可以獲取自身的經(jīng)緯度并計算出當(dāng)前的矢量速度；

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

圖1 RSAR的研究環(huán)境

圖1中源結(jié)點即當(dāng)前ICP報文的發(fā)起者，由于802.11p的通信能力有限，故采用多個中繼結(jié)點進(jìn)行ICP的轉(zhuǎn)發(fā)。

1.2 描述約定

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

2 路由算法

2.1 路由有效期計算

(1)

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

(2)

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

SD=Nv+Nov

(3)

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

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

(4)

2.2 路由質(zhì)量計算

RSAR將特定RS的當(dāng)前網(wǎng)絡(luò)狀態(tài)量化表示為Ss， 以作為路由規(guī)劃的依據(jù)。RS的網(wǎng)絡(luò)狀態(tài)則量化表示為段密度Sd、 段連接度Sc和段負(fù)載Sl。 為適應(yīng)不同交通情況及方便后期調(diào)節(jié)，在本節(jié)公式中引入加權(quán)參數(shù)α、β、γ，以方便根據(jù)仿真或?qū)嶋H測試結(jié)果進(jìn)行優(yōu)化。

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

(5)

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

(6)

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

(7)

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

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

(8)

2.3 路由協(xié)議

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

2.3.1 ICP報文設(shè)計

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

圖2 ICP的報文字段

2.3.2 ICP傳輸協(xié)議

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

圖3 ICP的段內(nèi)組播流

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

圖4 ICP的路口廣播流程

3 仿真實驗

3.1 仿真環(huán)境及評估方法

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

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

表1 仿真參數(shù)設(shè)置

數(shù)據(jù)包傳輸質(zhì)量的傳輸質(zhì)量由數(shù)據(jù)包交付率和數(shù)據(jù)延遲量化表示，考慮到網(wǎng)絡(luò)負(fù)載對網(wǎng)絡(luò)傳輸?shù)挠绊?，采用恒定比特?CBR)用戶數(shù)據(jù)報協(xié)議應(yīng)用進(jìn)行性能測試，該協(xié)議允許通過傳輸固定大小的分組以固定速率創(chuàng)建流量模式。實驗中通過控制OBU上CBR并發(fā)連接的數(shù)量，測試在負(fù)載下跟帖算法的效果。

3.2 分 析

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

圖5 ICP的生成數(shù)量統(tǒng)計

具體到數(shù)據(jù)對比，由于引入了VPM機(jī)制RSAR在高密度環(huán)境下較iCAR降低了70.5%的ICP報文生成量，但在低密度環(huán)境下只降低了47.3%，較TFOR亦有明顯的優(yōu)秀。對于RSAR在低密度環(huán)境下表現(xiàn)劣于高密度環(huán)境，經(jīng)過分析認(rèn)為低密度環(huán)境下，網(wǎng)絡(luò)路由變化后缺少備用路線導(dǎo)致路由故障的概念更高即Vp數(shù)值較低，必需多次使用ICP報文發(fā)送以維護(hù)網(wǎng)絡(luò)質(zhì)量。

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

圖6 低密度環(huán)境下的數(shù)據(jù)包交付率

圖7 高密度環(huán)境下的數(shù)據(jù)包交付率

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

圖8 低密度環(huán)境下的數(shù)據(jù)包延遲

圖9 高密度環(huán)境下的數(shù)據(jù)包延遲

3.3 實驗小結(jié)

結(jié)合數(shù)據(jù)包交付率、網(wǎng)絡(luò)時延，認(rèn)為RSAR可以較低的網(wǎng)絡(luò)維護(hù)開銷保證較高的數(shù)據(jù)包交付率，并在高車輛密度下有效降低了數(shù)據(jù)延遲，可以適用于大城市的VANET網(wǎng)絡(luò)路由服務(wù)。但RSAR在低車輛密度環(huán)境下數(shù)據(jù)延遲較大，不適用于緊急安全消息的應(yīng)用，故RSAR仍存在較大的改進(jìn)空間。

4 結(jié)束語

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