移動(dòng)網(wǎng)格環(huán)境下的資源調(diào)度研究

摘 要：本文結(jié)合移動(dòng)網(wǎng)格自身的特點(diǎn)，構(gòu)建與其相適應(yīng)的網(wǎng)絡(luò)模型。同時(shí)，對(duì)資源決策過(guò)程中具體采用的調(diào)度優(yōu)化算法進(jìn)行研究，將基本微粒群算法進(jìn)行離散化編碼，在迭代的過(guò)程中引入變異算子以及遺傳算子。經(jīng)仿真，該算法不僅能提高微粒群整體向最優(yōu)解逼進(jìn)的速度，更可協(xié)助避免陷入局部收斂，對(duì)大規(guī)模求解的計(jì)算效果優(yōu)越。

關(guān)鍵詞：移動(dòng)網(wǎng)格 資源調(diào)度 微粒群算法（PSO）

中圖分類(lèi)號(hào)：TN929.5文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1003-9082（2019）08-000-02

引言

目前，移動(dòng)網(wǎng)格系統(tǒng)中重點(diǎn)會(huì)對(duì)移動(dòng)設(shè)備進(jìn)行通信接口和通信資源本身進(jìn)行研究[1]。在移動(dòng)網(wǎng)格中，用戶與網(wǎng)絡(luò)資源需要保持實(shí)時(shí)的、動(dòng)態(tài)的連接，每個(gè)移動(dòng)設(shè)備可看作為一個(gè)網(wǎng)格節(jié)點(diǎn)，又要解決它自身的缺陷：如頻繁移動(dòng)，帶寬小，電池容量不足等問(wèn)題。可見(jiàn)，如何高效地組織這些移動(dòng)資源成為網(wǎng)格資源管理的關(guān)鍵問(wèn)題之一。

一、移動(dòng)網(wǎng)格的網(wǎng)絡(luò)模型

移動(dòng)網(wǎng)格建立在有線網(wǎng)格的框架之上，由無(wú)線網(wǎng)格、網(wǎng)關(guān)、有線網(wǎng)格這三部分構(gòu)成。其內(nèi)部的資源管理服務(wù)機(jī)制是基于移動(dòng)代理的分層模型，用移動(dòng)資源代理實(shí)時(shí)地對(duì)資源進(jìn)行監(jiān)測(cè)和分配這樣可增強(qiáng)系統(tǒng)的可擴(kuò)展性，提高執(zhí)行效率。

此外，在移動(dòng)網(wǎng)格的網(wǎng)關(guān)中需要對(duì)資源代理執(zhí)行監(jiān)控，同時(shí)還要根據(jù)執(zhí)行策略進(jìn)行任務(wù)策略的選擇，具體功能包括通信接口、信息采集、任務(wù)劃分以及調(diào)度決策。信息采集作為關(guān)鍵的一個(gè)部分，用于收集和發(fā)布網(wǎng)格系統(tǒng)各節(jié)點(diǎn)的狀態(tài)信息;NWS是一個(gè)分布式監(jiān)控系統(tǒng)，主要用于實(shí)時(shí)跟蹤網(wǎng)絡(luò)資源和狀況，提供網(wǎng)絡(luò)性能預(yù)判功能。收集到的網(wǎng)格資源相關(guān)信息會(huì)定期反饋到調(diào)度決策模塊，以供調(diào)度決策模塊執(zhí)行相應(yīng)調(diào)度策略。

在移動(dòng)網(wǎng)格運(yùn)行的過(guò)程中，其中一個(gè)重要環(huán)節(jié)就是資源調(diào)度，具體地，根據(jù)系統(tǒng)吞吐量、資源利用率、用戶需求等多種因素來(lái)選擇最佳的任務(wù)分配方案。傳統(tǒng)的資源調(diào)度常常只著重考慮任務(wù)在資源上的執(zhí)行時(shí)間，而移動(dòng)網(wǎng)格中更多的約束限制決定了其任務(wù)調(diào)度將更加復(fù)雜化，在選擇調(diào)度算法時(shí)，要實(shí)時(shí)地從網(wǎng)格系統(tǒng)中監(jiān)測(cè)最新的移動(dòng)節(jié)點(diǎn)資源狀況和位置變動(dòng)等信息，更新路由表，把通信因素對(duì)性能的影響作為分析的重點(diǎn)。

二、移動(dòng)網(wǎng)格資源調(diào)度算法

1.問(wèn)題假定

