3A-02
仮想グリッドネットワークにおけるスタイナー木生成のための自律分散アルゴリズムに関する研究
○金　鎔煥（名工大），増澤利光（阪大）
仮想グリッドネットワークは，無線ネットワークにおいて，ネットワーク全体のトポロジを格子型に変換するモデルであり，様々な問題を解くのに役立つモデルである．このような仮想グリッドネットワーク上において，指定された多数のノードを含むスタイナー木（Steiner Tree）を生成する自律分散アルゴリズムについて考える．
各ノードの間にはマルチホップ通信のためのルートが存在し，各ノードの移動によって動的に更新される．このようなルートの変化でも，システム全体の状況が把握できない各ノードは局所情報だけを利用して，自律的にルートの更新を行い，最小の中継ノードだけを利用して通信ができるようなルーティング用スタイナー木を生成する．
本稿では，モデルと問題を定義し，3ノード間環境でのアルゴリズムを紹介し，一般化に向けての問題の議論を行う．
footer 著作権について 倫理綱領 プライバシーポリシー セキュリティ 情報処理学会