CBF Computation Acceleration of CBFM Using k-Means Clustering Algorithm

Kim, In-Hwan; Im, Hyeong-Rae; Hong, Ic-Pyo; Kim, Young-Joo; Yook, Jong-Gwan

doi:10.5515/KJKIEES.2022.33.12.926

J. Korean Inst. Electromagn. Eng. Sci. 2022; 33(12):926-930

pISSN: 1226-3133, eISSN: 2288-226X

DOI: https://doi.org/10.5515/KJKIEES.2022.33.12.926

논문/REGULAR PAPERS

k-평균 클러스터링 알고리즘을 활용한 CBFM의 CBF 계산시간 가속화

김인환¹

, 임형래¹

, 홍익표^*

, 김영주^**

, 육종관¹^,^†

CBF Computation Acceleration of CBFM Using k-Means Clustering Algorithm

In-Hwan Kim¹

, Hyeong-Rae Im¹

, Ic-Pyo Hong^*

, Young-Joo Kim^**

, Jong-Gwan Yook¹^,^†

Author Information & Copyright ▼

¹연세대학교 전기전자공학과

^*공주대학교 정보통신공학부

^**국방과학연구소

¹Department of Electrical and Electronic Engineering, Yonsei University

^*Department of Information & Communication Engineering, Kongju National University

^**Agency of Defense Development

^†Corresponding Author: Jong-Gwan Yook (e-mail: jgyook@yonsei.ac.kr)

© Copyright 2022 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: Oct 05, 2022; Revised: Oct 13, 2022; Accepted: Dec 05, 2022

Published Online: Dec 31, 2022

요약

본 논문에서는 모멘트법을 기반으로 하는 대형 구조 해석 알고리즘 중 하나인 CBFM(characteristic basis function method)의 계산 시간 가속화를 위해 CBF(characteristic basis function) 계산을 위한 블록 생성에 클러스터링 알고리즘을 활용하였다. 해석 시간의 효율성을 위해 블록(block)별 메쉬 분포의 최적화는 필수적이며, 클러스터링을 통해 최적화된 블록을 생성하여, 이를 바탕으로 CBF를 계산하였다. 본 논문에서는 대표적인 클러스터링 기법인 k-평균 클러스터링 알고리즘을 활용하여 블록 최적화를 진행하였고, 그에 따른 계산 시간 감소를 확인하였다.

Abstract

This study utilized the clustering-based CBF(characteristic basis function) generation algorithm to reduce the computing time of CBFM(characteristic basis function method), which is an accelerated version of moment methods in electromagnetics. As an efficient optimization of block generation, the meshes are grouped using the clustering algorithm, resulting in a reduction in the CBF computing time. In this study, we optimized the mesh distribution using the K-means clustering algorithm and verified the performance of the clustering-based method.

Keywords: CBFM; Characteristic Basis Function; Clustering Algorithm; Mesh Grouping; Block

Ⅰ. 서 론

모멘트법(method of moments)은 맥스웰 방정식으로부터 유도된 표면 적분 방정식을 행렬화하여 전자기 문제를 해석하는 기법이다. 근래에는 모멘트법을 사용한 대형 구조 해석을 위해 다양한 가속화 기법들이 연구되고 있다.

가속화 알고리즘은 선형 행렬 방정식의 풀이 기반에 따라 FMM(fast multipole method), MLFMM(multi-level FMM)^[1]과 같은 반복 풀이법(iterative solver) 기반과 CBFM (characteristic basis function method)^[2]과 같은 직접 풀이법(direct solver) 기반의 두 가지 부류로 나뉜다. 직접 풀이법의 경우, 다양한 입사원에 대한 해석이 용이하고, 해석 구조의 성질에 따른 해의 수렴성 영향이 적기에 모노스태틱 RCS 해석과 같은 상황에 보다 큰 이점을 가진다.

