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

鄭均樂 弘益大學校 科學技術硏究所 2007 科學技術硏究論文集 Vol.18 No.-

The CATV network has traditionally delivered downward broadcasting signals from distribution centers to subscribers. Recently, the increased utilization of upward channels has expanded broadband services such as Internet and telephone services. This upward channel is vulnerable to ingress noises. When the noises from the children nodes accumulated in an amplifier exceeds a certain level, the signal can no longer be separated from the noise. In this case, the node has to be cut off to prevent the noise from propagating further. When each node has some profit value, the node selection problem(NSP) is to select nodes so that the noise in each node does not exceed the given threshold value and the sum of those profits can be maximized. The NSP has shown to be NP-hard. Thus if the number of nodes on the network is large, it is impossible to find the optimal solution as the execution time for finding the optimal solution grows exponentially. In this paper, we have proposed greedy heuristics to find the near-optimal solution for NSP and has shown experimental results.

[特輯]최적화 문제에서 그래프의 응용

정균락 한국정보과학회 1992 정보과학회지 Vol.10 No.6

VCG에서 사이클 최소화를 위한 모듈의 방향에 관한 연구

鄭均樂 弘益大學校 科學技術硏究所 1991 科學技術硏究論文集 Vol.1 No.-

The routability of a given placement of modules can be improved by flipping some or all of modules. A routing channel typically consists of a rectangular space between two parallel rows of terminals. Each module has a set of nets and can be flipped about its vertical axis. A vertical constraint graph(VCG) is associated with an assignment of nets to terminals. Many channel routing algorithms require the VCG acyclic. When modules can be flipped, two interesting problem arise : by flipping modules 1) can we get and acyclic VCG? 2) can we get a VCG with minimunm number of vertices in cycles?. In this paper, we show that these problems are NP-hard and develope heuristics.

FPGA에서 테크놀로지 매핑에 관한 연구

鄭均樂 弘益大學校 科學技術硏究所 1994 科學技術硏究論文集 Vol.5 No.-

In this paper, we study the technology mapping of a lookup-table-based field programmable gate arrays and analyze conventional techniques. For an effective technology mapping, logic optimization is preprocessed like the conventional gate arrays. The main goal is to minimize either the total number of LUTs for an area optimization or the number of levels of LUTs for a delay optimization. Our mapping algorithm consists of three parts. First, the decomposition algorithm transforms an original network into a two-input network. Second, the labeling algorithm determines each node's level for a delay optimization. Finally, the LUT mapping algorithm generates the logically equivalent network of K-LUTs.

무선 센서 네트워크에서 행위 기반 공격 탐지와 보고 문제를 위한 개선된 최단 경로 트리를 사용하는 알고리즘

정균락 한국정보과학회 2012 정보과학회논문지 : 정보통신 Vol.39 No.4

무선 센서 네트워크에서 센서들은 서로 교신하며 일을 해야 하므로 전통적인 인증이나 암호화 방식만으로는 네트워크 공격을 막기가 어렵다. 이러한 공격을 막기 위해 보통 사용하는 기법이 행위 기반 탐지인데 특별한 감시 노드들이 이웃 노드들이 합법적인지를 알기 위해 이웃의 교신을 감청한다. 행위 기반 공격 탐지와 보고 문제는 감시 노드들의 수를 제한하면서 커버되는 노드들의 수가 최대가 되게 연결된 감시 노드들의 집합을 구하는 문제이다. 최근에 이 문제가 NP-하드임이 증명되었으며, 최단 경로 트리를 사용하는 휴리스틱이 발표되었는데 간선에 비용을 할당할 때 일부 노드가 중복해서 계산되고, 최단 경로 트리를 선택할 때 초기 노드 커버리지만 고려하는 단점을 가지고 있다. 본 연구에서는 개선된 최단 경로 트리를 사용하는 알고리즘들을 제안하고 기존의 방법과 실험을 통해 비교하였는데, 간선의 비용 할당 방법만을 개선한 알고리즘은 기존의 알고리즘에 비해 노드 커버리지가 2.5% 향상되었고, 간선의 비용 할당과 최단 경로 선택 방법을 모두 개선한 알고리즘은 노드 커버리지가 40.5% 향상되었다. Due to the cooperative characteristic of WSNs, sensors are susceptible to many attacks that cannot be defeated by using traditional cryptographic mechanism of authentication or encryption alone. A commonly used approach for defending against such attacks is behavior-based detection in which some specialized monitoring nodes overhear communication in the neighborhood to determine if the neighbor's behavior is legitimate. The behavior-based attack detection and reporting problem is defined to find a set of connected monitoring nodes such that the number of covered nodes is maximized subject to constraining the total number of monitoring nodes to be no more than a predefined value. Recently, this problem has been shown to be NP-hard and a shortest path tree-based algorithm has been proposed. The drawbacks of this algorithm is that it counts some nodes twice during the edge cost assignment and considers only the initial node coverage information when selecting the shortest path tress. In this paper, we have proposed two improved shortest path tree-based algorithms and compared experimentally our algorithms with the known algorithm. The algorithm using the proposed edge cost assignment performed 2.5% better and the algorithm with both the proposed edge cost assignment and the shortest path tree selection performed 40.5% better.

