入り口に戻る
メンバー紹介 研究内容 研究室へのアクセス その他の情報 英語のページ-English Page

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

アドホックネットワークとは,ノートパソコンや携帯電話などの端末が,特定の基地局やアクセスポイントを介せずに端末同士で通信を行うネットワークです.また,センサネットワークとは,熱や温度等の検知機能と簡易的な通信機能を持った安価なセンサを広範囲に配置し,特定領域の監視を行うためのネットワークです.これらのネットワークは,端末やセンサのみでネットワークを構築できるので,新しい分散ネットワークの一つとして注目を集めています.

しかしながら,これらのネットワークには,基地局やアクセスポイントといった集中的な管理を行うコンピュータが存在しないので,各端末やセンサは,自分の持つ情報のみで通信や計算を行うという,自律分散的な動作を行わなければなりません.また,端末やセンサは主にバッテリーで駆動されており,充電量の減少を防ぐために,通信やコストの少ない動作が求められます.

本研究室では,これらのネットワークに対して,通信やコストを低減させるアルゴリズムの提案や,耐故障性を持ちネットワークの可用性を高める自律分散的な動作のアルゴリズムに関する研究を行っています.

これらのネットワークにおけるアルゴリズムの例として,センサネットワークにおける2連結な連結センサカバーについて簡単に説明します.センサネットワークを構成する小型自律センサは,検知機能と通信機能を持っており,各々のセンサが自身の検知範囲内の情報を通信範囲内の他のセンサにメッセージ通信することにより,ネットワーク全体で要求される領域の情報を得ることができます.そこで,ある特定の領域の監視を行う場合は,領域全体をセンサの検知領域で被覆し,かつ,各センサが通信可能であるセンサの集合を求める必要があります.このようなセンサの集合を連結センサカバーと呼びます.

一方,各センサは内蔵バッテリで駆動されているので,センサネットワーク全体で消費される電力はできるだけ少なく抑える必要があります.このような省電力化の手法の1つとして,できるだけセンサ数の少ない連結センサカバーを求める手法が考えられています. 

本研究室では,このセンサ数の少ない連結センサカバーを求める手法に加えて,連結センサカバーに対して,どのセンサが故障しても連結であるという2連結性を持たせることにより,可用性を持たせた連結センサカバーに関する研究を行っています.

この2連結な連結センサカバーの例を下図に示します.この図では,赤い点線が検知領域で被覆すべき領域を表し,各丸がセンサを表しています.このセンサ集合の中で,緑色のセンサを中心とする検知領域だけで被覆すべき領域は覆うことができますが,それだけではすべてのセンサが通信することはできません.これに対して,更に赤色のセンサを加えることで,任意の2つのセンサが2連結な連結センサカバーが得られています.

本研究室では,この2連結な連結センサカバーに代表されるようなセンサネットワークに対して,効率のよいアルゴリズムに関する研究を行っています.



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

現在のシリコンベースのCPUは, 物理的制約のため, 高速化の限界に近づきつつあります.そのため,この限界を打破するための新しい計算パラダイムに関する議論が盛んに行われていますが, その1つとして, 生体系に代表されるような自然界のシステムを計算に用いるナチュラルコンピューティングが現在注目を集めています.このナチュラルコンピューティングは,自然界の持つ自律的な処理の仕組みを用いて並列分散処理を行うという計算方式です.

例えば,生体系のシステムに基づくナチュラルコンピューティングでは,細胞等の各資源の活動を計算と考え,細胞間の情報伝達経路をネットワークと考えることにより,生体系を1つの自律並列分散処理システムと考えます.このシステムを統合的に制御し,計算に利用することがナチュラルコンピューティングの目的です.

本研究室では, このナチュラルコンピューティングに関して,細胞の活動をモデルとする膜計算や,DNAの性質を用いて計算を行うDNA計算について,算術演算や論理演算等の基本的な演算を行うアルゴリズムの提案を行っています.

ナチュラルコンピューティングの例として,以下に細胞の活動をモデルとする膜計算について簡単に説明します.膜計算とは,生物の細胞の活動をモデル化して計算に用います.例えば,下図の左は植物細胞の概略図ですが,一番外側の細胞膜には核や液胞といった膜が含まれており,また,各膜は独立した生命活動を行うミトコンドリアや葉緑体といった要素を含んでいます.

膜計算では,このような細胞の持つ,
(a) 1つの細胞はいくつかの膜の階層構造により構成される
(b) 各膜内の要素は,独立した生命活動を行う
という2つの特徴を利用して,計算を行っていきます.

本研究室では,この膜計算に代表されるようなナチュラルコンピューティングに関して,効率のよいアルゴリズムに関する研究を行っています.


Copyright. Fujiwara-Lab All Right Reserved.