劉澤寧 李 凱 吳連濤 王 智 楊 旸1,,6

1(上?？萍即髮W信息科學與技術(shù)學院 上海 201210) 2(上?？萍即髮W創(chuàng)意與藝術(shù)學院 上海 201210) 3(浙江大學控制科學與工程學院 杭州 310027) 4(上海霧計算實驗室(上海科技大學) 上海 201210) 5(紫金山實驗室 南京 211111) 6(鵬城實驗室網(wǎng)絡通信研究中心 廣東深圳 518000) 7(工業(yè)控制技術(shù)國家重點實驗室(浙江大學) 杭州 310027)liuzy1@shanghaitech.edu.cn)

隨著越來越多數(shù)據(jù)的產(chǎn)生以及更加強大的算力算法的運用，物聯(lián)網(wǎng)應用也變得越來越智能.典型的物聯(lián)網(wǎng)應用也從簡單的數(shù)據(jù)感知、收集和表示轉(zhuǎn)向復雜的信息提取和分析.未來，物聯(lián)網(wǎng)可廣泛應用于環(huán)境監(jiān)測、城市管理、醫(yī)療健康等任務.這些任務往往需要實時的數(shù)據(jù)處理、信息提取和分析決策.但是，由于有限的通信帶寬、不穩(wěn)定的網(wǎng)絡連接以及嚴格的時延要求等，僅僅依靠云計算已無法支持無處不在且日漸強大的物聯(lián)網(wǎng)部署和應用.為應對這一挑戰(zhàn)，多層次算力網(wǎng)絡[1]被提了出來.

多層次算力網(wǎng)絡涉及云計算、霧計算[2]、邊緣計算[3]和海計算[4]等技術(shù)之間的相互協(xié)作.這些技術(shù)的特點和覆蓋范圍不同，可以分別針對區(qū)域級別、本地級別和設備級別的物聯(lián)網(wǎng)應用和服務.云計算位于最上層，遠離終端設備.其通常是集中式的，用于全局任務.邊緣計算靠近終端設備，其通常是分布式的，擅長處理本地的實時任務.霧計算位于云計算和邊緣計算中間，起到橋梁的作用，是管理多層資源的關鍵.終端設備在設備層面上形成了海計算的概念，以支持實時的數(shù)據(jù)感知、控制執(zhí)行等一些基本功能.因此，這樣一個多層次算力網(wǎng)絡可以顯著提升終端設備的服務質(zhì)量和用戶體驗，節(jié)省時延和能耗.

但是，在這樣一個多層次算力網(wǎng)絡下，如何有效地進行任務調(diào)度是個挑戰(zhàn).首先，云、霧、邊緣等計算技術(shù)特點各異、側(cè)重不同，如上所述.其次，不同終端設備、用戶、任務需求各異.有的對時延敏感，有的則更在意能耗.如何根據(jù)設備用戶任務的不同需求，將任務調(diào)度到不同特點和網(wǎng)絡層次的算力資源上，是一個巨大的挑戰(zhàn).這也是實現(xiàn)多層次算力網(wǎng)絡功效的一個重要方面.另外，如何考慮或設計激勵機制以激勵網(wǎng)絡各層次資源參與多層次算力網(wǎng)絡也是我們需要思考的問題，因為這是多層次算力網(wǎng)絡得以成形的前提.

為解決上述挑戰(zhàn)，本文提出了一個云霧混合多層次算力網(wǎng)絡及計算卸載系統(tǒng)，定義了一個由時延、能耗及付費組成的加權(quán)代價函數(shù)，并建模了一個代價感知任務調(diào)度(cost aware task scheduling, CATS)問題.而且，為激發(fā)云和霧的積極性，我們提出了一個基于計算量的付費模型并將付費相關代價也考慮進總代價.具體來說，根據(jù)云和霧的不同特性和需求，我們分別提出了一個靜態(tài)付費模型和動態(tài)付費模型，從而構(gòu)建了一個混合付費模型.為解決上述CATS問題，我們提出了一個基于勢博弈的分析框架，并設計了一個分布式任務調(diào)度算法——CATS算法.

本文的主要貢獻包括3個方面:

1) 提出了一個云霧混合多層次算力網(wǎng)絡及計算卸載系統(tǒng)，定義了一個由時延、能耗及付費組成的加權(quán)代價函數(shù)，并建模了一個代價感知任務調(diào)度問題——CATS問題.

2) 提出了一個基于計算量的付費模型以激勵云和霧參與到多層次算力網(wǎng)絡及服務架構(gòu)，并進一步根據(jù)云和霧的不同特性和需求分別設計了一個靜態(tài)付費模型和動態(tài)付費模型，從而構(gòu)建了一個混合付費模型.數(shù)值仿真結(jié)果表明，和靜態(tài)付費模型相比，動態(tài)付費模型可以幫助霧服務提供商在用戶數(shù)較大時獲得更多收入.

3) 提出了一個基于勢博弈的問題分析框架，并設計了一個分布式任務調(diào)度算法——CATS算法.數(shù)值仿真結(jié)果表明，和集中式最優(yōu)方法相比，CATS算法既可以取得近似最優(yōu)的系統(tǒng)平均代價，又可以讓更多用戶從任務卸載中受益，即CATS算法在系統(tǒng)整體及用戶個體2個維度上均具有優(yōu)秀表現(xiàn).

1 相關工作

關于任務調(diào)度或計算卸載的研究可追溯到傳統(tǒng)的云計算.文獻[5-6]針對云計算，給出了一個一般的計算卸載策略.

最近，多層次算力網(wǎng)絡中的任務調(diào)度或計算卸載的研究愈發(fā)得到人們關注[14-18].文獻[14-15]研究了以最小化時延為目標的任務調(diào)度問題，并分別提出了一個基于整數(shù)規(guī)劃的集中式任務調(diào)度算法和一個基于匹配理論的分布式任務調(diào)度算法.文獻[16]研究了以最小化功耗為目標的任務調(diào)度及資源分配問題.文獻[16]將問題分解為3個子問題，并分別通過內(nèi)點法、廣義彎曲算法及匈牙利算法求解.和文獻[9]類似，文獻[17]提出了一個新穎的基于D2D的混合計算卸載架構(gòu)，并設計了一個基于三層圖匹配的任務調(diào)度算法以解決該卸載框架下以最小化時延及能耗代價為目標的任務調(diào)度問題.文獻[18]則針對多用戶的物聯(lián)網(wǎng)場景，研究了以最小化時延及能耗代價為目標的任務調(diào)度問題，并利用博弈論設計了一個分布式方法.以上工作都沒有考慮霧邊緣節(jié)點及云的激勵問題.

另一方面，一些工作也關注到了計算卸載中的激勵機制問題[9,19-23].對于單層算力網(wǎng)絡而言，如果同一網(wǎng)絡層節(jié)點之間可以相互進行計算卸載，那么我們一般可以采用“tit-for-tat”的激勵機制，即貢獻資源多的個體相應也可以享受更多的資源[9,19].文獻[9,19]分別提出了一個基于D2D和同構(gòu)霧計算網(wǎng)絡的計算卸載框架.在文獻[9]和文獻[19]中，設備(或霧節(jié)點)與設備(或霧節(jié)點)之間可以相互共享通信資源及計算資源，從而相互進行計算任務的卸載.這樣一個可以相互共享資源的單層算力網(wǎng)絡類似于點對點(peer-to-peer)系統(tǒng)，因此一般可以采用“tit-for-tat”的激勵機制以激勵個體參與資源共享.如果是跨層或多層的算力網(wǎng)絡架構(gòu)，那么不同網(wǎng)絡層或?qū)嶓w之間可以通過付費的方式共享資源[20-23].文獻[20]中，用戶需向邊緣節(jié)點付費以使用其計算資源.文獻[21]中，網(wǎng)絡運營商可以租用霧節(jié)點服務終端用戶，并根據(jù)霧節(jié)點提供的計算資源及服務質(zhì)量付費.文獻[22]中，云服務運營商可以通過付費的方式將計算卸載到邊緣服務器上.文獻[23]中，用戶可以通過付費的方式向數(shù)據(jù)服務運營商訂閱服務，而數(shù)據(jù)服務運營商則可以通過付費的方式來利用邊緣霧節(jié)點的資源更好地服務終端用戶.

