周雄，陳國彬

重慶工商大學(xué)融智學(xué)院，重慶 400033

基于權(quán)重參數(shù)實(shí)時(shí)更新的室內(nèi)定位算法

周雄，陳國彬

重慶工商大學(xué)融智學(xué)院，重慶 400033

為了提高室內(nèi)節(jié)點(diǎn)的定位精度，提出一種基于權(quán)值參數(shù)實(shí)時(shí)更新的室內(nèi)定位算法。選擇3個(gè)最能反映待定位點(diǎn)信息的訪問接入點(diǎn)，實(shí)時(shí)獲取測距模型的參數(shù)，并采用最小二乘支持向量機(jī)對測距進(jìn)行補(bǔ)償，得到距離權(quán)重，三邊定位算法根據(jù)權(quán)重對節(jié)點(diǎn)進(jìn)行定位，并對計(jì)算中的距離進(jìn)行加權(quán)處理，采用卡爾曼濾波法對定位誤差的進(jìn)行校正。實(shí)驗(yàn)結(jié)果表明，該算法可以較好地降低環(huán)境變化和測量誤差對定位的不利影響，提高了室內(nèi)節(jié)點(diǎn)的定位精度。

室內(nèi)定位；無線網(wǎng)絡(luò)；最小二乘支持向量機(jī)；卡爾曼濾波

1 引言

隨著無線通信技術(shù)和智能移動(dòng)終端不斷發(fā)展，位置服務(wù)已經(jīng)得到迅速普及，無線定位技術(shù)在軍事、交通、物流、醫(yī)療、民生等領(lǐng)域得到了廣泛的應(yīng)用。在室外空曠的環(huán)境下，全球定位系統(tǒng)（Global Position System，GPS）通過衛(wèi)星的授時(shí)和測距對用戶節(jié)點(diǎn)進(jìn)行定位，具有定位精度高、實(shí)時(shí)性好、抗干擾能力強(qiáng)等優(yōu)點(diǎn)[1]。相對于室外環(huán)境，室內(nèi)環(huán)境更加復(fù)雜，信號傳播易受到人員、墻體以及其他障礙物的阻擋，定位難度增加，GPS捕捉衛(wèi)星信號相當(dāng)微弱，其定位性能不能滿足實(shí)際人們生產(chǎn)活動(dòng)定位精度的需求，因此如何提高室內(nèi)定位精度已成為當(dāng)前無線定位技術(shù)研究中的熱點(diǎn)[2-3]。

針對無線室內(nèi)定位問題，大量學(xué)者和研究人員進(jìn)行了深入的研究，提出許多有效的室內(nèi)定位算法[4]。根據(jù)定位原理，室內(nèi)定位算法主要分為兩類：時(shí)間測距定位和接收信號強(qiáng)度（Received Signal Strength Indication，RSSI）定位[5]?；跁r(shí)間測距的定位方法主要包括：信號到達(dá)時(shí)間（Time Of A rrival，TOA）定位、信號到達(dá)時(shí)間差（Time Difference of A rrival，TDOA）定位等[6-9]。基于TOA定位算法存在對噪聲敏感、多路徑反射以及參考時(shí)鐘不精確等缺陷，距離估計(jì)誤差大；基于TDOA定位算法要求各設(shè)備間同步，但由于室內(nèi)距離有限，導(dǎo)致測得距離誤差較大，同時(shí)它們在定位過程中需要其他輔助設(shè)備的支持，因此在室內(nèi)定位中，這些算法難以真正有效實(shí)現(xiàn)[10]?；赗SSI的定位思想為：首先得到發(fā)射節(jié)點(diǎn)的發(fā)射信號強(qiáng)度，接收節(jié)點(diǎn)根據(jù)收到信號的強(qiáng)度計(jì)算出信號的傳播損耗，然后通過傳輸損耗模型得到待定位點(diǎn)到訪問接入點(diǎn)（Access Point，AP）之間的距離，再選擇合適的算法計(jì)算出節(jié)點(diǎn)的位置，從而實(shí)現(xiàn)對定位節(jié)點(diǎn)的精確定位。相對于時(shí)間測試距定位算法，其不需要添加額外的硬件設(shè)備，簡單易實(shí)現(xiàn)，成本低，可以將定位系統(tǒng)的應(yīng)用范圍擴(kuò)大到樓群和室內(nèi)，因此成為室內(nèi)定位的主要研究方向[11]。但是在實(shí)際室內(nèi)環(huán)境中，信號傳播過程受到傳播方向、通信多徑現(xiàn)象以及室內(nèi)結(jié)構(gòu)等環(huán)境因素的影響，AP的RSSI值不固定，具有時(shí)變性，如果直接采用AP的RSS值為輸入，實(shí)現(xiàn)室內(nèi)定位，導(dǎo)致室內(nèi)定位誤差大，精度低。針對該難題，許多學(xué)者在RSSI定位算法的基礎(chǔ)上，對環(huán)境影響因素進(jìn)行了分析，提出許多學(xué)改進(jìn)的RSSI室內(nèi)定位算法，對各種不利影響進(jìn)行抑制，消除估計(jì)誤差，以提高室內(nèi)定位的精度[12]。

