董曉慶，程良倫，陳洪財(cái)，鄭耿忠，謝森林*

(1. 廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州 510006 2. 韓山師范學(xué)院 物理與電子工程學(xué)院，廣東 潮州 521041)

1 引 言

用戶業(yè)務(wù)量及用戶終端數(shù)量近年來呈爆發(fā)性增長態(tài)勢，單一通信網(wǎng)絡(luò)已無法滿足用戶的需求，未來的無線通信網(wǎng)絡(luò)必然是多網(wǎng)絡(luò)共存、融合、優(yōu)勢互補(bǔ)，這也是下一代無線通信網(wǎng)絡(luò)的發(fā)展趨勢[1-2]。多模終端可通過多無線電接入技術(shù)選擇不同的接入網(wǎng)絡(luò)(比如蜂窩網(wǎng)絡(luò)、無線局域網(wǎng)絡(luò)(Wireless Local Area Networks，WLAN)、全球互通微波訪問網(wǎng)絡(luò)(Worldwide Interoperability for Microwave Access，WiMax)等)進(jìn)行數(shù)據(jù)傳輸。在異構(gòu)網(wǎng)絡(luò)重疊覆蓋多用戶多業(yè)務(wù)共存環(huán)境下，如何為用戶選擇合適的接入網(wǎng)絡(luò)及分配帶寬，以保障網(wǎng)絡(luò)系統(tǒng)可靠性并滿足不同用戶的服務(wù)需求，已成為研究熱點(diǎn)[3-4]。

目前異構(gòu)無線網(wǎng)絡(luò)的網(wǎng)絡(luò)接入及資源分配方面已取得一些研究成果。文獻(xiàn)[5]針對帶寬資源受限條件下如何選擇接入網(wǎng)絡(luò)以最大化傳輸速率的問題，提出了一種基于牛頓迭代算法的網(wǎng)絡(luò)選擇方法。該方法首先分別以信息傳輸速率最大化為目標(biāo)及帶寬資源受限為約束對網(wǎng)絡(luò)接入問題進(jìn)行建模，然后通過牛頓迭代算法求得信息傳輸速率最大化的接入網(wǎng)絡(luò)及在該網(wǎng)絡(luò)中所需帶寬資源理論值，把用戶分配到理論值與實(shí)際帶寬需求差值最小的網(wǎng)絡(luò)中，以提高帶寬資源的利用率。文獻(xiàn)[6]提出了一種基于離散粒子群的網(wǎng)絡(luò)選擇接入的多目標(biāo)優(yōu)化方法，該方法首先通過懲罰函數(shù)法將多優(yōu)化目標(biāo)轉(zhuǎn)換為單目標(biāo)，然后利用離散粒子群算法求解，提高了用戶滿意度。文獻(xiàn)[7]分析了無線異構(gòu)網(wǎng)絡(luò)中用戶總信息傳輸速率與網(wǎng)絡(luò)接入及帶寬分配的關(guān)系，將復(fù)雜的多鏈路動(dòng)態(tài)接入建模為系統(tǒng)傳輸速率最大化問題，提出一種支持多鏈路接入的多階段求解方法，從而最大化總用戶信息傳輸速率。文獻(xiàn)[5-7]把提高信息傳輸速率作為目標(biāo)，但忽略了網(wǎng)絡(luò)間的負(fù)載差異，易造成網(wǎng)絡(luò)間負(fù)載不均衡。文獻(xiàn)[8]利用博弈理論構(gòu)建了異構(gòu)無線網(wǎng)絡(luò)中的帶寬資源分配及用戶終端網(wǎng)絡(luò)關(guān)聯(lián)理論模型，提出了可靠通信的接入控制方法以降低用戶接入阻塞率，但非合作博弈中納什均衡的存在性和唯一性難以確定，求解最佳方案難度較大。文獻(xiàn)[9]針對負(fù)載均衡問題，通過構(gòu)建與實(shí)際流量模型相符的網(wǎng)絡(luò)節(jié)點(diǎn)分簇拓?fù)浣Y(jié)構(gòu)，提出了一種基于梯度的負(fù)載均衡非均勻分簇方法，在一定程度上提高了負(fù)載均衡并緩解網(wǎng)絡(luò)擁塞情況。文獻(xiàn)[10]分別分析了用戶的資源占用模型、阻塞率模型及網(wǎng)絡(luò)負(fù)載模型，并建模了總資源占用最小化、業(yè)務(wù)阻塞率最低及網(wǎng)絡(luò)負(fù)載最均衡的多目標(biāo)優(yōu)化模型，并通過最大化滿意度將多目標(biāo)轉(zhuǎn)化為單目標(biāo)，最后利用遺傳算法求解，但該方法在網(wǎng)絡(luò)負(fù)載較重時(shí)，用戶接入阻塞率偏高。文獻(xiàn)[11]針對現(xiàn)有異構(gòu)無線網(wǎng)絡(luò)接入多目標(biāo)優(yōu)化方法大多將多目標(biāo)轉(zhuǎn)化為單目標(biāo)，沒有充分考慮各目標(biāo)相對關(guān)系的問題， 提出一種基于分解的多目標(biāo)進(jìn)化算法，然后通過非支配排序得到最優(yōu)網(wǎng)絡(luò)接入方案，在用戶阻塞率、負(fù)載均衡及資源占用取得較好的折中效果。文獻(xiàn)[9-11]從網(wǎng)絡(luò)的角度對系統(tǒng)性能進(jìn)行優(yōu)化，但忽略了用戶的速率需求。

