與強度無關的位置指紋在線定位改進算法*

江春冬，惠 慧，陳云飛，杜太行，2(.河北工業(yè)大學控制科學與工程學院,天津30030;2.河北省控制工程研究中心,天津30030)

?

與強度無關的位置指紋在線定位改進算法*

江春冬**1，2，惠 慧1，陳云飛1，杜太行1，2
(1.河北工業(yè)大學控制科學與工程學院,天津300130;2.河北省控制工程研究中心,天津300130)

Foundation Item:The MIIT Topic(12-MC-KY-14)

**通信作者:chundong_j@163. com Corresponding author:chundong_j@163. com

摘 要:將現(xiàn)有的研究較熱的固定發(fā)射端、定位接收端的室內位置指紋定位系統(tǒng)應用到固定接收端、定位發(fā)射端的室內無線電干擾源定位中,研究了一種考慮干擾源發(fā)射強度的在線定位算法,以克服直接使用以一固定發(fā)射強度信號源建立的指紋數(shù)據(jù)庫和現(xiàn)有的在線定位方法無法實現(xiàn)對不同發(fā)射強度干擾源定位問題。在分析信號傳播模型和現(xiàn)有在線定位方法的基礎上,利用強度差的均方差進行定位計算。給出了算法實現(xiàn)依據(jù)和流程,對改進的算法進行了仿真和實驗驗證,結果證明了改進算法的實用性。同時,改進算法的思想對現(xiàn)有的考慮接收端異質的位置指紋定位系統(tǒng)也有一定的指導意義。

關鍵詞:位置指紋定位；干擾源強度；在線定位方法

1 引 言

位置指紋定位算法是當前研究較熱的室內無線電定位方法,它一般利用特定場所現(xiàn)有的無線局域網(wǎng)(Wireless Local Area Network,WLAN)中的固定接入點(Access Point,AP),建立以場強(Radio Signal Strength,RSS)為參考點(Reference Point,RP)處的特征參數(shù)的指紋數(shù)據(jù)庫,再用相應的定位算法對移動終端進行定位。系統(tǒng)中固定接入點是發(fā)射端,被定位的移動終端是接收端[1-2]。位置指紋定位算法概念清晰,定位精度受定位環(huán)境、特征參數(shù)測量、參考點稀疏程度、在線定位時的定位算法等因素的影響有所不同,但都有初步的研究結果且定位結果基本上能達到要求[3]。

考慮到位置指紋定位算法的優(yōu)點,期望將其用于固定接收端、定位發(fā)射端的室內無線電干擾源的定位查找上。兩者看似僅僅將接收裝置和發(fā)射裝置的位置進行了調換,但實際上會引起較多的問題。問題之一就是被定位的干擾源發(fā)射信號的強度不同,使用以某一固定發(fā)射強度的信號源建立的指紋數(shù)據(jù)庫和常用的在線定位方法在線定位時,定位結果是不可靠的?，F(xiàn)有文獻中的位置指紋定位系統(tǒng)由于固定的是發(fā)射端,其發(fā)射功率是不變的,接收端使用的手機、PAD等設備接收差異不大,所以考慮建庫時的信號強度和定位時的信號強度的情況較少。文獻[1,4-5]提出了接收端異質情況下的位置指紋定位系統(tǒng),給出了場強差作為指紋特征建立指紋數(shù)據(jù)庫的定位方法,改變的是指紋數(shù)據(jù)庫的特征量。這種方法對固定點AP個數(shù)較多的情況下比較有效,而在無線電干擾源位置指紋定位系統(tǒng)中,由于固定的接收端需要額外配置,價格不菲,安裝的個數(shù)有限,使用場強差建立數(shù)據(jù)庫會減少數(shù)據(jù)庫中矢量的個數(shù)而影響定位結果。

鑒于此,本文研究了無線電干擾源位置指紋定位系統(tǒng)中不改變指紋庫特征量時的在線定位方法,在原有近鄰法(Nearest Neighbor,NN)、K近鄰法(K Nearest Neighbor KNN)和加權K近鄰法(Weighted K Nearest Neighbor,WKNN)的基礎上,提出了改進的定位方法,討論了方法的思想和可行性,并用實驗進行了驗證,所得的結果證明了方法的可靠性,同時也可為類似問題提供一定的參考。

