多層次算力網(wǎng)絡(luò)集中式不可分割任務(wù)調(diào)度算法

鞏宸宇 舒洪峰 張昕

摘要：根據(jù)算力網(wǎng)絡(luò)不同層次的特性和各種應(yīng)用的不同需求，提出一種多層次算力網(wǎng)絡(luò)模型和計(jì)算卸載系統(tǒng)，并定義一個由時延、能耗組成的加權(quán)代價函數(shù)以建模一個任務(wù)調(diào)度問題。為解決這一問題，提出一個基于交叉熵的集中式不可分割任務(wù)調(diào)度（CUTS）算法。數(shù)值仿真結(jié)果表明，與其他基線算法相比，該算法在系統(tǒng)平均代價方面擁有較好的性能。

關(guān)鍵詞：多層次算力網(wǎng)絡(luò)；交叉熵；集中式；任務(wù)調(diào)度；不可分割

Abstract： According to the characteristics of different layers of computing power network and different requirements of various applications， a multi-tier computing power network model and computation offloading system are proposed. Specifically， a cost function consisting of latency and energy consumption to model a task scheduling problem is defined. To solve the problem， a centralized unsplittable task scheduling （CUTS） algorithm based on cross-entropy is introduced. Simulation results show that the algorithm provides superior performance in terms of the average system cost compared with other baseline solutions. Keywords： multi-tier computing power network； cross-entropy； centralized； task scheduling； unsplittable

近年來，隨著深度學(xué)習(xí)的不斷發(fā)展，人工智能服務(wù)和應(yīng)用大量涌現(xiàn)，比如人臉識別、自然語言處理、虛擬現(xiàn)實(shí)、增強(qiáng)現(xiàn)實(shí)等。這些應(yīng)用通常都是計(jì)算密集型任務(wù)，將消耗大量的終端資源（如算力和能耗）。然而，由于計(jì)算能力和能量供應(yīng)有限，終端設(shè)備（例如手機(jī)）可能無法提供良好的服務(wù)質(zhì)量。為此，研究者們提出云計(jì)算的概念。

云計(jì)算[1-2]是由分布式計(jì)算、并行處理、網(wǎng)格計(jì)算發(fā)展而來的新型計(jì)算模型。通過虛擬化技術(shù)建立強(qiáng)大的資源池，云計(jì)算使各種應(yīng)用和服務(wù)能夠按需獲取算力、存儲資源及各種軟件資源。云計(jì)算為海量數(shù)據(jù)的處理提供了可能，同時也為計(jì)算密集型的人工智能應(yīng)用提供了強(qiáng)大的算力。然而，端與云之間的傳輸時延使得云計(jì)算無法滿足時延敏感型應(yīng)用的需求。因此，霧計(jì)算和邊緣計(jì)算[3-4]的概念被提出，以解決云計(jì)算傳播時延大的問題。

邊緣計(jì)算是指，在靠近物或者數(shù)據(jù)源頭的一側(cè)部署設(shè)備，提供計(jì)算、存儲等軟件服務(wù)，并通過算力和通信資源的聯(lián)合分配，滿足應(yīng)用的時延需求。經(jīng)典的邊緣計(jì)算網(wǎng)絡(luò)由霧節(jié)點(diǎn)和本地用戶共同組成。其中，本地用戶通過任務(wù)拆分和任務(wù)卸載決策，來達(dá)到全局時延和能耗最小的最優(yōu)效果。此前，學(xué)者們的研究主要集中在單用戶多節(jié)點(diǎn)[5-6]和多用戶單節(jié)點(diǎn)[7-8]。文獻(xiàn)[9]研究了多用戶多節(jié)點(diǎn)這一應(yīng)用場景。研究表明，邊緣計(jì)算可以降低傳輸時延。但是對于一些對算力和時延都有較高要求的應(yīng)用來說，邊緣計(jì)算網(wǎng)絡(luò)將不再適用，比如自動駕駛、虛擬現(xiàn)實(shí)等。因此，算力網(wǎng)絡(luò)[10]的概念被提出。

