基于群体智能改进无线传感器网络定位算法

靳春景，董雪莹

(1.江西理工大学 信息工程学院，江西 赣州 341000; 2.南京邮电大学 光电工程学院，江苏 南京 210023)

基于群体智能改进无线传感器网络定位算法

靳春景1，董雪莹2

(1.江西理工大学 信息工程学院，江西 赣州 341000; 2.南京邮电大学 光电工程学院，江苏 南京 210023)

对经典DV-Hop算法误差比较大的现象进行讨论。对DV-Hop算法进行改进，提出BSADV-Hop算法。该算法分为两大部分，第一部分对跳数计算方法进行改进；第二部分对平均每跳距离进行寻优。在这过程中采用一种群体智能算法——鸟群算法最终降低平均每跳距离导致的误差。仿真实验结果证明，与经典DV-Hop和PSODV-Hop相比，该算法能更准确地计算节点平均跳距，定位精度得以提高，并且体现出较好的稳定性和可行性。

无线传感器网络；DV-Hop定位算法；鸟群算法；平均每跳距

0 引言

无线传感器网络中节点定位算法按不同的标准可分为多种。在WSN中根据测距可将算法分两种：基于测距定位算法和基于非测距定位算法。基于测距的算法需要采用测量途径得到距离信息，其中有以TOA[1]、TDOA以及RSSI为代表的定位技术。基于测距的算法有两点不足之处：(1)测距结果易受环境影响；(2)一般的测距过程中需要增加其他设备，这些设备需要花费额外的能量用于通信。而以Centroid算法、DV-Hop算法[2]为代表的定位算法通常采用连通性定位，对硬件设备没有其他的额外要求，在WSN定位过程花费成本比较低。因此适合在大规模的传感器网络中应用。

1 DV-Hop算法的误差源头

DV-Hop算法可分三个主要步骤[3]。

(1)无线传感器网络中节点最小跳数计算。

(2)锚节点获取自身真实的位置。用公式(1)[4]计算平均每跳距离，信标节点k的平均每跳距离为:

(1)

其中，信标节点k的位置用(xk,yk)表示，第l个信标节点的位置用(xl,yl)表示。hopkl为信标节点k与信标节点l之间的跳数。

待定位节点m接收离自己最近信标节点的平均跳距，并利用步骤(1)得到的距锚节点的跳数来计算距信标节点的长度：

Dmn=hopsize×hopmn

(2)

其中，Dmn是待定位节点m离自身最近信标节点n的距离，hopsize是平均每跳距离的大小，它表示待定位节点m与最靠近它信标节点n平均每跳距离的大小。hopmn为待定节点m到信标节点n的跳数。

(3)通常用最小二乘法来计算待定节点位置。

经典的DV-Hop算法比较容易实现节点位置的计算，并且花费成本相对比较少，但定位精度就差强人意了。这主要是由平均每跳距离有误差造成的。

图1 跳数误差来源示意图

DV-Hop算法中的跳数求解中，经常把在一跳范围内的节点都当做一跳。A节点与B节点都在一跳范围里，所以P节点把到节点A和到节点B的距离都记成一跳。但从图1中，这一跳的距离明显不等，故是误差的源头。

图2 节点距离误差示意图

经典的DV-Hop算法在求解信标节点平均每跳距离时，经常错误地把曲线的距离代替直线的距离进行计算。如图2所示，节点A到节点D的距离d显然不等于d1+d2+d3。这样就对定位精度产生影响。

2 DV-Hop算法的改进

2.1 线性纠正跳数

本节利用电磁场与电磁波理论中一个常见的理论，即信号的强度与信号传播距离成负相关的理论。在无线传感器中加入一个功能模块，利用这个模块计算接收的信号强度。用设定线性的阈值对节点接收的跳数问题进行纠正。具体步骤如下：

(1)设定阈值为S0。

(2)设节点i到节点j的跳数为hopij，节点i接收到节点j的信号强度用Sij表示。

图3 跳数纠正示意图

2.2 鸟群算法的DV-Hop

2.2.1鸟群算法简介

鸟群算法[6]是一种来自大自然的随机搜索群体智能的寻优方法。将鸟群行为特性抽象成如下规则进行描述：

(1) 选择觅食行为或选择保持放哨行为由鸟本身随机决定。

(2) 若选择觅食行为，则该鸟承担起寻找最佳觅食位置并对位置信息进行时刻记录更新，并且还要及时地广播该信息到整个鸟群中。

(3) 若选择不去觅食则保持放哨行为。整个鸟群的每只鸟均试图竞争性地飞向整个鸟群的中间，鸟群的鸟飞往中心的可能性的大小是由自身拥有粮食多少决定的。

