連宗凱,袁飛，祁偉

（廣東技術(shù)師范學(xué)院自動(dòng)化學(xué)院，廣州510000）

改進(jìn)K均值聚類BP神經(jīng)網(wǎng)絡(luò)超寬帶室內(nèi)定位方法

連宗凱,袁飛，祁偉

（廣東技術(shù)師范學(xué)院自動(dòng)化學(xué)院，廣州510000）

室內(nèi)定位技術(shù)隨著生產(chǎn)生活對室內(nèi)定位的需求不斷提高而成為熱點(diǎn)問題之一，超寬帶定位技術(shù)以其獨(dú)特的優(yōu)勢而快速發(fā)展，針對超寬帶定位系統(tǒng)定位數(shù)據(jù)存在穩(wěn)定性差、精度低的問題，提出改進(jìn)K均值聚類BP神經(jīng)網(wǎng)絡(luò)超寬帶室內(nèi)定位方法。該方法對超寬帶定位系統(tǒng)中原始數(shù)據(jù)進(jìn)行改進(jìn)K均值聚類算法的預(yù)處理，過濾位置偏差大的數(shù)據(jù)。再對測定區(qū)域內(nèi)多點(diǎn)進(jìn)行基于真實(shí)坐標(biāo)和聚類過濾坐標(biāo)的BP神經(jīng)網(wǎng)絡(luò)建模。定位過程則將過濾后的待定位坐標(biāo)輸入建好的BP神經(jīng)網(wǎng)絡(luò)定位模型，進(jìn)行識別定位。通過實(shí)驗(yàn)測定，該室內(nèi)定位方法精度可達(dá)26cm，且穩(wěn)定性好。

2016廣東省科技廳（No.2016A040403122）

0 引言

室內(nèi)定位應(yīng)用廣泛，在商場、機(jī)場等大型建筑物內(nèi)，家居環(huán)境中的服務(wù)機(jī)器人領(lǐng)域都是關(guān)鍵技術(shù)。研究室內(nèi)定位意義重大。根據(jù)定位所采用的測量標(biāo)度可以分為基于視覺的室內(nèi)定位、基于超聲波的定位、基于激光測距定位、基于慣性加速度傳感器定位和基于無線網(wǎng)絡(luò)的定位方法。視覺定位存在計(jì)算復(fù)雜度高的問題?；诔暡ǖ亩ㄎ淮嬖谑芏ㄎ画h(huán)境影響大的問題?；诩す鉁y距受室內(nèi)障礙物等外部因素影響大的問題。因此在實(shí)際應(yīng)用中，基于無線網(wǎng)絡(luò)的室內(nèi)定位方法研究得最多。

目前，基于無線網(wǎng)絡(luò)的室內(nèi)定位所采用的網(wǎng)絡(luò)類型主要包括藍(lán)牙、無線局域網(wǎng)（WLAN）、射頻識別（RFID）、ZigBee、超寬技術(shù)[1]。這些網(wǎng)絡(luò)中，定位精度最高的為超寬帶技術(shù)。其他無線網(wǎng)絡(luò)在使用中受到環(huán)境影響較大，定位精度相對較低。

UWB具有功耗低、頻帶極寬、短距離傳輸速率高、隱蔽抗干擾、時(shí)間分辨率高、穿透能力強(qiáng)等優(yōu)勢。這些優(yōu)勢提供了厘米級定位基礎(chǔ)[2]，并且超寬帶定位系統(tǒng)裝配簡單、算法時(shí)間復(fù)雜度和空間復(fù)雜度低。

由于室內(nèi)環(huán)境復(fù)雜，干擾源多，超寬帶定位系統(tǒng)存在非視距傳播和多徑傳播現(xiàn)象，導(dǎo)致返回的原始位置數(shù)據(jù)存在漂移現(xiàn)象，嚴(yán)重影響定位精度[3]。為此本文提出改進(jìn)K均值聚類BP神經(jīng)網(wǎng)絡(luò)超寬帶室內(nèi)定位方法。該方法先采用改進(jìn)K均值聚類算法對原始坐標(biāo)信息進(jìn)行過濾優(yōu)化，接著使用優(yōu)化過的數(shù)據(jù)訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)構(gòu)建定位模型，最后利用該模型識別經(jīng)過改進(jìn)K均值聚類處理過的待識別位置坐標(biāo)，從而得到最終定位結(jié)果。

