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

節點定位是WSN的關鍵技術，定位的精度對其所監測的區域有著至關重要的影響。傳統的獲取節點位置的信息主要采用GPS定位方法來實現，但是考慮到價格、體積、能耗等方面的因素，GPS定位不可能大規模的布置在監測區域，因此有必要采取簡單有效的定位算法來滿足大多數WSN應用場合的需求［1］。

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

近年來許多國內外學者提出很多針對RSSI技術的定位算法，文獻［7］提出了距離未知節點最近的信標節點作為參考節點對RSSI測距進行差分校正。文獻［8］采用了混合濾波的方法對RSSI的值進行優化。文獻［9］首先通過加權的方式優化RSSI值，然后將粒子群算法應用到定位計算中。然而在實際環境中，基于RSSI的測距技術受環境的影響非常大，若只對RSSI值進行優化，定位誤差依然很大，即便有些方法在定位過程中通過智能優化算法計算，但對初值依賴較大，容易陷入局部最優解，導致定位精度的誤差很大。基于此，本文提出了一種基于RSSI差分校正的最小二乘－擬牛頓定位算法。測距階段，該算法主要是利用信標節點的定位誤差，對未知節點到信標節點的距離進行修正;定位階段，將最小二乘法估計出來的未知節點坐標，作為擬牛頓法的初值，對未知節點坐標進行迭代求精。

第1節中給出并討論了無線電損耗模型、給出了差分校正的方法及信標節點自動校正的定位過程。第2節介紹了本文中最小二乘－擬牛頓法的具體實現過程。第3節通過本文提出的算法與其他算法仿真實驗，從各個方面對本文算法進行評價。最后，給出本文的總結。

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

1.1 無線電傳播損耗模型

在無線傳感器網絡定位算法中，常用的測距技術有RSSI定位技術［10］。一方面，傳感器本身的通信功能及其具有的RSSI測量功能使得測距簡單。但另一方面，當定位環境中存在較嚴重的多徑效應、反射、折射等干擾時，RSSI的測量誤差就會很大，定位誤差也隨之增大。目前常用的信號傳播模型主要有自由空間傳播損耗模型與對數－常態分布模型。

自由空間傳播損耗模型:

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

對數－常態分布模型:

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

節點接收信標節點的信號強度為:

式中，RSSI為接收到的功率，Psend為發射功率，Pamplify為天線增益，通過式(1)～式(3)可求節點間的距離d。

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

1.2 信標節點的自校正定位過程

如圖1所示，信標節點A0(x0，y0)距離未知節點O最近，該信標節點距其通信范圍內的信標節點A1(x1，y1)、A2(x2，y2)、……Ai(xi，yi)的實際距離為d01，d02，d03，…，d0i，信標節點A0(x0，y0)通過RSSI測距所得到的與其他信標節點間估計距離分別為^d01，^d02，^d03，…，^d0i，令^A0(^x0，^y0)為差分信標節點。

圖1 信標節點的差分校正定位示意圖

(1)信標節點的校正系數:

式中，n是未知節點通信半徑內的所有信標節點個數。傳感器網絡中的其他信標節點也可以通過以上方法獲得自身的校正系數，以便對其最近的未知節點進行校正。β表示使用信標節點的信息測量RSSI值時的差分校正系數。

(2)信標節點到未知節點的校正距離:

式中，di是差分校正后的未知節點的估計距離;d0'i是未知節點O到信標節點的測量距離;β是信標節點的校正系數。

2 最小二乘－擬牛頓法

2.1 最小二乘法［11］

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

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

因此，方程AX=b利用最小二乘法解未知節點的估計坐標為:~X=(ATA)－1ATb。

2.2 利用擬牛頓法對未知節點坐標迭代求精

在定位計算方面，利用最小二乘法可求出未知節點的估計坐標，但是在某些異常情況下，逆矩陣(ATA)－1估計無法實現，從而導致求解未知節點坐標失敗［12］。

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

本文采用最小二乘法和無約束擬牛頓法相結合的算法求解未知節點的估計坐標，即首先通過最小二乘法獲得未知節點的估計坐標，然后把估計值作為擬牛頓算法的初值，進一步對未知節點坐標迭代求精。因此，可以將定位問題轉換為求非線性最小二乘優化問題，通常也叫做無約束的極小平方和函數問題，即:

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

采用最小二乘－擬牛頓法求解未知節點坐標的步驟如下:

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

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

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

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

步驟5:令K=K+1，重復步驟二。

3 仿真結果與分析

本文利用MATLAB平臺對改進后的定位算法進行仿真分析，并同相關方法進行了對比，驗證本文提出的算法性能。

