多用戶D2D計(jì)算卸載與資源分配算法

韓躍林 朱 琦*

（1.南京郵電大學(xué)江蘇省無線通信重點(diǎn)實(shí)驗(yàn)室，江蘇南京 210003；2.南京郵電大學(xué)教育部泛在網(wǎng)絡(luò)健康服務(wù)系統(tǒng)工程研究中心，江蘇南京 210003）

1 引言

智能終端的普及使得人們的生活發(fā)生了翻天覆地的變化，然而隨著人工智能以及大數(shù)據(jù)的發(fā)展，應(yīng)用程序運(yùn)行時(shí)造成的開銷也呈現(xiàn)爆炸性增長(zhǎng)，這對(duì)于資源受限的移動(dòng)終端帶來了巨大的壓力。移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）被視為解決終端設(shè)備壓力的重要技術(shù)［1-2］，通過將任務(wù)卸載到具有豐富計(jì)算資源的邊緣服務(wù)器上進(jìn)行處理，能夠有效提高移動(dòng)終端的任務(wù)處理效率，同時(shí)還能夠減小終端的能量損耗［3］。

學(xué)術(shù)界對(duì)MEC 技術(shù)進(jìn)行了廣泛的研究。文獻(xiàn)［4］針對(duì)單邊緣服務(wù)器卸載時(shí)導(dǎo)致異地邊緣服務(wù)器空閑狀態(tài)下資源浪費(fèi)問題，在云服務(wù)器與多個(gè)邊緣服務(wù)器聯(lián)合卸載的方案下，提出一種基于改進(jìn)混合粒子群算法的邊緣云協(xié)同計(jì)算卸載策略。文獻(xiàn)［5］針對(duì)超密集組網(wǎng)（Ultra-dense Networks，UDN）的MEC 場(chǎng)景下的計(jì)算卸載場(chǎng)景，以任務(wù)卸載決策、信道分配決策和功率分配決策為優(yōu)化變量，提出了以用戶總能耗為優(yōu)化目標(biāo)的資源分配算法。文獻(xiàn)［6］研究了任務(wù)存在依賴關(guān)系的場(chǎng)景下的計(jì)算卸載問題，提出了一種基于強(qiáng)化學(xué)習(xí)（Reinforcement Learning，RL）的無模型方法，旨在最小化受能耗約束的移動(dòng)應(yīng)用程序的執(zhí)行時(shí)間。文獻(xiàn)［7］考慮了異構(gòu)網(wǎng)絡(luò)中無線回程鏈路場(chǎng)景下的計(jì)算卸載問題，作者假設(shè)用戶通過小基站與宏基站之間的無線回程鏈路傳輸將任務(wù)卸載到與宏基站相連的MEC 服務(wù)器上，通過優(yōu)化用戶任務(wù)卸載決策、服務(wù)器計(jì)算資源分配決策以及信道資源分配決策最小化所有用戶的總開銷。文獻(xiàn)［8］研究了具有數(shù)據(jù)壓縮的多用戶MEC 系統(tǒng)的節(jié)能計(jì)算卸載。在任務(wù)卸載之前，對(duì)數(shù)據(jù)進(jìn)行壓縮以減小數(shù)據(jù)大小。在延遲約束條件下，考慮MEC 計(jì)算能力有限，通過聯(lián)合優(yōu)化計(jì)算卸載、數(shù)據(jù)壓縮和資源分配來最小化能量消耗的問題。文獻(xiàn)［9］提出了一種基于深度強(qiáng)化學(xué)習(xí)的節(jié)能算法來優(yōu)化實(shí)時(shí)多用戶MEC 系統(tǒng)的能耗。在多用戶部分卸載場(chǎng)景下，形成了用戶任務(wù)卸載比例與資源分配的非凸優(yōu)化問題，為解決該問題，作者將能量最小化問題分解為任務(wù)卸載比例子問題和資源分配子問題，利用深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)無線信道和卸載比之間的最優(yōu)映射，并使用最優(yōu)本地計(jì)算資源分配決策的閉式解和凸優(yōu)化算法求解資源分配子問題。在車聯(lián)網(wǎng)場(chǎng)景下，文獻(xiàn)［10］考慮了由于車輛不同速度引起的通信環(huán)境的變化，通過聯(lián)合優(yōu)化多輛車的卸載比例和上行/計(jì)算/下行比特分配，使車輛在延遲約束下的總能量消耗最小化。在異構(gòu)云（包括邊緣云和遠(yuǎn)程云）場(chǎng)景下，為了進(jìn)一步降低移動(dòng)終端設(shè)備的能耗，提高計(jì)算資源的利用率，文獻(xiàn)［11］提出了一種多計(jì)算資源協(xié)同任務(wù)卸載模型，并設(shè)計(jì)了該模型的適應(yīng)度計(jì)算方法，提出了一種基于粒子群優(yōu)化算法的多計(jì)算資源協(xié)同能量?jī)?yōu)化算法。

