論文

Journal of the DBSJ Vol.7, No.1

P2P 型ジオキャストのための階層
ネットワークの提案と評価
Generating Hierarchical Network for P2P
GeoCast1.

はじめに

最近, ノードの位置を利用した P2P ネットワークに関する研究が注目を集めている [1, 2, 3, 4]. 特に, 指定した地域内のノード群に通信を行うジオキャストは, 固定資源を持たない MANET
環境 [5, 6, 7], 仮想共有空間システム [8], 基盤ネットワークのオーバーレイなど, 多くの領域での有用性が指摘されている.

奥 智照 ♥
上島 紳一 ♠

西出 亮 ♦

Tomoteru OKU
Shinichi UESHIMA

Ryo NISHIDE

本稿では, 平面上に存在するノード間を低ホップ数で結ぶ Skip

Geo Network(SGN) とその分散構成アルゴリズムを提案する.
SGN は, Skip Graph を用いた論理ネットワークとノードの位置関係により構成されるドロネーネットワークのハイブリッド構造を持ち, 各ノードはより近いノードから遠方ノードへのリンクをこれらの観点から, 我々もノードの位置関係を利用した幾何的なトポロジーを持つ P2P ドロネーネットワークを提案している[9]. このネットワークは, 平面上のノードの隣接関係に基づいて構成されるため, ノード数に増加に対するスケーラビリティに優れ, ノードの参加・脱退に対して弾力性を持つ．更に, 遠隔ノード
へのアクセスに対して, 各ノードのボロノイ領域の幅を基準とした遠隔接続経路 (以下, 幅 LRC) の P2P 方式による構成法を提案し, 任意の 2 地点間でホップ数を一様化する試みを行った [10].
しかし, 各ノードはボロノイ領域の幅に応じて通信先ノードを決定しており, ノードの参加・脱退を行う際に, 幅内に存在するすべてのノードに通信及び幅 LRC の修復が影響するため, 再構成
コストが高いという問題が残されていた．

持つことができる. SGN を用いて, 相手ノードを指定した通信

この問題を改善するため, 本稿では, 遠隔ノードへの経路構成に加えて, 目的位置や領域を指定したジオキャスト（Geocast）に, Skip Graph[11] とドロネーネットワークの両方を同時に用を行うことができる．SGN は, ノード間で P2P 型通信によりアいた Skip Geo Network（以下, SGN）を提案する. SGN は,

ドホックにネットワークを構成できるため, 移動体通信，緊急時

ハイブリッドなネットワーク構造を持ち, ノードの論理識別子かの情報散布などへ応用することができる. 最後に, 提案手法の有ら構成される論理ネットワークと, 平面上のノードの位置座標を

効性を確認するために数値シミュレーションにより, SGN のネッ

用いたドロネーネットワークの両者を連携させて階層化した構造

トワークの特性とジオキャストの性能などについて検証する.

を持つ．特に, SGN では, 各ノードが自律的にランダムに階層化
し, それぞれのレベルの階層を担当するノード集合が, そのレベIn this paper, we propose Skip Geo Network(SGN), which is a scalable geographic networkthat connects computational entities or nodes ina 2D space by low P2P hop counts. SGN has ahybrid structure of logical networks and Delaunay
networks generated using geographical coordinates
where nodes reside. In SGN, each node has a longrouting paths compared to method without SGN,
which can enable Geocast to speciﬁed points or regions with low hop counts. SGN can be generatedby P2P communication among nodes in ad-hoc network, and we expect that it is applicable to locationoriented systems, such as mobile hosts in MANET.
We propose an autonomous generation algorithm of
SGN and evaluate network parameters and geocast
parameters of SGN by numerical simulations.
♥♦♠

ルでドロネー隣接性に基づいてドロネーネットワークを自律分散生成する．この構造により, 上位層ネットワークになるほど担当
するノード数が減少し, 少ないノード数のドロネーネットワークが構成され, 結果的に, より遠隔地へのリンクを与えている．
次に, SGN を利用して幾何的な経路選択法を定義し, 地理的な座標や範囲を指定した P2P 型ジオキャストの実現法を与える.
ここでは, 各ノードが, SGN での接続先ノードの位置情報を用いて, 仮想ボロノイ図を計算して転送先を決定する．最後に，提案手法の有効性を確認するために, SGN の幾何学的データ特性や
幅 LRC との比較, 更に幾何的経路選択法を用いた遠隔ノードへのアクセス特性などを数値的に評価する．

