潘 甦，張 磊，劉勝美

（1．南京郵電大學(xué)通信與信息工程學(xué)院，江蘇南京210003；2．東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇南京210096）

基于未來負(fù)載預(yù)測(cè)的無線異構(gòu)網(wǎng)絡(luò)自適應(yīng)負(fù)載均衡算法

潘 甦1，2，張 磊1，劉勝美1

（1．南京郵電大學(xué)通信與信息工程學(xué)院，江蘇南京210003；2．東南大學(xué)移動(dòng)通信國(guó)家重點(diǎn)實(shí)驗(yàn)室，江蘇南京210096）

為避免由于網(wǎng)絡(luò)負(fù)載抖動(dòng)而造成的頻繁網(wǎng)絡(luò)選擇，本文為無線異構(gòu)網(wǎng)絡(luò)提出了一種預(yù)測(cè)網(wǎng)絡(luò)未來負(fù)載的自適應(yīng)負(fù)載均衡算法。通過馬爾可夫鏈預(yù)測(cè)負(fù)載狀態(tài)空間的概率，將預(yù)測(cè)到的概率通過負(fù)載趨勢(shì)函數(shù)映射為趨勢(shì)值，利用趨勢(shì)值進(jìn)行網(wǎng)絡(luò)選擇和自適應(yīng)觸發(fā)門限的調(diào)整。仿真結(jié)果表明，該算法能有效降低接入阻塞率及均衡切換次數(shù)。

無線異構(gòu)網(wǎng)絡(luò)；未來負(fù)載預(yù)測(cè)；負(fù)載趨勢(shì)函數(shù)；網(wǎng)絡(luò)選擇；自適應(yīng)門限

0 引 言

隨著寬帶無線接入和移動(dòng)通信技術(shù)的不斷發(fā)展，未來的無線網(wǎng)絡(luò)將會(huì)是由多種不同的無線接入技術(shù)共同組成的能夠滿足用戶的多種業(yè)務(wù)和服務(wù)質(zhì)量需求的異構(gòu)網(wǎng)絡(luò)［1］。網(wǎng)絡(luò)的異構(gòu)融合將成為未來通信網(wǎng)的一個(gè)重要特征，它能實(shí)現(xiàn)網(wǎng)絡(luò)間的負(fù)載均衡，有效提升系統(tǒng)性能以及無線資源的利用率。

無線異構(gòu)網(wǎng)絡(luò)負(fù)載均衡主要通過垂直切換的方式來實(shí)現(xiàn)［2－3］，網(wǎng)絡(luò)在滿足一定觸發(fā)條件時(shí)，如系統(tǒng)的負(fù)載不均衡程度達(dá)到了門限值，將一定數(shù)量的業(yè)務(wù)切換到負(fù)載較輕的網(wǎng)絡(luò)中，從而實(shí)現(xiàn)系統(tǒng)負(fù)載均衡。目前已有很多研究負(fù)載均衡的算法［3－9］，研究集中在兩個(gè)方面：一是網(wǎng)絡(luò)間負(fù)載比較準(zhǔn)則；二是均衡切換的觸發(fā)條件。對(duì)于網(wǎng)絡(luò)間負(fù)載的比較準(zhǔn)則，文獻(xiàn)［4］提出了基于模糊邏輯的網(wǎng)絡(luò)選擇算法來實(shí)現(xiàn)負(fù)載均衡，通過將業(yè)務(wù)類型、可用帶寬等作為模糊輸入，輸出合適的目標(biāo)切換網(wǎng)絡(luò)，實(shí)現(xiàn)負(fù)載均衡；文獻(xiàn)［3］提出了支持服務(wù)質(zhì)量（quality of service，QoS）的負(fù)載均衡算法，考慮影響QoS性能的系統(tǒng)帶寬、丟包率、延遲等參數(shù)，分別給這些參數(shù)賦予權(quán)值并構(gòu)造目標(biāo)函數(shù)，選擇函數(shù)值最大的網(wǎng)絡(luò)作為均衡目標(biāo)網(wǎng)絡(luò)。文獻(xiàn)［5］研究了一種混合動(dòng)態(tài)負(fù)載均衡算法，網(wǎng)絡(luò)可以從相鄰的輕載小區(qū)借用空閑信道，同時(shí)也可以在重疊區(qū)域?qū)⒇?fù)載轉(zhuǎn)移到輕載的小區(qū)中。文獻(xiàn)［6］提出了基于熵權(quán)值和灰度關(guān)聯(lián)分析的負(fù)載均衡算法，通過每個(gè)網(wǎng)絡(luò)的接收信號(hào)強(qiáng)度、可用資源和阻塞率構(gòu)建判斷矩陣，用灰度關(guān)聯(lián)矩陣反映接入網(wǎng)的性能，最后采用熵權(quán)值獲得每個(gè)指標(biāo)的權(quán)重并聯(lián)合關(guān)聯(lián)矩陣對(duì)各異構(gòu)網(wǎng)絡(luò)的性能排序，從而選擇最優(yōu)的目標(biāo)均衡網(wǎng)絡(luò)。文獻(xiàn)［7－9］主要研究了均衡切換的觸發(fā)條件，在文獻(xiàn)［7］所提的算法中，每當(dāng)有新呼叫發(fā)起都會(huì)計(jì)算效用函數(shù)，以使得系統(tǒng)負(fù)載增加最小的網(wǎng)絡(luò)接入新呼叫，因此系統(tǒng)開銷較大；文獻(xiàn)［8］提出了設(shè)定遲滯定時(shí)器的強(qiáng)制切換負(fù)載均衡算法，網(wǎng)絡(luò)負(fù)載達(dá)到設(shè)定門限且超過等待時(shí)間之后，若網(wǎng)絡(luò)依然過載才通過強(qiáng)制切換均衡負(fù)載。文獻(xiàn)［9］提出了自適應(yīng)調(diào)整負(fù)載均衡門限的算法，利用重疊區(qū)域網(wǎng)絡(luò)的負(fù)載最大差值與反應(yīng)當(dāng)前系統(tǒng)負(fù)載狀況的指標(biāo)進(jìn)行比較，若兩網(wǎng)絡(luò)負(fù)載差值大于指標(biāo)值則觸發(fā)均衡算法，這樣的自適應(yīng)門限算法在輕載條件下可以減少不必要的均衡操作。然而，總體而言，這些算法在負(fù)載比較準(zhǔn)則和切換觸發(fā)條件這兩個(gè)問題的解決上都存在不足：對(duì)于網(wǎng)絡(luò)間負(fù)載比較準(zhǔn)則，上述算法用網(wǎng)絡(luò)當(dāng)前負(fù)載值或當(dāng)前負(fù)載加上其他屬性作為負(fù)載均衡的準(zhǔn)則或指標(biāo)，而沒有考慮網(wǎng)絡(luò)未來負(fù)載的變化趨勢(shì)，所以這樣的均衡切換在網(wǎng)絡(luò)未來負(fù)載抖動(dòng)嚴(yán)重時(shí)會(huì)導(dǎo)致頻繁切換；對(duì)于均衡切換的觸發(fā)條件，不設(shè)觸發(fā)門限的均衡每當(dāng)有新呼叫發(fā)起都會(huì)計(jì)算效用函數(shù)［7］，大大增加了系統(tǒng)負(fù)擔(dān)，而設(shè)定遲滯定時(shí)器的觸發(fā)算法不能根據(jù)網(wǎng)絡(luò)情況及時(shí)進(jìn)行負(fù)載均衡。

