农田环境无线传感器网络无锚节点定位算法

1、农田环境无线传感器网络无锚节点定位算法*郭建全，赵伟，黄松岭（清华大学电机系电力系统国家重点实验室北京100084）摘要：无锚节点定位算法不需要添加额外硬件，无需锚节点或少量参考节点，仅利用自身的无线收发器即可实现整个网络的节点定位，使定位成本大大降低，是解决由大量廉价节点组成大规模网络定位问题的较好方法。以农田应用为背景，提出一种无锚节点定位算法。该算法从普通节点中选取基准节点以形成坐标系，其他未知节点根据自己到基准节点的距离计算出自身坐标，最终得到所有节点的相对位置。还以实测求平均方法解决了无锚节点定位算法的累积误差问题。算法具有分布式特点，实现过程简单，实用性强。关键词：无线传感器网络；

2、无锚节点定位；跳数梯度；累积误差中图分类号：TP393.05文献标识码：A国家标准学科分类代码：510.99Anchor-free location algorithm for wireless sensor networksin the application of farmland Guo Jianquan, Zhao Wei, Huang Songling（State Key Lab of Power Systems, Dept. of Electrical Engineering, Tsinghua University, Beijing 100084, China）Abstract：

3、Anchor-free location algorithm needs no anchor or only a few of reference nodes and realizes the location of the nodes in wireless sensor networks only using the wireless receiver equipped on each node without adding any other equipment or hardware, which is very applicable to the large scale wirele

4、ss sensor networks made up by many low-cost nodes. This paper proposes an anchor free location algorithm taking farmland application as a background. The algorithm first chooses some reference nodes as “anchors” from ordinary nodes according to certain criteria to form a coordinate system, based on

5、which other unknown nodes can calculate their coordinates. The algorithm calculates the average hop distance according to the actual size of the farmland and solves the problem of the accumulated error. The algorithm proposed in this paper has distributed feature, and is easy to be implemented and a

6、pplicable.Key words：wireless sensor network; anchor-free location; hop gradient; accumulated error1引言收稿日期：2008-10Received Date：2008-10 *基金项目：国家高新技术发展规划“863”课题基金 (2007AA10Z241) 资助项目节点定位技术是无线传感器网络重要的服务支撑技术。由于无线传感器网络节点成本、功耗和硬件条件的限制，如何实现低成本、低功耗和高精度定位是无线传感器网络技术的研究重点之一。根据定位算法是否需要通过物理测量获取节点间的距离或角度信息，可将定位算法

7、分为基于测距和非基于测距的定位算法。基于测距的定位算法一般利用测量得到节点相互间的距离或角度信息来实现位置计算，测量距离的方法有1：利用信号达到的时间差（TOA）、利用两种不同信号到达的时间差（TDOA）、利用角度（AOA）及利用无线信号的衰减度（RSSI），其中，RSSI法无需添加额外硬件，只利用自身携带的测量无线电信号强度指示功能，据经验公式计算两节点间的距离，但误差较大；TOA、TDOA和AOA方法均需依赖大量昂贵且消耗能量的硬件。非基于测距的定位算法是通过一定方法估计节点间的距离或确定包含未知节点的可能区域，实际上，仍需要被定位节点与参考节点的距离信息，只不过距离信息是通过其他方式间接

8、取得的。典型的非基于测距的定位算法有质心算法2、APIT算法3、DV-Hop算法4、Amorphous算法5-6等。质心算法和APIT算法依赖高密度的锚节点，使每个传感器节点都能接听几个锚节点的信号。DV-Hop算法和Amorphous算法依靠洪泛协议，由到锚节点的跳数信息计算距离。对于少锚节点和无锚节点的传感器网络，因大部分节点没有能力与足够数量的锚节点直接通信，如何有效实现节点定位极具挑战性。现有的无锚节点定位算法有AFL算法7、KPS算法8和ABS算法9。AFL算法是无锚节点、完全分布式的定位算法，它先用启发式原理得到一个无折叠布局，使之结构大致接近于实际布局图，然后基于质点弹簧模型优化

