基于改進蟻群算法的遙感信息處理負載均衡任務調度算法研究

趙 斐,陳 昊,白建東,劉 鐵

(北京跟蹤與通信技術研究所，北京 100094)

0 引言

遙感信息處理服務組合面臨的關鍵問題在于對用戶需求、遙感信息及其處理服務語義關聯的充分準確理解，并在組合過程中利用這些語義控制處理服務的選擇和構成復雜結構的服務鏈。遙感信息多任務服務鏈在線整合是一個并發執行調度服務與分布處理服務的過程，在多源異構與時空分布不均衡、網絡環境動態多變、處理節點負載不均衡的服務執行環境中，遙感信息處理調度策略對于系統執行的整體性能最優至關重要。

自適應負載均衡是指無論系統處于空閑、穩定還是繁忙狀態，負載均衡算法都會自動評估系統的服務能力，進行合理的資源分配，使整個系統始終保持較好的性能，不產生饑餓或者過載、宕機。自適應負載均衡有兩個主要目標：保持較短的請求響應時間和較小的請求阻塞概率；負載均衡算法在可控級別，不占用過多的 CPU、網絡等資源。自適應負載均衡建立在現有網絡結構之上，它提供了一種廉價有效透明的方法擴展網絡設備和服務器的帶寬、增加吞吐量、加強網絡數據處理能力、提高網絡的靈活性和可用性，使用自適應負載均衡能夠更合理的利用資源，提高運行性能[1-4]。

現有的自適應負載均衡算法主要分為靜態和動態兩類。靜態負載均衡算法以固定的概率分配任務，不考慮服務器的狀態信息，如輪轉算法、加權輪轉算法等，所以靜態負載均衡算法不適合遙感信息服務鏈的優化與服務資源配置。動態負載均衡算法以服務器的實時負載狀態信息來決定任務的分配，如最小連接法[5-7]、加權最小連接法[8-10]等，但是上述算法考慮的影響輸入因子比較少，而且權值無法自動選擇確定，所以對遙感信息服務鏈的優化也不適合。

本文提出了一種改進蟻群算法(EXACO)的整合負載自適應分配算法進行遙感信息服務鏈的優化與服務資源配置。蟻群算法(ACO,ant colony optimization)是一種用來在圖中尋找優化路徑的隨機搜索尋優技術，它由意大利學者Marco Dorigo于1992年在他的博士論文中引入，蟻群算法在求解多種組合優化問題中獲得了廣泛的應用，如在計算機技術應用中，它可以作為網絡路由控制的工具；在交通控制中，它成功地解決了車輛調度問題；在圖表制作中，它被用來解決顏色填充問題。而為了使蟻群算法在進行任務調度時在不陷入局部最優解的前提下盡可能加速收斂，本文提出了一種改進的蟻群算法，引入模擬退火算法的思想對原有的蟻群算法做出一定修改：當螞蟻k發現了一條最優路徑并形成最優解X*后，隨機交換兩個資源所執行的任務作為擾動，產生一個新解X，通過模擬退火算法的方式決定保留最優解X*還是用新解X替換最優解X*；同時將改進蟻群算法應用于遙感信息服務鏈處理系統中去，從而實現遙感信息服務在線協同調度優化執行。

1 蟻群算法

蟻群算法的誕生主要來源于自然界螞蟻覓食行為。螞蟻的視覺十分有限，但卻能依靠蟻群中每只螞蟻在路徑上釋放的“信息素”這種物質在“黑暗”的外界環境中尋找到從洞穴通向食物的最短路徑。螞蟻在行走過程中不斷地釋放信息素來標識自己的行徑，在尋找食物的過程中不斷根據信息素的濃度選擇行走的方向，最終到達食物所在的地方。由于每一只螞蟻都有著各自不確定的行動路徑，這導致較短路徑上爬行的螞蟻數量會比較長路徑上爬行的螞蟻數量多，從而使得較短路徑上被螞蟻釋放的信息素濃度越高，后出發的螞蟻總是趨向于往信息素濃度高的地方爬行。隨著時間的推移，越來越多的螞蟻聚集到最短的路徑上去，這種動態的正反饋機制使得蟻群算法具有很好的魯棒性。

