The DEVS Formalism

The DEVS Formalism

Rhys Goldstein (Autodesk Research, Canada), Gabriel A. Wainer (Carleton University, Canada) and Azam Khan (Autodesk Research, Canada)
DOI: 10.4018/978-1-4666-4369-7.ch003
OnDemand PDF Download:
$37.50

Abstract

The DEVS formalism is a set of conventions introduced in 1976 for the specification of discrete event simulation models. This chapter explains the core concepts of DEVS by applying the formalism to a single ongoing example. First, the example is introduced as a set of informal requirements from which a formal specification is to be developed. Readers are then presented with alternative sets of modeling conventions which, lacking the DEVS formalism’s approach to representing state, prove inadequate for the example. The chapter exploits the DEVS formalism’s support for modular model design, as the system in the example is specified first in parts and later as a combination of those parts. The concept of legitimacy is demonstrated on various model specifications, and the relationship between DEVS and both object-oriented programming and parallel computing is discussed.
Chapter Preview
Top

Introduction

The DEVS (Discrete Event System Specification) formalism is a set of conventions for specifying discrete event simulation models. It was introduced in 1976 with the publication of Bernard Zeigler’s Theory of Modeling and Simulation (Zeigler, 1976). While the latest edition of that book (Zeigler et al., 2000) provides a comprehensive overview of DEVS theory, here we focus on the application of the core concepts. The chapter is organized around a particular example: the simulation of an automatic lighting system in an office environment. We develop this example from a set of informal requirements to a complete formal specification.

Before we begin, let us clarify the difference between a discrete time simulation and a discrete event simulation. Numerous simulations are implemented with a time variable t that starts at some initial value t0, and increases by a fixed time step Δt between calculations. The flowchart in Figure 1 outlines the procedure.

Figure 1.

Discrete time simulation procedure

This type of simulation is a discrete time simulation, as t is effectively a discrete variable. The approach is simple and familiar, but limited in that the duration between any pair of inputs, outputs, or state transitions must be a multiple of Δt.

DEVS can be applied to discrete time simulation, but it is best suited to the discrete event approach for which it was invented. In a discrete event simulation, time is continuous. Any pair of events can be separated by any length of time, and there is generally no need for a global Δt. Later in the chapter we will present a procedure like that in Figure 1, but suitable for all discrete event simulations.

The adoption of a discrete event approach impacts the model development process. For example, suppose one designs separate models for different parts of a larger system. Ideally, modeling the overall system would be a simple matter of combining these submodels. With discrete time simulation, one would have to choose a single Δt appropriate for every submodel, or invent some scheme by which only certain submodels experience events at any given iteration. With DEVS, two models can be coupled together regardless of how they handle time advancement. The only requirement is that the output values of one model are consistent with the input values of the other.

In this chapter we exploit the DEVS formalism’s support for modular model design. First we present an example of a system as a combination of three interacting subsystems. We later specify an atomic model, an indivisible DEVS model, for each of these subsystems. From there we specify a coupled model, a DEVS model composed of other DEVS models, by combining the three atomic models. As we proceed from atomic models to coupled models, we analyze the legitimacy of various specifications. Towards the end of the chapter, we discuss DEVS in the context of object-oriented programming and parallel computing.

Top

An Example

Buildings are believed to be responsible for roughly one third of greenhouse gas emissions worldwide (United Nations Environment Programme, 2009). Understandably, there is a growing interest in technologies that reduce the energy required for building operation.

Consider an automatic lighting system in an office building. At its simplest, such a system consists of a motion detector controlling a lighting fixture for a single workstation. When an office worker is present, the motion detector signals the lighting fixture, and the lighting fixture keeps the workstation illuminated. When the worker leaves, the motion detector signals the lighting fixture again, and the lights may turn off to save energy. We are interested in modeling the overall system; not just the Detector and the Fixture subsystems that compose the Automatic Lighting System, but the Worker as well. Combined, the three subsystems compose the Automatic Lighting Environment as illustrated in Figure 2.

Figure 2.

Conceptual model of an automatic lighting environment

Complete Chapter List

Search this Book:
Reset