基于圆形的权重三角形选择方法的循环三边组合节点位置测量法

摘要

本发明提供的是一种基于圆形的权重三角形选择方法的循环三边组合节点位置测量法。1)任选两个节点A和B，求线段AB的边长a，并计算a2；2)计算x·AB；3)重复1和2步，计算所有的边的平方，和所有的x·AB；4)任选三个节点A、B和C，分别对应边a，b和c，其中a是最短边；5)如果a2+c2-b2＞0和a2+b2-c2＞0且b≤xa，则三角形ΔABC是一个具有较大权重的三角形；6)计算权重多边形的一个顶点；7)重复步骤4、5和6，计算所有的权重多边形的顶点；8)利用权重重心法计算l边形的权重重心位置，即未知节点的估计坐标值：本发明和IACT相比，在没有降低定位精度的前提下进一步降低了节点的能量消耗。

权利要求

1.一种基于圆形的权重三角形选择方法的循环三边组合节点位置测量法，其特征是：2

1)任选两个节点A和B，求线段AB的边长a，并计算a

2)计算x·AB，其中x＝cotα、α为权重三角形的最小角、α＝arccot(1.5)、x在节点布放前根据定位精度设定；

3)重复1和2步，计算所有的边的平方，和所有的x·AB；

4)任选三个节点A、B和C，节点A的对应边为a，节点B的对应边为b，节点C的对应边为c，其中a是最短边；

2 2 2 2 2 2

5)如果a+c-b ＞0和a+b-c ＞0且b≤xa，则三角形ΔABC是一个具有较大权重的三角形；

6)利用步骤5)中满足条件的权重三角形计算权重多边形的一个顶点；

7)重复步骤4、5和6，计算所有的权重多边形的顶点；

8)利用权重重心法计算l边形的权重重心位置，即未知节点的估计坐标值：其中l为满足条件的高权重三角形的个数，m为权重值排序后选取的三边测量组合数。

说明书

基于圆形的权重三角形选择方法的循环三边组合节点位置

测量法

(一)技术领域

[0001] 本发明涉及的是一种位置测量方法。(二)背景技术

[0002] 在传感器网络的应用中，只有当节点和被感知的物体的位置是可知的，节点获得的信息才有意义。因此，节点定位是传感器网络的关键技术之一。

[0003] 现在已有国内外的诸多学者提出了很多定位算法，但总体上来讲，定位精度和能耗费用之间不能很好的两者权衡，定位精度高，往往伴随着算法高复杂性和通信的高费用。传感器节点常采用接收信号强度(RSSI，Received Signal StrengthIndex)技术、信号到达时间(TOA，Time Of Arrival)技术、信号到达时间差(TDOA，Time Difference of Arrival)技术和信号到达角度(AOA，Angle Of Arrival)技术来进行节点间的测距。在以上节点间测距的基础上，传感器网络可采用APS，AHLoS算法、三边测量法、Lateration算法、循环三边组合测量法(ACT)和改进的循环三边组合测量法(IACT)等算法来进行未知节点的定位。

[0004] 三边测量法是已知三个信标节点的坐标以及未知节点到三个信标节点的距离，求未知节点的坐标。为了进一步提高三边测量法的定位精度，传感器网络定位算法及相关技术研究(重庆大学博士论文.2006)中提出了循环三边组合测量法。它通过计算任意三个信标节点所组成的三角形的中心来求出多边形的顶点，再利用质心法定位未知节点。为了进一步降低算法的复杂度和通信费用，又提出了改进的循环三边组合测量法，它利用三角形的角的tan值作为权重来选择权重三角形，并只选择m个权重较大的三角形进行计算来3
降低计算费用和通信费用。但是IACT的计算复杂度仍然是n，计算费用仍然较高。因此，我们需要寻找一种费用更低的定位算法，同时还要保证算法的定位精度。
(三)发明内容

[0005] 本发明的目的在于提供一种费用更低、同时能保证定位精度的基于圆形的权重三角形选择方法的循环三边组合测量法。

[0006] 本发明的目的是这样实现的：

[0007] 1.任选两个节点A和B( 种选择选择方案)，求线段AB的边长a，并计算a2；

[0008] 2.计算x·AB(x＝cotα，α为权重三角形的最小角，α＝arccot(1.5)，x在节点布放前根据定位精度设定)；

[0009] 3.重复1和2步，计算所有的边( 条边)的平方，和所有的x·AB；

[0010] 4.任选三个节点A、B和C( 种选择方案)，分别对应边a，b和c，其中a是最短边；

[0011] 5.如果a2+c2-b2＞0和a2+b2-c2＞0且b≤xa，则三角形ΔABC是一个具有较大权重的三角形；

[0012] 6.计算权重多边形的一个顶点；

[0013] 7.重复步骤4、5和6，计算所有的权重多边形的顶点；

[0014] 8.利用权重重心法计算l边形(总计选出l个满足条件的高权重三角形)的权重重心位置，即未知节点的估计坐标值：

[0015] 本发明的优点通过以下分析来验证：

[0016] 1、CBACT算法性能的数学分析

