5G通信中基于二分圖匹配的鏈路均衡負載方法研究

龍艦涵 李 平

1(瀘州職業技術學院電子工程學院 四川 瀘州 646000)2(西南石油大學計算機科學學院 四川 成都 610500)

0 引 言

當前移動通信用戶的總體規模和通信流量都在持續高速增長，4G-LTE通信技術由于受到整體框架體系的限制，在信道資源利用率、數據信息傳輸效率及頻譜帶寬使用等方面，都無法再為用戶提供更好的服務體驗，人類已經開始進入了5G通信時代。5G通信融合了新一代信號編碼調制體系[1]、大規模MIMO[2]、高頻段數據傳輸[3]、非正交多址接入[4]等先進的通信技術和理念，具有更大的網絡數據吞吐量、更低的通信時延和更高的數據傳輸效率。5G通信支持超密集的異構網絡框架[5]和無線自組織網絡[6]，可以進一步提高對頻譜的利用效率，降低通信網絡的維護成本，還將極大地改善通信網絡的健壯性，提升用戶真實的使用體驗。然而5G新技術的投入使用也會帶來新的問題和挑戰，由于采用了毫米波級別的通信技術[7]，需要實現跨頻譜的信號傳輸，這對通信網絡的均衡負載能力提出了更高的要求。此外，5G通信的用戶基數和通信流量都遠非4G網絡可比，網絡鏈路的密集程度更大[8]，同時對于數據傳輸的效率要求也更高，將會給網絡整體容納能力和通信鏈路的負載能力帶來巨大壓力。

目前，5G網絡已經在我國部分一、二線城市試運行，在5G網絡運行中也不同程度地出現鏈路負載不均衡的情況。網絡通信中為了使網絡資源得到更為充分的運用，往往會選擇增加硬件資源的投入，但會導致網絡成本增加及網絡的可擴展性降低。對于網絡均衡負載而言也可以采用，更優的方案是利用網絡均衡算法增強資源調度的靈活性。5G通信中由于毫米波通信固有的缺陷，會導致現有通信網絡分布不均勻、數據的動態傳輸出現大小流問題，影響網絡通信的均衡負載。針對現有的這些通信鏈路負載不均衡和局部擁塞問題，所選擇的解決方法大都是延續和優化原有4G-LTE網絡均衡負載的解決方法，主要包括PSO均衡算法[9]、IsoRank算法[10]等。PSO均衡算法從底層的物理資源結構研究為出發點，考慮到底層節點資源的消耗與分配，以此來節省節點能耗增強網絡性能。但在利用PSO算法尋找最優通信鏈路時，必須基于當前通信的實際情況，確定出不同鏈路之間的通信信號閾值范圍[11]，如果閾值范圍設定過大，直接會導致鏈路任務分配結果出現偏差，如果設定閾值范圍過小，則會影響算法的整體效率；而IsoRank算法基于一種貪心的啟發模式[12]，通過網絡資源路徑兩兩比對的方式實現全局范圍內鏈路尋優，但該種算法的計算過程過于復雜，運算量極大，在實際應用中的效果要遠差于理論研究。針對現有網絡均衡負載方法在實用性上的不足，本文基于經典的匈牙利算法[13-14]，提出一種解決5G網絡均衡負載的二分圖匹配方案，以更合理地做好基站資源、小區資源和用戶資源的合理分配，解決密集網絡通信中鏈路擁塞和不均衡問題。

1 5G網絡鏈路均衡負載管理與預測模型構建

作為一種重要的無線網絡資源管理模式，鏈路均衡負載性能在5G網絡時代具有更重要的意義。5G網絡的密集程度和復雜程度要遠遠高于前幾代通信網絡，包括蜂窩網絡、小區網絡、局域網絡以太網在內，共同形成了一種十分復雜的多協議異構網絡，而且網絡中通信鏈路眾多、結構復雜、相互重疊，給毫米波大規模MIMO通信帶來了極大的挑戰。要確保5G通信網絡的下行通信效率達到一種最優狀態，必須要保證數據信息在無線蜂窩網絡、局域網絡、小區網絡及各鏈路中保持一種相對負載均衡的狀態[15-16]。由于采用了大規模MIMO的通信方式，5G網絡的數據承載能力能夠滿足用戶的高速通信需求，但如何在短時間內滿足大量網絡用戶集中的數據上傳與下載要求，將成為制約5G通信產業發展的主要難題之一。通信鏈路擴容需要大量的軟硬件投入，在現階段5G建設的初期無法實現，而如何利用現有網絡資源有效實現網絡均衡負載和調度方法，提高對資源的利用率，減少網絡信道擁塞，將具有更重要的現實意義。在5G異構網絡中基于經典匈牙利算法的網絡均衡負載主要思想，是將全部網絡節點按照最大負載能力設定一個閾值范圍，并對這些網絡節點進行實時監控，一旦識別出個別節點的負載能力已經超過了最大閾值范圍，再按照重置分配方案重新分配網絡資源和數據傳輸任務，以減輕超負荷通信網絡節點的負載壓力。

