吳衛(wèi)祖 劉利群 謝冬青

1(廣東海洋大學信息學院 廣東 湛江 524088) 2(廣州大學計算機科學與教育軟件學院 廣東 廣州 510006)

?

基于道路段評價機制低延時VANETs路由算法

吳衛(wèi)祖1劉利群1謝冬青2

1(廣東海洋大學信息學院 廣東 湛江 524088)2(廣州大學計算機科學與教育軟件學院 廣東 廣州 510006)

針對城市車輛自組織網絡應用需求，提出一種低延時路由協(xié)議。該路由協(xié)議以城市交通網絡模型為基礎，首先從各道路段上尋找顯著節(jié)點，然后估計顯著節(jié)點之間的鏈路生存時間，接著從交叉口區(qū)域尋找最優(yōu)的中繼節(jié)點。一旦找到中繼節(jié)點便開始廣播道路段評價數據包，依據傳輸延時計算每一個道路段的權重值，最后在路由構建階段依據道路段權重和有效期選取最優(yōu)傳輸路徑，實現(xiàn)數據的低延時傳輸。大量的仿真實驗結果表明，與常用的GPSR和GPSR-R路由協(xié)議相比，該路由協(xié)議不僅端到端平均延時大幅降低，而且報文送達率高、網絡開銷小。

車輛自組織網絡 路由協(xié)議 傳輸延時 鏈路生存時間 顯著節(jié)點

0 引 言

車輛自組織網絡VANETs是無線自組織網絡的一種，采用攜帶無線通信設備的車輛作為通信節(jié)點，組建自由、靈活的無線通信網絡[1]。目前城市交通環(huán)境中運行的車輛非常多，大部分車輛裝配了無線通信和定位裝置，為車輛自組織網絡的構建提供了便利條件。通過構建車輛自組織網絡，可以為車輛駕駛員或乘客提供許多便捷服務(如媒體共享)[2～4]。隨著計算機網絡技術的迅猛發(fā)展，車輛自組織網絡的應用越來越廣泛。在實際應用過程中，許多應用場合對數據傳輸延時提出了更高的要求，如網絡接入、媒體共享和廣告服務等應用場合，用戶希望數據傳輸延時盡可能低[5]。然而，在城市交通網絡中，這些需求難以得到較好滿足。因為估計道路段上的車輛數量是非常復雜的，不同時段不同區(qū)域的車流密度變化很快，車輛在道路上的空間分布也不均勻，而且城市環(huán)境中障礙物也比較多，這些都會導致數據傳輸延時增加[6～8]。為了解決這些問題，目前也提出了有意義的路由協(xié)議，如GPSR[9]、GSR[10]、GPSR-R[11]等路由協(xié)議通過選擇源節(jié)點到目的節(jié)點之間的最短傳輸路徑來降低數據傳輸延時。然而，單純依靠距離最短準則難以大幅降低數據傳輸延時，而且此類準則在選擇最優(yōu)路由時容易陷入局部最優(yōu)問題。

為了進一步降低面向城市車輛自組織網絡的數據傳輸延時，本文提出了一種基于道路段評價機制的低延時路由協(xié)議?；舅悸肥且罁祿鬏斞訒r對每一個道路段進行評價，依據評價結果選擇數據傳輸延時小的道路段進行數據傳輸，從而大幅降低數據傳輸的端到端延時。

1 城市交通網絡模型

典型的城市交通環(huán)境常采用道路段和交叉口組成的網絡模型來模擬。每兩個交叉口之間存在一個道路段，每一個道路段都包含道路長度、道路寬度、車道數量、交通密度等特征。道路段上行駛的車輛組成網絡的通信節(jié)點。本文假定每一臺車輛都裝配了GPS定位裝置，可以提供車輛的位置、速度、方向以及一個包含道路段及交叉口等細節(jié)信息的數字地圖。在轉發(fā)數據包時，源節(jié)點可以通過查詢定位服務去獲取目的節(jié)點的位置。

無線自組織網絡常采用無向圖模型G(V,E)來描述，其中，V表示無向圖模型中的頂點集合，也即網絡中的車輛節(jié)點。E表示無向圖模型中的邊的結合，也即兩臺車輛之間的無線通信鏈路。

P=Vi→V1→…→Vn→Vj

(1)

2 本文方法

本文方法的設計目標是降低數據傳輸的端到端延時，以便在車輛自組織網絡中快速傳輸數據，主要用于對延時比較敏感的場合，如網絡接入、媒體共享和廣告服務等。本文方法主要包括五個部分，分別是顯著節(jié)點生成、鏈路生存時間估計、中繼節(jié)點選擇、道路段評價和路由構建，詳細描述如下。

