靳 鵬，李 康，*

（1.合肥工業(yè)大學(xué)管理學(xué)院，安徽 合肥 230009；2.合肥工業(yè)大學(xué)過程優(yōu)化與智能決策教育部重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230009）

0 引 言

遙感衛(wèi)星能夠快速準(zhǔn)確地進(jìn)行對地觀測以獲取地表信息，在國防建設(shè)、環(huán)境災(zāi)害防治等領(lǐng)域發(fā)揮重要作用［1-2］。衛(wèi)星任務(wù)規(guī)劃就是在滿足相關(guān)約束的前提下，將待觀測任務(wù)分配給最合適的衛(wèi)星，使得規(guī)劃目標(biāo)最優(yōu)［3］。衛(wèi)星任務(wù)規(guī)劃問題已經(jīng)被證明為非確定性多項(xiàng)式難（non deterministic polynomial hard，NP-hard）問題［4］。

傳統(tǒng)的衛(wèi)星地面任務(wù)規(guī)劃模式存在動態(tài)響應(yīng)不及時、過分依賴地面資源、時效性差等問題，難以高效開展衛(wèi)星任務(wù)規(guī)劃［5］。隨著衛(wèi)星技術(shù)的發(fā)展，衛(wèi)星已經(jīng)具有一定的自主規(guī)劃能力，衛(wèi)星之間通過協(xié)同進(jìn)行自主任務(wù)規(guī)劃，能有效提高衛(wèi)星任務(wù)規(guī)劃的效率。在此基礎(chǔ)上，如何進(jìn)行有效的衛(wèi)星資源調(diào)度和任務(wù)分配是衛(wèi)星規(guī)劃的重點(diǎn)［6-7］。

衛(wèi)星任務(wù)規(guī)劃問題多采用集中式架構(gòu)進(jìn)行處理。文獻(xiàn)［8-10］使用蟻群算法等啟發(fā)式算法進(jìn)行規(guī)劃，可以在短時間內(nèi)獲得規(guī)劃方案，但算法穩(wěn)定性較差。文獻(xiàn)［11］提出了一種星地聯(lián)合的運(yùn)行機(jī)制進(jìn)行任務(wù)規(guī)劃，能有效提高衛(wèi)星對非預(yù)期任務(wù)的響應(yīng)能力。文獻(xiàn)［12］采用模糊神經(jīng)網(wǎng)絡(luò)進(jìn)行衛(wèi)星任務(wù)規(guī)劃。上述集中式架構(gòu)方式雖然實(shí)現(xiàn)較為簡單，但是存在任務(wù)響應(yīng)能力差、執(zhí)行效率低等諸多缺陷［13］。分布式架構(gòu)以其通信分散、魯棒性好等優(yōu)點(diǎn)成為衛(wèi)星任務(wù)規(guī)劃的有效架構(gòu)方式，文獻(xiàn)［14-16］建立了分布式任務(wù)規(guī)劃求解框架，并通過實(shí)驗(yàn)表明了分布式架構(gòu)的優(yōu)勢。文獻(xiàn)［17-20］采取遺傳算法等啟發(fā)式算法進(jìn)行任務(wù)規(guī)劃，但僅適用于任務(wù)規(guī)模小并且需求簡單的衛(wèi)星任務(wù)規(guī)劃。合同網(wǎng)是解決分布式任務(wù)規(guī)劃的一種有效方法［21-22］，因其分配效率高、適應(yīng)動態(tài)環(huán)境強(qiáng)等特點(diǎn)在分布式任務(wù)規(guī)劃中得到廣泛應(yīng)用。文獻(xiàn)［23-24］引入合同網(wǎng)協(xié)議，設(shè)計(jì)相關(guān)合同網(wǎng)算法，有效解決了衛(wèi)星任務(wù)分配問題。文獻(xiàn)［25-26］對傳統(tǒng)合同網(wǎng)進(jìn)行改進(jìn)，設(shè)計(jì)投標(biāo)者初選策略以及誠信機(jī)制，有效降低了系統(tǒng)的通信負(fù)擔(dān)，但每輪只對單個任務(wù)進(jìn)行處理的方式效率較低，衛(wèi)星之間沒有建立有效的協(xié)調(diào)機(jī)制。文獻(xiàn)［27］面向應(yīng)急任務(wù)建立了基于虛擬星座的多智能體任務(wù)規(guī)劃模型并設(shè)計(jì)了改進(jìn)的合同網(wǎng)協(xié)議。文獻(xiàn)［28］針對海洋目標(biāo)的快速響應(yīng)問題設(shè)計(jì)了改進(jìn)的合同網(wǎng)算法，充分利用了衛(wèi)星計(jì)算的實(shí)時特征和靈活性并且對意外任務(wù)迅速響應(yīng)。文獻(xiàn)［29］在任務(wù)聚類方法的基礎(chǔ)上制定了合同網(wǎng)協(xié)議的二次分配策略，提高了分配效率以及動態(tài)響應(yīng)能力。文獻(xiàn)［30］設(shè)計(jì)了分層分布式任務(wù)框架，頂層規(guī)劃將衛(wèi)星和任務(wù)分解為集群，底層規(guī)劃根據(jù)合同網(wǎng)協(xié)議進(jìn)行任務(wù)分配。綜上，通過對上述文獻(xiàn)的分析發(fā)現(xiàn)，現(xiàn)階段進(jìn)行分布式衛(wèi)星任務(wù)規(guī)劃中主要存在以下問題：任務(wù)的處理通常是逐個進(jìn)行的，在大規(guī)模下會產(chǎn)生較大的通信量；衛(wèi)星之間沒有建立良好的協(xié)作機(jī)制造成資源的浪費(fèi)；沒有考慮分布式任務(wù)規(guī)劃中全局和局部代理目標(biāo)之間的不一致性［31］。

