Designing real-time systems using imprecise discrete-event system specifications

Real-time (RT) systems include hardware and software components interacting in a tight fashion. Although formal methods for RT systems development have advanced, they are sometimes difficult to apply in practical applications, and scalability is compromised as the complexity of the system scales up. Instead, using modeling and simulation (M&S) methods and tools has showed to be useful for verification of practical aspects of RT systems (and having the advantage to be able to including models of the physical environment they interact with). Although several efforts exist in M&S of RT systems, none of them has considered problems of transient overloading in the RT systems specifications. Here, we introduce a new theoretical framework called I-DEVS (imprecise discrete event systems specification) with the goal of guaranteeing responses to inputs within specified time constraints under such transient overloading conditions. The solution presented here has the advantages of a formal specification and the practicality of an M&S-based approach. We also discuss how to define hierarchical models running in RT, and we present a set of tools that can be applied to develop RT-embedded applications, and RT simulations.     

Ptolemy离散事件模型形式化验证方法

Ptolemy是一个广泛应用于信息物理融合系统的建模和仿真工具包,主要通过仿真的方式保证所建模型的正确性.形式化方法是保证系统正确性的重要方法之一.本文提出了一种基于形式模型转换的方法来验证离散事件模型的正确性.离散事件模型根据不同事件的时间戳触发组件,时间自动机模型能够表达这个特征,因此选用Uppaal作为验证工具.首先定义了离散事件模型的形式语义,其次设计了一组从离散事件模型到时间自动机的映射规则.然后在Ptolemy环境中实现了一个插件,可以自动将离散事件模型转换为时间自动机模型,并通过调用Uppaal验证内核完成验证.最后以一个交通信号灯控制系统为例进行了成功的转换和验证,实验结果证实了该方法能够验证Ptolemy离散事件模型的正确性.     

半张量积理论在网络遥操作系统中的应用

研究了网络遥操作系统的半张量积建模问题.网络遥操作系统中存在人机交互以及大时延事件,这使得系统中既有离散事件动态又有连续动态,当系统的离散事件动态与底层连续动态相互作用耦合强烈时,系统的性能、行为分析变得更为复杂.本文通过引入半张量积给出了一种新的半张量积混杂建模方法,它把一类特定事件系统建模为布尔系统,通过半张量积方法得到类似于离散动态系统的方程.它将系统中离散事件和连续动态相互耦合的地方表达为半张量积的形式,最后经过扩张简化得到完整统一的系统数学模型,它将有利于进一步分析、计算.本文给出的半张量积建模方法和步骤具有一定的通用性和一般性.此外本文还对基于半张量积的混杂网络遥操作系统模型进行了基于事件控制和时间控制的仿真.仿真结果表明,半张量积建模方法完全可信、可行,基于事件控制的方法在网络遥操作控制中明显优于基于时间控制的方法.     

SimQPN—A tool and methodology for analyzing queueing Petri net models by means of simulation

The queueing Petri net (QPN) paradigm provides a number of benefits over conventional modeling paradigms such as queueing networks and generalized stochastic Petri nets. Using queueing Petri nets (QPNs), one can integrate both hardware and software aspects of system behavior into the same model. This lends itself very well to modeling distributed component-based systems, such as modern e-business applications. However, currently available tools and techniques for QPN analysis suffer the state space explosion problem, imposing a limit on the size of the models that are tractable. In this paper, we present SimQPN—a simulation tool for QPNs that provides an alternative approach to analyze QPN models, circumventing the state space explosion problem. In doing this, we propose a methodology for analyzing QPN models by means of discrete event simulation. The methodology shows how to simulate QPN models and analyze the output data from simulation runs. We validate our approach by applying it to study several different QPN models, ranging from simple models to models of realistic systems. The performance of point and interval estimators implemented in SimQPN is subjected to a rigorous experimental analysis.     

DEVS methodology for evaluating time-constrained message routing policies

Due to its ability to support temporal issues of systems, discrete event simulation is widely applicable to real-time system design. This paper presents a methodology for the modeling and simulation of time-constrained message routing policies for hypercube interconnected real-time systems. The methodology is based on a framework called the DEVS (discrete event systems specification) formalism which supports modular and hierarchical specification of discrete event models. Within the methodology, we first develop DEVS specification for models for hypercube computers and experimental frames to measure the performance of alternative message routing policies. We then implement such specification in DEVSIM++, a C++-based modeling/simulation environment that implements the DEVS formalism. Simulations of various message routing policies are performed, and the performances of such policies are compared.     

SYSTEM THEORETIC FORMALISMS FOR COMBINED DISCRETE-CONTINUOUS SYSTEM SIMULATION

