《武汉工程大学学报》 2015年03期
68-73
出版日期：2015-04-23
ISSN:1674-2869
CN:42-1779/TQ
物联网目标定位算法的ＭATLAB仿真
０ 引 言基于物联网的无线定位算法是由已知坐标信息的锚节点和未知节点构成，各节点可以通过相互协调工作来发送、接受、处理、存储数据，通过无线方式连接，进而共同完成特定的应用任务. 算法允许位置任意存放，灵活度较高，相比于基于非测距的节点相比，由于可随意放置，精确度较高而用途广泛. 因为存在一定的冗余度，即使大部分不能工作，只要还有少许节点正常工作，仍可以获得较高的定位精度. 基于非测距定位算法，以大量简单的定位节点获得估计定位置，而基于测距的定位算法以少量复杂的定位节点换取较高的定位精度［１－２］. 通过ＭATLAB软件仿真结果对比得到了实用的基于测距的目标定位算法即ＴＯＡ、ＴＤＯＡ、ＡＯＡ、ＲＳＳ及ＴＤＯＡ－ＡＯＡ联合算法. 在定位系统中全球卫星定位系统（ＧＰＳ）占全球定位应用中绝大部分市场，但由于成本、体积等因素限制使得这四大系统均不适用于低成本的物联网应用，为此需要针对物联网定位区域相对较小、低成本等特性设计合适的定位算法及其应用. 无线定位算法可大体分为两类，基于测距的定位算法和基于非测距的定位算法. 基于非测距的定位算法主要有质心算法、ＤＶ－Ｈｏｐ算法、凸规划定位算法、ＡＰＩＴ算法. 着重介绍基于测距的定位算法ＴＯＡ、ＤＴＯＡ、ＲＳＳ、ＡＯＡ及ＴＤＯＡ－ＡＯＡ算法. 具体实现的主要功能如下：主要实现基于测距的算法，包含ＴＯＡ、ＤＴＯＡ、ＲＳＳ、ＡＯＡ及ＴＤＯＡ－ＡＯＡ算法的定位，每个算法首先会建立相应的模型，考虑误差以便更加符合实际情况.其次用ＴＯＡ、ＤＴＯＡ、ＲＳＳ、ＤＴＯＡ－ＡＯＡ测量的值运用受限地加权最小二乘法（ＣＷＬＳ）建立方程，接下来利用ＡＯＡ结合加权最小二乘法、拉格朗日乘法来建立方程，以及最大似然估计等方法处理方程，这样定位点比较精确. 通过求定位误差方差的克拉美罗下界（ＣＲＬＢ）来比较定位算法性能［３－４］. １ 定位算法的模型１．１ ＴＤＯＡ定位算法ＴＤＯＡ算法定位原理是首先选择一个基站为参考基站，运动站方发送无线信号，可以获得这个参考基站ＢＳ１与其他每个基站ＢＳｉ接收信号的时间差，从而知道了ＢＳｉ与ＢＳ１基站到移动站之间的距离差. 通过这些几何关系建立ＢＳｉ与ＢＳ１之间双曲线，双曲线焦点为这两个基站，根据双曲线的点到焦点距离差为一个定值，可以确定运动站的可能存在轨迹，通过两个以上的双曲线即可确定移动站的坐标. ＴＤＯＡ算法几何模型如图１所示.图１ ＴＤＯＡ几何模型Ｆｉｇ．１ Ｔｈｅ ｇｅｏｍｅｔｒｉｃ ｍｏｄｅｌ ｏｆ ＴＤＯＡ假设将第一个基站作为参考基站，将模型归纳成公式（1）形式： ｒＴＤＯＡ，ｉ=（di-d1）+ｎＴＤＯＡ，ｉ=■- ■+ｎＴＤＯＡ，ｉ （１）而ｎＴＤＯＡ，ｉ代表噪声、即每个测量距离差值的误差. 如果ｒＴＤＯＡ，ｉ直接由ＤＯＡ处获得的数据获得，那么 ｎＴＤＯＡ，ｉ＝ｎＤＯＡ，ｉ－ｎＤＯＡ，ｌ如果没有误差，可将公式（１）改写成ｒＴＤＯＡ，ｉ=■-■?圯 ｒＴＤＯＡ，ｉ+■=■（２）令R=■，带入方程，然后对公式（２）两边平方，可以得到（ｘ－ｘ１）（ｘｉ－ｘ１）＋（ｙ－ｙ１）（ｙｉ－ｙ１）＋ｒＴＤＯＡ，ｉR＝ ０．５*［（xi-x1）２＋（yi-y1）２－r■■］（３）将以上对所有的ｉ，方程改成矩阵的形式 Ｇｇ＝ｈ （４） 其中: Ｇ＝x2-x1 y2-y1 rTDOA,i■ ■ ■xn-x1 yn-y1 rTDOA,i ｈ＝■（x2-x1）２＋（y2-y1）２－r■■ ■ （xn-x1）２＋（yn-y1）２－r■■ （５）而参数向量ｇ＝［ｘ－ｘ１，ｙ－ｙ１，Ｒ］Ｔ同时（x2-x1）２＋（y2-y1）＝Ｒ２，可以将此公式改写成 ｇＴＭｇ＝０ （６）其中Ｍ＝ｄｉａｇ（［１，１，－１］）. 如此一来，对于受限制的加权最小二乘法的矩阵转化为拉格朗日乘法来求解. ?灼TDOA（g,?浊）=(Gg-h)T?酌-1(Gg-h)+?浊gTMg（７）求出此方程极值点，取值使公式（７）最小时的ｇ即可. １．２ ＲＳＳ定位算法在测量信号时，如果没有出现测量信号的误差，由移动站发送信号、基站ｉ接收信号，接受的信号功率为Ｐ■■，这可以建立以下的模型［５］ Ｐ ■■=ki■ （８）其中Ｐ ■■指的发送频率，ki指的可以影响接收信号功率的参数，ａ指的是传输参数，对于固定的空间，ａ的值也是确定的，在真空中，ａ＝２，但是在某些环境中，ａ的取值可以由３到６的变化. 对于有测量误差等因数影响下，则定位模型也会随之改变.rＲＳＳ，ｉ=ki■＋ｎＲＳＳ，ｉ=［（x-xi）２＋（y-yi）２］■＋nＲＳＳ，ｉ （９）ｎＲＳＳ，ｉ代表着误差，如果ａ＝１，那么该模型ＲＳＳ与ＤＯＡ模型一样. 如果ＲＳＳ定位算法没有测量误差，公式（９）可以变成公式（１０）形式［６］： rＲＳＳ，ｉ=da/2=［（x-xi）２＋（y-yi）２］■（１０）对其公式（１０）转变得 r■■=R2-2xxi-2yyi+(x■■+y■■)?圯 xxi+yyi-0.5R2=0.5(x■■+y■■-r■■)（１１）其中Ｒ＝■，这样做的好处是将非线性方程转化为线性方程. 其中对于所有的ｉ，可以将其转化为矩阵形式，表达式如下： Ａθ＝ｂ （１２）其中： A＝ x1 y1 -0.5■ ■ ■ xn yn -0.5 ?兹＝ x yR2 b＝■x1２＋y1２－r■■ ■ xn２＋yn２－r■■参照ＴＤＯＡ方法，由于Ａθ＝ｂ无解，对其进行受限制的加权最小二乘法的方差进行处理，得到公式（13）为 （Ａ■－b）Ｔ?鬃－１（Ａ■－b） （１３）其中γ－１是相应的加权矩阵，并且受约束条件Ｒ＝■转化为矩阵形式如下： qT■+■TP■=0（１４）其中： ■＝ ■ ■■2 Ｐ＝1 0 00 1 00 0 0 ｑ＝ 0 0-1求式（１２）最小值，应用拉格朗日乘法列方程如下：?灼RSS(■,?姿)=（Ａ■－b）Ｔ?鬃－１（Ａ■－b）+?姿qＴ■+■ＴP■（１４）求出方程（１４）极值点，取值使公式（１３）最小时的ｇ即可. １．３ ＡＯＡ定位算法ＡＯＡ算法测量的由移动站发送到基站ｉ的信号方向，这个方向与（ｘ，ｙ）及（ｘｉ，ｙｉ）相关，方向角度有?准i表示，有公式（１５）［７－８］： Ｔａｎ（?准i）＝■ （１５）图２为ＡＯＡ算法角度测量几何图形. 图２ ＡＯＡ算法定位的几何图形Ｆｉｇ．２ Ｔｈｅ ｇｅｏｍｅｔｒｉｃ ｍｏｄｅｌ ｏｆ ＡＯＡ ａｌｇｏｒｉｔｈｍ ｌｏｃａｌｉｚａｔｉｏｎ一般来说，?准i由第 ｉ个基站到移动站之间的直线与ｘ轴之间形成的夹角，如果存在误差，那么测量的角度由ｒＡＯＡ，ｉ表示，可以根据测量的角度建立如下模型： ｒＡＯＡ，ｉ＝?准i＋nＡＯＡ，ｉ＝tａｎ-1(■)+nＡＯＡ，ｉ （１６）其中nＡＯＡ，ｉ代表着测量rＡＯＡ，ｉ时附带的误差. 对于ＡＯＡ算法，如果没有出现误差干扰，则公式（１６）可以写成： tａｎ(rTDOA,i)=■=■（１７）可以将公式（１７）转化为xsin(rＡＯＡ，ｉ)-ycos(rＡＯＡ，ｉ)=xisin(rＡＯＡ，ｉ)-yicos(rＡＯＡ，ｉ)（1８）对于所有的ｉ，以向量的形式写出来，可以得到公式（１9）： Ｈｘ＝ｋ （１９）其中： H= sin(rＡＯＡ，1) -cos(rＡＯＡ，1) ■ ■ sin(rＡＯＡ，n) -cos(rＡＯＡ，n) k= x1sin(rＡＯＡ，1) -y1cos(rＡＯＡ，1) ■ ■ xnsin(rＡＯＡ，n) -yncos(rＡＯＡ，n) （２０）如同ＴＤＯＡ，ＲＳＳ一样，为了提高运动站定位精度，用加权最小二乘法，可以建立如下方程：x=argmin(Hx-k)TΩ-1(Hx-k)=（HTΩ-1H）HTΩ-1H（２１）其中Ω－１是加权矩阵，ｘ＝（ｘ，ｙ）Ｔ，根据最佳线性无偏估计（ＢＬＵＥ）来求Ω. １．４ ＴＤＯＡ－ＡＯＡ定位算法显而易见，若把两者算法混合，很可能提高算法的精度，或者可以减少使用基站的数量. 在可能混合算法中，ＡＯＡ和ＴＤＯＡ最容易混合起来，为了能够定位，需要重写公式（１７）定位模型，两边同时加变量：yicos(rＡＯＡ，1)-xisin(rＡＯＡ，n)得到如下等式［９－１０］： (x-xi)sin(rＡＯＡ，i)-(y-y1)cos(rＡＯＡ，i)= (xi-x1)sin(rＡＯＡ，i)-(yi-y1)cos(rＡＯＡ，i)（２２）把式（３）和式（１７）合并到一个向量中，可以转化为如下的等式： Ｂｇ＝ｗ （２３）式（２３）中： B= GH 0n w=hk′其中： k′= 0n(x2-x1)sin(rＡＯＡ，2)-(y2-y1)cos(rＡＯＡ，2) ■(xn-x1)sin(rＡＯＡ，n)-(yn-y1)cos(rＡＯＡ，n)0ｎ指ｎ×１的零向量，要求合适的ｇ只需保证取值最小. （Ｂｇ－ｗ）Ｔｗ－１（ｂｇ－ｗ） （２４）并保证约束条件 ｇＴＭｇ＝０ （２５）其中，矩阵ｗ是相应的加权矩阵. 然后根据第1．１节求ＴＤＯＡ中ｇ的过程来求ＴＤＯＡ－ＡＯＡ中的ｇ. 同样的道理，把ＡＯＡ与ＲＳＳ，或者ＴＯＡ结合，也可以提高单个算法的精度. １．５ 各种定位算法的克拉美罗下界对于方差达到克拉美罗下界（ＣＲＬＢ）的无偏估计称为有效方差. 克拉美罗下界表示定位误差的最小值，通过比较克拉美罗下界和提出的算法来验证算法的精度. ２ 定位算法仿真及分析下面的仿真结果由于要比较各种定位算法在噪声较小时的定位精度，故对仿真图片图３进行放大. 由图４可看出，当噪声较小时，ＲＳＳ定位精度比较准确，甚至超过了ＴＤＯＡ－ＡＯＡ联合算法，但是ＲＳＳ定位算法对误差也很敏感，当干扰功率大于－３０ｄＢ时，定位误差突然变大，但同比其他算法，误差也基本保持比较低，整体上说该算法仍是性能比较好的算法. 接着定位第二准确的是ＴＤＯＡ－ＡＯＡ，由图４所示，ＴＤＯＡ－ＡＯＡ算法定位精度相对于ＴＤＯＡ算法、ＡＯＡ算法都有所提高，在ＡＯＡ部分测量误差干扰为－３０ｄＢ，该算法误差也比较低，精度比较好. ＴＤＯＡ－ＡＯＡ、ＴＤＯＡ，ＡＯＡ算法对噪声有一定的抵抗力，当噪声功率提高时，定位精度也随之平稳地下降. 当误差较大时，ＲＳＳ与ＡＯＡ定位误差相对较小，即精度较高. 图３ 各种算法定位坐标变化Ｆｉｇ．３ Ｔｈｅ ｃｏｏｒｄｉｎａｔｅ ｖａｒｉａｔｉｏｎ ｏｆ ｌｏｃａｌｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ图４ 各种算法的定位噪声与定位误差变化Ｆｉｇ．４ Ｔｈｅ ｐｏｓｉｔｉｏｎｉｎｇ ｎｏｉｓｅ ａｎｄ ｐｏｓｉｔｉｏｎｉｎｇ ｅｒｒｏｒｖａｒｉａｔｉｏｎ ｏｆ ｐｏｓｉｔｉｏｎｉｎｇ ａｌｇｏｒｉｔｈｍｓ因此，总的来讲当噪声都充分小时，ＴＤＯＡ－ＡＯＡ算法、ＴＤＯＡ算法、ＡＯＡ算法、ＲＳＳ算法定位都可以很好地定位.当噪声变大时误差超过－３０ ｄＢ，相当于测量距离误差定位精度都严重下降. 在实际工程运用中，就要根据实际情况选择定位算法. 当噪声较小时，选择ＲＳＳ算法比较好，当噪声相对较大时，选择ＴＤＯＡ－ＡＯＡ算法合适些. 虽然给出了ＤＯＡ算法的模型，但是由于当ａ＝１时，ＲＳＳ算法即转化为ＤＯＡ算法处理过程，故不在本文中推导算法处理过程. 算法处理思想是根据测量结果得到的非线性方程转化为线性方程. 而这些线性方程应用加权最小二乘法与拉格朗日乘法来处理［１０－１３］. ３ 总结及展望现有实现定位的两类算法：基于测距（Ｒａｎｇｅ－Ｂａｓｅｄ）和基于非测距（Ｒａｎｇｅ－Ｆｒｅｅ）各有千秋. 若仅采用基于非测距的算法虽然无需根据角度和距离等信息，可仅根据网络连通性等约束条件实现节点定位，节约了开支，但以牺牲了精度为代价. 而基于测距的定位算法一般利用自身所配置的设备所拥有的一定测量技术来测量相关信息，例如距离、信号到达角度、深度等信息，它虽然能提供定位精度很高的定位效果，但是实现定位成本相对较高. 因此通过比较与仿真得出了统一的用加权最小二乘法／受限制的加权最小二乘法来解决ＴＤＯＤ算法、ＡＯＡ算法、ＲＳＳ算法及ＴＤＯＡ－ＡＯＡ算法. 该算法是将根据测量结果得到的非线性方程转化为线性方程，而这些线性方程应用加权最小二乘法与拉格朗日乘法来处理，它可以很容易扩展到ＴＤＯＡ－ＡＯＡ算法中. 仿真结果已经证明了所述算法在噪声相对较小时，算法的性已经可以达到克拉美罗下界（ＣＲＬＢ）和无偏性和准确性.当然仍有部分内容有待进一步探讨和研究，如可将ＴＤＯＡ、ＲＳＳ、ＴＯＤ中受限制的加权最小二乘法转换成不受限制的算法改进. 致 谢本文得到湖北省教育科学“十二五”规划２０１３年度立项课题：地方性高校新兴交叉学科建设的研究－－以网络科学为例（２０１３Ｂ０６０）项目资助，在此表示衷心的感谢.