一種高斯噪聲下基于最大分散度的WSN半定規劃定位算法*

何國鋼，鄧 平

(西南交通大學信息編碼與傳輸重點實驗室，成都610031)

無線傳感器網絡(WSN，Wireless Sensor Networks)，由于其在軍事偵察、交通監管、工農業控制、環境監測、物聯網、搶險救災等領域廣闊的應用前景，已經成為國際上備受關注的研究課題之一。在WSN的應用中，一個關鍵問題是如何獲取網絡節點的地理位置信息。因此，定位技術是一項非常重要的研究內容。定位算法根據采用的定位信息不同，可分為基于非測距和基于測距定位算法[1－2]。前者通常利用網絡的連通性等信息進行定位，而后者則是利用測距裝置獲得的節點間的距離信息實現定位。由于非測距算法定位精度不理想，基于測距定位算法成為實際應用中采用的主要定位解決方案。然而，在噪聲環境下，距離測量值的不準確性會導致測距定位算法定位精度明顯下降。因此，研究噪聲環境下傳感器網絡測距定位技術是非常必要的。

無線傳感器網絡定位問題可以被視為作圖實現問題[3]，通過將圖中的邊作為約束，將其建模成一個半定規劃SDP(Semi-Definite Programming)問題，從而實現定位。近年來，部分學者開展了相關的研究工作。文獻[4]將節點間點到點的通信連接視為節點位置的幾何約束，將定位問題轉化為凸優化問題，并通過半定規劃進行求解，然而其定位精度不高。與文獻[4]非測距方法相比，文獻[5]提出了一種基于測距的半定規劃定位方法，第一次構造了無線傳感器網絡定位問題的半定規劃松弛模型——fullSDP，該方法需要較少的錨節點即可完成定位。針對fullSDP計算復雜度過高不適合解決較大規模WSN定位問題的缺點，文獻[6]將單一的半正定矩陣錐松弛為一系列較小的半正定矩陣錐，進一步松弛了半定規劃定位模型，有效地降低了計算復雜度。文獻[7]也利用定位問題的稀疏性提出了一種半定規劃松弛模型的稀疏版本，提高了解決定位問題的效率。文獻[8]則是將半定規劃定位問題劃分成多個子問題進行求解。為解決大規模WSN定位問題，研究人員也提出了多種分布式半定規劃定位算法[9－10]。

1 高斯噪聲下WSN半定規劃定位

1.1 問題描述

在二維平面中，無線傳感器網絡中分布著m個錨節點和n個未知節點。假設所有節點的通信范圍為半徑為R的圓，當節點間的實際距離不大于通信半徑時，則兩節點能夠直接通信。定義分別為未知節點i與錨節點k間距離的真實值和測量值;未知節點 i和 j間距離的真實值和測量值。X={x1，x2，…，xn}∈R2×n表示未知節點矩陣，A={a1，a2，…，am}∈R2×m表示錨節點矩陣。定義矩陣，則無線傳感器網絡定位問題可以表示為式(1):

其中，eij為第i個元素為1第j個元素為－1的n維列向量;ei為第i個元素為1的n維列向量;Nx表示能夠直接通信的未知節點對的集合;Na表示能夠直接通信的未知節點與錨節點對的集合。

為解決式(1)中的傳感器網絡定位問題，文獻[5]通過引入松弛變量并應用舒爾補定理將傳感器網絡定位問題松弛為半定規劃問題，得到基于測距的傳感器網絡定位問題的半定規劃松弛模型(fullSDP)[5]:

為進一步提高定位精度，文獻[12]提出將半定規劃的解作為初始點，使節點沿著節點距離誤差的負梯度方向移動，將梯度搜索方法應用到定位問題中，其中目標函數為:

對f進行求導，目標函數f在xi的梯度為:

假設梯度搜索方法的迭代步長為α，則其迭代公式如式(5)。當?fxi接近零或達到最大迭代次數時，則沿xi方向的搜索結束。

現有研究表明，以式(2)的解作為初始點，梯度搜索方法能有效地改善半定規劃的定位結果。然而，當節點間距離測量受噪聲影響時，通過式(2)求解得到的節點估計位置將會向錨節點凸包中心匯聚[10]。這種匯聚效應將使部分節點定位誤差太大而不適合作為梯度搜索方法的初始解，導致梯度搜索方法改善定位結果的效果不明顯，甚至會進一步惡化半定規劃的定位結果。