考慮到5G通信中密集蜂窩異構無線網絡的通信場景，全部的單播通信行為[17]均由臨近的基站負責載波資源的發送與調配，在單基站能夠覆蓋的網絡范圍內假定有m個5G通信用戶和n個與之相對于的D2D用戶(終端直通用戶)[18]，那么此時在該小區內蜂窩網絡通信用戶使用基于正交的載波鏈路進行通信，在這種一對一的載波模式下，網絡鏈路的信道增益情況用zk,j表示為：

(1)

式中：η表示通信中的路徑損耗；α表示通信鏈路的信道衰落系數；d表示臨近基站與5G用戶之間的最短距離；i、j分別表示D2D模式中的第i個通信網絡用戶和第j通信網絡用戶；k為在第k個小區內收到的干擾信道增益符號。5G通信網絡中鏈路載波上下行管理模型如圖1所示。

圖1 上下行網絡通信資源載波分配管理模型

正常信道增益與干擾信道增益的定義結果如表1所示。

表1 5G通信中信道增益結果符號定義與表示

信干噪比是指系統接收到的期望信號強度與干擾信號強度的比值，在特定的閾值條件下信干噪比的值越大，鏈路均衡負載的效果越好。用戶i在小區k內收到通信鏈路傳輸過來的信干噪比表示為：

(2)

F(κi,κj)=ξ(κi,κj)-c(κi,κj)

(3)

式中：ξ(κi,κj)表示用戶i在小區內的收益增量總值；c(κi)表示為通信成本。這時在k小區的5G網絡均衡負載均衡管理模型表示為：

(4)

式中：χ0表示高信噪比條件下模型常數項；λ1和λ2為在區間(0,1)范圍內變化的實數。在相鄰小區內網絡信干噪比值越低，會對本小區的通信造成更強的干擾。利用式(3)中的效用函數，進而鏈路負載均衡管理模型即可預測出小區范圍內每個用戶所需要的網絡資源，再基于優化的二分圖匹配算法，改善網絡用戶與鄰近基站之間網絡資源匹配程度和一一對應程度，即可以充分利用現有5G網絡資源，改善用戶的使用體驗和工作效率。

2 基于二分圖匹配的5G網絡鏈路均衡負載方案

2.1 基于二分圖匹配的虛擬頂點轉換

針對密集異構的5G網絡場景，利用通信鏈路效用函數和鏈路均衡負載管理模型，預測出網絡用戶所需要帶寬資源，在均衡負載管理中將5G網絡資源與用戶的通信要求進行合理匹配至關重要。為此本文采用了匹配性能更好的二分圖模擬算法，平衡已有的網絡資源與小區用戶之間通信的實際通信需求，并通過增加虛擬數據頂點的方式平衡網絡性能，并提高與改善5G通信系統數據吞吐量及對5G網絡資源利用率。基于經典匈牙利算法，給定一個無向圖G=(D,E)，其中：D為頂點的集合；E為頂點對應的邊的集合。將頂點集合D按照以下條件劃分為兩個集合D1和D2：

(5)

