[發(fā)明專利]基于最小費(fèi)用最大流的負(fù)載均衡的多服務(wù)遷移方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202011436474.2
• 申請日: 2020-12-10
• 公開（公告）號: CN112601232B
• 公開（公告）日: 2022-04-26
• 發(fā)明（設(shè)計(jì)）人: 唐歡;王洋;張錦霞;須成忠;葉可江
• 申請（專利權(quán)）人: 中國科學(xué)院深圳先進(jìn)技術(shù)研究院
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W28/16;H04W48/04;H04W48/10;H04W76/10
• 代理公司: 深圳市科進(jìn)知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 44316
• 代理人: 魏毅宏

本發(fā)明涉及信息技術(shù)領(lǐng)域，公開一種基于最小費(fèi)用最大流的負(fù)載均衡的多服務(wù)遷移方法及系統(tǒng)，該方法包括：根據(jù)邊緣服務(wù)器的地理位置以及連接關(guān)系，構(gòu)建網(wǎng)絡(luò)拓?fù)鋱D；計(jì)算每一對邊緣服務(wù)器間的最短路徑距離，并生成最短路徑距離矩陣；建立最小費(fèi)用最大流模型，對模型進(jìn)行求解得到最小費(fèi)用最大流，并將服務(wù)結(jié)點(diǎn)放置在對應(yīng)的邊緣服務(wù)器結(jié)點(diǎn)上；更新每個服務(wù)的訪問信息，調(diào)整邊緣服務(wù)器結(jié)點(diǎn)連至終結(jié)點(diǎn)的邊的權(quán)值，并更新服務(wù)結(jié)點(diǎn)在邊緣服務(wù)器結(jié)點(diǎn)上的位置；實(shí)時(shí)的監(jiān)控和統(tǒng)計(jì)訪問信息并在其變化率超過設(shè)定閾值時(shí)，調(diào)整其對應(yīng)的服務(wù)結(jié)點(diǎn)和邊緣服務(wù)器結(jié)點(diǎn)。本發(fā)明使得虛擬服務(wù)在邊緣結(jié)點(diǎn)上的放置得更均衡且靈活可調(diào)，保證了對用戶的快速響應(yīng)，提升服務(wù)質(zhì)量。

技術(shù)領(lǐng)域

本發(fā)明涉及信息技術(shù)領(lǐng)域，更具體的說，特別涉及一種基于最小費(fèi)用最大流的負(fù)載均衡的多服務(wù)遷移方法及系統(tǒng)。

背景技術(shù)

移動邊緣計(jì)算(MEC)是一種新的計(jì)算范式，它融合了移動計(jì)算和邊緣計(jì)算的優(yōu)點(diǎn)，以提高移動用戶的服務(wù)質(zhì)量(QoS)。特別是有了MEC，計(jì)算資源可以從云中心推至網(wǎng)絡(luò)邊緣，這使得數(shù)據(jù)服務(wù)和其他相關(guān)處理任務(wù)可以在靠近移動用戶的地方運(yùn)行。因此，它不僅減少了服務(wù)延遲，而且使網(wǎng)絡(luò)流量最小化，這兩個好處對于那些有時(shí)間限制的服務(wù)(移動計(jì)算中的典型應(yīng)用程序)來說都是相當(dāng)重要的。

鑒于其訪問效率和低成本的優(yōu)點(diǎn)，MEC正迅速成為下一波研究的焦點(diǎn),尤其是在5G網(wǎng)絡(luò)中更智能和更強(qiáng)大的計(jì)算資源，其可以安裝在無線網(wǎng)絡(luò)的邊緣,使許多時(shí)間敏感服務(wù)的部署更加接近用戶。但考慮到用戶的移動性、對服務(wù)訪問的時(shí)間差異性以及單個邊緣服務(wù)器的有限覆蓋范圍，如果同時(shí)將多種服務(wù)固定在一個邊緣服務(wù)器上，則會出現(xiàn)資源的爭用而導(dǎo)致訪問服務(wù)延遲的增加。因此，如果不考慮這些因素，所提供的服務(wù)可能會顯著增加訪問延遲，更糟的是，會造成大量網(wǎng)絡(luò)流量，造成網(wǎng)絡(luò)擁塞，導(dǎo)致服務(wù)地性能下降，甚至是服務(wù)中斷。

