地空超短波數(shù)據(jù)鏈站點選址及覆蓋優(yōu)化

劉宏波，孟進，劉琴濤，馬俊凱

(1.海軍工程大學(xué) 艦船綜合電力技術(shù)國防科技重點實驗室，湖北 武漢 430033，2.海軍工程大學(xué) 電子工程學(xué)院，湖北 武漢 430033)

0 引言

數(shù)據(jù)鏈通信系統(tǒng)是地空通信中最常用的通信手段之一，針對重點空域，合理地選擇一定數(shù)量的站點布置數(shù)據(jù)鏈通信系統(tǒng)，可以保證重要空域的有效覆蓋；同時，進行合理信道規(guī)劃和容量分配，實現(xiàn)數(shù)據(jù)鏈通信系統(tǒng)的站點優(yōu)化。

選址問題是運籌學(xué)和計算科學(xué)等領(lǐng)域的決策問題，在數(shù)字地圖出現(xiàn)之前，基站選址主要依靠現(xiàn)地測量參數(shù)然后進行選擇確定地點；在數(shù)字地圖出現(xiàn)之后，根據(jù)工作經(jīng)驗利用電子地圖進行盲搜索，反復(fù)進行覆蓋分析和預(yù)測能力驗證[1]。經(jīng)典的選址問題包括Weber問題、P-中值問題、P-中心問題、覆蓋優(yōu)化、競爭選址、截流選址、選址- 分配、選址- 路線等問題，是選址研究工作的理論基礎(chǔ)[2]。地空超短波數(shù)據(jù)鏈站點選址及覆蓋優(yōu)化問題是非確定多項式(NP)-困難問題。目前有關(guān)數(shù)據(jù)鏈站點選址問題的文獻并不多見，但因與移動基站選址、雷達站選址[3]和廣播式自動相關(guān)監(jiān)視系統(tǒng)(ADS-B)地面站選址[4]等需要考慮的因素有相似之處，可以相互借鑒。

針對覆蓋模型方面，基站選址主要采用集合覆蓋模型，Toregas等[5]最早提出了集合覆蓋問題；Church等[6]提出了最大覆蓋問題，解決了集合覆蓋產(chǎn)生的資源閑置問題；Hogan等[7]提出了備用覆蓋的數(shù)學(xué)模型；Calegari等[8]利用最大覆蓋模型實現(xiàn)了基站的自適應(yīng)定位；Bell等[9]采用集合覆蓋模型設(shè)計航空警報器的選址問題；Eisenblatter等[10]針對基站選址布局問題建立了集合覆蓋算法模型，并進行了計算機仿真實驗；Lee等[11]針對Wi-Fi設(shè)備選址進行了仿真驗證；Erdemir等[12]針對航空設(shè)備研究了地面覆蓋等選址問題。

此外，針對數(shù)據(jù)鏈站點的選址方面，學(xué)者們綜合考慮了電磁波傳輸環(huán)境、地形覆蓋、代價等方面因素影響，認為需要加強站點保障能力、航線數(shù)量、站點建設(shè)費用等因素對數(shù)據(jù)鏈站點選擇的影響研究[13]；同時，考慮地理高程對電磁信號覆蓋范圍的影響，使用交互式的線性和通用優(yōu)化求解器LINGO軟件進行優(yōu)化[14]。此外，針對地基增強系統(tǒng)、空管監(jiān)視臺站和加油站等，進行覆蓋分析和選址仿真[15-19]，并且開展了基站選擇的算法和場景等相關(guān)研究，主要針對數(shù)據(jù)鏈接入控制協(xié)議進行研究[20]。

