WSN中基于RSSI的加權質心定位算法的改進

于慧霞

（南京郵電大學 南京 210046）

0 引言

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

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

本文融合文獻[6]和文獻[7]中算法的優點，并彌補兩種算法中的不足，在基于校正RSSI測距的基礎上，通過優選信標節點，最后采用修正加權權重的方法來對傳統的質心定位算法進行改進。

1 算法模型

1.1 無線信號傳播損耗模型

在基于接收信號強度指示RSSI的定位中，已知發射節點的發射信號強度，接收節點根據收到信號的強度，計算出信號的傳播損耗，利用理論和經驗模型將傳輸損耗轉化為距離，再利用已有的算法計算出節點的位置。

一般地，在實際應用環境中，無線傳感器網絡模擬的傳播模型我們考慮最多的就是綜合性強并被廣泛應用的Shadowing模型。

完整的Shadowing模型如下：

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

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

Shadowing模型的第二部分XdB是一個對數正態的隨機變量，它反映了當距離一定時，接收到能量變化。如果以dB作為計量單位時，它滿足高斯分布。它是一個沒有任何意義的高斯隨機變量，它對Shadowing模型作了一個擴展，使之成為一個富有統計學的模型，本文出于環境復雜性的考慮，將使用Shadowing的完整模型，即將一個零均值高斯分布的隨機噪聲引入了無線電傳播模型中，該噪聲分布服從對數正態分布。

1.2 傳統的質心定位算法模型

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

圖1 質心定位算法的示意圖

在質心算法中，信標節點周期性地向鄰近節點廣播信標分組，信標分組中包含信標節點的標識號和位置信息。當未知節點接收到來自不同信標節點的信標分組數量超過某一個門限或接收一定時間后，就確定自身位置為這些信標節點所組成的多邊形的質心：為未知節點能夠接收到其分組的信標節點坐標。

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

其中，wi表示每個固定信標節點的權值，通常，該權值是未知節點到固定信標節點的距離函數的倒數。特殊情況下，如果未知節點不能與固定信標節點Bi通信，那么權值為零。

2 基于傳統模型的改進算法模型

2.1 RSSI值校正模型-基于固定信標節點間距離的校正模型

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

又假設RSSI0i為未知節點A接收到錨節點Bi信號的RSSI平均值（dBm），RSSIij表示Bi接收到Bj信號的RSSI平均值（dBm）。因為在無線信道信號傳播損耗模型中，信號強度平均值和RSSI信號平均值存在著如下關系（以圖2為例）：

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

由上述分析可以得知：假設某個信標節點Bi的通信半徑內有N個信標節點，我們在計算某個未知節點o到信標節點Bi的距離doi時，可以表示為所有的dij對于所有j的可能值的平均值，從而未知節點o到信標節點Bi的距離doi可以校正為如下式子：

2.2 修正權重的加權定位質心算法

根據上述提到的傳統的加權質心定位算法的基本原理可知，加權權值這一部分對于整個算法定位精度有著至關重要的作用。加權質心定位算法中對于權值的選擇，不同的文獻采用不同的方式。本文中采取用文獻[7]中距離倒數之和代替傳統算法中距離和的倒數[5]的算法。

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

圖3 本文提出的加權質心定位算法原理圖

該加權定位算法中未知節點的估計坐標可以用以下公式來求取，即：

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

因此，本文所研究的基于RSSI值加權質心算法的基本思想是：在RSSI測距值的獲取階段，將信標節點之間的距離和信號強度信息同時考慮在內進行RSSI值校正；權值選擇階段采用了權值取距離倒數之和來對傳統的加權質心算法進行融合改進。

2.3 算法步驟

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

未知節點在收到超過閾值N個信標信息后，停止接受信息。只記錄同一個信標節點的RSSI均值。根據改進后的校正RSSI值測距算法，由式子（5）求出doi。

未知節點對計算得來的doi值從小到大排序，并建立RSSI值與節點到錨節點距離的映射。建立3個集合：

信標節點集合：Beacon={B1,B2,B3，…，BN}

信標節點位置信息集合：Position={(x1,y1), (x2,y2), (x3,y3),…，（xN,yN）}

未知節點到信標節點距離集合Distance={do1,do2,do3,…，don}，do1

在上述集合中選取離未知節點距離最近的前4個信標節點進行定位，然后依照上述介紹的改進的加權質心定位算法，分別對4個定位點坐標進行計算。

最后取4個估計點組成的多邊形的質心作為未知節點的坐標（x，y）。

3 仿真結果

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

圖4 信標節點個數變化時校正測距值對定位誤差的影響

圖5 信標節點個數變化時加權權值對定位誤差的影響

圖6 信標節點個數變化時融合兩種算法后對定位誤差的影響

上述中，圖4驗證了基于校正的RSSI算法的有效性，由圖可以得知，相同條件下，信標節點個數從5到20時，定位算法的誤差逐漸減小，說明增加信標節點的個數對于提高算法的定位精度有著重要作用。傳統的RSSI定位算法經過RSSI測距值修正以后，定位誤差減小，在20個信標節點定位的時候可以達到2.5m。圖5驗證了定位階段中加權權重修正算法的有效性，可見經過權值修正后，改進后的算法相對于傳統的RSSI質心定位算法有明顯優勢，這一部分說明了加權權重對于整個定位算法的重要作用。為了將RSSI測距修正和權值改進兩種算法融合在一起，圖6驗證了基于RSSI校正的改進權重的加權質心定位算法的有效性。在信標節點為5時，該算法定位誤差在4.4m左右，信標節點為20時，定位誤差則在2.2m左右，由此可見，該融合算法相對于傳統的基于RSSI的加權質心定位算法有著明顯優勢，大大的提高了算法的定位精度。

4 結論

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

[1]孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社,2005.

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

[3]方震,趙湛,郭鵬,張衛國.基于RSSI測距分析[J].傳感技術學報,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的無線傳感器網絡加權質心定位算法[J].武漢理工大學學報,2006,30(12):265-268.

[6]趙昭,陳小惠.無線傳感器網絡中基于RSSI的改進定位算法[J].傳感技術學報,2009(03).

[7]劉運杰,金明錄,崔承毅.基于RSSI的無線傳感器網絡修正加權質心定位算法[J].傳感技術學報,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]文舉,金建勛,袁海.一種無線傳感器網絡四邊測距定位算法[J].傳感器與微系統,2008,27(5):108-110.