陳順明，李平

長沙理工大學(xué)計算機(jī)與通信工程學(xué)院，長沙410114

基于RSSI權(quán)值的環(huán)境適應(yīng)型室內(nèi)定位算法研究

陳順明，李平

長沙理工大學(xué)計算機(jī)與通信工程學(xué)院，長沙410114

定位節(jié)點(diǎn)接收的信號強(qiáng)度指示（Received Signal Strength Indication，RSSI）值是室內(nèi)指紋定位技術(shù)重要的元素之一。通過對定位節(jié)點(diǎn)接收到的信號強(qiáng)度值特性分析，提出了基于RSSI權(quán)值的室內(nèi)定位算法。改進(jìn)型RSSI權(quán)值計算公式以及權(quán)值指數(shù)α的提出，使得定位算法具有一定的環(huán)境適應(yīng)性，能更靈活地運(yùn)用于實(shí)際定位場景。經(jīng)過一般實(shí)驗(yàn)場景驗(yàn)證，算法在定位精度上有較大的提升。

定位節(jié)點(diǎn)接收的信號強(qiáng)度指示（RSSI）；權(quán)值；環(huán)境適應(yīng)性；室內(nèi)定位

近年來，隨著各種無線通信技術(shù)的迅速發(fā)展以及移動設(shè)備的逐漸普及，室內(nèi)環(huán)境下各種基于位置的服務(wù)需求日益迫切［1-3］，無線室內(nèi)定位算法的研究，已成為國內(nèi)外研究的重點(diǎn)［4］。研究表明，基于RSSI指紋庫的室內(nèi)定位技術(shù)，由于操作簡單、硬件花費(fèi)少、容易實(shí)現(xiàn)等優(yōu)點(diǎn)，目前，已成為室內(nèi)定位技術(shù)研究的熱點(diǎn)。但是，傳統(tǒng)的指紋定位技術(shù)有著定位精度不高、不具有隨實(shí)驗(yàn)環(huán)境場景進(jìn)行變化調(diào)整等缺點(diǎn)，針對此點(diǎn)，本文提出了一種具有環(huán)境適應(yīng)性的改進(jìn)加權(quán)型室內(nèi)定位算法。

1　基于RSSI指紋庫的室內(nèi)定位技術(shù)

室內(nèi)環(huán)境復(fù)雜，定位干擾甚多，如多徑傳播、非視距傳播、多址傳播等都會帶來定位誤差［5］，但是基于RSSI指紋庫定位技術(shù)卻利用多徑傳播等來構(gòu)建節(jié)點(diǎn)位置信息，由于信號在室內(nèi)傳播過程中受到固定障礙物的影響，因而多經(jīng)效應(yīng)呈現(xiàn)出非常強(qiáng)的位置特性，對于每一個位置來說，傳播信道的多經(jīng)結(jié)構(gòu)是唯一的，它的多徑特征可以被認(rèn)為是該位置的指紋，通過指紋匹配可以很容易地找出定位節(jié)點(diǎn)的位置坐標(biāo)［6］。基于這樣的原理，人們提出了基于RSSI值指紋庫的室內(nèi)定位技術(shù)。

指紋技術(shù)的定位過程一般分為兩個階段［7］：第一個階段為離線采樣階段，該階段的主要任務(wù)是建立RSSI指紋數(shù)據(jù)庫V=［L1L2…Lj…Lm］。采集定位區(qū)域內(nèi)各個位置點(diǎn)的RSSI值并形成樣本位置指紋庫，其中每一條數(shù)據(jù)都對應(yīng)一個唯一位置Lj=［sj1sj2…sji…sjn］。第二階段為在線定位階段，該階段通過測定定位節(jié)點(diǎn)所在位置實(shí)時信號強(qiáng)度值，然后采用匹配算法找出與指紋數(shù)據(jù)庫中最為匹配的一條數(shù)據(jù)，從而確定定位節(jié)點(diǎn)的實(shí)際位置。

定位過程中采用的匹配算法是定位過程中的關(guān)鍵。目前，基于RSSI指紋庫定位技術(shù)的匹配算法主要分為兩類：第一類是確定性方法［8］，如信號空間最近鄰法和最接近K鄰居法（K-Nearest Neighbors，K-NN）。第二類是基于概率性的方法［9］，如貝葉斯算法。本文所要討論的重點(diǎn)是的K-NN算法。

K-NN算法一般過程為［10］：首先，利用公式（1）計算定位點(diǎn)與樣本點(diǎn)之間的信號歐幾里德距離［11］。

