基于改进Chan算法和多元Taylor算法的室内定位方法

陈大伟　钱路雁 　陈诗军　金玲飞　李俊强

摘要：随着5G时代的到来，人們对更精确，拓展性更好的定位系统的需求开始变得越来越迫切。本文提出了一种改进的融合定位算法。本文提出了使用模拟退火最优化算法对近距离情况下的Chan算法第一次初始值估计做了优化，并融合多元Taylor算法，充分利用了定位目标之间的距离关系，使得定位精度得到提高。

关键词：Chan算法;模拟退火算法;Taylor算法;室内定位算法

中图分类号：TP399         文献标识码： A

文章编号：1009-3044（2021）01-0011-05

Abstract： With the advent of 5G， the need for more accurate and scalable positioning systems is becoming more and more urgent. In this paper， we propose an improved fusion positioning algorithm. The simulated annealing optimization algorithm was used to optimize the first initial value estimation of the Chan algorithm in the case of close range， and the multivariable Taylor series expansion algorithm is integrated to make full use of the distance relationship between the positioning targets， so as to improve the positioning accuracy.

Key words： chan algorithm;simulated annealing algorithm;taylor algorithm;indoor location

1引言

随着5G时代的来临，以及信息技术软硬件的急速发展，获得更加精确、更加丰富的位置信息变得越来越容易。而且由于人们一天中大部分的时间都在室内，精确的室内位置信息对很多领域来说，其价值都是十分巨大的。由于位置信息的重要性，以及近年来对智能家居和类似扫地机器人这样的需求，室内定位领域的研究热度一直居高不下[1-4]。室外虽然有了GPS提供的高精度LOS（视距）定位，但由于GPS有着一定的局限性，如精度低等等，很多新的室内定位技术被发明了出来弥补GPS的缺陷，如： RFID（射频）定位、WiFi定位、基于WiFi指纹库的定位、蓝牙定位、超声波定位技术、超宽带（Ultra Wideband）技术、可见光定位技术等等，它们分别于有着各自的优点和缺陷[5-9]。

定位算法与最终定位的精确度密切相关。定位算法本质上是在于如何利用现实测量值，根据具体模型，高效高精度的解决一个超定的非线性方程组，从而获得较为精准的目标位置。定位基站接收的参数一般有RSSI（接收信号能量强度），AOA（信号到达的角度），TOA（信号到达的时间），TDOA（信号到达的时间差）。这四种方法各有特点。国内外目前应用最多的是TDOA以及TOA为基础的定位算法。

Chan算法是TDOA定位算法的一种[10]。其优势在于当测量误差服从高斯分布时，该算法定位精确，并且算法复杂度不高。但由于对于实际环境中的测量值很多时候并不会服从标准的高斯分布，此时Chan算法的性能会有显著的下降。

在传统的定位算法中，Taylor展开法是解非线性方程组的最佳解法之一[11]，Taylor算法有着较高的求解精度和较快的迭代速度，这是其成为最常用的定位算法的原因。Taylor算法的缺点主要有两点，其一是对初始值较敏感，迭代的初始值对Taylor算法的影响较大，第二是可能会出现不收敛的情况。解决方法一般是利用多种算法进行协同定位。先用一种算法得出定位初始值，再使用该初始值代入Taylor级数展开法得到精确解。近年来融合比较成功的是Chan算法与传统Taylor算法的协同定位算法[12]。最近，基于多元变量的Taylor算法被提出[13]，将定位目标与定位目标之间的位置信息充分地利用起来。

由于Chan算法主要步骤是两步最小二乘估计，当目标距离各个基站距离较近时，第一次最小二乘估算也需要一个估计初始值，才能求解初始解估计矩阵。在实际生活中，如室内定位场景，这样的情况是很常见的。

本文的改进Chan算法思路是通过使用模拟退火算法，搜索优质的初始解，用来辅助Chan算法来处理目标距离基站距离较近时的初始值估计，并融合多元变量Taylor算法，并根据几何位置关系，去除一些多余错误数据，进行精确定位。

