無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位算法分析*

史文進(jìn)，張 兢，李冠迪,曾建梅

(重慶理工大學(xué) 電子信息與自動(dòng)化學(xué)院，重慶 400054)

?

無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位算法分析*

史文進(jìn)，張 兢，李冠迪,曾建梅

(重慶理工大學(xué) 電子信息與自動(dòng)化學(xué)院，重慶 400054)

節(jié)點(diǎn)定位是無(wú)線傳感網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一，已經(jīng)在軍用、民用方面得到很廣泛的應(yīng)用。探討了國(guó)內(nèi)外無(wú)線傳感網(wǎng)絡(luò)定位技術(shù)現(xiàn)狀，對(duì)無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)做了調(diào)查研究，從錨節(jié)點(diǎn)/無(wú)錨節(jié)點(diǎn)定位、集中式/分布式定位、測(cè)距/非測(cè)距定位算法進(jìn)行闡述，同時(shí)對(duì)各類算法從節(jié)點(diǎn)定位的定位精度、規(guī)模、功耗等不同角度進(jìn)行了對(duì)比。重點(diǎn)探討基于RSSI的質(zhì)心定位算法，并進(jìn)行仿真，結(jié)果表明其定位精度明顯提高。

無(wú)線傳感器網(wǎng)絡(luò)；節(jié)點(diǎn)定位；測(cè)距/非測(cè)距

0 引言

無(wú)線傳感器網(wǎng)絡(luò)(Wireless Senor Network, WSN)是由大量具有數(shù)據(jù)獲取能力、無(wú)線通信傳輸數(shù)據(jù)能力、數(shù)據(jù)處理能力的微型傳感器節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)[1]。在被監(jiān)測(cè)區(qū)域放置成千上萬(wàn)的微型傳感器節(jié)點(diǎn)，節(jié)點(diǎn)之間相互通信，形成一個(gè)以無(wú)線連接傳輸方式的網(wǎng)絡(luò)。借助節(jié)點(diǎn)之間協(xié)作感知或者監(jiān)視外部變化，對(duì)采集的信息進(jìn)行預(yù)處理，同時(shí)通過(guò)基站將數(shù)據(jù)發(fā)送給用戶。

WSN利用其信息獲取和處理技術(shù)，在目標(biāo)偵查跟蹤、目標(biāo)監(jiān)測(cè)定位等相關(guān)領(lǐng)域有廣泛應(yīng)用。例如軍事偵查、生態(tài)環(huán)境監(jiān)測(cè)、目標(biāo)定位、目標(biāo)跟蹤、特殊病人的監(jiān)護(hù)與救護(hù)、幼童位置監(jiān)測(cè)與救護(hù)等。無(wú)線傳感器網(wǎng)絡(luò)的目標(biāo)位置識(shí)別、跟蹤或目標(biāo)定位是指通過(guò)分布區(qū)域內(nèi)節(jié)點(diǎn)的物理坐標(biāo)建立一個(gè)類似于GPS衛(wèi)星定位無(wú)線傳感器網(wǎng)絡(luò)地圖[2]。

1 定位技術(shù)

在WSN中，節(jié)點(diǎn)向周圍鄰居節(jié)點(diǎn)發(fā)送信息，必須確定自身節(jié)點(diǎn)位置。由于網(wǎng)絡(luò)中節(jié)點(diǎn)分布多、規(guī)模大，使得通過(guò)中心基站查詢節(jié)點(diǎn)位置，無(wú)法短時(shí)間內(nèi)完成。WSN中傳感器節(jié)點(diǎn)硬件配置較低，傳統(tǒng)的GPS因用戶成本較高并不適合于WSN定位應(yīng)用[3]。因此，節(jié)點(diǎn)在發(fā)送信息的數(shù)據(jù)中需包含自身的坐標(biāo)信息。另外WSN中節(jié)點(diǎn)定位涉及到定位精度、節(jié)點(diǎn)規(guī)模、容錯(cuò)性和魯棒性、能耗等。平衡定位精度是無(wú)線傳感器網(wǎng)絡(luò)定位的關(guān)鍵[4]。對(duì)于定位技術(shù)有很多種，本文從錨節(jié)點(diǎn)/無(wú)錨節(jié)點(diǎn)、集中式/分布式、測(cè)距/非測(cè)距幾方面進(jìn)行闡述。

