基于交替修正牛頓法的分布式傳感器定位算法

徐莎莎， 周 芳

(1.桂林電子科技大學廣西無線寬帶通信與信號處理重點實驗室， 桂林 541004； 2.桂林電子科技大學生命與環境科學學院， 桂林 541004)

無線傳感器網絡(wireless sensor network, WSN)是由大量的傳感器節點構成的網絡[1]，可以對指定環境進行實時監測。因其低成本、低功耗、體積小、多功能等諸多優點，無線傳感器網絡已經被廣泛地應用于醫療(病人檢測)、環境(大鴨島實驗)、家庭(用水檢測)等領域[2-3]。其中大部分應用場景需要結合節點的位置信息，才能提供有效的數據信息。

目前，為了經濟有效地實現WSN中的節點定位，通常在WSN中設置少部分位置已知的傳感器節點，這部分位置已知的傳感器節點安裝了可以獲取位置信息的全球定位系統(global positioning system, GPS)或中國北斗導航衛星系統(Beidou navigation satellite system, BDS)[4]，這些節點稱為已知位置(location aware, LA)節點，又稱錨節點，而其他需要定位的傳感器節點稱為未知位置(location unaware, LU)節點[2]。實現WSN中的節點定位還需獲得測距信息，測距信息可以通過到達角(angle of arrival, AOA)、接收信號強度(received signal strength, RSS)、到達時間(time of arrival, TOA)和到達時間差(time difference of arrival, TDOA)等方式獲得[5]。最后，結合錨節點位置信息和測距信息，采用協作定位方法定位LU節點[2]。

現有的大多數定位算法都假定錨節點位置準確，以便估計LU節點位置[2,6-8]。但在許多實際情況下，可能無法準確知道錨節點位置，這種不確定性反過來會顯著地影響估計傳感器節點位置的質量，水下WSN中的節點定位問題就是一個顯著例子[9]。水下WSN節點分為三類：LU節點、錨節點和參考節點，錨節點和部分已經定位的LU節點可以組成參考節點。水下WSN中的節點定位目標是：利用錨節點和參考節點信息，采用協作定位方法定位LU節點。但射頻波在水下會發生嚴重衰減，導致錨節點位置易出錯和測距誤差增大，從而產生較差的定位效果[10]。因此，考慮WSN中存在錨節點位置誤差是一項很有意義的工作。

現有的定位算法基于運算方式不同可劃分為兩種。一種是集中式定位算法，集中式定位算法的運算特點是：融合中心進行位置估計時，需要獲取所有范圍內傳感器節點之間的連接信息。Biswas等[8]將定位問題歸結為集中式優化問題，然后，采用半正定規劃松弛的方法，通過引入正則項減少優化變量的個數，并最終通過梯度下降法細化LU節點的位置，從而使得定位精度有所提高。但是，集中式定位算法隨著WSN規模增大，通信代價也會變大，帶寬會消耗過快，會導致整個WSN壽命縮短，無法適用于較大規模WSN。另一種是分布式定位算法，與集中式定位算法的運算方式相比，分布式定位算法的運算特點是：將處理器分布到每個傳感器節點上，采用局部化處理的方式，更高效節能，更易擴展到較大規模WSN。Srirangarajan等[1]采用二階錐規劃松弛技術將定位問題轉化為凸優化的問題，設計出了一種分布式算法，可適用于大規模WSN，但是該算法對于網絡邊界節點不能夠很好定位，且需要更多的錨節點信息。Soares等[11]采用松弛非凸的最大似然估計條件，提出了一種簡單凸松弛算法，并且每個節點采用梯度法達到收斂，從而降低了WSN的通信量。但是該算法要求LU節點在錨節點凸包之內才能保證良好定位效果。Zhou等[12]將WSN定位問題考慮成箱型約束下的歐式距離優化問題，提出了一種快速矩陣投影算法，有效地提高節點定位的速度。但是，該算法會使得誤差累積和傳播。上述定位算法具有很強適用性，易推廣到處理錨節點位置誤差影響定位精度這一優化問題。

