WSN中基于RSSI的加權(quán)質(zhì)心定位算法的改進(jìn)

于慧霞

（南京郵電大學(xué) 南京 210046）

0 引言

在無線傳感器網(wǎng)絡(luò)中，按節(jié)點(diǎn)位置估測機(jī)制，根據(jù)是否依靠測量距離劃分為基于測距(range-based)的算法和非基于測距(range-free)的算法。前者是利用測量得到的距離或角度信息來進(jìn)行位置計(jì)算，而后者一般是利用節(jié)點(diǎn)的連通性和多跳路由信息交換等方法來估計(jì)節(jié)點(diǎn)間的距離或角度，并完成位置估算。

文獻(xiàn)[6]提出了一種廉價(jià)實(shí)用的定位算法，該方法通過校正RSSI測距技術(shù)測量節(jié)點(diǎn)間的距離，并優(yōu)選信標(biāo)節(jié)點(diǎn)，最后用加權(quán)質(zhì)心方法進(jìn)行定位，該方法存在的缺點(diǎn)是在加權(quán)權(quán)重階段沒有對權(quán)值進(jìn)行更好的選取；文獻(xiàn)[7]提出了一種基于RSSI的修正加權(quán)質(zhì)心定位算法，在該算法中采用測試距離倒數(shù)之和來代替距離和的倒數(shù)作為權(quán)重， 該算法對于質(zhì)心算法的權(quán)值進(jìn)行了很好的修正，但是在測距階段沒有充分考慮到信標(biāo)節(jié)點(diǎn)的影響力，使得RSSI測距值存在著很大的誤差。

本文融合文獻(xiàn)[6]和文獻(xiàn)[7]中算法的優(yōu)點(diǎn)，并彌補(bǔ)兩種算法中的不足，在基于校正RSSI測距的基礎(chǔ)上，通過優(yōu)選信標(biāo)節(jié)點(diǎn)，最后采用修正加權(quán)權(quán)重的方法來對傳統(tǒng)的質(zhì)心定位算法進(jìn)行改進(jìn)。

1 算法模型

1.1 無線信號傳播損耗模型

在基于接收信號強(qiáng)度指示RSSI的定位中，已知發(fā)射節(jié)點(diǎn)的發(fā)射信號強(qiáng)度，接收節(jié)點(diǎn)根據(jù)收到信號的強(qiáng)度，計(jì)算出信號的傳播損耗，利用理論和經(jīng)驗(yàn)?zāi)Ｐ蛯鬏敁p耗轉(zhuǎn)化為距離，再利用已有的算法計(jì)算出節(jié)點(diǎn)的位置。

一般地，在實(shí)際應(yīng)用環(huán)境中，無線傳感器網(wǎng)絡(luò)模擬的傳播模型我們考慮最多的就是綜合性強(qiáng)并被廣泛應(yīng)用的Shadowing模型。

完整的Shadowing模型如下：

該模型包含兩個(gè)部分，第一部分是路徑損失模型（pass loss），它預(yù)測出當(dāng)給定距離d0（一般取1 m）和接收信號強(qiáng)度pr(d0)作為參考時(shí)，距離d時(shí)的信號強(qiáng)度pr(d)。

其中，β是衰減指數(shù)，它通常是由場地測量得來的經(jīng)驗(yàn)值，范圍一般在2～6之間。障礙物越多相對數(shù)值越大。因此隨著距離的增加接收到的平均能量下降的速度會越來越快。

Shadowing模型的第二部分XdB是一個(gè)對數(shù)正態(tài)的隨機(jī)變量，它反映了當(dāng)距離一定時(shí)，接收到能量變化。如果以dB作為計(jì)量單位時(shí)，它滿足高斯分布。它是一個(gè)沒有任何意義的高斯隨機(jī)變量，它對Shadowing模型作了一個(gè)擴(kuò)展，使之成為一個(gè)富有統(tǒng)計(jì)學(xué)的模型，本文出于環(huán)境復(fù)雜性的考慮，將使用Shadowing的完整模型，即將一個(gè)零均值高斯分布的隨機(jī)噪聲引入了無線電傳播模型中，該噪聲分布服從對數(shù)正態(tài)分布。

