非視距環(huán)境下基于二階錐規(guī)劃的RSS定位算法

金小萍，梁俊，謝少楓

（中國計量大學，浙江 杭州 310018）

1 引言

近年來，無線傳感器網(wǎng)絡（wireless sensor network，WSN）由于其低能耗和高效率，而在目標跟蹤、室內定位、海上救援、森林火災監(jiān)測等領域得到了廣泛的研究與應用。在WSN應用中，獲取傳感器節(jié)點的位置是必不可少的部分，關于節(jié)點位置確定的定位技術主要有如下兩大類。

· 第一類：基于非測距的方法，如重心法、DV-HOP、APIT等方法[1-2]，這些方法雖然易于實施，成本較低，但定位精度受傳感器網(wǎng)絡布置的限制。

· 第二類：基于測距的定位方法，如RSS、AOA、TOA、TDOA等方法[3-5]，相比非測距方法，這些方法雖然需要額外的測距硬件，但定位精度更高，其中基于RSS的測距方法僅需要測出信號的衰減信息，且硬件實現(xiàn)成本相比其他測距方式也更低，在小規(guī)模傳感器網(wǎng)絡中，是一種高性價比的定位方式。然而基于RSS測距方式的定位精度易受非視距（non-line-of-sight，NLOS）環(huán)境的干擾，尤其是在障礙物密集的室內環(huán)境中，例如地下車庫、監(jiān)獄、醫(yī)院等室內場景。在對人員進行定位時，墻壁、人流、房間的非視距干擾就很大，如果仍將傳感器之間假設為視距（line-of-sight，LOS），則會導致RSS信息收集的不準確甚至RSS信息的丟失，最終造成較大的定位誤差。

以往關于非視距環(huán)境下RSS定位問題的研究，主要包括3種類型。第一種方法基于非線性優(yōu)化算法，參考文獻[6]利用高斯混合模型將噪聲項的非視距與視距分布變換為指數(shù)形式后再利用牛頓法進行求解。參考文獻[7]基于最大似然（maximum likelihood，ML）準則構建了一個非線性方程組，合理設置初始點，再利用牛頓迭代法的思想進行求解。然而，此類方法需要對噪聲誤差以及非視距環(huán)境具有良好的認知，且非線性優(yōu)化算法本身就存在估計誤差較大的問題，定位精度無法保證。第二種方法基于加權最小二乘（weighted least squares，WLS）算法，此類方法的思想是將問題轉化為線性的估計器再利用二分法進行求解。參考文獻[8]使用無味變換（unscented transform，UT）將基于RSS的傳感器定位問題轉換為WLS估計問題應用于室內定位模型中，但該方法仍然需要對非視距狀態(tài)具有良好的認知。參考文獻[9]應用平方域（squared range，SR）和最小二乘（least squares，LS）準則將非視距偏差作為平衡干擾參數(shù)與目標位置一起進行估計，最終構建了一個WLS問題，但其中線性化的近似會帶來額外的誤差，從而導致求解精度不夠準確。第三種方法基于凸優(yōu)化技術，此類方法的思想是將非凸的定位問題轉化為凸問題求解，參考文獻[10]研究了RSS與TOA在非視距環(huán)境中的定位算法，對誤差項進行一階泰勒公式展開，在此基礎上利用LS準則構建了定位問題，最終將原始的非凸問題轉換為二階錐規(guī)劃（second-order cone programming，SOCP）問題，雖然此類方法可以有效地提高定位性能，但由于TOA定位對硬件要求較高，再結合RSS和TOA信息硬件設備的實現(xiàn)難度較大，并且將測距方程進行泰勒近似，會造成一定的誤差。

基于上述背景，提出了一種基于SOCP的魯棒性定位算法，與參考文獻[6-10]不同，本文考慮在非視距干擾量的影響達到最大的情況下去處理非視距RSS定位問題。首先，利用對數(shù)乘法法則將RSS模型化為線性乘積形式，接著，采用最小平方相對誤差（least squares relative error，LSRE）準則[12]構建了魯棒性的節(jié)點定位方程，然后，利用凸優(yōu)化技術提出了SOCP算法，從而解決原始定位問題的非凸性，最后，將問題推廣到未知發(fā)射功率的情況，提出了迭代估計的SOCP算法。與以往的方法相比，所提算法不用識別非視距的狀態(tài)以及分布，僅考慮非視距偏差達到最大的最壞情況，對非視距偏差具有魯棒性，減輕了非視距偏差的影響，從而提升了定位性能。

