摘  要： 利用車載自組網方便、靈活、成本低的特點，使用機會通信擴展車輛通信范圍，提出一種基于停車位可用概率的停車位發現算法來解決分布式網絡中信息不完全下的停車位發現問題。通過估算附近可用停車位在車輛到達時刻的可占用概率，為車輛分配成功率最大的停車位。仿真結果表明，該算法適用于車載自組網的分布式停車位算法，平均停車時間較短。

　　關鍵詞： VANET；停車；機會通信；概率

0 引言

　　私人汽車的激增使城市道路交通量日益增加，引發了一系列亟待解決的交通問題。其中，停車問題給大城市帶來了沉重的道路通行負擔，并成為交通擁堵的重要因素。如何采用先進的科學技術方法來解決“停車難”問題[1]，是當前城市交通發展急需解決的問題。

　　在停車位發現服務中，拓撲網絡結構變化快速，集中式的架構缺乏靈活性和適應性，車載自組織網絡（Vehicular Ad Hoc Network，VANET）提供了一種分布式停車位發現解決方案[2]。在分布式的VANET系統中，車輛節點通過與通信范圍內的節點組成臨時的Ad hoc網絡進行多跳通信、交換信息[3]，VANET在智能交通系統中起著重要作用，為系統提供統一的無線通信網絡及多種通信方式。

1 相關工作

　　2006年Caliskan等[2]提出了一種基于車載自組網的分布式停車位發現模型，通過階段性信息采集進行停車位計算。2007年，Sherisha等[4]提出使用停車場歷史數據計算車輛目的地附近的停車位可用概率的方法為車輛提供停車引導。Murat[5]對停車位發現問題建立了概率預測模型，從統計角度對區域停車概率進行了預測。2009年Mathur等[6]提出了一種集中式和一種分布式方案來解決尋找停車位問題，并對停車位發現思想予以評估。2011年，Kokolak等[7]提出了一種分布式的機會停車位發現算法，可以擴展個體車輛的通信范圍。2012年，Andreas[8]對Murat數據收集方法和模型進行了改進，優化了轉移矩陣。

　　現有停車位概率預測算法主要是從統計角度預測停車位空閑的概率，但是不能具體為停車位發現提供明確的決策目標。本文提出一種基于停車位可用概率的停車位發現算法（An Available Probability based Parking Algorithm，APPA），在分布式系統中使用機會通信擴展車輛通信范圍，估算車輛到達停車位時的車位可用概率，為車輛分配最佳的可用停車位，規劃有效的行駛路徑。

2 前期假設與模型分析

　　2.1 停車位信息獲取

　　限于通信半徑的影響，車輛節點能感知的停車位有限，使用報文交互擴大節點的感知范圍，使節點的停車位決策超出局部VANET網絡，擴大到環繞車輛的VANET網絡群，做出更加符合整體利益的決策。

　　在車輛行駛過程中，不斷偵測可用的停車位信息，當偵測到可用停車位時，記錄該停車位的位置信息，同時記錄該停車位的時間戳。并在路邊設置少量的RSU，維護一個標準的時間和一張可用停車位信息表。當車輛進入RSU通信范圍時，交換可用停車位的信息，更新可用停車位信息，使得車輛能得到超出自身通信范圍的可用停車位信息。

　　2.2 距離計算標準

　　從地理位置信息角度考慮，將道路網絡轉化為有向圖。以道路作為拓撲網絡中的線，并以停車位和車輛作為拓撲網絡中的節點，賦予停車位和車輛地理二維坐標。轉化道路平面圖的同時做如下約定：

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

　　（2）對每個道路交叉口賦予一個額外的平均等待時間；

　　（3）由于算法的依據是有效距離，因此把等待時間結合預定的車輛速度轉化為距離，這個距離也是有效距離的組成部分；

　　（4）使用Dijkstra算法計算節點間距離。

　　2.3 模型分析

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

3 主要工作

　　3.1 車輛到達時間計算

　　在信息交互過程中，車輛互相傳播停車位信息，在獲取的報文中，如果存在本地鏈表沒有的車位，則記錄該車位位置信息及時間戳；如果已經存在，則更新時間戳，時間的記錄以最早發現該停車位為準。

　　當車輛占用某停車位后，則時間戳設為0，并向其他車輛轉發一次該停車位信息，同時將本地的停車位節點刪除。當其他車輛接收到時間戳為0的停車位信息時，進行相同操作。

