基于改進加權KNN算法的室內無線電發(fā)射源定位研究

杜太行 孟巖 孫曙光 江春冬 田朋

摘要：針對室內無線電發(fā)射源的位置指紋定位問題，提出一種改進加權KNN定位算法。在分析現有定位算法的基礎上，建立測試點和參考點的余弦相似度關系，并把該余弦相似度用作KNN在線定位計算的權重，計算出第一次加權質心定位結果，根據此結果判斷是否進行二次加權來確定測試點最終的估計位置，最后進行算法的仿真測試。結果表明，較之傳統(tǒng)位置指紋算法該算法定位準確度提高17%左右，不僅克服傳統(tǒng)算法在發(fā)射源定位中由于在線階段針對測試點接收到的信號強度不同造成的定位穩(wěn)定性差的問題，還避免當存在離測試點較遠的參考點時造成的定位誤差大的問題。

關鍵詞：位置指紋定位;KNN算法;余弦相似度;二次加權質心算法;參考點

中圖分類號：TP391;TH823 文獻標志碼：A 文章編號：1674-5124（2019）09-0105-07

收稿日期：2019-01-10;收到修改稿日期：2019-02-28

基金項目：河北省教育廳資助科研項目（ZD2016108）

作者簡介：杜太行（1963-），男，天津市人，教授，博士生導師，主要研究方向為電器檢測、計算機應用。

通信作者：孫曙光（1979-），男，河北河間市人，副教授，博士，主要研究方向為智能檢測、故障診斷。

0 引言

隨著無線電技術的發(fā)展，查找室內無線電信號發(fā)射源非法使用者的位置是無線電管理中的一項重要工作。位置指紋定位算法是當前研究較熱的室內定位算法之一[1]，它一般利用室內無線局域網中的接入點（access point，AP），在參考點處用接收端接收到的指紋信號建立離線數據庫，在線階段利用相應的定位算法確定移動接收端的位置。位置指紋定位技術由于其無需部署其他設備，操作簡單且定位精度高，成為當前室內定位技術中越來越受歡迎的定位技術之一。

以上AP是固定的發(fā)射源，被定位的是接收端[2]。考慮到位置指紋定位技術在定位中的優(yōu)勢，可以將其從定位接收端引入到所研究的定位發(fā)射源的問題上。同時，也會面臨一些問題。問題主要集中在兩方面[3]：一是離線階段指紋信號的采集及其處理，它直接影響指紋數據庫的準確性。文獻[4]探究了離線階段建立的指紋數據庫受采樣間距的影響;文獻[5]提出了增大參考點之間的歐氏距離確定接收端位置的方案;文獻[6]中利用平滑均值濾波方法對采集信號的接收信號強度（received signal strength，RSS）值進行均值平滑處理，提高信號采集的精度。二是在線定位算法的適用性，它會影響整個定位系統(tǒng)的精度。文獻[7]提出了改進的基于區(qū)域劃分的定位算法;文獻[8]提出一種以位置指紋離散度作為權值參考的改進加權K近鄰（weighted K nearestneighbor，WKNN）位置指紋定位算法;文獻[9]提出了改進型 KNN（K nearest neighbor，KNN）算法，旨在提高精度減小計算復雜度。而在發(fā)射源的定位系統(tǒng)中，而由于接收機型號不同或環(huán)境差異造成在在線階段針對測試點接收到的信號強度不同，依靠傳統(tǒng)方法，即通過參考點和測試點之間歐氏距離的大小計算權重會造成一定的誤差。而且在有些情況下，定位算法對參考點的選取會使離測試點較遠的參考點參與定位計算，這樣也會產生較大誤差。

本文從定位算法方面人手，針對發(fā)射源的定位系統(tǒng)中由于在線階段針對測試點接收到的信號強度不同和存在離測試點較遠的參考點的問題，提出了一種改進加權KNN算法。將余弦相似度用作加權質心算法的權重，并根據初始定位結果選擇二次加權算法來確定測試點的最終估計位置。最后利用仿真實驗進行了驗證，將所得結果與傳統(tǒng)的KNN算法進行比對。

1 發(fā)射源的位置指紋定位技術

1.1 定位原理

位置指紋定位通常分為兩個階段：離線階段和在線階段。由圖1所示，離線階段的主要工作是建立指紋數據庫。

首先選定一個區(qū)域，如圖2所示，根據空間大小及實際現場環(huán)境選擇采集節(jié)點AP的個數，并固定采集節(jié)點的位置。從區(qū)域中選取多個參考點，然后把這些參考點的強度信息和位置信息一并存入離線指紋數據庫中。在線階段即指紋匹配階段，用某種定位算法將測試點強度信息與指紋數據庫中的指紋進行匹配，得到測試點的位置坐標，從而實現定位。