1 超寬帶室內(nèi)定位系統(tǒng)

本文采用超寬帶定位系統(tǒng)包括四個(gè)定位錨節(jié)點(diǎn)（A1，A2，A3，A4）和一個(gè)移動(dòng)目標(biāo)節(jié)點(diǎn)（Tag）。當(dāng)Tag位于某個(gè)位置時(shí)，Tag向四個(gè)錨節(jié)點(diǎn)發(fā)送數(shù)據(jù)，錨節(jié)點(diǎn)收到數(shù)據(jù)后，向Tag返回?cái)?shù)據(jù)。Tag根據(jù)發(fā)送數(shù)據(jù)和接收到數(shù)據(jù)之間的時(shí)間差，得到Tag與錨節(jié)點(diǎn)A1，A2，A3，A4間距離分別為d1、d2、d3和d4。再利用錨節(jié)點(diǎn)和Tag節(jié)點(diǎn)間空間幾何關(guān)系，得到Tag的坐標(biāo)數(shù)據(jù)，該坐標(biāo)數(shù)據(jù)為超寬帶系統(tǒng)采集到的原始坐標(biāo)數(shù)據(jù)。

2 改進(jìn)K均值聚類算法的數(shù)據(jù)預(yù)處理

對于某個(gè)已知位置，超寬帶定位系統(tǒng)受環(huán)境影響，存在采集到的原始坐標(biāo)數(shù)據(jù)漂移的問題，若采用傳統(tǒng)均值過濾方法，也存在過濾后坐標(biāo)受漂移點(diǎn)影響大的問題。因此，本文通過改進(jìn)k均值聚類算法對原始坐標(biāo)數(shù)據(jù)進(jìn)行聚類預(yù)處理，將漂移坐標(biāo)數(shù)據(jù)與可靠坐標(biāo)數(shù)據(jù)進(jìn)行區(qū)分，用可靠坐標(biāo)數(shù)據(jù)的中心作為該已知位置的坐標(biāo)數(shù)據(jù)。改進(jìn)K均值聚類算法也克服了k均值聚類算法需要事先指定聚類數(shù)K和易陷入局部最優(yōu)的問題。

改進(jìn)K均值聚類算法的數(shù)據(jù)預(yù)處理分為三步：Canopy算法確定聚類數(shù)K和初始聚類中心；K均值聚類算法確定各簇內(nèi)數(shù)據(jù)；根據(jù)各簇內(nèi)坐標(biāo)數(shù)據(jù)個(gè)數(shù)確定可靠坐標(biāo)數(shù)據(jù)。

2.1 Canopyy算法確定聚類數(shù) k和初始聚類中心

本文采用Canopy的算法是以歐氏距離作為相似度標(biāo)準(zhǔn)，在聚類速度有很大優(yōu)勢，可應(yīng)用與K均值聚類之前做粗聚類預(yù)處理得到K值與K均值聚類算法的初始聚類中心[4]。

Canopy算法的原理是對一個(gè)給定的包含n個(gè)d維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集合X={x1,x2,…,xn}，其中xi=｛xi1,xi2,…,xid｝，以歐氏距離作為相似度評判標(biāo)準(zhǔn)，通過給出兩個(gè)距離（T1,T2且T1

該算法步驟如圖1 Canopy算法流程圖所示。

上述過程之后，將k值與k個(gè)中心坐標(biāo)賦值給K均值聚類算法作為k值與初始聚類中心

2.2 K均值聚類算法確定各簇內(nèi)數(shù)據(jù)

K均值聚類算法的原理是對一個(gè)給定的包含n個(gè)d維數(shù)據(jù)點(diǎn)的數(shù)據(jù)集合X={x1,x2,…,xn}，其中xi={xi1,xi2，…，xid}，以歐氏距離作為相似度評判標(biāo)準(zhǔn)，將X劃分為K個(gè)數(shù)據(jù)子集C={Ci,i=1,2,…,K}[5]。

