[發明專利]一種公平感知任務調度和資源分配方法

有效

• 申請號: 202110744708.8
• 申請日: 2021-07-01
• 公開（公告）號: CN113472426B
• 公開（公告）日: 2022-06-28
• 發明（設計）人: 趙明雄;王子睿;楊昭杰;肖一明;張賢琪;張榕倩
• 申請（專利權）人: 云南大學
• 主分類號: H04B7/185
• 分類號: H04B7/185;H04W16/10;H04W52/34;H04W72/04
• 代理公司: 成都市鼎宏恒業知識產權代理事務所(特殊普通合伙) 51248
• 代理人: 謝敏

1.一種公平感知任務調度和資源分配方法，其特征在于，該方法包括以下步驟：

首先考慮了一個基于頻分多址的無人機啟用MEC網絡，其中多個地面終端節點分別表示為：并且它們隨機分布在地面上，記作：W_k＝(x_k,y_k)^T；定義整個導航時間為T，Q₀和Q_F分別表示3D笛卡爾坐標系中的原點和終點；無人機在固定高度H的水平面飛行，在導航過程中為GN地面終端節點提供數據計算和緩存服務，GN保持靜止；其中T被劃分為N個份，每個份的長度為τ＝T/N以秒為單位，記為q[n]＝(x[n]，y[n])^T為無人機在第n個時隙的位置，V_max為無人機的最大速度；由于τ很小，q[n+1]和q[n]之間的平均速度近似為瞬時速度||v[n]||，由下式給出

無人機作為移動邊緣計算服務器為物聯網設備提供計算資源和數據緩存服務；其中||·||表示歐氏距離，v[n]不能超過其最大速度Vmax，||q[n+1]-q[n]||≤τVmax；

此外，無人機與第n個時隙內的第k個GN之間的距離為

所述方法包括第一步驟為，設定傳輸模型：

假設無人機和第k個GN之間的無線信道由視線LoS鏈路主導；將第k個GN到第n個時隙處的無人機的信道增益表示為h_k[n]，由下式給出：

其中β₀表示參考距離d₀＝1m處的信道增益；總帶寬B在GN之間共享，分配

給第k個GN的幾率為b_k[n]，并且必須滿足：

因此，以每秒比特bps為單位的第k個GN的可實現速率為：

其中p_k是第k個GN的發射功率，N₀是無人機的噪聲功率譜密度；

所述方法包括第二步驟為，設定任務執行模型：

在飛行過程中，每個GN運行一個主循環應用程序，生成多個位，根據具體需要針對不同的操作：本地計算，計算卸載或緩存卸載進行處理，分別將S_k和S_k[n]表示為第k個GN的總比特數及其在第n個時隙調度的比特數，滿足每個GN的每個時隙內的調度比特都有一個下限和一個上限，

其中表示要處理的最小生成比特，以確保GN_S它們之間的公平性；

表示根據GN_S之間共享的無人機的計算能力和緩存容量調度的最大合理工作負載，使支持無人機的MEC網絡更加穩定；

無人機和第k個GN之間的信道容量的下限由下式給出為：

定義一個三元變量決定第k個GN處調度比特，其中表示本地計算，代表計算卸載，表示緩存卸載；

滿足以下約束

此外，計算每個GN的總大小應滿足：

保證不同類型卸載服務之間的公平性；

其中表示在UAV或第k個GN處執行計算的總位數；

如果執行緩存，則會分配緩沖區空間，總緩存位不能超過無人機的緩存容量，由下式給出

其中C代表無人機的最大緩存容量；

如果調度位在本地執行，則GN處對延遲的處理為：

其中θ_k表示第k個GN處的CPU計算強度；

如果卸載給無人機，則應考慮卸載延遲，包括傳輸延遲和處理延遲；由于寫入緩存的時間忽略不計，所以處理延遲僅針對計算任務，因此，卸載延遲為：

其中表示計算延遲，表示上行傳輸時延，θ表示在UAV上計算1位所需的CPU周期；此外，總分配的CPU頻率不能超過無人機的總計算能力F；

其中代表無人機分配給第k個GN的計算頻率；

每個時隙調度比特的處理延遲受到以下的約束：

第k個GN處的應用程序應該在給定的時間內完全執行T_k：

所述方法包括第三步驟，設定能耗模型，包括

1)GNs的能耗：給定處理器的計算能力f_k，處理器的功耗建模為(焦耳每秒，其中K_k表示與第k個GN處配備的處理器芯片相關的計算能效系數；考慮到公式(11)對于的處理延時，本地計算的能量消耗由下式給出

如果卸載到無人機，則在第k個GN處傳輸的能量消耗為：

而且，第k個GN的總能量消耗不能超過其能量預算：

2)無人機能耗：在卸載過程中，無人機為這些卸載的比特分配計算資源或緩存空間；以類似的方式，對于計算卸載，執行來自第k個GN的比特的能量消耗為：

其中η是無人機的CPU能耗系數；從第k個GN緩存比特的能耗為：

其中ω為無人機存儲硬盤相關的緩存能量系數；

對于無人機推進能量消耗采用旋翼能量模型，由下式給出：