2.1 顯著節(jié)點生成

每一條道路段可能存在很多車輛，這些車輛有些是在數據傳輸過程中作用重大的顯著車輛，有些是對數據傳輸作用不大的普通車輛。那么，我們需要尋找每一條道路段的顯著車輛，生成顯著節(jié)點。在這一過程中，車輛通過信標服務交互信息，交互信息內容為:

M=ID,x,y,v,θ,c,f

(2)

其中，ID為車輛的唯一標識符，(x,y)表示車輛的位置坐標，v表示車輛的速度，θ表示車輛的方向，c表示車輛的顯著屬性，如果車輛為顯著車輛，則c=1，否則c=0。f是一個穩(wěn)定因子，計算方式為:

(3)

其中，vn和dn分別表示當前車輛的所有一跳鄰居車輛的平均速度和平均距離，R表示車輛的通信范圍。

在式(3)中，第一項反映了當前車輛的一跳鄰居車輛與其相對速度值，該值越大，說明當前車輛的速度相對于其鄰居車輛的速度越小，這樣車輛在行駛過程中通信鏈路中斷的可能性越小，穩(wěn)定性越好。第二項反映了車輛的相對位置關系，當前車輛與一跳鄰居車輛的相對距離越小，通信鏈路中斷的可能性越小。

當車輛接收到信標消息之后，建立一個一跳鄰居列表。列表的每一個入口包含了從信標中獲取的信息。一旦發(fā)現(xiàn)一個新的鄰居，就增加一個新的入口。一臺車輛需要等待兩個連續(xù)的信標間隔來監(jiān)聽其鄰居。如果沒有接收到消息，將刪除對應的鄰居入口。一旦建立了鄰居列表，每一個通信節(jié)點都要計算穩(wěn)定因子f，并與其鄰居節(jié)點的穩(wěn)定因子進行比較。然后選取穩(wěn)定因子最大的節(jié)點作為顯著節(jié)點，并將對應的顯著屬性c置為1。

2.2 鏈路生存時間估算

本節(jié)所述的鏈路生存時間是指兩個顯著節(jié)點之間的鏈路生存時間，估算該時間的目的是預測該鏈路發(fā)生中斷的時間。

令Vi(d)和Vj(d)表示兩個連續(xù)的顯著節(jié)點。首先，我們比較兩臺車輛的行駛方向，如果它們的行駛方向相同，則鏈路中斷會發(fā)生在兩者的距離超過車輛通信范圍R之后，因此，鏈路生存時間應為:

(4)

其中，Di,j表示節(jié)點Vi(d)和Vj(d)之間的歐氏距離，也即:

(5)

如果節(jié)點Vi(d)和Vj(d)的行駛方向不同，則需要考慮兩種情況：

第一種情況是節(jié)點Vi(d)和Vj(d)相互接近。這樣，鏈路中斷發(fā)生在兩臺車輛相交叉且距離超過車輛通信范圍，此時鏈路的生存時間為:

(6)

第二種情況是節(jié)點Vi(d)和Vj(d)背向行駛，越離越遠。這種情況下，鏈路中斷發(fā)生在兩臺車輛的相對距離超過車輛通信范圍，此時鏈路的生存時間為:

(7)

需要說明的是，鏈路的生存時間也存儲在車輛的鄰居列表中，在每一次信標服務過程中計算和更新。

2.3 中繼節(jié)點選擇

前面所述的顯著節(jié)點都定義在道路段上，而不同道路段上的顯著節(jié)點之間無法連通。為了連通這些節(jié)點，本文在兩道路段的交叉口定義一個中繼節(jié)點。中繼節(jié)點的選擇方法是：

Step1尋找道路段交叉口區(qū)域的所有車輛，將其作為候選的中繼節(jié)點；

Step2剔除那些已經駛過交叉口中心的車輛，因為這些車輛即將離開交叉口，不適合作為中繼節(jié)點；

Step3從剩余節(jié)點中篩選出顯著屬性為1的節(jié)點，如果沒有，則保留所有剩余節(jié)點；

Step4從余下的節(jié)點中選擇行駛速度最慢的節(jié)點，因為速度越慢的節(jié)點在交叉口停留的時間越長。

當一個中繼節(jié)點即將離開交叉口區(qū)域時，需要為其尋找一個替代者。方法是：

首先，計算每一個與當前中繼節(jié)點相鄰的顯著節(jié)點通過交叉區(qū)域的時間t1；

然后，計算當前綠燈的剩余時間t2，表示為:

t2=tg-[tα%tC-(tC-tg)]

(8)

