一種改進的質心定位及誤差校正算法

杜士懷 宋 杰

(安徽大學計算機科學與技術學院 安徽 合肥 230601)

一種改進的質心定位及誤差校正算法

杜士懷 宋 杰

(安徽大學計算機科學與技術學院 安徽 合肥 230601)

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

節(jié)點定位 接收的信號強度指示 質心定位算法 凸多邊形 校正因子 補償

0 引 言

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

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

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

1 定位算法模型介紹

1.1 RSSI測距原理

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

(1)

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

Pd=A-10ηlgd

(2)

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

1.2 改進的質心定位算法

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

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

圖1 凹多邊形下的質心定位圖

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

(3)

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

圖2 改進的質心定位原理圖

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

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

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

1.3 坐標誤差校正算法

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

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

(4)

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

(5)

通過上式可得對應信標節(jié)點A的校正因子βA，按照以上兩步可得校正因子βB、βC、βD、βE。因而利用校正節(jié)點的校正因子代替未知節(jié)點的誤差因子。而將校正因子βA、βB、βC、βD、βE代入加權質心定位算法即可得到測距誤差校正公式：

(6)

2 基于RSSI測距的誤差校正改進的定位算法

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

圖3 基于RSSI測距的改進的質心算法流程圖

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

3 仿真實驗與分析

3.1 仿真環(huán)境

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

3.2 實驗結果與分析

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

圖4 在信標節(jié)點分布均勻的情況下

圖5 在信標節(jié)點分布不均勻的情況下

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

圖6 兩種誤差校正定位方法的對比

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

4 結 語

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

[1] 鄭軍, 張寶賢. 無線傳感器網(wǎng)絡技術[M]. 北京：機械工業(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的加權質心定位算法的實現(xiàn)[J]. 太原理工大學學報, 2009, 40(2):146-147,199.

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

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

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

[7] 劉政. 基于接收信號強度指示的誤差校正定位算法[J]. 傳感技術學報, 2014, 27(7):970-975.

[8] 朱博, 陳曙. 一種無線傳感器網(wǎng)絡質心定位改進算法[J]. 傳感技術學報, 2010, 23(6):868-872.

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

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

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

[12] 文春武, 宋杰, 姚家振. 基于RSSI校正的無線傳感器網(wǎng)絡定位算法[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。杜士懷，碩士生，主研領域：無線傳感器網(wǎng)絡。宋杰,副教授。

TP393

A

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