基于PSO—KNN的WiFi—RSSI指紋算法的四旋翼室內定位

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

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

關鍵詞：室內定位；K最近鄰算法；粒子群算法；四旋翼飛行器

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

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

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

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

2 改進WiFi-RSSI指紋算法描述

2.1離線數據采集建庫

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

2.2在線定位

上位機通過PSO-KNN算法與指紋數據庫中的數據信息進行匹配計算。首先初始化粒子群，將式（1）作為目標函數進行優化。式中，Di表示定位時獲取的指紋矢量與數據庫中第i個指紋矢量的歐氏距離，Wi表示其權重。

然后計算每個粒子的適應值，式（2）和式（3）更新粒子速度和位置，求出每個粒子的個體最優，進而求出整個群體的全局最優值，從而匹配出最相似的數據信息用于定位結果計算。

式中，c1、，c2為加速常數；r1，r2為區間[0，1]內的隨機數：Xi（xil，xi2，…，xid），Vi（vi1，vi2，…，vid）表示粒子i當前的位置與速度：Pi（pi1，pi2，…pid）表示粒子當前的最優位置；Pg（pg1，pg2，…，pgd）表示整個粒子群的全局最優位置；k為迭代次數。

3 仿真實驗

定位區域為15m×20 m的方形區域，AP和參考點部署如圖2所示。圖中圓點處為參考點，五角星處為布置的AP，邊界上菱形為所標記的四旋翼，圓柱為目標點。每個參考點采樣5次后取均值，構建離線指紋數據庫，目標點在定位區域內隨機生成。參數取值如下：

距離最小的指紋矢量個數K=4，初始種群個數N=50，迭代次數ger=100，慣性權重w=0.8，自我學習因子c1=1.494 45，群體學習因子c2=1.494 45。

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

從圖3和表1可以分析出，相對于NN算法、KNN算法，利用粒子群對權重進行優化PSO-KNN算法精度更優且誤差波動較小。部分參考節點誤差較大是由于此部分節點所在區域信號強度指紋區分度不明顯。

4 結語

本文在原有WiFi-RSSI指紋算法的基礎上，提出一種基于PSO算法對K最近鄰算法的權重進行優化的改進WiFi-RSSI指紋算法。仿真結果表明，該方法可快速有效地搜索出全局最優的權重值，去除因信號不穩定引起的干擾項，有較好的分類精度，并獲得較高的室內定位精度。

[參考文獻]

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

[2]陳小龍，唐強，車軍，等基于人工視覺的四旋翼飛行器室內定位與控制[J].兵工自動化，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]畢京學，甄杰，汪云甲，等高斯函數定權的改進KNN室內定位方法[J]測繪通報，2017 （6）：9-12，35.

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

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

[8]李瑛，基于BP神經網絡的室內定位技術研究[D]長沙：中南大學，2007.

[9]周錦，李煒，金亮，等基于KNN-SVM算-法的室內定位系統設計[J].華中科技大學學報（自然科學版），2015 （Sl）：517-520.