结合极大似然距离估计的MDS-MAP节点定位算法*

李津蓉，王万良，介　婧，姚信威

（1.浙江工业大学计算机科学与技术学院，杭州310023；2.浙江科技学院自动化与电气工程学院，杭州310023）

结合极大似然距离估计的MDS-MAP节点定位算法*

李津蓉1，2，王万良1*，介婧2，姚信威1

（1.浙江工业大学计算机科学与技术学院，杭州310023；2.浙江科技学院自动化与电气工程学院，杭州310023）

基于多维定标的定位算法通常利用节点间的最短路径长度代替欧式距离构建距离矩阵，当网络拓扑结构不规则时，会导致较大的定位误差。针对这一问题，提出了一种结合极大似然距离估计和多维定标的节点定位算法MDS-MAP（MLE）。算法将待测节点的一跳邻居节点信息作为极大似然方法的输入，利用与邻居节点的距离信息计算待测节点的相对坐标，然后根据已知锚节点的坐标，将所有节点的相对坐标映射为绝对坐标。实验结果表明，针对规则网络和不规则网络，MDS-MAP （MLE）算法均可取得较好的定位精度，且当网络连通度在一定范围内变化时，定位误差可保持在较低的稳定区间内。

无线传感网络；定位算法；多维定标；极大似然方法

EEACC:7230doi:10.3969/j.issn.1004-1699.2016.04.018

无线传感器网络中的节点定位机制是指依靠有限的位置已知节点，确定布设区域内其它节点的位置，建立各个传感器节点间的二维或三维空间关系。高密度的传感器节点通过近距离感知物理世界，为分析计算系统提供具有较高准确性和实时性的信息。而在大多数情况下，只有结合准确的位置信息，传感器所获得的数据才有实际的应用价值，如目标定位与跟踪、险情监测、环境勘查等［1］。

基于多维定标MDS（Multi Dimensional Scaling）的节点定位算法MDS-MAP［2-4］由于其所需锚节点的数目少，且可在基于测距和无需测距两种情况下使用，近年来成为节点定位技术的研究热点。但由于MDS-MAP算法利用网络节点间的最短距离近似欧式距离，导致网络的距离矩阵不准确，特别是当网络拓扑结构不规则或网络中存在通信空洞时，由于节点间的最短路径距离与实际的欧式距离差距较大，导致最终节点定位结果的误差难以接受［5］。

针对MDS-MAP所存在的问题，Shang提出了分布式MDS算法MDS-MAP（P）［6］，这种方法首先将两跳之内的邻居节点利用MDS算法获得局部地图，然后利用贪婪算法对局部地图进行融合得到所有节点的相对坐标，最后利用坐标已知的锚节点将各节点的相对坐标映射为绝对坐标。在此基础之上，一系列基于网络分簇的MDS-MAP算法［7-11］被提出，这类算法的基本思想是首先将网络节点基于某种策略分成若干“簇”，各个簇头节点利用局部信息对簇内节点进行定位，再将簇内地图通过融合算法构成全局地图。这类算法利用局部路径信息对节点进行定位，避免了远距离节点间的最短路径距离与欧式距离的较大误差，因此定位精度较高。但这类算法通常存在以下问题: 1）分簇算法较复杂，且簇的划分对后续算法的运行效率及定位精度有较大影响；2）局部地图的融合过程开销较大，且会出现误差累积问题。

针对以上算法不足，本文提出一种结合极大似然距离估计的MDS-MAP节点定位算法MDS-MAP （MLE）。MDS-MAP（MLE）算法首先利用MDS方法对一个一跳连接子网（即子网内各个节点均为一跳邻居关系）内的所有节点进行定位；然后利用极大似然方法对子网外的其余节点进行定位，逐步扩散子网直至覆盖整个网络。仿真实验表明，针对规则网络和不规则网络，该算法均可取得较好的定位精度。

1　MDS-MAP（MLE）算法

为了避免经典MDS-MAP算法中利用节点间的最短路径距离近似欧式距离所造成的计算误差，MDS-MAP（MLE）算法的基本思想是首先仅利用一跳邻居间的距离信息进行节点定位，然后将已定位的节点作为极大似然算法［12-13］中的锚节点，对相邻节点进行定位；逐步扩大已定位节点的范围，直至覆盖整个网络。

