MDS-MAP算法的改进及在室内车辆定位中的应用

乔中标， 李津蓉， 马连伟

(浙江科技学院 a.机械与汽车工程学院；b.自动化与电气工程学院，杭州 310023)



MDS-MAP算法的改进及在室内车辆定位中的应用

乔中标a， 李津蓉b， 马连伟b

(浙江科技学院 a.机械与汽车工程学院；b.自动化与电气工程学院，杭州 310023)

为了解决现代化大型停车场寻车难的问题，提出一种基于无线传感器网络的定位算法。即以经典的MDS-MAP(multidimensional scaling-map)节点定位算法为基础，在全局范围内选择1个一跳的邻居节点子网，对其进行相对定位；结合极大似然估计法，计算出其余节点的相对坐标；利用锚节点的坐标信息，得到网络内所有待测节点的绝对坐标。仿真结果表明，改进后的算法可以解决停车场形状不规则及车辆随机停放等情况所造成的网络空洞问题。因此，该算法能在很大程度上提高定位的精确性，适用于大型室内停车场的实际情况。

大型室内停车场；车辆定位；无线传感器网络；MDS-MAP；定位误差

随着社会的高速发展与人们消费水平的不断提高，汽车的拥有量也在逐年提升。汽车数量的激增给人们带来了诸多不便，如大型停车场“寻车难”的问题就经常困扰着车主。由于停车场内没有参照物，要找到自己的车经常要花费较长的时间，而传统的停车场系统很难解决这个问题。传统的GPS定位成本高，并且在有物体遮挡住卫星信号时则无法进行定位[1-2]，因此GPS并不适用于室内停车场。目前室内无线定位技术主要有ZigBee、RFID(射频识别技术)及Wi-Fi等技术[3-4]，如文献[5]中设计了基于Wi-Fi指纹定位的智能停车场系统，系统包括免取卡停车、智能导航、反向寻车等功能；文献[6]中设计了基于RSSI的室内停车场车辆定位算法，该算法在停车位处部署车辆节点，在天花板或墙体上部署汇聚节点[7]，将地标节点(坐标已知的节点)部署在停车场的各个位置，当1个车辆节点可以同时接收到3个地标节点信号时，利用三角测量法[8]计算车辆节点的位置；文献[9]中设计了基于CSS技术和TOA(信号到达时间差)[10]的室内停车场车辆定位算法，该算法利用CSS技术实现数据通信，再使用基于TOA改进的SDS-TWR双边双向测距算法，测量基站与车辆节点的距离，在得到1个车辆节点与3个基站的距离后，利用改进的三边算法[11]计算出车辆节点的位置。

综观现有的室内停车定位算法，大多存在定位不准确或者系统成本较高的问题。MDS-MAP(multidimentional scaling-map)算法[12]是基于多维定标MDS的节点定位算法，该算法是由美国密苏里哥伦比亚大学的Shang Yi等人最早提出的，并将其运用到无线传感器网络节点定位上[13]。MDS-MAP算法与应用较为广泛的LANDMARC和VIER室内定位算法相比，其定位参考标签的部署没有严格的要求，且需要的数量较少；同时，MDS-MAP算法也不存在对边界处节点定位误差大的问题。但在经典MDS-MAP算法中，当两个节点的距离较远而无法直接计算欧氏距离时，算法就利用网络节点间的最短路径距离来代替节点间的欧氏距离，因此当网络拓扑结构不规则或存在空洞时，距离的近似计算就会存在较大的误差，最终导致定位不准确。室内停车场的平面形状及车辆实际停放的情况，使得以车辆节点组成的网络拓扑结构并不规则，因此用经典算法无法进行准确的定位。笔者对MDS-MAP算法进行了改进，提出了一种基于一跳子网中节点间距的MOH(MDS one-hop)算法。改进的算法先对1个一跳子网内的节点进行定位，然后利用极大似然估计法[14-15]对子网外的其余节点逐个进行定位，直到覆盖整个网络，最后将得到的相对坐标转换成节点的绝对坐标，从而实现精确定位目标。

1 停车场车辆定位系统设计

