摘要：為解決網(wǎng)格流量資源負載失衡問題，設計基于改進拉格朗日松弛算法的網(wǎng)格自適應負載均衡調(diào)度系統(tǒng)。網(wǎng)格任務管理器啟動基于改進拉格朗日松弛算法的自適應負載均衡調(diào)度模型，由基于自適應權(quán)重更新的鯨魚優(yōu)化算法和改進拉格朗日松弛算法，將原目標函數(shù)求解問題，轉(zhuǎn)換為不存在約束的對偶問題，當對偶間隙滿足需求后，直接輸出虛擬交換機遷移的全局最優(yōu)調(diào)度方案，發(fā)送至網(wǎng)格服務調(diào)度器，調(diào)度虛擬交換機鏈接遷移狀態(tài)。實驗結(jié)果證明，不同時刻網(wǎng)格流量發(fā)送速率與接收速率一致，系統(tǒng)可根據(jù)網(wǎng)格服務需求，自適應調(diào)度虛擬交換機遷移狀態(tài)，避免出現(xiàn)負載失衡問題。

關鍵詞：改進拉格朗日松弛算法；網(wǎng)格自適應；負載均衡；調(diào)度系統(tǒng)；尖點突變

中圖分類號：TP393文獻標識碼：A文章編號：1001-5922（2025）02-0150-05

The design of grid adaptive equilibrium scheduling system based on improved lagrange relaxation algorithm

LUAN Ning，XU Mingsheng，ZHOU Situ，LI Yangchun

（Jiangsu Electric Power Information Technology Co.，Ltd.，Nanjing 210029，China）

Abstract：In order to solve the problem of load imbalance of grid traffic resources，a grid adaptive load balancing scheduling system based on improved Lagrangian relaxation algorithm was designed.Grid task manager started the adaptive load balancing scheduling model based on the improved Lagrange relaxation algorithm，and converted the original objective function solution problem into a non-constrained dual problem by the whale optimization algo?rithm based on the adaptive weight update and the improved Lagrange relaxation algorithm，and when the dual gap met the requirements，it directly output the global optimal scheduling scheme for virtual switch migration and sent it to the grid service scheduler to schedule the virtual switch link migration state.The experimental results showed that the sending rate of grid traffic was consistent with the receiving rate at different times，and the system could adaptively schedule the migration status of the virtual switch according to the grid service requirements to avoid the problem of load imbalance.

Key words：improved lagrangian relaxation algorithm；grid adaptation；load balancing；dispatching system；sharp point mutation

服務網(wǎng)格（Service-mesh）的使用目的，是實現(xiàn)網(wǎng)絡虛擬環(huán)境上的資源共享和協(xié)同工作，消除信息孤島和資源孤島。因此，網(wǎng)格被視為信息社會的網(wǎng)絡基礎設施。但網(wǎng)格調(diào)度問題中，以往的調(diào)度方法大多以最短路徑為流量傳輸?shù)膬?yōu)選路徑，導致虛擬交換機出現(xiàn)負載失衡問題。近年來，已經(jīng)有很多學者對網(wǎng)格自適應負載均衡調(diào)度系統(tǒng)進行了研究，如對電信綜合網(wǎng)格管理問題進行研究[1]。設計了衛(wèi)星資源一體化網(wǎng)格組織模型[2]。結(jié)合前人研究基礎，將網(wǎng)格資源調(diào)度問題進行系統(tǒng)化研究，設計了基于改進拉格朗日松弛算法的網(wǎng)格自適應負載均衡調(diào)度系統(tǒng)，主要以虛擬交換機遷移管理的方式，實現(xiàn)網(wǎng)格自適應負載均衡調(diào)度。

1網(wǎng)格自適應負載均衡調(diào)度系統(tǒng)

1.1系統(tǒng)架構(gòu)設計

從網(wǎng)格服務調(diào)度功能角度設計，基于改進拉格朗日松弛算法的網(wǎng)格自適應負載均衡調(diào)度系統(tǒng)結(jié)構(gòu)設計詳情如圖1所示。