為了提高室內(nèi)節(jié)點(diǎn)定位的精度，提出一種基于權(quán)值參數(shù)實(shí)時(shí)更新（Weight Parameter Real-time Updating，WPRU）的室內(nèi)定位算法，并通過仿真實(shí)驗(yàn)測試本文算法的有效性和優(yōu)越性。仿真結(jié)果表明，WPRU減少因環(huán)境因素以及信號強(qiáng)度測量過程的誤差，提高了室內(nèi)定位的精度。

2 三邊定位算法

在理想情況下，由測距階段得到的待定位點(diǎn)到3個(gè)AP的距離就可以計(jì)算出待定位點(diǎn)的位置，即以已知位置的三個(gè)AP為圓心，以其各自到待定位點(diǎn)的距離為半徑做圓，所得三個(gè)圓的交點(diǎn)，即為待定位點(diǎn)的位置[13]。

如圖1所示，設(shè)未知節(jié)點(diǎn)D坐標(biāo)為(x，y)，A，B，C三個(gè)點(diǎn)坐標(biāo)分別為(xA，yA)、(xB，yB)、(xC，yC)，它們到點(diǎn)D的距離分別為dA、dB、dC，根據(jù)距離公式得到以下方程組：

圖1 三邊定位法示意圖

3 WPRU定位算法

3.1 WPRU算法的工作流程

WPRU算法首先實(shí)時(shí)獲取測距模型參數(shù)A和n的值，然后采用最小二乘支持向量機(jī)補(bǔ)償測距誤差，然后計(jì)算距離權(quán)重，并采用三邊定位算法進(jìn)行定位，最后采用卡爾曼濾波法對定位誤差進(jìn)行校正，以提高定位精度，具體如圖2所示。

圖2 WPRU算法的工作流程

在城市、郊區(qū)等環(huán)境，接收到的信號強(qiáng)度為：

式中，n為信號路徑傳播耗散系數(shù)；RSSIr為接收到的信號強(qiáng)度；A為在參考距離的接收信號強(qiáng)度。

對式（3）進(jìn)行推導(dǎo)，可以得：

受到多種因素的影響，如人員走動(dòng)，A和n值的變化比較大，對于不同室內(nèi)環(huán)境，其值不相同，它們的值根據(jù)經(jīng)驗(yàn)進(jìn)行設(shè)置，有時(shí)誤差相當(dāng)大，因此需根據(jù)具體定位環(huán)境，找到最能反映定位環(huán)境的參數(shù)值，以提高室內(nèi)定位的精度。

已知3個(gè)錨節(jié)點(diǎn)A(xA，yA)，B(xB，yB)，C(xC，yC)的位置，C點(diǎn)的當(dāng)前環(huán)境下A、B兩個(gè)點(diǎn)信號強(qiáng)度RSSIA、RSSIB，按照測距模型得：

對式（5）進(jìn)行求解，可以得到A和n的值，這樣它們的值可以準(zhǔn)確反映當(dāng)前環(huán)境下的實(shí)時(shí)參數(shù)值。

3.2 設(shè)置距離的權(quán)值

文獻(xiàn)[14]指出，隨著距離的增大，信號強(qiáng)度的誤差相應(yīng)增大，在實(shí)時(shí)獲取參數(shù)A和n的值同時(shí)，需要對測距距離進(jìn)行加權(quán)處理，降低信號強(qiáng)度和距離引起的誤差。權(quán)重參數(shù)反映了不同AP對目標(biāo)點(diǎn)的影響程度，而距離可以反映目標(biāo)點(diǎn)和AP之間位置關(guān)系，因此采用距離平方的倒數(shù)作為權(quán)值，權(quán)重參數(shù)ωi計(jì)算公式為：

