異構(gòu)蜂窩網(wǎng)絡(luò)中分層任務(wù)卸載：建模與優(yōu)化

趙臨東，莊文芹，陳建新，周亮

（1.南京郵電大學(xué)通信與網(wǎng)絡(luò)技術(shù)國(guó)家工程研究中心，江蘇 南京 210003；2.南京郵電大學(xué)寬帶無(wú)線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，江蘇 南京 210003）

1 引言

隨著第五代移動(dòng)通信技術(shù)（5G,the fifth generation）的應(yīng)用，觸覺(jué)互聯(lián)網(wǎng)等新型多媒體服務(wù)和自動(dòng)駕駛等人工智能應(yīng)用將成為移動(dòng)用戶的熱門選擇[1-2]。這些應(yīng)用無(wú)一例外地需要龐大的計(jì)算資源來(lái)對(duì)數(shù)據(jù)進(jìn)行實(shí)時(shí)處理，且往往對(duì)時(shí)延有著十分苛刻的要求。然而，在物理尺寸受限的情況下，僅具備有限計(jì)算能力和電池容量的移動(dòng)設(shè)備如何承載這些計(jì)算密集型任務(wù)是一個(gè)不小的挑戰(zhàn)[3]。為了解決計(jì)算密集型應(yīng)用和資源受限的移動(dòng)設(shè)備之間的矛盾，任務(wù)卸載作為一種極具前景的解決方案應(yīng)運(yùn)而生。通過(guò)將任務(wù)卸載給計(jì)算能力更強(qiáng)大和電量更充足的節(jié)點(diǎn)處理，移動(dòng)用戶可以在現(xiàn)有硬件條件下享受更多新興服務(wù)[4]。

在任務(wù)卸載這一研究方向下，移動(dòng)邊緣計(jì)算（MEC,mobile edge computing）這一5G 新興卸載模式因進(jìn)一步減少了卸載時(shí)延而得到業(yè)界的廣泛關(guān)注[5]。與傳統(tǒng)云計(jì)算將計(jì)算資源配置在遠(yuǎn)離用戶的遠(yuǎn)端云不同，MEC 在更加靠近用戶的基站側(cè)即可實(shí)時(shí)處理數(shù)據(jù)，可以避免核心網(wǎng)傳輸?shù)念~外時(shí)延以及高峰期網(wǎng)絡(luò)擁塞等不利影響[6]。然而，盡管MEC通過(guò)將計(jì)算資源下沉獲得了時(shí)延方面的優(yōu)勢(shì)，該技術(shù)仍不可避免地受到上行通信帶來(lái)的額外時(shí)延和能耗的制約[7]。尤其是考慮到任務(wù)卸載時(shí)上行流量遠(yuǎn)大于下行流量這一顯著特點(diǎn)，如何設(shè)計(jì)高效的卸載調(diào)度方案以提升能量效率[8-10]或削減端到端時(shí)延[12-14]或?qū)崿F(xiàn)二者的聯(lián)合優(yōu)化[15-19]，已成為MEC 研究的一大熱點(diǎn)。

為了進(jìn)一步提高任務(wù)卸載的效率，有研究者提出引入基于終端直通（D2D,device-to-device）技術(shù)的卸載模式作為MEC 的有效補(bǔ)充[20]。該類方案又可稱為D2D 計(jì)算卸載，其基本原理是利用移動(dòng)設(shè)備間可用計(jì)算資源的強(qiáng)度異構(gòu)性和運(yùn)行時(shí)間異步性，將計(jì)算任務(wù)通過(guò)傳輸效率更高的D2D 鏈路傳送給當(dāng)前計(jì)算資源閑置的鄰近設(shè)備處理[21]。得益于設(shè)備間計(jì)算資源的合作共享和D2D 通信的復(fù)用增益等優(yōu)勢(shì)，MEC 和D2D 的結(jié)合帶給移動(dòng)用戶更多符合自身需求的卸載選擇，并進(jìn)一步提高了任務(wù)卸載的能量效率和網(wǎng)絡(luò)資源利用率[22]。

目前，圍繞MEC 結(jié)合D2D 的任務(wù)卸載方案已得到了一定研究[23-26]。文獻(xiàn)[23]將任務(wù)分割為3 份，分別交給邊緣節(jié)點(diǎn)、D2D 合作設(shè)備和本機(jī)同時(shí)處理，并以系統(tǒng)承載人數(shù)為目標(biāo)優(yōu)化任務(wù)分割。文獻(xiàn)[24]考慮設(shè)備移動(dòng)性，為車聯(lián)網(wǎng)設(shè)計(jì)了D2D-MEC任務(wù)卸載系統(tǒng)，并借助增強(qiáng)學(xué)習(xí)的手段實(shí)現(xiàn)卸載時(shí)延和能耗的聯(lián)合優(yōu)化。文獻(xiàn)[25]則針對(duì)無(wú)線網(wǎng)絡(luò)的隨機(jī)性為D2D-MEC 任務(wù)卸載系統(tǒng)設(shè)計(jì)了一種基于李雅普諾夫優(yōu)化的能量效率優(yōu)化方案。文獻(xiàn)[26]提出了一種本地計(jì)算、D2D 卸載和邊緣計(jì)算三選一的任務(wù)卸載系統(tǒng)，并重點(diǎn)研究了蜂窩上行通信擁塞和D2D 復(fù)用干擾對(duì)卸載決策的影響。

