無線傳感器網絡中基于RSSI的質心定位算法研究

周林　張厚望

摘 要： 無線傳感器網絡中，由于傳統質心算法普遍存在信標節點分布不均與中心化問題，導致定位誤差相對較大。針對這些問題，提出了基于RSSI的改進算法。在APIT的基礎上，改進算法依靠未知節點接收到不同信標節點的RSSI數值，判斷其周圍是否存在最佳三角形，若存在則利用最佳三角形進行定位；若不存在則選出一個距其較近的三角形，利用移動信標節點的辦法來縮小此三角形的范圍進行定位。Matlab平臺仿真結果表明，與傳統質心算法相比，改進算法減少了定位誤差，節點定位精度有所提高。

關鍵詞： 無線傳感器網絡； 質心定位算法； APIT； RSSI； 最佳三角形； 移動信標節點

中圖分類號： TN926?34 文獻標識碼： A 文章編號： 1004?373X（2015）01?0030?05

Abstract： In wireless sensor network， due to the widespread problems of beacons nodes' uneven distribution and centralization， traditional centroid algorithm has relatively large positioning error. In order to solve these problems， an improved algorithm based on RSSI is proposed. On the basis of APIT， the improved algorithm uses the received signal strength from different beacon nodes to determine whether the surrounding of a unknown node exists the best triangle. If does， the improved algorithm would use the best triangle to locate. If not， the improved algorithm would select a triangle which is closer to the unknown node and use the method of moving beacon node to narrow range of the triangle to locate. The results of Matlab simulation shows that， compared with the traditional centroid algorithm， the improved algorithm can reduce the positioning error and improve the positioning accuracy of nodes.

Keywords： wireless sensor network； centroid positioning algorithm； APIT； RSSI； best triangle； moving beacon node

0 引 言

在無線傳感器網（Wireless Sensor Network，WSN）中，位置信息對傳感器網絡的監測活動至關重要，確定事件發生的位置或獲取信息的節點位置對傳感器應用的有效性起著關鍵的作用[1]。節點定位技術為整個網絡系統獲取大量真實且可靠的監測信息，提供了網絡應用中非常重要的節點地理位置信息[2]。可以說，沒有位置信息的信息是沒有意義的。

在無線傳感器網絡中，有兩種節點[3]：一種是已知自己地理位置信息的節點，稱為信標節點，通過人工測量或者利用GPS等定位設備來獲得自身的地理位置信息；另外一種是不知道自己地理位置信息的節點，稱為未知節點，要借助信標節點的位置信息來確定自身位置。

在統計和系統分析已有定位算法的基礎上[4]，一般按照是否采用測距技術，將定位算法分為基于測距（Range?based）的定位算法和無需測距（Range?free）的定位算法。質心定位算法的提出是為了避免節點之間直接測量距離，屬于無需測距的定位算法。本文在RSSI技術、APIT方法與質心定位算法的基礎之上，提出了一些改進，實驗結果表明改進算法可以減少定位誤差，提高節點定位精度。

1 算法模型

1.1 RSSI技術

當無線信號在大氣環境中傳播時， 由于多種因素影響， 信號強度會隨著其傳播距離的增加而衰減。這表明，信號強度變化與傳播距離間存在著某種函數關系，且通常情況下傳感節點均可很容易配置測定接收信號強度的模塊[5]，這就是RSSI測距技術。其特點是隨著節點間距離的增大（或減小），兩者之間的信號強度變弱（或變強），RSSI數值變小（或變大）。

1.2 APIT方法

依靠于無線傳感器網絡未知節點密度較高及無線信號的傳播特性的特點，APIT算法可判斷未知節點是否位于由三個信標節點組成的三角形內部[6]。一般情況下，根據接收到的信號強度的大小變化判斷是否同時靠近或是遠離某個信標節點。在APIT算法中，未知節點與任一鄰居節點作相對于信標節點的位置比較來達到PIT中節點移動的效果。如圖1所示，若未知節點[X]通過與鄰居節點1交換信息，獲知如果未知節點[X]移動到節點1處，不會同時靠近或是遠離信標節點[A、][B、][C，]故未知節點[X]位于信標節點[A、][B、][C]組成的三角形內部；反義，若未知節點[Y]通過與鄰居節點2交換信息，獲知如果未知節點[Y]移動到節點2處，將同時靠近或是遠離信標節點[A、][B、][C，]故未知節點[Y]位于信標節點[A、][B、][C]組成的三角形外部。

1.3 傳統質心算法

質心算法（Centriod Algorithm）是一種基于距離無關（Range?free）的節點定位算法，僅僅通過網絡的連通度，節點就可以實現粗糙的定位，并且定位過程不需要其他的外在硬件設備[7]。它的基本原理是假設未知節點可接收到[n]個信標節點的位置坐標信息，則認為該未知節點位于這[n]個信標節點組成的多邊形的質心。其具體的定位過程為：定位初始階段，信標節點每間隔一段時間就廣播自身的數據包，其中包括自身的ID和位置坐標信息；未知節點持續監聽且接收來自信標節點的數據包，當未知節點在一段時間內所接收到的信標節點數據包的數量超過預先設定的閾值（或一定時間），計算得出此未知節點所接收到的所有信標節點組成的多邊形的質心位置，最后將質心位置作為此未知節點的估計位置。

