基于剖分網格的空域沖突檢測方法*

劉智奇 南 英 謝如恒

（1.南京航空航天大學 南京 211106）（2.空中交通管理系統與技術國家重點實驗室 南京 211106）

1 引言

隨著現代空中交通運輸業的發展，空管系統面臨的壓力隨之增大。空域沖突檢測功能雖然在空管系統中發揮著重要作用，但其性能卻有待提升。

對于空域沖突檢測的研究開始于20世紀40年代～50年代，國內外學者提出了多種相關模型和算法，目前使用最廣泛的是幾何浮點計算，即通過每個空域使用計劃所確定空域的邊進行交叉判定[1～6]，該方法雖然可以準確計算得到空域沖突及其范圍，但對于大規模的沖突檢測存在著計算量大、算法復雜度高、計算時間長、求解效率低下等問題。

本文基于剖分網格對需要進行檢測的空域進行網格化表征，使用含有空域網格表征信息的多叉樹對不同使用計劃所涉及的空域進行沖突檢測。仿真結果表明，在求解大規模空域使用計劃沖突的問題上，本文提出的方法能提高較檢測效率、縮短計算時間。

2 幾何空域的網格剖分

2.1 網格表征方法及應用現狀

地球剖分網格（Earth Tessellation Grid，ETG）是一種可以無限細分，但又不改變形狀的地球擬合格網，當細分到一定程度時，可以達到模擬地球的目的，而其離散性、層次性和全球連續性特征，恰好符合計算機對數據離散化處理的要求[7-8]。軍用網格參考系統（Military Grid Reference System，MGRS）于20世紀40年代由美軍根據歐洲網格化地圖修改得到[9～10]，該系統可在經緯度坐標與網格坐標之間建立對應關系，簡化士兵之間的位置報告和協調；全球區域參考系統（Global Area Reference Systems，GARS）由美國地理空間情報局于2006年提出，其網格采用等經緯度網格剖分方法被劃分為不同大小的3個層級，主要用于聯合作戰中地理位置相關的表述[11～14]。

北京大學程承旗教授團隊提出的GeoSOT-3D地球剖分框架以其全球性、層次性、多尺度性等特性吸引了國內外學者的關注，該框架在空間對象表達上得到了應用[15]；空域網格模型也已經在某些空管領域得到了應用，如空域調度、流量管控、氣象影響預估、無人機編隊等研究領域[16～19]，但目前在空域沖突的檢測及確定方面還沒有相應的研究。

2.2 空域網格剖分編碼方法

第一步，全球空域網格化建模。利用正軸圓柱等距離投影，將地表空間投影到一矩形平面，投影后經緯線形成兩組相互垂直的平行直線。然后剖分空域，在經緯方向將平面逐級按照8*8規格的六十四等分進行剖分，形成各層級相互包容且無縫隙的經緯投影平面網格，最高剖分10個層級；同樣地，在高度方向按八等分逐級剖分，最高剖分9個層級，且高度方向第一層級高度上不剖分；最后將平面剖分和高度剖分的網格相組合形成網格化的空域結構，如圖1所示為一空域的剖分效果。

圖1 全球網格剖分示意圖（局部）

第二步，空域網格數字編碼。編碼由經緯方向和高度方向編碼組成。經緯方向采用雙位八進制編碼，同時按層級由低到高（網格尺寸由大到小）嵌套編碼獲得第1～10層級編碼；高度方向則按高度由低到高進行編碼，但高度第1層不編碼，也采用八進制得到第2～10層級高度編碼；最后將經緯投和高度編碼按對應層級合形成空域網格的三維編碼。這一過程的前兩層編碼方法如圖2所示。

圖2 第一到第二層級網格經緯及高度編碼示意圖

3 利用編碼多叉樹進行沖突檢測

3.1 多叉樹的構建

構建空域網格編碼多叉樹的過程如下。

