제약만족 최적화 문제를 위한 백트래킹 탐색의 구조화

손석원,Sohn, Surg-Won 한국정보처리학회 2011 정보처리학회논문지 A Vol.18 No.3

모든 제약만족 최적화 문제의 해를 구하는 일반화된 알고리즘을 구하는 것은 매우 어렵다. 그러나 결정 변수의 특성에 따라 세분화된 문제는 해를 위한 알고리즘을 구하기에 더 쉽다는 가정을 할 수 있다. 이와 같은 가정 하에 문제를 세분화 시키는 문제분류규칙을 제안하고 세분화된 문제의 특성에 맞는 백트래킹 알고리즘을 개발한다. 백트래킹을 이용한 깊이우선탐색에서 해를 빨리 찾기 위한 방법 중 하나는 탐색되는 노드의 순서를 효과적으로 배열하는 것이다. 정적 특성이 우세한 무선 센서 네트워크의 클러스터 헤드 위치문제와 동적 및 정적 특성의 혼합특성을 갖는 RFID 리더 간섭 최소화 문제를 선택하여 최적의 변수 순서화 알고리즘을 개발하고 기존의 방법과 비교하였다. 결과적으로 문제를 세분화시킴으로써 체계적인 탐색을 위한 백트래킹의 구조화를 실현하였다. 또한 개발된 백트래킹 알고리즘의 성능이 우수함을 보였다. It is very hard to obtain a general algorithm for solution of all the constraint satisfaction optimization problems. However, if the whole problem is separated into subproblems by characteristics of decision variables, we can assume that an algorithm to obtain solutions of these subproblems is easier. Under the assumption, we propose a problem classifying rule which subdivide the whole problem, and develop backtracking algorithms fit for these subproblems. One of the methods of finding a quick solution is efficiently arrange for any order of the search tree nodes. We choose the cluster head positioning problem in wireless sensor networks in which static characteristics is dominant and interference minimization problem of RFID readers that has hybrid mixture of static and dynamic characteristics. For these problems, we develop optimal variable ordering algorithms, and compare with the conventional methods. As a result of classifying the problem into subproblems, we can realize a backtracking framework for systematic search. We also have shown that developed backtracking algorithms have good performance in their quality.

기지국 위치 문제를 위한 목적함수의 최적해 및 근사해

손석원,Sohn, Surg-Won 한국정보처리학회 2007 정보처리학회논문지 C : 정보통신,정보보안 Vol.14 No.2

The problem of selecting base station location in the design of mobile communication system has been basically regarded as a problem of assigning maximum users in the cell to the minimum base stations while maintaining minimum SIR. and it is NP hard. The objective function of warehouse location problem, which has been used by many researchers, is not proper function in the base station location problem in CDMA mobile communication, The optimal and approximate solutions have been presented by using proposed object function and algorithms of exact solution, and the simulation results have been assessed and analyzed. The optimal and approximate solutions are found by using mixed integer programming instead of meta-heuristic search methods. 이동 통신 시스템의 설계에 있어서 기지국의 위치를 선정하는 문제는 기본적으로 셀 내부 및 외부의 간접전파에 의한 최소 SIR을 만족하면서 최대한의 사용자를 최소의 기지국에 할당하는 문제로서 NP-hard 이다. 기존에 주로 사용된 목적함수는 창고위치문제에서 사용하던 것으로 CDMA 이동통신 시스템으로 직접 이용하는 단계에서 문제점이 발생한다. 그 문제점들을 해결하는 목적함수와 최적해 및 근사해를 구하는 알고리즘을 제안하고, 그에 따른 시뮬레이션을 하여 본 논문의 제안이 타당성이 있는지 평가 및 분석하였다. 본 논문에서는 기지국의 위치문제를 경험적 탐색방법을 사용하지 않고 혼합정수계획법의 완전해를 이용하여 최적해 및 근사해를 구하였다.

W -CDM A에서 기지국 위치선정 문제의 최적화

손석원(Surg-won Sohn) 호서대학교 공업기술연구소 2004 공업기술연구 논문집 Vol.23 No.1

This paper presents an optimization model for base station location in 3G W - C D M A uplink environm ent. The model concerns optim ization of the base station param eters such as base station location, transm itted pow er and antenna height, all of w hich can be in dividually assigned to each base station. All these choices m ust satisfy a set of constraints and optim ize a set of objectives. T his problem is contrasted with a warehouse location problem , so NP ᅳhard and consequently can not be practically solved by exact methods for real size networks. Thus w e apply a heuristic search m ethod for tackling this com plex and highly com binatorial problem . Integrated constraint and integer linear program m ing m ethod is presented for better output.