綜上所述，國內(nèi)外的研究人員針對多層次算力網(wǎng)絡中的任務調(diào)度或計算卸載問題已經(jīng)做了一些研究和探索，但其中很少有同時考慮云和霧或者邊緣的激勵問題的.大多數(shù)研究工作要么只集中于計算卸載過程中的任務調(diào)度或資源分配，要么主要研究激勵問題，且網(wǎng)絡場景多為單層或兩層算力網(wǎng)絡.與此同時，相較分布式算法，大多數(shù)工作在設計任務調(diào)度或者計算卸載算法時采用的是集中式算法.鑒于以上考慮，本文將提出一個云霧混合多層次算力網(wǎng)絡及計算卸載系統(tǒng)，定義一個由時延、能耗及付費組成的加權(quán)代價函數(shù)，建模一個代價感知任務調(diào)度(CATS)問題并相應地提出一個分布式任務調(diào)度算法.而且，為激發(fā)云和霧的積極性，我們將提出一個基于計算量的付費模型并將付費相關代價也考慮進總代價.具體來說，根據(jù)云和霧的不同特性和需求，我們將分別提出一個靜態(tài)付費模型和動態(tài)付費模型，從而構(gòu)建一個混合付費模型.

2 多層次算力網(wǎng)絡

在本節(jié)中，我們主要介紹多層次算力網(wǎng)絡的相關概念及特性.

如圖1所示，多層次算力網(wǎng)絡涉及云計算、霧計算、邊緣計算和海計算等技術(shù)之間的相互協(xié)作.這些技術(shù)的特點和覆蓋范圍不同，可以分別針對區(qū)域級別、本地級別和設備級別的物聯(lián)網(wǎng)任務和應用.云計算位于最上層，遠離終端設備，其通常是集中式的，用于全局任務.邊緣計算靠近終端設備，其通常是分布式的，擅長處理本地的實時任務.霧計算位于云計算和邊緣計算中間，起到橋梁的作用，是管理多層資源的關鍵.終端設備在設備層面上形成了海計算的概念，以支持實時的數(shù)據(jù)感知、控制執(zhí)行等一些基本功能.

這樣一個多層次算力網(wǎng)絡可以抽象為一個自上而下，具有多層組織的大公司結(jié)構(gòu)，如圖1所示.在一個公司中，各級管理者和員工通常擁有不同的資源和權(quán)限來訪問、處理、分配任務，發(fā)展客戶以及做出決策.云計算相當于公司的最高層：擁有最多的信息源、最強的分析能力、最大的存儲空間以及最高的決策權(quán).因此，云計算負責處理具有挑戰(zhàn)性的全局任務，如跨域的數(shù)據(jù)分析與處理、異常行為的診斷與跟蹤、隱藏問題的預測與搜索、新知識的發(fā)現(xiàn)與創(chuàng)造、長期戰(zhàn)略的規(guī)劃與決策等.另一方面，邊緣計算相當于一線員工，他們擁有的資源和權(quán)限最少，但可以與不同行業(yè)的客戶直接打交道.因此，邊緣計算擅長處理本地級別的時延敏感型任務，例如數(shù)據(jù)收集、數(shù)據(jù)壓縮、信息提取和事件監(jiān)視.霧計算位于云計算和邊緣計算中間，相當于公司的中層管理人員.和一個具有多層資源和職責的高效管理體系一樣，霧計算是多層次的結(jié)構(gòu)，每一層可以共享計算、通信、存儲等資源.由于用戶需求在時間上和空間上是動態(tài)變化的，因此霧計算可以提供一種靈活的方法，將網(wǎng)絡中分散在不同地理位置或邏輯位置的資源整合在一起，從而為任何客戶提供及時有效的服務.物聯(lián)網(wǎng)網(wǎng)絡中的設備或“物”相當于公司的客戶，它們對智能應用和服務有著不同的需求.盡管每個設備的處理、通信、存儲和電力資源有限，但它們在設備層面上形成了海計算的概念，以支持實時的數(shù)據(jù)感知、環(huán)境認知、移動控制和其他一些基本功能.

Fig. 2 An illustration of multi-tier computing network and computation offloading system with hybrid cloud and fog圖2 云霧混合多層次算力網(wǎng)絡及計算卸載系統(tǒng)

