基于UAV的无线传感器网络加权质心定位算法*

高美凤，尹持俊

(江南大学轻工过程先进控制教育部重点实验室，江苏 无锡214122)

无线传感器网络(Wireless Sensor Networks，WSN)是由大量传感器节点分布在监控区域组成的网络，具有感知、计算和通信能力[1]。在无线传感器网络应用中，确定了位置信息后的数据信息才会有意义，因此定位问题是无线传感器网络研究的关键问题之一[2]。无人机(Unmanned Aerial Vehicle，UAV)是一种自动驾驶、可重复使用、可操控并可以携带一定设备完成多种任务的航空器[3]。随着无人机的应用逐渐从军事领域扩展到民用领域，无人机的研究备受关注，无人机在WSN领域的应用也应运而生。由于其低成本，不受空间约束和使用灵活的优势，无人机在WSN节点定位也有很好的发展前景[4]。目前，在无线传感器网络节点定位中，根据是否需要测量节点间的距离分为两类:一类是需要测距的定位算法，测距方法有RSSI、TOA、TDOA等，基于此类测距方法的定位算法有极大似然估计法、三边测量法、三角测量法[5]；另一类是不需要测距的定位算法，有质心算法、DV-hop算法、APIT算法等[6]。在无需测距的定位算法中，基于RSSI值的加权质心定位算法(RSSI-Weighted Centroid Localization，R-WCL)直接采用RSSI值作为加权质心定位算法的权值，计算过程较为简单，容易实现[7]。文献[8]提出基于RSSI比值的加权质心定位算法(RSSI-RSSI-Weighted Centroid Localization，RRWCL)，将未知节点接收到的各邻居锚节点的信号强度比值作为每个锚节点的权值，在一定程度上提高了定位精度。文献[9]提出改进的基于RSSI极大似然估计定位算法(Taylor-Maximum Likelihood Estimation，T-MLE)，使用基于泰勒级数展开的最小二乘法求解方程组，改善了基于RSSI极大似然估计定位算法的稳定性，提高了定位精度。文献[10]以极大似然定位算法解得坐标后的误差倒数作为权值的加权质心定位算法(Error-Weighted Centroid Localization，E-WCL)，具有定位精度高等优势。另外在上述算法中，为了达到较好的定位结果，需要在网络内布置大量的锚节点，定位成本较高，限制了算法在无线传感器网络中的应用。文献[11]提出基于单个移动锚节点辅助的加权质心定位算法，该算法采用单个移动锚节点沿着既定的轨迹在监测区域移动，并在规定位置广播数据包，降低了定位成本。但是当移动锚节点无法在未知节点所在平面移动时，利用无人机充当移动锚节点则是一个很好的选择。

针对在监控区域内，移动锚节点无法处于未知节点平面的情况，本文采用无人机作为移动锚节点，以既定的航迹在整个无线传感器网络的监测区域飞行，在降低定位成本的情况下，对加权质心定位算法进行了改进，提出了基于信号强度比值并结合指数函数作为权值的加权质心定位算法(Exponent RSSIRSSI-Weighted Centroid Localization，ERR-WCL)。最后，对T-MLE、RR-WCL、E-WCL和ERR-WCL四种算法进行了仿真对比实验，仿真结果表明本文所提出的ERR-WCL算法利用无人机作为移动锚节点，能有效地降低未知节点的定位误差。

1 基于UAV的无线传感器网络加权质心定位算法

1.1 无人机飞行航迹

