一種基于跳距修正的物聯網中節點定位算法

唐一韜，鄧河

(長沙民政職業技術學院 通識教育中心,長沙 410004)

0 引言

隨著智能終端設備的日增以及無線網絡的普及，人們的生活與物聯網關系也日益緊密[1].由微型傳感節點構成的無線傳感網絡 (WSN)是物聯網的基石[2-3].傳感節點先感知環境數據，再通過鄰居節點的轉發，將數據傳輸至控制中心.

節點感知的數據離不開節點的位置.因此，定位是基于WSN 物聯網應用的關鍵.盡管衛星定位系統已被廣泛應用，但將其應用于WSN 的成本高，不適合大規模部署.多數節點只能依據網絡拓撲知識或者節點間的連通信息估計自己的位置信息.

針對WSN 的定位問題，學者已提出不同的定位算法.這些定位算法可粗略分為基于測距定位(Rangbased)和非測距定位(Rang-free)算法兩類[4].不失一般性，測距定位算法的精度優于非測距定位算法的精度.但是非測距定位算法易實施，部署成本低.

因此，非測距定位算法更適用于低功耗、低成本的物聯網.非測距定位算法不是建立在節點間距離值，而是網絡拓撲信息，如質心算法[5]、DV-Hop 算法[6]、近似三角形內點測試(APIT)算法[7].

因避免直接測量節點間距離，DV-Hop 算法成為非測距定位算法的代表.DV-Hop 算法先利用距離矢量路由方法估計錨節點與未知節點間的最小跳數，再結合平均跳距測量錨節點與未知節點間的距離，最后利用三邊測量法估計未知節點位置.

簡之，DV-Hop 算法主要涉及到最小跳數、平均跳距和估計節點位置三個環節.任一個環節的估計或者測量誤差，均會降低估計節點位置的精度.此外，前兩個環節的誤差會累加至估計節點位置的環節.其中最小跳數估計、平均跳距的計算易受網絡拓撲以及通信半徑影響.

針對DV-Hop 算法的定位精度問題，學者已著手對其進行改進.例如張晶等[8]提出基于DV-Hop 算法的三次修正的定位算法.該算法先根據接收信號強度值(RSSI)對跳數進行連續性劃分，再利用平方誤差適應度函數修正跳距值，最后利用泰勒展開式估計節點位置.然而，測量發送端與接收端間RSSI 值容易受環境影響.同一對收發端的RSSI 值也可能存在較大差異.同一個節點接收的多個RSSI 值可能波動較大.因此，利用RSSI 修正跳距效果并不好.

針對DV-Hop 算法的問題，提出基于獅群優化算法的節點定位 (NLLSO) 算法.NLLSO 算法根據DVHop 算法的特點，對其進行有針對性地改進.主要工作如下：1)采用不同通信半徑傳輸Beacon，進而提升估計跳數的精度；2) 修正平均跳距；3)利用獅群優化算法 (LSO) 估計未知節點位置.性能分析表明，NLLSO算法提高了定位精度.

1 網絡模型及LSO 概述

1.1 網絡模型

N個傳感節點隨機分布于二維網絡l×l，其中錨節點占比為p%，未知節點占比為(100-p)%.令αi表示第i個錨節點，其位置坐標為令sj表示第j個未知節點，其位置坐標為如圖1 所示,在100 m×120 m區域內隨機部署N=50 個未知節點.錨節點占比p=10 .

圖1 網絡模型

1.2 LSO 概述

作為智能優化算法，LSO 模擬了自然界中獅群的覓食行為.LSO 中主要涉及三類角色：獅王、母獅和幼獅.它們遵照自然界法則生存，并采用不同的位置更新方式更新自己的位置.相比于母獅和幼獅，獅王的位置更新更快、收斂快、不易陷入局部最優，能夠快速地搜索到全局最優解[9].因此，選擇LSO 估計節點位置.表1 給出LSO 中相關符號的物理意義.

表1 LSO 的相關符號

