一種自適應的分布式目標定位算法

馮燕 徐琨

摘要：在基于無線傳感網絡的分布式定位中，由于網絡中的傳感節點計算能力有限，會導致出現無法求解出最優解的問題。針對這個問題，該文提出了一種動態調整步長的分布式目標定位算法，提出算法在每次迭代求解過程中都動態調整步長大小，并考慮不同距離下錨節點的可靠性問題，利用目標對象前一次得到的位置估算值和相應的梯度值，求出目標對象在當前步的位置信息。采用實測數據對提出算法進行驗證，結果顯示和已有的經典分布式定位算法相比，提出算法能降低定位誤差，獲得較高的定位精度。

關鍵詞：無線傳感網絡；分布式；優化；目標定位

中圖分類號：TP393? ? ? 文獻標識碼：A

文章編號：1009-3044（2022）27-0001-04

開放科學（資源服務）標識碼（OSID）：

1 概述

無線傳感網絡[1]（Wireless Sensor Networks， WSN）是物聯網[2]（Internet of Thing， IoT）系統的骨干網絡，具有易于部署、自組網絡、多跳通信和協同感知等優點，使其被廣泛地應用于醫療健康[3]、環境監控[4]、智能家居[5]和目標追蹤[6]等各個領域。近十幾年以來，國內外的企業、研究機構和學者開展了大量基于WSN網絡的研究，在網絡拓撲結構、目標定位與軌跡追蹤、網絡路由和協同感知等領域取得了大量的研究成果，推動了WSN網絡在實際應用中的快速發展。目標定位是WSN網絡的關鍵基礎技術，是實現網絡高階應用的重要支撐基礎，得到了研究機構的大量關注，是WSN領域的研究熱點。

在WSN網絡中，遍布監測區域的微型WSN傳感節點能夠感知到周圍環境中的各種信息，通過無線網絡將采集到的信息傳送到服務器或云平臺，其中，位置信息是最重要的基礎數據，是確保網絡功能準確實施和應用的關鍵，沒有位置信息的數據是沒有任何意義的。集中式定位[7]和分布式定位[8]是應用于WSN網絡目標定位的兩種重要類別。在WSN網絡發展的早期階段，由于硬件設備的限制，網絡中的終端節點由于芯片處理能力較低，常在網絡中部署一個或多個中心節點實現節點自身和目標的定位，網絡中的終端節點將采集到的信息以多跳路由的方式傳送給網關節點，由網關節點集中處理后再發回控制指令和信息給終端節點[9]。集中式定位方法能夠高效地實現對網絡終端節點的自定位和網絡目標的定位，但是也存在很大的缺陷，WSN網絡不同于傳統網絡，終端節點多、網絡冗余度大、能耗低和帶寬有限是其最大的特點，所有的終端節點都將數據傳輸到網關節點統一處理，會給WSN網絡帶來非常大的通信開銷，造成很大的能耗，降低網絡的生存周期，當多個終端節點同時向網絡節點傳輸信息時，由于是采用多條路由的傳輸方式，會在網關節點附近出現網絡堵塞，導致發生丟包的問題[10]。近幾年來，芯片技術和無線傳輸技術的飛速發展，在功耗和成本沒有明顯增加的情況下，傳感節點的處理能力越來越強，分布式的定位方式能夠將信息在終端進行自主處理，無須將終端節點采集到的信息集中在網關節點統一處理，而且分布式處理方式能夠降低網絡的通信開銷，平衡網絡負載均衡，提高網絡的生存周期，被越來越多的企業和研究機構所青睞。

在分布式定位中，網絡中的傳感節點能夠通過接收周圍節點或目標的信息，自主進行定位，但是WSN網絡中的傳感節點計算能力有限，會出現無法求解出最優解的問題。針對這個問題，本文提出了一種動態調整步長的分布式目標定位算法，提出算法考慮不同距離下錨節點的009657可靠性問題，每輪迭代過程中都動態推導步長大小，根據目標對象前一位置的加權平均值和對應的梯度值，迭代優化出目標對象當次的位置，每次求出的位置估算值都將廣播給下一個鄰居節點。根據實測數據對提出算法進行驗證，結果表明相比于其他傳統的分布式定位算法，提出算法具有更優的定位性能。

2 網絡模型

在一個室內環境中部署由N個傳感節點和M個目標對象組成的WSN網絡，其中，N個傳感節點被隨機地部署在室內環境中，[Pi=pi，qi]，其位置已知，這些傳感節點會周期性地向周圍區域發送包含自身位置信息的無線信號，也會接收來自鄰近傳感節點或目標對象的無線信號，一般將其稱為錨節點。M個目標對象也隨機分布在室內環境中，其位置未知，[Xi=xi，yi]，需要利用位置已知的錨節點估算出目標對象的位置。目標對象能接收通信范圍內錨節點廣播的信標報文，報文中包含錨節點的位置信息和信號強度，傳感節點廣播的信標報文如圖1所示。

