基于PSO—KNN的WiFi—RSSI指紋算法的四旋翼室內(nèi)定位

孫瑤 王磊 王延召 周云天 陶少俊

摘要：針對室內(nèi)無GPS下的四旋翼定位問題，文章提出一種基于PSO-KNN的WiFi-RSSI指紋算法。運(yùn)用粒子群算法對1；最近鄰算法的權(quán)重進(jìn)行優(yōu)化，去除信號不穩(wěn)定產(chǎn)生的干擾項(xiàng)，快速選擇全局最優(yōu)權(quán)值，實(shí)現(xiàn)室內(nèi)四旋翼的較高精度定位。與傳統(tǒng)的NN和KNN比較分析表明，文章所設(shè)計(jì)基于PSO-KNN的WiFi-RSSI指紋算法可搜索到全局最優(yōu)的權(quán)值，有效提高分類的精度，降低定位誤差。

關(guān)鍵詞：室內(nèi)定位；K最近鄰算法；粒子群算法；四旋翼飛行器

近年來，得益于非線性控制理論的發(fā)展和微電子技術(shù)的進(jìn)步，使得精確控制如四旋翼無人機(jī)這樣的非線性、欠驅(qū)動(dòng)系統(tǒng)成為可能，其所具備的在三維空間運(yùn)動(dòng)的能力帶來了新的研究挑戰(zhàn)。四旋翼在軍民領(lǐng)域表現(xiàn)出極強(qiáng)的應(yīng)用潛力。例如戰(zhàn)場上對未知環(huán)境的偵察以及輔助打擊，電力線路的自主巡檢，偏遠(yuǎn)地區(qū)的快遞投送等。但在室內(nèi)飛行時(shí)，衛(wèi)星信號無法穿透墻體，傳統(tǒng)的GPS定位方案難以滿足四旋翼的自主飛行要求，從而制約了其在室內(nèi)的應(yīng)用范圍。

WiFi，ZigBee。Bluetooth和UWB等無線通信技術(shù)被用于實(shí)現(xiàn)室內(nèi)定位，成為工業(yè)界和學(xué)術(shù)界的研究熱點(diǎn)[1]。室內(nèi)定位也是小型無人機(jī)在室內(nèi)應(yīng)用的關(guān)鍵技術(shù)之一[2]。根據(jù)定位方法的數(shù)學(xué)原理，常用的方法有基于信號到達(dá)的角度（Angle of Arrival，AOA）、基于信號到達(dá)時(shí)間（Time ofArrival，TOA）、基于信號到達(dá)時(shí)間差（Time Different ofArrival，TDOA）、位置指紋法。三角定位法設(shè)備復(fù)雜且價(jià)格昂貴，容易因信號不穩(wěn)定而導(dǎo)致位置定位不精確。TOA的定位方式因?yàn)槎鄰叫?yīng)和時(shí)鐘分辨率低，定位效果較差。而基于接收的信號強(qiáng)度指示（ Received Signal StrengthIndication，RSSI）指紋定位法是目前主流的WiFi定位方法[3]，不需要將信號強(qiáng)度RSSI置換成距離，對環(huán)境復(fù)雜的室內(nèi)空間定位時(shí)精度較高。它通過與指紋數(shù)據(jù)庫中事先存儲的不同位置信號特征參數(shù)進(jìn)行對比，估算所在位置，定位精度取決于校準(zhǔn)點(diǎn)的密度。目前廣泛使用的匹配算法有近鄰算法[4]、K最近鄰算法[5]、加權(quán)近鄰算法[6]、貝葉斯概率算法[7]、神經(jīng)網(wǎng)絡(luò)算法[8]、SVM算法[9]）等。但以上算法存在計(jì)算量大、難以保證實(shí)時(shí)性、精度不高、對輸入數(shù)據(jù)的表達(dá)形式敏感等缺點(diǎn)。本文利用粒子群算法結(jié)構(gòu)簡單、收斂速度快、搜索能力強(qiáng)、易于工程實(shí)現(xiàn)的特點(diǎn)，提出一種基于PSO-KNN的WiFi-RSSI指紋算法。