綜上所述，在異構(gòu)無線網(wǎng)絡(luò)多用戶多業(yè)務(wù)接入環(huán)境下，目前在網(wǎng)絡(luò)側(cè)的負(fù)載均衡、阻塞率方面及用戶側(cè)的速率需求方面均取得一定的研究成果，但聯(lián)合考慮網(wǎng)絡(luò)負(fù)載均衡及用戶速率需求的研究成果還較少。因此，為保證系統(tǒng)通信速率及網(wǎng)絡(luò)間的負(fù)載均衡，本文以系統(tǒng)通信速率及負(fù)載均衡為目標(biāo)，構(gòu)建多目標(biāo)優(yōu)化控制模型，提出一種基于多目標(biāo)優(yōu)化的業(yè)務(wù)接入控制算法，以滿足用戶的服務(wù)質(zhì)量需求及保障網(wǎng)絡(luò)的可靠性。

2 網(wǎng)絡(luò)模型及問題定義

2.1 網(wǎng)絡(luò)模型

如圖1所示，假設(shè)存在N個(gè)異構(gòu)無線網(wǎng)絡(luò)重疊覆蓋(包括蜂窩網(wǎng)絡(luò)、WiMax及WLAN)，M個(gè)多模用戶終端可以根據(jù)自身服務(wù)質(zhì)量(Quality of Service，QoS)需求及網(wǎng)絡(luò)效益選擇接入任一網(wǎng)絡(luò)。載波傳輸方案采用基于多用戶正交頻分復(fù)用技術(shù)(Orthogonal Frequency Division Multiplexing，OFDM)[12-13]，基本的資源分配單元為一個(gè)子時(shí)隙和一個(gè)子信道構(gòu)成的二維資源單元( Two-dimensional Resource Unit，TRU)[10,14]，網(wǎng)絡(luò)k( 1≤k≤N) 能提供的TRU資源數(shù)Tk為：

(1)

其中，Nk為網(wǎng)絡(luò)k的子載波總數(shù)，F(xiàn)k為每個(gè)子信道包含子載波個(gè)數(shù)，TSk為每幀的幀長，SPk為OFDM的符號(hào)周期，Sk為每個(gè)時(shí)隙包含的 符號(hào)個(gè)數(shù)。

令Xjk表示用戶j的網(wǎng)絡(luò)接入情況，若用戶接入網(wǎng)絡(luò)k，則Xjk等于1，否則為0。因此用戶終端的網(wǎng)絡(luò)接入情況可表示為一個(gè)M×N的0/1二維矩陣，如公式(2)。

