SAGA：一種面向任務(wù)的衛(wèi)星網(wǎng)絡(luò)資源分配算法

楊 力，楊 恒，魏德賓，3，潘成勝

1(大連大學 通信與網(wǎng)絡(luò)實驗室，遼寧 大連 116622)2(大連大學 信息工程學院，遼寧 大連 116622)3(南京理工大學 自動化學院，南京 210094)

1 引 言

衛(wèi)星網(wǎng)絡(luò)在民生、軍事等諸多領(lǐng)域都處于十分關(guān)鍵的地位，這是因為衛(wèi)星網(wǎng)絡(luò)與傳統(tǒng)地面網(wǎng)絡(luò)相比，具有組網(wǎng)不受地理因素限制，覆蓋范圍沒有盲區(qū)等諸多優(yōu)點[1-3].隨著組網(wǎng)衛(wèi)星的增多和任務(wù)請求的增加，衛(wèi)星網(wǎng)絡(luò)資源分配變得越來越復雜，分配的復雜性體現(xiàn)在，除了需要為任務(wù)選擇資源之外，還需要考慮對多個任務(wù)進行優(yōu)化組合，問題求解空間的規(guī)模隨著任務(wù)和衛(wèi)星數(shù)量的增長而急劇擴大[4,5].因此，如何設(shè)計資源分配方法使所有任務(wù)在最短時間內(nèi)合理完成資源分配成為亟待解決的問題.

李衛(wèi)平等人[6]針對云計算的資源分配問題進行了研究，利用費用與時間矩陣表征任務(wù)執(zhí)行的收益，給出了基于收益的動態(tài)協(xié)商式分配算法，該算法在任務(wù)成功率、平均成本和完成時間方面具有優(yōu)勢.Xu等人[7]首先根據(jù)用戶鏈路的使用壽命以及地面站的個數(shù)等因素為衛(wèi)星資源分配問題構(gòu)建了混合非整數(shù)分配模型，隨后利用燕子群算法對模型進行了尋優(yōu)，最終得到了一種基于比例均衡的資源分配方法且取得了比較好的效果.許力等人[8]分析了虛擬資源分配中存在的高能耗問題，針對問題他們以CPU頻率作為突破口構(gòu)建了多目標模型，并提出了一種NSGA-II進化算法對模型進行求解，仿真結(jié)果表明該算法成功降低了分配過程中所需的能耗.辛波等人[9]考慮了虛擬資源分配中常常被忽略的資源異構(gòu)問題，重點關(guān)注了資源之間的差異性，它們提出的資源分配算法在滿足用戶需求的情況下可以節(jié)省一部分資源開銷.趙靜等人[10]建立了混合鏈路資源調(diào)度多目標約束規(guī)劃模型,將小生境技術(shù)引入遺傳算法，提出了一種改進的小生境遺傳算法對模型進行求解.所提方法成功解決了混合鏈路情況下的資源分配問題.

目前為止，針對衛(wèi)星網(wǎng)絡(luò)資源分配問題進行的有關(guān)研究大都只考慮了一類資源.另外，大多數(shù)研究都是以任務(wù)成功率作為目標函數(shù)，導致任務(wù)完成時間過長，少數(shù)研究以任務(wù)完成時間為目標函數(shù)，但沒有進一步考慮任務(wù)優(yōu)先級，導致資源分配優(yōu)先級匹配度不高.針對以上問題，本文提出了一種基于自適應(yīng)遺傳算法的衛(wèi)星網(wǎng)絡(luò)資源分配方法.該方法首先將現(xiàn)有衛(wèi)星網(wǎng)絡(luò)的資源劃分為傳感器資源、計算資源、存儲資源、通信資源四大類，同時考慮四種資源的分配問題.隨后，在建立目標函數(shù)時，同時考慮了任務(wù)優(yōu)先級和任務(wù)完成時間，可以使所有任務(wù)在最短時間內(nèi)合理完成資源分配；最后，提出了一種自適應(yīng)遺傳算法對模型求解，該算法利用精英保留的思想改進了采用輪盤賭策略的選擇算子并且給出了一種能夠自適應(yīng)更新自身概率的變異、交叉算子，解決了標準遺傳算法容易陷入局部最優(yōu)的缺陷，同時能夠避免最優(yōu)解的丟失.

