WSN에서 전파범위 기반의 저 전력 클러스터링 알고리즘

이충세,Rhee, Chung Sei 한국융합보안학회 2015 융합보안 논문지 Vol.15 No.3_2

최근 무선 센서 네트워크(WSN : Wireless Sensor Network)에서 센서노드의 에너지 소모 균등성과 효율성을 향상시켜 전제 네트워크의 수명을 최대화하기 위한 다양한 계층적 라우팅 프로토콜들이 제안되고 있다. 특히, 멀티홉기법이 향상된 에너지 효율성과 실제 적용 가능한 모델로 큰 각광받고 있다. 멀티-홉 기법에서는 센서 노드사이 거리에 따라 발송 에너지 능동조절 가능하다고 가정한다. 그러나 무선센서의 물리적 특성을 고려해보면 멀티-홉 기법의 이 가정은 현재 기술로 실제 실현하기 어렵다. 이 논문에서는 센서노드의 전파범위를 기반으로 에너지 효율성을 향상시킨 저 전력 클러스터링 기법을 제안한다. 제안기법은 에너지 효율적이고 기존기법보다 실제 무선센서네트워크에 적용하기 용이하다. Recently, lot of researches on multi-level protocol have been done to balance the sensor node energy consumption of WSN and to improve the node efficiency to extend the life of the entire network. Especially in multi-hop protocol, a variety of models have been studied to improve energy efficiency and apply it in real system. In multi-hop protocol, we assume that energy consumption can be adjusted based on the distance between the sensor nodes. However, according to the physical property of the actual WSN, it's hard to establish this. In this paper, we propose low-power sub-cluster protocol to improve the energy efficiency based on the spread of distance. Compared with the previous protocols, the proposed protocol is energy efficient and can be effectively used in the wireless sensing network.

서브 - 링의 신드롬 분석을 이용한 하이퍼큐브 진단 알고리즘

김학원(Hak-Won Kim),김동군(Dong-Kun Kim),최문석(Moon-Seok Choi),이충세(Chung-Sei Rhee) 한국정보과학회 2001 한국정보과학회 학술발표논문집 Vol.28 No.2Ⅰ

하이퍼큐브의 정규직이며 계층적인 구조적 특성은 효율적인 진단 알고리즘 개발에 유리하게 적용될 수 있다. Feng et al.의 HADA/IHADA와 Choi와 Rhee의 적응적 큐브 분할 방법은 하이퍼큐브의 전체 노드를 하나의 링으로 임베딩하여 링의 진단 특성을 이용하여 위하여 분할 및 정복 방법을 이용하였다. 또한 Kranakis와 Pelc는 결함을 모두 포함하는 최소의 서브링을 하나의 노드로 하는 하이퍼큐브의 형태로 분할하는 HYP-DIAG 알고리즘을 제안하였다. 또한 최악의 경우에, 테스트 수만을 고려하여 2ⁿ+3n/2의 테스트 수를 갖는 FAST-HYP-DIAG 알고리즘과 병렬 시간만을 고려하여 많아야 11테스트 라운드 이내에 진단을 수행하는 EXPRESS-HYP-DIAG 알고리즘을 제안하였다. 본 논문에서는 HYP-DIAG의 첫 번째 단계에서 얻어진 서브링들의 신드롬을 분석하여 테스트의 수와 테스트 라운드를 모두 고려하는 알고리즘을 제안한다.

PMC 진단모델의 적응 기법

이충세(Chung-Sei Rhee),구연설(Yeon-Selo Koo) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.12

시스템을 진단하는 방법으로 Adaptive 방법에 대한 연구가 많이 진행되고 있다. Hakimi, Schmeichel 그리고 Nakajima [4,6]는 이미 채택된 테스트 결과를 사용하는 종전의 진단 방법 대신에 앞에서 행한 테스트 결과에 따라 다음 테스트를 결정하는 적응 진단(adaptive test)방법을 제안하였다. Hakimi와 Nakajima [6]는 2t-1 이하의 적응 진단을 사용하여 결함이 아닌 장치를 발견하고 이 결함이 아닌 장치를 사용하여 n-1 진단후에 모든 결함장치를 발견하는 알고리즘, 즉 n+2t-2 진단을 사용하여 n개의 장치를 갖는 t 진단 시스템에서 모든 결함을 발견하는 알고리즘을 제안하였다. 위의 방법들은 한 장치(unit)가 다른 모든 장치들을 진단할 수 있다는 가정하에서 제안되었다. 그러나 일반적인 시스템하에서는 한 장치가 다른 모든 장치들을 진단할 수 없다. 이 논문에서는 Adaptive diagnosis 방법을 PMC 모델인 D(n,t,X) 시스템에 적용하는 방법과 알고리즘을 개발한다. Recently, researchers have begun studying adaptive approaches to the diagnosable system Hakimi et al. [4,6] assume that each unit is capable of testing every other units, with the tests being conducted one at a time in such a way that the choice of the next test to be performed depends on the results of the previous tests, rather than on a preselected pattern of test studied earlier. Hakimi and Nakajima [6] proposed an algorithm which identifies a fault-free unit after application of at most 2t-1 tests. Then they used the fault-free unit as a tester to identify all the fault units, thus using at most n+2t-2 tests to identify all the faulty units in a t diagnosable system with n units. But in general, it is not true in practice. To the best of our knowledge, there does not exist any result related to the adaptive diagnosis problem when the PMC model representation of the system is not a completely connected digraph. In this paper, we will investigate the application of adaptive diagnosis approach to a D(n,t,X) system which belongs to the PMC model.

