通信衛(wèi)星動態(tài)調(diào)度問題研究

近年來，在抗震救災(zāi)、遠洋貿(mào)易、反恐維穩(wěn)等通信中暴露出我國衛(wèi)星通信保障能力有限、衛(wèi)星通信資源調(diào)度緩慢等問題，衛(wèi)星通信在全球通信、國防通信、應(yīng)急通信以及邊海疆通信中的重要作用日益突出。國家高度重視并加快了專用衛(wèi)星通信系統(tǒng)的建設(shè)與發(fā)展，我國在軌通信衛(wèi)星數(shù)量，天線波束和轉(zhuǎn)發(fā)器類型、帶寬、功率、工作頻段，多址接入技術(shù)及地面終端類型、性能等將大幅提升，衛(wèi)星通信保障能力將進一步增強。

通信衛(wèi)星調(diào)度是指衛(wèi)星調(diào)度中心根據(jù)資源狀態(tài)及任務(wù)請求，依據(jù)任務(wù)優(yōu)先級、時間窗口需求及資源任務(wù)匹配規(guī)則，以完成任務(wù)的優(yōu)先級之和最大為優(yōu)化目標(biāo)，科學(xué)合理地利用衛(wèi)星通信資源。當(dāng)前多樣化任務(wù)及應(yīng)急任務(wù)對衛(wèi)星通信應(yīng)用提出了更高的要求，現(xiàn)有的人工調(diào)度方法無法解決大規(guī)模動態(tài)調(diào)度的突出問題。因此，通過研究建立通信衛(wèi)星動態(tài)調(diào)度系統(tǒng)，能夠有效提高衛(wèi)星通信資源的利用效率。

一、通信衛(wèi)星動態(tài)調(diào)度框架

通信衛(wèi)星調(diào)度問題主要包括衛(wèi)星通信資源、地面站資源、任務(wù)需求及調(diào)度約束條件等，通過通信任務(wù)場景的假設(shè)，對于上述資源及約束條件進行數(shù)學(xué)抽象，根據(jù)調(diào)度策略生成目標(biāo)優(yōu)化函數(shù)，建立調(diào)度模型，最后進行優(yōu)化算法求解。通信衛(wèi)星調(diào)度的目標(biāo)就是要選擇需要保障的通信任務(wù)、確定完成通信保障的衛(wèi)星轉(zhuǎn)發(fā)器資源及任務(wù)執(zhí)行時間窗口。對于多顆衛(wèi)星、多種轉(zhuǎn)發(fā)器、多個通信任務(wù)需求的情況下，如何生成一個優(yōu)化的衛(wèi)星資源調(diào)度方案，合理分配衛(wèi)星資源保障更多的通信任務(wù)，對充分發(fā)揮衛(wèi)星通信系統(tǒng)效能是至關(guān)重要的。通信衛(wèi)星動態(tài)調(diào)度總體框架如圖1所示，通信衛(wèi)星動態(tài)調(diào)度主要考慮新任務(wù)插入和資源變化兩種擾動。

（1）新增任務(wù)而導(dǎo)致的動態(tài)調(diào)度

通信衛(wèi)星調(diào)度過程中，新增任務(wù)的到達需要對初始調(diào)度方案進行調(diào)整，按照優(yōu)先級高低盡可能滿足所有任務(wù)需求，尤其當(dāng)新增任務(wù)優(yōu)先級相對比較高時，如果在資源有限且不能滿足所有任務(wù)需求的情況下進行重新調(diào)度，那么需要中斷某些低優(yōu)先級任務(wù)的調(diào)度，滿足新增高優(yōu)先級任務(wù)的需求。

（2）通信衛(wèi)星資源狀態(tài)變化導(dǎo)致的動態(tài)調(diào)度

