馮成旭 劉 忠 程遠國

(海軍工程大學(xué)電子工程學(xué)院 武漢 430033)

1 引言

在無線傳感器網(wǎng)絡(luò)的許多應(yīng)用中,監(jiān)測到事件的位置信息至關(guān)重要,定位技術(shù)是關(guān)鍵的技術(shù)之一。提到定位技術(shù),我們不難想到全球定位系統(tǒng)GPS。但是采用GPS技術(shù)的系統(tǒng),往往用戶節(jié)點能耗高、體積大、成本高,這些特點使得GPS技術(shù)并不適用于低成本自組織的無線傳感器網(wǎng)絡(luò)。因此,無線傳感器網(wǎng)絡(luò)定位已經(jīng)成為當(dāng)今一個很重要的研究方向和熱點問題。

在傳感器網(wǎng)絡(luò)中,定位算法通常劃分為基于距離(range-based)的定位算法和與距離無關(guān)(rangefree)的定位算法[2]?；诰嚯x的定位中,常采用的方法有:基于到達時間 TOA的定位、基于到達時間差TDOA的定位、基于接受信號強度指示RSSI的定位和基于到達角度AOA的定位等。與距離無關(guān)的定位算法主要有:質(zhì)心算法、DV-Hop算法、Amorphous算法、APIT算法等等[1]。其中最常用的是利用錨節(jié)點到未知節(jié)點的RSSI(接受信號強度指示)[4]值來估算未知節(jié)點到錨節(jié)點的距離,從而實現(xiàn)未知節(jié)點的定位,因為它不需要添加任何額外的硬件設(shè)備,只是在現(xiàn)有的硬件基礎(chǔ)上讀取信號的場強值再經(jīng)過數(shù)據(jù)處理和算法實現(xiàn)便可定位。

2 算法原理

2.1 三邊測量法

圖1 三邊測量法

在基于RSSI的定位中,最常見的便是三角形質(zhì)心定位算法[6]和加權(quán)質(zhì)心定位算法[3]。而三角形質(zhì)心定位算法的理論基礎(chǔ)是三邊測量法[1]。如圖1所示。

如圖 1所示,已知A、B、C三個節(jié)點的坐標(biāo)分別是(xa,ya)、(xb,yb)、(xc,yc),D點的坐標(biāo)是(x,y),它們到D點的距離分別為da,db,dc,則它們存在下列關(guān)系:

2.2 三角形質(zhì)心定位法

然而,在實際的基于RSSI距離的定位中,由錨節(jié)點到未知節(jié)點的RSSI值換算出來的距離值并不是精確的,而且由于電磁場信號的衰減,換算出來的這個距離值要大于從未知節(jié)點到錨節(jié)點的實際距離。因此,三邊測量法只是理想狀態(tài)下的模型,然而真實的模型應(yīng)該是如圖2所示。

圖2 三角形質(zhì)心定位算法

如圖2所示,D為未知節(jié)點,A、B、C為錨節(jié)點。分別以通過 A、B、C 到D 的 RSSI值換算出的距離值為半徑作圓。由于D必定在A、B、C相應(yīng)的通信半徑以內(nèi),因此三圓必定會有重疊的區(qū)域,如圖中弧EF、弧FG和弧GE所包圍的區(qū)域就是該重疊區(qū)域。而且,未知節(jié)點D的實際位置必定在該重疊區(qū)域內(nèi)。然后,再對△EFG求質(zhì)心,未知節(jié)點D的位置就是該質(zhì)心的坐標(biāo)。即D的坐標(biāo)為

2.3 改進的算法分析

但是,三角形質(zhì)心定位算法在實際環(huán)境測試中也有諸多不足:

1)三角形質(zhì)心定位算法只適用于理想三角形,即未知節(jié)點的位置在三個參與定位的錨節(jié)點所構(gòu)成的三角形的內(nèi)部如圖3。在實際的環(huán)境中,因為錨節(jié)點是大規(guī)模隨機布放的,因此必定存在一些非理想的三角形的情形并不適用于三角形質(zhì)心定位算法,如圖 4未知節(jié)點并不在錨節(jié)點三角形ABC的內(nèi)部;如圖5,與未知節(jié)點相鄰的3個錨節(jié)點并不能構(gòu)成三角形。在這些非理想三角形的情形下,三角形質(zhì)心定位算法并不適用,如果不予考慮的話必定帶來更嚴(yán)重的誤差。所以,考慮將該算法進行優(yōu)化,在進行三角形質(zhì)心定位算法之前進行理想三角形驗證。驗證未知節(jié)點D是否在由三個錨節(jié)點所構(gòu)成的三角形內(nèi)部,如果不在其內(nèi)部則將該三角形進行舍棄,繼續(xù)尋找,直到找到理想的三角形后再進行三角形質(zhì)心定位算法。

2)三角形質(zhì)心定位算法只是采用了3個錨節(jié)點的RSSI數(shù)據(jù)進行定位,并未利用整個網(wǎng)絡(luò)的數(shù)據(jù),從而造成了有效資源的浪費。而且,當(dāng)這錨節(jié)點因偶然因素造成數(shù)據(jù)失真時,會給定位帶來更大的誤差。因此,考慮將網(wǎng)絡(luò)中更多的理想三角形參與定位,從而給未知節(jié)點一個更準(zhǔn)確的定位。

3)三角形質(zhì)心定位算法并沒有考慮RSSI數(shù)值對距離的影響程度。在實際的無線電傳播路徑損耗模型中,RSSI值的衰減與距離的增加并不是線性關(guān)系。隨著未知節(jié)點到錨節(jié)點距離的增加,由RSSI數(shù)值的偏差產(chǎn)生的換算距離的誤差會迅速增大。因此,考慮在進行定位算法時引入權(quán)重系數(shù)來體現(xiàn)錨節(jié)點對未知節(jié)點位置的影響程度,從而來減小誤差。其基本思想是:RSSI數(shù)值越大的錨節(jié)點,對未知節(jié)點位置的影響力越大。在進行質(zhì)心定位算法時,將每一個決定質(zhì)心的點的坐標(biāo)都乘以一個權(quán)重系數(shù),以此來綜合權(quán)衡計算得出最終的未知節(jié)點位置。

2.4 改進的算法原理

針對第一個問題,理想三角形優(yōu)選的解決方案,最佳莫過于近似三角形內(nèi)點測試法APIT[4]中的核心思想。APIT測試的基本原理如圖6、圖7所示。

假設(shè)存在一個方向,節(jié)點D沿著這個方向移動時會同時接近或者遠離A、B、C三個節(jié)點,那么節(jié)點D位于△ABC之外,如圖7;否則節(jié)點D位于△ABC之內(nèi),如圖6。

而在實際的環(huán)境測試中,如果未知節(jié)點D收到的RSSI數(shù)值在增大,則說明D在遠離錨節(jié)點;反之,如果D收到的RSSI數(shù)值在減小,則說明D在接近錨節(jié)點。

利用APIT算法的核心思想來進行理想三角形的優(yōu)化選擇,可以看到如上圖中的兩種非理想三角形在APIT測試中會得出未知節(jié)點D在△ABC之外,對這種三角形予以舍棄,只保留未知節(jié)點在其內(nèi)部的理想三角形。

對于第二個問題,改進后的算法采用了更多的錨節(jié)點的有效數(shù)據(jù)。對RSSI數(shù)值達到一定門限的錨節(jié)點都認(rèn)為是可以參與定位算法的有效節(jié)點。而RSSI數(shù)值低于這個門限的錨節(jié)點因為會帶來比較大的誤差所以就予以舍棄。

3 算法過程

定位算法的整體流程:

