一種基于車載自組網的停車位協作發現算法

李 鵬，李德敏，張曉露

（東華大學 信息科技與技術學院，上海 201620）

在停車位發現服務中，由于車載自組網的拓撲結構具有快速頻繁變化的特點，使得原有的C/S構架網絡缺乏靈活性和適用性，而車載自組織網絡(Vehicular Ad Hoc Network，VANET)提供了一種分布式停車位發現解決方案[1]。在分布式的VANET系統中，車輛節點通過與通信范圍內的節點組成臨時的ad hoc網絡來進行多跳通信、交換信息（包括實時的駕駛者信息、路況信息以及非實時的交通模式信息）[2]，這為分布式停車位發現提供了數據通信基礎。

2006 年Caliskan等人[3]在提出了一種基于車載自組網的分布式停車位發現模型，通過階段性信息采集來進行停車位計算。Mathur等人[4]在2009年提出了一種集中式和一種分布式方案來解決尋找停車位問題。在集中式方案中車輛節點安裝超聲波傳感器，沿道路行進過程中收集停車位數據信息，然后向中央服務器提出申請來得到停車位分配服務。同時闡述了分布式停車系統的重要性。2010年Mathur等人[5]對集中式停車位發現思想予以實現和評估。2011年, Kokolaki等人[6]提出了一種分布式的機會停車位發現算法（OAPS -Opportunistically Assisted Parking Search），其基本思想是車

輛節點在停車位搜尋過程中與網絡中的鄰居節點進行分布式機會通信，交換路況信息和停車位信息，基于這些儲存在緩存中的信息按照搶占式原則計算出最近且最可達的停車位。

在具有代表性的OAPS算法中，機會通信可以讓車輛靈活的掌握網內鄰居節點的信息從而使停車位決策具有很大的智能性，但由于搶占式的原則，不能很好的體現整體的系統性能。因此本文基于OAPS提出了一種協作式停車位發現算法（簡稱COAPS- Collaborative OAPS）。該算法使用機會通信方式，利用車輛和停車位的數據信息來實現一種車輛與停車位協作交互，具有較好系統利用率的停車位分配機制，從而在性能上獲得兩方面的優勢：1)在分布式系統的靈活、成本低的特點下，克服車輛節點的“自私競爭”，做出最大限度滿足自身和全局的停車位選擇；2)車輛節點通過與停車位的報文交互來擴展通信范圍，獲得比車輛通信范圍內更大的信息量，從而做出具有協作特點的決策。

1 COAPS策略描述

1.1 問題描述

典型的停車位發現服務的問題描述在[6]已有敘述，其場景主要由地理信息、車輛節點及停車位節點組成，如圖1所示，（方塊代表車輛節點，實心點代表停車位，圓圈Mij代表路徑的交叉口節點）。

圖1 停車位發現服務場景示意圖Fig. 1 Typical scene of parking lot discovery service

基于圖1場景信息停車位發現算法可描述為：車輛節點如何在與鄰居節點競爭與協作的情況下從可用的停車位節點中找出最有可能占用且盡可能兼顧鄰居節點利益的最優停車位。

OAPS基于搶占式原則總是選擇個體指標最好也即最近的停車位，在典型的節點競爭場景下其停車位選擇如圖2所示。

圖2 OAPS車輛節點競爭Fig. 2 Competition of vehicles in COAPS

由圖2可知，車輛節點 具有兩個距離相近的停車位P0和 P1，但是占用P1后對節點N1造成了很大的額外路徑開銷，缺乏協作性。這種不良競爭會造成鄰居節點的利益損失，也是COAPS主要解決的問題，圖3是COAPS的理想競爭示意圖。對比圖2、圖3可知，如果要兼顧鄰居節點的利益就需要對鄰居節點的路徑開銷予以考慮，使得每個車輛節點的決策能夠體現局部的整體效益。因此COAPS在選擇停車位時會計算鄰居節點的開銷，以VANET網絡內各節點的綜合開銷作為衡量標準。但考慮每個節點選擇合作的傾向性不同，因此需要在個體開銷和鄰居節點開銷的權重及優先級上予以體現（詳見第2節）。