其中，tα表示車輛到達紅綠燈的時間，tg表示綠燈持續(xù)時間，tC表示綠燈的循環(huán)間隔?！?”表示整除運算。

如果t2>t1，我們選取t1最大的節(jié)點作為中繼節(jié)點。否則，我們在紅燈亮時從顯著節(jié)點集合中已經停止的車輛中選取一個距離交叉區(qū)域邊界最近的節(jié)點作為中繼節(jié)點。

2.4 道路段評價

在交叉口區(qū)域，一旦選定了中繼節(jié)點，就開始進行道路段評價。道路段評價是后續(xù)路由構建的依據，用于評價該道路段作為路由路徑的優(yōu)先級。道路段評價的方法是：

首先，在中繼節(jié)點處建立路由表，便于數據轉發(fā)。

然后，中繼節(jié)點生成一個道路評價數據包并在所有道路段上進行廣播。道路評價數據包用于收集道路段的相關信息，如數據包延時和跳數量，數據包格式如圖1所示。

圖1 道路評價數據包格式

在圖1中，時間戳指明了道路評價數據包的創(chuàng)建時間，delay表示數據包延時，具體為:

(9)

其中，n為一個道路段上的顯著節(jié)點數量，delayVi表示第i個顯著節(jié)點vi的數據包延時。

每一個節(jié)點的數據包延時都包含兩個部分，一是數據的傳輸延時，二是隊列延時。

當某一個顯著節(jié)點接收到道路評價數據包之后，它對道路評價數據包進行修改，修改內容包括兩個部分，一是在跳數量子項中加入該節(jié)點，二是更新數據包延時，即在原有延時的基礎上增加該節(jié)點的數據包延時。更新之后，再將道路評價數據包轉發(fā)給下一個顯著節(jié)點，直至到達下一個中繼節(jié)點。

中繼節(jié)點在接收到道路評價數據包之后，計算道路評價數據包的傳輸延時t3，計算方法是用該中繼節(jié)點接收到道路評價數據包的時間減去道路評價數據包上的時間戳。

記道路評價數據包的傳輸延時上限和下限分別為Tup和Tdown。對于一個長度為L的道路段，其可以容納的最大顯著節(jié)點數量為:

(10)

其中，Int()表示取整數運算。

那么，數據包延時下限Tdown可以表示為:

(11)

其中，Tt表示節(jié)點的傳輸延時。

數據包傳送延時上限Tup可以表示為:

Tup=Tdown-t1

(12)

如果t3Tup，中繼節(jié)點可以認定該道路段已經完全無法連接?；谶@一思路，中繼節(jié)點為不同的道路段分配不同的權重，第i個道路段的權重可以表示為:

(13)其中，t4表示該道路段的平均車輛通過時間，可以由該道路段的長度除以該道路段上所有車輛的平均速度計算。

考慮到權重與延時相關，需要為其計算一個有效期，用于描述該權重是否有效。第i個道路段權重的有效期可以由該道路段上所有鏈路的最小生存時間來表示，即:

Validi=min(lf1,lf2,…,lfk)

(14)

其中，k為該道路段上的鏈路數量。

在得到所有道路段的權重之后，每一個中繼節(jié)點構建一個路由表，用于后續(xù)的路由構建。

2.5 路由構建

當源節(jié)點需要發(fā)送數據給目的節(jié)點時，它生成一個路由請求數據包，該數據包一般包含源節(jié)點ID、目的節(jié)點ID和目的節(jié)點位置。源節(jié)點轉發(fā)該路由請求包給其所在道路段上的所有中繼節(jié)點。對于每一個中繼節(jié)點，當其接收到源節(jié)點發(fā)送的路由請求包之后，首先檢查其路由表，查看該中繼節(jié)點是否可以將數據送達目的節(jié)點，如果可以，它將從其路由表中選擇一個從源節(jié)點到目的節(jié)點的權重最大的路徑，將路由請求數據包轉發(fā)給目的節(jié)點。

路由路徑的權重可以表示為:

(15)

其中，m為該路徑所經過的道路段數量，Wi表示第i個道路段的權重，依據式(13)計算。路徑上所有道路段的權重之和越大，數據傳輸的端到端延時越小。

由于中繼節(jié)點不止一個，因此目的節(jié)點可能接收到多個路由請求數據包，也即存在多條數據傳輸路徑。這種情況下，目的節(jié)點將所有路徑存儲在路由表中，同時存儲路徑所對應的有效期，路徑有效期的計算公式為:

(16)

其中，Validi表示第i個道路段權重的有效期，依據式(14)計算。

