改進MOEA/ D算法的異構網絡接入控制

劉艷君，牛麗平

(1.新鄉學院 計算機與信息工程學院，河南 新鄉 453003；2.河南師范大學 計算機與信息工程學院，河南 新鄉 453007)

0 引 言

接入控制單元是無線異構網絡的核心，當多模終端用戶有業務需要接入網絡時，會對當前網絡的資源進行分析，并將其合理地分配到最適合的網絡中，在保證用戶接入體驗的同時，充分利用整個網絡資源[1-3]。目前，對異構網絡的接入控制研究已經取得了一定的成果，文獻[4]將NSGA-Ⅱ算法應用在異構網絡多業務接入控制中，優化了用戶的傳輸速率和網絡負載均衡，但沒有考慮網絡阻塞的影響，所以始終無法讓異構網絡的資源得到充分利用；文獻[5]利用高斯與戒上型組合隸屬函數對多目標進行模糊處理，再轉化為單目標問題后求出最優解，取得了不錯的效果。由于在異構網絡中的資源占用、阻塞率和負載均衡這3個方面相互沖突和制約，不能同時達到最優，屬于多目標優化問題[6-8]。基于分解的多目標進化算法MOEA/D算法在解決多目標優化問題的優越性，關于MOEA/D算法的改進，學者們也提出了很多策略，如：文獻[9]引入了懲罰機制建立了雙層優化模型，利用改進的多目標優化算法求解出了懲罰期望后悔度的帕累托前沿，但該方法對懲罰系數的控制較難；文獻[10]采用了動態懲罰參數的方法來調節候選解區域，避免邊界個體的遺失問題，但在求解的過程中還會經常出現搜索區域不全面的問題；文獻[11]通過在超平面生成初始權重向量的方式，不僅使解集的分布更加均勻，而且還降低了計算量，但仍有提升的空間。本文在MOEA/D的基礎上，對其采取了進一步的改進策略，大幅提升了算法的性能，并將其應用在異構無線網絡的接入控制中，分別對資源占用、阻塞率和負載均衡3個目標進行優化，能夠更好地充分利用網絡資源，解決異構網絡的業務接入控制問題。

1 建立異構無線網絡數學模型

異構網絡的業務接入控制需要全局考慮不同網絡和不同終端的各種因素，本文對正交頻分復用(OFDM)技術的異構無線網絡接入控制進行研究。假設在異構無線網絡系統中，存在m個不同類型的網絡，第j(1≤j≤m) 個網絡的子載波數為Nj，每個子信道中有Fj個子載波，通過TRU的模型能夠計算出第j個網絡可用的TRU總數Tj表示如下

(1)

其中，TLj表示數據幀的長度；Sj和TSj分別表示OFDM的符號數量和符號周期。

若有n個業務等待接入網絡，其中第i(1≤i≤n) 個業務接入第j個網絡的狀態表示為xij，接入成功xij=1，反之，未接入xij=0。實際上，本文最終求得的最優解形式是一個n×m的0/1矩陣X。

當業務i接入網絡j時，設所需的TRU數為tij，首先將業務i優先分配到距離基站較近和發射功率較大的網絡j，可以占用較少的網絡資源，這樣不僅可以降低整個網絡的負載率，還能夠保證更多的剩余網絡資源[12,13]。業務占用最小網絡資源的優化目標函數表示如下

(2)

為了避免網絡資源的不合理配置，使系統中各網絡的負載達到均衡，本文采用負載率方差對網絡的負載分布情況進行描述，負載率方差越小，則說明網絡負載越均衡，故將負載率方差作為最小優化目標函數，表達式描述如下

(3)

其中，η(j)為當業務i接入網絡j后，已用TRU數占整個網絡TRU總數的比，具體可描述為

(4)

其中，Bj表示業務i接入網絡前已占用的TRU網絡資源數量。

為了給用戶提供更穩定和可靠的服務，提高業務接入網絡的成功率，將最小阻塞率作為優化目標函數，表達式描述如下

