(セッション表へ)

マルチメディア，分散，協調とモバイル(DICOMO2007)シンポジウム

セッション 1G  P2P１(DPS)
日時: 2007年7月4日(水) 13:10 - 14:50
部屋: 展望サロンB
座長: 神崎 映光 (大阪大学)

1G-1 (時間: 13:10 - 13:35)
題名P2P環境におけるセンサ観測値の地理的分布を把握可能なデータ収集手法
著者*小西 佑治, 竹内 亨 (大阪大学大学院情報科学研究科), 寺西 裕一 (大阪大学サイバーメディアセンター), 春本 要 (大阪大学大学院工学研究科), 下條 真司 (大阪大学サイバーメディアセンター)
Pagepp. 165 - 172
KeywordP2P, ユビキタス, センサ, ドロネーネットワーク
Abstract近年ブロードバンド常時接続環境が普及し、生活の隅々にまで情報通信が溶け込んで「いつでも、どこでも、何でも、誰でも」ネットワークにつながるユビキタス環境への関心が高まっている。ユビキタス環境では、人−人の結びつきだけでなく人−モノ、モノ−モノも結ばれ、多くの人やモノが情報を発信したり取得したりする。また、様々な情報発信元がネットワークでつながることにより、遠隔地の情報や広範囲にわたる情報を自由に取得することが可能となる。 このように取得される情報に実世界の環境の情報があり、この環境の情報を発信するものとしてセンサが挙げられる。ユビキタス環境では、無線センサノードやセンサをもつ情報家電などがネットワークに接続されることで、膨大な数のセンサが利用可能になると考えられる。しかし、膨大なセンサ情報を従来のようにあらかじめサーバに集約して提供を行う形態では、負荷が集中したり情報のリアルタイム性が損なわれたりする。そのためセンサのネットワークは、各センサがピアとなり直接問い合わせを受けるP2Pネットワークが適している。 センサ情報を活用する場合として、ある地点周辺の少数のデータが必要な場合、広範囲の全データが必要な場合、広範囲のデータ全てが必ずしも必要ではない場合が考えられる。これらのうち、本研究では広範囲のデータ全てが必ずしも必要ではない場合について扱う。広範囲のデータ全てが必ずしも必要ではない場合とは、例えば降雨分布や温度分布といった観測値の大まかな分布を把握するために対象範囲の情報を収集する場合が挙げられる。このような場合、利用者がセンサに問い合わせを行うと検索範囲内に存在する多数のセンサ全てが対象となる。このとき、地理的に近いセンサの観測値はほぼ同値であるため、利用者は類似したセンサ情報を多数取得してしまう。しかし、センサ情報は高密度に存在するため、情報を間引いても利用者は十分に観測値の分布を把握できる。また、0℃〜20℃の範囲を5℃間隔で色分けして表示するような温度分布を考える時、同じ5℃の範囲に属する多数のセンサ情報は同じ色で表わされる。このように得たい分布の詳細度が粗くてよい場合、観測値がほぼ同値でなくても同じ意味を表す情報が多数存在することになり、より多くの情報を間引くことができる。 そこで、情報を間引くためにセンサの応答数を削減することを考える。各センサが確率pで応答するランダムサンプリングにより応答数を削減すると、利用者が取得するセンサ情報数は検索範囲内の全てのセンサ情報数の約p倍に減少する。しかし、ランダムサンプリングでは利用者の要求する詳細度を満たす観測値の分布を把握するために必要なセンサ情報を取りこぼし、全てのセンサの応答から得られる観測値の分布を得られない可能性がある。このため、観測値の分布を考慮して、利用者の要求する詳細度で観測値の分布を把握するために必要な情報は必ず取得できるような手法が必要となる。 本研究では、観測値の分布を大まかに把握する場合における、地理的に近く同じ値の範囲に属する領域に注目する。ここではこの領域をクラスタと呼ぶ。先ほどの温度分布の例では、クラスタは地理的に連続して分布する0℃〜5℃、5℃〜10℃といった領域にあたる。利用者はこのクラスタの境界となる閾値の間隔、つまり1℃間隔なのか5℃間隔なのかを検索時に与えることで、得られる分布から読み取れる観測値の変化の詳細度を決めることができる。このため、クラスタは検索時に動的に決定される必要がある。クラスタ内部は同じ値の範囲と分っているため、クラスタ内部に存在するセンサのうち境界に接するセンサの観測値がどの値の範囲に含まれるか分かれば、そのクラスタの分布範囲と値の範囲を知ることができる。そのため、検索範囲内に分布するクラスタを少ないセンサ情報で把握するために、クラスタの境界付近のセンサが応答する手法をとる。 P2Pネットワークにおいて、各ピアが広範囲にわたるセンサ観測値の分布を把握することは難しい。そのため、センサの構築するネットワークにP2Pドロネーネットワークを利用し、応答するかどうかは近傍のセンサ情報を利用して判断する。このようにして、本研究では冗長な情報を削減し、利用者の要求する詳細度でセンサ観測値の分布を把握できるセンサ情報収集手法を提案する。また、提案手法をシミュレーションにより評価し、ユーザの要求する詳細度でセンサ観測値の変化を把握することができ、かつ、冗長な情報を削減できていることを確認した。 キーワード： P2P、ユビキタス、センサ、ドロネーネットワーク

