【摘要】：為了滿足人們生活中的各種需求,豐富復(fù)雜的應(yīng)用程序相繼被軟件工程師開發(fā)出來。由于用戶的大部分任務(wù)是復(fù)雜繁重的,而移動設(shè)備的計算能力和資源通常是有限的,這就使得用戶對任務(wù)的實(shí)時高效的要求很難得到滿足。目前,移動云計算技術(shù)是解決這類問題的主流方法。然而,并不是應(yīng)用程序的所有子任務(wù)都適合卸載到云服務(wù)器上。同時,將子任務(wù)從移動端上傳到云端,或從云端下載到移動端,移動設(shè)備都需要消耗相應(yīng)的能量和時延。為使移動設(shè)備的能耗盡可能少和滿足用戶對任務(wù)的實(shí)時性要求,這就需要我們設(shè)計一種任務(wù)卸載和調(diào)度相結(jié)合的方法。關(guān)于移動云計算中任務(wù)的協(xié)同調(diào)度與卸載的問題,即移動云計算中的每一次任務(wù)卸載過程都需要調(diào)用任務(wù)調(diào)度的過程,不是單純的任務(wù)卸載問題。對于此類問題,在當(dāng)前學(xué)術(shù)界的研究中主要使用IBM的CPLEX優(yōu)化器來進(jìn)行解決,但是這種方法需要耗費(fèi)很大的內(nèi)存和計算資源,而且程序的運(yùn)行時間很長,不適合應(yīng)用在實(shí)際問題中。同時,由于IBM的CPLEX優(yōu)化器解決的移動云計算中協(xié)同任務(wù)卸載和調(diào)度的問題并沒有考慮到任務(wù)的異構(gòu)性,而實(shí)際問題中任務(wù)通常是異構(gòu)的,因此CPLEX優(yōu)化器并不適合應(yīng)用在實(shí)際問題中。關(guān)于移動云計算中協(xié)同任務(wù)的調(diào)度與卸載的問題,在現(xiàn)有的研究基礎(chǔ)上,本文給出了一個更加適合實(shí)際物理問題的數(shù)學(xué)模型。該數(shù)學(xué)模型與目前這類問題的模型不太相同,主要是考慮到了應(yīng)用程序中子任務(wù)的異構(gòu)性。針對該模型,本文提出了一種啟發(fā)式算法,來解決移動云計算中任務(wù)的協(xié)同卸載與調(diào)度的問題。該啟發(fā)式算主要由任務(wù)卸載的過程和任務(wù)調(diào)度的過程組成。其中,啟發(fā)式算法在每一次任務(wù)卸載的過程中都需要調(diào)用任務(wù)調(diào)度的過程,以便用來判斷這次任務(wù)卸載的過程是否可行的。任務(wù)卸載過程采用了貪心的策略,目的是確保每次卸載一個子任務(wù)的時候,移動設(shè)備所需要的能耗減少量比上一次都盡可能大。任務(wù)調(diào)度過程利用了任務(wù)的優(yōu)先權(quán)來進(jìn)行實(shí)時調(diào)度,目的是確保應(yīng)用程序的完成時間不超過它的截止時間。通過實(shí)驗(yàn)證明,本文提出的啟發(fā)式算法能在較短的時間內(nèi)得出問題的近似最優(yōu)解。在模擬實(shí)驗(yàn)中,我們將啟發(fā)式算法與現(xiàn)有的傳統(tǒng)方法進(jìn)行了對比。本文還提出了一種適合本研究的模擬退火算法,該算法對啟發(fā)式算法的解進(jìn)行了優(yōu)化。經(jīng)過實(shí)驗(yàn)觀察及對比,我們發(fā)現(xiàn)模擬退火算法的解與啟發(fā)式算法的解是十分接近的,進(jìn)一步說明了我們的啟發(fā)式算法是高效、可行的。
【學(xué)位授予單位】：廣東工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2019
【分類號】：TP30
【圖文】：

第一章 緒論 研究背景及意義1 研究背景隨著計算機(jī)技術(shù)的發(fā)展，各種各樣的移動設(shè)備的性能獲得了顯著地提升，手機(jī)、平板、筆記本電腦等。社會經(jīng)濟(jì)的發(fā)展促使人們的生活更加多樣化學(xué)習(xí)中的需求也越來越多，許多相應(yīng)的軟件相繼被開發(fā)出來。這就使得移運(yùn)行這類軟件時需要更多的內(nèi)存資源，計算資源和電量。雖然處理器和內(nèi)經(jīng)得到了很大的發(fā)展，移動終端的性能也有很大提升，但仍無法滿足計算務(wù)的需求。同時，在移動設(shè)備上，數(shù)據(jù)密集型程序的執(zhí)行受限于移動設(shè)備量，導(dǎo)致移動設(shè)備有限的資源將無法滿足移動用戶對相關(guān)資源的迫切需求

