基于多目標規劃的GNSS地面站任務資源優化

徐伯健，李昌哲，卜德鋒，符京楊

(1.北京衛星導航中心，北京 100094；2.西安測繪總站，陜西 西安 710054；3.中國洛陽電子裝備試驗中心，河南 洛陽 471003)

?

基于多目標規劃的GNSS地面站任務資源優化

徐伯健1，李昌哲2，卜德鋒3，符京楊1

(1.北京衛星導航中心，北京 100094；2.西安測繪總站，陜西 西安 710054；3.中國洛陽電子裝備試驗中心，河南 洛陽 471003)

摘要隨著衛星導航系統的不斷建設和發展，在復雜任務、多空間和長時間等多約束條件下的導航衛星地面站的資源優化分配問題逐漸顯現。為了準確、高效地解決該問題，應用多目標數學規劃對導航衛星地面站的任務資源建立相關模型并進行求解，仿真結果表明，建立模型的穩定度評價值量化指標在0.2以內，優于常用模型。因此，該方法可以成為嘗試解決導航衛星地面站資源優化問題的一種手段，為未來衛星導航系統形成全球覆蓋能力、多地面站執行復雜任務時的資源優化分配問題的研究打下了基礎。

關鍵詞導航衛星地面站；資源優化；多目標規劃

0引言

2020年前后，全球衛星導航系統(GNSS)的規模將比現階段有更大提升，導航衛星地面站的監測任務量也會大大增加。因此，對目前導航衛星地面站有限的業務資源及管理資源的優化分配的重要性逐漸突顯出來。針對相應的導航任務，得出可適用于多目標的資源優化方案，合理、有效地分配導航衛星地面站有限的業務資源，并在任務期內應對資源沖突時給出多組應對方案并進行比較擇優，以支持多導航任務同時進行。該問題已成為擁有自主GNSS系統的國家的學者們逐漸涉獵的研究方向。資源優化問題的難度與任務相關的因素和其他約束條件同數學模型有著緊密的聯系。

在理論研究層面，目前許多學者對衛星地面站任務規劃及資源調度的算法開展了廣泛研究。通過建立基于單任務的多約束數學模型，并采用貪婪算法[1-2]、混合蟻群算法[3]和模擬退火算法[4]等進行求解，有效地解決了衛星地面站單任務優化問題。該類模型算法的優點是可以獲得模型的最優解且易于編程實現，存在的問題是難以處理復雜的約束條件以及隨機性約束，進而難以應用于處理真實的地面站優化問題。在應用研究層面，目前已在地震電磁衛星[5]、電子偵查衛星[6]和星地混合網絡[7]的應用中取得一定進展。文獻[8-9]提出了相應的模型，文獻[10-11]對衛星地面站的能力進行了分析與評估。目前現有的研究主要針對通信和遙感衛星，而GNSS系統具有衛星數量多、星座構成復雜的特點，現有文獻對其地面站任務資源優化研究較少，故應開展相關研究。

1導航衛星地面站任務資源優化分析

目前我國導航衛星地面站的業務資源及管理資源相對有限，而這些有限的資源又是維持衛星導航系統正常運行的必備基礎之一，也就是說衛星導航系統的地面控制段業務都由這些導航地面站業務資源來保證。每一個地面站都有共同任務和獨特任務，而每一個任務在特定的時間和空間需要有特定的任務資源來支撐。此外，還需要考慮任務持續的時間。

通過前面的基礎描述，可以理解衛星導航的任務方案必須由資源分配方案作為基礎，衛星地面站的資源優化分配方案都不能在任意的時空范圍上超過其資源承載能力。目前已有人針對衛通系統提出了關鍵設備資源調度思想[12]。而衛星導航任務是多目標任務，需要將多種因素納入考慮，多目標數學規劃可能有多樣的可行解，那么具體選擇哪個，要根據任務的需求和地面站的時空條件等要素予以全局考慮。整個多目標規劃的目的是要最大化有效任務—資源連接的數目，最終得到最優的資源分配方案。

2導航衛星地面站任務資源優化的數學模型

導航衛星地面站任務資源優化的數學模型其核心與多目標數學規劃最優解的性質相同，而多目標數學規劃問題的標準形式[13]如下：

式中，V-min表示對P個目標函數f1(x),f2(x),…,fP(x)以向量(f1(x),f2(x),…,fP(x))形式來評價方案的好壞，以區別于單目標規劃中求最小的符號min。

這樣就在衛星導航地面站任務資源優化建模時統一了模型的數學概念。

多目標規劃問題最顯著的應用特點是可以用來評價多個目標評價方案的好壞。對一個多目標規劃問題，在約束集合S中，如果存在一個方案x*對每個目標都是最優的，則稱這個解x*為該多目標規劃問題的絕對最優解。但是在實際遇到的問題中，絕對最優解往往是不存在的。既然絕對最優解往往不存在，所面臨的問題就是對2個或多個都不是絕對最優解的方案，比如x(1),x(2)進行比較，區分其好壞。為了敘述方便，令

