一種改進(jìn)的質(zhì)心定位算法

劉皇保，王 濤，彭 剛

（1.桂林電子科技大學(xué) 電子工程與自動(dòng)化學(xué)院，廣西 桂林541004；2.空軍空降兵學(xué)院 教育技術(shù)中心，廣西 桂林541003）

無線傳感器網(wǎng)絡(luò)是大量的靜止或移動(dòng)的傳感器以自組織和多跳的方式構(gòu)成的無線網(wǎng)絡(luò)，大量的傳感器節(jié)點(diǎn)將探測數(shù)據(jù)，通過匯聚節(jié)點(diǎn)經(jīng)其他網(wǎng)絡(luò)發(fā)送給了用戶[1]。

節(jié)點(diǎn)定位技術(shù)是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一。沒有節(jié)點(diǎn)的位置信息，傳感器監(jiān)測信息將沒有實(shí)際意義。無線傳感器網(wǎng)絡(luò)只有少數(shù)錨節(jié)點(diǎn)可以人工布置或者通過GPS定位系統(tǒng)獲得自身的位置信息，大部分普通節(jié)點(diǎn)則必須通過錨節(jié)點(diǎn)信息來進(jìn)行定位。

無線傳感器網(wǎng)絡(luò)定位技術(shù)主要分為基于距離的定位算法（如RSSI、TOA/TDOA和AOA）和距離無關(guān)的定位算法（如質(zhì)心、DV-Hop、APIT、Amorphous和凸規(guī)劃）。

質(zhì)心算法可以快速、方便地定位節(jié)點(diǎn)的初始位置，而基于距離的定位算法RSSI[2]需要額外的器件來測量實(shí)際節(jié)點(diǎn)間的距離，會(huì)增加功耗，但與距離無關(guān)的定位算法相比較，其定位精度更高。將兩者結(jié)合勢必會(huì)取得較好的定位效果。通過分析現(xiàn)有的質(zhì)心算法缺陷，結(jié)合RSSI，對(duì)質(zhì)心算法進(jìn)行改進(jìn)，提出一種改進(jìn)的質(zhì)心定位算法。

1 質(zhì)心定位算法

1.1 質(zhì)心定位算法的基本思想

質(zhì)心算法[4]是由南加州大學(xué)的Nirupama Bulusu等人提出的，在未知節(jié)點(diǎn)收到相鄰錨節(jié)點(diǎn)的位置信息后，取這些相鄰錨節(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)識(shí)號(hào)和位置信息。當(dāng)未知節(jié)點(diǎn)接收到來自不同信標(biāo)節(jié)點(diǎn)的信標(biāo)分組數(shù)量超過某一個(gè)門限或接收一定時(shí)間后，就確定自身位置為這些信標(biāo)節(jié)點(diǎn)所組成的多邊形的質(zhì)心：

其中，（Xi1，Yi1）…（Xik，Yik）為未知節(jié)點(diǎn)能夠接收到其分組的信標(biāo)節(jié)點(diǎn)坐標(biāo)。

通過對(duì)算法思想的分析，可知傳統(tǒng)的質(zhì)心定位算法定位誤差較大。

1.2 現(xiàn)有改進(jìn)的質(zhì)心定位算法

胡詠梅等[4]人提出了一種改進(jìn)的加權(quán)質(zhì)心定位算法，對(duì)未知節(jié)點(diǎn)大致位置的算法作了新的修正，并對(duì)未知節(jié)點(diǎn)位置確定算法中的加權(quán)因子進(jìn)行了優(yōu)化。于慧霞[5]提出了一種新的校正RSSI測距值的加權(quán)定位算法。測距階段將錨節(jié)點(diǎn)之間的距離和信號(hào)強(qiáng)度信息同時(shí)考慮在內(nèi)，進(jìn)行RSSI值校正，權(quán)值選擇階段采用了修正傳統(tǒng)權(quán)重的計(jì)算方法，權(quán)值取距離倒數(shù)之和。茍勝難[6]提出了一種基于改進(jìn)的RSSI無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究。算法首先通過無線信號(hào)強(qiáng)度計(jì)算出節(jié)點(diǎn)間RSSI值，然后把RSSI值轉(zhuǎn)換成質(zhì)心算法權(quán)值，最后采用質(zhì)心定位算法對(duì)待測節(jié)點(diǎn)位置進(jìn)行估計(jì)，獲得節(jié)點(diǎn)的準(zhǔn)確位置。

