能量收集下的D2D-MEC 計(jì)算卸載

曾耀平，劉月強(qiáng)，關(guān)賽莘，江偉偉，夏玉婷

(西安郵電大學(xué) 通信與信息工程學(xué)院，陜西 西安 710121)

在5G 和人工智能快速發(fā)展下，計(jì)算密集型和潛在關(guān)鍵型應(yīng)用急劇增加(如虛擬現(xiàn)實(shí)、自動(dòng)駕駛和大規(guī)模實(shí)時(shí)視頻監(jiān)控)[1-2].由于設(shè)備資源和計(jì)算能力有限，難以滿足這些應(yīng)用程序的計(jì)算需求.D2DMEC(device-to-device mobile edge computing)技術(shù)應(yīng)運(yùn)而生，它整合了移動(dòng)邊緣計(jì)算與D2D 通信技術(shù)[3]，旨在改善通信性能、降低延遲，并減輕核心網(wǎng)絡(luò)負(fù)擔(dān)[4-6].

現(xiàn)有的D2D-MEC 研究大多忽略了D2D 通信中的社會關(guān)系屬性，這在很大程度上影響了D2DMEC 系統(tǒng)[7-9]的性能.Gao 等[8]提出通過用戶的社會關(guān)系決定D2D 傳輸過程的功率分配和D2D 連接的補(bǔ)償機(jī)制.Li 等[9]設(shè)計(jì)存在社會關(guān)系的中繼設(shè)備選擇機(jī)制，使更多的設(shè)備參與了D2D 的合作計(jì)算.關(guān)于社會意識的D2D-MEC 網(wǎng)絡(luò)中的長期隨機(jī)優(yōu)化問題及資源分配問題仍存在許多不足.

李雅普諾夫優(yōu)化方法可以根據(jù)實(shí)時(shí)輸入的數(shù)據(jù)在線計(jì)算系統(tǒng)控制參數(shù)，解決了長期時(shí)變的問題.Sun 等[10]研究在D2D 輔助的MEC 系統(tǒng)中，使用李雅普諾夫優(yōu)化理論進(jìn)行UEE 和網(wǎng)絡(luò)穩(wěn)定性之間的權(quán)衡，但沒有考慮D2D 之間的匹配問題.Jiang 等[11]研發(fā)了新的支持MEC 的多請求者協(xié)作者模型，但是沒有考慮協(xié)作者卸載到MEC 的計(jì)算過程.Long 等[12]研究具有社會感知的長期D2D 協(xié)作MEC 網(wǎng)絡(luò)節(jié)能計(jì)算卸載框架，但僅考慮了D2D 之間的一對一卸載，所使用的匹配理論算法復(fù)雜度較高.此外，傳統(tǒng)電池供電設(shè)備的總能量有限[13]，可能會因?yàn)槟芰亢谋M而導(dǎo)致計(jì)算性能受損.

針對上述問題，本文提出考慮不同設(shè)備下能量收集(energy harvesting,EH)技術(shù)和用戶間社會信任關(guān)系的D2D-MEC 網(wǎng)絡(luò)架構(gòu)，此架構(gòu)可以有效地降低系統(tǒng)的能量損耗，提高D2D 鏈路的安全性.設(shè)計(jì)基于李雅普諾夫的在線決策和資源分配(online decision matching and resource allocation,ODMRA)算法，最小化所有用戶的長期平均服務(wù)成本，將原始隨機(jī)優(yōu)化問題轉(zhuǎn)化為單時(shí)隙獨(dú)立的確定性問題，然后分別求解.仿真結(jié)果驗(yàn)證了ODMRA 算法在系統(tǒng)服務(wù)成本和隊(duì)列穩(wěn)定性方面具有性能優(yōu)勢.

1 系統(tǒng)模型

