通信网理论基础 课后答案

通信网理论基础

第二章习题

2.2 求M/M/m（n）中，等待时间w的概率密度函数。 解：

M/M/m（n）的概率分布为：

m1(m)k(m)m1nm1p0p0

k!m!1r01(m)kk!p0pkmmkk!p00n0km1mknkn

假定n>m，n≥0，现在来计算概率P{w>x}，既等待时间大于x的概率。

P{wx}pj•Pj{wx}

j0其中，Pj{w>x}的概率为：

Pj{wx}0

0jm1mxPj{wx}ePj{wx}1i0jm(mx)ii!mjn1 mjn可得：

P{wx}Pjejmi0n1jmmx(mx)iPni!mmn1jjmmx(mx)inP0em!jmi!i0

mmnm1mx(mx)iminP0ePnm!i!1i0若n则P0(m)m(m)xP{wx}e1m!特别的，新到顾客需等待的概率为：

P0(m)mP{W0}1m!

；.

.

nm1nm2mmP0(x)imxmm(x)fw(x)e[(m)mm!(1)i!(nm1)!i0而(m)nm1m](nm1)!n

在n注：mmP0fw(x)m(m)e(m)xm!(1)m1k0

P{w0}PkP{w}Pn

2.4求M/D/1排队问题中等待时间W的一、二、三阶矩m1、m2、m3，D表示服务时间为定值b，到达率为。 解：

s(1)G(s)

sB(S)stsb其中 B(s)(tb)edte

0

s(1)G(s)从而

sesbiG(s)gs 又 ii0

j(sb)gisisj!j0i0s(1) 

1(1)(2b32b4)b2(1)g0 g1 g2 321b12(1b)2(1b)(12b)(1)b4g324(1b)4(b)

b2m1G(0)g12(1)(2)b3m2G(0)g226(1)2(12)b4m3G(0)g364(1)3

2.5 求M/B/1，B/M/1和B/B/1排队问题的平均等待时间W，其中B是二阶指数分布：

f(t)1e1t(1)2e2t解：M/B/1

；.

1,2001

.

B(S)01(1)2f(t)edt1s2sstw1B(0)112w2B(0)2m211222w22(1)12122(1)122

B/M/1

122(1)221w121B()1(1)212取01的根令1122

1121(12)22(12)(12)2w(1)1121(12)22(12)(12)(1121(12)22(12)(12))

B/B/1

设到达的概率密度函数为设离去的概率密度函数为假设1f(t)1e1t(1)2e2t

f(t)3e3t(1)4e4t

24

213A(s)B(s)(1)211s2s(1)2(1)211A(s)B(s)1ss1ss221121242t2s2s421(1)2ss(1s)(2s)(1s)(2s)(1s)(2s)(1s)(2s)2取(s)s(ts)(1s)(2s)w(s)k(s)(s)s(ts)(1s)(2s)klims0(s)ts12k(1s)(2s)(ts)tSw(s)wSw(s)s0'12(12)t12t其中；.

2221222((12)1(22)22(1)121(1)2).

2.6 在D/D/1排队问题中，顾客到达的时间间隔为a，服务时间为b，均为恒定值，且a>b， 求：稳定状态时系统的队列长度为k的概率pk，顾客到达时队列的长度为k的概率vk，顾客离去时队列的长度dk，以及平均等待时间，并用G/G/1上界公式求出此时的平均等待时间，评论计算结果，并讨论a≤b的情况。 解：

由于是D/D/1问题，故子系统运行情况完全确定，第一个顾客到达后，系统无顾客，经过b后，服务完毕，顾客离去，再经过a-b后，下一个顾客到达。

此时有：

bapk(ab)a1rkdk0k1k0k0k0

顾客不等待时w0

r2t2w2t(1)G/G/1上界公式

22p()(a)w0p(t)(tb)t0

22wt02t(1)当aab时间后，系统队列长度增长ab2.7求M/E2/1即时拒绝系统的呼损，其中E2是二阶爱尔兰分布，b()(2)2e2

解：

设相邻呼叫到达间隔为t，如果服务时间t，将造成呼损，t时无呼损。

pc(t)b()dt则024

