一种面向无线传感器网络的分布式定位算法

晁旭，申晓红，白卫岗

（西北工业大学 航海学院，陕西 西安 710072）

随着微机电系统技术、数字电子学和无线通信技术的进步，促进了廉价、多功能的网络传感器结点的快速发展，使得无线传感器网络（Wireless Sensor Network，WSN）能够广泛应用于军事和民用领域[1-2]。而WSN中的大多数应用（如军事目标监测、森林火灾监控）都需要网络中节点的地理位置信息，从而获知信息来源的准确位置。此外，利用节点位置信息可以设计路由算法以提高路由效率等。所以，节点自定位问题已成为WSN的一个重要研究方向。

目前已经提出了很多节点自定位算法，而由于水下环境的特殊性，陆上无线传感器网络的节点定位算法在水下受到了一定的使用限制。在水下环境中，电磁波和光波衰减严重，节点需采用声波进行通信，节点无法通过接收GPS信号来获取精确的地理位置信息，从而无法生成整体绝对坐标系。为了满足水下无线传感器网络在军事应用等对节点定位的高精度的要求，笔者提出一种分布式无信标节点的相对定位算法。

该算法适用于节点布放在水下环境中的WSN，节点无法生成绝对坐标。首先，节点间通过 TOA（Time of Arrival）[3]测距技术获取节点间的相对距离信息；然后网络节点利用最高节点度分簇算法[7]分簇，并分别在簇内计算节点局部坐标；最后，各簇间进行合并以统一坐标，形成整体相对坐标系统。为了提高定位精度，该算法采用经典度量多维尺度分析技术计算簇内相对坐标，有效地减少了由于测量距离误差所带来的坐标估计误差。通过实验仿真表明，与同类算法相比，该定位算法提高了约10%的节点自定位精度。

1 相关工作

当前典型相对定位算法有MAP-Growing[4]和SDGPSN[5]等。

MAP-Growing算法首先通过计算相对坐标下非线性关系的3个邻居节点的位置从而建立初始局部坐标系，并向外广播坐标信息；然后计算与此3点相邻的节点坐标，如此反复计算其余相邻节点的坐标直至所有节点被定位。该算法对拓扑结构适应性很强，节点定位覆盖率高。该算法使用经过计算得到坐标的点协助定位会造成较大的误差累积。

SDGPSN算法分3步：首先，每个节点运行一个随机的定时器，时间一到，未收到邻居节点消息的节点自举为簇头并发布簇头消息，收到的节点为簇成员；其次，簇头以自身为坐标原点建立局部坐标系；最后，相邻簇通过边界节点合并成全局坐标系。该算法在分簇阶段，簇个数过多，使后期存在较大的通信量和计算量；在簇内坐标计算阶段，使用三边定位方法的定位误差较大。

2 DARL算法

笔者提出一种分布式无信标节点的相对定位算法（DARL）。算法假设：1）节点间距离通过TOA技术测得，该方法要求各节点间时钟同步，通过计算声波传播的时间来估计距离；2）节点随机分布在一个二维平面内，各节点结构相同，通信半径R相等，单跳通信；3）节点ID唯一，最小的为 0，用于全局坐标生成阶段。算法分为3个阶段：分簇阶段，局部坐标系建立阶段和全局坐标系建立阶段。

2.1 分簇阶段

算法开始时，每个节点广播其ID，节点通过邻节点发来的信息计算邻节点到自身的距离，收到信息的邻节点将节点的距离信息和ID记录下来，同时根据其他节点的广播信息更新自身邻节点列表。在所有节点发送一遍信息后，每个节点会获知所有一跳邻节点ID和距离。节点一跳邻节点的数目即为该节点的连通度。

然后，节点广播其连通度、邻节点ID和距离。节点在获得所有邻节点连通度后，连通度最大的节点成为簇头，其自身ID即为簇头ID，并发布成簇信息，当度数相同时则选择ID最小的节点作为簇头。收到信息的节点记录下簇头ID，并成为该节点的从节点。

由于在最后簇的合并阶段，需要簇和簇之间有至少两个公共边界节点，因此需要对分簇进行优化。初次分簇完成以后，公共边界节点向簇头广播消息，如果相邻簇之间只有一个公共节点，则以这个公共节点为簇头，其一跳邻节点为从节点。

2.2 局部坐标系的建立

当分簇完成完成以后，则要计算簇内节点相对坐标。本定位算法采用经典度量MDS[6]技术。由簇头负责收集节点间距离信息，以自身为原点计算包含所有簇成员坐标的局部坐标系。

算法简要描述如下：

1）簇头收集各从节点间距信息，包括从节点间的直测距离，如果从节点之间距离不可直接获得，则使用最短路径法求出节点之间距离，构成距离矩阵[Dij]；

2）使用各节点间距离矩阵[Dij]构建相异性矩阵[Pij]，即[Dij]=[Pij]；

3）对距离矩阵[Dij]使用经典MDS算法。其过程分以下5个步骤：

①计算距离矩阵的平方矩阵D2；

②计算矩阵J=I-e·eT/n，其中I为单位矩阵，n为节点数量，e=[1，1，…1]T

④奇异值分解：H=UVUT：

对于第5步，由于生成的是二维坐标，所以取矩阵U的前2列构成矩阵U2，选取大于零的前2个特征值构成V2，即可得到各节点相对位置的坐标矩阵。

为了进行坐标系合并，对得到的坐标矩阵进行平移，将簇头的坐标化为（0，0）。

