차선거리유지 경로찾기 = Finding a Second Best Coverage Path

국문 초록 (Abstract)

사용자가 가능한 센서 가까이에서 이동하는 문제를 최단거리유지 문제(Best Coverage Problem)라 하며, 무선 연결의 안정성을 높이기 위해서 두 개의 센서로부터 최대한 가까이 위치하며 움직이는 이동경로를 차선거리유지 경로(Second Best Coverage Path)라고 한다. 이 논문에서는 센서들의 집합 U와 시작점 s, 끝점 t가 주어질 때, s에서 t까지 이르는 모든 경로 중에서, 가장 가까운 두 개의 센서까지 거리 중 큰 값이 최소가 되는 차선거리유지 경로를 찾는 ？O(nlogn)-시간 알고리즘을 제시하며, 차선거리유지 경로를 따라 움직일 때가 최단거리유지 경로를 따라 움직일 때 보다, 네트워크에의 연결이 보다 안정적임을 보여주는 실험결과도 또한 제시한다.

다국어 초록 (Multilingual Abstract)

The best coverage problem is finding a path whose worst distance to the sensor-set is the best among all paths. Instead, if the user stays close to its nearest two sensors, then the stability of the wireless connection may be guaranteed. So we consider the problem of finding a second best coverage path; given the sensor set U, a starting point s and a target point t, find a path whose worst distance to the second closest sensor is minimized. This paper presents an O(nlogn)-time algorithm to find such a path. We also give experimental evidence showing that the connection to the sensor-set along a second best coverage path is more stable than that along the best coverage path.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 예비지식
• 3. 차선거리유지 경로 알고리즘
• 4. 알고리즘의 합당성 및 시간복잡도
• 5. 실험
• 6. 결론 및 향후 연구
• 참고문헌

참고문헌 (Reference)

1 D. P. Mehta, "Optimal Coverage Paths in Ad-hoc Sensor Networks" 507-511, 2003

2 T. H. Cormen, "Introduction to Algorithms" MIT 2000

3 X. -Y. Li, "Coverage in Wireless Ad Hoc Sensor Networks" Vol.52(6) 52 (52): 2003

4 S. Meguerdichian, "Coverage Problems in Wireless Ad-hoc Sensor Networks" IEEE INFOCOM 1380-1287, 2001

5 J. O'Rourke, "Computational Geometry in C" Cambridge 1998

6 M. de Berg, "Computational Geometry - Algorithms and Applications" Springer 2000