텔레매틱스 단말기를 위한 교통 정보를 활용한 최적 경로 탐색 기법

김진덕,Kim, Jin-Deog 한국정보통신학회 2006 한국정보통신학회논문지 Vol.10 No.12

최근 모바일 단말기의 위치정보를 활용하는 주요 응용 중의 하나인 최적 경로 탐색 시스템은 출발지와 목적지간의 거리뿐만 아니라 탐색 되어지는 구간에 존재하는 많은 교통 상황들을 파악하고 이를 경로 탐색에 활용해야 한다. 그러나 기존의 경로 탐색 알고리즘은 교통상황들을 적절히 이용하지 못하고 있다. 이 논문에서는 새로운 최적 경로 알고리즘을 제안한다. 알고리즘은 최적 경로를 검색하기 위해 교통상황을 고려하고, 연산비용을 줄이기 위해 도로를 그리드 형태로 나누어 각각의 평균속도를 가지고 휴리스틱 가중치를 부여한다. 또한 알고리즘의 전체 수행시간, 노드 접근 횟수, 최적경로의 정확도를 항목으로 하는 실험을 수행하여 기존의 탐색 알고리즘인 Dijkstra 알고리즘과 A*알고리즘과의 성능평가를 실시하였다. 실험 결과 제안한 알고리즘이 타 알고리즘에 대해 좋은 성능을 보여주었다. 제안한 알고리즘은 향상된 응용을 지원하는 텔레매틱스 시스템에 유용하게 사용될 것으로 기대된다. Optimal path search algorithm which is a killer application of mobile device to utilize location information should consider traffic flows of the roads as well as the distance between a departure and destination. The existing path search algorithms, however, are net able to cope efficiently with the change of the traffic flows. In this paper, we propose a new optimal path search algorithm. The algorithm takes the current flows into consideration in order to reduce the cost to get destination. It decomposes the road network into Fixed Grid to get variable heuristics. We also carry out the experiments with Dijkstra and Ar algorithm in terms of the execution time, the number of node accesses and the accuracy of path. The results obtained from the experimental tests show the proposed algorithm outperforms the others. The algorithm is highly expected to be useful in a advanced telematics systems.

빈번한 변경을 요구하는 실시간 스트림 데이터의 효율적 관리 및 슬라이딩 윈도우 질의

김진덕,Kim, Jin-Deog 한국정보통신학회 2008 한국정보통신학회논문지 Vol.12 No.3

최근 다수의 외부 장치를 제어하는 시스템에서는 빈번하게 변하는 신호의 이력을 자동적으로 관리하는 기법이 요구된다. 그 신호들은 스트림 데이터로서 다양한 종류, 짧은 보고 주기, 비동기적인 보고시간을 가진다. 또한 처리시스템은 스트림 데이터에 대해 높은 신뢰성과 실시간 처리를 필요로 한다. 그리고 스트림 데이터에 대한 질의는 최신의 값을 검색하는 현재 질의, 과거 특정시점의 값을 검색하는 스냅샷 질의, 과거부터 현재까지의 값들을 검색하는 슬라이딩 윈도우 질의 등이 있다. 이 논문에서는 소규모 운영체제에서 파일 구조화된 데이터베이스를 이용하여 스트림 데이터들을 효율적으로 저장하고 관리하는 기법을 제안하고자한다. 그리고 스트림 데이터에 대한 슬라이딩 윈도우 질의를 포함한 다양한 질의를 수용하는 질의 모델을 제안한다. 파일 기반 데이터 베이스는 QNX의 적은 저장장치, 낮은 계산 능력을 감안하여 델타버전과 공유메모리 버퍼링 등의 방법을 도입한다. Recently, the operator modules to control external devices are concerned about automatic management system to process continuously changed signals. These signals are the stream data of which characteristics are several numbers. a short report interval and asynchronous report time. It is necessary that the system brings about high accuracy and real time process for stream data. The typical queries of these systems consist of the current query to search the latest signal value, the snapshot query at a past time, the sliding window query from a past time to current. In this paper, we propose the efficient method to manage the above signals by using a file structured database in small-size operating systems. We also propose a query model to accommodate various queries including the sliding window query. The file database in the QNX adopts a delta version and a shared memory buffering method for the resource limit of a small storage and a low computing power.

영상을 이용한 차량의 주행 위치 측정 시스템

김진덕,문혜영,Kim, Jin-Deog,Moon, Hye-Young 한국정보통신학회 2011 한국정보통신학회논문지 Vol.15 No.12

