The Journal of Korean Institute of Electromagnetic Engineering and Science
The Korean Institute of Electromagnetic Engineering and Science
단편논문/SHORT PAPER

우선순위 큐를 이용한 함정용 다기능 레이다의 빔 스케줄링 기법

박지웅1,https://orcid.org/0000-0003-0329-1475, 양우용*https://orcid.org/0000-0001-8539-2506, 신상진*https://orcid.org/0000-0001-6329-9917, 전주환1https://orcid.org/0000-0002-3506-1722
Jiung Park1,https://orcid.org/0000-0003-0329-1475, Wooyong Yang*https://orcid.org/0000-0001-8539-2506, Sangjin Shin*https://orcid.org/0000-0001-6329-9917, Joohwan Chun1https://orcid.org/0000-0002-3506-1722
1한국과학기술원 전기 및 전자공학부
*한화시스템
1Department of Electrical Engineering, Korea Advanced Institute of Science and Technology
*Hanwha Systems
Corresponding Author: Jiung Park (e-mail: jiung@kaist.ac.kr)

© Copyright 2019 The Korean Institute of Electromagnetic Engineering and Science. This is an Open-Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/4.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Received: Nov 20, 2019; Revised: Jan 13, 2020; Accepted: Jan 31, 2020

Published Online: Feb 29, 2020

요약

본 논문에서는 우선순위 큐를 이용한 다기능 레이다의 빔 스케줄링 기법을 제안하였다. 제안된 기법은 방사될 시점을 우선순위로 하는 우선순위 큐를 사용하여 미래에 방사될 레이다 빔을 고려하여 스케줄링하도록 하였으며, 정밀 추적 임무, 일반 추적 임무, 탐색 임무 각각의 우선순위 큐가 임무의 중요도를 고려하여 레이다 타임라인에 빔을 배치함으로써 효율적인 빔 스케줄링이 가능하도록 하였다. 검증 과정에서는 마르코프 체인을 이용하여 실제 해상 전투상황과 유사한 시뮬레이션 환경을 구현하였으며, 기존의 빔 스케줄링 기법과 비교했을 때 지연시간의 총 가중합을 극소화하면서 그 효율성을 확인하였다.

Abstract

In this paper, a beam scheduling method for analyzing shipborne multifunction radars using priority queues is presented. The proposed method uses priority queues that use the beam’s emission time as a priority. The priority queues for each of precision tracking, normal tracking, and search consider the significance of the task in performing efficient beam scheduling. We adopted a simulation environment similar to an actual maritime combat situation using a Markov chain. The efficiency of the proposed method is verified via comparison with other beam scheduling methods, and the total weighted tardiness is minimized.

Keywords: Radar Beam Scheduling; Priority Queue; Shipborne Multi-Function Radar

Ⅰ. 서 론

레이다를 전자적으로 조향할 수 있는 기술이 개발됨에 따라 여러 임무를 동시에 수행할 수 있게 되었고, 한정된 레이다 자원을 효율적으로 분배할 수 있도록 하는 레이다 자원관리에 관한 연구의 중요성이 크게 대두되었다.

특히, 레이다가 여러 임무를 동시에 효율적으로 수행하기 위해서는 임무의 중요도, 갱신주기에 따라 방사될 빔을 스케줄링하는 과정이 필요하다. 이와 관련해 시간 균형(time balance) 개념을 이용하여 스케줄링하는 방법[1], 일반 추적 큐의 길이를 조절하여 정밀 추적 빔의 갱신주기를 보장하는 스케줄링 방법[2] 그리고 주로 산업공학 분야에서 사용하는 작업 단위 스케줄링(job shop scheduling)을 레이다 스케줄링에 접목한 방법[3] 등이 연구되기도 하였다.

