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