由圖1可知，網(wǎng)格服務調(diào)度器用于接收具備針對性的網(wǎng)格自適應負載均衡調(diào)度策略，且與虛擬交換機存在多個接口，負責根據(jù)調(diào)度方案管理虛擬交換機的運行狀態(tài)；網(wǎng)格任務管理器的功能是使用基于改進拉格朗日松弛算法的自適應負載均衡調(diào)度模型，設計自適應負載均衡調(diào)度方案；網(wǎng)格任務監(jiān)視器負責利用基于尖點突變模型的服務網(wǎng)格流量異常遠程診斷方法，分析網(wǎng)格流量是否存在負載失衡問題。

1.2網(wǎng)格任務監(jiān)視器設計

由于服務網(wǎng)格環(huán)境具有動態(tài)和多變的特點，這種動態(tài)性可以表現(xiàn)為新的服務需求持續(xù)加入，同時也有服務可能會退出，而且服務的形式也可能發(fā)生改變。此外，用戶的需求也可能在執(zhí)行過程中發(fā)生變更[3]。

因此，任務的執(zhí)行過程應進行實時監(jiān)控，以便在出現(xiàn)異常情況時，能夠及時通知服務調(diào)度器重新進行調(diào)度，從而提高整個系統(tǒng)的穩(wěn)定性和可靠性[4]。

1.3網(wǎng)格任務管理器設計

網(wǎng)格任務管理器負責處理網(wǎng)格調(diào)度任務請求，根據(jù)需求分析生成相應的調(diào)度方案，交由網(wǎng)格服務調(diào)度器執(zhí)行。這種設計使系統(tǒng)更具層次性，減輕了網(wǎng)格服務調(diào)度器的負擔。

1.4網(wǎng)格服務調(diào)度器設計

圖2是網(wǎng)格服務調(diào)度器的組織架構(gòu)圖。

由圖2可知。當網(wǎng)格任務管理器通過接口，將調(diào)度方案輸入網(wǎng)格服務調(diào)度器后，接口將調(diào)度方案中的調(diào)度任務發(fā)送至等待隊列中，由虛擬交換機資源匹配模塊，控制虛擬交換機鏈接遷移狀態(tài)。

1.5基于尖點突變模型的服務網(wǎng)格流量異常遠程診斷方法

此設計主要考慮服務網(wǎng)格正常流量、異常流量的平衡曲面存在偏差，設定服務網(wǎng)格流量負載失衡時，異常流量特征已知，在時間窗口是β，假如正常流量的尖點突變模型是Ytβ= （yt…yβ） ，提取每個網(wǎng)格流量監(jiān)控點yt對應的網(wǎng)格流量控制變量的時間序列后，訓練尖點突變模型。設定訓練所用勢函數(shù)參數(shù)是φ、φ，如果φ、φ為最小值，網(wǎng)格流量即為最穩(wěn)定狀態(tài)，無負載失衡問題。為了客觀分析網(wǎng)格流量狀態(tài)，設計平衡曲面函數(shù)與分歧集函數(shù)，將2種函數(shù)融合應用。設定網(wǎng)格流量狀態(tài)是F（φφ） ：

F（φφ） = min{|4yt（3）+ 2φvtyt+ φut|2}"" （1）

式中：ut、vt為一階導數(shù)。如果ut數(shù)值是0，那么F（φφ） 為最小值，網(wǎng)格流量便不存在負載失衡問題，此時φ、φ需符合式（2）條件：

式中：? 是給定閾值。

求得?、φ后，分析目前網(wǎng)格流量狀態(tài)和正常流量平衡曲面的偏離狀態(tài)，是否與? 存在分歧，由此便可分析網(wǎng)格流量是否穩(wěn)定。為保證網(wǎng)格流量狀態(tài)診斷精度，模型使用突變距離E，分析目前網(wǎng)格流量狀態(tài)和正常流量平衡曲面的偏離度[5]。針對某個網(wǎng)格流量監(jiān)控點yt，突變距離E表示yt與正常流量平衡曲面F′（y） 的Eu-clidean距離最小值。則：

E= y） ? （yt F′（y））""""""""""""" （3）

網(wǎng)格環(huán)境中，正常流量存在隨機特征，對應的突變距離滿足正態(tài)分布，設置網(wǎng)格流量置信區(qū)間是ε，則閾值的運算方法是：

? = ε+ δη（4）

