交替非負(fù)約束框架的海洋傳感網(wǎng)協(xié)同定位

程 帥，吳華鋒，梅驍峻

上海海事大學(xué) 商船學(xué)院，上海 201306

作為探索海洋的一種重要的工具，海洋傳感網(wǎng)（Ocean Sensor Networks，OSNs）在氣候預(yù)測、資源開發(fā)等應(yīng)用中扮演著關(guān)鍵的角色[1-3]，利用網(wǎng)絡(luò)中的節(jié)點對相應(yīng)的數(shù)據(jù)進(jìn)行采集、處理及分析，能夠有效地應(yīng)對突發(fā)的災(zāi)難性天氣亦或是提高資源開發(fā)的效率[4-5]。而在OSNs中，若采集到的數(shù)據(jù)沒有位置信息，則相應(yīng)的數(shù)據(jù)將變得沒有意義[6-9]，因此定位技術(shù)又是OSNs中的一項關(guān)鍵問題[10]。然而，如何在復(fù)雜的海洋環(huán)境中獲取較為準(zhǔn)確的位置仍是一個挑戰(zhàn)[11-13]。

為此，Huang等提出一種OSNs稀疏性節(jié)點定位方法。該方法利用基于到達(dá)角度（Angle of Arrival，AOA）的測距方法來估計錨節(jié)點與多跳路由節(jié)點間的歐式距離[14]。同樣地，為解決節(jié)點稀疏性導(dǎo)致的定位精度差等問題，Nuo等研究了一種基于水面部署移動錨節(jié)點（Surface Deployed Mobile Anchor node，SDMA）的定位方法，利用移動節(jié)點在水面上周期性運動來定位目標(biāo)節(jié)點，通過節(jié)點的機(jī)動性補償部署稀疏性導(dǎo)致的定位精度低等問題，降低錨節(jié)點的部署成本[15]。Zhang等考慮了由于水流引起的OSNs節(jié)點運動的問題，提出了基于到達(dá)時間（Time of Arrival，TOA）測距策略的OSNs節(jié)點定位，利用灰狼優(yōu)化算法來估計OSNs下一時刻的最佳位置[16]。Zhang等結(jié)合移動性預(yù)測及粒子群優(yōu)化算法，進(jìn)一步提出了一種基于TOA的OSNs定位方法，利用節(jié)點的空間相干性對目標(biāo)節(jié)點進(jìn)行預(yù)測，并基于投影定位[17]將三維場景轉(zhuǎn)化為二維場景使用三邊定位方法對目標(biāo)節(jié)點定位[18]。Cheng等則利用到達(dá)時間差（Time Difference of Arrival，TDOA）的測距方法提出了一種基于最小二乘法（Least Squares，LS）的大規(guī)模OSNs目標(biāo)節(jié)點定位法。為進(jìn)一步提高節(jié)點的定位效率，利用已時鐘同步的布置在水面的三個錨節(jié)點來輔助水下目標(biāo)節(jié)點，通過周期性收發(fā)測距信號在三維拓?fù)渲邢蚋鱾€方向進(jìn)行迭代定位[19]。

相對于TOA、AOA、TDOA等測距技術(shù)而言，基于信號強度指示值（Received Signal Strength Indication，RSSI）的測距方法成本較廉價，通信開銷較小，不需要TDOA、TOA技術(shù)的時鐘校正要求，也不要AOA技術(shù)天線相控的需求[20]，因此近些年，一些學(xué)者開始探索利用RSSI對OSNs中的目標(biāo)進(jìn)行定位。Saeed等提出了一種基于RSSI的定位框架，使用基于主優(yōu)化方法的定位算法（Majorization Approach Based Localization，MABL）來減少每個塊內(nèi)核矩陣的最短路徑的定位誤差[21]。呂品品通過基于RSSI的球形傳播模型來估計目標(biāo)節(jié)點與錨節(jié)點間的距離，并結(jié)合歐幾里德幾何學(xué)估計目標(biāo)節(jié)點位置[22]。Chang等將定位問題轉(zhuǎn)換為廣義信任區(qū)域子問題（Generalized Trust Region Sub-problem，GTRS），并進(jìn)一步研究一種已知發(fā)射功率方案和未知發(fā)射功率方案的加權(quán)最小二乘法（Weighted Least Squares，WLS）[23]。Mei等為減小異常損耗帶來的影響，提出了一種穩(wěn)健的、非協(xié)作的定位算法（Robust Non-cooperative Localization Algorithm，RNLA）[11]。該方法在已知先驗水深的情況下將三維定位問題轉(zhuǎn)換為二維定位問題。盡管RNLA可以減少異常損耗帶來的估計誤差，隨后進(jìn)一步提出一種吸收損耗抑制的定位技術(shù)[12]，以減少信號吸收損耗帶來的額外定位誤差。此外，Poursheikhali等提出一種在低傳輸頻率下基于過采樣匹配濾波器的RSS定位方法（Oversampled Matched Filter-based RSSI，OSMF-RSSI），以減少水下介質(zhì)不均勻引起的定位誤差[24]。

