基于改进四边测距算法的智慧农业无线传感器精确定位

陈洪涛+孙云娟

摘要：为提高智慧农业中无线传感器目标定位的精度，采用改进四边测距算法。首先通过4个查询节点坐标构造与信标节点坐标的线性方程，为兼顾定位区域其他信标节点定位误差，对信标节点的坐标误差求均值；随后未知节点到信标节点的距离采用牛顿迭代求精；最后对邻居位置相对不集中的节点进行排除，并且给出了算法流程。试验仿真显示，在信标节点比例增加的情况下，该算法比其他算法的定位误差下降速度快，定位误差与其他算法间隔比较大，而且变化幅度较小，定位性能趋于稳定。

关键词：智慧农业；无线传感器；精确定位；四边测距；迭代；定位误差；阈值

中图分类号： S126；TP212.9文献标志码： A文章编号：1002-1302（2017）17-0234-03

在智慧农业监测中，使用飞行器将几百个甚至几千个传感器随机抛撒到监测区域，便于获取环境信息，但是对获取的监测信息需要附带相应的位置信息，在大多数情况下，无线传感器随机布放的环境不是在二维区域中，而是在复杂多变的三维区域中，传感器节点取得的信息只有与自身位置相结合才有意义，因此三维区域的无线传感器节点定位应用价值较高[1]。

传统的无线传感器三维定位算法有Landscape-3D节点定位算法，该算法在未知节点之间无需通信，减小了通信开销[2]，但是需定位辅助设备，同时每个节点需要存储大量的观测信息；基于球壳交集的三維定位算法仅对信标节点进行2次广播，从而降低了通信开销，延长了网络生存期[3]，但是定位覆盖率、定位精度受信标节点密度影响较大，从而加大了节点的成本，实用性较差；Costrained 3D节点定位算法能够将未知节点转化为信标节点来对距离相对更远的未知节点进行定位[4]，但是会产生误差累积；APIT-3D算法不要求节点移动，能够高度近似实现定位，避免了大量数据向中心节点传输而造成的能量损耗[5]，但是要求定位区域和未知节点与信标节点相邻，该算法要求较高的信标节点密度；Centroid-3D算法只需要用三维坐标值替代二维坐标值即可[6]，但是减小定位误差却不太明显，甚至还有使其恶化的可能。

本研究采用改进四边测距算法，首先通过4个查询节点坐标构造与信标节点坐标的线性方程，为兼顾定位区域其他信标节点的定位误差，对信标节点的坐标误差求均值；接着未知节点到信标节点的距离采用牛顿迭代求精；最后对邻居位置相对不集中的节点进行排除，并且给出了算法流程；试验仿真显示，在信标节点比例增加的情况下，本研究算法比其他算法的定位误差下降速度快，定位误差与其他算法间隔比较大，而且变化幅度较小，定位性能趋于稳定。

1测距定位过程

1.1基于四边测距算法模型

在使用节点进行定位时，未知节点附近的信标节点数量往往多于3个，在三边测距的基础上，再添加1个信标节点参与定位，采用未知节点周围较近的4个信标节点来进行质心计算，四边测距法示意见图1。

设4个查询节点的坐标分别为（x1，y1，z1）、（x2，y2，z2）、（x3，y3，z3）、（x4，y4，z4），它们到待测节点的距离分别为d1、d2、d3、d4，待测节点的坐标为（x，y，z），那么有：

（x-x1）2+（y-y1）2+（z-z1）2=d1

（x-x2）2+（y-y2）2+（z-z2）2=d2

（x-x3）2+（y-y3）2+（z-z3）2=d3

（x-x4）2+（y-y4）2+（z-z4）2=d4。（1）

则有：

x

y

z=12x1-x4y1-y4z1-z4

x2-x4y2-y4z2-z4

x3-x4y3-y4z3-z4-1x21-x24+y21-y24+z21-z24+d24-d21

x22-x24+y22-y24+z22-z24+d24-d22

x23-x24+y23-y24+z23-z24+d24-d23。（2）

将4个节点扩展到m个：

（x-x1）2+（y-y1）2+（z-z1）2=d1

（x-x2）2+（y-y2）2+（z-z2）2=d2

（x-xm）2+（y-ym）2+（z-zm）2=dm。（3）

从首个方程向下分别减去最后1个方程，并利用线性方程AX+M=B表示：

X=x

y

z

A=（x1-xm）（y1-ym）（z1-zm）

（xm-1-xm）（ym-1-ym）（zm-1-zm）

B=x21-x2m+y21-y2m+z21-z2m+d2m-d21

x2m-1-x2m+y2m-1-y2m+z2m-1-z2m+d2m-1-d21。（4）