실제 운용되는 함정용 다기능 레이다에서는 표적을 추적하거나 표적을 격추하기 위해 발사된 미사일을 추적하는 등 정밀 추적 임무의 목적이 각기 다르므로 임무의 갱신율이 다른 점을 고려해야 한다. 또한, 실제 교전 상황을 가정했을 때, 일반 추적보다는 위협요소가 큰 표적에 대한 정밀 추적을 먼저 처리해야 하는 것이 매우 중요하다. 본 논문에서는 이와 같은 필요조건들을 충족할 수 있도록 우선순위 큐를 이용해 가까운 미래에 방사될 빔을 고려하였으며, 임무의 중요도를 잘 반영할 수 있도록 알고리즘을 설계하였다. 또한, 마르코프 체인을 이용해 시뮬레이션을 구현하였고, 시뮬레이션을 통해 제안한 기법이 지연시간의 총 가중합을 극소화함으로써 효율적으로 빔 스케줄링함을 확인하였다.

Ⅱ. 빔 스케줄링 파라미터와 비용함수

제안하는 빔 스케줄링 기법에서 사용하는 파라미터는 다음과 같다. 아랫첨자 jj번째 임무를 의미하며, 빔 방사 시작 시간(rj: release time), 빔 방사 완료 시간(cj: completion time), 빔이 표적에 머무르는 시간(pj: dwell time)은 식 (1)과 같은 관계를 갖는다.

c j = r j + p j
(1)

빔 방사 완료 시간은 실제 빔 방사가 완료된 시간을 의미하지만, 빔의 방사가 완료되어야 할 시간(dj: Due date)은 이전에 실행된 빔이 완료된 시간(cj)과 임무에 따른 레이다 갱신율(uj: update rate)을 식 (2)를 이용하여 구할 수 있다.

d j = c j + 1 u j
(2)

빔의 방사가 완료되어야 할 시간에 맞춰 완료되는 것이 가장 이상적이지만, 그렇지 못한 경우 임무 지연시간(TDj: tardiness)이 식 (3)과 같이 발생할 수 있다.

T D j = max ( c j d j , 0 )
(3)

그림 1에서 Task 1은 빔의 방사가 완료되어야 하는 시간과 완료 시간이 같으므로 지연시간이 발생하지 않았고, Task 2의 경우, 빔의 방사가 완료되어야 할 시간보다 완료 시간이 더 늦어졌기 때문에 지연시간이 발생했음을 알 수 있다.

jkiees-31-2-200-g1
그림 1. | Fig. 1. 빔 스케줄링 파라미터 | Beam scheduling parameters.
Download Original Figure

알고리즘 검증을 위한 비용함수는 프레임 시간(frame time)과 지연시간의 총 가중 합(total weighted tardiness: TWT)을 사용하였다. 프레임 시간은 레이다 프레임 하나를 모두 탐색하는데 걸리는 시간이며, TWT는 발생한 모든 지연시간에 임무의 중요도(wj: weight)를 곱한 후 합한 것을 의미한다. TWT는 식 (4)와 같이 구할 수 있다. 임무의 중요도는 실제적인 전투상황에 따라 달라질 수 있지만, 일반적으로 우선순위 높은 임무가 더 큰 값을 갖도록 설정한다.

T W T = w j max ( c j d j , 0 )
(4)

Ⅲ. 우선순위 큐를 이용한 빔 스케줄링

우선순위 큐는 우선순위에 따라 데이터가 선출되는 순서가 달라지는 추상 자료형을 의미하며, 데이터를 삽입하거나 선출하는 과정에서 정렬을 수행하여 우선순위가 높은 데이터가 먼저 선출된다. 우선순위 큐는 힙이나 배열과 같은 자료구조를 통해 구현할 수 있다.

본 논문에서는 임무의 중요도를 정밀 추적, 일반 추적, 탐색으로 나누어 그림 2와 같이 총 세 개의 우선순위 큐가 존재하도록 스케줄러의 구조를 설계하였다. 스케줄러는 빔 방사 요청을 받으면 처리기를 통해 해당 빔을 중요도에 따라 우선순위 큐에 삽입하며, 결과적으로 레이다 타임라인에 빔이 배치함으로써 스케줄링을 수행하게 된다. 제안한 기법은 빔을 우선순위 큐에 삽입하는 과정과 우선순위 큐에 있는 빔을 선출하여 레이다 타임라인에 배치하는 두 단계로 나누어 설명될 수 있다.