蟻群算法最早用于解決著名的旅行商問題[11-12]，該問題可被描述為：某商人從一座城市出發，途徑n座城市，最后再回到出發的城市，并且每座城市必須且只能經過一次，求一種旅行方案使得所需路徑最短。該問題的數學描述為：設n座城市組成的集合為C={c1,c2,...,cn}，每兩座城市之間的道路為R={rij|ci,cj∈C}，G=(C,R)是一個有向圖，求有向圖G的一條最短漢密爾頓回路[13]。

當螞蟻k(k=1,2,...,m)出發尋找城市之間的最短路徑時，會根據每條鄰近路徑上的信息素濃度來確定下一步通過哪條路徑前往下一座城市。為了防止螞蟻重復經過已到達過的城市，引入禁忌表tabuk(k=1,2,...,m)來表示螞蟻k已經經過的城市，集合allowedk={0,1,...,n-1}-tabuk表示螞蟻k下一步允許選擇的城市，這一約束在自然界中的螞蟻身上并不存在。螞蟻k根據以下公式選擇下一個到達的城市：

為了防止信息素在路徑上的過度積累導致算法提前達到終止條件而結束，需要不斷更新信息素。在τ+n時刻，路徑rij上的信息素更新依據以下公式：

τij(t+n)=ρ*τij(t)+Δτij

其中:Q為常數，Lk表示螞蟻k在本次循環中途經的總路程，參數α,β表示螞蟻在運動中積累的信息和啟發式因子在螞蟻選擇路徑時所起的不同作用。初始時刻τij(0)為常數C，并且Δτij=0。參數Q、C、α、β、ρ均可以用實驗的方式確定最優的組合。至于算法的停止條件，則可以設定為超過固定的循環次數或進化趨勢不明顯。

相較于遺傳算法等其他啟發式算法，蟻群算法具有以下特點[14-16]：

1)魯棒性強。在算法的運算過程中，如果系統的狀態發生了改變，蟻群算法仍然可以進行自我調整。例如蟻群當前的路徑上出現了不可逾越的障礙物，蟻群仍然能夠在一段時間的調整后重新找到新的路徑。

2)自組織。蟻群中的螞蟻在剛開始覓食時隨機并且無序地尋找各自的路徑，但隨著時間的推移，每只螞蟻個體之間通過信息素的作用開始互相影響，最后趨向于最優化的路徑。

3)可并行。蟻群中每個螞蟻個體的行為互不干擾，僅僅通過路徑上的信息素進行通信，因此蟻群算法從本質上具備并行性，易于并行實現以改善算法性能。

4)擴展性強。蟻群算法可以與模擬退火算法等多種啟發式算法結合使用，因此具備多種拓展后的變種蟻群算法。

蟻群算法的基本流程如圖1所示。

圖1 蟻群算法流程圖

2 基于改進蟻群算法的遙感信息處理服務負載均衡任務調度算法

用戶通過終端發出任務指令以后，需要對用戶的任務需求進行快速地分析處理，來幫助用戶高效快速地獲得所需要的遙感信息產品，而遙感信息服務鏈動態構建技術即是來解決這一問題。遙感信息處理服務鏈是指從終端提出需求、衛星獲取、處理、傳輸、信息分發到終端的信息節點構成的一條動態鏈路。

服務鏈動態構建包含兩方面內容：依據任務的重要性對單個節點的執行序列動態調整，根據各節點的能力狀況對鏈路動態調整。滿足遙感信息“按需保障、隨時隨地保障”的需求，需要動態構建服務鏈，包括對衛星、星群的調度完成數據獲取，動態調度鏈路上計算資源對獲取到的(光學、SAR)數據進行處理生成數據產品等。服務鏈動態構建技術難點在于遙感信息處理涉及的服務鏈中星上處理能力，中間節點計算、存儲及處理能力，端群的計算處理能力，網絡節點多，可用能力動態變化，如何高效、快速完成信息處理。

負載均衡主要是進行合理的資源分配，使整個系統始終保持較好的性能，不產生饑餓或者過載、宕機。負載均衡任務調度問題可以被描述為：求一種最優的任務分配策略，將n個長度不等的任務T={T1,T2,...,Tn}按照某一策略分配給m個處理能力不同的服務節點S={S1,S2,...,Sm}，并且使n個任務的總完成時間C=max{c1,c2,...cm}達到最短。每一種分配策略都對應著該問題的一個可行解X，而具有最小完成時間的分配策略就是該問題的最優解。