2 改進算法理論依據(jù)

改進算法是在信號傳播模型及位置指紋定位算法中常用的在線定位方法的基礎上想到并加以改進的。

2. 1 信號傳播模型

在自由空間中,無線信號的場強傳播模型可表示為

式中:PR、PT分別為接收信號和發(fā)射信號的功率; GR、GT分別為信號接收增益和發(fā)射增益;λ為信號的波長;d為發(fā)射端到接收端的距離[1,6]。

信號功率與以dB為單位的場強表達關系為

在復雜室內空間中,由于環(huán)境對無線電信號的傳播影響很大,往往通過計算路徑損耗再計算接收端接收到的場強值,即

式中:各量的單位均為dB或dBm; RSS [ PR]、RSS[PT]分別為接收信號和發(fā)射信號的強度;PL為路徑損耗;Xσ高斯噪聲,為正態(tài)分布的隨機數(shù)。

室內環(huán)境中路徑損耗的計算模型主要使用對數(shù)距離損耗模型,其表達式為

式中,PL( d0)表示自由空間中d0處接收信號的路徑損耗;d0為參考距離,通常取1 m;d為接收端到發(fā)射端的距離,單位為m;n為傳播損耗系數(shù),它與傳播環(huán)境密切相關,不同環(huán)境下,該值取不同值,針對具體環(huán)境,該值可由測量的值整定,自由環(huán)境中,該值取2[7-8]。

2. 2 位置指紋定位系統(tǒng)常用在線定位方法

以場強為特征量建立的指紋數(shù)據(jù)庫在線階段常用的匹配算法有最近鄰法、K近鄰法和加權K近鄰法[9-11]。

(1)最近鄰算法(NN)

當測試點測得的場強信息為x=(x1,x2,x3,…, xm)時,針對每一個參考點,由公式(5)求取測試點和參考點關于場強的矢量歐幾里德距離:

取最小距離所對應的參考點的坐標作為定位結果的輸出坐標。

(2)K近鄰算法(KNN)

K近鄰法是在最近鄰法的改進。它在利用式(5)求取距離后,不是取最小的一個距離,而是依次取從小到大的K個最小距離,對這K個距離所對應的坐標,求其平均值作為輸出,具體K取多大的值,文獻[2,5]中都進行了研究,綜合考慮運算復雜度和定位準確度情況,K值取3或4較好。

(3)加權K近鄰法(WKNN)

加權K近鄰法又是對K近鄰法的一種改進。K近鄰法選取的K個最小距離對最后的定位結果貢獻相同,取的是平均值,但距離越小應該對定位結果坐標貢獻越大。因此,對所取的K個最小距離進行權值分配,距離越小,權值越大。K個權值wk之和為1。至于wk如何給定,可自行設定,也可由式(6)算出:

3 改進算法的思想與實現(xiàn)

從式(3)信號傳播的模型可以看出,接收的信號強度不僅與環(huán)境有關,還與發(fā)射信號強度、發(fā)射模塊增益、接收模塊增益都有關系。而在對信號源進行位置指紋定位時,接收端的增益可以固定,發(fā)射端的增益和發(fā)射源功率均不確定,也是未知的。當以固定的發(fā)射源獲得參考點的指紋信息后,對范圍內的不同發(fā)射源進行在線定位時,直接采用近鄰法、K近鄰法或者加權K近鄰法進行定位就會出現(xiàn)很大問題。以近鄰法為例,由于接收端接收不同發(fā)射源得到的場強不同,最近距離的未必是真實發(fā)射源的位置。因此,要對在線定位算法進行改進。

前已論及,在固定接收端對發(fā)射源進行定位時直接用場強差作為特征參數(shù)是不合適的,因為接收端數(shù)目有限。因此,我們仍舊選擇針對某一固定發(fā)射端獲得參考點指紋數(shù)據(jù)庫信息,特征量仍舊為接收的場強。

根據(jù)式(3)和式(4)可以得出,式(3)中等號右側的第二項與發(fā)射端的發(fā)射強度無關,只與距離有關。當參考點的坐標固定時,PL項理論上可認為是確定的。而發(fā)射源的強度不僅與發(fā)射源的功率有關,還與發(fā)射模塊和發(fā)射天線相關,這個強度就包含了發(fā)射端的這些因素。

