文 秘，方 強，黃興龍，張一鳴

(1.空軍指揮學院 研究生大隊，北京 100097；2.中國人民解放軍66133部隊，北京 100097)

空域劃設問題直接關系到空域使用效率和安全，從而影響作戰(zhàn)效能和經(jīng)濟效益，不論在軍航還是民航都是研究的熱點。目前，空域劃設主要有兩種思路[1]：一是從上向下劃設，以基于最優(yōu)化理論的“排樣”法為典型代表。該算法將空域劃設問題抽象為一個多維“下料”問題，結合最優(yōu)化算法，得到空域劃設方案。二是從下向上劃設，以網(wǎng)格“生長”算法[2-3]最為突出。該算法是在空域離散化的基礎上，從初始生長點，按照一定的信息素條件進行臨近生長，直至實現(xiàn)空域的完全劃分。兩種思路各有其特點。近年來，網(wǎng)格“生長”算法由于更貼近劃設實際、算法過程明晰等特點，得到了更廣泛應用和研究。

一般的“生長”算法[4-5]，網(wǎng)格選擇任意,缺乏實際意義，不能與地圖相匹配，信息素收集困難；且生長網(wǎng)格沒有嵌套效應，需專門設計邊緣平滑算法?；《戎迫蚓W(wǎng)格系統(tǒng)，用等弧度劃分替代等角度劃分，用十進制代替六十進制，采用單一尺度均勻劃設而非多尺度劃設，形成了以網(wǎng)格為單元的全新地理空間計算和管理框架，極大地簡化了空間計算。基于弧度制網(wǎng)格剖分的改進“生長”算法，信息素收集方便，使用算法嵌套平滑邊緣，能極大提升空域劃設效率。

1 弧度制全球網(wǎng)格

全球網(wǎng)格參考網(wǎng)格系統(tǒng)是一種科學的、簡明的、全球統(tǒng)一的剛性定位網(wǎng)格參照系統(tǒng)，比較常見的是MGRS和GARS[6-7]。MGRS與GARS網(wǎng)格系統(tǒng)，在目標定位和區(qū)域協(xié)同方面各有其優(yōu)勢，但存在共同缺陷：① 采用角度制，計算復雜。角度制是一種六十進制的計數(shù)方法，與日常生活的十進制區(qū)別較大，帶來計算和認知麻煩；② 劃分具有多尺度效應。兩種網(wǎng)格都是等度、等分、等秒劃設，但間隔尺度不一。如在GARS中，劃分為30′、15′和5′的3個層級[8-10]，實現(xiàn)網(wǎng)格向下 “四等分”和“九等分”，這種尺度差異給跨網(wǎng)格(空域)組合和拆分帶來極大的困難?；《戎凭W(wǎng)格參考系統(tǒng)，采用弧度制和“百等分”方法，將角度和距離統(tǒng)一起來，并實現(xiàn)十進制計算，克服了MGRS與GARS網(wǎng)格系統(tǒng)的不足。

1.1 弧度制網(wǎng)格構建

弧度制網(wǎng)格系統(tǒng)，按照“確定地圖基礎和坐標系——確定劃分規(guī)則，進行全球劃分——確定編碼規(guī)則，對剖分進行編碼”的步驟進行網(wǎng)格系統(tǒng)構建[11，12]。

1.1.1確定地圖基礎和坐標系

以經(jīng)緯度坐標體系為依據(jù)，采用圓柱投影中的橫軸墨卡托投影，按照西經(jīng)180°經(jīng)線展開形成平面地圖為劃分基礎，它的坐標范圍為：西經(jīng)180°至東經(jīng)180°；南緯90°至北緯90°，將其轉換為弧度制為：經(jīng)線(-π,π)；緯線(-π/2,π/2)。若以180°W90°N(南極點)為原點，180°W經(jīng)線方向為y軸，垂直于180°W經(jīng)線方向為x軸，建立平面直角坐標系，則相應的坐標范圍變?yōu)椋簒軸方向(0,2π)；y軸方向為(0,π)，如圖1所示。由于π值近似等于3.14，因此坐標范圍又可描述為：x軸方向(0,6.29)；y軸方向為(0,3.15)。

圖1 弧度制坐標系統(tǒng)

