杜士懷 宋 杰

(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)

一種改進(jìn)的質(zhì)心定位及誤差校正算法

杜士懷 宋 杰

(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)

在信標(biāo)節(jié)點(diǎn)分布不均勻的情況下，為了使節(jié)點(diǎn)定位的誤差盡可能小以及在誤差校正過程更加有效和可靠，提出一種改進(jìn)的質(zhì)心定位算法。該算法首先確定未知節(jié)點(diǎn)通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)，然后取部分這些信標(biāo)節(jié)點(diǎn)作為頂點(diǎn)構(gòu)成凸多邊形，通過RSSI獲取未知節(jié)點(diǎn)與凸多邊形的各個(gè)頂點(diǎn)的距離，之后將質(zhì)心定位的凸多邊形內(nèi)的所有信標(biāo)節(jié)點(diǎn)都作為校正節(jié)點(diǎn)，由這些校正節(jié)點(diǎn)得到相對(duì)應(yīng)的校正因子，通過添加權(quán)重因子綜合所有的校正因子來替換未知節(jié)點(diǎn)的測(cè)距誤差因子，對(duì)測(cè)距誤差進(jìn)行補(bǔ)償，最后利用加權(quán)質(zhì)心定位方法確定未知節(jié)點(diǎn)的最終位置。仿真實(shí)驗(yàn)表明：在信標(biāo)節(jié)點(diǎn)分布不均勻的情況下，在100 m×100 m的監(jiān)測(cè)區(qū)域內(nèi)，該算法相比于其他定位算法具有更強(qiáng)的抗干擾能力，而且平均定位誤差至少減少12%，是一種定位精度更高的算法。

節(jié)點(diǎn)定位 接收的信號(hào)強(qiáng)度指示 質(zhì)心定位算法 凸多邊形 校正因子 補(bǔ)償

0 引 言

在研究無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)定位技術(shù)是一項(xiàng)重要的支撐技術(shù)。獲取傳感器節(jié)點(diǎn)的位置信息的精確與否對(duì)于無線傳感器網(wǎng)絡(luò)至關(guān)重要[1]。

在無線傳感器網(wǎng)絡(luò)(WSN)定位算法中，由節(jié)點(diǎn)的坐標(biāo)位置信息是否已知可分為信標(biāo)節(jié)點(diǎn)和未知節(jié)點(diǎn)；在獲得位置信息時(shí)根據(jù)未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)之間的距離是否需要測(cè)量分為測(cè)距算法和非測(cè)距算法[2]。前者常使用的測(cè)距算法主要包括RSSI、AOA、TOA等定位算法，而后者常使用的非測(cè)距算法主要有質(zhì)心法、凸規(guī)劃法、DV-Hop等定位算法[3]。

盡管當(dāng)前的定位算法很多，但都有定位精度不足、及抗干擾性差等問題，本文結(jié)合以上問題提出了一種基于RSSI測(cè)距的改進(jìn)的質(zhì)心定位算法。仿真實(shí)驗(yàn)表明：該算法在抗干擾性、定位的精度和定位誤差等方面都有所優(yōu)化，本算法是一種有效處理節(jié)點(diǎn)定位的算法。

1 定位算法模型介紹

1.1 RSSI測(cè)距原理

RSSI測(cè)距即測(cè)量發(fā)送節(jié)點(diǎn)和接收節(jié)點(diǎn)之間的距離，通常采用信號(hào)強(qiáng)度或接收功率來測(cè)量，而無線射頻信號(hào)是這類測(cè)量的常用方法[4]；考慮到在實(shí)際環(huán)境中，無線信號(hào)是受到多路徑、散射等的影響，故在這里使用Shadowing模型作為無線信號(hào)傳播路徑損耗模型。如下式：

(1)

其中，發(fā)射節(jié)點(diǎn)到接收節(jié)點(diǎn)的距離為d；參考距離為d0；η為衰減指數(shù)，通常取2～4；Pd為距發(fā)射節(jié)點(diǎn)d處的信號(hào)強(qiáng)度；P0為參考距離d0處的接收信號(hào)功率；Xσ是均值為零、方差為σ的高斯隨機(jī)噪聲；在應(yīng)用中常常忽略Xσ的影響，并取參考距離=1 m，于是得到常用的基于RSSI的測(cè)距公式如下：

Pd=A-10ηlgd

(2)

其中A為距發(fā)射節(jié)點(diǎn)1 m處的接收信號(hào)功率[4]。

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

