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

発表の流れ SoC amicus を利用した複製アルゴリズムの評価 グループ抽出とは ー Amicus の導入 －

研究背景 様々な情報機器 種類 相互関係 移動パターン 種類，目的，移動パターン， グループ抽出 抽出条件をもとにグループを抽出する

抽出するグループの種類 Physical Group Informatics Group Semantic Group 物理空間上の位置から抽出 例: 動物の群れ Informatics Group 論理空間上の位置から抽出 例: トポロジ，ネットワーク遅延 Semantic Group 意味空間上の位置から抽出 例: 友人，親子，大学，会社

抽出するグループのモデル化 - Amicus の導入 - ノードの位置を物理，論理，意味空間にマッピング ノード間の距離を強度としてあらわす 強度の時系列変動を考慮 動的変動への対応 互いの関係を強度としてあらわす、 ２台の場合 強度の時系列変動を考慮している点が　アミクース　モデル自体の売り 強度　Ｓij i j 物理，論理，意味空間上での距離

Amicus の適用 ネットワークコミュニティの抽出 興味や関心が共通する人の集団 アドホックネットワークでの群れの抽出

ネットワークコミュニティ抽出への適用 得点付けやブックマーク情報から属性を生成 ベクトル間の余弦値を 強度Ｓ に置き換える 多次元ベクトルで表現 ベクトル間の余弦値を　強度Ｓ　に置き換える Ａさん 洋菓子好き度　４ 和菓子好き度　２ A= (4.2) Ｂさん 洋菓子好き度　２ 和菓子好き度　６ B=(2,6) ＡさんとＢさんの距離 （-2, 4) （4+16)^1/2 = 4.47

Amicus の適用 ネットワークコミュニティの抽出 アドホックネットワークでの群れの抽出 興味や関心が共通する人の集団

アドホックネットワーク (MANET) とは 無線ノードのみでマルチホップ可能なネットワーク 無線ノードの頻繁な移動を想定 パーソナルエリアネットワーク 携帯電話、ラップトップ、時計 一般市民の (Civilian) 環境 タクシーネットワーク、ミーティングルーム 緊急時の操作 地震、洪水、竜巻 捜索と救出、警察や消防士

アドホックネットワークの問題 ネットワークの切断が頻繁に発生 データの利用性の低下が大きな問題

Amicus の適用： SoC amicus 相手ノードとの接続強度(SoC) を強度 Ｓ とする SoC の変動から amicus を抽出: SoC amicus SoC A B 切断しにくいノードの集合を抽出 A´ B´ SoC

SoC amicus の抽出方法 - SoC amicus プロトコル機構 - 受動 / 能動 SoC amicus 識別

受動 SoC amicus 抽出プロトコル Passive Amicus Abstraction Protocol (PSAAP) 各ノードが定期的にメッセージをブロードキャスト メッセージを受信したノードは受信時間と SoC 値を記録 A, 10 C, 7 B B, 10 A, 5 C A C, 5 B, 7

能動 SoC amicus 抽出プロトコル Active Amicus Abstraction Protocol (ASAAP) アクティブノードのみメッセージをブロードキャスト アクティブノード：　SoC amicus 情報が必要なノード 受信ノードは送信ノードと amicus の時に応答 A, 10 A, 10 B C A A, 5 B

SoC amicus 識別 対象ノードが SoC amicus か否か識別 SoC amicus 抽出プロトコルが収集した SoC値 SoCｔｈ，Tth, Ttm T+Tth 時点のSoC値を予測 最小二乗法を用いる SoC amicus 現時刻

SoC amicus を利用した 複製アルゴリズムの提案

アドホックネットワークでの複製配置 ネットワークの切断が頻繁に発生 データの複製配置によるデータ利用性の向上 データの利用性の低下が大きな問題 データの複製配置によるデータ利用性の向上 E B D G Send Query Search α TTL 3 A α F C Success α’ replicate

複製配置の課題 切断しないノード間に配置した複製は無駄 SoC amicus を使うと切断しにくいグループが分かる キャッシュ可能な容量の限界 SoC amicus を使うと切断しにくいグループが分かる E α’ α’ B D G Send Query Search α TTL 3 A α F C α’ Success α’ α’

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

SoC amicus 複製アルゴリズムの評価 複製アルゴリズムの分類 移動モデルの分類 評価環境 評価結果 検索ヒット率の比較 SoC amicus 抽出プロトコルの送信メッセージ数 ネットワーク分断による

