史文進，張 兢，李冠迪,曾建梅

(重慶理工大學 電子信息與自動化學院，重慶 400054)

?

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

史文進，張 兢，李冠迪,曾建梅

(重慶理工大學 電子信息與自動化學院，重慶 400054)

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

無線傳感器網(wǎng)絡；節(jié)點定位；測距/非測距

0 引言

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

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

1 定位技術(shù)

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

1.1 錨節(jié)點算法/無錨節(jié)點算法

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

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

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

集中式定位算法：定位信息傳送到一個中心基站，然后進行定位計算。集中式計算從全局出發(fā)，計算量和存儲量幾乎沒有限制，實現(xiàn)實時定位。由于只有一個基站來完成計算，所以導致通信、存儲消耗較大，最終導致電能消耗完，從而無法實現(xiàn)長時間的實時定位。

分布式定位算法：與集中式定位算法對應的一種算法，利用節(jié)點間的通信節(jié)點自行計算、估計節(jié)點位置坐標。集中式與分布式定位算法的對比如表1所示。

表1 集中式與分布式定位算法的對比

1.3 測距/非測距定位

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

這類定位算法是通過測量節(jié)點之間的距離或者角度進行定位。通過傳感器來估計節(jié)點間的距離。常見的基于測距技術(shù)的定位算法有基于接收信號強度的算法(Received Signal Strength Indicator, RSSI)、基于信號到達時間的方法(Time of Arrival, TOA)、基于信號到達角的方法(Angle of Arrival, AOA)、基于信號傳輸時間差的方法(Time Difference of Arrival, TDOA)。

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

Pr=PtGtGrλ2(4π)2R2L

(1)

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

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

d=c×Δt

(2)

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

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

(4)基于信號傳輸時間差的方法(TDOA)：TDOA方法測量距離是根據(jù)兩波到達同一目標或者不同目標的時間間隔。節(jié)點的距離公式如下:

d=S×Δt

(3)

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

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

表2 不同測距方式定位算法的比較

1.3.2 無需測距技術(shù)的算法

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

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

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

(4)

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

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

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

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

3 仿真驗證

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

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

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

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

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

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

4 結(jié)論

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

[1] 邱巖, 趙沖沖, 戴桂蘭. 無線傳感器網(wǎng)絡節(jié)點定位技術(shù)研究[J]. 計算機科學, 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ǎng)絡移動節(jié)點定位及安全定位技術(shù)研究[D].哈爾濱:哈爾濱工業(yè)大學,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] 涂巧鈴,牟小燕,宋佳. 一種改進的DV-Hop改進算法[J]. 重慶理工大學學報(自然科學),2014，28(11):84-88.

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

[8] 徐林,傅成華.基于Zigbee的三邊測量算法誤差研究及改進[J].微型機與應用,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

重慶市基礎與前沿研究計劃項目(cstc2015jcyjA040055); 重慶市教委科學技術(shù)研究項目(KJ1500917)

TN911

A

10.19358/j.issn.1674- 7720.2016.21.020

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

2016-07-13)

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

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