• 分散アルゴリズムとは？
• 研究内容
• 発表論文

アルゴリズムの世界では、コンピュータを「計算機」とか「ノード」というものでモデル化します。ネットワークは「通信リンク」とかでモデル化します。 以下は「計算機」と「リンク」という言葉を使います。

分散システムを対象として設計された分散アルゴリズムの多くは、 すべてのノードで足並みをそろえたような、 理想的な状況から計算をはじめた場合のみ正しい結果を得られることを 保証しています(例えば、すべてのノードを初期化した状況や、 すべてのノードがネットワーク全体の形状を知っている状況、など)。 しかし、実際のネットワークではノードの参加や離脱、ネットワークの形状の 変化などが頻発しています。また、ノードの故障も無視できません。 このような環境では、「理想的な状況」から計算を開始することは とても困難です。

自己安定アルゴリズムはどのような状況から計算をはじめても、正しい結果を 得られることを保証するアルゴリズムです。 この性質から、自己安定アルゴリズムはノードの故障・参加・離脱や ネットワーク形状の変化に対して、人間の介入なく自律的に対処することが でき、すぐれた自己適応能力、故障耐性を備えています。

分散システムが必要とする基本的な機能に対して、多くの自己安定 アルゴリズムが考えられてます。 効率的にすべてのノードへ情報を伝えるための通信経路の作成 (生成木作成問題)、ノード間の相互排除(トークン巡回問題，哲学者の食事問題) などです。 また、特定の故障や変化への適応性の高い自己安定アルゴリズムも考えられて います。悪意のあるユーザがノードを悪用している場合でも正しい計算結果を 得られる自己安定アルゴリズム(強安定アルゴリズム)、 小規模の故障に対して迅速に適応できるアルゴリズム(故障封じ込め自己安定 アルゴリズム)などです。



分散システムの大規模化・複雑化に対して、エージェントを利用したシステムの設計が注目を集めています。エージェントとは、自律的に動作するプログラムのことで、通信リンクで接続された計算機間を移動したり、他のエージェントと情報交換を行うことで、エージェント同士は協調して処理を行えます。そのため、エージェントを用いることで計算機の故障や、リンクの切断といった、トポロジの変化に対する適応性が優れたシステムの構築が行えます。

エージェントシステムでは、エージェントの持つ自律性、協調性を十分に発揮するための様々なアルゴリズムが考えられています。例えば、システム内に存在するエージェント数を理想的な数に保つにはどうするか(エージェント数制御)、各エージェントが初期状況で持っているそれぞれの情報をすべてのエージェントに伝えるには、各エージェントはどのような移動を行えばよいか(gossip問題)などに対する研究が行われています。



P2Pネットワークは、ネットワークに参加する計算機がサーバとクライアント 両方の役割をするネットワークで、すでに実用化されているシステムとしては ファイル共有システムやメッセージサービス、分散計算、マルチメディアスト リーミングなどが挙げられます。

P2Pネットワークの通信は、実ネットワーク上に構成された論理的ネットワー ク上で行われると考えます。この論理的なネットワークをオーバレイネットワー クとよびます。オーバレイネットワークの構造は主に2種類あり、構造化オー バレイと非構造化オーバレイに分けられます。構造化オーバレイでは実ネット ワークをリングやスキップグラフなどのグラフに写像し、すべての通信は仮想 ネットワーク上で行われると考えます。仮想ネットワークの構築、維持のため にコストが必要になりますが、検索やデータの送受信にかかるコストは劇的に 低下します。一方、非構造化オーバレイでは、仮想ネットワークの構築、維持 のためのコストが少ない分、検索やデータの送受信のアルゴリズムを工夫しな いと、ネットワーク中に検索クエリや転送パケットが蔓延して性能が低下する という問題があります。

増澤研では、通信コストが最適になる非構造化オーバレイの探索手法や、比較 的維持コストの少ない構造化オーバレイの構築、モバイルP2Pネットワーク向 けのアルゴリズムの研究を行っています。



MANET(Mobile Adhoc NETwork)とは 携帯電話やノートPCのような移動無線通信端末のみで構成されるネットワークのことです。 MANETの大きな特徴は、各端末同士が通信を行う際に、基地局やアクセスポイントを介さず、 お互いの端末を中継するマルチホップ通信を行うことです。 MANETを用いることにより、災害により既存のインフラが利用できない場合や、 イベント会場などで一時的なネットワークを利用したい場合に、 安価で容易にネットワークを構成することが可能となります。 しかし、MANETでは各端末が自由に移動するため、 ネットワークの構成が時々刻々と大きく変化します。 そのため、今までの固定のネットワークでは 考えられていなかった問題を考慮しなければいけません。

増澤研では、このようなMANET上でも効率よく適用することができるような アルゴリズムについての研究を行っています。 最近の研究事例では、各端末間が通信を行う際に できる限り長い間利用可能な経路を選択する手法や、 端末を効率よく管理するための手法(ノードの重み付け手法)などがあります。



センサーネットワークとは、センサーを搭載した 小型のノード(センサーノード)多数で構成された分散システムです。 センサーノードは計算回路、無線通信回路、バッテリなどを 備えていて、無線通信によって他のセンサーノードと協調しながら センシング結果を処理しています。 建物内での空調・照明の自動制御、 自然界での動植物の生態観測に用いられています。

センサーネットワークは今までの分散システムにはない 新しい特徴を持っています。 小型化によってノードの計算能力、バッテリが制限されている点や、 非常に多数のノードから構成されているといった点です。 このような特徴を持つセンサーネットワークに対し、 観測領域を覆うセンサーノードの配置を求める問題の研究や、 理論上の分散アルゴリズムを 実際のセンサーネットワークに実装する実験などが行われています。