최근 차량 항법 장치에서 널리 사용되고 있는 GPS 기술은 다음과 같은 두 가지 문제점을 가지고 있다. 첫째, 빌딩숲, 터널 등과 같은 도시 계곡(Urban Canyon) 지역에서는 GPS 신호 수신이 불가능하다. 둘째, GPS 신호를 이용한 측위는 항상 내재적인 위치 오차율 갖고 있다. 전자는 기존의 많은 연구를 통해 해결되었지만, 후자는 여전히 병행 도로와 같은 지역에서는 부정확한 위치 정보를 운전자에게 제공한다. 이 논문에서는 차량 네트워크와 기타 장비로부터 획득한 영상을 이용하여 차량의 주행 경로를 인식하는 시스템을 제안한다. 제안한 시스템은 실시간 영상 매칭 알고리즘을 이용한다. 또한 영상 매칭 정확도를 높이기 위한 기법 또한 제안한다. 이 논문에서 제안한 시스템은 실시간 주행 실험을 통해 원활하게 동작함을 보였다. 또한 매칭 정확도가 향상됨을 보여주었다. The GPS technique widely used recently in car navigation system has two problems that are unavailability in urban canyons and inherent positional error rate. The one has been studied and solved in many literatures. However, the other still leads to incorrect locational information in some area, especially parallel roads. This paper proposes and implements a system to recognize lane of moving vehicle based on images obtained from in-vehicle networks or other devices. The proposed system utilizes a real-time image matching algorithm which determines the direction of moving vehicle in parallel section of road. It also employs a method for accuracy improvement. The results obtained from experimental test on real-time navigation show that the proposed systems works well and the accuracy increases.

가변 휴리스틱 기반 추정치 간소화를 통한 경로탐색 기법의 설계 및 성능 평가

김진덕,Kim, Jin-Deog 한국정보통신학회 2006 한국정보통신학회논문지 Vol.10 No.11

텔레매틱스 시스템에서의 경로 탐색 기법은 교통흐름의 변화에 따라 최단 운행 시간을 갖는 최적 경로가 변하기 때문에 최단 시간 뿐 만 아니라 도로의 교통 흐름까지 고려해야 한다. 기존의 경로 탐색 기법들은 이러한 교통 흐름의 변화에 능동적으로 대처 할 수 없다. 또한 교통 정보를 이용하는 탐색 기법은 기존의 최단 경로 탐색 기법보다 연산 수행시간이 길다. 이 논문에서는 추정치 계산의 단순화를 통한 최적 경로 탐색 기법을 구현하고 성능을 평가한다. 제안한 기법은 교통흐름에 적응적인 휴리스틱을 위해 고정 그리드를 도입한다. 또한 추정치 계산을 간소화하기 위해 출발지와 목적지 사이의 기울기를 고려하여 실수의 곱셈 연산 대신 단계화 된 정수의 덧셈 연산을 한다. 제안한 알고리즘은 최적 경로 정확도 향상뿐만 아니라 탐색 시간을 줄어듦을 실험으로 입증한다. The path search method in the telematics system should consider traffic flow of the roads as well as the shortest time because the optimal path with minimized travel time could be continuously changed by the traffic flow. The existing path search methods are not able to cope efficiently with the change of the traffic flow. The search method to use traffic information also needs more computation time than the existing shortest path search. In this paper, a method for efficiency improvement of path search is implemented and its performance is evaluated. The method employs the fixed grid for adjustable heuristic to traffic flow. Moreover, in order to simplify the computation of estimation values, it only adds graded decimal values instead of multiplication operation of floating point numbers with due regard to the gradient between a departure and a destination. The results obtained from the experiments show that it achieves the high accuracy and short execution time as well.

모바일 벡터 지도 서비스를 위한 객체 재사용 기법의 설계 및 구현

김진덕,최진오,Kim, Jin-Deog,Choi, Jin-Oh 한국정보처리학회 2003 정보처리학회논문지D Vol.10 No.3