傳統(tǒng)的質(zhì)心定位算法是一種僅基于連通性、與距離無關(guān)的定位算法，該算法簡(jiǎn)單、實(shí)現(xiàn)難度低，算法的基本思想如下：未知節(jié)點(diǎn)首先確定在其網(wǎng)絡(luò)通信范圍內(nèi)有哪些信標(biāo)節(jié)點(diǎn)，然后把這些信標(biāo)節(jié)點(diǎn)作為頂點(diǎn)構(gòu)成多邊形，最后根據(jù)這個(gè)多邊形的質(zhì)心來估計(jì)未知節(jié)點(diǎn)的位置[5-6]。

在傳統(tǒng)的質(zhì)心定位算法中把多邊形的質(zhì)心當(dāng)作未知節(jié)點(diǎn)，這種做法的精確度與信標(biāo)節(jié)點(diǎn)的密度以及信標(biāo)節(jié)點(diǎn)的分布是否均勻都有著直接的關(guān)系，當(dāng)信標(biāo)節(jié)點(diǎn)的密度較低且分布不均勻時(shí)，常見的特別是在多邊形為非對(duì)稱不規(guī)則的凹多邊形時(shí)，如圖1所示。

圖1 凹多邊形下的質(zhì)心定位圖

顯然此時(shí)多邊形的質(zhì)心與未知節(jié)點(diǎn)相差甚遠(yuǎn)，在這種情況下使用此算法獲得的未知節(jié)點(diǎn)坐標(biāo)的精度明顯降低，所以基于此，本文提出了一種改進(jìn)的基于RSSI的質(zhì)心定位算法。算法的基本思想如下：如上所述，以信標(biāo)節(jié)點(diǎn)作為頂點(diǎn)構(gòu)成多邊形，對(duì)此多邊形作如下操作：如果是凹多邊形，通過剔除頂點(diǎn)的方式轉(zhuǎn)變?yōu)檩^為規(guī)則的凸多邊形；如果是凸多邊形則不變。然后以質(zhì)心定位算法為基礎(chǔ)，依次將RSSI引入，起輔助信息的作用，為每一個(gè)信標(biāo)節(jié)點(diǎn)增加權(quán)值，反映不同信標(biāo)節(jié)點(diǎn)對(duì)未知節(jié)點(diǎn)的影響。所以未知節(jié)點(diǎn)的預(yù)測(cè)坐標(biāo)計(jì)算如式(3)：

(3)

故先構(gòu)成凸多邊形，然后在傳統(tǒng)的質(zhì)心定位算法中引入RSSI數(shù)據(jù)信息，從而提高預(yù)測(cè)坐標(biāo)的精度。算法示意如圖2及其應(yīng)用過程如下：

圖2 改進(jìn)的質(zhì)心定位原理圖

(1) 信標(biāo)節(jié)點(diǎn)周期性地向鄰居節(jié)點(diǎn)廣播身的ID和位置信息的信號(hào)；當(dāng)未知節(jié)點(diǎn)O接收到這些信息后將其儲(chǔ)存，當(dāng)收到某個(gè)信標(biāo)節(jié)點(diǎn)的信號(hào)數(shù)量超過預(yù)先設(shè)定的閾值后，該節(jié)點(diǎn)認(rèn)為與此信標(biāo)節(jié)點(diǎn)連通，并取該信標(biāo)節(jié)點(diǎn)RSSI的均值。

(2) 由上一步得到信標(biāo)節(jié)點(diǎn)的集合：B_set=(b1,b2,…,bk)；通過凸多邊形的所有邊中，任意一條邊向兩方無限延長(zhǎng)成為一條直線時(shí)，其他各邊及頂點(diǎn)都在此直線的同旁的原則，將此集合中的節(jié)點(diǎn)構(gòu)成凸多邊形(ABCDE)。

(3) 然后將RSSI值轉(zhuǎn)換為距離值，即距離集合：D_set=(d1,d2,…,dk)，以及凸多邊形(ABCDE)的頂點(diǎn)坐標(biāo)值代入式(3)中進(jìn)行計(jì)算，從而得到未知節(jié)點(diǎn)O的預(yù)測(cè)值。

1.3 坐標(biāo)誤差校正算法

