摘  要： 利用車(chē)載自組網(wǎng)方便、靈活、成本低的特點(diǎn)，使用機(jī)會(huì)通信擴(kuò)展車(chē)輛通信范圍，提出一種基于停車(chē)位可用概率的停車(chē)位發(fā)現(xiàn)算法來(lái)解決分布式網(wǎng)絡(luò)中信息不完全下的停車(chē)位發(fā)現(xiàn)問(wèn)題。通過(guò)估算附近可用停車(chē)位在車(chē)輛到達(dá)時(shí)刻的可占用概率，為車(chē)輛分配成功率最大的停車(chē)位。仿真結(jié)果表明，該算法適用于車(chē)載自組網(wǎng)的分布式停車(chē)位算法，平均停車(chē)時(shí)間較短。

　　關(guān)鍵詞： VANET；停車(chē)；機(jī)會(huì)通信；概率

0 引言

　　私人汽車(chē)的激增使城市道路交通量日益增加，引發(fā)了一系列亟待解決的交通問(wèn)題。其中，停車(chē)問(wèn)題給大城市帶來(lái)了沉重的道路通行負(fù)擔(dān)，并成為交通擁堵的重要因素。如何采用先進(jìn)的科學(xué)技術(shù)方法來(lái)解決“停車(chē)難”問(wèn)題[1]，是當(dāng)前城市交通發(fā)展急需解決的問(wèn)題。

　　在停車(chē)位發(fā)現(xiàn)服務(wù)中，拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)變化快速，集中式的架構(gòu)缺乏靈活性和適應(yīng)性，車(chē)載自組織網(wǎng)絡(luò)（Vehicular Ad Hoc Network，VANET）提供了一種分布式停車(chē)位發(fā)現(xiàn)解決方案[2]。在分布式的VANET系統(tǒng)中，車(chē)輛節(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ú)線(xiàn)通信網(wǎng)絡(luò)及多種通信方式。

1 相關(guān)工作

　　2006年Caliskan等[2]提出了一種基于車(chē)載自組網(wǎng)的分布式停車(chē)位發(fā)現(xiàn)模型，通過(guò)階段性信息采集進(jìn)行停車(chē)位計(jì)算。2007年，Sherisha等[4]提出使用停車(chē)場(chǎng)歷史數(shù)據(jù)計(jì)算車(chē)輛目的地附近的停車(chē)位可用概率的方法為車(chē)輛提供停車(chē)引導(dǎo)。Murat[5]對(duì)停車(chē)位發(fā)現(xiàn)問(wèn)題建立了概率預(yù)測(cè)模型，從統(tǒng)計(jì)角度對(duì)區(qū)域停車(chē)概率進(jìn)行了預(yù)測(cè)。2009年Mathur等[6]提出了一種集中式和一種分布式方案來(lái)解決尋找停車(chē)位問(wèn)題，并對(duì)停車(chē)位發(fā)現(xiàn)思想予以評(píng)估。2011年，Kokolak等[7]提出了一種分布式的機(jī)會(huì)停車(chē)位發(fā)現(xiàn)算法，可以擴(kuò)展個(gè)體車(chē)輛的通信范圍。2012年，Andreas[8]對(duì)Murat數(shù)據(jù)收集方法和模型進(jìn)行了改進(jìn)，優(yōu)化了轉(zhuǎn)移矩陣。

　　現(xiàn)有停車(chē)位概率預(yù)測(cè)算法主要是從統(tǒng)計(jì)角度預(yù)測(cè)停車(chē)位空閑的概率，但是不能具體為停車(chē)位發(fā)現(xiàn)提供明確的決策目標(biāo)。本文提出一種基于停車(chē)位可用概率的停車(chē)位發(fā)現(xiàn)算法（An Available Probability based Parking Algorithm，APPA），在分布式系統(tǒng)中使用機(jī)會(huì)通信擴(kuò)展車(chē)輛通信范圍，估算車(chē)輛到達(dá)停車(chē)位時(shí)的車(chē)位可用概率，為車(chē)輛分配最佳的可用停車(chē)位，規(guī)劃有效的行駛路徑。