9、算法修正和平衡定位误差，使对应于位置的能量函数达到最小。KPS算法是根据事先假定的节点分组配置模型，每个节点观察邻节点所在组的成员节点个数，并根据预先假定的分组配置模型实现自身定位。ABS算法则是利用节点间的通信连接关系，按顺序一次计算一个未知节点坐标，不断经修正和冗余计算减少定位误差。但这3种无锚节点定位方法均还存在问题。如：AFL算法并未明确给出单跳跳距的计算方法；KPS算法是基于一个分组布置的概率模型前提；而ABS算法需已知4个锚节点坐标，或要事先设定4个节点的坐标。而且，这3种算法由于各自固有的特点，都存在严重的误差累加现象，故往往导致定位结果不可用。应用无线传感器网络实现农业典型危害

10、动物的数字化声防，对提高我国农业的精细耕作、集约化经营水平具有重要现实意义。针对农田环境的特殊应用背景，本文提出一种适用于大规模农田环境的无锚节点定位算法。该算法首先从大量同质传感器节点中选出基准节点，根据农田尺寸信息赋予基准节点相对坐标值，建立相对坐标系；然后以每个基准节点为“锚节点”，利用改进的Amorphous算法得到各节点到每个基准节点的距离；最后，每个未知节点计算出自己在这个坐标系中的坐标。该算法是一种分布式定位算法，实用性强、实现简单、定位精度较高，解决了农田环境中无线传感器网络节点的低成本、高精度定位问题。2本文算法要解决的关键问题在没有锚节点存在情况下，为实现节点定位，首先要选

11、择一些节点作为“锚节点”。为区分于其他基于已知锚节点的定位算法，本文将从普通节点中选出的“锚节点”称为“基准节点”。利用基准节点建立坐标系，其他节点可根据到基准节点的距离得到自身在此坐标系中的位置。对于常见的矩形农田，首选其4个角的节点作为基准节点。如何通过算法实现基准节点的选取，是本文首先要解决的问题。无锚节点定位算法简单易行，无需额外添加硬件，但与其他有昂贵硬件支持的定位算法相比，其定位精度不高。产生较大误差的最主要原因是误差累加严重。在Amorphous算法5-6,10中，通过建立以基准节点为原点的跳数梯度场得到各节点到基准节点的跳数距离（式（1），跳数距离乘以平均跳距（式（2）即可得到

12、以长度单位衡量的距离值。 (1) (2)式中：si为局部平均跳数；表示节点i与基准节点间的最小跳数；表示节点i信号辐射半径内的所有节点。为平均跳距；r为通信半径；为平均邻居节点数（通信半径内的平均节点数）。式（2）的计算过于复杂，难以在节点上实现。另外，通信半径r是一个与节点周围环境有关的量，不同周围环境（如土壤湿度、植被、气象条件等）对应着不同的值，故用经验公式计算无疑会出现误差；再有，节点局部密度的变化也会产生误差。这些误差均会随跳数距离的增加而累积增大，往往使最终计算结果不可用。但根据农田尺寸，可利用算法得到较精确的平均跳距，从而使计算精度大大提高。得到各节点到基准节点的距离后，由基准节

13、点的坐标即可求出各节点自身的坐标。由于定位算法得到的各节点到基准节点的距离值存在误差，因此节点最佳坐标的求取是一个寻优过程。综上所述，本文定位算法需要解决的关键问题有3个：1)基准节点的选取；2)平均跳距的求取；3)未知节点坐标的求取。3基准节点的选取对于常见的矩形农田，其4个角的节点作基准节点是首选。本文利用节点到已有基准节点的跳数距离值来选择新的基准节点。如图1所示，从边界上某一点（通常为sink节点，如图1中的A点）触发开始，发送导标信号，执行距离矢量路由交换协议，将建立以节点A为“源”，距离这个节点的跳数值递增的跳数梯度场。在跳数梯度场中，位于对角的C点显然属于跳数值最大的那一环的节点

14、集合中。因此，还需根据一定准则从这个集合中选出合适的节点作为基准节点。基准节点B、D也可按照同样道理选出。图1基准节点选取示意图Fig.1 Selection of the reference nodes以图1为例，基准节点C满足关系，此处，s的含义与式（1）同，i为网络中的任意节点。由于每个节点只能得到邻居节点的信息，如何利用局部信息实现整体目标是需要解决的问题。假定传感器节点随机均匀分布，在给定面积为a的范围内存在k个节点的概率满足泊松分布：式中：，表示节点密度，即节点总数N除以总面积S。易知，在给定面积a中分布的节点个数的期望值为a。因此，如果节点位于矩形农田的角上，其邻居节点个数的期望