其中，sji表示樣本點(diǎn)的RSSI值，s′i表示定位節(jié)點(diǎn)RSSI值。

然后，選取其中距離最小的前K個，獲得其樣本坐標(biāo)：

最后，通過質(zhì)心計算得到定位點(diǎn)的定位坐標(biāo)：

K-NN算法是指紋定位算法的一個重要匹配方法，由于K-NN算法簡單、易操作，在室內(nèi)定位被廣泛應(yīng)用。因此，許多改進(jìn)型的指紋算法都是針對K-NN算法提出的。

2　相關(guān)研究

基于K-NN算法的指紋改進(jìn)算法主要分為兩大類：第一類是基于RSSI值的，李奇［12］等人根據(jù)定位點(diǎn)與樣本點(diǎn)之間RSSI值的相關(guān)性，提出了相關(guān)性算法。通過公式（2）得出定位點(diǎn)與樣本點(diǎn)RSSI值之間的相關(guān)系數(shù)ρ，然后選取ρ值最大的K個，再通過質(zhì)心計算，得到定位點(diǎn)坐標(biāo)。

第二類是基于信號距離的，這一類的改進(jìn)分為兩個方面，其一是加入權(quán)值的計算，汪媛卿等人［13］提出的基于距離權(quán)重（WDF）的指紋定位算法，在計算信號距離時，加入距離權(quán)值，權(quán)值定義為定位節(jié)點(diǎn)實(shí)測RSSI值與其訓(xùn)練值方差之間的差值，根據(jù)差值不同賦予不同的權(quán)值；其二是將信號距離轉(zhuǎn)化為實(shí)際物理距離計算，Liang等人［14］提出的改進(jìn)型K-NN算法（DWFW-KNN），根據(jù)實(shí)際驗(yàn)證節(jié)點(diǎn)之間的信號距離與物理實(shí)際距離之間有著較大的差異，利用LDPL（Log-Distance Path Loss）室內(nèi)信號傳播公式，將信號距離轉(zhuǎn)化為物理距離進(jìn)行計算，從而獲得較高的定位精度。

以上算法對于室內(nèi)定位精度都有著不同程度的提高，但是，這些算法都沒有考慮定位節(jié)點(diǎn)RSSI值本身對定位的影響，通過對數(shù)據(jù)進(jìn)行分析得知，RSSI值本身應(yīng)該具有權(quán)重值，定位時不能統(tǒng)一計算；同時，上述一些改進(jìn)算法都不能隨著環(huán)境參量的改變而進(jìn)行調(diào)整，不具備環(huán)境適應(yīng)能力。在此，提出了基于RSSI權(quán)值的環(huán)境適應(yīng)型室內(nèi)定位算法—RW（RSSI-Weight）算法。

3　RW算法介紹

RW算法是基于RSSI值本身權(quán)重的定位算法，定位過程中根據(jù)定位節(jié)點(diǎn)接收信號強(qiáng)度值進(jìn)行權(quán)值分配計算，而權(quán)值指數(shù)的調(diào)整變化，使得定位算法具有一定的環(huán)境適應(yīng)性，從而使得定位計算更加貼近實(shí)際，定位精度更高。

3.1權(quán)值依據(jù)

在室內(nèi)環(huán)境下，無線信號的傳播符合LDPL衰減模型［15］，用公式表示為：

化簡得到：

其中，pd是在距離d處的信號能量，Pd0是在距離為d0處的信號能量，通常設(shè)為1，η是信道衰減參數(shù)，與當(dāng)時實(shí)驗(yàn)環(huán)境相關(guān)。通過實(shí)驗(yàn)，可以得出實(shí)測接收信號強(qiáng)度值與距離之間的關(guān)系，如圖1所示。

圖1　RSSI值與距離關(guān)系

由公式（3）和圖1，可以得出如下結(jié)論：RSSI值與距離成反比；距離越小，RSSI值越大，而較小的距離，說明節(jié)點(diǎn)間的相關(guān)性較大，因此具有較大的權(quán)值；反之，較大的距離，說明節(jié)點(diǎn)之間相關(guān)性較小，具有較小的權(quán)值。

3.2權(quán)值公式

根據(jù)上面得到的結(jié)論，再結(jié)合權(quán)值的一般定義，所以通常情況下，將權(quán)值公式定義為［13］：

經(jīng)過多次數(shù)據(jù)訓(xùn)練，發(fā)現(xiàn)公式（4）并不適合應(yīng)用于實(shí)際：首先，計算過程中公式（4）中分母數(shù)值過?。ǎ?0-4），累加過程中的四舍五入會給計算結(jié)果帶來很大誤差；其次，對于定位精度通過改進(jìn)還可以進(jìn)一步提升，如圖2所示。