1.2 傳統(tǒng)的質(zhì)心定位算法模型

質(zhì)心算法[3-4]是由南加州大學(xué)的Bulusu等人提出，在未知節(jié)點(diǎn)收到鄰居信標(biāo)節(jié)點(diǎn)的位置信息后，取這些鄰居信標(biāo)節(jié)點(diǎn)的質(zhì)心作為該節(jié)點(diǎn)的估計(jì)位置。傳統(tǒng)的質(zhì)心算法（Centroid Algorithm）是一種基于連接性的，而無需距離信息的簡單定位算法。傳統(tǒng)的質(zhì)心算法的基本原理如圖1所示。

圖1 質(zhì)心定位算法的示意圖

在質(zhì)心算法中，信標(biāo)節(jié)點(diǎn)周期性地向鄰近節(jié)點(diǎn)廣播信標(biāo)分組，信標(biāo)分組中包含信標(biāo)節(jié)點(diǎn)的標(biāo)識號和位置信息。當(dāng)未知節(jié)點(diǎn)接收到來自不同信標(biāo)節(jié)點(diǎn)的信標(biāo)分組數(shù)量超過某一個(gè)門限或接收一定時(shí)間后，就確定自身位置為這些信標(biāo)節(jié)點(diǎn)所組成的多邊形的質(zhì)心：為未知節(jié)點(diǎn)能夠接收到其分組的信標(biāo)節(jié)點(diǎn)坐標(biāo)。

通過對無線電傳播路徑損耗模型的分析，可以發(fā)現(xiàn)普通質(zhì)心算法沒有反映出信標(biāo)節(jié)點(diǎn)對節(jié)點(diǎn)位置的影響力大小，影響了定位精度。理論證明，利用節(jié)點(diǎn)之間的距離信息（接收信號強(qiáng)度指示RSSI），可獲得定位信標(biāo)節(jié)點(diǎn)的偏移權(quán)值，從而可以提高質(zhì)心定位算法的精度。在基于RSSI的定位算法中，通常有普通的質(zhì)心定位算法，加權(quán)質(zhì)心定位算法、三角形面積定位算法等。這些模型中，普通的質(zhì)心定位算法最簡單，但定位精度較低，使用較少。一般來說，已知無線傳感器網(wǎng)絡(luò)的N個(gè)固定信標(biāo)節(jié)點(diǎn)Bi的位置坐標(biāo)（xi，yi），其中1≤i≤N，未知節(jié)點(diǎn)O的估計(jì)位置坐標(biāo)為（x，y），那么基于RSSI的加權(quán)質(zhì)心定位算法計(jì)算公式為：

其中，wi表示每個(gè)固定信標(biāo)節(jié)點(diǎn)的權(quán)值，通常，該權(quán)值是未知節(jié)點(diǎn)到固定信標(biāo)節(jié)點(diǎn)的距離函數(shù)的倒數(shù)。特殊情況下，如果未知節(jié)點(diǎn)不能與固定信標(biāo)節(jié)點(diǎn)Bi通信，那么權(quán)值為零。

2 基于傳統(tǒng)模型的改進(jìn)算法模型

2.1 RSSI值校正模型-基于固定信標(biāo)節(jié)點(diǎn)間距離的校正模型

如圖2所示，假設(shè)o點(diǎn)是未知節(jié)點(diǎn)，Bi，Bj都是已知自身位置的錨節(jié)點(diǎn)。未知節(jié)點(diǎn)o到Bi的距離表示為doi，固定錨節(jié)點(diǎn)Bi和Bj之間的距離表示為dij.未知節(jié)點(diǎn)o接收到錨節(jié)點(diǎn)Bi信號的信號強(qiáng)度平均值為Poi（mW）。固定錨節(jié)點(diǎn)Bi接收到Bj的信號強(qiáng)度平均值（mW）為Pij，由上述式子（1）可知，它們之間存在著如下的關(guān)系：