2 模型建立

衛(wèi)星網(wǎng)絡(luò)資源分配問題能夠被視為一種多目標約束滿足問題.這類問題求解的關(guān)鍵在于如何將對資源的約束描述為條件滿足模型，并采用最優(yōu)化算法搜索滿足約束模型的解.

2.1 資源池的建立

資源池[11]被定義為衛(wèi)星網(wǎng)絡(luò)里全部可用資源的集合,如圖1所示.構(gòu)建資源池時，主要考慮四種資源，分別是計算資源、通信資源、傳感器資源和存儲資源.其中，計算資源主要考慮CPU資源，通信資源主要考慮鏈路資源.我們會將衛(wèi)星網(wǎng)絡(luò)里全部的資源都集中表示在資源池里.

圖1 資源池模型Fig.1 Resource pool model

資源分配星：資源池位于資源分配星，資源分配星的主要職責在于通過監(jiān)控網(wǎng)絡(luò)內(nèi)部衛(wèi)星的變動從而更新資源的變化，并將這種資源變化記錄到資源池里.因為衛(wèi)星具有比較高的動態(tài)性，因此我們需要及時更新資源以方便任務(wù)的資源請求.

2.2 參數(shù)及決策變量定義

假設(shè)衛(wèi)星網(wǎng)絡(luò)中共有s顆衛(wèi)星，設(shè)衛(wèi)星集為：

sat={sat1,sat2,…,sats}

(1)

由s顆衛(wèi)星構(gòu)成的衛(wèi)星網(wǎng)絡(luò)里資源的種類有m種，資源的個數(shù)有r個，每種任務(wù)在執(zhí)行時會調(diào)用衛(wèi)星上一定的資源.

假設(shè)用戶提交了n個任務(wù)，設(shè)有任務(wù)集為：

Task={Task1,Task2,…,Taskn}

(2)

每個任務(wù)包含獨立且保持序關(guān)系的Qi個子任務(wù)，可以表示為：

Taski={Taski1,Taski2,…,TaskiQi}

(3)

其中Taski的每個子任務(wù)都需要遵守序關(guān)系.序關(guān)系有兩種，“=”表示前后子任務(wù)間可以并行執(zhí)行，“<”表示前面子任務(wù)是后面子任務(wù)執(zhí)行的前提，子任務(wù)間需要串行執(zhí)行.兩種序關(guān)系同時出現(xiàn)時，任務(wù)呈現(xiàn)出混合模態(tài)，即：

Taski1=Taski2<…

(4)

作如下定義，令k代表資源標號，令i代表任務(wù)標號，令j代表子任務(wù)標號，那么Tijk代表于資源k上任務(wù)i的第j個子任務(wù)的完成時間.tijk代表于資源k上任務(wù)i的第j個子任務(wù)的執(zhí)行時間.Tik代表于資源k上任務(wù)i的完成時間.Tik等于任務(wù)i的所有子任務(wù)中最后一個子任務(wù)的完成時間.

任務(wù)i在資源k上的完成時間：在資源k上從第一個被執(zhí)行任務(wù)開始執(zhí)行(記為0)到第i個任務(wù)被執(zhí)行完成的時間.

任務(wù)i在資源k上的執(zhí)行時間：在資源k上從第i個被執(zhí)行任務(wù)開始執(zhí)行到第i個任務(wù)被執(zhí)行完成的時間差值.

任務(wù)i的第j個子任務(wù)在資源k上的完成時間：在資源k上從第一個被執(zhí)行任務(wù)開始執(zhí)行(記為0)到第i個任務(wù)的第j個子任務(wù)被執(zhí)行完成的時間.