t/k-진단 시스템을 사용한 하이퍼큐브 네트워크의 결함 진단

김창환,이충세,Kim, Jang-Hwan,Rhee, Chung-Sei 한국통신학회 2006 韓國通信學會論文誌 Vol.31 No.11C

시스템-레벨 진단 알고리즘은 결함의 개수가 t개를 초과하지 않는다는 t-진단가능 시스템의 특성을 이용한다. 기존의 진단 알고리즘으로 대형 멀티프로세서 시스템에서의 보다 많은 수의 결함을 처리하기에는 한계가 있다. Somani와 Peleg은 진단의 정확 여부를 판단할 수 없는 충분히 작은 개수의 노드가 존재한다는 것을 허용으로써 결함의 갯수가 t개를 초과할 경우에도 시스템을 진단하는 t/k-diagnosable 시스템을 제안하였다. 본 논문에서는 t/k-diagnosable 시스템을 이용한 적응적 방법에 의한 하이퍼큐브 진단 알고리즘을 제안한다. 결함의 개수가 t개를 초과하는 경우에 대하여, k개의 부정확한 진단을 허용한다. 성능 실험 결과 제안 알고리즘은 HADA알고리즘보다 우수함을 보여 주었다. 제안한 알고리즘은 RGC-Ring들의 신드롬을 분석하여 기존의 HADA/IHADA의 기법보다 테스트 라운드를 줄이는 보다 개선된 방법을 제안하였다. 또한 제안 알고리즘은 HYP-DIAG알고리즘과의 성능 비교에서도 유사한 결과를 보여 준다. System level diagnosis algorithms use the properties of t-diagnosable system where the maximum number of the faults does not exceed 1. The existing diagnosis algorithms have limit when dealing with large fault sets in large multiprocessor systems. Somani and Peleg proposed t/k-diagnosable system to diagnose more faults than t by allowing upper bounded few number of units to be diagnosed incorrectly. In this paper, we propose adaptive hypercube diagnosis algorithm using t/k-diagnosable system. When the number of faults exceeds t, we allow k faults to be diagnosed incorrectly. Simulation shows that the performance of the proposed algorithm is better than Feng's HADA algorithm. We propose new algorithm to reduce test rounds by analyzing the syndrome of RGC-ring obtained in the first step of HADA/IHADA method. The proposed algorithm also gives similar performance compared to HYP-DIAG algorithm.

유전체 상호간의 BLAST 최대 히트(best-hit)를 사용하여 서열화가 완성된 다수의 유전체로부터 Orthologous 단백질그룹을 자동적으로 클러스터링하는 기법

김선신,이충세,류근호,Kim Sun-Shin,Rhee Chung-Sei,Ryu Keun-Ho 한국정보처리학회 2006 정보처리학회논문지D Vol.13 No.2

서열화가 완성된 유전체의 수가 최근에 빠르게 상승하고 있지만, 상동성에 의한 단백질 기능을 예측하는 방법은 충분히 연구되고 있지 않다. 서열화가 완성된 다수의 유전체로부터 유전체 상호간의 BLAST 최대 히트(best-hit)를 사용하여 OPCs(Orthologous Protein Clusters)를 만드는 일은 성공적으로 연구되어 왔다. 그러나 OPCs를 수작업으로 구축하는 것은 시간과 노력이 많이 드는 일이다. 이 논문에서 우리는 서열화가 완성된 다수의 유전체로부터 OPs(Orthologous Proteins)를 클러스터링하는 자동화 방법을 제시하고, 해당 클러스터링의 타당성을 수학적으로 증명 한다. Though the number of completely sequenced genomes quickly grows in recent years, the methods to predict protein functions by homology from the genomes have not been used sufficiently. It has been a successful technique to construct an OPCs(Orthologous Protein Clusters) with the best reciprocal BLAST hits from multiple complete-genomes. But it takes time-consuming-processes to make the OPCs with manual work. We, here, propose an automatic method that clusters OPs(Orthologous Proteins) from multiple complete-genomes, which is, to be extended, based on INPARANOID which is an automatic program to detect OPs between two complete-genomes. We also Prove all possible clustering mathematically.

하이퍼큐브를 이용한 결함 허용 라우팅 알고리즘

최병환,강성수,이충세,Choi Byung-whan,Kang Sung-soo,Rhee Chung-sei 한국통신학회 2005 韓國通信學會論文誌 Vol.30 No.5C