et(2)2e2ddtt(2)2

pca(t)b()ddt0t

2.8在优先级别队列中，A队为优先级，不拒绝，B队为非优先级，只准一人排队等待（不计在服务中的），且当A队无人时才能被服务，求各状态概率，A队的平均等待时间和B队的拒绝概率。

；.

.

解：

说明：

0状态代表系统中无顾客状态； i，j状态代表系统中正在服务且A队中有i个顾客，B队列中有j个顾客排队的状态。

状态转移图如右，A队到达率为1，B队到达率为2，服务率，系统稳定时，应有112200 020 1111 01 111

11可得到特征方程如下:

(12)P0P00()P(PP)()P12000110120(1)P012P00P11()PPPi012i,01i1,0i1,0(1)Pi,11Pi1,1Pi1,12Pi,0i0

i由于4是差分方程，不妨设其通解为：pi0p00x 代入有：

123 45(112)p00xi1p00xi1p00xi1x2(112)x10

0x11121122122212x0222

由于5是非齐次差分方程：

pi1,1(1p1)pi,11pi1,12pi,00 其特征根为：a1

ii假设其通解为：pi,1A1Bx0代入前式得：

i1ii1iBx0(11)Bx01Bx02p00x00

解之，得：B代入3式得：

p00pi,1Ap00x0i1i

11p012p00p11 即：

；.

.

Ap00112x0iipi，p1xx1001201ippxi，000p0012p0

由正则条件：

p012p0112x01i1i011p01112112x0wAr1pr01r，0pr，1r1p100r0112x01rp00112x0112rPCBpr，p1xx10012010rr0r0

p00112x0p00111x0

2.9排队系统中有三个队列,其到达率分别为

a,b,c公用同一出线路，其中a类最

优先，即线路有空闲就发送；b类次之，即a无排队时可以发送，c类最低，即a，b类均无排队时可以发送，不计正在传送的业务，各个队列的截至队长为na＝2，nb=1，nc＝0，试列出稳定状态下的状态方程，并计算

0abcaa0 0 0bab1 0 0ba2 0 0abc时，各状态的概率和三类呼叫

0 1 01 1 02 1 0的呼损。

解：

r，s，k分别表示a，b，c三队中等待的呼叫数，状态以（r，s，k）表示。 稳态方程：

；.

.

(abc)p0p000(ab)p000(p010p100)(abc)p0(ab)p100p200ap000(b)p200ap100(a)p010bp000p110

p210ap110bp200(a)p110bp100ap010p210归一条件

p0pi,j,k1 若 abc 令p010p110p210a

p0003p0p100p2003233p0222133p022213293124p0222163154125p0222164155126p02221

2221p012627536427314251

C类呼损为：B类呼损为：A类呼损为：

pc1p0

pBp010p110p210

pAp210p200

2.10 有一个三端网络，端点为v1,v2,v3，边为1e(v1,v2)及e2(v2,v3)，v1

到v3的业务由v2转接，设所有的端之间的业务到达率为，线路的服务率为的问题，当采用即时拒绝的方式时，求：

1) 各个端的业务呼损。 2) 网络的总通过量。 3) 线路的利用率。

解：

令：00表示e1,e2均空闲。

10表示e1忙,e2闲（即e1由v1,v2间业务占用）。

01表示e1闲,e2忙（即e2由v2,v3间业务占用）。 11表示e1,e2均忙，且分别由v1v2,v2v3间业务占用。

；.

.

★表示e1,e2均忙，且由v1，v3间业务占用。

状态转移图如右：

13

当121323时 有下列关系:

★230 0230 11212ptp003pppp000110*p10p00p11ppp0100112p11p01p10

又

1 01 1

p*p01p10p00 解之得: p12p11p00这里p0011322

232pp1ppp1p呼损13而23 12000100132132322通过量T(1p12)(1p13)(1p23)132

22线路利用率p*p11(p10p01)/2132

2.11上题中的网若用于传送数据包,到达率仍为每秒，平均包长为b比特,边的容量为c比特/秒,采用不拒绝的方式,并设各端的存储容量足够大,求:

1) 稳定条件。

2) 网络的平均时延。 3) 总的通过量。

