考慮負載均衡和用戶體驗的垂直切換算法

馬 彬 鐘世林* 謝顯中 陳 鑫

①(重慶郵電大學計算機科學與技術學院 重慶 400065)

②(重慶郵電大學重慶市計算機網絡與通信技術重點實驗室 重慶 400065)

1 引言

在城市核心區域，隨著5G基站的大量部署以及公共交通網絡的迅速發展，逐漸形成了超密集異構無線網絡[1,2]。然而，隨著城市的發展和車輛的普及，城市的交通擁堵情況卻日益加劇，每天的交通高峰期會有大量的車輛，特別是公交車，擁堵在城市核心區域路段。車輛的爆發式增長除了引起道路的擁堵，還會因大量車載終端(vehicle terminal)在短時間內的聚集性移動造成網絡擁塞和帶寬資源緊缺，使得已接入網絡用戶的服務質量出現嚴重下降。因此，在車輛異構無線網絡中如何通過移動性管理緩解網絡擁塞，實現負載均衡，進而保證用戶體驗成為該領域研究的熱點問題。

作為異構網絡中移動性管理的關鍵技術，垂直切換是多網融合的基礎。目前國內外已有較多文獻致力于垂直切換的研究。根據采取研究方法的不同，垂直切換算法大致可以分為以下4類：(1)基于單閾值判決的垂直切換算法[3,4]，當接收信號強度(Receive Singal Strength, RSS)或其他網絡參數達到設定閾值后直接觸發切換；(2)基于多屬性決策的垂直切算法[5,6]，首先確定網絡側和用戶側的多個參數指標(如帶寬、抖動、負載、用戶偏好等)的權重，然后構建目標效用函數并計算效用值，最后選擇最優效用值的網絡進行接入；(3)基于人工智能的垂直切換算法，利用模糊邏輯[7,8]、神經網絡[9,10]、強化學習[11,12]或智能仿生算法[13,14]等模型，將判決參數作為模型輸入進行智能的切換判決；(4)基于匹配博弈網絡的垂直切換算法[15,16]，把網絡中的基站或者用戶抽象為博弈過程的參與者，使用判決參數建立博弈雙方的效用函數，并通過博弈過程中的納什均衡求解，優化網絡性能。

當前已有不少的文獻致力于研究異構無線網絡中的網絡擁塞、負載不均、用戶體驗等問題，并且都取得了一定的成效。文獻[17]提出了一種基于效用函數的網絡選擇方案，通過綜合考慮用戶的服務質量 (Quality of Service, QoS)需求、偏好、成本以及網絡負載，改善了用戶體驗，提高了網絡吞吐量。文獻[18]通過分析用戶行為給用戶設定不同的優先級，然后給不同優先級的用戶制定不同的遷移策略，緩解了網絡擁塞。文獻[19]引入一種基于端對端 (Device to Device, D2D)通信輔助的流量遷移方案，減輕了蜂窩網絡中遷移用戶給WiFi訪問點帶來的嚴重負擔。文獻[20]則巧妙地將網絡建模為一個有向圖，并以超載的網絡及其n層鄰居構建集群，通過在集群中實現局部負載均衡，提高了網絡總體性能。另外，文獻[21–24]提出通過機器學習和大數據分析的方式，來對自動的流量遷移方案進行學習，達到了緩解網絡擁塞，均衡負載的目的。

上述算法大多通過切換遷移的方式在一定程度上緩解了網絡擁塞，但在因大量終端短時間聚集性移動引起網絡擁塞的場景中，僅通過遷移的方式，而不考慮用戶的選網需求會隨著網絡環境的變化做出相應的調整，并對網絡容量進行提升，則極易造成鄰近基站的網絡資源緊缺和用戶體驗得不到實質性改善。為解決這一問題，如何提升網絡容量、改進切換策略、優化終端的選網過程成為本文研究關注的核心問題。因此，本文提出一種考慮負載均衡和用戶體驗(Load Balance and User Experience,LBUE)的垂直切換算法。該算法將城市核心區域的網絡通信建模為車輛自組織異構無線網絡模型，與直接與外基站連接相比，本模型采用了在公交車輛上部署無線信號收發器(Radio Transceiver, RT)的策略，提高了網絡總容量。若將部署了RT的車輛作為簇頭，以分簇結構組建自組織網絡(ad hoc)，能夠避免因大量終端與基站直接相連引起服務質量的嚴重下降，緩解了網絡擁塞。此外，當終端觸發切換后，通過自適應切換判決算法能夠為用戶篩選出當前網絡環境下滿意度最高的網絡，提升了用戶體驗。本文的主要貢獻可以概括如下：