這樣,針對一種發(fā)射源確定的參考點i處,即使x和xi矢量距離最小,但由于兩個發(fā)射源的強度不同,也不能說明x位于xi附近,或者認為xi所在的位置就是x的位置。根據(jù)式(3)和式(4),對于同一位置處強度不同的兩個發(fā)射源,由于同一接收端接收到的場強差由于只包含發(fā)射源強度信息和噪聲,故不同接收端接收到的場強的強度差理論上是相近的,于是對在線定位階段的定位算法進行了改進,將矢量距離的計算公式式(5)改寫為

算法實現(xiàn)由圖1所示的流程圖來表示。

圖1 改進定位算法流程圖Fig. 1 Flowchart of the improved location algorithm

改進算法具體步驟描述如下:

(1)將各固定的接收端檢測到的針對某一測試點處的無線信號場強信息傳送到服務器,形成檢測強度矢量;

(2)用指紋數(shù)據(jù)庫中每一參考點處指紋矢量與檢測的強度矢量作差,形成新的數(shù)據(jù)庫;

(3)對每一個矢量差矢量求取均方差;

(4)對均方差進行排序;

(5)利用改進最近鄰法、K近鄰法或加權K近鄰法對檢測的矢量進行定位。最近鄰法就是均方差最小的那個矢量點所在的位置就是測試點的位置, K近鄰法、加權K近鄰法與前面一樣就不難理解了。

4 改進算法仿真驗證

4. 1 仿真條件

為驗證改進算法合理性,進行了仿真驗證。選擇100 m×100 m正方形區(qū)域為仿真區(qū)域,以橫縱坐標均為5 m的間距將其離散化為二維坐標圖,參考點的個數(shù)為441個;實驗區(qū)域內依次安放8個AP點接收端并編號,其二維坐標為分別(2,2)、(22, 98)、(42,2)、(62,98)、(82,2)、(98,98)、(2,52)、(98,52),同時選擇22個測試點進行了相關的定位測試。數(shù)據(jù)庫的建立在考慮環(huán)境噪聲的情況下,選取發(fā)射信號源強度為10 dB,利用信號傳播模型計算各AP點測量的參考點處的強度信息,并按AP點排好的順序存儲在指紋數(shù)據(jù)庫中。參考點與測試點的位置關系見圖2,圖2中橫軸為定義的X坐標,單位為m;縱軸為定義的Y坐標,單位為m;橫縱坐標范圍代表仿真區(qū)域大小。

圖2 參考點與測試點關系Fig. 2 Relationship between the reference and test points

4. 2 改進前算法針對一個測試點的定位結果

發(fā)射源發(fā)射功率選擇5 dB、10 dB和20 dB,分別對上述3種定位方法進行了實驗,限于篇幅,只給出針對一個測試點(24,27)的3種算法的定位結果和誤差(誤差單位為m),見表1。

表1 測試點(24,27)改進前算法定位結果Tab. 1 Positioning results of the test point(24,27) before the algorithm is improved

從表1中可以看出,由于建立數(shù)據(jù)庫時發(fā)射源強度為10 dB,故針對10 dB的發(fā)射信號定位結果較準,說明了算法的正確性。其他兩種強度的發(fā)射源定位結果誤差過大,定位結果是完全不符合實際要求的。因此,直接應用此算法定位是錯誤的。

4. 3 改進后算法針對相同測試點的定位結果

針對發(fā)射功率分別為5 dB、10 dB和20 dB的發(fā)射源,用改進的定位算法對各測試點進行定位實驗,對前面的測試點(24,27)定位結果和誤差見表2。

表2 測試點(24,27)改進后算法定位結果Table 2 Positioning results of the test point(24,27) after the algorithm is improved

表2數(shù)據(jù)說明,改進后的算法無論對與參考點測試強度相同還是不同的發(fā)射源都能實現(xiàn)較好的定位,定位精度亦可接受。

4. 4 改進后算法針對所有測試點的仿真定位測試

