物联网目标定位算法的MATLAB仿真

陈向阳，柯伟，杜炼，刘培，徐莹，沈超

1.武汉工程大学计算机科学与工程学院，湖北 武汉 430205；2.武汉工程大学邮电与信息工程学院，湖北 武汉 430205；3.湖北省档案局（馆）科技处，湖北 武汉 430071

物联网目标定位算法的MATLAB仿真

陈向阳1，柯伟1，杜炼2，刘培2，徐莹3，沈超1

1.武汉工程大学计算机科学与工程学院，湖北 武汉 430205；2.武汉工程大学邮电与信息工程学院，湖北 武汉 430205；3.湖北省档案局（馆）科技处，湖北 武汉 430071

为了解决物联网定位中面临的诸多问题，对经典定位算法进行了仿真研究，并通过对仿真结果进行对比分析得到将最小二乘法、最大似然估计与拉格朗日日乘法结合起来使用的估计目标位置方法，即统一地利用加权最小二乘法／受限制的加权最小二乘法来计算各种算法.根据测量结果得到的非线性方程能够转化为线性方程，而这些线性方程应用加权最小二乘法与拉格朗日乘法来处理，这种方法可以很容易应用到其他算法上.在噪声相对较小时，上述算法性能已经可以达到克拉美罗下界和无偏性.

定位算法；最小二乘法；最大似然估计；拉格朗日日乘法

0 引言

基于物联网的无线定位算法是由已知坐标信息的锚节点和未知节点构成，各节点可以通过相互协调工作来发送、接受、处理、存储数据，通过无线方式连接，进而共同完成特定的应用任务.算法允许位置任意存放，灵活度较高，相比于基于非测距的节点相比，由于可随意放置，精确度较高而用途广泛.因为存在一定的冗余度，即使大部分不能工作，只要还有少许节点正常工作，仍可以获得较高的定位精度.基于非测距定位算法，以大量简单的定位节点获得估计定位置，而基于测距的定位算法以少量复杂的定位节点换取较高的定位精度［1-2］.通过MATLAB软件仿真结果对比得到了实用的基于测距的目标定位算法即TOA、TDOA、AOA、RSS及TDOA-AOA联合算法.

在定位系统中全球卫星定位系统（GPS）占全球定位应用中绝大部分市场，但由于成本、体积等因素限制使得这四大系统均不适用于低成本的物联网应用，为此需要针对物联网定位区域相对较小、低成本等特性设计合适的定位算法及其应用.

无线定位算法可大体分为两类，基于测距的定位算法和基于非测距的定位算法.

基于非测距的定位算法主要有质心算法、DV-Hop算法、凸规划定位算法、APIT算法.着重介绍基于测距的定位算法TOA、DTOA、RSS、AOA及TDOA-AOA算法.具体实现的主要功能如下:

主要实现基于测距的算法，包含TOA、DTOA、RSS、AOA及TDOA-AOA算法的定位，每个算法首先会建立相应的模型，考虑误差以便更加符合实际情况.其次用TOA、DTOA、RSS、DTOA-AOA测量的值运用受限地加权最小二乘法（CWLS）建立方程，接下来利用AOA结合加权最小二乘法、拉格朗日乘法来建立方程，以及最大似然估计等方法处理方程，这样定位点比较精确.通过求定位误差方差的克拉美罗下界（CRLB）来比较定位算法性能［3-4］.

1 定位算法的模型

1.1 TDOA定位算法

TDOA算法定位原理是首先选择一个基站为参考基站，运动站方发送无线信号，可以获得这个参考基站BS1与其他每个基站BSi接收信号的时间差，从而知道了BSi与BS1基站到移动站之间的距离差.通过这些几何关系建立BSi与BS1之间双曲线，双曲线焦点为这两个基站，根据双曲线的点到焦点距离差为一个定值，可以确定运动站的可能存在轨迹，通过两个以上的双曲线即可确定移动站的坐标.TDOA算法几何模型如图1所示.

图1 TDOA几何模型Fig.1 The geometric model of TDOA

