姜伟，赵方
北京邮电大学软件学院，北京（100876）
E-mail：
摘要：无线传感器网络是一种全新的信息获取和处理技术，能够实时监测、感知和采集各种环境或监测对象的信息。传感器多节点协调的自身定位是各种应用的基础，论文深入分析比较了在无线传感器网络领域中有代表性的三种分布式定位算法（Bounding box，Euclidean 和Robust position），并在OMNET++平台上作了性能的仿真检验；分别从理论和实际仿真结果上，对各定位算法的性能作了定量分析，并对各算法的应用环境给出了建议；对Robust position算法的改进提出了建议，并对无线传感器网络定位算法的未来研究作了展望。 关键词：无线传感器网络；自身定位；定位；仿真
1. 引言1
近些年来，微电子技术、计算技术和无线通信技术的进步，推动了低功耗多功能传感器的快速发展，使其在微小的体积内能够集成信息采集、数据处理和无线通信等多种功能。
由于传感器节点在部署时的不可控制
性（例如通过飞机撒放），网络中大多数节点位置不能事先确定，而无线传感器网络的大量应用都需要网络中节点的地理位置信息，从而获知信息来源的准确位置。此外，节点的位置信息还可以辅助实现数据路由。 人工部署和为所有网络节点安装GPS 接收器都会受到成本、功耗、扩展性等问题的限制，甚至在某些场合可能根本无法实现，因此必须采用一定的机制与算法实现WSN的自身定位。
由于传感器网络对能耗十分敏感，所以不宜将大量的通信和计算固定于某个或者某
些节点，否则，这些节点的电能会很快耗尽，出现网络的“空穴”。要求要尽量采用分布式的节点定位算法，尽量延长传感器网络的生命期。对定位算法性能的评价标准主要有：定位精度、规模、锚节点密度、节点密度、容错性和自适应性、功耗、代价等。
1本课题得到国家高技术研究发展计划（863）资助（No. 2007AA12Z321）。
论文对定位算法仿真的意义在于能够在尽量接近现实的环境中得出算法性能的数据，进行定量分析，从而得出算法的应用环境和不足之处，以待改进。
论文要通过研究无线传感器网络中典型的分布式定位算法，选择Bounding box，Euclidean和Robust Position三种算法进行实现，并在OMNET++平台上对他们进行仿真比较，研究环境参数（测距误差，锚节点密度，连通度）变化对他们性能的影响。论文最后给出这些算法性能的评估和应用环境的建议，并对算法改进提出建议。
2. 分布式定位算法
总结分布式定位算法，大都分为三个模块：确定未知节点和锚节点间距离模块；计算每个未知节点位置模块；循环精确节点位置模块。首先，未知节点通过基于测距或非测距方法确定其到锚节点的距离；然后，通过到锚节点的距离来计算每个未知节点的位置；最后，对未知节点的位置进行迭代求精，最终所有未知节点报告它们的位置。 分布式定位算法的每个模块中都有几种可选算法。其中确定未知节点和锚节点间的距离模块中可选算法有基于RSSI的测距算法，美国路特葛斯大学（Rutgers University）的Dragos Niculescu[1]等人提出的Euclidean，DV-Hop，DV-distance三种算法；计算未知节点位置模块中可选算法有三
边测量法，多边形算法法，Min-Max 算法；位置求精模块主要有由Savarese [2]等提出的根据所有可获得的节点信息重复执行三边测量或多边形算法过程重新确定节点位置。
2.1 确定未知节点到锚节点距离模块可选算法
在这个模块中，未知节点通过共享信息确定其到锚节点的距离，以便在第二个模块中可以计算节点的初始位置。 2.1.1 RSSI 算法[4]
此算法已知节点发射功率，在接收节点测量接收功率，计算传播损耗，然后使用理论或经验的信号传播模型将传播损耗转化为距离。
所用公式如下：
σηX )d d (
log 10)d (PL P )d (P 0
100T +−−=
的随机变量
期望为方差为是一个服从正态分布的是一个信号衰减指数
时信号强度的损耗
是在两节点距离为是信号发射的强度
时的信号强度为两节点相距为其中0X d )d (PL P d )d (P 200T σησ根据如上公式可推导出信号强度转换距离的公式：
0T d ]10P(d)-)PL(d -P X 10exp[
d ×+=η
σ （2－1）
实际应用中的情况要复杂的多，尤其是在分布密集的无线传感器网络中。反射、多径传播、非视距、天线增益等问题都会对相同距离产生显著不同的传播损耗。因此这种方法的主要误差来源是环境影响所造成的信号传播模型的复杂性。信号强度测距法通常属于一种粗糙的测距技术，在现实环境中，温度、障碍物、传播模式等条件往往都是变化的，使得该技术在实际应用中仍存在困难，通常会产生50%左右的测距误差。
然而，基于射频信号强度的RSSI 方法成本很低，适合于无线传感器网络的部署要求，所以前景很好。 2.1.2 DV-distance 算法
DV-distance 算法很简单，在泛洪传输中
仅通过在每个节点上累加测得的距离来确定其距锚节点的距离。算法从锚节点开始，它们发送一个包含其身份，位置和设为0路径长度的信息包。每个接收到信息的节点将测得的其距发送点距离加到路径长度上，如果可控泛洪允许的话继续广播这个消息。另一个限制是，当节点再次收到以前接收过的节点信息时，只有当前信息中距锚节点路径长度小于原先信息中距锚节点路径长度时，才允许发送这个消息，并更新自身信息。最终结果是，每个节点将存储它们距锚节点的最短路径长度。
DV-distance 算法的缺点是，当距离信息在多跳中传播时，测距误差被累加放大。在锚节点很少或测距硬件差的大型网络中，这种累计误差很大。
2.1.3 DV-Hop 算法
水电安装开槽机
DV-hop 算法可以克服DV-distance 算法的缺点，它通过计算跳数而不是累加有误差的测距获得网络拓扑信息。定位算法可以分为两个阶段，即两次广播过程。
第一个阶段，每个锚节点采用广播方式将其位置信息传递给其邻居节点。广播的信息包格式为：{Id i ，x i ，y i ，Hops i }，其中包含了该节点的标识Id i 、位置坐标(x i ，y i )，以及跳数Hops i 信息。初始Hops i 为0，接收到此数据的每个节点将此信息记录到一张表中。然后继续向其邻居节点广播，每广播一次就将Hops i 加1。当节点接收到一个相同Id 的数据包时，便要与原来的Hops i 进行比较，如果新的跳数小于原表中的跳数，就用新的跳数更新表中的跳数信息，意味着到了一条更短的到达该
锚节点的路径。如果新的跳数大于原表中的跳数，就丢弃该数据包，也不再进行转发。经过第一阶段的广播过程后，锚节点也获得其它所有锚节点的坐标及跳数距离，而且所有传感器节点都已经得到所有锚节点的坐标和跳数距离。这样，每个锚节点即可用式2-2计算出锚节点i 到其它锚节点j 的每跳的平均间隔距离C ij ：
（2－2）其中j是除i之外的所有其它锚节点。
水力模块
第二个阶段，每个锚节点广播其计算出的每跳平均距离，数据包的格式为：{Id i，C i}。C i是该锚节点到所有其它锚节点的每跳平均距离。每个接收到此数据的节点将此信息添加到表中，然后继续向其邻居广播。重复ID的数据包就丢弃。经过此阶段的广播后，所有节点都已知所有锚节点计算的每跳平均距离C i。然后再将所有的每跳平均距离相加取平均：
（2－3）其中n为所有锚节点的个数。
配料罐
由此得到了全网所有锚节点之间的每
跳平均距离。此时，各个节点也得到与各个锚节点的跳数。由此可计算出该节点到锚节点的距离：D i = hops × cc。
图1 DV-hop定位算法示意图
如图1所示，已知锚节点L1与L2，L3之间的距离和跳数，L2计算得到平均每跳距离为(40+75)/(2+5)=16.42。同理，L1与L3也计算出平均每跳距离。节点A将分别从L1，L2与L3获得平均每跳距离，然后去这三个距离的平均值cc。用cc乘以节点A到L1，L2与L3的跳数即可得到A到这三个锚节点的距离。
2.1.4Euclidean算法
Dv-hop算法的缺点是不适用于极为不规则的网络拓扑结构，这种结构中，实际每跳间的距离差别很大。Niculescu和Nath提出了另一种称之为Euclidean的算法，这种测距算法是基于围绕锚节点的未知节点的局部几何算法。同样，信息也从锚节点开始泛洪传输，但测距算法比前几种情况复杂的多。
如图2(a)所示，假设节点拥有RSSI测距能力，已知未知节点B，C在锚节点L的无线射程内，BC距离已知或通过RSSI测量获得；节点A与B、C相邻。对于四边形ABCL，所有边长和一条对角线BC已知，根据三角形的性质可以计算出AL的长度(节点A与L的
距离)。使用这种方法，当未知节点获得与3个或更多锚节点之间的距离后定位自身。未知节点B、C与锚节点L 两两相邻，节点A 与B、C相邻。对于四边形ABCL，所有边长和一条对角线BC已知，根据简单的几何原理可计算出AL 的长度。但节点A有两个可能的位置A和A′，假如A还有其他邻居节点D 与锚节点L相邻，并与B或C之一相邻，那么可以使用D来替换B或C，再次计算AL的距离，则A节点就能在两个可能的位置中选择出正确的一个。使用这种方法，当未知节点获得与三个或更多锚节点距离后定位自身。由基本的几何知识，可以得出：
(2-4) 以上是在理想情况下，当四边形是凹四边形时情况要复杂一些。如图2(b)所示，一个节点（self）有两个邻居节点n1和n2，n1距锚节点的距离估算为a，n2距锚节点的距离为估算为b。再加上已知距离c，d和e，Euclidean算法能获得self节点距锚节点距离的可能值r1和r2。Niculescu描述了两种确定使用哪个值（如果有两个）的算法。如果存在第三个邻居节点n3，n3距锚节点的距离已估算出，且与n1或n2连通，可使用neighbor vote算法进行测距。用n3代替n2（或n1）又将产生两个估算距离。正确的距离是这两对距离的一部分，且被一个简单的投票算法选出。当然，为了选出更精确的距离，可以考虑很多邻居节点。
(a)
锁架(b)
图2 Euclidean 算法示意图
2.2 计算节点位置模块可选算法
在此阶段，通过模块1提供的未知节点到若干锚节点间的估算距离计算未知节点的初始位置。此阶段有三边测量法、多边形算法和Min-Max 等算法。 2.2.1 三边测量法
图3 三边测量法示意图
三边测量法是最简单的定位方法，在二维平面上用几何图形表示出来的意义是：当得到未知节点到一个锚节点的距离时，就可以确定此未知节点在以此锚节点为圆心、以距离为半径的圆上。得到未知节点到3个锚节点的距离时，3个圆的交点就是未知节点的位置，如图3所示。
从被估测的距离（di ）和已知的锚节点
的位置（xi ，yi ）中我们可以得到一组方程：
(x 1 - x)2 + (y 1 - y)2 =2
1d （2－6） (x 2 - x)2 + (y 2 - y)2 =22d （2－7）
(x 3 - x)2 + (y 3 - y)2 =23d （2－8）
求出(x ，y)即是节点位置。
2.2.2 多边形算法
多边形算法源于三边测量法，当参考节点数量超过3个时，就是通过定义方程组，利用冗余信息能够更精确地计算节点的位置。
假设未知节点坐标是( x ，y )，锚节点坐
标分别为( x 1，
y 1 )，( x 2，y 2 )，…，( x k ， y k )，未知节点到锚节点的距离分别是r 1，r 2，…，r k ，我们可以得到一组方程：
（2－9）
式（2－9）可以线性化为：Ax = b 其中：
（2－10）
（2－11）
由于存在测距误差，合理的线性模型应该是：
Ax +N = b
其中，N 为k - 1维随机误差向量。利用最小二乘法原理，x 的值应当使模型误差N = b - Ax 达到最小，即通过最小化Q ( x) = ||N||2
d3d2
d1
B(x1，y1)
C(x2，y2)zssi
A(x0，y0)
D
= ||b – Ax||2。求x的估计，对Q ( x)关于x求导并令其等于零，可以求解未知节点的最小二乘位置估计：
$x=(ATA)-1ATb
2.2.3 Bounding box算法
基于最小二乘估计的多边测量定位法是最常用的定位方法，在很多定位算法中得到应用。多边测量定位的缺点是需要大量的浮点运算。
针对这个问题，加州大学伯克利分校的Semic提出了一种更为简单的算法Bounding box。该方法的主要思想是利用锚节点的位置和测距值划出边界框（bounding box），求解边界框的交集（图4中的黑框），黑框的中心就是未知节点的估计位置，从图中可以看到Bounding box算法与三边测量算法求解的差异。该算法实质是将求解二次方程组的问题简化为求解一次方程问题，从而避免了复杂的最小二乘解法，可以大大减少计算开销。
图4 Bounding box算法示意图
算法主要思想是，用距离估计和锚节点位置为每个锚节点构建一个限定大小的盒子，然后确定这些盒子的重合部分。未知节点的位置即被设为重合部分的中心。如图2-7所示，用Min-Max算法确定一个已知到三个锚节点距离估计的节点的位置。值得注意的是，用Min-Max算法估测的节点位置接近于用多边形算法计算出的位置（也就是，三个圆的重合部分）。
锚节点a的盒子是通过a的坐标（x a，y a）加上和减去估测距离（d a）得到的：
[x a-d a，y a-d a]×[x a+d a，y a+d a] （2－12）盒子的重合部分是通过取所有锚节点坐标与估测距离之差的最大值和所有锚节点坐标与估测距离之和的最小值计算得到的：[max(x i-d i)，max(y i-d i)]
×[min(x i+d i)，
min(y i+d i)]（2－13）2.3 循环定位求精模块算法
这个阶段的目的是使在第二阶段计算
得出的（初始）节点位置更精确。即使在好的条件下（高连通度，低测距误差），这些节点定位也不可能很精确。原因是前两个阶段并没有用到所有可获得的信息。由Savarese[3]等提出的精确过程正是当节点更新他们的位
置信息时考虑了与所有节点间的距离。在每步开始时，一个节点广播它的位置并相应地从它的邻居节点那里接收邻居节点位置和
距离，然后执行阶段二的多边形算法计算过程以确定它的新位置。在很多情况下，由到邻居节点距离所限，将迫使新的位置向节点真实的位置靠近。经过几步迭代后，当节点位置更新过程收敛时，精确过程结束并报告最终位置。
3. 算法仿真
对定位算法的仿真的意义在于能够在接近现实的环境中得出算法性能的数据，进行定量分析，从而得
出算法的应用环境和不足之处，以待改进。仿真工具选择的是布达佩斯技术大学电信学院开发的OMNET++离散事件模拟器。
木材旋切机3.1 仿真算法选择
本文选择完全的分布式算法，即节点位置的计算在节点本地完成。这种算法可以应用于大规模的无线传感器网络。这样的网络要满足：
（1）自组织，不依赖于全局基础设施（如卫星）；
