摘 要: 利用車載自組網(wǎng)方便、靈活,、成本低的特點,,使用機會通信擴展車輛通信范圍,提出一種基于停車位可用概率的停車位發(fā)現(xiàn)算法來解決分布式網(wǎng)絡(luò)中信息不完全下的停車位發(fā)現(xiàn)問題,。通過估算附近可用停車位在車輛到達時刻的可占用概率,為車輛分配成功率最大的停車位,。仿真結(jié)果表明,,該算法適用于車載自組網(wǎng)的分布式停車位算法,平均停車時間較短,。
關(guān)鍵詞: VANET,;停車;機會通信,;概率
0 引言
私人汽車的激增使城市道路交通量日益增加,,引發(fā)了一系列亟待解決的交通問題。其中,,停車問題給大城市帶來了沉重的道路通行負(fù)擔(dān),,并成為交通擁堵的重要因素。如何采用先進的科學(xué)技術(shù)方法來解決“停車難”問題[1],,是當(dāng)前城市交通發(fā)展急需解決的問題,。
在停車位發(fā)現(xiàn)服務(wù)中,拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)變化快速,,集中式的架構(gòu)缺乏靈活性和適應(yīng)性,,車載自組織網(wǎng)絡(luò)(Vehicular Ad Hoc Network,VANET)提供了一種分布式停車位發(fā)現(xiàn)解決方案[2],。在分布式的VANET系統(tǒng)中,,車輛節(jié)點通過與通信范圍內(nèi)的節(jié)點組成臨時的Ad hoc網(wǎng)絡(luò)進行多跳通信、交換信息[3],,VANET在智能交通系統(tǒng)中起著重要作用,,為系統(tǒng)提供統(tǒng)一的無線通信網(wǎng)絡(luò)及多種通信方式,。
1 相關(guān)工作
2006年Caliskan等[2]提出了一種基于車載自組網(wǎng)的分布式停車位發(fā)現(xiàn)模型,通過階段性信息采集進行停車位計算,。2007年,,Sherisha等[4]提出使用停車場歷史數(shù)據(jù)計算車輛目的地附近的停車位可用概率的方法為車輛提供停車引導(dǎo)。Murat[5]對停車位發(fā)現(xiàn)問題建立了概率預(yù)測模型,,從統(tǒng)計角度對區(qū)域停車概率進行了預(yù)測,。2009年Mathur等[6]提出了一種集中式和一種分布式方案來解決尋找停車位問題,并對停車位發(fā)現(xiàn)思想予以評估,。2011年,,Kokolak等[7]提出了一種分布式的機會停車位發(fā)現(xiàn)算法,可以擴展個體車輛的通信范圍,。2012年,,Andreas[8]對Murat數(shù)據(jù)收集方法和模型進行了改進,優(yōu)化了轉(zhuǎn)移矩陣,。
現(xiàn)有停車位概率預(yù)測算法主要是從統(tǒng)計角度預(yù)測停車位空閑的概率,,但是不能具體為停車位發(fā)現(xiàn)提供明確的決策目標(biāo)。本文提出一種基于停車位可用概率的停車位發(fā)現(xiàn)算法(An Available Probability based Parking Algorithm,,APPA),,在分布式系統(tǒng)中使用機會通信擴展車輛通信范圍,估算車輛到達停車位時的車位可用概率,,為車輛分配最佳的可用停車位,,規(guī)劃有效的行駛路徑。
2 前期假設(shè)與模型分析
2.1 停車位信息獲取
限于通信半徑的影響,,車輛節(jié)點能感知的停車位有限,,使用報文交互擴大節(jié)點的感知范圍,使節(jié)點的停車位決策超出局部VANET網(wǎng)絡(luò),,擴大到環(huán)繞車輛的VANET網(wǎng)絡(luò)群,,做出更加符合整體利益的決策。
在車輛行駛過程中,,不斷偵測可用的停車位信息,,當(dāng)偵測到可用停車位時,記錄該停車位的位置信息,,同時記錄該停車位的時間戳,。并在路邊設(shè)置少量的RSU,維護一個標(biāo)準(zhǔn)的時間和一張可用停車位信息表,。當(dāng)車輛進入RSU通信范圍時,,交換可用停車位的信息,更新可用停車位信息,使得車輛能得到超出自身通信范圍的可用停車位信息,。
2.2 距離計算標(biāo)準(zhǔn)
從地理位置信息角度考慮,,將道路網(wǎng)絡(luò)轉(zhuǎn)化為有向圖。以道路作為拓?fù)渚W(wǎng)絡(luò)中的線,,并以停車位和車輛作為拓?fù)渚W(wǎng)絡(luò)中的節(jié)點,,賦予停車位和車輛地理二維坐標(biāo)。轉(zhuǎn)化道路平面圖的同時做如下約定:
?。?)對道路和道路交叉口賦予不同的量化值,;
(2)對每個道路交叉口賦予一個額外的平均等待時間,;
?。?)由于算法的依據(jù)是有效距離,因此把等待時間結(jié)合預(yù)定的車輛速度轉(zhuǎn)化為距離,,這個距離也是有效距離的組成部分,;
(4)使用Dijkstra算法計算節(jié)點間距離,。
2.3 模型分析
在車輛位置信息不完全的模型中存在兩種對停車位有需求的車輛,,一種是加入車載自組網(wǎng)并實時共享信息的車輛,其他車輛能通過車載網(wǎng)得到這些車輛的位置信息,,位置信息由GPS設(shè)備提供,;另一種車輛是沒有加入車載自組網(wǎng)的車輛,它們自發(fā)且隨機地搜索停車位,,網(wǎng)絡(luò)中的車輛無法得知這些車輛的數(shù)量和位置等信息。在這種情況下,,停車問題變得非常復(fù)雜,,如果通過分配預(yù)約等方式為車載自組網(wǎng)中的車輛分配停車位,則在車輛向預(yù)定車位行駛的過程中,,既定停車位很可能已經(jīng)被不在網(wǎng)絡(luò)中的車輛所占據(jù),,顯然固定分配的停車位發(fā)現(xiàn)方式不適用于此模型。
3 主要工作
3.1 車輛到達時間計算
在信息交互過程中,,車輛互相傳播停車位信息,,在獲取的報文中,如果存在本地鏈表沒有的車位,,則記錄該車位位置信息及時間戳,;如果已經(jīng)存在,則更新時間戳,,時間的記錄以最早發(fā)現(xiàn)該停車位為準(zhǔn),。
當(dāng)車輛占用某停車位后,則時間戳設(shè)為0,,并向其他車輛轉(zhuǎn)發(fā)一次該停車位信息,,同時將本地的停車位節(jié)點刪除,。當(dāng)其他車輛接收到時間戳為0的停車位信息時,進行相同操作,。
假設(shè)當(dāng)前時刻為t,,車輛行駛速度為v,根據(jù)Dijkstra算法計算得到的車輛與停車位之間的最短路徑為D,。在得到可用停車位的位置信息后,,可以根據(jù)Dijkstra算法和車輛的行駛速度估計得到車輛相對每個停車位的到達時間:
3.2 可用車位獲取概率計算
假設(shè)車輛vi對一個車位sj的可用概率為P(vi,sj):
式中,,P(vi,,sj)為T時刻停車位sj被其他車輛占用的概率。要計算車輛到達時刻的停車位可用概率,,只需計算P(vi,,sj)即可。
P(vi,,sj)主要受兩個因素的影響:一個是停車位的空閑時長,,即從停車位空閑時刻開始至車輛發(fā)起停車請求,這段時間的車位沒有被占用,,但車位被選擇的概率會隨著時間的延長而累積,,下一時刻被占用的概率隨之增大;另一個是當(dāng)前時刻至車輛到達停車位,,此時車輛與其他所有可能駛向此車位的車輛進行競爭,,車輛距離停車位越近,勝出的可能性越高,。
在參考文獻[9]中,,針對計算實時可用停車位的變化進行了大量實驗,得到了關(guān)于停車場各個時刻停車位占用情況的實驗數(shù)據(jù),。本文引用這些實驗數(shù)據(jù),,并通過分析,將歷史數(shù)據(jù)抽象為函數(shù),,該函數(shù)表示車位被占用概率隨時間的變化關(guān)系,,簡化了算法的復(fù)雜度,提高了算法效率,。函數(shù)如式(3)所示:
其中c=86 400-a+b,。
令概率Ph(sj)表示在t時刻可用停車位sj被任意一輛車占用的概率,其中包括沒有加入車載自組網(wǎng)的車輛,。那么,,從停車位sj空閑時刻開始至當(dāng)前時刻t,認(rèn)為其在t時刻后被任意車輛占用的概率為:
Ph(sj)=Pr(t)(4)
其中t為當(dāng)前時刻。
設(shè)從停車位sj空閑時刻t開始,,停車位的空閑時間和停車時間服從指數(shù)分布,,則車輛節(jié)點流量可以看作一個泊松過程(λ)。那么,,Pn(vi,,sj)可以由式(5)計算得到:
Pn(vi,sj)=1-P(K=1)(5)
其中,,T為記錄的車輛到達時刻,,P(K=1)可看作到T時刻停車位被占用的概率。
那么,,最終的停車位可用概率可由式(6)得到:
P(vi,,sj)=(1-Ph(sj))·Pn(vi,sj)(6)
即P(vi,,sj)可以由式(7)表示:
P(vi,,sj)=1-P(vi,sj)=(1-Ph(sj))·Pn(vi,,sj)(7)
P(vi,,sj)越大,則到達時刻的停車位可用概率越高,。
3.3 算法描述
車輛在行駛過程中,,不斷偵聽感知范圍內(nèi)的可用停車位,同時進行車間報文交互,。當(dāng)發(fā)起停車請求時,,計算車輛與每個可用停車位之間的有效距離,并通過APPA算法計算每個可用停車位的概率,,選擇概率最高的停車位并向其行駛,,在行駛過程中,不斷重復(fù)進行偵聽和概率更新,,始終駛向最大可用概率的停車位,;當(dāng)與某停車位距離D小于閾值Z(Z=v)時,,占用停車位并將此停車位的時間戳置0,。算法偽代碼如下:
FUNCTION APPA(S){
for所有的停車位節(jié)點S
{ 計算車輛與停車位之間距離D
IF D<Z
{
占用停車位,時間戳置0
END
}
}
for所有的停車位節(jié)點S
{
Ph(sj)=Pr(t)
Pn(vi,,sj)=1-P(K=1)
P(vi,,sj)=(1-Ph(sj))·Pn(vi,sj)
}
Pmax(vi)=max(1-P(vi,,sj))
向Pmax(vi)車位方向行駛1 s,,同時更新S
RETURN FUNCTION APPA(S)
}
4 仿真分析
4.1 場景描述
本文在VanetMobiSim框架下進行仿真,仿真過程中,每當(dāng)一輛車占用一個停車位時,,保存記錄這輛車找尋停車位所花費的時間,,并在整個道路上隨機位置重新生成一個車輛,在另一隨機位置重新生成一個可用停車位,。這可看作道路交通中的實時變化因素,,更加符合實際情況。具體參數(shù)見表1,。
4.2 仿真分析
仿真場景中停車位節(jié)點數(shù)為30,,車輛節(jié)點數(shù)為5~80,且設(shè)定隱藏車輛與非隱藏車輛數(shù)量比約為1∶1,。
圖1表示停車位節(jié)點數(shù)和車輛平均行駛時間的關(guān)系曲線,。當(dāng)車輛數(shù)少于停車位時,每個車輛都能分配到停車位,,APPA算法根據(jù)有限的信息找到最優(yōu)的車位,,產(chǎn)生的額外行車開銷較小,且在行駛過程中,,實時地更新數(shù)據(jù),,使車輛更大概率獲取位置更優(yōu)的可用停車位;當(dāng)車輛數(shù)目多于停車位時,,APPA算法能根據(jù)已知信息做出更加合理的決策,,使車輛能在車位很少時更快地找到可用停車位。
圖2表示停車位平均空閑時間的關(guān)系曲線,。由圖2可知,,APPA算法的停車位平均空閑時間與就近原則方法接近,略優(yōu)于就近原則,。當(dāng)可用停車位數(shù)目較多時,,車輛有更多的停車選擇,APPA算法的決策擁有最大的成功概率,;在車輛數(shù)目大于停車位數(shù)目時,,車輛之間存在激烈的競爭,由于APPA算法計算了停車位從空閑時刻開始至發(fā)起停車請求這段時間對停車占用概率的影響,,因此能提高車輛尋找車位的有效性,。
5 結(jié)束語
本文對分布式系統(tǒng)中車輛和停車位位置信息不完全的模型進行研究,提出了一種基于停車位可用概率的停車位發(fā)現(xiàn)算法來解決分布式網(wǎng)絡(luò)中信息不完全情況下的停車位發(fā)現(xiàn)問題,。通過仿真分析得知,,在系統(tǒng)模型中,APPA算法有較大的優(yōu)越性,,其能更好地應(yīng)對信息不完全的情形,,縮短車輛的平均停車位發(fā)現(xiàn)時間,。
參考文獻
[1] DELOT T, ILARRI S,, LECOMTE S,, et al. Sharing with caution: Managing parking spaces in vehicular networks[J]. Mobile Information Systems, 2013,,9(1):69-98.
[2] CALISKAN M,, GRAUPNER D, MAUVE M. Decentralized discovery of free parking places[C]. Proceedings of the 3rd International Workshop on Vehicular ad hoc Networks. ACM,, 2006: 30-39.
[3] YOUSEFI S,, MOUSAVI M S, FATHY M. Vehicular ad hoc networks(VANETs): challenges and perspectives[C]. ITS Telecommunications Proceedings,, 2006 6th International Conference on. IEEE,, 2006: 761-766.
[4] PULLOLA S, ATREY P K,, EL SADDIK A. Towards an intelligent GPS-based vehicle navigation system for finding street parking lots[C]. Signal Processing and Communications,, 2007. ICSPC 2007:1251-1254.
[5] CALISKAN M, BARTHELS A,, SCHEUERMANN B,, et al. Predicting parking lot occupancy in vehicular ad hoc networks[C]. Vehicular Technology Conference, 2007. IEEE 65th. IEEE,, 2007: 277-281.
[6] MATHUR S,, KAUL S, GRUTESER M,, et al. ParkNet: a mobile sensor network for harvesting real time vehicular parking information[C]. Proceedings of the 2009 MobiHoc S 3 workshop on MobiHoc S 3. ACM,, 2009: 25-28.
[7] KOKOLAKI E, KARALIOPOULOS M,, STAVRAKAKIS I. Opportunistically assisted parking service discovery: now it helps,, now it does not[J]. Pervasive and Mobile Computing, 2012,, 8(2): 210-227.
[8] KLAPPENECKER A,, LEE H, WELCH J L. Finding available parking spaces made Easy[C]. Proceedings of the 6th International Workshop on Foundations of Mobile Computing. ACM,, 2010: 49-52.
[9] 魯忠輝.基于VanetMobiSim/NS-2的車載自組網(wǎng)的研究與仿真[D].武漢:武漢理工大學(xué),,2010.