移動邊緣計算中以節點能耗約束的遷移策略研究

楊曉慧，熊小峰，宋逸杰，楊忠明，趙玲珠

（江西理工大學 理學院，江西 贛州 341000）

0 引言

過去10 年中，為滿足爆炸式增長的流量對大量計算資源的需求，將計算、控制和數據存儲轉移到云成為趨勢，這種重新定位引入了網絡延遲，對時延敏感的應用程序延遲要求帶來了重大挑戰。移動應用程序日益復雜化、智能化及多樣化，人臉識別、語言處理、在線游戲和遠程醫療等應用均具有時效性強、數據量大、帶寬高等特點，越來越超出設備的有限能力，使得智能移動終端在計算能力和電池壽命方面面臨巨大挑戰。由此，邊緣計算（Edge Computing，EC）應運而生，并與傳統云計算互補，在靠近移動用戶附近的網絡邊緣提供云計算功能，滿足快速交互響應需求，提供普遍且靈活的計算服務［1］。邊緣計算思想是將全部或部分計算任務遷移至邊緣服務器/其余終端設備，降低計算時延與能耗開銷。因此，計算遷移是邊緣計算的關鍵技術之一，可彌補設備的能力限制和不斷增長的計算需求［2］。計算遷移有以下3 個優點：①降低了移動設備本地處理計算任務的能耗，延長了電池使用壽命；②利用遠程云/邊緣服務器等更強大的CPU 計算能力，減少任務的處理延遲；③通過本地和云處理資源協同服務處理更多的計算任務，提高服務質量（Quality of service，QoS），提高用戶滿意度。計算遷移有效解決了設備在資源存儲、計算性能以及能效等方面的不足。

智能終端的電池能量局限性很大，電池更換或充電不便且成本較大；因終端自身資源不足，部分設備在計算遷移過程中出現拒絕協作現象，增加了網絡負載和延遲，導致丟包率增加。特別是在MEC（Mobile edge computing）場景下，當計算任務較小且完成的延遲和能量較低時，遷移反而導致成本增加［3］。因此，通過制定有效的遷移策略快速響應，降低節點能耗，提高邊緣網絡QoS、吞吐量和生命周期，成為邊緣計算領域需要解決的核心問題之一。

針對上述問題，本文提出一種基于節點剩余能量的計算遷移策略。以節點剩余能量為約束，構建計算遷移決策模型，降低因能源不足導致的網絡抖動；利用模擬退火算法（Simulated Annealing，SA）和改進的粒子群算法（Particle Swarm Optimization，PSO）對該模型求解，提高網絡吞吐量，降低丟包率和延遲，使網絡邊緣設備獲得良好性能，以保障邊緣網絡的魯棒性和穩定性。

1 相關工作

為實現就近服務、提高網絡容量和保障數據安全，邊緣計算通過計算遷移方式，根據策略將計算向邊緣節點、邊緣服務器或云遷移，通過計算遷移協同服務，提升邊端計算能力和電池壽命，降低計算延遲和網絡帶寬消耗，均衡云中心負載，提高網絡QoS。其中，邊緣計算遷移的能耗與延遲是衡量遷移決策的重要指標，降低處理及傳輸任務的延遲和能耗的相關研究成果頗豐。

文獻［4］考慮了移動邊緣計算中優化資源策略的單一性，為保證延遲約束情況下充分降低邊緣設備能耗，提出一種基于粒子群任務調度算法的多重資源計算遷移能耗模型。驗證了該策略所對應的任務調度算法收斂穩定、適應度最優；文獻［5］以移動設備的任務處理延遲和能量消耗約束為研究對象，通過遷移將邊緣服務器分配給一對深度神經網絡移動設備，使邊緣服務器利潤最大化；文獻［6］提出一種高效安全的多用戶多任務計算遷移模型，使用JPEG 和MPEG4 壓縮算法來減少傳輸開銷，對大規模物聯網具有很好的擴展性。

