基于網(wǎng)絡連接性的移動網(wǎng)格任務調(diào)度算法

吳香林，蔣 青，張佳星

(1.中國移動通信集團四川有限公司樂山分公司，四川樂山 416000;2.重慶郵電大學移動通信技術(shù)重慶市重點實驗室，重慶 400065)

隨著移動終端技術(shù)和網(wǎng)格技術(shù)的快速發(fā)展，用戶在任何地點、任何時間都可以訪問全球網(wǎng)絡資源，那么將移動終端加入網(wǎng)格系統(tǒng)作為網(wǎng)格資源，形成移動網(wǎng)格［1］。移動資源大多屬于便攜式移動設備，隨網(wǎng)格用戶的移動，其網(wǎng)絡連接性發(fā)生變化。資源移動的網(wǎng)絡連接狀態(tài)會影響任務調(diào)度過程中資源的重新分配。現(xiàn)有任務調(diào)度技術(shù)存在不足［2－3］:移動網(wǎng)格計算資源包括固定設備和移動設備，這些設備的處理能力差異很大;大部分設備不是移動網(wǎng)格的專用處理設備，它們隨時有可能處理用戶自己的事務，因此在執(zhí)行網(wǎng)格任務時其處理能力也在動態(tài)變化;并且受移動環(huán)境的影響，移動終端與通信網(wǎng)絡的連接是一種弱連接，即低帶寬、長延遲、不穩(wěn)定和經(jīng)常性的斷開。因此在任務處理過程中還要考慮移動設備的間歇連接性［4］?，F(xiàn)有遺傳算法［5－7］進行任務調(diào)度過程中未考慮移動資源特性，文獻［8］表明一個資源節(jié)點平均只有28%的時間保持在一個網(wǎng)絡連接狀態(tài)。移動設備的網(wǎng)絡連接遭受頻繁斷連。因此，本文將重點分析移動性和網(wǎng)絡連接性對任務調(diào)度技術(shù)的影響。

1 移動設備移動概率分析

根據(jù)已有的移動模型，可以預測行人和車輛的移動速度和方向，但是移動終端在移動網(wǎng)格中移動的概率如何計算未知，因此本文假設移動設備j的移動概率為pj'

式中:n是位置定位檢測器在Δt時間內(nèi)總的定位次數(shù);m是在該短時間內(nèi)連續(xù)兩次定位結(jié)果不同的次數(shù)。式(1)只能判斷移動設備j在同一個網(wǎng)格中移動的頻繁度，無法判斷它是否移出了當前的移動網(wǎng)格。為此引入式(2)計算移動設備移動，但是仍然保留在當前移動網(wǎng)格中的概率為

如果移動設備移出了當前的移動網(wǎng)格，則P″j=0。其中:A事件是移動設備j保留在當前移動網(wǎng)格中;B事件是移動設備移動。為了研究需要，本文取(B/A)的對立事件(即移動設備移出了當前網(wǎng)格和移動設備在當前網(wǎng)格中不移動)的概率為

那么移動設備從當前網(wǎng)格移出到另一個網(wǎng)格中的概率為

Pjout僅考慮移動設備的移動性，未考慮移動設備移出到另一個網(wǎng)格的網(wǎng)絡連接性。下文討論網(wǎng)絡的連接性因素對網(wǎng)格任務調(diào)度的影響。

2 改進算法的理論分析

調(diào)度的目標是最小化應用的時間跨度，也就是在盡可能短的時間內(nèi)完成任務。約束條件是整個調(diào)度期間內(nèi)所有資源的處理能力總和應大于等于所有任務的負載總和。

任務集合T={t1，t2，…，tn};在一個調(diào)度期間內(nèi)n的值不變。

資源包括固定資源和移動資源，本文重點分析移動資源。假設移動資源集合R={r1，r2，…，rm};其初始狀態(tài)與網(wǎng)絡的連接狀態(tài)有無連接(不可用)和有連接(可用)兩種情況。

任務向量Vt是一個向量(t，r，e)。其中t代表任務;r代表資源;e代表執(zhí)行時間。根據(jù)t和r在時間矩陣EETn×m中查出。任務執(zhí)行時間矩陣EETn×m，其中每個元素值表示該任務在對應的資源號上執(zhí)行時間用eij表示。

