[發明專利]一種多接入邊緣計算系統中的任務卸載與分派方法

有效

• 申請號: 202011222810.3
• 申請日: 2020-11-05
• 公開（公告）號: CN112512061B
• 公開（公告）日: 2022-11-22
• 發明（設計）人: 劉通;方璐;童維勤;李衛民
• 申請（專利權）人: 上海大學
• 主分類號: H04W24/02
• 分類號: H04W24/02;H04W24/06
• 代理公司: 上海上大專利事務所(普通合伙) 31205
• 代理人: 何文欣

1.一種多接入邊緣計算系統中的任務卸載與分派方法，其特征在于操作步驟如下：

步驟一，為邊緣計算系統進行建模；

步驟二，為計算任務的通信，執行模式進行建模；

步驟三，將任務卸載與分派問題進行形式化表示，并建模為多主從斯塔克伯格博弈；

步驟四，證明任務卸載與分派問題的斯塔克伯格均衡的存在性，提出其有效的算法；

在所述步驟一中，為邊緣計算系統進行建模；所述多接入邊緣計算系統包含M個充當邊緣節點的無線接入點和N個移動智能設備每個接入點都配備有比移動設備計算能力更大的邊緣服務器；用和表示每個接入點和每個移動設備的計算能力，即CPU頻率；每個移動設備i有一個要執行的計算任務其中s_i為該任務輸入數據大小，c_i為任務所需的CPU周期數；所有接入點通過核心網絡中的光纖互相連接；每個移動設備通過無線信道接入一個或多個接入點，每個移動設備一次只能與一個接入點通信；移動設備i可訪問的接入點集合由表示；接入點m擁有的無線頻譜帶寬為W_m，并且每個接入點根據頻分多址FDMA技術將自己的無線頻譜劃分為帶寬不等的多個子信道以分配給與其相連的移動設備；每個移動設備選擇在本地執行其任務，或者將任務卸載到可訪問的接入點，這稱為任務卸載決策；移動設備i的可行卸載決策集為其中0表示本地執行；o_i∈O表示移動設備i的特定卸載決策，并將定義為所有移動設備的卸載決策組合，給定特定的卸載決策組合O；將其任務卸載到接入點m的移動設備集合表示為接入點m收到移動設備i卸載的任務后，選擇在其邊緣服務器上執行該任務，或將任務分派給另一個接入點來執行，這稱為任務分派決策；使用表示接入點m用于處理任務的特定分派決策，而d_i，m＝m表示不分派任務然后，將接入點m做出的任務分配決策表示為并且作為所有接入點的任務分派決策組合；此外，其任務從接入點n分派到接入點m的移動設備集合由表示；因此，其任務最終在接入點m上執行的移動設備集合為

在所述步驟二中，為計算任務的通信，執行模式進行建模，并分別根據每個移動設備和每個接入點的任務完成時延來定義其成本函數；

首先，所有決定將任務卸載到接入點m的移動設備都必須共享接入點m擁有的無線頻譜資源；接入點m將其頻譜劃分為幾個子信道，且子信道的數量等于其中|·|表示集合中元素的數量；子信道帶寬應由接入點m合理分配，以實現最佳的任務處理效率；直接采用已被提出的最佳無線資源分配策略，在該策略中，接入點m分配給移動設備的帶寬計算方式為：與接入點m連接的移動設備i的數據傳輸速率表示為r_i，m＝μ_i，m·R_i，m，其中R_i，m是移動設備i占據接入點m整個頻譜帶寬時達到的最大數據傳輸速率，即此處的g_i，m是信道功率增益，受移動設備i和接入點m之間的距離以及無線介質的物理特性影響，σ_m是接入點m處的白噪聲功率，p_i是移動設備i的傳輸功率；此外，μ_i，m表示在給定了卸載決策組合O的情況下，接入點m分配給移動設備i的無線資源的比例；根據最優無線資源分配策略，最佳比例是

其次，每個計算任務都可在以下兩種執行模式的任一種模式下完成，每種執行模式所引起的任務完成時延是不同的；

