徐 琳,曲仕茹,魚 濱

(1.西北工業(yè)大學(xué)自動(dòng)化學(xué)院,陜西西安 710129; 2.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

ITSGrid資源調(diào)度策略的研究

徐 琳1,曲仕茹1,魚 濱2

(1.西北工業(yè)大學(xué)自動(dòng)化學(xué)院,陜西西安 710129; 2.西安電子科技大學(xué)計(jì)算機(jī)學(xué)院,陜西西安 710071)

定義了系統(tǒng)負(fù)載均衡評(píng)價(jià)值和資源節(jié)點(diǎn)滿意度評(píng)價(jià)模型,并在此基礎(chǔ)上設(shè)計(jì)了一種分布式資源自適應(yīng)調(diào)度算法(GLBCQ),同時(shí)兼顧全局負(fù)載均衡和用戶自定義的服務(wù)質(zhì)量,可根據(jù)智能交通系統(tǒng)計(jì)算任務(wù)的自定義服務(wù)質(zhì)量需求,結(jié)合當(dāng)前智能交通系統(tǒng)網(wǎng)格的系統(tǒng)負(fù)載狀況,為提交的任務(wù)自適應(yīng)地選擇最優(yōu)資源.仿真實(shí)驗(yàn)結(jié)果表明,GLBCQ算法具有更高的效率和自適應(yīng)性,能夠促進(jìn)智能交通系統(tǒng)網(wǎng)格的系統(tǒng)負(fù)載均衡以及整體性能的提升.

智能交通系統(tǒng)網(wǎng)格;資源調(diào)度算法;自定義服務(wù)質(zhì)量需求;系統(tǒng)負(fù)載

隨著社會(huì)的發(fā)展,交通需求也隨之快速增長(zhǎng),對(duì)現(xiàn)有的智能交通系統(tǒng)(ITS)應(yīng)用提出更多更高的要求.為了更好地支持ITS的各類計(jì)算服務(wù),高效管理ITS中海量具有分布性、異構(gòu)型、自治性和動(dòng)態(tài)性[1]等復(fù)雜特征的計(jì)算資源,智能交通系統(tǒng)網(wǎng)格(Intelligent Transportation System Grid,ITSGrid)應(yīng)運(yùn)而生,且被視為解決分布式異質(zhì)性環(huán)境下ITS應(yīng)用問(wèn)題的一種理想方案.目前,ITSGrid平臺(tái)所支持的計(jì)算服務(wù)的規(guī)模越來(lái)越大,計(jì)算服務(wù)所涉及的資源越來(lái)越多,計(jì)算服務(wù)的種類越來(lái)越多元化,并且不同的ITS計(jì)算服務(wù)分屬不同的應(yīng)用類型,具有各自的特征.即使是同屬于一個(gè)應(yīng)用類型的不同計(jì)算服務(wù),也可能有各自的服務(wù)質(zhì)量(Quality of Service,QoS)需求.由此可見(jiàn),智能交通系統(tǒng)網(wǎng)格應(yīng)用中QoS的協(xié)商和保證是一項(xiàng)非常復(fù)雜和具有挑戰(zhàn)性的工作[2].因此,如何有效地進(jìn)行分布式資源調(diào)度是ITSGrid應(yīng)用所面臨的重要問(wèn)題,也是保證ITS應(yīng)用的QoS、高效利用分布式ITS資源和提高ITSGrid系統(tǒng)整體性能的關(guān)鍵.為此,筆者設(shè)計(jì)了一種分布式資源自適應(yīng)調(diào)度算法GLBCQ,可根據(jù)ITS計(jì)算任務(wù)的自定義QoS的需求,結(jié)合ITSGrid系統(tǒng)實(shí)時(shí)負(fù)載狀況,為ITS計(jì)算任務(wù)自動(dòng)選擇最優(yōu)資源,從而實(shí)現(xiàn)既滿足計(jì)算服務(wù)的自定義QoS的需求、又兼顧ITSGrid整體性能的目標(biāo).

1 ITSGrid資源調(diào)度問(wèn)題的特點(diǎn)

在ITSGrid中,資源調(diào)度的對(duì)象廣泛分布,經(jīng)常需要跨越多個(gè)管理域.不同的ITS子系統(tǒng)或交通參與部門采用不同策略管理各自的資源,甚至存在資源用戶和資源提供者的目的分歧相互抵觸的現(xiàn)象.這些分布式資源所提供的QoS是多層次的,ITSGrid用戶在很大程度上需要依賴遠(yuǎn)程資源提供最后的QoS,以實(shí)現(xiàn)計(jì)算任務(wù)的應(yīng)用約束.

ITSGrid是一個(gè)多資源多任務(wù)的環(huán)境.在此類環(huán)境中,資源調(diào)度問(wèn)題本質(zhì)上是為計(jì)算任務(wù)的執(zhí)行而選擇和確定ITS資源.ITS資源與計(jì)算任務(wù)之間可能存在一對(duì)一、一對(duì)多、多對(duì)一,甚至多對(duì)多的關(guān)系,兩者之間的映射關(guān)系是一個(gè)NP完全問(wèn)題[3].因此,ITSGrid的資源調(diào)度系統(tǒng)在進(jìn)行分布式資源選擇時(shí)可能存在多種問(wèn)題,需要根據(jù)不同的問(wèn)題制定相應(yīng)的解決方案,應(yīng)充分考慮計(jì)算任務(wù)自定義QoS要求和ITSGrid系統(tǒng)負(fù)載均衡,按照調(diào)度策略在計(jì)算任務(wù)和分布式資源之間找到一個(gè)理想的匹配.

2 ITSGrid資源調(diào)度策略

目前,國(guó)內(nèi)外已出現(xiàn)了許多成熟的關(guān)于通用網(wǎng)格的分布式資源調(diào)度策略,其中較為經(jīng)典的調(diào)度策略有隨機(jī)負(fù)載平衡(OLB)、最短完成時(shí)間(MCT)、最短執(zhí)行時(shí)間(MET)、切換算法(SA)和百分比K最佳啟發(fā)式(KPB)等.雖然這些經(jīng)典的調(diào)度策略在實(shí)際應(yīng)用中已展現(xiàn)了各自的效果,但是這些模型和算法也存在一定的局限性,例如它們大多只部分地考慮了眾多系統(tǒng)級(jí)QoS要求,在調(diào)度中逐個(gè)匹配相關(guān)參數(shù)實(shí)現(xiàn)資源的選擇[4],與特定的應(yīng)用系統(tǒng)或應(yīng)用特征高度耦合.更關(guān)鍵的是,所有的算法均不考慮應(yīng)用任務(wù)的個(gè)性化資源QoS需求.

因此,在設(shè)計(jì)ITSGrid資源調(diào)度的策略時(shí),需要重點(diǎn)考慮以下兩個(gè)方面:

(1)來(lái)自計(jì)算任務(wù)的應(yīng)用級(jí)QoS需求.在ITSGrid中,不同的大規(guī)模應(yīng)用計(jì)算任務(wù)往往具有不同的QoS需求,如CPU速度最快、可用內(nèi)存最大、網(wǎng)絡(luò)延遲最小、使用費(fèi)用最少等.

(2)來(lái)自ITSGrid系統(tǒng)的全局級(jí)QoS需求,通常反映為全局級(jí)的吞吐量和效率等指標(biāo).一般情況下, ITSGrid系統(tǒng)的全局級(jí)QoS需求可通過(guò)引入全局負(fù)載共享的機(jī)制來(lái)實(shí)現(xiàn).

因此,在為ITSGrid設(shè)計(jì)資源調(diào)度算法時(shí),需同時(shí)考慮以上兩個(gè)方面的需求,做到既尊重ITSGrid中各類計(jì)算任務(wù)的自定義QoS需求,又充分考慮ITSGrid系統(tǒng)本身的全局級(jí)QoS需求,根據(jù)ITSGrid資源負(fù)載情況,自適應(yīng)地調(diào)整全局級(jí)QoS需求在分布式資源調(diào)度過(guò)程中的權(quán)重.

2.1 ITSGrid負(fù)載均衡評(píng)價(jià)模型

對(duì)于ITSGrid這種高復(fù)雜性、超大規(guī)模的綜合性網(wǎng)格,一個(gè)理想的資源調(diào)度系統(tǒng)應(yīng)能在分布式資源調(diào)度過(guò)程中,將計(jì)算任務(wù)盡可能均衡地分配到ITSGrid中各個(gè)資源節(jié)點(diǎn)上,從而實(shí)現(xiàn)ITSGrid全局級(jí)的負(fù)載共享與均衡,保證系統(tǒng)整體性能的高效.由此可見(jiàn),ITSGrid系統(tǒng)全局級(jí)負(fù)載的均衡程度是分布式資源調(diào)度效果的直接體現(xiàn)[5].在ITSGrid的資源調(diào)度系統(tǒng)中引入系統(tǒng)負(fù)載均衡評(píng)價(jià)技術(shù),將有助于資源調(diào)度系統(tǒng)的自適應(yīng)性,以實(shí)現(xiàn)ITSGrid全局級(jí)的負(fù)載共享與均衡.因此,系統(tǒng)負(fù)載均衡評(píng)價(jià)對(duì)ITSGrid的應(yīng)用具有十分重要的意義.根據(jù)ITSGrid系統(tǒng)負(fù)載均衡評(píng)價(jià)的目的和要求,文中以ITSGrid中各個(gè)資源節(jié)點(diǎn)的負(fù)載情況為基礎(chǔ),對(duì)ITSGrid系統(tǒng)負(fù)載均衡的評(píng)價(jià)進(jìn)行建模.

定義1假設(shè)ITSGrid中的資源節(jié)點(diǎn)個(gè)數(shù)為n,每個(gè)資源節(jié)點(diǎn)在某一時(shí)刻的負(fù)載為li(0≤li≤1),分布式資源節(jié)點(diǎn)的負(fù)載指標(biāo)可以根據(jù)需求自主選擇和組合,如資源節(jié)點(diǎn)的CPU利用率、內(nèi)存利用率、數(shù)據(jù)庫(kù)連接池利用率和網(wǎng)絡(luò)帶寬利用率等.對(duì)應(yīng)的ITSGrid資源節(jié)點(diǎn)負(fù)載集合可表示為L(zhǎng)={l1,l2,…,ln},且ITSGrid的當(dāng)前平均負(fù)載lavg可定義為

在式(1)中,0≤lavg≤1.系統(tǒng)負(fù)載均衡評(píng)價(jià)值可表示為

在式(2)中,0≤B≤0.5.當(dāng)B=0時(shí),表示系統(tǒng)當(dāng)前的負(fù)載均衡程度處于最優(yōu)狀態(tài);當(dāng)B=0.5時(shí),則表示系統(tǒng)當(dāng)前的負(fù)載均衡程度處于最差狀態(tài).由此可見(jiàn),系統(tǒng)負(fù)載均衡評(píng)價(jià)值B與系統(tǒng)負(fù)載均衡程度成反比.

由于B具有線性變化的特點(diǎn),可以采用最小最大規(guī)格化方法[6]對(duì)B進(jìn)行規(guī)范化處理.在經(jīng)過(guò)規(guī)格化處理后,ITSGrid系統(tǒng)負(fù)載均衡評(píng)價(jià)值B就轉(zhuǎn)換成B′∈[0,1]區(qū)間.

2.2 ITSGrid資源節(jié)點(diǎn)滿意度評(píng)價(jià)模型

用下面3個(gè)定義構(gòu)建資源節(jié)點(diǎn)滿意度評(píng)價(jià)模型.

定義2分布式資源的QoS參數(shù)q是從分布式資源的屬性中抽象而來(lái)的,可用一個(gè)二元組表示為q= {attr,v},其中,attr表示分布式資源的屬性名稱,v表示該資源屬性的當(dāng)前值.理論上,分布式資源所有的屬性均可作為資源調(diào)度的QoS參數(shù),然而在應(yīng)用和實(shí)踐中,為了便于數(shù)學(xué)建模,一般要求選定的資源屬性是可測(cè)量的.

定義3QoS類別s為QoS參數(shù)的一個(gè)概念集合,可用一個(gè)三元組表示,即s={qcn,attr-set,w}.其中,qcn為QoS類別名稱;attr-set表示屬性集合,attr-set={attr1,attr2,…,attrm},其中,attrk為QoS參數(shù)中某一個(gè)具體的屬性,1≤k≤m;w表示QoS類別在分布式資源調(diào)度過(guò)程中所占的權(quán)重,即該QoS類別在資源調(diào)度過(guò)程中的重要程度,w∈[0,1].

定義4計(jì)算任務(wù)對(duì)分布式資源調(diào)度結(jié)果的滿意度評(píng)價(jià)模型M可用一個(gè)四元組表示,即M={Ri,Di, Ei,P}.其中,Ri表示被選中的資源節(jié)點(diǎn)實(shí)例;Di表示ri的資源屬性的數(shù)據(jù),它可以包含多個(gè)數(shù)據(jù)項(xiàng),每個(gè)數(shù)據(jù)項(xiàng)代表數(shù)據(jù)實(shí)例Di在滿意度評(píng)價(jià)過(guò)程中某一個(gè)QoS參數(shù)的取值;Ei為評(píng)價(jià)模型的輸出,用以保存Ri的滿意度評(píng)價(jià)結(jié)果;P為評(píng)價(jià)模型中組件間約束關(guān)系的集合.

2.3 GLBCQ分布式資源自適應(yīng)調(diào)度算法

在進(jìn)行資源調(diào)度的過(guò)程中,GLBCQ將在ITSGrid系統(tǒng)負(fù)載均衡QoS需求和計(jì)算任務(wù)自定義QoS需求之間進(jìn)行適當(dāng)?shù)钠胶?盡可能做到兩者兼顧,從而保證ITS應(yīng)用計(jì)算的服務(wù)質(zhì)量和ITSGrid的整體性能.

