自適應(yīng)無線傳感器網(wǎng)絡(luò)室內(nèi)定位算法研究*

周建國(guó) 張 鵬 馮 欣

(1)武漢大學(xué)測(cè)繪學(xué)院，武漢 430079 2)精密工程測(cè)量和工業(yè)測(cè)量國(guó)家測(cè)繪局重點(diǎn)實(shí)驗(yàn)室，武漢430079)

自適應(yīng)無線傳感器網(wǎng)絡(luò)室內(nèi)定位算法研究*

周建國(guó)1，2)張 鵬1，2)馮 欣1，2)

(1)武漢大學(xué)測(cè)繪學(xué)院，武漢 430079 2)精密工程測(cè)量和工業(yè)測(cè)量國(guó)家測(cè)繪局重點(diǎn)實(shí)驗(yàn)室，武漢430079)

傳統(tǒng)的基于接收信號(hào)強(qiáng)度測(cè)距定位需要人工建模獲取定位場(chǎng)景的先驗(yàn)測(cè)距模型參數(shù)，無法適應(yīng)復(fù)雜及動(dòng)態(tài)變化的環(huán)境。利用參考節(jié)點(diǎn)之間相互通信為每個(gè)參考節(jié)點(diǎn)賦予不同的路徑損耗指數(shù)的特性，實(shí)現(xiàn)了室內(nèi)定位的自適應(yīng)和自動(dòng)化。測(cè)試結(jié)果表明，與采用單一的測(cè)距模型參數(shù)相比，該算法提高了定位精度。

無線傳感器網(wǎng)絡(luò);室內(nèi)定位;接收機(jī);信號(hào)強(qiáng)度;路徑損耗指數(shù)

1 前言

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

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

2 測(cè)距模型分析

采用基于RSSI的三邊測(cè)量法進(jìn)行室內(nèi)定位時(shí)，首先需要建立RSSI與距離的關(guān)系，即測(cè)距模型;然后在定位階段利用該測(cè)距模型將RSSI轉(zhuǎn)換為距離再采用相應(yīng)的定位算法求取未知點(diǎn)的坐標(biāo)。

根據(jù)自由空間損耗模型［3］可知，接收信號(hào)功率(P)和信號(hào)傳播路徑長(zhǎng)度(d)存在如下關(guān)系:

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

在距離發(fā)射器為d1和d2兩個(gè)不同位置測(cè)量接收信號(hào)功率P1和P2。即可得:

假設(shè)發(fā)射器和接收器的天線增益GT、GR相同，對(duì)式(2)、(3)進(jìn)行處理，并取信號(hào)傳播路徑長(zhǎng)度d1=1 m，即可得基于RSSI的測(cè)距模型:

式中PR是信號(hào)傳播路徑長(zhǎng)度為d2時(shí)的接收信號(hào)強(qiáng)度，單位為dbm，A是距離發(fā)射器1 m處的接收信號(hào)強(qiáng)度，X是服從(0，δ)的正態(tài)分布的觀測(cè)誤差。

由測(cè)距模型可知，只要知道和路徑損耗指數(shù)n，就可以通過測(cè)量接收器處的接收信號(hào)強(qiáng)度PR求得發(fā)射器和接收器之間的距離d2。

在假設(shè)發(fā)射器和接收器的天線增益GT、GR不變的情況下，A值可以認(rèn)為與信號(hào)路徑無關(guān)，僅受發(fā)射器的發(fā)射功率Pt的影響。故在采用未知節(jié)點(diǎn)發(fā)送參考節(jié)點(diǎn)接收的定位模式時(shí)，只需要一個(gè)A值。而路徑損耗指數(shù)卻受到定位場(chǎng)景內(nèi)多路徑效應(yīng)、陰影、衰落以及環(huán)境動(dòng)態(tài)變化等的影響。那么在環(huán)境復(fù)雜及動(dòng)態(tài)變化的定位場(chǎng)景內(nèi)僅使用同一個(gè)路徑損耗指數(shù)n是不恰當(dāng)?shù)?。為了提高該測(cè)距模型的定位精度，應(yīng)根據(jù)定位場(chǎng)景的情況選取多個(gè)不同的路徑損耗指數(shù)n。

3 算法分析及實(shí)現(xiàn)

傳統(tǒng)的基于RSSI測(cè)距模型的定位算法中的測(cè)距模型參數(shù)是通過人工建模獲取的［4］。對(duì)于A值，在天線各向同性的條件下，一般是通過測(cè)量距離發(fā)射節(jié)點(diǎn)1 m處的RSSI然后取平均獲得。路徑損耗指數(shù)n采用擬合的方法獲取，即在定位場(chǎng)景內(nèi)沿某一直線以一定的間隔測(cè)量多個(gè)RSSI，然后通過對(duì)數(shù)曲線擬合獲取路徑損耗指數(shù)n?；蛘哌x取幾個(gè)坐標(biāo)已知的點(diǎn)，通過測(cè)量參考節(jié)點(diǎn)到這些點(diǎn)的RSSI，再利用它們到參考節(jié)點(diǎn)的距離已知這一條件采用線性回歸求取值和值。人工建模獲取模型參數(shù)的缺點(diǎn)就是不能實(shí)現(xiàn)定位的自動(dòng)化，且無法適應(yīng)一些復(fù)雜及動(dòng)態(tài)變化的定位場(chǎng)景。也有研究利用參考節(jié)點(diǎn)之間通信來獲取測(cè)距模型參數(shù)［5］，但是在復(fù)雜的環(huán)境下只使用一個(gè)路徑損耗指數(shù)是不夠的，要根據(jù)參考節(jié)點(diǎn)的數(shù)量采用多個(gè)路徑損耗指數(shù)。

3.1 算法描述