4) 线路的平均利用率。

解：这是一个无损但有时延的系统。

两条线路上到达率为：2，而服务率为：c/b的M/M/1系统。

1) 稳定条件为： 2b/c<1。 2) 网络的平均时延：

对v1v2和v2v3间的业务：w111

(1)c2b对v1v3间的业务：w22w12c2b

3) 系统稳定时，总的通过量为：3b/c。

；.

.

4) 线路的平均利用率==2b/c。

一般来说，通过率与利用率均有增加，这是以稳定性和时延为代价换来的。

2.12在分组交换系统中，设信息包以泊松率到达，平均到达率为，但信息包的长度为固定b比特，信道容量为c比特/秒。由于端内存储量的限制，设除了在传送的包外，只允许有两个信息包等待传送，试：

1) 列出关于dr(顾客离去时的队长)的系统方程 2) 解出个dr. 3) 求平均时延。

4) 求信息包被拒绝的概率。 解：

d0d0q0d1q0ddqdqdq0111201d2d0q2d1q2d2q1d3p0 （）d3d0q3d1q3d2q2d31p03di1i0其中p0是第4个顾客被拒绝离去之后，第3个顾客的残余寿命中无顾客到达的概率。 这里到达是随机的，可知：

p0b/c0ctbcedt1ecb b

设

b

cq0e0b则

bdebdec0q1ebde21q0d1d0q00q22ebd22e

d2e21ed0

；.

.

3222e12eed02d3e1 e1di1d0423221e122ee2

平均时延：

mmvb31b32swbcvd1mde2ed0 12c22c22m12m1

拒绝概率：

pCd3

2.13有四个端三条边组成的数据网，如图所示。端间的信息包分别为和每秒，信息包长度

为负指数分布，平均包长为k比特，各信道容量分别为c1，c2和c3，和一起排队，和一起排队，和一起排队，均不拒绝，求

1) 各种业务的平均时延。 2) 网络的平均时延。 3) 各信道的平均利用率。 解:

由于均不拒绝且到达和离去均随机，故3个信道均等效于3个M/M/1系统，其中： C1：到达为1213。服务为：c1/b C2：到达为1242。服务为：c2/b

C3：到达为1343。服务为：c3/b

11C1的平均迟延为

1(11)c11213b

11C1的平均迟延为

2(12)c21242b

11C1的平均迟延为

3(13)c31343b

；.

.

s12sc1sc21c11213b

c21242b1s13sc1sc31c11213b1

c31343b1s42sc2c21242bs43sc31c11343b

网络的平均时延为：s各信道利用率为：

12s1213s1342s4243s4312134243

c111213b/c1c221242b/c2 c331343b/c3

2.14总线上有4个用户v1,v2,v3和v4，它们之间以Alopha方式互相通信，信包到达率均为每秒，信息包的长度为b比特；总线上的传输速率为c比特/秒，试求通过率r，并大致画出r与b的曲线关系。

解：r与b的曲线关系如右图，从直观上来看，这也是显然的。

总线上一个包的服务时间总的呼叫量为：a通过量为：r通过率：rbc秒，

12bc，

ae2a

b12e2a c

r第3章习题

习题 3.1总线上有4个用户v1,v2,v3和v4，它们之间以Alopha方式互相通信，信包到达率均为每秒，信息包的长度为b比特；总线上的传输速率为c比特/秒，试求通过率r，并大致画出r与b的曲线关系。

；.

.

解：r与b的曲线关系如右图，从直观上来看，这也是显然的。

总线上一个包的服务时间b秒，

c总的呼叫量为：a12b，

c通过量为：rae通过率：rr

2a

b12e2a c

习题3.2 设在一个纯ALOHA系统中，分组长度20ms，总业务到达率t10 pkt/s，试求一个消息成功传输的概率。

解：由题意，20ms，t10pkt/s，则系统的总业务量为

Pt10201030.2

纯ALOHA系统吞吐量满足pPe2P，一个消息成功传输的概率为

PspPe2Pe20.2e0.40.67

若系统改为S-ALOHA系统，试求这时消息成功传输的概率。

解：S-ALOHA系统的吞吐量满足pPeP，这时消息成功传输的概率为

