기존 관로를 고려한 광통신망의 최적 설계를 위한 효과적인 휴리스틱에 관한 연구

한치근(C.G Han),조성준(S.Z.Cho),정학영(H.Y Chung),조성원(S.W. Cho),김형석(H.S. Kim),이태주(T.J. Lee),박종철(J.C. Park),정태일(T.L. Jung),이재영(J.Y. Lee) 한국정보과학회 1995 한국정보과학회 학술발표논문집 Vol.22 No.1

일부 망의 손실이나 고장에도 전체 망 서비스가 가능하도록 망의 설계를 고려하는 문제를 망의 생존도 문제라고 한다. 광케이블 망을 구축할 경우, 최소의 경비로, 동시에 생존도 문제를 해결하는 설계 방법이 필요하다. 또한, 관로(Conduit)가 이미 있을 경우에 기존 관로를 고려하여 최소의 경비로 생존도를 해결하는 방안이 요구된다. 본 논문에서는 기존 관로가 있는 경우의 문제를 해결할 수 있는 휴리스틱을 설명한다.

실험계산을 통한 에지 한 개 추가에 따른 그래프의 중심성 및 순위 변화 분석

한치근 ( Chi-geun Han ),이상훈 ( Sang-hoon Lee ) 한국인터넷정보학회 2015 인터넷정보학회논문지 Vol.16 No.5

그래프에서 각 노드에 대해 그래프 내의 중요도를 나타내는 중심성(centrality)을 계산할 수 있고, 그 값에 따라 각 노드는 중요도 순위(ranking)를 갖는다. 중심성을 나타내는 방법으로는 여러 척도가 있는데, 본 연구에서는 연결도(degree) 중심성, 밀접도(closeness) 중심성, 특성벡터(eigenvector) 중심성, betweenness 중심성에 국한하여 연구를 수행하였다. 본 연구는 그래프에서 에지를 하나 추가할 경우, 그래프 내 노드 전체에 미치는 노드의 중심성 및 순위의 변화를 실험계산을 통해 확인한다. 그리고, 추가되는 에지가 노드 전체의 중심성 및 순위에 미치는 영향은 그래프의 형태에 따라 달라진다는 것을 PCA(Principal Component Analysis)를 통해 밝혔다. 이 사실은 그래프의 구조적 특성을 구분하는 방법으로도 사용될 수 있다. The centrality is calculated to describe the importance of a node in a graph and ranking is given according to the centrality for each node. There are many centrality measures and we use degree centrality, closeness centrality, eigenvector centrality, and betweenness centrality. In this paper, we analyze the effect of an additional edge of a graph on centrality and ranking through experimental computations. It is found that the effect of an additional edge on centrality and ranking of the nodes in the graph is different according to the graph structure using PCA. The results can be used for define the graph characteristics.

대규모 계산 공학 문제를 위한 내부점 알고리즘의 응용

한치근(Chi-Geun Han) 한국정보과학회 1993 정보과학회논문지 Vol.20 No.8

이 논문에서는 공학 분야에서 발견되는 옵스터클 문제와 일레스틱-플레스틱 토션 문제를 풀기 위한 다항 함수시간의 내부점 알고리즘의 응용을 설명한다. n이 변수의 갯수, L이 문제의 크기일 때 응용된 내부점 알고리즘의 복잡도는 O(n^(35)L)로 주어진다. IBM 3090-600S 상에서 49만개의 변수를 갖고 있는 문제까지 풀어 얻어진 결과로 제안된 알고리즘의 최종해가 충분한 정확도를 갖고 있음을 알 수 있다. 얻어진 해들을 컴퓨터 그래픽으로 표현한 그림들은 모든 변수들이 최종해를 향하여 동시에 움직이고 있음을 보여주고 있다. We apply a polynomial time interior-point algorithm for solving some large-scale engineering problems such as obstacle problems and elastic-plastic torsion problems. The time complexity of the algorithm is O(n^(35)L) when n is the number of variables and L is the size of the input data of the problem. Computational results obtained by solving problems up to half a million variables on IBM 3090-600S show that the final solutions have sufficient accuracy. Graphical representation of the solutions shows that the algorithm finds a sequence of solutions where all variables are moving to the optimum simultaneously.

교통망의 강건성 민감도를 이용한 특정 구간의 정체에 의한 파급효과 분석