1.1.2確定劃分規(guī)則，進行全球劃分

弧度制網(wǎng)格剖分，以原點為起點，向東和向北，按照0.01 rad×0.01 rad進行劃分，形成628×314個一級網(wǎng)格，網(wǎng)格大小為64 km×64 km。依次對上一級網(wǎng)格進行10×10等分，形成第二、三、四、五、六級網(wǎng)格(見圖2)，后一級網(wǎng)格尺寸是上一級尺寸的1/10，面積為1/100，維持十進制關系?；《戎颇苁菇堑募吓c實數(shù)集合R存在一一對應關系，一個完整的圓的弧度是2π，即2π rad=360°，因此1 rad=57.3°?；《戎撇粌H能將角度和距離度量統(tǒng)一到十進制，而且能夠極大的簡化弧長(距離)的計算：L=α(弧度)×R(半徑)。

圖2 RGRS剖分及編碼示意圖

1.1.3確定編碼規(guī)則，對網(wǎng)格進行編碼

按照弧度制網(wǎng)格剖分規(guī)則，全球可劃設628×314個一級網(wǎng)格。一級網(wǎng)格編碼按照“序號不足三位補足三位數(shù)”的編碼規(guī)則，構成XXX-YYY的結構，則網(wǎng)格坐標軸范圍為：緯線方向000～628；經(jīng)線方向000～314。如圖2中陰影部分的一級網(wǎng)格的編碼為“627-309”，二級至六級編碼，按照“10×10”坐標點的方式進行“分層—交叉”編碼，圖2中的二級編碼為“2-3”，三級編碼為“8-6”，則一個完整的精確到三級網(wǎng)格的編碼為“627-309-2-3-8-6”，亦可簡寫為“627-309-23-86”。

1.2 網(wǎng)格信息素矩陣

地球是一個橢球體，兩極稍扁，赤道略鼓，半徑長度均值約為6 400 km，由此可得弧度制全球網(wǎng)格系統(tǒng)基礎網(wǎng)格層級及精度，見表1。一個完整的網(wǎng)格編碼長度等于“4+2×級數(shù)”，第六級網(wǎng)格的完整編碼有16位，通常劃分到三級(10位)，區(qū)域精度為“640 m×640 m”，已經(jīng)能夠滿足絕大多數(shù)區(qū)域定位和協(xié)調需求。

表1 RGRS基礎網(wǎng)格層級及精度

以不同精度的弧度網(wǎng)格作為存儲空間數(shù)據(jù)的“抽屜”，把多源異構數(shù)據(jù)規(guī)則地放置到“抽屜”中，不同數(shù)據(jù)之間通過網(wǎng)格編碼有機地關聯(lián)在一起，由此可實現(xiàn)多源異構數(shù)據(jù)在空間特征上的關聯(lián)整合，這些“抽屜”和信息數(shù)據(jù)共同構成了網(wǎng)格信息素矩陣。在圖2中，弧度制全球網(wǎng)格參考系統(tǒng)的一級網(wǎng)格，構成了一個628×314的信息素矩陣A；二級網(wǎng)格構成了一個6 280×3 140的信息素矩陣B；三級網(wǎng)格構成了一個62 800×31 400的信息素矩陣C。

(1)

式(1)中：?i∈[1,618];?j∈[1,314]; ?k,l∈[1,10]；sum+(·)算子表示信息素矩陣所有元素值求和。利用多顆粒度的信息素矩陣，能夠實現(xiàn)區(qū)域定位和數(shù)據(jù)的存儲計算。

2 弧度制網(wǎng)格空域劃設

區(qū)域生長算法[2-3]，是一種經(jīng)典的基于區(qū)域的圖像分割方法，是一種根據(jù)事前定義的準則將像素或子區(qū)域聚合成更大區(qū)域的過程，其實質就是按照一定的規(guī)則(如性質相似)把像素連通起來，從而最終構成分割區(qū)域。本文中將區(qū)域生長算法應用到空域劃設，將弧度網(wǎng)格單元統(tǒng)計數(shù)據(jù)(信息素)作為“像素值”。

2.1 空域劃設數(shù)學模型

