基于半定松弛優(yōu)化估計(jì)的無(wú)線傳感網(wǎng)絡(luò)定位

李曉飛，陳廣福，藍(lán)天明

（1.茶產(chǎn)業(yè)大數(shù)據(jù)應(yīng)用與智能化重點(diǎn)實(shí)驗(yàn)室，福建 武夷山 354300；2.武夷學(xué)院數(shù)學(xué)與計(jì)算機(jī)學(xué)院，福建 武夷山 354300）

無(wú)線定位在過(guò)去幾十年吸引了大量學(xué)者關(guān)注，是無(wú)線傳感器不可或缺的最重要組成部分。當(dāng)這些無(wú)線傳感器節(jié)點(diǎn)的信號(hào)能被確認(rèn)地理位置時(shí)，這些信號(hào)數(shù)據(jù)才具有意義?；谀芰康臒o(wú)線定位利用接收信號(hào)強(qiáng)度(RSS)將傳統(tǒng)定位技術(shù)，如TOA[1?2]、TDOA[3?4]和AOA[5]，變成簡(jiǎn)單的定位計(jì)算。近年來(lái)，基于精度分析的定位在各種網(wǎng)絡(luò)中均有應(yīng)用，包括無(wú)線傳感器網(wǎng)絡(luò)(WSNs)[6]、無(wú)線局域網(wǎng)(WLAN) [7]和車載自組網(wǎng)(VANETs)?；诮邮招盘?hào)強(qiáng)度的定位算法會(huì)導(dǎo)致非線性和非凸優(yōu)化問(wèn)題。為了解決這個(gè)問(wèn)題，文獻(xiàn)[8]提出了一種加權(quán)最小二乘算法（WLS），近似估計(jì)傳感器節(jié)點(diǎn)位置以及采樣變換的發(fā)射功率。文獻(xiàn)[9]首先對(duì)低噪聲水平的ML 算法進(jìn)行近似估計(jì)，然后將基于二階錐規(guī)劃（SOCP）的凸優(yōu)化算法應(yīng)用到ML 估計(jì)的松弛方法中。針對(duì)基于接收信號(hào)強(qiáng)度（RSS）的定位問(wèn)題，文獻(xiàn)[10]設(shè)計(jì)了半定規(guī)劃算法。傳統(tǒng)的無(wú)線傳感器網(wǎng)絡(luò)定位算法設(shè)計(jì)是基于經(jīng)典的信道路徑損耗模型，噪聲為高斯分布。由于噪聲的非均勻性以及多源性，噪聲并不總是服從高斯分布[11]，因此，傳統(tǒng)的高斯模型不能很好地表示測(cè)量到的噪聲，導(dǎo)致定位算法的錯(cuò)誤。眾所周知，至今還沒(méi)有研究無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)算法中基于非高斯噪聲模型的實(shí)際信道路徑損失模型。為此，本文提出一種基于無(wú)跡卡爾曼濾波[12]的半定松弛優(yōu)化估計(jì)算法（SCSDP 算法），以實(shí)現(xiàn)無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)位置的準(zhǔn)確估計(jì)，噪聲由非高斯模型表示，然后對(duì)噪聲進(jìn)行經(jīng)驗(yàn)參數(shù)估計(jì)。同時(shí)，本文將定位作為一個(gè)優(yōu)化問(wèn)題來(lái)實(shí)現(xiàn)半定松弛化，并對(duì)后續(xù)的非線性和非凸優(yōu)化問(wèn)題求解，得到次優(yōu)解。實(shí)驗(yàn)結(jié)果表明，本文提出的半定松弛優(yōu)化估計(jì)（SC-SDP）算法性能優(yōu)于傳統(tǒng)定位算法。本文的具體貢獻(xiàn)如下。

1) 本文提出一種基于半定松弛優(yōu)化估計(jì)算法的定位技術(shù)，建立系統(tǒng)模型并將其作為一個(gè)優(yōu)化問(wèn)題，通過(guò)尋找初始非凸目標(biāo)函數(shù)的更低下界來(lái)重新闡述優(yōu)化問(wèn)題，將非線性和非凸問(wèn)題分別松弛優(yōu)化，得到次優(yōu)化解 。

