基于效用函數(shù)的異構(gòu)網(wǎng)絡(luò)負(fù)載均衡算法*

郭強(qiáng)， 車玉潔， 張曉萌， 朱若菡

(山東財(cái)經(jīng)大學(xué) 管理科學(xué)與工程學(xué)院，濟(jì)南 250014)

摘要：提出了一種基于效用函數(shù)的異構(gòu)網(wǎng)絡(luò)負(fù)載均衡算法.該算法通過(guò)網(wǎng)絡(luò)參數(shù)的定時(shí)測(cè)量，得到各性能指標(biāo)的效用函數(shù)，經(jīng)過(guò)歸一化和權(quán)重處理，選取重負(fù)載和輕負(fù)載的小區(qū)，并選取資源利用效率低的業(yè)務(wù)終端，通過(guò)終端的轉(zhuǎn)移實(shí)現(xiàn)負(fù)載均衡.仿真分析表明，該算法能夠有效提高網(wǎng)絡(luò)吞吐量，降低網(wǎng)絡(luò)阻塞率，并減少網(wǎng)絡(luò)時(shí)延.

關(guān)鍵詞：負(fù)載均衡；異構(gòu)網(wǎng)絡(luò)；效用函數(shù); 網(wǎng)絡(luò)吞吐量；網(wǎng)絡(luò)阻塞率

doi:10.16055/j.issn.1672-058X.2015.0011.015

收稿日期：2015-02-26；修回日期：2015-06-02.

基金項(xiàng)目：*山東省自然科學(xué)基金(ZR2011FM022).

作者簡(jiǎn)介：郭強(qiáng)(1975-)，男，山東人，博士，副教授，碩士生導(dǎo)師，從事無(wú)線通信網(wǎng)絡(luò)研究.

中圖分類號(hào)：TN929.5文獻(xiàn)標(biāo)志碼：A

未來(lái)的通信網(wǎng)絡(luò)一定是多用接入網(wǎng)絡(luò)并存的異構(gòu)融合網(wǎng)絡(luò).異構(gòu)無(wú)線網(wǎng)絡(luò)的資源管理技術(shù)已成為熱點(diǎn)研究領(lǐng)域，一個(gè)有效的無(wú)線資源管理機(jī)制能夠充分利用有限的資源給用戶提供高質(zhì)量的通信服務(wù).負(fù)載均衡作為其中的關(guān)鍵技術(shù)之一，對(duì)于優(yōu)化網(wǎng)絡(luò)資源的使用，提高網(wǎng)絡(luò)吞吐量和避免網(wǎng)絡(luò)擁塞有著積極的意義[1].

目前，對(duì)于異構(gòu)網(wǎng)絡(luò)負(fù)載均衡的研究很多，實(shí)現(xiàn)負(fù)載均衡的方式也有多種，可以根據(jù)整個(gè)網(wǎng)絡(luò)系統(tǒng)的負(fù)載狀況，通過(guò)業(yè)務(wù)流的轉(zhuǎn)移來(lái)實(shí)現(xiàn)重負(fù)載和輕負(fù)載小區(qū)的網(wǎng)絡(luò)負(fù)載均衡，也可以通過(guò)一定的接入規(guī)則或方案，為新業(yè)務(wù)提供最佳網(wǎng)絡(luò)選擇，避免接入負(fù)載過(guò)重小區(qū)，實(shí)現(xiàn)負(fù)載均衡[2].文獻(xiàn)[3]提出了基于業(yè)務(wù)類型和逗留時(shí)間的負(fù)載均衡算法，它根據(jù)吞吐量門限將小區(qū)的負(fù)載狀態(tài)進(jìn)行分級(jí)，根據(jù)不同負(fù)載狀態(tài)接入不同的終端進(jìn)而實(shí)現(xiàn)負(fù)載均衡.文獻(xiàn)[4]提出了灰關(guān)聯(lián)度負(fù)載均衡算法，將影響負(fù)載均衡的因素構(gòu)建灰關(guān)聯(lián)因子集并進(jìn)行灰關(guān)聯(lián)分析，得到網(wǎng)絡(luò)的關(guān)聯(lián)度，進(jìn)而計(jì)算業(yè)務(wù)流在各網(wǎng)絡(luò)之間的分配比例.這些算法從不同角度實(shí)現(xiàn)了負(fù)載均衡，并且這些算法中，大部分是根據(jù)網(wǎng)絡(luò)負(fù)載狀態(tài)進(jìn)行判斷是否進(jìn)行負(fù)載均衡，對(duì)于負(fù)載狀態(tài)即過(guò)重負(fù)載的門限值，沒有具體的確定方式.在文獻(xiàn)[5]中，提出了基于用戶滿意度的負(fù)載均衡算法，即當(dāng)系統(tǒng)超過(guò)某一門限值時(shí)，把負(fù)載較重小區(qū)的終端移動(dòng)到輕負(fù)載小區(qū)中,但是該方法采用的負(fù)指數(shù)函數(shù)作為終端收益函數(shù)，只是針對(duì)理想狀態(tài)或特殊狀態(tài)的研究，負(fù)指數(shù)分布只是愛爾朗分布的一種退化形式.在負(fù)指數(shù)分布的情況下，網(wǎng)絡(luò)內(nèi)的業(yè)務(wù)可以正常運(yùn)行，但實(shí)際的業(yè)務(wù)流情況卻要復(fù)雜的多.