為解決上述問題，本文設(shè)計(jì)了改進(jìn)的合同網(wǎng)協(xié)議。首先，建立衛(wèi)星任務(wù)規(guī)劃的雙層規(guī)劃模型，上層為主星規(guī)劃模型，規(guī)劃目標(biāo)是達(dá)到全局最優(yōu)，底層為從星規(guī)劃模型，規(guī)劃目標(biāo)是各從星達(dá)到各自局部的最優(yōu)。其次，引入并發(fā)機(jī)制，包括全任務(wù)投標(biāo)策略以及二次中標(biāo)策略。然后，建立了可解約循環(huán)合同網(wǎng)，引入逼近理想解排序方法（technique for oder preference by similarity to an ideal solution，TOPSIS）完善評標(biāo)策略。最后，提出一種基于自適應(yīng)退火的合同網(wǎng)算法（contract network algorithm based on adaptive annealing，CNAA）進(jìn)行任務(wù)規(guī)劃。通過仿真實(shí)驗(yàn)證明CNAA能有效提高規(guī)劃的質(zhì)量，適用于分布式衛(wèi)星任務(wù)規(guī)劃。

1 問題描述與建模

1.1 問題描述

分布式衛(wèi)星任務(wù)規(guī)劃可以描述為m個具有自治能力的衛(wèi)星在一定時間內(nèi)通過協(xié)同對n個任務(wù)進(jìn)行觀測，使得目標(biāo)函數(shù)最優(yōu)。合同網(wǎng)協(xié)議是解決分布式任務(wù)規(guī)劃的一種有效方法，通過模仿市場機(jī)制中的“招標(biāo)-投標(biāo)-評標(biāo)”過程完成對任務(wù)的規(guī)劃。在使用合同網(wǎng)協(xié)議解決分布式衛(wèi)星任務(wù)規(guī)劃問題時，將衛(wèi)星分為主星和從星，分別充當(dāng)招投標(biāo)過程中的招標(biāo)方和投標(biāo)方。規(guī)劃過程如圖1所示。首先，主星將任務(wù)信息作為招標(biāo)信息廣播至從星進(jìn)行招標(biāo)；然后，各從星在收到招標(biāo)信息后根據(jù)信息進(jìn)行自主規(guī)劃生成投標(biāo)方案，并決定是否投標(biāo)；最后，主星對返回的所有投標(biāo)方案進(jìn)行評價，確定中標(biāo)方案，并將中標(biāo)信息廣播至從星。整個規(guī)劃過程需要進(jìn)行多次招投標(biāo)，最終輸出一個完整的任務(wù)分配方案。由于衛(wèi)星任務(wù)規(guī)劃的復(fù)雜性，本文做出以下基本假設(shè)：①待觀測任務(wù)為點(diǎn)目標(biāo)任務(wù)，任務(wù)有一定的持續(xù)時間；②攜帶的傳感器類型唯一，觀測過程中數(shù)據(jù)實(shí)時下傳；③各個衛(wèi)星之間存在實(shí)時通訊；④不考慮云層等因素對觀測的影響。

圖1 合同網(wǎng)協(xié)商協(xié)議Fig.1 Contract network negotiation agreement

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

1.2.1 模型符號

S′：表示主星；

S＝｛S1，S2，…，Si，…，Sm｝：表示從星序列；

T＝｛t1，t2，…，t j，…，tn｝：表示待觀測任務(wù)集合，共有n個任務(wù)；

t j＝〈P j，durj，dtj〉：表示任務(wù)的相關(guān)信息，其中P j表示任務(wù)t j的觀測收益，durj表示任務(wù)t j的觀測持續(xù)時間，dtj表示任務(wù)t j的任務(wù)最遲完成時間；

