基于邻居协助的无线传感器网络定位算法

刘巍 杨美 阮芸星 蔡霞

摘  要： 在无线传感器网络定位中，所有的节点都可以测量彼此之间的距离。由于这些测量值存在误差，在计算节点位置时需要选择合适的测量距离。首先将节点测量信息构成有向图，然后获取从锚节点到盲节点的拓扑顺序，最后利用最小二乘法计算盲节点的位置。在挑选有向边时采用粒子群算法，以盲节点的估计位置的联合概率为适应度函数来评价盲节点的估计位置的准确性，从而挑选最优测量值作为节点位置。相比采用距离无关的智能定位算法，本算法的定位准确度更高。

关键词： 邻居协助; 无线传感器网络; 节点定位; 联合概率

中图分类号：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 引言

节点定位是无线传感器网络中的支撑技术。大多数基于无线传感器网络的应用，例如运输、救援、跟踪、环境监测等，都需要在已知节点位置的基础上实现。

目前的定位算法主要包括基于距离的定位、距离无关的定位方法。基于距离的定位算法包括：极大似然估计算法[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