劉宏波，高俊，古尚利

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

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

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

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

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

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

1 概述

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

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

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

2 總體思路和方法

2.1 總體思路

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

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

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

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

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

2.2 空域柵格化方法

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

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

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

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

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

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

2.3 站點(diǎn)保障范圍與空域疊加方法

站點(diǎn)保障范圍與空域疊加原理：首先根據(jù)視距通信的特點(diǎn)計(jì)算出擬建設(shè)站點(diǎn)的保障范圍，然后將站點(diǎn)保障范圍疊加到空域中，計(jì)算保障站點(diǎn)的覆蓋空域，并標(biāo)記該站點(diǎn)保障的空域。基本步驟如下：

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

式中h1為站點(diǎn)高度，h2為保障空域的高度。

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

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

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

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

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

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

2.5 站點(diǎn)費(fèi)用估算方法

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

3 站點(diǎn)保障能力綜合評(píng)定

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

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

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

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

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

3.2 目標(biāo)I

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

約束條件：

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

3.3 目標(biāo)II

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

約束條件：

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

4 案例分析

4.1 案例想定

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

表1 每個(gè)站點(diǎn)建設(shè)費(fèi)用

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

4.2 初步分析

（1）分析每個(gè)站點(diǎn)覆蓋的柵格，如表2所示。

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

表2 每個(gè)站點(diǎn)覆蓋的柵格情況

4.3 利用LINGO編程求解

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

表3 LINGO編程求解程序摘要

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

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

5 結(jié)束語(yǔ)

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

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

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

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

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

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

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

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

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

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

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

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

［12］趙源.開(kāi)發(fā)商擬建項(xiàng)目建設(shè)費(fèi)用估算談［J］.建筑經(jīng)濟(jì)，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

國(guó)家自然科學(xué)基金（61372165）；國(guó)家“863”計(jì)劃基金資助項(xiàng)目（2013AA7026058）

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