圖1 Canopy算法流程圖

K均值算法是反復(fù)迭代直到收斂的過程，收斂條件為聚類各聚類中心點(diǎn)移動(dòng)幅度小于設(shè)定的閾值ε，算法流程包括四個(gè)步驟如圖2 K均值聚類算法流程圖所示。

圖2 K均值聚類算法流程圖

從上不難看出，K均值聚類算法存在兩個(gè)缺陷：

①k值的確定沒有自動(dòng)化

②初始聚類中心選取沒有自動(dòng)化

在不同的問題應(yīng)用里，K值往往是是難以估計(jì)的，而初始聚類中心的選取則對聚類結(jié)果有較大影響，因此結(jié)合Canopy聚類算法改進(jìn)K均值聚類算法以克服以上兩個(gè)缺陷是有必要的。

2.3 確定可靠坐標(biāo)數(shù)據(jù)

K均值聚類算法得K個(gè)數(shù)據(jù)子集C={Ci,i=1,2,…,K}，計(jì)算每個(gè)Ci中數(shù)據(jù)的數(shù)量，取數(shù)量最大的Ci作為可靠數(shù)據(jù)，輸出該可靠數(shù)據(jù)集的均值中心作為可靠坐標(biāo)數(shù)據(jù)Cicenter。

3 BP神經(jīng)網(wǎng)絡(luò)定位模型構(gòu)建

超寬帶定位系統(tǒng)對多個(gè)已知位置的原始坐標(biāo)數(shù)據(jù)進(jìn)行改進(jìn)k均值聚類算法的數(shù)據(jù)預(yù)處理后，將這多個(gè)（已知位置、可靠數(shù)據(jù)中心）數(shù)據(jù)對通過BP神經(jīng)網(wǎng)絡(luò)[6]構(gòu)建定位模型，以便對待識別位置的坐標(biāo)數(shù)據(jù)進(jìn)行識別。

BP神經(jīng)網(wǎng)絡(luò)定位模型構(gòu)建如圖3 BP神經(jīng)網(wǎng)絡(luò)模型構(gòu)建流程圖所示：

圖3 BP神經(jīng)網(wǎng)絡(luò)模型構(gòu)建流程圖

4 待定位位置的定位確定

圖4模型建立與定位識別框圖給出了改進(jìn)K均值聚類算法與BP神經(jīng)網(wǎng)絡(luò)整合的定位算法過程：

首先將超寬帶定位系統(tǒng)返回的原始數(shù)據(jù)送入Canopy預(yù)處理，獲取k值后再將k值與原始數(shù)據(jù)送入K均值聚類處理，最后將K均值聚類算法中數(shù)據(jù)量最大的類的均值中心送入BP神經(jīng)網(wǎng)絡(luò)的輸入層，通過BP神經(jīng)網(wǎng)絡(luò)定位模型輸出定位位置。

圖4 模型建立與定位識別框圖

基于改進(jìn)K-means聚類算法與BP神經(jīng)網(wǎng)絡(luò)整合的定位算法方案有優(yōu)勢如下：

①保留單獨(dú)使用算法的優(yōu)勢，即運(yùn)算時(shí)時(shí)間復(fù)雜度和空間復(fù)雜度低，無需求取復(fù)雜參數(shù)；

②消除兩者單獨(dú)作用于該定位系統(tǒng)時(shí)的缺點(diǎn)，K均值聚類算法為BP神經(jīng)網(wǎng)絡(luò)提高的樣本與待識別位置的準(zhǔn)確性，BP神經(jīng)網(wǎng)絡(luò)算法則對K均值聚類算法的結(jié)果做進(jìn)一步精細(xì)擬合。

5 定位精確度檢驗(yàn)

5.1 定位精確度指標(biāo)

定位精確度是評價(jià)定位技術(shù)的重要指標(biāo)。本文針對定位精確度采用均方根誤差作為評價(jià)定位方法的性能指標(biāo)：式中Pi表示第i個(gè)坐標(biāo)信息，表示與i個(gè)坐標(biāo)信息對應(yīng)的實(shí)際坐標(biāo)。

