コミュニケーションと計算の科学

研究展示 9

こわれにくいネットワークをデザインします

～二分決定グラフを用いたネットワーク信頼性最大化～

どんな研究

電線や道路などを増強する場合に、最も信頼性が高くなるようなネットワークの増強方法を自動的に見つけます。信頼性とは各電線や道路が寸断されたとしても通信や行き来ができる度合いを表します。信頼性の高い増強方法を見つけることは膨大な計算が必用な難しい問題でした。

どこが凄い

最適な増強方法を見つけるためには、膨大な数の故障パターンを調べ上げる必用があります。私達は二分決定グラフとよばれるデータ構造を用いて故障パターン集合を小さく表現することで、既存方法よりも十倍以上大きい実用的な通信ネットワークの最適解を求めることに成功しました。

めざす未来

本技術を用いることで、既存の方法よりも信頼性の高いネットワークをより安価に設計できるようになります。今後は広域の道路網などの大規模なネットワークの設計や、自然災害による断線が発生するケースへの対応などを行い、より幅広い場面で活用できる技術の実現をめざします。

関連文献

  • [1] M. Nishino, T. Inoue, N. Yasuda, S. Minato, M. Nagata, “Optimizing network reliability via best-first search over decision diagrams,” in Proc. IEEE Conference on Computer Communications (INFOCOM 2018), April 2018.

ポスター

アイコンをクリックすると、展示ポスターのPDFが開きます。
PDFの表示にはAdobe Acrobat Reader等のPDF閲覧表示が必要です。

当日の様子

展示代表者

西野 正彬
西野 正彬
協創情報研究部