이산사건시스템 명세

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

이산사건 시스템 명세(Discrete Event System Specification, 이하 DEVS)는 애리조나 대학교의 교수인 버나드 P. 지글러(Bernard P. Zeigler)[1] 가 고안한 모형화를 위한 계층적 형식론(形式論, formalism)으로 사건(事件, event)의 발생에 따라 상태가 변하는 관점에서 시스템의 동적인 변화를 기술한다.

역사[편집]

DEVS 형식론은 지글러가 자신의 박사학위 논문을 작성하던 중 오토마타[2][3]에서부터 (1) 입력 사건에 의해서 상태가 천이(遷移, transition)되거나 (2) 시간의 흐름에 따라서 내부적으로 상태 천이[4]가 가능한 방법론을 고안하게 된다. 그는 1976년에 출간된 그의 첫 번째 저서인 Theory of Modeling and Simulation[5]에서 이러한 방법론을 미분방정식으로 표현되는 연속 시스템(continuous system)과 차분방정식(difference equation)으로 표현되는 이산시간시스템(discrete time system)과 비교하여 설명하였다.

형식론[편집]

DEVS는 수학적으로 크게 원소 모델과 연결 모델로 구성된다.

원소 모델[편집]

원소 DEVS 모델은 (1) 입력 사건에 의한 상태의 천이(遷移, transition)와 (2) 시간 진행에 따른 내부 상태의 천이[4]를 기술하기 위해서, 다음의 7개의 요소를 이용한다.

M = \, <X,Y,S,ta, \delta_{ext}, \delta_{int}, \lambda> \,

여기서

  • X 는 입력 사건 집합(set of input events)을 의미한다.
  • Y 는 출력 사건 집합(set of output events)을 의미한다.
  • S 는 상태 집합(set of states)을 의미한다.
  • ta:S \rightarrow \mathbb{R}_{[0,\infty]} 는 시간 전진 함수(time advance function)로서, 어떤 상태에 얼마나 머물 수 있는가를 기술하는 데 사용된다.[6]
    • 여기서 \mathbb{R}_{[0,\infty]}는 무한대(infinity)를 포함한 비음(non-negative)의 실수 집합을 의미한다.
  • \delta_{ext}:Q \times X \rightarrow  S 는 외부 상태 천이함수(external transition function)로서, 외부의 입력 사건이 원소 모델의 상태를 어떻게 변화시키는가를 기술하는 데 사용된다.
    • 여기서 Q=\{(s,t_e)|s \in S,  t_e \in ([0,\infty)\cap[0,ta(s)]) \}는 총 상태(total state) 집합을, t_e 는 최근 사건 발생 이후부터의 소요시간(elapsed time)을 각각 의미한다.
  • \delta_{int}:S \rightarrow S 는 내부 상태 천이함수(internal transition function)로서, 외부의 입력사건과 무관하게 소요시간이 현 상태의 수명(lifespan)에 도달 했을 때에 다음 상태로 바뀌는 현상을 기술하는 데 사용된다.
  • \lambda:S \rightarrow  Y 는 출력 함수(output function)로서, 내부상태 천이가 발생하는 시점에서 외부로 출력 사건을 발생하는 것을 기술하는 데 사용된다.

연결 모델[편집]

연결 DEVS 모델은 DEVS모델을 연결하여 커다란 시스템을 만들고, 또 그 시스템이 더 큰 시스템의 부품으로 사용될 수 있도록 하는 기능을 제공한다. 따라서 DEVS 형식론을 사용할 경우 모델을 부품화(部品化, modular)하고 계층적으로 개발할 수 있는 장점이다.

다음 8개의 요소로 정의된다.

 N = \, <X,Y,D,\{M_i\},C_{xx}, C_{yx}, C_{yy}, Select> \,

여기서

  • X 는 입력 사건 집합(set of input events)을 의미한다.
  • Y 는 출력 사건 집합(set of output events)을 의미한다.
  • D 는 구성 모델의 이름 집합(name set of sub-components)을 의미한다.
  • \{M_i\} 는 구성 모델 집합(set of sub-components)을 의미한다. 여기서, 한 i \in D에 대한 M_i는 원소 DEVS 모델이거나 연결 DEVS 모델이다.
  • C_{xx}\subseteq X \times \bigcup_{i \in D} X_i 은 입력 연결 집합(set of external input couplings)을 의미한다.
  • C_{yx}\subseteq \bigcup_{i \in D} Y_i \times \bigcup_{i \in D} X_i 은 내부 연결 집합(set of internal couplings)을 의미한다.
  • C_{yy}\subseteq \bigcup_{i \in D} Y_i \times Y 는 출력 연결 집합(set of external output couplings)을 의미한다.
  • Select:2^D \rightarrow D는 동률 해결 함수(tie-breaking function)로서, 구성 모델 중에 동일한 시점의 내부 상태 천이 일정을 갖는 복수의 모델이 존재할 때에 어떤 모델을 선택할지를 기술할 때에 사용된다.

참고 문헌[편집]

  • [Cellier91] Francois E. Cellier (1991). 《Continuous System Modeling》, first, Springer. ISBN 978-0387975023
  • [CK06] Francois E. Cellier and Ernesto Kofman (2006). 《Continuous System Simulation》, first, Springer. ISBN 978-0387261027
  • [Zeigler68] Bernard Zeigler (1968). 《On the Feedback Complexity of Automata》, Ph.D. Thesis, University of Michigan
  • [Zeigler76] Bernard Zeigler (1976). 《Theory of Modeling and Simulation》, first, Wiley Interscience, New York
  • [Zeigler84] Bernard Zeigler (1984). 《Multifacetted Modeling and Discrete Event Simulation》. Academic Press, London; Orlando. ISBN 978-0127784502
  • [Zeigler87] Bernard Zeigler (1987년). Hierarchical, modular discrete-event modelling in an object-oriented environment. 《SIMULATION》.
  • [ZKP00] Bernard Zeigler, Tag Gon Kim, Herbert Praehofer (2000). 《Theory of Modeling and Simulation》, second, Academic Press, New York. ISBN 978-0127784557

주석[편집]

  1. http://www.acims.arizona.edu/MEMBERS/bio/BPZWebBio.htm
  2. 오토마타는 지글러의 박사학위 논문에서 수학모델로 사용되었다.
  3. [Zeigler68]
  4. 이때 출력 사건을 발생시킴
  5. [Zeigler76]
  6. 예를 들면,
    ta(공부)=50분, ta(사망)=\infty
    는 '공부'라는 상태는 50분 동안, '사망'이라는 상태는 무한히 오래 유지됨을 각각 표시한다.