현대 무선 통신 네트워크의 기본 요구 사항으로 높은 연결성과 넓은 네트워크 커버리지를 보장하기 위한 효율적인 중계소 배치 방식이 요구된다. 이에 본 논문은 모든 중계소 간의 연결을 완벽히 보장하기 위한 방법을 제안한다. 동적계획법을 이용하여 추가적인 중계소 배치를 통해 모든 중계소가 연결되도록 하는 새로운 방법을 제안하였다. 본 논문에서 제안된 알고리즘은 그리드 환경에서 작동하며 환경 내에는 임의로 중계소가 배치될 수 없는 셀이 형성된다. 기존에 배치된 중계소의 연결관계에 따라 그룹을 설정하고 추가로 배치하는 중계소의 수를 최소화하면서 모든 그룹이 연결되도록 추가 중계소를 배치한다. 시뮬레이션을 통한 중계소 배치의 시각화로 결과를 확인하여 모든 중계소의 연결을 확인할 수 있다.
An efficient relay station placement strategy is needed to meet the fundamental requirements of modern wireless communication networks for high connectivity and broad network coverage. This paper introduces a method to ensure complete connectivity by interlinking all existing relay stations. A novel approach is proposed, using dynamic programming, to ensure the connection of all relay stations through additional relay station placements. The proposed algorithm operates in a grid environment where cells incapable of random relay station placement is formed. Groups are established according to the connection relationship of previously deployed relay stations, and additional relay stations are arranged so that all groups are connected while minimizing the number of additional relay stations. The results are confirmed through the visualization of relay station placement via simulation, verifying the connectivity of all relay stations.