離線階段建立的數據庫中的指紋信號強度表示如下：

[YSSl7 rssi，…rssi”1

RSSi=（YSSi]，YSSi2，" " " ，YSSin）表示任意一個參考點的指紋信息，YSSin表示第n個采集節(jié)點接收到的第i個參考點的信號強度值。

要準確地確定測試點的位置信息，除了要在離線階段建立一個高質量的數據庫，在線階段的定位算法也同樣重要。常用的位置指紋算法有最近鄰（nearest neighbor，NN）法、K近鄰法和基于歐氏距離的加權K近鄰法。

1.2 位置指紋定位算法

1）最近鄰法

最近鄰法是位置指紋定位最基本的匹配算法，它通過接收機接收到的發(fā)射源的信號強度與指紋數據庫中保存的信號強度進行比較，找出歐幾里德距離最小的參考點，其坐標即為測試點的定位結果。

測試點與參考點i的關于信號強度的歐氏距離矢量表示為：其中RSS=（rss₁，rss₂，…，rss_n）為采集節(jié)點對測試點測得的信號強度特征值。

2）K近鄰法

K近鄰是在最近鄰法基礎上做出的改進。對式（2）取最近的K個距離，（xk，Yk）為第k組參考點的坐標信息，將這K個距離所對應的參考點的坐標的平均值作為測試點的定位結果。如式（3）所示：

3）基于歐氏距離的加權K近鄰法

加權K近鄰法是基于K近鄰法的改進。K近鄰法取的是K個最小歐氏距離所對應的參考點的坐標的平均值。但根據信號傳播模型，距離越小，信號強度值越大，對定位結果的影響程度就越大，因此對這K個最小歐氏距離所對應的坐標采用權值分配，距離越小，權值就越大。如式（4）所示：其中w_k=1/L_k為第k個參考點的權重，為相應歐氏距離的倒數。

2 基于余弦相似度的二次加權KNN定位算法

2.1 基于余弦相似度的權重分配