本文針對(duì)上述問題提出了一種預(yù)測(cè)網(wǎng)絡(luò)未來負(fù)載的自適應(yīng)負(fù)載均衡算法，通過預(yù)測(cè)網(wǎng)絡(luò)負(fù)載處于某種狀態(tài)的概率，計(jì)算出網(wǎng)絡(luò)負(fù)載趨勢(shì)值，將趨勢(shì)值作為網(wǎng)絡(luò)選擇的準(zhǔn)則，從而實(shí)現(xiàn)網(wǎng)絡(luò)負(fù)載均衡，減少不必要的切換。

本文首先描述了網(wǎng)絡(luò)系統(tǒng)模型以及提出負(fù)載預(yù)測(cè)算法；然后在預(yù)測(cè)負(fù)載的基礎(chǔ)上提出基于負(fù)載預(yù)測(cè)的網(wǎng)絡(luò)選擇負(fù)載均衡策略以及自適應(yīng)門限的調(diào)整算法；最后給出仿真結(jié)果以及對(duì)比分析。

1 異構(gòu)網(wǎng)絡(luò)中基于未來負(fù)載預(yù)測(cè)的自適應(yīng)負(fù)載均衡算法

1．1 異構(gòu)網(wǎng)絡(luò)模型

未來一段時(shí)間內(nèi)，覆蓋范圍廣的3G、4G等蜂窩網(wǎng)絡(luò)和覆蓋范圍短的無線局域網(wǎng)（wireless local area network，WLAN）將是主流，因此本文考慮由蜂窩網(wǎng)和WLAN組成的無線異構(gòu)網(wǎng)絡(luò)。如圖1所示，用戶以移動(dòng)模型［10］在系統(tǒng)內(nèi)做隨機(jī)運(yùn)動(dòng)，同時(shí)不斷有新用戶發(fā)起呼叫以及老用戶斷開連接。

假設(shè)系統(tǒng)中有M個(gè)異構(gòu)網(wǎng)絡(luò)，每個(gè)網(wǎng)絡(luò)都支持N種不同的業(yè)務(wù)。在異構(gòu)網(wǎng)絡(luò)中，對(duì)負(fù)載需要一個(gè)統(tǒng)一的定義。對(duì)于FDMA、TDMA、CDMA以及OFDM等不同的接入系統(tǒng)，負(fù)載都可以用業(yè)務(wù)在無線信道上的速率Rb［11］來表示，則k網(wǎng)絡(luò)l業(yè)務(wù)的單個(gè)呼叫負(fù)載loadk，l＝Rb（l），Rb（l）為用戶要求有質(zhì)量保證的業(yè)務(wù)l的比特速率，如話音業(yè)務(wù)為16kbps，視頻業(yè)務(wù)為384kbps。則k網(wǎng)絡(luò)l業(yè)務(wù)的所有負(fù)載為

式中，l＝（1，2，3，…，N）；k＝（1，2，3，…，M）；akl為k網(wǎng)絡(luò)中保持的l業(yè)務(wù)呼叫數(shù)量。

則網(wǎng)絡(luò)k在s時(shí)刻的負(fù)載表達(dá)式為

圖1 異構(gòu)網(wǎng)絡(luò)模型

1．2 負(fù)載預(yù)測(cè)算法

