소출력 라디오 방송의 주파수 할당

손석원(Surgwon Sohn) 호서대학교 공업기술연구소 2007 공업기술연구 논문집 Vol.26 No.1

We present a constraint satisfaction problem modeling and algorithms to solve a frequency assignment problem for low power FM broadcasting. Our research objective is to find a frequency assignment that satisfies all the constraints using minimum number of frequencies while maximizing the number of radio stations served for a given area. To get a good suboptimal solution, some variable ordering heuristics such as Dsatur variable ordering and most-used value ordering rule are provided. They enforce the backtracking process in a constraint satisfaction proDlem,so both the search space and computing time are greatly reduced. A lot of outstanding work on graph coloring problems has been achieved, and the theoretical lower bound of the chromatic number of random graph is one of them. Comparison between the theoretical lower bound and our computed approximate solution has been made for evaluation of proposed algorithm.

공동체 라디오 방송을 위한 주파수 할당의 최적화

손석원(Surgwon Sohn),한광록(Kwang-Rok Han) 한국컴퓨터정보학회 2008 韓國컴퓨터情報學會論文誌 Vol.13 No.2

본 논문에서는 주파수 할당의 최적화를 위하여 제약만족문제의 모델링과 백트랙킹 탐색의 경험적 알고리즘을 제안한다. 연구의 목적은 주어진 서비스 영역에서 공동체 라디오 방송국의 개수를 최대화 하면서 동시에 필요 주피수를 최소화시키는 제약조건을 만족하는 주파수 할당이다. 본 연구는 효과적으로 해를 찾기 위하여 경험적 알고리즘을 제안하는데, 이것은 제한된 시간 안에 해를 찾는데 필요한 백트랙킹 횟수를 최소화하는 변수 순서와 값 순서에 관한 방법이다. 백트랙킹에서 불일치성을 늦게 발견하는 문제를 보완하기 위해서 일관성 강화기술 또는 제약 전파 방법을 사용한다. 백트랙킹 탐색과 일관성 강화 기술을 함께 사용함으로써 제약만족문제에 관한 보다 강력하고 효과적인 알고리즘을 얻을 수 있다. 본 논문은 또한 계산된 해와 이론적인 하한 값을 비교함으로써 제안된 알고리즘의 성능 비교를 수행한다. We present a modeling of constraint satisfaction problems and provide heuristic algorithms of backtracking search to optimize the frequency assignment. Our research objective is to find a frequency assignment that satisfies all the constraints using minimum number of frequencies while maximizing the number of community radio stations served for a given area. In order to get a effective solution, some ordering heuristics such as variable orderings and value orderings are provided to minimize the backtracking in finding all solutions within a limited time. To complement the late detection of inconsistency in the backtracking, we provide the consistency enforcing technique or constraint propagation to eliminate the values that are inconsistent with some constraints. By integrating backtracking search algorithms with consistency enforcing techniques, it is possible to obtain more powerful and effective algorithms of constraint satisfaction problems. We also provide the performance evaluation of proposed algorithms by comparing the theoretical lower bound and our computed solution.

Heuristic Backtrack Search Algorithm for Energy-efficient Clustering in Wireless Sensor Networks

손석원(Surgwon Sohn) 한국컴퓨터정보학회 2008 韓國컴퓨터情報學會論文誌 Vol.13 No.5

