林 峰,段建嵐,李傳偉,蔣建春

(重慶郵電大學(xué) a.電子信息與網(wǎng)絡(luò)工程研究院; b.通信與信息工程學(xué)院; c.自動化學(xué)院,重慶 400065)

0 概述

隨著車聯(lián)網(wǎng)技術(shù)的快速發(fā)展,蜂窩車聯(lián)網(wǎng)(Cellular Vehicle to Everything,C-V2X)與移動邊緣計(jì)算(Mobile Edge Computing,MEC)技術(shù)不斷融合,C-V2X可大幅度降低未來自動駕駛和車聯(lián)網(wǎng)部署成本,而MEC將計(jì)算存儲與業(yè)務(wù)服務(wù)能力向網(wǎng)絡(luò)邊緣遷移[1],從而實(shí)現(xiàn)“人-車-路-云”協(xié)同交互。然而,在道路上由于不同區(qū)域的車輛分布不均衡,因此導(dǎo)致不同區(qū)域MEC服務(wù)器的數(shù)據(jù)訪問量各不相同。負(fù)載均衡的目的是將大量并發(fā)任務(wù)合理調(diào)度到各個服務(wù)器節(jié)點(diǎn)上進(jìn)行計(jì)算,從而避免服務(wù)器出現(xiàn)負(fù)載傾斜問題,進(jìn)而提高集群性能。在現(xiàn)有的負(fù)載均衡算法研究中,根據(jù)調(diào)度策略的不同,主要可以分為靜態(tài)負(fù)載均衡算法和動態(tài)負(fù)載均衡算法兩類[2]。靜態(tài)負(fù)載均衡算法是依據(jù)既定的策略來調(diào)度任務(wù),而不考慮當(dāng)前服務(wù)器節(jié)點(diǎn)的負(fù)載狀況,如輪詢算法、加權(quán)輪詢算法等。動態(tài)負(fù)載均衡算法是以當(dāng)前服務(wù)器節(jié)點(diǎn)負(fù)載狀況為參考,合理調(diào)度任務(wù),如最小連接法、加權(quán)最小連接法等[3]。在實(shí)際應(yīng)用中,相較于靜態(tài)負(fù)載均衡算法,動態(tài)負(fù)載均衡算法通常可以更好地反映服務(wù)器狀態(tài),因此其在任務(wù)調(diào)度方面具有更好的效果。為此,本文提出一種動態(tài)負(fù)載均衡算法,其充分考慮各邊緣服務(wù)器自身負(fù)載狀態(tài),動態(tài)更新負(fù)載指標(biāo)權(quán)重,并根據(jù)服務(wù)器性能合理分配任務(wù)。

1 相關(guān)工作

在云計(jì)算系統(tǒng)中,文獻(xiàn)[4]提出一種基于最小流量的自適應(yīng)調(diào)度算法,通過網(wǎng)絡(luò)流量狀態(tài)參數(shù)判定服務(wù)器負(fù)載狀態(tài)并設(shè)置服務(wù)器管理閾值,從而將新請求調(diào)度到低負(fù)載的服務(wù)器節(jié)點(diǎn)上。該算法雖然可在一定程度上減輕服務(wù)器節(jié)點(diǎn)負(fù)載,但由于其只考慮了網(wǎng)絡(luò)流量,未考慮服務(wù)器CPU利用率、磁盤讀寫速率等其他性能指標(biāo),因此不能全面反映服務(wù)器節(jié)點(diǎn)的實(shí)際負(fù)載狀態(tài)。文獻(xiàn)[5]將鯨魚算法與人工蜂群算法相結(jié)合,先將鯨魚個體對應(yīng)資源負(fù)載調(diào)度方案,利用鯨魚算法對其進(jìn)行種群初始化,并引入淘汰機(jī)制和競爭機(jī)制提高算法局部搜索能力,再將鯨魚個體模擬成蜂群個體,利用人工蜂群算法對其進(jìn)行優(yōu)化提高算法全局搜索能力。文獻(xiàn)[6]研究發(fā)現(xiàn)蟻群算法在任務(wù)調(diào)度方面具有收斂速度慢及資源調(diào)度不均衡等問題,并針對這些問題進(jìn)行改進(jìn),通過計(jì)算負(fù)載指標(biāo)權(quán)重加快算法收斂速度,提高虛擬機(jī)的負(fù)載均衡度。