廣東工業(yè)大學(xué)碩士學(xué)位論文Step5: 如果ΔC<0 則接受 V 作為新的當(dāng)前解，即更新當(dāng)前解；否則算法將會以概率 exp(-ΔC/T)接受 V 作為新的當(dāng)前解。然而，如果當(dāng)新解被判定為不可被接受的時候，則只需要在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)，即在。Step6: 如果滿足終止條件，比如要求的目標(biāo)函數(shù)的值或者溫度下降到終止溫度T0，則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。算法的終止條件是指，如果遇到連續(xù)很多個新的解決方案都不被算法接受時，那么就終止算法的運(yùn)行過程。Step7: T 以衰減因子Δt 逐漸減少，且 T 趨向 T0，然后轉(zhuǎn) Step2。

邊代表著兩個子任務(wù)之間的數(shù)據(jù)交互或者信息交互。其中任務(wù)圖，因?yàn)樽尤蝿?wù)之間的數(shù)據(jù)傳輸時單向不可逆的。任務(wù)圖中只有一務(wù)節(jié)點(diǎn)，這個節(jié)點(diǎn)代表了應(yīng)用程序的起始任務(wù)。同樣，任務(wù)圖中節(jié)點(diǎn)的任務(wù)節(jié)點(diǎn)，這個節(jié)點(diǎn)代表了應(yīng)用程序的終止任務(wù)。合任務(wù)調(diào)度和卸載 (Joint Scheduling & Computation Offloading, Jard 問題[42]，一般都比較復(fù)雜。因此，現(xiàn)存研究的聯(lián)合任務(wù)調(diào)度和情況下任務(wù)圖的結(jié)構(gòu)是串行依賴圖,如圖 3-1 所示，大大降低了研實(shí)際應(yīng)用任務(wù)之間的依賴關(guān)系，在大部分情況下是非線性串行的應(yīng)用程序所形成的任務(wù)拓?fù)鋱D是十分復(fù)雜的，一個孩子節(jié)點(diǎn)或許或者一個父親節(jié)點(diǎn)擁有多個孩子節(jié)點(diǎn)。但是，本文研究的任務(wù)圖中不存在到自身的路徑。很顯然，這種假設(shè)是符合實(shí)際應(yīng)用場景的子任務(wù)之間數(shù)據(jù)流是不會回溯的。

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 李玉;石小林;;考慮倒垛情況的場吊調(diào)度問題研究[J];交通運(yùn)輸工程與信息學(xué)報;2017年02期

2 沈益民;范玉順;;調(diào)度問題微結(jié)構(gòu)及柔性優(yōu)化方法[J];自動化學(xué)報;2006年02期

3 董平;機(jī)器調(diào)度問題及求解方法[J];物流技術(shù)與應(yīng)用;1997年01期

4 楊自厚,李寶澤,高志遠(yuǎn);鋼鐵廠煤氣資源的最優(yōu)分配[J];冶金自動化;1988年03期

5 朱繼忠,徐國禹;電力系統(tǒng)有功安全經(jīng)濟(jì)再調(diào)度[J];重慶大學(xué)學(xué)報(自然科學(xué)版);1989年06期

6 鄢勇,劉鍵;同步并行任務(wù)流圖的最佳近似調(diào)度[J];電子學(xué)報;1989年05期

7 劉長有;李磊;;一種電網(wǎng)經(jīng)濟(jì)調(diào)度問題的分布式對偶優(yōu)化解法[J];山西建筑;2016年33期

8 周龍飛;張霖;劉永奎;;云制造調(diào)度問題研究綜述[J];計算機(jī)集成制造系統(tǒng);2017年06期

9 劉志雄;;求解調(diào)度問題的粒子群算法編碼方法研究[J];武漢科技大學(xué)學(xué)報;2010年01期

10 王璇;劉世峰;劉達(dá);;基于“實(shí)時智能”方法的港口物流調(diào)度問題研究[J];物流技術(shù);2009年12期

相關(guān)會議論文 前10條

1 劉海龍;黃小原;;總的未完工費(fèi)用最小的多機(jī)調(diào)度問題[A];1995中國控制與決策學(xué)術(shù)年會論文集[C];1995年

2 耿兆強(qiáng);康勛;鄒益仁;;用遺傳算法解決模糊加工時間與模糊交貨期下的單機(jī)調(diào)度問題[A];2001年中國智能自動化會議論文集（下冊）[C];2001年

3 吳斌;方葉祥;崔志勇;;基于人工蜂群算法的越庫調(diào)度問題研究[A];第25屆中國控制與決策會議論文集[C];2013年

4 張雷;;關(guān)于多人旅行商與調(diào)度問題[A];1995年中國控制會議論文集（下）[C];1995年

