自適應無線傳感器網絡室內定位算法研究*

周建國 張 鵬 馮 欣

(1)武漢大學測繪學院，武漢 430079 2)精密工程測量和工業測量國家測繪局重點實驗室，武漢430079)

自適應無線傳感器網絡室內定位算法研究*

周建國1，2)張 鵬1，2)馮 欣1，2)

(1)武漢大學測繪學院，武漢 430079 2)精密工程測量和工業測量國家測繪局重點實驗室，武漢430079)

傳統的基于接收信號強度測距定位需要人工建模獲取定位場景的先驗測距模型參數，無法適應復雜及動態變化的環境。利用參考節點之間相互通信為每個參考節點賦予不同的路徑損耗指數的特性，實現了室內定位的自適應和自動化。測試結果表明，與采用單一的測距模型參數相比，該算法提高了定位精度。

無線傳感器網絡;室內定位;接收機;信號強度;路徑損耗指數

1 前言

基于位置的服務(LBS)需要知道用戶的位置坐標，當前，絕大多數的定位都是通過全球衛星定位系統(GPS)實現的。但在室內、地鐵、隧道等場景中，由于接收不到衛星信號導致無法利用GPS確定用戶位置。此時需要尋找GPS的替代產品實現定位。無線傳感器網絡［1］以其低成本、低功耗成為了這些場景中定位的絕佳選擇。

基于接收信號強度(RSSI)的無線傳感器網絡定位只需要具有無線收發功能的傳感器節點，不像基于超聲波、紅外等的定位需要額外的硬件設備支持，進一步減少了設備成本，也使得該方法備受關注。無線室內定位技術主要分為三邊測量法和場景分析法［2］。三邊測量法通過測量未知點到多個已知參考點的距離計算其位置。場景分析法首先采集定位場景內的特征信息，然后在定位階段通過匹配算法確定未知點的坐標。在利用RSSI定位時，無論是三邊測量法還是場景分析法都需要在離線階段人工采集數據建立測距模型或者是特征信息數據庫。如何消除這一前期工作實現定位的自動化并提高定位精度和環境適應性是無線傳感器網絡定位的研究重點。

2 測距模型分析

采用基于RSSI的三邊測量法進行室內定位時，首先需要建立RSSI與距離的關系，即測距模型;然后在定位階段利用該測距模型將RSSI轉換為距離再采用相應的定位算法求取未知點的坐標。

根據自由空間損耗模型［3］可知，接收信號功率(P)和信號傳播路徑長度(d)存在如下關系:

式中，Pt是發射器的發射功率，GT和GR分別是發射器和接收器的天線增益，λc是無線電波長，n是路徑損耗指數。

在距離發射器為d1和d2兩個不同位置測量接收信號功率P1和P2。即可得:

假設發射器和接收器的天線增益GT、GR相同，對式(2)、(3)進行處理，并取信號傳播路徑長度d1=1 m，即可得基于RSSI的測距模型:

式中PR是信號傳播路徑長度為d2時的接收信號強度，單位為dbm，A是距離發射器1 m處的接收信號強度，X是服從(0，δ)的正態分布的觀測誤差。

由測距模型可知，只要知道和路徑損耗指數n，就可以通過測量接收器處的接收信號強度PR求得發射器和接收器之間的距離d2。

在假設發射器和接收器的天線增益GT、GR不變的情況下，A值可以認為與信號路徑無關，僅受發射器的發射功率Pt的影響。故在采用未知節點發送參考節點接收的定位模式時，只需要一個A值。而路徑損耗指數卻受到定位場景內多路徑效應、陰影、衰落以及環境動態變化等的影響。那么在環境復雜及動態變化的定位場景內僅使用同一個路徑損耗指數n是不恰當的。為了提高該測距模型的定位精度，應根據定位場景的情況選取多個不同的路徑損耗指數n。

3 算法分析及實現

傳統的基于RSSI測距模型的定位算法中的測距模型參數是通過人工建模獲取的［4］。對于A值，在天線各向同性的條件下，一般是通過測量距離發射節點1 m處的RSSI然后取平均獲得。路徑損耗指數n采用擬合的方法獲取，即在定位場景內沿某一直線以一定的間隔測量多個RSSI，然后通過對數曲線擬合獲取路徑損耗指數n。或者選取幾個坐標已知的點，通過測量參考節點到這些點的RSSI，再利用它們到參考節點的距離已知這一條件采用線性回歸求取值和值。人工建模獲取模型參數的缺點就是不能實現定位的自動化，且無法適應一些復雜及動態變化的定位場景。也有研究利用參考節點之間通信來獲取測距模型參數［5］，但是在復雜的環境下只使用一個路徑損耗指數是不夠的，要根據參考節點的數量采用多個路徑損耗指數。

