[논문]실시간 모바일 GIS를 위한 효율적인 경로탐색 기법

이형석; 김경창

[국내논문] 실시간 모바일 GIS를 위한 효율적인 경로탐색 기법
Efficient Path Search Method in Real-Time Mobile GIS 원문보기

이형석 (홍익대학교 컴퓨터공학과) , 김경창 (홍익대학교 컴퓨터공학과)

본 논문에서는, 비교적 제약이 심한 모바일 클라이언트를 위해 구현한 실시간 모바일 GIS에서, 최적의 경로탐색을 위한 최단 경로 탐색 관리자를 추가하였다. CAD파일로부터 추출한 벡터기반의 지리데이터를 사용하여 최단경로 검색의 시간비용을 줄이고자 필요한 정보를 추가하고, 처리비용에 불필요한 부담이 되는 데이터를 제외하는 처리를 한 후. 질의의 빈도가 각각 다른 MBR들간의 특성을 고려하여 상황에 맞는 최단 경로질의 처리 방법을 선택 수행하도록 하여 서버의 부담을 줄이고 처리 속도를 향상시키고자 하였다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

□ 중에서도 GIS를 기반으로 한 지도 검색 서비스나 CNS(Ca「Navigation System) 등이 각광 받고 있고, 이러한 시스템에서 최적의 경로를 알려주는 최단 경로 서비스는 질의 빈도가 높은 것 중 하나이匚卜. 본 논문에서는, 지리 데이터의 빠른 검색을 위해 제안된 주기억 데이터베이스 시스템 기반의 GIS를 바탕으로, 경로 탐색 관리자를 추가하여 효율적인 경로 탐색을 위한 방법을 소개하고자 한다.

제안 방법

