基于緩存模型改進NSGA- Ⅲ算法車聯網卸載策略

摘 要：車聯網場景中，計算任務處理的時延敏感性極高，將計算任務卸載至邊緣服務器是降低時延的有效手段，進行任務卸載還需要綜合考慮負載均衡以及能耗問題。為此提出一種融合差分進化改進的快速非支配排序遺傳算法（NSGA- Ⅲ -DE）卸載方案，引入了緩存模型、時延模型、能耗模型、負載均衡模型，實現多目標優化問題。所提出的算法與NSGA- Ⅱ" 算法相比，系統時延降低了18.5%，能量消耗減少了44.5%，負載均衡標準差下降了14.7%，充分驗證了NSGA- Ⅲ -DE算法的有效性和優越性。

關鍵詞：邊緣計算；任務卸載；緩存模型；差分進化；多目標優化；NSGA- Ⅲ算法

中圖分類號：TP391 文獻標識碼：A 文章編號：2095-1302（2025）01-0-05

0 引 言

相較于傳統的云計算技術，邊緣計算減少了路由的跳數、縮短了設備與服務器之間的物理距離，從而有效降低了數據延遲時間，提高了穩定性。智慧交通系統車聯網對邊緣設備的任務卸載策略、負載均衡、能耗、實時性及穩定性都有嚴格要求，是當前研究的熱點。

文獻[1]設計了一個分布式調度機制，旨在最大程度地提升服務率。文獻[2]針對多服務器場景，提出了一種在線計算調度方法，以實現合理的任務調度，從而減輕服務器負載。文獻[3]提出了一種基于指針網絡的計算卸載與任務調度方案，該方案通過設定卸載優先級，并采用深度強化學習的方法訓練指針網絡，以達到減少任務執行時延與車輛能耗的目的。目前在車聯網邊緣計算任務卸載領域，評價指標多以時延與能耗為主。文獻[4]采用一種多目標優化的計算卸載機制，緩解網絡負荷，降低卸載能耗以及任務卸載響應時延。文獻[5]提出了一個云邊協同的計算卸載方式，聯合優化了資源調度，最大化了系統效用函數，該設計同時考慮了時延、計算資源開銷、歸一化這3個指標。伴隨著計算任務的增多，服務器的負載問題逐漸引起了廣大研究者的關注。文獻[6]針對任務負載的相互依賴性，提出了一種兩層負載模型，通過優化資源分配、用戶關聯和計算負載使系統能耗最小化。文獻[7]提出了通過附近車輛的空閑資源來緩解服務器過載問題，采用雙深度Q網絡方法得到任務卸載和資源分配的最優策略。文獻[8]建立了一個數據壓縮和安全保護任務優化模型，將計算負載建模成非線性函數，通過設計的卸載算法達到降低負載的目的。

就現有的研究而言，計算卸載的需求差異使得目前計算卸載策略的目標集中于時延或能耗方向的優化[9]、資源調度機制的選擇[10]以及時延與能耗權衡的多目標優化[11]。但在車載設備邊緣計算的場景下，計算卸載模型以及卸載策略方面仍面臨著諸多挑戰，大量計算任務的出現使得邊緣服務器的負載成為亟待解決的問題。

據此本文建立了車聯網邊緣計算場景下的多任務卸載模型，在兼顧時延與能耗的同時，考慮邊緣服務器負載對整體的影響，以三者最小化問題為優化目標，改進NSGA- Ⅲ算法，提出了融合差分進化策略的快速非支配排序遺傳算法（NSGA- Ⅲ -DE算法），引入了緩存模型和資源優先調度機制，實現了多目標問題的優化。

1 系統模型

1.1 系統場景

假設在該場景下有n輛車，每一輛車都有獨立的計算密集型任務，有m個邊緣服務器，車載終端設備產生計算任務，通過5G或WiFi的方式傳輸至路邊單元；同時本研究設計為每一個路邊單元配備一個邊緣服務器，由路邊單元接收數據。

在本文場景中，車輛設備集合記作。

對車輛特征信息建模為，為車載終端計算單元的計算能力，和分別表示終端設備計算任務的上傳和下傳速率。假定終端設備上有一個特定類型的計算密集型任務，記作。計算任務特征信息建模。其中表示計算任務的輸入數據；表示計算任務的輸出數據；wj表示執行第j個任務時的計算量；表示執行第j個任務的計算資源；表示執行第j個任務的存儲資源。當車載計算單元無法負擔計算任務的算力時，車輛將任務傳輸到邊緣服務器E，使邊緣服務器作為算力分擔設備，邊緣服務器記作

。對邊緣服務器特征信息建模為。其中表示第i個邊緣服務器的計算能力；表示第i個邊緣服務器的計算資源；表示第i個邊緣服務器的存儲資源。

1.2 緩存模型

