第三章_3 MG1型排隊(duì)系統(tǒng)

1、通信網(wǎng)絡(luò)理論基礎(chǔ)通信網(wǎng)絡(luò)理論基礎(chǔ)Information Science Institute, Xidian Universityhttp:/ Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityM/G/1型排隊(duì)系統(tǒng)型排隊(duì)系統(tǒng)v服務(wù)過程服務(wù)過程假定第假定第i個(gè)用戶的服務(wù)時(shí)間為個(gè)用戶的服務(wù)時(shí)間為Xi，Xi是獨(dú)立同分布的，是獨(dú)立同分布的，與到達(dá)間隔相互獨(dú)立。與到達(dá)間隔相互獨(dú)立

2、。令令 ，則服務(wù)時(shí)間的均值和二階矩為，則服務(wù)時(shí)間的均值和二階矩為 平均服務(wù)時(shí)間平均服務(wù)時(shí)間 服務(wù)時(shí)間的二階矩服務(wù)時(shí)間的二階矩 ,21XXX X 1XE2X2XEXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv下面我們將證明，下面我們將證明，M/G/1M/G/1排隊(duì)系統(tǒng)的平均等待時(shí)間排隊(duì)系統(tǒng)的平均等待時(shí)間為為v其中，其中，v該式稱為該式稱為P-KP-K（Pollac

3、zek-KhinchinPollaczek-Khinchin）公式。）公式。P-K公式公式122XWXXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式v根據(jù)上述根據(jù)上述P-K公式，應(yīng)用公式，應(yīng)用Little定理定理,可以得該系統(tǒng)的可以得該系統(tǒng)的平均時(shí)延為平均時(shí)延為v平均隊(duì)列長(zhǎng)度為平均隊(duì)列長(zhǎng)度為 v系統(tǒng)中的平均用戶數(shù)為系統(tǒng)中的平均用戶數(shù)為22 1XTXW

4、X1222XWNQ1222XXTNXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式v如果如果G GM M，即服務(wù)時(shí)間服從指數(shù)分布，即服務(wù)時(shí)間服從指數(shù)分布，M/M/1M/M/1， v如果服務(wù)時(shí)間是常量，即如果服務(wù)時(shí)間是常量，即M/D/1 M/D/1 222X1X221X22212 12 11XW22112 12 121XWXidian Univ.B Br

5、oadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式vP-KP-K公式證明的思路是基于對(duì)平均剩余服務(wù)時(shí)間（公式證明的思路是基于對(duì)平均剩余服務(wù)時(shí)間（Mean Mean Residual Service TimeResidual Service Time）的求解。設(shè)第）的求解。設(shè)第i i個(gè)用戶到達(dá)系統(tǒng)個(gè)用戶到達(dá)系統(tǒng)時(shí)，第時(shí)，第l l個(gè)用戶正在接受服務(wù)，其剩余服務(wù)時(shí)間為個(gè)用戶正在接受服務(wù)，其剩

6、余服務(wù)時(shí)間為RiRi，此，此時(shí)等待隊(duì)列中有時(shí)等待隊(duì)列中有NiNi個(gè)用戶，個(gè)用戶， Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式v設(shè)第設(shè)第k個(gè)用戶的服務(wù)時(shí)間為個(gè)用戶的服務(wù)時(shí)間為Xk，則由圖可知，用戶，則由圖可知，用戶i的等待時(shí)間為的等待時(shí)間為 v對(duì)上式求平均得對(duì)上式求平均得iiWW lim1iNikkiiiiiXRNRW個(gè)用戶的服務(wù)時(shí)間 iiiNik

7、kiiNEXREXEREWi1WRWRNRNXRWQQ111RWXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式v假定系統(tǒng)有穩(wěn)態(tài)解，且具有各態(tài)歷經(jīng)性，則剩余服務(wù)時(shí)間假定系統(tǒng)有穩(wěn)態(tài)解，且具有各態(tài)歷經(jīng)性，則剩余服務(wù)時(shí)間 可用下圖表示可用下圖表示Xidian Univ.B Broadband roadband WWireless ireless C Comm

8、unications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式v為了方便起見，取為了方便起見，取t t為為 的時(shí)刻，則的時(shí)刻，則0,0,t t 區(qū)間區(qū)間的平均剩余服務(wù)時(shí)間為的平均剩余服務(wù)時(shí)間為 v式中，式中，M M( (t t) )表示表示00，t t 區(qū)間內(nèi)已服務(wù)的用戶數(shù)。區(qū)間內(nèi)已服務(wù)的用戶數(shù)。 上式可上式可以寫成以寫成v式中，第二項(xiàng)為平均到達(dá)率，第三項(xiàng)為式中，第二項(xiàng)為平均到達(dá)率，第三項(xiàng)為XiXi的二階矩。的二階矩。 0tr 2102111itMittXtdrtR tMXtt

9、MRtMiii1221Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式v令令 ，得，得v從從P-KP-K公式可以看出，公式可以看出，M/G/1M/G/1隊(duì)列的一個(gè)重要特隊(duì)列的一個(gè)重要特征：征： 。即使。即使 ，如，如 果果 ，則則v它說明，如果有少量用戶有非常長(zhǎng)的服務(wù)時(shí)間，一旦這些用它說明，如果有少量用戶有非常長(zhǎng)的服務(wù)時(shí)間，一旦這些用戶被服務(wù)，將導(dǎo)致隊(duì)