如圖1 所示為能量收集下的D 2 D 輔助MEC 網(wǎng)絡(luò)系統(tǒng)，由物理域和社會域2 個(gè)部分組成.其中物理域由一個(gè)配備MEC 服務(wù)器的基站(base station,BS)和多個(gè)移動(dòng)設(shè)備組成.移動(dòng)設(shè)備分為遠(yuǎn)程發(fā)送設(shè)備(distant transmitters,DTs)和近端發(fā)送設(shè)備(nearby receivers,NRs)2 種類型，其中DTs 的集合為 N，NRs 的集合為 K.考慮細(xì)粒度的卸載方式，DTs 生成的任務(wù)可以在本地、NRs 和MEC 服務(wù)器上3 處并行執(zhí)行.定義(t)為DTi在時(shí)隙t 內(nèi)執(zhí)行的任務(wù)量.由于DTs 與BS 距離較遠(yuǎn)，信道連接很差，DTs 不能直接將任務(wù)卸載到MEC 服務(wù)器.NRs 距離BS 較近，且有空閑的計(jì)算能力來協(xié)助DTs 計(jì)算任務(wù).Dij(t)為從 DTi 傳輸?shù)絅Rj 的任務(wù)量，其中NRj 為在時(shí)隙t 內(nèi)執(zhí)行(t)的數(shù)據(jù)量，由于NR 處的計(jì)算和傳輸能力有限，剩余的數(shù)據(jù)量在NR 處的任務(wù)緩沖區(qū)中等待進(jìn)一步執(zhí)行.

圖1 能量收集下的D2D 輔助MEC 網(wǎng)絡(luò)系統(tǒng)模型圖Fig.1 System model of D2D-assisted MEC network with energy harvesting

將時(shí)間離散為時(shí)隙的形式，用 t∈T表示，其中每個(gè)時(shí)隙長度為 τ0.引入二進(jìn)制指示器 xij(t)表示用戶的關(guān)聯(lián)決策[14]，在每個(gè)時(shí)隙開始的時(shí)刻，DTi 通過D2D 卸載決策 xij(t)決定卸載到哪個(gè)NRj，若DTi 決定將任務(wù)卸載到NRj，則 xij(t)=1，否則 xij(t)=0.一個(gè)DT 在一個(gè)時(shí)隙內(nèi)只能將任務(wù)卸載到一個(gè)NR 上，一個(gè)NR 最多輔助 Nmax個(gè)DTs，因此D2D 設(shè)備間關(guān)聯(lián)的約束條件如下.

假設(shè)DTi 在每個(gè)時(shí)隙產(chǎn)生的計(jì)算任務(wù)量為Ai(t).在不失一般性的情況下，Ai(t)在每個(gè)時(shí)隙內(nèi)服從 Ai(t)∈[Amin,Amax]的均勻分布，即任務(wù)量服從E[Ai(t)]=λi的獨(dú)立同分布函數(shù).由于下行傳輸中任務(wù)的數(shù)據(jù)量較小，忽略數(shù)據(jù)返回能耗和傳輸時(shí)間.

本節(jié)闡述了物理域中移動(dòng)設(shè)備的基本關(guān)系.物理域包含隊(duì)列模型、傳輸模型、任務(wù)計(jì)算模型和EH 模型，其中每個(gè)DT 和NR 對應(yīng)社會域中的單個(gè)用戶.在社會域中，將用戶之間的社會關(guān)系量化為社會信任矩陣后，作為D2D 匹配過程中決策選擇的重要依據(jù).下面詳細(xì)介紹各個(gè)模型.

1.1 任務(wù)隊(duì)列模型

由于D2D 的傳輸速率大于本地任務(wù)的生成速率，DT 生成的任務(wù)在本地計(jì)算一部分后，剩余部分可以通過D2D 快速上傳到匹配的NR 上.一個(gè)NR 最多可以接收 Nmax個(gè)DT 的部分計(jì)算任務(wù)，考慮本身計(jì)算能力的限制,在每個(gè)NR 處都設(shè)置任務(wù)緩沖區(qū) QNjR(t)，用于儲存從DT 卸載到NR 上的任務(wù).NR 處過多的任務(wù)量將存儲在任務(wù)緩沖區(qū)中，在后續(xù)的時(shí)隙中進(jìn)行計(jì)算或卸載.QNjR(t)可以用下式表示：

1.2 傳輸模型