針對(duì)上述問(wèn)題，提出了基于效用函數(shù)的異構(gòu)網(wǎng)絡(luò)負(fù)載均衡算法，該算法通過(guò)網(wǎng)絡(luò)參數(shù)的定時(shí)測(cè)量，得到各性能指標(biāo)的效用函數(shù)(采用可以更好對(duì)現(xiàn)實(shí)數(shù)據(jù)進(jìn)行擬合的Erlang分布模型)，將其經(jīng)過(guò)歸一化和權(quán)重處理，選取重負(fù)載和輕負(fù)載小區(qū)，并選取資源利用效率低的業(yè)務(wù)終端，通過(guò)業(yè)務(wù)端從重負(fù)載小區(qū)到輕負(fù)載小區(qū)的轉(zhuǎn)移實(shí)現(xiàn)負(fù)載均衡.

1基于效用函數(shù)的負(fù)載均衡算法

基于效用函數(shù)的負(fù)載均衡算法的核心思想：網(wǎng)絡(luò)的負(fù)載狀況和服務(wù)質(zhì)量狀況可以通過(guò)影響負(fù)載均衡性能指標(biāo)的效用值反映出來(lái)，性能指標(biāo)的效用值越大，則表明得到的服務(wù)質(zhì)量越高，反之亦然.為了實(shí)現(xiàn)負(fù)載均衡并且提高用戶終端的服務(wù)質(zhì)量，算法將負(fù)載過(guò)重網(wǎng)絡(luò)里效用較小的終端業(yè)務(wù)切換到重疊覆蓋區(qū)域負(fù)載較輕的網(wǎng)絡(luò)中.

1.1性能指標(biāo)及其效用函數(shù)

未來(lái)無(wú)線網(wǎng)絡(luò)支持多種業(yè)務(wù)，其中包括語(yǔ)音、數(shù)據(jù)、視頻流、網(wǎng)頁(yè)瀏覽以及FTP文件傳輸?shù)?，這些業(yè)務(wù)可以分為實(shí)時(shí)業(yè)務(wù)(RT)和非實(shí)時(shí)業(yè)務(wù)(NRT)兩類.為了分析簡(jiǎn)便，此處主要考慮兩種典型的業(yè)務(wù)類型即實(shí)時(shí)語(yǔ)音業(yè)務(wù)和非實(shí)時(shí)數(shù)據(jù)業(yè)務(wù).在評(píng)價(jià)網(wǎng)絡(luò)的性能時(shí)，語(yǔ)音業(yè)務(wù)主要考察其呼叫阻塞率和掉話率，數(shù)據(jù)業(yè)務(wù)主要考察時(shí)延和丟包率，有效帶寬是兩種業(yè)務(wù)均考慮的因素.效用函數(shù)模型采用文獻(xiàn)[6]的方法，首先假定兩種業(yè)務(wù)的呼叫到達(dá)率分布服從均值為λRT,λNRT的泊松分布，呼叫持續(xù)時(shí)間分別服從1/μRT，1/μN(yùn)RT的指數(shù)分布，占用的數(shù)據(jù)長(zhǎng)度服從θRT，θNRT的指數(shù)分布.兩種業(yè)務(wù)最多可以分別得到NRT，NNRT個(gè)連接，根據(jù)Erlang分布模型，分別可以得到兩種業(yè)務(wù)的呼叫阻塞率為

