張晶晶, 薛 偉

(江南大學(xué) 物聯(lián)網(wǎng)工程學(xué)院, 無錫 214122)

1 引言

現(xiàn)在許多大型停車場依舊是傳統(tǒng)的人工管理停車場方式, 而人工管理停車場存在很多問題. 停車場內(nèi)剩余車位信息“不透明”, 沒有被占用的車位位置不明確,車主停車時(shí)無法及時(shí)找到空余停車位, 這就造成停車場利用率低下[1]. 除此之外, 駕駛員在停車場內(nèi)迂回地尋找車位一方面容易造成停車場內(nèi)車輛擁堵, 另一方面大量汽車在尋找車位時(shí)排放的汽車尾氣容易造成空氣污染[2]. 本文針對這一問題, 設(shè)計(jì)了智能停車場. 智能停車場內(nèi)的每個(gè)車位上空放置超聲波車位傳感器采集車位信息, 并通過ZigBee無線網(wǎng)絡(luò)傳輸信息[3]. 停車場內(nèi)的管理系統(tǒng)[4]采用Microsoft Visual Studio平臺設(shè)計(jì),主要完成車位信息的處理和存儲. 停車場內(nèi)岔路口處有方向顯示屏, 顯示左、前、右方向信息, 指引泊車者行進(jìn)方向, 將車停至最佳停車位置. 這個(gè)智能停車誘導(dǎo)系統(tǒng)就能避免泊車者在停車場盲目尋找車位, 減少了汽車在尋找車位時(shí)在道路上迂回浪費(fèi)的時(shí)間, 緩解道路空間, 節(jié)約資源, 同時(shí)也減輕工作人員的負(fù)擔(dān), 降低人工成本, 提高停車場的利用率.

2 系統(tǒng)總體設(shè)計(jì)

本文提出了一種基于蟻群算法的智能停車誘導(dǎo)系統(tǒng), 該系統(tǒng)采用的技術(shù)方案包括超聲波車位檢測,ZigBee無線傳輸協(xié)議, VS平臺軟件開發(fā). 該智能停車場系統(tǒng)包括上位機(jī)綜合管理, 空車位檢測, 車輛引導(dǎo)等功能. 總體結(jié)構(gòu)框圖如圖1所示.

圖1 系統(tǒng)總體框架圖

2.1 ZigBee無線模塊與超聲波車位探測

超聲波車位傳感是基于ZigBee終端模塊設(shè)計(jì)的,采用HC-SR04超聲波測距模塊檢測距離, 放置在距離車位上空3.5 m處的位置. 模塊的發(fā)射器發(fā)送8個(gè)40 kHz的方波自動(dòng)檢測, 如果發(fā)現(xiàn)有障礙物則接收器接受返回的信號. 汽車高度范圍在1.3–2.2 m之間, 所以如果檢測到1.3–2.2 m處有障礙物代表車位有車紅燈亮, 否則綠燈亮.

ZigBee無線模塊包括終端、路由器、協(xié)調(diào)器都是采用TI公司生產(chǎn)的以CC2530芯片為核心, CC2530芯片[5]支持IEEE802.15.4標(biāo)準(zhǔn)、ZigBee標(biāo)準(zhǔn)、ZigBee RF4CE標(biāo)準(zhǔn)的無線傳感器網(wǎng)絡(luò)協(xié)議, 具有優(yōu)秀的接收器靈敏度和健壯抗干擾性, 支持低功耗的無線通信.

無線傳輸網(wǎng)絡(luò)采用Z-Stack協(xié)議棧, Z-Stack包含了網(wǎng)狀拓?fù)涞膸缀跞抗δ艿膮f(xié)議棧, 開發(fā)者可以很容易地開發(fā)出具體的應(yīng)用程序. 在本系統(tǒng)選擇了樹狀網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu), 首先協(xié)調(diào)器節(jié)點(diǎn)負(fù)責(zé)建立一個(gè)網(wǎng)絡(luò)和整合數(shù)據(jù)信息, 終端節(jié)點(diǎn)負(fù)責(zé)加入網(wǎng)絡(luò)和通過無線傳輸?shù)姆绞綄⒔邮盏某暡ㄜ囄粰z測信息上傳至父節(jié)點(diǎn),經(jīng)過路由器節(jié)點(diǎn)上傳至協(xié)調(diào)器. 如圖2包括終端(即基于ZigBee模塊的超聲波車位傳感器)、路由器、協(xié)調(diào)器.