在第1．1節(jié)無線異構(gòu)網(wǎng)絡(luò)模型的基礎(chǔ)上，本文提出了通過預(yù)測(cè)網(wǎng)絡(luò)未來負(fù)載進(jìn)行網(wǎng)絡(luò)選擇及觸發(fā)門限自適應(yīng)調(diào)整的負(fù)載均衡算法。為預(yù)測(cè)網(wǎng)絡(luò)負(fù)載，首先，將網(wǎng)絡(luò)負(fù)載分為不同的狀態(tài)空間；其次，通過馬爾可夫轉(zhuǎn)移函數(shù)計(jì)算出網(wǎng)絡(luò)未來負(fù)載處于各個(gè)狀態(tài)空間的概率；最后，結(jié)合預(yù)測(cè)結(jié)果選擇網(wǎng)絡(luò)以達(dá)到網(wǎng)絡(luò)間的負(fù)載均衡，同時(shí)自適應(yīng)調(diào)整均衡觸發(fā)門限。

基于式（2）網(wǎng)絡(luò)負(fù)載的表達(dá)式，將負(fù)載在s時(shí)刻劃分為輕載、平衡、重載和過度重載4種狀態(tài)，用狀態(tài)空間T＝｛1，2，3，4｝表示。其中狀態(tài)1代表輕載，狀態(tài)2代表平衡，狀態(tài)3代表重載，狀態(tài)4代表過度重載。

為了劃分網(wǎng)絡(luò)負(fù)載的狀態(tài)空間，設(shè)定相應(yīng)的劃分門限。設(shè)網(wǎng)絡(luò)k的最大負(fù)載容量為Cmax，k，定義thdk，1、thdk，2、thdk，3、thdk，4分別為網(wǎng)絡(luò)處于輕載、平衡、重載和過度重載的門限值。各門限按網(wǎng)絡(luò)最大負(fù)載的一定比例取值，比例大小不影響算法本身，不失一般性，令thdk，1＝0．3 Cmax，k，thdk，2＝0．6 Cmax，k，thdk，3＝0．8 Cmax，k，thdk，4＝Cmax，k。若負(fù)載小于輕載門限，即Loadk（s）≤thdk，1，則網(wǎng)絡(luò)k在s時(shí)刻處于輕載狀態(tài)；若thdk，1＜Loadk（s）≤thdk，2，網(wǎng)絡(luò)k在s時(shí)刻處于平衡狀態(tài)；若thdk，2＜Loadk（s）≤thdk，3，網(wǎng)絡(luò)k在s時(shí)刻處于重載狀態(tài)；若thdk，3＜Loadk（s）≤thdk，4，則網(wǎng)絡(luò)k在s時(shí)刻處于過度重載狀態(tài)。

基于以上狀態(tài)空間劃分，任意時(shí)刻網(wǎng)絡(luò)負(fù)載都處于上述4種狀態(tài)之一。而下一時(shí)刻網(wǎng)絡(luò)處于任一狀態(tài)的概率只與當(dāng)前時(shí)刻狀態(tài)有關(guān)，所以網(wǎng)絡(luò)負(fù)載狀態(tài)的變化可以用馬爾可夫鏈描述。為了計(jì)算網(wǎng)絡(luò)負(fù)載狀態(tài)轉(zhuǎn)移概率，首先確定業(yè)務(wù)呼叫的到達(dá)和離去所服從的分布模型，通過計(jì)算轉(zhuǎn)移概率預(yù)測(cè)網(wǎng)絡(luò)負(fù)載狀態(tài)，以便進(jìn)行網(wǎng)絡(luò)選擇及觸發(fā)門限調(diào)整。假設(shè)有n個(gè)終端，對(duì)于k網(wǎng)絡(luò)的l業(yè)務(wù)，各終端對(duì)業(yè)務(wù)l發(fā)起呼叫的概率為pl，不發(fā)起的概率為1－pl。因此，業(yè)務(wù)l的個(gè)呼叫發(fā)起的概率為

若對(duì)于業(yè)務(wù)l每個(gè)呼叫離去的概率為ql，不離去的概率為1－ql，則業(yè)務(wù)l的個(gè)呼叫離去概率為

當(dāng)n很大，pl、ql很小時(shí)有以下近似式

由于泊松分布過程同時(shí)也是平穩(wěn)增量過程，所以由下式可計(jì)算出k網(wǎng)絡(luò)的業(yè)務(wù)l在t時(shí)間內(nèi)增加akl個(gè)呼叫的概率

減少的負(fù)載為

由增加和減少的負(fù)載可以計(jì)算網(wǎng)絡(luò)k負(fù)載的變化為

由式（9）可以計(jì)算出網(wǎng)絡(luò)負(fù)載狀態(tài)的一步轉(zhuǎn)移概率。設(shè)s時(shí)刻，網(wǎng)絡(luò)k處于以上4種狀態(tài)的概率為Pk（s）＝［Pk，1（s），Pk，2（s），Pk，3（s），Pk，4（s）］，則在s＋1時(shí)刻，處于T中各個(gè)狀態(tài)的概率為

圖2為網(wǎng)絡(luò)k的負(fù)載狀態(tài)轉(zhuǎn)移圖，在s和s＋1時(shí)刻有4個(gè)狀態(tài)空間，從某一狀態(tài)可以轉(zhuǎn)移到其他4種狀態(tài)之一，j代表了下一時(shí)刻要轉(zhuǎn)移的狀態(tài)，j∈｛1，2，3，4｝。

圖2 網(wǎng)絡(luò)k的負(fù)載狀態(tài)轉(zhuǎn)移圖

