[發明專利]一種移動邊緣計算網絡中多目標優化的計算卸載方法

有效

• 申請號: 202011272786.4
• 申請日: 2020-11-14
• 公開（公告）號: CN112512056B
• 公開（公告）日: 2022-10-18
• 發明（設計）人: 方娟;史佳眉;陸帥冰;張夢媛;葉志遠
• 申請（專利權）人: 北京工業大學
• 主分類號: H04W16/22
• 分類號: H04W16/22;H04W52/02;H04W52/24;H04W76/34
• 代理公司: 北京思海天達知識產權代理有限公司 11203
• 代理人: 張慧

1.一種移動邊緣計算網絡中多目標優化的計算卸載方法，該方法適用的網絡構架為，上端的云服務器通過交換機與基站進行通信，在整個網絡中有多個基站，且每個基站附近都部署一個MEC服務器，每個基站所覆蓋的區域內都存在多個用戶進行計算，考慮到云時延較高的問題，當用戶選擇卸載的時候則只會將對應比例的用戶程序卸載到該區域內的MEC服務器上進行計算，其特征在于包括以下步驟：

S1.根據網絡架構進行建模，包括系統模型，應用程序模型，通信模型以及計算模型；

整個移動邊緣計算系統網絡架構，由若干個小區域組成，整體卸載工作包括兩部分，首先考慮一個小區域中的計算卸載情況，然后對各個區域進行求和；

對于任意子區域1，即考慮多個用戶與一個MEC服務器的場景，

系統模型如下：在該區域中，一、總共有U個用戶，即{1,2,…,U}，有一個MEC服務器，二、無線鏈路為正交信道，鏈路不受其他信道的干擾；

應用程序模型如下：用戶i產生的任務T_i用表示，其中，w_i表示任務的工作負載，即所需的CPU周期數，D_i表示該用戶的計算能力，即每周期可以計算的數據bit，σ_i表示該用戶輸入和輸出數據量的比例，表示用戶i可以接受的最大延遲，此外，a為應用程序的卸載比例，a的取值為0-1之間，即用戶是否選擇卸載，或者選擇其應用程序的百分之多少卸載到MEC上；

通信模型如下：對于每一個用戶i，其傳輸速率r_i為

其中，B表示的是鏈路帶寬，p_i表示的是用戶i的傳輸功率，h表示的是用戶i與MEC服務器通信道路上的信道增益，d表示的是用戶與MEC服務器傳輸道路的距離，θ表示的是路徑損耗指數，N代表的是加性高斯白噪聲；

計算模型包括用戶在本地的計算模型，以及卸載在MEC服務器端的計算模型，每個計算模型包括時延與能耗兩部分：

其中，所述的用戶在本地的計算模型包括用戶i在本地的計算時延T_i^l和用戶i在本地的計算所消耗的能耗兩部分，

所述的用戶i在本地的計算時延T_i^l為：

其中f_i為用戶i的CPU頻率，

所述的用戶i在本地的計算所消耗的能耗為：

其中k_i為用戶i芯片結構的系數因子；

其中，卸載在MEC服務器端的計算模型包括用戶i的總的卸載時延和卸載能耗

所述用戶卸載在MEC服務器端的計算模型包括用戶i的總的卸載時延和計算卸載能耗兩部分；

其中，用戶i卸載到MEC服務器中時，總的卸載時延由計算時延、傳輸時延、結果回傳時延、以及等待時延組成，因此用戶i的總的卸載時延為：

其中指的是用戶在MEC端的計算時延，f代表MEC服務器的計算能力，表示的是任務上行鏈路的傳輸時延，表示的是結果回傳的時延，t_wait表示的是任務卸載到MEC時產生的等待時延；

用戶的計算卸載能耗為：

S2.對于整體網絡建立面向時延和能耗的聯合優化模型，具體模型為：

其中，C_total表示整體網絡中所有M個小區域的代價總和；

任意一個小區域的代價C為該區域內所有用戶進行任務處理時，所消耗的代價總和，第i個用戶進行任務處理時所消耗的代價C_i為：

其中，β指的是時延加權因子，Υ指的是能耗的加權因子，兩者之和為1；p表示用戶傳輸功率。

2.根據權利要求1所述的一種移動邊緣計算網絡中多目標優化的計算卸載方法，其特征在于：步驟S2中聯合優化模型的求解方法為GPSO優化算法，用于提高計算時效。