假设自组织网络内共有N个传感器节点，节点集合记为V，对应的坐标向量为X=［X1，X2，…，XN］T，其中Xi=（xi，yi），（i=1，…，N）表示第i个节点的坐标。MDS-MAP（MLE）算法步骤如下:

Step 1根据网络连通情况，构建全网邻接矩阵A（N×N），若节点i与j为一跳邻居关系，则矩阵元素aij=1，否则aij=0。

Step 2在全局网络中找到一跳邻居子网。这相当于在全局网络所对应的无向图G中找到一个全连接子图，这通常被称为最大团问题MCP（Maximum Clique Problem），是一NP完全问题，需要使用相应的优化策略搜索最优解。但在我们的实际应用中只需要找到一个全连接子图即可，而并不要求为最大子图，因此为了简化算法，我们采用以下策略:①在邻接矩阵A中删除邻居最少的节点所对应的行和列，得到矩阵A′；②检查矩阵A′是否为全1矩阵，是则退出循环；否则，令A=A′，回到步骤①）。当以上算法结束时，A′中所有行（或列）所对应节点的集合记为VCLOSED，其中所有节点为全连接关系，构成了1跳邻居子网，网络中的其余节点集合记为VOPEN，即VOPEN=V-VCLOSED。

Step 3计算1跳邻居子网中所有节点的相对坐标。由于VCLOSED中所有节点均为一跳邻居关系，因此直接利用测距方法所获得的节点距离测量值构建节点距离矩阵，并利用MDS方法计算VCLOSED中所有节点的相对坐标值。

Step 4根据全网邻接矩阵A，在VOPEN中找到一个节点v，要求集合VCLOSED中与v构成一跳邻居关系的节点数大于等于3，假设节点集合｛v1，v2，…，vm｝⊂VCLOSED，且v1，v2，…，vm与节点v均为一跳邻居关系，由于在Step 3中已通过MDS方法计算得到v1，v2，…，vm的坐标，因此可利用极大似然方法计算节点v的坐标，记录节点v的坐标，并将节点v从VOPEN集合转移到VCLOSED集合，即VOPEN=VOPEN-v，VCLOSED=VCLOSED⋃v。

Step 5重复Step 4，直至集合VOPEN=∅，此时VCLOSED集合包含了网络中的所有节点，且已计算获得所有节点的相对坐标矩阵

Step 6利用坐标已知的锚节点，将VCLOSED集合中节点的相对坐标矩阵转换为绝对坐标矩阵

2　实验研究及性能分析

为了测试MDS-MAP（MLE）算法对自组织传感器网络中节点的定位性能，我们在Matlab2012b环境下分别对规则网络和不规则网络中的节点定位进行了仿真实验。

2.1算法流程示例

首先，以一个规则网络为例，说明算法的运行流程。在1 000 m×1 000 m正方形网络区域内随机部署200个节点，其中锚节点数量为40个，其余为待测节点，锚节点和待测节点的位置均为随机，测距误差为0。经算法Step 2，可在全局网络的中部找到一个包含14个节点的一跳邻居子网，子网内的任意两节点均为一跳邻居关系。网络布局及子网连接如图1所示，其中，黑色实心圆点表示锚节点，空心圆点表示待测节点，节点间的连线表示节点为一跳邻居关系。此时，子网内的所有节点构成了集合VCLOSED，其余节点构成集合VOPEN。对VCLOSED集合中的节点利用MDS算法得到它们的相对坐标，之后即可根据Step 4进行迭代，在集合VOPEN中寻找与VCLOSED子网连接度大于3的一跳邻居节点，利用极大似然方法计算它的相对坐标，并将其加入VCLOSED集合。图2给出了第一次迭代、和最后一次迭代时，VCLOSED集合中节点相对坐标，其中“黑色□”表示新加入的节点，黑色虚线表示新加入节点与VCLOSED集合中节点的一跳邻居关系。

图1　示例网络拓扑结构及一跳邻居子网

图2　MDS-MAP（MLE）算法迭代结果（相对定位）

最终，网络中所有节点定位结果如图3所示，图中每个节点连接的线段末端为节点实际坐标位置，即线段越长，则定位误差越大。节点i的定位误差δi记为

其中，R表示节点的通信半径。实际上此次实验中节点的平均误差仅为1.0×10-4，因此图中的线段近似于一点。

图3　MDS-MAP（MLE）算法的定位结果

2.2性能分析及比较

