XFD-DEVS

W3C XML Schema for Finite Deterministic(FD) DEVS Models

DEVS Model Generation using JAXB Implementation




Bernard P. Zeigler,
Arizona Center for Integrative Modeling and Simulation
University of Arizona, Tucson, AZ		 Saurabh Mittal
Dunip Technologies, New Delhi, India		 Moon Ho Hwang
Dassault Systemems Delmia Corp.
Auburn Hills, MI 48326, USA



Formal Specification of XFD-DEVS
 Natural Language for XFD-DEVS
 References
Working with GUI



This work is aimed towards development of DEVS models using template-based design. It is motivated by work done by Dr. Mittal during his PhD thesis on DEVS Unified Process (DUNIP) and Dr. Hwang's research on verifiable Finite Deterministic (FD) DEVS. Natural Language implementation of XFD-DEVS has been contributed by Dr. Zeigler.


Formal Specification of XFD-DEVS

The semantics of an XFD-DEVS specification are given by showing how an XFD-DEVS description specifies a DEVS model. This approach replicates that employed to prescribe the semantics of the DEVS itself, as a specification of a subclass within the broader class of I/O Dynamic systems [3]. An XFD-DEVS is specified by a structure:

XFD-DEVS = <incomingMessageSet, outgoingMessageSet, StateSet, TimeAdvanceTable, InternalTransitionTable, ExternalTransitionTable,OutputTable>
where
incomingMessageSet, outgoingMessageSet, StateSet are finite sets
TimeAdvanceTable: StateSet → R0,∞+  (the positive reals with zero and infinity)
InternalTransitionTable: StateSet → StateSet
ExternalTransitionTable: StateSet × incomingMessageSet → StateSet, and
OutputTable: StateSet → 2outgoingMsgSet  ( = the set of subsets of outgoingMsgSet)

The mapping from an XFD-DEVS to a DEVS model is given in the following table:

XFD-DEVS Parameter
 Comment
incomingMessageSet
 for each incoming message, Msg, we construct an input port inMsg and allow Msg as the only value on it
outgoingMsgSet
 For each outgoing message, Msg we construct an output port outMsg and allow Msg as the only value on it. Bags of such message output are allowed. They can be constructed by providing rows in the internal transition table having different output paths for the same transition
StateSet
 States in XFD-DEVS become phases in DEVS and have an associated time advance value, sigma
TimeAdvanceTable: StateSet → R0,∞+ The TimeAdvanceTable in XFD-DEVS is used to assign initial sigma values in DEVS as is seen below.
InternalTransitionTable: StateSet → StateSet The  InternalTransitionTable in XFD-DEVS determines the phase of the next phase in DEVS while the  TimeAdvanceTable determines the initial value of sigma in this phase.
ExternalTransitionTable: StateSet × incomingMessageSet → StateSet When it is defined, the  ExternalTransitionTable in XFD-DEVS determines the phase of the next state in DEVS while the  TimeAdvanceTable determines the initial value of sigma in this state.  We say that the ExternalTransitionTable is defined for a state and incoming message when there is an entry in the table for that pair. Thus, when you don’t provide a next state for a particular combination of states and inputs in XFD-DEVS, it is interpreted in the DEVS model as an order to ignore the input and continue in the state to the original transition time.

The confluent function must be specified by the modeler in the DEVS model constructed from XFD-DEVS
OutputTable: StateSet → 2outgoingMsgSet The output in the DEVS model is obtained by applying the XFD-DEVS output table to the phase component of the DEVS model state. The resulting value could be the empty set, in which case no output is emitted, a single value, or multiple values, in which case, a bag of values is constructed.

Note:  XFD-DEVS does not specify a unique DEVS since the confluent transition function is not specified.
Note: While the output of an XFD-DEVS can be a bag, the input is always a single element of the incomingMsgSet, not a bag

It is sometimes useful to retain the same time of next event even when a phase change is specified. To do this, an input may be distinguished as schedule preserving with the following effect on its DEVS.

Schedule preserving incoming message, Msg

δext: Q×X → S ,where                  

δext (phase,sigma,e,(inMsg,Msg)) =
(phase’, sigma – e)

where phase’ = ExternalTransitionTable(phase,Msg)
provided that ExternalTransitionTable(phase,Msg)
is defined. otherwise,

δext (phase,sigma,(inMsg,Msg)) =
(phase, sigma – e)

 When it is defined for a schedule preserving input, the ExternalTransitionTable in XFD-DEVS
determines an immediate transition to the phase of the next state in DEVS with the next transition scheduled at the original transition time.   Otherwise, it is interpreted in the DEVS model as an order to ignore the input and continue in the state to the original transition time.


Natural Language For XFD-DEVS

An alternative and complimentary way to build XFD-DEVS models is to provide a constrained natural language input that has the following statement forms:
to start hold in PHASE for time SIGMA !
hold in PHASE for time SIGMA !
after PHASE then output MSG !
from PHASE go to PHASE’ !
when in PHASE and receive MSG go to PHASE’ !