2 誤差分析

2.1 信標節點隨機分布

質心算法的優點在于僅需利用網絡的連通度就可定位，實現簡單，無需測量節點之間的距離或是角度信息，但是其定位精度很大程度上受到信標節點分布和密度的影響。文獻[8]證明了在信標節點分布均勻的情況下，可以達到要求較好的定位精度；然而當信標節點隨機分布時，信標節點的分布并不均勻，未知節點的估計位置會向信標節點密度較大的方向偏移，定位精度大幅下降。并且，無論信標節點是隨機分布還是均勻分布，定位誤差都會隨著信標節點數量的增多而下降；此外，信標節點隨機分布的定位精度總是小于均勻分布的定位精度，且往往達不到精度要求。如圖3所示，當信標節點[A，][B，][C，][D，][E]分布不均勻的時候，根據傳統質心算法得出的未知節點[M]的估計位置[M]明顯偏于信標節點數量多的一側。

2.2 中心化問題

傳統質心算法中，通常存在中心化問題。所謂中心化問題，就是無論未知節點位于信標節點組成的多邊形的何處，都籠統地認為未知節點位于此多邊形的質心位置。為簡化說明，以信標節點組成的多邊形為三角形的情況進行分析[9]。如圖4所示，無論未知節點[M]實際位于[△ABC]內部何處，傳統質心算法都認為估計位置[M]為未知節點的所在位置。

3 本文改進算法

根據距離與RSSI數值成反比關系的特點，本文將在每個傳感器節點中嵌入信號接收強度分析模塊，解決信標節點隨機分布與中心化問題。

3.1 最佳三角形的選擇

合理選擇未知節點通信半徑范圍內信標節點組成的三角形，可以解決其估計位置向信標節點密度較大方向偏移的問題。但是，若未知節點的通信半徑范圍內存在[n]個信標節點，則其周圍存在[C3n]個三角形，如何選擇未知節點通信范圍內的最佳三角形是本文研究的重點。

通過大量理論實驗分析，本文得出了未知節點周圍最佳三角形的判決條件：

（1） 未知節點必須位于此三角形的內部，可利用APIT方法進行驗證；

（2） 未知節點分別接收三個信號節點的信號強度數值的差值應小于一定閾值閾值的大小可根據定位精度要求人為設定：

[RSSI1-RSSI2≤ηRSSI1-RSSI3≤ηRSSI2-RSSI3≤η] （1）

式中：RSSI分別表示未知節點接收來自信標節點1、2、3的信號強度數值；[η]表示根據定位精度要求而人為設定的閾值。

若同時滿足上述兩個條件，未知節點就可確定其通信半徑范圍內的最佳三角形，則最佳三角形的質心位置就認為是未知節點的估計位置。如果存在多個最佳三角形，則分別求出多個最佳三角形的質心，再對這些質心求算術平均，其平均值就認為是未知節點的估計坐標。

如圖5所示，[M]為未知節點實際位置，信標節點[A，][B，][C，][D，][E]均在其通信半徑范圍內，[M]為多邊形[ABCDE]的質心。為了確定未知節點[M]周圍的最佳三角形，具體步驟如下：首先，未知節點[M]判斷其周圍存在[C35=]10個三角形；其次，根據條件（1），利用APIT方法得出未知節點[M]只位于[△ABE]與[△ACD]內部；然后，分別計算未知節點[M]接收來自信標節點[A，][B，][E]與信標節點[A，][C，][D，]兩兩信號強度的差值，利用式（1），判斷其差值是否小于閾值。就圖5而言，[MA，][MB，][ME]之間的距離誤差較小，其RSSIMA，RSSIMB，RSSIME數值也接近，因此選擇[A，][B，][E]這三個信標節點的兩兩信號強度的差值更小，其定位精度最高。從圖5可以看出，[M1]為[△ABE]的質心，[M2]為[△ACD]的質心，若將[M1]的位置作為[M]點的估計坐標，誤差明顯小于以[M2]作為[M]點的估計坐標。

3.2 縮小三角形的范圍

為了解決未知節點周圍不存在最佳三角形的情況，本文提出了縮小與其距離較近的一個特定三角范圍的辦法來提高定位精度，具體步驟如下：

（1） 在未知節點周圍不存在最佳三角形的情況下，通過比較接收未知節點信號強度數值的大小，選擇其中三個最大（較大）值，即選取離未知節點最近（較近）的三個信標節點；