하이퍼 큐브는 정규적이며 결함 허용 능력을 갖고 있기 때문에 결함 허용 알고리즘을 구현하기 쉽다. 하이퍼 큐브를 이용한 결함 허용 알고리즘들이 많이 개발되었다. 이러한 알고리즘들 중에 안전(safe)과 불안정(unsafe) 개념을 이용한 알고리즘이 Masuyama등에 의해 개발되었다. 이 논문에서는 Masuyama의 알고리즘을 개선한 새로운 알고리즘을 제안하고 시뮬레이션을 통하여 성능을 비교한다. Hypercube has a capability of fault-tolerance and regularity, which is easy to develop an algorithm. Many algorithms have been developed as an efficient fault-tolerance routing algorithm using hypercube. Among these algorithms, a method which use safe and unsafe concept was developed by Masuyama. Masuyama suggested an enhanced algorithm that take advantage of unsafe-safe concept. In this paper, we propose an algorithm that uses the unsafe, safe concept and modify Masuyama's algorithm. Using simulator we compare the performance of the proposed algorithm with existing algorithms.

M - Commerce 향상을 위한 전자화폐 공정 은닉 서명 시스템

이현주(Hyun Ju Lee),이충세(Chung Sei Rhee) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.2Ⅰ

무선 전자상거래(M-Commerce)는 이동 통신 네트워크 기술과 무선 단말기를 기반으로 하여 언제 어디서나 필요한 시점에서 행할 수 있는 상거래를 의미하며 이때, 전자지불 방식의 하나인 전자화폐는 실물 화폐와 유사한 성질을 만족해야 한다. 본 논문에서는 이산대수문제에 기반한 메타-메시지 복원과 은닉 서명 기법을 이용하여 전자화폐가 이중사용, 돈 세탁 그리고 불법 무기 구매 등 부정한 수단으로 악용되었을 때 신뢰센터가 사용자의 익명성을 제어하고 지불 금액을 다시 복원할 수 있는 알고리즘을 제안한다.

하이퍼큐브에서의 결함허용 라우팅 알고리즘

강성수 ( Sung-su Kang ),이충세 ( Chung-sei Rhee ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.2

하이퍼큐브을 이용한 많은 라우팅 알고리즘이 개발되어왔다. 이러한 알고리즘 중에서는 불안전(unsafe), 안전(safe) 노드를 이용한 알고리즘이 개발되었고, 이 알고리즘을 발전시킨 알고리즘들이 많이 출현하였다. 이 논문에서는 불안전, 안전개념을 개선하여 라우팅 실패가능성을 낮추고 우회횟수를 줄이는 알고리즘을 제안한다. 그리고 시뮬레이션을 통하여 성능을 비교한다.

적응적 큐브 분할을 이용한 하이퍼큐브 진단 알고리즘

최문옥(Moon-Ok Choi),이충세(Chung-Sei Rhee) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.4

본 논문에서는 하이퍼큐브 병렬시스템을 진단하기 위한 알고리즘으로써 적응적 큐브 분할 방법을 적용한 진단 알고리즘을 제안한다. Feng[1]등이 제안한 하이퍼큐브 진단 알고리즘은 이전의 연구결과에 비교하여 비교적 적은 진단 비용을 필요로 하는 반면 진단 알고리즘의 수행 중에 나타나는 큐브의 분할이 신드롬의 분석이 없이 정적인 방법을 사용하여 진단함으로써 불필요한 진단 오버헤드를 야기하였다. 본 논문에서는 이를 보완하기 위한 방법으로써 신드롬 분석을 통하여 진단비용을 줄일 수 있는 분할을 선택하는 적응적 큐브 분할방법을 제안한다. 또한 시뮬레이션을 통하여 Feng이 제안한 방법에 비하여 효율적인 성능을 나타내는 것을 보인다. In this paper, we propose a system-level diagnosis algorithm for hypercube mutiprocessors using adaptive cube partition method. Feng[1] proposed a diagnosis algorithm for hypercube multiprocessors which gives a better performance compared to previous researches[2, 3]. But cube partitions in Feng's algorithm are performed without syndrome analysis. Therfore unnecessery overhead is made during cube partitions. In this paper, we propose an adaptive cube partition method which gives better partition through syndrome analysis and reduces diagnosis cost. We give a simulation result for comparisons. We have found that our algorithm shows better performance compared to Feng's method.

유전자검색알고리즘을 이용한 예측모델의 성능 평가

권영탁(Young-Tak Kwon),이충세(Chung-Sei Rhee) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.2A

최근 인공지능분야에서는 보다 정확한 예측결과와 예측모델을 얻기 위한 학습방법 및 학습하고자하는 문제를 표현할 수 있는 구조(architecture) 개발에 대해 연구가 활발히 진행되고 있다. 본 논문에서는 복잡한 요인이 작용하는 예측문제를 해결하기 위하여 신경망(neural network)을 이용한 예측모델과 유전자검색알고리즘(genetic search algorithm)을 기반으로 하는 BP, TDNN, CATNN모델을 소개하고 성능을 비교 평가한다.