MDS-MAP算法的改進及在室內(nèi)車輛定位中的應(yīng)用

喬中標， 李津蓉， 馬連偉

(浙江科技學(xué)院 a.機械與汽車工程學(xué)院；b.自動化與電氣工程學(xué)院，杭州 310023)

?

MDS-MAP算法的改進及在室內(nèi)車輛定位中的應(yīng)用

喬中標a， 李津蓉b， 馬連偉b

(浙江科技學(xué)院 a.機械與汽車工程學(xué)院；b.自動化與電氣工程學(xué)院，杭州 310023)

為了解決現(xiàn)代化大型停車場尋車難的問題，提出一種基于無線傳感器網(wǎng)絡(luò)的定位算法。即以經(jīng)典的MDS-MAP(multidimensional scaling-map)節(jié)點定位算法為基礎(chǔ)，在全局范圍內(nèi)選擇1個一跳的鄰居節(jié)點子網(wǎng)，對其進行相對定位；結(jié)合極大似然估計法，計算出其余節(jié)點的相對坐標；利用錨節(jié)點的坐標信息，得到網(wǎng)絡(luò)內(nèi)所有待測節(jié)點的絕對坐標。仿真結(jié)果表明，改進后的算法可以解決停車場形狀不規(guī)則及車輛隨機停放等情況所造成的網(wǎng)絡(luò)空洞問題。因此，該算法能在很大程度上提高定位的精確性，適用于大型室內(nèi)停車場的實際情況。

大型室內(nèi)停車場；車輛定位；無線傳感器網(wǎng)絡(luò)；MDS-MAP；定位誤差

隨著社會的高速發(fā)展與人們消費水平的不斷提高，汽車的擁有量也在逐年提升。汽車數(shù)量的激增給人們帶來了諸多不便，如大型停車場“尋車難”的問題就經(jīng)常困擾著車主。由于停車場內(nèi)沒有參照物，要找到自己的車經(jīng)常要花費較長的時間，而傳統(tǒng)的停車場系統(tǒng)很難解決這個問題。傳統(tǒng)的GPS定位成本高，并且在有物體遮擋住衛(wèi)星信號時則無法進行定位[1-2]，因此GPS并不適用于室內(nèi)停車場。目前室內(nèi)無線定位技術(shù)主要有ZigBee、RFID(射頻識別技術(shù))及Wi-Fi等技術(shù)[3-4]，如文獻[5]中設(shè)計了基于Wi-Fi指紋定位的智能停車場系統(tǒng)，系統(tǒng)包括免取卡停車、智能導(dǎo)航、反向?qū)ぼ嚨裙δ?；文獻[6]中設(shè)計了基于RSSI的室內(nèi)停車場車輛定位算法，該算法在停車位處部署車輛節(jié)點，在天花板或墻體上部署匯聚節(jié)點[7]，將地標節(jié)點(坐標已知的節(jié)點)部署在停車場的各個位置，當1個車輛節(jié)點可以同時接收到3個地標節(jié)點信號時，利用三角測量法[8]計算車輛節(jié)點的位置；文獻[9]中設(shè)計了基于CSS技術(shù)和TOA(信號到達時間差)[10]的室內(nèi)停車場車輛定位算法，該算法利用CSS技術(shù)實現(xiàn)數(shù)據(jù)通信，再使用基于TOA改進的SDS-TWR雙邊雙向測距算法，測量基站與車輛節(jié)點的距離，在得到1個車輛節(jié)點與3個基站的距離后，利用改進的三邊算法[11]計算出車輛節(jié)點的位置。