10、列非常長(zhǎng)。戶被服務(wù)，將導(dǎo)致隊(duì)列非常長(zhǎng)。 t221XR1212XRW2XW 12XWXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式v例例 返回返回n nARQARQ系統(tǒng)的時(shí)延性能分析系統(tǒng)的時(shí)延性能分析 設(shè)返回設(shè)返回n nARQARQ系統(tǒng)中的分組到達(dá)過程是速率為系統(tǒng)中的分組到達(dá)過程是速率為 的的PoissonPoisson過程，過程，分組（幀）長(zhǎng)度相同，

11、為一個(gè)單位，分組（幀）長(zhǎng)度相同，為一個(gè)單位，等待應(yīng)答的最長(zhǎng)時(shí)間（重傳間隔）為等待應(yīng)答的最長(zhǎng)時(shí)間（重傳間隔）為 個(gè)分組長(zhǎng)度。因此，任一分組傳輸出錯(cuò)后，將在個(gè)分組長(zhǎng)度。因此，任一分組傳輸出錯(cuò)后，將在 n-1n-1個(gè)分組后重傳。個(gè)分組后重傳。1nXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式Xidian Univ.B Broadband roadband

12、WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityP-K公式公式v在在該該系系統(tǒng)統(tǒng)中，一中，一個(gè)個(gè)分分組組（幀幀）的服）的服務(wù)時(shí)間務(wù)時(shí)間，不，不僅僅僅僅是一是一個(gè)個(gè)分分組組的一次的一次傳輸時(shí)間傳輸時(shí)間，而且，而且還應(yīng)當(dāng)還應(yīng)當(dāng)包括分包括分組組的重的重傳時(shí)間傳時(shí)間。因此，。因此，這這里的服里的服務(wù)時(shí)間為務(wù)時(shí)間為一一個(gè)個(gè)等效服等效服務(wù)時(shí)間務(wù)時(shí)間，它它等于等于從從一一個(gè)個(gè)分分組組的第一次的第一次傳輸開傳輸開始，到始，到該該分分組組的最后一次

13、的最后一次傳輸結(jié)傳輸結(jié)束束時(shí)時(shí)刻之刻之間間的的時(shí)間長(zhǎng)時(shí)間長(zhǎng)度，度，它它服服從從一般性分布，因而一般性分布，因而該該系系統(tǒng)統(tǒng)可用可用M/G/1隊(duì)隊(duì)列模列模型型來來描述。描述。Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv假定分組傳輸錯(cuò)誤的概率為假定分組傳輸錯(cuò)誤的概率為p p。如果分組重傳次數(shù)。如果分組重傳次數(shù)為為k k，則等效服務(wù)時(shí)間為，則等效服務(wù)時(shí)間為 ，其概率

14、為，其概率為 （一次正確傳輸，（一次正確傳輸，k k次傳輸錯(cuò)誤，共次傳輸錯(cuò)誤，共k k+1+1次傳輸），次傳輸），即等效服務(wù)時(shí)間即等效服務(wù)時(shí)間X Xk k的概率分布為的概率分布為v其一階矩和二階矩為其一階矩和二階矩為 P-K公式公式kn1kpp1kkppknXP11pnpppknXkk11110 222022112111pppnpnpppknXkkXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian Unive

15、rsityUniversityP-K公式公式v該公式的推導(dǎo)過程中，利用了下列結(jié)果：該公式的推導(dǎo)過程中，利用了下列結(jié)果：v利用利用P-KP-K公式可得，分組的平均等待時(shí)延和分組的公式可得，分組的平均等待時(shí)延和分組的平均時(shí)延分別為平均時(shí)延分別為011kkpp201ppkpkk03221kkppppkXXW122WXTXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)員

16、有休假的服務(wù)員有休假的M/G/1排隊(duì)模型排隊(duì)模型v服務(wù)員有休假的服務(wù)員有休假的M/G/1M/G/1（M/G/1 Queues with M/G/1 Queues with VacationsVacations）排隊(duì)系統(tǒng)是指在每一個(gè)忙周期后（分）排隊(duì)系統(tǒng)是指在每一個(gè)忙周期后（分組傳輸結(jié)束后），服務(wù)員需要休假（休假對(duì)應(yīng)于服組傳輸結(jié)束后），服務(wù)員需要休假（休假對(duì)應(yīng)于服務(wù)員（通信節(jié)點(diǎn)）要進(jìn)行其它處理，如存儲(chǔ)數(shù)據(jù)、務(wù)員（通信節(jié)點(diǎn)）要進(jìn)行其它處理，如存儲(chǔ)數(shù)據(jù)、信令交換等），在服務(wù)員休假期內(nèi)到達(dá)的用戶，要信令交換等），在服務(wù)員休假期內(nèi)到達(dá)的用戶，要等待服務(wù)員休假結(jié)束后，才能被服務(wù)。如服務(wù)員休等待服務(wù)員休假結(jié)

17、束后，才能被服務(wù)。如服務(wù)員休假期滿后，沒有用戶到達(dá)，服務(wù)員進(jìn)入另一個(gè)休假假期滿后，沒有用戶到達(dá)，服務(wù)員進(jìn)入另一個(gè)休假期。期。 Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)員有休假的服務(wù)員有休假的M/G/1排隊(duì)模型排隊(duì)模型Xidian Univ.B Broadband roadband WWireless ireless C Communications La

