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