基于分布式實(shí)時機(jī)制的車載網(wǎng)絡(luò)出行計劃算法

摘 要:提出了一種基于分布式實(shí)時交通統(tǒng)計的機(jī)制，每輛汽車能夠分布式地實(shí)時獲取各路段的汽車通行時間，這樣汽車就能夠根據(jù)這些信息計算出行計劃。仿真結(jié)果顯示該方法對各路段交通情況評估具有有效性和信息擴(kuò)散的實(shí)時性。

關(guān)鍵詞:車載自組織網(wǎng)絡(luò); 出行計劃; 分布式

中圖分類號:TP393文獻(xiàn)標(biāo)志碼:A

文章編號:1001-3695(2009)09-3440-02

doi:10.3969/j.issn.1001-3695.2009.09.067

Algorithm for travel plan in vehicularAd hoc networks based on distributed real-time scheme

SONG Chao， LIU Ming， GONG Hai-gang

(Institute of Computer Science Engineering， University of Electronic Science Technology of China， Chengdu 610054， China)

Abstract:This paper proposed a distributed real-time traffic statistics scheme for travel plan in wireless vehicular Ad hoc networks. Each vehicle stored the evaluation of average travel time for each road by the scheme. Then it could calculate the travel plans based on these evaluations. Experimental results show that the effectiveness of the proposed approach and related data dissemination protocol.

Key words:VANET(vehicular Ad hoc network); travel plan; distributed

世界有超過6億的車輛行駛在道路中。現(xiàn)代生產(chǎn)的每輛汽車都有超過100個傳感器，這使得汽車成為一個潛在的擁有豐富的感應(yīng)數(shù)據(jù)的傳感器。與其他移動平臺不同的是，汽車能夠提供豐富的資源以保證計算和通信系統(tǒng)的健壯性。更重要的是，汽車已經(jīng)融入了人們的生活，并且與各種不同環(huán)境的接觸使其將傳感器應(yīng)用的范圍擴(kuò)大了。

交通監(jiān)視和出行計劃就是車載自組織網(wǎng)絡(luò)的一個重要應(yīng)用。假設(shè)汽車裝有GPS和電子地圖，而且汽車裝載有當(dāng)前城市中各街道交通情況的數(shù)據(jù)，即汽車通過各路段的時間和平均速度。試想，當(dāng)一個人從家出發(fā)到機(jī)場搭乘40 min后起飛的飛機(jī)，那么在出發(fā)時就可以通過這套設(shè)備搜索出有哪些路段是能夠滿足要求的。本文就是針對這種應(yīng)用，提出了一種基于分布式的實(shí)時交通統(tǒng)計的車載自組織網(wǎng)絡(luò)來解決出行計劃問題。

1 相關(guān)工作

文獻(xiàn)[1]提出了利用車載網(wǎng)絡(luò)能夠有效改善傳感器網(wǎng)絡(luò)的感應(yīng)和無線傳輸范圍。指出將傳感器嵌入到汽車中作為移動的節(jié)點(diǎn)，能夠用于監(jiān)視路面情況和其周圍的環(huán)境。在出行計劃的應(yīng)用方面，提出汽車記錄各路段在一天中不同時段的交通情況的統(tǒng)計信息，就能夠很好地幫助用戶完成出行計劃。

文獻(xiàn)[2]中提出在典型的汽車安全應(yīng)用中，每輛汽車周期性地廣播其當(dāng)前GPS位置、速度、方向以及其他傳感器信息，如剎車狀態(tài)、加速度等，以便其鄰居汽車能夠接收并估計與其行駛關(guān)系是否有潛在的危險。文獻(xiàn)[3]中，作者假設(shè)汽車都安裝了預(yù)先載入的電子地圖，并且提供了不同時段各路段的交通統(tǒng)計的歷史信息，包括車輛密度和汽車行駛速度等。

在數(shù)據(jù)傳遞方面，文獻(xiàn)[4，5]提出了利用有規(guī)律移動的節(jié)點(diǎn)來實(shí)現(xiàn)。例如公交車，由于其運(yùn)動線路和發(fā)車時間相對較固定，可以很好地幫助數(shù)據(jù)傳遞。

在文獻(xiàn)[6]中提出利用靜止的節(jié)點(diǎn)輔助數(shù)據(jù)傳遞。作者提出在路口安置靜止節(jié)點(diǎn)用于存儲和轉(zhuǎn)發(fā)數(shù)據(jù)包。

2 模型

2.1 基本假設(shè)