盡管現(xiàn)有的MEC 結(jié)合D2D 計(jì)算卸載的方案已取得不俗成效，但其仍在以下三方面存在著不足。第一，設(shè)備間通信資源的強(qiáng)度異構(gòu)性和運(yùn)行時(shí)間異步性沒(méi)有得到利用。第二，現(xiàn)有方案往往假設(shè)邊緣服務(wù)器給每個(gè)用戶提供固定的計(jì)算資源而不設(shè)接入數(shù)量上限，忽略了用戶對(duì)有限邊緣計(jì)算資源的競(jìng)爭(zhēng)帶給任務(wù)卸載性能的影響。第三，現(xiàn)有方案往往忽略云計(jì)算在任務(wù)卸載系統(tǒng)中的作用，或假設(shè)邊緣服務(wù)器具有和遠(yuǎn)端云對(duì)等的計(jì)算能力[23-26]。在實(shí)際邊緣計(jì)算資源受限的情況下，存在額外往返時(shí)延但計(jì)算資源更充足的云計(jì)算仍然可以起到分流卸載用戶和緩解邊緣負(fù)擔(dān)的作用。

針對(duì)上述問(wèn)題，本文提出了一種基于D2D 通信、MEC 和云計(jì)算的三層任務(wù)卸載框架。在所提框架下，用戶自低到高依次具有設(shè)備層（本地設(shè)備和D2D 合作設(shè)備）、邊緣層（邊緣服務(wù)器）和云層（云計(jì)算中心）3 個(gè)卸載層級(jí)可選。層級(jí)越高的卸載模式具有越豐富的計(jì)算資源，而將任務(wù)卸載到更高層級(jí)處理所付出的傳輸成本也更高。除了構(gòu)建上述分層卸載理念之外，所提框架還引入了D2D 協(xié)作中繼技術(shù)用于輔助用戶接入更高卸載層級(jí)，以使設(shè)備間通信資源的強(qiáng)度異構(gòu)性和運(yùn)行時(shí)間異步性得到開(kāi)發(fā)。本文通過(guò)考慮資源受限、復(fù)用干擾和回程時(shí)延等實(shí)際因素的影響，對(duì)所提框架中具有異構(gòu)設(shè)備能力和需求的用戶的卸載決策進(jìn)行合理調(diào)度，任務(wù)卸載效率和網(wǎng)絡(luò)資源利用率得到顯著提高。

本文主要貢獻(xiàn)概括如下。

1)為了最大化任務(wù)卸載可用的計(jì)算和通信資源并提高任務(wù)卸載的效率，本文提出了一種基于D2D通信、MEC 和云計(jì)算的三層任務(wù)卸載框架，并引入D2D 協(xié)作中繼技術(shù)輔助用戶接入遠(yuǎn)端計(jì)算資源。

2)針對(duì)所提出的三層任務(wù)卸載框架，本文兼顧上行通信擁塞、D2D 復(fù)用干擾、邊緣計(jì)算資源受限和云計(jì)算回程時(shí)延等實(shí)際因素的影響，為多用戶場(chǎng)景設(shè)計(jì)了一種基于博弈論的卸載調(diào)度和負(fù)載均衡方案。

3)通過(guò)設(shè)置仿真實(shí)驗(yàn)與其他計(jì)算卸載方案對(duì)比，所提方案可以有效降低端到端時(shí)延和卸載能耗，并在面對(duì)邊緣計(jì)算資源減少和接入用戶增多的不利情況下也保持良好的穩(wěn)定性能。

2 系統(tǒng)模型

本節(jié)將給出結(jié)合D2D 通信、MEC 和云計(jì)算所設(shè)計(jì)的三層任務(wù)卸載框架的系統(tǒng)模型，并借助多用戶任務(wù)卸載示意（如圖1 所示）和單用戶各卸載模式示意（如圖2 所示），詳細(xì)說(shuō)明所提框架的工作原理和各環(huán)節(jié)技術(shù)細(xì)節(jié)。

圖1 三層框架下多用戶任務(wù)卸載示意

假設(shè)在一個(gè)基站覆蓋范圍下有若干移動(dòng)設(shè)備同時(shí)配有蜂窩接口和D2D 接口，其中具有計(jì)算密集型任務(wù)亟待處理的移動(dòng)設(shè)備是所提框架的目標(biāo)用戶（如圖1 中的終端1、終端2、終端4 和終端6），而CPU 負(fù)載較低或信道質(zhì)量較好的設(shè)備（如圖1中的終端3 和終端5）則是目標(biāo)用戶潛在的D2D 合作設(shè)備。假設(shè)每個(gè)目標(biāo)用戶都有一個(gè)不重復(fù)的備選合作設(shè)備，能夠?yàn)槠涮峁┲欣^和計(jì)算卸載服務(wù)。基站側(cè)配有計(jì)算資源有限的邊緣服務(wù)器，可以處理移動(dòng)設(shè)備通過(guò)蜂窩上行傳來(lái)的任務(wù)，同時(shí)可以通過(guò)核心網(wǎng)將用戶任務(wù)卸載到計(jì)算資源充足的遠(yuǎn)端云。