(4) 鸟群周期性迁徙。鸟群之间共享食物信息，鸟群中食物生产者具有超高的捕食本领，而乞食者则相反，其捕食本领为最差的。鸟的身份随飞往的区域而改变。

(5) 第一批发现食物的鸟称之为整个鸟群的生产者，乞食者随机选择跟在一个生产者身后祈求食物。随机选择哪一个是由规则(1)决定。当在(0, 1)之间随机生成的随机数大于常数P时，鸟就选择觅食行为，否则保持放哨行为。

规则(2)中每一只鸟进行觅食的行为都是依据自己的经验，该经验可由下式进行模拟：

(3)

对于规则(3)，鸟竞争性飞往种群中央，这种行为用下式表示：

(4)

(5)

N2=a2×

(6)

表达式中，ε是在[1，S]随机取整,规定ε与h不同，其中S是种群数量的多少；a1、a2是[0,2]之间常数；pFith表示第h只鸟适应度值；sumFit代表所有鸟适应度总和。ε为无穷小的常数，其作用保证发生分割。averagek表示种群适应度平均值。

鸟群周期性迁徙可以躲避天敌，增加捕食的机会。假定迁徙的周期为FT，在整个鸟群中利用上述的规则(4)筛选生产者和乞食者。这两种行为特征可利用下式进行表征。

(7)

(8)

式(7)、(8)中rand(0,1)是服从标准正态分布中的随机数；FP为乞食者随机选择跟在一个生产者身后祈求食物事件发生的概率，FP的值为小于1的正数。

本文构建的数学模型采用最小均方误差准则，并且考虑到经典的DV-Hop算法利用最小二乘法计算出来的位置坐标不可避免存在误差，因此利用鸟群算法进行求解。

假定已知节点的实际坐标信息。锚节点n与未知节点m之间的距离可用下式计算：

(9)

本文利用纠正后比较精确的跳数与利用式(1)求得的平均每跳距离相乘即可求得锚节点n与未知节点m之间的距离，即:

将未知节点与最近相邻的信标节点间的真实距离与测量计算得到距离的均方误差设定成目标函数G(x,y)。则目标函数可以写成如下形式：

(10)

其中w是待定位区域中信标节点的数量，用(xm,ym)表示一个待定位的未知节点。而信标节点用(xn,yn)表示。通过上述方法将求待定节点的坐标转化成一个求最优的过程，通过多次的迭代计算从而求得目标函数的最优解，最终求解得精确度高的待定位节点坐标信息。两个坐标节点之间的误差即为定位误差。通过上述过程，本文将鸟群最优化问题转化为求最小值的问题。

2.2.2BSADV-Hop算法流程

鸟群算法中，每一只鸟作为生产者的概率都是由自身的适应度决定的。因此，利用鸟群算法求平均每跳距离的hopesizei，结合鸟群算法中鸟群行为简化的规则，本文算法流程如下：

(1)初始化种群N。在待定位网络中随机进行种群的分布。种群的大小设置为N，对BSA算法相关变量的参数大小进行合理的设置，假设算法的参数做如下设置:C1=C2=1.5,C=S=1,FQ=5。

(2)设置公示板。公示板值的大小设置为 besty。公示板作用是当每次进行迭代时，记载每次的适应度函数的最优值，并广播线性纠正后的跳数。

(3)迭代寻优。利用BSADV-Hop算法进行节点定位，每次迭代定位过程中利用式(10)得到适应度函数G(x,y)的最优值。

(4)计算新种群的适应度值。

(5)判断是否满足终止条件。如果满足终止条件就输出最优解和待定节点的坐标。反之进行迭代次数增1的操作并且回到步骤(3)继续对种群进行优化和迭代计算。

3 算法仿真

本文仿真工具为MATLAB2012a。假设在边长为100 m的正方形区域随机将传感器节点进行抛撒。

本文对节点的定位精度的性能使用平均定位误差Erroravg来评判。Erroravg表示待定位的未知节点的自身真实位置与经BSADV-Hop算法后坐标之间的差值。

评价定位误差公式[7]如下：

本文设定PSODV-Hop[8]的参数为：C1=C2=1.5，惯性因子ωmax=1.2，ωmin=0.1;两种算法的种群大小为200；迭代数为45。进行实验结果的对比分析。

从图4可知，本文BSADV-Hop算法只需经历18次的迭代计算即可获得很高的定位精度，而PSODV-Hop算法要得到相同的定位精度，其迭代的次数是BSADV-Hop的1.5倍。因此可以说本文的BSADV-Hop算法的收敛速度更快。

图4 不同定位算法收敛速度比较

图5中只把节点通信半径作为自变量进行分析比较。由图可知，在这个实验过程中保持节点的总数和锚节点数量不变，算法的定位精度整体上与通信半径成负相关。从图中易看出，在同等的半径时，在节点的定位精度方面BSADV-Hop比PSODV-Hop和传统的DV-Hop算法都高。