1.2 策略描述

圖3 COAPS車輛節點競爭Fig. 3 Competition of vehicles in COAPS

停車位發現服務的核心是如何在拓撲結構頻繁變換的網絡場景中為車輛節點及時找到“最優”的停車位?！白顑灐钡脑u價通常是通過兩個層次的指標來予以衡量[1]：一是個體指標，即如何讓車輛節點以最短時間找到停車位；二是系統指標，如何讓停車位區域的停車位利用率達到最高。OAPS基于搶占式原則主要面向個體指標，COAPS則是綜合考慮兩種指標，在尊重個體指標情況下最大限度兼顧系統指標。

為了獲得節點的協作性，COAPS中的車輛節點以自己和鄰居節點的均衡開銷作為總開銷，通過調節鄰居節點開銷的權重來改變節點的協作傾向，但當鄰居節點和停車位節點數量較多時，最優解的求解變得非常緩慢低效，因此引入具有全局性能優化的模擬退火算法可以顯著提高求解效率，同時針對停車位組合優化問題的非凸型，避免陷入局部最優。

在模擬退火的算法框架下，COAPS中的車輛節點與其鄰居節點首先在可選停車位中任意分配產生初始解（同時作為當前解），在隨后從高溫到低溫的模擬退火過程中不斷的由當前解產生新解，同時以各節點的整體路徑開銷作為性能評價指標來確定其優劣性，以大概率接受更優解，以小概率接受次優解（跳出局部最優），當溫度達到最低（算法的終止條件）時即得出最終的最優停車位。每個節點依次進行運算即可得到其相應的停車位，至此在單一節點間完成了協作。但在不同節點間仍會出現停車位沖突也即競爭的情況，此時通過節點與其最優停車位之間的報文交換，由相應停車位來從沖突的節點中選擇最優節點，拒絕其他次優節點，由此來完成多節點之間的協作。

以下是COAPS算法的總體描述，下一節將給出具體的算法實現細節：

Step1：車輛節點從可用停車位中隨機選擇一個停車位以及參與競爭的鄰居節點集合，生成初始解，同時作為當前解（詳見2.1）；

Step2：由當前解產生新解，對當前解進行更新（詳見2.2）；

Step3：計算節點開銷作為評價解的性能指標，對當前解進行篩選（詳見2.3）；

Step4：由初始解依次從高溫向低溫收斂，以Step3的性能指更新最優解（詳見2.4）；

Step5：與解得的最優停車位進行報文交互，確定是否可占用。（詳見2.5）；

2 COAPS算法

基于1.2節的COAPS算法策略描述，本節將闡述算法的具體實現細節。

下面首先對COAPS所用到的基本參量進行定義說明：

-V={V1,…V2…VN},1≤i≤x, 為車輛節點集合，x為車輛節點數目；

-Ni={,……},1≤j≤y,1≤i≤x為車輛節點在VANET網絡范圍內的鄰居節點， 為鄰居節點數目；

-Pi={,……},1≤j≤z,1≤j≤x為Vi傳感感知到的和鄰居節點告知的停車位；

-C={V1,…V2…Vi}，V ∈ V，∈Pi為節點Vi到停車位的開銷。

-α:為節點的協作參數。

2.1 停車位的初始解

COAPS算法首先為節點Vi從可用停車位Pi中隨機選取停車位。由于鄰居節點和停車位數量不確定，因此參與競爭的鄰居節點Ji的數量為鄰居節點數量和停車位數量的最小值：

Ji為鄰居節點集合的一個隨機子序列，其數量為min(|Pi|,|Ni|) 。同理Ki對應的可選的停車位集合Ki為：