在s時(shí)刻網(wǎng)絡(luò)k的負(fù)載為L(zhǎng)oadk（s），根據(jù)負(fù)載的變化可計(jì)算狀態(tài)轉(zhuǎn)移概率，若網(wǎng)絡(luò)處于狀態(tài)i，則下一時(shí)刻處于狀態(tài)1、2、3、4的轉(zhuǎn)移概率為

式中，i∈｛1，2，3，4｝分別表示網(wǎng)絡(luò)處于輕載、平衡、重載和過度重載狀態(tài)。

將式（7）、式（8）計(jì)算得到的k網(wǎng)絡(luò)l業(yè)務(wù)在t時(shí)間段里呼叫數(shù)增加個(gè)和減少個(gè)的概率代入式（12），可求出各狀態(tài)轉(zhuǎn)移概率，將計(jì)算得到的代入式（11），求得轉(zhuǎn)移矩陣（s），再由式（10）計(jì)算出s＋1時(shí)刻網(wǎng)絡(luò)負(fù)載處于狀態(tài)空間T中各個(gè)狀態(tài)的概率Pk（s＋1）。

通過本節(jié)提出的負(fù)載預(yù)測(cè)算法計(jì)算下一時(shí)刻網(wǎng)絡(luò)負(fù)載處于各個(gè)狀態(tài)的概率，達(dá)到預(yù)測(cè)網(wǎng)絡(luò)負(fù)載狀態(tài)的目的，將預(yù)測(cè)的網(wǎng)絡(luò)負(fù)載狀態(tài)作為網(wǎng)絡(luò)選擇策略的輸入，即通過一定的策略使呼叫接入未來負(fù)載較輕的網(wǎng)絡(luò)中。

2 基于負(fù)載預(yù)測(cè)的網(wǎng)絡(luò)選擇及門限調(diào)整策略

通過第1節(jié)負(fù)載預(yù)測(cè)算法預(yù)測(cè)網(wǎng)絡(luò)未來負(fù)載之后，網(wǎng)絡(luò)選擇策略可以根據(jù)預(yù)測(cè)結(jié)果進(jìn)行相應(yīng)的負(fù)載均衡控制。在網(wǎng)絡(luò)重疊區(qū)域，當(dāng)多個(gè)網(wǎng)絡(luò)滿足呼叫的QoS需求時(shí)，網(wǎng)絡(luò)選擇策略會(huì)考慮讓該呼叫選擇下一時(shí)刻網(wǎng)絡(luò)負(fù)載趨勢(shì)值最小的網(wǎng)絡(luò)接入，即網(wǎng)絡(luò)輕載趨勢(shì)最大的網(wǎng)絡(luò)接入，從而可以均衡各異構(gòu)網(wǎng)絡(luò)間的負(fù)載，并避免頻繁切換現(xiàn)象。

2．1 網(wǎng)絡(luò)負(fù)載趨勢(shì)函數(shù)

本文定義了網(wǎng)絡(luò)負(fù)載趨勢(shì)函數(shù)，它能量化下一時(shí)刻網(wǎng)絡(luò)處于輕載、平衡、重載、過載的趨勢(shì)大小。根據(jù)網(wǎng)絡(luò)當(dāng)前趨勢(shì)值，以及負(fù)載預(yù)測(cè)算法預(yù)測(cè)到的網(wǎng)絡(luò)負(fù)載處于4種狀態(tài)的概率，計(jì)算出下一時(shí)刻的負(fù)載趨勢(shì)值，定義如下：

式中，Ek（s）為k網(wǎng)絡(luò)在s時(shí)刻負(fù)載趨勢(shì)值；該式中分子Pk，4（s＋1）×Pk，3（s＋1）表示網(wǎng)絡(luò)下一時(shí)刻是重載的概率；分母Pk，1（s＋1）×Pk，2（s＋1）表示下一時(shí)刻是輕載的概率；重載概率與輕載概率的比值Pk，4（s＋1）Pk，3（s＋1）／Pk，1（s＋1）Pk，2（s＋1）反映了網(wǎng)絡(luò)未來負(fù)載的趨勢(shì)，值越大表明負(fù)載比較重的趨勢(shì)就越明顯。當(dāng)有新呼叫到達(dá)時(shí)，網(wǎng)絡(luò)選擇策略選擇下一時(shí)刻趨勢(shì)值最小的網(wǎng)絡(luò)接入，從而可以避免接入到未來負(fù)載較重的網(wǎng)絡(luò)中去。由于負(fù)載趨勢(shì)函數(shù)為非減函數(shù)，所以每隔一段時(shí)間對(duì)趨勢(shì)值進(jìn)行復(fù)位。

2．2 網(wǎng)絡(luò)選擇觸發(fā)門限自適應(yīng)調(diào)整

