移動錨節(jié)點凸規(guī)劃定位算法研究及改進

任克強,莊放望

(江西理工大學(xué)信息工程學(xué)院,江西 贛州 341000)

?

移動錨節(jié)點凸規(guī)劃定位算法研究及改進

任克強*,莊放望

(江西理工大學(xué)信息工程學(xué)院,江西 贛州 341000)

為了提高無線傳感器網(wǎng)絡(luò)的節(jié)點定位精度,對相關(guān)文獻進行了研究,提出了一種改進的移動錨節(jié)點凸規(guī)劃定位算法。該算法對原算法作了以下改進:利用正半定松弛方法擴大求解問題的可行域,以降低求解優(yōu)化問題的計算復(fù)雜度;采用局部梯度下降法進行迭代優(yōu)化來逼近最優(yōu)估計,以提高優(yōu)化問題的求解精度。實驗結(jié)果表明,改進算法比原算法具有更高的定位精度,并可以更好地適應(yīng)不同的網(wǎng)絡(luò)規(guī)模。

無線傳感器網(wǎng)絡(luò);定位算法;凸規(guī)劃;梯度下降法;移動錨節(jié)點

在無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)中,對于大部分的感知任務(wù),例如路由協(xié)議效率、定位與跟蹤、節(jié)點分簇等,獲取傳感器節(jié)點的位置信息極其重要[1]。節(jié)點定位是無線傳感器網(wǎng)絡(luò)的關(guān)鍵技術(shù)之一,根據(jù)定位過程中是否需要距離信息,可將定位算法分為測距相關(guān)與測距無關(guān)兩大類[2]。典型的測距相關(guān)定位算法有基于到達時間TOA(Time of arrival)定位、基于到達時間差TDOA(Time Difference of Arrival)定位、基于到達角度AOA(Angle of Arrival)定位和基于接收信號強度指示RSSI(Received Signal Strength Indicator)定位等算法[3-4],典型的測距無關(guān)定位算法有質(zhì)心定位,距離向量-跳段DV-hop(Distance Vector-hop)定位,凸規(guī)劃定位、基于多維定標(biāo)MDS(Multidimensional Scaling)定位等算法[5-6]。

近年來,通過優(yōu)化方法來解決節(jié)點定位問題成為研究的熱點之一,許多基于規(guī)劃的定位方法逐漸被提出[7-8]。文獻[9]提出Convex定位算法,該算法將傳感器網(wǎng)絡(luò)中的未知節(jié)點和錨節(jié)點能否進行通信作為約束條件,通過多個鄰接錨節(jié)點的通信約束構(gòu)造凸規(guī)劃問題,但通過節(jié)點通信區(qū)域交集的外接矩形面積近似通信區(qū)域交集,降低了定位精確度。文獻[10]提出了一種基于二階錐規(guī)劃松弛的分布式定位算法,盡管在凸包內(nèi)的未知節(jié)點可獲得較好的定位精度,但在凸包外的未知節(jié)點定位性能較差。文獻[11]對二階錐規(guī)劃問題進行了改進,用半定松弛的方法把非凸規(guī)劃問題轉(zhuǎn)化為凸規(guī)劃問題,從而根據(jù)距離約束采用極大似然準(zhǔn)則計算節(jié)點的位置,但定位過程中需測量未知節(jié)點與錨節(jié)點的距離。文獻[12]提出一種新的半定規(guī)劃松弛方法將最大似然估計最小二乘問題轉(zhuǎn)化為凸規(guī)劃問題,但定位過程需使用RSS測距模型。文獻[13]提出Co-SRL的凸規(guī)劃節(jié)點定位算法,以多個移動錨節(jié)點進行協(xié)作定位,并采用凸規(guī)劃方法計算節(jié)點的位置。文獻[14]提出一種高斯噪聲下基于最大分散度的半定規(guī)劃定位算法,該算法利用半定規(guī)劃,并用梯度下降法進行求精,取得了較好的定位精度。文獻[15]利用移動錨節(jié)點以不同的功率發(fā)射信標(biāo)信號,將未知節(jié)點接收到的信標(biāo)信息轉(zhuǎn)化為二次不等式約束組,再利用凸規(guī)劃方法計算節(jié)點的位置,取得了較高的定位精度,但定位精度還可進一步提升。因此,本文對文獻[15]的方法進行了改進,提出了一種改進的移動錨節(jié)點凸規(guī)劃定位算法,以提高節(jié)點定位的精度。

