論文標(biāo)題：Revenue-Optimal Task Scheduling and Resource Management for IoT Batch Jobs in Mobile Edge Computing

錄用期刊：Peer-to-Peer Networking and Applications (SCI，JCR Q2，CCF C類(lèi))

作者列表：

1）黃霽崴 中國(guó)石油大學(xué)（北京） 信息科學(xué)與工程學(xué)院 教授

2）李松遠(yuǎn) 北京郵電大學(xué) 網(wǎng)絡(luò)與交換技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室 2018級(jí)碩士

3）陳   瑩 北京信息科技大學(xué) 計(jì)算機(jī)學(xué)院 副教授

原文DOI:  https://doi.org/10.1007/s12083-020-00880-y

基于邊緣計(jì)算架構(gòu)的QoS感知任務(wù)調(diào)度和資源管理方法

QoS感知的任務(wù)調(diào)度和資源管理方法針對(duì)移動(dòng)邊緣計(jì)算架構(gòu)設(shè)計(jì)，如上圖所示。邊緣服務(wù)供應(yīng)商將多個(gè)邊緣服務(wù)器部署在各處基站的位置，基站負(fù)責(zé)和用戶(hù)維持?jǐn)?shù)據(jù)通信和任務(wù)交互，用戶(hù)提交的任務(wù)請(qǐng)求在邊緣服務(wù)器端處理。用戶(hù)的任務(wù)請(qǐng)求通常被調(diào)度到鄰近的邊緣服務(wù)器，所以相較于將任務(wù)調(diào)度到遠(yuǎn)程云端，大幅減少了任務(wù)響應(yīng)時(shí)間和任務(wù)傳輸帶寬。在用戶(hù)分布密度較大的區(qū)域（如城市中央商務(wù)區(qū)），與用戶(hù)鄰近的邊緣服務(wù)器會(huì)有多個(gè)。本部分充分考慮如上情況的任務(wù)調(diào)度策略。同時(shí)，一個(gè)邊緣服務(wù)器在相應(yīng)基站的信號(hào)覆蓋范圍內(nèi)通常被多個(gè)用戶(hù)共享，而多個(gè)用戶(hù)間達(dá)成對(duì)邊緣服務(wù)器的資源競(jìng)爭(zhēng)關(guān)系。用戶(hù)在邊緣服務(wù)器內(nèi)分配得到更多計(jì)算資源，意味著更快的任務(wù)處理速度，即更高的QoS。因此，本部分也同時(shí)關(guān)注邊緣服務(wù)器內(nèi)的資源管理問(wèn)題。

本部分的任務(wù)調(diào)度和資源管理充分了時(shí)間動(dòng)態(tài)性，用戶(hù)跨邊緣基站的信號(hào)覆蓋范圍操作位置移動(dòng)。任務(wù)調(diào)度和資源管理算法，在不同的時(shí)間槽下，根據(jù)當(dāng)前各用戶(hù)位置和邊緣服務(wù)器計(jì)算資源使用情況，做出任務(wù)調(diào)度和資源管理的決策。決策結(jié)果滿(mǎn)足多用戶(hù)的QoS需求，并且最大化邊緣供應(yīng)商的總服務(wù)收益，維護(hù)邊緣服務(wù)生態(tài)的可持續(xù)性發(fā)展。

具體地說(shuō)，首先，建立關(guān)于移動(dòng)邊服務(wù)動(dòng)態(tài)過(guò)程的數(shù)學(xué)模型，給出QoS指標(biāo)（即任務(wù)響應(yīng)時(shí)間）的計(jì)算解析式。其次，基于模型描述，設(shè)計(jì)最大化邊緣服務(wù)供應(yīng)商收益的優(yōu)化模型，并以用戶(hù)QoS需求作為優(yōu)化模型的約束條件。然后，針對(duì)優(yōu)化模型，設(shè)計(jì)高效的調(diào)度算法，分析算法時(shí)間復(fù)雜度。最后，基于邊緣計(jì)算數(shù)據(jù)集，設(shè)計(jì)仿真實(shí)驗(yàn)，驗(yàn)證調(diào)度算法的有效性和高效性。

基于移動(dòng)邊緣架構(gòu)的QoS感知任務(wù)調(diào)度和資源管理方法

1. 最大化邊緣供應(yīng)商收益的任務(wù)/資源優(yōu)化模型

