一種預約式智能停車場及其LEACH路由算法改進

古　輝，顧杰杰

(浙江工業(yè)大學 計算機科學與技術(shù)學院，浙江 杭州 310023)

?

一種預約式智能停車場及其LEACH路由算法改進

古輝，顧杰杰

(浙江工業(yè)大學 計算機科學與技術(shù)學院，浙江 杭州 310023)

摘要：通過超聲波傳感器實現(xiàn)對停車位上車輛有無檢測，利用手機App來實時查詢和預約停車位以及在線支付功能，提出了一種以超聲波傳感技術(shù)和無線傳感網(wǎng)絡(luò)技術(shù)，以及移動互聯(lián)網(wǎng)絡(luò)技術(shù)相結(jié)合的預約式智能停車場的控制與管理技術(shù)方案.在構(gòu)建停車場無線傳感網(wǎng)絡(luò)過程中，基于某個特定的場景，提出了基于LEACH的簇樹網(wǎng)絡(luò)的路由算法改進方法，Matlab模擬實驗表明，改進后的算法對節(jié)點能耗有很大減少，延長了停車場無線傳感網(wǎng)絡(luò)的生命周期，從而實現(xiàn)整個預約式智能停車場系統(tǒng)的有效管理.

關(guān)鍵詞：停車位控制器；超聲波；App；無線傳感器網(wǎng)絡(luò)；LEACH蔟樹網(wǎng)絡(luò)

隨著我國車輛保有量的激增，開車堵和停車難問題在城市顯得尤為明顯，造成當前停車問題主要有以下5點：1) 停車位資源匱乏；2) 違章停放現(xiàn)象普遍；3) 停車設(shè)施利用率低；4) 管理存在盲點；5) 停車管理的信息化程度低.無線傳感網(wǎng)絡(luò)的興起帶動了停車場智能管理的發(fā)展，國內(nèi)外研究日漸成熟，但能耗問題一直都是研究熱點.Jong-Myoung Ki等[1]提出了一種無線傳感器網(wǎng)絡(luò)中基于模糊邏輯的簇頭選舉機制，通過使用模糊邏輯，收集和計算開銷可以減少，并且傳感器網(wǎng)絡(luò)的壽命可以延長.Guang-yao Ji等[2]提出了一種上下文自適應聚類的高效的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)融合方法，對改善能耗和網(wǎng)絡(luò)壽命有很大成效.周玉等[3]提出了一種基于遺傳算法的新型路由算法LEACH-GEC，較LEACH協(xié)議分簇更均勻，簇首選取更合理，有效延長了網(wǎng)絡(luò)壽命.吳臻等[4]基于對能量和簇頭間距的考慮，對LEACH路由算法的改進，提高了網(wǎng)絡(luò)生存時間和簇負載平衡程度.

在上述研究的基礎(chǔ)上，筆者提出一種預約式智能停車場，利用手機App進行預約，超聲波傳感器檢測車輛有無，在線計時扣費，其中停車場中各個停車位傳感控制模塊構(gòu)成了無線傳感網(wǎng)絡(luò)，基于以上文獻都是在無線傳感網(wǎng)絡(luò)大范圍下提出的改進或者新算法，沒能針對停車場進行特定環(huán)境進行深度處理，提出一種更加適合停車場場景的LEACH的簇樹網(wǎng)絡(luò)的路由算法改進方法，在節(jié)點能耗方面得到很大改進，使得整個預約式智能停車場系統(tǒng)能夠完成停車到收費的自動化管理.

1系統(tǒng)概述和流程

1.1系統(tǒng)概述

基于無線傳感網(wǎng)絡(luò)的預約式智能停車場主要組成：具有查詢和預約車位以及在線支付功能的手機App[5-6]，是由具有無線通信和溫濕度檢測的Telosb節(jié)點、超聲波傳感器以及車位鎖等組成的停車位控制模塊.系統(tǒng)結(jié)構(gòu)框圖如圖1所示.圖1中的Sink, EndDevice只是分工不同的Telosb節(jié)點[7].