上述文獻(xiàn)研究了MEC 中的計(jì)算卸載問題，然而MEC 的實(shí)施依賴于蜂窩網(wǎng)絡(luò)的部署，在用戶密集分布的場(chǎng)景下或者基站弱覆蓋區(qū)域，邊緣計(jì)算的增益效果將大大降低［12］，因此業(yè)界提出了基于設(shè)備到設(shè)備（Device-to-Device，D2D）通信的計(jì)算卸載方案。文獻(xiàn)［13］提出了一種面向聯(lián)合學(xué)習(xí)的D2D 計(jì)算任務(wù)卸載方案，作者考慮不同邊緣節(jié)點(diǎn)通過D2D通信交換數(shù)據(jù)樣本，平衡節(jié)點(diǎn)的處理能力和任務(wù)負(fù)載，以最小化聯(lián)合學(xué)習(xí)模型訓(xùn)練過程的總時(shí)延。文獻(xiàn)［14］以最小化MEC 網(wǎng)絡(luò)的任務(wù)延遲和終端能耗為目標(biāo)，通過建立多目標(biāo)約束的成本優(yōu)化模型，提出了D2D 輔助MEC 網(wǎng)絡(luò)中考慮任務(wù)卸載和計(jì)算資源分配的聯(lián)合優(yōu)化問題。文獻(xiàn)［15］提出了一種基于網(wǎng)絡(luò)輔助D2D 協(xié)作的新型移動(dòng)任務(wù)卸載框架，移動(dòng)用戶通過網(wǎng)絡(luò)運(yùn)營(yíng)商的控制輔助，可以動(dòng)態(tài)、有益地共享計(jì)算和通信資源。作者旨在最小化所有用戶的任務(wù)執(zhí)行的單位時(shí)間能耗，同時(shí)提出了有效的激勵(lì)機(jī)制防止用戶過度占用公共資源和自私行為的發(fā)生?？紤]到終端的移動(dòng)性、用戶的自私性和信息卸載不完整等因素，文獻(xiàn)［16］在D2D 輔助的MEC 網(wǎng)絡(luò)提出了一種整合遷移成本和卸載意愿的協(xié)同卸載框架。文獻(xiàn)［17］研究了D2D 輔助MEC 的多用戶聯(lián)合協(xié)同部分卸載、傳輸調(diào)度分配和計(jì)算分配問題?？紤]隨機(jī)的應(yīng)用程序請(qǐng)求、不可預(yù)測(cè)的MΤs 狀態(tài)、時(shí)變的信道狀態(tài)和計(jì)算資源，建立了一個(gè)定制的應(yīng)用程序卸載模型，旨在同時(shí)最小化網(wǎng)絡(luò)范圍內(nèi)的響應(yīng)延遲和能量消耗。文獻(xiàn)［18］假設(shè)部分用戶有任務(wù)計(jì)算需求，并可以執(zhí)行本地計(jì)算、MEC 卸載或D2D 卸載，任務(wù)可以劃分為小數(shù)據(jù)，并可以通過各種計(jì)算模式同時(shí)執(zhí)行，在此場(chǎng)景下研究了計(jì)算卸載和資源分配問題，提出了一種能夠?qū)崿F(xiàn)有效的信息交互和任務(wù)管理的聯(lián)合任務(wù)管理體系結(jié)構(gòu)。文獻(xiàn)［19］將D2D 與MEC 結(jié)合以進(jìn)一步提高蜂窩網(wǎng)絡(luò)的計(jì)算容量，考慮用戶任務(wù)可以同時(shí)進(jìn)行D2D 卸載與MEC 卸載，通過優(yōu)化D2D 設(shè)備匹配與MEC 計(jì)算資源分配以最大化蜂窩網(wǎng)絡(luò)能支持的最大設(shè)備數(shù)。上述文獻(xiàn)考慮了基于D2D 通信輔助的計(jì)算卸載場(chǎng)景，然而并沒有著重研究D2D 場(chǎng)景下用戶之間的利益競(jìng)爭(zhēng)問題。在基于D2D 模式的計(jì)算卸載場(chǎng)景下，用戶自身的自私屬性以及移動(dòng)設(shè)備有限的計(jì)算資源都會(huì)影響到用戶之間的協(xié)作積極性，因此有必要對(duì)用戶之間的利益競(jìng)爭(zhēng)關(guān)系進(jìn)行研究，通過合適的策略激勵(lì)用戶參與協(xié)作計(jì)算。

本文在多用戶場(chǎng)景下對(duì)用戶的計(jì)算卸載問題進(jìn)行了研究。聯(lián)合考慮具有計(jì)算需求的用戶與能夠提供計(jì)算服務(wù)的空閑用戶雙方的利益競(jìng)爭(zhēng)關(guān)系，提出了一種基于D2D 通信的計(jì)算卸載與資源分配算法，該算法通過對(duì)需求用戶的任務(wù)卸載決策和計(jì)算資源租賃單價(jià)決策以及空閑用戶的計(jì)算資源分配決策進(jìn)行優(yōu)化，以最大化需求用戶與空閑用戶的效用。針對(duì)需求用戶的計(jì)算資源租賃單價(jià)決策和空閑用戶的計(jì)算資源分配決策，提出了基于斯坦柯爾伯格博弈（Stackelberg Game）的優(yōu)化算法，針對(duì)需求用戶的任務(wù)卸載決策，提出了基于遺傳算法的優(yōu)化算法，仿真結(jié)果表明，本文算法能夠有效提高需求用戶與空閑用戶的效用。

