基于ＲＳＳＩ的無線傳感器網(wǎng)絡(luò)三角形質(zhì)心定位算法

林　瑋　陳傳峰

摘 要：節(jié)點定位是無線傳感器網(wǎng)絡(luò)中的關(guān)鍵技術(shù)之一?；赗SSI的定位技術(shù)是現(xiàn)階段研究的熱點，為解決RSSI測量方法定位誤差較大的問題，提出一種將RSSI測量方法與三角形質(zhì)心算法相結(jié)合的新型定位算法，該算法用三角形質(zhì)心算法減小RSSI的測量誤差。仿真表明該算法比基于RSSI的三邊測量法定位算法的定位精度有較大提高。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò);定位算法;RSSI;質(zhì)心;三角形質(zhì)心定位算法

中圖分類號：TP393文獻標識碼：B

文章編號：1004 373X(2009)02 180 03

RSSI－based Triangle and Centroid Location in Wireless Sensor Network

LIN Wei,CHEN Chuanfeng

(College of Physics and Information Engineering,Fuzhou University,Fuzhou,350002,China)

Abstract：Node location is one of the key technologies in wireless sensor network.RSSI－based location is a hotspot in nowadays.For resolving biggish error in RSSI－based location,the paper presents a new method of location,RSSI－based triangle and centroid location,using triangle and centroid method to reduce the error of RSSI measurement.Simulation experiments prove that this algorithm can obviously improve the location accuracy compared to trilateration.

Keywords：wireless sensor network;location algorithm;RSSI;centroid;triangle and centroid location algorithm

0 引 言

無線傳感器網(wǎng)絡(luò)是面向事件的監(jiān)測網(wǎng)絡(luò)，對于大多數(shù)應(yīng)用，不知道傳感器位置而感知的數(shù)據(jù)是沒有意義的［1］。實時地確定事件發(fā)生的位置或獲取消息的節(jié)點位置是傳感器網(wǎng)絡(luò)最基本的功能之一，也是提供監(jiān)測事件位置信息的前提，所以定位技術(shù)對傳感器網(wǎng)絡(luò)應(yīng)用的有效性起著關(guān)鍵的作用［2］。

在無線傳感器網(wǎng)絡(luò)中，按節(jié)點位置估測機制，根據(jù)定位過程中是否測量節(jié)點間的實際距離或角度，可分為基于距離(Range－based)的定位算法和距離無關(guān)(Range－free)的定位算法［3］。前者需要測量節(jié)點間的實際距離；后者是利用節(jié)點間的估計距離來計算末知節(jié)點的位置。在基于距離的定位算法中，測量節(jié)點間距離或方位時采用的方法有TOA(Time of Arrival)，TDOA(Time Difference of Arrival)，RSSI(Received Signal Strength Indication)和AOA(Angle of Arrival)。距離無關(guān)的算法主要有質(zhì)心算法、DV－h(huán)op算法等。相比之下，基于距離的定位算法測量精度較高，距離無關(guān)的定位算法對硬件要求較低。

比較各種基于距離的測距算法，TOA需要精確的時鐘同步，TDOA需要節(jié)點配備超聲波收發(fā)裝置，AOA需要有天線陣列或麥克風陣列，這三種算法對硬件要求較高。RSSI技術(shù)主要是用RF信號，而節(jié)點本身就具有無線通信能力，故其是一種低功耗、廉價的測距技術(shù)。

接收信號強度指示RSSI的定位方法，是在已知發(fā)射節(jié)點的發(fā)射信號強度，根據(jù)接收節(jié)點收到的信號強度，計算出信號的傳播損耗，再利用理論和經(jīng)驗?zāi)Ｐ蛯鬏敁p耗轉(zhuǎn)化為距離，最后計算節(jié)點的位置。因為理論和經(jīng)驗?zāi)Ｐ偷墓罍y性質(zhì)，故而RSSI具有較大定位誤差。

基于RSSI技術(shù)，提出一種將RSSI測量方法與三角形質(zhì)心算法相結(jié)合的新型定位算法，該算法用三角形質(zhì)心算法減小RSSI的測量誤差。仿真表明，該算法基于RSSI的三邊測量法

定位算法相比，極大提高了定位精度。

1 國內(nèi)外相關(guān)研究

當無線信號在大氣環(huán)境中傳播時，由于多種因素影響，信號強度會隨著其傳播距離的增加而

衰減。這表明，信號強度變化與傳播距離間存在著某種函數(shù)關(guān)系，且通常情況下傳感節(jié)點均可很容易配置測定接收信號強度的模塊。所以，近年來研究人員開始將RSSI技術(shù)用于傳感器節(jié)點定位中。

目前，對RSSI的研究主要有兩個方面。一是，提高改良傳輸損耗模型，建立更符合實際環(huán)境的數(shù)學(xué)模型；二是，結(jié)合各種測量算法，減小傳輸損耗模型帶來的誤差。這里研究重點在第二個方面。

