基于MDP的呼叫接入控制策略優(yōu)化

1、基于mdp的呼叫接入控制策略優(yōu)化陳波(合肥工業(yè)人學(xué)管理學(xué)院)摘要：應(yīng)川馬爾科夫決策過程與性能勢相結(jié)合的方法，將呼叫接入控制中的長期平均報(bào)酬問 題轉(zhuǎn)化為馬爾科夫決策過程中的穩(wěn)態(tài)性能；給出基于長期平均報(bào)酬準(zhǔn)則的呼叫接入控制策略 優(yōu)化算法，該算法將対一個(gè)mxk維向量的整體尋優(yōu)轉(zhuǎn)化為k次m維向量的尋優(yōu)，因而能 克服狀態(tài)維數(shù)過高所帶來的計(jì)算困難，且該算法具有很快的收斂速度；最后運(yùn)用該算法比較 了一個(gè)單節(jié)點(diǎn)、多服務(wù)網(wǎng)絡(luò)在兒種常用的呼叫接入控制策略下的長期平均報(bào)酬。關(guān)鍵詞：markov決策過程；呼叫接入控制；性能勢；平均報(bào)酬中圖分類號：f626.5policy optimization for call a

2、dmission control strategybased on mdpchen bo(school of management, hefei university of technology)abstract: through converting the long-run average reward in call admission control (cac) into the performance potential in markov decision process (mdp) by using the method of mdp combined with performa

3、nce potential, a policy optimization algorithm under the rule of long-run expected average reward is presented. this algorithm transform mxk dimension global optimization into k times of m dimension vector optimization; so the computing complexity brought by high-dimension state decreases evidently

4、and the convergence speed of the algorithm is very fast. at last, the long-run average reward of a single-node and multi-scrviccs network under different cac policies is compared based on the above method.key words: markov decision process; call admission control; performance potential; average rewa

5、rd0引言網(wǎng)絡(luò)通信業(yè)的發(fā)展引發(fā)了研究者對多服務(wù)類排隊(duì)系統(tǒng)實(shí)時(shí)收入管理的研究。當(dāng)系統(tǒng)的資 源有限時(shí)，決策者而臨著在某一或多個(gè)最優(yōu)準(zhǔn)則的前提下如何動(dòng)態(tài)地管理分配系統(tǒng)的資源的 問題。通過制定合理的價(jià)格控制策略從一定程度上可以解決這個(gè)問題，因?yàn)榕c那些傳統(tǒng)的技 術(shù)方案或擴(kuò)張容量相比，價(jià)格能夠更玄接地影響消費(fèi)者的消費(fèi)行為，從而能夠成為一種有效 的、切實(shí)可行的實(shí)施方案。如odlyzko提出的固定計(jì)價(jià)i , mason & varian提出的 4<smart-market pricing"*。岳曉寧等建立的基于交叉擾的線性激勵(lì)價(jià)格策略|3|,更多關(guān)于 網(wǎng)絡(luò)定價(jià)策略可參考文獻(xiàn)4-5 o

6、價(jià)格控制策略因其實(shí)施簡便而受到?jīng)Q策者的青睞。但如果某一部分服務(wù)的流量由于大量新消 費(fèi)者的進(jìn)入或服務(wù)應(yīng)用需求的突發(fā)增加，會(huì)導(dǎo)致網(wǎng)絡(luò)性能的急劇惡化。而在較短時(shí)間內(nèi)改變 價(jià)格是比較困難的，為了維持良好的服務(wù)性能與較高的利潤，這時(shí)就需要對新進(jìn)入的服務(wù)請 求進(jìn)行有選擇的控制，也就是呼叫接入控制。近年來，研究者從不同的方面基于不同的h標(biāo) 對接入控制策略進(jìn)行了廣泛的研究。如dziong & mason從合作博弈論的角度分析了多服務(wù) 網(wǎng)絡(luò)的公平有效的接入控制問題，運(yùn)用值迭代算法分別估計(jì)了網(wǎng)絡(luò)在nash、raffia、修正基金項(xiàng)目：高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20100111120015);高等學(xué)校

