陶孫杰，宋 竹

(中國西南電子技術(shù)研究所，成都610036)

1 引 言

隨著在軌衛(wèi)星數(shù)量的增加、衛(wèi)星能力的提升，為衛(wèi)星提供數(shù)傳、測控服務(wù)的地面資源也越來越緊張，對于同一套地面站天線及配套設(shè)備，同一時刻該地面資源僅能為一顆衛(wèi)星提供服務(wù)，當(dāng)多顆衛(wèi)星的過境時間窗口存在交叉時，該資源即存在資源使用沖突問題。因此，如何合理有效地為用戶衛(wèi)星任務(wù)分配地面站網(wǎng)資源，在滿足衛(wèi)星測控數(shù)傳需求的情況下，最大化地發(fā)揮地面站網(wǎng)資源使用效益，是站網(wǎng)資源調(diào)度的首要關(guān)注點(diǎn)。

現(xiàn)有的大部分站網(wǎng)資源調(diào)度都是根據(jù)不同任務(wù)類型(測控、數(shù)傳)單獨(dú)進(jìn)行規(guī)劃，不符合地面站網(wǎng)資源測控數(shù)傳一體化的發(fā)展方向。因此，設(shè)計具備在站網(wǎng)資源調(diào)度中考慮不同任務(wù)類型，同時盡可能最大化滿足各用戶需求，針對實(shí)際應(yīng)用的多星多站多任務(wù)站網(wǎng)資源調(diào)度算法，是當(dāng)前站網(wǎng)資源調(diào)度規(guī)劃亟待解決的問題。

近年來，國內(nèi)外學(xué)者針對衛(wèi)星和地面資源調(diào)度開展了大量工作并取得豐碩的研究成果[1-10]。但是，現(xiàn)有的研究都聚焦于單一測控任務(wù)或單一數(shù)傳任務(wù)的資源調(diào)度，未考慮未來測控數(shù)傳一體化衛(wèi)星任務(wù)規(guī)劃和地面資源調(diào)度中測控需求和數(shù)傳需求的差異性。同時，現(xiàn)有的理論研究雖然較為深入，但對于實(shí)際應(yīng)用中用戶常規(guī)使用約束和使用要求未進(jìn)行充分考慮和針對性設(shè)計，使得研究成果無法直接進(jìn)行工程應(yīng)用。因此，本文從實(shí)際應(yīng)用出發(fā)，針對測控數(shù)傳一體化的用戶需求及任務(wù)類型特點(diǎn)，對約束分析、問題建模、算法設(shè)計等方面進(jìn)行研究。

2 站網(wǎng)資源調(diào)度問題描述

站網(wǎng)資源調(diào)度可以理解為為用戶的站網(wǎng)資源使用申請分配地面站資源以及資源的使用時間。在測控數(shù)傳一體化規(guī)劃要求下，站網(wǎng)資源調(diào)度需要為測控、數(shù)傳任務(wù)進(jìn)行統(tǒng)一資源調(diào)度，需要支持不同的衛(wèi)星任務(wù)類型，具備多星多天線1～7天資源調(diào)度的能力。

為了切實(shí)滿足工程和實(shí)際應(yīng)用需求，站網(wǎng)資源調(diào)度算法的研究需要考慮以下內(nèi)容：

(1)需求與任務(wù)類型。支持用戶指定衛(wèi)星進(jìn)出站時間的指定圈次模式以及用戶指定時間范圍與任務(wù)總時長的指定時長模式。其中指定圈次模式需要用戶指定該弧段的任務(wù)類型，而指定時長模式需要用戶分別指定測控、數(shù)傳任務(wù)的需求時長。

(2)各類約束與優(yōu)先原則。調(diào)度算法必須滿足所有客觀約束條件，同時盡量滿足用戶的主觀優(yōu)先原則或使用習(xí)慣。

(3)調(diào)度規(guī)模與調(diào)度性能。在一定調(diào)度規(guī)模下，調(diào)度算法必須在要求的時間內(nèi)生成有效的調(diào)度方案。

(4)目標(biāo)函數(shù)與結(jié)果評估。目標(biāo)函數(shù)應(yīng)體現(xiàn)分配方案對需求的滿足程度及其他用戶關(guān)注的指標(biāo)。