為了避免不同卸載用戶間的嚴(yán)重干擾，系統(tǒng)采用正交頻分多址（OFDMA）技術(shù).D2D 傳輸過程中分為N 個(gè)相同大小的子信道，從NRj 卸載到MEC 的可用帶寬被劃分為K 個(gè)相同大小的子信道，N+K 個(gè)子信道的帶寬均為W Hz.從DTi 到NRj 的信道功率增益為 Hij(t)=hij(t)g0(d0/dij)θ.從NRj 到MEC 的蜂窩鏈路信道功率增益設(shè)置為Hjs(t)=hjs(t)g0(d0/djs)θ.其中 hij(t)和 hjs(t)為小尺度的瑞利衰落系數(shù)，符合單位均值的指數(shù)分布，g0為路徑損失函數(shù)，θ為路徑損失指數(shù)，d0為參考距離，dij為從DTi 到NRj 的距離，djs為從NRj 到邊緣服務(wù)器MEC 的距離.通過香農(nóng)公式可知，從DTi 到NRj 的D2D 傳輸速率為 rij(t)=Wlog2(1+從NRj 到邊緣服務(wù)器MEC 的傳輸速率為其中為DTi 的發(fā)射功率，為NRj 的發(fā)射功率，σ2為背景噪聲方差.

1.3 任務(wù)計(jì)算模型

為了確保MEC 的可持續(xù)使用，搭載MEC 的基站通常由電網(wǎng)供電，所以忽略MEC 計(jì)算過程的能量消耗.令 fiDT(t)為DTi 在t 時(shí)刻的本地CPU 循環(huán)頻率，γi為DTi 的計(jì)算負(fù)載，單位為cycles/bit.DTi 在單個(gè)時(shí)隙內(nèi)的計(jì)算任務(wù)大小為執(zhí)行DTi 本地計(jì)算任務(wù)的能耗為.其中 κ1為DT 芯片架構(gòu)的功率系數(shù).

1.4 EH 模型

每個(gè)移動(dòng)設(shè)備都配備EH 裝置，可以捕獲可再生能源供能.在時(shí)隙開始的時(shí)刻，DTi 的能量為，NRj 的能量為，它們服從在不同時(shí)隙的最大值為和的獨(dú)立同分布模型.ei(t)、ej(t)為被收集并存儲在電池中的能量，用于本時(shí)隙的任務(wù)計(jì)算和下一個(gè)時(shí)隙的任務(wù)卸載.在每個(gè)時(shí)隙中，ei(t)、ej(t)滿足以下約束：

采用虛擬電池能量隊(duì)列來量化DTi 和NRj 的電池能量水平，在每個(gè)時(shí)隙開始時(shí)，將DTi 和NRj 的虛擬電池隊(duì)列記為 Bi(t)和 Bj(t).在本文中Bi(0)=0,Bj(0)=0,Bi(t)＜∞,Bj(t)＜∞,DTi 和NRj在t 時(shí)刻消耗的能量記為

兩者受到以下能量關(guān)系的約束：

DT 和NR 的虛擬電池能量隊(duì)列動(dòng)態(tài)模型為

1.5 社會信任矩陣

在社會域中，社會關(guān)系為用戶通過社交網(wǎng)絡(luò)中的連接、交流和互動(dòng)構(gòu)建的關(guān)系網(wǎng)絡(luò)，反映了用戶間的信任度和親密程度.利用貝葉斯技術(shù)，將不同社交網(wǎng)絡(luò)平臺下收集到的歷史記錄進(jìn)行整合，獲得用戶之間的社會關(guān)系，用社會信任矩陣表示一個(gè)時(shí)隙內(nèi)DTi 和NRj 的社會關(guān)系強(qiáng)度.社會關(guān)系的強(qiáng)度越大，移動(dòng)設(shè)備之間越有可能建立D2D 通信鏈接.社會關(guān)系屬性在D2D 匹配決策中發(fā)揮了關(guān)鍵作用.

1.5.1 社會信任矩陣的獲取方案 在互聯(lián)網(wǎng)的社交領(lǐng)域，系統(tǒng)在微博、抖音、Twitter 等社交平臺上獲取用戶間的社會關(guān)系，如發(fā)布的帖子、評論、點(diǎn)贊、分享等.這些記錄不僅可以揭示用戶的興趣、觀點(diǎn)和偏好，還反映用戶之間的社交關(guān)系.利用貝葉斯技術(shù)，可以對不同社交網(wǎng)絡(luò)平臺收集到的歷史記錄進(jìn)行整合，得到社會信任矩陣[9,15].

具體過程如下.使用貝葉斯技術(shù)對不同的社交網(wǎng)絡(luò)平臺上收集的數(shù)據(jù)進(jìn)行整合，通過用戶選擇相似內(nèi)容的概率密度分布函數(shù)來表示用戶行為的相似性，決定社會關(guān)系的強(qiáng)度.量化社會關(guān)系的強(qiáng)度，在得到社會信任值后，可得社會信任矩陣.該模型在獲取用戶之間的社會信任關(guān)系模型中得到了廣泛應(yīng)用[8,12].

1.5.2 社會信任矩陣在本文的應(yīng)用 在利用上述方案得到多個(gè)社交網(wǎng)絡(luò)的數(shù)據(jù)整合模型后，社會信任矩陣 Ω(t)=[ω1(t),ω2(t),···,ωN(t)]表示用戶之間的社會關(guān)系.其中社會信任矩陣 Ω(t)的列向量為 ωi(t)=[ωi1(t),ωi2(t),···,ωiK(t)]T，其中 ωij(t)為DTi 和NRj 之間的社會信任值，用來表示一個(gè)時(shí)隙內(nèi)DTi 和NRj 的社會關(guān)系強(qiáng)度.時(shí)變的社會信任值 ωij(t)為

ωij(t)=0表示DTi 和NRj 之間不存在社會關(guān)系，因此他們之間不會建立D2D 鏈接.從D2D 傳輸?shù)男畔踩院蛡鬏斂煽啃缘姆矫婵紤]，用戶之間更喜歡與其社會關(guān)系較高的用戶建立D2D 鏈接，傳輸DT 產(chǎn)生的計(jì)算任務(wù).

