基于卸載策略的物聯(lián)網(wǎng)邊緣計算任務(wù)調(diào)度優(yōu)化

摘要：移動邊緣計算 （Mobile Edge Computing， MEC） 通過將計算任務(wù)卸載到邊緣服務(wù)器， 為用戶提供了低延時、低能耗的服務(wù)，解決了傳統(tǒng)云計算的不足。在移動邊緣計算中，如何進 行卸載決策是提供低延時、低能耗服務(wù)的關(guān)鍵技術(shù)之一。除此之外，由于無線信道的帶寬資源 有限，不合理的帶寬分配會使用戶設(shè)備的能耗和延時增加，因此如何進行合理的資源分配也是 邊緣計算實現(xiàn)的關(guān)鍵。為聯(lián)合優(yōu)化時延、能耗與計算資源，本文提出了一個基于蒙特卡洛樹搜 索的多通道探索算 法 （Multi-Channel Search Algorithm based on Monte Carlo Tree Search， MCS-MCTS）。首先，以延時和能耗的成本為優(yōu)化目標，將計算資源分配決策及傳輸功率建模 決策建模為凸優(yōu)化問題，采用梯度下降法求解最優(yōu)傳輸功率分配問題，通過拉格朗日乘子法及 卡羅需-庫恩-塔克 （Karush-Kuhn-Tucker， KKT） 條件求解最優(yōu)計算資源分配問題。隨后，通過 MCS-MCTS 算法處理二進制卸載決策問題，為避免搜索結(jié)果陷入局部最優(yōu)，引入模擬退火算 法。數(shù)值結(jié)果表明，MCS-MCTS 算法能在線性相干時間內(nèi)得到接近最優(yōu)的卸載決策與資源分 配決策，與現(xiàn)有的啟發(fā)式搜索算法相比，該算法可以在減少時間復(fù)雜度和提高系統(tǒng)能量有效性 的同時，達到接近最優(yōu)的性能。

關(guān)鍵詞：物聯(lián)網(wǎng)；移動邊緣計算；深度學(xué)習(xí)；任務(wù)卸載；資源分配

中圖分類號：TN915

文獻標志碼：A

隨著人工智能、移動通信與物聯(lián)網(wǎng)設(shè)備的日益 普及，涌現(xiàn)出了在線游戲、虛擬現(xiàn)實等眾多新型、高 需求量的應(yīng)用，此類應(yīng)用需要無線設(shè)備終端擁有龐 大的計算能力，從而導(dǎo)致更多的能量消耗。但是，目 前設(shè)備終端計算能力是有限的，導(dǎo)致設(shè)備的硬件設(shè) 施條件要求更高，無法滿足多樣化的應(yīng)用需求，設(shè)備 對資源消耗過高的應(yīng)用無法進行實時解決。因此， 如何在設(shè)備上提高數(shù)據(jù)計算處理能力，同時解決高 時延與高能耗的問題成為了當(dāng)前研究熱點。隨著第 五代移動通信技術(shù)的核心技術(shù)之一—移動邊緣計 算技術(shù)[1] 的不斷發(fā)展，無線設(shè)備的計算能力得到了顯 著的提升，移動邊緣計算（MEC）將計算資源和服務(wù) 直接部署在終端的邊緣服務(wù)器，以相對較低的網(wǎng)絡(luò) 延遲傳輸數(shù)據(jù)信息，從而提供更快的響應(yīng)時間和更 低的能量消耗，滿足了當(dāng)前市場對于低時延和低功 耗的需求。