（2） 利用APIT方法判斷未知節點是否位于這三個信標節點組成的三角形內部，若不滿足則返回到步驟（1）中繼續尋找合適的三角形，直到滿足條件為止；

（3） 以滿足條件的三角形的三邊為信標節點移動的軌跡，縮小此三角形的范圍，改變質心位置，解決中心化問題。

如圖6所示，在未知節點[U]周圍選擇了一個滿足上述條件的[△ABC，]其中[A，][B，][C]為信標節點。固定信標節點[B，][C，]移動信標節點[A。]先在[AB]邊上向著信標節點[B]以一定的速率移動。若移動過程中，未知節點[U]收到的RSSI值變大，則繼續移動；若變小，不再移動。這樣就可以在直線[AB]上找到一點[A，]使得[A]點到未知節點[U]的RSSI值最大，故[A]點到未知節點的距離越近。以相同的方法，可在[BC]邊上找到一點[B，]在[CA]邊上找到一點[C。]連接[ABC，]形成一個新的三角形。在圖6中，[U]為未知節點的實際位置，[U]為原三角形質心，[U]為移動信標節點之后，即迭代一次之后，新三角形的質心。將新三角形質心坐標作為未知節點的坐標，不僅緩解了中心化問題，并且也提高了定位精度。也可以利用同樣的方法繼續縮小新[△ABC]的范圍，依次循環，一直縮小三角形的范圍。當滿足定位精度要求時（或是迭代次數時），將最后一個小三角形的質心作為未知節點的坐標。

4 仿真驗證與分析

（2） 不同的信標節點數量

其他仿真參數不變，分別在信標節點的數量為10～50情況下比較兩種算法的性能。

如圖9所示，當節點總數不變時，信標節點數量的增加會導致網絡連通度的增大，未知節點可參考到的信標節點數量增多，未知節點越趨近于信標節點組成的多邊形的質心，所以本文改進算法與傳統質心算法的平均定位誤差都會隨著信標節點數量的增加而降低。但是可以看出，當信標節點數量相同時，本文改進算法的平均定位誤差明顯低于傳統質心算法，而且當信標節點數量較少時，本文改進算法的平均定位精度也明顯優于傳統質心算法。因此，相比于傳統質心算法，本文改進算法降低了定位誤差，提升了定位精度。

（3） 不同通信半徑

最后改變節點的通信半徑，對兩種算法進行性能比較，如圖10所示。通信半徑[R]分別取20，25，30。

從圖10可以看出，當信標節點數量一定時，隨著節點通信半徑的不斷增大，本文改進算法的平均定位誤差也在降低。這是因為節點通信半徑的增大會提升網絡的連通度，未知節點可參考到更多的信標節點，其位置就越趨近于信標節點組成三角形的質心，定位精度就會相對準確。

5 結 語

節點定位技術在無線傳感器網絡中的定位至關重要，是檢測事件位置發生的基礎。與傳統的質心算法相比，本文改進算法以解決傳統質心算法普遍存在的信標節點分布不均與中心化問題為目的，有效地降低了傳統算法中存在的誤差。仿真結果表明，改進算法的定位誤差明顯低于傳統質心算法，定位精度可滿足實際需要。這就意味著，本文的改進算法更加實際且準確地反映了網絡的狀況，對于節點隨機部署、大規模的無線傳感器網絡節點定位來說，符合無線傳感器網絡的基本要求，是一種有效的解決辦法。

參考文獻

[1] 馬祖長，孫怡寧，梅濤.無線傳感器網絡綜述[J].通信學報，2004，25（4）：114?124.

[2] 史躍飛，馮秀芳，高昊.一種基于動態錨節點的改進加權定位算法[J].計算機應用與軟件，2013，30（10）：151?154.

[3] 彭宇，王丹.無線傳感器網絡定位技術綜述[J].電子測量與儀器學報，2011，25（5）：389?399.

[4] 趙雁航，錢志鴻，尚小航，等.基于跳距修正粒子群優化的WSN定位算法[J].通信學報，2013，34（9）：105?114.

[5] 劉峰，章登義.基于RSSI的無線傳感器網絡質心定位算法[J].計算機科學，2012，39（6）：96?98.

[6] 徐小玲，張福強，李少彪.基于APIT的無線傳感器網絡質心算法研究[J].傳感器與微系統，2011，30（7）：57?63.

[7] 劉皇保，王濤，彭剛.一種改進的質心定位算法[J].微型機與應用，2013，32（11）：73?75.

[8] 李兆斌，魏占禎，徐風麟.無線傳感器網絡增強的質心定位算法及性能分析[J].傳感技術學報，2009，22（4）：563?566.

[9] 衣曉，王梓，薛興亮.一種基于次錨節點的無線傳感器網絡質心定位算法[J].計算機應用與軟件，2013，30（6）：116?120.

[10] 白進京，嚴新平，張存保，等.基于加權質心和DV?Hop混合算法WSN定位方法研究[J].計算機應用研究，2009，26（6）：2248?2250.