RSSI-Based Differential Correction Least-Squares-Quasi-Newton Positioning Algorithm*

CHENG Xiuzhi，ZHU Darong，ZHANG Shen，ZHU Guang

(1.School of Mechanical and Electrical Engineering，Anhui Jianzhu University，Hefei230022，China; 2.CUMT-IoT Perception Mine Research Center，Xuzhou Jiangsu 221008，China)

RSSI-Based Differential Correction Least-Squares-Quasi-Newton Positioning Algorithm*

CHENG Xiuzhi1，ZHU Darong1，ZHANG Shen2*，ZHU Guang1

(1.School of Mechanical and Electrical Engineering，Anhui Jianzhu University，Hefei230022，China; 2.CUMT-IoT Perception Mine Research Center，Xuzhou Jiangsu 221008，China)

A least－squares differential correction based on RSSI－Newton location algorithm is presented in accordance with the low positioning accuracy lying in the Wireless Sensor Network(WSN)in this paper.In terms of RSSI ranging，correction coefficient had been firstly acquired by self－correcting of beacon nodes，and then had been applied to distance solving from unknown nodes to the beacon nodes;in terms of positioning calculations，utilizing character of simpleness of LS and the fast rate of convergence of Quasi－Newton algorithm，the initial value worked out by Quasi－Newton algorithm had been applied for the iterative refinement of unknown node coordinate with LS method.The simulation experiment showed that the accuracy of positioning algorithm presented is36%higher compared with the traditional LSmethod.

WSN;received signal strength indication;least squares;quasi－Newton method;differential correction

節(jié)點(diǎn)定位是WSN的關(guān)鍵技術(shù)，定位的精度對(duì)其所監(jiān)測(cè)的區(qū)域有著至關(guān)重要的影響。傳統(tǒng)的獲取節(jié)點(diǎn)位置的信息主要采用GPS定位方法來(lái)實(shí)現(xiàn)，但是考慮到價(jià)格、體積、能耗等方面的因素，GPS定位不可能大規(guī)模的布置在監(jiān)測(cè)區(qū)域，因此有必要采取簡(jiǎn)單有效的定位算法來(lái)滿足大多數(shù)WSN應(yīng)用場(chǎng)合的需求［1］。

目前，針對(duì)WSN提出的定位算法大體可以分為兩類(lèi)［2－6］:基于距離的定位算法(Range－Based)和與距離無(wú)關(guān)的定位算法(Range－Free)［3］。前者需要測(cè)量相鄰節(jié)點(diǎn)間的絕對(duì)距離或者角度信息［4］，使用較多的測(cè)距定位技術(shù)有RSSI，TDOA，AOA，TOA［5］;后者需知道傳感器網(wǎng)絡(luò)的連通性等信息［6］。其中，RSSI具有定位算法簡(jiǎn)單、成本低、功耗小且無(wú)需額外的硬件等優(yōu)勢(shì)被廣泛應(yīng)用。但在實(shí)際環(huán)境中，基于RSSI的測(cè)距技術(shù)受環(huán)境的影響非常大，使得該技術(shù)在環(huán)境惡劣的情況下，定位誤差較大，精度不高。在定位計(jì)算上，由于最小二乘法在定位過(guò)程中可能存在非奇異矩陣，導(dǎo)致最小二乘法估計(jì)出來(lái)的未知節(jié)點(diǎn)坐標(biāo)不僅誤差大，而且定位精度的穩(wěn)定性差，甚至出現(xiàn)錯(cuò)誤的結(jié)果。

