排隊(duì)論及其在通信領(lǐng)域中的應(yīng)用

排隊(duì)論及其在通信領(lǐng)域中的應(yīng)用信息與通信工程學(xué)院2010211112班姓名：李紅豆學(xué)號(hào)：10210367班內(nèi)序號(hào)：26指導(dǎo)老師：史悅摘要排隊(duì)論是為了系統(tǒng)的性態(tài)、系統(tǒng)的優(yōu)化和\o"統(tǒng)計(jì)推斷"統(tǒng)計(jì)推斷，根據(jù)資料的合理建立模型，其目的是正確設(shè)計(jì)和有效運(yùn)行各個(gè)服務(wù)系統(tǒng)，使之發(fā)揮最佳效益。排隊(duì)是一種司空見(jiàn)慣的現(xiàn)象，因此排隊(duì)論可以用來(lái)解決許多現(xiàn)實(shí)問(wèn)題。利用排隊(duì)論的知識(shí)可以來(lái)解決通信服務(wù)中的排隊(duì)論問(wèn)題。應(yīng)用排隊(duì)論一方面可以有效地解決通信服務(wù)系統(tǒng)中信道資源的分配問(wèn)題；另一方面通過(guò)系統(tǒng)優(yōu)化，找出用戶和服務(wù)系統(tǒng)兩者之間的平衡點(diǎn)，既減少排隊(duì)等待時(shí)間，又不浪費(fèi)信號(hào)資源，從而達(dá)到最優(yōu)設(shè)計(jì)的完成。關(guān)鍵字排隊(duì)論、最簡(jiǎn)單流、排隊(duì)系統(tǒng)、通信引言排隊(duì)論又稱隨機(jī)服務(wù)系統(tǒng),主要解決與隨機(jī)到來(lái)、排隊(duì)服務(wù)現(xiàn)象有關(guān)的應(yīng)用問(wèn)題。是研究系統(tǒng)由于隨機(jī)因素的干擾而出現(xiàn)排隊(duì)(或擁塞)現(xiàn)象的規(guī)律的一門(mén)學(xué)科,排隊(duì)論的創(chuàng)始人Erlang是為了解決電話交換機(jī)容量的設(shè)計(jì)問(wèn)題而提出排隊(duì)論。它適用于一切服務(wù)系統(tǒng),包括通信系統(tǒng)、計(jì)算機(jī)系統(tǒng)等?？梢哉f(shuō),凡是出現(xiàn)擁塞現(xiàn)象的系統(tǒng),都屬于隨機(jī)服務(wù)系統(tǒng)。隨著電子計(jì)算機(jī)的不斷發(fā)展和更新,通信網(wǎng)的建立和完善,信息科學(xué)及控制理論的蓬勃發(fā)展均涉及到最優(yōu)設(shè)計(jì)與最佳服務(wù)問(wèn)題,從而使排隊(duì)論理論與應(yīng)用得到發(fā)展。正文排隊(duì)論概述：1.1基本概念及有關(guān)概率模型簡(jiǎn)述：1.1.1排隊(duì)論基本概念及起源：排隊(duì)論是一個(gè)獨(dú)立的數(shù)學(xué)分支有時(shí)也把它歸到運(yùn)籌學(xué)中。排隊(duì)論是專門(mén)研究由于隨機(jī)因素的影響而產(chǎn)生的擁擠現(xiàn)象(排隊(duì)、等待)的科學(xué)也稱為隨機(jī)服務(wù)系統(tǒng)理論或擁塞理論。它專于研究各種排隊(duì)系統(tǒng)概率規(guī)律性的基礎(chǔ)上解決有關(guān)排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì)和最優(yōu)控制問(wèn)題。排隊(duì)論起源于20世紀(jì)初。當(dāng)時(shí)美國(guó)貝爾Bell電話公司發(fā)明了自動(dòng)電話以后如何合理配臵電話線路的數(shù)量以盡可能地減少用戶重復(fù)呼叫次數(shù)問(wèn)題出現(xiàn)了。1909年丹麥工程師愛(ài)爾蘭A.K.Erlang發(fā)表了具有重要?dú)v史地位的論文“概率論和電話交換”從而求解了上述問(wèn)題。1917年A.K.Erlang又提出了有關(guān)通信業(yè)務(wù)的擁塞理論用統(tǒng)計(jì)平衡概念分析了通信業(yè)務(wù)量問(wèn)題形成了概率論的一個(gè)新分支。后經(jīng)C.Palm等人的發(fā)展由近代概率論觀點(diǎn)出發(fā)進(jìn)行研究奠定了話務(wù)量理論的數(shù)學(xué)基礎(chǔ)。排隊(duì)論廣泛應(yīng)用在網(wǎng)絡(luò)的設(shè)計(jì)和優(yōu)化方法移動(dòng)通信系統(tǒng)中的切換呼叫的處理方法隨機(jī)接入系統(tǒng)的流量分析方法ATM業(yè)務(wù)流的數(shù)學(xué)模型及其排隊(duì)分析方法等。1.1.2排隊(duì)論系統(tǒng)的組成一個(gè)排隊(duì)系統(tǒng)由三個(gè)基本部分組成，輸入過(guò)程、排隊(duì)規(guī)則和服務(wù)機(jī)構(gòu)。Pk（t）=(λt)k這里的Pk（t）是在時(shí)間t內(nèi)有k個(gè)顧客到達(dá)的概率，或是一個(gè)排隊(duì)系統(tǒng)中在時(shí)間t內(nèi)有k個(gè)顧客在等待或正在處理的概率，或是總的C條信道中有k條信道被占用概率。泊松過(guò)程的顧客到達(dá)時(shí)間間隔分布為顧客到達(dá)的時(shí)間間隔小于t的概率，即t內(nèi)有顧客的概率分布。兩相鄰顧客到達(dá)的時(shí)間間隔是一連續(xù)型隨機(jī)變量，用T表示。在時(shí)間內(nèi)沒(méi)有顧客到達(dá)的概率為P0（t）=(λt)00!則T的分布函數(shù)為F（t）=P(T≤t)=1-P(T>t)=1-e其概率密度函數(shù)為fT所以說(shuō)，一個(gè)隨機(jī)過(guò)程為“泊松到達(dá)過(guò)程”或“到達(dá)時(shí)間間隔為指數(shù)分布”實(shí)際上是一回事。一般來(lái)說(shuō)大量的稀有事件流，如果每一事件流在總事件流中起的作用很小，而且相互獨(dú)立，則總的合成流可以認(rèn)為是最簡(jiǎn)單流。大量研究表明將電話呼叫當(dāng)做最簡(jiǎn)單流處理得到的分析結(jié)果是正確的。1.3排隊(duì)系統(tǒng)的主要性能指標(biāo)最優(yōu)化問(wèn)題一般涉及排隊(duì)系統(tǒng)的最優(yōu)設(shè)計(jì)(靜態(tài)優(yōu)化),例如固話網(wǎng)中的中繼電路群數(shù)目的確定,分組交換網(wǎng)中的存儲(chǔ)空間容量的配等等。還涉及到排隊(duì)系統(tǒng)的最優(yōu)控制（動(dòng)態(tài)優(yōu)化），例如固話網(wǎng)中的中繼電路群數(shù)目的增加與否、無(wú)線信道中的信道分配策略等。排隊(duì)系統(tǒng)的性能指標(biāo)描述了排隊(duì)的概率規(guī)律性。通過(guò)計(jì)算一些性能指標(biāo)，研究排隊(duì)系統(tǒng)的最優(yōu)化問(wèn)題。現(xiàn)列舉指標(biāo)如下：排隊(duì)長(zhǎng)度，簡(jiǎn)稱隊(duì)長(zhǎng)，是某觀察時(shí)刻系統(tǒng)內(nèi)滯留的顧客數(shù)。包括正在被服務(wù)的顧客。k是非負(fù)的離散型隨機(jī)變量。通常用來(lái)描述隊(duì)長(zhǎng)k的指標(biāo)有兩個(gè)：k的概率分布與k的統(tǒng)計(jì)平均值Ls和平均等待隊(duì)長(zhǎng)Lq。知道了隊(duì)長(zhǎng)分布，就可以確定隊(duì)長(zhǎng)超過(guò)某個(gè)數(shù)量的概率從而能為設(shè)計(jì)排隊(duì)空間的大小提供依據(jù)。等待時(shí)間，從顧客到達(dá)排隊(duì)系統(tǒng)的時(shí)刻算起到它開(kāi)始接受服務(wù)的時(shí)刻為止的這段時(shí)間為等待時(shí)間。平均等待時(shí)間Wq是等待時(shí)間的統(tǒng)計(jì)平均值。系統(tǒng)逗留時(shí)間是從顧客到達(dá)系統(tǒng)時(shí)刻算起到它接受服務(wù)完畢離開(kāi)系統(tǒng)時(shí)刻為止的這段時(shí)間。平均系統(tǒng)逗留時(shí)間（或系統(tǒng)時(shí)間）Ws是系統(tǒng)逗留時(shí)間的統(tǒng)計(jì)平均值。系統(tǒng)效率：設(shè)某時(shí)刻有r個(gè)窗口被占用，若共有m個(gè)窗口則r/m就是窗口占用率。它的統(tǒng)計(jì)平均值為平均窗口占用率就是系統(tǒng)效率即η=rm空閑概率P0和拒絕概率Pn：P0為系統(tǒng)內(nèi)無(wú)顧客的情況，即系統(tǒng)空閑狀態(tài)概率。通過(guò)，可知系統(tǒng)的忙閑情況。拒絕系統(tǒng)Pn（或Pc）為系統(tǒng)內(nèi)顧客已滿、拒絕新到顧客進(jìn)入系統(tǒng)的狀態(tài)概率，也稱為阻塞概率（或損失概率）。1.4兩類重要排隊(duì)系統(tǒng)模型的簡(jiǎn)要介紹及分析1.4.1M/M/1排隊(duì)系統(tǒng)最簡(jiǎn)單的排隊(duì)系統(tǒng)模型是M/M/1單窗口非拒絕系統(tǒng)。該系統(tǒng)的顧客到達(dá)為泊松流，設(shè)到達(dá)率為λ；服務(wù)時(shí)間為指數(shù)分布，設(shè)平均服務(wù)率為μ。圖2M/M/1排隊(duì)系統(tǒng)的狀態(tài)轉(zhuǎn)移圖1.4.2M/M/m/(n)排隊(duì)系統(tǒng)解決M/M/1系統(tǒng)的服務(wù)質(zhì)量與系統(tǒng)效率之間的矛盾必須壓縮排隊(duì)長(zhǎng)度、減小等待時(shí)間。通?？刹捎脙煞N措施，增加窗口數(shù)和截止排隊(duì)長(zhǎng)度。增加窗口數(shù)可提高總服務(wù)率但意味著投資加大。而截止排隊(duì)長(zhǎng)度則通過(guò)降低系統(tǒng)質(zhì)量來(lái)?yè)Q取系統(tǒng)效率和穩(wěn)定性。M/M/m(n)排隊(duì)系統(tǒng)的模型（混合排隊(duì)方式）中，顧客到達(dá)為泊松流，到達(dá)率為λ。同時(shí)有m個(gè)窗口，每個(gè)窗口對(duì)一位顧客的服務(wù)時(shí)間為指數(shù)分布，每個(gè)窗口的平均服務(wù)率為μ。顧客采用混合排隊(duì)方式。隊(duì)列長(zhǎng)度為n，同時(shí)采取拒絕方式，即系統(tǒng)內(nèi)最多可有n個(gè)顧客。圖3M/M/m(n)排隊(duì)系統(tǒng)的系統(tǒng)模型和狀態(tài)轉(zhuǎn)移圖排隊(duì)論在通信領(lǐng)域基于通信業(yè)務(wù)量的簡(jiǎn)單應(yīng)用分析：排隊(duì)論作為概率論的一個(gè)重要分支，在學(xué)術(shù)界各個(gè)領(lǐng)域都發(fā)揮著重要作用，而在通信領(lǐng)域，排隊(duì)論的價(jià)值得到了空前的發(fā)掘，現(xiàn)就排隊(duì)論在通信業(yè)務(wù)量的應(yīng)用做出簡(jiǎn)要介紹以及相關(guān)討論。2.1通信業(yè)務(wù)量基本理論設(shè)計(jì)和建設(shè)一個(gè)通信網(wǎng)及所配臵的設(shè)備是以全網(wǎng)業(yè)務(wù)量為主要依據(jù)的。進(jìn)入通信網(wǎng)送到通信設(shè)備和線路上進(jìn)行傳輸?shù)恼Z(yǔ)音、數(shù)據(jù)等輸入信息統(tǒng)稱為通信呼叫，簡(jiǎn)稱呼叫，在排隊(duì)論中對(duì)應(yīng)顧客，呼叫長(zhǎng)度（呼叫持續(xù)時(shí)間）對(duì)應(yīng)服務(wù)時(shí)間。網(wǎng)中的呼叫源即是網(wǎng)內(nèi)的所有用戶。在網(wǎng)中傳送的信息量稱為通信業(yè)務(wù)量，也稱為流量。信道數(shù)C或線路容量在排隊(duì)論中對(duì)應(yīng)窗口數(shù)m，而不同類型的呼叫事件也分別對(duì)應(yīng)了不同的典型的排隊(duì)模型。2.1.1呼叫的發(fā)生過(guò)程通常情況下，滿足以下三個(gè)條件的呼叫條件稱為稱為純隨機(jī)呼叫：呼叫源無(wú)限多，即能夠發(fā)生呼叫的用戶數(shù)很大；處于占線狀態(tài)（占用信道）的呼叫源數(shù)目相對(duì)少可不考慮；用戶（呼叫）之間相互獨(dú)立；呼叫的發(fā)生和交換網(wǎng)（或信道）的阻塞狀態(tài)可分別考慮。若同時(shí)滿足最簡(jiǎn)單流條件，即可表示為M/M/m(n)排隊(duì)系統(tǒng)模型。實(shí)際通信網(wǎng)中的顧客（用戶）數(shù)總是有限的，所以不存在嚴(yán)格的純隨機(jī)呼叫，而多屬于準(zhǔn)隨機(jī)呼叫。準(zhǔn)隨機(jī)呼叫滿足以下兩個(gè)條件：呼叫源有限且用戶之間仍相互獨(dú)立。若同時(shí)滿足最簡(jiǎn)單流條件，即可表示為M/M/m(n，N)排隊(duì)系統(tǒng)模型。當(dāng)N很大時(shí)(N>>k)或用戶數(shù)非常多時(shí)準(zhǔn)隨機(jī)呼叫可近似當(dāng)做純隨機(jī)呼叫處理。N越大這種近似越合理。實(shí)際通信網(wǎng)中往往會(huì)遇到多個(gè)顧客（用戶）同時(shí)使用的狀況，這就需要引入呼叫合成發(fā)生的情況來(lái)做分析。設(shè)有兩個(gè)相互獨(dú)立的呼叫源，各自按呼叫發(fā)生率λ1、λPP則合成呼叫發(fā)生數(shù)為k的概率為P所以說(shuō)兩個(gè)分別按λ1、λ2的泊松分布的合成等于呼叫發(fā)生率為λ1+λ2的泊松分布。易推得若有個(gè)各自任意速率,為λ2.1.2業(yè)務(wù)量和呼叫量業(yè)務(wù)量是在指定觀察時(shí)間內(nèi)各個(gè)線路（或信道）可能被占用的時(shí)間之和即占用的總時(shí)間。這些時(shí)間可以是重疊的或不重疊的。若某線路有m條信道，第i條信道被占用Qi秒，則m條信道或該線路上的業(yè)務(wù)量Q為Q=i=1mQr。業(yè)務(wù)量的量綱是時(shí)間。若一個(gè)信道代表一個(gè)電話話路則業(yè)務(wù)量或話務(wù)量的單位是秒/話路。這里的Q具不僅反映了信息源所發(fā)生的用戶需求業(yè)務(wù)量業(yè)務(wù)量的強(qiáng)度通常稱為呼叫量。它可定義為線路（或信道）可能占用的時(shí)間與觀察時(shí)間之比，即呼叫量為a=業(yè)務(wù)量觀察時(shí)間=Qr（erl），a是沒(méi)有量綱的，通常使用“小時(shí)呼”或“愛(ài)爾蘭（erl）”表示它的單位。通常取T為一小時(shí)。一個(gè)erl表示一小時(shí)一個(gè)完全被占用的信道的呼叫量，即單位小時(shí)或單位分鐘的呼叫時(shí)長(zhǎng)。根據(jù)定義呼叫量也可表示為a=λ電話網(wǎng)中的業(yè)務(wù)量稱為話務(wù)量。話務(wù)量用來(lái)反映電話用戶的通話頻繁程度和通話時(shí)間的長(zhǎng)短。表示為Y=Λst，其中λ表示單位時(shí)間內(nèi)的呼叫次數(shù)，即呼叫強(qiáng)度（次/h）；對(duì)應(yīng)排隊(duì)論中的系統(tǒng)到達(dá)率。S表示一次呼叫的平均占用時(shí)長(zhǎng)（h/次）；對(duì)應(yīng)平均服務(wù)時(shí)間。T表示計(jì)算話務(wù)量的時(shí)間范圍（h）。話務(wù)量含義反映了占用設(shè)備的程度，同時(shí)也反映了用戶對(duì)電話網(wǎng)設(shè)備的需求。時(shí)延是指消息進(jìn)入網(wǎng)內(nèi)后直到被利用完畢所需的時(shí)間。包括等待時(shí)間、服務(wù)時(shí)間、處理時(shí)間、傳輸時(shí)延。其中傳輸時(shí)延一般是較小的，處理時(shí)間與消息內(nèi)容有關(guān)，一般可從技術(shù)上縮短所占的份額不一定太大而且往往是恒定的。時(shí)延的主要部分是系統(tǒng)時(shí)間即等待時(shí)間和服務(wù)時(shí)間。2.1.3服務(wù)等級(jí)及服務(wù)系統(tǒng)業(yè)務(wù)量理論利用ErlangB公式或C公式，即業(yè)務(wù)量、中繼線或信道數(shù)量和阻塞概率或呼叫等待概率之間的關(guān)系式在一定的服務(wù)等級(jí)上在已知業(yè)務(wù)量預(yù)測(cè)值的條件下確定中繼電路數(shù)、長(zhǎng)途電路數(shù)或求移動(dòng)網(wǎng)中核心網(wǎng)的電路數(shù)、無(wú)線網(wǎng)的信道配臵等。目的是使固定數(shù)量的中繼線路或信道可為一個(gè)數(shù)量更大的、隨機(jī)的用戶群體服務(wù)。服務(wù)等級(jí)表示為GoS（GradeofService）是表示擁塞的量。定義為呼叫阻塞概率（也稱呼叫阻塞率），或呼叫延遲時(shí)間大于某一特定排隊(duì)時(shí)間的概率。在實(shí)際的通信網(wǎng)中多為截止型的排隊(duì)系統(tǒng)。當(dāng)系統(tǒng)處于拒絕狀態(tài)時(shí)系統(tǒng)是阻塞的將出現(xiàn)呼損。按處理阻塞呼叫（未接續(xù)的呼叫）的方式不同，通信網(wǎng)中通常用到兩種服務(wù)系統(tǒng)：阻塞呼叫清除系統(tǒng)和阻塞呼叫延遲系統(tǒng)。阻塞呼叫清除系統(tǒng)不對(duì)阻塞呼叫請(qǐng)求進(jìn)行排隊(duì)即放棄阻塞呼叫的接續(xù)。這種系統(tǒng)又叫做阻塞系統(tǒng)或損失制系統(tǒng)、立接制系統(tǒng)。系統(tǒng)模型為M/M/m（m）或M/M/m（m，N），基本的阻塞呼叫清除系統(tǒng)為M/M/m（m）。而阻塞呼叫延遲系統(tǒng)系統(tǒng)模型為M/M/m（n）、M/M/m基本的阻塞呼叫延遲系統(tǒng)為M/M/m（n）。2.2舉例分析——蜂窩移動(dòng)網(wǎng)中的呼叫處理排隊(duì)方案蜂窩移動(dòng)通信是采用蜂窩無(wú)線組網(wǎng)方式，在終端和網(wǎng)絡(luò)設(shè)備之間通過(guò)無(wú)線通道連接起來(lái)，進(jìn)而實(shí)現(xiàn)用戶在活動(dòng)中可相互通信。其主要特征是終端的移動(dòng)性，并具有越區(qū)切換和跨本地網(wǎng)自動(dòng)漫游功能。蜂窩移動(dòng)通信業(yè)務(wù)是指經(jīng)過(guò)由基站子系統(tǒng)和移動(dòng)交換子系統(tǒng)等設(shè)備組成蜂窩移動(dòng)通信網(wǎng)提供的話音、數(shù)據(jù)、視頻圖像等業(yè)務(wù)。其中在GSM網(wǎng)絡(luò)呼叫切換處理中常用三個(gè)典型的越區(qū)切換方案有無(wú)優(yōu)先級(jí)方案、切換呼叫排隊(duì)方案、信道預(yù)留方案。先分析如下：2.2.1無(wú)優(yōu)先級(jí)方案系統(tǒng)模型表示為處理新呼叫和切換呼叫的排隊(duì)模型M/M/C（C）。對(duì)這種這種方案來(lái)說(shuō)小區(qū)中所有的C個(gè)信道均被新呼叫和越區(qū)切換呼叫所共享。基站處理以上兩種呼叫的方法完全相同。任意一種呼叫，如在其到達(dá)的時(shí)刻基站內(nèi)沒(méi)有空閑信道那么到達(dá)的呼叫都將被系統(tǒng)阻塞。2.2.2切換呼叫排隊(duì)方案系統(tǒng)模型表示為處理新呼叫的排隊(duì)模型M/M/C（C），或處理切換呼叫的排隊(duì)模型M/M/C（N）。就這種方案而言，小區(qū)中所有的C個(gè)信道同樣被新呼叫和越區(qū)切換呼叫所共享。當(dāng)上述兩種呼叫同時(shí)到達(dá)并且小區(qū)中的信道全被占用時(shí)將對(duì)切換呼叫進(jìn)行排隊(duì)并阻塞新呼叫。如果在最大排隊(duì)時(shí)間內(nèi)無(wú)空閑信道可用就將阻塞切換呼叫。2.2.3信道預(yù)留方案系統(tǒng)模型表示為處理新呼叫的排隊(duì)模型M/M/Sc（Sc）或處理切換呼叫的排隊(duì)模型