1 凸規(guī)劃定位算法

WSN中的錨節(jié)點與未知節(jié)點之間相互通信必須滿足歐幾里德距離的約束關(guān)系:

‖x-a‖≤R

(1)

其中,x為未知節(jié)點的位置,a為錨節(jié)點的位置,R為錨節(jié)點的最大傳輸半徑。

圖1 兩種定位情形

如果錨節(jié)點在不同位置以多種功率發(fā)射信標(biāo)信號,則每個未知節(jié)點可獲得與自身位置x有關(guān)的不等式約束組:

rk<‖x-ak‖≤Rkk=1,2,…,n

(2)

其中,ak為k時刻錨節(jié)點的位置,rk(可能為零)和Rk為k時刻的有效約束半徑。

在多功率移動錨節(jié)點的WSN中,每個未知節(jié)點的定位問題可以轉(zhuǎn)化為二次不等式組的求解問題。但網(wǎng)絡(luò)環(huán)境因素的復(fù)雜性可能導(dǎo)致未知節(jié)點與錨節(jié)點之間不滿足通信的條件,信號的干擾、衰減等因素也會對節(jié)點定位過程造成嚴(yán)重影響。因此,可能導(dǎo)致兩種節(jié)點定位的情形,如圖1所示。圖1中的黑色方塊表示錨節(jié)點位置,空心圓圈表示未知節(jié)點位置;圖1(a)的可行集不為空,圖1(b)的可行集為空。

文獻[15]提出一種移動錨節(jié)點輔助的凸規(guī)劃定位算法,該算法可適用于上述兩種定位的情形,也可推廣應(yīng)用于測距相關(guān)的定位系統(tǒng)。

根據(jù)通信約束關(guān)系,每個未知節(jié)點可以得到一組關(guān)于自身位置的約束,并通過最小化得到最優(yōu)位置的逼近。

(3)

(4)

2 改進的凸規(guī)劃定位算法

文獻[15]利用凸松弛方法將式(4)的非凸規(guī)劃問題轉(zhuǎn)化為凸規(guī)劃問題,但采用這種優(yōu)化方法將會增加計算復(fù)雜度,并且導(dǎo)致求解結(jié)果出現(xiàn)非最優(yōu)解或可行解,這無疑降低了規(guī)劃問題求解的精度。本文對文獻[15]的方法進行了改進,利用正半定松弛方法,擴大求解問題的可行域并降低求解優(yōu)化問題的計算復(fù)雜度,采用局部梯度下降法提高優(yōu)化問題的求解精度。

將式(3)展開得到:

(5)

由于錨節(jié)點的有效半徑可根據(jù)其發(fā)射功率計算得到,即rk和Rk已知,故:

(6)

由于式(6)為非凸規(guī)劃問題,但可利用凸松弛方法將式(6)轉(zhuǎn)化為凸規(guī)劃問題。

令X=[x1,x2,…,xn]∈R2×n,Y=XTX,

μxa=‖x-ak‖2,vxa=‖x-ak‖

則式(6)中的范數(shù)部分為:

‖x-ak‖2=(ak;ei)T[I2;X]T[I2;X](ak;ei)

(7)

從而,式(6)可表示為:

(8)

其中,I2為2維單位矩陣,ei為第i個元素為1的n維單位向量,(ak;ei)為(2+n)維列向量。

根據(jù)非凸優(yōu)化理論,可以通過半定松弛方法,將非凸規(guī)劃問題轉(zhuǎn)化為凸規(guī)劃問題:

(9)

因此,可以得到式(9)凸規(guī)劃問題的一般形式:

(10)

由于半定規(guī)劃內(nèi)點法產(chǎn)生的解具有高秩性,其松弛解可能不是最優(yōu)解,甚至不是可行解。因此,通過局部梯度下降法來逼近最優(yōu)解。