In this paper we present an approach to combined discrete-continuous modelling which can be used to model and simulate an intelligent multi-layer control architecture as can be found in high autonomy systems. The modelling approach is based on system theoretical concepts; the three system specification formalisms-differential equation, discrete time, and the discrete event system specification formalism-have been combined to facilitate multi-formalisms modelling. Simulation concepts are based on the abstract simulator concept for discrete event simulation developed by Zeigler. Similar simulation methods have been developed to simulate modular, hierarchical discrete time and differential equation specified systems as well as multi-formalism models. Included in the paper are several examples of multi-formalism models together with the simulation results from the STIMS environment-an implementation of the modelling and simulation concepts in Interlisp-D/LOOPS.     

Distributed simulation of DEVS and Cell-DEVS models in CD++ using Web-Services

Discrete event system specification (DEVS) is a modeling and simulation formalism that has been widely used to study the dynamics of discrete event systems. Cell-DEVS is a DEVS-based formalism that defines spatial models as a cell space assembled of a group of DEVS models connected together. CD++ is a modeling and simulation toolkit capable of executing DEVS and Cell-DEVS models that has proven to be useful for executing complex models. We present the design and implementation of a distributed simulation engine, known as D-CD++, which exposes CD++ simulation utilities as machine-consumable services. In addition, we present the design and implementation of the Web-Service components which enable D-CD++ to expose the simulation functionalities to remote users. Enabling CD++ with Web-Services technology provides a solid framework for interoperating different DEVS implementations in order to achieve a standard DEVS Modeling Language and simulation protocols. This paves the road towards DEVS standardization, while providing a mashup approach, which can lead to higher degree of reuse and reduced time to set up and run experiments, and making sharing among remote users more effective. To prove this fact, we integrate it within larger services (such as a 3D visualization engine), showing the mechanism to incorporate to other environments (including geographical information systems, web-based applications and other modeling and simulation tools) through using standard Web-Service tools. Performance of D-CD++, major bottlenecks and communication overheads are analyzed.     

Intelligent Control Paradigm for Dynamic Discrete Event System Simulation

Simulation based control of discrete event systems has been a potential approach to support decision-making in the manufacturing scenario. In this paper, a knowledge intensive simulation modelling approach for a discrete even system is investigated. Based on the proposed simulation model, a robust control mechanism is presented that is believed to add significant value to discrete event dynamic system. The algorithm utilises neural network feedforward control plus robust proportional derivative feedback control to achieve control performance and output stability. The novel simulation approach, as well as the proposed controller, is implemented in an Extend TM environment and the effectiveness and usefulness of the proposed controller are verified, industrially, in the hard disk drive assembly process, a significant component of the Singapore manufacturing economy.     

Synchronization in federation community networks

A large scale High Level Architecture (HLA)-based simulation can be constructed using a network of simulation federations to form a “federation community”. This effort is often for the sake of enhancing scalability, interoperability, composability and enabling information security. Synchronization mechanisms are essential to coordinate the execution of federates and event transmissions across the boundaries of interlinked federations. We have developed a generic synchronization mechanism for federation community networks with its correctness mathematically proved. The synchronization mechanism suits various types of federation community network and supports the reusability of legacy federates. It is platform-neutral and independent of federate modeling approaches. The synchronization mechanism has been evaluated in the context of the Grid-enabled federation community approach, which allows simulation users to benefit from both Grid computing technologies and the federation community approach. A series of experiments has been carried out to validate and benchmark the synchronization mechanism. The experimental results indicate that the proposed mechanism provides correct time management services to federation communities. The results also show that the mechanism exhibits encouraging performance in terms of synchronization efficiency and scalability.     

An integrated data collection and analysis framework for remote monitoring and planning of construction operations

Recent advances in data collection and operations analysis techniques have facilitated the process of designing, analyzing, planning, and controlling of engineering processes. Mathematical tools such as graphical models, scheduling techniques, operations research, and simulation have enabled engineers to create models that represent activities, resources, and the environment under which a project is taking place. Traditionally, most simulation paradigms use static or historical data to create computer interpretable representations of real engineering systems. The suitability of this approach for modeling construction operations, however, has always been a challenge since most construction projects are unique in nature as every project is different in design, specifications, methods, and standards. Due to the dynamic nature and complexity of most construction operations, there is a significant need for a methodology that combines the capabilities of traditional modeling of engineering systems and real time field data collection. This paper presents the requirements and applicability of a data-driven modeling framework capable of collecting and manipulating real time field data from construction equipment, creating dynamic 3D visualizations of ongoing engineering activities, and updating the contents of a discrete event simulation model representing the real engineering system. The developed framework can be adopted for use by project decision-makers for short-term project planning and control since the resulting simulation and visualization are completely based on the latest status of project entities.     

DEVSpecL: DEVS specification language for modeling,simulation and analysis of discrete event systems