18、boratoryommunications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)員有休假的服務(wù)員有休假的M/G/1排隊(duì)模型排隊(duì)模型v服務(wù)員的休假期用服務(wù)員的休假期用V V1 1，V V2 2，表示，表示，V Vi i是獨(dú)立同分是獨(dú)立同分布的隨機(jī)變量，并且與到達(dá)間隔相互獨(dú)立，其均值布的隨機(jī)變量，并且與到達(dá)間隔相互獨(dú)立，其均值為為 。v用戶（分組）的到達(dá)是速率為用戶（分組）的到達(dá)是速率為 的的PoissonPoisson過程，每過程，每個(gè)用戶的服務(wù)時(shí)間也是獨(dú)立同分布的隨機(jī)變量，其個(gè)用戶的服務(wù)時(shí)間也是獨(dú)立同分布的隨機(jī)變量，其平均服務(wù)時(shí)間

19、為平均服務(wù)時(shí)間為 V1Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)員有休假的服務(wù)員有休假的M/G/1排隊(duì)模型排隊(duì)模型v一個(gè)新用戶到達(dá)系統(tǒng)時(shí)，它可能會(huì)遇到兩種情況一個(gè)新用戶到達(dá)系統(tǒng)時(shí)，它可能會(huì)遇到兩種情況 當(dāng)前有一個(gè)分組正在接受服務(wù)當(dāng)前有一個(gè)分組正在接受服務(wù) 服務(wù)員正在處于休假期服務(wù)員正在處于休假期 v前一種情況的剩余服務(wù)時(shí)間與標(biāo)準(zhǔn)的前一種情況的剩余服務(wù)時(shí)間與

20、標(biāo)準(zhǔn)的M/G/1M/G/1隊(duì)列相隊(duì)列相同，后一種情況的剩余服務(wù)時(shí)間為服務(wù)員休假的同，后一種情況的剩余服務(wù)時(shí)間為服務(wù)員休假的剩余服務(wù)時(shí)間。剩余服務(wù)時(shí)間。 Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)員有休假的服務(wù)員有休假的M/G/1排隊(duì)模型排隊(duì)模型圖中陰影部分表示分組傳輸?shù)氖Ｓ喾?wù)時(shí)間Xi，其余部分是服務(wù)員休假期的剩余服務(wù)時(shí)間Vi。Xidian Univ.B