在以下的仿真實(shí)驗(yàn)中可見，以上改進(jìn)的基于RSSI測(cè)距的質(zhì)心定位算法比傳統(tǒng)的質(zhì)心定位算法精度更高，而且它的算法復(fù)雜度更低，但如果在要求精度更高的應(yīng)用環(huán)境下，以上算法還不能滿足；為了使坐標(biāo)定位更精確，最后再提出一種對(duì)坐標(biāo)進(jìn)行誤差校正的算法；在現(xiàn)有校正算法如三角形質(zhì)心定位的誤差校正的算法中，通常引入一個(gè)校正節(jié)點(diǎn)，此校正節(jié)點(diǎn)一般取離未知節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)，由于未知節(jié)點(diǎn)與校正節(jié)點(diǎn)距離很近，可以近似認(rèn)為兩者的誤差因子影響一致，因而利用校正節(jié)點(diǎn)的校正因子代替未知節(jié)點(diǎn)的誤差因子[7-9]。

以上算法得到的校正因子在一定程度上能夠校正1.2節(jié)中得到的預(yù)測(cè)坐標(biāo)，但是在環(huán)境干擾過大以及其他不確定的因素下，誤差因子由某一個(gè)節(jié)點(diǎn)確定難免會(huì)帶來更大的誤差，故本文提出利用1.2節(jié)中的凸多邊形內(nèi)的所有的信標(biāo)節(jié)點(diǎn)作為校正節(jié)點(diǎn)，然后對(duì)預(yù)測(cè)坐標(biāo)進(jìn)行校正計(jì)算，此校正算法更為可靠及有效地避免上類問題的出現(xiàn)。本文提出的改進(jìn)的誤差校正算法如下：

(4)

可得相應(yīng)的測(cè)距誤差因子(αf1、αf2、αf3、…)。

(5)

通過上式可得對(duì)應(yīng)信標(biāo)節(jié)點(diǎn)A的校正因子βA，按照以上兩步可得校正因子βB、βC、βD、βE。因而利用校正節(jié)點(diǎn)的校正因子代替未知節(jié)點(diǎn)的誤差因子。而將校正因子βA、βB、βC、βD、βE代入加權(quán)質(zhì)心定位算法即可得到測(cè)距誤差校正公式：

(6)

2 基于RSSI測(cè)距的誤差校正改進(jìn)的定位算法

正如1.2節(jié)中所述，在傳統(tǒng)的基于RSSI的質(zhì)心定位算法中，當(dāng)由未知節(jié)點(diǎn)通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)構(gòu)成的多邊形是凸多邊形時(shí)，會(huì)提高定位的精度，故提出將多邊形轉(zhuǎn)為凸多邊形；而常用的誤差校正方法存在環(huán)境干擾的偶然性過大及相關(guān)的不確定因素存在，故本文提出了一種更可靠以及更有效的誤差校正算法以避免上類問題的出現(xiàn)。算法過程及流程如圖3所示。

圖3 基于RSSI測(cè)距的改進(jìn)的質(zhì)心算法流程圖

首先通過已確定的未知節(jié)點(diǎn)接收信標(biāo)節(jié)點(diǎn)的信號(hào)數(shù)量的閾值判斷節(jié)點(diǎn)之間的連通性，然后使用與未知節(jié)點(diǎn)連通的信標(biāo)節(jié)點(diǎn)構(gòu)造多邊形，接著使多邊形向凸多邊形轉(zhuǎn)變。凸多邊形的所有邊中，任意一條邊向兩方無限延長(zhǎng)成為一條直線時(shí)，其他各邊及頂點(diǎn)都在此直線的同旁，然后利用RSSI計(jì)算未知節(jié)點(diǎn)與信標(biāo)節(jié)點(diǎn)的距離，將以上信息代入式(3)中得到未知節(jié)點(diǎn)的預(yù)測(cè)坐標(biāo)值，在對(duì)定位精度要求不高的應(yīng)用環(huán)境中，此種方法已滿足；在定位精度更高的環(huán)境下，則可以將校正因子代入式(3)，即利用凸多邊形內(nèi)的信標(biāo)節(jié)點(diǎn)作為校正節(jié)點(diǎn)，由這些校正節(jié)點(diǎn)得到相對(duì)應(yīng)的校正因子，通過添加權(quán)重因子綜合所有的校正因子來替換未知節(jié)點(diǎn)的測(cè)距誤差因子，對(duì)測(cè)距誤差進(jìn)行補(bǔ)償，最后利用加權(quán)質(zhì)心方法確定定位(式(6))，從而得到未知節(jié)點(diǎn)的最終坐標(biāo)。

3 仿真實(shí)驗(yàn)與分析

3.1 仿真環(huán)境