无人机在网络内按照一定的时间间隔广播信息包，当未知节点收集到多个航迹点位置信息后，利用定位算法对自身进行位置估计。常用的无人机航迹规划方法有四种，其中Dimitrios提出了Scan、Double Scan、Hilbert三种航迹规划方法[12]，文献[13]提出正三角形航迹，如图1所示。Scan的飞行航迹长度较短，但共线问题较为严重。Double Scan算法很好地解决了Scan算法的共线问题，但是飞行航迹长度相比增加了一倍，而且区域边缘节点的定位精度较低。Hilebert算法很好地解决了上述问题，但其飞行航迹长度比Scan算法多很多。文献[13]分析证明，当三个锚节点对称放置时，可以达到最优部署。也就是为了获得更精确的未知节点位置信息，可以将三个锚节点放置成一个等边三角形。这种正三角形的飞行广播方式，最大程度的保证了监测区域内的未知节点处于至少三个航迹点构成的多边形内部，进而达到较好的定位结果。

图1 四种航迹规划方法示意图

本文根据正三角形航迹思想，采用无人机沿正三角形的飞行航迹遍历整个传感器网络区域，设计了无人机立体正三角形航迹如图2所示(*表示无人机的航迹点，即虚拟锚节点；→表示无人机飞行航迹；o表示未知节点)。

图2 无人机正三角形航迹图

在飞行的过程中，无人机在每个三角形顶点停留一定时间，感知周围邻近的未知节点并广播数据包，接收到数据包的未知节点将该虚拟锚节点标记为邻居虚拟锚节点。无人机广播的数据包需包含有自身移动位置坐标、标号和信号强度。

1.2 改进加权质心定位算法权值

加权质心算法的主要思想是利用锚节点和未知节点之间的接收信号强度指示值作为权值，利用权值来体现锚节点对质心位置的影响程度。加权质心定位算法的计算公式为:

式中:P(x，y)为未知节点估计位置；B i(x，y)为锚节点i的位置坐标；N为未知节点的邻居锚节点数；w i为邻居锚节点i对未知节点的权重值，其通常可以是未知节点和锚节点间距离的函数、或者是未知节点接收到的RSSI的函数。

在无线传感器网络中，环境对未知节点接收到的RSSI值是有一定影响的。文献[8]提出了RRWCL算法采用接收信号强度比值作为加权值，从而抑制环境对未知节点接收到的RSSI值的差异影响。依据文献[8]的思想，本文提出了ERR-WCL算法，该算法在采用信号强度比值作为权值的同时，为了扩大个体信号强度值差异对节点间实际位置坐标的影响程度，结合以e为底的指数函数y＝ex，即自然对数进行修正，扩大个体信号强度值差异影响，对未知节点的估计位置进行修正。显然，当未知节点接收到的虚拟锚节点信号强度越强，则该邻居虚拟锚节点的坐标对未知节点的定位结果影响越大；反之，则影响越小。据此，首先运用权重的概念，定义R ji为未知节点M分别从邻居虚拟锚节点B j、B i接收到的信号强度比值:

式中:i＝1，…，N，j＝1，…，N。当无人机发射功率为0 dBm时，RSSIi为负数，故RSSIi的绝对值越大，则说明未知节点离邻居虚拟锚节点越远。

定义式(1)中邻居锚节点i对未知节点的权重值为

在x>0的情况下，由exp(x)－x恒大于等于1且随x的增大单调递增可知，对于未知节点M的邻居虚拟锚节点B k，k∈[1，N]的权值始终大于从而扩大了不同邻居虚拟锚节点的权值影响程度，使距离较近的邻居虚拟锚节点所占的权重比例更大，估算的质心位置更加趋近于未知节点的实际位置。

1.3 权值变化对未知节点定位坐标的影响分析

当要研究未知节点到某一邻居虚拟锚节点RSSI值变化对该邻居虚拟锚节点权重值的影响时，就要把权值当变量。

定义邻居虚拟锚节点B i(x，y)对最终未知节点定位结果的贡献大小为P i(x，y)，即:

则式(1)则可以表示为:

取权值作为变量，B i(x，y)为邻居虚拟锚节点i的坐标，其为常数可以忽略，将w i代入式(4)中作为变量，即可得:

