《電子技術(shù)應用》
您所在的位置:首頁 > 通信與網(wǎng)絡 > 設計應用 > 無線傳感網(wǎng)絡節(jié)點定位算法分析
無線傳感網(wǎng)絡節(jié)點定位算法分析
2016年微型機與應用第21期
史文進,張兢,李冠迪,曾建梅
重慶理工大學 電子信息與自動化學院,重慶 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é)果表明其定位精度明顯提高。
Abstract:
Key words :

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

 ?。ㄖ貞c理工大學 電子信息與自動化學院,重慶 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é)果表明其定位精度明顯提高。

  關(guān)鍵詞:無線傳感器網(wǎng)絡;節(jié)點定位;測距/非測距

0引言

   重慶市教委科學技術(shù)研究項目(KJ1500917) 無線傳感器網(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所示。

圖像 001.png

  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)。

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

  QQ圖片20161207161215.png

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

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

  QQ圖片20161207161218.png

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

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

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

  QQ圖片20161207161222.png

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

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

圖像 002.png

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

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

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

 ?。?)質(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)為:

  QQ圖片20161207161225.png

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

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

  傳統(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中。進一步對此算法進行仿真驗證。

圖像 003.png

3仿真驗證

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

圖像 004.png

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

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

圖像 005.png

  仿真結(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)境選擇合適的定位算法很有必要。

  參考文獻

 ?。?] 邱巖, 趙沖沖, 戴桂蘭. 無線傳感器網(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.

 ?。?] 彭保.無線傳感器網(wǎng)絡移動節(jié)點定位及安全定位技術(shù)研究[D].哈爾濱:哈爾濱工業(yè)大學,2009.

 ?。?] 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.

 ?。?] 涂巧鈴,牟小燕,宋佳. 一種改進的DVHop改進算法[J]. 重慶理工大學學報(自然科學),2014,28(11):84-88.

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

 ?。?] 徐林,傅成華.基于Zigbee的三邊測量算法誤差研究及改進[J].微型機與應用,2012,31(21):68-70.

  


此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。