圖2　改進(jìn)型式子與傳統(tǒng)式子誤差比較

再者，由于公式固定，不能針對定位環(huán)境進(jìn)行調(diào)整，而使得算法適應(yīng)性不強(qiáng)。經(jīng)過對數(shù)據(jù)的多次對比和分析，最終將RSSI權(quán)值公式定義為：

3.3權(quán)值指數(shù)

式子（5）中的指數(shù)α將其定義為權(quán)值指數(shù)，α的適應(yīng)性變化使得RW算法具有一定的環(huán)境適應(yīng)能力。α隨著環(huán)境場景的改變而進(jìn)行調(diào)整，使得定位算法能適應(yīng)當(dāng)時的定位環(huán)境，從而進(jìn)一步減小定位誤差。在不同的場景下α都有一個最佳值，最值范圍一般為1.5～2.5。

α的變化會帶來定位平均誤差（Mean Error，ME）的相應(yīng)變化，兩者之間具有一定的函數(shù)關(guān)系，這是計算α值的方法。經(jīng)過多次測試數(shù)據(jù)描點(diǎn)得到α與ME之間的關(guān)系如圖3所示。

圖3　α與ME之間的關(guān)系

由圖3可以看出，ME可以用α的多項(xiàng)式函數(shù)表示出來，再通過最小二乘多項(xiàng)式擬合法可以求得其函數(shù)表達(dá)式。不妨設(shè)α與ME的函數(shù)為：

通過計算得到下面矩陣：

將這個范德蒙得矩陣化簡之后得到：

由此矩陣就可以得出系數(shù)矩陣A，從而得到α與ME之間的多項(xiàng)式函數(shù)的確切式子。

3.4RW算法計算式

由前文知道目前基于K-NN算法的指紋算法改進(jìn)方向主要分為兩類，因此，提出了加入RSSI權(quán)值計算的兩類計算公式。

3.4.1相關(guān)性法計算公式

前文提到的相關(guān)性算法，在定位過程中將RSSI值賦予同樣的置信度，進(jìn)行統(tǒng)一計算，這樣的計算并不完善，因此在式（2）中加入權(quán)值計算，得到新的改善公式：

3.4.2歐式距離計算公式

在計算信號距離的匹配算法中，也要加入RSSI權(quán)值計算。式（1）是計算定位節(jié)點(diǎn)與樣本點(diǎn)之間歐式距離的一般公式，過程中，同樣沒有考慮定位點(diǎn)RSSI值的權(quán)重分配，而進(jìn)行統(tǒng)一計算，為此，在式（1）的基礎(chǔ)上提出加入RSSI權(quán)值的計算公式：

在此定義了RW算法的核心部分—RW計算公式。RW算法是在傳統(tǒng)指紋定位算法的基礎(chǔ)上進(jìn)行改進(jìn)的算法，在定位過程中加入定位節(jié)點(diǎn)RSSI權(quán)值計算，使得定位計算更加的完善，同時權(quán)值指數(shù)的存在，使得定位算法具有一定的環(huán)境適應(yīng)性，能更靈活的應(yīng)用于各類實(shí)驗(yàn)場景。

4　實(shí)驗(yàn)分析

算法是服務(wù)于實(shí)際應(yīng)用，同樣在實(shí)際應(yīng)用中才能檢驗(yàn)算法的優(yōu)劣。通過數(shù)據(jù)分析，性能比較，才能知道算法是否能適用于實(shí)際或者優(yōu)于現(xiàn)存算法。在定位算法的比較中，一些重要指標(biāo)是可以判斷一種算法的優(yōu)劣，如平均定位誤差、最小誤差以及最大誤差。因此，下面將對RW算法的性能指標(biāo)進(jìn)行實(shí)際比較。

4.1實(shí)驗(yàn)場景

實(shí)驗(yàn)場景設(shè)置在一個長為10 m，寬為9 m的室內(nèi)實(shí)驗(yàn)室當(dāng)中，具體布置如圖4所示。

如圖4所示：實(shí)驗(yàn)是設(shè)置在一般實(shí)驗(yàn)場景中，場景內(nèi)部并不是空曠的，而是符合一般的實(shí)際情況，具有各種干擾和障礙，這樣的場景更能檢測出算法的性能。

圖4　室內(nèi)實(shí)驗(yàn)場景布置

4.2實(shí)驗(yàn)過程