由于站網(wǎng)資源種類繁多，性能各異，為了聚焦實(shí)際應(yīng)用，本文的研究內(nèi)容適用的對象有具備配套鏈路(變頻器、解調(diào)器)及記錄設(shè)備的常規(guī)拋物面天線接收站、測控站或接收測控一體化站，包括固定站和機(jī)動站。同時，本文的研究內(nèi)容亦可對其他類型測控數(shù)傳資源調(diào)度提供參考。

站網(wǎng)資源調(diào)度的約束與需求可以分為客觀約束和主觀要求兩類。

站網(wǎng)資源調(diào)度主要關(guān)注地面資源的使用約束，包括規(guī)劃時間約束、可達(dá)性約束、任務(wù)切換時間約束、任務(wù)能力匹配約束、地面站資源沖突約束、任務(wù)優(yōu)先級約束、遙測任務(wù)約束、數(shù)傳任務(wù)約束、最小可用弧段約束和弧段完整性約束。

在實(shí)際應(yīng)用中，除了上述地面資源約束外，還需考慮星上載荷的約束，例如連續(xù)工作時長、開關(guān)機(jī)時間、衛(wèi)星天線切換時間等約束。

主觀要求包括任務(wù)需求要求、資源使用負(fù)載均衡要求、弧段能力要求和衛(wèi)星任務(wù)均衡性要求。

3 問題建模

站網(wǎng)調(diào)度問題的特性在于調(diào)度過程中必須滿足的所有客觀約束和盡可能滿足的所有主觀使用要求，使得站網(wǎng)調(diào)度問題的解空間不具有連續(xù)性。因此，現(xiàn)有的通用算法不能直接用于這類解空間離散問題的尋優(yōu)，需要針對所有約束條件建立約束滿足模型解決解空間離散的問題。

3.1 約束滿足模型

對于約束條件較多的站網(wǎng)調(diào)度問題，可以預(yù)見直接使用優(yōu)化算法將導(dǎo)致算法的適配過于繁復(fù)。對于元啟發(fā)式算法，需要將隨機(jī)搜索范圍適配至所有約束范圍內(nèi)，這將導(dǎo)致算法鄰域結(jié)構(gòu)設(shè)計的復(fù)雜化，甚至導(dǎo)致算法無法適配。以遺傳算法為例，需要解決編碼方式和編碼對象。為保證種群中的下一代在遺傳或變異后仍然滿足模型中所有約束條件，需要設(shè)計對應(yīng)的遺傳算法編碼方式和編碼對象，因此優(yōu)化算法的適配需要首先建立約束滿足模型。通過建立約束滿足模型，可以使得算法的搜索區(qū)域永遠(yuǎn)位于問題的解空間內(nèi)，從而使得優(yōu)化算法的適配成為可能。

約束滿足模型根據(jù)所有需求與約束條件，設(shè)計多種啟發(fā)式規(guī)則，建立了以弧段處理順序?yàn)轵?qū)動的確定性啟發(fā)式算法。通過啟發(fā)式規(guī)則，算法的搜索空間被限制在站網(wǎng)調(diào)度問題的解空間內(nèi)，對于確定的弧段的處理順序，通過啟發(fā)式算法可以得到確定的結(jié)果和目標(biāo)函數(shù)；通過改變弧段的處理順序，實(shí)現(xiàn)站網(wǎng)調(diào)度問題的全局搜索。

3.2 鄰域結(jié)構(gòu)設(shè)計

鄰域構(gòu)建直接決定了算法的搜索效率，本算法的鄰域設(shè)計結(jié)構(gòu)參考了經(jīng)典旅行商問題(Traveling Salesman Problem，TSP)的常用鄰域結(jié)構(gòu)設(shè)計。TSP問題和尋找最優(yōu)弧段處理順序問題具有一定程度的相似性。TSP問題是賦權(quán)漢密爾頓(Hamiltonian)回路最小化問題(回到起點(diǎn))，尋找最優(yōu)弧段處理順序問題可以抽象為賦權(quán)漢密爾頓路徑最小化問題(無需回到起點(diǎn))。TSP問題求解的是最優(yōu)路徑，在n個節(jié)點(diǎn)的集合中，選擇一條經(jīng)過每個節(jié)點(diǎn)各一次，最終再回到起點(diǎn)的路徑，要求路線的總距離或開銷最小。對于多星多站調(diào)度問題也可以抽象成類似的問題：衛(wèi)星的弧段組成一個序列，尋找序列的最佳排序方式(無需回到起點(diǎn))使得算法在該弧段處理順序下得到的調(diào)度方案在滿足約束的條件下目標(biāo)函數(shù)最優(yōu)。