5.2 實(shí)驗(yàn)數(shù)據(jù)采集

實(shí)驗(yàn)時(shí)，在廣東技術(shù)師范學(xué)院自動(dòng)化學(xué)院機(jī)器人實(shí)驗(yàn)室內(nèi)，部署了超寬帶定位系統(tǒng)。設(shè)備部署如圖5實(shí)驗(yàn)環(huán)境與設(shè)備部署所示。

超寬帶定位系統(tǒng)包括四個(gè)定位錨節(jié)點(diǎn)A1，A2，A3，A4和一個(gè)移動(dòng)目標(biāo)節(jié)點(diǎn)Tag，在實(shí)驗(yàn)室采用吸頂方式水平按照位置固定四個(gè)錨節(jié)點(diǎn)，形成一個(gè)400× 600的矩形，天線朝下與地面垂直；移動(dòng)目標(biāo)通過超寬帶定位系統(tǒng)相配套的配置軟件，以A1為原點(diǎn)建立空間直角坐標(biāo)系，根據(jù)實(shí)際距離設(shè)置各個(gè)定位錨節(jié)點(diǎn)的坐標(biāo)：A1（0，0，285）、A2（400，600，285）、A3（0，600，285）、A4（400，600，285），啟動(dòng)超寬帶定位系統(tǒng)即可通過串口接收該系統(tǒng)返回的融合定位數(shù)據(jù)。四個(gè)錨節(jié)點(diǎn)圍成平面所投影地面按照相鄰100cm取參考位置。

圖5 實(shí)驗(yàn)環(huán)境與設(shè)備部署

實(shí)驗(yàn)環(huán)境為實(shí)驗(yàn)室一個(gè)10×10的矩形區(qū)域，定位區(qū)域內(nèi)為視距環(huán)境，定位區(qū)域外擺放有大量金屬設(shè)備，具體圖6定位環(huán)境所示：

圖6 定位環(huán)境

下面說明采集數(shù)據(jù)和使用數(shù)據(jù)：

將Tag放置在某一已知位置，按照超寬帶定位系統(tǒng)串口通訊協(xié)議進(jìn)行數(shù)據(jù)采集，每次讀取i個(gè)坐標(biāo)，構(gòu)成集合Mi(i=1,2,…)。

將取得的坐標(biāo)集合采用改進(jìn)K均值聚類算法處理，將返回值作為已知位置可靠的訓(xùn)練樣本點(diǎn)

在同一已知位置，重復(fù)步驟2）k次，取得可靠的樣本訓(xùn)練點(diǎn)集合，k的取值根據(jù)BP神經(jīng)網(wǎng)絡(luò)訓(xùn)練效果決定。

重復(fù)步驟1）～3），取得個(gè)已知位置坐標(biāo)及其可靠估計(jì)坐標(biāo)構(gòu)成訓(xùn)練樣本集合，使用該訓(xùn)練樣本集合訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)，從而獲得BP神經(jīng)網(wǎng)絡(luò)定位模型。

最后在定位階段，將Tag放在某一待定位識別位置，按照步驟1）和步驟2）的做法，獲得待定位識別位置的估計(jì)坐標(biāo)Sx，將其輸入到訓(xùn)練好的BP神經(jīng)網(wǎng)絡(luò)定位模型進(jìn)行擬合定位，從而得到Tag所處位置坐標(biāo)信息。

5.3 定位精確度驗(yàn)證

在定位區(qū)域內(nèi)，每隔1m取一個(gè)已知位置，共35個(gè)位置，分別進(jìn)行數(shù)據(jù)采樣100次，每5個(gè)數(shù)據(jù)進(jìn)行一次改進(jìn)K均值聚類，每個(gè)位置得20個(gè)經(jīng)過過濾優(yōu)化的數(shù)據(jù)。對于BP神經(jīng)網(wǎng)絡(luò)，使用每個(gè)位置中的10個(gè)數(shù)據(jù)進(jìn)行訓(xùn)練，最終建立層數(shù)為3、隱藏層神經(jīng)元數(shù)為14的BP神經(jīng)網(wǎng)絡(luò)。建立定位識別模型后采用另外10個(gè)數(shù)據(jù)進(jìn)行驗(yàn)證，得到的定位結(jié)果如圖7僅聚類與有神經(jīng)網(wǎng)絡(luò)的RMSE比較與表1僅聚類與有神經(jīng)網(wǎng)絡(luò)定位數(shù)據(jù)比較所示。