通信衛(wèi)星調(diào)度過程中，通信資源狀態(tài)變化是不確定的。衛(wèi)星通信資源狀態(tài)主要變化情況是衛(wèi)星故障或者特殊情況下被敵方干擾，導(dǎo)致可用衛(wèi)星通信資源的減少，如果衛(wèi)星通信資源發(fā)生重大變化，則初始調(diào)度方案是無法繼續(xù)執(zhí)行的，需要進行初始調(diào)度方案調(diào)整。通常情況是資源的有限性造成了多任務(wù)調(diào)度問題的困難，因此對于衛(wèi)星通信資源增加情況，即使存在部分任務(wù)沒有被調(diào)度的情況，可以用初始調(diào)度模型對新任務(wù)與新資源重新進行求解匹配。

二、通信衛(wèi)星動態(tài)調(diào)度流程

通信衛(wèi)星動態(tài)調(diào)度流程如圖2所示，通過對任務(wù)需求和衛(wèi)星資源狀態(tài)分析，為調(diào)度模型求解進行數(shù)據(jù)準(zhǔn)備，確定可以滿足通信任務(wù)需求的衛(wèi)星及轉(zhuǎn)發(fā)器資源。如果某個通信任務(wù)需求具有滿足其要求的衛(wèi)星通信資源（通過分析任務(wù)所屬地面終端類型、所需通信資源），則需要計算該通信需求的可見時間窗口（衛(wèi)星同地面站的可見時間段，主要是衛(wèi)星點波束覆蓋范圍限制）。只有當(dāng)通信需求同時具有可用資源和可用時間窗口，才認為該通信任務(wù)需求可能被完成，需要通過按照優(yōu)先級調(diào)度原則來確定其是否被執(zhí)行及執(zhí)行該通信任務(wù)的衛(wèi)星資源。然后，根據(jù)確定的通信需求、時間窗口等基本數(shù)據(jù)，建立通信衛(wèi)星調(diào)度模型，采用優(yōu)化算法對模型進行求解，分配通信任務(wù)的資源需求和時間窗口，獲得初始調(diào)度方案。

在初始方案執(zhí)行過程中，可能會出現(xiàn)各種擾動因素。需要根據(jù)擾動類型，對問題進行重新建模求解，以滿足擾動需求。如果沒有擾動發(fā)生，則執(zhí)行初始方案；當(dāng)有擾動發(fā)生時（主要指衛(wèi)星資源狀態(tài)變化或者新任務(wù)插入），則作相應(yīng)的方案調(diào)整，這是一個根據(jù)實際需要重復(fù)執(zhí)行的過程，當(dāng)擾動發(fā)生時，如新任務(wù)插入，則需對新增任務(wù)進行調(diào)度預(yù)處理，即進行數(shù)據(jù)分析工作。

三、通信衛(wèi)星動態(tài)調(diào)度模型分析

動態(tài)約束滿足問題（Dynamic Constraint Satisfaction Problems，DCSP）能夠很好地描述智能領(lǐng)域的調(diào)度、規(guī)劃和組合等復(fù)雜問題，適用于表示和求解大規(guī)模組合優(yōu)化問題，動態(tài)體現(xiàn)在變量、變量值域和約束條件的變化，如圖3所示。根據(jù)動態(tài)變化狀態(tài)，動態(tài)約束滿足問題分為變量狀態(tài)變化、約束條件動態(tài)變化和兩者均有的混合變化。

調(diào)度問題一直是系統(tǒng)工程中的難點熱點問題，通信衛(wèi)星動態(tài)調(diào)度包括資源約束、時間窗口約束等通常的約束條件，還包括地面終端類型及任務(wù)時效性等復(fù)雜約束條件。通信衛(wèi)星調(diào)度問題可視為一個基于DCSP的優(yōu)化問題，可以將通信衛(wèi)星動態(tài)調(diào)度問題中的任務(wù)、衛(wèi)星資源與時間窗口、約束規(guī)則分別映射到DCSP中的變量集合、變量集合值域以及限制變量取值的約束集合。DCSP求解目標(biāo)是確保原調(diào)度方案與新調(diào)度方案之間空間距離變化最小的情況下，完成任務(wù)優(yōu)先級之和最大。

