改进的分布式无线传感器网络多维标度定位算法

刘健苗，许新忠，黄书广，李哲(.中讯邮电咨询设计院有限公司，郑州450007;.河南艺术职业学院，郑州45000)

改进的分布式无线传感器网络多维标度定位算法

刘健苗1，许新忠2*，黄书广1，李哲2
(1.中讯邮电咨询设计院有限公司，郑州450007;2.河南艺术职业学院，郑州450001)

为提高无线传感器网络集中式多维标度MDS-MAP算法的定位精度，提出了一种改进的基于MDS的分布式定位算法。该算法在构建距离矩阵时引入Euclidean算法距离估算思想，同时采用一种优化的基于最小二乘逼近的坐标转换方法实现节点由相对坐标到绝对坐标的转换。实验结果显示，与经典MDS-MAP算法相比，改进算法在多种网络拓扑结构下均能有效提高节点的定位精度。

无线传感器网络;节点定位;坐标转换;分布式;多维标度

无线传感器网络WSN(Wireless Sensor Network)是由密集部署在监测区域内的大量功能和结构完全相同的廉价传感器节点通过节点间的多跳无线通信而形成的自组织网络系统［1］。作为一种全新的信息感知及处理技术，近年来无线传感器网络被广泛应用在灾害监测、医疗卫生和工业生产等领域，这些应用大多与传感器节点的位置信息密不可分，缺少位置信息支持的监测信息通常是毫无意义的［2-3］。同时，精确获取节点位置信息还有助于提高路由效率，降低节点能耗，延长网络生命周期［4］。全球定位系统是目前应用最广的定位技术，具有定位精度高、时效性强等优点，但能耗大，成本高，不适于遮蔽环境的特点导致其无法规模应用于无线传感器网络;而人工定位又因为测量工作量极大也不适于节点数量巨大的无线传感器网络［5］。因此必须结合传感器网络的自身特点来实现节点的自定位。

节点定位技术作为无线传感器网络研究领域的基础支撑技术，已得到学术界的广泛研究，多种定位算法相继被提出。哥伦比亚大学Shang Yi等人将多维标度技术MDS(Multidimensional Scaling)［6］应用到Ad-Hoc网络定位中，提出了经典MDS-MAP算法［7］。该算法仅需少量锚节点便可实现网络中其他节点的定位，在精准测距条件下定位精度很高。然而，集中式定位模式导致其在网络规模较大时计算复杂度很高，同时该算法在网络拓扑不规则的情况下定位误差较大。为提升定位精度，研究人员相继提出多种基于MDS的改进算法，如分布式MDS算法［4，8-9］，加权MDS算法［10］，非线性滤波MDS算法［3］以及距离重构MDS算法［11］等，它们在特定条件下均取得了较好的定位效果。然而，这些改进算法都需要基于节点距离信息进行坐标计算，在精准测距的理想状态下，借助锚节点的绝对坐标经过线性变换来定位其他未知节点是没有问题的。但是往往节点测距范围有限，由此获得的距离矩阵并不准确，需要采用更优的坐标变换方法来减少未知节点定位的误差。

针对MDS-MAP及其相关改进算法存在的问题，本文在构造节点距离矩阵时引入Euclidean算法［12］距离估算思想，同时采用一种更为有效的坐标转换方法优化原算法中的坐标转换过程。实验结果表明，改进算法在提高节点定位精度的同时，降低了算法的时间复杂度。

1 MDS-MAP算法及分析

MDS-MAP算法利用数学心理学中的多维标度分析技术，以节点间距离信息构造距离相异性矩阵，并对其双重中心化后再进行特征分解，最后借助锚节点坐标构造多维空间中节点的绝对坐标图。

1.1 MDS-MAP算法流程

经典MDS-MAP算法可分为以下3个步骤［5］:①各节点向周围节点广播其路由信标，节点利用系统建立路由的过程采集来自其他节点的信号强度并保存待发，当经过一定次数的发送以后，认为节点已经采集了所有邻居节点的信号强度，每个节点将这些邻居节点信号强度发送至中心节点(通常中心节点是PC机)，由中心节点生成网络拓扑连通图。在此，信号强度被转换成节点间距赋予每条边，当节点间信号强度有效时，就使用该值来估计距离，当仅拥有连通性信息时，则为该边赋值1，最后采用最短路径算法(如Dijkstra算法或Floyd算法)生成节点距离矩阵;②对距离矩阵应用多维标度技术，生成2维或3维相对坐标系统;③借助少量锚节点(2维不少于3个，3维不少于4个)，经过线性变换将相对坐标系统转换成绝对坐标系统。

1.2 MDS-MAP算法坐标转换方法

