[發明專利]MEC中近似最優化與基于強化學習的任務卸載方法

有效

• 申請號: 201911300667.2
• 申請日: 2019-12-17
• 公開（公告）號: CN110971706B
• 公開（公告）日: 2021-07-16
• 發明（設計）人: 夏秋粉;婁錚;徐子川
• 申請（專利權）人: 大連理工大學
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 大連理工大學專利中心 21200
• 代理人: 溫福雪;侯明遠

1.一種MEC中近似最優化與基于強化學習的任務卸載方法，由兩部分組成：一部分是基于整數線性規劃的近似最優化方法，通過松弛-過濾-舍入的方法，給出近似最優的卸載策略與資源分配策略；另一部分是基于強化學習理論，使用線性回歸方法預測并給出卸載策略，然后在此基礎上通過深度神經網絡進一步給出相應的最優資源分配策略；其特征在于，

(1)移動邊緣計算卸載模型的具體建立過程如下：

(1.1)考慮一個由多個邊緣云服務器組成的邊緣計算網絡其中分別代表一個邊緣云服務器、一個數據中心以及一個無線接入點；邊緣云服務器和數據中心都用來卸載用戶發送來的計算任務，無線接入點負責連接用戶與服務器并進行數據的傳輸；使用L_h表示計算服務器，即使用C(L_h)以及C(AP_k)分別代表服務器的計算能力和接入點的帶寬容量，使用n_ap表示無線接入點分配給每個用戶的傳輸帶寬；

(1.2)定義用戶集合U＝{u_i|1≤i≤M}；一個用戶可連接到任何在他的通信范圍之內的接入點AP，以此來連接到一個CL或DC；在這里，考慮一個較長的監控時期T，并將其細分為數個等長的短時期t∈T；假設每一次決策都是發生在一個短周期t中；

(1.3)定義一個待卸載的計算任務為τ_i,t＝W_i,t,t,f_i,t,D(τ_i,t)，其中W_i,t為任務的計算量，f_i,t為任務的大小，D(τ_i,t)為任務的延遲需求，即必須在此時間內完成這項任務；

(2)計算任務運行模型與問題模型的建立過程如下：

(2.1)當任務被卸載到某一個云計算服務器上時，它的運行時間為

其中，n_ap表示無線接入點分配給每個用戶的傳輸帶寬，y_i,t,h代表卸載指示變量，當其值為1時表示進行卸載，為0時表示在本地運行；p(L_h)表示L_h的計算速度；α為一個常數，表示計算結果與原始任務大小的比例；

(2.2)當計算任務在用戶設備本地執行時，它的運行時間為

其中，p(u_i)表示用戶設備的計算速度；

(2.3)根據上述關系式，得當任務被卸載到服務器上運行時的用戶設備能耗：

其中，z_i,t,k為指示變量，表示任務τ_i,t是否經由AP_k卸載；β_k為一常數，表示傳輸單位數據時的能耗；P_idle和P_t分別為用戶設備的閑時功率和傳輸時功率；

(2.4)同樣得任務在用戶設備本地運行時的用戶設備能耗：

其中，表示用戶設備的計算時功率；

(2.5)基于上述定義，以最小化所有用戶設備的能耗為目標，制定整數線性規劃問題如下：

相關約束如下：

y_i,t,h,z_i,t,k∈{0,1}#(12)

其中，(6)式確保每一個被卸載至云服務器的任務都必須被分配一個用來傳輸數據的無線接入點；(7)式確保所有在某臺云服務器上運行的計算任務的計算量不能超過這臺服務器的計算能力上限；(8)式確保所有經由某無線接入點進行傳輸的用戶設備所分配的帶寬資源之和不能超過這個無線接入點的帶寬上限；(9)式中表示設備i的剩余電量，此項約束確保在時期T內，用戶設備所消耗的總能量不能超過設備自身剩余的電量；(10)式和(11)式確保所有任務在遠程或是本地執行時不能超過它所規定的延遲要求，其中D(τ_i,t,MD)為在用戶設備本地運行任務所需時間；(12)式確保y,z兩個變量的取值必須是0或1；