2 Chan优化算法

2.1 Chan算法

TOA/TDOA定位模型是非常常用的高精度定位模型之一，通过基站发射某种信号（通常是电磁波信号），接收信号时通过时延估计算法得到信号的到达时间或者到达时间差，再通过乘以信号的传播速度获得与目标之间的距离，若假设经过时延估计后得到的实际测[ti，i=1，2，...，N]，则距离测量值为[δi=c?ti，i=1，2，...，N]，其中[c=299792458]m/s表示光速。

从而建立基站离目标的距离方程组就可以得到单目标的TOA定位模型，设[Ri]表示第[i]个定位基站与定位目标之间的距离测量值：

虽然[x0，y0，R0]不是相互独立的，Chan算法的核心思想是采用的两步加权最小二乘方法（WLS），先假设这两个中间变量是相互独立的，将非线性方程线性化，使用加权最小二乘获得他们的估计值，求得该估计值后再考虑他们之间的相互关系，这样就可以求解得到目标位置。于是，令

假设系统有着较高的信噪比，可以认为测量值为高斯数据，即他们服从近似的正态分布，由于噪声向量[n]也服从近似的正态分布，则可以得到关于误差的向量统计的关系为：

通过Chan算法可以看出，当目标距离各个基站距离较近时，第一次估算也需要一个估计初始值，才能求解初始解估计矩阵。在实际生活中，如室内定位场景，这样的情况是很常见的。

2.2基于模拟退火算法改进Chan算法

本文提出了使用模拟退火算法，搜索优质的初始解，用来辅助Chan算法来处理目标距离基站距离较近时的初始值估计。

常见的最优化方法有遗传算法、模拟退火算法和爬山算法，使用模拟退火算法的原因是其局部搜索能力强，运行时间较短，但由于之后有Taylor算法来加强定位的精度，所以模拟退火算法是平衡和效率和精确的最佳选择。

假设场所内共有N个基站，M个待测目标，对于每个待测目标，模拟退火算法的目标函数设置为：

3 融合多元Taylor算法

虽然Chan算法在测量误差服从高斯分布时，定位精确，并且算法复杂度不高，但现实情况下往往误差不服从标准的高斯分布，此时Chan算法的精度会有显著的下降，通常使用融合多种算法来实现，常见如Chan与Taylor算法的协同定位方法[12]。Taylor算法在信道条件较差时拥有较好的性能，并且由于其对初始值敏感，所以需要一个稍好的初始值作为算法的输入，所以将Chan算法与Taylor算法融合是正确的选择。近年来，多元Taylor算法被提出[13]，成功地将目标之间的位置信息利用起来，提高了Taylor算法的精度，所以本文提出了改进Chan算法与多元Taylor算法的融合算法。

3.1多元Taylor算法

设场所内共有N个基站，M个待测目标。由于传统的Taylor级数展开算法并没有将待测目标之间的测量距离值考虑在内，所以会损失一部分的有用信息，从而为导致定位的精度有所损失。

那么理论上[A，B]的距离测量值因为大圆半径与小圆半径之间，由于之前根据模拟退火的改进Chan算法得到了一个初始值，则代入初始值，计算各个基站距离该初始值的误差，并计算累积分布函数，将90%误差以上的误差去除，既可以换来一部分的性能提升，并且可以筛除一部分数据。

3.2 Taylor算法对初始值的敏感性研究

在100m×100m的室内均匀分布5个基站。假设TODA测量误差服从均值为零方差的高斯分布N（0，1），然后在平面内均匀的选择10201个不同的初始值，考察其对Taylor算法收敛性的影响。

在图2中，红色区域表示该区域内的初始值不收敛，可以简单地看出若收敛值选取在基站包围的凸多边形区域内，或者靠近真实值的位置，則Taylor算法收敛，否则则不一定收敛。