图5 不同通信半径的定位误差比较

图6表示，保持待定位区域总的节点数目不变，分别取5，10，15，…，40个锚节点，对算法定位的精度进行分析。从图中易得到，锚节点的个数与算法的定位优劣成正相关。在同等的通信半径下，比较三个算法的定位精度。经典的DV-Hop算法比本文提出的算法定位精度低23%左右。PSODV-Hop算法也比本文的算法低。图中可以得到低6%。本文的算法引入鸟群算法来优化平均每跳距离，这样降低了平均每跳距离引起的误差。并且本文引入的鸟群算法，其最优解搜索能力比较强，这样本文提出算法可以较好地提高节点的定位精度。

图6 不同信标节点数量与定位误差的关系

图7表示在待定位的区域中，随机进行节点的部署。在实验的过程中节点的通信半径和锚节点的数量始终保持不变。本实验过程中只改变节点的数量来进行三个定位算法的精度比较。易从图中得到，在定位精度方面，本文的算法优于PSODV-Hop和经典的DV-Hop算法，并且分别相对于它们提高了8%左右和30%左右。因此，可以得出本文提出的算法，在相同的节点数量条件下定位精度是最优的。

图7 不同节点总数量的误差率比较

4 结论

本文对经典的DV-Hop算法的不完善之处进行了分析讨论，对其缺点进行改进和完善，提出了BSADV-Hop算法。在求优化模型时，采用鸟群算法进行求解，并利用BSADV-Hop算法代替最小二乘法，降低计算误差。通过实验验证，本文的BSADV-Hop算法比 PSODV-Hop算法在最优解搜索能力上表现得更好。在不同的实验条件和不同的变量条件下，分析了BSADV-Hop算法、PSODV-Hop算法和经典的DV-Hop算法的定位精度和定位的开销，得出本文提出的BSADV-Hop算法优于PSODV-Hop算法和经典的DV-Hop算法。

[1] KANG Y, WANG J. A high-precision TOA-based positioning algorithm without the restriction of strict time synchronization for wireless systems[J]. International Conference on Signal Processing. IEEE, 2017,64(2):70-74.

[2] 方旺盛，雷高祥，黄辉. 基于RSSI值跳数修正和跳距加权处理的DV-HOP算法[J]. 江西理工大学学报,2015,36(5):80-84.

[3] MEHRABI M, TAHERI H, TAGHDIRI P. An improved DV-Hop localization algorithm based on evolutionary algorithms[J]. Telecommunication Systems, 2017, 64(3):1-9.

[4] 刘玉珍, 王兆锋. 基于DV-HOP改进的无线传感器网络定位算法[J]. 计算机工程与应用, 2016,52(4):79-83.

[5] 周林, 张厚望. 无线传感器网络中基于DV-Hop节点定位算法的研究[J]. 计算机应用与软件,2015,32(11):92-96.

[6] MENG X B, GAO X Z, LU L, et al. A new bio-inspired optimisation algorithm: Bird swarm algorithm[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2015,25(2):1-5.

[7] 崔坤利, 郎朗, 陈孟元,等. 配电网中基于分簇定位的WSN节点故障定位研究[J]. 传感技术学报, 2017,30(1):146-151.

[8] 李新春, 李苏晨, 王晓明. 基于粒子群优化的DV-Hop定位算法研究[J]. 测控技术, 2017, 36(1):84-87.

Improved localization algorithm for wireless sensor networks based on swarm intelligence

Jin Chunjing1, Dong Xueying2

(1. School of Information Engineering,Jiangxi University of Science and Technology, Ganzhou 341000, China;2. School of Opto-electronics Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210023, China)

In this paper, the error of DV-Hop algorithm is discussed. The DV-Hop algorithm is improved and BSADV-Hop algorithm is proposed. This algorithm is divided into two parts. In the first part, the hop count method is improved. The second part is to optimize the average hop distance. In this process, a biologically inspired algorithm called bird swarm algorithm is used to minimize the error caused by the average hop distance. Simulation results show that compared with DV-Hop and PSODV-Hop, the average hop distance of nodes can be calculated more accurately, and the positioning accuracy can be improved. Moreover, the proposed algorithm shows good stability and feasibility.

WSN; DV-Hop location algorithm; BSA; the average distance per hop

TP393

A

10.19358/j.issn.1674- 7720.2017.23.018

靳春景，董雪莹.基于群体智能改进无线传感器网络定位算法[J].微型机与应用，2017,36(23)：62-65.

2017-06-15)

靳春景(1990-)，通信作者，男，硕士研究生，主要研究方向：无线传感器网络定位。 E-mail:jincj2011@163.com。

董雪莹(1991-)，女，硕士研究生，主要研究方向：无线传感器网络。