王凌/吳楚格/范文慧
隨著物聯(lián)網(wǎng)和移動(dòng)終端的迅速發(fā)展，邊緣計(jì)算技術(shù)應(yīng)運(yùn)而生，通過(guò)將計(jì)算和存儲(chǔ)配置在互聯(lián)網(wǎng)邊緣，處理物聯(lián)網(wǎng)終端產(chǎn)生的大量數(shù)據(jù)，應(yīng)對(duì)時(shí)延敏感型應(yīng)用請(qǐng)求。為提高計(jì)算資源使用效率，優(yōu)化性能指標(biāo)，邊緣計(jì)算資源分配與任務(wù)調(diào)度優(yōu)化問(wèn)題受到了廣泛關(guān)注。邊緣計(jì)算資源的地理分散性、異構(gòu)性以及對(duì)性能、能耗、費(fèi)用、穩(wěn)定性等的需求，增加了優(yōu)化調(diào)度的復(fù)雜性。通過(guò)介紹邊緣計(jì)算和物聯(lián)網(wǎng)、云計(jì)算協(xié)同的系統(tǒng)模型，給出優(yōu)化的指標(biāo)、調(diào)度模型及其求解算法，包括精確算法、啟發(fā)式方法及智能優(yōu)化方法等，歸納典型應(yīng)用案例，指出有待進(jìn)一步研究的內(nèi)容和方向，有助于促進(jìn)邊緣計(jì)算的發(fā)展。
引言
隨著移動(dòng)設(shè)備的更新?lián)Q代，物聯(lián)網(wǎng)快速發(fā)展，地理上分散分布的終端設(shè)備向計(jì)算平臺(tái)提出了低時(shí)延、高帶寬、數(shù)據(jù)私密性等需求，在云計(jì)算基礎(chǔ)上文獻(xiàn)[1]提出邊緣計(jì)算的概念，通過(guò)將數(shù)據(jù)推到互聯(lián)網(wǎng)邊緣來(lái)提升系統(tǒng)整體的可用性和可拓展性；文獻(xiàn)[2]提出霧計(jì)算的概念，通過(guò)將計(jì)算和存儲(chǔ)設(shè)備配置在互聯(lián)網(wǎng)邊緣來(lái)減少互聯(lián)網(wǎng)數(shù)據(jù)傳輸量，從而降低時(shí)延、節(jié)省帶寬及相關(guān)費(fèi)用。
目前，邊緣計(jì)算和霧計(jì)算引起了學(xué)術(shù)界和工業(yè)界的極大關(guān)注[3]。文獻(xiàn)[4]介紹了霧計(jì)算的關(guān)鍵技術(shù)，如計(jì)算、通訊、存儲(chǔ)、命名和私密性等，列舉了常見的霧計(jì)算應(yīng)用。文獻(xiàn)[5]綜述了霧計(jì)算的概念、框架及編程模型、設(shè)計(jì)及規(guī)劃、資源管理、操作、軟件及工具、硬件及協(xié)議等。多個(gè)國(guó)家聯(lián)合成立了OpenFog聯(lián)盟[6]。霧計(jì)算和邊緣計(jì)算緊密相關(guān)，相比于霧計(jì)算，邊緣計(jì)算更強(qiáng)調(diào)邊緣設(shè)備間資源的相互協(xié)同，是處理云上游數(shù)據(jù)或物聯(lián)網(wǎng)下游數(shù)據(jù)的技術(shù)[7]，而霧計(jì)算服務(wù)的實(shí)現(xiàn)需要邊緣技術(shù)的支撐。
資源分配和任務(wù)調(diào)度優(yōu)化是計(jì)算系統(tǒng)的重要研究問(wèn)題之一，其解決方案影響資源使用的有效性和用戶的服務(wù)體驗(yàn)[8]。鑒于邊緣計(jì)算資源的異構(gòu)性、處理器的地理分散性以及電池耗電量等優(yōu)化需求，對(duì)資源分配和任務(wù)調(diào)度優(yōu)化形成了新的挑戰(zhàn)。文獻(xiàn)[9]梳理了邊緣計(jì)算場(chǎng)景下的優(yōu)化問(wèn)題，總結(jié)了40多項(xiàng)優(yōu)化指標(biāo)，并按優(yōu)化場(chǎng)景分類綜述相關(guān)研究。
針對(duì)邊緣計(jì)算資源配置問(wèn)題，文獻(xiàn)[10]綜述了優(yōu)化算法類型、優(yōu)化目標(biāo)和約束?；谏鲜龉ぷ鳎疚膶⒔榻B“物聯(lián)網(wǎng)-邊緣計(jì)算-云計(jì)算”系統(tǒng)架構(gòu)及相關(guān)描述模型，總結(jié)邊緣計(jì)算場(chǎng)景下資源分配調(diào)度問(wèn)題中的常見優(yōu)化指標(biāo)、約束及典型算法，并按抽象調(diào)度模型對(duì)研究工作進(jìn)行分類，概述問(wèn)題的數(shù)學(xué)模型與求解方法，介紹典型應(yīng)用，并指出進(jìn)一步研究的內(nèi)容，有助于研究人員根據(jù)場(chǎng)景、目標(biāo)、調(diào)度問(wèn)題等建立調(diào)度模型，設(shè)計(jì)優(yōu)化算法，獲得有效調(diào)度方案。
1.系統(tǒng)模型
云計(jì)算中心協(xié)同計(jì)算場(chǎng)景下的資源調(diào)度優(yōu)化，如圖1“云-邊-端”3層計(jì)算系統(tǒng)[11]。
圖1“云-邊-端”計(jì)算系統(tǒng)結(jié)構(gòu)
Fig.1 Three-tier computing system architecture
第1層是物聯(lián)網(wǎng)層[12]，傳感器、處理器根據(jù)應(yīng)用需求感知、測(cè)量和收集原始數(shù)據(jù)，在本地處理大量數(shù)據(jù)或?qū)⑵渖蟼髦劣?jì)算節(jié)點(diǎn)。此外，物聯(lián)網(wǎng)裝置被劃分為不同集合，相同集合的多個(gè)裝置能夠提高容錯(cuò)度。
第2層是邊緣計(jì)算層，位于互聯(lián)網(wǎng)邊緣，靠近數(shù)據(jù)源。邊緣計(jì)算節(jié)點(diǎn)連接物聯(lián)網(wǎng)，邊緣節(jié)點(diǎn)之間可以互相通信，提供計(jì)算和存儲(chǔ)功能。文獻(xiàn)[13]將該層分為抽象層和協(xié)同層。文獻(xiàn)[14]將邊緣節(jié)點(diǎn)分為計(jì)算和網(wǎng)關(guān)節(jié)點(diǎn)，其中計(jì)算節(jié)點(diǎn)包含控制、計(jì)算和通訊模塊，負(fù)責(zé)接收和處理應(yīng)用請(qǐng)求，網(wǎng)關(guān)節(jié)點(diǎn)包含期望評(píng)級(jí)和應(yīng)用分配單元，負(fù)責(zé)評(píng)估應(yīng)用請(qǐng)求的優(yōu)先級(jí)并為應(yīng)用分配處理節(jié)點(diǎn)。
第3層是云計(jì)算層。一般而言，云計(jì)算中心的計(jì)算和存儲(chǔ)能力強(qiáng)于霧節(jié)點(diǎn)，提供高聚合度的集中計(jì)算、存儲(chǔ)等服務(wù)，但云計(jì)算中心和本地的長(zhǎng)距離往往會(huì)造成的傳播和傳輸時(shí)延，導(dǎo)致數(shù)據(jù)型任務(wù)上傳云節(jié)點(diǎn)時(shí)存在難以容忍的延時(shí)。
對(duì)于上述3層計(jì)算系統(tǒng)的架構(gòu)模型，文獻(xiàn)[15]綜述了集成物聯(lián)網(wǎng)+霧+云C2F2T(Cloud to Fog to Things)解析模型、Petri網(wǎng)模型、整數(shù)規(guī)劃模型等以及預(yù)測(cè)和分析系統(tǒng)的各項(xiàng)指標(biāo)。文獻(xiàn)[16]提出了解析模型，預(yù)測(cè)給定應(yīng)用的計(jì)算資源需求和服務(wù)質(zhì)量QoS(quality of service)。文獻(xiàn)[17]通過(guò)實(shí)例分析了物聯(lián)網(wǎng)應(yīng)用對(duì)邊緣計(jì)算的需求，考察異構(gòu)、結(jié)構(gòu)分層以及大規(guī)模設(shè)施等特性，為邊緣計(jì)算系統(tǒng)、服務(wù)質(zhì)量、應(yīng)用及操作建立解析模型。文獻(xiàn)[18]建立了邊緣計(jì)算節(jié)點(diǎn)的排隊(duì)模型，給出各環(huán)節(jié)時(shí)延的解析模型，基于模型量化卸載策略對(duì)系統(tǒng)相關(guān)軟硬件的影響，并觀測(cè)系統(tǒng)參數(shù)變化。文獻(xiàn)[19]利用Petri網(wǎng)模型評(píng)估其邊緣計(jì)算架構(gòu)的性能，并與標(biāo)準(zhǔn)移動(dòng)眾包架構(gòu)進(jìn)行對(duì)比。文獻(xiàn)[20]利用Petri網(wǎng)模型評(píng)估數(shù)據(jù)的可追溯性。對(duì)系統(tǒng)的各組件及參數(shù)建模，可以輔助驗(yàn)證優(yōu)化算法的可行性、有效性、優(yōu)化性。
2.優(yōu)化目標(biāo)及約束
將用戶、運(yùn)營(yíng)方等方面的需求建模為優(yōu)化目標(biāo)與約束，進(jìn)而尋求問(wèn)題的解決方案非常重要。文獻(xiàn)[10]整理了280項(xiàng)霧計(jì)算下的優(yōu)化指標(biāo)，包括時(shí)延、能耗、收益與花費(fèi)、設(shè)備相關(guān)和其他5大類。本節(jié)從性能、能耗、花費(fèi)3個(gè)方面介紹邊緣計(jì)算下優(yōu)化目標(biāo)和約束的建模與典型優(yōu)化方法。
2.1性能指標(biāo)
2.1.1時(shí)延
服務(wù)時(shí)延或反應(yīng)時(shí)間，是指應(yīng)用提交請(qǐng)求和收到回應(yīng)間的耗時(shí)[18]。時(shí)延是邊緣計(jì)算資源調(diào)度優(yōu)化的重要指標(biāo)。文獻(xiàn)[10]將時(shí)延分為計(jì)算節(jié)點(diǎn)上耗時(shí)、節(jié)點(diǎn)間傳輸耗時(shí)及計(jì)算節(jié)點(diǎn)間遷移時(shí)間共6類。
針對(duì)邊緣計(jì)算環(huán)境，文獻(xiàn)[18]給出了時(shí)延解析模型，任務(wù)的服務(wù)時(shí)延由不同計(jì)算節(jié)點(diǎn)的處理時(shí)延按分配概率加權(quán)計(jì)算得到。文獻(xiàn)[21]考慮架構(gòu)中的網(wǎng)關(guān)數(shù)量以及緩沖區(qū)占用率等情況，定義了多個(gè)時(shí)延計(jì)算方程。除理論模型外，文獻(xiàn)[22]對(duì)霧計(jì)算時(shí)延進(jìn)行了實(shí)驗(yàn)統(tǒng)計(jì)分析，統(tǒng)計(jì)了不同應(yīng)用、http需求等在不同霧計(jì)算設(shè)備、不同環(huán)境下的時(shí)延，發(fā)現(xiàn)II型廣義極值分布能較好地模擬時(shí)延，指出小型計(jì)算任務(wù)時(shí)延取決于通訊時(shí)間且不同環(huán)境對(duì)時(shí)延的影響最高可達(dá)11倍。此外，針對(duì)時(shí)延的穩(wěn)定性實(shí)驗(yàn)表明，時(shí)延敏感型任務(wù)應(yīng)將根據(jù)環(huán)境變化而調(diào)整分配方案。目前，以最小化時(shí)延為目標(biāo)的算法很多，分布式優(yōu)化策略、計(jì)算任務(wù)卸載、任務(wù)調(diào)度等方法或模型都旨在降低時(shí)延進(jìn)而提升系統(tǒng)性能。
2.1.2截止時(shí)間
除最小化時(shí)延外，任務(wù)的截止時(shí)間可表示任務(wù)的緊迫程度。實(shí)時(shí)系統(tǒng)[23]給出硬期限和軟期限的定義。不同任務(wù)的時(shí)延敏感度不同，一些任務(wù)未能在期限前完成則會(huì)出現(xiàn)嚴(yán)重后果，于是被定義為硬期限約束任務(wù)，否則為軟期限約束任務(wù)。若完成時(shí)間大于期限，則存在拖期，即完成時(shí)間和期限之差。此外，時(shí)間相關(guān)效率函數(shù)也被用來(lái)描述任務(wù)完成時(shí)間的要求，譬如用階躍函數(shù)刻畫硬約束，用衰減指數(shù)函數(shù)作為延時(shí)函數(shù)，任務(wù)完成時(shí)間越晚則其完成效用越低。
文獻(xiàn)[24]提出在線調(diào)度方法，最大化滿足截止時(shí)間的任務(wù)個(gè)數(shù)。文獻(xiàn)[25]將用戶體驗(yàn)轉(zhuǎn)化為任務(wù)截止時(shí)間并作為問(wèn)題的約束，優(yōu)化獲得滿足條件的可行解。文獻(xiàn)[26]在定義適配值時(shí)對(duì)超過(guò)截止時(shí)間的應(yīng)用添加懲罰項(xiàng)。文獻(xiàn)[27]將工作流中的子任務(wù)按期限類型分為硬期限和軟期限約束任務(wù)，分別考慮其合法性和拖期大小。文獻(xiàn)[22]用概率分布函數(shù)模擬任務(wù)時(shí)延，對(duì)任務(wù)完成的時(shí)間函數(shù)與設(shè)定時(shí)間相關(guān)效率函數(shù)的積分作為任務(wù)完成效率，并最大化任務(wù)分配問(wèn)題的任務(wù)完成效率。目前，根據(jù)任務(wù)特征及邊緣計(jì)算場(chǎng)景需求選擇合適的指標(biāo)，設(shè)計(jì)特定優(yōu)化算法，是截止時(shí)間相關(guān)優(yōu)化問(wèn)題的重點(diǎn)。
2.1.3用戶體驗(yàn)質(zhì)量
相比于客觀的時(shí)延等性能，QoE的定義依賴于用戶、環(huán)境和服務(wù)，較為主觀。在國(guó)際電信聯(lián)盟給出的定義基礎(chǔ)上，文獻(xiàn)[28]將QoE定義為用戶在一定的客觀環(huán)境中對(duì)所使用的服務(wù)或者業(yè)務(wù)對(duì)整體的認(rèn)可程度。常見的QoE優(yōu)化問(wèn)題要求提高用戶對(duì)音頻質(zhì)量、視頻清晰度的滿意程度等。隨著移動(dòng)端視頻需求的增大，對(duì)QoE的量化、建模及優(yōu)化的研究日益增多。邊緣計(jì)算作為降低即時(shí)應(yīng)用時(shí)延的解決方案之一，可提高用戶滿意度，通過(guò)部署霧節(jié)點(diǎn)提供霧計(jì)算服務(wù)，因而考慮QoE的邊緣資源分配和任務(wù)調(diào)度策略可為用戶提供更優(yōu)質(zhì)的服務(wù)。
為了優(yōu)化用戶玩交互游戲的體驗(yàn)，文獻(xiàn)[29]綜合反應(yīng)時(shí)間、網(wǎng)絡(luò)擁塞和服務(wù)覆蓋度作為用戶的QoE，并設(shè)計(jì)Cloud-Fog系統(tǒng)，從而降低時(shí)延，提升終端用戶的覆蓋度。文獻(xiàn)[30]利用QoE指標(biāo)估計(jì)和指導(dǎo)下一步的資源分配。另外，文獻(xiàn)[15]將QoE設(shè)為邊緣計(jì)算資源配置算法的唯一優(yōu)化目標(biāo)，根據(jù)用戶對(duì)應(yīng)用的期待和邊緣計(jì)算資源狀態(tài)，匹配“特定應(yīng)用-計(jì)算節(jié)點(diǎn)”，從而優(yōu)化整體滿意度。目前，如何與具體問(wèn)題結(jié)合來(lái)量化QoE并設(shè)計(jì)優(yōu)化算法，滿足用戶需求并提升滿意度，是重點(diǎn)的研究工作。
2.2能耗指標(biāo)
能耗是數(shù)據(jù)中心的主要開銷之一，包括計(jì)算機(jī)器、制冷散熱設(shè)備耗電等。將計(jì)算設(shè)備移至網(wǎng)絡(luò)邊緣，保證資源有限的電池供電設(shè)備正常運(yùn)行非常重要。文獻(xiàn)[31]探討了邊緣計(jì)算是否能節(jié)省云計(jì)算能耗，討論了下載、更新、預(yù)加載數(shù)據(jù)量等應(yīng)用以及不同場(chǎng)景下用電量的變化。研究不同情況下的資源分配和任務(wù)調(diào)度對(duì)降低能耗很有意義。
2.2.1電池電量
邊緣計(jì)算環(huán)境下，移動(dòng)終端設(shè)備的電池電量約束問(wèn)題亟待研究，其中耗電量分為監(jiān)測(cè)、計(jì)算、通訊和執(zhí)行4部分[32]。監(jiān)測(cè)耗電量與其數(shù)據(jù)包大小、時(shí)長(zhǎng)相關(guān)；通訊分為上傳和接收2部分，上傳能耗與數(shù)據(jù)量及傳輸距離正相關(guān)，接收能耗與數(shù)據(jù)量正相關(guān)；計(jì)算能耗取決于具體硬件參數(shù)；執(zhí)行能耗與具體執(zhí)行應(yīng)用和次數(shù)正相關(guān)。文獻(xiàn)[33]在應(yīng)用截止時(shí)間約束下，分配和排序任務(wù)最小化物聯(lián)網(wǎng)設(shè)備總能耗。此外，文獻(xiàn)[34]將系統(tǒng)的生存周期定義為所有傳感器中最先耗盡電量的傳感器的工作時(shí)長(zhǎng)，進(jìn)而延長(zhǎng)系統(tǒng)生存周期成為一個(gè)優(yōu)化目標(biāo)。目前，如何有效的節(jié)約移動(dòng)端電量，并維持系統(tǒng)穩(wěn)定，是研究工作的重點(diǎn)。
2.2.2其他能耗
文獻(xiàn)[31]給出了路由器等多用戶訪問(wèn)的網(wǎng)絡(luò)設(shè)備和家用服務(wù)器等計(jì)算設(shè)備的能耗模型，其中網(wǎng)絡(luò)設(shè)備主要依據(jù)數(shù)據(jù)流量計(jì)算能耗，服務(wù)器能耗則基于時(shí)間，同時(shí)指出微型服務(wù)器接入特定類型網(wǎng)絡(luò)、活躍時(shí)間呈一定比例、下載活動(dòng)占較大比例的應(yīng)用等情形下邊緣計(jì)算可節(jié)省云計(jì)算中心的能耗。
文獻(xiàn)[35]將邊緣計(jì)算節(jié)點(diǎn)能耗建模為關(guān)于計(jì)算量的單增嚴(yán)格凸函數(shù)，并用二次函數(shù)刻畫其特性，用服務(wù)器開關(guān)狀態(tài)以及處理器CPU頻率的一次函數(shù)刻畫云計(jì)算節(jié)點(diǎn)能耗。文獻(xiàn)[36]將能耗分為空閑時(shí)和占用時(shí)能耗2類，可以通過(guò)對(duì)時(shí)間積分計(jì)算。目前，針對(duì)邊緣計(jì)算和云計(jì)算節(jié)點(diǎn)的能耗優(yōu)化，包括總能耗的優(yōu)化、性能和能耗的多目標(biāo)均衡優(yōu)化。
2.3花費(fèi)指標(biāo)
經(jīng)濟(jì)指標(biāo)是用戶選擇資源以及運(yùn)營(yíng)商提供解決方案時(shí)需要考慮的重要因素。云計(jì)算的廣泛應(yīng)用一定程度上取決于其成功的“pay-as-you-go”商業(yè)模式?？梢?，服務(wù)的合理定價(jià)和對(duì)商業(yè)成本的優(yōu)化是邊緣計(jì)算亟待解決的重要問(wèn)題。資源調(diào)度優(yōu)化的花費(fèi)主要集中于計(jì)算、存儲(chǔ)和網(wǎng)絡(luò)等資源成本。
文獻(xiàn)[37]在考慮性能、虛擬機(jī)等約束下，將虛擬機(jī)的配置成本和數(shù)據(jù)通訊的花費(fèi)之和作為優(yōu)化目標(biāo)，獲得最優(yōu)的用戶基站選擇、虛擬機(jī)-基站的配對(duì)等解決方案。文獻(xiàn)[38]考慮城域網(wǎng)中的經(jīng)濟(jì)成本問(wèn)題，將應(yīng)用分為只需計(jì)算、只需存儲(chǔ)以及存儲(chǔ)與計(jì)算等類別，以計(jì)算節(jié)點(diǎn)計(jì)算、存儲(chǔ)、鏈路容量和時(shí)延為約束，最小化支持網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下的經(jīng)濟(jì)成本，包括計(jì)算、存儲(chǔ)、城域網(wǎng)帶寬和核心計(jì)算節(jié)點(diǎn)上下游各項(xiàng)的成本。同時(shí)，參考谷歌云等的價(jià)格模型給出了不同計(jì)算節(jié)點(diǎn)的計(jì)算、存儲(chǔ)的價(jià)格，價(jià)格差異將導(dǎo)致不同應(yīng)用的資源選擇方案不同。目前，如何將定價(jià)模型和實(shí)際應(yīng)用結(jié)合，根據(jù)邊緣計(jì)算特點(diǎn)定義花費(fèi)和建立優(yōu)化模型，是研究工作的重點(diǎn)。
3.
調(diào)度優(yōu)化模型及求解方法
本節(jié)針對(duì)“云-邊-端”計(jì)算系統(tǒng)，介紹單一任務(wù)的卸載或分配決策、多任務(wù)分配及調(diào)度、邊緣計(jì)算環(huán)境中的資源約束與和任務(wù)優(yōu)先關(guān)系約束、相應(yīng)的求解方法。體系結(jié)構(gòu)如圖2所示，其中決策變量為xi,j,r=1，表示任務(wù)i在計(jì)算節(jié)點(diǎn)j上第r個(gè)處理。
圖2邊緣計(jì)算資源分配與任務(wù)調(diào)度優(yōu)化
Fig.2 Edge computing resource allocation and task scheduling optimization
3.1獨(dú)立任務(wù)卸載/分配
3.1.1問(wèn)題與模型
邊緣計(jì)算旨在減輕網(wǎng)絡(luò)負(fù)載、分擔(dān)終端計(jì)算任務(wù)，而獨(dú)立任務(wù)的卸載決策則是基礎(chǔ)。文獻(xiàn)[39]探討了移動(dòng)終端的任務(wù)卸載決策問(wèn)題，包括何時(shí)卸載、靜止/動(dòng)態(tài)、確定任務(wù)是否卸載、卸載收益等。文中指出卸載的目的是提高性能、節(jié)省能耗，并指出很有必要卸載高計(jì)算量和低數(shù)據(jù)量的任務(wù)。文獻(xiàn)[40]在智能網(wǎng)關(guān)場(chǎng)景下，根據(jù)能量狀態(tài)、數(shù)據(jù)類型和通訊頻率進(jìn)行卸載決策，同時(shí)介紹了物聯(lián)網(wǎng)中間件支撐卸載決策的技術(shù)手段與常見的任務(wù)卸載場(chǎng)景。
獨(dú)立任務(wù)的卸載或分配，可看作x1,j,1的0/1決策問(wèn)題，如圖2所示，即確定任務(wù)是否分配至節(jié)點(diǎn)j。多個(gè)獨(dú)立任務(wù)的卸載或分配，可看作xi,j,1的0/1決策問(wèn)題，即任務(wù)i和節(jié)點(diǎn)j的匹配問(wèn)題，以實(shí)現(xiàn)負(fù)載均衡。如果計(jì)算節(jié)點(diǎn)特定時(shí)間內(nèi)最多只能處理一個(gè)任務(wù)時(shí)，可看作xi,j,r的0/1決策問(wèn)題，即任務(wù)-節(jié)點(diǎn)匹配和節(jié)點(diǎn)上的任務(wù)排序問(wèn)題。
排隊(duì)模型、狀態(tài)轉(zhuǎn)移方程等解析模型可用于分析邊緣節(jié)點(diǎn)任務(wù)卸載策略的有效性。文獻(xiàn)[41]針對(duì)環(huán)形拓?fù)浣Y(jié)構(gòu)邊緣節(jié)點(diǎn)間的負(fù)載均衡問(wèn)題，建立了隨機(jī)游走模型，分析了超負(fù)荷節(jié)點(diǎn)是否應(yīng)向相鄰節(jié)點(diǎn)卸載任務(wù)。文獻(xiàn)[21]基于邊緣節(jié)點(diǎn)和任務(wù)的數(shù)據(jù)、緩存狀態(tài)、數(shù)據(jù)接收和計(jì)算能力等特點(diǎn)，建立了狀態(tài)更新、網(wǎng)關(guān)和云計(jì)算節(jié)點(diǎn)排隊(duì)模型，并提出了分布式算法優(yōu)化整體時(shí)延。文獻(xiàn)[42]將車輛視作邊緣節(jié)點(diǎn)構(gòu)建交通管理模型，利用排隊(duì)論和馬爾科夫轉(zhuǎn)移方程對(duì)任務(wù)處理狀態(tài)建模，進(jìn)而決策節(jié)點(diǎn)間的計(jì)算轉(zhuǎn)移。
3.1.2啟發(fā)式策略
智能終端設(shè)備具有決策能力，鑒于邊緣計(jì)算環(huán)境的動(dòng)態(tài)性、不確定性，研究邊緣節(jié)點(diǎn)根據(jù)環(huán)境和自身狀態(tài)的分布式在線決策算法十分必要。文獻(xiàn)[43]對(duì)每個(gè)終端預(yù)先分別計(jì)算各項(xiàng)任務(wù)在邊緣和云層的能耗，進(jìn)而確定是否卸載任務(wù)。文獻(xiàn)[18]提出了分布式卸載策略，邊緣節(jié)點(diǎn)針對(duì)請(qǐng)求判斷計(jì)算時(shí)延是否超過(guò)閾值，進(jìn)而將請(qǐng)求加入隊(duì)列，或獲取周邊節(jié)點(diǎn)狀態(tài)選擇最佳卸載對(duì)象，若無(wú)合適節(jié)點(diǎn)則上傳云端處理。同時(shí)，文中提出解析模型分析了分布式算法的可行性和有效性。文獻(xiàn)[44]討論了全卸載、部分卸載等策略，利用改進(jìn)交替方向乘子法同時(shí)優(yōu)化用戶的平均時(shí)延和能耗。
針對(duì)多任務(wù)分配問(wèn)題，文獻(xiàn)[24]分別給出了集中式和分布式在線優(yōu)化算法，最大化滿足截止期限的任務(wù)個(gè)數(shù)，其中分布式算法在接入節(jié)點(diǎn)和邊緣節(jié)點(diǎn)實(shí)現(xiàn)。文獻(xiàn)[15]對(duì)QoE建立模糊模型，給出了霧計(jì)算環(huán)境下最大化QoE的多任務(wù)分配方案。
3.2資源約束下的任務(wù)分配
3.2.1優(yōu)化問(wèn)題
由于計(jì)算系統(tǒng)的計(jì)算、存儲(chǔ)、帶寬、電池電量等資源有限，將有限資源作為約束給出調(diào)度優(yōu)化模型，更符合現(xiàn)實(shí)。文獻(xiàn)[45]提出了帶CPU容量、電池電量約束的任務(wù)-節(jié)點(diǎn)分配模型。文獻(xiàn)[11]將任務(wù)分配問(wèn)題按約束分為網(wǎng)絡(luò)、節(jié)點(diǎn)、能耗和應(yīng)用4類，其中計(jì)算節(jié)點(diǎn)約束分為軟件約束(如庫(kù)、操作系統(tǒng))和硬件約束(如內(nèi)存、CPU、存儲(chǔ))。
求解資源約束下的任務(wù)分配問(wèn)題即尋找滿足約束的任務(wù)-計(jì)算節(jié)點(diǎn)分配方案。對(duì)于計(jì)算、內(nèi)存、帶寬有限的物理設(shè)備或虛擬機(jī)，可建立相應(yīng)的多維背包[46]模型。
3.2.2模型與算法
資源約束可表示為Σi(Σrxi,j,r)·ai,j≤Aj，如圖2所示，其中Σrxi,j,r=1表示任務(wù)i分配至節(jié)點(diǎn)j，ai,j表示任務(wù)i占用的某類資源量，Aj表示節(jié)點(diǎn)j該資源總量。當(dāng)沒(méi)有任務(wù)處理時(shí)間約束時(shí)，可建模為多個(gè)物品分配到若干多維背包的匹配問(wèn)題。考慮邊緣計(jì)算節(jié)點(diǎn)的容量，文獻(xiàn)[22]給出容量有限情況的動(dòng)態(tài)規(guī)劃求解方法，通過(guò)計(jì)算任務(wù)分配收益、拒絕無(wú)法分配的任務(wù)，最大化整體處理效率。針對(duì)工業(yè)4.0場(chǎng)景下的任務(wù)-網(wǎng)關(guān)分配問(wèn)題，文獻(xiàn)[26]利用負(fù)載-風(fēng)險(xiǎn)模型定義任務(wù)分配的可靠性，提出相應(yīng)的貪婪算法尋求同時(shí)滿足時(shí)延和可靠性要求的方案。文獻(xiàn)[47]建立混合整數(shù)規(guī)劃模型，確定滿足邊緣節(jié)點(diǎn)CPU、內(nèi)存和存儲(chǔ)容量約束的利用率最大化且的任務(wù)分配方案。文獻(xiàn)[17]標(biāo)記節(jié)點(diǎn)的硬軟件參數(shù)，設(shè)計(jì)并實(shí)現(xiàn)了任務(wù)分配的回溯搜索算法。
對(duì)于一些復(fù)雜情況，資源約束下的任務(wù)分配問(wèn)題僅是子問(wèn)題之一。針對(duì)邊緣節(jié)點(diǎn)的容量約束和云節(jié)點(diǎn)的CPU頻率約束下的負(fù)載均衡問(wèn)題，文獻(xiàn)[35]將原始問(wèn)題分解成邊緣節(jié)點(diǎn)負(fù)載分配、云節(jié)點(diǎn)負(fù)載分配和最小化時(shí)延指派問(wèn)題3個(gè)子問(wèn)題，分別利用凸優(yōu)化、Benders分解和匈牙利算法求解。文獻(xiàn)[48]約定存儲(chǔ)服務(wù)器預(yù)存任務(wù)圖像后才能處理相關(guān)的讀寫操作，即任務(wù)圖像-存儲(chǔ)器的匹配子問(wèn)題，通過(guò)松弛0–1決策變量利用貪婪算法獲得可行解。
3.2.3智能算法
鑒于在諸多復(fù)雜問(wèn)題上的優(yōu)越性能，智能算法在本領(lǐng)域得到了推廣應(yīng)用。文獻(xiàn)[49]采用分布式遺傳算法(Genetic Algorithm，GA)求解CPU、內(nèi)存和帶寬約束下混合云任務(wù)分配問(wèn)題，利用有偏隨機(jī)鍵和特定解碼規(guī)則處理不可行解，最大化同時(shí)處理的任務(wù)數(shù)。文獻(xiàn)[25]用GA求解任務(wù)-公交車的分配問(wèn)題，在節(jié)點(diǎn)計(jì)算容量約束下尋求經(jīng)濟(jì)成本最低的方案。文獻(xiàn)[50]提出了一種共生有機(jī)體搜索算法，在不同場(chǎng)景下向虛擬機(jī)分配任務(wù)，評(píng)價(jià)成本、網(wǎng)絡(luò)占用和能耗指標(biāo)。針對(duì)CPU算力約束下的邊緣計(jì)算容器遷移問(wèn)題，文獻(xiàn)[51]將遷移策略建模為多維馬爾科夫過(guò)程空間，并利用深度強(qiáng)化學(xué)習(xí)快速?zèng)Q策。
3.3帶優(yōu)先約束任務(wù)調(diào)度/卸載
3.3.1優(yōu)化問(wèn)題
為了加快計(jì)算進(jìn)程，將分布式計(jì)算系統(tǒng)中的復(fù)雜任務(wù)分割為多個(gè)子任務(wù)形成任務(wù)流，進(jìn)而分配到處理器上并行處理。由于部分任務(wù)的計(jì)算需要前序任務(wù)的結(jié)果數(shù)據(jù)，任務(wù)間存在優(yōu)先約束關(guān)系，可利用有向無(wú)環(huán)圖DAG(directed acyclic graph)抽象和建模工作流，圖節(jié)點(diǎn)代表子任務(wù)，節(jié)點(diǎn)間連線代表子任務(wù)間的優(yōu)先約束關(guān)系。文獻(xiàn)[52]給出了DAG調(diào)度問(wèn)題的樹形圖，考慮任務(wù)間是否存在通訊時(shí)間、處理器資源是否有限、處理器是否完全連接等多種情況。
3.3.2數(shù)學(xué)模型及相關(guān)算法
任務(wù)間優(yōu)先約束表示為EST(j)≤CT(i)，∀i→j，如圖2所示，其中EST(j)表示任務(wù)j可開始處理的最早時(shí)間，CT(i)表示任務(wù)i的完成時(shí)間，i→j表示任務(wù)i到j(luò)存在優(yōu)先約束。
針對(duì)移動(dòng)端卸載問(wèn)題，設(shè)定處理器同一時(shí)間可以處理多個(gè)任務(wù)，文獻(xiàn)[53]提出了基于動(dòng)態(tài)規(guī)劃的確定性時(shí)延約束任務(wù)分割算法，證明了其次優(yōu)性。針對(duì)截止時(shí)間約束下的能耗最小化問(wèn)題，不限制DAG的拓?fù)浣Y(jié)構(gòu)，但約定處理器在同一時(shí)間只能處理一個(gè)任務(wù)，文獻(xiàn)[54]給出了邊緣計(jì)算節(jié)點(diǎn)與遠(yuǎn)端云節(jié)點(diǎn)協(xié)同環(huán)境下的DAG混合整數(shù)規(guī)劃模型。該問(wèn)題包含具有NP難特性的一般性指派問(wèn)題，目前沒(méi)有多項(xiàng)式時(shí)間的最優(yōu)化方法。文獻(xiàn)[54]利用松弛整數(shù)規(guī)劃模型中的0–1變量將問(wèn)題轉(zhuǎn)換為凸優(yōu)化問(wèn)題，進(jìn)而設(shè)計(jì)啟發(fā)式方法。針對(duì)多DAG的移動(dòng)終端卸載問(wèn)題，文獻(xiàn)[55]提出了混合整數(shù)規(guī)劃模型，對(duì)是否將任務(wù)上傳云端進(jìn)行決策，并在截止時(shí)間約束下優(yōu)化能耗。
3.3.3啟發(fā)式方法
DAG調(diào)度優(yōu)化方法主要包括啟發(fā)式方法、智能算法及混合算法[56]，其中啟發(fā)式方法主要分為列表調(diào)度、聚類和任務(wù)復(fù)制3類。列表調(diào)度方法按優(yōu)先級(jí)排列任務(wù)，然后從待調(diào)度的任務(wù)中選擇最高優(yōu)先級(jí)的任務(wù)分配給合適的處理器[57]；聚類方法將任務(wù)聚類，直到類別數(shù)與處理器數(shù)相等[58,59]。任務(wù)復(fù)制將傳輸數(shù)據(jù)量大的任務(wù)復(fù)制到多個(gè)處理器上處理，進(jìn)而降低時(shí)延。
在“云-邊-端”系統(tǒng)下，文獻(xiàn)[60]將前向排名作為列表調(diào)度準(zhǔn)則，同時(shí)優(yōu)化時(shí)延以及云和邊緣計(jì)算節(jié)點(diǎn)的計(jì)算與通訊成本。同時(shí)考慮截止時(shí)間和費(fèi)用，文獻(xiàn)[54]利用下界估計(jì)等方法為DAG的子任務(wù)分配截止時(shí)間并為任務(wù)分配計(jì)算節(jié)點(diǎn)。參照任務(wù)截止時(shí)間的順序，文獻(xiàn)[61]依據(jù)任務(wù)的最早完成時(shí)間插空分配虛擬機(jī)，進(jìn)而優(yōu)化整體時(shí)間性能。
3.3.4智能算法
區(qū)別于啟發(fā)式規(guī)則，智能算法力爭(zhēng)全局的優(yōu)化性能。文獻(xiàn)[62]利用GA優(yōu)化任務(wù)-邊緣節(jié)點(diǎn)群的分配。文獻(xiàn)[12]采用概率表征任務(wù)間的前后位置關(guān)系，在基于啟發(fā)式方法的DAG預(yù)分割后，利用雙變量相關(guān)的分布估計(jì)算法排序任務(wù)，同時(shí)優(yōu)化應(yīng)用整體完成時(shí)間和邊緣節(jié)點(diǎn)能耗。文獻(xiàn)[27]考慮任務(wù)截止時(shí)間信息，利用EDA優(yōu)化總拖期。針對(duì)任務(wù)-節(jié)點(diǎn)分配問(wèn)題，文獻(xiàn)[63]利用粒子群算法優(yōu)化成本和完成時(shí)間的加權(quán)目標(biāo)。
針對(duì)邊緣計(jì)算資源分配和任務(wù)調(diào)度問(wèn)題，從任務(wù)卸載決策、資源約束下的任務(wù)分配、DAG調(diào)度與分配的上述綜述可見：一些建模工作比較系統(tǒng)，在剖析系統(tǒng)特性的基礎(chǔ)上提出了精確方法，但算法復(fù)雜性高，占用計(jì)算資源多，不適用于大規(guī)模問(wèn)題；大部分工作采用啟發(fā)式策略分配資源和調(diào)度任務(wù)，盡管面對(duì)大規(guī)模任務(wù)和異構(gòu)化的資源，這類方法設(shè)計(jì)方便、易于實(shí)現(xiàn)且不占用過(guò)多的計(jì)算資源，但難以取得很好的整體優(yōu)化效果；智能算法適用于強(qiáng)約束、多目標(biāo)的復(fù)雜問(wèn)題，可拓展性強(qiáng)，但很難適用于分布式在線問(wèn)題等實(shí)時(shí)性要求高的場(chǎng)景。
4.
應(yīng)用與仿真驗(yàn)證
邊緣計(jì)算技術(shù)已在增強(qiáng)現(xiàn)實(shí)、圖像識(shí)別、網(wǎng)站性能優(yōu)化、智慧城市、車聯(lián)網(wǎng)等諸多領(lǐng)域得到成功應(yīng)用[64]。邊緣計(jì)算資源分配和任務(wù)調(diào)度優(yōu)化亦在相關(guān)領(lǐng)域發(fā)揮了巨大作用。為了對(duì)資源管理策略進(jìn)行評(píng)價(jià)，邊緣環(huán)境的實(shí)證分析十分必要。由于現(xiàn)實(shí)邊緣計(jì)算環(huán)境搭建難度大、實(shí)體變更成本高，仿真已成為重要的工具。通過(guò)提供自定義接口，可重復(fù)評(píng)估實(shí)驗(yàn)，進(jìn)而驗(yàn)證資源分配與任務(wù)調(diào)度優(yōu)化的算法性能。
對(duì)邊緣計(jì)算環(huán)境建模與實(shí)驗(yàn)運(yùn)行的現(xiàn)有模擬器與工具包有Edgecloudsim[65]，iFogSim[66]，DeFog[67]等。其中，DeFog可建模邊緣計(jì)算環(huán)境，搜集測(cè)試應(yīng)用，譬如深度學(xué)習(xí)目標(biāo)檢測(cè)、語(yǔ)音識(shí)別、在線游戲等，標(biāo)記測(cè)量并發(fā)數(shù)、成功率、平均時(shí)延和上傳下載數(shù)據(jù)量等指標(biāo)，輔助分析算法的有效性。文獻(xiàn)[47，68]則利用iFogSim驗(yàn)證資源調(diào)度策略的有效性。
除了仿真驗(yàn)證，一些調(diào)度算法被用于真實(shí)邊緣場(chǎng)景解決實(shí)際問(wèn)題，表1列舉了一些實(shí)際案例，包括制造業(yè)[26,36]、交通運(yùn)輸[25,42]、視頻處理[20,55,68]等領(lǐng)域。當(dāng)然，對(duì)于不同領(lǐng)域的應(yīng)用，目標(biāo)以及相應(yīng)的建模與優(yōu)化算法都有所不同。
表1應(yīng)用場(chǎng)景與調(diào)度問(wèn)題
Tab.1 Applications and scheduling problems
對(duì)于任務(wù)卸載問(wèn)題，算法主要決策任務(wù)的派發(fā)與卸載，譬如文獻(xiàn)[68]將視頻監(jiān)控應(yīng)用分為用戶交互、目標(biāo)探測(cè)和追蹤等任務(wù)，算法主要解決任務(wù)分類、處理器類型匹配等問(wèn)題。對(duì)于資源約束問(wèn)題，文獻(xiàn)[20，26]考慮帶寬、CPU等約束，文獻(xiàn)[25]將完成時(shí)間和邊緣節(jié)點(diǎn)存儲(chǔ)作為約束，文獻(xiàn)[69]則將實(shí)時(shí)功耗的上限作為約束。對(duì)于任務(wù)間無(wú)法忽視的優(yōu)先約束，文獻(xiàn)[17，55]將其設(shè)置為問(wèn)題的一個(gè)維度進(jìn)行調(diào)度優(yōu)化。
5.
結(jié)論
隨著邊緣計(jì)算的快速發(fā)展，資源分配和任務(wù)調(diào)度的研究面臨諸多挑戰(zhàn)，從5個(gè)方面進(jìn)行討論。
(1)理論
在理論層面，面向復(fù)雜問(wèn)題或應(yīng)用場(chǎng)景，理論性成果很匱乏。譬如，研究截止時(shí)間的優(yōu)化算法的可調(diào)度性、計(jì)算資源受限下調(diào)度算法的計(jì)算復(fù)雜度、分布式優(yōu)化算法的收斂性。同時(shí)，針對(duì)簡(jiǎn)化模型的尋優(yōu)算法的收斂性與魯棒性、基于模型的問(wèn)題下界，都是很有意義的理論研究?jī)?nèi)容。
另外，面對(duì)多目標(biāo)優(yōu)化問(wèn)題，目標(biāo)均衡策略、協(xié)同優(yōu)化機(jī)制、決策空間與目標(biāo)空間的分解策略、層次分析等方法與技術(shù)的研究、改進(jìn)均有待相應(yīng)的理論分析的支撐。
(2)建模
在模型層面，大規(guī)模的邊緣節(jié)點(diǎn)、有限的計(jì)算資源、不穩(wěn)定的網(wǎng)絡(luò)連接不穩(wěn)定、異構(gòu)性的平臺(tái)，都給問(wèn)題的建模帶來(lái)挑戰(zhàn)。針對(duì)大規(guī)模和異構(gòu)等特點(diǎn)，可建立分布式模型；針對(duì)網(wǎng)絡(luò)、計(jì)算資源、物聯(lián)網(wǎng)應(yīng)用的不穩(wěn)定特性，可建立不確定模型；針對(duì)需求的實(shí)時(shí)性和動(dòng)態(tài)性，可建立動(dòng)態(tài)和重調(diào)度模型，進(jìn)而設(shè)計(jì)相應(yīng)的方法獲得可行、有效、魯棒的調(diào)度方案，保證滿意的實(shí)時(shí)性、可擴(kuò)展性、魯棒性等。
(3)方法
在方法層面，要同時(shí)注重基于數(shù)學(xué)模型和數(shù)據(jù)驅(qū)動(dòng)的優(yōu)化調(diào)度策略、算法研究。盡管精確求解方法因?qū)?yōu)效率低而不適用于大規(guī)模邊緣計(jì)算節(jié)點(diǎn)與物聯(lián)網(wǎng)應(yīng)用，但問(wèn)題的可調(diào)度性研究有理論意義。盡管啟發(fā)式與貪婪搜索方法難以取得全局性能，但適用于對(duì)優(yōu)化質(zhì)量要求不高的實(shí)時(shí)邊緣計(jì)算場(chǎng)景。智能算法是進(jìn)一步研究的重點(diǎn)，但必須結(jié)合實(shí)際應(yīng)用的需求兼顧計(jì)算效率和優(yōu)化質(zhì)量。
考慮到邊緣計(jì)算環(huán)境的實(shí)時(shí)性與動(dòng)態(tài)性、計(jì)算資源的有限性、缺少獲取所有邊緣節(jié)點(diǎn)狀態(tài)的主節(jié)點(diǎn)等情況，分布式優(yōu)化方法的研究值得關(guān)注與發(fā)展。另外，隨著人工智能技術(shù)的發(fā)展，將優(yōu)化方法與深度學(xué)習(xí)、強(qiáng)化學(xué)習(xí)等有機(jī)結(jié)合，利用已有調(diào)度案例數(shù)據(jù)實(shí)現(xiàn)模型的線下訓(xùn)練，進(jìn)而再開展線上優(yōu)化與決策，是當(dāng)前研究的熱點(diǎn)方向。
(4)驗(yàn)證
理論分析、性能對(duì)比、仿真驗(yàn)證，都是調(diào)度優(yōu)化算法驗(yàn)證層面可開展的工作。譬如，利用排隊(duì)模型或狀態(tài)轉(zhuǎn)移模型建立邊緣計(jì)算節(jié)點(diǎn)任務(wù)處理狀態(tài)的模型并開展性能分析，利用Petri網(wǎng)模型評(píng)估系統(tǒng)的性能和可靠性，利用數(shù)學(xué)規(guī)劃模型獲得性能的界作為尋優(yōu)算法的對(duì)比基準(zhǔn)。
另外，搭建原型系統(tǒng)驗(yàn)證所提算法的可用性、有效性、高效性，是實(shí)際應(yīng)用的必要前提，尤其是智能戰(zhàn)場(chǎng)等復(fù)雜應(yīng)用對(duì)邊緣計(jì)算側(cè)仿真提出了很高的實(shí)際需求[70]。只有通過(guò)面向?qū)嶋H系統(tǒng)的驗(yàn)證，才能為算法的可行性、有效性、穩(wěn)定性提供充分說(shuō)服力的依據(jù)。
(5)推廣與應(yīng)用
邊緣計(jì)算調(diào)度優(yōu)化理論與方法的研究，是技術(shù)實(shí)現(xiàn)與應(yīng)用的前提。通過(guò)實(shí)際系統(tǒng)的應(yīng)用，一方面可驗(yàn)證理論與算法的有效性，另一方面可發(fā)現(xiàn)新的問(wèn)題與需求，通過(guò)推廣應(yīng)用使得理論與方法的研究得到進(jìn)一步完善與發(fā)展。先進(jìn)理論成果在實(shí)際工業(yè)、生活場(chǎng)景下驗(yàn)證和應(yīng)用，有利于加深對(duì)調(diào)度優(yōu)化問(wèn)題的理解，有效算法的成功應(yīng)用則將促進(jìn)邊緣計(jì)算技術(shù)的落地與發(fā)展。
總之，邊緣計(jì)算技術(shù)方興未艾，資源分配和任務(wù)調(diào)度作為核心問(wèn)題許多研究工作亟待深入，促進(jìn)理論、方法、技術(shù)與應(yīng)用的發(fā)展以及相關(guān)學(xué)科的交叉融合。
參考文獻(xiàn)
[1].Pang H H,Tan K L.Authenticating Query Results in Edge Computing[C]//20th International Conference on Data Engineering.Boston,MA,USA:IEEE Comput Soc,2004:560-571.
[2].Bonomi F,Milito R,Zhu J,et al.Fog Computing and its Role in the Internet of Things[C]//1st Edition MCC Workshop Mobile Cloud Comput.NY,USA:ACM,2012:13-16.
[3].Vaquero L M,Rodero-Merino L.Finding Your Way in the Fog:Towards a Comprehensive Definition of Fog Computing[J].ACM SIGCOMM Computer Communication Review(S0146-4833),2014,44(5):27-32.
[4].Hu P,Dhelim S,Ning H,et al.Survey on Fog Computing:Architecture,Key Technologies,Applications and Open Issues[J].Journal of Network and Computer Applications(S1084-8045),2017,98(11):27-42.
[5].Yousefpour A,Fung C,Nguyen T,et al.All One Needs to Know About Fog Computing and Related Edge Computing Paradigms:A Complete Survey[J].Journal of Systems Architecture(S1383-7621),2019,98(1):289-330.
[6].O.C.Architecture Working Group,Open Fog Reference Architecture for Fog Computing[R].2017,1(1):162.
[7].Shi W,Cao J,Zhang Q,et al.Edge Computing:Vision and Challenges[J].IEEE Internet of Things Journal(S2327-4662),2016,3(5):637-646.
[8].Hussain H,Malik S U R,Hameed A,et al.A Survey on Resource Allocation in High Performance Distributed Computing Systems[J].Parallel Computing(S0167-8191),2013,39(11):709-736.
[9].Bellendorf J,Mann ZÁ.Classification of Optimization Problems in Fog Computing[J].Future Generation Computer Systems(S0167-739X),2020,107(1):158-176.
[10].Brogi A,Forti S,Guerrero C,et al.How to Place Your Apps in the Fog:State of the Art and Open Challenges[J].Software:Practice and Experience(S0167-739X),2019,1(1):1-8.
[11].Wu C,Li W,Wang L,et al.Hybrid Evolutionary Scheduling for Energy-efficient Fog-enhanced Internet of Things[J].IEEE Transactions on Cloud Computing(S2168-7161),2018,1(1):1-1.
[12].Atzori L,Iera A,Morabito G.The Internet of Things:A Survey[J].Computer Networks(S1389-1286),2010,54(15):2787-2805.
[13].Bonomi F,Milito R,Natarajan P,et al.Fog Computing:A Platform for Internet of Things and Analytics.N.Bessis,C.Dobre.Big Data and Internet of Things:A roadmap for smart environments[M].Cham:Springer,2014,546:169-186.
[14].Mahmud R,Srirama S N,Ramamohanarao K,et al.Quality of Experience(QoE)-aware Placement of Applications in Fog Computing Environments[J].Journal of Parallel and Distributed Computing(S0743-7315),2019,132(1):190-203.
[15].Buyya R.,Srirama S.N.霧計(jì)算與邊緣計(jì)算:原理和范式[M].NJ,USA:Wiley,2019:31-50.
[16].Wu H,Yue K,Hsu C,et al.Deviation-based Neighborhood Model for Context-aware QoS Prediction of Cloud and IoT Services[J].Future Generation Computer Systems(S0167-739X),2017,76(1):550-560.
[17].Brogi A,Forti S.QoS-Aware Deployment of IoT Applications Through the Fog[J].IEEE Internet of Things Journal(S2327-4662),2017,4(5):1185-1192.
[18].Yousefpour A,Ishigaki G,Gour R,et al.On Reducing IoT Service Delay Via Fog Offloading[J].IEEE Internet of Things Journal(S2327-4662),2018,5(2):998-1010.
[19].Merlino G,Arkoulis S,Distefano S,et al.Mobile Crowdsensing as a Service[J].Future Generation Computer Systems(S0167-739X),2016,56(1):623-639.
[20].Lomotey R K,Pry J,Sriramoju S.Wearable IoT Data Stream Traceability in a Distributed Health Information System[J].Pervasive and Mobile Computing(S1574-1192),2017,40(1):692-707.
[21].Desikan K E S,Srinivasan M,Murthy C S R.A Novel Distributed Latency-aware Data Processing in Fog Computing-enabled IoT Networks[C]//Proc.of the ACM Workshop on Distributed Information Processing in Wireless Networks.Chennai,India:ACM,2017:1-6.
[22].Gorlatova M,Inaltekin H,Chiang M.Characterizing Task Completion Latencies in Fog Computing[J].Computer Networks(S1389-1286),2020,181:107526.
[23].Abbott R K,Garcia-Molina H.Scheduling Real-time Transactions:A Performance Evaluation[J].ACM Transactions on Database Systems(S0362-5915),1992,17(3):513-560.
[24].Meng J,Tan H,Li X Y,et al.Online Deadline-aware Task Dispatching and Scheduling in Edge Computing[J].IEEE Transactions on Parallel and Distributed Systems(S1045-9219),2020,31(6):1270-1286.
[25].Ye D,Wu M,Tang S,et al.Scalable Fog Computing with Service Offloading in Bus Networks[C]//3rd International Conference on Cyber Security and Cloud Computing.Beijing,China:IEEE,2016:247-251.
[26].Verba N,Chao K M,Lewandowski J,et al.Modeling Industry 4.0 based Fog Computing Environments for Application Analysis and Deployment[J].Future Generation Computer Systems(S0167-739X),2019,91(1):48-60.
[27].Wu C,Wang L.A Deadline-aware Estimation of Distribution Algorithm for Resource Scheduling in Fog Computing Systems[C]//IEEE Congress on Evolutionary Computation.Wellington,New Zealand:IEEE,2019:660-666.
[28].林闖,胡杰,孔祥震.用戶體驗(yàn)質(zhì)量(QoE)的模型與評(píng)價(jià)方法綜述[J].計(jì)算機(jī)學(xué)報(bào),2012,35(1):1-15.
Lin Chuang,Hu Jie,Kong Xiangzhen.Survey on Models and Evaluation of Quality of Experience[J].Chinese Journal of Computers,2012,35(1):1-15.
[29].Lin Y,Shen H.Cloud Fog:Towards high quality of experience in cloud gaming[C]//44th International Conference on Parallel Processing.Beijing,China:IEEE,2015:500-509.
[30].Aazam M,St-Hilaire M,Lung C,et al.MeFoRE:QoE based Resource Estimation at Fog to Enhance QoS in IoT[C]//23rd International Conference on Telecommunications.Thessaloniki,Greece:IEEE,2016:1-5.
[31].Jalali F,Hinton K,Ayre R,et al.Fog Computing May Help to Save Energy in Cloud Computing[J].IEEE Journal on Selected Areas in Communications(S0733-8716),2016,34(5):1728-1739.
[32].Halgamuge M N,Zukerman M,Ramamohanarao K,et al.An Estimation of Sensor Energy Consumption[J].Progress in Electromagnetics Research B(S1559-8985),2009,12(12):259-295.
[33].Li W,Delicato F C,Zomaya A Y.Adaptive Energy-efficient Scheduling for Hierarchical Wireless Sensor Networks[J].ACM Transactions on Sensor Networks(S1550-4859),2013,9(3):1-34.
[34].Dietrich I,Dressler F.On the Lifetime of Wireless Sensor Networks[J].ACM Transactions on Sensor Networks(S1550-4859),2009,5(1):1-39.
[35].Deng R,Lu R,Lai C,et al.Optimal Workload Allocation in Fog-cloud Computing Towards Balanced Delay and Power Consumption[J].IEEE Internet of Things Journal(S2327-4662),2016,1(1):1-1.
[36].Wan J,Chen B,Wang S,et al.Fog Computing for Energy-aware Load Balancing and Scheduling in Smart Factory[J].IEEE Transactions on Industrial Informatics(S1551-3203),2018,14(10):4548-4556.
[37].Gu L,Zeng D,Guo S,et al.Cost Efficient Resource Management in Fog Computing Supported Medical Cyber-Physical System[J].IEEE Transactions on Emerging Topics in Computing(S2168-6750),2017,5(1):108-119.
[38].Sturzinger E,Tornatore M,Mukherjee B.Application-aware Resource Provisioning in a Heterogeneous Internet of Things[C]//International Conference on Optical Network Design and Modeling.Budapest:IEEE,2017:1-6.
[39].Kumar K,Liu J,Lu Y H,et al.A Survey of Computation Offloading for Mobile Systems[J].Mobile Networks and Applications(S1383-469X),2013,18(1):129-140.
[40].Aazam M,Zeadally S,Harras K A.Offloading in Fog Computing for IoT:Review,Enabling Technologies,and Research Opportunities[J].Future Generation Computer Systems(S0167-739X),2018,87(1):278-289.
[41].Fricker C,Guillemin F,Robert P,et al.Analysis of an Offloading Scheme for Data Centers in the Framework of Fog Computing[J].ACM Transactions on Modeling and Performance Evaluation of Computing Systems(S2376-3639),2016,1(4):16-34.
[42].Wang X,Ning Z,Wang L.Offloading in Internet of Vehicles:A Fog-enabled Real-time Traffic Management System[J].IEEE Transactions on Industrial Informatics(S1551-3203),2018,14(10):4568-4578.
[43].Zhao X,Zhao L,Liang K.An Energy Consumption Oriented Offloading Algorithm for Fog Computing[C]//12th International Conference on Heterogeneous Networking for Quality,Reliability,Security and Robustness.Cham:Springer,2016:293-301.
[44].Xiao Y,Krunz M.QoE and Power Efficiency Tradeoff for Fog Computing Networks with Fog Node Cooperation[C]//IEEE Conference on Computer Communications.Atlanta,USA:IEEE,2017:1-9.
[45].Kattepur A,Dohare H,Mushunuri V,et al.Resource Constrained Offloading in Fog Computing[C]//1st Workshop on Middleware for Edge Clouds&Cloudlets.Trento,Italy:ACM,2016:1-6.
[46].Pisinger D.Where Are the Hard Knapsack Problems[J].Computers&Operations Research(S1873-765X),2005,32(9):2271-2284.
[47].Skarlat O,Nardelli M,Schulte S,et al.Towards QoS-aware Fog Service Placement[C]//1st International Conference on Fog and Edge Computing.Madrid,Spain:IEEE,2017:89-96.
[48].Zeng D,Gu L,Guo S,et al.Joint Optimization of Task Scheduling and Image Placement in Fog Computing Supported Software-Defined Embedded System[J].IEEE Transactions on Computers(S0018-9340),2016,65(12):3702-3712.
[49].Mennes R,Spinnewyn B,Latre S,et al.GRECO:A Distributed Genetic Algorithm for Reliable Application Placement in Hybrid Clouds[C]//5thInternational Conference on Cloud Networking.Pisa,Italy:IEEE,2016:14-20.
[50].Rahbari D,Nickray M.Scheduling of Fog Networks with Optimized Knapsack by Symbiotic Organisms Search[C]//21stConference of Open Innovations Association.Helsinki:IEEE,2017:278-283.
[51].Tang Z,Zhou X,Zhang F,et al.Migration Modeling and Learning Algorithms for Containers in Fog Computing[J].IEEE Transactions on Services Computing(S1939-1374),2019,12(5):712-725.
[52].Kwok Y,Ahmad I.Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessors[J].ACM Computing Surveys(S1557-7341),1999,31(4):406-471.
[53].Kao Y,Krishnamachari B.Optimizing Mobile Computational Offloading with Delay Constraints[C]//IEEE Global Communications Conference.TX,Austin:IEEE,2014:2289-2294.
[54].Sundar S,Liang B.Offloading Dependent Tasks with Communication Delay and Deadline Constraint[C]//IEEE Conference on Computer Communications.Honolulu,HI:IEEE,2018:37-45.
[55].Mahmoodi S E,Uma R N,Subbalakshmi K P.Optimal Joint Scheduling and Cloud Offloading for Mobile Applications[J].IEEE Transactions on Cloud Computing(S2168-7161),2019,7(2):301-313.
[56].Selvi S,Manimegalai D.DAG Scheduling in Heterogeneous Computing and Grid Environments Using Variable Neighborhood Search Algorithm[J].Applied Artificial Intelligence(S0883-9514),2017,31(2):134-173.
[57].Topcuoglu H,Hariri S,Min-You Wu.Performance-effective and Low-complexity Task Scheduling for Heterogeneous Computing[J].IEEE Transactions on Parallel&Distributed Systems(S1045-9219),2002,13(3):260-274.
[58].Liou J,Palis M A.A Comparison of General Approaches to Multiprocessor Scheduling[C]//11th International Parallel Processing Symposium.Switzerland:IEEE,1997:152-156.
[59].Xu Y,Li K,He L,et al.A DAG Scheduling Scheme on Heterogeneous Computing Systems Using Double Molecular Structure-Based Chemical Reaction Optimization[J].Journal of Parallel and Distributed Computing(S0743-7315),2013,73(9):1306-1322.
[60].Pham X Q,Huh E N.Towards Task Scheduling in a Cloud-fog Computing System[C]//18th Asia-Pacific Network Operations and Management Symposium.Kanazawa,Japan:IEEE,2016:1-4.
[61].Stavrinides G L,Karatza H D.A Hybrid Approach to Scheduling Real-time IoT Workflows in Fog and Cloud Environments[J].Multimedia Tools and Applications(S1380-7501),2019,78(17):24639-24655.
[62].Skarlat O,Nardelli M,Schulte S,et al.Optimized IoT Service Placement in the Fog[J].Service Oriented Computing and Applications(S1863-2386),2017,11(4):427-443.
[63].Xie Y,Zhu Y,Wang Y,et al.A Novel Directional and Non-local-convergent Particle Swarm Optimization based Workflow Scheduling in Cloud-edge Environment[J].Future Generation Computer Systems(S0167-739X),2019,97(1):361-378.
[64].趙梓銘,劉芳,蔡志平,等.邊緣計(jì)算:平臺(tái)、應(yīng)用與挑戰(zhàn)[J],計(jì)算機(jī)研究與發(fā)展,2018,55(2):327-337.
Zhao Ziming,Liu Fang,Cai Zhiping,et al.Edge Computing:Platforms,Applications and Challenges[J].Journal of Computer Research and Development,2018,55(2):327-337.
[65].Sonmez C,Ozgovde A,Ersoy C,et al.EdgeCloudSim:An Environment for Performance Evaluation of Edge Computing Systems[J].Transactions on Emerging Telecommunications Technologies(S2161-3915),2018,29(11):1-1.
[66].Gupta H,Dastjerdi A V,Ghosh S K,et al.iFogSim:A Toolkit for Modeling and Simulation of Resource Management Techniques in the Internet of Things,Edge and Fog computing environments[J].Software-Practice and Experience(S0038-0644),2017,47(9):1275-1296.
[67].Jonathan M,Nan W,Ashish T,et al.DeFog:fog Computing Benchmarks[C]//Proc 4th ACM/IEEE Symposium on Edge Computing.New York,USA:ACM Press,2019:47-58.
[68].Sharma S,Saini H.A Novel Four-tier Architecture for Delay Aware Scheduling and Load Balancing in Fog Environment[J].Sustainable Computing:Informatics and Systems(S2210-5379),2019,1(1):1-8.
[69].Xia C,Li W,Chang X,et al.Edge-based Energy Management for Smart Homes[C]//16th Dependable,Autonomic and Secure Computing.Athens,Greece:IEEE,2018:849-856.
[70].翟巖龍,孫文心,包天虹,等.基于微服務(wù)的邊緣側(cè)仿真方法及框架研究[J].系統(tǒng)仿真學(xué)報(bào),2018,30(12):44-53.
Zhai Yanlong,Sun Wenxin,Bao Tianhong,et al.Edge-side Simulation Method and Framework Based on Micro-services[J].Journal of System Simulation,2018,30(12):44-53.
作者簡(jiǎn)介：
王凌清華大學(xué)自動(dòng)化系長(zhǎng)聘教授、博士生導(dǎo)師、學(xué)位委員會(huì)副主席，國(guó)家杰出青年科學(xué)基金獲得者。中國(guó)仿真學(xué)會(huì)理事，中國(guó)仿真學(xué)會(huì)智能仿真優(yōu)化與調(diào)度專委會(huì)副主任；中國(guó)人工智能學(xué)會(huì)自然計(jì)算與數(shù)字智能城市專委會(huì)副主任；國(guó)際期刊IJAAC主編、CSMS執(zhí)行主編；IEEE TEVC、SEC、ESWA等SCI期刊副主編；控制理論與應(yīng)用、控制與決策、系統(tǒng)工程與電子技術(shù)等期刊編委。
長(zhǎng)期從事復(fù)雜系統(tǒng)建?？刂婆c優(yōu)化調(diào)度的研究與應(yīng)用，主持國(guó)家杰出青年科學(xué)基金及面上項(xiàng)目、國(guó)家重點(diǎn)研發(fā)計(jì)劃課題等20余項(xiàng)；已出版專著5部、譯著1部，在IEEE Trans等刊物上發(fā)表SCI論文200余篇、WOS引用一萬(wàn)余次、Google Scholar引用兩萬(wàn)余次；獲國(guó)家自然科學(xué)二等獎(jiǎng)1項(xiàng)；省部級(jí)科技獎(jiǎng)勵(lì)6項(xiàng)；自動(dòng)化學(xué)報(bào)、控制理論與應(yīng)用、控制與決策等期刊優(yōu)秀論文獎(jiǎng)。獲國(guó)家杰出青年科學(xué)基金、北京市科技新星、教育部新世紀(jì)優(yōu)秀人才、清華大學(xué)學(xué)術(shù)新人獎(jiǎng)、中國(guó)自動(dòng)化學(xué)會(huì)青年科學(xué)家獎(jiǎng)、中國(guó)高被引作者等。