2 非視距RSS系統(tǒng)模型及問題分析

考慮一個二維平面的無線傳感器網(wǎng)絡，該傳感器網(wǎng)絡具有N個錨節(jié)點si(i=1,…,n)，錨節(jié)點固定位置用來接收未知的待定位目標節(jié)點x的RSS信息，如圖1所示，假定目標節(jié)點向錨節(jié)點發(fā)出信號，錨節(jié)點可以良好地從接收信號中提取RSS信息，在非視距環(huán)境下，對應著第i個錨節(jié)點的接收信號強度為[10-11]：其中，P0是參考距離處的發(fā)射功率（dBm），γ是路徑損耗指數(shù)，d0是參考距離，設置為1 m，ni是測量的噪聲誤差量，一般設定服從零均值的高斯分布， 如ni～N(0,Oi2)。bi是非視距偏差（當bi=0的時候，i∈lLOS，當bi＞0，i∈lNLOS，其中l(wèi)LOS與lNLOS分別代表視距傳感器和非視距環(huán)境下的傳感器的數(shù)目，對應的有l(wèi)NLOS=N-lLOS），在本文中，假設非視距偏差的大小受一個已知常數(shù)bmax的限制， 如0 ≤bi≤bmax，·均表示二范數(shù)運算。

圖1 RSS定位示意圖

基于式（1）中的測量值Pi，可以得到關于未知節(jié)點x和bi(i=1,…,n)的最大似然估計：

式（2）的求解非常困難，由于未知的非視距偏差ib的存在，該問題的解是不確定的，需要去識別傳感器節(jié)點之間的連接狀態(tài)，才可以求解；其次，式（2）中的目標函數(shù)具有嚴重的非凸和非線性，難以獲取全局最優(yōu)解。為了解決這些問題，在第3節(jié)中，將通過假定非視距偏差的上界來構建魯棒優(yōu)化問題，以此克服非視距偏差的影響，并利用凸優(yōu)化技術處理定位估計中求解量是非全局最優(yōu)的問題。

3 魯棒性SOCP定位算法

3.1 已知發(fā)射功率

首先，在發(fā)射功率已知（即0P已知）的情況下推導魯棒性SOCP定位算法。針對式（1），在其兩邊同時加上變形移項后得到：

利用對數(shù)運算法則，將式（4）改寫為線性乘積形式：

基于式（5）的乘積形式，得到如下關于未知節(jié)點x的魯棒最小平方相對誤差（robust least squares relative error，R-LSRE）估計表達式[12]：

該問題就是在最壞的情況下，對節(jié)點估計方程進行魯棒優(yōu)化，也就是最大化ie的情況下再最小化該目標函數(shù)。與參考文獻[10]中利用LS估計構建的目標函數(shù)相比，LSRE估計比LS估計具有更好的估計精度[12]。此外，由于考慮了非視距干擾量的影響達到最大的最壞情況，對非視距偏差量具有魯棒性，故利用該估計方法可以減輕非視距偏差帶來的影響。

為了解決式（6），以ie為自變量，引入一個函數(shù)y=f(ei)，可以得到：

要解決式（8）對應的問題，需要計算函數(shù)算該問題，分為兩種情況進行分析：

基于上述兩種情況，式（8）可以等價為如下最優(yōu)化目標節(jié)點問題：

式（9）中最優(yōu)化問題的目標函數(shù)是非凸非線性的。針對該問題，將利用凸優(yōu)化松弛技術將原始節(jié)點估計問題轉化為一個SOCP問題，首先，式（9）可以等價為如下上鏡圖形式問題[13]：

其中，t1i、t2i、t3i、t4i分別是所對應的約束條件的第i個變量的上界。

可以看出目標函數(shù)是線性的，而約束條件仍為非凸的。引入二個等價變量和基于此，把約束條件（10b）和引入的二個等價變量同時松弛到二階錐（second-order cone，SOC）中，最終式（10）轉變?yōu)閇13]：

這是一個標準的SOCP問題，可以由內點法求解未知的目標節(jié)點，具體可由CVX仿真軟件實現(xiàn)[14]，在后續(xù)描述中，將該發(fā)射功率已知的魯棒性SOCP定位算法定義為R-SOCP。

3.2 未知發(fā)射功率

在實際情況下，傳感器的發(fā)射功率0P往往隨著外部環(huán)境的變化而發(fā)生改變，而這將造成額外的定位誤差，針對這一情況，本節(jié)將在定位方法（11）的基礎上進行改進，并通過一個迭代SOCP算法來提升性能。