在無向圖結構中任一條邊都滿足e=(di,dj)∈D，且di∈D1，dj∈D2，集合D1和D2為頂點互補的子集。按照目標小區內用戶的帶寬需求與網絡鏈路的負載情況，構建帶有權重比例關系的二分圖結構G=(H,D,E)，其中集合H和集合D是具有互補性關系的子集，H={h1,h2,…,hm}，D={d1,d2,…,dn}。對于任意的一個集合元素hi和dj，賦予頂點之間的邊一個權重ωij，此時在5G網絡中鏈路均衡問題就可以通過二分圖模型轉換為頂點集合元素的匹配問題。二分圖模型還要求滿足條件|H|=|D|，但在實際的網絡資源匹配中小區用戶數與總體網絡鏈路的數據通常不相等，必須對經典的二分圖算法進行優化和轉換，假定|H|<|D|，就需要在H集合中增加|D|-|H|個虛擬頂點，虛擬頂點集合Q={q1,q2,…,qa}，其中|D|-|H|=a，二分圖匹配的轉換過程如圖2所示。

圖2 二分圖虛擬頂點的轉換過程

2.2 基于二分圖的極大匹配

在給定的無向圖G=(D,E)中，邊集合M的任意兩條邊都不依附于同一個頂點，如果要實現邊的極大匹配，可以通過增加已有邊的匹配邊數實現，選擇這樣的邊數最大的子集稱為圖的最大匹配問題。如果一個匹配中，圖中的每個頂點都與圖中某條邊相關聯，則稱此匹配為完全匹配，也稱作完備匹配。二分圖經過虛擬轉換后，頂點集合數量與集合D的數量保持一致，經過優化后的二分圖結構G′滿足如下條件：

G′=H∪QG′∈(D,E)

(6)

(7)

(8)

5G網絡中用戶i與小區j組成的每一條邊所占權重比例關系矩陣可以表示為：

(9)

采用基于二分圖算法的5G網絡資源匹配法，需要保證構建的集合中頂點數量相等，一般通過虛擬頂點的方式保證通信系統結構的穩定，這樣才能夠保證用戶與小區資源之間的一對一匹配關系。利用鏈路均衡負載管理模型得到的網絡資源匹配預估結果，優化和擴展原有的二分圖結構，計算權重值和矩陣表達式，并對矩陣ωT的行元素和列元素進行初始化處理，得到k行n列權值不為零的矩陣：

(10)

計算矩陣的權值比例關系，如果矩陣中的任一個元素ωij的值為gx(i)+gy(i)，即可以實現矩陣匹配的最優化，并按照矩陣列和行的對應關系均衡小區內部用戶與基站之間的鏈路均衡負載關系。在5G通信網絡條件下，通信功能不僅限于傳統小容量、高延時的通信場景，還要滿足用戶大容量多點通信的要求，最大限度地降低通信網絡延遲。5G網絡下的通信是一種動態、高速通信，對于通信網絡的鏈路性能有著更高的要求。為更精確地預測網絡鏈路的負載情況，需要首先通過網絡鏈路模型預測出用戶所需要的網絡資源及小區資源的利用效率，在均衡網絡負載的過程中實現小區基站、網絡鏈路與用戶之間的均衡負載。

3 仿真驗證與性能評估

3.1 仿真模型搭建與仿真參數設置

為驗證文中提出基于二分圖匹配均衡負載方法的性能，在MATLAB仿真平臺搭建仿真環境，在仿真場景中共設置了8個5G通信基站，其他的移動用戶終端在小區范圍內均勻布置，為保證實驗測試的公平性，依據頻譜的空閑時間，隨機生成通信頻譜。本文所搭建仿真系統的參數配置如表2所示。

表2 仿真參數設置

在本文建立的5G仿真網絡中，基于二分圖匹配的鏈路均衡機制流程如表3所示。

算法1基于二分圖匹配的仿真流程

1. 系統初始化并設置小區基站數和用戶數

2. 根據已有網絡節點生成拓撲結構

3. 執行主循環程序，并對小區用戶位置和基站位置賦值，明確通信網絡的鏈路關系

4. 根據對小區鏈路資源占用的預估，計算用戶數據傳輸中的信干噪比值和判決效用函數值

5. 根據hod值的更新結果，輸出結果

6. if(nueinbs=ueinbs)

7. 系統鏈路性能指數輸出

8. else

9. 重復步驟5、步驟6

10. end if

11.uen=max輸出最優的網絡鏈路負載匹配結果

3.2 鏈路均衡負載方法的性能比較

