基于多目標(biāo)粒子群算法的異構(gòu)網(wǎng)接入控制

席 斌，李 帥，侯媛媛

(成都信息工程學(xué)院計(jì)算機(jī)學(xué)院，四川成都614000)

0 引言

當(dāng)前，各種無線通信網(wǎng)絡(luò)大量部署。各種無線網(wǎng)絡(luò)的設(shè)計(jì)，是分別針對特定的業(yè)務(wù)類型、用戶需求和特定的通信環(huán)境設(shè)定的。為了充分利用網(wǎng)絡(luò)資源，向用戶提供隨時(shí)隨地的任意業(yè)務(wù)的無線通信服務(wù)，給用戶最好的感觀，各網(wǎng)絡(luò)聯(lián)合進(jìn)行呼入接納控制。

文獻(xiàn)［1］提出了一種業(yè)務(wù)區(qū)分的呼叫準(zhǔn)入算法，并根據(jù)各種業(yè)務(wù)分配不同的優(yōu)先級，同時(shí)動(dòng)態(tài)分配帶寬。文獻(xiàn)［2］在對UMTS和WLAN底層特性分析的前提下，結(jié)合應(yīng)用層為用戶設(shè)定的效用函數(shù)，利用跨層信息提出了一種新的聯(lián)合呼叫接納控制及流量均衡策略。文獻(xiàn)［3］分別建立博弈模型，用博弈論來實(shí)現(xiàn)了網(wǎng)絡(luò)間負(fù)載均衡。文獻(xiàn)［4］提出了基于模糊邏輯的聯(lián)合接納控制。這種接納方式的優(yōu)點(diǎn)是網(wǎng)絡(luò)擴(kuò)展性好，另一優(yōu)點(diǎn)是在各網(wǎng)絡(luò)中并發(fā)執(zhí)行，執(zhí)行速度高，但運(yùn)算較復(fù)雜。

本文提出一種利用多目標(biāo)粒子群優(yōu)化算法的呼入接納控制算法，對呼入請求用戶進(jìn)行批量接入控制，在同時(shí)追求運(yùn)營商和用戶效益最大化中獲取平衡。

1 網(wǎng)絡(luò)模型的建立

網(wǎng)絡(luò)模型如圖 1［5］所示。

圖1 網(wǎng)絡(luò)模型

假設(shè)在Δt內(nèi)，有m個(gè)用戶發(fā)起呼叫用戶的增加的總體收益:

式中，μi是接入網(wǎng)絡(luò)的的延時(shí)，λi是所接入網(wǎng)絡(luò)的傳輸單位數(shù)據(jù)量的價(jià)格，θi是接入網(wǎng)絡(luò)的當(dāng)前阻塞率，φ是傳輸速率。?1、?2和?3分別是延時(shí)、價(jià)格和阻塞率的權(quán)重，是常數(shù)。在此的收益，即用戶的滿意度，即在延時(shí)越小、價(jià)格越低、阻塞率越低和傳輸速率越高時(shí)，用戶的滿意度越大。

運(yùn)營商增加的總體收益:

式中，與式(1)一樣，λi是所接入網(wǎng)絡(luò)的傳輸單位數(shù)據(jù)量的價(jià)格，θi是所接入網(wǎng)絡(luò)的阻塞率。

式(1)、式(2)中θ是阻塞率:

式中，ω代表歸一化資源占用量，即業(yè)務(wù)占用的資源塊個(gè)數(shù)與系統(tǒng)總資源塊個(gè)數(shù)之比，η是歸一化的網(wǎng)絡(luò)負(fù)載。

2 基本粒子群算法

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)，是近年來發(fā)展起來的新進(jìn)化算法。PSO的優(yōu)點(diǎn)是實(shí)現(xiàn)容易、精度高和收斂快，廣泛應(yīng)用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡(luò)訓(xùn)練和模糊系統(tǒng)控制等領(lǐng)域［6］。

粒子群算法中，每個(gè)粒子代表優(yōu)化問題的一個(gè)潛在解，附帶一個(gè)速度可以使粒子在整個(gè)可行解空間上“飛行”，粒子根據(jù)自己和同伴的“飛行”經(jīng)驗(yàn)來調(diào)整自己的飛行速度。每次迭代，粒子通過跟蹤2個(gè)極值來更新自己，一個(gè)是粒子本身經(jīng)歷過的最優(yōu)解，即局部極值;另一個(gè)是整個(gè)群體找到的最優(yōu)解，稱為全局極值gBest。

3 多目標(biāo)粒子群優(yōu)化算法

許多問題都是由相互沖突和影響的多個(gè)目標(biāo)組成，優(yōu)化問題存在的優(yōu)化目標(biāo)超過一個(gè)并需要同時(shí)處理，就成為多目標(biāo)優(yōu)化問題。一般情況下，多目標(biāo)優(yōu)化問題的各個(gè)子目標(biāo)之間是矛盾的，多目標(biāo)優(yōu)化就是為決策者提供一組均勻分配的可能解集，并從中挑選出滿意解。

