遮挡环境下室内定位系统的信标节点布局优化*

焦 侃， 冯刘涛， 张 磊， 胡志新

(1.长安大学 工程机械学院，陕西 西安 710064； 2.成都国光电气股份有限公司，四川 成都 610051)

0 引 言

随着各类型智能移动终端的发展，如何在复杂室内获取实时、高精度的位置信息是智能移动终端在室内场景为人们提供各类服务的关键，具有广阔的市场应用前景[1,2]。根据微软国际室内定位大赛的评估结果，基于测距的室内定位系统在室内复杂环境中具有较好的性能[3]。其主要定位架构包括基于到达时间(time of arrival，TOA)法、到达时间差(time difference of arrival，TDOA)法，以及基于信号接收强度指示(received signal strength indication,RSSI)的测距法。与其他技术相比，基于测距的定位系统具有低计算复杂度和低能耗的特点，因而具有较好的应用前景。但在实际应用和推广中，室内遮挡非视距(non-line-of-sight，NLOS)环境成为该类技术所面临的最主要挑战[4]。

在室内复杂环境中，遮挡往往会给测距引入一个较大的正偏差，极大地削弱了系统的定位精度和稳定性。目前，改善室内NLOS环境下定位系统性能的解决途径包括：研究更好的NLOS定位算法[5]；增加信标的部署密度[6]。前者会提高计算复杂度，后者则会增加定位系统整体的成本。通过优化系统信标的布局方式，可以在不改变计算复杂度和部署成本的前提下，提高系统的定位性能。

目前，针对室内定位系统信标节点最优化布局的研究尚处在起步阶段，且绝大多数研究成果均是针对理想的非遮挡(即视距(line-of-sight，LOS))环境。文献[7]给出了寻找节点最优布局的一种迭代搜索算法，但这种方法对于简单规则环境下的锚节点最优布局搜索有较好的收敛性，对于复杂的室内定位环境还有改进的空间。文献[8]提出了定位误差的简化算法与近似函数，利用改进的随机搜索算法在可接受的时间成本内找到信标节点的次优分布。文献[9]给出了TDOA和频差到达(frequency difference of arrival,FDOA)定位算法下的最优参考节点的配置策略，未考虑遮挡物问题。文献[10]利用混合整数线性规划 (mixed-integer linear programming,MILP)法基于信标节点布局几何精度因子(geometric dilution of precision，GDOP)最小化三维无遮挡环境下的定位信标节点数并找到其对应的最优分布。但所给出的信标节点只能分布于定位空间的表面且不考虑空间内的NLOS问题。

因此，本文针对遮挡环境中基于测距的定位系统，提出了一种基于粒子群优化(particle swarm optimization，PSO)算法的信标节点布局优化，并提出了针对遮挡环境的最优化适应度函数,分别通过数值仿真和实验进行性能评估，来提高室内复杂环境中基于测距的定位系统的精度和稳定性。

1 问题描述

1.1 GDOP

GDOP是衡量由信标节点布局所引起的系统定位误差的一个重要参数， GDOP值越小表示定位系统的定位精度越高。在高斯环境下的m个信标节点特定布局，GDOP的值G可以表示为

(1)

(2)

相对应地，TDOA架构的Q和H分别表示为[11]

(3)

(4)

1.2 遮挡环境下的GDOP

在理想无遮挡环境下的GDOP计算中，距离量测被看作服从独立同分布的高斯分布。但在NLOS环境下，当待测节点与信标节点之间存在遮挡物时，距离测量信息服从高斯分布的假设不成立。基于式(1)对GDOP进行计算会存在较大误差。

为了对NLOS环境中的GDOP进行计算，一种切实可用的方法是剔除掉遮挡的距离量测信息后，仅使用LOS量测来对GDOP值进行近似计算。因此,遮挡环境下GDOP值的计算，只需考虑LOS信标节点布局的影响。

2 遮挡环境下的适应度函数

信标节点布局优化问题，即为在定位空间中找到一种最优的布局方式，使得定位区域中的GDOP均值最小。本文研究的是遮挡环境中信标节点布局优化问题，由于遮挡的影响，单个待测节点需获取足够的LOS量测才能成功定位。TOA架构需要2个以上，而TDOA架构则需要3个。

因此,布局优化的目标可描述为：在定位目标区域找到一组信标节点的布局，使得区域内能够成功定位的待测节点GDOP均值最小。选取目标区域内均匀分布的N个测量点作为待测节点，信标节点布局P能够成功定位的节点个数为N′，优化问题的适应度函数可定义为

(5)

该适应度函数仅考虑到能够成功定位的待测节点。对于LOS量测数量小于最小需求的未知节点则不予考虑。因此，针对遮挡环境，对上述适应度函数进行改进

(6)

式中i为待测节点所能获得的LOS量测信息的数量，N′i为获取LOS信息数量为i的未知节点的总数，fi为权重系数，不同权重系数下所期望的每类未知节点占比例有所不同。对于TOA架构，i′=2;对于TDOA架构，i′=3。

3 优化方法

3.1 PSO算法

