| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2012-03-09 14:30 故障時においても直径が抑制されたリンク数の少ないネットワーク設計法 ○西田幸平・巳波弘佳（関西学院大）  NS2011-252 |
|
| 抄録 | （和） | インターネットをはじめ，通信ネットワークが社会において必要不可欠なインフラとなった現在，ネットワークには高い信頼性が求められている．しかし，ネットワークにおいてリンク故障による経路切断が発生した際，代替経路の経路長が大幅に増加し，通信品質の大幅な劣化を引き起こす可能性がある．本稿では，直径・次数の制約を満たしつつ，コストに対応するリンク数を抑えた新規ネットワークの設計問題を扱う．まず，この問題が一般に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 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | NS2011-252 |
|
| 研究会情報 | |
| 研究会 | 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.) |
| 講演者 | 第1著者 |
| 発表日時 | 2012-03-09 14:30:00 |
| 発表時間 | 20分 |
| 申込先研究会 | NS |
| 資料番号 | NS2011-252 |
| 巻番号（vol） | vol.111 |
| 号番号（no） | no.468 |
| ページ範囲 | pp.409-414 |
| ページ数 | 6 |
| 発行日 | 2012-03-01 (NS) |
[研究会発表申込システムのトップページに戻る]