在TSP問題中，任意兩點(diǎn)的距離或開銷是一定的，不會因?yàn)榻?jīng)過某節(jié)點(diǎn)的不同次序使得該節(jié)點(diǎn)與另一節(jié)點(diǎn)的距離或開銷改變。該問題的領(lǐng)域結(jié)構(gòu)通常采用交換序列中兩節(jié)點(diǎn)順序的方式進(jìn)行領(lǐng)域搜索。

在站網(wǎng)資源調(diào)度問題中，衛(wèi)星的某一弧段一旦被選定，可能會對其他衛(wèi)星的弧段可用性造成影響，該影響的結(jié)果可能使得受影響的弧段不可用或弧段因沖突消解改變了長度。對于某一顆衛(wèi)星，尋找其弧段的最優(yōu)排列順序和TSP問題相似，但對于多星來講，衛(wèi)星的處理順序同樣可能對每顆衛(wèi)星的弧段造成影響。多星多站調(diào)度問題可以看作是一個兩層的賦權(quán)漢密爾頓路徑最小化問題：一層是衛(wèi)星處理序列，一層是各衛(wèi)星的弧段處理序列。

根據(jù)站網(wǎng)資源調(diào)度的需求，用戶的站網(wǎng)資源使用申請分為應(yīng)急、重要、普通三類，其中重要和普通類站網(wǎng)資源使用申請屬于常規(guī)任務(wù)申請，需要通過算法為其分配使用方案。因此在鄰域設(shè)計上，本文根據(jù)任務(wù)的優(yōu)先程度，依據(jù)任務(wù)優(yōu)先級、衛(wèi)星優(yōu)先級固化邏輯上的衛(wèi)星處理序列。僅針對各衛(wèi)星的弧段處理序列設(shè)計鄰域交換模式，以改變某衛(wèi)星的弧段排序方式實(shí)現(xiàn)鄰域交換。衛(wèi)星序列層次結(jié)構(gòu)示意如圖1所示。改變衛(wèi)星弧段排序的方式可以采用序列交換、多點(diǎn)隨機(jī)排序、交叉排序等方式。

圖1 衛(wèi)星序列層次結(jié)構(gòu)Fig.1 Hierarchy of satellites’ sequence

根據(jù)優(yōu)先級約束的要求，將同一顆衛(wèi)星優(yōu)先級為重要的弧段和優(yōu)先級為普通的弧段視為兩顆邏輯衛(wèi)星弧段進(jìn)行排序，使得優(yōu)先級為重要的弧段優(yōu)先進(jìn)行分配。對于相同優(yōu)先級的內(nèi)部用戶衛(wèi)星和外部商用衛(wèi)星，衛(wèi)星處理序列中內(nèi)部用戶衛(wèi)星在外部商用衛(wèi)星前列，使得同優(yōu)先級情況下內(nèi)部用戶衛(wèi)星任務(wù)優(yōu)先進(jìn)行分配。

在每個邏輯衛(wèi)星弧段排序中，用戶的站網(wǎng)資源使用申請包括指定圈次模式和指定時長模式。其中指定時長模式下弧段的分配由資源調(diào)度算法決定，而指定圈次模式下，用戶已對確定的弧段提出申請，因此可以認(rèn)為同優(yōu)先級下，指定圈次模式的申請應(yīng)優(yōu)先進(jìn)行分配。同時根據(jù)弧段能力要求，具備全任務(wù)能力的弧段優(yōu)先于只具備部分能力的弧段分配。每個邏輯衛(wèi)星弧段排序如圖2所示。

圖2 弧段序列和鄰域結(jié)構(gòu)Fig.2 Structure of arcs’ sequence and neighborhoods

3.3 模型表示