圖1　預約式智能停車場系統(tǒng)框架圖Fig.1　The frame chart of reserved-intelligent parking lot system

Sink節(jié)點一方面負責收集各個EndDevice的車位信息并通過串口輸出到電腦終端存儲到后臺中心，另一方面轉(zhuǎn)發(fā)后臺指令到某個具體的EndDevice實現(xiàn)車位鎖的操作.EndDevice實現(xiàn)車輛的檢測和對車位鎖的操作.

1.2系統(tǒng)流程

預約式智能停車場的系統(tǒng)停車流程如圖2所示，可分為如下6個步驟：

1) 車主打開手機App，輸入停車地點、時間和搜索范圍，搜索可用車位：范圍內(nèi)無有可用車位，返回1)；搜到可用車位，進入2).

2) 根據(jù)距離依次顯示最佳車位，用戶決定是否進行預約：不預約，返回2)；選擇某個車位進行預約，進入3).

3) 系統(tǒng)鎖定車主預約的車位，對后臺數(shù)據(jù)庫的車位狀態(tài)進行更新，提供用戶到達該車位的導航功能.

4) 車主到達該車位后，點擊手機App的開鎖按鈕，通過后臺傳送開鎖指令到具體的車位鎖，實現(xiàn)開鎖，車輛駛?cè)?，停車計費開始.

5) 超聲波傳感器模塊開始工作，對車輛是否離開進行檢測：檢測到未離開，返回5)；檢測到離開，進入到6).

6) 自動產(chǎn)生停車費用，從手機App的用戶賬戶上扣除，并自動對車位上鎖，后臺更新車位狀態(tài).

圖2　系統(tǒng)停車流程圖Fig.2　The flowchart of Parking system

2停車位檢測控制模塊

2.1Telosb節(jié)點

采用美國美新半導體(MEMSIC)公司開發(fā)的telosb節(jié)點TPR2420CA作為控制器和無線通信模塊，TPR2420CA把所有要素都集中在一個獨立的平臺上：USB 編程能力，IEE802.15.4 射頻器和天線，低功耗擴大內(nèi)存得MCU和可選的傳感器套件，其內(nèi)部結(jié)構(gòu)如圖3所示.

圖3　Telosb節(jié)點內(nèi)部結(jié)構(gòu)Fig.3　The internal structure of Telosb Node

2.2超聲波傳感器模塊

筆者采用HC-SR04超聲波測距模塊，具有測距精準和性能穩(wěn)定等優(yōu)點，模塊包含超聲波發(fā)射器、接收器與控制電路[8].該模塊通過一個控制端口發(fā)送一個大于10 μs的高電平，接收端口等待高電平輸出，一檢測到就打開定時器開始計時，直到轉(zhuǎn)為低電平時結(jié)束，通過高電平持續(xù)時間來計算測量的距離，公式為

測量距離=(高電平持續(xù)時間×聲速)/2

式中聲速為340 m/s.由于一般車輛底盤高度小于30 cm，只要對車輛的底盤高度進行檢測，就能知道車位上是否有車輛存在.超聲波傳感器裝在車位鎖底盤上，底盤與地面距離為10 cm左右，這里設(shè)定測量閾值為20 cm.為達到測量的結(jié)果準確性，可通過以下步驟：

Step 1連續(xù)3次測量車位上車輛底盤與超聲波傳感器之間的距離：若3次測量值都有效且都小于設(shè)定的閾值20 cm，則判定車位上有車輛存在；若3次測量值出現(xiàn)至少一次未檢測到有效值或者測量值大于閾值20 cm，則跳轉(zhuǎn)Step 2.

Step 2再次測量車輛底盤與超聲波傳感器之間的距離：若測量值都有效且小于設(shè)定的閾值20 cm，則跳轉(zhuǎn)Step 1繼續(xù)測量；若未檢測到有效值或者測量值大于閾值20 cm，則判定車位上無車輛存在.

