基于机会网络节点定位算法的优化设计

刘 涛

（阜阳职业技术学院 工程科技学院，安徽 阜阳 236031）

0 引言

节点定位技术是机会网络主要支撑技术，国内外对该技术的研究渗透到了移动互联网、物联网、计算机网络等多个领域，也出现了比较多的新思路和新算法，但节点定位的 “安全” “准确” “广泛” 的特征很大程度上决定了技术推广的实际价值.因此，龙增艳等［1］提出机会网络中的节点数据在转发数据包之前，利用探测的方式来发现自身节点与其他节点的连接点，需要一种均衡关系来满足这一要求.刘名阳等［2］提出，随着无线网络的普及与发展，不同移动网络的路由节点自主性提高，在此基础上，网络安全以及网络定位成为机会网络研究的重要一环.张光华等［3］提出，机会网络中的自私节点是影响网络安全输出数据的重要因素，建立可信的路由模型是构建网络安全的一项重要手段.综上所述，网络节点定位问题是机会网络构建的核心问题，而如何解决节点定位覆盖率低这一问题更是重中之重.本文正是基于原有的经典APIT 算法做了相应改进，得到基于内点测试法的加权质心定位改进算法，该算法的扩展性能比APIT 算法更强，节点定位精度和覆盖率也较原先的算法大幅提高，可以满足大中型规模的机会网络中较低的定位误差和较高的节点定位覆盖率的要求.

1 基于内点测试的改进算法

原有的经典APIT算法存在一些问题，为了解决原有算法的问题，提出了优化算法.优化算法利用内点测试法判断未知节点与其邻居锚节点的位置关系，从而缩小未知节点可能所处的范围，再利用加权质心算法对未知节点进行定位.

1.1 内点测试法

假如节点的移动存在一个方向，沿着这个方向节点D同时远离或靠近三角形的三个端点A，B，C，那么可以判定节点D 位于△ABC 之外，如图1（a）所示；否则，当节点D 远离其中两个节点并且靠近另一个节点，或者靠近两个节点并且远离另一个节点时，则判定节点D位于△ABC内，如图1（b）所示.

图1 内点测试法原理图

这里的内点测试法是利用信号的传播特性来判断未知节点是否远离或靠近的.本文假设节点间发射信号强度与距离满足式（1）的通用模型：

其中：PR为节点接收到的信号强度；PT为发射功率；W(d0)为经过距离d0的路径损耗；η 为路径损耗指数；d为距离.通常节点信号源距离未知节点越远，未知节点接收到的能量信号越弱.

1.2 基于两个锚节点定位方法

在机会网络中经常会遇到这样的情况：节点是移动的，当未知节点只有两个邻居锚节点时，可以通过一定的数学计算来得到它的位置坐标［4］.设A，B是它的两个邻居锚节点.锚节点A，B的坐标是已知的，未知节点S的坐标为(xs,ys).通过信号强度与距离转换模型式（1），可以得到AS，BS，AB 之间的距离，它们分别用d1，d2，d3表示，那么在△ABS中作AB的高SC，SF⊥x轴，CE⊥x轴，BD⊥x轴，如图2所示.

图2 基于两个锚节点的定位

设∠SAB = α，∠BAD = β，根据正余弦定理得到

所以

导出

同理，结合锚节点B的坐标和正余弦定理，易知

又

计算未知节点坐标为

2 实验仿真结果与分析

2.1 同一锚节点比例

在网络环境部署完成的情况下，现保持锚节点比例为30%不变，节点总数分别为100，110，120，130和140个.仿真情况如图3所示.

图3 同一锚节点比例统计

由图3（a）可见，在锚节点比例不变的情况下，本文算法比传统APIT算法体现出更小的定位误差.随着总结点个数的增加，定位误差接近0.3%，而APIT算法的定位误差却保持在0.45%左右，这说明了本文算法比APIT算法优越，比较适合大规模的网络节点定位［5］.由图3（b）可见，APIT算法的定位覆盖率维持在70%左右.而本文算法随着节点总数的增加，定位覆盖率不断接近100%，这说明当锚节点比例不变时，本文算法在定位覆盖率方面略胜一筹.

2.2 不同锚节点比例

考虑锚节点比例不同的情况.设节点总数为100，不同的锚节点数分别为20，30，40，50，60 等，两种算法的定位精度和定位覆盖率的变化情况如图4所示.

由图4（a）可见，随着锚节点个数的增多，APIT 算法的定位误差越来越差，最差可达到0.6%，这说明APIT算法中，未知节点定位时受到锚节点的影响较大，尤其是相距未知节点较远的邻居锚节点，这样会使质心估计时的误差增大.而在本文算法中就不存在这样的问题，锚节点个数增多对本文算法是有利的，即邻居锚节点增多，在内点测试阶段，选择距离未知节点最近的三角形的加权质心作为估计位置，结果会更加准确［6］.由图4（b）可见，随着锚节点个数增加，APIT 算法的节点定位覆盖率呈现上升趋势，而本文的算法的节点定位覆盖率不断接近100%.这说明锚节点个数增加时，本文算法比APIT算法性能更加优越.

图4 不同锚节点比例统计

2.3 不同的网络连通度

比较两种算法在不同的网络连通度下的性能，通过改变节点通信半径来实现网络连通度的改变.通信半径R分别取20，22，24，26，28 m，算法性能如图5所示.

图5 不同网络连通度统计

由图5（a）可见，当通信半径增大时，本文算法的定位误差率与APIT 算法呈现不同的趋势.传统APIT 算法的定位误差率存在上升势头，当通信半径增大到28 m 时，定位误差率已经达到0.48%.而本文算法的定位误差率在缓慢下降，当通信半径增大到28 m 时，定位误差率已经接近0.28%，比APIT 算法低很多.由图5（b）可见，当增大通信半径时，本文算法的节点定位覆盖率一直呈现上升趋势，不断接近100%.

3 结语

本文根据机会网络的网络特性，一方面鉴于免测距定位算法易实现的优点，另一方面结合内点测试法和加权质心算法，提出了定位精度、节点定位覆盖率都比较高的新机会网络节点定位算法.经节点升级后的优化算法相对于传统的APIT算法更具精度高、误差低、易实现等多方面的优越性.