T：資源調(diào)度時間范圍T=[TS,TE]，僅對TS至TE時間范圍內(nèi)的可用資源和弧段進(jìn)行調(diào)度。

S：過境衛(wèi)星集合S={s1,s2,…,sn}。

A：地面站天線集合A={a1,a2,…,am}。

W：地面站天線權(quán)重集合W={w1,w2,…,wm}。

R：站網(wǎng)資源使用需求集合R={r1,r2,…,rz}，對于集合R中的任意需求ri={ridi,sidi,rwi,rmi,tmi,Dtci,Ddti,Tsi,Tei}，其中ridi為需求id，sidi為申請衛(wèi)星id，rwi為需求的權(quán)重，rmi為需求模式(指定時長/指定圈次模式)，tmi為需求的任務(wù)類型(測控/數(shù)傳/測控+數(shù)傳)，Dtci為需求測控任務(wù)時長，Ddti為需求數(shù)傳任務(wù)時長，Tsi和Tei分別為需求任務(wù)開始時間和結(jié)束時間。

Td：任務(wù)切換時間，即地面站資源在兩個相鄰任務(wù)間需要的常量任務(wù)切換準(zhǔn)備時間。

Tl：弧段長度閾值，低于閾值的弧段不進(jìn)行任務(wù)分配。

站網(wǎng)資源調(diào)度模型需要滿足的主要地面資源約束條件可以表示為

(1)

(2)

(3)

(4)

(5)

式(1)表示同一地面站天線兩個相鄰可用時段的間隔必須滿足任務(wù)切換時間約束，且同一天線及配套設(shè)備不能同時對兩顆及以上衛(wèi)星執(zhí)行任務(wù)；式(2)表示僅對調(diào)度時間范圍內(nèi)的資源進(jìn)行規(guī)劃；式(3)表示所有分配執(zhí)行任務(wù)的弧段必須滿足最小弧段長度約束；式(4)表示分配給測控或數(shù)傳任務(wù)的弧段必須具備相應(yīng)能力；式(5)表示執(zhí)行數(shù)傳任務(wù)時，該衛(wèi)星不能同時執(zhí)行其他數(shù)傳任務(wù)。

3.4 目標(biāo)函數(shù)

根據(jù)用戶需求，本文目標(biāo)函數(shù)用以評估調(diào)度方案對用戶申請的滿足程度以及對地面站資源分配均衡性的評價。由于地面資源調(diào)度的目的為盡量滿足用戶測控和數(shù)傳任務(wù)的需求，因此僅在同樣滿足用戶需求的情況下，比較兩組調(diào)度方案的資源分配均衡性優(yōu)劣才有意義。因此，目標(biāo)函數(shù)設(shè)計為兩部分：一是用戶申請的滿足程度，用整數(shù)位表示，綜合考慮任務(wù)優(yōu)先級、優(yōu)先級權(quán)重、需求時長、分配時長，計算方案對所有申請的整體滿足情況；二是資源負(fù)載均衡使用情況評估，用小數(shù)位表示，計算當(dāng)前分配方案下對各地面資源的使用情況，依據(jù)地面站天線權(quán)重評估分配方案。

算法對于最大化目標(biāo)函數(shù)F的定義如下：

max:F=f1(R)+f2(A)。

(6)

式中：f1(R)為需求滿足程度，用以標(biāo)識方案對需求的滿足程度；f2(A)為資源使用情況評估，用以標(biāo)識方案的負(fù)載均衡分配評價指標(biāo)；R為用戶的需求集合，需求數(shù)量為z，方案中分配給需求ri的測控任務(wù)總時長和數(shù)傳任務(wù)總時長分別記為Ttci和Tdti。需求ri的滿足率Pi為

(7)

需求ri的權(quán)重記為rwi,則需求滿足程度f1(R)可由下式所得：

(8)

記地面站天線aj的分配時長為Taj，則

(9)

目標(biāo)函數(shù)體現(xiàn)了對方案優(yōu)劣程度的評估，方案對用戶申請的滿足程度(整數(shù)部分)決定了方案的優(yōu)劣，在滿足程度相同的情況下比較方案對地面資源的使用負(fù)載均衡情況(小數(shù)部分)。

