研究紹介 Research Topics

自律分散アルゴリズムの設計評価

現在、膨大な数の端末がネットワーク上に存在しますが、各端末はネットワークの全体像を知っているわけではなく、局所的(部分的)な情報しか知らない状況下で複数の端末間で協調動作を行い、電子メール等の何かしらのサービスを実現させる必要があります。自律分散アルゴリズムは、上記のようなサービス実現を目指して各端末はどのように行動すればよいかについての方針を定めるものになります。
例として、ワイアレスセンサネットワーク上の経路制御があります。形状はグリッドと呼ばれる碁盤の目のようなものを考えます。左側の図のような経路が確立されているときに(図(a))、目的地のノードが左側へ移動したとします(図(b))。このとき、局所的な経路拡張により接続の維持自体は可能ですが、目的地の移動・経路拡張を続けていくと接続は維持されているものの経路は最短ではありません(図(c))。このようなときに、局所的な情報のみを用いて最短経路の構築を考えます。これは、実は3つルール(図(d))を適用するだけで可能になります(図(e))。このように、特定の課題を解決するアルゴリズムの設計や評価を行います。

また、システムの効率的な設計手法としてモバイルエージェントというものもあります。これは、ネットワーク中を自律的に移動するソフトウェアを模擬したものです。エージェントの協調動作を実現させるための問題として、g-部分集合問題というものがあります。これは、複数体のエージェントがg体以上ずつのグループに分けれて別々のノードに集まるような自律的な移動を要求する問題です。この問題を解決することで、エージェントはグループ間での情報共有や、その後の意思決定や行動を迅速かつ効率的に行うことができます(下図)。他にも、均一配置問題と呼ばれる、エージェントを等間隔に配置するための移動を要求する問題や、探索問題と呼ばれる、各ノードは少なくとも1回は訪問・点検されるためのエージェントの移動計画を設計する問題等、様々なエージェントアルゴリズムが研究されています。

・ソフトウェアネットワーク上の高速ファイル転送や異常リンク検知

近年、地理的に分散されたデータセンタ間でやり取りされるトラフィック量の増大に伴い、帯域を有効利用するための高速・高効率なファイル転送技術の授業が高まってきています。そこで、先行研究として複数経路転送とマルチキャスト転送を組み合わせた複数経路マルチキャスト転送が研究されています。まず、送信したいファイルを複数のブロックに分割します(下図(a))。その後、複数経路転送を用いてそれぞれの経路に異なるブロックを転送することで高速な転送が期待できます(下図(b))。また、同時にマルチキャスト転送によって送信ブロックを転送途中で複製して複数の受信者へ転送することで効率的な転送が期待できます(下図(c))。このような複数経路マルチキャスト技術の拡張に関する研究も行っています。

また、効率的な通信を行うためには、各リンクの品質をリアルタイムで監視し、必要に応じて柔軟な経路変更を行うことが重要です。そこで、これまでに行われてきたリンク品質監視に関する研究では、計測端末から各リンクが1回ずつ通過されるような経路木に従って検査パケットを複数回送信し、指定した区間やリンクのパケットロス率を計算することで、品質低下しているリンクの場所を迅速に特定する手法が提案されてきました。この品質低下リンクの特定を効率的・低コストで行うための経路木設計等に関する研究も行っています。

・ICTを用いた災害時の救護活動支援

近年、大規模災害の件数が増加してきています。災害発生時には災害対策本部というものが消防局等により立ち上がり、消防車両等を用いて被災地の各道路の被災状況の把握が行われます。この時、ダメージが深刻だと通信インフラ(基地局)も被災しキャリア通信が使えず、車両は災害対策本部に帰還して被災状況を直接伝達する必要があります。このような状況下で、複数の車両が移動の途中で合流して、得られた情報をまとめて災害対策本部へ伝達する車両と残りの領域の探索を行う車両を役割分担させる等の工夫を行うことにより、迅速に多くの情報を災害対策本部に伝達し、二次被害の発生リスクを低減させるための手法設計に関する研究を行っています。