2) 本文采用無(wú)跡卡爾曼算法過(guò)濾噪聲，獲得了一個(gè)可更準(zhǔn)確地捕捉真實(shí)均值和協(xié)方差的濾波器，采用無(wú)軌跡轉(zhuǎn)換使高斯輸入信號(hào)精確到三階，非高斯輸入信號(hào)精確到二階。這不僅避免噪聲產(chǎn)生干擾，增加了系統(tǒng)的抗干擾性，而且提高了SC-SDP 算法的定位精度。

3) 通過(guò)大量的實(shí)驗(yàn)分析，其結(jié)果表明SC-SDP算法在無(wú)線傳感器網(wǎng)絡(luò)的定位誤差（RMSE）要優(yōu)于GM-SDP[13]、WLS[8]以及CRLB[13]的定位誤差，其精度比其他算法要高。

1 系統(tǒng)模型和初步探究

假定第j目標(biāo)節(jié)點(diǎn)未知坐標(biāo)為θj=[θj1,θj2]T(θj∈R2，j=1,2,···,M)，第i參照節(jié)點(diǎn)αi=[αi1,αi2]T(αi∈R2,i=1,2,···,N)，其中M和N分別是目標(biāo)節(jié)點(diǎn)和參考節(jié)點(diǎn)的總數(shù)。從第i個(gè)參考節(jié)點(diǎn)接收的第j個(gè)目標(biāo)節(jié)點(diǎn)功率建模為

式中：P0是接收機(jī)在參考距離d0的傳動(dòng)功率；d(θj,αi)=||θj?αi||2是第j目標(biāo)節(jié)點(diǎn)和第i參照節(jié)點(diǎn)之間的距離；γ是2 和6 之間的路徑損失指數(shù)；附加噪聲 ηi,j服從高斯分布，分別表示多路徑環(huán)境中的對(duì)數(shù)正態(tài)投影效果。

高斯混合的噪聲模型及觀測(cè)功率矢量Pj=[Pi,j,Pi+1,j,···,PN,j]，所產(chǎn)生的第j目標(biāo)節(jié)點(diǎn)的聯(lián)合條件概率為

式中：λi,m是噪聲的均值um和方差的簇m相應(yīng)的權(quán)重；M是混合組件的數(shù)量。

2 問(wèn)題的提出及解決方案

其中，Ψ(θj,λ)是聯(lián)合條件概率密度函數(shù)的對(duì)數(shù)似然函數(shù)，Ψ(θj,λ)=lnp(Pj|λj)，同時(shí)混合權(quán)重 λi,m的總和等于1。然而目標(biāo)函數(shù)的組合屬性導(dǎo)致NP 難問(wèn)題[14]。為了降低優(yōu)化問(wèn)題的復(fù)雜性，可以通過(guò)尋找初始非凸目標(biāo)函數(shù)的更低下界來(lái)重新闡述優(yōu)化問(wèn)題。然后，通過(guò)松弛法重新闡述問(wèn)題，作為SDP 問(wèn)題求解，得到全局最優(yōu)解。

對(duì)可行性的配對(duì)(θj,λ)，如果該對(duì)是公式（4）優(yōu)化問(wèn)題的最優(yōu)解，為：

那么，配對(duì)(θj,λ)是公式（3）優(yōu)化問(wèn)題的次優(yōu)化。

采用Jensen 不等式，公式（5）為公式（3）的初始非凸加權(quán)目標(biāo)函數(shù)的下界，為

Ψ1(θj,λ)是參數(shù)(θj,λ)的對(duì)數(shù)似然函數(shù)的更低界。?ω′，ω′使參數(shù)(θj,λ)滿足Ψ1(θj,λ)≥Ψ??ω′。

公式（3）優(yōu)化問(wèn)題可以重新闡述為：

其中，

將公式（6）重新改寫成公式（8），為：

公式（9）是凸優(yōu)化問(wèn)題，可以利用現(xiàn)存的工具解決初始優(yōu)化問(wèn)題公式（3）的全局優(yōu)化方案。

3 半定松弛優(yōu)化估計(jì)的去噪算法