計算任務的增加使得電池使用壽命成為難題。文獻［7］為解決移動終端電池能量和計算能力受限問題，基于MEC 架構，以終端能耗最小化與移動服務提供商收益最大化為目標，提出一種動態定價策略，使用Q-learning 與DE相結合的算法，提高資源的利用率和處理效率；文獻［8］基于無線供電技術研究了MEC 場景中終端遷移決策問題，設計一種基于深度強化學習的在線遷移決策算法，降低計算時間開銷和網絡延遲，實現計算自適應遷移和資源合理分配；文獻［9］基于能量收集技術，提出一種綠色可持續的移動邊緣計算（GS-MEC）模型，提出在能量隊列穩定性限制下最小化任務響應時間和包丟失，提高任務處理的及時性和可靠性，實現設備在物聯網環境中利用綠色能源自供電。

源任務節點通常在覆蓋范圍內首先考慮優秀節點進行遷移，導致優秀節點任務隊列任務堆積，致使負載不均，降低了網絡吞吐量。為解決該問題，文獻［10］基于無線傳感網絡應用場景，提出一種改進的簇頭節點選擇算法，循環選擇剩余能量較高的節點作為簇頭，并在其之間輪換簇頭位置，提高了網絡的吞吐量、生命周期及剩余能量，實現網絡負載均衡；文獻［11］研究了計算遷移環境下移動設備資源的能效問題，基于修改的李雅普諾夫優化技術優化計算遷移決策，保持移動設備上運行程序的吞吐量和公平性；文獻［12］提出一種基于累積社會信任組織計算遷移的在線學習輔助協同遷移機制，在無法精準預測的情況下保證接近最優的系統性能，但是系統的魯棒性是以降低穩定性為代價；文獻［13］提出一種在多約束條件下邊緣計算可信協同任務遷移策略，以K 維權值任務遷移作為優化目標，采用改進的貪心算法求解最優任務分配策略，保障計算遷移效率和QoS。

隨著我國海事活動日趨頻繁，海洋無線通信與邊緣計算融合應用越來越多。文獻［14］聯合優化遷移策略、通信資源和計算資源，研究了MEC 系統在慢衰落信道和快衰落信道下的計算任務與遷移順序之間的依賴性，分別設計了黃金算法和即時信道策略選擇最優遷移決策，實現在延遲約束下最小化終端設備的能耗；文獻［15］針對海上資源有限導致延遲和能耗過大問題，提出一種基于移動邊緣計算的兩段式聯合優化遷移算法（JOOA）。通過構建低成本、大規模的海上通信網絡框架，降低了任務遷移中的延遲以及計算能耗。但在海上大規模網絡環境中，若節點掉線會導致網絡抖動且在短期內難以重新自主組網，所以保證網絡節點的穩定性是需要考慮的重點。

以上方法都未在因節點下線導致的網絡抖動方面進行能耗優化。本文根據遷移決策和任務分配方式的不同，提出基于能耗約束的計算混合遷移策略（Hybrid Offloading Strategy Constrained by Node Energy，HOS-NE）。利用粒子群算法和模擬退火算法優化該遷移模型，綜合考慮計算遷移時邊緣遷移節點的負載情況和能量利用率等因素，自主選擇遷移決策和任務分配，保證在任務期限內降低任務的丟包率，提高節點能量利用率和系統吞吐量。

2 HOS-NE 策略模型構建

2.1 邊緣計算遷移模式

根據源遷移節點與遷移節點的相對位置關系，邊緣計算遷移可分為上行、平行和下行3 種遷移模式［16］。其中，利用上行遷移與平行遷移技術，將任務及時遷移到移動邊緣計算服務器或臨近空閑的移動終端進行計算處理，能夠有效擴展移動設備的即時計算能力，降低計算延遲，提高移動終端電池壽命。如圖1 所示，當智能終端發起計算請求時，依據任務計算量、響應延遲進行遷移決策，將計算量較大的任務遷移至計算能力強的遠程云中心或邊緣服務器執行，降低終端能耗；將計算量小的任務或者需要地理位置信息、響應延遲低的任務留在本地處理或D2D 協作執行，降低計算響應延遲。因此，計算密集型任務計算量大，采用以能耗為約束的上行遷移；而對于延遲敏感任務采用以延遲為約束的本地遷移。

Fig.1 Computing migration scenario圖1 計算遷移場景

