P2Pドロネーネットワークにおける遠隔接続経路の自律分散生成法 Building Long Range Contact over P2P Delaunay Network Distributively

この論文にアクセスする

この論文をさがす

著者

抄録

本稿では,P2Pドロネーネットワークにおける遠隔接続経路群(LRC)の自律分散生成法および遠隔地点への経路選択と範囲問合せへの適用について述べる.ドロネー図の構造を持つオーバレイネットワークであるP2Pドロネーネットワークでは,各ノードは近傍ノードのみと接続する.この特徴は地理的な経路選択や範囲問合せに有効である.しかし,ノード数の増加に対してネットワークの直径が増大するため,遠隔ノード間の通信や広範囲の問合せに要するクエリのホップ数が増大し,通信遅延が生じるという課題が残されていた.そこで,空間全体にLRCを構成することで2ノード間のホップ数を低減する.我々は,平面上の各ノードが,ホップ数に基づいた水平/鉛直方向の経路を協調的に生成することで,平面全体へのLRCを完成させるボトムアップな生成法を与える.この水平/鉛直のLRCを用いた経路選択法,効率的な範囲問合せ法を提案する.さらに,ノードの参加・離脱時に,LRCを部分的に修正し構造を維持するアルゴリズムについて述べる.そして,数値シミュレーションにより,LRCの生成と維持にかかる負荷やLRCを用いた経路選択と範囲問合せの効果について検証した.また,応用システム例として災害時の被災者支援システムを提案し,実利用を想定したシミュレーションにより,LRCを組み込んだP2Pドロネーネットワークおよび関連システムのGeoPeerに対して2種類の構造を設定し,3者を比較評価した.In this paper, the authors propose an autonomous distributive generation algorithm of LRC (Long Range Contact) over P2P Delaunay network, and discuss on a routing method to distant location and on range query. In a P2P Delaunay network, which builds-in a Delaunay diagram as a topology using node location, a node has connections only with its neighboring nodes. This structural property has advantages for a geometric routing and range query mechanism among nodes. However, in case a P2P Delaunay network consists of a large number of nodes, its diameter increases which causes a serious communication delay in the wide area of range query. To overcome the problem, the authors show a method for nodes to construct LRC collaboratively in a bottom-up fashion both horizontally and vertically over a P2P Delaunay network to the entire target space, and provide algorithms for geometric routing as well as efficient range queries by use of horizontal/vertical LRC's. Moreover, algorithms for partial structural maintenance due to node join/leave are given. The authors examine the loads for generating/maintaining LRC, and the efficiency for routing and range query using LRC through numerical simulations. As a practical application, we set a scenario of a communication network for victims in a disaster area and rescue crues, and compare the efficiencies between the proposed system and two types of network topologies using GeoPeer numerically.

In this paper, the authors propose an autonomous distributive generation algorithm of LRC (Long Range Contact) over P2P Delaunay network, and discuss on a routing method to distant location and on range query. In a P2P Delaunay network, which builds-in a Delaunay diagram as a topology using node location, a node has connections only with its neighboring nodes. This structural property has advantages for a geometric routing and range query mechanism among nodes. However, in case a P2P Delaunay network consists of a large number of nodes, its diameter increases which causes a serious communication delay in the wide area of range query. To overcome the problem, the authors show a method for nodes to construct LRC collaboratively in a bottom-up fashion both horizontally and vertically over a P2P Delaunay network to the entire target space, and provide algorithms for geometric routing as well as efficient range queries by use of horizontal/vertical LRC's. Moreover, algorithms for partial structural maintenance due to node join/leave are given. The authors examine the loads for generating/maintaining LRC, and the efficiency for routing and range query using LRC through numerical simulations. As a practical application, we set a scenario of a communication network for victims in a disaster area and rescue crues, and compare the efficiencies between the proposed system and two types of network topologies using GeoPeer numerically.

収録刊行物

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

    情報処理学会論文誌データベース(TOD) 48(SIG11(TOD34)), 190-214, 2007-06-15

    情報処理学会

参考文献:  19件中 1-19件 を表示

被引用文献:  3件中 1-3件 を表示

各種コード

  • NII論文ID(NAID)
    110006317695
  • NII書誌ID(NCID)
    AA11464847
  • 本文言語コード
    JPN
  • 資料種別
    Article
  • ISSN
    1882-7799
  • NDL 記事登録ID
    8862343
  • NDL 請求記号
    Z74-C192
  • データ提供元
    CJP書誌  CJP引用  NDL  NII-ELS  IR  IPSJ 
ページトップへ