蚁群算法在室内地磁定位中的应用

2020-03-24郭燕莎

天津职业技术师范大学学报 2020年1期

郭燕莎

（天津职业技术师范大学信息技术工程学院，天津 300222）

室内定位作为移动互联网发展的应用领域之一，正在直接或间接地影响着人们的工作和生活。在生活中可用来监控老人和小孩的活动，可为残疾人提供实时的导航帮助，并在危急时刻自动求助；在购物时可协助用户便捷获取需求商品的位置和信息；在困境中可及时引导救援人员快速解救危难者；在参观时可为游客实时展现作品信息。此外，室内定位还可应用于医疗管理、公共事务和网络安全等领域。室内定位的广阔前景吸引着国内外众多学者和机构对其进行研究和探索。超声波[1]、红外线[2]、射频识别[3]、WIFI[4]、Zigbee[5]和蓝牙[6]等是常用的室内定位技术，定位精度较高，且各有优缺点和适用场合，但共同特点是需预先在环境中安装无线网络或额外设备，以接收和发射信号，再按照多边测量或指纹匹配等算法实现定位。前期准备和后续维护工作将耗费一定的时间以及人力、物力和财力。

利用和挖掘环境中现有资源进行室内定位已然成为学者关注的焦点和努力的方向。不同研究者根据具体需求和环境特征提出了单一和融合的室内地磁定位，精度较高，可满足一定的位置服务需求。Haverinen 等[7]基于地下铁矿石引起的地磁异常，采用蒙特卡罗算法实现地下采矿环境定位，该技术可为基础设施要求较低的地下环境提供一种高效的定位方案；申文波[8]通过改进粒子滤波算法融合地磁指纹和惯性传感器信息进行室内定位研究，实现了2 m的定位精度；周家鹏等[9]通过克里金插值算法，在环境中建立地磁数字基准图（地磁值模），然后利用动态时间规整算法实现室内定位，具有较高的理论和实际应用价值；李思民等[10]在手机室内定位系统中融合了PDR 和地磁指纹信息，实现了2 m 的定位精度；而宋宇等[11]为了进一步提高精度，在WIFI 和PDR 组合定位的基础上又融合了地磁指纹信息，使平均定位误差降低至1.41 m；张文杰[12]采用改进的粒子滤波算法融合RFID 和地磁指纹信息进行室内定位，1 m 内的累积概率达82%。上述定位过程均使用了地磁指纹匹配，但并未考虑随时间和外围环境而变化的地磁特征、不同位置间某个或多个维度地磁属性的相似性、不同位置间地磁值模的相似性等。基于地磁场的室内定位研究和应用还有待于进一步探索。针对目前地磁定位存在的问题，本文首次将蚁群算法引入室内定位的地磁指纹匹配过程，并通过实验测试，比较了提出的6 种思路与最近邻算法（k-nearest neighbor，KNN），结果表明蚁群算法应用于室内定位是合理和可行的，且位置识别率较高。

1 蚁群算法概述

蚁群算法是受自然界真实蚁群觅食过程启发而提出的一种群智能算法。基本思路[13]为每只蚂蚁在寻找食物的过程中，可感知路径上已存信息素的同时，也会在路径上留下信息素；而且每个个体都是朝着信息素强度高的方向移动，随着时间推移，路径越短信息素越强（因挥发少留存多），进而吸引其他蚂蚁访问的次数相应增多；久而久之，整个蚁群都可找到最短路径的食物源，此为蚁群算法的目的所在，也即问题的最优解。室内定位原则是在环境中实时采集地磁属性（测试数据），并分别与数据库中每个位置的属性值（训练数据）进行比较，属性越相似，其所在位置被匹配的概率就越大；测试数据与训练数据间的相似度相当于蚁群算法中的信息素，所找到的信息素最强的位置即为与测试数据最接近的位置。二者的相似性是在室内定位中引用蚁群算法的直接原因。

