林吉+李晖

摘要：本文提出了一种基于多维标度技术的分簇迭代定位算法LC-MDS。首先，在网络中选取一个可定位簇，在簇内应用MDS技术，实现局部网络中未知节点定位，然后将定位后的节点升级为伪锚节点，配合其他锚节点，进行迭代运算，直到网络所有节点都成功定位。本文算法解决了因MDS距离矩阵过于庞大而导致的的计算繁琐问题，定位精度优于传统算法MDS-MAP。

关键词：多维标度；分簇迭代；无线传感器网络

中图分类号：TN929.5 文献标识码：A 文章编号：1007-9416（2017）01-0125-02

在无线传感器网络中，传感器节点多是被飞机、大炮等方式随机抛洒至目标监测区域，节点自组成网，除了少数配备GPS模块的锚节点可获取自身的地理位置信息外，其他节点的地理位置未知。然而，无论是实现环境监测、目标跟踪等应用，确定触发事件消息的来源，即节点定位是无线传感器网络应用实现的基础前提[1]。目前，以多维标度技术为核心的的定位算法MDS-MAP，仅利用节点的关联信息和少量的锚节点位置信息，就可同時对多点定位，然而，MDS-MAP采用集中式其计算方法，计算复杂，通信代价高，能耗较大，本文针对问题提出改进算法LC-MDS。本文组织如下：第1节介绍相关研究工作，第2节详细介绍LC-MDS算法，第3节进行仿真分析，并总结全文。

1 相关研究工作

1.1 经典多维标度技术

多维标度（简称MDS）是一种将数据关系表示成几何图形加以研究的数据分析技术[2]，在无线传感器网络中，可利用它计算节点的相对坐标。MDS生成节点的相对坐标的具体实现方法如下：已知n个传感器节点的坐标：X={x1，x2，..，xn}，和它们间n维对称距离矩阵：D=[dij]n×n，1≤i≤n， 1≤j≤n。首先，计算距离平方相似度矩阵D（2）=[D2]，求矩阵D（2）的双中心形式：H=-（1/2）JD（2）J，其中J=I-e*eT/n，e=（1）1×n，I=[1]n×n。然后，提取H的前k个特征值并从小到大排列成对角矩阵：Uk=diag（λ1，λ2，…，λk），对应的k个特征向量构成：Vk=[e1，e2，…，ek]，那么，H=UkVkUkT，H还可以表示成：H=XXT。最后，将关于H的这两个表达式联立计算，可得到这n个节点在k维空间的坐标解：Xk=VkLk1/2，其中Lk1/2为k个特征值构成的对角阵的开平方。

1.2 绝对坐标变换原理

使用多维技术计算出节点相对坐标后，要利用分布式定位方法把相对位置对齐到物理位置，对齐过程包括移动、旋转和坐标反射，在二维情况中，至少需要三个位置已知的节点，这些传感器节点可以是锚节点，也可以是通过计算获知自身物理位置的节点，通过确定三个位置已知的节点从相对位置到物理位置的转换规律[3]，可以将其他节点对齐到物理位置，如图1所示：节点1、2、3、4、5为物理位置，其中1、2、3为锚节点。1、2、3、4、5为相对坐标位置，通过把1、2、3对其到物理位置1、2、3，节点4、5也可以对齐到物理位置。

2 LC-MDS算法

设一个二维无线传感器网络由m+n个节点构成，其中锚节点集合为A={ax}，x=1-->m，未知节点集合为U={uy}，y=1-->n，每个节点拥有唯一的ID，信号功率发射半径为R，节点i通信范围内的其他节点称为节点i的邻节点，记为集合Ni。

2.1 拓扑感知

通过节点间的信息交换可以实现节点对周围的拓扑环境的感知，流程如下：

（1）源节点洪泛查询分组。分组内容包括消息源节点序号S_ID，跳数值H，初始化为0，当前转发节点F_ID，初始化为null。（2）邻节点收到该分组，同时查询本是否存在该分组，若不存在，保存该分组，并继续转发。若存在，将H+1，再与本地记录的跳数值比较：大于，丢弃该分组；小于，替换本地记录；等于，对比F_ID：若相同，丢弃该分组，若不同，保存该分组。（3）节点融合本地的已保存分组，提取路由节点的序号，跳数和个数信息，并将这些信息广播。

2.2 分簇迭代

遍历锚节点信息，寻找任意3个锚节点的共同邻居节点ui，若存在，将ui及其邻居节点作为簇成员，将这3个锚节点中具有最小ID的锚节点作为簇首；若不存，则寻找两个锚节点的共同邻居节点uj，再选取第三个锚节点使得它到这两个锚节点的距离和最短，簇首和簇成员的选择方法同上。簇首和簇成员构成局部网络簇。分簇后，簇首利用MDS算法将簇内节点映射到相对位置，再根据簇内锚节点的已知物理坐标和映射规律，将未知节点对齐到物理位置。已定位的未知节点升级为伪锚节点，重复以上步骤，直到整个网络节点都成功定位。

3 算法仿真与分析

定义定位误差为：，在matlab仿真平台下， 在100m×100m的方形区域里，随机产生100个节点，其中锚节个数m=10，定位误差曲线见图2所示：定位精度随着通信半径的增大提高，后趋于稳定，相比于MDS-MAP算法，对本文算法可将精度提高9%左右。计算复杂度由O（n3）下降到 kO（p3），其中k为网络分簇的个数，p为平均簇内的节点个数，p远小于n。

参考文献

[1]彭宇，王丹.无线传感器网络定位技术综述[J].电子测量与仪器学报，2011， 25（5）：389-399.

[2]王博.无线传感器网络基于多维标度定位算法的研究[D].沈阳：辽宁大学，2014.

[3]屈剑锋，郭茂耘.一种基于锚节点分簇的传感器网络节点定位方法[J].计算机应用研究，2011（9）：3470-3473.