(2)

2.1.1 系統(tǒng)負(fù)載率模型

設(shè)業(yè)務(wù)j接入網(wǎng)絡(luò)k后，需要網(wǎng)絡(luò)提供的TRU資源數(shù)為tjk，那么網(wǎng)絡(luò)k分配給所有用戶的資源數(shù)量為：

(3)

其中，Bk為用戶所占用的網(wǎng)絡(luò)資源。根據(jù)公式(1)中的網(wǎng)絡(luò)可提供資源，可推導(dǎo)出網(wǎng)絡(luò)k的負(fù)載率為：

(4)

2.1.2 傳輸速率模型

網(wǎng)絡(luò)k的信息傳輸速率由接入該網(wǎng)中的所有用戶終端決定，根據(jù)香農(nóng)定理，網(wǎng)絡(luò)k的信息傳輸速率可表示為：

(5)

其中，bjk表示用戶j在網(wǎng)絡(luò)k中分配到的信道帶寬，Sjk、Njk分別表示信號(hào)功率及噪聲功率，ωjk表示用戶j在網(wǎng)絡(luò)k中的效益因子。

圖1 重疊覆蓋的異構(gòu)無線網(wǎng)絡(luò)Fig.1 Overlapping heterogeneous wireless networks

2.2 問題定義

用戶的網(wǎng)絡(luò)接入及帶寬分配影響到系統(tǒng)的傳輸速率及網(wǎng)絡(luò)間負(fù)載，本文從整個(gè)異構(gòu)無線網(wǎng)絡(luò)的角度，通過為用戶選擇合理的接入網(wǎng)絡(luò)及資源分配，使系統(tǒng)獲得最大傳輸速率并保持網(wǎng)絡(luò)間的負(fù)載均衡。因此，本文將目標(biāo)函數(shù)建模為最均衡網(wǎng)絡(luò)負(fù)載及最大化系統(tǒng)傳輸速率。

本文以負(fù)載率方差衡量各異構(gòu)網(wǎng)絡(luò)間負(fù)載均衡程度，負(fù)載率方差最小化表征負(fù)載最均衡，由2.1節(jié)中的負(fù)載率模型，負(fù)載最均衡可表示如下：

(6)

從整個(gè)網(wǎng)絡(luò)的角度，系統(tǒng)傳輸速率為各個(gè)異構(gòu)網(wǎng)絡(luò)獲得的傳輸速率之和，根據(jù)公式(5)網(wǎng)絡(luò)k的傳輸速率，系統(tǒng)傳輸速率最大化可表示如下：

(7)

由公式(6)、(7)，可以推導(dǎo)出以系統(tǒng)傳輸速率最大化及網(wǎng)絡(luò)負(fù)載最均衡為目標(biāo)，以帶寬資源限制作為約束條件的數(shù)學(xué)模型，具體如下：

(8)

其中約束條件1表示接入網(wǎng)絡(luò)k的所有用戶占用資源總和不得超過網(wǎng)絡(luò)k所能提供的總資源，約束條件3表示每個(gè)用戶最多只能接入一個(gè)網(wǎng)絡(luò)。該優(yōu)化模型既考慮了用戶的傳輸速率需求，同時(shí)保證了網(wǎng)絡(luò)間的負(fù)載均衡。

3 接入控制方法

本文在帶寬資源受限條件下，以網(wǎng)絡(luò)負(fù)載最均衡及系統(tǒng)傳輸速率最大化為目標(biāo)，構(gòu)建了如公式(8)所示的多目標(biāo)優(yōu)化模型。對于約束條件的多目標(biāo)優(yōu)化問題，難以利用多項(xiàng)式時(shí)間算法求解，因此，本文基于非支配排序遺傳算法NSGA-Ⅱ求解復(fù)雜的資源分配及網(wǎng)絡(luò)接入問題。