2 前期假設(shè)與模型分析

　　2.1 停車(chē)位信息獲取

　　限于通信半徑的影響，車(chē)輛節(jié)點(diǎn)能感知的停車(chē)位有限，使用報(bào)文交互擴(kuò)大節(jié)點(diǎn)的感知范圍，使節(jié)點(diǎn)的停車(chē)位決策超出局部VANET網(wǎng)絡(luò)，擴(kuò)大到環(huán)繞車(chē)輛的VANET網(wǎng)絡(luò)群，做出更加符合整體利益的決策。

　　在車(chē)輛行駛過(guò)程中，不斷偵測(cè)可用的停車(chē)位信息，當(dāng)偵測(cè)到可用停車(chē)位時(shí)，記錄該停車(chē)位的位置信息，同時(shí)記錄該停車(chē)位的時(shí)間戳。并在路邊設(shè)置少量的RSU，維護(hù)一個(gè)標(biāo)準(zhǔn)的時(shí)間和一張可用停車(chē)位信息表。當(dāng)車(chē)輛進(jìn)入RSU通信范圍時(shí)，交換可用停車(chē)位的信息，更新可用停車(chē)位信息，使得車(chē)輛能得到超出自身通信范圍的可用停車(chē)位信息。

　　2.2 距離計(jì)算標(biāo)準(zhǔn)

　　從地理位置信息角度考慮，將道路網(wǎng)絡(luò)轉(zhuǎn)化為有向圖。以道路作為拓?fù)渚W(wǎng)絡(luò)中的線(xiàn)，并以停車(chē)位和車(chē)輛作為拓?fù)渚W(wǎng)絡(luò)中的節(jié)點(diǎn)，賦予停車(chē)位和車(chē)輛地理二維坐標(biāo)。轉(zhuǎn)化道路平面圖的同時(shí)做如下約定：

　　（1）對(duì)道路和道路交叉口賦予不同的量化值；

　　（2）對(duì)每個(gè)道路交叉口賦予一個(gè)額外的平均等待時(shí)間；

　　（3）由于算法的依據(jù)是有效距離，因此把等待時(shí)間結(jié)合預(yù)定的車(chē)輛速度轉(zhuǎn)化為距離，這個(gè)距離也是有效距離的組成部分；

　　（4）使用Dijkstra算法計(jì)算節(jié)點(diǎn)間距離。

　　2.3 模型分析

　　在車(chē)輛位置信息不完全的模型中存在兩種對(duì)停車(chē)位有需求的車(chē)輛，一種是加入車(chē)載自組網(wǎng)并實(shí)時(shí)共享信息的車(chē)輛，其他車(chē)輛能通過(guò)車(chē)載網(wǎng)得到這些車(chē)輛的位置信息，位置信息由GPS設(shè)備提供；另一種車(chē)輛是沒(méi)有加入車(chē)載自組網(wǎng)的車(chē)輛，它們自發(fā)且隨機(jī)地搜索停車(chē)位，網(wǎng)絡(luò)中的車(chē)輛無(wú)法得知這些車(chē)輛的數(shù)量和位置等信息。在這種情況下，停車(chē)問(wèn)題變得非常復(fù)雜，如果通過(guò)分配預(yù)約等方式為車(chē)載自組網(wǎng)中的車(chē)輛分配停車(chē)位，則在車(chē)輛向預(yù)定車(chē)位行駛的過(guò)程中，既定停車(chē)位很可能已經(jīng)被不在網(wǎng)絡(luò)中的車(chē)輛所占據(jù)，顯然固定分配的停車(chē)位發(fā)現(xiàn)方式不適用于此模型。

3 主要工作

　　3.1 車(chē)輛到達(dá)時(shí)間計(jì)算

　　在信息交互過(guò)程中，車(chē)輛互相傳播停車(chē)位信息，在獲取的報(bào)文中，如果存在本地鏈表沒(méi)有的車(chē)位，則記錄該車(chē)位位置信息及時(shí)間戳；如果已經(jīng)存在，則更新時(shí)間戳，時(shí)間的記錄以最早發(fā)現(xiàn)該停車(chē)位為準(zhǔn)。