信號強度在空氣中傳輸時，會隨著距離的增大逐漸衰減，錨節點和目標對象之間的距離與信號強度之間存在映射關系。目標對象能夠根據接收到的多個錨節點的位置信息和接收信號強度估算自己的位置，目標對象s接收到的第i個錨節點的接收信號強度為Ri，[s=x，y]，根據對數-正態衰減模型可以將其表示為：

[Ri=R0-10?np?log10did0+Ωi]? ? ?（1）

其中，Ri表示目標對象s收到的第i個錨節點的接收信號強度值，單位為dBm；R0表示目標對象s和錨節點距離為1m時的參考接收信號強度值；[di=s-Pi]表示目標對象s和第i個錨節點之間的歐氏距離；d0表示目標對象s和參考節點之間的歐氏距離，通常設為1m；np表示路徑衰減因子，它是一個隨監測環境變化的變量，一般在室內環境中取值在2～6之間；[Ωi]表示無線信號傳輸時的遮蔽效應，它是一個服從對數正態分布的高斯變量。

式（1）描述了接收信號強度Ri和距離di之間的映射關系，可以采用最大似然估計算法對其進行求解。[Ωi]服從對數正態分布，則求解出來的目標對象s的位置坐標[s=x，y]是其真實坐標的概率密度函數為：

[Px=xT，y=yT=12πσNexpi=1Ns-Pi-di2] （2）

其中，[xT，yT]表示目標對象s在網絡中的真實坐標，用最大似然估計算法對式（2）進行求解，目標位置[s=x，y]的最大似然估計量為：

[s=argmaxx，yPx=xT，y=yT]? ? ? ? ? ? ? ? ?（3）

在WSN網絡中，離目標對象s較近的錨節點由于相隔距離比較短，廣播的信標報文會比距離較遠的錨節點具有更高的可靠性，進而在求解目標對象s的位置坐標時能提供更多的價值。因此在求解式（3）描述的定位問題時，需要考慮錨節點和目標對象s之間的距離，距離越近的錨節點可靠性越高。將式（2）中的具體項代入式（3），考慮不同距離下錨節點的可靠性問題，式（3）可以被進一步表示為：

[s=argmaxx，ywi?i=1Ns-Pi-di2]? ? ?（4）

其中，[wi]是一個加權系數，表示錨節點對目標對象的可靠程度，離目標對象較近的錨節點的[wi]值較大，通過這個加權系統可以突出在定位過程中占重要位置的錨節點，提供對目標對象的定位精度。

令[fs=wi?i=1Ns-Pi-di2]，將式（4）進一步簡化為：

[s=argmaxx，yfs]? ? ? ? ? ? ? ? ? ? ?（5）

式（5）中存在非線性項[s-Pi]，采用最大似然算法求解最優值是一件非常困難的事情，而且計算復雜度非常高。針對式（5）中存在非線性項的問題，結合WSN網絡低能耗和有限處理能力的特點，將采用分布式的迭代優化算法進行求解。

3 基于動態步長的分布式定位算法

在對網絡中的目標對象進行定位時，由于存在[s-Pi]這一非線性項，直接對其處理是非常困難的，因此需要對式（5）中包含的[s-Pi]進行線性化處理，降低計算的復雜度，讓其能夠便利地求出最優解。為了便于迭代優化算法求出最優解，將求最大化的問題等價轉換為求最小化問題，然后將式（5）按照一級泰勒級數展開，可以將其轉換為：

[s=argmin[x，y]i=1Nfis+?fix0?s-s]? ?（6）

其中，[x0=x0，y0]表示泰勒級數展開的初始位置，取值為使[fiΔs+?fix0?s-Δs≥0]的任意點；[?fix0]表示函數[fs]在點[x0]處的梯度值；[s]表示前一階段的目標對象的估算位置。在對式（6）采用迭代方式進行最優值求解時，需要進行多次迭代循環。針對網絡中存在多個目標對象的情況，采用分布式的迭代優化方式對式（6）進行求解。

在對目標對象的坐標[[x，y]]進行迭代時，對于每一步迭代，都需要向梯度[?fi]的反方向對上一次求出的坐標進行更新。當采用分布式方式進行迭代時，每一個目標對象都將經歷m次循環迭代過程，每次迭代，目標對象都要根據接收到的多個錨節點的接收信號強度和位置信息進行迭代計算。目標對象在第k次迭代循環后得到的位置估計值為：