1.1 錨節(jié)點(diǎn)算法/無(wú)錨節(jié)點(diǎn)算法

錨節(jié)點(diǎn)定位方式是以錨節(jié)點(diǎn)作為參考節(jié)點(diǎn)。首先估計(jì)未知節(jié)點(diǎn)與錨節(jié)點(diǎn)的距離以及選擇不同要求的算子進(jìn)行未知節(jié)點(diǎn)的坐標(biāo)初始化估計(jì)，最后對(duì)初始的未知節(jié)點(diǎn)的位置進(jìn)行優(yōu)化處理。錨節(jié)點(diǎn)的密度越高，參考節(jié)點(diǎn)越多，定位就越精確。但是由于增加了節(jié)點(diǎn)的數(shù)量，會(huì)導(dǎo)致系統(tǒng)成本增加。

無(wú)錨節(jié)點(diǎn)算法需要?jiǎng)?chuàng)建映射，通過(guò)節(jié)點(diǎn)間的映射關(guān)系估計(jì)測(cè)量節(jié)點(diǎn)間的距離。不同的映射關(guān)系，也會(huì)有不同的精度。有時(shí)是通過(guò)旋轉(zhuǎn)、翻轉(zhuǎn)、平移等創(chuàng)建映射關(guān)系。NISSanka[5]等人提出的算法是一種無(wú)需錨節(jié)點(diǎn)的定位，它是通過(guò)多跳確立一個(gè)映射關(guān)系，得到每個(gè)節(jié)點(diǎn)在坐標(biāo)系中的坐標(biāo)，最后采用質(zhì)量—彈簧模型進(jìn)行迭代優(yōu)化。

1.2 集中式算法與分布式算法

集中式定位算法：定位信息傳送到一個(gè)中心基站，然后進(jìn)行定位計(jì)算。集中式計(jì)算從全局出發(fā)，計(jì)算量和存儲(chǔ)量幾乎沒(méi)有限制，實(shí)現(xiàn)實(shí)時(shí)定位。由于只有一個(gè)基站來(lái)完成計(jì)算，所以導(dǎo)致通信、存儲(chǔ)消耗較大，最終導(dǎo)致電能消耗完，從而無(wú)法實(shí)現(xiàn)長(zhǎng)時(shí)間的實(shí)時(shí)定位。

分布式定位算法：與集中式定位算法對(duì)應(yīng)的一種算法，利用節(jié)點(diǎn)間的通信節(jié)點(diǎn)自行計(jì)算、估計(jì)節(jié)點(diǎn)位置坐標(biāo)。集中式與分布式定位算法的對(duì)比如表1所示。

表1 集中式與分布式定位算法的對(duì)比

1.3 測(cè)距/非測(cè)距定位

1.3.1 基于測(cè)距技術(shù)的定位算法

這類定位算法是通過(guò)測(cè)量節(jié)點(diǎn)之間的距離或者角度進(jìn)行定位。通過(guò)傳感器來(lái)估計(jì)節(jié)點(diǎn)間的距離。常見(jiàn)的基于測(cè)距技術(shù)的定位算法有基于接收信號(hào)強(qiáng)度的算法(Received Signal Strength Indicator, RSSI)、基于信號(hào)到達(dá)時(shí)間的方法(Time of Arrival, TOA)、基于信號(hào)到達(dá)角的方法(Angle of Arrival, AOA)、基于信號(hào)傳輸時(shí)間差的方法(Time Difference of Arrival, TDOA)。