节点布局优化问题大多采用随机搜索法来寻找其最优解。本文采用PSO算法来寻找遮挡环境下信标节点的最优布局。PSO算法是一种基于简化生物社会模型的群智能优化算法,可描述为：n个粒子组成的群体在D维空间中运动，结合粒子自身以及群体所经历的最好位置来更新粒子的运动状态。粒子的运动速度与位置更新由式(7)和式(8)决定[12]

(7)

(8)

w=wmin+(wmax-wmin)×(1-k/kmax)

(9)

式中wmax和wmin分别为最大惯性权重与最小惯性权重，kmax为最大迭代步数。

3.2 算法流程

在定位空间中对m个信标节点进行布局优化。定位区域离散化后待测节点数量为N。粒子规模取S，每个粒子表示一种信标布局方式，则单个粒子的维度为m×3，每个维度的最大搜索速度为vmax。综合考虑算法的初期的全局搜索能力以及后期的局部搜索能力，选取最大惯性权重wmax为0.9，最小惯性权重wmin为0.4，最大迭代次数为kmax步。

步骤1 在定位区域内随机初始化粒子群的初始位置与初始速度，即随机确定S种初始信标节点布局方式与初始速度,并要保证每种布局的信标节点位置都在非遮挡区域内。

步骤4 若满足终止条件，则输出最优布局方式与其适应度值，否则返回步骤2。终止条件包括：1)迭代次数超出最大值；2)适应度函数的值小于设定阈值；3)迭代步间差值小于设定阈值。

4 数值仿真与结果分析

以基于TOA定位系统在二维平面内的4个信标节点布局优化问题进行数值仿真。定位区域为40 m×40 m，对定位区域进行长宽均为0.5 m的网格划分，其顶点为待测节点。PSO算法的最大惯性权重与最小惯性权重分别取0.9与0.4，最大搜索速度为5 m/s，粒子群规模为20，迭代次数为500次。

当定位区域为LOS时，信标节点的最优布局如图1(a)所示，该结果与文献[13]中的结果相似。当定位区域存在遮挡物时，定位区间为非凸。以式(6)为优化适应度函数，权重系数f2,f3,f4取0.1,0.1,0.8，优化布局结果如图1(b)所示。分析两种环境下的信标节点优化布局结果可发现，当定位空间为遮挡环境时，信标节点的最优布局会优先提高能同时接收到更多LOS信号的未知节点的数量，其结果与实际的认知情况相符合。

图1 LOS与遮挡场景的布局优化结果对比

适应度函数式(6)中，不同权重系数fi用于控制所期望的不同数量LOS量测定位区域的占比。取f2,f3,f4的值为

(10)

计算在该权重下的信标节点最优布局，并统计不同权重系数下N′2，N′3，N′4占比如图2所示。

图2 不同权重配比下的区域占比

5 实验与结果分析

通过在实际场景中的实验对本文所提出的定位方法性能进行评估。室内实验环境选在长安大学本部北院主教学楼三楼大厅进行，如图3所示，长约11 m，宽约9 m。该场景是一个半敞开的大厅，利用场景中的柱子来模拟室内遮挡现象。具体实验步骤为：在同一室内遮挡环境下依次布设两种信标布局，在每种布局方式下选取三个位置相同的节点作为待定位的未知节点进行定位实验,如图4所示。根据最大似然估计算法得出每个未知节点的位置估计信息。依据经验的布局方式和最优化布局如图5(a)所示。两类布局方式下的定位结果如图5(b)和图5(c)所示。

图3 实验场景照片

图4 实验硬件设备

图5 不同布局方式下的定位结果

可以看出，最优布局整体定位结果相较于经验布局有所提高。在定位点1处，经验布局和最优化布局的结果相似。但布局在经过优化后，其定位精度和稳定性均得到了提升。

在定位点2，经验布局由于信标B被遮挡，仅依靠A和C来进行位置估计。并且三者处在一条直线上，使得其定位误差较大，稳定性较差。经过布局优化后，该点定位性能得到极大提升。

定位点3，经验布局对该点较为友好，不存在NLOS问题，其获得了较高的定位精度和稳定性。而最优布局仅依赖信标B′和C′进行定位，其定位精度和稳定性有所下降。如图6所示为定位结果的CDF对比，可以看出，经过布局优化后，其定位性能和稳定性均得到了提升。

图6 两类布局下的CDF对比

6 结 论

本文针对室内NLOS环境，面向基于LOS的室内定位，在不改变室内定位算法与增加信标部署数量的前提下，通过优化信标节点的布局方式以提高定位精度与稳定性。通过分析NLOS环境中的GDOP问题，提出了信标节点布局优化的适应度函数，并基于PSO算法对其进行求解。进一步地，对其算法的详细计算过程进行了阐述。随后，通过数值仿真，在遮挡环境中对本文所提出方法的性能进行评估。并对适应度函数的权重对优化结果的影响进行了仿真和分析。结果表明:所提出的适应度函数能够有效解决遮挡环境中的信标节点布局优化问题，并能够通过适应度函数的权重对信标节点布局优化的结果进行控制。通过在实际场景中，对比TOA定位系统在信标节点经验布局和最优化布局下的定位性能，可以看出,经过布局优化后，其定位性能和稳定性均得到了提升。