假定在二維空間中分布了M只獅子，其中成年獅的比例為 β .每個成年獅群中只有一只公獅，余下的成年獅為母獅.幼獅數量為M(1-β) .

2 NLLSO 算法

2.1 基于多通信半徑的最小跳數估計

傳統估計最小跳數的算法將通信半徑內的跳數值都看成一跳[10].例如，若節點1 離節點2 的距離為30 m，節點1 離節點3 的距離為20 m.如果節點1 的通信半徑大于30 m,節點2 和3 節點就在其一跳通信范圍內.依據傳統估計最小跳數估計算法，節點2、3 離節點1 的跳數均為1.當平均跳距為d時，節點1 離節點2、3 的距離均為d，而實際上，節點1 離節點2、3 的距離分別為30 m、20 m.

為此，采用動態的通信半徑.通過調整發射功率，錨節點選擇不同的通信半徑.令R表示默認的節點通信半徑.錨節點采用5 種通信半徑，分別為 0.2R、0.4R、0.6R、0.8R和R.

具體實現過程如下：最初網絡中所有錨節點采用0.2R的通信半徑廣播Beacon 包，Beacon 包攜帶了錨節點位置以及ID 號.在0～ 0.2R傳播范圍內的節點收到Beacon 包，未知節點就獲取離錨節點的最小跳數為0.2 跳.

然后再逐步增加通信半徑(從 0.4R～ 0.6R，再提升到0.8R～R)，相應地，未知節點獲取不同通信半徑下的跳數值.

2.2 跳距的修正

利用離其他錨節點的距離和其他錨節點位置(已知信息)，錨節點修正自己的跳距值.即錨節點 αi先利用式(4)計算平均跳距AHDi

再利用hi j和 AHDi，估計錨節點 αi離 αj的距離(估計距離)

不失一般性，實際距離dij與估計距離間存在誤差，并且該誤差是已知的.因此，可利用該書籍信息修正平均跳距.即通過最小化誤差對平均跳距進行修正

考慮到錨節點間跳數影響了AHDi的值，式(1)所估計 AHDi可能存在誤差.為了降低誤差，引用權值對平均跳距進行約束，進而降低因平均跳距誤差引起的測距誤差.

依式(5)可知，錨節點 αi離 αj的跳數越大，估計距離的誤差越大.因此，將跳數大的兩節點間的權值變小，可降低其對測距的影響.為了求解方便，對式(7)進行矩陣化表述

2.3 位置估計

NLLSO 算法采用獅群優化估計未知節點位置.為此，先設定目標函數

式中，fj(x,y)為求解未知節點sj所建立目標函數.

節點sj建立的適應值函數

具體的基于LSO 求解未知節點位置的步驟如步驟1～6 所示：

步驟1：在二維空間中隨機初始化N個節點位置，并將其作為獅群中獅子的位置，并設置最大迭代次數T和成年獅比例.

步驟2：計算獅群中不同角色獅子數量，獅王位置設置為初始種群最優位置，設置個體歷史最優位置為各獅的當前位置.

步驟3：依據式(1)～(3)更新獅王、母獅和幼獅的位置，并根據式(12)計算適應度值.

步驟4：更新自身和獅群歷史最優位置.檢測兩次最優值的差值的絕對值是否小于預設的精度值.若小于，則跳轉步驟6，否則轉入步驟5.

步驟5：每隔10 次重新排序，確認獅王、母獅和幼獅的位置，再跳轉到步驟3.

步驟6：輸出獅王的位置，即未知節點的位置.

3 性能仿真

3.1 仿真環境

利用MATLAB 2018 a 軟件建立仿真平臺，N個節點隨機分布于100 m×100 m，其中錨節點數比例p%從10%～31%變化.節點的傳輸功率從-5～-15 dBm變化，具體的仿真參數如表2 所示.每次仿真獨立進行20 次，取平均值作為最終定位數據.

表2 仿真參數

