[發明專利]一種不確定網絡環境中的任務卸載和資源分配方法

有效

• 申請號: 202110635596.2
• 申請日: 2021-06-08
• 公開（公告）號: CN113242568B
• 公開（公告）日: 2022-05-03
• 發明（設計）人: 姚枝秀;夏士超;陳曾平;王婧琳;李云
• 申請（專利權）人: 重慶郵電大學
• 主分類號: H04W24/02
• 分類號: H04W24/02;H04W24/06
• 代理公司: 重慶輝騰律師事務所 50215
• 代理人: 盧勝斌

1.一種不確定網絡環境中的任務卸載和資源分配方法，其特征在于，包括以下步驟：

利用隨機規劃理論將任務在MEC服務器的排隊等待時間建模為一組隨機參數，并將任務卸載過程建模為兩階段卸載模型；

基于兩階段卸載模型，在時延約束條件下，以最小化系統總能耗為目標，將優化問題建模為基于兩階段隨機規劃的任務卸載和資源分配問題；在兩階段卸載模型中，將卸載決策過程分為兩個階段，包括：

第一階段的決策變量為任務的傳輸功率，即用戶在沒有觀察到不確定性MEC服務器排隊等待時間的情況下，考慮未來所有可能排隊時間的影響，做出第一階段的傳輸功率分配策略p_i；

第二階段的決策變量為MEC服務器的CPU頻率資源，即當任務上傳至MEC服務器，排隊等待時間實現已知，在獲得排隊等待時間和第一階段的傳輸功率分配策略p_i的條件下，MEC服務器將根據約束條件采取追索動作，對第一階段策略進行補償；

基于兩階段隨機規劃的任務卸載和資源分配問題表示為：

約束條件：

f_i^l,min≤f_i^l≤f_i^l,max；

f^e,min≤f_i^l≤f^e,max；

T_i^loca(f_i^l)≤τ_i；

π_i∈{0,1}；

其中，π＝{π₁,π₂,...,π_N}表示任務卸載決策集合，N為請求任務處理的用戶數；表示本地CPU頻率資源分配策略集合，f_i^l表示第i個用戶的本地CPU頻率資源分配策略；表示所有組合場景下MEC服務器CPU頻率資源分配策略集合，其中表示第i個用戶在MEC服務器的排隊等待時間的集合；p＝{p₁,p₂,...p_N}表示用戶任務傳輸功率分配策略集合，p_N表示第N個用戶任務傳輸功率分配策略；π_i表示第i個用戶的卸載決策；κ_i為第i個用戶芯片構架相關的有效能量系數；D_i為待計算任務的任務量大小；L_i表示單位bit任務所需要的CPU周期數；R_i為第i個用戶將任務卸載到MEC服務器的傳輸速率；γ為與MEC服務器芯片架構相關的有效能量系數；τ_i表示計算完成該任務的最大時延要求；表示組合場景的期望；和分別表示傳輸功率的最小值和最大值；f_i^l,min和f_i^l,max分別表示本地CPU頻率的最小值和最大值；f^e,min和f^e,max分別表示MEC服務器CPU頻率的最小值和最大值；T_i^wait(ω)表示組合實現為ω時第i個用戶的排隊等待時間；T_i^loca(f_i^l)為第i個用戶本地計算的時延；T_i^tran(p_i)為第i個用戶選擇將任務卸載到MEC服務器處理時任務上傳的通信時延；為第i個用戶在MEC服務器的計算時延；

利用隨機模擬方法將基于兩階段隨機規劃的任務卸載和資源分配問題轉化為樣本均值近似問題，表示為：

約束條件：

f_i^l,min≤f_i^l≤f_i^l,max；

f^e,min≤f_i^l≤f^e,max；

T_i^loca(f_i^l)≤τ_i；

π_i∈{0,1}；

其中，S＝K^N表示該樣本組合場景的數量，K為從第i個用戶的場景集合Ω_i中抽取的獨立同分布樣本數量；

