周 騰 李曉妍

（1.中國科學(xué)院合肥物質(zhì)科學(xué)研究院 合肥 230031）（2.中國科學(xué)技術(shù)大學(xué) 合肥 230026）（3.江蘇海事職業(yè)技術(shù)學(xué)院 南京 210000）

1 引言

隨著移動終端的飛速發(fā)展，GPS 技術(shù)的不斷進步，智能手機已成為一種非常普遍的設(shè)備［1］，廣泛應(yīng)用于通信設(shè)備看護和通信線路巡檢中。在電信綜合代維管理系統(tǒng)中，這些智能設(shè)備能夠采集代維巡檢人員移動線路的GPS軌跡的經(jīng)緯度信息，并通過4G 移動網(wǎng)絡(luò)傳輸?shù)胶蠖朔?wù)器中，系統(tǒng)會自動與預(yù)先設(shè)定的巡檢范圍進行適配，通過加強對代維巡檢人員的管控力，提高巡檢質(zhì)量。同時，移動設(shè)備所采集到的GPS 經(jīng)緯度信息也呈現(xiàn)出一種爆炸性的增長趨勢［2］，大量的數(shù)據(jù)不僅極大地影響了系統(tǒng)的存儲效率，占用了較多的運算資源，也影響了前端的瀏覽體驗。因此，研究如何將GPS經(jīng)緯度信息進行壓縮存儲勢在必行，既從算法方面進行改進，一方面要能夠在軌跡保存完整的情況下，簡化軌跡數(shù)據(jù)，以提高存儲資源的利用效率；另一方面要通過壓縮數(shù)據(jù)，減輕運算復(fù)雜度，提高讀取效率，以改善前端展示時的用戶體驗。

2 GPS軌跡壓縮算法——道格拉斯-普克算法

軌跡數(shù)據(jù)壓縮算法一般分為兩類［7］，一是將運動軌跡進行分段線性化［3］，由于其算法形式簡單，計算復(fù)雜度低，是目前最為常用的算法；二是非線性的軌跡擬合［4］，如Bezier曲線，非線性擬合更接近真實軌跡，但是其算法復(fù)雜，計算量大。由于電信代維巡檢中的人員軌跡是沿電信線路或者巡檢道路而記錄的，所以使用線性壓縮算法更能夠貼合現(xiàn)實中的情況，而且也能夠節(jié)約一部分運算資源。在眾多線性壓縮算法中，道格拉斯-普克算法最具有代表性。

道格拉斯-普克算法（Douglas-Peucker Algorithm）［5］簡稱DP 算法，在1973 年由Douglas 和Peucker提出。該算法步驟如下：

1）在軌跡曲線首尾兩點A、B 之間連接一條直線AB，該直線為曲線的弦；遍歷曲線上其他所有點，求每個點到直線AB的距離，找到最大距離的點C，最大距離記為dmax；

2）比較該距離dmax與預(yù)先定義的閾值Dmax大小，如果dmax＜Dmax，則將該直線AB 作為曲線段的近似，曲線段處理完畢。

3）若dmax＞Dmax，則使C 點將曲線AB 分為AC和CB兩段，并分別對這兩段進行1）、2）步處理。

4）當(dāng)所有曲線都處理完畢時，依次連接各個分割點形成的折線，即為原始曲線的路徑。

該算法結(jié)構(gòu)簡單，效率相對較高［6］。但它是一種需要明確起點和終點的后壓縮方法，是一種離線壓縮方法。而在電信代維系統(tǒng)中，數(shù)據(jù)需要實時進行處理，DP 算法在代維系統(tǒng)這種場景中并不能有效適用。因此，需要對該算法進行改進，使其能夠?qū)@些數(shù)據(jù)進行實時壓縮處理。

3 改進的道格拉斯-普克算法

3.1 軌跡采集方式改進思路

DP 算法是一種離線后壓縮算法，需要明確知道曲線的起點和終點，而代維系統(tǒng)中的GPS軌跡記錄是實時傳輸數(shù)據(jù)，需要一種在線實時的壓縮算法，因此，需要在DP算法的基礎(chǔ)上進行改進。