[sk=arg minxk，yki=1kfis+?fix0s-s， k=1，2，…m]? ? （7）

其中，[sk=xk，yk]表示目標對象在第k次迭代后得到的位置估值，經過m次迭代循環后求出目標對象位置的最優值，實現對目標對象的定位。由于非線性項的存在，只能通過最小化[fis+?fix0s-s]的值來求出[xk，yk]的最優解。但是如果存在[xk，yk]，能使[fis+?fix0s-s=0]時，可以得到式（7）的最小值，從而求出[xk，yk]的最優解。

令[fis+?fix0s-s=0]，可以將求解式（7）最優解的問題進行等價變換，其表示形式為：

[?fix0?ss=sk=?fix0?s-fis]? ? ? ? ? ? ? （8）

用第k-1次迭代得到的目標對象的坐標位置[sk-1=xk-1，yk-1]代替式（8）中的[x0]和[s]，經過整理后的表達式為：

[?fisk-1?sk=?fisk-1?sk-1-fisk-1] （9）

其中，[?fisk-1]表示函數[fi]在[sk-1]處的梯度值，式（9）中有兩個參數，分別是[sk-1]和[sk]，[sk-1]表示第k-1個迭代后求出的目標對象的位置估計值，[sk]表示第k個迭代后求出的目標對象的位置估計值。在迭代優化過程中，第k個位置估計值要基于第k-1次迭代后的位置估計值進行估算，經過變換后的式（9）能夠很好地描述第k-1次迭代和第k個迭代之間的轉換關系，其表示形式為：

[sk=sk-1-fisk-1W??fisk-1]? ? ? ? ? ? ? ? ? ?（10）

其中，[?fisk-1]表示函數[fi]在位置[sk-1]處的梯度值；[fisk-1W]表示在第i次迭代時的步長大小，[W=1?fisk-12]表示步長的分母部分。式（10）很好地反映了第k-1次迭代后的估算結果和第k次迭代的估算結果之間的映射關系。根據第k-1次的坐標位置、第k-1次迭代的梯度值和步長值，能夠估算出第k次的目標對象坐標位置。而且從式（10）可以看出，[W]和[fisk-1]都只和第k-1次迭代時的目標對象的估算位置[sk-1]有關，和之前其他的迭代估算結果無關。令[λ=-fisk-1W]，將式（10）進一步表示為：

[sk=sk-1+λ??fisk-1]? ? ? ? ? ? ? ? ? ? ?（11）

式（11）描述了目標對象第k次迭代的估算位置和第k-1次迭代的估算位置之間的關系。其中，[λ]表示每次迭代時的步長，它的值都會根據前一次的迭代結果動態地求出。因此，當目標對象第k-1次迭代后估算出位置為[sk-1]時，利用步長[λ]和梯度[?fisk-1]，可以推導出目標對象第k次迭代后的估算位置[sk]；根據式（11）可以進一步得到，當目標對象第k次迭代后估算出位置為[sk]時，利用步長[λ]和梯度[?fisk]，可以推導出目標對象第k+1次迭代后的估算位置[sk+1]，依此類推。

根據上述的求解過程，基于動態步長的分布式定位算法的實現可以用以下步驟進行描述：

步驟1：定義迭代變量：設置k=1；

步驟2：選擇開始迭代的初始值：設置目標對象的初始位置為[s0=x0，y0]；

步驟3：計算梯度：根據[?fis0]求出對應的梯度值；

步驟4：計算步長：根據[λ=-fis0W]求出步長值；

步驟5：迭代：根據式（11），利用動態步長[λ]估算目標對象在第一次迭代優化中求解的位置估算值[s1=x1，y1]；

步驟6：進行下一次迭代：[sk=sk-1+λ??fisk-1]，k=k+1；

步驟7：開始下一次迭代：跳轉到步驟3重復執行；

步驟8：求出最優解：當k=m時，停止迭代，求出目標對象位置信息的最優解。

4 性能分析

從一個已經部署好WSN網絡的室內辦公區域采集實驗數據，該區域位于一棟辦公大樓的第四層，在一個40*20平方米的區域內部署了28個傳感節點，2個移動機器人作為目標對象，所有傳感節點和目標對象都裝配TI公司的CC2530作為無線收發設備，安裝1/4波長的全向天線，工作在2.4GHz頻段。將所有傳感節點按順時針方向排序，周期性地向目標對象廣播包含自身位置和接收信號強度的信標報文，目標對象接收通訊范圍內傳感節點發送的信標報文，重復執行10000次試驗。