7、優(yōu)秀青年人才基金資助項(xiàng)目 (2009sqrz011)作者簡介：陳波41980-),男，博士，副教授，研究方向：決策分析，網(wǎng)絡(luò)服務(wù)控制與優(yōu)化，行為運(yùn)籌. okchenbothomson仲裁模型下的網(wǎng)絡(luò)性能。與傳統(tǒng)的接入控制模型流量最大化與擁塞平等模型相 比，仲裁模型所得出的解具有傳統(tǒng)模型所不具有的公平性。gopal etal.研究在綜合業(yè)務(wù)網(wǎng) 絡(luò)環(huán)境下，棊于網(wǎng)絡(luò)輸出最大化目標(biāo)下的接入控制策略7旳。oda& watanabe研究了一種干 線預(yù)約（trunk reservation, tr）的接入控制策略。liao ef al.研究了負(fù)荷相關(guān)控制策略，與 tr接入控制策略和似，只是比tr策略

8、更特殊的控制策略iio。marbach & tsitsiklis應(yīng)川神經(jīng) 元?jiǎng)討B(tài)規(guī)劃與函數(shù)逼近技術(shù)給出了 tr策略基于仿真的策略優(yōu)化算法。carrizosa et al.研究 一個(gè)用戶到達(dá)可由到達(dá)率與期望服務(wù)時(shí)間來區(qū)分的丟失排隊(duì)網(wǎng)絡(luò)模型，得出最優(yōu)的靜態(tài)接入 控制策略為cp策略|12。上述研究成果都是針對某一個(gè)具體的目標(biāo)提出了某一相關(guān)的cac策略，但卻沒冇考慮 實(shí)際中針對不同的系統(tǒng)狀態(tài)的cac策略優(yōu)化與選擇問題。因而面對多樣化的cac策略， 如何選擇一個(gè)適介當(dāng)前網(wǎng)絡(luò)狀況的cac策略就成為一個(gè)很有意義的研究課題。很顯然，如 果按常規(guī)的考慮系統(tǒng)的總報(bào)酬或某一段時(shí)間的報(bào)酬顯然是沒有意義的，因?yàn)?/p>

9、不同系統(tǒng)的運(yùn)行 周期是不同的。為了解決這個(gè)問題，木文應(yīng)用馬爾科夫決策過程與性能勢相結(jié)合的方法，給 出了基于長期平均報(bào)酬準(zhǔn)則下的cac策略的優(yōu)化算法，并運(yùn)用該方法對多服務(wù)、單節(jié)點(diǎn)網(wǎng) 絡(luò)中幾種常川的cac策略基丁長期平均報(bào)酬準(zhǔn)則下的系統(tǒng)收益進(jìn)行了分析比較。木文的結(jié)構(gòu)如下：第二部分介紹木文研究的理論基礎(chǔ)markov性能勢與mdp平均代 價(jià)模型的最優(yōu)性方程；第三部分介紹給出幾種常用的cac及cac問題的轉(zhuǎn)化；第四部分 給出cac問題基于長期平均報(bào)酬準(zhǔn)則的策略優(yōu)化算法，并通過一個(gè)簡單的算例比較了系統(tǒng) 在兒種不同cac策略下的長期平均報(bào)酬；最后分析了木文的研究結(jié)果與研究展望。1模型1.1基本問題考慮-個(gè)多

