행위 기반 공격 탐지에서 감지 영역을 최대로 하는 감시 노드 선택

정균락(Kyun-Rak Chong) 한국컴퓨터정보학회 2016 한국컴퓨터정보학회논문지 Vol.21 No.1

In wireless sensor networks, sensors have capabilities of sensing and wireless communication, computing power and collect data such as sound, movement, vibration. Sensors need to communicate wirelessly to send their sensing data to other sensors or the base station and so they are vulnerable to many attacks like garbage packet injection that cannot be prevented by using traditional cryptographic mechanisms. To defend against such attacks, a behavior-based attack detection is used in which some specialized monitoring nodes overhear the communications of their neighbors(normal nodes) to detect illegitimate behaviors. It is desirable that the total sensing area of normal nodes covered by monitoring nodes is as large as possible. The previous researches have focused on selecting the monitoring nodes so as to maximize the number of normal nodes(node coverage), which does not guarantee that the area sensed by the selected normal nodes is maximized. In this study, we have developed an algorithm for selecting the monitoring nodes needed to cover the maximum sensing area. We also have compared experimentally the covered sensing areas computed by our algorithm and the node coverage algorithm.

캐쉬 효과를 고려한 확장된 Pairing Heap 알고리즘 (pp.250-257)

정균락(Kyun-Rak Chong),김경훈(Kyoung-Hoon Kim) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.5·6

빠른 프로세서 속도에 비해 메모리 접근(access)하는 시간이 상대적으로 느려짐에 따라, 대부분의 시스템은 격차를 줄이기 위하여 캐쉬(cache)라는 매우 빠른 메모리를 사용하고 있으며 캐쉬 메모리를 얼마나 효과적으로 사용하는 가 하는 문제는 알고리즘의 성능에 있어서도 결정적인 영향을 미치게 된다. 블록을 사용하는 방법은 캐쉬의 효율성을 향상시키는 방법으로 잘 알려져 있으며 행렬곱셈이나 d-heap과 같은 탐색트리에 사용되어 좋은 결과를 내고 있다. 그러나 삽입과 삭제 연산시 트리의 회전(rotation)이 필요한 자료구조에서는 블록을 사용하면 블록사이에 데이터의 이동이 필요해서 실행시간이 증가하게 된다. 본 논문에서는 블록을 사용하는 pairing heap에서 개선된 삽입과 삭제 알고리즘을 제안하였고 실험을 통해 우수성을 입증하였다. 또 블록을 사용하는 경우 여러 개의 데이터를 한 블록에 저장하므로 포인터의 개수가 줄어들게 되어 메모리를 적게 사용하게 된다. As the memory access time becomes slower relative to the fast processor speed, most systems use cache memory to reduce the gap. The cache performance has an increasingly large impact on the performance of algorithms. Blocking is the well known method to utilize cache and has shown good results in multiplying matrices and search trees like d-heap. But if we use blocking in the data structures which require rotation during insertion or deletion, the execution time increases as the data movements between blocks are necessary. In this paper, we have proposed the extended pairing heap algorithms using block node and shown by experiments that our structure is superior. Also in case of using block node, we use less memory space as the number of pointers decreases.

무선 센서 네트워크에서 행위 기반 공격 탐지를 위한 감시 노드의 연결성과 일반 노드의 커버리지 분석

정균락(Kyun-Rak Chong) 한국컴퓨터정보학회 2013 한국컴퓨터정보학회논문지 Vol.18 No.12

In wireless sensor networks, sensors need to communicate with each other to send their sensing data to the administration node and so they are susceptible to many attacks like garbage packet injection that cannot be prevented by using traditional cryptographic approaches. A behavior-based detection is used to defend against such attacks in which some specialized monitoring nodes overhear the communications of their neighbors to detect bad packets. As monitoring nodes use more energy, it is desirable to use the minimal number of monitoring nodes to cover the whole or maximal part of the network. The monitoring nodes can either be selected among the deployed normal nodes or differ in type from normal nodes. In this study, we have developed an algorithm for selecting the predefined number of monitoring nodes needed to cover the maximum number of normal nodes when the different types of normal nodes and monitoring nodes are deployed. We also have investigated experimentally how the number of monitoring nodes and their transmission range affect the connection ratio of the monitoring nodes and the coverage of the normal nodes.