문제분류규칙을 이용한 변수 순서화 알고리즘

손석원(Surg-Won Sohn) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.4

백트래킹을 이용한 깊이우선탐색에서 해를 빨리 찾기 위한 방법 중 하나는 결정변수의 순서를 효과적으로 배열하는 것이다. 이 때 문제의 동적 및 정적 특성을 고려한 변수 순서화 알고리즘 개발은 매우 중요한 문제이다. 그러나 문제에 적합한 최적의 변수 순서화 알고리즘을 개발하는 것은 어려운 문제이다. 본 논문에서는 변수의 속성에 기반을 두어 문제의 형태를 규정하는 문제분류규칙을 제안하고 이 규칙을 이용하여 문제에 적합한 변수 순서화 알고리즘의 형태를 예측할 수 있게 한다. 결정변수가 동적 및 정적 특성을 갖는 DS-type 문제로서 주파수 할당문제를 선택하여 최적의 변수 순서화 알고리즘을 예측한다. 또한 문제분류규칙에 의해 생성되지 않는 특별한 형태의 문제인 기지국 위치문제를 적용하여 제안하는 문제분류규칙의 효용성을 입증한다. Efficient ordering of decision variables is one of the methods that find solutions quickly in the depth first search using backtracking. At this time, development of variables ordering algorithms considering dynamic and static properties of the problems is very important. However, to exploit optimal variable ordering algorithms appropriate to the problems. In this paper, we propose a problem classifying rule which provides problem type based on variables' properties, and use this rule to predict optimal type of variable ordering algorithms. We choose frequency allocation problem as a DS-type whose decision variables have dynamic and static properties, and estimate optimal variable ordering algorithm. We also show the usefulness of problem classifying rule by applying base station problem as a special case whose problem type is not generated from the presented rule.

상황인식 미들웨어의 설계와 적용에 관한 연구

장동욱,손석원,한광록,Jang, Dong-Wook,Sohn, Surg-Won,Han, Kwang-Rok 한국정보처리학회 2011 정보처리학회논문지D Vol.18 No.5

본 논문에서는 상황인식 시스템 개발에 필수적인 미들웨어의 설계와 적용에 관하여 논한다. 다양한 상황 데이터들을 처리할 수 있도록 트랜스듀서 인터페이스 프로토콜을 정의하고, 미들웨어 모듈 간 일관성 있는 데이터 처리를 위하여 메시지 기반의 미들웨어를 설계하고 구현하였다. 상황인식 미들웨어는 서비스 기반 구조로 설계되어서 모듈간 기능이 독립적이고 확장성이 뛰어나다. 또한 모듈 간 통신은 메시지를 이용하기 때문에 응용 프로그램 개발이 용이해진다. 본 논문의 상황인식 미들웨어는 교량의 구조물 건전성 감시 시스템에 적용하여 실험하였고, 미들웨어의 효용성을 확인하였다. This paper describes a design and application of middleware that is essential to the context-aware system. We define a transducer interface protocol in order to deal with a variety of context data. For the purpose of systematic process of data between middleware modules, a message oriented middleware is designed and implemented. Memory improves the performance of high-performance computing system compared to previous strategies. Context aware middleware adopts service oriented architecture so that functions in modules may be independent and scalability can be remarkable. Using messages across modules decreases the complexity of the application development. In order to justify the usefulness of the proposed context aware middleware, we carried out our experiments in bridge health monitoring system and verified the efficacy.

지상파 DMB 수신기 시험을 위한 방송신호 시뮬레이션 시스템

김유원(Yoo-Won Kim),손석원(Surg-Won Sohn),차상진(Sang-Jin Cha),조근식(Geun-Sik Jo) 한국컴퓨터정보학회 2008 韓國컴퓨터情報學會論文誌 Vol.13 No.3

