Advanced
A Study on Time Synchronization for Programmable Electronic Systems of Train Control
A Study on Time Synchronization for Programmable Electronic Systems of Train Control
The Transactions of The Korean Institute of Electrical Engineers. 2014. Jul, 63(7): 1019-1023
Copyright © 2014, The Korean Institute of Electrical Engineers
  • Received : June 09, 2014
  • Accepted : June 23, 2014
  • Published : July 01, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Article
Author
Metrics
Cited by
TagCloud
About the Authors
신주 강
Dept. of Railway Electrical and Signalling, Seoul National University of Science and Technology, Korea
종우 이
Corresponding Author : Dept. of Railway Electrical and Signalling, Seoul National University of Science and Technology, Korea E-mail :saganlee@seoultech.ac.kr

Abstract
The issue of safety insurance in PES(Programmable Electronic Systems) has been provoked because PES is difficult to define failure modes which are appeared in many different ways. But the PES applications extend rapidly in various areas. One of the solutions for PES safety insurance is voting which PES is used by comparing the outputs of several PES. The time synchronization of the PES is necessary for this reliable voting. The voting must be carried out with the outputs from same time inputs. There are several methods for time synchronization of the PES. In this paper, we discussed two modes of the time synchronization which are mutual synchronization of several PES and using UTC(Universal Time Clock).
Keywords
1. 서 론
현재 시스템 안전과 관련된 핵심 기능에 대한 PES(Programmable Electronic System) 적용이 급속히 확대되고 있다. 하지만 PES는 마이크로일렉트로닉스와 소프트웨어가 결합되어 그 특성상 결함에 의한 고장 특성을 예측하기가 매우 어렵다. 이러한 고장 특성을 극복하기 위해 다중화 시스템을 이용하여, 다수결에 의한 시스템의 안전성을 확보한다. PES의 다중화에는 시간 동기화가 필요하며, 이를 위해서 여러 가지 방법이 제시되었다. 프로세서 간의 시간 동기화는 PES 외부에서 시간을 제공하는 방법과 PES의 자체 시간을 이용하는 방법이 있다 [1] [2] [3] [4] .
표준 시간과의 정확한 동기화가 필요한 시스템으로는 증권 거래 시스템, 발권 시스템, 경매 시스템 등이 있다. 이 시스템들은 정확한 시간을 기준으로 동작한다. 외부 시간과 동기화해야 하는 시스템은 허용된 시간의 오차를 유지하기위해서 정확한 시간의 제공과 그 주기를 결정하는 것이 필요하다. 이러한 시스템에서의 동기화는 UTC(Universal Time Clock)와 같이 정밀한 시계를 이용하여 정확한 시간을 각 프로세서에 제공하는 방법을 이용한다 [5] [6] .
독립된 망으로 구성되어 있는 분산형 시스템은 내부적으로 시간 동기화가 되어있으면, 외부 시간과 정확하게 일치하지 않아도 주어진 임무를 수행할 수 있다. 분산형 시스템의 동기화는 내부를 구성하고 있는 프로세서의 구성과 상태에따라 달라진다. 프로세서가 동기화되었다는 것은 각 프로세서 시간의 오차가 허용범위 ρ 내에서 유지된다는 것을 의미한다. 이와 다르게 UTC와 시간이 일치하지는 않지만, 프로세스의 자체 시간을 상대 시간으로 정하여 동기화하는 방법이 있다 [1] [3] [4] [7] [8] .
대부분의 분산형 시스템은 일치된 시간 기준이 필요하다. 각 노드마다 하나의 시간이 제공되고, 일정 주기로 동기화를 하는 방법으로 시간 기준은 여러 시계에 의해서 생성된다. 시스템의 동작 오류를 발생시킬 수 있는 시간 오차가 발생하지 않도록 동기화된 시간을 분산형 시스템에 사용한다. 안전 관련 시스템에서는 동기화된 시간은 대부분의 결함허용 동작에서 필요하다 [6] .
2절에서는 다중 PES 시스템의 시간 동기화 에 대한 정의 및 일반적인 방법을 제시하였으며, 3절에서는 시간 보정 값을 구하는 방법 그리고 동기화된 시간과 UTC의 오차 및 영향을 제시하였으며, 5절에서는 결론을 도출하였다.
2. 다중 PES 시간 동기화
- 2.1 시간 동기화 정의
프로세서 p 의 시간 cp ( t )와 프로세서 q 의 시간 cq ( t )가 동기화가 되었다는 것은 임의의 절대 시간 t 에서 각 프로세서의 시간차가 식 (1)과 같이 허용범위 ρ 내에 있다는 것을 의미한다 [5] .
PPT Slide
Lager Image
분산형 시스템의 각 프로세서 시간 ci ( t )가 동기화되어도 시간이 경과함에 따라 그 오차가 증가하게 되며, 오차의 크기는 각 프로세서의 시간마다 다르며, 이후 이 오차로 인해 프로세서 간의 동기화를 벗어나게 된다. 시간 오차가 허용범위 내에 있다는 것은 동기화를 이용한 분산형 시스템의 임무에는 영향을 미치지 않는 것을 의미한다. 분산형 시스템의 시간 동기화를 위해서 다음과 같은 정의들이 필요하다.
ε i 를 프로세서 i 의 시간 편차율이라 할 때, 시간 Δ t 가 경과한 후에 프로세서 i 의 시간 ci ( t 2 )는 식 (2)와 같다.
PPT Slide
Lager Image
프로세서 i 의 시간 정밀도는 다음과 같이 나타낼 수 있다.
PPT Slide
Lager Image
허용오차 ρ 와 시간 편차율의 관계는 동기화 주기Δ t t = t r+1 t r 결정에 사용할 수 있다. 동기화 주기 Δ t 는 오차율을 고려한 이 허용오차 내 ε • Δ t 에서 이루어 져야 한다. 허용오차를 벗어나면 즉, r < ρ < ε • Δ t 이면 분산형 시스템이 동기화되었다고 할 수 없다. 따라서 ε i 의 값이 작으면 작을수록 시계의 정밀도는 높아지고, 동기화 주기Δ t 는 길어지게 된다. 분산형 시스템에서는 모든 프로세서가 동시에 시간 동기화하기 위해서 주기적인 명령을 발생시켜야 한다. 프로세서의 시간을 조정하기 위해서 각각 프로세서의 시간을 제공한다. 제공된 값을 기준으로 각각의 허용오차를 갖도록 하면, 그 값은 식 (1)을 만족해야 한다 [5] .
2.2 N 분산형 시스템 시간 동기화
N 개의 노드를 갖는 시스템에서 시간 동기화를 고려할 수있다. 프로세서의 시간 흐름에 따라 프로세서 p 의 시간 cp ( tr )은 각각 다른 시간 편차율 ε p 에 의해서 다른 프로세서의 시간 ci ( tr )( i p )와 차이가 난다. 보정된 프로세서 시간 ĉp ( tr )은 cp ( tr )에 보정 시간 ap ( tr )을 더함으로써 다음과 같이 얻는다.
PPT Slide
Lager Image
적정한 보정 시간에 의해서 프로세서들의 시간을 동기화할 수 있으며, 최적의 보정 시간 ap ( tr )을 구하는 것이 필요하다. 일정 시간이 지난 후에 프로세서의 시간은 시계의 동작 오차에 의해서 각각 다르게 된다. N 개의 프로세서의 시간차는 다음과 같이 정의된다. δ i,j r 번째 동기화 주기에서 프로세서 i 와 프로세서 j 의 시간차를 나타낸다.
PPT Slide
Lager Image
각 프로세서에 대한 시간차는 식 (6)과 같이 나타낼 수 있다.
PPT Slide
Lager Image
이를 통해서 프로세서 p 의 시간을 보정할 수 있다.
PPT Slide
Lager Image
보정된 프로세서 시간은 전체 시간의 평균과 같으며, 모든 프로세서의 시간이 동기화된다. 현재 시간에 보정 값을 감함으로써 시간 보정이 가능하다. 또한 모든 프로세서에 평균값을 적용하는 것과 동일하다.
평균값으로 동기화를 하는 경우는 절대시간 tr 과 일치하지 않을 수 있으며, 이 tr δ i,j 의 분포에 따라 달라진다. 어떤 프로세서 시계의 고장이 발생하였을 경우,
PPT Slide
Lager Image
가 고장난 프로세서 시계의 시간차 값에 의해서 좌우된다. 프로세서의 시간은 빠르거나 혹은 느린 특성을 있으므로 δ i,j 는 양 혹은 음의 값을 갖게 된다. 프로세서의 시간들이 tr 을 기준으로 좌우에 분포되면 보정된 시간
PPT Slide
Lager Image
tr 에 근접하게 된다. 그러나 시스템 고장 발생으로 특정 δ i,j 가 너무 크게 되어 결정 변수가 된다면,
PPT Slide
Lager Image
tr 에 근접할 수 없게 된다. 이렇게 고장 난 프로세서의 δ i,j 를 보정 값 ap ( tr ) 계산에서 제외하는 방법이 있다. ap ( t )를 계산하는 방법에는 여러 가지 방법이 제안되어 있으며, 3장에서는 그 방법들을 논한다.
2.3 동기화 시간
PPT Slide
Lager Image
과 절대시간 t 의 관계
프로세서의 각각 다른 ci ( tr )은 ( tr t 0 ) ε i 의 시간 편차율에 의해서 발생하며, 각각의 시계 오차에 의해서 동기화를 수행한다. 동기화를 수행하여 프로세서 간의 시간차를 허용범위내로 정한다. 프로세서 i 에서 t 0 는 절대시간과 동기화된 시간이고, tr 만큼 시간이 경과하였을 때 시간 ci ( tr )은 다음과 같다.
PPT Slide
Lager Image
식 (7)을 이용하면 ĉ ( t )는 다음과 같다.
PPT Slide
Lager Image
따라서 동기화된 시간과 절대시간의 차이 δ t ( t )는 다음과 같다.
PPT Slide
Lager Image
동기화된 시간과 절대시간의 차이는 전체 시간 오차율의 평균과 같다. 평균 오차율이 작을 경우, 절대시간과 차이가 작아진다.
3. 동기화를 위한 보정 값 계산
앞 절에서는 시간을 보정하는 방법으로 평균값을 이용했지만, 프로세서 시계의 고장이 발생한 경우도 있을 수 있다. 그러한 경우는 동기화된 시간과 절대시간의 차이가 크게 된다. 이를 피하기 위해서 여러 가지 알고리즘이 제시되었다 [6] [9] [10] [11] [12] [13] .
먼저, 다음의 조건을 만족하면 프로세서 i 는 고장이 발생한 것이다.
PPT Slide
Lager Image
- 3.1 다양한 보정 값 알고리즘
평균값 알고리즘은 모든 프로세서 시간의 평균값을 식(12)의
PPT Slide
Lager Image
로 설정하는 방법이다. 프로세서 p 가 시간을 동기화시키기 위해서 다른 프로세서와의 시간차 평균값
PPT Slide
Lager Image
로 보정하는 방법이다. 이 방법은 프로세서의 고장과 상관없이 각 프로세서 평균 시간으로
PPT Slide
Lager Image
을 설정하는 것이다.
PPT Slide
Lager Image
PPT Slide
Lager Image
값은 식 (13)과 같이 된다.
PPT Slide
Lager Image
수정 평균값 알고리즘은 프로세서의 시간 중에 고장 난 프로세서 k 개를 제외한 후에 평균값을 식 (14)의
PPT Slide
Lager Image
로 설정하는 방법이다. 이 방법은 프로세서의 고장과 상관없이 각 프로세서가 시간을
PPT Slide
Lager Image
)로 설정하는 것이다.
PPT Slide
Lager Image
결함허용 중간값 알고리즘은 δ i,j 의 값들 중에서 최대값 k 개와 최소값 k 개를 제외한 값 중에서 중간 값을
PPT Slide
Lager Image
로 선택한다.
PPT Slide
Lager Image
)는 식 (16)과 같이 된다.
PPT Slide
Lager Image
PPT Slide
Lager Image
결함허용 평균값 알고리즘은
PPT Slide
Lager Image
의 값들 중에서 최대값 k 개와 최소값 k 개를 제외한 값 중에서 평균값을
PPT Slide
Lager Image
로 선택한다.
PPT Slide
Lager Image
PPT Slide
Lager Image
프로세서의 시간 중 고장이 발생한 프로세서 k 를 제외한후에 평균값을 다음과 같이
PPT Slide
Lager Image
)로 설정하는 방법이다. 고장이 발생한 프로세서에서 이 방법은 프로세서의 고장과 관련없이 각 프로세서가 시간을
PPT Slide
Lager Image
)로 설정하는 것이다.
PPT Slide
Lager Image
- 3.2 알고리즘 별 시간오차
시간 보정 후, 프로세서 간에 시간은 동기화 되었다. 그러나 절대시간 t 와의 차이가 존재한다. 보정된 시간의 오차를 정의하기 위해서 연산자
PPT Slide
Lager Image
PPT Slide
Lager Image
를 정의한다. 연산자
PPT Slide
Lager Image
은 식 (20)과 같이 ε i 를 절대값으로 변환하고, 올림차순 j 를 갖는다. 연산자
PPT Slide
Lager Image
는 식 (21)과 같이 연산자
PPT Slide
Lager Image
의 역 변환이다.
PPT Slide
Lager Image
PPT Slide
Lager Image
연산자 ℕ는 식 (22)과 같이 ε i 을 올림차순으로 정리한 것이며 j 를 갖는다. 연산자
PPT Slide
Lager Image
PPT Slide
Lager Image
ε i 값으로 변환한 값이다.
PPT Slide
Lager Image
PPT Slide
Lager Image
식 (8)은 각 프로세서의 시간을 나타낸다. 평균값 알고리즘에서 이 시간의 평균값으로 보정 시간을 설정할 경우 편차와 절대시간은 다음과 같다.
PPT Slide
Lager Image
수정 평균값 알고리즘은 프로세서 k 개 고장이 발생하였을 경우이다.
PPT Slide
Lager Image
결함허용 중간값 알고리즘은 시간 편차율의 중간값을 취한다.
PPT Slide
Lager Image
결함허용 평균값 알고리즘은 고장이 발생한 k 개의 프로세서를 고려하고, 상하 k 의 프로세서 시간을 제외한 평균값을 취한다.
PPT Slide
Lager Image
- 3.3 상대시간 및 절대시간 오차
동기화는 상대시간을 허용 오차이내로 시간을 재설정한다. 동기화는 제어시스템에서 동일한 시간에 동일한 입력과 출력을 내기 위해 사용된다. 외부와 독립된 시스템은 내부 동기화에 의해서 입출력 값을 비교해도 상관없다. 그러나 철도 제어 시스템은 독립적으로도 동작이 되어야하며, 또한 절대시간과의 동기화가 필요하다. 3절에서는 동기화 방법과 절대시간과의 오차를 나타내었는데, 절대시간과의 오차는 동기화 시간과는 다른 특성을 가지며, 시간 오차 ε 에 따라 절대시간과의 편차가 달라진다. 3.2절에서 나타낸 것처럼 프로세서의 시계가 지상과 진상이 똑같이 분포되어 있는 경우 절대시간 t 와 프로세서 시간 c ( t )와 차이는 없다. 4절에서는 간단한 예시를 통하여 고장 난 프로세서와 시간 오차의 영향을 도식적으로 규명하기 위해 시뮬레이션을 수행하였다.
4. 시뮬레이션
시간 동기화를 위해서 시뮬링크를 이용하였다. 4개의 프로세서와 이를 연결하는 LAN으로 구성되어 있다. 프로세서시간을 생성하기 위해 클럭 생성기를 사용하였으며, 각각의 프로세서마다 시간 오차를 갖도록 각각 클럭을 사용하였다. 3개의 프로세서는 시간 동기화를 하는 프로세서이며, 나머지 1개의 프로세서는 표준 시각을 생성하기 위해 사용하였다. 프로세서 간의 시간을 전송하기 위해서 LAN을 이용하였다. 각 프로세서에서 시간이 생성되면 LAN을 통하여 다른 프로세서에 전송한다. 시뮬링크의 S-function을 이용하여 LAN을 만들고, 이를 통해 전달된 다른 프로세서의 시간정보를 이용하여 시간을 동기화 한다. 본 논문에서 LAN에서의 지연시간은 고려하였지만, 통신 지연시간은 무시를 하였다. 통신지연 시간을 시스템 구성에 따라 달라질 수 있다.
그림 1 의 순서대로 펄스주기는 임의로 각각 0.022초, 0.021초, 0.018초 및 0.02초로 하였다. 시간이 빠른 프로세서는 0.02초 보다 작게 하였으며, 느린 프로세서는 그보다 크게 하였다. 주기 0.02초는 표준시간 즉, UTC라고 가정하였다. 3개의 프로세서가 시간 동기화를 실행하지만, UTC와의 오차가 발생 한다. 이 차이를 비교하기 위해서 UTC 시간을 사용하였다.
PPT Slide
Lager Image
3개 프로세서를 이용한 시간동기화 모델 Fig. 1 Time synchronization model for 3 processors
각 프로세서간의 시간차는 각 프로세서 시계의 편류 오류에 의해 발생된다. 시간 편차율 ε 은 작을수록 절대시간에 가깝다. 그러나 시간 편차율 εi 이 작아도, 다른 프로세서들의 시간 편차율이 크고 상대 시간 편차율 차가 작으면, εi 를 고장난 프로세서로 간주할 수 있다.
시간 동기화는 상대시간 오차를 최소화하는 것이다. 시간 동기화의 주기를 짧게 하면 프로세서 간의 시각차가 작아지지만, 반면에 프로세서의 부하로서 작용되어, 작업처리 시간이 길어질 수 있다. 시간을 동기화하기 위한 변수는 동기화 주기 Δ t 는 30 pulse ×( pulse periodsec )/ pulse 로 하였다. 각 프로세서의 주기가 다르기 때문에 각각의 프로세서는 동기화 시간이 조금씩 달라진다. 동기화된 시간은 식 (13)을 이용하는 3개 프로세서 시간의 평균으로 정하였다. 그림 2 는 peusdo 10초 동안 진행된 UTC와 시간 차이에서 peusdo 5~10초 기간을 나타낸 것이며, 가로축은 sec, 세로축은 50pulse/sec 이다. 동기화 되었을 때는 시간 값 도약이 발생한다. 동기화된 시간이 정확하게 일치하지 않는 것은 LAN 특성에서 기인된것이다
PPT Slide
Lager Image
3개 프로세서의 시간 동기화 Fig. 2 Time synchronization of 3 processors
그림 4 는 pseudo UTC와 프로세서 간의 시간차를 나타낸것이다. 세로축은 펄스주기이며 0.02를 곱하여 초로 환산할수 있다. 프로세서 1과 2는 pseudo UTC 보다 시간이 느리므로 하향 시간 값으로 나타나며, 프로세서 3은 pseudo UTC 보다 빠르므로 상향 시간값으로 나타난다. 시간 동기화는 프로세서 1과 2는 상향으로 도약을 하며, 프로세서 3은 하향으로 도약을 하게 된다. 그림 4 의 7.12초 경의 도약은 프로세서의 시각이 pseudo UTC와 일정 오차가 발생한다고 가정하여 pseudo UTC와 동기화한 것이다.
PPT Slide
Lager Image
pseudo 10초 동안 수행된 시간동기화 Fig. 4 Time synchronization for pseudo 10seconds
위에서 제시된 알고리즘들은 시간 동기화에 모두 사용할수 있다. 단지 응용분야에 따라서 동기화 허용오차 ρ 와 UTC의 허용오차가 다르게 설정되기 때문에, 응용분야에 따라 동기화 방법을 달리할 수 있다.
5. 결 론
본 논문에서는 다중계 PES 시스템에서 시간 동기화 알고리즘과 그 알고리즘의 구현을 증명하기 위해 시뮬레이션 도구로 시뮬링크를 이용하여 개발하였으며, 제시된 알고리즘과 시뮬레이션의 동작을 확인하였다.
시간 동기화는 응용 분야에 따라 허용오차 ρ 가 설정되며, ρ 를 만족하기 위해서 LAN 혹은 프로세서 간의 직접연결등 동기화 기법을 달리 해야 한다. 부분적으로 프로세서 간의 동기화가 되었다하더라도 UTC와 허용오차 내에 있어야 하는 경우도 있다. 응용분야에 따라서, 내부적인 프로세서간에 허용오차 ρ 를 만족하기 위해서 일정한 주기 Δ t 에 동기화를 수행하여야 하며, 허용오차 ρ 와 동기화 주기 Δ t 는 설정된다. CSMA/CD를 사용하는 LAN을 사용할 경우에는 MAC에 의해서 일정한 지연시간을 산정하기가 어렵다. LAN을 사용할 경우에는 별도로 지연시간을 예측하는 알고리즘을 개발할 필요가 있다.
UTC와 동기화가 필요한 경우에는 각각의 프로세서에서 별도의 시스템으로부터 UTC 시간을 수신하고, 각 프로세서는 수신된 시간이 일치하는가는 비교하여야 한다. 이 경우는 UTC와의 허용오차 ρ ′와 동기화 주기 Δ t ′를 설정하여, 동기화를 위한 별도의 시스템을 구성하여야 한다.
Acknowledgements
본 연구는 2014년도 서울과학기술대학교 산학협력단의 지원에 의하여 이루어진 “ 열차제어 장치용 실시간 시스템의 시간 동기화에 관한 연구” 에 대한 연구로서, 관계부처에 감사드립니다.
BIO
강 신 주 (姜 信 柱)
2008년 서울과학기술대학교 석사졸업, 2005년~현재 (주)혁신전공사 이사, 2008 년~현재 서울과학기술대학교 박사과정
이 종 우 (李 鍾 宇)
1983년 한양대학교 기계설계공학과 학사 졸업, 1986년 Ecole Centrale de Nantes 석사졸업, 1993년 University of Paris VI 박사졸업, 2005년~현재 서울과학기술대 학교 철도전기신호공학과 교수
References
Azevedo Marcelo M. , Blough Douglas M. 1994 “Software Based Fault Tolerant Clock Synchronization for Distributed UNIX Environments” from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.30.7563&rep=rep1&type=pdf
Welch Jennifer L. , Lynch Nancy A. 1988 “A New Fault tolerant Algorithm for Clock Synchronization” Information and Computation 77 (1) 1 - 36    DOI : 10.1016/0890-5401(88)90043-0
Dolev D. , Lynch Nancy A. , Pinter Shlomit S. , Stark Eugene W. , Weihl William E. 1986 “Reaching Approximate Agreement in the Presence of Faults” Journal of the ACM 33 (3) 499 - 516    DOI : 10.1145/5925.5931
Kopetz H. , Ochsenreiter W. 1987 “Clock Synchronization in Distributed Real-Time Systems” IEEE 36 (8) 933 - 940
Lui E. J. , Martin J. M. 1994 “A Convergence Function for Clock Synchronization Protocols” IEEE 9 - 16
Mahaney Stephen R. , Schneider Fred B. 2001 “Inexact Agreement: Accuracy, Precision, and Graceful Degradation” 239 - 249
Kopetz H. , Damm A. , Koza C. , Mulazzani M. , Schwabl W. , Senft C. , Zainlinger R. 1989 "Distributed Fault tolerant Real-time Systems the Mars Approach" IEEE Micro 9 (1) 25 - 40    DOI : 10.1109/40.16792
Lonn H. 1999 "A Fault Tolerant Clock Synchronization Algorithm for Systems with Low-Precision Oscillators" Springer Verlag Berlin Heidelberg 1667 88 - 105
Shin Kang G. , Butler Ricky W. , Ramanathan P. 1990 "Fault-tolerant Clock Synchronization in Distributed Systems " IEEE 23 33 - 42
Lundelius J. , A Lynch Nancy. 1984 "A New Fault tolerant Algorithm for Clock Synchronization" Proceedings of the third annual ACM symposium on Principles of distributed computing (3) 75 - 88
Lamport L. , Melliar Smith P. M. 1985 "Synchronizing Clocks in the Presence of Faults" the Association for Computing Machinery 32 (1) 52 - 78    DOI : 10.1145/2455.2457
Malekpour Mahyar R. 2006 "A Byzantine-Fault Tolerant Self-stabilizing Protocol for Distributed Clock Synchronization Systems" Lecture Notes in Computer Science (4280) 411 - 427
Halpern Joseph Y. , Simons B. , Strong R. , Dolev D. 1984 "Fault-Tolerant Clock Synchronization" Proceedings of the third annual ACM symposium on Principles of distributed computing 89 - 102