基于鄰居協助的無線傳感器網絡定位算法

劉巍 楊美 阮蕓星 蔡霞

摘? 要： 在無線傳感器網絡定位中，所有的節點都可以測量彼此之間的距離。由于這些測量值存在誤差，在計算節點位置時需要選擇合適的測量距離。首先將節點測量信息構成有向圖，然后獲取從錨節點到盲節點的拓撲順序，最后利用最小二乘法計算盲節點的位置。在挑選有向邊時采用粒子群算法，以盲節點的估計位置的聯合概率為適應度函數來評價盲節點的估計位置的準確性，從而挑選最優測量值作為節點位置。相比采用距離無關的智能定位算法，本算法的定位準確度更高。

關鍵詞： 鄰居協助; 無線傳感器網絡; 節點定位; 聯合概率

中圖分類號：TP212.9? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2020）04-18-03

Neighbor-assisted localization algorithm for wireless sensor networks

Liu Wei， Yang Mei， Ruan Yunxing， Cai Xia

（School of Computer Science， Central China Normal University， Wuhan， Hubei 430079， China）

Abstract： In wireless sensor network localization， all nodes can measure the distance between each other. Due to the errors of these measurements， it is necessary to select the appropriate measurement distances when calculating the nodes' position. The proposed method is to construct a digraph by measuring distances firstly; then to obtain the topological order from anchor node to blind node; finally， the locations of blind nodes are calculated by least square method. When selecting the directed edge， particle swarm optimization algorithm is used to evaluate the accuracy of the estimated position of the blind nodes with the joint probability of the estimated positions of the blind nodes as the fitness function. Thus， the optimal measurement value is selected as the node location. Compared with the range-free localization intelligent algorithm， this algorithm has higher accuracy.

Key words： neighbor-assisted; wireless sensor networks; node location; joint probability

0 引言

節點定位是無線傳感器網絡中的支撐技術。大多數基于無線傳感器網絡的應用，例如運輸、救援、跟蹤、環境監測等，都需要在已知節點位置的基礎上實現。

目前的定位算法主要包括基于距離的定位、距離無關的定位方法?；诰嚯x的定位算法包括：極大似然估計算法[1]、智能優化定位算法[2-4]等利用節點之間的距離計算未知節點的位置。距離無關的定位算法[5]利用節點之間的鄰接關系，通過平均跳距，計算節點的位置。這些算法通過計算錨節點和盲節點之間的距離對盲節點定位，如圖1（a）中所示。但是這些算法往往忽略了大量的盲節點所獲取的距離信息，如圖1（b）中虛線所示。這些測量距離描述了節點和鄰居之間的相對位置信息。本文通過粒子群算法選擇部分測量數據作為極大似然估計定位算法的依據，再利用全部測量距離評估位置未知的節點位置，從中選擇最優節點定位結果。

1 相關技術介紹

在實際測量中，不可避免存在測量誤差。極大似然估計的方法是在已知n個錨節點的位置和它們測量的n個距離信息的基礎上，通過最小二乘法，計算未知盲節點的位置坐標。記n個錨節點的位置坐標為（x1，y1）……（xn，yn），盲節點的位置為（x，y），錨節點到未知節點的測量距離為d1，……dn。對定位問題建模，可以獲得式⑴所示的方程組。

⑴

對式⑴，從第1個方程開始依此減去最后一個方程可以得到式⑵所示的線性方程：

AX=b ⑵

其中：

⑶

因此盲節點的位置坐標為：

⑷

利用極大似然估計算法對節點定位時，錨節點越多，節點定位越準確。但是當錨節點共線或者幾乎共線的時候，細微的誤差都會帶來較大的誤差[6]。因此挑選合適的錨節點和合適的測量距離，對于計算節點的位置非常重要。

2 算法介紹

本文采用粒子群優化算法從測量距離集合中挑選最優測量距離，然后通過極大似然估計定位算法，從錨節點開始依次計算所有盲節點的位置。

⑴ 解空間的描述

記G=（V，D）為無線傳感器網絡的有向圖，其中V是節點集合，包含全部錨節點和盲節點;D是有向邊的集合D={di，j}，代表節點i到節點j的測量距離。從集合D中挑選合適的邊計算盲節點的位置的問題，本質上是0-1背包問題。因此將所有節點的測量距離依次排列，構成列向量作為解向量，當Si，k=1時，表示第i條有向邊選中成為有向圖中的有向邊，當si=0時，表示沒有選中第i邊。