又假設(shè)RSSI0i為未知節(jié)點(diǎn)A接收到錨節(jié)點(diǎn)Bi信號的RSSI平均值（dBm），RSSIij表示Bi接收到Bj信號的RSSI平均值（dBm）。因?yàn)樵跓o線信道信號傳播損耗模型中，信號強(qiáng)度平均值和RSSI信號平均值存在著如下關(guān)系（以圖2為例）：

圖2 基于RSSI的測距值校正模型

由上述分析可以得知：假設(shè)某個(gè)信標(biāo)節(jié)點(diǎn)Bi的通信半徑內(nèi)有N個(gè)信標(biāo)節(jié)點(diǎn)，我們在計(jì)算某個(gè)未知節(jié)點(diǎn)o到信標(biāo)節(jié)點(diǎn)Bi的距離doi時(shí)，可以表示為所有的dij對于所有j的可能值的平均值，從而未知節(jié)點(diǎn)o到信標(biāo)節(jié)點(diǎn)Bi的距離doi可以校正為如下式子：

2.2 修正權(quán)重的加權(quán)定位質(zhì)心算法

根據(jù)上述提到的傳統(tǒng)的加權(quán)質(zhì)心定位算法的基本原理可知，加權(quán)權(quán)值這一部分對于整個(gè)算法定位精度有著至關(guān)重要的作用。加權(quán)質(zhì)心定位算法中對于權(quán)值的選擇，不同的文獻(xiàn)采用不同的方式。本文中采取用文獻(xiàn)[7]中距離倒數(shù)之和代替?zhèn)鹘y(tǒng)算法中距離和的倒數(shù)[5]的算法。

本文主要研究的基于RSSI的加權(quán)質(zhì)心定位算法做法是：首先將所接收到的RSSI 數(shù)據(jù)轉(zhuǎn)化為距離信息，將這些距離從小到大進(jìn)行排序，并優(yōu)選距離最小所對應(yīng)的4個(gè)信標(biāo)節(jié)點(diǎn)進(jìn)行定位，每次取其中的3個(gè)信標(biāo)節(jié)點(diǎn)進(jìn)行組合，這樣就會有4中不同的組合。然后分別以選取的3個(gè)信標(biāo)節(jié)點(diǎn)為圓心，以未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)之間的距離為半徑畫圓，這樣3個(gè)圓相交會產(chǎn)生公共的部分。此時(shí)，未知節(jié)點(diǎn)就應(yīng)該位于所有圓的交集部分，以上述提到的質(zhì)心算法為基礎(chǔ)，對3個(gè)圓的共同交點(diǎn)組成的多邊形進(jìn)行分析，利用優(yōu)選的錨節(jié)點(diǎn)和未知節(jié)點(diǎn)之間的距離為每一個(gè)坐標(biāo)增加了權(quán)值，以體現(xiàn)不同頂點(diǎn)的貢獻(xiàn)。算法的基本原理圖如如圖3所示。

圖3 本文提出的加權(quán)質(zhì)心定位算法原理圖

該加權(quán)定位算法中未知節(jié)點(diǎn)的估計(jì)坐標(biāo)可以用以下公式來求取，即：

其中（x，y）就是未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，d1,d2,d3分別為未知節(jié)點(diǎn)獲得的到3個(gè)信標(biāo)節(jié)點(diǎn)的近似距離。（xA，yA），（xB，yB），（xC，yC）為利用上述算法原理求出的 3圓的交點(diǎn)位置坐標(biāo)。

因此，本文所研究的基于RSSI值加權(quán)質(zhì)心算法的基本思想是：在RSSI測距值的獲取階段，將信標(biāo)節(jié)點(diǎn)之間的距離和信號強(qiáng)度信息同時(shí)考慮在內(nèi)進(jìn)行RSSI值校正；權(quán)值選擇階段采用了權(quán)值取距離倒數(shù)之和來對傳統(tǒng)的加權(quán)質(zhì)心算法進(jìn)行融合改進(jìn)。