　　當(dāng)車(chē)輛占用某停車(chē)位后，則時(shí)間戳設(shè)為0，并向其他車(chē)輛轉(zhuǎn)發(fā)一次該停車(chē)位信息，同時(shí)將本地的停車(chē)位節(jié)點(diǎn)刪除。當(dāng)其他車(chē)輛接收到時(shí)間戳為0的停車(chē)位信息時(shí)，進(jìn)行相同操作。

　　假設(shè)當(dāng)前時(shí)刻為t，車(chē)輛行駛速度為v，根據(jù)Dijkstra算法計(jì)算得到的車(chē)輛與停車(chē)位之間的最短路徑為D。在得到可用停車(chē)位的位置信息后，可以根據(jù)Dijkstra算法和車(chē)輛的行駛速度估計(jì)得到車(chē)輛相對(duì)每個(gè)停車(chē)位的到達(dá)時(shí)間：

　　3.2 可用車(chē)位獲取概率計(jì)算

　　假設(shè)車(chē)輛vi對(duì)一個(gè)車(chē)位sj的可用概率為P（vi，sj）：

　　式中，P（vi，sj）為T(mén)時(shí)刻停車(chē)位sj被其他車(chē)輛占用的概率。要計(jì)算車(chē)輛到達(dá)時(shí)刻的停車(chē)位可用概率，只需計(jì)算P（vi，sj）即可。

　　P（vi，sj）主要受兩個(gè)因素的影響：一個(gè)是停車(chē)位的空閑時(shí)長(zhǎng)，即從停車(chē)位空閑時(shí)刻開(kāi)始至車(chē)輛發(fā)起停車(chē)請(qǐng)求，這段時(shí)間的車(chē)位沒(méi)有被占用，但車(chē)位被選擇的概率會(huì)隨著時(shí)間的延長(zhǎng)而累積，下一時(shí)刻被占用的概率隨之增大；另一個(gè)是當(dāng)前時(shí)刻至車(chē)輛到達(dá)停車(chē)位，此時(shí)車(chē)輛與其他所有可能駛向此車(chē)位的車(chē)輛進(jìn)行競(jìng)爭(zhēng)，車(chē)輛距離停車(chē)位越近，勝出的可能性越高。

　　在參考文獻(xiàn)[9]中，針對(duì)計(jì)算實(shí)時(shí)可用停車(chē)位的變化進(jìn)行了大量實(shí)驗(yàn)，得到了關(guān)于停車(chē)場(chǎng)各個(gè)時(shí)刻停車(chē)位占用情況的實(shí)驗(yàn)數(shù)據(jù)。本文引用這些實(shí)驗(yàn)數(shù)據(jù)，并通過(guò)分析，將歷史數(shù)據(jù)抽象為函數(shù)，該函數(shù)表示車(chē)位被占用概率隨時(shí)間的變化關(guān)系，簡(jiǎn)化了算法的復(fù)雜度，提高了算法效率。函數(shù)如式（3）所示：

　　其中c=86 400-a+b。

　　令概率Ph（sj）表示在t時(shí)刻可用停車(chē)位sj被任意一輛車(chē)占用的概率，其中包括沒(méi)有加入車(chē)載自組網(wǎng)的車(chē)輛。那么，從停車(chē)位sj空閑時(shí)刻開(kāi)始至當(dāng)前時(shí)刻t，認(rèn)為其在t時(shí)刻后被任意車(chē)輛占用的概率為：

　　Ph（sj）=Pr（t）（4）

　　其中t為當(dāng)前時(shí)刻。

　　設(shè)從停車(chē)位sj空閑時(shí)刻t開(kāi)始，停車(chē)位的空閑時(shí)間和停車(chē)時(shí)間服從指數(shù)分布，則車(chē)輛節(jié)點(diǎn)流量可以看作一個(gè)泊松過(guò)程（λ）。那么，Pn（vi，sj）可以由式（5）計(jì)算得到：

