鞏宸宇 舒洪峰 張昕

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

關鍵詞：多層次算力網(wǎng)絡；交叉熵；集中式；任務調(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

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

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

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

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

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

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

1.1系統(tǒng)概述

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

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

3實驗與結(jié)果

3.1仿真設置

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

與CUTS算法相對比的幾種基準方法為：

（1）本地計算：每個用戶都在本地運行任務；

（2）云計算：每個用戶都將任務卸載到云端；

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

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

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

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

3.3受益用戶數(shù)

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

3.4時延及能耗成本分布

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

3.5本地計算、霧計算和云計算用戶分布

圖6展示了隨著用戶數(shù)增加，各用戶的卸載決策分布?？梢钥闯?，選擇本地用戶和云計算的用戶數(shù)目逐漸增多，而選擇霧節(jié)點的用戶數(shù)卻幾乎不變。這是因為霧節(jié)點的算力資源接近飽和。

4結(jié)束語

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

致謝

本研究得到上?？萍即髮W楊旸老師、吳連濤老師的幫助，謹致謝意！

參考文獻

[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信息與技術學院在讀碩士研究生；研究領域主要包括物聯(lián)網(wǎng)與無線通信、霧計算等。

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

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