一個公司的成功離不開不同職級和部門之間有效的溝通和協(xié)作機制.同樣地，云計算、霧計算、邊緣計算和海計算之間的交互和協(xié)作對于構(gòu)建多層次算力網(wǎng)絡架構(gòu)至關重要.因此，該架構(gòu)應連接網(wǎng)絡中所有節(jié)點共享的計算、通信和存儲資源，充分利用它們在不同位置和層次的能力，并根據(jù)用戶的動態(tài)需求提供智能、及時、高效的服務.因此，這種多層次算力網(wǎng)絡可以顯著提高服務質(zhì)量和用戶體驗，同時節(jié)省時間、資源和成本.

但是應該指出的是，多層次算力網(wǎng)絡的發(fā)展和標準化才剛剛開始，還有許多技術(shù)挑戰(zhàn)有待解決.具體來說，在安全、信任和隱私方面，終端用戶應該在不犧牲個人數(shù)據(jù)的前提下，使用附近的共享計算節(jié)點.再者，需要開發(fā)資源虛擬化和資源可視化功能，以便在不同的機器和硬件上共享物理計算資源.此外，高效的業(yè)務流程，即異構(gòu)資源和服務的管理及分配，需要網(wǎng)絡節(jié)點之間的互相操作.最后，為服務多組用戶，即滿足多租戶需求，需要開發(fā)一種新的商業(yè)模式，并構(gòu)建生態(tài)系統(tǒng)以鼓勵共享資源和協(xié)作服務.這些問題的解決需要跨學科的研究和合作[1].

3 基于多層次算力網(wǎng)絡的計算卸載系統(tǒng)

3.1 系統(tǒng)概述

本節(jié)將詳細介紹一個云霧混合多層次算力網(wǎng)絡及計算卸載系統(tǒng)，定義一個由時延、能耗及付費組成的加權(quán)代價函數(shù)，并建模一個代價感知任務調(diào)度(CATS)問題.

如圖2所示，該云霧混合多層次算力網(wǎng)絡由多個邊緣霧節(jié)點(fog node, FN)和一個遠端的云組成，它們共同向終端用戶(user equipment，UE)提供云計算類服務.其中，云由云服務提供商運營，如亞馬遜、微軟、阿里巴巴，而邊緣霧節(jié)點由霧服務提供商管理，如電信運營商(電信運營商可以通過在已有基站或接入點附近安裝服務器的方式為用戶提供存儲、計算等云計算服務).在本文中，我們假設云由單個云服務提供商運營，而邊緣霧節(jié)點也由單個霧服務提供商管理.用戶可以通過付費的方式獲取云服務提供商或霧服務提供商所提供的服務.

用戶出于時延或能耗的考慮，可以將其計算任務卸載到霧節(jié)點或云上進行處理，這取決于二者提供的服務質(zhì)量，即任務卸載過程中的時延或和能耗，以及用戶為此支付的費用.一般來說，云擁有強大的計算能力，但遠離終端用戶，通過廣域網(wǎng)為終端用戶提供服務，通信時延較大；而霧節(jié)點靠近終端用戶，可以通過局域網(wǎng)為用戶提供服務，通信時延較小，但單個霧節(jié)點計算能力有限.用戶如何根據(jù)其自身不同的時延、能耗以及付費的考慮從而決定任務的處理位置是本文考慮的重點.

接下來，我們將分別介紹該多層次算力網(wǎng)絡及計算卸載系統(tǒng)下的通信模型、計算模型及付費模型，及其相關的時延、能耗及付費代價.

3.2 通信模型

由于霧節(jié)點靠近終端用戶，因此用戶可以通過局域網(wǎng)接入霧節(jié)點.我們用Rn,m表示，當用戶n獨占霧節(jié)點m的信道時，從用戶n到霧節(jié)點m的傳輸速率，其取決于物理層信號特征、發(fā)射功率、信道增益等.當多個用戶同時將計算任務卸載到霧節(jié)點m上時，因為單個霧節(jié)點的通信資源有限，所以不同用戶需要共享或競爭霧節(jié)點的通信資源.根據(jù)帶寬共享模型[24-25]，當多個用戶將計算任務卸載到霧節(jié)點m上時，用戶n到霧節(jié)點m的傳輸速率可以建模為