為了克服錨節點位置誤差影響定位精度這一問題，提出了基于交替修正牛頓法的分布式定位算法。首先，可將WSN看作一個無向圖，特定區域內部署的傳感器節點之間看作有一條邊相連接，能相互通信。然后，將整個無向圖劃分成部分重疊的子圖，這樣全局的定位問題被劃分成一系列的子圖內定位問題。對于子圖內定位問題的求解，提出了基于交替修正牛頓法的定位算法，其算法過程包含三個步驟：首先，LU節點根據不準確的錨節點和測距信息估計其位置，然后對部分重疊子圖內的LU節點融合求平均，得到初步估計值；其次，不準確的錨節點根據LU節點初步估計值和測距信息更新其位置，再對部分重疊子圖內的錨節點融合求平均，得到相對準確的錨節點位置；最后，LU節點再根據相對準確的錨節點位置和測距信息重復第一步步驟，得到最終估計值。仿真結果表明，當WSN存在錨節點位置誤差時，相比較于現有的分布式定位算法，節點定位效果更好，且易適用于較大規模的WSN。

1 定位問題

N個傳感器節點被隨機分布在R2維空間的特定區域內，其中，有m個LA節和n個LU節點。所有準確位置的LA 節點表示為a1,a2,…,am，其在k點位置表示為ak=[xk,yk]T，所有LU節點表示為x1,x2,…,xn，其在i點位置表示為xi=[xi,yi]T。利用RSS測距技術能夠測出傳感器節點之間的距離[13-14]，但是，由于在此過程中易受到多徑衰落等不確定因素影響，測得的數據往往是帶噪聲的。因此，假設LU節點xi和LU節點xj之間帶噪聲的歐幾里得距離為dij，且dij=dji，LU節點xi和LA節點ak之間帶噪聲的歐幾里得距離為dik。通常，在特定區域內，一定數量的傳感器節點因受到功率的限制，不一定能夠正常通信，因此，不是所有的傳感器節點之間的歐幾里得距離都可測得的，本文假設可測距的LU節點xi和LU節點xj的節點集合N為(i,j)∈N，可測距的LU節點xi和LA節點ak的節點集合M為(i,k)∈M[2,8]。wij和wik為根據帶噪距離的反比取得的歸一化權重[2,8]。這樣可以將WSN全局定位問題歸結為無約束優化問題[2,8]，可表示為

(1)

2 分布式定位算法

基于第1節定位問題的描述，正常通信的傳感器節點之間是可以獲取距離信息，根據距離信息，可以用無向圖G=(V,E)表示WSN，其中，V(G)為傳感器節點的位置，E(G)為傳感器節點之間的連通性。基于傳感器節點之間的連通性E(G)，將LU節點以及和其相連接的鄰居節點所在的區域看作一個子圖，從而將WSN表示的無向圖劃分成n個部分重疊的子圖，重新建立起可以獨立求解的子圖內定位問題；然后，采用基于交替修正牛頓法的分布式定位算法，對子圖內定位問題進行優化求解和局部融合。接下來，將分別從劃分子圖、子圖內定位問題、子圖內優化求解、算法總結進行詳細描述。

2.1 劃分子圖

通過對式(1)的觀察可知，LU節點位置只與通信半徑R范圍內的鄰居節點和節點之間的距離有關[2]。因此，將LU節點視作中心節點，將與其構成鄰居的節點組成無向圖G的子圖，這樣，有n個LU中心節點則可劃分成n個部分重疊的子圖，這樣做使得WSN的通信量和計算量能得到有效地降低，提高WSN的整體擴展性，使其易適用于較大規模的WSN。如圖1所示，特定區域內隨機分布部分傳感器節點，以LU節點為中心，R為半徑畫一個虛線圓，一個虛線圓則表示一個子圖。

(2)

式(2)中：Gs=(Vs,Es)為第s個子圖，s=1,2,…，n，其中，Vs為第s個子圖Gs內傳感器節點的集合，Es為第s個子圖Gs內傳感器節點之間邊的集合。

圖1 子圖劃分示意圖Fig.1 Schematic diagram of subgraphs division

2.2 子圖內定位問題

基于子圖Gs=(Vs,Es)包含的相關信息，通過最小化鄰居節點之間距離誤差的加權和[2,8]，將式(1)重新構建為一個無約束的子圖內定位優化問題，可表示為

(3)

