[發明專利]D2D多播網絡中的移動邊緣計算卸載與資源分配算法

在審

• 申請號: 202011490867.1
• 申請日: 2020-12-17
• 公開（公告）號: CN112654058A
• 公開（公告）日: 2021-04-13
• 發明（設計）人: 陳雷
• 申請（專利權）人: 中國刑事警察學院
• 主分類號: H04W24/02
• 分類號: H04W24/02;H04W28/02;H04W28/08;H04W28/22
• 代理公司: 沈陽利泰專利商標代理有限公司 21209
• 代理人: 史進斗

1.D2D多播網絡中的移動邊緣計算卸載與資源分配算法，其特征在于包括下列步驟：

首先，為了提高多播傳輸鏈路的穩定性和增加計算資源，提出了D2MD簇首選擇和分簇選擇策略，在簇首選擇策略中聯合考慮了D2MD用戶的社會屬性、可用能量和傳輸速率；

其次，在考慮用戶選擇、計算卸載策略和計算資源分配的條件下，將最大化用戶的收益作為最優化問題進行了公式；進一步，將最優化問題轉化為兩個子問題，分別是用戶選擇最優化USO問題和資源分配最優化RAO問題，其中RAO問題是一個凸優化問題，采用拉格朗日乘數法得到了它的最優解。

2.根據權利要求1所述的D2D多播網絡中的移動邊緣計算卸載與資源分配算法，其特征在于包括下列步驟：

1系統模型；

在基站覆蓋范圍內，用戶根據地理位置被分為多個D2MD簇；在每個簇中，有唯一的一個用戶被選中作為D2MD簇首，D2MD簇首有全雙工天線，通過無線的方式連接到用戶端和基站端；這些D2MD簇首能夠幫助用戶終端連接到網絡，并且協助用戶將任務傳輸給基站端的MEC服務器；簇首主動的保存一些內容，并且可以將內容多播傳輸給同簇內的用戶；當用戶要求某些內容時，簇首通過多播方式進行傳輸；為了實現有效的分發緩存，用戶分別屬于并且唯一屬于一個簇；D2D用戶的集合表示為K＝{1,2,L,K}；D2D簇的集合表示為M＝{1,2,L,M}；用其中x_i,m＝1表示用戶設備i使用的D2MD簇首m；X＝{x_i,m}表示使用簇首m的用戶設備集合；

2聯合社會屬性、能量和速率的簇首選擇和分簇策略；

在簇首選擇中，采用的是著名的中餐館過程模型，在簇c_n中，用戶j選擇用戶i作為簇首的概率表示為：

在這里a_w表示CRP的參數，m(m≥3)是簇c_n內的用戶數，是用戶j選擇用戶i作為簇首的概率；

因此用戶被選為簇首的概率矩陣表示為：

在這里第i行表示用戶i被選做簇首的概率，第i行元素之和表示用戶i的選擇概率，其中選擇概率最大的用戶，就是簇首；

因此，在簇c_n中，用戶j選擇用戶i作為簇首的概率通過公式(3)計算得到；

在這里是用戶i對用戶j的影響因子；表示為：

在這里w_S+w_E+w_R＝1；和分別表示用戶i對用戶j的社會影響因子，能量影響因子和傳輸速率影響因子；

2.1社會影響因子；

表示用戶i對用戶j的社會影響因子；用戶i與用戶j之間的社會相似因子，表示為：

在這里表示用戶i與用戶j之間的社會相似因子；的值越高表示相似度越高；如果則表示用戶i與用戶j之間將不會建立D2D通信鏈路；對于用戶簇c_n中的用戶，歸一化的社會影響因子表示為：

在這里表示用戶簇c_n中，其余用戶對用戶i的社會影響因子之和；

2.2能量影響因子；

表示用戶簇c_n中，用戶i在用戶j上的能量影響；用戶i在用戶j上能夠衡量出的最大可用傳輸時間表示為：

在這里表示用戶i可利用的能量，P₀表示用戶i的電路損耗，表示用戶i的傳輸功率；

在這里σ²表示噪聲功率，γ₀表示接收的信噪比門限；為了保證傳輸質量，需要用戶實際的接收SNR要大于γ₀；表示用戶i與用戶j間的信道增益，并且表示為：

表示瑞麗衰落，α_h表示路損參數，表示用戶i與用戶j間的距離；

將公式(8)和(9)代入公式(7)，得用戶i與用戶j間的最大傳輸時間為：

在這里值越高表示用戶i對用戶j的能量影響越大；考慮整個用戶簇c_n，一個歸一化的影響因子表示為：

