一種基于車載自組網的停車位協(xié)作發(fā)現(xiàn)算法

李 鵬，李德敏，張曉露

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

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

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

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

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

1 COAPS策略描述

1.1 問題描述

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

圖1 停車位發(fā)現(xiàn)服務場景示意圖Fig. 1 Typical scene of parking lot discovery service

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

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

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

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

1.2 策略描述

圖3 COAPS車輛節(jié)點競爭Fig. 3 Competition of vehicles in COAPS

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

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

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

以下是COAPS算法的總體描述，下一節(jié)將給出具體的算法實現(xiàn)細節(jié)：

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

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

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

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

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

2 COAPS算法

基于1.2節(jié)的COAPS算法策略描述，本節(jié)將闡述算法的具體實現(xiàn)細節(jié)。

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

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

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

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

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

-α:為節(jié)點的協(xié)作參數(shù)。

2.1 停車位的初始解

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

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

2.2 停車位的新解

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

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

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

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

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

2.3 停車位的開銷計算

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

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

2.4 停車位的最優(yōu)解

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

2.5 車輛節(jié)點—停車位的報文交互

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

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

3 仿真與分析

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

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

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

車輛通信范圍：200 m

車輛數(shù)目：5～80

停車位通信范圍：100 m

停車位數(shù)目：30

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

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

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

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

停車位的空閑時間是指車輛節(jié)點從開始尋找到預定到停車位的時間（不包括節(jié)點行駛到停車位的時間），體現(xiàn)了車輛節(jié)點對停車位的競爭情況，也是表征車輛協(xié)作性的一個重要指標。停車位空閑時間及其均方差的仿真結果圖如圖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中的車輛節(jié)點基于搶占式原則總是選擇盡可能近的停車位，導致鄰居節(jié)點很有可能去選擇更遠的停車位，因而車輛節(jié)點間不均衡的停車位選擇導致停車位空閑時間的均方差很大。由此可以看出COAPS算法由于兼顧鄰居節(jié)點的利益，均化了節(jié)點的停車位搜尋時間，體現(xiàn)出協(xié)作性特征。雖然在停車位平均空閑時間上沒有明顯優(yōu)勢，但可以換來停車位發(fā)現(xiàn)效率的顯著提升。

4 結 論

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

[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