通信網理論基礎 課后問題詳解

通信網理論根底 第二章習題 2.2 求M/M/m〔n〕中，等待時間w的概率密度函數。 解： M/M/m〔n〕的概率分布為： 假定n>m，n≥0，現在來計算概率P{w>x}，既等待時間大于x的概率。 其中，Pj{w>x}的概率為： 可得： 特別的，新到顧客需等待的概率為： 2.4求M/D/1排隊問題中等待時間W的一、二、三階矩m1、m2、m3，D表示服務時間為定值b，到達率為。 解： 其中 從而 又 2.5 求M/B/1，B/M/1和B/B/1排隊問題的平均等待時間，其中B是二階指數分布： 解：M/B/1 B/M/1 B/B/1 設到達的概率密度函數為 設離去的概率密度函數為 假設 2.6 在D/D/1排隊問題中，顧客到達的時間間隔為a，服務時間為b，均為恒定值，且a>b， 求：穩(wěn)定狀態(tài)時系統(tǒng)的隊列長度為k的概率pk，顧客到達時隊列的長度為k的概率vk，顧客離去時隊列的長度dk，以與平均等待時間，并用G/G/1上界公式求出此時的平均等待時間，評論計算結果，并討論a≤b的情況。 解： 由于是D/D/1問題，故子系統(tǒng)運行情況完全確定，第一個顧客到達后，系統(tǒng)無顧客，經過b后，服務完畢，顧客離去，再經過a-b后，下一個顧客到達。 此時有： 顧客不等待時 G/G/1上界公式 當a<b時系統(tǒng)將不穩(wěn)定,以恒定的速率增加顧客，即每隔時間后，系統(tǒng)隊列長度增長1。 2/1即時拒絕系統(tǒng)的呼損，其中E2是二階愛爾蘭分布， 解： 設相鄰呼叫到達間隔為t，如果服務時間，將造成呼損，時無呼損。 2.8在優(yōu)先級別隊列中，A隊為優(yōu)先級，不拒絕，B隊為非優(yōu)先級，只準一人排隊等待〔不計在服務中的〕，且當A隊無人時才能被服務，求各狀態(tài)概率，A隊的平均等待時間和B隊的拒絕概率。 解： 說明： 0狀態(tài)代表系統(tǒng)中無顧客狀態(tài)； i，j狀態(tài)代表系統(tǒng)中正在服務且A隊中有i個顧客，B隊列中有j個顧客排隊的狀態(tài)。 狀態(tài)轉移圖如右，A隊到達率為，B隊到達率為，服務率，系統(tǒng)穩(wěn)定時，應有 可得到特征方程如下: 由于4是差分方程，不妨設其通解為： 代入有： 由于5是非齊次差分方程： 其特征根為： 假設其通解為：代入前式得： 解之，得： 代入3式得： 即： 由正如此條件： 2.9排隊系統(tǒng)中有三個隊列,其到達率分別為公用同一出線路，其中a類最優(yōu)先，即線路有空閑就發(fā)送；b類次之，即a無排隊時可以發(fā)送，c類最低，即a，b類均無排隊時可以發(fā)送，不計正在傳送的業(yè)務，各個隊列的截至隊長為na＝2，nb=1，nc＝0，試列出穩(wěn)定狀態(tài)下的狀態(tài)方程，并計算時，各狀態(tài)的概率和三類呼叫的呼損。 解： r，s，k分別表示a，b，c三隊中等待的呼叫數，狀態(tài)以〔r，s，k〕表示。 穩(wěn)態(tài)方程： 歸一條件 假如 令 C類呼損為： B類呼損為： A類呼損為： 2.10 有一個三端網絡，端點為，邊為與，v1到v3的業(yè)務由v2轉接，設所有的端之間的業(yè)務到達率為，線路的服務率為m的M/M/1問題，當采用即時拒絕的方式時，求： 1) 各個端的業(yè)務呼損。 2) 網絡的總通過量。 3) 線路的利用率。 解： 令：00表示e1,e2均空閑。 10表示e1忙,e2閑〔即e1由v1,v2間業(yè)務占用〕。 01表示e1閑,e2忙〔即e2由v2,v3間業(yè)務占用〕。 11表示e1,e2均忙，且分別由v1v2,v2v3間業(yè)務占用。 ★表示e1,e2均忙，且由v1，v3間業(yè)務占用。 狀態(tài)轉移圖如右： 當時 有如下關系: 又 解之得: 呼損而 通過量 線路利用率 2.11上題中的網假如用于傳送數據包,到達率仍為每秒，平均包長為b比特,邊的容量為c比特/秒,采用不拒絕的方式,并設各端的存儲容量足夠大,求: 1) 穩(wěn)定條件。 2) 網絡的平均時延。 3) 總的通過量。 4) 線路的平均利用率。 解：這是一個無損但有時延的系統(tǒng)。 兩條線路上到達率為：2l，而服務率為：c/b的M/M/1系統(tǒng)。 1) 穩(wěn)定條件為： 2lb/c<1。 2) 網絡的平均時延： 對v1v2和v2v3間的業(yè)務： 對v1v3間的業(yè)務： 3) 系統(tǒng)穩(wěn)定時，總的通過量為：3lb/c。 4) 線路的平均利用率h=r=2lb/c。 一般來說，通過率與利用率均有增加，這是以穩(wěn)定性和時延為代價換來的。 2.12在分組交換系統(tǒng)中，設信息包以泊松率到達，平均到達率為l，但信息包的長度為固定b比特，信道容量為c比特/秒。由于端存儲量的限制，設除了在傳送的包外，只允許有兩個信息包等待傳送，試： 1) 列出關于dr(顧客離去時的隊長)的系統(tǒng)方程 2) 解出個dr. 3) 求平均時延。 4) 求信息包被拒絕的概率。 解： 其中p0是第4個顧客被拒絕離去之后，第3個顧客的剩余壽命中無顧客到達的概率。 這里到達是隨機的，可知： 設 如此 平均時延： 拒絕概率： 2.13有四個端三條邊組成的數據網，如下列圖。端間的信息包分別為和每秒，信息包長度為負指數分布，平均包長為k比特，各信道容量分別為c1，c2和c3，和一起排隊，和一起排隊，和一起排隊，均不拒絕，求 1) 各種業(yè)務的平均時延。 2) 網絡的平均時延。 3) 各信道的平均利用率。 解: 由于均不拒絕且到達和離去均隨機，故3個信道均等效于3個M/M/1系統(tǒng)，其中： C1：到達為。服務為：c1/b C2：到達為。服務為：c2/b C3：到達為。服務為：c3/b C1的平均遲延為 C1的平均遲延為 C1的平均遲延為 網絡的平均時延為： 各信道利用率為： 2.14總線上有4個用戶v1,v2,v3和v4，它們之間以Alopha方式互相通信，信包到達率均為每秒，信息包的長度為b比特；總線上的傳輸速率為c比特/秒，試求通過率r，并大致畫出r與b的曲線關系。 解：r與b的曲線關系如右圖，從直觀上來看，這也是顯然的。 總線上一個包的服務時間秒， 總的呼叫量為：， 通過量為： 通過率： 第3章習題 總線上有4個用戶v1,v2,v3和v4，它們之間以Alopha方式互相通信，信包到達率均為每秒，信息包的長度為b比特；總線上的傳輸速率為c比特/秒，試求通過率r，并大致畫出r與b的曲線關系。 解：r與b的曲線關系如右圖，從直觀上來看，這也是顯然的。 總線上一個包的服務時間秒， 總的呼叫量為：， 通過量為： 通過率： 習題3.2 設在一個純ALOHA系統(tǒng)中，分組長度ms，總業(yè)務到達率 pkt/s，試求一個消息成功傳輸的概率。 解：由題意，ms，pkt/s，如此系統(tǒng)的總業(yè)務量為 純ALOHA系統(tǒng)吞吐量滿足，一個消息成功傳輸的概率為 假如系統(tǒng)改為S-ALOHA系統(tǒng)，試求這時消息成功傳輸的概率。 解：S-ALOHA系統(tǒng)的吞吐量滿足，這時消息成功傳輸的概率為 在S-ALOHA系統(tǒng)中，試求一個消息分組傳輸時和另一個分組碰撞的概率。 解：其概率為：。 習題設在一個S-ALOHA系統(tǒng)中每秒共發(fā)送120次，其中包括原始發(fā)送和重發(fā)。每次發(fā)送需占用一個12.5 ms的時隙。試問： （1） 系統(tǒng)的歸一化總業(yè)務量等于多少？ （2） 第一次發(fā)送就成功的概率等于多少？ （3） 在一次成功發(fā)送前，剛好有兩次碰撞的概率等于多少？ 解：由題意，=120次/秒， =12.5 ms。 〔1〕 。 〔2〕 。 〔3〕 。 習題 設一條長度為10 km的同軸電纜上，接有1000個站，信號在電纜上傳輸速度為200 m/us，信號發(fā)送速率為10 Mb/s，分組長度為5000 b。試問： （1） 假如用純ALOHA系統(tǒng)，每個站最大可能發(fā)送分組速率等于多少？ （2） 假如用CSMA/CD系統(tǒng)，每個站最大可能發(fā)送分組速率等于多少？ 解：〔1〕純ALOHA中，發(fā)送分組不用等待。理想情況下，各站一個接一個發(fā)送分組，互不干擾，發(fā)送分組的最大速率為 pkt/s 〔2〕對于CSMA/CD系統(tǒng)，信號傳輸速率為200 m/s，對于10 km電纜，單程傳播時間為 CSMA/CD系統(tǒng)發(fā)送一個分組必須等待的時間為：2t=100 us=0.1 ms。 故每個站的最大可能發(fā)送分組速率為：。 第四章習題答案 例題1：環(huán)上有k個端〔3≤k≤n〕，此k個端的選擇方式有種；對于某固定的k端來說，考慮可以生成的環(huán)，任指定一個端，下個端的選取方法公有k-1種，再下端的選法有k-2種，等等，注意，這樣生成的環(huán)可按兩種試圖順序取得，故有種，總的環(huán)數為 例題2：某一固定邊e確定了兩個端，經過e的環(huán)數按其過余下端進展分類，假如環(huán)再過k個端〔1≤k≤n-2〕，有選法種；對于某固定端來說，自然可以生成k!個環(huán)，從而總的環(huán)數為個。 例題3：兩個固定端之間的徑按其經過端數分類，其中有一條不經過其他端的徑，假如經過k個端，〔1≤k≤n-2〕，如此對于第一個端有〔n-2〕種選擇，第二個端有〔n-3〕種選擇，第k個端有〔n-k-1〕種選擇，共有 總的徑數為 試求圖3-52中圖的主樹數目，并列舉所有的主樹。 圖3-52 解：為圖的端編號為v1,v2,v3,v4。 取v3為參考點，有： 所得主樹見下: 4.6 試證明端數n大于4的連接圖都是非平面圖，并求n=2，3，4的全連接圖為對偶圖。 證明：設有n個端的全聯接圖為Kn因為K5是非平面圖，而當n>5時K5是Kn的子圖，從而Kn〔n>5〕均不是平面圖。一下是對偶圖〔注意K4為自對偶圖〕。 一個圖的鄰接矩陣如左，畫出此圖，并求各端之間的最小有向徑長。 對所繪制圖形的端點進展編號，得鄰接矩陣。 解：首先作出圖形： 經計算： 因而有 其余有向徑長均為 ∞，或不存在。 圖有六個端，其無向距離矩陣如下： 1. 用P算法，求出最短樹。 2. 用K算法，求出最短樹。 3. 限制條件為兩端間通信的轉接次數不超過2的最短樹。 解： 1. P算法求解： 2. K算法求解： 按最小邊長順序取得： 此結果意味著最短樹不唯一。 3. 原圖有一個邊長全為1的根本子圖G1，要求轉接次數小于等于2，假如選取G1的任何4個連續(xù)頂點，,作為根底，然后再按要求增加邊，例如以為根底，增加，得到一個樹長為7轉接次數小于等于2的樹T1，事實上，以任何4個連續(xù)頂點均可得到樹長為7的轉接次數小于等于2的樹 圖有六個端，端點之間的有向距離矩陣如下： 1. 用D算法求V1到所有其他端的最短徑長與其路徑。 2. 用F算法求最短徑矩陣和路由矩陣，并找到V2至V4和V1至V5的最短徑長與路由。 3. 求圖的中心和中點。 解： 1、D算法 V1 V2 V3 V4 V5 V6 指定 最短徑長 0 ∞ ∞ ∞ ∞ ∞ V1 W1＝0 9 1 3 ∞ ∞ V3 W13＝0 9 3 2 ∞ V5 W15＝0 8 3 7 V4 W14＝0 8 7 V3 W16＝0 8 V2 W12＝0 2、F算法 最短路徑矩陣與最短路由陣為W5，R5 有向距離為4，有向距離為2 3、 中心為V3或V5 中心為V2 第五章習題答案 求如下圖中Vs到Vt的最大流量fst,圖中編上的數字是該邊的容量。 解： 此題可以利用M算法，也可以使用最大流－最小割簡單計算可知： 可知：最大流為12，可以安排為fs1 = 3,，fs2 =5，f12=1，f2t＝4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。 試移動3.54圖中的一條邊，保持其容量不變，是否能增大fst？如果可以，求此時的最大值，但假如所有轉接端v1v2v3和v4的轉接容量限制在4，如此情況將如何？ 解： 依然按照最大流－最小割定理，假如能依一邊從X找到部至割中，自然可以增大流量，可以將e34移去，改為：e41 或者e42均可，使總流量增至12＋2＝14。 當vi(i = 1,...4)的轉接容量限制到4時，等效圖為右圖，對于3.11中的流量分配，在此題限制下，假如將fs2由5改為4即得到一個流量為11的可行流。 但假如， 如此，換句話說就是11已是最大流。 s和Vt間要求有總流量fst＝6，求最優(yōu)流量分配，圖中邊旁的兩個數字前者為容量，后者為費用。 解： 圖1 此題可以任選一個容量為6的可行流，然后采用負價環(huán)法，但也可用貪心算法，從Vs出發(fā)的兩條線路費用一樣，但進入Vt的兩條路徑費用為7和2，故盡可能選用費用為2的線路，得如下圖1。 再考慮V0，進入V0的兩條路徑中優(yōu)先滿足費用為3的路徑，得：圖2，很容易得到最后一個流量為fst=6的圖3，邊上的數字為流量安排。總的費用為 易用負價環(huán)驗證圖4的流量分配為最優(yōu)流量分配。 19 / 19