2.

SGN の生成2.1

ノードの前提ノードは以下の条件を満たすものとする.

1. ノードは, 自律的で等価な通信主体であり, 自身の論理 ID な
らびに平面上の位置情報を保持する．

学 生 会 員関 西 大 学 大 学 院 総 合 情 報 学 研 究 科

fb8m121@edu.kansai-u.ac.jp
学 生 会 員関 西 大 学 大 学 院 総 合 情 報 学 研 究 科

fa4d003@edu.kansai-u.ac.jp
正 会 員

関 西 大 学 大 学 院 総 合 情 報 学 研 究 科

2. ノードは, 隣人ノードの論理 ID ならびに平面上の位置座標を隣人表に保持し，隣人ノードのみと通信可能とする．

3. ノードは基盤ネットワークの上に存在し, オーバーレイネッ
トワークを定義できるものとする．

ueshima@edu.kansai-u.ac.jp1

日本データベース学会論文誌 Vol.7, No.1

論文

Journal of the DBSJ Vol.7, No.1

図 1 SGN:環状の論理ネットワーク群と対応する P2P ドロ
ネーネットワーク群

Fig. 1 SGN: hybrid hierarchical structure of ring logicalnetworks and the corresponding P2P delaunay networks
図2

全階層ドロネー隣人の射影と仮想ボロノイ図

Fig. 2 Union of delaunay neighbor nodes of all levels andwithout hierarchy on a geographic plane

2.2

論理ネットワークと平面ネットワーク

P2P ドロネーネットワークでは, 隣人ノードがノード間の地
理的な隣接関係によって決定されるので, 局所的なノード分布

ネットワークの生成を繰り返して, ネットワークを階層化すの粗密に依存せず, 安定的な次数を持つネットワークを構成でき

る．最後に, 論理ネットワークの要素が 1 つになるまで, 両る特徴がある [9]. 一方, 遠隔ノードの経路として構築された幅LRC[10] では, ノードの偏った分布の際に負荷が集中するノードが存在することや, 再構築負荷が大きいなどの問題点があった.
これらの問題点を克服するため, Skip Graph[11] の確率的な階層化手法を導入することで, Skip Graph のノードの論理 ID

方のネットワークを階層化し, 階層化を停止する．

を用いた論理ネットワークと位置情報を用いたドロネーネット
ワークの両者を連携させて構成することを考える．それにより,上位階層でより少ないノード間のドロネー隣接関係に基づくトポ
ロジーを生成して, 平面上の遠隔ノードへ接続することを考える．
本稿では, 連結性を保証する Skip Graph の論理ネットワークの階層化を行ない, 次に各層でできる論理サブネットワークをもとに, 平面上のドロネーネットワークを自律分散生成アルゴリズ
ムにより構成する．詳細な構成手順を次節に述べる．

2.3

SGN の構成手順

以下に, SGN の構成手順を示す．

• すべてのノードが論理 ID により環状ネットワークを形成しているものと仮定する（図 1 左の最下層（レベル 0））．
• [初期論理ネットワークから空間ネットワークの生成] まず,
この論理ネットワークの連結性を用いて, ノード群が位置座標を交換し, 互いのドロネー隣接関係を導出して, 対応する層での幾何ネットワークトポロジーを決定する (図 1 右).
• [論理ネットワークの階層化] 次に, 初期の論理ネットワーク
において, 各ノードが独立に確率 1/2 で直上の 2 つの論理部
分ネットワークに分化する．つまり, 各ノードに論理 ID の各ビットを前から調べ, 2 つの上位階層のいずれかへの参加を決定する．次に, 論理ネットワークの連結性を用いて, ノード間で通信を行い, 2 つの論理サブネットワークを構成する．
• [空間ネットワークの生成] それぞれの論理サブネットワークの連結性を用いて, ノード群が位置座標を交換し, 互いのドロネー隣接関係を導出して, 対応するレベルの層でのノード間の幾何ネットワークトポロジーを決定する．

• [順次的な階層化] この論理サブネットワークの階層化と空間2

上記手順では, 初期の環状ネットワークから開始して, 論理ネッ
トワークと P2P ドロネーネットワークを順に作成する．レベル