假设将第一个基站作为参考基站，将模型归纳成公式（1）形式:

而nTDOA，i代表噪声、即每个测量距离差值的误差．如果rTDOA，i直接由DOA处获得的数据获得，那么

如果没有误差，可将公式（1）改写成

将以上对所有的i，方程改成矩阵的形式

其中：

而参数向量g＝［x-x1，y-y1，R］T

同时（x2-x1）2+（y2-y1）＝R2，可以将此公式改写成

其中M＝diag（［1，1，-1］）．如此一来，对于受限制的加权最小二乘法的矩阵转化为拉格朗日乘法来求解．

求出此方程极值点，取值使公式（7）最小时的g即可．

1.2 RSS定位算法

nRSS，i代表着误差，如果a＝1，那么该模型RSS与DOA模型一样．如果RSS定位算法没有测量误差，公式（9）可以变成公式（10）形式［6］:

对其公式（10）转变得

其中:

参照TDOA方法，由于Aθ＝b无解，对其进行受限制的加权最小二乘法的方差进行处理，得到公式（13）为

其中:

求式（12）最小值，应用拉格朗日乘法列方程如下:

求出方程（14）极值点，取值使公式（13）最小时的g即可．

1.3 AOA定位算法

AOA算法测量的由移动站发送到基站i的信号方向，这个方向与（x，y）及（xi，yi）相关，方向角度有φi表示，有公式（15）［7-8］:

图2为AOA算法角度测量几何图形．

图2 AOA算法定位的几何图形Fig.2 The geometric model of AOA algorithm localization

一般来说，φi由第i个基站到移动站之间的直线与x轴之间形成的夹角，如果存在误差，那么测量的角度由rAOA，i表示，可以根据测量的角度建立如下模型:

其中nAOA，i代表着测量rAOA，i时附带的误差．对于AOA算法，如果没有出现误差干扰，则公式（16）可以写成:

可以将公式（17）转化为

对于所有的i，以向量的形式写出来，可以得到公式（19）:

其中:

如同TDOA，RSS一样，为了提高运动站定位精度，用加权最小二乘法，可以建立如下方程:

其中Ω-1是加权矩阵，x＝（x，y）T，根据最佳线性无偏估计（BLUE）来求Ω．

1.4 TDOA-AOA定位算法

显而易见，若把两者算法混合，很可能提高算法的精度，或者可以减少使用基站的数量．在可能混合算法中，AOA和TDOA最容易混合起来，为了能够定位，需要重写公式（17）定位模型，两边同时加变量:yicos(rAOA，1)-xisin(rAOA，n)得到如下等式［9-10］:

把式（3）和式（17）合并到一个向量中，可以转化为如下的等式:

式（23）中:

其中:

0n指n×1的零向量，要求合适的g只需保证取值最小．

并保证约束条件

其中，矩阵w是相应的加权矩阵．

然后根据第1．1节求TDOA中g的过程来求TDOA-AOA中的g．同样的道理，把AOA与RSS，或者TOA结合，也可以提高单个算法的精度．

1.5 各种定位算法的克拉美罗下界

对于方差达到克拉美罗下界（CRLB）的无偏估计称为有效方差．克拉美罗下界表示定位误差的最小值，通过比较克拉美罗下界和提出的算法来验证算法的精度．

2 定位算法仿真及分析

下面的仿真结果由于要比较各种定位算法在噪声较小时的定位精度，故对仿真图片图3进行放大．由图4可看出，当噪声较小时，RSS定位精度比较准确，甚至超过了TDOA-AOA联合算法，但是RSS定位算法对误差也很敏感，当干扰功率大于-30dB时，定位误差突然变大，但同比其他算法，误差也基本保持比较低，整体上说该算法仍是性能比较好的算法．接着定位第二准确的是TDOAAOA，由图4所示，TDOA-AOA算法定位精度相对于TDOA算法、AOA算法都有所提高，在AOA部分测量误差干扰为-30dB，该算法误差也比较低，精度比较好．TDOA-AOA、TDOA，AOA算法对噪声有一定的抵抗力，当噪声功率提高时，定位精度也随之平稳地下降．当误差较大时，RSS与AOA定位误差相对较小，即精度较高．