然后，目的節(jié)點選擇權重最大的路徑，將其放進路由應答數據包，回傳給源節(jié)點。當源節(jié)點收到路由應答數據包之后，即可開始發(fā)送數據給目的節(jié)點。

在數據發(fā)送過程中，中繼節(jié)點在數據轉發(fā)過程中更新傳輸路徑的權重，路徑權重會逐漸降低，當路由的有效期結束或者路徑的權重低于閾值WT時，源節(jié)點重新發(fā)起路由請求，建立新的路由。

3 實驗仿真與分析

車輛自組織網絡常用的仿真軟件是Network Simulator[12]軟件，本文在該軟件上仿真本文路由協(xié)議和常用的GPSR、GPSR-R路由協(xié)議，測試常用的端到端平均延時、報文送達率和網絡開銷三個指標[13]，依據這三個指標評測三種路由協(xié)議的性能，仿真軟件的相關參數見表1所示。下面首先分析本文路由協(xié)議的參數取值，然后再對比不同路由協(xié)議的性能指標。

表1 仿真軟件相關參數

3.1 參數分析

本文路由協(xié)議涉及一個閾值參數，為權重閾值WT。當該參數取值不同時，數據傳輸的端到端平均延時是不同的。圖2給出了本文路由協(xié)議的端到端平均延時隨權重閾值WT的變化曲線，其中數據包產生速率為5個/s。

圖2 端到端平均延時隨權重閾值的變化曲線

由圖2可見，權重閾值WT太小或者太大時都會導致端到端平均延時增加。因為權重閾值WT太大時，在數據傳輸過程中路由路徑的權重會很快下降到權重閾值WT之下，這樣就需要重新發(fā)起路由請求，盡管數據在路由路徑上的傳輸延時較小，但由于頻繁構建路由，導致整體的端到端平均延時增大。而當權重閾值WT太小時，盡管路由請求次數較少，但是，在數據傳輸過程中路由路徑上的權重越來越小，導致數據傳輸延時越來越大，從而也會導致整體的端到端平均延時增大。由圖2可見，當WT=120(ms)時，數據傳輸的端到端平均延時最小。因此，本文取權重閾值WT=120(ms)。

3.2 性能對比

本文路由協(xié)議的設計目標是盡可能降低數據傳輸的端到端平均延時，用于服務媒體共享、廣告接入等低延時需求的應用。因此，本文路由性能最關注的性能指標是數據傳輸的端到端平均延時。但同時，報文送達率和網絡開銷也是車輛自組織網絡服務質量的重要評價指標。因此，這里對這三項指標分別進行評價(如圖3-圖5所示)，然后給出綜合評價結果。

圖3 端到端平均延時隨數據包產生速率的變化曲線

圖3給出了數據包產生速率不同時三種路由協(xié)議的端到端平均延時指標?？梢姡M管本文路由協(xié)議的端到端平均延時指標也會像其他兩種方法一樣隨著數據包產生速率的增加而增加。但是很明顯本文路由協(xié)議的端到端平均延時指標隨著數據包產生速率增加的上升速率較低，而且在同等條件下的端到端平均延時都遠小于其他兩種路由協(xié)議。這是因為本文路由協(xié)議以路由路徑的傳輸延時最小(也即路由路徑的權重最大)為路由選擇依據，因此本文路由協(xié)議的端到端傳輸延時要明顯小于其他兩種路由協(xié)議。

圖4 報文送達率隨數據包產生速率的變化曲線

圖4給出了三種路由協(xié)議的報文送達率指標隨數據包產生速率的變化曲線，可見在同等條件下本文路由協(xié)議的報文送達率指標也高于其他兩種路由協(xié)議。這是因為本文路由協(xié)議在各道路段有效期結束后會重新構建路由，路由穩(wěn)定性好。因此在大幅降低端到端平均延時的情況下，還能夠提高報文送達率指標。

圖5 路由開銷隨數據包產生速率的變化曲線

圖5給出了三種路由協(xié)議的路由開銷指標隨數據包產生速率的變化曲線。同樣，相同條件下本文路由協(xié)議的路由開銷要小于其他兩種路由協(xié)議，數據包產生速率越大，本文路由協(xié)議的優(yōu)勢越明顯。這是因為本文路由協(xié)議在數據傳輸過程中路由請求次數較少，路由穩(wěn)定性較好。

綜合分析端到端平均延時、報文送達率和路由開銷三個指標，本文路由協(xié)議在大幅降低端到端平均延時的情況下，路由開銷也隨之降低，報文送達率指標也有提高，優(yōu)于其他兩種常用的車輛自組織網絡路由協(xié)議。

4 結 語

