SAGA：一種面向任務的衛星網絡資源分配算法

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

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

1 引 言

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

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

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

2 模型建立

衛星網絡資源分配問題能夠被視為一種多目標約束滿足問題.這類問題求解的關鍵在于如何將對資源的約束描述為條件滿足模型，并采用最優化算法搜索滿足約束模型的解.

2.1 資源池的建立

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

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

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

2.2 參數及決策變量定義

假設衛星網絡中共有s顆衛星，設衛星集為：

sat={sat1,sat2,…,sats}

(1)

由s顆衛星構成的衛星網絡里資源的種類有m種，資源的個數有r個，每種任務在執行時會調用衛星上一定的資源.

假設用戶提交了n個任務，設有任務集為：

Task={Task1,Task2,…,Taskn}

(2)

每個任務包含獨立且保持序關系的Qi個子任務，可以表示為：

Taski={Taski1,Taski2,…,TaskiQi}

(3)

其中Taski的每個子任務都需要遵守序關系.序關系有兩種，“=”表示前后子任務間可以并行執行，“<”表示前面子任務是后面子任務執行的前提，子任務間需要串行執行.兩種序關系同時出現時，任務呈現出混合模態，即：

Taski1=Taski2<…

(4)

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

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

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

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

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

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

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

2.3 多目標約束模型建立

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

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

b)一個任務的某些子任務需要在同一顆衛星上執行；

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

d)子任務間的執行順序可以是串行，并行或混合模態；

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

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

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

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

(6)

3 基于自適應遺傳算法的分配方法

根據衛星網絡資源分配模型生成分配方案并計算目標函數，采用遺傳算法對分配方案進行尋優.現如今遺傳算法已經被廣泛使用并且在約束滿足、組合優化等的相關問題上取得了良好的效果.

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

3.1 編碼與解碼

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

解碼過程：按照編碼序號選擇對應的子任務.

3.2 適應度函數設計

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

(7)

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

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

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

3.4 自適應交叉、變異算子

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

(8)

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

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

計算得到自適應交叉概率Pc和變異概率Pm后，對染色體進行自適應交叉、變異操作.為確保每條染色體中的每個基因出現且僅出現一次，交叉算子采用循環交叉算子，變異算子采用基因對換變異算子.

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

父體A

子體A′

123|4567|89→218|4567|93

父體B

子體B′

452|1876|93→234|1876|59

基因對換變異算子的原理比較簡單，隨機選擇兩個基因對換位置即可.

3.5 算法流程

自適應遺傳算法的具體流程如圖2所示.

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

4 仿真驗證

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

表1 衛星信息表Table 1 Satellite information table

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

表2 設備代碼Table 2 Device code

本次實驗里，統計設備個數是45.1-6號設備是1號返回式偵察衛星具有的資源，7-13號設備是2號光電成像數據傳輸型衛星具有的資源，14-18號設備是3號詳查光電成像數據傳輸型普查衛星具有的資源，19-25號設備是4號合成孔徑雷達偵察衛星具有的資源，26-32號設備是5號靜止氣象衛星具有的資源，33-39號設備是6號極軌氣象衛星具有的資源，40-45號設備是7號傳輸型地球資源衛星具有的資源.里面，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.

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

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

表3 任務屬性舉例Table 3 Examples of task attributes

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

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

為了初步分析分配方法的可行性，我們取前25個任務，90個子任務進行仿真并把初始交叉概率設定為0.8，初始變異概率設定為0.1.每組算例進行50次仿真并對結果求取均值.最終分配結果如表4所示.

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

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

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

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

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

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

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

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

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

圖4 任務完成時間Fig.4 Task completion time

圖5 優先級逆序數Fig.5 Priority inverse number

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

5 結 論

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