图3 各种算法定位坐标变化Fig.3 The coordinate variation of localization algorithms

图4 各种算法的定位噪声与定位误差变化Fig.4 The positioning noise and positioning error variation of positioning algorithms

因此，总的来讲当噪声都充分小时，TDOAAOA算法、TDOA算法、AOA算法、RSS算法定位都可以很好地定位．当噪声变大时误差超过-30 dB，相当于测量距离误差定位精度都严重下降．在实际工程运用中，就要根据实际情况选择定位算法．当噪声较小时，选择RSS算法比较好，当噪声相对较大时，选择TDOA-AOA算法合适些．虽然给出了DOA算法的模型，但是由于当a＝1时，RSS算法即转化为DOA算法处理过程，故不在本文中推导算法处理过程．算法处理思想是根据测量结果得到的非线性方程转化为线性方程．而这些线性方程应用加权最小二乘法与拉格朗日乘法来处理［10-13］．

3 总结及展望

现有实现定位的两类算法:基于测距（Range-Based）和基于非测距（Range-Free）各有千秋．若仅采用基于非测距的算法虽然无需根据角度和距离等信息，可仅根据网络连通性等约束条件实现节点定位，节约了开支，但以牺牲了精度为代价．而基于测距的定位算法一般利用自身所配置的设备所拥有的一定测量技术来测量相关信息，例如距离、信号到达角度、深度等信息，它虽然能提供定位精度很高的定位效果，但是实现定位成本相对较高．因此通过比较与仿真得出了统一的用加权最小二乘法／受限制的加权最小二乘法来解决TDOD算法、AOA算法、RSS算法及TDOA-AOA算法．该算法是将根据测量结果得到的非线性方程转化为线性方程，而这些线性方程应用加权最小二乘法与拉格朗日乘法来处理，它可以很容易扩展到TDOA-AOA算法中.仿真结果已经证明了所述算法在噪声相对较小时，算法的性已经可以达到克拉美罗下界（CRLB）和无偏性和准确性.当然仍有部分内容有待进一步探讨和研究，如可将TDOA、RSS、TOD中受限制的加权最小二乘法转换成不受限制的算法改进.

致谢

本文得到湖北省教育科学“十二五”规划2013年度立项课题:地方性高校新兴交叉学科建设的研究--以网络科学为例（2013B060）项目资助，在此表示衷心的感谢.

［1］Akyildiz I．F．，．Su W，．Sankarasubramaniam Y，et al．A survey on sensor networks［J］．Communications Magazine IEEE，2002，40（8）:102-114．

［2］张兴如．无源定位及定位性能的分析［D］．成都:电子科技大学，2001．

ZHANG Xingru．Analysis of passive location and positioning performance．［D］.Chengdu:University of Electronic Science and Technology of China，2001．（in chineses）

［3］刘书静，罗海勇，吴彬．基于最小二乘测距定位算法信标最优部署模型［J］．计算机学报，2013，36（3）:562-576．

LIU Shu jing，LUOHaiyong，WUBing．Optimal landmark deployment patterns for range-based least squares localization［J］．Chinese Journal of Computers，2013，36（3）:562-576．（in chineses）

［4］马祖长，孙怡宁，梅涛．无线传感器网络综述［J］．通信学报，2004，25（4）:114-124.

MA Zuchang，SUN Yining，MEI Tao．Survey on wireless sensors network［J］．Journal on Communications，2004，25（4）:114-124．（in chineses）

［5］赵春梅，欧吉坤，袁运斌．基于单点定位模型的GALILEO及GPS-GALILEO组合系统的定位精度和可靠性的仿真分析［J］．科学通报，2005，50（8）: 811-818.