假設(shè)每輛車都能通過GPS知道其位置(現(xiàn)在很多車都已實(shí)現(xiàn)，今后會更加普遍)，而且每輛車都有電子地圖。汽車之間的通信是通過短距離無線信息(100～250 m)。路口i用Ii表示。從路口I(xiàn)i到Ij的路段記為rij。

定義1 鄰居汽車。一輛汽車的鄰居汽車指的是在其通信范圍內(nèi)的所有汽車。汽車通過beacon消息發(fā)現(xiàn)其鄰居汽車，這在文獻(xiàn)[1]中有討論。圖1中汽車A的鄰居汽車包括汽車B、C、D和E。

2.2 交通統(tǒng)計

在交通統(tǒng)計模型中，每輛車均保存了地圖中各路段實(shí)時的平均通行時間。統(tǒng)計數(shù)據(jù)的實(shí)時性來自于每輛車所通過的路段的通行時間的記錄。當(dāng)汽車進(jìn)入路段rij時，記錄下當(dāng)前時間為s time;當(dāng)汽車離開該路段進(jìn)入路口I(xiàn)j時，記錄當(dāng)前時間為e time，汽車就能夠計算出該路段的通行時間:

ptij=e time-s time(1)

汽車保存該通行時間作為該路段的通行時間記錄，并保存e time作為該記錄的時間戳(用t表示)。記錄格式如下:

〈ptij， t〉

通行時間記錄是通過汽車間的數(shù)據(jù)擴(kuò)散協(xié)議來更新汽車上的數(shù)據(jù)，更新的汽車重新計算對該路段交通情況的評估。

3 數(shù)據(jù)擴(kuò)散協(xié)議

數(shù)據(jù)擴(kuò)散協(xié)議的目的是:盡可能將實(shí)時數(shù)據(jù)在最短的時間內(nèi)擴(kuò)散到最大范圍的區(qū)域。協(xié)議定義數(shù)據(jù)擴(kuò)散的原則如下:

a)選擇速度最快的鄰居車輛交換數(shù)據(jù)。

b)在直路上，選擇與自身行駛方向相反的車輛，如圖1所示，汽車A會先選擇汽車D作為數(shù)據(jù)擴(kuò)散的對象，這樣就能將信息擴(kuò)散到更遠(yuǎn)的地方。

c)在路口，選擇與自身行駛方向不同的車輛，如圖2所示，汽車A會先選擇汽車C作為數(shù)據(jù)擴(kuò)散的對象，這樣不僅能將信息擴(kuò)散到更遠(yuǎn)的地方，而且也能接收來自其他方向的統(tǒng)計數(shù)據(jù)。

汽車在每個時間間隔Δt時選擇一個鄰居汽車交換數(shù)據(jù)。在交換數(shù)據(jù)的過程中，根據(jù)時間戳選擇最新的記錄更新。汽車以接收記錄的時間戳ti為權(quán)重計算所有通行時間記錄ptij n的加權(quán)平均，作為對該路段的通行時間的估計(用PTij n表示): 

PTij n=ptij 1#8226;t1+ptij 2#8226;t2+…+ptij n#8226;tn/

t1+t2+…+tn(2)

將時間戳作為延時記錄的權(quán)重，是因?yàn)闀r間戳的值越大，記錄就越新，這樣就既保證了延時估計的實(shí)時性，又能考慮到該路段延時的歷史統(tǒng)計。但是這樣估計延時的方法需要汽車保存所有接收的記錄信息，代價會比較大，因此利用遞推方法改進(jìn)式(2)。當(dāng)一輛汽車接收更新路段rij的記錄為〈μ， φ〉，汽車就要重新計算該路段的平均通行時間PTij n和時間戳總和stij n的記錄:

PTij n=PTij n-1#8226;stij n-1+μ#8226;φ/(stij n-1+φ)(3)

然后更新時間戳總和:

stij n=stij n-1+φ(4)

因此，用戶在出發(fā)時，就可以基于汽車上各路段平均通行時間的統(tǒng)計，采用Dijkstra算法，計算出滿足出行計劃要求的行駛路徑，如圖3(a)所示，汽車比較到目的點(diǎn)不同路徑平均通行時間，會選擇用時最短的路徑經(jīng)過B點(diǎn)到目的地，從而在電子地圖上確定出行路徑，如圖3(b)所示。

4 仿真實(shí)驗(yàn)