1)收集所有錨節(jié)點到未知節(jié)點的RSSI數(shù)值,并多次采集取其均值。然后,設(shè)定一個RSSI值門限,將RSSI數(shù)值低于這個門限的錨節(jié)點予以舍棄,高于這個門限的錨節(jié)點視為有效節(jié)點,將其數(shù)據(jù)保留。

2)將所有有效節(jié)點按照 RSSI數(shù)值的大小進行降序排序,假設(shè)有n個有效的錨節(jié)點即(R1,R2,R3,…,Rn),這里R1為最大的 RSSI值,Rn為最小的RSSI值。

4)將所有的有效錨節(jié)點所組成的三角形集,進行理想三角形的優(yōu)化選擇。因此,共有個三角形,進行次近似三角形內(nèi)點測試后,將測試結(jié)果為理想的三角形予以保留,非理想的三角形予以舍棄。

5)將保留的理想三角形進行如圖2所示的質(zhì)心定位算法,得出未知節(jié)點第一階段定位的近似位置(xi,yi),共有m組近似位置。

7)將所有的理想三角形的輸出結(jié)果(即未知節(jié)點第一階段定位的近似位置(xi,yi))分別與其相應(yīng)的權(quán)重系數(shù)相乘,進行加權(quán)質(zhì)心定位。最后的輸出結(jié)果就是未知節(jié)點的坐標(biāo)(X,Y),即

4 算法仿真

在Matlab平臺上進行該改進的定位算法仿真。組建一個虛擬的實驗場景,初始條件為無線傳感器網(wǎng)絡(luò)在一個100m*100m的正方形區(qū)域內(nèi)。在此,錨節(jié)點是隨機的分布在這個正方形的區(qū)域內(nèi)的。節(jié)點的有效通信半徑設(shè)定為50m。每次仿真結(jié)果都是通過運行算法100次,然后取平均值得到的。

圖8 仿真結(jié)果分析

由圖 8分析可知,當(dāng)錨節(jié)點數(shù)目較少(10個)的時候,改進的算法對于普通的質(zhì)心定位算法誤差并沒有明顯的提升。但是隨著錨節(jié)點數(shù)目的增加(20個以上),誤差就明顯減小了。

5 結(jié)語

本文提出了一種基于RSSI的改進定位算法。仿真結(jié)果表明,本文算法比傳統(tǒng)的RSSI定位算法有更好的定位精度。將近似三角形內(nèi)點測試的核心思想引入理想三角形的篩選,加權(quán)算法中權(quán)重系數(shù)模型的選擇,都能夠明顯減小定位誤差。但是同時也帶來了算法復(fù)雜度的提高。因此,下一步的工作是研究理想三角形的優(yōu)化選擇機制,以降低算法的復(fù)雜度。以進一步優(yōu)化算法的整體性能,從而得到更好的定位效果。

[1]孫利民,李建中,陳渝,等,無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2005

[2]王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)中的自定位系統(tǒng)和算法[J].軟件學(xué)報,2005,16(5):1148～1157

[3]陳維克,李文峰,首珩,等.基于 RSSI的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].武漢理工大學(xué)學(xué)報(交通科學(xué)與工程版),2006,30(2)

[4]He T,Huang C,Blum B M,et al.Range-free localization schemes for large scale sensor networks[C]//Proc 9th Annual Int'l Conf on M obile Computing and Networking(M obiCom),San Diego,CA.,2003:81～95

[5]趙昭,陳小惠.無線傳感器網(wǎng)絡(luò)中基于RSSI的改進定位算法[J].傳感技術(shù)學(xué)報,2009(3)

[6]林瑋,陳傳峰.基于RSSI的無線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法[J].現(xiàn)代電子技術(shù),2009(2)

[7]周四清,陳銳標(biāo).無線傳感器網(wǎng)絡(luò)APIT定位算法及其改進[J].計算機工程,2009(4)