2.3.1 源數(shù)據(jù)的獲取

假設(shè)對(duì)計(jì)算任務(wù)T的QoS需求進(jìn)行抽象,得到需求向量R=(r1,r2,…,rn),R∈attr-set,R中的每個(gè)rk(1≤k≤n)為所需資源的QoS參數(shù)取值.由此假設(shè),ITSGrid中能滿足任務(wù)T的QoS需求的候選資源節(jié)點(diǎn)的集合N=(n1,n2,…,nm);針對(duì)N中的ni(1≤i≤m),假設(shè)需求向量R中的n個(gè)資源屬性值的資源屬性集向量yi=(yi1,yi2,…,yin);根據(jù)向量R和yi,計(jì)算出計(jì)算任務(wù)T對(duì)N中每一個(gè)候選資源節(jié)點(diǎn)的滿意度向量si=(si1,si2,…,sin)=

在計(jì)算滿意度向量過(guò)程中,為了降低調(diào)度算法的復(fù)雜度,采用絕對(duì)值把候選資源節(jié)點(diǎn)QoS滿意程度參數(shù)轉(zhuǎn)化為單調(diào)遞增的線性屬性.于是,k個(gè)si構(gòu)成的矩陣mS=(s1,s2,…,Sk)T與候選資源節(jié)點(diǎn)的當(dāng)前系統(tǒng)負(fù)載li共同組成GLBCQ算法的原始數(shù)據(jù)集,作為分布式資源調(diào)度器尋求最佳分布式資源節(jié)點(diǎn)的基礎(chǔ).