用戶(hù)發(fā)起的任務(wù)請(qǐng)求允許跨邊緣端地調(diào)度到多個(gè)邊緣服務(wù)器。αi,j(t)表示于時(shí)間槽t分配給用戶(hù)i的任務(wù)請(qǐng)求的、位于邊緣服務(wù)器j的資源實(shí)例數(shù)量。任務(wù)/資源的優(yōu)化決策在每個(gè)決策時(shí)間槽Γ執(zhí)行。優(yōu)化目標(biāo)是最大化邊緣供應(yīng)商收益，收益來(lái)自各用戶(hù)上報(bào)的服務(wù)預(yù)算Bi。任務(wù)/資源優(yōu)化模型的形式化定義如下圖所示，資源約束表示在每個(gè)時(shí)間槽t向所有用戶(hù)分配的總資源數(shù)量不超過(guò)資源容量，而QoS約束表示對(duì)任務(wù)請(qǐng)求i的調(diào)度和資源決策僅在任務(wù)執(zhí)行期限前操作。

任務(wù)/資源優(yōu)化模型

2. 基于線(xiàn)性規(guī)劃的任務(wù)/資源決策模型

上圖定義的優(yōu)化模型是整數(shù)規(guī)劃（Integer Programming, IP）問(wèn)題，屬于NP難題。 因此，借助優(yōu)化約束式的完全幺模性質(zhì)，利用λ-優(yōu)化求解技術(shù)，上圖的整數(shù)規(guī)劃問(wèn)題可以通過(guò)線(xiàn)性規(guī)劃技術(shù)等效地求解。線(xiàn)性規(guī)劃問(wèn)題可以使用高效算法（如單純形算法，內(nèi)點(diǎn)法）和求解器（如MOSEK，CPLEX）求解?；诰€(xiàn)性規(guī)劃的決策優(yōu)化模型如下圖所示。

線(xiàn)性規(guī)劃決策模型

3. 跨邊緣端的動(dòng)態(tài)任務(wù)調(diào)度和資源管理算法

下圖算法敘述了跨邊緣端的任務(wù)調(diào)度和資源管理算法，實(shí)現(xiàn)了邊緣供應(yīng)商收益的最大化。當(dāng)為用戶(hù)的服務(wù)請(qǐng)求提供調(diào)度決策時(shí)，同時(shí)確定分配的邊緣資源數(shù)量。對(duì)任務(wù)調(diào)度和資源管理的決策沿著決策時(shí)間槽Γ動(dòng)態(tài)執(zhí)行；在每一決策時(shí)間槽Γ，更新各移動(dòng)用戶(hù)的位置信息，收集新提出的任務(wù)請(qǐng)求，并依此操作決策。

任務(wù)調(diào)度和資源管理算法

實(shí)驗(yàn)結(jié)果

邊緣供應(yīng)商在不同算法下的服務(wù)收益

移動(dòng)物聯(lián)網(wǎng)設(shè)備在不同算法下的任務(wù)完成率

不同移動(dòng)IoT設(shè)備規(guī)模下邊緣供應(yīng)商的服務(wù)收益

不同系統(tǒng)規(guī)模下的算法運(yùn)行時(shí)(系統(tǒng)規(guī)模指，移動(dòng)IoT設(shè)備/邊緣服務(wù)器的數(shù)量)

經(jīng)過(guò)實(shí)驗(yàn)驗(yàn)證，我們算法的有效性和效率得到充分驗(yàn)證。

作者簡(jiǎn)介

黃霽崴 博士，教授，博士生導(dǎo)師，石油數(shù)據(jù)挖掘北京市重點(diǎn)實(shí)驗(yàn)室主任，中國(guó)石油大學(xué)（北京）計(jì)算機(jī)科學(xué)與技術(shù)系主任。2015年度北京市優(yōu)秀人才，2018年度中國(guó)石油大學(xué)（北京）優(yōu)秀青年學(xué)者，2020年度北京市科技新星。分別在2009年和2014年于清華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系獲得工學(xué)學(xué)士和工學(xué)博士學(xué)位，2012-2013年國(guó)家公派赴美國(guó)佐治亞理工學(xué)院聯(lián)合培養(yǎng)。研究方向包括：系統(tǒng)性能評(píng)價(jià)和優(yōu)化、隨機(jī)模型理論和應(yīng)用、服務(wù)質(zhì)量測(cè)量與保障技術(shù)、服務(wù)計(jì)算和物聯(lián)網(wǎng)等。擔(dān)任中國(guó)計(jì)算機(jī)學(xué)會(huì)（CCF）服務(wù)計(jì)算專(zhuān)委會(huì)委員，CCF高級(jí)會(huì)員，IEEE、ACM會(huì)員。已主持國(guó)家自然科學(xué)基金、北京市自然科學(xué)基金等科研項(xiàng)目13項(xiàng)，在國(guó)內(nèi)外著名期刊和會(huì)議發(fā)表論文五十余篇，出版學(xué)術(shù)專(zhuān)著1部，獲得國(guó)家發(fā)明專(zhuān)利5項(xiàng)、軟件著作權(quán)3項(xiàng)，擔(dān)任多個(gè)國(guó)際頂級(jí)期刊和知名會(huì)議審稿人。聯(lián)系郵箱：[email protected]。