然而，當(dāng)網(wǎng)絡(luò)中存在多個目標(biāo)時，利用上述定位技術(shù)對多目標(biāo)單一循環(huán)依次定位，則相應(yīng)的定位效率較低。為此，引入?yún)f(xié)同理論，通過多目標(biāo)節(jié)點間的信息交互，能夠有效地提升定位效率，提高定位精度[25]。雖已有相應(yīng)的協(xié)同定位算法在陸地傳感網(wǎng)（Terrestrial Wireless Sensor Networks，TWSNs）被提出[25-28]，但不同于陸地的部署環(huán)境，高度動態(tài)的海洋環(huán)境使得網(wǎng)絡(luò)中所有節(jié)點在每一時刻的位置都處于變化，因此直接利用現(xiàn)有的TWSNs協(xié)同定位技術(shù)，定位精度往往效果不理想。故本文提出一種基于有效集的再優(yōu)化協(xié)同定位（Active Set Method based Re-Estimation Cooperative Localization，ASM-RECL）算法。將原定位問題轉(zhuǎn)化為基于交替非負(fù)約束最小二乘（Alternative Nonnegative Constrained Least Squares，ANCLS）的優(yōu)化問題，利用有效集法（Active Set Method，ASM）通過內(nèi)外循環(huán)尋求優(yōu)化問題的可行解。然而，在實際解決過程中，基于ASM算法的求解易陷入局部最優(yōu)，為進(jìn)一步提升解的質(zhì)量，改進(jìn)定位精度，利用一階泰勒級數(shù)線性展開再次構(gòu)造優(yōu)化方程，最小化定位誤差。此外，為模擬OSNs環(huán)境的高度動態(tài)性，在實驗中節(jié)點的位置在每次蒙特卡洛仿真過程中是變化的，并推導(dǎo)得到基于協(xié)同定位的克勞美羅下界（Cooperative Localization-based Cramer-Rao Low Bound，CRLB-CL），以此來驗證提出算法的有效性。

1 問題描述

假設(shè)OSNs水面部署有N個浮標(biāo)節(jié)點以及M個目標(biāo)節(jié)點，第i個錨節(jié)點位置表示為ai=[ai1,ai2]T,i=1,2,…,N；第j個目標(biāo)節(jié)點位置為xj=[xj1,xj2]T,j=1,2,…,M，其中T表示轉(zhuǎn)置。網(wǎng)絡(luò)中節(jié)點利用無線電進(jìn)行通信，節(jié)點間通過信息的交互獲取RSSI，假設(shè)各節(jié)點的發(fā)射功率相同，利用對數(shù)-正態(tài)信號損耗模型可相應(yīng)的RSSI測距值[29]，即：

通過最大化概率密度函數(shù)，可得到最大似然估計器，即：

但基于最大似然估計，即式（4）具有較高的非凸性，求解相應(yīng)的全局最優(yōu)值較為困難，且計算復(fù)雜度較高[9]。為此，本文提出一種新的求解思路，將原問題轉(zhuǎn)化至ANCLS框架下，分兩步對OSNs的多個目標(biāo)節(jié)點同時進(jìn)行求解，利用協(xié)同理論，避免單一循環(huán)地利用相對應(yīng)的測距值對目標(biāo)節(jié)點依次求解，提高網(wǎng)絡(luò)的定位效率。

2 基于有效集的再優(yōu)化協(xié)同定位（ASM-RECL）

2.1 ANCLS框架

當(dāng)γ較小，d0=1 m時，對于第j個目標(biāo)節(jié)點來說，式（1）和式（2）可轉(zhuǎn)化為：