綜觀現(xiàn)有的室內(nèi)停車定位算法，大多存在定位不準確或者系統(tǒng)成本較高的問題。MDS-MAP(multidimentional scaling-map)算法[12]是基于多維定標MDS的節(jié)點定位算法，該算法是由美國密蘇里哥倫比亞大學(xué)的Shang Yi等人最早提出的，并將其運用到無線傳感器網(wǎng)絡(luò)節(jié)點定位上[13]。MDS-MAP算法與應(yīng)用較為廣泛的LANDMARC和VIER室內(nèi)定位算法相比，其定位參考標簽的部署沒有嚴格的要求，且需要的數(shù)量較少；同時，MDS-MAP算法也不存在對邊界處節(jié)點定位誤差大的問題。但在經(jīng)典MDS-MAP算法中，當兩個節(jié)點的距離較遠而無法直接計算歐氏距離時，算法就利用網(wǎng)絡(luò)節(jié)點間的最短路徑距離來代替節(jié)點間的歐氏距離，因此當網(wǎng)絡(luò)拓撲結(jié)構(gòu)不規(guī)則或存在空洞時，距離的近似計算就會存在較大的誤差，最終導(dǎo)致定位不準確。室內(nèi)停車場的平面形狀及車輛實際停放的情況，使得以車輛節(jié)點組成的網(wǎng)絡(luò)拓撲結(jié)構(gòu)并不規(guī)則，因此用經(jīng)典算法無法進行準確的定位。筆者對MDS-MAP算法進行了改進，提出了一種基于一跳子網(wǎng)中節(jié)點間距的MOH(MDS one-hop)算法。改進的算法先對1個一跳子網(wǎng)內(nèi)的節(jié)點進行定位，然后利用極大似然估計法[14-15]對子網(wǎng)外的其余節(jié)點逐個進行定位，直到覆蓋整個網(wǎng)絡(luò)，最后將得到的相對坐標轉(zhuǎn)換成節(jié)點的絕對坐標，從而實現(xiàn)精確定位目標。

1 停車場車輛定位系統(tǒng)設(shè)計

車輛定位系統(tǒng)主要分為無線傳感器網(wǎng)絡(luò)模塊、數(shù)據(jù)處理模塊、信息發(fā)布與顯示模塊[16]。定位系統(tǒng)中的無線傳感器節(jié)點使用線性調(diào)頻擴頻技術(shù)進行通信，線性調(diào)頻擴頻技術(shù)的鏈路層、控制層及物理層均采用IEEE802.15.4a技術(shù)標準并施以擴展。

1.1 傳感器網(wǎng)絡(luò)模塊

將無線傳感器節(jié)點制作成定位標簽，當車輛入庫時領(lǐng)取定位標簽，與此同時利用攝像機拍下車牌號，在后臺服務(wù)器中與定位標簽的信息綁定。當車輛駛?cè)胪＼噲鰠^(qū)域后，定位標簽便接入整個無線傳感器網(wǎng)絡(luò)。

1.2 信息處理模塊

服務(wù)器每隔5 s對定位標簽的數(shù)據(jù)進行采集，計算處理后生成車輛的定位信息。

1.3 信息發(fā)布與顯示模塊

利用編程軟件制作一個顯示界面，將車輛的定位信息與停車場的電子地圖相結(jié)合，從而實現(xiàn)車主在手機終端上車輛的可視化查找。

停車場車輛定位流程如圖1所示，定位系統(tǒng)架構(gòu)如圖2所示。

圖1 停車場車輛定位流程示意圖Fig.1 Schematic diagram of vehicle positioning process in parking lots

圖2 停車場車輛定位系統(tǒng)架構(gòu)圖Fig.2 Structure diagram of vehicle positioning system in parking lots

2 MDS-MAP算法的改進

2.1 MDS-MAP定位算法簡介

MDS-MAP算法的核心思想是得到節(jié)點間的距離矩陣，進而利用MDS方法獲得各節(jié)點的相對坐標；然后利用已知的錨節(jié)點將相對坐標轉(zhuǎn)化成實際環(huán)境中的絕對坐標。具體方法如下。

假設(shè)某監(jiān)控區(qū)域內(nèi)有n個傳感器節(jié)點，節(jié)點i和節(jié)點j之間歐氏距離為：

(1)

不能通信的兩節(jié)點之間的距離用節(jié)點間的最短路徑距離來代替。根據(jù)各節(jié)點間的距離估值，建立網(wǎng)絡(luò)節(jié)點的距離矩陣D。

(2)

式(2)中：Q表示坐標系旋轉(zhuǎn)和鏡像映射的過程；B表示坐標系平移的過程。Q和B的元素值可通過已知錨節(jié)點的實際坐標與其對應(yīng)的相對坐標計算得到。

