随着iBeacon技术在移动设备上的成熟以及廉价的iBeacon信标设备的普及^[1]，高密集度的信标部署在室内定位中成为可能，基于接收的信号强度指示（received signal strength indication, RSSI）的定位技术在商业应用中也得到了飞速发展。在基于RSSI定位的方法中，信标节点的空间布局极大影响着定位精度^[1]。通常情况下，信标节点部署越密集，定位精度也越高，但当节点密度超过一定程度后，相邻信标的信号易发生串扰，定位精度反而会降低^[2]。此外，信标节点分布的几何结构和RSSI在传播过程中的不稳定等都会影响定位效果^[3]。如何规避各类影响因素，选取最佳的参考信标，是提高定位精度亟需解决的问题。

针对上述问题，业界已开展了多方面的研究并取得了较好效果。如直接优化RSSI，通过低通滤波、均值滤波等方法减弱RSSI传播过程中受到的影响；对信标节点的最佳部署结构进行研究，通过提前优化节点部署来提高定位精度；分析节点部署密度和几何结构对定位精度的具体影响，如低密度环境下信标的最佳几何结构^[4]，在指定区域探讨如何部署信标节点以达到最佳定位效果^[5]。文献[6]表明，信标节点部署间距至少不低于指定检测区域半径的两倍才能避免RSSI串扰。也有优选定位解算阶段参考信标，其中基于近似三角形内点测试法定位算法（approximate point-in-triangulation test, APIT）和在此基础上改进的基于信标节点筛选的定位算法（locating algorithm based on selection of beacon nodes，LASBN）^[7]均主要通过三角形内点测试法筛选出合适的信标节点群。文献[8]比较了节点筛选的几种方案，结果表明，基于熵的方案^[9]选取的节点能达到最好效果。动态信息驱动方案以确定一个领导节点为基础，根据布局最近规则选出其他节点^[10]。基于最小均方差的解决方案则是通过计算不同节点组合，使解算出的目标位置的均方差最小^[11]。以上研究表明，通过优选参考信标能明显改善定位效果。

上述方法均起到了一定效果，但对信标部署完成后信标间的空间布局关系在定位优化中的作用少有研究，如何利用信标节点已存在的空间布局关系来优化定位是本文所探讨的问题。本文提出了一种通过优选参考信标节点来优化室内定位的算法，该算法相比传统的三边定位算法，新增了区域最佳信标组合库建立和参考信标优选两个核心模块（图 1），利用空间布局信息从实时信标序列中筛选出能达到较好效果的信标组合来优化定位。该算法主要作用于定位信标部署完成后与三边解算前的参考信标优选阶段，能够与上述许多研究方法结合使用，互为补充，进一步优化定位效果。

1 信标节点布局与三边定位 1.1 信标节点布局

信标节点的空间布局包括信标节点的空间密度和空间拓扑结构等信息。信标节点的布局通常因定位需求而异，若精度要求高，信标需密集部署，相反则可稀疏部署，均匀合理的信标部署一般会有较好的定位效果。参考信标节点常见的部署方式，可以将信标节点布局结构分为独立节点、线状布局和面状布局3种结构。其中，面状布局是最为常见的布局方式，大多数室内定位场景信标节点的布局都是面状。在面状布局中，因密集部署引起的信号串扰问题也更突出，对参考信标的准确选取也更加困难。本文将利用信标空间布局关系优选定位参考信标，实验所用的iBeacon信标属于短距离定位设备，适合于在室内场所中呈面状的密集部署^[12]。

1.2 三边测量定位

三边测量定位算法根据信号强度随距离衰减模型得到未知点到参考点的距离^[13]，结合已知参考信标的位置解算未知点的位置。如已知3点位置$\left({{x_1}, {y_1}} \right)、\left({{x_2}, {y_2}} \right)、\left({{x_3}, {y_3}} \right)$到未知点$\left({{x_0}, {y_0}} \right)$的距离分别为${d_1}、{d_2}、{d_3}$。以${d_1}、{d_2}、{d_3}$为半径作3个圆，交点即为未知点位置，即：