移動設備的狀態(tài)分4種:設備開機網(wǎng)絡連接、設備開機網(wǎng)絡斷開、設備關機網(wǎng)絡斷開、設備關機網(wǎng)絡連接(不可能事件)。本文主要考慮手機處于開機狀態(tài)下，則移動設備只會處于兩種狀態(tài):連接狀態(tài)和非連接狀態(tài)。兩者轉(zhuǎn)化概率分別是α和β，其中α是單位時間內(nèi)移動設備從連接狀態(tài)轉(zhuǎn)化為非連接狀態(tài)時的平均發(fā)生率，β是單位時間內(nèi)移動設備從非連接狀態(tài)轉(zhuǎn)化為連接狀態(tài)時的平均發(fā)生率。

移動終端的連接與非連接狀態(tài)的狀態(tài)轉(zhuǎn)移概率矩陣如下

由此可以得出

結(jié)合公式(6)和(7)聯(lián)解得

求解:α=0或α+β=1。其中α=0舍棄，不符合實際情況。則α+β=1。通常情況下，兩者轉(zhuǎn)化概率的選取原則是β≥α。根據(jù)下文實際場景設置兩者的取值分布。

根據(jù)上述分析，假設移動設備在同一個網(wǎng)格內(nèi)的網(wǎng)絡連接狀態(tài)維持不變，移動設備移出當前移動網(wǎng)格并保證下一個選中的移動網(wǎng)格的網(wǎng)絡連接狀態(tài)良好的概率為

移動設備經(jīng)過一段時間后仍然保留在當前移動網(wǎng)格中并且處于網(wǎng)絡連接狀態(tài)下的概率為

移動設備移動后進入下一個移動網(wǎng)格并且處于網(wǎng)絡斷開狀態(tài)的概率為

移動設備經(jīng)過一段時間后仍然保留在當前移動網(wǎng)格中并且處于網(wǎng)絡斷開狀態(tài)下的概率為

移動網(wǎng)格任務調(diào)度中，需要考慮移動網(wǎng)格的移動性和移動設備的網(wǎng)絡連接狀態(tài)影響的數(shù)據(jù)傳輸時間。如果移動設備執(zhí)行任務時斷開了連接，其上運行的任務就被終止等待重新調(diào)度。假設理想情況下網(wǎng)絡處于連接狀態(tài)，傳輸數(shù)據(jù)需要的時間為t，那么實際Pconn傳輸數(shù)據(jù)的時間為gc(t)，在Pdisc傳輸數(shù)據(jù)時間為gd(t)，其中β－1為網(wǎng)絡恢復連接的平均等待時間。那么

若不考慮終端的移動性并且終端在同一個移動網(wǎng)格中的連接性不變，則在移動設備j傳輸數(shù)據(jù)的平均時間結(jié)合上式(8)和式(14)得出

假設twj表示在資源j上執(zhí)行的等待時間，則調(diào)度一個任務i在資源j上的時間Tijall為

基于移動設備移動性考慮，在t時刻移動設備j傳輸數(shù)據(jù)的平均時間結(jié)合上式(8)和(14)得出gmj(t)為

假設twj表示在資源j上的等待時間，則調(diào)度一個任務i在資源j上的時間Tijmall為

為了獲得最優(yōu)的任務調(diào)度方案，本文采用具有全局搜索能力強、速度快的啟發(fā)式算法，如遺傳算法來實現(xiàn)，提高移動網(wǎng)格任務執(zhí)行分析效率。

3 仿真結(jié)果與分析

3.1 遺傳算法的優(yōu)勢分析

假設在同一個移動網(wǎng)格中，移動資源的能量充足，不考慮其移動性和終端的網(wǎng)絡一直處于連接狀態(tài)(完全理想狀態(tài)下)。固定任務數(shù)和資源數(shù)，通過采用兩種不同的調(diào)度算法如Min－Min算法和GA算法分析比較單個任務的執(zhí)行時間和各個資源的負載分布狀況。

