《通信網(wǎng)性能分析基礎(chǔ)》課件ch2_通信信源模型

1、第二章 通信信源模型和M/M/1排隊(duì)系統(tǒng)七月 222Simon Denis Poisson Born: 6/21/1781-Pithiviers, FranceDied: 4/25/1840-Sceaux, France“Life is good for only two things: discovering mathematics and teaching mathematics.”七月 223Simon Denis PoissonPoissons father originally wanted him to become a doctor. After a brief apprenti

2、ceship with an uncle, Poisson realized he did not want to be a doctor.After the French Revolution, more opportunities became available for Poisson, whose family was not part of the nobility.Poisson went to the cole Centrale and later the cole Polytechnique in Paris, where he excelled in mathematics,

3、 despite having much less formal education than his peers.七月 224Poissons education and workPoisson impressed his teachers Laplace and Lagrange with his abilities.Unfortunately, the cole Polytechnique specialized in geometry, and Poisson could not draw diagrams well.However, his final paper on the th

4、eory of equations was so good he was allowed to graduate without taking the final examination.After graduating, Poisson received his first teaching position at the cole Polytechnique in Paris, which rarely happened.Poisson did most of his work on ordinary and partial differential equations. He also

5、worked on problems involving physical topics, such as pendulums and sound.七月 225Poissons accomplishmentsHe has many mathematical and scientific tools named for him, including Poissons integral, Poissons equation in potential theory, Poisson brackets in differential equations, Poissons ratio in elast

6、icity, and Poissons constant in electricity. He first published his Poisson distribution in 1837 in Recherches sur la probabilit des jugements en matire criminelle et matire civile. 七月 2262.1泊松過程2.1.1 Poisson過程下面通過描述到達(dá)電話交換機(jī)的呼叫流來引入Poisson過程。到達(dá)交換機(jī)的電話呼叫流或顧客在一定條件下滿足下面幾個(gè)條件：七月 227（1）平穩(wěn)性:在區(qū)間 內(nèi)有k個(gè)呼叫到來的概率與起點(diǎn)

7、a無關(guān)，只與時(shí)間區(qū)間的長度有關(guān)，這個(gè)概率記為 （2）無后效性：不相交區(qū)間內(nèi)到達(dá)的呼叫數(shù)是相互獨(dú)立的；（3）普通性:令 表示長度為t的區(qū)間內(nèi)至少到達(dá)兩個(gè)呼叫的概率， 則 （4）有限性：在任意有限區(qū)間內(nèi)到達(dá)有限個(gè)呼叫的概率為1，即 Poisson過程定義七月 228Poisson過程定義這種輸入過程容易處理，并且應(yīng)用廣泛，被稱為Poisson過程。下面定理2-1描述了Poisson過程的特點(diǎn)，并且（2-1）計(jì)算了在長度為t的時(shí)間內(nèi)到達(dá)k個(gè)呼叫的概率。七月 229定理2-1 定理2-1 對于Poisson呼叫流，長度為t的時(shí)間內(nèi)到達(dá)k個(gè)呼叫的概率 服從Poisson分布，即 （2-1）其中 0為一常

8、數(shù)，表示了平均到達(dá)率或Poisson呼叫流的強(qiáng)度。 七月 2210定理2-1：證明思路：由Poisson流的平穩(wěn)性，求出p0(t)；將0,t)劃分為n等分，求pk(t)；關(guān)鍵步驟說明可用于證明一個(gè)流是泊松流！-性質(zhì)2.1 七月 2211平均呼叫數(shù)在參數(shù)t固定的情況下,如果用 表達(dá) 內(nèi)到的呼叫數(shù) ,那么到達(dá)的平均呼叫數(shù)為七月 2212Poisson分布的方差例2-1：計(jì)算 的方差 。七月 2213Poisson分布的方差七月 2214Poisson過程用途Poisson過程是一個(gè)很簡單的隨機(jī)過程，有許多良好的性質(zhì)，在一定條件下將被用來模擬到達(dá)網(wǎng)絡(luò)節(jié)點(diǎn)的電話呼叫流或數(shù)據(jù)包流，模擬到達(dá)網(wǎng)絡(luò)的各種信源

