基于改進蟻群算法的遙感信息處理負載均衡任務(wù)調(diào)度算法研究

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

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

0 引言

遙感信息處理服務(wù)組合面臨的關(guān)鍵問題在于對用戶需求、遙感信息及其處理服務(wù)語義關(guān)聯(lián)的充分準確理解，并在組合過程中利用這些語義控制處理服務(wù)的選擇和構(gòu)成復(fù)雜結(jié)構(gòu)的服務(wù)鏈。遙感信息多任務(wù)服務(wù)鏈在線整合是一個并發(fā)執(zhí)行調(diào)度服務(wù)與分布處理服務(wù)的過程，在多源異構(gòu)與時空分布不均衡、網(wǎng)絡(luò)環(huán)境動態(tài)多變、處理節(jié)點負載不均衡的服務(wù)執(zhí)行環(huán)境中，遙感信息處理調(diào)度策略對于系統(tǒng)執(zhí)行的整體性能最優(yōu)至關(guān)重要。

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

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

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

1 蟻群算法

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

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

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

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

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

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

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

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

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

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

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

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

圖1 蟻群算法流程圖

2 基于改進蟻群算法的遙感信息處理服務(wù)負載均衡任務(wù)調(diào)度算法

用戶通過終端發(fā)出任務(wù)指令以后，需要對用戶的任務(wù)需求進行快速地分析處理，來幫助用戶高效快速地獲得所需要的遙感信息產(chǎn)品，而遙感信息服務(wù)鏈動態(tài)構(gòu)建技術(shù)即是來解決這一問題。遙感信息處理服務(wù)鏈是指從終端提出需求、衛(wèi)星獲取、處理、傳輸、信息分發(fā)到終端的信息節(jié)點構(gòu)成的一條動態(tài)鏈路。

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

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

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

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

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

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

在當前狀態(tài)i生成狀態(tài)j后，如果新的狀態(tài)j的內(nèi)能小于原狀態(tài)i的內(nèi)能，即Ej

接受新狀態(tài)j，其中k為玻爾茲曼常數(shù)，這一準則稱為Metropolis準則。

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

模擬退火算法的初始參數(shù)包括：

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

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

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

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

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

圖2 模擬退火算法流程圖

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

基于改進蟻群算法的任務(wù)調(diào)度算法流程如圖3所示。

圖3 基于改進蟻群算法的負載調(diào)度算法流程圖

3 仿真實驗

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

3.1 仿真平臺介紹

仿真實驗是在云計算仿真平臺CloudSim環(huán)境下進行的。云計算仿真平臺CloudSim是一個基于離散事件的云計算仿真工具箱。CloudSim是在網(wǎng)格仿真平臺GridSim的基礎(chǔ)上開發(fā)的，提供各種異構(gòu)云計算資源、用戶、調(diào)度算法等的模擬與仿真。

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

1)仿真初始化；

2)創(chuàng)建云計算資源和任務(wù)；

3)編寫任務(wù)調(diào)度算法；

4)仿真啟動；

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

3.2 實驗場景設(shè)計

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

表1 算法各項參數(shù)設(shè)置

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

表2 CloudSim屬性設(shè)置

3.3 實驗結(jié)果及分析

圖4為使用不同種算法調(diào)度各組任務(wù)的總完成時間。

圖4 各算法執(zhí)行不同任務(wù)數(shù)的總完成時間

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

為比較各節(jié)點在執(zhí)行任務(wù)中的負載情況，在實驗過程中記錄下每個節(jié)點運行任務(wù)的總長度，針對每個節(jié)點計算其負載的任務(wù)總長度與其計算能力的比值。以執(zhí)行100個任務(wù)時產(chǎn)生的實驗數(shù)據(jù)為例，將得出的結(jié)果繪制如下統(tǒng)計圖：

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

圖5 任務(wù)數(shù)為100個時各算法的節(jié)點負載均衡情況

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

4 結(jié)束語

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