考慮負載均衡與傳輸速率的異構網絡接入控制

劉麗娟，劉定一，陳松楠,3

(1.信陽農林學院 信息工程學院，河南 信陽 464000；2.河南警察學院 網絡安全系，河南 鄭州 450046； 3.北京林業大學 工學院，北京100083)

0 引 言

近些年無線終端用戶的數量出現了爆發式的增長，且對視頻業務的需求量也越來越大，這就需要更多的頻譜資源來滿足不同的業務接入。由于固定單一的網絡頻譜資源有限，當大量用戶有業務請求時，不僅會出現接入成功率低的情況，還會影響在線用戶的使用體驗[1]。當無線終端處在多種不同類型的異構網絡覆蓋中時，運營商會根據業務類型和網絡資源的剩余情況，將不同的業務接入到最適合的網絡中，保證資源的利用率及用戶的使用體驗。從運營商的角度考慮，會優先關心網絡的負載均衡問題，因為非均衡的網絡容易出現接入成功率低和阻塞的問題；而從用戶的角度考慮，則希望得到最大的傳輸速率[2-4]。

在生活中往往會遇到此類問題，在滿足一定的約束條件下，希望兩個或兩個以上相互沖突的目標達到最優，統稱為多目標優化問題(MOP)[5-7]。MOEA/D算法可以更高效地求解高維多目標優化問題，得到的解集精確，且計算復雜程度低[8,9]。但在MOP中仍然存在收斂性和多樣性相互制約的問題，學者們也相繼提出了很多的改進方法。文獻[10]采用精英策略和差分進化修正的方法進行全局搜索，提高了算法的收斂精度和全局搜索能力；文獻[11]設計了自適應的變異算子和鄰域值，有效改善了算法的全局搜索能力和收斂性；文獻[12]引入了多策略變異，并通過采取非支配排序，選取更優的解來實現差分進化，改善了算法的收斂速度和多樣性。然而，上述這些方法在平衡算法的多樣性和收斂性方面仍有不足，為此本文在優化了聚合函數的基礎上，從變異概率和鄰域兩個方面提出了自適應的改進策略，并將其應用在異構無線網絡的業務接入控制中，來解決網絡負載平衡和系統傳輸速率的問題，最后通過實驗驗證了方法的有效性。

1 建立異構網絡模型

假設在某區域存在N個異構無線網絡，在其重疊覆蓋的空間有M個多模終端，采用多用戶正交頻分復用(OFDM)的方式進行數據傳輸，其中最小的資源計量單位是1個時隙和1個子信道組成的二維資源單元(TRU)[13]。若網絡k的子載波數量為Nk，每個子信道中有Fk個子載波，那么網絡k的最大資源TRU可表示如下

(1)

式中：SPk表示OFDM的符號周期；Sk表示每個時隙中符號的數量；TSk表示數據幀的長度。

假設用xjk來描述終端業務與網絡的連接情況，當終端業務j接入網絡k時，xjk=1，反之，則xjk=0。那么M個終端業務與N個網絡就形成的映射關系，可表示成1個M×N的矩陣，矩陣的元素為xjk。若網絡k連接到終端業務j要占用的資源數是tjk，那么所有的業務消耗網絡k的資源總數為

(2)

聯合式(1)、式(2)可計算網絡k的負載率描述如下

(3)

假設終端業務j占用網絡k的信道帶寬為bjk，利用香農定理可計算出網絡k的數據傳輸速率rk如下

(4)

式中：ωjk為效益因子；Sjk為信號功率；Njk為噪聲功率。

本文將最小網絡間負載率方差V和所有網絡系統傳輸速率的倒數R作為優化的目標函數進行組合，轉化成多目標優化模型。

根據網絡負載率式(3)，最小網絡間負載率方差函數V可描述如下形式

(5)

根據網絡傳輸速率式(4)，對所有網絡中業務的傳輸速率進行累加，再對其求倒數，將其最小值(也就是系統最大速率)作為優化函數R可描述為

(6)

對于單個網絡來說，其能提供的資源是有限的，所以接入該網絡所有的資源數不能大于其能提供的總數，產生約束條件描述如下