4 算法設(shè)計

本文提出了一種組合式站網(wǎng)調(diào)度算法，算法由通用的遺傳算法和本文提出的啟發(fā)式站網(wǎng)調(diào)度算法組成，嵌套使用。其中啟發(fā)式算法用于計算一個輸入(衛(wèi)星弧段序列，即弧段分配判斷的先后順序)下的調(diào)度方案、目標(biāo)函數(shù)值，而智能算法則根據(jù)需求目標(biāo)函數(shù)結(jié)果在衛(wèi)星弧段的所有可能序列中尋找最優(yōu)排序方式。

通過啟發(fā)式站網(wǎng)調(diào)度算法，對于確定的衛(wèi)星和弧段的處理順序，得到確定的結(jié)果和目標(biāo)函數(shù)；通過智能優(yōu)化算法，搜索最優(yōu)的衛(wèi)星和弧段的處理順序；同時，與算法無直接關(guān)聯(lián)的數(shù)據(jù)處理在預(yù)處理部分解決。站網(wǎng)資源調(diào)度的簡要流程圖如圖3所示。

圖3 站網(wǎng)資源調(diào)度簡要流程圖Fig.3 Flow chart of ground-station resource scheduling

4.1 預(yù)處理

根據(jù)預(yù)處理工作的內(nèi)容和工作順序，分為三級預(yù)處理：需求及資源匯總預(yù)處理、可見窗口預(yù)處理以及弧段標(biāo)注預(yù)處理。

需求及資源匯總預(yù)處理匯總所有用戶需求，得到任務(wù)規(guī)劃衛(wèi)星集合、任務(wù)規(guī)劃起止時間、優(yōu)先級、需求類型和需求時長等信息，同時也匯總所有參與調(diào)度的資源信息，包括可用的地面站天線、天線能力信息、天線可用時段，最小可用弧段長度等信息。

可見窗口預(yù)處理根據(jù)衛(wèi)星與各地面站天線的可見時間窗口，為每個弧段建立索引維護(hù)與該弧段在時間上有重疊的弧段，便于資源調(diào)度過程中弧段的沖突監(jiān)測與消解。通過建立索引方式可避免資源調(diào)度沖突檢測頻繁的弧段遍歷和判斷，提高算法效率，且索引一次計算，多次使用。

弧段標(biāo)注預(yù)處理在衛(wèi)星弧段標(biāo)注其連續(xù)升/降軌周期序號、弧段序號、對應(yīng)的需求id，根據(jù)弧段對應(yīng)地面站天線能力，標(biāo)注測控任務(wù)能力和數(shù)傳任務(wù)能力，供站網(wǎng)資源調(diào)度算法使用。

4.2 啟發(fā)式算法

本文提出的啟發(fā)式算法為基于貪心思想的確定性算法，計算一個衛(wèi)星序列和一組衛(wèi)星弧段序列輸入下的目標(biāo)函數(shù)值和結(jié)果。算法根據(jù)衛(wèi)星序列依次選擇衛(wèi)星開始規(guī)劃。依據(jù)弧段連續(xù)升/降軌周期序號，以周期為單位選擇相同周期的弧段進(jìn)行分配，以滿足衛(wèi)星任務(wù)的均衡性。在每個周期，按照該衛(wèi)星的弧段序列，依次判斷弧段對應(yīng)的需求是否已滿足，若不滿足且弧段可分配時，分配弧段，并依據(jù)該弧段對應(yīng)的測控或數(shù)傳需求，決定是否對與該弧段時間交叉的弧段進(jìn)行數(shù)傳衛(wèi)星弧段沖突消解。依次進(jìn)行該周期內(nèi)的弧段分配，直至滿足該衛(wèi)星任務(wù)均衡性要求。隨后進(jìn)入下一周期，以此類推。當(dāng)該衛(wèi)星所有周期均滿足衛(wèi)星任務(wù)均衡性要求后(或無弧段可分配)，整合所有該衛(wèi)星未分配弧段，逐條進(jìn)行分配，直至遍歷完所有弧段。

完成一顆衛(wèi)星的弧段分配后，按衛(wèi)星序列進(jìn)入下一顆衛(wèi)星進(jìn)行分配，以此類推，直至完成所有衛(wèi)星任務(wù)分配。啟發(fā)式算法流程如圖4所示。

