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

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

1 引 言

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

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

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

2 模型建立

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

2.1 資源池的建立

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

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

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

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種，資源的個(gè)數(shù)有r個(gè)，每種任務(wù)在執(zhí)行時(shí)會(huì)調(diào)用衛(wèi)星上一定的資源.

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

Task={Task1,Task2,…,Taskn}

(2)

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

Taski={Taski1,Taski2,…,TaskiQi}

(3)

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

Taski1=Taski2<…

(4)

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

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

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

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

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

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

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

2.3 多目標(biāo)約束模型建立

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

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

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

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

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

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

(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}

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

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

(6)

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

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

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

3.1 編碼與解碼

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

解碼過(guò)程：按照編碼序號(hào)選擇對(duì)應(yīng)的子任務(wù).

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

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

(7)

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

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

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

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

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

(8)

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

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

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

循環(huán)交叉算子：對(duì)于兩個(gè)父體A、B，選擇兩個(gè)交叉位置，交叉位置之間的基因片段直接拷貝到子體中，為了得到子體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變異算子的原理比較簡(jiǎn)單，隨機(jī)選擇兩個(gè)基因?qū)Q位置即可.

3.5 算法流程

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

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

4 仿真驗(yàn)證

為驗(yàn)證算法的有效性，我們以偵察任務(wù)為例進(jìn)行分析，設(shè)計(jì)了一個(gè)具有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

本次實(shí)驗(yàn)里，統(tǒng)計(jì)設(shè)備個(gè)數(shù)是45.1-6號(hào)設(shè)備是1號(hào)返回式偵察衛(wèi)星具有的資源，7-13號(hào)設(shè)備是2號(hào)光電成像數(shù)據(jù)傳輸型衛(wèi)星具有的資源，14-18號(hào)設(shè)備是3號(hào)詳查光電成像數(shù)據(jù)傳輸型普查衛(wèi)星具有的資源，19-25號(hào)設(shè)備是4號(hào)合成孔徑雷達(dá)偵察衛(wèi)星具有的資源，26-32號(hào)設(shè)備是5號(hào)靜止氣象衛(wèi)星具有的資源，33-39號(hào)設(shè)備是6號(hào)極軌氣象衛(wèi)星具有的資源，40-45號(hào)設(shè)備是7號(hào)傳輸型地球資源衛(wèi)星具有的資源.里面，1、21是紅外照相機(jī)IC，8、36、41是光譜照相機(jī)SC，2、26、42是可見(jiàn)光相機(jī)VC，7、14、34是多光譜照相機(jī)MSC，19、20、35是雷達(dá)照相機(jī)RC，15、27、40 是紅外攝像機(jī)IV，9、33是多光譜攝像機(jī)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為存儲(chǔ)器R_1，11、43為存儲(chǔ)器R_2，16、25、28為存儲(chǔ)器R_3.

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

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

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

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

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

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

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

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

為驗(yàn)證算法的收斂特性，取任務(wù)數(shù)為25，種群規(guī)模為50，進(jìn)行一次仿真實(shí)驗(yàn)，仿真過(guò)程中自適應(yīng)遺傳算法(SAGA，the self-adaption genetic algorithm)和標(biāo)準(zhǔn)遺傳算法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)度值與第一次收斂時(shí)相比出現(xiàn)了一次較大的攀升.這是由于進(jìn)化過(guò)程中SAGA算法可以自適應(yīng)的調(diào)節(jié)交叉、變異算子，當(dāng)適應(yīng)度值趨于一致或陷入局部最優(yōu)時(shí)，較大的Pc和Pm，有利于算法跳出局部最優(yōu).另外，采用精英保留思想改進(jìn)選擇機(jī)制使得最優(yōu)染色體不會(huì)被破壞.

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

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

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

在任務(wù)量為30的情況下，分別對(duì)SAGA算法和SGA算法仿真50次.這是因?yàn)橹暗囊淮畏抡娣峙浣Y(jié)果不太具有說(shuō)服力，結(jié)果比較如圖4、圖5所示.

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

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

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

5 結(jié) 論

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