www.sensorsmag.com
June 2002
|
 |
|
SIMULATION SOFTWARE
|
Imitating Life:
An Introduction to
Computer Simulation and Modeling
Part 2: Simulation Models for Systems that Change Over Time
Ed Ramsden, Lattice Semiconductor Corp.
The first part of this article, which appeared in the May 2002 issue of Sensors, described several types of static simulation models. The common characteristic of these models is that they lack any memory of past inputs or internal conditions. A change of the inputs of a static model results in an instantaneous change in its outputs.
But for many real systems, history plays a major role in determining behavior. These systems are said to exhibit dynamic behavior. In a dynamic system, the outputs are a function of both the present values of the input and internal state variables, which are themselves functions of historical data. Part 2 of this article will explore several different types of dynamic models through examples of simple dynamic systems. (Graphics are numbered consecutively from Part 1.)
Dynamic Systems
Dynamic systems with variables that vary continuously as a function of time are often described with first-order ordinary differential equations (ODEs). In this formulation, one or more state variables x describe the present condition of the system, and dx/dt represents the rate of change of each state variable. A function of both the present state x(t) and present input u(t) defines the rate of change of the state variables. Because the system’s output y(t) can be dependent on both the state and the inputs, it’s also defined as a function g( ) of the inputs and system state. This yields the following equations:
 |
(10) |
When you need multiple state or output variables to define the system, an additional function of the inputs and state variables defines each additional state or output variable.
To solve a first-order ODE numerically on a computer, you must approximate it using a difference equation. One simple approximation of Equation 10 is:
 |
(11) |
In this formulation, 
t is a small, finite increment in time, and x is the change in x that occurs with a change in time of t. In a numerical simulation, t is often referred to as the simulation timestep, or clock tick, because time in the simulation is advanced in discrete increments of t. Changes in the simulation model’s state occur only when simulation time advances by t.
A significant advantage of casting a dynamic model in the form of first-order ODEs, and ultimately into difference equations, is that you define the immediate future values of the state variables in terms of the present values, making it simple to compute these values algorithmically. This compute-friendly form of difference equation is:
 |
(12) |
In this form, it becomes straightforward to translate into a computer program to repetitively calculate new values of x(t) while advancing time in steps of t.
X = 0
FOR t = dt to stoptime STEP dt
X = X + f( X, U) * dt
NEXT t
In this program, X is changed by an amount proportional to the time step dt. As you make dt smaller, the discrete model will tend to more closely approximate the exact solution of the original ODE. Note that the first statement in the program is X = 0; this is to define the initial condition of X at t = 0. Proper consideration of initial conditions is often important in simulations because different choices of initial conditions can yield different results.
The general technique of approximately solving an ODE by summing a series of small, discrete changes is called numerical integration. The example in Equation 12 shows one of the simplest numerical integration techniques (the Forward Euler method). Many more sophisticated techniques have been developed to solve various classes of ODEs and provide more accurate solutions.
|
As a simple example of a dynamic system, consider the flight of a cannonball (see Figure 10). Ignoring non-ideal effects, such as air resistance, the cannonball is subject to constant acceleration downward (–ay) from gravity, and zero acceleration horizontally (ax direction). The acceleration is the derivative in time of the velocity (vx,vy), and the velocity is the derivative in time of the position (px,py). These relationships result in four equations:
 |
(13) |
The initial conditions for these equations are the position of the cannon (0,0) and a function of the muzzle velocity (vm) and elevation angle (
):
 |