本文設計了車載邊緣計算任務卸載的緩存模型。在實際應用場景中，邊緣服務器在為計算任務提供服務時會提前在服務器端緩存任務所需的服務應用，這樣可以為任務提供更高效的服務，盡可能地減少時延與能耗。為此設計了緩存策略，定義二進制緩存決策變量Hj，規定當Hj=0時代表邊緣服務器上沒有緩存任務，反之Hj=1時代表已經緩存了任務。當任務被分配到本地進行計算時，首先檢查該任務是否已經被緩存在設備的緩存中，即緩存是否命中。如果是，則可以直接讀取緩存中的數據并進行計算，否則需要在儲存設備中讀取數據，并將計算結果緩存在設備的緩存中。

本文假設該場景下每個邊緣服務器的緩存容量相同，考慮到邊緣服務器緩存容量有限的問題，該緩存模型在執行時應該滿足的約束條件見式（1）：

（1）

此外將邊緣服務器按實時可用計算資源的大小進行排序，資源大者優先級高，任務優先選擇計算資源多的邊緣服務器。

1.3 時延模型

整體任務時延主要分為3部分：本地計算時延，服務器計算時延，傳輸時延。本地計算時延是車輛計算任務在本地車載終端計算單元上的計算時延。本地第j個任務的計算時延的具體表達式見式（2）：

（2）

同時假設每臺服務器在處理計算任務時計算能力穩定，考慮到服務器任務的緩存情況，通過判斷二進制變量Hj，得到第j個任務在服務器上的計算時延，具體表達式為：

（3）

計算任務在傳輸過程中的時延則會被分為兩部分：上傳時延、下傳時延。因此第j個任務的傳輸計算時延的具體表達式見式（4）：

（4）

考慮到傳輸過程中信息的傳輸速率Trans會受到通信鏈路的影響，結合香農公式， Transup的具體表達式見式（5）：

" （5）

式中：B代表的是信道帶寬；pup為移動設備上傳信道的傳輸功率；gn， m為移動終端n與計算接入點m之間的信道增益，信道增益gn， m的具體表達式見式（6）：

（6）

式中：α為路徑損耗指數；d0為參考距離；d為移動設備與邊緣服務器的距離；R為路徑損耗常數。同理可得Transdown的計算公式。

根據建立的時延模型可得，該系統中任務計算總時延 的具體表達式為：

（7）

1.4 能耗模型

根據所設計的系統模型可知，能耗主要涉及3部分，分別為任務的本地計算能耗、服務器的計算能耗以及傳輸能耗。假設該模型中能耗與時延成正比，假定兩個能耗系數λ1、λ2，λ1代表本地能耗系數，λ2代表邊緣服務器能耗系數。因此第j個任務的本地能耗的具體表達式見式（8）：

（8）

當計算任務被卸載到邊緣服務器上計算時，邊緣服務器產生計算能耗，具體表達式見式（9）：

（9）

計算任務被卸載到邊緣服務器上傳輸時產生的能耗的具體表達式見式（10）：

（10）

根據建立的能耗模型可知，該系統的任務計算總能耗的具體表達式見式（11）：

（11）

1.5 負載均衡模型

為了更好地對模型的負載情況進行評測，將車輛計算任務的卸載決策使用二進制變量Fj， i表示為式（12）：

（12）

由此可得服務器上存在被卸載任務的服務器數量M的具體表達式見式（13）：

（13）

假設每個服務器的任務量為Qj，則服務器的平均任務量 AQ的具體表達式見式（14）：

（14）

本節將標準差作為評測服務器負載情況的指標，來評估每臺邊緣服務器的負載情況，標準差用AQS表示，AQS的具體表達式見式（15）：

（15）

1.6 優化目標

車聯網邊緣計算任務的卸載模型以最小化時延為主要優化目標，并保證各服務器的負載均衡，同時降低服務器能耗，因此將本文要解決的問題定義為：

（16）

（17）

（18）

（19）

式（16）表示優化目標的時延、能耗、標準差（即負載）最小化；式（17）表示在計算任務的卸載過程中服務器的計算資源不會過載；式（18）表示在計算任務的卸載過程中服務器存儲資源不會過載；式（19）表示每一個計算任務至多卸載到一個服務器上。

2 改進NSGA- Ⅲ算法任務卸載方案

本文改進了NSGA- Ⅲ算法并與差分進化（DE）操作結合。差分進化算法有較好的全局搜索能力且收斂速度快，可在NSGA- Ⅲ算法的基礎上提高算法的搜索效率，這樣既保證了搜索廣度，又可快速靠近最優解。另外差分進化算法又有較強的魯棒性。將二者結合提出一種融合差分進化操作的非支配排序遺傳算法（NSGA- Ⅲ -DE），用于求解車聯網計算卸載場景下的多目標任務卸載問題。

