2.2 仿真系統(tǒng)工作流程
　　(1)當(dāng)用戶提交一個任務(wù)請求(包含任務(wù)的任務(wù)量,、通信量、任務(wù)提交時間,、時間限度等參數(shù)）時,，觸發(fā)任務(wù)接收器，任務(wù)接收器就將新任務(wù)加入到任務(wù)隊(duì)列排隊(duì),。任務(wù)隊(duì)列按照優(yōu)先級排序,，可以根據(jù)不同用戶的不同需要(用戶等級、任務(wù)緊迫度等)對進(jìn)入隊(duì)列的任務(wù)進(jìn)行排序,。
　　(2)仿真環(huán)境中的計(jì)時器每隔一定時間觸發(fā)任務(wù)調(diào)度器,，任務(wù)調(diào)度器就會從任務(wù)隊(duì)列中取出待處理的任務(wù)，并從資源監(jiān)視器中獲得當(dāng)前系統(tǒng)資源使用情況列表,。
　　(3)根據(jù)待處理任務(wù)及系統(tǒng)資源調(diào)用任務(wù)分配策略器,，產(chǎn)生一個最優(yōu)化的任務(wù)分配表。
　　(4)根據(jù)最優(yōu)化任務(wù)分配表,，調(diào)用任務(wù)分配器,，執(zhí)行任務(wù)分配表中的任務(wù)。如果任務(wù)順利完成,，則將任務(wù)占有的資源釋放并加入到資源列表中,；如果任務(wù)失敗，則釋放該任務(wù)占有的系統(tǒng)資源,，并將失敗的任務(wù)插入到任務(wù)隊(duì)列中,，以待下次調(diào)度。
　　(5)當(dāng)不能從任務(wù)隊(duì)列中獲得任務(wù)時,，表明所有任務(wù)都已經(jīng)完成,，將根據(jù)運(yùn)行中得到的數(shù)據(jù)產(chǎn)生需要的統(tǒng)計(jì)結(jié)果,。
3 螞蟻算法在網(wǎng)格任務(wù)調(diào)度中的應(yīng)用
3.1 改進(jìn)后的螞蟻算法思想
　　當(dāng)一個新資源s加入網(wǎng)格系統(tǒng)時，需要提供其鏈路帶寬r（Mbps）,、CPU個數(shù)m和處理能力p（MIPS）,、磁盤存儲容量f(MB)以及此資源的單位定價k等基本參數(shù)，資源發(fā)現(xiàn)器（類似于GLOBUS中的GIIS）據(jù)此可以初始化該資源的各種信息素（每種信息素對應(yīng)于一個基本參數(shù)）,。在初始化各種信息素之前,，先定義資源中各基本參數(shù)的閾值：
　　r_max=r₀ 　m_max=m₀ p_max=p₀ 　f_max=f₀ 　k_max=k₀
　　并規(guī)定：如果資源的各參數(shù)值超過閾值，則統(tǒng)一以閾值進(jìn)行后面的計(jì)算,。
　　然后初始化各種信息素：
　　T_sr(0)=r/r₀*100%　　　　　　　鏈路帶寬r的信息素
　　T_sm(0)=(m*p)/(m₀*p₀)*100%　　CPU計(jì)算能力的信息素
　　T_sf(0)=f/f₀*100% 　　　　　　磁盤存儲容量f的信息素
　　T_sk(0)=k/k₀*100% 　　　　　　資源的單位定價k的信息素 　　　(1)
　　則資源s的初始化總信息素為：
　　T_s(0)=a*T_sr(0)+b*T_sm(0)+c*T_sf(0)+d*T_sk(0)　　　　　　　　　　(2)
　　其中,，a+b+c+d=1，a,，b,，c，d分別表示鏈路帶寬信息素,、CPU計(jì)算能力信息素,、磁盤存儲容量信息素以及資源的單位定價信息素在該資源總信息素中所占的比重。
　　每當(dāng)有新資源加入網(wǎng)格系統(tǒng),，或某資源退出或者掉線,，或任務(wù)成功或失敗返回時，資源信息素都會隨之改變：T_s^new=g*T_s^old+△T_s,，△T_s是信息素改變量,，g表示信息素持久性（取0.6），1-g表示信息素的揮發(fā)性^[7],。
　　當(dāng)任務(wù)從資源s成功返回時,，△T_s=Ce*K，Ce是獎勵參數(shù),，取0.6,，表示增加成功經(jīng)驗(yàn)；當(dāng)任務(wù)從資源s失敗返回時,，△Ts=Cp*K,，Cp是懲罰因子，取-1.2.
資源信息素改變時,，任務(wù)分配概率隨之改變：
　　
　　式中,，T_s(t)為時間t時資源s的信息素濃度，η_s表示資源s的固有屬性,，η_s=T_s(0),；α表示信息素的重要性，β表示資源固有屬性的重要性。
3.2 改進(jìn)后的螞蟻算法流程
　　基于上面的公式和思想,，設(shè)計(jì)了下面的用于網(wǎng)格系統(tǒng)中任務(wù)調(diào)度的算法，該算法分為9個步驟：
　　(1)利用公式（1）初始化所有資源的各種信息素,，利用公式（2）初始化各資源的總信息素,。
　　(2)調(diào)度器接收當(dāng)前從用戶發(fā)送來的實(shí)驗(yàn)數(shù)據(jù)，即隨機(jī)任務(wù),。
　　(3)對當(dāng)前實(shí)驗(yàn)的每個任務(wù),，依據(jù)其分配給每個資源的概率判斷使用哪個資源。具體做法是以下(4)～(6),。
　　(4)利用公式：
　　
　　算出該任務(wù)分配給每個資源的概率,。其中，ηs表示資源s的固有屬性,，ηs=Ts(0),；T_s(t)是資源s的信息素濃度；α表示信息素的重要性,，取α=0.5,；β表示資源固有屬性的重要性；u代表系統(tǒng)中所有可用資源,。
　　(5)依據(jù)概率將任務(wù)分配給一個資源,。
　　(6)利用公式：
　　Tsr(t′)=Ts(t)*p-0.0005L1
　　Tsr(t)=Tsr(t′)
　　Tsm(t′)=Ts(t)*p-0.0005L2
　　Tsm(t)=Tsm(t′)
　　對鏈路帶寬信息素、CPU計(jì)算能力信息素進(jìn)行更新,。而磁盤容量信息素及資源單位定價信息素暫時不變,。其中，L₁,，L₂為任務(wù)的通信量及計(jì)算量,。然后根據(jù)公式：Ts(t)=a*Tsr(t)+b*Tsm(t)+c*Tsf(t)+d*Tsk(t)將該資源的信息素進(jìn)行更新。
　　(7)將當(dāng)前實(shí)驗(yàn)的所有任務(wù)都分配給資源后,，則等待任務(wù)的返回,。如果任務(wù)成功返回，則利用以下公式：
　　Tsr(t+1)=p*Tsr(t)+0.6*L₁
　　Tsm(t+1)=p*Tsm(t)+0.6*L₂
　　Tsf(t+1)=p*Tsf(t)+0.6*L₃
　　Tsk(t+1)=Tsk(t)
　　Ts(t+1)=a*Tsr(t+1)+b*Tsm(t+1)+c*Tsf(t+1)+d*Tsk(t+1)
　　對該資源的信息素進(jìn)行更新,。其中,，L3為任務(wù)在計(jì)算過程中占用磁盤容量最大時的值。
　　如果任務(wù)失敗返回,，則利用公式：
　　T_sr(t+1)=p*T_sr(t)-1.2*L₁
　　T_sm(t+1)=p*T_sm(t)-1.2*L₂
　　T_sf(t+1)=p*T_sf(t)-1.2*L₃
　　T_sk(t+1)=T_sk(t)
　　Ts(t+1)=a*T_sr(t+1)+b*T_sm(t+1)+c*T_sf(t+1)+d*T_sk(t+1)
　　對該資源的信息素進(jìn)行更新,。
　　(8)重復(fù)（3）～（7），直到當(dāng)前實(shí)驗(yàn)的所有任務(wù)都成功返回為止,。
　　(9)重復(fù)(2)～(8),，直到所有用戶實(shí)驗(yàn)都被處理完為止。
3.3 負(fù)載平衡因子的添加
　　當(dāng)某個資源負(fù)載很重時，很容易成為網(wǎng)格計(jì)算的瓶頸,，影響所有任務(wù)的及時完成,。改進(jìn)后的螞蟻算法，在很大程度上實(shí)現(xiàn)了負(fù)載平衡,。為了取得更好的負(fù)載平衡效果,，要不斷地探測資源的負(fù)載及其任務(wù)完成情況，以便對以后新任務(wù)的分配產(chǎn)生積極的影響,。同時通過把各資源的負(fù)載完成率的差值控制在一個較小的門限之內(nèi)以保證負(fù)載均衡,。本文在螞蟻算法中引入一個負(fù)載平衡因子λ。
　　λ=u/Ts(0)
　　式中,，u為資源上尚未完成的任務(wù)量,，而Ts(0)基本上可以代表某資源的處理能力。
　　每次任務(wù)完成時的信息素改變量為△Ts+c/λ(c為調(diào)節(jié)因子),，即如果對未完成任務(wù)中所需處理時間長的節(jié)點(diǎn),，將資源信息素降低一些，則所需處理時間短的節(jié)點(diǎn)信息素就增加一些,。這樣就能保證任務(wù)負(fù)載率盡快逼近同一個值,，在以后分配任務(wù)的過程中，系統(tǒng)的負(fù)載均衡能力就會得到進(jìn)一步提高,。
4 實(shí)驗(yàn)結(jié)果
　　在仿真平臺下,，用8個資源和800個任務(wù)進(jìn)行模擬實(shí)驗(yàn)。資源情況如表1所示,，任務(wù)計(jì)算量為2000M～10000M,，數(shù)據(jù)通信量在10M～100M。

?

　　圖2給出了各資源的初始總信息素(其中,，取a=0.2,，b=0.5，c=0.2,，d=0.1),。初始總信息素基本上代表了這個資源的處理能力。
　　如圖3所示,，所有資源的任務(wù)量與資源處理能力之比基本相同,。任務(wù)最終完成情況與資源的處理能力成正比，性能好的資源分到了更多的任務(wù),。同時由此圖與資源列表可以分析出,，任務(wù)的調(diào)度受處理器個數(shù)、處理器計(jì)算能力影響較大,。而當(dāng)磁盤容量滿足任務(wù)存儲需求時,，其差別可以忽略不計(jì),。