作為下一代云計(jì)算系統(tǒng)的發(fā)展趨勢(shì),移動(dòng)邊緣計(jì)算(Mobile Edge Computing,MEC)能夠在網(wǎng)絡(luò)邊緣就近地提供高帶寬、低時(shí)延的“邊緣云”服務(wù),彌補(bǔ)了移動(dòng)云計(jì)算的不足。其中,用戶委派MEC系統(tǒng)執(zhí)行計(jì)算任務(wù)的過(guò)程,稱為計(jì)算卸載。作為MEC領(lǐng)域的核心技術(shù),計(jì)算卸載的研究成果雖不斷涌現(xiàn),但依然存在不足:首先,現(xiàn)有算法研究針對(duì)異構(gòu)場(chǎng)景的考慮相對(duì)匱乏,但未來(lái)該場(chǎng)景將隨著異構(gòu)組網(wǎng)技術(shù)的普及而廣泛存在;其次,生產(chǎn)環(huán)境下諸多服務(wù)多由相互依賴的細(xì)粒度子任務(wù)構(gòu)成,而針對(duì)子任務(wù)的卸載研究雖然能夠大幅提升性能表現(xiàn),但卻鮮少有人問(wèn)津;另外,非專用系統(tǒng)中普遍真實(shí)存在的動(dòng)態(tài)性問(wèn)題,更因其復(fù)雜性而缺乏關(guān)注。鑒于此,本文立足于動(dòng)態(tài)且異構(gòu)的Het-MEC系統(tǒng),考慮了任務(wù)圖模型,著眼于計(jì)算卸載中指派決策和調(diào)度執(zhí)行兩個(gè)階段,分別研究了用戶端自適應(yīng)計(jì)算卸載和服務(wù)端在線實(shí)時(shí)調(diào)度兩個(gè)問(wèn)題。誠(chéng)然,本研究面臨眾多挑戰(zhàn),如異構(gòu)場(chǎng)景下決策標(biāo)準(zhǔn)的差異化難題、任務(wù)圖模型下細(xì)粒度算法設(shè)計(jì)的較大難度、動(dòng)態(tài)環(huán)境中決策結(jié)果的偏差或失效等。在并存的機(jī)遇與挑戰(zhàn)下,本文提出了下述新穎且高效的應(yīng)對(duì)算法:一是針對(duì)卸載決策階段,本文提出了自適應(yīng)卸載決策算法(ADaptive Computing Offloading,ADCO),旨在為動(dòng)態(tài)Het-MEC系統(tǒng)中的移動(dòng)用戶,解決如何決策指派使任務(wù)圖總體完工時(shí)間最短的問(wèn)題。ADCO算法的關(guān)鍵思想在于在分散的時(shí)機(jī)將關(guān)鍵任務(wù)重復(fù)卸載至不同服務(wù)器中同時(shí)執(zhí)行,從而高效地自適應(yīng)于系統(tǒng)異常波動(dòng),并有效地規(guī)避了單點(diǎn)失效風(fēng)險(xiǎn)。ADCO算法還在決策前對(duì)待卸載任務(wù)圖進(jìn)行聚類預(yù)處理,減小了問(wèn)題規(guī)模,降低了卸載過(guò)程的通信開(kāi)銷。此外,依托于列表調(diào)度的迭代框架,ADCO算法能夠以較低的時(shí)間開(kāi)銷實(shí)現(xiàn)較高的卸載性能表現(xiàn)。實(shí)驗(yàn)表明,同比對(duì)照組,ADCO算法下任務(wù)圖總體完工時(shí)間最高下降超過(guò)50%,且資源依賴性更低、規(guī)模擴(kuò)展性更強(qiáng)。二是針對(duì)調(diào)度執(zhí)行階段,本文設(shè)計(jì)了在線鏈表調(diào)度算法(名為彈簧滑軌調(diào)度,Spring SLideway Scheduling,SSLS),旨在為硬實(shí)時(shí)任務(wù)圖動(dòng)態(tài)到達(dá)的邊緣服務(wù)器,解決如何在線調(diào)度使長(zhǎng)期平均拒絕服務(wù)率最低的問(wèn)題。為了健壯地自適應(yīng)于異常請(qǐng)求激增,SSLS通過(guò)將任務(wù)時(shí)序約束定義為其彈性指標(biāo),允許任務(wù)開(kāi)始時(shí)刻在彈性限度內(nèi)任意變動(dòng),以充分利用資源碎片擴(kuò)充調(diào)度空間。為了實(shí)現(xiàn)高度靈活性,SSLS創(chuàng)新地將等待隊(duì)列建模為線性鏈表,以迭代而非構(gòu)造的插入式鏈表操作進(jìn)行調(diào)度。同時(shí),得益于失敗任務(wù)的重調(diào)度調(diào)整機(jī)制,SSLS不僅拒絕率低而且長(zhǎng)期穩(wěn)定,具有在線運(yùn)行適用性。實(shí)驗(yàn)表明,SSLS算法的長(zhǎng)期拒絕服務(wù)率最高僅為對(duì)照組相應(yīng)指標(biāo)的10%上下,且可擴(kuò)展性和硬實(shí)時(shí)適應(yīng)性更強(qiáng)、資源依賴性更低。
【學(xué)位單位】：華中科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位年份】：2019
【中圖分類】：TN929.5;TP301.6
【部分圖文】：