任務(wù)i的第j個子任務(wù)在資源k上的執(zhí)行時間：在資源k上從第i個任務(wù)的第j個子任務(wù)開始執(zhí)行到這個子任務(wù)被執(zhí)行完成的時間差值.

最優(yōu)任務(wù)序列：如果優(yōu)先級pi∈{1,2,…,pmax}，pmax是正整數(shù)，代表最高優(yōu)先級.對任務(wù)隊列里全部的任務(wù)按照優(yōu)先級進行排序(優(yōu)先級高的排在前面)，優(yōu)先級相同的任務(wù)按照任務(wù)所需執(zhí)行時間越短優(yōu)先級越高的原則進行排序，則可以得到基于優(yōu)先級的最優(yōu)任務(wù)執(zhí)行序列，記為最優(yōu)任務(wù)序列.

任務(wù)序列優(yōu)先級逆序數(shù)(PIN，priority inverse number of task sequence)：由于受到資源的限制，資源分配后得到的結(jié)果一般情況下都不是最優(yōu)任務(wù)序列，為了對任務(wù)優(yōu)先級的匹配程度進行度量，本文引入線性代數(shù)中逆序數(shù)的概念，定義任務(wù)執(zhí)行序列的優(yōu)先級逆序數(shù)PIN：對于需要分配的n個任務(wù)，可以得到它的最優(yōu)任務(wù)序列，在最終得到的任務(wù)執(zhí)行序列中，當某兩個元素的先后次序與最優(yōu)任務(wù)序列不同時，則有1個逆序，則任務(wù)執(zhí)行序列中所有逆序的總數(shù)叫做這個任務(wù)執(zhí)行序列的優(yōu)先級逆序數(shù)PIN.對于一個任務(wù)執(zhí)行序列，它的優(yōu)先級逆序數(shù)越小，則基于優(yōu)先級的角度該任務(wù)執(zhí)行序列越好.

2.3 多目標約束模型建立

本文描述的問題符合以下假設(shè)條件：

a)用戶已知提交任務(wù)與其子任務(wù)的類型和子任務(wù)所需要占用資源的類型與時間；

b)一個任務(wù)的某些子任務(wù)需要在同一顆衛(wèi)星上執(zhí)行；

c)每個子任務(wù)可以在可用資源子集的任意衛(wèi)星上處理；

d)子任務(wù)間的執(zhí)行順序可以是串行，并行或混合模態(tài)；

當前問題的難點在于怎樣分配任務(wù)和資源，才能使所有任務(wù)完成時間盡可能短的同時使任務(wù)的優(yōu)先級匹配度也較高.基于上述定義，建立的衛(wèi)星網(wǎng)絡(luò)資源分配系統(tǒng)多目標約束模型為：

(5)

s.t.

1)Tijk-Tizk≥tijk

i∈Task,j,z∈Taski,0

2)Tegk-Tijk≥tegk

i,e∈Task,j∈Taski,g∈Taske,k∈{1,2,…,r}

3)Tijk≥tijk,?j∈Taski

4)Tik≥0,?i∈Task,k∈{1,2,…,r}

上述模型中，目標函數(shù)f1表示完成所有任務(wù)的時間，通過最小化f1使完成所有任務(wù)的時間最短.目標函數(shù)f2表示任務(wù)執(zhí)行序列的優(yōu)先級逆序數(shù)，通過最小化f2使任務(wù)執(zhí)行盡可能合理.約束1)是串行約束：為了確保每個任務(wù)的子任務(wù)之間的串行關(guān)系，任務(wù)i的第z個子任務(wù)需要于第j個子任務(wù)之前執(zhí)行完成.這里的子任務(wù)z是子任務(wù)j之前的第一個和子任務(wù)j具有串行關(guān)系的子任務(wù).約束2)是資源約束：任何資源在同一時間只能執(zhí)行一個任務(wù).約束3)是時間約束：每個子任務(wù)的執(zhí)行時間都需要小于等于其完成時間.約束4)是正約束：表示任何子任務(wù)的完成時間都需要是正數(shù).

