随着无线传感器网络(Wireless Sensor Network, WSN)的发展和普及,传感器网络自身定位技术在应用中显得愈发重要。WSN定位技术通常可分为基于测距和无须测距两种[1],其中基于测距技术的定位算法如三边定位等由于定位精度较高,应用最为广泛。但由于测距方法本身存在一定误差,如接收信号强度指示(Received Signal Strength Indication, RSSI)的测距误差可能高达±50%,使得测量的距离信息并不准确,进而对定位算法的定位效果产生不良影响[2]。这种情况随着高精度测距技术如到达时间差(Time Difference Of Arrival, TDOA)、飞行时间(Time Of Fly, TOF)等测距技术的发展而得到大幅改善。然而,除测距精度之外,在WSN定位算法中,因为选择不恰当的锚节点也可能会导致较大的定位误差甚至定位失败。在基于测距的多维定标(Multi-Dimensional Scaling, MDS)定位算法中,如MDS-MAP[3]、等距特征映射 (ISOmetric feature MAPping,ISOMAP)[4-5]等,这类算法完全依赖锚节点将网络相对坐标转换为绝对坐标。因此如何选择合适的锚节点便成为此类定位算法中的一个重要问题。
当前研究人员普遍认为选择分布较均匀的锚节点进行定位能够提高WSN的定位精度[6-9]。为了充分认识锚节点之间以及锚节点与未知节点之间的分布或拓扑关系对WSN定位精度的影响,文献[6]针对锚节点的部署或分布与算法定位精度的关系进行分析并提出了锚节点的优化部署策略;文献[7]则针对传感器网络提出一种改进的锚节点选择策略以提高定位精度。文献[8]和文献[9]则引入了共线度(Degree of Collinearity, DC)的概念,并将其应用到网络节点定位中以避免较大的定位误差。其中,文献[8]将共线度用于衡量选择的锚节点组合是否有效,并提出一种基于三角形最小高的“共线度”定义,即三个锚节点构成的三角形中三个高的最小值;文献[9]则提出了一种基于最小角的“共线度”的概念,并基于此提出一种基于共线度的无线传感器网络定位算法(Collinearity Based Localization Algorithm, CBLA)以提高定位精度。
基于共线度的定义,文献[10]针对动态传感器网络提出了一种基于共线限制因子(Collinearity Limiting Factor, CLF)的锚节点共线解决方案,CLF即锚节点组成三角形任意高与底边的比值,该方法本质上源自三角形最小高的共线度定义。受其影响,文献[11]通过限制锚节点之间的角度大小给出了一种锚节点共线约束选择策略,该方法本质上则源自基于最小角的共线度定义。 除此之外,Zhang等[12]基于共线度改进DV-Hop(Distance Vector-Hop)定位算法定位精度;文献[13]则研究了2维、3维空间网络节点定位估计中的共线、共面问题,并通过对锚节点位置几何拓扑关系的研究提出了基于拓扑质量的解决方案。
然而,目前尚无研究对这两类基于最小高和最小角的共线度定义及相关的定位算法进行比较。本文对这两种基于不同共线度定义的算法的缺陷进行分析,引出“聚集-共线度”(Degree of Aggregation-Collinearity,DAC)概念,并在此基础上提出一种基于“聚集-共线度”和“节点度”的锚节点选择策略以提高定位精度,称为DAC-ND。最后通过Matlab仿真实验与基于共线度的定位算法进行对比验证。
1 锚节点分布对定位精度的影响在对MDS、ISOMAP等定位算法的实验分析中,如何选择合适的锚节点成为制约此类算法定位精度的一个非常重要的因素,因此对其进行专门分析。通过实验分析可知,当所选择的锚节点组合在共线分布和集中分布两种情况下时会导致定位结果出现较大的误差,下面将通过实验结果来具体说明锚节点分布对定位结果的影响。在仿真实验中,选择MDS定位算法中最早也是最为常用的MDS-MAP[3-4]作为实验对象,在50 m×50 m的二维平面随机部署15个节点,假设节点通信半径R=30 m,邻居节点间距离可测且不考虑测距误差以便观察问题现象。
1.1 锚节点共线分布在随机部署的包含15个节点的网络中,假设其中{2,5,7,12,13}为坐标已知节点,并从中随机选择三个作为锚节点,其余节点均为坐标未知节点。那么在仿真实验结果中会出现如图 1、2所示的两种极端情况。
图 1表示选择锚节点组合{2,12,13}时MDS-MAP算法的定位计算结果与真实绝对坐标的对比,此时三个锚节点{2,12,13}的分布构成一个较为均匀的三角形,图 1(a)和(b) 的形状几乎完全相同,所有网络节点坐标的平均定位误差仅为0.31 m,在所有锚节点组合中定位精度最高。
图 2表示选择锚节点组合为{2,5,7}时MDS-MAP算法的定位计算结果与真实绝对坐标的对比,此时定位算法结果误差非常大,平均定位误差达到36.34 m,比选择锚节点组合{2,12,13}所得最小定位误差增大近117倍,高出两个数量级。通过观察可发现,锚节点{2,5,7}近似共线。
通过多次重复实验统计可知,锚节点均匀分布时定位算法具有较好的定位精度,而锚节点共线或近似共线则会导致定位算法出现极大的定位误差。
1.2 锚节点集中分布同样随机部署15个节点的网络,其中{2,5,7,12,13}为坐标已知节点,其余均为坐标未知节点。
图 3为选择锚节点{2,5,7}定位的结果示意图,这组锚节点的分布构成一个较为均匀的三角形,图 3(a)和(b)的形状大致相似,此时算法平均定位误差约0.77 m。
图 4为选择锚节点{2,12,13}进行定位的结果,图 4(a)和(b) 的形状存在较大差异,部分节点位置发生较大偏移超出图片范围之外。观察可知,所选三个锚节点分布太过集中,算法的定位结果误差达到8.47 m,与选择锚节点组合{2,5,7}所得最小定位误差相比,提高了一个数量级,误差增大10多倍。
通过以上两个实验的对比结果可知,WSN定位算法中的锚节点的分布对定位结果的误差有很大影响,选择近似共线的锚节点组合会导致较大的定位误差,而选择集中分布的锚节点组合也会降低定位精度。因此,采用共线度来衡量锚节点组合是否有效对于WSN定位算法是有意义的,但其也有明显不足之处,本文将在后面进行分析说明。
2 锚节点的优化选择和定位算法在WSN部署时,应尽可能均匀部署或选择锚节点,以最大化每个锚节点的贡献,并避免锚节点共线和集中分布。目前已有相关研究人员针对这一问题进行研究并提出共线度的概念和方法[8-11],以优化选择锚节点进而提高算法定位精度。
2.1 共线度文献[8]中提出采用共线度来衡量选择的锚节点组合是否有效,其依据是三个锚节点共线或近似共线时,即便是微小的测距误差也会导致较大的定位误差,这与本文第1章的实验结论相同。文献[8]提出了一种基于三角形最小高的“共线度”的定义(本文将其简记为DC-H),如图 5所示,由三个锚节点A、B、C构成的三角形中三个高的最小值,即最大内角或最长边对应的高的长度为这组锚节点的共线度:
$D{{C}_{\text{DC-H}}}=\underset{i=1,2,3}{\mathop{\text{min}}}\,\left\{ {{h}_{i}} \right\}$ | (1) |
在此定义下,DCDC-H的取值范围为[0,
文献[9]则认为以三角形内角来表示共线度更为恰当,并提出一种新的共线度定义,即三个锚节点所组成的三角形的内角的余弦值的最大值(对应三角形的最小内角),如图 6所示,从而得到基于最小角的共线度(本文将其简记为DC-A)定义:
$D{{C}_{\text{DC-H}}}=\text{max}(\text{cos}(\angle A),\text{cos}(\angle B),\text{cos}(\angle C))$ | (2) |
由三角形余弦定理可知,△ABC的三个角的余弦值分别为:
$\left\{ \begin{align} & \text{cos}\left( \angle A \right)=\left| \frac{A{{B}^{2}}+A{{C}^{2}}-B{{C}^{2}}}{2*AB*AC} \right| \\ & \text{cos}\left( \angle B \right)=\left| \frac{A{{B}^{2}}+B{{C}^{2}}-A{{C}^{2}}}{2*AB*BC} \right| \\ & \text{cos}\left( \angle C \right)=\left| \frac{A{{C}^{2}}+B{{C}^{2}}-A{{B}^{2}}}{2*AC*BC} \right| \\ \end{align} \right.$ | (3) |
由于三角形最小内角的角度范围为0~60°,则DCDC-A的取值范围为[0.5,1],并与角度成反比。在选择定位锚节点组合时,该算法认为DCDC-A的取值越小越好。
基于共线度的算法认为锚节点以等边三角形的形式分布最均匀,定位结果最佳,利用共线度来度量锚节点共线的程度,有利于选择定位结果较好的锚节点组合。然而,目前尚无研究对这两种基于不同共线度定义的定位算法进行对比研究和分析。
2.2 基于聚集共线度和节点度的算法笔者经过分析和实验认为以上两种共线度:DC-H和DC-A的定义均有不足之处,用于WSN定位均有其局限性。文献[8]中基于三角形最小高度的共线度定义只能对大小相似的三角形进行比较,无法真正衡量不同锚节点组合的共线度。如图 7(a)所示,左边△A1B1C1中的最小高h1虽然比右边△A2B2C2最小高h2要小,然而△A1B1C1是钝角三角形,其DC值要比△A2B2C2大,即DC(△A1B1C1)>DC(△A2B2C2),即最小高越大共线度越大的假设在此并不成立; 而文献[9]提出的基于最小角余弦值的共线度定义可用于衡量并解决锚节点共线的问题,但却无法度量锚节点是否集中分布,如图 7(b)所示,△D1E1F1和△D2E2F2的大小、集中程度不同,但共线度却相同,即DC(△D1E1F1)=DC(△D2E2F2)。
综合最小高和最小角两种不同定义的共线度的优点,本文提出一种新的聚集-共线度(Degree of Aggregation and Collinearity, DAC)概念。如图 8所示,在锚节点A、B、C组成的△ABC中,假设其中的∠A为最小内角,h为最小高,则可综合最小角和最小高共同衡量锚节点的集中和共线程度,得到的聚集-共线度DAC可表示为:
$D{{C}_{\text{DAC}}}=h/\cos \left( \angle A \right)$ | (4) |
DCDAC由最小高的值和最小角对应的余弦值共同决定,其与最小高的大小成正比,与最小角的余弦值成反比。DCDAC越大,表明共线程度或聚集程度越小,反之亦然。结合前面基于最小角度和最小高度这两种共线度的定义,其表达式亦可表示为:
$D{{C}_{\text{DAC}}}=\frac{D{{C}_{\text{DC-H}}}}{D{{C}_{\text{DC-A}}}}=\frac{\underset{i=1,2,3}{\mathop{\text{min}}}\,\left\{ {{h}_{i}} \right\}}{\text{max}(\text{cos}(\angle A),\text{cos}(\angle B),\text{cos}(\angle C))}$ | (5) |
可知DCDAC的取值范围为[0,
除了锚节点的共线度会对定位结果产生较大影响之外,锚节点与其他节点的连通度对定位算法也有较大影响。这是因为离锚节点较远的节点在测算其间距或位置时会产生累积误差,从而降低定位精度,如MDS-MAP算法中采用最短路径替代节点间距离,基于三边定位的算法中也存在用已定位节点迭代计算未知节点坐标而导致误差积累的问题。锚节点的邻居节点越多,实际可测得的数据就更多、更准确,对算法定位结果的贡献越大,由此产生的累积计算误差就越小。本文借用图论中的节点度(Node Degree, ND)的概念来表示锚节点的连通度,即与该锚节点相邻的节点个数。
基于以上分析和定义,本文提出一种基于聚集-共线度(DAC)和节点度(ND)的锚节点选择算法,称之为DAC-ND,结合锚节点组合的“聚集-共线度”和锚节点组合的“节点度”来综合判断所选的锚节点组合是否适用于定位,其算法表达式如式(6) 所示:
$\begin{align} & D{{C}_{\text{DAC-ND}}}= \\ & \frac{\underset{i=1,2,3}{\mathop{\text{min}}}\,\left\{ {{h}_{i}} \right\}}{\text{max}(\text{cos}(\angle A),\text{cos}(\angle B),\text{cos}(\angle C))}*\sum\limits_{i=\left\{ A,B,C \right\}}{ND\left( i \right)} \\ \end{align}$ | (6) |
DCDAC-ND越小,表明锚节点的聚集-共线度高或者连通度差,所选锚节点组合不适合用于定位; DCDAC-ND越大,表示共线程度和聚集程度低,锚节点布均匀,连通度高,更适合用于定位。
3 仿真实验与结果为了验证DAC-ND算法的有效性,基于测距的MDS定位算法MDS-MAP来进行实验。在100 m×100 m的二维仿真场景中随机部署N个节点,从中按照不同的算法选择3个作为锚节点进行网络定位。实验通过随机选择(Random)、基于最小高的共线度(DC-H)、基于最小角的共线度(DC-A)和本文提出的DAC-ND等四种算法进行对比,节点通信和测距范围为R,假设在测距范围内的节点之间距离均可测得,并分别在无测距误差和有测距误差两种情况下进行仿真实验。
3.1 无测距误差条件下的实验结果首先在假设无测距误差的理想情况下,不考虑测距误差的影响,直接对比以上四种算法的定位性能。实验分别以节点数量和测距半径为变量,以平均定位误差为对比参量。仿真结果如图 9所示。
图 9(a)给出了在不同节点数量情况下几种算法的平均定位误差对比曲线。节点测距半径R为40 m,节点数量N从20增加到60,由于节点平均连通度增加,各算法的平均定位误差均随节点数量增加而降低。其中Random的平均定位误差最大,DC-H与DC-A的定位误差大小居中,而DAC-ND误差最小、性能最好。其中DC-H算法在节点数量为20时要优于DC-A,而当节点数量增加时,DC-A算法要优于DC-H,说明二者互有优劣。综合计算可知,DAC-ND比前三种算法的误差平均分别降低56.9%、22.6%和18.9%。
图 9(b)表示不同测距范围情况下四种算法的平均定位误差对比。节点数量N为40,测距范围R从30 m增加到70 m,各算法的定位误差随测距范围增加而下降。可明显得出Random算法定位误差最大,DC-H其次,DC-A误差较小,DAC-ND的平均定位误差最小。计算可得DAC-ND算法的平均定位误差比Random、DC-H、DC-A三种算法分别降低了54.7%、23.3%和12.8%。
3.2 有测距误差条件下的实验结果在有测距误差的情况下,采用乘性正态噪声测距误差模型,即假设节点间测距结果dij符合乘性正态噪声模型[14]:
${{d}_{ij}}={{\delta }_{ij}}+{{\delta }_{ij}}\text{N}(0,e_{r}^{2})$ | (7) |
其中:δij为真实距离;N(0,er2)表示均值为0、方差为er2的独立正态随机变量,并且假设dij=dji。实验结果如图 10所示。
从图 10(a)可知,各算法的平均定位误差随着测距模型中正态随机变量N(0,er2)中误差控制参数er2的增大而增加,且Random的定位误差远大于其他三种算法,DC-H和DC-A算法的平均定位误差相近,DAC-ND算法定位误差最小。统计结果表明,与Random、DC-A和DC-H等三种锚节点选择算法相比较,DAC-ND算法可大幅度提高算法定位精度,其定位误差平均可分别降低63.8%、22.1%和23.4%。
图 10(b)表示不同节点数量下四种算法的平均定位误差比较,其中测距误差控制参数er2为0.03,节点测距半径R为40 m,节点数量N从20增加到60,连通度增加,因此各算法平均定位误差均随节点数量增加而降低。统计结果表明,与Random、DC-A和DC-H等三种算法相比较,DAC-ND的定位误差平均可分别降低73%、21.8%和23.3%,定位误差更小。
图 10(c)表示不同测距范围下四种算法的平均定位误差比较。其中测距误差控制参数er2为0.03,节点数量N为40,节点测距半径R从30 m增加到70 m,连通度增加,因此各算法的定位误差均随节点测距半径R增加而降低。当节点数量增加到50以上时,DAC-ND与DC-H、DC-A算法的定位误差结果逐渐接近。统计结果表明,与Random、DC-A和DC-H等三种算法相比较,DAC-ND的平均定位误差可分别降低54.47%、15.12%和14.13%,可知其定位精度更高。
4 结语定位技术是无线传感器网络应用的基础研究问题之一,在战场应用中提供了十分重要的位置信息和决策依据。现有基于测距的多维定标定位技术一方面依赖测距精度,另一方面跟算法的性能和网络部署有关。本文重点对锚节点分布与定位精度之间的关系进行研究,分析锚节点的分布对定位算法精度的影响,对现有的两种基于共线度的锚节点选择策略进行分析,进而提出一种基于“聚集-共线度”和“节点度”的锚节点选择方法DAC-ND。将DAC-ND与Random随机选择算法、基于最小高的共线度算法DC-H和基于最小角的共线度算法DC-A等通过多个角度进行仿真实验对比。结果表明,与Random相比,DC-H、DC-A和DAC-ND算法均能大幅度降低定位误差,其中DC-H和DC-A算法的定位性能相近,而DAC-ND算法定位性能则更为优越,从而验证了本文提出方法的有效性,它能够弥补现有基于共线度定位算法的不足,进一步提高定位精度。下一步研究可考虑通过改进算法测距和定位误差累积以进一步降低定位误差。
[1] | 贲伟, 吴振峰, 秦晅. RSSI/TDOA/DV-Distance组合定位算法[J]. 指挥信息系统与技术, 2012, 4 (3) : 55-59. ( BEN W, WU Z F, QIN X. RSSI/TDOA/DV-Distance combined positioning algorithm[J]. Command Information System and Technology, 2012, 4 (3) : 55-59. ) |
[2] | 王福豹, 史龙, 任丰原. 无线传感器网络中的自身定位系统和算法[J]. 软件学报, 2005, 16 (5) : 857-868. ( WANG F B, SHI L, REN F Y. Self-localization systems and algorithms for wireless sensor networks[J]. Journal of Software, 2005, 16 (5) : 857-868. doi: 10.1360/jos160857 ) |
[3] | SHANG Y, RUML W, ZHANG Y. Localization from connectivity in sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2004, 15 (11) : 961-973. doi: 10.1109/TPDS.2004.67 |
[4] | LI B, HE Y G, et al. A novel localization algorithm based on isomap and partial least squares for wireless sensor networks[J]. IEEE Transactions on Instrumentation and Measurement, 2013, 62 (2) : 304-314. doi: 10.1109/TIM.2012.2216476 |
[5] | WANG C Q, CHEN J M, SUN Y X, et al. Wireless sensor networks localization with isomap[C]//ICC 2009:Proceedings of the 2009 IEEE International Conference on Communications. Piscataway, NJ:IEEE, 2009:1-5. |
[6] | HUANG L, WANG F B, MA C, et al. The analysis of anchor placement for self-localization algorithm in wireless sensor networks[C]//Advances in Wireless Sensor Networks, Communications in Computer and Information Science 334. Berlin:Springer, 2013:117-126. |
[7] | HANEN A, FEDERICO V, ALESSANDRO P, et al. An improved anchor selection strategy for wireless localization of WSN nodes[C]//ISCC 2016:Proceedings of the 2016 IEEE Symposium on Computers and Communication. Washington, DC:IEEE Computer Society, 2016:108-113. |
[8] | POGGI C, MAZZINI G. Collinearity for sensor network localization[C]//Proceedings of 2003 IEEE 58th Vehicular Technology Conference. Piscataway, NJ:IEEE, 2004:3040-3045. |
[9] | 吴凌飞, 孟庆虎, 梁华为. 一种基于共线度的无线传感器网络定位算法[J]. 传感技术学报, 2009, 22 (5) : 722-727. ( WU L F, MENG Q H, LIANG H W. A collinearity-based localization algorithm for wireless sensor networks[J]. Chinese Journal of Sensors and Actuators, 2009, 22 (5) : 722-727. ) |
[10] | 刘克中, 崔永强, 张金奋, 等. 基于Monte Carlo的多能量级移动节点定位算法研究[J]. 计算机科学, 2011, 38 (12) : 61-64. ( LIU K Z, CUI Y Q, ZHANG J F, et al. Improved Monte Carlo node localization scheme by using multi-energy-level beacon[J]. Computer Science, 2011, 38 (12) : 61-64. ) |
[11] | 吴世通, 陈良, 李云飞, 等. 基于RSSI等级的蒙特卡罗定位算法应用研究[J]. 计算机工程与应用, 2014, 50 (17) : 114-119. ( WU S T, CHEN L, LI Y F, et al. Application and research on Monte Carlo localization algorithm based on RSSI rank[J]. Computer Engineering and Applications, 2014, 50 (17) : 114-119. ) |
[12] | ZHANG Y Z, XIANG S, FU W Y, et al. Improved normalized collinearity DV-Hop algorithm for node localization in wireless sensor network[J]. International Journal of Distributed Sensor Networks, 2014, 2014 (11) : 1-14. |
[13] | YAN X Y, SONG A G, YU J M, et al. Toward collinearity-avoidable localization for wireless sensor network[J]. Journal of Sensors, 2015, 2015 (2) : 1-16. |
[14] | LATSOUDAS G and SIDIROPOULOS N D. A fast and effective multi dimensional scaling approach for node localization in wireless sensor networks[J]. IEEE Transactions on Signal Processing, 2007, 55 (10) : 5121-5127. doi: 10.1109/TSP.2007.896101 |