(5)

另外，業務所需資源不應大于整個網絡提供的資源總數。同時，每個業務實際上僅可以接入一個網絡，所以可產生兩個約束條件

(6)

(7)

通過上述分析可知，如果以業務占用最小的資源為優化目標，會優先接入距離較近的基站，從而出現不同網絡負載不均衡的問題，持續接入業務后還會出現個別網絡阻塞的現象，拒絕業務的接入，嚴重影響用戶的體驗。如果以網路負載平衡為最小優化目標，業務會優先接入已使用資源最少的網絡，但可能會以消耗更多的TRU資源數為代價，從而影響整個網絡的容量，當業務持續增加后，依然會提前出現網絡阻塞的情況[14]。為此，本文將3個最小優化目標函數結合兩個約束條件進行組合，轉化成多目標優化模型，利用改進的MOEA/D算法進行求解，得到最優的業務接入控制方案。

2 MOEA/D算法及其改進策略

傳統MOEA/D算法的思路是將多目標問題轉化為多個單目標子問題進行求解，較其它常見智能算法在收斂性和復雜度方面均有了明顯的改善，但是也仍然存在一些不足，如：給權重向量隨機分配個體容易導致種群多樣性和收斂性下降。另外，固定的鄰域值不僅會使收斂速度放緩，而且還會影響算法的全局和局部搜索能力[15,16]。針對這兩個方面的缺陷，給出改進策略。

2.1 權重向量與個體的匹配優化

在傳統MOEA/D算法求解的初期，會為權重向量λ隨機分配個體，而這種隨機分配的方法可能會導致將某個權重向量臨近的最優解分配給較遠的權重向量，從而使該權重向量下的適應度變差，所以會出現該個體被其它個體替代的情況，進而使種群的多樣性和收斂性下降。給權重向量λi隨機分配個體的過程如圖1所示。

圖1 給權重向量隨機分配個體過程

從圖1中可看出，在隨機分配的方式下，距離權重向量λ2較近的個體B可能會分配給λ3，而個體C則可能分配給λ2。然后，在隨后的進化過程中，距離權重向量λ3更近的個體F會取代B，距離權重向量λ2更近的個體G會替代C，但實際上B的Pareto支配G，C的Pareto支配F，即B和C的Pareto要比F和G更優，故這種隨機的分配方式會導致算法多樣性和收斂性下降。同時，隨著種群的不斷進化，這個最優解還有被丟棄的可能，從而影響算法的收斂性精度。為此，本文提出了權重向量與個體匹配優化的方法，使權重向量選擇最優解，計算權重向量和所有個體的偏差Δλ，表達式如下

(8)

(9)

其中，F′(X)=(f′1(X),f′2(X),…,f′i(X),…,f′m(X))。f′i(X) 則表示如下

(10)

綜上所述，如果在多個權重向量選取同一個個體X的情況下，把該個體X匹配給ΔX最小的權重向量，通過權重向量與個體的匹配優化，可以形成兩者的最佳對應關系，不僅維持了種群的多樣性，而且還能利于獲得均勻分布的Pareto最優解。

2.2 自適應鄰域

在MOEA/D算法中使用權重向量間的歐式距離定義了個體間鄰域，所以鄰域值是固定的，但這樣會影響到種群的進化。在進化的前期，應盡量用優良的個體對更多劣質的個體進行替換，需要較大的鄰域加快算法的收斂速度，而到了進化的后期，需要適當減小鄰域值，來維持種群的多樣性和提升局部搜索能力。實際上，相鄰個體間存在著共同的基因，通過這種內在關聯能夠促進種群的進化，使優良的基因得到保留。根據種群所處的進化階段和分布情況，本文提出了一種自適應動態調節的鄰域，具體描述如下

(11)

式中：t表示當前的迭代次數；tmax表示設置的最大迭代次數；μ為比例系數；β為比例調整參數；fav表示種群的平均適應度值；fmax則表示最大適應度值。

