다차원 이진트리를 한글색인사전의 구현

김희철(Hiecheol Kim),신정훈(Jeonghun Shin),이용두(Yong-Doo Lee) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.1B

본 연구에서는 지금까지 한글 전자사전이 가지고 있는 과다한 검색횟수, 비효율적인 주 기억 장치 사용, 이미 구축된 사전에 새로운 단어에 대한 추가 · 삭제의 어려움에 대한 단점들을 개선하기 위하여 다차원 이진트리 구조와 한글 전자사전을 구현한다. 본 논문에서 구현된 한글 전자사전의 검색시간 성능평가를 위해 입력 키워드(Keyword)의 종류에 따라 실험1, 실험2로 나누어 성능평가 한 결과, 실험 1에서는 구현된 사전의 단어를 입력 키워드로 사용하여 실험한 결과 제안한 사전구조가 기존의 트라이 사전구조 보다 약 1.5배 빠른 검색성능을 가진다. 실험 2에서는 입력 키워드의 평균 어절이 3.58이고, 입력 키워드가 사전에 존재하지 않는 경우가 전체 입력 단어의 48% 차지하는 조건에서의 실험결과도 다차원 이진트리 구조의 한글 전자사전이 트라이 구조의 한글 전자사전 보다 약 2.3배의 성능향상 결과를 가진다. 또 한편, 사전 구축 시 필요한 주 기억 장치 용량에 대한 성능평가 결과는 트라이 구조 사전은 1,987 Kbyte를 가지는 반면 제안한 다차원 이진트리 구조의 한글 전자사전은 1,136Kbyte를 가지므로 약 1.8배의 성능 향상을 가진다.

Formal Models of Module Linking Mechanisms for a Single Address Space

Hiecheol Kim(김희철),Won-Kee Hong(홍원기) 한국산업정보학회 2014 한국산업정보학회논문지 Vol.19 No.2

As WSNs(Wireless Sensor Networks) are being deployed widely in diverse application areas, their management and maintenance become more important. Recent sensor node software takes modular software architectures in pursuit of flexible software management and energy efficient reprogramming. To realize an flexible and efficient modular architecture particularly on resource constrained mote-class sensor nodes that are implemented with MCUs(Micro-Controller Units) of a single address space. an appropriate module linking model is essential to resolve and bind the inter-module global symbols. This paper identifies a design space of module linking model and respectively their implementation frameworks. We then establish a taxonomy for module linking models by exploring the design space of module linking models. Finally, we suggest an implementation framework respectively for each module linking model in the taxonomy. We expect that this work lays the foundations for systematic innovation toward more flexible and efficient modular software architectures for WSNs.

Static Analysis of AND-parallelism in Logic Programs based on Abstract Interpretation

Hiecheol Kim(김희철),Yong-Doo Lee(이용두) 한국산업정보학회 1997 한국산업정보학회 학술대회논문집 Vol.1997 No.11

수신 대기시간 보정을 통한 IEEE 802.15.4 MAC 프로토콜의 비컨 동기화 신뢰성 개선

김희철(Hiecheol Kim) 한국산업정보학회 2018 한국산업정보학회논문지 Vol.23 No.3

이 논문은 OS가 제공하는 소프트웨어 타이머를 사용한 네트워킹 스택의 구현 상황에서 고도의 정확성이 요구되는 시분할 동기적 통신의 신뢰성 문제를 다룬다. IEEE 802.15.4를 목표 프로토콜로 선정해 비컨 동기화의 신뢰성 향상 이슈를 상세히 탐구한다. 먼저, IEEE 802.15.4 비컨 모드의 구현에 소프트웨어 타이머를 사용할 때, 소프트웨어 타이머에 사용되는 하위 하드웨어 타이머 인터럽트의 처리 지연 및 유실과 소프트웨어 타이머 관리 오버헤드 등이 실제로 비컨 동기화의 저해요인으로 작용한다는 점을 실험을 통해 확인한다. 이러한 상황을 개선하기 위한 제안한 비컨 대기시간 보정기법은 비컨 동기화의 신뢰성을 향상시킨다는 점을 입증한다. This paper explores the reliability issue especially associated with the time-division synchronous communication when a networking stack is implemented using software timers provided by embedded operating systems. Especially, we explore the reliability of beacon synchronization of IEEE 802.15.4. Our experiments based on its practical implementation clearly show that processing delays or losses of hardware timer interrupts used for software timers lead to occasional failures in beacon synchronization. To avoid such failures, we suggest a reception time compensation scheme that turns on the receiver earlier than expected.

PROLOG로 부터 C 언어로의 코드변환 기법

김희철(Hiecheol Kim) 한국정보과학회 1998 정보과학회논문지(B) Vol.25 No.11