在定位過程中，四旋翼無人機(jī)停在指定位置，通過機(jī)載無線定位芯片測定其周邊的無線信號特征參數(shù)，發(fā)回上位機(jī)。上位機(jī)通過離線指紋數(shù)據(jù)庫進(jìn)行匹配計(jì)算，將計(jì)算出的四旋翼與目標(biāo)點(diǎn)的位置信息發(fā)送給四旋翼。機(jī)載微控制器接收到控制指令后，控制四旋翼飛向目標(biāo)點(diǎn)。1WiFi-RSSI指紋算法概述

WiFi-RSSI指紋算法主要思想是利用來自于無線局域網(wǎng)中路由器產(chǎn)生的RSSI在室內(nèi)分布的差異性，為每一個(gè)地點(diǎn)產(chǎn)生一個(gè)RSSI指紋并錄入離線指紋庫。在線定位時(shí)，將當(dāng)前的信號特征與RSSI指紋庫匹配，確定目標(biāo)位置。如圖1所示，整個(gè)過程分為離線數(shù)據(jù)采集建庫和在線定位兩個(gè)階段。

2 改進(jìn)WiFi-RSSI指紋算法描述

2.1離線數(shù)據(jù)采集建庫

離線數(shù)據(jù)采集建庫是指針對待定位區(qū)域建立指紋數(shù)據(jù)庫。首先在室內(nèi)待定位區(qū)域內(nèi)布置6個(gè)無線訪問接入點(diǎn)（Access Point，AP），按照間距1 m劃分該區(qū)域并標(biāo)記參考點(diǎn)位置，然后使用設(shè)備遍歷所有參考點(diǎn)，并記錄下每個(gè)參考點(diǎn)接收的AP的信號強(qiáng)度、媒體訪問控制（MediaAccess Control，MAC）地址、參考點(diǎn)的物理位置等信息，存入指紋數(shù)據(jù)庫，每個(gè)指紋唯一對應(yīng)一個(gè)地址。數(shù)據(jù)采集過程中，我們對采樣數(shù)據(jù)取均值，以提高離線指紋數(shù)據(jù)庫的精確度。

2.2在線定位

上位機(jī)通過PSO-KNN算法與指紋數(shù)據(jù)庫中的數(shù)據(jù)信息進(jìn)行匹配計(jì)算。首先初始化粒子群，將式（1）作為目標(biāo)函數(shù)進(jìn)行優(yōu)化。式中，Di表示定位時(shí)獲取的指紋矢量與數(shù)據(jù)庫中第i個(gè)指紋矢量的歐氏距離，Wi表示其權(quán)重。

然后計(jì)算每個(gè)粒子的適應(yīng)值，式（2）和式（3）更新粒子速度和位置，求出每個(gè)粒子的個(gè)體最優(yōu)，進(jìn)而求出整個(gè)群體的全局最優(yōu)值，從而匹配出最相似的數(shù)據(jù)信息用于定位結(jié)果計(jì)算。

式中，c1、，c2為加速常數(shù)；r1，r2為區(qū)間[0，1]內(nèi)的隨機(jī)數(shù)：Xi（xil，xi2，…，xid），Vi（vi1，vi2，…，vid）表示粒子i當(dāng)前的位置與速度：Pi（pi1，pi2，…pid）表示粒子當(dāng)前的最優(yōu)位置；Pg（pg1，pg2，…，pgd）表示整個(gè)粒子群的全局最優(yōu)位置；k為迭代次數(shù)。

3 仿真實(shí)驗(yàn)