i では, 2i 個の論理ネットワークを用いて, 2i 個のドロネー部分
ネットワークを自律分散生成する（図 1 の（レベル i））．
図 1 に, 論理ネットワークと平面ネットワークの対応を示す.
左図が階層化された論理ネットワークであり, 各レベルにおいて環状の論理サブネットワークをもとに, 右図の P2P ドロネーネッ
トワークを自律分散生成している様子を示す．論理ネットワーク
では, レベル 0 のノードが, レベル 1-0 とレベル 1-1 の部分ネッ
トワークに分化し, 更に, レベル 1-0 ネットワークは同様にレベル 2-00 とレベル 2-01 のネットワークに分化している．一方, 平
面上でドロネーネットワークが同数の論理ネットワークが生成されている．図 1 では, 7 つの階層化論理ネットワークと 7 つの階層化ドロネーネットワークがそれぞれ得られている.

2.4

ノード参加・脱退における SGN 修復

本節では，ノードの参加脱退に対する SGN 修復方法について述べる．ただし，SGN の論理ネットワーク部分は Skip Graphの修復アルゴリズムによる [11]．

[ノードの参加] ノードが新規参加する場合は，まず論理ネット
ワークに参加した後，論理ネットワークの接続関係を利用して，各層のドロネーネットワークに参加することにより SGN の構成を維持する．つまり，新規ノードは各層のドロネーネットワークとの接続関係を持つことにより，個別に修復する．

[注] 提案手法は，修復された論理ネットワークの連結性を利用して，階層数分のドロネーネットワークに参加する形になる．つまり，各層のドロネーネットワークを一から作り直す訳ではない．

[ノードの脱退] ノードが脱退する場合は，各層のドロネーネット
ワークにおいて，ノードの位置関係に基づきドロネー隣接関係を導出することにより，ネットワークを修復する．つまり，ノードの脱退の際には階層数分のドロネーネットワークを個別に修復することにより構成を維持する．

日本データベース学会論文誌 Vol.7, No.1

論文

図3

Journal of the DBSJ Vol.7, No.1

3 つの仮想ボロノイ図（濃い実線）とボロノイ図（薄い実線）

Fig. 3 Three distinct virtual voronoi diagrams(thick)and voronoi diagram(thin)
図4

仮想ボロノイ図を用いた経路選択法

Fig. 4 Routing method using virtual voronoi diagrams[注] ノード参加の際は，論理ネットワークと連携しドロネーネッ
トワークの構成を維持するが，ノード脱退の際は，論理ネット
ワークと連携せずに個別に修復する．

2.5

SGN の特徴

SGN では, 各層において Skip Graph を用いた論理ネットワー
クから平面上の P2P ドロネーネットワークを生成しているため,
次の特徴を持つ．

• ノードの論理 ID と空間内の位置座標を用いたハイブリッド型ネットワーク構造となっている．従って論理 ID と位置座標のいずれの識別子を用いた通信も可能である．

• 各ノードが各レベルにおいて自律的に確率的階層化を行うことで, 平面上のノードの分布に応じたノード配置を得る.
• 各層のネットワークは, Skip Graph と P2P ドロネーネット
ワークの持つ性質を継承しているため, ノードの新規参加・脱退が容易であり, 局所的な影響に留まる.
• 上位層のドロネー隣人は下位層のドロネー隣人に比べ, より
遠方のノードへの接続関係となり, より遠隔地への幾何学的
経路選択ができる (図 2).
• SGN は, 平面上でノードの分布に依存せず自律分散的に生成でき, ノードが密に分布する部分ではより細かいノード間接続が得られ, 疎に分布する部分ではいノード間接続が得られる. 従って, 幾何学的経路選択を用いても, 特定のノードにアクセスが集中しない.

3.

ジオキャストへの利用

3.1

仮想ボロノイ図

本節では, 仮想ボロノイ図と SGN を用いた経路選択について述べる．仮想ボロノイ図とは, 各ノードがそれぞれに SGN の各層の平面ネットワーク部分であるドロネー隣人ノードすべての位
置情報を用いて, 各ノード自身が生成するボロノイ図である（図2）．つまり, 各ノードが独立に自身の持つ隣人情報を用いて生成する図である．
仮想ボロノイ図は, 次の特徴を持つ．

1. 各ノードの生成する仮想ボロノイ図は, 通常のボロノイ図と同様に, 平面全体を分割し仮想ボロノイ領域を生成する．つまり, 仮想ボロノイ領域集合が平面全体を被覆する (図 2)．