9、。Poisson過程在任何時(shí)間區(qū)間內(nèi)的到達(dá)率都是一樣，如果到達(dá)率隨著時(shí)間變化，在習(xí)題2.9中有一個(gè)廣義Poisson過程，它的到達(dá)率可以隨著時(shí)間變化。七月 2215Poisson過程的性質(zhì)（2-1）性質(zhì)2-1：m個(gè)Poisson流的參數(shù)分別為 ， ， ，并且它們是相互獨(dú)立的，合并流仍然為Poisson流，且參數(shù)為 。 證明：下面僅僅 考慮的情形。 表示 內(nèi)第一個(gè)流到達(dá)的呼叫數(shù)， 表示 內(nèi)第二個(gè)流到達(dá)的呼叫數(shù)， 表示 內(nèi)到達(dá)的合并流的呼叫數(shù)為說明 服從Poisson流，只需證七月 2216Poisson過程的性質(zhì)（2-1）這個(gè)性質(zhì)也就是說獨(dú)立的Poisson過程是可加的。 七月 2217Pois

10、son過程的性質(zhì)（2-2）性質(zhì)2-2：參數(shù)為 的Poisson流到達(dá)交換局A后，每個(gè)呼叫將獨(dú)立去兩個(gè)不同方向，且去兩個(gè)方向的概率分別為 則Poisson流被分解為兩個(gè)獨(dú)立的Poisson流，參數(shù)分別為 只需證：七月 2218Poisson過程的性質(zhì)（2-2）證明：設(shè) 分別為相應(yīng)的過程在 中到達(dá)的呼叫數(shù)，則為說明 的特性，計(jì)算概率：因?yàn)?這里 另外七月 2219Poisson過程的性質(zhì)（2-2）所以：這個(gè)結(jié)果說明原來的Poisson流按照概率 分 解為2個(gè)獨(dú)立的Poisson流，這兩個(gè)Poisson流的參數(shù)分別為 。這個(gè)結(jié)果也容易被推廣到分解為多個(gè)Poisson 流的情形。 七月 22202.2

11、Poisson過程和負(fù)指數(shù)分布的關(guān)系隨機(jī)變量X滿足 ，或分布函數(shù)為： 這個(gè)分布被稱之為參數(shù)為 的負(fù)指數(shù)分布。這個(gè)分布的概率密度函數(shù)為： 七月 2221負(fù)指數(shù)分布的均值和方差例2-2：計(jì)算參數(shù)為 的負(fù)指數(shù)分布的均值和方差 。七月 2222負(fù)指數(shù)分布的性質(zhì)（2-3）關(guān)于負(fù)指數(shù)分布，有如下無記憶特性：性質(zhì)2-3：假定 服從參數(shù)為 的負(fù)指數(shù)分布，對任意 有 這個(gè)性質(zhì)實(shí)際上表明負(fù)指數(shù)分布的殘余分布和原始分布服從一致的分布，這個(gè)性質(zhì)也被稱為無記憶性?？梢宰C明具有性質(zhì)（2-3）的連續(xù)分布一定是負(fù)指數(shù)分布。七月 2223負(fù)指數(shù)分布的無記憶性證明：七月 2224負(fù)指數(shù)分布的性質(zhì)（2-4）性質(zhì)2-4：假設(shè) 為相互

12、獨(dú)立的兩個(gè)負(fù)指數(shù)分布，參數(shù)分別為 ，令 則：（1） 是一個(gè)以 為參數(shù)的負(fù)指數(shù)分布；（2） 的分布和 誰是較小數(shù)無關(guān)；（3） 七月 2225性質(zhì)2-4：證明證明：（）只需證（）略（）欲證思路：連續(xù)函數(shù)在某點(diǎn)的概率不好算用極限來算七月 2226定理2-2定理2-2：一個(gè)隨機(jī)過程是參數(shù) 的Poisson過程的充分必要條件為呼叫到達(dá)間隔 相互獨(dú)立，且服從相同參數(shù) 的負(fù)指數(shù)分布。 證明：充分性（B）： 假定一個(gè)Poisson過程事件發(fā)生的時(shí)刻為 ,則 是第 次事件的發(fā)生間隔。首先， 然后考慮 的分布，有類似可說明Poisson過程的到達(dá)間隔 獨(dú)立同分布。七月 2227定理2-2必要性證明(BA)反之，假