本文剩余內(nèi)容安排如下：第二部分給出了多用戶單任務(wù)場(chǎng)景下的計(jì)算卸載系統(tǒng)模型；第三部分將給定需求用戶計(jì)算卸載決策下各方用戶的利益競(jìng)爭(zhēng)問題搭建為Stackelberg 博弈模型；第四部分給出了Stackelberg 博弈均衡求解算法以及需求用戶的任務(wù)卸載決策優(yōu)化算法；第五部分進(jìn)行了算法的仿真與分析；第六部分進(jìn)行了總結(jié)。

2 系統(tǒng)模型

2.1 卸載模型

基于D2D 通信的計(jì)算卸載模型如圖1 所示。在當(dāng)前任務(wù)周期內(nèi)，將基站覆蓋范圍內(nèi)的移動(dòng)用戶分為兩類，一類是具有任務(wù)計(jì)算需求的需求用戶，另一類是無任務(wù)需要處理且能夠?qū)ν馓峁┯?jì)算資源的空閑用戶。假設(shè)需求用戶的總?cè)藬?shù)為N，用集合Ν={1，2，…，n，…，N}表示，空閑用戶的總?cè)藬?shù)為I，用集合Ι={1，2，…，i，…，I}表示。假設(shè)每個(gè)需求用戶有一個(gè)計(jì)算密集型任務(wù)，用戶n的任務(wù)可用{Cn，Dn，Ln}表示，其中Cn表示計(jì)算任務(wù)所需要的CPU 執(zhí)行周期，Dn表示任務(wù)的數(shù)據(jù)量大小，Ln表示任務(wù)的最大容忍延遲。Cn與Dn之間滿足關(guān)系Cn=κnDn，其中κn計(jì)算每比特?cái)?shù)據(jù)量的任務(wù)所需要的CPU 周期數(shù)，反映了任務(wù)計(jì)算的復(fù)雜度。對(duì)于任意需求用戶的任務(wù)，用戶可以選擇將任務(wù)在本地終端設(shè)備上處理，也可以將任務(wù)以整體卸載的方式卸載到空閑用戶終端上進(jìn)行處理，并支付一定的費(fèi)用給空閑用戶，用戶之間進(jìn)行D2D 時(shí)不存在信道干擾。xn，loc表示需求用戶n任務(wù)本地執(zhí)行的標(biāo)志，如果xn，loc=1，則表示用戶n選擇將任務(wù)置于本地執(zhí)行，如果xn，loc=0，則表示用戶n選擇將任務(wù)進(jìn)行卸載。xn，i表示需求用戶n與空閑用戶i的D2D 卸載標(biāo)志，如果xn，i=1，則表示用戶n選擇將任務(wù)卸載到空閑用戶i的終端上處理，如果xn，i=0，則表示用戶n選擇將任務(wù)卸載到空閑用戶處理。假設(shè)每個(gè)空閑用戶最多只能處理一個(gè)任務(wù)，即對(duì)于任意空閑用戶i?Ι，均滿足

圖1 基于D2D通信的計(jì)算卸載模型Fig.1 D2D communication-based computation offloading system

2.2 開銷模型

為了提高用戶體驗(yàn)，本文聯(lián)合考慮了任務(wù)完成時(shí)延，終端能耗以及可能涉及到的任務(wù)卸載費(fèi)用等多方面的用戶開銷。同時(shí)也考慮了空閑用戶在協(xié)作計(jì)算卸載過程中的收益，并建立了Stackelberg 模型，以最大化多方的利益。對(duì)于需求用戶n而言，其任務(wù)具有兩種處理模式，分別是本地執(zhí)行和卸載到空閑用戶終端上執(zhí)行。下面針對(duì)這兩種模式對(duì)需求用戶n的開銷進(jìn)行分析。

（1）本地執(zhí)行

對(duì)于需求用戶n，若其任務(wù)在本地執(zhí)行，則設(shè)備消耗的能耗En，loc可以表示為［20］

其中，αn為用戶n終端設(shè)備能耗系數(shù)，該值與設(shè)備CPU的結(jié)構(gòu)有關(guān)。fn為用戶n終端本地的計(jì)算能力。

用戶任務(wù)的處理完成時(shí)延Tn，loc可以表示為

（2）D2D卸載

如果需求用戶n選擇將任務(wù)卸載到空閑用戶i終端上處理，則用戶n終端的能耗為發(fā)送任務(wù)所需要的通信能耗。需要說明的是，由于任務(wù)處理結(jié)果一般數(shù)據(jù)量較小，因此本文不考慮設(shè)備接收任務(wù)處理結(jié)果需要消耗的能量。在此情況下，設(shè)備消耗的能耗En，i可以表示為

其中，Pn表示用戶n終端設(shè)備的發(fā)射功率。Rn，i表示用戶n與用戶i的信息傳輸速率，Rn，i具體表示為

