吳香林，蔣 青，張佳星

(1.中國(guó)移動(dòng)通信集團(tuán)四川有限公司樂山分公司，四川樂山 416000;2.重慶郵電大學(xué)移動(dòng)通信技術(shù)重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

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

1 移動(dòng)設(shè)備移動(dòng)概率分析

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

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

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

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

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

2 改進(jìn)算法的理論分析

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

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

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

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

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

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

由此可以得出

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

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

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

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

移動(dòng)設(shè)備移動(dòng)后進(jìn)入下一個(gè)移動(dòng)網(wǎng)格并且處于網(wǎng)絡(luò)斷開狀態(tài)的概率為

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

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

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

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

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

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

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

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

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

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

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

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

圖1 兩種算法的資源負(fù)載比較

圖2 兩算法單個(gè)任務(wù)調(diào)度跨度時(shí)間

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

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

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

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

3.2 改進(jìn)算法的驗(yàn)證和分析

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

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

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

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

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

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

圖6 不同場(chǎng)景的任務(wù)執(zhí)行順序比較

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

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

4 結(jié)束語

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

:

［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)危.移動(dòng)網(wǎng)格發(fā)展研究［J］.計(jì)算機(jī)工程與設(shè)計(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)格任務(wù)調(diào)度算法［J］.重慶郵電大學(xué)學(xué)報(bào):自然科學(xué)版，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)格任務(wù)調(diào)度方法研究［J］.計(jì)算機(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.