(3)為了求解上述優化問題，首先對整數線性規劃問題的整數約束條件進行松弛操作，以使其轉化為可解的線性規劃問題；然后對求解結果進行過濾操作，以去除其中不滿足原約束條件的候選解；最后，比較各個候選解的執行性能，只保留性能最優的候選解作為最終解，舍去其余部分；最終解包含每一個用戶的任務卸載策略與對應的資源分配策略；具體過程如下：

(3.1)首先對問題進行松弛處理，去除原問題中的約束(12)式，將其轉化為線性規劃問題求解，得到最優解(y^*,z^*)；

(3.2)接下來根據求得的最優解，對所有候選卸載地點進行過濾；將原問題的目標函數定義為兩個函數之和F(y)+θ(z)，其中：

為了將邊緣云服務器和無線接入點中比在用戶設備本地運行計算任務時會產生高于(1+∈)倍的能量消耗的候選解過濾掉，首先要定義兩個值和分別代表候選解中任務計算量與邊緣云服務器計算能力之比的最大值、候選解中計算任務數據量與無線接入點帶寬容量之比的最大值：

再定義延遲所有計算任務在每個邊緣云服務器的計算時間與計算任務的延遲要求之比的最大值，以及在用戶設備本地的計算時間與計算任務的延遲要求之比最大值，取二者中的最小值記為

對于任務τ_i,t，將過濾后的候選運行地點與候選無線接入點分別記為L_i,t和AP_i,t，則過濾規則為：

其中

θ_i,t(z)與之同理；此外，? 、σ與φ為3個常量，用以控制過濾規則；通過對這三個常量的調整得到更加合理的過濾結果；

由此得到原問題(5)式對應的線性規劃問題的可行解(y′,z′):

(3.3)下面對上一步中得到的可行解進行舍入操作；首先根據線性規劃問題的最優解(y^*,z^*)選擇計算消耗最小的任務τ_i,t，對于這個任務，擬將其放置在候選地點L_i,t中產生計算消耗最小的地點θ(h)，即令y_i,t,θ(h)＝1；對于此計算任務，如果在用戶設備本地運行會產生更少的功耗，則令y_i,t,h＝0，其中L_h∈L_i,t；重復上述過程，直到所有的計算任務都被分配到一個指定的運行地點；此時，即得到問題(5)式的一個最優可行解，即滿足約束條件的、使得所有用戶設備的能耗最低的計算任務卸載策略與資源分配策略；

(4)針對問題(5)式，給出另一種基于強化學習理論的在線解法；與上述步驟(3)解法不同，在線算法在每個時間段給出當前的最優解，而不需要在收集所有時間段的信息后再一一求解各時間段的最優解；原問題要求解的是使得所有用戶設備的能耗最低的計算任務卸載策略與資源分配策略；首先給出基于強化學習理論的計算任務卸載策略的求解過程：

(4.1)首先根據強化學習理論，定義出待解決的問題中的幾個重要部分；強化學習過程需要將原問題轉化為一個馬爾科夫決策過程，即由狀態、動作、獎勵三部分組成的過程；系統從所處的某一狀態開始，根據當前狀態選擇動作并加以執行，而后到達新的狀態，并取得新狀態對應的獎勵；定義每個用戶設備在t時間段的剩余電量R_residual為其在t時間段所處的狀態；在每個狀態下，用戶設備的可選動作為其中三個決策動作分別代表無動作、將計算任務在本地運行、將計算任務卸載到邊緣云服務器運行；每個狀態的獎勵信息R_t定義為到達此狀態時的能量消耗的相反數-E_i；

(4.2)根據上述定義，從起始時刻t＝1起，對于用戶i進行如下操作：計算當前狀態下獲得的獎勵R_t與上一狀態下的獎勵R_t-1之差Δ；然后比較Δ與δ，其中δ為預定義的閾值；若Δ大于δ，則首先通過線性回歸方法，通過過去p個狀態下的計算任務能量消耗來預測時刻t的計算任務τ_i,t的能量消耗：

E(τ_i,t)＝a₁·E(τ_i，t-1)+a₂·E(τ_i，t-2)+…+a_p·E(τ_i，t-p)#(23)

接下來計算所處時刻的待執行計算任務τ_i,t卸載到邊緣云服務器時產生的能耗，將其與預測值E(τ_i,t)比較；如果采取卸載動作產生的能耗更少，則將卸載至邊緣云服務器作為計算任務τ_i,t的卸載策略，輸出動作a＝1；否則將在用戶設備本地運行作為卸載策略，輸出動作a＝0，即不進行卸載；在每個時間段執行上述過程，即在線地得到每個時間段中每個用戶各自的卸載策略；