在移動(dòng)網(wǎng)格中，資源調(diào)度是把移動(dòng)網(wǎng)格中提交的作業(yè)分割成許多子任務(wù)，根據(jù)子任務(wù)在不同移動(dòng)節(jié)點(diǎn)上的執(zhí)行的吞吐量和資源利用率不同，來(lái)選擇最佳的作業(yè)分配方案，使任務(wù)完成時(shí)間最小。不同的作業(yè)調(diào)度算法可能擁有不同的調(diào)度目標(biāo)，比如考慮服務(wù)質(zhì)量?jī)?yōu)先、網(wǎng)絡(luò)跨度優(yōu)先、資源負(fù)載優(yōu)先 [2]等，這里對(duì)移動(dòng)網(wǎng)格中的資源調(diào)度問(wèn)題作以下幾個(gè)假定：

1.1同一時(shí)刻下，一臺(tái)節(jié)點(diǎn)設(shè)備僅能執(zhí)行一個(gè)任務(wù)，該任務(wù)不會(huì)被其他設(shè)備搶占。

1.2一個(gè)用戶提交的任務(wù)被劃分為許多任務(wù)，任務(wù)相互之間不具備必然的依賴(lài)關(guān)系，并且不會(huì)發(fā)生數(shù)據(jù)交互。

1.3實(shí)時(shí)獲得未來(lái)一段時(shí)間內(nèi)系統(tǒng)的預(yù)測(cè)信息，在資源節(jié)點(diǎn)故障或其所有者離開(kāi)了網(wǎng)格系統(tǒng)的情況下，原來(lái)分配到該資源節(jié)點(diǎn)上的任務(wù)會(huì)被重新進(jìn)行資源調(diào)度和分配。

資源調(diào)度采用以下數(shù)學(xué)模型進(jìn)行搭建：

任務(wù)集合表示為，資源集合表示為，其中N小于等于M。獲取資源和任務(wù)的屬性信息矩陣：

任務(wù)在資源上的預(yù)期執(zhí)行時(shí)間：

任務(wù)到資源上執(zhí)行所需的通信時(shí)間、數(shù)據(jù)傳輸時(shí)間以及結(jié)果返回所用的時(shí)間之和，統(tǒng)稱(chēng)為通信時(shí)延：

尋求優(yōu)化調(diào)度的目標(biāo)就是求得這樣一種映射方案，使總的時(shí)間損耗T最小，以獲得最高效的系統(tǒng)性能。

2.基本微粒群算法

微粒群算法具有公認(rèn)的諸多優(yōu)點(diǎn)，比如計(jì)算簡(jiǎn)單、所需個(gè)體數(shù)目少等，尤其是在求解復(fù)雜問(wèn)題時(shí)，其優(yōu)越性表現(xiàn)地更為突顯 [3-4]。其中，一個(gè)可行解可看作成“微粒”，每一個(gè)微粒會(huì)通過(guò)跟蹤多個(gè)最優(yōu)解來(lái)對(duì)自己進(jìn)行更新，包括每個(gè)微粒自身尋找的個(gè)體最優(yōu)解、種群整體當(dāng)前尋找到的全局最優(yōu)解。微粒采用以下方式來(lái)更新速度和位置：

3.改進(jìn)的PSO資源調(diào)度算法

本文對(duì)PSO算法進(jìn)行優(yōu)化，改進(jìn)的算法流程圖如下所示：

3.1初始微粒種群，計(jì)算各微粒的適應(yīng)度

設(shè)置基本參數(shù)，隨機(jī)離散編碼生成微粒群，每個(gè)微粒包含以下參數(shù)：

位置向量：，表示為把第個(gè)資源節(jié)點(diǎn)分配用為執(zhí)行第個(gè)任務(wù)，的范圍小于搜索空間N。

飛行速度：，表示第個(gè)任務(wù)下一次迭代所選擇的資源節(jié)點(diǎn)與當(dāng)前分配的資源節(jié)點(diǎn)之間存在的偏離，初始時(shí)的速度取值范圍可以界于（-N+1）與（N-1）之間，并且取整。

適應(yīng)值：將第個(gè)微粒當(dāng)前的位置表示為，將微粒群中適應(yīng)值最優(yōu)的那個(gè)微粒所處的位置定義為，計(jì)算適應(yīng)值。

以上參數(shù)按序存放用于表征一個(gè)微粒，主要是便于執(zhí)行迭代和參數(shù)的更新，如下表所示：