jkiees-31-2-200-g2
그림 2. | Fig. 2. 빔 스케줄러 구조 | Structure of beam scheduler.
Download Original Figure

빔이 우선순위 큐에 삽입되는 과정은 다음과 같다. 어떠한 임무가 개시되면 첫 번째 빔을 우선순위 큐에 삽입하고, 그 빔이 방사되는 순간(rj) 그 다음 빔의 방사가 시작될 시간(rj)을 식 (5)와 같이 계산하여 삽입한다.

r j = r j + 1 u j
(5)

각각의 우선순위 큐 내부는 빔 방사 시작 시간이 이른 빔을 우선으로 정렬되도록 하여, 빔의 삽입 순서와는 무관하게 빔 방사 시작 시간을 기준으로 스케줄링되도록 한다.

빔을 우선순위 큐에 삽입한 후에는 우선순위 큐에서 빔을 선출하여 레이다 타임라인에 배치하는 과정이 수행된다. 이 단계에서는 임무의 중요도에 따른 파라미터를 구분하기 위해 기존 파라미터의 아랫첨자를 P 또는 N 또는 S로 변경하였으며, 각각의 첨자는 순서대로 정밀 추적, 일반 추적, 탐색을 나타낸다. 현재 시점에 레이다 타임라인이 비어 있다면, 정밀 추적 우선순위 큐, 일반 추적 우선순위 큐 그리고 탐색 우선순위 큐 순으로 큰 임무 중요도를 가지므로 정밀 추적 큐에 들어있는 빔을 먼저 꺼내어 빔 방사 시작 시간(rP)을 확인한다. rP가 현재 시간보다 같거나 작다면, 그 빔을 레이다 타임라인에 배치한다. 반면에 rP가 현재 시간보다 크다면, 꺼낸 빔을 다시 정밀 추적 우선순위 큐에 넣음으로써 빔이 rP보다 일찍 방사되지 않도록 한다. 정밀 추적 빔이 레이다 타임라인에 배치되지 않으면, 일반 추적 우선순위 큐에 들어있는 빔을 꺼내어 빔 방사 시작 시간(rN)을 확인한다. rN이 현재 시간보다 같거나 작고, 일반 추적 빔이 표적에 머무르는 시간(pN)과의 합(rN+pN)이 이전 단계에서 확인한 rP보다 작으면 그 빔을 레이다 타임라인에 배치한다. 정밀 추적 빔과는 다르게 일반 추적 빔은 그림 3과 같이 rNpN의 합이 rP를 침범하지 않도록 빔 방사가 제한됨을 알 수 있다. rN이 현재 시간보다 크거나, rN+pNrP와 같거나 크다면, 꺼낸 빔을 다시 일반 추적 큐에 넣는다. 비슷한 방법으로, 탐색 우선순위 큐에 들어있는 빔을 꺼내어 빔 방사 시작 시간(rS)을 확인한다. rS가 현재 시간보다 같거나 작고, 탐색 빔이 표적에 머무르는 시간(pS)과의 합(rS+pS)이 rP 그리고 rN보다 작을 경우 그 빔을 레이다 타임라인에 배치한다. 이러한 빔 스케줄링 방법은 임무 중요도가 낮은 빔에 의해 임무 중요도가 높은 빔의 지연시간이 발생하지 않도록 한다.

jkiees-31-2-200-g3
그림 3. | Fig. 3. 임무 중요도에 따른 빔 배치 방법 | Beam placement based on priority of a task.
Download Original Figure

Ⅳ. 시뮬레이션 결과