最早的研究人員使用RSSI加三邊測量法的定位技術(shù)，如文獻［4］中的RADAR室內(nèi)定位系統(tǒng)。

文獻［5］的作者提出采用交疊環(huán)定位的方式，利用包含未知節(jié)點的相互交疊的環(huán)形區(qū)域來定位未知節(jié)點。該方法只是比較相應(yīng)RSSI的大小，并未利用它測距。

文獻［6］提出一種加權(quán)質(zhì)心定位算法，它提出信標節(jié)點影響力的概念，節(jié)點到信號源的距離越近，由RSSI值的偏差產(chǎn)生的絕對距離誤差越小，影響力越大。影響力越大的信標節(jié)點對節(jié)點位置有更大的決定權(quán)。其采用優(yōu)選信標節(jié)點的方式，根據(jù)信標節(jié)點對未知節(jié)點的不同影響力確定加權(quán)因子，以此來提高定位精度。

文獻［7］提出綜合RSSI算法和切圓圓心法的RCM算法，提高了定位精度，仿真表明，在RSSI測距誤差散布達到50％時，定位誤差可降到10％以內(nèi)。

2 基于RSSI的三角形質(zhì)心算法模型

與文獻［6］一樣，該算法針對大規(guī)模隨機散布野外應(yīng)用環(huán)境，這類應(yīng)用大都不需要節(jié)點進行精確定位，只需要知道節(jié)點的大概區(qū)域就可滿足需求，同時要求硬件成本低、定位過程通信開銷小、節(jié)能。

2.1 基于RSSI的定位

RSSI測量，一般利用信號傳播的經(jīng)驗?zāi)Ｐ团c理論模型［2,6］。

對于經(jīng)驗?zāi)Ｐ?，在實際定位前，先選取若干測試點，記錄在這些點各基站收到的信號強度，建立各個點上的位置和信號強度關(guān)系的離線數(shù)據(jù)庫(x,y,ss1,ss2,ss3)。在實際定位時，根據(jù)測得的信號強度(ss1′,ss2′,ss3′)和數(shù)據(jù)庫中記錄的信號強度進行比較，信號強度均方差最小的那個點的坐標作為節(jié)點的坐標。

對于理論模型，常采用無線電傳播路徑損耗模型進行分析［8－10］。常用的傳播路徑損耗模型有：自由空間傳播模型、對數(shù)距離路徑損耗模型、哈它模型、對數(shù)－常態(tài)分布模型等。自由空間無線電傳播路徑損耗模型為：

Loss=32.44+10klog10 d+10klog10 f(1)

式中，d為距信源的距離，單位為km；f為頻率，單位為MHz；k為路徑衰減因子。其他的模型模擬現(xiàn)實環(huán)境，但與現(xiàn)實環(huán)境還是有一定的差距。比如對數(shù)－常態(tài)分布模型，其路徑損耗的計算公式為：

PL(d)=PL===(d0)+10klog(d/d0)+Xσ(2)

式中，Xσ是平均值為0的高斯分布隨機變數(shù)，其標準差范圍為4~10；k的范圍在2~5之間。取d＝1，代入式（1）可得，Loss，即PL===(d0)的值。此時各未知節(jié)點接收錨節(jié)點信號時的信號強度為：

RSSI＝發(fā)射功率＋天線增益－路徑損耗（PL(d)）

2.2 基于RSSI的三角形質(zhì)心定位算法的數(shù)學(xué)模型

不論哪種模型，計算出的接收信號強度總與實際情況下有誤差，因為實際環(huán)境的復(fù)雜性，換算出的錨節(jié)點到未知節(jié)點的距離d總是大于實際兩節(jié)點間的距離。如圖1所示，錨節(jié)點A，B，C，未知節(jié)點D，根據(jù)RSSI模型計算出的節(jié)點A和D的距離為r瑼 ；節(jié)點B和D的距離為r瑽 ；節(jié)點C和D的距離為r瑿。分別以A，B，C為圓心；r瑼 ，r瑽 ，r瑿 為半徑畫圓，可得交疊區(qū)域。這里的三角形質(zhì)心定位算法的基本思想是：計算三圓交疊區(qū)域的3個特征點的坐標，以這三個點為三角形的頂點，未知點即為三角形質(zhì)心，如圖2所示，特征點為E，F(xiàn)，G，特征點E點的計算方法為：

(x璭－x璦)2+(y璭－y璦)2≤r璦

(x璭－x璪)2+(y璭－y璪)2=r璪

(x璭－x璫)2+(y璭－y璫)2=r璫（3）

同理，可計算出F，G，此時未知點的坐標為x璭+x璮+x璯3，y璭+y璮+y璯3。由仿真得，在圖2中，實際點為D；三角形質(zhì)心算法出的估計點為M；三邊測量法算出的估計點為N?？芍切钨|(zhì)心算法的準確度更高。

圖1 三個有交集的圖

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

