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

太原理工大学
硕士学位论文
基于分布式MDS的无线传感器网络节点定位算法研究
姓名:张坤鹏
申请学位级别:硕士
专业:@
指导教师:王华奎
@
太原理工大学硕士研究生学位论文
基于分布式 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 算法作为初始位置算法,
- I -
太原理工大学硕士研究生学位论文
仿真结果表明,在由经典 MDS 所得到的初始位置的基础上,dwMDS 算法
能够收敛,但相对来说定位精度的提高不是很大。
2. 研究了几种比较经典的迭代优化算法,如最速下降法、牛顿法和松
弛迭代法,分析了各种算法的优缺点并将其中的最速下降法和迭代松弛法
应用于分布式 MDS 定位方案中,并对两种算法进行了仿真实验。实验结果
表明基于松弛法的分布式 MDS 定位算法收敛速度快,与 dwMDS 算法相比
更适合于低连通度的情况;最速下降法的引入能使定位算法收敛性能更好,
比 dwMDS 算法的定位精度更高。
3. 研究了最速下降算法中迭代步长的改进方案,文中根据实验数据,
通过数据拟合的方式在迭代步长和连通度之间构造了一种函数关系,方便
定位场景中迭代步长的计算,并在不同的网络环境下进行了仿真,结果表
明,与基于最速下降法的定位方案相比,在明显减小计算量的同时,该方
案的定位精度只是略显偏低。
关键词:无线传感器网络,分布式定位,MDS,迭代优化,迭代步长
- II -
太原理工大学硕士研究生学位论文
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
coa