圖2 ZigBee模塊

2.2 改進(jìn)蟻群算法與管理員平臺

2.2.1 改進(jìn)蟻群算法

如圖3所示的簡易停車場平面結(jié)構(gòu)圖, 根據(jù)圖顯示的停車場平面圖建立停車場抽象模型. 為建立停車場車位模型將圖中的有兩條及以上行車方向的交叉路口, 以及各個(gè)停車位作為節(jié)點(diǎn). 將各個(gè)可相通的交叉路口之間的路段和各個(gè)停車位到與之相通的交叉路口的路段作為邊.

圖3 停車場平面結(jié)構(gòu)圖

如圖4所示的停車場抽象模型, 邊權(quán)構(gòu)成網(wǎng)狀結(jié)構(gòu)圖轉(zhuǎn)化為帶權(quán)有向圖G=(V, E), 其中V是包含所有節(jié)點(diǎn)的集合, E表示所有包含邊(弧段)的集合. 圖中Ri(1≤i≤6)是停車場的各個(gè)岔路口節(jié)點(diǎn), 其中R1作為

停車場的入口節(jié)點(diǎn), R3作為停車場的出口節(jié)點(diǎn), 圖中的P29, P32等代表的是剩余空車位節(jié)點(diǎn). 蟻群算法計(jì)算從停車場入口R1到各個(gè)空余停車位的距離, 然后進(jìn)行比較得出最短路徑, 獲得最優(yōu)停車位以及到達(dá)該停車位的路線, 所以建立邊權(quán)的權(quán)值就是各個(gè)部分的實(shí)際距離. 邊權(quán)的構(gòu)建包含兩個(gè)方面, 一個(gè)是各個(gè)交叉路口之間的邊權(quán)(即交叉路口之間的距離), 采用符號W＜Ri, Rj＞(1≤i,j≤6)表示; 另一個(gè)是交叉路口到具體停車位的邊權(quán)采用符號W＜Ri, Pk＞(1≤i≤6)(k=1, 2, 3,…)表示.

圖4 帶權(quán)有向圖

基本蟻群算法是一種源于大自然生物世界的新的仿生進(jìn)化算法, 模擬自然界中螞蟻集體尋徑行為而提出的一種基于種群的啟發(fā)式隨機(jī)搜索算法[6]. 螞蟻在尋找食物的行進(jìn)過程中在其走過的路徑上釋放信息素,隨著時(shí)間的推移, 路徑上的信息素會揮發(fā), 后來的螞蟻會根據(jù)信息素的強(qiáng)度來決定選擇該路徑的概率. 根據(jù)真實(shí)蟻群在搜索食物時(shí)解決最短路徑的問題的方式,可以構(gòu)建人工蟻群解決本文的最短路徑問題.

基本蟻群算法應(yīng)用在停車場的應(yīng)用中會出現(xiàn)一些問題, 例如死鎖, 停滯, 甚至無解(即無法到達(dá)指定終點(diǎn)無法得出結(jié)果)的情況. 針對上述問題并且為了更好地應(yīng)用于停車場的情況, 對傳統(tǒng)蟻群算法進(jìn)行改進(jìn), 主要包括三個(gè)方面: MAX-MIN Ant System[7](最大-最小螞蟻系統(tǒng)), 局部信息素更新[8]和撤退方法. 這樣既能搜索更大的解空間, 又能使系統(tǒng)陷入局部最優(yōu)后跳出停滯狀態(tài). 而為了增加螞蟻的全局搜索性, 并且能夠有機(jī)會選擇更多的路徑方向, 在選擇下一步的轉(zhuǎn)移規(guī)則中增加輪盤賭算法.