蘋果想要賣上好價(jià)，關(guān)鍵在提高果品質(zhì)量?，F(xiàn)場采購商對(duì)王建云及其他參賽選手的蘋果品質(zhì)表示了認(rèn)可，并向記者透露，果農(nóng)是否選擇大品牌的農(nóng)資產(chǎn)品，對(duì)于采購商來說是一個(gè)重要的參考指標(biāo)。因?yàn)槭褂孟裼H土1號(hào)這樣的產(chǎn)品，更能有效保障果品的質(zhì)量和安全，而只要是品質(zhì)好的果子，既不愁賣，也不擔(dān)心賣不上價(jià)。

2 本文對(duì)質(zhì)心算法的改進(jìn)

以往的算法應(yīng)用于未知節(jié)點(diǎn)周邊的錨節(jié)點(diǎn)的整個(gè)區(qū)域，本文將未知節(jié)點(diǎn)周邊區(qū)域進(jìn)行了細(xì)分，利用未知節(jié)點(diǎn)收到周邊錨節(jié)點(diǎn)的信號(hào)強(qiáng)度（RSSI），取細(xì)分后的某區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置。

具體步驟如下：

（1）利用周圍錨節(jié)點(diǎn)收到的未知節(jié)點(diǎn)信號(hào)的強(qiáng)度確定最近的3個(gè)不共線的錨節(jié)點(diǎn)。

如圖2所示，可知錨節(jié)點(diǎn)A、B、C為未知節(jié)點(diǎn)O周圍最近的3個(gè)不共線的錨節(jié)點(diǎn)。

（2）確定3個(gè)錨節(jié)點(diǎn)構(gòu)成的三角形的外接圓，通過三角形三邊的垂直平分線將外接圓分成6個(gè)區(qū)域，如圖3所示。

圖3中，由3條垂直平分線l1、l2、l3將未知節(jié)點(diǎn)O周圍圓形區(qū)域劃分為6個(gè)區(qū)域。6個(gè)區(qū)域內(nèi)的未知點(diǎn)發(fā)送的信號(hào)在A、B、C 3個(gè)位置收到的信號(hào)強(qiáng)度大小關(guān)系各不同。

圖2 未知節(jié)點(diǎn)周邊錨節(jié)點(diǎn)

圖3 分區(qū)示意圖

（3）根據(jù)A、B、C 3個(gè)位置錨節(jié)點(diǎn)收到的信號(hào)強(qiáng)度關(guān)系確定未知節(jié)點(diǎn)所在區(qū)域，如圖4所示。

圖4 未知節(jié)點(diǎn)所在區(qū)域

從區(qū)域的△OPQ內(nèi)的未知節(jié)點(diǎn)發(fā)射的信號(hào)，在A、B、C 3個(gè)位置收到的信號(hào)強(qiáng)度有如下關(guān)系：

未知節(jié)點(diǎn)在6個(gè)區(qū)域中發(fā)射的信號(hào)在A、B、C 3個(gè)位置錨節(jié)點(diǎn)收到的信號(hào)強(qiáng)度關(guān)系各不同。因此，根據(jù)信號(hào)強(qiáng)度關(guān)系，按照以下方法可以進(jìn)行更為精確的定位：

①如果3個(gè)錨節(jié)點(diǎn)收到的信號(hào)強(qiáng)度都不同，則根據(jù)信號(hào)強(qiáng)度關(guān)系先確定未知節(jié)點(diǎn)所在三角形區(qū)域，然后取該區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置。

②如果A、B、C 3個(gè)錨節(jié)點(diǎn)中某兩個(gè)點(diǎn)收到的信號(hào)強(qiáng)度一樣，則定位區(qū)域變成一條線。如圖4所示，假設(shè)RSSIa=RSSIc，則未知節(jié)點(diǎn)在l3上，結(jié)合RSSIa>RSSIb，可確定未知節(jié)點(diǎn)的估計(jì)位置在上，此時(shí)，取的中點(diǎn)作為估計(jì)位置。

