离散事件动态系统及其在网络仿真中的应用

张霖

摘 要：离散事件动态系统已成为控制领域的重要理论基础。文章着眼于离散事件的理论体系，研究了离散事件动态系统的模型设计和分析方法。根据分析结果，结合工程实例，进行了基于DEDS理论的通信网络仿真。仿真结果清晰地展示了通信网络的各项性能指标，从而使离散事件动态系统的特性得以具体化。

关键词：DEDS；系统仿真；模型

离散事件动态系统（Discrete Event Dynamic System，DEDS）是指系统的状态由于某种事件的驱动而在一些不确定的离散时间点上发生变化，它是控制系统分析、设计和大型复杂信息处理的重要理论基础。由于其内部机制的复杂性和状态空间缺乏易操作的运算结构等特点，使得它无法用常规的数学方法来研究，所以计算机仿真实验就成了最为实用的方法之一。现阶段离散事件动态系统的研究目标是运用理论方法结合各种模型，全面反映离散事件动态系统的特性并给出针对实际问题的行之有效的解决方法。

1 离散事件动态系统概述

离散事件动态系统本质上属于人造系统的范畴，而人造系统的含义是指以高技术为背景的一类按人为机制和人为规则所构成的“非物理型”系统，例如计算机通信网络、柔性生产线等都是典型的人造系统，所以这些系统也可以称之为DEDS。

自从对DEDS理论研究以来，先后出现了不同类型的DEDS模型，如：有限状态自动机模型、时序逻辑模型和排队网络模型等[1]。虽然这些模型并不通用，但是从现有模型的形成过程来看，在离散事件动态系统的建模过程中，常用的方法主要有排队网络法、摄动分析法和离散事件系统仿真法等。本文主要介绍离散事件系统仿真法及其在通信网络中的应用。

2 离散事件系统仿真

由于DEDS固有的离散性和内部机制的复杂性，往往难以用常规的差分方程、微分方程等数学模型来描述，同时关于系统动态过程的解析表达也很难得到，而离散事件系统仿真则能借助仿真的方式很好地描述DEDS各方面的性能，因此，它是目前研究DEDS最为流行的方法之一。

2.1 基本概念

DEDS是指对系统状态随时间发生的所有变化建模，离散事件系统的状态变化发生在离散的时间点上，它通过产生一系列系统映像来表示系统随时间的演变。一个给定某个时刻（CLOCK=t）的映像不仅包括时刻t的系统状态，也包括推进中当前所有活动的表和每一个类似的活动即将结束的时间、所有实体和所有集合当前成员的状态，还有累积统计和计数器的当前值以用于仿真结束时的总统计[2]。DESS的仿真机制的核心是时钟推进和事件调度机制，它能在不影响实际系统的情况下客观评价系统的运行性能，并给出合理可行的运行方案，同时，Zeigler提出的DEVS形式化理论能够构成层次化和模块化的抽象仿真器概念，成了仿真系统软件开发和仿真建模的理论基础，定义如下[3]：

将离散事件系统表示为外部事件（X），輸出事件（Y），序贯状态（S），状态转移描述函数（δ），输出函数（λ）和时间推进函数（ta）的逻辑集合：

M=< X，Y，S，δ，λ，ta>

2.2 相关模型

DESS主要包含了系统的理论模型和仿真模型两部分。

理论模型是指对所研究的系统的理论描述，简称一次建模；它分为概念模型、描述模型、功能模型、约束模型、空间模型等5种基本类型。活动周期图法、实体流图法、Petri网法和Euler网法是几种主要的理论模型建模方法。

仿真模型简称二次建模，它建立在理论模型的基础之上，是一种易于在计算机上编程实现的模型。

将理论模型转换成仿真模型，且能在计算机上运行，需要完成3个方面的工作：（1）设计仿真策略，确定仿真模型的表达方法和仿真运行的解算机制。（2）构造仿真模型，详细设计基于某种仿真策略的仿真模型及解算机制。（3）编写仿真程序，使用程序设计语言实现仿真模型[4]。

无论采用哪一种仿真策略，都可以从以下3方面设计仿真模型：（1）设计总控程序；（2）设计基本模型单元的处理程序；（3）编写公共子程序。

DEDS的仿真模型主要有面向事件、面向活动和面向进程3种，它们各有不同特点，我们可根据不同需要选择合适的仿真模型。仿真模型实现的有效方法之一是建立仿真函数库。它的优点在于建模者可以专注于模型的逻辑关系而不必担心模型实现的细节，因此，仿真函数库的建立需要足够灵活，以保证其适用于各类系统的建模。它的基本功能模块包括：随机数生成、实体建模、运行调度、队列建模、仿真结果收集和分析。仿真函数库首先应有调用子程序或函数的能力，并且是通过参数传递来实现。其次，要有实时生成动态数据对象的能力和能够支持应用预编译模块构成的库[4]。

3 基于离散事件动态系统的网络仿真

3.1 通信网络中的DEDS理论