13、定 為獨(dú)立同分布的負(fù)指數(shù)分布，而 是一個(gè)n階愛爾蘭分布，它的概率密度計(jì)算留作習(xí)題，則 反復(fù)利用分部積分，有 注意到 事件和 事件是一碼事，則 最后，所以， 為一個(gè)參數(shù)為 的Poisson過程。 七月 22282.3生滅過程生滅過程是一種特殊的離散狀態(tài)的連續(xù)時(shí)間馬爾可夫過程，或被稱為連續(xù)時(shí)間馬爾可夫鏈。生滅過程的特殊性在于狀態(tài)為有限個(gè)或可數(shù)個(gè)，并且系統(tǒng)的狀態(tài)變化一定是在相鄰狀態(tài)之間進(jìn)行。生滅過程的極限解或穩(wěn)態(tài)解有很簡單的形式。 七月 2229生滅過程定義如果用 表示系統(tǒng)在時(shí)刻 的狀態(tài)，則 取非負(fù)整數(shù)值。如果 ，稱在 時(shí)刻系統(tǒng)處于狀態(tài) 。當(dāng)滿足下面幾個(gè)條件時(shí)系統(tǒng)稱之為生滅過程。（a）在時(shí)間 內(nèi)系統(tǒng)

14、從狀態(tài) 轉(zhuǎn)移到 的概率為 ，這里 為在狀態(tài) 的出生率； 七月 2230生滅過程定義（b）在時(shí)間 內(nèi)系統(tǒng)從狀態(tài) 轉(zhuǎn)移到 的概率為 ， 這里 為在狀態(tài) 的死亡率；（c）在時(shí)間 內(nèi)系統(tǒng)發(fā)生跳轉(zhuǎn)的概率為 ；（d）在時(shí)間 內(nèi)系統(tǒng)停留在狀態(tài) 的概率為 ；七月 2231生滅過程的狀態(tài)轉(zhuǎn)移圖 根據(jù)條件(C)生滅過程是一個(gè)馬爾可夫鏈狀態(tài)轉(zhuǎn)移圖包含了系統(tǒng)所有狀態(tài)和所有可能的變化七月 2232生滅過程的穩(wěn)態(tài)分布對于生滅過程，許多時(shí)候關(guān)心系統(tǒng)在較長時(shí)間之后的穩(wěn)態(tài)分布首先 ， 表示系統(tǒng)從狀態(tài) 經(jīng)過時(shí)間 后轉(zhuǎn)移到狀態(tài) 的條件概率，則七月 2233生滅過程的穩(wěn)態(tài)分布推導(dǎo)柯爾莫哥洛夫（Kolmogorov）方程七月 2234

15、生滅過程的穩(wěn)態(tài)分布推導(dǎo)假設(shè)穩(wěn)態(tài)分布存在,考慮穩(wěn)態(tài)分布的形式在 時(shí)，其中，如果令則因?yàn)槠咴?2235生滅過程的穩(wěn)態(tài)分布推導(dǎo)（續(xù)）即令 ，由 七月 2236極限定理 定理2-3：對有限狀態(tài)的生滅過程或?qū)M 足條件 的可數(shù)狀態(tài)的生滅過程，穩(wěn)態(tài)分布存在，且與初始條件無關(guān)?？蓴?shù)狀態(tài)時(shí) ；有限狀態(tài)時(shí)，如果有n+1個(gè)狀態(tài)，則 七月 2237關(guān)于生滅過程中微分方程和穩(wěn)態(tài)方程的建立可以依照下面圖2-3簡單完成 微分方程和穩(wěn)態(tài)方程七月 22382.4 M/M/1排隊(duì)系統(tǒng)2.4.1排隊(duì)系統(tǒng)概念在實(shí)際應(yīng)用中，有一大類被稱之為隨機(jī)服務(wù)系統(tǒng)或排隊(duì)系統(tǒng)。在這些系統(tǒng)中，顧客到來的時(shí)刻與進(jìn)行服務(wù)的時(shí)間都是隨機(jī)的，會隨不同的條件

