基于北斗定位的疫情時(shí)空伴隨者快速匹配方法

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

(東南大學(xué)交通學(xué)院，江蘇 南京 211189)

0 引 言

在疫情防控中，準(zhǔn)確確定涉疫對(duì)象的時(shí)空伴隨者，對(duì)精準(zhǔn)疫情防控具有重要的意義。現(xiàn)行確定時(shí)空伴隨者的方法主要是通過(guò)通訊基站定位，判斷兩者是否出現(xiàn)在同一信號(hào)區(qū)域內(nèi)[1]。此方法原理簡(jiǎn)單，但由于基站定位精度較低，難以對(duì)伴隨程度進(jìn)行準(zhǔn)確判定。

目前，我國(guó)北斗導(dǎo)航系統(tǒng)已全面向全球提供導(dǎo)航定位服務(wù)，其基于高速運(yùn)動(dòng)的空中衛(wèi)星，可實(shí)時(shí)實(shí)現(xiàn)米級(jí)定位。以北斗定位技術(shù)和智能手機(jī)為基礎(chǔ)，可建立基于精準(zhǔn)時(shí)空信息的公共疫情防控系統(tǒng)。其中，對(duì)兩對(duì)象間的精準(zhǔn)時(shí)空軌跡進(jìn)行快速匹配是確定涉疫時(shí)空伴隨者的關(guān)鍵步驟。常規(guī)匹配方法是對(duì)每個(gè)歷元的軌跡數(shù)據(jù)進(jìn)行遍歷，計(jì)算對(duì)象間距離以及不同距離范圍下共存時(shí)間，對(duì)距離和時(shí)間數(shù)據(jù)進(jìn)行可視化、軌跡分析等二次處理[2-3]。但在大跨度空間、海量數(shù)據(jù)下，此方法存在大量無(wú)關(guān)的冗余運(yùn)算，智能手機(jī)運(yùn)行負(fù)擔(dān)大[4]。一旦出現(xiàn)突發(fā)情況，巨大計(jì)算量極易造成智能手機(jī)系統(tǒng)崩潰。

針對(duì)確定時(shí)空伴隨者過(guò)程中智能手機(jī)運(yùn)算負(fù)擔(dān)大問(wèn)題，本文提出一種時(shí)空伴隨快速匹配方法，通過(guò)識(shí)別并跳過(guò)無(wú)關(guān)軌跡時(shí)間段，減少冗余運(yùn)算，節(jié)省計(jì)算空間，以提升應(yīng)用體系的可靠性與穩(wěn)定性。

1 基于北斗的智能手機(jī)定位

目前，智能手機(jī)使用已基本普及，其功能也愈加完善。智能手機(jī)具有獨(dú)立的操作系統(tǒng)和開(kāi)放性的操作平臺(tái)，根據(jù)個(gè)人需要可安裝多個(gè)應(yīng)用程序?，F(xiàn)階段，在CPU的快速發(fā)展之下，智能手機(jī)具備更強(qiáng)的運(yùn)算能力，這為手機(jī)進(jìn)行大數(shù)據(jù)的運(yùn)算提供了堅(jiān)實(shí)的基礎(chǔ)。同時(shí)，智能手機(jī)通過(guò)移動(dòng)通信接入因特網(wǎng)，可實(shí)時(shí)與相關(guān)數(shù)據(jù)中心進(jìn)行數(shù)據(jù)交互，具備了在疫情防控系統(tǒng)中承擔(dān)客戶終端的能力。

絕大多數(shù)智能手機(jī)均能實(shí)現(xiàn)北斗實(shí)時(shí)米級(jí)定位。手機(jī)APP可通過(guò)函數(shù)實(shí)時(shí)讀取手機(jī)上北斗定位模塊測(cè)得的用戶坐標(biāo)，根據(jù)歷元間隔，逐歷元獲取用戶位置數(shù)據(jù)，進(jìn)而形成用戶軌跡數(shù)據(jù)[5]。

疾控部門鎖定涉疫者后，可將涉疫者的北斗定位軌跡數(shù)據(jù)發(fā)送給普通用戶。普通用戶可利用個(gè)人智能手機(jī)自行進(jìn)行時(shí)空伴隨程度計(jì)算，實(shí)時(shí)實(shí)現(xiàn)群防群控。

2 快速匹配方法

涉疫者一定時(shí)間段內(nèi)的生活軌跡數(shù)據(jù)量一般比較大，如果普通用戶在手機(jī)上逐歷元與其進(jìn)行比對(duì)，必然會(huì)大量占用手機(jī)的運(yùn)算資源。特別是在疫情爆發(fā)期，如果不避免大量冗余計(jì)算，可能會(huì)導(dǎo)致用戶手機(jī)運(yùn)行崩潰。通過(guò)剔除或跳過(guò)兩計(jì)算對(duì)象距離較遠(yuǎn)的歷元，可有效避免冗余計(jì)算，實(shí)現(xiàn)時(shí)空伴隨程度的快速判定。下面給出跳過(guò)距離較遠(yuǎn)歷元的具體判斷方法。

對(duì)于ti歷元，可得普通用戶與涉疫者的距離為

(1)

