R-Tree を用いた位置依存型 P2P ネットワークの性能評価
2002MT008 戎嶋 佑貴
指導教員

1 はじめに河野 浩之ることができる動的なインデックス構造を持ち，定期的な再編成は必要ない．

近年のユビキタス環境の浸透に伴い，コンテキスト(場所や時間などの実世界の情報) を用いたコンテキストアウェアサービスが注目されている．現在でもコンテキストアウェアサービスは多数存在するが，現在主に用いられているサーバクライアント型のネットワークでは，サーバへの負荷集中に問題がある．その問題を解決するために P2P ネットワーク [1] を用いることを考えるが，P2P ネットワークの検索手法においても，動的な環境で機能しづらいという問題がある．
そこで本論文では，R-Tree を参考にした端末の位置情報に基づく P2P ネットワーク LR-Net を提案する．
このようなネットワークを構築することで LR-Net と同様に階層的な構造を持つ P2P ネットワークである
LL-Net[2] との比較を行い，その優劣や超短所，有用性を示す．

図 1 エリアの ID と階層構造2 関連研究
2.1

位置情報に基づく P2P ネットワークにおけるエリアの階層化 [2]端末の位置情報を考慮に入れた P2P ネットワーク，LL-Net(Location-based Logical Network) の構築手法とそれを用いた情報検索手法が金子らによって提案されている．
LL-Net は図 1 のように検索領域を (x, y) 座標で格子状に区切り，各領域をエリア，座標をエリア ID とする．最小のエリアを Lv1 とし LvN のエリアが 4 つでLv(N+1) を形成するというように，エリアとエリア IDを階層的に考えることでピアを位置によって分類する．
またネットワーク維持プロトコル (ネットワーク参加，外部リンク構築，エリア間移動，故障回復) によって各ピアがエリア間にリンクを構築し，ピアの移動や故障などにも動的に対応することができる．その結果，少ないトラフィック，最大でも log4 n(n は Lv1 のエリアの数)のホップ数で任意の領域までクエリを伝播できること，端末が故障した場合にも十分な検索性効率とレスポンス数を保証できることを示している．

図 2 R-Tree

3 LR-Net の提案
3.1

LR-Net の要素
検索領域を x, y 軸の二次元空間とし，エントリはそれぞれ座標 (x, y) を持つ. ノードは複数のエントリまたはノードをまとめる. ノードはノード内の全エントリまたは全ノードを包括する最小の矩形である．ノード内に含まれるエントリの数が一定範囲内であるため, 密度の濃い部分のノードは小さく, 薄い部分は広くといったようにエントリの分布に応じてノードの大きさが変化する. 図 3 のように一定の数のエントリをまとめたノードを Lv0 のノードとし，Lv0 ノードを複数まとめたノードを Lv1 という形で, ノードを階層的に考える．エントリの分布具合によってはノードが重複する可能性もあるが, ノードの重複は認められる．

2.2 R-Tree [3]R-Tree は図 2 のように空間上の点をクラスタリングできるような適当な矩形 (MBR:Minimum BoundingRectangle) でまとめ，それらの矩形を階層状 (木状) にして管理する．MBR に重なりが許容されており，それによって動的な環境においても木の平衡を維持することが可能である．しかし，領域に重なりがあることで，探索結果に重複が生じる．また挿入と削除, 検索を混合す

図 3 ノードと階層構造

3.2 LR-Net の検索方法
LR-Net では任意の領域を指定してクエリを送ること数を増加，ノードを動的に階層化する必要がある．

が可能である．これにより，ある場所の端末から情報を取得したり，付近の端末の検索をすることが可能である．
3.3 LR-Net の維持
エントリの動き (追加，削除，故障) に対応し動的なネットワークを維持する．

4 LR-Net と LL-Net との比較評価
1. ピア数固定 (10,000)+ エリア数変化 (4〜3000)• 検索成功率• 検索エリアまでの平均ホップ数 (図 4)• 検索 1 回あたりのトラフィック (図 5)による LL-Net との比較を行い，
2. ピア数変化 (10,000・20,000・40,000)+ エリア数変化 (4〜2000) (表 1)• 検索エリアまでの平均ホップ数• 検索 1 回あたりのトラフィックを計測した．
図 4 より，LR-Net はエリア数が 4 のときに限り，LL-Net よりもホップ数を抑えることができる．図 5 より，検索 1 回あたりのトラフィックにおいては，LL-Netよりも 55-80% の範囲でトラフィックを抑えることができる．両ネットワークは，ともにフラッディングする領域を任意の範囲に抑えることができるが，LL-Net ではピアの偏りによりフラッディング対象となるピアが大量に存在し，大量のトラフィックが発生する．しかし
LR-Net では範囲内に存在するエントリ数は一定である
ため，ノード内でのフラッディングにおけるトラフィック量は限られている．そのため，LL-Net に比べ少ないトラフィック量で検索できるという結果になったと考えられる．表 1 より，ホップ数は 64 まではエントリ数に

図 5 検索 1 回あたりのトラフィック

表1LR-Net のエントリの増加を考慮したシミュレーション結果
エントリ数

10000

20000

40000

葉ノード数

ホップ

トラフィックホップ

トラフィックホップ

トラフィック

41664250
1000
2000

28322416141249
31111145221728324420182499
633
189843623283212533234996
1256344205
53345 考察
本論文では端末の位置情報に基づく P2P ネットワー
ク LR-Net を提案し，シミュレーションによって評価した．
LR-Net はコンテキストアウェアサービスにおいて重要なコンテキストとなる位置をキーとする検索を行うことができる．シミュレーション評価によって，LR-Net
は LL-Net に比べて，ホップ数はについては劣るが，トラフィックにおいては 55-80% の範囲で，常に少ないトラフィックを維持することができることを示した．今後の課題としては，ネットワークへのエントリの追加と削除，故障した場合のシミュレーション結果の比較や，
R-Tree の派生型である R+-Tree や R*-Tree，RS-Tree，
SS-Tree を用いた領域分割でのネットワーク構築をした場合のシミュレーション評価などがある．

参考文献
図4

平均ホップ数関わらず同値で，それ以降はエントリ数によって変化する．また，エントリ数がある値になるまでは増加し，それを超えると次第に減少している．その値もエントリ数に比例して増加する．トラフィックはピア数に比例して増加する．LR-Net では検索の際に，目的ノードでクエリをフラッディングするため，ノード内のエントリ数に伴い検索あたりのトラフィックも増加する．トラフィッ
クの増加を抑えるためには，エントリ数に応じてノード[1] M. Miller，P2P コンピューティング入門，トップス
タジオ (訳)，翔泳社，2002．
[2] 金子 雄，春本 要，福村 真哉，下條 真司，西尾 章
治郎，“位置情報に基づく P2P ネットワークにおけるエリアの階層化”，電子情報通信学会第 16 回
データ工学ワークショップ論文集，1B-o1，2005.
http://www.ieice.org/iss/de/DEWS/DEWS2005/procs/papers/1B-o1.pdf (accessed 2005.9)[3] A. Guttman, “R-Trees: A Dynamic Index Structure For Spatial Searching,” Proc. ACM SIGMOD, pp.47-57, 1984.