算力網(wǎng)絡(luò)涉及云計(jì)算、霧計(jì)算、邊緣計(jì)算等。算力網(wǎng)絡(luò)是由云邊端等設(shè)備構(gòu)成的多層次資源網(wǎng)絡(luò)，它能夠?qū)⒃七叾诉M(jìn)行統(tǒng)一調(diào)配，但是如何實(shí)現(xiàn)系統(tǒng)的最優(yōu)性能仍是一個難題。原因主要有兩點(diǎn)：（1）云邊端各有其特性。云距離端較遠(yuǎn)但算力強(qiáng)，多用于處理全局任務(wù)；邊距離端較近但算力弱，多處理本地實(shí)時任務(wù)。（2）用戶任務(wù)的需求不同。計(jì)算密集型任務(wù)可能更多地需要云的參與，時延敏感型任務(wù)可能更多地需要邊的參與，對算力和時延同時有較高要求的任務(wù)則需要聯(lián)合進(jìn)行調(diào)度?；谝陨显?，文獻(xiàn)[11]研究了多層次算力網(wǎng)絡(luò)，并提出一種分布式調(diào)度算法。但是該模型是邊端混合的兩層算力網(wǎng)絡(luò)，并未考慮云的作用。

試想存在如下場景：一座辦公大樓內(nèi)有多個樓層，每層都有多間辦公室，且每間辦公室都有多個用戶和不同性質(zhì)的任務(wù)。由于職能劃分不同，不同部門通常所需要的算力不盡相同。這就容易造成算力資源的不合理利用，甚至造成任務(wù)中斷。如果我們按照辦公室和樓層的位置，將其構(gòu)造成一個多層次算力網(wǎng)絡(luò)，進(jìn)行任務(wù)的調(diào)度和算力分配，那么就能夠更好地滿足計(jì)算密集型和時延敏感型應(yīng)用的需求。

1計(jì)算卸載系統(tǒng)建模

1.1系統(tǒng)概述

本節(jié)將詳細(xì)介紹一個多層次算力網(wǎng)絡(luò)和計(jì)算卸載系統(tǒng)，定義一個由時延、能耗組成的加權(quán)代價函數(shù)，并建模一個任務(wù)調(diào)度問題。

算力網(wǎng)絡(luò)一共有多層。第1層為用戶節(jié)點(diǎn)，其他層為霧節(jié)點(diǎn)。霧節(jié)點(diǎn)的算力隨層數(shù)的增加而上升。通常，距離用戶較遠(yuǎn)的高層霧節(jié)點(diǎn)算力比較強(qiáng)大，但是往返時延較長；距離用戶較近的低層霧節(jié)點(diǎn)往返時延較短，但是算力有限。在考慮時延和能耗的基礎(chǔ)上，用戶可以將不可拆分的任務(wù)卸載到某層的某個霧節(jié)點(diǎn)，也可以選擇將任務(wù)在本地執(zhí)行。因此，如何根據(jù)時延和能耗幫助用戶做出卸載決策，是解決任務(wù)調(diào)度問題并獲取全局最優(yōu)解的核心。

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

3.1仿真設(shè)置

我們假設(shè)存在這樣一個多層次算力網(wǎng)絡(luò)（參數(shù)設(shè)置如表1所示）。該網(wǎng)絡(luò)為3層算力網(wǎng)絡(luò)：第1層有多個用戶，第2層有10個霧節(jié)點(diǎn)，第3層有1個霧節(jié)點(diǎn)。用戶的任務(wù)不可拆分。用戶先將任務(wù)卸載到第2層霧節(jié)點(diǎn)，其他層的霧節(jié)點(diǎn)之間通過有線進(jìn)行連接。假設(shè)霧節(jié)點(diǎn)的初始狀態(tài)都為無其他任務(wù)在運(yùn)行。

與CUTS算法相對比的幾種基準(zhǔn)方法為：

（1）本地計(jì)算：每個用戶都在本地運(yùn)行任務(wù)；

（2）云計(jì)算：每個用戶都將任務(wù)卸載到云端；

（3）隨機(jī)卸載：每個用戶做出的卸載決策是隨機(jī)的。

本文以下仿真結(jié)果均為400次仿真結(jié)果的平均值。