실제 전투상황에서는 탐색 빔에 의해 표적이 탐지되면 그 뒤로는 추적 빔을 방사하게 되고, 표적의 거동에 따라 정밀 추적 임무로 전환이 될 수도 있다. 시뮬레이션에서는 사용되는 레이다 프레임이 300개의 탐색 빔으로 이루어진 상황을 가정하였으며, 각각의 탐색 빔은 그림 4의 마르코프 체인을 따름을 가정한다. 탐색(search), 단거리 표적 추적(short range tracking), 장거리 표적 추적(long range tracking), 정밀 표적 추적(precision target tracking), 미사일 추적(missile tracking)이 상태(state)로서 존재하며, 한 상태에서 다른 상태로 전이가 가능한 경우 화살표로 방향을 나타내었고, 그 옆에 전이 확률을 표현하였다. 또한, 일반 추적 임무에서 정밀 추적 임무로 전환되면, 정밀 표적 추적과 미사일 추적이 함께 발동하도록 하였다. 본 논문의 비용함수인 프레임시간은 300개의 탐색 빔이 다 방사될 때까지의 시간을 측정하였으며, 정밀 추적 빔, 일반 추적 빔에 각각 0.7과 0.3의 중요도를 부여하여 TWT를 구하였다.

jkiees-31-2-200-g4
그림 4. | Fig. 4. 시뮬레이션에 적용된 마르코프 체인 | Simulation Markov chain.
Download Original Figure

비교를 위해 제안한 기법에서 미래에 배치될 빔을 고려하지 않고 빔 방사 시간이 빠른 것을 기준으로 탐욕 알고리즘을 구현하였으며, 기존에 연구된 작업 단위 스케줄링 기법 중 레이다 스케줄링에 가장 적합한 WMDD(weighted modified due date : WMDD) 기법[3]을 구현하여 비교하였다. 시뮬레이션은 각 알고리즘 당 30번씩 진행하고 프레임시간과 TWT의 평균값을 구하였다. 아래의 표 1은 시뮬레이션에 사용된 파라미터이다.

표 1. | Table 1. 시뮬레이션 파라미터 | Simulation parameters.
Task Dwell time(ms) Update rate(Hz) Maximum task number
Search 20 1
Short range tracking 3.2 0.8 100
Long range tracking 8.0 0.4 10
Precision target tracking 4.1 8 15
Missle tracking 5.0 10 15
Download Excel Table

시뮬레이션 결과인 그림 5를 보면, 제안된 알고리즘의 프레임시간이 10.561초 정도로 다른 알고리즘에 비해 약 3초 가량 증가하게 되었지만, TWT는 58.003으로 다른 알고리즘에 비해 매우 낮은 수치를 보인다. 일반적으로 해상전투상황에서는 새로운 표적을 탐색하는 임무보다 함정을 향해 날아오는 표적의 추적과 요격용 미사일 추적 임무가 더욱 높은 중요도를 가진다. 시뮬레이션 결과는 다기능 레이다의 빠른 탐색에 대한 지표인 프레임 시간이 증가했지만, 추적의 질을 나타내는 지표인 TWT가 대폭 감소하는 유의미한 결과를 나타낸다.

jkiees-31-2-200-g5
그림 5. | Fig. 5. 시뮬레이션 결과 | Simulation result.
Download Original Figure

Ⅴ. 결 론

제안한 알고리즘은 미래에 배치될 빔의 방사 시작 시간과 임무 중요도를 고려하여 스케줄링하였으며, 결과적으로 다른 알고리즘에 비해 프레임시간이 조금 증가하지만 TWT가 대폭 감소하여 효과적인 빔 스케줄링이 가능함을 보였다.

Acknowledgements

이 논문은 2018~2019 한화시스템(주)의 재원을 지원받아 수행된 연구임.

References

[1].

R. Reinoso-Rondinel, T. Y. Yu, and S. Torres, “Multifunction phased-array radar: Time balance scheduler for adaptive weather sensing,” Journal of Atmospheric and Oceanic Technology, vol. 27, no. 11, pp. 1854-1867, 2010.

[2].

A. G. Huizing, A. A. F. Bloemen, “An efficient scheduling algorithm for a multifunction radar,” in the Proceedings of International Symposium on Phased Array Systems and Technology, Boston, MA, pp. 359-364, 1996.

[3].

N. H. Jeong, S. H. Jin, J. H. Choi, C. H. Kim, and K. T. Kim, “Beam scheduling for shipborne multi-function radar based on job shop scheduling theory,” The Journal of Korean Institute of Electromagnetic Engineering and Science, vol. 30, no. 8, pp. 668-676, 2019.