電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2012-03-09 14:30
故障時においても直径が抑制されたリンク数の少ないネットワーク設計法
西田幸平巳波弘佳関西学院大
技報オンラインサービス実施中
抄録 (和) インターネットをはじめ,通信ネットワークが社会において必要不可欠なインフラとなった現在,ネットワークには高い信頼性が求められている.しかし,ネットワークにおいてリンク故障による経路切断が発生した際,代替経路の経路長が大幅に増加し,通信品質の大幅な劣化を引き起こす可能性がある.本稿では,直径・次数の制約を満たしつつ,コストに対応するリンク数を抑えた新規ネットワークの設計問題を扱う.まず,この問題が一般にNP困難であることと,同時に故障するリンクは一つだけとする単一リンク故障(SLF)に限定してもNP完全であることを証明し,SLFに対するヒューリスティックなアルゴリズムを設計した.さらに,ネットワーク生成モデルを用いて生成したネットワークへアルゴリズムを適用し,有効性を評価した. 
(英) A telecommunication network should be reliable, since it is important as social infrastructure. However, in many actual networks, there exists the risk that the quality of service drastically degrades when the length of paths increases by a link failure. To get rid of this risk, it is necessary to design a network so that the diameter is small even if a link fails. In this paper, we formulated this network design problem as the discrete optimization problem which determines a spanning subgraph with the smallest number of edges such that, even if any edge is deleted, the diameter of the resulting graph is not more than a threshold and such that the maximum degree is constrained. First, we proved that this problem is NP-hard in general. Next, we presented three heuristic algorithms to solve the probrem that the number of link failures is restricted to one. Furthermore, we evaluated the performance of the proposed algorithms by applying the algorithms to some random graphs. The results showed that the hybrid algorithm that some redundant edges are removed after some paths are added to a degree-constrained spanning tree works well.
キーワード (和) ネットワーク / 通信品質 / リンク故障 / 直径 / 次数 / 最適化 / NP困難 / アルゴリズム  
(英) network / quality of service / link failure / diameter / degree / optimization / NP-complete / algorithm  
文献情報 信学技報, vol. 111, no. 468, NS2011-252, pp. 409-414, 2012年3月.
資料番号 NS2011-252 
発行日 2012-03-01 (NS) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 NS IN  
開催期間 2012-03-08 - 2012-03-09 
開催地(和) 宮崎シーガイア 
開催地(英) Miyazaki Seagia 
テーマ(和) 一般 
テーマ(英) General 
講演論文情報の詳細
申込み研究会 NS 
会議コード 2012-03-NS-IN 
本文の言語 日本語 
タイトル(和) 故障時においても直径が抑制されたリンク数の少ないネットワーク設計法 
サブタイトル(和)  
タイトル(英) Design Method of Robust Network with Small Diameter during Failures 
サブタイトル(英)  
キーワード(1)(和/英) ネットワーク / network  
キーワード(2)(和/英) 通信品質 / quality of service  
キーワード(3)(和/英) リンク故障 / link failure  
キーワード(4)(和/英) 直径 / diameter  
キーワード(5)(和/英) 次数 / degree  
キーワード(6)(和/英) 最適化 / optimization  
キーワード(7)(和/英) NP困難 / NP-complete  
キーワード(8)(和/英) アルゴリズム / algorithm  
第1著者 氏名(和/英/ヨミ) 西田 幸平 / Kohei Nishida / ニシダ コウヘイ
第1著者 所属(和/英) 関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第2著者 氏名(和/英/ヨミ) 巳波 弘佳 / Hiroyoshi Miwa / ミワ ヒロヨシ
第2著者 所属(和/英) 関西学院大学 (略称: 関西学院大)
Kwansei Gakuin University (略称: Kwansei Gakuin Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2012-03-09 14:30:00 
発表時間 20 
申込先研究会 NS 
資料番号 IEICE-NS2011-252 
巻番号(vol) IEICE-111 
号番号(no) no.468 
ページ範囲 pp.409-414 
ページ数 IEICE-6 
発行日 IEICE-NS-2012-03-01 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会