Discrete EVent Systems Specification (DEVS) formalism supports specification of discrete event models in a hierarchical modular manner. This paper proposes a DEVS modeling language called DEVS Specification Language (DEVSpecL) based on which discrete event systems are modeled, simulated and analyzed within a DEVS-based framework for seamless systems design. Models specified in DEVSpecL can be translated in different forms of codes by code generators, which are executed with various tools for models verification, logical analysis, performance evaluation, and others.     

Specification and simulation of queuing network models using Domain-Specific Languages

Queuing network models (QNMs) provide powerful notations and tools for modeling and analyzing the performance of many different kinds of systems. Although several powerful tools currently exist for solving QNMs, some of these tools define their own model representations, have been developed in platform-specific ways, and are normally difficult to extend for coping with new system properties, probability distributions or system behaviors. This paper shows how Domain Specific Languages (DSLs), when used in conjunction with Model-driven engineering techniques, provide a high-level and very flexible approach for the specification and analysis of QNMs. We build on top of an existing metamodel for QNMs (PMIF) to define a DSL and its associated tools (editor and simulation engine), able to provide a high-level notation for the specification of different kinds of QNMs, and easy to extend for dealing with other probability distributions or system properties, such as system reliability.     

The OsMoSys approach to multi-formalism modeling of systems

Analysis and simulation of complex systems are facilitated by the availability of appropriate modeling formalisms and tools. In many cases, no single analysis and modeling method can successfully cope with all aspects of a complex system: a multi-formalism multi-solution approach is very appealing, since it offers the possibility of applying the most suitable formalisms and solution techniques to model and analyze different components or aspects of a system. Another important feature that a successfull modeling approach should include is the possibility of reusing (sub)models: by composing parameterized submodels and then instantiating the parameters, complete models of different scenarios can be obtained and analyzed.This paper introduces an innovative approach to multi-formalism modeling of systems that is part of the OsMoSys (Object-based multi-formaliSm MOdeling of SYStems) framework. OsMoSys uses the proposed modeling approach to build multi-formalism models, and workflow management to achieve multi-solution. Our modeling approach is based on meta-modeling, allowing to easily define and integrate different formalisms, and on some concepts from object orientation. Its main objectives are the interoperability of different formalisms and the definition of mechanisms to guarantee the flexibility and the scalability of the modeling framework.     

POEMS: end-to-end performance design of large parallel adaptive computational systems

The POEMS project is creating an environment for end-to-end performance modeling of complex parallel and distributed systems, spanning the domains of application software, runtime and operating system software, and hardware architecture. Toward this end, the POEMS framework supports composition of component models from these different domains into an end-to-end system model. This composition can be specified using a generalized graph model of a parallel system, together with interface specifications that carry information about component behaviors and evaluation methods. The POEMS Specification Language compiler will generate an end-to-end system model automatically from such a specification. The components of the target system may be modeled using different modeling paradigms and at various levels of detail. Therefore, evaluation of a POEMS end-to-end system model may require a variety of evaluation tools including specialized equation solvers, queuing network solvers, and discrete event simulators. A single application representation based on static and dynamic task graphs serves as a common workload representation for all these modeling approaches. Sophisticated parallelizing compiler techniques allow this representation to be generated automatically for a given parallel program. POEMS includes a library of predefined analytical and simulation component models of the different domains and a knowledge base that describes performance properties of widely used algorithms. The paper provides an overview of the POEMS methodology and illustrates several of its key components. The modeling capabilities are demonstrated by predicting the performance of alternative configurations of Sweep3D, a benchmark for evaluating wavefront application technologies and high-performance, parallel architectures.     

Hybrid fluid modeling approach for performance analysis of P2P live video streaming systems

In this paper a hybrid modeling approach with different modeling formalisms and solution methods is employed in order to analyze the performance of peer to peer live video streaming systems. We conjointly use queuing networks and Fluid Stochastic Petri Nets, developing several performance models to analyze the behavior of rather complex systems. The models account for: network topology, peer churn, scalability, peer average group size, peer upload bandwidth heterogeneity and video buffering, while introducing several features unconsidered in previous performance models, such as: admission control for lower contributing peers, control traffic overhead and internet traffic packet loss. Our analytical and simulation results disclose the optimum number of peers in a neighborhood, the minimum required server upload bandwidth, the optimal buffer size and the influence of control traffic overhead. The analysis reveals the existence of a performance switch-point (i.e. threshold) up to which system scaling is beneficial, whereas performance steeply decreases thereafter. Several degrees of degraded service are introduced to explore performance with arbitrary percentage of lost video frames and provide support for protocols that use scalable video coding techniques. We also find that implementation of admission control does not improve performance and may discourage new peers if waiting times for joining the system increase.     

Exploring airport traffic capability using Petri net based model