(5)由上述過程得到的卸載策略將決定哪些計算任務在用戶設備本地運行，哪些計算任務將被卸載到邊緣云服務器上運行；對于將要卸載到邊緣云服務器上運行的任務，下面給出基于深度強化學習方法的在線資源分配策略，以決定卸載過程中所使用的無線接入點以及作為目標的邊緣云服務器，具體過程如下：

(5.1)首先將邊緣網絡結構抽象為一個帶權有向圖Graph(V,Eb,w)；其中，V是頂點集合，Eb是邊集合，w是邊的權重集合；對于一條邊(u,v)∈Eb，w(u,v)代表它的權重；集合V中包含一個用戶頂點、數個無線接入點頂點以及數個邊緣服務器頂點；用戶頂點與每個無線接入點頂點之間都有一條有向邊，由前者指向后者；而每個無線接入點頂點都與至少一個邊緣服務器頂點之間有一條有向邊，同樣由前者指向后者；兩個頂點之間有有向邊，代表源頂點沿此方向連接到目標頂點；每條有向邊的權重所代表的含義由它所指向的頂點來決定：如果一條有向邊指向一個無線接入點頂點，則它的權重代表這個無線接入點的帶寬容量；如果一條有向邊指向一個邊緣云服務器頂點，則它的權重代表這個邊緣云服務器的計算能力；也就是說，一個無線接入點的帶寬或邊緣云服務器的計算能力越大，則指向它的邊的權重也就越大；這樣得到網絡結構的圖的表達形式，同時網絡結構的參數也被以權重的方式體現在圖中；

(5.2)然后使用structure2vec算法構建一個圖嵌入網絡，為圖中的每一個頂點計算其對應的圖嵌入值向量，目的是將圖中每個頂點的結構信息轉化為向量信息，以便于將其作為后續神經網絡的輸入；其中每個頂點的圖嵌入值由多次迭代生成；具體圖嵌入網絡如下：

其中，代表頂點v在第t次迭代后的圖嵌入值，初始值默認為0；N(v)代表與頂點v相鄰的頂點的集合；為與頂點v相鄰的頂點u在第t次迭代后的圖嵌入值；relu為線性整流函數，θ為神經網絡參數；x_v為指示器變量，代表頂點v是否屬于局部解，初始化為0；可見經過數次迭代計算后，圖中每一個頂點的特征值都會由其自身以及相鄰頂點、相鄰邊的特征所共同決定；

(5.3)將上述的圖嵌入網絡結合深度強化學習模型，構建深度強化學習網絡；網絡的輸入為上一步求得的圖嵌入值，輸出為對應輸入頂點的狀態-動作值表達式為：

其中，Θ為網絡參數θ的集合；h(S)為當前整個系統的狀態，由當整個圖的圖嵌入值來表示；

(5.4)構建如上兩個神經網絡后，還需初始化經驗重放緩存；當收到卸載請求時，將圖中一個頂點v的信息作為輸入，由式(24)迭代得到該頂點的圖嵌入值后，將嵌入值作為式(25)的輸入得到對應頂點的狀態-動作值對于所有頂點進行上述操作后，將其中狀態-動作值最大的頂點作為卸載路徑中的一個頂點，并記x_v＝1；對于圖中每個頂點，重復上述步驟，直到將邊緣云服務器頂點放置到卸載路徑集合V_t中；此時，卸載路徑中的頂點就是最優的資源分配決策，其中包括對于本次卸載任務所應連接的無線接入點以及邊緣云服務器；至此，即可在線地得到每一次卸載請求對應的網絡資源和計算資源分配策略；

(5.5)在得到神經網絡輸出的策略同時，獲取此策略帶來的獎勵R_t，此處的收益定義為本分配策略所產生的能耗的相反數然后將本次決策過程的狀態信息S_t、決策結果V_t、獎勵R_t，以及所到達的新的狀態信息S_t+1存儲至經驗重放緩存中作為歷史經驗；在隨后的決策過程中，每隔N次決策過程，從緩存中隨機抽取一批歷史經驗訓練神經網絡參數；方法為使用隨機梯度下降法，沿使收益增加的方向調整神經網絡參數