한치근(Chi-Geun Han),이성근(Sung-Geun Lee) 한국컴퓨터정보학회 2023 韓國컴퓨터情報學會論文誌 Vol.28 No.4

본 연구는 특정 구간의 정체가 전체 고속도로에 미치는 영향을 분석하기 위한 고속도로 망의 강건성 민감도 지수(RSI: robustness sensitivity index)를 제안한다. 새로 제안된 RSI는 특정 구간의 길이가 연장되었을 때, 연장된 단위 길이 당 교통망의 총 운행거리 변화량으로 정의한다. RSI 값이 클 경우, 해당 구간의 교통 정체는 다른 구간에 비해 전체 망에 나쁜 영향을 미치게 된다. 기존의 망 강건성 지수(NRI: network robustness index)는 단순히 특정 구간이 있을 때와 없을 때의 교통망 변화를 관찰하지만, 본 연구가 제안한 RSI는 일종의 성능 지표로 특정 구간의 정체 정도에 따른 망 전체의 파급효과를 정량적으로 분석할 수 있게 해준다. 특정 구간의 정체 정도를 변화시키면서, 그 정체가 발생시키는 다른 구간들의 교통량 증가, 감소, 정체 구간의 크기 및 위치 등이 어떻게 변화하는지를 계산할 수 있다. 이 분석은 NRI로는 분석 불가능한 것으로 RSI의 우수성을 입증하는 것이다. 국내 고속도로 망의 데이터를 이용해 RSI의 다양한 성질을 분석한다. 그리고 RSI 개념을 이용하면 특정 구간의 정체 정도 변화가 발생시키는 다른 구간들에 대한 파급효과를 분석할 수 있음을 보인다. In this paper, we propose a robustness sensitivity index (RSI) of highway networks to analyze the effect of congestion in a specific section on the entire highway. The newly proposed RSI is defined as the change in the total mileage of the transportation network per extended unit length when the length of a particular section is extended. When the RSI value is large, traffic congestion in the section has a worse effect on the entire network than in other sections. The existing network robustness index (NRI) simply observes changes in transportation networks with and without specific sections, but the RSI proposed in this study is a kind of performance indicator that allows quantitative analysis of the ripple effect of the entire network according to the degree of congestion in a specific section. While changing the degree of congestion in a particular section, it is possible to calculate how the traffic volume increases, decreases, and the size and location of the congestion section change. This analysis proves the superiority of RSI as it cannot be analyzed with NRI. Various properties of RSI are analyzed using data from the domestic highway network. In addition, using the RSI concept, it is shown that the ripple effect on other sections in which a change in the degree of congestion of a specific section occurs can be analyzed.

에지 한 개 추가에 따른 그래프의 고유벡터 중심성 변화 분석

한치근(Chi-Geun Han),이상훈(Sang-Hoon Lee) 한국컴퓨터정보학회 2016 韓國컴퓨터情報學會論文誌 Vol.21 No.1

There are many methods to describe the importance of a node, centrality, in a graph. In this paper, we focus on the eigenvector centrality. In this paper, an analytical method to estimate the difference of centrality with an additional edge in a graph is proposed. In order to validate the analytical method to estimate the centrality, two problems, to decide an additional edge that maximizes the difference of all centralities of all nodes in the graph and to decide an additional edge that maximizes the centrality of a specific node, are solved using three kinds of random graphs and the results of the estimated edge and observed edge are compared. Though the estimated centrality difference is slightly different from the observed real centrality in some cases, it is shown that the proposed method is effective to estimate the centrality difference with a short running time.

대규모 네트워크에서 Modularity를 이용한 향상된 커뮤니티 추출 알고리즘

한치근 ( Chi-geun Han ),조무형 ( Moo-hyoung Jo ) 한국인터넷정보학회 2012 인터넷정보학회논문지 Vol.13 No.3