由于代維系統(tǒng)中線路巡檢的軌跡是有折返的，實時數(shù)據(jù)量龐大，因此算法改進時需要考慮以下三個問題。

其一，相同經(jīng)緯度的記錄點冗余問題。當(dāng)巡檢遇到設(shè)備檢查點時，巡檢人員會在此處停留，軌跡偏移量便會大大減少，甚至?xí)霈F(xiàn)多次上報的數(shù)據(jù)經(jīng)緯度值相同的情況，造成大量數(shù)據(jù)冗余。這部分數(shù)據(jù)若是運算后再進行剔除，會加大計算資源的耗損［7］，因此應(yīng)在運算前進行預(yù)處理比較篩選，減少計算量。

其二，計算模型問題。地理空間距離的計算中含有大量的三角函數(shù)運算［8］，對計算資源的消耗較大。一般來說，地球上兩點之間的距離計算有以下兩種模型［9］：一是球面模型。這種模型將地球看成一個標準球體，球面上兩點之間的最短距離即為圓弧長，這種方法使用較廣，邏輯相對簡單，消耗的CPU 計算資源較少。二是橢球模型［9］。這種模型最貼近真實地球，精度較高，但計算較為復(fù)雜，需要耗費更多的CPU 運算資源［10］。根據(jù)電信巡檢業(yè)務(wù)需求特點，對GPS 軌跡精度并無高精度要求，因此應(yīng)采用球面模型來計算地理空間距離以減少運算資源的消耗。

其三，共線軌跡點記錄存留問題。因軌跡是有折返的［11］，即出現(xiàn)三個GPS軌跡點在同一條直線上的情況，則需要對三點共線的情況進行討論，如果巡檢方向一致，應(yīng)該舍棄位于中間的點；如果巡檢線路出現(xiàn)折返，則必須全部保留。這樣既能保證軌跡完整性，又能夠有效減少數(shù)據(jù)冗余。

因此，改進的DP算法步驟如下：

1）將GPS 軌跡記錄上的某一點記為第一點A，與相鄰的下一個記錄點進行比較，若兩點經(jīng)緯度數(shù)據(jù)完全一致，則刪除下一點的記錄，再將A 與下一個記錄進行比較，依次篩選，排除經(jīng)緯度數(shù)據(jù)完全相同的冗余點，直至記錄點與A 經(jīng)緯度數(shù)據(jù)不同，記為點B。

2）按照步驟1 的方法，找到與點B 經(jīng)緯度數(shù)據(jù)不同的記錄點C。

3）在AB 之間連接一條直線，計算點C 到直線AB的歐式距離d。

4）若距離d=0，則A、B、C 三點共線。根據(jù)經(jīng)緯度信息，判斷C 點是否位于A、B 兩點之間，若是，則保留C點數(shù)據(jù)；若否，則刪除B點數(shù)據(jù)。

若距離d 小于閾值，則刪除C 點數(shù)據(jù)。重復(fù)步驟2），尋找下一C點。

若距離d 大于閾值，則保留C 點數(shù)據(jù)。將記錄點B作為第一點，重復(fù)步驟1）、2）、3）、4），直至工單記錄結(jié)束。

3.2 GPS軌跡兩點間距離的計算優(yōu)化

在軌跡記錄距離計算時，有大量的三角函數(shù)計算，占用了較多計算資源，影響系統(tǒng)運行速度，因此對此進行計算優(yōu)化。

根據(jù)球面計算模型，在GPS軌跡上有任意兩點A、B，設(shè)φ1、φ2為AB兩點的緯度，ω1、ω2為兩點的經(jīng)度，R為地球球面模型的半徑，Δω、Δφ分別為AB兩點的經(jīng)、緯度差，這兩點的圓心角σ 可通過球面余弦定理［12］得出：