F(x)=(f1(x),f2(x),…,fP(x))，

對每個x∈S,F(x)是P維空間RP上的一個向量。x(1),x(2)所對應的目標向量分別是：

F(1)=F(x(1))=(f1(x(1)),f2(x(1)),…,fp(x(1)))，

F(2)=F(x(2))=(f1(x(2)),f2(x(2)),…,fp(x(2)))。

要比較x(1),x(2)的好壞，就要比較這2個目標向量F(x(1)),F(x(2))的好壞，但是比較2個向量的好壞是困難的。為此，要通過軟件程序進行計算比較。

3導航衛星地面站任務資源優化方案

3.1程序實現的流程

如上所述，導航衛星地面站任務資源優化的多目標任務規劃數學模型建立以后，可以通過ILOG OPL組件[14]來解算模型，從而得到任務資源優化的可行解，應用程序對其實現的流程如圖1所示。

3.1.1定義決策變量

決策變量也叫做控制變量。用符合目標的適當數值來描述系統的任務特性，其數量稱之為自由度，該值不能多于總的變量數和方程數目的差值。

在對所描述的問題確定后，定義導航衛星地面站(Station)站名(name)、地面站編號(sta_id)和信號傳輸設備數(Num)，描述如下：

Station=。

可選擇項(Alternative)含任務資源編號(taskres_id)、地面站編號(sta_id)、初始時間(FTime)、持續時間(duration)和結束時間(LTime)，描述如下：

Alternative=。

以上2個公式完成了決策變量的定義。

圖 1　程序實現流程

3.1.2定義優化目標

優化目標是指導航衛星地面站任務資源與相關因素的函數關系。根據多目標規劃數學模型中的描述，優化目標應為最大化的導航衛星與地面站任務資源中相關的數目，描述如下：

max{sum{a|ai≠aj;a,ai,aj∈Alternatives,}}。

3.1.3定義約束條件

運用多目標規劃的數學方法解決導航衛星地面站任務資源優化問題時，需將必須明確的前提條件定義為多目標任務規劃的約束條件。約束條件的選擇往往受到多目標規劃中的多重條件的限制。

在導航衛星地面站任務資源優化問題中主要需滿足的約束條件，首先是任務資源必須被使用且滿足任務完成的基本條件，

task∈Tasks&{task,ta1,ta2∈Alternative;ta1≠ta2}。

另外一個關鍵的約束條件是導航衛星地面站的最大任務資源量不能超過站點所能承受的極限資源量s.Max，表達式為：

∑{task∈A&s∈S&task.sta_id=s.sta_id}<=s.Max。

3.2解決方案的生成

最終應用ILOG OPL組件進行求解，生成的結果便是導航衛星地面站任務資源優化方案的一組解，使得結果與任務資源的需求量相對應，在執行過程中設定上限并充分滿足任務的時間節點，其中模型中所含的過程量也可在生成結果中查詢到，最終可得數據解及多組解的比較結果，如圖2所示。

圖2　導航衛星地面站任務資源優化解決方案對比

3.3仿真實驗與分析

針對GNSS地面站任務資源優化案例進行仿真，仿真條件如下：實驗在Windows7(64位)系統，Intel CORE i7處理器，8 GB內存儲器，仿真軟件選用ILOG OPL和Matlab R2015b的工作站上進行。地面站位置模擬位置位于北緯N37°0′0″，東經E113°30′0″，高程為1 089.66 m。在目前已有的GNSS系統中選擇GPS系統為仿真實驗研究對象，星歷采用IGS提供的精密星歷數據。設定任務資源優化以300個歷元時刻為周期重復進行，則任務中存在的沖突主要體現在每個周期內地面站中存在的任務對資源的競爭。由于該時刻衛星可見數目可知，可以確定目標活動的資源預約用量值，因此可以確定導航衛星與地面站之間的時間窗口，從而應用模型進行資源優化。

首先根據地面站資源優化問題的特點及其特定性，將資源優化的求解共分3個階段：系統初始配置階段、初始化階段和沖突檢測與修復階段。在系統初始配置階段，主要獲得參數的輸入，包括地面站參數的定義和任務與資源的聲明；在初始化階段，對具體的計算模型進行迭代計算生成一個初始化結果，初始化并不可得到優化結果，結果中可能存在很多沖突；沖突檢測與修復階段負責對初始化結果中的沖突進行探測和修復，本文實驗中設計了一個循環修復算法，通過反復的沖突修復最終生成一個滿足優化目標的輸出結果。資源優化求解流程如圖3所示。

在資源優化的初始化解的過程中，本文參考文獻[2]和文獻[4]中提出的模型，將其抽象為單任務多約束的模型1和模型2，并與本文提出的模型進行比較。通過對ILOG OPL給出的3種方案進行迭代計算，從而對評價值進行考核。該評價值表示經過模型優化過的平均值與計算結果的平均值的比值，理論上越接近于1表示該模型更加優化和穩定，如表1所示。

