基于混合測距的二階錐規(guī)劃節(jié)點定位算法

孫瑩瑩，張 飛

(1.國網(wǎng)河南省電力公司 駐馬店供電公司，河南 駐馬店 463000；2.黃淮學院 信息工程學院，河南 駐馬店 463000)

0 引 言

受硬件條件和無線環(huán)境因素的制約，在WSNs中對傳感節(jié)點的定位仍是一項挑戰(zhàn)的工作[1-4]。至今，研究人員已提出多類定位算法[5,6]，依據(jù)定位過程是否需要測距，現(xiàn)存的定位算法歸屬為基于測距或非測距。與非測距定位算法相比，基于測距定位算法的精度較高。在基于測距定位算法中，通常依據(jù)信號的相關參數(shù)獲取距離，如到達時間(time of arrival，ToA)、到達角度(angle of arrival，AoA)[6,7]以及信號強度(received signal strength，RSS)。

此外，考慮了節(jié)點能量的局限性和定位精度，常引用協(xié)作混合定位算法[8]。文獻[9]采用了線性最小二乘(least squares，LS)和優(yōu)化估計的定位算法，而文獻[10]采用了基于RSS差和AoA測量的LS和最大似然估計(ML)的定位算法。相應地，文獻[11]通過權重LS求解基于RSS/AoA混合定位問題。

上述的這些算法均采用集中式方案求解混合測距定位問題。盡管集中式方案在大型網(wǎng)絡具有較高的穩(wěn)定性，但是具有足夠計算機容量的集中處理器可能難以獲取。因此，分布式方案更具有可操作性。

為此，提出分布式的基于RSS-AoA測距的二階錐規(guī)劃節(jié)點定位(RSS and AoA-based second-order cone programming target localization，R-S-SOCP)算法。R-S-SOCP算法充分利用RSS和AoA測距的優(yōu)勢，獲取測量值，然后再利用最大似然(maximum likelihood，ML)估計獲取未知節(jié)點位置，最后由SOCP將ML估計轉換成SOCP的凸優(yōu)問題。實驗數(shù)據(jù)表明，提出R-S-SOCP算法能有效地降低定位誤差。

1 定位模型

考慮一個大型傳感網(wǎng)絡，其由M個未知節(jié)點和N個錨節(jié)點構成。同時，引用S={s1,s2,…,sk,…,sM} 表示未知節(jié)點集和A={a1,a2,…,ai,…,aN} 表示錨節(jié)點集。

相應地，錨節(jié)點位置矢量表示為ai∈R3， 且?i∈A， 而未知節(jié)點位置矢量表示為xk∈R3， 且?k∈S。

當兩節(jié)點在彼此通信范圍R內(nèi)，這兩個節(jié)點間才能建立連接。為此，所有未知節(jié)點和錨節(jié)點鏈路以及未知節(jié)點與未知節(jié)點間鏈路分別定義為

(1)

(2)

引用基于RSS和角度AoA測距算法，估計未知位置，測距模型如圖1所示。

圖1 定位模型

假定第k個未知位置的笛卡爾坐標為x=[xk,yk,zk]T， 而第i個錨節(jié)點的笛卡爾坐標為αi=[αix,αiy,αiz]T。 圖1中的dik、φik和αik分別表示k個未知節(jié)點離第i個錨節(jié)點間距離、方位角和仰角。

由于RSS測距無需額外硬件設備[12]，先利用RSS值進行測距。在無噪聲條件下，兩個節(jié)點i、j間的RSS值Pij(W)，定義如式(1)所示[13]

(3)

式中：Pi為第i個傳感節(jié)點的發(fā)射功率，而λ0i表示第i個傳感節(jié)點在參考距離為d0時的路徑衰耗，且d0≤dij。其中dij表示兩個節(jié)點i、j間的距離。

(4)

接下來，引用AoA測量。錨節(jié)點引用全向天線或天線陣列測量角度。因此，通過簡單幾何理論，引用文獻[9]理論，可測量方位角

(5)

(6)

假定觀察矢量θ=[LT,φT,αT]， 且θ∈R3N， 其中L=[Lij]T、φ=[φij]T和α=[αij]T。 假定條件概率密度分布函數(shù)(probability density function，PDF)

(7)

而函數(shù)f(χ)

(8)

最后，利用最大似然估計算法估計未知矢量χ的值，可得[14]

(9)

注意到，最大似然估計是非凸優(yōu)的，且無封閉的解。因此，需用近似求解法，進而獲取閉合解，提高定位精度。

2 R-S-SOCP算法

R-S-SOCP定位算法主要包括測距和定位算法兩部分。先利用RSS和AoA進行測量，然后利用最大似然估計建立式(9)，再通過最小二乘估計未知位置，并作為局部ML的迭代初始值，最后，利用SOCP求解未知位置。R-S-SOCP 定位算法的總體模塊如圖2所示。