3.1 仿真參數設置及相關定義

本文將原始的RSSI測距結合最小二乘的算法記為RSSI，將文獻［9］通過粒子群優化算法對加權質心定位算法的改進記為RSSI－WP，將最小二乘法和擬牛頓法相結合的算法改進記為最小二乘－擬牛頓改進(RSSI－LN)，將RSSI－差分改進和最小二乘－擬牛頓改進綜合的算法記為本文所述的改進算法(RSSI－DLN)。

仿真的網絡環境如下:WSN區域大小為100 m× 100 m，該區域內隨機布置100個傳感器節點(包括未知節點和信標節點)。假設無線電信號的路徑傳播模型的路徑損耗衰減因子k=4.8，無線信號載波頻率為2.4 GHz，信道中的隨機噪聲分布在5～8之間。為了驗證算法的穩定性，對該算法進行100次仿真并取均值，圖中涉及的相關定義如下:

(1)設節點i的實際位置為Ti，估計位置為~Ti，記|Ti－~Ti|為一次網絡仿真時節點i的定位誤差，定義整個網絡的平均定位誤差為

式中，K為未知節點的個數，N=100為仿真次數。

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

式中，e(i)為估計值，r(i)為真實值，N為錨節點數目，M=1。

3.2 仿真結果分析

圖2仿真了通信半徑為30、信標節點為20時，傳統定位算法(RSSI)與本文中改進算法(RSSIDLN)的未知坐標偏差圖。從圖2中可以看出，RSSI－DLN算法比RSSI測距算法的定位精度高很多，RSSI－DLN的定位精度偏差大體分布在4 m左右。

圖2未知坐標偏差圖

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

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

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

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

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

表1 算法性能比較

4 結論

本文提出了一種基于RSSI差分校正的最小二乘－擬牛頓定位算法。該算法充分利用RSSI測距和定位估計兩個方面存在的較大誤差，提出把信標節點在定位過程中存在的誤差利用到求未知節點到信標節點的距離當中以及用擬牛頓法對最小二乘法估計出來的坐標進行迭代求精。在相同的仿真網絡環境下，本文算法在精度和魯棒性上都比傳統算法更優，同時本文提出的定位算法對硬件的要求不高，滿足了低成本低功耗的要求，具有很高的應用價值。

［1］嵇瑋瑋，劉中.DV－Hop定位算法在隨機傳感器網絡中的應用研究［J］.電子與信息學報，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］楊鳳，史浩山，朱靈波，等.一種基于測距的無線傳感器網絡智能定位算法［J］.傳感技術學報，2008(1):135－140.

［5］林金朝，陳曉冰，劉海波.基于平均跳距修正的無線傳感器網絡節點迭代定位算法［J］.通信學報，2009，30(10):107－113.

［6］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005.

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

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

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

［10］胡詠梅，張歡.一種改進的無線傳感器網絡質心定位算法［J］.計算機工程與科學，2012(2):45－49.

［11］劉少飛，趙清華，王華奎.基于平均跳距估計和位置修正的DV－Hop定位算法［J］.傳感技術學報，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中一種改進的DV－Hop節點定位算法［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－)，女，安徽建筑大學講師，中國礦業大學碩士，目前主要研究方向為傳感器網絡定位技術與煤礦安全自動化;

張申(1957－)，男，中國礦業大學教授，博士，博士生導師，煤炭學會資深會員，國家863項目初評專家。目前主要研究方向為礦山通信和礦山物聯網。

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

程秀芝1，朱達榮1，張申2*，朱廣1

(1.安徽建筑大學，機械與電氣工程學院，合肥230022;2.中國礦業大學物聯網(感知礦山)研究中心，江蘇徐州221008)

針對無線傳感器網絡(WSN)中存在定位精度不足的問題，提出了一種基于RSSI差分校正的最小二乘－擬牛頓定位算法。在RSSI測距方面，首先通過信標節點的自校正定位求得誤差校正系數，將該誤差校正系數運用到求未知節點到信標節點的距離當中。在定位計算方面，該算法運用最小二乘法估計簡單和擬牛頓法收斂速度快的特點，將最小二乘法計算出來的初值，用擬牛頓法對未知節點坐標進行迭代求精。通過仿真實驗表明，本文提出的定位算法定位精度高，與傳統的最小二乘法相比提高了近36%的精度。

無線傳感器網絡;接收信號強度指示;最小二乘;擬牛頓法;差分校正

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

項目來源:國家自然科學基金項目(61073161);省自然科學基金項目(KJ2012B048);省科技攻關基金項目(1301022066)