基于資源約束多目標優化的物聯網邊緣計算資源分配

李智威，莫王昊，李 北，張文東，王 博

(新疆大學軟件學院，新疆烏魯木齊 830049)

0 引 言

在物聯網（IoT）的背景下，邊緣計算被定義為一種分布式計算范式，它使數據處理和分析能夠在更靠近數據源的地方進行。 通過將計算資源部署到更靠近網絡邊緣的位置，邊緣計算可以顯著降低延遲并提高網絡效率[1]，從而應對超密集網絡帶來的挑戰。邊緣計算具有實時數據處理和分析的能力，可以幫助提高超密集網絡的效率和可靠性，并支持在物聯網生態系統中開發新的應用和服務[2-3]。

物聯網模型下的邊緣計算問題（Edge Computing for IoT, ECIoT）的研究，主要集中在低功耗和低計算延遲情況下邊緣計算的數據資源配置問題。

針對低功耗的研究，Chen Xu 等人綜合考慮了ECIoT 的動態緩存、數據資源配置等要素模型目標，利用深度學習策略對其進行梯度調整優化，實現了目標成本的最小化[4]；I. A. Elgendy 等人的研究側重點在于在線互聯物聯網設備的非正交多址資源配置問題，共同考慮安全、計算卸載和資源分配，以使整個系統的時間和能源消耗最小，采用的優化計算方法仍然是深度學習算法[5]。

對于低時延的研究，為求解ECIoT 問題，Zhang Kaiyuan 等人設計了一種求解次優解的分支有界優化計算模型，顯著提升了邊緣計算資源配置算法的計算效率[6]；針對ECIoT 問題的物理器件數量龐大問題，Jiang Congfeng 等人提出一種分布式的多智能體優化學習策略，在保障計算功耗指標前提下，有效降低了數據傳輸壓力；針對多物聯網移動服務站點設置問題[7]，Li Shichao 等人基于數據流調度優化算法，實現了邊緣計算的資源配置優化[8]；Z. Ghanbari 等人將光網絡的邊緣計算問題作為研究對象，提出了一種多路時分模式的延遲最優的計算網絡，并實現了網絡計算模型的線性優化[9]；H. A. Alameddine 等人與其他研究做法不同，其將網絡容量和頻譜有效性兩個指標作為優化目標，實現了ECIoT 問題的網絡部署優化[10]。

上述ECIoT 問題的研究主要集中在模型算法的設計優化，對于資源配置的多目標優化方案的研究并不深入。本文對于ECIoT 問題的計算時延和資源調度能耗的Pareto 前沿面問題進行研究，針對時延指標和能耗指標進行建模，形成Pareto 前沿面問題；并將其轉換成效用優化模型，提出了一種RA-NSGAⅢ算法對該模型進行求解，實現了ECIoT 問題的多目標優化配置。

1 ECIoT 架構模型

1.1 系統框架

在ECIoT 中，基站可以分為宏基站和微基站兩種類型。宏基站通常覆蓋大范圍區域，提供較高的帶寬和覆蓋范圍，用于支持大規模的數據傳輸和處理；微基站是一種覆蓋范圍較小、功率較低的基站，通常部署在人口密集的區域和需要低延遲、高可靠性的場景中。在邊緣計算物聯網中，宏基站和微基站的地位和作用不同。宏基站主要用于連接云端，承擔數據的轉發和聚合等任務；而微基站通常搭載在邊緣計算服務器或虛擬服務器，用于提供邊緣計算和存儲服務，從而降低云端的壓力和延遲。微基站和宏基站共同構成了邊緣計算物聯網的基礎設施，支持物聯網設備的連接、數據的處理和分析，實現物聯網的智能化決策和控制。針對物聯網模型下的邊緣計算問題，ECIoT 系統架構如圖1 所示。

圖1 ECIoT 系統架構

ECIoT 系統架構中，宏基站覆蓋范圍為紅色區域，范圍較大，終端設備可以將任務卸載到宏基站或者微基站，宏基站中的云中心根據策略進行資源分配和調度；黃色區域為微基站的覆蓋域，在實際ECIoT 中，微基站分布十分廣泛，可以處理大部分用戶請求。本文為了視覺清楚，只選擇兩個微基站進行說明。

1.2 系統模型