定位區(qū)域?yàn)?5m×20 m的方形區(qū)域，AP和參考點(diǎn)部署如圖2所示。圖中圓點(diǎn)處為參考點(diǎn)，五角星處為布置的AP，邊界上菱形為所標(biāo)記的四旋翼，圓柱為目標(biāo)點(diǎn)。每個(gè)參考點(diǎn)采樣5次后取均值，構(gòu)建離線指紋數(shù)據(jù)庫，目標(biāo)點(diǎn)在定位區(qū)域內(nèi)隨機(jī)生成。參數(shù)取值如下：

距離最小的指紋矢量個(gè)數(shù)K=4，初始種群個(gè)數(shù)N=50，迭代次數(shù)ger=100，慣性權(quán)重w=0.8，自我學(xué)習(xí)因子c1=1.494 45，群體學(xué)習(xí)因子c2=1.494 45。

NN算法[4]、KNN算法[5]、PSO-KNN算法的平均誤差曲線如圖3所示。3種算法定位誤差對比分析如表1所示。

從圖3和表1可以分析出，相對于NN算法、KNN算法，利用粒子群對權(quán)重進(jìn)行優(yōu)化PSO-KNN算法精度更優(yōu)且誤差波動(dòng)較小。部分參考節(jié)點(diǎn)誤差較大是由于此部分節(jié)點(diǎn)所在區(qū)域信號強(qiáng)度指紋區(qū)分度不明顯。

4 結(jié)語

本文在原有WiFi-RSSI指紋算法的基礎(chǔ)上，提出一種基于PSO算法對K最近鄰算法的權(quán)重進(jìn)行優(yōu)化的改進(jìn)WiFi-RSSI指紋算法。仿真結(jié)果表明，該方法可快速有效地搜索出全局最優(yōu)的權(quán)重值，去除因信號不穩(wěn)定引起的干擾項(xiàng)，有較好的分類精度，并獲得較高的室內(nèi)定位精度。

[參考文獻(xiàn)]

[1]高業(yè)，何敏，室內(nèi)定位技術(shù)研究綜述[A.江蘇省測繪地理信息學(xué)會(huì)、江蘇省測繪工程院.2017年度江蘇省測繪地理信息學(xué)會(huì)GPS、大地專業(yè)委員會(huì)學(xué)術(shù)年會(huì)暨JSCORS技術(shù)交流大會(huì)論文集[C].南京：江蘇省測繪地理信息學(xué)會(huì)、江蘇省測繪工程院，2017：5.

[2]陳小龍，唐強(qiáng)，車軍，等基于人工視覺的四旋翼飛行器室內(nèi)定位與控制[J].兵工自動(dòng)化，2012（5）：61-64.

[3]YUAN Y， PEI L， XU C， et al.Efficient WiFi fingerprint traimng using semi-supervised learning[C].Corpus Christ： Ubiquitous Positioning Indoor Navigation and Location Based Service （UPINLBS）， 2014： 148-155.

[4]CAMPOS R s，LOVISOLO L， DECAMPOS M L R.Wi-Fi multi-floor indoor positioning considering architectural aspects and controlled computational complexity[J].Expert Systems with Applications， 2014 （14）： 6211-6223.

[5]畢京學(xué)，甄杰，汪云甲，等高斯函數(shù)定權(quán)的改進(jìn)KNN室內(nèi)定位方法[J]測繪通報(bào)，2017 （6）：9-12，35.

[6]孫新，歐陽童，嚴(yán)西敏，等基于訓(xùn)練集裁剪的加權(quán)K近鄰文本分類算法[J].情報(bào)工程，2016 （6）：8-16.

[7]彭玉旭，楊艷紅，一種基于RSSI的貝葉斯室內(nèi)定位算法[J].計(jì)算機(jī)工程，2012 （10）：237-240.

[8]李瑛，基于BP神經(jīng)網(wǎng)絡(luò)的室內(nèi)定位技術(shù)研究[D]長沙：中南大學(xué)，2007.

[9]周錦，李煒，金亮，等基于KNN-SVM算-法的室內(nèi)定位系統(tǒng)設(shè)計(jì)[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2015 （Sl）：517-520.