在進化的前期，由于迭代次數t值較小，鄰域值T能夠保持較大值，突出全局搜索能力；隨著迭代次數t的增加，到了進化的后期，鄰域值T逐漸減小，又突出了算法的局部搜索能力。另外，從適應度值的角度看，如果適應度值分布較均勻，那么個體間的差異就明顯，種群表現出多樣性，此時平均適應度值距離最大值較遠，即arcsin(fav/fmax) 會更趨近于0，鄰域T會被動態增大，就相應提升了算法收斂性。相反，如果適應度值分布較集中，個體間的差異就不大，即arcsin(fav/fmax) 會更趨近于1，鄰域T就會被動態減小，來保持種群的多樣性。

3 改進算法性能測試與對比

為了驗證本文提出的改進算法的性能，利用通用的2目標測試函數ZDT1-ZDT4和3目標測試函數DTLZ1-DTLZ4進行仿真驗證，并分別與標準MOEA/D算法、文獻[10]中的MOEA/D-DPS和文獻[11]中的MOAC/DE算法進行比較。通過反向世代距離[17,18](inverted generation distance，IGD)指標對不同算法運算得到結果進行比較和分析。IGD均值和標準差越小，對應算法的收斂性、分布性和穩定性就越優。

傳統MOEA/D算法的參數：采用模擬二進制交叉，ηc=25，交叉率為1，鄰域值T=15。本文提出的改進算法的參數：比例系數μ為0.5，比例調整參數β為45。設置種群大小為150，最大迭代次數tmax為300。在8個測試函數上分別運行50次，求得對應算法的IGD均值和標準差見表1。

從表1中的運行結果可看出：本文提出的改進算法在8個測試函數上求得的IGD均值均優于傳統MOEA/D算法、MOEA/D-DPS算法、MOAC/DE算法，收斂性和分布性兩個方面均得到了明顯的提升。同時，也得到了最優的IGD標準差，也說明了改進算法具有更佳的穩定性，從而驗證了改進策略的有效性和優越性。

表1 不同算法運行得到的IGD均值和標準差

4 仿真結果與分析

4.1 仿真環境參數設置

為了驗證本文提出的改進算法在處理異構無線網絡接入控制的效果，選擇較為常見的無線網絡TD-LTE、WiMax和LTE-FDD構成仿真網絡模型。仿真網絡模型如圖2所示。

圖2 仿真網絡模型

實驗運行的硬件平臺配置為：Intel Core i7的CPU，主頻率2.8 GHz；8 GB的內存，操作系統采用的是64位的Windows 7，在Matlab 2012a的環境中進行仿真，無線網絡的參數見表2。

表2 3種無線網絡的參數

4.2 仿真結果與對比分析

仿真環境搭建完畢后，預設100個業務，利用本文提出的改進算法求解異構網絡接入控制的多目標優化問題。每當有新業務接入時，通過運算都能夠得到一系列的最優解集，每個解均代表著一種接入方案。為了直觀展示，當接入的業務數量為80個時，最優解集在目標空間的Pareto前沿分布如圖3所示。

圖3 本文改進算法求解得到的Pareto前沿分布(n=80)

從圖3的結果可看出：每個點均代表著多目標優化問題的一個最優解，實際上是0/1矩陣，每個業務與接入網絡的對應關系。每個解在占用TRU資源、阻塞率和負載均衡3個目標函數上表現出了不同的優勢，從這些解中選擇一個兼顧三者的折中方案，并將其應用到仿真環境中，對新接入異構網絡的業務進行控制，并分別與文獻[4]中的NSGA-Ⅱ算法、文獻[5]中的MOC方法、文獻[11]中的MOAC/DE算法得到的結果進行比較，記錄接入業務數從50到100的控制過程，在不同算法下業務占用資源TRU總數和業務阻塞率的變化情況，得到的曲線如圖4、圖5所示。

圖4 不同算法下業務占用TRU的變化情況

圖5 不同算法下業務阻塞率的變化情況