每個(gè)用戶可自由選擇任務(wù)卸載的模式，共有6種模式，分別介紹如下。模式1 為本地計(jì)算，即用本機(jī)CPU 處理任務(wù)（如圖1 終端6）；模式2 為邊緣計(jì)算，即通過(guò)蜂窩上行將任務(wù)卸載給基站側(cè)邊緣服務(wù)器（如圖1 終端1）；模式3 為云計(jì)算，即通過(guò)蜂窩上行和核心網(wǎng)將任務(wù)卸載給遠(yuǎn)端云（如圖1終端1）；模式4 為D2D 卸載，即通過(guò)D2D 鏈路將任務(wù)交由合作設(shè)備處理（如圖1 終端4）；模式5 為 D2D 輔助邊緣計(jì)算，即通過(guò)合作設(shè)備的D2D中繼接入基站，再將任務(wù)卸載給基站側(cè)邊緣服務(wù)器（如圖1 終端2）；模式6 為D2D 輔助云計(jì)算，即通過(guò)合作設(shè)備的D2D 中繼接入基站，再將任務(wù)卸載給遠(yuǎn)端云（如圖1 終端2）。定義N={1,2,…,N}為N個(gè)目標(biāo)用戶的集合，i∈N 表示集合中某一用戶，di為與用戶i配對(duì)的D2D 合作設(shè)備，集合S={1,2,3,4,5,6}為所有用戶備選的策略集，ai∈S為用戶i所選決策，ai的值對(duì)應(yīng)用戶i選擇的卸載模式編號(hào)。用戶i選擇不同卸載模式對(duì)應(yīng)的任務(wù)卸載路徑、時(shí)延來(lái)源和能耗來(lái)源等，如圖2 所示。接下來(lái)將給出具體的參數(shù)設(shè)定，并結(jié)合圖2 詳細(xì)闡述這6 種卸載模式的技術(shù)細(xì)節(jié)。

2.1 本地計(jì)算模式

圖2 三層框架下單用戶各卸載模式示意

當(dāng)ai=1時(shí)，用戶i在本地獨(dú)立處理計(jì)算任務(wù)。從圖2 可以看出，模式1 對(duì)應(yīng)的時(shí)延為本地CPU計(jì)算耗時(shí)，能耗為本地CPU 計(jì)算耗電。用戶i的計(jì)算任務(wù)可由三元組描述，其中，λi表示任務(wù)卸載時(shí)本地設(shè)備需向外傳輸?shù)臄?shù)據(jù)量，μi表示任務(wù)處理完成后由外部節(jié)點(diǎn)傳回的數(shù)據(jù)量，ψi表示處理該任務(wù)所需的機(jī)器語(yǔ)言指令數(shù)，表示用戶i本機(jī)CPU 的計(jì)算速度，ωi表示用戶i當(dāng)前可用計(jì)算資源的總占比，則用戶i在本地計(jì)算模式下的總時(shí)延可以表示為

用戶i在本地計(jì)算模式下的總能耗表示為

考慮到時(shí)延和能耗都是任務(wù)卸載所重點(diǎn)關(guān)注的指標(biāo)，并且不同用戶對(duì)二者的重視程度和要求會(huì)有所不同，本文定義任一卸載模式下任務(wù)處理時(shí)延和能耗的加權(quán)和為用戶選擇該模式的開(kāi)銷。用戶i本地計(jì)算模式下的開(kāi)銷為

2.2 邊緣計(jì)算模式

當(dāng)ai=2時(shí)，用戶i經(jīng)蜂窩上行將任務(wù)卸載給基站側(cè)邊緣服務(wù)器。在時(shí)延方面，參照文獻(xiàn)[23]的假設(shè)，本文考慮所有用戶處在準(zhǔn)靜態(tài)信道狀態(tài)下，即所有蜂窩鏈路和D2D 鏈路的信道增益在一個(gè)計(jì)算任務(wù)周期內(nèi)保持不變，僅在進(jìn)入下一個(gè)周期時(shí)發(fā)生變化；假設(shè)蜂窩通信和D2D 通信使用不同的頻段，因此不考慮彼此干擾對(duì)傳播時(shí)延的影響；由于任務(wù)處理后的計(jì)算結(jié)果相對(duì)輸入數(shù)據(jù)規(guī)模較小而蜂窩下行速率較高，因此忽略計(jì)算結(jié)果傳回的時(shí)延；由于邊緣服務(wù)器就近部署在基站側(cè)并與基站以有線方式連接，因此忽略任務(wù)從基站接入邊緣服務(wù)器的耗時(shí)；但考慮到邊緣服務(wù)器的計(jì)算資源有限，其計(jì)算耗時(shí)不可忽略。在能耗方面，由于蜂窩下行時(shí)延可忽略且移動(dòng)設(shè)備接收功率較小，因此忽略用戶接收計(jì)算結(jié)果的能耗。

從圖2 可以看出，模式2 對(duì)應(yīng)的時(shí)延為蜂窩上行的無(wú)線傳播時(shí)延和邊緣服務(wù)器計(jì)算耗時(shí)，能耗為用戶設(shè)備無(wú)線接口發(fā)射耗電。用戶i的蜂窩上行傳輸速率Ri,cell(a)可以表示為