32. 各ノードの持つ隣人が異なるため, 各ノードで生成される
仮想ボロノイ図はそれぞれ異なる．また, 全平面に存在するノードに対して定義されるボロノイ図（以後, 単にボロノイ
図という）とも異なる (図 3)．

3.2

仮想ボロノイ図を用いたジオキャスト

与えられた目的地や目的領域に対して, ノードがジオキャストを行う場合, 各ノードは各自の持つ仮想ボロノイ図を用いて転送先ノードを選択し, ノード間をマルチホップ形式で通信を行う．

[地点へのジオキャストにおける経路選択法]
まず, 出発ノード vs に対して, 目的地として平面内の位置 d が与えられたと仮定し, vs から d をボロノイ領域に含むノードへの経路を選択する場合について考える．
各ノードは次の手順により経路選択を行う．即ち,

1. vs は自身の仮想ボロノイ図を生成し, d を含む仮想ボロノイ領域を持つ隣人ノード v1 を転送先として選択する．仮想ボ
ロノイ図の性質により, 各層のドロネー隣人ノードの中で dに最も近いノードを一意に決定できる（図 4）．
2. v1 は, 自身の仮想ボロノイ図を生成し, d を含む仮想ボロノ
イ領域を持つ隣人ノード v2 を選び, v2 を転送先とする．
3. 以下, 同様にして, vs からの経路を v1 , v2 , v3 , . . . , vm を決定する．ここで, vm は, 含む全ノードから構成されるボロノイ図（仮想ボロノイ図ではない）において, d をボロノイ領域に含むノードである．
上記の手順を用いて, vs から目的地点をボロノイ領域を持つノードへ必ず到達することが次のようにして確認できる．つまり, SGN では, 各ノードは, 目的地 d までの残存距離を自身の隣
人ノードの中で最小になるような隣人を決定するため, ホップ数が増えるとともに, 残存距離は単調に減少する．従って, ある mが存在して, vm のボロノイ領域が d を含む．SGN では, 最下層(レベル 0) において, 各ノードがドロネー隣人ノードを隣人表に格納しているために, レベル 0 では, d の近傍のノードが存在する．よって vm への経路が存在することになり, vm へ必ず到達することができる．
つまり, SGN では, 最下層で接続性を保証しながら, 上位層で日本データベース学会論文誌 Vol.7, No.1

論文

Journal of the DBSJ Vol.7, No.1

図 5 再帰的な転送による領域へのジオキャスト

図 6 N に対する SGN の層数の平均

Fig. 5 Reﬂexible and dynamic generation of multicast tree in GeoMultiCast

Fig. 6 Average count of node layer

1 ホップあたりの距離を増加させている．ノード vs から出発して, 各ノードが局所的なボロノイ図とドロネー図を用いて転送先を選択しながら経路を決定し, 当該平面上のすべてのノード集合
に対する大域的なボロノイ領域を持つノード vm へ到達させるこを行う対象領域が重複している R03 を新たな対象領域として受とができる点が特徴である．

のボロノイ領域内に対象領域が収まるまで転送を繰り返す．

[注] vm への到達までのホップ数 m は, ノードの平面上の分布状
況や, SGN を生成する際のランダム選択確率 p に依存する．
[領域へのジオキャストのデータ転送法]
次に, 与えられた対象領域に対するジオキャストのデータ転送

け取った v4 は v4 自身が生成した仮想ボロノイ領域と新たな対象領域とが重複するノードである, v6 ,v7 ,v8 ,v9 に対して，同様に対象領域を変更しながら転送を行う (図 5(Step2))．最終的に自身提案手法の領域へのジオキャストでは，転送元ノードの仮想ボ
ロノイ領域を基準にデータの対象領域が分割され転送される．これは，転送先のノードが転送する対象領域を転送元ノードの仮想
ボロノイ領域内とすることにより，冗長な転送を抑制するためで法について述べる．領域を点の集合と考えることにより，対象領ある．それにより，転送元の仮想ボロノイ領域内かつ，初期の対域へのジオキャストの経路選択法は，地点へのジオキャストと同象領域内のノードにのみ転送を行うことにより，転送を経るごと様に行うことができる．しかし，対象領域へのジオキャストは地に対象領域は単調に小さくなる．ＳＧＮでは，各ノードのボロノ点へのジオキャストの経路選択に加え，対象領域とボロノイ領域

イ領域内に対象領域 (点の集合) が含まれない限り，対象領域にが重複する複数のノードに対して転送する．そのため，領域への対してより近いノードが存在する. また，地点へのジオキャスト