15、值为，r为通信半径。于是，可设定一个阈值，包含C的节点集合中的节点满足关系： (3)通常，满足式（3）的节点不止一个。必须通过sink节点来确定哪个才是所要的基准节点。实现的方法是，当节点发现自己满足式（3）时，首先跟邻居节点比较跳数值，以确保自己的跳数值最大。然后，再发送一个包含节点编号和平均跳数值的信息给sink节点。sink节点将比较接收到的所有信息中的值，取其最大的一个作为基准节点C，并将包含的确认信息广播到网络中。同理，可以选出基准节点B和D，基准节点B满足且；基准节点D满足。4平均跳距的确定平均跳距的计算精度直接影响最终定位结果的精度。由第3节可知，基准节点选取过程中，已得到了基准

16、节点之间以跳数表示的距离值，现在只需利用网络的尺寸大小，直接得到平均跳距，避免了用经验公式计算造成的误差累积，以提高定位精度。但是，对于在给定面积上分布的节点，选取的基准节点的间距是节点分布密度的函数，因此，需首先求出基准节点间距与节点分布密度之间的关系。以图2为例，节点P、Q为选取的基准节点，在基准节点的选取过程中，已得到了SpQ的值，下面求取节点P、Q之间距离PQ的表达式。图2 对角线基准节点间距期望值求取原理示意Fig. 2 Calculation of the expected distance between two diagonal reference nodes由基准节点的选取过

17、程可知，基准节点P、Q为最靠近“角”的节点，即在它们与“角”之间存在一个没有节点分布的区域（如图2中的近似为三角形的CEF阴影部分）。对于节点分布密度为（节点数/单位面积）的二维均匀分布网络，由概率知识可知，在给定面积为S的范围内有k个节点的概率满足泊松分布，分布概率可表示为：设二维平面内没有任何传感器节点存在的面积为。的概率分布可表示为：F(s)=Pr(S<s)=Pr(在s上有1个节点)+Pr(在s上有2个节点)+=1-Pr(在s上有0个节点)=1-e-s计算的数学期望：由于对角线基准节点之间距离较远，可按三角形来处理。因此，由于梯度形成的形状，由基准节点的选取过程和几何相似关系（理论

18、推导过程略）可知，三角形的形状跟矩形的尺寸有关，如果，有。因此可求出：，从而有：可求出平均跳距：需要说明，从的推导过程可知，对传感器节点均匀分布的情况，这里所得平均跳距是统计意义上的期望值。5计算节点坐标各节点在得到与基准节点之间的距离值后，开始求取自身的坐标值。坐标的求取过程是一个寻优过程。设待求节点的坐标为，节点利用跳数梯度算法估得到的到基准节点的距离为，实际距离为；则节点的坐标的最优估计值应满足：节点i的坐标的最优值可用牛顿迭代法求取，每次迭代，坐标值更新的大小正比于总平方差对坐标分量的偏导：坐标的更新公式为：和式中：为迭代步长。迭代初始值的选择非常关键，它直接关系着迭代是否收敛和迭代的

19、快慢。如图3所示，假定节点E到基准节点X、Y、Z和W的距离分别为d1、d2、d3和d4，设基准节点X为坐标原点，因为，迭代的初始值可按几何比例关系，求平均值得到： (4)图3未知节点坐标的计算Fig. 3 Calculation of the coordinates of the unknown nodes显然，选择的初始值已经很接近真实值，只要进行较少次迭代，即可达到满意的精度。6定位算法的实现过程本文提出的无锚节点定位算法整个实现过程的主要步骤为：步骤 1 ：各个节点初始化变量。与本文算法相关的主要变量有：IfRefNode:节点状态（是否是基准节点），初始化值为0（表示普通节点）。Coo

20、rdinate1×2：节点的坐标，各元素初始化值为0。HopToRef1×5：到sink节点及各基准节点的平均跳数值。各元素的初始化值要足够大。SingleHopDis: 平均跳距，初始化为0。CorOfRef4×2:4个基准节点的坐标，各元素初始化值为0。DisToRef1×4: 到sink节点及其4个基准节点的距离，各元素初始化值应足够大，以便在跳数梯度形成过程中满足更新条件。步骤 2 ：sink节点触发定位过程和第一个基准节点（假定为节点n1）的选取。sink节点广播一个跳数初值为1的信标，邻居节点收到此信标后将跳数值加1，并转发给它们的邻居节点。