2.1 算法改進

本文設計了一種基于差分進化的自適應變異算子，不同于單點變異、倒序變異等變異算子，該自適應變異算子可以根據當前問題的特性和進化搜索過程中得到的信息來調整其行為，以更好地適應問題。

在第g次迭代過程中，從種群中隨機選擇3組個體Xp1（g），Xp2（g），Xp3（g），且p1≠p2≠p3≠i，差分進化算法是使用兩個不同的向量來干擾一個現有向量，進行差分操作，由此生成的變異向量為：

（20）

式中：S為縮放因子，且參數S能夠自適應調整。將變異算子中隨機選擇的3個個體從優至劣排序，得到Xa、Xb、Xc，對應適應度fa、fb、fc，將變異算子改為式（21）：

（21）

同時S的取值根據生成差分向量的兩個個體自適應變化，見式（22）：

（22）

式中：Sl=0.1；Su=0.9 。

差分進化交叉策略則是對第g代種群及其變異的中間體進行個體間的交叉操作，交叉算子的具體表達式見式（23）：

（23）

式中：cr∈[0， 1]為交叉概率，且cr的自適應調整表達式為：

（24）

式中：fi是個體Xj的適應度；fmin和fmax分別是當前種群中最差和最優個體的適應度；是當前種群適應度的平均值；crl和cru分別是交叉概率的下限和上限。

2.2 算法流程

本文算法在NSGA- Ⅲ算法的基礎上增加了差分進化策略，差分進化的交叉變異算子通過引入隨機性來增加搜索多樣性，擴展探索解空間，同時可以有效地利用歷史信息和種群中個體間的關系，提供更快的收斂速度，其框架如下：

（1）輸入系統模型的相關參數。

（2）初始化種群：從搜索空間中隨機生成一組個體作為初始種群pop，根據約束條件初始化。

（3）交叉變異操作：將基于差分進化的自適應變異交叉操作產生的新個體作為子代，并將父代種群和子代種群合并作為新的種群pop'。

（4）快速非支配排序：根據每個個體的目標函數值進行非支配排序，將所有個體分為不同等級。

（5）基于參考點的選擇操作：將個體與參考點進行關聯操作，并計算個體與參考點的距離選出下一代個體。

（6）更新種群：將新個體與原始個體合并，篩除不滿足約束條件的個體，得到擴展種群。

（7） 終止條件判斷：判斷是否滿足循環終止條件，若滿足，則輸出最終結果，否則返回第（3）步。

3 仿真實驗及分析

為驗證提出的卸載方案與算法的有效性，本文使用MATLAB軟件進行仿真實驗。在該仿真實驗中，為公平起見，所有算法方案的種群規模N=60，最大迭代次數G=250，終端設備數量（任務數量）Task設為40、60、80、100個。為驗證本文算法卸載策略的有效性，將其與NSGA- Ⅲ、NSGA- Ⅱ、MOEA/D、MOEA/D-DE四組算法卸載策略進行對比實驗。仿真實驗的主要參數設定見表1。

3.1 算法有效性評估

在對比實驗中將系統時延、能耗與服務器負載均衡作為重要評判指標，將參數最小化作為優化目標，與NSGA- Ⅱ、NSGA- Ⅲ、MOEA/D和MOEA/D-DE算法進行分析對比，統一進行250次迭代得到優化后pareto前沿如圖1所示，圖中每一個點都代表算法的一個卸載優化方案，本文卸載方案在時延、負載、能耗這3個維度上得到的解的集合更為接近原點，即本文的卸載方案更優。

在各個算法的優化下，產生的卸載方案對時延與能耗關系的影響如圖2所示。在各個算法策略下，能耗均隨時延的增加呈上升趨勢，這是由于任務在服務器上的執行時間增加，導致服務器產生更多能量消耗。根據式（15）可知，本文提出的NSGA- Ⅲ -DE算法優化策略，相較于其他算法在相同的時間消耗下能產生更少的能量消耗。負載與時延的關系如圖3所示，在相同負載下，NSGA- Ⅲ -DE算法的卸載策略產生的時延明顯低于其他算法，表明NSGA- Ⅲ -DE算法在尋找最優解方面性能突出，能夠避免局部最優情況的出現。各個算法下優化卸載方案中負載與能耗的關系如圖4所示，其他對比算法的優化方案在相同負載下的能耗相對一致，NSGA- Ⅲ -DE算法可保證相同負載下能耗更低，提高了解的質量。

3.2 不同算法的性能對比

NSGA- Ⅲ -DE算法、NSGA- Ⅱ算法、NSGA- Ⅲ算法、MOEA/D算法和MOEA/D-DE算法在不同用戶數量下對時延的影響如圖5所示。NSGA- Ⅲ -DE算法相較于其他算法在各個用戶數量下都有很好的時延表現，該策略下相較于其他算法時延最小，保證了任務卸載效率。該算法分別與NSGA- Ⅱ算法、NSGA- Ⅲ算法、MOEA/D算法和MOEA/D-DE算法相比，系統時延降低了18.5%、25.24%、151.6%和140.2%。