（1）采樣節(jié)點(diǎn)均勻采集室內(nèi)各個位置的樣本坐標(biāo)及RSSI值，并建立樣本指紋數(shù)據(jù)庫。

（2）定位節(jié)點(diǎn)在目標(biāo)區(qū)域內(nèi)隨機(jī)選擇150個位置，測量其坐標(biāo)及實(shí)時RSSI值。

（3）利用公式（7）和（8）分別進(jìn)行匹配定位計算并得到定位點(diǎn)估計坐標(biāo)。

（4）求出定位點(diǎn)的估計坐標(biāo)和定位點(diǎn)坐標(biāo)之間的誤差。

（5）分析各項(xiàng)性能指標(biāo)。

上述過程中，為了減少測量和計算誤差，都將進(jìn)行多次測量，以其均值進(jìn)行統(tǒng)計和計算。

4.3權(quán)值指數(shù)α的確定

在RW定位過程中還有一個重要的環(huán)節(jié)，就是在本次實(shí)驗(yàn)中權(quán)值指數(shù)α的取值。由前文以及式子（6）知道α與ME之間的函數(shù)關(guān)系，在實(shí)驗(yàn)過程中，可以通過數(shù)據(jù)的統(tǒng)計運(yùn)算獲得α和ME的對應(yīng)數(shù)值，再經(jīng)過描點(diǎn)和曲線擬合可以得到α與ME在本次實(shí)驗(yàn)中的確切表達(dá)式。如圖3所示，即為α與ME之間的數(shù)值關(guān)系，通過最小二乘多項(xiàng)式曲線擬合可以得到這樣一個函數(shù)曲線圖，如圖5所示。

圖5　關(guān)于α的擬合曲線

通過對數(shù)據(jù)的多次擬合，發(fā)現(xiàn)4次多項(xiàng)式函數(shù)，最為貼近α與ME之間的數(shù)值關(guān)系，所以α與ME之間的函數(shù)關(guān)系可以表示為：

根據(jù)式子（9），通過多項(xiàng)式函數(shù)導(dǎo)數(shù)求最值的方法，得到α的最值，將最值帶入（9）中進(jìn)行比較計算，最后得到ME的最小值，此時的α則為本次實(shí)驗(yàn)的最佳值。經(jīng)過計算，本次實(shí)驗(yàn)最佳值為α=1.9。

4.4算法性能分析

通過上述過程獲得的實(shí)驗(yàn)數(shù)據(jù)，需要進(jìn)行比較才能發(fā)現(xiàn)其中的差異。將RW算法獲得的各項(xiàng)數(shù)據(jù)指標(biāo)與同類算法進(jìn)行比較。

4.4.1與相關(guān)性算法比較

在相關(guān)性法的計算公式（2）的基礎(chǔ)上提出的加入RSSI權(quán)值計算的式子（7），通過此式，RW算法可以用于RSSI相關(guān)性算法中，運(yùn)用式子（7）計算后得到的結(jié)果與相關(guān)性法進(jìn)行比較，如圖6所示。

圖6　RW算法與相關(guān)性法比較

由圖6中可以看出RW算法在誤差減少方面要優(yōu)于相關(guān)性算法，其他性能指標(biāo)可以通過下表進(jìn)行了解。

表1　RW算法與相關(guān)性算法各項(xiàng)性能比較

由表1中可以看出，RW算法在平均誤差方面相對于相關(guān)性算法有較明顯的提升，而在其他方面兩種算法的差異則不是很大，但是，從整體上分析RW算法要優(yōu)于相關(guān)性算法。

4.4.2與基于歐式距離的算法比較

基于信號距離的算法是室內(nèi)指紋定位算法中的主要算法，所以在提高定位精度方面，技術(shù)相對比較成熟，因此，與這類算法的比較更能看到RW的優(yōu)劣所在。經(jīng)過數(shù)據(jù)分析，得到圖7。

由圖中可以看出，RW算法在定位誤差方面要優(yōu)于同類算法，其他的性能指標(biāo)可以通過下表進(jìn)行了解。

由表2可以看出，RW算法在定位精度各項(xiàng)指標(biāo)上，都要優(yōu)于同類算法，尤其是在最小誤差和平均誤差方面，提升更是比較明顯。

圖7　RW算法與各類算法比較

5　結(jié)論

