作者：逯昭义,孙丽珺
出版社：电子工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
通信业务量理论与应用(下册)试读：
前言
应用数学的一个重要分支——排队论，早就在各行各业，包括交通、运输、民航、建筑、医疗、信息、通信等各种服务部门被广泛应用。然而在目前的诸多应用中，促进排队论得到重要发展的只有通信领域。排队论与通信已经紧密结合，形成了一门重要的学科发展方向——通信业务量理论（Tele-traffic Theory，也称为通信信息量理论）。出现这种情况的原因有二：① 排队论的第一篇论著，即A. K. Erlang（爱尔兰）的著作“Solution of some problems in the theory of probability of significance in automatic telephone exchanges”，是通过分析电话交换机的运行情况而得到的。电话交换是一种技术实践，在实践的基础上产生理论是符合科学规律的。因此，可以说排队论起源于通信。② 排队论创立后，它在通信领域的应用，有力地促进了通信技术，包括电话交换、计算机网络通信等的发展。这种在理论指导下的再实践也是符合科学发展规律的。总之，实践—理论—再实践—再理论是科学技术发展的必然规律，电信科学也不例外，因此在电信科学中产生业务量理论就不难理解了。从目前看，通信业务量理论的发展经历了这样几个发展时期：① 通信业务量理论的出现。在20世纪初人们把概率论引入电话网而创立早期的通信业务量理论以后，伴随着通信技术的进步，该理论得到了一定发展。然而只是自 20 世纪 50 年代以来，当运筹学（OR）和排队论得到发展后，通信业务量理论才形成一门较完整的理论而登上电信科学的学术舞台。② 通信业务量理论的发展及计算机通信网信息量理论的形成。自20世纪70 年代以来，计算机通信网络得到了很大发展，与此同时，人们把通信业务量理论扩展到计算机通信网络，用它评价网络性能，设计建造性价比更优异的计算机网络。经过 30多年的研究进展，人们发展了通信业务量理论。20 世纪末，当典型排队论（以肯达尔模型为代表）发展到非典型排队论（以扩展肯达尔模型为代表）时，出现了计算机通信网信息量理论。与早期的通信业务量理论相比，它已成为电信科学发展的新起点。由于复杂的网络分层协议代替了简单的电话通信规程，也由于复杂的计算机网络代替了比较简单的电话网系统，所以在计算机通信网信息量理论中，数据单元替代了呼叫，非即时通信或准即时通信代替了即时通信，各种非典型排队模型代替了典型排队模型，数学模型及解析方法也发生了很大改变，等等。③ 后现代通信业务量理论正在建立。自1995年以来，正当计算机通信网信息量理论飞快发展之际，研究人员在 ATM（异步交换方式）交换网上发现了信息的猝发现象。这一重要现象表明，对高速综合业务网，采用自相似模型远比马尔可夫模型更符合实际，因此进一步研究自相似业务量问题对宽带综合业务网络更具有重要意义。在通信技术飞速发展，将要在全球实现后现代通信的 21 世纪前叶，通信理论中的通信业务量理论进入了第三个发展阶段。显然将自相似理论及近似自相似理论引入后现代通信而使后现代通信得以发展的业务量理论，是当前及今后一个时期的重要研究任务。发展通信业务量理论的研究，是当前国内外同行学者的研究热点。其中为数有限的中国学者也处于这一研究的前沿领域。但从研究进展看，关键难点是长相关理论。在这方面，目前并未取得突破性进展，要取得突破恐怕还有一个过程。目前很多国外学者进行了诸多近似研究，而国内学者的研究大多处于“开场白”状态，即小综述状态。然而这一点并不防碍那些为数有限的中国学者紧跟国际前沿而不舍弃的奋斗精神。反过来，如果我们不跟随该方向的前沿发展水平，多年后，当国外研究已取得重大进展时，将会后悔和遗憾。因为那时我们将很难占有一席之地。出于这样的考虑，也为了吸引诸多青年学者投入这一研究中来，本书作者竭尽全力完成了《通信业务量理论与应用》这部专著，以敬献读者。特别要献给为发展通信业务量理论而不惜辛劳的同行学者，希望能起到抛砖引玉的作用。本书内容较多，分上、下册出版。上册的主要内容包括：Ⅰ 基础理论篇——典型肯达尔模型；Ⅱ 扩展理论篇——非典型（扩展型）肯达尔模型。下册的主要内容包括：Ⅲ 应用篇——计算机网络数学建模；Ⅳ 前沿研究篇——现代、后现代通信的部分业务量问题。本书的优势在于其手稿曾作为最近10届研究生“计算机通信网信息量理论”课的讲稿，边讲授边锤炼，先后五次易稿，不断增加新内容；本书作者在最近的25年间，坚持计算机通信网络理论的研究，在国内外一流学术刊物上发表过上百篇学术论文，其中数十篇被SCI、EI收录，应该说对通信业务量的发展前沿跟随较紧。为了使内容新颖，这些研究成果与其他重要参考文献一起都反映到了本书中。本书（下册）第12章由孙丽珺、逯昭义两人执笔，第14章及下册附录A、B由孙丽珺执笔，其余章节由逯昭义执笔。本书（下册）各章节脱稿后，冯慧芳（博士）、逯迈（博士）与作者一起完成了统稿和甄别任务。在写作手法上，本书与纯数学著作略有不同，许多章节通过“浅入深出”的阐述，强化了物理概念和物理意义的讨论，从而使读者既能把握应用数学的严密性，又能把握明确的物理概念。在本书写作过程中，作者曾访问过诸多同行学者。其中，有北京邮电大学通信研究所国家重点实验室陈俊亮教授（中国科学院院士），电子科技大学电子通信研究所光纤国家重点实验室李乐民教授（中国工程院院士），青岛大学复杂性科学研究所张嗣瀛教授（中国科学院院士），天津大学计算机科学与技术系舒炎泰教授（博导），北京航空航天大学理学院王天民教授（博导），云南大学信息学院赵东风教授（博导），暨南大学电子信息学院王思明教授，以及陈永义教授、杨庆德教授、樊建席教授、王立宏教授等，或征询他们的意见，或请求佐证问题。研究生罗秀秀、宁玉新、吕磊（博士）、崔杰、杨兴梅、姜辉（博士）、刘海光、逯进（博士）等参与了本书书稿（下册）的计算机文字处理以及在统稿过程中对电子版的修改工作，郭菊英协助作者参与了校对、清样等辅助工作。在本书出版之际，谨向他们致谢。本书是国家自然科学基金项目（No.60902634）的重要研究内容。在国家自然科学基金的支持下，作者加大了写作力度，现在终于能够使本书与广大读者见面了。在此，谨向国家自然科学基金委员会致敬。个人的水平毕竟有限，书中难免还存在错误和不足之处，敬请广大读者批评指正。作者2011年3月于青岛全书通用符号本书出现的参数符号很多，大致分为全书通用符号和各章节专用符号。对通用符号除在此处集中解释外，在书中第一次出现的地方再给予解释，后续出现则不再解释。对专用符号分别在各章节予以集中解释，以加深读者印象。F(x)：概率变量X不超过x值的概率，即，F(x)称为分布函数，其中P表示概率。f(x)：概率变量X为连续型变量，则f(x) = dF(x)/dx为概率密度函数。f (x )：X 为离散型概率变量，X 取值为 x ，j = 0,1,2,…，则 ( ) ( ) f x = P X = jjjjx 为概率质量函数。E[X]：概率变量X的平均值。V[X]：概率变量X的方差。M：k阶阶乘矩符号。kB：k阶二项矩符号。kC[X,Y]：X，Y的协方差。R[X,Y]：X，Y的相关系数。LS：拉普拉斯−斯蒂吉尔斯变换。G(Z )：概率母函数，与Z变换相同。：顾客到达率，为到达间隔。：顾客服务率。设数据单元长度为，数据速率为c，则为数据单元所占时宽，自然，为单位时间传输的数据单元数。在计算机通信信息量理论中，通常把数据单元当做顾客，因此为服务率。将服务率设为而不是像通常排队论中设为，其原因正在于此。u：服务员服务强度，也称忙闲度，。当服务员数n=1时， 称为业务量，这时通常以代替u，即，是单服务员的服务强度。 P ：系统状态由 i 转移为 j 的转移概率， ( | ) P P X j X i = = = ，r = 0,1,2,ij1ijrr+…，r 表示时点，当然r也可用字母n等取代。 P：系统处于i状态的状态概率。 P是绝对概率，不是转移概率，iiP：系统状态由i转移为j的转移概率矩阵，P=[P ]。ij[m]P ：系统状态由i经m步转移为j的转移概率。ijm[]mP ：系统状态由i经m步转移为j的转移概率矩阵， P =[P ]。mijP(n)：第 n 时刻系统处于 i 状态的绝对概率， () ( ) Pn =PX =i。如果以转移步iin为计时单位，则P (n)也是系统在第n步处于状态i的概率。i：系统在第n时刻处于各种状态的概率分布列，用列矩阵表示为P (0)：初始时刻0系统处于i状态的绝对概率，即初始概率。 (0) ( )P =P X i0i=i。：系统在初始时刻处于各种状态的概率分布列，用列矩阵表示为：所有服务员都处于忙碌状态，顾客需要等待的概率。L：系统长度，即系统中有顾客的平均数。L：排队长度，队列中有排队顾客的平均数。qW：顾客滞留时间，即平均等待时间与平均服务时间之和。W ：平均等待时间。。qM：泊松流或负指数服务。D：定常分布。G：一般分布。E：k阶爱尔兰分布。kH：超几何分布。L：二项式分布，准随机分布。FCFS：先来先服务。LCFS：后来先服务。RSS：随机选择服务。L-RSS：局部随机选择服务。PR：优先权服务。Ba：集体（批量）服务或到达。Sc：离散型到达。Fe：有反馈到达。Mu：多路到达。Pa：并联排队系统。In：间歇服务。Sh：移动服务。Di：杂乱排队系统。HD：中途有脱离的排队系统。CL：改换队列的排队系统。AL：服务员轮换服务系统。MC：多级循环排队系统。MN：多级网络排队系统。MS：多级串型排队系统。T RT：实测令牌循环时间。T T RT：目标令牌循环时间。：时隙。H (t )：服务时间分布。Q(t)：循环时间分布。R(t)：回归时间分布，也称间歇时间分布。Ⅲ 应用篇——计算机网络数学建模第8章 计算机局域网（LAN）的性能解析评价8.1 总线型 LAN 的存取方式——CSMA/CD 的系统模型及解析8.1.1 竞争-冲突随机服务方式综述1．竞争-冲突随机服务方式分类在社会的服务生活中，顾客（泛指广义的顾客）发生冲突是一种司空见惯的现象，比如人们抢购某种紧俏的商品；众人同时拥到狭窄的车门；许多车辆堵塞在桥上或道路的咽喉地带；开会时与会者争先恐后地要求发言；同时找领导反映情况者因顺序而冲突；几个班级的学生因抢占球场而冲突，等等。由于多个顾客竞争而产生的冲突，往往造成两种后果：使服务员在一段时间内无法进行服务；顾客等待服务时间必然要发生变化。为此，人们在长期的社会生活中找到了妥善解决顾客冲突的各种办法，如争执的顾客在排队后得到有序的服务；只允许一个顾客（或一个顾客集团）得到服务；系统暂时中断服务等。社会生活中自然而然出现的这种服务冲突现象以及竞争-冲突服务方式在科学技术的发展中是否有借鉴应用价值呢？长期以来人们很少问津。近年来随着计算机通信网络技术的发展，在局部网络中，有人模仿社会服务解决冲突现象的方法，[1]提出了性能优异的存取方式 CSMA/CD （Carrier Sense Multiple Access with Collision Detection，带冲突检测的载波侦听多路访问），之后，人们感到有必要深入探讨这个问题了。社会生活中虽然存在着各种各样的竞争冲突现象，但都可以归纳为如图 8-1 所示的基本过程。按消除冲突的不同办法及其后系统的服务状态，对竞争-冲突型随机服务分类，最能反映竞争-冲突服务的实际特征。竞争-冲突型随机服务可以区分为两个大类，依据消除冲突的措施，每个大类又可以区分为若干个小类，如图8-2所示。第一大类与第二大类的主要区别是冲突消除后只有一个顾客（或一部分顾客）得到服务还是冲突各方都能得到有序的服务，从而决定了下次冲突参与者不同。虽然冲突型随机服务系统可分为多类，但在服务员如何进行服务（即服务规约）的问题上有其共同特征。它与典型排队模型不同，顾客的服务并非是一个接一个（或一批接一批）地进行，而是在两次服务之间因冲突等原因存在一个时间间隔，即服务员“受理请求与处理冲突”的时间。同样，这种服务与多队列服务员循环移动服务也有区别。多队列循环移动服务虽然服务员有“步行时间”（对某特定队列是间歇服务），但就每一个队列而言是先来先服务。而竞争-冲突型服务中因存在冲突，能进入服务的顾客具有随机性。图8-1 顾客在竞争-冲突型随机服务的流程图图8-2 竞争-冲突型随机服务分类第Ⅰ大类竞争-冲突型随机服务有两种重要情况：顾客的竞争是随机发生的，只有经过退让和重新请求服务，并且不发生冲突时，某个顾客才能获得服务权。顾客的冲突是随机发生的，只有经过仲裁或者随机淘汰，才能让竞争各方中的一个（或几个）获得服务权。2．竞争-冲突型服务的系统模型经过简单分析可得上述多种竞争-冲突型随机服务的系统模型，如图8-3所示。由图可见，竞争-冲突型系统模型与典型排队的系统模型相比，由原来的四步式，即顾客到达→排队室排队→顾客接受服务→顾客离去，分为五步式，多出了“顾客竞争服务权”。和典型排队服务一样，这种系统也可以考虑服务失败顾客返回的所谓反馈问题。图8-3的（a）和（b）系统虽然都是竞争-冲突型随机服务系统，但二者有一个关键性的区别。在图8-3（a）中，当两个或多个顾客竞争服务权时，因必然产生冲突而全部返回排队室准备重新参加竞争，而在图8-3（b）中，当竞争时，不论参加者如何之多，必然是一个顾客（或一群顾客）获得服务权而接受服务，其余顾客返回排队室准备重新参加竞争。我们将图8-3（a）的形式称为“冲突后退式”，将图8-3（b）的形式称为“冲突仲裁式”或“冲突淘汰式”。本节对前者进行解析，关于竞争-冲突淘汰式系统将在本章多星LAN一节讲述。图8-3 竞争-冲突型服务系统模型8.1.2 CSMA/CD存取方式的数学建模1．竞争-冲突后退式服务系统模型的引入总线型 LAN介质存取控制方式——CSMA/CD的物理运行机理可用如图 8-4所[2]示的流程表示。由图8-4可见，CSMA/CD的系统模型正是图8-3（a）。这种系统模型与肯达尔的典型系统模型（见上册图2-1）相比，多出了“顾客竞争服务权”。在图8-3（a）中，顾客对应报文分组，排队室对应缓冲器，服务员对应 LAN 的总线。如果在该图中忽略服务失败的情况，且从服务员的角度考虑其服务流程，则如图8-5所示。图8-3（a）和图8-5反映出CSMA/CD是竞争-冲突后退方式的服务本质，因此本节以这两个图为依据来讨论竞争-冲突后退式服务系统的数学建模。图8-4 CSMA/CD流程图8-5 冲突后退式随机服务流程2．解析条件的设定[3]由图8-5可知，系统分为4个时期，3种状态，2类周期，即4个时期和2类周期的关系如图8-6所示。由图8-6不难看出：服务期和冲突期之后必定是空闲期，而最短的空闲期等于请求期（这时休息期或退让期为0），服务期只为1个顾客服务，不会出现连续服务；在请求期如果只有1个顾客请求服务，则服务成功，出现服务周期；如果有2个以上顾客请求服务，则发生冲突，出现冲突周期。图8-6 服务周期与冲突周期的组成设终端数为N，每个终端每次只能产生1个分组（即顾客），即每个终端的发送缓冲器只有1个缓冲区间，只能存放单个分组。已产生的分组在未服务结束前，不产生新的分组。将时间轴划分成以为单位的时隙。常见的的时宽为终端之间标准线路试读结束[说明：试读内容隐藏了图片]