这里假定未知节点接收到邻居虚拟锚节点k的信号强度值RSSIk增大，其绝对值减小，推导P k(w k)的变化。在式(6)的分母中，将w k单独列出，则:

对式(7)中w k求导可得:

即RSSIk增大，其绝对值减小，增大，增大，而P′k(w k)恒大于零，故可得到P k(w k)增大，P k(w k)相对于P(x，y)所占的比例越大，即邻居虚拟锚节点k对未知节点的估计位置坐标贡献大。反之，邻居虚拟锚节点k对未知节点的估计位置坐标贡献小。

1.4 基于UAV的节点定位

当移动锚节点无法在未知节点所处平面移动时，可以用无人机来代替移动锚节点在监测区域飞行，形成许多航迹点(虚拟锚节点)，以协助未知节点实现定位。若未知节点均在同一高度平面，即处于(x，y，z0)位置，而无人机在另一高度平面飞行，即无人机所处位置为(x，y，z1)，其中z0和z1是已知的。此时，无人机在z1高度飞行过程中，定时发布位置信息，以形成虚拟锚节点，同时考虑未知节点和无人机所处监测区域媒质是各向同性且均匀的，则可以将三维空间的定位问题简化为二维空间的定位。

根据式(1)、式(2)和式(3)求得未知节点的横纵坐标估计值:

式中:

通常用相对平均定位误差来表示定位效果，即节点的定位误差和节点最大传播距离的比值，即

式中:m、n、r分别是虚拟锚节点数量、节点总数量和节点的通信半径，P(x，y)r为未知节点的实际位置的横纵坐标。

1.5 改进的加权质心定位算法步骤

无人机沿正三角形航迹飞行结束后，未知节点根据记录的信号强度值和邻居虚拟锚节点的位置坐标，用改进的加权质心定位算法ERR-WCL计算未知节点自身的位置，具体的算法伪代码如下:

?

2 仿真与分析

2.1 仿真环境设置

以室内环境为例，室内部署的无线传感器网络节点，无法通过GPS(Global Positioning System)等方法进行定位[14]。无人机的位置由即时定位与地图构建(Simultaneous Localization and Mapping，SLAM)获得[15]。为验证本文所提的ERR-WCL算法的有效性，在Window10操作系统下利用MATLAB R2019a进行仿真分析。仿真环境的设置如表1所示。

表1 仿真环境

2.2 通信半径的影响分析

无人机初始的坐标为(0，0，3)，且按图1正三角形航迹飞行，设置节点通信半径r＝5 m。未知节点与通信半径内的邻居虚拟锚节点进行通信，生成邻居关系图如图3所示(*表示无人机的航迹点位置，即虚拟锚节点位置，○表示未知节点位置，－表示将未知节点与邻居虚拟锚节点连接在一起)。

图3 通信半径为5 m的邻居关系图

由图3可以看出，每个未知节点可以接收5或6个邻居虚拟锚节点的位置坐标，且这些位置坐标不都在一条直线上，能够连接成多边形进行定位。

图4 、图5、图6和图7分别是T-MLE、RR-WCL、E-WCL和ERR-WCL算法在通信半径r＝5 m，未知节点同分布的定位结果(○表示未知节点的实际位置，－表示未知节点估计位置与实际位置的偏差)。

图4 T-MLE定位效果图

图5 RR-WCL定位效果图

图6 E-WCL定位效果图

图7 ERR-WCL定位效果图

对比图4、图5、图6和图7，根据未知节点估计位置到其真实位置连线的长短，可以看出:当通信半径为5 m时，ERR-WCL算法的定位误差最小，E-WCL也较小，RR-WCL和T-MLE较大。

相同的仿真环境下，改变节点的通信半径后，节点的相对平均定位误差由式(11)计算得出，如图8所示。

图8 不同通信半径下相对平均定位误差