[0017] 由于加减法计算的时间复杂性远低于乘除法运算和三角函数运算，故这里不考虑加减法计算的复杂性。CBACT算法和Lateration算法的计算费用基本相等，远远低于ACT和IACT算法。ACT算法中的乘除法运算约为52次，三角函数运算为3 次。IACT算法由于采用了不同的权重角度函数，所以避免了需要进行大量的倒数与方根运算的三角函数计算。IACT算法的乘除法运算为9 +28m次，没有三角函数运算。基于圆形权重三角形选择算法，2 +25l，没有三角函数运算。显然，本算法的计算复杂性远低于IACT算法的。图1给出了当m＝20、α＝35°时的几种算法复杂性的比较。分析的结果表明，ACT算法的复杂性最高，当具有12个信标节点的时候，ACT算法的计算次数已经接近万次，计算费用已经很高。和ACT相比，IACT在很大程度上降低了计算费用，但是IACT的计算复杂度仍然
3 2
是n，计算费用仍然较高。将计算复杂度降为是n。和IACT相比，极大地降低了计算费用。

[0018] 2、CBACT算法性能的仿真分析

[0019] 为了评价本算法，利用数字仿真的方法将算法IACT算法进行比较。仿真分析的网络模型设置如下：

[0020] 1)所有的传感器节点及信标节点都随机分布在50m×50m的正方形区域内；

[0021] 2)信标节点的数目N不少于5，每个信标节点均含有自身的ID号和位置信息，所有节点均具有计算能力和测距能力；

[0022] 3)传感器场中没有障碍物，因此位于通信半径范围之内的所有节点均可实现通信；

[0023] 4)在IACT算法中，权重值排序后选取的三边测量组合数为m＝20；

[0024] 5)在算法中，每次通信半径选择为

[0025] 6)随机测距噪声标准差设定为测距的20％。

[0026] 在仿真中，研究了未知节点的平均可侦测信标节点数对节点定位误差的影响。为了保证仿真结果的可靠性，两个仿真均运行1000次，然后求出定位误差的平均值。

[0027] 在仿真研究中，利用EL作为定位误差大小的评价标准，EL由下式计算：

[0028]

[0029] 式中，(IX，IY)和(Xactual，Yactual)分别是未知节点的估计位置和实际位置。为便于比较，所有的定位误差均为绝对误差。

[0030] 1)可侦测信标节点数变化对定位误差的影响

[0031] 在第一个仿真方案中，该仿真分析了可侦测信标节点数变化对定位误差的影响。如图2所示，CBACT算法不受可监测信标节点的影响，这意味着本算法可明显降低网络对信标节点密度要求。IACT算法随着可侦测节点数增加，定位误差减小，当到达某一值时，定位误差趋于稳定。IACT算法的临界转变点是7。当信标节点不规则布置时，仿真也能得到类似的结论。和IACT算法相比，CBACT算法误差值小且相当稳定。显然，尽管选择权重节点的方法不同，但是，同样选择了足够的权重三角形来进行位置节点的定位。因此，具有非常好的定位精度。

[0032] 2)测距噪声变化对定位误差的影响

[0033] 第二个仿真方案研究了测距噪声对定位误差的影响。这时平均可侦测信标节点数设为9。两种算法的定位精度与测距噪声之间的关系如图3所示，Centroid算法的定位误差和测距噪声没有明显的关系。CBACT算法、IACT算法和Lateration算法都是随着测距噪声的增加，误差也在增加，但CBACT算法的定位误差明显小于后两者。即CBACT算法具有更好的鲁棒性。

[0034] 3)CBACT算法和IACT算法误差的比较

[0035] 当测距噪声为20％时，对CBACT算法和IACT算法的定位误差的比较(如图4所示)。和IACT算法相比，CBACT算法受可监测信标节点个数的影响不大。

[0036] 针对IACT算法存在的计算复杂性问题，本发明提出一种低计算复杂性的定位算法——基于圆形的循环三边组合测量法。通过使用更为简单的高权重三角形选择方法，该算法减少了IACT算法中的三角的权重运算，在不影响定位精度的前提下，将计算复杂度由3 2
n 降到了n。此外，本算法定位时的通信开销与IACT算法的相似。因此，和IACT相比，CBACT在没有降低定位精度的前提下进一步降低了节点的能量消耗。
(四)附图说明

[0037] 图1是算法复杂性比较；

[0038] 图2是可侦测信标节点数对定位误差影响；

[0039] 图3是测距噪声变化对定位误差影响；

[0040] 图4是CBACT算法和IACT算法误差的比较。(五)具体实施方式

[0041] 下面结合附图举例对本发明做更详细地描述：

[0042] 一种基于圆形的权重三角形选择方法的循环三边组合测量法，它包括如下具体步骤：2

[0043] 1.任选两个节点A和B( 种选择选择方案)，求线段AB的边长a，并计算a ；

[0044] 2.计算x·AB(x＝cotα，α为权重三角形的最小角，α＝arc cot(1.5)，x在节点布放前根据定位精度设定)；

[0045] 3.重复1和2步，计算所有的边( 条边)的平方，和所有的x·AB；

[0046] 4.任选三个节点A、B和C( 种选择方案)，分别对应边a，b和c，其中a是最短边；

[0047] 5.如果a2+c2-b2＞0和a2+b2-c2＞0且b≤xa，则三角形ΔABC是一个具有较大权重的三角形；

[0048] 6.计算权重多边形的一个顶点；

[0049] 7.重复步骤4、5和6，计算所有的权重多边形的顶点；

[0050] 8.利用权重重心法计算l边形(总计选出l个满足条件的高权重三角形)的权重重心位置，即未知节点的估计坐标值：