3.根據權利要求2所述的一種移動邊緣計算網絡中多目標優化的計算卸載方法，其特征在于：

所述GPSO優化算法是根據生物界中的種群行為衍生出來的啟發式算法，通過一定的優化規則更新種群并搜索最優解；在算法中，主要是通過不斷更新種群進行最優解的求解，具體求解過程如下：

步驟一：設置總的迭代次數為T，收斂標準為ε，令迭代次數t＝1，初始化S組用戶，每一組用戶的用戶個數為U，用戶維數為2，每一組用戶表示為向量組X′(t)＝{X′₁(t),X′₂(t),…,X′_U(t)}，s＝1,2,…S，其中X′_i(t)＝[X′_i,1(t),X′_i,2(t)]表示第s組第i個用戶選擇的策略，即選擇的卸載比例以及功率,i＝1,2,…U,X′_i,1(t)表示第s組第i個用戶的卸載比例，X′_i,2(t)表示第s組第i個用戶的功率；設置用戶選擇策略的取值范圍，卸載比例的值為0-1之間，功率的值處于0與設置的最大功率之間；

步驟二：設置迭代次數T₁，令迭代次數t₁＝1；

步驟三：計算S組用戶中每組用戶的適應度值，適應度函數為在區域內用戶產生的總代價，具體如下：

保留S組中最優的用戶適應度值，所述的最優的用戶選擇策略是指S組中適應度值最小的一組用戶對應的值；

步驟四：將上一步保留的最優選擇策略的一組用戶復制S/2份，組成一個“種馬種群”；

步驟五：從S組用戶中去除步驟三所求出來的最優個體，并在剩下的個體中運用輪盤賭的方法選擇S/2個個體，并與步驟四中的種馬種群共同組成新的S組用戶；

步驟六：開始進行進化操作；設置交叉算子p_c,變異算子p_m，首先采用部分匹配交叉算法對步驟五得到的新的S組用戶進行交叉重組操作，再將得到的結果進行變異操作，得到新的S組用戶；

步驟七：令t₁＝t₁+1,判斷是否滿足t₁T₁，如果不滿足，將新一代的S組用戶返回步驟三進行迭代；如果滿足，則進入下一步；

步驟八：設置迭代次數T₂，慣性權重ω，加速度常數c₁,c₂；令迭代次數t₂＝1；初始化S組用戶，此時S組用戶的值為步驟七所得到的新一代的S組用戶，并初始化每一組用戶的更新速度V′(t)＝{V′₁(t),V′₂(t)…V′_U(t)}，其中V′_i(t)＝[V′_i,1(t),V′_i,2(t)]表示每一組用戶中每個用戶卸載比例決策與功率選擇的更新速度；

步驟十：計算這S組用戶每組用戶的適應度值，同理，每一組用戶的適應度函數為上面所述的公式7，即在區域內用戶產生的總代價；并初始化每組用戶的最佳適應度值pbest，并根據每組用戶的最佳適應度值pbest得到所有組的最佳適應值gbest，gbest為所有S組用戶中的最小適應度值；

步驟十一：更新速度、S組用戶的策略選擇值，具體更新公式如下所示：

V′_i(t+1)＝ω*V′_i(t)+c₁*random(0,1)*(pbest_i-X′(t))+c₂*random(0,1)*(gbest_i-X′(t)) (10)

X′(t+1)＝X′(t)+V′_i(t+1) (11)

步驟十二：計算更新后的S組用戶的適應度值，對于每一組用戶，如果它的新的適應度值比該組歷史的最小的適應度值還要小，則將該組用戶的最佳適應度值pbest更新為新的適應度值；

步驟十三：根據每一組用戶的最佳適應度值更新歷史中出現過的所有用戶中的最佳適應值gbest，即最小的適應度值，并記錄其對應的那一組用戶的決策值；

步驟十四：t₂＝t₂+1，判斷是否滿足t₂T₂,如果不滿足，將更新后的S組用戶返回步驟十一進行迭代；如果滿足，則進入下一步；

步驟十五：t＝t+1，判斷是否滿足tT,是否達到收斂標準，如果不滿足，將更新后的S組用戶返回步驟二進行迭代；如果滿足，結束，輸出最終的所有用戶的最佳適應值gbest，以及其對應的那一組用戶的決策值，得到最優解。