基于RSSI 測(cè)距的凸半定規(guī)劃節(jié)點(diǎn)定位算法*

楊 青

（駐馬店職業(yè)技術(shù)學(xué)院信息工程系，河南 駐馬店 463000）

0 引言

無(wú)線傳感網(wǎng)絡(luò)（wireless sensor networks，WSNs）已在精準(zhǔn)農(nóng)業(yè)、森林防火、動(dòng)物跟蹤等領(lǐng)域廣泛使用。節(jié)點(diǎn)的位置信息是傳感器網(wǎng)絡(luò)具體應(yīng)用的重要前提。在多數(shù)應(yīng)用中，節(jié)點(diǎn)必須獲取自身的位置信息，缺乏位置信息的節(jié)點(diǎn)監(jiān)測(cè)數(shù)據(jù)是沒有應(yīng)用價(jià)值的。

估計(jì)未知節(jié)點(diǎn)位置有3 個(gè)步驟：1）測(cè)量信號(hào)參數(shù)，如：到達(dá)時(shí)間、到達(dá)角度，利用這些信號(hào)參數(shù)轉(zhuǎn)換成定位參數(shù)；2）利用定位參數(shù)，結(jié)合定位算法估計(jì)節(jié)點(diǎn)位置；3）利用定位算法校正位置估計(jì)，提高定位精度。

盡管全球定位系統(tǒng)（global positioning system，GPS）是解決多數(shù)定位問題的常用策略，但是考慮到成本和能耗問題，利用GPS 系統(tǒng)估計(jì)WSNs 中節(jié)點(diǎn)位置的可操作性低。因此，先在網(wǎng)絡(luò)內(nèi)部署一些已知位置的節(jié)點(diǎn)（錨節(jié)點(diǎn)），再利用錨節(jié)點(diǎn)與未知節(jié)點(diǎn)（源節(jié)點(diǎn)）間的測(cè)距數(shù)據(jù)，并結(jié)合定位算法估計(jì)未知節(jié)點(diǎn)位置。

目前存在多種方式測(cè)距，例如：到達(dá)時(shí)間（time of arrival，ToA）、到達(dá)時(shí)間差（time difference of arrival，TDoA）、到達(dá)角度（angle of arrival，AoA）和接收信號(hào)強(qiáng)度指標(biāo)（received signal strength indicator，RSSI）。相比于ToA、TDoA 和AoA，RSSI 測(cè)距無(wú)需額外的硬件設(shè)施，易實(shí)施。因此，基于RSSI 測(cè)距的定位算法受到廣泛關(guān)注。先利用RSSI 測(cè)距數(shù)據(jù)建立定位方程，再利用優(yōu)化算法求解，進(jìn)而實(shí)現(xiàn)對(duì)節(jié)點(diǎn)位置的估計(jì)。

現(xiàn)多數(shù)RSSI 定位算法將定位方程轉(zhuǎn)化為最大似然（maximum likelihood，ML）估計(jì)優(yōu)化問題。目前，研究人員針對(duì)優(yōu)化問題，提出了不同的算法。例如，文獻(xiàn)［5］采用牛頓迭代法求解ML 優(yōu)化問題，然而，ML 優(yōu)化問題等式存在較高的非線性和非凸性，傳統(tǒng)的循環(huán)迭代法求解ML 優(yōu)化問題的誤差較大，難以獲得全局最優(yōu)解。文獻(xiàn)［7］將ML 優(yōu)化問題轉(zhuǎn)化為半定規(guī)劃（semi-definite programming，SDP）問題，進(jìn)而提高定位精度，但是該算法的魯棒性差。類似地，文獻(xiàn)［8-9］先對(duì)ML 優(yōu)化問題進(jìn)行近似處理，再利用二階錐規(guī)劃（second order cone programming，SOCP）求解。然而，該算法存在一個(gè)不足：源節(jié)點(diǎn)位于凸集外時(shí)，定位誤差很大。

為此，提出基于接收信號(hào)強(qiáng)度測(cè)距的凸半定規(guī)劃節(jié)點(diǎn)定位算法RCSP。RCSP 算法先建立基于ML 的定位方程，并利用最優(yōu)化理論對(duì)定位方程近似處理，進(jìn)而形成SDP 優(yōu)化問題，最終利用內(nèi)點(diǎn)法求解源節(jié)點(diǎn)位置。仿真結(jié)果表明，提出的RCSP 算法的定位精度逼近于克羅下界（cramer rao lower bound，CRLB）。

1 問題描述

網(wǎng)絡(luò)有N 個(gè)錨節(jié)點(diǎn)和一個(gè)源節(jié)點(diǎn)。令s表示第i 個(gè)錨節(jié)點(diǎn)，其位置表示為X，用X 表示源節(jié)點(diǎn)位置。所有錨節(jié)點(diǎn)位置已知，源節(jié)點(diǎn)位置未知，需估計(jì)。

依據(jù)式（2）可以計(jì)算N 個(gè)錨節(jié)點(diǎn)所接收的RSSI值的條件概率密度函數(shù)：

2 基于SDP 松馳定位算法

由于式（4）是非線性和非凸性，對(duì)其進(jìn)行處理，再利用SDP 求解。根據(jù)最優(yōu)化理論，在式（4）右邊乘以一個(gè)正數(shù)不會(huì)改變最優(yōu)解。為此，先將式（4）轉(zhuǎn)化為：