傳感器節(jié)點(diǎn)隨機(jī)分布在100 m×100 m的監(jiān)測(cè)區(qū)域內(nèi)，200個(gè)未知節(jié)點(diǎn)隨機(jī)分布在平面內(nèi)，通信半徑設(shè)為20 m,通過Matlab對(duì)實(shí)驗(yàn)環(huán)境進(jìn)行模擬并對(duì)數(shù)據(jù)進(jìn)行分析。本仿真實(shí)驗(yàn)分兩部分，首先驗(yàn)證改進(jìn)的質(zhì)心定位算法能否有效地提高定位精度，然后驗(yàn)證誤差校正算法在有環(huán)境干擾的情況下定位的精度是否更加穩(wěn)定和可靠。

3.2 實(shí)驗(yàn)結(jié)果與分析

首先實(shí)驗(yàn)驗(yàn)證改進(jìn)的質(zhì)心定位算法能否提高定位的精度。將改進(jìn)的算法與傳統(tǒng)的質(zhì)心定位算法做對(duì)比，實(shí)驗(yàn)在無環(huán)境干擾的情況下進(jìn)行，在同一網(wǎng)絡(luò)環(huán)境下重復(fù)實(shí)驗(yàn)50次，每次實(shí)驗(yàn)都將所有節(jié)點(diǎn)重置，對(duì)50次實(shí)驗(yàn)結(jié)果求均值，分別在信標(biāo)節(jié)點(diǎn)分布情況不同的條件下進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)結(jié)果如下所示：在圖4中可見，在信標(biāo)節(jié)點(diǎn)分布均勻的情況下，改進(jìn)的質(zhì)心定位算法并沒有有效地降低定位誤差，而如圖5在信標(biāo)節(jié)點(diǎn)分布不均勻的情況下，隨著信標(biāo)節(jié)點(diǎn)的數(shù)量從20增加到80，傳統(tǒng)的質(zhì)心定位算法的定位誤差從39.24%下降到26.28%，改進(jìn)的算法的定位誤差從27.89%下降到17.73%；改進(jìn)算法有明顯降低誤差的效果，而且從兩個(gè)圖中可以看到，改進(jìn)算法的誤差曲線波動(dòng)更小，更穩(wěn)定，受信標(biāo)節(jié)點(diǎn)分布情況的影響更小。

圖4 在信標(biāo)節(jié)點(diǎn)分布均勻的情況下

圖5 在信標(biāo)節(jié)點(diǎn)分布不均勻的情況下

接著在同樣的環(huán)境下，增加環(huán)境干擾，對(duì)比基于RSSI的誤差校正的三角形質(zhì)心定位算法和本文提出的基于RSSI誤差校正質(zhì)心定位算法。對(duì)比兩種算法之間的誤差分布對(duì)比圖如圖6所示：在此實(shí)驗(yàn)中固定信標(biāo)節(jié)點(diǎn)為40個(gè)，此處使用的環(huán)境干擾為高斯白噪聲，在MATLAB中產(chǎn)生此噪聲非常方便，對(duì)某一局部進(jìn)行干擾，此干擾的影響是RSSI的測(cè)距的誤差逐漸變大，對(duì)定位造成影響；故在實(shí)驗(yàn)中不斷加大環(huán)境干擾，分析在此情況下兩種算法的穩(wěn)定性和可靠性。實(shí)驗(yàn)結(jié)果如下所示：隨著噪聲干擾的逐漸增大，兩種定位算法的誤差都逐漸增大，但顯然基于RSSI的誤差校正的三角形質(zhì)心定位算法的誤差增大的幅度比本文提出的算法更快，而且誤差也更大。

圖6 兩種誤差校正定位方法的對(duì)比

由以上兩個(gè)實(shí)驗(yàn)驗(yàn)證了以上的理論，改進(jìn)的基于RSSI的質(zhì)心定位算法相對(duì)于傳統(tǒng)的質(zhì)心定位算法的定位精度更高，而基于此算法的誤差校正算法的精度和穩(wěn)定性、可靠性都有所提高?？傊倪M(jìn)的算法可以有效地提高測(cè)距的精度和增強(qiáng)定位的穩(wěn)定性和可靠性，從而更加適用于無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位。

4 結(jié) 語

本文在研究定位算法的基礎(chǔ)上，提出一種改進(jìn)的基于RSSI測(cè)距的質(zhì)心定位算法和其誤差校正的定位算法。即通過未知節(jié)點(diǎn)通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)構(gòu)造凸多邊形，通過RSSI測(cè)距利用加權(quán)質(zhì)心算法對(duì)未知節(jié)點(diǎn)定位。在此算法的基礎(chǔ)上，利用凸多邊形內(nèi)的信標(biāo)節(jié)點(diǎn)得到校正因子，對(duì)RSSI的距離信息進(jìn)行校正，得到最終的坐標(biāo)值。該算法不僅在提高定位的精度方面有很好的效果，而且在抗干擾、穩(wěn)定性和可靠性上都有很好的表現(xiàn)。基于仿真實(shí)驗(yàn)表明：本文提出的改進(jìn)算法不但能提高節(jié)點(diǎn)的測(cè)距精度，滿足節(jié)點(diǎn)的定位，同時(shí)還有良好的抗干擾能力和可靠性。