其中，Wn，i表示用戶n終端與用戶i終端之間的可用信道帶寬，hn，i表示用戶n終端與用戶i終端之間的信道增益，σ2表示加性高斯白噪聲功率。

在D2D 卸載模式下，用戶任務(wù)的處理完成時(shí)延Tn由兩部分組成，分別是任務(wù)傳輸至用戶i終端的時(shí)延與用戶i終端計(jì)算任務(wù)的時(shí)延，因此，Tn，i可以表示為

其中，fi，n表示用戶i向用戶n提供的計(jì)算能力。

為激勵(lì)空閑用戶參與協(xié)作計(jì)算，用戶n在向用戶i卸載任務(wù)的同時(shí)需要支付一定的費(fèi)用作為任務(wù)計(jì)算酬金。假設(shè)用戶n以單價(jià)租賃的方式占用空閑用戶i終端的計(jì)算資源，用pn，i表示用戶n向用戶i給出的計(jì)算資源租賃單價(jià)，則用戶n需要向用戶i支付的費(fèi)用可以表示為

在協(xié)作計(jì)算中，空閑用戶終端的開銷為計(jì)算任務(wù)消耗的能量，其中任意空閑用戶i的能耗可以表示為

其中，αi為空閑用戶i終端設(shè)備的能耗因子，該參數(shù)與設(shè)備CPU的結(jié)構(gòu)有關(guān)。

2.3 效用函數(shù)

本文定義需求用戶的效用為相較于本地計(jì)算模式下的用戶總開銷的減小值，聯(lián)合考慮任務(wù)完成時(shí)延，用戶終端設(shè)備能耗以及計(jì)算資源租賃費(fèi)用等三方面的用戶開銷，則需求用戶n的效用函數(shù)定義為：

其中，λn表示任務(wù)在最大容忍延遲內(nèi)完成帶來的收益因子，如果任務(wù)Tn

定義空閑用戶的效用為除去開銷后協(xié)作需求用戶計(jì)算任務(wù)所獲得的收益，對(duì)于任務(wù)空閑用戶i，其效用函數(shù)可表示為

其中，ηi為能耗加權(quán)因子，反映了空閑用戶對(duì)能耗的重視程度。

3 Stackelberg博弈模型

本節(jié)聯(lián)合考慮協(xié)作計(jì)算中需求用戶與空閑用戶多方的利益，首先根據(jù)各方的效用函數(shù)構(gòu)建了相應(yīng)的優(yōu)化問題，接下來結(jié)合卸載方（需求用戶）與服務(wù)方（空閑用戶）之間的相互作用關(guān)系，建立了Stackelberg 博弈模型。在Stackelberg 博弈模型中，需求用戶作為領(lǐng)導(dǎo)層，空閑用戶為從屬層。領(lǐng)導(dǎo)層根據(jù)任務(wù)卸載決策對(duì)計(jì)算資源租賃單價(jià)具有優(yōu)先報(bào)價(jià)權(quán)，從屬層根據(jù)需求用戶提供的計(jì)算資源租賃單價(jià)決定提供的計(jì)算資源大小，使得自身目標(biāo)效用最大化，雙方基于計(jì)算資源租賃單價(jià)與可提供計(jì)算資源進(jìn)行博弈。

3.1 優(yōu)化問題

對(duì)于任意需求用戶n，其在計(jì)算卸載過程中的決策包括任務(wù)卸載決策{xn，loc，xn，i}和計(jì)算資源租賃單價(jià)pn，i，其中i?Ι。用戶n的優(yōu)化問題可以表示為

其中，約束C1 表示用戶任務(wù)只能在一處執(zhí)行，約束C2 規(guī)定了計(jì)算資源租賃單價(jià)的上下限，表示用戶n計(jì)算資源租賃單價(jià)的下界，表示用戶n計(jì)算資源租賃單價(jià)的上界。

對(duì)于任意空閑用戶i，其在協(xié)作計(jì)算過程中的決策為向需求用戶提供的計(jì)算資源，用戶i的優(yōu)化問題可以表述為

其中，約束C3 表示用戶i為需求用戶提供的計(jì)算資源不能超過設(shè)備限制。

3.2 Stackelberg博弈均衡

假設(shè)每個(gè)需求用戶以整體卸載的方式進(jìn)行任務(wù)卸載，為了提高空閑用戶參與協(xié)作計(jì)算的積極性，考慮需求用戶與空閑用戶之間以博弈論的方法進(jìn)行計(jì)算資源議價(jià)，作為領(lǐng)導(dǎo)層，需求用戶在任務(wù)卸載決策決定方面具有絕對(duì)主導(dǎo)權(quán)。考慮在給定需求用戶的任務(wù)卸載決策{xn，loc，xn，i}基礎(chǔ)上，對(duì)需求用戶與空閑用戶的剩余變量進(jìn)行優(yōu)化，使得雙方在此基礎(chǔ)之上的效用最大化。本文對(duì)于Stackelberg博弈均衡的定義如下：

