劉宏波，高俊，古尚利

（1.海軍工程大學電子工程學院，武漢430033；2.中國船舶重工集團公司第七○九研究所，武漢430205）

基于柵格化空域的數(shù)據(jù)鏈站點選址優(yōu)化*

劉宏波1，高俊1，古尚利2

（1.海軍工程大學電子工程學院，武漢430033；2.中國船舶重工集團公司第七○九研究所，武漢430205）

針對對空數(shù)據(jù)鏈站點選址優(yōu)化實際問題，引入柵格化分析方法進行數(shù)據(jù)鏈站點的精細化規(guī)劃和優(yōu)化，綜合考慮站點保障能力、飛行航線、站點建設費用等能力因素，通過柵格化分析方法進行數(shù)學建模，將數(shù)據(jù)鏈站點選址優(yōu)化問題轉換為0-1整數(shù)規(guī)劃問題，通過案例想定，利用優(yōu)化軟件LINGO進行模型求解，給出了一種柵格化空域的數(shù)據(jù)鏈站點優(yōu)化選址的方法。

柵格法，數(shù)據(jù)鏈，LINGO，優(yōu)化，0-1整數(shù)規(guī)劃

1 概述

目前在對空數(shù)據(jù)鏈站點規(guī)劃建設方面，缺乏對飛機作戰(zhàn)任務區(qū)域，飛行航線等作戰(zhàn)需求的考慮，致使現(xiàn)有站點的分布位置無法滿足飛機在任務區(qū)域的通信保障需求。同時，隨著復雜國際形勢的變化，將呈現(xiàn)出空中作戰(zhàn)力量越來越多，作戰(zhàn)空域越來越復雜的特點，使得現(xiàn)有站點的通信保障能力已不能夠滿足部隊作戰(zhàn)需求，迫切需要優(yōu)化建設數(shù)據(jù)鏈站點。

柵格法是1968年由W.E.Howden所提出的方法［1］，指將整個區(qū)域分解成具有價值信息的網(wǎng)格單元，然后通過優(yōu)化算法完成搜索功能［2］；在柵格法上可運用很多成熟算法，例如深度優(yōu)先算法、遺傳算法和蟻群算法等。柵格法在移動機器人運動規(guī)劃、仿生機器魚路徑規(guī)劃等方面得到重要應用［3-5］。

數(shù)據(jù)鏈站點的選擇問題和數(shù)據(jù)鏈規(guī)劃問題不同，數(shù)據(jù)鏈網(wǎng)絡規(guī)劃問題是被證明是NP-hard問題［6］，而數(shù)據(jù)鏈站點的選擇兼顧動態(tài)空域配置和空域建模［7］，同時考慮站點建設費用等約束條件，因此，數(shù)據(jù)鏈站點選址優(yōu)化問題綜合考慮站點保障能力、飛行航線、站點建設費用等能力因素，結合柵格法，建模成0-1整數(shù)規(guī)劃問題［8-9］。

2 總體思路和方法

2.1 總體思路

以往數(shù)據(jù)鏈站點建立時，參考的因素較少，使得建立的站點難以有效保障部隊的通信需求。因此，需要找到一種新的方式方法，使得新建的站點能夠更好地滿足部隊通信需求。在新建站點時，采用將空域柵格化的方式，對這些飛行區(qū)域進行編號，同時收集部隊飛行航線，確定每一個柵格化飛行區(qū)域所能保障的航線數(shù)，然后根據(jù)備選站點保障范圍，綜合度量各站點的通信保障能力，為站點建設優(yōu)先順序有效的決策支持。

數(shù)據(jù)鏈站點保障柵格化空域示意圖如圖1所示。

（1）空域按照一定的標準劃分柵格，將空域劃分成行號為M個，列號為N個，共計M×N個柵格，對每一個柵格進行編號為aij。

（2）數(shù)據(jù)鏈站點采用擬建設的地理位置。

（3）飛行航線采用實際工作的飛行航線，收集的飛行航線越多，分析得越準確。

2.2 空域柵格化方法

柵格化分析方法把區(qū)域細化到以平方公里或者更小區(qū)域進行規(guī)劃優(yōu)化分析的方法［10］，其中最簡單的柵格形狀是正方形，按照一定規(guī)模劃分柵格［11］，然后在地圖上形成固定的分區(qū)，每個柵格都可以用兩種方法進行標識：

（1）坐標系法：建立坐標系建模，每個柵格用直角坐標進行唯一表示，如圖1所示。

（2）編號法：按照從左到右、從上到下的順序開始對每個柵格進行編號，每個柵格對應唯一編號。

空域柵格化可以更加貼近數(shù)據(jù)鏈的實際需求，可將重點保障區(qū)域精細化到指定的部分區(qū)域，在站點建設方面有利于保障重點空域，空域柵格化的基本步驟如下：

（1）首先設定柵格大小，柵格大小直接影響柵格分析結果的可靠性和使用性，若柵格設置過小，則無法反映區(qū)域性能，只能反映單個數(shù)據(jù)鏈站點的性能；若柵格設置過大，則無法準確定位問題點。根據(jù)經(jīng)驗，柵格大小可以根據(jù)數(shù)據(jù)鏈站點間距進行選取。