4）簇头广播各节点的坐标。

2.3 全局坐标系的建立

当网内各簇均建立局部相对坐标系后，公共边界节点发布自身所在簇的所有ID信息。当相邻簇之间有两个或两个以上公共边界节点时，便开始合并，合并方向为ID较大的簇向ID较小的簇合并。重复这个过程，直至所有簇都合完成。

簇间坐标转换示意图如图1所示。簇间坐标转换要求簇间至少有两个以上的公共边界点，i、k为簇头原点，j、l为两簇的公共边界点，实线表示两节点间可以进行测距即距离已知，虚线表示两节点间不能进行测距即距离未知。可通过四边形计算公式得出i、k之间的距离[4]。

图1 簇间坐标转换示意图Fig.1 Coordinate transformation diagram between clusters

此处假设 k 向 i转换，在三角形 Δ（i，j，l）和 Δ（k，j，l）中，θ1，θ2，可以由下式得出：

令 θ=θ1+θ2，dik由下式计算：

通过计算，可得出节点k在i簇坐标系中的相对坐标以及以i为原点的坐标系中的向量。对于k中任意从节点m，坐标转换可以通过计算向量获得m点在以i为原点的坐标系中的坐标。依此即可将k所在簇的节点坐标转化为i节点所在簇的节点坐标，从而实现簇间的坐标变换，建立全局相对坐标系。

2.4 算法估计精度分析

1）map-growing算法使用递进式的坐标计算方式，使得测距误差不断的累积，而本算法利用分簇思想，将网络分成大大小小的几个簇，可以降低测距误差的累积；

2）SDGPSN算法在簇内坐标计算使用的是三边定位法，本算法使用MDS定位方法可以改善定位精度。

3 仿真实验与结果分析

本实验采用MATLAB对文中提出的定位算法进行了仿真计算。仿真环境为一定面积内的矩形场景，并随机分布一定数量的网络节点，以节点间的距离作为节点实际距离，然后再在节点实际距离上加入均值为0、方差为σ2的随机高斯噪声e（作为测量误差）作为节点间的测量距离参数。

文中假设网络节点分簇已经完成。首先，在长宽各为150 m的矩形区域内随机分别布放一定数量的20～100个节点，令节点有效通信距离r=100，噪声方差σ2为1时，分别对DARL和SDGPSN方法各进行50次的仿真实验，并进行定位误差平均统计，实验结果如图2所示。然后，在长宽各为100 m的矩形区域内随机分布60个节点，通信距离r=80，噪声方差σ2按步长0.5取1～3，分别对两种方法进行50次仿真实验，实验结果如图3所示。

图2 定位误差与节点数量关系图Fig.2 Relationship chart between positioning error and the number of node

图3 定位误差与噪声方差关系图Fig.3 Relationship chart between positioning error and noise variance

从图2中可以看出，文中算法的定位精度比SDGPSN算法有显著提高，并且没有因为节点增多而导致误差的累积。主要原因是SDGPSN算法在局部坐标生成阶段只使用了三边定位法，没有使节点间的测距误差得到控制。而本算法使用经典度量MDS技术计算局部坐标，该技术能有效地利用多余的节点间距信息来减少计算误差，并且分簇后，簇内节点之间最多有两跳通信距离，降低了最短路径误差，进一步降低了MDS技术的方法误差。

从图3中可以看出，节点数量一定时，随着噪声的增大，两种方法的定位误差都有所增大，但是相比SDGPSN算法，本算法的误差增幅较小，这说明测距误差对本算法的影响较小，算法稳定性好。

4 结 论

文中主要以水下应用为背景，提出了一种分布式无信标节点的相对定位算法。通过实验仿真计算，验证了该定位算法的合理性，同时与同类算法相比提高了定位精度，为水下事件位置报告、目标跟踪、地理路由等应用提供了有力的技术支持。

[1]孙殿东，朱悦.无线传感器网络及应用研究[J].电子设计工程，2010，18（5）：90-91.

SUN Dian-dong，ZHU Yue.Research of wireless sensor networks and its applications [J].Electronic Design Engineering，2010，18（5）：90-91.

[2]关亮，张开龙，李同松.无线传感器网络（WSN）定位系统设计[J].电子设计工程，2010，18（5）：84-86.

GUAN Liang，ZHANG Kai-long，LI Tong-song.Design of WSN location system[J].Electronic Design Engineering，2010，18（5）：84-86.

[3]Girod L，Estrin D.Robust range estimation using acoustic and multimodal sensing[C]//Proc IEEE/RSJ Int’l Conf Intelligent Robots and Systems（IROS’01），2001（3）：1312-1320.

[4]LI Xiao-li，SHI Hong-chi，Yi Shang.A MAP-growing localization algorithm for Ad hoc wireless sensor networks[C]//Proc.of the 10th ICPADS.Newport Beach，USA：[s.n.]，2004.

[5]Iyengar.R，Sikdar.B Scalable and distributed GPS-free positioning for sensor networks[C]//Proceedings of IEEE International Conference on Communications.An-chorage：IEEE Press，2003（1）：338-342.

[6]Shang Y，Ruml W.Localization from mere connectivity[C]//Proceedings of the 4th ACM International Symposium on Mobile Ad-hoc Networking and Computing.Annapolis， 2003：201-212.

[7]郑少仁，王海涛，赵志峰，等.Ad Hoc网络技术[M].北京：人民邮电出版社，2005.