式(3)中：xsi為第s個子圖內第i個LU節點位置，xsi=[xsi,ysi]T；xsj為第s個子圖內第j個LU節點位置，xsj=[xsj,ysj]T；通常對流層誤差、電離層誤差、衛星鐘差等誤差容易影響錨節點位置[14]，因此，獲取的錨節點位置很有可能是帶噪聲的，且不準確的，其帶噪聲模型如式(4)所示[1]，psk為第s個子圖內第k個LA節點位置，psk=[xsk,ysk]T；Ns為第s個子圖內可測距的LU節點xsi和LU節點xsj的節點集合；Ms為第s個子圖內可測距的LU節點xsi和LA節點psk的節點集合；dsisj為子圖內LU節點xsi和LU節點xsj之間帶噪聲的歐幾里得距離；dsisk為子圖內LU節點xsi和LA節點psk之間帶噪聲的歐幾里得距離，其帶噪聲模型分別如式(5)、式(6)所示；wsisj和wsisk為子圖內基于傳感器節點之間帶噪距離的反比取得的歸一化權重[2]，其權重值可根據RSS測距技術特點得到，測距時，兩個節點距離相距越遠，噪聲就越容易干擾到無線信號，得到的數據可信度越低，賦予的權重值越小，反之權重值越大[2,8]，wsisj和wsisk分別如式(7)、式(8)所示。

dsisj=‖xsi-xsj‖2|1+τ1εsisj|

(4)

dsisk=‖xsi-psk‖2|1+τ1εsisk|

(5)

psk=ask|1+τ2εsk|

(6)

(7)

(8)

式中：ask為錨節點真實位置；τ1∈[0,1]為錨節點位置噪聲因子，作用是控制錨節點位置的噪聲強度；τ2∈[0,1]為距離噪聲因子，作用是控制測距之間的噪聲強度；εsisj、εsisk和εsk為隨機噪聲，服從正態的隨機變量N(0,1)。

(9)

(10)

式中：

A=(ei1-ej1)(ei1-ej1)T+(ei2-ej2)(ei2-ej2)T

(11)

(12)

(13)

(14)

(15)

則目標函數式(3)可以表示為

(16)

2.3 子圖內優化求解

當WSN中存在錨節點位置誤差時，LU節點基于不準確的錨位置和測距信息，采用協作定位算法定位出來的LU節點位置會估計誤差較大。采用基于交替修正牛頓法的分布式傳感器定位算法，確保當WSN存在錨節點位置誤差時，能夠更高精度地完成定位問題。基于交替修正牛頓法的分布式傳感器定位算法包括：子圖內估計LU節點、子圖內更新LA節點、子圖內融合。

2.3.1 估計LU節點

由式(16)可知，歸結出來的子圖內定位問題是關于LU節點位置xs和LA節點位置ps的高度非線性非凸的函數，因此，直接求解會比較比較困難。對此，因三邊定位算法易于實現和維護，已被廣泛應用于傳感器定位領域[2,15-16]，采用三邊定位算法得到一個初始值，以便可以快速地得到目標函數的局部最優解。然后，對于子圖內定位問題，采用基于單位步長的交替修正牛頓法進行優化求解。

首先，在迭代優化之前，對式(16)進行一階求導首先，對式(16)一階和二階求導，可得?f(xs)和?2f(xs)的表達式分別為

(17)

(18)

式中：Hessian矩陣?2f(xs)不一定是正定的，無法保證算法中的牛頓方向為下降方向，算法可能會失敗，解決Hessian矩陣?2f(xs)非正定基本思想是：構建正定的?2f(xs)，可表示為

DTps)(2Bxs-Cps-DTps)T]

[1]Laufer,B.&P.,Nation.(1999).A Vocabulary Size Test of Controlled Productive Ability,Language Testing,16(1).33-51.

(19)

從而能使用凸優化的求解方法進行優化求解，采用單位步長的修正牛頓算法估計LU節點。

算法1子圖內估計LU節點

輸入：xs0。

輸出：xsi+1。

步驟1使用三邊定位算法得到粗略的初始值xs0，設置i=0，表示第i次迭代，ω=1，步長ω為單位步長，迭代終止條件δ=1×10-9。

步驟2求目標函數式(16)的梯度向量?f(xsi)和修正后的Hessian矩陣?2f(xsi)。

步驟3計算搜索方向gsi=-?2f(xsi)-1×?f(xsi)。

步驟4沿著搜索方向gsi進行一維線性搜索，則xsi+1=xsi+ωgsi，不斷更新子圖內LU節點位置。

當WSN存在錨節點位置誤差時，第2.3.1節子圖內LU節點根據不準確的LA節點位置和測距信息，估計出來的LU節點坐標值存在較大的偏差。因此，將設計位置不準確的LA節點根據LU節點初步估計值和測距信息更新其位置，使得LA節點位置誤差逐漸減小，從而得到相對準確的LA節點位置。這樣，第2.3.1節LU節點再根據相對準確的LA節點位置和測距信息進行估計時，可以減小估計偏差。