车辆定位系统主要分为无线传感器网络模块、数据处理模块、信息发布与显示模块[16]。定位系统中的无线传感器节点使用线性调频扩频技术进行通信，线性调频扩频技术的链路层、控制层及物理层均采用IEEE802.15.4a技术标准并施以扩展。

1.1 传感器网络模块

将无线传感器节点制作成定位标签，当车辆入库时领取定位标签，与此同时利用摄像机拍下车牌号，在后台服务器中与定位标签的信息绑定。当车辆驶入停车场区域后，定位标签便接入整个无线传感器网络。

1.2 信息处理模块

服务器每隔5 s对定位标签的数据进行采集，计算处理后生成车辆的定位信息。

1.3 信息发布与显示模块

利用编程软件制作一个显示界面，将车辆的定位信息与停车场的电子地图相结合，从而实现车主在手机终端上车辆的可视化查找。

停车场车辆定位流程如图1所示，定位系统架构如图2所示。

图1 停车场车辆定位流程示意图Fig.1 Schematic diagram of vehicle positioning process in parking lots

图2 停车场车辆定位系统架构图Fig.2 Structure diagram of vehicle positioning system in parking lots

2 MDS-MAP算法的改进

2.1 MDS-MAP定位算法简介

MDS-MAP算法的核心思想是得到节点间的距离矩阵，进而利用MDS方法获得各节点的相对坐标；然后利用已知的锚节点将相对坐标转化成实际环境中的绝对坐标。具体方法如下。

假设某监控区域内有n个传感器节点，节点i和节点j之间欧氏距离为：

(1)

不能通信的两节点之间的距离用节点间的最短路径距离来代替。根据各节点间的距离估值，建立网络节点的距离矩阵D。

(2)

式(2)中：Q表示坐标系旋转和镜像映射的过程；B表示坐标系平移的过程。Q和B的元素值可通过已知锚节点的实际坐标与其对应的相对坐标计算得到。

用最短路径距离代替节点间的欧氏距离必然会存在误差，特别是当传感器网络中存在通信空洞或网络部署区域很不规则时，误差会非常明显。为了解决这一问题，并且让其适用于室内停车场车辆定位的环境，笔者将其做了改进，提出了MOH算法。

2.2MAD-MAP算法的改进

极大似然估计的基本思想就是,利用1个未知节点可以接收到多个锚节点信息来构建由多个方程式组成并拥有唯一解的系统，在解方程的过程中引入最小均方误差来得到方程组的最优解。在改进算法中使用极大似然估计可以降低那些定位误差较大的节点对新节点定位精度的影响，提高了定位的鲁棒性。

MOH算法首先选取1个一跳范围的子网进行定位，得到子网中节点的相对坐标后，再以子网内的节点作为锚节点，利用极大似然估计对子网外的节点进行定位。这样就可以避免用最短路径代替欧氏距离所产生的定位误差。

假设现有由n个节点组成的自组织无线传感器网络，坐标矩阵为X=[X1,X2,…,Xn]T，其中Xi=(xi,yi),i=1,2,…,n，表示第i个节点的坐标。新算法步骤如下。

1)根据节点间是否可以相互通信构建一个n×n的邻接矩阵A。如果节点i可以接收到节点j的信号，即节点j是节点i的一跳节点，则矩阵元素aij=1，否则aij=0。

2)在整个网络内找出1个全连接的子网，该子网内的节点全都互为一跳节点。对邻接矩阵A进行如下处理便可得到1个子网：

①删除矩阵A中邻居节点最少的行和列，得到新矩阵A1；

②检验新矩阵是否是全1矩阵，是则退出循环；否则令A=A1，重新执行步骤①。

经以上步骤便可得到一个全1矩阵，将矩阵A1的行(或列)所对应的节点作为集合Vin，子网外的节点作为集合Vout。如果全网络节点的集合为V，则有Vin=V-Vout。

3)利用MDS方法计算集合Vin中节点的相对坐标。集合Vin中节点间的欧氏距离都可以测到，因此可以利用MDS方法计算其相对坐标。