ZHAO Chunmei，OU Jikun，YUAN Yunbin．Single pointpositioningmodelbasedonGALILEO，The positioning accuracy of GPS-GALILEO combination systemandReliabilityanalysisofsimulation［J］．Chinese Science Bulletin，2005，50（8）:811-818．（in chineses）

［6］何佳鸿，张小明，王永恒．基于物联网空间划分的定位算法［J］．计算机应用，2012，32（12）:3517-3520．

HE Jiahong，ZHANG Xiaoming，WANG Yongheng．Positioning algorithm based on Internet of things spatial meshing［J］．JournalofComputerApplications，2012，32（12）:3517-3520．（in chineses）

［7］王文秀．无线传感器网络自定位算法研究［D］．大庆:东北石油大学，2013.

WANG Wenxiu．Research on localization algorithm for wireless sensor networks［D］．Daqing:Northeast Petroleum University，2013．（in chineses）

［8］郭龙江，李建中，李金宝．无线传感器网络若干定位算法的研究［J］．计算机工程与设计，2006，27（12）: 2114-2118.

GUO Longjiang，LI Jianzhong，LI Jinbao．Study to severalpositioningalgorithmsonwirelesssensor networks［J］．Computer Engineering and Design，2006，27（12）:2114-2118．（in chineses）

［9］金纯，叶诚，韩志斌，等．无线传感器网络中DV-Hop定位算法的改进［J］．计算机工程与设计，2013，34（2）:45-54．

JIN Chun，YE Cheng，HAN Zhibin etc．DV-Hop localization algorithm improvements in wireless sensor networks［J］．Computer Engineering and Design，2013，34（2）:45-54．（in chineses）

［10］李冬．基于DV-Hop的无线传感器网络定位［D］．南京:南京理工大学，2013．

LI Dong，Positioning based on DV-Hop for wireless sensor network［D］．Nanjing:Nanjing University of Science and Technology，2013．（in chineses）

［11］杨冕，秦前清．对传感器网络定位技术现状的研究［J］．微机发展，2005，15（3）:26-28．

YANG Mian，QIN Qianqing．Researchon current localization technology of sensor networks［J］．Microcomputer Development，2005，15（3）:26-28．（in chineses）

［12］Cheung K W，So H C．A multidimensional scaling framework for mobile location using time - of - arrival measurements［J］．IEEE Transactions on Signal Processing，2005，53（2）:460-470．

［13］Cheung K W，So H C，Ma W-K．A constrained Least squares approach to mobile positioning:algorithms and optimality，signal processing［J］．IEEE Transactions，2014，62（11）:2999-3012．

Simulation of target location algorithm for Internet of Things in Matlab

CHEN Xiang-yang1，KE wei1，DU Lian2，LIU Pei2，XU Ying3，SHEN Chao1
1.School of Computer Science and Engineering，Wuhan Institute of Technology，Wuhan 430074，China；2.The college of Post and Telecommunication of Wuhan Institute of Technology，Wuhan 430074，China；3.Science and Technology Department，Hubei Provincial Archives Bureau，Wuhan 430071，China

To solve the many problems faced in the location of Internet of Things，the classic positioning methods are studied．By the comparative analysis of the simulation results，an effectively method of estimated target location（least squares，maximum likelihood estimation and Lagrange combined positioning algorithm）were got，and an generalized weighted least square method／limited weighted least square method can be used to calculate various algorithm．The nonlinear equation obtained from the result of measurement can be transformed to linear equation．And then the linear equation can be solved with weighted Least squares and Lagrange algorithm．This method can be easily applied to other algorithm too．When noise is relatively low，the performance of the algorithm can reach the Cramer Rao lower bound and be unbiased．

positioning algorithm；least squares；maximum likelihood estimation；lagrange algorithm

TN643

A

10.3969/j.issn.1674-2869.2015.03.014

1674-2869（2015）03-0068-06

本文编辑：陈小平

2015-01-16

湖北省教育科学“十二五”规划2013年度立项课题（2013B060）

陈向阳（1969-），男，河南开封人，副教授，硕士.研究方向:网络通信工程、复杂网络、生物信息等．