《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 可編程邏輯 > 設(shè)計應(yīng)用 > 基于停車位可用概率的停車位發(fā)現(xiàn)算法
基于停車位可用概率的停車位發(fā)現(xiàn)算法
2015年微型機與應(yīng)用第1期
金 康1,,2,李德敏1,,2,,湯海涅1,2,,李 彤1,,2
(1.東華大學(xué),上海 201620,; 2.數(shù)字化紡織服裝技術(shù)教育部工程研究中心,,上海 201620)
摘要: 利用車載自組網(wǎng)方便,、靈活、成本低的特點,,使用機會通信擴展車輛通信范圍,,提出一種基于停車位可用概率的停車位發(fā)現(xiàn)算法來解決分布式網(wǎng)絡(luò)中信息不完全下的停車位發(fā)現(xiàn)問題。通過估算附近可用停車位在車輛到達時刻的可占用概率,,為車輛分配成功率最大的停車位,。仿真結(jié)果表明,該算法適用于車載自組網(wǎng)的分布式停車位算法,,平均停車時間較短,。
關(guān)鍵詞: VANET 停車 機會通信 概率
Abstract:
Key words :

  摘  要: 利用車載自組網(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算法和車輛的行駛速度估計得到車輛相對每個停車位的到達時間:

  1.png

  3.2 可用車位獲取概率計算

  假設(shè)車輛vi對一個車位sj的可用概率為P(vi,sj):

  2.png

  式中,,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)所示:

  3.png

  其中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,。

003.jpg

  4.2 仿真分析

  仿真場景中停車位節(jié)點數(shù)為30,,車輛節(jié)點數(shù)為5~80,且設(shè)定隱藏車輛與非隱藏車輛數(shù)量比約為1∶1,。

001.jpg

  圖1表示停車位節(jié)點數(shù)和車輛平均行駛時間的關(guān)系曲線,。當(dāng)車輛數(shù)少于停車位時,每個車輛都能分配到停車位,,APPA算法根據(jù)有限的信息找到最優(yōu)的車位,,產(chǎn)生的額外行車開銷較小,且在行駛過程中,,實時地更新數(shù)據(jù),,使車輛更大概率獲取位置更優(yōu)的可用停車位;當(dāng)車輛數(shù)目多于停車位時,,APPA算法能根據(jù)已知信息做出更加合理的決策,,使車輛能在車位很少時更快地找到可用停車位。

002.jpg

  圖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.


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。