當(dāng)前國內(nèi)外對移動邊緣計算任務(wù)卸載技術(shù)的研 究主要集中于能耗與延時的降低方面。Cui 等[2] 提出了一種新的基于多用戶細粒度的物聯(lián)網(wǎng)卸載調(diào) 度方法來解決 MEC 中細粒度卸載的能量和延遲問 題，將計算卸載視為一個約束多目標優(yōu)化問題，然后 提出了一種改進的 NSGA-II 算法來解決該問題，該 算法可以實現(xiàn)局部和邊緣并行處理，有效地降低了 延遲和能耗。Dai 等[3] 在工業(yè)物聯(lián)網(wǎng)提出了一種使 用 D2D 輔助 MEC 網(wǎng)絡(luò)中整合遷移成本和卸載意愿 的共同卸載框架，在此基礎(chǔ)上設(shè)計了一種基于學(xué)習(xí) 的任務(wù)協(xié)同卸載算法，該算法使工業(yè)物聯(lián)網(wǎng)設(shè)備能 夠從候選邊緣節(jié)點中觀察和學(xué)習(xí)系統(tǒng)成本，從而在 不需要完整卸載信息的情況下選擇最佳邊緣節(jié)點。 Chen 等[4] 提出了采用人工智能的方法來實現(xiàn)物聯(lián)網(wǎng)的普及連接以及可靠的低延時通信。Zhao 等[5] 提出 了一種基于 ARIMA-BP 的選擇性卸載策略（ABSO）， 該策略在滿足延遲要求的同時，最大限度地減少了 移動設(shè)備的能耗。Bi 和 Tran 等[6-7] 提出了啟發(fā)式局 部搜索算法，Dinh 等[8] 提出了半定松弛方法。每當(dāng) 信道環(huán)境發(fā)生較大變化時，這些算法都需要重新進 行大量的迭代才能適應(yīng)新的信道環(huán)境，因此它們并 不適用于快速衰落信道。 Chen 等 [9]研究了動 態(tài) MEC 系統(tǒng)中的任務(wù)卸載調(diào)度問題，通過將能量收集 技術(shù)集成到物聯(lián)網(wǎng)設(shè)備中，提出了一種混合能源供 應(yīng)模型，隨后基于隨機優(yōu)化理論提出了一種在線動 態(tài)任務(wù)卸載算法（DTOME），通過權(quán)衡系統(tǒng)成本和隊 列穩(wěn)定性來做出任務(wù)卸載決策。

本文以智慧農(nóng)業(yè)大棚的物聯(lián)網(wǎng)環(huán)境監(jiān)控場景為 例，設(shè)計了一個多服務(wù)器、多無線設(shè)備的 MEC 系統(tǒng) 模型，通過將 MEC 技術(shù)應(yīng)用于智慧農(nóng)業(yè)大棚的環(huán)境 監(jiān)控，來實現(xiàn)數(shù)據(jù)實時采集和分析，提高農(nóng)業(yè)生產(chǎn)的 效率和質(zhì)量。相較于以往的研究，本文針對新的應(yīng) 用場景，通過建立多服務(wù)器、多無線設(shè)備的 MEC 系 統(tǒng)模型，解決了傳統(tǒng)單服務(wù)器單設(shè)備的 MEC 系統(tǒng)無 法滿足大規(guī)模數(shù)據(jù)處理需求的問題。同時，本文還 聯(lián)合優(yōu)化任務(wù)時延、設(shè)備能耗，建立了一個成本最小 化優(yōu)化問題，并提出了一種基于蒙特卡洛樹搜索的 多通道探索算法，該算法能夠動態(tài)調(diào)整通道數(shù)和選 擇最優(yōu)可能導(dǎo)致最優(yōu)解的節(jié)點，以適應(yīng)不同的任務(wù) 負載和網(wǎng)絡(luò)條件，能夠高效地搜索到最優(yōu)解。最后，通過實驗驗證了該算法的有效性。