(1)

該模型廣泛運用于基于TDMA和OFDMA的MAC協(xié)議中帶寬共享的建模.因此，用戶n將任務卸載到霧節(jié)點m上的通信時延可表示為

(2)

這里，和大多數(shù)工作[7-9,12,18]一樣，我們忽略結(jié)果返回至用戶的過程，因為和任務本身大小相比，結(jié)果可以忽略不計.

相應地，用戶n將任務卸載到霧節(jié)點m上的能耗可表示為

(3)

(4)

(5)

3.3 計算模型

本地計算的時延可以表示為

(6)

其中,fn是用戶n的本地計算能力，即CPU的時鐘頻率(CPU轉(zhuǎn)數(shù)秒).

本地計算的能耗可以表示為[9-10,12,14,17-18]

(7)

其中,κn是與硬件結(jié)構(gòu)相關的常數(shù).

同樣地，當用戶將任務卸載到霧節(jié)點或云上時，霧節(jié)點或云的計算時延也可以表示成類似的形式.但因為單個霧節(jié)點的計算能力有限，所以當多個用戶將計算任務卸載到霧節(jié)點上時，不同用戶需要共享或競爭霧節(jié)點的計算能力.通常情況下，分配給單個用戶或任務的計算能力是用戶數(shù)的非增函數(shù).這里為了簡單起見，我們假設霧節(jié)點的計算能力被均勻分配給其上的任務[24-25].因此，用戶n將任務卸載到霧節(jié)點m上的計算時延可以表示為

(8)

其中,fm是霧節(jié)點m的計算能力.

而云因為計算能力通常充足，因此每個用戶可以被分配以一定的云計算能力fc.因此，用戶n將任務卸載到云上的計算時延可以表示為

(9)

3.4 付費模型

為補償霧節(jié)點和云在處理用戶計算任務過程中的開銷并激勵它們參與到用戶的任務卸載中來，霧節(jié)點和云會向用戶收取一定的費用，因此用戶會支付一筆費用給霧節(jié)點和云.這是最直接也最直觀的激勵方式[20-23].一般來說，任務的計算量越大，霧節(jié)點和云處理任務時的付出越多，如能耗，因此支付給霧節(jié)點和云的費用也應該越多.但是，對于霧節(jié)點而言，如果其服務的用戶數(shù)越多，單個用戶等待的時延及消耗的能耗越大.因此，用戶支付給霧節(jié)點的費用也應該減少，以彌補增加的時延及能耗代價.從霧節(jié)點角度理解，霧節(jié)點為了吸引更多的用戶使用自身的服務以增加潛在的收入，并且彌補因為服務用戶數(shù)的增加而導致的用戶服務質(zhì)量的下降，霧節(jié)點會給予用戶一定的價格優(yōu)惠.

我們將支付給霧節(jié)點m的費用建模為

Cn,m=cfog(1-α(nm(a)-1))znγn,

(10)

其中,cfog是一個常數(shù)，表示霧服務提供商對單位計算量的收費，為霧服務提供商對外統(tǒng)一報價;α∈(0,αmax]是折扣率.我們將上述付費模型稱作動態(tài)付費模型.

而支付給云的費用可相應建模為

Cn,c=ccloudznγn,

(11)

其中,ccloud是一個常數(shù)，表示云服務提供商對單位計算量的收費.我們將上述付費模型稱作靜態(tài)付費模型.

不同的建模方式也可以從云和霧各自特點的角度予以理解、解釋.云服務提供商一般都是大公司，且市場成熟，個體用戶對其議價能力弱，因此其付費模式較為固定；而霧服務提供商則更多為個人或者小公司，屬于新加入的市場玩家，用戶對其議價能力較強，因此其付費模式可以動態(tài)變化.霧服務提供商為從云服務提供商手中搶奪市場份額，以及不同霧服務提供商之間的相互競爭，其愿意采取一定的降價策略以吸引更多用戶，以增加最終收入.我們將在數(shù)值仿真部分來進一步分析這樣一個混合付費模型.

3.5 問題建模