通過實驗發(fā)現(xiàn)，該策略能保證檢測結(jié)果的成功率.在20 cm的閾值范圍內(nèi)，最低的判定成功率為95.5%.當要檢測車輛離開的動作時，按照上面提到的檢測車輛存在的策略，若上一次進行檢測，判定結(jié)果為存在車輛，緊接著下一次測量結(jié)果判定為不存在車輛，則判定檢測到車輛駛離的動作，從而正確做出相應的關(guān)閉車位鎖的動作.

3LEACH蔟樹網(wǎng)絡(luò)的路由算法改進

3.1改進算法的簇樹網(wǎng)絡(luò)建立

假定一個擁有116 個車位的城市停車場，各個停車位上都配置一個車位鎖，車位鎖包括一個超聲波傳感器和一個無線傳感網(wǎng)絡(luò)通信模塊，一個城市停車場無線傳感網(wǎng)絡(luò)就可以組建完成.網(wǎng)絡(luò)只擁有一個Sink節(jié)點，Sink節(jié)點和計算機連接，所以不考慮能源問題，其主要負責匯聚和分發(fā)數(shù)據(jù).這里防止安全干擾，對網(wǎng)絡(luò)節(jié)點進行安全加密處理.為了設(shè)計簡單，每一個車位的長度設(shè)為6 m，寬度設(shè)為3 m.國家技術(shù)監(jiān)督局、建設(shè)部聯(lián)合發(fā)布的《城市道路交通規(guī)劃設(shè)計規(guī)范》中對機動車公共停車場出入口設(shè)計作了如下規(guī)定：少于50 個停車位的停車場，可設(shè)計一個出入口，其寬度宜采用雙車道；50～300 個停車位的停車場，應設(shè)兩個出入口[9].因此采用雙出口，圖4表示對應的城市停車場車位示意圖.

將每個停車位抽象為一個無線傳感器節(jié)點，就可以形成如圖5所示的節(jié)點抽象圖，每個節(jié)點的坐標值可計算得知.對車位進行編號，車位號n從1～116，并以各個車位的中心點作為節(jié)點的坐標.各節(jié)點的直角坐標值(xn,yn)與車位號n的關(guān)系式分別為

圖4　停車場示意圖Fig.4　The schematic diagram of the parking lot

(1)

(2)

式中：xn，yn分別為節(jié)點的橫坐標和縱坐標；n為車位號.

圖5　停車位節(jié)點抽象圖Fig.5　The abstract diagram of Parking lot Node

在圖5所示的停車場中建立簇樹無線傳感網(wǎng)絡(luò)，可先將整個停車場區(qū)域劃分為8個區(qū)，區(qū)內(nèi)擁有一個簇頭節(jié)點與多個子節(jié)點，該網(wǎng)絡(luò)的匯聚節(jié)點Sink在停車場入口處，其坐標值(x0,y0)為(66,0)，Sink節(jié)點不算作116個車位節(jié)點.兩個無線傳感網(wǎng)絡(luò)節(jié)點的有效通信距離設(shè)定為60 m，超過60 m就只能通過路由器轉(zhuǎn)發(fā)才能到達.停車場的車位分區(qū)規(guī)劃如表1所示.

表1　停車場車位分區(qū)表

表2　16位通信地址結(jié)構(gòu)

LEACH協(xié)議采用了“輪數(shù)”的概念[10]，第一輪分為簇建立和穩(wěn)定工作兩個階段，通常為了減少能耗，簇建立階段的時間遠小于穩(wěn)定階段的持續(xù)時間.LEACH協(xié)議在初始化階段選取簇首按照以下策略來進行：

傳感器節(jié)點隨機生成一個0～1之間的隨機數(shù)，并且與閾值T(n)做比較，選取小于該閾值的節(jié)點作為簇頭.其中閾值T(n)的計算公式為

(3)