10、服務(wù)、單節(jié)點(diǎn)的通信網(wǎng)絡(luò)問題。設(shè)該節(jié)點(diǎn)的總帶寬為b單位，可以同時(shí)向有 m類不同應(yīng)用要求的消費(fèi)者提供服務(wù)，用集合m二表示，不同用戶類對該節(jié)點(diǎn)的 服務(wù)請求為獨(dú)立的泊松過程，笫i類用戶的到達(dá)率為右當(dāng)一個(gè)用戶有服務(wù)請求時(shí)，系統(tǒng)既町以拒絕該用戶，也可以（在帶寬容許時(shí)）接受該用 戶，這便是呼叫接入控制問題。如果接受一位第i類用戶，該類用戶將占用加單位的帶寬， 且會(huì)持續(xù)一段時(shí)間/,其中/服從參數(shù)為為的指數(shù)分布，它與系統(tǒng)中其它任何事件無關(guān)。一 旦系統(tǒng)接受一位/類用戶，系統(tǒng)就將獲口單位的報(bào)酬。對于上述系統(tǒng),我們可用一個(gè)m維向量 心"血,.,加描述其狀態(tài),其中m為系統(tǒng)中 第z類用戶的個(gè)數(shù)。過程的控制行動(dòng)也

11、可以由一個(gè)m維向量v=w,v2,.m描述,其中元 素w的収值只能為（）或1。當(dāng)時(shí)v；=l,表示接受第/類用戶新的服務(wù)請求；當(dāng)v/=0時(shí)，表示 拒絕第z類用戶新的服務(wù)請求。用 歸乩九,加表示用戶的占用帶寬向量，同理有到達(dá)率 向量2,服務(wù)率向量“，報(bào)酬向量/-o對于追求利潤嚴(yán)大化的網(wǎng)絡(luò)提供商，其目標(biāo)就是尋找一個(gè)呼叫接入控制策略使長期平均 報(bào)酬：達(dá)到最大,其中u表示第i類用戶在系統(tǒng)中的平均逗留時(shí)間。在應(yīng)用mdp與性能勢相結(jié)合的方法來比較不同控制策略的長期平均報(bào)酬z前，我們首 先介紹相關(guān)的理論基礎(chǔ)。1.2 markov性能勢考慮一個(gè)正常返、不可約的markov過程,其狀態(tài)空間為q=1,2上，k,無窮小

12、知陣為a = a.un , h.存在一個(gè)有限的行動(dòng)集a。假設(shè)該過程的穩(wěn)態(tài)概率行向量為85t量，c = (l, 1,厶，1)昱k維單位列向最，則冇：ae = 0,兀 0 = 1, 71 a = 0(2)定義穩(wěn)態(tài)性能“為性能函數(shù)./關(guān)于穩(wěn)態(tài)概率兀的期望值：k(3)90 其中兀f表示兩向量的數(shù)-最積。引理1： poisson方程ay = - f +r|e有唯一解y=-af+pc莫中p為任一實(shí)數(shù)，an =(a+e7i)'-en為無窮小矩陣a的群逆13|。定義1： poisson方程ay = - f +r)e的任一解g稱為markov過程 xt, t>0關(guān)于性能函數(shù)/的95 勢能向量,g稱