在衛(wèi)星網(wǎng)絡(luò)資源分配問題中，任務(wù)完成時間、優(yōu)先級逆序數(shù)是不同量綱的目標函數(shù).為了方便后續(xù)算法的求解，我們首先對函數(shù)進行歸一化去量綱計算并利用線性加權(quán)的思想把多目標模型構(gòu)建成單目標模型.具體表達為：

(6)

3 基于自適應(yīng)遺傳算法的分配方法

根據(jù)衛(wèi)星網(wǎng)絡(luò)資源分配模型生成分配方案并計算目標函數(shù)，采用遺傳算法對分配方案進行尋優(yōu).現(xiàn)如今遺傳算法已經(jīng)被廣泛使用并且在約束滿足、組合優(yōu)化等的相關(guān)問題上取得了良好的效果.

標準遺傳算法(SGA，the standard genetic algorithm)因為利用目標函數(shù)的相關(guān)變形構(gòu)造適應(yīng)度函數(shù)，所以算法的全局搜索能力很強，但是它容易陷入局部最優(yōu)并進而導致早熟問題.針對上述問題，文中采用精英保留策略與輪盤賭策略相結(jié)合的方法設(shè)計選擇機制、設(shè)計自適應(yīng)的交叉、變異算子，改進了標準遺傳算法，改進后的算法可以有效避免早熟現(xiàn)象的發(fā)生，同時能夠防止最優(yōu)解的丟失，有效提高了算法的尋優(yōu)速度.

3.1 編碼與解碼

編碼方式也就是染色體的表現(xiàn)形式，這里我們采用子任務(wù)的方式，即染色體上每個基因代表一個子任務(wù).這里采用整數(shù)形式表示基因.

解碼過程：按照編碼序號選擇對應(yīng)的子任務(wù).

3.2 適應(yīng)度函數(shù)設(shè)計

利用公式(6)定義的單目標函數(shù)設(shè)計適應(yīng)度函數(shù)，對于給定的染色體，適應(yīng)度函數(shù)定義為：

(7)

在計算適應(yīng)度值之前，由于生成染色體時沒有考慮子任務(wù)的序關(guān)系，因此需要先調(diào)整序關(guān)系，使染色體變成問題的可行解.調(diào)整方法比較簡單，遍歷染色體，把不滿足序關(guān)系的基因交換位置即可.

3.3 基于精英保留和輪盤賭策略設(shè)計選擇算子

很多算法通過輪盤賭策略來判斷是否把染色體遺傳給下一代，但是這種方式容易造成精英個體的丟失，為此本文基于精英保留策略改進選擇機制，精英保留就是保留父代中的優(yōu)秀個體直接進入子代.具體的方法描述是：對當前種群中的個體分別計算適應(yīng)度值，對比個體的適應(yīng)度值，把適應(yīng)度值大的部分個體直接保留并遺傳給下一代，剩下的個體通過輪盤賭策略進行選擇.

3.4 自適應(yīng)交叉、變異算子

本文給出了一種能夠根據(jù)情況自動更新自身概率的交叉、變異算子，令Pc和Pm分別表示自適應(yīng)交叉和變異概率.采用公式(8)具體計算自適應(yīng)交叉概率和變異概率：

(8)

式(8)中：k1,k2為0～1之間的常數(shù)，分別為初始交叉概率,變異概率；f表示種群的適應(yīng)度值列表；E(*)為求隨機變量數(shù)學期望的函數(shù)；Pc,Pm為自適應(yīng)交叉概率、變異概率.