4.3 遺傳算法

本文站網(wǎng)資源調(diào)度組合算法的步驟如下：

Step1 初始化算法控制參數(shù)，根據(jù)預(yù)處理輸入的衛(wèi)星序列，隨機(jī)生成種群數(shù)量個衛(wèi)星弧段序列，隨機(jī)僅限于弧段鄰域交換范圍內(nèi)。

Step2 對當(dāng)前種群內(nèi)每個個體(各衛(wèi)星弧段序列)調(diào)用啟發(fā)式算法。

Step2.1 根據(jù)遺傳算法輸入的衛(wèi)星序列，依次選擇衛(wèi)星；

Step2.6 判斷周期內(nèi)分配弧段數(shù)是否滿足衛(wèi)星任務(wù)均衡性要求，不滿足則選擇待處理隊列中下一弧段，進(jìn)入Step 2.3；滿足則進(jìn)入Step 2.2；

Step2.7 清空待處理隊列，匯總該衛(wèi)星弧段序列中所有未分配弧段并順序加入待處理隊列，順序選擇隊列中弧段進(jìn)行調(diào)度分配，直至完成該衛(wèi)星所有弧段的分配，進(jìn)入Step 2.1；

Step2.8 完成所有衛(wèi)星的弧段分配后，輸出調(diào)度方案與目標(biāo)函數(shù)。

Step3 將適應(yīng)度最高的個體作為精英解，直接進(jìn)入下一代種群。

Step4 通過輪盤賭方式依次選擇個體進(jìn)入候選解。

Step5 按照交叉概率進(jìn)行交叉操作，得交叉后的所有候選解。

Step6 根據(jù)變異概率對候選個體進(jìn)行變異操作，與精英解組成下一代種群，種群代數(shù)+1。

Step7 判斷種群代數(shù)是否滿足終止條件，滿足則進(jìn)入Step 8，否則進(jìn)入Step 2。

Step8 輸出當(dāng)代種群最優(yōu)方案和相應(yīng)的目標(biāo)函數(shù)值。

本文組合算法中，遺傳算法為啟發(fā)式算法的上層調(diào)用算法，為啟發(fā)式算法提供輸入。遺傳算法根據(jù)弧段序列結(jié)構(gòu)和鄰域交換范圍，在允許的衛(wèi)星弧段排序方式中進(jìn)行搜索，通過調(diào)用啟發(fā)式算法得到一組衛(wèi)星弧段排序的目標(biāo)函數(shù)值，并通過交叉和變異的方法實(shí)現(xiàn)尋優(yōu)。

遺傳算法采用實(shí)數(shù)編碼方式，以弧段排序序號為編碼對象，以啟發(fā)式算法輸出的目標(biāo)函數(shù)作為適應(yīng)度函數(shù)，以輪盤賭方式作為選擇算子，并使用精英策略將每一代中適應(yīng)度最大的個體直接選擇至下一代。在衛(wèi)星弧段序列的每一個弧段鄰域交換范圍內(nèi)，采用次序交叉[11](Order Crossover)作為交叉算子，對其分別進(jìn)行交叉操作。算法采用單點(diǎn)置頂?shù)姆绞綄?shí)現(xiàn)變異，按照變異概率選擇需要進(jìn)行變異的個體，隨機(jī)選擇該個體的一個弧段序號，并將該序號置入其鄰域交換范圍中隊列頂端。單點(diǎn)置頂變異示意圖如圖5所示。

圖5 遺傳算法單點(diǎn)置頂變異示意圖Fig.5 Diagram of single gene mutation of GA

5 仿真驗(yàn)證

為了驗(yàn)證本文提出的測控數(shù)傳一體化站網(wǎng)資源調(diào)度算法的性能，建立仿真模型進(jìn)行驗(yàn)證。仿真驗(yàn)證環(huán)境為Win7 32位系統(tǒng)，CPU為Core i3-4160，3.60 GHz雙核，4 GB RAM，仿真工具為Matlab R2009a。