裹挾于移動(dòng)互聯(lián)風(fēng)起云涌的洪流，移動(dòng)云計(jì)算技術(shù)（MobileCloudComputing, MCC）迎來(lái)了高速發(fā)展。因可靠性高、擴(kuò)展性佳、運(yùn)算力強(qiáng)，從龍頭巨擘至初創(chuàng)小微，莫不以該技術(shù)作為移動(dòng)應(yīng)用的基礎(chǔ)支撐。譬如國(guó)際電商巨頭亞馬遜的專業(yè)云服務(wù)（AmazonWebServices,AWS）通過(guò)部署在全球各地?cái)?shù)據(jù)中心、數(shù)量超過(guò)200 萬(wàn)臺(tái)的云服務(wù)器，為 190 多個(gè)國(guó)家和地區(qū)的成千上萬(wàn)家企業(yè)提供云平臺(tái)支持[1]。如今，站上工業(yè) 4.0 時(shí)代的新業(yè)態(tài)風(fēng)口，移動(dòng)應(yīng)用面臨愈發(fā)嚴(yán)苛的服務(wù)質(zhì)量（Quality-of-Service, QoS）要求[2]；大數(shù)據(jù) 2.0 的時(shí)代演進(jìn)為海量數(shù)據(jù)的井噴式增長(zhǎng)推波助瀾[3]；而 5G 承載技術(shù)的成熟與落地，勢(shì)必使核心網(wǎng)絡(luò)罹受更為苛刻的考驗(yàn)[4]。如此形勢(shì)下，提供中心式服務(wù)的 MCC 恐將身陷囹圄，難以實(shí)現(xiàn)毫秒級(jí)響應(yīng)的宏大愿景[3]：一方面，涌向數(shù)據(jù)中心的海量請(qǐng)求造成的網(wǎng)絡(luò)擁堵使實(shí)時(shí)通信難以實(shí)現(xiàn)；另一方面，數(shù)據(jù)中心的繁重負(fù)載使其極易成為延緩響應(yīng)的服務(wù)瓶頸；更甚者，數(shù)據(jù)中心的高昂擴(kuò)容成本顯然不相適應(yīng)于指數(shù)級(jí)飆升的需求規(guī)模。因此，下一代云服務(wù)系統(tǒng)的設(shè)計(jì)需求迫在眉睫、呼之欲出，激發(fā)了國(guó)內(nèi)外研究者踴躍研究的熱忱[5]。

圖 1.2 計(jì)算卸載技術(shù)的概念與流程計(jì)算卸載技術(shù)具有重要價(jià)值：對(duì)于移動(dòng)用戶而言，計(jì)算卸載技術(shù)擴(kuò)展了移動(dòng)設(shè)備的計(jì)算能力，節(jié)約了能耗開(kāi)銷，其運(yùn)行時(shí)間得以延長(zhǎng)[9]，用戶體驗(yàn)得以提升；對(duì)于運(yùn)營(yíng)商和服務(wù)提供商而言，計(jì)算卸載技術(shù)使網(wǎng)絡(luò)資源得以充分利用，生產(chǎn)效率得以提高，能夠創(chuàng)造巨大效益。在 MEC 研究領(lǐng)域中，計(jì)算卸載技術(shù)更因其較高的研究?jī)r(jià)值而備受高度關(guān)注。Mach 等人[8]在全面考察了多種 MEC 系統(tǒng)后明確指出：計(jì)算卸載技術(shù)是 MEC 系統(tǒng)的三大設(shè)計(jì)要素之首，是最關(guān)鍵的核心技術(shù)要素。故可言，MEC 系統(tǒng)的服務(wù)質(zhì)量高低直接取決于計(jì)算卸載算法的性能表現(xiàn)好壞，因而具備重大的理論意義。綜上可知，本文針對(duì)計(jì)算卸載領(lǐng)域的研究選題兼具實(shí)用和理論雙重意義。1.2.2 現(xiàn)有計(jì)算卸載研究的不足近年來(lái)，計(jì)算卸載技術(shù)研究領(lǐng)域已涌現(xiàn)出大量相關(guān)文獻(xiàn)和成果[30-53]。然而，雖然