2.3.2 源數(shù)據(jù)的預(yù)處理

在計(jì)算任務(wù)T的個(gè)性化QoS需求過(guò)程中,各個(gè)QoS參數(shù)分屬不同的數(shù)值類型,且取值范圍也各不相同.為了使得QoS參數(shù)在調(diào)度算法中的權(quán)重具有可比性,采用式(4)所定義的向量規(guī)范化方法對(duì)調(diào)度算法的源數(shù)據(jù)矩陣mS進(jìn)行規(guī)范化,Sij被轉(zhuǎn)換為zij∈[0,1],矩陣mS={Sij},則被規(guī)范化為Z={Zij}.

經(jīng)過(guò)規(guī)范化后,QoS滿意度參數(shù)的取值范圍被轉(zhuǎn)換到[0,1]區(qū)間.而候選資源節(jié)點(diǎn)的負(fù)載li的取值范圍原本就處于[0,1]區(qū)間,因此不需進(jìn)行規(guī)范化操作.

2.3.3 權(quán)重調(diào)整

為了實(shí)現(xiàn)ITSGrid的系統(tǒng)負(fù)載共享與均衡,在GLBCQ算法中以候選資源節(jié)點(diǎn)的實(shí)時(shí)負(fù)載作為主要考慮的因素.然而,ITSGrid的系統(tǒng)負(fù)載均衡程度是動(dòng)態(tài)變化的,這就要求資源調(diào)度算法必須適應(yīng)這種動(dòng)態(tài)性,同樣具有相應(yīng)的靈活性.一般可以分為以下兩種情況:

(1)當(dāng)ITSGrid的系統(tǒng)負(fù)載均衡程度較好時(shí),調(diào)度算法就不需要過(guò)多地考慮系統(tǒng)負(fù)載共享與均衡因素,只需把如何滿足計(jì)算任務(wù)的個(gè)性化QoS需求放在首位.在GLBCQ算法中的處理方法為:降低分布式資源節(jié)點(diǎn)實(shí)時(shí)負(fù)載在調(diào)度算法中的權(quán)重.

(2)當(dāng)ITSGrid的系統(tǒng)負(fù)載均衡程度較差時(shí),調(diào)度算法在保證滿足計(jì)算服務(wù)個(gè)性化QoS需求的同時(shí),還需重點(diǎn)考慮ITSGrid的系統(tǒng)負(fù)載的均衡因素.在GLBCQ算法中的處理方法為:提升分布式資源節(jié)點(diǎn)實(shí)時(shí)負(fù)載在調(diào)度算法中的權(quán)重.

由此可見(jiàn),以ITSGrid的系統(tǒng)負(fù)載均衡評(píng)價(jià)值作為候選資源節(jié)點(diǎn)實(shí)時(shí)負(fù)載在GLBCQ算法中的權(quán)重,能夠較好滿足分布式資源調(diào)度算法的靈活性要求.由于系統(tǒng)負(fù)載均衡評(píng)價(jià)值B與系統(tǒng)負(fù)載均衡程度成反比,系統(tǒng)負(fù)載均衡評(píng)價(jià)值B越接近0,ITSGrid的系統(tǒng)負(fù)載均衡程度越好,而此時(shí)的候選資源節(jié)點(diǎn)的實(shí)時(shí)負(fù)載在調(diào)度算法中所占權(quán)重比例也越小.