在Web服務(wù)器集群系統(tǒng)中,文獻(xiàn)[7]提出一種改進(jìn)型輪詢負(fù)載均衡策略,利用系統(tǒng)狀態(tài)信息優(yōu)化調(diào)度結(jié)果,根據(jù)循環(huán)列表及上一次選定服務(wù)器的指針進(jìn)行調(diào)度。文獻(xiàn)[8]研究基于神經(jīng)網(wǎng)絡(luò)反饋機(jī)制的負(fù)載均衡算法,利用神經(jīng)網(wǎng)絡(luò)的反饋機(jī)制獲取負(fù)載狀態(tài),并將其作為加權(quán)最小連接數(shù)算法的輸入得到最佳可分配負(fù)載權(quán)值,從而實(shí)現(xiàn)任務(wù)的合理分配。文獻(xiàn)[9]研究一種基于殘差的模糊自適應(yīng)算法,具有較高的算法準(zhǔn)確性。文獻(xiàn)[10]在螢火蟲算法的基礎(chǔ)上引入混沌算法,解決了螢火蟲算法收斂速度慢、易陷入局部最優(yōu)的問題。

在軟件自定義網(wǎng)絡(luò)中,文獻(xiàn)[11]研究基于鏈路實(shí)時(shí)狀態(tài)的負(fù)載均衡策略,通過鏈路監(jiān)測數(shù)據(jù)來選擇低負(fù)載鏈路,從而解決鏈路擁塞問題。文獻(xiàn)[12]針對節(jié)點(diǎn)負(fù)載信息獲取困難、流量導(dǎo)向方式復(fù)雜等問題,提出一種負(fù)載均衡機(jī)制,利用SNMP協(xié)議和OpenFlow協(xié)議監(jiān)測服務(wù)器實(shí)時(shí)狀態(tài),通過加權(quán)計(jì)算選出最優(yōu)服務(wù)器,并采用最優(yōu)轉(zhuǎn)發(fā)路徑算法進(jìn)行流量調(diào)度,從而提高集群效率。文獻(xiàn)[13]基于遺傳算法和蟻群算法提出融合算法,提高了軟件自定義網(wǎng)絡(luò)的綜合性能。

在邊緣計(jì)算網(wǎng)絡(luò)中,文獻(xiàn)[14]研究了無共享、隨機(jī)共享和最小負(fù)載共享3種負(fù)載均衡方案,通過比較發(fā)現(xiàn)最小負(fù)載共享方案最適用于服務(wù)器之間的協(xié)作,可實(shí)現(xiàn)集群的負(fù)載均衡。文獻(xiàn)[15]提出一種數(shù)據(jù)中心協(xié)作的資源共享方案,規(guī)定每個數(shù)據(jù)中心都使用緩沖區(qū)存儲服務(wù)請求以供本地執(zhí)行,當(dāng)緩沖區(qū)已滿時(shí)將請求遷移至相鄰數(shù)據(jù)中心,如果該數(shù)據(jù)中心的當(dāng)前隊(duì)列長度低于給定閾值,則接受該請求。通過該方式可以有效緩解數(shù)據(jù)中心的阻塞狀態(tài)及減少任務(wù)執(zhí)行時(shí)延。文獻(xiàn)[16]針對邊緣計(jì)算復(fù)雜多變的環(huán)境,提出一種基于深度強(qiáng)化學(xué)習(xí)的智能資源分配方案,可自適應(yīng)分配計(jì)算資源,減少平均服務(wù)時(shí)間。文獻(xiàn)[17]提出一種邊緣計(jì)算任務(wù)調(diào)度模型,將等待時(shí)間最小化問題轉(zhuǎn)換為整體規(guī)劃問題,并通過動態(tài)規(guī)劃實(shí)現(xiàn)最優(yōu)調(diào)度。文獻(xiàn)[18]提出一種改進(jìn)型混沌蝙蝠群算法,在蝙蝠算法的基礎(chǔ)上引入混沌因素和二階振蕩機(jī)制來加快動態(tài)參數(shù)更新,從而提升算法收斂速度,并通過深度學(xué)習(xí)快速預(yù)測調(diào)度結(jié)果。