用最短路徑距離代替節(jié)點間的歐氏距離必然會存在誤差，特別是當傳感器網(wǎng)絡(luò)中存在通信空洞或網(wǎng)絡(luò)部署區(qū)域很不規(guī)則時，誤差會非常明顯。為了解決這一問題，并且讓其適用于室內(nèi)停車場車輛定位的環(huán)境，筆者將其做了改進，提出了MOH算法。

2.2MAD-MAP算法的改進

極大似然估計的基本思想就是,利用1個未知節(jié)點可以接收到多個錨節(jié)點信息來構(gòu)建由多個方程式組成并擁有唯一解的系統(tǒng)，在解方程的過程中引入最小均方誤差來得到方程組的最優(yōu)解。在改進算法中使用極大似然估計可以降低那些定位誤差較大的節(jié)點對新節(jié)點定位精度的影響，提高了定位的魯棒性。

MOH算法首先選取1個一跳范圍的子網(wǎng)進行定位，得到子網(wǎng)中節(jié)點的相對坐標后，再以子網(wǎng)內(nèi)的節(jié)點作為錨節(jié)點，利用極大似然估計對子網(wǎng)外的節(jié)點進行定位。這樣就可以避免用最短路徑代替歐氏距離所產(chǎn)生的定位誤差。

假設(shè)現(xiàn)有由n個節(jié)點組成的自組織無線傳感器網(wǎng)絡(luò)，坐標矩陣為X=[X1,X2,…,Xn]T，其中Xi=(xi,yi),i=1,2,…,n，表示第i個節(jié)點的坐標。新算法步驟如下。

1)根據(jù)節(jié)點間是否可以相互通信構(gòu)建一個n×n的鄰接矩陣A。如果節(jié)點i可以接收到節(jié)點j的信號，即節(jié)點j是節(jié)點i的一跳節(jié)點，則矩陣元素aij=1，否則aij=0。

2)在整個網(wǎng)絡(luò)內(nèi)找出1個全連接的子網(wǎng)，該子網(wǎng)內(nèi)的節(jié)點全都互為一跳節(jié)點。對鄰接矩陣A進行如下處理便可得到1個子網(wǎng)：

①刪除矩陣A中鄰居節(jié)點最少的行和列，得到新矩陣A1；

②檢驗新矩陣是否是全1矩陣，是則退出循環(huán)；否則令A(yù)=A1，重新執(zhí)行步驟①。

經(jīng)以上步驟便可得到一個全1矩陣，將矩陣A1的行(或列)所對應(yīng)的節(jié)點作為集合Vin，子網(wǎng)外的節(jié)點作為集合Vout。如果全網(wǎng)絡(luò)節(jié)點的集合為V，則有Vin=V-Vout。

3)利用MDS方法計算集合Vin中節(jié)點的相對坐標。集合Vin中節(jié)點間的歐氏距離都可以測到，因此可以利用MDS方法計算其相對坐標。

4)在集合Vout中搜索一個節(jié)點v，要求在集合Vin中至少有3個節(jié)點是節(jié)點v的一跳節(jié)點。假如集合Vin有節(jié)點v1，v2，…，vm都是節(jié)點v的一跳鄰居節(jié)點。而這m個節(jié)點的相對坐標已知，因此可利用極大似然估計法算出節(jié)點v的相對坐標。得到節(jié)點v的相對坐標后，將節(jié)點v加入到集合Vin中。

3 仿真實驗

用MATLAB模擬停車場的環(huán)境來對經(jīng)典MDS-MAP算法與改進MDS-MAP(MOH)算法的性能進行比較。

3.1 車輛節(jié)點部署及參數(shù)設(shè)定

圖3 車輛節(jié)點分布圖Fig.3 Diagram of vehicle node distribution

假設(shè)現(xiàn)有1個200m×200m的室內(nèi)停車場。沿橫坐標方向和縱坐標方向每隔10m停放1輛車，并且每輛車的實際位置都在此基礎(chǔ)上有2m的偏差。每輛車上都裝配無線傳感器網(wǎng)絡(luò)節(jié)點，總共265個傳感器節(jié)點，其中27個錨節(jié)點；節(jié)點通信半徑為50m。為了模擬車輛分布區(qū)域的不規(guī)則，這里在200m×200m的區(qū)域內(nèi)去除一個120m×160m的區(qū)域，這部分區(qū)域車輛不可以停放。圖3即為車輛節(jié)點的分布圖。圖3中，小圓圈代表車輛節(jié)點，星號代表錨節(jié)點。此時網(wǎng)絡(luò)中節(jié)點的平均連通度為43.8。