$ \left\{ {\begin{array}{*{20}{c}} {{{\left( {{x_1} - {x_0}} \right)}^2} + {{\left( {{y_1} - {y_0}} \right)}^2} = {d_1}^2}\\ {{{\left( {{x_2} - {x_0}} \right)}^2} + {{\left( {{y_2} - {y_0}} \right)}^2} = {d_2}^2}\\ {{{\left( {{x_3} - {x_0}} \right)}^2} + {{\left( {{y_3} - {y_0}} \right)}^2} = {d_3}^2} \end{array}} \right.$

(1)

在较高密度的信标部署环境中，三边测量定位解算的定位精度受所选参考信标影响极大。若能准确选择较优的参考信标节点，则能准确定位未知点所在的局部区域，再利用三边测量定位，容易得到较准确的定位结果。若选择的参考信标节点不恰当，则易导致三边测量解算出现较大误差。

2 信标节点优选定位算法

依据信标节点空间布局，定位场景可划分为多个独立单元区域。对于其中的每个单元区域，都存在几个空间关系紧密的信标节点，若这些节点的部署密度与几何结构能够使该区域内的设备实现较好的定位效果，则该信标组即为区域最佳信标组合。由区域最佳信标组合构建的集合即为区域最佳信标组合库。通过实时扫描的信标序列与最佳信标组合进行匹配，即可实现对参考信标节点的优选。

2.1 区域最佳信标组合库构建

基于信标节点基础信息建立区域最佳信标组合库的总流程如图 2所示，其主要过程可分为信标空间关系提取和区域最佳信标组合库构建两部分。信标空间关系提取通过基于线状分布的邻近关系和面状分布的三角形点边关系实现，区域最佳信标组合则基于提取到的信标关联关系，通过逐层搜索新增信标的方式构建。

信标节点部署完成后，可获取其基本信息，即图 3中信标的ID、MAC、X、Y、Type等信息，其中ID为编号，MAC为设备地址，X、Y为坐标位置，Type为部署类型。图 3详细描述了在不同布局模式下，利用基于信标节点的基础信息生成信标空间关系来构建区域最佳信标组合库的详细过程，包含信标空间位置信息、信标空间关系信息和区域最优信标组合信息的组成结构描述。

2.1.1 空间布局构建信标关联关系

本文研究的信标空间布局主要为线状布局和面状布局。线状布局的信标节点空间关系主要为点间关系，通过最邻近算法寻找中心信标点最相邻的两个信标实现，存储结构为图 3中的“点：点1，点2”结构。面状分布的信标节点空间关系主要为三角形底边与顶点间的点边关系，基础三角形单元采用不规则三角网（triangulated irregular network, TIN）算法生成^[14]，TIN算法优先构建锐角三角形的特点能将区域中的信标节点用较好拓扑结构的三角形关联起来。面状布局信标间关联关系存储结构为图 3中的“边：点1，点2”。从信标基础信息到构建信标间空间关联关系的具体流程如下：

1）加载区域内所有信标信息，按分布类型（线状、面状）将信标分为两类。

2）对线状分布的信标以任意信标为中心，按信号有效距离域值L选取待选信标，构建中心信标与待选信标的连接边。对于面状分布的信标，用TIN算法生成关联三角形网络，三角形边为关联信标连接边。

3）加载研究区域的矢量区划数据，通过矢量区域内线要素提取算法，移除不完全处于区域内的连接边，如图 4中AD与AB边穿墙被移除。

4）对于线状分布的信标，从剩余连接信标中通过最邻近方式提取中心信标的左右关联信标。对于面状分布的信标，选取一条连接边为中心，获取以该边为底边的三角形顶点的对应信标为关联信标。将提取的关联信标按对应结构存储。

5）遍历所有线状分布中的节点和面状分布中的边，重复步骤4），即可完成对整个区域内信标间空间关联关系的构建。

2.1.2 区域最佳信标组合库构建

依据信标关联关系库中的点间关系和点边关系，可搜索建立各局部区域所对应的最佳信标组合。不同空间布局均采用一致的区域最佳信标组合存储格式——“边：序列1，序列2”的结构进行存储，以方便统一管理使用。基于信标节点间关联关系构建区域最佳信标组合库的步骤如下：

1）选取一组关联信标的连接边为区域中心，确定当前信标的布局类型。

2）对于线状布局的信标，分别以构成连接边的两个信标从库中按点间关系寻找新关联信标。对于面状布局的信标，首先以边为中心从库中按点边关系寻找内层关联信标，再将关联信标与原信标两两组合，构成新的边，以同样方式从库中寻找外层关联信标。

3）对于线状布局信标，以“边：序列1”的形式存储。对于面状布局的信标，搜索到的关联信标对应内外两层，以“边：序列1，序列2”的形式存储，其中“序列1”比“序列2”更接近区域中心，有更大的参考价值。

4）重复步骤1）~3），遍历区域内所有信标连接边，完成整个区域内区域最佳信标组合库的构建。

对整个搜索过程进行结构化表示，类似一种树形结构（图 3最优信标组合部分），离顶层越近的参考节点的意义越大，总的搜索过程类似于对该树进行广度优先搜索得到的结果。在图 3的示例中，对于线状布局，A、B信标提取的空间关系分别为“A：B，C”、“B：A，D”。以AB为中心，依据空间关系搜索得到新的信标为C、D，最终区域最优参考信标组合为“AB：ABCD”（图 3第1个示例）。对于面状布局，AB边从三角网中提取点边关系为“AB：C，D”，首次搜索得到的内层关联信标为C、D；与A、B信标组合构成新的边AC、AD、BC、BD，进一步搜索得到外层关联信标，进而得到完整的两层最佳信标组合结构为“AB：ABCD，EFGH”（图 3第3个示例）。若由点边关系未搜索到新的关联信标，则得到非完整的两层结构为“AB：ABCD，EF”（图 3第2个示例，AD、BC边无新的关联信标）。当信标节点的部署越均匀时，同一层的各信标节点到区域中心的距离越接近。

2.2 匹配优选参考信标定位

对移动设备扫描获取的信标序列，首先按RSSI进行排序，然后与区域最佳信标组合进行匹配，筛选出能够达到较优定位效果的信标节点组合，并根据优选参考信标结果评判该信标序列的可用性，以评估最终定位结果的可信度。

对设备实时获取的信标序列，距离信标节点越近，RSSI越大，可信度越高^[15]，因而可选择RSSI最大的两个信标进行组合，作为当前移动设备所在区域的中心，再从库中匹配相对应的最佳信标组合。如设备在AB区域扫描的信标序列按强度排序为ABDICEHLJK，当前区域最佳信标组合为“AB：ABCD，EFGH”。选择前4个信标节点，按RSSI排序为ABDI，匹配优选为ABCD，优选得到该区域最优的参考信标组合具有更好的参考效果。复杂环境中，若存在I点RSSI强于B点情况，而信标组合AI在最佳信标组合库中无对应信息。为避免匹配失败，通常选择RSSI的前3个或者前4个信标两两组合（根据信标节点的部署情况和计算资源确定）来寻找对应的区域最佳信标组合。对于匹配出的多组信标序列，依据其匹配评分对各组结果加权得到最终结果。选择最佳参考信标定位的流程如图 5所示。

对中心信标组合排序位置评分和实时信标序列与最佳信标序列的匹配情况分别评分，再对两个评分进行加权平均，得到最终优选出的信标组合的评分，作为本次信标优选结果的评价指标。具体评分计算步骤如下：

1）计算实时扫描RSSI得到区域最佳信标组合的评分${M_A}$。令N为选来两两组合成中心边的信标数量，i、j为信标编号$\left({0 \le i, j \le N - 1;i \ne j} \right)$，有：

$ {M_{{A_{i,j}}}} = \frac{{2\left( {N - 1} \right) - \left( {i + j} \right)}}{{\left( {N - 1} \right) + \left( {N - 2} \right)}}$

(2)

2）计算区域最佳信标组合与实际扫描信标优选情况的评分${M_B}$。i、j区域最佳信标组合中序列1、序列2用L_A、L_B表示，实时扫描信标为L_S，L_A与L_S匹配数为L₁，L_B与L_S匹配数为L₂（线状分布时L_B=0），有：

$ {M_{{B_{i,j}}}} = \left\{ {\begin{array}{*{20}{l}} {\frac{{{L_{{1_{i,j}}}}}}{{{L_{{A_{i,j}}}}}} \times 0.7 + \frac{{{L_{{2_{i,j}}}}}}{{{L_{{B_{i,j}}}}}} \times 0.3,{\rm{}}{L_{{B_{i,j}}}} \ne 0}\\ {\frac{{{L_{{1_{i,j}}}}}}{{{L_{{A_{i,j}}}}}},{\rm{}}{L_{{B_{i,j}}}} = 0} \end{array}} \right.$

(3)

3）对两组评分进行加权求和，得到由i、j区域最终优选出定位参考信标节点的评分：

$ {M_{{S_{i,j}}}} = {M_{{A_{i,j}}}} \times 0.5 + {M_{{B_{i,j}}}} \times 0.5$

(4)

4）本次算法最终优选出的定位参考节点的评分${M_S}$为各组评分的总和：

$ {M_S} = \mathop \sum \nolimits {M_{{S_{i,j}}}}$

(5)

实际应用中，依据定位的具体需求、信标节点的实际部署情况和定位时间间隔等综合考虑确定N的值。对定位精度要求不高、对设备有节能需求或信标部署较合理时，可以仅选择前两个信标用单组区域最佳信标组合来优化定位。

3 实验与分析 3.1 实验区域选择

本文选取实验室机房和走道作为实验场所，长为28 m，宽为24 m，共布设32个信标，实验设备为小米手机。iBeacon信标部署在墙壁两侧，呈对称形式，信标左右间隔2~4 m，相对间隔4 m左右，具体部署情况如图 6所示，密集且对称的部署模式增强了信标间信号的串扰。实验中信号序列采集频率为每秒1次，分别在实验场的14个不同位置（图 6中1~14点处）各采集100组数据，去除开始和结尾部分各25组，保留中间50组数据。分别对各采样点位置获取的信标序列用不同的算法进行定位解算，得到各采样点50组结果的误差均值和误差标准差。基于各类方法在采样点的误差均值曲线和误差标准差曲线以及总体误差均值和误差标准差的统计值，综合比较分析本文算法的优化效果。

图 6中灰色区域为实验区域，其中信标节点间的连线为生成三角网的边，虚线为研究区域与连接边进行空间运算后删除的不合理边，黑色实线为信标间关联关系的连线。黑色连线将研究区域拆分为多个三角形单元，各三角形均由拓扑结构较优（节点间距离接近，且基本为锐角三角形）的3个信标构成，可见TIN构建三角网的优势让三角形组成较为合理，以信标间连线作为各局部区域中心，对整个研究区域具有较好的概括。

3.2 定位优化效果

对采集并排序后的信标序列用以下几种方式进行定位解算：（1）取序列的前4个、前6个信标直接进行定位解算；（2）利用前3个信标确定区域中心，用k近邻法（k-nearest neighbors, kNN）取距中心点最近的4个信标进行定位解算；（3）利用采样位置的最佳参考信标组合进行位置解算（最佳参考信标组合由当前采集点周围物理布局最合理的信标节点组成）；（4）利用LASBN算法优选参考信标进行定位解算；（5）通过本文算法优选的信标组合进行定位解算。对以上几种解算结果进行统计，分析比较不同方法的效果。

图 7为采样点误差均值分布曲线图，图 8为定位误差标准差分布曲线图，表 1为不同算法所有采样点的误差均值和误差标准差统计表。从图 7、图 8可以看出，直接用RSSI排序选取信标解算存在较大的定位误差，采样点中最大的误差均值达到2 m，同时误差波动较大。随信标选取数的增加，定位误差呈增大的趋势，原因在于随参考信标的增加，引入错误参考信标的概率也随之增加。利用kNN优选一定程度上优化了定位效果，采样点的平均误差为1.228 m，但其误差波动仍较大，存在较大的误差点，这与实验场所信标的密集部署和信号串扰导致的中心位置偏移有关。通过LASBN算法优选参考信标对定位精度有较大的改善，所有采样点的平均误差为0.974 m，误差波动也相对减小，即定位结果相对较稳定，具有较好的应用效果。而利用参考最佳信标组合直接筛选实时信标序列进行解算，各采样点的误差均值均在1 m以内，总平均误差为0.747 m，标准差为0.210 m，具有很好的定位效果，表明若能准确地选出最佳的参考信标节点，则对定位效果有明显改善。本文优化算法的总误差均值为0.889 m，标准差为0.362 m，其效果较直接解算（前4个和前6个信标）和kNN有明显改善，优于LASBN算法，与参考最佳信标组合筛选得到的效果更接近，但仍具有较大波动。虽然本文算法是基于区域最佳参考信标组合优选实时信标序列，但信号的波动使对局部区域的确定存在偏差，导致优选的参考信标难以达到参考最佳的效果。

3.3 优选评分分析

在3号采样点处持移动设备分别朝东南西北4个方向各采集信号50组，得到200组信标序列。用§2.2的方法对优化算法信标序列的匹配情况进行评分，并将所有信标序列依据其评分值由高到低进行排序，如图 9所示，横坐标的信标序列编号越小，其对应评分值越高，纵坐标对应着各个信标序列的定位解算误差。按信标序列优选的评分排序，将其分为评分较高、评分居中和评分较低3个区间。从图 9中可以看出，随着评分降低，优化后的定位误差曲线的波动性增强，定位误差值总体呈增大的趋势。评分较高区间较其他区间误差的分布情况总体较优，评分居中时的误差波动较大，评分较低区间的误差总体偏高。优化算法的评分在一定程度上反映了实时扫描到的信标节点的RSSI与其实际物理位置的匹配程度（即距离信标越近，RSSI值越大）。评分越高，说明参考节点总体RSSI与实际情况越相符；评分越低，则说明某些参考信标的RSSI受噪声影响严重，导致最终定位精度低，不稳定性增加。

4 结语

本文基于区域最佳信标组合研究了信标节点的空间布局关系对定位效果的改善，即理论上任意局部区域都存在一组达到最佳定位效果的参考信标节点。该算法主要在传统三边定位算法的基础上增加了利用空间布局对参考信标节点进行优选的步骤。实验表明，本文算法在信标节点优选中的效果较好，接近理论最佳参考信标组合。此外，本文研究只是对参考信标节点的优选，在寻找出区域最佳参考信标组合前，需要确定当前设备所在的局部区域，当信号受到严重干扰、无法通过扫描信标准确确定当前设备所在的局部区域时，则无法利用该算法进行有效优化，后续将针对这一问题进行更深入的研究。