本文采用的去噪算法是無(wú)跡卡爾曼濾波（UKF）算法。如同KF 算法[15]和EKF 算法[16]，UKF 算法還利用了預(yù)測(cè)校正周期。EKF 算法通過(guò)簡(jiǎn)單地執(zhí)行一階非線性函數(shù)的線性化變換來(lái)近似非線性系統(tǒng)的狀態(tài)，而UKF 算法通過(guò)使用確定性抽樣方法解決了這個(gè)問(wèn)題 。這種采樣技術(shù)主要選取均值周圍樣本點(diǎn)集最小值集合。它在預(yù)測(cè)器和校正器之外還有一個(gè)額外的步驟，即選擇2×n+1 個(gè)sigma點(diǎn)。這些sigma 點(diǎn)傳播到非線性系統(tǒng)，并從估計(jì)的均值和協(xié)方差恢復(fù)。該算法能得到一個(gè)更準(zhǔn)確地捕捉真實(shí)均值和協(xié)方差的濾波器，無(wú)軌跡轉(zhuǎn)換的使用能精確到高斯輸入信號(hào)的三階近似，非高斯輸入至少為二階。假定先驗(yàn)狀態(tài)及誤差協(xié)方差 δt可以表示為：

而校正階段可以表示為：

4 半定松弛優(yōu)化估計(jì)（SC-SDP）算法的偽代碼

Step1，輸入i參照節(jié)點(diǎn)和j節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)的坐標(biāo)。

Step2，計(jì)算功率建模為

Step4，? ω′，ω′使參數(shù)(θj,λ)滿足Ψ1(θj,λ)≥Ψ??ω′。

公式（3）優(yōu)化問(wèn)題可以重新闡述為：

Step5，為了解決凸優(yōu)化問(wèn)題，利用現(xiàn)存的工具解決初始優(yōu)化問(wèn)題公式（3）的全局優(yōu)化方案，為

Step6，利用無(wú)跡卡爾曼濾波（UKF）算法，通過(guò)使用確定性抽樣方法解決去噪問(wèn)題。

Step7，選擇2×n+1 個(gè) sigma 點(diǎn)，將這些sigma點(diǎn)傳播到非線性系統(tǒng)，獲取一個(gè)能更準(zhǔn)確地捕捉真實(shí)均值和協(xié)方差的濾波器，以去除噪聲。

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

5.1 編碼相位轉(zhuǎn)移的傳統(tǒng)估計(jì)

傳感器執(zhí)行的核心操作之一是估計(jì)局部和輸入擴(kuò)展編碼，也是基于編碼的交叉關(guān)聯(lián)函數(shù)的評(píng)估。交叉關(guān)聯(lián)函數(shù)依賴于傳播編碼的特性?？紤]傳感接收器的信號(hào)數(shù)據(jù)采集到的局部編碼[17]，為

式中：βi={1?11?1?1?1?11?1?1?11?1?1111?1}；r(t)是單位幅度矩形函數(shù)；Tc是芯片的寬度；編碼頻率Rc=0.5 MHz。假定dloc(t)是周期性的輸入信號(hào)，可以評(píng)估交叉關(guān)聯(lián)函數(shù)的屬性。偽隨機(jī)噪聲序列的交叉關(guān)聯(lián)函數(shù)的屬性之一是當(dāng)2 個(gè)編碼完全相對(duì)應(yīng)時(shí)具有一個(gè)最大值，即dloc(t)是din(t)的不確定時(shí)間。根據(jù)要求的樣品率，取偽隨機(jī)噪聲序列樣品之后，關(guān)聯(lián)函數(shù)由公式（2）得出，為

關(guān)聯(lián)函數(shù)運(yùn)行的結(jié)果如圖1 所示，表示0 級(jí)芯片延遲時(shí)呈現(xiàn)的最大值情況，假定樣品頻率為10 MHz。

圖1 0 級(jí)芯片延時(shí)Fig.1 0 chip delay

當(dāng)輸入信號(hào)的初始編碼級(jí)跳轉(zhuǎn)到4 級(jí)芯片時(shí)，最大4 級(jí)延時(shí)的交叉關(guān)聯(lián)函數(shù)的運(yùn)行結(jié)果如圖2所示。

圖2 4 級(jí)芯片延遲時(shí)間Fig.2 Fourth chip delay

當(dāng)2 個(gè)編碼完全對(duì)應(yīng)的時(shí)候，偽噪聲序列PRN的自動(dòng)相關(guān)聯(lián)函數(shù)擁有4 級(jí)芯片延遲的最大值?？紤]高斯白噪聲的因素，接收函數(shù)s[n]可改寫為

