一种改进的APIT定位算法

一种改进的APIT定位算法刘尚翼1134041005一、节点定位技术的重要性首先，无线传感器网络中，节点所采集的数据或探测的事件，通常都需要有相应的地理位置信息作为标识，对大多数应用来说，不知道传感器位置，所感知的数据是没有意义的。比如：一个被监控的车辆的地点、森林火灾发生的位置、战场上敌方车辆的运动区域等。其次，无线传感器网络的一些系统功能需要节点的位置信息。例如：确定无线传感器网络的覆盖范围等。最后，许多无线传感器网络协议也都利用了节点的位置信息，比如利用节点间的地理位置信息控制节点的发送功率以及约束波束的方向性、进行路由决策等。因此，传感器的节点定位在整个无线传感器网络中占有重要地位，是无线传感器网络的支持技术之一。二、节点定位技术的分类无线传感器网络的节点地位技术分主要为两类：基于测距的定位技术和免于测距的定位技术。基于测距的定位技术(Range-BasedLocalizationSchemes)：需要通过不同的测距技术，如到达时间测量法（TOA）、到达时间差测量法（TDOA）、基于接收信号能量的测距技术(RSSI）等得到节点间的距离或角度信息，然后再使用相应定位方法计算节点位置。免于测距的定位技术(Range-FreeLocalizationSchemes)：无需节点间的距离或角度信息，而利用节点间的邻近关系和连通性实现定位。一般说来，免于测距的定位技术定位精度不如基于测距的定位技术高，但是基于测距的定位技术对硬件要求很高，而且在测量距离和角度的准确性方面需要大量的研究，而免于测距的定位技术不需要知道未知节点到锚节点的距离，在成本和功耗方面比基于测距的技术具有优势，因此得到了广泛应用。常用的免于测距的定位技术质心定位算法、APS算法、MDS-MAP算法、APIT定位算法等。APIT定位算法的基本思想简单，实现容易。而且由于其定位功耗小、成本低、节点定位精度高等特点得到广泛应用和研究。三、APIT定位算法APIT算法的理论基础是PIT（pointin-triangulationtest）算法（三角形内点测试法）：假如存在一个方向，沿着这个方向节点M会同时远离或接近参考节点A、B、C，那么节点M位于三角形ABC外部，如图1所示；否则，M位于三角形ABC内部，如图2所示。图1图2AMCBAMCBPIT算法中假设待定位节点M是运动的，然而，在大多数WSN中，待定位节点通常是静止的。为了在静态网络中执行PIT测试，我们定义了APIT算法，即近似三角形内点测试法（approximatepoint-in-triangulationtest）：假如待定位节点M的相邻节点没有同时远离或靠近参考节点A、B、C，则节点M位于三角形ABC内部；否则，位于三角形ABC外部。APIT算法是利用WSN较高的节点密度，同时在给定方向上，节点离参考点越远，信号强度越弱的特性，通过与相邻节点的信息交换来模拟PIT算法的。下面以图来说明。在图3中，节点M与相邻节点1都通过发送信号的强弱得知自己与参考节点A、B、C的远近，然后节点M与节点1通过交换信息，得知自己如果运动至1处，将远离B、C，但会接近A，与2、3、4点的判断也类似，最终确定自己位于三角形ABC内部。图3ACB1M423在图4中，待定位节点M通过上述类似的通信判断知如果运动至相邻节点2处，则将同时远离参考节点A、B、C，所以可以得知自己位于三角形ABC的外部。图4A13M42CB在判断出M位于三角形内后，则将其标记（在三角形外部则不标记），依次对M周围的所有邻近参考节点（在发送功率范围内的参考节点）进行各种不同的组合并检测，最终找出所有满足要求的三角形的重叠区域，求其质心位置以替代待定位节点在网络中的具体位置坐标，如图5所示。图5通过以上关于APIT算法思想的描述,可以得出其实现过程分为以下4个阶段:(1)节点间信息接收和交换。待定位节点接收参考节点的位置信息、节点ID和信号强度等信息,以及未知节点之间相互交换各自接收到的参考节点信息。(2)执行APIT测试。使用APIT测试方法判断未知节点是否位于参考节点三元组合形成的三角形内部。(3)计算重叠区域。计算多个三角形覆盖区域的重叠部分，计算重叠区域的方法为格子扫描法（GridScan)：将WSN所监测区域分为大小相同的网格，每个网格初始值设为0，如果判断出待测节点位于三角形内，相应三角形所在网格区域值加1；反之，相应三角形所在网格区域值减1，不断重复上述步骤，最后得到网格数值最大的区域就是要求的重叠区域。(4)计算质心。计算(3)中所求得的重叠区域的质心,作为未知节点的估计位置。四、APIT算法的不足通过上述分析发现，APIT算法仅仅分析几个有限的方向，而且定位覆盖率（可实现定位的未知节点数目与总的未知节点数目之比）与相邻节点数量及分布密切相关，因此APIT算法有时会做出不正确的判断以及存在大量无法定位的节点。下面以图例进行分析。如图6所示，由于相邻节点2在三角形ABC之外且离参考节点A、B、C都较M点距这三个参考点远，从而当模拟M点朝2处运动时，会使M点错误的判断自身在三角形ABC之外。图6AB12M4C3如图7所示，由于相邻节点1、2、3的不规则部署，从而使得M点模拟朝1、2、3的任何一个方向运动时，都不会同时远离或靠近A、B、C，从而M点错误的判断自身在三角形ABC之内。图7A12M3CB如图8、9所示，待定位节点M的邻近参考节点少于三个或M在三角形ABC的外部，造成APIT算法无法应用，这样M点就成了无法定位的节点。图8图9ABMMACB由于上述客观原因的存在，影响了整个WSN的定位覆盖率及定位精度。因此，文章针对上述问题，提出了改进算法。五、改进的APIT算法在节点定位中，我们最关心的莫过于定位精度和定位覆盖率这两个性能参数。我们先对定位精度这个问题进行分析。定位精度的问题，与图6和图7情况下的两种错误判决密切相关，这两种错误WSN中将其称为In-to-outerror和Out-to-inerror。下面以图的形式分析如何将其改进。如图10所示，假设图中所得到的两个顶点为空心圆的三角形区域均为正确的。节点经过APIT测试后获得了一个错误的Out-To-In区域(用实心顶点的三角形标识)。假设该错误的三角形区域覆盖了grid(2,5)这个网格，则该网格对应的值将要加1，即变为2。本来，原本正确的交集区域的中心应该位于grid(5,3)对应的网格附近。然而，Out-To-Inerror将中心位置移至了grid(3,4)对应的网格附近。图10假设网格大小为0.1R，R为参考节点的通信半径，则定位精度将因此增加大于20%的误差。000011110001021110001111100012111000022110000111100000针对以上问题，文章提出了计算未知节点可能存在的所有三角形区域的重心坐标法，通过计算重心坐标所构成图形的质心作为未知节点的估计位置。如图11所示。图11000011110001021110001111100012111000022110000111100000通过对比图10和图11可以发现，求三角形重心坐标比网格扫描法更加接近grid(5,3)，主要是因为三角形重心扫描算法是以点为出发点，而网格扫描法是以区域为出发点，从而网格扫描算法更易受Out-To-In或In-To-Out错误区域的影响。这样，重心扫描算法相比网格扫描法可以提高定位精度。定位覆盖率的问题，主要受图8和图9所示问题的影响，在这两种情况下，WSN无法对相应节点进行定位。为了提高定位覆盖率，可以将已经定位的未知节点升级为参考节点，这样就有效提高了参考节点的比例。为了保证定位的精确性，新的参考节点在进行定位时所用到参考节点组成三角形的数量须大于等于4个。这样，如果部分处于图8和图9情况下的待定位节点的邻近参考节点变得大于等于三个且其处于三角形内部，就可以用APIT算法进行定位了。但是，即使使用上面的方法，仍然可能有一些未知节点的邻近节点数少于三个或者处于所有三角形的外部，这样造成无法定位。为了进一步扩大定位覆盖率，我们可以再引入基于测距的定位技术中的RSSI算法。RSSI算法，即基于接收信号能量的测距技术，其原理是已知发射节点的发射信号强度，接收节点根据接收到的信号强度，然后利用无线信号能量与距离的公式：d=d0*10[Pr(d0)-Pr(d)]/10n得出发射节点与接收节点的距离d。这里可以引入RSSI算法的理论基础是在APIT算法中，节点间交换信息时，本身就存在着所谓的能量强度信息的交换，而且能量与距离公式的计算方法也不复杂，因此，引入RSSI算法基本不会增加硬件成本。在得出距离后，便可以利用一些定位方法，如三边测量法，多边测量法等得出待定位节点的位置坐标了。由于RSSI算法不涉及角度信息，因此，对于邻近节点只有两个或两个以下的未知节点，仍然无法定位。同时，为了减少开销，对于大于等于三个邻近节点的未知节点，我们只得出其与其中三个邻近参考节点的距离信息就可以了，因此，估计未知节点坐标时，采用三边测量法比较合理。整个改进算法流程图如下所示：NYYNYN网络布置初始化节点信息交换参考节点=3且处于三角形内?重心扫描法对未知节点定位新定位节点升级结束参考节点=3且处于4个三角形内？参考节点3?标记为routernode执行RSSI技术和三边扫描六、仿真结果及分析平均定位误差（即定位精度）随锚节点比例变化曲线，节点总数不变。定位覆盖率随锚节点比例变化曲线，节点总数不变。平均定位误差（即定位精度）随节点总数变化曲线，锚节点比例不变。定位覆盖率随节点总数变化曲线，锚节点比例不变。上述两组图是传统APIT算法和改进算法在不同锚节点比例和节点总数时平均定位误差和定位覆盖率的比较。从图中可以看出，改进后的算法的平均定位误差明显小于传统算法，而定位覆盖率明显高于传统算法，说明改进后的APIT算法在算法上的确优于传统的APIT算法。再从通信开销上来看，改进算法和传统算法的区别只在于传送最后升级的已定位未知节点的数据包，由于改进算法中对已定位未知节点的升级有一定的限制条件，故算法中最终升级的未知节点数量不会太多，而且在无限传感器网络中，节点本身在间隔一定的时间后会广播自己的位置信息，故改进算法与原算法比较，通信开销的增加不是特别明显。在计算开销方面，改进算法在近似三角形内点测试前先比较了未知节点与锚节点所组成三角形一边的两个顶点距离之和与三角形的边长，在计算开销中增加了未知节点与锚节点、锚节点之间距离的估计。但是，改进算法在进行未知计算时没有采用传统的网格扫描方式，而是直接计算锚节点所组成三角形重心的质心，在这个过程中省去了网格扫描时三角形区域与每个网格边界的比较，大大的减小了计算开销。综合以上分析结果可知，改进后的算法与原算法相比较，在通信开销上有所增加，并且因为未知节点的能量要比锚节点小，升级的部分未知节点会因为能量过早耗尽而产生失效的问题，但是考虑到无线传感器网络中节点一般是密集布置，因此这样的缺点基本上不会对网络构成威胁。在计算开销方面，改进的算法节省了大量的计算开销，可以降低传感器节点的能量损耗速度。总的来说，改进算法在无需添加硬件设备的情况下改善了定位的精度和覆盖率，在无线传感器网络节点定位研究中具有一定的意义。七、参考文献[1]SavareseC,RabaeyJ,Beutel.Locationingindistributedad-hocwirelesssensornetwork.Proceedingsofthe2001IEEEInternationalConferenceonAcoustics,Speech,AndSingal(ICASS’01),Vol.4,SaltLake:IEEESingalProcessingSociety,2001:2037-2040.[2]于宏毅，李鸥，张效义等.无线传感器网络理论、技术与实现.北京：国防工业出版社，2010,9重印.[3]马刚，陈盛云.WSN中APIT节点定位改进算法研究.昆明理工大学信息工