(14) |
A computer program to integrate these equations could be written:
Elevation = 0.5326
’ 30 degrees expressed in radians
’ BASIC uses radians for trig functions
Vm = 300 ’ muzzle velocity meters/s
ax = 0 ’ no horizontal acceleration
ay = -9.8 ’ gravity in m/s2
vx = Vm * Cos(Elevation)
vy = Vm * Sin(Elevation)
px = 0
py = 0
dt = 0.01 ’ 1/100 second timesteps
Stoptime = 30 ’ seconds
For T = 0 To Stoptime Step dt
Print T, vx, vy, px, py
’ print out results
dvx = ax * dt ’ integrate vx
vx = vx + dvx
dvy = ay * dt ’ integrate vy
vy = vy + dvy
dpx = vx * dt ’ integrate px
px = px + dpx
dpy = vy * dt ’ integrate py
py = py + dpy
Next T
Although the dynamic system described here is simple, the same modeling techniques can be used to simulate more complex systems. For example, consider the effect of air resistance. This effect will form a feedback loop in the model because the force on the projectile will be dependent on its velocity. Accounting for the new effect doesn’t require a different modeling paradigm but merely involves computing the air resistance force for a given velocity and modifying the expressions that integrate acceleration.
Discrete-State Dynamic Systems
While differential equations are useful for describing natural systems that vary continuously, many manmade systems are best described as varying in near-instantaneous jumps between discrete states. For example, consider a refrigerator, which can be in one of three states:
Running (Compressor on) Idling (Compressor off) Defrosting (Compressor off and Defroster on)
In this case, there are no significant halfway conditions between the various states; the transitions among the operating states are for all practical purposes complete and instantaneous. For this reason, you can describe a refrigerator as a discrete-state system.
A state-transition diagram (see Figure 11a) is a useful way of describing discrete-state systems.
 Figure 11. A refrigerator can be modeled partly as a discrete-state system, with a behavior described by a state-transition diagram (A). Changes in the refrigerator's continuous state (temperature and frost levels) trigger changes in the refrigerator's discrete state (running, idling, or defrosting) (B). |
This type of diagram shows the possible states of the system (the bubbles) and the possible transitions between states (arcs). Because you can often leave a given state and head to one of several others, you must also specify the conditions under which transitions can occur.
The formulation for a discrete-state system is similar to that of the continuous systems previously described, except that instead of specifying the degree to which a state variable changes, you must specify a new value for the state variable (x(t+t)). This results in a state transition equation:
 |
(15) |
As in the case of a continuous-state system, you still define output variables in terms of the present value of the states and the inputs.
 |