第一步，根據空域下底面任意一點經緯高個坐標，計算與之存在交集的第1層級網格，并將該網格在經緯方向擴展，獲得全部與該空域下底面存在交集的第1層級網格，并生成這些第1層級網格的經緯編碼，然后以該空域ID或編碼為根節點、存在交集的第1層級經緯編碼為子節點構建空域網格表征多叉樹。

第二步，將第1層級網格向下一層級分解，獲取第2層級與空域底部存在交集的網格并生成第2層級經緯編碼，同時在高度方向擴展并生成第2層級高度編碼。依此逐層分解至目標層級（例如，目標層級經緯方向分解到第10層級，則高度網格也分解至第10層級）。最后將由低到高層級的經緯和高度編碼組合，形成各子節點并插入網格編碼多叉樹對應的節點。全部剖分過程及構造的的多叉樹結構如圖3所示。

圖3 幾何空域的網格表征

從圖中可以看出，第1層級由于不進行高度網格剖分，因此編碼中只含經緯網格編碼，第2層和更高層級網格編碼則由經緯和高度兩種編碼結合而成。第2層級第一個節點網格編碼中的xy2即表示經緯方向第2層級編碼，其后數字碼為經緯方向網格數字編碼；編碼z1表示高度方向第1層級編碼，其后數字碼為高度方向網格數字編碼。對于更高層級網格編碼則同理進行，同時相應編碼也按照規則寫入上述多叉樹更深層次的子結點中，最終可將空域完整表示為圖中結構。

3.2 多叉樹檢測原理

由于空域已經通過空間網格及其編碼構成的多叉樹進行表示，因此可將檢測原理表示在圖4中。不難看出這種檢測結構具有如下兩個特點。

圖4 多叉樹沖突檢測原理

1）實際的空域沖突區可以用多個空域中編碼相同的網格來表示，其顯然就是這些編碼所代表的空間網格集合；

2）雖然網格有層級和尺寸跨度的大小之分，但是對于存在沖突的空域而言，若某一層級的網格存在多空域共用現象，則包含該網格的低層級網格也一定存在多空域共用現象。

圖中多叉樹的根層級（矩形表示）代表一待檢測空域，空心節點表示該空域劃分的網格中所在層級存在與其他空域沖突的網格，實心節點則不與其他空域沖突，按照上述特點，則顯然實心節點下的深層節點中也一定存在實心節點。因此，從低層級向高層級遍歷，且遇到不存在沖突的網格（實心節點）則停止向高級遍歷，這樣即可在檢測中省去不必要的遍歷步驟。

3.3 沖突檢測算法

應用以上原理，將基于網格的空域沖突檢測算法流程列出如圖5所示，接下來對該過程進行詳細說明。

圖5 沖突檢測方法流程圖

一般空域沖突檢測需同時考慮時間和空間上的沖突，沖突檢測算法首先對待檢測的兩空域進行時間排斥檢測。顯然若在占用時間上無重疊，則兩空域即使存在空間交集也不存在沖突可能性，因此不發生空域沖突；再對兩空域進行空間排斥檢測，這需要對比兩空域的經緯高邊界，若這三個維度中存在不重疊的維度，則空域也不可能存在沖突區。

如果以上情況均未發生，則利用網格編碼多叉樹結構計算沖突空域。獲取兩待檢測空域的第1層級經緯編碼并求交集，然后在空域編碼多叉樹中分別獲取兩空域第1層級交集網格下的第2層級經緯編碼，計算下一層級交集網格經緯編碼并依此直至獲取最高層級的交集網格經緯編碼。以相同方法逐級求得各交集網格的高度編碼，并將交集網格經緯和高度編碼組合成網格編碼，則網格編碼所對應的網格集合就代表了空域的沖突區域。

4 仿真分析

通過使用不同檢測方法，對同一區域內總數不同的空域執行沖突檢測仿真，分析在不同空域總數以及不同沖突空域數量條件下的算法檢測時長，驗證基于剖分網格的沖突檢測算法的計算效率。