式中，di為目標(biāo)點(diǎn)到AP距離大小的序列。

目標(biāo)點(diǎn)的位置計(jì)算公式為：

3.3 誤差補(bǔ)償

設(shè)實(shí)際距離為d，則實(shí)際距離d與測量距離d′間存在如下關(guān)系：

式中，?E表示誤差。

采用最小二乘支持向量機(jī)對誤差進(jìn)行預(yù)測和補(bǔ)償，LSSVM的回歸函數(shù)為：

式中，ω表示為權(quán)向量。

綜合考慮函數(shù)的復(fù)雜度和擬合誤差，最小二乘支持向量機(jī)的目標(biāo)函數(shù)為：

式中，ξi為誤差變量；γ為正則化參數(shù)。

根據(jù)Karush-Kuhn-Tucker（KKT）最優(yōu)條件，得到如下線性方程組：

根據(jù)Mercer條件，核函數(shù)可寫為：

計(jì)算b，a后，最小二乘支持向量機(jī)的回歸函數(shù)為：

徑向基核函數(shù)具有參數(shù)少，通用性好等優(yōu)點(diǎn)，選擇該函數(shù)作為最小二乘支持向量機(jī)的核函數(shù)，具體定義如下：

通過式（14）建立了距離誤差函數(shù)，得到相應(yīng)的預(yù)測誤差值(?E′)，并進(jìn)行誤差補(bǔ)償，即

其中，d″為未知節(jié)點(diǎn)與錨節(jié)點(diǎn)間的測量距離修正值。

3.4 卡爾曼濾波修正誤差

為了得到更準(zhǔn)確的信號強(qiáng)度值，使用卡爾曼濾波修正誤差，卡爾曼濾波通過線性隨機(jī)差分方程來評估離散系統(tǒng)過程中狀態(tài)變量x的一個(gè)過程，其表達(dá)形式如下：

式中，A∈Rn×n為狀態(tài)轉(zhuǎn)移矩陣；uk-1和B分別為輸入變量和與之對應(yīng)的系數(shù)矩陣；zk∈Rm為測量值；H∈Rm×n為測量矩陣；隨機(jī)變量wk和vk分別表示濾波系統(tǒng)誤差和測量誤差，它們被假定為相互獨(dú)立且具有標(biāo)準(zhǔn)正態(tài)分布的白噪聲，即

式中，Q為濾波過程噪聲協(xié)方差矩陣，R為測量噪聲協(xié)方差矩陣[15]。

卡爾曼濾波器的計(jì)算方程分為兩組：時(shí)間更新方程和測量更新方程；時(shí)間更新方程中當(dāng)前階段的預(yù)測狀態(tài)通過上個(gè)階段的狀態(tài)和誤差協(xié)方差矩陣獲得；測量更新方程則將當(dāng)前階段的測量值與當(dāng)前階段的預(yù)測狀態(tài)結(jié)合起來獲得當(dāng)前階段的狀態(tài)。時(shí)間更新方程的數(shù)學(xué)表達(dá)如下：

式中，Kk為卡爾曼增益，zk為當(dāng)前階段的測量值。

圖3 卡爾曼濾波方框圖

定位算法的位置用zk表示，先前狀態(tài)得到的定位位置用表示，整個(gè)卡爾曼濾波過程應(yīng)用在每次誤差計(jì)算中，對協(xié)方差進(jìn)行不斷遞歸，卡爾曼增益不斷調(diào)節(jié)，并將校正后的距離用在新的定位計(jì)算中。

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

4.1 仿真環(huán)境

為了測試本文算法的性能，實(shí)驗(yàn)場景大小為10 m× 40 m的區(qū)域，在4個(gè)頂點(diǎn)部署4個(gè)錨節(jié)點(diǎn)，中間隔放置4個(gè)錨節(jié)點(diǎn)。定位誤差計(jì)算公式為：

式中，(x，y)表示計(jì)算得到的待定位點(diǎn)的位置；(x′，y′)表示待定位點(diǎn)實(shí)際的位置。

4.2 參數(shù)實(shí)時(shí)更新對定位的影響