我們將用戶的任務卸載代價建模成時延、能耗及付費的線性組合[9-12,16-17]，即定義了一個加權(quán)代價函數(shù).我們將時延、能耗及付費這些不同度量統(tǒng)一映射為同一量綱[21].

如果用戶n選擇在本地處理任務，其代價可以表示為

(12)

如果用戶n選擇將任務卸載到霧節(jié)點m上進行處理，其代價可以表示為

(13)

如果用戶n選擇將任務卸載到云上進行處理，其代價表示為

(14)

根據(jù)式(12)～(14)，在策略組合a下，用戶n的代價可以表示為

(15)

其中a-n=(a1,a2,…,an-1,an+1,…,aN),表示除了用戶n之外其他所有用戶的卸載策略，a=(an,a-n).

在我們的問題中，每個用戶需自主決定其卸載決策，以最小化自身代價.因此，我們可以將相應的任務調(diào)度問題建模為：

(16)

我們將式(16)所述問題稱作代價感知任務調(diào)度(CATS)問題.

因為用戶之間的目標彼此矛盾，卸載決策相互耦合，所以CATS問題難以解決.從式(16)可知，用戶的代價不僅取決于其自身的卸載策略，還取決于其他用戶的卸載策略.為解決上述難題，接下來我們將把上述問題重新建模為一個非合作博弈，進而通過勢博弈理論予以分析、解決.

4 基于勢博弈的代價感知任務調(diào)度算法

在本節(jié)中，我們將詳細介紹如何通過博弈論相關理論去高效解決3.5節(jié)的任務調(diào)度問題.

接下來，我們研究CATS博弈是否存在純策略的納什均衡解.在此之前，我們需要介紹2個定義.

定義1.給定a-n，用戶n的最佳響應函數(shù)bn(a-n)是一組策略：

(17)

(18)

納什均衡解的解釋如下：在納什均衡解，每個玩家(在我們問題中為用戶)可以在其他玩家策略(在我們問題中為卸載策略)不變的情況下，通過改變其自身策略而進一步減小其成本(在我們問題中為加權(quán)代價).

推論1.CATS博弈G擁有至少一個純策略的納什均衡解并具有有限提升性，如果

(19)

(20)

(21)

證明. 我們可以證明CATS博弈G是一個廣義勢博弈[27]，該勢博弈的勢函數(shù)為

(22)

從而

(23)

證畢.

具體證明過程可以參考我們補充的在線材料[26].每個廣義勢博弈都存在至少一個純策略的納什均衡解.而且，無論以什么為起點，每個較優(yōu)或最佳響應序列都收斂于一個純策略的納什均衡解，即有限提升性[27].

式(20)中，Dn,m表示霧節(jié)點m每多服務一位用戶，其所服務的用戶n增加的計算卸載的代價.這一值在實際中一般為正數(shù)，否則霧節(jié)點可以服務越來越多的用戶，而這顯然與實際不符.Bn和Fn的值一般也為正數(shù)，否則用戶會因為費用項過大而選擇本地計算，博弈則失去意義.在實際仿真時，我們可以通過限制用戶的決策空間得已保證這些條件得到滿足.

利用有限提升性，我們可以設計一個分布式算法——CATS算法，去尋找CATS博弈的一個純策略納什均衡解.我們將時間劃分為多個決策時隙[8,10-12]，進而整個算法如算法1所示.

我們進一步分析了上述分布式算法的收斂復雜度，如推論2所示.

(24)

(25)

具體證明過程可以參考我們補充的在線材料[26].

5 實驗與結(jié)果

在本節(jié)中，我們通過數(shù)值仿真來評估CATS算法及動態(tài)付費模型的表現(xiàn).

5.1 仿真設置

我們考慮一個由多個用戶、10個霧節(jié)點及云組成的多層次算力網(wǎng)絡，其中每個用戶可以使用LTE將計算任務卸載到遙遠的云上，或WiFi將計算任務卸載到附近的霧節(jié)點上.為方便起見，我們假設每個用戶都可以使用所有霧節(jié)點及云的服務.另外，我們假設每個計算任務的大小zn(單位是KB)和處理密度γn(單位是cycleb)分別從[500,5 000]和[500,3 000]中隨機選取.