21、Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)員有休假的服務(wù)員有休假的M/G/1排隊(duì)模型排隊(duì)模型v令令M M( (t t) )和和L L( (t t) )分別為分別為 區(qū)間內(nèi)到達(dá)的用戶數(shù)區(qū)間內(nèi)到達(dá)的用戶數(shù)和服務(wù)員休假的次數(shù)。平均剩余服務(wù)時(shí)間為和服務(wù)員休假的次數(shù)。平均剩余服務(wù)時(shí)間為 t , 0 )()(21)()(212112111)(12)(12)(12)(120tLVttLtMXttM

22、VtXtdrttLiitMiitLiitMiitXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv由于分組傳輸和休假期的交替到達(dá)占滿整個(gè)時(shí)間軸，則在由于分組傳輸和休假期的交替到達(dá)占滿整個(gè)時(shí)間軸，則在單位時(shí)間，分組所占的比例為單位時(shí)間，分組所占的比例為 ，v休假期占的比例為休假期占的比例為 。v因而有休假到達(dá)率為因而有休假到達(dá)率為v當(dāng)當(dāng) ，得平均剩余服務(wù)時(shí)間為，得平均

23、剩余服務(wù)時(shí)間為 ( )( )2211011( )1( )2( )2( )M tL tiitiiXVM tL trdttM ttL t1V1t2212121VVXR1( )tVL tXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv例：時(shí)隙例：時(shí)隙FDMFDM和和TDMTDM系統(tǒng)的性能比較系統(tǒng)的性能比較 v設(shè)基本的設(shè)基本的FDMFDM（Frequency Divisi

24、on MultiplexingFrequency Division Multiplexing）系統(tǒng)）系統(tǒng)有有m m個(gè)信道，每個(gè)信道的分組到達(dá)率為個(gè)信道，每個(gè)信道的分組到達(dá)率為 ， 每個(gè)分組的傳輸時(shí)間為每個(gè)分組的傳輸時(shí)間為m m個(gè)單位時(shí)間，即服務(wù)時(shí)個(gè)單位時(shí)間，即服務(wù)時(shí)間間 。在該系統(tǒng)中，只要分組到達(dá)時(shí)信道空閑，該分組就會(huì)在該系統(tǒng)中，只要分組到達(dá)時(shí)信道空閑，該分組就會(huì)立即得到服務(wù)。顯然每個(gè)信道是標(biāo)準(zhǔn)的立即得到服務(wù)。顯然每個(gè)信道是標(biāo)準(zhǔn)的M/D/1M/D/1排隊(duì)系統(tǒng)，排隊(duì)系統(tǒng)，v其等待時(shí)間為其等待時(shí)間為 mm1mmm1)(1212mWFDMXidian Univ.B Broadband roadban

25、d WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv假設(shè)假設(shè)m m個(gè)信道變成以時(shí)隙為基礎(chǔ)，時(shí)隙的寬度為個(gè)信道變成以時(shí)隙為基礎(chǔ)，時(shí)隙的寬度為m m個(gè)單位，所個(gè)單位，所有的分組都在時(shí)隙的開始點(diǎn)進(jìn)行傳輸。如果在時(shí)隙開始時(shí)，有的分組都在時(shí)隙的開始點(diǎn)進(jìn)行傳輸。如果在時(shí)隙開始時(shí)，沒有分組到達(dá)，信道將空閑一個(gè)時(shí)隙（對(duì)應(yīng)于服務(wù)員休假一沒有分組到達(dá)，信道將空閑一個(gè)時(shí)隙（對(duì)應(yīng)于服務(wù)員休假一次）。該系統(tǒng)被稱為次）。該系統(tǒng)被稱為SFDMSFDM系統(tǒng)。系

26、統(tǒng)。 Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityvSFDMSFDM系統(tǒng)的每個(gè)信道是

27、服務(wù)員有休假的系統(tǒng)的每個(gè)信道是服務(wù)員有休假的M/D/1M/D/1系統(tǒng)，系統(tǒng)，v該公式與我們直觀上的理解是一致的，即在該公式與我們直觀上的理解是一致的，即在SFDMSFDM系統(tǒng)中，分系統(tǒng)中，分組到達(dá)后平均要比組到達(dá)后平均要比FDMFDM系統(tǒng)多等半個(gè)時(shí)隙。系統(tǒng)多等半個(gè)時(shí)隙。22mXmV 22mV12212112mmWmmWFDMSFDMXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUni

28、versityvTDMTDM（Time Division MultiplexingTime Division Multiplexing）系統(tǒng)，）系統(tǒng)，M M個(gè)信道合成一個(gè)信道，信道速率提高了個(gè)信道合成一個(gè)信道，信道速率提高了m m倍，故分組的傳輸時(shí)間倍，故分組的傳輸時(shí)間降低為原傳輸時(shí)間的降低為原傳輸時(shí)間的一幀由一幀由m m個(gè)時(shí)隙組成，每個(gè)分組的傳輸時(shí)間為一個(gè)時(shí)隙，時(shí)隙的寬個(gè)時(shí)隙組成，每個(gè)分組的傳輸時(shí)間為一個(gè)時(shí)隙，時(shí)隙的寬度為一個(gè)單位時(shí)間。度為一個(gè)單位時(shí)間。由于每個(gè)用戶在一幀中僅占一個(gè)時(shí)隙，如果在時(shí)隙開始時(shí)刻該用由于每個(gè)用戶在一幀中僅占一個(gè)時(shí)隙，如果在時(shí)隙開始時(shí)刻該用戶無分組到達(dá)，則必須等到下一

29、幀中相同的時(shí)隙才可能開始傳輸戶無分組到達(dá)，則必須等到下一幀中相同的時(shí)隙才可能開始傳輸分組。分組。因此，對(duì)于每個(gè)用戶來說，信道將暫停（休假）一幀（因此，對(duì)于每個(gè)用戶來說，信道將暫停（休假）一幀（m m個(gè)時(shí)隙）。個(gè)時(shí)隙）。在在TDMTDM系統(tǒng)中，剩余服務(wù)時(shí)間與系統(tǒng)中，剩余服務(wù)時(shí)間與SFDMSFDM系統(tǒng)的完全相同，即當(dāng)該用戶系統(tǒng)的完全相同，即當(dāng)該用戶在某一幀有分組傳送時(shí)，他等待的剩余服務(wù)時(shí)間不是一個(gè)時(shí)隙的在某一幀有分組傳送時(shí)，他等待的剩余服務(wù)時(shí)間不是一個(gè)時(shí)隙的剩余時(shí)間，而是一幀中的剩余時(shí)間，剩余時(shí)間，而是一幀中的剩余時(shí)間， m1Xidian Univ.B Broadband roadband WWi

30、reless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv因此，因此，TDM系統(tǒng)中每個(gè)用戶的等待時(shí)間為系統(tǒng)中每個(gè)用戶的等待時(shí)間為 v上述三種系統(tǒng)的分組總的時(shí)延分別為上述三種系統(tǒng)的分組總的時(shí)延分別為 12mWWSFDMTDM12mmTFDM2mTTFDMSFDM) 12()1 (21mTmTFDMTDMXidian Univ.B Broadband roadband WWireless ireless C Communications Labor

31、atoryommunications Laboratory, , Xidian Xidian UniversityUniversityXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity采用不同服務(wù)規(guī)則的采用不同服務(wù)規(guī)則的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng) v在前面的討論中，我們沒有考慮服務(wù)規(guī)則和分組的在前面的討論中，我們沒有考慮服務(wù)規(guī)則和分組的優(yōu)先級(jí)，來一個(gè)分組服務(wù)一個(gè)分組。