從圖4的結果可以看出：隨著新業務的不斷接入，業務占用TRU總數逐漸攀升，從整體上看，在相同接入業務數量的情況下，本文提出的改進算法占用的資源數均小于其它3種比較算法，使剩余的網絡資源能夠接入更多的業務，當接入業務數量達到85后，其它方法的網絡資源陸續用盡，而在本文方法下當業務數達到95時，仍然有剩余網絡資源可接入新業務。

從圖5的結果可以看出：在文獻[4]中NSGA-Ⅱ算法下，當新業務接入數量達到75個時，就開始出現了業務阻塞的現象，且隨著新業務接入的增加阻塞率不斷攀升，當接入第100個新業務時，阻塞率達到了18%；在文獻[5]中MOC方法下，當新業務接入數量達到80個時，開始出現業務阻塞的現象，當接入第100個新業務時，阻塞率達到了14%；在文獻[11]中MOAC/DE算法下，新業務接入數量達到85個時，開始出現業務阻塞的現象，當接入第100個新業務時，阻塞率達到了11%；在本文改進算法下，當新業務接入數量達到90個時，才開始出現業務阻塞的現象，而且當接入第100個新業務時，阻塞率僅為8%。

隨著接入業務的增加，在4種不同算法下對3種網絡負載進行歸一化處理，得到結果如圖6所示。其中，3條曲線越緊湊說明網絡間的負載越均衡，縱軸的值越小，說明占用的資源越少。

從圖6的仿真結果可看出：在新業務不斷接入的過程中，3個網絡的負載均逐漸攀升，但在本文改進算法下攀升的速度最慢(斜率最小)，說明算法有效控制了網絡的總體資源占用率。在文獻[4]中的NSGA-Ⅱ算法下，如圖6(a)所示，當接入業務數量達到75時，由于LTE-FDD網絡資源耗盡，已經開始滿載，也正是此時開始出現網絡阻塞現象；在文獻[5]中的MOC方法下，如圖6(b)所示，當接入業務數量達到80時，LTE-FDD也開始出現了滿載和阻塞的情況；在文獻[11]中的MOAC/DE算法下，如圖6(c)所示，當接入業務數量達到85時，WiMax網絡出現滿載和阻塞情況；而在本文提出的改進算法下，如圖6(d)所示，由于對資源占用和網絡阻塞的有效控制，當接入業務數量達到90時，WiMax網絡才出現了滿載和阻塞情況。另外，從負載均衡的方面分析，文獻[4]算法下，3種網絡的歸一化負載間距最大，在文獻[5]和文獻[11]算法下，歸一化負載得到了明顯改善，而本文提出的改進算法得到的3種網絡的歸一化負載曲線一致性最強，說明本文改進算法的求解精度更高、性能更強，在控制異構網絡業務接入時，不僅占用最小的網絡資源，還具有最小的阻塞率，也有更優的負載均衡控制能力。

圖6 4種算法下的歸一化負載情況

5 結束語

針對異構無線網絡的業務接入問題，本文從資源占用率、阻塞率和負載均衡3個方面進行考慮建立了多目標優化數學模型，引入了復雜度較低的MOEA/D算法，并通過權重向量與個體的匹配進行優化，改善了種群的多樣性和解的分布。同時，引入自適應鄰域的策略，大大提升了算法的收斂速度和搜索能力。改進的MOEA/D算法在8個標準函數上進行測試，得到的IGD均值和標準差明顯優于其它3種比較算法，驗證了改進策略的有效性和優越性。將改進的MOEA/D算法應用在異構無線網絡的接入控制中進行仿真實驗，通過選取折中的解并與其它3種方法在資源占用、阻塞率和負載均衡進行比較，本文改進算法均得到了最優的結果，其中，本文方法在接入業務數為90個時，網絡才開始出現阻塞的現象，而其它3種算法出現阻塞時對應的接入業務數分別為75、80和85，說明提出的改進算法能夠對網絡資源進行更為合理的分配，改善用戶對業務接入的體驗。