2 C-V2X邊緣服務(wù)器負(fù)載均衡算法

對于C-V2X邊緣服務(wù)器負(fù)載均衡的研究,多數(shù)算法著重于探究任務(wù)分配策略,而忽視了服務(wù)器的任務(wù)分配時(shí)間以及如何準(zhǔn)確判斷服務(wù)器運(yùn)行狀態(tài)等問題。這些問題對后續(xù)任務(wù)分配具有較大影響,容易導(dǎo)致集群負(fù)載均衡度及資源利用率低等問題,而車聯(lián)網(wǎng)環(huán)境中存在邊緣服務(wù)器負(fù)載差異大、負(fù)載狀態(tài)隨時(shí)間變化、集群計(jì)算資源分配不均衡等問題,因此本文提出一種基于動態(tài)負(fù)載指標(biāo)權(quán)重的負(fù)載均衡算法,其充分考慮服務(wù)器當(dāng)前負(fù)載狀態(tài),并動態(tài)調(diào)整負(fù)載指標(biāo)權(quán)重,從而提升集群負(fù)載均衡度。

2.1 算法應(yīng)用場景

由于從現(xiàn)有基站和終端上無法直接獲得C-V2X安全應(yīng)用所需的實(shí)時(shí)計(jì)算、存儲、控制、加速等資源且不具備高效計(jì)算能力,而從云平臺上獲取這些資源并進(jìn)行計(jì)算所需要的時(shí)延會急劇增加,無法達(dá)到V2X應(yīng)用的時(shí)延和帶寬要求,因此將V2X應(yīng)用在靠近車輛的位置部署,使得V2X應(yīng)用中產(chǎn)生的巨大流量和網(wǎng)絡(luò)負(fù)擔(dān)可在本地卸載,從而減少信息傳輸時(shí)延及網(wǎng)絡(luò)帶寬消耗。

圖1顯示了C-V2X與MEC融合應(yīng)用場景,考慮道路在自由流狀態(tài)下具有不間斷交通,沿路設(shè)有演進(jìn)型基站(eNodeB),每個eNodeB為其傳輸范圍內(nèi)的車輛提供無線接入服務(wù),且每輛車在其范圍內(nèi)只能與一個eNodeB通信,eNodeB之間通過X2接口通信。由于每個eNodeB的無線電功率不同以及無線環(huán)境多樣,因此這些eNodeB的無線覆蓋區(qū)域可能不同[19],并且每個eNodeB都配備一個資源有限的MEC服務(wù)器為卸載的任務(wù)提供計(jì)算服務(wù)[20],每個MEC服務(wù)器都可與區(qū)域內(nèi)的調(diào)度中心通信,MEC服務(wù)器id與其對應(yīng)的eNodeB id相匹配。調(diào)度中心負(fù)責(zé)周期性記錄各個服務(wù)器負(fù)載狀態(tài),并為發(fā)起任務(wù)轉(zhuǎn)移請求的服務(wù)器制定任務(wù)轉(zhuǎn)移策略。

圖1 C-V2X與MEC融合應(yīng)用場景Fig.1 Integration application scenario of C-V2X and MEC

2.2 相關(guān)參數(shù)定義

MEC服務(wù)器負(fù)載均衡的首要問題是評估當(dāng)前服務(wù)器狀態(tài),而評估指標(biāo)的不同會對負(fù)載狀態(tài)的判斷結(jié)果產(chǎn)生較大影響。本文算法充分考慮MEC服務(wù)器運(yùn)行狀態(tài),綜合處理器利用率、磁盤讀寫速率、內(nèi)存使用率、帶寬占用率4個方面對服務(wù)器狀態(tài)進(jìn)行評估,分別反映了服務(wù)器CPU的繁忙程度、數(shù)據(jù)操作的吞吐量、系統(tǒng)運(yùn)行狀態(tài)及接收數(shù)據(jù)量。

服務(wù)器i的負(fù)載率為:

(1)

αcpu+αi/o+αmem+αband=1

(2)

(3)

(4)

(5)

(6)

2.3 負(fù)載指標(biāo)權(quán)值計(jì)算