通过多维标度技术获得的节点坐标是相对坐标，需要参考锚节点的绝对坐标，经过平移、旋转和翻转等一系列线性坐标变换，将相对坐标转换到锚节点所在的绝对坐标系中去。下面以二维传感器网络为例，对MDS-MAP算法的坐标转换方法进行讨论。

令二维传感器网络中传感器节点数为n，锚节点数为k(k≥2);X=［xij］2*n=［X1，X2，…，Xn］为节点的相对坐标，Y=［yij］2*n=［Y1，Y2，…，Yn］为其对应的绝对坐标，假设Y1，Y2，…，Yk为锚节点的绝对坐标。

平移变换可通过X'i=Xi+X0将坐标向量Xi转换成X'i，其中X0=［a b］T由各锚节点在不同坐标系下对应之矢量差的均值计算得出;坐标向量Xi旋转一个角度α即Xαi=Q1Xi可实现旋转变换，其中

在相对坐标X和锚节点绝对坐标Y1，Y2，…，Yk已知的情况下，有

故

对锚节点以外的节点进行相同的坐标变化可得

结合式(4)、式(5)可得其余节点的绝对坐标

1.3 MDS-MAP算法误差分析

在Range-Based条件下，MDS-MAP算法中节点的测距误差是引起定位误差的主要原因。当所有节点间的几何距离都正确时，MDS-MAP算法能给出没有误差的解。然而受到节点通信范围的制约，该算法对于不能直接测距的非邻居节点间的欧氏距离以最短路径距离来代替，在大多数情况下这样的估算会放大节点间的实际距离(最短路径上所有节点在同一直线上时除外)。不难推断，网络越不规则，由此产生的误差则会越大。

另外，MDS-MAP算法中采用的线性坐标转换方法修正定位误差的作用不够。坐标转换的目的是试图找到最优的转换方法将相对坐标系统图复原成绝对坐标系统图，由于MDS-MAP算法采用最短路径距离代替了多跳节点间的几何距离，多维标度后生成的相对坐标图将会变形，因此，无论采取何种线性变换该算法最终得到的绝对坐标图都会有较大的误差［13］。MDS-MAP算法将最小化锚节点在相对坐标与绝对坐标系统中的相对距离的最小均方误差作为衡量线性坐标变换是否最优的标准，其坐标转换过程在一定程度上减小了距离估算引起的误差，但并不是最优变换。

2 改进算法

针对上述MDS-MAP算法的不足，本文给出了一种改进的基于MDS的分布式定位算法，主要做了如下两方面的改进:①引入Euclidean算法距离估算思想构建距离矩阵;②采用了一种优化的基于最小二乘逼近的坐标转换方法。

2.1 算法描述

本文提出的改进定位算法实现步骤如下:

①节点分簇。以节点分簇思想作为该分布式算法的前提，将传感器网络划分为多个簇。最简单的分簇方法是将网络中每个节点作为主节点，以它的一跳或两跳邻居节点作为从节点来划分簇。本文为了减小MDS算法的计算量，同时可以有效利用Euclidean算法提高两跳节点间的距离精度，将以一跳邻居来分簇。

②构建局部距离矩阵。以簇为单位，引入Euclidean算法距离估算思想(见3.2节)构建局部距离矩阵。在距离矩阵中，相邻节点间距离可以通过测距得到，而对于非邻居节点来说，若能利用Euclidean算法计算节点间距离，则以该计算值作为节点间的欧氏距离，否则仍用最短路径距离来代替。

③生成局部相对坐标。利用多维标度技术对局部距离矩阵处理后得到各簇局部网络中节点的相对坐标。

④全局网络图的“缝合”。选择连通度最大(即邻节点最多)的簇局部相对坐标图作为全局网络图的起点，采用贪婪递增方式将剩余的相对坐标图逐步缝合到全局网络图中，最终生成全局相对坐标图。在网络缝合过程中，每次均选择与现有全局网络图拥有最多公共节点的局部坐标图作为下一次缝合的对象。

⑤全局绝对坐标的确定。借助锚节点绝对坐标，采用3.3节描述的坐标转换方法将全局相对坐标转换为全局绝对坐标，从而实现节点的定位。在坐标转换过程中，利用锚节点的相对坐标和绝对坐标，通过式(13)可以计算出最优的正交变换阵Q和向量b，作为其他未知节点坐标转换的参数。

假设传感器网络中共有n个节点，每个节点的平均邻节点数即网络平均连通度为r，锚节点数为k。改进算法中:生成全局相对坐标的时间复杂度为O(n·r3);由于构建距离矩阵时引入了Euclidean和Dijkstra算法，r个节点中至少已知r-1条边，由此带来的时间复杂度为O(r2+n);将局部相对坐标图缝合成全局相对坐标图的时间复杂度为O(n·r3);将全局相对坐标转换为绝对坐标的时间复杂度为O(k3+ n)。因此，改进算法的总时间复杂度为O(k3+2nr3+ r2+2n)，优于MDS-MAP算法O(n3)的时间复杂度。