本章通過仿真實(shí)驗(yàn)討論本文提出的實(shí)時交通統(tǒng)計的性能。在中國成都市的真實(shí)街道地圖上仿真，選擇的區(qū)域范圍為4500×3500 m，包括36個路口，如圖4所示。汽車數(shù)量為500輛，汽車的平均速度在40～80 km/h，汽車的通信半徑均為250 m。MAC協(xié)議采用2 Mbps 802.11。間隔時間Δt為1 s，仿真時間為1 h。圖5顯示的是所有汽車對隨機(jī)選擇的三條路段的通行時間的平均值隨仿真時間的變化情況。可以看到這個變化過程分為三個階段:

a)初始階段。在初始一段時間，沒有車輛通過該路段，因此該路段的記錄為0。

b)調(diào)整階段。有汽車通過該路段后，由于個體差異的影響，使得總的平均通行時間會存在上下波動調(diào)整的現(xiàn)象。c)平穩(wěn)階段。當(dāng)統(tǒng)計記錄和信息擴(kuò)散達(dá)到一定程度后，總的平均通行時間會穩(wěn)定在一個小范圍內(nèi)。

根據(jù)汽車對各路段平均通行時間的估計和路段的長度，可以很容易地得到該路段的平均通行速度的估計。圖6顯示的是所有汽車對各路段平均速度的平均值。圖6(a)給出的是所有汽車對隨機(jī)的三條路段平均速度的平均值隨仿真時間變化的情況，這與圖5的情況類似，同樣可以分為初始、調(diào)整和穩(wěn)定三個階段;(b)顯示的是當(dāng)仿真結(jié)束時所有汽車對各路段平均速度估計的平均值。可以看出大多數(shù)路段統(tǒng)計的平均速度都是在15～18 m/s，這與本文給出的仿真速度范圍是相符合的。

圖7顯示的是對隨機(jī)選擇的三條路段考察、記錄有該路段通行時間信息的汽車數(shù)量隨仿真時間的變化情況。可以看出這個變化過程分為三個階段:

a)初始階段。沒有汽車通過該路段，所以記錄數(shù)為0。

b)擴(kuò)散階段。當(dāng)一有該路段的消息，就會通過網(wǎng)絡(luò)快速擴(kuò)散，記錄數(shù)也會迅速增長。圖中可以這個時間不超過200 s，保證了數(shù)據(jù)的實(shí)時性。

c)更新階段。所有500輛汽車在很短的時間內(nèi)均擁有了

該路段的記錄，剩下的時間就是通過交換信息更新記錄和對交通狀況的重新評估。

5 結(jié)束語

出行計劃是車載自組織網(wǎng)絡(luò)中的一個重要應(yīng)用。本文提出了一種基于分布式實(shí)時交通統(tǒng)計的機(jī)制，每輛汽車分布式地實(shí)時獲取各路段的汽車通行時間，這樣汽車就能夠根據(jù)這些信息進(jìn)行統(tǒng)計并估計各路段的平均通行時間，從而幫助用戶制訂出行計劃。通過仿真實(shí)驗(yàn)可以看出，通過該方法得到的對各路段交通狀況的統(tǒng)計與真實(shí)情況是相符的，而且信息擴(kuò)散時間很短，保證了數(shù)據(jù)的實(shí)時性。

參考文獻(xiàn):

[1]HULL B， BYCHKOVSKY V， ZHANG Y， et al. CarTel: a distributed mobile sensor computing system[C]//Proc of the 4th ACM SenSys.2006.

[2]WISITPONGPHAN N， BAI Fan，MUDALIGE P， et al. On the routing problem in disconnected vehicular Ad hoc networks[C]//Proc of INFOCOM. 2007.

[3]ZHAO Jing， CAO Guo-hong. VADD: vehicle-assisted data delivery in vehicular Ad hoc networks[J]. IEEE Trans on Vehicular Technology，2008，57(3):1910-1922.

[4]BURNS B， BROCK O， LEVINE B. MV routing and capacity buil-ding in disruption tolerant networks[C]//Proc of INFOCOM.2005.

[5]BURGESS J， GALLAGHER B， JENSEN D， et al. Maxprop: routing for vehicle-based disruption-tolerant networking[C]//Proc of INFOCOM. 2006.

[6]DING Yong， WANG Chen， XIAO Li. A static-node assisted adaptive routing protocol in vehicular networks[C]//Proc of VANET.2007.

[7]NAUMOV V， GROSS T R.Connectivity-aware routing (CAR) in vehicular Ad doc networks[C]//Proc of INFOCOM. 2007.