算法設(shè)置種群個體數(shù)目為30，交叉概率為0.8，變異概率為0.1，遺傳算法終止條件為進(jìn)化30代。設(shè)置任務(wù)切換時間Td=240 s，弧段長度閾值Tl=180 s。

本文以真實(shí)衛(wèi)星軌道為基礎(chǔ)，設(shè)計了10顆存在不同程度沖突的衛(wèi)星軌道參數(shù)用于仿真驗(yàn)證，通過STK計算所有衛(wèi)星一周內(nèi)的過境弧段，對每顆衛(wèi)星的需求設(shè)置為指定時長模式，每個需求要求全能力弧段總時長10 000 s。

在不同的場景下，站網(wǎng)資源調(diào)度的規(guī)模如圖6所示。

圖6 弧段數(shù)量與應(yīng)用場景的關(guān)系Fig.6 The relationship between the number of arcs and application scenarios

從圖6可以看出，弧段數(shù)量，即資源調(diào)度的問題規(guī)模，隨衛(wèi)星及天線數(shù)量的增加呈線性增長，因此需要評估實(shí)際應(yīng)用中問題規(guī)模對算法性能的影響。經(jīng)過50種衛(wèi)星-天線數(shù)量組合，各取3次仿真時間均值，得到不同場景下，本文啟發(fā)式算法的運(yùn)算性能曲線，如圖7所示?？梢钥闯觯?0星10天線7天約2 800弧段的仿真場景下，啟發(fā)式算法的時間消耗在當(dāng)前仿真環(huán)境下仍處于可接受范圍內(nèi)。

圖7 啟發(fā)式算法運(yùn)行時間與應(yīng)用場景的關(guān)系Fig.7 The relationship between time consumptions of the heuristic algorithm and application scenarios

由于實(shí)際應(yīng)用中通常以一天為規(guī)劃時間范圍，因此本文使用6組場景一天的衛(wèi)星過境弧段驗(yàn)證本文的測控數(shù)傳一體化站網(wǎng)資源調(diào)度算法效果。測控數(shù)傳一體化站網(wǎng)資源調(diào)度算法為遺傳算法與本文啟發(fā)式算法的組合使用,對比算法選用本文的啟發(fā)式算法，該算法核心為貪婪算法，且該算法針對用戶需求進(jìn)行了針對性設(shè)計了啟發(fā)式規(guī)則，因此調(diào)度效果要優(yōu)于常規(guī)的基于優(yōu)先級的貪婪算法。算法性能對比如表1所示。

表1 算法性能對比Tab.1 Performance comparison between proposed algorithm and the heuristic algorithm

以表中分配弧段數(shù)量與弧段總數(shù)量的比值為調(diào)度成功率，對比6種場景下兩種算法的調(diào)度結(jié)果，使用本文的組合式算法調(diào)度成功率較啟發(fā)式算法平均提高了22.3%，目標(biāo)函數(shù)值平均提高了11.8%。

可以看出，本文的啟發(fā)式算法與遺傳算法的組合使用在各仿真場景下，均能有效提高需求的滿足程度和設(shè)備的負(fù)載均衡要求，其中4個場景的分配方案可完全滿足用戶需求。從弧段的分配數(shù)量也可看出，對比傳統(tǒng)的貪婪算法，本文的測控數(shù)傳一體化站網(wǎng)資源調(diào)度算法可有效提高資源調(diào)度成功率。

6 結(jié) 論

本文針對未來測控和數(shù)傳任務(wù)統(tǒng)一進(jìn)行站網(wǎng)資源調(diào)度的發(fā)展趨勢，提出了一種測控數(shù)傳一體化的站網(wǎng)資源調(diào)度算法。算法針對測控數(shù)傳一體化實(shí)際應(yīng)用需求，以天線及配套鏈路為站網(wǎng)資源的調(diào)度粒度，建立了約束滿足模型并設(shè)計了相應(yīng)的啟發(fā)式算法，通過定義鄰域結(jié)構(gòu)并采用遺傳算法和啟發(fā)式算法組合使用的方法，在仿真實(shí)驗(yàn)中驗(yàn)證了本文算法的尋優(yōu)能力。仿真結(jié)果顯示，在多種仿真場景下，本文組合式算法可有效提高資源調(diào)度的成功率以及任務(wù)需求的滿足程度。