(1)引入網絡擁塞感知模型，提出一個融合自組織網絡的超密集異構無線網絡架構。

(2)定義業務適應度和負收益因子兩個自適應參數，提出一種基于秩和比的自適應切換判決算法。

2 算法設計思路和流程

在城市核心區域，由于車輛的聚集性移動，網絡的負載狀況呈現出時變特性。因此在設計選網算法時，需要對當前網絡狀況進行實時感知，并能根據感知結果觸發不同的處理機制。若網絡環境正常，可直接為切換用戶篩選出能保證其偏好需求的目標網絡；若網絡環境擁塞，則需要緩解擁塞的措施來保證用戶的正常通信?；谝陨纤悸?，如圖1所示，本文算法可設計為以下3個階段：(1)網絡環境感知：獲取網絡中各個基站的平均負載程度和負載變化率數據評判出網絡的擁塞情況。(2)構建自組織網絡：當網絡環境感知判決網絡狀態為擁塞時，啟動分簇算法，根據車輛的運動信息以分層的簇結構組建車輛自組織網絡，讓自組織網絡也成為用戶的備選網絡。(3)自適應切換判決算法：終端觸發切換后，根據網絡的擁塞情況和用戶的業務請求，調整輸入到決策算法中的決策參數，為用戶篩選出當前環境下滿意度最高的目標網絡。

圖1 算法流程示意圖

3 網絡環境感知

假設各個基站都連接到了網絡控制中心，通過中心的負載管理器能對各個基站資源使用情況進行實時監測。網絡環境感知指的是通過分析監測到的網絡資源變化數據對網絡當前的擁塞狀況和未來的擁塞趨勢作出判決的過程。傳統感知策略[25]通常采用單個負載閾值與基站的負載程度進行比較來判斷網絡是否陷入擁塞，不能對網絡的擁塞趨勢進行預測。因此，本文提出一種網絡擁塞感知模型，首先使用監測數據計算出網絡平均負載程度和負載變化率均值，然后根據這兩項指標綜合評估網絡環境是否有擁塞的趨勢。

3.1 相關參數定義

(1) 網絡平均負載程度。本文通過網絡已使用資源塊數量占總資源塊數量的比值來定義網絡平均負載程度。假設某區域內共有N個基站，其中第j個基站能分配的總資源塊數為Rj，接入到基站j的終端數量為U，其中第i個終端分配到的資源塊數量為rij， 則網絡平均負載程度ξ可表示為

3.2 網絡擁塞感知模型

設計網絡感知模型的目的是簡單、直接、有效地獲得網絡擁塞狀況，以便于區分下一步是否需要構建自組織網絡。故本文采用網絡平均負載程度ξ和平均負載變化率?ξˉ來綜合評判網絡的擁塞狀況。ξ反映的是網絡資源的使用情況，ξ越大表示網絡資源消耗越多，擁塞情況越嚴重； ?ξˉ反映的則是網絡資源被消耗的快慢程度， ?ξˉ越大表示網絡資源消耗越快，網絡陷入擁塞的風險越大。式(4)是網絡擁塞判斷函數

在該函數中，通過引入負載上下限閾值區間[ξmin,ξmax]和 負載變化率閾值?ξ0，對網絡負載程度和負載變化快慢進行度量。在負載達到負載下限閾值時，通過考察平均負載變化率決策網絡是否會在較短時間陷入網絡擁塞。如果網絡持續緩慢增大，無法通過負載變化率感知出擁塞結果，則通過負載上限閾值作為擁塞感知的兜底策略。

圖2(a)和圖2(b)是負載管理器在2 min內監測到的平均負載程度實時變化曲線，其中1個采樣周期?t的間隔為1 s，從采集的實時數據可計算出在1個?t內ξt ?ξt?1的 取值區間為[–0.05,0.05]，也即?ξ的取值范圍為?0.05≤?ξ ≤0.05 。在ξ和?ξ取值范圍以及ξmin<ξmax等條件的 約束下，以0.1, 0.1和0.005為步長，對這3個閾值的取值進行組合，將組合得到的605組值依次代入到仿真程序，發現在[0.3,0.5],[0.7,0.9]和[0.04,0.05]范圍內進行取值更符合本文設置閾值的意圖。在剩下的27組取值組合中，經逐一對比發現，將3個變量分別設置為0.4, 0.8和0.045時，兩種策略在不同的終端到達率下對緩解網絡擁塞和提高用戶體驗的效果相對其他組取值更為理想，因此此處采用此組數據來驗證兩種策略對網絡環境的感知效果。從中可以看出，本文策略由于考慮了平均負載程度ξ和平均負載變化率?ξˉ兩個指標，在第80個采樣周期?ξˉ超過?ξ0時做出了第1次預警，并且在此之后由于負載變化率一直超過?ξ0，本文感知策略已經預警出網絡陷入擁塞的趨勢為高風險，在第91個采樣周期ξ超過ξmax時再次做出了預警提示。而傳統策略只有當ξ超過ξmax時才會進行預警，故本文感知策略相較于傳統策略能夠根據網絡的擁塞趨勢提早做出預警。