OTWij＝〈OTSij，OTEij〉：表示任務(wù)t j在衛(wèi)星S i上的實(shí)際觀測時間窗，OTSij和OTEij分別表示該觀測時間窗的開始時間和結(jié)束時間；

PTE：任務(wù)規(guī)劃的截止時間；

cij：衛(wèi)星Si觀測任務(wù)t j消耗的存儲量；

Ci：衛(wèi)星Si的最大存儲限制。

1.2.2 模型變量

T q：表示第q次進(jìn)行招投標(biāo)的任務(wù)集合；

CTi：表示衛(wèi)星Si規(guī)劃方案中任務(wù)的總數(shù)；

ETi：表示衛(wèi)星Si上規(guī)劃方案的觀測結(jié)束時間，ETi＝OTEi（lsti），其中l(wèi)sti表示衛(wèi)星S i上最后一個任務(wù)的觀測結(jié)束時間；

rdij：表示衛(wèi)星Si對任務(wù)t j進(jìn)行觀測時所產(chǎn)生的擾動，本文考慮3種形式的擾動：①任務(wù)安排到原任務(wù)序列的空閑時間片內(nèi)，此時rdij＝1；②任務(wù)安排導(dǎo)致原任務(wù)序列上的任務(wù)被替換，此時rdij＝1；③任務(wù)安排導(dǎo)致原任務(wù)序列上的任務(wù)不能觀測，此時rdij＝2。

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

（1）從星模型

其中，式（1）表示從星進(jìn)行任務(wù)規(guī)劃時的最大化收益以及最小化擾動的目標(biāo)，w p和w r分別表示收益和擾動的權(quán)重；式（2）表示唯一性約束，即一個任務(wù)最多被觀測一次；式（3）表示任務(wù)進(jìn)行觀測時必須要滿足時間窗要求，即任務(wù)的執(zhí)行時間窗必須在可見時間窗內(nèi)，且都早于任務(wù)的最遲完成時間；式（4）表示任務(wù)的實(shí)際觀測結(jié)束時間和任務(wù)觀測持續(xù)時間的關(guān)系，即實(shí)際觀測結(jié)束時間等于實(shí)際觀測開始時間和任務(wù)觀測持續(xù)時間的和；式（5）表示存儲約束。

（2）主星模型

其中，式（6）表示目標(biāo)函數(shù)，由最大化觀測收益、最大化完成時間差以及最大化負(fù)載均衡3個部分組成。規(guī)劃總目標(biāo)是這3個目標(biāo)的加權(quán)和，w1、w2、w3分別表示3個目標(biāo)的權(quán)重；式（7）表示負(fù)載均衡值，計(jì)算方式為規(guī)劃方案中各衛(wèi)星完成任務(wù)數(shù)量的標(biāo)準(zhǔn)差大??；式（8）表示任務(wù)數(shù)量之間在招投標(biāo)過程中的約束，每輪投標(biāo)的任務(wù)數(shù)等于總?cè)蝿?wù)數(shù)減去已安排觀測的任務(wù)數(shù)；式（9）表示方案的觀測結(jié)束時間小于任務(wù)規(guī)劃截止時間。

2 改進(jìn)合同網(wǎng)設(shè)計(jì)

本文對傳統(tǒng)合同網(wǎng)進(jìn)行改進(jìn)，設(shè)計(jì)多屬性評標(biāo)機(jī)制以及基于并發(fā)機(jī)制的可解約循環(huán)合同網(wǎng)。

2.1 多屬性評標(biāo)

本文設(shè)計(jì)多屬性評標(biāo)機(jī)制以完善評標(biāo)過程。首先，針對各投標(biāo)方案，采用向量規(guī)范化的方式進(jìn)行歸一化處理；然后，采用TOPSIS得到每個衛(wèi)星方案的最終指標(biāo)值；最后，將綜合指標(biāo)值最高的方案作為中標(biāo)方案。

（1）構(gòu)建規(guī)范決策矩陣

假設(shè)有f個投標(biāo)方案，其中f≤m，第h個衛(wèi)星的投標(biāo)方案可以用一個三元組〈BPTh，ETGh，CTh〉進(jìn)行表示，其中BPTh表示衛(wèi)星S h投標(biāo)方案中的任務(wù)集合、ETGh表示衛(wèi)星S h投標(biāo)方案的觀測結(jié)束時間與規(guī)劃截至?xí)r間的差值、CTh表示衛(wèi)星Sh規(guī)劃方案中包含的任務(wù)總數(shù)。主星在獲得各個投標(biāo)方案后通過計(jì)算各決策指標(biāo)的值將各投標(biāo)方案轉(zhuǎn)化為可比較的新投標(biāo)方案NCh，h＝｛1，2，…，f｝，其中NCh＝（FPh，ETGh，LDh）T。FPh＝，表示投標(biāo)方案的任務(wù)觀測收益和；ETGh＝PTE-ETh，表示最終觀測完成時間差；LDh＝，表示投標(biāo)方案的負(fù)載均衡率，其中對決策矩陣中的值進(jìn)行預(yù)歸一化處理得到規(guī)范決策矩陣，這里采取向量規(guī)范化的方式得到?jīng)Q策矩陣［z hg］f×3，計(jì)算方式為

