一種利用聲音能量的兩步SDR定位算法

田 強，馮大政，李 進，胡豪爽

(1.西安電子科技大學 雷達信號處理國家重點實驗室，陜西 西安 710071；2.西安電子科技大學 綜合業(yè)務網(wǎng)理論及關(guān)鍵技術(shù)國家重點實驗室，陜西 西安 710071)

無線傳感器網(wǎng)絡(luò)定位技術(shù)在雷達、無線通信、麥克風陣列等領(lǐng)域[1-3]有著廣泛的應用。目前無線定位技術(shù)主要包括基于到達時間定位、基于到達時間差定位、基于到達角度定位以及基于聲音能量定位[4-7]。其中，基于聲音能量定位只需要傳感器對接收到的信號樣本加和求平均即可獲得定位測量數(shù)據(jù)，不需要傳感器之間進行復雜的時間同步，具有操作簡單、成本低的優(yōu)點，因而受到了越來越多的關(guān)注。

根據(jù)聲音能量衰減模型[8]，利用聲音能量數(shù)據(jù)對目標進行定位本質(zhì)上是一個非線性、非凸的參數(shù)估計問題。最大似然估計提供了非線性問題在統(tǒng)計意義下的最優(yōu)解。然而其需要進行迭代求解，且迭代過程依賴于初始值的選取；當初始值選取不好時容易陷入局部極小點，難以得到令人滿意的解。為了解決這一問題，目前主要采用的方法包括閉式解算法[8-10]和凸優(yōu)化方法[11-12]。閉式解算法能夠避免迭代運算，具有計算復雜度低的優(yōu)勢。其中，文獻[8]通過消除二次項，將定位問題轉(zhuǎn)化為無約束最小二乘估計，得到目標位置的閉式解；但實驗結(jié)果表明該方法定位精度較差。文獻[9]和文獻[10]通過引入不同的輔助變量來克服非線性問題，分別提出了加權(quán)最小二乘(Weighted Least Squares, WLS)算法和基于校正技術(shù)的加權(quán)直接最小二乘(Weighted Direct least squares solution with Correction, WDC)算法。以上兩種方法在定位性能上均優(yōu)于文獻[8]中的算法，且在量測誤差較小時可以逼近克拉美羅界(Cramér-Rao Lower Bound，CRLB)；然而由于這兩個方法在推導過程中忽略了二階誤差項，因此當測量誤差較大時，定位精度會嚴重下降。與閉式解方法不同，凸優(yōu)化方法是利用凸松弛(Convex Relaxation, CR)技術(shù)將原非凸的定位問題轉(zhuǎn)化為半正定規(guī)劃(Semi-Definite Program, SDP)[11]或二階錐規(guī)劃(Second Order Cone Program, SOCP)[12]等凸優(yōu)化問題進行求解，其優(yōu)點是迭代過程不依賴于初始值的選取并且能夠保證全局收斂性；但是這類方法對代價函數(shù)的松弛變換在多數(shù)情況下不是緊的，容易造成性能損失。

基于聲音能量的定位模型涉及目標位置和信號發(fā)射能量兩個未知變量。需要指出的是，雖然量測數(shù)據(jù)對于目標位置是非線性的，但是對于信號發(fā)射能量是線性函數(shù)。現(xiàn)有的大多數(shù)算法忽略了這一特性，而是將這兩個未知變量進行聯(lián)合估計。為了充分利用上述特性，筆者將原問題近似為一個加權(quán)最小二乘問題，通過對兩個未知變量分別進行求解，提出了一種兩步半正定松弛定位方法。該方法首先將信號發(fā)射能量表示成關(guān)于目標位置的函數(shù)，并在代價函數(shù)中將其替換消除掉；然后利用新的凸松弛技術(shù)將新得到的代價函數(shù)轉(zhuǎn)化為半正定規(guī)劃問題進行求解。

1 定位模型

考慮文獻[8-11]中所采用的聲音能量衰減模型。假設(shè)在二維平面內(nèi)分布了M個傳感器錨節(jié)點，其坐標已知且表示為si=[xi,yi]Τ,i=1,2,…，M；待估計的目標節(jié)點坐標假設(shè)為x=[x,y]Τ。根據(jù)能量衰減模型，第i個傳感器接收到的聲音能量數(shù)據(jù)為

(1)

由式(1)可得關(guān)于目標位置x和信號發(fā)射能量P的最大似然估計等價于最小化如下代價函數(shù)：

(2)

優(yōu)化求解式(2)即可得到未知變量x與P的估計值。然而，式(2)中的代價函數(shù)是非線性、非凸的，難以直接求解。下面將原定位問題轉(zhuǎn)化為近似加權(quán)最小二乘估計，并提出兩步半正定松弛算法進行優(yōu)化求解。

2 算法描述

2.1 近似加權(quán)最小二乘估計

將式(1)中的ni移到方程等號左邊，對兩邊進行開方運算，然后求取倒數(shù)，經(jīng)整理可以得到：

(3)

式中zi是已知常量，則式(3)左邊可以看成是關(guān)于隨機變量ni的函數(shù)。由于ni相比于zi和P很小，且均值為零，對式(3)左邊在ni=0處進行一階泰勒展開，經(jīng)進一步整理，可近似得到：

