通信网理论基础复习

通信网基础复习课第2章通信信源模型和M/M/1排队系统一泊松过程1泊松过程的四个条件平稳性、无后效性、普通性、有限性2长度为t的时间内到达k个呼叫的概率etkkkttp!)()(ttNEtNVar)()(（应用：期中考试题2，以及等待时间分布）3泊松流的性质独立泊松流的合并与分解二负指数分布10,1}{tetXPt，1EX（平均服务时间间隔与离去率的倒数关系）2无记忆特性残余分布与原始分布一致，仍为负指数分布（黑红球合并，可靠性作业有关并接寿命）3性质2.4),min(21TTT，假设21,TT为相互独立的参数分别为21,的负指数分布，则T是一个以21为参数的负指数分布。——M/M/s状态转移图的k的依据。4泊松过程与负指数分布的关系三、生灭过程1四个条件)(totk)(totk跳转的概率为)(to停留在状态k的概率为)()(1totkk；2状态转移图011kk12k1k01k1-k1k3稳态分布的结论1,21110kkkk，11001,kkkkppp4微分方程和稳态方程的建立变化率＝到达率－离去率（可靠性中的()Rt）四M/M/1排队系统1稳态分布相关)1(pkk，（直接应用生灭过程的结论）队长的均值0[]p1kkENk平均系统时间11[]EnEs（Little公式）（分组交换中的应用）2闲期与忙期3系统时间服从参数为的负指数分布00p}{}{}{kkkkkktsptsptsP，1k阶爱尔兰（Erlang）分布注：概念kp，k为队长，系统中的顾客数（含被服务的）[]ENws第3章爱尔兰拒绝和等待系统一概念1一段时间T内通过的话务量即为该时段内被占用的平均中继数2时间阻塞率vs呼叫阻塞率二爱尔兰即时拒绝系统)(//ssMM1状态转移图23s2稳态分布.,,2,1,0!!/0skrakapsrrkk3Erlang公式.,!!/),(0arasaasBsrrs（s条中继线全忙，呼叫被拒绝）迭代公式),1(),1(),(asaBsasaBasB4到达的呼叫量为a，M/M/∞排队系统的平均队长通过的呼叫量为)],(1[asBaa5严格按顺序使用的中继线群（例3.4及期中考试题）6主备用线即时拒绝系统思路①选择状态变量②画状态转移图，注意约束条件③列稳态方程④解方程⑤求中继线的利用率或通过的呼叫量⑥系统呼损三Erlang等待制系统M/M/s1状态转移图2稳态分布skpssaskpkapskkkk00!0!，100/11!!1sksksasakap3呼叫需要等待的概率sapsaasCs/1!),(04通过的呼叫量为as系统中的平均呼叫数为[](,)1ENCsaa平均等待时间)1(),(/)],(1[sasCasCEw5分组交换系统的时间分析bcsE/11)(四一般混合制的)(//nsMM系统1稳态分布nkspssaskpkapskkkk00!0!])(1[!!11100snsskksaasssakap2呼叫需要等待的概率01])(1[!),(}0{psaasssapasCwpsnnskskn3等待时间的分布1k{}{}nkkspwtppwt{}kpwt，积分换序，n为等待系统的等待时间的分布，1s为M/M/1系统的等待时间的分布注：三种机制的kp的对比等待时间的分布是难点，注意等价条件的变化特殊的不适用生灭过程的情况的处理基本概念的应用，如到达和通过的呼叫量等队长分布均值和方差little公式的应用，物理意义等待时间均值或分布非生灭过程的处理，优先级排队系统第四章通信网络性能分析一重复呼叫流),(RRRasBaaa二溢出呼叫流1统计特征Wilkinson公式)11(),(asavasaB2溢出呼叫流呼损的近似计算方法Rapp方法vz，)1(3zzva＋，11)(zzas，zzsa)1)(1]([，拒绝的呼叫量为,aBsca3Rapp的应用，迂回路由，备用线系统（注意泊松过程的a）三电话网络平均呼损1串并接)1(11iniABpp，inipp1AB2例4.7，存在迂回路由情况下，求网络平均呼损的方法123边),(ji上的呼叫量ijA的组成（直达呼叫量加溢出呼叫量）边的阻塞率，ijb满足,()ijijijBsAb，迭代求解根据串并接特性求端i和端j间的呼损ijp计算网络平均呼损四数据网络平均时延1二次排队问题1211Tccbb2Kleinrock假设包长重新取负指数分布3输出定理第五章网络拓扑结构分析一基本概念1连通图，树，割集（基本割集和基本圈）2矩阵表示关联阵－支撑树的数目；邻接阵（F算法中的W阵）二最短路径问题1最小支撑树反圈法（生长法）、避圈法、破圈法2指定端与其余端之间的最短路径Dijkstra算法Labelsetting()(,)()kilX反圈，000()(,)()()minkiiliililXww前提条件，各边的权为负3F算法，任意两端之间的最短路径labelcorrecting初始化(0)0ijijijijweEweEij　若　若　　若，　其它　　若,0w)0()0(ijijjr（i回溯）更新：)ww,w(minw1)-(kjk,)1k(k,i)1k(j,i(k)ji,)1(,)(,)1(,)1(,)(,)1(,)(,kjikjikjikjikjikkikjiwwrwwrr　若　若（(1),kkjr，回溯）注：如何利用R矩阵寻找最短路由通过画图来验证F算法的延伸应用（限制转接端，端有权，转接次数最少）4网络的中心和中点)(max)(*,njijw=)](max[min)(,njijiw(),min[]nijijw三流量问题1可行流满足的条件（1)非负有界性：对任意边jie,有，jijicf,,0；（2)连续性:对任意端iv有，其他v为宿端v为源端0tsEj)(i,E(j,i)iijiijvvFFffFfv)(为源宿间流}{,jif的总流量。2最大流问题割量),(cXXC表示割集中所有边容量的和:cjiXvXvijcXXC,c),(流量v(f)f(,)(,)ccFXXfXX,其中Xvs，ctXv，),(cXXCF可增流路：若在某条路中，前向边均不饱和（jijicf,,），反向边均有非0流量（0,jif），称这条路为可增流路。(最大流-最小割定理)可行流}f{f*j,i*为最大流当且仅当G中不存在从sv到tv的可增流路。为了求从sv到tv的最大流，可以在任意一个可行流的基础上，找sv到tv的可增流路，然后在此路上增流；继续寻找新流的可增流路，直至无可增流路时，停止。3最小费用流在确定流的源和宿的情况下,求一个可行流f,使C为最小。生成流f的补图：对于所有边,ije，如果,,ijijcf，构造边1,ije，容量为,,ijijf，单位流费用为,ijd；对于所有边,ije，如果,0ijf，构造边2,jie，容量为,ijf，单位流费用为,ijd。随意寻找一个流量符合要求的可行流，在它的补图中寻找负价环，如果找到负价环，沿环可以改变可行流的安排，进而降低费用；找不到负价环，这个流已经是最小费用流。第七章网络可靠性分析一可靠性理论基础1寿命分布}.{)(tXPtF()'()ftFt可靠度函数)(1}{)(tFtXPtR'()()Rtft平均寿命0)()(dttRXE失效率函数()'()()1()()ftRtrtFtRt如果寿命分布为负指数分布，则各函数分别为2不可修复系统vs可修复系统可修复系统：MTBFRMTBFMTTR正常时间总时间3独立串并系统的可靠度与寿命状态转移图的分析方法，以单个可修复系统为例，0为正常工作状态，1为故障状态，失效率为，修复率为。可依据状态转移图求稳态分布和可靠度。4非独立系统的可靠度例7.25桥接等复杂系统的分析（分解）注难点在于寿命分布，可靠度函数以及失效率函数之间的关系的理解负指数分布的性质及状态转移图的应用（课后题）二连通度与线连通度（确定性指标）1、、（相互之间的等式关系）以及A，B和C分类计数的技巧三网络可靠度的计算可靠集{未失效的端之间连通}，可靠度为网络处于可靠集的概率准确计算niiniiqqCnR)1(1)(只有端故障的近似可靠度qCnR1)(只有边故障的近似可靠度pBeR1)(边和端故障下的近似可靠度tsqpenR1)(，，其中tsts，，00，求和的项遍历所有A个混合割集。两端之间的可靠度－A的子集四网络的综合可靠度可靠集{网络平均呼损小于}，可靠度为网络处于可靠集的概率例7.7的应用第八章局域网性能分析用表示平均到达率，单位为：包/秒，L表示平均包长，单位为比特，C为信道速率，单位为比特/秒，则平均传输时间为/X=LC，归一化吞吐量为LSXC。随机服务系统M/D/1，等待时间w的均值为[]2(1)Ew=，其中=为到达的总量。FDMA：平均传送时延为2(1)MXT=MX，其中=MX网络吞吐量为SMXTDMA：SMX=22(1)2(1)XSMXMXTMXXSSCDMA：2(1)SMXT=MXS纯ALOHA系统，包的传播时间P，所有包包括重传包的到达符合参数为的泊松过程，则t秒内到达k个包的概率为()(),0!ktktPtekk，用G表示P秒内平均到的包数，则G=P。包正确传送的概率为{}PPPee正确传送，系统的吞吐量为2GS=Ge。在G0.5=时，S达到最大值，为max12S0.184e。每次成功发送需要的发送次数为2GGeS，则每次成功发送的不成功尝试的次数为rN，即211GrGNeS。设碰撞发生时会随机退避，退避策略是在0,1,2...1K，，之间均匀随机选择一个，则平均退避时延为1=()(1)2K-1k=0PBkPKK。则平均传输时延为2=(1)G(K+1)TeP+P2。、时隙ALOHA系统：各站在时隙开始时传送包正确传送的概率为{}PPe正确传送，系统的吞吐量为GS=Ge。在1G=时，S达到最大值，为max1368S0.e。