NSGA-Ⅱ利用強(qiáng)大的全局搜索能力較好地解決了多目標(biāo)優(yōu)化問題，其具有進(jìn)化操作規(guī)則的概率性、充分利用適應(yīng)值函數(shù)而不需要其它先驗(yàn)知識(shí)等特點(diǎn)，且在解空間中沿多個(gè)方向并行搜索，不易陷入局部最優(yōu)，適合求解傳統(tǒng)方法難以解決的復(fù)雜優(yōu)化問題。但由于非支配排序算法求得的一組最優(yōu)帕累托解集中不存在一個(gè)可使所有優(yōu)化目標(biāo)同時(shí)最優(yōu)的解，而本文需要求得唯一方案以確定網(wǎng)絡(luò)接入及帶寬資源分配，因此本文對經(jīng)典的非支配排序算法進(jìn)行改進(jìn)，提出了一種折中的決策精選策略對得到的帕累托解進(jìn)行排序。在得到帕累托解集后，該方法通過計(jì)算個(gè)體各個(gè)優(yōu)化目標(biāo)值與對應(yīng)最優(yōu)值的歸一化趨近度，一個(gè)優(yōu)化目標(biāo)對應(yīng)一個(gè)趨近度，并根據(jù)優(yōu)化目標(biāo)的重要性賦予一定的權(quán)重；最后將同一個(gè)體所有優(yōu)化目標(biāo)對應(yīng)的趨近度相加以表征該個(gè)體對最優(yōu)個(gè)體的趨近度，趨近度越小表示越接近最優(yōu)值，并選擇趨近度最小的個(gè)體作為本文的解。同時(shí)，本文對NSGA-II算法進(jìn)行適應(yīng)性處理，以解決復(fù)雜的資源分配及網(wǎng)絡(luò)接入問題。下面將給出本文改進(jìn)的非支配排序算法關(guān)鍵步驟。

3.1 個(gè)體編碼

個(gè)體表示問題的解決方案，給出用戶終端的接入網(wǎng)絡(luò)及選擇的帶寬資源，一定數(shù)量的個(gè)體組成一個(gè)種群。基于此，本文采用二進(jìn)制方式對個(gè)體進(jìn)行編碼，個(gè)體中基因?qū)?yīng)用戶終端，基因的值表示用戶接入的網(wǎng)絡(luò)及分配到的資源，所以m個(gè)用戶，需要m個(gè)基因。下面給出一個(gè)個(gè)體實(shí)例，假設(shè)在一個(gè)由3個(gè)異構(gòu)無線網(wǎng)絡(luò)重疊覆蓋場景中，每個(gè)網(wǎng)絡(luò)有10個(gè)TRU資源，網(wǎng)絡(luò)中有8個(gè)用戶申請接入，那么需要8個(gè)基因表示8個(gè)用戶的資源分配情況，每個(gè)基因需要用2位表示接入的網(wǎng)絡(luò)，4位表示所選TRU資源，共48位組成了一個(gè)個(gè)體，其編碼方案如圖2所示。

圖2 個(gè)體編碼方式Fig.2 Chromosome coding

3.2 非支配排序

本文的優(yōu)化目標(biāo)包括傳輸速率最大化及負(fù)載最均衡，1個(gè)個(gè)體確定1個(gè)網(wǎng)絡(luò)接入、資源分配方案及對應(yīng)的系統(tǒng)傳輸速率、網(wǎng)絡(luò)間負(fù)載方差目標(biāo)值，本文基于傳輸速率及負(fù)載方差目標(biāo)值進(jìn)行非支配排序，排序方法如下：(1)目標(biāo)值處理：同時(shí)考慮網(wǎng)絡(luò)資源約束及終端接入約束，對于符合約束條件的個(gè)體，取其目標(biāo)值進(jìn)行排序，否則令其傳輸速率為0、網(wǎng)絡(luò)間負(fù)載方差為最大值，以淘汰不符合約束條件的個(gè)體；(2)非支配排序：設(shè)a和b為種群中任意2個(gè)不同個(gè)體，如果滿足a個(gè)體的目標(biāo)值都不比b差，且至少存在一個(gè)目標(biāo)值優(yōu)于個(gè)體b，則稱a為非支配解，b被a所支配；如果兩個(gè)個(gè)體目標(biāo)值相等或互有優(yōu)劣，則a、b互不支配，分配在同一層級(jí)。