在這里表示用戶簇c_n中，其余用戶對用戶i的能量影響因子之和；

2.3傳輸速率影響因子；

表示用戶簇c_n中，用戶i的傳輸速率；如果基站以定量的功率傳輸數據，則用戶i的傳輸速率表示為：

在這里表示基站與用戶i之間的信道增益，P_B表示基站的發射功率，表示用戶i與基站間的距離，W表示用戶i與基站間的信道帶寬，表示用戶i與基站間的瑞麗衰落，α_B表示路損參數；傳輸速率越高，則對用戶i的影響越大；考慮整個用戶簇c_n，一個歸一化的影響因子表示為：

在這里表示用戶簇c_n中，其余用戶對用戶i的傳輸速率影響之和；

綜上所述將公式(6)，(11)和(13)代入公式(4)得用戶i對用戶j的影響因子表示為：

用公式(14)代替(3)，得到選擇用戶i為簇首的概率；按照概率遞減的順序進行排列，概率最大的選做簇首；

2.4分簇策略；

初始化每個簇剩余的用戶集合表示為當時循環：從計算每個簇的平均影響因子選擇更新輸出：得到用戶分簇結果K_m,1≤m≤M；

3計算卸載和資源分配；

3.1支持MEC的D2MD系統通信模型與計算模型；

定義L_i＝(σ_i,s_i,T_i)表示用戶設備i需要處理的任務，其中δ_i(每兆比特的CPU工作的周期)表示處理任務需要總的計算資源，s_i(比特)表示需要執行的任務的數據量，T_i表示該任務可以接受的最大時延值；

支持MEC的D2MD網絡的計算任卸載的步驟是：首先，用戶設備發送一定比例的任務給與它們相聯系的D2MD簇首；其次，D2MD簇首接收任務后將使用前向鏈路相同的頻帶進一步傳輸給基站中的MEC；對于用戶i其計算卸載比例表示為o_i∈[0,1]，其中o_i＝1(o_i＝0)表示任務卸載到MEC執行；

1)通信模型；

設用戶設備和D2MD簇首的前向鏈路和反向鏈路工作在正交的頻譜上；前向鏈路的帶寬與反向鏈路的帶寬相同，用B表示；

用戶(i∈K)到D2MD簇首(m∈M)的鏈路上能夠獲得的傳輸速率表示為：

在這里p_i表示用戶設備i的發送功率；g_i,m表示從用戶設備i到D2MD簇首m的信道增益；SI表示全雙工天線的自干擾，并且SI＝Ib_i,mp_m，其中I 是剩余的SI的增益，p_m是D2MD簇首m分配的功率，b_i,m是D2MD簇首m的功率比；SI作為干擾刪除技術的一個常量；

從D2MD簇首m到基站的反向鏈路的數據速率表示為：

在這里p_m表示D2MD簇首m的最大傳輸功率；b_i,m∈(0,1]表示用戶設備i需要卸載任務時所分配的功率比；g_m表示D2MD簇首m到基站的信道增益；

用戶設備i傳輸到D2MD簇首m的上行數據速率表示為：

全雙工通信要求輸入鏈路的傳輸速率要高于輸出鏈路的傳輸速率。因此有：令其中表示卸載任務給MEC的傳輸速率；

2)計算模型；

定義為用戶設備i的本地計算能力(每兆比特的CPU工作的周期)，因此終端全部的任務通過本地計算時的本地計算執行時延表示為：

任務從用戶設備i傳輸到D2MD簇首上，這時在D2MD簇首上的任務的計算執行延遲表示為：

因此移動邊緣計算服務器上處理任務時的總的計算執行時延表示為：

其中w^e表示MEC服務器上的計算能力；a_i表示MEC服務器上執行用戶設備i上任務的計算因子；

從用戶i傳輸到D2MD簇首m的任務L_i＝(σ_i,s_i,T_i)的傳輸延以表示為：

從用戶i通過D2MD簇首m傳到MEC的任務L_i＝(σ_i,s_i,T_i)的傳輸延遲表示為：

令和分別表示卸載到MEC和D2MD簇首的任務的比例；因此，當任務被卸載到D2MD簇首和MEC上時，剩余任務在本地的處理時間表示為：

卸載的任務從用戶i到D2MD簇首m和MEC的總執行時延表示為：

假設任務被同時分配給本地移動終端和MEC服務器上執行，因此任務L_i的總的完成時間是本地執行時間與MEC服務器或D2MD簇首上執行時間中最大的，因此當任務被卸載到MEC時，總的完成時間表示為：

