任付彪, 周 雷, 馬學(xué)森, 魏振春

(合肥工業(yè)大學(xué)計算機與信息學(xué)院,安徽合肥 230009)

事件驅(qū)動Q學(xué)習(xí)在呼叫接入控制中的應(yīng)用

任付彪, 周 雷, 馬學(xué)森, 魏振春

(合肥工業(yè)大學(xué)計算機與信息學(xué)院,安徽合肥 230009)

文章研究了計時報酬方式下最優(yōu)呼叫接入控制問題,建立了系統(tǒng)的連續(xù)時間M arkov決策過程(CTMDP),根據(jù)系統(tǒng)特征引入后狀態(tài)Q值更新方法,給出呼叫接入控制問題基于事件驅(qū)動Q學(xué)習(xí)優(yōu)化算法,并給出一個數(shù)值仿真實例;仿真結(jié)果表明,該算法比Q學(xué)習(xí)具有收斂速度快、存儲空間小的優(yōu)勢;根據(jù)實驗結(jié)果分析了在最優(yōu)策略下業(yè)務(wù)拒絕率與業(yè)務(wù)特征的關(guān)系。

連續(xù)時間M arkov決策過程;事件驅(qū)動 Q學(xué)習(xí);呼叫接入控制

0 引 言

隨著網(wǎng)絡(luò)的日益普及,新業(yè)務(wù)不斷涌現(xiàn)以及業(yè)務(wù)量的迅速增長,網(wǎng)絡(luò)資源需求日益增加。由于網(wǎng)絡(luò)資源的有限性,如何利用現(xiàn)有資源獲取最大收益是每個網(wǎng)絡(luò)運營商需要考慮的問題。呼叫接入控制(Call Admission Control,簡稱CAC)是解決這類問題的主要方法,一直受到廣泛關(guān)注。收益獲取通常采用固定報酬方式[1,2],在理論上,計時報酬方式更為合理,因此本文使用計時報酬代替?zhèn)鹘y(tǒng)的固定報酬,并求解在該方式下報酬最大化的呼叫接入控制問題。

目前,最優(yōu)呼叫接入控制問題通常建模成CTMDP/半Markov決策過程(SMDP)[1-5],主要由于這類問題已有很多求解算法,如策略迭代、線性規(guī)劃等方法能夠很好地解決這類問題[1-3],但這些方法需要確切的模型參數(shù),不利于在線學(xué)習(xí)和實際的應(yīng)用。Q學(xué)習(xí)不依賴于模型,然而該方法求解呼叫接入控制問題時收斂速度慢、存儲空間大[4,5]。關(guān)于排隊系統(tǒng)接入控制問題,文獻[6]研究了一種求解事件驅(qū)動MDP問題的簡單Q學(xué)習(xí)算法,該算法能夠有效地提高收斂速度,減少狀態(tài)存儲空間,因此,本文利用該算法,并根據(jù)呼叫接入控制問題特征引入后狀態(tài)Q值更新方法[7],給出了問題基于CTMDP模型的簡單Q學(xué)習(xí)優(yōu)化算法。由于算法僅適合這類特殊的事件驅(qū)動問題,為了區(qū)別傳統(tǒng)的Q學(xué)習(xí),稱該算法為事件驅(qū)動Q學(xué)習(xí)。

1 問題描述與CTMDP建模

考慮擁有固定帶寬、多類業(yè)務(wù)的單服務(wù)節(jié)點呼叫接入控制問題。假定節(jié)點帶寬為C個單位,業(yè)務(wù)劃分為K類,第i(i=1,2,…,K)類業(yè)務(wù)呼叫到達率服從參數(shù)為λ(i)的獨立泊松分布,接受一個第i類業(yè)務(wù)需要b(i)個單位帶寬,第i類業(yè)務(wù)單位時間獲得報酬(即報酬率)為r(i),離去率服從參數(shù)為μ(i)的指數(shù)分布。