為了測距模型參數(shù)實(shí)時(shí)更新對定位結(jié)果的影響，采用經(jīng)驗(yàn)參數(shù)確定方法進(jìn)行對比實(shí)驗(yàn)，待定位節(jié)點(diǎn)在室內(nèi)進(jìn)行隨機(jī)移動(dòng)，并不斷測量AP節(jié)點(diǎn)發(fā)送來的信號強(qiáng)度信息，它們待定位點(diǎn)的位置如圖4所示。

實(shí)時(shí)獲取參數(shù)方法和參數(shù)經(jīng)驗(yàn)設(shè)置方法的定位誤差如圖5所示，從圖5可知，相對于經(jīng)驗(yàn)設(shè)置參數(shù)值方法，實(shí)時(shí)獲取參數(shù)方法定位誤差明顯減小，而且波動(dòng)范圍較小，對比結(jié)果表明，由于實(shí)時(shí)獲取參數(shù)方法可以較好地描述實(shí)驗(yàn)場景動(dòng)態(tài)變化，適用范圍更廣，定位結(jié)果更加可靠。

圖4 兩種方法的節(jié)點(diǎn)定位軌跡

圖5 實(shí)時(shí)和經(jīng)驗(yàn)參數(shù)定位方法的誤差比較

4.3 卡爾曼濾波對定位結(jié)果的影響

為了測試卡爾曼濾波的作用，采用沒有卡爾曼濾波定位方法進(jìn)行對比實(shí)驗(yàn)，兩種方法的定位誤差的變化曲線如圖6所示。從圖可知，卡爾曼濾波法的平均定位誤差較小，50次實(shí)驗(yàn)平均定位誤差變化平穩(wěn)，較好解決了RSSI測距誤差室內(nèi)定位的不利影響，而沒有采用卡爾曼濾波法的平均定位誤差變化比較劇烈，誤差較大，定位結(jié)果不可靠，對比結(jié)果證明了WPRU方法采用卡爾曼濾波法校正定位算法誤差的思想是正確的，有利于提高室內(nèi)的定位精度。

4.4 與其他定位方法的性能對比

為了使WPRU定位算法的結(jié)果更具說服力，選擇三邊定位算法、文獻(xiàn)[14]的室內(nèi)定位算法進(jìn)行對比實(shí)驗(yàn)，它們的結(jié)果見表1所示。對表1的結(jié)果進(jìn)行分析，可以得到如下結(jié)論：

圖6 卡爾曼濾波法對定位誤差的影響

（1）相對于三邊定位算法，WPRU算法的定位精度顯著提高，定位誤差大變化幅度減小，這是因?yàn)樵趯?shí)際定位過程中，由于測距存在著誤差，使得三圓心未必會(huì)交于一點(diǎn)，使三邊定位算法的定位誤差較大，而WPRU算法通過實(shí)時(shí)采集測距模型的參數(shù)，減少了測距誤差，并通過卡爾曼濾波對定位誤差進(jìn)行校正，有效提高了室內(nèi)的定位精度。

（2）相對于文獻(xiàn)[14]的定位算法，WPRU算法的定位精度得到了相應(yīng)提高，主要由于WPRU算法采用最小二乘支持向量機(jī)對距離誤差進(jìn)行補(bǔ)償，減少了定位誤差，一定程度上可以提高室內(nèi)的定位精度。

表1 不同定位算法的定位誤差比較

WPRU定位算法與其他算法的定位速度進(jìn)行對比實(shí)驗(yàn)，采用定位時(shí)間作為衡量指標(biāo)，它們的結(jié)果如圖7所示，從圖7可知，相對于三邊定位算法和文獻(xiàn)[14]的定位算法，WPRU定位算法的定位時(shí)間更短，定位最快，可以較好地滿足無線室內(nèi)定位的實(shí)時(shí)性要求。

圖7 不同算法的定位速度對比

5 結(jié)語

針對室內(nèi)定位精度低的難題，提出一種基于WPRU定位算法，并通過仿真實(shí)驗(yàn)測試算法的性能。仿真結(jié)果表明，WPRU算法不僅提高了室內(nèi)定位的精度，降低了定位的誤差，同時(shí)沒有增加定位成本，具有更大的實(shí)用值。

[1]Gu Y Y，Lo A，Niemegeers I.A survey of indoor positioning systems for wireless personal networks[J].IEEE Communications Surveys&Tutorials，2009，11（1）：13-32.