定義1 Pareto支配 稱一個(gè)向量u=u(u1，u2，…um)支配(或非劣于)向量 v=(v1，v2，…，vm)，當(dāng)且僅當(dāng)對于?i∈(1，2，…，m)，ui＜ vi∧?i∈(1，2，…，m)。

定義2 Pareto最優(yōu) 一個(gè)解稱為多目標(biāo)優(yōu)化問題的Pareto最優(yōu)解，當(dāng)且僅當(dāng)不存在X∈Z使用得:F(X)＜F(X*)。

4 尋求用戶與運(yùn)營商共同滿意的粒子群算法

以下運(yùn)用多目標(biāo)粒子群算法來求解用戶滿意度與運(yùn)營商收益和的最優(yōu)解。

4.1 編碼策略

m個(gè)用戶分別接入不同網(wǎng)絡(luò)的解可用粒子yi=(yi1，yi2，yi3，yi4，…yim)表示［7］。例如，一個(gè)接入的組合解為 y=(y12，y23，y31，…ym2)，表示第 1 個(gè)用戶接入網(wǎng)絡(luò)1中，第2個(gè)用戶接入網(wǎng)絡(luò)3中，第3個(gè)用戶接入網(wǎng)路1中，第m個(gè)用戶接入網(wǎng)絡(luò)2中。

4.2 初始化粒子群

4.3 適應(yīng)度計(jì)算

每個(gè)粒子代表的是一種接入方案，將此接入方案的參數(shù)帶入式(1)和式(2)中，其值的和越大，表示此方案越好。

4.4 精英歸檔策略

將適應(yīng)度大的個(gè)體稱為精英個(gè)體，這些個(gè)體不參加交叉、變異等操作而直接被復(fù)制到下一代群體中去。根據(jù)粒子對應(yīng)的目標(biāo)向量受支配程度來確定粒子的優(yōu)劣度。第t代種群的yi個(gè)體的目標(biāo)向量被同種群的Cti個(gè)目標(biāo)向量所支配，那么個(gè)體yi的序值rank(yi，t)=1+Cti，所有非支配個(gè)體的序值定位1。

精英歸檔策略的思想是將當(dāng)前種群中的精英各地保存到外部檔案庫:當(dāng)外部檔案庫大小小于規(guī)定值，非劣解直接進(jìn)入外部檔案;如果外部檔案庫大小小于或等于規(guī)定值，且新解支配了外部檔案庫的部分個(gè)體，則用新解替換掉那些收支配的檔案庫中的個(gè)體。

外部檔案庫里保存的是最優(yōu)非劣解，直接從外部檔案庫里隨機(jī)取得全局最優(yōu)解。而粒子最優(yōu)解是從粒子當(dāng)前位置和歷史最優(yōu)位置中選擇一個(gè)非劣解作為粒子的最優(yōu)值。如果兩者無支配關(guān)系則保持個(gè)體最優(yōu)值不變。

4.5 粒子速度與位置變換

粒子在解決方案的組合空間中飛行，速度可以分解為分速度，分別為延時(shí)μ、價(jià)格λ和阻塞率θ 3個(gè)屬性。分速度有式(4)變換:

式中，X表示是延時(shí)、價(jià)格還是阻塞率，k為迭代的次數(shù)，c1和 c2為學(xué)習(xí)因子。rand()是介于(0，1)之間的隨機(jī)數(shù)，X為當(dāng)前位置。

w為慣性權(quán)重，為了保持種群多用性而引入的，是自適應(yīng)動(dòng)態(tài)遞減的:

式中，w0為初始慣性權(quán)重，k同式(4)中一樣是當(dāng)前迭代次數(shù)，g為總共迭代次數(shù)，p為遞減系數(shù)。

位置變換:首先計(jì)算k+1代粒子在該維上各屬性的值，利用式(6)將當(dāng)前粒子對應(yīng)的屬性值與相應(yīng)分速度相加得到新的各個(gè)屬性，就可得到新的位置:

4.6 變異策略

多目標(biāo)粒子群算法保持了MOPSO收斂速度快的特點(diǎn)，但是由于收斂過快，搜索范圍受限，常導(dǎo)致收斂到局部Pareto前沿，而非全局Pareto最優(yōu)前沿。于是引入了變異機(jī)制，對粒子位置進(jìn)行小范圍的擾動(dòng)，以增強(qiáng)算法的全局搜索能力。粒子變異概率Pm如式(7)所示:

式中，n為個(gè)體最優(yōu)值不變的代數(shù)，Gexe為當(dāng)前迭代的代數(shù)，G為總迭代次數(shù)。