2 問題公式化

2.1 性能度量

本文的優(yōu)化目標(biāo)為在計(jì)算資源和隊(duì)列穩(wěn)定性約束下盡量減少系統(tǒng)服務(wù)成本，其中系統(tǒng)服務(wù)成本主要包括系統(tǒng)能耗成本、任務(wù)丟失成本和安全成本3 部分.當(dāng)DT 或NR 沒有足夠的能量或者無線信道條件較差時(shí)，放棄到達(dá)的任務(wù).考慮這方面的因素，對每一個(gè)放棄的任務(wù)都加一個(gè)單位成本懲罰因子[16-17].此時(shí)，將系統(tǒng)的服務(wù)成本定義為所有設(shè)備的計(jì)算能耗和傳輸能耗、任務(wù)丟失成本和社會信任值的加權(quán)和.

式中：xij(t)∈{0,1}為在t 時(shí)刻的D2D 鏈接指示器，若DTi 與NRj 在t 時(shí)刻建立鏈接，則 xij(t)=1，否則 xij(t)=0 ;Di(t)、Dj(t)∈{0,1}為DTi 和NRj 的任務(wù)丟棄指示器，等于1 表示不丟棄任務(wù)，否則為丟棄；φi(t)、φj(t)為DTi 和NRj 的丟棄任務(wù)懲罰成本；?為社會信任值的懲罰成本，社會信任值與系統(tǒng)安全成本間存在近似反比關(guān)系，應(yīng)選擇盡可能大的社會信任值來降低系統(tǒng)服務(wù)成本.

2.2 最小化系統(tǒng)服務(wù)成本

由于 Bi(t)和 Bj(t)為理想化狀態(tài)下的電池能量隊(duì)列，將擾動(dòng)參數(shù) θi和 θj加入其中表示消耗的實(shí)際電池能量水平，則2 種設(shè)備的虛擬能量隊(duì)列和表示為

擾動(dòng)參數(shù) θi和 θj滿足下列不等式[16,18]：

不等式（19a）～（19d）表示每個(gè)設(shè)備的計(jì)算頻率和發(fā)射功率不超過它們的最大值.式（19e）表示社會信任值的約束.不等式（19f）、（19g）表示DTs 和NRs 的電池輸出量不超過它們的電池放電約束.式(19h)保證了任務(wù)緩沖隊(duì)列是有界的，即平均速率穩(wěn)定.P1是隨機(jī)的混合整數(shù)規(guī)劃問題，其中包括的連續(xù)變量和二元變量是耦合且時(shí)變的，到達(dá)的計(jì)算任務(wù)和隊(duì)列積壓是隨機(jī)且不可預(yù)測的，很難推導(dǎo)出長期的最優(yōu)策略.李雅普諾夫優(yōu)化技術(shù)是解耦長期問題的有效方法，可以根據(jù)系統(tǒng)實(shí)時(shí)輸入的數(shù)據(jù)，在線計(jì)算系統(tǒng)的控制參數(shù)，實(shí)現(xiàn)對系統(tǒng)的在線控制和調(diào)整，在解決資源分配問題上得到了廣泛應(yīng)用[19-20].

2.3 李雅普諾夫優(yōu)化框架

為了解決隨機(jī)優(yōu)化問題 P1，在隊(duì)列穩(wěn)定條件下最小化系統(tǒng)服務(wù)成本問題轉(zhuǎn)化為漂移加懲罰函數(shù)，通過漂移函數(shù)滿足隊(duì)列穩(wěn)定，利用懲罰函數(shù)滿足系統(tǒng)成本最小化.當(dāng)前時(shí)刻的隊(duì)列積壓為,引入二次的李雅普諾夫函數(shù)：