3.1 算法描述

在采用WiFi無線接入點定位時，可以給每個無線接入點賦予不同的測距模型參數來提高定位精度［6］。但WiFi節點之間無法相互通信，需要用復雜的算法才能達到其目的，而無線傳感器網絡節點之間沒有這個限制。于是可以充分利用作為參考節點的傳感器節點相互通信來提高定位精度。本算法采用集中式定位模式，即未知節點發送信息參考節點測量RSSI傳送到電腦終端進行處理取得未知節點的坐標(圖1)。集中式計算的優點在于從全局統籌規劃，能夠進行復雜計算，可以獲得相對精確的位置估計［7］。

圖1 集中式定位模式Fig.1 Centralized location model

第一階段，終端發送定位命令，未知節點收到命令后周期性地廣播定位請求信息，處于通信范圍內的參考節點收到該信息后測量RSSI并將數據最終傳回電腦終端。當終端獲得足夠的RSSI數據時則發送命令讓未知節點停止廣播。此時終端雖然獲得了多個未知節點到參考節點的RSSI，但沒有測距模型參數無法將RSSI轉化為距離值，所以也無法實現定位，這時需要利用參考節點相互通信獲取測距模型參數。

第二階段，終端根據RSSI值的大小選取N(N≥4)個參考節點發送其相互通信獲取測距模型參數的命令。這些節點收到命令后開始互發信息。以參考節點i為例，節點i向其他參考節點發送信息，其他參考節點測量該信息的RSSI然后將結果轉發至終端。當收集到足夠的RSSI數據時終端即可計算出節點i的測距模型參數。因為參考節點的坐標已知，則參考節點i到其他參考節點的距離是已知的。即dij已知:

其中，dij是參考節點i到參考節點j的距離。(xi，yi)是節點i(i∈N)的坐標，(xj，yj)是參考節點j(j∈N，j≠i)的坐標。對于參考節點i，根據式(4)的測距模型，設參考節點i的模型參數為Ai和ni，可得:

式中Pj為節點j的RSSI。通過參考節點i到N-1個參考節點的RSSI可以采用線性回歸求出節點i的模型參數為Ai和ni。同理，對于其他參考節點，可采用同樣辦法計算出它們的測距模型參數。由于我們采用的是集中式定位模式，需要的只是多個路徑損耗指數，故此時將這些路徑損耗指數保留，對于A值，我們并不需要。

第三階段，利用第一階段獲取的RSSI求取未知節點的坐標。設未知節點的坐標為(x，y)，與發射功率相關的模型參數為A，可得

式Pi中是未知節點到參考節點i(i∈N)的RSSI，ni為參考節點i的已獲取的路徑損耗指數，(xi，yi)為參考節點i的坐標。由于Pi的觀測誤差服從(0，δ)正態分布，為最小二乘問題。即:

其中:

由于fi(X)并非線性函數，用Gause-Newton法解此非線性最小二乘問題。

1)取初始點X(1)=［A(1)，x(1)，y(1)］，并置精度要求為ε，令k=1;

得到Gause-Newton方向d(k);

4)令X(k+1)=X(k)+d(k);

5)令k=k+1，轉2)。

3.2 精度分析

由Δx和Δy可以計算未知節點的點位真誤差ΔP為:

未知數的協因數陣為:

3.3 算法實現

TinyOS是專為無線傳感器網絡設計的開放源代碼的嵌入式操作系統，該系統及其應用程序采用nesC語言實現［8］。本定位算法在未知節點、參考節點以及基站節點端的程序即采用nesC語言實現。為了獲取未知節點發送信息及參考節點相互通信時接收到的RSSI，需要定義消息數據結構，其中包含發送接收節點的ID及接收到數據包的RSSI，填充這些數據之后利用TinyOS自身的Collection收集協議將其多跳自組織的匯聚到基站節點。當需要發送定位命令或者是參考節點通信的命令時則利用Dissemination分發協議將基站傳遞過來的命令分發給目標節點。基站節點起到了連接計算機終端和傳感器網絡的橋梁作用。計算機終端的命令發送、數據接收以及數據處理程序采用Java語言來實現，充分利用了TinyOS提供的通信接口。具體的定位流圖如圖2所示。

4 測試結果分析