2.3.4 候選資源節(jié)點(diǎn)滿意度評(píng)價(jià)模型

根據(jù)規(guī)范化的候選分布式資源節(jié)點(diǎn)的用戶滿意度矩陣Z,按照

計(jì)算出運(yùn)行在候選資源節(jié)點(diǎn)ni上的計(jì)算任務(wù)T的QoS需求滿意度值.再利用vi、候選資源節(jié)點(diǎn)的實(shí)時(shí)負(fù)載li和負(fù)載均衡評(píng)價(jià)值B′,計(jì)算出候選資源節(jié)點(diǎn)ni的滿意度評(píng)價(jià)值為

為了實(shí)現(xiàn)ITSGrid系統(tǒng)負(fù)載動(dòng)態(tài)的共享與均衡,GLBCQ算法需要從候選資源節(jié)點(diǎn)中優(yōu)先選擇系統(tǒng)負(fù)載最輕的節(jié)點(diǎn)進(jìn)行資源調(diào)度,在式(6)中,選擇用1-li和1-B′作為計(jì)算因子.另外,由于B′∈[0,1],為了避免B′以1-B′為0,因此增加經(jīng)驗(yàn)參數(shù)σ∈(0,1),σ通常為一個(gè)極小的常數(shù).Ei可視為計(jì)算任務(wù)T將獲得資源服務(wù)QoS的預(yù)測(cè)[7].