圖3(a)～(c)分別給出了使用改進后的算法對發(fā)射強度分別為5 dB、10 dB和20 dB發(fā)射源使用3種定位算法進行定位的誤差曲線,橫坐標為誤差值,單位為m;縱坐標表示誤差在對應值下的測試點的百分數(shù)。

圖3 強度分別為5 dB、10 dB和20 dB時的誤差曲線Fig. 3 Error curves for 5 dB,10 dB and 20 dB strength

從圖3可以看出,改進的算法仿真時能夠實現(xiàn)對不同發(fā)射源強度的干擾源進行定位,定位誤差絕大多數(shù)在4 m以下的占95%以上,只有個別幾個點的定位誤差大于5 m。從圖3中還可以看到,3種算法的誤差最近鄰法誤差較大,K近鄰法和加權K近鄰法在K取相同值時誤差差別不大。

5 改進算法實驗驗證

5. 1 實驗環(huán)境與實驗條件

為進一步驗證改進算法合理性,在實際環(huán)境中進行了指紋數(shù)據(jù)庫的測試建立并選擇一定的測試點進行了定位計算。以實驗室所在樓層的一部分為定位區(qū)域進行了實驗驗證。實驗區(qū)域大概為20 m× 10 m,包括3間實驗室和對應的走廊。以Z字型安放4個SA44B測量接收機,以約1. 5 m的間距設置54個參考點,并且在區(qū)域內選擇20個測試點進行了定位測試。AP點、參考點、測試點在定位區(qū)域內的示意圖如圖4所示。

圖4 實驗區(qū)域AP點、參考點、測試點位置圖Fig. 4 The location map of AP point,the reference point and the test point in the experimental area

實驗所用的發(fā)射源為頻率和強度均可調的TFG6300信號發(fā)生裝置,指紋數(shù)據(jù)庫建立時發(fā)射源的發(fā)射功率選擇為最大的13 dB。測試點進行測試時分別在不同時間段選擇發(fā)射源的強度為13 dB和7 dB進行了數(shù)據(jù)采集。坐標原點選擇在實驗區(qū)域的左下角,以1. 14 m為間隔將其離散化為二維坐標區(qū)域。

5. 2 改進后算法針對所有測試點的實驗定位測試

圖5(a)和(b)分別給出了使用改進后的算法對發(fā)射強度分別為7 dB和13 dB發(fā)射源使用3種定位算法進行定位的誤差曲線,曲線含義與仿真時相同。

圖5 強度分別為7 dB和13 dB時的誤差曲線Fig. 5 Error curves for 7 dB and 13 dB strength

從圖5中可以看出,針對具體的實驗區(qū)域,算法對不同強度的發(fā)射源仍舊能夠實現(xiàn)定位。定位精度在4 m以內的達到60%,對兩種強度的信號源定位精度基本相同,但定位精度比仿真時差一些。從圖5中還可以看出,最近鄰法定位精度最差,K近鄰法定位精度較好,加權K近鄰法在兩者之間。

5. 3 定位誤差產生原因分析

無論仿真過程還是實驗過程都會產生定位誤差,且實驗時誤差較大,具體誤差產生原因包括:

(1)仿真時在強度測量時只加了固定的隨機噪聲,實際實驗環(huán)境要復雜得多,故實際誤差較大;

(2)特征量檢測時由于干擾的存在,需要進行多次數(shù)據(jù)采集并利用一定的算法進行處理,數(shù)據(jù)個數(shù)和處理方法也會影響到定位精度;

(3)參考點的稀疏對最近鄰法的精度影響較大;

(4)K值的選取對K近鄰法和加權K近鄰法的定位精度也有一定的影響。

上述這些影響因素在其他論文中會進一步加以研究。

6 結束語

