移動無線傳感網絡的分布式協作定位的研究

賀 偉 梁 潘

1(阿壩師范學院電子信息與自動化學院 四川 汶川 623002) 2(成都航空職業技術學院機電工程學院 四川 成都 610100)

0 引 言

微型的、能量受限的具有數據感知能力的傳感節點組成的無線傳感網絡WSNs(Wireless Sensor Networks)[1-2]已在醫療、環境監測、軍事等領域得到廣泛應用。這些應用均以節點有效的收集數據為前提，并且節點所感知的數據需配備準確的位置才具有價值，換言之，無準確位置的感測數據是無價值的。因此，節點定位已成為WSNs的研究焦點[3-4]。

考慮到WSNs的節點能量、尺寸和成本限制，常通過測量傳感節點與錨節點間的測距信息估計傳感節點位置，其中錨節點是指已知位置的傳感節點[3]。通常，通過測量無線信號的物理參數獲取測距數據。在眾多的測量技術中，基于到達時間TOA[4]受到廣泛關注。

目前，盡管研究人員提出不同的定位算法，但是這些定位算法是針對靜態傳感網絡，即傳感節點和錨節點都是靜態的。然而，在一些實際場景中，如水下傳感網絡，小型的跟蹤移動網絡、車聯網。這些場景中節點是非靜態的。

現只有少數文獻關注了移動錨節點協助定位問題[5-6]。文獻[6]針對移動傳感節點環境，研究了基于最大似然ML(Maximum Likelihood)估計的節點定位問題。但是，文獻[6]所提出的定位方案屬非協作式[7]。在非協作式定位中，每個傳感節點需要不斷與錨節點通信。然而，如果傳感節點不能直接與足夠多的錨節點通信時，傳感節點就無法定位。例如，在二維空間中，每個傳感節點至少需要與三個錨節點連接，才能定位，否則傳感節點將無法獲取自己的位置。為了解決此問題，協作定位[7]得到關注。在協作定位算法中，每個節點與其通信范圍內的節點進行通信，獲取更多測量信息，進而提高定位精度。

為此，基于TOA測量，提出二階錐規劃的分布式定位算SOCP-DL(Second-order Cone Programming-based distributed localization)算法。SOCP-DL算法將復雜的ML問題分解為分布式子問題，然后再由傳感節點局部求解。因此，提出的SOCP-DL算法適用于大型WSNs網絡。

1 測距模型

假定WSNs內有ms個傳感節點和ma個移動錨節點構成，這些移動錨節點能獨自移動，并且錨節點位置已知。類似文獻[6]，假定每個移動錨節點能測量它的速度矢量，包括大小和方向，并將這些速度矢量用于定位階段。

此外，引用式(1)的感測模型協作速度測量，進而完成定位[7]：

(1)

(2)

(3)

其中，1≤i≤ms，1≤j≤ms+ma，且i≠j，1≤n≤N。

(4)

2 算法設計

本文算法先利用測距值和測速值作為ML估計的觀察數據，再建立ML估計表達式。考慮到ML估計為非凸、NP-hard問題，利用SOCP松弛技術求解。然而，為了降低算法的復雜度，將集中式求解轉化為分布式求解，整個SOCP-DL算法框架如圖1所示。

圖1 本文算法框架

2.1 基于ML定位

(5)

基于TOA場景，定義D集，其內元素表示所有的測距值，如式(6)所示：

(6)

依據速度測量值V和測距值D，再最大化條件概率分布函數f(D,V|S)，便可獲取ML估計。具體而言，由于速度和距離測量誤差相互獨立，可得f(D,V|S)=f(D|S)f(V|S)，其定義如式(7)所示：

(7)

再對式(7)兩邊取對數，便可得ML估計值：

(8)

此外，式(8)是基于ML的協作定位估計，且其屬于非凸的，通常認為是NP-hard。針對非凸問題，常利用半定規劃SDP(Semi-definiteProgramming)松弛技術求解。然而，SDP技術并不適用于求解式(8)，這主要是基于兩點原因：1) 對于大型網絡，利用SDP技術求解，計算復雜度很高；2) 由于它們的復雜結構[8]，利用SDP技術求解，需要集中計算。為此，SOCP-DL算法利用SOCP松弛技術求解，降低計算時間，更適合于分布式算法。

2.2 基于SOCP定位

將式(8)轉換成集中式凸SOCP問題。先建立約束問題，如式(9)所示：

(9)

(10)

(11)

利用現成的凸優化軟件包(CVX)便可有效地求解式(11)。CVX是MATLAB軟件自帶的軟件包，并提供MATLAB接口。通過CVX軟件包可解決線性規劃、最小二乘法等問題。

然而，式(11)需要集中方式求解，其要求將所有測距值傳輸至融合中心FC，這將導致大量的功率消耗和高的計算成本。為此，以分布方式求解式(11)。

2.3 分布式實施SOCP

分析如何利用分布方式實現SOCP算法。首先，將約束優化的式(9)問題進行松弛：

(12)

(13)

觀察到式(13)不難發現，對于每個傳感節點i∈{1,2,…,ms}，式(13)僅取決于位置和它的鄰居節點所轉發的測距信息和速度測量值。因此，可將式(13)分解為ms個獨立的子問題。

(14)

3 實 驗

3.1 仿真環境

利用MATLAB 7.1軟件建立仿真平臺，并通過實驗分析SOCP-DL算法的性能。利用CVX編程工具實施凸規劃[9]。所有傳感節點和錨節點部署于10 m×10 m方形區域。最初(n=1)，所有錨節點和傳感節點隨機分布于10 m×10 m區域，并且它們依據隨機的點移動模型(Random-way point mobility)[10-11]進行移動。最大的移動速度為Vmax。

在每個時刻，每個節點就隨機地選擇目的地，當它達到了目的地后，再隨機地選擇下一目的地，并以不同的速度移動。此外，引用均方根誤差RMSE(Root Mean Square Error)作為性能指標。

3.2 實驗數據分析

圖2 RMSE隨的變化曲線

圖3 RMSE隨R、Vmax變化曲線

從圖3可知，通信半徑R的增加，有利于降低RMSE。這主要是因為：通信半徑越大，節點的通信范圍越寬，節點獲取的信息就越多，越有利于定位。例如，當Vmax=1.4 m/s時，R=2.5 m增加至R=5.0 m,RMSE也隨之下降。但是，Vmax從1.4 m/s增加至2.8 m/s比通信半徑R從2 m增加至4 m，RMSE降低得更多。

圖4 對比實驗

從圖4可知，與文獻[7]的算法相比，提出的SOCP-DL算法的RMSE得到有效地降低。例如，在n=15,Vmax=1.4 m/s時，文獻[7]算法的RMSE為3 m，而提出SOCP-DL算法的RMSE為2.25 m。這些數據表明，提出的SOCP-DL算法能夠有效地降低RMSE。

表1 算法的運行時間

E-NIL算法的計算時間為2.34 s，而文獻[7]算法的計算時間為3.01 s。但是采用集中式求解的運行時間達到3.32 s，高于E-NIL。這也說明通過分布式實施SOCP能夠有效地降低算法的復雜度。

4 結 語

本文針對移動WSNs的節點定位，提出基于二階錐規劃的分布式定位算法SOCP-DL。SOCP-DL算法先基于測距和速度測量值，建立ML估計表達式，然后再利用SOCP松弛技術求解，并對SOCP松馳技術分布式實施，進而降低算法的復雜度。實驗數據表明，提出的SOCP-DL算法能夠有效地提高定位精度。