3.1新增任務(wù)的動態(tài)調(diào)度模型

當(dāng)增加或減少CSP問題的變量數(shù)目時，將引發(fā)原問題發(fā)生改變，使之變成一個新的CSP問題。對于此類問題，需要考慮解的穩(wěn)定性，即獲得的初始解盡量能夠繼續(xù)使用。例如：調(diào)度問題中，用戶在某時刻的需求是m，CSP根據(jù)用戶需求進行求解得到了調(diào)度方案，在下一時刻用戶的需求發(fā)生變化，又增加了n個需求，如果CSP在此時對該問題進行重新求解，其前面的解決方案會遭到破壞，這對于調(diào)度問題是很不利的?；谛氯蝿?wù)到達的通信衛(wèi)星調(diào)度模型就可以視為增加變量數(shù)目的CSP問題，即基于數(shù)量變化的DCSP問題。

基于新任務(wù)到達的動態(tài)調(diào)度可以簡單表示為如圖4所示，新任務(wù)的到達造成了變集合任務(wù)數(shù)量在tn時刻發(fā)生變化，約束集合新增了動態(tài)約束條件，變量的值域集合即衛(wèi)星資源沒有發(fā)生變化，tn時刻需要進行最小化地調(diào)整任務(wù)到資源的映射關(guān)系。

3.3動態(tài)調(diào)度遵循的原則

在動態(tài)調(diào)度過程中，必須充分考慮約束規(guī)則的變化，最大化保障任務(wù)需求。對于動態(tài)調(diào)度要遵循以下原則。

（1）優(yōu)先級調(diào)度原則

在通信任務(wù)保障過程中，根據(jù)調(diào)度優(yōu)化的目標(biāo)，要按照優(yōu)先級高低進行調(diào)度，高優(yōu)先級的任務(wù)必須優(yōu)先保障完成。針對某些突發(fā)事件帶來的應(yīng)急任務(wù)，是要求優(yōu)先保障完成的，以確保突發(fā)事件的情況處置能力。在優(yōu)先保障高優(yōu)先級任務(wù)的條件下，最大化保障時效性強的低優(yōu)先級通信任務(wù)。

（2）方案變化最小原則

由于擾動因素導(dǎo)致初始調(diào)度方案進行整時，應(yīng)確保調(diào)整后方案與初始方案相比變化最小。對于衛(wèi)星資源來說，衛(wèi)星通信應(yīng)用過程復(fù)雜，工作指令需要專門的時間和設(shè)備進行上傳，大規(guī)模改變衛(wèi)星指令浪費通信資源和時間；對于用戶來說，初始調(diào)度方案確定后，可能相關(guān)用戶根據(jù)調(diào)度方案中的需求安排，制定了相應(yīng)的工作計劃，如果對任務(wù)規(guī)劃進行大規(guī)模調(diào)整，必定會影響用戶的下一步工作和決策，導(dǎo)致較大的損失，故應(yīng)該將這種影響降到最低。

（3）快速調(diào)整原則

在實際應(yīng)用中，在通信任務(wù)或衛(wèi)星資源發(fā)生變化時，需要對初始調(diào)度方案進行動態(tài)調(diào)整，對于方案調(diào)整的時間性要求較高，需要在原有方案基礎(chǔ)上進行快速調(diào)整，以快速滿足資源與任務(wù)變化的需求。

四、結(jié)語

通信衛(wèi)星調(diào)度問題屬于航天領(lǐng)域亟需解決的重點問題之一，對于該問題的研究具有重要意義，能夠有效提高衛(wèi)星通信系統(tǒng)的服務(wù)保障能力和資源利用效率。通過對通信衛(wèi)星動態(tài)調(diào)度問題的研究，利用優(yōu)化算法生成動態(tài)調(diào)度方案，可以為實際衛(wèi)星通信規(guī)劃方案提供參考依據(jù)，為解決星上通信資源和任務(wù)需求的供需矛盾提供技術(shù)支持。