센서들이 무선 네트워크 환경을 구성하는 경우, 사용자의 이동 경로와 센서의 거리는 중요한 요소로 작용한다. 거리가 멀수록 정보의 손실이 크고, 또한 각 센서는 사용자와의 접속을 유지하기 위해서 더 많은 전력을 필요로 한다. 따라서 가능하다면 사용자와 센서와의 거리를 짧게 줄이는 것이 필요하다. 사용자가 가능한 센서 가까이에서 이동하는 문제를 최단거리 경로 문제(Best CoveragePath Problem)라 하며, 무선 연결의 안정성을 높이기 위해서 두 개의 센서로부터 최대한 가까이 위치하며 움직이는 이동경로를 차선 최단거리 경로(Second Best Coverage Path)라고 한다. 이 논문에서는 주어진 센서들의 집합 U와 시작점 s, 도착점 t가 주어질 때, s에서 t까지 이르는 경로로서, 가장 가까운 두 개의 센서까지의 거리가 최소인 차선 최단거리 경로를 찾는 O(nlogn)-시간 ...
센서들이 무선 네트워크 환경을 구성하는 경우, 사용자의 이동 경로와 센서의 거리는 중요한 요소로 작용한다. 거리가 멀수록 정보의 손실이 크고, 또한 각 센서는 사용자와의 접속을 유지하기 위해서 더 많은 전력을 필요로 한다. 따라서 가능하다면 사용자와 센서와의 거리를 짧게 줄이는 것이 필요하다. 사용자가 가능한 센서 가까이에서 이동하는 문제를 최단거리 경로 문제(Best CoveragePath Problem)라 하며, 무선 연결의 안정성을 높이기 위해서 두 개의 센서로부터 최대한 가까이 위치하며 움직이는 이동경로를 차선 최단거리 경로(Second Best Coverage Path)라고 한다. 이 논문에서는 주어진 센서들의 집합 U와 시작점 s, 도착점 t가 주어질 때, s에서 t까지 이르는 경로로서, 가장 가까운 두 개의 센서까지의 거리가 최소인 차선 최단거리 경로를 찾는 O(nlogn)-시간 알고리즘을 제시한다. 최적의 차선 최단거리 경로를 찾음으로서 사용자는 센서 사이를 이동하면서 무선 네트워크의 잦은 끊김으로 인한 불안정성을 피할 수 있다.
센서들이 무선 네트워크 환경을 구성하는 경우, 사용자의 이동 경로와 센서의 거리는 중요한 요소로 작용한다. 거리가 멀수록 정보의 손실이 크고, 또한 각 센서는 사용자와의 접속을 유지하기 위해서 더 많은 전력을 필요로 한다. 따라서 가능하다면 사용자와 센서와의 거리를 짧게 줄이는 것이 필요하다. 사용자가 가능한 센서 가까이에서 이동하는 문제를 최단거리 경로 문제(Best Coverage Path Problem)라 하며, 무선 연결의 안정성을 높이기 위해서 두 개의 센서로부터 최대한 가까이 위치하며 움직이는 이동경로를 차선 최단거리 경로(Second Best Coverage Path)라고 한다. 이 논문에서는 주어진 센서들의 집합 U와 시작점 s, 도착점 t가 주어질 때, s에서 t까지 이르는 경로로서, 가장 가까운 두 개의 센서까지의 거리가 최소인 차선 최단거리 경로를 찾는 O(nlogn)-시간 알고리즘을 제시한다. 최적의 차선 최단거리 경로를 찾음으로서 사용자는 센서 사이를 이동하면서 무선 네트워크의 잦은 끊김으로 인한 불안정성을 피할 수 있다.
In a wireless network, the distance between the path of user and a sensor of the network is the most important factor. The longer is the distance, the more wastes the power and the more disconnected is the connection. So, If possible, a user should move closer to the sensors of the network. The best...
In a wireless network, the distance between the path of user and a sensor of the network is the most important factor. The longer is the distance, the more wastes the power and the more disconnected is the connection. So, If possible, a user should move closer to the sensors of the network. The best coverage path 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.
In a wireless network, the distance between the path of user and a sensor of the network is the most important factor. The longer is the distance, the more wastes the power and the more disconnected is the connection. So, If possible, a user should move closer to the sensors of the network. The best coverage path 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.
Keyword
#Wireless sensor network Voronoi diagram Computational geometry Find a path
학위논문 정보
저자
김정희
학위수여기관
숭실대학교 대학원
학위구분
국내석사
학과
컴퓨터학과
발행연도
2008
총페이지
vi, 25 p.
키워드
Wireless sensor network Voronoi diagram Computational geometry Find a path
AI-Helper
※ AI-Helper는 부적절한 답변을 할 수 있습니다.