Advanced
Design and Implementation of Optimized Route Search Technique based on User Experience Using Open APIs
Design and Implementation of Optimized Route Search Technique based on User Experience Using Open APIs
Journal of Korea Multimedia Society. 2015. May, 18(5): 682-690
Copyright © 2015, Korea Multimedia Society
  • Received : February 11, 2015
  • Accepted : April 09, 2015
  • Published : May 31, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
운 사공
Dept. of Computer Engineering, Yeungnam University
wsagong@yu.ac.kr

Abstract
Among location-based systems, a route search service is very highly utilized as a representative technique, but it provides relatively low accuracy when we find a route path on foot in our real environment. In this paper, we design and implement an optimized route search technique based on user experience utilizing open APIs as location-based services. Finally, we develop an Android-based application to provide this feature. In our experiment, we found that our technique enhanced performance by about 14-36% compared to previous solutions, such as route path searches using map APIs. In addition, the performance of our technique can be further enhanced, as the number of users who find such optimized route path is increasing.
Keywords
1. 서 론
개인용 휴대 단말기와 GPS수신기를 전자지도와 결합하여 차량이나 사람의 이동 경로를 탐색하는 소프트웨어 개발에 대한 연구가 활발하다 [1] . GPS를 사용하여 단말기의 위치 추적이 가능한 스마트폰이나 태블릿PC와 같은 스마트 디바이스의 보급으로 제공되는 다양한 서비스들은 우리의 일상에 많은 변화를 가져왔으며, 특히 LBS(Location Based Service)라 불리는 위치 기반 서비스는 사용자의 위치를 인식하여 그 위치에서 유용한 정보를 제공하거나 필요한 서비스를 제공하는 정보시스템으로 서비스 이용자에게 맞춤형 정보를 제공할 수 있다 [2] . 국내에선 위치정보를 기반으로 한 정보 제공을 목적으로 주변 정보서비스, 도로상황 및 교통 정보서비스, 위치 파악을 통한 안전 서비스, 사람,차량,물류 등을 추적 할 수 있는 서비스 등으로 다양하게 활용되고 있다 [11] 그 중 온라인 지도 서비스는 사용자가 지도상의 특정 위치를 지정하면 그 위치에 대한 지도, 항공사진, 거리의 사진, 해당위치까지의 이동수단에 대한 정보 및 소요시간 등 다양한 주변 정보를 제공한다. 온라인 지도 서비스 중 하나인 경로 탐색 서비스는 출발지와 목적지를 지정하면 그 구간의 최적 이동 경로에 대한 정보와 이동 시간, 이동 수단에 대한 정보 등을 제공하고 있다. 경로 탐색 서비스는 ‘길찾기’ 등으로 명명되어 온라인 지도 사용자들이 가장 많이 사용하는 서비스로 자리 매김하고 있다 [3] .
경로 탐색 서비스는 대부분 지적도와 같은 공식적인 지도를 기반으로 동작하며, 서비스 제공자의 다양한 경로 탐색 기법이나 교통정보 등을 반영하여 도로를 중심으로 경로를 탐색하여 이용자에게 그 결과를 보여준다. 그러나 공식적인 지도 정보를 기반으로 경로탐색을 수행하면 지도에는 나와 있지 않지만 이용자들의 통행이 빈번한 샛길이나 지름길에 대한 정보를 반영할 수 없어 최적화 된 경로의 탐색율이 낮아지는 단점이 있다. 이를 보완하기 위해서는 최적 경로 탐색 시 지도 상의 도로 정보뿐만 아니라 이용자의 통행이 빈번한 지름길에 대한 정보를 활용해야 하므로 지름길에 대한 데이터베이스 구축이 필요하다. 지름길에 대한 정보는 해당 지역에 거주하거나 그 길을 빈번하게 이용하는 사용자가 제공한 정보를 기반으로 구축되어야 하나, 개별적으로 제공한 정보는 비용과 시간의 부담이 가중되는 것은 물론이고 정보에 대한 신뢰도 또한 확신하기 어렵다. 소수의 사용자가 제공한 잘못된 정보로 인해 최적의 경로가 탐색되지 않거나 왜곡된 경로가 제시될 경우 정확도와 서비스 이용율이 낮아지게 될 것이다 [4] .
본 연구에서는 포털 사이트에서 제공하는 지도 오픈 API를 활용하여 목적지까지 최적화된 경로를 제공하기 위해 다수 사용자의 경험을 기반으로 경로를 탐색하는 기법을 개발하였다. 이 기법은 스마트폰에 설치된 응용 프로그램이 다수의 사용자가 이동시 선택한 경로를 추적하여 이를 바탕으로 지름길 데이터베이스를 구축한다. 사용자가 구축된 지름길이 포함된 경로를 탐색하면 응용 프로그램은 지름길 정보를 참조하여 탐색된 결과를 제공한다. 스마트폰에 해당 응용프로그램을 설치한 사용자가 많아지고, 사용 기간이 길어질수록 학습율의 증가로 인해 더욱 최적화된 경로탐색 결과를 얻을 수 있다. 본 연구의 실험결과, 기존의 탐색 경로보다 최대 36%이상 단축되었다.
이하 본 논문의 구성은 다음과 같다. 2장에서 관련 연구에 대해 살펴보고 3장에서 사용자 경험 기반 탐색 알고리즘을 제안하며 그리고 4장에서는 제안한 알고리즘과 기존 알고리즘을 비교하여 성능을 평가하고 5장에서 결론을 맺는다.
2. 관련연구
- 2.1 위치 기반 서비스(Location Based System)
위치 기반 서비스(Location Based System)는 이동통신망과 GPS를 이용하여 모바일 디바이스의 위치를 추적하고 측정한 위치와 관련된 다양한 정보를 제공하기 위한 기술로 이동통신망 기술, 위치추적 기술, 단말기 기술, 정보처리 기술 등, 유기적으로 결합된 시스템 구성을 필요로 한다. 스마트폰과 같은 이동 단말기들은 해당 단말기의 위치를 구하기 위해서, 내장된 GPS 칩이 복수의 GPS 위성에서 보내오는 반송파 신호의 위상이나 반송판 신호 코드를 추적하는 삼각측량법을 사용한다. 그러나 일반적으로 GPS만 활용하여 위치를 측위하면 많은 오차가 발생할 수 있어 정확한 위치를 얻기 위해 GPS, Wi-Fi, Cell- ID, Sensor 등의 다양한 하드웨어적인 요소와 소프트웨어 기술을 이용한 위치보정, 디지털 컴퍼스 등의 복합적인 기술을 사용한다 [2] . Fig. 1 은 스마트폰 환경에서 LBS 지원을 위한 주요 구성요소들이다.
PPT Slide
Lager Image
Components for LBS on smart phone.
구글, 네이버, 다음과 같은 포털 사이트에서는 사용자가 스마트폰이나 태블릿과 같은 스마트 디바이스를 이용하여 다양한 위치 기반 서비스를 활용 할 수 있도록 지도 정보를 제공하고 있다 [5] . Fig. 2 는 네이버에서 제공하고 있는 지도 서비스의 사례이다. 이들은 스마트 디바이스가 취득한 위치정보를 기반으로 위치 기반의 여행 정보 및 시설 정보 제공, 내 위치 검색, 길 찾기, 거리 측정, 면적 산정, 로드 뷰, 항공 뷰 등의 다양한 부가서비스를 제공하고 있다 [6] . 뿐만 아니라 LBS는 지리정보시스템(GIS), 지능형 교통시스템(ITS), 증강현실(AR, Augmented Reality) 등과 연동되어 모바일 시대의 가장 중요한 서비스가 되고 있다 [7] .
PPT Slide
Lager Image
Naver map service.
- 2.2 오픈 API와 매시업
API(Application Program Interface)는 프로그램 또는 애플리케이션이 플랫폼의 요청 처리를 위해 호출할 수 있는 서브루틴 또는 함수의 집합이다. 오픈 API는 ‘데이터 개방 및 공유’를 구현하는 핵심 기술로 개발자가 포털 사이트의 특정 서비스를 활용하여 직접 응용 프로그램이나 인터넷의 서비스를 개발할 수 있도록 포털 사업자에 의해 개방된 API이다. 다양한 포털 사이트는 자사 플랫폼를 활용하여 비즈니스 모델을 만들 수 있도록 다양한 API를 제공하고 있다. 구글, 네이버와 같은 포털 사이트는 자사의 검색, 지도, 로그인, 블로그, 카페 등과 결합하여 연동할 수 있는 다양한 서비스의 개발이 가능하도록 여러 가지 오픈 API를 공개하고 있다.
매시업(mashup)은 서로 다른 서비스를 제공하는 다양한 웹사이트를 조합하여 새로운 서비스를 제공하는 것으로, 대표적 예로는 Fig. 3 의 하우징맵( www.housingmaps.com )이 있다. 하우징맵은 구글의 지도 서비스와 부동산 정보 사이트인 크레이그 리스트( www.craigslist.org )를 결합 시킨 것으로 지도에서 특정 영역을 클릭하면 그 지역의 부동산 매물 정보를 보여주는 서비스를 제공한다. 국내에서도 호텔자바, korMedi, MTB Course 등 다양한 매시업 서비스가 등장하고 있으며, 점차 확대될 것으로 예상된다.
PPT Slide
Lager Image
Housingmap service.
매시업 서비스를 이용하면 이미 구축된 서비스를 조합하여 새로운 서비스를 만들어 낼 수 있으므로 서비스에 필요한 자원의 구축비용을 절감하고 시간을 단축시킬 수 있으며 다양하고 풍부한 서비스 제공이 가능하다. 본 연구에서는 포털 사이트가 제공하는 지도 오픈 API를 이용하여 사용자 경험 기반 경로탐색 서비스를 제공하는 안드로이드 기반 응용 프로그램을 개발한다 [8] .
3. 이동 경로 탐색 기법의 설계
- 3.1 사용자 경험 기반 이동 경로 탐색 기법의 필요성
온라인 지도 서비스 중 ‘길찾기’는 사용자가 스마트 디바이스를 사용하여 출발지와 목적지를 입력하고 경로탐색을 실행하면, 일반적으로 출발지에서 목적지까지의 여러 개의 추천 경로를 보여준다. 더불어, 출발지에서 목적지까지 교통수단별로 이동 거리와 소요시간을 표시하며 실시간 교통 정보를 반영하여 탐색된 최적의 경로를 보여준다. 대부분의 경로 탐색은 출발지에서 목적지까지 공인된 지도를 기반으로 이루어지므로 샛길이나 지름길과 같은 비공식적인 정보가 반영되지 않는다. 자동차로 이동하는 경우에는 대부분 도로 정보를 참조하고 실제 자동차가 다닐 수 있는 길이 한정되어 있으므로 실제 최단 경로와 큰 차이를 보이지 않지만 도보 이동의 경우 차이가 발생하는 경우가 많다 [9] .
Fig. 4 에서 보는바와 같이 포털사이트의 지도서비스에 접속하여 출발지를 중앙도서관으로, 도착지를 학교 외부의 특정지역으로 설정하고 ‘갈찾기’를 이용하면 (a)와 같은 추천 경로를 표시한다. 하지만 실제 많은 이용자들이 이용하는 경로는 (b)이다. 온라인 지도서비스가 추천하는 경로의 거리는 883m이지만 실제 이용자들이 이동하는 최단거리는 563m로 약 320m 정도의 차이를 보인다. 그 이유는 Fig. 4 에서 보는바와 같이, 추천경로로 나타나는 (b) 경로 중 일부가 공식적인 지도에는 길로 나타나지 않지만 많은 통행자들이 주로 다니는 지름길이기 때문이다. 즉, 공식적인 지도에 부분 경로 상에 존재하는 200m 구간이 통행로로 기록되지 않았기 때문이다.
PPT Slide
Lager Image
Comparison of paths.
이와 같은 결과는 Fig. 5 를 통해 확인할 수 있다. ‘디자인관’을 기준으로 중앙도서관-디자인관의 경로 (a)와 디자인관-목적지의 경로 (b)로 분리하여 탐색하면 추천 경로의 거리는 각각 335m, 880m가 된다. 경로를 각각 분리하여 탐색하면 총 거리는 1215m로 Fig. 4 에서처럼 통합하여 탐색한 경로의 거리인 883m보다 오히려 더 거리가 길어지게 된다. 만약 ‘디자인관’에서 ‘목적지’까지의 경로(c)가 통행로로 인식되어 있으면 그 경로를 반영하여 최단 경로를 구할 수 있다. 경로 (c)의 거리가 약 200m 이므로 전체 추천 경로는 535m가 될 것이며 이 값은 최초 통합하여 구한 경로보다 30%이상 단축된 것이다. 이처럼 대학과 같이 한정된 지역에는 포털사이트가 사용하는 지적도나 경로탐색 방법으로 찾을 수 없는 다양한 경로가 존재한다. 본 연구에서는, 숨겨진 경로를 파악하여 데이터베이스에 탑재하고 포털 사이트의 지도 API를 활용하여 최적화된 탐색 경로를 제공하는 응용프로그램을 개발한다.
PPT Slide
Lager Image
Finding a separated path.
- 3.2 사용자 경험 기반 최적화 이동 경로 탐색 및 설정 기법
- 3.2.1. 경로 탐색
본 연구에서는 앞서 언급한 문제를 해결하기 위해 사용자 경험 기반 최적화 이동 경로 탐색 및 설정 기법을 제안한다. 사용자 경험 기반 최적화 이동 경로 탐색 및 설정 기법이란 지도상에 도로로 표시되지 않은 길이라도 다수의 사용자들에 의해 빈번한 통행이 이루어지면 그 경로를 데이터베이스에 저장하고 이후에 경로탐색 요청이 발생하면 저장된 경로를 반영하여 탐색된 경로를 제공한다. 사용자 경험 기반 최적화 이동 경로 탐색 절차는 Fig. 6 과 같으며, 다음은 각 단계별 구체적인 동작 알고리즘이다.
PPT Slide
Lager Image
Optimized route search technique based on user experience
(1) 사용자의 의해 출발지와 목적지가 입력되면 각각의 위치 값을 추출한다
(2) 추출된 위치 값을 사용하여 두 경로 사이에 학습된 경로의 존재 여부를 검색한다.
(3) 두 지점 사이에 학습된 경로가 존재하지 않으면 기존의 경로 탐색 알고리즘을 사용하여 탐색 경로를 추출한다. 경로를 출력하기 위해 (7)로 간다.
(4) 두 지점 사이에 학습된 경로가 1개 이상 존재하면 학습된 경로를 중심으로 전체 경로를 분할한다.
(5) 분할된 경로에 대한 탐색 알고리즘을 적용하여 탐색 경로를 추출한다.
(6) 추출된 탐색 경로를 결합하여 1개의 탐색 경로로 조합한다.
(7) 추출된 탐색 경로를 mapView에 출력한다.
- 3.2.2. 사용자 경험 탐색 경로 반영
사용자 경험 기반 최적화 경로 탐색을 위해서는 사용자의 이동 경험을 데이터베이스에 저장하거나 내부 구성원이 제공한 경험 정보를 학습 경로 데이터 베이스에 저장해야 한다. 일부 구성원이 제공한 정보를 학습 경로 데이터베이스에 반영하는 것은 시간과 비용이 많이 발생할 뿐만 아니라 편의적이거나 검증되지 않은 경로가 반영될 위험성이 있다. 특히 상업적인 의도를 가지고 지름길 정보를 제공할 경우 왜곡된 정보의 반영으로 인해 최적 경로의 탐색이 불가능해 질 수도 있다. 그러므로 다수의 일반 통행자들의 빈번한 통행정보를 데이터베이스에 반영하는 것이 합리적인 방안이라 할 수 있다.
통행로를 지나다니는 통행자의 이동 정보를 서버로 전송하여 축적하고 일정기간 동안 그 발생빈도가 높을 경우에만 최적 경로 탐색에 그 정보를 반영하는 것이다. 응용프로그램의 배포 초기에는 길로 등록되지 않아 그 도로가 통행로로 등록되지 않더라도 다수의 사용자가 그 도로를 통행할 경우 그 지수가 높아져서 도로로 반영되게 된다. 반대로 사용자 경험을 통해 축적된 경로 정보라 할지라도 일정 기간 동안 통행 정보가 수집되지 않거나 일정 기준이하로 통행이 발생할 경우 경험 데이터베이스에서 삭제하여 탐색 경로 전체의 정확성을 높인다.
- 3.3 검증 도구의 설계 및 구현
사용자 경험기반 최적화 이동 경로 탐색 및 설정 기법의 검증을 위해 사용자 경험을 경로 탐색에 반영하여 경로 데이터베이스를 갱신한다. 먼저 검증할 대상 지역을 선정하고 포털사이트의 오픈 API를 활용하여 ‘길찾기’ 기능을 수행하는 응용 프로그램을 개발한다. 개발된 응용 프로그램은 대상 지역의 시설물 정보와 이동 경로를 탐색하고 응용 프로그램 사용자의 이동 경로를 추적하여 통행로도 등록되어 있지 않지만 통행이 발생하는 지역의 정보를 축적하게 된다. 응용 프로그램은 Fig. 7 과 같이 사용자가 입력한 출발지와 목적지의 정보를 네이버의 오픈 API를 활용하여 사용자에게 경로 정보를 제공한다 [10] .
PPT Slide
Lager Image
Android based application for performance testing.
본 연구에서 제안한 사용자 경험기반 최적화 이동 경로 탐색 및 설정 기법의 검증을 위해 개발된 응용프로그램은 사용자 경험 기반 경로 탐색서비스와 사용자의 경험 정보를 저장하는 기능을 탑재한다. 스마트 폰에서 이 응용프로그램이 실행 중인 경우, 기본 경로 탐색 서비스에 비해 향상된 경로 탐색 정보를 제공 받을 수 있을 뿐만 아니라, 실시간 이동 경로 분석을 위한 정보를 경로 분석 서버로 전송한다. 단, 서버로 전송되는 정보는 단말기나 단말기 소유자를 식별할 수 있는 정보를 제외하고 전송한다. 즉, 단말기 ID, 전화번호, 포털 ID등 사용자의 식별이 가능한 정보를 제외한 순수한 경로 이동 정보만 전송한다. 그 이유는 개인 정보 보호를 위해서 뿐만 아니라, 본 연구에서 제안하는 기법의 구현을 위해 필요한 정보는 통행 빈도이기 때문이다. 따라서 본 응용 프로그램은 다수의 사용자가 개인 정보 노출에 대한 부담없이 사용할 수 있도록 구현 되었다.
4. 성능 평가 및 분석
- 4.1 구현 및 테스트
사용자 경험 기반 경로 탐색을 위한 스마트폰 애플리케이션을 스마트폰에 설치하고 5곳의 경로에 대해 테스트를 실시하였다. 테스트 방법은 응용 프로그램 사용을 희망하는 사람을 대상으로 사용자의 동의하에 위치정보를 사용하였으며, 탐색된 위치 정보를 서버로 전송토록 하였다. 전송 시 개인정보보호를 위해 단말기 식별정보 등은 제외하고 시간과 위치정보만 전송토록 하였다.
- 4.2 테스트 결과
전송된 경로 정보를 바탕으로 학습된 사용자 경험 기반의 추천 경로와 기존 방식과의 차이를 Table 1 을 통해 요약하여 제시하였다. Table 1 에서 보는 것처럼 14~36% 추천 거리가 단축된 것을 알 수 있다. 아울러 Fig. 8 Fig. 9 Table 1 에서 제공된 경로 탐색에 대한 구체적인 사례로써, Biology Building과 Farmers Hall로의 경로 탐색에 대한 Naver 추천 길찾기와 사용자 경험 기반 길찾기 정보의 경로 선정과정에 있어서 실질적 차이를 보여 준다.
Performance Comparison Summary
PPT Slide
Lager Image
Performance Comparison Summary
PPT Slide
Lager Image
Route path of central library to biology building.
PPT Slide
Lager Image
Route path of central library to farmers hall.
5. 결 론
본 연구에서는 사용자의 통행 경험을 지도에 반영하여 기존의 경로 탐색 서비스가 제공할 수 없었던 최적화된 경로 탐색 기법을 제안하였으며, 검증을 위해 안드로이드 기반 응용프로그램을 개발하였다. 제안된 기법은 사용자가 요구하는 최적화된 경로를 제공하기 위해 다수의 사용자가 이용하는 이동 경로 정보를 서버에 반영하여 학습하게 하고, 이를 다른 사용자가 활용 할 수 있게 하였다. 기존의 온라인 지도 서비스가 가지는 단점을 보완하기 위해 보행자의 지름길 이용 정보를 자동으로 추가하거나 삭제하도록 구성된 것이다. 개발된 기법을 적용한 결과 최소 14%에서 최대 36%까지 경로 단축 결과를 보였으며, 사용자가 늘어날수록 성능이 향상되는 결과를 보였다. 성능 향상은 사용자와 사용시간이 늘어날수록 사용자 경험 데이터베이스에 반영되는 정보가 늘어나게 되기 때문이며, 추후 경로 최적화율은 더욱 높아질 것으로 예상된다. 기본적으로 본 연구는 도보 이동에 기반하여 연구가 진행되었으나, 추후 도보의 대안이 될 수 있는 이동 수단, 즉 자전거나 오토바이를 사용한 경로 이동에서도 유사한 방식의 경로 선정이 가능하므로 이와 관련한 후속연구를 진행할 예정이다.
BIO
사 공 운
1990년 2월 서울대학교 Bio_Statistics 전공(석사)
1989년 6월~2001년 3월 IBM Senior Manager
2001년 4월~2004년12월 International Solution Group CEO
2005년 1월~2013년 3월 KOLON BENIT 이사 KOLON iFortress 상무
2013년 9월~현재 영남대학교 공과대학 컴퓨터공학과 조교수
관심분야: IoT, 임베디드, Smart Factory
References
Pearlman R. , Scott S. “IVHS Map Database Transfer Standards: Current Status, Transfer Standards : Current Status,” Proceeding of 1995 Vehicle Navigation and Information System 1995 368 - 378
Choi H.O. 2003 “Location Based Service,” TTA Journal 1 (86) 59 - 69
Jeong M. , Choi W.S. 2010 “Technology Trends for Smart Phone Location Based Service,” TTA Jourmal 4 (130) 75 - 81
Ham Y.K. , Kim T.E. 2005 “The Optimization Path Searching Method Development for Destination,” Journal of Digital Contents Society 6 (1) 55 - 62
Song E.J. 2012 “A Case of the Mobile Application System Development using Location Based Service,” Journal of Digital Contents Society 13 (1) 53 - 60    DOI : 10.9728/dcs.2012.13.1.053
Ahn Y.A. , Lee J.H. , Cho H.J. "Study of Mobile Context Data Management for LBS," Proceeding of International Digital Design Invitation Exhibition 2011 249 - 250
Kim J.P. , Lee D.C. 2014 "Development of Mobile Location Based Service App using Augmented Reality," Journal of the institute of information and Communication Engineering 18 (6) 1481 - 1487    DOI : 10.6109/jkiice.2014.18.6.1481
Ko S.H. 2010 “A Trend of Android Platform,” The Korea Contents Association Review 8 (2) 45 - 49
The Analysis on the Research of Practical Use of Location Information http://www.kisa.or.kr/public/library/reportView.jsp?regno=011546
Bae H.J. 2008 “Google Android Programming: Application Structure Analysis”,Maso Interactive 236 - 242
Seo M.J. , Kim M.G. , Kim. J.H. , Kim H.I. “A location-based deals recommendation system for mobile devices,” Proceeding of the springl Conference of the Korea Multimedia Society 2012 106 - 107