[2]Bshara M，Orguner U，Gustafsson F，et al.Fingerprinting localization in wireless networks based on received-signalstrength measurements：a case study on W iMAX networks[J].IEEE Trans on Veh Technol，2010，59（1）：283-294.

[3]Bulusu N，Heidemann J，Estrin D.GPS-less low cost outdoor localization for very small devices[J].IEEE Personal Communications M agazine，2000，7（5）：28-34.

[4]朱劍，趙海，孫佩剛，等.基于RSSI均值的等邊三角形定位算法[J].東北大學(xué)學(xué)報(bào)，2007，28（8）：1094-1097.

[5]劉運(yùn)杰，金明錄，崔承毅.基于RSSI的無線傳感器網(wǎng)絡(luò)修正加權(quán)定位算法[J].傳感技術(shù)學(xué)報(bào)，2009，23（5）：717-721.

[6]徐鳳燕，單杭冠，王宗欣.一種帶參數(shù)估計(jì)的基于接收信號強(qiáng)度的室內(nèi)定位算法[J].微波學(xué)報(bào)，2008，24（2）：67-72.

[7]張明華，張申生，曹健.無線局域網(wǎng)中基于信號強(qiáng)度的室內(nèi)定位[J].計(jì)算機(jī)科學(xué)，2007，34（6）：68-71.

[8]劉召偉，徐鳳燕，王宗欣.基于參數(shù)擬合的室內(nèi)多用戶定位算法[J].電波科學(xué)學(xué)報(bào)，2009，23（6）：1090-1094.

[9]Agustín E，Salcedoz S，Vidales P，et al.Near optimal cityWide W iFi network deployment using a hybrid grouping genetic algorithm[J].Expert Systems with Applications，2011，38（8）：9543-9556.

[10]倪巍，王宗欣.基于接收信號強(qiáng)度測量的室內(nèi)定位算法[J].復(fù)旦學(xué)報(bào)：自然科學(xué)版，2004，43（1）：72-76.

[11]Carlos K F，Inmaculada M J，A licia G C，et al.Nonparametric model comparison and uncertainty evaluation for signal strength indoor location[J].IEEE Transactions on Mobile Computing，2009，8（9）：1250-1264.

[12]萬國鋒，鐘俊.基于三角形理論的無線傳感器網(wǎng)絡(luò)定位算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30（1）：249-251.

[13]Kushki A，Plataniotis K，Venetsanopoulos A.Intelligent dynamic radio tracking in indoor wireless local area networks[J].IEEE Transactions on M obile Computing，2010，9（3）：405-419.

[14]白云.一種傳播模型無關(guān)的快速W iFi訪問點(diǎn)定位算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2013，34（2）：220-223.

[15]Raman Kumar K，Apte V，Powar Y A.Improving the accuracy of wireless LAN based location determ ination systems using Kalman filter and multiple observers[C]//IEEE Wireless Communication and Networking Conference，Las Vegas，USA，2006，1：463-468.

ZHOU Xiong,CHEN Guobin

College of Rongzhi, Chongqing Technology and Business University, Chongqing 400033, China

In order to improve the localization precision, a novel indoor localization algorithm based on weight parameter real-time updating is proposed in this paper. Three APs which can best explain the information of object are selected, and then the parameters of range model are updated in a real-time way, and the least square support vector machine is used to correct the range error to obtain the distance weights, the localization is obtained by using triangle-based localization algorithm based on distance weights and the localization error is corrected by Kalman filter method. The experimental results show that the proposed algorithm can reduce the error caused by surroundings and signal strength, and it has improved the higher localization precision.

indoor location;wireless network;least square support vector machine;Kalman filter

ZHOU Xiong, CHEN Guobin. Indoor localization algorithm based on weight parameter real-time updating. Computer Engineering and Applications, 2014, 50（17）：191-194.

A

TP393

10.3778/j.issn.1002-8331.1401-0396

重慶市教委科學(xué)技術(shù)研究項(xiàng)目（No.KJ133103）。

周雄（1980—），男，高級工程師，主研領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)類；陳國彬（1982—），男，講師，主研領(lǐng)域?yàn)橛?jì)算機(jī)網(wǎng)絡(luò)類。

2014-01-23

2014-03-10

1002-8331（2014）17-0191-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-08-05,http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1401-0396.htm l