3.2系統(tǒng)平均代價

如圖2所示，隨著用戶數(shù)的變化，CUTS算法總是能夠取得最優(yōu)的系統(tǒng)平均代價。本地計(jì)算通信時延較小，然而總代價卻高于多層算力網(wǎng)絡(luò)，這說明引入算力網(wǎng)絡(luò)有效解決了本地計(jì)算算力較小的問題。圖3展示了當(dāng)用戶的任務(wù)性質(zhì)不同時，不同算法的效果。當(dāng)α值較大時，任務(wù)性質(zhì)偏向時延敏感型。因?yàn)樵贫司嚯x用戶較遠(yuǎn)，通常具有比較大的時延，從圖3中我們可以看出，引入多層算力網(wǎng)絡(luò)可以有效解決云計(jì)算網(wǎng)絡(luò)存在的延遲大的問題。

3.3受益用戶數(shù)

圖4展示了在不同算法下的受益用戶數(shù)。受益用戶是指，在當(dāng)前卸載策略下降低自身處理任務(wù)代價的用戶。除隨即卸載算法外，其他算法的受益用戶數(shù)都與總用戶數(shù)呈正相關(guān)。由圖4可知，CUTS算法依然表現(xiàn)出最優(yōu)性能。

3.4時延及能耗成本分布

圖5展示了隨著用戶數(shù)目的增加，時延和能耗的對比情況?？梢钥闯觯S著總用戶數(shù)的增加，總的代價也在增加，但是增加幅度在減緩。此外，時延產(chǎn)生的代價要略高于能耗產(chǎn)生的代價。

3.5本地計(jì)算、霧計(jì)算和云計(jì)算用戶分布

圖6展示了隨著用戶數(shù)增加，各用戶的卸載決策分布。可以看出，選擇本地用戶和云計(jì)算的用戶數(shù)目逐漸增多，而選擇霧節(jié)點(diǎn)的用戶數(shù)卻幾乎不變。這是因?yàn)殪F節(jié)點(diǎn)的算力資源接近飽和。

4結(jié)束語

本文中，我們提出一種多層次算力網(wǎng)絡(luò)模型和計(jì)算卸載系統(tǒng)，定義一個由時延、能耗組成的加權(quán)代價函數(shù)，并建模一個任務(wù)調(diào)度問題。為解決這一問題，我們提出CUTS算法，即將一個確定性問題轉(zhuǎn)化成了一個估計(jì)問題，通過重要性采樣和交叉熵的方法來求解問題的最優(yōu)解。數(shù)值仿真結(jié)果表明，CUTS算法能夠在系統(tǒng)平均代價和受益用戶數(shù)方面提供最優(yōu)性能。算力網(wǎng)絡(luò)可以有效解決單層網(wǎng)絡(luò)帶來的算力小或時延大的問題。

致謝

本研究得到上海科技大學(xué)楊旸老師、吳連濤老師的幫助，謹(jǐn)致謝意！

參考文獻(xiàn)

[1] REN J K， HE Y H， YU G D， et al. Joint communication and computation resource allocation for cloud-edge collaborative system [C]// 2019 IEEE Wireless Communications and Networking Conference （WCNC）. Marrakesh， Morocco： IEEE， 2019： 1-6. DOI： 10.1109/ WCNC.2019.8885877

[2] MOURADIAN C， NABOULSI D， YANGUI S M， et al. A comprehensive survey on fog computing： state-of-the-art and research challenges [J]. IEEE communications surveys & tutorials， 2018， 20（1）： 416-464. DOI： 10.1109/ COMST.2017.2771153

[3] LIU Z N， YANG Y， CHEN Y， et al. A multi-tier cost model for effective user scheduling in fog computing networks [C]//IEEE INFOCOM 2019 - IEEE Conference on Computer CommunicationsWorkshops（INFOCOMWKSHPS）. Paris， France： IEEE， 2019： 1-6. DOI： 10.1109/INFCOMW.2019.8845252