通信方面，LTE和WiFi的平均傳輸速率為5.85 Mbs和3.01 Mbs[18,28]，因此我們假設LTE的傳輸速率Rn,c(單位是Mbs)和WiFi的傳輸速率Rn,m(單位是Mbs)分別均勻分布于[4.85,6.85]和[2.01,4.01][17,28].云計算的往返時延設為3 s.另外，我們將用戶通過LTE通信的傳輸功率和通過WiFi通信的傳輸功率分別設為2 605 mJs[18,29]和1 224.78 mJs[18,28].

計算方面，我們假設每個用戶的本地計算能力為fn，即本地設備的CPU時鐘頻率(單位是GHz)，從{0.8,0.9,1.0,1.1,1.2}中隨機選取[7]，而云提供的計算能力fc和霧節(jié)點的計算能力fm分別設為10 GHz和20 GHz.另外，本地計算的能耗常數(shù)κn=10-27[13,30].

付費方面，考慮到一般的云計算數(shù)據(jù)中心位于偏僻位置且集中管理，成本較低，而霧節(jié)點一般位于用戶周圍且分散管理，成本相對較高，因此我們設云服務提供商的報價ccloud=9×10-10，霧服務提供商的報價cfog=10×10-10，以確保付費和時延、能耗在同一數(shù)量級大小.另外，設霧服務提供商的折扣因子α=0.04.

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

圖3比較了CATS算法和4種基準方法在系統(tǒng)平均代價方面的表現(xiàn)：

1) 本地計算(Local).每個用戶在本地設備處理其計算任務.

2) 云計算(Cloud).每個用戶將其計算任務卸載到云上進行處理.

3) 隨機卸載(Random).每個用戶隨機地決定是在本地處理其計算任務，還是將其計算任務卸載到云或某個霧節(jié)點上進行處理.

4) 最優(yōu)卸載(Optimal).我們采用交叉熵[31]方法得到最小化系統(tǒng)整體代價的解.交叉熵是一種求解組和優(yōu)化問題近似最優(yōu)解的有效方法.具體的求解過程及參數(shù)設置可參考文獻[32].

Fig. 3 System average cost vs number of UEs圖3 系統(tǒng)平均代價vs用戶數(shù)

如圖3所示，CATS算法總能取得近似最優(yōu)的系統(tǒng)平均代價，并且大大優(yōu)于其他基準方法.這從系統(tǒng)整體角度驗證了CATS算法的表現(xiàn).另外，我們可以發(fā)現(xiàn)，通過引入霧層，可以大大降低用戶的計算卸載代價.

5.3 受益用戶數(shù)

Fig. 4 Number of beneficial UEs vs number of UEs圖4 受益用戶數(shù)vs用戶數(shù)

如圖4所示，除了隨機卸載之外，CATS算法、最優(yōu)卸載以及云計算的受益用戶數(shù)都隨著用戶數(shù)的增加而增加，但CATS算法的受益用戶數(shù)始終最大.這是因為以最小化系統(tǒng)代價為目標的最優(yōu)卸載會損害用戶個體利益，而通過將任務卸載建模為CATS博弈，可以協(xié)調(diào)用戶之間的競爭、沖突，從而使得更多用戶可以從中獲益.所以，CATS算法可以使得用戶對調(diào)度結(jié)果更滿意，因此結(jié)果也更穩(wěn)定.這從用戶個體角度驗證了CATS算法的表現(xiàn).

5.4 本地計算、霧計算及云計算用戶分布

圖5展示了CATS算法下，選擇本地計算、霧計算及云計算的用戶分布.如圖5所示，隨著用戶數(shù)的增加，選擇本地計算及云計算的用戶也隨之增加，這是因為霧節(jié)點的資源慢慢趨近飽和.

5.5 時延、能耗及付費成本分布

圖6展示了CATS算法下，用戶的平均時延、能耗及付費的成本分布.如圖6所示，隨著用戶數(shù)的增加，時延及能耗成本也隨之緩慢增加，逐漸占據(jù)主要成本.但付費成本反而隨著用戶數(shù)的增加而緩慢下降直至飽和.這是因為在動態(tài)付費模型下，單個用戶的付費隨著用戶數(shù)的增加而降低，直至霧節(jié)點達到服務容量上限.