首先，對式(16)先進行一階求導，可得?f(ps)的表達式為

(20)

然后，再進行二階求導，可得?2f(ps)的表達式為

(21)

(22)

然后，同2.3.1節一樣采用基于單位步長的修正牛頓法迭代更新LA節點。

算法2子圖內更新LA節點。

輸入：ps0。

輸出：psk+1。

步驟1根據2.3.1節優化求解的LU節點估計值，采用三邊定位算法，粗略得到LA節點的估計值ps0，設k=0,表示第k次迭代，α=1,步長α為單位步長，迭代終止條件η=1×10-9。

步驟2求目標函數式(16)的?f(psk)和修正后的?2f(psk)。

步驟3計算搜索方向dsk=-?2f(psk)-1×?f(psk)。

步驟4沿著搜索方向更新子圖內LA節點位置，psk+1=psk+αdsk。

2.3.3 子圖融合

劃分子圖時，將WSN表示的無向圖G=(V,E)，以LU為中心劃分成n個部分重疊的子圖Gs=(Vs,Es)，s=1,2,…,n。如圖1所示，各個子圖內在獨立優化求解節點位置時，不同子圖內，同一個節點被估計出來的位置都是不相同的，這將導致某個子圖內信息利用較少，也導致優化求解的節點位置誤差較大。為了有效地降低這部分誤差，促進子圖之間的協作定位，提高整體定位精度，采用融合求平均的方式，對該節點在不同子圖內的節點位置求平均，即

(23)

(24)

2.4 分布式算法總結

當WSN中存在錨節點位置誤差時，所提的分布式定位算法中，首先，將LU節點視為中心節點，以及其鄰居節點所在的區域為子圖，將全局的定位問題重新構建為多個子圖內定位問題。一方面，對于子圖內定位問題的求解，采取交替修正牛頓法進行優化求解，通過不斷地交替估計LU節點位置和更新LA節點位置，使得LA節點位置誤差逐漸地減小，進而可以有效地降低LU節點位置估計誤差。在算法迭代開始之前，采用易于維護和實現的三邊定位算法得到LU節點初始位置，目的是確保估計節點位置時能不斷地接近局部最優解，確保搜索方向是沿著子圖內目標函數的下降方向，并使得子圖內目標函數能夠盡快地收斂。另一方面，同一個節點會被包含在多個子圖內，會優化求解得到不同的估計位置，因此，對部分重疊子圖內的節點采用融合求平均的方式，在一定程度上，對子圖內定位誤差較大的節點進行修正，使其獲得一個較好的初始值參與下一步的迭代?？傊ㄟ^不斷地重復對子圖內節點優化求解和融合求平均這兩個步驟，可以有效地利用子圖之間協作定位的特點，確保當WSN存在錨節點位置誤差時，能夠更高精度的完成定位任務。

綜上所述，WSN存在錨節點位置誤差的情況下，基于交替修正牛頓法的分布式定位算法如下。

步驟1將n個LU節點，m個LA節點隨機部署在[-0.5,0.5]2的單位正方形區域內，通信半徑設為R，把WSN以LU節點為中心劃分n個部分重疊的子圖，n個子圖內分別可以進行分布式運算。令t=0，終止條件β=1×10-2。

3 實驗結果及分析

為了表明本文算法的定位性能，給出了4個仿真實驗。使用軟件MATLAB 2017b來仿真實驗，并運行在Intel i7-7700主頻3.6 GHz的PC。為表明算法的魯棒性，所有的仿真實驗都是5次取平均，定位區域均為[-0.5,0.5]2。為了客觀真實地評估所提的分布式定位算法的性能，采用與文獻[8,12,15]的評價指標，即根均方距離(root mean square distance, RMSD)，其表達式為

(25)

圖2 不同LA節點數目下各算法的平均RMSDFig.2 The average RMSD of each algorithm under different number of LA nodes

3.1 實驗1

