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

田 強(qiáng)，馮大政，李 進(jìn)，胡豪爽

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

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

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

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

1 定位模型

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

(1)

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

(2)

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

2 算法描述

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

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

(3)

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

(4)

(5)

(6)

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

(7)

2.2 兩步半正定松弛算法

2.2.1 消除變量P′

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

(8)

(9)

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

2.2.2 半正定松弛

(10)

(11)

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

(12)

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

(13)

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

(14)

(15)

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

(16)

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

值得注意的是，雖然在對(duì)式(15)的松弛過(guò)程中直接忽略了矩陣D的秩-1約束，但下面的定理表明在求解問(wèn)題(16)時(shí)得到的矩陣D的估計(jì)值總是滿足秩等于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)

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

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

3 算法性能評(píng)估

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

圖1 不同測(cè)量誤差下的各算法性能對(duì)比圖

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

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

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

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

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

4 結(jié)束語(yǔ)

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