　　假設當前時刻為t，車輛行駛速度為v，根據Dijkstra算法計算得到的車輛與停車位之間的最短路徑為D。在得到可用停車位的位置信息后，可以根據Dijkstra算法和車輛的行駛速度估計得到車輛相對每個停車位的到達時間：

　　3.2 可用車位獲取概率計算

　　假設車輛vi對一個車位sj的可用概率為P（vi，sj）：

　　式中，P（vi，sj）為T時刻停車位sj被其他車輛占用的概率。要計算車輛到達時刻的停車位可用概率，只需計算P（vi，sj）即可。

　　P（vi，sj）主要受兩個因素的影響：一個是停車位的空閑時長，即從停車位空閑時刻開始至車輛發起停車請求，這段時間的車位沒有被占用，但車位被選擇的概率會隨著時間的延長而累積，下一時刻被占用的概率隨之增大；另一個是當前時刻至車輛到達停車位，此時車輛與其他所有可能駛向此車位的車輛進行競爭，車輛距離停車位越近，勝出的可能性越高。

　　在參考文獻[9]中，針對計算實時可用停車位的變化進行了大量實驗，得到了關于停車場各個時刻停車位占用情況的實驗數據。本文引用這些實驗數據，并通過分析，將歷史數據抽象為函數，該函數表示車位被占用概率隨時間的變化關系，簡化了算法的復雜度，提高了算法效率。函數如式（3）所示：

　　其中c=86 400-a+b。

　　令概率Ph（sj）表示在t時刻可用停車位sj被任意一輛車占用的概率，其中包括沒有加入車載自組網的車輛。那么，從停車位sj空閑時刻開始至當前時刻t，認為其在t時刻后被任意車輛占用的概率為：

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

　　其中t為當前時刻。

　　設從停車位sj空閑時刻t開始，停車位的空閑時間和停車時間服從指數分布，則車輛節點流量可以看作一個泊松過程（λ）。那么，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 算法描述

　　車輛在行駛過程中，不斷偵聽感知范圍內的可用停車位，同時進行車間報文交互。當發起停車請求時，計算車輛與每個可用停車位之間的有效距離，并通過APPA算法計算每個可用停車位的概率，選擇概率最高的停車位并向其行駛，在行駛過程中，不斷重復進行偵聽和概率更新，始終駛向最大可用概率的停車位；當與某停車位距離D小于閾值Z（Z=v）時，占用停車位并將此停車位的時間戳置0。算法偽代碼如下：

　　FUNCTION APPA（S）{

　　for所有的停車位節點S

　　{  計算車輛與停車位之間距離D

　　IF D<Z

　　{

　　占用停車位，時間戳置0

　　END

　　}

　　}

　　for所有的停車位節點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框架下進行仿真，仿真過程中，每當一輛車占用一個停車位時，保存記錄這輛車找尋停車位所花費的時間，并在整個道路上隨機位置重新生成一個車輛，在另一隨機位置重新生成一個可用停車位。這可看作道路交通中的實時變化因素，更加符合實際情況。具體參數見表1。

　　4.2 仿真分析

　　仿真場景中停車位節點數為30，車輛節點數為5~80，且設定隱藏車輛與非隱藏車輛數量比約為1∶1。

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

　　圖2表示停車位平均空閑時間的關系曲線。由圖2可知，APPA算法的停車位平均空閑時間與就近原則方法接近，略優于就近原則。當可用停車位數目較多時，車輛有更多的停車選擇，APPA算法的決策擁有最大的成功概率；在車輛數目大于停車位數目時，車輛之間存在激烈的競爭，由于APPA算法計算了停車位從空閑時刻開始至發起停車請求這段時間對停車占用概率的影響，因此能提高車輛尋找車位的有效性。

5 結束語

　　本文對分布式系統中車輛和停車位位置信息不完全的模型進行研究，提出了一種基于停車位可用概率的停車位發現算法來解決分布式網絡中信息不完全情況下的停車位發現問題。通過仿真分析得知，在系統模型中，APPA算法有較大的優越性，其能更好地應對信息不完全的情形，縮短車輛的平均停車位發現時間。

參考文獻

　　[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的車載自組網的研究與仿真[D].武漢：武漢理工大學，2010.