劉巍 楊美 阮蕓星 蔡霞

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

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

中圖分類號：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 引言

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

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

1 相關技術介紹

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

⑴

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

AX=b ⑵

其中：

⑶

因此盲節(jié)點的位置坐標為：

⑷

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

2 算法介紹

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

⑴ 解空間的描述

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

⑵ 粒子群算法的迭代方案

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

⑶ 適應度

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

⑸

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

⑹

3 實驗

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

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

⑺

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

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

⑴ 錨節(jié)點比例與定位準確性的關系

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

⑵ 節(jié)點數量與定位準確性的關系

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

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

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

4 結論

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

參考文獻（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] 曹欲曉，嚴奎，徐金寶.一種最優(yōu)錨節(jié)點集合上的兩重粒子群優(yōu)化DV-Hop定位算法[J].傳感技術學報，2015.28（3）：424-429

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

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

[5] 任克強，李亞杰.WSN中DV-Hop節(jié)點定位算法的改進[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