基于改进Chan算法和多元Taylor算法的室内定位方法 陈大伟1，钱路雁2，陈诗军1，金玲飞2，李俊强1
（1.移动网络和移动多媒体技术国家重点实验室中兴通讯股份有限公司，广东深圳518057；2.上海市智能信息处理重点实验室复旦大学计算机科学技术学院，上海200082）
摘要：随着5G时代的到来，人们对更精确，拓展性更好的定位系统的需求开始变得越来越迫切。本文提出了一种改进的融合定位算法。本文提出了使用模拟退火最优化算法对近距离情况下的Chan算法第一次初始值估计做了优化，并融合多元Taylor算法，充分利用了定位目标之间的距离关系，使得定位精度得到提高。 关键词：Chan算法；模拟退火算法；Taylor算法；室内定位算法
中图分类号：TP399文献标识码:A
文章编号：1009-3044(2021)01-0011-05
苏拿
开放科学（资源服务）标识码（OSID）:
Indoor Location based on Improved Chan Algorithm and Taylor Algorithm
CHEN Da-wei1,QIAN Lu-yan2,CHEN Shi-jun1,JIN Ling-fei2,LI Jun-qiang1
(1.State Key Laboratory of Mobile Network and Mobile Multimedia,Zhongxing Telecommunication Equipment Corporation,Shen⁃zhen518057,China;2.Shanghai Key Laboratory of Intelligent Information Processing,School Computer Science,Fudan University, Shanghai200082,China)
Abstract:With the advent of5G,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 opti⁃mize 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]。其优势在于当测量误差服从高斯分布时，该算法定位精确，并且算法复杂度不高。但由于对于实际环境中的测量值很多时候并不会服从标准的高斯分布，此时Ch
an算法的性能会有显著的下降。
在传统的定位算法中，Taylor展开法是解非线性方程组的最佳解法之一[11]，Taylor算法有着较高的求解精度和较快的迭代速度，这是其成为最常用的定位算法的原因。Taylor算法的缺点主要有两点，其一是对初始值较敏感，迭代的初始值对Taylor算法的影响较大，第二是可能会出现不收敛的情况。解决方法一般是利用多种算法进行协同定位。先用一种算法得出定位初始值，再使用该初始值代入Taylor级数展开法得到精
收稿日期：2020-10-10
基金项目：国家自然科学基金(11871154)；中兴产学研项目
作者简介：陈大伟（1988—），男，黑龙江人，无线算法工程师，研究方向：无线室内定位；钱路雁（1995—），男，江苏人，硕士研究生，研究方向：应用算法与应用密码；陈诗军（1972—），男，山东人，技术预研工程师，研究方向：无线室内定位；金玲飞（1986—），女，浙江人，副教授，研究方向：编码与密码；李俊强（1990—），男，广东人，无线算法工程师，研究方向：无线室内定位。
Computer Knowledge and Technology 电脑知识与技术第17卷第1期(2021年1月)
确解。近年来融合比较成功的是Chan 算法与传统Taylor 算法的协同定位算法[12]。最近，基于多元变量的Taylor 算法被提出[13]，将定位目标与定位目标之间的位置信息充分地利用起来。
由于Chan 算法主要步骤是两步最小二乘估计，当目标距离各个距离较近时，第一次最小二乘估算也需要一个估计初始值，才能求解初始解估计矩阵。在实际生活中，如室内定位场景，这样的情况是很常见的。
本文的改进Chan 算法思路是通过使用模拟退火算法，搜索优质的初始解，用来辅助Chan 算法来处理目标距离距离较近时的初始值估计，并融合多元变量Taylor 算法，并根据几何位置关系，去除一些多余错误数据，进行精确定位。
2Chan 优化算法
2.1Chan 算法
TOA/TDOA 定位模型是非常常用的高精度定位模型之一，通过发射某种信号（通常是电磁波信号），接收信号时通过时延估计算法得到信号的到达时间或者到达时间差，再通过乘以信号的传播速度获得与目标之间的距离，若假设经过时延估计后得到的实际测t i ,i =1,2,...,N ，则距离测量值为δi =c ⋅t i ,i =1,2,...,N ，其中c =299792458m/s 表示光速。
老板山从而建立离目标的距离方程组就可以得到单目标的TOA 定位模型，设R i 表示第i 个定位与定位目标之间的距离测量值：
R i =δi =
(x i -x 0)2+(y i -y 0)2,i =1,2,...,N
（1）
其中要定位目标的位置为s 0=(x 0,y 0)。
R i 2=(x i -x 0)2+(y i -y 0)2=K i -2x i x 0-2y i y 0+x 02+y 02（2）
中国药典2005版其中K i =x i 2+y i 2，由于平方项的存在，使得上述公式成
为非线性方程，通过令R 02=x 02+y 02得到线性方程为：
R i 2-K i =-2x i x 0-2y i y 0+R 0
（3）
虽然x 0,y 0,R 0不是相互独立的，Chan 算法的核心思想是采
用的两步加权最小二乘方法(WLS ），先假设这两个中间变量是
相互独立的，将非线性方程线性化，使用加权最小二乘获得他们的估计值，求得该估计值后再考虑他们之间的相互关系，这样就可以求解得到目标位置。于是，令
TIMEARh =éëêêêêùûúúúúR 12-K 1R 22-K 2⋮R N 2-K N ,G a =éëêêêêêùû
úúúúú-2x 1-2y 11-2x 2-2y 21⋮⋱⋮-2x N -2y N 1,Z a =éëêêêêùûúúúúx y R （4）其中x ,y 和R 分别是x 0,y 0,R 0的估计值，且有：
R =x 2+y 2
（5）
定义噪声的误差向量为：
ψ=h -G a Z a （6）
假设系统有着较高的信噪比，可以认为测量值为高斯数据，即他们服从近似的正态分布，由于噪声向量n 也服从近似的正态分布，则可以得到关于误差的向量统计的关系为：
ψ=2c B n +c 2n ⋅n （7）
其中，B =diag {r 1,r 2,...,r N },r 1,r 2,...,r N 定位i 与定位目标的真实距离。因此B T =B 。
R i =r i +c n i （8）由于实际应用场景中，c n i ≪r 成立，则可以忽略式(7)的尾
项，将误差向量变成随机向量，误差向量可写成如下形式：
ϕ=E (ψψT )≈4c 2BQB
（9）
其中Q =diag {σ12
,σ22
,...,σN 2
}是测量值的协方差矩
阵，先假设Z a 中的各个量相互独立，用加权最小二乘得到：
Z a =(G a T ϕ-1
G a )-1G a T ϕ-1h （10）
由于B 中有定位目标和定位之间的距离，因此ϕ是个未知量，接下来是计算ϕ的问题。
若定位目标与定位距离较远时，则可以近似认为R 1
与R i 相等，所以在估计ψ时，可以使用R 1I 近似的替换B =
diag {r 1,r 2,...,r N }中位i 与定位目标的真实距离，所以可以
将式(10)近似的化简为为：
Z a ≈(G a T Q -1G a )-1G a T Q -1h
（11）
若定位目标距离定位较近时，则同样可以利用上述公式得到一个估计解，使用初始的估计解和定位的坐标，计算出近似的定位与定位目标的“真实”距离，从而得到B 矩阵，然后再使用式(10)得到第一次的加权最小二乘结果。
由于第一次加权最小二乘时没有x ,y ,R 考虑之间的关系，第二次加权最小二乘中将会考虑，从而实现更高的定位精度。利用第一次估计值，构造一组误差方程组进行第二次估计。
{
Z 1=x 0+e 1Z 2=y 0+e 2Z 3=R 0+e 3
（12）其中Z i 表示Z a 中的第i 分量，e i 表示Z a 的估计误差，定义
新的误差向量：
ψ'=h'-G 'z '（13）
其中：
h '=éëêêêêùû
úúúú(Z 1-X 1)2
(Z 2-Y 1)2Z 32,G '=éëêêùûúú100111,z '=éëêùûú(x 0-X 1)2(y 0-Y 1)2（14）其中S =(X 1,Y 1)代表1的已知坐标，
ψ'的协方差矩阵可以表示为：
φ'=E (ψ'ψ'T )=4B 'Cov(Z )B '
（15）
其中
B '=diag {x 0-X 1,y 0-Y 1,R 0},Cov(Z )=E (ee T )。
同样采用之前的方法估计，得到：
Z '=(G 'T
φ'-1G ')-1G 'T φ'h '
（16）
最后得到最终的估计位置Z =±Z '+S 。通过Chan 算法可以看出，当目标距离各个距离较近时，第一次估算也需要一个估计初始值，才能求解初始解估计矩阵。在实际生活中，如室内定位场景，这样的情况是很常见的。
2.2基于模拟退火算法改进Chan 算法
本文提出了使用模拟退火算法，搜索优质的初始解，用来
辅助Chan 算法来处理目标距离距离较近时的初始值估计。
常见的最优化方法有遗传算法、模拟退火算法和爬山算法，使用模拟退火算法的原因是其局部搜索能力强，运行时间较短，但由于之后有Taylor 算法来加强定位的精度，所以模拟退火算法是平衡和效率和精确的最佳选择。
假设场所内共有N 个，M 个待测目标，对于每个待测目标，模拟退火算法的目标函数设置为：
J (ω)=∑i =1N
|
|R i -R i '其中R i 为目标与已知的距离估计值，
R i '为测量值。
Computer Knowledge and Technology 电脑知识与技术
第17卷第1期(2021年1月)
目标函数的含义为，使用估计的待测目标坐标求出的R i 与测量值R i '差距的绝对值越小，则估计的坐标越准确。
算法伪代码：
算法1改进Chan 算法输入：ω：表示当前坐标;r ：用于控制降温的快慢;
T max ：系统的初始温度，系统初始应该要处于一个高温的状态;T min ：系统温度的下限;k max ：迭代次数;
输出：ω;
1：随机生成初始解ω,k ←0,T ←T max ;2:while T >T max do 3:if k >k max then 4:k ←0,T ←rT max ;5:else
6：随机产生扰动生成ω';7:ΔJ =J (ω')-J (ω)
8:if ΔJ <0then
9:ω←ω',T ←rT ,k ←k +1;
10:else if 满足Metropolis 准则then 11:ω←ω',T ←rT ,k ←k +1;
12:end if
13:end if
14:end while
15：利用ω求出Chan 算法的矩阵B ，再求出ϕ;16：求出第一次最小二乘解Z 0;
17：代入剩下的Chan 算法步骤得到坐标估计值ω;
3融合多元Taylor 算法
虽然Chan 算法在测量误差服从高斯分布时，定位精确，并
且算法复杂度不高，但现实情况下往往误差不服从标准的高斯分布，此时Chan 算法的精度会有显著的下降，通常使用融合多种算法来实现，常见如Chan 与Taylor 算法的协同定位方法[12]。Taylor 算法在信道条件较差时拥有较好的性能，并且由于其对初始值敏感，所以需要一个稍好的初始值作为算法
的输入，所以将Chan 算法与Taylor 算法融合是正确的选择。近年来，多元Taylor 算法被提出[13]，成功地将目标之间的位置信息利用起来，提高了Taylor 算法的精度，所以本文提出了改进Chan 算法与多元Taylor 算法的融合算法。3.1多元Taylor 算法
avmen设场所内共有N 个，M 个待测目标。由于传统的Tay⁃lor 级数展开算法并没有将待测目标之间的测量距离值考虑在内，所以会损失一部分的有用信息，从而为导致定位的精度有所损失。
原本的Taylor 算法只考虑了待测目标与之间的距离关系，即：
ìí
îïï
ï
ïR i ,j =(x 1-X j )2+(y i -Y j )2,i <j ⋮R M ,N
=(x M -X N )2+(y M -Y N )2
（17）其中R i ,j 表示待测目标与已知之间的距离测量值。为了让定位更精确，基于多元变量的Taylor 算法被提出[9]，加入了待测目标之间的距离测量值建立方程组。
ìí
îïï
ïïR'i ,j =(x i -x j )2+(y i -y j )2,i <j
⋮R'
M -1,M =(x M -1-x M )2+(y M -1-y M )
2（18）其中(x i ,y i )表示待测目标的坐标值，
(X i ,Y i )表示已知的坐标值，
R'i ,j 表示待测目标之间的距离测量值，R i ,j 表示待测目标与已知之间的距离测量值。
在待测目标的初始值(x 01,y 01),...,(x 0M ,y 0
M )处进行泰勒级数
展开，去除二阶以上分量，得到方程组。
ì
íî
ïïïïïïïïïïïïïïïïïïïïïïïïïïïïïïïï
R'-R '=Δx (x 0-x 0)R '+Δy (y 0-y 0)R '-Δx (x 0-x 0)R '-Δy (y 0-y 0
)R '+e ⋮R'-R '=Δx (x 0-x 0)R '+Δy (y 0-y 0)R '-Δx (x 0-x 0)R '-Δy (y 0-y 0)R '+e R -R =Δx (x 0-X )R +Δy (y 0
-Y )R +e'⋮R -R =Δx (x 0-X )R +Δy (y 0-Y )R +e'整理后得到定位模型：
h =G Δ+E （19）
对式(19)使用加权最小二乘法（WLS ），可以得到对Δ的估计：
Δ=(G T Q -1G )-1G T Q -1h （20）
其中Q 代表TDOA 测量值的协方差矩阵。在第二次递归
计算中，令
éëêêêêêêùû
úúúúúúx 1
1y 11⋮x 1M y 1M =éëêêêêêêùû
úúúúúú
x 0
1
+Δx 1y 01+Δy 1⋮x 0
M +Δx M y 0M
+Δy M （21）
重复计算多次，直到Δx i 和Δy i 都足够小，满足某个设定的
门限值ε：
∑i =1
M (||Δx i
+||Δy i
)<ε
（22）
由于测量值可能会有NLOS
或者多径带来的延时误差，并且后Taylor 级数展开算法对初始值敏感，所以在得到初始的估计值之后，开始Taylor 算法的之前需要将误差数据进行抛弃处理。
图1理论距离测量值范围
图1中A,B 为，T 为真实目标，e 为测量误差的期望，圆的方程为：
R i ,A =(x i -X A )2+(y i -Y A )2,R i ,B =(x i -X B )2+(y i -Y B )2
（23）
那么理论上A ,B 的距离测量值因为大圆半径与小圆半径之间，由于之前根据模拟退火的改进Chan 算法得到了一个初始值，则代入初始值，计算各个距离该初始值的误差，并计算累积分布函数，将90%误差以上的误差去除，既可以换来一
Computer Knowledge and Technology 电脑知识与技术第17卷第1期(2021年1月)
部分的性能提升，并且可以筛除一部分数据。3.2Taylor 算法对初始值的敏感性研究
在100m×100m 的室内均匀分布5个。假设TODA 测量误差服从均值为零方差的高斯分布N(0,1)，然后在平面内均匀的选择10201个不同的初始值，考察其对Taylor 算法收敛性
的影响。
图2不同的初始值对Taylor 算法收敛性的影响
在图2中，红区域表示该区域内的初始值不收敛，可以简单地看出若收敛值选取在包围的凸多边形区域内，或者靠近真实值的位置，则Taylor 算法收敛，否则则不一定收敛。
然后观察初始值对收敛速度的影响，依然在100m×100m 的室内均匀分布5个，TODA 测量误差服从均值为零方差的高斯分布N(0,1)，待测目标的真实坐标为(40,40)。设δi 表示Taylor 算法在第i 次迭代后，估计位置与真实位置的绝对距离误差。
表1初始值对Taylor 算法收敛速度的影响
Initial value (40,70)(60,20)(30,40)(40,41)
δ1
16.334917.57354.03590.8554
δ2
12.47270.83290.77310.8005
δ3
1.51260.86430.80300.8023
δ4
0.88050.80010.80300.8023
δ5
0.79930.80230.80300.8023
从表1中可以看出，初始值越靠近真实值，则算法的收敛
速度越快。3.3
算法流程
图3算法流程图
算法步骤：
1.随机生成初始解ω，并计算目标函数J (ω)，当前迭代次
数k =0，当前温度t 0=T max ，
r ∈(0,1)用来控制降温退火。2.扰动产生新解ω'，并计算目标函数J (ω')。3.计算增量ΔJ =J (ω')-J (ω)。
4.如果ΔJ <0，则接受新解ω←ω',k ←k +1，降低温度t k =rt k -1，否则按照Metropolis 准则接受新解，即以概率
e -ΔJ /t 接受新解。
5.判断是否达到迭代次数，否的话继续步骤2.
6.判断是否满足终止条件，终止条件为达到终止温度，满足的话输出最终结果，不满足的话重置迭代次数k =0，并降低初始温度t 0=rT max 。
7.得到坐标估计初始值(x',y')。8.利用初始值计算Chan 算法中的矩阵B ，再代入式(9)求出ϕ，之后利用式(10)求出第一次最小二乘解Z a 。9.由于第一次最小二乘时没有考虑x ,y ,R 之间的关系，第
二次最小二乘中将会考虑，从而实现更高的定位精度。利用式
(13-16)求出Z '=(G 'T φ'-1
G ')-1G 'T φ'h '。
10.得到最终估计位置。Z i =±Z i '+S
11.
通过
测
量
值
计
算是否存在
|
|||R
i ,B
-R i ,A -R AB >4σ2，存在的话就将大圆方程舍去。
12.在待测目标的初始估计值(x 01,y 01),...,(x 0M ,y 0
M )处进行泰
勒级数展开，去除二阶以上分量，得到方程组。整理后得到：
h =G Δ+E
13.使用加权最小二乘法（WLS ），可以得到对Δ的估计：
Δ=(G T Q -1G )-1G T Q -1
h 其中Q 代表TDOA 测量值的协方差矩阵。在第二次递归
计算中，令
éëêêêêêêùû
úúúúúúx 1
1y 11⋮x 1M y 1M =éëêêêêêêùû
ú
úúúúúx 0
1+Δx 1y 01
+Δy 1⋮x 0M +Δx M y 0M +Δy M 14.重复计算多次，直到Δx i 和Δy i 都足够小，满足某个设定的门限值ε：
∑i =1
M (||Δx i +||Δy i )<ε15.得到最终结果(x 1,y 1),...,(x M ,y M )。
4仿真分析
在100m×100m 的平面内随机放置20个未知位置的待测目标，5个已知位置的节点。假设距离测量误差服从10m ，方差为δ2=1的指数分布。
表2不同算法误差分析
算法误差
Chan 3m
Chan+Taylor
1m
融合算法0.49m
通过表2可以看出，融合算法有着较高定位精度。在其他不变的情况下，分析误差的方差与定位精度的关系：
图4不同算法定位误差对比
Computer Knowledge and Technology 电脑知识与技术
第17卷第1期(2021年1月)
在δ2=0.5时，重复测试50次测试定位误差分布函数和
方差的关系：
图5累计分布与测量误差方差的关系
当真实目标在(60,65)点时，运行20次算法，得到定位点
分布。
三维建模
图6算法定位点分布
当距离测量误差服从方差为δ2=1的标准正态分布时：
表3不同算法误差分析
算法误差
Chan 0.82m
Chan+Taylor 0.83m
融合算法0.52m
增加个数查看算法精度的变化：
图7个数与定位误差关系
通过仿真分析可以看出，本文提出的算法在信道条件不够好，并且较少但有着多个待测目标时有着更高的定位精度，现实场景中适用性广泛。
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 deploy⁃ment challenges[C].IEEE International Symposium on Person⁃alIndoor 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 hyper⁃bolic 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.
【通联编辑：梁书】
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议