STP-MSPBEL 근사 알고리즘을 통한 무선 센서 네트워크에서의 효율적인 릴레이 노드 배치 방법
Alternative Title
An Efficient Relay Node Placement in Wireless Sensor Networks via STP-MSPBEL Approximation Algorithms
Issued Date
2022-12-22
Citation
우은규. (2022-12-22). STP-MSPBEL 근사 알고리즘을 통한 무선 센서 네트워크에서의 효율적인 릴레이 노드 배치 방법. 2022 한국소프트웨어종합학술대회 (KSC 2022), 973–975.
Type
Conference Paper
Abstract
무선 센서 네트워크(Wireless Sensor Networks)에서 많은 노드가 동시에 손상되어 네트워크가 여러 부분으로 분할되는 경우, 네트워크의 연결 단절이라는 큰 결함으로 이어질 수 있다. 이러한 상황에서, 네트워크의 연결을 비용과 시간 측면에서 효율적으로 복구하는 것이 매우 중요하다. 본 논문은 가장 적은 수의 릴레이 노드를 배치함으로써 연결을 완전히 복원하는 것을 목표로, 제한된 간선 길이 하의 스타이너트리 문제(STP-MSPBEL)에 대한 근사 알고리즘들을 제시한다. STP-MSPBEL 문제는 트리의 모든 간선의 길이가 주어진 양수 이하임을 만족하면서, 스타이너 점의 개수를 최소화하는 문제이다. 이 문제는 NP-Complete임이 증명되었으며, 선행연구에 의해 다항 시간 알고리즘의 근사율이 5에서 3으로 줄어든바 있다. 본 논문에서는 최악의 경우 근사율이 3임이 보장되면서, 선행연구보다 개선된 휴리스틱 알고리즘들을 제시하고, 그 성능을 비교실험을 통해 확인한다.