本文針對數(shù)據(jù)鏈站點的保障能力和站點建設(shè)費用等因素對站點選擇的影響開展研究，針對柵格覆蓋是否有重疊或者漏覆蓋的柵格作出約束，采用覆蓋面積最大模型和覆蓋價值最大模型，建立數(shù)學(xué)模型進行優(yōu)化計算。通過軟件的仿真案例，介紹了數(shù)據(jù)鏈站點選址優(yōu)化的建模方法，利用無線電頻譜規(guī)劃管理軟件，采用數(shù)學(xué)模型完成覆蓋范圍計算和覆蓋范圍優(yōu)化計算。在模型的優(yōu)越性方面，體現(xiàn)在采用電子地圖和覆蓋模型相結(jié)合的快速優(yōu)化技術(shù)，提升選址過程的計算效率，可用于數(shù)據(jù)鏈站點選址優(yōu)化的輔助決策。

1 選址的覆蓋問題分析

1.1 覆蓋問題模型

覆蓋范圍問題可分為區(qū)域覆蓋、點覆蓋和障礙覆蓋，覆蓋能力分析主要包括站點部署方案、通信與感知范圍等。數(shù)據(jù)鏈覆蓋分析的主要目標是針對用戶特定的規(guī)劃區(qū)域，進行網(wǎng)絡(luò)覆蓋和業(yè)務(wù)容量的分析，得出數(shù)據(jù)鏈網(wǎng)絡(luò)的重要鏈路性能指標、方向圖覆蓋范圍以及業(yè)務(wù)量負載情況。覆蓋分析需要提供包括電子地圖、基站位置、參數(shù)設(shè)計、天線參數(shù)以及傳播模型等信息。覆蓋問題包括集合覆蓋問題和最大覆蓋問題，基站選址主要采用集覆蓋模型。

1.1.1 集合覆蓋問題模型

集合覆蓋問題要求每一個服務(wù)站至少覆蓋一次，尋找成本最小的服務(wù)站集合。

定義fj為候選點j的服務(wù)站固定建站費用；定義0-1變量為

定義決策變量Xj為

數(shù)學(xué)模型為

(1)

(2)

Xj=0,1， ?j.

(3)

目標函數(shù)(1)式表示服務(wù)站建站成本最小；約束(2)式表示限制每一個服務(wù)站至少覆蓋一次；約束(3)式是0-1約束。

1.1.2 最大覆蓋問題模型

集合覆蓋問題的缺點是沒有考慮各站點的需求量，最大覆蓋問題主要解決服務(wù)站需求量最大的問題。定義符號hi為需求點i的需求量，p為準備設(shè)立的服務(wù)站個數(shù)，定義決策變量Zj為

變量Xj和Cij的定義同前，則最大覆蓋問題可以描述為

(4)

(5)

(6)

Xj=0,1，?j，

(7)

Zi=0,1，?i.

(8)

目標函數(shù)(4)式表示被覆蓋的需求量最大；約束(5)式表示服務(wù)站是否被覆蓋；約束(6)式為p個服務(wù)站；約束(7)式和(8)式是0-1約束。

1.2 覆蓋優(yōu)化的常見算法

覆蓋選址問題是NP-困難問題，其中求解覆蓋問題包括貪婪算法、遺傳算法和拉格朗日松弛算法等常見算法；其中，貪婪算法在集合覆蓋選址方面可以獲得局部最優(yōu)的解，因此，貪婪算法使用的場合比較多。簡單的貪婪算法包括貪婪相加和貪婪減少兩種算法，針對簡單的貪婪算法進行改進的算法包括隨機貪婪算法和貪婪改善算法。

求解覆蓋問題方面，包括有蟻群算法、人工神經(jīng)網(wǎng)絡(luò)、模擬退火算法、禁忌搜索算法等算法，主要用于尋求選址問題的滿意解，但不一定是最優(yōu)解。

2 基于柵格化的站點保障能力模型

根據(jù)數(shù)據(jù)鏈站點選擇的問題分析，為了綜合評定站點對柵格化空域的保障能力，考慮兩種基于柵格化的站點保障能力，求解站點覆蓋面積最大和站點覆蓋柵格價值最大，約束條件是建設(shè)費用具有一定限制[14]。其中費用估算是針對擬建設(shè)的數(shù)據(jù)鏈站點項目，根據(jù)一定的文字資料和圖紙資料，通過一定的市場調(diào)查或者詢價過程，用報表或者報告的形式，進行開發(fā)費用估算。