如果種群內(nèi)各個染色體的適應(yīng)度值趨于相同，那么種群容易陷入局部最優(yōu)的狀態(tài)，此時種群的多樣性較差，適當增大Pc和Pm可以增加新染色體出現(xiàn)的概率，從而提升種群跳出局部最優(yōu)的可能.

計算得到自適應(yīng)交叉概率Pc和變異概率Pm后，對染色體進行自適應(yīng)交叉、變異操作.為確保每條染色體中的每個基因出現(xiàn)且僅出現(xiàn)一次，交叉算子采用循環(huán)交叉算子，變異算子采用基因?qū)Q變異算子.

循環(huán)交叉算子：對于兩個父體A、B，選擇兩個交叉位置，交叉位置之間的基因片段直接拷貝到子體中，為了得到子體A′，只需要移走父體B中已在A′中存在的基因，剩下的基因依次放入A′中，即可得到A′.同理可以得到B′.循環(huán)交叉算子示例如下(豎線為交叉位置).

父體A

子體A′

123|4567|89→218|4567|93

父體B

子體B′

452|1876|93→234|1876|59

基因?qū)Q變異算子的原理比較簡單，隨機選擇兩個基因?qū)Q位置即可.

3.5 算法流程

自適應(yīng)遺傳算法的具體流程如圖2所示.

圖2 遺傳算法流程圖Fig.2 Flow chart of GA

4 仿真驗證

為驗證算法的有效性，我們以偵察任務(wù)為例進行分析，設(shè)計了一個具有8顆衛(wèi)星的衛(wèi)星星座，其中一顆高軌衛(wèi)星作為資源分配星，其他衛(wèi)星的代碼和類型如表1所示.

表1 衛(wèi)星信息表Table 1 Satellite information table

表1中每顆衛(wèi)星承載了不同類別的設(shè)備，設(shè)備代碼和種類如表2所示.

表2 設(shè)備代碼Table 2 Device code

本次實驗里，統(tǒng)計設(shè)備個數(shù)是45.1-6號設(shè)備是1號返回式偵察衛(wèi)星具有的資源，7-13號設(shè)備是2號光電成像數(shù)據(jù)傳輸型衛(wèi)星具有的資源，14-18號設(shè)備是3號詳查光電成像數(shù)據(jù)傳輸型普查衛(wèi)星具有的資源，19-25號設(shè)備是4號合成孔徑雷達偵察衛(wèi)星具有的資源，26-32號設(shè)備是5號靜止氣象衛(wèi)星具有的資源，33-39號設(shè)備是6號極軌氣象衛(wèi)星具有的資源，40-45號設(shè)備是7號傳輸型地球資源衛(wèi)星具有的資源.里面，1、21是紅外照相機IC，8、36、41是光譜照相機SC，2、26、42是可見光相機VC，7、14、34是多光譜照相機MSC，19、20、35是雷達照相機RC，15、27、40 是紅外攝像機IV，9、33是多光譜攝像機MSV.5、12、30、31是處理器C_1，6、18、22、32、39為處理器C_2，13、23、45為處理器C_3，3、29、37為天線A_1，38、44為天線A_2，4、17為天線A_3，10、24為存儲器R_1，11、43為存儲器R_2，16、25、28為存儲器R_3.

本文假定，同一任務(wù)的某些子任務(wù)需要在同一顆衛(wèi)星上執(zhí)行，其它子任務(wù)可以在其它衛(wèi)星上執(zhí)行，我們用同星標識進行標記，如表3所示，其中任務(wù)2中的前三個子任務(wù)，它們的同星標識都為1，需要在同一顆衛(wèi)星上執(zhí)行，最后一個子任務(wù)的同星標識為2，可以在其它衛(wèi)星上執(zhí)行.最后，每個子任務(wù)需要相應(yīng)資源完成，資源一旦被子任務(wù)占用，其他子任務(wù)必須等到該資源釋放之后才可以使用.