圖2 本文策略和傳統策略對比

4 組建車輛自組織網絡

4.1 相關假設

由于自組織網絡具有隨時隨地自動組網、可擴展性強等特性，當某段道路有大量車輛擁堵引起網絡擁塞時，可建立帶簇頭節點的自組織網絡來提升網絡性能。因此本文將自組織網絡引入到城市核心區域的網絡場景中，形成宏蜂窩、微蜂窩、無線局域網(Wireless Local Area Network, WLAN)、自組織網絡異構而成的車輛自組織異構無線網絡[26]。該場景中的相關假設如下：

(1)每輛車上都裝備了GPS，并能協助車載終端精準獲取到速度、位置、方向等運動信息。

(2)每輛公交車上都裝備了一種能夠提供網絡服務的無線信號收發器，該裝置啟動后便能與外部基站建立起通信鏈路，為接入的車載終端提供網絡服務[27]。

(3)將自組織網絡的組網形式考慮成由1個簇頭(cluster head) 和多個簇節點(cluster node)組成的若干個簇結構。當多個車載終端接入到RT，組成的網絡結構稱為簇。在一個簇中，裝載了無線信號接收器的車輛為簇頭，接入到RT的車載終端節點為簇節點。簇頭(cluster head)的數量為ch，每個簇頭有唯一的編號h，第h個簇中的簇節點(cluster node)數量為cn，各個簇節點也有唯一的編號n。

(4)每個簇頭都維護了一張簇信息表(Cluster Information Table, CIT)，用于存儲簇的基本信息。

4.2 自組織網絡的生成過程和維護

(1)簇相關因子。簇相關因子用于描述自組織網絡生成過程中，簇頭和簇節點車輛之間的相關性。如果簇節點車輛與簇頭的運動方向一致，相對速度越小，位置越接近，則簇相關因子值越大。簇節點更適合加入到簇相關因子更大的簇以維持更持久的連接，簇節點n和簇頭h的簇相關因子β可表示為

(3)車輛自組織網絡分簇算法。當網絡環境感知算法判決出網絡有擁塞趨勢時，就應該提早啟動分簇算法組建車輛自組織網絡來緩解網絡擁塞。由于車輛的移動會導致簇頭和簇節點之間的狀態頻繁發生變化，為了維持簇內的正常通信，本文通過報文消息機制對簇的生成、簇飽和限制、簇銷毀幾個階段進行維護，在簇頭和簇節點之間傳輸的報文消息攜帶了建簇過程需要采集的數據，算法具體步驟如表1所示。

表1 車輛自組織網絡分簇算法

5 自適應切換判決算法

在本文網絡場景中將車載終端的業務請求大致分為高帶寬時延敏感型業務(如視頻通話)和低帶寬數據型業務(如網頁瀏覽)兩種類型。通過分析用戶的實際用網體驗可知，隨著網絡環境的變化，用戶對網絡的要求也會做出相應調整。當網絡環境正常時，大多數網絡都能滿足用戶的基本服務需求，此時用戶希望用更低的網絡花費換來更高的傳輸速率；當網絡環境擁塞時，一味地追求性價比會加劇網絡的擁塞，此時低阻塞率成為用戶關注的重點。因此本文提出一種自適應切換判決算法，該算法能夠根據終端請求的業務類型和網絡環境感知結果，自適應調整用戶的候選網絡和輸入到判決算法中的選網參數，為終端篩選出當前環境下滿意度最高的目標網絡。

5.1 相關參數定義

(1)接收信號強度與數據傳輸速率。接收信號強度(Received Signal Strength, RSS)是終端評價網絡的一個基本指標，它反映了網絡的信道質量。由于信號在傳輸過程中存在路徑損耗，終端i接入網絡j的接收信號強度可表示為