4)在集合Vout中搜索一个节点v，要求在集合Vin中至少有3个节点是节点v的一跳节点。假如集合Vin有节点v1，v2，…，vm都是节点v的一跳邻居节点。而这m个节点的相对坐标已知，因此可利用极大似然估计法算出节点v的相对坐标。得到节点v的相对坐标后，将节点v加入到集合Vin中。

3 仿真实验

用MATLAB模拟停车场的环境来对经典MDS-MAP算法与改进MDS-MAP(MOH)算法的性能进行比较。

3.1 车辆节点部署及参数设定

图3 车辆节点分布图Fig.3 Diagram of vehicle node distribution

假设现有1个200m×200m的室内停车场。沿横坐标方向和纵坐标方向每隔10m停放1辆车，并且每辆车的实际位置都在此基础上有2m的偏差。每辆车上都装配无线传感器网络节点，总共265个传感器节点，其中27个锚节点；节点通信半径为50m。为了模拟车辆分布区域的不规则，这里在200m×200m的区域内去除一个120m×160m的区域，这部分区域车辆不可以停放。图3即为车辆节点的分布图。图3中，小圆圈代表车辆节点，星号代表锚节点。此时网络中节点的平均连通度为43.8。

3.2 算法性能对比

用经典MDS-MAP算法进行定位，效果如图4所示。图4中，小圆圈表示车辆节点的估算位置，线段表示车辆节点实际位置与理论位置的偏差，线段的另一端代表车辆节点的实际位置。可见，用经典的MDS-MAP算法进行定位，误差非常大。

用改进后的算法对车辆节点进行定位,首先模拟理想情况(即节点间的距离可以准确测得)，得到定位结果如图5所示。

图4 MDS-MAP算法定位误差图Fig.4 Diagram of localization error of MDS-MAP algorithm

图5 MOH算法定位误差图Fig.5 Diagram of localization error of MOH algorithm

由图5可以看出，图中没有明显的表示定位误差的线段，此时由于定位误差小，线段近似成了一个点，基本上都位于小圆圈当中，这说明定位比较精准。

3.3 测距误差与通信半径对定位精度的影响

(3)

图5是理想条件下的定位结果，其定位误差均值约为1.0×10-4m。在实际环境中，传感器节点利用信号的传播损耗来测量距离是存在误差的。因此，加上节点通信半径距离5%的测距误差来测试定位的效果，如图6所示。

由图6可知，当测距误差为5%时，也可以得到较为理想的定位结果。在节点通信半径固定为50m的情况下，分别以测距误差为0%、5%、10%、15%、20%来进行测试，得到其平均定位误差分别为0.001、2.75、6.95、9.45、21.50m。可见，当测距误差增加时，平均定位误差也在增加。因此在工程实践中，如果测距误差超过一定的范围，定位结果将没有意义。

节点的通信半径也对定位精度存在影响。图7是在测距误差分别为0%、5%、10%和15%的情况下，得到的节点通信半径与平均定位误差之间的关系图。

图6 5%测距误差定位效果图Fig.6 Positioning effect diagram of 5% ranging error

图7 通信半径与平均定位误差的关系图Fig.7 Diagram of relation between communication radius and average localization error

由图7可以看出，随着通信距离的增大，平均定位误差逐渐减小，并趋于稳定。测距误差越大，最终趋于稳定的平均误差值也越大。显然，减小测距误差和提高节点的通信半径可以提高节点的定位精度。

4 结 论

笔者提出了一种基于无线传感器网络的室内停车场车辆定位算法，该算法在MDS-MAP算法的基础上进行改进，使其适用于室内停车场车辆停放的实际情况。仿真试验表明，与传统算法相比，改进后的算法可以对车辆节点进行较为准确的定位，且增加节点通信半径可以提高定位的精度。但是，由于该种集中式算法会存在误差累计的问题，特别是当测距误差增大时，某些节点会存在较大的定位误差，因此在这些方面还需做进一步研究。

[1] 黄艺，胡善岳，何芹,等.基于Android平台的移动通讯设备的GPS定位研究[J].激光杂志，2014，35(3):42.