表1　3種模型應用于各方案的評價值比較

此外，針對評價值的考量還應驗證其隨時間變化的穩定度。3種模型隨時間變化的評價值如圖4所示。從圖4中可以看出，本文采用的模型在程序運行5 min的計算時間內，相比模型1和模型2的評價值浮動較小，證明本文采用的模型在穩定度方面具有一定優勢。

圖4　3種模型隨時間變化的評價值

3.4結論

通過對上述實驗結果加以分析和歸納，可得結論如下：

① 基于多目標數學規劃的模型可以嘗試建立導航衛星地面站的任務資源優化模型；

② 應用該模型的數學解得到的方案可以形成現有的導航衛星地面站任務資源管理方案的備選方案集；

③ 相比單任務多約束的數學模型及其解法，采用多目標數學規劃法建立模型可以得到更加綜合穩定的優化解。

4結束語

本文對導航衛星地面站任務資源優化問題進行了描述，針對該問題建立了數學模型，并提出了通過確定相關決策變量、約束條件和目標函數，進而嘗試采用ILOG OPL軟件對問題演算和求解。

在未來的研究中，應結合我國自主的GNSS地面站管理任務，形成更切合實際情況且更為精確的基于多目標任務規劃的資源優化數學模型并進行求解，同時嘗試應用更多的現有程序與ILOG OPL組件進行接口集成，使得導航衛星地面站的任務資源優化問題擁有更多、更好、更快的解決方案。

參考文獻

[1]張超.基于貪婪算法的遙感地面站任務調度技術[J].無線電工程,2011,41(1):58-60.

[2]張紅旗.基于貪婪算法的衛星地面站資源調度方法[J].無線電工程,2010,40(12):4-6.

[3]邢立寧,陳英武.基于混合蟻群優化的衛星地面站系統任務調度方法[J].自動化學報,2008(4):414-418.

[4]韓麗,張學慶.基于模擬退火的衛星地面站任務規劃方法[J].無線電工程,2010,40(9):42-43.

[5]王紅飛,劉玉榮,閻鎮.地震電磁衛星任務規劃系統研究[J].空間科學學報,2010,30(6):620-625.

[6]冉承新,熊綱要,王慧林,等.電子偵察衛星任務規劃調度模型與算法研究[J].通信對抗,2009(1):3-8.

[7]徐婧婧.星地混合網絡中的容量規劃與任務調度研究[D].成都:電子科技大學,2013.

[8]徐露露,陳俊,馮鐘葵,等.一種衛星地面系統中實現任務調度策略可配置的方法[J].遙感信息,2012,27(6):35-38.

[9]金光.衛星地面站測控資源調度CSP模型[J].系統工程與電子技術,2007(7):1 117-1 120.

[10]金光,武小悅,高衛斌.基于沖突的衛星地面站系統資源調度與能力分析[J].小型微型計算機系統,2007(2):310-312.

[11]常飛.衛星地面站系統資源能力評估方法研究[D].長沙：國防科學技術大學,2005.

[12]孟學軍,趙艷朝,林賀.衛星通信地球站智能切換單元的設計與實現[J].無線電通信技術,2014,40(5):89-92.

[13]陳慶華，郭全魁.裝備運籌學教程[M].北京:國防工業出版社,2006.

[14]楊廣強.基于ILOG OPL的傳輸網資源使用能效優化分析[J].現代電信科技,2011,41(7):54-57.

doi:10.3969/j.issn.1003-3106.2016.07.12

收稿日期：2016-03-15

中圖分類號V556.1

文獻標志碼A

文章編號1003-3106(2016)07-0045-04

作者簡介

徐伯健男，(1973—)，高級工程師。主要研究方向：衛星導航定位性能提升。

Optimization of GNSS Ground Station Task Resources Based on Multi-objective Programming

XU Bo-jian1,LI Chang-zhe2,BU De-feng3,FU Jing-yang1

(1.TheBeijingSatelliteNavigationCenter,Beijing100094,China;2.Xi’anDivisionofSurveyingandMapping,Xi’anShaanxi710054,China;3.LuoyangElectronicEquipmentTestingCenter,LuoyangHe’nan471003,China)

AbstractWith the continuous construction and development of satellite navigation system,the problem of resource allocation of navigation satellite ground station is gradually emerging in constraints of complex tasks,multi space,and long time.In order to solve this problem accurately and efficiently,the task resource of navigation satellite ground station is established by using multi-objective mathematical programming.The simulation results show that the stability evaluation value of the model is less than 0.2,which is better than the common model.This method can solve the problem of the optimization of the ground station resources,and it is the basis of studying the resource optimization allocation for complex tasks implementation through multiple ground stations when the future satellite navigation system has global coverage capability.

Key wordsGNSS ground station;resource optimization;multi-objective programming

引用格式：徐伯健,李昌哲,卜德鋒,等.基于多目標規劃的GNSS地面站任務資源優化[J].無線電工程,2016,46(7):45-48.