3.2 算法性能對比

用經(jīng)典MDS-MAP算法進行定位，效果如圖4所示。圖4中，小圓圈表示車輛節(jié)點的估算位置，線段表示車輛節(jié)點實際位置與理論位置的偏差，線段的另一端代表車輛節(jié)點的實際位置?？梢姡媒?jīng)典的MDS-MAP算法進行定位，誤差非常大。

用改進后的算法對車輛節(jié)點進行定位,首先模擬理想情況(即節(jié)點間的距離可以準確測得)，得到定位結(jié)果如圖5所示。

圖4 MDS-MAP算法定位誤差圖Fig.4 Diagram of localization error of MDS-MAP algorithm

圖5 MOH算法定位誤差圖Fig.5 Diagram of localization error of MOH algorithm

由圖5可以看出，圖中沒有明顯的表示定位誤差的線段，此時由于定位誤差小，線段近似成了一個點，基本上都位于小圓圈當中，這說明定位比較精準。

3.3 測距誤差與通信半徑對定位精度的影響

(3)

圖5是理想條件下的定位結(jié)果，其定位誤差均值約為1.0×10-4m。在實際環(huán)境中，傳感器節(jié)點利用信號的傳播損耗來測量距離是存在誤差的。因此，加上節(jié)點通信半徑距離5%的測距誤差來測試定位的效果，如圖6所示。

由圖6可知，當測距誤差為5%時，也可以得到較為理想的定位結(jié)果。在節(jié)點通信半徑固定為50m的情況下，分別以測距誤差為0%、5%、10%、15%、20%來進行測試，得到其平均定位誤差分別為0.001、2.75、6.95、9.45、21.50m?？梢姡敎y距誤差增加時，平均定位誤差也在增加。因此在工程實踐中，如果測距誤差超過一定的范圍，定位結(jié)果將沒有意義。

節(jié)點的通信半徑也對定位精度存在影響。圖7是在測距誤差分別為0%、5%、10%和15%的情況下，得到的節(jié)點通信半徑與平均定位誤差之間的關(guān)系圖。

圖6 5%測距誤差定位效果圖Fig.6 Positioning effect diagram of 5% ranging error

圖7 通信半徑與平均定位誤差的關(guān)系圖Fig.7 Diagram of relation between communication radius and average localization error

由圖7可以看出，隨著通信距離的增大，平均定位誤差逐漸減小，并趨于穩(wěn)定。測距誤差越大，最終趨于穩(wěn)定的平均誤差值也越大。顯然，減小測距誤差和提高節(jié)點的通信半徑可以提高節(jié)點的定位精度。

4 結(jié) 論

筆者提出了一種基于無線傳感器網(wǎng)絡(luò)的室內(nèi)停車場車輛定位算法，該算法在MDS-MAP算法的基礎(chǔ)上進行改進，使其適用于室內(nèi)停車場車輛停放的實際情況。仿真試驗表明，與傳統(tǒng)算法相比，改進后的算法可以對車輛節(jié)點進行較為準確的定位，且增加節(jié)點通信半徑可以提高定位的精度。但是，由于該種集中式算法會存在誤差累計的問題，特別是當測距誤差增大時，某些節(jié)點會存在較大的定位誤差，因此在這些方面還需做進一步研究。

[1] 黃藝，胡善岳，何芹,等.基于Android平臺的移動通訊設(shè)備的GPS定位研究[J].激光雜志，2014，35(3):42.

[2] 李博文，姚丹亞，蔣鳳成.車載GPS定位滯后時間的計算方法[J].清華大學(xué)學(xué)報(自然科學(xué)版)，2014，54(9):1215.

[3] 趙軍，李鴻斌，王智.無線網(wǎng)絡(luò)室內(nèi)定位系統(tǒng)研究[J].信息與控制，2008，37(4):465.

