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

陳順明，李平

長沙理工大學計算機與通信工程學院，長沙410114

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

陳順明，李平

長沙理工大學計算機與通信工程學院，長沙410114

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

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

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

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

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

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

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

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

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

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

最后，通過質(zhì)心計算得到定位點的定位坐標：

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

2　相關研究

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

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

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

3　RW算法介紹

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

3.1權值依據(jù)

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

化簡得到：

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

圖1　RSSI值與距離關系

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

3.2權值公式

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

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

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

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

3.3權值指數(shù)

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

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

圖3　α與ME之間的關系

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

通過計算得到下面矩陣：

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

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

3.4RW算法計算式

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

3.4.1相關性法計算公式

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

3.4.2歐式距離計算公式

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

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

4　實驗分析

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

4.1實驗場景

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

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

圖4　室內(nèi)實驗場景布置

4.2實驗過程

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

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

（3）利用公式（7）和（8）分別進行匹配定位計算并得到定位點估計坐標。

（4）求出定位點的估計坐標和定位點坐標之間的誤差。

（5）分析各項性能指標。

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

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

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

圖5　關于α的擬合曲線

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

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

4.4算法性能分析

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

4.4.1與相關性算法比較

在相關性法的計算公式（2）的基礎上提出的加入RSSI權值計算的式子（7），通過此式，RW算法可以用于RSSI相關性算法中，運用式子（7）計算后得到的結果與相關性法進行比較，如圖6所示。

圖6　RW算法與相關性法比較

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

表1　RW算法與相關性算法各項性能比較

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

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

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

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

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

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

5　結論

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

表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)定位技術［C］//中國地理信息系統(tǒng)協(xié)會第八屆，北京，2004：996-972.

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

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

［7］彭宇，王丹.無線傳感器網(wǎng)絡定位技術綜述［J］.電子測量與儀器學報，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］陳永光，李修和.基于信號強度的室內(nèi)定位技術［J］.電子學報，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相關系數(shù)的指紋定位技術方法［J］.廣東通信技術，2013（3）：29-32.

［13］汪媛卿，梁津垚，宋欣.基于距離權重的無線指紋定位方法［J］.信息技術，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］.傳感技術學報，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—），男，碩士研究生，主要研究方向為無線傳感器網(wǎng)絡；李平（1972—），男，教授，碩士生導師，主要研究方向為網(wǎng)絡與信息安全、無線傳感網(wǎng)和物聯(lián)網(wǎng)。

2013-11-08

2013-12-06

1002-8331（2015）22-0099-05

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