5 尹新;楊自厚;;帶有等待時間懲罰的提前／拖期調(diào)度問題的啟發(fā)式解法[A];1994中國控制與決策學(xué)術(shù)年會論文集[C];1994年

6 吳斌;董敏;;考慮行為主體的越庫調(diào)度問題干擾管理研究[A];中國系統(tǒng)工程學(xué)會第十八屆學(xué)術(shù)年會論文集——A12系統(tǒng)科學(xué)與系統(tǒng)工程理論在各個領(lǐng)域中的應(yīng)用研究[C];2014年

7 劉興初;趙千川;鄭大鐘;;具有不同準(zhǔn)備時間和交付期的單機(jī)E／T調(diào)度問題研究[A];1998年中國控制會議論文集[C];1998年

8 王海星;申金升;;智能蟻群算法解決公交區(qū)域調(diào)度問題研究[A];2006年首屆ICT大會信息、知識、智能及其轉(zhuǎn)換理論第一次高峰論壇會議論文集[C];2006年

9 全雄文;王力;;基于沖突集的區(qū)間調(diào)度問題性質(zhì)分析和算法設(shè)計[A];中國自動化學(xué)會控制理論專業(yè)委員會D卷[C];2011年

10 齊向彤;涂奉生;;雙交付期E／T調(diào)度問題[A];1997年中國控制會議論文集[C];1997年

相關(guān)重要報紙文章 前1條

1 ;事故教訓(xùn)應(yīng)以改革誠意彌補(bǔ)[N];21世紀(jì)經(jīng)濟(jì)報道;2011年

相關(guān)博士學(xué)位論文 前10條

1 肖世昌;加工時間具有隨機(jī)性的Job Shop魯棒調(diào)度問題研究[D];西北工業(yè)大學(xué);2018年

2 趙玉明;基于數(shù)學(xué)規(guī)劃的煉油廠原油調(diào)度問題建模與算法研究[D];廣東工業(yè)大學(xué);2019年

3 陳鑫;基于誤工損失指標(biāo)的調(diào)度問題與算法研究[D];大連理工大學(xué);2019年

4 孫德峰;鋼鐵原料物流計劃與調(diào)度的建模及最優(yōu)化方法研究[D];東北大學(xué);2016年

5 文晶;風(fēng)電集群接入電力系統(tǒng)的源荷協(xié)調(diào)優(yōu)化調(diào)度模型研究[D];華北電力大學(xué)(北京);2015年

6 劉迪迪;能量捕獲無線網(wǎng)絡(luò)的傳輸調(diào)度和能量管理研究[D];西安電子科技大學(xué);2018年

7 侯愛琴;高性能網(wǎng)絡(luò)中面向大數(shù)據(jù)傳輸QoS的帶寬調(diào)度研究[D];西北大學(xué);2018年

8 袁媛;鋼鐵生產(chǎn)與物流調(diào)度的時空建模和凸優(yōu)化方法[D];東北大學(xué);2017年

9 李巖;批運(yùn)輸排序與物流調(diào)度的算法研究[D];吉林大學(xué);2019年

10 譚龍華;控制性能導(dǎo)向的實(shí)時系統(tǒng)調(diào)度參數(shù)優(yōu)化研究[D];西北工業(yè)大學(xué);2016年

相關(guān)碩士學(xué)位論文 前10條

1 戴喜妹;基于分派規(guī)則的航班排序與調(diào)度研究[D];南京航空航天大學(xué);2019年

2 王文權(quán);帶時間窗農(nóng)機(jī)調(diào)度問題模型及算法研究[D];浙江大學(xué);2019年

3 譚文越;整車配送調(diào)度優(yōu)化方法及系統(tǒng)實(shí)現(xiàn)[D];南昌大學(xué);2019年

4 陳凱;船舶分段堆場調(diào)度研究與應(yīng)用[D];上海交通大學(xué);2016年

5 羅裕春;移動云計算中任務(wù)的協(xié)同調(diào)度與卸載算法研究[D];廣東工業(yè)大學(xué);2019年

6 張曉鳴;青島市純電動公交城市調(diào)度優(yōu)化問題研究[D];青島大學(xué);2019年

7 宋小靜;機(jī)場貨運(yùn)區(qū)雙機(jī)ETV調(diào)度優(yōu)化的研究[D];中國民航大學(xué);2019年

8 趙明明;數(shù)據(jù)驅(qū)動下的共享單車調(diào)度優(yōu)化研究[D];大連理工大學(xué);2019年

9 馬海明;帶結(jié)果收集的多趟調(diào)度優(yōu)化模型及算法研究[D];西安電子科技大學(xué);2019年

10 李晉青;靜態(tài)/動態(tài)訂單下考慮時間窗的跨工序協(xié)同調(diào)度研究[D];浙江工業(yè)大學(xué);2019年

本文編號：2774568