將樣本均值近似問題解耦為本地計算資源分配子問題、傳輸功率和邊緣計算資源聯合分配子問題，以及卸載決策子問題；

采用標準拉格朗日乘子法獲得所述本地計算資源分配子問題的最優分配策略，即若第i個用戶的任務卸載決策為0，即第i個用戶將任務在本地處理，則任務在本地計算時最優CPU頻率分配策略為：

其中，f_i^l*為任務在本地計算時最優CPU頻率分配策略；

采用遺傳算法獲得所述傳輸功率和邊緣計算資源聯合分配子問題的最優分配策略，若第i個用戶的任務卸載決策為1，即第i個用戶將任務卸載到服務器計算，則通過遺傳算法計算最優的卸載策略，具體包括：

將每一個可行的傳輸功率進行浮點向量編碼，每一個浮點向量表示一個染色體，浮點向量維數與解向量維數一致；

從用戶i傳輸功率的可行域中隨機產生一個點，并檢驗其是否滿足用戶傳輸時延小于最大傳輸時延要求，如果滿足則作為一個染色體，否則，重新產生一個隨機點，直到滿足約束條件，重復以上過程M次，產生M個染色體作為初始種群，記為p_i,1,p_i,2,...,p_i,M；

對于每個染色體p_i,m，求解其適應度函數，則染色體p_i,m的評價函數表示為：

eval(p_i,m)＝a(1-a)^m-1,m＝1,2,...,M；

其中，eval(p_i,m)為染色體p_i,m的評價函數；a為常數，且a∈(0,1)

并根據適應度求其評價函數，且對于每個染色體評價函數值越大，被選擇產生后代的概率越大，其中適應度為樣本均值近似問題函數；

對于染色體p_i,m，計算前m個染色的累積概率從區間(0,q_i,M)中生成一個隨機數r，若滿足q_i,m-1＜r＜q_i,m，q_i,0＝0，則選擇染色體p_i,m作為父本繁殖下一代，依此規則選擇M個染色體；

定義P_c為交叉概率，則種群中有期望值為P_c×M個染色體進行交叉操作，即假設p_i,1和p_i,2為要交叉的兩個染色體，則從區間(0,1)中生成一個隨機數c，直到p′_i,1＝cp_i,1+(1-c)p_i,2和p′_i,2＝(1-c)p_i,1+cp_i,2滿足用戶傳輸時延小于最大傳輸時延要求，則p′_i,1和p′_i,2將代替原染色體p_i,1和p_i,2成為兩個新的染色體；

定義P_u為變異概率，則種群中有期望值為P_u×M個染色體進行變異操作，即假設p_i,1為要變異的染色體，隨機選擇一個變異方向d，從中生成一個隨機數α，直到p′_i,1＝p_i,1+αd滿足約束條件，則p′_i,1將取代原染色體p_i,1成為新的染色體；

經過選擇、交叉和變異操作，可以得到一個新的種群，并準備進行下一代進化，如果上述步驟達到了給定的循環次數，則遺傳算法終止；算法終止后，從最后一代選擇一個適應度最高的染色體，即得到優化問題的全局最優解；

通過分析本地計算和邊緣計算的時延估計和能耗預算獲得所述卸載決策子問題的最優策略，表示為：

其中，為最優卸載決策；f_i^l*為任務在本地計算時最優CPU頻率分配策略；為每個場景下MEC服務器最優CPU頻率分配策略；為第i個用戶的最優發射功率；

用戶基于所述本地計算資源分配子問題的最優分配策略、傳輸功率和邊緣計算資源聯合分配子問題的最優分配策略，以及卸載決策子問題的最優策略進行任務卸載。

2.根據權利要求1所述的一種不確定網絡環境中的任務卸載和資源分配方法，其特征在于，每個場景下MEC服務器最優CPU頻率分配策略表示為：

其中，T_i^tran(p_i,m)為第i個用戶選擇發射功率為p_i,m時將任務卸載到MEC服務器處理時任務上傳的通信時延。