③如果A、B、C 3點(diǎn)收到的信號(hào)強(qiáng)度是一樣的，則取外心O作為未知節(jié)點(diǎn)的估計(jì)位置。

3 實(shí)驗(yàn)及仿真結(jié)果

本文采用MATLAB 7.1作為仿真工具，對(duì)算法進(jìn)行了仿真。仿真環(huán)境設(shè)置在1 000 m×1 000 m的正方形區(qū)域內(nèi)，隨機(jī)生成300個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，錨節(jié)點(diǎn)占一定比例，錨節(jié)點(diǎn)的通信距離為200 m。對(duì)仿真結(jié)果數(shù)據(jù)取10次仿真的平均值。節(jié)點(diǎn)分布如圖5所示。

圖5 初始節(jié)點(diǎn)分布

接下來，根據(jù)區(qū)域內(nèi)節(jié)點(diǎn)的分布關(guān)系，計(jì)算出所有節(jié)點(diǎn)的鄰居關(guān)系，為后面的未知節(jié)點(diǎn)定位做好準(zhǔn)備。節(jié)點(diǎn)鄰居關(guān)系如圖6所示。

圖6 節(jié)點(diǎn)鄰居關(guān)系

最后，采用改進(jìn)的質(zhì)心定位算法進(jìn)行未知節(jié)點(diǎn)的定位，計(jì)算出各個(gè)未知節(jié)點(diǎn)的定位誤差。畫出定位誤差圖形如圖7所示。

圖7 每個(gè)未知節(jié)點(diǎn)的定位誤差

通過設(shè)置不同的錨節(jié)點(diǎn)比例得到相應(yīng)不同的定位誤差，與原始的質(zhì)心算法仿真結(jié)果對(duì)比，可以得出定位誤差對(duì)比圖，如圖8所示。

在通信距離為200 m時(shí)以錨節(jié)點(diǎn)占全部節(jié)點(diǎn)的比例來作為圖中的橫坐標(biāo)，以未知節(jié)點(diǎn)的平均定位誤差作為縱坐標(biāo)，作出原始質(zhì)心算法和改進(jìn)的質(zhì)心算法的平均定位誤差圖。從圖8可以看出，隨著錨節(jié)點(diǎn)增加，未知節(jié)點(diǎn)的定位誤差相應(yīng)減小，同時(shí)，與原始質(zhì)心算法相比，改進(jìn)的質(zhì)心算法平均定位誤差減少了將近60%。

圖8 平均定位誤差

基于傳統(tǒng)的質(zhì)心算法和RSSI思想，本文提出了一種基于RSSI的改進(jìn)的質(zhì)心定位算法。該算法首先通過RSSI大小確定未知節(jié)點(diǎn)周邊錨節(jié)點(diǎn)的遠(yuǎn)近，找出最近的3個(gè)錨節(jié)點(diǎn)，采用3個(gè)錨節(jié)點(diǎn)確定的三邊的垂直平分線將未知節(jié)點(diǎn)的輻射范圍劃為6個(gè)區(qū)域；然后，根據(jù)RSSI確定未知節(jié)點(diǎn)所在的更小區(qū)域；最后，取該區(qū)域的質(zhì)心作為未知節(jié)點(diǎn)的估計(jì)位置。仿真結(jié)果證明，此方法大大提高了定位精度。

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

[2]HEURTEFEUX K，VALOIS F.Is RSSI a good choice for localization[C].26th IEEE International Conference on Advanced Information Networking and Applications in Wireless Sensor Network，F(xiàn)rance，2012.

[3]BULUSU N，HEIDEMANN J，ESTRIN D.GPS-less lowcost outdoor localization for very small devices[J].Personal Communications，IEEE，2000，7（5）：28-34.

[4]胡詠梅，張歡.一種改進(jìn)的無線傳感器網(wǎng)絡(luò)質(zhì)心定位算法[J].計(jì)算機(jī)工程與科學(xué)，2012，34（2）：45-49.

[5]于慧霞.WSN中基于RSSI的加權(quán)質(zhì)心定位算法的改進(jìn)[J].電子測試，2012，1（1）：28-34.

[6]茍勝難.基于改進(jìn)的RSSI無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法研究[J].計(jì)算機(jī)應(yīng)用研究，2012，29（5）：1867-1869.