定義1（Stackelberg 博弈均衡）假設(shè)x={xn，loc，xn，i}n?Ν表示當(dāng)前所有需求用戶的任務(wù)卸載決策，為需求用戶n的最優(yōu)計(jì)算資源租賃單價(jià)決策，表示空閑用戶i的最優(yōu)計(jì)算資源決策。在所有的解情況中，Stackelberg 博弈均衡可以表示為)，該均衡點(diǎn)滿足以下條件：

定理1給定所有需求用戶的卸載決策x={xn，loc，xn，i}n?Ν，需求用戶與空閑用戶的決策存在唯一納什均衡。

證明：

對(duì)于空閑用戶i，假設(shè)需求用戶n的任務(wù)卸載決策xn，i=1，則用戶i受需求用戶計(jì)算資源租賃單價(jià)影響下的效用函數(shù)可以表示為

對(duì)上式求導(dǎo)分別得到其一階導(dǎo)函數(shù)與二階導(dǎo)函數(shù)如下：

將需求用戶的計(jì)算資源租賃單價(jià)變化區(qū)間邊界值分別對(duì)應(yīng)fi，n=0與fi，n=Fi的情況，得到

對(duì)任意需求用戶n，其最優(yōu)決策必定在與之間，所以空閑用戶的最優(yōu)決策可以表示為

對(duì)上式求導(dǎo)分別得到其一階導(dǎo)函數(shù)與二階導(dǎo)函數(shù)如下：

故在給定所有用戶的任務(wù)卸載決策x={xn，loc，xn，i}n?Ν下，Stackelberg 博弈存在唯一納什均衡，證畢。

4 博弈算法與卸載決策

本節(jié)針對(duì)需求用戶與空閑用戶的優(yōu)化問題提出了相應(yīng)的求解算法。在給定需求用戶任務(wù)卸載決策下，針對(duì)計(jì)算卸載中卸載方（需求用戶）與服務(wù)方（空閑用戶）之間的利益博弈問題提出了納什均衡求解算法，以兼顧各方的效用。針對(duì)需求用戶的任務(wù)卸載決策問題，提出了基于遺傳算法的啟發(fā)式優(yōu)化算法，以提高需求用戶的收益。

4.1 納什均衡求解算法

如算法1 所示，在算法起始階段，首先需要輸入當(dāng)前所有需求用戶的任務(wù)卸載決策x={xn，loc，xn，i}n?Ν，因?yàn)槿蝿?wù)卸載決策下將會(huì)影響到納什均衡結(jié)果。在初始化階段，令當(dāng)前迭代周期τ=0，并規(guī)定算法迭代收斂的精度需求ε，假設(shè)當(dāng)所有需求用戶的效用總和滿足時(shí)，算法迭代終止。將所有需求用戶的起始計(jì)算資源租賃單價(jià)設(shè)為po，其中的具體值可以由公式（19）和（20）計(jì)算得出。在{pn，i}n?Ν=po的基礎(chǔ)上，可以根據(jù)公式（21）求出當(dāng)前空閑用戶的最優(yōu)決策{fi，n}i?Ι，并結(jié)合公式（9）計(jì)算出當(dāng)前各需求用戶的效用{Un(τ)}n?Ν。如算法1步驟7～14 所示，在每次算法循環(huán)迭代過程中，首先對(duì)當(dāng)前迭代周期進(jìn)行操作τ=τ+1，如果需求用戶選擇在本地終端處理任務(wù)，則只需要根據(jù)公式（9）計(jì)算出用戶效用。針對(duì)將任務(wù)卸載到空閑用戶終端的用戶，根據(jù)公式（25）對(duì)其計(jì)算資源租賃單價(jià)決策進(jìn)行變更，緊接著根據(jù)公式（21）對(duì)相應(yīng)空閑用戶的決策進(jìn)行變更，并根據(jù)公式（9）計(jì)算出當(dāng)前需求用戶本迭代周期內(nèi)的效用。當(dāng)算法迭代終止時(shí)，此時(shí)的{pn，i}n?Ν與{fi，n}i?Ι即為給定需求用戶任務(wù)卸載下各用戶的最優(yōu)決策，記作)。需要說明的是，由公式（25）可知，給定需求用戶任務(wù)卸載決策下，需求用的最優(yōu)計(jì)算資源租賃單價(jià)決策是固定的，因此經(jīng)過兩輪報(bào)價(jià)后，需求用戶與空閑用戶的決策即可收斂至納什均衡點(diǎn)，算法1 的時(shí)間復(fù)雜度為o（N）。

4.2 任務(wù)卸載決策優(yōu)化算法

在算法1 的基礎(chǔ)上，在給定所有需求用戶的卸載決策下，可以求解出需求用戶與空閑用戶形成的Stackelberg 博弈問題的納什均衡解，從而有效提高各方在計(jì)算卸載過程中的收益。當(dāng)需求用戶的任務(wù)卸載決策變化時(shí)，算法1求解出的結(jié)果也隨之變化，這意味著需求用戶的效用會(huì)受到自身任務(wù)卸載決策的影響，為了優(yōu)化所有需求用戶的任務(wù)卸載決策，本文給出了基于遺傳算法的任務(wù)卸載決策優(yōu)化算法，以進(jìn)一步提高需求用戶的收益，具體見算法2。

