The DEVS Formalism

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 t₀, 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.

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