1""" 系統(tǒng)模型

本文考慮的 MEC 系統(tǒng)以智慧農(nóng)業(yè)大棚的物聯(lián) 網(wǎng)環(huán)境監(jiān)控為背景，系統(tǒng)模型如圖 1 所示。該 MEC 系統(tǒng)中，無線設(shè)備產(chǎn)生的任務(wù)遵循二進制卸載策略。

在本文中，令N={1，2，… ，N}表示無線設(shè)備集合，令M={1，2，… ，M}表示MEC服務(wù)器集合，每一個無線設(shè)備可以選擇M種MEC服務(wù)器或者直接本地執(zhí)行處理任務(wù)，因此，每一個無線設(shè)備有M＋1種方式處理計算任務(wù)。用yn表示每個無線設(shè)備的卸載決策，y. E {0，1，2，… ，N}。當(dāng)yn=0時，無線設(shè)備n的任務(wù)將在本地進行計算;當(dāng)ya=m（l ≤m≤M）時，無線設(shè)備n的計算任務(wù)將被卸載到MEC服務(wù)器m中進行計算，用集合幣= fn c N，m ∈ M}表示所有無線設(shè)備卸載策略。

本文假設(shè)每個無線設(shè)備都有一個需要完成的計算密集型任務(wù)，表示為T.={D.Z..T\"\"*}，其中，D.表示輸入任務(wù)大小，Z表示完成任務(wù)所需的計算量，T表示任務(wù)所能容忍的最大時延。

任務(wù)卸載流程如圖2所示，在產(chǎn)生一個隨機任務(wù)后，首先決定是本地執(zhí)行還是卸載到MEC服務(wù)器中執(zhí)行，如果選擇本地執(zhí)行則直接計算結(jié)果，若選擇卸載到MEC服務(wù)器中執(zhí)行，則需要將任務(wù)上傳到MEC服務(wù)器中，待MEC服務(wù)器計算完成后再將計算結(jié)果回傳到無線設(shè)備中。

圖 3 示出了迭代次數(shù)、無線設(shè)備數(shù)量以及模擬 次數(shù)對幾種方法歸一化獎勵函數(shù)的影響，從圖中可 以看出，本文所提出的 MCS-MCTS 算法擴大了搜索 過程，提高了全局搜索的能力，總體性能比較好，隨 著迭代次數(shù)的增加其收斂速度要優(yōu)于其他幾種方 法，在迭代此數(shù)為 120 次左右時就基本已經(jīng)完成收 斂；而本地執(zhí)行 LE 由于只能使用本地資源，導(dǎo)致系 統(tǒng)處理任務(wù)效率低，因此其獲得的獎勵最低；而除了 OE 外其他方法基本 在 200 次左右全部收斂 ， 但 OE 方法可能導(dǎo)致系統(tǒng)一些關(guān)鍵功能或性能缺失，系 統(tǒng)的覆蓋范圍受到影響，導(dǎo)致性能下降，從而影響其 歸一化獎勵值，因此實驗參數(shù)選取為 220 次迭代次 數(shù)。從圖 3（b） 中可以發(fā)現(xiàn)，對于不同數(shù)量的移動設(shè) 備，MCS-MCTS 的中位數(shù)總是接近于 1，置信區(qū)間大 多高于 0.995，相比之下其他兩種方法的置信區(qū)間雖 然大多都大于 0.980，但明顯 MCS-MCTS方法可以在 不同的網(wǎng)絡(luò)布局下實現(xiàn)接近最優(yōu)的計算性能。從 圖 3（c） 可以看出，模擬次數(shù)超過 2000 時，歸一化獎 勵值趨于穩(wěn)定，約為 0.998，由此可知，本文所提出的 MCS-MCTS 算法可以獲得接近于最優(yōu)的任務(wù)調(diào)度 解，圖形的波動是由于隨機采樣造成的。

圖 4 描述了不同參數(shù)下幾種算法的系統(tǒng)成本對 比。圖 4（a） 示出了無線設(shè)備數(shù)量 N 對系統(tǒng)成本的影 響。隨著移動設(shè)備數(shù)量增多，系統(tǒng)成本急劇增長，這 是因為移動設(shè)備數(shù)量越多，所需要處理的任務(wù)也更 多，導(dǎo)致傳輸時延與能耗都更高，因此所需系統(tǒng)總成 本會更大。圖 4（b） 描述了幾種方法在不同的時間權(quán) 重 與和能耗權(quán)重 下對系統(tǒng)成本的影響，當(dāng) 取 不同參數(shù)時，則相應(yīng)地 ，由圖可以看出，本 地執(zhí)行時系統(tǒng)成本隨著 的增大、 的減小而不斷 減小，卸載執(zhí)行時系統(tǒng)成本則隨之不斷增大，而其他 方法在增大到一定程度時，系統(tǒng)成本有著下降的趨 勢，從圖中明顯看出，MCS-MCTS 算法要優(yōu)于其他 DQN 算法與 GA 算法。圖 4（c）與圖 4（d） 描述了輸入 任務(wù)大小與完成任務(wù)所需計算量變化時，幾種方法 所需系統(tǒng)成本的對比。從圖中可以看出，除了本地 執(zhí)行計算任務(wù)時，系統(tǒng)成本不會隨著輸入任務(wù)大小 增大而改變外，其余方法均隨著輸入任務(wù)大小或隨 著完成任務(wù)所需計算量的增大而增大。本地執(zhí)行計 算任務(wù)時，由于其計算時間與能耗均與輸入的任務(wù) 大小無關(guān)，因此本地計算時系統(tǒng)成本不會隨著輸入 任務(wù)大小改變而改變。綜上，與其他幾種方式相比， MCS-MCTS 算法在減小系統(tǒng)成本上有著明顯優(yōu)勢。 因此，選擇合適的輸入任務(wù)大小與完成任務(wù)所需計 算量，對降低系統(tǒng)成本有著很大的作用。

圖 5 描述了無線設(shè)備數(shù) N 與服務(wù)器數(shù) M 不同 時，幾種方法對系統(tǒng)開銷成本與獎勵值的對比。由 圖 5（a）～5（c） 可以看出，當(dāng) N 不變，M 增加時，只有本 地執(zhí)行時的成本不變，這是因為本地執(zhí)行時與是否 有邊緣服務(wù)器無關(guān)，而其他幾種方式的系統(tǒng)成本均 隨著服務(wù)器數(shù)量增加而減小，因為邊緣服務(wù)器數(shù)量 越多，會增加任務(wù)卸載時可供選擇方案，當(dāng)出現(xiàn)更優(yōu)服務(wù)器時，卸載成本就會下降，從而使系統(tǒng)總成本下 降；而當(dāng) M 不變，N 增加時，無線設(shè)備數(shù)量越多，所需 處理的任務(wù)越多，因此整體所花時間與能耗均增大， 導(dǎo)致系統(tǒng)開銷成本增高。顯然本文所提出的 MCS[1]MCTS 方法所獲得的系統(tǒng)成本明顯低于其他幾種。 由圖 5（d） 可以看出，無論無線設(shè)備數(shù)量還是服務(wù)器 數(shù)量改變時，本文所提出的 MCS-MCTS 方法都能獲 得更優(yōu)的獎勵值。

4""" 結(jié) 論