⑵ 粒子群算法的迭代方案

對于解向量Sk，所有挑選的有向邊可以構成有向圖Gk=（V，Dk），判斷有向圖是否是有向無環圖。當有向圖為有向無環圖時，利用從錨節點到所有盲節點的拓撲順序可以依次計算所有盲節點的位置坐標。

⑶ 適應度

記單個盲節點i的估計坐標，它與它所有的鄰居節點的估計距離為，實測距離為D={di，j}，其中j=1：ni。用聯合概率評估節點i的估計坐標的準確性，如式⑸。

⑸

因此，所有盲節點的位置的聯合概率為式⑹：

⑹

3 實驗

為了驗證算法的有效性， 本文采用MATLAB進行仿真。和DV-HOP[7]，PSO-DV-HOP[8]算法進行對比。實驗環境是在邊長為100 m的正方形區域，隨機分布100個傳感器節點， 其中包含錨節點。本文所用算法的種群規模為60， 最大迭代次數均為100， 通信半徑為30m，傳感器的測量方差為0.1m。

標記第i個盲節點的實際位置為（xi，yi），估計位置為，本文采用歸一化誤差作為衡量標準，公式如下：

⑺

其中，un為盲節點的個數，R為傳感器節點的通信半徑，K為實驗重復的次數，實驗中K=100。

本文分別調整錨節點比例、節點數量、通信半徑進行比較分析。仿真結果如圖2所示。實驗顯示，錨節點比例越高、節點數量越多、通信半徑越大，節點的歸一化的測量誤差越小。

⑴ 錨節點比例與定位準確性的關系

調節錨節點占總節點的比例，進行仿真，結果如圖2（a）所示，本算法在錨節點的比例大于25%時趨于穩定，歸一化誤差明顯優于DV_HOP和BPSO_DV_HOP算法，此時歸一化誤差只有BPSO_DV_HOP算法的3%。

⑵ 節點數量與定位準確性的關系

調節總節點數目，進行仿真，結果如圖2（b）所示，本算法在總節點數目大于100個時，歸一化誤差明顯優于DV_HOP和BPSO_DV_HOP算法，在總節點數目為150個時趨于穩定，節點的歸一化誤差只有BPSO_DV_HOP算法的1.6%。

⑶ 通信半徑與定位準確性的關系

調節節點通信半徑，進行仿真，結果如圖2（c）所示，本算法在通信半徑大于30m時，歸一化誤差明顯優于DV_HOP和BPSO_DV_HOP算法。當通信半徑為35m時，算法趨于穩定，節點的歸一化誤差只有BPSO_DV_HOP算法的1.4%。

4 結論

在傳感器網絡中鄰居節點之間可以相互感知距離，這有助于節點的定位。因此本文利用粒子群優化算法，鄰居協助優化定位，獲得最優節點位置坐標。結果顯示，相比于傳統的僅利用基于錨節點的測量信息，而忽略鄰居測距的定位算法，本算法定位精度更高。

參考文獻（References）：

[1] Bhaskar S A. Localization From Connectivity： A 1-bit?Maximum Likelihood Approach[J].IEEE/ACM Transactions on Networking，2015.24（5）：1506-1511

[2] 曹欲曉，嚴奎，徐金寶.一種最優錨節點集合上的兩重粒子群優化DV-Hop定位算法[J].傳感技術學報，2015.28（3）：424-429

[3] 李鵬，陳桂芬，胡文韜.基于雞群算法的無線傳感器網絡定位研究[J].傳感技術學報，2019.32（6）：866-871，891

[4] 段亞青，王華倩，喬學工.基于測距和灰狼優化的無線傳感器網絡定位算法[J].傳感技術學報，2018.31（12）：1894-1899

[5] 任克強，李亞杰.WSN中DV-Hop節點定位算法的改進[J].傳感技術學報，2017.30（4）：611-617

[6] 吳凌飛，孟慶虎，梁華為.一種基于共線度的無線傳感器網絡定位算法[J].傳感技術學報，2009.22（5）：722-727

[7] GuiL， Val T， Wei A， et al. Improvement of range-freelocalization technology by a novel DV-hop protocol in wireless sensor networks[J]. Ad Hoc Networks，2015.24：55-73

[8] 范時平，羅丹，劉艷林.基于跳距與改進粒子群算法的DV-Hop定位算法[J].傳感技術學報，2016.29（9）：1410-1415