然后观察初始值对收敛速度的影响，依然在100m×100m的室内均匀分布5个基站，TODA测量误差服从均值为零方差的高斯分布N（0，1），待测目标的真实坐标为（40，40）。设[δi]表示Taylor算法在第[i]次迭代后，估计位置与真实位置的绝对距离误差。

从表1中可以看出，初始值越靠近真实值，则算法的收敛速度越快。

3.3 算法流程

4 仿真分析

在100m×100m的平面内随机放置20个未知位置的待测目标，5个已知位置的节点。假设距离测量误差服从10m，方差为[δ2=1]的指数分布。

通过仿真分析可以看出，本文提出的算法在信道条件不够好，并且基站较少但有着多个待测目标时有着更高的定位精度，现实场景中适用性广泛。

5结语

由于人们一天中大部分的时间都是在室内的，精确的室内位置信息对很多领域来说，其价值十分巨大。不仅会给人们生活带来很大的便利，让人们再也不会害怕在大型室内建筑里迷路，如：商场、医院、体育馆、博物馆等;也会给火灾、地震等自然灾害中的救援人员带来不可估计的价值;同时也会大大增强虚拟现实、增强现实、体感游戏等需要超高精度定位的娱乐设备的沉浸感。本文提出了使用模拟退火算法来优化Chan算法在近距离的情况下第一次最小二乘估计初始值的选择，并融合了多元Taylor算法，将目标之间的位置信息利用起来，完成高精度的定位方法。但是本算法的局限在假设测量误差服从同一分布。未来可以从，若是每个定位基站的误差参数不服从同一分布出发，研究如何从算法层面更进一步的提升该情况下的定位精度。

参考文献：

[1] Porcino D，Hirt W.Ultra-wideband radio technology：potential and challenges ahead[J].IEEE Communications Magazine，2003，41（7）：66-74.

[2] 李珊，张春明，汪卫国.5G商用起步，融合应用蓬勃兴起[J].中兴通讯技术，2019，25（6）：2-7.

[3] 严斌峰，袁晓静，胡博.5G技术发展与行业应用探讨[J].中兴通讯技术，2019，25（6）：34-41.

[4] Miyazawa S，SongX，Xia T Q，etal.Integrating GPS trajectory and topics from Twitter stream for human mobility estimation[J].Frontiers of Computer Science，2019，13（3）：460-470.

[5] 赵锐，钟榜，朱祖礼，等.室内定位技术及应用综述[J].电子科技，2014，27（3）：154-157.

[6] 曹蓟光，张健.发达国家宽带战略及我国与其发展差距分析[J].信息通信技术，2011，5（1）：18-23.

[7] 李俊.基于RFID的室内定位系统的研究和设计[D].成都：电子科技大学，2009.

[8] 潘德宇.基于ZigBee的医院室内定位系统应用框架研究与实现[D].上海：上海交通大学，2011.

[9] Scholtz R A， Weaver R， Homier E， et al. UWB radio deployment challenges[C]. IEEE International Symposium on PersonalIndoor and Mobile Radio Communications. London， UK， 2000： 620-625. doi： 10.1109/PIMRC.2000.881497.

[10] Chan Y T，Ho K C.A simple and efficient estimator for hyperbolic location[J].IEEE Transactions on Signal Processing，1994，42（8）：1905-1915.

[11] 李莉，邓平，刘林.Taylor级数展开法定位及其性能分析[J].西南交通大学学报，2002，37（6）：684-688.

[12] 刘林，邓平，范平志.基于Chan氏算法和Taylor级数展开法的协同定位方法[J].电子与信息学报，2004，26（1）：41-46.

[13] 李瑞雪，夏斌，袁文浩，等.基于多元变量Taylor级数展开模型的定位算法[J].计算机应用研究，2016，33（6）：1853-1856，1881.

【通联编辑：梁书】