慶應義塾大学 政策・メディア研究科 修士課程 ２年 間 博人 移動計算機環境における グループ抽出機構 慶應義塾大学　政策・メディア研究科 修士課程　２年　　　　間　博人

修論の流れ グループ抽出のモデル amicus の導入 アドホックネットワークへの適用: SoC amicus

Amicus とは あるポリシーに基づいて形成されるグループ

Amicus の分類 Physical amicus Informatics amicus Semantic amicus 例: 動物の群れ Informatics amicus 情報空間上の距離から amicus 形成 例: トポロジ，ネットワーク遅延 Semantic amicus 意味空間上の距離から amicus 形成 例: 友人，親子，大学，会社

ネットワークおける amicus の意義 多様な通信形態のサポート ドメインとして利用 １対１ : Peer-to-peer １対Ｎ : 先生から生徒への通信 (Multicast) Ｎ対１ : 情報の収集 (Concast) Ｎ対Ｎ : グループ通信 ドメインとして利用 セキュリティー キャッシュ管理

アドホックネットワークへの適用

アドホックネットワーク (MANET) とは 無線ノードのみでマルチホップ可能なネットワーク 無線ノードの頻繁な移動を想定 利用形態 ミーティグルーム パーソナルエリアネットワーク タクシーネットワーク 災害地での救助

ＭＡＮＥＴの特徴 ノードの移動により，ネットワークトポロジが頻繁に分裂・統合を繰り返す トポロジを利用した Informatics amicus は非効率的

Physical amicus モデルの適用: SoC amicus 無線リンクの切断はノードの移動ではなく相手ノードとの距離の変化が原因 Physical amicus モデルの適用 相手ノードとの接続強度(SoC) の変動から amicus を構成する　(SoC amicus) 切断しにくいノードの集合 移動ノードの中の群れの発見 B A´ B´

SoC amicus の形成方法 SoC Amicus Protocol Architecture Amicus Detection Protocol 他ノードの SoC 情報を収集する　（pull 型，push 型) Amicus Identifier 収集した SoC情報の履歴と与えられたポリシーを元に SoC amicus か識別 Application

SoC amicus を利用したP2Pシステムの 効率的な複製アルゴリズムの提案

アドホックネットワーク上でのP2Pシステム 中央集中的なサーバがない環境が想定される Peer-to-Peer アプローチの有用性 ファイルの共有 サービスの検索 中央集中的なサーバがない環境が想定される

Ｐ２Ｐシステムの分類と研究対象 中央集中型 分散・構造型 分散・非構造型 Napster Chord, Tapestry, Freenet Gnutella, FastTrack 研究のフォーカスを何処に絞るか。。。

非構造型 P2P システムの問題点 Flooding search が非効率 Passive replication Proactive replication Q. Lv, P. Cao, E. Cohen, K. Li, and S. Shenker. Search and replication in unstructured peer-to-peer networks. In Proceedings of the International Conference on supercomputing, 2002. E. Cohen, S. Shenker. Replication Strategied in Unstructured Peer-to-Peer Networks. In Proceedings of the SIGCOMM, 2002.

アドホックネットワークにおける データ複製 ノードＧがＦにデータαを複製 ノードＡの Query は成功 E B D G Send Query Search α TTL 3 A α F C Success α’ replicate

アドホックネットワークにおける データ複製 D-E、Ｄ-F間が切断 ノードAの Query 失敗 E B D G A Send Query Search α TTL 3 Fail α F C α’

アドホックネットワークにおける データ複製 　αをＴＴＬ３の範囲に複製する E α’ α’ B D G A α F C α’ α’ α’

アドホックネットワークにおける データ複製 ノードＡのQuery成功 E α’ α’ B D G Send Query Search α TTL 3 A α F C α’ Success α’ α’ 無駄な複製が多い キャッシュ可能な容量には限界がある

SoC amicus を適用したデータ複製 SoC amicus の適用 各リンクの接続性の強度が分かる 無駄なキャッシュを消すことができる E α’ α’ B amicus D G A amicus α F C α’ α’ α’ 無駄なキャッシュを消すことができる

SoC amicus の適用したデータ複製 無駄なキャッシュを消すことでキャッシュヒット率を上げることが可能 amicus E B Send Query Search α TTL 3 D G A α F C α’ Success

評価 検索ヒット率 移動パターン Random Static group Dynamic group 複製ポリシ アクセスパターン 移動パターン　 Random Static group Dynamic group 複製ポリシ アクセスパターン キャッシュ容量

検索ヒット率のスナップショット Number of nodes: 100, query policy: random and each 1 second, 　 Replicate policy: piggyback Query, movement of nodes: RPGM,　Each node has 1 original data

考え中 Amicus とクラスタリングの関係 関連研究の配置 クラスタリング 移動予測 セル移動予測 ＧＰＳ移動予測 複製最適配置