[2] 李博文，姚丹亚，蒋凤成.车载GPS定位滞后时间的计算方法[J].清华大学学报(自然科学版)，2014，54(9):1215.

[3] 赵军，李鸿斌，王智.无线网络室内定位系统研究[J].信息与控制，2008，37(4):465.

[4] 夏英，王磊，刘兆宏.基于无线局域网接收信号强弱分析的混合室内定位方法[J].重庆邮电大学学报(自然科学版)，2012，24(2):219.

[5] 黄旭，范婧，吴茂念，等.基于Wi-Fi指纹定位技术的智能停车场系统的设计与实现[J].计算机科学，2016，43(6A):512.

[6] 路正，王晓燕.基于无线传感器网络的室内停车场定位系统[J].通讯技术，2012，33(10):67.

[7] 夏侯凯顺，余辉荣，邬依林，等.基于自适应分簇的改进RSSI定位算法[J].微电子学与计算机，2014，31(5):103.

[8] 冯秀芳，王丽娟，关志艳.无线传感器网络研究与应用[M].北京：国防出版社，2014:138.

[9] 李国良，丁施健，王阳，等.基于CSS技术和TOA的室内停车场定位系统[J].南京师范大学学报(工程技术版)，2015，15(3):64.

[10]WANGA,YANGK,JIANPINGAN.Totalleast-squaresalgorithmfortimeofarrivalbasedwirelesssensornetworkslocation[J].IEICETransactionsonFundamentalsofElectronics,CommunicationsandComputerSciences,2011,94(9):1851.

[11] 刘玉军，蔡猛，高立恒.基于RSSI测距的传感器节点质心定位修正算法[J].计算机测量与控制，2014，22(9):2860.

[12]AMINK,OHS.Robustlocalizationfromincompletelocalinformation[J].IEEE-ACMTransactiononSignalProcessing,2013,21(4):1131.

[13]SHANGY,RUMLW.ImprovedMDS-basedlocation[C]//Proceedingsofthe23rdInternationalConferenceoftheComputerCommunications.Piscataway:IEEE,2004:2640.

[14] 刘健苗，许新忠，黄书广，等.改进的分布式无线传感器网络多维标度定位算法[J].传感技术学报,2014,27(5):692.

[15]WEISSAJ,PICARDJS.Networklocalizationwithbiasedrangemeasurements[J].IEEETransactionsonWirelessCommunications,2008,7(1):298.

[16] 刘敏，张国山，邴志刚，等.大型停车场中车辆定位问题研究[J].系统仿真技术,2014，10(3):192.

Improvement of MDS-MAP algorithm and its application in indoor vehicle localization

QIAO Zhongbiaoa， LI Jinrongb， MA Lianweib

(a. School of Mechanical and Automotive Engineering; b. School of Automation and Electrical Engineering, Zhejiang University of Science and Technology, Hangzhou 310023, Zhejiang, China)

To solve the problem of positioning vehicles in modern large-scale parking lots, a localization algorithm based on wireless sensor networks is proposed. Firstly, on the basis of the classical multidimensional scaling-map(MDS-MAP) node positioning algorithm, a one-hop neighbor node subnet is selected within the global network and positioned; and then the relative coordinates of the remaining nodes are able to be calculated by combining the estimation method of maximum likelihood; finally, the absolute coordinates of all unknown nodes in the network can be obtained by utilizing the coordinate information of anchor nodes. Simulation results show that the improved algorithm can solve the problem of the network cavity caused by the irregular shape of the parking lot and random parking of vehicles, which can greatly enhance accuracy of localization, more applicable to the actual situation of large-scale indoor parking lots.

large-scale indoor parking lots; vehicle positioning; wireless sensor networks; MDS-MAP (multidimentional scaling-map); localization error

10.3969/j.issn.1671-8798.2017.03.007

2017-02-28

国家自然科学基金项目(61540034)；浙江省公益性技术应用研究计划项目(2014C31020)

李津蓉(1977— )，女，天津市人，副教授，博士，主要从事无线传感器网络节点定位和智能学习算法研究。E-mail: jrli@zust.edu.cn。

TP212.9

A

1671-8798(2017)03-0195-06