无线节点定位算法研究硕论 - 图文(3)

锚节点（anchor nodes）：也称为导标节点（beacon nodes），网络初始状态自身位置信息已知的节点。

未知节点（unknown nodes）：网络中锚节点以外的其他节点，网络初始状态自身位置信息未知，通过网络与锚节点互联计算获取位置信息。

邻居节点（neighboring nodes）：每个节点的通信范围内节点的集合。 节点度（node degree）：与一节点相邻节点的个数。 跳数（hop count）：一节点到另一节点的跳段的总和。

跳距（hop distance）：从一节点到另一节点的所有跳段的距离和。 上文中提到将定位算法大体有两类，一类是基于测距的定位算法，另一类是基于非测距的定位机制算法，这两种算法的机制有明显的不同，前者必须在已知未知节点与锚节点之间的距离或者角度信息情况下，再进行测量。而后者不是根据距离进行定位的而是由整个网络的连通性等相关信息从而得出节点的位置。

3.2 与距离有关的定位算法分析

2.2.1 基于测距的定位方法

这是常用的定位方法。不过利用这种方法事先要知道两个节点的位置关系的信息，例如距离或角度，其过程大体分为三个阶段：

（1）测距阶段。测量锚节点与其临近已知节点的位置信息角度或距离，在测量所求未知节点到该已知节点距离或角度，进而得到它到锚节点的直线距离。

（2）定位阶段。根据未知节点到与其临近的三个或以上锚节点的距离或角度，利用相关算法即可求出位置节点的坐标；

（3）修正阶段。主要针对阶段（2）所得到的坐标进行进一步求解已到达减小误差的目的。

2.2.2 到达时间（TOA）定位法法

TOA[24]技术是通过测量信号传播时间来测量距离。其实质上是利用速度乘以时间两者的积为距离。利用这种定位方法必须要确保节点有非常精确的时钟。

2.2.3 时间差（TDOA）定位法

TDOA[24]测距是通过计算两种不同无线信号到达未知节点的时间差，再根据两种信号传播速度来计算得到未知节点与锚节点之间的距离。

平面解析几何中定义双曲线法是到两定点的距离差为常数的点的集合，其中这两个定点叫做焦点。TDOA定位同双曲线的几何意义相类似它将两个锚节点设为双曲线的焦点，则未知节点到两锚节点的距离差即为双曲线的实轴，经过测量即可得到未知节点所属的两个以上双曲线方程时，则他们的交点即为未知节点的位置。利用这种方法虽然对时间的同步性要求不高，但仍要求要有准确的计时功能。不过这种方法因为无线传感器网络其传感器节点数量较大其无线通信范围小实现起来并不容易。

2.3 与距离无关的定位算法分析

2.3.1 质心算法

质心算法[9]的中心思想是：未知节点将其信息可以传递到的最大范围内的所有锚节点的几何质心视为自己估计位置。

在该算法中，锚节点每隔一定时间临近的节点广播同一个信标信号，当未知节点在一定时间内所接收到信标信号的数量超过设定值以后，该未知节点则认为它通锚节点建立了连通。

而所谓质心算法则体现在未知节点将其自己的位置确定为所有与之连通的锚节点所组成的多边形的质心。

值得说明的是信标节点中携带着该节点的各种位置信息和标识号等。 该方法较其他算法较简单，同时处理的数量较少，适合于无线传感网络，但利用这种方法需要大量的锚节点。

多边形ABCDE的顶点坐标分别为：A(x1,y1)，B(x2,y2)，C(x3,y3)、 D(x4,y4)、E(x5,y5)，其质心坐标：

(x,y)?[(x1?x2?x3?x4?x5)/5,(y1?y2?y3?y4?y5)/5]。

采用质心定位算法其第一步是要首先确定未知节点所处的区域，然后算出整个区域的质心，将这个质心视为未知节点的位置。在这种算法中，信标节点会定期向其临近节点广播信标分组，而当未知节点所接收到的不同信标节点的信标分组数量超过设定值或是接收时间超过规定值，就确定自身位置为这些信标节点所组成的多边形的质心。

该算法以网络连通性为基础，操作简便，容易实现

2.3.2 DV-Hop算法

DV-Hop算法：锚节点会以泛洪的形式将携带其自身的位置信息和一个初始值为1的跳数的信标在网络中广播出去。当信标被其他节点转发时，它的跳数将会加1。则接收节点只会保存有关该锚节点的跳数最小的信标，将跳数较大的信标舍弃。利用这一方法，网络中所有节点(包括其他锚节点)都获得了到每一个锚节点的最小跳数值。表示了网络中的节点到锚节点A的跳数值。