隨著云計(jì)算中虛擬化技術(shù)的快速發(fā)展，越來越多的應(yīng)用服務(wù)以封裝在虛擬機(jī)或者容器中的形式，在MEC中為用戶提供隨需應(yīng)變的移動服務(wù)，能夠有效緩解上一段提出的問題。在許多場景下，是由大量的移動用戶在不同的時(shí)間與地點(diǎn)對服務(wù)進(jìn)行訪問，因此服務(wù)的放置與遷移策略一般不能針對每個用戶進(jìn)行設(shè)計(jì)，而是依賴于移動訪問模式在時(shí)空維度上的動態(tài)變化。與此同時(shí)，服務(wù)的遷移也不是免費(fèi)的，其代價(jià)是大量數(shù)據(jù)傳輸?shù)某杀荆⑶铱赡軐?dǎo)致服務(wù)中斷，從而增加總體服務(wù)延時(shí)。因此，遷移的目標(biāo)通常是降低遷移成本和服務(wù)延遲，同時(shí)有著良好的性能保證。

傳統(tǒng)上，動態(tài)規(guī)劃算法、啟發(fā)式算法以及機(jī)器學(xué)習(xí)方法經(jīng)常被用來解決這個問題。但這些方法都具有較高的時(shí)間復(fù)雜度、空間復(fù)雜度以及離線性質(zhì)。故在網(wǎng)絡(luò)規(guī)模較大時(shí)，策略的求解時(shí)間過長，不能滿足應(yīng)用的低延時(shí)需求。對于用戶訪問密集的時(shí)刻與地點(diǎn)，這些方法也難以應(yīng)對請求的突然增加和異常情況。同時(shí)這些方法也能沒考慮到服務(wù)遷移的通信代價(jià)。

相比之下，一些在線遷移算法可以在精度和響應(yīng)時(shí)間之間進(jìn)行權(quán)衡。有學(xué)者利用了強(qiáng)化學(xué)習(xí)的方法在很大程度上改善了所存在的問題，但其針對的只是單個服務(wù)，而MEC的大多數(shù)場景都會涉及多個服務(wù)。有人利用了馬爾可夫模型，但其針對的是移動云服務(wù)中的動態(tài)服務(wù)問題，其能夠得出最佳的遷移策略，但是沒有考慮均衡放置的問題。有學(xué)者將同樣的問題表述為一對一契約博弈模型，并開發(fā)了基于學(xué)習(xí)的價(jià)格控制機(jī)制，以有效處理MEC的資源。通過運(yùn)用博弈方法和學(xué)習(xí)過程，該方法能夠通過與未知系統(tǒng)環(huán)境的持續(xù)交互來獲取MEC系統(tǒng)的動態(tài)信息。非常可惜的是，它總是需要一段時(shí)間來學(xué)習(xí)，在其收斂之前，決策的質(zhì)量無法得到保證，也無法實(shí)現(xiàn)服務(wù)的低延時(shí)。

現(xiàn)有工作在遷移策略上已經(jīng)取得了不錯的效果，但其往往沒有考慮邊緣服務(wù)器資源有限而發(fā)生多個服務(wù)爭用資源的問題，并且隨著人們需求的日益增長，網(wǎng)絡(luò)規(guī)模也隨之增長，訪問模式也更為復(fù)雜，之前的策略難以在大規(guī)模的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下做出最優(yōu)決策。同時(shí)，之前的策略或是針對單服務(wù)的遷移，或是缺乏一定的動態(tài)性，亦或是求解時(shí)間過長。最主要的缺點(diǎn)是不能同時(shí)兼顧低服務(wù)延遲以及各邊緣結(jié)點(diǎn)的負(fù)載均衡。

發(fā)明內(nèi)容