32、但當(dāng)多個(gè)用戶優(yōu)先級(jí)，來一個(gè)分組服務(wù)一個(gè)分組。但當(dāng)多個(gè)用戶共享一個(gè)統(tǒng)計(jì)復(fù)用的系統(tǒng)時(shí)，就必須采用適當(dāng)?shù)姆蚕硪粋€(gè)統(tǒng)計(jì)復(fù)用的系統(tǒng)時(shí)，就必須采用適當(dāng)?shù)姆?wù)規(guī)則，如預(yù)約或輪詢，對(duì)不同優(yōu)先級(jí)的分組采用務(wù)規(guī)則，如預(yù)約或輪詢，對(duì)不同優(yōu)先級(jí)的分組采用不同的服務(wù)方式等。不同的服務(wù)方式等。 采用預(yù)約方式的采用預(yù)約方式的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversi

33、ty采用預(yù)約方式的采用預(yù)約方式的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)v假設(shè)系統(tǒng)采用周期性預(yù)約的方式（類似于假設(shè)系統(tǒng)采用周期性預(yù)約的方式（類似于LANLAN中的中的令牌環(huán)協(xié)議），第一個(gè)用戶預(yù)約并傳輸一定數(shù)量的令牌環(huán)協(xié)議），第一個(gè)用戶預(yù)約并傳輸一定數(shù)量的分組后，由第二個(gè)用戶進(jìn)行預(yù)約和傳輸，依次類推，分組后，由第二個(gè)用戶進(jìn)行預(yù)約和傳輸，依次類推，所有用戶按循環(huán)的次序預(yù)約傳輸，所有用戶預(yù)約傳所有用戶按循環(huán)的次序預(yù)約傳輸，所有用戶預(yù)約傳輸一次構(gòu)成一個(gè)周期。輸一次構(gòu)成一個(gè)周期。Xidian Univ.B Broadband roadband WWireless ireless C Communications La

34、boratoryommunications Laboratory, , Xidian Xidian UniversityUniversity采用預(yù)約方式的采用預(yù)約方式的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity采用預(yù)約方式的采用預(yù)約方式的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)v由于在每次預(yù)約分組和數(shù)據(jù)分組的傳輸期內(nèi)（稱由于在每次預(yù)約分組和數(shù)據(jù)分組

35、的傳輸期內(nèi)（稱為預(yù)約傳輸期），會(huì)有新的分組到達(dá)，對(duì)于這些為預(yù)約傳輸期），會(huì)有新的分組到達(dá)，對(duì)于這些新的分組有三種不同的處理方式：新的分組有三種不同的處理方式：Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity采用預(yù)約方式的采用預(yù)約方式的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)在每個(gè)用戶的預(yù)約傳輸期內(nèi)，僅傳送預(yù)在每個(gè)用戶的預(yù)約傳輸期內(nèi)，僅傳送預(yù)約分組傳輸前到達(dá)的分組，該系統(tǒng)稱為約分組

36、傳輸前到達(dá)的分組，該系統(tǒng)稱為閘門型系統(tǒng)（閘門型系統(tǒng)（gated systemgated system）Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity采用預(yù)約方式的采用預(yù)約方式的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)在每個(gè)用戶的預(yù)約傳輸期內(nèi)，將上次預(yù)約傳輸在每個(gè)用戶的預(yù)約傳輸期內(nèi)，將上次預(yù)約傳輸期結(jié)束到本次預(yù)約傳輸期結(jié)束前到達(dá)的分組都期結(jié)束到本次預(yù)約傳輸期結(jié)束前到達(dá)的分組都在本

37、預(yù)約傳輸期內(nèi)傳輸，或者說在預(yù)約傳輸期在本預(yù)約傳輸期內(nèi)傳輸，或者說在預(yù)約傳輸期內(nèi)，將內(nèi)存中所有到達(dá)的分組都傳送完畢，該內(nèi)，將內(nèi)存中所有到達(dá)的分組都傳送完畢，該系統(tǒng)稱為耗盡型系統(tǒng)（系統(tǒng)稱為耗盡型系統(tǒng)（exhaustive systemexhaustive system）Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity采用預(yù)約方式的采用預(yù)約方式的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)

38、v在每個(gè)用戶的預(yù)約傳輸期內(nèi)，僅傳送預(yù)約分組傳輸在每個(gè)用戶的預(yù)約傳輸期內(nèi)，僅傳送預(yù)約分組傳輸結(jié)束前到達(dá)的所有分組，該系統(tǒng)稱為部分閘門型系結(jié)束前到達(dá)的所有分組，該系統(tǒng)稱為部分閘門型系統(tǒng)（統(tǒng)（partially gated systempartially gated system）。）。 Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv假設(shè)所有（假設(shè)所有（m m個(gè)）用戶

39、的分組到達(dá)過程都是相互獨(dú)個(gè)）用戶的分組到達(dá)過程都是相互獨(dú)立到達(dá)的立到達(dá)的PoissonPoisson過程過程到達(dá)率為到達(dá)率為 分組傳送時(shí)間的均值為分組傳送時(shí)間的均值為 二階矩為二階矩為 信道利用率為信道利用率為 采用預(yù)約方式的采用預(yù)約方式的M/G/1排隊(duì)系統(tǒng)排隊(duì)系統(tǒng)m1X2XXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity單用戶系統(tǒng)單用戶系統(tǒng)v單單用用戶戶系系統(tǒng)統(tǒng)