如上所述歐氏距離表示空間中兩點的真實距離，作為一種最基本的相似性度量方法，由于算法簡單，成為KNN算法的核心。在室內定位技術中，參考點的RSS值越接近于測試點的Rss值，得到的歐氏距離就越小。而在實際中由于接收機型號不同或環(huán)境差異造成在線階段針對測試點接收到的信號強度不同。如圖3所示，以3個接收機為例，即信號強度特征向量為3維，圖3中尸是數據庫中的參考點，RSS_P表示P的信號強度的特征向量，即為圖3中的OP矢量。S₁、S₂是測試點，RSS_S是測試點的信號強度特征向量，即為OS矢量，OS₁與OS₂正是反映由于接收機型號不同或環(huán)境差異導致信號強度不同問題所造成的向量大小的變化刀巧{和PS₂表示接收機在同一測試點位置接收到的信號強度得出的參考點與測試點之間的歐氏距離，在這種情況下采用歐氏距離進行參考點權重計算，會造成針對同一測試點的參考點權重計算不同，進而造成較大的定位誤差。

而余弦相似度[10]是通過兩個向量的夾角余弦值來評估它們的相似度。相比于歐氏距離表示空間中兩點之間的實際直線距離，余弦相似度更多的關注于兩個向量之間方向上的關系。因此可基于此對加權KNN算法進行改進，利用余弦相似度代替歐氏距離的倒數作為權重進行定位，即計算參考點對應的強度特征向量與測試點對應的強度特征向量的相似度情況。表示為：其中P，RSS_S>是點P和點S的信號強度特征向量的內積，|RSS_P|·|RSS_S|是信號強度特征向量的長度的乘積。基于上述原理在圖3中盡管OS₁與OS₂向量長度數值上有差異，但其與參考點的余弦相似度cosθ的數值是不變的，也即針對同一測試點的參考點權重計算相同，可消除接收機型號不同或環(huán)境差異造成的在線階段針對測試點接收到的信號強度不同造成的定位誤差問題。既而可以結合KNN原理求出參與定位計算的K個參考點。

2.2 二次加權質心算法的位置估計

在上述基礎上，利用加權質心算法進行位置估計，將最終確定的K個參考點組成一個多邊形，然后計算多邊形的質心作為測試點的估算位置。

當所求得的參考點的分布較為均勻時，采用質心算法可以取得較高的定位精度。但是，有時候K個參考點中常常存在離測試點比較遠的點，采用一次質心算法就會容易受到這些點的干擾，定位結果就會不同程度的偏向這些點，在這種情況下，一次質心算法會產生比較大的定位誤差，如圖4所示，A為離測試點較遠的參考點，I'為一次質心算法的定位結果，而s為測試點的真實位置。

因此，本文采用二次加權質心算法[11]。第一次質心加權算法預估出測試點的初始位置，然后計算初始位置與每個參考點的距離，與提前設置的閾值進行比較，閾值根據實驗環(huán)境和參考點的布局間距綜合考慮選取，若都小于該閾值，則完成定位，直接輸出定位結果;若超出該閾值，則用第一次定位結果來取代離初始位置較遠的參考點，進行二次加權質心計算估算出測試點的準確位置，在圖5中，用I'取代A，再利用B、C、D、E、I'組成的多邊形的質心I作為最終的定位結果。

由此，基于余弦相似度的二次加權KNN定位算法如下：其中，（x_i，y_i）表示第_i組參考點的坐標信息，r_i表示第i個參考點與測試點之間的余弦相似度關系。（x'，y'）為一次加權定位結果，（x"，y"）為二次加權定位結果，S_j為一次加權定位結果與第j個參考點的距離，Thr為設定的閾值，在此第j個參考點為離測試點較遠的參考點。

3 室內定位仿真實驗原理

3.1 信號傳播模型

為了驗證本文所提的改進加權KNN算法的合理性，應用仿真實驗來模擬實際環(huán)境中無線電發(fā)射源的定位，信號傳播模型選用最常用的對數距離衰減模型，模型表示為：

PL（d）=PL（d₀）+10_nnlg（d/d_n）（7）其中，PL（d）是距離發(fā)射源d處的信號傳播損耗，PL（d₀）為近地參考距離的路徑損耗，在室內，近地距離d₀一般取1m，n₀為路徑損耗因數，自由空間中一般取2，在實際環(huán)境中，n₀會有所不同，室內辦公室一般在1.8～2.8[12]。

3.2 仿真實驗步驟

1）離線階段，根據定位區(qū)域選取合適的接收機的個數并部署接收機的位置。然后利用仿真信號傳播模型進行離線階段參考點指紋信號采集，把采集到的強度信息和位置信息一并存入指紋數據庫。

2）在線階段，仿真采集測試點的強度信息，并與指紋數據中的數據進行比對，選用基于余弦相似度的二次加權KNN算法作為定位算法。仿真實驗定位流程如圖6所示。

4 仿真實驗及結果分析

利用Matlab仿真平臺，對本文提出的改進加權KNN算法進行仿真驗證，為了模擬實際環(huán)境中接收機型號不同或環(huán)境差異引起的接收信號強度差異，在線階段中，在每次測試中針對測試點的強度信息仿真采集，在信號傳播模型中加入一隨機值，以模擬接收機接收強度的差異;定位環(huán)境選擇為10m×10m、 20m×20m，使用了4個接收機，并根據經驗部署接收機的位置。參考點的布局間距取1，2，3m分別建立數據庫。定位誤差如下：式中，（x_p，y_p）表示第p個測試點的實際位置坐標，（x_p'，y_p'）表示第P個測試點的估計位置坐標。

為分析余弦相似度作為權重在解決由于接收機型號不同或環(huán)境差異造成在線階段針對測試點接收到的信號強度不同而帶來的定位誤差問題，下面分別在10m×10m和20m×20m的環(huán)境下進行仿真驗證，并用基于余弦相似度的KNN算法與KNN算法和基于歐氏距離的WKNN算法進行結果對比。

4.1 10m×10m定位實驗分析

10m×10m的環(huán)境下，在不同的K值下，參考點的布局間距分別取1m、2m進行實驗。K=3，布局間距為2m時基于余弦相似度的KNN算法與傳統(tǒng)的KNN和WKNN算法在各個測試點的定位誤差如圖7所示。相比于其他兩種算法，基于余弦相似度的KNN算法的定位誤差波動較小，且最大定位誤差均小于其他兩種算法。

將圖7中25個測試點的定位誤差進行統(tǒng)計得到圖8中的累計誤差概率分布，由統(tǒng)計結果可知，基于余弦相似度的KNN算法的小誤差累計概率更高。

為了考察不同K值時的定位效果，表1為上述環(huán)境下，參考點的布局間距為1m，K值取3～7時，基于余弦相似度的KNN算法與其他兩種傳統(tǒng)算法平均定位誤差的對比，可見基于余弦相似度的KNN算法的定位平均誤差均小于其他兩種算法。

4.2 20m×20m定位實驗分析

20m×20m的環(huán)境下，在尺二3時，參考點的布局間距分別取1m、2m、3m進行實驗，3種算法的平均定位誤差如表2所示，結合實驗結果，同時為了降低計算復雜度，在此布局間距選取為3m。

K=3時3種定位算法在各個測試點的定位誤差如圖9所示。圖10為36個測試點的累計誤差概率統(tǒng)計結果。3種算法在K值取3～7時的平均定位誤差比較如表3所示。

綜上，由圖7～圖10和表1～表3所得結果均能說明本文的基于余弦相似的KNN算法提高了定位精度，克服了定位中由于接收機型號不同或環(huán)境差異造成在在線階段針對測試點接收到的信號強度不同引起的定位穩(wěn)定性差的問題。

4.3 一次加權與二次加權質心算法的誤差對比分析

為了分析二次加權在存在離測試點較遠的參考點時的修正作用，在20m×20m的環(huán)境下，參考點的布局間距為3m，K=3時一次加權與二次加權算法在各個測試點的定位誤差如圖11所示，均采用基于余弦相似度的權重分配。由結果可知，由于離測試點較遠的參考點參與在線定位計算造成了某些測試點誤差較大，在經過二次加權計算之后誤差有所降低。

表4為上述環(huán)境下，K值取3～7時，一次加權與二次加權算法的平均定位誤差對比結果，二次加權算法的平均定位誤差均小于一次加權結果。尺畢3的條件下，進一步與表3中KNN算法和WKNN算方法進行對比，得出本文算法的平均定位誤差由約2m減小到了1.65m，平均定位精度提高了17%左右。

綜合以上3種實驗分析，本文基于余弦相似度的KNN算法相比傳統(tǒng)的KNN和WKNN算法，解決了接收信號強度的差異造成的定位穩(wěn)定性差的問題，提高了定位精度。在此基礎上采用二次加權質心算法，修正了較遠參考J點帶來的定位誤差大的問題。

5 結束語

本文提出一種基于余弦相似度的二次加權KNN定位算法，用于對發(fā)射源的定位。以余弦相似度作為KNN在線定位計算的權重;并根據情況進行二次加權以準確估計測試點的位置。仿真結果驗證了該算法的合理性，相比傳統(tǒng)的KNN和WKNN算法定位精度提高了17%左右，采用基于余弦相似度的權重分配，解決了由于接收機型號不同或環(huán)境差異造成在線階段針對測試點接收到的信號強度不同引起的定位穩(wěn)定性差的問題;二次加權改善了由于較遠參考點造成的定位誤差大的問題。將本文算法應用到復雜的實際環(huán)境中，優(yōu)化接收機的部署位置，是后續(xù)需要研究的內容。

參考文獻

[1]李昊.位置指紋定位技術[J].山西電子技術，2007（5）：84-87.

[2]謝代軍.無線局域網室內定位技術研究[D].鄭州：解放軍信息工程大學，2013.

[3]秦泗明.基于位置指紋的WiFi室內定位技術研究[D].成都：電子科技大學，2013.

[4]羅宇鋒，劉艷輝，李曉春.WiFi指紋定位中采樣間距對定位精度的影響[J].全球定位系統(tǒng)，2018，43（3）：77-81，94.

[5]杜太行，李娟妹，江春冬，等.平臺側位置指紋定位系統(tǒng)中接收端問題的優(yōu)化[J].電訊技術，2017，57（8）：950-956.

[6]汪倫杰，廖興宇，潘偉杰，等.基于信號均值濾波+k-means+WKNN的Wifi指紋定位算法研究[J].微電子學與計算機，2017，34（3）：30-34.

[7]蔡朝暉，夏溪，胡波，等.室內信號強度指紋定位算法改進[J].計算機科學，2014，41（11）：178-181.

[8]田洪亮，錢志鴻，梁瀟，等.離散度WKNN位置指紋Wi-Fi定位算法[J].哈爾濱工業(yè)大學學報，2017（5）：94-99.

[9]李昂，肖甫，李雷.基于改進型KNN算法和Android平臺的室內定位技術研究[J].物聯網技術， 2018，8（3）：21-25.

[10]趙聰.基于位置指紋的WLAN室內定位算法研究[D].哈爾濱：哈爾濱工業(yè)大學，2014.

[11]王緩緩，邱建文.基于區(qū)域分割的二次質心定位算法[J].計算機應用與軟件，2015（4）：279-282.

[12]李紅麗.基于WiFi的室內定位技術的研究[D].北京：北京交通大學，2014.

（編輯：劉楊）