式中：δ、η分別是分位數(shù)、突變序列方差；ε是網(wǎng)格流量突變序列均值。

網(wǎng)格流量異常診斷時，使用Hoeffding不等式設計判定規(guī)則：

根據(jù)式（5）規(guī)則，便可將突變距離大于給定閾值的網(wǎng)格，診斷為負載失衡狀態(tài)。

1.6基于改進拉格朗日松弛算法的自適應負載均衡調(diào)度模型

1.6.1網(wǎng)格自適應負載均衡調(diào)度目標函數(shù)設計

當診斷網(wǎng)格流量處于負載失衡狀態(tài)后，設定網(wǎng)格流量負載失衡范圍是ym，系統(tǒng)使用基于改進拉格朗日松弛算法的自適應負載均衡調(diào)度模型，實時地適應服務網(wǎng)格中服務的動態(tài)變化和多樣化的通信模式[6]。設計網(wǎng)格自適應負載均衡調(diào)度的目標函數(shù)為：

O*= min Sj′ CPUv+ （1- Sj） ′ CPUj-kj 2（6）

式中：m代表網(wǎng)格負載失衡范圍ym的虛擬交換機數(shù)目；Sj屬于指示變量，代表虛擬交換機j鏈接是否需要遷移至理想位置，如果Sj數(shù)值是1，那么表示虛擬交換機j需要遷移；CPUj代表虛擬交換機j的CPU資源利用率；kj代表虛擬交換機j的理想資源利用率，理想資源利用率是指網(wǎng)格負載均衡時CPU資源利用狀態(tài)。

約束條件是：

?（y m）Sj′ CPUv+ （1- Sj） ′ CPUj-kjlt;K（7）

式中：K是虛擬交換機CPU容量最大限值。此約束條件表示網(wǎng)格負載均衡時CPU資源利用狀態(tài)，不能超過虛擬交換機CPU容量最大限值。

1.6.2基于改進拉格朗日松弛算法的調(diào)度方案求解

拉格朗日松弛算法運算效率高，且自適應性能好，在混合整數(shù)規(guī)劃問題中使用較多[7]。本文以選擇、修正拉格朗日乘子的方式，改進拉格朗日松弛算法，從而實現(xiàn)網(wǎng)格自適應負載均衡調(diào)度的全局求解。

把約束條件式（7）與目標函數(shù)式（6）融合分析，使用拉格朗日乘子θt、ψt，便可構(gòu)建拉格朗日函數(shù)，即為求解的調(diào)度方案p*；p*也屬于拉格朗日函數(shù)求解的問題對偶最優(yōu)值。則：

p*= θt kj- CPUj+ ψt kj+ Zr- CPUj× K

式中：kj、CPUj分別代表負載均衡所需遷移的第j個虛擬交換機CPU資源利用率、目前第j個虛擬交換機CPU資源利用狀態(tài)；Zr為備用約束量。

將式（6）導進式（8），使用拉格朗日松弛算法求解，原函數(shù)的最優(yōu)解O*和對偶最優(yōu)值p*之間差異設成“對偶間隙”，使用相對對偶間隙P*作為最優(yōu)解尋優(yōu)準則。則：

當相對對偶間隙P*數(shù)值滿足給定值，便可結(jié)束尋優(yōu)。

為了保證網(wǎng)格自適應負載均衡調(diào)度最優(yōu)解的求解精確度，使用基于自適應權(quán)重更新的鯨魚優(yōu)化算法，改進拉格朗日松弛算法[7]。

以往常用次梯度法迭代求解拉格朗日對偶問題，若問題規(guī)模顯著，求解效率便會變低，且自適應能力較差。所以，使用基于自適應權(quán)重更新的鯨魚優(yōu)化算法，改進拉格朗日松弛算法，提高求解效率。此算法分為包圍捕食、氣泡捕獵、搜尋獵物3個階段。

在包圍捕食、氣泡捕獵階段中，鯨魚處于局部尋優(yōu)狀態(tài)，為了保證局部尋優(yōu)效果，引入自適應權(quán)重更新方法，在鯨魚靠近獵物時，將自適應權(quán)重調(diào)小，改變鯨魚當前最優(yōu)位置，優(yōu)化鯨魚局部尋優(yōu)效果。自適應權(quán)重更新方法是：