近年來(lái)許多國(guó)內(nèi)外學(xué)者提出很多針對(duì)RSSI技術(shù)的定位算法，文獻(xiàn)［7］提出了距離未知節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)作為參考節(jié)點(diǎn)對(duì)RSSI測(cè)距進(jìn)行差分校正。文獻(xiàn)［8］采用了混合濾波的方法對(duì)RSSI的值進(jìn)行優(yōu)化。文獻(xiàn)［9］首先通過(guò)加權(quán)的方式優(yōu)化RSSI值，然后將粒子群算法應(yīng)用到定位計(jì)算中。然而在實(shí)際環(huán)境中，基于RSSI的測(cè)距技術(shù)受環(huán)境的影響非常大，若只對(duì)RSSI值進(jìn)行優(yōu)化，定位誤差依然很大，即便有些方法在定位過(guò)程中通過(guò)智能優(yōu)化算法計(jì)算，但對(duì)初值依賴(lài)較大，容易陷入局部最優(yōu)解，導(dǎo)致定位精度的誤差很大?；诖?，本文提出了一種基于RSSI差分校正的最小二乘－擬牛頓定位算法。測(cè)距階段，該算法主要是利用信標(biāo)節(jié)點(diǎn)的定位誤差，對(duì)未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離進(jìn)行修正;定位階段，將最小二乘法估計(jì)出來(lái)的未知節(jié)點(diǎn)坐標(biāo)，作為擬牛頓法的初值，對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行迭代求精。

第1節(jié)中給出并討論了無(wú)線電損耗模型、給出了差分校正的方法及信標(biāo)節(jié)點(diǎn)自動(dòng)校正的定位過(guò)程。第2節(jié)介紹了本文中最小二乘－擬牛頓法的具體實(shí)現(xiàn)過(guò)程。第3節(jié)通過(guò)本文提出的算法與其他算法仿真實(shí)驗(yàn)，從各個(gè)方面對(duì)本文算法進(jìn)行評(píng)價(jià)。最后，給出本文的總結(jié)。

1 基于差分校正的無(wú)線電傳播損耗模型

1.1 無(wú)線電傳播損耗模型

在無(wú)線傳感器網(wǎng)絡(luò)定位算法中，常用的測(cè)距技術(shù)有RSSI定位技術(shù)［10］。一方面，傳感器本身的通信功能及其具有的RSSI測(cè)量功能使得測(cè)距簡(jiǎn)單。但另一方面，當(dāng)定位環(huán)境中存在較嚴(yán)重的多徑效應(yīng)、反射、折射等干擾時(shí)，RSSI的測(cè)量誤差就會(huì)很大，定位誤差也隨之增大。目前常用的信號(hào)傳播模型主要有自由空間傳播損耗模型與對(duì)數(shù)－常態(tài)分布模型。

自由空間傳播損耗模型:

式中，P(d0)是無(wú)線電傳播距離d0的路徑損耗，k為路徑損耗因子，通常取2～5之間，f為信號(hào)的頻率。

對(duì)數(shù)－常態(tài)分布模型:

式中，P(d)是傳輸距離為d的路徑損耗，P(d0)是傳輸距離為d0=1 m時(shí)的路徑損耗，ξn為均值為0的高斯隨機(jī)分布函數(shù)。

節(jié)點(diǎn)接收信標(biāo)節(jié)點(diǎn)的信號(hào)強(qiáng)度為:

式中，RSSI為接收到的功率，Psend為發(fā)射功率，Pamplify為天線增益，通過(guò)式(1)～式(3)可求節(jié)點(diǎn)間的距離d。

實(shí)際環(huán)境中由于障礙物等環(huán)境因素的影響，測(cè)距出來(lái)的RSSI值并不能直接滿足無(wú)線電傳播損耗模型，若仍采用該模型而不對(duì)RSSI的值進(jìn)行修正［9］就會(huì)引起定位精度偏低。本文利用離未知節(jié)點(diǎn)最近的信標(biāo)節(jié)點(diǎn)在定位過(guò)程中產(chǎn)生的校正系數(shù)反饋給未知節(jié)點(diǎn)，未知節(jié)點(diǎn)通過(guò)該誤差校正系數(shù)求出到信標(biāo)節(jié)點(diǎn)的校正距離。該方法從測(cè)距存在的誤差方面對(duì)算法進(jìn)行改進(jìn)，從根本上減小了對(duì)定位結(jié)果的影響，因而能夠提高定位精度。

1.2 信標(biāo)節(jié)點(diǎn)的自校正定位過(guò)程