式中：cin[n]表示輸入信號(hào)的樣品；w[n]表示白噪聲；N為樣品總數(shù)。

最大編碼相位值G，為

式中：Rc表示白噪聲的編碼頻率；fs表示輸入信號(hào)的白噪聲相關(guān)聯(lián)函數(shù)。由公式(15)可知，當(dāng)噪聲標(biāo)準(zhǔn)方差值達(dá)到2.5，輸入信號(hào)的白噪聲相關(guān)聯(lián)函數(shù)fs的最大編碼相位值G是3.99，而實(shí)際的最大編碼相位G是4。若噪聲標(biāo)準(zhǔn)方差等于12，在2 個(gè)傳播編碼之間的關(guān)聯(lián)函數(shù)最大編碼被噪聲干擾，信號(hào)取值導(dǎo)致編碼相位轉(zhuǎn)移出現(xiàn)偏差。

5.2 半定松弛優(yōu)化估計(jì)算法的實(shí)驗(yàn)結(jié)果分析

本文采用若干個(gè)實(shí)驗(yàn)評(píng)估半定松弛優(yōu)化算法性能并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析。如圖3，考慮100×100 m2的二維正方形區(qū)域，獨(dú)立部署240 個(gè)傳感器，包括20 錨。假定噪聲遵從雙模高斯混合分布，α1=0.67，β1=?4.36 dBm，σ1=6.83 dBm，α2=0.84，β2=3.76 dBm，σ2=5.63 dBm。室內(nèi)噪聲檢測(cè)技術(shù)就是計(jì)算每混合組件的均值和方差值。本文采用100 個(gè)蒙特卡洛自帶的20 個(gè)不等錨定量計(jì)算RMSE的值來(lái)評(píng)估室內(nèi)噪聲水平。

圖3 傳感器數(shù)量和 RMSE 的關(guān)系Fig.3 Relationship between the number of sensors and RMSE

由圖3 可知，隨著傳感器數(shù)量的增加，噪聲的干擾也越來(lái)越影響到無(wú)線傳感器網(wǎng)絡(luò)的性能。隨著傳感器數(shù)量的增加，均方根誤差（RMSE）隨著方差的變化出現(xiàn)向下波動(dòng)。當(dāng)噪聲方差σ1=6.83 dBm時(shí)，傳感器數(shù)量的增多，導(dǎo)致更多噪聲干擾以及信號(hào)傳輸?shù)牟环€(wěn)定，均方根誤差(RMSE)向下波動(dòng)增大，當(dāng)再加入噪聲方差σ2=5.63 dBm時(shí)，2 個(gè)噪聲疊加在一起形成雙模高斯噪聲，隨著傳感器數(shù)量增加，更多噪聲干擾導(dǎo)致均方根誤差(RMSE)向上波動(dòng)增大。

5.2.1 均方根方差（RMSE）的實(shí)驗(yàn)分析

本節(jié)分析了半定松弛化定位問(wèn)題的實(shí)驗(yàn)結(jié)果。假定有N個(gè)參考節(jié)點(diǎn)均勻分布在以（0,0）為圓心，200 m 為半徑的圓周上。第i參考點(diǎn)（i=1,2,···,N）的位置為

將本文SC-SDP 算法與半定規(guī)劃算法SDP[18?19]、ML 算法[20]進(jìn)行比較，并以CRLB 算法作為無(wú)線傳感器網(wǎng)絡(luò)定位性能的比較標(biāo)準(zhǔn)。利用凸優(yōu)化（CVX）[21]解決半定松弛優(yōu)化估計(jì)（SC-SDP）算法?；c(diǎn)和參考點(diǎn)不同的幾何層次影響了定位的準(zhǔn)確性。為了研究基點(diǎn)和參考點(diǎn)的幾何層次的效果，本文的實(shí)驗(yàn)采用N=5參考點(diǎn)，選擇5 個(gè)不同的基點(diǎn)定位，分別代表5 種典型的幾何形基點(diǎn)—參考點(diǎn)設(shè)置。本文SC-SDP 算法與GM-SDP 算法[13]和CRLB算法等的比較結(jié)果如表1 所示。

表1 不同算法的均方根方差Table 1 Root mean square variances of different algorithms