仿真實驗中共計50個任務(wù)，180個子任務(wù).其中前5個任務(wù)，18個子任務(wù)的相關(guān)信息如表3所示.這里的任務(wù)與子任務(wù)已經(jīng)按照3.1中的編碼思想進行了排序，表中子任務(wù)編碼屬性代表了子任務(wù)對應(yīng)的編碼序號，我們按照這個序號進行編解碼.子任務(wù)序關(guān)系屬性表征一個任務(wù)的子任務(wù)的序關(guān)系，舉例來說，任務(wù)1的子任務(wù)的序關(guān)系全是1，表示這三個子任務(wù)可以并行執(zhí)行；任務(wù)3的子任務(wù)的序關(guān)系是1、2、3，表示這三個子任務(wù)串行執(zhí)行；任務(wù)2的子任務(wù)的序關(guān)系是1、2、3、3，表示前兩個子任務(wù)串行執(zhí)行，第二個子任務(wù)執(zhí)行完后，后兩個子任務(wù)執(zhí)行，這兩個子任務(wù)可以并行執(zhí)行.

表3 任務(wù)屬性舉例Table 3 Examples of task attributes

實驗計算機配置為Intel(R)Core(TM)i7-3770 CPU@3.40GHz 3.40GHz,內(nèi)存為4GB，操作系統(tǒng)為Windows7.python仿真程序運行在PyCharm平臺上.實驗結(jié)果記錄了適應(yīng)度函數(shù)值、任務(wù)完成時間，任務(wù)序列優(yōu)先級逆序數(shù)等.

一個好的分配方案應(yīng)該是在考慮任務(wù)優(yōu)先級的情況下完成同樣工作需要的時間最少.因此，將全部任務(wù)的完成時間和任務(wù)序列優(yōu)先級逆序數(shù)作為判斷分配方案優(yōu)劣的主要指標，適應(yīng)度函數(shù)正是根據(jù)任務(wù)完成時間和任務(wù)序列優(yōu)先級逆序數(shù)定義的.從定義可知，完成時間越短、任務(wù)序列優(yōu)先級逆序數(shù)越小則適應(yīng)度值越高.設(shè)常量con=15，權(quán)重w1,w2分別取為0.8，0.2，則最理想的適應(yīng)度值應(yīng)該為15，可在資源充足，不發(fā)生沖突的情況下得到.然而因為資源限制、序關(guān)系的存在，這個值只能作為一個理論值用來評判分配結(jié)果.

為了初步分析分配方法的可行性，我們?nèi)∏?5個任務(wù)，90個子任務(wù)進行仿真并把初始交叉概率設(shè)定為0.8，初始變異概率設(shè)定為0.1.每組算例進行50次仿真并對結(jié)果求取均值.最終分配結(jié)果如表4所示.

表4 分配算法實驗結(jié)果Table 4 Experimental results of allocation algorithm

在當前仿真參數(shù)設(shè)置下，由表4能夠知道適應(yīng)度值最優(yōu)是13.114.在仿真過程中適應(yīng)度值隨運行代數(shù)的增加而提高，當運行代數(shù)確定時適應(yīng)度值隨種群規(guī)模增加而更加穩(wěn)定.由于當前適應(yīng)度值與理論值比較接近而且分配速度可以接受，所以初步說明了算法的可行性.

為驗證算法的收斂特性，取任務(wù)數(shù)為25，種群規(guī)模為50，進行一次仿真實驗，仿真過程中自適應(yīng)遺傳算法(SAGA，the self-adaption genetic algorithm)和標準遺傳算法SGA的適應(yīng)度函數(shù)值變化曲線如圖3所示.

圖3 算法收斂示意圖Fig.3 Schematic diagram of algorithm convergence