16、而變化。因而服務(wù)系統(tǒng)的狀況也是隨機(jī)的，會隨各種條件而波動。七月 2239排隊(duì)論在電信網(wǎng)絡(luò)中，交換機(jī)就可以看成一種隨機(jī)服務(wù)系統(tǒng).對于不同的電信網(wǎng)絡(luò)，未來將使用不同的排隊(duì)系統(tǒng)模擬不同的電信業(yè)務(wù)交換機(jī)進(jìn)行分析。七月 2240排隊(duì)系統(tǒng)下圖中，外界到來一個(gè)顧客流，當(dāng)顧客到達(dá)系統(tǒng)后，如果有空閑的服務(wù)員就得到服務(wù)。如果沒有空閑的服務(wù)員，有兩種可能情況，或者可以排隊(duì)等待，或者系統(tǒng)拒絕該顧客。七月 2241排隊(duì)系統(tǒng)描述3個(gè)方面的內(nèi)容：（a）輸入過程；（b）服務(wù)時(shí)間；（c）排隊(duì)方式等。下面使用一個(gè)隨機(jī)點(diǎn)移動模型來說明關(guān)于排隊(duì)系統(tǒng)的模型和假設(shè) .七月 2242排隊(duì)系統(tǒng)的假設(shè) 如果只有一個(gè)服務(wù)員，在軸上有一些點(diǎn)從左向

17、右做同速率的勻速直線運(yùn)動.圖2-5中的 表示顧客到達(dá)排隊(duì)系統(tǒng)的到達(dá)間隔，它們均為隨機(jī)變量. 表示不同顧客的服務(wù)時(shí)間，它們也是隨機(jī)變量.關(guān)于 ，滿足下面3個(gè)假設(shè)：七月 2243（1）（2）（3）在上面這個(gè)假設(shè)的基礎(chǔ)上，排隊(duì)系統(tǒng)將相對容易處理并可以根據(jù) 將不同的排隊(duì)系統(tǒng)分類。排隊(duì)系統(tǒng)的假設(shè)七月 2244排隊(duì)系統(tǒng)分類輸入過程和服務(wù)時(shí)間可以分別使用一個(gè)分布來表示M表示到達(dá)為Poisson過程或服務(wù)時(shí)間為負(fù)指數(shù)分布G表示一般分布D表示確定性分布等等。 七月 2245排隊(duì)系統(tǒng)分類在排隊(duì)方式和隊(duì)列的內(nèi)容中主要包括服務(wù)員的數(shù)目，系統(tǒng)中等待顧客的排隊(duì)方式和隊(duì)列的容量等。排隊(duì)的方式可以有先進(jìn)先出（FIFO），后進(jìn)

18、先出（LIFO），優(yōu)先級服務(wù)和隨機(jī)服務(wù)等不同方式。隊(duì)列的容量表示系統(tǒng)中對顧客總數(shù)的限制如果隊(duì)列的容量和服務(wù)員數(shù)目相同，表明系統(tǒng)不可以等待為即時(shí)拒絕系統(tǒng)；如果隊(duì)列的容量為無限大，系統(tǒng)為不拒絕等待系統(tǒng)等。七月 2246基本排隊(duì)模型肯德爾記號ServerQueueArrival關(guān)于不同排隊(duì)系統(tǒng)的記法采用肯德爾（D.G. Kendall） 的記號A/B/C/D/E。A表示輸入過程；B表示服務(wù)時(shí)間；C表示服務(wù)員數(shù)目；D表示系統(tǒng)的容量；E表示排隊(duì)規(guī)則，其中D/E的缺省表示容量無限大和FIFO方式。如M/M/s， G/G/1等。 M/M/1/FCFS M/M/1 /M: 指數(shù)分布 (Markovian)D: 定長分布 (常數(shù)時(shí)間)Ek: k階Erlang 分布G: 普通的概率分布 (任意概率分布)七月 2247排隊(duì)系統(tǒng)對于排隊(duì)系統(tǒng)到達(dá)率 ，服務(wù)率 ，有時(shí)服務(wù)率也被稱為離去率。對于排隊(duì)系統(tǒng)的分析，主要希望得到：（1）隊(duì)長分布或其各種統(tǒng)計(jì)值及其估計(jì)；（2）等待時(shí)間分布或其各種統(tǒng)計(jì)值及其估計(jì)。七月 2248Little公式Little公式描述了任意排隊(duì)系統(tǒng)滿足的關(guān)系，下面通過簡單描述來說明該公式。如果 表示系統(tǒng)中的平均顧客數(shù)， 表示顧客在系統(tǒng)中的平均時(shí)間（這個(gè)時(shí)間有時(shí)也被稱為系統(tǒng)時(shí)間）， 表示單位時(shí)間到達(dá)系統(tǒng)的顧客數(shù)，對于任意排隊(duì)系統(tǒng)，有 七月 2249M/M/1