（2）計(jì)算方案綜合指標(biāo)，確定中標(biāo)方案

在得到規(guī)范決策矩陣后，首先計(jì)算理想解和負(fù)理想解

然后，計(jì)算各個方案到理想解和負(fù)理想解之間的加權(quán)距離和：

最后，計(jì)算各個方案的綜合評標(biāo)指標(biāo)CEh，將綜合評價指標(biāo)最大的方案作為中標(biāo)方案。

2.2 基于并發(fā)機(jī)制的可解約循環(huán)合同網(wǎng)

傳統(tǒng)合同網(wǎng)“單任務(wù)投標(biāo)，單代理中標(biāo)”的模式在大規(guī)模任務(wù)規(guī)劃下會造成較大的通信量。本文設(shè)計(jì)并發(fā)機(jī)制來減少協(xié)商次數(shù)，包括全任務(wù)招標(biāo)和二次中標(biāo)策略。首先，在每一輪招投標(biāo)時，主星都會獲取當(dāng)前未進(jìn)行安排觀測的任務(wù)，將其作為招標(biāo)信息進(jìn)行招標(biāo)，各從星根據(jù)招標(biāo)信息生成規(guī)劃方案并進(jìn)行投標(biāo)方案的篩選來決定是否投標(biāo)，投標(biāo)方案的篩選如圖2所示。其次，為了充分利用衛(wèi)星資源，當(dāng)存在多個投標(biāo)方案時，采取二次中標(biāo)策略選擇兩個中標(biāo)方案。最后，引入可解約機(jī)制，允許上輪中標(biāo)衛(wèi)星在下輪投標(biāo)過程中對已簽約的任務(wù)進(jìn)行解約處理。綜上，本文設(shè)計(jì)了基于并發(fā)機(jī)制的可解約循環(huán)合同網(wǎng)，主要步驟如下：

圖2 投標(biāo)方案篩選Fig.2 Selection of bidding scheme

步驟1主星獲得待觀測任務(wù)序列T，進(jìn)入循環(huán)招投標(biāo)過程，令q＝1，設(shè)定循環(huán)終止次數(shù)N te；

步驟2主星開始第q次招投標(biāo)，獲取當(dāng)前所有未安排觀測的任務(wù)組成任務(wù)序列T q，若T q為空，轉(zhuǎn)步驟7，否則，轉(zhuǎn)步驟3；

步驟3主星將Tq作為招標(biāo)任務(wù)廣播給從星，各從星根據(jù)Tq生成當(dāng)前規(guī)劃方案集合｛Fiq，i＝1，2，…，m｝。同時，篩選投標(biāo)方案集合｛TFiq，i＝1，2，…，m｝，其中TFiq＝｛Fiq∩Tq｝。若各從星投標(biāo)方案都為空，轉(zhuǎn)步驟7，否則，轉(zhuǎn)步驟4；

步驟4主星獲取投標(biāo)方案集合，采用多屬性評標(biāo)策略進(jìn)行評標(biāo)，選擇首次中標(biāo)方案TFiq，中標(biāo)衛(wèi)星將規(guī)劃方案更新為F iq。更新當(dāng)前未安排觀測的任務(wù)序列T q。若T q為空，轉(zhuǎn)步驟7；否則，轉(zhuǎn)步驟5；

步驟5進(jìn)行二次評標(biāo)過程，篩選出針對T q的投標(biāo)方案集合｛，i＝1，2…，m｝，其中＝｛F iq∩T q｝，若各從星投標(biāo)方案都為空，轉(zhuǎn)步驟7，否則，轉(zhuǎn)步驟6；

步驟6進(jìn)行多屬性評標(biāo)，選擇二次中標(biāo)方案TF′iq，中標(biāo)衛(wèi)星將方案更新為F′iq。更新當(dāng)前未安排觀測的任務(wù)序列T q。兩次都未中標(biāo)的從星規(guī)劃方案不進(jìn)行更新；

步驟7若所有任務(wù)都被安排觀測或目標(biāo)函數(shù)值連續(xù)N te相同，則規(guī)劃結(jié)束，否則，令q＝q＋1，轉(zhuǎn)步驟2。

3 CNAA設(shè)計(jì)

為了快速且有效的完成任務(wù)規(guī)劃，本文設(shè)計(jì)了CNAA解決分布式衛(wèi)星任務(wù)規(guī)劃問題。

3.1 自適應(yīng)退火

