基于北斗定位的疫情时空伴随者快速匹配方法

于浚清，于先文，黎钊溢，袁昊麟

(东南大学交通学院，江苏 南京 211189)

0 引 言

在疫情防控中，准确确定涉疫对象的时空伴随者，对精准疫情防控具有重要的意义。现行确定时空伴随者的方法主要是通过通讯基站定位，判断两者是否出现在同一信号区域内[1]。此方法原理简单，但由于基站定位精度较低，难以对伴随程度进行准确判定。

目前，我国北斗导航系统已全面向全球提供导航定位服务，其基于高速运动的空中卫星，可实时实现米级定位。以北斗定位技术和智能手机为基础，可建立基于精准时空信息的公共疫情防控系统。其中，对两对象间的精准时空轨迹进行快速匹配是确定涉疫时空伴随者的关键步骤。常规匹配方法是对每个历元的轨迹数据进行遍历，计算对象间距离以及不同距离范围下共存时间，对距离和时间数据进行可视化、轨迹分析等二次处理[2-3]。但在大跨度空间、海量数据下，此方法存在大量无关的冗余运算，智能手机运行负担大[4]。一旦出现突发情况，巨大计算量极易造成智能手机系统崩溃。

针对确定时空伴随者过程中智能手机运算负担大问题，本文提出一种时空伴随快速匹配方法，通过识别并跳过无关轨迹时间段，减少冗余运算，节省计算空间，以提升应用体系的可靠性与稳定性。

1 基于北斗的智能手机定位

目前，智能手机使用已基本普及，其功能也愈加完善。智能手机具有独立的操作系统和开放性的操作平台，根据个人需要可安装多个应用程序。现阶段，在CPU的快速发展之下，智能手机具备更强的运算能力，这为手机进行大数据的运算提供了坚实的基础。同时，智能手机通过移动通信接入因特网，可实时与相关数据中心进行数据交互，具备了在疫情防控系统中承担客户终端的能力。

绝大多数智能手机均能实现北斗实时米级定位。手机APP可通过函数实时读取手机上北斗定位模块测得的用户坐标，根据历元间隔，逐历元获取用户位置数据，进而形成用户轨迹数据[5]。

疾控部门锁定涉疫者后，可将涉疫者的北斗定位轨迹数据发送给普通用户。普通用户可利用个人智能手机自行进行时空伴随程度计算，实时实现群防群控。

2 快速匹配方法

涉疫者一定时间段内的生活轨迹数据量一般比较大，如果普通用户在手机上逐历元与其进行比对，必然会大量占用手机的运算资源。特别是在疫情爆发期，如果不避免大量冗余计算，可能会导致用户手机运行崩溃。通过剔除或跳过两计算对象距离较远的历元，可有效避免冗余计算，实现时空伴随程度的快速判定。下面给出跳过距离较远历元的具体判断方法。

对于ti历元，可得普通用户与涉疫者的距离为

(1)

基于国内的交通方式情况[6]，通过距离Di可以保守得到两者实现近距离时空伴随所需要的时间。当Di>300 km时，两者可能密接的最快速度是同时乘坐飞机前往同一个目的地。考虑到飞机起降时间及飞机速度，可得所需的时间近似为：

(2)

式中，Tf为飞机起降时间；vf为飞机飞行速度，可取经验值。当Di≤300 km时，两者可能密接的最快速度是同时乘坐高铁前往同一个目的地。考虑到高铁进站时间及高铁速度，可得所需的时间近似为：

(3)

式中，Tg为高铁进站所需时间；vg为高铁运行速度，可取经验值。

得到ΔTi后，可计算跳过的历元数：

(4)

从当前历元起，直接跳过n个历元，得到下一个计算历元：

ti+n=ti+n×Δt

(5)

从上述过程可见，当两对象距离较远时，可极大减少计算的历元个数，从而大大减轻系统运算负担，提升高压情况时的应对能力及系统稳定性。

3 算 例

为了进一步展示该方法的使用过程及效果，下面给出一计算案例。

本算例研究对象为用户A与涉疫B，其部分轨迹如表1所示，历元间隔Δt为1 s。为检验用户A与涉疫B的时空伴随性，现对二者14 d中部分轨迹信息进行时空匹配，并验证本方法的快速匹配能力。

表1 用户A与涉疫B部分轨迹数据

算例数据处理过程过程如下：

首先，在第一历元t1时，由式(1)可得两者距离：

(6)

此情况下，判断二者近距离伴随的最快方式为乘坐飞机。一般客机起飞要经过两个爬升阶段才能进入平飞，这个过程要20 min左右；为保证乘客安全，降落速度通常不超过36 km/h，从万米高空降落大概需要16 min[7-8],故综合起飞与降落两个过程，本文取Tf=36 min。民航飞行速度一般在500～900 km/h[8-9]，本文取vf=900 km/h。由式(2)可得

(7)

由式(4)可得跳过的历元数n1=4 287。因此，从当前历元t1起，直接跳过4 287个历元再进行距离判断。由式(5)可得下一个计算历元t4288=13:11:27。进入t4288历元后，可得两者距离

(8)

此时D4288<300 km，判断二者近距离伴随最快的方式为相向乘坐高铁。高铁进站再启动所需时间通常为5 min左右[10],故本文取Tg=5 min，高速列车时速可达300 km[9],本文取vg=300 km/h，由式(3)计算得：

(9)

由式(4)可得跳过的历元数n2=1 038，可得下一个计算历元为t5626=13：28：45。

重复上述匹配过程，直至最后一个历元。部分轨迹数据匹配结果如表2所示，在该时间段内，计算历元数仅占总历元量的3.754%，说明此方法可大大提高匹配速度，避免了冗余计算。

表2 部分轨迹数据匹配结果

4 结 语

本文针对判别时空伴随性巨量计算导致系统荷载过大的问题，提出了一种可跳跃无关历元的时空数据快速匹配算法。基于北斗系统获取的时空数据，利用用户与涉疫者之间的时空关系，按相遇条件越过伴随可能性较低的无关历元，得到下一次可能产生接触的历元，从而实现跳跃式快速匹配。通过算例展示了本文方法应用过程，并进一步验证了本方法可跳跃无效时间区间，减少运算的冗余，实现快速匹配，减轻系统负担的目的。