式中：M为m-1维随机向量。根据标准最小均方差估计方法，满足M=B-AX的最小值，E（X）=‖X-AX‖2得最小值时的X=（ATA）-1ATB为位置节点坐标。

利用坐标误差对未知节点的测量坐标进行校正，通过校正减小各种不利因素对定位结果的干扰[7]，信标节点的坐标误差：

exi=xi-xci

eyi=yi-yci

ezi=zi-zci。（5）

式中：xi、yi、zi为第i个信标节点x、y、z的实际值；xci、yci、zci为第i个信标节点x、y、z方向计算值；信标节点坐标误差（exi，eyi，ezi）仅表示所在定位区域该点的定位误差，为兼顾定位区域其他信标节点的定位误差，对信标节点的坐标误差求均值：

ex=14∑4i=1exi

ey=14∑4i=1eyiendprint

ez=14∑4i=1ezi。（6）

式中：（ex，ey，ez）是4个信标节点所组成区域的定位误差。最终未知节点坐标（x′，y′，z′）：

x′=x+ex

y′=y+ey

z′=z+ez。（7）

1.2未知节点到信标节点的距离迭代求精

设未知节点l的初始估计位置（xel，yel，zel）到信标节点（x，y，z）距离计算公式如下：

dl=（x-xel）2+（y-yel）2+（z-zel）2。（8）

得出对应估计距离为del，泰勒级数展开式：

dl=del+x-xeldelΔx+y-yeldelΔy+z-zeldelΔz+εl。（9）

式中：Δx，Δy，Δz为相对偏差。将未知节点与4个以上信标节点的距离所得的εl采用牛顿迭代，∑lεl2取最小值的解（Δx，Δy，Δz）与（xel，yel，zel）相加即可，把相加结果作为下次的（xel，yel，zel），多次迭代直到满足定位阈值要求[8-10]。

1.3数据优化

通过迭代计算目标函数的最小值把未知节点的坐标优化[11-12]，假设节点j（xj，yj，zj）到未知节点i的距离函数如下：

dji=（xj-xi）2+（yj-yi）2+（zj-zi）2。（10）

包含噪聲信息的距离值为d⌒ji，优化目标函数如下：

d′ji=1N∑Ni=1（dij-d⌒ji）2。（11）

式中：N为未知节点数。在三维空间需要较多的节点才能满足空间测距定位，对某个未知节点可能存在多个邻居信标节点，但是估计的时候仅需要任意4个即可，因此存在多估计的可能性，对于估算到的未知节点的一系列位置需要进行过滤。

定位阈值dth：

dth=3L3×A3/（S×P×43πR3）。（12）

式中：L为空间立方体边长；A为每个未知节点定位需要的平均信标节点数；S为网络中节点总数；P为信标节点的比例；R为节点通信半径。

2个位置节点坐标的距离小于定位阈值dth，则该位置是可靠位置，否则认为是不可靠位置，不再计算。若未知节点周围有5个传感器位置坐标分别为（x1，y1，z1）、（x2，y2，z2）、（x4，y4，z4）、（x5，y5，z5）、（x6，y6，z6），为了减少数据误差 ，则本研究将这5个位置构成的质心x1+x2+x4+x5+x65，

y1+y2+y4+y5+y65，z1+z2+z4+z5+z65作为未知节点的位置估计。

假如很多估计位置比较集中，只有少数比较分散，那么这几个少数位置是不可靠估计，其他认为是可靠节点。如图2所示，假设笔者得到未知节点的7个估计位置：1、2、3、4、5、6、7，可以看出，1、2、4、5、6的邻居位置相对集中，3、7位置离这些邻居位置较远，如果排除3、7位置的统计，则估计的位置必定在包括1、2、4、5、6这5个点的圆内，误差小；不排除则使估计的位置范围扩大。对于只有2个位置估计的，不进行过滤，取这2个估计位置连线的中点作为节点的估计位置。

为了减少目标位置解的数据误差，采用平均融合方法对数据进行优化：

X=1M∑Mi=1Xti。（13）

式中：X为由多部传感器组网形成最终融合定位估计；M为可靠传感器数量。

1.4算法流程

算法流程如下：（1）定位空间初始化；（2）通过最小均方差估计方法计算未知节点与信标节点距离；（3）去除不可靠距离估计；（4）未知节点牛顿迭代求精，若满足定位阈值要求转至步骤（5），否则转至步骤（2）；（5）输出定位结果。

2仿真试验

仿真试验构造了边长为1 000 m的正方体三维空间试验区域，面积为1 000 m×1 000 m，该空间区域内随机投放了200个节点，其中信标节点比例控制在10%～30%，信标节点的通信半径为30 m，未知节点通信半径为20 m，节点一经部署，位置不再变化，程序采用Matlab实现。