为了进一步分析MDS-MAP（MLE）算法的性能，将其与经典MDS-MAP算法分别在规则网络和不规则网络连接环境下进行比较。算法性能通过待测节点定位的最大误差、最小误差、平均误差和运行时间进行评估。在1 000 m×1 000 m的方形区域内随机部署200个节点，其中20个锚节点，节点通信半径为200 m，测距误差为5%。图4（a）为网络规则连接情况，图4（b）为C形网络连接情况。

图4　网络连接图

MDS-MAP算法和MDS-MAP（MLE）算法的定位结果如图5和图6所示，从图5和图6可以看出，MDS-MAP（MLE）算法的定位精度明显高于MDSMAP，尤其是在不规则连接的网络中，由于节点间的路径距离与欧式距离的偏差较大，导致MDSMAP算法的定位结果非常不准确，而MDS-MAP （MLE）算法成功避免了这一问题，定位效果较好。两种算法的性能指标如表1所示。

图5　两种算法对规则网络中节点的定位结果比较

图6　两种算法对C形网络中节点的定位结果比较

表1　两种算法对节点定位的性能比较

当网络中的节点数量或节点通信半径变化时，均会影响网络连通度，进而对定位算法的结果产生影响，为此我们在不同的网络连通度下，对两种算法分别在规则网络和不规则网络中的定位误差进行了比较，比较结果如图7所示。

从图7可以看出，MDS-MAP算法的定位误差会随着连通度的提高明显下降，而MDS-MAP（MLE）算法的定位误差则保持一个稳定的较低水平。分析两种算法的工作原理，可知其原因如下:MDS-MAP算法的定位误差主要来自于节点间的最短路径距离与欧式距离的偏差，当连通度较低时，由于任意两节点间的连通路径数量较少，使得所选出的最短路径长度与两节点的欧式距离有很大偏差，导致定位误差较大，而当网络连通度提高时，节点的最短路径长度与欧式距离接近，使得定位误差显著降低。MDS-MAP （MLE）算法的定位误差主要由节点的测距误差所导致，网络连通度的提高可以增加待测节点的邻居数量，若测距误差满足高斯分布，使用极大似然算法计算待测节点的相对坐标时，可以更好地消除测距误差的影响。但当测距误差不是很显著时（小于5%），邻居节点数量的增加对定位误差的消除不会产生明显作用。因此，对于MDS-MAP（MLE）算法而言，只要待测节点的已知邻居数量满足算法要求，即可在一定范围的网络连通度内保持较低的定位误差水平。

图7　两种算法在不同网络连通度下的定位误差比较

由于网络节点间的测量距离是获得节点相对坐标的唯一依据，因此测距误差会对定位结果产生严重影响。为此，在实验中考虑了测量误差为通信距离的0～20%范围内，并假设测量误差满足正态分布，对MDS-MAP（MLE）和MDS-MAP的定位误差进行了比较，比较结果如图8所示。

图8　两种算法在不同测量误差下的定位误差比较

由图8可以看出，当测距误差上升时，MDS-MAP （MLE）与MDS-MAP算法定位误差的增长趋势基本一致，无明显的误差积累现象，这实际上得益于测距误差为正态分布的假设。由于在MDS-MAP（MLE）算法的每次迭代过程中，使用极大似然算法对未知节点进行定位时，利用了多个邻居节点与未知节点的距离信息，测距误差在一定程度上相互抵消，可获得较为准确的定位结果。但如果测距误差不满足正态分布，或用于定位的邻居节点数量较少时，则会产生较严重的误差累积现象，在这种情况下，如何进一步提高算法的容错性还需进行更为深入的研究。

3　结论

本文提出了一种基于极大似然方法估计节点间欧式距离的无线传感器网络多维定标自定位算法MDS-MAP（MLE），该算法避免了经典MDS-MAP算法中利用最短路径近似欧式距离所导致的误差。仿真实验表明，MDS-MAP（MLE）算法在规则网络和不规则网络中均可获得较高的定位精度，且当网络连通度在一定范围内变化时，定位误差可保持在一个相对稳定的低水平区间之内。但MDS-MAP （MLE）算法仍属于集中式定位算法，且计算速度与MDS-MAP算法相比无明显优势，在此方面需做进一步的深入研究。

［1］ 于海斌，梁炜，曾鹏.智能无线传感器网络系统［M］.第2版.北京:科学出版社，2013.

［2］ Amin K，Oh S.Robust Localization from Incomplete Local Information［J］.IEEE-ACM Transactions on Networking，2013 21（4）: 1131-1144.