基于國(guó)內(nèi)的交通方式情況[6]，通過(guò)距離Di可以保守得到兩者實(shí)現(xiàn)近距離時(shí)空伴隨所需要的時(shí)間。當(dāng)Di>300 km時(shí)，兩者可能密接的最快速度是同時(shí)乘坐飛機(jī)前往同一個(gè)目的地?？紤]到飛機(jī)起降時(shí)間及飛機(jī)速度，可得所需的時(shí)間近似為：

(2)

式中，Tf為飛機(jī)起降時(shí)間；vf為飛機(jī)飛行速度，可取經(jīng)驗(yàn)值。當(dāng)Di≤300 km時(shí)，兩者可能密接的最快速度是同時(shí)乘坐高鐵前往同一個(gè)目的地。考慮到高鐵進(jìn)站時(shí)間及高鐵速度，可得所需的時(shí)間近似為：

(3)

式中，Tg為高鐵進(jìn)站所需時(shí)間；vg為高鐵運(yùn)行速度，可取經(jīng)驗(yàn)值。

得到ΔTi后，可計(jì)算跳過(guò)的歷元數(shù)：

(4)

從當(dāng)前歷元起，直接跳過(guò)n個(gè)歷元，得到下一個(gè)計(jì)算歷元：

ti+n=ti+n×Δt

(5)

從上述過(guò)程可見(jiàn)，當(dāng)兩對(duì)象距離較遠(yuǎn)時(shí)，可極大減少計(jì)算的歷元個(gè)數(shù)，從而大大減輕系統(tǒng)運(yùn)算負(fù)擔(dān)，提升高壓情況時(shí)的應(yīng)對(duì)能力及系統(tǒng)穩(wěn)定性。

3 算 例

為了進(jìn)一步展示該方法的使用過(guò)程及效果，下面給出一計(jì)算案例。

本算例研究對(duì)象為用戶A與涉疫B，其部分軌跡如表1所示，歷元間隔Δt為1 s。為檢驗(yàn)用戶A與涉疫B的時(shí)空伴隨性，現(xiàn)對(duì)二者14 d中部分軌跡信息進(jìn)行時(shí)空匹配，并驗(yàn)證本方法的快速匹配能力。

表1 用戶A與涉疫B部分軌跡數(shù)據(jù)

算例數(shù)據(jù)處理過(guò)程過(guò)程如下：

首先，在第一歷元t1時(shí)，由式(1)可得兩者距離：

(6)

此情況下，判斷二者近距離伴隨的最快方式為乘坐飛機(jī)。一般客機(jī)起飛要經(jīng)過(guò)兩個(gè)爬升階段才能進(jìn)入平飛，這個(gè)過(guò)程要20 min左右；為保證乘客安全，降落速度通常不超過(guò)36 km/h，從萬(wàn)米高空降落大概需要16 min[7-8],故綜合起飛與降落兩個(gè)過(guò)程，本文取Tf=36 min。民航飛行速度一般在500～900 km/h[8-9]，本文取vf=900 km/h。由式(2)可得

(7)

由式(4)可得跳過(guò)的歷元數(shù)n1=4 287。因此，從當(dāng)前歷元t1起，直接跳過(guò)4 287個(gè)歷元再進(jìn)行距離判斷。由式(5)可得下一個(gè)計(jì)算歷元t4288=13:11:27。進(jìn)入t4288歷元后，可得兩者距離

(8)

此時(shí)D4288<300 km，判斷二者近距離伴隨最快的方式為相向乘坐高鐵。高鐵進(jìn)站再啟動(dòng)所需時(shí)間通常為5 min左右[10],故本文取Tg=5 min，高速列車時(shí)速可達(dá)300 km[9],本文取vg=300 km/h，由式(3)計(jì)算得：

(9)

由式(4)可得跳過(guò)的歷元數(shù)n2=1 038，可得下一個(gè)計(jì)算歷元為t5626=13：28：45。

重復(fù)上述匹配過(guò)程，直至最后一個(gè)歷元。部分軌跡數(shù)據(jù)匹配結(jié)果如表2所示，在該時(shí)間段內(nèi)，計(jì)算歷元數(shù)僅占總歷元量的3.754%，說(shuō)明此方法可大大提高匹配速度，避免了冗余計(jì)算。

表2 部分軌跡數(shù)據(jù)匹配結(jié)果

4 結(jié) 語(yǔ)

本文針對(duì)判別時(shí)空伴隨性巨量計(jì)算導(dǎo)致系統(tǒng)荷載過(guò)大的問(wèn)題，提出了一種可跳躍無(wú)關(guān)歷元的時(shí)空數(shù)據(jù)快速匹配算法?；诒倍废到y(tǒng)獲取的時(shí)空數(shù)據(jù)，利用用戶與涉疫者之間的時(shí)空關(guān)系，按相遇條件越過(guò)伴隨可能性較低的無(wú)關(guān)歷元，得到下一次可能產(chǎn)生接觸的歷元，從而實(shí)現(xiàn)跳躍式快速匹配。通過(guò)算例展示了本文方法應(yīng)用過(guò)程，并進(jìn)一步驗(yàn)證了本方法可跳躍無(wú)效時(shí)間區(qū)間，減少運(yùn)算的冗余，實(shí)現(xiàn)快速匹配，減輕系統(tǒng)負(fù)擔(dān)的目的。