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

李 鵬，李德敏，張曉露

（東華大學(xué) 信息科技與技術(shù)學(xué)院，上海 201620）

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

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

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

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

1 COAPS策略描述

1.1 問題描述

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

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

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

OAPS基于搶占式原則總是選擇個體指標(biāo)最好也即最近的停車位，在典型的節(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可知，如果要兼顧?quán)従庸?jié)點的利益就需要對鄰居節(jié)點的路徑開銷予以考慮，使得每個車輛節(jié)點的決策能夠體現(xiàn)局部的整體效益。因此COAPS在選擇停車位時會計算鄰居節(jié)點的開銷，以VANET網(wǎng)絡(luò)內(nèi)各節(jié)點的綜合開銷作為衡量標(biāo)準(zhǔn)。但考慮每個節(jié)點選擇合作的傾向性不同，因此需要在個體開銷和鄰居節(jié)點開銷的權(quán)重及優(yōu)先級上予以體現(xiàn)（詳見第2節(jié)）。

1.2 策略描述

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

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

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

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

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

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

Step2：由當(dāng)前解產(chǎn)生新解，對當(dāng)前解進(jìn)行更新（詳見2.2）；

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

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

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

2 COAPS算法

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

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

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

-Ni={,……},1≤j≤y,1≤i≤x為車輛節(jié)點在VANET網(wǎng)絡(luò)范圍內(nèi)的鄰居節(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中隨機(jī)選取停車位。由于鄰居節(jié)點和停車位數(shù)量不確定，因此參與競爭的鄰居節(jié)點Ji的數(shù)量為鄰居節(jié)點數(shù)量和停車位數(shù)量的最小值：

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

2.2 停車位的新解

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

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

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

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

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

2.3 停車位的開銷計算

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

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

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

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

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

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

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

3 仿真與分析

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

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

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

車輛通信范圍：200 m

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

停車位通信范圍：100 m

停車位數(shù)目：30

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

為了表現(xiàn)典型的實際情況，地圖采用網(wǎng)格道路模型，隨機(jī)生成20×20的道路，車輛節(jié)點和停車位的起始位置隨機(jī)均勻分布于區(qū)域中，按照節(jié)點數(shù)量的不同分別進(jìn)行多次仿真，取統(tǒng)計均值來消除節(jié)點分布不同所造成的影響。仿真結(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。當(dāng)車輛數(shù)目接近于停車位數(shù)目時便出現(xiàn)了競爭，于是OAPS所造成的資源浪費(fèi)開始顯現(xiàn)出來，因為節(jié)點對最近停車位的盲目搶占極有可能造成鄰居節(jié)點更大的路徑開銷，而這種情況下最能體現(xiàn)出COAPS的協(xié)作性優(yōu)勢。當(dāng)車輛數(shù)目遠(yuǎn)多于停車位數(shù)量時不是所有車輛節(jié)點都可以分配到停車位，同時車輛的高密度增加了路徑分配的難度，這種環(huán)境最為惡劣的情況對OAPS影響最大，而COAPS按照分層局部最優(yōu)的原則保護(hù)鄰居節(jié)點的利益，因而受車輛密度的影響不大。

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

4 結(jié) 論

文中通過對停車位發(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