式中：L(Θ(t))表示隊(duì)列積壓的標(biāo)量度量，L(Θ(t))＞0 .L(Θ(t))越小，所有任務(wù)的隊(duì)列積壓數(shù)量越少.

引入李雅普諾夫漂移函數(shù)：

通過將隊(duì)列穩(wěn)定性納入執(zhí)行成本性能中，定義李雅普諾夫漂移加懲罰函數(shù)來解決上述問題：

式中：V 為目標(biāo)函數(shù)對漂移懲罰的權(quán)值，可以作為調(diào)整系統(tǒng)成本和隊(duì)列穩(wěn)定性的控制參數(shù)[21].

在每個(gè)時(shí)隙中，通過最小化 ΔV(Θ(t))，將系統(tǒng)成本最小化的同時(shí)，穩(wěn)定了隊(duì)列水平.由于 ΔV(Θ(t))是非線性的，沒有直接最小化 ΔV(Θ(t))，而是推導(dǎo)出李雅普諾夫漂移加罰函數(shù)的上界，并設(shè)計(jì)在線卸載算法，最小化 ΔV(Θ(t))在可行區(qū)域 O(t)的上界，使得隊(duì)列穩(wěn)定.

在每個(gè)時(shí)隙中，對于任意隊(duì)列積壓 Θ(t)和系統(tǒng)服務(wù)成本 W(t)，在可行決策 O(t)下的漂移加懲罰函數(shù) ΔV(Θ(t))滿足

證明：將隊(duì)列積壓公式(4)的兩邊平方，得到

將式(25)的所有移動(dòng)設(shè)備相加，得到以下不等式：

對2 種設(shè)備的虛擬能量隊(duì)列(15)、(16)開展與式(4)相同的操作，如下所示：

將式(26)～(28)相加，可得

將C 和式(29)代入式(22)，可得漂移加罰函數(shù)的上界(23).

根據(jù)漂移加罰函數(shù)的上界，設(shè)計(jì)基于李雅普諾夫的在線優(yōu)化方法.通過最小化式(23)的右側(cè)，將長期優(yōu)化問題轉(zhuǎn)化為基于單個(gè)時(shí)隙的優(yōu)化問題P2，將其拆分后逐個(gè)進(jìn)行處理，使得優(yōu)化問題更加容易、高效地求解.

3 ODMRA 算法的設(shè)計(jì)

該部分的目標(biāo)是將長期平均優(yōu)化問題轉(zhuǎn)化為如下4 個(gè)單時(shí)隙優(yōu)化問題：1)能量收集；2)計(jì)算資源分配；3)發(fā)射功率分配；4）D2D 匹配決策.結(jié)合凸分解和子模塊優(yōu)化理論，提出基于李雅普諾夫優(yōu)化的D2D 在線決策匹配和資源分配(ODMRA)算法，分別解決這些子問題.

3.1 收獲的最佳能量

通過如下問題求解DTs 和NRs 收獲的能量.

3.2 最優(yōu)卸載決策和資源分配

將P3從問題 P2中解耦后，則轉(zhuǎn)化為問題 P4.通過解決以下問題，獲得DTs 和NRs 的最優(yōu)CPU 頻率、最優(yōu)的D2D 傳輸功率、最優(yōu)的上傳功率和最佳的D2D 匹配決策.

P4是混合整數(shù)規(guī)劃問題，若使用蠻力方法求解，則計(jì)算復(fù)雜度非常高.觀察到可行區(qū)域是f(t)、p(t)、x(t)的笛卡爾乘積，使用高斯-賽德爾迭代法交替[22-23]最小化求解，可以有效地保證 P4的收斂性.設(shè)計(jì)ODMRA 算法，提出利用迭代的方法交 替求解問題 P4.

3.2.1 最優(yōu)的CPU 頻率 假設(shè)發(fā)射功率和D2D 匹配決策固定，最優(yōu)的CPU 周期頻率調(diào)度問題為

將P4.1分解為DTs 的CPU 頻率問題和NRs 的CPU 頻率問題.由于DTs 的CPU 頻率問題是非凸的，將放縮后，得到原問題的上界為

3.2.2 功率分配問題 通過固定DTs 和NRs 的CPU 循環(huán)頻率和D2D 連接決策，功率分配問題可以寫成如下形式：

接下來解決NR 到MEC 的傳輸功率問題：