針對上述描述,本文把呼叫接入控制問題建模成CTMDP,定義一個K維向量x=(x(1),x(2),…,x(i),…,x(K))描述上述節(jié)點狀態(tài),其中x(i)為當(dāng)前第i類業(yè)務(wù)的在線個數(shù),系統(tǒng)的狀態(tài)空間為:

事件指某個業(yè)務(wù)到達或離開節(jié)點,假設(shè)任意2個事件不能在同一時刻發(fā)生,可以用一個K元組e=(e(1),e(2),…,e(K))描述事件。其中,元素e(i)=1表示一個i類業(yè)務(wù)到達事件,e(i)=-1時表示一個i類業(yè)務(wù)離開事件,e(i)=0時表示其它。于是事件集合可以表示為:

系統(tǒng)只有在業(yè)務(wù)到達節(jié)點時需要采取行動,假設(shè)行動不需要時間,行動集A={0,1},行動用a表示,其中a=1表示接受業(yè)務(wù),a=0表示拒絕業(yè)務(wù)。當(dāng)業(yè)務(wù)離開節(jié)點時,不需要采取行動,此時默認(rèn)a=0。

由于系統(tǒng)的狀態(tài)空間為S,事件集合為E,行動集合為A,于是平穩(wěn)策略L表示狀態(tài)空間與事件集的笛卡爾積到行動集的一個映射,記L:S×E→A。

系統(tǒng)在狀態(tài) x∈S下,若有事件e∈E發(fā)生,并采取行動 a后,則下一狀態(tài) x′可以由函數(shù)h:S×E×A→S確定,即 x′=h(x,e,a),其表達式為:

假設(shè)t0=0為系統(tǒng)開始時刻,tn表示第n個事件en發(fā)生時刻,則系統(tǒng)在(tn,tn+1]時間段的狀態(tài)為xn,于是系統(tǒng)在這段時間的累積報酬為:

由此可以得到在策略L下的目標(biāo)函數(shù),即系統(tǒng)長期平均報酬為:

其中,x0為初始狀態(tài),由于初始時刻沒有事件發(fā)生,系統(tǒng)直到t1時刻事件e1發(fā)生時才進行決策,因此系統(tǒng)在t1時刻的狀態(tài)仍然為 x0,故[t0,t1]間的累積報酬g(x0)t1與決策L無關(guān)。系統(tǒng)的優(yōu)化目標(biāo)是尋找最優(yōu)策略L使得系統(tǒng)目標(biāo)函數(shù)達到最大。

2 事件驅(qū)動Q學(xué)習(xí)算法及實現(xiàn)

呼叫接入控制問題具有事件驅(qū)動特征,系統(tǒng)決策時刻為事件發(fā)生時刻,事件發(fā)生滿足M arkov特性,在確定的狀態(tài)和事件下,采取特定的行動后狀態(tài)轉(zhuǎn)移是已知的,而且行動選擇較少。本文利用系統(tǒng)特征引入后狀態(tài)Q更新方法,給出了事件驅(qū)動Q學(xué)習(xí)算法求解該問題。

后狀態(tài)Q值更新過程如圖1所示,其中tn、tn+1為決策時刻(即事件en、en+1發(fā)生時刻)。由決策時刻tn到tn+1的過程來說明后狀態(tài)Q值更新,系統(tǒng)在tn時刻會發(fā)生狀態(tài)轉(zhuǎn)移,決策后的狀態(tài)為xn。由此系統(tǒng)經(jīng)過一段時間到達tn+1時刻,此時需要采取行動并更新tn時刻的狀態(tài)Q值。后狀態(tài)Q值更新是指:在tn+1時刻利用決策后的狀態(tài)Q值(即是xn+1的Q值),更新tn時刻決策后的狀態(tài)xn的Q值。

圖1 后狀態(tài)Q值更新過程

因此,解決在決策時刻tn+1的行動選擇和Q值函數(shù)更新具有一般性。系統(tǒng)在該時刻狀態(tài)為xn,若en+1為某個 i類業(yè)務(wù)到達事件,則行動選擇如下:

其中,h(xn,en+1,0)、h(xn,en+1,1)分別表示采取拒絕與接受行動后的系統(tǒng)狀態(tài)。(4)式能利用行動后狀態(tài)Q值函數(shù)大小選擇行動,是因為此時行動只有拒絕和接受這2個狀態(tài),采取行動后的狀態(tài)可由(1)式確定,而且狀態(tài)Q值函數(shù)能通過查找Q值表得到,這充分利用了呼叫接入控制系統(tǒng)的特征。為了避免陷入局部最優(yōu)解,采用ε-greedy策略選擇行動。對于業(yè)務(wù)離開事件,只更新狀態(tài)Q值,并默認(rèn)a=0。選擇行動后觀察下一系統(tǒng)狀態(tài)xn+1。

根據(jù)文獻[8,9],給出該問題平均準(zhǔn)則下的即時差分公式為:

其中,ˉηn為平均報酬的學(xué)習(xí)值,則有:

其中,c(xn)為(tn,tn+1]間的累積報酬,在這段時間內(nèi)系統(tǒng)狀態(tài)為xn,其逗留時間 Δtn=tn+1-tn,則累積報酬為:

于是,可以得到?jīng)Q策時刻tn+1的Q值更新公式為:

其中,γn為學(xué)習(xí)步長,這種狀態(tài)Q值更新方式能有效解決平均準(zhǔn)則下CTMDP[7]。

具體的事件驅(qū)動Q學(xué)習(xí)算法步驟如下:

(1)初始化每個狀態(tài)Q 值,ˉη0=0,設(shè)置學(xué)習(xí)步數(shù) N,用 n記錄學(xué)習(xí)步數(shù),令 n:=0。

(2)觀察tn時刻后系統(tǒng)狀態(tài)xn,等待下一事件en+1發(fā)生,記錄發(fā)生時間 tn+1。計算狀態(tài) xn的逗留時間Δtn,利用(7)式計算累積報酬c(xn)。

(3)如果en+1是某個業(yè)務(wù)到達事件,根據(jù)(4)式采用ε-greedy策略選擇行動a,如果為業(yè)務(wù)離開事件,令行動a=0,觀察確定系統(tǒng)的下一狀態(tài)xn+1。

(4)選擇學(xué)習(xí)步長γn,利用(6)～(8)式更新Q(xn)。

(5)n:=n+1,若 n ＞N,轉(zhuǎn)第(6)步 ;否則 ,轉(zhuǎn)第(2)步。

(6)學(xué)習(xí)結(jié)束,根據(jù)所得狀態(tài)Q值,求解在各狀態(tài)x下,各類業(yè)務(wù)到達事件e發(fā)生時的最優(yōu)行動(業(yè)務(wù)離開不需要決策),從而獲得最優(yōu)策略L。

3 數(shù)值實例和實驗結(jié)果

考慮一個實際呼叫接入控制系統(tǒng)實例,系統(tǒng)的總帶寬C為12個單位,包含3類業(yè)務(wù),各類業(yè)務(wù)參數(shù)見表1所列。設(shè)參數(shù)ε=0.15,各狀態(tài)Q值均為0,初始狀態(tài)為(0,0,0),學(xué)習(xí)步數(shù) N=400萬步。

表1 各類業(yè)務(wù)參數(shù)

本文分別使用事件驅(qū)動Q學(xué)習(xí)和Q學(xué)習(xí)進行模擬仿真。從統(tǒng)計意義上來說,Q學(xué)習(xí)所得策略對于平均報酬要好于事件驅(qū)動Q學(xué)習(xí),這是由于Q學(xué)習(xí)需要的學(xué)習(xí)要素多,學(xué)習(xí)得更充分。2種學(xué)習(xí)算法所得平均報酬變化曲線如圖2所示,這里每學(xué)習(xí)5萬步產(chǎn)生一個策略,根據(jù)所產(chǎn)生策略,模擬實際系統(tǒng)的運行過程(模擬步數(shù)150萬),統(tǒng)計得到該策略的平均報酬。

圖2 2種學(xué)習(xí)對應(yīng)平均報酬變化曲線