지상파 DMB 수신기 및 그 응용제품은 일반적인 수신 시험, 잡음에 대한 수신상태 실험, 방송의 출력신호 변화에 따른 수신상태 변화 측정 및 수신환경의 변화에 따른 수신상태 등의 다양한 시험을 필요로 한다. 따라서 지상파 DMB 관련 연구기관과 제조업체 및 기타 유관 기관에서는 실시간으로 지상파 DMB 방송을 시뮬레이션 할 수 있는 시스템이 필요하다. 본 논문은 이러한 시험에 필요한 지상파 DMB 방송의 신호 스트림을 실시간으로 생성시키고, 실제의 방송과 유사하게 시뮬레이션하는 시스템의 개발에 관한 연구이다. 본 시스템은 PCI 인터페이스의 T-DMB 신호 생성기와 다양한 기능의 프로그램 모듈로 구성된 시뮬레이션 소프트웨어로 구성된다. 본 연구를 통하여, 경제적인 개발비용으로 PC 를 이용한 소프트웨어 기반의 T-DMB 시뮬레이션 시스템 구현이 가능함을 보였다. 또한 다양한 실험을 통하여 본 시뮬레이션 시스템의 성능을 평가하고 추후 연구 방향을 제시하고자 한다. The terrestrial DMB receivers and their application products need many tests such as normal reception, reception state for the noisy environment, reception state changes due to the changes of output power of the DMB signal, and reception state of various environment. Therefore, the real-time simulation system of the terrestrial DMB broadcasting system is a necessity to the terrestrial DMB research institutions. manufacturers, and other related organizations. In the paper, we design the DMB simulation system, which generates the real-time streams of terrestrial DMB broadcast signals and simulates the real DMB broadcasting signals. The system consists of T-DMB signal generator with PCI interface and simulation software for various functional components of program. The study reveals that the implementation of software-based T-DMB simulation system is possible with low cost. Through various experiments, we evaluate the performance of the simulation system, and we provide the future directions of research.

디지털 방송에서 효율적인 다중 오디오 모니터링 시스템

김유원(Yoo-Won Kim),손석원(Surg-Won Sohn),조근식(Geun-Sik Jo) 한국컴퓨터정보학회 2008 韓國컴퓨터情報學會論文誌 Vol.13 No.7

디지털방송(Digital Broadcasting)에서는 최대 100여개 정도의 오디오 또는 음악방송을 다중화하여 전송에 적합한 MPEG-2 TS(Transport Stream) 형태로 만들어서 1개 채널로 전송하는 것이 가능하다. 이렇게 다중화 된 많은 음악방송이 정상적으로 전송되고 있는지 확인하기 위해서는 실시간 모니터 링이 가능한 다중 오디오 모니터링 시스템이 필요하다. 아날로그방송에서는 모니터링 할 음악 방송수가 많지 않기 때문에 하드웨어 기반의 오디오 모니터링 시스템을 구현하여 사용하였다. 그러나 하드웨어 기반의 모니터링 시스템을 디지털 음악방송 환경에 적용하는 것은 비용 및 기능 효율성에서 떨어지기 때문에 디지털 방송 환경에 맞는 새로운 시스템이 요구되었다. 본 논문에서는 이 요구사항을 만족시키기 위해서 소프트웨어 기반의 디지털 오디오 모니터링 시스템을 설계하고 구현하였다. 시스템 구현에 있어서 다수의 하드웨어 장비의 도움 없이 소프트웨어를 기반으로 하는 1대의 컴퓨터만을 이용하여 1개 채널로 수신되는 다중화 된 디지털 음악방송을 효율적으로 모니터링 한다. 전송된 디지털 방송신호를 역다중화하여 각각의 방송에 대한 오디오 레벨 및 패킷 에러 정보를 추출하여 화면으로 실시간 상태를 표시하면서 정상적으로 방송이 되고 있지 않는 방송을 자동으로 검출하여 알려준다. 실험 결과 디지털 음악방송 채널에 대한 효율적인 실시간 다중 오디오 모니터링이 가능함을 보였다. In digital broadcasting, it is possible to multiplex maximum one hundred audio or music programs into MPEG-2 transport stream, which is suitable for transmitting through one channel. In order to check if multiplex music programs are transmitted well, we need a multiplex audio monitoring system that monitors the programs in real-time. In analog broadcasting, we have used hardware-based audio monitoring system for a small number music programs. However, the effectiveness of hardware-based audio monitoring system from the cost and function viewpoint is so low that a new system is needed for digital broadcasting. In this paper, we have designed and implemented a software-based audio monitoring system to satisfy these requirements. In this implementation, only one PC is used without other hardware facilities, and the system monitors digital broadcasting music programs effectively. Transmitted digital broadcasting streams are demultiplexed into many music programs and the realtime value of audio level and packet error information for these programs are displayed in the screen. Thus, the system detects and shows the abnormal transmitting programs automatically. Simulation results show that effective realtime multiplex audio monitoring is possible for digital broadcasting music programs.

응급상황의 신속한 감지를 위한 u-Health 시스템 개발에 관한 연구

