基于多目標(biāo)規(guī)劃的GNSS地面站任務(wù)資源優(yōu)化

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

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

?

基于多目標(biāo)規(guī)劃的GNSS地面站任務(wù)資源優(yōu)化

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

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

摘要隨著衛(wèi)星導(dǎo)航系統(tǒng)的不斷建設(shè)和發(fā)展，在復(fù)雜任務(wù)、多空間和長時間等多約束條件下的導(dǎo)航衛(wèi)星地面站的資源優(yōu)化分配問題逐漸顯現(xiàn)。為了準(zhǔn)確、高效地解決該問題，應(yīng)用多目標(biāo)數(shù)學(xué)規(guī)劃對導(dǎo)航衛(wèi)星地面站的任務(wù)資源建立相關(guān)模型并進行求解，仿真結(jié)果表明，建立模型的穩(wěn)定度評價值量化指標(biāo)在0.2以內(nèi)，優(yōu)于常用模型。因此，該方法可以成為嘗試解決導(dǎo)航衛(wèi)星地面站資源優(yōu)化問題的一種手段，為未來衛(wèi)星導(dǎo)航系統(tǒng)形成全球覆蓋能力、多地面站執(zhí)行復(fù)雜任務(wù)時的資源優(yōu)化分配問題的研究打下了基礎(chǔ)。

關(guān)鍵詞導(dǎo)航衛(wèi)星地面站；資源優(yōu)化；多目標(biāo)規(guī)劃

0引言

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

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

1導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化分析

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

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

2導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化的數(shù)學(xué)模型

導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化的數(shù)學(xué)模型其核心與多目標(biāo)數(shù)學(xué)規(guī)劃最優(yōu)解的性質(zhì)相同，而多目標(biāo)數(shù)學(xué)規(guī)劃問題的標(biāo)準(zhǔn)形式[13]如下：

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

這樣就在衛(wèi)星導(dǎo)航地面站任務(wù)資源優(yōu)化建模時統(tǒng)一了模型的數(shù)學(xué)概念。

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

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

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

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個目標(biāo)向量F(x(1)),F(x(2))的好壞，但是比較2個向量的好壞是困難的。為此，要通過軟件程序進行計算比較。

3導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化方案

3.1程序?qū)崿F(xiàn)的流程

如上所述，導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化的多目標(biāo)任務(wù)規(guī)劃數(shù)學(xué)模型建立以后，可以通過ILOG OPL組件[14]來解算模型，從而得到任務(wù)資源優(yōu)化的可行解，應(yīng)用程序?qū)ζ鋵崿F(xiàn)的流程如圖1所示。

3.1.1定義決策變量

決策變量也叫做控制變量。用符合目標(biāo)的適當(dāng)數(shù)值來描述系統(tǒng)的任務(wù)特性，其數(shù)量稱之為自由度，該值不能多于總的變量數(shù)和方程數(shù)目的差值。

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

Station=。

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

Alternative=。

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

圖 1　程序?qū)崿F(xiàn)流程

3.1.2定義優(yōu)化目標(biāo)

優(yōu)化目標(biāo)是指導(dǎo)航衛(wèi)星地面站任務(wù)資源與相關(guān)因素的函數(shù)關(guān)系。根據(jù)多目標(biāo)規(guī)劃數(shù)學(xué)模型中的描述，優(yōu)化目標(biāo)應(yīng)為最大化的導(dǎo)航衛(wèi)星與地面站任務(wù)資源中相關(guān)的數(shù)目，描述如下：

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

3.1.3定義約束條件

運用多目標(biāo)規(guī)劃的數(shù)學(xué)方法解決導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化問題時，需將必須明確的前提條件定義為多目標(biāo)任務(wù)規(guī)劃的約束條件。約束條件的選擇往往受到多目標(biāo)規(guī)劃中的多重條件的限制。

在導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化問題中主要需滿足的約束條件，首先是任務(wù)資源必須被使用且滿足任務(wù)完成的基本條件，

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

另外一個關(guān)鍵的約束條件是導(dǎo)航衛(wèi)星地面站的最大任務(wù)資源量不能超過站點所能承受的極限資源量s.Max，表達式為：

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

3.2解決方案的生成

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

圖2　導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化解決方案對比

3.3仿真實驗與分析

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

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

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

表1　3種模型應(yīng)用于各方案的評價值比較

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

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

3.4結(jié)論

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

① 基于多目標(biāo)數(shù)學(xué)規(guī)劃的模型可以嘗試建立導(dǎo)航衛(wèi)星地面站的任務(wù)資源優(yōu)化模型；

② 應(yīng)用該模型的數(shù)學(xué)解得到的方案可以形成現(xiàn)有的導(dǎo)航衛(wèi)星地面站任務(wù)資源管理方案的備選方案集；

③ 相比單任務(wù)多約束的數(shù)學(xué)模型及其解法，采用多目標(biāo)數(shù)學(xué)規(guī)劃法建立模型可以得到更加綜合穩(wěn)定的優(yōu)化解。

4結(jié)束語

本文對導(dǎo)航衛(wèi)星地面站任務(wù)資源優(yōu)化問題進行了描述，針對該問題建立了數(shù)學(xué)模型，并提出了通過確定相關(guān)決策變量、約束條件和目標(biāo)函數(shù)，進而嘗試采用ILOG OPL軟件對問題演算和求解。

在未來的研究中，應(yīng)結(jié)合我國自主的GNSS地面站管理任務(wù)，形成更切合實際情況且更為精確的基于多目標(biāo)任務(wù)規(guī)劃的資源優(yōu)化數(shù)學(xué)模型并進行求解，同時嘗試應(yīng)用更多的現(xiàn)有程序與ILOG OPL組件進行接口集成，使得導(dǎo)航衛(wèi)星地面站的任務(wù)資源優(yōu)化問題擁有更多、更好、更快的解決方案。

參考文獻

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

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

[3]邢立寧,陳英武.基于混合蟻群優(yōu)化的衛(wèi)星地面站系統(tǒng)任務(wù)調(diào)度方法[J].自動化學(xué)報,2008(4):414-418.

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

[5]王紅飛,劉玉榮,閻鎮(zhèn).地震電磁衛(wèi)星任務(wù)規(guī)劃系統(tǒng)研究[J].空間科學(xué)學(xué)報,2010,30(6):620-625.

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

[7]徐婧婧.星地混合網(wǎng)絡(luò)中的容量規(guī)劃與任務(wù)調(diào)度研究[D].成都:電子科技大學(xué),2013.

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

[9]金光.衛(wèi)星地面站測控資源調(diào)度CSP模型[J].系統(tǒng)工程與電子技術(shù),2007(7):1 117-1 120.

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

[11]常飛.衛(wèi)星地面站系統(tǒng)資源能力評估方法研究[D].長沙：國防科學(xué)技術(shù)大學(xué),2005.

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

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

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

doi:10.3969/j.issn.1003-3106.2016.07.12

收稿日期：2016-03-15

中圖分類號V556.1

文獻標(biāo)志碼A

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

作者簡介

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

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

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