ジオキャストでは，転送データに対象領域の情報を付与する．

では，レベル 0 のドロネーネットワークにおいて，仮想ボロノイ

まず, 出発ノード v0 に対して, 目的領域 R0 が与えられたものとする. R0 への転送は以下の手順により行われる．

1. v0 は自身の仮想ボロノイ図を生成し,R0 と仮想ボロノイ領
域が重複する隣人ノード集合を転送先として決定する.
2. 転送元ノード v0 は転送先ノードの 1 つである v1 に対して，
v0 が生成した v1 の仮想ボロノイ領域との重複領域を v1 に対する新たな対象領域 R01 として転送する. 同様に, 他の転送先ノード集合に対してもそれぞれの重複領域を転送する.
3. 以下同様に，R01 を受け取った v1 は自身の仮想ボロノイ領
域から R01 と領域が重複している候補ノードである v2 に対して転送を行う．このような手順で対象領域を受け取った各ノードが再帰的に転送を行い，最終的に，レベル 0 ボロノイ領域内に対象領域全体が収まるまで転送を繰り返す．

図を用いてより近いノードに対して転送を繰り返すことにより，データの到達性は保障できる. そのため，自身のボロノイ領域内に対象領域が含まれない限り，転送を繰り返すことにより，対象領域へのジオキャストにおいてもデータの到達性が保障できる．

4.

シミュレーションによる評価

本章では, SGN 生成のための構築コスト, 再構成コスト, ならびに構築後の SGN のネットワーク特性, 利用時の効果について評価する. ここでは, ノード総数を N とし, ノードを [0,1] ×[0,1] の正方領域に一様分布させる．また, 各ノードが各レベルで行う自律的な階層化の確率を 1/2 とする．

4.1

SGN の幾何学的特性

本節では提案手法である SGN の平面ネットワーク部分におけるネットワーク特性について評価する．

図 5 は対象領域 R0 へ転送が行われる例を示す．図 5(Step1)

4.1.1

SGN の層数の短形領域 R0 は転送を行う対象範囲である．まず, 転送を行う

図 6 に, ノード総数 N に対する SGN 構築後の各ノードの層

ノード v0 は v0 が生成した仮想ボロノイ図の中で対象領域 R0

数の平均を示す. 確率 1/2 で上位層の同一空間に存在するノードを含むノードである, v1 ,v2 ,v3 ,v4 ,v5 を転送先ノードとして決定を選び出すため, 層数の平均は N の指数的な増加に対して一定する．これらの転送先ノードの中でも特に，v1 に R00 を, v2 にの増加になっており, log(N ) に比例している.

R01 のように，対象領域と v0 の持つ転送先ノードの仮想ボロノ

4.1.2

1 ホップあたりの距離

イ領域が重複してる領域を新たな対象領域として各転送先ノード

各階層毎にネットワークの地理的直径に対する 1 ホップの距離に転送する．v0 が生成した, v4 の仮想ボロノイ領域と v0 が転送の平均を図 7 に示す. 各 N において, 階層の増加に伴い 1 ホップ

4

日本データベース学会論文誌 Vol.7, No.1

論文

図7

Journal of the DBSJ Vol.7, No.1

N に対する 1 ホップの地理的距離の平均
Fig. 7 Average Distance of 1-hop

図 10

図8

図 9 ノード次数の平均と最大

Fig. 8 Network diameter vs N

再構築の影響ノード数

Fig. 10 Nodes Aﬀected by Net. Repair

N に対するネットワーク直径

図 11

Fig. 9 Average/maximum node degree

再構築の通信回数

図 12

Fig. 11 Transfer Counts for Net. Repairの距離は指数的に増加し, log(N ) レベル付近から増加が収束に

4.2.1

N に対するホップ数の平均と最大

Fig. 12 Average of hop counts vs N

ノード次数

向かっている. これは, 階層化時に新たなドロネー隣人に接続で

図 9 に, N に対するノード次数の平均および最大値を示す．

きる場合は, より地理的に遠距離ノードと接続できるが, 階層レ

ネットワーク直径として, 任意 2 点間で仮想ボロノイ図を用いて

P2P ドロネーネットワーク単体におけるノードの次数は, ドロネー図の幾何学的特徴を示して，N に関わらず平均が 6 程度である．一方，SGN の場合は, 次数の平均と最大は N の指数的な増加に対して一定の増加となっている. これは, 各層でドロネー
ネットワークを構成しドロネー隣人を選出しているため, 層数の増加に比例した値となることによる. また，従来手法である幅
LRC も，N の指数的な増加に対して一定の増加となっている．