3.3 遺傳操作

3.4 決策精選

利用非支配排序算法求得一組最優(yōu)帕累托解，該組解集中不存在一個(gè)可使所有優(yōu)化目標(biāo)同時(shí)最優(yōu)的解，而本文需要求得唯一方案以確定網(wǎng)絡(luò)接入及帶寬資源分配，因此本文提出了一種折中的決策精選策略，該策略如式(9)所示：

(9)

綜上所述，本文基于改進(jìn)的非支配排序方法對染色體進(jìn)行排序，再利用遺傳操作實(shí)現(xiàn)染色體的迭代更新，最后通過決策精選策略優(yōu)選出1個(gè)折中優(yōu)化方案。

4 實(shí)驗(yàn)結(jié)果分析

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

對于優(yōu)化問題，采用凸優(yōu)化理論求解及利用啟發(fā)式智能算法求解是兩類常用的解決方法，文獻(xiàn)[5]基于牛頓迭代算法(Newton Iteration，NI)的網(wǎng)絡(luò)選擇策略及文獻(xiàn)[10]中的多目標(biāo)優(yōu)化控制(Multi-objective Optimization Control，MOC)算法是這兩類方法的典型代表。因此，本章通過仿真將本文基于NSGA-Ⅱ的算法與文獻(xiàn)[5]的NI算法及文獻(xiàn)[10]的MOC算法進(jìn)行對比分析，以測試算法的有效性。假設(shè)3 種目前常見的網(wǎng)絡(luò)重疊覆蓋，如圖 1 所示，網(wǎng)絡(luò) 1、網(wǎng)絡(luò) 2、網(wǎng)絡(luò) 3 分別表示W(wǎng)iMax、多載波無線信息本地環(huán)路網(wǎng)絡(luò)(Multi-Carrier Wireless Information Local Loop，McWiLL)和分時(shí)長期演進(jìn)網(wǎng)絡(luò)(Time Division Long Term Evolution，TD-LTE)，網(wǎng)絡(luò)半徑分別為 3，3，1.5 km，基站位置隨機(jī)生成。WiMax和TD-LTE的網(wǎng)絡(luò)參數(shù)設(shè)置同文獻(xiàn)[15]，McWiLL 網(wǎng)絡(luò)參數(shù)設(shè)置同文獻(xiàn)[16]。

假設(shè)各異構(gòu)無線網(wǎng)絡(luò)中初始業(yè)務(wù)分布隨機(jī)產(chǎn)生，同時(shí)隨機(jī)生成100 個(gè)新到通信業(yè)務(wù)，其中實(shí)時(shí)業(yè)務(wù)帶寬需求隨機(jī)均勻分布在 50～200kb/s，非實(shí)時(shí)業(yè)務(wù)分布在40～140 kb/s，兩種業(yè)務(wù)各約占50%。本文所提算法參數(shù)如下：初始種群隨機(jī)生成，種群規(guī)模P=60，交叉概率pc為0.9，變異概率(pm)為0.1，迭代次數(shù)為200。

4.2 算法性能分析

下面分別對算法的負(fù)載率均衡程度及傳輸速率進(jìn)行對比分析。

4.2.1 歸一化負(fù)載率對比

圖3給出了本文所提算法在3個(gè)網(wǎng)絡(luò)中的負(fù)載均衡狀況，如圖所示，隨著用戶數(shù)量的增加，用戶占用網(wǎng)絡(luò)資源相應(yīng)增加，3個(gè)網(wǎng)絡(luò)負(fù)載率均上升；在負(fù)載率上升的過程中，3條曲線始終保持纏繞，在不同用戶數(shù)下負(fù)載率差距較小，網(wǎng)絡(luò)間負(fù)載始終較為均衡。

