ノード位置を用いたP2Pモデルのためのドロネー図の自律分散生成アルゴリズム

機関リポジトリ 情報処理学会 HANDLE Web Site 被引用文献13件 参考文献14件

書誌事項

タイトル別名
  • ノード イチ オ モチイタ P2P モデル ノ タメ ノ ドロネーズ ノ ジリツ ブンサン セイセイ アルゴリズム
  • Autonomous and Distributive Generation Algorithm of Delaunay Network for P2P Model Utilizing Node Location

この論文をさがす

抄録

本稿では,スケーラブルなネットワーク基盤として,計算幾何の分野で知られるドロネー図をトポロジとして持つP2Pドロネーネットワークとその自律分散生成アルゴリズムを提案する.ここでは,まず本P2Pドロネーネットワークの特徴について述べ,次に生成アルゴリズムについて述べる.提案アルゴリズムは,各ノードの局所的な動きから,ノード間の幾何学的な位置関係を利用して接続関係を更新し続けるアルゴリズムであり,さらにノードが相互に情報交換することでネットワークを構成できる特徴を持つ.また,ノードが幾何学的退化状態にある場合も動作できる.本アルゴリズムにより,与えられた2つのP2Pドロネーネットワークを融合することも可能であり,P2Pパラダイムの持つスケーラビリティを活かしながら,システムの対象空間を段階的に拡張できる.提案アルゴリズムでは,ノードの3つの操作を定義している.すなわち,局所ドロネー化操作と三角化通知操作が,局所的なドロネー図を自律分散的に生成し,委譲操作により,ノード間でノード情報の情報交換を行う.最後に, 数値シミュレーションにより,P2Pドロネーネットワークの形成過程を,ノードへの負荷,P2Pドロネーネットワークへの収束ステップ数,各ノードの次数の変化,ネットワーク負荷などから検証し,提案アルゴリズムの有効性を確認する.また,本アルゴリズムの適用性についても議論する. 　　 This paper proposes a P2P Delaunay network whose topology is a Delaunay diagram wellknown in computational geometry as a scalable network infrastructure for spatial data management. We first discuss its features as a P2P network, and propose an algorithm to construct the network autonomously and distributively in P2P settings. In the proposed algorithm, nodes update their connection defined by node adjacency with respect to geometric location and generate local Delaunay networks of neighboring nodes, while they exchange node-location information to generate a network. The algorithm also works for the case nodes locate in geometrical degeneracy. Furthermore, the algorithm can also be applied to merging two independent P2P Delaunay networks. Owing to the algorithm, we can manage large target spaces using the P2P paradigm, and furthermore extend the target space incrementally by utilizing scalability that the P2P paradigm possesses. By numerical simulations, the authors examine the construction process of P2P Delaunay networks in terms of loads of nodes, time-steps consumed for constructing P2P Delaunay networks, degree of each node, and networkload cost. The applicability of the proposed algorithm for P2P models is also discussed.

収録刊行物

被引用文献 (13)*注記

もっと見る

参考文献 (14)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