空域生長算法是從初始點網(wǎng)格出發(fā)，向四周不斷的生長合并其他網(wǎng)格，最終實現(xiàn)對區(qū)域網(wǎng)格的完全劃分。劃分的過程中始終堅持各劃分區(qū)域之間信息素均衡。由此可得，基于弧度網(wǎng)格的空域劃設數(shù)學模型為：

MIN=VAR(Zi)

s.t.

(2)

式(2)中：i表示優(yōu)化劃分的第i個區(qū)域；j表示空域內第j個網(wǎng)格單元；n表示空域內的所有網(wǎng)格單元個數(shù)；m表示區(qū)域劃分總數(shù)；Ni表示與網(wǎng)格單元j相鄰的網(wǎng)格單元集合；xij∈{0,1}表示網(wǎng)格單元j是否屬于區(qū)域i；yi∈{0,1}表示存在第i區(qū)域輸出時為1，否則為0；Zi表示第i個劃分區(qū)總信息素。

目標函數(shù)表示各劃分區(qū)塊信息素應當均勻；約束條件1確保了每個空域網(wǎng)格單元只能歸屬于一個分區(qū)，即反映了分區(qū)不能交叉重疊，也不能留有空隙的約束；約束條件2確保所劃分的分區(qū)大小和形狀合理；約束條件3確保扇區(qū)內所有網(wǎng)格單元是相連的，滿足了分區(qū)連續(xù)性約束；約束條件4保證所有網(wǎng)格單元被劃分出去，不會有剩余網(wǎng)格存在。

2.2 改進區(qū)域生長算法

區(qū)域生長算法是建立在區(qū)域網(wǎng)格化的基礎之上，有三個關鍵步驟[4-5]：

1)種子點的選取。選擇一組能正確反映所需區(qū)域特征的點。一是種子點的數(shù)目m，即空域劃設的數(shù)目；二是種子點的位置，該問題可選擇航跡點密度最大的前m個網(wǎng)格作為種子點或者隨機選擇。

3)確定區(qū)域生長的終止原則。所有的網(wǎng)格都分配完畢。

以基于航跡點密度的空域分割為例，改進生長算法的具體步驟為：

步驟1根據(jù)劃設區(qū)域范圍，建立劃設區(qū)一級網(wǎng)格坐標系統(tǒng)；根據(jù)劃設精度，確定弧度網(wǎng)格最終等級Num；

步驟2統(tǒng)計當前等級網(wǎng)格系統(tǒng)中，每個網(wǎng)格的信息素，確定劃設分區(qū)數(shù)目及相應初始生長點；

步驟3從每個初始點所在單元網(wǎng)格出發(fā)，搜索相鄰單元網(wǎng)格中信息素最小的網(wǎng)格，并將其信息素與相應生長點的信息素相加，形成待生長區(qū)；

步驟4比較各待生長區(qū)總信息素，找到其中信息素最小的待生長區(qū)，合并其網(wǎng)格及信息素，作為下一輪生長的初始生長點，釋放其余待生長區(qū)；

步驟5重復步驟3、步驟4，直至找不到還未分配網(wǎng)格，完成該級網(wǎng)格劃分；

步驟6判斷網(wǎng)格等級是否達到Num；若沒有達到網(wǎng)格等級要求，則根據(jù)該級網(wǎng)格劃分確定的劃分邊界，依次對每一個邊界網(wǎng)格10×10剖分，形成下一級網(wǎng)格坐標系統(tǒng)，選出該系統(tǒng)中最靠近相應分區(qū)的點作為新的生長點，轉到步驟2；若達到網(wǎng)格等級要求，轉到步驟7。

步驟7對網(wǎng)格邊沿進行平滑，完成空域劃設。

假設任意網(wǎng)格單元為Bij，共N個；分為M個區(qū)塊；每個區(qū)塊的種子單元為Zijk,k∈[1,M]；第k個區(qū)塊集合為Qk，顯然Zijk?Qk；第k個區(qū)塊的臨近區(qū)塊集合為Lk={與k區(qū)塊相鄰且未分配的Bij}，Bijk表示集合Lk中信息素最小的網(wǎng)格，則一個層級網(wǎng)格的算法流程如圖3所示。

圖3 改進生長算法流程

由算法步驟和流程圖，得到改進生長算法與原生長算法[2-3]，見表2。

表2 改進生長算法與原算法