蚁群算法已广泛应用在监测网优化、旅行商问题[14]、物流配送[15]和车辆路径规划[16]等领域，并取得了显著成果，但在室内定位中却鲜有文献描述。本文提出的6种思路，旨在通过蚁群算法提高定位过程中的地磁指纹匹配精度。

2 蚁群算法在室内定位中的应用

2.1 数据采集

本研究基于某工作区域8 个工位的地磁场（X，Y，Z）数据进行分析，采集数据位置如图1 所示。该环境为典型的工作场所，配备有电脑、桌子、椅子、柜子和公用打印机等设施，工作时间启用的公共设备和人员流动可能影响环境中的地磁属性；总覆盖面积约6 m2，不同工位间的最大距离为2.4 m，最小距离是1 m。

图1 采集数据位置

数据采集过程：利用自主研发的手机APP 整点采集数据，工作日从9 点—21 点，周末从11 点—16 点，每个工位每次收集325 条记录，共32 d。

数据处理过程：第1～16d 样本是训练数据，第17～32d 样本为测试数据；由于直接采集的样本波动较大，故首先对其进行卡尔曼滤波处理[17]，取较为稳定的最后25 条记录作为当前时间点的训练数据；而测试数据则取滤波后的最后1 条记录，实验中仅选用有代表性的 10 点（80 条记录）、15 点（136 条记录）和 21 点（80条记录）的数据进行测试、比较和分析；其中，10 点和15 点为工作时间，环境较为嘈杂，21 点为非工作时间，环境较为简单；每个工位的测试数据包括37 条记录。

2.2 算法描述

本研究首次将蚁群算法引入室内定位的地磁指纹匹配过程，并通过实验对提出的6 种定位思路和KNN 算法进行了比较。

2.2.1 基于KNN算法的定位思路

比较测试数据与不同位置训练数据间的差异性，平均差值最小的位置即为测试数据所在位置。采用式（1）计算的欧式距离d 表示差异性程度，其值越小说明测试数据和训练数据越相似；反之，差异性则越大。

式中：（x1，y1，z1）和（x2，y2，z2）分别为测试数据和训练数据的三维地磁属性值。

由KNN 算法可知，与测试数据最相似或最接近的训练数据所在位置即为当前测试数据的所属位置，本算法适用于不同位置间的地磁属性完全相异，同一位置不同时间点的地磁属性基本一致。但由于地磁场易受环境因素影响，从而使得同一位置不同时段的属性值可能相异，不同位置同一时段的属性值可能相似，故室内定位中已不能完全依赖KNN 算法进行地磁指纹匹配。

2.2.2 基于蚁群算法的定位思路

根据特定规则选择一个待选工位，将其地磁属性与测试数据比较后，更新该位置信息素。每次迭代后，依据蒸发系数更新所有工位信息素，其中，信息素最大的工位即为当次迭代的测试数据所属位置。完成指定迭代次数后，出现频率最高的工位即为测试数据的最佳位置。具体执行步骤如下。

（1）参数设置和初始化启发式因子

蚁群算法在地磁指纹匹配过程中的相关参数设置如表1 所示。

表1 蚁群算法在地磁指纹匹配过程中的相关参数设置

表1中：α 和 β 分别为信息素强度 τ 和启发式因子 δ 在蚁群寻优过程中的相对重要性；ρ（0 ＜ ρ ＜ 1）为寻优路径上留存信息素的蒸发系数；（1-ρ）为留存信息素的持久性系数[18]。

本文在初始化启发式因子时考虑了2 种情况：①测试数据与每个工位训练数据第1 条记录的欧式距离倒数作为启发式因子；②测试数据与每个工位相同时间点训练数据第1 条记录的欧式距离倒数作为启发式因子。启发式因子和距离值d 互为倒数，即测试数据与训练数据的差异越小，启发式因子越大。

（2）随机选择第1 个访问目标和确定未访问位置