(1)本地執行模式：如果移動設備i決定在本地執行其任務即o_i＝0，則此任務的完成時延僅包括在移動設備i上進行處理所花費的時間，即

(2)邊緣端執行模式：若任務被移動設備i卸載到接入點m，即則移動設備i向接入點m傳輸的輸入數據，傳輸時延計算為這受所有移動設備的卸載決策的影響；如果接入點m決定將任務分派給另一個接入點，接入點n，則將傳輸的輸入數據接入點m到接入點n所花費的時間的計算公式為其中r_i，m→n是任務從接入點m分派到接入點n時的數據傳輸速率；接入點之間有線連接的數據傳輸速率遠高于移動設備和接入點之間無線連接的速率；此外，設置r_i，m→m＝+∞，即以在接入點m不分派的情況下確保符號有意義；假設任務最終由接入點的邊緣服務器上執行，則任務的處理時延可計算為其中，是接入點n分配的用于執行的CPU頻率；由于可能在接入點n上處理多個任務，并且其邊緣服務器的計算能力有限，因此接入點n需要合理分配其計算資源，即CPU頻率；采用已提出的最優計算資源分配策略，下面將對此進行介紹；接入點n分配給任務的CPU頻率表示為其中v_i，n是分配給的計算資源的比例；根據最優計算資源分配策略，最佳比例是卸載到接入點的任務的完成時延表示為其中是一個指示函數，如果滿足條件*，則指標函數等于1；否則，該函數等于0；

最后，分別根據每個移動設備和每個接入點的任務完成時延來定義成本函數；一個移動設備承擔的成本是其任務的完成時延，這不僅取決于其自身的卸載決策，還取決于其他移動設備的卸載決策和接入點的分派決策組合；將移動設備的成本函數定義為每個接入點的成本函數是卸載給它的所有任務的總完成時延；因此，接入點的成本函數表示為

在所述步驟三中，將任務卸載與分派問題進行形式化表示，并建模為多主從斯塔克伯格博弈：考慮由自治且自私的移動設備和接入點組成的多接入邊緣計算系統中的聯合任務卸載和分派問題，即每個移動設備和接入點都會分別做出其任務卸載或分派決策以將其各自的成本降至最低；由于每個任務的完成時延取決于所有移動設備的卸載決策組合和所有接入點的分發決策組合，而且移動設備的卸載決策與接入點的分派決策高度相關，將任務卸載和分派問題建模為多領導者多跟隨者斯塔克伯格博弈，其中移動設備是領導者，接入點是跟隨者；

在所述步驟四中，根據以上建模過程，首先證明任務卸載與分派問題的斯塔克伯格均衡的存在性，其次，提出一種有效的算法來求得斯塔克伯格均衡，該均衡包括移動設備的卸載策略子均衡和接入點的分派策略子均衡；

所述步驟四中的算法如下：將每個移動設備i的混合卸載策略定義為Π_i＝(π_i，0，π_i，1，…，π_i，M)，其中，是移動設備選擇本地執行，即o_i＝0，或選擇卸載任務到接入點即的概率且基于Q-值的移動設備卸載策略求解方法操作步驟如下：

1)所有移動設備根據自己的混合卸載策略選擇一個可選卸載決策組成卸載策略集合O；

2)給定O，所有接入點執行分派決策算法得出分派決策均衡D；

3)所有移動設備根據下方公式更新自己的Q-值，其中θ_i∈[0，1)是移動設備i的學習率

4)所有移動設備根據玻爾茲曼探索機制更新自己的混合卸載策略，其中λ_i是可調正參數，用于調整探索與利用之間的權衡

5)重復以上四個步驟直到所有移動設備的混合卸載策略收斂；

給定O，上述步驟三中的接入點的分派策略子均衡的求解方法如下：

為所有接入點依次計算并更新自己的最優響應分派策略，最優響應策略計算公式為

重復步驟一直到所有接入點的分派策略都不再改變。