傳統(tǒng)負(fù)載均衡算法通常將負(fù)載指標(biāo)權(quán)值設(shè)為定值,然而由于各個服務(wù)器性能存在差異且運(yùn)行中各個指標(biāo)的依賴情況不同,因此導(dǎo)致傳統(tǒng)負(fù)載均衡算法無法準(zhǔn)確反映服務(wù)器節(jié)點(diǎn)的負(fù)載狀態(tài)[21]。例如,服務(wù)器的CPU利用率已接近峰值,而其他指標(biāo)均處于較低水平,該情況在傳統(tǒng)負(fù)載均衡算法中并未達(dá)到高負(fù)載的狀態(tài),但實(shí)際情況中卻已處于高負(fù)載的狀態(tài),此時(shí)若繼續(xù)為其分配任務(wù),則會嚴(yán)重影響服務(wù)器運(yùn)行性能。又由于融合場景下車輛的移動性會導(dǎo)致邊緣服務(wù)器負(fù)載狀態(tài)隨時(shí)間改變,因此本文提出一種動態(tài)更新負(fù)載指標(biāo)權(quán)值的方法對其進(jìn)行優(yōu)化,從而更加準(zhǔn)確地判斷服務(wù)器實(shí)際負(fù)載狀態(tài)。

由于在一個eNodeB覆蓋范圍內(nèi),車輛數(shù)量不會出現(xiàn)躍變情況,即短時(shí)間內(nèi)車輛數(shù)量突然降低或升高,因此與eNodeB匹配的MEC服務(wù)器負(fù)載情況呈緩慢變化趨勢,同時(shí)考慮到較高的負(fù)載指標(biāo)應(yīng)獲取較高的權(quán)值,通過對比負(fù)載指標(biāo)均值,判斷負(fù)載指標(biāo)權(quán)重是否需要提高或降低。當(dāng)前負(fù)載指標(biāo)均值的計(jì)算公式如下:

(7)

(8)

(9)

本文考慮處理器利用率、磁盤讀寫速率、內(nèi)存使用率、帶寬占用率4個負(fù)載指標(biāo),得到:

(10)

結(jié)合式(2)、式(7)～式(10)得到負(fù)載指標(biāo)的新權(quán)值為:

(11)

2.4 服務(wù)器負(fù)載判斷

(12)

2.5 任務(wù)轉(zhuǎn)移

當(dāng)服務(wù)器處于高負(fù)載狀態(tài)時(shí),服務(wù)器將發(fā)起任務(wù)轉(zhuǎn)移請求,調(diào)度中心接收請求后會將該服務(wù)器排隊(duì)中的任務(wù)轉(zhuǎn)移至低負(fù)載狀態(tài)的服務(wù)器上,從而提升整個集群的負(fù)載均衡度。

(13)

設(shè)σF為集群負(fù)載率標(biāo)準(zhǔn)差,負(fù)載率標(biāo)準(zhǔn)差體現(xiàn)了集群負(fù)載率的變化情況,負(fù)載率標(biāo)準(zhǔn)差越低,負(fù)載率變化越小,反之越大,其計(jì)算公式為:

(14)

由式(14)可知,若要提升集群整體負(fù)載均衡度,則需降低σF值。因此,合理遷移高負(fù)載狀態(tài)服務(wù)器任務(wù)隊(duì)列中的任務(wù)將成為關(guān)鍵。

假設(shè)待分配的任務(wù)數(shù)為n,集群的服務(wù)器數(shù)為m,結(jié)合服務(wù)器當(dāng)前負(fù)載狀態(tài),考慮到負(fù)載率越低的服務(wù)器具有越高的分配概率,且可接收遷移的任務(wù)量也越多。設(shè)Pij表示任務(wù)i分配到服務(wù)器j上的概率,計(jì)算公式為:

(15)

其中,set表示服務(wù)器集群中滿足Gsi≠2時(shí)的服務(wù)器集合。

根據(jù)以上計(jì)算可知,當(dāng)有任務(wù)需要進(jìn)行遷移時(shí),調(diào)度中心都會對比各個服務(wù)器負(fù)載狀態(tài)并計(jì)算遷移概率,然后用輪盤賭法決定任務(wù)遷移到哪個服務(wù)器上,概率值即賭盤的扇區(qū)面積,概率值越大,扇區(qū)面積越大,被選中的幾率越大。因此,通過合理分配遷移任務(wù)可提升整個服務(wù)器集群的負(fù)載均衡度。