為了研究WSN存在錨節點位置誤差時，錨節點數目在WSN中所占比例對定位精度的影響，本文算法與文獻[1,11-12]中的分布式定位算法做對比實驗。本次實驗中，設置節點總數N=200，錨節點位置噪聲因子τ1=0.10，距離噪聲因子τ2=0.10，WSN中通信半徑R=0.30，將WSN中錨節點所占比例p從0.10增加到0.30。實驗結果如圖2所示，可以看出，隨著WSN中錨節點數目所占比例p的增加，本文算法和文獻[1,11-12]算法的RMSD均在降低，定位精度得到提高。但是與文獻[1,11-12]算法相比，本文算法在不同錨節點所占比例下，RMSD明顯小于對比的三篇文獻所提算法的RMSD，本文算法的定位精度更高。分析其原因是：隨著WSN中的錨節點數目增多，LU節點會獲得更多鄰居的相關信息，從而得到一個更好的初始值參與下一步迭代，使得定位精度得到提高。這意味著：當大規模WSN存在錨節點位置誤差時，本文算法可以使用較少的錨節點數目實現更好的定位效果，有效地降低了WSN的部署成本。

3.2 實驗2

為了研究WSN存在錨節點位置誤差時，WSN中通信半徑R對定位精度的影響，本文算法與文獻[1,11-12]中的分布式定位算法做對比實驗。本次實驗中，設置節點總數N=200，錨節點位置噪聲因子τ1=0.10，距離噪聲因子τ2=0.10，WSN中的錨節點所占比例p=0.15，將WSN中通信半徑R從0.22增加0.30。實驗結果如圖3所示，可以看出，隨著WSN中通信半徑R增加，本文算法和文獻[1,11-12]算法的RMSD均在增大，定位精度均在降低。但是與文獻[1,11-12]算法相比，本文算法的RMSD在不同R下始終保持最小，本文算法的定位精度高于文獻[1，11-12]算法。分析其原因是：隨著通信半徑R增加，WSN的通信量和計算量也會隨之增大，相應的也會影響定位性能。這意味著：當大規模WSN存在錨節點位置誤差時，本文算法可以使用較小通信半徑R實現更好的定位效果，能夠減少傳感器通信時的能量消耗，提升整體WSN的壽命。

3.3 實驗3

為了研究WSN存在錨節點位置誤差時，不同傳感器網絡規模情況下的定位效果，固定WSN中錨節點所占比例p=0.15，錨節點位置噪聲因子τ1=0.10，距離噪聲因子τ2=0.10，本文算法與文獻[1,11-12]算法在改變總節點數目N，通信半徑R下進行仿真實驗，仿真參數具體設置和實驗結果如表1所示。分析可知：隨著WSN中總節點數目N不斷地增大，在相同的仿真參數下，本文算法與文獻[1,11-12]算法相比較，本文算法的RMSD更小，定位精度更高，進而定位性能更好。這表明當大規模WSN存在錨節點位置誤差時，本文算法具有較好的擴展性，能夠有效地應用于較大規模的WSN，并且具有較高的定位精度。

圖3 不同通信半徑下各算法的平均RMSDFig.3 The average RMSD of each algorithm under different communication radius

表1 各定位算法5次仿真所得的定位結果Table 1 The localization results obtained from 5 simulations of each localization algorithm

圖4 不同算法在隨機拓撲中的結果Fig.4 The results of different algorithms in random topology

3.4 實驗4

為了研究節點分布的方式以及僅存在錨節點位置誤差時對定位精度的影響。仿真參數設置如下：定位區域為[-0.5,0.5]2，節點數目N=100，錨節點所占比例p=0.15，錨節點位置噪聲因子τ1=0.10，通信半徑R=0.40，并將實驗結果可視化。本次實驗與文獻[1,11]算法相比較，仿真結果如圖4、圖5所示，圖4展示的是傳感器節點隨機分布在指定區域，圖5展示的是傳感器節點分布在C型拓撲中。從實驗結果可以看出，在不同的分布形式，相同的仿真參數下，本文算法相比較文獻[1,11]算法，對分布區域的邊界節點展現較好的定位效果，RMSD都比較低，有較高的定位精度。這表明當WSN存在錨節點位置誤差時，本文算法能在不同分布式形式下展現較好的定位效果。

圖5 不同算法在C型拓撲中的結果Fig.5 The results of different algorithms in type C topology

4 結論

為了克服錨節點位置誤差影響定位精度這一問題，提出一種基于交替修正牛頓法的分布式定位算法。首先，將WSN劃分為多個部分重疊的子圖，建立可以獨立求解得到子圖內優化問題。然后，通過本文算法對子圖內定位問題進行優化求解。仿真實驗表明，本文算法在WSN存在錨節點位置誤差的情況下，能對較大規模WSN實現精確定位，可見本文算法具備一定的優勢，可以為無線傳感器網絡在環境科學、水下定位等領域提供技術上的支持。后續工作會在提高定位精度的同時，考慮異步的分布式算法。