(1)

另外，為了便于描述，將涉及的部分符號(hào)及含義標(biāo)記于表1.

表1　文中使用的符號(hào)標(biāo)記

其中，負(fù)載承受程度及時(shí)延可以表示為

(2)

(3)

其中，式(3)中的各個(gè)參數(shù)分別指的是實(shí)時(shí)或非實(shí)時(shí)兩種業(yè)務(wù)下的參數(shù).

此處采用網(wǎng)絡(luò)可用帶寬、呼叫阻塞率和傳輸時(shí)延作為網(wǎng)絡(luò)負(fù)載狀況的衡量標(biāo)準(zhǔn)，下面對(duì)這3個(gè)參數(shù)的效用函數(shù)進(jìn)行討論.

網(wǎng)絡(luò)i的可用帶寬的效用函數(shù)可以表示為

(4)

從式(4)中可以看出，網(wǎng)絡(luò)的剩余可用帶寬越大，效用函數(shù)的值也越大.網(wǎng)絡(luò)i的呼叫阻塞率的效用函數(shù)可以表示為

(5)

式(5)為實(shí)時(shí)業(yè)務(wù)呼叫阻塞率的效用函數(shù)，非實(shí)時(shí)業(yè)務(wù)的同理.從式(5)可以看出，網(wǎng)絡(luò)的呼叫阻塞率越小，效用函數(shù)的值越大.網(wǎng)絡(luò)i的傳輸時(shí)延的效用函數(shù)可以表示為

(6)

式(6)為實(shí)時(shí)業(yè)務(wù)傳輸時(shí)延的效用函數(shù)，非實(shí)時(shí)業(yè)務(wù)的同理.從式(6)可以看出，網(wǎng)絡(luò)的傳輸時(shí)延越小，效用函數(shù)的值越大.

1.2重負(fù)載和輕負(fù)載網(wǎng)絡(luò)的選取

在進(jìn)行重負(fù)載和輕負(fù)載網(wǎng)絡(luò)選取時(shí)，需要根據(jù)不同網(wǎng)絡(luò)的總效用值比較來(lái)確定其網(wǎng)絡(luò)負(fù)載狀況.對(duì)已剩余可用帶寬、呼叫阻塞率以及時(shí)延各個(gè)參數(shù)進(jìn)行歸一化處理，讓其取值在(0,1)之間.

(7)

(8)

為了使負(fù)載均衡快速收斂，算法在迭代過(guò)程中需找出全網(wǎng)負(fù)載最重的接入網(wǎng)，選擇其合適的用戶終端切入到其他網(wǎng)絡(luò)中.而網(wǎng)絡(luò)效用能夠體現(xiàn)負(fù)載狀況，因此選擇效用最小的網(wǎng)絡(luò)為重負(fù)載網(wǎng)絡(luò)即待減負(fù)網(wǎng)絡(luò)，將其記為H，則

H=argmin{ U(i)}

(9)

同理，選擇效用值最大的網(wǎng)絡(luò)為輕負(fù)載網(wǎng)絡(luò)即待接入網(wǎng)絡(luò)，將其記為L(zhǎng)，則

L=argmax{U(i)}

(10)

1.3業(yè)務(wù)流的選取