반면, 벡터 데이터는 지리 데이터의 특정 좌표계에서의 좌표들로 구성이 되기 때문에 시각화를 위한 프로세싱 과정이 필요하지만 데이터의 업데이트가 용이하고 보다 다양한 질의를 통해서 데이터를 선택할 수 있다는 장점이 있다. 때문에, 많은지도 데 이 터들은 벡터 기반의 데이터로 제공되어 지고, 본 시스템에서도 벡터 데이터를 기반으로 GIS 시스템을 구현하였고, 이들 데이터를 최단 경로 탐색 관리자를 구현하는데 기본 데이터로 이용하도록 하였다. 효율적인 경로 탐색을 위해 원 데이터(shp format)에 필요한 정보를 추가하고 불필요한 데이터를 제외 시키는 작업을 거쳐 경로 탐색 데이터를 형성하고, 각 MBR에 요청되는 최단 경로 질의의 빈 도수와 객체 노드들의 비율을 고려하여 상황에 따라 더 빠르게 수행되어 질 수 있는 최단 경로 질의 처리 방법을 제안한다.
때문에, 많은지도 데 이 터들은 벡터 기반의 데이터로 제공되어 지고, 본 시스템에서도 벡터 데이터를 기반으로 GIS 시스템을 구현하였고, 이들 데이터를 최단 경로 탐색 관리자를 구현하는데 기본 데이터로 이용하도록 하였다. 효율적인 경로 탐색을 위해 원 데이터(shp format)에 필요한 정보를 추가하고 불필요한 데이터를 제외 시키는 작업을 거쳐 경로 탐색 데이터를 형성하고, 각 MBR에 요청되는 최단 경로 질의의 빈 도수와 객체 노드들의 비율을 고려하여 상황에 따라 더 빠르게 수행되어 질 수 있는 최단 경로 질의 처리 방법을 제안한다.
도로의 크기, 방향성과 같은 도로의 속성과 교통량, 사고, 공사 등 실시간으로 변하는 도로의 교통 상황이 최단 경로 탐색에 있어 중요햔 변수들이 될 수 있으나, 본 시스 템에서는 각 도로 데이터의 위치 정보를 이용한 유클리드 거리를 사용하여 알고리즘을 구현하였다.
본 시스템은 CPU, 메모리 등의 자원 제약이 심한 모바일 기기들을 클라이언트로 하고 대부분의 질의를 서버에서 처리하여 최소한의 결과만을 클라이언트에 전송하도록 하는 환경에서의 GIS를 고려하여 구현하였다. 그림 1 과 같이 GIS 서버의 구조는 기본적으로 질의 관리자와 스키마 관리자, 인덱스 관리자, 메모리 관리자, 데이터 관리자, 페이지 관리자로 구성되어 있고, 여기에 경로 탐색을 위한 최단 경로 관리자 모듈을 추가하였다.
본 시스템에서도 CAD 파일 포멧의 지도 데이터를 불러와 각각의 벡터 데이터의 point, polygon 등의 속성에 따라 그림 2와 같이 각 layerO, 1, 2, 3을 구성하여 GIS 서버 에 데이터베이스를 구성하여. 사용한다.
사용한다. 여기에는 특별히 도로 정보를 판단할 lay아■가 없기 패문에, 도로 정모를 p이yline형태로 하로 저장한 Laye「4를 추가하였다.
도로 정보의 데이터를 통해 경로 탐색을 수행褂기 위해서는 각 도로의 주요 지점을 노드(node)화 시켜야 하는 데, 서론에서 언급했듯이 도로의 제반 속성들은 고려하지 않았기 때문에 그림 3(a)과 같이 방향성을 고려하지 않은 그래프 모델[4]을 선택하였고, 다음과 추가 처리 과정을 수행하였다.
경로 탐색을 위해 사전 처리를 거친 도로 정보 노드들 각각을 1차원 배열로 형성하여 위치 정보를 저장하고, 이 둘 배열의 인덱스를 이용하여 각 노드들 간의 거리를 □ 림 5와 같이 2차원 테이블로 형성하여 경로 탐색에 사용한다.
이런 두 알고리즘의 특성을 이용하여, 특정 MBR영역 에 요청되는 경로함 색 질의를 카운트하여 기록하고, 일 정 주기 동안 요청되는 경로 탐색 요청 질의의 평균이 해당 MBR의 노드들보다 많아질 경우 디。yd algorithm을 이용하여 노드들 간의 최단 경로 테이블을 미리 계산하여 경로와 거리 값을 저장하고, 이를 이용하여 서버의 부담을 줄일 수 있도록 구현하였다.
본 시스템은 MR-Tree[1]2F T-Tree[2]2| 인덱스 기법을 사용하여 구현한 주기억 데이터베이스 시스템을 기반으로 설계되었고, 추가된 도로 정보 또한 빠른 검색속도를 보장하기 위해서 MR-T「ee를 사용하여 저장하도록 하였다.
본 시스템은 벡터 기반의 지리 데이터를 주기억 데이터베이스 시스템을 기반으로 구축하여 모바일 클라이언트가 실시간으로 지리 데이터를 검색할 수 있도록 구현 한 시스템에 최단 경로 관리자를 추가적으로 구현하였다. 추출한 데이터를 일련의 과정을 거쳐 경로 탐색 질의에서 더 적은 공간으로 더 빠르게 수행할 수 있도록 하였다.
본 시스템은 벡터 기반의 지리 데이터를 주기억 데이터베이스 시스템을 기반으로 구축하여 모바일 클라이언트가 실시간으로 지리 데이터를 검색할 수 있도록 구현 한 시스템에 최단 경로 관리자를 추가적으로 구현하였다. 추출한 데이터를 일련의 과정을 거쳐 경로 탐색 질의에서 더 적은 공간으로 더 빠르게 수행할 수 있도록 하였다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] 실시간 모바일 GIS를 위한 효율적인 경로탐색 기법
Efficient Path Search Method in Real-Time Mobile GIS 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper

문제 정의

제안 방법

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 실시간 모바일 GIS를 위한 효율적인 경로탐색 기법 Efficient Path Search Method in Real-Time Mobile GIS 원문보기

초록 용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

AI 본문요약 엑셀 다운로드 AI-Helper

문제 정의

제안 방법

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 실시간 모바일 GIS를 위한 효율적인 경로탐색 기법
Efficient Path Search Method in Real-Time Mobile GIS 원문보기

초록
AI-Helper

AI 본문요약
AI-Helper