(1)接收信號(hào)強(qiáng)度算法(RSSI)：該方法依據(jù)接收信號(hào)能量強(qiáng)度(RSSI)確定距離，對(duì)通信信道參數(shù)要求較高。根據(jù)已知信號(hào)的發(fā)射功率和節(jié)點(diǎn)接收的信號(hào)功率，就可以測(cè)得節(jié)點(diǎn)間的距離。節(jié)點(diǎn)A到B的信號(hào)強(qiáng)度具體公式如下：

Pr=PtGtGrλ2(4π)2R2L

(1)

其中Pr是節(jié)點(diǎn)B接收信號(hào)強(qiáng)度，Pt是發(fā)射功率，Gt、Gr分別是A、B的天線增益，λ是波長(zhǎng)，R是距離，L是損耗因子。由于信號(hào)傳播的過(guò)程中，受到距離和障礙物的影響，信號(hào)的功率強(qiáng)度隨之衰減，間接影響精度。所以對(duì)于短距離通信可以得到良好的精度。

(2)基于信號(hào)到達(dá)時(shí)間的方法(TOA)：TOA 也稱為TOF(Time of Flight)。這種方法的前提是節(jié)點(diǎn)之間的時(shí)鐘同步，移動(dòng)終端發(fā)射測(cè)量信號(hào)到達(dá)基站，并施以特定算法的計(jì)算,就可以實(shí)現(xiàn)對(duì)移動(dòng)終端的定位。其中距離可以通過(guò)下面的公式計(jì)算：

d=c×Δt

(2)

其中d是節(jié)點(diǎn)之間距離，c是傳播速度，Δt為時(shí)間間隔。

(3)基于信號(hào)到達(dá)角的方法(AOA)：AOA指測(cè)量發(fā)送端和接收端的角度獲得節(jié)點(diǎn)的位置信息最終完成定位。測(cè)量角度是通過(guò)安裝在節(jié)點(diǎn)上的天線陣列，選擇合適的三角測(cè)量術(shù)算法得到的。由于AOA方法需要在接收和發(fā)送兩端安裝天線陣列，其成本和能耗問(wèn)題就會(huì)相應(yīng)提高，所以AOA的實(shí)用性較差。

(4)基于信號(hào)傳輸時(shí)間差的方法(TDOA)：TDOA方法測(cè)量距離是根據(jù)兩波到達(dá)同一目標(biāo)或者不同目標(biāo)的時(shí)間間隔。節(jié)點(diǎn)的距離公式如下:

d=S×Δt

(3)

其中d是節(jié)點(diǎn)之間的距離，Δt是接收時(shí)間間隔，S=(C1×C2)/(C1-C2)，C1和C2是兩種波的傳播速度。

對(duì)于不同的測(cè)距方式，定位算法需要根據(jù)精度要求進(jìn)行選擇，如表2是不同測(cè)距定位算法精度比較。

表2 不同測(cè)距方式定位算法的比較

1.3.2 無(wú)需測(cè)距技術(shù)的算法

此類算法不需要根據(jù)節(jié)點(diǎn)之間的通信距離進(jìn)行定位，由于信息可以通過(guò)多跳方式發(fā)送，利用對(duì)跳數(shù)信息的處理估計(jì)兩個(gè)節(jié)點(diǎn)間的通信距離，再根據(jù)算法得到未知節(jié)點(diǎn)的坐標(biāo)位置。該算法無(wú)需測(cè)距，其優(yōu)點(diǎn)是功耗低、成本低，缺點(diǎn)是定位精度不高。常見(jiàn)的方法有DV-Hop[6]和質(zhì)心定位(Centroid Location, CL)。

(1)DV-Hop：DV-Hop算法是一種基于距離矢量計(jì)算跳數(shù)的算法。DV-Hop算法一般分為三個(gè)步驟：(1)計(jì)算節(jié)點(diǎn)之間的最小跳數(shù)；(2)每個(gè)錨節(jié)點(diǎn)計(jì)算自己的平均跳距；(3)通過(guò)三邊法、極大似然法、最小二乘法[7]等估計(jì)未知節(jié)點(diǎn)的坐標(biāo)。