본 논문에서는 modularity를 기반으로 한 향상된 커뮤니티 추출 알고리즘을 제안한다. 기존의 알고리즘은 modularity 값을 증가시키는 커뮤니티를 구축할 때 노드가 갖고 있는 정보를 고려하지 않음으로써, 계산을 비효율적으로 반복하여 수행한다. 제안하는 알고리즘은 노드의 degree(weight)를 계산하고 그것을 내림차순으로 정렬하고, 정렬된 순서대로 modularity 값의 증가여부를 확인함으로써, 반복되는 계산과정을 줄여 기존의 알고리즘보다 빠르게 최종 결과를 도출해낸다. 실험계산을 통해 제안하는 알고리즘이 더 짧은 시간 내에, 기존알고리즘이 구한 modularity 값보다 같거나, 향상된 값을 찾는다는 것을 보인다. In this paper, an improved community detection algorithm based on the modularity is proposed. The existing algorithm does not consider the information that the nodes have in checking the possible modularity increase, hence the computation may be inefficient. The proposed algorithm computes the node degree (weight) and sorts them in non-increasing order. By checking the possible modularity value increase for the nodes in the nonincreasing order of node weights, the algorithm finds the final solution more quickly than the existing algorithm does. Through the computational experiments, it is shown that the proposed algorithm finds a modularity as good as the existing algorithm obtains.

홉제한이 있는 멀티캐스팅 알고리즘의 연구

이성근(Sunggeun Han),한치근(ChiGeun Han) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.2Ⅰ

통신망의 발전으로 사용자는 새로운 인터넷 서비스를 요구하게 되었다. 이러한 서비스의 대부분은 멀티 캐스팅을 사용하며, 전송되는 데이터는 대용량의 멀티미디어 데이터가 주를 이루고 있다. 멀티미디어 서비스는 일정한 수준의 서비스를 위하여 신뢰도를 보장해야만 한다. 신뢰도는 경로의 흡수와 관련되어 있다. 즉, 경로에 포함된 홉의 수가 많아지면 그 경로를 통한 서비스의 신뢰도는 떨어지게 된다. 이러한 이유로 전송에 관련된 경로의 흡수에 제한을 두는 것은 통신의 신뢰성을 위하여 고려되어져야하는 중요한 문제이다. 본 논문에서는 멀티캐스트 트리의 각 경로의 흡수와 비용의 관계를 알아보기 위해 유전자 알고리즘과 개미 알고리즘을 사용한다.

관로가 있는 생존가능망 설계에 관한 효율적인 알고리즘 연구

강효관,한치근,Kang, Hyo-Kwan,Han, Chi-Geun 한국정보처리학회 2001 정보처리학회논문지 C : 정보통신,정보보안 Vol.8 No.5

Network is changed from voice-based network into multimedia-based network by development of communication technology and multimedia service. We need a large bandwidth for multimedia service. The optical fiber is a more suitable medium than existing copper-based cable for large bandwidth. But, it is so expensive than copper-based cable. So, Minimizing total cost becomes a more important concept. In order to construct a minimum cost network, we have to consider existing conduits in network. On the other hand, optical fiber network allows that larger amount of traffic can be transmitted than copper-based network does. However, a failure of a node or link can make a serious damage to the network service. Thus, we have to get multiple paths to support continuous service even if a loss of failure occurs in some point of the network. The network survivability problem is to design the network that can provide reliable service to customers anytime with minimum total cost. In an existing solution of the network survivability problem with conduits, a conduit is considered only one time. But, the conduit is reusable if the network satisfies the required survivability. Proposed algorithm can more effectively considered already existed conduit. Network survivability and edge cost is predetermined. The proposed algorithm finds the best solution by conduit sharing within the limits of network survivability. According to the simulation result, the proposed method can decrease 7% of total cost than an existing method by effective conduits adaption. 최근 각종 멀티미디어 서비스의 제공은 전송데이터의 급격한 증가를 가져왔으며, 이러한 서비스의 원활한 제공을 위해서는 초고속 통신망의 구축이 불가피하게 되었다. 초고속 통신망의 구축은 막대한 비용을 요구하기 때문에 망 구축비용의 감소를 위해서는 기존에 설치된 관로를 고려해야한다. 또한 초고속 통신망은 하나의 선로에 많은 양의 데이터가 전송되므로 한 선로에 문제가 있는 경우 막대한 손실이 발생하는 특징을 지닌다. 이 때문에 전체 네트워크를 일정수준이상의 생존도를 가질 수 있게 설계하여야한다. 이러한 문제의 해결을 위해서 기존의 논문에서는 비용을 줄이기 위해 고려된 기존 관로를 다음 단계에서 배제하여 한 관로를 여러 경로에서 사용함으로써 얻을 수 있는 비용 절감효과를 상실하였다. 그러나 본 논문에서는 생존도를 유지하는 범위 내에서 기존에 설치된 관로를 최대한 고려하여 비용 절감을 극대화한 네트워크를 효과적으로 설계하는 방법을 제안한다. 제안한 방법을 사용하여 실험한 결과에 따르면 기존의 방법에 비해 약 7%의 비용절감 효과를 얻을수 있었다.