　　Pn（vi，sj）=1-P（K=1）（5）

　　其中，T為記錄的車(chē)輛到達(dá)時(shí)刻，P（K=1）可看作到T時(shí)刻停車(chē)位被占用的概率。

　　那么，最終的停車(chē)位可用概率可由式（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í)刻的停車(chē)位可用概率越高。

　　3.3 算法描述

　　車(chē)輛在行駛過(guò)程中，不斷偵聽(tīng)感知范圍內(nèi)的可用停車(chē)位，同時(shí)進(jìn)行車(chē)間報(bào)文交互。當(dāng)發(fā)起停車(chē)請(qǐng)求時(shí)，計(jì)算車(chē)輛與每個(gè)可用停車(chē)位之間的有效距離，并通過(guò)APPA算法計(jì)算每個(gè)可用停車(chē)位的概率，選擇概率最高的停車(chē)位并向其行駛，在行駛過(guò)程中，不斷重復(fù)進(jìn)行偵聽(tīng)和概率更新，始終駛向最大可用概率的停車(chē)位；當(dāng)與某停車(chē)位距離D小于閾值Z（Z=v）時(shí)，占用停車(chē)位并將此停車(chē)位的時(shí)間戳置0。算法偽代碼如下：

　　FUNCTION APPA（S）{

　　for所有的停車(chē)位節(jié)點(diǎn)S

　　{  計(jì)算車(chē)輛與停車(chē)位之間距離D

　　IF D<Z

　　{

　　占用停車(chē)位，時(shí)間戳置0

　　END

　　}

　　}

　　for所有的停車(chē)位節(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）車(chē)位方向行駛1 s，同時(shí)更新S

　　RETURN FUNCTION APPA（S）

　　}

4 仿真分析

　　4.1 場(chǎng)景描述

　　本文在VanetMobiSim框架下進(jìn)行仿真，仿真過(guò)程中，每當(dāng)一輛車(chē)占用一個(gè)停車(chē)位時(shí)，保存記錄這輛車(chē)找尋停車(chē)位所花費(fèi)的時(shí)間，并在整個(gè)道路上隨機(jī)位置重新生成一個(gè)車(chē)輛，在另一隨機(jī)位置重新生成一個(gè)可用停車(chē)位。這可看作道路交通中的實(shí)時(shí)變化因素，更加符合實(shí)際情況。具體參數(shù)見(jiàn)表1。

　　4.2 仿真分析

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

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

　　圖2表示停車(chē)位平均空閑時(shí)間的關(guān)系曲線(xiàn)。由圖2可知，APPA算法的停車(chē)位平均空閑時(shí)間與就近原則方法接近，略?xún)?yōu)于就近原則。當(dāng)可用停車(chē)位數(shù)目較多時(shí)，車(chē)輛有更多的停車(chē)選擇，APPA算法的決策擁有最大的成功概率；在車(chē)輛數(shù)目大于停車(chē)位數(shù)目時(shí)，車(chē)輛之間存在激烈的競(jìng)爭(zhēng)，由于APPA算法計(jì)算了停車(chē)位從空閑時(shí)刻開(kāi)始至發(fā)起停車(chē)請(qǐng)求這段時(shí)間對(duì)停車(chē)占用概率的影響，因此能提高車(chē)輛尋找車(chē)位的有效性。

5 結(jié)束語(yǔ)

　　本文對(duì)分布式系統(tǒng)中車(chē)輛和停車(chē)位位置信息不完全的模型進(jìn)行研究，提出了一種基于停車(chē)位可用概率的停車(chē)位發(fā)現(xiàn)算法來(lái)解決分布式網(wǎng)絡(luò)中信息不完全情況下的停車(chē)位發(fā)現(xiàn)問(wèn)題。通過(guò)仿真分析得知，在系統(tǒng)模型中，APPA算法有較大的優(yōu)越性，其能更好地應(yīng)對(duì)信息不完全的情形，縮短車(chē)輛的平均停車(chē)位發(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的車(chē)載自組網(wǎng)的研究與仿真[D].武漢：武漢理工大學(xué)，2010.