Fig. 5 Number of UEs processed at local, fog, and cloud vs number of UEs圖5 本地計算、霧計算及云計算的用戶數(shù)vs用戶數(shù)

Fig. 6 Delay, energy and payment vs number of UEs圖6 時延、能耗及付費vs用戶數(shù)

5.6 收斂性

圖7展示了CATS算法收斂所需的決策時隙數(shù)隨用戶數(shù)的變化關系.如圖7所示，CATS算法收斂所需的決策時隙數(shù)隨著用戶數(shù)的增長而線性增長，與我們推論2得到的結(jié)果基本吻合.這也表明，CATS算法可以很好地適應網(wǎng)絡規(guī)模，因此適用于大規(guī)模網(wǎng)絡.

5.7 動態(tài)付費模型vs靜態(tài)付費模型

圖8比較了霧節(jié)點分別采用動態(tài)付費模型和靜態(tài)付費模型的收入.所謂靜態(tài)付費模型是指霧服務提供商對單位計算量收取的費用固定為cfog，不受用戶數(shù)影響，因此用戶n向霧節(jié)點支付的費用為cfogznγn.我們將動態(tài)付費模型的CATS算法和靜態(tài)付費模型的CATS算法分別記作CATS-dynamic和CATS-static.CATS博弈在靜態(tài)付費模型下對應的博弈同樣是一個廣義勢博弈，因此可以采用類似CATS算法的方法去尋找純策略的納什均衡解.由于內(nèi)容限制，我們不再另做證明.

Fig. 7 Number of decision slots vs number of UEs圖7 決策時隙數(shù)vs用戶數(shù)

Fig. 8 Income of FNs vs number of UEs under different payment model圖8 不同付費模型下的霧節(jié)點的收入vs用戶數(shù)

如圖8所示，2種付費模型下，霧節(jié)點的收入都隨著用戶數(shù)的增加而增加.在用戶數(shù)較小時，CATS-dynamic的霧節(jié)點收入和CATS-static的霧節(jié)點收入不相上下，但在用戶數(shù)較大時，前者明顯要大于后者.這是因為，在用戶數(shù)較小時，霧節(jié)點無法吸引足夠的用戶，因此和云相比無法形成價格優(yōu)勢，從而使不同付費模型下霧節(jié)點服務的用戶數(shù)可能一致.在服務用戶數(shù)一致的情況下，靜態(tài)付費模型顯然可以幫助霧節(jié)點獲得更多收入.但是，在用戶數(shù)較大時，霧節(jié)點可以吸引足夠的用戶，動態(tài)模型這種“薄利多銷”的模式可以幫助霧節(jié)點獲得更多收入.因此，相比靜態(tài)付費模型，動態(tài)付費模型可以讓霧節(jié)點獲得更多收入，尤其是在用戶數(shù)較大時.

6 總 結(jié)

本文提出了一個云霧混合多層次算力網(wǎng)絡及計算卸載系統(tǒng)，定義了一個由時延、能耗及付費組成的加權(quán)代價函數(shù)，并建模了一個代價感知任務調(diào)度CATS問題.而且，為激發(fā)云和霧的積極性，我們提出了一個基于計算量的付費模型并將付費相關代價也考慮進總代價.具體來說，根據(jù)云和霧的不同特性和需求，我們分別提出了一個靜態(tài)付費模型和動態(tài)付費模型，從而構(gòu)建了一個混合付費模型.為解決上述任務調(diào)度問題，我們提出了一個基于勢博弈的問題分析框架.具體地，我們先將原問題構(gòu)造為一個非合作博弈，然后通過勢博弈理論證明了該博弈存在純策略的納什均衡解，最后利用有限提升性設計了一個分布式任務調(diào)度CATS算法去尋找納什均衡解.我們最后進行了大量的數(shù)值仿真驗證了算法在系統(tǒng)整體及用戶個體2個維度上均具有優(yōu)異的表現(xiàn)，即和集中式最優(yōu)方法相比，CATS算法既可以取得近似最優(yōu)的系統(tǒng)平均代價，又可以讓更多用戶從任務卸載中受益.此外，數(shù)值仿真結(jié)果也驗證了，與靜態(tài)付費模型相比，動態(tài)付費模型可以幫助霧在用戶數(shù)較大時獲得更多收入.