當發(fā)射功率未知時, 等價于di參數(shù)未知。重新改寫式（5），可以得到：

其中，對應參數(shù)n是未知量，類似地，可以得到如下最優(yōu)化問題：

對于問題（13），其中的約束條件（13b）和（13c）是非凸的，因為其中的未知量在二階錐約束中是非仿射非線性的。通過添加二階錐松弛條件將發(fā)射功率量等價成偽線性形式，由此，式（13）可以二階錐松弛（second-order cone relaxation，SOCR）為[13]：

式（14）也是一個SOCP問題，同樣可由內點法求解，此外，為了進一步提升式（14）中SOCP方法的性能，提出了一個同時估計發(fā)射功率與目標位置的迭代SOCP算法，如算法1所示，后續(xù)把發(fā)射功率未知時的魯棒性SOCP定位算法定義為R-SOCP-U，最終，將所推導的發(fā)射功率已知與發(fā)射功率未知情況下的魯棒性SOCP定位算法歸納如下。

算法1魯棒性SOCP定位算法

步驟1輸入錨節(jié)點位置{si}；最大非視距偏差為{bmax}；噪聲標準差為{σi}；路徑損耗指數(shù)為{γ}；接收信號強度為{Pi}；發(fā)射功率為{P0}；最大迭代次數(shù)為{kmax}；極小正值為{}δ；

步驟2當發(fā)射功率已知，求解式（11），得到估計的目標位置；當發(fā)射功率未知，求解式（14），得到估計位置xk1-，令k=1；

步驟3將xk1-代入式（1）中，反解出發(fā)射功率pk-1：

步驟4利用Pk-1求解式（11），得到估計位置xk；

步驟5判斷如果＜δ或者k＞kmax則得到估計的目標位置，如果不是，則令k=k+1，重新計算步驟3。

輸出步驟2或步驟5的目標節(jié)點的位置x。

4 定位性能仿真

在定位性能仿真中，主要選擇了3種方法用來對比R-SOCP與R-SOCP-U算法：基于牛頓迭代思路的NR法[7]、基于WLS的UT法[8]、基于LS的SOCP法[10]。其中，SOCP等凸問題可使用CVX軟件包進行仿真，并且仿真中只涉及RSS算法的部分。定位環(huán)境設定如下：所有傳感器均勻設定在30 m×30 m的平面區(qū)域，其中的仿真參數(shù)設定如下：發(fā)射功率P0=-4 0 dBm ，路徑損耗指數(shù)γ=4。簡單起見，假設RSS測量模型的所有噪聲標準差都相等，也就是σi=σ。定位的性能采用均方根誤差（root mean square error, RMSE）進行分析，定義如下：

其中，Mc是蒙特卡羅仿真次數(shù)，本次仿真，進行運算3 000次，ix為第i次不同定位算法運算所產(chǎn)生的估計位置，ex為每次實驗當中隨機產(chǎn)生的目標節(jié)點的真實位置。

圖2展示了R-SOCP算法的RMSE與噪聲標準差σ之間的關系的性能比較圖形，設定噪聲標準差從1 dB到6 dB均勻地增加。如圖2中顯示，所有算法的RMSE都隨著σ的增長而變大，這是因為隨著環(huán)境中的噪聲干擾增加，傳感器接收的信號會受到較大的干擾，從而造成誤差。最后，圖2顯示，對于所有考慮到的σ跨度，所提出的R-SOCP算法的定位誤差是最小的，優(yōu)于現(xiàn)有的算法。

圖2 RMSE隨著噪聲標準差變化

圖3展示了R-SOCP算法的RMSE與錨節(jié)點數(shù)目N之間的關系的性能比較圖形，設定σ= 3 dB，lNLOS=N，bmax= 6 dB ，錨節(jié)點數(shù)目從4到10均勻增加?？梢钥闯觯S著N的增加，所有算法的RMSE都會變得更小。這是因為隨著錨節(jié)點數(shù)量的增加，目標節(jié)點可以從錨節(jié)點處獲取更多的信號信息，從而提高定位精度。此外，當布置的錨節(jié)點傳感器多于8個的時候，所有算法的RMSE將趨于平穩(wěn)，這是因為當N很大時，在網(wǎng)絡中收集的RSS信息足以使所有算法的性能達到最好。最后，圖3顯示，與其他算法相比，隨著N的增加，所提出的算法的RMSE也是最低的，例如，當N=10時，R-SOCP算法的RMSE=3.4 m，相比SOCP、UT和NR算法的性能分別提高了0.7 m、2.1 m、3.3 m。