針對城市交通場景下網絡接入、媒體共享和廣告服務等對延時比較敏感的應用場合，本文提出了一種基于道路段評價機制的車輛自組織網絡路由協(xié)議。該協(xié)議通過顯著節(jié)點生成、鏈路生存時間估計、中繼節(jié)點選擇、道路段評價和路由構建五個階段，實現(xiàn)低延時路由的構建。實驗表明，本文提出的路由協(xié)議可以大幅降低數據傳輸的端到端延時，同時路由開銷小、報文送達率高，是一種低延時的城市車輛自組織網絡路由協(xié)議。

[1] 吳怡, 沈穎祺, 沈連豐,等. 基于協(xié)議序列的車輛自組織網絡信道接入控制算法[J].電子學報, 2012, 40(4):826-831.

[2] Wang S S, Lin Y S. PassCAR: A passive clustering aided routing protocol for vehicular ad hoc networks[J]. Computer Communications, 2013, 36(2):170-179.

[3] 姚宏, 滕超, 叢磊,等. 車輛自組織網絡中使用公交車輛協(xié)助的數據分發(fā)[J]. 計算機工程與科學, 2014, 36(11):2114-2118.

[4] Li Y, Boukerche A. QuGu: A Quality Guaranteed Video Dissemination Protocol Over Urban Vehicular Ad Hoc Networks[J].Acm Transactions on Multimedia Computing Communications & Applications, 2015,11(4):1-23.

[5] Campolo C, Molinaro A. Multi-channel communications in Vehicular Ad hoc NETworks: A Survey[J].IEEE Communications Magazine, 2013,51(5):158-169.

[6] Dua A, Kumar N, Bawa S. A systematic review on routing protocols for Vehicular Ad Hoc Networks[J]. Vehicular Communications, 2014,1(1):33-52.

[7] Li Y, Jin D, Hui P, et al. Revealing contact interval patterns in large scale urban vehicular ad hoc networks[J].Acm Sigcomm Computer Communication Review, 2012,42(4):299-300.

[8] Villas L A, Boukerche A, Maia G, et al. DRIVE: An efficient and robust data dissemination protocol for highway and urban vehicular ad hoc networks[J].Computer Networks, 2014,75:381-394.

[9] Ding X T, Peng X G. An energy balancing routing based on GPSR protocol[J]. Transducer & Microsystem Technologies, 2013,32(4):12-15.

[10] Behera A, Panigrahi A. Determining the network throughput and flow rate using GSR And AAL2R[J]. International Journal of Oncology, 2015, 43(2):661-669.

[11] 李超, 韓江洪, 魏振春,等. VANET 場景下的 GPSR-R 路由算法[J]. 合肥工業(yè)大學學報:自然科學版, 2015(2):181-185.

[12] The Network Simulator-ns-2[EB/OL]. 2011. http://www.isi.edu/nsnam/ns/.

[13] Daraghmi Y A, Yi C W, Stojmenovic I. Forwarding methods in data dissemination and routing protocols for vehicular Ad Hoc networks[J].IEEE Network, 2013,27(27):74-79.

ALOW-DELAYROUTINGALGORITHMFORVANETSBASEDONROAD-SECTIONEVALUATIONMECHANISM

Wu Weizu1Liu Liqun1Xie Dongqing2
1(SchoolofInformation,GuangdongOceanUniversity,Zhanjiang524088,Guangdong,China)2(SchoolofComputerScienceandEducationSoftware,GuangzhouUniversity，Guangzhou510006,Guangdong,China)

A low-delay routing protocol is proposed for application demand of city vehicle ad hoc networks. Based on the model of city traffic network, the new routing protocol look for the significant nodes on each road-section firstly, then it estimated the lifetime of links between two significant nodes, and found the optimal relay nodes on intersection. Once finding the relay node, the algorithm will begin broadcasting the road-section evaluation packet and calculate a weight value for every road-section according to transmission delay. In the end, it selects the optimal transmission path according to weight and validity of road-sections in routing building stage and achieve low-delay transmission for data. Experiments show that the new routing protocol can not only reduce the average end-to-end transmission delay significantly, but also obtain high packet delivery rate and low network overhead compared with the commonly used GPSR and GPSR-R routing protocols.

Vehicle ad hoc networks Routing protocol Transmission delay Link lifetime Significant node

2016-08-16。國家高技術研究發(fā)展計劃項目(2009AA012420)；廣東省科技計劃項目(2014A020218016)。吳衛(wèi)祖，副教授，主研領域：信息系統(tǒng)，網絡安全，物聯(lián)網，北斗通信及應用。劉利群，副教授。謝冬青，教授。

TP393

A

10.3969/j.issn.1000-386x.2017.08.048