各從星在收到任務(wù)序列后，如何生成規(guī)劃方案是規(guī)劃的重點(diǎn)，本文設(shè)計(jì)了自適應(yīng)模擬退火算法以生成投標(biāo)方案。首先，構(gòu)造3種領(lǐng)域算子以增強(qiáng)解的多樣性；其次，設(shè)計(jì)自適應(yīng)策略解決模擬退火算法參數(shù)敏感性強(qiáng)的問題，包括自適應(yīng)升溫策略以及動態(tài)等溫步長。

3.1.1 領(lǐng)域生成算子設(shè)計(jì)

本文設(shè)計(jì)3種鄰域生成算子，每次生成鄰域解的過程會隨機(jī)選擇一種算子生成鄰域解。3種算子分別為插入、刪除以及移位算子，如圖3～圖5所示。

圖3 插入算子Fig.3 Insertion operator

圖4 刪除算子Fig.4 Delete operator

圖5 移位算子Fig.5 Shifted operator

3.1.2 自適應(yīng)升溫策略

在模擬退火算法中，一般來說，初始溫度應(yīng)該設(shè)置的足夠大從而保證搜索質(zhì)量，但是過高的溫度會增加算法的運(yùn)行時間。本文采取自適應(yīng)升溫策略確定初始溫度，具體步驟如下：

步驟1設(shè)定初始溫度為TE*，等溫步長設(shè)定為當(dāng)前任務(wù)數(shù)，獲得滿足約束的初始解；

步驟2基于3種算子生成鄰域解，獲得當(dāng)前溫度下的鄰域解集合。檢驗(yàn)所有鄰域解，若所有鄰域解都被接受，轉(zhuǎn)步驟4；否則，轉(zhuǎn)步驟3；

步驟3更新初始溫度。更新的方法為：TE*＝TE*＋10；同時，返回步驟1；

步驟4重復(fù)步驟1～步驟3共10次，取10次初始溫度的平均值作為最終初始溫度。

3.1.3 動態(tài)等溫步長

等溫步長的值對模擬退火算法的影響也很大。較大的等溫步長可以生成更多的鄰域解，以便于找到更優(yōu)的解，但同時也會導(dǎo)致計(jì)算的時間大大增加。針對這一特點(diǎn)，設(shè)計(jì)了與溫度有關(guān)的動態(tài)等溫步長，第v次迭代下的動態(tài)等溫步長N v計(jì)算公式為

式中：λv表示第v次進(jìn)行等溫步長調(diào)節(jié)的系數(shù)，λv的計(jì)算公式為

式中：t v表示第v次迭代下的溫度；α為降溫速率；n為任務(wù)數(shù)量；n v表示在溫度t v下最優(yōu)解的完成任務(wù)的數(shù)量。

3.1.4 自適應(yīng)退火算法

本文自適應(yīng)退火算法用于各從星生成規(guī)劃方案，算法的輸入為任務(wù)序列T′以及從星S i，i∈｛1，2，…，m｝，算法的輸出為規(guī)劃方案F iq。算法最開始的初始解和最優(yōu)解都設(shè)定為衛(wèi)星Si未進(jìn)行退火的原規(guī)劃方案，算法流程如下：

步驟1執(zhí)行自適應(yīng)溫度策略獲得初始溫度TE*，設(shè)定終止溫度TEmin，降溫速率f c，設(shè)定初始等溫步長N c，令c＝0，v＝0；

步驟2進(jìn)行判斷，若TE*＞TEmin，轉(zhuǎn)步驟7。否則，轉(zhuǎn)步驟3；

步驟3進(jìn)行判斷，若c＞N c，轉(zhuǎn)步驟6。否則，轉(zhuǎn)步驟4；

步驟4隨機(jī)選擇生成算子生成領(lǐng)域解，以Metropolis準(zhǔn)則判斷是否接受領(lǐng)域解；

步驟5更新當(dāng)前解和最優(yōu)解，c＝c＋1，轉(zhuǎn)步驟3；

步驟6v＝v＋1，根據(jù)式（16）和式（17）更新等溫步長N c；同時，進(jìn)行降溫操作，TE*＝f c·TE*，令c＝0，轉(zhuǎn)步驟2；

步驟7退火結(jié)束，輸出Si的規(guī)劃方案。

3.2 CNAA

本文設(shè)計(jì)CNAA進(jìn)行分布式衛(wèi)星任務(wù)規(guī)劃。算法的輸入為任務(wù)集合T，衛(wèi)星集合｛S1，S2，…，Sm｝，算法輸出為最終規(guī)劃方案，主要算法流程如下：

步驟1算法初始化，對任務(wù)集合T按照收益從大到小進(jìn)行重排序，若存在多個收益相同的任務(wù)，按照任務(wù)觀測持續(xù)時間由小到大進(jìn)行二次排序；