在物聯(lián)網(wǎng) MEC 系統(tǒng)中，隨著無線設(shè)備計算能力 的增強與功能的復(fù)雜化，任務(wù)量不斷增加。此時，若 任務(wù)全部本地執(zhí)行或全部卸載執(zhí)行都會造成計算壓 力的急劇增加。本文針對智慧農(nóng)業(yè)大棚的環(huán)境監(jiān)控 應(yīng)用場景下的 MEC 系統(tǒng)任務(wù)調(diào)度問題，建立了移動 邊緣計算任務(wù)調(diào)度架構(gòu)?；谠摷軜?gòu)，以聯(lián)合優(yōu)化 能耗與延時為目標，提出了系統(tǒng)開銷成本最小化的 優(yōu)化問題。根據(jù)該優(yōu)化問題，將計算資源分配決策 和傳輸功率分配決策建模為凸優(yōu)化問題，并通過拉 格朗日乘子法與 KKT 條件獲得最優(yōu)資源分配策略， 使用梯度下降法獲得最優(yōu)傳輸功率分配策略。接 著，本文設(shè)計了一個 MCS-MCTS 算法來生成最優(yōu)卸 載決策，并引入模擬退火算法增加了 MCS-MCTS 算 法收斂于最優(yōu)解的可能性。在仿真實驗中，對比了 MCS-MCTS、DQN、GA、OE、LE 這幾種方法在不同 無線設(shè)備數(shù)量、時延與能耗權(quán)重、輸入任務(wù)大小等不 同指標下的表現(xiàn)。結(jié)果顯示，本文所提出的 MCS[1]MCTS 算法在保證決策生成效率的同時，生成了最優(yōu) 的卸載決策，降低了系統(tǒng)的總體開銷。在未來的研 究中，我們將分析大任務(wù)量時的卸載決策策略和資 源分配策略。

