本发明公开了一种应用于大型室内环境的基站三维协作定位方法，包括以下步骤：(1)手动量测至少四个锚基站的三维坐标，通过TPSN测距原理估计未知基站间、未知基站和锚基站间的量测距离；(2)用矩阵表示基站的位置坐标，利用矩阵相乘得到用坐标表示的基站间实际距离；(3)将步骤(2)中的坐标矩阵松弛为半定矩阵，建立优化的约束条件；(4)将步骤(1)获得的量测距离和步骤(2)获得的实际距离求差的平方和作为优化过程中的目标函数，同时加入权重因素，构造出半定规划问题；(5)求解步骤(4)中的半定规划问题，获得的最优矩阵即为基站的三维位置坐标。本方法避免了因与锚基站连接个数不足而无法定位的情况，同时提升了定位精度。
1.一种应用于大型室内环境的基站三维协作定位方法，其特征在于，包括以下步骤：(1)手动量测至少四个锚基站的三维坐标，通过TPSN测距原理估计未知基站间、未知基站和锚基站间的量测距离；
(2)用矩阵表示未知基站的位置坐标，利用矩阵相乘得到用位置坐标表示的实际距离，构建基站间的三维距离约束；
(3)将步骤(2)中的位置坐标矩阵松弛为半定矩阵，建立优化的约束条件；
(4)将步骤(1)获得的未知基站间、未知基站和锚基站间的量测距离和步骤(2)获得的实际距离求差的平方和作为优化过程中的目标函数，同时在目标函数中加入权重因素，构造出半定规划问题；所述步骤(4)具体为：假设锚基站位置ak与未知基站位置xj间的距离误差为εjk，服从均值为0，方差为σ12的正态分布；另一未知基站位置即为xi，xi和xj间的距离误差为εij，服从均值为0，方差为σ22的正态分布，ejk与eij间相互独立；将权重信息加入到优化目标中，得到优化目标：Xml表示矩阵X的最优解，Na表示锚基站与未知基站间的距离空间，Na＝{(j，k)：1≤j≤n，
1≤k≤m}；d(xj，αk)表示锚基站位置ak与未知基站位置xj间的量测距离；Nx表示未知基站间的距离空间，Nx＝{(i，j)：1≤i，j≤n}；d(xi，xj)表示另一未知基站位置xi与未知基站位置xj间的量测距离；djk表示第k个锚基与第j个未知基站间的欧几里得距离，dij表示第i个未知基站与第j个未知基站间的欧式距离；
(0；0；0；ei-ej)TZ(0；0；0；ei-ej)＝dij2T 2
(axk；ayk；azk；-ej) Z(axk；ayk；azk；-ej)＝djk其中，ei是第i个值为1，其余为0的n维单位向量；ej是第j个值为1，其余为0的n维单位向量；I为3×3的单位矩阵；(axk，ayk，azk)表示第k个锚基站的三维位置坐标；X表示未知基站的位置矩阵；Y＝XTX，代表一个未知基站的三维位置坐标；
(5)对步骤(4)中构造出的半定规划问题进行求解，获得的最优矩阵即为基站的三维位置坐标。
2.根据权利要求1所述的一种应用于大型室内环境的基站三维协作定位方法，其特征在于，所述TPSN(timing-sync protocolfor sensor networks)测距原理包括下列步骤：(1)通过每两个基站之间进行TPSN测距获得这两个基站之问的距离量测值，令基站A发送信号的实际时间tA0，基站A和基站B接收信号的时间分别为tA1，tB1；基站B发送信号的实际时间是tB0，基站A和基站B接收信号的时间分别为tA2，tB2；将tA1和tB2分别近似为基站A和基站B的真实发送时刻；
(2)在基站A和基站B时钟预先同步的情况下，两基站间的距离表示为D＝(tB1-tA1)v，D＝(tA2-tB2)v，将这两个式子相加整理得到： 其中v是声速，通过直接在两台基站各自采集的信号中估计在自己时钟上的时延然后做差即可求得距离量测值，获得未知基站间、未知基站和锚基站间的量测距离。
3.根据权利要求1所述的一种应用于大型室内环境的基站三维协作定位方法，其特征在于，步骤(2)中三维距离约束的构建具体为：将锚基站k与未知基站j间的欧几里得距离用djk表示，未知基站i与未知基站j间的欧式距离用dij表示；用3×m的矩阵 来表示锚基站的位置，每列的三维向量代表一个锚基站的三维位置坐标；用3×n的矩阵来表示未知基站的位置，这里每列的三维向量代表一个未知基站的三维位置坐标，Y＝XTX∈Rn×n，此矩阵满足以下距离信息：(ei-ej)TY(ei-ej)＝dij2
其中，ei是第i个值为1，其余为0的n维单位向量，ej是第j个值为1，其余为0的n维单位向量，I为3×3的单位矩阵，(axk，ayk，azk)表示第k个锚基站的三维位置坐标，Rn×n为n×n的实数矩阵。
4.根据权利要求3所述的一种应用于大型室内环境的基站三维协作定位方法，其特征在于，所述步骤(3)具体为：将Y＝XTX松弛为Y≥XTX，设立可行区的边界，将问题转化为寻找一个矩阵且其满足约束：
(0；0；0；ei-ej)TZ(0；0；0；ei-ej)＝dij2(axk；ayk；azk；-ej)TZ(axk；ayk；azk；-ej)＝djk2
5.根据权利要求1所述的一种应用于大型室内环境的基站三维协作定位方法，其特征在于，利用matlab的CVX工具包求解半定规划问题。
应用于大型室内环境的基站三维协作定位方法
技术领域
[0001] 本发明属于室内定位领域，具体涉及一种应用于大型室内环境的基站三维协作定位方法。
背景技术
[0002] 随着各种大型建筑的兴起和居民生活水平的提高，基于位置信息的服务(Location-Based Service,LBS)越来越受到关注，成为人们日常出行、购物、旅行、住宿等必不可少的部分。然而由于建筑物遮挡造成的卫星信号急剧衰减以及建筑群之间反射产生的多径效应影响，室内环境中全球导航卫星系统的定位精度急剧下滑。同时，医疗救护、精准营销、智能仓储等室内位置服务需求日益增加，各种室内定位方法应运而生，其中，基站定位能够达到较高的精度。
[0003] 各种技术实现中，WIFI定位、蓝牙定位多采用指纹识别的定位方式，定位精度较低，且系统性能易受环境变化的影响，稳定性差且维护难度大；超声波技术和超宽带技术能够取得较高的位置估计精度，然而这些技术需定制专业的模块设备，成本高昂；基于声信号的定位技术由于其具有成本较低、手机兼容性好、稳定性和估计精度高等特征成为近几年的前沿研究课题，但也存在时钟同步、多径效应等问题。
[0004] 应用最为广泛的定位方法是基于距离量测的定位方法，根据是否可以利用未知基站间的距离分为协作定位和非协作定位。非协作定位仅仅依靠未知基站与锚基站之间的距离，多用于对目标进行定位。协作定位除了利用未知基站与锚基站之间的距离外，还利用未知基站间距离，如图3所示，多用于网络节点定位中。
[0005] 基站定位可以达到较高的精度但需要提前已知基站的精确位置，然而对基站位置的标定需要手工进行，容易引入误差，且当基站数量随着室内面积增大而增大时，这个过程将耗时又耗力。我们希望能够通过几个已知位置的锚基站对室内的所有基站位置进行标定。然而室内环境中存在很多遮挡，无法准确测得每两个基站之间的距离。另外，在大型室内空间中，基站间距离超过可测量的最大距离也将会造成测量值缺损，使得与未知基站相连接的锚基站个数不足以进行单独地三维定位。通过与其它未知基站的连接，协作定位在一定程度上解决了这个问题。但目前的半定规划算法都是二维的，在复杂的大型室内建筑中，为了提升三维定位的精度，基站往往需要遍布各种高度和角落，二维定位算法远远不够。
发明内容
[0006] 针对上述不足，本发明提供一种应用于大型室内环境的基站三维协作定位方法，解决了大型复杂室内环境下基站的三维标定问题，将定位问题转化为一个矩阵优化问题，寻找能使量测与实际距离差的平方和最小的矩阵。即使基站数量庞大，仍能够在较短时间内将基站的位置同时标定出来，解决由于量测距离限制和复杂室内环境阻碍造成的无法对每个未知基站进行单独定位的问题。
[0007] 本发明所采用的技术方案如下：一种应用于大型室内环境的基站三维协作定位方法，包括以下步骤：
[0008] (1)手动量测至少四个锚基站的三维坐标，通过TPSN测距原理估计未知基站间、未知基站和锚基站间的量测距离；
[0009] (2)用矩阵表示未知基站的位置坐标，利用矩阵相乘得到用位置坐标表示的实际距离，构建基站间的三维距离约束；
[0010] (3)将步骤(2)中的位置坐标矩阵松弛为半定矩阵，建立优化的约束条件；
[0011] (4)将步骤(1)获得的未知基站间、未知基站和锚基站间的量测距离和步骤(2)获得的实际距离求差的平方和作为优化过程中的目标函数，同时在目标函数中加入权重因素，构造出半定规划问题；
[0012] (5)对步骤(4)中构造出的半定规划问题进行求解，获得的最优矩阵即为基站的三维位置坐标。
[0013] 进一步的，所述TPSN(timing-sync protocol for sensor networks)测距原理包括下列步骤：
[0014] (1)通过每两个基站之间进行TPSN测距获得这两个基站之问的距离量测值，令基站A发送信号的实际时间tA0，基站A和基站B接收信号的时间分别为tA1，tB1；基站B发送信号的实际时间是tB0，基站A和基站B接收信号的时间分别为tA2，tB2；将tA1和tB2分别近似为基站A和基站B的真实发送时刻；
[0015] (2)在基站A和基站B时钟预先同步的情况下，两基站间的距离表示为D＝(tB1-tA1)v，D＝(tA2-tB2)v，将这两个式子相加整理得到： 其中v是声速，通过直接在两台基站各自采集的信号中估计在自己时钟上的时延然后做差即可求得距离量测值，获得未知基站间、未知基站和锚基站间的量测距离。
[0016] 进一步的，步骤2中三维距离约束的构建具体为：
[0017] 将锚基站k与未知基站j间的欧几里得距离用djk表示，未知基站i与未知基站j间的欧式距离用dij表示；用3×m的矩阵 来表示锚基站的位置，每列的三维向量代表一个锚基站的三维位置坐标；用3×n的矩阵来表示未知基站的位置，这里每列的三维向量代表
一个未知基站的三维位置坐标，Y＝XTX∈Rn×n，此矩阵满足以下距离信息：
[0018] (ei-ej)TY(ei-ej)＝dij2
[0019]
[0020] 其中，ei是第i个值为1，其余为0的n维单位向量，ej是第j个值为1，其余为0的n维单位向量，I为3×3的单位矩阵，(axk，ayk，azk)表示第k个锚基站的三维位置坐标，Rn×n为n×n的实数矩阵。
[0021] 进一步的，所述步骤3具体为：
[0022] 将Y＝XTX松弛为Y≥XTX，设立可行区的边界，将问题转化为寻找一个矩阵且其满足约束：
[0023] (0；0；0；ei-ej)TZ(0；0；0；ei-ej)＝dij2
[0024] (axk；ayk；azk；-ej)TZ(axk；ayk；azk；-ej)＝djk2
[0025]
[0026] 进一步的，所述步骤4具体为：
[0027] 假设锚基站位置ak与未知基站位置xj间的距离误差为εjk，服从均值为0，方差为σ12的正态分布；另一未知基站位置即为xi，xi和xj间的距离误差为εij，服从均值为0，方差为σ22的正态分布，ejk与eij间相互独立；将权重信息加入到优化目标中，得到优化目标：
[0028]
[0029] Xml表示矩阵X的最优解，Na表示锚基站与未知基站间的距离空间，Na＝{(j，k)：1≤j≤n，1≤k≤m}；d(xj，αk)表示锚基站位置ak与未知基站位置xj间的量测距离；Nx表示未知基站间的距离空间，Nx＝{(i，j)：1≤i，j≤n}；d(xi，xj)表示另一未知基站xi与未知基站xj间的量测距离；
[0030] 结合松弛技术，即可得到一个半定规划问题：
[0031]
[0032]
[0033]
[0034] (0；0；0；ei-ej)TZ(0；0；0；ei-ej)＝dij2
[0035] (axk；ayk；azk；-ej)TZ(axk；ayk；azk；-ej)＝djk2
[0036]
[0037] 进一步的，利用matlab的CVX工具包求解半定规划问题。
[0038] 本发明有益效果如下：本发明避免了基站标定时大量手工量测带来的误差累积，人力及时间成本消耗。相对于传统目标定位方法而言，协作定位考虑未知基站之间的距离，避免了因与锚基站连接个数不足而无法定位的情况，提升了定位精度；相对于节点定位而言，基站分布不再局限于同一平面内，不同高度的基站也将有效提升系统三维目标定位时的精度。
[0039] 本发明以三维坐标代表实体对象，将定位问题转化为矩阵优化问题，以量测距离信息和锚基站三维位置坐标作为约束，以带有权重的量测距离和实际距离差的平方和作为优化目标，引入松弛技术将目标矩阵松弛为半定矩阵，从而利用凸优化工具箱求得三维坐标矩阵的解。本发明在距离量测信息不足总量50％时仍能保持分米级精度。
附图说明
[0040] 图1为算法流程图；
[0041] 图2为距离量测原理图；
[0042] 图3为协作定位示意图；
[0043] 图4为定位结果三维表示图；
[0044] 图5为定位均方误差与距离量测范围关系图；
[0045] 图6为SDP定位精度与最小二乘算法(LLS)比较图。
具体实施方式
[0046] 下面结合附图和实施例对本发明做进一步的详细说明。
[0047] 本方法需要已知四个或以上锚基站的三维位置，未知基站间的距离，未知基站与锚基站之间的距离。我们通过TPSN原理估计基站间的距离，由于信号测距存在距离限制，且复杂室内环境中存在诸多障碍，我们仅能得到部分基站间距离。
[0048] 我们规定定位过程中一些代号以方便描述。假设在三维空间R3中，有m个锚基站ak，k＝1，2，...，m；n个未知基站xj，j＝1，2，...，n，第k个锚基与第j个未知基站间的欧几里得距离用djk表示，第i个未知基站与第j个未知基站间的欧式距离用dij表示。用Na表示锚基站与未知基站间的距离空间，Na＝{(j，k)：1≤j≤n，1≤k≤m}；用Nx表示未知基站间的距离空间，Nx＝{(i，j)：1≤i，j≤n}。假设信号的最大量测距离为R，当两基站间距离超过R，无法得到量测距离；当两基站间的距离小于R，认为此量测距离真实有效，则距离空间表示为：Na＝{(j，k)：||xj-ak||2≤R，1≤j≤n，1≤k≤m}，Nx＝{(i，j)：||xi-xj||2≤R，1≤i，j≤n}。
[0049] 下面，介绍三维协作定位的步骤：
[0050] 步骤1：锚基站位置量测与基站间距离估计。
[0051] 由于锚基站数量较少，可以进行手工量测。通过每两个基站之间进行TPSN测距获得这两个基站之问的距离量测值，如图2所示，令基站A发送信号的实际时间tA0，基站A和基站B接收信号的时间分别为tA1，tB1；基站B发送信号的实际时间是tB0，基站A和基站B接收信号的时间分别为tA2，tB2；由于基站收发信号模块距离相对于两基站间的距离可以忽略不计，因此在实际使用时，将tA1和tB2分别近似为基站A和基站B真实的发送时刻。
[0052] 在基站A和基站B时钟预先同步的情况下，两基站间的距离可以表示为D＝(tB1-tA1)v，D＝(tA2-tB2)v，将这两个式子相加整理得到： 其中v是声速，通常以340m/s计，通过直接在两台基站各自采集的信号中估计在自己时钟上的时延然后做差即可求得距离量测，此方法可以成功规避掉距离量测过程中的时钟同步问题。基站将距离信息传输到服务器中，进行下一步的位置计算。
[0053] 步骤2：构造距离应用基础。
[0054] 锚基站位置用3×m的矩阵 来表示，每列的三维向量代表一个锚基站的三维位置，用3×n的矩阵
来表示位置基站的位置，每列的三维向量代表一个未知基站的三维位置坐标，我们的问题即为寻找一个矩阵X，Y＝XTX∈Rn×n，满足以下距离信息：
[0055] (ei-ej)TY(ei-ej)＝dij2
[0056]
[0057] 其中，ei为第i位为1，其他位为0的长度为n的单位向量，ej是第j个值为1，其余为0的n维单位向量，I为3×3的单位矩阵，(axk，ayk，azk)表示第k个锚基站的三维位置坐标，Rn×n为n×n的实数矩阵。
[0058] 步骤3：引入松弛技术构造凸优化问题。
[0059] 为了将此问题转化为一个凸优化问题，通过松弛技术，将Y＝XTX松弛为Y≥XTX，设立可行区边界，将问题转化为寻找一个矩阵 且其满足约束：
[0060] (0；0；0；ei-ej)TZ(0；0；0；ei-ej)＝dij2
[0061] (axk；ayk；azk；-ej)TZ(axk；ayk；azk；-ej)＝djk2
[0062]
[0063] 步骤4：综合考虑距离量测误差。
[0064] 在真实的场景中，由于时钟同步、多径效应、噪声干扰等原因，利用TPSN技术测得的距ak与未知基站位置xj间的误差为εjk，服从均值为0，方差为σ12的正态分布；另一未知基站位置即为xi，xi和xj间的误差为εij，服从均值为0，方差为σ22的正态分布，ejk与eij间相互独立；即：
[0065]
[0066]
[0067] 以距离越长量测误差越大为准则，将方差的倒数作为权重，得到优化目标：
[0068]
[0069] Xml表示矩阵X的最优解，Na表示锚基站与未知基站间的距离空间，Na＝{(j，k)：1≤j≤n，1≤k≤m}；d(xj，αk)表示锚基站ak与未知基站xj间的量测距离；Nx表示未知基站间的距离空间，Nx＝{(i，j)：1≤i，j≤n}；d(xi，xj)表示另一未知基站xi与未知基站xj间的量测距离；
[0070] 结合松弛技术，即可得到优化问题中的半定规划问题：
[0071]
[0072] s.t.Na＝{(j，k)：||xj-ak||2≤R，1≤j≤n，1≤k≤m}
[0073] Nx＝{(i，j)：||xi-xj||2≤R，1≤i，j≤n}
[0074]
[0075]
[0076] (0；0；0；ei-ej)TZ(0；0；0；ei-ej)＝dij2
[0077] (axk；ayk；azk；-ej)TZ(axk；ayk；azk；-ej)＝djk2
[0078]
[0079] 步骤5：半定规划问题的求解。
[0080] 通过matlab的CVX工具箱对上述半定规划问题进行求解，求得信号测距感知半径为R时各未知基站所在位置的坐标。
[0081] 实施说明：
[0082] 本算法流程如图1所示，定位误差与多种因素相关，包括锚基站的个数及布局，信号距离量测范围，距离量测误差分布等。距离量测越准确，定位误差越小。但距离量测可能建立在提升信号带宽和提升发射功率的基础上，前者可同时发送的信号数量会减少，后者可能产生噪声，定位精度的提升在此方面的受到了时间成本与噪声影响的约束。随着锚基站个数的增多，定位误差逐渐下降，但当锚基站占比达到一定程度后，精度提升缓慢。锚基站位置的测定耗时耗力，因此锚基站数量的选择是精度需求与人力成本的折中。测距范围越大，基站间的连接数量约多，同样有利于提升定位的精度，如图5所示，但同样需要提升功率带来噪声的影响。
[0083] 本发明避免了基站标定时大量手工量测带来的误差累积，人力及时间成本消耗。相对于传统目标定位方法而言，协作定位考虑未知基站之间的距离，避免了因与锚基站连接个数不足而无法定位的情况，提升了定位精度，如图6对比图所示；相对于节点定位而言，基站分布不再局限于同一平面内，如图4所示，不同高度的基站也将有效提升系统三维目标定位时的精度。
[0084] 应用环境：
[0085] 应用于复杂大型室内环境的定位系统需要大量位置已知的基站，手工标定耗时耗力，还会引入不确定的误差。更严重的是，在一些大型古建筑中，位于空中某些特殊位置的锚基站难以测量，手工标定无法进行。同时，由于信号在传播过程中的衰减，测量距离存在限制，即存在感知半径，基站间距离超过感知半径将无法连通。对大型室内空间中某未知基站而言，与已知基站间连接数量不足，无法通过锚基站对未知基站进行单独标定。另外，大型空中机器人编队，水下潜艇编队等同样需要三维协作算法，通过少数位置已知的坐标和相互之间的距离信息，得到所有机器的位置信息。
