TOP > 研究紹介 > 藤原 暁宏

教授
藤原 暁宏

並列分散アルゴリズム、計算量理論

ホームページ

研究紹介

アドホックネットワーク及びセンサネットワークにおけるアルゴリズム

アドホックネットワークとは、ノートパソコンや携帯電話などの端末が、特定の基地局やアクセスポイントを介せずに端末同士で通信を行うネットワークです。また、センサネットワークとは、熱や温度等の検知機能と簡易的な通信機能を持った安価なセンサを広範囲に配置し、特定領域の監視を行うためのネットワークです。これらのネットワークは、端末やセンサのみでネットワークを構築できるので、新しい分散ネットワークの一つとして注目を集めています。
しかしながら、これらのネットワークには、基地局やアクセスポイントといった集中的な管理を行うコンピュータが存在しないので、各端末やセンサは、自分の持つ情報のみで通信や計算を行うという、自律分散的な動作を行わなければなりません。また、端末やセンサは主にバッテリーで駆動されており、充電量の減少を防ぐために、通信やコストの少ない動作が求められます。
本研究室では、これらのネットワークに対して、通信やコストを低減させるアルゴリズムの提案や、耐故障性を持ちネットワークの可用性を高める自律分散的な動作のアルゴリズムに関する研究を行っています。
これらのネットワークにおけるアルゴリズムの例として、以下にセンサネットワークにおける２連結な連結センサカバーについて簡単に説明します。センサネットワークを構成する小型自律センサは、検知機能と通信機能を持っており、各々のセンサが自身の検知範囲内の情報を通信範囲内の他のセンサにメッセージ通信することにより、ネットワーク全体で要求される領域の情報を得ることができます。そこで、ある特定の領域の監視を行う場合は、領域全体をセンサの検知領域で被覆し、かつ、各センサが通信可能であるセンサの集合を求める必要があります。このようなセンサの集合を連結センサカバーと呼びます。
一方、各センサは内蔵バッテリで駆動されているので、センサネットワーク全体で消費される電力はできるだけ少なく抑える必要があります。このような省電力化の手法の１つとして、できるだけセンサ数の少ない連結センサカバーを求める手法が考えられています。
本研究室では、このセンサ数の少ない連結センサカバーを求める手法に加えて、連結センサカバーに対して、どのセンサが故障しても連結であるという２連結性を持たせることにより、可用性を持たせた連結センサカバーに関する研究を行っています。
この２連結な連結センサカバーの例を下図に示します。この図では、赤い点線が検知領域で被覆すべき領域を表し、各丸がセンサを表しています。このセンサ集合の中で、緑色のセンサを中心とする検知領域だけで被覆すべき領域は覆うことができますが、それだけではすべてのセンサが通信することはできません。これに対して、更に赤色のセンサを加えることで、任意の２つのセンサが２連結な連結センサカバーが得られています。

fujiwara_research

　本研究室では、この２連結な連結センサカバーに関して、

  • できるだけ少ないセンサ数の２連結なセンサカバーを求める集中型アルゴリズムの提案
  • 各センサが自律分散的な動作で２連結な連結センサカバーを求める分散型アルゴリズムの提案

等の研究を行っています。

ナチュラルコンピューテイングに関するアルゴリズム

現在のシリコンベースのCPUは、物理的制約のため、高速化の限界に近づきつつあります。そのため、この限界を打破するための新しい計算パラダイムに関する議論が盛んに行われていますが、その１つとして、生体系に代表されるような自然界のシステムを計算に用いるナチュラルコンピューティングが現在注目を集めています。このナチュラルコンピューティングは、自然界の持つ自律的な処理の仕組みを用いて並列分散処理を行うという計算方式です。
例えば、生体系のシステムに基づくナチュラルコンピューティングでは、細胞等の各資源の活動を計算と考え、細胞間の情報伝達経路をネットワークと考えることにより、生体系を１つの自律並列分散処理システムと考えます。このシステムを統合的に制御し、計算に利用することがナチュラルコンピューティングの目的です。
本研究室では、このナチュラルコンピューティングに関して、細胞の活動をモデルとする膜計算や、DNAの性質を用いて計算を行うDNA計算について、算術演算や論理演算等の基本的な演算を行うアルゴリズムの提案を行っています。
ナチュラルコンピューティングの例として、以下に細胞の活動をモデルとする膜計算について簡単に説明します。膜計算とは、生物の細胞の活動をモデル化して計算に用います。例えば、下図の左は植物細胞の概略図ですが、一番外側の細胞膜には核や液胞といった膜が含まれており、また、各膜は独立した生命活動を行うミトコンドリアや葉緑体といった要素を含んでいます。

fujiwara_research2

膜計算では、このような細胞の持つ、

  • (a) １つの細胞はいくつかの膜の階層構造により構成される
  • (b) 各膜内の要素は，独立した生命活動を行う

という２つの特徴を利用して、計算を行っていきます。
具体的に説明すると、(a)の特徴である膜の階層構造は、上図の右のように識別子のついた均一な膜の包含関係として抽象化され、各膜に含まれる要素は、データを表す記号列を意味するオブジェクトとして定義されます。また、(b)の特徴である要素の生命活動は、各オブジェクトに対する進化規則として定義されます。例えば、上図の右の様に、膜0の中にオブジェクトMが存在し、このオブジェクトがある一定時間後にオブジェクトM’に変化する場合は、M→M’という進化規則が定義されます。
このように膜計算では、膜及び膜内のオブジェクトに対して進化規則を繰り返し適用し、膜及びオブジェクトを進化させることにより計算を行います。この膜計算と現在の計算機との大きな違いは、生命活動の特性に由来する最大並列則です。最大並列則とは、複数のオブジェクトに対してそれぞれ適用できる進化規則があれば、すべてのオブジェクトはそれぞれの進化規則に従って並列に進化するというものです。この最大並列則により、膜計算におけるオブジェクトの進化を並列計算とみすことができます。

本研究室では、この膜計算に関して、

  • 足し算や論理演算を行うアルゴリズムの提案
  • データ操作の一種である辞書演算を実行するアルゴリズムの提案

等の研究を行っています。

研究紹介トップ