








摘要:為解決網(wǎng)格流量資源負(fù)載失衡問題,設(shè)計(jì)基于改進(jìn)拉格朗日松弛算法的網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度系統(tǒng)。網(wǎng)格任務(wù)管理器啟動(dòng)基于改進(jìn)拉格朗日松弛算法的自適應(yīng)負(fù)載均衡調(diào)度模型,由基于自適應(yīng)權(quán)重更新的鯨魚優(yōu)化算法和改進(jìn)拉格朗日松弛算法,將原目標(biāo)函數(shù)求解問題,轉(zhuǎn)換為不存在約束的對偶問題,當(dāng)對偶間隙滿足需求后,直接輸出虛擬交換機(jī)遷移的全局最優(yōu)調(diào)度方案,發(fā)送至網(wǎng)格服務(wù)調(diào)度器,調(diào)度虛擬交換機(jī)鏈接遷移狀態(tài)。實(shí)驗(yàn)結(jié)果證明,不同時(shí)刻網(wǎng)格流量發(fā)送速率與接收速率一致,系統(tǒng)可根據(jù)網(wǎng)格服務(wù)需求,自適應(yīng)調(diào)度虛擬交換機(jī)遷移狀態(tài),避免出現(xiàn)負(fù)載失衡問題。
關(guān)鍵詞:改進(jìn)拉格朗日松弛算法;網(wǎng)格自適應(yīng);負(fù)載均衡;調(diào)度系統(tǒng);尖點(diǎn)突變
中圖分類號:TP393文獻(xiàn)標(biāo)識碼: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ù)網(wǎng)格(Service-mesh)的使用目的,是實(shí)現(xiàn)網(wǎng)絡(luò)虛擬環(huán)境上的資源共享和協(xié)同工作,消除信息孤島和資源孤島。因此,網(wǎng)格被視為信息社會(huì)的網(wǎng)絡(luò)基礎(chǔ)設(shè)施。但網(wǎng)格調(diào)度問題中,以往的調(diào)度方法大多以最短路徑為流量傳輸?shù)膬?yōu)選路徑,導(dǎo)致虛擬交換機(jī)出現(xiàn)負(fù)載失衡問題。近年來,已經(jīng)有很多學(xué)者對網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度系統(tǒng)進(jìn)行了研究,如對電信綜合網(wǎng)格管理問題進(jìn)行研究[1]。設(shè)計(jì)了衛(wèi)星資源一體化網(wǎng)格組織模型[2]。結(jié)合前人研究基礎(chǔ),將網(wǎng)格資源調(diào)度問題進(jìn)行系統(tǒng)化研究,設(shè)計(jì)了基于改進(jìn)拉格朗日松弛算法的網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度系統(tǒng),主要以虛擬交換機(jī)遷移管理的方式,實(shí)現(xiàn)網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度。
1網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度系統(tǒng)
1.1系統(tǒng)架構(gòu)設(shè)計(jì)
從網(wǎng)格服務(wù)調(diào)度功能角度設(shè)計(jì),基于改進(jìn)拉格朗日松弛算法的網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度系統(tǒng)結(jié)構(gòu)設(shè)計(jì)詳情如圖1所示。
由圖1可知,網(wǎng)格服務(wù)調(diào)度器用于接收具備針對性的網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度策略,且與虛擬交換機(jī)存在多個(gè)接口,負(fù)責(zé)根據(jù)調(diào)度方案管理虛擬交換機(jī)的運(yùn)行狀態(tài);網(wǎng)格任務(wù)管理器的功能是使用基于改進(jìn)拉格朗日松弛算法的自適應(yīng)負(fù)載均衡調(diào)度模型,設(shè)計(jì)自適應(yīng)負(fù)載均衡調(diào)度方案;網(wǎng)格任務(wù)監(jiān)視器負(fù)責(zé)利用基于尖點(diǎn)突變模型的服務(wù)網(wǎng)格流量異常遠(yuǎn)程診斷方法,分析網(wǎng)格流量是否存在負(fù)載失衡問題。
1.2網(wǎng)格任務(wù)監(jiān)視器設(shè)計(jì)
由于服務(wù)網(wǎng)格環(huán)境具有動(dòng)態(tài)和多變的特點(diǎn),這種動(dòng)態(tài)性可以表現(xiàn)為新的服務(wù)需求持續(xù)加入,同時(shí)也有服務(wù)可能會(huì)退出,而且服務(wù)的形式也可能發(fā)生改變。此外,用戶的需求也可能在執(zhí)行過程中發(fā)生變更[3]。
因此,任務(wù)的執(zhí)行過程應(yīng)進(jìn)行實(shí)時(shí)監(jiān)控,以便在出現(xiàn)異常情況時(shí),能夠及時(shí)通知服務(wù)調(diào)度器重新進(jìn)行調(diào)度,從而提高整個(gè)系統(tǒng)的穩(wěn)定性和可靠性[4]。
1.3網(wǎng)格任務(wù)管理器設(shè)計(jì)
網(wǎng)格任務(wù)管理器負(fù)責(zé)處理網(wǎng)格調(diào)度任務(wù)請求,根據(jù)需求分析生成相應(yīng)的調(diào)度方案,交由網(wǎng)格服務(wù)調(diào)度器執(zhí)行。這種設(shè)計(jì)使系統(tǒng)更具層次性,減輕了網(wǎng)格服務(wù)調(diào)度器的負(fù)擔(dān)。
1.4網(wǎng)格服務(wù)調(diào)度器設(shè)計(jì)
圖2是網(wǎng)格服務(wù)調(diào)度器的組織架構(gòu)圖。
由圖2可知。當(dāng)網(wǎng)格任務(wù)管理器通過接口,將調(diào)度方案輸入網(wǎng)格服務(wù)調(diào)度器后,接口將調(diào)度方案中的調(diào)度任務(wù)發(fā)送至等待隊(duì)列中,由虛擬交換機(jī)資源匹配模塊,控制虛擬交換機(jī)鏈接遷移狀態(tài)。
1.5基于尖點(diǎn)突變模型的服務(wù)網(wǎng)格流量異常遠(yuǎn)程診斷方法
此設(shè)計(jì)主要考慮服務(wù)網(wǎng)格正常流量、異常流量的平衡曲面存在偏差,設(shè)定服務(wù)網(wǎng)格流量負(fù)載失衡時(shí),異常流量特征已知,在時(shí)間窗口是β,假如正常流量的尖點(diǎn)突變模型是Ytβ= (yt…yβ) ,提取每個(gè)網(wǎng)格流量監(jiān)控點(diǎn)yt對應(yīng)的網(wǎng)格流量控制變量的時(shí)間序列后,訓(xùn)練尖點(diǎn)突變模型。設(shè)定訓(xùn)練所用勢函數(shù)參數(shù)是φ、φ,如果φ、φ為最小值,網(wǎng)格流量即為最穩(wěn)定狀態(tài),無負(fù)載失衡問題。為了客觀分析網(wǎng)格流量狀態(tài),設(shè)計(jì)平衡曲面函數(shù)與分歧集函數(shù),將2種函數(shù)融合應(yīng)用。設(shè)定網(wǎng)格流量狀態(tài)是F(φφ) :
F(φφ) = min{|4yt(3)+ 2φvtyt+ φut|2}"" (1)
式中:ut、vt為一階導(dǎo)數(shù)。如果ut數(shù)值是0,那么F(φφ) 為最小值,網(wǎng)格流量便不存在負(fù)載失衡問題,此時(shí)φ、φ需符合式(2)條件:
式中:? 是給定閾值。
求得?、φ后,分析目前網(wǎng)格流量狀態(tài)和正常流量平衡曲面的偏離狀態(tài),是否與? 存在分歧,由此便可分析網(wǎng)格流量是否穩(wěn)定。為保證網(wǎng)格流量狀態(tài)診斷精度,模型使用突變距離E,分析目前網(wǎng)格流量狀態(tài)和正常流量平衡曲面的偏離度[5]。針對某個(gè)網(wǎng)格流量監(jiān)控點(diǎn)yt,突變距離E表示yt與正常流量平衡曲面F′(y) 的Eu-clidean距離最小值。則:
E= y) ? (yt F′(y))""""""""""""" (3)
網(wǎng)格環(huán)境中,正常流量存在隨機(jī)特征,對應(yīng)的突變距離滿足正態(tài)分布,設(shè)置網(wǎng)格流量置信區(qū)間是ε,則閾值的運(yùn)算方法是:
? = ε+ δη(4)
式中:δ、η分別是分位數(shù)、突變序列方差;ε是網(wǎng)格流量突變序列均值。
網(wǎng)格流量異常診斷時(shí),使用Hoeffding不等式設(shè)計(jì)判定規(guī)則:
根據(jù)式(5)規(guī)則,便可將突變距離大于給定閾值的網(wǎng)格,診斷為負(fù)載失衡狀態(tài)。
1.6基于改進(jìn)拉格朗日松弛算法的自適應(yīng)負(fù)載均衡調(diào)度模型
1.6.1網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度目標(biāo)函數(shù)設(shè)計(jì)
當(dāng)診斷網(wǎng)格流量處于負(fù)載失衡狀態(tài)后,設(shè)定網(wǎng)格流量負(fù)載失衡范圍是ym,系統(tǒng)使用基于改進(jìn)拉格朗日松弛算法的自適應(yīng)負(fù)載均衡調(diào)度模型,實(shí)時(shí)地適應(yīng)服務(wù)網(wǎng)格中服務(wù)的動(dòng)態(tài)變化和多樣化的通信模式[6]。設(shè)計(jì)網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度的目標(biāo)函數(shù)為:
O*= min Sj′ CPUv+ (1- Sj) ′ CPUj-kj 2(6)
式中:m代表網(wǎng)格負(fù)載失衡范圍ym的虛擬交換機(jī)數(shù)目;Sj屬于指示變量,代表虛擬交換機(jī)j鏈接是否需要遷移至理想位置,如果Sj數(shù)值是1,那么表示虛擬交換機(jī)j需要遷移;CPUj代表虛擬交換機(jī)j的CPU資源利用率;kj代表虛擬交換機(jī)j的理想資源利用率,理想資源利用率是指網(wǎng)格負(fù)載均衡時(shí)CPU資源利用狀態(tài)。
約束條件是:
?(y m)Sj′ CPUv+ (1- Sj) ′ CPUj-kjlt;K(7)
式中:K是虛擬交換機(jī)CPU容量最大限值。此約束條件表示網(wǎng)格負(fù)載均衡時(shí)CPU資源利用狀態(tài),不能超過虛擬交換機(jī)CPU容量最大限值。
1.6.2基于改進(jìn)拉格朗日松弛算法的調(diào)度方案求解
拉格朗日松弛算法運(yùn)算效率高,且自適應(yīng)性能好,在混合整數(shù)規(guī)劃問題中使用較多[7]。本文以選擇、修正拉格朗日乘子的方式,改進(jìn)拉格朗日松弛算法,從而實(shí)現(xiàn)網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度的全局求解。
把約束條件式(7)與目標(biāo)函數(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分別代表負(fù)載均衡所需遷移的第j個(gè)虛擬交換機(jī)CPU資源利用率、目前第j個(gè)虛擬交換機(jī)CPU資源利用狀態(tài);Zr為備用約束量。
將式(6)導(dǎo)進(jìn)式(8),使用拉格朗日松弛算法求解,原函數(shù)的最優(yōu)解O*和對偶最優(yōu)值p*之間差異設(shè)成“對偶間隙”,使用相對對偶間隙P*作為最優(yōu)解尋優(yōu)準(zhǔn)則。則:
當(dāng)相對對偶間隙P*數(shù)值滿足給定值,便可結(jié)束尋優(yōu)。
為了保證網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度最優(yōu)解的求解精確度,使用基于自適應(yīng)權(quán)重更新的鯨魚優(yōu)化算法,改進(jìn)拉格朗日松弛算法[7]。
以往常用次梯度法迭代求解拉格朗日對偶問題,若問題規(guī)模顯著,求解效率便會(huì)變低,且自適應(yīng)能力較差。所以,使用基于自適應(yīng)權(quán)重更新的鯨魚優(yōu)化算法,改進(jìn)拉格朗日松弛算法,提高求解效率。此算法分為包圍捕食、氣泡捕獵、搜尋獵物3個(gè)階段。
在包圍捕食、氣泡捕獵階段中,鯨魚處于局部尋優(yōu)狀態(tài),為了保證局部尋優(yōu)效果,引入自適應(yīng)權(quán)重更新方法,在鯨魚靠近獵物時(shí),將自適應(yīng)權(quán)重調(diào)小,改變鯨魚當(dāng)前最優(yōu)位置,優(yōu)化鯨魚局部尋優(yōu)效果。自適應(yīng)權(quán)重更新方法是:
?= sin+ π+ 1(10)
式中:tmax是迭代次數(shù)最大值。自適應(yīng)權(quán)重更新下,鯨魚個(gè)體位置更新方法是:
式中:是迭代期間鯨魚個(gè)體位置更新結(jié)果,即為尋優(yōu)改進(jìn)后拉格朗日函數(shù);、為系數(shù)向量。
使用基于自適應(yīng)權(quán)重更新的鯨魚優(yōu)化算法和改進(jìn)拉格朗日松弛算法后,基于改進(jìn)拉格朗日松弛算法的調(diào)度方案求解步驟是:
(1)導(dǎo)入全部負(fù)載失衡的網(wǎng)格流量數(shù)據(jù);
(2)初始化虛擬交換機(jī)調(diào)度數(shù)據(jù)與拉格朗日乘子;
(3)構(gòu)建t個(gè)時(shí)刻的虛擬交換機(jī)遷移問題和原問題的對偶問題;
(4)設(shè)定相對對偶間隙P*準(zhǔn)則;
(5)使用基于自適應(yīng)權(quán)重更新的鯨魚優(yōu)化算法,將拉格朗日乘子進(jìn)行尋優(yōu)設(shè)定,根據(jù)相對對偶間隙P*準(zhǔn)則,篩選目前拉格朗日乘子最優(yōu)解,改進(jìn)拉格朗日松弛算法;
(6)改進(jìn)拉格朗日松弛算法后,使用式(8)輸出目前調(diào)度方案為最優(yōu)方案。
2實(shí)驗(yàn)分析
為分析系統(tǒng)的使用效果,搭建如圖3所示實(shí)驗(yàn)環(huán)境。
由圖3可知,j1~j7為虛擬交換機(jī)編碼;A1~A7為服務(wù)網(wǎng)格中主機(jī)編碼。所搭建實(shí)驗(yàn)環(huán)境,虛擬交換機(jī)各條鏈路帶寬是150 MB/s,由Iperf工具對服務(wù)網(wǎng)格網(wǎng)絡(luò)注入數(shù)據(jù),主機(jī)A1與A4朝主機(jī)A5、A7傳輸Ⅰ類電力業(yè)務(wù),主機(jī)A2對主機(jī)A6傳輸Ⅱ類電力業(yè)務(wù),主機(jī)A3對主機(jī)A7傳輸Ⅲ類電力業(yè)務(wù)。為測試本文系統(tǒng)的可用價(jià)值,設(shè)定主機(jī)A1、A2以及A3同時(shí)對主機(jī)A5、主機(jī)A6、主機(jī)A7傳輸數(shù)據(jù),使用Ryu控制器提取虛擬交換機(jī)j1~j7的運(yùn)行日志信息,分析網(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)化,時(shí)延、丟包率2項(xiàng)指標(biāo)均變小,CPU資源利用率增大,表示系統(tǒng)的使用,可有效調(diào)度網(wǎng)格自適應(yīng)負(fù)載均衡,優(yōu)化網(wǎng)格流量傳輸狀態(tài)[10]。
測試系統(tǒng)使用下,各個(gè)虛擬交換機(jī)的CPU資源利用率,詳情如圖4、圖5所示。
由圖4、圖5可知,系統(tǒng)使用前,多個(gè)虛擬交換機(jī)的CPU資源利用率均大于最大限值,而有的虛擬交換機(jī)CPU資源利用率較小,說明CPU資源利用不均衡,存在負(fù)載失衡問題。使用系統(tǒng)后,各個(gè)虛擬交換機(jī)的CPU資源利用率均衡,此時(shí)網(wǎng)格流量不存在負(fù)載失衡問題[11]。
設(shè)定網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度方案相對對偶間隙的收斂標(biāo)準(zhǔn)是0.10,測試?yán)窭嗜账沙谒惴ǜ倪M(jìn)前后,迭代50次求解網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度方案時(shí)的對偶間隙變化[12],具體如圖6所示。
由圖6可知,拉格朗日松弛算法改進(jìn)前,迭代次數(shù)為50次時(shí),相對對偶間隙并沒有滿足0.01這一條件,說明在50次迭代過程中,未能獲取最優(yōu)網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度方案[13];拉格朗日松弛算法改進(jìn)后,迭代25次,相對對偶間隙便達(dá)到0.01這一標(biāo)準(zhǔn),改進(jìn)后拉格朗日松弛算法更易跳出振蕩模式,收斂效率得以優(yōu)化。
設(shè)定網(wǎng)格流量在不同時(shí)刻出現(xiàn)不同的流量要求,測試系統(tǒng)使用后,網(wǎng)格自適應(yīng)負(fù)載均衡效果[14]如表3所示。
由表3可知,不同時(shí)刻的網(wǎng)格流量發(fā)送速率與接收速率一致,說明網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度效果較好,設(shè)計(jì)的系統(tǒng)可根據(jù)網(wǎng)格服務(wù)需求,自適應(yīng)調(diào)度虛擬交換機(jī)遷移狀態(tài),避免出現(xiàn)鏈路堵塞問題,有效實(shí)現(xiàn)自適應(yīng)負(fù)載均衡[15]。
3結(jié)語
針對網(wǎng)格流量易出現(xiàn)負(fù)載失衡問題,設(shè)計(jì)了基于改進(jìn)拉格朗日松弛算法的網(wǎng)格自適應(yīng)負(fù)載均衡調(diào)度系統(tǒng),此系統(tǒng)可根據(jù)實(shí)時(shí)的網(wǎng)絡(luò)和服務(wù)狀況來動(dòng)態(tài)地分配請求負(fù)載,將請求路由到最優(yōu)的服務(wù)實(shí)例上,從而提高整個(gè)系統(tǒng)的性能和可靠性,達(dá)到動(dòng)態(tài)負(fù)載均衡,確保整個(gè)網(wǎng)格系統(tǒng)能夠應(yīng)對不斷變化的負(fù)載情況,保持服務(wù)網(wǎng)格流量穩(wěn)定和可靠的運(yùn)行狀態(tài)。
【參考文獻(xiàn)】
[1]朱明英,華竹軒,史萌.基于數(shù)字化轉(zhuǎn)型的電信綜合網(wǎng)格管理的研究和實(shí)踐[J].電信科學(xué),2021,37(11):128-134.
[2]張瑋,王守斌,程承旗,等.一種衛(wèi)星資源一體化網(wǎng)格組織模型[J].武漢大學(xué)學(xué)報(bào)(信息科學(xué)版),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)格計(jì)算調(diào)度模型SCE部署研究[J].計(jì)算機(jī)仿真,2021,38(5):329-333.
[5]張學(xué)欽.基于MSTP技術(shù)的地調(diào)調(diào)度數(shù)據(jù)網(wǎng)第二張網(wǎng)規(guī)劃設(shè)計(jì)分析研究.[J].粘接,2021,47(8):178-182.
[6]徐林浩,錢斌,胡蓉,等.綠色車輛路徑問題的改進(jìn)拉格朗日松弛算法[J].廣東工業(yè)大學(xué)學(xué)報(bào),2022,39(5):61-67.
[7]向征.基于改進(jìn)拉格朗日松弛算法的電力通信網(wǎng)絡(luò)負(fù)載均衡優(yōu)化策略研究[J].電測與儀表,2023,60(4):85-91.
[8]何昕,韓丹,蔣豪.基于拉格朗日松弛算法的終端區(qū)飛機(jī)排序研究[J].航空計(jì)算技術(shù),2016,46(3):1-3.
[9]軒華.運(yùn)輸能力有限混合流水車間調(diào)度的改進(jìn)拉格朗日松弛算法[J].計(jì)算機(jī)集成制造系統(tǒng),2013,19(7):1633-1639.
[10]米翠花.基于改進(jìn)粒子群算法的網(wǎng)絡(luò)路由選擇和CFA的優(yōu)化研究[D].蘭州:蘭州大學(xué),2007.
[11]湯偉,楊鋮.基于數(shù)據(jù)挖掘技術(shù)的電力調(diào)度系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J].自動(dòng)化與儀器儀表,2019(5):55-58.
[12]黃偉鴻,趙子奇,安琪.基于IIoT的增材制造生產(chǎn)調(diào)度系統(tǒng)設(shè)計(jì)與應(yīng)用研究[J].新型工業(yè)化,2023,13(9):79-87.
[13]譚振鵬,鄧智廣.基于改進(jìn)蟻群算法的電力自動(dòng)調(diào)度模型構(gòu)建計(jì)[J].粘接,2021,48(11):88-91.
[14]許丹莉,朱文,彭超逸,等.基于云邊協(xié)同的虛擬電廠調(diào)度系統(tǒng)設(shè)計(jì)[J].電力信息與通信技術(shù),2023,21(7):44-48.
[15]劉玉.生活垃圾中轉(zhuǎn)站的自動(dòng)化控制系統(tǒng)設(shè)計(jì)[J].自動(dòng)化應(yīng)用,2023,64(14):74-76.
(責(zé)任編輯:平海,蘇幔)