2.6 算法流程

本文算法主要分為:1)本地服務(wù)器計(jì)算各負(fù)載指標(biāo)權(quán)值、服務(wù)器性能和服務(wù)器負(fù)載率,并將結(jié)果周期性上傳至調(diào)度中心;2)調(diào)度中心收集各服務(wù)器信息并存表,當(dāng)服務(wù)器發(fā)起任務(wù)遷移請求時(shí),調(diào)度中心計(jì)算任務(wù)遷移概率并用輪盤賭法決定任務(wù)遷移到哪個服務(wù)器上。若無服務(wù)器可接收遷移任務(wù),即集群中的服務(wù)器都處于高負(fù)載狀態(tài),則拋棄任務(wù)。

動態(tài)負(fù)載均衡算法流程如圖2所示,具體步驟如下:

步驟1對各個MEC服務(wù)器進(jìn)行參數(shù)初始化,包括服務(wù)器性能參數(shù)、指標(biāo)權(quán)值設(shè)置等。

步驟2各個MEC服務(wù)器按照一定時(shí)間間隔T,動態(tài)更新指標(biāo)權(quán)值、計(jì)算服務(wù)器性能和負(fù)載率以及判斷服務(wù)負(fù)載狀態(tài)并將相關(guān)信息上傳至調(diào)度中心。

步驟3調(diào)度中心接收各個MEC服務(wù)器上傳的信息,并對這些信息進(jìn)行存表、更新等操作。

步驟4若調(diào)度中心接收到服務(wù)器的任務(wù)遷移請求,則對服務(wù)器進(jìn)行分類,選出可接收遷移任務(wù)的服務(wù)器,并計(jì)算各個服務(wù)器的轉(zhuǎn)移概率。

步驟5調(diào)度中心根據(jù)轉(zhuǎn)移概率設(shè)計(jì)任務(wù)遷移方案,eNodeB接收調(diào)度中心調(diào)度安排,將任務(wù)通過X2接口傳輸至eNodeB。當(dāng)任務(wù)計(jì)算完成后,將計(jì)算結(jié)果進(jìn)行回傳。

步驟6重復(fù)步驟4和步驟5,等待下一個周期,從步驟2開始執(zhí)行并進(jìn)行周期性循環(huán)。

圖2 動態(tài)負(fù)載均衡算法流程Fig.2 Procedure of dynamic load balancing algorithm

3 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證本文算法性能,選擇傳統(tǒng)隨機(jī)輪詢算法和文獻(xiàn)[4]最小流量均衡算法做對比實(shí)驗(yàn)。實(shí)驗(yàn)環(huán)境使用Cloudsim仿真軟件進(jìn)行模擬,通過Datacenter類、Vm類和Cloudlet類設(shè)置數(shù)據(jù)中心、模擬服務(wù)器和產(chǎn)生計(jì)算任務(wù),利用Origin9對仿真結(jié)果進(jìn)行圖形化處理。

3.1 參數(shù)設(shè)置

通過Cloudsim仿真軟件進(jìn)行模擬,設(shè)置虛擬機(jī)參數(shù)和任務(wù)參數(shù)如表1、表2所示。

表1 虛擬機(jī)參數(shù)設(shè)置Table 1 Virtual machine parameter setting

表2 任務(wù)參數(shù)設(shè)置Table 2 Task parameter setting

3.2 評價(jià)指標(biāo)

在實(shí)驗(yàn)過程中,為充分模擬現(xiàn)實(shí)環(huán)境,本文將從以下兩方面分析算法性能:

1)將負(fù)載率均值和負(fù)載率標(biāo)準(zhǔn)差作為參考指標(biāo),其中:負(fù)載率均值體現(xiàn)了整個集群的負(fù)載狀態(tài),其值越低,說明集群整體負(fù)載越低、負(fù)載狀態(tài)越好;負(fù)載率標(biāo)準(zhǔn)差體現(xiàn)了整個集群的負(fù)載穩(wěn)定性,其值越低,說明集群負(fù)載越均衡、穩(wěn)定性越強(qiáng)。

2)將任務(wù)完成時(shí)間作為算法性能指標(biāo),任務(wù)完成時(shí)間越短,算法性能越好。

3.3 結(jié)果分析