如算法2所示，在算法初始化階段，首先對(duì)遺傳算法的相關(guān)參數(shù)進(jìn)行初始化，具體包括種群的個(gè)體數(shù)量，最大遺傳進(jìn)化次數(shù)，每次進(jìn)化產(chǎn)生新個(gè)體數(shù)量和個(gè)體變異概率?？紤]到每個(gè)需求用戶的任務(wù)具有兩種執(zhí)行方式，即本地執(zhí)行和D2D 卸載，故對(duì)任意用戶n，其任務(wù)卸載決策可以用包含I+1的元素的一維向量xn={xn，loc，xn，1，xn，2，???，xn，i，???，xn，I}表示，則種群中個(gè)體的基因型可以用如圖2 表示。值得說明的是，在將任務(wù)卸載決策映射為種群中個(gè)體時(shí)必須保證所有需求用戶的任務(wù)決策滿足條件（1）和C1，即需求用戶的任務(wù)只能選擇在一臺(tái)設(shè)備上執(zhí)行且每個(gè)空閑用戶最多只能接收一個(gè)任務(wù)。

圖2 任務(wù)卸載決策編碼示意圖Fig.2 Τask offloading decision encoding diagram

初始化階段完成后，算法開始執(zhí)行迭代。在種群的每一次進(jìn)化周期（即算法迭代周期）內(nèi)，首先對(duì)種群執(zhí)行交叉操作，具體執(zhí)行方式為從種群按照適應(yīng)度優(yōu)先的準(zhǔn)則挑選兩個(gè)個(gè)體作為父代，個(gè)體的適應(yīng)度越大，則從種群中被選中的概率越大。種群在初始化時(shí)，假設(shè)所有個(gè)體的適應(yīng)度相同。父代個(gè)體在執(zhí)行交叉操作之前會(huì)首先確定交叉位置θ，θ為區(qū)間1 ≤θ≤N-1內(nèi)的隨機(jī)值，在交叉位置θ的基礎(chǔ)上，父代個(gè)體執(zhí)行交叉操作的具體方法如圖3所示。

圖3 交叉操作示意圖Fig.3 Crossover-operation diagram

由于交叉位置具有隨機(jī)性，因此產(chǎn)生的子代個(gè)體基因型對(duì)應(yīng)的任務(wù)卸載決策可能不滿足約束（1）和C1，所以有必要對(duì)新產(chǎn)生的子代個(gè)體進(jìn)行校正，校正步驟如下：

（1）針對(duì)所有空閑用戶i，判斷是否 大于1，如果是，找出卸載標(biāo)志為1 的兩個(gè)需求用戶n1和n2，隨機(jī)確定n?{n1，n2}，令xn，i=0。

（2）針對(duì)所有需求用戶n，判斷是否大于1，如果是，找出卸載標(biāo)志為1 的兩個(gè)空閑用戶i1和i2，隨機(jī)確定i?{i1，i2}，令xn，i=0。

（3）針對(duì)所有需求用戶n，判斷是否等于0，如果是，則找出當(dāng)前沒有接收任務(wù)的空閑用戶，隨機(jī)將需求用戶與空閑用戶進(jìn)行匹配，在此過程中，需求用戶也可選擇將任務(wù)置于本地執(zhí)行。

執(zhí)行完上述步驟后，即可將子代個(gè)體納入種群中，當(dāng)產(chǎn)生新個(gè)體數(shù)量為時(shí)，種群開始進(jìn)入變異階段。

圖4 變異操作示意圖Fig.4 Mutation-operation diagram

在交叉操作與變異操作執(zhí)行完成后，對(duì)將每個(gè)個(gè)體轉(zhuǎn)換為需求任務(wù)的任務(wù)卸載決策x={xn，loc，xn，i}n?Ν，根據(jù)算法1，可求出需求用戶的最優(yōu)計(jì)算資源租賃單價(jià)決策與空閑用戶的最優(yōu)計(jì)算資源提供決策，結(jié)合公 式（9）可進(jìn)一步求出需求用戶的效用總和，將此效用值記作當(dāng)前個(gè)體的適應(yīng)度，在選擇階段，根據(jù)個(gè)體適應(yīng)度大小，挑選出適應(yīng)度最高的個(gè)個(gè)體作為下一進(jìn)化周期的種群。當(dāng)算法達(dá)到最大迭代周期時(shí)，輸出此時(shí)種群中適應(yīng)度最高的個(gè)體基因型對(duì)應(yīng)的任務(wù)卸載決策，即為需求用戶的最終任務(wù)卸載決策x*。算法2的迭代次數(shù)由種群進(jìn)化次數(shù)決定，在每個(gè)迭代周期內(nèi)，交叉操作與變異操作的語(yǔ)句執(zhí)行頻次處于小于的常數(shù)量級(jí)，算法2 的執(zhí)行頻次為1，故算法2的時(shí)間復(fù)雜度為o（N）。

5 仿真與分析