（2）然后將空域范圍轉換為墨卡托坐標系的坐標范圍，確認需要重點保障的空域范圍，實現(xiàn)對柵格空域進行精細化管理。

2.3 站點保障范圍與空域疊加方法

站點保障范圍與空域疊加原理：首先根據(jù)視距通信的特點計算出擬建設站點的保障范圍，然后將站點保障范圍疊加到空域中，計算保障站點的覆蓋空域，并標記該站點保障的空域?；静襟E如下：

（1）計算出數(shù)據(jù)鏈站點保障半徑r：

式中h1為站點高度，h2為保障空域的高度。

（2）將數(shù)據(jù)鏈站點的經(jīng)緯度通過墨卡托投影到世界坐標系下（x0，y0），根據(jù)數(shù)據(jù)站點保障半徑，判斷保障范圍與柵格空域關系，若保障范圍覆蓋該空域則進行標記。

2.4 飛行航線與柵格空域疊加關聯(lián)方法

為了統(tǒng)計柵格空域的實際使用需求，在確定空域柵格后，盡量多地收集飛行航線，收集的航線越多，實際需求分析得越準確，然后按照一定的關聯(lián)方法，將航線到整個空域進行關聯(lián)，并標記經(jīng)過的空域，從而確認空域的重要性。航線與柵格空域關聯(lián)的基本步驟如下：

（1）將航線映射到墨卡托坐標系下。

（2）判斷航線與柵格空域的位置關系，與相交的柵格空域做標記。

（3）依次將所有航線按進行計算，統(tǒng)計所有柵格空域包含的航線條數(shù)，航線條數(shù)取值取決于收集的航線信息，取值越大表示空域的重要程度越高。

2.5 站點費用估算方法

費用估算是根據(jù)一定的文字資料和圖紙資料，就擬制的工程項目，通過一定的人類腦力活動的分工與合作，用報表的形式，把費用的開發(fā)費用數(shù)字計算出來。費用估算受多種因素影響，包括國家政策、價格因素等因素影響，費用估算的計算方法可以根據(jù)建筑指標法、測算法、專業(yè)歸類法等方法進行估算［12］。

3 站點保障能力綜合評定

為了綜合評定站點對柵格化空域的保障能力，根據(jù)問題分析和模型假設，在考慮投資有最高上限的約束條件下，模型I求解站點覆蓋面積最大，模型II求解站點覆蓋柵格價值最大。

3.1 數(shù)學模型建立

（1）引入覆蓋矩陣Bk，定義bkij（其中1≤k≤K）為第k個站點對第aij柵格的覆蓋情況，若覆蓋為值1，未覆蓋值為0；

（2）引入柵格價值矩陣D，定義dij為柵格內(nèi)保障飛行航線的數(shù)量，取值越大表示空域的重要程度越高；

（3）引入站點建設矩陣C，定義ci為數(shù)據(jù)鏈站點是否建設，若建設為1，否則為0。

3.2 目標I

投資建設數(shù)據(jù)鏈站點的最大覆蓋面積：

約束條件：

式中：Mi為第i個數(shù)據(jù)鏈站點的建設費用，H為數(shù)據(jù)鏈站點建設的總費用，OR表示或的關系。

3.3 目標II

求解建設數(shù)據(jù)鏈站點的覆蓋柵格價值最大，即保障飛行航線數(shù)量最多：

約束條件：

式中：Mi為第i個數(shù)據(jù)鏈站點的建設費用，H為數(shù)據(jù)鏈站點建設的總費用，OR表示或的關系。

4 案例分析

4.1 案例想定

案例想定：準備在一個區(qū)域開展數(shù)據(jù)鏈站點建設，該區(qū)域由5×5個柵格組成，每個柵格100 km× 100 km，假設有4個位置具備建設條件，每個站點計劃覆蓋3 000 m高度的空域，保障半徑r=200 km，初步設想如圖1所示。同時，假設計劃投資300萬元，每個站點的建設費用如表1所示，求解建設哪些數(shù)據(jù)鏈站點保障覆蓋柵格價值最大。

表1 每個站點建設費用

用最優(yōu)化方法解決決策問題包括兩個基本步驟：首先，需要把實際決策問題用數(shù)學建模的方法建立優(yōu)化模型；其次，選擇利用優(yōu)化方法和工具求解模型。

4.2 初步分析

（1）分析每個站點覆蓋的柵格，如表2所示。

（2）根據(jù)每個柵格內(nèi)保障飛行航線的數(shù)量，得到柵格價值矩陣D。

表2 每個站點覆蓋的柵格情況

4.3 利用LINGO編程求解

利用LINGO工具求解優(yōu)化模型，其中LINGO是美國LINDO系統(tǒng)公司推出的求解最優(yōu)化問題專業(yè)軟件包，優(yōu)勢在于求解各種大型線性、非線性和整數(shù)規(guī)劃方面。數(shù)學求解公式如3.3所示，可利用LINGO編程求解，關鍵代碼如表3所示。