40、單單用用戶閘門戶閘門型系型系統(tǒng)統(tǒng)的性能的性能 Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv假定第假定第l l個(gè)預(yù)約分組的長(zhǎng)度為個(gè)預(yù)約分組的長(zhǎng)度為ViVi，ViVi是相互獨(dú)立同分布的隨是相互獨(dú)立同分布的隨機(jī)變量，機(jī)變量，其均值為其均值為 二階矩為二階矩為 v第第i i個(gè)分組到達(dá)時(shí)等待時(shí)間包括個(gè)分組到達(dá)時(shí)等待時(shí)間包括剩余服務(wù)時(shí)間，剩余服務(wù)時(shí)間，預(yù)約分組傳輸區(qū)間預(yù)約

41、分組傳輸區(qū)間V Vl l（i i）NiNi個(gè)等待分組的傳輸時(shí)間和。即個(gè)等待分組的傳輸時(shí)間和。即 單用戶系統(tǒng)單用戶系統(tǒng)V2V 1iiil iE WE RE VE NXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity單用戶系統(tǒng)單用戶系統(tǒng)v當(dāng)當(dāng) 時(shí)，有時(shí)，有iWNNEQiilim VVEililim RREiilimWWEiilimVWRVWRW11VRWVVXR21212

42、2 1iiil iE WE RE VE NXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv單用戶閘門系統(tǒng)的平均等待時(shí)間為單用戶閘門系統(tǒng)的平均等待時(shí)間為v如果預(yù)約分組長(zhǎng)度為一個(gè)常量如果預(yù)約分組長(zhǎng)度為一個(gè)常量A A，則有，則有單用戶系統(tǒng)單用戶系統(tǒng)121222VVVXW132122AXWXidian Univ.B Broadband roadband WWireless

43、 ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity多用戶系統(tǒng)多用戶系統(tǒng)v多用戶系統(tǒng)多用戶系統(tǒng)對(duì)于多用戶系統(tǒng)來說，與單用戶的差別主要是新到達(dá)對(duì)于多用戶系統(tǒng)來說，與單用戶的差別主要是新到達(dá)分組進(jìn)入不同用戶的隊(duì)列（系統(tǒng)共有分組進(jìn)入不同用戶的隊(duì)列（系統(tǒng)共有m m個(gè)隊(duì)列）時(shí)，將個(gè)隊(duì)列）時(shí)，將會(huì)遇到不同數(shù)量的預(yù)約時(shí)隙數(shù)（服務(wù)休假次數(shù)）。設(shè)會(huì)遇到不同數(shù)量的預(yù)約時(shí)隙數(shù)（服務(wù)休假次數(shù)）。設(shè)系統(tǒng)有系統(tǒng)有m m個(gè)用戶，當(dāng)?shù)趥€(gè)用戶，當(dāng)?shù)趇 i個(gè)分組到達(dá)系統(tǒng)時(shí)正好是第個(gè)分組到

44、達(dá)系統(tǒng)時(shí)正好是第l l個(gè)個(gè)用戶的預(yù)約傳輸期。如果第用戶的預(yù)約傳輸期。如果第i i個(gè)分組屬于個(gè)分組屬于l l1 1個(gè)用戶的個(gè)用戶的隊(duì)列，則它只會(huì)遇到一個(gè)預(yù)約分組的傳輸。如果第隊(duì)列，則它只會(huì)遇到一個(gè)預(yù)約分組的傳輸。如果第i i個(gè)個(gè)分組屬于第分組屬于第 l l1 1個(gè)用戶的隊(duì)列，則它會(huì)遇到個(gè)用戶的隊(duì)列，則它會(huì)遇到 m m1 1個(gè)個(gè)預(yù)約分組的傳輸。預(yù)約分組的傳輸。Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian U

45、niversityUniversity多用戶系統(tǒng)多用戶系統(tǒng) iiiiYENEREWE1Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity多用戶系統(tǒng)多用戶系統(tǒng)v設(shè)每一用戶的預(yù)約分組的傳輸時(shí)間為設(shè)每一用戶的預(yù)約分組的傳輸時(shí)間為V Vl l，其均值，其均值為為 ，則對(duì)于耗盡型系統(tǒng)來說，第，則對(duì)于耗盡型系統(tǒng)來說，第i i個(gè)分組在個(gè)分組在第第l l個(gè)用戶的預(yù)約傳輸期到達(dá)，但屬于

46、（個(gè)用戶的預(yù)約傳輸期到達(dá)，但屬于（l l+ +j j）mod mod m m個(gè)用戶，則要等待的預(yù)約分組傳輸時(shí)間之和為個(gè)用戶，則要等待的預(yù)約分組傳輸時(shí)間之和為v因此，在耗盡型系統(tǒng)中的平均等待時(shí)間為因此，在耗盡型系統(tǒng)中的平均等待時(shí)間為lV1 modmodilmljmYVV iiiiYENEREWE1Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity多用戶系統(tǒng)多用戶系統(tǒng)v令

47、令iYWRW1YRW122222201011111111222222mllmllVVVmRXXXVVVm101mllVmV10221mllVmV iiiiYENEREWE1Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity多用戶系統(tǒng)多用戶系統(tǒng)v另外，可以證明，耗盡型系統(tǒng)的平均等待的預(yù)約分組傳輸另外，可以證明，耗盡型系統(tǒng)的平均等待的預(yù)約分組傳輸時(shí)間為時(shí)間為v令令 該式表