首先構建實驗條件與場景，建立一系列規模大且位置、形狀都具有隨機性的多邊形空域，顯然這些空域會存在沖突。以此為基礎多次生成隨機空域，其總數依次設定為100，150，200，……，500，每次分別使用傳統方法和本文方法進行沖突檢測、最后分析沖突檢測信息及每種方法的運行耗時。

4.1 傳統檢測算法

傳統空域沖突檢測算法輸出的沖突空域顯示如圖6所示，圖中對應總空域數量為100個，同時將空域沖突信息輸出在圖中重疊區域。表1給出了傳統算法仿真得出的沖突檢測信息和計算時間。

圖6 傳統沖突檢測方法輸出的沖突結果

表1 傳統方法空域沖突計算耗時

由表1可知，隨著需要分析的空域總數增加，與之相對應的可能存在沖突的空域數量就會增多，而沖突檢測算法運行所需要的時間也就會不斷增長。

4.2 基于剖分網格的檢測算法

基于剖分網格的空域沖突檢測算法輸出的沖突空域如圖7所示，圖中對應總空域數量為100個，該算法輸出的檢測信息和計算時間如表2所示。

圖7 基于剖分網格檢測法輸出沖突結果

表2 基于剖分網格法對空域沖突的計算時長

由圖6和圖7對比可知，基于剖分網格的沖突檢測算法與傳統算法對相同的空域沖突情況檢測結果一致，因此本文方法能夠同樣有效地進行空域沖突檢測。

4.3 算法效率對比

將本文的檢測方法耗時數據與傳統方法進行對比，可以得到本文方法相對于傳統沖突檢測算法計算消耗時間的縮短比例，如表3所示。

表3 不同方法沖突計算耗時對比結果

圖8所示為傳統的空域沖突檢測算法和本文算法的檢測時間變化情況。從圖中可以看出，隨著每次實驗需要檢測的空域數量增加，兩種方法計算所需時間都有所增加，但本文算法耗時明顯少于傳統算法，且其隨空域總數增長而產生的計算時長的增速也明顯小于傳統的空域沖突檢測算法。

圖8 不同空域總數下兩種方法檢測時長結果

圖9所示為本文算法相對于傳統沖突檢測算法計算時長節省比例隨空域總數變化的特性圖，從圖中可以看到，盡管每次實驗中需要檢測的空域數在不斷增加，但是本文方法的計算時長相對傳統方法的節省比例一直能夠保持在不低于50%的水平。也就是說，基于剖分網格的沖突檢測法效率要明顯高于傳統檢測算法。

圖9 剖分網格檢測方法縮短計算時長情況

由上述仿真分析結果可知，本文提出的基于地球剖分網格的空域沖突檢測算法能夠有效檢測空間內存在沖突的空域，并且該方法在計得到與傳統算法相同結果的情況下，能夠將原來的計算時長縮短50%以上，大大提高了大規模空域沖突的檢測效率。這主要是因為在考察的區域已經確定時，該區域對應的網格剖分方法及其規模是確定的，因此新方法的多叉樹遍歷規模和上限就可以確定，且不隨區域內總的檢測空域數增多而變化；但對傳統方法而言，由于判斷方法的根本是依據每一塊空域的幾何參數依次計算，因此實際運算量會隨區域內總的檢測空域數增多而增大，綜前所述，新的判斷方法避免了空域數量規模對檢測過程的影響。

5 結語

本文基于地球剖分網格模型對待檢區域的沖突空域進行描述并利用多叉樹結構計算沖突空域。由此構建的新的空域沖突檢測方法與傳統的空域檢測方法同時進行試驗，得到兩種方法對于空域沖突檢測的計算時間。根據實驗結果分析得到如下結論。

1）對于相同數量的若干空域進行沖突檢測，基于剖分網格的沖突檢測方法可以得到和傳統的幾何浮點計算方法一樣的空域沖突檢測結果。

2）利用傳統方法和本文提出的基于剖分網格的檢測方法對同樣的沖突產生區域進行檢測可以發現，本文提出的新方法相對于傳統檢測方法的計算時長可縮短50%以上。顯然，該方法在計算性能上優于傳統方法。