式中：p為節(jié)點成為網(wǎng)絡(luò)中簇頭節(jié)點的百分數(shù)；r為當前的輪數(shù)；G為一個集合，該集合中的節(jié)點是前1/p輪中沒有充當過簇頭節(jié)點的節(jié)點.

簇頭節(jié)點選定之后，會向其他各節(jié)點廣播自己成為簇頭的消息，各節(jié)點根據(jù)收到消息的強度來選擇加入哪個簇頭，并告知該簇頭節(jié)點.在穩(wěn)定工作階段，各個成員節(jié)點會將采集到的數(shù)據(jù)轉(zhuǎn)發(fā)到簇頭節(jié)點，經(jīng)過數(shù)據(jù)融合之后，統(tǒng)一發(fā)送到Sink節(jié)點，一段時間后，進行下一輪循環(huán)[11].從中可以看出:LEACH協(xié)議是假定所有節(jié)點擁有相同的能量并且簇頭節(jié)點能耗相同，在停車場網(wǎng)絡(luò)節(jié)點能量不均衡的網(wǎng)絡(luò)中不太適用.同時可能出現(xiàn)簇頭分布過于集中，從而導致網(wǎng)絡(luò)分布不均.

算法改進是針對蔟樹建立的和簇頭選擇過程中的，建立簇樹網(wǎng)絡(luò)利用上述的邏輯地址來進行，其步驟如下：

Step 1選取各個區(qū)內(nèi)的地址編碼最小的節(jié)點作為簇頭節(jié)點，選擇bit8作為簇頭標志位，并設(shè)置為1，默認狀態(tài)為0，申請加入由Sink組建的網(wǎng)絡(luò).

Step 2計算區(qū)內(nèi)的簇頭節(jié)點與Sink節(jié)點的距離計算公式為

(4)

1)計算簇頭節(jié)點與Sink節(jié)點之間的距離滿足d(0,n)<60 m，則判定可以直達，直接加入網(wǎng)絡(luò)，跳轉(zhuǎn)到Step 4.

2)計算簇頭節(jié)點與Sink節(jié)點之間的距離滿足d(0,n)≥60 m，則判定為加入網(wǎng)絡(luò)失敗，跳轉(zhuǎn)Step 3.

Step 3網(wǎng)絡(luò)中剩余的未能加入無線網(wǎng)絡(luò)的簇頭節(jié)點通過搜索成功加入網(wǎng)絡(luò)的簇頭，并計算與各個簇頭節(jié)點之間的距離d，滿足d(0,n)<60 m情況下，取d最小的簇頭節(jié)點作為父節(jié)點加入網(wǎng)絡(luò).若加入失敗，則繼續(xù)執(zhí)行Step 3；若加入成功，則跳轉(zhuǎn)到Step 4.

Step 4每個分區(qū)內(nèi)的剩余節(jié)點依次加入到該分區(qū)的簇頭節(jié)點下面，就此無線網(wǎng)絡(luò)建立完成.

一輪完畢后，A，C，F(xiàn)三個簇首由于和基站的距離超過60 m[8]，選取離他最近的簇首作為下一跳，所以通過建立多跳路由方式來和基站通信，避免直接通信所要花費更大的能耗.其他簇首和基站的距離少于60 m，直接和基站通信.

簇首形成及路由算法示意圖如圖6所示.當簇樹網(wǎng)絡(luò)完成建立后，會隨著節(jié)點剩余能量值來進行網(wǎng)絡(luò)重構(gòu)，以維持網(wǎng)絡(luò)的最大壽命.其具體的重構(gòu)方式如下：每一輪中計算各個區(qū)中的簇首節(jié)點的剩余能量(通過測量剩余電壓值)，若發(fā)現(xiàn)任意一個簇頭節(jié)點的剩余電壓值低于設(shè)定的閾值v(v初始值為90%的節(jié)點額定電壓，隨著輪數(shù)的增加而做出相應調(diào)整，現(xiàn)設(shè)定每經(jīng)過一輪降低10%額定電壓)，則進行簇頭重新選取，區(qū)內(nèi)的節(jié)點能量值(電壓值)由該區(qū)的簇頭節(jié)點來收集，選取每個區(qū)內(nèi)節(jié)點能量值最大(電壓值最高)作為新的簇頭節(jié)點，加入網(wǎng)絡(luò)參考上述步驟.原先每個區(qū)內(nèi)的簇頭節(jié)點都將以新的簇頭作為父節(jié)點加入網(wǎng)絡(luò)，各區(qū)內(nèi)剩余的節(jié)點都將加入到新的簇頭節(jié)點下.

