劉宏波，高俊，古尚利

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

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

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

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

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

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

1 概述

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

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

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

2 總體思路和方法

2.1 總體思路

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

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

（1）空域按照一定的標(biāo)準(zhǔn)劃分柵格，將空域劃分成行號為M個，列號為N個，共計M×N個柵格，對每一個柵格進(jìn)行編號為aij。

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

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

2.2 空域柵格化方法

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

（1）坐標(biāo)系法：建立坐標(biāo)系建模，每個柵格用直角坐標(biāo)進(jìn)行唯一表示，如圖1所示。

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

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

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

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

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

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

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

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

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

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

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

（1）將航線映射到墨卡托坐標(biāo)系下。

（2）判斷航線與柵格空域的位置關(guān)系，與相交的柵格空域做標(biāo)記。

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

2.5 站點費用估算方法

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

3 站點保障能力綜合評定

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

3.1 數(shù)學(xué)模型建立

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

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

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

3.2 目標(biāo)I

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

約束條件：

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

3.3 目標(biāo)II

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

約束條件：

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

4 案例分析

4.1 案例想定

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

表1 每個站點建設(shè)費用

用最優(yōu)化方法解決決策問題包括兩個基本步驟：首先，需要把實際決策問題用數(shù)學(xué)建模的方法建立優(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ù)學(xué)求解公式如3.3所示，可利用LINGO編程求解，關(guān)鍵代碼如表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）。運行結(jié)果顯示該案例想定是整數(shù)線性優(yōu)化（ILP）、全局優(yōu)化算法（Global Opt）問題，采用分支定界法（B-and-B），仿真結(jié)果為：建設(shè)站點1、站點2和站點3，最佳目標(biāo)函數(shù)值是12。

圖2 仿真結(jié)果界面

5 結(jié)束語

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

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

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

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

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

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

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

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

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

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

［10］陳磊，江俊敏，袁汶雯.自動?xùn)鸥窕ぞ叩膶崿F(xiàn)及其在網(wǎng)規(guī)網(wǎng)優(yōu)中的應(yīng)用［J］.郵電設(shè)計技術(shù)，2010（12）：49-52.

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

［12］趙源.開發(fā)商擬建項目建設(shè)費用估算談［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

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

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