其中，a=(a1,a2,…,aN)為集合N 中每個(gè)用戶所選決策組成的決策向量；Y(A)為一指示函數(shù)，當(dāng)A為真時(shí)函數(shù)值為1，反之為0；?0為傳輸背景噪聲功率；B1為蜂窩上行帶寬；Hi,cell為用戶i與基站間蜂窩上行信道增益；Pi,cell為用戶i的蜂窩上行發(fā)射功率。需要說(shuō)明的是，本文主要研究資源受限條件下的多用戶接入競(jìng)爭(zhēng)問(wèn)題，并著重考慮過(guò)量用戶無(wú)序競(jìng)爭(zhēng)帶來(lái)的網(wǎng)絡(luò)擁塞效應(yīng)對(duì)卸載性能的影響。因此參考文獻(xiàn)[28]的假設(shè)，在頻譜分配處額外引入?yún)⑴c用戶數(shù)的非線性項(xiàng)，以反映通信擁塞的邊際效應(yīng)遞增這一特性，β1為控制蜂窩上行網(wǎng)絡(luò)擁塞效應(yīng)強(qiáng)弱的系數(shù)。該模型可用于對(duì)基于時(shí)分多址（TDMA,time division multiple access）或正交頻分多址（OFDMA,orthogonal frequency division multiple access）的帶寬共享機(jī)制進(jìn)行建模。

考慮到邊緣服務(wù)器的計(jì)算能力有限，根據(jù)文獻(xiàn)[11]，定義多用戶參與下邊緣服務(wù)器的計(jì)算耗時(shí)為

其中，F(xiàn)表示邊緣服務(wù)器可用CPU 轉(zhuǎn)速。需要說(shuō)明的是，描述邊緣服務(wù)器計(jì)算能力受限的主流模型共有2 種，一種是硬性設(shè)置邊緣云的任務(wù)負(fù)載上限；另一種是假設(shè)計(jì)算資源均分給用戶，邊緣服務(wù)器計(jì)算時(shí)延將隨過(guò)量接入增大[11]。本文為反映多用戶對(duì)計(jì)算資源的競(jìng)爭(zhēng)而使用了后一種假設(shè)。

綜上，用戶i在邊緣計(jì)算模式下的總時(shí)延表示為

用戶i在邊緣計(jì)算模式下的總能耗表示為

用戶i邊緣計(jì)算模式下的開(kāi)銷為

2.3 云計(jì)算模式

當(dāng)ai=3時(shí)，用戶i經(jīng)蜂窩上行將計(jì)算任務(wù)傳給基站，再經(jīng)核心網(wǎng)卸載給遠(yuǎn)端云。如圖2 所示，模式3 的時(shí)延除了上行無(wú)線傳播時(shí)延外，主要為回程時(shí)延、排隊(duì)時(shí)延、核心網(wǎng)傳輸時(shí)延等核心網(wǎng)相關(guān)參數(shù)。為了簡(jiǎn)化分析，本文假設(shè)每個(gè)用戶的計(jì)算任務(wù)和計(jì)算結(jié)果通過(guò)核心網(wǎng)帶來(lái)的時(shí)延總和均為定值tcore，這一參數(shù)可以由當(dāng)前時(shí)段歷史平均時(shí)延表示或通過(guò)分析近期網(wǎng)絡(luò)時(shí)延動(dòng)態(tài)預(yù)測(cè)得到。考慮到遠(yuǎn)端云的計(jì)算資源較充足，故忽略其計(jì)算耗時(shí)。

由此，用戶i在云計(jì)算模式下的總時(shí)延可以表示為

用戶i在云計(jì)算模式下的總能耗與邊緣計(jì)算模式能耗相同，即，其在云計(jì)算模式下的開(kāi)銷為

2.4 D2D 卸載模式

當(dāng)ai=4時(shí)，用戶i將任務(wù)卸載給D2D 合作設(shè)備。如圖2 所示，模式4 對(duì)應(yīng)的時(shí)延為D2D 鏈路無(wú)線傳播時(shí)延以及合作設(shè)備CPU 計(jì)算耗時(shí)。由于D2D 回傳鏈路也受擁塞影響，傳輸速率較蜂窩下行更低，因此盡管計(jì)算結(jié)果數(shù)據(jù)量較小，仍不可忽略其回傳時(shí)延。

由此，用戶i與其合作設(shè)備的D2D 鏈路傳輸速率為

其中，B2是模式4 下D2D 鏈路的可用帶寬，是用戶i與其合作設(shè)備間D2D 信道增益，是用戶i進(jìn)行D2D 通信的功率。為了簡(jiǎn)化分析，這里假設(shè)用戶i的合作設(shè)備di的D2D 發(fā)射功率也為，故既是用戶i進(jìn)行D2D 通信的發(fā)送速率，也是接收速率。本文出于公平性的考慮，假設(shè)模式4 中D2D 鏈路與模式5 和模式6 中D2D 協(xié)作通信使用不同的頻段。這是由于D2D 協(xié)作通信時(shí)用戶及其合作設(shè)備均處于發(fā)射狀態(tài)，較模式4 帶來(lái)的網(wǎng)絡(luò)擁塞效應(yīng)更強(qiáng)。此外，為研究過(guò)量用戶無(wú)序競(jìng)爭(zhēng)帶來(lái)的網(wǎng)絡(luò)擁塞效應(yīng)對(duì)卸載性能的影響，本文同樣參考文獻(xiàn)[28]在頻譜分配時(shí)額外加入?yún)⑴c用戶數(shù)的非線性項(xiàng)，β2為反映D2D 通信網(wǎng)絡(luò)擁塞效應(yīng)強(qiáng)弱的系數(shù)。