2.3.5 GLBCQ算法框架

分布式資源自適應(yīng)按需調(diào)度算法GLBCQ框架可用偽代碼描述如下:

Max_value=0;/*設(shè)定初始節(jié)點(diǎn)滿意度最大評(píng)價(jià)值為零*/

Satisfy_value=0;/*設(shè)定初始節(jié)點(diǎn)滿意度評(píng)價(jià)值為零*/

Selected_node=NULL;/*設(shè)定初始選中節(jié)點(diǎn)為空*/

Customed_QoS=task Analysis(ITS_task);/*解析ITS應(yīng)用計(jì)算任務(wù)XML說(shuō)明書,獲取自定義QoS需求*/

For(i=0;i＜Resource_number;i++){ /*Resource_number為ITSGrid中資源節(jié)點(diǎn)的總數(shù)*/

if(checkSatisfied(Resource_node[i],Customed_QoS)){/*檢查資源節(jié)點(diǎn)是否滿足計(jì)算任務(wù)的自定義QoS需求*/

dataPreprocess(Resource_node[i],Customed_QoS);/*按照式(4)預(yù)處理源數(shù)據(jù)*/

Satisfy_value=getSatisfaction(Resource_node[i]);/*按照式(5)和式(6)計(jì)算候選資源節(jié)點(diǎn)的滿意度評(píng)價(jià)值*/

if(Satisfy_value＞Max_value){

Max_value=Satisfy_value;

Selected_node=Resource_node[i];/*在已計(jì)算出的候選資源節(jié)點(diǎn)的滿意度評(píng)價(jià)值中,查找值最大的節(jié)點(diǎn)*/}

}

}

if(Selected_node!=NULL)

schedule Task2node(ITS_task,Selected_node)/*調(diào)度計(jì)算任務(wù)至滿意度評(píng)價(jià)值最大的資源節(jié)點(diǎn)*/

3 實(shí)驗(yàn)與分析

為了測(cè)試文中構(gòu)建的面向ITSGrid中計(jì)算服務(wù)的分布式資源調(diào)度管理模型的適用性和有效性,借助某校園的計(jì)算網(wǎng)格系統(tǒng)(Campus Grid,CG)、某公路勘察設(shè)計(jì)院的遙感計(jì)算中心(Remote Sensing Computing Center,RSCC)以及西安市交通警察支隊(duì)的道路交通監(jiān)控系統(tǒng)(UTCS)中的交通管理(TMS)、交通信息服務(wù)(ISP)和交通規(guī)劃(PS)子系統(tǒng),組成ITSGrid實(shí)驗(yàn)仿真環(huán)境,其配置如表1所示.

表1 模擬ITSGrid計(jì)算節(jié)點(diǎn)的資源配置

每個(gè)模擬節(jié)點(diǎn)都安裝了支持實(shí)時(shí)應(yīng)用集群(Real Application Clusters,RAC)的Oracle 10g數(shù)據(jù)庫(kù),設(shè)置每個(gè)連接池的連接數(shù)量的最小值為5,最大值為100.用連接池的利用率來(lái)反映節(jié)點(diǎn)資源的利用情況.根據(jù)ITS資源需求頻度的歷史統(tǒng)計(jì),從仿真ITSGrid環(huán)境選擇需求頻度最多的R1、R3、R4和R6,作為實(shí)驗(yàn)所用的分布式資源節(jié)點(diǎn).