參考文獻：

SIRIWARDHANA" Y，" PORAMBAGE" P，" LIYANAGE M， et al." A" survey" on" mobile" augmented" reality" with" 5G mobile" edge" computing：" Architectures，" applications，" and technical" aspects[J]." IEEE" Communications" Surveys" amp; Tutorials， 2021， 23（2）： 1160-1192.

CUI" Y，" ZHANG" D，" ZHANG" T， et al." A" novel" offloading scheduling" method" for" mobile" application" in" mobile" edge computing[J]. Wireless Networks， 2022， 28（6）： 2345-2363.

DAI" X，" XIAO" Z，" JIANG" H， et al." Task" co-offloading" for D2D-assisted mobile edge computing in industrial internet of" things[J]." IEEE" Transactions" on" Industrial" Informatics， 2022， 19（1）： 480-490.

CHEN" M" Z，" CHALLITA" U，" SAAD" W， et al." Artificial neural networks-based" machine" learning" for" wireless"" net[1]works：" A" tutorial[J]." IEEE" Communications" Surveys" amp; Tutorials， 2019， 21（4）： 3039-3071.

ZHAO" M，" ZHOU" K." Selective" offloading" by" exploiting ARIMA-BP for" energy" optimization" in" mobile" edge"" com[1]puting networks[J]. Algorithms， 2019， 12（2）： 48.

BI" S" Z，" ZHANG" Y" J." Computation" rate" maximization" for wireless powered mobile-edge computing with binary com[1]putation" offloading[J]. IEEE" Transactions" on" Wireless Communications， 2018， 17（6）： 4177-4190.

TRAN" T" X，" POMPILI" D." Joint" task" offloading" and resource allocation" for" multi-server" mobile-edge"" comput[1]ing" networks[J]. IEEE Transactions" on" Vehicular" Techno[1]logy， 2019， 68（1）： 856-868.

DINH" T" Q，" TANG" J" H，" LA" Q" D， et al." Offloading" in mobile edge computing： Task allocation and computational frequency scaling[J]." IEEE" Transactions" on"" Communica[1]tions， 2017， 65（8）： 3571-3584.

CHEN Y， ZHAO F， LU Y， et al. Dynamic task offloading for" mobile" edge" computing" with" hybrid" energy" supply[J]. Tsinghua Science and Technology， 2022， 28（3）： 421-432.

TRAN" T" X，" POMPILI" D." Joint" task" offloading" and resource allocation" for" multi-server" mobile-edge"" comput[1]ing networks[J]." IEEE" Transactions" on" Vehicular" Techno[1]logy， 2018， 68（1）： 856-868.

CHEN" X." Decentralized" computation" offloading" game" for mobile cloud computing[J]. IEEE Transactions on Parallel and Distributed Systems， 2014， 26（4）： 974-983.

LYU" X，" TIAN" H，" SENGUL" C， et al." Multiuser" joint" task offloading" and" resource" optimization" in" proximate clouds[J]." IEEE" Transactions" on" Vehicular" Technology， 2016， 66（4）： 3435-3447.

MNIH"" V，"" KACUKCUOLU"" K，"" SLIVER"" D， et al."" Hu[1]manlevel"" control"" through"" deep"" reinforcement "learning[J]. Nature， 2015， 518（7540）： 529-533.