| 1 |
1
최적 경로를 탐색하기 위한 방법에 있어서,복수의 목적지들을 결정하는 단계;출발지와 제1 목적지를 반경으로 하는 제1 반경 내 하나 또는 그 이상의 제1 노드들을 결정하는 단계;상기 출발지에서 상기 결정된 적어도 하나의 제1 노드를 거쳐 상기 제1 목적지까지의 모든 경로들을 탐색하는 단계;상기 탐색된 경로들 각각에 대해 방향 패널티, 최대 방향 패널티, 링크 거리, 최대 링크 거리, 목적지의 거리 패널티 및 최대 목적지 거리 패널티를 고려하여 각 경로에 대한 경로 비용을 계산하는 단계;상기 계산된 경로 비용 중 최소값을 가지는 경로를 상기 출발지에서 상기 제1 목적지까지의 제1 최적 경로로 결정하는 단계;상기 제1 목적지와 제2 목적지를 반경으로 하는 제2 반경 내 하나 또는 그 이상의 제2 노드들을 결정하는 단계;상기 제1 목적지에서 상기 결정된 적어도 하나의 제2 노드를 거쳐 상기 제2 목적지까지의 모든 경로들을 탐색하는 단계;상기 모든 경로들 각각에 대해 방향 패널티, 최대 방향 패널티, 링크 거리, 최대 링크 거리, 목적지의 거리 패널티 및 최대 목적지 거리 패널티를 고려하여 각 경로에 대한 경로 비용을 계산하는 단계; 및상기 계산된 경로 비용 중 최소값을 가지는 경로를 상기 제1 목적지에서 상기 제2 목적지까지의 제2 최적 경로로 결정하는 단계를 포함하되,상기 각 경로에 대한 경로 비용은 제1 서브 경로 비용, 제2 서브 경로 비용 및 제3 서브 경로 비용의 합으로 계산되며,상기 제1 서브 경로 비용은 상기 방향 패널티의 값을 상기 최대 방향 패널티의 값으로 나눈 값에 가중치 a를 곱한 값이며,상기 제2 서브 경로 비용은 상기 링크 거리의 값을 상기 최대 링크 거리의 값으로 나눈 값에 가중치 β를 곱한 값이며,상기 제3 서브 경로 비용은 상기 목적지 거리 패널티의 값을 상기 최대 목적지 거리 패널티의 값으로 나눈 값에 가중치 γ를 곱한 값이며,상기 a, β 및 γ는 각각 0에서 1 사이의 값을 가지는 가중치 값인 것을 특징으로 하는 방법
|
| 2 |
2
제1 항에 있어서,상기 제1 최적 경로와 상기 제2 최적 경로를 포함하는 전체 경로 비용을 계산하는 단계; 및상기 전체 경로 비용이 최소인 경로를 상기 복수의 목적지들에 대한 최적 경로로 결정하는 단계를 더 포함하는 것을 특징으로 하는 방법
|
| 3 |
3
제1 항에 있어서,상기 a, β 및 γ의 합은 1인 것을 특징으로 하는 방법
|
| 4 |
4
제1 항에 있어서,상기 링크 거리는 노드와 노드 사이의 거리이며,상기 방향 패널티의 값은 좌회전 방향 또는 직진 방향일 경우 1이며,상기 목적지 거리 패널티의 값은 목적지와 멀어지는 경로 선택 시 1인 것을 특징으로 하는 방법
|
| 5 |
5
제1 항에 있어서, 상기 복수의 목적지들을 결정하는 단계는,탐색할 목적지의 개수를 설정하는 단계;상기 출발지를 중심으로 하는 제1 탐색 반경 내 상기 출발지로부터 최소의 거리를 가지는 목적지 A를 선택하는 단계; 및상기 목적지 A를 중심으로 하는 제2 탐색 반경 내 상기 목적지 A로부터 최소의 거리를 가지는 목적지 B를 선택하는 단계를 포함하는 것을 특징으로 하는 방법
|
| 6 |
6
제5 항에 있어서,상기 선택된 목적지의 수가 상기 설정된 목적지의 개수를 만족하는지 여부를 확인하는 단계를 더 포함하는 것을 특징으로 하는 방법
|
| 7 |
7
제6 항에 있어서,상기 선택된 목적지의 수가 상기 설정된 목적지의 개수를 만족하는 경우, 상기 선택된 목적지를 상기 복수의 목적지들로 결정하는 것을 특징으로 하는 방법
|
| 8 |
8
제6 항에 있어서,상기 선택된 목적지의 수가 상기 설정된 목적지의 개수를 만족하지 못한 경우, 상기 목적지 B를 중심으로 하는 제3 탐색 반경 내 상기 목적지 B로부터 최소의 거리를 가지는 목적지 C를 선택하는 단계를 더 포함하는 것을 특징으로 하는 방법
|
| 9 |
9
제1 항에 있어서,상기 복수의 목적지들은 상기 제1 목적지 및 상기 제2 목적지를 포함하는 것을 특징으로 하는 방법
|
| 10 |
10
최적 경로를 탐색하기 위한 장치에 있어서,RF(Radio Frequency) 모듈;적어도 하나의 프로세서; 및상기 적어도 하나의 프로세서에 동작 가능하게 접속 가능하고, 상기 적어도 하나의 프로세서에 의해 실행될 때, 동작들을 수행하는 지시(instruction)들을 저장하는 적어도 하나의 컴퓨터 메모리를 포함하며,상기 동작들은,복수의 목적지들을 결정하는 단계;출발지와 제1 목적지를 반경으로 하는 제1 반경 내 하나 또는 그 이상의 제1 노드들을 결정하는 단계;상기 출발지에서 상기 결정된 적어도 하나의 제1 노드를 거쳐 상기 제1 목적지까지의 모든 경로들을 탐색하는 단계;상기 탐색된 경로들 각각에 대해 방향 패널티, 최대 방향 패널티, 링크 거리, 최대 링크 거리, 목적지의 거리 패널티 및 최대 목적지 거리 패널티를 고려하여 각 경로에 대한 경로 비용을 계산하는 단계;상기 계산된 경로 비용 중 최소값을 가지는 경로를 상기 출발지에서 상기 제1 목적지까지의 제1 최적 경로로 결정하는 단계;상기 제1 목적지와 제2 목적지를 반경으로 하는 제2 반경 내 하나 또는 그 이상의 제2 노드들을 결정하는 단계;상기 제1 목적지에서 상기 결정된 적어도 하나의 제2 노드를 거쳐 상기 제2 목적지까지의 모든 경로들을 탐색하는 단계;상기 모든 경로들 각각에 대해 방향 패널티, 최대 방향 패널티, 링크 거리, 최대 링크 거리, 목적지의 거리 패널티 및 최대 목적지 거리 패널티를 고려하여 각 경로에 대한 경로 비용을 계산하는 단계; 및상기 계산된 경로 비용 중 최소값을 가지는 경로를 상기 제1 목적지에서 상기 제2 목적지까지의 제2 최적 경로로 결정하는 단계를 포함하되,상기 각 경로에 대한 경로 비용은 제1 서브 경로 비용, 제2 서브 경로 비용 및 제3 서브 경로 비용의 합으로 계산되며,상기 제1 서브 경로 비용은 상기 방향 패널티의 값을 상기 최대 방향 패널티의 값으로 나눈 값에 가중치 a를 곱한 값이며,상기 제2 서브 경로 비용은 상기 링크 거리의 값을 상기 최대 링크 거리의 값으로 나눈 값에 가중치 β를 곱한 값이며,상기 제3 서브 경로 비용은 상기 목적지 거리 패널티의 값을 상기 최대 목적지 거리 패널티의 값으로 나눈 값에 가중치 γ를 곱한 값이며,상기 a, β 및 γ는 각각 0에서 1 사이의 값을 가지는 가중치 값인 것을 특징으로 하는 장치
|
| 11 |
11
제10 항에 있어서, 상기 동작들은,상기 제1 최적 경로와 상기 제2 최적 경로를 포함하는 전체 경로 비용을 계산하는 단계; 및상기 전체 경로 비용이 최소인 경로를 상기 복수의 목적지들에 대한 최적 경로로 결정하는 단계를 더 포함하는 것을 특징으로 하는 장치
|
