席 斌，李 帥，侯媛媛

(成都信息工程學院計算機學院，四川成都614000)

0 引言

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

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

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

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

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

圖1 網(wǎng)絡模型

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

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

運營商增加的總體收益:

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

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

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

2 基本粒子群算法

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

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

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

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

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

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

4 尋求用戶與運營商共同滿意的粒子群算法

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

4.1 編碼策略

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

4.2 初始化粒子群

4.3 適應度計算

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

4.4 精英歸檔策略

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

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

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

4.5 粒子速度與位置變換

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

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

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

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

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

4.6 變異策略

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

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

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

5 仿真實驗及分析

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

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

圖2 各算法阻塞率比較

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

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

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

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

6 結(jié)束語

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

［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)絡中基于效用的呼叫接納控制及流量均衡策略［J］.計算機科學，2008，35(9):45-47.

［3］ 李明欣，孫黃山，謝東亮，等.異構(gòu)無線網(wǎng)絡中基于非合作博弈論的資源分配和接入控制［J］.軟件學報，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)絡中基于免疫計算的聯(lián)系會話接納控制［J］.電子學報，2011，39(11):2648-2653.

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