用來實(shí)現(xiàn)負(fù)載均衡的網(wǎng)絡(luò)選擇策略并非一直執(zhí)行，而是需要設(shè)定一個(gè)適當(dāng)?shù)挠|發(fā)門限，以控制均衡帶來的開銷。本文提出的自適應(yīng)觸發(fā)門限可以根據(jù)預(yù)測(cè)到的負(fù)載趨勢(shì)值綜合考慮其他網(wǎng)絡(luò)未來負(fù)載狀況，從而對(duì)自身觸發(fā)門限進(jìn)行動(dòng)態(tài)自適應(yīng)調(diào)整。如該網(wǎng)絡(luò)下一時(shí)刻負(fù)載趨勢(shì)值小于所有網(wǎng)絡(luò)負(fù)載趨勢(shì)值的平均值，即全局平均負(fù)載趨勢(shì)值，說明該網(wǎng)絡(luò)相比其他網(wǎng)絡(luò)負(fù)載輕的趨勢(shì)更明顯，可提高本網(wǎng)絡(luò)下一時(shí)刻的負(fù)載觸發(fā)門限值，以減少下一時(shí)刻由該網(wǎng)絡(luò)向相鄰網(wǎng)絡(luò)轉(zhuǎn)移負(fù)載進(jìn)行切換的次數(shù)，從而在保證系統(tǒng)性能的同時(shí)減少了切換均衡開銷；若該網(wǎng)絡(luò)下一時(shí)刻負(fù)載趨勢(shì)值大于全局平均負(fù)載趨勢(shì)值，說明該網(wǎng)絡(luò)相比其他網(wǎng)絡(luò)負(fù)載重的趨勢(shì)更明顯，可降低本網(wǎng)絡(luò)下一時(shí)刻的觸發(fā)門限，以盡早將自身負(fù)載向其他負(fù)載較輕的網(wǎng)絡(luò)轉(zhuǎn)移，保證網(wǎng)絡(luò)性能以及網(wǎng)絡(luò)間負(fù)載均衡。

為此，定義全局平均負(fù)載趨勢(shì)值為同一時(shí)刻系統(tǒng)中所有網(wǎng)絡(luò)負(fù)載趨勢(shì)值的平均，用來表示，則有

在系統(tǒng)初始化階段，網(wǎng)絡(luò)k的負(fù)載均衡觸發(fā)門限設(shè)為初始值thdk，0，隨后通過預(yù)測(cè)未來負(fù)載算法計(jì)算出各個(gè)網(wǎng)絡(luò)下一時(shí)刻的趨勢(shì)值，以及根據(jù)式（14）計(jì)算全局平均負(fù)載趨勢(shì)值。

自適應(yīng)門限調(diào)整如下：

（1）初始時(shí)，對(duì)于網(wǎng)絡(luò)k的初始觸發(fā)門限thdk，0本文設(shè)為固定值0．4Ck，max。

（2）在s＋1時(shí)刻，網(wǎng)絡(luò)k的負(fù)載趨勢(shì)值為Ek（s＋1），同時(shí)由式（14）計(jì)算出全局平均負(fù)載趨勢(shì)值為avg＿Es＋1。

（3）若Ek（s＋1）＜ε×avg＿Es＋1，則說明此網(wǎng)絡(luò)下一時(shí)刻相對(duì)其他網(wǎng)絡(luò)負(fù)載輕，觸發(fā)負(fù)載均衡策略的門限值（即thdk，0）可以相應(yīng)地提高一個(gè)步長(zhǎng)Δ，減少?gòu)淖陨砭W(wǎng)絡(luò)轉(zhuǎn)移負(fù)載的切換次數(shù)；相反，若，則說明此網(wǎng)絡(luò)下一時(shí)刻相對(duì)其他網(wǎng)絡(luò)負(fù)載重，為了保證盡早轉(zhuǎn)移自身負(fù)載以實(shí)現(xiàn)均衡，門限值相應(yīng)地降低一個(gè)步長(zhǎng)Δ。

2．3 網(wǎng)絡(luò)選擇控制策略

網(wǎng)絡(luò)k每隔一個(gè)時(shí)間周期檢查自身的負(fù)載，若其負(fù)載超過觸發(fā)門限thdk，0，則觸發(fā)負(fù)載預(yù)測(cè)算法對(duì)該網(wǎng)絡(luò)未來負(fù)載狀態(tài)進(jìn)行概率預(yù)測(cè)，從而計(jì)算出下一時(shí)刻該網(wǎng)絡(luò)的負(fù)載趨勢(shì)值?；谪?fù)載預(yù)測(cè)的網(wǎng)絡(luò)選擇流程如圖3所示。

圖3 基于負(fù)載預(yù)測(cè)的網(wǎng)絡(luò)選擇流程圖

從圖3可知，當(dāng)有新的呼叫或切換請(qǐng)求時(shí)，進(jìn)行網(wǎng)絡(luò)可接入性判斷，若系統(tǒng)只有一個(gè)網(wǎng)絡(luò)可以接入則接入該網(wǎng)絡(luò)；若系統(tǒng)有兩個(gè)或以上網(wǎng)絡(luò)可以接入時(shí)，網(wǎng)絡(luò)選擇策略會(huì)比較各網(wǎng)絡(luò)的趨勢(shì)值，選擇趨勢(shì)值最小的網(wǎng)絡(luò)作為目標(biāo)網(wǎng)絡(luò)接入。同時(shí)，根據(jù)負(fù)載趨勢(shì)值來提高或降低觸發(fā)負(fù)載預(yù)測(cè)的均衡算法門限，從而保證負(fù)載均衡的同時(shí)控制均衡開銷，減少不必要的均衡。

3 仿真與結(jié)果分析

系統(tǒng)仿真模型如圖4所示，在通用移動(dòng)通信系統(tǒng)（universal mobile telecommunications system，UMTS）和WLAN的覆蓋范圍內(nèi)，對(duì)于l業(yè)務(wù)不斷有新呼叫按到達(dá)率λl發(fā)起呼叫，同時(shí)系統(tǒng)中l(wèi)業(yè)務(wù)的呼叫按離開率μl離開系統(tǒng)。系統(tǒng)參數(shù)如表1所示。

表1 仿真網(wǎng)絡(luò)參數(shù)表

用戶的呼叫發(fā)起位置均勻分布在網(wǎng)絡(luò)覆蓋面上，運(yùn)動(dòng)方向在0～2π之間服從均勻分布，每隔一段時(shí)間移動(dòng)臺(tái)速度也發(fā)生改變，速度的改變服從如下分布：

