基于分布式MDS的无线传感器网络节点定位算法研究.pdf

太原理工大学硕士学位论文基于分布式MDS的无线传感器网络节点定位算法研究姓名:张坤鹏申请学位级别:硕士专业:@指导教师:王华奎@太原理工大学硕士研究生学位论文- I - 基于分布式MDS 的无线传感器网络节点定位算法研究摘要在无线传感器网络节点定位技术中,基于多维尺度分析(multi-dimensional scaling, MDS)的定位方法一般有两类:经典的MDS方法和基于迭代MDS的方法,它们都基于节点之间的相似性信息即距离信息对网络中的未知节点进行定位,因此都属于基于测距的定位方法。经典MDS算法对网络中节点之间的距离组成的矩阵进行变换,算法简单,是一种粗粒度的定位方案,不过该方法是集中式的,在定位过程中会带来比较大的通信量。迭代MDS方法实际上是一种求精算法,它基于初始位置信息对未知节点的位置进行迭代求解,往往能达到比经典MDS算法更高的精度,但也会带来由于迭代计算所导致的比经典MDS算法更高的计算量。分布式多维尺度分析技术是一种将迭代MDS算法以分布式的形式应用于定位中的方案,由Jose A. Costa等人提出来的分布式加权多维尺度分析(distributed weighted-multidimensional scaling, dwMDS)算法是目前存在的比较好的算法,但其定位精度还有提高的空间。本文学习研究了一些迭代求精的算法并将它们以分布式的形式应用于定位的仿真中,得出了一些比较有意义的结果,主要工作概括如下:1. 研究了MDS算法的种类,分析了经典MDS算法的实现过程。对于迭代MDS算法,重点研究了dwMDS算法的原理,并且通过仿真观察RSSI测距模型导致的负偏差效应和两步邻居节点选择方案对定位结果的改善。对两类主要的MDS算法在不同的实验场景和连通度下进行了仿真,其中迭代MDS算法以dwMDS算法为例,以经典MDS算法作为初始位置算法,太原理工大学硕士研究生学位论文- II - 仿真结果表明,在由经典MDS所得到的初始位置的基础上,dwMDS算法能够收敛,但相对来说定位精度的提高不是很大。2. 研究了几种比较经典的迭代优化算法,如最速下降法、牛顿法和松弛迭代法,分析了各种算法的优缺点并将其中的最速下降法和迭代松弛法应用于分布式MDS定位方案中,并对两种算法进行了仿真实验。实验结果表明基于松弛法的分布式MDS定位算法收敛速度快,与dwMDS算法相比更适合于低连通度的情况;最速下降法的引入能使定位算法收敛性能更好,比dwMDS算法的定位精度更高。3. 研究了最速下降算法中迭代步长的改进方案,文中根据实验数据,通过数据拟合的方式在迭代步长和连通度之间构造了一种函数关系,方便定位场景中迭代步长的计算,并在不同的网络环境下进行了仿真,结果表明,与基于最速下降法的定位方案相比,在明显减小计算量的同时,该方案的定位精度只是略显偏低。关键词:无线传感器网络,分布式定位,MDS,迭代优化,迭代步长太原理工大学硕士研究生学位论文- III - LOCALIZATION ALGORITHM BASED ON DISTRIBUTED MDS IN WIRELESS WORK ABSTRACT In wireless works, node localization technology based on multi-dimensional scaling can generally be divided into two categories: the classical MDS method and the iterative MDS method. They all use the similar information such as the distance information between the unknown nodes to execute the localization, therefore both belong to localization method based on measured distances. The classical MDS transforms the matrix derived from distances between unknown nodes so as to localize them. It’s a simple coarse-grained algorithm but executed by centralized program which would lead a high volume munication. The iterative MDS in fact is one kind refinement algorithm, and it mak