文章编号：2096-3424（2021）01-0068-07DOI：10.3969/j.issn.2096-3424.20062
何 伟，王 栋，熊宇虹，陈丽琼，刘云翔
（上海应用技术大学计算机科学与信息工程学院，上海 201418）
摘 要：基于蓝牙beacon的室内定位方案在谷歌、苹果等公司的力推下得以广泛应用，但高效解决大规模、高精度的定位问题仍是研究难点。出于信息安全、抗干扰等因素考虑，限制定位信号辐射范围且满足定位精度的“有界”定位方案具有广阔的应用前景。详细阐释有界定位问题的整数线性规划求解方法，证明大型定位问题可分解为多个独立求解的有界定位问题并快速获得次优解，最后通过仿真验证解在beacon个数、耗时等方面的性能。
关键词：蓝牙；定位算法；混合整数线性规划
中图分类号：TN925 文献标志码：A
Bounded Positioning Problem via Bluetooth
HE Wei，WANG Dong，XIONG Yuhong，CHEN Liqiong，LIU Yunxiang （School of Computer Science and Information Engineering, Shanghai Institute of Technology,
Shanghai 201418, China）
Abstract：Indoor positioning via Bluetooth beacon has been widely applied under the promotion of Google, Apple, and other companies, but it is still difficult to solve large-scale and high-precision positioning problems efficiently. Due to information security, anti-interference and other concerns, bounded positioning which keeps the positioning signals in range and achieves desired accuracy is promising in application. The integer linear programming method for solving bounded positioning problems is investigated in detail in this paper. It is proved that the large-scale positioning problem can be decomposed into several independent bounded positioning problems and the sub-optimal solutions can be obtained quickly. Finally, the performance of the solutions in terms of beacon consumption and running time is verified by simulation.
Key words：Bluetooth；positioning algorithm；mixed integer linear programming
基于蓝牙beacon的室内定位方案在苹果与谷歌等公司的力推下迅速成长为向用户智能推送定制信息的新媒体[1]。各类beacon产品层出不穷，并与及云平台相融合，极大提升用户体验并创造巨大的商
业价值。定位应用的多样性发展，催生用户对大规模、高精度、实时定位的迫切需求，使得快速高性价比地解决大规模定位问题日益紧迫。
蓝牙等无线定位方案所依赖的无线通信，因其广
收稿日期：2020-09-03
基金项目：上海市自然科学基金（20ZR1455600）；上海应用技术大学引进人才项目（YJ2019-1）资助
作者简介：何 伟（1982-），男，讲师，博士，主要研究方向为无线定位算法、物联网、光网络故障定位与恢复等。E-mail：
通信作者：王 栋（1981-），男，讲师，博士，主要研究方向为信息系统、智能决策支持系统、信息服务、可信计算和社交网络。
E-mail：
引文格式：何伟，王栋，熊宇虹，等. 蓝牙有界定位问题[J]. 应用技术学报，2021，21（1）：68-74.
Citation：HE Wei，WANG Dong，XIONG Yuhong，et al. Bounded Positioning Problem via Bluetooth[J]. Journal of Technology，2021, 21（1）：68-74.
第21卷第1期应 用 技 术 学 报Vol. 21 No. 1 2021年 3月JOURNAL OF TECHNOLOGY Mar. 2021
播特性天生易被窃听，而使信号有界有助于实现物理隔离和保障信息安全；同频无线信号间极易发生碰撞造成信号质量下降，引发数据丢失、延时等问题，虽有跳频、随机间隔发送等防碰撞手段，但维持信号有界更易缓解问题；对定位应用而言，以GPS电子围栏实现共享单车管理、定位辅助智能泊车[2]、定位辅助区域性舆情分析等应用，在信号有界的情况下更能实现精准高效的研判；本文研究更将证明一些大型定位问题可分解为多个有界问题独立求解，并快速得到次优解。因此，基于保障信息安全[3]、减少信号干扰、实现“有界”应用和加速大型定位问题求解等考虑，将无线定位信号限制在指定区域内且满足定位精度的“有界定位”方案拥有广阔的应用前景。
目前，基于蓝牙beacon进行室内定位的方案尚未关注“有界”定位问题，研究热点主要集中在提高定位
精度与准确性的一般算法、应用拓展和实际部署测试等方面。在一般定位算法方面，文献[4]综述一般无线定位算法的原理并作分析比较。文献[5]研究基于贝叶斯滤波提高蓝牙beacon定位准确性的方法。文献[6]讨论联合使用Wi-Fi和蓝牙进行等级式定位的算法。文献[7]讨论基于粒子滤波和蓝牙beacon 进行智能停车的算法。文献[8]研究基于条件对抗神经网络提高蓝牙定位准确性的方法。文献[9]研究一种半自动调参的系统来提高蓝牙定位的准确性。文献[10]为本文前期研究，系统描述无歧义蓝牙beacon 部署问题并通过混合整数线性规划（mixed integer linear programming，MILP）求解，其仿真表明，该方案所需的beacon个数为苹果iBeacon方案所需个数的12.5%至50%，但对于高精度、大规模的定位问题，该方案耗时较长、逼近理论最优难度增大。应用拓展和部署方面，文献[11]提出一种支持多协议和动态广告内容的蓝牙beacon方案。文献[12]探讨使用常用机器学习算法（KNN和SVM等）的商业低功耗蓝牙（Bluetooth low energy，BLE）室内定位方案，并实测其准确性、训练复杂度和实时跟踪速度。文献[13]综述蓝牙beacon在智慧城市领域所面临的机遇与挑战。
基于以上观察，本文在文献[10]的基础上重点解决有界beacon部署定位问题（bounded beacon deployment positioning，BBDP），同时满足定位精度和定位信号的有界性，并可加速大型定位问题的求解。主要贡献如下：①系统化定义有界定位相关问题，提出对大型定位问题基于有界定位问题进行分解的方法并证明其可行性；②使用MILP对有界定位问题进行建模仿真；③提出功率级约简和外部点定义算法两种预处理技术，辅助MILP求解。
正文组织如下：第1节介绍BBDP问题和大型问题分解与近似求解的方法；第2节讨论BBDP求解方法，其中第2.1节详述BBDP的MILP求解方法，第2.2节介绍所提出的预处理技术；第3节针对BBDP 的特例进行仿真并分析结果；第4节总结全文。
1 有界定位问题建模
定位常在一个有界区域——关心区域（area of interest，AOI）内实施，内部常用等间距的网格描述；测试点（test position，TP）和候选点（candidate position，CP）分别为AOI内需被定位和可eacon 的网格位置；共享信息测试点组（shared interest test position group，SIPG）为一组TP的集合；TP被区分是指不同TP被不同的beacon集合辐射的信号所覆盖；SIPG被区分是指分属不同SIPG的TP可被区分。在不同功率级下beacon可覆盖的区域被称为该级的辐射模式。在特定衰减模型与网格间距下，最大功率级下可覆盖的TP数称为功率密度ϕ，而辐射的最远距离（以网格间距为单位）称为最大辐射半径r[11]。对于图1（a）中的功率级，ϕ=25，r=2.85。
5
5
4
4
3
3
2
2
1
1
−1
−1
列
A
B
C
D
C F
E
(b)(c)
5
5
4
4
3
3
2
2
1
1
−1
−1
列
(d)
5
5
4
4
3
3
2
2
1
1
−1
−1
列
(a)
列
级功率/
dBm
rssi/
dBm
1
2
4
5
6
7
3
−30
−20
−16
−8
−4
4
−12
−91
−81
−76
−68
−66
−62
−60
−74
图1有界beacon部署问题示例
Fig. 1 Bounded beacon deployment demo
第1期何 伟，等：蓝牙有界定位问题69
给定TP 、CP 、SIPG 和功率级集合，部署最少的beacon 使得AOI 内所有TP 被覆盖，所有SIPG 可被区分且beacon 信号不超AOI 边界的问题，被称为BBDP 问题。特别地，当各TP 均为SIPG ，即所有TP 需被区分时，称为有界beacon 部署无歧义定位（bounded beacon
deployment
unambiguous
positioning ，
BBDUP ）问题。
图1演示有界beacon 部署相关问题及其最优解。beacon 信号衰减假设满足对数衰减
[10]
且衰减因子为
3，网格间距g =6 m ，图1（b ）至图1（d ）中的灰框线代表AOI 界限，其内所有的网格点位置（整数坐标）默认都可作TP 或CP 。部署的beacon 为estimote beacon [10]
，图1（a ）为各功率级下所能覆盖的TP 集合。图1（b ）为一个BBDP 问题，其TP 用“+”标注，CP 用“×”标注，名为A ～F 的SIPG 分别用虚框框出各自包含的TP 。图1（c ）为利用本文MILP 求出的最优解，beacon 用“△”标注并以圆形表示其辐射范围，显然不同SIPG 内的TP 被不同beacon 集覆盖且
信号位于AOI 界内。图1（d ）为对应的BBDUP 问题最优解，即25个网格点都为TP 和CP 且TP 都需区分的情况。
大型BBDUP 问题可按定理 1进行分解，各子问题独立求解后合并为次优解。
定理1（BBDUP 分解定理） 设大型BBDUP 问题的AOI 为A o
，可划分为n 个互不重叠的子AOI ：A 1，A 2，···，A n 。以子AOI 及其内的TP 、CP 可定义对应的子BBDUP 问题：P 1，P 2，···，P n ，记其最优解为S 1，S 2，···，S n （解表示为beacon 及其设置的集合）。则
S 1，S 2，···，S n 的并集至少是原BBDUP 问题的次优解。
证明 ①有界性：将大型定位问题划分为多个子BBDUP 问题后，定位信号被限制在各子AOI （A 1，A 2，···，A n ）内，自然也被限制在其并集A o
内。②区分性：由有界性知，各子BBDUP 问题考虑的TP 仅被其私有的beacon 所覆盖，故不同子AOI 内的TP 间必可区分。又，按BBDUP 定义各子问题的解必可区分其内所有TP 。故A o
内所有TP 皆可区分。综合①和②可知，子问题的并集至少是原大型定位问题的可行解，但不一定最优，因为AOI 切分后较原问题增加各子AOI 边界对信号的限制。得证。
2 问题求解
本节介绍有界定位问题的MILP 求解方法及相关的预处理技术。
2.1 BBDP 问题的混合整数规划求解
本MILP 基于文献[10]中给出的MILP 改写而来，主要变化如下：①输入变量新增了预计算的外部点；②距离＞2r 且归属不同SIPG 的“TP 对”不被考虑以加速求解；③根据最大可行的功率级计算beacon 下界；④对功率级预先进行约简。
表1列出MILP 所需的变量设置。注意：①为简化问题，本文假设T 始终为C 的子集；②外部点用于测试beacon 是否越界，其位置不一定在网格上，任意信号越界都应体现为某些外部点被覆盖，不越界时外部点必不被覆盖；③约束（3）、（4）、（7）相对原有MILP
[10]
进行修改，其余不变。
表 1 BBDP MILP 变量设定Tab. 1 BBDP MILP variable settings
输入变量说明
决策变量说明
T 、T e
、C 、G
TP 、外部点(新增)、CP 、SIPG 集合v ij ∈{0,1}v ij 若CP i 安装功率级为j 的beacon ，取1，否则取0Q ij k 位于CP i 的beacon 可否用功率级k 覆盖TP j
q ij ∈{0,1}q ij 若CP i 所在beacon 可覆盖TP j ，取1，否则取0V
功率级集合x k ij ∈{0,1}
x k ij =q ki ·q kj
用于计算两个变量的异或值，C i
可能覆盖TP i 的CP 集合B min
问题所需的最少beacon 数
BBDP 问题可建模如下：
目标函数：
约束：
70应 用 技 术 学 报第21卷
j 目标函数式（1）用于最小化所用的beacon 个数。式（2）保证一个beacon 最多使用1个功率级。式（3）规定beacon 数应不小于预定的理论下界（仍用文献[10]的下界定理，但Φ以不完全覆盖AOI 的最大功率级来计算）。式（4）计算所有T 和T e
内的位置被beacon i 覆盖的情况（依AOI 边界要求调整）。式（5）保证AOI 内的TP 必被覆盖。式（6）规定所有外部TP 不被覆盖，以保证MILP 间的求解独立性（新增）。式（7）保证任意距离＞2r 的分属不同SIPG 的两个TP 必被不同的beacon 集合覆盖（新增|i ，j |≤2r
条件加速求解）。式（8）用于计算两个变量的异或值。
2.2 预处理技术
为辅助MILP 的求解，功率级集合先使用功率级
压缩算法进行约简以减小问题规模，外部点T e
则由外部点定义算法给出。
2.2.1 功率级压缩算法
图2给出功率级压缩算法。
图 2 功率级压缩算法
Fig. 2 Power-level reduction algorithm
设各功率级辐射模式以边界形式给出，有效功率级集合V e 初始为空（行1～2）。对各功率级依次以当前CP 为中心，在网格上用广度或深度优先算法向外（八向）探索本功率级下可覆盖的界内TP 集合P v （行3～5）。若P v 不在V e 中，将其加入V e ，否则代表已存在覆盖相同TP 集的功率级，当前功率级与其等效可忽略（行6～7）。以图1（a ）中的8个功率级为例，级0～3均覆盖1个TP ，级4～5覆盖相同的9个TP ，级6、7分别覆盖21和25个TP ，使用本压缩算法后，降为4个有效功率级，即级0、4、6和7。显然，使用图2给出的算法不影响BBDP 问题最优解的质量。
2.2.2 外部点定义算法
外部点定义可分3种情况，先介绍情况1及相关概念，其余情况在算法中直接介绍。
在x 、y 轴向辐射距离最远的辐射模式称为xy 最远辐射模式（例：圆形、椭圆）。若AOI 中任意一点到x 、y 轴线方向边界点的距离不大于到任意其他边界点的距离，该AOI 称为xy 最近AOI （例：圆形、矩形）。
定理2 考虑按“xy 最远”辐射模式定义的功率级和“xy 最近”AOI ，过AOI 内各CP 作x 、y 方向的直线，记录其与AOI 边界的交点。以所有交点作为外部点，即可检测任意越界。
证明 ①在xy 最远辐射模式下，CP i 在x 、y 轴向的辐射距离最远。故当AOI 对x 、y 轴向的边界约束不松于其他方向时，CP i 越界，x 、y 轴向必越界。②在xy 最短AOI 中，CP i 在x 、y 轴向离AOI 边界的距离最近，即AOI 在x 、y 轴向的边界约束最紧。综合①和②，越界时CP i 的x 、y 轴向必越界。故可用i 在x 、y 轴向与AOI 边界的交点测试是否越界。
推论 对于圆形辐射模式，AOI 为顶点定义在网格上的矩形，以AOI 边界上所经过的所有网格点作为外部点集合即可检测所有越界情况。
证明 由定理2可得。
图3给出MILP 中外部点集合T e
的计算方法。T e
初始为空（行1～2）。①若满足定理2条件，直接取AOI 内CP 与AOI 边界在x 、y 轴方向的交点作为T e 即可（行3～4）。否则，应对各CP i 依次测试是否越界（行5～6）。越界判断方法为：令rp i v
代表CP i 的第v 级辐射模式所围成的区域，若越界则rp i v
和AOI 的差集非空。②若本CP 各功率级的辐射模式满足嵌套包含关系，即低功率级被覆盖的TP 必被高功率级覆盖。可二分搜索越界的最小功率级v m ，若存在v m ，将rp i v
m 和AOI 的差集区域内的任意坐标点
①加入T e
集合即可。③若各功率级不嵌套包含，需测试所有功率级，越界时将各功率级rp i v
和AOI 的差集区域内的任意坐标点加入T e
集合。
定理3 图3算法选取的外部点，可检测任意越界的情况。
证明 图3算法的情况1由定理2直接得证。在情况2下，各CP 所有越界的功率级共享最小越界功率级下的1个外部越界点，越界时该点必被覆盖。在情况3下，各CP 越界的各功率级独用1个外部越界点，越界时必被覆盖。综合3种情况，得证。
第1期何 伟，等：蓝牙有界定位问题71
① 若差集区域用多边形表示，取某多边形顶点即可；若以曲线段表示，在曲线段出界部分上任取一点
图 3 外部点定义算法
Fig. 3 Exterior points definition algorithm
3 仿真结果
所有仿真皆针对BBDUP 问题，衰减因子为3，功率级设置参照图1（a ），求解使用SCIP 7.01软件
[14]
在双核2.2 GHz CPU 、4 GiB 内存的PC 上完
成。求解时限为5 h ，当|T |≤100时，多数可获得最优解。
如表2所示，随着问题规模变大，当间隔g 和衰减因子固定时，所需beacon 数逐渐增加。在相同规模下，间隔g 的大小与所需beacon 数不存在固定关系。例如，对于|T |=5×5，最小beacon 数在g =4 m 时得到，而当|T |=8×8，g =6 m 时得到最佳结果。观察：若|T |很小，只可用很小的功率级才不越界，这对求解造成困难。若|T |较大，需权衡用大功率减少beacon 数和不越界之两难，也可能造成求解困难。
表 2 仿真结果（网格间距与TP 规模）
Tab. 2 Simulation results （grid distance vs TP scale ）
g /m |T |=5×5|T |=8×8|T |=10×10|T |=12×12|T |=15×15
beacon 数/个耗时/s Gap/%beacon 数/个耗时/s Gap/%Beacon/个耗时/s Gap/%beacon 数/个耗时/s Gap/%beacon 数/个耗时/s Gap/%
381021363025 1.8×104
2433 1.8×104
5464 1.8×104
1644101019586025 1.8×10
42530 1.8×10
44463 1.8×104
143583017 1.3×103
020 3.6×103
036 1.8×1047352 1.8×104
926
8
2
16
234
20
3.6×10
30
39
1.8×10
4
89
55
1.8×10
4
115
注：Gap 为所得解与MILP 对应的LP 最优解之差距。
图4展示表2中的部分最优解及性能，显然所有解均满足有界和定位区分的要求。间隔g 为3、4、5 m 时，图4（a ）至图4（c ）和图4（d ）至图4（f ）分别绘制|T |为5行5列和10行10列的情况。图4（g ）研究节省比（|T |与beacon 个数之比）与问题规模的关系。在各间隔下，随着问题规模变大，“节省比”不一定变大。仿真显示一般可获得2.5～5.0倍的节省比，在较大问题规模时（|T |≥64），可获3倍以上的节省比。在同一问题规模下，节省比和间隔也不存在固定的关系，其原因类似对同一规模下beacon 需求的分析。在求解大型问题时，应选择节省比较高的“子问题”以减少
大问题的beacon 消耗数。
表3展示不同网格间距时仿真问题的规模变化（以变量和约束数衡量）。由表3中可看出：①在相同衰减因子下，间隔g 决定最大功率级的辐射半径r 、功率密度φ和约简后的有效功率级数；②间距变大后，最大功率级的辐射半径r 、覆盖的TP 数φ和有效功率级数逐步变小，从而减少ILP 的变量和约束个数，降低求解难度；③采用本文提出的功率级压缩算法可有效无损地降低原问题的求解难度；④上述数据同时与表2中各问题所对应的求解时间和解间距的仿真情况相符。
(a)
55
44
33221100
−1
−1列(b)
55
44
332
21100
−1
−1列(c)
55
44
33221100
−1
−1列72应 用 技 术 学 报
第21卷
