基于RGRS的空域劃設問題研究

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

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

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

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

1 弧度制全球網格

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

1.1 弧度制網格構建

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

1.1.1確定地圖基礎和坐標系

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

圖1 弧度制坐標系統

1.1.2確定劃分規則，進行全球劃分

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

圖2 RGRS剖分及編碼示意圖

1.1.3確定編碼規則，對網格進行編碼

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

1.2 網格信息素矩陣

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

表1 RGRS基礎網格層級及精度

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

(1)

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

2 弧度制網格空域劃設

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

2.1 空域劃設數學模型

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

MIN=VAR(Zi)

s.t.

(2)

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

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

2.2 改進區域生長算法

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

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

3)確定區域生長的終止原則。所有的網格都分配完畢。

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

步驟1根據劃設區域范圍，建立劃設區一級網格坐標系統；根據劃設精度，確定弧度網格最終等級Num；

步驟2統計當前等級網格系統中，每個網格的信息素，確定劃設分區數目及相應初始生長點；

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

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

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

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

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

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

圖3 改進生長算法流程

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

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

3 空域劃設仿真

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

表3 區域頂點坐標及所在網格編碼

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

根據作戰計劃，特別是航跡規劃信息，可以得到航跡點統計數據，由于保密原因，以隨即產生一組信息素矩陣A為條件進行仿真實驗，表4為一組隨機信息素矩陣A數據。

圖4 多邊形區域及柵格化

表4 信息素矩陣A13×13

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

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

圖5 一級網格尺度下空域分區劃設結果

圖6 邊緣平滑及最終分區

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

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

(3)

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

表5 邊緣網格數目計算

4 結論

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