[1] 鄭軍, 張寶賢. 無線傳感器網(wǎng)絡(luò)技術(shù)[M]. 北京：機(jī)械工業(yè)出版社, 2012.

[2] Erramilli V, Malta I, Bestavros A. On the interaction between data aggregation and topology control in wireless sensor networks[C]//Proceedings of the 1st Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2004:557-565.

[3] 張嬋愛, 馬艷艷, 白鳳娥, 等. 基于RSSI的加權(quán)質(zhì)心定位算法的實(shí)現(xiàn)[J]. 太原理工大學(xué)學(xué)報(bào), 2009, 40(2):146-147,199.

[4] 馬祖長(zhǎng), 孫怡寧. 無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的定位算法[J]. 計(jì)算機(jī)工程, 2004, 30(7):13-14,48.

[5] 詹杰, 吳伶錫, 唐志軍. 無線傳感器網(wǎng)絡(luò)RSSI測(cè)距方法與精度分析[J]. 電訊技術(shù), 2010, 50(4):83-87.

[6] 楊寧, 鐘紹山, 徐耀良, 等. 一種改進(jìn)高斯-卡爾曼濾波的RSSI處理算法[J]. 自動(dòng)化儀表, 2013, 34(7):6-8,11.

[7] 劉政. 基于接收信號(hào)強(qiáng)度指示的誤差校正定位算法[J]. 傳感技術(shù)學(xué)報(bào), 2014, 27(7):970-975.

[8] 朱博, 陳曙. 一種無線傳感器網(wǎng)絡(luò)質(zhì)心定位改進(jìn)算法[J]. 傳感技術(shù)學(xué)報(bào), 2010, 23(6):868-872.

[9] 李娟, 王珂, 李莉, 等. 基于錨圓交點(diǎn)加權(quán)質(zhì)心的無線傳感器網(wǎng)絡(luò)定位算法[J]. 吉林大學(xué)學(xué)報(bào)(工學(xué)版), 2009, 39(6):1649-1653.

[10] 張春園, 劉興長(zhǎng), 張偉偉, 等. 基于6LowPAN的RSSI測(cè)距方法優(yōu)化[J]. 自動(dòng)化與儀器儀表, 2014(11):151-154.

[11] 王振朝, 張琦, 張峰. 基于RSSI測(cè)距的改進(jìn)加權(quán)質(zhì)心定位算法[J]. 電測(cè)與儀表, 2014, 51(21):63-66.

[12] 文春武, 宋杰, 姚家振. 基于RSSI校正的無線傳感器網(wǎng)絡(luò)定位算法[J]. 傳感器與微系統(tǒng), 2014, 33(12):134-136,145.

AN IMPROVED CENTROID LOCALIZATION AND ERROR CORRECTION ALGORITHM

Du Shihuai Song Jie

(ScoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

In order to make the error of node location as small as possible and more effective and reliable in the error correction process, an improved centroid location algorithm is proposed in the case of nonuniform beacon distribution. The algorithm firstly determines the beacon nodes in the communication range of unknown nodes, and then takes some of these beacon nodes as vertices to form convex polygons. The distance between the unknown node and each vertex of the convex polygon is obtained through the RSSI. Then all the beacon nodes in the convex polygon of the center of mass are taken as correction nodes, and the corresponding correction factors are obtained by these correction nodes. By adding the weighting factor, all the correction factors are combined to replace the ranging error factor of the unknown node, and the error of the ranging is compensated. Finally, the final position of the unknown node is determined by the weighted centroid localization method. Simulation results show that the algorithm has stronger anti-jamming capability than other localization algorithms in the 100 m×100 m monitoring area, and the average positioning error is reduced by at least 12% when the beacon nodes are distributed unevenly, the algorithm is a more accurate location algorithm.

Node localization RSSI Centroid localization algorithm Convex polygon Correction factor Compensation

2016-01-29。杜士懷，碩士生，主研領(lǐng)域：無線傳感器網(wǎng)絡(luò)。宋杰,副教授。

TP393

A

10.3969/j.issn.1000-386x.2017.05.020