2.3 算法步驟

錨節(jié)點(diǎn)周期性的以相同功率向周圍廣播信息，信息中包括自身節(jié)點(diǎn)ID及坐標(biāo)，同時(shí)信標(biāo)節(jié)點(diǎn)Bi將收到的信標(biāo)節(jié)點(diǎn)Bj的RSSI值求均值，由式子（3）（4）（5）求出Pij和dij，并將結(jié)果廣播出去。

未知節(jié)點(diǎn)在收到超過閾值N個(gè)信標(biāo)信息后，停止接受信息。只記錄同一個(gè)信標(biāo)節(jié)點(diǎn)的RSSI均值。根據(jù)改進(jìn)后的校正RSSI值測距算法，由式子（5）求出doi。

未知節(jié)點(diǎn)對計(jì)算得來的doi值從小到大排序，并建立RSSI值與節(jié)點(diǎn)到錨節(jié)點(diǎn)距離的映射。建立3個(gè)集合：

信標(biāo)節(jié)點(diǎn)集合：Beacon={B1,B2,B3，…，BN}

信標(biāo)節(jié)點(diǎn)位置信息集合：Position={(x1,y1), (x2,y2), (x3,y3),…，（xN,yN）}

未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)距離集合Distance={do1,do2,do3,…，don}，do1

在上述集合中選取離未知節(jié)點(diǎn)距離最近的前4個(gè)信標(biāo)節(jié)點(diǎn)進(jìn)行定位，然后依照上述介紹的改進(jìn)的加權(quán)質(zhì)心定位算法，分別對4個(gè)定位點(diǎn)坐標(biāo)進(jìn)行計(jì)算。

最后取4個(gè)估計(jì)點(diǎn)組成的多邊形的質(zhì)心作為未知節(jié)點(diǎn)的坐標(biāo)（x，y）。

3 仿真結(jié)果

為了對本文提出的RSSI測距值校正算法和修正加權(quán)質(zhì)心算法進(jìn)行驗(yàn)證，我們采用MATLAB對此進(jìn)行仿真。仿真實(shí)驗(yàn)的初始條件為：無線傳感器網(wǎng)絡(luò)位于100 m×100 m的區(qū)域內(nèi)，信標(biāo)節(jié)點(diǎn)隨機(jī)分布在此區(qū)域內(nèi)，為了驗(yàn)證簡單性，本文把未知節(jié)點(diǎn)初始化為原點(diǎn)（0,0）。無線信號載頻為2.4 GHz，路徑損耗系數(shù)設(shè)為4，節(jié)點(diǎn)的通信半徑為50。另外，所有的仿真實(shí)驗(yàn)環(huán)境中都加入了均值為零，標(biāo)準(zhǔn)差為0.5的滿足高斯分布的隨機(jī)噪聲，來代替實(shí)際環(huán)境中的反射、多徑、物體移動、氣候等帶來的影響。在信標(biāo)節(jié)點(diǎn)從5到25變化的基礎(chǔ)上，我們分3個(gè)方面對本文提出的算法進(jìn)行了仿真分析，仿真結(jié)果如圖4-6所示，所有仿真次數(shù)都取500次，仿真結(jié)果取500次的平均值。

圖4 信標(biāo)節(jié)點(diǎn)個(gè)數(shù)變化時(shí)校正測距值對定位誤差的影響

圖5 信標(biāo)節(jié)點(diǎn)個(gè)數(shù)變化時(shí)加權(quán)權(quán)值對定位誤差的影響

圖6 信標(biāo)節(jié)點(diǎn)個(gè)數(shù)變化時(shí)融合兩種算法后對定位誤差的影響

