如今,随着智能手机的普及,基于手机测量信息的定位问题有着很大的商业价值和应用前景.如何对终端进行较高精度的定位,被认为是一个很具有挑战性的问题.相比于GPS,基于无线网络基站(base station,BS)的定位具有以下两方面特殊性:一是覆盖范围广.在室内、地下、繁华市区等地方,GPS定位不能满足人们对定位精度的要求,而基站定位有可能在这些复杂的环境中实现高精度定位需求.二是基站周围的电磁信号复杂.比如在室内、山区和繁华市区,信号在这些环境中传播时会经过多次折射、反射、吸收等,造成测量信息存在大量噪声.那么,怎样处理这些噪声对定位精度的影响,也是基于基站定位面临的问题.
终端定位技术的基本原理[1]是首先通过测量终端或者基站所发的信号来估计出相应参数,然后用合适的算法求得终端的估计位置.常见的终端定位技术包括:基于到达角度(angle of arrival,AOA)测量的定位方法、基于到达时间(time of arrival,TOA)测量的定位方法、基于到达时差(time difference of arrival,TDOA)测量的定位方法等,终端定位研究的关键是避免一些因素对定位精度的影响,如多址干扰、多径传播、非视距(non-line of sight,NLOS)传播等.
在三维定位问题中,时间的测量值往往是非视距传输值,而信号的非视距传输极大地降低了算法的定位精度.为了减小信号非视距传输的影响,人们提出了多种算法[2-16],主要通过以下两种途径来实现:1)通过加权来减小非视距的影响;2)从接收信号中检测出视距信号,然后用视距信号进行定位.具有代表性的定位算法成果有:Chen在其博士论文中提出对于消除非视距误差可以利用残差加权的方法解决[7];Roos和Myllymäki等[8]将定位问题视为机器学习的问题,并在最后提出了一个概率性的框架来解决三维定位问题;Kleine-Ostmann等提出了一种适合于定位估计的数据融合模型[9];Kyriazakos和Mangold提出了将基于隐Markov模型的模式识别技术用于定位估计[10];Nhat等提出基于神经网络的原理,输入以多个节点的接收信号强度指示(received signal strength indication, RSSI),输出为位置坐标来训练多层感知机,从而实现定位[11];Wylie等提出了一种经典方法来判断和消除非视距误差[12];Chan等提出了在误差近似服从Gauss分布时的一种性能优良的定位算法[13];McGuire等提出了一种鲁棒函数估计[14];张洁颖提出了一种基于场景指纹的定位方法,通过采样点收到无线信号的某种特征信息建立有关场景数据库,以此来估计待定位目标的空间位置[15];倪巍等根据已有的路径损耗模型进行改进提出了一种定位算法,得出一种通过迭代的最大似然估计算法[16].
解决定位问题是多学科的交叉融合,需要LS估计、数据拟合、数值分析、机器学习等很多数学和信息通信理论的支撑.每一个对终端定位问题有创新性的算法,都可能带来巨大的社会效益,其主要应用有智慧城市、智能物流、车辆导航、紧急救援等领域[17].
本文探讨基于TOA测量信息的三维定位问题,进行两个方面的研究,其一为消除非视距传播的误差,受博弈论[18]启发,将三维移动定位看成演化博弈问题,以各个测量基站作为博弈局中人,建立关于移动定位的复制动态模型.该模型推广了经典复制动态模型[19],提出了基于演化博弈的TOA定位算法(TOA-geolocation algorithm based on evolutionary game,EGTOA),通过迭代计算消除非视距误差,获得其平衡解和移动端的位置估计.第二则为了消除各个测量基站分布不均匀带来的定位坐标误差较大的缺陷,在前述平衡解的基础上引入虚拟基站,与实际基站相比,虚拟基站的位置坐标分布相对均衡,以虚拟基站+实际基站作为局中人进行演化博弈,计算定位出的移动终端三维坐标误差都在合理范围内.
论文后续结构如下:第1节提出了用于非视距环境下三维定位的复制动态模型及其算法;第2节针对基站位置坐标分布范围有较大差距的情形,将实际基站映射到虚拟基站,以虚拟基站+实际基站作为博弈局中人建模;第3节进行了对比实验;最后一节进行了总结.
博弈论(game theory)[19]是现代数学的分支之一,主要研究多个参与者在利益存在竞争和交互的局势中,理性的参与者为实现自身效用最大化,如何选择各自策略并达到利益均衡的理论,是研究具有竞争和合作性质现象的理论和方法.博弈论可以指导和分析通信网络中的算法设计,已被用于解决移动通信网络中的许多设计问题,比如网络资源分配、功率控制、接入控制、分组传输控制、协作中继通信等问题[20].
经典博弈论中通常假设博弈方是完全理性的,但对于现实中的决策者而言是很难达到完全理性的,当博弈环境或者决策问题复杂时,人们的理性局限非常明显.如果博弈参与方不满足完全理性假设,则称这样的博弈为有限理性博弈.有限理性博弈意味着博弈方不可能一开始就找到最优策略,而是在博弈过程中通过学习和试错来寻找较好的策略.研究有限理性博弈的一个重要途径是利用生物进化机制来模拟,称之为演化博弈[18].
1973年,Maynard Smith描述生物演化现象时提出了演化博弈[18],演化博弈模型[19]有两个最基础的方面建立:选择和突变.选择是指能够获得较高支付的策略在以后将被更多的参与者采用;突变是指部分个体以随机的方式选择不同于群体的策略(可能是能够获得高支付的策略,也可能是获得较低支付的策略).突变是一种不断试错的过程,也是一种学习与模仿的过程,这个过程是适应性且是不断改进的,演化稳定策略是演化博弈中最基本的概念.
有限理性意味着均衡是不断调整和改进而不是一次性选择的结果,而且即使到达了均衡也可能再次偏离.有限理性博弈方会在博弈过程中学习博弈通过试错寻找较好的策略,其策略与均衡用复制动态模型来刻画.经典的复制动态模型[19]如下:
(1)
其中,xi是第i方的策略,ui是第i方的支付,是平均支付.
为能够描述更多的问题,将经典复制动态模型推广如下:
(2)
表示第i个局中人的策略变化率是参与博弈各方策略的函数,k代表参与博弈人数.
1.2.1 演化博弈模型
假设在某个场景中有m个BS参与定位测量,该场景中有n个移动端MS.设第i个BS的坐标为(Xi,Yi,Zi),第j个MS的坐标为(xj,yj,zj),i=1,2,…,m, j=1,2,…,n.令Rij表示第i个BS与第j个MS的非视距测量距离,rij表示第i个BS与第j个MS的视距距离.
将第j个MS的定位当作多个BS之间的博弈,设第i个BS的策略为λij=rij/Rij(视距距离与非视距距离之比),平均支付为(xj,yj,zj),其中,xj,yj和zj都是λij的函数.
取
则复制动态方程组如下:
i=1,2,…,m, j=1,2,…,n.
(3)
为求解其平衡点,令dλij/dt=0,则有
Ki-2Xixj-2Yiyj-2Zizj+Qj,
(4)
其中
该非线性方程组共有mn个方程,变量有4n+mn个,方程个数小于变量个数,方程组有无限多组解.以下研究如何近似求解复制动态方程组.
1.2.2 复制动态方程组的近似求解
1) 假设事先能够估计出λij的值,则变量数量为4n个,进一步可以将非线性方程(4)简化为线性方程,步骤如下.
将i=1代入式(4),有
(5)
式(4)与式(5)相减,得
2(Xi-X1)xj+2(Yi-Y1)yj+2(Zi-Z1)zj=
(6)
选取4个BS(下标分别记为2~5,要求这5个BS不在同一平面上)代入方程(6),得
Bq=p,
(7)
其中
采用最小二乘法求解得B=(BTB)-1BTp,得第j个MS的位置估计
2) 估计λij的值
令λi是第i个BS对应的随机变量,其取值范围是{λij=rij/Rij|j=1,2,…,n},假设λi近似服从某种分布πi,即在方程中用λi代替λij,则有近似方程:
(8)
这样的方程共有mn个,变量有4n+m个,要使方程组不存在无限多组解,必有方程个数大于等于变量个数,选择其中m1个BS和n1个MS的数据来构造方程组并求解,使得4n1+m1≤m1n1,为使方程个数和变量个数尽量少,取n1=3,m1=6,即3个MS和6个BS,并且这6个BS中的任意4个都不在同一平面上.
方程组(8)的矩阵形式:
Ah=b,
(9)
其中
A=(A1|A2|A3), h=(h1,h2,h3)T,
b=(K1,K2,…,K6,K1,K2,…,K6,K1,K2,…,K6)T,
h1=(x1,y1,z1,x2,y2,z2,x3,y3,z3), h2=(Q1,Q2,Q3),
当A=(A1|A2|A3)非奇异时,方程组有解h=A-1b,得到6个BS对应的λi,以及3个MS的位置估计当A奇异时,在A31或A32或A33的最后3列中的每一列加上单位矩阵的某个列向量,目的是构造非奇异系数矩阵A.固定这6个BS,如果剩下的MS个数大于等于6,则在剩下的MS中重新取3个MS及其Rij,与这6个BS配合得到新的方程组,求解得到3个新MS的位置估计如果剩下的MS个数小于6,则剩下的全体MS与这6个BS配合得到新的方程组,重复此过程,得到全体MS的位置估计
取
(10)
令
(11)
随机变量λi取值范围令计算中各个值的概率分布,设为πi,则有
至此,得到视距距离估值rij=λijRij,其中且取值概率服从分布
将视距距离估值rij=λijRij代入算法解出全体MS的位置(xj,yj,zj),将上述计算过程总结算法如下.
Step 1 初始化全体移动端MS位置集合V={(xj,yj,zj)|j=1,2,…,n}和全体基站BS位置集合U={(Xi,Yi,Zi)|i=1,2,…,m},其中n为MS数量,m为BS数量,k←1,n1←3,m1←6,其中←表示赋值.
Step 2 在V中取出n1个MS,在U中选取m1个BS(任意4个都不在同一平面上),利用m1个BS和n1个MS的位置坐标和非视距测量距离等信息来构造方程组(9),n←n-n1.
Step 3 求解方程组Ah=b,当n1=3时,h=A-1b;当n1>3时,h=(ATA)-1ATb,得n1个MS的第k次位置估计
Step 4 如果n=0, 转step 5; 如果n≥6, 在V中取出n1个MS, n←n-n1, m1个BS保持不变; 如果n<6, 令n1=n, n←n-n1; 用这n1个MS和m1个BS来构造方程组(9), 转step 3.
Step 5 对第j个MS的第k次位置估计计算其到第i个BS的视距估值计算视距与非视距比值计算集合中各个值的概率分布,记为πi,i=1,2,…,m, j=1,2,…,n.
Step 6 对于i=1,2,…,m, j=1,2,…,n,按如下方式重新估计且取值概率服从分布πi,据此λij计算第i个BS与第j个MS的视距距离rij=λijRij.
Step 7 k←k+1,对第j个MS(j=1,2,…,n),取step 1中的前5个BS以及step 6得到的rij代入方程组(7),采用最小二乘法求解得q=(BTB)-1BTp,得第j个MS的第k次位置估计
Step 8 如果k=3,算法结束;如果k<3,转step 5.
当BS位置在x,y,z三个方向上分布明显不均时,上述算法结果误差不容忽视,此时通过构造虚拟基站,加入虚拟基站后重新定位.
记
ΔX和ΔY相当,但ΔX≫ΔZ.
记α=ΔX/ΔZ,对第i个BS构造对应的虚拟基站(virtual base station,VBS),坐标为满足
(12)
第i个VBS与第j个MS的视距距离:
(13)
λij是上述EGTOA算法结束后的随机变量,λij=rij/Rij.
对方程组(7)增加2个方程:
Bq=p,
(14)
其中
采用最小二乘法求解得q=(BTB)-1BTp,得第j个MS的位置估计
综上,当所有BS位置分布相对均衡,即ΔX,ΔY和ΔZ的数量级相当时,运行上述算法后即得到各个MS的坐标位置估计.
如果BS位置分布严重不均衡,如若ΔX的数量级和ΔY的数量级相当,但ΔX的数量级远远大于ΔZ的数量级,则先运行EGTOA算法,根据EGTOA结果按式(13)构造视距距离,按式(12)构造虚拟基站VBS,用虚拟基站+实际基站,再一次求解方程组.
基于虚拟基站的三维定位算法(TOA-geolocation algorithm based on virtual base station,VBTOA)如下:
Step 1 执行EGTOA算法.
Step 2 在EGTOA算法的step 7选取5个BS的基础上,按式(12)构造虚拟基站VBS,按式(13)构造视距距离.
Step 3 对第j个MS(j=1,2,…,n),采用最小二乘法求解方程组(14)得q=(BTB)-1BTp,得第j个MS的位置估计
以2016年全国研究生数学建模竞赛给出的测试数据集来验证算法性能,数据集1有30个BS、1 100个MS,包含30×1 100个TOA下的测量数据,数据集2有40个BS、1 200个MS,包含40×1 200个TOA下的测量数据,这2组测试数据集都包含了MS的准确位置供算法验证.
在两个数据集上分别运行上述EGTOA算法,得到两个数据集BS的λij取值分布参数见表1,其中,和是第i个BS对应的λij的均值和方差.从表中反映出两个数据集的λij取值分布较为集中,不同BS的λij均值很接近,方差很小.数据集2的λij均值接近1,表明该数据集对应的场景可以近似为视距环境.
考察两个数据集中BS位置分布情况,在数据集1中,ΔX≈ΔY≈600,ΔZ≈3.3;在数据集2中,ΔX≈ΔY≈750,ΔZ≈2.7,两个数据集中的BS位置分布在x,y,z三个方向上相对差距较大.
表1 2组测试数据对应λij的分布参数
Table 1 Distribution parameters corresponding toλijin test data
min1≤i≤mμimax1≤i≤mμimin1≤i≤mσ2imax1≤i≤mσ2itestdataset1(m=30)0.705460.706052.151×10-72.184×10-5testdataset2(m=40)0.968280.969443.2109×10-64.7115×10-5
在两个数据集上分别运行经典的Chan算法和Taylor算法,以及本文的EGTOA算法和VBTOA算法,在x,y,z三个方向上MS位置估值的误差比较见表2和表3(从偏差最大值和平均偏差两个方面比较).表2和表3对比可以看出,本文中提出的EGTOA算法在x,y两个方向上的MS位置估值误差略优于传统的Chan算法和Taylor算法, 但这3个算法在z方向上的MS位置估值误差都很大, 而本文提出的基于虚拟基站的三维定位算法VBTOA在z方向上的估值误差明显优于Chan算法、Taylor算法和EGTOA算法,整体上看VBTOA算法的效果最好.
表2 在测试集1上4种算法估值误差对比
Table 2 Error comparison of 4 algorithms in test data set 1
ChanTaylorEGTOAVBTOAmax1≤j≤n|xj-xj|2.862.871.111.11E(|xj-xj|)1.931.890.680.68max1≤j≤n|yj-yj|2.922.901.091.09E(|yj-yj|)1.951.890.660.66max1≤j≤n|zj-zj|22.0524.4221.051.62E(|zj-zj|)14.2716.6212.850.72
表3 在测试集2上4种算法估值误差对比
Table 3 Error comparison of 4 algorithms in test data set 2
ChanTaylorEGTOAVBTOAmax1≤j≤n|xj-xj|1.921.901.081.08E(|xj-xj|)0.910.900.390.39max1≤j≤n|yj-yj|1.891.911.061.06E(|yj-yj|)0.910.910.400.40max1≤j≤n|zj-zj|23.4625.3923.521.57E(|zj-zj|)15.2117.3214.850.76
对产生VBTOA算法效果的原因分析如下.
在虚拟基站引入之前,EGTOA算法的step 7中,由q=(BTB)-1BTp得第j个MS的第k次位置估计对于实验中的第一个数据集,有
矩阵各个元素都取到小数点后4位数字, 其中第3行数据的绝对值明显远大于第1和第2行, 由于p中的数据有测量误差, 导致的误差远大于和的误差,对第二个数据集也是同样如此.
在虚拟基站引入之后,对于基于虚拟基站的三维定位算法VBTOA,其step 3中,由q=(BTB)-1BTp得第j个MS的位置估计对于实验中的第一个数据集,有
第3行数据的绝对值和第1和第2行的相当,这样使得的误差和和的误差是相当的,第二个数据集也是同样如此.
虚拟基站的作用是使让基站在x,y,z这3个方向上分布范围的长度大致相当,这样得到的(BTB)-1BT矩阵第3行数据的绝对值和第1和第2行的大致相当,从而使得的误差和和的误差上限也大致相当.由于算法VBTOA的主要时间开销是第一步的EGTOA算法,因此虚拟基站的引入不会增加算法的计算复杂度.
为消除非视距环境对TOA三维定位带来的误差,引入演化博弈模型.为适应TOA三维定位要求对经典复制动态方程进行了推广,以各个测量基站作为博弈局中人,为非视距环境下的TOA三维定位问题建立了复制动态模型,将视距距离与非视距距离之比视为一定的概率分布πi,提出了基于演化博弈的TOA定位算法EGTOA,通过演化迭代进行概率分布πi的学习,其学习过程也是减少非视距误差的过程,最后获得移动端的位置估计.进一步地,针对基站位置分布明显不均的情况,在EGTOA定位算法的基础上,通过构造虚拟基站,采用虚拟基站+实际基站对移动端定位,提出了基于虚拟基站的三维定位算法VBTOA.实验对比显示EGTOA算法略优于经典定位算法,在基站位置分布明显不均的情况下,VBTOA算法效果有明显优势.
[1] 邱善勤, 龚耀寰. 移动通信定位技术之比较[J]. 电子科技大学学报, 2003, 32(6): 598-603.(QIU Shanqin, GONG Yaohuan. Comparision of cellular location technologies[J]. Journal of University of Electronic Science and Technology of China, 2003, 32(6): 598-603.(in Chinese))
[2] 刘琚, 李静. 一种在非视距环境中的TDOA/AOA混合定位方法[J]. 通信学报, 2005, 26(5): 63-68.(LIU Ju, LI Jing. TDOA/AOA hybrid wireless location method in NLOS situation[J]. Journal on Communicarions, 2005, 26(5): 63-68.(in Chinese))
[3] 屈保平, 袭著有, 陈长衍. 一种NLOS环境下基于散射模型的TOA定位方法[J]. 火力与指挥控制, 2014, 39(5): 26-30.(QU Baoping, XI Zhuyou, CHEN Changyan. A method for TOA location based on scattering models in NLOS environments[J]. Fire Control & Command Control, 2014, 39(5): 26-30.(in Chinese))
[4] 田孝华, 廖桂生. 一种有效减小非视距传播影响的TOA定位方法[J]. 电子学报, 2003, 31(9): 1429-1432.(TIAN Xiaohua, LIAO Guisheng. An effective TOA-based location method for mitigating the lnfluence of the NLOS propagation[J]. Acta Electronica Sinica, 2003, 31(9): 1429-1432.(in Chinese))
[5] 徐彤阳. NLOS环境下无线传感器网络TOA定位算法[J]. 计算机工程, 2013, 39(12): 90-93.(XU Tongyang. TOA location algorithm in wireless sensor network under NLOS environment[J]. Computer Engineering, 2013, 39(12): 90-93.(in Chinese))
[6] 赵军辉, 张雪雪, 曾龙基. 提高NLOS环境下室内定位精度的新方法[J]. 北京邮电大学学报, 2012, 35(6): 38-43.(ZHAO Junhui, ZHANG Xuexue, ZENG Longji. An approach to improving the accuracy of the indoor positioning with NLOS environment[J]. Journal of Beijing University of Posts and Telecommunications, 2012, 35(6): 38-43.(in Chinese))
[7] CHEN P C. A non-line-of-sight error mitigation algorithm in location estimation[C]//IEEE Wireless Communications and Networking Conference. 1999.
[8] ROOS T, MYLLYMKI P, TIRRI H, et al. A probabilistic approach to WLAN user location estimation[J]. International Journal of Wireless Information Networks, 2002, 9(3): 155-164.
[9] KLEINE-OSTMANN T, BELL A E. A data fusion architecture for enhanced position estimation in wireless networks[J]. IEEE Communications Letters, 2001, 5(8): 343-345.
[10] KYRIAZAKOS S, MANGOLD S. Applying pattern recognition techniques based on hidden Markov models for vehicular position location in cellular networks[J]. Vehicular Technology Conference, 1999, 2(2): 780-784.
[11] NHAT T L, VILLANI R, BATTITI R. Neural network model for intelligent networks: deriving the location from signal patterns[C]//Proceedings of AINS. 2002.
[12] WYLIE M P, HOLTZMANN J. The non-line-of-sight problems in mobile location estimation[C]//5th IEEE International Conference on Universal Personal Communications. Cambridge, MA, 1996.
[13] 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.
[14] MCGUIRE M, PLATANIOTIS K N, VENETSANOPOULOS A N. Robust estimation of mobile terminal position[J]. Electronics Letters, 2000, 36(16): 1426-1428.
[15] 张洁颖. 基于ZigBee网络的定位跟踪研究与实现[D]. 硕士学位论文. 上海: 同济大学, 2007.(ZHANG Jieying. The research and implementation of localization and tracking in the ZigBee network[D]. Master Thesis. Shanghai: Tongji University, 2007.(in Chinese))
[16] 倪巍, 王宗欣. 基于接收信号强度测量的室内定位算法[J]. 复旦学报(自然科学学报), 2004, 41(1): 72-76.(NI Wei, WANG Zongxin. An indoor location algorithm based on the measurement of the received signal strength[J]. Journal of Fudan University(Natural Science), 2004, 41(1): 72-76.(in Chinese))
[17] 范平志, 邓平, 刘林. 蜂窝网无线定位[M]. 北京: 电子工业出版社, 2002.(FAN Zhiping, DENG Ping, LIU Lin. Wireless Location in Cellular Network[M]. Beijing: Electronic Industry Press, 2002.(in Chinese))
[18] WEIBULL J. Evolutionary Game Theory[M]. Cambridge: The MIT Press, 1995.
[19] 谢识予. 经济博弈论[M]. 上海: 复旦大学出版社, 2002.(XIE Shiyu. Economic Game Theory[M]. Shanghai: Fudan University Press, 2002.(in Chinese))
[20] 王增. 基于博弈论的蜂窝网络功率控制与多维效率优化研究[D]. 博士学位论文. 北京: 北京邮电大学, 2018.(WANG Zeng. Research on power control and multi-dimensional efficiency optimization of cellular network based on game theory[D]. PhD Thesis. Beijing: Beijing University of Posts and Telecommunications, 2018.(in Chinese))