(7)

另外，對于終端業務接入網絡的數量有限制，即每個業務最多只能與1個網絡進行連接，產生約束條件描述如下

(8)

2 多目標優化問題及MOEA/D算法

由于MOP之間的解往往相互制約和沖突，當一個目標的解較好時，另外一個解就會變差，所以MOP的解并不唯一，而是一組最優的解集，這就需要在參數設置時，要根據實際的需要進行折中選擇[14,15]。終端業務的接入方式(即終端與網絡的映射關系)決定了不同網絡間的負載平衡和系統的傳輸速率，屬于多目標優化問題。故本文以接入方式作為變量，將最小負載率方差函數和系統最大傳輸速率的倒數作為目標函數，并結合2個約束條件進行組合，轉化成多目標優化模型，利用改進的MOEA/D算法進行求解，得到最優的接入方案。

2.1 多目標優化問題描述

針對m個目標的優化問題，設其具有n個決策變量，對應的決策向量為x=(x1,x2,…,xn)∈Rn，通過數學表達進行描述如下

(9)

式中：Ω表示可行域空間；Ω→Rn有m個目標函數，分別為f1(x)，f2(x)，…，fm(x)。

為了能夠更加清楚表述多目標優化問題，對以下問題進行了定義：

定義1 Pateto支配：若x,y∈Ω是可行解，對于任意的i=1,2，…，m，當且僅滿足式(9)時，那么xPateto支配y，計作xy

(10)

定義2 Pateto最優解集：MOP的最優解是由多個Pateto最優解組成，即所有的最優解稱為Pateto最優解集(Pateto set，PS)，或者稱為非支配解，表示為

(11)

定義3 Pateto最優前沿：Pateto最優解集在目標空間的投影對應的就是Pateto最優前沿(Pateto front，PF)，表示為

PF={F(x)|x∈PS}

(12)

2.2 MOEA/D算法框架分解

MOEA/D算法的核心思想是將多目標問題分解成多個單目標問題進行求解，經典的分解方法有：加權和、切比雪夫和PBI這3種方法[16]。其中，最常用的是切比雪夫法，通過在單目標上增加權重來進行變換，這個分解的過程表示如下

(13)

由于MOEA/D算法本質上屬于迭代的過程，在每次的迭代中都會保持種群的個體數量n，分別為x1,x2,…,xn，那么xi則表示第i個單目標優化問題的當前解。同時，單目標優化問題對應著權重向量λi，利用權重向量間的歐式距離定義鄰居集合，也就是對應權重向量距離最小的子問題集合。

3 MOEA/D算法的改進策略

由于傳統的MOEA/D算法在整個進化過程中會保持固定的鄰域值和變異概率，容易出現全局搜索能力差和收斂慢的問題，本文提出了自適應的調整策略。同時，構造了雙曲線聚合函數，根據權重向量與坐標軸的距離調整個體的支配范圍來增強算法的收斂性和散布性。

3.1 雙曲線聚合函數

令理想的參考點z*=(0,0,…,0)，在二維目標空間，本文構造了雙曲線函數對多目標問題進行分解，表示為

(14)

式中：α表示雙曲線的實軸長度，用來調節彎曲度；θ表示雙曲線漸近線斜率的倒數，用來調節張角；ki則表示權重向量λ與目標空間上各坐標軸夾角的余弦；f′1,f′2分別表示目標向量f1,f2的變換，表示為

(15)

通過調整參數α和θ能夠生成不同形狀的曲線，實現對聚合函數的光滑化處理。其中，α可以控制算法的收斂性，而θ可以控制算法的散布性。不失一般性，在處理m維的多目標優化問題時，聚合函數表示為

(16)

從目標向量(f1,f2,…,fm)到(f′1,f′2,…,f′m)的變換表示如下

(17)

式中：A為m×m的變換矩陣，表示為

利用雙曲線函數對多目標問題進行分解，在選擇個體時，使得接近坐標軸的權重向量增大了個體的支配范圍，從而具有更強的收斂性。同時，使得距離坐標軸較遠的權重向量能夠縮小個體的支配范圍，則突出了散布性。

3.2 自適應因子調整策略