其中P₀和P_i表示懸停狀態下的恒定葉片輪廓功率和感應功率；Q_tip是轉子葉片的葉尖速度，v₀表示懸停時的平均轉子感應速度，P_C是與環境相關的常數值；因此，無人機的總能耗為：

定義Q＝{q[n]}，其中

所述方法包括第四步驟為，問題的制定；通過聯合優化無人機的軌跡Q、任務決策A和比特調度S、帶寬B和計算資源分配F來最小化無人機的能耗；因此，優化問題為：

滿足

q[0]＝Q₀，q[N]＝Q_F，(23c)

其中(23i)確保根據信道條件成功卸載，(23k)保證不同操作之間的公平性，(23o)和(23p)是延遲要求，而(23l)，(23m)和(23q)用于任務調度和資源分配；

所述方法包括問題P是一個MINLP問題，采用BCD方法來解耦P中的這些變量；

將原始問題分為三個更易于管理的子問題：

1)P_T：無人機軌跡優化Q，

2)P_S：任務決策和位調度，A和S，

3)P_R：UAV的通信和計算資源分配B和F，并根據BCD方法以替代方式優化這些子問題；

所述方法包括BCD方法的應用；

首先，根據給定的任務決策和比特調度A和S，通信和計算資源分配B和F，在其內部循環的第i次迭代中獲得最佳軌跡Q^*；

其次，利用新獲得的軌跡Q^*，根據線性規劃求解器和BB算法在其內循環中迭代優化任務決策和位調度，A和S；

第三，使用求解器CVX，借助輔助變量推導出最優的(B^*，F^*)，這使得P_R與新實現的(Q^*，A^*，S^*)相凸；

最后，將在外循環中迭代更新導出的{Q，A，S，B，F}；

所述方法包括BCD方法為將按照基BCD的迭代方法提出無人機軌跡、任務決策和比特調度、通信帶寬和計算資源分配的聯合優化，如下所示；

A：無人機的軌跡優化

給定{A，S，B，F}，無人機Q的軌跡從以下問題導出：

P_T：

滿足：(23c)-(23e)(23i)(23o)-(23q)，

利用SCA技術在輔助變量的幫助下處理非凸性從而使目標函數相對于v[n]是凸的；在第i次迭代時使用一階泰勒展開式，o[n]進一步轉化為以下給定點(o_i[n]，v_i[n])的不等式，

引入松弛變量來處理約束中與r_k[n]相關的非凸部分，并由下式給出：

其中和是常數速率和第i次迭代的一階導數，其中di＝||q[n]-w_k||²+H²；最終，P_T轉化為如下凸優化問題：

滿足

(23c)-(23e)

其中P_T1通過求解器求解；

B：任務決策和位調度

使用優化的軌跡Q^*并給定{B，F}，通過求解以下優化問題來導出任務決策和比特調度(A，S)，使無人機的能耗最小化：

滿足(23a)(23b)(23j)-(23q)；

提出了一種基于BCD的算法將P_S劃分為兩個子問題，如下所示：

1)關于位調度S的線性規劃(LP)問題，通過線性規劃求解器解決；

2)關于任務決策A的整數線性規劃(ILP)問題，通過BB解決；通過構建搜索樹和計算邊界值，BB通過遞歸遍歷來獲得精確解；

C：資源分配

基于新推導出的{Q^*，A^*，S^*}，通過求解P_R獲得通信帶寬和計算資源分配，進一步降低無人機的能耗

P_R：

滿足(23f)-(23i)(23m)(23o)-(23q)；

由于與延遲要求(23o)、(23p)和能源供應(23q)相關的約束是非凸和非線性的，因此引入輔助變量來處理這些強耦合約束

其中并且(31)的相對于b_k[n]是凹的；因此，P_R是轉化為以下問題：

P_R1：

滿足

(23f)(23g)(23h)(23m)(31)，

通過CVX求解；

所述方法包括CVX的算法；

整體算法

輸入：給定初始點{Q_i，B_i，A_i，F_i，S_i}，其中i＝0；

輸出：{Q^*，A^*，S^*，F^*，B^*}；

1)循環

2)給定{B_i，A_i，F_i，S_i}，通過基于算法一求解P_T1來優化無人機的軌跡Q_i+1；

3)給定{B_i，F_i}和新推導出的Q_i+1，從步驟4到步驟8得到任務決策和位調度{A_i+1，S_i+1}，其中在P_S的內循環中初始化j＝0；

4)循環

5)在第j次迭代中求解具有給定A^j，*的LP問題以獲得S^j，*；

6)在第j次迭代時用新獲得的S^j，*解決ILP問題并推導出A^j，*；

7)更新A^j＝A^j，*，j＝j+1；

8)直到收斂到容錯精度；

9)利用新導出的{A_i+1，S_i+1，Q_i+1}，通過求解P_T1來優化通信帶寬和計算資源分配{B_i+1，F_i+1}；

10)更新變量Q_i＝Q_i+1，A_i＝A_i+1，S_i＝S_i+1，B_i＝B_i+1，F_i＝F_i+1；

11)直到收斂到容錯精度。