步驟2進(jìn)入循環(huán)合同網(wǎng)，主星獲取所有未觀測任務(wù)信息。若所有任務(wù)都被觀測，轉(zhuǎn)步驟7。否則，基于全任務(wù)投標(biāo)策略進(jìn)行投標(biāo)，轉(zhuǎn)步驟3；

步驟3各從星基于自適應(yīng)退火算法生成規(guī)劃方案；

步驟4篩選投標(biāo)方案，若各從星投標(biāo)方案都為空，轉(zhuǎn)步驟7。否則，基于多屬性評標(biāo)策略進(jìn)行評標(biāo)，更新中標(biāo)衛(wèi)星的規(guī)劃方案和未觀測任務(wù)序列，轉(zhuǎn)步驟5；

步驟5若當(dāng)前未觀測任務(wù)序列為空，轉(zhuǎn)步驟7。否則，執(zhí)行二次評標(biāo)策略，更新二次中標(biāo)衛(wèi)星的規(guī)劃方案和未觀測任務(wù)序列，轉(zhuǎn)步驟6；

步驟6若最優(yōu)收益連續(xù)N te次保持不變，轉(zhuǎn)步驟7。否則，循環(huán)步驟2～步驟5進(jìn)行方案迭代更新；

步驟7停止循環(huán)，輸出方案。

4 仿真算例

本節(jié)通過實(shí)驗(yàn)驗(yàn)證本文所提出的方法的合理性和有效性。實(shí)驗(yàn)計(jì)算機(jī)配置為Intel（R）Xeon（R）W-2255，CPU＠3.70 GHz，編程語言為java，基于IDEA 2021開發(fā)環(huán)境實(shí)現(xiàn)。本文利用仿真軟件生成3顆、4顆、5顆衛(wèi)星的數(shù)據(jù)。任務(wù)規(guī)劃時域?yàn)?017年4月23日00：00：00～2017年4月23日24：00：00。隨機(jī)生成50、100、150、200、250、300、350、400、450、500個任務(wù)集合的10組算例，實(shí)驗(yàn)過程中每組算例運(yùn)行50次，取50次的平均值作為最終結(jié)果，部分任務(wù)信息如表1所示。由于衛(wèi)星任務(wù)規(guī)劃問題的復(fù)雜性，目前沒有該領(lǐng)域公認(rèn)的實(shí)驗(yàn)測試集。本文首先在3顆衛(wèi)星資源下使用CNAA的求解結(jié)果與CPLEX求解器的求解結(jié)果進(jìn)行對比以表明本文算法的有效性；其次，在3顆衛(wèi)星資源下，與基于二次分配策略的合同網(wǎng)算法［29］（contract network algorithm based on secondary allocation strategy，CNSA）以及集中式算法（centralized algorithm，CA）對比以表明本文算法的合理性；最后，將3顆衛(wèi)星的規(guī)劃結(jié)果和4顆以及5顆衛(wèi)星的規(guī)劃結(jié)果進(jìn)行對比，分析資源增加后對規(guī)劃的影響情況。

表1 部分任務(wù)信息Table 1 Partial task information

4.1 算法有效性實(shí)驗(yàn)

為了驗(yàn)證CNAA的有效性，將上述10組算例在分別使用CNAA以及CPLEX求解器進(jìn)行任務(wù)規(guī)劃，規(guī)劃結(jié)果對比如表2所示。

表2 CNAA和CPLEX結(jié)果Table 2 CNAA and CPLEX results

從表2可以看出，CNAA相較于CPLEX求解器能夠以較短的時間完成任務(wù)規(guī)劃。當(dāng)任務(wù)規(guī)模較小的時候，CNAA的觀測收益率和CPLEX求解器的觀測收益率基本保持一致。當(dāng)任務(wù)規(guī)模增大至150時，CNAA的觀測收益率和CPLEX求解器的觀測收益率之間的差距約為2%。當(dāng)任務(wù)規(guī)模增大至250時，CPLEX就無法對其進(jìn)行求解，而CNAA仍能在較短的時間內(nèi)完成任務(wù)規(guī)劃，綜上，說明了CNAA的有效性。

4.2 算法合理性實(shí)驗(yàn)

為了驗(yàn)證CNAA和改進(jìn)合同網(wǎng)協(xié)議的合理性，將上述10組算例分別使用CNAA、CNSA以及CA進(jìn)行任務(wù)規(guī)劃，通過對比表明CNAA 和改進(jìn)合同網(wǎng)協(xié)議的合理性。

（1）為了說明CNAA在觀測收益率、任務(wù)完成率以及規(guī)劃耗時的合理性，將10組算例分別使用CNAA、CNSA、CA進(jìn)行規(guī)劃。實(shí)驗(yàn)結(jié)果如表3以及圖6～圖8所示。

表3 收益率和完成率以及規(guī)劃耗時對比結(jié)果Table 3 Yield and completion rate and planning time comparison