先在相同的仿真網絡環境下，對比不同的鏈路均衡負載方法的Jain氏負載公平性均衡指數變化情況及系統資源利用率的大小。當5G網絡小區內的通信用戶總體數量持續增加，通信鏈路的負載情況也會隨之出現同步漲落的現象，進而導致網絡節點和通信鏈路出現負載不均衡的情況發生，個別用戶的通信質量也會得不到保證，Jain氏公平性均衡指數是衡量網絡負載公平性的重要指標之一(指數值通常的取值范圍在(0.5,1.0)之間，指數值越高表明公平性越好)，該指數可以用j(xi)來表示：

(11)

在本文仿真環境下不同鏈路均衡負載方法的Jain氏公平性均衡指數變化情況如圖3所示。

圖3 Jain氏公平性指數隨用戶數的變化情況

當小區內用戶數量增加時，不可避免地會導致Jain氏公平性均衡指數出現降低的趨勢，用戶之間會出現一種通信鏈路資源的競爭，這也是采取鏈路均衡負載算法控制網絡節點和鏈路出現擁塞的原因。由于二分圖匹配方法采用了基于最大相似度的二分圖匹配矩陣，從行向量和列向量兩個角度同步計算用戶之間、用戶與基站之間的鏈路負載情況，因此具有更好的鏈路資源分配效果，當小區內的用戶數量達到峰值140時，公平指數仍舊可以控制在0.9左右，明顯優于傳統PSO的73%和IsoRank算法的74%，可以更好地維持鏈路的相對公平。

5G網絡的系統容量主要指基站與用戶之間、用戶與用戶之間鏈路容量的總和。分析各種不同鏈路均衡負載方法控制下仿真網絡的系統容量變化，如圖4所示。

圖4 不同鏈路均衡負載方法下系統容量的變化情況

由于在仿真系統中采用了均衡負載機制，能夠使小區內通信質量較差的用戶得到更多的網絡資源，但3種均衡方法的效率是不一致的，在二分圖匹配均衡負載方法控制下，仿真系統的容量提升更快，系統資源的利用效率更高。在不同系統容量及3種鏈路資源負載均衡方法下，對網絡帶寬資源利用效率數據統計，結果如表4所示。

表4 資源利用效率

本文選取的評價5G通信網絡中鏈路均衡負載方法的性能指標還包括通信業務的阻塞率，該指標對于衡量5G異構網絡的均衡性、穩定性、鏈路均衡度水平至關重要。針對于實時的通信業務，異構網絡系統的業務阻塞率如圖5、圖6所示，5G通信業務的阻塞率越低，表明鏈路均衡算法的性能越好。

圖5 實時業務下各均衡方法的通信阻塞率

圖6 非實時業務下各均衡方法的通信阻塞率

實時業務條件下，當小區內通信業務的用戶數量超過100時，系統由于業務繁忙開始出現阻塞現象，但在基于二分圖匹配的鏈路均衡算法下系統阻塞率變化幅度要更小，網絡延遲相對于傳統方法更低；而在非實時5G通信業務條件下，本文方法的優勢更為明顯。

在非實時業務條件下IsoRank算法和PSO算法分別在超過40個用戶和50個用戶時，就開始陸續出現通信阻塞，表明非實時業務對于通信鏈路不均衡的影響較為嚴重；而非實時通信業務對于二分圖匹配均衡負載方法的影響程度較低，與實時業務的影響相近，這證明二分圖匹配方法的適用范圍更大，可以適合多場景的5G異構網絡鏈路負載均衡應用。

4 結 語

5G網絡條件下通信鏈路的密集程度更大，在高容量、高負載的網絡環境下更容易導致網絡鏈路負載不均衡和網絡節點的數據擁塞，這將在很大程度上降低5G用戶的網絡使用體驗。為滿足用戶更高、更快及更低延遲的實時通信要求，本文提出一種基于二分圖匹配的網絡鏈路均衡負載方法，利用二分圖在頂點與側邊優化匹配等方面的優勢，提升5G網絡中通信鏈路均衡負載性能。鏈路均衡負載技術是5G通信的核心技術之一，只有在網絡均衡負載的前提下，大規模MIMO和毫米波通信才具有實際的意義。隨著5G用戶數量的增加，二分圖匹配算法的迭代次數也會呈幾何數量級增加，會給虛擬頂點的選擇與權重矩陣的構建帶來一些新的問題，因此必須不斷地優化模型效用函數性能和降低算法的復雜程度，以更好地應對用戶數量的增長和網絡鏈路密集程度的提高。