用戶i的合作設(shè)備di的CPU 計(jì)算速度用表示，則用戶i在D2D 卸載模式下的總時(shí)延可以表示為

合作設(shè)備di的CPU 每執(zhí)行一機(jī)器語(yǔ)言指令所消耗能量用表示，用戶i在D2D 卸載模式下的總能耗為

此處合作設(shè)備的能耗也被計(jì)入用戶在模式4 下的總能耗。這是因?yàn)楹献髟O(shè)備通常也是能量受限的，其能耗往往以報(bào)酬形式在激勵(lì)機(jī)制中有所體現(xiàn)，使用戶在請(qǐng)求D2D 協(xié)作時(shí)不得不計(jì)入這一成本。為了簡(jiǎn)化分析，本文不再展開(kāi)相關(guān)議價(jià)細(xì)則，而是以一比一的轉(zhuǎn)化關(guān)系將合作設(shè)備能耗計(jì)入用戶總能耗。

綜上，用戶i在D2D 卸載模式下的總開(kāi)銷為

2.5 D2D 輔助邊緣計(jì)算模式

當(dāng)ai=5時(shí)，用戶i經(jīng)合作設(shè)備中繼與基站連接，再將任務(wù)卸載給基站側(cè)邊緣服務(wù)器。如圖2 所示，模式5 的時(shí)延包括中繼鏈路時(shí)延和邊緣服務(wù)器計(jì)算耗時(shí)，能耗為用戶及其合作設(shè)備無(wú)線接口通信耗電。為了簡(jiǎn)化分析，本文考慮模式5 和模式6 的D2D 中繼采用譯碼重傳（DF,decode-and-forward）模式。參考文獻(xiàn)[29]，協(xié)作通信可實(shí)現(xiàn)的傳輸速率表示為

其中，B3表示DF 中繼的可用帶寬，ξi,di表示合作設(shè)備di在DF 中繼模式下收到用戶i信號(hào)的信干噪比，ξi,cell和ξdi,cell分別表示基站在DF 中繼模式下收到用戶i及其合作設(shè)備信號(hào)的信干噪比，和分別表示用戶i及其合作設(shè)備在DF 中繼模式下的發(fā)射功率，β3為D2D 中繼網(wǎng)絡(luò)擁塞效應(yīng)強(qiáng)弱的系數(shù)。

由此，用戶i在D2D 輔助邊緣計(jì)算模式下的總時(shí)延表示為

用戶i在D2D 輔助邊緣計(jì)算模式下的總能耗表示為

用戶i在D2D 輔助邊緣計(jì)算模式下的總開(kāi)銷為

2.6 D2D 輔助云計(jì)算模式

當(dāng)ai=6時(shí)，用戶i經(jīng)合作設(shè)備中繼與基站連接，再經(jīng)核心網(wǎng)將任務(wù)卸載給遠(yuǎn)端云。如圖2 所示，模式6 的時(shí)延包括D2D 協(xié)作中繼鏈路時(shí)延和核心網(wǎng)傳輸相關(guān)時(shí)延，能耗為用戶及其合作設(shè)備無(wú)線接口通信耗電。

用戶i在D2D 輔助云計(jì)算模式下的總時(shí)延表示為

用戶i在D2D 輔助邊緣計(jì)算模式下的總能耗與模式5 能耗相同，即，其在D2D 輔助云計(jì)算模式下的開(kāi)銷為

由上述分析可以看出，本文框架下不同用戶的決策之間存在耦合關(guān)系，過(guò)多用戶選擇相同的卸載路徑不利于提高任務(wù)卸載性能。因此，網(wǎng)絡(luò)運(yùn)營(yíng)者有必要為多用戶參與的情況設(shè)計(jì)卸載調(diào)度方案，以起到優(yōu)化系統(tǒng)效率和實(shí)現(xiàn)負(fù)載均衡的效果。

3 三層框架下多用戶任務(wù)卸載方案

本節(jié)基于上述系統(tǒng)模型為所提框架設(shè)計(jì)了一個(gè)基于博弈論的多用戶任務(wù)卸載方案。考慮到所提框架下所有用戶均希望最小化自身開(kāi)銷，而不同用戶設(shè)備性能、所運(yùn)行應(yīng)用和對(duì)時(shí)延能耗的敏感程度不同，基于最優(yōu)化的方案得到的全局最優(yōu)或次優(yōu)調(diào)度結(jié)果往往建立在犧牲部分用戶的基礎(chǔ)上。本節(jié)旨在尋求一個(gè)兼具公平性和效率的帕累托最優(yōu)調(diào)度結(jié)果，因此使用博弈論設(shè)計(jì)卸載方案。

這里首先給出博弈論中最優(yōu)決策的定義。假設(shè)a-i=(a1,…,ai-1,ai+1,…,aN)為用戶i以外的其他用戶所選決策組成的向量。約定俗成地，給定向量a-i，用戶i的最優(yōu)決策將最大化自身收益。考慮到所提框架下的理性決策人以最小化自身開(kāi)銷為目標(biāo)，故將用戶的收益函數(shù)定義為開(kāi)銷值的相反數(shù)，進(jìn)而可將最優(yōu)決策表示為