从图8中可以看出随着通信半径增加，T-MLE的相对平均定位误差在11.26%~15.33%波动；RRWCL的相对平均定位误差在10.22%~12.51%波动；E-WCL的相对平均定位误差在7.63%~11.52%波动；ERR-WCL的相对平均定位误差在6.81%~9.15%波动。ERR-WCL的定位精度较T-MLE算法提高了4.45%~6.18%，较RR-WCL算法提高了3.36%~3.41%，较E-WCL算法提高了0.82%~2.37%。ERR-WCL算法可以得到较小的定位误差，定位效果较好。

同时可以看出，当无人机广播位置不变时，随着节点的通信半径增加，节点的相对平均定位误差逐渐减小。这是由于在一定范围内，节点通信半径的增大会提高网络的连通度，使得未知节点可以接收的无人机的数据包数量增多，其位置也可以越来越趋近于邻居虚拟锚节点位置所构成的多边形中心，从而使得未知节点的相对平均定位误差有所降低。

2.3 UAV高度的影响

无人机仍然按正三角形航迹飞行，且设置通信半径为定值r＝5 m。未知节点与通信半径内的邻居虚拟锚节点进行通信，无人机在不同飞行高度时，生成邻居关系图分别如图9、图10和图11所示(*表示无人机的航迹点位置，即虚拟锚节点位置，○表示未知节点位置，－表示将未知节点与邻居虚拟锚节点连接在一起)。

图9 飞行高度为0.5 m的邻居关系图

图10 飞行高度为1.5 m的邻居关系图

由图9、图10和图11可以看出，通信半径一定时，无人机飞行高度为0.5 m时，未知节点可以接收7~10个邻居虚拟锚节点的位置坐标；飞行高度为1.5 m时，未知节点可以接收6~9个邻居虚拟锚节

图11 飞行高度为2.5 m的邻居关系图

点的位置坐标；飞行高度为2.5 m时，未知节点可以接收6或7个邻居虚拟锚节点的位置坐标。这是由于节点的通信半径固定为5 m，当无人机飞行高度越高，未知节点周围的邻居虚拟锚节点的数目就越少。相同的仿真环境下，改变无人机的飞行高度后，根据式(11)求节点的相对平均定位误差，得到节点的相对平均定位误差如图12所示。

图12 不同飞行高度的相对平均定位误差

从图12中可以看出，随着无人机的飞行高度增加，T-MLE的相对平均定位误差在9.98%~14.37%波动；RR-WCL的相对平均定位误差在9.51%~11.94%波动；E-WCL的相对平均定位误差在7.99%~11.25%波动；ERR-WCL的相对平均定位误差在6.45%~7.95%波动。ERR-WCL的定位精度较T-MLE算法提高了3.53%~6.72%，较RR-WCL算法提高了3.06%~4.01%，较E-WCL算法提高了1.54%~4.30%。ERR-WCL算法可以得到较小的定位误差，定位效果较好。表示无人机可以灵活的在飞行范围内飞行，不受到空间约束，并结合所提ERR-WCL定位算法可以得到较好的定位结果。

同时可以看出，当无人机通信半径不变时，随着无人机飞行高度的增加，节点的相对平均定位误差逐渐增大。这是由于在通信半径一定的情况下，无人机飞行高度越高，使得未知节点可以接收的无人机的数据包数量减少，从而使得未知节点的相对平均定位误差有所增加。

3 结束语

加权质心定位算法对锚节点数量和分布有比较高的要求，本文在不增加硬件资源的前提下，提出ERR-WCL算法。该算法采用无人机以既定的合理航迹飞行在整个监测区域，在充分考虑了不同邻居虚拟锚节点位置对未知节点的影响情况下，利用了未知节点的接收信号强度比值并结合指数函数对未知节点的位置进行估计。仿真实验表明ERR-WCL算法可以得到较小的定位误差，同时使用无人机降低了定位成本并解决了二维移动锚节点受到空间约束，移动不灵活等问题。接下来的工作依据定位结果优化无人机的航迹，对未知节点进行进一步精确定位。