PspPePe0.20.82

在S-ALOHA系统中，试求一个消息分组传输时和另一个分组碰撞的概率。 解：其概率为：1Ps10.820.18。

习题3.3设在一个S-ALOHA系统中每秒共发送120次，其中包括原始发送和重发。每次发送需占用一个12.5 ms的时隙。试问：

（1） 系统的归一化总业务量等于多少？ （2） 第一次发送就成功的概率等于多少？

（3） 在一次成功发送前，刚好有两次碰撞的概率等于多少？

解：由题意，t=120次/秒， =12.5 ms。 （1） Pt12012.51031.5。 （2） P0ete1.50.223。

；.

.

（3） p31ePeP10.2230.2230.135。

22

习题 3.4 设一条长度为10 km的同轴电缆上，接有1000个站，信号在电缆上传输速度为200 m/us，信号发送速率为10 Mb/s，分组长度为5000 b。试问：

（1） 若用纯ALOHA系统，每个站最大可能发送分组速率等于多少？

（2） 若用CSMA/CD系统，每个站最大可能发送分组速率等于多少？

解：（1）纯ALOHA中，发送分组不用等待。理想情况下，各站一个接一个发送分组，互不干扰，发送分组的最大速率为

10M/500010002 pkt/s

（2）对于CSMA/CD系统，信号传输速率为200 m/s，对于10 km电缆，单程传播时间为 t10103/20050 s

CSMA/CD系统发送一个分组必须等待的时间为：2t=100 us=0.1 ms。 故每个站的最大可能发送分组速率为：10M0.1 ms/50000.2 pkt/s。

第四章习题答案

例题1：环上有k个端（3≤k≤n），此k个端的选择方式有Cn种；对于某固定的k端来说，考虑可以生成的环，任指定一个端，下个端的选取方法公有k-1种，再下端的选法有k-2种，等等，注意，这样生成的环可按两种试图顺序取得，故有

kCnk3nk(k1)!种，总的环数为2(k1)! 2k例题2：某一固定边e确定了两个端，经过e的环数按其过余下端进行分类，若环再过k个端（1≤k≤n-2），有选法Cn2种；对于某固定端来说，自然可以生成k!个环，从而总的环

kC数为n2k!个。

k3n例题3：两个固定端之间的径按其经过端数分类，其中有一条不经过其他端的径，若经过k个端，（1≤k≤n-2），则对于第一个端有（n-2）种选择，第二个端有（n-3）种选择，第

n2(n2)!(n2)!1k个端有（n-k-1）种选择，共有 总的径数为 (nk2)!(nk2)!k1

；.

.

4.5 试求图3-52中图的主树数目，并列举所有的主树。

解：为图的端编号为v1,v2,v3,v4。 取v3为参考点，有：

3S11

图3-52

112008 2所得主树见下:

4.6 试证明端数n大于4的连接图都是非平面图，并求n=2，3，4的全连接图为对偶图。 证明：设有n个端的全联接图为Kn因为K5是非平面图，而当n>5时K5是Kn的子图，从而Kn（n>5）均不是平面图。一下是对偶图（注意K4为自对偶图）。

；.

.

4.7

00C00

1000010010 10

已知一个图的邻接矩阵如左，画出此图，并求各端之间的最小有向径长。

对所绘制图形的端点进行编号，得邻接矩阵。

解：首先作出图形：

v1

经计算：

C

v2v3v410100010

0001000000C200因而有

01000001 C300000000d(v1,v3)2

001000

000000d(v1,v4)1

d(v1,v2)1 d(v2,v3)1 d(v3,v4)1

d(v2,v4)2

其余有向径长均为 ∞，或不存在。

4.8 图有六个端，其无向距离矩阵如下：

v1v1v2v3v4v5v6v2012321v3v4v5v6123210123210123210123210123120

1. 用P算法，求出最短树。 2. 用K算法，求出最短树。

3. 限制条件为两端间通信的转接次数不超过2的最

短树。

解：

1. P算法求解：

；.

.

eeeev1v1,v2v1,v2,v3v1,v2,v3,v6v1,v2,v3,v6,v5 ev1,v2,v3,v6,v5,v412231665342. K算法求解：