3.2.3 D2D 決策選擇問題 給定最優(yōu)的發(fā)射功率和設(shè)備的CPU 頻率，關(guān)于社會信任關(guān)系的D2D 匹配決策問題表述如下：

子模塊優(yōu)化是解決組合問題的強(qiáng)大工具[23-24]，適用于求解策略選擇問題.與其他的策略選擇算法相比，它具有高效性、復(fù)雜度更低、資源分配更加公平等優(yōu)點(diǎn)，因此子模塊優(yōu)化在網(wǎng)絡(luò)問題中被廣泛應(yīng)用.

利用子模塊優(yōu)化來尋找D2D 之間的決策.具體來說，將約束下的2 種移動(dòng)設(shè)備DT 和NR 之間的決策約束(1)和(2)寫為擬陣的形式，嚴(yán)格證明了D2D 決策選擇的效用函數(shù) xij(t)Uij(t)存在單調(diào)性和子模性.將問題 P4.3轉(zhuǎn)化為擬陣約束下的子模函數(shù)最大化問題，用“邊際效用遞減”性質(zhì)結(jié)合低復(fù)雜度的貪婪算法，可得保證系統(tǒng)性能最優(yōu)的D2D 匹配決策.

G(t)包含所有可能的關(guān)聯(lián)策略，這些策略可以劃分為N 個(gè)不相交的集合，如G(t)=∪i∈NAi(t),Ai(t)∩Ai′(t)=?,i ≠i′.其中Ai(t)={x?i1(t),···,x?iK(t)},?i∈N，表示DTi 與NR 配對的集合.這些策略可以劃分為K 個(gè)不相交的集合，如G(t)=∪j∈KBj(t),Bj(t)∩Bj′(t)=?,j ≠j′.其中Bj(t)={x?1j(t),···,x?Nj(t)},?j∈K表示NR 與DTs 配對的集合.

擬陣 I表示每個(gè)DT 可以關(guān)聯(lián)的NRs 的約束(1)和每個(gè)NR 可以關(guān)聯(lián)的DTs 的約束(2)，|·|表示基數(shù).

定理1：給定地面集合 G(t)和它的一個(gè)子集X(t)∈G(t)，則是基于X(t)∈G(t)的單調(diào)子模函數(shù).

證明：因?yàn)?/p>

令ε(t)?X(t)，v∈X(t)ε(t)，則

接下來證明目標(biāo)函數(shù) F(X(t))的子模性.若F(X(t))滿足“邊際效應(yīng)遞減”性質(zhì)，則它具有子模性.向集合 ε(t)中添加一個(gè)元素的邊際增益至少與它的超集中添加一個(gè)元素的邊際增益相等，即滿足

式中：ε(t)?ε(t)′∈X(t),a(t)∈G(t)ε′(t).根據(jù)式(46)，可以推導(dǎo)出如下的邊際效應(yīng)關(guān)系.

可以看出，ΔF(t)(a(t)|ε(t))=ΔF(t)(a(t)|ε′(t))，滿足“邊際效應(yīng)遞減”性質(zhì)，證明了函數(shù) F(X(t))的子模性，從而證明了定理1 存在的合理性.此時(shí)，可以將最小化問題 P4.3轉(zhuǎn)化為最大化問題，求解最優(yōu)策略.

將問題 P4.3重新表示為擬陣約束的單調(diào)子模問題的最大問題：

在擬陣約束的情況下，根據(jù)“邊際效應(yīng)遞減”性質(zhì)，結(jié)合貪婪算法的思想，設(shè)計(jì)策略選擇算法，解決問題 P4.4.設(shè)置定義函數(shù)F(X(t))的邊際增益為

初始化集合 X(t)、Xi(t)、Xj(t)(?i∈N,?j∈K)為空集?，其中 X(t)為D2D 的策略選擇集合.Xi(t)包含了DTi 將任務(wù)卸載到哪個(gè)NR 的決策集合.Xj(t)表示NRj 輔助哪些DTs 的決策集合.在初始化完成后，用 戶匹配策略選擇算法設(shè)計(jì)如下.

3.2.4 ODMRA 算法和最優(yōu)值分析 通過考慮D2D 用戶卸載決策、CPU-周期頻率、傳輸功率分配和收集的電池能量，將ODMRA 算法總結(jié)在算法2 中.求解問題 P3的計(jì)算復(fù)雜度為 O(N+K)，本方案通過交替迭代解決子問題 P4.1、P4.2和 P4.3來優(yōu)化目標(biāo)問題 P4，假設(shè)迭代過程中的最大迭代次數(shù)為 κ，在每次迭代中復(fù)雜度為 O(2(N+K)+NK)，因?yàn)樵诘孛婕?G(t)中有NK 個(gè)元素，求解 P4.3的時(shí)間復(fù)雜度為 O(NK).本文所提ODMRA 算法的計(jì)算復(fù)雜度為 O(N+K+κ(2(N+K)+NK)).通過對算法復(fù)雜度進(jìn)行理論分析可知，與匹配博弈算法相比，本文算法的復(fù)雜度更低，可以更好地應(yīng)用于 實(shí)際系統(tǒng).

