摘 要: 利用車載自組網(wǎng)方便、靈活、成本低的特點(diǎn),使用機(jī)會(huì)通信擴(kuò)展車輛通信范圍,提出一種基于停車位可用概率的停車位發(fā)現(xiàn)算法來(lái)解決分布式網(wǎng)絡(luò)中信息不完全下的停車位發(fā)現(xiàn)問(wèn)題。通過(guò)估算附近可用停車位在車輛到達(dá)時(shí)刻的可占用概率,為車輛分配成功率最大的停車位。仿真結(jié)果表明,該算法適用于車載自組網(wǎng)的分布式停車位算法,平均停車時(shí)間較短。
關(guān)鍵詞: VANET;停車;機(jī)會(huì)通信;概率
0 引言
私人汽車的激增使城市道路交通量日益增加,引發(fā)了一系列亟待解決的交通問(wèn)題。其中,停車問(wèn)題給大城市帶來(lái)了沉重的道路通行負(fù)擔(dān),并成為交通擁堵的重要因素。如何采用先進(jìn)的科學(xué)技術(shù)方法來(lái)解決“停車難”問(wèn)題[1],是當(dāng)前城市交通發(fā)展急需解決的問(wèn)題。
在停車位發(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é)點(diǎn)通過(guò)與通信范圍內(nèi)的節(jié)點(diǎn)組成臨時(shí)的Ad hoc網(wǎng)絡(luò)進(jìn)行多跳通信、交換信息[3],VANET在智能交通系統(tǒng)中起著重要作用,為系統(tǒng)提供統(tǒng)一的無(wú)線通信網(wǎng)絡(luò)及多種通信方式。
1 相關(guān)工作
2006年Caliskan等[2]提出了一種基于車載自組網(wǎng)的分布式停車位發(fā)現(xiàn)模型,通過(guò)階段性信息采集進(jìn)行停車位計(jì)算。2007年,Sherisha等[4]提出使用停車場(chǎng)歷史數(shù)據(jù)計(jì)算車輛目的地附近的停車位可用概率的方法為車輛提供停車引導(dǎo)。Murat[5]對(duì)停車位發(fā)現(xiàn)問(wèn)題建立了概率預(yù)測(cè)模型,從統(tǒng)計(jì)角度對(duì)區(qū)域停車概率進(jìn)行了預(yù)測(cè)。2009年Mathur等[6]提出了一種集中式和一種分布式方案來(lái)解決尋找停車位問(wèn)題,并對(duì)停車位發(fā)現(xiàn)思想予以評(píng)估。2011年,Kokolak等[7]提出了一種分布式的機(jī)會(huì)停車位發(fā)現(xiàn)算法,可以擴(kuò)展個(gè)體車輛的通信范圍。2012年,Andreas[8]對(duì)Murat數(shù)據(jù)收集方法和模型進(jìn)行了改進(jìn),優(yōu)化了轉(zhuǎn)移矩陣。
現(xiàn)有停車位概率預(yù)測(cè)算法主要是從統(tǒng)計(jì)角度預(yù)測(cè)停車位空閑的概率,但是不能具體為停車位發(fā)現(xiàn)提供明確的決策目標(biāo)。本文提出一種基于停車位可用概率的停車位發(fā)現(xiàn)算法(An Available Probability based Parking Algorithm,APPA),在分布式系統(tǒng)中使用機(jī)會(huì)通信擴(kuò)展車輛通信范圍,估算車輛到達(dá)停車位時(shí)的車位可用概率,為車輛分配最佳的可用停車位,規(guī)劃有效的行駛路徑。
2 前期假設(shè)與模型分析
2.1 停車位信息獲取
限于通信半徑的影響,車輛節(jié)點(diǎn)能感知的停車位有限,使用報(bào)文交互擴(kuò)大節(jié)點(diǎn)的感知范圍,使節(jié)點(diǎn)的停車位決策超出局部VANET網(wǎng)絡(luò),擴(kuò)大到環(huán)繞車輛的VANET網(wǎng)絡(luò)群,做出更加符合整體利益的決策。
在車輛行駛過(guò)程中,不斷偵測(cè)可用的停車位信息,當(dāng)偵測(cè)到可用停車位時(shí),記錄該停車位的位置信息,同時(shí)記錄該停車位的時(shí)間戳。并在路邊設(shè)置少量的RSU,維護(hù)一個(gè)標(biāo)準(zhǔn)的時(shí)間和一張可用停車位信息表。當(dāng)車輛進(jìn)入RSU通信范圍時(shí),交換可用停車位的信息,更新可用停車位信息,使得車輛能得到超出自身通信范圍的可用停車位信息。
2.2 距離計(jì)算標(biāo)準(zhǔn)
從地理位置信息角度考慮,將道路網(wǎng)絡(luò)轉(zhuǎn)化為有向圖。以道路作為拓?fù)渚W(wǎng)絡(luò)中的線,并以停車位和車輛作為拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn),賦予停車位和車輛地理二維坐標(biāo)。轉(zhuǎn)化道路平面圖的同時(shí)做如下約定:
(1)對(duì)道路和道路交叉口賦予不同的量化值;
(2)對(duì)每個(gè)道路交叉口賦予一個(gè)額外的平均等待時(shí)間;
?。?)由于算法的依據(jù)是有效距離,因此把等待時(shí)間結(jié)合預(yù)定的車輛速度轉(zhuǎn)化為距離,這個(gè)距離也是有效距離的組成部分;
(4)使用Dijkstra算法計(jì)算節(jié)點(diǎn)間距離。
2.3 模型分析
在車輛位置信息不完全的模型中存在兩種對(duì)停車位有需求的車輛,一種是加入車載自組網(wǎng)并實(shí)時(shí)共享信息的車輛,其他車輛能通過(guò)車載網(wǎng)得到這些車輛的位置信息,位置信息由GPS設(shè)備提供;另一種車輛是沒(méi)有加入車載自組網(wǎng)的車輛,它們自發(fā)且隨機(jī)地搜索停車位,網(wǎng)絡(luò)中的車輛無(wú)法得知這些車輛的數(shù)量和位置等信息。在這種情況下,停車問(wèn)題變得非常復(fù)雜,如果通過(guò)分配預(yù)約等方式為車載自組網(wǎng)中的車輛分配停車位,則在車輛向預(yù)定車位行駛的過(guò)程中,既定停車位很可能已經(jīng)被不在網(wǎng)絡(luò)中的車輛所占據(jù),顯然固定分配的停車位發(fā)現(xiàn)方式不適用于此模型。
3 主要工作
3.1 車輛到達(dá)時(shí)間計(jì)算
在信息交互過(guò)程中,車輛互相傳播停車位信息,在獲取的報(bào)文中,如果存在本地鏈表沒(méi)有的車位,則記錄該車位位置信息及時(shí)間戳;如果已經(jīng)存在,則更新時(shí)間戳,時(shí)間的記錄以最早發(fā)現(xiàn)該停車位為準(zhǔn)。
當(dāng)車輛占用某停車位后,則時(shí)間戳設(shè)為0,并向其他車輛轉(zhuǎn)發(fā)一次該停車位信息,同時(shí)將本地的停車位節(jié)點(diǎn)刪除。當(dāng)其他車輛接收到時(shí)間戳為0的停車位信息時(shí),進(jìn)行相同操作。
假設(shè)當(dāng)前時(shí)刻為t,車輛行駛速度為v,根據(jù)Dijkstra算法計(jì)算得到的車輛與停車位之間的最短路徑為D。在得到可用停車位的位置信息后,可以根據(jù)Dijkstra算法和車輛的行駛速度估計(jì)得到車輛相對(duì)每個(gè)停車位的到達(dá)時(shí)間:
3.2 可用車位獲取概率計(jì)算
假設(shè)車輛vi對(duì)一個(gè)車位sj的可用概率為P(vi,sj):
式中,P(vi,sj)為T時(shí)刻停車位sj被其他車輛占用的概率。要計(jì)算車輛到達(dá)時(shí)刻的停車位可用概率,只需計(jì)算P(vi,sj)即可。
P(vi,sj)主要受兩個(gè)因素的影響:一個(gè)是停車位的空閑時(shí)長(zhǎng),即從停車位空閑時(shí)刻開(kāi)始至車輛發(fā)起停車請(qǐng)求,這段時(shí)間的車位沒(méi)有被占用,但車位被選擇的概率會(huì)隨著時(shí)間的延長(zhǎng)而累積,下一時(shí)刻被占用的概率隨之增大;另一個(gè)是當(dāng)前時(shí)刻至車輛到達(dá)停車位,此時(shí)車輛與其他所有可能駛向此車位的車輛進(jìn)行競(jìng)爭(zhēng),車輛距離停車位越近,勝出的可能性越高。
在參考文獻(xiàn)[9]中,針對(duì)計(jì)算實(shí)時(shí)可用停車位的變化進(jìn)行了大量實(shí)驗(yàn),得到了關(guān)于停車場(chǎng)各個(gè)時(shí)刻停車位占用情況的實(shí)驗(yàn)數(shù)據(jù)。本文引用這些實(shí)驗(yàn)數(shù)據(jù),并通過(guò)分析,將歷史數(shù)據(jù)抽象為函數(shù),該函數(shù)表示車位被占用概率隨時(shí)間的變化關(guān)系,簡(jiǎn)化了算法的復(fù)雜度,提高了算法效率。函數(shù)如式(3)所示:
其中c=86 400-a+b。
令概率Ph(sj)表示在t時(shí)刻可用停車位sj被任意一輛車占用的概率,其中包括沒(méi)有加入車載自組網(wǎng)的車輛。那么,從停車位sj空閑時(shí)刻開(kāi)始至當(dāng)前時(shí)刻t,認(rèn)為其在t時(shí)刻后被任意車輛占用的概率為:
Ph(sj)=Pr(t)(4)
其中t為當(dāng)前時(shí)刻。
設(shè)從停車位sj空閑時(shí)刻t開(kāi)始,停車位的空閑時(shí)間和停車時(shí)間服從指數(shù)分布,則車輛節(jié)點(diǎn)流量可以看作一個(gè)泊松過(guò)程(λ)。那么,Pn(vi,sj)可以由式(5)計(jì)算得到:
Pn(vi,sj)=1-P(K=1)(5)
其中,T為記錄的車輛到達(dá)時(shí)刻,P(K=1)可看作到T時(shí)刻停車位被占用的概率。
那么,最終的停車位可用概率可由式(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)越大,則到達(dá)時(shí)刻的停車位可用概率越高。
3.3 算法描述
車輛在行駛過(guò)程中,不斷偵聽(tīng)感知范圍內(nèi)的可用停車位,同時(shí)進(jìn)行車間報(bào)文交互。當(dāng)發(fā)起停車請(qǐng)求時(shí),計(jì)算車輛與每個(gè)可用停車位之間的有效距離,并通過(guò)APPA算法計(jì)算每個(gè)可用停車位的概率,選擇概率最高的停車位并向其行駛,在行駛過(guò)程中,不斷重復(fù)進(jìn)行偵聽(tīng)和概率更新,始終駛向最大可用概率的停車位;當(dāng)與某停車位距離D小于閾值Z(Z=v)時(shí),占用停車位并將此停車位的時(shí)間戳置0。算法偽代碼如下:
FUNCTION APPA(S){
for所有的停車位節(jié)點(diǎn)S
{ 計(jì)算車輛與停車位之間距離D
IF D<Z
{
占用停車位,時(shí)間戳置0
END
}
}
for所有的停車位節(jié)點(diǎn)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,同時(shí)更新S
RETURN FUNCTION APPA(S)
}
4 仿真分析
4.1 場(chǎng)景描述
本文在VanetMobiSim框架下進(jìn)行仿真,仿真過(guò)程中,每當(dāng)一輛車占用一個(gè)停車位時(shí),保存記錄這輛車找尋停車位所花費(fèi)的時(shí)間,并在整個(gè)道路上隨機(jī)位置重新生成一個(gè)車輛,在另一隨機(jī)位置重新生成一個(gè)可用停車位。這可看作道路交通中的實(shí)時(shí)變化因素,更加符合實(shí)際情況。具體參數(shù)見(jiàn)表1。
4.2 仿真分析
仿真場(chǎng)景中停車位節(jié)點(diǎn)數(shù)為30,車輛節(jié)點(diǎn)數(shù)為5~80,且設(shè)定隱藏車輛與非隱藏車輛數(shù)量比約為1∶1。
圖1表示停車位節(jié)點(diǎn)數(shù)和車輛平均行駛時(shí)間的關(guān)系曲線。當(dāng)車輛數(shù)少于停車位時(shí),每個(gè)車輛都能分配到停車位,APPA算法根據(jù)有限的信息找到最優(yōu)的車位,產(chǎn)生的額外行車開(kāi)銷較小,且在行駛過(guò)程中,實(shí)時(shí)地更新數(shù)據(jù),使車輛更大概率獲取位置更優(yōu)的可用停車位;當(dāng)車輛數(shù)目多于停車位時(shí),APPA算法能根據(jù)已知信息做出更加合理的決策,使車輛能在車位很少時(shí)更快地找到可用停車位。
圖2表示停車位平均空閑時(shí)間的關(guān)系曲線。由圖2可知,APPA算法的停車位平均空閑時(shí)間與就近原則方法接近,略優(yōu)于就近原則。當(dāng)可用停車位數(shù)目較多時(shí),車輛有更多的停車選擇,APPA算法的決策擁有最大的成功概率;在車輛數(shù)目大于停車位數(shù)目時(shí),車輛之間存在激烈的競(jìng)爭(zhēng),由于APPA算法計(jì)算了停車位從空閑時(shí)刻開(kāi)始至發(fā)起停車請(qǐng)求這段時(shí)間對(duì)停車占用概率的影響,因此能提高車輛尋找車位的有效性。
5 結(jié)束語(yǔ)
本文對(duì)分布式系統(tǒng)中車輛和停車位位置信息不完全的模型進(jìn)行研究,提出了一種基于停車位可用概率的停車位發(fā)現(xiàn)算法來(lái)解決分布式網(wǎng)絡(luò)中信息不完全情況下的停車位發(fā)現(xiàn)問(wèn)題。通過(guò)仿真分析得知,在系統(tǒng)模型中,APPA算法有較大的優(yōu)越性,其能更好地應(yīng)對(duì)信息不完全的情形,縮短車輛的平均停車位發(fā)現(xiàn)時(shí)間。
參考文獻(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.