経路選択を行ったときの最大ホップ数経路をとる. 任意 2 点間の4.2.2

ベルが log(N ) 付近では隣人が減少するのみであることによる．
以上より, 階層化することにより平均的に 1 ホップの地理的距離が長くなっていることが確認できる.

4.1.3

グラフ特性

図 8 に, N の増加に対するネットワーク直径を示す. ここでは,最短ホップ数経路の最大値ではない.
階層化しない場合, ネットワーク直径は N の増加に比例して再構築コスト

図 10, 11 に 1 ノードの参加と脱退におけるネットワークの修復に要する負荷について計測した．

増加しており, N =8192 のとき 118 であった. これは, N の増加[参加・脱退にかかる影響ノード数] 図 10 は 1 ノードの参加と脱により, 2 ノード間の経路上に存在するノード数が増加するため

退における修復の際に，接続隣人ノードの変更が及んだ影響ノーである. 一方, 階層化する場合, N の指数的な増加に対し一定のド数を示す．従来手法である幅 LRC では，ボロノイ領域幅を基増加に留まっており, N =8192 のとき 12 であった. これにより,準として，水平垂直方向に存在する全ノードと協調して生成して階層化によりネットワークの直径を log(N ) 程度に下げられたこいる．そのため，ノードの新規参加脱退に対して幅内の全ノードとが確認できる.

に対してネットワーク修復の影響が及ぶ．それに対し，提案手法

4.2

では階層化したドロネーネットワークの各層が独立にネットワー

提案手法と幅 LRC との比較評価

本節では，従来手法である幅 LRC との性能比較を行い SGNクを修復する．つまり，各層のドロネーネットワークにおいて接の有効性を示す．なお，本節では SGN の平面ネットワーク部分

続が修復されるノードにのみ修復の影響が及ぶ．また，ドロネーとの比較を行うものとし，SGN の論理ネットワークである Skip

ネットワークの修復は局所的に収まるため，影響ノード数は低く

Graph の生成や修復コストに関しては考慮しない．

なると期待できる．以上の理由により，図 10 において提案手法
は，幅 LRC に比べて影響ノード数が小さくなることがわかる．

5

日本データベース学会論文誌 Vol.7, No.1

論文

Journal of the DBSJ Vol.7, No.1

[参加・脱退にかかる通信回数] 図 11 は N に対する，ノードの参

本稿では,P2P ドロネーネットワーク上において平面上の遠隔

work Computing and Applications, pp.39–46 (2004)[2] 金子雄，春本要，福村真哉，下條真司，西尾章治郎．ユビキタ
ス環境における端末の位置情報に基づく P2P ネットワーク．
情報処理学会論文誌データベース, vol. 46, pp.1-15 (2005)[3] Xiang-Yang Li, Calinescu, G. , Peng-Jun Wan, Yu Wang,“Localized Delaunay Triangulation with Application in
Ad Hoc Wireless Networks”, IEEE Trans. Parallel Distrib. Syst., Vol.14 No.10, pp.1035–1047 (2003)[4] I. Stojmenovic, “Position-Based Routing in Ad Hoc Networks”, IEEE Commununications Magazine, Vol. 40,
pp.128–134 (2002)[5] Navas, Julio C. and Imielinski, Tomasz, “GeoCastGeographic Addressing and Routing”, Mobile computing
and networking, pp.66–76 (1997)[6] Young-Bae Ko and Nitin H. Vaidya, “GeoTORA : A Protocol for Geocasting in Mobile Ad Hoc Networks”, Proc.
Int’l Conf on Network Protocols 2000, pp.240–250 (2000)[7] Tsuboi, S., Oku, T., Ohnishi, M., and Ueshima S., “Generating Skip Delaunay Network for P2P Geocasting”, 6th Int’l Conf. on Creating, Connecting and Collaborating
through Computing (C5), pp.179–186 (2008)[8] Hu, S.-Y., Chen, J.-F. and Chen, T.-H., “VON: A
scalable peer-to-peer network for virtual environments”,
IEEE Network, Vol. 20 No. 4, pp.22–31 (2006)[9] 大西真晶，源元佑太，江口隆之，加藤宏章，西出亮，上島紳一, “ノード位置を用いた P2P モデルのためのドロネー図の
自律分散生成アルゴリズム”, 情報処理学会論文誌：データ
ベース, Vol. 47 No. SIG4(TOD29), pp.51–64 (2006)[10] 大西真晶，坪井新治，平山雅夫，江口隆之，上島紳一, “P2P