3 基于RSSI的三角形質(zhì)心算法過程

3.1 步驟

（1） 錨節(jié)點周期性向周圍廣播信息，信息中包括自身節(jié)點ID及坐標。普通節(jié)點收到該信息后，對同一錨節(jié)點的RSSI取均值。

（2） 當普通節(jié)點收集到一定數(shù)量的錨節(jié)點信息時，不再接收新信息。普通節(jié)點根據(jù)RSSI從強到弱對錨節(jié)點排序，并建立RSSI值與節(jié)點到錨節(jié)點距離的映射。建立3個集合。

錨節(jié)點集合：

B_set={a1，a2，…，a璶}

未知節(jié)點到錨節(jié)點距離集合：

D_set={d1，d2，…，d璶}，d1＜d2＜…d璶

錨節(jié)點位置集合：

P_set={(X1，Y₁)，(X2，Y2)，…，(X璶，Y璶)}

（3） 選取RSSI值大的前幾個錨節(jié)點進行自身定位計算［4］。

在B_set中優(yōu)先選擇RSSI值大的信標節(jié)點組合成下面的錨節(jié)點集合，這是提高定位精度的關(guān)鍵。

T_set={(a1,a2,a3),(a1,a2,a4),…,

(a1,a3,a4),(a1,a3,a5)…}

對錨節(jié)點集合，依次根據(jù)（3）式算出3個交點的坐標，最后由質(zhì)心算法，得出未知節(jié)點坐標。

（4） 對求出的未知節(jié)點坐標集合取平均，得未知節(jié)點坐標。

3.2 誤差定義

定義定位誤差為ER，假設(shè)得到的未知節(jié)點的坐標為(x璵,y璵)，其真實位置為(x,y)，則定位誤差ER為：

ER=(x璵－x)2+(y璵－y)2

4 仿 真

利用Matlab仿真工具模擬三角形質(zhì)心算法，考察該算法的性能。假設(shè)在100 m×100 m的正方形區(qū)域內(nèi)，36個錨節(jié)點均勻分布，未知節(jié)點70個，分別用三邊測量法［2］和三角形質(zhì)心定位算法進行仿真，仿真結(jié)果如圖3所示。由圖3可知，三角形質(zhì)心算法比三邊測量法，定位精度更高，當測距誤差變大時，用三角形質(zhì)心算法得出的平均定位誤差比用三邊測量法得出的小得多。

5 結(jié) 語

在此提出了將RSSI方法和三角形質(zhì)心定位算法相結(jié)合的方法，通過仿真實驗，將該算法和三邊測量算法相比較，證明了該算法的優(yōu)越性。下一步將研究在錨節(jié)點數(shù)量不同時的平均定位誤差。

圖3 平均定位誤差

參考文獻

［1］Rabacy J J,Ammer M J,da Silva Jr J L,et al.Picorodio Supports Ad Hoc Ultra－low Power Wireless Networking ［J］.Computer,2000,33(7):42－48.

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

［3］He T,Huang C D,Blum B M,et al.Range－Free Localization Schemes in Large Scale Sensor Networks［A］.In:Proc.of the 9th Annual Int′l Conf.on Mobile Computing and Networking.San Diego: ACM Press,2003:81－95.

［4］Elson J,Griod L,Esrein D.Fine－grained Network Time Synchronization Using Reference Broadcasts.In:Proc.5th Symp.Operating Systems Design and Implementation (OSDI 2002).Boston,MA.2002.

［5］Liu Chong,Wu Kui,He Tian.Sensor Localization with Ring Overlapping Based on Comparison of Received Signal Strength Indicator［A］.2004 IEEE International Conference on Mobile Ad－Hoc and Sensor Systems.2004.

［6］陳維克,李文鋒,首珩,等.基于RSSI的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法［J］.武漢理工大學(xué)學(xué)報，2006,20(12):2 695－2 700.

［7］鄧宏彬,賈云得,劉書華,等.一種基于無線傳感器網(wǎng)絡(luò)的星球漫游機器人定位算法［J］.機器人，2007(4):384－389.

［8］汪煬.無線傳感器網(wǎng)絡(luò)定位技術(shù)研究［D］.合肥：中國科學(xué)技術(shù)大學(xué),2007.

［9］余義斌.傳感器網(wǎng)絡(luò)定位算法及相關(guān)技術(shù)研究［D］.重慶：重慶大學(xué),2006.

［10］端木慶敏.無線傳感器網(wǎng)絡(luò)節(jié)點定位算法研究［D］.長沙：國防科學(xué)技術(shù)大學(xué),2006.

作者簡介 林 瑋 女，1982年出生，福建福清人，碩士研究生。主要研究方向為無線傳感器網(wǎng)絡(luò)。

陳傳峰 男，1963年出生，福建福州人，副教授，研究生導(dǎo)師。主要研究方向為計算機網(wǎng)絡(luò)，無線傳感器網(wǎng)絡(luò)。