在采用WiFi無線接入點(diǎn)定位時(shí)，可以給每個(gè)無線接入點(diǎn)賦予不同的測(cè)距模型參數(shù)來提高定位精度［6］。但WiFi節(jié)點(diǎn)之間無法相互通信，需要用復(fù)雜的算法才能達(dá)到其目的，而無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)之間沒有這個(gè)限制。于是可以充分利用作為參考節(jié)點(diǎn)的傳感器節(jié)點(diǎn)相互通信來提高定位精度。本算法采用集中式定位模式，即未知節(jié)點(diǎn)發(fā)送信息參考節(jié)點(diǎn)測(cè)量RSSI傳送到電腦終端進(jìn)行處理取得未知節(jié)點(diǎn)的坐標(biāo)(圖1)。集中式計(jì)算的優(yōu)點(diǎn)在于從全局統(tǒng)籌規(guī)劃，能夠進(jìn)行復(fù)雜計(jì)算，可以獲得相對(duì)精確的位置估計(jì)［7］。

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

第一階段，終端發(fā)送定位命令，未知節(jié)點(diǎn)收到命令后周期性地廣播定位請(qǐng)求信息，處于通信范圍內(nèi)的參考節(jié)點(diǎn)收到該信息后測(cè)量RSSI并將數(shù)據(jù)最終傳回電腦終端。當(dāng)終端獲得足夠的RSSI數(shù)據(jù)時(shí)則發(fā)送命令讓未知節(jié)點(diǎn)停止廣播。此時(shí)終端雖然獲得了多個(gè)未知節(jié)點(diǎn)到參考節(jié)點(diǎn)的RSSI，但沒有測(cè)距模型參數(shù)無法將RSSI轉(zhuǎn)化為距離值，所以也無法實(shí)現(xiàn)定位，這時(shí)需要利用參考節(jié)點(diǎn)相互通信獲取測(cè)距模型參數(shù)。

第二階段，終端根據(jù)RSSI值的大小選取N(N≥4)個(gè)參考節(jié)點(diǎn)發(fā)送其相互通信獲取測(cè)距模型參數(shù)的命令。這些節(jié)點(diǎn)收到命令后開始互發(fā)信息。以參考節(jié)點(diǎn)i為例，節(jié)點(diǎn)i向其他參考節(jié)點(diǎn)發(fā)送信息，其他參考節(jié)點(diǎn)測(cè)量該信息的RSSI然后將結(jié)果轉(zhuǎn)發(fā)至終端。當(dāng)收集到足夠的RSSI數(shù)據(jù)時(shí)終端即可計(jì)算出節(jié)點(diǎn)i的測(cè)距模型參數(shù)。因?yàn)閰⒖脊?jié)點(diǎn)的坐標(biāo)已知，則參考節(jié)點(diǎn)i到其他參考節(jié)點(diǎn)的距離是已知的。即dij已知:

其中，dij是參考節(jié)點(diǎn)i到參考節(jié)點(diǎn)j的距離。(xi，yi)是節(jié)點(diǎn)i(i∈N)的坐標(biāo)，(xj，yj)是參考節(jié)點(diǎn)j(j∈N，j≠i)的坐標(biāo)。對(duì)于參考節(jié)點(diǎn)i，根據(jù)式(4)的測(cè)距模型，設(shè)參考節(jié)點(diǎn)i的模型參數(shù)為Ai和ni，可得:

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

第三階段，利用第一階段獲取的RSSI求取未知節(jié)點(diǎn)的坐標(biāo)。設(shè)未知節(jié)點(diǎn)的坐標(biāo)為(x，y)，與發(fā)射功率相關(guān)的模型參數(shù)為A，可得

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

其中:

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

1)取初始點(diǎn)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，轉(zhuǎn)2)。

3.2 精度分析

由Δx和Δy可以計(jì)算未知節(jié)點(diǎn)的點(diǎn)位真誤差ΔP為:

未知數(shù)的協(xié)因數(shù)陣為:

3.3 算法實(shí)現(xiàn)

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

4 測(cè)試結(jié)果分析

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

圖2 定位流程Fig.2 Positioning flowchart

圖3 測(cè)試節(jié)點(diǎn)分布Fig.3 Distribution of test nodes

表1 各參考節(jié)點(diǎn)的路徑損耗指數(shù)Tab.1 Path loss exponent of the reference nodes

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

圖4 未知節(jié)點(diǎn)點(diǎn)位真誤差Fig.4 Point true error of unknown nodes

5 總結(jié)

通過對(duì)無線室內(nèi)定位的測(cè)距模型進(jìn)行分析，認(rèn)為在復(fù)雜的室內(nèi)環(huán)境下，采用多個(gè)不同的路徑損耗指數(shù)有利于提高室內(nèi)定位的精度。同時(shí)為了克服傳統(tǒng)的人工建模獲取測(cè)距模型參數(shù)不能適應(yīng)變化的環(huán)境問題，通過參考節(jié)點(diǎn)相互通信在定位時(shí)實(shí)時(shí)獲取多個(gè)路徑損耗指數(shù)。實(shí)際測(cè)試結(jié)果表明，與采用單一的路徑損耗指數(shù)相比，賦予每個(gè)參考節(jié)點(diǎn)不同的路徑損耗指數(shù)的確能夠改善未知節(jié)點(diǎn)的定位誤差。

1 任豐原，黃海寧，林闖.無線傳感器網(wǎng)絡(luò)［J］.軟件學(xué)報(bào)，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 王福豹，史龍，任豐原.無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法［J］.軟件學(xué)報(bào)，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

國(guó)家自然科學(xué)基金(41074025);武漢大學(xué)青年教師資助項(xiàng)目(111172)

周建國(guó)，男，1988年生，碩士研究生，主要研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)室內(nèi)定位.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)