依據(jù)泰勒級(jí)數(shù)近似理論（taylor series approxima-

再將式（12）、式（13）轉(zhuǎn)換成SDP 凸優(yōu)化問題：

3 基于內(nèi)點(diǎn)法的優(yōu)化問題求解

為了求解式（14）、式（15）所示的不等式約束的優(yōu)化問題，采用基于內(nèi)點(diǎn)法的約束優(yōu)化算法求解。內(nèi)點(diǎn)法的思想為：在可行域的邊界構(gòu)成一道很高的“圍墻”，當(dāng)?shù)c(diǎn)靠近“圍墻”，目標(biāo)函數(shù)（優(yōu)化問題函數(shù)）就快速增大，增加懲罰，阻止迭代點(diǎn)穿越“圍墻”，進(jìn)而將最優(yōu)解保留在可行域之內(nèi)?；趦?nèi)點(diǎn)法的求解步驟如算法1 所示。

?

4 性能分析

4.1 仿真參數(shù)及性能指標(biāo)

利用MATLAB 軟件建立仿真平臺(tái)，對(duì)RCSP 算法進(jìn)行M=1 000 次蒙特卡洛仿真試驗(yàn)。N 個(gè)錨節(jié)點(diǎn)隨機(jī)分布在半徑為20 m 的圓內(nèi)，一個(gè)源節(jié)點(diǎn)隨機(jī)分布在20 m×20 m 的正方形內(nèi)（源節(jié)點(diǎn)位于錨節(jié)點(diǎn)凸集內(nèi)），路徑衰減指數(shù)η=3，所有節(jié)點(diǎn)的通信半徑為R。

為了更好地分析RCSP 算法的性能，選擇UT-WSL、SDP和SOCP2 算法作為參照，如下頁(yè)表1 所示。并分析定位算法的歸一化均方根誤差性能（normalized root mean square error，NRMSE）：

表1 算法概述

除了算法的定位精度（NRMSE），算法的復(fù)雜度也是衡量定位算法性能的重要指標(biāo)。為此，依據(jù)文獻(xiàn)［14］提出計(jì)算算法的復(fù)雜度公式，分析RCSP 算法的復(fù)雜度。

4.2 CRLB 性能

CRLB 是衡量定位算法性能的重要指標(biāo)。令F表示費(fèi)舍爾信息矩陣：

4.3 性能分析

首先分析噪聲方差σ 對(duì)NRMSE 的影響，σ 從1 dB～5 dB 變化，如圖1 所示，其中，N=8。假定，σ=σ，i=1，2，…，N。

圖1 NRMSE 隨噪聲標(biāo)準(zhǔn)差σ 變化情況

由圖1 可知，噪聲標(biāo)準(zhǔn)差σ 的增加提升了NRMSE，增加定位誤差。原因在于：σ 越大，噪聲干擾越大，加大了RSSI 擾動(dòng)值的比例，這必然增加定位誤差。相比于UT-WSL、SDP 和SOCP2 算法，RCSP 算法的NRMSE 最低，定位精度最高，與CRLB相近。例如，當(dāng)σ=2 dB 時(shí)，SOCP2 算法的NRMSE 低于UT-WSL 和SDP 的NRMSE 值，但是它比RCSP算法的NRMSE 值仍高了約0.4 m。

如圖2 所示，分析錨節(jié)點(diǎn)數(shù)對(duì)NRMSE 的影響，其中σ=4 dB，N 從2～16 變化。由圖2 可知，錨節(jié)點(diǎn)數(shù)的增加使各算法的NRMSE 呈下降趨勢(shì)。原因在于：錨節(jié)點(diǎn)數(shù)越多，源節(jié)點(diǎn)獲取的測(cè)距信息越多，定位精度越高。相比于UT-WLS 算法、SDP 算法和SOCP2 算法，RCSP 算法的NRMSE 得到有效降低。例如，當(dāng)N=16 時(shí)，RCSP 算法的NRMSE 比UT-WLS算法、SDP 算法和SOCP2 算法分別下降了0.8 m、2.2 m 和1.4 m。

圖2 NRMSE 隨錨節(jié)點(diǎn)數(shù)變化情況

表2 顯示了UT-WLS 算法、SDP 算法和SOCP2算法的復(fù)雜度。由表2 可知，RCSP 算法與SDP 的復(fù)雜度相同，但是比UT-WLS 算法的復(fù)雜度略高。由圖1 和圖2 可知，RCSP 算法的NRMSE 最低，換而言之，RCSP 算法以略高的復(fù)雜度換取高的定位精度。

表2 算法的復(fù)雜度

5 結(jié)論

針對(duì)WSNs 的節(jié)點(diǎn)定位問題，提出基于接收信號(hào)強(qiáng)度測(cè)距的凸半定規(guī)劃節(jié)點(diǎn)定位算法RCSP。RCSP 算法利用RSSI 測(cè)距，再建立基于ML 估計(jì)的定位方程。通過轉(zhuǎn)換處理，使定位方程轉(zhuǎn)換成SDP形式，最終利用內(nèi)點(diǎn)法求解。性能分析表明，相比于SDP 和UT-WSL 算法，RCSP 算法降低了定位誤差。后期將進(jìn)一步優(yōu)化RCSP 算法，降低算法的復(fù)雜度，并拓展到真實(shí)環(huán)境場(chǎng)景。