Parallel Machine Scheduling Considering the Moving Time of Multiple Servers

Kyun-Rak Chong(정균락) 한국컴퓨터정보학회 2017 한국컴퓨터정보학회논문지 Vol.22 No.10

In this paper, we study the problem of parallel machine scheduling considering the moving time of multiple servers. The parallel machine scheduling is to assign jobs to parallel machines so that the total completion time(makespan) is minimized. Each job has a setup phase, a processing phase and a removal phase. A processing phase is performed by a parallel machine alone while a setup phase and a removal phase are performed by both a server and a parallel machine simultaneously. A server is needed to move to a parallel machine for a setup phase and a removal phase. But previous researches have been done under the assumption that the server moving time is zero. In this study we have proposed an efficient algorithm for the problem of parallel machine scheduling considering multiple server moving time. We also have investigated experimentally how the number of servers and the server moving time affect the total completion time.

모듈 방향 결정 문제 해결을 위한 정규화된 평균장 어닐링 알고리즘

정균락(Kyun Rak Chong) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.12

각 모듈들의 위치가 배치 알고리즘에 의해 결정된 후에도 모듈들을 종축 또는 횡축을 중심으로 뒤집거나 회전시킴으로써 회로의 효율성과 연결성을 향상시킬 수 있다. 고집적 회로설계의 한 단계인 모듈 방향 결정 문제는 모듈간에 연결된 선의 길이의 합이 최소가 되도록 각 모듈의 방향을 결정하는 문제이다. 최근에 평균장 어닐링 방법이 조합적 최적화 문제에 사용되어 좋은 결과를 보여 주고 있다. 평균장 어닐링은 신경회로망의 빠른 수렴 특성과 시뮬레이티드 어닐링의 우수한 해를 생성하는 특성이 결합된 방법이다. 본 논문에서는 정규화된 평균장 어닐링을 사용해서 모듈 방향 결정 문제를 해결하였고 실험을 통해 기존의 Hopfield 네트워크 방법과 시뮬레이티드 어닐링과 그 결과를 비교하였다. 시뮬레이티드 어닐링, 정규화된 평균장 어닐링과 Hopfield 네트워크의 총 길이 감소율은 각각 19.86%, 19.85%, 19.03%였으며, 정규화된 평균장 어닐링의 실행 시간은 Hopfield 네트워크보다는 1.1배, 시뮬레이티드 어닐링보다는 11.4배 정도 빨랐다. After modules are placed according to some placement algorithm, both circuit performance and routability can be improved while keeping the module placement fixed. Module orientation problem, an important step in VLSI design, is to determine the flip status of each module so as to minimize the total wire length. Recently the mean field annealing is used to solve combinatorial optimization problems. Mean field annealing exhibits the rapid convergence of the neural network while preserving the good solution afforded by simulated annealing. In this paper we applied the normalized mean field annealing algorithm to module orientation problem and compared the result with those of Hopfield network and simulated annealing experimentally. Simulated annealing, normalized mean field annealing and Hopfield network reduce the total wire length by 19.86%, 19.85%, and 19.03%, respectively. Mean field annealing runs 1.1 times and 11.4 times as fast as Hopfield network and simulated annealing, respectively.

케이블 TV 망에서 노드 선택을 위한 휴리스틱 연구

정균락(Kyun Rak Chong) 한국컴퓨터정보학회 2008 한국컴퓨터정보학회논문지 Vol.13 No.4

The cable TV network has delivered downward broadcasting signals from distribution centers to subscribers. Since the traditional coaxial cable has been upgraded by the Hybrid Fiber Coaxial(HFC) cable, the upward channels has expanded broadband services such as Internet. This upward channel is vulnerable to ingress noises. When the noises from the children nodes accumulated in an amplifier exceeds a certain level, that node has to be cut off to prevent the noise propagation. The node selection problem(NSP) is defined to select nodes so that the noise in each node does not exceed the given threshold value and the sum of profits of selected nodes can be maximized. The NSP has shown to be NP-hard. In this paper, we have proposed heuristics to find the near-optimal solution for NSP. The experimental results show that interval partitioning is better than greedy approach. Our heuristics can be used by the HFC network management system to provide privileged services to the premium subscribers on HFC networks.