在一臺中央處理器為Intel Core i9-10900k，核心數為8核，主頻2.90GHz，內存64G的計算機上進行所有的驗證實驗，根據在上述辦公環境中得到的實測數據，R0表示目標對象s和錨節點距離為1m時的參考接收信號強度值R0=32.57dBm；參考距離d0定義為1m；路徑衰減因子[np]在2～6之間隨機取值。

將提出算法和期望最大算法（Expectation Maximization， EM）、加權增量次梯度（Weighted Incremental Subgradient， WIG）等分布式定位算法進行比較。將所有算法的初始坐標都設為[s0=1，1]，設置加權增量次梯度算法的步長為0.08，提出算法的步長動態生成。為了驗證算法的性能，采用均方根定位誤差[MMSE=1mi=1m（x-xT）2+（y-yT）2]作為評判標準。

不同分布式定位算法的誤差累計分布函數如圖2所示，從圖中可以看出，提出算法定位性能要明顯優于期望最大算法和加權增量次梯度算法。期望最大算法的定位性能最差，90%的定位誤差在3.3米以內；加權增量次梯度算法有90%的定位誤差在2.7米以內；提出算法的定位性能最好，90%的定位誤差在2.2米以內。

目標對象定位時，通信范圍內錨節點的數量會對定位性能產生影響，不同錨節點數量下，各種分布式定位算法的定位誤差如圖3所示。從圖中可以看出，當錨節點數量增多時，三種分布式定位算法的定位誤差都逐漸降低，提出算法的定位誤差降低的速度最快，定位性能最優；當錨節點數量增多到一定程度時，三種分布式定位算法誤差降低的程度都逐漸變緩。當錨節點數量相同時，提出算法定位誤差最小，定位性能最優；期望最大算法的定位誤差最大。

不同分布式定位算法迭代次數和均方根誤差的關系如圖4所示，從圖中可以看出，當迭代次數增加時，所有定位算法的定位誤差都得到了顯著降低，其中，期望最大算法的定位性能最差；提出算法的定位誤差降低的程度最高，定位性能明顯優于其他兩個分布式定位算法。

5 結束語

集中式定位和分布式定位是WSN網絡中最常用的兩種定位形式，分布式定位由于無須中心節點，能降低網絡的通信開銷，是目前的研究熱點。針對分布式定位會出現無法求解出最優解的問題，提出了一種動態計算步長的分布式定位算法，該算法考慮錨節點的可靠性問題并將其表示為權重形式，在每次迭代時動態調整步長大小，根據上一步估算出的位置信息，結合步長和梯度值求出當前步的位置信息。將提出算法和期望最大算法、加權增量次梯度算法等分布式定位算法進行比較，結果表明提出算法的定位誤差要明顯低于傳統的兩種分布式定位算法，具有較好的定位性能。

參考文獻：

[1] 劉瑞興，段中興，李博.改進DV-Hop定位算法在鋼構建筑健康監測中的應用[J].儀器儀表學報，2022，43（4）：38-49.

[2] 程杰，董云玲，陳嘉興，等.一種具有連續跳數值的三維DV-Hop改進算法[J].電子學報，2020，48（11）：2122-2130.

[3] 徐莎莎，周芳，李楊劍，等.一種新的傳感器節點分布式定位算法[J].西安電子科技大學學報，2022，49（2）：89-96，172.

[4] 蔣俊正，趙海兵.基于超級節點的分布式傳感器節點定位算法[J].控制與決策，2020，35（12）：2898-2906.

[5] 余修武，周利興，余齊豪，等.基于剛分簇與雞群優化的深井無線傳感網絡定位算法[J].西南交通大學學報，2019，54（4）：870-878.

[6] 劉宏，韓亞波，張時斌，等.基于自適應罰函數優化粒子群的WSN定位算法[J].傳感技術學報，2018，31（8）：1253-1257，1265.

[7] 王芳.射頻RSS聚類與多傳感器融合的室內定位算法[J].計算機工程與設計，2018，39（6）：1553-1558，1585.

[8] 汪晗，成昂軒，王坤，等.無線傳感器網絡分布式迭代定位誤差控制算法[J].電子與信息學報，2018，40（1）：72-78.

[9] 陳為業，劉廣怡，沈智翔，等.基于數據融合的輻射源目標定位EM算法研究[J].信息工程大學學報，2021，22（4）：399-404.

[10] 單好民，陳才學.基于RSSI高斯濾波的人工蜂群定位算法[J].傳感技術學報，2021，34（7）：979-983.

【通聯編輯：謝媛媛】