대표적인 직접 풀이법 중 하나인 CBFM^[2]은 전체 해석 영역(domain)을 여러 부영역(subdomain)으로 나누어, 각 부영역별, CBF라 일컫는 MBF(macro basis function)를 계산하여 자유도(degrees of freedom)를 감소시키는 방법이다. 부영역별로 계산된 CB를 통해 축소 행렬(reduced matrix) 방정식을 구성하고 해를 구함으로써, 계산 시간 가속화와 메모리 자원 감소라는 이점을 지닌다.

계산 시간 가속화를 위해 여러 해석 영역을 어떻게 나누는지도 문제 해석에 있어 중요한 요소 중에 하나이며, 이를 위해 클러스터링을 활용하기 위한 연구가 활발히 진행되고 있다. 실제로, 전자기 해석 문제에서는 FMM, MLFMM과 같은 알고리즘에서 해의 수렴성 향상과 계산 자원 비용을 줄이기 위해서 k-평균 클러스터링 알고리즘이 사용되어 왔다^[3],[4].

CBFM도 마찬가지로 전체 해석 영역을 부영역으로 나누는 과정에서 영역별 메쉬 분포 및 블록 크기 최적화를 통해 계산 시간 감소 같은 큰 이점을 얻을 수 있다^[5]. 본 논문에서는 k-평균 클러스터링 기법을 활용하여 메쉬 분포 최적화를 통한 계산 시간 감소를 확인하고자 한다.

Ⅱ. CBFM 알고리즘 개요

2-1 부영역별 CBF 계산

CBFM에서는 전체 해석 영역을 약 0.5~2.0 λ의 크기를 가지는 정육면체 블록으로 전체 메쉬를 분할한다. 그리고, 연속성을 보장하기 위해, 정규 블록 외부에 추가적인 연장 영역을 구성하여 전체 부영역을 구성한다^[1]. 그 후, 각 부영역에 다양한 각도로 입사하는 평면파가 입사될 때의 전류 분포를 계산하여 CBF를 구성한다. 이를 식으로 표현하면, i번째 영역에 대해서 식 (1)과 같이 선형 행렬 방정식을 구성할 수 있다.

[Z] i [C B] i = [V]

(1)

이때, Z_i는 해당 영역의 RWG(Rao-Wilson-Glisson) 기저 함수를 통해 계산된 임피던스 행렬이며, V 행렬을 구성하는 각 열(column)들은 해당 영역에 다양한 방향으로부터 입사하는 여러 평면파들을 testing하여 벡터화한 것이다. 식 (1)의 해를 구해 해당 영역의 CBF를 계산할 수 있으며, CBF는 해당 영역에 존재할 수 있는 전류분포의 조합을 의미한다.

2-2 축소 행렬 시스템 구성

모든 부영역에 대한 CBF가 계산되고 나면, 축소 행렬을 식 (2)과 같이 구성할 수 있다.

[Z] m reduced = [C B] m T [V] m

(2)

이때, Z_mn은 m번째 부영역과 n번째 부영역 내에 존재하는 RWG 기저 함수들 간의 임피던스 행렬이다. 마찬가지로, 축소 벡터도 식 (3)와 같이 계산할 수 있다.

[V] m reduced = [C B] m T [V] m

(3)

이때, V_m은 m번째 부영역에서 excitation을 testing하여 계산된 벡터이다. 최종적으로, 식 (4)와 같이 축소 행렬 시스템을 구성할 수 있다. 이 행렬 시스템의 해를 구하여 RWG 기저 함수의 weighting값으로 변환하면 해석 결과를 도출할 수 있다.

[Z] reduced [I] reduced = [V] reduced

(4)

일반적으로, 축소 행렬의 크기는 통상적인 모멘트법을 사용하였을 때 행렬의 크기보다 작아지기 때문에 계산 시간 감소라는 이점을 얻을 수 있다.

Ⅲ. 클러스터링 기반 블록 생성 알고리즘

3-1 Cube 기반 블록 생성의 문제점