在搜索初期，粒子不易進(jìn)入局部最優(yōu)，不需對其進(jìn)行變異。隨著迭代的進(jìn)行，單靠粒子根據(jù)自身的知識和社會(huì)行為跳不出局部最優(yōu)。式(7)中粒子變異概率隨著迭代次數(shù)的增加而變大。算法迭代后期，逐漸減小粒子的變異概率。當(dāng)粒子在最后迭代次數(shù)達(dá)到全局最優(yōu)時(shí)，變異概率也變小，這樣避免錯(cuò)誤判斷粒子陷入局部最優(yōu)而對其進(jìn)行變異。變異過程中，隨機(jī)選擇粒子某一維，將其變?yōu)殡S機(jī)接入另一個(gè)基站。例如，隨機(jī)選擇用戶3，本來它是接入基站1的，變?yōu)閷⑵浣尤牖?。

5 仿真實(shí)驗(yàn)及分析

假設(shè)有3G、WiMax和WLAN 3種無線網(wǎng)絡(luò)，同屬一個(gè)運(yùn)營商;終端為多模終端，有分別接入這3種網(wǎng)絡(luò)的能力;每個(gè)終端在某個(gè)時(shí)刻只有一種業(yè)務(wù)。仿真工具為MATLAB和NS2、在NS2仿真環(huán)境下，隨機(jī)產(chǎn)生3種基站位置。有語音、數(shù)據(jù)和IPTV 3種業(yè)務(wù)。

從圖2可以看出，本算法因?yàn)榭紤]了阻塞率因素，其阻塞率總體上并不明顯比其他算法高。用戶量不多的情況下，沒有優(yōu)勢，但隨著用戶數(shù)的增加，其阻塞率的增加相對較小。

圖2 各算法阻塞率比較

在有100個(gè)語音用戶、100個(gè)數(shù)據(jù)用戶和100個(gè)IPTV用戶使用不同呼入接納控制算法接入后的結(jié)果如表1所示。

表1 各接納算法中接入各網(wǎng)絡(luò)的業(yè)務(wù)比較

從表1可見本算法在合適的業(yè)務(wù)接入合適的網(wǎng)絡(luò)這一方面表現(xiàn)最佳。

在用戶滿意度方面，其他呼入接納控制算法基本沒有考慮用戶的接入網(wǎng)絡(luò)價(jià)格，本算法將其作為一個(gè)參考因素。在這一方面，用戶的滿意度會(huì)比較高。

6 結(jié)束語

利用多目標(biāo)粒子群優(yōu)化算法，建立起單一運(yùn)營商的異構(gòu)無線網(wǎng)絡(luò)呼入接納控制機(jī)制，對呼入接納請求進(jìn)行批量控制。通過仿真，證明在將合適的業(yè)務(wù)接入合適的網(wǎng)絡(luò)上有很好的表現(xiàn)，同時(shí)隨著呼入用戶數(shù)量的增多，阻塞率并未很明顯增加，說明此算法可以適應(yīng)高負(fù)載應(yīng)用。相比對每個(gè)呼入請求分別單獨(dú)做出控制，批量控制接納算法具有更好的宏觀性。運(yùn)用多目標(biāo)粒子群算法，由于其收斂性快的特點(diǎn)，運(yùn)算效率較高，同時(shí)引入變異機(jī)制，對粒子進(jìn)行小范圍擾動(dòng)，使算法的全局搜索能力更強(qiáng)。在同時(shí)追求運(yùn)營商的收益和用戶滿意度的最大化上做到好的折中，具有較好實(shí)際應(yīng)用價(jià)值。

［1］ BEJAOUT T，MOKDAD L.Adaptive Hybrid Call Admission Control policy for UMTS with Underlying Tunnel-WLANs Heterogeneous Networks［C］ ∥Proceedings of IEEE International Conference on Communications.Dresden:IEEE，2009:1-5.

［2］ 陳明欣，朱光喜，劉干.異構(gòu)無線網(wǎng)絡(luò)中基于效用的呼叫接納控制及流量均衡策略［J］.計(jì)算機(jī)科學(xué)，2008，35(9):45-47.

［3］ 李明欣，孫黃山，謝東亮，等.異構(gòu)無線網(wǎng)絡(luò)中基于非合作博弈論的資源分配和接入控制［J］.軟件學(xué)報(bào)，2010，21(8):2037-2049.

［4］ OLABISI E F，Chan H A.Fuzzy Logic Based Call Admission Control for Next Generation Wireless Networks［C］∥Cape Town:Wioreless Communications System，2006:574-578.

［5］ KONSTANTINOS E，PARSOPOULOS，MICHAEL N，et al.On the Computation of All Global Minimizers Through Particle Swarm Optimization［J］.IEEE Transaction on Evolutionary Computation，2004，8(3):211-224.

［6］ 朱思峰，劉芳，戚玉濤，等.異構(gòu)無線網(wǎng)絡(luò)中基于免疫計(jì)算的聯(lián)系會(huì)話接納控制［J］.電子學(xué)報(bào)，2011，39(11):2648-2653.

［7］ 須濤，王新環(huán).基于多目標(biāo)粒子群優(yōu)化算法的Web服務(wù)組合［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2010，31(18):4076-4081.