從模擬ITSGrid的計(jì)算作業(yè)庫(kù)中,隨機(jī)挑選出資源需求及其QoS要求各異的50個(gè)ITS計(jì)算任務(wù)構(gòu)成實(shí)驗(yàn)所需的測(cè)試集.測(cè)試集在性能最好的節(jié)點(diǎn)R6上的執(zhí)行時(shí)間少于50 h.通過(guò)ITSGrid的計(jì)算作業(yè)批處理模式,作業(yè)管理模塊在10 h內(nèi),隨機(jī)提交測(cè)試集中的全部計(jì)算作業(yè).

作業(yè)調(diào)度策略庫(kù)內(nèi)預(yù)置了3種資源調(diào)度算法:經(jīng)典的OLB算法、MCT算法以及文中提出的GLBCQ算法.觀察在以上3種調(diào)度策略下,每個(gè)ITS節(jié)點(diǎn)的數(shù)據(jù)庫(kù)連接池的利用率、系統(tǒng)負(fù)載均衡評(píng)價(jià)值以及所有作業(yè)的調(diào)度運(yùn)行信息(平均等待時(shí)間、成功率和按時(shí)完成率)的情況.觀察周期為50 h,取樣頻率為1次/h.

圖1中,在MCT算法主導(dǎo)的調(diào)度策略下,50個(gè)系統(tǒng)負(fù)載均衡評(píng)價(jià)值中的4個(gè)在0.10～0.20之間,表示系統(tǒng)負(fù)載均衡程度良好;44個(gè)在0.20～0.45之間,表示系統(tǒng)負(fù)載均衡程度一般;剩下的2個(gè)分布在0.45以上的區(qū)間里,表示系統(tǒng)負(fù)載均衡程度很差.在OLB算法主導(dǎo)的調(diào)度策略下,系統(tǒng)負(fù)載均衡評(píng)價(jià)值波動(dòng)較大,在0.05～0.40之間隨機(jī)分布,其中分布在0.05～0.20區(qū)間的有18個(gè),表示系統(tǒng)負(fù)載均衡程度良好;剩下32個(gè)都處于0.20～0.40之間,表示系統(tǒng)負(fù)載均衡程度一般.在GLBCQ算法主導(dǎo)的調(diào)度策略下,系統(tǒng)負(fù)載均衡評(píng)價(jià)值都分布在0.00～0.20之間,表示系統(tǒng)負(fù)載均衡程度良好.

圖1 模擬ITSGrid系統(tǒng)負(fù)載均衡評(píng)價(jià)

圖2 數(shù)據(jù)庫(kù)連接池的利用率

從圖2可見(jiàn),與MCT和OLB資源調(diào)度算法比較,在GLBCQ算法主導(dǎo)的調(diào)度策略下,ITSGrid中各節(jié)點(diǎn)的資源利用率始終維持在75%以上,處于一個(gè)較高的水平,而且波動(dòng)范圍較小.

從表2中的各項(xiàng)數(shù)據(jù)可見(jiàn),構(gòu)建的模型在3種調(diào)度算法的主導(dǎo)下,在作業(yè)的平均等待時(shí)間和作業(yè)成功率方面,GLBCQ算法優(yōu)于MCT算法和OLB算法;在作業(yè)按時(shí)成功完成率方面,GLBCQ算法與MCT算法非常接近.

表2 測(cè)試作業(yè)集的作業(yè)調(diào)度信息

4 結(jié)束語(yǔ)