ノードへのアクセスのために SGN を提案し, 仮想ボロノイ図をドロネーネットワークにおける遠隔接続経路の自律分散生

用いたジオキャスト手法について提案した．提案手法は, 確率的成法”, 情報処理学会論文誌：データベース, Vol. 48 No.

な階層化手法を導入しているため, 従来手法と比較して再構成コ

SIG11(TOD34), pp.190–214 (2007)[11] James Aspnes and Gauri Shah, “Skip graphs”, SODA
’03: Proc. 14th annual ACM-SIAM Symp. on Discretealgorithms, pp.384–393 (2003)

加・脱退の際の修復にかかる各ノードの通信回数の平均を示す．
・脱退：提案手法におけるノードの脱退は，各層で構成されたド
ロネーネットワークの近接関係により修復する．そのため，ネッ
トワーク修復の通信は局所的に留まる. 一方，幅 LRC ではボロノイ領域幅を基準として，水平垂直方向の全ノードに通信が及ぶ
ためネットワークの修復の通信回数が大きくなる．
・参加：提案手法におけるノードの参加は，参加した論理ネット
ワークの隣人と自身の位置関係により，ドロネー構築の際に委譲の回数が増加し，通信回数が増大する．そのため，修復にかかる通信が局所的に収まる脱退時とは異なり，通信回数は大きくなる．しかし，図 11 では幅 LRC に比べると低く抑えられている．
以上の理由から，提案手法では，幅 LRC に比べてノードの新規参加や脱退に対するネットワークの再構築が容易であり，ネッ
トワークの弾力性があるといえる．

4.2.3

任意 2 点間のジオキャスト

任意の 2 ノード間でジオキャストを行い, ホップ数の計測し比較した. N を変化させたときのすべての 2 ノードの組み合わせ
で計測を行い, 提案手法，幅 LRC 及びドロネーネットワーク単体のホップ数を計測した（図 12）. なお，提案手法は仮想ボロノイ図を利用した経路選択手法を用いた．
ホップ数の平均は, ドロネーネットワーク単体の場合は N の指数的な増加に比例して増加しているのに対し, 提案手法及び幅

LRC の場合は，一定の増加に留まっている. このことから, 提案
手法は幅 LRC と同様に，任意の 2 ノード間を log(N ) ホップでジオキャストできることが確認できる.

5.

おわりに

ストが小さく, ノードの影響範囲が局所的に留まることをシミュ
レーションにより示した．これによりネットワークの弾力性が期待できる. SGN により，地理的な位置に即したアドホックネッ
トワークを構築することが可能になり，MANET への応用が期

奥 智照 Tomoteru OKU

待できる. 今後の課題として, 領域へのジオキャストの評価や実2008 年関西大学総合情報学部卒業．現在，同大学院総合情報学研究科博士前期課程在学中．P2P ネットワークに関する研利用環境での SGN の性能評価などが必要である．

[謝辞]

究に従事．情報処理学会，日本データベース学会各学生会員．

西出 亮 Ryo NISHIDE

評価に用いたドロネー図生成，幅 LRC，SGN のプログラムの2004 年関西大学大学院総合情報学研究科博士前期課程修了．

一部は，大西真晶氏らにより作成された．ここに記して謝意を表

現在，同大学院博士後期課程在学中．仮想空間の高度利用，する．本研究の一部は，文部科学省私立大学学術研究高度化推進

P2P システムの研究に従事．IEEE，ACM 等各学生会員．

事業オープン・リサーチ・センター整備事業の支援を受けた．

上島 紳一 Shinichi UESHIMA[文献][1] F. Araújo, L. Rodrigues, “GeoPeer: A Location-Aware
Peer-to-Peer System”, Proc. 3-rd IEEE Int’l Symp. Net-6

関西大学総合情報学部教授．1983 年京都大学大学院工学研究科博士課程単位取得退学，工学博士．マルチメディア情報シ
ステムの研究，柔軟な情報ベースに関する研究に従事．情報処理学会，電子情報通信学会，IEEE，ACM 等の会員．

日本データベース学会論文誌 Vol.7, No.1