一种基于多维标度的分簇迭代无线传感器网络定位算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于多维标度的分簇迭代无线传感器网络定位算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：本文提出了一种基于多维标度技术的分簇迭代定位算法LC-MDS。首先，在网络中选取一个可定位簇，在簇内应用MDS技术，实现局部网络中未知节点定位，然后将定位后的节点升级为伪锚节点，配合其他锚节点，进行迭代运算，直到网络所有节点都成功定位。本文算法解决了因MDS距离矩阵过于庞大而导致的的计算繁琐问题，定位精度优于传统算法MDS-MAP。
中图分类号：TN929.5 文献标识码：A 文章编号：1007-9416（2017）01-0125-02
在无线传感器网络中，传感器节点多是被飞机、大炮等方式随机抛洒至目标监测区域，节点自组成网，除了少数配备GPS模块的锚节点可获取自身的地理位置信息外，其他节点的地理位置未知。然而，无论是实现环境监测、目标跟踪等应用，确定触发事件消息的来源，即节点定位是无线传感器网络应用实现的基础前提[1]。目前，以多维标度技术为核心的的定位算法MDS-MAP，仅利用节点的关联信息和少量的锚节点位置信息，就可同r对多点定位，然而，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.