如圖6所示，在NSGA- Ⅲ -DE算法、NSGA- Ⅱ算法、NSGA- Ⅲ算法、MOEA/D算法和MOEA/D-DE算法的優化策略下，能耗隨用戶數量的增加而增加，在相同用戶數量下NSGA- Ⅲ -DE算法相較于其他算法的能量消耗相對更少，減少了不必要的能量浪費。同時NSGA- Ⅲ -DE算法相比于NSGA- Ⅱ算法、NSGA- Ⅲ算法、MOEA/D算法和MOEA/D-DE算法能量消耗分別減少了44.5%、35.6%、18.3%和41.1%。

不同用戶數量下不同算法對服務器負載均衡的影響如圖7所示。本文用標準差來表示服務器的負載均衡情況。負載均衡可使服務器避免因任務過多產生過熱或者損壞情況。從圖7中可明顯看出，隨著用戶的增多，各算法下的標準差也在增大，這是因為隨任務的增多，每個服務器接收的任務也在增多，整體標準差呈上升趨勢。NSGA- Ⅲ -DE算法相較于其他算法在相同數量任務下標準差更小，意味著該優化方案下服務器負載更加均衡；并且NSGA- Ⅲ -DE算法相比于NSGA- Ⅱ算法、NSGA- Ⅲ算法、MOEA/D算法和MOEA/D-DE算法負載均衡標準差減少了14.7%、12.5%、18.9%和46.4%。

4 結 語

本文通過邊緣服務器按計算資源優先級排序的方式，提高了計算資源的利用率。系統通過加入緩存策略加深卸載決策與傳輸時延的聯系，有效降低了系統時延。本文提出了一種結合差分進化機制的快速非支配排序遺傳算法（NSGA- Ⅲ -DE）的卸載方案，克服了局部最優解問題。仿真實驗表明，該算法有更好的尋優能力，在處理車聯網中時延、能耗、負載等問題上效果更優。未來將繼續嘗試該算法在真實智慧交通環境中的應用，考慮車輛在服務器之間信號切換對任務卸載的影響以及數據安全問題。

注：本文通訊作者為趙潔。

參考文獻

[1] DAI P， LIU K， WU X， et al. A learning algorithm for real-time service in vehicular networks with Mobile-Edge Computing [C]//ICC 2019-2019 IEEE International Conference on Communications （ICC）. [S.l.]： IEEE， 2019.

[2] HAN Z H， TAN H S， LI X Y， et al. On disc： online latency-sensitive job dispatching and scheduling in heterogeneous Edge-Clouds [J]. IEEE/ACM transactions on networking， 2019（99）： 1-14.

[3] JU X， SU S C， CHAO J X， et al. Computation offloading and tasks scheduling for the internet of vehicles in edge computing： A deep reinforcement learning-based pointer network approach [J]. Computer networks， 2023， 223： 109572.

[4] XU X， GU R， DAI F， et al. Multi-objective computation offloadingfor internet of vehicles in cloud-edge computing [J]. Wireless networks： The journal of mobile communication， computation and" information， 2020， 26（5）： 1611-1629.

[5] ZHAO J， LI Q， GONG Y， et al. Computation offloading and resource allocation for cloud assisted mobile edge computing in vehicular networks [J]. IEEE transactions on vehicular technology， 2019， 68（8）： 7944-7956

[6] DAI Y Y， XU D， MAHARTAN S， et al. Joint computation offloading and user association in Multi-Task mobile edge computing [J]. IEEE transactions on vehicular technology， 2018， 67（12）： 12313-12325.

[7] ZHANG B， ZHU C， JIN L， et al. Task offloading and resource allocation for intersection scenarios in vehicular edge computing [J]. International journal of sensor networks， 2023， 42（1）： 1-14.

[8] WANG Z M， DING Y R ， JIN X M， et al. Task offloading for edge computing in industrial internet with joint data compression and security protection[J]. The journal of supercomputing， 2022， 79（4）： 4291-4317.

[9] 王凌，吳楚格，范文慧. 邊緣計算資源分配與任務調度優化綜述[J]. 系統仿真學報，2021，33（3）：509-520.

[10]代美玲，劉周斌，郭少勇，等. 基于終端能耗和系統時延最小化的邊緣計算卸載及資源分配機制[J]. 電子與信息學報，2019，41（11）：2684-2690.

[11]李國燕，薛翔，劉毅，等. 改進TD3的SDN車聯網邊緣計算卸載策略[J]. 計算機集成制造系統，2023，29（5）：1627-1634.