如圖1所示，信標(biāo)節(jié)點(diǎn)A0(x0，y0)距離未知節(jié)點(diǎn)O最近，該信標(biāo)節(jié)點(diǎn)距其通信范圍內(nèi)的信標(biāo)節(jié)點(diǎn)A1(x1，y1)、A2(x2，y2)、……Ai(xi，yi)的實(shí)際距離為d01，d02，d03，…，d0i，信標(biāo)節(jié)點(diǎn)A0(x0，y0)通過(guò)RSSI測(cè)距所得到的與其他信標(biāo)節(jié)點(diǎn)間估計(jì)距離分別為^d01，^d02，^d03，…，^d0i，令^A0(^x0，^y0)為差分信標(biāo)節(jié)點(diǎn)。

圖1 信標(biāo)節(jié)點(diǎn)的差分校正定位示意圖

(1)信標(biāo)節(jié)點(diǎn)的校正系數(shù):

式中，n是未知節(jié)點(diǎn)通信半徑內(nèi)的所有信標(biāo)節(jié)點(diǎn)個(gè)數(shù)。傳感器網(wǎng)絡(luò)中的其他信標(biāo)節(jié)點(diǎn)也可以通過(guò)以上方法獲得自身的校正系數(shù)，以便對(duì)其最近的未知節(jié)點(diǎn)進(jìn)行校正。β表示使用信標(biāo)節(jié)點(diǎn)的信息測(cè)量RSSI值時(shí)的差分校正系數(shù)。

(2)信標(biāo)節(jié)點(diǎn)到未知節(jié)點(diǎn)的校正距離:

式中，di是差分校正后的未知節(jié)點(diǎn)的估計(jì)距離;d0'i是未知節(jié)點(diǎn)O到信標(biāo)節(jié)點(diǎn)的測(cè)量距離;β是信標(biāo)節(jié)點(diǎn)的校正系數(shù)。

2 最小二乘－擬牛頓法

2.1 最小二乘法［11］

在WSN中，若未知節(jié)點(diǎn)獲得3個(gè)或者3個(gè)以上能夠與其相互通信的信標(biāo)節(jié)點(diǎn)的信息，則執(zhí)行三邊定位法或最大似然估計(jì)法即能夠求出未知節(jié)點(diǎn)的估計(jì)坐標(biāo)。假設(shè)某一未知節(jié)點(diǎn)p坐標(biāo)為(x，y)測(cè)得到m個(gè)信標(biāo)節(jié)點(diǎn)的距離，第i個(gè)信標(biāo)節(jié)點(diǎn)的坐標(biāo)為(xi，yi)，未知節(jié)點(diǎn)p到信標(biāo)節(jié)點(diǎn)i的距離為di。假設(shè)有n個(gè)未知節(jié)點(diǎn)，則未知節(jié)點(diǎn)p的坐標(biāo)可以根據(jù)式(6)方程組估計(jì)。

上述方程組可以轉(zhuǎn)化為AX=b的形式。其中，

因此，方程AX=b利用最小二乘法解未知節(jié)點(diǎn)的估計(jì)坐標(biāo)為:~X=(ATA)－1ATb。

2.2 利用擬牛頓法對(duì)未知節(jié)點(diǎn)坐標(biāo)迭代求精

在定位計(jì)算方面，利用最小二乘法可求出未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，但是在某些異常情況下，逆矩陣(ATA)－1估計(jì)無(wú)法實(shí)現(xiàn)，從而導(dǎo)致求解未知節(jié)點(diǎn)坐標(biāo)失敗［12］。

擬牛頓法是一種高效的求解優(yōu)化問(wèn)題的方法，該算法收斂速度快、定位精度高，因此被廣泛應(yīng)用在求解優(yōu)化問(wèn)題的算法中［13］。

本文采用最小二乘法和無(wú)約束擬牛頓法相結(jié)合的算法求解未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，即首先通過(guò)最小二乘法獲得未知節(jié)點(diǎn)的估計(jì)坐標(biāo)，然后把估計(jì)值作為擬牛頓算法的初值，進(jìn)一步對(duì)未知節(jié)點(diǎn)坐標(biāo)迭代求精。因此，可以將定位問(wèn)題轉(zhuǎn)換為求非線性最小二乘優(yōu)化問(wèn)題，通常也叫做無(wú)約束的極小平方和函數(shù)問(wèn)題，即:

式中，xi，yi分別為信標(biāo)節(jié)點(diǎn)i的橫坐標(biāo)和縱坐di為未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)i的距離。對(duì)于本文中求解未知節(jié)點(diǎn)的坐標(biāo)，即求F(x，y)，x∈R+且y∈R+的最優(yōu)解X*(x*，y*)。

采用最小二乘－擬牛頓法求解未知節(jié)點(diǎn)坐標(biāo)的步驟如下:

步驟1:通過(guò)最小二乘法求得未知坐標(biāo)的估計(jì)值X，將估計(jì)值X作為擬牛頓算法的初始值X(0)， H0∈Rn×n，0≤ε≤1，K=0;

步驟2:如果‖gk‖≤‖▽F(X(k))‖≤ε，停止計(jì)算，否則計(jì)算dk∈－Hkgk;

步驟3:沿著dk方向進(jìn)行線性搜索，并求ak，接著令xk+1=xk+akdk;

步驟4:校正Hk+1=Hk，使擬牛頓條件成立;

步驟5:令K=K+1，重復(fù)步驟二。

3 仿真結(jié)果與分析

本文利用MATLAB平臺(tái)對(duì)改進(jìn)后的定位算法進(jìn)行仿真分析，并同相關(guān)方法進(jìn)行了對(duì)比，驗(yàn)證本文提出的算法性能。

3.1 仿真參數(shù)設(shè)置及相關(guān)定義

本文將原始的RSSI測(cè)距結(jié)合最小二乘的算法記為RSSI，將文獻(xiàn)［9］通過(guò)粒子群優(yōu)化算法對(duì)加權(quán)質(zhì)心定位算法的改進(jìn)記為RSSI－WP，將最小二乘法和擬牛頓法相結(jié)合的算法改進(jìn)記為最小二乘－擬牛頓改進(jìn)(RSSI－LN)，將RSSI－差分改進(jìn)和最小二乘－擬牛頓改進(jìn)綜合的算法記為本文所述的改進(jìn)算法(RSSI－DLN)。

仿真的網(wǎng)絡(luò)環(huán)境如下:WSN區(qū)域大小為100 m× 100 m，該區(qū)域內(nèi)隨機(jī)布置100個(gè)傳感器節(jié)點(diǎn)(包括未知節(jié)點(diǎn)和信標(biāo)節(jié)點(diǎn))。假設(shè)無(wú)線電信號(hào)的路徑傳播模型的路徑損耗衰減因子k=4.8，無(wú)線信號(hào)載波頻率為2.4 GHz，信道中的隨機(jī)噪聲分布在5～8之間。為了驗(yàn)證算法的穩(wěn)定性，對(duì)該算法進(jìn)行100次仿真并取均值，圖中涉及的相關(guān)定義如下:

(1)設(shè)節(jié)點(diǎn)i的實(shí)際位置為T(mén)i，估計(jì)位置為~Ti，記|Ti－~Ti|為一次網(wǎng)絡(luò)仿真時(shí)節(jié)點(diǎn)i的定位誤差，定義整個(gè)網(wǎng)絡(luò)的平均定位誤差為

式中，K為未知節(jié)點(diǎn)的個(gè)數(shù)，N=100為仿真次數(shù)。

(3)算法的性能評(píng)價(jià)，通常使用均方根RMS (Root Mean Square)［14］作為算法性能的評(píng)價(jià)指標(biāo)，具體公式為:

式中，e(i)為估計(jì)值，r(i)為真實(shí)值，N為錨節(jié)點(diǎn)數(shù)目，M=1。

3.2 仿真結(jié)果分析