圖6 觀測收益率對比Fig.6 Comparison of observed yield

圖7 任務(wù)完成率對比Fig.7 Task completion rate comparison

圖8 規(guī)劃耗時對比Fig.8 Comparison of planning time

從表3以及圖6～圖8可以看出，在本文進(jìn)行試驗(yàn)的10組算例下，CNAA在任務(wù)規(guī)劃的觀測收益率以及任務(wù)完成率上都明顯高于CNSA，在觀測收益率方面，CNAA的觀測收益率比CNSA平均提高約11.5%，與CA相比，差距不超過2.5%。在任務(wù)完成率方面，CNAA的任務(wù)完成率比CNSA平均提高約16.3%，與CA相比，差距不超過3%。隨著任務(wù)規(guī)模的增加，3種算法在觀測收益率以及任務(wù)完成率之間的差距趨于穩(wěn)定。

在規(guī)劃耗時方面，CNAA的規(guī)劃耗時優(yōu)于CNSA 和CA的規(guī)劃耗時。當(dāng)任務(wù)規(guī)模較少時，3種算法的規(guī)劃耗時都比較短，但當(dāng)任務(wù)規(guī)模增大時，CNSA和CA的規(guī)劃耗時迅速增加。尤其是集中式規(guī)劃CA在任務(wù)規(guī)模超過300后，其規(guī)劃耗時呈現(xiàn)指數(shù)型的快速增長趨勢，而CNAA隨著任務(wù)規(guī)模的增加，其規(guī)劃耗時的增長趨勢較為平緩，且保持在一個相對較短的水平。綜上，CNAA在觀測收益率、任務(wù)完成率兩個方面均優(yōu)于CNSA，且與CA之間的差距較低。在規(guī)劃耗時方面，CNAA不管是在小規(guī)模還是大規(guī)模算例中均能以較短的規(guī)劃時長獲得較好的規(guī)劃方案。

（2）為了說明改進(jìn)合同網(wǎng)協(xié)議的合理性，將上述10組算例分別使用CNAA、CNSA、CA進(jìn)行任務(wù)規(guī)劃，通過平均完成時間差以及負(fù)載均衡值以及協(xié)商次數(shù)以表明改進(jìn)合同網(wǎng)協(xié)議的合理性。其中，完成時間差是任務(wù)規(guī)劃截至?xí)r間和最終任務(wù)完成時間的差值，差值越大，說明任務(wù)完成的越早。負(fù)載均衡值是各衛(wèi)星完成任務(wù)數(shù)量的標(biāo)準(zhǔn)差，負(fù)載均衡值越小，說明任務(wù)在各衛(wèi)星上的數(shù)量分布越均衡。平均完成時間差、負(fù)載均衡值以及協(xié)商次數(shù)的結(jié)果分別如表4以及圖9～圖11所示。

表4 平均完成時間差和負(fù)載均衡值以及協(xié)商次數(shù)對比結(jié)果Table 4 Comparison results of average completion time difference，load balancing value，and negotiation times

圖9 時間差對比Fig.9 Time difference comparison

圖10 負(fù)載對比Fig.10 Load comparison

圖11 協(xié)商次數(shù)對比Fig.11 Negotiation times comparison

從表4以及圖9可以看出，當(dāng)任務(wù)規(guī)模為50時，CNAA的平均完成時間差小于CA的平均完成時間差，這是因?yàn)榧惺揭?guī)劃會充分利用衛(wèi)星的能力，當(dāng)任務(wù)規(guī)模較小時，會出現(xiàn)只需要部分衛(wèi)星就完成任務(wù)觀測的情況，無觀測任務(wù)的衛(wèi)星的完成時間差就為規(guī)劃時域的大小，從而造成較大的平均完成時間差。隨著任務(wù)規(guī)模增大，當(dāng)任務(wù)規(guī)模達(dá)到100后，CNAA的平均完成時間差均大于CNSA和CA的平均完成時間差，CNAA的完成時間比CNSA 完成時間平均早12.3 min，比CA的完成時間平均早6.2 min左右，能夠更早地完成任務(wù)觀測。隨著任務(wù)規(guī)模的進(jìn)一步增加，各算法的平均完成時間差都逐漸減小，這是因?yàn)殡S著安排觀測任務(wù)數(shù)的增加，會導(dǎo)致觀測時間窗后移，最終觀測任務(wù)的觀測時間窗也會漸漸靠近規(guī)劃截止時間，造成完成時間差的降低，從而出現(xiàn)完成時間差隨著任務(wù)規(guī)模增大而減小的情況。