如圖1 所示建立ECIoT 網絡，設用戶集為U={U1,U2,…,Uu}，基站搭載的計算節點表示為N={E1,E2,…,En}，則用戶Uu的任務請求可表示為qu={Dq,Wq,Rq,Tqd,Tqmax}。其中：Dq表示輸入的數據大??；參數Wq表示任務請求的工作負載；參數Rq是請求qu運行所占ECIoT 系統計算資源量；參數Tqd是用戶請求qu在理想狀態下的計算時延；參數是用戶請求qu運行所占ECIoT 系統計算時延上限。由于ECIoT 中的用戶大多是移動的，因此將用戶位置表示為Pu={xu,yu}，基站的位置不變，表示為Pn={xn,yn}。

1）時間指標。用戶的響應時間由上行時間、下行時間和處理時間構成，用戶請求qu的上行時間由用戶和基站的距離以及設備的發射功率共同決定。用戶Uu將請求qu發送給計算節點En時的發射功率可以表示為pun，則根據香農公式，用戶請求qu的上行速率可表示為：

式中：Bun和σ2分別是分配給用戶的帶寬資源和高斯白噪聲。用戶Uu和節點En的信道增益可表示為：

式中：參數g0是用戶與節點距離小于1 m 時的信道增益，此時發射功率為1 W。則用戶請求的上行時間可以表示為：

為簡化模型，假設下行時間與上行時間相同。定義決策變量xqn，當xqn=1 時，該用戶請求被卸載到節點En；當xqn=0 時，該用戶請求被卸載到宏基站。節點處理時延由節點分配的計算資源決定，可表示為：

式中：Rqn是邊緣節點En分配給任務請求qu的計算資源；Rqc是宏基站分配給任務請求qu的計算資源。假設由于請求頻繁，邊緣服務器和云服務器的平均功率不變，分別為PE和PC，請求qu的時延則可表示為：

2）能耗指標。在ECIoT 網絡中，能耗是需要重點考慮的優化指標。能耗主要包括兩個方面，即傳輸數據的能耗和處理請求的能耗，其中從用戶到邊緣計算節點的數據傳輸能耗計算公式可表示為：

給定宏基站和微基站的評價功率，則執行用戶請求qu所產生的能耗可表示為：

式中：PE和PC分別為微基站和宏基站執行的平均功耗。請求qu的能耗可表示為：

由以上整理得到效用函數：

式中：λ1和λ2分別表示總時延和總能耗的權衡值，用來表示任務對時延和能耗的偏好程度。由此可以建立節點效用模型：

式（10）保證時延不超過最大容忍時間，且只能無限接近理想值；式（11）保證請求qu只能被卸載到搭載邊緣計算服務器的微基站或者搭載云計算服務器的宏基站；式（12）保證了分配給用戶的帶寬不超過邊緣節點的總帶寬；式（13）保證了邊緣節點分配給用戶的計算資源不超過自身的計算資源；式（14）保證了用戶的發射功率不超過最大發射功率；式（15）使得能耗和時延的權衡值被歸一化。該模型是一個多目標優化問題，由于多目標優化問題通常是非凸、非光滑或離散的，因此可能存在許多局部最優解，這些解會干擾全局Pareto 前沿的搜索。為解決假前沿、孤立前沿、不確定性、噪聲、動態變化等難題，將多目標模型中的計算時延和資源調度能耗使用加權平均或其他轉換方式綜合起來；然后，將綜合目標函數作為效用函數，并將其與系統開銷一起作為優化目標。

2 多目標問題轉化

2.1 問題轉換

在ECIoT 系統中，為了更直接地反映系統的性能和用戶的需求，更符合實際應用需求，將時延和能耗的多目標轉化成效用函數和系統開銷的優化目標[11]。對處理請求qu的時延效用值做如下定義：

式中Ta為理想時延和最大容忍時延的均值，公式為：

則請求qu的花銷為：

式中α為常數，它的作用是使得在[0,1]的范圍內。在宏基站上，處理請求qu的總效用可以表示為：

式中μ是常量，可以表示時延和能耗之間的重要性權衡關系。則原效用函數轉化為：

為實現多目標優化過程，將在云服務器和邊緣服務器的能耗作為開銷函數：

由于發射功率、分配的計算資源、帶寬資源對時延的計算有耦合性，因此分解出功率分配問題，對發射功率進行解耦后，再對上述W、O函數組成的多目標問題進行求解，功率分配模型如下：

2.2 計算過程

在解決P2 問題時，不妨將帶寬進行就近分配，這樣可以得到一個可參考的發射功率值。此外，還需要根據用戶和基站的位置算出信道增益gun。在完成初始化后，模擬退火算法可以接受一定概率的劣解，因此對于上述非線性優化問題可以獲得一個較好的解。使用模擬退火算法對發射功率進行求解的過程如下：

算法1：模擬退火算法

輸入：Bun、gun、σ2、Dq

輸出：pun

1. 初始化：

初始溫度T0，最小溫度Tf、ε、E

