| 1 |
1
내비게이션 기기에서 출발지 및 목적지와 탐색제한 시간 정보를 입력 받아 상기 탐색제한 시간 정보 보다 적은 시간이 되도록 휴리스틱 값을 조절한 후 메쉬 셋을 추출하여 경로 탐색 예상 시간을 추정하는 경로 탐색 스케쥴러와,
상기 경로 탐색 스케쥴러로부터 전달된 상기 휴리스틱 값 및 메쉬 셋으로 경로 탐색을 수행하는 경로 탐색부
를 포함하는 QoS 보장 경로탐색 장치
|
| 2 |
2
제 1항에 있어서,
상기 경로 탐색 스케쥴러는,
상기 입력된 출발지 및 목적지 사이의 다중 도로 네트워크에 대한 복수의 레벨 사용 여부를 판단하는 레벨 판단부와,
상기 판단된 레벨에 기 설정된 휴리스틱 값을 할당하는 휴리스틱 값 추출부와,
상기 할당된 휴리스틱값으로 상기 출발지 및 목적지 사이의 메쉬 셋을 추출하는 메쉬셋 추출부와,
상기 추출된 메쉬 셋으로 상기 경로 탐색 예상 시간을 추정하여 상기 경로 탐색 예상 시간이 상기 탐색제한 시간 보다 적은 경우에만, 상기 경로 탐색 예상 시간 추정에 사용된 상기 휴리스틱 값 및 메쉬 셋을 상기 경로 탐색부로 전달하는 추정부와,
상기 추정부로부터 전달된 상기 휴리스틱값에 기 설정된 값만큼 추가시키는 명령을 상기 휴리스틱 값 추출부로 전달하는 휴리스틱값 조정부
를 포함하는 것을 특징으로 하는 QoS 보장 경로탐색 장치
|
| 3 |
3
제 2항에 있어서,
상기 추정부는,
각 메쉬별 링크 정보 및 기 테스트된 검색 시간 정보 테이블을 포함하는 것을 특징으로 하는 QoS 보장 경로탐색 장치
|
| 4 |
4
제 2항에 있어서,
상기 메쉬셋 추출부는,
상기 할당된 휴리스틱 값을 각 레벨 별로 달리 적용하여 상기 출발지 및 목적지 사이에 달리 적용된 각각의 메쉬 셋을 추출하는 것을 특징으로 하는 QoS 보장 경로탐색 장치
|
| 5 |
5
제 1항에 있어서,
상기 경로 탐색부는,
상기 휴리스틱 값과, 상기 메쉬 셋에 포함된 노드 및 링크 데이터를 메모리에 로딩한 후, 경로 탐색 알고리즘을 동작시켜 경로를 산출하는 것을 특징으로 하는 QoS 보장 경로탐색 장치
|
| 6 |
6
내비게이션 기기에서 출발지 및 목적지 정보와 탐색제한 시간 정보를 입력 받는 과정과,
기 설정된 휴리스틱 값으로 상기 출발지 및 목적지 주변의 제1메쉬 셋을 추출하는 과정과,
상기 추출한 제1 메쉬 셋으로 경로 탐색 예상 시간을 추정하는 과정과,
상기 추정된 경로 탐색 예상 시간이 상기 입력 받은 경로 탐색 시간 정보를 초과하는지 여부를 판단하여 초과하는 경우, 상기 휴리스틱 값을 조절하여 제2 메쉬 셋을 추출하는 과정과,
상기 추출한 제2 메쉬 셋으로 경로 탐색 예상 시간을 추정하여 상기 경로 탐색 시간 정보 보다 적게 걸리는 경우, 상기 제2메쉬 셋으로 경로 탐색을 수행하는 과정
을 포함하는 QoS 보장 경로탐색 방법
|
| 7 |
7
제 6항에 있어서,
상기 제2 메쉬 셋을 추출하는 과정은,
A* 알고리즘의 직진성을 통해 검색 영역이 작아지도록 상기 휴리스틱 값을 기존 보다 큰 값으로 설정하는 것을 특징으로 하는 QoS 보장 경로탐색 방법
|
| 8 |
8
제 6항에 있어서,
상기 경로 탐색 예상 시간을 추정하는 과정은,
각 메쉬별 링크 정보 및 기 테스트된 검색 시간 정보 테이블을 포함하는 것을 특징으로 하는 QoS 보장 경로탐색 방법
|
| 9 |
9
제 6항에 있어서,
상기 제 1 메쉬 셋을 추출하는 과정 및 상기 제2 메쉬 셋을 추출하는 과정은,
상기 입력된 출발지 및 목적지 사이의 다중 도로 네트워크에 대한 복수의 레벨 사용 여부를 판단하여, 상기 복수의 레벨을 사용하는 경우, 상기 할당된 휴리스틱 값을 각 레벨 별로 달리 적용하여 상기 출발지 및 목적지 사이에 달리 적용된 각각의 메쉬 셋을 추출하는 것을 특징으로 하는 QoS 보장 경로탐색 방법
|
| 10 |
10
제 6항에 있어서,
상기 경로 탐색을 수행하는 과정은,
상기 휴리스틱 값과, 상기 제2 메쉬 셋에 포함된 노드 및 링크 데이터를 메모리에 로딩한 후, 경로 탐색 알고리즘을 동작 시켜 경로를 산출하는 것을 특징으로 하는 QoS 보장 경로탐색 방법
|