根據(jù)弧長公式可得A、B 間的球面距離：d=Rσ 。如果A、B 之間距離很短，即d 相對于R 很短時［13］，A、B 間的圓心角很小，cos Δω余弦函數(shù)無限趨近于1［9］，那么上述的反余弦函數(shù)就會出現(xiàn)較大的舍入誤差。為避免這種情況的出現(xiàn)，利用正弦函數(shù)的haversine 公式來進行公式變形計算地球表面距離。這樣即便距離很近值很小，也能保持足夠的有效數(shù)字。

在實際應(yīng)用中，GPS 軌跡記錄采集的密度較高（30s/次），而代維巡檢人員的行走速度不會超過20km/h，因此，可以認為經(jīng)緯度偏移值較小即

3.3 偏移值d的計算

根據(jù)上述內(nèi)容，GPS 軌跡記錄會出現(xiàn)記錄點共線的情況，要對此進行判斷。因此，需要分別計算AB、AC、BC 的距離。為避免三角函數(shù)運算，本研究采用海倫公式［14］，根據(jù)三點構(gòu)成的三角形來計算歐式距離d。設(shè)S 為三角形ABC 的面積，AB 為底，d 則為三角形的高。根據(jù)三角形面積公式，可知：d=海倫公式如下所示：

其中，a=AB，b=BC，c=AC，p 為三角形的周長的即

因此：

4 算法實驗與仿真

本研究對改進后的算法進行數(shù)據(jù)檢驗。從數(shù)據(jù)庫中隨機抽取了30s采集一次的500條線路巡檢工單，共計25231 條記錄作為測試數(shù)據(jù)，利用面向?qū)ο蟮膒ython語言對算法進行編程。

4.1 壓縮比測試

對上述工單進行壓縮處理。選取4 個閾值進行比較。壓縮比如圖1所示。

圖1 不同閾值下的壓縮比

可見，運用改進的DP 算法，在閾值為20m 時，壓縮比取得了非常良好的壓縮效果，壓縮比達到5.31，若實際應(yīng)用到系統(tǒng)中，將大大減少工單記錄數(shù)據(jù)量，減輕存儲壓力［15］，提高存儲讀取效率。

4.2 壓縮軌跡展示示例

選取一條有85 條記錄的工單，并采用5m、10m、15m、20m 四種閾值進行壓縮處理，處理后軌跡如圖2～6所示。

圖2 原始軌跡記錄（30s/次采集）

圖3 采用5m閾值處理的軌跡

圖4 采用10m閾值處理的軌跡

圖5 采用15m閾值處理的軌跡

圖6 采用20m閾值進行處理

可見，在不同的閾值下，線段的基本都能夠清晰保存GPS 軌跡記錄，且隨著閾值的擴大，線段化的明顯越來越明顯。仿真實驗證明能夠滿足線路巡檢業(yè)務(wù)的需要。

5 系統(tǒng)應(yīng)用

經(jīng)過仿真實驗結(jié)果和業(yè)務(wù)中精度的需求的綜合考慮，在江蘇移動綜合代維系統(tǒng)中進行實地應(yīng)用。運用改進的DP算法，采用10m作為閾值，對工單進行處理。首先對2018年8月的數(shù)據(jù)進行處理，并與原數(shù)據(jù)進行離線后比較。經(jīng)比對，8 月GPS 軌跡記錄數(shù)據(jù)量可減少70%，前臺加載渲染速度提高近50%，達到了較為預(yù)期滿意的效果。此后，又將此算法應(yīng)用到2018 年9 月數(shù)據(jù)的實時處理中。同比數(shù)據(jù)量下降77%左右得到的相對滿意的效果。

6 結(jié)語

本研究采用了改進后的DP 算法，對GPS 軌跡記錄進行壓縮，使其適應(yīng)電信業(yè)務(wù)中的實時壓縮要求，并進一步討論了節(jié)約運算資源并提高運算速度的方法。經(jīng)過實驗測試，證明該算法能夠在提高壓縮比的情況下，滿足軌跡展現(xiàn)管理的要求。通過這一算法，能夠顯著減輕服務(wù)器的存儲和渲染負擔(dān)［16］，進一步提升了用戶體驗。本研究對電信人員巡檢軌跡和看護軌跡的壓縮和存儲方面有一定的參考價值。