在多目標優化算法的迭代前期，需要盡量保持種群的多樣性，讓搜索范圍盡可能大些，這樣可避免陷入局部最優，而在迭代的后期，則需要提高算法的收斂速度。

3.2.1 自適應變異概率

在MOEA/D算法中大多設置了固定的變異概率，若取值過小會難于產生新個體，影響進化速度，取值過大，則會趨于隨機搜索，不僅弱化了全局的搜索能力，還容易出現早熟的問題。為此，提出了一種自適應的變異概率，通過最大適應度與平均適應度的距離來自適應調整變異概率的大小，改進策略描述如下

(18)

式中：fav表示種群的平均適應度值；fmax則表示最大適應度值；k表示范圍在(0,1]的常數。當arcsin(fav/fmax)大于等于π/6時，說明種群適應度的平均值與最大值的距離較近，而距離最小值較遠，種群的適應度值較分散，個體間的差異明顯，種群表現出了多樣性，所以此時會相應地降低變異概率值，避免優良個體被破壞，從而提高收斂速度；相反，當arcsin(fav/fmax)小于π/6時，說明種群的平均適應度與最小值距離較近，個體間的差異不大，所以此時會適當地升高變異概率值，避免陷入局部最優，從而能夠提高全局搜索能力。

3.2.2 自適應鄰域

在MOEA/D算法中，鄰域值越大，可選解的數量就越多，也可以更好地維持種群的多樣性，但會占用過多的計算資源，且還會使解偏離Pareto前沿；鄰域值越小，雖然算法的收斂性增強了，但會弱化種群的多樣性。為此，本文通過引入自適應調整鄰域值，來平衡算法在整個進化過程中的多樣性與收斂性，提升算法的整體性能，鄰域值的自適應表達式如下

(19)

3.3 改進算法流程

改進算法的工作具體步驟描述如下：

步驟2 遺傳操作。計算個體的適應度，再根據式(18)求出變異概率，并進行變異操作得到新個體y，將新個體的適應度值與理想點z的適應度值進行比較和更新；

步驟3 根據當前的迭代進程，利用式(19)計算出鄰域值，如y1支配鄰域內的y2，則用y1替換y2；

步驟4 若滿足收斂條件，則直接輸出結果PF；

步驟5 如不滿足收斂條件，且未到最大迭代次數，則將迭代次數t+1后，繼續執行遺傳進化操作。反之，則輸出結果PF。

4 改進算法測試驗證與對比

為驗證本文提出改進算法的性能，在Matlab 2016a環境中進行了測試實驗，運行的硬件平臺配置為：Intel Core i7的CPU，主頻率2.8 GHz；8 GB的內存；操作系統是64位的Windows 7。采用經典MOEA/D、文獻[10]中的MOEA/D-DE、文獻[11]中MOEA/D-εC、文獻[12]中的MOEA/D-DMSM和本文的改進算法求解具有代表性的2維目標空間基準函數ZDT1、ZDT2、ZDT3和ZDT4，每種算法在上述的測試函數上分別運行25次，并將計算得到的反向時代距離(inverted generation distance，IGD)均值和標準差記錄到表1中。其中，IGD可以衡量算法的收斂性和多樣性，IGD的值越小，則說明計算得到的Pareto最優解的收斂性和分布性越好。設置經典MOEA/D算法參數：采用模擬二進制交叉，ηc=30，交叉率為1，鄰域大小T=20。本文提出算法的參數設置如下：雙曲線形態調整參數θ=2.8，α=0.12；自適應變異概率的調整參數k=0.75；縮放因子F=0.5。設置種群大小n=100，迭代進化的最大次數tmax=1500。

表1 不同算法在測試函數上運行得到的IGD結果

從表1中的數據可直觀看出：提出的改進算法在測試函數ZDT1、ZDT2和ZDT4上得到的IGD均值明顯優于其它4種比較算法；在測試函數ZDT3上，MOEA/D-DMSM算法得到的IGD均值最優，但與本文提出的改進算法得到的運行結果在同一數量級，且差距并不大，驗證了提出的改進方法在改善算法收斂性和多樣性方面具有的優勢。另外，改進算法計算得到的標準差也都優于其它比較算法，進一步驗證了改進策略能夠給算法帶來更高的穩定性。