在找出全網(wǎng)負(fù)載最重的網(wǎng)絡(luò)后，需要從此網(wǎng)絡(luò)中選取合適的業(yè)務(wù)流切換到其他接入網(wǎng)中.在選取業(yè)務(wù)流時(shí)，要考慮兩方面的因素：當(dāng)前業(yè)務(wù)流的服務(wù)質(zhì)量狀況；當(dāng)前業(yè)務(wù)流的資源利用效率，即傾向于選擇服務(wù)質(zhì)量體驗(yàn)較低或者信道狀況差的業(yè)務(wù)流切換到其他網(wǎng)絡(luò)以得到更好的服務(wù)質(zhì)量，并停止在重負(fù)載網(wǎng)絡(luò)的資源占用.選擇業(yè)務(wù)流直到重負(fù)載網(wǎng)絡(luò)的效用值和輕負(fù)載網(wǎng)絡(luò)的效用值盡可能接近為止.

1.4算法流程

此處提出一種基于效用函數(shù)的異構(gòu)網(wǎng)絡(luò)均衡算法的流程圖如圖1所示.

步驟1：網(wǎng)絡(luò)管理中心保持實(shí)時(shí)監(jiān)測(cè)各個(gè)網(wǎng)絡(luò)的負(fù)載狀況，當(dāng)達(dá)到預(yù)定時(shí)間時(shí)，觸發(fā)基于效用的負(fù)載均衡算法.設(shè)定預(yù)定時(shí)間觸發(fā)機(jī)制可以在負(fù)載過(guò)重的情況發(fā)生前合理配置資源，一定程度減少過(guò)重負(fù)載情況發(fā)生.

步驟2：管理中心獲取網(wǎng)絡(luò)參數(shù)值，包括實(shí)時(shí)和非實(shí)時(shí)業(yè)務(wù)的數(shù)量等.

步驟3：計(jì)算剩余可用帶寬、呼叫阻塞率和時(shí)延的效用函數(shù)，并進(jìn)行歸一化處理.

步驟4：選擇負(fù)載最重和負(fù)載最輕的網(wǎng)絡(luò)分別作為待減負(fù)網(wǎng)絡(luò)和待接入網(wǎng)絡(luò).

步驟5：在重負(fù)載網(wǎng)絡(luò)中選取合適的業(yè)務(wù)流進(jìn)行切換.

從算法的流程看出，通過(guò)效用函數(shù)的設(shè)計(jì)，網(wǎng)絡(luò)效用和業(yè)務(wù)流的收益可以量化衡量.通過(guò)網(wǎng)絡(luò)和業(yè)務(wù)流的選擇及切換，網(wǎng)絡(luò)的效用和業(yè)務(wù)流的QOS收益逐漸實(shí)現(xiàn)均衡.付出的代價(jià)只是由于算法的運(yùn)行，需要網(wǎng)絡(luò)和用戶端的管理中心實(shí)際執(zhí)行，并交換相應(yīng)的信息和網(wǎng)絡(luò)選擇策略.可以看出，此處提出的算法可以以較小的代價(jià)換取整個(gè)網(wǎng)絡(luò)性能的提升.

圖1　算法流程圖

圖2　異構(gòu)網(wǎng)絡(luò)場(chǎng)景圖

2仿真

首先介紹仿真的評(píng)估模型與參數(shù)設(shè)置，然后對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析.為了對(duì)基于效用的負(fù)載均衡算法的性能進(jìn)行全面的分析和評(píng)價(jià)，采用隨機(jī)游走模型描述異構(gòu)網(wǎng)內(nèi)用戶終端的移動(dòng)規(guī)律.異構(gòu)網(wǎng)絡(luò)的仿真場(chǎng)景如圖2所示.圖2所示的異構(gòu)網(wǎng)絡(luò)場(chǎng)景圖由2個(gè)UMTS網(wǎng)絡(luò)及4個(gè)WLAN網(wǎng)絡(luò)形成交織重疊覆蓋，大量用戶在重疊異構(gòu)覆蓋范圍隨意行走.設(shè)定系統(tǒng)中存在60個(gè)用戶終端，每個(gè)用戶只使用一種業(yè)務(wù)，每種業(yè)務(wù)各20個(gè)用戶.業(yè)務(wù)的分組到達(dá)服從泊松分布，用戶終端同一時(shí)刻只能接入一種網(wǎng)絡(luò)，用戶初始接入按照接入信號(hào)強(qiáng)度準(zhǔn)則進(jìn)行，即根據(jù)用戶終端接收到的接入網(wǎng)絡(luò)的信號(hào)強(qiáng)度，動(dòng)態(tài)選擇信號(hào)強(qiáng)度最大的網(wǎng)絡(luò)接入.用戶終端在異構(gòu)網(wǎng)中，依據(jù)此處提出的基于效用函數(shù)的算法選擇不同的網(wǎng)絡(luò)實(shí)現(xiàn)負(fù)載均衡.表2給出了仿真參數(shù)及其取值.