表3 LINGO編程求解程序摘要

通過LINGO 11.0軟件運行后，仿真界面如圖2所示，包括求解狀態(tài)（Solver Status）、擴展求解狀態(tài)（Extended Solver Status）、變量數(shù)量（Variables）、約束數(shù)量（Constraints）、非零系數(shù)數(shù)量（Nonzeroes）、內(nèi)存使用量（Generator Memory Used）、已運行時間（E-lapsed Runtime）。運行結果顯示該案例想定是整數(shù)線性優(yōu)化（ILP）、全局優(yōu)化算法（Global Opt）問題，采用分支定界法（B-and-B），仿真結果為：建設站點1、站點2和站點3，最佳目標函數(shù)值是12。

圖2 仿真結果界面

5 結束語

針對對空數(shù)據(jù)鏈站點選址優(yōu)化實際問題，綜合考慮站點保障能力、飛行航線、站點建設費用等能力因素，通過柵格化分析方法進行數(shù)學建模，將數(shù)據(jù)鏈站點選址優(yōu)化問題轉換為0-1整數(shù)規(guī)劃問題。通過求解建設數(shù)據(jù)鏈站點保障覆蓋柵格價值最大的案例想定，并利用優(yōu)化軟件LINGO進行模型優(yōu)化求解，驗證了柵格化空域方法的可行性。采用空域柵格化方法，在數(shù)據(jù)鏈站點在建設和規(guī)劃方面，能夠更加貼近實際需求；同時，結合飛機航線的實際情況，可更好地提高數(shù)據(jù)鏈站點的服務質量。

［1］夏梁盛，嚴衛(wèi)生.基于柵格法的移動機器人運動規(guī)劃研究［J］.計算機仿真，2012，29（12）：229-232.

［2］王曉林.基于柵格法的仿生機器魚路徑規(guī)劃研究［D］.天津：天津大學，2010.

［3］孫璐.基于柵格法的三維六面體網(wǎng)格自適應生成算法及優(yōu)化技術研究［D］.濟南：山東大學，2012.

［4］王偉峰，吳勇超，張旭，等.基于柵格法的移動機器人單元分解遍歷方法研究［J］.自動化技術與應用，2013，32（11）：34-38.

［5］司馬文霞，李永福，楊慶，等.改進網(wǎng)格法及其在雷電參數(shù)統(tǒng)計中的應用［J］.高電壓技術，2012，38（8）：1834-1841.

［6］司小江，吳禮發(fā)，胡谷雨.數(shù)據(jù)鏈規(guī)劃問題的貪心算法［J］.國防科技大學學報，2013，25（6）：45-49.

［7］張晨，胡明華，張進.基于管型空域配置的交通復雜性管理［J］.系統(tǒng)管理學報，2012，21（5）：327-335.

［8］夏軍，龐征斌，張峻，等.一種基于0_1整數(shù)規(guī)劃的全局數(shù)據(jù)分布優(yōu)化方法［J］.國防科技大學學報，2009，31（4）：62-67.

［9］朱利民，邊計年，周強，等.基于整數(shù)規(guī)劃的層次式FPGA布線算法［J］.計算機輔助設計與圖形學學報，2010，20（10）：1687-1693.

［10］陳磊，江俊敏，袁汶雯.自動柵格化工具的實現(xiàn)及其在網(wǎng)規(guī)網(wǎng)優(yōu)中的應用［J］.郵電設計技術，2010（12）：49-52.

［11］張慧文，鮑廣宇，張義.柵格化網(wǎng)絡態(tài)勢感知能力評估模型［J］.指揮控制與仿真，2013，35（2）：9-12.

［12］趙源.開發(fā)商擬建項目建設費用估算談［J］.建筑經(jīng)濟，2007（7）：252-255.

Research on Location Optimization of Data Link Site Based on Grid Airspace

LIU Hong-bo1，GAO Jun1，GU Shang-li2
（1.School of Electronics Engnieering，Naval University of Engineering，Wuhan 430033，China；
2.The 709th Research Institute，China Shipbuilding Industry Corporation，Wuhan 430205，China）

For the practical problem of optimizing the air data link site，this paper uses rasterized analysis method to carefully plan the data link site and optimize the comprehensive support capability，flight line and cost of building site.Translating the problem of location optimization of data link site to 0-1 Integer programming one，after carefully analyzing the cases，it conducts mathematical modeling with rasterized analysis method and solves the model with optimization software LINGO.Furthermore，the paper puts forward a location optimization of rasterized air data link site.

grid method，data link，LINGO，optimization，0-1 integer programming

TJ630

A

1002-0640（2015）12-0018-04?

2014-11-26

2015-01-05

國家自然科學基金（61372165）；國家“863”計劃基金資助項目（2013AA7026058）

劉宏波（1979-），男，黑龍江齊齊哈爾人，博士生。研究方向：無線通信、網(wǎng)絡通信。