제약만족문제(Constraint Satisfaction Problem)의 연구에서 밝혀졌듯이, 제약최적화 문제(Constraint Optimization Problem)를 효율적으로 풀기 위해서는 변수 순서화의 경험적 방법이 매우 중요하다. 이기종이 혼합된 무선 센서 네트웍의 에너지 효율적인 집단화같은 문제는 클러스터 헤드가 기지국에 가깝게 위치하려는 경향이 있다. 본 논문은 이 집단화 문제를 풀기 위해서 정적 우선순위 변수 순서화에 기반을 둔 새로운 접근방법을 제시하고, pnode 라는 새로운 알고리즘을 제안한다. 이 pnode 알고리즘은 우선순위가 가장 높은 변수를 다음 변수로 선택한다. 집단화 문제에 있어서, 우선순위가 높다는 것은 클러스터 헤드가 최적지역에 근접하게 된다는 것을 의미하며 이것은 문제의 성격상 미리 정해진다. 클러스터화된 센서 네트웍에서 클러스터 헤드는 에너지 소비가 가장 많이 일어나는 곳이기 때문에, 센서 노드뿐만 아니라 클러스터 헤드에서 발생하는 최대 에너지 소비를 최소화하도록 만드는 방법을 찾는 것이 본 논문의 목적이다. pnode 알고리즘을 사용하여 시뮬레이션 한 결과 제안된 방법이 다른 방법들보다 우수함을 알 수 있었다. As found in research on constraint satisfaction problems, the choice of variable ordering heuristics is crucial for effective solving of constraint optimization problems. For the special problems such as energy-efficient clustering in heterogeneous wireless sensor networks, in which cluster heads have an inclination to be near a base station, we propose a new approach based on the static preferences variable orderings and provide a pnode heuristic algorithm for a specific application. The pnode algorithm selects the next variable with the highest preference. In our problem, the preference becomes higher when the cluster heads are closer to the optimal region, which can be obtained a priori due to the characteristic of the problem. Since cluster heads are the most dominant sources of power consumption in the cluster-based sensor networks, we seek to minimize energy consumption by minimizing the maximum energy dissipation at each cluster heads as well as sensor nodes. Simulation results indicate that the proposed approach is more efficient than other methods for solving constraint optimization problems with static preferences.

밀집리더환경에서 RFID 리더를 위한 채널 할당

손석원(Surgwon Sohn) 한국컴퓨터정보학회 2013 韓國컴퓨터情報學會論文誌 Vol.18 No.2

RFID 시스템에서 리더간 간섭은 일정한 서비스 영역에서 제한된 주파수를 사용하기 때문에 발생하며 수동형 태그의 가독율을 떨어뜨리는 주요 원인이 된다. 그러므로 제한된 주파수 자원 환경에서 가독율을 최대화하려면 리더간 주파수 간섭을 최소화시켜야 한다. 본 논문에서는 RFID 리더간 주파수 간섭 최소화 문제를 FDM/TDM 혼합방식의 제약만족문제로 모델링하고 기존의 백트래킹 탐색 알고리즘을 적용하여 각각의 리더에게 최적의 채널을 할당한다. 제약 만족 문제의 해를 구하기 위해서 백트래킹을 이용한 깊이우선탐색을 실행하는데 이 때 탐색되는 노드의 순서를 효과적으로 배열하는 변수 순서화 방법이 중요하다. 본 논문의 실험에서 적용된 변수 순서화 알고리즘들은 그래프 채색에 효과적인 것으로 알려져 있다. 제안한 제약만족문제 모델의 성능을 입증하기 위하여 수동형 UHF RFID 시스템 환경에서 시뮬레이션하여 간섭조건을 만족하면서 각각의 리더에게 최적의 채널을 할당한다. Reader-to-reader interference in RFID system is occurred due to the use of limited number of frequencies, and this is the main cause of read rate reduction in the passive RFID tags. Therefore, in order to maximize the read rate under the circumstances of limited frequency resources, it is necessary to minimize the frequency interference among RFID readers. This paper presents a hybrid FDM/TDM constraint satisfaction problem models for frequency interference minimization problems of the RFID readers, and assigns optimal channels to each readers using conventional backtracking search algorithms. A depth first search based on backtracking are accomplished to find solutions of constraint satisfaction problems. At this moment, a variable ordering algorithm is very important to find a solution quickly. Variable ordering algorithms applied in the experiment are known as efficient in the graph coloring. To justify the performance of the proposed constraint satisfaction problem model, optimal channels for each readers in the passive UHF RFID system are allocated by using computer simulation satisfying various interference constraints.

고정밀 가속도 센서를 이용한 휴대용 진동 데이터 수집 시스템 개발