(2)業務適應度。當網絡擁塞時，希望通過自組織網絡來緩解網絡擁塞，但由于自組織網絡提供的服務能力有限，因此應盡可能避免讓高帶寬業務需求的終端接入到自組織網絡。為了讓切換的終端能根據業務請求自適應匹配候選網絡，本文定義業務適應度這一指標來衡量各網絡對業務的適應能力，業務適應度越高表示網絡越適宜該類業務請求，反之，越不適宜。若業務適應度為0，則表示網絡不支持用戶請求的業務。因此終端i以業務類型l接入網絡j的業務適應度可表示為

5.2 基于秩和比的自適應切換判決算法

秩和比綜合評價法[28]，是一種集古典參數統計與近代非參數統計各自優點于一體的統計分析方法，它能夠很好地避免決策過程中的主觀因素。在終端選網決策過程中，將待評價的候選網絡和評價網絡性能的參數抽象為一個N行M列的數據矩陣，便可通過秩和比綜合評價法決策出最優網絡。本文所提基于秩和比的自適應切換判決算法的流程如圖3所示。

圖3 基于秩和比的自適應切換判決算法

(1)獲取選網參數：選網判決過程中需提前獲取的網絡參數有網絡擁塞程度(ρ)、終端請求的業務類型(l)、數據傳輸速率(e)、網絡成本(c)、網絡阻塞率(b)。

6 仿真結果分析

6.1 系統模型和仿真參數設置

為了評估本文所提算法的性能，利用Matlab仿真工具模擬了城市核心區域潮汐高峰期某一段長3000 m、寬30 m雙向4車道的網絡仿真場景。在該仿真場景中，假設部署有2個5G宏基站(5GM)，2 0 個5 G 微 基 站(5 G S)以 及2 0 個 無 線 局 域 網(WLAN)和若干車輛自組織網絡(Ad Hoc)。在整個網絡覆蓋范圍內，假設車輛的到達服從到達率為1≤λ ≤10的泊松分布。本文的網絡場景如圖4所示，為了便于觀察，圖4的網絡場景簡化了5G微基站、無線局域網和車輛自組織網絡的數量。

圖4 城市核心區域異構無線網絡仿真場景

為了驗證本文算法能夠適應車輛自組織異構網絡中的接入問題，仿真中設計了平均負載程度、網絡吞吐量、平均阻塞率、接入終端掉話率等8組實驗。由于文獻基于層次分析法和簡單加權(Analytic Hierarchy and Simple Additive Weighting, AHPSAW)的垂直切換算法[30]，基于閾值的多業務負載均衡(Multi-Traffific Load Balance, MTLB)算法[31]和基于負載均衡和QoS感知(Load Balancing and QoS-Aware, LBQA)的網絡選擇算法[32]提出了不同的方案來解決與本文類似的網絡擁塞和負載均衡等問題，故選取了這3種算法與本文所提算法進行對比分析。仿真中的網絡參數設置如表2所示。

表2 網絡仿真參數

6.2 網絡平均負載程度和吞吐量

圖5為4種算法的平均負載程度變化曲線，從中可以看出隨著車載終端數量的增加，網絡的平均負載程度逐漸上升。在車載終端數量低于400臺時，本文的LBUE算法的網絡平均負載程度比MTLB算法略高，這是因為LBUE算法在網絡不擁塞時，選擇的是網絡服務質量較好且成本較低的網絡，消耗了更多的網絡資源。但隨著車載終端數量增加到500臺時，本文算法通過網絡環境感知判決出網絡有擁塞風險，便通過分簇算法引入車輛自組織網絡，并通過自適應算法調整決策參數，讓終端接入到了阻塞率較低的網絡，減少了接入到重負載基站的終端數量，降低了網絡的平均負載程度。

圖5 網絡平均負載程度

圖6比較了4種算法的網絡總吞吐量。從中可以看出，隨著終端數量的增加，系統總吞吐量呈上升趨勢，當終端數量低于500臺時，4種算法的總吞吐量都迅速上升；當終端數量高于500臺時，由于網絡總的資源有限，總吞吐量上升的趨勢逐漸趨于平穩。但當終端數量相同時，LBUE算法的總吞吐量始終高于其他3種算法。這是因為當網絡即將擁塞時，本文算法引入了車輛自組織網絡，增加了網絡容量，減少了接入到蜂窩網絡和WLAN中的車載終端數量，均衡了各個網絡的負載，有效地提高了網絡總吞吐量。

圖6 網絡總吞吐量

6.3 平均阻塞率和接入終端掉話率