假設由1 個邊緣服務器和u個智能終端（本文統稱為節點）構成的集合U={1 ,2,…,U} ，移動邊緣計算應用場景中每個終端可同時執行多個計算任務且每個計算任務不能再進行劃分。其中，每個終端ui的任務表示為Aui={aui,1,aui,2,…,aui,m}，用ζui,j={cui,j,dui,j,tui,j} 表示每個任務aui,j的屬性特征。cui,j表示任務aui,j需求的計算能力，dui,j為該任務的最后期限，即該任務所能容忍的最大時延，tui,j為該任務在標準算力下完成所需要的時間。

為克服設備資源、算力限制，以及響應高效、實時的需求，MEC 允許UEs 根據任務的屬性特征選擇執行方式：

（1）平行遷移。遷移至鄰近設備執行延遲較低且滿足實時響應需求。

（2）上行遷移。允許UEs 將任務轉移到鄰近的服務器以更快地進行任務計算。

本文主要采用平行遷移與上行遷移相結合的混合遷移模式，依據任務計算量、響應延遲進行遷移決策，以降低終端能耗和響應延遲。使用二元變量xij∈{ 0,1} 表示終端的決策，xij= 1 表示任務遷移到其余節點j執行，xij= 0 表示任務在終端本地執行。

根據文獻［17］構建MEC 遷移系統模型。當任務在終端本地執行時，設節點ui的計算能力為fiL，TiL表示任務aui,j在本地執行的時間，則：

本地計算的能耗為：

其中，κm為一個受設備硬件影響的參數。

當任務遷移到MEC服務器執行時，設邊緣服務器的計算能力為fiS，TiS表示任務aui,j遷移到網絡邊緣執行的時間，則：

其中，Tit為任務的傳輸時間，受傳輸任務量的大小與傳輸鏈路的影響。遷移到邊緣服務器遠程執行，則終端ui的能耗為：

其中，pi為ui的發射功率，ζi為設備的功率放大器效率。

綜上所述，最小化移動智能終端公式可表示為：

其中，為ui的最大功率。

考慮到終端設備的多樣異構性，且功率差異較大，實際上公式（5）的求解過程較復雜。為簡化問題復雜度，本文使用終端節點的待機時長表示終端能耗，根據剩余電量的狀態表示終端設備的狀態。因此，本文提出一種基于節點剩余能量的移動邊緣計算混合遷移策略——HOS-RE，根據源遷移節點任務的算力、能量等需求特征和遷移節點的剩余能量、計算能力等特征，將任務遷移至合適的節點執行。采用上行與平行的混合遷移模式，提高網絡的穩定性、魯棒性，實現負載均衡。制定合適的遷移決策是求解該問題的關鍵，具體策略框架如圖2 所示。

2.2 平行遷移決策

對于每個終端ui，使用三元組{,u_ti,τi}表示節點的屬性特征。其中，表示終端ui的實時計算能力，u_ti表 示終端初始待機時長，τi為節點實時待機時長。當任務i發送遷移請求給終端ui時，設備根據以下兩個方面來判斷是否接受任務：

Fig.2 Framework for computing migration strategy圖2 計算遷移策略框架

（1）終端ui選擇接受任務時首先需要考慮自身的算力能不能滿足任務需求的算力，節點的實時計算能力可以表示為：

其中，c′ui,j表示正在處理計算任務所需的算力。

（2）終端ui選擇接受任務時還需要考慮自身的能量能不能保持完成任務后仍在線。因此，節點接受計算請求服務待機時長下界u_ti′可表示為：

其中，ω表示節點電量預留的閾值，保證節點執行任務后仍有能量保持自身在線，進而維持網絡穩定。

綜上所述，使用二元變量yij表示終端ui的任務接收決策，當yij= 1 時表示uj成功接受任務ai的遷移請求，否則不接受。任務接收決策函數表示為：

當終端ui向周圍節點發送任務計算遷移請求時，周圍節點可拒絕接受該任務請求。當該任務被拒絕多次，則將該任務計算遷移到MEC 服務器進行處理。平行遷移終端設備的剩余能量可表示為：

2.3 上行遷移決策

