C-V2X邊緣服務器的動態負載均衡算法研究

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

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

0 概述

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

1 相關工作

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

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

在軟件自定義網絡中,文獻[11]研究基于鏈路實時狀態的負載均衡策略,通過鏈路監測數據來選擇低負載鏈路,從而解決鏈路擁塞問題。文獻[12]針對節點負載信息獲取困難、流量導向方式復雜等問題,提出一種負載均衡機制,利用SNMP協議和OpenFlow協議監測服務器實時狀態,通過加權計算選出最優服務器,并采用最優轉發路徑算法進行流量調度,從而提高集群效率。文獻[13]基于遺傳算法和蟻群算法提出融合算法,提高了軟件自定義網絡的綜合性能。

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

2 C-V2X邊緣服務器負載均衡算法

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

2.1 算法應用場景

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

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

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

2.2 相關參數定義

MEC服務器負載均衡的首要問題是評估當前服務器狀態,而評估指標的不同會對負載狀態的判斷結果產生較大影響。本文算法充分考慮MEC服務器運行狀態,綜合處理器利用率、磁盤讀寫速率、內存使用率、帶寬占用率4個方面對服務器狀態進行評估,分別反映了服務器CPU的繁忙程度、數據操作的吞吐量、系統運行狀態及接收數據量。

服務器i的負載率為:

(1)

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

(2)

(3)

(4)

(5)

(6)

2.3 負載指標權值計算

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

由于在一個eNodeB覆蓋范圍內,車輛數量不會出現躍變情況,即短時間內車輛數量突然降低或升高,因此與eNodeB匹配的MEC服務器負載情況呈緩慢變化趨勢,同時考慮到較高的負載指標應獲取較高的權值,通過對比負載指標均值,判斷負載指標權重是否需要提高或降低。當前負載指標均值的計算公式如下:

(7)

(8)

(9)

本文考慮處理器利用率、磁盤讀寫速率、內存使用率、帶寬占用率4個負載指標,得到:

(10)

結合式(2)、式(7)～式(10)得到負載指標的新權值為:

(11)

2.4 服務器負載判斷

(12)

2.5 任務轉移

當服務器處于高負載狀態時,服務器將發起任務轉移請求,調度中心接收請求后會將該服務器排隊中的任務轉移至低負載狀態的服務器上,從而提升整個集群的負載均衡度。

(13)

設σF為集群負載率標準差,負載率標準差體現了集群負載率的變化情況,負載率標準差越低,負載率變化越小,反之越大,其計算公式為:

(14)

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

假設待分配的任務數為n,集群的服務器數為m,結合服務器當前負載狀態,考慮到負載率越低的服務器具有越高的分配概率,且可接收遷移的任務量也越多。設Pij表示任務i分配到服務器j上的概率,計算公式為:

(15)

其中,set表示服務器集群中滿足Gsi≠2時的服務器集合。

根據以上計算可知,當有任務需要進行遷移時,調度中心都會對比各個服務器負載狀態并計算遷移概率,然后用輪盤賭法決定任務遷移到哪個服務器上,概率值即賭盤的扇區面積,概率值越大,扇區面積越大,被選中的幾率越大。因此,通過合理分配遷移任務可提升整個服務器集群的負載均衡度。

2.6 算法流程

本文算法主要分為:1)本地服務器計算各負載指標權值、服務器性能和服務器負載率,并將結果周期性上傳至調度中心;2)調度中心收集各服務器信息并存表,當服務器發起任務遷移請求時,調度中心計算任務遷移概率并用輪盤賭法決定任務遷移到哪個服務器上。若無服務器可接收遷移任務,即集群中的服務器都處于高負載狀態,則拋棄任務。

動態負載均衡算法流程如圖2所示,具體步驟如下:

步驟1對各個MEC服務器進行參數初始化,包括服務器性能參數、指標權值設置等。

步驟2各個MEC服務器按照一定時間間隔T,動態更新指標權值、計算服務器性能和負載率以及判斷服務負載狀態并將相關信息上傳至調度中心。

步驟3調度中心接收各個MEC服務器上傳的信息,并對這些信息進行存表、更新等操作。

步驟4若調度中心接收到服務器的任務遷移請求,則對服務器進行分類,選出可接收遷移任務的服務器,并計算各個服務器的轉移概率。

步驟5調度中心根據轉移概率設計任務遷移方案,eNodeB接收調度中心調度安排,將任務通過X2接口傳輸至eNodeB。當任務計算完成后,將計算結果進行回傳。

步驟6重復步驟4和步驟5,等待下一個周期,從步驟2開始執行并進行周期性循環。

圖2 動態負載均衡算法流程Fig.2 Procedure of dynamic load balancing algorithm

3 實驗驗證

為驗證本文算法性能,選擇傳統隨機輪詢算法和文獻[4]最小流量均衡算法做對比實驗。實驗環境使用Cloudsim仿真軟件進行模擬,通過Datacenter類、Vm類和Cloudlet類設置數據中心、模擬服務器和產生計算任務,利用Origin9對仿真結果進行圖形化處理。

3.1 參數設置

通過Cloudsim仿真軟件進行模擬,設置虛擬機參數和任務參數如表1、表2所示。

表1 虛擬機參數設置Table 1 Virtual machine parameter setting

表2 任務參數設置Table 2 Task parameter setting

3.2 評價指標

在實驗過程中,為充分模擬現實環境,本文將從以下兩方面分析算法性能:

1)將負載率均值和負載率標準差作為參考指標,其中:負載率均值體現了整個集群的負載狀態,其值越低,說明集群整體負載越低、負載狀態越好;負載率標準差體現了整個集群的負載穩定性,其值越低,說明集群負載越均衡、穩定性越強。

2)將任務完成時間作為算法性能指標,任務完成時間越短,算法性能越好。

3.3 結果分析

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

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

圖4 負載率標準差對比Fig.4 Comparison of standard deviation of load ratio

圖5 任務完成時間對比Fig.5 Comparison of task completion time

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

4 結束語

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