原最大似然估計可轉(zhuǎn)化為最小二乘框架，即：

平方式（6）中的每一項并展開后，可得：

式中：

2.2 有效集法（ASM）

由于ASM能夠在有限的迭代次數(shù)里獲得較高精度的解，相較于其他求解ANCLS框架的問題而言，不僅計算復(fù)雜度較低，計算效率亦較好[30]。故本文引入ASM來求解基于RSSI定位的ANCLS問題，即求解式（8）。

假設(shè)Γ={1,2,3}表示矩陣ξ的列以及矩陣θ行的索引集合，Λ和Ξ分別為Γ兩個子集，代表主動集和被動集，即Λ?Ξ=Γ。若存在某一矩陣，并根據(jù)將1至3的索引數(shù)劃分至相應(yīng)子集Λ和Ξ中，則矩陣的對偶矩陣??可表示為。

ASM通過內(nèi)外循環(huán)來將式（8）分解成M個子問題進(jìn)而求解ANCLS，即：

ASM算法偽代碼如下：

具體地：

（1）在外循環(huán)過程中利用LS求得可行解，即：

其中κ為被動集Ξ相應(yīng)索引值。

在求得可行解后，尋找索引l∈Λ使得δl=max{δκ:κ∈Λ}，并將相關(guān)索引從主動集Λ移入被動集Ξ中。

（2）在內(nèi)循環(huán)過程，通過約束優(yōu)化可行解，將約束外的解剔除，即：

通過來回在主動集和被動集間交換可行解索引，進(jìn)而求得式（8）的解。

2.3 基于一階泰勒級數(shù)展開的再優(yōu)化

然而，ASM的實質(zhì)亦是利用LS求解，而LS的求解精度并非全局最優(yōu)值[29]，為進(jìn)一步提高解的精度，以ASM求得的解為觀測量再構(gòu)造函數(shù)，即：

定義ν為關(guān)于θ的函數(shù)，即：

式（8）則可進(jìn)一步轉(zhuǎn)化為優(yōu)化方程：

對于第j個目標(biāo)節(jié)點來說，在附近，利用對進(jìn)行一階泰勒級數(shù)展開，可得：

對于M個目標(biāo)節(jié)點來說：

將式（18）代入式（17）可得：

當(dāng)式（21）的偏導(dǎo)為零時，ASM-RECL可得：

2.4 CRLB-CL

CRLB為無偏估計可能達(dá)到的最小方差的理論極限，通常用于評估不同估計算法的性能[31]，它被定義為費雪信息矩陣（Fisher Information Matrix，F(xiàn)IM）逆的跡，即：

式中，tr表示矩陣的跡。

根據(jù)式（1）和式（2），對于第j個目標(biāo)節(jié)點來說：

對于M個目標(biāo)節(jié)點來說，設(shè)，則：

對于Fx來說，每一列表示第j個目標(biāo)節(jié)點相較于錨節(jié)點的觀測值以及其他未知節(jié)點k的觀測值對于的一階導(dǎo)，其中0表示k=j；第1行至第N行的值表示第i個錨節(jié)點相較于未知節(jié)點的觀測值對于的一階導(dǎo)，第N+1行至N+M行的值表示第j個目標(biāo)節(jié)點相較于其他未知節(jié)點k的觀測值對于的一階導(dǎo)，其中0表示k=j。而Fy與Fx同理，但是相對于的一階導(dǎo)。

相對應(yīng)的FIM可表示為：

式中，n表示蒙特卡洛仿真次數(shù)，MC表示蒙特卡洛仿真總次數(shù)。

3 仿真結(jié)果分析

為驗證提出算法的有效性，仿真實驗在Matlab R2018b進(jìn)行，仿真區(qū)域35 m×35 m，P0=-55 dBm，α=3.5，MC=1 000。此外，由于海洋環(huán)境的動態(tài)性，在每一次的蒙特卡洛仿真過程中，網(wǎng)絡(luò)中的節(jié)點位置在區(qū)域中動態(tài)變化，服從隨機(jī)游走模型[33]，通過在不同條件下對比基于ASM的非協(xié)同定位（ASM-based Non-Cooperative Localization，ASM-NCL）[9]、基于LS的協(xié)同定位（LS-based Cooperative Localization，LS-CL）[29]、基于LS的非協(xié)同定位（LS-based Non-Cooperative Localization，LS-NCL）[24]，以及基于協(xié)同思想推導(dǎo)得到的ASM-CL，基于本文算法ASM-RE推導(dǎo)得到的非協(xié)同ASM-RENCL、CRLB-NCL以及推導(dǎo)得到的協(xié)同CRLBCL，利用NRMSE作為基準(zhǔn)評判算法的有效性，即：

