无线传感器网络(Wireless Sensor Network，WSN)是由多个节点组成的自组织网络，其优点是成本低、功耗低、对环境适应性强，现在已被广泛应用于战场监视、工业控制、土壤环境监测等多种应用场合中[1-2]。近年来，WSN定位算法成为科研人员研究的热点之一。通常WSN定位算法被分类为距离有关和距离无关的算法[3-4]。信号到达时间(Time of Arrival，TOA)、信号到达时间差(Time Difference of Arrival，TDOA)、信号到达角度(Angle of Arrival，AOA)以及接收信号强度(Received Signal Strength Indicator，RSSI)等都属于距离有关的算法，该类算法需要获得测量距离，并辅以定位算法求出未知点的位置，效果较好[5]。其中，TOA、TDOA和AOA算法的测距结果较准确，但它们需要复杂和昂贵的硬件设备[6]。RSSI算法不需要额外的硬件，但在测距中会受到多径传播、信道衰落的影响，造成测距精度下降[7]。DV-Hop、APIT和MDS-MAP等算法则属于距离无关的算法，它们的定位精度较低[8]。
DV-Hop算法的复杂性低、成本低，使得其在WSN定位中的应用较为广泛，许多改进的DV-Hop算法被提出：文献[9]提出了一种基于三角不等式的加权双曲线DV-Hop定位算法，利用三角不等式约束节点间的跳距，以减小误差；文献[10]提出一种改进的DV-Hop定位算法，利用加权的方式计算较优平均跳距，并将已定位的节点当作新的锚节点进行其余未知节点的定位；文献[11]提出一种基于最优辅助距离估计锚节点的DV-Hop定位算法，根据不同的估距类型计算节点间的估计距离，并将加权因子的概念引入到三边定位法中，以提高定位精度；文献[12]提出一种加权距离估计方法，通过对来自多个锚节点的加权跳数进行运算，使网络平均跳距估计更准确。本文提出了一种基于RSSI测距的改进DV-Hop定位算法，利用RSSI测距优化两个节点之间的跳数，同时，设置校正因子修正平均跳距，再根据无约束优化算法估计未知节点的位置。
1 DV-Hop定位算法
DV-Hop算法采用泛洪来获得两个节点之间的最短路径和网络中的平均跳数，然后使用三边测量法来估计节点位置。DV-Hop算法可以分成3个步骤执行[13]：
步骤1 获取未知节点和锚节点之间的最小跳数。每个锚节点向其他节点广播两个参数：自身坐标和跳数，其中在算法开始时初始化跳数为0。每个邻居节点将锚节点的坐标信息和其到锚节点的最小跳数保存在自身列表中，并将最小跳数增加1发送给其邻居节点。如果一个节点接收到来自同一个锚的另一个消息，但是与其列表中保存的跳数相比，跳数更高，则忽略该消息。
步骤2 计算锚节点的平均每跳距离：定义一个Hopsize参数，它表示锚节点的平均每跳距离，由以下公式计算得出：
(1)
式(1)中：(xk,yk)和(xl,yl)分别表示锚节点k和l的坐标；n表示锚节点的数量；hkl表示这两个锚节点间的最小跳数。锚节点向其他节点广播它的平均每跳距离，未知节点接收并保存距离最近锚节点的平均每跳距离并将其转发。
步骤3 未知节点Ui到锚节点Ak的距离可以表示为：
dik=c×hik
(2)
假设n个锚节点的坐标分别为(x1,y1),(x2,y2),…,(xn,yn)，每个锚节点到未知节点的距离为d1,d2,…,dn，设未知节点Ui的坐标是(x,y)，可以得到一组方程组，即：
(3)
上述公式每一个等式的左右两边都分别减去最后一个等式的左右两边，由此得到：
(4)
用线性方程组表示为AX=b，其中：
(5)
(6)
(7)
根据最小二乘法，求出未知节点坐标为：
X=(ATA)-1ATb
(8)
在DV-Hop算法中，用于计算的两个节点之间的跳数是一个整数，但实际的跳数通常不是整数。在图1中，节点B和节点C在节点A的通信范围R内。此时B、A之间的距离和C、A之间的距离并不相等，但节点B、C与节点A之间的跳数都被看作是1。此外，当使用最近的锚节点的平均跳距，而不是使用网络中所有锚节点的平均跳距计算定位结果时，误差通常会更大。因此，必须找到一种更加精确的改进DV-Hop定位算法。
图1 节点位置示意图
2 基于RSSI测距的改进DV-Hop定位算法
本文提出的基于RSSI测距的加权DV-Hop定位算法包括3个步骤。首先，利用RSSI算法计算节点之间的加权跳数；然后使用校正因子来改进平均跳距；最后，使用无约束优化算法估计未知节点的位置。
2.1 基于RSSI测距的节点加权跳数计算
RSSI测距传输常用的损耗模型[14]如式(9)所示：
(9)
式(9)中：Pr(d0)是发射机和接收机之间距离为d0时的接收信号功率; Pr(d)是距离为d时的接收信号功率；η是路径损耗指数，其取值范围为1.5和5之间；Xσ是均值为零，标准差为σ的高斯随机变量，σ的值在4 dBm和12 dBm之间。
对于给定的RSSI误差，当节点间的距离越大时，最终的定位误差也越大。因此，在算法的步骤1中，将RSSIj添加到广播消息中，该广播消息对应于从锚节点Ak到未知节点Ui的第j个广播之后的接收信号。如果锚节点接收到的消息对应的跳数大于另一个消息对应的跳数，则锚节点丢弃对应跳数较大的消息，跳数可表示为：
hj=hj-1+Hjh1
(10)
式(10)中h1是给定的初始跳数，可由式(11)计算得出：
(11)
且有：
(12)
式(12)中，RSSI0由式(9)计算得到。
2.2 使用校正因子改进平均跳距
本文使用校正因子来改进DV-Hop算法中的平均距离，校正因子表示为：
(13)
式(13)中: dkl是锚节点Ak、Al之间的实际距离；
是锚节点Ak、Al之间的估计距离；hkl由式(10)得出。则平均跳距表示为：
(14)
式(14)中
它表示所有锚节点的平均每跳距离；λ是用于平衡网络中平均跳距的参数，它与网络环境有关。根据式(2)计算未知节点Ui和锚节点Ak之间的距离，并且在式(2)中，c用式(14)代替，而hik由式(10)迭代得到。
2.3 未知节点的位置计算
由于根据最小二乘法计算未知节点的坐标会导致误差积累，效果不佳[15]。因此本文利用无约束优化算法[16]估计未知节点的坐标，可得如下方程组：
(15)
式(15)中：(x,y)和(xk,yk)表示未知节点Ui和锚节点Ak, k=1,2,…,n的坐标；dk,k=1,2,…,n表示锚节点和未知节点之间的距离；ek,k=1,2,…,n表示误差。上述公式每一个等式的左右两边都分别减去最后一个等式的左右两边，得到一个超定方程组。定义常数ai，bi，ci，c和Di。i=1,2,…,n-1，且有：
(16)
(17)
那么超定方程组就可以写成矩阵形式：
Gz=d
(18)
且有：
(19)
(20)
(21)
等式(18)可以写成二次规划问题
(22)
式(22)中
是与跳数hik相关的加权矩阵，定义为：
(23)
未知节点坐标可以通过求解式(22)得到。为方便求解，将式(22)转化为无约束优化问题，如式(24)所示：
min(eTWe+
)
(24)
求解式(24)可得：
z=(P+GTG+ΔI)-1GTD
(25)
ΔI是Δ>0时的正则化项，I是n+2阶的单位矩阵，并且
(26)
3 仿真实验分析
3.1 仿真参数选择
利用Matlab软件对本文算法进行仿真分析，并与传统的DV-Hop算法、文献[10]提出的改进的DV-Hop定位算法、文献[11]提出的基于最优辅助距离估计锚节点的DV-Hop定位算法以及基于RSSI测距的改进DV-Hop定位算法(最小二乘法求解)进行比较。在传输损耗模型中，令η=4，σ=4 dBm。仿真区域为100 m×100 m的二维平面。为了减小算法的偶然性带来的误差，将各个算法重复运行50次，取平均值作为最终的结果，用平均定位误差(Average Localization Error，ALE)衡量算法性能：
(27)
式(27)中：N表示未知节点的数量；(xi,yi)表示未知节点Ui的实际坐标；(Xi,Yi)表示未知节点Ui的估计位置坐标；R表示通信半径。
上文提到，λ是用于平衡网络中平均跳距的参数，它与网络环境有关。本节通过多次仿真实验选取出合适的λ值。图2给出了对应于不同λ值时本文算法的平均定位误差。假设网络中有200个节点，3种情况下锚节点数量分别为20，40，60，通信半径为R=20 m。由图2可知，在锚节点数量逐渐增加的过程中，平均定位误差越来越小，综合考虑三种不同锚节点比例下的平均定位误差，当λ=0.7时，3种情况下的平均定位误差都较小。因此在本文算法中，选择λ=0.7作为仿真参数。
图2 λ取不同值时本文算法的平均定位误差曲线
3.2 结果分析
1)节点总数变化对平均定位误差的影响
WSN中的传感器节点部署是随机的，节点总数量对定位精度有着重要影响。图3为在不同数量的传感器节点情况下，不同算法的平均定位误差曲线。在100 m×100 m的二维平面内，令节点的总数量从100增加到400，而锚节点的比例始终保持在20%。每个节点的通信半径R=20 m。由图3可知，当传感器节点数量不断增加时，平均定位误差越来越小。其原因是传感器节点数量的增加使得节点密度也随之提高，网络连通性越来越好，此时未知节点可以获得更多的定位所需的信息，并且使用无约束优化的算法能够提高定位精度。而当网络中的传感器节点数量达到一定的值时，平均定位误差只会发生微小的变化。与其他算法相比，本文算法在定位精度方面表现更好，当节点数量为150时，本文算法的平均定位误差为0.25，DV-Hop算法、文献[10]算法、文献[11]算法的平均定位误差分别为0.53、0.49、0.41，本文算法和其余3种算法相比，平均定位误差降低了52.8%、49.0%、39.1%。
图3 节点总数变化时的平均定位误差曲线
2)锚节点比值变化对平均定位误差的影响
图4为在不同锚节点比值的情况下，不同算法的平均定位误差曲线。在100 m×100 m的二维平面内部署300个节点，设置通信半径为30 m，锚节点比值从5%增加到30%。由图4可知，在锚节点比值逐渐增大的过程中，所有算法的平均定位误差均减小，其原因是锚节点比值的增加意味着锚节点密度增大，锚节点间的估计距离会变得更加准确，此时利用RSSI算法计算出的节点之间的加权跳数会更精确，平均跳距也会更精确。另外我们还可以看出，相同条件下，本文算法的平均定位误差始终是最小的。当锚节点比例为30%时，本文算法的平均定位误差有最小值0.28，此时DV-Hop算法、文献[10]算法、文献[11]算法的平均定位误差分别为0.67、0.51、0.42，本文算法和其余3种算法相比，平均定位误差降低了58.2%、45.1%、33.3%。
图4 锚节点比值变化时的平均定位误差曲线
3)通信半径变化对平均定位误差的影响
图5为在不同通信半径的情况下，不同算法的平均定位误差曲线。在100 m×100 m的二维平面内部署300个节点，其中锚节点个数为60，设置通信半径的变化范围在15～40 m。
图5 通信半径变化时的平均定位误差曲线
由图5可知，在通信半径逐渐增大的过程中，所有算法的平均定位误差均在减小，这是因为在未知节点位置的计算过程中使用了无约束优化算法，它充分考虑了节点间的测距误差对定位结果的影响，将定位结果的计算转化为无约束优化问题，提高了定位精度。本文算法的定位效果始终是最好的。当通信半径为30 m时，本文算法的平均定位误差为0.19，此时DV-Hop算法、文献[10]算法、文献[11]算法的平均定位误差分别为0.55、0.45、0.38，本文算法和其余3种算法相比，平均定位误差降低了65.5%、57.8%、50.0%。
4)不同的定位算法对平均定位误差的影响
图6为利用无约束优化算法(本文算法)和最小二乘法进行定位计算求解得到的平均定位误差图。在100 m×100 m的二维平面内部署300个节点，其中锚节点个数为80，设置通信半径的变化范围在15～40 m。由图6可知，在通信半径逐渐增大的过程中，两种算法的平均定位误差均在减小，但是，利用无约束优化算法求得的平均定位误差始终小于利用最小二乘法求得的平均定位误差。因为在利用无约束优化算法求解的过程中，加入了节点的跳数信息以及节点间的测距误差信息，从而优化了定位结果。当通信半径为40 m时，利用无约束优化算法可以获得最小平均定位误差为0.16。
图6 通信半径变化时利用最小二乘法和无约束优化算法计算的平均定位误差曲线
4 结论
提出一种RSSI测距和DV-Hop算法相结合的改进DV-Hop算法。首先根据节点间的RSSI测距值计算节点间的跳数，根据所有锚节点的平均每跳距离以及网络环境参数设置校正因子以修正平均跳距，采用无约束优化算法代替传统的最小二乘法计算未知节点的坐标，减小了定位误差的累计。本文提出的改进DV-Hop算法不需要额外的硬件，和同类型的算法相比有更好的节点定位精度。
[1] 郄剑文,贾方秀,李兴隆,等.基于组合测距的无线传感器网络自定位算法[J].传感技术学报,2016,29(5):739-744.
[2] PEROTTI J M,LUCENA A R,MULLENIX P A,et al.Wireless Sensor Network[C]//Proceedings of SPIE-The International Society for Optical Engineering,2017:16.
[3] HUA X,JINJIN Z,LEI B.A new three-dimension spatial location algorithm of wireless sensor network[J].International Journal on Smart Sensing & Intelligent Systems,2016,9(1):233-255.
[4] WANG J.A Node Location Algorithm in Wireless Sensor Network Based on DV-Hop[J].Computer Engineering,2015,41(1):82-86.
[5] 龙佳,卑璐璐,李轶,等.基于RSSI的改进加权质心定位修正算法[J].微电子学与计算机,2017,34(4):89-93.
[6] WANG X,GAO L,MAO S,et al.CSI-Based Fingerprinting for Indoor Localization:A Deep Learning Approach[J].IEEE Transactions on Vehicular Technology,2017,66(1):763-776.
[7] 崔法毅，邵冠兰.基于RSSI多边定位误差的加权质心定位算法[J].红外与激光工程.2015,44(7):2162-2168.
[8] 邹东尧,李晨,刘碧微.基于垂直平分线的非测距定位算法[J].计算机测量与控制,2016,24(2):202-204.
[9] ZHOU L,KANG Z,HE Y.Weighted hyperbolic positioning DV-Hop algorithm based on triangle inequality[J].Journal of Electronic Measurement & Instrument,2013,27(5):389-395.
[10] 邱奉美,李怀忠.无线传感器网络DV-Hop定位算法的改进[J].计算机工程,2014,40(8):15-20.
[11] 李彦,田亮.一种结合辅助估距锚点的WSN改进型DV-Hop算法[J].南京邮电大学学报(自然科学版),2016,36(5):120-126.
[12] TAO Q,ZHANG L.Enhancement of DV-Hop by weighted hop distance[C]//Advanced Information Management,Communicates,Electronic and Automation Control Conference.IEEE,2017:1577-1580.
[13] 谭志,张卉.基于节点间覆盖关系的改进DV-Hop算法[J].北京邮电大学学报,2014,37(1):35-38.
[14] 李奇越,李伟,孙伟,等.基于RSSI和辅助节点协作的Wi-Fi室内定位方法[J].电子测量与仪器学报,2016,30(5):794-802.
[15] 詹华伟,詹海潮,赵勇.基于RSSI极大似然估计定位算法的改进与实现[J].河南师范大学学报(自然科学版),2018,46(5):43-47.
[16] KUNAR S,LOBIYAL D K.Novel DV-Hop localization algorithm forwireless sensor networks[J].Telecommun Systems,2017,64(3):509-524.