在算法1 中，對Bun、gun、Dq進行初始化后，就可以對pun進行優化。在P2 模型中，模擬退火算法能夠找到一組合適的用戶發射功率pun，以達到能耗最小的目的。其基本思路是在一個大的搜索空間中，隨機選取一個初始解，通過一系列的隨機擾動來更新當前的解。這里的隨機擾動可以是對某個用戶的發射功率進行微小的增加或減少。在每一次更新解之后，都會計算當前解的能耗，并將其與歷史最優解進行比較，如果當前解比歷史最優解更優，則將當前解作為新的歷史最優解。隨著算法的進行，模擬退火算法會逐漸降低溫度，使得算法更傾向于選擇更優的解，并且隨著溫度的下降，算法會逐漸收斂到全局最優解。

NSGA Ⅲ是一種基于進化算法的多目標優化算法[12]，被用于解決如機器人路徑規劃、圖像分割、生物序列對比等多目標優化問題，通過非支配排序和擁擠度分配來維護種群的多樣性和收斂性。本文基于NSGAⅢ算法提出一種RA-NSGAⅢ算法，其核心思想是將其進行空間的凸型曲面劃分，從而獲得更為理想的Pareto 前沿面問題解。本文的初始染色體設計如下：

式中：rq為到達邊緣服務器的任務q所分配的計算資源數；bq為分配的帶寬資源；pq是模擬退火算法計算出來的較優的發射功率；xq為卸載決策，移動邊緣設備只在搭載了邊緣服務器的微基站覆蓋范圍內進行卸載。

算法2：RA-NSGAⅢ算法

輸入：N（種群規模）、U（種群）、C（曲率參數）、W（權重集）

輸出：Ut+1

1. 進化種群歸一化U;

2. 計算參考點p= estimate_PFshape(U)

首先，算法2 對種群進行初始化，將種群進行歸一化操作，目的是獲得更為理想的種群多樣化進化效果。計算過程為：利用Lp范式對個體的曲率p值進行計算，從而獲得候選Pareto 前沿面；其次獲得其所對應的標準方差，該指標取值越小，表明所得到的Pareto 前沿面具有越優異的曲面擬合分布性能。Pareto 前沿面的映射模型計算公式如下：

然后，選取目標空間的原點作為假設理想點，由此可計算相互之間的距離參數：d1(x)是原始個體與假設理想點的空間距離，d2(x)是映射個體與假設理想點的空間距離。利用距離d1(x)和d2(x)的差值可獲得節點在目標空間轉換過程中需要的距離參數d(x)?？苫诰嚯xd(x)進行凸曲面模型定義：

式中：[f1(x),f2(x),…,fm(x) ]是凸曲面上的參數向量；參數C是曲率值參數。凸曲面上的個體映射模型如下：

最后，將原來求取問題最小化過程進行轉化，獲得問題最大化的求解方式，并對個體目標空間進行轉換，采取適應值優勢選取的方式進行個體進化。

2.3 算法復雜度分析

衡量算法性能的另一個非常關鍵的指標參數是時間復雜度，該指標也是物聯網絡應用中最應該考慮的指標參數。算法歸一化過程中，對于多目標算法個體的獲取可基于變異和交叉操作實現，所需計算復雜度是O(DN)，參數D是ECIoT 系統模型優化中的決策變量數，即種群的維度。Pareto 前沿面的排序所需計算復雜度是O(Nlogm-2N)。

目標權重重組多目標優化過程的計算復雜度的步驟如下：

1）對于規模2N的進化種群進行歸一化操作，計算復雜度是O(mN)。

2）對于規模2N的進化種群進行預設曲面距離參數的計算，計算復雜度是O(mN)。

3）對于規模2N的進化種群進行特定曲面的個體轉換，計算復雜度是O(mN)。

4）對于規模2N的進化種群進行目標權重重組，計算復雜度是O(mN|W|)，參數W是參考向量維度。

基于以上計算復雜度分析，ECIoT 系統的目標權重重組多目標優化算法計算復雜度是O(mN|W|)。

3 實驗與分析

3.1 實驗環境

為了評估RA-NSGAⅢ算法的有效性，本實驗采用Matlab 2021b 進行模擬。實驗硬件設備為：操作系統使用Windows 10 64 位系統，內存大小是16 GB。多個移動用戶組成了多區域邊緣計算系統，其他設定值如表1所示[13]。

表1 系統參數

3.2 評價指標

