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

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