為了能夠更直觀地了解改進算法的運行結果，使用本文的改進算法在測試函數ZDT1-ZDT4上進行求解，得到Pareto前沿的分布情況如圖1所示。

從圖1的仿真結果可看出：利用本文提出的改進算法在測試函數上得到的非支配解集非常逼近真實的Pareto前沿，且分布較為均勻，從而驗證了雙曲線聚合函數、自適應變異概率以及動態鄰域在進化的不同階段起到的調節作用，說明了提出改進策略能夠有效平衡算法的多樣性和收斂速度。

圖1 改進算法在測試函數上求解出的PF分布

5 實驗結果與分析

為驗證本文提出的改進算法在異構網絡接入控制中的有效性和優越性，在Matlab環境下進行仿真實驗，選擇TD-LTE、WLAN和WiMax這3個無線網絡組成異構網絡，網絡配置參數見表2。

表2 異構網絡配置參數

假設異構網絡中有50個初始的業務，并隨機生成50個待接入的業務，其中實時業務和非實時的業務各占50%，且速率均勻分布在400 kbps-800 kbps和600 kpbs-1200 kpbs。

5.1 不同算法下3種網絡歸一化負載率對比

為清晰展示3種網絡在接入新業務過程中的變化情況，對網絡的負載率進行歸一化處理，并記錄從接入第51個業務到第100個業務在文獻[17]、文獻[18]和本文改進算法下3種網絡歸一化負載率的變化情況如圖2所示。

從圖2的仿真結果可看出：在3種算法下，隨著新業務的接入，3種網絡的負載率均呈上升趨勢。在文獻[17]的算法下，由于沒有把網絡均衡作為優化的目標，在接入相同業務的情況下，3個網絡間的負載率相差較大；文獻[18]的算法較文獻[17]有了較大改善，3條線出現了明顯的聚攏，但仍然不夠均衡；而在本文改進算法下，3條負載率曲線最緊湊，說明網絡負載最均衡，從某種程度上講，這樣能夠保證每個網絡都有相當的剩余資源供新業務的接入，也能有效避免網絡阻塞的情況發生。

圖2 新業務接入過程中歸一化負載率變化情況

5.2 不同算法下系統傳輸速率對比

同樣，采用文獻[17]、文獻[18]和本文改進算法在接入不同數量的新業務時，網絡的系統傳輸速率結果如圖3所示。

圖3 新業務接入過程中傳輸速率的變化情況

從圖3的仿真結果可看出：當接入業務數量小于80個時，在3種算法的作用下，3種網絡的傳輸速率與業務的接入數量呈近似線性增長。由于文獻[17]的方法沒有考慮負載平衡，且算法求解精度較低，影響了系統的傳輸速率；而在本文改進方法下，初始狀態在所有網絡中的系統傳輸速度為43.5 Mpbs，低于文獻[17]，高于文獻[18]，但在業務增加過程中，當接入業務數為65時，系統傳輸速率已變為最大，并一直保持最大的狀態，說明提出的改進算法在分配異構網絡資源時，能夠保證系統的最大的傳輸速率。

6 結束語

為改善異構無線網絡的接入質量，優化異構網絡間的負載均衡和系統傳輸速率，建立了多目標優化模型，然后采用改進的MOEA/D算法進行求解，通過構造雙曲線函數對MOP進行分解，并控制權重向量與坐標軸的距離來調整個體的支配范圍，同時引入了自適應變異概率和自適應鄰域，進一步提高了收斂性和全局搜索能力。在標準測試函數上的仿真結果表明：提出的改進算法得到了更佳的IGD評價指標和Pareto前沿，不僅平衡了算法的多樣性和收斂性，而且提升了全局搜索能力。將改進的算法應用在異構網絡業務接入控制中，與其它幾種算法相比，表現出了更優的性能，不僅有效地平衡了網絡間的負載，避免出現網絡阻塞，還能保證整個網絡系統為終端用戶業務提供最大的數據傳輸帶寬，從而驗證了改進策略的有效性和優越性。