當任務被卸載到D2MD簇首時，總的完成時間表示為：

3.2收益最大化問題；

首先，定義效用函數為在服務收益和成本之間的一個減法函數；基于效用函數，公式了最大化收益問題；其次，將原始的最優化問題進行了分解，分解為兩個最優化問題；最后，采用貪婪算法進行了求解；

1)效用函數和最優化問題公式；

效用函數表示為在服務收益和成本之間的減函數；服務收益表示為包括獲得任務數據的多少和使用計算資源的多少；成本包括分配的計算資源的價格和傳輸數據給MEC所需要的功率；因此任務L_i＝(σ_i,s_i,T_i)的效用函數表示為：

其中d_m表示D2MD簇首m的當前狀態，d_m＝1表示處于工作狀態，否則d_m＝0表示處于空閑狀態；在這里κ和η分別表示每單元卸載數據的收益系數和D2MD簇首每單元功率的收益系數；ρ和β分別表示每單元計算資源的價格系數和每單元時間內所分配的計算能力的價格系數；

s.t.C1：

C2:

C3:

C4:

C5:

C6:

其中限制條件C1表示在MEC服務器上和本地用戶設備上的任務是并行計算的；限制條件C2表示保障用戶設備每次只能連接到一個全雙工D2MD簇首；限制條件C3表示要求每個D2MD簇首同時接入的用戶設備數量不能超過其能夠接受的最大值；限制條件C4表示每個D2MD簇首分配的功率不能超過它的最大傳輸功率；限制條件C5表示分配給MEC的計算資源不能超過MEC最大的計算能力；限制條件C6表示對于每個用戶設備其反向鏈路的傳輸速率小于前向鏈路的傳輸速率；

2)最優化問題轉化；

由于是二進制的變量，因此目標函數(30)(即公式30)是一個非凸函數；原始的問題是一個混合離散非凸的最優化問題，因此該最優化問題是一個NP-hard問題；重構原始問題分解為兩個子問題，分別命名為用戶選擇最優化(USO)問題和資源分配最優化(RAO)問題；

對一個固定值X，RAO問題表示為：

令公式(31)重構為：

命題1：對于任務L_i將被卸載到MEC或D2MD簇首中，其中最優的卸載率是計算卸載總的執行時間是T_i；經證明得

當計算卸載分配給D2MD簇首時，因為任務卸載比例的增加，基于公式(32)可知，從完成任務所獲得的收益將會減少；

令整合公式(30)和(31)，并替代相關變量后得：

公式(32)重新寫為：

s.t.C7:

C8:

C9:

3)最優化問題的求解；

首先討論RAO問題的求解；對Z_i,m中ξ_i,m的二階導數表示為：

從命題1可知，因此得：

同理，并且能夠得到：

當時，合并公式(37)和(38)得：

因此得并且函數(39)(即公式39)是凸函數；作為目標函數(39)(即公式39)的二階導是嚴格收斂的；因此，解決公式(39)的最優化問題；

對于USO問題的求解，令和分別表示在用戶選擇X的接入方案中分配的功率和分配的計算資源；通過前述的算法獲得最優的資源分配結果，對應剩余的用戶選擇問題，則是一個0-1的非線性最優化問題，同時也是一個完整的NP問題。

3.根據權利要求2所述的D2D多播網絡中的移動邊緣計算卸載與資源分配算法，其特征在于包括下列步驟：

解決公式(39)應用KKT條件時；公式(39)的拉格朗日表達式為：

對于KKT條件表示為：

在這里a′_i(ξ_i,m)＝JV/(J-Cξ_i,m)²，其中C＝w^eBT_iσ_i，令[y]⁺＝max{y,0}，結合公式(41)-(43)，拉格朗日乘數重新寫為：

在這里t是迭代次數，δ(t)表示第t次迭代的間距；利用KKT條件，獲得最優的資源分配結果；最優的ξ_i,m從公式(45)-(48)獲得；按照公式(32)和(33)，獲得最優的和

對于USO問題的求解，采用貪婪算法來獲得最優的用戶選擇，具體算法的細節如下：

算法：貪婪算法

輸入：

用戶設備的集合表示為：K＝{1,2,L,K}

最大迭代次數為：I

正在工作的D2MD簇首集合表示為：

D＝{d₁,d₂,L,d_M}

用戶設備的任務表示為：L_i＝(σ_i,s_i,T_i)

同時定義B,p_m,p_i,w^e,κ,ρ,η,β

輸出：

采用的資源分配策略A^*,B^*,O^*

采用的用戶選擇策略X^*