周林　張厚望

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

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

中圖分類號(hào)： TN926?34 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 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）中，位置信息對(duì)傳感器網(wǎng)絡(luò)的監(jiān)測(cè)活動(dòng)至關(guān)重要，確定事件發(fā)生的位置或獲取信息的節(jié)點(diǎn)位置對(duì)傳感器應(yīng)用的有效性起著關(guān)鍵的作用[1]。節(jié)點(diǎn)定位技術(shù)為整個(gè)網(wǎng)絡(luò)系統(tǒng)獲取大量真實(shí)且可靠的監(jiān)測(cè)信息，提供了網(wǎng)絡(luò)應(yīng)用中非常重要的節(jié)點(diǎn)地理位置信息[2]?？梢哉f，沒有位置信息的信息是沒有意義的。

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

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

1 算法模型

1.1 RSSI技術(shù)

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

1.2 APIT方法

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

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

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

2 誤差分析

2.1 信標(biāo)節(jié)點(diǎn)隨機(jī)分布

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

2.2 中心化問題

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

3 本文改進(jìn)算法

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

3.1 最佳三角形的選擇

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

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

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

（2） 未知節(jié)點(diǎn)分別接收三個(gè)信號(hào)節(jié)點(diǎn)的信號(hào)強(qiáng)度數(shù)值的差值應(yīng)小于一定閾值閾值的大小可根據(jù)定位精度要求人為設(shè)定：

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

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

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

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

3.2 縮小三角形的范圍

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

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

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

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

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

4 仿真驗(yàn)證與分析

（2） 不同的信標(biāo)節(jié)點(diǎn)數(shù)量

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

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

（3） 不同通信半徑

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

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

5 結(jié) 語

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

參考文獻(xiàn)

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

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

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

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

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

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

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

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

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

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