(11)

令精度為ε(ε>0),迭代次數(shù)為m(m的初值為1),則局部梯度下降法的步驟如下:

S1 以半定規(guī)劃松弛解xi(i=1,2,…,n)為初始點開始迭代;

本文改進方法的計算復(fù)雜度和求解精度分析如下:

求解凸規(guī)劃問題,一般情況下,采用內(nèi)點法解決n個未知節(jié)點定位問題的計算復(fù)雜度與約束條件個數(shù)有關(guān),如果約束條件的個數(shù)在O(n)范圍內(nèi),其計算復(fù)雜度為O(n3)[16]。文獻[15]模型引入松弛后,約束條件的個數(shù)在O(n2)范圍內(nèi),故求解文獻[15]規(guī)劃問題的計算復(fù)雜度為O(n6)。而本文模型進一步松弛,式(10)中的(2+n)維矩陣錐Z可以被分解成小矩陣錐,分解后的約束條件個數(shù)在O(n)范圍內(nèi),故求解本文凸規(guī)劃問題的計算復(fù)雜度為O(n3)。因此,本文模型比文獻[15]模型運算更加快速,計算復(fù)雜度更低。

由于局部梯度下降法利用負梯度作為每次迭代的搜索方向,每次以松弛解為起點,沿著目標(biāo)函數(shù)在起點處的負梯度方向改善松弛解,使之接近最優(yōu)解,從而提高定位精度。因此,局部梯度下降法可以有效改善求解問題的松弛解,提高定位精度。

3 實驗結(jié)果與分析

為了驗證算法的性能,將本文算法與文獻[15]的算法進行比較實驗。實驗平臺:Windows XP SP3+MATLAB 2009a。實驗場景:2-D平面內(nèi)L×L的區(qū)域隨機分布100個未知節(jié)點。實驗參數(shù):一個移動錨節(jié)點按文獻[15]的移動路徑在網(wǎng)絡(luò)中移動并以兩級發(fā)射功率發(fā)送信標(biāo)信號,如圖2所示,錨節(jié)點兩級發(fā)射功率對應(yīng)的最大傳輸半徑分別為r和R,r=0.15L,R=2r,錨節(jié)點移動步長s=0.1L;ε=0.01,η=0.005L。

采用歸一化平均定位誤差來評估算法的性能:

(12)

3.1 理想傳輸模型的定位

本實驗主要比較兩種方法在理想傳輸模型下的性能。

在實驗場景中隨機部署100個未知節(jié)點,分別用文獻[15]的方法和本文方法進行定位,定位結(jié)果如圖3所示,圖中星號表示實際坐標(biāo),圓圈表示估計坐標(biāo),兩者之間的連線表示定位誤差。表1為實驗場景隨機部署100次并分別用兩種方法進行定位的歸一化定位誤差。

圖3 理想傳輸模型的定位結(jié)果

表1 理想傳輸模型的歸一化定位誤差

從圖3和表1可以看出,在理想傳輸模型下,文獻[15]取得了較高的定位精度,但由于文獻[15]只利用松弛方法對凸規(guī)劃問題進行求解,并沒有考慮松弛解的因素;而本文采用松弛方法使得凸規(guī)劃問題的可行域更大,能有效減少松弛解的數(shù)目,并且采用局部梯度下降法提高松弛解的精度,可以更有效地逼近全局最優(yōu)解。因此,本文方法的定位精度比文獻[15]有了一定的提高。

3.2 非理想傳輸模型的定位

在實際環(huán)境中,由于網(wǎng)絡(luò)環(huán)境的復(fù)雜性及信號傳播媒介等原因,錨節(jié)點傳輸過程的通信范圍并不滿足固定的無線電射程。本實驗主要比較兩種方法在非理想傳輸模型下的性能。通過不規(guī)則信號模型來模擬實際環(huán)境,利用不規(guī)則度DOI(Degree of Irregular)來表征錨節(jié)點傳播信號在傳輸過程中受到的影響。通常,DOI為0時表示錨節(jié)點通信范圍為理想的圓形區(qū)域,DOI為0.2表示節(jié)點的有效傳輸半徑在[0.8r,1.2r]的范圍內(nèi)變化,DOI越大,錨節(jié)點的通信范圍變化越大且越不規(guī)則。