［3］ 刘政.基于粒子群优化的多维标度节点定位算法［J］.传感技术学报，2015，28（8）:1228-1232.

［4］ Amar A，Wang Y Y，Leus G，et al.Extending the Classical Multidimensional Scaling Algorithm Given Partial Pairwise Distance Measurements［J］.IEEE Signal Processing Letters，2010，17（5）: 473-476.

［5］ 明良，赵刚，谢桂海，等.面向智能空间的位置感知算法研究［J］.软件学报，2009，20（3）:671-681.

［6］ Shang Y，Ruml W.Improved MDS-based Location［C］//Proc of the 23rd Conf of the IEEE Communications Society，2004:2640-2651.

［7］ Shon M，Jo M，Choo H.An Interactive Cluster-Based MDS Localization Scheme for Multimedia Information in Wireless Sensor Networks［J］.Computer Communications，2012，35（15）:1921-1929.

［8］ 王勇，胡良梁，袁巢燕.基于密度分簇的无线传感器网络定位算法［J］.电子科技大学学报，2013，43（3）:406-409.

［9］ Shon M，Choi W，Choo H，et al.A Cluster-Based MDS Scheme for Range-Free Localization in Wireless Sensor Networks［C］//Cyber-Enabled Distributed Computing and Knowledge Discovery（CyberC），2010 International Conference，2010:42-47.

［10］Sert S A，Bagci H，Yazici A，et al.MOFCA:Multi-Objective Fuzzy Clustering Algorithm for Wireless Sensor Networks［J］.Applied Soft Computing，2015，30:151-165.

［11］刘健苗，许新忠，黄书广，等.改进的分布式无线传感器网络多维标度定位算法［J］.传感技术学报，2014，27（5）:692-697.

［12］Weiss A J，Picard J S.Network Localization with Biased Range Measurements［J］.IEEE Transactions on Wireless Communications，2008，7（1）:298-304.

［13］钟丽鸿，胡成全，金京姬.基于RSSI极大似然估计定位算法的分析与实现［J］.吉林大学学报（理学版），2014，52（3）:557-660.

李津蓉（1977-），女，天津市人，博士，副教授。现为浙江科技学院自动化与电气工程学院教师，浙江工业大学计算机科学与技术学院博士后，主要研究方向包括:无线传感器网络，机器学习、智能计算等；

王万良（1957-），男，江苏高邮人，博士，教授，现为浙江工业大学计算机科学与技术学院院长，主要研究方向包括:计算机控制与智能自动化、网络化控制与远程监控、复杂系统的智能调度与优化控制、无线网络与物联网等；

介婧（1972-），女，博士（博士后），教授。现为浙江科技学院自动化与电气工程学院教师。主要研究方向包括智能控制、调度优化、智能系统及检测装备，群智能及机器人。

Localization Algorithm for Wireless Sensor Networks Based on MDS-MAP Integrated with Maximum Likelihood Estimating*

LI Jinrong1，2，WANG Wanliang1*，JIE Jing2，YAO Xinwei1
（1.College of Computer Science&Technology，Zhejiang University of Technology，Hangzhou 310023，China；2.School of Automation and Electric Engineering，Zhejiang University of Science&Technology，Hangzhou 3100233，China）

The multidimensional scaling（MDS）positioning algorithms of wireless sensor networks usually use the length of shortest path in lieu of the Euclidean distance between two nodes to build the distance matrix，which may result in large positioning errors，especially when the network topology is irregular.To solve this problem，a new localization algorithm MDS-MAP（MLE）was proposed in this work，in which the MDS-MAP method and Maximum Likelihood Estimating was combined.The information coming from the 1-hop neighbors are deemed as the input of the maximum likelihood method to estimate the relative coordinate of the tested node.And this process will iterate until all unknown nodes'relative coordinate are estimated.And then the global map can be transformed to an absolute map based on the absolute positions of anchors.Simulation results shows that the MDS-MAP（MLE）algorithm can get high positioning precision，either for regular or irregular network.In addition，the positioning errors can stay relatively constant at a low level when the network connectivity vary within a certain range.

wireless sensor networks；localization algorithm；multidimensional scaling；maximum likelihood 6210Q

TP393

A

1004-1699（2016）04-0572-06

项目来源:国家自然科学基金项目（61379123）；国家自然科学基金项目（61402414）；浙江省自然科学基金项目（LQ14F050002）

2015-11-29修改日期:2016-01-07