1G-2 (時間: 13:35 - 14:00)
題名PLATON: 超分散環境におけるデータ共有のためのP2P多次元範囲検索システム
著者*中台 慎二, 谷口 邦弘 (NEC　インターネットシステム研究所)
Pagepp. 173 - 184
KeywordP2P, DHT, 空間充填曲線, 分布関数, de Bruijn
Abstract実世界から得られるデータを利用して、ユーザに多様な付加価値を提供するユビキタス社会を実現するには、これを支えるデータ共有基盤に、汎用な検索機能とスケーラビリティが求められる。ここでの汎用な検索機能とは、文字列の前方一致検索や数値の範囲検索など、多様なアプリケーションが汎用に利用可能な検索式を提供する機能である。また、スケーラビリティとは、データを収集するセンサー、データを利用するユーザ、および共有されるデータの数が増加しても、システム負荷や検索性能が劣化しないことである。この種のスケーラビリティを有すデータ共有方式として、P2Pデータ共有技術がある。 初期のP2Pデータ共有技術であるGnutellaなどは、インターネット上に分散する膨大なホスト間で膨大な情報を共有できる可能性を示した。そこでは汎用な検索機能が提供されていたが、問題点としてネットワーク利用の非効率性と検索の不完全性、すなわち格納したデータが確実には検索できないという問題があった。一方、Chord, CAN, Pastry, Tapestry, Koordeといった先駆的研究で注目されているDHTは、スケーラブルにデータ欠落のない検索を可能とするが、完全一致検索しかサポートされない。 　これに対しMAANやSENSといった先行研究は、それぞれChordやCANを、多次元属性に対する範囲検索が可能なようにデータのID算出方法を拡張した。具体的には、ChordやCANではHash関数を用いてデータのIDを算出するが、ここに各属性の分布関数を用いる。このように算出されたデータIDは均一性が保たれるだけでなく、属性値の連続性も保持されるため範囲検索が可能となる。 しかしながら、これら従来の分布関数を用いたID算出方式では、多次元属性値をID空間に写像する際に問題があった。MAANでは、多次元属性を構成する各属性値を個別にChord一次元ID空間に写像するため、テーブルに対して複数の単一インデックスが設定されている状態と同様、多次元属性値の分布を考慮した効率的な検索を行うことができない。具体的には検索時に、多次元検索式を構成する各属性について、その属性の分布関数を用いて検索条件の範囲をID範囲に変換する。そして、それらのID範囲の中から最も狭いID範囲を選択し、この範囲に到達するようにメッセージ転送を行う。このため、本来必要な多次元検索式を満たす集合要素数に比べてより大きな集合にメッセージ転送をする必要があり、効率的でない。一方、SENSでは、多次元属性の各属性値をCAN多次元ID空間に写像するため、データの均一配置に問題がある。具体的には、データ登録時に各属性の分布関数を用いて多次元IDを算出するが、この関数には多次元属性値の分布情報は含まれていないため、データが密に存在しない値域に対しても広いID空間が割り当てられてしまう。 スケーラビリティの観点では、いずれの技術にも一長一短がある。MAANがベースとするChordはO(logN)の次数でO(logN)ホップ数を実現する。これはピア数の増加に伴って、ホップ数は飽和するものの、ピア数が少ない状態からルーティングテーブルの管理負荷が大きいことを意味する。一方で、SENSがベースとするCANでは、次元数をdとしてO(d)の次数でO(dN1/d)ホップ数を実現する。すなわち、ｄを小さく設定した際には、ピア数に寄らずにルーティングテーブルの管理負荷は小さいものの、ピア数が増加するに従いホップ数が飽和しにくい。ｄを大きく設定した際には、ホップ数は飽和しやすいもののルーティングテーブルの管理負荷が大きくなる。 本提案システムPLATON (Planetary-scale Table on Overlay Network)は、これらの多次元属性の範囲検索に関する課題を解決する。すなわち、メッセージ転送負荷としては、多次元検索式を満たす値の集合と対応するピアにのみメッセージを転送するため、負荷が低く効率的である。データ配置の均一性としては、多次元属性値の分布に歪みがある場合でも均一にデータを配置することが可能となる。さらに、スケーラビリティとしてはO(logN)の次数でO(logN)のホップ数を実現する範囲検索方式に加えて、O(1)の次数でO(logN)のホップ数を実現する範囲検索も実現する。このことは、ピア数が増加してもルーティングテーブルの管理負荷は小さく、なおかつホップ数が飽和することを意味する。これらの提案方式は、検索式の入力として簡易SQL言語を持つシステムとして実装し、その効果検証を行った。

1G-3 (時間: 14:00 - 14:25)
題名アプリケーション層マルチキャストプロトコルの設計開発および性能評価を支援するミドルウェアの設計と実装
著者*池田 和史, Thilmee, M. Baduge, 梅津 高朗, 山口 弘純, 東野 輝夫 (大阪大学大学院情報科学研究科)
Pagepp. 185 - 193
Keywordアプリケーション層マルチキャスト, ミドルウェア, PLanetLab, 設計開発, 性能評価
Abstract本稿では，アプリケ−ション層マルチキャスト（ALM）プロトコルの設計開発および性能評価を支援するためのミドルウェアを提案する．我々は既存のALMプロトコルを詳しく分析，そのオーバレイトポロジや制御方式によりそれらを分類し，共通に利用できる汎用的な機能を抽出し，提案ミドルウェアに実装した．提案ミドルウェアはトポロジ管理機能，通信支援機能，ALMプロトコル設計支援機能，性能評価支援機能などを提供することで，ALMプロトコルの開発および性能評価に必要な時間と労力を大幅に削減する．我々はミドルウェアの提供するこれらの機能を用いて，既存の著名なALMプロトコルであるALMI,NARADA,NICE,OMNIを実装し，実環境として世界中に配置されているサーバからなる実験用テストベットであるPlanetLab上で，これらのALMプロトコルの性能比較評価実験を行った．これらの実験を通して，提案ミドルウェアを利用することで，ALMプロトコルの実装にかかる労力が大幅に削減され，実環境での様々な性能評価試験を容易に行うことができることを確認した．