圖2仿真了通信半徑為30、信標(biāo)節(jié)點(diǎn)為20時(shí)，傳統(tǒng)定位算法(RSSI)與本文中改進(jìn)算法(RSSIDLN)的未知坐標(biāo)偏差圖。從圖2中可以看出，RSSI－DLN算法比RSSI測(cè)距算法的定位精度高很多，RSSI－DLN的定位精度偏差大體分布在4 m左右。

圖2未知坐標(biāo)偏差圖

圖3 仿真了通信半徑為30時(shí)，4種不同方法的歸一化平均定位誤差。從圖3中可以看出，隨著信標(biāo)節(jié)點(diǎn)個(gè)數(shù)的增多，提供給求取RSSI值的有用信息也都越來(lái)越多，定位誤差首先快速下降，然后緩慢下降。RSSI－DLN算法比傳統(tǒng)RSSI測(cè)距算法提高了約28%～36%的定位精度，比RSSI－WP算法提高了近16%的定位精度。

圖3歸一化平均定位誤差圖

圖4 仿真了信標(biāo)節(jié)點(diǎn)為20、通信半徑為30時(shí)，平均定位誤差隨通信半徑變化比例之間的關(guān)系。從圖4中可以看出，通信半徑小于15時(shí)，4種算法的平均定位誤差基本接近，這是由于通信半徑過(guò)小導(dǎo)致很多未知節(jié)點(diǎn)無(wú)法定位。隨著通信半徑的增加本文提出的算法優(yōu)勢(shì)越來(lái)越明顯，比RSSI提高了近36%的定位精度。從圖4中還可以看出，4種定位算法的平均定位誤差都隨著通信半徑的增大先減小而后緩慢回升，說(shuō)明通信半徑并不是越大越好。因此，在大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)定位算法中，選取最優(yōu)的通信半徑十分重要，本文所述的網(wǎng)絡(luò)環(huán)境下最優(yōu)通信半徑為33。

圖4 3種算法的平均定位誤差曲線

表1給出了通信半徑為30時(shí)的算法性能比較，從表中可以看出，平均定位誤差的比較中，本文改進(jìn)算法(RSSI－DLN)比傳統(tǒng)定位算法(RSSI)更低。RSSI－DLN算法的均方根誤差僅為RSSI算法的RSSI－DLN算法在定位精度方面更具有優(yōu)勢(shì)。

表1 算法性能比較

4 結(jié)論

本文提出了一種基于RSSI差分校正的最小二乘－擬牛頓定位算法。該算法充分利用RSSI測(cè)距和定位估計(jì)兩個(gè)方面存在的較大誤差，提出把信標(biāo)節(jié)點(diǎn)在定位過(guò)程中存在的誤差利用到求未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離當(dāng)中以及用擬牛頓法對(duì)最小二乘法估計(jì)出來(lái)的坐標(biāo)進(jìn)行迭代求精。在相同的仿真網(wǎng)絡(luò)環(huán)境下，本文算法在精度和魯棒性上都比傳統(tǒng)算法更優(yōu)，同時(shí)本文提出的定位算法對(duì)硬件的要求不高，滿足了低成本低功耗的要求，具有很高的應(yīng)用價(jià)值。

［1］嵇瑋瑋，劉中.DV－Hop定位算法在隨機(jī)傳感器網(wǎng)絡(luò)中的應(yīng)用研究［J］.電子與信息學(xué)報(bào)，2008，30(4):970－974.

［2］He T，Huang C D，Blum B M，et al.Range－Free Localization Schemes in Large Scale Sensor Networks［C］//Proceedings of the Ninth Annual Intemational Conference on Mobile Computing and Networking SanDiego，United states，2003.81－95.

［3］Kyildiz IF A，Su W，Sankarasubramaniam Y，et al.Wireless Sensor Network a Survey［J］.Computer Networks，2002，38(4):393－425.

［4］楊鳳，史浩山，朱靈波，等.一種基于測(cè)距的無(wú)線傳感器網(wǎng)絡(luò)智能定位算法［J］.傳感技術(shù)學(xué)報(bào)，2008(1):135－140.

［5］林金朝，陳曉冰，劉海波.基于平均跳距修正的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)迭代定位算法［J］.通信學(xué)報(bào)，2009，30(10):107－113.

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

