多層次算力網絡中代價感知任務調度算法

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

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

2 多層次算力網絡

在本節中，我們主要介紹多層次算力網絡的相關概念及特性.

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

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

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

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

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

3 基于多層次算力網絡的計算卸載系統

3.1 系統概述

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

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

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

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

3.2 通信模型

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

(1)

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

(2)

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

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

(3)

(4)

(5)

3.3 計算模型

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

(6)

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

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

(7)

其中,κn是與硬件結構相關的常數.

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

(8)

其中,fm是霧節點m的計算能力.

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

(9)

3.4 付費模型

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

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

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

(10)

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

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

Cn,c=ccloudznγn,

(11)

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

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

3.5 問題建模

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

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

(12)

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

(13)

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

(14)

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

(15)

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

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

(16)

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

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

4 基于勢博弈的代價感知任務調度算法

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

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

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

(17)

(18)

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

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

(19)

(20)

(21)

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

(22)

從而

(23)

證畢.

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

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

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

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

(24)

(25)

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

5 實驗與結果

在本節中，我們通過數值仿真來評估CATS算法及動態付費模型的表現.

5.1 仿真設置

我們考慮一個由多個用戶、10個霧節點及云組成的多層次算力網絡，其中每個用戶可以使用LTE將計算任務卸載到遙遠的云上，或WiFi將計算任務卸載到附近的霧節點上.為方便起見，我們假設每個用戶都可以使用所有霧節點及云的服務.另外，我們假設每個計算任務的大小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和霧節點的計算能力fm分別設為10 GHz和20 GHz.另外，本地計算的能耗常數κn=10-27[13,30].

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

5.2 系統平均代價

圖3比較了CATS算法和4種基準方法在系統平均代價方面的表現：

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

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

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

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

Fig. 3 System average cost vs number of UEs圖3 系統平均代價vs用戶數

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

5.3 受益用戶數

Fig. 4 Number of beneficial UEs vs number of UEs圖4 受益用戶數vs用戶數

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

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

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

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

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

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

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

5.6 收斂性

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

5.7 動態付費模型vs靜態付費模型

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

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

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

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

6 總 結

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