고집적회로 설계에서 최적의 플로어플랜을 위한 효율적인 Branch-and-Bound 방법

鄭均樂 弘益大學校 科學技術硏究所 1993 科學技術硏究論文集 Vol.3 No.-

The floorplan of a VLSI chip is comprised of several building blocks. Each of these may have several possible realizations with each realization having different dimensions. To realize a VLSI chip, one has to select a realization for each of its building blocks. This selection together with the floorplan determine the overall dimensions of the chip. For nonslicing floorplans, branch-and-bound can be used to get an optimal(minimum area) solution. Both the block order and dimension order affect the number of nodes in the state space tree that are actually expanded during a branch-and-bound search. In this paper, we suggest the best combination of block ordering and dimension ordering for efficient branch-and-bound algorithm.

캐쉬 효과를 고려한 확장된 Pairing Heap 알고리즘

정균락,김경훈 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.5

빠른 프로세서 속도에 비해 메모리 접근(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.

POPS 네트워크 구조에서의 Bitonic 정렬 알고리즘에 관한 연구

鄭均樂,宋命根 弘益大學校 科學技術硏究所 2001 科學技術硏究論文集 Vol.12 No.-

The partitioned optical passive stars network (POPS) is an optical interconnection network for a multiprocessor computer. It uses multiple OPS couplers which can receive an optical signal from any one of its source nodes and transmit the received signal to all of its destination nodes. A message can be sent from one processor to the other in a single slot. A POPS(d, g) network partitions the n processors into g groups of size d and the choice of g and d affects the interconnection cost and the bandwidth. Sorting is one of the most important operations performed by a computer and many parallel sorting algorithms have been investigated for various parallel computer architectures. In this paper, we have studied how to implement efficiently the bitonic sort on a POPS network.

스트링 탐색을 위한 효율적인 자료구조에 관한 연구

鄭均樂 弘益大學校 科學技術硏究所 1994 科學技術硏究論文集 Vol.4 No.-

Suppose we construct a computer dictionary. The words in the dictionay need to be stored in some data structure for frequent searches. Since the amount of storage required is very huge and words are searched very often, that structure must occupy less storage and provide fast searches. In the paper, we propose an efficient data structure for storing strings. This structure can be used for storing dictionary words and circuit paths.

캐쉬 효과를 고려한 확장된 Pairing Heap 알고리즘

정균락,김경훈 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.6

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. 빠른 프로세서 속도에 비해 메모리 접근(access)하는 시간이 상대적으로 느려짐에 따라, 대부분의 시스템은 격차를 줄이기 위하여 캐쉬(cache)라는 매우 빠른 메모리를 사용하고 있으며 캐쉬 메모리를 얼마나 효과적으로 사용하는 가 하는 문제는 알고리즘의 성능에 있어서도 결정적인 영향을 미치게 된다. 블록을 사용하는 방법은 캐쉬의 효율성을 향상시키는 방법으로 잘 알려져 있으며 행렬곱셈이나 d-heap과 같은 탐색트리에 사용되어 좋은 결과를 내고 있다. 그러나 삽입과 삭제 연산시 트리의 회전(rotation)이 필요한 자료구조에서는 블록을 사용하면 블록사이에 데이터의 이동이 필요해서 실행시간이 증가하게 된다. 본 논문에서는 블록을 사용하는 pairing heap에서 개선된 삽입과 삭제 알고리즘을 제안하였고 실험을 통해 우수성을 입증하였다. 또 블록을 사용하는 경우 여러 개의 데이터를 한 블록에 저장하므로 포인터의 개수가 줄어들게 되어 메모리를 적게 사용하게 된다.