移動モデル Entity Mobility Model Static Group Mobility Model 互いのノードが独立して移動 Random way point　mobility model Static Group Mobility Model 移動中に形成するグループのメンバが固定 Reference point group mobility model Dynamic Group Mobility Model 移動中に形成するグループのメンバが変動 Boid motion model Random way point　mobility model 各ノードが、ランダムに目的地と、移動速度を決定する 目的地に到達すると，一定時間まち（ポーズタイム）　ふたたび、目的地と速度をランダムで決定する Reference point group mobility model グループの移動を規定するグループ移動ベクトルＧＭ　と各ノードのランダム移動ベクトル　ＲＭ　から成る移動モデル Boid motion model 群知性（Mass Intelligence) のシミュレーションとして考案されたもの Separation 最適距離を保つ Alignment　視野内のノードと同じ方向を向く Cohesion　視野内のノードの中心に向かう

複製手法 定周期複製アルゴリズム (PR) PSAAP SoC amicus 複製アルゴリズム (PSAR) 定期的に各ノードがデータの複製を配置 PSAAP SoC amicus 複製アルゴリズム (PSAR) PSAAP で抽出した SoC amicus を使用 SoC amicus にあるデータを優先して削除 ASAAP SoC amicus 複製アルゴリズム (ASAR) ASAAP で抽出した SoC amicus を使用 検索　各ノード Ni は，一定間隔でランダムに選択したデータDj の検索クエリーをフラッディング． 検索クエリーを受信したノードが Dj を持っていれば Ni に通知する．

評価環境 各ノード Ni が オリジナルデータ Di を持つ 複製アルゴリズムにより複製 各ノード定期的にランダムで選択した Dj を検索 検索クエリーをフラッディング 複製、検索パラメータ キャッシュ容量： 5 複製配置間隔：　3 秒 検索間隔：　　　　3 秒 最大検索範囲：　10 hop 測定パラメータ フィールドサイズ：　　　 500 m 四方 無線通信範囲：　　 　　 50 m ノード数：　　　　　　　　　50 台 シミュレーション時間：　600 秒 測定回数：　　　　　　　　10 回 移動モデルパラメータ 最大速度： 10 m/s 待機時間：　 0 sec グループ数：　 3 最適距離：　 40 m Alignment率： 0.3 Cohesion 率: 0.1

検索ヒット率の推移 Dynamic Group Mobility の場合 ５０秒程度まで急激に検索ヒット率が上昇 １００秒位から検索ヒット率が安定

検索ヒット率の比較 全移動モデルにおいて検索効率が上昇

SoC amicus 抽出プロトコルの 送信メッセージ数 アクティブノードの比率が上がると ASAAPは高負荷

まとめ グループ抽出のモデル amicus アドホックネットワークに適用: SoC amicus ３タイプの移動モデルにおいて検索効率を評価

今後の課題 実機による検証 Amicus の非対称性の解消

アドホックネットワーク上での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.

評価 検索ヒット率 移動パターン 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

関連研究 クラスタリング 移動予測 セル移動予測 ＧＰＳ移動予測 複製最適配置

PSAAP A B C D PSAAP message PSAAP table entry PSAAP message 1 PSAAP message PSAAP table entry

PSAAP A B C D PSAAP message PSAAP table entry PSAAP message 1 PSAAP table entry

PSAAP A B C D PSAAP message PSAAP table entry PSAAP message B0,A1,C1 C0, B1, D1 D0,C1 PSAAP table B1 A1 B1 C1 C1 D1 PSAAP message 1 PSAAP table entry

PSAAP A B C D PSAAP message PSAAP table entry PADP message PADP table B0,A1,C1 C0, B1, D1 D0,C1 PADP table B1, C2 A1 B1, A2 C1, B2 C1, D2 D1 1 PSAAP message PSAAP table entry

ASAAP A B C D ASAAP message ASAAP table entry ASAAP message ASAAP REQ table ASAAP REP table ASAAP message 1 ASAAP table entry

ASAAP A B C D ASAAP message ASAAP table entry ASAAP message REQ 2 ASAAP REQ table A1 ASAAP REP table ASAAP message 1 ASAAP table entry

ASAAP A B C D ASAAP message ASAAP table entry ASAAP message REQ 2 REP B0 REQ 1 ASAAP REQ table A1 B1 ASAAP REP table BB1 ASAAP message 1 ASAAP table entry

ASAAP A B C D ASAAP message ASAAP table entry ASAAP message REQ 2 REP B0C1 REQ 1 REP C0 ASAAP REQ table A1 B1 ASAAP REP table BB1 CC1 CB1 1 ASAAP message ASAAP table entry