當終端設備的計算能力與待機時長均無法滿足任務ai需求，即被拒絕次數R達到上界k時，則該任務所在的終端選擇將任務遷移至MEC 服務器執行。與終端節點相似，使用三元組{,s_ti,τis}表示邊緣服務器屬性特征。其中,表示邊緣服務器計算能力，s_ti表示邊緣服務器初始能量，表示邊緣服務器實際能量。使用二元變量zij表示終端是否將任務遷移到邊緣服務器。當zij= 1 時表示將任務遷移到邊緣服務器執行，否則為0，丟棄該任務，將本次遷移視為失敗，則：

上行遷移的剩余能量表示為：

綜上，將式（5）中的終端設備能耗最小化問題轉化為最大化終端剩余能量問題：

2.4 算法設計與實現

由于公式（13）求解復雜度較高，為優化求解能力，本文分別采用PSO 算法和SA 算法對該問題進行求解，具體算法描述如下：

3 實驗仿真與分析

3.1 仿真場景與實驗設計

構建計算遷移系統模型應用場景如下：一個MEC 網絡環境中分布127 個節點以及1 個MEC 服務器，設定每個設備產生任務的個數在區間［0，20］中隨機生成，每個任務所需算力在區間［1，5］中隨機產生。設節點初始電量均為300min，且不可持續充電，即當電量耗盡后該節點下線，仿真參數及描述如表1 所示。

Table 1 Experimental simulation parameters表1 仿真參數

為驗證所提出遷移模型的有效性，采用MATLAB 工具進行仿真實驗。首先，第一組實驗從遷移失敗次數和節點平均剩余能量兩方面與基于PSO 的智能算法［18］、隨機游走（Random execution，RE）和基于能量的貪心算法（Greedy_energy，G_E）［19］進行比較；第二組仿真實驗中，與基于SA 的智能算法［20］、RE、基于算力的貪心算法（Greedy_compute，G_C）和G_E 算法在吞吐量、剩余能量和任務處理成功率方面進行比較。

3.2 算法仿真與性能分析

3.2.1 同一周期內不同遷移策略性能分析

為了驗證遷移策略的有效性，本文將基于PSO 的智能算法與RE、G_E 算法進行丟包數與設備剩余時間對比分析。RE 算法、G_E 算法介紹如下：

（1）隨機遷移（RE）算法。在任務遷移請求發起時，每個設備的任務隨機選擇邊緣服務器端或鄰近的終端設備進行處理，但未進行選擇優化。

（2）基于能量的貪心（G_E）算法。任務遷移時為每個任務在時間允許范圍內貪心地選擇能量較多的終端設備進行處理。

實驗1算法穩定性評估

從圖3 可以看出，算法迭代次數達到80 時趨于穩定，表1 給出了實驗中共用參數的詳細值。PSO 算法實驗參數設置如下：算法迭代次數為L= 150，速度最大最小值Smax=5,Smin= -5，學習因子C1= 2,C2= 1.5，慣性因子W1=0.9,W2= 0.4。為了提高實驗的準確性，針對設備資源是否重置進行兩組實驗：①隨著任務量增加，每次遷移時重新尋找最優遷移矩陣；②隨著任務數增加，依據剩余資源尋找最優遷移矩陣，即終端資源不進行重置。

Fig.3 Stability of the algorithm圖3 算法穩定性

實驗2設備資源重置

在設備資源重置場景下，隨著任務量的增加，任務丟包數與平均剩余能量的對比如圖4、圖5 所示。

Fig.4 Change of lost packet number圖4 丟包數的變化（彩圖掃OSID 碼可見，下同）

Fig.5 Average residual time change圖5 平均剩余時間變化

從圖4 可以看出，隨著任務的增加，3 種算法的任務丟包數均增加，RE 與G_E 算法幾乎呈線性增長趨勢。與其余兩種算法相比，PSO 算法能夠顯著降低丟包數。這是因為RE 算法雖然可以在很短的時間內選擇一個節點進行遷移，但隨機性較高導致被選擇節點的屬性差異也較大，且可能多個任務同時遷移到同一遷移節點，致使任務超時被丟包；G_E 算法會優先考慮能量和算力較大的節點，計算任務堆積在隊列中從而導致任務完成時間超過任務期限，丟包數增大；基于PSO 算法進行遷移時，綜合考慮節點的多種特征如能耗、時延、代價等，所以任務選到適合自己的節點概率較高，丟包數比較理想。隨著任務數量上升，基于PSO 算法的遷移方式丟包數也呈現出平緩增加趨勢。