2.2 Euclidean算法求距思想

Euclidean算法给出了传感器网络中求解与锚节点相隔两跳跳距的未知节点距离的方法，该算法的求距思想如图1所示。

图1 Euclidean算法求距示意图

假设所有节点均具有测距能力，未知节点B、C在锚节点A的测距范围内，而未知节点D在A的测距范围之外，节点B和C间距离BC已知或可测距，节点D与B、C相邻。那么对于节点A和D间的距离AD，可以通过以下几何关系计算得到。

2.3 改进的坐标转换方法

同样令二维传感器网络中传感器节点数为n，锚节点数为k(k≥2);X为节点的相对坐标，Y为其对应的绝对坐标。记两组坐标的中心节点为:

最优的坐标变换为正交变换阵Q和向量b使得式(11)最小，其中QTQ=I，e=［1，…，1］。

文献［14］给出此优化条件的最优解为

其中U和V满足

下面给出该最优解的求证过程:

由矩阵迹与Frobenius范数的关系‖A‖2F= tr(ATA)=tr(AAT)，有

若正交阵Q和向量b为式(11)的最优解，那么向量b需满足

结合式(14)和式(15)可将式(11)转换为

由QTQ=I和tr(ATB)=tr(BAT)，有

由式(17)可知，要求得式(16)的最小值，只需求得式(18)的最大值。

对(Y-eTyc)T(X-eTxc)奇异值分解，有

这里，Z=VTQU为正交阵，由ZZT=I可知显然-1≤zii≤1，i=1:2。因此，且当zii=1，i=1:2时得到其最大值，此时Z=I。故Q=VZUT=VUT，得证。

3 仿真实验与分析

基于MATLAB平台，从网络拓扑结构、锚节点数量及网络连通度等方面进行实验仿真，对本文提出的改进算法进行了有效性验证和分析。对平均定位误差定义为:

其中，R为节点的通信半径，n为网络中节点的总数，～di为节点i的实际坐标与定位坐标间的偏移距离。

为了验证网络拓扑结构对算法性能的影响，本文分别在正方形区域和C型区域进行仿真。同时为保证2种分布条件下网络连通度的一致，做如下假定:正方形区域边长为200 m，随机布设200个节点，C型区域边长200 m，其中空白区域140 m×120 m，随机布设116个节点;另设锚节点占比为5%，测距误差方差Er=0.15，节点通信半径为30 m。如图2所示，在规则区域和不规则区域MDS-MAP算法的平均定位误差分别为11.9%和105.63%，而本文提出的基于MDS的分布式改进算法平均定位误差为7.9%和5.9%，显然，改进算法在不规则网络拓扑情况下能明显改善定位精度，这是由于在分布式的定位算法中，各个节点的定位只依赖于周围邻居节点的距离信息，而与网络的整体拓扑结构关系不大。

图2 不同网络拓扑结构下的仿真结果

同时为验证改进的坐标转换方法的作用，在相同环境下，将本文提出的改进算法与分布式的MDSMAP算法(引入Euclidean算法测距思想)的定位结果进行对比后发现，改进算法的平均定位误差有0.5%～2%的降低。

图3给出了在规则区域中锚节点数量的不同对算法定位误差的影响。分析图中曲线可以看出，经典的DV-HOP算法受锚节点数影响较大，锚节点越多，定位越精确。而无论是MDS-MAP算法还是基于MDS的分布式算法，虽然随着锚节点的增多定位误差有所下降，但改善并不明显，锚节点数大于3个即可。这是因为，DV-HOP算法中每个节点直接估算与锚节点的距离，锚节点越多，估算越准确;而MDS-MAP算法和基于MDS的分布式算法只依赖于节点间的距离信息，当节点间距离矩阵确定后，节点的相对位置就可以确定。锚节点的作用仅仅是用来获得未知节点绝对坐标的转换参数。因此，基于MDS的定位算法受锚节点数量的影响较小。

图3 锚节点数量与定位误差的关系

要考察网络连通度对定位算法误差的影响，可以通过调整单位面积内节点数量或节点通信半径2种方式实现，本文将保持节点密度不变，通过调整节点通信半径来实现。在边长为200 m的正方形区域，节点数为200，测距误差Er=0.15，锚节点10个，节点通信半径在15 m～45 m之间，以5 m为步长递增，相应的网络连通度分别为:3.534 2、6.283 2、9.817 5、14.137 2、19.242 3、25.132 7和31.808 4。仿真结果如图4所示，当连通度较低(小于4)时，改进算法定位精度较MDS-MAP算法低，这是因为连通度较低时对网络分簇后存在较多一跳邻居节点小于1的节点，这些节点无法进行定位，而经典算法在规则网络条件下能较为精确地估算节点间的距离，从而得到较高的定位精度;当连通度较大(大于30)时，改进算法定位精度很高，但与经典算法相比提高有限，反而算法的计算量和通信量有所增加;而当网络连通度介于5和30之间时改进算法定位精度与经典算法相比有较大的提高。在实际应用中，综合考虑算法的定位精度和复杂度，基于MDS的分布式改进算法适合于网络节点连通度介于5至30之间的网络。