4 仿真分析

考慮半徑為200 m 的圓形區(qū)域，配備了MEC服務(wù)器的BS 位于該區(qū)域的中心.NRs 和DTs 分別隨機(jī)分布在半徑分別為50～150 m 和150～200 m 的環(huán)狀區(qū)域內(nèi).仿真參數(shù)基于文獻(xiàn)[12]和[16]設(shè)置.DT 生成的任務(wù)在 1.0×104～2.0×104bits/s 內(nèi)呈均勻分布.信道功率增益呈平均值為 g0(d/d0)-4的指數(shù)分布.時(shí)隙數(shù)T=200,DTs 的數(shù)量Nmax=10,NRs的數(shù)量K=4,W=1 MHz,τ0=0.1 s,σ2=10-12W,γi=γj=[1,1.1,1.2,1.3] cycles/bit，κ1=10-12，κ2=10-16,d0=1,g0=-40 dB.為了評估本文算法的性能，最大程度地消除單次運(yùn)行的隨機(jī)性對仿真結(jié)果造成的誤差，因此進(jìn)行100 次蒙特卡羅模擬，對最終的仿真結(jié)果取平均值.

本文的對比算法如下.1)基線1：只考慮MEC 服務(wù)器的執(zhí)行和本地執(zhí)行，而附近的設(shè)備只作為中繼設(shè)備，無法執(zhí)行計(jì)算任務(wù).2)基線2：NRs 僅用于通過D2D 通信卸載任務(wù)，不作為中繼設(shè)備.3)隨機(jī)算法：DTs 和NRs 在D2D 中隨機(jī)匹配的算法.4)SADLS 算法：Long 等[12]提出的使用匹配博弈的方法進(jìn)行D2D 的策略選擇算法.5)Qlearning 算法.

近端發(fā)送設(shè)備NR 的隊(duì)列長度隨時(shí)隙數(shù)t 變化的圖像如圖2 所示.隨著時(shí)間的增加，近端發(fā)送設(shè)備的隊(duì)列長度逐漸增加并趨于穩(wěn)定.這是由于ODMRA 算法可以通過最小化目標(biāo)函數(shù)，調(diào)整懲罰函數(shù)的大小來調(diào)整任務(wù)到達(dá)率和任務(wù)處理率之間的動(dòng)態(tài)關(guān)系，使得李雅普諾夫漂移項(xiàng)逐漸減小，系統(tǒng)逐漸趨于穩(wěn)定狀態(tài).仿真圖像顯示了李雅普諾夫漂移懲罰函數(shù)的上界，證明了本文算法的有效性.

圖2 輔助設(shè)備隊(duì)列長度隨時(shí)隙數(shù)的變化Fig.2 NR’s queue length with number of time slot

2 種設(shè)備的虛擬電池隊(duì)列隨著時(shí)間變化的圖像如圖3 所示.NRs 的計(jì)算能力大于DTs，故NRs 的電池容量大于DTs.隨著時(shí)間的增加，2 種設(shè)備的虛擬電池隊(duì)列長度在本文算法的優(yōu)化下逐漸減小并逐漸穩(wěn)定在擾動(dòng)參數(shù) θi和 θj附近,驗(yàn)證了電池水平的下界.

圖3 電池隊(duì)列長度隨時(shí)隙數(shù)的變化Fig.3 Battery queue length with number of time slot

如圖4、5 所示，比較了2 種移動(dòng)設(shè)備數(shù)量改變時(shí)輔助設(shè)備隊(duì)列長度的變化，圖4 顯示了輔助設(shè)備數(shù)量為4 時(shí)，隊(duì)列長度隨著DT 數(shù)量NDTs的增加而增加.隨著任務(wù)數(shù)量的增加，D2D 傳輸和輔助設(shè)備計(jì)算的任務(wù)量增加.在系統(tǒng)任務(wù)處理能力不變的情況下，移動(dòng)設(shè)備產(chǎn)生的計(jì)算任務(wù)將會在NR 中不斷積累，導(dǎo)致隊(duì)列長度增加，近端設(shè)備的隊(duì)列需要更長的時(shí)間達(dá)到穩(wěn)定狀態(tài).圖5 中，當(dāng)DT 的數(shù)量固定為10 時(shí)，隊(duì)列長度隨著NR 數(shù)量NNRs的增加而減小.這是因?yàn)殡S著輔助設(shè)備數(shù)量的增加，在任務(wù)到達(dá)率不變的情況下，系統(tǒng)的任務(wù)處理能力提升，隊(duì)列積壓減小.