21、每个接收到此信标的邻居节点会把跳数加1，并向邻居节点发送包含跳数加1后的信标。每个节点只记录跳数的最小值而忽略包含较大跳数值的信标，如此，便阻止了信标的反向传播。照此进行下去，会形成从基准节点向外扩展的跳数梯度场。最终，节点保留了到sink节点的最小跳数值。然后，所有节点收集邻居节点的最小跳数值，并根据式（1）计算出平均跳数值，保存到HopToRef1×5的第1个元素中。根据第2节方法选出第1个基准节点n1，并赋予坐标值。节点n1将变量IfRefNode赋值为1，在下一轮基准节点选取过程中，将充当已有的基准节点，建立跳数梯度场。步骤 3：按照第2节中的方法选出其他3个基准节点n2、n

22、3 、n4。 步骤 4：根据第3节中的方法计算出平均跳距，并广播到网络中，这个值将被保存到各节点的变量SingleHopDis中。步骤 5：计算未知节点的坐标。未知节点根据HopToRef1×5和SingleHopDis计算出自己到各基准节点的距离值，保存到变量DisToRef1×4中，根据第4节中的方法计算出自身的坐标，将其存放在变量Coordinate1×2中，整个定位过程结束。7仿真实验7.1各节点到基准节点距离的求取利用MATLAB仿真，设1 000个传感器节点均匀分布在1 000 m×1 000 m的农田面积上。首先，基准节点建立以自身为“源”

23、的跳数梯度场，各节点利用式（1）计算出它们到基准节点的以跳数表示的距离；然后，利用两个基准节点间的跳数距离，根据网络的尺寸得到较精确的平均跳距。各节点到基准节点的距离，即可通过跳数值乘以平均跳距得到。图4（a）为以坐标原点为基准节点建立的跳数梯度场示意图，跳数值为奇数次的节点用“·”表示，为偶数次的用“*”表示。跳数梯度场为以基准节点为圆心，向外环状扩展的形状，每个节点都位于某个环上，如果某个节点位于第h跳的环上，则除边界节点外，它的通信半径内一般都包含有h-1跳、h跳和h+1跳的节点。利用式（1）可计算出各节点到基准节点的平均跳数。图4（b）是平均跳距用式（2）计算得到的到基准节点

24、的测距效果。图4（c）为利用本文提出的算法，直接求取平均跳距后的效果。节点位置的计算值由“·”表示，其上连接的短线，表示计算的位置与实际位置间的误差。为更清晰地说明问题，图4（b）和图4（c）均只考虑节点到基准节点之间距离的变化，即假定所有节点只在到基准节点的连线方向上移动。可以看出，用本文方法算出的平均跳距，消除了由于周围环境影响和局部节点密度不均匀造成的累计误差，得到的测距效果明显优于理论公式计算的结果。(a)跳数梯度场的建立过程(a)The process of establishing the hop gradient(b)用理论公式计算平均跳距的测距效果(b) The av

25、erage hop distance calculated by theoretical formula(c)用本文方法计算平均跳距的测距效果(c) is the average hop distance calculated by the proposed algorithm图4各节点到基准节点距离的求取Fig.4 Calculation of the distance between each nodeand the reference node.图5是不同节点密度（用通信半径内平均节点个数N_averager表示）下，用理论公式计算和本文方法计算得到的平均测距误差的对比，平均测距误差为所

26、有节点的测距误差的平均值。图5用理论公式和本文方法得到的平均测距误差对比Fig.5 Comparison of average calculated distance errors usingtheoretical formula and the proposed algorithm误差的总趋势是节点密度越小误差越大，这是由算法的固有特性决定的，可见，在任何情况下，本文方法的平均测距误差均小于理论公式计算的结果。7.2计算未知节点的坐标采用与7.1节相同的仿真环境，图6为按照第4节中的方法，经过100次迭代的计算结果，迭代初始值按照式（4）计算。“·”表示节点位置的计算值，连线表示节