(1) MAX-MIN Ant System

最大最小螞蟻系統(tǒng)為了充分利用當(dāng)前循環(huán)中的最優(yōu)解, 在每次循環(huán)之后, 得到的最優(yōu)解的螞蟻?zhàn)哌^的路徑進(jìn)行信息素更新. 除此之后, 將每條路徑上的信息素的值域范圍限制在[τmin,τmax]區(qū)間內(nèi), 這就避免過多螞蟻行進(jìn)相同路徑而使得路徑上的信息素遠(yuǎn)遠(yuǎn)高于其他邊, 而導(dǎo)致再次吸引更多的螞蟻在同路徑上行進(jìn).

(2) 局部信息素更新

最大最小螞蟻系統(tǒng)中, 只更新每次循環(huán)中最優(yōu)解路徑上的信息素, 而為了更好地搜索到最優(yōu)解, 本文在系統(tǒng)中增加局部更新規(guī)則, 如式(1)所示:

其中,τ0表示是各個(gè)路徑的信息素的初始值, 那么全局最優(yōu)螞蟻的信息素的更新規(guī)則如式(2)所示:

其中,Lbest表示最優(yōu)路徑的長度.

(3) 撤退方法

蟻群算法在停車場結(jié)構(gòu)圖的應(yīng)用中易出現(xiàn)無解的情況, 例如一個(gè)路徑的終點(diǎn)是R3, 而螞蟻在行動(dòng)中走的路線是R1→R2→R5→R4, 蟻群算法在運(yùn)行中要求一個(gè)節(jié)點(diǎn)只能走一次, 那么如果出現(xiàn)上述的路線, 螞蟻將無法走到終點(diǎn)R3. 為了解決這個(gè)問題提出了撤退方法, 如果過程中出現(xiàn)上述類似問題, 將螞蟻的走向退回到R5節(jié)點(diǎn), 并且將R5→R4路段上的信息素更新為零,利用輪盤賭算法再次為螞蟻重新選擇下一節(jié)點(diǎn), 避免螞蟻重復(fù)上述路段, 直至有路線能夠到達(dá)終點(diǎn).

2.2.2 算法執(zhí)行步驟及實(shí)驗(yàn)結(jié)果

Step1. 建立停車場平面圖模型, 利用貪婪算法規(guī)劃出一條從初始點(diǎn)到終點(diǎn)的初始路徑, 然后計(jì)算出τ0.

Step2. 蟻群參數(shù)初始化, 設(shè)置參數(shù)m,α,β,ρ,Q的值, 令循環(huán)次數(shù)Nc=0和τ=τmax, 設(shè)置最大迭代次數(shù)G,將m只螞蟻置于初始節(jié)點(diǎn).

Step3. 蟻群算法開始搜索, 當(dāng)前螞蟻節(jié)點(diǎn)i，按照如下公式和輪盤賭算法計(jì)算下一節(jié)點(diǎn)j:

Step4. 判斷下一節(jié)點(diǎn)j是否確定, 如果無法取得j則選擇撤退方法, 再返回到Step4并且路徑上信息素更新為0. 如果下一節(jié)點(diǎn)j確定, 螞蟻要對剛走過的路徑＜i,j＞上的信息素按照式(1)進(jìn)行局部信息素更新,并將該節(jié)點(diǎn)放入路徑表中.

Step5. 判斷螞蟻是否達(dá)到終點(diǎn), 若達(dá)到終點(diǎn)則轉(zhuǎn)到Step6, 否則轉(zhuǎn)到Step3.

Step6. 統(tǒng)計(jì)當(dāng)前m只螞蟻搜索到的最優(yōu)路徑, 選出最短路徑, 并將此路線上的信息素通過式(2)局部更新和式(3)進(jìn)行全局最優(yōu)螞蟻的信息素更新.

Step7. 若滿足結(jié)束條件, 即循環(huán)次數(shù)Nc≥G, 則程序結(jié)束并輸出最優(yōu)結(jié)果, 否則清空禁忌表并轉(zhuǎn)至Step3.

