無線傳感器網(wǎng)絡(luò)中基于RSSI的質(zhì)心定位算法研究

周林　張厚望

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

關(guān)鍵詞： 無線傳感器網(wǎng)絡(luò)； 質(zhì)心定位算法； APIT； RSSI； 最佳三角形； 移動信標節(jié)點

中圖分類號： 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 引 言

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

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

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

1 算法模型

1.1 RSSI技術(shù)

當無線信號在大氣環(huán)境中傳播時， 由于多種因素影響， 信號強度會隨著其傳播距離的增加而衰減。這表明，信號強度變化與傳播距離間存在著某種函數(shù)關(guān)系，且通常情況下傳感節(jié)點均可很容易配置測定接收信號強度的模塊[5]，這就是RSSI測距技術(shù)。其特點是隨著節(jié)點間距離的增大（或減?。?，兩者之間的信號強度變?nèi)酰ɑ蜃儚姡琑SSI數(shù)值變?。ɑ蜃兇螅?/p>

1.2 APIT方法

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

1.3 傳統(tǒng)質(zhì)心算法

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

2 誤差分析

2.1 信標節(jié)點隨機分布

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

2.2 中心化問題

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

3 本文改進算法

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

3.1 最佳三角形的選擇

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

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

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

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

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

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

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

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

3.2 縮小三角形的范圍

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

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

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

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

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

4 仿真驗證與分析

（2） 不同的信標節(jié)點數(shù)量

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

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

（3） 不同通信半徑

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

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

5 結(jié) 語

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

參考文獻

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

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

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

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

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

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

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

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

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

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