由圖2可以得知，SGA算法在第40次迭代左右收斂，陷入局部最優(yōu)；SAGA算法產(chǎn)生了兩次收斂，第一次收斂發(fā)生在第30次迭代左右，第二次收斂發(fā)生在第50次迭代左右，其適應(yīng)度值與第一次收斂時相比出現(xiàn)了一次較大的攀升.這是由于進化過程中SAGA算法可以自適應(yīng)的調(diào)節(jié)交叉、變異算子，當適應(yīng)度值趨于一致或陷入局部最優(yōu)時，較大的Pc和Pm，有利于算法跳出局部最優(yōu).另外，采用精英保留思想改進選擇機制使得最優(yōu)染色體不會被破壞.

為進一步驗證本文提出的資源分配算法，設(shè)定迭代次數(shù)為100，種群規(guī)模為20，將任務(wù)量分別設(shè)定為10、20、30、40和50進行仿真運算，每組任務(wù)量所對應(yīng)場景進行50次仿真并對運算結(jié)果求均值.與標準遺傳算法SGA進行對比，結(jié)果如表5所示.

表5 SGA與SAGA分配結(jié)果比較表Table 5 ComparisonTable of SGA and SAGA distribution results

由表5可以看出，自適應(yīng)遺傳算法SAGA在任務(wù)完成時間和優(yōu)先級方面的分配結(jié)果均優(yōu)于標準遺傳算法SGA.當總?cè)蝿?wù)量較少時，自適應(yīng)遺傳算法SAGA和標準遺傳算法SGA分配結(jié)果比較接近，但是SAGA算法分配結(jié)果均好于SGA算法，原因在于SAGA算法不會輕易陷入局部最優(yōu).當任務(wù)的數(shù)量增大后，資源受限情況下的請求沖突增加，SAGA算法在任務(wù)完成時間和優(yōu)先級方面的分配優(yōu)勢更加明顯，任務(wù)完成時間較標準遺傳算法SGA降低了15.84%，優(yōu)先級方面較標準遺傳算法降低了24.32%，說明自適應(yīng)遺傳算法SAGA對于任務(wù)量大、分配安排復雜的場景可獲得更優(yōu)的分配結(jié)果.

在任務(wù)量為30的情況下，分別對SAGA算法和SGA算法仿真50次.這是因為之前的一次仿真分配結(jié)果不太具有說服力，結(jié)果比較如圖4、圖5所示.

圖4 任務(wù)完成時間Fig.4 Task completion time

圖5 優(yōu)先級逆序數(shù)Fig.5 Priority inverse number

由圖4、圖5可以看出，SAGA算法多次實驗的資源分配結(jié)果在任務(wù)完成時間和優(yōu)先級兩方面均優(yōu)于SGA算法，且多次實驗分配結(jié)果的波動較小，表明本文提出的分配算法具有較強的穩(wěn)定性.

5 結(jié) 論

針對衛(wèi)星網(wǎng)絡(luò)資源分配存在的優(yōu)先級匹配度低，任務(wù)完成時間過長等問題，建立了以全部任務(wù)完成時間最短和任務(wù)序列優(yōu)先級逆序數(shù)最小為目標的約束模型，設(shè)計了一種自適應(yīng)遺傳算法對模型進行求解.本文算法利用精英保留的思想改進了采用輪盤賭策略的選擇算子并且給出了一種能夠自適應(yīng)更新自身概率的變異、交叉算子，解決了標準遺傳算法容易陷入局部最優(yōu)的缺陷，同時能夠避免最優(yōu)解的丟失.仿真實驗驗證表明，本文算法在任務(wù)完成時間方面降低了15.84%，在優(yōu)先級匹配度方面降低了24.32%，有效解決了衛(wèi)星網(wǎng)絡(luò)多資源、多任務(wù)約束下的多目標分配問題.在下一步的工作中，將對資源的種類進行更細致、合理的劃分.本文方法在構(gòu)建模型時，假設(shè)已經(jīng)對子任務(wù)進行了合理劃分，但是子任務(wù)劃分是方法實現(xiàn)的一個關(guān)鍵點，接下來會提出一種子任務(wù)自動劃分方法以提升方法的可行性.