式中，v－＝4．3km／h；σv＝3．6km／h。

圖4 系統(tǒng)仿真模型

目前，多數(shù)研究采用多屬性［12－14］的負(fù)載均衡算法，即考慮網(wǎng)絡(luò)價(jià)格和負(fù)載水平等屬性，它們都以網(wǎng)絡(luò)當(dāng)前的屬性值作為均衡標(biāo)準(zhǔn)。

本文提出用于預(yù)測(cè)未來負(fù)載的負(fù)載趨勢(shì)值也可以作為屬性之一，用于多屬性決策。為了清楚顯示本文所提出的算法在負(fù)載均衡上的優(yōu)勢(shì)，在仿真中設(shè)計(jì)了一個(gè)只考慮負(fù)載趨勢(shì)值和價(jià)格的簡(jiǎn)單多屬性決策代價(jià)函數(shù)，當(dāng)然也可以使用復(fù)雜的多屬性方法，如TOPSIS法、AHP算法［15－17］等。

這里只考慮價(jià)格因素以及預(yù)測(cè)的網(wǎng)絡(luò)趨勢(shì)值，定義的代價(jià)函數(shù)為

式中，?、β分別為網(wǎng)絡(luò)價(jià)格和負(fù)載趨勢(shì)值的權(quán)重因子，可根據(jù)實(shí)際情況調(diào)節(jié)；Ck為k網(wǎng)絡(luò)的價(jià)格；Ek（s＋1）為k網(wǎng)絡(luò)負(fù)載趨勢(shì)值。

若沒有進(jìn)行負(fù)載均衡，即式（16）中的β＝0。如圖5所示，隨著系統(tǒng)中用戶不斷增加，由于WLAN價(jià)格便宜，在達(dá)到業(yè)務(wù)需求的條件下用戶優(yōu)先接入WLAN。可以看出WLAN的負(fù)載增加比較迅速，最終處于接近滿負(fù)載的狀態(tài)；而UMTS的負(fù)載僅達(dá)到50%，處于平衡狀態(tài)。如果沒有執(zhí)行負(fù)載均衡，網(wǎng)絡(luò)之間負(fù)載出現(xiàn)了失衡。

圖5 沒有執(zhí)行負(fù)載均衡算法

在相同場(chǎng)景下，執(zhí)行預(yù)測(cè)未來負(fù)載的自適應(yīng)均衡算法，其結(jié)果如圖6所示。圖6（a）為網(wǎng)絡(luò)負(fù)載趨勢(shì)值曲線；圖6（b）為根據(jù)趨勢(shì)值進(jìn)行網(wǎng)絡(luò)選擇的負(fù)載變化圖。

圖6 執(zhí)行預(yù)測(cè)負(fù)載的自適應(yīng)負(fù)載均衡算法

從圖6（a）可以看出，起初兩個(gè)網(wǎng)絡(luò)的負(fù)載都比較輕，未觸發(fā)負(fù)載均衡算法，所以新加入網(wǎng)絡(luò)的用戶按照網(wǎng)絡(luò)價(jià)格優(yōu)先的原則接入合適網(wǎng)絡(luò)。當(dāng)移動(dòng)用戶數(shù)增加到一定數(shù)量時(shí)，在點(diǎn)A處WLAN網(wǎng)絡(luò)負(fù)載先達(dá)到觸發(fā)門限，開始預(yù)測(cè)網(wǎng)絡(luò)未來負(fù)載狀況，從點(diǎn)A到點(diǎn)B看到WLAN的趨勢(shì)值大于UMTS趨勢(shì)值，由于負(fù)載趨勢(shì)值的權(quán)值大于價(jià)格的權(quán)值，所以接入控制會(huì)優(yōu)先選擇代價(jià)值小的UMTS網(wǎng)絡(luò)接入，從而在重疊區(qū)域盡管WLAN價(jià)格便宜，增加的呼叫也會(huì)選擇輕載趨勢(shì)大的UMTS網(wǎng)絡(luò)接入，從圖6（b）中對(duì)應(yīng)區(qū)域看出UMTS的負(fù)載明顯增加。當(dāng)UMTS的負(fù)載增加到觸發(fā)門限后，即對(duì)應(yīng)圖6（a）中的D點(diǎn)，UMTS的負(fù)載趨勢(shì)值也根據(jù)預(yù)測(cè)的結(jié)果增大，從點(diǎn)B到點(diǎn)C，UMTS的趨勢(shì)值大于WLAN的趨勢(shì)值，此時(shí)圖6（b）中WLAN負(fù)載的增長(zhǎng)比UMTS迅速。由圖6（b）可以看出，隨著用戶數(shù)的增加，UMTS和WLAN的負(fù)載在逐漸增加，WLAN負(fù)載最終達(dá)到85%，UMTS負(fù)載最終達(dá)到78%。與圖5比較可知，預(yù)測(cè)未來負(fù)載的負(fù)載均衡算法使得網(wǎng)絡(luò)間負(fù)載達(dá)到了有效均衡。

為了比較預(yù)測(cè)未來負(fù)載的自適應(yīng)負(fù)載均衡算法與現(xiàn)有的遲滯定時(shí)器算法性能的差異，設(shè)定如下一種場(chǎng)景：以圖4系統(tǒng)模型為基礎(chǔ)，在t＝6s、7s、8s3個(gè)時(shí)刻，系統(tǒng)中的用戶數(shù)量激增，接著用戶數(shù)量又恢復(fù)正常。因此，在t＝6s時(shí)，WLAN和UMTS網(wǎng)絡(luò)負(fù)載都達(dá)到了觸發(fā)負(fù)載均衡算法的門限。兩種算法在此情況下的仿真結(jié)果比較如圖7所示。

