이산사건시스템 명세

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

역사

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

형식론

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

원소 모델

원소 DEVS 모델은 (1) 입력 사건에 의한 상태의 천이와 (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》 fir판. Springer. ISBN 978-0387975023.
[CK06] Francois E. Cellier and Ernesto Kofman (2006). 《Continuous System Simulation》 fir판. 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》 fir판. 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》: 219–230.
[ZKP00] Bernard Zeigler, Tag Gon Kim, Herbert Praehofer (2000). 《Theory of Modeling and Simulation》 seco판. Academic Press, New York. ISBN 978-0127784557. CS1 관리 - 여러 이름 (링크)

각주

↑ “보관된 사본”. 2010년 6월 25일에 원본 문서에서 보존된 문서. 2010년 4월 6일에 확인함.
↑ 오토마타는 지글러의 박사학위 논문에서 수학모델로 사용되었다.
↑ [Zeigler68]
↑ ^가 ^나 이때 출력 사건을 발생시킴
↑ [Zeigler76]
↑ 예를 들면,
$ta$ (공부)=50분, $ta$ (사망)= $\infty$
는 '공부'라는 상태는 50분 동안, '사망'이라는 상태는 무한히 오래 유지됨을 각각 표시한다.

[1] “보관된 사본”. 2010년 6월 25일에 원본 문서에서 보존된 문서. 2010년 4월 6일에 확인함.

[2] 오토마타는 지글러의 박사학위 논문에서 수학모델로 사용되었다.

[3] [Zeigler68]

[output-4] 가 ^나 이때 출력 사건을 발생시킴

[5] [Zeigler76]

[6] 예를 들면,
$ta$ (공부)=50분, $ta$ (사망)= $\infty$
는 '공부'라는 상태는 50분 동안, '사망'이라는 상태는 무한히 오래 유지됨을 각각 표시한다.

[1]

[2]

[3]

[4]

[5]

[6]