지난 10 여년의 연구 노력에도 불구하고 논리 언어인 프롤로그(Prolog)의 구현은 아직도 프로그래밍 구현의 연구 영역에서 중요한 테마로 여겨지고 있다. TC-Prolog는 논리 프로그램을 C 프로그램으로의 변환을 통하여 논리 프로그램을 구현하는 새로운 기법이다. 이 TC-Prolog는 C 언어 변환 방식 자체가 제공하는 신속한 구현성과 고이식성의 장점을 갖으며, 변환을 통해 코드의 실행 속도와 코드 크기면에서 높은 성능을 갖는다. 실제 구현을 통한 성능 분석의 결과, TC-Prolog는 기존의 가장 우수한 기법인 WAMCC보다 실행 속도와 코드 크기 면에서 각각 24%,와 30%의 성능 향상을 보이고 있다. 본 논문은 프롤로그 프로그램의 C-언어 프로그램으로의 변환에 관련된 여러 중요 기법들의 성능을 정성적으로 분석하는 방법론을 먼저 제시한 후, TC-Prolog를 포함한 기존 기법들의 성능의 정성적 비교결과를 기술한다. 그리고 본 논문의 주된 연구내용인 TC-Prolog 기법, 그리고 실험을 통한 성능 평가내용을 기술한다. Despite of the effort over the last decade, the implementation of Prolog is still an important issue in logic programming. TC-Prolog is a sequential Prolog engine based on a new scheme for the translation-based execution of logic programs. TC-Prolog aims at high quality of the output code in terms of the code size and its execution speed, while benefiting from the inherent advantages of translation-based approaches, i.e., fast prototyping and high portability. The empirical study of TC-Prolog shows that, with regard to the execution speed of the produced code and its code size, TC-Prolog shows respectively about 24 and 30 percents of improvement over WAMCC that is one of the most efficient translation-based sequential Prolog systems. This paper presents our study on a framework that enables us to qualitatively assess various crucial issues pertaining to the Prolog-to-C code translation. Then, we present our code translation scheme developed for TC-Prolog and the result of its empirical study made to evaluate and compare the performance between TC-Prolog and WAMCC.

TPC-C 벤치마크를 이용한 SPAX 병렬 컴퓨터의 성능분석

김희철(Hiecheol Kim),신정훈(Jeonghun Shin),이용두(Yong-Doo Lee) 한국산업정보학회 1997 한국산업정보학회 학술대회논문집 Vol.1997 No.11

협업기반 상황인지를 위한 u-Surveillance 다중센서 스테이션 개발

유준혁(Joonhyuk Yoo),김희철(Hiecheol Kim) 제어로봇시스템학회 2012 제어·로봇·시스템학회 논문지 Vol.18 No.8

Surveillance has become one of promising application areas of wireless sensor networks which allow for pervasive monitoring of concerned environmental phenomena by facilitating context awareness through sensor fusion. Existing systems that depend on a postmortem context analysis of sensor data on a centralized server expose several shortcomings, including a single point of failure, wasteful energy consumption due to unnecessary data transfer as well as deficiency of scalability. As an opposite direction, this paper proposes an energy-efficient distributed context-aware surveillance in which sensor nodes in the wireless sensor network collaborate with neighbors in a distributed manner to analyze and aware surrounding context. We design and implement multi-modal sensor stations for use as sensor nodes in our wireless sensor network implementing our distributed context awareness. This paper presents an initial experimental performance result of our proposed system. Results show that multi-modal sensor performance of our sensor station, a key enabling factor for distributed context awareness, is comparable to each independent sensor setting. They also show that its initial performance of context-awareness is satisfactory for a set of introductory surveillance scenarios in the current interim stage of our ongoing research.

SDS-TWR 기반의 거리측정 정확도를 위한 IEEE 802.15.4a 소프트웨어 스택 구현

유준혁(Joonhyuk Yoo),김희철(Hiecheol Kim) 한국산업정보학회 2013 한국산업정보학회논문지 Vol.18 No.6