?= sin+ π+ 1（10）

式中：tmax是迭代次數(shù)最大值。自適應權(quán)重更新下，鯨魚個體位置更新方法是：

式中：是迭代期間鯨魚個體位置更新結(jié)果，即為尋優(yōu)改進后拉格朗日函數(shù)；、為系數(shù)向量。

使用基于自適應權(quán)重更新的鯨魚優(yōu)化算法和改進拉格朗日松弛算法后，基于改進拉格朗日松弛算法的調(diào)度方案求解步驟是：

（1）導入全部負載失衡的網(wǎng)格流量數(shù)據(jù)；

（2）初始化虛擬交換機調(diào)度數(shù)據(jù)與拉格朗日乘子；

（3）構(gòu)建t個時刻的虛擬交換機遷移問題和原問題的對偶問題；

（4）設定相對對偶間隙P*準則；

（5）使用基于自適應權(quán)重更新的鯨魚優(yōu)化算法，將拉格朗日乘子進行尋優(yōu)設定，根據(jù)相對對偶間隙P*準則，篩選目前拉格朗日乘子最優(yōu)解，改進拉格朗日松弛算法；

（6）改進拉格朗日松弛算法后，使用式（8）輸出目前調(diào)度方案為最優(yōu)方案。

2實驗分析

為分析系統(tǒng)的使用效果，搭建如圖3所示實驗環(huán)境。

由圖3可知，j1～j7為虛擬交換機編碼；A1～A7為服務網(wǎng)格中主機編碼。所搭建實驗環(huán)境，虛擬交換機各條鏈路帶寬是150 MB/s，由Iperf工具對服務網(wǎng)格網(wǎng)絡注入數(shù)據(jù)，主機A1與A4朝主機A5、A7傳輸Ⅰ類電力業(yè)務，主機A2對主機A6傳輸Ⅱ類電力業(yè)務，主機A3對主機A7傳輸Ⅲ類電力業(yè)務。為測試本文系統(tǒng)的可用價值，設定主機A1、A2以及A3同時對主機A5、主機A6、主機A7傳輸數(shù)據(jù)，使用Ryu控制器提取虛擬交換機j1～j7的運行日志信息，分析網(wǎng)格狀態(tài)參數(shù)[9]。則本文系統(tǒng)使用前后，網(wǎng)格流量傳輸狀態(tài)參數(shù)如表1、表2所示。

由表1與表2對比可知，系統(tǒng)使用后，網(wǎng)格流量傳輸狀態(tài)得到優(yōu)化，時延、丟包率2項指標均變小，CPU資源利用率增大，表示系統(tǒng)的使用，可有效調(diào)度網(wǎng)格自適應負載均衡，優(yōu)化網(wǎng)格流量傳輸狀態(tài)[10]。

測試系統(tǒng)使用下，各個虛擬交換機的CPU資源利用率，詳情如圖4、圖5所示。

由圖4、圖5可知，系統(tǒng)使用前，多個虛擬交換機的CPU資源利用率均大于最大限值，而有的虛擬交換機CPU資源利用率較小，說明CPU資源利用不均衡，存在負載失衡問題。使用系統(tǒng)后，各個虛擬交換機的CPU資源利用率均衡，此時網(wǎng)格流量不存在負載失衡問題[11]。

設定網(wǎng)格自適應負載均衡調(diào)度方案相對對偶間隙的收斂標準是0.10，測試拉格朗日松弛算法改進前后，迭代50次求解網(wǎng)格自適應負載均衡調(diào)度方案時的對偶間隙變化[12]，具體如圖6所示。

由圖6可知，拉格朗日松弛算法改進前，迭代次數(shù)為50次時，相對對偶間隙并沒有滿足0.01這一條件，說明在50次迭代過程中，未能獲取最優(yōu)網(wǎng)格自適應負載均衡調(diào)度方案[13]；拉格朗日松弛算法改進后，迭代25次，相對對偶間隙便達到0.01這一標準，改進后拉格朗日松弛算法更易跳出振蕩模式，收斂效率得以優(yōu)化。