48、示所有的預(yù)約分組長(zhǎng)度的方差該式表示所有的預(yù)約分組長(zhǎng)度的方差v耗盡型系統(tǒng)的平均等待時(shí)間為耗盡型系統(tǒng)的平均等待時(shí)間為 1YRW VmVVmYEYmili212102mVVmlllV10222VVmXWV2121222Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity多用戶系統(tǒng)多用戶系統(tǒng)v對(duì)于部分閘門性系統(tǒng)，它與耗盡型系統(tǒng)的差別是：在部分閘對(duì)于部分閘門性系統(tǒng)，它與耗盡型系統(tǒng)

49、的差別是：在部分閘門型系統(tǒng)中，當(dāng)分組到達(dá)自己的數(shù)據(jù)傳輸時(shí)，要等到下一次門型系統(tǒng)中，當(dāng)分組到達(dá)自己的數(shù)據(jù)傳輸時(shí)，要等到下一次本節(jié)點(diǎn)的預(yù)約傳輸期才能傳輸，即要多增加本節(jié)點(diǎn)的預(yù)約傳輸期才能傳輸，即要多增加 時(shí)延，發(fā)時(shí)延，發(fā)生該事件的概率為生該事件的概率為 。因此，因此，Y Y部分要增加部分要增加 部分閘門系統(tǒng)的等待時(shí)間為：部分閘門系統(tǒng)的等待時(shí)間為：VmmVVmmVVmXWV2121222Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xi

50、dian Xidian UniversityUniversity多用戶系統(tǒng)多用戶系統(tǒng)v對(duì)于閘門型系統(tǒng)，當(dāng)分組到達(dá)自己的預(yù)約分組傳輸對(duì)于閘門型系統(tǒng)，當(dāng)分組到達(dá)自己的預(yù)約分組傳輸期，比部分閘門型系統(tǒng)還要增加期，比部分閘門型系統(tǒng)還要增加 ，發(fā)生該，發(fā)生該事件的概率為事件的概率為 ，因此因此Y Y部分要增加部分要增加v可以推出閘門型系統(tǒng)的平均等待時(shí)間為可以推出閘門型系統(tǒng)的平均等待時(shí)間為Vm(1)/mVVmm11VVmXWV21221222Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommun

51、ications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)受限的系統(tǒng)服務(wù)受限的系統(tǒng)v所謂服務(wù)受限的系統(tǒng)是指只允許每個(gè)隊(duì)列每次僅傳輸一所謂服務(wù)受限的系統(tǒng)是指只允許每個(gè)隊(duì)列每次僅傳輸一個(gè)分組。個(gè)分組。v由于每次服務(wù)受限，本來可以在一次預(yù)約傳輸期中傳輸由于每次服務(wù)受限，本來可以在一次預(yù)約傳輸期中傳輸結(jié)束的分組，現(xiàn)在要經(jīng)過若干個(gè)循環(huán)才能傳輸完畢。結(jié)束的分組，現(xiàn)在要經(jīng)過若干個(gè)循環(huán)才能傳輸完畢。v每次循環(huán)就要經(jīng)過每次循環(huán)就要經(jīng)過m m個(gè)預(yù)約分組傳輸期個(gè)預(yù)約分組傳輸期 ，即要延，即要延時(shí)時(shí)m mVVXidian Univ.B Broadband r

52、oadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)受限的系統(tǒng)服務(wù)受限的系統(tǒng)v對(duì)對(duì)于部分于部分閘門閘門型系型系統(tǒng)統(tǒng)，到，到達(dá)達(dá)分分組組i所所屬屬的的隊(duì)隊(duì)列平均等待的列平均等待的分分組為組為v在每次在每次僅傳輸僅傳輸一一個(gè)個(gè)分分組組的情的情況況下，到下，到達(dá)達(dá)分分組組i要多等待要多等待 個(gè)個(gè)周期，而每周期，而每個(gè)個(gè)周期的周期的預(yù)約預(yù)約分分組組的的傳輸時(shí)間為傳輸時(shí)間為m ，因，因而而總總的多等待的的多等待的時(shí)間為時(shí)間為

53、mWmNmNEQiilimmWVVWVmmWXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity服務(wù)受限的系統(tǒng)服務(wù)受限的系統(tǒng)v僅僅僅僅要求要求 小于小于1并并不能保不能保證證W是有限的。由于每是有限的。由于每個(gè)個(gè)分分組組的的傳輸傳輸都伴有一都伴有一個(gè)預(yù)約個(gè)預(yù)約期，即其服期，即其服務(wù)時(shí)間為務(wù)時(shí)間為 ，所以必所以必須須有有V1VVVVmVXWv1211212221 VXid

54、ian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversityv設(shè)設(shè)M/G/1M/G/1系統(tǒng)的到達(dá)流具有系統(tǒng)的到達(dá)流具有 n n個(gè)優(yōu)先級(jí)，第個(gè)優(yōu)先級(jí)，第1 1類的分組流具類的分組流具有最高優(yōu)先級(jí)，第有最高優(yōu)先級(jí)，第 n n類的分組流具有最低的優(yōu)先級(jí)類的分組流具有最低的優(yōu)先級(jí)從最高優(yōu)先級(jí)到最低優(yōu)先級(jí)的分組流的到達(dá)率分別為從最高優(yōu)先級(jí)到最低優(yōu)先級(jí)的分組流的到達(dá)率分別為服務(wù)時(shí)間的均值分別為服

