通信网理论基础作业答案

2.182.252.262.252.26，重点关注从B发送往AB的SN和窗口以及节点A发出的包的RN（假设所有的帧都携有数据包。Figure2.25goback41B端被错误的接收而B1A传完所有的窗数据，超时然1。Figure图.6在oack4RR2（A前窗口的最后一个包A包含R=3信息的错误帧当他后面的返回帧保持等待状态直到节点A发送了他全A。0123412NodeNode000111112Packets Figure2.26重Tmax（2.31）（aFigureGoback7ARQ61ack还0的重传。request0，所以显然至少需要返回第二个request=mm-1个帧已经接收完毕，可以进行窗移至少两个request（SNRN）来说，要返回两个request直到第二个request到达发送方需要最多2Tmax+Tmin+Td的时间。可得下式：这里Tmax

(b)requestrequest且在发送方这里Tmax

requestp,request想要成功发送时至少已经多传输了1/（1-p）个长帧而第一个长帧即RN=0时隙传输结束后发出的request=0能否传输成功并不影响发送第二个request的判断。所以有：

p1Tmax

这里TmaxT

3.810个数据包的泊松过程。上图表示数据包的到达，𝒓𝟏,𝒓𝟐分别表示该数据包与其前后相邻数据包的时n包与第n-1个数据包到达的时间间隔𝒓𝟏要大于第n-1个数据包的传输时间𝑿𝟏第n+1个数据包到达的时间间隔要大于第n个数据包的传输时间𝑿𝟐。∴𝐏{数据包既不和它前面的数据包也不和它后面的数据包发生碰撞}𝐏{𝒓𝟏>𝑿𝟏，𝒓𝟐>𝑿𝟐}=𝐏{𝒓𝟏>𝑿𝟏}∗𝐏{𝒓𝟐>后所有数据包都不发生碰撞。对于第n个数据包来说，只要它在传输过程中与第n+1个数据包不发生碰撞，成功传输，那么与第n+2、n+3…个数据包（即之设：𝑷𝟏=𝑷{与该数据包之前所有数据包不碰撞}，则𝑷{数据包不和其他数据包发生碰撞}=𝑷𝟏∗𝐏{𝒓𝟐>根据题意，数据包的到达率：𝛌=𝟏𝟎包由于每个数据包的传输时间X=20ms，即𝑿𝟏𝑿𝟐𝟐𝟎𝒎𝒔为P{𝒓>𝟐𝟎}（𝒓为数据包到达的时间间隔。由泊松定理可知：在时间间P(𝑛,𝑡)

𝝀𝒏∙20ms20ms0个数据包，将n=0代入泊松，得：P{𝒓>𝟐𝟎}

𝝀𝟎∙

=𝒆−𝝀𝒕=

=

∴𝐏{𝒓𝟏>𝑿𝟏}=𝐏{𝒓𝟐>𝑿𝟐}=𝐏{𝐫>𝟐𝟎}=𝐏{数据包既不和它前面的数据包也不和它后面的数据包发生碰撞}𝒆−𝟎.𝟐∗𝒆−𝟎.𝟐=𝒆−𝟎.𝟒=𝟎.X=20ms20ms的情况下，先到达的数据包肯定先离开，所以只需保证第n个数据包与第n-1个数据包不发生碰撞，则与之前所有数据包都不发生碰撞。∴𝑷𝟏=𝑷{与该数据包之前所有数据包不碰撞}=𝐏{𝒓𝟏>=𝐏{𝐫>𝟐𝟎}=𝒆−𝝀𝒕=𝑷{数据包不和其他数据包发生碰撞𝑷𝟏𝐏{𝒓𝟐>𝑿𝟐}=𝒆−𝟎.𝟒=𝟎. ∞系统的到达速率λ=10包/𝑠，离开速率μ=1

=50包/𝑠 间X服从负指数分布，期望为T=1=20ms，则负指数分布的参数为1 μ。所以X的概率密度函数为：f(𝑥)=μe−μxx≥0所以第n个数据包不与第n-1个数据包发生碰撞的概率𝐏{𝒓𝟏>𝑿𝟏}即为𝑿𝟏0（为负指数分布乘以在该时间条件下𝒓𝟏>𝑿𝟏的概率（根据泊松分布，即在X达的概率n-1个数据包的传输时间𝑿𝟏∞𝐏{𝒓𝟏>𝑿𝟏}=∫𝑷{𝑿𝟏=𝐗}∗𝑷{𝒓𝟏>𝑿|𝑿𝟏= 𝑷{𝒓𝟏>𝑿}∗𝑷{𝑿𝟏==∫𝑷{𝑿𝟏=𝐗}∞

= ∞=∫𝑷{𝑿𝟏=𝐗}∗𝑷{𝒓𝟏>𝑿}𝐝𝐗=∫μe−μX∗

0=μ∫e−(μ+𝝀)X𝐝𝐗0

−(𝝁+

e−(μ+𝝀)X|∞

𝝁+

=

}=

}=∴𝐏{数据包既不和它前面的数据包也不和它后面的数据包发生碰撞=𝐏{𝒓𝟏>𝑿𝟏}∗𝐏{𝒓𝟐>𝑿𝟐}=𝟑𝟔=𝟎.∴𝑷𝟏=𝑷{与该数据包之前所有数据包不碰撞

=𝑷{稳态下系统中没有数据包}=𝒑𝟎=

𝝁=∴𝑷{数据包不和其他数据包发生碰撞}=

}=𝒆−𝟎.𝟐∗𝟓𝟎.3.10证明：3.11到的时间，A(t)t内系统到达的数据个数，时间间隔τ=𝑡𝑛+1−𝑡𝑛P{𝜏𝑛≤s}=1−𝑒−𝜆s且相互独立 （对于任意的t0，δ0（下式中ο(δ)满足limο(δ)0，有：𝛿→0P{𝐴(𝑡+δ)−𝐴(𝑡)=0}=1−𝜆∗𝛿+ （P{𝐴(𝑡+δ)−𝐴(𝑡)=1}=𝜆∗𝛿+ （P{𝐴(𝑡+δ)−𝐴(𝑡)≥2}=ο(δ) （3.14）解：设𝑡n表示第n到达的时间，A(t)t内系统到达的数据个数，τ𝑛=𝑡𝑛+1−𝑡𝑛，因为到达时间间隔符合指数分布，所以该数据流可看作是泊松数据流，所以数据的到达时间服从泊松分布，所以对于s≥0有：P{𝜏𝑛>s}=P{A(𝑡n+𝑠)−A(𝑡n)=0}P{𝜏𝑛≤s}=1−

𝑒−𝜆s=若𝜏𝑛的概率与𝜏𝑛−1𝜏𝑛与𝜏𝑛−1𝜏1…𝜏1…𝜏𝑛P{𝜏𝑛>s|𝜏𝑛−1=𝜏}=P{𝜏𝑛>s}P{𝜏𝑛>s|𝜏𝑛−1=𝜏}=P{A(𝑡n+𝑠)−A(𝑡n)=0|𝜏𝑛−1=𝜏}P{A(𝑡n+𝑠)−A(𝑡n),𝜏𝑛−1==

=P{A(𝑡n+𝑠)−A(𝑡n)}P{𝜏𝑛−1=

=

=P{A(𝑡n+𝑠)−A(𝑡n)=0}3.11

𝑒−𝜆s=𝑒−𝜆s=P{𝜏𝑛>

+δ)−

)=0}=(𝜆δ)0𝑒−𝜆δ=若3.12成立，即P{𝐴(𝑡+δ)−𝐴(𝑡)=0}=1−𝜆∗𝛿+则有：lime−𝜆∗𝛿+𝜆∗𝛿−1−ο(δ)=由（𝑒𝑥=1+𝑥+𝑥2+𝑥3+⋯,−∞<𝑥<∞）知 2lime−𝜆𝛿+𝜆𝛿−1=1+−𝜆𝛿+

+⋯+𝜆𝛿−1−

=

−ο(δ))=综上3.12得证。

+δ)−

)=1}=(𝜆δ)1𝑒−𝜆δ=若3.13成立，即P{𝐴(𝑡+δ)−𝐴(𝑡)=1}=𝜆∗𝛿+则有：lim𝜆𝛿e−𝜆𝛿−𝜆𝛿−ο(δ)=由（𝑒𝑥=1+𝑥+𝑥2+𝑥3+⋯,−∞<𝑥<∞）知 2lim𝜆𝛿e−𝜆𝛿−𝜆𝛿−ο(δ)=lim𝜆𝛿（1+−𝜆𝛿+（−

+⋯）−𝜆𝛿−

2

=lim−3.13得证。P{𝐴(𝑡+δ)−𝐴(𝑡)≥

−ο(δ)==1−P{𝐴(𝑡𝑛+δ)−𝐴(𝑡𝑛)=0}−P{𝐴(𝑡𝑛+δ)−𝐴(𝑡𝑛)==1−(1−𝜆∗𝛿+ο(δ))−(𝜆∗𝛿+ο(δ))=3.14得证。泊松分布。当两个数据流合并后的到达服从参数为λ𝜏1+𝜆𝜏2的泊松分布。的概率符合泊松。现在设𝑁1𝑁2分别是在两个不相交的时间间隔𝜏1，𝜏2到达的数据个数，𝑛=𝑁1𝑁2 P{𝑁1+𝑁2=𝑛}=∑P{𝑁1=𝑘,𝑁2=𝑛−𝑘}=∑P{𝑁1=𝑘}∗P{𝑁2=𝑛− =

∙

(𝑛−=e−λ(𝜏1+𝜏2)∙

𝑘!(𝑛−

𝑖∗

=e−λ(𝜏1+𝜏2)∙∑ 𝑛!(𝑛−=e−λ(𝜏1+𝜏2)∙ =e−λ𝜏1+λ𝜏2∙

+

由上式可以看出它符合泊松(P(n)=(𝜆𝑡)𝑛e−𝜆t)，且参数为λ𝜏+𝜆𝜏 K个相互独立的泊松过程𝐴1…𝐴𝑘，若A=𝐴1+𝐴2𝐴k，那么A的参数是𝐴1至𝐴𝑘对应的参数𝜆1至𝜆𝑘的和。同时证明联合过程中第一解：因为𝐴1…𝐴𝑘b的结论可以先将𝐴1，𝐴2A’再与𝐴3合P{A(𝑡+𝜏)−A(𝑡)=𝑛}=𝑒−(𝜆1+⋯+𝜆𝑘)𝜏

[(𝜆1+由上式可以看出A符合泊松分布(P(n)=(𝜆𝑡)𝑛e−𝜆t)且参数λ=

𝜆

对于总系统

P{在时间t内只有1个数据到达(𝜆t)1𝑒−𝜆𝑡=𝜆𝑡𝑃2=P{在时间t内𝐴110个数据=P{𝐴1=1}∗P{𝐴2=0}∗…∗P{𝐴k=

𝑒−𝜆1𝑡

𝑒−𝜆2𝑡∙…

P{在时间t内

=𝜆1𝑡∙𝑒−(𝜆1+⋯+𝜆𝑘)𝑡=𝜆1𝑡∙到达一个数据|时间t内系统只到达一个数据}=𝑃2=

1

假设泊松过程在[𝑡1𝑡2]数据到达时间在[𝑡1𝑡2]内均匀分布。设t∈[𝑡1𝑡2]为数据到达时间，n为时间tP{𝑡<𝑠,𝑛=P{𝑡<𝑠|𝑛=1}

P{𝑛=P{在时间段[𝑡1s)内n=1，在时间段(s𝑡2]内n= P{𝑛=𝜆(𝑠−𝑡1)𝑒−𝜆(𝑠−𝑡1)∙

𝑠−

−𝑡)∙ =

− ,𝑥<它是一个均匀分布的分布函数(f(x)={𝑥−𝑎，𝑎<𝑥<𝑏) ,𝑥>3.15M/M/1k才开始提供服务（k在状态集{12𝑖′}(𝑖′=12(𝑘−1)′)ik时，就是标准的M/M/1系统，所以有pi1i<kpipipi'… )0 )0ik1ik(12 k1) kp

(12p(k

(1k) 1

12

)由Little定理知系统的闲时概率为

=

k(k+2p

i(12 i1)pi1ik(12 k1

pk(k1)p

(1i

1ik(1ki

1

ik

1 (1i

k

(1

i1

1

=i11i11

-(1)i1xx

ii122334kkkkx32kkkk(1)x23

k1kk2(1kx

kk1所

(1i1

(1)

-(1-

2(1k

kk]1 1ik(1k

1ik(1k1

ik1 ik

11

=limik1= lim[(k1)=(1)

1(k

=limik1

1

-limik

13 n1nkxlim[(k1)2(k2)3 3 n1nkxlim[(k1)3(k2)4 (n1)1nkn2nk

3(1nk1(1)xlim(k2

3

lim(k

1(1)x(k

1

k

k2同样的方法求limik 2

[(k

1

1N

k(k1)p

(1i

1ik(1ki

1

ik

1代入得Nk1 14.1(a)证明图4.3 pnpi

mm pn当n<m时，利用(a)中 ，用p1,p2,,pn来表示pn1p0p1,p2m=2p0图4.3时隙ALOHA链（a）n，从其他状态转入的概率应该等于从该状态转出的概率。n0,1，……，n+1n-1，n，……，m。

mmpnPnj

mmm

Pnjmmpi

0n

pnpiPinpnPnnpn(1pnn)piPinpn1 n0p1

p1(1 n=1p2因为p0p1p2

p PP(1P)P(1

)(1P10

4.44.2.1中提到的没有缓存的理想化时隙多址接入模型。nkk个时隙开始时，等待重传的节点数目，并令n为所有nk的期望值。需要注意的是n的值取决于解决碰撞的特定方式。但是这里，我们认为n的值是给定的。qa是每个节点到达率。PsuccNsys（系统中的数量是储求一个接收包的延时（Little假设现在改进解决碰撞的策略，并且设想的等待重传节点的期望值被减小到n<nNaPsuccNsysT减小。值得注意的是这意味着通过改变某一个参数（a）∵

m(mnkNa(mPsuccNa(mNsysnNan(1qa)T Na

(m（a（c (4.5)中的已经明确给出。对于给定的qa1/m,n1，证明使Psucc最大qr11

qa(mn)1

qrn01qr设满足上述等式的值qrqa的一个函数，记为qr(qa。证明qr(qa)qa（qa1mPsuccqa的全导数，用qr(qa表示qr，并证明这个导数是负数（满足qr(qaPsuccqr0，比较Psuccqa和Psuccqr证明如果qr使得Psucc最大并且qr1，那么比起马上传输新到达的包，马上 到达的包的Psucc更大（提示：后一种情况，待重传的节点以概率qaqrqa进行传输） q(1

Qr(0,n)(1qrQa(0,n)(1qa

n*qr*(1qr

(m

)mnn(1

0，并且两边同时除以n(1qa)mn(1qr)n1

(m1

1qr(n1)01qr1

1

qa(mn)1

qrn01qr

qa(mn)1

qrn01qr1qaqa(mn)(1qr)qrn(1qa)因为qrqa的函数，将qrrqqa(mn1)11qa(mnrmqa nn=0Psucc与qr无关，也就不用讨论在此条件下qrn>=1qa1mqa1m1mqa0rqqqa(mn1)qa(n1)(1mqarn aqa(n1)qa(1mqa)ad

dqPsucc(qa,qr(qa))qPsucc(qa,qr)qPsucc(qa,qr)dqqr(qa) 由（a）的结果可知，用qaqrPsucc(qaqr(qaqr

,

))

,qr(mn)(mn1)qa(1qa)mn2(1qrn(mn)(1qa)mn1qr(1qrK(qaqr(qa))(mn)(1qa)mn1(1qr(qa

,

(mn

)nqr(qa))

1

1

(qaK(q,q

(mn)qa

nqr(qa)

1 1q(q) a显然，m=nK(qaqr(qa对于1nmK(qaqr(qa

1

qa(mn)1qa

1

0由（b）,当n1时qr(qa)qa，即1/(1qr(qa))1/(1qa因此方括号内的值为负，也就可以得出dPsuccdqa为负。A：每个节点的到达率为qaqrB：每个节点的到达率为qaqr，重传的概率为qr，新到达的马上进行转发。C：每个节点的到达率为qa，重传概率为qrACPsuccA、B这足够说明在任何速率的情况下，A、BPsucc。对于系统B，~q(q~)使 最大。因此~也使得系统A的 最大 a

Cqrqr(qaPsucc由

Psucc为减函数，而qa

qaBCPsuccArCPsuccr5.2Bellman-FordDijkstra5.741的最短路解析：B-F算法的思想是利用𝐷ℎ+1=min[𝑑𝑖𝑗+𝐷ℎ]，对所有的i≠1进行迭代。先 D节点的最近节点，将该节点放入集合P中，依此类推，知道集合P包含了所有的节点。他们的主要区别是：B-FD算法按照路解：B-F2132D12132

D2222

55534D134

33D23

D2

666