클라이언트에서 검색한 지도를 스크롤할 경우 이미 전송받은 객체를 캐슁하여 무선 데이터 전송량을 줄일 수 있지만, 클라이언트 내에서 데이터 좌표 변환, 선택적인 객체 삭제, 압축 단계, 구조화 단계가 부가적으로 요구된다 특히 좌표 변환 연산은 모바일 휴대폰의 낮은 계산 능력, 적은 메모리 용량 등과 같을 제한적 자원으로 많은 시간이 요구된다 따라서 휴대폰 기반 모바일 지도 서비스에서 효과적인 지도 제어 연산을 수행하기 위해서는 휴대폰의 제한적인 자원을 극복함과 동시에 무선 네트웍 대역폭을 줄이는 방안으로서 객체 재사용 기법이 연구되어야 한다. 이 논문에서는 클라이언트-서버 기반 모바일 벡터 지도 서비스 시스템에서 지도 제어를 위한 객체의 효율적인 객체 재사용 기법을 제안한다. 또한 실제 데이터를 제공하는 Web GIS 시스템을 이용한 실험 평가는 제안한 기법이 모바일 폰을 위한 지도 서비스에 적합하다는 것을 보여준다. 그리고 실험 결과를 토대로 객체 재사용 방법과 재전송 방법의 장단점을 분석한다. Although the reuse of the cached data for scrolling the map reduces the amount of passed data between client and server, it needs the conversions of data coordinates, selective deletion of objects, cache compaction and object structuring step in the clients. The conversion is a time- intensive operation due to limited resources of mobile phones such as low computing power, small memory. Therefore, in order to control the map efficiently in the vector map service based mobile phones, it is necessary to study the methods which reuse cached objects for reducing wireless network bandwidth and overwhelming the limited resources of mobile phones as well. This paper proposes the methods of reusing pre-received spatial objects for map control in the mobile vector map service system based on client-server architecture. The experiments conducted on the Web GIS systems with real data show that the proposed method is appropriate to map services for mobile phone. We also analyze the advantages and drawbacks between the reuse of cached data and transmission of raw data respectively.

부분순위 연속 k 최근접 객체 탐색 기법

김진덕,Kim, Jin-Deog 한국정보통신학회 2011 한국정보통신학회논문지 Vol.15 No.1

위치기반서비스와 지능형교통시스템 등의 응용분야에서는 이동 중인 경로 상에 존재하는 모든 지점에 대해 k개의 최근접 객체를 탐색하는 연속 k 최근접 객체 탐색 질의가 폭넓게 사용되고 있다. 최근접 질의는 위와 같은 응용에 빠른 응답을 요구하고, 공간 네트워크 데이터베이스에 적용가능해야 한다. 또한 잦은 POI(Point of Interest) 객체의 변경에 유연하게 대처해야 한다. 이 논문에서는 도로 네트워크에서 이동 중인 질의 객체를 위한 최근접 객체를 효율적으로 탐색하는 새로운 기법을 제안하고자 한다. 제안하는 기법은 다수의 분할점과 그에 상응하는 k개의 최근접 객체 집합들을 결과로 추출하며, POI들 간에는 순서가 없다. 실제 데이터를 이용한 실험은 제안한 기법에 기존 기법에 비해 우수함을 보인다. 최적의 조건에서 제안한 기법이 기존 기법에 비해 짧은 연산 시간(15%)을 보인다. In the application areas of LBS(Location Based Service) and ITS(Intelligent Transportation System), continuous k-nearest neighbor query(CkNN) which is defined as a query to find the nearest points of interest to all the points on a given path is widely used. It is necessary to acquire results quickly in the above applications and be applicable to spatial network databases. It is also able to cope successfully with frequent updates of POI objects. This paper proposes a new method to search nearest POIs for moving query objects on the spatial networks. The method produces a set of split points and their corresponding k-POIs as results with partial order among k-POIs. The results obtained from experiments with real dataset show that the proposed method outperforms the existing methods. The proposed method achieves very short processing time(15%) compared with the existing method.

보호자의 위치를 고려한 WiFi 기술 기반 이동 객체의 위치 관리 시스템

김진덕,강효운,Kim, Jin-Deog,Kang, Hyo-Woon 한국정보통신학회 2013 한국정보통신학회논문지 Vol.17 No.10

LBS는 이동 객체의 위치를 정확하게 확인하기 위해 주로 GPS 기술을 이용한다. 그러나 지금까지 휴대폰의 WiFi 기술을 활용한 이동 객체의 위치 관리 기법을 제시되지 않았으며, 또한 보호자의 위치를 고려한 이동 객체의 위치 관리 기법 또한 제시되지 않았다. 이 논문에서는 보호자의 위치를 고려한 WiFi 기반 이동 객체의 위치 관리 시스템을 제안한다. 구체적으로 미아 찾기 및 통보를 위해 다음과 같은 3가지 방법을 제안한다. 1) 스마트폰 앱 기반, 2) 관제 서버 기반, 3) 관제 서버와 고정 AP(Access Point) 기반 방법이 그것이다. 시스템은 보호자의 위치를 고려하므로 즉각적인 보호 아동 상태의 확인이 가능하다. LBS(Location Based System) usually uses GPS technology to measure the exact position of the moving object. However, the method of managing location which utilizes the WiFi technology of mobile phone has not been introduced so far. The method of managing moving objects in view of the location of guardian has also not been proposed. In this paper, a new location management system of moving objects which take guardian's location into consideration is proposed. Specifically, the three methods of searching for missing child proposed in this paper are as follows : 1) a method based on an app for smart phone, 2) a method based on control server, 3) a method based on control server and fixed APs. Because the proposed system reflects the location of the guardian, the guardian is able to identify the state of child immediately and the workload can be reduced.