求一个锚节点到另一个锚节点的实际距离，利用平均每跳的平均估算值乘以从该锚节到另一个锚节点的跳数即可。通过计算可以得到锚节点每跳的平均距离，然后将这个值广播到网络中，则这个值被叫做校正值，一旦其它节点接收到这个值，并可估算其到锚节点的距离。如果是未知节点，其得到3个以上校正值并可利用最小二乘法就可以估算出其自身的位置。

DV-Hop算法同基于测距算法的原理基本相似，不过他们通过不同的方法获得距离，其中DV-Hop算法是通过网络中拓扑结构信息来计算得到的，基于测距算法通过无线电波信号的测量得到的。

DV-Hop算法同基于测距的算法相比不再局限于其节点自己射频所能覆盖区域范围的锚节点的距离，它获其射程以外的锚节点的距离，利用这种方法可以有限提高定位精度。

Sum-dist一个缺点便是当进行多跳传播的时候，节点的测距误差会发生累积效应。这种累积误差会受到网络规模较大小或锚节点数量等因素的影响。Ad-Hoc positioning中将其称为DV-Hop，Robust positioning中则将其称为Hop-TERRAIN。DV-Hop实际上由两波的洪泛组成，第一波洪泛中类似于Sum-dist，节点获得锚节点的位置信息和离锚节点的最小跳数。在第二波洪泛中将跳数信息转换为距离信

息。每个锚节点根据第一波中记录的跳数信息和相距距离，利用式（3-1）估算平均每跳实际距离

?Hopsize?j?i(xi?xj)2?(yi?yj)2?Hopsj?i （3-1）

i式中 (xi,yi)，Hopj为锚节点i和 j(i≠j )之间的跳数。(xj,yj)为锚节点的坐标；锚节点计算完每跳平均距离后，用带有生存期字段的消息分组广播到网络中，未知节点会将收到的第一个每跳平均距离记录下来，并将其转发给临近点。这个策略确保了绝大多数节点从最近的锚节点接收到每跳平均距离值。未知节点接收到平均每跳距离后，在根据其先前记录的跳数，即可算出其到各个锚节点的距离。

DV-Hop算法包括三个步骤。第一步，主要求的锚节点到除图自己以外所有节点的跳数 (distance in hops)。第二步，在完成第一步以后，要计算锚节点到其他节点每跳的平均距离，将这个值作为校正值(correction)将以可控洪泛的形式广播到网络中去。每个节点一旦接受到一个校正值后就不在接受其他的校正值了，之所以不在接受其他校正值视为了确保它是从离它最近的锚节点接受的。第三步，主要利用未知节点所获得与3个或更多锚节点的距离利用三边测量进行定位。

从图3-4我们可以看出，已知锚节点L1与L2，L3为已知锚节点间，它们的距离及跳数从图中可以看出。已知L2的校正值为 (40+75)/(2+5)=16.42。假设未知节点A从L2获得校正值，由此可以得到它到3个锚节点之间的距离分别为L1-3*1.642，L2-2*1.642，L3-3*16.4，通过这三个数再利用三边测量法即可得到节点A的位置。

75m 4A100m 图3-1 DV-Hop算法

2.4小结

进过上面的介绍，我们可以发现现有的定位算法都各有其优缺点。一般而言，与距离有关的定位算法需要增加配备硬件装置，导致所需的能量和成本加大，受环境影响大，通用性差。而与距离无关的定位算法不需要额外的硬件配置，通用行佳，虽然定位精度不如前者，但是在大多数的传感器网络实际应用中，这样的精度是可以满足应用需求的。我们将提出一种改进的粒子群算法，对DV-Hop算法进行优化，以获得更佳的定位精度。

第四章 DV-Hop算法改进的定位技术

4.1 DV-Hop算法的缺陷

(1)下面介绍一下无线传感器网络中的bad节点；

(i)图4-1是第一类bad节点的示意图，节点M为已知节点，其位置坐标为已知，节点N是未知节点，其位置不确定，它可能在N1，也可能在N2、…Nn但它的一跳节点只能是M，则这样的节点N被称为 bad节点。

百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典教育范文无线节点定位算法研究硕论 - 图文(3)在线全文阅读。