圖2 R-S-SOCP定位算法的總體模塊

2.1 局部ML估計

因此，利用局部最大似然估計，計算未知i在第t+1次迭代時位置估計值，如式(10)所示

(10)

式中：Ai={j∶(i,j)∈A}、Si={k∶(i,k)∈S} 分別表示第i個未知節(jié)點的所有鄰居的錨節(jié)點和所有鄰居的未知節(jié)點。

而函數(shù)fj(χi)

(11)

若噪聲較小的環(huán)境下，并結合式(4)可得

(12)

對式(8)兩邊進行平方，再丟掉二階噪聲變量，可得

(13)

類似地，式(5)和式(6)可分別轉換成

(14)

(15)

其中，cij=[-sinφij,cosφij,0]T, 且k=[0,0,1]T。

利用三角函數(shù)知識，并忽略二階噪聲變量，從式(15)可知

(16)

最后，基于LS準則，并利用式(13)、式(14)和式(16)，可得

(17)

注意到式(17)，式(17)的解是一個非凸、非封閉解。為此，利用SOCR算法轉換成凸優(yōu)解。

2.2 SOCR算法

引用epigraph變量e、ρ和q，利用這些變量轉換式(17)，進而將式(17)轉換成SOCP問題，如式(18)所示

(18)

約束條件

(19)

(20)

(21)

(22)

(23)

式(18)是典型的SOCP問題，可通過Matlab軟件的工具箱CVX有效解決[14]，基于SOCP的定位方案的流程如圖3所示。

圖3 R-S-SOCP算法的定位流程

3 性能分析

通過3.07 GHz的處理器、8GRAM的計算機，并結合MATLAB 2009a建立仿真平臺，同時利用工具箱CVX計算SOCP問題。

本小節(jié)分析算法定位的準確性，選用定位均方誤差RMSE作為性能指標，其定義如式(24)所示

(24)

假定仿真區(qū)域內(nèi)有M個未知節(jié)點、N=9個錨節(jié)點，仿真區(qū)域為50 m×50 m。而參數(shù)路徑衰落指數(shù)γ=3、參考距離d0=1 m。

(1)實驗一

首先分析當M=6，R=6 m，方差σ=5 dB仿真場景。9個錨節(jié)點的位置分別為：(40,12)、(18,35)、(-5,39)、(-30,8)、(-13,44)、(0,-6)、(37,-23)、(30,20)。仿真結果如圖4所示。

圖4 R-S-SOCP算法估計6個未知節(jié)點的位置

圖4描述了R-S-SOCP算法估計未知節(jié)點位置情況，其中“▲”代表錨節(jié)點，而“■”代表未知節(jié)點、“●”代表對未知節(jié)點的位置估計。從圖4可知，提出的R-S-SOCP算法能夠較準確地估計未知節(jié)點的位置?！啊瘛本凇啊觥备浇?，甚至重疊。

(2)實驗二

表1顯示了各算法的復雜度。從表1可知，R-S-SOCP算法的復雜度高于SDPURSS和WANG算法，R-S-SOCP算法的復雜度為2·O(N3.5)、而SDPURSS、WANG算法的復雜度分別為O(N3.5)和O(N)。這說明R-S-SOCP算法是以一定的復雜度換取定位精度。

(3)實驗三

最后，節(jié)點通信半徑R對RMSE影響，實驗數(shù)據(jù)如圖6 所示，其中N=9、M=6。

圖5 定位均方誤差RMSE隨N的變化情況

算法算法具體描述復雜度WANGWANG估計[16]O(N)SDPURSSSDP估計[17]O(N3.5)R-S-SOCP本文提出的定位算法2·O(N3.5)

圖6 RMSE隨通信范圍R的變化情況

從圖6可知，RMSE隨通信半徑R的增加而下降，這主要是因為R的增加，提高了節(jié)點通信范圍，使得未知節(jié)點能獲取更多的測距信息，這有利于定位精度的提高。與WANG、SDPURSS相比，R-S-SOCP算法的RMSE分別下降了近1 m、0.5 m。

4 結束語

本文針對無線傳感網(wǎng)絡的節(jié)點定位問題，提出基于RSS和AoA的二階錐規(guī)劃的R-S-SOCP算法。R-S-SOCP算法通過結合RSS和AoA測量信號參數(shù)，再建立定位模型，然后利用SOCP建立定位SOCP定位優(yōu)化問題，最后由CVX求解未知節(jié)點位置。通過引用RSS和AoA測量的優(yōu)勢，降低了測距誤差。同時，建立SOCP模型，提高定位的精度。實驗數(shù)據(jù)表明，提出的R-S-SOCP算法有效地降低定位誤差。此外，通過表1可知，提出的R-S-SOCP算法提高算法的復雜度。在后期，在維持算法精度的同時，優(yōu)化算法，降低算法的復雜度。