首先，引入遺傳算法需要設置一些參數(shù)。假設任務數(shù)為100個，資源數(shù)為10個，變異概率為0.1，分析交叉概率的變化時，要保證適應度函數(shù)平穩(wěn)變化，因此選取交叉概率為0.8。任務執(zhí)行過程中，數(shù)據(jù)通信輸入和輸出的時間設置為1 s，一個任務的期望執(zhí)行時間隨機設為20 s左右。

其次，通過搭建仿真場景，假設任務一旦被調(diào)度都是一次性執(zhí)行成功，那么分別采用兩種算法進行仿真驗證，得出各個資源的負載分配和單個任務調(diào)度完成的總時間分布如下圖1和圖2所示。

圖1 兩種算法的資源負載比較

圖2 兩算法單個任務調(diào)度跨度時間

最后，分析圖1可見，采用遺傳算法資源的負載均衡效果優(yōu)于Min－Min算法。分析圖2可見，在同一個移動網(wǎng)格中，資源位置固定并且網(wǎng)絡的連接性不改變時，固定資源數(shù)為10個，任務數(shù)逐漸增加。當任務數(shù)較小時，Min－Min算法執(zhí)行任務速度較快。隨著任務數(shù)增多，Min－Min算法對單個資源的負載情況較重。每次選取最小時間的任務在對應的資源上執(zhí)行，會出現(xiàn)單個任務的等待時間，導致資源浪費或是資源負載不均衡的現(xiàn)象，從而迫使后續(xù)任務執(zhí)行時間增加。但是采用遺傳算法，在同樣場景下這一現(xiàn)象會得到明顯改善。通過仿真驗證，當任務數(shù)逐漸增加時，遺傳算法對縮短任務的等待時間，實現(xiàn)單個任務時間最小化調(diào)度的優(yōu)勢很顯著。

進一步分析上述場景，在同一個移動網(wǎng)格中，固定資源數(shù)改變?nèi)蝿諗?shù)。分析兩種不同的調(diào)度算法對任務調(diào)度總時間的影響。通過仿真驗證得出隨著任務數(shù)的增加兩種算法的任務調(diào)度總時間分布如圖3所示。

圖3 任務數(shù)增加，兩種算法總執(zhí)行時間

從圖3中可以得出，當任務數(shù)和資源數(shù)比較接近時，兩種算法的調(diào)度總時間幾乎一致。但是隨著任務數(shù)逐漸增加，遺傳算法的任務總跨度時間會有極大的縮短，而Min－Min算法資源負載分布不均衡導致產(chǎn)生了大量的等待時間，導致了任務總跨度時間偏長。鑒于上述對比分析，本文后續(xù)將對遺傳算法進行改進探討。

3.2 改進算法的驗證和分析

假設移動設備在不同的網(wǎng)格中，有不同的網(wǎng)絡連接概率，同時考慮其移動性，采用遺傳算法對引入移動性和網(wǎng)絡連接因子的前后兩種狀況進行分析，比較引入前后對任務調(diào)度時間和資源負載情況的影響。

設置任務數(shù)為100個，資源數(shù)為10個，交叉概率為0.8，變異概率為0.1。根據(jù)式(9)移動設備的網(wǎng)絡連接性由連接狀態(tài)轉(zhuǎn)化為斷開狀態(tài)的概率α服從泊松分布。搭建仿真環(huán)境，得到各個資源在執(zhí)行單個任務過程中網(wǎng)絡連接性發(fā)生轉(zhuǎn)化的概率分布如圖4所示。可見資源網(wǎng)絡開始處于連接到斷開的概率較小，則反之概率較大。但是某些特殊場合會存在執(zhí)行任務時網(wǎng)絡突然失效的現(xiàn)象，所以需要考慮網(wǎng)絡連接性對任務調(diào)度的影響。

圖4 網(wǎng)絡連接性狀態(tài)改變的概率分布

針對實際網(wǎng)絡連接不穩(wěn)定和理想狀態(tài)網(wǎng)絡一直處于連接的情況，采用不同算法進行分析。得出兩種情況的資源負載分布如圖5所示，可見資源負載是不一致的。因為在實際情況中由于移動設備自身的網(wǎng)絡不穩(wěn)定等特點，使得任務和資源按照理想狀態(tài)下的分配方式無法執(zhí)行，需要重新選擇資源。所以當某一個移動網(wǎng)格的網(wǎng)絡比較穩(wěn)定時，則該網(wǎng)格中移動設備執(zhí)行任務的次數(shù)偏高，就出現(xiàn)某個網(wǎng)格中的資源負載量過大。