圖3 RMSE隨著錨節(jié)點數(shù)目變化

圖4展示了R-SOCP算法的RMSE與非視距錨節(jié)點數(shù)目lNLOS之間的關系的性能比較曲線，設定σ=3 dB，N=8，bmax= 6 dB ，錨節(jié)點中非視距傳感器的數(shù)目lNLOS從2個一直增加到8個?？梢钥吹剑琑-SOCP算法的RMSE始終要低于SOCP、UT和NR算法，其定位誤差是最小的。此外，基于牛頓迭代思路的NR法和線性近似的UT法會隨著非視距傳感器數(shù)目的增多而降低定位性能，因為其不能良好地識別非視距傳感器。而所提出的R-SOCP和SOCP算法都顯示了對非視距偏差的良好緩解能力，其定位性能不會隨著傳感器網(wǎng)絡中的非視距錨節(jié)點數(shù)目而改變，其中R-SOCP算法由于考慮了非視距偏差達到最大的最壞情況下非視距傳感器的誤差干擾，不用再去識別非視距傳感器，對非視距偏差具有魯棒性，從而減輕了非視距偏差的影響，帶來了性能上的提升。

圖4 RMSE隨著非視距錨節(jié)點數(shù)目變化

圖5展示了R-SOCP算法的RMSE與最大非視偏差bmax之間關系的性能比較曲線，設定σ= 1dB ，N=lNLOS=10，最大非視距偏差bmax從1 dB到6 dB均勻增加。可以看出，所有考慮的算法的RMSE都會隨著bmax的增長而變大。這是因為非視距環(huán)境越惡劣，RSS信號的接收也會受到很大干擾，從而造成誤差。此外，對于所有考慮的最大非視距偏差，本文所提算法都要優(yōu)于其余的算法，最后，R-SOCP相比其他算法，性能分別提升了1 m、2.5 m、3.6 m。

圖5 RMSE隨著最大非視距偏差變化

圖6展示了未知發(fā)射功率下的R-SOCP-U算法的累積分布函數(shù)（cumulative distribution function，CDF）性能對比曲線，設定bmax=6 dB，可以看出在未知發(fā)射功率下的R-SOCP-U算法的性能相比于SOCP算法以及UT算法都要好，具體而言，當估計誤差為2 m時，R-SOCP-U算法的累積分布函數(shù)為95%，SOCP算法的累積分布函數(shù)為86%，UT算法的累積分布函數(shù)為58%，也就是說在3 000次蒙特卡羅仿真運算中、95%的情況下，R-SOCP-U算法的估計誤差維持在2 m之內，可以得知，R-SOCP-U算法的定位精度是良好的。

圖6 R-SOCP-U算法CDF曲線的性能對比

5 復雜度分析

對于所提出的魯棒性SOCP定位算法，其中SOCP問題是由內點法去求解[13]，其中內點法中每次的迭代復雜度為O(N3)，每次的迭代數(shù)目為ξ為設定的SOCP問題求解的精度，綜上可知，整體的運算復雜度為而求解NR法的牛頓迭代法解法的迭代次數(shù)設定為kmax，求解UT法的二分法解法設定最大迭代次數(shù)為kmax，它們的最差運算復雜度均為O(kmaxN)?？梢钥闯鏊狒敯粜許OCP定位算法的運算復雜度與SOCP算法一致，但高于NR法與UT算法，權衡復雜度與定位精度，其性能是較好的。

6 結束語

針對非視距環(huán)境下的RSS定位，本文提出了魯棒性SOCP定位算法，該算法在假設非視距偏差上界的基礎上，無須獲取非視距偏差在實際環(huán)境中的統(tǒng)計信息和數(shù)目等情況，有效抑制了非視距偏差對定位性能造成的干擾。同時，將該算法推廣到未知發(fā)射功率的情況，提出了改進的迭代SOCP算法，通過將發(fā)射功率與目標位置同時迭代估計來提高定位性能。仿真結果表明，所提出的魯棒性SOCP定位算法對非視距偏差具有魯棒性，減輕了非視距偏差的影響，與現(xiàn)有的RSS非視距定位方法相比，也具有更好的定位精度。最后，本文所提出的基于SOCP的定位算法雖然定位精度較高，但存在運算復雜度較高的問題，在之后的研究中，將重點解決復雜度較高的問題。