在實驗場景中隨機部署100個未知節(jié)點,并在DOI=0.2時分別用文獻[15]的方法和本文方法進行定位,定位結(jié)果如圖4所示。

圖4 非理想傳輸模型的定位結(jié)果(DOI=0.2)

圖5 非理想傳輸模型的平均定位性能

由圖4可知,在DOI為0.2時,本文的歸一化平均誤差比文獻[15]提高了9.036%。

圖5為實驗場景隨機部署100次并在不同DOI取值時,分別用兩種方法進行定位的歸一化定位誤差。

從圖5可以看出,DOI值越小,平均定位性能越接近理想傳輸模型的平均定位性能,但是隨著DOI值的增大,定位誤差也隨之增長。由于本文方法在求解凸規(guī)劃問題的基礎(chǔ)上,對松弛解采用局部梯度下降法進行迭代逼近最優(yōu)解,可以更好地適應(yīng)實際的網(wǎng)絡(luò)環(huán)境,故在相同的條件下,本文的平均定位性能優(yōu)于文獻[15]的定位性能。

3.3 不同錨節(jié)點傳輸半徑的定位

本實驗主要比較兩種方法在錨節(jié)點移動步長s=0.1L的條件下,錨節(jié)點最大傳輸半徑r分別取0.10L、0.15L、0.20L、0.25L、0.30L和0.35L時的性能。實驗結(jié)果如圖6所示。

圖6 不同錨節(jié)點傳輸半徑的定位性能

從圖6可以看出,在錨節(jié)點移動步長相同、錨節(jié)點最大傳輸半徑取不同值時,本文方法通過局部梯度下降法,可有效改善松弛解,其平均定位性能優(yōu)于文獻[15]的定位性能。

3.4 未知節(jié)點密度對定位性能的影響

本實驗主要比較未知節(jié)點密度對兩種方法性能的影響。在實驗場景中分別隨機部署25、50、75、100、125、150、175、200、225、250、275和300個未知節(jié)點,分別用文獻[15]的方法和本文方法進行定位,實驗結(jié)果如圖7所示。

從圖7可以看出,兩種方法在不同未知節(jié)點密度的定位性能均較平穩(wěn),但本文方法在不同未知節(jié)點密度下的定位性能均優(yōu)于文獻[15],因此,本文方法可以更好地適應(yīng)于不同的網(wǎng)絡(luò)規(guī)模。

圖7 不同未知節(jié)點密度的定位性能

4 結(jié)束語

針對移動錨節(jié)點凸規(guī)劃定位算法的不足,提出了一種改進的移動錨節(jié)點凸規(guī)劃定位算法。改進算法從求解優(yōu)化問題的計算復(fù)雜度和求解精度兩個方面對原算法作了改進,并在理想傳輸模型、非理想傳輸模型、不同錨節(jié)點傳輸半徑以及未知節(jié)點密度的實驗場景中進行了算法性能比較實驗。實驗結(jié)果表明,改進算法的定位精度和網(wǎng)絡(luò)適應(yīng)性均優(yōu)于原算法,從而驗證了改進措施的有效性。

[1] Akyildiz I F,Su W,Sankarasubramaniam Y,et al. Wireless Sensor Networks:A Survey[J]. Computer Networks,2002,38(4):393-422.

[2]王福豹,史龍,任豐原. 無線傳感器網(wǎng)絡(luò)中的自身定位系統(tǒng)和算法[J]. 軟件學(xué)報,2005,16(5):857-868.

[3]Park J W,Park D H,Lee C. Angle and Ranging Based Localization Method for Ad Hoc Network[J]. The Journal of Supercomputing,2013,64(2):507-521.

[4]梅舉,陳滌,辛玲. 基于蒙特卡洛方法的移動傳感網(wǎng)節(jié)點定位優(yōu)化算法[J]. 傳感技術(shù)學(xué)報,2013,26(5):689-694.

