无线传感器网络633Amorphous

1、6.3.3 Amorphous6.3.3 Amorphous算法算法宿舍：513概念传感器节点是无线传感器网络中的基本组成单位。在无线传感器网络中，节点的位置信息至关重要，没有位置的信息，监测信息就毫无意义。节点定位是无线传感器网络系统布设完成后面临的首要问题。节点定位指根据有限的位置已知的节点来确定无线传感器网络中其他节点的位置，在无线传感器网络的节点之间建立起位置关联关系的定位机制。3 在不定形计算机(Amorphous Computer)上实现的定位算法。 不定形计算机是一种并行计算结构，和智能群（蚁群、鸟群、粒子群等）很相似。 本质上，Amorphous算法是DV-Hop算法的增强，引

2、入了多参考点测量进行估计求精的步骤。Amorphous定位算法4 Amorphous算法思想是利用两节点之间跳段距离代表二者之间的直线距离。分为三个阶段： 第一个阶段，与DV-Hop定位算法相同，未知节点计算与每个信标节点之间的最小跳数； 第二个阶段，假设网络中节点的通信半径相同，平均每跳距离为节点的通信半径，未知节点计算到每个信标节点的跳段距离； 第三阶段，利用三边测量法或极大似然算法，计算未知节点的位置。 Amorphous算法将节点的通信半径作为平均每跳段距离，定位误差大。Amorphous定位算法重新计算平均每跳距离 由于节点随机部署，未知节点与信标节点之间的跳段距离通常不是二者之间的

3、直线距离，采用节点的通信半径作为平均每跳距离，过大估计了跳段距离。利用下式计算平均每跳距离： 其中，r表示节点的通信半径；nlocal表示网络平均连通度，即网络中节点的平均邻居节点数。Amorphous定位算法利用局部跳数平均值代替跳数 未知节点计算与信标节点之间的跳数时，结果都是整数，实验表明这大约增加了0.5个平均跳数的误差。未知节点利用下式计算局部跳数平均值，代替它与信标节点之间的跳数： 其中，nbrs(i)表示未知节点i的邻居节点集合；hi表示节点i与信标节点之间的跳数；hj表示邻居节点j与这个信标节点之间的跳数。Amorphous定位算法Amorphous定位算法 根据平均每跳距离及

4、距各信标节点的局部跳数，计算未知节点距各信标节点的距离： 其中， 为未知节点i获得的平均每跳距离， 则代表未知节点i到信标节点j的最小跳数。Amorphous定位算法采用三边测量法或极大似然估计法进行定位 当未知节点获得了距三个或三个以上信标节点的估算距离，便可以采用三边测量法或极大似然法计算自身位置。 利用最小二乘法对上述方程进行求解，可求得未知节点位置 其中，(x1,y1),(x2,y2),(x3,y3),(xn,yn)对应n个信标节点的坐标，(x,y)为未知节点的坐标，未知节点到各信标节点的距离依次为d1,d2,d3,dn。Amorphous定位算法 这个算法基于经验模型，在试验环境中可

5、以取得较好的效果。 但这个算法假设网络平均连通度nlocal已知，要求在网络部署前离线计算平均每跳距离，网络的扩展性差，而且对信标节点的密度要求高。 累积误差 图一为传感器节点个数为150，随机分布区域为300300(m2)，信标节点比例为17.2%，平均网络连通度为15.3%时，Amorphous定位算法所对应的跳数值与累积误差关系图。 由图1可以看出，随着未知节点与信标节点之间的跳数值的增大，二者间估算距离与真实距离的误差也随之增大。未知节点到达信标节点每增加一跳，便引入不同程度的累积误差。如何减少由于跳数值过大而引起的累积误差，是Amorphous算法要解决的一个问题。缺点分析缺点分析缺

6、点分析缺点分析不良参考节点的引入 在无线传感器网络的定位算法中，有这样一个结论：在未知节点的定位过程中，参与定位的信标节点数目越多，未知节点的定位精度越高。但是在基于跳段距离的定位算法中，这个结论并不总是正确的。缺点分析缺点分析 不良参考节点的引入 图二为信标节点比例为10%，平均网络连通度为10时，Amorphous算法分别采用三边测量法与极大似然测量法的定位性能比较图。其中，横坐标对应节点定位精度，纵坐标为各定位精度以内的节点比例。由图二可知，定位精度在40%（绝大多数应用已满足）以内时，三边测量法对应的未知节点比例大于极大似然法。这说明采用极大似然法进行定位会引入不良信标节点可降低未知节点定位精度。缺点分析缺点分析需要较大信标节点比例 在基于跳段距离的定位算法中，需要较高的信标节点比例，才能获得较高的定位精度。但若信标节点比例太高，又大大增加无线传感器网络的成本。AHLos4算法中将定位成功的未知节点全部转化为信标节点，虽然在一定程度上缓解了该问题，但同时也引入了更大的定位误差。 总总 结结 总的来说，Amorphous定位算法定位精度较好，通信开销、存储开销、计算量和时间复杂性相对较小，并且具有相对好的容错性和自适性，但是该算法仍有些地方需要改进，如它需要预知网络的连通性，网络扩展性差，定位效果受锚节点密