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

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

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

0 引 言

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

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

1 建立異構網絡模型

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

(1)

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

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

(2)

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

(3)

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

(4)

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

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

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

(5)

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

(6)

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

(7)

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

(8)

2 多目標優(yōu)化問題及MOEA/D算法

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

2.1 多目標優(yōu)化問題描述

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

(9)

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

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

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

(10)

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

(11)

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

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

(12)

2.2 MOEA/D算法框架分解

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

(13)

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

3 MOEA/D算法的改進策略

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

3.1 雙曲線聚合函數(shù)

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

(14)

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

(15)

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

(16)

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

(17)

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

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

3.2 自適應因子調整策略

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

3.2.1 自適應變異概率

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

(18)

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

3.2.2 自適應鄰域

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

(19)

3.3 改進算法流程

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

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

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

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

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

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

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

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

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

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

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

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

5 實驗結果與分析

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

表2 異構網絡配置參數(shù)

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

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

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

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

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

5.2 不同算法下系統(tǒng)傳輸速率對比

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

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

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

6 結束語

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