2.1 基本數(shù)學(xué)模型

1)引入覆蓋矩陣Bk，

(9)

式中：bkij為第k個站點對第aij柵格的覆蓋情況，若該柵格被覆蓋則數(shù)值取1，否則取0；1≤k≤K，K為站點的最大值；1≤i≤M，M為柵格的橫坐標最大值；1≤j≤N，N為柵格的縱坐標最大值。

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

(10)

3)引入站點建設(shè)矩陣C，

(11)

式中：ck為數(shù)據(jù)鏈站點是否建設(shè)，若建設(shè)為1，否則為0.

引入覆蓋矩陣Bk、柵格矩陣D和站點建設(shè)矩陣C之后，需要選擇計算模型。針對數(shù)據(jù)鏈站點的保障能力計算，最優(yōu)指標的選取可采用覆蓋面積最大模型；針對降低站點建設(shè)費用計算，可采用覆蓋價值最大模型。

2.2 覆蓋面積最大模型

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

(12)

(13)

式中：Mk為第k個數(shù)據(jù)鏈站點的建設(shè)費用；H為數(shù)據(jù)鏈站點建設(shè)的總費用。

2.3 覆蓋價值最大模型

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

(14)

(15)

3 覆蓋范圍優(yōu)化計算工具分析

無線電頻譜規(guī)劃管理軟件具有豐富的可選電波傳播模型，可以計算無線電波傳播和干擾特性，進行頻率指配，包含的分析計算模塊有：覆蓋范圍計算工具、無線鏈路性能分析計算工具、干擾計算工具、同址干擾計算工具、頻率指配計算工具、短波規(guī)劃計算工具和覆蓋范圍優(yōu)化計算工具等。覆蓋范圍優(yōu)化計算工具提供基于無線電臺站特性、地理信息系統(tǒng)和電波傳播模型，在最優(yōu)化范圍內(nèi)取得任何類型臺站布放位置及自動選址計算功能，并可結(jié)合工程成本及布放數(shù)量進行優(yōu)化分析。

圖1為費用及覆蓋范圍優(yōu)化計算軟件界面。該軟件包括計算工具的基本設(shè)置項，提出覆蓋面積標準及所要達到的接收功率值。覆蓋范圍優(yōu)化工具提供基于無線電臺站特性、地理信息系統(tǒng)和電波傳播模型，在最優(yōu)化范圍內(nèi)取得任何類型臺站布放位置及自動選址計算功能，并可結(jié)合工程成本及布放數(shù)量進行優(yōu)化分析。

圖1 費用及覆蓋范圍優(yōu)化器界面圖Fig.1 Cost and coverage optimizer interface

覆蓋范圍計算工具用于分析無線電業(yè)務(wù)適用于全頻段(10 kHz～300 GHz)，基于各發(fā)射臺的傳輸衰減計算覆蓋區(qū)域，同時結(jié)合發(fā)射功率、發(fā)射天線方位圖、接收天線增益、濾波衰減以及電纜衰減等因素計算接收信號電平。針對干擾信號的計算，需考慮發(fā)射頻譜、發(fā)射天線及接收天線濾波器及接收選擇性等因素?？梢跃庉嬇_站和設(shè)備的相關(guān)參數(shù)，并依據(jù)修改后的參數(shù)進行計算；計算運行完畢后，可由二維或三維地圖顯示多個層次的地面覆蓋效果。

4 站點選址及覆蓋優(yōu)化案例