人力資源管理系統主要是采用B/S(Browser/Server)架構即瀏覽器／服務器架構為支撐，該架構是隨著英特網技術的興起，并對C/S架構進行改進的一種優化架構。此外，在B/S架構下，用戶所有的工作界面均是運用WWW瀏覽器來實現整個的，也有極少一部分事務邏輯是通過前端(Browser)實現的，但是大多數事務邏輯都運用服務器端(Server)來實現，進而形成完整的三層架構。和傳統架構相比，這種架構優勢非常明顯，主要表現為維護運行方法較為簡便、快捷，能夠從不同地域和不同的人員進行自由選擇，并運用不同的接入方式來完成數據訪問與操作工作。

1.2 最大分散度SDP定位算法

為解決fullSDP在噪聲環境下存在的問題，本文借鑒文獻[13]中非測距定位算法中分散度的概念，在測距定位中，定義分散度SD(Scatteredness Degree)為所有未知節點與錨節點質心間的距離的均方值，即:

假設節點間的測量距離受高斯噪聲影響，則:

利用節點間距離的測量值和噪聲的標準差，可以確定節點間距離的一個上界，如式(8):

將最大化網絡分散度作為目標函數，式(8)作為約束條件，傳感器網絡定位問題可以表示為如式(9)的最優化問題。

由高斯分布的性質可知，部分節點間的距離不滿足式(8)，即存在誤差。為此，加入松弛變量βij和βik，則最優化問題式(9)的目標函數中應包含最小化誤差項，如式(10):

其中，p(η)是定義的目標函數平衡因子，其值與網絡平均連通度η有關。根據仿真與數值分析，p(η)可以由式(11)確定。

將最優化問題(9)表示為矩陣形式，并將其松弛為半定規劃模型，則最大分散度半定規劃定位算法MSDSDP(Maximum Scatteredness Degree SDP)如式(12):

為了進一步提高定位精度，同樣將作為初始點進行梯度搜索，以期進一步提高定位精度。

2 仿真與分析

假設無線傳感器網絡60個未知節點隨機分布在一個1×1的正方形區域中，錨節點的分布和通信半徑R將在具體的仿真實驗中說明。節點間距離的測量值通過式(13)得到。

2.1 仿真實驗1

設置錨節點個數為8，噪聲因子為0.2，通信半徑為0.25，仿真結果如圖1所示。由圖可以看出，MSDSDP能在一定程度上克服fullSDP節點估計位置向錨節點凸包中心匯聚的問題。圖1中圓圈表示未知節點真實位置，星型表示未知節點估計位置，直線表示定位誤差，棱形表示錨節點。

圖1 兩種算法仿真結果示意圖

2.2 仿真實驗2

本實驗研究通信半徑R的影響。設置錨節點個數為8，噪聲因子為0.2，通信半徑 R分別設為0.2，0.25，0.3，0.35，0.4(連通度分別為 7.22，10.93，14.95，19.63，25.03)，仿真結果如圖 2 所示。由圖可以看出，MSDSDP的定位精度優于fullSDP，尤其是在低連通度情況下。圖2顯示，在低連通度下出現了梯度搜索方法使fullSDP定位結果惡化的情況;MSDSDP的解比fullSDP更適合用于梯度搜索方法的初始解。

圖2 通信半徑R對MSDSDP的影響

2.3 仿真實驗3

本實驗研究噪聲因子的影響。設置錨節點個數為8，通信半徑為0.25，仿真結果如圖3所示。圖中可以看出，MSDSDP隨著噪聲的增大，定位精度逐漸下降，但是明顯優于fullSDP及其梯度搜索后的定位精度。圖3表明，MSDSDP結合梯度搜索方法能夠很好地解決高斯噪聲下傳感器網絡定位問題，并再一次表明MSDSDP的解比fullSDP更適合用于梯度搜索方法的初始解。

圖3 噪聲因子對MSDSDP的影響

2.4 仿真實驗4