[4] MAO Y Y， YOU C S， ZHANG J， et al. A survey on mobile edge computing： the communication perspective [J]. IEEE communications surveys & tutorials， 2017， 19（4）： 2322-2358. DOI： 10.1109/COMST.2017.2745201

[5] YANG Y， WANG K L， ZHANG G W， et al. MEETS： maximal energy efficient task scheduling in homogeneous fog networks [J]. IEEE Internet of Things journal， 2018， 5（5）： 4076-4087. DOI： 10.1109/JIOT.2018.2846644

[6] DINH T Q， TANG J H， LA Q D， et al. Offloading in mobile edge computing： task allocation and computational frequency scaling[J]. IEEE transactions on communications， 2017，65（8）：3571-3584.DOI： 10.1109/ TCOMM.2017.2699660

[7] CHEN X， JIAO L， LI W Z， et al. Efficient multiuser computation offloading for mobile-edge cloud computing [J]. IEEE/ACM transactions on networking， 2016， 24（5）： 2795-2808. DOI： 10.1109/TNET.2015.2487344

[8] NOWAK D， MAHN T， AL-SHATRI H， et al. A generalized Nash game for mobile edge computation offloading [C]//2018 6th IEEE International Conference on Mobile Cloud Computing， Services， and Engineering （MobileCloud）. Bamberg， Germany： IEEE， 2018： 95-102. DOI： 10.1109/MobileCloud.2018.00022

[9] YANG Y， LIU Z N， YANG X M， et al. POMT： paired offloading of multiple tasks in heterogeneous fog networks [J]. IEEE Internet of Things journal， 2019， 6（5）： 8658-8669. DOI： 10.1109/JIOT.2019.2922324

[10] YANG Y. Multi-tier computing networks for intelligent IoT [J]. Nature electronics， 2019， 2（1）： 4-5. DOI： 10.1038/s41928-018-0195-9

[11] LIU Z N， YANG Y， ZHOU M T， et al. A unified cross-entropy based task scheduling algorithm for heterogeneous fog networks[C]//Proceedings of the 1st ACM International Workshop on Smart Cities and Fog Computing. New York， NY， USA： ACM， 2018： 1-6. DOI： 10.1145/3277893.3277896

[12] SHAH-MANSOURI H， WONG V W S. Hierarchical fog-cloud computing for IoT systems： a computation offloading game [J]. IEEE Internet of Things journal， 2018， 5（4）： 3246-3257. DOI： 10.1109/JIOT.2018.2838022

作者簡介

鞏宸宇，上?？萍即髮W(xué)信息與技術(shù)學(xué)院在讀碩士研究生；研究領(lǐng)域主要包括物聯(lián)網(wǎng)與無線通信、霧計(jì)算等。

舒洪峰，深圳市智慧城市科技發(fā)展集團(tuán)有限公司副總經(jīng)理，曾擔(dān)任深圳市鹽田港集團(tuán)有限公司辦公室副主任，深圳市特區(qū)建設(shè)發(fā)展集團(tuán)有限公司辦公室主任、董事會秘書；主要研究領(lǐng)域包括大數(shù)據(jù)與云計(jì)算、5 G及城域物聯(lián)專網(wǎng)、數(shù)字經(jīng)濟(jì)等。

張昕，教授級高級工程師，深圳市智慧城市科技發(fā)展集團(tuán)有限公司解決方案部部長，深圳市智能交通標(biāo)準(zhǔn)化技術(shù)委員會委員、深圳市政府采購中心資深專家、深圳市后備級領(lǐng)軍人才；從事智慧城市、智能交通等政府信息化工作，主持并完成綜合交通運(yùn)行指揮中心、智慧寶安總體規(guī)劃、路邊停車系統(tǒng)、僑香路智慧道路、智慧國資管理展示中心及智慧國資大數(shù)據(jù)中心等項(xiàng)目；獲華夏建設(shè)科學(xué)技術(shù)獎一等獎、中國智能交通協(xié)會一等獎、深圳市科技創(chuàng)新獎等省部級獎勵（7項(xiàng)）；發(fā)表論文與專著2 0余篇，申請發(fā)明專利3項(xiàng)，參與編制深圳市地方標(biāo)準(zhǔn)9項(xiàng)。