[5]Ma D,Er M J,Wang B,et al. Range-Free Wireless Sensor Networks Localization Based on Hop-Count Quantization[J]. Telecommunication Systems,2012,50(3):199-213.

[6]黃亮,王福豹,段渭軍,等. 基于距離重構(gòu)的無線傳感器網(wǎng)絡(luò)多維定標(biāo)定位算法[J]. 傳感技術(shù)學(xué)報,2013,26(9):1284-1287.

[7]Chiu W Y,Chen B S,Yang C Y. Robust Relative Location Estimation in Wireless Sensor Networks with Inexact Position Problems[J]. IEEE Transactions on Mobile Computing,2012,11(6):935-946.

[8]Ji S,Sze K F,Zhou Z,et al. Beyond Convex Relaxation:a Polynomial-Time Non-Convex Optimization Approach to Network Localization[C]//Proceedings of IEEE International Conference on Computer Communications(INFOCOM),Turin,Italy:IEEE,2013:2499-2507.

[9]Doherty L,El Ghaoui L. Convex Position Estimation in Wireless Sensor Networks[C]//Proceedings of IEEE International Conference on Computer Communications(INFOCOM). Anchorage USA:IEEE. 2001,3:1655-1663.

[10]Srirangarajan S,Tewfik A H,Luo Z Q. Distributed Sensor Network Localization Using SOCP Relaxation[J]. IEEE Transactions on Wireless Communications,2008,7(12):4886-4895.

[11]Xie S,Wang J,Hu A,et al. Localization Algorithm Based on Positive Semi-Definite Programming in Wireless Sensor Networks[J]. International Journal of Signal Processing,Image Processing and Pattern Recognition,2013,6(1):1-12.

[12]Vaghefi R M,Gholami M R,Buehrer R M,et al. Cooperative Received Signal Strength-Based Sensor Localization with Unknown Transmit Powers[J]. IEEE Transactions on Signal Processing 2013,61(6):1389-1403.

[13]Liu W,Sun D,Ren P,et al. Co-SRL:A Convex Optimization Algorithm for Anchor Localization in Wireless Sensor Networks[C]//Proceedings of 2013 AASRI Conference on Parallel and Distributed Computing and Systems,Singapore,2013,5:62-66.

[14]何國鋼,鄧平. 一種高斯噪聲下基于最大分散度的WSN半定規(guī)劃定位算法[J]. 傳感技術(shù)學(xué)報,2012,25(8):1116-1120.

[15]史清江,何晨. 多功率移動錨節(jié)點輔助的分布式節(jié)點定位方法[J]. 通信學(xué)報,2009,30(10):8-13.

[16]Biswas P,Ye Y. Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization[C]//Proceedings of the 3rd International Symposium on Information Processing in Sensor Networks. ACM,2004:46-54.

任克強(1959-),男,教授,碩士研究生導(dǎo)師,主要研究方向為嵌入式系統(tǒng)、無線傳感器網(wǎng)絡(luò)等,jxrenkeqiang@163.com;

莊放望(1988-),男,碩士研究生,主要研究方向為無線傳感器網(wǎng)絡(luò)。

ResearchandImprovementofMobileAnchorNodeLocalizationAlgorithmBasedonConvexProgramming

RENKeqiang*,ZHUANGFangwang

(School of Information Engineering,Jiangxi University of Science and Technology,Ganzhou Jiangxi 341000,China)

In order to enhance the node localization accuracy in wireless sensor networks,this article had studied the related references,and proposed an improved convex programming localization algorithm of mobile anchor node. The algorithm made some improvements on the original algorithm to reduce the computational complexity of solving optimization problems,positive semidefinite relaxation method was utilized for enlarging the feasible region of solving problems to improve the accuracy of solving optimization problems and local gradient descent method was used to approximate the optimal estimate. The experimental results show that the algorithm has higher positioning accuracy than the original algorithm,and can better adapt to the different network scale.

wireless sensor network;localization algorithm;convex optimization;gradient descent method;mobile anchor node

2014-06-28修改日期:2014-08-26

10.3969/j.issn.1004-1699.2014.10.019

TP393

:A

:1004-1699(2014)10-1406-06