交替非負約束框架的海洋傳感網協同定位

程 帥，吳華鋒，梅驍峻

上海海事大學 商船學院，上海 201306

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

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

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

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

1 問題描述

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

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

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

2 基于有效集的再優化協同定位（ASM-RECL）

2.1 ANCLS框架

當γ較小，d0=1 m時，對于第j個目標節點來說，式（1）和式（2）可轉化為：

原最大似然估計可轉化為最小二乘框架，即：

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

式中：

2.2 有效集法（ASM）

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

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

ASM通過內外循環來將式（8）分解成M個子問題進而求解ANCLS，即：

ASM算法偽代碼如下：

具體地：

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

其中κ為被動集Ξ相應索引值。

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

（2）在內循環過程，通過約束優化可行解，將約束外的解剔除，即：

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

2.3 基于一階泰勒級數展開的再優化

然而，ASM的實質亦是利用LS求解，而LS的求解精度并非全局最優值[29]，為進一步提高解的精度，以ASM求得的解為觀測量再構造函數，即：

定義ν為關于θ的函數，即：

式（8）則可進一步轉化為優化方程：

對于第j個目標節點來說，在附近，利用對進行一階泰勒級數展開，可得：

對于M個目標節點來說：

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

當式（21）的偏導為零時，ASM-RECL可得：

2.4 CRLB-CL

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

式中，tr表示矩陣的跡。

根據式（1）和式（2），對于第j個目標節點來說：

對于M個目標節點來說，設，則：

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

相對應的FIM可表示為：

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

3 仿真結果分析

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

3.1 不同錨節點數量下的定位誤差

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

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

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

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

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

3.3 不同目標節點數量的定位誤差

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

圖3 不同目標節點數量的定位誤差Fig.3 Localization error under different number of targets

3.4 累計密度函數（Cumulated Distributed Function，CDF）

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

圖4 不同條件下對應的CDFFig.4 Corresponding CDF under different conditions

3.5 各定位方法在相對靜態TWSNs的定位誤差

不同于相對高動態性的OSNs，TWSNs節點通常是靜態部署。為探究本文提出方法是否能夠在相對靜態的TWSNs網絡中也有著在OSNs的良好定位表現，仿真在不同噪聲條件下進行，且設置N=10，M=3。靜態的部署場景如圖5所示。

圖5 TWSNs節點靜態部署場景Fig.5 Static deployment scheme of nodes for TWSNs

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

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

4 結語

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