根據(jù)建立的停車場模型, 搜索最優(yōu)停車位, 編程環(huán)境 VS2013. 設(shè)置m=50,ρ=0.5,α=1,β=2,G=300. 根據(jù)上述步驟得出實(shí)驗(yàn)步驟, 結(jié)果如表1所示.

表1 停車場仿真實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)結(jié)果表明, 最佳車位是P46, 路線(S)R1→R2→P46.

2.2.3 管理員平臺

管理員平臺作為主控機(jī)一般采用PC機(jī), 放置在中央控制室, 該上位機(jī)主要用來進(jìn)行人機(jī)交互, 并在無線局域網(wǎng)內(nèi)向顯示屏發(fā)送方向命令. 我們采用Visual Studio2013在Windows平臺上對上位機(jī)人機(jī)交互界面進(jìn)行設(shè)計(jì), 使用.Net框架下的TCP傳輸協(xié)議建立TCP通信, 設(shè)置IP地址以及端口號方便與顯示屏建立連接.

具體實(shí)現(xiàn)功能, 接收、處理和存儲下位機(jī)上傳的車位信息, 將車位信息內(nèi)容展示在上位機(jī)平臺上, 如圖5的上位機(jī)管理員界面, 紅色(圖中深色著色)代表此車位已被占用, 綠色(圖中淺色著色) 代表車位狀態(tài)是空閑. 上位機(jī)內(nèi)部統(tǒng)計(jì)車位節(jié)點(diǎn)信息, 通過改進(jìn)蟻群算法計(jì)算出最優(yōu)停車路線并保存在數(shù)據(jù)庫中, 為方向引導(dǎo)屏提供信息支持, 以及顯示剩余車位信息.

圖5 管理員界面

2.3 方向引導(dǎo)屏

采用Visual Studio2013在Windows平臺設(shè)置的顯示屏懸掛在停車場內(nèi)岔路口上方, 顯示屏輸入IP地址與端口號以及所在岔路口的節(jié)點(diǎn)名稱在局域網(wǎng)內(nèi)與服務(wù)器建立通信, 接收從管理員服務(wù)器的信息, 指引駕駛員行駛到達(dá)最優(yōu)的停車位置.

如圖6所示, 圖6的引導(dǎo)屏位于停車場入口的R1位置, 假定停車場先后進(jìn)入兩輛停車場, 獲得兩輛車的車牌號分別為蘇B01010和蘇B02020, 由蟻群算法得出的最優(yōu)的停車位是P29, 所以為第一位駕駛員指向前行駛方向, 指引第一位駕駛員將車停至P29車位.在假定第一停車位已經(jīng)被占用的情況下, 為第二輛車輛分配最佳車位P35, 到達(dá)P35停車位經(jīng)過的拐角路徑是R1→R2, 所以在R1入口處為蘇B02020車輛指引向左行駛方向, 將蘇B02020車輛指引至R2節(jié)點(diǎn)處,再由R2節(jié)點(diǎn)處的引導(dǎo)屏指引車輛停至P35車位.

圖6 方向引導(dǎo)屏

3 結(jié)論

針對停車場內(nèi)停車難問題, 在停車位上方安裝超聲波告訴泊車者車位信息; 提出用蟻群算法解決場內(nèi)最優(yōu)解問題, 針對停車場的模型對蟻群算法進(jìn)行優(yōu)化改進(jìn), 使改進(jìn)后的蟻群算法能更好應(yīng)用在停車場; 上位機(jī)通過改進(jìn)的蟻群算法計(jì)算出距離停車場入口最近的空閑停車位, 并得出具體路線, 通過TCP/IP通信方式向方向指引屏傳輸信息誘導(dǎo)駕駛員行駛至最佳停車位.本系統(tǒng)的設(shè)計(jì)能夠避免駕駛員在停車場內(nèi)盲目尋找停車位, 實(shí)現(xiàn)了對車位智能誘導(dǎo)功能, 有效地提高停車場的運(yùn)行效率.