圖5 不同網(wǎng)絡環(huán)境下的負載圖

為了體現(xiàn)兩種情況下任務執(zhí)行順序是不一致的特性，本文在調(diào)度的過程中計算個體選擇概率值，根據(jù)概率值大小選取任務執(zhí)行的順序。為了便于觀察，設置任務數(shù)為50個，其他參數(shù)保持不變，進行仿真驗證，兩種情況的任務執(zhí)行順序如圖6所示。

圖6 不同場景的任務執(zhí)行順序比較

最后，進一步考慮移動性和網(wǎng)絡連接性，固定資源數(shù)和任務數(shù)。分別在理想狀態(tài)下與實際場景下，采用標準遺傳調(diào)度算法進行分析。對采用遺傳算法與不采用調(diào)度算法進行隨機選擇調(diào)度的情況都進行了對比，分析3種狀態(tài)下對任務調(diào)度總時間的影響。通過仿真驗證3種情況下任務調(diào)度總時間分布如圖7所示。分析圖7在實際場景下未采用調(diào)度算法比采用遺傳算法的任務執(zhí)行時間長，實際場景網(wǎng)絡連接不穩(wěn)定狀態(tài)比理想狀態(tài)下的任務執(zhí)行時間長。這是因為在實際情況下任務執(zhí)行過程中網(wǎng)絡頻繁斷連，造成部分任務多次被調(diào)度的時間浪費;又如在網(wǎng)絡全連接狀態(tài)下，移動終端不必考慮選擇網(wǎng)絡的時間，也節(jié)約了一部分時間。因此理想狀態(tài)下任務調(diào)度總時間最少。

圖7 任務調(diào)度總時間的比較

4 結(jié)束語

本文首先對所持便攜式移動資源的網(wǎng)格用戶的移動概率進行了理論推導。其次對資源在移動網(wǎng)格中的網(wǎng)絡斷連性進行了分析，提出了基于移動性和網(wǎng)絡斷連性的算法。仿真結(jié)果表明，在理想狀態(tài)下，遺傳算法比Min－Min算法較適合本文所設場景?；谝苿有院瓦B接性的算法在實際場景中能提高資源利用率和任務執(zhí)行成功率，更加精確任務調(diào)度的時間，提高用戶的滿意度。

:

［1］VAITHIYA S S，BHANU S M.Scheduling tasks in mobile grid environment using mobility based resource prediction［C］//Proc.lst Intemational Conference on Parallel Distributed and Grid Computing(PDGC2010).Solan:［s.n.］，2010:89－94.

［2］杜麗娟，余鎮(zhèn)危.移動網(wǎng)格發(fā)展研究［J］.計算機工程與設計，2010，31(6):1166－1169.

［3］PARK S M，KO Y B，KIM J H.Disconnected operation service in mobile grid computing［C］//Proc.1st International Conference on Service Oriented Computing(ICSOC’2003).Trento，Italy:Springer，2003:499－513.

［4］劉宴兵，陳杰，熊仕勇.基于QoS相似度的網(wǎng)格任務調(diào)度算法［J］.重慶郵電大學學報:自然科學版，2009，21(3):416－420.

［5］PRABHU S，KUMAR N V.Multi－objective optimization based on genetic algorithm in grid scheduling［J］.Int J Adv Res Technol，2011，1(1):54－58.

［6］CHIN S H，SUH T，YU H C.Genetic algorithm based scheduling method for efficiency and reliability in mobile grid［C］//Proc.the 4th International Conference on IEEE Trans.Parallel and Distributed Systems.［S.l.］:IEEE Press，2009:928－934.

［7］劉慧婷，姜曉濤，陳健.基于遺傳算法的網(wǎng)格任務調(diào)度方法研究［J］.計算機技術(shù)與發(fā)展，2012，22(4):69－76.

［8］XU Haiyan.Research for new modified adaptive genetic algorithm［C］//Proc.World Automation Congress(WAC).［S.l.］:IEEE Press，2012:1－4.