從圖2可以看出,2種學(xué)習(xí)算法收斂于同一水平,但與Q學(xué)習(xí)相比,事件驅(qū)動Q學(xué)習(xí)在學(xué)習(xí)較少的步數(shù)時就能得到相對穩(wěn)定的結(jié)果。其原因是事件驅(qū)動Q學(xué)習(xí)只存儲和更新狀態(tài)Q值,而其需要學(xué)習(xí)的狀態(tài)值函數(shù)比Q學(xué)習(xí)少,因此狀態(tài)Q值更新頻繁,學(xué)習(xí)速度快。

表2所列給出了2種Q學(xué)習(xí)算法的收斂步數(shù)、收斂時間、狀態(tài)空間和平均報酬。經(jīng)計算,在該問題中Q學(xué)習(xí)狀態(tài)空間大小為840個,事件驅(qū)動Q學(xué)習(xí)由于不需要把事件擴充為狀態(tài),其狀態(tài)空間大小為140。

在INTEL雙核CPU1.73 GHz,內(nèi)存為1 G的PC機上對2種算法的學(xué)習(xí)用時進行測試。統(tǒng)計結(jié)果顯示,Q學(xué)習(xí)在60×5萬步后結(jié)果趨于穩(wěn)定,平均用時為20.82 s,而事件驅(qū)動Q學(xué)習(xí)在16×5萬步后結(jié)果就趨于穩(wěn)定,平均用時僅為6.60 s,這表明了事件驅(qū)動Q學(xué)習(xí)的有效性。

表2 2種算法相關(guān)結(jié)果比較

表3所列給出了總是接受策略、Q學(xué)習(xí)所得策略和事件驅(qū)動Q學(xué)習(xí)所得策略對應(yīng)長期平均報酬和3類業(yè)務(wù)的拒絕率。由表3可以看出,與總是接受策略相比,2種Q學(xué)習(xí)所得策略對應(yīng)長期平均報酬有明顯提高,說明2種Q學(xué)習(xí)算法均得到了較好的優(yōu)化策略;2種Q學(xué)習(xí)所得策略下各參數(shù)結(jié)果非常接近,這說明2種學(xué)習(xí)算法得到的最優(yōu)策略基本一致,從而進一步表明了事件驅(qū)動Q學(xué)習(xí)的有效性。另外,比較3類業(yè)務(wù)的拒絕率情況發(fā)現(xiàn),在2種Q學(xué)習(xí)所得最優(yōu)策略下,業(yè)務(wù)2的拒絕率相對較大,而業(yè)務(wù)1拒絕率相對較小,這表明采用計時報酬方式下,業(yè)務(wù)拒絕率與業(yè)務(wù)報酬率正相關(guān),與業(yè)務(wù)帶寬和離開率負(fù)相關(guān)。這為網(wǎng)絡(luò)運營商制定合理的報酬率,以獲得最大的網(wǎng)絡(luò)收益提供了參考。

表3 不同策略的長期平均報酬和3類業(yè)務(wù)的拒絕率

4 結(jié)束語

本文結(jié)合后狀態(tài)Q值更新方法,研究了最優(yōu)呼叫接入控制問題基于事件驅(qū)動Q學(xué)習(xí)的優(yōu)化算法。算法既是對Q學(xué)習(xí)在求解該類問題時的改進,也是對文獻[6]給出的簡單Q學(xué)習(xí)算法的擴展。在學(xué)習(xí)過程中,事件驅(qū)動Q學(xué)習(xí)只存儲和更新狀態(tài)的Q值函數(shù),同時采用后狀態(tài)Q值更新方法。從仿真結(jié)果可以看出,該算法能很好地解決這類問題,具有存儲空間小、收斂速度快、模型無關(guān)的優(yōu)點。隨著業(yè)務(wù)類型的不斷增加,呼叫接入控制系統(tǒng)將會更加復(fù)雜,事件驅(qū)動Q學(xué)習(xí)的優(yōu)勢也將會更加突出。另外,本文使用計時報酬代替固定報酬,并根據(jù)仿真結(jié)果分析了最優(yōu)策略下業(yè)務(wù)拒絕率與業(yè)務(wù)特征的關(guān)系,由于帶寬資源有限,計時報酬將會成為一種重要的發(fā)展趨勢,分析這種關(guān)系對網(wǎng)絡(luò)運營商來說具有重要的參考意義。本文討論的是單節(jié)點呼叫接入控制問題,對于多個節(jié)點情況有待進一步研究。