방향성 정보를 이용한 최적 경로 탐색 알고리즘의 설계

김진덕,이현섭,이상욱,Kim Jin-Deog,Lee Hyun-Seop,Lee Sang-Wook 한국정보통신학회 2005 한국정보통신학회논문지 Vol.9 No.2

텔레매틱스의 주요 응용분야인 차량 항법 시스템은 CIS의 지도기술과 CPS의 측위 기술에 융합되어 탄생한 것이다. 기존의 시스템들은 정점과 정점간의 최단경로를 중심으로 한 경로 탐색을 제시하였지만 교통량의 변화와 교통사고 및 수시 병목 구간 등의 교통 변화에 대해서는 능동적인 대처를 할 수 없는 시스템이다. 바꿔 말하면 현실적으로 최단경로 탐색보다는 교통 정보를 파악하며 최단시간에 목적지로 도착하는 최적경로 탐색 시스템이 필요하다. 이 논문에서는 교통 정보를 기반으로 최적경로를 탐색하는 알고리즘을 제안한다. 구체적으로 최적 경로 탐색을 위한 시스템 구조를 제안하며 기존의 최단경로 탐색 알고리즘의 문제점을 살펴보고 수집되는 교통정보의 방향성을 활용하는 최적경로 탐색 알고리즘을 새롭게 제안한다. Car navigation system which is killer application fuses map management techniques into CPS techniques. Even if the existing navigation systems are designed for the shortest path, they are not able to cope efficiently with the change of the traffic flow and the bottleneck point of road. Therefore, it is necessary to find out shortest path algorithm based on time instead of distance which takes traffic information into consideration. In this paper, we propose a optimal path search algorithm based on the traffic information. More precisely. we introduce the system architecture for finding out optimal paths, and the limitations of the existing shortest path search algorithm are also analyzed. And then, we propose a new algorithm for finding out optimal path to make good use of the orientation of the collected traffic information.

텔레매틱스 단말기의 CDMA 통신을 이용한 위치 관리 시스템

김진덕,최진오,문상호,이상욱,Kim Jin-Deog,Choi Jin-Oh,Moon Sang-Ho,Lee Sang-Wook 한국정보통신학회 2004 한국정보통신학회논문지 Vol.8 No.8

대규모 영업용 차량의 텔레매틱스 단말기를 활용하여 효과적으로 위치 데이터를 획득하고 관리하면 이동 중인 차량의 관제 및 전체 도로 교통 흐름 정보를 추출할 수 있는 기반이 된다. 기존의 공간 색인에 관한 연구는 효율적인 검색 방법을 제시하였지만 텔레매틱스 단말기와 같은 객체를 다루는 이동체 데이터베이스에서는 질의처리의 효율성보다 이동 객체 최신 위치를 획득, 저장하는 것이 더 중요하다. 그러므로 보다 정확한 현재 위치 정보를 제공해야 하는 이동체 DB를 위해서는 병렬 처리 시스템의 도입이 필요하다. 이 논문에서는 텔레매틱스 단말기의 CDMA 통신을 이용한 위치관리 시스템을 제안한다. 구체적으로 다중 처리기를 이용하여 모바일 객체를 공간 색인하는 시스템을 제안하며, 데이터베이스의 변경연산을 최소화하기 위해 이동객체의 특성을 이용한 버켓 분할 기법을 제안한다. 그리고 처리기 간의 메시지 전송량을 줄이기 위한 데이터 획득 방법 및 버켓 경계 정보 전송 방법을 제안한다. If the location information of a great number of cars kept for business with telematics terminals is acquired and managed efficiently, this information forms the foundation for controlling cars and traffic flows. The studies on the pure spatial indices have focused on the efficient retrievals. However, the acquisition and management of the terminal location of moving objects are more important than the efficiency of the query processing in the moving object databases. Therefore, it will be need to adopt parallel processing system for the moving object databases which should maintain the object's current location as precise as possible. This paper proposes a location management system using CDMA communications of telematics terminals. More precisely, we propose a architecture of spatial indexing mobile objects using multiple processors, and also newly propose a method of splitting buckets using the properties of moving objects in order to minimize the number of database updates. We also propose a acquisition method for gathering the location information of moving objects and passing the information of the bucket extents in order to reduce the amount of passed messages between processors.

충북개발연구원 운영활성화 방안 -연구과제 성과거양 방안을 중심으로-

김진덕 ( Kim Jin Deog ) 충북개발연구원 1998 정책연구 Vol.98 No.2