圖7表示的是4種算法的平均阻塞率變化曲線，從中可以看出當車載終端的到達率λ≤3時，網絡資源充足，4種算法的接入阻塞率都趨近于0，隨著到達率的增大，網絡中會有越來越多的終端開始競爭網絡資源，因此3種對比算法都相繼出現部分終端被阻塞。從圖中不難看出MTLB算法的阻塞率一直處于最大，而本文所提的LBUE算法在終端到達率λ= 8時才開始出現阻塞，這是因為MTLB算法在均衡實時業務和非實時業務時，部分實時業務被遷移到了將要發生阻塞的網絡中，增加了阻塞的可能性。而本文算法，在通過環境感知判決出網絡有擁塞的可能就會引入自組織網絡，增加了終端的接入選擇，因此隨著終端到達率的增加，本文算法的接入阻塞率始終低于其他3種算法。

圖7 用戶平均阻塞率

圖8是接入終端掉話率隨到達率的變化曲線。從圖中可以看出當網絡中接入的終端數量較少時，每個終端能夠分配到足夠的網絡資源，因此掉話率趨近于0，但由于網絡資源有限，隨著接入網絡終端數量的增加，部分終端分配到的網絡資源將無法滿足其最低需求，終端掉話率逐漸上升，但本文算法相較于其他3種算法，掉話率上升得比較緩慢，這是因為自組織網絡能夠為部分網頁瀏覽類業務終端提供服務，較大程度地減少了掉話終端的數量。

圖8 接入終端掉話率

6.4 接入終端數量和網絡穩定性

圖9反映的是當接入終端數量為1000臺時，采用本文算法的不同業務類型終端接入到各類網絡的數量。從中可以看出瀏覽網頁的終端在各類網絡中均有接入，而視頻通話的終端則主要接入到了5G微蜂窩和WLAN網絡。這是因為瀏覽網頁所需的資源塊較少，在計算業務適應度時各類網絡均能適應其業務請求，視頻通話需要的資源塊較多，接入到自組織網絡的業務適應度會比較低。

圖9 不同業務類型終端接入各類網絡的數量

圖10反映的是某業務類型為網頁瀏覽的終端在1 min內接入4種不同類型網絡所能獲得的數據傳輸速率。從中不難看出，該終端在各個時刻獲得的數據傳輸速率一直處于波動狀態，但4類網絡均能滿足該終端的業務需求。由于標準差能夠衡量數據的穩定性，使用4組數據計算標準差，求得宏蜂窩的標準差為5.4325，微蜂窩的標準差為5.7729,WLAN的標準差為5.7709，Ad Hoc網絡的標準差為5.9772。因此，相較于已有的網絡，自組織網絡的數據傳輸速率的波動在可接受范圍，且能夠保證該終端的正常通信。

圖10 數據傳輸速率波動情況

6.5 時間開銷和信令開銷

圖11為4種算法的時間開銷變化曲線，從中可以看出隨著車載終端數量的增加，4種算法的時間開銷都逐漸增加。剛開始時幾種算法的時間復雜度相差不大。但隨著車載終端數量增加到500臺時，本文算法的時間復雜度比其他3種算法略微偏大。出現這種現象是因為本文算法感知到網絡擁塞時，就啟動了自組織網絡的構建過程，組建自組織網絡的過程產生了一定的時間開銷，并且隨著車輛數量的增加，越來越多的車輛會考慮接入到自組織網絡，因此本文算法的時間開銷始終略微高于其他3種算法。

圖11 時間開銷

圖12顯示了隨著車載終端數量增加時，4種算法的信令開銷占總資源消耗的比值對比。隨著終端數量的增加，4種算法的信令開銷占比也在不斷增加，這是因為終端請求接入網絡的過程會有一定的信令開銷。當終端數量增加到500臺時，本文算法的信令開銷占比相較于其他3種算法一直處于略微偏高的狀態，這是因為本文采用了報文消息機制構建自組織網絡，在簇的生成和維護過程中產生了一些必要的信令開銷。

圖12 信令開銷

7 結束語

本文提出一種考慮負載均衡和用戶體驗的垂直切換算法，該算法適用于城市核心區域車輛自組織異構無線網絡中的切換問題。首先根據負載程度和負載變化率數據實時感知網絡環境的擁塞情況。其次，通過網絡環境感知結果判決是否建立帶簇節點的自組織網絡，并把簇頭節點加入備選網絡集。再次，當終端觸發切換后，自適應切換判決算法會根據網絡的擁塞狀況和業務請求，調整輸入到決策算法中的自適應參數，為用戶篩選出滿意的接入網絡。最后，仿真表明，該算法能夠緩解城市核心區域的網絡擁塞問題，實現負載均衡，提升用戶體驗。下一步工作，希望通過位置預測和跳躍切換算法解決城市核心區域超密集部網引起的頻繁切換，服務降級問題。