55、務(wù)時(shí)間的均值分別為 服務(wù)時(shí)間的二階矩分別為服務(wù)時(shí)間的二階矩分別為第第k k類分組的等待隊(duì)長(zhǎng)、等待時(shí)間和利用率。類分組的等待隊(duì)長(zhǎng)、等待時(shí)間和利用率。 具有優(yōu)先級(jí)的排隊(duì)系統(tǒng)具有優(yōu)先級(jí)的排隊(duì)系統(tǒng) n，21n11121，22221nXXX，kQNkWkXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity具有優(yōu)先級(jí)的排隊(duì)系統(tǒng)具有優(yōu)先級(jí)的排隊(duì)系統(tǒng)v當(dāng)一個(gè)分組正在傳輸，而有一個(gè)高優(yōu)先

56、級(jí)分組到當(dāng)一個(gè)分組正在傳輸，而有一個(gè)高優(yōu)先級(jí)分組到達(dá)時(shí)，有兩種處理方法：達(dá)時(shí)，有兩種處理方法： 允許當(dāng)前正在傳輸?shù)姆纸M傳輸結(jié)束后再傳送高允許當(dāng)前正在傳輸?shù)姆纸M傳輸結(jié)束后再傳送高優(yōu)先級(jí)的分組（稱為非強(qiáng)插優(yōu)先級(jí)，優(yōu)先級(jí)的分組（稱為非強(qiáng)插優(yōu)先級(jí)，Nonpreemptive PriorityNonpreemptive Priority） 高優(yōu)先級(jí)分組要中斷當(dāng)前低優(yōu)先級(jí)分組的傳輸，高優(yōu)先級(jí)分組要中斷當(dāng)前低優(yōu)先級(jí)分組的傳輸，待高優(yōu)先級(jí)分組傳輸結(jié)束后，再接著傳輸?shù)蛢?yōu)待高優(yōu)先級(jí)分組傳輸結(jié)束后，再接著傳輸?shù)蛢?yōu)先級(jí)的分組（該方法稱為強(qiáng)插優(yōu)先級(jí)，先級(jí)的分組（該方法稱為強(qiáng)插優(yōu)先級(jí)，Preemptive Priorit

57、yPreemptive Priority）。）。Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity非強(qiáng)插優(yōu)先排隊(duì)系統(tǒng)非強(qiáng)插優(yōu)先排隊(duì)系統(tǒng) v設(shè)系統(tǒng)能夠處理所有種類的業(yè)務(wù)，即：設(shè)系統(tǒng)能夠處理所有種類的業(yè)務(wù)，即：v平均剩余服務(wù)時(shí)間為平均剩余服務(wù)時(shí)間為 R R，仿效，仿效P-KP-K公式的推導(dǎo)過程，公式的推導(dǎo)過程，來求解各類業(yè)務(wù)的等待時(shí)間。來求解各類業(yè)務(wù)的等待時(shí)間。 121n

58、Xidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity非強(qiáng)插優(yōu)先排隊(duì)系統(tǒng)非強(qiáng)插優(yōu)先排隊(duì)系統(tǒng)v對(duì)于最高（第對(duì)于最高（第1類）優(yōu)先級(jí)隊(duì)列有：類）優(yōu)先級(jí)隊(duì)列有：WRWRNRWQ11111111111RWXidian Univ.B Broadband roadband WWireless ireless C Communications Laboratoryommunicatio

59、ns Laboratory, , Xidian Xidian UniversityUniversity非強(qiáng)插優(yōu)先排隊(duì)系統(tǒng)非強(qiáng)插優(yōu)先排隊(duì)系統(tǒng)v 對(duì)于第對(duì)于第2 2類優(yōu)先級(jí)隊(duì)列有類優(yōu)先級(jí)隊(duì)列有第二項(xiàng)為最高優(yōu)先級(jí)分組的傳輸時(shí)間，第二項(xiàng)為最高優(yōu)先級(jí)分組的傳輸時(shí)間，第三項(xiàng)為第第三項(xiàng)為第2 2優(yōu)先級(jí)隊(duì)列的傳輸時(shí)間，優(yōu)先級(jí)隊(duì)列的傳輸時(shí)間，第四項(xiàng)是已到達(dá)分組在等待過程中，新到達(dá)的最第四項(xiàng)是已到達(dá)分組在等待過程中，新到達(dá)的最高優(yōu)先級(jí)分組的傳輸時(shí)間，利用高優(yōu)先級(jí)分組的傳輸時(shí)間，利用LittleLittle公式，上公式，上式可以寫成式可以寫成 12122112WNNRWQQ2122112WWWRWXidian Un

60、iv.B Broadband roadband WWireless ireless C Communications Laboratoryommunications Laboratory, , Xidian Xidian UniversityUniversity非強(qiáng)插優(yōu)先排隊(duì)系統(tǒng)非強(qiáng)插優(yōu)先排隊(duì)系統(tǒng)v經(jīng)整理得：經(jīng)整理得：v類似地有：類似地有：v平均剩余服務(wù)時(shí)間為：平均剩余服務(wù)時(shí)間為： ）（21121112111RWRW）（kkkRW112111niiiXR1221Xidian Univ.B Broadband roadband WWireless ireless C Communications