연구성과물검색
유형별/분류별 연구성과물 검색
HOME ICON HOME > Search by Achievements Type > Reports View

Reports Detailed Information

https://www.krm.or.kr/krmts/link.html?dbGubun=SD&m201_id=10019534&local_id=10026451
링 네트워크에서 k-에지 생존도를 구하는 해법
Reports NRF is supported by Research Projects( 링 네트워크에서 k-에지 생존도를 구하는 해법 | 2009 Year | 명영수(단국대학교(천안캠퍼스)) ) data is submitted to the NRF Project Results
Researcher who has been awarded a research grant by Humanities and Social Studies Support Program of NRF has to submit an end product within 6 months(* depend on the form of business)
  • Researchers have entered the information directly to the NRF of Korea research support system
Project Number B00178
Year(selected) 2009 Year
the present condition of Project 종료
State of proposition 재단승인
Completion Date 2011년 02월 14일
Year type 결과보고
Year(final report) 2011년
Research Summary
  • Korean
  • 통신망의 생존도는 마디 또는 호로 표현되는 네트워크의 요소에 장애가 발생했을 때 소통이 유지되는 통신 흐름의 양으로 측정된다. 본 연구의 목적은 링(ring) 구조의 네트워크에서 호의 장애에 대한 네트워크의 생존도를 계산하는 방법을 개발하는 것이다. 링 네트워크는 통신망에서 광범위하게 활용되고 있는 동기식 광전송망(SONET), 교통망, 전기회로 등을 표현하는데 흔히 사용되고 있다. 본 논문에서는 링 네트워크는 여러 개의 경로 네트워크(path network)으로 분할된다는 점에 착안하여 링 네트워크에서 망의 생존도를 구하는 다항시간해법을 개발하는 것이다.
  • English
  • Given an undirected network with a set of source-sink pairs, we are assumed to get a benefit if a pair of source and sink nodes are connected. The k-edge survivability of a network is defined as the total benefit secured after arbitrarily selected k edges are destroyed. The problem of computing k-edge survivability is known to be NP-hard and has applications of evaluating the survivability or vulnerability of a network. In this paper, we consider the k-edge survivability problem restricted to ring networks and develop an algorithm to solve it in polynomial time.
Research result report
  • Abstract
  • 통신망의 생존도는 마디 또는 호로 표현되는 네트워크의 요소에 장애가 발생했을 때 소통이 유지되는 통신 흐름의 양으로 측정된다. 본 연구의 목적은 링(ring) 구조의 네트워크에서 호의 장애에 대한 네트워크의 생존도를 계산하는 방법을 개발하는 것이다. 링 네트워크는 통신망에서 광범위하게 활용되고 있는 동기식 광전송망(SONET), 교통망, 전기회로 등을 표현하는데 흔히 사용되고 있다. 본 논문에서는 링 네트워크는 여러 개의 경로 네트워크(path network)으로 분할된다는 점에 착안하여 링 네트워크에서 망의 생존도를 구하는 다항시간해법을 개발하는 것이다.
  • Research result and Utilization method
  • (연구결과) 1) 문헌조사 및 관련 연구자의 최근 진행 연구에 대한 조사를 통해 최근까지 진행된 네트워크의 생존도 관련 연구에 대한 동향을 분석하였음. 네트워크의 구조가 특수한 경우 중, 링과 나무(tree)구조를 갖는 경우에 대한 유사연구를 비교 분석하였음.
    2) 링 네트워크에서의 k-호 생존도를 구하는 문제 를 해결하기 위한 우리의 전략은 원문제를 여러 개의 부분문제로 나누어서 푸는 것이다. 부분문제는 경로 네트워크에서의 k-호 생존도를 구하는 문제가 된다. 본 연구에서는 부분문제를 Lagrangean 완화를 이용하여 다항시간에 해결하고, 최적의 Lagrangean 승수를 역시 다항시간에 찾는 방법을 개발하였다. 이를 이용하여 원래의 문제인 링 네트워크의 생존도 문제를 다항시간에 풀 수 있는 해법을 개발하였다.
    (활용방안)
    조합최적화 분야에서 생존도가 높은 네트워크의 설계와 네트워크의 생존도 또는 안정성의 분석은 중요한 연구과제로 꾸준히 연구되어 왔다. 이는 교통, 통신망 등이 대다수 국가의 중요한 기간시설이고 이러한 시설의 장애는 국가적으로 매우 심각한 사태를 발생시킬 수 있기 때문이다. 이러한 이유로 통신망의 생존도에 대한 연구는 수십년동안 경영과학 또는 OR분야 학술대회의 중요한 주제로 채택되어 왔다. 본 연구의 결과도 이러한 학회 중 하나인 세계OR학회(IFORS)에 발표할 예정이고, 학술지에 본 연구의 내용을 발표하여 정보통신산업계에서 통신망의 안정성을 평가하는 기술로 활용되도록 할 것이다.
  • Index terms
  • 조합최적화, 네트워크 생존도, 링 네트워크, 다항시간해법
  • List of digital content of this reports
데이터를 로딩중 입니다.
  • This document, it is necessary to display the original author and you do not have permission
    to use copyrighted material for-profit
  • In addition , it does not allow the change or secondary writings of work
데이터 이용 만족도
자료이용후 의견
입력