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

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

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

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

【相似文獻】

相關期刊論文 前10條

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

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

3 董平;機器調度問題及求解方法[J];物流技術與應用;1997年01期

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

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

6 鄢勇,劉鍵;同步并行任務流圖的最佳近似調度[J];電子學報;1989年05期

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

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

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

10 王璇;劉世峰;劉達;;基于“實時智能”方法的港口物流調度問題研究[J];物流技術;2009年12期

相關會議論文 前10條

1 劉海龍;黃小原;;總的未完工費用最小的多機調度問題[A];1995中國控制與決策學術年會論文集[C];1995年

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

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

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

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

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

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

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

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

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

相關重要報紙文章 前1條

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

相關博士學位論文 前10條

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

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

3 陳鑫;基于誤工損失指標的調度問題與算法研究[D];大連理工大學;2019年

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

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

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

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

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

9 李巖;批運輸排序與物流調度的算法研究[D];吉林大學;2019年

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

相關碩士學位論文 前10條

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

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

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

4 陳凱;船舶分段堆場調度研究與應用[D];上海交通大學;2016年

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

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

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

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

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

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

本文編號：2774568