圖4 不同數(shù)量DTs 下隊(duì)列長度隨時(shí)隙數(shù)的變化Fig.4 Change of queue length with number of time slot under different quantities of DTs

圖5 不同數(shù)量NRs 下隊(duì)列長度隨時(shí)隙數(shù)的變化Fig.5 Change of queue length with number of time slot under different quantities of NRs

如圖6 所示為不同算法下時(shí)隙長度對系統(tǒng)性能的影響.可知，執(zhí)行延遲越長，系統(tǒng)的服務(wù)成本越小.所有算法的系統(tǒng)服務(wù)成本都隨著 τ0的增加而減小，其中本文算法的平均服務(wù)成本性能最好，驗(yàn)證了該算法的有效性.隨著 τ0的增加，本文算法、隨機(jī)匹配算法和SADLS 算法均可達(dá)到相似的平均服務(wù)成本.由于信道條件的不確定性，基線1 和基線2 的算法性能明顯最差.

圖6 平均服務(wù)成本隨時(shí)隙長度的變化Fig.6 Change of average service cost with length of time slot

如圖7 所示為不同算法下平均任務(wù)到達(dá)率 λi的變化對系統(tǒng)性能的影響.圖中，Eˉ為平均能量消耗.由于未能充分利用系統(tǒng)資源，基線1、基線2 和隨機(jī)算法的平均能耗隨著 λi的增加而出現(xiàn)大幅度上升.Q-learning 算法、SADLS 算法和本文算法都設(shè)計(jì)了卸載決策和資源分配方案，顯著降低了系統(tǒng)平均能耗.其中Q-learning 算法通過訓(xùn)練過程生成的Q 表是靜態(tài)的，這意味著Q 表一旦被創(chuàng)建，它就不能根據(jù)系統(tǒng)狀態(tài)的實(shí)時(shí)變化（如隊(duì)列積壓或長期成本的變化）進(jìn)行動(dòng)態(tài)調(diào)整，故會導(dǎo)致平均能耗較高.SADLS 算法采用匹配博弈，每個(gè)用戶追求自身利益最大化，各方之間的利益沖突可能會導(dǎo)致參與者失去利益，得到較差的納什均衡解，故算法性能較差且不穩(wěn)定.本文算法在決策選擇時(shí)，從系統(tǒng)的整體性能出發(fā)，將問題拆分成單個(gè)子模塊后逐個(gè)進(jìn)行優(yōu)化，每個(gè)參與者可以分配相對公平和合理的資源.在該模型中，本文算法相較于其他算法能耗更低且更加穩(wěn)定.

圖7 平均能量消耗隨平均任務(wù)到達(dá)率的變化Fig.7 Change of average energy consumption with average task arrival rate

5 結(jié) 語

本文研究具有社會關(guān)系屬性的D2D-MEC 網(wǎng)絡(luò)的任務(wù)卸載和資源分配框架，即具有空閑計(jì)算能力的附近設(shè)備發(fā)揮中繼作用，幫助遠(yuǎn)程發(fā)送設(shè)備執(zhí)行或進(jìn)一步將其任務(wù)轉(zhuǎn)移到MEC 服務(wù)器.將具有QoS 和能量隊(duì)列穩(wěn)定性約束的平均服務(wù)成本最小化的隨機(jī)優(yōu)化問題表述為一系列的短期確定性優(yōu)化問題.設(shè)計(jì)基于李雅普諾夫優(yōu)化的ODMRA 算法解決該問題.該算法對設(shè)備收集的能量、CPU 計(jì)算頻率、發(fā)射功率及D2D 鏈路匹配決策進(jìn)行優(yōu)化.仿真結(jié)果和理論分析表明，在任務(wù)隨機(jī)到達(dá)、系統(tǒng)狀態(tài)時(shí)變的情況下，該算法提高了隊(duì)列穩(wěn)定性，減少了能量消耗，且算法復(fù)雜度較低，優(yōu)于其他算法.