上述中，圖4驗(yàn)證了基于校正的RSSI算法的有效性，由圖可以得知，相同條件下，信標(biāo)節(jié)點(diǎn)個(gè)數(shù)從5到20時(shí)，定位算法的誤差逐漸減小，說明增加信標(biāo)節(jié)點(diǎn)的個(gè)數(shù)對于提高算法的定位精度有著重要作用。傳統(tǒng)的RSSI定位算法經(jīng)過RSSI測距值修正以后，定位誤差減小，在20個(gè)信標(biāo)節(jié)點(diǎn)定位的時(shí)候可以達(dá)到2.5m。圖5驗(yàn)證了定位階段中加權(quán)權(quán)重修正算法的有效性，可見經(jīng)過權(quán)值修正后，改進(jìn)后的算法相對于傳統(tǒng)的RSSI質(zhì)心定位算法有明顯優(yōu)勢，這一部分說明了加權(quán)權(quán)重對于整個(gè)定位算法的重要作用。為了將RSSI測距修正和權(quán)值改進(jìn)兩種算法融合在一起，圖6驗(yàn)證了基于RSSI校正的改進(jìn)權(quán)重的加權(quán)質(zhì)心定位算法的有效性。在信標(biāo)節(jié)點(diǎn)為5時(shí)，該算法定位誤差在4.4m左右，信標(biāo)節(jié)點(diǎn)為20時(shí)，定位誤差則在2.2m左右，由此可見，該融合算法相對于傳統(tǒng)的基于RSSI的加權(quán)質(zhì)心定位算法有著明顯優(yōu)勢，大大的提高了算法的定位精度。

4 結(jié)論

加權(quán)質(zhì)心定位算法采用了具有較大的無線發(fā)射功率的信標(biāo)節(jié)點(diǎn)，其發(fā)射半徑遠(yuǎn)大于普通節(jié)點(diǎn)的通信半徑[8-10]，可以減少信標(biāo)節(jié)點(diǎn)的數(shù)目，同時(shí)，該算法對于硬件的要求不高，具有較好的綜合效果。本文算法在此基礎(chǔ)上，研究了基于RSSI的加權(quán)質(zhì)心定位算法，在基于測距階段和加權(quán)定位階段提出了新的改進(jìn)算法，充分融合了rangebased與range-free兩種算法的優(yōu)點(diǎn)，使得改進(jìn)后的算法定位精度得到了提高。另一方面，算法在信標(biāo)節(jié)點(diǎn)的覆蓋性問題和功率設(shè)計(jì)都有待進(jìn)一步完善，在今后的應(yīng)用中，可以通過硬件實(shí)驗(yàn)來驗(yàn)證算法的有效性。

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

[2]王福豹,史龍,任豐原.無線傳感器網(wǎng)絡(luò)的自身定位和算法[J].軟件學(xué)報(bào),2005,16(5):857-868.

[3]方震,趙湛,郭鵬,張衛(wèi)國.基于RSSI測距分析[J].傳感技術(shù)學(xué)報(bào),2007,20(11):2526-2530.

[4]Li J,Li J,Cuo L,et al.Power-Efficient Node Localization Algorithm in Wireless Sensor Networks[C]//APWeb 2006 International Workshops, Harbin,China,2006,3842:420-430.

[5]陳維克,李文鋒,首珩,等.基于RSSI的無線傳感器網(wǎng)絡(luò)加權(quán)質(zhì)心定位算法[J].武漢理工大學(xué)學(xué)報(bào),2006,30(12):265-268.

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

[7]劉運(yùn)杰,金明錄,崔承毅.基于RSSI的無線傳感器網(wǎng)絡(luò)修正加權(quán)質(zhì)心定位算法[J].傳感技術(shù)學(xué)報(bào),2010(05).

[8]Ssu K,Ou C,Jiau H C.Localization with Mobile Anchor Points in Wireless Sensor Networks[J].IEEE Transaction on Vehicular Technolo gy,2005,54(3):1187-1197.

[9]Bulusa N,Heidemann J,Estrin D.GPS-less Cost Outdoor Localization for Very Small Devices [J].IEEE Personal Communications Magazine,2000,7(5):28-34.

[10]文舉,金建勛,袁海.一種無線傳感器網(wǎng)絡(luò)四邊測距定位算法[J].傳感器與微系統(tǒng),2008,27(5):108-110.