本實驗研究錨節點個數的影響。設置通信半徑為0.25，噪聲因子為0.2，仿真結果如圖4所示。圖中顯示，半定規劃定位方法在錨節點個數很少的情況下也能達到良好的定位精度。然而，MSDSDP在錨節點數量少時，定位精度明顯高于fullSDP，并且對錨節點個數具有更好的魯棒性。

根據文獻[5]，fullSDP采用內點法解決n個節點的傳感器網絡定位問題的計算復雜度為O(n3)。由式(2)和式(12)可以看出，MSDSDP的變量個數和約束條件個數與fullSDP相同，由此推斷MSDSDP的計算復雜度也為O(n3)。綜上分析可知，相對于fullSDP，MSDSDP在不增加計算復雜度的情況下能夠明顯提高定位精度。由文獻[6]分析知，梯度搜索方法的計算復雜度為O(λn)(λ為迭代搜索次數)，遠遠小于半定規劃的計算復雜度。因此，MSDSDP結合梯度搜索方法能在增加較小代價的情況下定位精度明顯得到改善。

圖4 錨節點個數對MSDSDP的影響

3 結論

本文提出了一種新的在噪聲情況下最大化網絡節點分散度的半定規劃定位算法(MSDSDP)。該算法能夠有效地克服fullSDP中節點向錨節點凸包中心匯聚的問題，定位精度得到有效提高。分析還表明MSDSDP對網絡連通度、噪聲水平和錨節點個數更具魯棒性，并且MSDSDP的解更適合作為梯度搜索方法的初始解。因此，MSDSDP結合梯度搜索方法能夠適用于具有噪聲的實際WSN網絡環境中未知節點的定位。

[1]楊鳳，史浩山，朱靈波，等.一種基于測距的無線傳感器網絡智能定位算法[J].傳感技術學報，2008，21(1):135－140.

[2]石為人，賈傳江，梁煥煥.一種改進的無線傳感器網絡DV-Hop定位算法[J].傳感技術學報，2011，24(1):83－87.

[3]Man-Cho So A，Ye Yinyu.Theory of Semidefite Programming for Sensor Network Localization[J].Math Program，2007，109:367－384.

[4]Doherty L，Ghaoui L E，Pister S J.Convex Position Estimation in Wireless Sensor Networks[C]//IEEE Infocom，Anchorage，2001:1655－1663.

[5]Biswas P，Ye Y.Semidefinite Programming for Ad Hoc Wireless Sensor Network Localization[C]//3rd IPSN，Berkeley，2004:46－54.

[6]Wang Zizhuo，Zheng Song，Boydy Stephen，etal.Further Relaxations of the SDP Approach to sensor Network Localization[Z].Dept of Management Science and Engineering，Stanford University，2006.

[7]Sunyoung Kim，Kojima M.Semidefinite Programming Relaxations forSensor Network Localization[C]//IEEE International Symposium on Computer-Aided Control System Design，2010.

[8]Carter M W，Jin H H，Saunders M A，et al.An Adaptive Subproblem Algorithm for Scalable Wireless Sensor Network Localization[J].SIAM，2006，17(4):1102－1128.

[9]Biswas P，Ye Y.A Distributed Method for Solving Semidefinite Programming Arising from Ad Hoc Wireless Sensor Network Localization[R].Dept of Management Science and Engineering，Stanford University，2006.

[10]Shi Q，He C，Chen H，et al.Distributed Wireless Sensor Network Localization via Sequential Greedy Optimization Algorithm[J].IEEE Transactions on Signal Processing，2010，58(6):3328－3340.

[11]Biswas P，Liang T C，Toh K C，et al.Semidefinite Programming Approaches for Sensor Network Localization with Noisy Distance Measurements[J].IEEE Tran.Auto.Sci.and Eng，2006，3(4):360－371.

[12]Liang T，Wang T，Ye Y.A Gradient Search Method to Round the Semidefinite Programming Relaxation Solution for Ad Hoc Wireless Sensor Network Localization[R].Dept of Management Science and Engineering，Stanford University，2004.

[13]Shi Q，He C.A SDP Approach for Range-Free Localization in Wireless Sensor Networks[C]//IEEE ICC，Beijing，2008:4214－4218.