(4)

(5)

(6)

為了簡單起見，令P′=P1/2，則式(6)可以等價地轉(zhuǎn)化為如下最小化問題：

(7)

2.2 兩步半正定松弛算法

2.2.1 消除變量P′

在式(7)中，固定目標位置x，單獨求解變量P。將式(7)中的代價函數(shù)對P求導，并令導數(shù)等于0，易得P′關(guān)于x的解析表達式為

(8)

(9)

可以看到，式(9)的代價函數(shù)中只包含未知變量x，但其依然是非線性、非凸的，下面利用新的凸松弛技術(shù)將其轉(zhuǎn)化為半正定規(guī)劃問題。

2.2.2 半正定松弛

(10)

(11)

注意到，優(yōu)化問題(11)中的代價函數(shù)是凸的，但其中的兩個約束條件依然非凸。首先考慮非凸約束di=‖x-si‖2。定義輔助變量u=xΤx，結(jié)合矩陣D的定義，此約束條件可寫成

(12)

式中，Dii表示D的對角元素。此外，根據(jù)柯西-施瓦茲不等式，D的非對角元素滿足

(13)

式中|·|表示絕對值運算。接下來考慮非凸約束D=ddΤ。根據(jù)半正定松弛理論[13]，此約束條件等價于

(14)

(15)

由于約束rank(D)=1是非凸的，在問題(15)中將矩陣D的這個“秩-1約束”直接去掉，同時將u=xΤx松弛成u≥xΤx；此時，原非線性、非凸的目標定位問題最終轉(zhuǎn)化為如下半正定規(guī)劃問題：

(16)

顯然，問題(16)是一個凸優(yōu)化問題，通過調(diào)用凸優(yōu)化工具包(CVX)[14]很容易對其進行優(yōu)化求解，最終得到目標位置的估計值。

值得注意的是，雖然在對式(15)的松弛過程中直接忽略了矩陣D的秩-1約束，但下面的定理表明在求解問題(16)時得到的矩陣D的估計值總是滿足秩等于1。

定理1 假設(shè){D*,d*,x*,u*}是式(16)的最優(yōu)解，則D*的秩總是等于1的，即rank(D*)=1。

(17)

(18)

根據(jù)D′的定義，顯然{D′,d*,x*,u*}是滿足式(16)的一組可行解。而{D*,d*,x*,u*}是最優(yōu)解，則有

tr(AD*)≤tr(AD′) 。

(19)

對比式(18)和式(19)，可以得到D*=D′。由D′的定義可知，其秩是等于1的，因此rank(D*)=1。 證畢。

根據(jù)定理1及其證明可以看出，文中算法對矩陣D的松弛近似是緊的。

3 算法性能評估

下面通過仿真實驗與文獻[9]中的基于校正技術(shù)的加權(quán)直接最小二乘(WDC)算法、文獻[10]中的加權(quán)最小二乘(WLS)算法、文獻[11]中的半正定松弛(SDR)算法以及克拉美羅界(CRLB)[10]進行對比，詳細評估了文中算法的定位性能(由于文獻[12]中的二階錐規(guī)劃算法假設(shè)P是先驗已知的，與筆者提出的定位模型不同，因此這里不做對比)。在實驗中，半正定松弛(SDR)和文中算法都用凸優(yōu)化工具包(CVX)進行優(yōu)化求解。

圖1 不同測量誤差下的各算法性能對比圖

圖2 各算法的誤差累積分布函數(shù)

圖3表示各算法的定位性能隨傳感器節(jié)點數(shù)目變化的統(tǒng)計結(jié)果。可以看到，隨著傳感器節(jié)點數(shù)目的增多，由于可以提供更多冗余測量數(shù)據(jù)，各算法的定位精度均有所提高，而WLS算法變化卻很不明顯。文中算法的位置估計均方根誤差一直保持最低，定位性能優(yōu)于其他參考算法。

圖3 不同傳感器數(shù)目下各算法性能對比圖

圖4 衰減因子偏差對各算法性能的影響

圖4描述了各算法的估計均方根誤差隨衰減因子偏差的變化曲線。從圖4中可以看出，隨著衰減因子偏差的增大，由于定位模型失配的原因，所有算法的定位精度都有所下降。其中，WLS算法對衰減因子偏差最為敏感；而文中算法的性能始終保持最優(yōu)，說明文中算法對衰減因子偏差的容忍度較高。

4 結(jié)束語

針對基于聲音能量定位存在的非線性問題，筆者提出了一種兩步半正定松弛算法。先利用定位模型對于信號發(fā)射能量是線性函數(shù)這一特性，將信號發(fā)射能量從代價函數(shù)中消除；然后利用凸松弛技術(shù)將原定位問題轉(zhuǎn)化為半正定規(guī)劃問題進行求解。從理論上證明了文中的松弛近似過程是緊的。仿真結(jié)果表明，該算法的定位性能優(yōu)于傳統(tǒng)的閉式解算法以及凸優(yōu)化方法，尤其在測量誤差較大時具有明顯的優(yōu)勢。