其中，Ui(ai,a-i)是用戶i的收益函數(shù)。根據(jù)式(3)、式(8)、式(10)、式(14)、式(18)、式(20)，可得Ui(ai,a-i)表達(dá)式為

用戶能否取得最優(yōu)策略對(duì)于本文所提計(jì)算卸載框架具有重要意義。從用戶角度來(lái)看，最優(yōu)策略保證了決策的個(gè)人理性，即用戶不會(huì)主動(dòng)選擇有損計(jì)算卸載效果的模式；從網(wǎng)絡(luò)運(yùn)營(yíng)者角度來(lái)看，最優(yōu)策略保證了空閑網(wǎng)絡(luò)資源能夠得到充分使用，提高了用戶購(gòu)買云/邊緣計(jì)算服務(wù)的積極性。因此，有別于傳統(tǒng)的計(jì)算卸載或無(wú)線接入方案（如文獻(xiàn)[11,23]），所提方案需要保證用戶選擇最優(yōu)決策，從而不會(huì)拒絕調(diào)度結(jié)果（如拒絕使用云/邊緣計(jì)算服務(wù)，而選擇本地計(jì)算）。

基于上述分析，三層框架下各用戶有關(guān)計(jì)算卸載模式的決策問(wèn)題可以建模為博弈Ω={N,ΦN,Ui}，相關(guān)要素描述如下。

3）當(dāng)污水流速為0.15 m/s，堵塞換熱系數(shù)約685 W/m2·K，當(dāng)污水流速增大到0.2 m/s，換熱系數(shù)約850 W/m2·K，增大了約24%.而污水速度增大到0.25 m/s時(shí)，堵塞換熱系數(shù)僅提高7%.

1)集合N 為博弈Ω的玩家集合，即三層框架下的用戶集合。

2)ΦN={(ai)i∈N:ai∈S,?i∈N}為博弈Ω中每個(gè)玩家可選的策略空間。

3)博弈Ω中玩家i的收益函數(shù)Ui如式(22)所示。

4)博弈Ω中玩家i的最優(yōu)反應(yīng)策略如式(21)所示。

首先，假設(shè)博弈過(guò)程在基站控制下進(jìn)行，而基站可以通過(guò)反饋的方式了解到各用戶及其合作設(shè)備的信道狀況、CPU 性能、任務(wù)屬性、當(dāng)前決策等相關(guān)信息。因此，可以認(rèn)為在博弈Ω中的玩家將依次做出決策（即每一步有且僅有一個(gè)玩家行動(dòng)），且任一玩家可以知道之前每一步何玩家做出了何種決策，即博弈Ω為一完美信息序貫博弈。本節(jié)將說(shuō)明博弈Ω不在基站集中求解時(shí)，如何保證其為完美信息序貫博弈。

下面給出博弈論中納什均衡的定義，通過(guò)求解博弈Ω的納什均衡，可以得到符合上述要求的調(diào)度結(jié)果。

定義1博弈Ω的納什均衡是一個(gè)決策向量aNE，當(dāng)博弈中的各玩家決策按此分布時(shí)，沒(méi)有玩家可以通過(guò)單方面改變自身決策來(lái)提高自身收益。或者說(shuō)，aNE滿足對(duì)每一玩家i，是i針對(duì)其他N-1 個(gè)玩家所選策略a-i的最優(yōu)反應(yīng)策略，即

考慮到策略空間離散且有限的完美信息序貫博弈必然存在納什均衡，因此博弈Ω的納什均衡存在且能夠由本地搜索算法迭代有限步逼近得到[26,30]。接下來(lái)具體分析當(dāng)單個(gè)用戶的6 種卸載模式之一分別作為最優(yōu)決策時(shí)需要滿足的條件。

其中，定常數(shù)c1由式(3)得到，其余定常數(shù)表示如下：

由于博弈Ω為一策略空間有限且離散的完美信息序貫博弈，在確定某玩家的最優(yōu)決策時(shí)，其他玩家的決策可被視為定常值（完備的全局信息已知）。比較該玩家不同決策對(duì)應(yīng)的收益函數(shù)值大小，便可通過(guò)有限次排序得到結(jié)果。由此整理式(21)、式(22)、式(24)，可得到如下結(jié)論。

1)ai=6是玩家i當(dāng)前最優(yōu)決策的條件表示為

2)ai=5是玩家i當(dāng)前最佳決策的條件表示為

3)ai=4是玩家i當(dāng)前最佳決策的條件表示為

4)ai=3是玩家i當(dāng)前最佳決策的條件表示為

5)ai=2是玩家i當(dāng)前最佳決策的條件表示為

由此，可以改寫(xiě)博弈Ω中玩家的最優(yōu)決策式(21)為

通過(guò)上述分析可以看出，單個(gè)玩家在任一次決策更新時(shí)用到的定常數(shù)只在系統(tǒng)初始化時(shí)計(jì)算一次并存儲(chǔ)即可。該玩家只需知道當(dāng)前公開(kāi)的決策向量便可由式(30)更新得到該步最優(yōu)策略。通過(guò)使用最優(yōu)決策響應(yīng)求解式(23)所示的納什均衡，為本文框架設(shè)計(jì)了一種多用戶任務(wù)卸載方案，如算法1 所示。