멀티캐스트 라우팅을 위한 Ant Colony System 설계에 대한 연구

이성근,한치근,Lee, Sung-Geun,Han, Chi-Geun 한국정보처리학회 2003 정보처리학회논문지 A Vol.10 No.4

조합 최적화 문제를 풀기 위한 개미 알고리즘(Ant Algorithm)은 실제 개미 집단의 행동을 모방하여 만들어진 것이다. Ant Colony System(ACS)은 여러 유형의 개미 알고리즘 중 비교적 최근에 소개된 것이다. ACS의 설계를 위해 순회 외판원 문제(Traveling Salesman Problem, TSP)를 사용하여 실험을 수행하였다. ACS를 다양한 조합 최적화 문제에 적용할 때 순회 외판원 문제에 사용된 ACS의 파라미터와 전략을 사용하고 있다. 본 논문에서는 조합 최적화 문제들 중 하나인 멀티캐스팅 라우팅 문제를 해결하기 위해 ACS를 이용하였다. 멀티캐스트 라우팅은 데이터를 하나의 송신자에서 여러 수신자들로 보내기 때문에 모든 노드를 포함하는 순회 외판원 문제와는 속성이 다르고, 송신자에서 각 수신자에 하나의 최단경로를 설정하는 문제와도 다른 속성을 지니고 있다. 본 논문에서는 멀티캐스트 라우팅에 ACS를 적용하기 위해 알고리즘의 동작을 수정하고, 수정한 ACS의 성능을 향상시키기 위한 최적의 전략과 파라미터를 설계한다. Ant Algorithm is used to find the solution of Combinatorial Optimization Problems. Real ants are capable of finding the shortest path from a food source to their nest without using visual informations. This behavior of real ants has inspired ant algorithm. There are various versions of Ant Algorithm. Ant Colony System (ACS) is introduced lately. ACS is applied to the Traveling Salesman Problem (TSP) for verifying the availability of ACS and evaluating the performance of ACS. ACS find a good solution for TSP When ACS is applied to different Combinatorial Optimization Problems, ACS uses the same parameters and strategies that were used for TSP. In this paper, ACS is applied to the Multicast Routing Problem. This Problem is to find the paths from a source to all destination nodes. This definition differs from that of TSP and differs from finding paths which are the shortest paths from source node to each destination nodes. We introduce parameters and strategies of ACS for Multicasting Routing Problem.

무선 ATM 망에서 페이징 트래픽 부하의 감소를 위한 동적 페이징 영역 관리 기법

이태로,이성원,한치근,유인태,Lee, Tae-Ro,Lee, Seong-Won,Han, Chi-Geun,Yu, In-Tae 한국정보처리학회 2000 정보처리논문지 Vol.7 No.s8

본 논문은 ATM-Forum의 WATM 기반 제3세대 무선 멀티미디어 망 환경에서 하나의 M.E.SW(Mobility Enabled ATM Switch)가 단순화된 많은 AP들을 관리하는 방안에 대하여 고려하였다. 또한 WATM 망 환경에서 가변 그룹 크기와 동적인 그룹 페이징 순서 방법을 사용하는 효율적인 페이징 방안을 제안하였다. 그리고 제안한 방안과 기존의 방안에 대해 성능을 평가 및 분석하였다. 여기서는 blanket-polling, sequential-polling 그리고 고정크기 그룹화 방안과 같은 대부분의 기존 방안들을 제안한 가변적이면서 동적인 그룹화 방안과 비교 분석하였다. 분석결과 offered-load가 낮은 환경에서는 단순한 blanket-polling paging 방안이 약간 더 우수한 성능을 보였다. 그러나 트래픽 밀도가 높아지면서 제안한 방안이 기존의 방안들 보다 더 우수한 성능을 보였다. 성능개선은 주로 가변적인 그룹 크기와 MS(Mobile Station)기반 동적인 페이징 순서 방안에 기인한다. 또한 제안한 방안은 MS에 대한 아주 간단한 이력정보와 최종적으로 통신한 AP 정보만이 필요하다. 따라서 이 방안은 효율적으로 구현하는 것이 가능하다.