本文在同等條件下,對隨機(jī)輪詢算法、最小流量均衡算法以及本文算法進(jìn)行仿真驗(yàn)證對比,仿真結(jié)果如圖3～圖5所示。由圖3可以看出,本文動態(tài)負(fù)載均衡算法的負(fù)載率均值最低,其次是最小流量均衡算法,負(fù)載率均值最大為隨機(jī)輪詢算法。本文算法和最小流量均衡算法均在任務(wù)數(shù)達(dá)到300后,觸發(fā)大規(guī)模任務(wù)調(diào)度,從而使負(fù)載率均值上升速度變緩,但本文算法負(fù)載率均值上升速度約為最小流量均衡算法的一半,表明其對任務(wù)的分配更加合理。由圖4可以看出,本文算法的負(fù)載率標(biāo)準(zhǔn)差比另外兩種算法都低,且在任務(wù)數(shù)達(dá)到250后基本呈穩(wěn)定狀態(tài),表明其可以更好地提升集群負(fù)載均衡度。由圖5可以看出,在任務(wù)數(shù)較少時(shí),3種算法的任務(wù)完成時(shí)間差距不大,集群負(fù)載基本都處于低負(fù)載狀態(tài)。隨著任務(wù)數(shù)的增加,3種算法在任務(wù)完成時(shí)間上的差距越來越大,表明其對集群負(fù)載的影響各不相同,且本文算法的任務(wù)完成時(shí)間一直處于最少狀態(tài),相較另外兩種算法能更好地縮短用戶完成任務(wù)的時(shí)間,從而提高用戶體驗(yàn)。

圖3 負(fù)載率均值對比Fig.3 Comparison of mean value of load ratio

圖4 負(fù)載率標(biāo)準(zhǔn)差對比Fig.4 Comparison of standard deviation of load ratio

圖5 任務(wù)完成時(shí)間對比Fig.5 Comparison of task completion time

通過上述實(shí)驗(yàn)對比可知,本文算法相較隨機(jī)輪詢算法與最小流量均衡算法能夠更好地適應(yīng)C-V2X與MEC融合應(yīng)用場景,提升邊緣服務(wù)器集群負(fù)載均衡度,減少任務(wù)完成時(shí)間。其主要原因?yàn)?相較隨機(jī)輪詢算法與最小流量均衡算法,本文算法考慮了處理器利用率、磁盤讀寫速率、內(nèi)存使用率、帶寬占用率這些對服務(wù)器負(fù)載有較大影響的因素,通過對所有因素進(jìn)行加權(quán)可以更準(zhǔn)確地反映出當(dāng)前服務(wù)器的負(fù)載狀態(tài)。此外,本文算法同時(shí)考慮融合環(huán)境下任務(wù)數(shù)量與類型會隨時(shí)間變化,導(dǎo)致邊緣服務(wù)器負(fù)載對不同影響因素的依賴程度隨時(shí)間而變化,因此本文通過邊緣服務(wù)器負(fù)載狀態(tài)合理判斷邊緣服務(wù)器的任務(wù)轉(zhuǎn)移時(shí)間,從而提升集群負(fù)載均衡度。

4 結(jié)束語

在車聯(lián)網(wǎng)環(huán)境中為減少端到端通信時(shí)延并提供更加可靠的服務(wù),引入了邊緣計(jì)算技術(shù),然而在C-V2X與MEC融合應(yīng)用場景中車輛分布不均容易導(dǎo)致邊緣服務(wù)器負(fù)載不均、資源利用率低等問題。為此,本文提出一種動態(tài)負(fù)載均衡算法,通過充分考慮邊緣服務(wù)器自身運(yùn)行狀態(tài),動態(tài)調(diào)整指標(biāo)權(quán)重并合理分配計(jì)算任務(wù),從而提升集群負(fù)載均衡度。實(shí)驗(yàn)結(jié)果表明,與傳統(tǒng)隨機(jī)輪詢算法和最小流量均衡算法相比,本文算法可以更好地分配計(jì)算資源,提高資源利用率,縮短任務(wù)完成時(shí)間。后續(xù)將對集群調(diào)度中心的任務(wù)分配機(jī)制進(jìn)行研究,進(jìn)一步減少任務(wù)分配時(shí)間并提升用戶體驗(yàn)。