2.2 停車位的新解

對于節點Vi，其新解是在當前解的基礎上產生的，目的是在當前狀態下產生新的更優解，來達到進化演算的目標。由于解是一個行向量序列，因此可以采取二交換的形式產生新解。

由于Ji是鄰居節點Ni的一個不完全子集，因此其補集的信息同樣需要考慮，這里我們設Ji的補集為Ji。在進行交換前，首先從Ji集合選出兩個待交換元素和，再從Ji集合選出一個待交換元素，于是滿足：

為了讓Ji和Ji'同時參與選擇，利用0～1的概率隨機數 α對進行交換，即：

交換的結果便是更新Ji和Ji'。Ki的更新與Ji類似，不同之處在于與的關聯，因此需在、、與四者之間進行概率交換，即：

為了加速解的更新還需引入三交換，即在Ji和Ki中選出3個變量進行交換，原理與二交換一樣，需要再引入一個隨機數 在二交換和三交換之間進行概率均衡，即：

2.3 停車位的開銷計算

在節點Vi選取停車位情況下，首先計算Vi到的開銷為 Dijkstra（Vi，），其中Dijkstra是以道路節點為無向圖計算出的兩個節點間最短路徑。然后計算鄰居節點開銷，并用節點的合作傾向參數α進行均衡，于是Vi對于停車位Picur的最終路徑總開銷C（Vi，）為：

考慮到不同節點的鄰居節點和可用停車位數量不同，且存在節點不可達的情況，因此用VANET網內各節點的平均路徑開銷來統一表示。α表征節點與鄰居節點的協作程度，α=0時協作程度最低，退化為OAPS，α=1時協作程度最高，不考慮自身利益（通常α=0.5 ）。

2.4 停車位的最優解

對于節點Vi，其最優停車位即是以C（Vi，）為目標函數的最優解。在模擬退火中，以作為初始解和當前解，以 C（Vi，）作為內能依次從高溫向低溫靠近，同時保持對當前最低內能及對應當前解的記錄，以大概率接受新的最優解，小概率接受次優解作為當前解，從而最終算出達到最低溫度時的最優停車位（最優解），即：

2.5 車輛節點—停車位的報文交互

以上得到的關于節點Vi的最優停車位反映的是VANET網內信息，限于通信半徑的影響，節點的決策不能很好的體現以停車位為中心的區域信息。作為V-V(Vehicle-to-Vehicle)通信的一種重要途徑，以報文為載體的信息傳遞交互使得車輛節點不僅能獲取如停車位等相關場所信息，同時避免一些有害的場景[7]。因此與停車位的報文交互一方面可以擴大節點對停車位的感知范圍，另一方面可以擴大停車位對車輛節點的控制范圍，使節點的停車位決策超出局部VANET網絡，擴大到環繞停車位的VANET網絡群，表現系統指標。

因此每個節點Vi在算得最優停車位后，將計算出的總路徑開銷C（Vi，）發送申請報文給，從接收到的申請報文中選出開銷最小的節點向其發送確認報文，確認其被分配成功，并向其他節點發送拒絕報文。收到拒絕報文的節點開始新一輪的停車位搜索。

3 仿真與分析

車載自組網算法仿真主要分為交通仿真(Traffic Simulation)和網絡仿真(Network Simulation)[8]，停車位發現算法側重于應用層的交通仿真（不考慮網絡層的丟包率等），因此在VanetMobisim(VANET運動模型及交通仿真平臺)的框架基礎上用Java語言擴展算法模型，對COAPS與OAPS進行對比仿真，仿真環境描述如下：

仿真場景范圍：1 200 m×1 200 m

車輛平均行駛速度：40 km/h

車輛通信范圍：200 m

車輛數目：5～80

停車位通信范圍：100 m

停車位數目：30

道路網格參數（水平/垂直方向道路的數量）：20×20

