基于RSSI權值的環境適應型室內定位算法研究

陳順明，李平

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

基于RSSI權值的環境適應型室內定位算法研究

陳順明，李平

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

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

定位節點接收的信號強度指示（RSSI）；權值；環境適應性；室內定位

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

1　基于RSSI指紋庫的室內定位技術

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

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

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

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

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

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

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

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

2　相關研究

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

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

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

3　RW算法介紹

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

3.1權值依據

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

化簡得到：

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

圖1　RSSI值與距離關系

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

3.2權值公式

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

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

圖2　改進型式子與傳統式子誤差比較

再者，由于公式固定，不能針對定位環境進行調整，而使得算法適應性不強。經過對數據的多次對比和分析，最終將RSSI權值公式定義為：

3.3權值指數

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

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

圖3　α與ME之間的關系

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

通過計算得到下面矩陣：

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

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

3.4RW算法計算式

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

3.4.1相關性法計算公式

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

3.4.2歐式距離計算公式

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

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

4　實驗分析

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

4.1實驗場景

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

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

圖4　室內實驗場景布置

4.2實驗過程

（1）采樣節點均勻采集室內各個位置的樣本坐標及RSSI值，并建立樣本指紋數據庫。

（2）定位節點在目標區域內隨機選擇150個位置，測量其坐標及實時RSSI值。

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

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

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

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

4.3權值指數α的確定

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

圖5　關于α的擬合曲線

通過對數據的多次擬合，發現4次多項式函數，最為貼近α與ME之間的數值關系，所以α與ME之間的函數關系可以表示為：

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

4.4算法性能分析

通過上述過程獲得的實驗數據，需要進行比較才能發現其中的差異。將RW算法獲得的各項數據指標與同類算法進行比較。

4.4.1與相關性算法比較

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

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

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

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

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

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

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

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

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

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

5　結論

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

表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，Friedland G，et al.Precise indoor localization using smart phones［C］//Proceedings of ACM Multimedia，Firenze，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］張立立，鐘耳順.無線室內定位技術［C］//中國地理信息系統協會第八屆，北京，2004：996-972.

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

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

［7］彭宇，王丹.無線傳感器網絡定位技術綜述［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］陳永光，李修和.基于信號強度的室內定位技術［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相關系數的指紋定位技術方法［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—），男，碩士研究生，主要研究方向為無線傳感器網絡；李平（1972—），男，教授，碩士生導師，主要研究方向為網絡與信息安全、無線傳感網和物聯網。

2013-11-08

2013-12-06

1002-8331（2015）22-0099-05

CNKI網絡優先出版：2014-04-03，http://www.cnki.net/kcms/doi/10.3778/j.issn.1002-8331.1311-0116.html