著者

大西真晶 源 元佑太 江口 隆之 加藤宏章 西出 亮 上島 紳一

出版者

情報処理学会

雑誌

情報処理学会論文誌データベース(TOD) (ISSN:18827799)

巻号頁・発行日

vol.47, no.4, pp.51-64, 2006-03-15

被引用文献数

13

---

本稿では,スケーラブルなネットワーク基盤として,計算幾何の分野で知られるドロネー図をトポロジとして持つ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 y utilizing scalability that the P2P paradigm possesses. By numerical simulations, he authors examine the construction process of P2P Delaunay networks in terms of loads of odes, time-steps consumed for constructing P2P Delaunay networks, degree of each node, nd networkload cost. The applicability of the proposed algorithm for P2P models is also iscussed.