假設(shè)初始化產(chǎn)生的微粒群的微粒數(shù)目表示為D，則微粒群可用二維數(shù)組表示，大小相應(yīng)地就是D*（3*M+1），在迭代中不斷更新該數(shù)組，慢慢逼進(jìn)全局的最優(yōu)解。

3.2采用遺傳選擇、隨機(jī)交叉、線性衰減的慣性因子進(jìn)行迭代

將適應(yīng)度較低的部分微粒進(jìn)入下一代，將其他適應(yīng)度較大的微粒執(zhí)行遺傳選擇以及隨機(jī)的交叉，然后更新微粒：當(dāng)交叉后微粒的適應(yīng)度低于之前，則不改變?cè)嘉恢茫绻麑?duì)之前更優(yōu)，則對(duì)個(gè)人最優(yōu)解進(jìn)行更新。

此外，考慮到慣性因子具有以下特點(diǎn)：w值越大，越對(duì)局部最小點(diǎn)的跳出有利;w值越小，則可以加快算法進(jìn)行收斂。為此，采用線性衰減的w進(jìn)行改進(jìn)：

（3）對(duì)微粒的速度、位移，不斷更新個(gè)體最優(yōu)解以及全局最優(yōu)解

（4）判定收斂條件

設(shè)置迭代的總次數(shù)，達(dá)到此次數(shù)時(shí)算法終止，輸出最優(yōu)方案;否則重新回到步驟（2），繼續(xù)執(zhí)行迭代。

三、實(shí)驗(yàn)分析

采用該帶有遺傳因子和交叉因子的PSO算法與基本PSO算法進(jìn)行比較進(jìn)行仿真，模擬了在8個(gè)移動(dòng)網(wǎng)格節(jié)點(diǎn)上來(lái)執(zhí)行10-50個(gè)服務(wù)任務(wù)。設(shè)置初始種群為40，迭代次數(shù)為100，c1=c2=1.8，false=0.9， false=0.2。兩種算法下分配效率隨任務(wù)數(shù)增加所產(chǎn)生的影響，如圖所示：

由仿真圖可以直觀地發(fā)現(xiàn)，改進(jìn)的PSO調(diào)度算法在任務(wù)數(shù)量變大的情況下調(diào)度效率更優(yōu)越。分析其原因，任務(wù)數(shù)量越大，基本PSO算法容易陷入局部最優(yōu)，使得向全局最優(yōu)執(zhí)行搜索的進(jìn)度變得較慢。改進(jìn)的算法則因?yàn)槭褂昧诉z傳因子、隨機(jī)交叉以及變化的慣性因子，會(huì)更加明顯可以擴(kuò)大搜索范圍。此外，由于每一次迭代交叉具有隨機(jī)性，任務(wù)調(diào)度的完成時(shí)間整體上具有隨著任務(wù)量的增大而增加的趨勢(shì)，但同時(shí)也呈現(xiàn)有一定幅度的波動(dòng)。

結(jié)語(yǔ)

本文重點(diǎn)是分析了移動(dòng)網(wǎng)格系統(tǒng)的特征，把傳統(tǒng)網(wǎng)格資源調(diào)度模型應(yīng)用其中。為了滿足移動(dòng)節(jié)點(diǎn)資源調(diào)度的復(fù)雜性，這里全面地考慮了影響分配方案的因素，然后采用改進(jìn)的PSO算法來(lái)加快搜索的收斂速度，在更短的時(shí)間內(nèi)獲得更優(yōu)的分配方案，在應(yīng)對(duì)大規(guī)模移動(dòng)網(wǎng)格中的動(dòng)態(tài)資源管理問(wèn)題上效果顯著。

參考文獻(xiàn)

[1]PHAN T，HUANG L，DULAN C. Challenge： integrating mobile wireless devices into the computational grid[C] //Proc of the 8thACM International Conference on Mobile Computing and Networking. New York ：ACM Press， 2002： 271-278.

[2]都志輝，陳渝，劉鵬.網(wǎng)格計(jì)算[M].北京：清華大學(xué)出版社，2002.

[3]Kennedy J，EberhartR C. Particle swarm optimization[C]//Proc. IEEE International Conference on Neural Networks.Pis-cataway，NJ，1995

[4]曾建潮，介婧，崔志華.微粒群算法[M].北京：科學(xué)出版社， 2004： 10-15.

作者簡(jiǎn)介;朱丹丹，（1987.5-）女，安徽省亳州市人，研究方向：通信與信息系統(tǒng)。