劉智奇 南 英 謝如恒

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

3 利用編碼多叉樹(shù)進(jìn)行沖突檢測(cè)

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

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

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

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

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

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

3.2 多叉樹(shù)檢測(cè)原理

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

圖4 多叉樹(shù)沖突檢測(cè)原理

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

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

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

3.3 沖突檢測(cè)算法

應(yīng)用以上原理，將基于網(wǎng)格的空域沖突檢測(cè)算法流程列出如圖5所示，接下來(lái)對(duì)該過(guò)程進(jìn)行詳細(xì)說(shuō)明。

圖5 沖突檢測(cè)方法流程圖

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

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

4 仿真分析

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

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

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

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

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

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

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

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

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

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

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

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

4.3 算法效率對(duì)比

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

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

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

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

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

圖9 剖分網(wǎng)格檢測(cè)方法縮短計(jì)算時(shí)長(zhǎng)情況

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

5 結(jié)語(yǔ)

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

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

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