從表4以及圖10可以看出，在任務(wù)規(guī)劃的負(fù)載均衡方面，當(dāng)任務(wù)規(guī)模為50時，CNAA的負(fù)載均衡值大于CNAA的負(fù)載均衡值，這是因?yàn)閭鹘y(tǒng)合同網(wǎng)算法采取單任務(wù)投標(biāo)形式，所以在任務(wù)規(guī)模較少的時候，多次投標(biāo)會使任務(wù)有更大概率分散到各個衛(wèi)星上，從而使得負(fù)載更均衡。但隨著任務(wù)規(guī)模增大，CNAA的負(fù)載均衡值差均大于CNSA和CA的平負(fù)載均衡值，說明在大規(guī)模下CNAA更能保證規(guī)劃的負(fù)載均衡。

對于通信協(xié)商成本使用協(xié)商次數(shù)進(jìn)行衡量，從表4以及圖11可以看出，CNAA的協(xié)商次數(shù)顯然小于CNSA協(xié)商次數(shù)。在不同規(guī)模下，CNAA所需要的協(xié)商次數(shù)平均只有CNSA的22.7%，大大減小了通信成本。隨著任務(wù)規(guī)模的增加，規(guī)劃的復(fù)雜性也大大增加，從而導(dǎo)致協(xié)商的次數(shù)也會增加。傳統(tǒng)合同網(wǎng)采用單任務(wù)招投標(biāo)，所以其協(xié)商次數(shù)就等同于任務(wù)數(shù)，CNSA采用了二次分配策略，所以協(xié)商次數(shù)高于任務(wù)數(shù)。不管是傳統(tǒng)合同網(wǎng)算法還是CNSA，CNAA所需的協(xié)商次數(shù)都有很大的優(yōu)勢。綜上，CNAA在平均完成時間差、負(fù)載均衡以及協(xié)商次數(shù)3個方面均優(yōu)于CNSA和CA，表明了CNAA的合理性。

4.3 衛(wèi)星資源影響分析

為了分析不同規(guī)模的衛(wèi)星資源下對規(guī)劃的影響程度，將衛(wèi)星個數(shù)增加至4顆和5顆，并且對10組算例進(jìn)行規(guī)劃，從觀測收益率、協(xié)商次數(shù)、規(guī)劃耗時3個指標(biāo)進(jìn)行分析，規(guī)劃結(jié)果如表5以及圖12～圖14所示。

表5 不同資源下規(guī)劃結(jié)果對比Table 5 Comparison of planning results under different resources

圖12 收益率對比Fig.12 Yield ratio comparison

圖13 協(xié)商對比Fig.13 Negotiating comparison

圖14 耗時對比Fig.14 Time consuming compared

從表5以及圖12可以看出，隨著衛(wèi)星資源的增多，觀測收益率隨之增加。當(dāng)任務(wù)規(guī)模達(dá)到200之后，觀測收益率的差距得到進(jìn)一步體現(xiàn)，從規(guī)劃結(jié)果可以看出，4星相較于3星觀測收益率平均提高了約4.8%，5星相較于3星觀測收益率提高了約6.5%。

另一方面，規(guī)劃耗時和協(xié)商次數(shù)隨著衛(wèi)星資源的增多而減少。4星相較于3星規(guī)劃耗時平均減少了約3.1 s，5星相較于3星規(guī)劃耗時平均減少了約4.5 s。4星相較于3星協(xié)商次數(shù)平均減少了約19.3次，5星相較于3星協(xié)商次數(shù)減少了32.3次。在任務(wù)規(guī)模不變的情況下，隨著衛(wèi)星資源的增加，規(guī)劃能力得到提高，能夠以更少的協(xié)商次數(shù)完成對任務(wù)的規(guī)劃，協(xié)商次數(shù)的減少就會降低規(guī)劃的時長。不同衛(wèi)星資源下的規(guī)劃對比實(shí)驗(yàn)揭示了任務(wù)規(guī)劃和衛(wèi)星資源之間的影響關(guān)系。

5 結(jié)束語

本文針對分布式衛(wèi)星任務(wù)規(guī)劃問題，提出了可解約循環(huán)合同網(wǎng)進(jìn)行任務(wù)規(guī)劃。設(shè)計(jì)全任務(wù)投標(biāo)策略以及二次評標(biāo)策略解決傳統(tǒng)合同網(wǎng)協(xié)商次數(shù)多的問題，有效降低了衛(wèi)星的通信成本。建立多屬性評標(biāo)策略，彌補(bǔ)了評標(biāo)屬性單一的問題。提出了CNAA進(jìn)行分布式任務(wù)規(guī)劃，通過對比實(shí)驗(yàn)證明了算法的有效性和合理性。在本文的基礎(chǔ)上，下一步的研究主要考慮：①當(dāng)應(yīng)急任務(wù)到達(dá)時，如何及時響應(yīng)且快速完成任務(wù)規(guī)劃；②當(dāng)衛(wèi)星發(fā)生通信故障或成像不能完成情況時，如何合理優(yōu)化調(diào)整現(xiàn)有規(guī)劃方案。