圖3 本文算法的歸一化負(fù)載Fig.3 Normalized load of the proposed algorithm

下面進(jìn)一步將本文所提算法與其他兩種算法的歸一化負(fù)載進(jìn)行對比。如圖4(a)所示，本文算法與MOC算法的網(wǎng)絡(luò)負(fù)載率均隨著用戶數(shù)的增加而增加，且各網(wǎng)絡(luò)負(fù)載曲線比較集中，表明網(wǎng)絡(luò)間保持較均衡的狀態(tài)，因?yàn)閮煞N算法都將網(wǎng)絡(luò)間的負(fù)載方差最小化作為優(yōu)化目標(biāo)，使各用戶均衡地接入到各個(gè)網(wǎng)絡(luò)，較好地實(shí)現(xiàn)了負(fù)載均衡；同時(shí)，可看出MOC算法的負(fù)載率稍低于本文算法，因?yàn)镸OC算法將占用最少資源作為優(yōu)化目標(biāo)之一。圖4(b)給出了本文算法與基于NI算法的負(fù)載對比，如圖所示，NI方法在不同用戶數(shù)下各曲線較為松散，網(wǎng)絡(luò)間負(fù)載差距較大，且負(fù)載率相比本文算法大，因?yàn)镹I方法將傳輸速率最大化作為唯一目標(biāo)，始終選擇使傳輸速率最大化的接入網(wǎng)絡(luò)，而忽視了網(wǎng)絡(luò)間的負(fù)載均衡。

(a)與MOC算法對比(a)Comparison with MOC algorithm

(b) 與NI算法對比(b) Comparison with NI algorithm圖4 歸一化負(fù)載對比Fig.4 Normalized load comparison

4.2.2 傳輸速率對比

圖5比較了算法在不同接入用戶數(shù)下的傳輸速率。如圖所示，3種算法在接入用戶數(shù)小于85時(shí)，系統(tǒng)信息傳輸速率與用戶數(shù)呈線性增長關(guān)系，在大于85時(shí)，傳輸速率增長平緩而趨于穩(wěn)定。同時(shí)，由于MOC算法沒有考慮傳輸速率，其各用戶數(shù)下的傳輸速率均明顯低于其它兩種算法。本文算法與NI算法都將傳輸速率最大化作為優(yōu)化目標(biāo)之一，令用戶接入信道條件較好的網(wǎng)絡(luò)，取得了較高的傳輸速率。

圖5 傳輸速率對比Fig.5 Transmission ratecomparison

由上述實(shí)驗(yàn)可知，采用本文提出的基于NSGA-Ⅱ算法的業(yè)務(wù)接入控制策略，在保持網(wǎng)絡(luò)間負(fù)載均衡的情況下，獲得了較高的傳輸速率，顯示出本文所提方法的有效性。

5 結(jié) 論

本文針對異構(gòu)網(wǎng)絡(luò)多用戶多業(yè)務(wù)共存環(huán)境下，用戶期望接入最優(yōu)網(wǎng)絡(luò)以獲取最大的信息傳輸速率，導(dǎo)致網(wǎng)絡(luò)負(fù)載不均衡的問題，構(gòu)建了信息傳輸速率最大化及網(wǎng)絡(luò)負(fù)載最均衡的雙目標(biāo)優(yōu)化模型，并基于NSGA-Ⅱ多目標(biāo)優(yōu)化算法求解該復(fù)雜的業(yè)務(wù)接入問題。實(shí)驗(yàn)結(jié)果表明，與已有的網(wǎng)絡(luò)接入及資源分配方法相比，本文算法兼顧了用戶的傳輸速率需求及系統(tǒng)間的負(fù)載均衡問題，在用戶的QoS需求及網(wǎng)絡(luò)系統(tǒng)性能間取得較好的均衡，具有一定的應(yīng)用價(jià)值。