為了適應(yīng)ITSGrid的發(fā)展,需要根據(jù)ITS分布式資源的不同應(yīng)用場(chǎng)景選擇相應(yīng)的資源調(diào)度策略.文中提出了一種自適應(yīng)的資源調(diào)度算法GLBCQ,能夠根據(jù)ITS計(jì)算任務(wù)的自定義資源的需求、ITSGrid資源節(jié)點(diǎn)的負(fù)載情況以及ITSGrid系統(tǒng)負(fù)載均衡評(píng)價(jià)值,為應(yīng)用任務(wù)從資源節(jié)點(diǎn)中選擇合適的節(jié)點(diǎn).最后,仿真實(shí)驗(yàn)結(jié)果表明,GLBCQ算法的有效性和實(shí)用性良好,能夠促進(jìn)ITSGrid整體系統(tǒng)性能的提升.目前,該算法已經(jīng)在文中所述的ITSGrid中得到具體部署和應(yīng)用,取得的應(yīng)用效果符合預(yù)期,證明了算法和策略的有效性.

[1] Xu Lin,Qu Shiru.A Resource Information Description Reference Model for ITSGrid[C]//Proceedings of the IEEE International Conference on Transportation,Mechanical&Electrical Engineering.Piscaaway:IEEE,2011:303-306.

[2] 劉宴兵,尚明生,肖云鵬.網(wǎng)格高性能調(diào)度及資源管理技術(shù)[M].北京:科學(xué)出版社,2010:94-95.

[3] Berman F,Casanova H,Chien A,et al.New Grid Scheduling and Rescheduling Methods in the Gr ADS Project[J]. International Journal of Parallel Programming,2005,33(2-3):209-229.

[4] 段富海,馬滿福.一種網(wǎng)格資源調(diào)度中QoS的最大化匹配算法[J].計(jì)算機(jī)應(yīng)用,2010,30(1):108-110. Duan Fuhai,Ma Manfu.Maximum Matching Algorithm with QoSin Grid Resource Scheduling[J].Journal of Computer Applications,2010,30(1):108-110.

[5] Krzhizhanovskaya V V,Korkhov V V.Dynamic Load Balancing of Black-Box Applications with a Resource Selection Mechanism on Heterogeneous Resources of the Grid[C]//Parallel Computing Technologies.Heidelberg:Springer Press, 2007:245-260.

[6] Han J W,Kamber M.Data Mining:Concepts and Techniques[M].California:Morgan Kaufmann,2000:23-24.

[7] 彭飛,鄧浩江,劉磊.面向個(gè)性化服務(wù)推薦的QoS動(dòng)態(tài)預(yù)測(cè)模型[J].西安電子科技大學(xué)學(xué)報(bào),2013,40(4):174-180. Peng Fei,Deng Haojiang,Liu Lei.QoS-aware Temporal Prediction Model for Personalized Service Recommendation[J]. Journal of Xidian University,2013,40(4):174-180.

(編輯:齊淑娟)

Research on distributed resources scheduling strategy in the ITSGrid

XU Lin1,QU Shiru1,YU Bin2
(1.School of Automatic Control,Northwestern Polytechnical Univ.,Xi’an 710129,China; 2.School of Computer Science and Technology,Xidian Univ.,Xi’an 710071,China)

A distributed resource adaptive scheduling algorithm GLBCQ(Global Load Balance and Customed QoS)is proposed,which could take the customed QoS requirement of ITS computing tasks and current system load status of ITSGrid into account and select the optimal resources for the submitted tasks adaptively.Experimental result showed that compared to classical algorithms,GLBCQ has a higher efficiency and adaptability which could promote load balance and overall performance of the ITSGrid.

intelligent transportation system grid;resource scheduling algorithm;customed QoS requirement;system load

TP393

A

1001-2400(2014)03-0203-06

10.3969/j.issn.1001-2400.2014.03.031

2013-07-03< class="emphasis_bold">網(wǎng)絡(luò)出版時(shí)間:

時(shí)間:2013-11-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61172147);教育部博士點(diǎn)基金項(xiàng)目資助項(xiàng)目(20096102110027);航天科學(xué)創(chuàng)新基金資助項(xiàng)目(CASC201104)

徐 琳(1978-),男,西北工業(yè)大學(xué)博士研究生,E-mail:true-xulin@tom.com.

http://www.cnki.net/kcms/detail/61.1076.TN.20131122.1628.201403.223_031.html