算法1三層框架下多用戶任務(wù)卸載方案

輸入背景噪聲?0，邊緣計(jì)算能力F，核心網(wǎng)時(shí)延tcore，各用戶計(jì)算任務(wù)Ti，權(quán)重；本地設(shè)備計(jì)算相關(guān)參數(shù)；D2D 合作設(shè)備計(jì)算相關(guān)參數(shù)；蜂窩通信相關(guān)參數(shù)B1,Hi,cell,Pi,cell；D2D 通信相關(guān)參數(shù)；協(xié)作中繼相關(guān)參數(shù)

輸出達(dá)到納什均衡的決策向量

算法1 可分為系統(tǒng)初始化和納什均衡擬合2 個(gè)階段。擬合階段中，系統(tǒng)決策向量通過(guò)迭代更新，該過(guò)程又可分為兩步，第一步為玩家根據(jù)當(dāng)前公開(kāi)的決策向量計(jì)算傳輸速率和計(jì)算耗時(shí)，第二步則根據(jù)第一步計(jì)算結(jié)果判斷是否需要更新卸載模式。當(dāng)沒(méi)有玩家更新自身決策時(shí)，系統(tǒng)達(dá)到穩(wěn)態(tài)，即取得納什均衡。

4 仿真結(jié)果

本節(jié)通過(guò)仿真分析評(píng)估所提出的任務(wù)卸載框架和多用戶卸載方案的性能。具體仿真環(huán)境設(shè)置如下。

假設(shè)有N個(gè)用戶隨機(jī)分布在邊長(zhǎng)為200 m的正方形小區(qū)中，基站部署在小區(qū)的中心位置，用戶的合作設(shè)備在距其1～50 m 隨機(jī)均勻分布。用戶計(jì)算任務(wù)輸入數(shù)據(jù)大小λi在50～500 KB 隨機(jī)均勻分布，輸出數(shù)據(jù)規(guī)模μi為輸入的，平均每比特所需機(jī)器語(yǔ)言指令數(shù)在[50,1 000]隨機(jī)均勻分布，用戶設(shè)備計(jì)算能力在{1.0,1.1,…,2.0}等概率取值，單位為GIPS（giga instruction per second）。用戶及其合作設(shè)備CPU 每指令耗電在[0,20]×10-11J/指令隨機(jī)均勻分布[11]。用戶可用計(jì)算資源占比ωi在[0.75,1]隨機(jī)均勻分布，用戶決策時(shí)對(duì)時(shí)延的敏感程度在{0,0.5,1}等概率取值。合作設(shè)備計(jì)算能力為2 GIPS，默認(rèn)邊緣服務(wù)器可用計(jì)算能力F為40 GIPS，核心網(wǎng)往返時(shí)延為500 ms。設(shè)置蜂窩鏈路和D2D 鏈路的信道增益為，其中l(wèi)i,j為節(jié)點(diǎn)i到節(jié)點(diǎn)j間距離，α=4為路徑損耗因子，取擁塞效應(yīng)系數(shù)β1=β3=0.01，β2=0.001，其他相關(guān)參數(shù)如表1所示[19]。

為了更好地評(píng)估所提框架和所提方案的性能，本文選擇在同等網(wǎng)絡(luò)資源條件下，所有用戶分別采取本地計(jì)算、邊緣計(jì)算、D2D 卸載、云-邊緣計(jì)算的方案進(jìn)行對(duì)比，其中云-邊緣計(jì)算表示用戶同時(shí)具有云計(jì)算和邊緣計(jì)算2 種模式可供任務(wù)卸載。不失一般性地，用戶總數(shù)N={5,10,…,50}情況下的各仿真結(jié)果均為各仿真實(shí)驗(yàn)重復(fù)1 000 次并取平均的結(jié)果。

表1 蜂窩鏈路和D2D 鏈路的相關(guān)參數(shù)

不同用戶總數(shù)條件下參與所提方案中本地計(jì)算模式、邊緣計(jì)算模式（不限接入方式）、云計(jì)算模式（不限接入方式）和D2D 卸載模式參與用戶數(shù)如圖3所示。可以看出，隨著用戶總數(shù)的增加，選擇邊緣計(jì)算模式的用戶數(shù)呈增長(zhǎng)放緩趨勢(shì)，選擇云計(jì)算模式的用戶數(shù)近似呈線性增長(zhǎng)，而選擇本地計(jì)算和D2D 卸載模式的用戶數(shù)呈增長(zhǎng)加快趨勢(shì)。這是因?yàn)椋S著用戶總數(shù)的增加，受限的上行通信資源和邊緣計(jì)算資源漸漸不能滿足用戶需求，帶給用戶更大的開(kāi)銷，進(jìn)而更多用戶分流到計(jì)算資源穩(wěn)定、通信質(zhì)量更好的本地計(jì)算模式和D2D 卸載模式。

圖3 不同用戶總數(shù)條件下所提方案中各卸載模式參與用戶數(shù)

