（管理科学与工程专业论文）tcpip网络仿真系统的研究与设计.pdf

摘要 t c p i p 计算机网络技术作为互联网络的基础架构技术，具有十分 重要的地位。因此，为t c p f l i p 计算机网络技术的教学和 - m - 培训而 设计的交互式实验环境和仿真工具就具有非常重要的意义和作用。本 论文在对当前计算机网络的建模和仿真技术进行了深入调研的基础 上，设计开发了一个适合高等教育网络教学实验的计算机网络仿真系 统，并使用该系统对t c p f l i p 协议内容进行了仿真。主要完成了以下工 作： 首先，对网络仿真技术的国内外的发展现状进行了深入的调研， 并对网络仿真技术的主要问题进行了讨论，深入研究了离散事件系统 仿真的基本理论和基本的建模、仿真方法，提出了t c p i p 网络仿真系 统s i m 的总体设计方案。 其次，对t c p i p 网络仿真系统的关键技术进行了深入的研究。对 目前离散事件系统常用的三种仿真策略进行了分析和比较，并根据仿 真对象t c p f l i p 网络的特点，设计了事件调度机制作为系统的仿真策 略；设计了代码生成器和检测编译器，使用户可以方便地建立仿真对 象的模型；设计了结构清晰，透明度高的三层s i m 系统，此系统与当 前高校主要学习的t c p i p 协议的五层结构相对应，每层都设计了接口 函数，使用s i m 系统进行t c p i p 协议仿真设计是十分简单方便的。 最后，使用本文提出的s i m 系统，对t c p f l i p 协议内容中的停止等 待流量控制和以太网通信进行了仿真开发，并应用于教学效果良好。 关键词：网络仿真，t c p i p 协议，s i m ，离散事件系统 中图分类号：t p 3 9 3 a b s t r a c t a st h eb a s i c c o n f i g u r a t i o nt e c h n o l o g yo fc o m p u t e rn e t w o r k s ， t c p i pt e c h n o l o g yt a k e sa ni m p o r t a n tr o l ei nt h en e t w o r k s t a r t i n g f r o mt h i sp o i n t t od e s i g na ni n t e r a c t i v ee x p e r i m e n t a le n v i r o n m e n to r a ne m u l a t i o nt o o lh a s v e r yi m p o r t a n ts i g n i f i c a n c e t h i sp a p e r s t u d i e s t h ep r e s e n tp o p u l a rn e t w o r k m o d e l i n ga n d e m u l a t i o n t e c h n o l o g y a n d d e s i g n san e t w o r ke m u l a t i o ns y s t e m ，b yw h i c ht h ee m u l a t i o no ft h e c o n t e n t so ft h en e t w o r ke m u l a t i o nh a sb e e nd o n e f i r s t ，t h ep a p e r i n v e s t i g a t e s t h e d e v e l o p m e n t o fe m u l a t i o n t e c h n o l o g yo f t h en e t w o r ka tp r e s e n t 。d i s c u s s e st h ek e yp r o b l e m so f t h ee m u l a t i o n 。s t u d i e st h ef u n d a m e n t a l t h e o r y a n dt h eb a s i c m o d e l i n ga n de m u l a t i o ns k i l l s o ft h ed i s c r e t ee v e n ts y s t e m ，p u t s f o r w a r dag e n e r a ld e s i g ns c h e m eo ft h et c p i pn e t w o r ks i m u l a t i o n s y s t e m ，w h i c h w en a m es i m s e c o n d ，i o t so f i n v e s t i g a t i o n h a sb e e nd o n eo nt h e k e y t e c h n o l o g y o ft c p i i pn e t w o r ke m u l a t i o ns y s t e m ：t h r e ep o p u l a r s i m u l a t i o ns t r a t e g i e su s e di nt h ed i s c r e t ee v e n ts y s t e ma r ea n a l y z e d a n d c o m p a r e d ，t h e ne v e n ts c h e d u l i n gm e c h a n i s m i sd e s i g n e da st h e e m u l a t i o n c a t e g o r yo ft h es y s t e m ；c o d eg e n e r a t o ra n dd e t e c t i o n c o m p i l e r a r ed e s i g n e ds o a st h a tt h eu s e rc a nb u i l dt h em o d e io ft h e e m u l a t i o n o b j e c t ；t h e t h r e el e v e ls i m ，w h i c hh a s a p p a r e n t a r c h i t e c t u r ea n dh i g ht r a n s p a r e n c y , i sc o r r e s p o n dt ot h ef i v e l a y e r s t r u c t u r eo ft h et c p l pp r o t o c o lw h i c hi sl e a r n e di nt h eh i g h s c h o o l ； b a s e do nt h et h r e ei e v e is y s t e m i n t e r f a c ef u n c t i o n sa r ed e s i g n e df o r e v e r yl e v e l ，w h i c hm a k e si ts i m p l ea n dc o n v e n i e n tt oe m u l a t et h e c o n t e n t so ft c p i p a ti a s t s i mi su s e dt oe m u l a t et h es t o pa n dw a i tt r a f f i cc o n t r o i a n dt h ee t h e r n e tc o m m u n i c a t i o n a n dt h ea c t u a l t e a c h i n g e x p e r i e n c ep r o v e st h a tt h es i mw ep u tf o r w a r dc a nb r i n gu ss o u n d e f f e c t s k e y w o r d s ： n e t w o r ke m u l a t i o n ，n e t w o r ke m u l a t i o n ， s i m ，d i s c r e t ee v e n t s y s t e m c l cn u m b e r ：t p 3 9 3 独创声明 6 8 4 3 2 5 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获缛 ( 注：如没有其他需要特别声明的，本栏可空) 或其他教育机构的学 位或证书使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名： 导师签字 签字日期：2 0 0 4 年月 日 签字日期：2 0 0 4 年月日 第一章绪言 本文设计了一个t c p i p 计算机网络仿真系统s i m ，对其中的关键技术进行了 实现，实验证明，本文提出的s i m 系统在当前的t c p i p 计算机网络技术的教学和实 验活动中具有非常重要的意义和作用。 1 1 计算机网络仿真概述 计算机网络仿真是一种很有用的网络研究方法，它以系统理论、形式化理论、随 机过程和统计学理论、优化理论为基础。从不同的方面对计算机网络进行模拟，通过 提供一个虚拟模型来预测并比较各种方案的性能，然后通过对不同环境和工作负荷的 分析和比较，来优化系统的性能。在某些情况下，仿真是一种必要的方法和技术。仿 真方法的抽象化程度比数学分析方法低，耗费的时间比测量技术少，而且可视化程度 高，莫低成本和有效性是其他传统方法不可替代的。随着网络新技术的不断出现和数 据网络的日趋复杂，对网络仿真技术的需求越来越迫切，网络仿真的应用也将越来越 广泛，网络仿真技术已成为研究、规划、设计计算机网络不可缺少的工具。从8 0 年 代开始，在美国等发达国家就一直致力于开发商业和非商业用途的网络仿真产品。近 年来，我国的网络仿真研究和应用也得以发展。i 9 9 7 年，c e r n e q 网络中心开始开发 自己的网络仿真软件；此外，我国多家单位陆续引进o p n e t 网络仿真软件，用于网络 协议开发、网络规划设计和应用的研究。 1 2 网络仿真技术的现状 在国外，网络仿真技术的研究和应用已经有1 0 多年的历史。过去网络仿真技术 主要用于网络协议和网络设备的开发和研究，使用者大都是大学和研究院、所的研究 和开发人员。网络仿真软件的操作相当复杂，使用者一般需要较长时间的培训和熟悉 才能够熟练地掌握。 近年来，由于数据网络日趋复杂、网络规模日趋庞大，网络仿真技术应用于网络 规划和设计的需求日渐强烈。于是，网络仿真软件厂商近年来纷纷把应用和开发重点 转向网络规划和设计方面，将用户由原来的研究开发人员转向网络规划和设计人员， 简化软件界面和操作流程，强化软件的工程应用能力，特别是加强了与网络管理软件 厂商的合作，开发与网管软件的接口，使得网络模型的建立逐步自动化，加快网络建 模的速度。o p n e t 与h p 网管紧密结合就是一个典型的例子。 目前进行网络仿真有两种方式：在已有仿真系统上进行二次开发或自己编写仿真 系统进行仿真。 目前，使用最广泛的网络仿真工具莫过于o p n e t ( 商业软件) 和n s 2 ( 免费软件) 。 这两款软件的差别很大，此处不做功能的逐一对比，而是从用户的角度对各自的特点 分别进行介绍： 1 ) n $ 2 n s 2 是n e t w o r ks i m u l a t o r ( 版本2 ) 的缩写，是一个用于网络研究的离散事件 仿真器，主要用于仿真各种网络协议和网络体系结构。n s 产生于1 9 8 9 年，由r e a l 网络仿真器发展而来，1 9 9 5 年，d a r p a 通过v n t ( v j r t u a li n t e r n e t w o r kt e s t b e d ) 项目给予资助，目前由i 。b l ，x e r o xp a r c ，u c b 和u s c t s i 协作研制。 n s 2 采用两种编程语言c + + 和o t c | 。c + + 是一个编译性语言，通过它可以有效的 处理字节、包头等数据信息，实现运行于大数据集的算法。因此，对于运行速度要求 很高而对程序维护( 运行、调试修改以及重新运行的多次反复) 速度不敏感的任务非 常适用，一般用于协议的仿真研究。而o t c ( 面向对象的t c l ) 是个解释性语言， 用于书写仿真脚本，适用于大多数网络结构的研究，只要修改一下网络的参数和配置， 就可以对大量的场景进行比较，o t c 运行速度慢但可以快速的改变配置。两种语言 的混合使用，满足了不同的需要，也弥补了彼此的缺陷。 n s 2 定义了一个 t r 格式的文件用于记录仿真的结果，通过脚本配置，可以指定 文件名并对仿真过程进行跟踪，通过n s 2 中x g r a p h 的解释，此记录文件可以以图形 的方式显示仿真结果。 为了使显示结果更逼真，n s 2 提供了一个用于产生动画效果的可视化工具：n a m ( n e t w o r ka n i m a t o r ) 。n a m 用于有线和无线网络的可视化，在n a m 中，执行仿真的 人可以控制动画演示的速度，如正向播放、快速前进、快速后退停止运行等，以监视 网络的行为( 如队列的变化) ，还可以将动画转换为其他的格式，如g i f ，从而扩展 2 了仿真结果的使用，如一个网络课的教师可以构造一个以太网的仿真模型，存模型中 加入感兴趣的网络属性，从丽生成一个具有动画效果的直观的以太网模型，并通过 p o w e r p o jn t 将结果展示给学生。 一个完整的仿真脚本一般包括；创建事件调度表( e v e n ts e h e d u 【e r ，即未来事 件表) 、创建网络( 包括网络节点、链路及队列) 、建立不同节点之间的连接、生成嘲 络流量( t r a f f i c ) ，进行跟踪等。n s 2 中的网络实体包括： 节点：网络中的硬件实体。 代理：节点上的软件实体( 如t c p ，u d p 等) 。 链路；用于连接网络各节点。链路有单工和双工之分。 流量生成器：它是一种代理，分为源( s o u r c e ) 和汇( s i n k ) ，分别代表着包 的生成方和接受方，主要模拟网络中的业务流。n s 2 支持的协议有：t c p ，u d p ， i p ，r i p r t c p ，s 蹦，8 0 2 3 f f 哺c ，8 0 2 n m a c ：支持静态单播，动态单播和多 播路由协议；支持d r o p t a i l ，r e d ，c b q ，w r r ，d r r ，s f q 等队列和包的调度。 可以生成指定的业务流：如c b r ( c o n s t a n t b i t r a t e ) ：支持链路失效，链路 出错：也可以和真实的网络互换数据。1 。 2 ) o p n e t o p n e t 是o p n e tt e c h n o l o g i e sl n c 公司的产品，最早由麻省理工学院信息决策 实验室受美国军方委托开发。目前，该产品在通信、国防及电脑网络领域获得了广泛 认可和采用。被n e t w o r kw o r l d 评选为“世界级网络仿真软件”。 o p n e t 通过多层子网嵌套来实现复杂的网络拓扑管理。提供了三层建模机制，分 别为进程级( p r o c e s sl e v e l ) 、节点级( n o d el e v e l ) 和网络级( n e t w o r k l e v e l ) ， 在进程级对各对象行为进行仿真，互联进程级对象形成节点级的设备，通过链路将设 备互联形成网络级的网络，将多个网络场景组织在一起形成工程。 决议和其它进程通过有限状态机( f i n i t es t a t em a c h i n e f s m ) 来建立模型，f s m 的状态和状态的转换是由c c + + 的逻辑完成的。为简化模型的书写，该产品提供了4 0 0 多个库函数。 该产品提供了集成的调试环境和分析工具。在仿真过程中和仿真完成后，均可以 用动画来展示模型的行为。仿真结果可输出到电子表格中，从而简化图形的绘制和时 问序列的分析，提供柱状图、概率函数、参数曲线、置信区问等。 可以模拟卫星网或任何具有移动节点的网络，动态的控制每一个节点的位置或预 定义移动节点的轨迹，为其增加地图或其它背景图以增强视觉效果。模拟的数据可来 自文本文件、x m l ，也可从h p 、c o a c o r d 、s n i f f e r 、n e t s c o u t 和其它公司的流彳于网管 工具中导入数据。 其标准模块可进行以下仿真： 数据链路层技术a t m 、c o a x i a l 、1 0 b a s e t 、1 0 0 b a s e t 、1 0 0 0 b a s e x 、f d d l 、l a n e 、 l a p b 、s t b 、s r p ，s n a 、t r 、v l a n ，x 2 5 。 网络层l 办议i p 、i p x 、r s v p 。 路由选择协议o s p f 、b g p 、i g r p 、r i p 、e i g r p 。 传输层协议t c p 、n c p 、u d p 。 物理层技术s o n e t 、x i ) s l 、i s d n 。 工具：失效恢复、内存使用、丢包模拟、网络设备的构建。 混合仿真对象：局域网节点、云状节点。 应用层：可定制的应用、数据库、e - m a i l 、f t p 、t i t t p 、远程登陆、打印、声 音有关的应用、视频会议。 无线a m p s 、w l a n 。 号用模块：用于满足用户对新技术和销售商的专有技术的需求，专用模块需要单 独付费使用。o p n e t 支持w i n d o w sn t ，w i n d o w s2 0 0 0 ，u n l x ，平台的迁移是透明的”。 如果现有的仿真系统平台不能满足仿真需要或应用需要，就必须要自己编写仿真 系统了。本论文描述的t c p i p 网络仿真系统s i r 即是自己编写的仿真系统。 自己编写仿真系统的优点是可以避免或克服现有仿真系统的缺点，设计出符合特 定需要的仿真系统，可定制性强。 下面对涉及到的几项关键实现技术进行简要的介绍： 面向对象技术 面向对象技术的思想是把系统看作是由一系列对象和对象之间的联系组成的，每 个对象具有一系列属性( p r o p e r t y ) ，方法( m e t h o d ) 和事件( e v e n t ) 。属性代表对 象的状态，方法代表对象的行为。它提供了一条方便的途径，便于人们建立起与现实 世界尽可能接近的模型。面向对象技术包括面向对象的分析方法( o o a ) 和面向对象 的设计方法( o o d ) 。 设计模式( d e sjg np a t t e r n ) 设计模式是对被用来在特定场景下解决一般设计问题的类和相互通信的对象的 描述。一个没计模式命名、抽象和确定了一个通用设计结构的主要方面，这些设计结 构能被用来构造可复用的面向对象设计。设计模式使人们可以更加简单方便的复用成 功的设计和体系结构。例如，对于现代的交互式软件来说，对用户操作提供撤销重 做的功能是很重要的。命令模式( c o m m a n dp a t t e r n ) 即是解决这个问题的一般方法( 模 式) 。 使用设计模式的好处一方面是充分利用前人在类似问题上的设计经验，减小设计 风险，另方面也使得系统结构更加清晰，更容易维护，是设计高质量软件系统的重 要手段。 设计模武归纳起来主要有以下三类： 创造型模式：处理实例化过程( 怎样，何时和什么对象被创建) 以及类 和对象的配置。允许一个系统处理在结构和功能上变化很大的“产品” 对象 结构型模式：处理类和对象在大的结构中的使用方法，以及分离界面和 实现。 行为型模式：处理算法以及在对象之间分配责任，还有在类和对象之间动态 交互。行为型模式处理对象间的通信，而不仅仅是结构。 1 3 论文主要工作 为了对网络仿真技术进行深入研究，并开发一种适合高等教育网络教学实验的计 算机网络仿真系统，本文开发了一个为计算机网络教学和实验服务的仿真工具和实验 环境t c p i p 网络仿真系统s i m ；并对s i r e 系统中的关键技术进行了实现；最后使 用该系统进行了t c p i p 协议内容的仿真。 1 ) t c p i p 网络仿真系统s i m 的设计 通过深入研究离散事件系统仿真的理论和建模方法，提出了t c p i p 网络仿真系统 s i m 的总体设计方案。s i m 系统由系统仿真模块、代码生成模块、编辑模块和仿真运行 模块组成。用户通过编辑模块构造出通信网络的静态拓扑结构和相应实体的属性，系 统仿真模块提供了多种仿真调度策略可生成不同的仿真模型代码，再通过代码生成模 块与网络模型代码组合成中间代码，最后由运行模块检测编译并运行。 2 ) s i m 系统中的关键技术实现 设计了事件调度机制作为系统的运行机制：设计了代码生成器和检测编译器，使 用户可以方便地建立仿真对象的模型：设计了由应用层、中间层和物理层组成的三层 s i m 系统，此系统与当前高校主要学习的t c p 【p 济议的五层结构相对应，结构清晰， 透明度高，每层都设计了接口函数，使用s i m 系统进行t c p i p 协议仿真设计是十分 简单方便的。 。 3 ) t c p i p 协议仿真 最后，使用s i m 系统对t c p i p 协议内容中的流量控制和以太网通信进行了仿真 开发，实验证明本文提出的s i m 系统有较强的通用性和灵活性，可视化程度高。 从应用角度来看，s i m 系统使用三层结构与当前高校主要学习的t c p i p 协议的 五层结构相对应，结构清晰，每层都设计了接口函数，使用s i m 系统进行仿真设计是 十分简单方便的。从开发角度来看，系统由系统仿真模块、代码生成模块、编辑模块 和仿真运行模块组成，有较强的通用性和灵活性，对系统进行二次开发也是十分方便 的。此外，s i m 系统的可视化程度高，用户可以根据自己的需要，对仿真界面进行设 计，以达到演示和评价的目的。 s i m 系统首先是根据计算机网络仿真的理论和方法( 即离散事件系统仿真的理论 和方法) ，使用面向对象技术对将要实现的仿真系统进行分析和建模：然后根据建模 结果进行系统和建模设计，在这个过程中会用到些设计模式；最后使用面向对象的 程序设计语言，如c + + 编写和实现仿真系统。 第二章t c p i p 网络仿真系统s i r e 的设计 21 s i r e 系统概述 21 l 开发背景 t c p i p 计算机网络技术是构成我们今天互联网络的基础架构技术，具有十分卞 要的作用，关于t c p i p 计算机网络技术的教学和科研也已经有很多年了，然而， t c p i p 计算机网络技术的教学和培训大多数情况下还只是停留在教科书和幻灯片的 层次上，缺乏生动、交互性强的计算机课件和实验环境，实验内容较少，涉及到t c p i p 基本原理和算法的实验内容更是少之又少。这样，造成教学和培训效果不是很理想。 现在，不少学过t c p i p 的学生对基于t c p i p 的互联网应用如w w w 、e m a i l 等非常熟 悉，提到t c p i p 的概念也是耳熟能详，但是对t c p i p 的实现机制和算法，尤其是对 于底层的协议及实现却是一知半解，大多数停留在书面层次。 西方些技术较先进的国家也有在t c p i p 计算机网络技术的教学和培训中使用 辅助软件仿真系统或多媒体教学课件的，但效果并不十分理想。通用计算机网络仿真 系统如n s 仿真系统，通常并不是专为教学和培训而设计的，同时也比较复杂和专业 ( 例如n s 需要学习和掌握t c l 脚本语言的编程才能很好的使用) ，使得学习者学习和 使用比较不便，难以成为教学和培训的得力助手。而其他一些电子类课程，如电路设 计等，因为对仿真环境需求较突出，很早就有各种成熟的实验和仿真环境了。至于多 媒体教学课件，虽然对某个或几个问题能够以鲜明、生动的方式演示，但是由于从 根本上缺乏交互性和用户可控性，用户基本只能按照设计者的思路和框架进行操作， 故功能有限，难以承担重任。 因此，为t c p i p 计算机网络技术的教学编写一个交互性和演示性强的实验和仿 真环境是非常有意义和必要的。 2 1 _ 2 开发方案选择 在本文第一章中所述，仿真系统的实现有两种方法，即在在已有仿真系统( 如 n s 2 ) 上进行二次开发和自己编写仿真系统，基于以下原因我选择了自己编写仿真系 统： ( 1 ) n s 2 系统比较复杂，需要一段时间的学习才能够使用，这就学q 三在进行实验之 前先要学习n s 2 ，显然要求是比较高的。 ( 2 ) 由于n s 2 在系统结构上将仿真和演示分离，在界面设计和演示效果方面略显不 足，所以不太适合在教学过程中使用，而比较适合做网络研究。 ( 3 ) 自己编写的为教学和实验使用的仿真系统，框架会很简单、清晰，代码容易维 护，便于教师和学生使j j 。 2 1 3s i m 系统描述 s i m 系统是一个为计算机网络教学和实验服务的仿真工具和实验环境，应具有较 强的通用性和灵活性，可视化程度高，用户可以根据自己的需要，对t c p i p 通信协 议中的以下不同方面进行仿真，以达到演示和评价的目的。 物理层：i e e e8 0 2 3 以太网和点到点的链路| 办议。 数据链路层：流量控制和差错控制等机制 网络层：a r pi pi c m pi g m p 传输层：t c pu d p 应用层：f t ph t t pt e l n e t 2 2 相关理论介绍 t c p i p 计算机网络是一个包交换网络，对于计算机仿真来讲属于离散事件系统， 因此可以使用离散事件系统仿真的理论和方法对计算机网络进行仿真。本节将对离散 事件系统的仿真理论进行简要介绍。 2 21 离散事件系统仿真的基本概念和特点 离散事件系统的特点是状态只在离散的点上发生变化，而且这些离散的时间 点是不确定的。例如，计算机网络、定票系统、交通控制系统等都是离散事件系统。 对于离散事件系统来说，系统的内部状态变化是随机的，同一个内部状态可 以向多种状态转变，因此很难用函数形式来描述系统内部状态的变化，通常所关 心的是系统内部状态变化的统计规律。另一方面，系统的内部状态只在离散的随 机时间点上发生变化，且状态在一段时间内保持不变。因此在建立离散事件系统 模型时，只需考虑系统内部状态发生变化的时间点以及产生这些状态变化的原 因，而不用描述系统内部状态发生变化的过程。下面介绍离散事件系统建模过程 中的一些基本概念。 ( 1 ) 实体( e n t i t y ) 实体是被仿真系统中可单独辨识和描述的构成要素。实体是系统的组成部 分，是系统的三个基本要素之一。在仿真建模人员看来，实际系统就是由相互间存在 定关系的实体集合组成的，实体间的相互联系和作用产生系统特定的行为。在离散 事件系统中的实体可分为两类，即临时实体和永久实体。临时实体是系统中活动的部 分，它在某时刻达到并进入系统，在系统中停留一段时间并与其它实体发生作用后离 开系统。永久实体是系统中固定的部分，它永久停留在系统中。例如在计算机网络中， 数据包不断被发送、接收和处理，属于临时实体，而主杌则属于永久实体。系统中临 时实体的到达和离开及实体之间的相互作用促使系统的内部状态发生变化。 属性和行为相同或相近的实体可以用类来描述，这样做可以简化系统的组成 和关系。例如，计算机网络可以看作是由“主机”、“路由器”、“网卡”等实体类组成 的。 ( 2 ) 属性( a t t r i b u t e ) 属性是实体特征的描述，一般是实体所拥有的全部特征的一个子集，用特征 参数或变量表示。选用哪些特征参数作为实体的属性与建模目的有关，可参照以下原 则选取： 1 、便于实体的分类 例如将理发店顾客的性别( “男”或“女”) 作为属性考虑，可将“顾客”实体分 为二类，每类顾客占用不同的服务台。 2 、便于实体行为的描述 例如将飞机的飞行速度作为属性考虑，便于对“飞机”实体的行为( 如两地间的 飞行时间) 进行描述。 3 、便于排队规则的确定 例如生产线上待处理工件的优先级水平有时考虑为“工件”实体的一个属性，以 便于“按优先级排队”规则的建立和实现。 ( 3 ) 活动( a c t i v i t y ) 活动指实体在一段时间内持续进行的操作或过程。活动所占用的时问区段称为忙 期( d u r a t i o n ) ，忙期可以是定时的或随杌的。在离散事件建模中，一般要给出忙期 的计算公式或概率分布函数，保证实体在一进入菜一活动时其忙期就可计算，或从某 一概率分布函数中抽取得到。很多情况下活动是由几个实体协同完成的。 ( 4 ) 状态( s t a t e ) 状态是对实体活动的特征状况或形态的划分，其表征量称为状态变量。在理发店 服务系统模型中，“顾客”有“等待服务”、“接受服务”等状态，“服务员”有“畦” 和“闲”等状态。活动总是与一个或几个实体的状态相对应。状态可作为动态属性进 行描述。 ( 5 ) 事件( e v e n t ) 事件就是引起系统状态发生变化的瞬间操作或行为。只有在事件的作用下，系统 状态才会发生变化。从某种意义上说，离散事件系统是由事件驱动的。事件发生的时 刻称为事件点。不关心事件所代表的操作和行为意义时，事件与事件点是同义语。若 事件的发生是有前提的，则称为条件事件。 为实现对系统中事件的管理，在仿真模型中必须建立事件表，以记录发生的事件 或将要发生的事件以及与该事件相关联的实体的有关属性。系统中固有的事件称为系 统事件，用于控制仿真进程的事件称为程序事件。 考察活动、状态和事件三者间的联系。由于事件的发生会导致状态的变化，而实 体的活动可以与定的状态相对应，因此可以用事件来标示活动的开始和结束。 ( 6 ) 进程( p r o c e s s ) 一组按发生时间排列的事件活动序列称为一个进程。 ( 7 ) 队列( q u e u e ) 队列是处于等待状态的实体序列。一般按新到的实体排在队尾的次序组成队 列。在离散事件建模中，队列可作为一种状态或特殊实体对待。 ( 8 ) 仿真时钟( t i m e r ) 1 0 仿真时钟表示仿真时间的变化。对于离散事件系统仿真来说，仿真时钟的推进步 长是随机的。 2 2 2 离散事件系统仿真的一般步骤 离散事件系统仿真的一般步骤如下：( 如图2 一l 所示) l 、系统建模 般可用流程图或网格图的方式描述，反映l 临时实体在系统内部历经的过 程、永久实体对临时实体的作用以及它们相互之间的逻辑关系。具体建模方法将 在f 节讲述。 2 、确定仿真算法 分为两个方面的内容：如何产生所需求的随机变量( 视系统所需的概率模型 而定) ：采用什么方法对离散事件系统仿真( 即仿真策略) 。 3 、建立仿真模型 根据仿真算法建立被仿真系统的计算机模型( 变量定义及程序流程) 。这一步即 是从系统仿真模型到计算机编程模型的映射。 1 2 4 殴计仿真程序 使用通用程序设计语占，如c c 什，或使用专用计算机仿真语言开发和实玑仿 真模型。如果是基- 丁- 现有仿真平台进行二次开发，则可必充分利用仿真平台提供的模 型和函数。 5 仿真结果分析 在仿真程序调试通过后，即可输入给定数据得到仿真结果。对仿真结果要进 行相应的分析和处理，以确定仿真实验中所得到的信息是否合理和充分，是否满 足系统的目标要求等。：。 2 ，2 3 离散事件系统仿真建模方法 1 、实体流图法 实体流图法与计算机程序流程图的画法类似，可以描述临时实体产生、流动、 消亡及其被永久实体加工、处理的过程和逻辑关系，应用比较广泛；所建立的实 体流图模型易于转换为面向事件的仿真模型。借助实体流程图，可以表示事件、 状态变化及实体间相互作用的逻辑关系。出于计算机程序框图的思想和编制方法 己广为人们所接受，加上实体流程图编制方法虽然简单，但对离散事件系统的描 述却比较全面等特点，使得实体流图法的应用比较普遍。 建立实际系统的实体流图模型没有什么特别的技巧和理论可言，是要x 、j 实 际系统的工作过程有深刻的理解和认识，二是要将事件、状态变化、活动和队列 等概念贯穿于建模过程中。常用的图示符号只有菱形框( 表示判断) 、矩形框( 表 示事件、状态、活动等中间过程) 、圆端矩形框( 表示开始和结束) 及箭头线( 表 示逻辑关系) 等。建模时可以按照以下思路进行： ( f 辨识组成系统的实体及属性。其中。将队列作为一种特殊的实体考虑。 ( 2 ) 分析各种实体的状态和活动，及其相互间的影响。队列实体的状态是队列 的长度。 ( 3 ) 考察有哪些事情导致了活动的开始或结束，或者可以作为活动开始或结束 的标志，以确定引起实体状态变化的事件，并合并条件事件。 ( 4 ) 分析各种事件发生时，实体状态的变化规律。 ( 5 ) 在一定的服务流程下，分析与队列实体有关的特殊操作( 女u 换队等) 。 ( 6 ) 通过以上分析，以临时实体的流动为主线，用约定的图示符号画出被仿真 系统的实体流程图。 ( 7 ) 给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法。 属性描述变量，例如顾客到达时间、服务时间等，可以取组固定值，可以由某 一计算公式取值，还可以是一个随机变量。属性描述变量是随机变量时，应给出 其分布函数。 ( 8 ) 给出队列的排队规则。有多个队列存在时，还应给出其服务规则，包括队 列的优先序、换队规则等。 需要指出的是，实体流图是为描述实体流动和相互间逻辑关系而绘制的，它 和计算机程序框图不同，与计算机编程实现的要求还有较大距离。 2 、活动周期圈法 活动周期图法针对实体的行为模式进行建模，可以直观的表示出某类实体生命周 期中的活动和状况，具有规范化的特点，对不同实体之间的协同关系的描述十分清晰、 明确，而且应用活动周期图法建立的系统模型，转换为面向活动的仿真模型比较方便。 活动周期图以直观的方式显示了实体的状态变化历程和各实体之间的交互作用 关系，便于理解和分析。活动用期图可以充分反映各类实体的行为模式，并将系统的 状态变化以“个体”状态变化的集合方式表示出来，因此可以较好的表达众多实体的 并发活动和实体之间的协同。但是，它只描述了系统的稳态，而没有表示系统的瞬态， 即活动的开始和结束事件。 活动周期图建模方法将实体的状态分为静寂( d e a d ) 和激活( a c t i v e ) 两种，并 分别用不同的符号子阻表示。状态之间用箭头线相连，不同的实体用不同的线型，表 示各种实体的状态变化历程。激活状态通常是实体的活动，模型中活动的忙期可采用 随机抽样等方法事先加以确定。相反，静寂状态通常表示无活动发生，是实体等待参 加某一活动时的状态，其持续时间在模型中无法事先确定，取决于有关活动的发生时 刻和忙期。每一类实体的生命周期都由一系列状态组成。随者时间的推移和实体问的 相互作用，各个实体从一个状态变化到另一个状态，形成一个动态变化过程。 图2 2a c d 基本图例 静寂状态 激活状态 活动间期图建模过程如下： ( 1 ) 辨识组成系统的实体及属性 辨识组成系统的永久实体和临时实体，队列不作为实体考虑。 ( 2 ) 分别画出各实体的话动周期图 实体活动周期图的绘制要以实际过程为依据。队列作为排队等待状态来处 理。在实体流程图法中当作事件看待的某些操作或行为，要拓展为活动来处理。 活动周期图服从以下两i 页原则： 1 ，交替原则 静寂状态和激活状态必须交替出现。如果实际系统中某一活动完成后其后续 活动就立即开始，则后续活动称为直联活动。为了使直联活动与其前置活动的连 接仍符合交瞀原则，规定这两个活动之间存在一个虚拟的队列。 2 闭合原则 每类实体的活动周期图都必须是闭合的，其中临时实体的活动周期图表示一卟或 几个单位实体从产生到消失的循环过程，而永久实体的活动周期图则表示个或几个 实体被占用和释放的循环往复过程。 ( 3 ) 将各实体的活动周期图联结成系统活动周期图 以各实体之间的协同活动为纽带，将各实体的活动周期图合并在起。 ( 4 ) 增添必要的虚拟实体 在活动周期图中，当一个活动的所有前置静寂状态均取非零值( 队列不空) 时， 该活动才有可能发生。利用这一特性，可以增添某些必要的虚拟实体，并假定它们与 另外的实体协同完成某项活动。用这种方法可以为实体活动的发生加上某种附加条 件，从而实现“隔时发生”的建模效果。 ( 5 ) 标明活动发生的约束条件和占用资源的数量 包括：1 活动是否可以发生的判断条件，这些条件应是用a c d 纠示符号无法或 不便表达的：2 永久实体在参加次防同活动时被占用和活动完成时释放的数量。 活动发生的条件一般为某种表达式，标在活动框的旁边。协同活动发生时占用释放 永久实体( 资源) 的数量标在相应箭头线的旁边( 带有+ 一符号) ，数量为1 时不标。 ( 6 ) 给出模型参数的取值、参变量的计算方法及属性描述变量的取值方法，并 给出排队规则和服务规则。 3 、p e t rj 网法 p e t r i 网法适于建立加工系统等多种离散事件系统的模型，并可以对网系统的特 性进行比较严密的数学分析，得到对并发、冲突、死锁等现象的深刻认识，应用也比 较广泛。 p e t r i 网定义如下： 三元组n = ( s ，t ；p ) 称为p e t r i 网的充要条件是： ( 1 ) s u t 中： ( 2 ) s n t = 巾； ( 3 ) f s x t u t s ( 4 ) d o m ( f ) uc o d ( f ) = s u t 条件( j ) 和( 2 ) 表明，p e t r i 网由s 和t 两类元素组成；其中s 叫做n 的库所 集，t 叫做变迁集。条件( 3 ) 表明，f 是由一个s 元素和一个t 元素组成的有序偶的 集合：f 称为n 的流关系。条件( 4 ) 中，d o m ( f ) 是f 所含序偶的第一个元素的集合， c o d ( f ) 则是第二个元素的集台。 条件( 4 ) 表明，n 不能有孤立元素，从而s ，t 和f 均不能为空集。p e t rj 又称 有向网，简称网。x = sut 称为n 的元素集。 元素的输入和输入集 设x x 为网n ( s ，t ：f ) 的一个元素，令x = y i ( y ，x ) f ) ，x = y ( x ，y ) f ， 则x 称为x 的输入集或前集；x 称为x 的输出集或后集。 p e t r i 网的标淮图形表示是用圆圈代表库所，用方框或竖线表示变迁，用从x 到 y 的有向弧表示序偶( x ，y ) 。如果( x ，y ) 是从x 到y 的有向弧，就称x 是y 的输入， y 是x 的输出“。 4 、e u l e r 网法 e o l e r 网法以图论和网论为数学描述语言，贳穿了面向对象的建模思想，描述方 法比较规范，可以建立连续一离散事件混合系统模型，方法的通用性较强。在此不再 赘述。 2 2 4 离散事件系统仿真模型设计 前面介绍了离散事件系统模型的建模方法。为了使模型能够在计算机卜运行，需 要将系统模型转换为仿真模型( 也称计算机模型，c o m p u t e r i z e dm o d e ) ，这是从模 型到计算机仿真的一个必不可少的步骤。 将系统模型转换为一个可以在计算机上运行的仿真模型，一般需要完成三部分工 作。 ( 1 ) 设计仿真策略，具体的说就是确定仿真模型的控制逻辑和仿真h j 钟推进机 制； ( 2 ) 构造仿真模型，即确定模型的具体操作： ( 3 ) 仿真程序设计与实现，即采用某种程序设计方法及语言，实现仿真策略和 仿真模型。 e 述过程系统的称为仿真模型的设计与实现。 i 、仿真策略 要将系统模型转换为计算机模型，首先要从总体上确定仿真模型的控制逻辑和仿 真时钟推进机制，即确定仿真策略。仿真策略是仿真模型的核心，反映了仿真模型的 本质，从根本上决定了仿真模型的结构。迄今为止，离散事件系统己形成三种基本的 仿真策略，分别是事件调度( e v e n ts c h e d u li n g ，e s ) 、活动扫描( a c t i v i t y s c a n n i n g ， a s ) 和进程交互( p r o c e s si n t e r a c t i o n ，p i ) 。其它仿真策略均是以这三种仿真策略 为基础的。 事件调度法 事件调度法的基本思想是，将事件例程作为仿真模型的基本模型单元，按照事件 发生的先后顺序不断执行相应的事件例程。每一事先可预知其发生时间的确定事件都 带有一个事件例程，用以处理事件发生后对实体状态所发生的影响，并安排后续事件： 条件事件一i 具有事件例程，对它的处理隐含在某一确定事件的例程中。因此，事件调 度法中所说的事件是指确定事件。对实体流图法建立的概念模型，般可采用事件调 度法建立其仿真模型。 事件调度法的仿真策略如下： ( 1 ) 初始化 l 。置仿真的开始时间t o 和结束时间l f ： 2 置实体的初始状态： 3 置初始事件及其发生时间t s ； ( 2 ) 仿真时钟t i m e = t s ； ( 3 ) 确定在当前时钟t 】m e 下发生的事件类型e i ，i = l ，2 ，n ，并排序。 ( 4 ) 如果t i m e = l f ，根据当前事件类型e j 调用相应的事件例程并产生后续事 件类型及发生时间。否则，转( 6 ) 。 ( 5 ) 将仿真时钟t i m e 推进到下一最早事件发生时刻；转( 3 ) ( 6 ) 仿真结束 事件调度法的第( 5 ) 步体现了仿真时钟的推进机制，是将仿真时钟推进到下一 最早事件的发生时刻。这反映了离散事件系统状