基于網絡連接性的移動網格任務調度算法

吳香林，蔣 青，張佳星

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

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

1 移動設備移動概率分析

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

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

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

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

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

2 改進算法的理論分析

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

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

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

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

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

移動終端的連接與非連接狀態的狀態轉移概率矩陣如下

由此可以得出

結合公式(6)和(7)聯解得

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

根據上述分析，假設移動設備在同一個網格內的網絡連接狀態維持不變，移動設備移出當前移動網格并保證下一個選中的移動網格的網絡連接狀態良好的概率為

移動設備經過一段時間后仍然保留在當前移動網格中并且處于網絡連接狀態下的概率為

移動設備移動后進入下一個移動網格并且處于網絡斷開狀態的概率為

移動設備經過一段時間后仍然保留在當前移動網格中并且處于網絡斷開狀態下的概率為

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

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

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

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

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

為了獲得最優的任務調度方案，本文采用具有全局搜索能力強、速度快的啟發式算法，如遺傳算法來實現，提高移動網格任務執行分析效率。

3 仿真結果與分析

3.1 遺傳算法的優勢分析

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

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

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

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

圖2 兩算法單個任務調度跨度時間

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

進一步分析上述場景，在同一個移動網格中，固定資源數改變任務數。分析兩種不同的調度算法對任務調度總時間的影響。通過仿真驗證得出隨著任務數的增加兩種算法的任務調度總時間分布如圖3所示。

圖3 任務數增加，兩種算法總執行時間

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

3.2 改進算法的驗證和分析

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

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

圖4 網絡連接性狀態改變的概率分布

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

圖5 不同網絡環境下的負載圖

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

圖6 不同場景的任務執行順序比較

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

圖7 任務調度總時間的比較

4 結束語

本文首先對所持便攜式移動資源的網格用戶的移動概率進行了理論推導。其次對資源在移動網格中的網絡斷連性進行了分析，提出了基于移動性和網絡斷連性的算法。仿真結果表明，在理想狀態下，遺傳算法比Min－Min算法較適合本文所設場景。基于移動性和連接性的算法在實際場景中能提高資源利用率和任務執行成功率，更加精確任務調度的時間，提高用戶的滿意度。

:

［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］杜麗娟，余鎮危.移動網格發展研究［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相似度的網格任務調度算法［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］劉慧婷，姜曉濤，陳健.基于遺傳算法的網格任務調度方法研究［J］.計算機技術與發展，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.