為了表現典型的實際情況，地圖采用網格道路模型，隨機生成20×20的道路，車輛節點和停車位的起始位置隨機均勻分布于區域中，按照節點數量的不同分別進行多次仿真，取統計均值來消除節點分布不同所造成的影響。仿真結果如圖4所示。

圖4 車輛節點搜尋停車位的平均行駛時間仿真對比Fig. 4 Comparative simulation of vehicles’ average parking lot discovery time

圖4為車輛節點搜尋停車位的平均行駛時間，停車位數量為30，車輛節點數目為5～80。分析圖4可知，在車輛數目少于停車位數量的情況下，由于所有節點最終都可以分配到停車位，COAPS與OAPS的平均搜尋時間相比差別不是很大，COAPS僅僅是在路徑規劃上略優于OAPS。當車輛數目接近于停車位數目時便出現了競爭，于是OAPS所造成的資源浪費開始顯現出來，因為節點對最近停車位的盲目搶占極有可能造成鄰居節點更大的路徑開銷，而這種情況下最能體現出COAPS的協作性優勢。當車輛數目遠多于停車位數量時不是所有車輛節點都可以分配到停車位，同時車輛的高密度增加了路徑分配的難度，這種環境最為惡劣的情況對OAPS影響最大，而COAPS按照分層局部最優的原則保護鄰居節點的利益，因而受車輛密度的影響不大。

停車位的空閑時間是指車輛節點從開始尋找到預定到停車位的時間（不包括節點行駛到停車位的時間），體現了車輛節點對停車位的競爭情況，也是表征車輛協作性的一個重要指標。停車位空閑時間及其均方差的仿真結果圖如圖5～6所示。

圖5 停車位的平均空閑時間Fig. 5 Average idle time of the parking lots

圖6 停車位搜尋時間的均方差Fig. 6 Average variance of parking lot discovery time

圖5顯示COAPS與OAPS的停車位平均空閑時間相差不大，但圖6顯示的停車位搜尋時間均方差要遠小于OAPS。OAPS中的車輛節點基于搶占式原則總是選擇盡可能近的停車位，導致鄰居節點很有可能去選擇更遠的停車位，因而車輛節點間不均衡的停車位選擇導致停車位空閑時間的均方差很大。由此可以看出COAPS算法由于兼顧鄰居節點的利益，均化了節點的停車位搜尋時間，體現出協作性特征。雖然在停車位平均空閑時間上沒有明顯優勢，但可以換來停車位發現效率的顯著提升。

4 結 論

文中通過對停車位發現算法的研究，基于OAPS和模擬退火算法提出了一種協作式停車位發現算法（COAPS），通過車輛節點間的協作來避免不良競爭。通過COAPS與OAPS的對比仿真，驗證COAPS算法具有更好的全局效益，可以減少車輛節點的不良競爭和停車位發現時間。

[1] Caliskan M,Barthels A,Scheuermann B,et al.Predicting parking lot occupancy in vehicular ad hoc networks[C].Vehicular Technology Conference, 2007. VTC2007-Spring. IEEE 65th.IEEE, 2007: 277-281.

[2] Mousannif H,Khalil I,Al Moatassime H.Cooperation as a Service in VANETs[J].Journal of Universal Computer Science,2011,17(8):1202-1218.

[3] 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.

[4] 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.

[5] Mathur S, Jin T, Kasturirangan N, et al. Parknet: drive-by sensing of road-side parking statistics[C].Proceedings of the 8th international conference on Mobile systems, applications, and services.ACM,2010:123-136.

[6] 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.

[7] Lee U, Gerla M. A survey of urban vehicular sensing platforms[J].Computer Networks, 2010, 54(4): 527-544.

[8] Stanica R, Chaput E, Beylot A L. Simulation of vehicular ad-hoc networks: Challenges, review of tools and recommendations[J].Computer Networks, 2011, 55(14): 3179-318