圖6　簇首形成及路由算法示意圖Fig.6　The schematic diagram of first cluster routing algorithm

3.2與LEACH路由算法仿真結(jié)果比較

采用Matlab 2015a平臺作為仿真工具，通過仿真實驗比較改進后的LEACH算法和未改進的LEACH算法.在本次仿真中，根據(jù)設(shè)定的停車場的一個真實環(huán)境，共計116個節(jié)點和一個Sink節(jié)點，傳感器節(jié)點坐標分布圖如圖7所示.

圖7　傳感器節(jié)點坐標分布圖Fig.7　The distribution map of sensor nodes coordinate

系統(tǒng)中的存活節(jié)點數(shù)目直接影響無線傳感網(wǎng)絡(luò)的生命周期，從圖8可以看出：未改進的LEACH算法出現(xiàn)第一個死亡節(jié)點大約在270 s，而改進后的LEACH算法出現(xiàn)第一個死亡節(jié)點的時間大約是370 s.在相同的時間內(nèi)改進后的LEACH算法的網(wǎng)絡(luò)系統(tǒng)存活的節(jié)點數(shù)目明顯多于采用LEACH 算法的網(wǎng)絡(luò)系統(tǒng).這是因為改進后的LEACH算法通過增加節(jié)點位置信息，并人為地對區(qū)域劃分，更有效的簇頭選取方式，保證簇頭的能量為分區(qū)內(nèi)最大值，均衡了網(wǎng)絡(luò)負載，結(jié)合單跳與多跳的方式實現(xiàn)簇頭節(jié)點的通信，很大程度上減少了節(jié)點的能量消耗.

圖8　節(jié)點存活數(shù)Fig.8　The number of survival Node

從基站單位時間內(nèi)接收到的數(shù)據(jù)量，可以看出該網(wǎng)絡(luò)的傳輸時延，以及網(wǎng)絡(luò)通信流暢度.從圖9可見采用改進后的算法網(wǎng)絡(luò)中的基站接收到的數(shù)據(jù)量遠遠大于采用LEACH算法網(wǎng)絡(luò)中的基站接收到的數(shù)據(jù)量.這是因為改進后的算法避免了簇頭節(jié)點過早死亡而導致網(wǎng)絡(luò)生命周期過早結(jié)束，循環(huán)利用網(wǎng)絡(luò)中的能量，以達到最大利用率.

圖9　基站接收數(shù)據(jù)數(shù)量Fig.9　The quantity of the data received by base station

能量消耗問題是無線傳感網(wǎng)絡(luò)中最關(guān)心的指標，圖10表示改進的LEACH算法和未改進的LEACH算法的系統(tǒng)總能量消耗對比圖，從圖10中可以看出：采用改進后的算法，網(wǎng)絡(luò)中的總能量消耗速度較常規(guī)LEACH 算法能量消耗比較緩慢，隨著輪數(shù)的增加，效果更顯著.

圖10　總能量消耗Fig.10　The quantity of total energy consumption

4結(jié)論