기존 CBFM에서 cube 기반으로 블록을 생성하는 기법은 해석 공간상에 격자 모양으로 여러 정육면체를 배치하고 메쉬를 각 정육면체 별로 분류해 부영역을 생성한다. 그림 1(a)와 cutted-cone 구조에 대해 cube 기반의 블록 생성을 진행하였다. 그림 2(a)를 보면, cube 기반으로 블록을 생성하였을 때, 블록별 메쉬 수가 매우 산발적으로 분포하는 것을 확인할 수 있다. 블록별 메쉬 수의 차이가 발생하면 CBF를 형성하기 위한 행렬 연산에서 계산 시간의 증가를 야기할 수 있다. 이러한 문제점을 개선하기 위해 본 논문에서는 클러스터링 알고리즘을 활용하고자 한다.

그림 1. | Fig. 1. Cutted-cone 구조의 블록 생성 모식도(각각 1,052개 블록). | Configuration of the block generation for the cutted cone (total 1,052 blocks in each case).

Download Original Figure

그림 2. | Fig. 2. Cutted-cone 구조에 대한 블록 내 메쉬 분포 히스토그램 | Mesh distribution histogram for the cutted cone.

Download Original Figure

3-2 k-평균 클러스터링을 활용한 영역 생성

k-평균 클러스터링 알고리즘은 주어진 데이터들을 k개의 클러스터로 그룹화하는 알고리즘으로서, 각 클러스터의 중심점으로부터 데이터까지의 분산을 최소화하는 방식으로 구현된다. 다시 말해, n개의 데이터 (x₁, x₂,···,x_n)가 주어졌을 때, k(≤n)개의 집합 S₁,S₂,···,S_k으로 그룹화를 진행하여, 식 (5)의 값을 최소화하도록 각 데이터들을 그룹화하는 것을 의미한다.

arg min S ∑ i = 1 k ∑ x ∈ S i ‖ x − μ i ‖ 2

(5)

해당 클러스터링 알고리즘을 이용하여 그림 1(b)와 같이 동일한 구조에 대해 블록 생성을 수행하였고, 그림 2(b)와 표 1을 보면, 기존보다 비교적 더 고른 분포를 가지는 것을 확인할 수 있다. 동일한 수의 블록이 생성되었을 때, 클러스터링 기반 메쉬 분포의 표준편차가 11.1로 cube 기반의 17.9보다 더 낮은 것을 확인할 수 있다.

표 1. | Table 1. Cutted-cone 구조에 대한 cube 및 k-평균 클러스터링 기반 블록 생성 기법의 메쉬 분포 통계 지표 | Statistical indexes for cube- and k-menas clustering-based block generation.

Index	Cube	k-means clustering
Average	36.88	36.88
Standard deviation	17.88	11.10

Download Excel Table

Cube 기반의 블록 생성의 경우, 그림 3(a)와 같이 정규 블록의 크기를 확장한 블록을 생성하여 해당 영역에 포함되는 메쉬를 분류하여 연장 영역 생성을 수행한다. 클러스터링 기법을 활용한 블록 생성에서는 그림 3(b)와 같이 각 클러스터 내 모든 메쉬를 포함할 수 있는 구 반경을 조사하고, 해당 구 반경보다 일정 비율 큰 구를 그려 그 내부에 존재하는 메쉬를 연장 영역에 할당하는 방식을 사용하였다.

그림 3. | Fig. 3. Cube 및 k-평균 클러스터링 기반 연장 영역 할당 방식 모식도 | Configuration of extended region edge allocation for cube- and k-means clustering-based methods.

Download Original Figure

3-3 CBF 계산시간 비교 및 모노스태틱 RCS 해석 결과 검증

본 절에서는 각 방식에 대한 비교분석을 진행하였다. 앞서서 제시한 cutted-cone 구조에 대해서 해석을 진행하였고, 그림 1과 동일하게 블록을 생성하여, 부영역별 CBF를 계산하였다. 계산 시간 분석 결과는 표 2, 그리고 해석 구조에 대한 모노스태틱 RCS 결과는 그림 4에 나타내었다. 검증용 모노스태틱 RCS 결과로 FEKO를 사용하였고, 두 블록 생성 기법 모두 잘 일치하는 것을 확인하였다.