3.1 不同錨節(jié)點數(shù)量下的定位誤差

為探究不同錨節(jié)點數(shù)量情況下的定位誤差，仿真設(shè)置M=3，σi=5 dB。在該條件下相應(yīng)的誤差如圖1所示。由于錨節(jié)點數(shù)量的增多意味著網(wǎng)絡(luò)中可用的測距信息相應(yīng)增加，故各算法的定位誤差隨著錨節(jié)點數(shù)量的增多而減小。與非協(xié)同定位相比，協(xié)同定位除了錨節(jié)點的測距信息外，還包含有其他目標(biāo)節(jié)點的測距信息，故各算法的協(xié)同定位的定位誤差比非協(xié)同定位要來得小。其中，ASM算法的實質(zhì)雖然是利用LS解決，但增加了相應(yīng)的約束條件，在第二階段的內(nèi)循環(huán)過程中剔除了約束條件外的可行解，因此定位精度相比于LS要來得高。而ASM-RE在ASM算法的基礎(chǔ)上，通過一階泰勒級數(shù)進(jìn)行誤差最小化的線性展開，再構(gòu)造優(yōu)化方程，進(jìn)一步改善了定位精度。因此從圖1中可以看出，無論是協(xié)同定位ASM-RECL亦或是非協(xié)同定位ASM-RENCL，其定位精度都比其他算法來得高，并且更接近CRLB。

圖1 不同錨節(jié)點數(shù)量情況下的定位誤差Fig.1 Localization error under different number of anchors

3.2 不同噪聲條件下的定位誤差

為探究不同噪聲條件下的定位誤差，仿真設(shè)置M=3，N=10。在該條件下相應(yīng)的誤差如圖2所示。如預(yù)期一樣，噪聲的增加導(dǎo)致定位誤差的增大。從圖2可以看出，各算法隨著噪聲的增大相應(yīng)的定位精度也變得越差，其中基于協(xié)同定位的算法相比于基于非協(xié)同定位算法的誤差小。當(dāng)噪聲較小時，各算法的定位精度較為接近，而當(dāng)噪聲逐漸增大時，相對應(yīng)的算法精度的差別顯現(xiàn)則較為明顯。對于采用了一階線性展開的ASM-RE來說，其非協(xié)同定位的精度甚至好于基于協(xié)同定位的LS-CL。而相應(yīng)的協(xié)同定位ASM-RECL的精度相較于其他的方法來說誤差較小，且更接近于CRLB-CL。

圖2 不同噪聲條件下的定位誤差Fig.2 Localization error under different variances

3.3 不同目標(biāo)節(jié)點數(shù)量的定位誤差

為探究不同目標(biāo)節(jié)點數(shù)量對定位誤差的影響，仿真設(shè)置N=10，=5 dB。各算法在不同數(shù)量目標(biāo)節(jié)點下的定位誤差如圖3所示。從圖中可以看出，利用錨節(jié)點與目標(biāo)節(jié)點及目標(biāo)節(jié)點間的協(xié)同進(jìn)行定位的精度要顯著好于只利用錨節(jié)點與目標(biāo)節(jié)點的非協(xié)同定位。當(dāng)目標(biāo)節(jié)點較少時，目標(biāo)節(jié)點間可交換的測距信息較少，因此相應(yīng)的非協(xié)同定位精度與協(xié)同定位精度差別較小。而當(dāng)目標(biāo)節(jié)點數(shù)量增多時，相應(yīng)的目標(biāo)節(jié)點收到的測距信息亦增多，故協(xié)同定位與非協(xié)同定位的定位精度會有所差別。此外，由于目標(biāo)節(jié)點數(shù)量的增多，雖然交互的測距信息增多有益于定位精度相比于非協(xié)同定位有所改進(jìn)，但是已知位置的錨節(jié)點是一定的，因此隨著目標(biāo)節(jié)點數(shù)量的增多，總體的定位誤差是有所下降的。在其中，ASM-RECL的定位精度比其他算法來說更為優(yōu)越。