(16) |
Note that this model is actually equivalent to the difference-based model based on differential equations; the difference is largely a matter of how you choose to look at the problem. The difference-based viewpoint assumes that state variables will be updated by small increments, while the discrete-state viewpoint assumes that the state can be updated to any arbitrary value. One consequence of this is that because states are expected to change in arbitrarily large jumps, the size of the timestep (dt) (assuming it is sufficiently small) may not play any part in the model formulation.
Another and perhaps more significant distinction between a difference-based and a discrete-state model is that the function being evaluated by the former will generally yield a numerical quantity that is intended to be numerically integrated, while the function being evaluated by the latter may be an abstract state. For this reason, discrete-state update functions often depend heavily on look-up tables as well as conditional and Boolean expressions. In many cases, expressions in a computer programming language are often the most straightforward way to describe them. In the case of the refrigerator, the state transition function can be described with a look-up table (see Table 4).
|
TABLE 4 |
||||
|
State Transition Function Look-Up Table |
||||
|
|
Input Conditions
|
|||
|
Present State
|
Cool enough, not frosty |
Cool enough, frosty |
Too warm not frosty |
Too warm, frosty |
|
IDLE
|
IDLE
|
DEFROST
|
RUN
|
DEFROST
|
|
RUN
|
IDLE
|
IDLE
|
RUN
|
RUN
|
|
DEFROST
|
IDLE
|
DEFROST
|
IDLE
|
DEFROST
|
You should define a state-transition function over all possible conditions of input and present state; otherwise, the model can exhibit unintended behaviors if the undefined conditions arise during a simulation. In this example, with three states and four possible combinations of input conditions involving temperature and frost, building a look-up table is straightforward. For more complex cases, however, the size of the look-up table can become prohibitive. In these circumstances, you can often better define the state-transition function using statements in a computer programming language, as shown below.
SELECT CASE State_Present ‘ present value
CASE IDLE
IF Too_Much_Frost THEN
State_Next = DEFROST
ELSE IF Too_Warm THEN
State_Next = RUN
ELSE
State_Next = IDLE
END IF
CASE RUN
IF Too_Warm then
State_Next = RUN
ELSE
State_Next = IDLE
END IF
CASE DEFROST
IF Too_Much_Frost THEN
State_Next = DEFROST
ELSE
State_Next = IDLE
END IF
END SELECT
This code segment describes the same state-transition function as the above look-up table, but in a way that is both simpler to formulate and to understand. Once you have a suitable state-transition function (F_Refrigerator), the program implementation of a discrete-state model is nearly trivial:
FOR k = dt to StopTime step dt
State = F_Refrigerator(State, Too_Warm, Too_Much_Frost)
NEXT k
A simulation of the refrigerator model might exhibit behavior like that shown in Figure 11b. Note that for this simulation to work, both temperature and frost levels must also be modeled. Because temperature and frost change continuously, these variables typically need to be simulated using difference models, such as those described in the previous section.
Discrete-Event Systems
In both differential and discrete-state models, the values of the state variables change only at simulation clock ticks. So far, we’ve assumed that the simulation clock is periodic and evenly spaced, with an interval of t; simulations built this way are said to be time driven.
For many types of discrete-state systems, time-driven models are not the most effective means of describing the system. Consider a model of a bank. Customers enter the bank at random intervals and enter a single line to wait for the next available teller. If not occupied, a teller will serve the customer at the head of the line. Each customer’s transaction will require some time to process, after which the teller can serve the next customer.
In this system, the tellers have discrete states (e.g., busy and idle), as does the line of waiting customers (the number of customers in line). Although this system could be simulated with a time-driven model, a small time step relative to the average activity level may be required to accurately model the system.
For example, all of the tellers may be occupied for several minutes with difficult customers, and then they may call up several customers within seconds of each other. If you want to model this system with a fixed-time step and maintain a degree of fidelity to the real system, the time step will have to be smaller than the smallest time interval of interest. What this means in practice is that the simulation will use most of its computational resources, repetitively evaluating the same functions over and over with relatively few significant changes in state.
An alternative approach is to perform computations only at significant changes in system state, which are often called events. In an event-driven model, you schedule events to occur at particular times in the future. The simulator then looks at the set of pending events and selects the earliest one in that set to be the next event. Once that is chosen, the simulator advances simulation time to that of the next event and then executes it.
While you can use traditional programming languages (e.g., C, Fortran, and Basic) to build event-driven models, software companies have developed specialized discrete-event simulation languages that automatically handle much of the housekeeping required to implement a model. If you use a discrete-modeling language, you can represent the bank-teller model with a collection of processes and events corresponding to the entities and activities in the system. For example, consider the process by which customers enter the line. You can model this as an event that adds a customer to the line and then schedules itself to occur sometime in the future. If there is a free teller, it also schedules the teller to take a customer from the line.
Event Arriving_customer
’ Add customer to queue
Queue_length = Queue_length+1
’ If teller not busy, dispatch customer-
’ -Only one teller used for clarity
If Teller_state =IDLE then schedule
Teller_Start in 0 ‘NOW!
’ schedule another customer for future
’ arrival
Schedule Arriving_customer in Random_arrival_time
End event
To continue with this example, you might represent each teller by a pair of events in which the teller periodically (at random intervals) tries to take a customer from the queue, process the transaction, and repeat the cycle. The Teller_Start routine tries to get a customer. If successful, it sets the teller state to busy and then schedules a second event (Teller_Finish), which returns the teller back to the idle state when done with the customer.
Event Teller_Start
If Queue_length =0 then
Teller_State=IDLE
’ can’t take a customer
Else
Queue_length=Queue_length-1
’ take customer
Teller_State=BUSY
’ become BUSY
’ schedule teller to get done with
’ customer in some time
Schedule Teller_Finish for
Random_Processing_time
End if
End Event
Event Teller_Finish
Teller_State = IDLE
Schedule Teller_Start in 0
’ ready for new customer
End event
Of course, at some point when the simulation starts, the Arriving_customer event must be initially scheduled or nothing will happen.
In a discrete-event model such as this one, the simulator’s clock advances in an irregular fashion, depending on the order of occurring events. In this simulation, because the events are scheduled with random intervals to simulate statistical behavior, the event sequence can vary from run to run.
A significant benefit of using a modeling language (discrete-event or otherwise) is that it frees you from having to focus on many computational details and allows you to focus the bulk of your attention on the model. Because many real-world systems map well into a discrete-event modeling paradigm, this simulation technique has found widespread use. Typical applications of discrete-event simulations include factory production planning, analysis of traffic and mass transit systems, and computer network performance estimation.
Conclusion
This article has attempted to present a survey of several representative computational techniques used to implement computer simulations, as well as some of the underlying modeling paradigms.
SIDEBAR 1:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
SIDEBAR 2:
|
SIDEBAR 3:
|
SIDEBAR 4:
|
SIDEBAR 5:
|
SIDEBAR 6:
|
Ed Ramsden is Senior Applications Engineer, Mixed Signal Products, Lattice Semiconductor Corp., 5555 NE Moore Ct., Hillsboro, OR 97124-8347; 503-268-8648, fax 503-268-8693, ed.ramsden@latticesemi.com.
|
|
|
|