표 2. | Table 2. 각 기법별 CBF 계산 시간 비교 | Comparison of CBF computing time.

^* CPU: Intel(R) Xeon(R) Gold 6230R @ 2.10 GHz.

Index	Cube	k-means clustering
Total number of CBFs	16,981	18,379
Total computing time for CBFs	287 sec	251 sec
Averaged computing time per CBF	16.90 msec	13.66 msec

Download Excel Table

그림 4. | Fig. 4. 모노스태틱 RCS 해석 결과(주파수: 10 GHz) | Monostatic RCS result (frequency: 10 GHz).

Download Original Figure

표 2의 결과를 보면, CBF의 개수가 더 증가한 것을 확인할 수 있다. 이는 연장 영역 생성 시, 몇몇 부영역에 불필요한 메쉬가 많이 할당된 것이 원인으로 사료된다. CBF의 개수가 늘어났음에도 클러스터링을 활용한 블록 생성 기법의 전체 CBF 계산 시간이 12.5 % 정도 감소된 것을 확인할 수 있다. CBF 계산 시간은 블록별 Z 행렬의 크기에 영향을 받는데 이는 블록 내 메쉬 분포와 관련이 있고, 생성 CBF의 개수와는 무관하기 때문이다. 또한, CBF당 평균 계산 시간을 확인해 보면, 각각 16.90 msec/CBF와 13.66 msec/CBF로 제안한 기법을 통해 계산 시간이 19.2 % 정도 감소하는 것을 확인할 수 있다.

Ⅳ. 결 론

본 논문에서는 클러스터링 알고리즘을 활용한 계산 시간 가속화 방안을 제시하였다. 같은 수의 블록일 때, 총 CBF 계산 시간은 12.5 %, CBF당 평균 계산 시간은 19.2 %의 계산 시간 감소를 보였다. 균일한 메쉬 분포를 가지는 블록을 생성할 수 있다는 점에서 추후 CBFM 기법의 해석 효율성 측면에 큰 기여를 할 수 있을 것이다. 논문에서 제시한 구조뿐만 아니라, 다양한 복잡한 구조에 대해서도 제안한 방법을 사용하여 충분히 계산 시간을 감소시킬 수 있을 것으로 사료된다.

Acknowledgements

이 연구는 국방과학연구소의 연구비의 지원으로 연구되었음.

본 연구는 방위사업청과 국방과학연구소가 지원하는 스텔스 대형 플랫폼 전파해석 특화연구실 사업의 일환으로 수행되었습니다(UD200047JD).

References

[1].

J. Song, C. C. Lu, and W. C. Chew, “Multilevel fast multipole algorithm for electromagnetic scattering by large complex objects,” IEEE Transactions on Antennas and Propagation, vol. 45, no. 10, pp. 1488-1493, Oct. 1997.

[2].

V. V. S. Prakash, R. Mittra, “Characteristic basis function method: A new technique for efficient solution of method of moments matrix equation,” Microwave and Optical Technology Letters, vol. 36, no. 2, pp. 95-100, Jan. 2003.

[3].

D. J. Yun, I. I. Jung, H. Jung, H. Kang, W. Y. Yang, and I. Y. Park, “Improvement in computation time of the finite multipole method by using K-means clustering,” IEEE Antennas and Wireless Propagation Letters, vol. 18, no. 9, pp. 1814-1817, Jul. 2019.

[4].

D. Yun, H. Jung, H. Kang, W. Y. Yang, and D. W. Seo, “Acceleration of the multi-level fast multipole algorithm using K-means clustering,” Electronics, vol. 9, no. 11, p. 1926, Nov. 2020.

[5].

C. S. Park, Y. R. Jeong, I. P. Hong, and J. G. Yook, “Block size optimization of CBFM for scattering problems,” IEEE Transactions on Antennas and Propagation, vol. 66, no. 10, pp. 5370-5377, Oct. 2018.