表2　仿真參數(shù)及數(shù)值

為了驗(yàn)證所提出的基于效用函數(shù)的負(fù)載均衡算法(ULBA)的性能，采用文獻(xiàn)7提出的基于QOS感知的算法(QLBA)作為對(duì)比算法，從實(shí)時(shí)業(yè)務(wù)阻塞率、非實(shí)時(shí)業(yè)務(wù)時(shí)延以及全網(wǎng)吞吐等方面進(jìn)行比較.圖3-5為仿真結(jié)果.其中圖3比較了ULBA和QLBA兩種算法下的實(shí)時(shí)業(yè)務(wù)的阻塞率和業(yè)務(wù)到達(dá)率的關(guān)系.可以看出，隨著呼叫到達(dá)率的增加，由于網(wǎng)絡(luò)資源有限，實(shí)時(shí)業(yè)務(wù)的阻塞率有上升趨勢(shì).但QLBA較新算法ULBA下的阻塞狀況更嚴(yán)重.由此看出，新算法ULBA可以及時(shí)調(diào)節(jié)網(wǎng)絡(luò)間的負(fù)載均衡，給用戶帶來(lái)更好的服務(wù)質(zhì)量.

圖4給出了QLBA和ULBA兩種不同的算法下非實(shí)時(shí)業(yè)務(wù)傳輸時(shí)延的對(duì)比結(jié)果.可以明顯看出，兩種方法下非實(shí)時(shí)業(yè)務(wù)的傳輸時(shí)延均隨著用戶呼叫到達(dá)率的提高而增加，但是新算法ULBA下的時(shí)延相對(duì)QLBA來(lái)說(shuō)更短，讓終端用戶等待的時(shí)間也更短，服務(wù)質(zhì)量更高，能夠說(shuō)明新算法ULBA在縮短時(shí)延方面有更好的性能.圖5給出了QLBA和ULBA兩種算法下網(wǎng)絡(luò)吞吐量的情況，可以看出，當(dāng)業(yè)務(wù)流速率較低時(shí)，兩種算法差異不大，但隨著業(yè)務(wù)流平均速率不斷增加時(shí)，采用ULBA算法使網(wǎng)絡(luò)有更大的吞吐量.

圖3　實(shí)時(shí)業(yè)務(wù)阻塞率

圖4　非實(shí)時(shí)業(yè)務(wù)傳輸時(shí)延

圖5　全網(wǎng)吞吐量

3總結(jié)

提出了一種基于效用函數(shù)的異構(gòu)網(wǎng)絡(luò)均衡算法，該算法通過(guò)網(wǎng)絡(luò)參數(shù)的監(jiān)測(cè)測(cè)量，并通過(guò)預(yù)定時(shí)間觸發(fā)算法，首先獲取各網(wǎng)絡(luò)參數(shù)的相關(guān)信息，得到一些性能指標(biāo)的效用函數(shù)(采用可以更好地對(duì)現(xiàn)實(shí)數(shù)據(jù)進(jìn)行擬合的Erlang分布模型)，經(jīng)過(guò)歸一化和權(quán)重處理，選取重負(fù)載和輕負(fù)載的小區(qū)，并選取服務(wù)質(zhì)量狀況差或資源利用效率低的業(yè)務(wù)終端，通過(guò)終端的轉(zhuǎn)移實(shí)現(xiàn)負(fù)載均衡.仿真分析表明，該算法能夠有效提高網(wǎng)絡(luò)吞吐量，降低了網(wǎng)絡(luò)阻塞率，并減少網(wǎng)絡(luò)時(shí)延.