每只蚂蚁随机选择一个位置作为出发点，也就是m 只蚂蚁随机选m 个位置作为第1 个访问目标。随后每次迭代，每只蚂蚁需遍历所有工位与测试数据比较，故应先确定所有未访问工位，然后再按照规则选出下一个待访问目标。

（3）选择下一个待访问目标

选择下一个待访问目标并计算测试数据与待访问位置训练数据间的欧式距离和sum。分2 种情况选择下一个待访问目标，并针对如何从待访问工位选择训练数据与测试数据相比较，提出了6 种思路。

情况1 从未访问工位中随机选择下一个待访问目标k。随后，计算测试数据与待访问工位训练数据间的欧式距离和，选择训练数据的方式为：①Loc 算法，从待选工位的训练数据中随机选5 条记录；②Loc_Time 算法，从待选工位的训练数据中随机选5 条与测试数据时间点一致的记录。

情况2 依据信息素强度和启发式因子，计算每个未访问工位的状态转移概率Pk[18]，见式（2），并通过比较累积概率与生成的随机数确定下一个待访问目标k。

式中：visited（end）为最后 1 个已访问位置；τ（visited（end））和 τ（k）分别为最后 1 个已访问位置和第 k 个未访问位置的信息素强度；δ（visited（end））和 δ（k）分别为最后1 个已访问位置和第k 个未访问位置的启发式因子。

随后，计算测试数据与待访问工位训练数据间的欧式距离和，选择训练数据的方式为：①Loc_Prob算法，从待选工位训练数据中随机选5 条记录；② Loc_Time_Prob 算法，从待选工位训练数据中随机选5 条与测试数据时间点一致的记录；③Loc_Prob_Diff 算法，根据待选工位在有序信息素中的顺序，依据代码的设置规则确定从训练数据中选的记录数；④Loc_Time_Prob_Diff 算法，根据待选工位在有序信息素中的顺序，按照同样规则确定从训练数据中选几条与测试数据时间点一致的记录。

从训练数据中选择记录数的设置规则：

%order 是当前工位在有序信息素中的顺序号

%Loc_Prob_Diff 算法：num 是选定待访问工位训练数据的总记录数

%Loc_Time_Prob_Diff 算法：num 是选定待访问工位训练数据中与

%测试数据时间点一致的总记录数

if order＞=1&order ＜3

visitP=randperm（num，8）；

elseif order ＞=3&order ＜6

visitP=randperm（num，6）；

else visitP=randperm（num，4）；

（4）更新不同位置的信息素

更新当前位置的信息素，信息素是蚁群觅食过程中彼此沟通的媒介。根据训练数据与测试数据间的相似度（欧式距离），更新当前位置的信息素[3]。

式中：Δτ（k）为第k 个工位的信息素更新量。

每次迭代时，测试数据均与所有工位比较；随后，依据相似度更新每个位置的信息素。蚂蚁觅食规则：在追踪信息素寻找食物的过程中，信息素也在不断挥发；将此迁移到位置寻优中，按式（4）完成所有工位的信息素更新。

将信息素强度按从大到小的顺序排序，信息素强度越大，说明测试数据越接近该位置的地磁属性；Loc_Prob_Diff 算法和Loc_Time_Prob_Diff 算法正是根据这个排序结果，确定从训练数据中选择记录与测试数据进行比较的。

（5）获得测试数据的最佳位置

获取本次迭代中信息素最大的位置：由式（3）和式（4）可知，测试数据与训练数据间的差距越小（越相似），信息素强度则越大，故信息素强度最大的工位极有可能是测试数据的所属位置。

统计所有迭代中出现次数最多的位置：每次迭代完，都可获取到当次迭代的最佳位置；多次迭代后，出现次数最多的即为测试数据所属的最佳位置。

2.3 结果比较与分析

本研究在某工作区域采集了不连续的32d 地磁数据进行实验测试，跨度较大，覆盖较全。以下将分别从不同时间点的定位精度、不同工位的正确匹配数和不同算法迭代过程中识别的正确工位数3 个方面进行分析和讨论。