不同用戶總數(shù)條件下所提方案和對(duì)照方案的平均計(jì)算卸載開(kāi)銷對(duì)比如圖4 所示。隨著用戶總數(shù)的增加，邊緣計(jì)算方案開(kāi)銷很快超過(guò)其他方案，本地計(jì)算方案開(kāi)銷近似不變，D2D 卸載方案開(kāi)銷呈近似線性增長(zhǎng)趨勢(shì)并最后超過(guò)本地計(jì)算方案開(kāi)銷，云-邊緣計(jì)算方案開(kāi)銷則穩(wěn)定保持增長(zhǎng)，所提方案開(kāi)銷增速較緩慢。這表明邊緣計(jì)算在競(jìng)爭(zhēng)較緩和時(shí)表現(xiàn)占優(yōu)，而D2D 卸載方案和云-邊緣計(jì)算方案得益于穩(wěn)定供給的計(jì)算資源不會(huì)隨系統(tǒng)用戶數(shù)增加而迅速增長(zhǎng)，但同樣會(huì)受通信資源制約。所提方案因充分利用了空閑網(wǎng)絡(luò)資源，在不同用戶數(shù)條件下性能均明顯占優(yōu)，開(kāi)銷相比云-邊緣計(jì)算方案平均減少了61%。

圖4 不同用戶總數(shù)條件下所提方案和對(duì)照方案的平均計(jì)算卸載開(kāi)銷

本節(jié)分別設(shè)定用戶僅考慮能耗或時(shí)延進(jìn)行決策的情況，以分析調(diào)度方案對(duì)這2 個(gè)指標(biāo)的影響，平均卸載能耗和時(shí)延性能曲線分別如圖5 和圖6 所示。可以看出，隨著用戶總數(shù)逐漸增多，所提方案較云-邊緣計(jì)算方案的能耗差逐漸增大。這是由于所提方案具備更豐富的接入手段，在上行帶寬占用不斷飽和時(shí)，部分用戶可智能分流到負(fù)載較小的其他模式，從而避免加重網(wǎng)絡(luò)擁塞效應(yīng)。所提方案的平均時(shí)延相較云-邊緣計(jì)算方案平均減少了近68%。

圖5 不同用戶總數(shù)條件下平均卸載能耗

圖6 不同用戶總數(shù)條件下平均卸載時(shí)延

本節(jié)在默認(rèn)系統(tǒng)參與用戶數(shù)為30 個(gè)的條件下，針對(duì)邊緣節(jié)點(diǎn)計(jì)算能力不同的情況對(duì)所提方案性能進(jìn)行了仿真。選擇所有用戶均采用不受邊緣節(jié)點(diǎn)影響的本地計(jì)算模式和均采用直接受邊緣計(jì)算資源影響的邊緣計(jì)算模式進(jìn)行對(duì)比。不失一般性地，邊緣計(jì)算資源F={20,25,…,60}GIPS 情況下各仿真結(jié)果均為仿真實(shí)驗(yàn)重復(fù)1 000 次并取平均的結(jié)果。不同邊緣計(jì)算資源條件下所提方案中各卸載模式參與用戶數(shù)如圖7 所示，不同邊緣計(jì)算資源條件下所提方案和對(duì)照方案的平均計(jì)算卸載開(kāi)銷如圖8 所示。從圖7可以看出，隨著邊緣計(jì)算資源增多，本地計(jì)算模式參與用戶數(shù)總體保持不變，用戶主要由計(jì)算資源供給穩(wěn)定的云計(jì)算和D2D 卸載模式向邊緣計(jì)算模式遷移。圖8 則展示了所提方案的穩(wěn)健性和穩(wěn)定性，即通過(guò)整合網(wǎng)絡(luò)中所有可用的計(jì)算和通信資源，在邊緣計(jì)算資源較少時(shí)依然保持性能平穩(wěn)占優(yōu)。

圖7 不同邊緣計(jì)算資源條件下所提方案中各卸載模式參與用戶數(shù)

圖8 不同邊緣計(jì)算資源條件下所提方案和對(duì)照方案的平均計(jì)算卸載開(kāi)銷

5 結(jié)束語(yǔ)

本文提出了一種基于D2D 通信、移動(dòng)邊緣計(jì)算和云計(jì)算的分層任務(wù)卸載框架。所提框架通過(guò)自低到高提供設(shè)備層、邊緣層和云層3 種卸載層級(jí)，并引入D2D 協(xié)作中繼技術(shù)輔助用戶接入更高層級(jí)的卸載模式，實(shí)現(xiàn)了對(duì)設(shè)備間計(jì)算和通信資源的能力異構(gòu)性和運(yùn)行時(shí)間異步性的充分開(kāi)發(fā)，發(fā)揮了云計(jì)算分流卸載用戶和減輕邊緣計(jì)算負(fù)擔(dān)的作用。借助博弈論的設(shè)計(jì)理念，本文針對(duì)所提框架設(shè)計(jì)的多用戶任務(wù)卸載調(diào)度方案，實(shí)現(xiàn)了兼具公平性的效率提升和負(fù)載均衡效果，從而提升了空閑網(wǎng)絡(luò)資源的利用率和用戶購(gòu)買云-邊緣計(jì)算服務(wù)的積極性。仿真結(jié)果證實(shí)了所提方案在減少端到端時(shí)延與卸載能耗方面和面對(duì)邊緣計(jì)算資源受限等不利條件時(shí)的優(yōu)越性。未來(lái)研究將著眼于所提分層任務(wù)卸載框架中，不同業(yè)務(wù)屬性帶來(lái)的固定時(shí)延限制或安全性要求對(duì)卸載決策和性能的影響。