The first part of the paper introduces a novel tool for modeling and simulation of discrete event system. This tool called GPenSIM is a Petri net based simulator and offers significant benefits to model builders such as flexibility to include diverse libraries, ease of extending the models, and ease of programming. The second part of the paper presents a case study on modeling and optimization of airport traffic management; this study is to explore air traffic management capability of Evenes airport in Norway. The case study shows that with GPenSIM, modeling and simulation problems of large industrial discrete event systems can be done. Future research directions are discussed as well.     

Modeling and performance evaluation of supply chains using batch deterministic and stochastic Petri nets

Batch deterministic and stochastic Petri nets are introduced as a tool for modeling and performance evaluation of supply chains. The new model is developed by enhancing deterministic and stochastic Petri nets (DSPNs) with batch places and batch tokens. By incorporating stochastic Petri nets (SPNs) with the batch features, inhibitor arcs, and marking-dependent weights, operational policies of supply chains such as inventory policies can be easily described in the model. Methods for structural and performance analysis of the model are developed by extending existing ones for DSPNs. As applications, an inventory system and an industrial supply chain are modeled and their performances are evaluated analytically and by simulation, respectively, using this BSPN model. The applications demonstrate that our model and associated methods can solve some important supply chain modeling and analysis issues. Note to Practitioners-This paper was motivated by the problem of performance analysis and optimization of supply chains but it also applies to other discrete event systems where materials are processed in finite discrete quantities (batches) and operations are performed in a batch way because of batch inputs and/or in order to take advantages of the economies of scale. Existing Petri net modeling and analysis tools for such systems ignore their batch features, making their modeling complicated. This paper suggests a new model called batch deterministic and stochastic Petri nets (BDSPNs) by enhancing deterministic and stochastic Petri nets with batch places and batch tokens. Methods for structural and performance analysis of the model are developed. We then show how an inventory system and a real-life supply chain can be modeled and their performances can be evaluated analytically and by simulation respectively based on the model. The model and associated analysis methods therefore provide a promising tool for modeling and performance evaluation of supply chains.     

System-of-Systems Modeling and Simulation of a Ship Environment With Wireless and Intelligent Maintenance Technologies

Modeling and simulation environments are needed to support decision making in Navy Warfighters, which are emergent systems that pose a challenge to operations management. Ships consist of complex interconnected systems such as the infrastructure, crew, and workflow. A system-of-systems approach using agent-based modeling is applied here to develop workflow simulations involving a ship's crew conducting routine maintenance, watch duty, and reporting functions. Simple models are used to describe basic behavioral traits and intelligence in crew members; machinery including sensors for intelligent maintenance; equipment consuming power; mobile and stationary communication network access points; models for data transfer over the network; crew mobility models; power distribution and trimming models for the electrical system; and a fire model to simulate emergency scenarios. The simulation results demonstrate an increase in machine availability due to the implementation of intelligent maintenance systems. The effects of wireless-network usage on crew resource utilization and overall ship capability in normal operational scenarios are also demonstrated. A simple rescheduling algorithm is used to improve crew utilization and estimate manning requirements. The effects of emergency scenarios such as fires in different locations are also studied. Sensitivity analysis is presented to verify the developed model, and a note on validation is given.     

Using a Discrete-Event System Specifications (DEVS) for designing a Modelica compiler

We introduce a new architecture for the design of a tool for modeling and simulation of continuous and hybrid systems. The environment includes a compiler based on Modelica, a modular and a causal standard specification language for physical systems modeling (the tool supports models composed using certain component classes defined in the Modelica Standard Library, and the instantiation, parameterization and connection of these MSL components are described using a subset of Modelica). Models are defined in Modelica and are translated into DEVS models. DEVS theory (originally defined for modeling and simulation of discrete event systems) was extended in order to permit defining these of models. The different steps in the compiling process are show, including how to model these dynamic systems under the discrete event abstraction, including examples of model simulation with their execution results.     

Performance Modeling and Evaluation of Distributed Component-Based Systems Using Queueing Petri Nets

Performance models are used increasingly throughout the phases of the software engineering lifecycle of distributed component-based systems. However, as systems grow in size and complexity, building models that accurately capture the different aspects of their behavior becomes a more and more challenging task. In this paper, we present a novel case study of a realistic distributed component-based system, showing how Queueing Petri Net models can be exploited as a powerful performance prediction tool in the software engineering process. A detailed system model is built in a step-by-step fashion, validated, and then used to evaluate the system performance and scalability. Along with the case study, a practical performance modeling methodology is presented which helps to construct models that accurately reflect the system performance and scalability characteristics. Taking advantage of the modeling power and expressiveness of Queueing Petri Nets, our approach makes it possible to model the system at a higher degree of accuracy, providing a number of important benefits.