13、為兀，宀0關(guān)于f在狀態(tài)i時(shí)的勢能。山定義1與引理1可知，g = -af為markov過程；,/>0的一個(gè)勢能向量。引理 2： lyapunov 方程 ad + dat = -(eft - fej 在 v = ey< 一 yer : y e rk | 中有唯解 d ,且可知道：d = egx-gez o其中d稱為markov過程xf,t>0關(guān)于性能函數(shù)f的實(shí)現(xiàn)矩陣，d 中的元素成為實(shí)現(xiàn)因子i。10()山上述論述可知，兩個(gè)狀態(tài)的勢能z差具有確定的意義，即實(shí)現(xiàn)矩陣d中的一個(gè)元素，這與物理學(xué)中的勢能一樣。勢能本身具冇明確的物理意義，關(guān)于現(xiàn)代markov過程的勢理論， 可參見文獻(xiàn)15o

14、1.3 mdp平均代價(jià)模型的最優(yōu)性方程考慮上述markov過程，在每一狀態(tài)轉(zhuǎn)移時(shí)刻有一個(gè)行動(dòng)空間a中的行動(dòng)a作用于該過105 程，木文假設(shè)行動(dòng)數(shù)口是有限的。對于狀態(tài)n (n w g兒其所有可能的作用該狀態(tài)上的行動(dòng)的集合構(gòu)成一個(gè)非空了集as) o策略是一個(gè)序列vo , vi ,厶 , vk : q > a是一個(gè)影射,對于所有neg ,滿足vk ( n) e a ( )。 我們稱策略v,l為平穩(wěn)策略，為簡單起見用v表示平穩(wěn)策略。平穩(wěn)策略v定義了一個(gè)一步 轉(zhuǎn)移概率矩陣為pv的上述markov過程的嵌入馬氏鏈xk,k = a 2,l 。對于給定的策略v ,110系統(tǒng)當(dāng)前狀態(tài)為n ,則系統(tǒng)的下一個(gè)

15、狀態(tài)為m的概率由一步轉(zhuǎn)移概率r(久同決定。在給定的策略v下，系統(tǒng)的穩(wěn)態(tài)概率行向量記為hv =(7t(hv),n(2,v),a ,n(k,v),性能 函數(shù)列向最記為fv = (f(l,v(l) ,l,f(k,v( k):在狀態(tài)n ,如果采取的行動(dòng)為aea(n), 系統(tǒng)的收益為f(n,a) , mdp耍解決的問題即是選擇一個(gè)策略v ,使穩(wěn)態(tài)性能：k(4)h5 達(dá)到最大。cao給出了將mdp方法、攝動(dòng)分析以及markov性能勢相結(jié)合所導(dǎo)出的markov鏈的最 優(yōu)性方程，并給出了基于該最優(yōu)性方程的策略迭代算法及其收斂性證明?？梢宰C明，對于 markov過程，也有類似的最優(yōu)性方程。在給出mdp平均代價(jià)模

16、型的最優(yōu)性方程z前，我們 先給岀兩個(gè)引理，設(shè)策略v與w對應(yīng)的性能函數(shù)分別為n和耳，穩(wěn)態(tài)概率向量分別為兀和兀, 無窮小矩陣分別為a和a，,性能向量分別為/和r o引理 3: t| f =兀 t( a 理+ fag + f)引理4：若向量(/，g+/) (/g+/)巾的每一個(gè)分量均非負(fù)，且其巾至少有一個(gè)分呈為正，則可<n<n1。該引理表明如果要比較兩個(gè)策略下的性能，只需要用到一個(gè)策略f的勢即可。mdp平均代價(jià)模型的最優(yōu)性方程：策略v為最優(yōu)策略，當(dāng)且僅當(dāng)對丁所有的v'wv ,都有下 式成立：ag+f>a'g+f其中向量關(guān)系x > y表示x中的每一個(gè)分量都不小于

17、y中所對應(yīng)的分量17。1.4 cac問題的轉(zhuǎn)化由1.2與1.3的知識我們可知，1.1中所考慮系統(tǒng)的演進(jìn)過程是一個(gè)markov向量過程。設(shè)在某時(shí)刻系統(tǒng)的狀態(tài)為n ,采取的行動(dòng)為a(n,i)(=l,2,l,k,i=/,2,l,m),則該markov 過程的一步轉(zhuǎn)移概率為：jx/ (7 ( a7, /) v ( n)"7 =(a71,l ,巾+1,l , /7m)| m 屮 v (/?)m = ( wi,l , wz -l,l ,m>0p毗='r m r|0其它其屮川)=列兀+砰表示狀態(tài)h的總轉(zhuǎn)移率，矩陣p = rlpn.mu為-步轉(zhuǎn)移概率矩陣。由一步轉(zhuǎn)移概率矩陣可得到該mp

18、的無窮小矩陣a = diag (v(/),v(2),l,v(k)(p-i)，其第(,?)個(gè)元素為：x/ a ( a?,z)m =(w1,l , hi +1,l , hm).|加 wm = ( ni,l , m -1,l , hm) , m>0j 1 11$-陽s(v')ljm = n0其它為了能夠應(yīng)用mdp與性能勢和結(jié)合的方法來比較不同控制策略的長期平均報(bào)酬，我們 將i中的口標(biāo)函數(shù)表示成公式(4)中穩(wěn)態(tài)性能形式。記系統(tǒng)在單位時(shí)間獲得的平均報(bào)酬為 f(n,v(n):=f(n)= £=】mci叭其中少=1/仍。該平均報(bào)酬是一個(gè)僅取決于口前狀態(tài)n以及m二兀(n, v (n)

19、f (n) = 7t(7)下面介紹在呼叫接入控制中兒種常川的控制策略。1.5 cac策略完全共享(complete sharing, cs)控制策略。這是最簡單的控制策略，實(shí)際上系統(tǒng)基 本是沒有控制的，資源在各個(gè)服務(wù)z間是完全共享的，系統(tǒng)也不需要太多的實(shí)時(shí)信息，只要 系統(tǒng)的空閑資源人于到達(dá)的服務(wù)請求所需的資源請求量，系統(tǒng)就不會(huì)拒絕到達(dá)的服務(wù)請求。 釆用該策略的系統(tǒng)的狀態(tài)空間可表示為：clcs = p 乙心1 nab < b r完全分割(complete partitioning, cp)策略。與cs策略和反，cp策略是將系統(tǒng)的資源 完全獨(dú)立的預(yù)先分配給每類服務(wù)，也就是相應(yīng)地限制了每類服務(wù)

20、可以接受的服務(wù)顧客數(shù)。而 對于系統(tǒng)中的每一個(gè)獨(dú)立的服務(wù)類別，系統(tǒng)的cac策略與上面cs策略完全相同；系統(tǒng)分 配給第i類服務(wù)的資源數(shù)最為hi o系統(tǒng)需要知道當(dāng)前系統(tǒng)各個(gè)服務(wù)類別的顧客數(shù)，也就等價(jià) 于要知道系統(tǒng)中各個(gè)服務(wù)類的空閑資源量。采川該策略的系統(tǒng)的狀態(tài)空間可表示為：gcp = n ni bi < hi, i g jv )干線預(yù)留(trunk reservation, tr)策略在電話網(wǎng)絡(luò)屮常用的一類控制策略。采用該策 略，系統(tǒng)總是接受某一類服務(wù)，只要服務(wù)的接受不改變系統(tǒng)的資源約束；而接受其它類服務(wù) 則要求系統(tǒng)的剩余資源量必須大于某一個(gè)數(shù)值。系統(tǒng)需要知道系統(tǒng)資源總的使用情況，控制 只是基

21、于某一個(gè)參數(shù)，即系統(tǒng)的剩余資源量。定義4： 一個(gè)策略稱為tr-i策略，如果在該策略下，系統(tǒng)的狀態(tài)空間滿足：對丁 hk = 0,1, i b / i , qtr-i = n n e qcs , nk < hk, k e m/i)負(fù)荷相關(guān)(load-dependent, ld)策略。與tr控制策略很和似，ld策略只是比tr策 略更特殊的控制策略。采用該策略，系統(tǒng)接受每-類服務(wù)的前提是，首先不改變系統(tǒng)的資源 約束，冃要求系統(tǒng)的剩余資源量必須大于某一個(gè)數(shù)值。系統(tǒng)需要知道系統(tǒng)資源總的使用情況， 控制也只是基于某一個(gè)參數(shù)，即系統(tǒng)的剩余資源量。采用該策略的系統(tǒng)的狀態(tài)空間可表示為： 對丁 hk = 0,

22、1,厶，丨 l b / bk u , fl ld = n n e ges, nk < hk 動(dòng)態(tài)規(guī)劃(dynamic programming, dp)控制策略。采用dp策略，決策的制定不僅依 賴于系統(tǒng)如果接受該服務(wù)請求厲系統(tǒng)所轉(zhuǎn)移的狀態(tài)，而h依賴于請求服務(wù)的類型。該策略是 上述的所有接入控制策略的一個(gè)特殊情況。系統(tǒng)不僅需要知道系統(tǒng)資源總的使用悄況，還需 要知道系統(tǒng)當(dāng)前的狀態(tài)。2算法及算例2.1算法本節(jié)我們給出cac問題基于長期平均報(bào)酬準(zhǔn)則的策略優(yōu)化算法。該算法是從一個(gè)任意 的勢向量開始迭代，對每一狀態(tài)，求使mdp平均代價(jià)模型的最優(yōu)性方程中不等式達(dá)到最 大的行動(dòng)。我們町以從一個(gè)零勢能開始迭

23、代，cao證明了可以以性能函數(shù)向量作為勢向量的 近似，此時(shí)得到的是一個(gè)cs策略。因此，在cac策略優(yōu)化中，我們得到一個(gè)很自然的 初始策略cs策略，將此策略作為初始策略進(jìn)行優(yōu)化，算法如下：步1：山初始策略cs策略vo，計(jì)算a(n.i),由(6)求出其相應(yīng)的無窮小矩陣avo ,由go = at+ f求出勢能向量，由求出穩(wěn)態(tài)概率向量kv0 ,由求出該策略對應(yīng)的長期平均報(bào)酬r|o，置k = 0 o步2：對于每一個(gè)狀態(tài)neq ,選擇一個(gè)策略kv ( n),使工mwd av( n, m) g k + f (n, vk +i (n) > 工aa(n, m)gk + f(n, a)對所有的awa(n)均

24、成立，由此得到vk+i o步3：由gk+i = a、zgk + f求出勢能向量，由求出穩(wěn)態(tài)概率向量71vr.i ,并由(7求出該 策略対應(yīng)的長期平均報(bào)酬n-. o步4：若，則置k + 1 = k ,轉(zhuǎn)步2,否則轉(zhuǎn)步5o步5：結(jié)束，v為最優(yōu)策略：小為最優(yōu)長期平均報(bào)酬。該算法的優(yōu)點(diǎn)是能克服狀態(tài)維數(shù)過高所帶來的計(jì)算困難。因?yàn)樵摲椒ㄊ菍σ粋€(gè)mxk 維向量的整體尋優(yōu)轉(zhuǎn)化為k次m維向量的尋優(yōu)。在問題中，這意味著將對2( mxk )個(gè)可能策 略的尋優(yōu)轉(zhuǎn)化為若t次循環(huán)，而每次循環(huán)是作k次2'味策略中的尋優(yōu)。這無疑極人地加快 了優(yōu)化速度，尤其狀態(tài)數(shù)k很大時(shí)更是如此。此外山引理3與引理4,我們很容易證明

25、，算 法的每一次迭代，性能值總能得到改善。由于行動(dòng)集是冇限的，i大i此該算法總是收斂的。2.2算例下面我們給岀一個(gè)單節(jié)點(diǎn)、多服務(wù)網(wǎng)絡(luò)中cac問題的實(shí)際例了，對不同的控制策略進(jìn) 行比較。為了進(jìn)一步比較系統(tǒng)在不同控制策略下的性能，我們下面給出系統(tǒng)在不同負(fù)荷下的 情況。為了簡化分析，下而只考慮系統(tǒng)到達(dá)率改變的情況。系統(tǒng)的參數(shù)分別為：m = 3 , b = 12 , b =(1,2,2), c =(8, 20, 9), p = ( 0.5, 0.& 0.9)。下表給岀了系統(tǒng)在不同負(fù)荷下(我 們只選取4組結(jié)果來說明問題，對于英它的到達(dá)率悄況我們可以得到同樣的結(jié)論)不同cac 策略所對應(yīng)的最優(yōu)性能

26、值及所對應(yīng)的參數(shù)向呈。表 1 x= (0.2, 0.32, 0.36)tab.l z= (0.2, 0.32,0.36)cscptratr丄tr3lddp性能值16.799015.935516.799016.799016.799016.799017.8864參數(shù)無(2,6,4)(0,1,1)(1,0,1)(1,1,0)(1,1,1)無表 2 z= (0.3, 0.4& 0.54)tab.2z= (0.3, 0.4& 0.54)cscptrtr丄tr_3lddp性能值16.799015.935516.799016.799016.799016.799017.8864參數(shù)無(2, 6

27、,4)(0, 1 , 1)(1,0,1)(1,1,0)(1,1,1)無從表12可以看出，當(dāng)系統(tǒng)各個(gè)部分的負(fù)荷較低(到達(dá)率較小)時(shí)，除cp控制策略 外，系統(tǒng)采用其它不同控制策略的長期平均報(bào)酬的差別很小，系統(tǒng)的最優(yōu)控制策略應(yīng)該是 cs控制策略，因?yàn)椴纱ㄟ@種控制策略所需信息最少，成本最低，而且容易實(shí)施。但是該控 制策略由于不對系統(tǒng)各個(gè)部分服務(wù)加以控制，資源的利用效率往往很低，口不能體現(xiàn)公平性。表 3 x= (0.5,0.8, 0.9)tab.3 2= (0.5, 0.8, 0.9)步2：對于cscptr_1tr丄tr_3lddp性能值27.267724.680027.267727.267727.26

28、7727.267729.0551參數(shù)無(2, 6,4)(0, 1 , 1)(1,0, 1)(1,1,0)(1, 1 , 1)無表 4 z= (3tab.4 2=lo, 2.6, 1.8)30, 2.6, 1.8)cscptr_1tr丄77?_3lddp性能值27.267724.680027.267727.267727.267727.267729.0551參數(shù)無 6,4)(0, 1, 1)(1,0,1)(1,1,0)(1,1,1)無從表3-4可以看出，當(dāng)系統(tǒng)各個(gè)部分的負(fù)荷較高(到達(dá)率較大)時(shí)，不同的控制策略 的氏期平均報(bào)酬就有差別了。此時(shí)，系統(tǒng)的最優(yōu)控制策略是qp控制策略，采用該策略時(shí)系 統(tǒng)的性

29、能值最大，明顯高于其它兒種控制策略；但是釆用這種控制策略一個(gè)缺點(diǎn)就是系統(tǒng)需在要很多顧客消費(fèi)的信息。干線預(yù)留策略并不總是優(yōu)于cs策略的，如表4屮系統(tǒng)采用tr_ 控制策略時(shí)的性能值就低于cs策略下的性能值。結(jié)合tr_策略的控制方法，我們不難得 出這一結(jié)果。因?yàn)樵趖r_l控制策略中，系統(tǒng)不對第一類服務(wù)的消費(fèi)進(jìn)行控制，這樣會(huì)導(dǎo)致 第一類顧客占用大量的系統(tǒng)資源，而系統(tǒng)從第一類服務(wù)得到的收益是最低的，這樣就會(huì)導(dǎo)致 系統(tǒng)的平均報(bào)酬的減小。ld控制策略的性能介于cs控制策略的性能與dp控制策略性能之間，但與cs控制策 略的件能相差不大。該策略一個(gè)很好的優(yōu)點(diǎn)是能夠體現(xiàn)公平件，采用厶d控制策略的系統(tǒng)能 夠控制每一

30、類服務(wù)的所占用的系統(tǒng)資源數(shù)，進(jìn)而控制每一類服務(wù)的消費(fèi)者的在線人數(shù)。結(jié)合表1-4可以看出，不論系統(tǒng)各個(gè)部分的負(fù)荷高低，cp的性能都是最差的。一個(gè)直 觀的解釋就是，當(dāng)系統(tǒng)某一部分服務(wù)顧客數(shù)相對較少且有剩余帶寬時(shí)，由于cp控制策略限 制其它部分顧客占用這部分剩余帶寬，因而造成這部分系統(tǒng)資源的暫時(shí)性浪費(fèi)，系統(tǒng)的長期 平均收益就會(huì)較差。該策略一個(gè)很好的優(yōu)點(diǎn)與ld策略類似，能夠體現(xiàn)公平性，且采用這種 控制策略所需信息量少，成木低，容易實(shí)施。3總結(jié)與展望木文應(yīng)用mdp與性能勢相結(jié)合的方法，將呼叫接入控制(cac)中的長期平均報(bào)酬問題 轉(zhuǎn)化為mdp中的穩(wěn)態(tài)性能。在分析不同cac策略的基礎(chǔ)上，給出基于長期平均報(bào)

31、酬準(zhǔn)則 的cac策略優(yōu)化算法，該算法將對-個(gè)m* k維向量的整體尋優(yōu)轉(zhuǎn)化為k次m維向量的尋 優(yōu)，因而能克服狀態(tài)維數(shù)過高所帶來的計(jì)算困難，且該算法具有很快的收斂速度。最后運(yùn)用 該方法対多服務(wù)、單節(jié)點(diǎn)網(wǎng)絡(luò)中幾種常川的呼叫接入控制策略基于長期平均報(bào)酬準(zhǔn)則進(jìn)行了 分析比較。實(shí)際的算例表明，呼叫接入控制策略在長期平均報(bào)酬準(zhǔn)則下的優(yōu)劣性與系統(tǒng)的負(fù) 荷相關(guān)，盡管cp控制策略無論在什么情況下都是最優(yōu)的策略，但是如果考慮系統(tǒng)采用該策 略所需信息的成木時(shí)，不同負(fù)荷下的最優(yōu)cac策略是不同的。本文的研究給網(wǎng)絡(luò)管理者實(shí)際資源分配與接入控制策略的優(yōu)化與選擇上提供一個(gè)有利 的分析工具，從而選擇合適的資源分配策略與cac策

32、略以更好地控制與管理網(wǎng)絡(luò)，有效地 利川稀缺的網(wǎng)絡(luò)資源，提供更優(yōu)質(zhì)的網(wǎng)絡(luò)服務(wù)。文中對控制策略的優(yōu)化都是假設(shè)服務(wù)報(bào)酬是 給定的，下一步可以考慮應(yīng)用本文所提出的方法研究cac策略中報(bào)酬可變的情況。另外呼 叫接入控制問題中的服務(wù)節(jié)點(diǎn)與排隊(duì)網(wǎng)絡(luò)有很多相似z處，可以在19的基礎(chǔ)上考慮基于并行仿真的方法對系統(tǒng)策略進(jìn)行優(yōu)化。參考文獻(xiàn)(references)1 a. odlyzko internet pricing and the history of communications j. computer networks, 2001, 36: 493-517.2 m. mason, r. varian. pr

33、icing congcstiblc network resources j|. ieee journal on selected areas in communications, 1995, 13 (7): 1141-1149.3 井元偉，岳曉寧，王玉琢，沈曉軍.基丁交義干擾的多優(yōu)先級網(wǎng)絡(luò)線性激勵(lì)價(jià)控|j控制與決策,2005, 20(1):23 -26.|4j m. falkner, m. devetsikiotis, i. lambadaris an overview of pricing concepts for broadband ip networksfj. ieee communic

34、ations review, 2000, 3:2-13.5 jun wang, kin f.li. understanding internet pricing: an objective-oriented classificationc. ieee canadian conference on electrical and computer engineering, 2003, 2 : 703-708 zbigniew dziong, l.g. mason. fair-efficient call admission control policies for broadband networ

35、ks-a game theoretic framework jj. ieee/acm transactions on networking, 1996, 4 (1): 23-136.71 l. s. gopal. t. e. stem. optimal call blocking policies in an integrated services environment c proc.corf inform sci. syst, johns hopkins univ, 1983, pp. 383-388.8 kw. ross, d.h.k. tsarrg. optimal circuit a

36、ccess policies in an isdn environment: a markov decision approach|jj. ieee transactions on communications, 1989, 37: 34-939. t.oda, y. watanabe. optimal trunk reservation for a group with multi-slot traffic stream j. ieee transactions on communications, 1990, 38(7): 78-108410 k.q liao, z dziong, l.g. mason. dynamic link bandwidth allocation in an integrated services networkc. in proc. ieee international conference on communications, boston, ma, june 198