圖3 不同目標(biāo)節(jié)點數(shù)量的定位誤差Fig.3 Localization error under different number of targets

3.4 累計密度函數(shù)（Cumulated Distributed Function，CDF）

為進(jìn)一步探究本文提出算法在協(xié)同定位方面的優(yōu)越性，基于上述三個仿真實驗的在每個場景下的仿真條件，對相應(yīng)的CDF進(jìn)行仿真，結(jié)果如圖4所示。在不同錨節(jié)點數(shù)量條件下的CDF，如圖4（a）所示，從圖中可以看出，對于ASM-RECL而言，其接近100%，而ASM-CL和LS-CL來說，在達(dá)到相同概率時分別為和；在不同噪聲條件下的CDF，如圖4（b）所示，從圖中可以看出，對于ASM-RECL而言，其接近100%，而ASM-CL和LS-CL來說，在達(dá)到相同概率時分別為和；在不同目標(biāo)節(jié)點數(shù)量條件下的CDF，如圖4（c）所示，從圖中可以看出，對于ASM-RECL而言，其接近100%，而ASM-CL和LS-CL來說，在達(dá)到相同概率時分別為和。

圖4 不同條件下對應(yīng)的CDFFig.4 Corresponding CDF under different conditions

3.5 各定位方法在相對靜態(tài)TWSNs的定位誤差

不同于相對高動態(tài)性的OSNs，TWSNs節(jié)點通常是靜態(tài)部署。為探究本文提出方法是否能夠在相對靜態(tài)的TWSNs網(wǎng)絡(luò)中也有著在OSNs的良好定位表現(xiàn)，仿真在不同噪聲條件下進(jìn)行，且設(shè)置N=10，M=3。靜態(tài)的部署場景如圖5所示。

圖5 TWSNs節(jié)點靜態(tài)部署場景Fig.5 Static deployment scheme of nodes for TWSNs

從圖6的定位誤差可以看出，在TWSNs中，不同噪聲情況下各個方法的定位效果較為接近，且都隨著噪聲的增大而變差。本文提出的算法雖然在某些條件下的定位效果稍遜于現(xiàn)有算法，但總的來說其在相對靜態(tài)的TWSNs中仍具有較好表現(xiàn)。相比之下，在動態(tài)性較高的OSNs，即每一時刻節(jié)點位置處于變化的狀態(tài)，本文提出的算法具有較好的魯棒性，且從圖1到圖4的結(jié)果中可以看出，其定位效果的優(yōu)越性相較于靜態(tài)的TWSNs來得明顯。因此，在某種程度上，本文提出的算法更適用于動態(tài)性較高的OSNs，能夠為OSNs提供較為準(zhǔn)確的目標(biāo)節(jié)點位置信息。

圖6 在靜態(tài)部署中不同噪聲條件下的定位誤差Fig.6 Localization error under different variances in TWSNs

4 結(jié)語

本文提出一種OSNs協(xié)同定位算法，即ASM-RECL。將原非線性非凸的定位問題轉(zhuǎn)化在ANCLS框架下，利用ASM內(nèi)外循環(huán)進(jìn)行解決。為進(jìn)一步提升解的質(zhì)量，一階泰勒級數(shù)進(jìn)行誤差最小化的線性展開，再構(gòu)造優(yōu)化方程進(jìn)行求解，以提高定位精度，并推導(dǎo)得到了基于協(xié)同定位的CRLB對提出算法進(jìn)行審查，以評估算法的有效性。此外，為模擬海洋高度動態(tài)的環(huán)境，網(wǎng)絡(luò)中所有的節(jié)點在每一次蒙特卡洛仿真中的位置不固定，并遵循隨機(jī)游走模型。實驗結(jié)果表明，提出的協(xié)同定位算法能夠有效地提高定位精度，并且無需單一循環(huán)依次對目標(biāo)進(jìn)行定位，利用相關(guān)節(jié)點間的測距信息求解多目標(biāo)節(jié)點位置，有效地提高了定位的效率。由于海洋傳感網(wǎng)節(jié)點能量有限，因此如何簡化定位過程的計算復(fù)雜度，獲取輕量級的定位算法是未來需要進(jìn)一步研究的內(nèi)容。