蟻群算法適合解決各種離散問題，但是當問題規模較大時，蟻群算法在實際運用中容易遇到收斂速度慢、易陷入局部最優解的情況。使用基本的蟻群算法能夠較好地解決任務調度問題，但是在實際應用過程中，可以針對特定的任務調度問題進行一定的策略和算法優化。

因此，將完成任務的時間跨度和節點負載均衡度綜合起來作為衡量指標的目標函數為F(X)=LB(X)*C(X)。

為了使蟻群算法在進行任務調度時在不陷入局部最優解的前提下盡可能加速收斂，引入模擬退火算法的思想對原有的蟻群算法做出一定修改。

模擬退火算法(simulated annealing algorithm)最早由S.Kirkpatrick等人于1983年提出，是一種通用概率演算法。模擬退火算法的思想來源于固體退火的場景：當一個固體被加熱到很高的溫度后，便進入緩慢的冷卻。在其升溫階段，固體內部的粒子隨著溫度的不斷升高而變得無序，同時內能也在不斷增大；在降溫階段則恰恰相反，固體內部的粒子會逐漸趨于有序。當冷卻時間足夠長，冷卻過程中的任一溫度下固體都處于熱平衡狀態。最終固體冷卻到最低溫度時其內能也達到最小[17-19]。自然界總是趨于能量最低，而分子熱運動則趨于破壞這種能量最低的狀態。基于這一理論，通過熱平衡狀態把內能最小化作為優化目標的算法就是模擬退火算法[20]。

在當前狀態i生成狀態j后，如果新的狀態j的內能小于原狀態i的內能，即Ej

接受新狀態j，其中k為玻爾茲曼常數，這一準則稱為Metropolis準則。

若將溫度T作為控制參數，待優化的目標函數f作為內能E，固體處于某一溫度Tx下的狀態對應一個解x，則可將固體退火的思想應用于求解優化問題中。通過控制參數T的逐漸降低，目標函數f也隨之降低，直至趨于全局最小值[21]。

模擬退火算法的初始參數包括：

1)控制參數T的初始值T0，即冷卻開始時的溫度；

2)控制參數T的衰減函數，最常見的一種衰減函數為Tk+1=<λTk，k=0,1,2，…。其中λ為常數，也稱為退火系數，通常其取值范圍為[0.5，0.99]；

3)控制參數T的終止值；

4)馬爾科夫鏈的長度L，即任一溫度T下的迭代參數。

模擬退火算法的基本流程如圖2所示。

圖2 模擬退火算法流程圖

引入模擬退火算法思想當螞蟻k發現了一條最優路徑并形成最優解X*后，隨機交換兩個資源所執行的任務作為擾動，產生一個新的解X，通過模擬退火算法的方式決定保留最優解X*還是用新解X替換最優解X*：若ΔF=F(X)-F(X*)<0，則用新解X替換最優解X*；否則若ΔF=F(X)-F(X*)>0，則在0～1分布上依概率e-ΔF/T,決定是否用新解X替換最優解X*。其中，T為退火溫度，初始值為T0，終止值為Tend。退火溫度T按照T(t+1)=αT(t)進行迭代，其中α為退火系數。退火溫度衰減到終止值時結束模擬退火過程，并依照蟻群算法信息素更新公式利用模擬退火過程得出的最優解X*更新路徑上信息素，結束本次循環。當循環執行次數達到蟻群算法的最大迭代次數上限時，結束整個循環并輸出結果。

基于改進蟻群算法的任務調度算法流程如圖3所示。

圖3 基于改進蟻群算法的負載調度算法流程圖

3 仿真實驗

為驗證基于蟻群算法的整合負載自適應分配算法在遙感信息多任務服務鏈在線優化場景中的應用效果，通過云計算仿真平臺，設定貼近遙感信息多任務服務鏈處理場景的任務負載、系統資源和調度算法，驗證本文提出的基于蟻群算法的整合負載自適應分配算法的優化效果，并與傳統遙感信息多任務服務調度方法的效果進行比對。

3.1 仿真平臺介紹

仿真實驗是在云計算仿真平臺CloudSim環境下進行的。云計算仿真平臺CloudSim是一個基于離散事件的云計算仿真工具箱。CloudSim是在網格仿真平臺GridSim的基礎上開發的，提供各種異構云計算資源、用戶、調度算法等的模擬與仿真。