［7］任維政，徐連明，鄧中亮，等.基于RSSI的測(cè)距差分修正定位算法［J］.傳感技術(shù)學(xué)報(bào)，2008，21(7):1247－1250.

［8］陶為戈，朱昳華，賈子彥.基于RSSI混合濾波和最小二乘參數(shù)估計(jì)的測(cè)距算法［J］.傳感技術(shù)學(xué)報(bào)，2012，25(12):1748－1753.

［9］王新芳，張冰，馮友兵.基于粒子群優(yōu)化的改進(jìn)加權(quán)質(zhì)心定位算法［J］.計(jì)算機(jī)工程，2012(1):90－92.

［10］胡詠梅，張歡.一種改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)質(zhì)心定位算法［J］.計(jì)算機(jī)工程與科學(xué)，2012(2):45－49.

［11］劉少飛，趙清華，王華奎.基于平均跳距估計(jì)和位置修正的DV－Hop定位算法［J］.傳感技術(shù)學(xué)報(bào)，2009(8):1155－1158.

［12］Langendoen K，Reijers N.Distributed Localization in Wireless Sensor Networks:A Quantitative Comparison［J］.Computer Networks，2003，43(4):499－518.

［13］史洪宇，燕莎.WSN中一種改進(jìn)的DV－Hop節(jié)點(diǎn)定位算法［J］.電光與控制，2011(4):93－96.

［14］Entenmann R C.A Circuit for Finding the Root Mean Square［J］. Proc IEEE，1964，52(2):193.

程秀芝(1975－)，女，安徽建筑大學(xué)講師，中國(guó)礦業(yè)大學(xué)碩士，目前主要研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)定位技術(shù)與煤礦安全自動(dòng)化;

張申(1957－)，男，中國(guó)礦業(yè)大學(xué)教授，博士，博士生導(dǎo)師，煤炭學(xué)會(huì)資深會(huì)員，國(guó)家863項(xiàng)目初評(píng)專(zhuān)家。目前主要研究方向?yàn)榈V山通信和礦山物聯(lián)網(wǎng)。

基于RSSI差分校正的最小二乘－擬牛頓定位算法*

程秀芝1，朱達(dá)榮1，張申2*，朱廣1

(1.安徽建筑大學(xué)，機(jī)械與電氣工程學(xué)院，合肥230022;2.中國(guó)礦業(yè)大學(xué)物聯(lián)網(wǎng)(感知礦山)研究中心，江蘇徐州221008)

針對(duì)無(wú)線傳感器網(wǎng)絡(luò)(WSN)中存在定位精度不足的問(wèn)題，提出了一種基于RSSI差分校正的最小二乘－擬牛頓定位算法。在RSSI測(cè)距方面，首先通過(guò)信標(biāo)節(jié)點(diǎn)的自校正定位求得誤差校正系數(shù)，將該誤差校正系數(shù)運(yùn)用到求未知節(jié)點(diǎn)到信標(biāo)節(jié)點(diǎn)的距離當(dāng)中。在定位計(jì)算方面，該算法運(yùn)用最小二乘法估計(jì)簡(jiǎn)單和擬牛頓法收斂速度快的特點(diǎn)，將最小二乘法計(jì)算出來(lái)的初值，用擬牛頓法對(duì)未知節(jié)點(diǎn)坐標(biāo)進(jìn)行迭代求精。通過(guò)仿真實(shí)驗(yàn)表明，本文提出的定位算法定位精度高，與傳統(tǒng)的最小二乘法相比提高了近36%的精度。

無(wú)線傳感器網(wǎng)絡(luò);接收信號(hào)強(qiáng)度指示;最小二乘;擬牛頓法;差分校正

TP301.6;TP212

A

1004－1699(2014)01－0123－05

2013－10－23修改日期:2013－12－03

C:6150P

10.3969/j.issn.1004－1699.2014.01.023

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(61073161);省自然科學(xué)基金項(xiàng)目(KJ2012B048);省科技攻關(guān)基金項(xiàng)目(1301022066)