图4 网络连通度与定位误差的关系

4 结语

基于多维标度技术的无线传感器网络节点定位算法其误差主要来源于构建距离矩阵时的距离估算，网络越不规则，误差越大，网络规模越大，算法时间复杂度越高。本文对经典MDS-MAP算法进行分布式改进，引入Euclidean算法计算非邻节点间距离，同时优化了原算法中的坐标转换方法，在规则和不规则网络结构下均有效地提高了节点的定位精度，同时降低了算法时间复杂度。诚然，复杂的算法固然可以提高定位精度，但无线传感器网络节点的能量是有限的，在算法时间复杂度与能量消耗之间寻求合理的平衡点将值得进一步的研究和探讨。

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京:清华大学出版社，2005.

［2］Sayed A H，Alireza T，Nima K.Network-Based Wireless Location Challenges Faced in Developing Techniques for Accurate Wireless Location Information［J］.IEEE Signal Processing Magazine，2006，23(5):24-40.

［3］陈岁生，卢建刚，楼晓春.基于MDS-MAP和非线性滤波的WSN定位算法［J］.浙江大学学报(工学版)，2012，5(5):866-872.

［4］王健，赵亚凤，刘劲风.一种适用于大规模无线传感器网络的定位算法［J］.东北林业大学学报，2009，37(8):84-89.

［5］王福豹，史龙，任丰原.无线传感器网络中的自身定位系统和算法［J］.软件学报，2005，16(5):857-868.

［6］Borg I，Groener P.Modern Multidimensional Scaling Theory and Applications［M］.New York:Springer-Verlag，1997:10-35.

［7］Shang Yi，Ruml Wheeler，Zhang Ying.Localization from Mere Connectivity［C］//Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing.2003:201 -212.

［8］韩双霞，张露，范一鸣.WSN中改进的分布式多维定标定位算法［J］.传感技术学报，2009，22(5):728-733.

［9］Gopakumar Aloor，Lillykutty Jacob.Distributed Wireless Sensor Network Localization Using Stochastic Proximity Embedding［J］. Computer Communications，2010，33(6):745-755.

［10］Chan F，So H C.Efficient Weighted Multi-Dimensional Scaling for Wireless Sensor Network Localization［J］.IEEE Trans on Signal Processing，2009，57(11):4548-4553.

［11］黄亮，王福豹，段渭军，等.基于距离重构的无线传感器网络多维定标定位算法［J］.传感技术学报，2013，26(9):1284 -1287.

［12］Niculescu D，Nath B.Ad-Hoc Positioning Systems(APS)［C］// Proceedings of2006 IEEE Global Telecommunications Conference，Washington，2006:2926-2931.

［13］王林，王晓鹏.改进的无线传感器网络中多维定标定位算法［J］.计算机工程与应用，2011，47(27):115-118.

［14］Luo Xinlong，Wu Zhijun.Least-Square Approximations in Geometric Buildup for Solving Distance Geometry Problems［J］.Journalof Optimization Theory and Applications，2010.

刘健苗(1980-)，男，湖南武冈人，硕士，工程师，研究方向为通信信息，传感技术;

许新忠(1978-)，男，河南修武人，硕士，讲师，研究方向为算法优化;

黄书广(1985-)，男，河南汤阴人，硕士，助理工程师，研究方向为无线传感器网络。

Advanced Distributed Multidimensional Scaling Localization Algorithm for Wireless Sensor Network

LIU Jianmiao1，XU Xinzhong2*，HUANG Shuguang1，LI Zhe2

(1.China Information Technology Designing and Consulting Institute Co.，Ltd.，Zhengzhou 450007，China; 2.Henan Vocational College of Art，Zhengzhou 450001，China)

An advanced distributed localization algorithm based on MDS was proposed，which attempted to improve the node localization accuracy of the classical MDS-MAP algorithm in wireless sensor network.During the course of producing localnode distance matrix，a new distance estimates method from Euclidean localization algorithm is introduced.Besides，a more effective transforming technology which based on the least-squares approximation is used to replace the original one，to transform the relative coordinate system to absolute coordinate system.Experimental results show that in the same experiment environment，compared with the classical MDS-MAP algorithm，the improved algorithm is more reliable in various topology networks.

wireless sensor network;coordinate transformation;node localization;distribution;multidimensional scaling

TP393

A

1004－1699(2014)05－0692－06

10.3969/j.issn.1004－1699.2014.05.023

2014-01-23

2014-04-09