本文采用MAΤLAB對(duì)提出算法進(jìn)行仿真，以驗(yàn)證其有效性。假設(shè)需求用戶和空閑用戶的位置隨機(jī)生成，D2D 通信的最大通信距離為50 m，各通信鏈路之間的信道衰落根據(jù)大尺度衰落模型hA，B=計(jì)算，其中k為信道衰落系數(shù)，dA，B為通信節(jié)點(diǎn)A和B之間的空間距離，λ為信道衰落指數(shù)。其他相關(guān)參數(shù)如表1所示［21］。

表1 仿真參數(shù)Tab.1 Simulation parameters

為了進(jìn)行性能分析，本文將所提出的算法與隨機(jī)算法和文獻(xiàn)［22］中的算法在相同參數(shù)設(shè)置下進(jìn)行比較。其中，隨機(jī)算法是指對(duì)任意需求用戶n，其任務(wù)卸載決策{xn，i}i?Ι和計(jì)算資源租賃單價(jià){pn，i}i?Ι在取值范圍內(nèi)隨機(jī)生成，對(duì)于任意空閑用戶i，其計(jì)算資源決策{fi，n}n?Ν同樣在取值范圍內(nèi)隨機(jī)產(chǎn)生。文獻(xiàn)［22］采用圖論方法對(duì)任務(wù)卸載以及資源分配進(jìn)行優(yōu)化，且不考慮需求用戶與空閑用戶之間的利益競(jìng)爭(zhēng)關(guān)系。

圖5 和圖6 給出了本文提出的算法與隨機(jī)算法在不同任務(wù)計(jì)算量下的用戶總效用對(duì)比圖。其中圖5 給出了需求用戶總效用的對(duì)比圖，圖6 給出了空閑用戶的效用對(duì)比圖。假設(shè)需求用戶與空閑用戶的數(shù)量都為10，需求用戶的本地計(jì)算能力為{fn}n?Ν=2 GHz，隨機(jī)算法下的用戶效用為算法執(zhí)行1000 次的平均結(jié)果。由圖5 可以看出，在不同任務(wù)計(jì)算量{Cn}n?Ν下，相比較于其他兩種算法，本文算法都能有效提高需求用戶的收益，這是因?yàn)楸疚牟捎肧tackelberg博弈模型對(duì)需求用戶與空閑用戶之間的利益競(jìng)爭(zhēng)關(guān)系進(jìn)行了建模分析，通過求解納什均衡得到了需求用戶與空閑用戶的最優(yōu)決策，能夠有效提高用戶的效用。隨機(jī)算法下的空閑用戶與需求用戶在進(jìn)行決策時(shí)具有隨機(jī)性，無法保證需求用戶根據(jù)信道傳輸環(huán)境、空閑用戶設(shè)備能耗因子以及空閑用戶的能耗加權(quán)因子做出合理的任務(wù)卸載決策和計(jì)算資源租賃單價(jià)決策，因此在性能上不如本文算法。文獻(xiàn)［22］算法沒有考慮需求用戶與空閑用戶之間決策的相互作用關(guān)系，僅能夠保證需求用戶根據(jù)當(dāng)前環(huán)境做出合理的任務(wù)卸載決策，但是不能夠通過調(diào)整計(jì)算資源租賃單價(jià)決策以進(jìn)一步提高自身效用。同時(shí)可以看出，隨著任務(wù)計(jì)算量的增加，用戶的效用也隨之增加，這是因?yàn)楫?dāng)任務(wù)計(jì)算量增加時(shí)，需求用戶可以通過將任務(wù)卸載向空閑用戶，以節(jié)省更多的能量，因此用戶效用呈上升趨勢(shì)。

圖5 需求用戶總收益隨任務(wù)計(jì)算所需CPU周期數(shù)對(duì)比圖Fig.5 Comparison of total utility of demand users versus the number of CPU cycles required for task calculation

圖6 空閑用戶總收益隨任務(wù)計(jì)算所需CPU周期數(shù)對(duì)比圖Fig.6 Comparison of total utility of idle users versus the number of CPU cycles required for task calculation

由圖6可以看出，與其他算法相比，在不同需求用戶任務(wù)計(jì)算量{Cn}n?Ν下，本文算法能夠有效提高空閑用戶的收益。這是因?yàn)?，本文算法將凸?yōu)化理論應(yīng)用于空閑用戶的決策過程，能夠在給定需求用戶的計(jì)算資源租賃單價(jià)下求出空閑用戶的最優(yōu)決策，從而為空閑用戶帶來更高的效用，而隨機(jī)算法和文獻(xiàn)［22］算法無法保證空閑用戶根據(jù)需求用戶的決策做出最優(yōu)計(jì)算資源分配決策，由圖中可以看出，隨著需求用戶任務(wù)計(jì)算量的增加，空閑用戶的效用也隨之增加，這是因?yàn)楫?dāng)需求用戶任務(wù)計(jì)算量增加時(shí)，需求用戶愿意給出更高的計(jì)算資源租賃單價(jià)以減少自身能耗開銷，空閑用戶也因此能夠獲得更高的收益。