[4] 夏英，王磊，劉兆宏.基于無線局域網(wǎng)接收信號強弱分析的混合室內(nèi)定位方法[J].重慶郵電大學(xué)學(xué)報(自然科學(xué)版)，2012，24(2):219.

[5] 黃旭，范婧，吳茂念，等.基于Wi-Fi指紋定位技術(shù)的智能停車場系統(tǒng)的設(shè)計與實現(xiàn)[J].計算機科學(xué)，2016，43(6A):512.

[6] 路正，王曉燕.基于無線傳感器網(wǎng)絡(luò)的室內(nèi)停車場定位系統(tǒng)[J].通訊技術(shù)，2012，33(10):67.

[7] 夏侯凱順，余輝榮，鄔依林，等.基于自適應(yīng)分簇的改進RSSI定位算法[J].微電子學(xué)與計算機，2014，31(5):103.

[8] 馮秀芳，王麗娟，關(guān)志艷.無線傳感器網(wǎng)絡(luò)研究與應(yīng)用[M].北京：國防出版社，2014:138.

[9] 李國良，丁施健，王陽，等.基于CSS技術(shù)和TOA的室內(nèi)停車場定位系統(tǒng)[J].南京師范大學(xué)學(xué)報(工程技術(shù)版)，2015，15(3):64.

[10]WANGA,YANGK,JIANPINGAN.Totalleast-squaresalgorithmfortimeofarrivalbasedwirelesssensornetworkslocation[J].IEICETransactionsonFundamentalsofElectronics,CommunicationsandComputerSciences,2011,94(9):1851.

[11] 劉玉軍，蔡猛，高立恒.基于RSSI測距的傳感器節(jié)點質(zhì)心定位修正算法[J].計算機測量與控制，2014，22(9):2860.

[12]AMINK,OHS.Robustlocalizationfromincompletelocalinformation[J].IEEE-ACMTransactiononSignalProcessing,2013,21(4):1131.

[13]SHANGY,RUMLW.ImprovedMDS-basedlocation[C]//Proceedingsofthe23rdInternationalConferenceoftheComputerCommunications.Piscataway:IEEE,2004:2640.

[14] 劉健苗，許新忠，黃書廣，等.改進的分布式無線傳感器網(wǎng)絡(luò)多維標度定位算法[J].傳感技術(shù)學(xué)報,2014,27(5):692.

[15]WEISSAJ,PICARDJS.Networklocalizationwithbiasedrangemeasurements[J].IEEETransactionsonWirelessCommunications,2008,7(1):298.

[16] 劉敏，張國山，邴志剛，等.大型停車場中車輛定位問題研究[J].系統(tǒng)仿真技術(shù),2014，10(3):192.

Improvement of MDS-MAP algorithm and its application in indoor vehicle localization

QIAO Zhongbiaoa， LI Jinrongb， MA Lianweib

(a. School of Mechanical and Automotive Engineering; b. School of Automation and Electrical Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, Zhejiang, China)

To solve the problem of positioning vehicles in modern large-scale parking lots, a localization algorithm based on wireless sensor networks is proposed. Firstly, on the basis of the classical multidimensional scaling-map(MDS-MAP) node positioning algorithm, a one-hop neighbor node subnet is selected within the global network and positioned; and then the relative coordinates of the remaining nodes are able to be calculated by combining the estimation method of maximum likelihood; finally, the absolute coordinates of all unknown nodes in the network can be obtained by utilizing the coordinate information of anchor nodes. Simulation results show that the improved algorithm can solve the problem of the network cavity caused by the irregular shape of the parking lot and random parking of vehicles, which can greatly enhance accuracy of localization, more applicable to the actual situation of large-scale indoor parking lots.

large-scale indoor parking lots; vehicle positioning; wireless sensor networks; MDS-MAP (multidimentional scaling-map); localization error

10.3969/j.issn.1671-8798.2017.03.007

2017-02-28

國家自然科學(xué)基金項目(61540034)；浙江省公益性技術(shù)應(yīng)用研究計劃項目(2014C31020)

李津蓉(1977— )，女，天津市人，副教授，博士，主要從事無線傳感器網(wǎng)絡(luò)節(jié)點定位和智能學(xué)習(xí)算法研究。E-mail: jrli@zust.edu.cn。

TP212.9

A

1671-8798(2017)03-0195-06