針對地空超短波通信數(shù)據(jù)鏈站點選址，增加選址的數(shù)量，計算的復(fù)雜度會發(fā)生變化。根據(jù)數(shù)據(jù)模型可知，模型收斂主要取決于限制條件的選取，如果限制條件設(shè)置過多或者過于嚴格，會出現(xiàn)無解的情況，此時需要用戶根據(jù)優(yōu)化模型的優(yōu)點和缺點進行選取。下面通過軟件仿真案例，重點說明數(shù)據(jù)鏈站點選址優(yōu)化的建模方法，以地圖和數(shù)據(jù)兩種形式顯示效果。

假設(shè)區(qū)域現(xiàn)有5個已知站點具備架設(shè)臺站條件，考慮多方面因素，需要從現(xiàn)有5個站點中選擇部分站點(不超過4個)完成選址，要求對高空區(qū)域?qū)崿F(xiàn)全面覆蓋，并針對主要區(qū)域?qū)崿F(xiàn)重點覆蓋。

其中，通信臺站主要性能如下：

1)地面站：頻率125 MHz，有效全向輻射功率(EIRP)為19 dBW，天線架高20 m，增益3 dBi，垂直極化；

2)空中飛機：飛行高度3 000 m高空，接收機靈敏度-90 dBm，接收天線增益0 dBi，垂直極化。

基于上述需求，使用無線電頻譜規(guī)劃管理軟件完成臺站選址。具體選址過程如下：

1)使用無線電頻譜規(guī)劃管理軟件，在地圖中布放現(xiàn)有站點位置，站點位置部署有5個已知站點。

2)在地圖中劃定需要覆蓋的區(qū)域，重點區(qū)域覆蓋可以由用戶自定義區(qū)域，此處省略。

圖2 覆蓋范圍的參數(shù)設(shè)置界面Fig.2 Parameter setting interface for coverage

3)使用覆蓋范圍優(yōu)化計算工具，設(shè)置布放條件、覆蓋條件和評估條件等，覆蓋范圍的參數(shù)設(shè)置界面如圖2所示。

4) 選址計算執(zhí)行后可獲得最終選址方案，需要區(qū)域覆蓋。傳播模型參數(shù)設(shè)置界面如圖3所示。

圖3 傳播模型的參數(shù)設(shè)置界面Fig.3 Parameter setting interface of propagation model

5)使用軟件提供的選址方案，并在地圖中顯示臺站位置，從現(xiàn)有5個站點中選擇部分站點(例如4個)，完成選址優(yōu)化并計算站點的覆蓋效果，優(yōu)化后站點覆蓋示意圖如圖4所示。

圖4 優(yōu)化后的站點覆蓋示意圖Fig.4 Optimized site coverage

5 結(jié)論

本文針對數(shù)據(jù)鏈站點選擇利用工作經(jīng)驗和地圖進行盲搜索覆蓋分析能力的難題，設(shè)計了基于柵格化的站點保障能力模型，分析了覆蓋范圍優(yōu)化計算工具，結(jié)合站點選址及覆蓋優(yōu)化案例，研究了地空超短波數(shù)據(jù)鏈站點選址及覆蓋優(yōu)化問題。采用無線電頻譜規(guī)劃管理軟件完成覆蓋范圍計算和覆蓋能力優(yōu)化計算，將傳統(tǒng)電波傳播模型計算與地理信息平臺進行有機結(jié)合，基于地形條件的臺站優(yōu)化選址功能，研究了站點保障能力、航線數(shù)量、站點建設(shè)費用等因素對數(shù)據(jù)鏈站點選擇的影響，確保利用有限的資源完成最優(yōu)的項目配置方案，實現(xiàn)數(shù)據(jù)鏈站點的覆蓋范圍優(yōu)化分析。其中，采用覆蓋面積最大模型進行數(shù)據(jù)鏈站點的保障能力計算，采用覆蓋價值最大模型進行降低站點建設(shè)費用計算。本文在選址的計算效率方面進行了技術(shù)提升，下一步針對重點區(qū)域業(yè)務(wù)量的變化規(guī)律，可以研究數(shù)據(jù)鏈系統(tǒng)運行過程中網(wǎng)絡(luò)覆蓋能力的實時評估技術(shù)。