按最小边长顺序取得： e12e23e34e45e561此结果意味着最短树不唯一。

3. 原图有一个边长全为1的基本子图G1，要求转接次数小于等于2，若选取G1的任何4个

连续顶点，vivi1vi2vi3,作为基础，然后再按要求增加边，例如以v1v2v3v4为

基础，增加v5v6，得到一个树长为7转接次数小于等于2的树T1，事实上，以任何4个连续顶点均可得到树长为7的转接次数小于等于2的树

4.9 图有六个端，端点之间的有向距离矩阵如下：

1. 用D算法求V1到所有其他端的最短径长及其路径。 v1v2v3v4v5v62. 用F算法求最短径矩阵和路由矩阵，并找到V2至V4v10913和V1至V5的最短径长及路由。 v210473. 求图的中心和中点。 v2013v4v5v65062872202750 解：

1、D算法

；.

.

V1 0 2、F算法

V2 ∞ 9 9 8 8 8 V3 ∞ 1 V4 ∞ 3 3 3 V5 ∞ ∞ 2 V6 ∞ ∞ ∞ 7 7 指定 V1 V3 V5 V4 V3 V2 最短径长 W1＝0 W13＝0 W15＝0 W14＝0 W16＝0 W12＝0 最短路径矩阵及最短路由阵为W5，R5

v2v1v4有向距离为4，v1v3v5有向距离为2

906901161690116169011166139011166138078681405221205221205221205221205221204223083450810345081034508734507734507723120223120223120271202712021671202750750750011R0001011R1001011R2021011R3333011R4333011R5533505525201321201321310533200020201021201021310333310333411033330333310333310333411033411033335505400044411041411041335505335505055505055505255505000660000660000660012W07012W17012W277012W3744012W4744012W5644；.

750101112750786750000660444660555660.

3、 MaxWij(8,8,7,8,7,8) 中心为

j5V3或V5

Wj5ij(21,18,21,27,24,23) 中心为V2

第五章习题答案

5.1求下图中Vs到Vt的最大流量fst,图中编上的数字是该边的容量。 解：

本题可以利用M算法，也可以使用最大流－最小割简单计算可知：

Xvs,v3,v4

Xv1,v2,vt

CX,X351312

可知：最大流为12，可以安排为

fs1 = 3,，

fs2 =5，f12=1，f2t＝4，f1t=4，fs3=1，fs4=3，f3t=1，f4t=3。

5.2试移动3.54图中的一条边，保持其容量不变，是否能增大fst？如果可以，求此时的最大值，但若所有转接端v1v2v3和v4的转接容量限制在4，则情况将如何？ 解：

依然按照最大流－最小割定理，若 v1v1'能依一边从X找到X内部至割

24

62(X,X)中，自然可以增大流量，可以

将e34移去，改为：e41 或者e42均可，使总流量增至12＋2＝14。 当vi(i = 1,...4)的转接容量限制到4时，等效图为右图，对于3.11中的流量分配，在本题限制下，若将fs2由5改为4即得到一个流量为11的可行流。 但若

''X*vS,v3,v3v4,v4,v2Vs3v244v2'v3'Vt52v364132v44v4'，

X*''v1,v1,v2,vt 则

C(X*,X*)134311，换句话说就是11已是最大流。

；.

.

5.3图3.55中的Vs和Vt间要求有总流量

fst＝6，求最佳流量分配，图中边旁的两个数

Vs字前者为容量，后者为费用。 解：

本题可以任选一个容量为6的可行流，然后采用负价环法，但也可用贪心算法，从Vs出发的两条线路费用一样，但进入Vt的两条路径费用为7和2，故尽可能选用费用为2的线路，得下图1。

再考虑V0，进入V0的两条路径中优先满足费用为6,33的路径，得：图2，很容易得到最后一个流量为5,7fst=6的图3，边上的数字为流量安排。总的费用

Vt为

3,2 3,2 1,1 2 图1

,324,3,4

L3232132411

23422752易用负价环验证图4的流量分配为最佳流量分配。

123Vt34Vs Vs1 4 4图 22图 3 2图 4

；.

4 3 2 2 VtVs 2 Vt 2