分析圖5 可知，隨著任務數增加，節點平均剩余能量逐漸減少。與RE 算法相比，基于PSO 算法的平均剩余能量在任務量少時近似相同。但隨著任務量的增加，PSO 算法下的節點處理任務較多，能耗增加；在G_E 算法下的節點由于呈現任務趨優現象，任務丟包率較大所以能耗較低。

實驗3設備資源非重置

圖6 和圖7 均在節點資源非重置的環境下進行仿真，即每產生一個計算遷移任務，該任務就會在節點處理完之前的任務后在剩余節點資源中尋找適合自己的設備。

Fig.6 Change of lost packet number圖6 丟包數變化

Fig.7 Average residual time change圖7 平均剩余時間變化

由圖6 分析可知，隨著任務數的增加，任務丟包數都呈現上升趨勢。基于PSO 算法的任務丟包數上升緩慢，丟包率在5%-10%之間，比RE和G_E算法分別降低了65% 、71.4%。

分析圖7 可知，基于PSO 的算法隨著任務量的增加耗能也增加，剩余能量逐漸減少。PSO 算法平均剩余時間比RE 和G_E 算法分別提高了16.7%、28.6%，在任務數增加至1 000 后下降，趨于平緩的趨勢更加明顯。

綜合圖6 和圖7 可以得出，PSO 算法在能耗和丟包方面都優于RE 和G_E 算法，任務通過PSO 算法選擇最適合自己的節點，既不浪費資源也不增大延遲，可消耗更少的能量處理更多的任務。

3.2.2 任務周期內不同遷移策略性能分析

為進一步驗證遷移策略模型性能，在圖1 場景下，本文從時間周期角度運用基于SA 的智能算法與G_C、RE 和G_E 算法進行比較，分析吞吐量、丟包數與平均剩余能量評價性能的優劣，仿真結果分別如圖8-圖10 所示。

Fig.8 The throughput change圖8 吞吐量變化

Fig.9 Change of lost packet number圖9 丟包數變化

從圖8 分析可知，每個周期中基于SA 智能算法的吞吐量都優于其他3 種算法，且SA 算法在第14 周期達到穩定，吞吐量比其余3 種算法提高約40%，G_C 算法優化后的系統吞吐量在第9 個觀察周期達到穩定，這是由于G_C 算法中算力高的節點能量耗光后網絡無法處理后續的遷移任務，且由于網絡總能量不足致使G_C 算法和SA 算法優化后的系統吞吐量增量逐漸減少。

從圖9 分析可知，隨著時間推遲，設備能量逐漸消耗，SA、G_C、RE 算法的丟包數逐漸增加。實驗中僅考慮了平行遷移的丟包數，其中G_E 算法由于參數原因不會使任務堆積而導致卸載失敗，所以不產生丟包；SA 算法因節點電量降低導致丟包現象，但與G_C、RE 算法相比，任務遷移的丟包率降低了很多。

Fig.10 Average residual energy change圖10 平均剩余能量變化

從圖10 分析可知，隨著系統完成任務數的增加，節點剩余能量逐漸減少。SA 算法的剩余電量小于其余3 種算法，結合圖8、圖9，SA 算法提高了邊緣計算的資源利用率和協作率，合理利用了不同算力設備，且節點剩余能量會收斂在一定范圍，以便提供耗能較小的計算遷移服務和處理自身任務，提高了網絡穩定性。

綜上所述，基于SA 智能算法優化的遷移策略能實現網絡負載均衡，提高系統吞吐量和網絡穩定性。

4 結語

針對移動智能終端電力受限問題，本文根據遷移決策和任務分配方式不同，提出一種基于節點剩余能量的移動邊緣計算混合遷移策略HOS-NE，并將遷移問題中的節點功率使用終端節點的剩余能量進行轉化，采用PSO 與SA 的智能算法對化簡后的問題進行求解。仿真結果表明，基于智能算法優化后的HOS-NE 能有效提高系統吞吐量和節點在線時長，實現負載均衡。但由于節點的自主性，并非網絡中所有計算節點均能滿足遷移節點條件。所以，如何評價節點，構建可信、可靠的計算遷移策略是下一步研究工作重點。