設定網(wǎng)格流量在不同時刻出現(xiàn)不同的流量要求，測試系統(tǒng)使用后，網(wǎng)格自適應負載均衡效果[14]如表3所示。

由表3可知，不同時刻的網(wǎng)格流量發(fā)送速率與接收速率一致，說明網(wǎng)格自適應負載均衡調(diào)度效果較好，設計的系統(tǒng)可根據(jù)網(wǎng)格服務需求，自適應調(diào)度虛擬交換機遷移狀態(tài)，避免出現(xiàn)鏈路堵塞問題，有效實現(xiàn)自適應負載均衡[15]。

3結(jié)語

針對網(wǎng)格流量易出現(xiàn)負載失衡問題，設計了基于改進拉格朗日松弛算法的網(wǎng)格自適應負載均衡調(diào)度系統(tǒng)，此系統(tǒng)可根據(jù)實時的網(wǎng)絡和服務狀況來動態(tài)地分配請求負載，將請求路由到最優(yōu)的服務實例上，從而提高整個系統(tǒng)的性能和可靠性，達到動態(tài)負載均衡，確保整個網(wǎng)格系統(tǒng)能夠應對不斷變化的負載情況，保持服務網(wǎng)格流量穩(wěn)定和可靠的運行狀態(tài)。

【參考文獻】

[1]朱明英，華竹軒，史萌.基于數(shù)字化轉(zhuǎn)型的電信綜合網(wǎng)格管理的研究和實踐[J].電信科學，2021，37（11）：128-134.

[2]張瑋，王守斌，程承旗，等.一種衛(wèi)星資源一體化網(wǎng)格組織模型[J].武漢大學學報（信息科學版），2020，45（3）：331-336.

[3]金紅洋，申永山，滕云，等.考慮碳減排的多能源系統(tǒng)網(wǎng)格化優(yōu)化調(diào)度方法[J].可再生能源，2023，41（2）：261-267.

[4]楚志剛，陶永才.遺傳優(yōu)化的混合網(wǎng)格計算調(diào)度模型SCE部署研究[J].計算機仿真，2021，38（5）：329-333.

[5]張學欽.基于MSTP技術(shù)的地調(diào)調(diào)度數(shù)據(jù)網(wǎng)第二張網(wǎng)規(guī)劃設計分析研究.[J].粘接，2021，47（8）：178-182.

[6]徐林浩，錢斌，胡蓉，等.綠色車輛路徑問題的改進拉格朗日松弛算法[J].廣東工業(yè)大學學報，2022，39（5）：61-67.

[7]向征.基于改進拉格朗日松弛算法的電力通信網(wǎng)絡負載均衡優(yōu)化策略研究[J].電測與儀表，2023，60（4）：85-91.

[8]何昕，韓丹，蔣豪.基于拉格朗日松弛算法的終端區(qū)飛機排序研究[J].航空計算技術(shù)，2016，46（3）：1-3.

[9]軒華.運輸能力有限混合流水車間調(diào)度的改進拉格朗日松弛算法[J].計算機集成制造系統(tǒng)，2013，19（7）：1633-1639.

[10]米翠花.基于改進粒子群算法的網(wǎng)絡路由選擇和CFA的優(yōu)化研究[D].蘭州：蘭州大學，2007.

[11]湯偉，楊鋮.基于數(shù)據(jù)挖掘技術(shù)的電力調(diào)度系統(tǒng)設計與實現(xiàn)[J].自動化與儀器儀表，2019（5）：55-58.

[12]黃偉鴻，趙子奇，安琪.基于IIoT的增材制造生產(chǎn)調(diào)度系統(tǒng)設計與應用研究[J].新型工業(yè)化，2023，13（9）：79-87.

[13]譚振鵬，鄧智廣.基于改進蟻群算法的電力自動調(diào)度模型構(gòu)建計[J].粘接，2021，48（11）：88-91.

[14]許丹莉，朱文，彭超逸，等.基于云邊協(xié)同的虛擬電廠調(diào)度系統(tǒng)設計[J].電力信息與通信技術(shù)，2023，21（7）：44-48.

[15]劉玉.生活垃圾中轉(zhuǎn)站的自動化控制系統(tǒng)設計[J].自動化應用，2023，64（14）：74-76.

（責任編輯：平海，蘇幔）