김수희 ( Suhee Kim ),손석원 ( Surgwon Sohn ),송원길 ( Wongil Song ),이현준 ( Hyunjun Lee ),우경민 ( Kyungmin Woo ),손홍성 ( Hongsung Sohn ),안계홍 ( Gyehong An ) 한국정보처리학회 2014 한국정보처리학회 학술대회논문집 Vol.21 No.1

구조적인 한계로 인해 전통적인 진동 측정 시스템의 구축이 곤란할 경우나, 고가의 데이터 수집 시스템을 사용하기가 어려운 상황에 대비하여, 언제 어디서나 용이하게 진동 데이터를 측정하기 위해 휴대용 무선 측정 시스템을 개발한다. 이 연구를 통해 개발한 시스템을 기반으로 기능들을 업그레이드하면 철로 주변의 진동 환경 평가 등을 포함한 다양한 분야에 사용될 수 있으며, 근/원거리 진동 데이터 무선 모니터링 시스템의 개발에 적용될 수 있다.

무선 센서 네트워크에서의 개선된 시각 동기화 구현

방상원(Sangwon Bang),손석원(Surgwon Sohn) 한국컴퓨터정보학회 2013 한국컴퓨터정보학회 학술발표논문집 Vol.21 No.2

본 논문은 TPSN 알고리즘의 시각 동기화 오차를 개선하기 위하여 Imote2 센서 노드의 클럭 드리프트 특성을 적용하는 개선된 TPSN 알고리즘을 제안한다. 클럭 드리프트의 원인은 주로 수정발진기에 기인한다. 본 연구에서는 온도 및 습도 등 환경 조건이 비슷할 경우에 드리프트가 크게 차이나지 않는다는 실험 결과에 따라 드리프트의 평균값을 구하고 이를 TPSN 동기화 오차 보정에 사용한다. 이때 적용되는 드리프트 특성 값은 센서 노드 설치 이전에 미리 측정하여야 한다. 실험을 통하여 본 논문에서 제안한 개선된 TPSN 알고리즘이 동기화 오차 개선에 효과적임을 확인하였다.

트레이딩 플랫폼의 네트워크 지연 비교 연구

박지영 ( Jiyoung Park ),손석원 ( Surgwon Sohn ) 한국정보처리학회 2019 한국정보처리학회 학술대회논문집 Vol.26 No.1

Windows 환경에서 상용 저지연 NIC를 이용하여 컴퓨터 네트워크 통신 지연을 감소시킬 수 있다. 일반적으로 시스템의 커널에서 네트워크 처리를 담당하지만 본 논문은 커널을 우회하여 NIC에서 처리하여 운영체제에서 발생하는 지연을 최소화한다. 상용 NIC과 광섬유 케이블을 사용하여 네트워크 지연에 대한 비교결과를 보이며 네트워크 저지연 시스템의 구성을 제시한다.

열차용 블랙박스 분석 도구 설계

김정빈 ( Jeong-bin Kim ),장동욱 ( Dong-wook Jang ),김광렬 ( Kwnag Ryul Kim ),한광록 ( Kwang-rok Han ),손석원 ( Surgwon Sohn ) 한국정보처리학회 2009 한국정보처리학회 학술대회논문집 Vol.16 No.1

최근 철도의 고속화, 자동화됨에 따라 철도 사고 역시 항공기 사고처럼 대형화 되고 인명피해 역시 매우 커지고 있다. 따라서 사고 발생시 사고원인을 신속하고 정확하게 분석하기 위해 철도 차량에 블랙박스의 설치를 법제화 하고 있고, 이에 대한 연구를 진행하고 있다. 사고의 정확한 판단을 위해서 블랙박스에 기록된 데이터를 분석하하는 분석 소프트웨어를 개발하였다. 본 논문의 블랙박스 분석 소프트웨어는 신속하고 정확하게 사고 원인을 규명할 수 있고, 구간별 운행 패턴과 기관사의 습관등을 파악할 수 있어, 운행을 개선 할 수 있어 사고를 미연에 방지 할 것으로 기대한다.