2.1信标节点数量、通信半径对定位误差影响的对比仿真

定位精度通过平均定位误差与节点的通信半径的比值来衡量：

Rerror=∑ni=m+1（Xiest-Xireal）2（n-m）×R。（14）

式中：Xiest、Xireal分别为未知节点的估计值、真实值；Rerror为定位误差；n、m分别为节点总数、信标节点数；R为节点通信半径。

图3给出本研究算法与其他算法定位精度对比分析，试验结果均是15次蒙特卡罗独立仿真平均值。

在信标节点数量相同的情况下，本研究算法与其他算法相比，平均定位误差下降明显，各种算法均随信标节点数的增加，定位误差呈下降趋势，其中，在信标节点分布比例为25%时，本研究算法定位效果最好，归一化平均误差下降40%以上；随着信标节点比例的增加，本研究算法的定位误差下降速度最快，并且定位误差与其他算法间隔比较大，定位误差最小，定位精度较高；同时随着通信半径的增加，由于通信半径增加后导致节点接收到的数据量增多，对节点间跳数估计准确性降低，但是本研究算法定位误差降低幅度较其他算法小。

2.2定位误差与定位时间关系仿真

图4的试验结果是15次蒙特卡罗独立仿真平均值，可以看出，定位误差随着定位测试时间的变化而不断变化。在刚开始5 s内，各种算法定位误差均为最大，本研究算法整体定位误差比其他算法低，并且变化幅度较小，定位性能趋于稳定，定位误差范围在1～3 m之间，在一定程度上提高了定位精度，对环境具有较好的适应性。

3总结

本研究采用改进四边测距算法对无线传感器目标定位，endprint

通过4个查询节点的坐标构造与信标节点的线性方程，根据标准最小均方差估计方法确定位置节点坐标，未知节点到信标节点的距离采用牛顿迭代求精，对邻居位置相对不集中的节点进行排除。试验仿真显示，随着信标节点比例的增加，本研究算法的定位误差下降速度最快，并且定位误差与其他算法间隔比较大，定位误差最小，定位精度较高。因此，本研究可为智慧农业无线传感器精确定位目标提供一种新思路。

参考文献：

[1]彭泓，赵阳，夏天鹏. 基于优化RSSI精度的WSN加权质心定位算法[J]. 计算机工程与应用统，2015，51（21）：88-91.

[2]Lovett A，Appleton K，Warren-Kretzschmar B，et al. Using 3D visualization methods in landscape planning：an evaluation of options and practical issues[J]. Landscape and Urban Planning，2015，142（SI）：85-94.

[3]Jiammeepreecha W，Chucheepsakul S，Huang T. Nonlinear static analysis of an axisymmetric shell storage container in spherical polar coordinates with constraint volume[J]. Engineering Structures，2014，68（6）：111-120.

[4]Liu Y，Pottmann H，Wang W P. Constrained 3D shape reconstruction using a combination of surface fitting and registration[J]. Computer-Aided Design，2006，38（6）：572-583.

[5]Butzke D，Hurwitz R，Thiede B，et al. Cloning and biochemical characterization of APIT，a new l-amino acid oxidase from Aplysia punctata[J]. Toxicon，2005，46（5）：479-489.

[6]Wang L. Multi-band multi-centroid clustering based permutation alignment for frequency-domain blind speech separation[J]. Digital Signal Processing，2014，31（5）：79-92.

[7]吳君钦，卢陶. 基于RSSI测距的无线传感器网络定位算法[J]. 微电子学与计算机，2014，31（5）：49-52.

[8]冯向科，沈雪梅. 基于WSN定位的Euclidean算法改进研究[J]. 科技通报，2013，29（2）：124-126.

[9]胡中栋，谢金伟. 基于山区地形的无线传感器网络三维定位机制[J]. 传感技术学报，2015，28（3）：408-411.

[10]周礼争，唐瑞，张乙竹，等. 无线传感器网络中APIT-SC三维定位算法[J]. 传感器与微系统，2015，34（7）：104-106.

[11]葛斌，郑建宝，韩江洪. RSSI辅助的三维空间坐标四面体质心定位算法[J]. 计算机科学，2015，42（4）：81-84.

[12]廖兴宇，汪伦杰. 基于UWB/AOA/TDOA的WSN节点三维定位算法研究[J]. 计算机技术与发展，2014，24（11）：61-64.王旭，孙兆军，王正，等. Green-Ampt入渗模型在龟裂碱土改良过程中的应用[J]. 江苏农业科学，2017，45（17）：237-240.endprint