通過上述的實(shí)驗(yàn)分析，有這樣一個結(jié)論：RW算法在定位精度各項(xiàng)指標(biāo)上均優(yōu)于同類算法，而且提升比較明顯，尤其是在平均定位誤差方面，誤差為1.6 m，比室內(nèi)定位算法設(shè)計的要求減少較多，說明，RW算法是符合設(shè)計要求的；同時權(quán)值指數(shù)α的設(shè)置，使RW算法具有一定的環(huán)境適應(yīng)性，使得RW算法更具靈活性，更能有效的運(yùn)用于定位各類場景當(dāng)中；但是，α的求值，需要進(jìn)行大量的數(shù)據(jù)統(tǒng)計運(yùn)算，使得算法的使用比較的復(fù)雜。下一步的要求就是：權(quán)值指數(shù)α的獲取更加的便捷，同時考慮RW算法應(yīng)用于移動節(jié)點(diǎn)定位。

表2　RW算法與各類算法性能比較

［1］Chintalapudi K，Iyer A P，Padmanabhan V N.Indoor localization with the pain［C］//Proceeding of MobiCom Chicago，Illinois，2010：173-184.

［2］Martin E，Vinyals O，F(xiàn)riedland G，et al.Precise indoor localization using smart phones［C］//Proceedings of ACM Multimedia，F(xiàn)irenze，Italy，2010：787-790.

［3］Tarzia S P，Dinda P A，Dick R P，et al.Indoor localization without infrastructure using the acoustic background spectrum［C］//Proceedings of MobiSys，Bethesda，Maryland，2011：79-81.

［4］張立立，鐘耳順.無線室內(nèi)定位技術(shù)［C］//中國地理信息系統(tǒng)協(xié)會第八屆，北京，2004：996-972.

［5］任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報，2003，14（7）：1282-1291.

［6］容曉峰，楊娜.RSSI位置指紋的定位誤差分析與仿真［J］.西安工業(yè)大學(xué)學(xué)報，2010，30（6）：574-578.

［7］彭宇，王丹.無線傳感器網(wǎng)絡(luò)定位技術(shù)綜述［J］.電子測量與儀器學(xué)報，2011（5）：389-399.

［8］Brunato M，Battiti R.Statistical learning theory for location fingerprinting in wireless LANs［J］.Computer Networks（S1389-1286），2005，47（6）.

［9］Ito S，Kawaguchi N.Bayesian based location estimation system using wireless LAN［C］//Proceedings of the Third InternationalConferenceonPervasiveComputingand CommunicationWorkshops.KauaiIsland，Hawaii，USA：IEEE，2005.

［10］陳永光，李修和.基于信號強(qiáng)度的室內(nèi)定位技術(shù)［J］.電子學(xué)報，2004，32（9）.

［11］Zhao J，Zhang Y.Research on the received signal strength indication location algorithm for RFID systems［C］//International Symposium on CIT，2006：881-885.

［12］李奇.一種基于RSSI相關(guān)系數(shù)的指紋定位技術(shù)方法［J］.廣東通信技術(shù)，2013（3）：29-32.

［13］汪媛卿，梁津垚，宋欣.基于距離權(quán)重的無線指紋定位方法［J］.信息技術(shù)，2013（6）：125-128.

［14］Liang Xiaomei，Gou Xuerong，Liu Yong.Fingerprint-based Location Positioning Using Improved KNN［C］//Proceedings 3rd IEEE International Conference on Network Infrastructure and Digital Conten，IC-NIDC 2012：57-61.

［15］方震，趙湛，郭鵬，等.基于RSSI測距分析［J］.傳感技術(shù)學(xué)報，2007，20（11）：2526-2530.

Indoor localization algorithm research of environmental adaptability based on RSSI-weights.

CHEN Shunming，LI Ping

School of Computer and Telecommunications，Changsha University of Science and Technology，Changsha 410114，China

The localization node received signal strength indication value is one of important element for indoor fingerprint localization technology.This paper through analyzing the characteristic of the localization node received signal strength value，proposes indoor localization based on RSSI-weights algorithm.The raising of improved RSSI-weight calculation formula and the weights index make the localization algorithm have the environmental adaptability，apply more flexible to the actual location scene.After general experiment scene verification，this algorithm has a great improvement in location accuracy.

A

TP393

10.3778/j.issn.1002-8331.1311-0116

陳順明（1988—），男，碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)；李平（1972—），男，教授，碩士生導(dǎo)師，主要研究方向?yàn)榫W(wǎng)絡(luò)與信息安全、無線傳感網(wǎng)和物聯(lián)網(wǎng)。

2013-11-08

2013-12-06

1002-8331（2015）22-0099-05

CNKI網(wǎng)絡(luò)優(yōu)先出版：2014-04-03，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0116.html