장동욱,선복근,손석원,한광록,Jang, Dong-Wook,Sun, Bok-Keun,Sohn, Surg-Won,Han, Kwang-Rok 한국정보처리학회 2007 정보처리학회논문지B Vol.14 No.6

This study discusses the development of a u-Health care system that can detect quickly and cope actively with emergent situations of chronic disease patients who lead everyday life. If a patient's emergent situation is detected by personal health care host(PHCH), which is composed of acceleration and vibration sensors, GPS, and CDMA communication module, a text message on the patient's current location is transmitted to the hospital and the guardian's mobile terminal so that they can cope with the situation immediately. Especially, the system analyzes data from sensors by using neural network and determines emergent situations such as syncope and convulsion promptly. The exact location of patients can also be found in the electronic map by using GPS information. The experiments show that this system is very effective to find emergencies promptly for chronic disease patients who cannot take care of themselves and it is expected to save many lives. 본 논문은 만성질환을 갖고 있으면서도 일상생활을 하고 있는 환자들의 응급상황을 신속히 감지하여 능동적으로 대처할 수 있게 하는 u-Health 시스템의 개발에 관하여 기술한다. 기울기 및 진동 센서, GPS, CDMA 통신 모듈 등으로 구성된 PHCH(Personal Health Care Host) 장치에 의해 환자의 위급상황이 신속히 감지되면 현재 환자가 위치한 위치정보를 병원과 보호자의 모바일 단말기로 문자 전송하여 상황에 즉각 대처할 수 있도록 한다. 특히, 시스템은 신경회로망을 이용하여 센서로부터 수신되는 신호 데이터를 분석하고 기절 또는 발작 증상과 같은 응급상황을 신속히 판단한다. 또한 환자의 응급 상황시에 GPS 데이터를 이용하여 환자의 위치를 지도에서 확인할 수 있다. 일상생환을 하면서 항상 주의가 필요한 만성질환자에게 이 시스템을 적용시킴으로써 응급 상황에 신속히 대처하여 귀중한 생명을 구할 수 있을 것으로 기대된다.

상황인식 미들웨어를 위한 트랜스듀서 인터페이스 프로토콜 설계

장동욱(Dong-Wook Jang),손석원(Surg-Won Sohn),한광록(Kwang-Rok Han),선복근(Bok-Keun Sun) 한국컴퓨터정보학회 2011 韓國컴퓨터情報學會論文誌 Vol.16 No.9

사용자가 필요로 하는 서비스를 제공하기 위해서는, 일상생활 곳곳에 편재된 센서가 수집한 각종 환경 정보를 효율적으로 상호 공유하여 주변 상황을 인식하는 기술이 필요하다. 그러나 이를 위한 센서의 종류는 다양하고 각각의 센서는 고유의 특성과 서로 다른 방식으로 통신을 하기 때문에 센서의 활용에 제한이 있다. 이에 센서와 네트워크 계층과의 통신 프로토콜 표준화를 위한 IEEE 1451이 발표되었다. 그러나 IEEE 1451은 트랜스듀서(Transducer)의 표준화를 위한 프로토콜이므로 미들웨어에 접속되지 않는다. 본 논문에서는 XML을 이용하여 주변상황 정보를 얻기 위한 프로토콜을 정의함으로써 상황인식 미들웨어에 연결되는 트랜스듀서 인터페이스 및 응용 인터페이스 프로토콜을 제안한다. 그리고 서로 다른 센서와 응용 프로그램을 이용한 교량 건전성 감시 시스템과 철로 감시 시스템을 구현하고 제안한 인터페이스 프로토콜의 효용성을 확인하였다. Context awareness technologies are based on efficient sharing of environment information of ubiquitous sensors in everyday life, and users require this awareness technologies to get quality of services. However, the application has been restricted due to its varieties of sensors and many different methods of communications. Therefore, IEEE 1451 standard has been published to interface between sensors and network layer. But it does not connect to a middleware because IEEE 1451 is for transducer standards. This paper presents a transducer and application interface protocol which connect to the context-aware middleware by defining a protocol to obtain context information using XML. We have implemented a bridge health monitoring system and railroad monitoring system in which different sensors and users' application are used to prove the efficacy of proposed interface protocols.

질의어 기반의 유사도를 이용한 요약문 추출에 관한 연구

김민석(Min-Seok Kim),한광록(Kwang-Rok Han),선복근(Bok-Keun Sun),손석원(Surg-Won Sohn) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.2003 No.2