2.3.1 不同时间点的定位精度

不同算法的定位精度比较如表2 所示，其中，第2列为本文提出的6 种思路和KNN 算法的室内定位精度，第3-5 列分别表示在10 点、15 点和21 点的位置识别率。从表2 可知，KNN 算法的定位精度最低；Loc、Loc_Time、Loc_Prob、Loc_Time_Prob 和 Loc_Prob_Diff算法的定位精度类似，彼此间的差距为0.68%～2.37%；Loc_Time_Prob_Diff 算法的地磁指纹匹配过程融合了上述5 种思路的定位细节，其总体定位精度最高，可达82.77%。

表2 不同算法的定位精度比较

由于每个时间点测试数据包含的记录数不同，故位置识别率的计算方式为某时间点的正确位置匹配数与该时间点测试记录总数的比值。本文提出的6 种思路在不同时间点的位置识别率均高于KNN 算法。除Loc_Time_Prob 算法在21 点的位置识别率略高于Loc_Time_Prob_Diff 算法外，后者在定位精度和3 个时间点的位置识别率均高于其他算法。总体上，21 点的位置识别率最高，Loc_Time、Loc_Prob、Loc_Time_Prob和Loc_Time_Prob_Diff 算法在10 点的位置识别率高于 15 点，而 KNN、Loc 和 Loc_Prob_Diff 算法则正好相反，但差别不大。其原因是10 点和15 点属于正常工作时间，环境中启动的机器设备和密集的人员流动导致地磁场波动较大，从而使得同一位置不同时段的地磁属性不一致或不同位置间的地磁属性相互干扰，造成位置匹配率降低；而21 点则是非工作时间，工作场所中仅有少量的人员活动和设备启动，降低了环境对地磁场的影响程度，位置识别率也就相应提升。总之，室内的地磁属性随时间和环境状态而变，导致室内地磁定位精度也随之改变。

2.3.2 不同工位的正确匹配数

测试数据中每个工位都有37 条记录，本研究分别统计了不同定位算法识别每个工位的正确率。基于不同算法获取的正确位置匹配数如表3 所示，从表3可知，工位 1（8.1%～56.8%）和工位 7（2.7%～73%）的正确匹配数最低，工位8 的正确匹配数（66.7%～73%）次之；工位2 的每条测试数据均可得到正确匹配位置（100%）；工位 3、4 和 5 的正确位置匹配数较高（89.2%～100%），而工位 6 则略低（83.8%～94.6%）。

表3 基于不同算法获取的正确位置匹配数

KNN 算法作为典型的位置指纹匹配方法，只要不同位置间的属性值完全相异，同一位置不同时间点的属性值基本相同，KNN 算法便可精确地进行位置识别。从表3 中可以看出，因工位2-6 的地磁属性较为独立，干扰较少，故KNN 算法对其识别率较高；而工位1、7 和8 的地磁属性波动较大，且受环境干扰多，相应地，KNN 算法的识别率就较低，尤其是工位1 和工位7。本文提出的6 种算法不仅可以保持对易识别工位的高匹配率，同时又可提高对工位1、7 和8 的识别率。值得注意的是：Loc_Time_Prob_Diff 算法虽对工位4-6 的识别率略低于KNN 算法，但却大幅提高了对工位1、7 和8 的位置匹配度，其识别率分别增长了48.6%、67.6%和24.3%。

2.3.3 不同算法迭代过程中识别的正确工位数

不同算法迭代过程中的位置识别数如图2 所示。较为明显的是Loc_Time_Prob_Diff 和Loc_Prob_Diff 算法，前者从第2 次迭代开始每次识别出的正确位置数都远超过其他算法，且自第3 次迭代后，每次的位置识别数较为稳定（最大值：245，最小值：225）；后者在大部分迭代过程中的位置识别数均低于其他算法，且波动较大（最大值：220，最小值：194）。其他4 种算法每次迭代时的位置识别数较为相似，且变化幅度不大（最大值：227，最小值：214）。