4圖 1.3 Het-MEC 系統(tǒng)的部署環(huán)境源豐富的同構(gòu)服務(wù)器集群構(gòu)成。圖 1.3 展示了 Het-MEC 系統(tǒng)典型的部署網(wǎng)絡(luò)環(huán)境及其地理分布特性。由此可見(jiàn)，基于 Het-MEC 場(chǎng)景的計(jì)算卸載研究因更為貼合實(shí)際而具有實(shí)用價(jià)值。然而，目前大多的計(jì)算卸載研究集中在單用戶模型或多用戶單服務(wù)器模型[33-35,48-51]，而基于 Het-MEC 模型的相關(guān)研究較為匱乏。二是任務(wù)圖模型下細(xì)粒度算法少人問(wèn)津。生產(chǎn)環(huán)境下的服務(wù)和應(yīng)用通常由多個(gè)相互依賴的任務(wù)、模塊構(gòu)成。例如，圖 1.4 展示了智能家居監(jiān)控系統(tǒng)的依賴性模塊結(jié)構(gòu)[3]。通常，上述依賴性結(jié)構(gòu)可被建模為有向無(wú)環(huán)圖[58]（DirectedAcyclicGraph,DAG）。圖 1.4 智能家居監(jiān)控系統(tǒng)的依賴性模塊結(jié)構(gòu)研究任務(wù)圖模型下的細(xì)粒度計(jì)算卸載決策算法意義卓著：除了更為貼合真實(shí)的應(yīng)用場(chǎng)景，細(xì)粒度卸載算法通常還更為精密高效，不僅能提升系統(tǒng)資源利用率，而且能大幅增加計(jì)算并行度、減少響應(yīng)時(shí)間[3]，更具場(chǎng)景通配性以及性能卓越性，擁有廣闊的實(shí)用價(jià)值和市場(chǎng)前景。然而
【相似文獻(xiàn)】

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

1 張春開(kāi);;基于任務(wù)圖示的寫作生成實(shí)踐[J];英語(yǔ)教師;2013年01期

2 張德富，吳巧泉;基于任務(wù)圖的一種并行程序設(shè)計(jì)方法（Ⅰ）──任務(wù)圖的設(shè)計(jì)[J];軟件學(xué)報(bào);1995年06期

3 周本海;喬建忠;林樹(shù)寬;;多核處理平臺(tái)上任務(wù)圖模型的并行調(diào)度策略研究[J];小型微型計(jì)算機(jī)系統(tǒng);2012年11期

4 周軍;張強(qiáng);于曉洲;;利用層次任務(wù)圖和多種群遺傳算法的可重構(gòu)計(jì)算任務(wù)劃分[J];計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào);2011年03期

5 劉鍵,張靜;含過(guò)程任務(wù)圖的調(diào)度[J];計(jì)算機(jī)工程與科學(xué);1997年01期

6 郭兆陽(yáng);;基于遺傳算法的軟硬件協(xié)同設(shè)計(jì)探索[J];集成電路應(yīng)用;2005年01期

7 郭兆陽(yáng);基于遺傳算法的軟硬件協(xié)同設(shè)計(jì)探索[J];真空電子技術(shù);2005年02期

8 楊峰;張建軍;;廣義Fork-Join任務(wù)圖的調(diào)度問(wèn)題研究[J];兵工自動(dòng)化;2009年12期

9 李慶華,阮幼林,劉干,蔣盛益,楊世達(dá);一個(gè)調(diào)度Fork-Join任務(wù)圖的最優(yōu)算法(英文)[J];軟件學(xué)報(bào);2005年05期

10 楊峰;張建軍;;一個(gè)新的Fork任務(wù)圖的調(diào)度算法[J];兵工自動(dòng)化;2010年03期

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

1 張建軍;基于Fork-Join任務(wù)圖的調(diào)度算法研究[D];華中科技大學(xué);2010年

2 馬天義;低功耗軟硬件劃分算法研究[D];哈爾濱工業(yè)大學(xué);2009年

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

1 翟金亭;“神威·太湖之光”上某流體力學(xué)應(yīng)用的任務(wù)圖并行化研究[D];山東科技大學(xué);2018年

2 張超;異構(gòu)動(dòng)態(tài)邊緣計(jì)算系統(tǒng)中任務(wù)圖自適應(yīng)卸載與在線實(shí)時(shí)調(diào)度算法研究[D];華中科技大學(xué);2019年

3 郭強(qiáng);“神威·太湖之光”上tend_lin應(yīng)用的任務(wù)圖并行優(yōu)化研究[D];山東科技大學(xué);2018年

4 高希然;“神威·太湖之光”上任務(wù)圖并行調(diào)度優(yōu)化研究[D];山東科技大學(xué);2018年

5 馬嘯;基于任務(wù)圖分割與膜計(jì)算的仿生陣列自組織方法[D];國(guó)防科學(xué)技術(shù)大學(xué);2016年

6 楊俊;多核系統(tǒng)靜態(tài)任務(wù)調(diào)度問(wèn)題研究[D];合肥工業(yè)大學(xué);2016年

7 Mohammed Ali Hasan Al-towayti;Chombo中的AMRPossion應(yīng)用的DAG并行化[D];山東科技大學(xué);2017年

8 孔德華;基于Petri網(wǎng)的并行分布計(jì)算中的調(diào)度問(wèn)題的研究[D];山東科技大學(xué);2006年

9 周湖廣;P2P環(huán)境下基于任務(wù)圖的感知模型的優(yōu)化與實(shí)現(xiàn)[D];廣西大學(xué);2014年

10 王雷;片上網(wǎng)絡(luò)映射優(yōu)化算法研究[D];電子科技大學(xué);2010年

本文編號(hào)：2858046