本文研究的位置指紋定位系統(tǒng)與文獻中的發(fā)射端和接收端位置不同,由此引起一系列問題。本文對實現(xiàn)不同強度干擾源進行定位的在線定位算法進行了改進,給出了改進算法的思想、原理和實現(xiàn)流程;分別通過仿真和實驗對改進的算法進行了驗證,說明改進算法對發(fā)射信號強度不敏感,證明了算法的可行性;并用多個測試點驗證了改進后算法對不同強度信號源的定位精確度。仿真和實驗結果表明,改進的算法對不同強度的信號源使用最近鄰法、K近鄰法和加權K近鄰法都能夠實現(xiàn)定位。此外,該算法不僅對強度不同的信號源能夠定位,而且,如果信號源發(fā)射模塊增益不同,發(fā)射源頻率不同(但需要在同頻段范圍),把這些因素歸至發(fā)射源強度上,改進的算法一樣可以實現(xiàn)較好的定位;該定位算法的思想可以應用到現(xiàn)有的結接收端進行位置指紋定位系統(tǒng)中,可以避免接收端接收模塊增益不同的影響。

參考文獻:

[1] 謝代軍.無線局域網(wǎng)室內定位技術研究[D].鄭州:解放軍信息工程大學,2013.

XIE Daijun. Research on WLAN indoor location estimation technology[D]. Zhengzhou:PLA Information Engineering University,2013. (in Chinese)

[2] ZHOU M,XU Y B,MA L. Adaptive autocorrelation approach for fingerprint-based distance dependent positioning algorithms in WLAN indoor areas [J]. Journal of Network,2011,6(10):1475-1482.

[3] 劉洺辛,孫建利.基于能效的WLAN室內定位系統(tǒng)模型設計與實現(xiàn)[J].儀器儀表學報,2014,35(5):1169-1178.

LIU Mingxin,SUN Jianli. Design and implementation of WLAN indoor positioning system model based on energy efficiency[J]. Chinese Journal of Scientific Instrument, 2014,35(5):1169-1178. (in Chinese)

[4] 張維,李文濤,王力.基于接收信號強度的不同移動終端定位方法研究[J].西北工業(yè)大學學報,2014,32 (3):481-485.

ZHANG Wei,LI Wentao,WANG Li. Research on RSS(received signal strength) positioning method when mobile terminals are different[J]. Journal of Northwestern Polytechnical University,2014,32(3):481-485. (in Chinese)

[5] 謝代軍,孔范增,胡捍英.終端異質下位置指紋的魯棒性研究[J].計算機工程,2014,40(5):81-85.

XIE Daijun,KONG Fanzeng,HU Hanying. Research onrobustness of location fingerprint under terminal heterogeneity[J]. Computer Engineering,2014,40(5):81-85. (in Chinese)

[6] RATANA P,PANARAT C. A comparative study on indoor localization based on RSSI measurement in wireless sensor network[C] / / Proceedings of the 8th International Joint Conference on Computer Science and Software Engineering. Nakhon Pathom,Thailand:IEEE,2011:1-6.

[7] XIE L. A new indoor localization method based on inversion propagation model[C] / / Proceedings of the 6th International Conference on Wireless Communications Networking and Mobile Computing. Chengdu:IEEE,2010:1-4.

[8] 張興. WLAN室內定位信號特征提取算法研究[D].哈爾濱:哈爾濱工業(yè)大學,2013.

ZHANG Xing. Signal feature extraction algorithm in WLAN indoor localization[D]. Harbin:Harbin Institute of Technology,2013. (in Chinese)

[9] CARLOS F,JOSE L,INMACULADA M. Time - space sampling and mobile device calibration for WIFI indoor location systems[J]. IEEE Transactions on Mobile Computing,2011,10(7):913-926.

[10] 李論,丁恩杰,郝麗娜,等.一種改進的煤礦井下指紋定位匹配算法[J].傳感技術學報,2014,27(3):388-393.

LI Lun,DING Enjie,HAO Lina,et al. An improved location fingerprint localization matching algorithm in coal mine[ J]. Chinese Journal of Sensors and Actuators, 2014,27(3):388-393. (in Chinese)

[11] SUROSO D J, CHERNTANOMWONG P, SOORAKSA P,et al. Fingerprint-based technique for indoor localization in wireless sensor networks using fuzzy C-means clustering algorithm[J]. International Symposium on Intelligent Signal Processing and Communication system, 2011,2(2):1288-1294.

[12] JAIN V, TAPASWI S, SHUKLA A. RSS fingerprints based distributedsemi-supervised locally linear embedding location estimation system for indoorWLAN [J]. Wireless Personal Communications,2012(1):1-18.