27、点位置的计算值与实际值之间的误差。计算结果表明，总的平均定位误差为节点通信半径的11%。可以看出，边界处的节点相对于中间位置的节点而言，定位误差要大些。这是因为，各节点定位误差的大小不但与节点到各基准节点的测距误差大小有关，而且还与基准节点自身坐标的误差及各节点与基准节点的相对位置有关。图6本文算法得到的定位效果.Fig.6 The effect of location using the proposed algorithm如果传感器节点分布面积给定，定位误差主要受节点个数多少和节点通信半径大小影响。假定定位误差以所有节点的计算位置到其实际位置之间距离的平均值表示。改变仿真环境中节点的个数和

28、通信半径的大小，节点个数分别取值为1 000、950、800、750、700450、400、300、200，总共13组；通信半径大小从130递减到30，间隔为10，总共11组。得到的定位误差如图7所示。图7中，不同深浅度颜色对应着不同大小的误差等级。可以看到，节点个数越多，通信半径越大，总误差越小；反之误差越大。图7中左下角的区域和右上角近似三角形的区域之间有一条明显的分隔带。如果用辐射半径内节点的平均个数表示节点的密度，这个分隔带对应的节点密度约为5，即通信半径内节点个数低于5时误差会明显增大。这是由于当局部节点分布不均匀时，如果节点密度过低，一些节点就会与其他节点失去联系（特别是在角落附近

29、），致使在跳数梯度的建立过程中出现较大局部误差。因此，为得到较满意的计算精度，在利用本文算法实现节点定位过程中，应保证通信半径内的平均节点个数大于5。图7总的平均误差特性Fig.7 The characteristic of the total average error8结论本文以农田应用为背景，提出一种大规模网络无锚节点定位算法。该算法首先从网络的所有普通节点中选取基准节点，再利用所选基准节点建立坐标系，利用跳数梯度场得到未知节点到基准节点的距离，未知节点根据到基准节点间的距离算出自身在网络中的相对位置。为解决无锚节点定位算法误差累积问题，针对农田的特殊情况，本文采用实测求平均法得到平均跳

30、距，提高了计算精度。本文提出的定位算法具有分布式的特点，具有较强的实用性和可扩展性，非常适用于由大量低成本节点组成的大规模无线传感器网络。本文提出的定位算法虽以农田环境为背景，但其基本思想在其他应用场合仍然具有借鉴价值。如：对于不同的网络形状，只要恰当地选择基准节点以建立适合于该网络形状的坐标系，即可按照本文的方法得到其他未知节点的相对坐标。另外，必须指出，本文提出的定位算法未考虑障碍物存在的情况。障碍物的存在，可能使得建立的跳数梯度场与没有障碍物时的情况有一定甚至是较大差别，但直觉上，通过分析基于不同基准节点建立的跳数梯度场之间的约束关系，仍然可以计算未知节点的相对位置，这也是今后值得深入研

31、究的方向。参考文献1 BIAZ S, JI Y. A survey and comparison on localization algorithms for wireless ad hoc networksC. International Journal of Mobile Communications (IJMC), 2005, 3(4): 374-410.2 BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less low cost outdoor localization for very small devicesJ. IEEE Personal Commu

32、nications Magazine, 2001, 7(5):28-34.3 HE T, HUANG G, BLUM B, et al. Range-free location schemes in large scale sensor networksA. Proceedings of The 9th Annual International Conference on MobileComputing And Network (MobiCom 03 )C. San Diego, 2003(3):81-95.4 NICULESCU D, NATH B. DV based positioning

33、 in Ad Hoc networksJ. Journal of Telecommunication Systems, 2003, 22(14): 267-280.5 NAGPAL R. Organizing a global coordinate system from local information on an amorphous computer: Report of AI memoR. MIT Artificial Intelligence Laboratory, 1999.6 NAGPAL R, SHROBE H, BACHRACH J. Organizing a global

34、coordinate system from local information on an Ad hoc sensor networkC. Proceeding of Workshop on Information Processing In Sensor Networks. April 2003: 333-348.7 PRIYANRHA N, BALAKRISHNAN H, DEMAINE E, et al. Anchor-free distributed localization in sensor networksR. Technical Report TR-892, MIT Laboratory for Computer Science, April 2003.8 FANG L, DU W, NING