提出的預約式智能停車場系統(tǒng)能夠?qū)⒁苿踊ヂ?lián)網(wǎng)技術(shù)和無線傳感網(wǎng)絡(luò)技術(shù)結(jié)合，提高了停車管理的信息化程度和設(shè)施利用率，“一車一位”的方式一定程度上減少了亂停放現(xiàn)象，使管理更加清晰化，最重要的是促使了停車的過程更加高效和方便.基于停車場特定的環(huán)境，提出在停車場無線傳感網(wǎng)絡(luò)中LEACH協(xié)議的改進算法，經(jīng)過仿真表明，改進的LEACH算法在能耗和能量使用效率上得到很大改進，并能夠更好地均衡網(wǎng)絡(luò)負載，使得預約式智能停車場能夠更有效的管理和操作，已運用到實際工程中.

參考文獻：

[1]KIM J M, PARK S H, HAN Y J, et al. CHEF: cluster head election mechanism using fuzzy logic in wireless sensor networks[C]//Advanced Communication Technology (ICACT). New York: IEEE,2008:654-659.

[2]JIN G, PARK M S. CAC: context adaptive clustering for efficient data aggregation in wireless sensor networks[J]. Networking technologies, services, and protocols; performance of computer and communication networks; mobile and wireless communications systems,2006(5):1132-1137.

[3]周玉，景博，楊洲.一種基于遺傳算法的無線傳感器網(wǎng)絡(luò)LEACH路由協(xié)議的改進算法[J].計算機研究與發(fā)展，2010(S2)：175-179.

[4]吳臻，金心宇.無線傳感器網(wǎng)絡(luò)的LEACH算法的改進[J].傳感技術(shù)學報，2006，19(1)：34-36.

[5]周曉，邊裕挺，李杰.基于Android智能終端的WSN監(jiān)控系統(tǒng)[J].浙江工業(yè)大學學報，2013，41(5)：558-561.

[6]MOREIRA N, VENDA M ,SILVA C , et al.Mobile application to monitor a WSN[C]//Information Systems and Technologies (CISTI). New York: IEEE Press,2011:1-6.

[7]陸歡佳，俞立，董齊芬，等.基于無線傳感網(wǎng)的樓宇環(huán)境監(jiān)測系統(tǒng)設(shè)計[J].浙江工業(yè)大學學報，2011，39(6)：683-687.

[8]李軍，申俊澤.超聲測距模塊HC—SR04的超聲波測距儀設(shè)計[J].單片機與嵌入式系統(tǒng)應用，2011，11(10)：77-78.

[9]中華人民共和國建設(shè)部.城市道路交通規(guī)劃設(shè)計規(guī)范：GB 50220—1995[S].北京：中國計劃出版社，1995.

[10]彭靜，劉光祜，謝世歡.無線傳感器網(wǎng)絡(luò)路由協(xié)議研究現(xiàn)狀與趨勢[J].計算機應用研究，2007，24(2)：4-9.

[11]周曉，朱仁烽，趙鋒，等.基于人工蜂群算法的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J].浙江工業(yè)大學學報，2014，42(5)：577-580.

(責任編輯：陳石平)

A smart reservation-parking system and an improved LEACH cluster routing algorthm

GU Hui, GU Jiejie

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:The ultrasonic sensors are used to detect the parking situation and the Apps installed in cell phone can be used to inquire and reserve parking service in this paper. A control and management method for the smart reservation-parking is proposed combining with ultrasonic sensor technology, wireless sensor network technology, as well as mobile Internet technology. During construction process of wireless sensor networks in the parking system, based on a particular scene, an improved routing algorithm based on LEACH cluster tree network approach is proposed. The simulation experiments on Matlab show that the improved algorithm greatly reduces the energy consumption of nodes and extends the wireless sensor network life cycle in the parking system. The entire smart reservation-parking system can be managed effectively.

Keywords:parking control; ultrasonic; App; wireless sensor networks; LEACH cluster tree network

收稿日期：2015-11-10

作者簡介：古輝(1962—)，男，山西孝義人，教授，研究方向為模式識別與圖形圖像處理技術(shù)，E-mail：gh@zjut.edu.cn.

中圖分類號：TP391

文獻標志碼：A

文章編號：1006-4303(2016)02-0134-06