圖7 兩種負(fù)載均衡算法性能比較

由圖7（a）可以看出，由于用戶數(shù)的激增，t＝6s時(shí)WLAN和UMTS的負(fù)載達(dá)到觸發(fā)門限（初始觸發(fā)門限為thdk，0），執(zhí)行遲滯定時(shí)器的負(fù)載均衡算法。由于遲滯定時(shí)器需要等待2s，在這2s內(nèi)不執(zhí)行均衡切換的操作，而在這個(gè)時(shí)間段中系統(tǒng)的用戶數(shù)還在激增，所以在這2s內(nèi)，WLAN的負(fù)載急劇增加到了極限，即歸一化的負(fù)載為1，而UMTS的價(jià)格比WLAN高，所以負(fù)載增加沒有WLAN快，因此網(wǎng)絡(luò)間的負(fù)載出現(xiàn)了失衡，WLAN負(fù)載飽和意味著用戶的QoS急劇變壞。相同的場(chǎng)景，圖7（b）的仿真結(jié)果說明，當(dāng)網(wǎng)絡(luò)負(fù)載達(dá)到均衡觸發(fā)門限的時(shí)候，網(wǎng)絡(luò)就執(zhí)行預(yù)測(cè)未來負(fù)載的自適應(yīng)均衡算法，避免了用戶都接入到價(jià)格便宜但負(fù)載比較重的WLAN網(wǎng)絡(luò)中，從而有效均衡了網(wǎng)絡(luò)間的負(fù)載，提高了系統(tǒng)中用戶的QoS。

為了比較預(yù)測(cè)未來負(fù)載的負(fù)載均衡算法對(duì)呼叫阻塞率的改善，在不同的到達(dá)率下，比較無負(fù)載均衡算法、遲滯定時(shí)器負(fù)載均衡算法和預(yù)測(cè)未來負(fù)載的自適應(yīng)均衡算法呼叫阻塞率，該仿真場(chǎng)景中到達(dá)率大于離開率。圖8為呼叫阻塞率隨到達(dá)率變化的曲線圖。

圖8 呼叫阻塞率隨到達(dá)率的變化

由圖8可見，隨著呼叫到達(dá)率增大，系統(tǒng)的呼叫阻塞率也在增大，無負(fù)載均衡情況下呼叫阻塞率最大，基于遲滯定時(shí)器的強(qiáng)制切換負(fù)載均衡算法呼叫阻塞率其次，本文提出的預(yù)測(cè)未來負(fù)載狀況的自適應(yīng)負(fù)載均衡算法呼叫阻塞率最小。

圖9為預(yù)測(cè)網(wǎng)絡(luò)未來負(fù)載的自適應(yīng)負(fù)載均衡算法和現(xiàn)有遲滯定時(shí)器強(qiáng)制切換的負(fù)載均衡算法在均衡切換次數(shù)上的比較。從圖中可以看出，預(yù)測(cè)網(wǎng)絡(luò)未來負(fù)載的自適應(yīng)負(fù)載均衡算法在大部分仿真時(shí)間內(nèi)所發(fā)生的均衡切換次數(shù)比強(qiáng)制切換負(fù)載均衡算法發(fā)生的切換次數(shù)要少。所以，預(yù)測(cè)網(wǎng)絡(luò)未來負(fù)載的自適應(yīng)負(fù)載均衡算法能適應(yīng)網(wǎng)絡(luò)未來的負(fù)載抖動(dòng)，有效地減少了系統(tǒng)均衡切換的次數(shù)。

圖9 系統(tǒng)發(fā)生均衡切換次數(shù)的比較

4 結(jié)束語

本文主要研究了一種無線異構(gòu)網(wǎng)絡(luò)中基于網(wǎng)絡(luò)未來負(fù)載預(yù)測(cè)的自適應(yīng)負(fù)載均衡算法，該算法將網(wǎng)絡(luò)負(fù)載劃分為輕載、平衡、重載和過載4種狀態(tài)，由呼叫模型服從的分布計(jì)算出網(wǎng)絡(luò)狀態(tài)轉(zhuǎn)移矩陣，進(jìn)而通過馬爾可夫鏈確定網(wǎng)絡(luò)未來負(fù)載處于各個(gè)狀態(tài)空間的概率。通過本文提出的負(fù)載趨勢(shì)函數(shù)量化成網(wǎng)絡(luò)負(fù)載趨勢(shì)值，由負(fù)載趨勢(shì)值作為均衡指標(biāo)進(jìn)行網(wǎng)絡(luò)選擇、切換控制，同時(shí)利用趨勢(shì)值自適應(yīng)調(diào)整觸發(fā)網(wǎng)絡(luò)選擇策略的門限。達(dá)到了有效避免負(fù)載分布不均衡，進(jìn)一步降低呼叫阻塞率，減少頻繁切換，提高無線資源利用率等目的。

［1］Damnjanovic A，Montojo J，Wei Y B，et al．A survey on 3GPP heterogeneous networks［J］．IEEE Wireless Communications，2011，18（3）：10－21．

［2］Kunarak S，Suleesathira R．Predictive RSS with fuzzy logic based vertical handoff algorithm in heterogeneous wireless networks［C］∥Proc．of the International Symposium on Communications and Information Technologies，2010：1235－1240．

