2012 年度 卒業論文要旨 マイクロブログのための DHT マルチキャストによるメッセージ数削減方式 学修番号 09175020 高橋 拓生 指導教員 朝香 卓也 1 序論 近年，情報交換のツールとして SNS（social net- working service）やマイクロブログ（ミニブログ）な どのソーシャルメディアの需要が高まっている．ソー シャルメディアとは，一般のユーザ同士で情報を送受 信し合うことで社会的なネットワークを構築するメ ディアである．ソーシャルメディアは，情報が迅速に かつ広大に伝播していくので，企業のマーケティング 戦略や災害時のコミュニケーションの手段としても利 図 1: 提案方式と Chord のメッセージホップ例 用される． マイクロブログには時間が経過することによって， 意味を持たなくなる情報が他のソーシャルメディアに 比べて多く存在する．そのため，サーバ負荷による情 報伝達の遅延が起こらないシステムが必要である． マイクロブログのサーバに対する負荷の軽減手法は， マルチキャストを行う方式やハイブリッド P2P(Peer to Peer) を用いた方式など様々な方式がこれまで提案 されている．しかし，これらの方式はサーバを利用 した方式のため，ネットワーク負荷が原因となるサー バダウンには強いが，サーバそのものに問題がある 場合，サービスの提供ができなくなる．サーバが存 在しない方法として，非構造化 P2P を利用した方式 があげられる．非構造化 P2P を利用することによっ て，サーバの問題は解消される．しかし，メッセージ 数の増加に伴う全体のネットワークトラヒック量が増 管理している．この interesting keyword management table は自ノードの興味のあるキーワードを保持するだ けでなく，隣のノードの興味のあるキーワードを保持 する．あるピアがデータを検索する際は，interesting keyword management table を参照することで，デー タを探し出す．データを見つけることができなかった 場合，クエリメッセージをグループの先端のノードに 送る．既存の Social P2P では隣のユーザはグループに クエリメッセージを送ることによって検索し，必要な データは neibor list を用いることによって検索してい る．しかし，[1] では，近くのユーザはキーワードを用 いることによって検索し，必要なデータは interesting keyword management table を用いることによって検 索することができる． 加してしまう． そこで，本稿ではメッセージ数の削減を目的に，構 造化 P2P 技術である DHT（Distributed Hash Table） 3 提案方式 を用いてマイクロブログサービスを実現する方式を 提案方式では趣味嗜好などで関連性の高いユーザ 提案する．提案方式でのマイクロブログは Twitter を へのリンクを各ユーザが持つことによって，無駄な 想定し，Twitter 独自のフォロー・フォロワーという 経由を削減し，メッセージ数の削減を目指す (図 1)． ユーザ同士のつながりを利用することによって，メッ Twitter などのマイクロブログでは，同じ趣味嗜好を 持つユーザ同士での情報交換が多い．そこで，同じ セージ数を削減する方式を提案する． 趣味嗜好を持つユーザ同士のリンクを直接あるいは 数人のユーザを介すだけで繋がるようなネットワー 2 関連研究 グループをキーワードをもとにして作成する P2P ネットワーク [1] では，P2P ネットワーク上に存在する 各ピアが interesting keyword management table を クを作成することで，関連性の高いユーザ間のメッ セージ数が削減される．提案方式ではネットワーク・ トラヒックの大部分である関連性が高いユーザへの メッセージ数を削減し，関連性の低いユーザへのメッ セージ数は増加することになる．マイクロブログ内 のユーザから新たに記事を投稿された時，経路表を 用いてマルチキャストツリー (DHT マルチキャスト) を構成し，自分の保持するフォロワーの Twitter ID を目的 ID とするメッセージをマルチキャストする． マルチキャスト先は自分の保持するリンクを用いて 決定する．メッセージを受信したユーザは自分が目的 ID でなければ，自分の保持するリンクをもとに次の ノードに送信．ツイート情報が目的 ID のにたどり着 くまで繰り返す． 重複度はユーザが他のどのユーザと関連性が高い かを表す指標であり，2 名のユーザ間ごとに重複度は 存在する．重複度が高いほどユーザ間のつながりが 図 2: 提案方式と Chord のメッセージ数比較 (グルー プの重複を許す場合) 強いことから，各ユーザは重複度の高いユーザのリ ンクを保持する． 重複度による経路表作成手順を以下に示す．ある ユーザとそのフォロワー間の重複度を 1 増やす．ただ し，各ユーザ間の重複度の初期値は 0 とする．次に， あるユーザのフォロワー同士の重複度を 1 増やす．こ れを全てのユーザに対して行う．全てのユーザ間の重 複度を集計した後，各ユーザは重複度が高いユーザ へのリンクを順に保持し，各ユーザのリンクを集め たものが経路表となる． 図 3: 提案方式と Chord のメッセージ数比較 (グルー プの重複を許さない場合) 4 シミュレーション シミュレーションによる提案方式の性能を評価す 図 3 に，各ユーザが所属するグループの数を 1 と る．シミュレーションでは，ユーザ数を 1024，2048， して，関係が無いユーザを経由する確率を減らした 4096，8192 とし，ユーザは Chord のようなリング状 場合のグループ内選択率 F に対する p/c を示す．図 の数直線上に配置し，ユーザは参加・離脱を行わな 3 では，ノード数 4096 とノード数 8192 どちらもメッ セージの削減が 99 ％を超えており，ノード数が多く なるほど効果が出ている．図 2 と図 3 より，提案方式 い．また，配信者がフォロワーへ Push 配信すること とする． 評価は，DHT 技術の一つである Chord と提案方式 のメッセージ数を比較することによって行う．提案方 では情報交換をある一定のユーザのみで行なうよう な閉じた関係で効果が際立つことが分かった． 式のメッセージ数を Chord のメッセージ数で割った 値を p/c とする． フォロワーが所属するグループ内から選ばれてい る確率をグループ内選択率 F とする．このグループ 内選択率 F が 1 に近いほど，閉じた関係を形成する ことになる．閉じた関係とは，情報交換のほとんどを フォロー関係のあるユーザもしくは趣味嗜好の似通っ たユーザ同士で行うような関係である. 5 結論 本論文では，メッセージ数の削減を実現するために DHT マルチキャストを用いてリンク関係を構成する 方式を提案した．また，シミュレーションにより提案 方式が有効となる場合を明らかにした． 図 2 にユーザが重複してグループに所属できる場 合におけるグループ内選択率 F に対する p/c を示す． グループ内選択率が 1 と 0.8 のときは，全てのノード 数で p/c が 1 未満となっており，提案方式の方が有利 となっている． 参考文献 [1] Rim Haw and Choong Seon Hong, ”A Social P2P Networking Based on Interesting Keywords”, Information Networking (ICOIN), 2011 International Conference 509-512, 2011
© Copyright 2024 ExpyDoc