參考文獻(xiàn)：

[1] CIUBOTARU B,MUNTEAN G M. A Quality-oriented Handover Algorithm for Multimedia Content Delivery to Mobile Users [J]. IEEE Transactions on Broadcasting,2009,55(2): 437-450

[2] ZAHRAN A H,LIANG B. A Generic Framework for Mobility Modeling and Performance Analysis in Next-generation Heterogeneous Wireless Networks [J]. IEEE Communications Magazine,2007,45(9):92-99

[3] 羅俊輝,白光偉,沈航,等.異構(gòu)無(wú)線網(wǎng)絡(luò)終端服務(wù)感知的動(dòng)態(tài)負(fù)載均衡機(jī)制[J].計(jì)算機(jī)科學(xué)，2014,41(6):37-42

[4] 陳曉玉.異構(gòu)無(wú)線網(wǎng)絡(luò)的負(fù)載均衡算法研究[D].南京：南京郵電大學(xué)，2013

[5] 王華東,侯燕,王鳳春.一種適用于 Ad hoc 網(wǎng)絡(luò)的基于概率負(fù)載均衡算法[J].計(jì)算機(jī)應(yīng)用研究，2014,31(3):872-875

[6] 焦毅,易克初,馬懋德,等. 基于服務(wù)質(zhì)量感知的異構(gòu)無(wú)線網(wǎng)絡(luò)負(fù)載均衡算法[J].吉林大學(xué)學(xué)報(bào)，2013,43(3):794-800

[7] 周炯槃,張琳,望育梅，等.通信網(wǎng)理論基礎(chǔ) [M].北京:人民郵電出版社,2009

[8] 劉琪,袁堅(jiān),山秀明，等.3G/WLAN網(wǎng)絡(luò)中基于終端移動(dòng)與業(yè)務(wù)認(rèn)知的動(dòng)態(tài)負(fù)載均衡機(jī)制[J]. 計(jì)算機(jī)學(xué)報(bào)，2010,33(9):1569-1579

[9] 石文孝,張閣,王繼紅,等.基于網(wǎng)格的異構(gòu)無(wú)線網(wǎng)絡(luò)負(fù)載均衡算法[J].吉林大學(xué)學(xué)報(bào)，2013,43(3):788-793

[10] ZUKRI M,JOUABA B,ZEGHLACHE D.A Review on Mobile Management and Vertical Handover Solutions over Heterogeneous Wireless Networks[J]. Computer Communications,2012,35(17):2055-2068

[11] LEE D,HSUEH Y. Bandwidth-reservation Scheme Based on Road Information for Next-generation Cellular Networks [J]. IEEE Transactions on Vehicular Technology,2004,53(1):243-252

[12] 孫建民.無(wú)線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,2006

[13] PIAMRAT K,KSENTINI A,BONNIN J,et al. Radio Resource Management in Emerging Heterogeneous Wireless Networks[J]. Computer Communications,2011,34(9):578-585

[14] 彭燕.凹印機(jī)P2D算法實(shí)現(xiàn)[J].包裝工程：工程版，2015(17)：131-133；138

Load Balancing Algorithm for Heterogeneous Wireless NetworksBased on Utility Function

GUO Qiang,CHE Yu-jie*,ZHANG Xiao-meng,ZHU Ruo-han

(School of management Science and Engineering,Shandong University of Finance and

Economics,Jinan 250014,China)

Abstract：Load balancing algorithm for heterogeneous wireless networks based on utility function is proposed in this paper. Through timing measurements of network parameters,the algorithm firstly gets the utility function of each performance index,and secondly deals with the indexes by normalization and weighting process,then selects the busiest RAN and lightest RAN,and also selects the low QOS utility terminal,finally achieves load balance by transferring terminal. Simulation results show that the proposed algorithm can effectively improve network throughput and reduce network congestion rate and time-delay.

Key words： load balance; heterogeneous network; utility function; network throughout; network congestion rate