圖7 和圖8 給出了不同空閑用戶與需求用戶數(shù)量比例下的用戶總效用對(duì)比圖。其中圖7給出了需求用戶總效用的對(duì)比圖，圖8 給出了空閑用戶的效用對(duì)比圖。由圖7 可以看出，隨著空閑用戶在人群中的占比增大時(shí)，需求用戶的總收益呈現(xiàn)遞增趨勢(shì)，這是因?yàn)?，?dāng)空閑用戶的數(shù)量增加時(shí)，更多的需求用戶可以通過D2D 的方式進(jìn)行任務(wù)卸載，從而降低了需求用戶終端的能耗開銷，在一定程度上提高了需求用戶的效用。同時(shí)可以看出，與隨機(jī)算法相比，在不同空閑用戶占比下，本文算法能夠有效提高需求用戶的總收益，這是因?yàn)?，無論空閑用戶數(shù)量占比高低，本文算法都能夠根據(jù)當(dāng)前環(huán)境為需求用戶求解出合理的任務(wù)卸載決策。

圖7 不同空閑用戶與需求用戶數(shù)量比例下的需求用戶效用對(duì)比圖Fig.7 Comparison of total utilities of demand users under different ratios of idle users to demand users

圖8 不同空閑用戶與需求用戶數(shù)量比例下的空閑用戶效用對(duì)比圖Fig.8 Comparison of total utilities of idle users under different ratios of idle users to demand users

由圖8 可以看出，隨著空閑用戶在人群中的占比增大時(shí)，空閑用戶的總收益也隨之增加，這是因?yàn)?，?dāng)空閑用戶的數(shù)量增加時(shí)，更多的需求用戶將任務(wù)交由空閑用戶處理，空閑用戶在協(xié)作計(jì)算過程中的總收益增加。由圖中可以看出，隨著需求用戶任務(wù)計(jì)算所需要的CPU 周期數(shù)增加，空閑用戶的效用也隨之增加，這是因?yàn)?，任?wù)計(jì)算所需要的CPU周期數(shù)的增加會(huì)使得需求用戶在決策出的計(jì)算資源租賃單價(jià)更高，結(jié)合公式（21）和（25）可知，空閑用戶將獲得更高的收益。

圖9 和圖10 給出了不同空閑用戶能耗重視因子ηi下的用戶總效用對(duì)比圖。其中圖9給出了需求用戶總效用的對(duì)比圖，圖10給出了空閑用戶的效用對(duì)比圖。由圖9 可以看出，隨著空閑用戶能耗重視因子ηi的增大，需求用戶的總效用呈現(xiàn)下降趨勢(shì)，這是因?yàn)?，?dāng)空閑用戶的能耗重視因子ηi增大時(shí)，給定需求用戶的計(jì)算資源租賃單價(jià)下，空閑用戶愿意提供的計(jì)算資源減少，從而導(dǎo)致需求用戶的任務(wù)處理時(shí)延開銷增加，需求用戶的效用也因此降低。

圖9 不同空閑用戶能耗加權(quán)因子下的需求用戶效用對(duì)比圖Fig.9 Comparison of total utilities of demand users under different energy-consumption-weighting factors for idle users

圖10 不同空閑用戶能耗加權(quán)因子下的空閑用戶效用對(duì)比圖Fig.10 Comparison of total utilities of idle users under different energy-consumption-weighting factors for idle users

由圖10可以看出，隨著空閑用戶能耗重視因子ηi的增大，空閑用戶的總效用呈現(xiàn)上升趨勢(shì)。由公式（21）可知，空閑用戶能耗重視因子ηi越大，當(dāng)需求用戶的計(jì)算資源租賃單價(jià)固定時(shí)，空閑用戶提供的計(jì)算資源越少，從而減少了協(xié)作計(jì)算中的能耗開銷，同時(shí)，由公式（25）可知，更高的能耗重視因子ηi會(huì)使得需求用戶制定更高的計(jì)算資源租賃單價(jià)，因此空閑用戶的效用會(huì)隨著能耗重視因子ηi的增加而增加。

6 結(jié)論

本文在多用戶場(chǎng)景下，將用戶劃分為有任務(wù)計(jì)算需求的需求用戶和能夠提供計(jì)算資源的空閑用戶，并分別分析了兩種用戶在計(jì)算卸載過程中的開銷，構(gòu)建了各方的效用函數(shù)。提出了分層結(jié)構(gòu)的計(jì)算卸載與資源分配算法，其中內(nèi)層采用Stackelberg博弈模型將需求用戶與空閑用戶之間的利益競(jìng)爭(zhēng)關(guān)系進(jìn)行建模，通過動(dòng)態(tài)迭代算法求解出了該博弈模型的納什均衡解，外層采用遺傳算法對(duì)需求用戶的任務(wù)卸載決策進(jìn)行了優(yōu)化。最后，本文通過MAΤLAB 仿真工具對(duì)本文算法進(jìn)行了仿真。仿真結(jié)果表明，與隨機(jī)算法相比，本文算法能夠有效提高需求用戶與空閑用戶的效用。