(2)質(zhì)心算法(CL)：質(zhì)心算法基于網(wǎng)絡(luò)的連通性，以未知節(jié)點(diǎn)周圍的錨節(jié)點(diǎn)作為幾何質(zhì)心，每一個(gè)周期向鄰邊節(jié)點(diǎn)發(fā)送錨節(jié)點(diǎn)的坐標(biāo)信息，最終未知節(jié)點(diǎn)確定為組成多邊形的相對(duì)幾何質(zhì)心，以此估計(jì)未知節(jié)點(diǎn)的位置。設(shè)與未知節(jié)點(diǎn)聯(lián)通的錨節(jié)點(diǎn)的坐標(biāo)為(x1,y1)(x2,y2)…(xn,yn)，則由n個(gè)錨節(jié)點(diǎn)組成的n-1邊的多邊形質(zhì)心(x,y)為：

(4)

該質(zhì)心定位算法相比于加權(quán)質(zhì)心算法和三邊測(cè)量法[8]較為簡(jiǎn)單，但位置錯(cuò)誤率高。

2 基于RSSI的質(zhì)心定位算法

圖1 質(zhì)心算法和RSSI算法結(jié)合

傳統(tǒng)的質(zhì)心定位算法簡(jiǎn)單，可行性高，但定位精度不高，常常定位不到目標(biāo)。為了提高定位精度，提出基于RSSI的質(zhì)心定位算法，使質(zhì)心算法與RSSI相結(jié)合，通過(guò)RSSI的信號(hào)強(qiáng)度轉(zhuǎn)化為傳輸距離，就可以提高定位精度。即鄰居節(jié)點(diǎn)接收到信息后，記錄錨節(jié)點(diǎn)的RSSI值，計(jì)算以錨節(jié)點(diǎn)為圓心的傳輸距離，記錄下以傳輸距離為半徑的所有圓的相交節(jié)點(diǎn)。對(duì)交點(diǎn)采用質(zhì)心算法，就可以估計(jì)未知節(jié)點(diǎn)坐標(biāo)。如圖1所示，A、B、C為錨節(jié)點(diǎn),未知節(jié)點(diǎn)P1必然落在三角形O1O2O3中。進(jìn)一步對(duì)此算法進(jìn)行仿真驗(yàn)證。

3 仿真驗(yàn)證

實(shí)驗(yàn)環(huán)境使用MATLAB2010b版本仿真軟件，在100 m×100 m的區(qū)域，30個(gè)未知節(jié)點(diǎn)隨機(jī)分布，取平均誤差值，比較質(zhì)心定位算法、RSSI定位算法、基于RSSI質(zhì)心定位算法的誤差。仿真結(jié)果如圖2。

圖2 質(zhì)心定位、RSSI定位、基于RSSI質(zhì)心算法的誤差比較

圖2中，實(shí)點(diǎn)是錨節(jié)點(diǎn)，星號(hào)是未知節(jié)點(diǎn)，圓圈是算法估計(jì)位置，連線是定位誤差。結(jié)果表明質(zhì)心算法和RSSI定位算法對(duì)未知節(jié)點(diǎn)的位置估計(jì)特性一般，而基于RSSI質(zhì)心定位算法對(duì)未知節(jié)點(diǎn)的定位效果明顯提高。

改變通信半徑，在不同通信半徑下的基于RSSI質(zhì)心與質(zhì)心定位算法誤差比較，仿真結(jié)果如圖3所示。

圖3 基于RSSI的質(zhì)心算法與單一質(zhì)心算法的比較

仿真結(jié)果表明，基于RSSI質(zhì)心定位優(yōu)化算法要比普通質(zhì)心定位算法誤差小，隨著通信距離的增大，定位誤差逐步減少，并在通信半徑達(dá)到一定值后趨于誤差平穩(wěn)。如果未知移動(dòng)節(jié)點(diǎn)越靠近參考節(jié)點(diǎn)，錨節(jié)點(diǎn)越多，則結(jié)果誤差就越小。

4 結(jié)論

