任克強(qiáng),莊放望

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

?

移動(dòng)錨節(jié)點(diǎn)凸規(guī)劃定位算法研究及改進(jìn)

任克強(qiáng)*,莊放望

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

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

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

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

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

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

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

‖x-a‖≤R

(1)

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

圖1 兩種定位情形

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

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

(2)

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

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

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

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

(3)

(4)

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

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

將式(3)展開得到:

(5)

由于錨節(jié)點(diǎn)的有效半徑可根據(jù)其發(fā)射功率計(jì)算得到,即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個(gè)元素為1的n維單位向量,(ak;ei)為(2+n)維列向量。

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

(9)

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

(10)

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

(11)

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

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

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

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

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

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

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

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

(12)

3.1 理想傳輸模型的定位

本實(shí)驗(yàn)主要比較兩種方法在理想傳輸模型下的性能。

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

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

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

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

3.2 非理想傳輸模型的定位

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

在實(shí)驗(yàn)場(chǎng)景中隨機(jī)部署100個(gè)未知節(jié)點(diǎn),并在DOI=0.2時(shí)分別用文獻(xiàn)[15]的方法和本文方法進(jìn)行定位,定位結(jié)果如圖4所示。

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

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

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

圖5為實(shí)驗(yàn)場(chǎng)景隨機(jī)部署100次并在不同DOI取值時(shí),分別用兩種方法進(jìn)行定位的歸一化定位誤差。

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

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

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

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

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

3.4 未知節(jié)點(diǎn)密度對(duì)定位性能的影響

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

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

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

4 結(jié)束語

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

[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é)報(bào),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]梅舉,陳滌,辛玲. 基于蒙特卡洛方法的移動(dòng)傳感網(wǎng)節(jié)點(diǎn)定位優(yōu)化算法[J]. 傳感技術(shù)學(xué)報(bào),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é)報(bào),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é)報(bào),2012,25(8):1116-1120.

[15]史清江,何晨. 多功率移動(dòng)錨節(jié)點(diǎn)輔助的分布式節(jié)點(diǎn)定位方法[J]. 通信學(xué)報(bào),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.

任克強(qiáng)(1959-),男,教授,碩士研究生導(dǎo)師,主要研究方向?yàn)榍度胧较到y(tǒng)、無線傳感器網(wǎng)絡(luò)等,jxrenkeqiang@163.com;

莊放望(1988-),男,碩士研究生,主要研究方向?yàn)闊o線傳感器網(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