3 空域劃設仿真

以某地區(qū)空戰(zhàn)場管制空域劃設為例，該空戰(zhàn)場覆蓋的區(qū)域是一個由A1～A5(順時針)五個頂點構成的多邊形區(qū)域，各頂點的經(jīng)緯度坐標已知，則按照弧度制網(wǎng)格編碼規(guī)則能夠計算出對應的網(wǎng)格編碼，見表3。

表3 區(qū)域頂點坐標及所在網(wǎng)格編碼

按照弧度制剖分規(guī)則，進一步將待劃設的對多邊形區(qū)域進行柵格化，形成13×13個一級網(wǎng)格組成的柵格化區(qū)域，精確度為64 km×64 km，如圖4所示。

根據(jù)作戰(zhàn)計劃，特別是航跡規(guī)劃信息，可以得到航跡點統(tǒng)計數(shù)據(jù)，由于保密原因，以隨即產(chǎn)生一組信息素矩陣A為條件進行仿真實驗，表4為一組隨機信息素矩陣A數(shù)據(jù)。

圖4 多邊形區(qū)域及柵格化

表4 信息素矩陣A13×13

隨機選擇A(3,4)(對應弧度網(wǎng)格519-213)、A(6,11)(對應弧度網(wǎng)格526-210)、A(8,9)(對應弧度網(wǎng)格524-208)三個點，作為初始生長點(表3中被框選的位置)，按照2.2節(jié)的改進生長算法進行空域分割。

經(jīng)過一次空域生長，得到了一個大體的分區(qū)劃設結果，如圖5所示。顯然，該結果并不能滿足分區(qū)空域滿足凸約束的條件，因此需要對其邊緣進行調整。將三部分空域區(qū)塊的邊緣部分網(wǎng)格進行向下一級剖分，每個網(wǎng)格重新形成10×10個二級網(wǎng)格，精確度為6.4 km×6.4 km，然后按照2.2節(jié)的改進生長算法對每個邊緣網(wǎng)格再進行一次空域分割，并進行邊緣平滑，得到最終的分區(qū)劃設結果，如圖6所示。

圖5 一級網(wǎng)格尺度下空域分區(qū)劃設結果

圖6 邊緣平滑及最終分區(qū)

由生長算法的流程可以看出，算法復雜度和對于系統(tǒng)資源的消耗主要集中在本文2.2節(jié)步驟3(改進算法與原算法共有)：搜索生長區(qū)邊界最小信息素單元網(wǎng)格。以按照四個方向生長為例，可以歸納統(tǒng)計出邊界單元網(wǎng)格數(shù)目n邊與區(qū)域內部網(wǎng)格數(shù)目n內的關系，如表5所示。

由表5可以得到：n邊≥2n內，當n內較大時n邊≈2n內。從初始生長點生長到n內網(wǎng)格點的區(qū)域的過程中，需要進行的邊緣搜索的總次數(shù)為：S=n內(n內+1)。若待生長區(qū)域總網(wǎng)格數(shù)為n，區(qū)域劃分塊數(shù)為N，每個區(qū)塊所包含的網(wǎng)格數(shù)為n/N，則區(qū)域劃設總邊緣搜索總次數(shù)為：n2/N+n，對于一個固定的問題N為定值，則該算法的復雜度由n2/N決定。因此，對于本文空域劃設問題，提升效率的計算方法如下：

(3)

式(3)中：ρ表示提升的劃設效率；λ內表示多邊形內網(wǎng)格數(shù)量；λ邊表示多邊形內部各分區(qū)之間的邊界所包含的網(wǎng)格數(shù)量；乘數(shù)100表示將當前網(wǎng)格劃分為100個次一級網(wǎng)格。在該問題中劃設效率大概提升了90.4%，效果明顯。

表5 邊緣網(wǎng)格數(shù)目計算

4 結論

本文提出了基于弧度制的全球網(wǎng)格系統(tǒng)，并將其應用于空戰(zhàn)場管制空域劃設。利用弧度制網(wǎng)格參考系統(tǒng)的全球剖分、十進制和多顆粒度特性，對空域劃設生長算法進行了改進。仿真實驗表明，該方法信息素收集方便，嵌套平滑邊緣，能夠極大的提升空域劃設的效率。