劉智奇 南 英 謝如恒
(1.南京航空航天大學(xué) 南京 211106)(2.空中交通管理系統(tǒng)與技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 南京 211106)
隨著現(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í)間。
地球剖分網(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)的研究。
第一步,全球空域網(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)緯及高度編碼示意圖
構(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)。
由于空域已經(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è)中省去不必要的遍歷步驟。
應(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ū)域。
通過(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í)。
傳統(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)。
基于剖分網(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è)。
將本文的檢測(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ò)程的影響。
本文基于地球剖分網(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)方法。