從表1 看出：當(dāng)參照點(diǎn)數(shù)目逐漸增大時(shí)，均方根方差（RMSE）逐漸降低。當(dāng)參照點(diǎn)數(shù)目增大到18 時(shí)，相比GM-SDP[13]算法、WLS 算法以及CRLB算法，SC-SDP 算法的均方根方差（RMSE）最優(yōu)。因此，雖然參照點(diǎn)數(shù)目增多導(dǎo)致噪聲增加，但是SC-SDP 算法的性能是遞增的 。

5.2.2 半定松弛優(yōu)化估計(jì)算法的實(shí)驗(yàn)分析

SC-SDP 算法是優(yōu)化并去除半定松弛化算法產(chǎn)生的噪聲，同時(shí)調(diào)整實(shí)驗(yàn)參數(shù)。本文的實(shí)驗(yàn)采用無(wú)跡卡爾曼濾波算法優(yōu)化并緩解半定松弛化算法產(chǎn)生的噪聲。本文拓展了無(wú)跡傳送信道，獲得推導(dǎo)和應(yīng)用框架，有效地消除了幾乎所有常見(jiàn)的非線性坐標(biāo)變換的噪聲偏差。圖4 是添加卡爾曼過(guò)濾器之后的WLS 和SC-SDP 兩種算法的定位誤差比較結(jié)果。傳感器數(shù)量增加也就間接導(dǎo)致位置誤差增加。當(dāng)最后傳感器數(shù)目增加到20 時(shí)，SC-SDP 算法比WLS 算法定位誤差大，但和 圖5 添加卡爾曼過(guò)濾器之前的定位誤差相比，SC-SDP 算法的定位誤差也是降低的。

圖4 WLS 和SC-SDP 的位置誤差比較（添加卡爾曼過(guò)濾器之后）Fig.4 Comparison of position errors between WLS and SCSDP(After adding the Kalman filter)

圖5 WLS 和SC-SDP 的位置誤差比較（添加卡爾曼過(guò)濾器之前）Fig.5 Comparison of position errors between WLS and SCSDP(before adding the Kalman filter)

圖5 是增加卡爾曼過(guò)濾器之前的實(shí)驗(yàn)結(jié)果。采用WLS 算法和SC-SDP 算法計(jì)算出均方根方差，再通過(guò)均方根方差計(jì)算定位位置的誤差。傳感器數(shù)目剛增加時(shí)，定位誤差快速遞增，直到傳感器數(shù)目增加到18 時(shí)，定位誤差進(jìn)入相對(duì)穩(wěn)定的階段，但是定位誤差是增大的。

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

為提高無(wú)線傳感網(wǎng)絡(luò)室內(nèi)定位精度，本文提出基于半定松弛優(yōu)化估計(jì)算法的無(wú)線傳感網(wǎng)絡(luò)定位算法（SC-SDP 算法）。在半定規(guī)劃算法的基礎(chǔ)上，將算法的約束條件松弛化，使定位更加準(zhǔn)確。同時(shí)采用無(wú)跡卡爾曼濾波（UKF）算法過(guò)濾信號(hào)傳輸過(guò)程中的噪聲，對(duì)無(wú)線傳感器網(wǎng)絡(luò)定位進(jìn)行精確分析。將SC-SDP 算法與WLS 算法、CRLB 算法進(jìn)行比較實(shí)驗(yàn)和過(guò)濾噪聲前后的比較實(shí)驗(yàn)。噪聲沒(méi)過(guò)濾前時(shí)，實(shí)驗(yàn)結(jié)果表明，隨著傳感器參考點(diǎn)位置數(shù)量的增加，定位誤差呈上升趨勢(shì)。因此，在采用無(wú)跡卡爾曼濾波（UKF）算法過(guò)濾掉傳輸過(guò)程中的噪聲之后，定位誤差呈遞減趨勢(shì)，半定松弛優(yōu)化估計(jì)算法性能也得到提升。實(shí)驗(yàn)結(jié)果也表明SC-SDP算法的均方根方差（RMSE ）比GM-SDP 算法、WLS算法以及CRLB 算法的均方根方差更小。在未來(lái)的網(wǎng)絡(luò)定位算法里，采用半定松弛優(yōu)化估計(jì)算法來(lái)解決定位精度性能分析具有更加廣闊的前景。