거리측정(Ranging-based) 기반 무선측위 알고리즘을 활용하는 무선 네트워크 환경에서 위치추적의 정확도는 노드들 간의 거리측정의 정확도에 크게 좌우된다. 저전력 무선 네트워크 환경에서 거리측정 기반 무선측위의 실용화를 위해서는 하드웨어에서 제공하는 거리측정 정확도를 훼손시키지 않고 그대로 유지할 수 있는 안정된 HAL(Hardware Abstraction Layer)과 MAC(Medium Access Layer) 소프트웨어의 구현이 요구된다. 본 연구에서는 IEEE 802.15.4a를 지원하는 RF 칩인 나노트론(Nanotron)사의 NA5TR1를 기반으로 한 센서노드를 제작한 후 이 노드에 탑재될 IEEE 802.15.4a 소프트웨어 스택의 기본적인 기능을 설계?구현하였다. 소프트웨어 스택은 나노트론 사의 SDS-TWR 기법의 일반모드를 거리측정 알고리즘으로 채택ㆍ지원하고 있다. 개발된 센서노드를 활용해 테스트 네트워크를 구축한 후 노드간의 실 환경에서 실시간 거리측정의 정확도를 평가한 결과 SDS-TWR의 일반모드에서 평균 거리측정 오류율은 24.2%인 것으로 나타났다. The localization accuracy in wireless sensor networks using ranging-based localization algorithms is greatly influenced by the ranging accuracy. Software implementation of HAL(Hardware Abstraction Layer) and MAC(Medium Access Layer) should seamlessly deliver the raw performance of ranging-based localization provided by hardware capability fully to the applications without degrading the raw performance. This paper presents the design and implementation of the software stack for IEEE 802.15.4a which supports normal ranging mode of the Nanotron"s NA5TR1 RF chip. The experiment results shows that average ranging error rate with our implementation is 24.5% for the normal mode of the SDS-TWR ranging scheme.

정밀한 무선측위 기반 CPS를 위한 SDS-TWR 거리측정 기법의 성능 평가

유준혁(Joonhyuk Yoo),김희철(Hiecheol Kim) 한국통신학회 2014 韓國通信學會論文誌 Vol.39 No.9(네트워크)

거리 기반 실시간 측위 시스템에서 보다 정확한 측위가 가능하기 위해서는 우수한 측위 알고리즘과 함께 거리측정의 정확도 확보도 필수적으로 요구된다. 본 논문에서는 두 노드 간의 실제적인 거리측정의 정확도를 평가하기 위해 기존의 Symmetry 가정이 제거된 SDS-TWR 거리계산식 유도에 의한 정성적인 분석을 수행하고, 개발된 센서노드를 활용해 테스트 네트워크를 구축한 후 실험결과에 의한 정량적인 평가를 동시에 수행한다. 본 연구에서 구현된 IEEE 802.15.4a 소프트웨어 스택을 탑재한 센서노드 환경이 기존 나노트론사의 상용 참조보드 환경보다 평균 약 60% 감소된 거리측정 오차율을 산출하여 상대적으로 매우 높은 거리측정 정확도를 보인다. Range-based real time localization systems require superior localization techniques as well as accurate ranging algorithms for better performance. To evaluate the ranging accuracy between two nodes in practical environments, this paper does not only present a qualitative analysis by computing a distance equation under SDS-TWR measurement model of no symmetry assumption, but also executes a quantitative evaluation by doing experiments after building up a test network employing the developed sensor node. Experimental results show that the ranging accuracy of the proposed implementation of IEEE 802.15.4a software stack is superior with smaller average error rate by 60% to one of the commercial Nanotron"s reference development kit.

RFID 시스템에서의 트리 기반 메모리래스 충돌방지 알고리즘에 관한 연구

권성호,홍원기,이용두,김희철,Quan Chenghao,Hong Wonkee,Lee Yongdoo,Kim Hiecheol 한국정보처리학회 2004 정보처리학회논문지 C : 정보통신,정보보안 Vol.11 No.6

RFID(Radio Frequency IDentification) 기술은 RF 신호를 사용하여 물품에 부착된 전자태그를 식별하는 비접촉 기술이다. 식별 영역 내에 다수의 태그가 존재한 경우에 요구되는 다중 태그 식별 문제는 RFID 기술 중에서도 핵심 이슈이며 이 문제는 충돌방지 알고리즘을 통하여 해결할 수 있다. 하지만 기존 알고리즘들은 구현의 복잡성과 낮은 성능이 문제로 제기되고 있다. 본 논문에서는 이러한 문제를 해결할 수 있는 트리 기반 메모리래스 충돌방지 알고리즘인 충돌 추적(Collision Tracking) 트리 알고리즘을 제안하고 성능평가 결과를 제시한다. 성능평가 결과 제안하는 알고리즘이 초당 749개의 태그를 식별하면서 기존 트리 기반 메모리래스 알고리즘인 트리-워킹 알고리즘과 쿼리 트리 알고리즘에 비해 각각 약 49배와 2.4배의 성능향상을 확인할 수 있었다. RFID(Radio frequency IDentification) is a technology that automatically identifies objects containing the electronic tags by using radio wave. The multi-tag identification problem is the core issue in the RFID and could be resolved by the anti-collision algorithm. However, most of the existing anti-collision algorithms have a problem of heavy implementation cost and low performance. In this paper. we propose a new tree based memoryless anti-collision algorithm called a collision tracking tree algorithm and presents its performance evaluation results obtained by simulation. The Collision Tracking Tree algorithm proves itself the capability of an identification rate of 749 tags per second and the performance evaluation results also show that the proposed algorithm outperforms the other two existing tree-based memoryless algorithms, i.e., the tree-walking algorithm and the query tree algorithm about 49 and 2.4 times respectively.