[13] ZHOU M,XU Y,TANG L. Multilayer ANN indoor location system with area division in WLAN environment [J]. Systems Engineering and Electronics, 2010, 21 (5):914-926.

[14] 徐鳳燕,李樑賓,王宗欣.一種新的基于區(qū)域劃分的距離-損耗模型室內WLAN定位系統(tǒng)[J].電子與信息學報,2008,30(6):1405-1408.

XU Fengyan, LI Liangbin, WANG Zongxin. A new WLAN indoor localization system based on distance-loss model with area partition[J]. Journal of Electronics & Information Technology, 2008, 30 (6): 1405 - 1408. (in Chinese)

[15] 周牧,張巧,邱楓.基于物理鄰近點輔助的無線局域網(wǎng)指紋定位方法[J].計算機應用,2014,34(6):1563-1566.

ZHOU Mu,ZHANG Qiao,QIU Feng. Fingerprinting location method for WLAN using physical neighbor points information[J]. Journal of Computer Applications,2014, 34(6):1563-1566. (in Chinese)

江春冬(1974—),女,吉林鎮(zhèn)賚人,2013年于河北工業(yè)大學獲工學博士學位,現(xiàn)為講師,主要研究方向為信息檢測與智能算法;

JIANG Chundong was born in Zhenlai,Jilin Province,in 1974. She received the Ph. D. degree from Hebei University of Technology in 2013. She is now a lecturer. Her research concerns information detection and intelligent algorithms.

Email:chundong_j@163. com

惠 慧(1991—),女,河北滄州人,碩士研究生,主要研究方向計算機控制與工程應用;

HUI Hui was born in Cangzhou,Hebei Province,in 1991. She is now a graduate student. Her research concerns computer control and engineering applications.

陳云飛(1979—),男,河北邢臺人,講師,博士研究生,主要研究方向為計算機檢測技術;

CHEN Yunfei was born in Xingtai, Hebei Province, in 1979. He is now a lecturer and currently working toward the Ph. D. degree. His research concerns computer detection technology.

杜太行(1963—),男,天津人,教授、博士生導師,主要研究方向為電器檢測和計算機應用。

DU Taihang was born in Tainjin,in 1963. He is now a professor and also the Ph. D. supervisor. His research concerns electrical testing and computer applications.

An Improved Online Position Fingerprint Algorithm for Strength-independent Interference Source Location

JIANG Chundong1,2,HUI Hui1,CHEN Yunfei1,DU Taihang1,2
(1. School of Control Science and Engineering,Hebei University of Technology,Tianjin 300130,China; 2. Control Engineering Research Center of Hebei,Tianjin 300130,China)

Abstract:The existing hotter indoor location fingerprint positioning system that fixes the transmitter and positions the receiver is applied to the indoor radio interference source location that fixes the receiver and positions the transmitter. And an online locating method considering interference source signal strength is studied in order to overcome the problem that using directly the established fingerprint database with constant emission intensity and existing online positioning methods couldn't position when interference sources are from different emission intensities. According to the analysis of signal propagation model and the existing online positioning method,the presented method uses the variance of intensity differences to perform positioning calculation. The algorithm basis and procedures are given,and the improved algorithm's practicability is verified by simulation and experiment. At the same time,the idea of the improved algorithm also has a certain guiding significance to fingerprint positioning systems considering the receiver heterogeneity position.

Key words:location fingerprint position;interference source intensity;online position method

doi:10. 3969/ j. issn. 1001-893x. 2016. 02. 004引用格式:鐘德安,茅永興,劉揚,等.船載雷達光軸晃動對修正參數(shù)標定的影響[J].電訊技術,2016,56(2):135-139. [ZHONG Dean,MAO Yongxing,LIU Yang,et al. Influence of ship-borne radar optical axis jitters on calibration of correction parameters[J]. Telecommunication Engineering,2016,56(2):135-139. ]

作者簡介:

中圖分類號:TN966. 3

文獻標志碼:A

文章編號:1001-893X(2016)02-0128-07

基金項目:工業(yè)和信息化部課題(12-MC-KY-14)

*收稿日期:2015-07-13;修回日期:2015-09-22 Received date:2015-07-13;Revised date:2015-09-22