For convenience, some of these statements can be compounded as phrases in the following statements:
          hold in PHASE for time SIGMA then output MSG and go to PHASE' !
          hold in PHASE for time SIGMA then go to PHASE' !

The semantics of these statements is provided by the following table along with examples of how to use them.

Natural Language Phrase
  Description
Example
to start hold in PHASE for time SIGMA!

where SIGMA is 0, a positive real, or the symbol Infinity (other variants such as Inf are allowe 		 
to specify an initial state called PHASE
and remain in it for time SIGMA


 to stat hold in waitForJob for time Infinitiy!

This can also be expressed as: to start passivate in waitForJob!
hold in PHASE for time SIGMA

where SIGMA = 0, a positive real, or the symbol Infinity(other variants such as Inf are allowed)
 to specify a state and remain in it for time SIGMA
 hold in sendOut for time 0.1 !
after PHASE then output MSG!
 output a message ( named MSG) before transition from the current state PHASE
 after sendOut then output Job !
from PHASE go to PHASE'!
 specify an Internal Transition from Current state  (PHASE) to another PHASE'
 from sendOut go to waitForJob !
when in PHASE and receive MSG go to PHASE'!
 when in current state PHASE, and receive a message( MSG) , do an External Transition to
state PHASE'
 when in waitForJob and receive Job go to processing!
when in PHASE and receive MSG go to PHASE’ eventually ! As above but with a mark to note that this input is schedule-preserving in this state
 when in waitForJob and receive Job go to processing eventually !

The semantics of compound statements are composed of the semantics of the individual phrases


References:

1. Risco-Martin, J.L., Mittal, S., Zeigler, B.P., Cruz, J.L, "From UML Statecharts to DEVS State Machines using XML", Multi-paradigm Modeling, IEEE/ACM International Conference on Model Driven Engineering Languages and Systems, September 2007
2. Mittal, S., Ph. D. Dissertation: DEVS Unified Process for Integrated Development and Testing of Service Oriented Architectures
3. M.H. Hwang and B.P. Zeigler, ``Reachability Graph of Finite & Deterministic DEVS'', submitted to IEEE Transactions on Automation Science and Engineering
4. Mittal, S., Risco-Martin, J.L., Zeigler, B.P., "DEVS-Based Simulation Web Services for Net-centric T&E", Summer Computer Simulation Conference SCSC'07, July 2007


Following are the templates to construct atomic FD-DEVS models (Version 0.5):

Figure 1: GUI to generate DEVS models
Figure 2: Snapshot to consturct state-TimeAdvance pairs
Figure 3: Snapshot to construct internal behavior as Delta-int function
Figure 4: Snapshot to construct external input behavior as Delta-ext function
Figure 5: Snapshot showing generated XML XFD-DEVS model for 'proc'
Figure 6: Snapshot showing generated Java XFD-DEVS model for 'proc'

Coming soon:
Figure 7: Snapshot showing generation of coupled models from selected FD-DEVS XML models
Figure 8: Snapshot showing simulation using DEVSJAVA SimView viewer
Figure 9: Snapshot showing net-centric simulation using SOA/DEVS, a part of DUNIP process


Working With FDEVS GUI



Figure 1: GUI to generate DEVS models

Let’s construct a processor, called proc. First type “proc” into the ModelName field and hit the Create button. Then hit the Finite Sate Time Advance Functions button and fill in the table that opens up as in Figure 2. After hitting the Done button, you can go on to use the entries that you have inserted into the table as states (or phases)  in other tables.


Figure 2: Snapshot to consturct state-TimeAdvance pairs

You can define internal transitions for any of the defined states by hitting the Default Internal State Machine Specifications button, as shown in Figure 3.  The drop down menus display such states (that were defined in the Time Advance Table). Enter the transition from passive to passive first since this will make passive the initial state for the model – the state that it starts in.  In general, the startin state of the row in the table having the number 1 will be taken as the model’s initial state.



Figure 3: Snapshot to construct internal behavior as Delta-int function

Finally, Figure 4 shows how external input transitions are specified. You can enter an incoming message name and select a start state, an end state, and optionally, an output message for the end state. Note that you can also enter output messages for transitions in the internal transition table for any states not covered in the external transition table.  For example, when the model is in passive, an incoming job message will send it to processing where it will stay for the prescribed time and then output the job. You will have already  prescribed the residence  time the Time Advance table since the latter table  only include states in the drop down menus that have been entered in that table. The transition out of processing is prescribed in the internal transition table, e.g., processing to passive, and the output message after processing can be entered there as well, but both have to agree.



Figure 4: Snapshot to construct external input behavior as Delta-ext function

Figures 5 and 6 show the XML and Java codes that are generated when the Generate FDDevs button is pressed. The XML specification, proc.xml, corresponds to the formal specification of the model and contains  all the information you have entered in a form that is easily understood and processed. The Java model, proc.java, is ready to run in package Models.java within DEVSJAVA.



Figure 5: Snapshot showing generated XML FD-DEVS model for 'proc'


Figure 6: Snapshot showing generated Java FD-DEVS model for 'proc'