為了更好地分析NLLSO 定位算法的性能，選同類算法DV-Hop[11]、基于RSSI 測距修正的四邊形加權質心定位(QWCRC)算法[12]進行比較.并分析它們的歸一化定位誤差

式中：m為未知節點數，即m=N-N×p% ；為節點的平均通信半徑.

3.2 定位誤差隨錨節點數變化情況

先分析定位誤差隨錨節點數的變化情況.圖2 顯示歸一化定位誤差隨錨節點數的變化曲線.總的節點數為150，錨節點數占比從0.1～0.31 變化，通信半徑R=36 m.

圖2 歸一化定位誤差隨錨節點數變化情況

由圖2 可知，在總的節點數一定時，增加錨節點數提升定位精度.但值得注意的是，當錨節點數達到一定量后，定位精度的提升也存在“飽和”現象.這也說明，優化錨節點數也是定位算法須考量的問題之一.

此外，在同等條件下，NLLSO 算法的定位精度優于DV-Hop 算法和QWCRC 算法，且分別提高了相比于DV-Hop 和QWCRC 算法，NLLSO 算法9%和5%.這說明NLLSO 算法通過平均跳距的修正和基于LSO，可以有效地提高平均定位精度.

3.3 定位誤差隨通信半徑變化情況

本小節分析定位誤差隨通信半徑的變化情況.圖3 描述了定位誤差隨通信半徑的變化曲線.總的節點數為150，錨節點數占比為0.2，通信半徑約為21～45 m 變化.

圖3 定位誤差隨通信半徑的變化情況

由圖3 可知，增加通信半徑可提高定位精度.這主要因為節點通信半徑越大，數據傳輸路徑的跳數越小，這有利于降低估計最小跳數和跳距的誤差.更準確的跳數值和跳距有利于提高定位精度.此外，相比于DV-Hop 和QWCRC 算法，NLLSO 算法有效地降低定位誤差，且分別降低約8%和3%.

3.4 定位誤差隨節點數變化情況

最后分析定位誤差隨總節點數的變化情況.圖4描繪了歸一化定位誤差隨總節點數的變化曲線.錨節點數占比為0.2，總節點數從100～200 變化.節點通信半徑為36 m.

圖4 節點數對歸一化定位誤差的影響

由圖4 的曲線走勢可知，增加總節點數降低了定位誤差.最初，增加總節點數能夠快速地降低定位誤差.但當總節點數增加到140 后，定位誤差的下降速度變緩慢，趨于直線.原因在于：最初網絡內節點數的增加，增加測距精度和估計最小跳數的精度.但當網絡內節點數達到一定量后，再增加節點數，就增加了網絡負擔，出現“飽和現象”.此外，相比于DV-Hop 和QWCRC 算法，NLLSO 算法有效地提升了定位精度.

3.5 算法復雜度

在Windows 7 操作系統、8 GB 內存，Core i7 CPU的PC 運行算法，并記錄運算時間.運行50 次，取平均值作為最終的數據，如表3 所示.由表3 可知，DVHop 算法的運行時間最短，NLLSO 算法的運行時間次之，QWCRC 算法的運行時間最長.原因在于：NLLSO 算法利用LSO 估計節點位置，增加了算法的復雜度.結合定位誤差的數據可知，NLLSO 算法能夠在定位誤差與復雜度間達到較好地平衡.

表3 算法的復雜度

4 結束語

NLLSO 算法針對傳統DV-Hop 算法在跳數估計、跳距測量和定位三個環節上的問題進行了一定的改進.通過采用不同通信半徑傳輸Beacon 包，提升估計最小跳數的精度.并引用權重對平均跳距的修正，降低測距誤差.通過LSO 估計節點位置，性能分析表明，相比于傳統DV-Hop 算法 NLLSO 算法降低了定位誤差.

然而，本文僅關注了NLLSO 算法在定位精度方面的優勢，并沒有考慮了多通信半徑過程中所產生開銷.后期，將考慮如何降低節點間的通信量，控制節點能量消耗，這將是后期的工作方向.