基于CloudSim平臺仿真的主要步驟如下：

1)仿真初始化；

2)創建云計算資源和任務；

3)編寫任務調度算法；

4)仿真啟動；

5)仿真結束，輸出任務完成情況，對結果進行分析與評價。

3.2 實驗場景設計

基于改進蟻群算法的任務調度算法中的a，b，c分別代表節點的計算能力、內存和磁盤容量的重要性。一般來說，任務的執行受CPU的處理能力的影響較大，因此將a，b，c三個參數的值分別設為0.6，0.2，0.2。算法中蟻群算法部分的信息素揮發系數影響著算法的全局搜索能力和收斂速度兩項指標，綜合考慮后將其確定為0.5。參數α與β分別決定了信息素和匹配因子的重要程度，螞蟻數量m決定迭代的次數，退火系數λ決定退火的速度。根據經驗取參數α=1，β=2，m=10，λ=0.95，T0=10 000，Tend=1 000。

表1 算法各項參數設置

為對比不同算法的任務調度效果，選擇輪詢算法、遺傳算法和改進蟻群算法進行比較。在仿真開始前，利用CloudSim Plus創建20個節點。為模擬真實環境，每個節點具有的計算能力采用隨機生成，分布于1 000至6 000 MIPS之間。根據任務數的不同，隨機生成任務長度同樣采用隨機的方式生成，分布于50 M至200 M之間。根據任務數量的不同將實驗分成五組，五組實驗的任務數分別為100、200、300、400、500。為盡量降低隨機數據的偶然性對實驗結果的影響，多次進行實驗并取平均值作為每組實驗的結果。

表2 CloudSim屬性設置

3.3 實驗結果及分析

圖4為使用不同種算法調度各組任務的總完成時間。

圖4 各算法執行不同任務數的總完成時間

圖4中橫坐標表示每組實驗的任務數，縱坐標表示各組任務在分別不同調度算法下的總完成時間。由圖可知，基于改進遺傳算法的調度結果較其他對比算法具有更低的總完成時間。同時，隨著任務數的增多，該算法的優勢越來越顯著。

為比較各節點在執行任務中的負載情況，在實驗過程中記錄下每個節點運行任務的總長度，針對每個節點計算其負載的任務總長度與其計算能力的比值。以執行100個任務時產生的實驗數據為例，將得出的結果繪制如下統計圖：

圖5中，以“■”標記的折線反映了使用輪詢算法調度任務后各節點的負載情況，以“●”標記的折線反映了使用遺傳算法調度任務后各節點的負載情況，以“▲”標記的折線反映了使用改進后的遺傳算法調度任務后各節點的負載情況。由上圖可知，輪詢算法與蟻群算法在進行任務調度時由于沒有充分考慮節點的負載均衡問題，各節點的負載水平相差很大，這一點在使用遺傳算法后得到了些許改善，但我們可以很明顯地看到使用改進后的蟻群算法時，各節點的負載程度相對均衡。為定量對比上述算法在負載均衡方面的表現，可以使用標準差來分析上述數據，如下公式：

圖5 任務數為100個時各算法的節點負載均衡情況

分析以上實驗結果可以得出，遺傳算法和改進的蟻群算法相較于輪詢算法而言，在任務總完成時間和節點負載均衡性上都有較好的表現。輪詢算法由于其簡單的策略，不可避免地會出現將較長的任務分配給計算能力較弱的節點的情況，造成任務的堆積，而延長了全部任務的總完成時間，這樣還會造成系統中各節點負載不均衡。遺傳算法相較于輪詢算法能夠在一定程度上優化任務的分配，使得全部任務的總完成時間減少。基于改進的蟻群算法較好地避免了蟻群算法容易陷入局部最優解的問題，并且進一步減少了任務總完成時間。同時，在任務分配時考慮了節點實際負載情況，使得系統中各節點的負載趨于平衡。實驗結果表明，基于改進蟻群算法的負載調度算法在針對遙感信息服務鏈處理調度的場景下具備更優的效果。

4 結束語

本文提出了一種改進蟻群算法(EXACO)的整合負載自適應分配算法進行遙感信息服務鏈的優化與服務資源配置，該算法完成遙感信息多任務處理服務鏈的計算任務分配，提升數據處理系統整體的處理效率和負載均衡度，能夠支撐面向遙感信息支援保障的處理服務鏈動態構建技術的研究。