［3］Alam M，Choong S H，Seung M，et al．A load balancing algorithm with QoS support over heterogeneous wireless networks［C］∥Proc．of the Network Operations and Management Symposium，2012：1－4．

［4］Sheng J，Yang Z，Tang L R，et al．A novel load balancing algorithm based on utility functions and fuzzy logic in heterogeneous wireless networks［C］∥Proc．of the International Conference on Fuzzy Systems and Knowledge Discovery，2012：414－418．

［5］Chen Y Y，Qi B，Luo Y T，et al．A hybrid dynamic load balancing algorithm in hetero－geneous wireless packet networks［C］∥Proc．of the International Conference on Fuzzy Systems and Knowledge Discovery，2012：2052－2056．

［6］Sheng J，Qi B，Dong X J，et al．Entropy weight and grey relation analysis based load balancing algorithm in heterogeneous wireless networks［C］∥Proc．of the International Conference on Networking and Mobile Computing，2012：1－4．

［7］Lee S，Sriram K，Golmie N，et al．Vertical handoff decision algorithms for providing optimized performance in heterogeneous wireless networks［J］．IEEE Trans．on Vehi－cular Technology，2009，58（2）：865－881．

［8］Zhou X T．The research of load balance control strategy and algorithm in heterogeneous wireless networks［D］．Nanjing：Nanjing University of Posts and Telecommunications，2011．（周曉團(tuán)．異構(gòu)無線網(wǎng)絡(luò)負(fù)載均衡控制策略與算法研究［D］．南京：南京郵電大學(xué)，2011．）

［9］Zhang Y J，Zhang K，Chi C，et al．An adaptive threshold load balancing scheme for the end－to－end reconfigurable system［J］．Wireless Personal Communication，2008，46（1）：47－65．

［10］Plamen I．User mobility modeling in cellular communications networks［D］．Austria：Vienna University of Technology，1999．

［11］Quoc－thinh N，Nazim A，Yacine G．Novel approach for load balancing in heterogeneous wireless packet networks［C］∥Proc．of the Network Operations and Management Symposium Workshops，2008：26－31．

［12］Lian R R，Tian H，F(xiàn)ei W C，et al．QoS－aware load balancing algorithm for joint group call admission control in heterogeneous networks［C］∥Proc．of the IEEE Vehicular Technology Conference，2012：1－5．

［13］Chai R，Dong X Y，Ma J，et al．An optimal IASA load balancing scheme in heterogeneous wireless networks［C］∥Proc．of the International Conference on Communications and Networking in China，2011：714－719．

［14］Jeounglak H，JiYeon K，Jin－up K，et al．Dynamic load balancing architecture in heterogeneous wireless network environment［C］∥Proc．of the International Symposium on Communications and Information Technology，2009：248－253．

［15］Bernardon D P，Sperandio M，Garcia V J，et al．AHP decisionmaking algorithm to allocate remotely controlled switches in distribution networks［J］．IEEE Trans．on Power Delivery，2011，26（3）：1884－1892．

［16］Fan C Y，Li Q S，Wang C H，et al．Topsis based on grey correlation method and it’s application［C］∥Proc．of the IEEE International Conference on Grey Systems and Intelligent Services，2013：23－25．

［17］Goyette R，Karmouch A．Using AHP／TOPSIS with cost and robustness criteria for virtual network node assignment［C］∥Proc．of the IEEE International Conference on Communications，2012：5885－5889．

E－mail：supan＠njupt．edu．cn

張 磊（1990－），男，碩士研究生，主要研究方向?yàn)橐苿?dòng)通信與無線技術(shù)。

E－mail：zhanglei7655823＠126．com

劉勝美（1977－），女，副教授，博士，主要研究方向?yàn)楫悩?gòu)無線網(wǎng)絡(luò)移動(dòng)性管理、資源管理、運(yùn)動(dòng)預(yù)測(cè)。

E－mail：smliu＠njupt．edu．cn

Adaptive load balancing algorithm based on future load predicting

PAN Su1，2，ZHANG Lei1，LIU Sheng－mei1
（1．College of Telecommunications and Information Engineering，Nanjing University of Posts and Telecommunications，Nanjing 210003，China；2．National Mobile Communications Research Lab，Southeast University，Nanjing 210096，China）

In order to avoid the frequent network selection caused by the load fluctuation of networks，an adaptive load balancing algorithm with the future load predicting is proposed in heterogeneous wireless networks．The probabilities of networks’future load states are predicted by the Markov－chain，then the predicted probabilities are mapped into load tread values by the load trend function．The trend values are used for the network selection and the adaptive adjustment of the trigger threshold．The simulation results show that the proposed algorithm can reduce the access blocking probability and the times of the vertical handover．

wireless heterogeneous networks；future load predicting；load trend function；network selection；adaptive threshold

TN 929．5

A

10．3969／j．issn．1001－506X．2015．06．24

潘 甦（1969－），男，教授，博士，主要研究方向?yàn)闊o線通信與移動(dòng)互聯(lián)網(wǎng)技術(shù)。

1001－506X（2015）06－1384－07

2014－08－27；

2014－10－29；網(wǎng)絡(luò)優(yōu)先出版日期：2014－11－06。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20141106．1240．002．html

國(guó)家自然科學(xué)基金（61271235）；江蘇省科技支撐計(jì)劃（EE2011190）；東南大學(xué)國(guó)家移動(dòng)通信重點(diǎn)實(shí)驗(yàn)室開放基金（2011D07）資助課題