공유 네트워크에서 공유대역폭 트리 구성을 위한 선형 시간 알고리즘

정균락(Kyun-Rak Chong) 한국컴퓨터정보학회 2012 한국컴퓨터정보학회논문지 Vol.17 No.6

In this paper we have proposed a linear time algorithm for solving the minimum sharable-bandwidth tree construction problem. The public-shared network is a user generated infrastructure on which a user can access the Internet and transfer data from any place via access points with sharable bandwidth. Recently, the idea of constructing the SVC video streaming delivery system on public-shared network has been proposed. To send video stream from the stream server to clients on public-shared network, a tree structure is constructed. The problem of constructing a tree structure to serve the video streaming requests by using minimum amount of sharable bandwidth has been shown to be NP-hard. The previously published algorithms for solving this problem are either unable to find solutions frequently or less efficient. The experimental results showed that our algorithm is excellent both in the success rate of finding solutions and in the quality of solutions.

공유 네트워크에서 최대 요구대역폭 트리 구축을 위한 효율적인 알고리즘

정균락(Kyun-Rak Chong) 한국컴퓨터정보학회 2015 한국컴퓨터정보학회논문지 Vol.20 No.4

Recently, an idea has been suggested in which members construct the network by sharing their surplus bandwidth of their own access point. This kind of network is called public-shared network. As an application, SVC video streaming delivery system on public-shared network has been proposed. To send video stream from the stream server to clients, a tree structure is constructed where the root is a stream server, internal nodes are sharable access points, and leafs are clients. The previous researches have focused on constructing the minimal sharable-bandwidth tree which can serve all video streaming requests using the minimal sharable bandwidth. In this paper, we have shown that the problem of constructing a tree structure with given sharable access points to serve maximal video streaming requests is NP-hard. We also have developed an efficient heuristic algorithm for this problem and evaluated experimentally our algorithm.

다중 서버를 사용하는 병렬 머신 스케줄링을 위한 효율적인 알고리즘

정균락(Kyun-Rak Chong) 한국컴퓨터정보학회 2014 한국컴퓨터정보학회논문지 Vol.19 No.6

The parallel machine scheduling is to schedule each job to exactly one parallel machine so that the total completion time is minimized. It is used in various manufacturing system areas such as steel industries, semiconductor manufacturing and plastic industries. Each job has a setup phase and a processing phase. A removal phase is needed in some application areas. A processing phase is performed by a parallel machine alone while a setup phase and a removal phase are performed by both a server and a parallel machine simultaneously. Most of previous researches used a single server and considered only a setup phase and a processing phase. If a single server is used for scheduling, the bottleneck in the server increases the total completion time. Even though the number of parallel machines is increased, the total completion time is not reduced significantly. In this paper, we have proposed an efficient algorithm for the parallel machine scheduling using multiple servers and considering setup, processing and removal phases. We also have investigated experimentally how the number of servers and the number of parallel machines affect the total completion time.

연결 지향 네트워크에서 최초 가용 구간을 찾는 효율적인 알고리즘

정균락(Kyun-Rak Chong) 한국컴퓨터정보학회 2010 한국컴퓨터정보학회논문지 Vol.15 No.3

The advancement of communication and networking technologies has enabled e-science and commercial application that often require the transport of large volume of data over wide-area network. Schedulable high-bandwidth low-latency connectivity is required to transport the large volume of data. But the public Internet does not provide predictable service performance. Especially, if data providers and users are far away, dedicated bandwidth channels are needed to support remote process efficiently. Currently several network research projects are in progress to develop dedicated connectionsy sA bandwidth scheduler computes an user requested path based on network topology information and link bandwidth allocationsy In this paper, we have proposed an efficient algorithm for finding the earliest time interval when minimum bandwidth and duration are giveny Our algorithm is experimentally compared with the known algorithm.