基于剖分網(wǎng)格的空域沖突檢測方法*

劉智奇 南 英 謝如恒

（1.南京航空航天大學(xué) 南京 211106）（2.空中交通管理系統(tǒng)與技術(shù)國家重點實驗室 南京 211106）

1 引言

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

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

本文基于剖分網(wǎng)格對需要進行檢測的空域進行網(wǎng)格化表征，使用含有空域網(wǎng)格表征信息的多叉樹對不同使用計劃所涉及的空域進行沖突檢測。仿真結(jié)果表明，在求解大規(guī)?？沼蚴褂糜媱潧_突的問題上，本文提出的方法能提高較檢測效率、縮短計算時間。

2 幾何空域的網(wǎng)格剖分

2.1 網(wǎng)格表征方法及應(yīng)用現(xiàn)狀

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

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

2.2 空域網(wǎng)格剖分編碼方法

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

圖1 全球網(wǎng)格剖分示意圖（局部）

第二步，空域網(wǎng)格數(shù)字編碼。編碼由經(jīng)緯方向和高度方向編碼組成。經(jīng)緯方向采用雙位八進制編碼，同時按層級由低到高（網(wǎng)格尺寸由大到?。┣短拙幋a獲得第1～10層級編碼；高度方向則按高度由低到高進行編碼，但高度第1層不編碼，也采用八進制得到第2～10層級高度編碼；最后將經(jīng)緯投和高度編碼按對應(yīng)層級合形成空域網(wǎng)格的三維編碼。這一過程的前兩層編碼方法如圖2所示。

圖2 第一到第二層級網(wǎng)格經(jīng)緯及高度編碼示意圖

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

3.1 多叉樹的構(gòu)建

構(gòu)建空域網(wǎng)格編碼多叉樹的過程如下。

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

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

圖3 幾何空域的網(wǎng)格表征

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

3.2 多叉樹檢測原理

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

圖4 多叉樹沖突檢測原理

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

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

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

3.3 沖突檢測算法

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

圖5 沖突檢測方法流程圖

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

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

4 仿真分析

通過使用不同檢測方法，對同一區(qū)域內(nèi)總數(shù)不同的空域執(zhí)行沖突檢測仿真，分析在不同空域總數(shù)以及不同沖突空域數(shù)量條件下的算法檢測時長，驗證基于剖分網(wǎng)格的沖突檢測算法的計算效率。

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

4.1 傳統(tǒng)檢測算法

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

圖6 傳統(tǒng)沖突檢測方法輸出的沖突結(jié)果

表1 傳統(tǒng)方法空域沖突計算耗時

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

4.2 基于剖分網(wǎng)格的檢測算法

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

圖7 基于剖分網(wǎng)格檢測法輸出沖突結(jié)果

表2 基于剖分網(wǎng)格法對空域沖突的計算時長

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

4.3 算法效率對比

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

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

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

圖8 不同空域總數(shù)下兩種方法檢測時長結(jié)果

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

圖9 剖分網(wǎng)格檢測方法縮短計算時長情況

由上述仿真分析結(jié)果可知，本文提出的基于地球剖分網(wǎng)格的空域沖突檢測算法能夠有效檢測空間內(nèi)存在沖突的空域，并且該方法在計得到與傳統(tǒng)算法相同結(jié)果的情況下，能夠?qū)⒃瓉淼挠嬎銜r長縮短50%以上，大大提高了大規(guī)?？沼驔_突的檢測效率。這主要是因為在考察的區(qū)域已經(jīng)確定時，該區(qū)域?qū)?yīng)的網(wǎng)格剖分方法及其規(guī)模是確定的，因此新方法的多叉樹遍歷規(guī)模和上限就可以確定，且不隨區(qū)域內(nèi)總的檢測空域數(shù)增多而變化；但對傳統(tǒng)方法而言，由于判斷方法的根本是依據(jù)每一塊空域的幾何參數(shù)依次計算，因此實際運算量會隨區(qū)域內(nèi)總的檢測空域數(shù)增多而增大，綜前所述，新的判斷方法避免了空域數(shù)量規(guī)模對檢測過程的影響。

5 結(jié)語

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

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

2）利用傳統(tǒng)方法和本文提出的基于剖分網(wǎng)格的檢測方法對同樣的沖突產(chǎn)生區(qū)域進行檢測可以發(fā)現(xiàn)，本文提出的新方法相對于傳統(tǒng)檢測方法的計算時長可縮短50%以上。顯然，該方法在計算性能上優(yōu)于傳統(tǒng)方法。