圖7 僅聚類與有神經(jīng)網(wǎng)絡(luò)的RMSE比較

表1 僅聚類與有神經(jīng)網(wǎng)絡(luò)定位數(shù)據(jù)比較

數(shù)據(jù)分析

上表與圖可知，采用改進(jìn)K均值BP神經(jīng)網(wǎng)絡(luò)方法的最大偏差、最小偏差、平均RMSE、平均偏差均有大幅度降低，平均RMSE降低了45%，定位精度相比僅聚類算法有大幅度改善。

6 結(jié)語

在超寬帶定位系統(tǒng)的基礎(chǔ)上，本文提出改進(jìn)K均值聚類BP神經(jīng)網(wǎng)絡(luò)超寬帶室內(nèi)定位方法。從改進(jìn)K均值聚類、BP神經(jīng)網(wǎng)絡(luò)模型構(gòu)建兩個(gè)方面入手，通過實(shí)驗(yàn)驗(yàn)證該方法在減小超寬帶定位系統(tǒng)定位數(shù)據(jù)穩(wěn)定性差、精度低等方面有明顯效果，并且定位精度理想，具有良好的應(yīng)用價(jià)值。

[1]石曉偉.基于BP神經(jīng)網(wǎng)絡(luò)和改進(jìn)質(zhì)心算法的室內(nèi)無線定位技術(shù)的研究.北京工業(yè)大學(xué)，2012：11-13.

[2]肖竹等.超寬帶定位研究與應(yīng)用:回顧和展望.電子學(xué)報(bào)，2011（01）:1.

[3]馮曉莉.超寬帶通信系統(tǒng)定位技術(shù)研究.南京理工大學(xué)，2009：35.

[4]趙慶.基于Hadoop平臺下的Canopy-Kmeans高效算法.電子科技，2014（02）.

[5]王千等.K-means聚類算法研究綜述.電子設(shè)計(jì)工程，2012（07）.

[6]劉彩紅.BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法的研究.重慶師范大學(xué)，2008.

Improved K-means Clustering BP Neural Network UWB Indoor Location Method

LIAN Zong-kai，YUAN Fei，QI Wei

（School of Automation，Guangdong Polytechnic Normal University，Guangzhou 51000）

Indoor positioning technology with the production and living on the indoor positioning of the demand has become one of the hot issues,ul?tra-wideband positioning technology with its unique advantages and rapid development,for ultra-wideband positioning system positioning data is poor stability,low accuracy,proposes the improved K-means clustering BP neural network UWB indoor location method.This meth?od improves the original data in the UWB positioning system and preprocesses the K-means clustering algorithm to filter the data with large deviation of the position.And then carries on the BP neural network modeling based on the real coordinates and the clustering filter coordinates in the multi-point in the measurement area.Positioning process is filtered after the positioning of the coordinates of the input BP neural network positioning model,identification and positioning.Through the experimental determination,the indoor positioning meth?od accuracy of up to 26cm,and good stability.

1007-1423（2017）21-0016-05

10.3969/j.issn.1007-1423.2017.21.003

連宗凱（1996-），男，廣東汕頭人，在讀本科，專業(yè)方向?yàn)?015級電氣工程及其自動(dòng)化；袁飛(1984-)，男，湖南常德人，博士研究生，研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)、數(shù)據(jù)融合；祁偉（1964-），女，山東陵縣人，本科，研究方向?yàn)闄z測技術(shù)與自動(dòng)化裝置、智能機(jī)器人；；

2017-05-04

2017-07-16

超寬帶；室內(nèi)定位；聚類算法；BP神經(jīng)網(wǎng)絡(luò)

Ultra-Wide Band;Indoor Location;Clustering Algorithm;BP Neural Network