通信网络作为典型的离散事件系统，它充分借鉴了DEDS理论的各项成果。

首先，排队网理论就成功地运用在网络建模中。排队网络的特点是运用概率和统计的方法对DEDS进行建模，一般是先对网络特性作基本的假设，然后采用基于状态稳态概率分布的平均性能分析方法，用以导出表征系统性能的解析表达式。它的优点是能够很好地描述具有成熟的随机过程和概率论的理论基础和常规类型的排队系统。

其次，研究通信网络的另一种有效工具就是仿真分析法。由于通信网络中固有的随机性和离散性，纯粹用数学方法已很难解决问题，所以仿真分析法就成为分析通信网络性能的有效方法，其中具有代表性的就是摄动分析法（Perturbation Analysis，PA）[5]。它既有理论计算，又有仿真试验，吸取了两者的优点，很容易对DEDS的统计性能进行优化分析。所以，PA方法是排队网理论和计算机仿真分析的创造性结合。

3.2 基于DEDS理论的AODV模拟

本文将使用网络仿真软件NS2和OPNET去仿真一个无线AD hoc网络中经典的路由协议—无线自组网按需平面距离向量路由协议（Ad hoc On-demand Distance Vector Routing，AODV），进而通过实验来阐述DEDS理论在网络仿真中的实际应用。

AODV是经典的源驱动路由协议，它包含3种消息类型：路由请求（RREQ）、路由回复（RREP）和路由错误（RERR）。整个协议分为路由发现和路由维护两个阶段。

AODV的优点是避免了路由环路的产生，并且很容易通过编程来实现。

3.2.1 NS2中的AODV模拟

NS2是一个面向对象的，基于离散事件驱动的网络仿真软件。它使用面向对象的编程语言C++和Otcl，其特点是构造模型的自由度高和支持并行化的扩展，比较适合中小规模的网络模拟。

本文采用的仿真场景是在1 000 m×600 m的空间中随机配置100个移动节点，最大移动速度为15 m/s，仿真总时间设定为500 s。节点的运动采用Random Waypoint模型，每个节点将会以给定的速度移至目的地，停留一段时间后，再向下一个随机选取的目的地移动，所有节点均采用AODV路由协议。仿真中采用了7个不同的暂停时间：0 s，50 s，100 s，200 s，300 s，400 s，500 s，然后取7次仿真结果的平均值。为了评估AODV协议的性能，考虑选取归一化路由开销（Normalized Routing Overhead）、端到端时延（End To End Delay）、分组投递率（Packet Delivery Ratio）和路由发现频率（Initiated Routing Frequency）这几个统计量作为评价的指标[6]。实验中首先使用NS2得出数据，然后用Matlab绘图，结果如图1—4所示。

如图1所示，路由开销随着节点停留时间的延长而降低，这是因为网络拓扑结构的变化不再频繁所致。图2表明網络整体的端到端时延随节点停留时间的增加而降低。图3表明分组投递率随节点停留时间的增加而提高。如图4所示，路由发现频率随节点停留时间的增加而降低。

3.2.2 OPNET中的AODV模拟

OPNET采用离散事件驱动的模拟机理和混合建模机制，并提供了包括模型设计、仿真和统计量收集、分析的各种研究工具，同时它还引入了面向对象的编程技术。OPNET的特点是建模方便，功能强大，尤其是在大规模网络模拟中表现卓越。

仿真场景是在一个1 000 m×1 000 m的空间中随机配置1 000个节点，一个服务器，两个标准应用业务配Profile Configure和Application Configure，所有节点均采用AODV路由协议，仿真时间设为500 s。根据AODV和MANET的网络特性，考虑选取端到端时延、负载、吞吐量、丢包数进行分析，结果如图5—8所示。

如图5所示，AODV过程的端到端时延随仿真时间的延长而略有增加，但整体还是比较稳定的，这是因为节点在一个固定的区域内移动，节点的通信距离覆盖了区域的大部分，使得路由缓存不会轻易地发生更新所致。图6和7表明随着路由缓存的建立，网络的负载和吞吐量逐渐增加，但经过一段时间后，随之趋于稳定的状态。如图8所示，丢包数在不同的时间点上均保持在个位数，这说明AODV协议不仅具有良好的稳定性，而且具有极高的传输效率。

4 结语

从以上实验可看出，无论是在中小规模网络仿真领域见长的NS2，还是在大规模网络仿真领域表现卓越的OPNET，对于复杂的AODV协议都能做到全面而精确的仿真，当然对于其他的网络协议也同样能够做到。而它们都用到了DEDS理论的精华，像建模中的排队论，仿真分析中的摄动分析法，以及数据统计中的概率分布、数学期望和方差、曲线拟合、似然比等。由此表明，DEDS理论无论是在中小规模还是在大规模网络仿真领域都有非常普遍的应用，因此，它的价值得以充分体现，同时这也为它在其他领域的应用提供了充分的理论依据和丰富的实践经验。