為了驗證所提算法在ECIoT 系統優化中的性能，選取三種性能較好的算法作為對比，分別是D-CoMOLS、CM-PSO 和C-PSO 算法。其中，CM-PSO 和C-PSO 的優化策略是進化多粒子保存策略，可實現進化過程的協同優化。C-PSO 的計算策略與CM-PSO 略有不同，其選取的進化計算策略是瓶頸學習方式，主要目的是提升粒子進化過程的視野，有助于增強粒子進化過程的種群多樣性能。D-CoMOLS 則是基于WS 分解優化策略，并采用邊界交叉策略進行種群個體的進化。這種進化策略有助于保持進化種群的分布均勻性。

為了便于算法之間的性能對比，設定算法的進化種群大小[2]N均為1 000。與此同時，CM-PSO 和C-PSO 算法在進行進化Pareto 前沿面保存時，采用了外部集合存儲方式，外部集合存儲器的規模NA 設定為300。DCoMOLS 算法中采用雙種群協同進化，其種群大小均設定為500，懲罰因子T設定為5。算法參數設定如表2所示。

表2 算法參數設置

3.3 結果分析

算法1 在用戶數為32，最大功率為5 時，其較優的發射功率如圖2 所示，其中發射功率接近0 是由于該用戶距離基站很近，且信噪比很高，基站可以通過在接收端使用更高的增益來抵消用戶發射功率的降低，從而實現更高的傳輸速率。在實際過程中，通常將這些用戶進行分組，將他們的信號一起傳輸。

圖2 用戶發射功率圖

為了保證本文算法計算結果的穩定性，設定計算測試環境，采取多次運算求平均值的方式進行結果對比，運行測試次數選取為20 次，設定算法的迭代最大值是500。

根據圖3 所示的算法收斂結果，本文算法所獲得的解集分布更加接近真實的Pareto 前沿面，并且具有更加均勻的解集分布結果。雖然CM-PSO 也具有相對較好的收斂結果，但是其解集分布上具有一定的缺失性，整體表現欠佳，原因是粒子與目標的對應關系導致其對于其他解的關注度較低。D-CoMOLS 算法和C-PSO 算法雖然能夠獲得相對較為理想的解集均勻分布，但是相對于本文算法獲得的解集收斂性較差。

圖3 算法收斂結果

圖4 所示是四種算法在計算能耗性能指標隨著用戶數量增加的實驗對比結果。可以觀察到在ECIoT 環境中，處理更多的用戶請求會導致能耗的增加，C-PSO算法由于對初始解的依賴性，隨著用戶數增加的能耗沒有得到良好的優化；RA-NSGAⅢ算法比其他算法更加節能，比CM-PSO 能耗平均降低了14.8%。

圖4 用戶數量對能耗的影響圖

圖5 所示是四種算法對于響應時間的箱線圖，可以觀察到D-CoMOLS 和CM-PSO 算法取得0.72 s 平均響應時間，但最大響應時間高達1.2 s，且在時間分布上較不均勻；C-PSO 算法有均勻的響應時間和比較低的最大響應時間，在整體上穩定，但缺乏較優的平均響應時間；RA-NSGAⅢ算法雖然犧牲了一些平均響應時間，平均響應時間達到了0.81 s，但是在穩定性和最大響應時間上具有一定優勢。

圖5 四種算法響應時間對比

圖6 所示為不同請求荷載下的對比，以及不同荷載下用戶數量的影響。結果顯示：在請求荷載為2 000時，四種算法均能進行良好的資源分配，取得較好的效用值；在請求荷載為1 000 和1 500 時，由于D-CoMOLS算法和CM-PSO 算法采用局部搜索的方式，在不同的局部最優解之間進行搜索，因此縮小了搜索空間，但是容易陷入局部最優；當請求荷載到2 500 時，微基站的邊緣計算服務器資源不能及時調度，用戶請求得不到及時處理，使得系統效用值明顯降低。

圖6 請求荷載對效用值的對比

4 結 語

本文提出了一種基于資源約束混合決策的多目標優化策略，通過考慮物聯網邊緣資源配置的資源約束條件和綜合考慮計算時延和資源調度能耗，實現了合理配置有限的計算資源和網絡資源，從而提高了系統性能和用戶體驗。本文使用模擬退火算法進行發射功率的微調，采用RA-NSGAⅢ優化算法進行多目標優化，得出與CM-PSO 算法相比，所提算法減小了0.09 s 的平均響應時間，降低了14.8%的能耗，充分證明了該方法的有效性和可行性。

接下來將探索具體場景下邊緣計算資源配置的多目標優化策略，進一步完善算法的實現和性能。此外，進一步探索如何將深度學習技術與邊緣計算相結合，實現更為高效的資源配置和應用場景。

注：本文通訊作者為張文東。