實際的室內定位測試采用的是Crossbow公司生產的IRIS型號傳感器節點［9］。該節點采用符合IEEE802.15.4的Atmel RF230無線收發器和Atmega128l微處理器。實際測試時的節點分布如圖3所示。共采用了5個參考節點，圖中黑色點位為參考節點的位置，為了進行定位誤差分析，一共選取了15個未知點位進行測試，如圖中的白色點所示。參考節點通過相互通信計算得到的各自的路徑損耗指數如表1所示。

圖2 定位流程Fig.2 Positioning flowchart

圖3 測試節點分布Fig.3 Distribution of test nodes

表1 各參考節點的路徑損耗指數Tab.1 Path loss exponent of the reference nodes

先采用每個參考節點的路徑損耗指數作為單一的測距模型參數，計算未知節點坐標并利用預先精確測量的真實坐標計算點位真誤差;然后再給每個參考節點賦予不同路徑損耗指數來計算未知節點坐標并同時計算點位真誤差，最終的誤差分布如圖4所示，圖中粗黑線代表給每個參考節點賦予不同的路徑損耗指數獲得的結果。由圖4可以看出，與采用單一的路徑損耗指數相比，給予每個參考節點賦予不同的路徑損耗指數的確減小了未知節點的點位真誤差。

圖4 未知節點點位真誤差Fig.4 Point true error of unknown nodes

5 總結

通過對無線室內定位的測距模型進行分析，認為在復雜的室內環境下，采用多個不同的路徑損耗指數有利于提高室內定位的精度。同時為了克服傳統的人工建模獲取測距模型參數不能適應變化的環境問題，通過參考節點相互通信在定位時實時獲取多個路徑損耗指數。實際測試結果表明，與采用單一的路徑損耗指數相比，賦予每個參考節點不同的路徑損耗指數的確能夠改善未知節點的定位誤差。

1 任豐原，黃海寧，林闖.無線傳感器網絡［J］.軟件學報，2003，14(7):1 282-1 291.(Ren Fengyuan，Huang Haining and Lin Chuang.Wireless sensor networks［J］.Journal of Software，2003，14(7):1 282-1 291)

2 HightowerJ and Borriello G.Location systems for ubiquitous computing［J］.Computer，2001，34(8):57-66

3 安德烈·戈德史密斯.無線通信［M］.北京:人民郵電出版社，2007.(Andrea Goldsmith.Wireless communication［M］.Beijing:Postsamp;Telecom Press，2007)

4 CC2431 location engine.Application Note AN042［EB/OL］.Texas Instruments，2006.

5 Janire Larranaga and Leire Muguira.An environment adaptive ZigBee-based indoor positioning algorithm［C］.2010 International Conference on Indoor Positioning and Indoor Navigation.2010:1-8.

6 Chintalapudi K，Iye A P and Padmanabhan V N.Indoor localization without the pain［A］.Proceedings of the sixteenth annual international conference on Mobile computing and networking［C］.Chicago，ACM2010:173-184.

7 王福豹，史龍，任豐原.無線傳感器網絡中的自身定位系統和算法［J］.軟件學報，2005，16(5):857-868.(Wang Fubao，Shi Long and Ren Fengyuan.Self-localization systems and algorithms for wireless sensor networks［J］.Journal of Software，2005，16(5):857-868)

8 David Gay，et al.The nesC Language:A holistic approach to networked embedded systems［A］.Proceedings of the ACM SIGPLAN［C］.California:ACM2003:1-11.

9 Crossbow Corporation.MPR/MIB user’s manual［R］.Crossbow Corporation，2007.

STUDY ON ADAPTIVE ALGORITHM FOR WIRELESS SENSOR NETWORK INDOOR POSITIONING

Zhou Jianguo1，2)，Zhang Peng1，2)and Feng Xin1，2)

Indoor positioning by the use of wireless sensor networks is a hot topic for research.The traditional ranging positioning method based on the strength of

signals can not work in complex and dynamic environment because the necessary priori ranging model parameters of the positioning scene can only be obtained through artificial modeling.The current research based on the analysis of ranging models，by attaching different path loss exponents to each reference node through the communication between the reference nodes，achieves the self-adaptation and automation of indoor positioning.The experimental results show that the positioning accuracy is improved with this algorithm compared to the method through single model parameters.

wireless sensor network;indoor position;receiver;signal strength;path loss exponent

1671-5942(2012)02-0074-04

2011-11-03

國家自然科學基金(41074025);武漢大學青年教師資助項目(111172)

周建國，男，1988年生，碩士研究生，主要研究方向為無線傳感器網絡室內定位.E-mail:tinyos@whu.edu.cn

P227

A

(1)School of Geodesy and Geomatics，Wuhan University，Whan 430079 2)The key Lab.of Precise Engineering and Industry Surveying，SBSM，Wuhan 430079)