STP-MSPBEL 근사 알고리즘을 통한 무선 센서 네트워크에서의 효율적인 릴레이 노드 배치 방법

Abstract

무선 센서 네트워크(wireless sensor networks)에서 많은 노드가 동시에 손상되어 네트워크가 여러 부분으로 분할되는 경우, 네트워크의 연결 단절이라는 큰 결함으로 이어질 수 있다. 이러한 상황에서, 네트워크의 연결을 비용과 시간 측면에서 효율적으로 복구하는 것이 매우 중요하다. 본 논문은 가장 적은 수의 릴레이 노드를 배치함으로써 연결을 완전히 복원하는 것을 목표로, 제한된 간선 길이 하의 스타이너트리 문제(STP-MSPBEL)에 대한 근사 알고리즘들을 제시한다. STP-MSPBEL 문제는 트리의 모든 간선의 길이가 주어진 양수 R 이하임을 만족하면서, 스타이너 점의 개수를 최소화하는 문제이다. 이 문제는 NP-Complete임이 증명되었으며, 선행연구에 의해 다항 시간 알고리즘의 근사율이 5에서 3으로 줄어든 바 있다. 본 논문에서는 최악의 경우 근사율이 3임이 보장되면서, 선행연구보다 개선된 휴리스틱 알고리즘들을 제시하고, 그 성능을 비교실험을 통해 확인한다.

In wireless sensor networks, when many nodes are simultaneously damaged and the network is divided into several parts, it can lead to a significant failure known as network disconnection. In such situations, it is extremely important to efficiently recover the network connection in terms of cost and time. This paper presents approximate algorithms for the Steiner Tree Problem with the Minimum number of Steiner Points and Bounded Edge-Length(STP-MSPBEL) to fully restore the connection by placing the minimum number of relay nodes. The STP-MSPBEL problem aims to minimize the number of Steiner points while satisfying the condition that the length of all edges in the tree is no more than a given positive constant. This problem has been proven to be NP-Complete, and prior studies have shown a reduction in the approximation ratio of the polynomial time algorithm from 5 to 3. In this paper, we propose improved heuristic algorithms that guarantee an approximation ratio of 3 in the worst case and demonstrate their performance through comparison experiments with previous works.