[1] 周亞平,奚宏生,殷保群,等.連續(xù)時間 Markov決策過程在呼叫接入控制中的應(yīng)用[J].控制與決策,2001,16(Z1):795-799.

[2] M arbach P,Tsitsiklis JN.A neuro-dynam ic p rog ramm ing approach to call adm ission control in integ rated service netw ork s:the single link case,Technical Repor t LIDS-P-2402[R/OL].Laboratory for Inform ation and Decision System s,1997.[2008-09-06].http://eprints.kfupm.edu.sa/73464/.

[3] Choi J,Kw on T,Choi Y,et al.Call adm ission con trol for m ultimedia services in mobile cellular netwo rk s:a Markov decision approach[C]//IEEE International Symposium on Com puter Communications,Antibes,2000:594-599.

[4] Senou ciSM,Beylot A,Pujolle G.Call adm ission con trol in cellular netw orks:a reinforcement learning solu tion[J].International Journal of Netw ork Managemen t,2004,14(2):89-103.

[5] Yu Fei,W ong V W S,Leung V C M.A new QoS p rovisioningm ethod for adaptive multimedia in w ireless netw ork s[J].IEEE Transactions on Vehicular Technology,2008,57(3):1899-1909.

[6] 王利存,鄭應(yīng)平.一類事件驅(qū)動馬氏決策過程的Q學(xué)習(xí)[J].系統(tǒng)工程與電子技術(shù),2001,23(4):80-82.

[7] Das T K,GosaviA,M ahadevan S,et al.Solving sem i-M arkov decision problem using average rew ard rein forcement learning[J].M anagem en t Science,1999,45(4):560-574.

[8] 唐 昊,萬海峰,韓江洪,等.基于多Agen t強化學(xué)習(xí)的多站點CSPS系統(tǒng)的協(xié)作look-ahead控制[J].自動化學(xué)報,2010,36(2):289-296.

[9] 岳 峰.一階非線性隨機系統(tǒng)的學(xué)習(xí)優(yōu)化控制[J].合肥工業(yè)大學(xué)學(xué)報:自然科學(xué)版,2010,33(5):679-682.

Application of event driven Q-leaning in call adm ission control

REN Fu-biao, ZHOU Lei, MA Xue-sen, WEIZhen-chun

(School of Compu ter and Inform ation,Hefei University of Technology,H efei 230009,China)

Optimal calladm ission control(CAC)based on tim e com pensation is concerned in this paper.The continuous-time M arkov decision processes(CTMDP)for the system is estab lished,and amethod of afterstate Q-value updating is introduced according to the characteristicsof the system.Then an optimal algorithm of event driven Q-learning is proposed to solve the calladmission control problem.Finally,an examp le of numerical simu lation is given.The sim ulation resu lts show that the p roposed algorithm needs lessmemory and has faster convergence than Q-learning.And on the basisof the experimental resu lts,the relationship between the rejection rate of business and the characteristics of business is analyzed under optimal calladmission policy.

continuous-time Markov decision processes(CTMDP);event driven Q-learning;call admission control(CAC)

TP202.7

A

1003-5060(2011)01-0076-04

10.3969/j.issn.1003-5060.2011.01.018

2010-02-01;

2010-06-28

國家自然科學(xué)基金資助項目(60873003);教育部回國人員科研啟動基金資助項目(2009AKZR 0279);安徽省自然科學(xué)基金資助項目(090412046)和安徽省高校自然科學(xué)研究重點資助項目(KJ2008A 058)

任付彪(1983-),男,安徽界首人,合肥工業(yè)大學(xué)碩士生;

魏振春(1978-),男,寧夏青銅峽人,博士,合肥工業(yè)大學(xué)副教授,碩士生導(dǎo)師.

(責(zé)任編輯 張秋娟)