隨著定位技術(shù)的發(fā)展，廉價(jià)無(wú)線定位服務(wù)大眾化趨勢(shì)加劇。對(duì)基于RSSI的質(zhì)心定位算法進(jìn)行仿真表明，其定位精度比傳統(tǒng)的質(zhì)心算法的精度高，且具有低成本、設(shè)備少、距離遠(yuǎn)、易獲取的特點(diǎn)。該算法基本滿足高精度的定位需求，適用于定位精度、發(fā)射效率相對(duì)較高的無(wú)線定位系統(tǒng)。目前，許多算法只適合特定環(huán)境或需要對(duì)條件嚴(yán)格限定，且還有很多問(wèn)題沒(méi)有解決，如耗能、網(wǎng)絡(luò)安全、測(cè)距干擾、定位優(yōu)化、三維定位問(wèn)題等，所以根據(jù)不同定位需求以及定位環(huán)境選擇合適的定位算法很有必要。

[1] 邱巖, 趙沖沖, 戴桂蘭. 無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位技術(shù)研究[J]. 計(jì)算機(jī)科學(xué), 2008, 35(5): 47-50.

[2] KOTWAL S B, VERMA S, ABROL R K. Approaches of self localization in wireless sensor networks and directions in 3D[J]. International Journal of Computer Applications, 2012, 50(11):1-10.

[3] YAN L Q,GIANNAKIS G B. Ultra wide band communications an idea whose time has come [J]. IEEE Signal Processing Magazine, 2005, 21(6):26-54.

[4] 彭保.無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)定位及安全定位技術(shù)研究[D].哈爾濱:哈爾濱工業(yè)大學(xué),2009.[5] PRIYANTHA N B, BALAKRISHNAN H, DEMAINE E, et al. Anchor-free distributed localization in sensor networks[C].Proceedings of the 1st International Conference on Embedded Networked Sensor Systems. ACM, 2003: 340-341.

[6] 涂巧鈴,牟小燕,宋佳. 一種改進(jìn)的DV-Hop改進(jìn)算法[J]. 重慶理工大學(xué)學(xué)報(bào)(自然科學(xué)),2014，28(11):84-88.

[7] 孫利民.無(wú)線傳感器網(wǎng)絡(luò)[M]．北京:清華大學(xué)出版社,2005.

[8] 徐林,傅成華.基于Zigbee的三邊測(cè)量算法誤差研究及改進(jìn)[J].微型機(jī)與應(yīng)用,2012，31(21)：68-70.

Analysis of node localization algorithm for WSN

Shi Wenjin,Zhang Jing,Li Guandi,Zeng Jianmei

(School of Electronic Information and Automation, Chongqing University of Technology, Chongqing 400054, China)

Node localization is one of the key technologies on wireless sensor network，which has been got a wide application in military and civilian areas. WSN node localization is an important research direction. The research on WSN location in home and abroad was investigated in this paper. And the research on wireless sensor network node localization was done. Location algorithms were elaborated from need anchor nodes or not, centralized or distributed, range-free or range-based. While various of algorithms were compared from the location positioning accuracy, scale and power consumption and so on. Moreover, the paper mainly discussed the centroid localization algorithm based on RSSI. And the simulation shows that the positioning accuracy has improved significantly.

Wireless Senor Network (WSN); node localization; range-based/range-free

重慶市基礎(chǔ)與前沿研究計(jì)劃項(xiàng)目(cstc2015jcyjA040055); 重慶市教委科學(xué)技術(shù)研究項(xiàng)目(KJ1500917)

TN911

A

10.19358/j.issn.1674- 7720.2016.21.020

史文進(jìn)，張兢，李冠迪，等. 無(wú)線傳感網(wǎng)絡(luò)節(jié)點(diǎn)定位算法分析[J].微型機(jī)與應(yīng)用，2016,35(21)：65-67,71.

2016-07-13)

史文進(jìn)(1989-)，男，碩士研究生，助教，主要研究方向：無(wú)線傳感網(wǎng)絡(luò)。

張兢(1965-)，女，碩士，教授，主要研究方向：無(wú)線傳感網(wǎng)絡(luò)。