Vol. 0

No. 0

情報処理学会論文誌??? 1959

DTN 環境を想定したトポロジ変化に強いメッセージルーティング
落 合 秀 也†1

江 崎

浩†1

Delay (or Disruption) Tolerant Networks(DTN) の技術は，無線に代表される通信回線が不安定
なネットワークで効率よくメッセージを配送する技術として有望視されている．ただ，DTN の想定する環境ではネットワークが物理的に切断されるなどのため，全体で同期を取ることが難しく，従来のルーティング方式では期待通りにメッセージを配送することができない．本研究では，ネットワーク全体で同期を取ることなく近隣ノードとの相対的な関係だけでメッセージ配送を行う Potential-Based
Routing(PBR) を DTN 環境に適用し，トポロジ変化に強いルーティング手法，Topology Change
Tolerant Routing(TCTR) を提案する．本研究では，プロトタイプシステムおよび TCTR シミュ
レータを開発した．プロトタイプシステムを使って TCTR が実装可能であることを確認すると共に，シミュレータを使い 100 台規模のノードが行動する状況において，メッセージの配送時間，転送総量，メッセージプールサイズの評価を行った．

Topology Change Tolerant Routing for Delay Tolerant Networks
Hideya Ochiai†1 and Hiroshi Esaki†1
Delay (or Disruption) Tolerant Networks (DTN) are promised as an eﬃcient message delivery scheme in physically unstable networks like wireless networks. However, because datalinks
could be physically disrupted in DTN environment, global synchronization in the network is
absolutely diﬃcult, which indicates the traditional routing schemes cannot work appropriately.
We propose Topology Change Tolerant Routing (TCTR), which do not need global synchronization in the network for message delivery. In fact, TCTR is a instance of Potential-Based
Routing(PBR) which selects the next hop of messages only using the relative information with
its neighbor nodes. We have developed a prototype system and TCTR simulator. We have
conﬁrmed that the implementation of TCTR is feasible. We have also evaluated TCTR interms of message delivery time, transmission cost and message pool size with the simulator.

的なネットワーク・トポロジが絶えず変化しており，”

1. は じ め に現在”の全体像を把握することは，困難である．これ

MANET，無線センサネットワーク，惑星間通信や潜はネットワーク全体でコントロール信号等による同期

水艦間通信など，接続関係が不安定な環境下でのメッを取ることが困難であることと等価である．ここからセージ配送に Delay (or Disruption) Tolerant Net-

ネットワーク全体で同期を取ることで実現されていた

works(DTN) の技術を応用することが有望視されてい従来型の経路制御プロトコル (e.g., RIP14) , OSPF16) ,る．IP ネットワークの場合，TCP などでエンドツー

MPLS18) , AODV17) ) が，DTN 環境には不向きであ

エンドのセッションを張るには安定したネットワーク

ることが理解できる．

特性が必要であり，先に述べた環境への適用は困難で本研究は，上記の考察を踏まえ，物理的なトポロジ

あった．一方，エンドツーエンドでセッションを張るの変化により，ネットワーク全体の様子が把握できなことを想定しない DTN は，このような環境下でもい環境下でも，近隣ノードとの関係を知るだけで，メッ

メッセージを効率的に配送することができると言われセージ配送を行う Topology Change Tolerant Rout-ている．

ing(TCTR) を提案する．本研究の提案する TCTR は，本研究の DTN 環境は，ノード (ルータ) 間の物理

Potential-Based Routing(PBR) に分類される経路制

的な通信回線が，接続状態と切断状態を繰り返す環境

御手法で，近隣ノードとのポテンシャルと呼ばれるスを意味することとする．DTN 環境においては，物理

カラー値を比較し，ポテンシャル値の低い方向へメッ
セージを転送することで，宛先ノードまでメッセージを配送する形態を取っている．TCTR では，ポテン†1 東京大学
The University of Tokyo

1

2

情報処理学会論文誌

シャルを自律分散的に生成し，ネットワーク全体のトポロジとは独立にメッセージ転送を可能にすることで，トポロジ変化に強いルーティングを実現する．

??? 1959

2. 関 連 研 究
Delay (or Disruption) Tolerant Networks (DTN)3)

一般に DTN におけるメッセージは，Application

は，大きな遅延や接続状態が不安定な性質のデータリ

Protocol Data Units(APDU)6) であり，IP パケット

ンク上であっても，メッセージを宛先まで配送するこのような 1 キロバイト規模の小さなデータ単位とはとが可能なネットワークである．本研究は，この分野限らない．数メガバイトや数ギガバイトのメッセージの中でも特にルーティングについて扱っている．ルーも対象となり，ノード間のメッセージ転送時間やスト

ティングに対しては，メッセージの配送時間，通信量，レージの大きさを考慮すべき状況も存在する．これら

バッファサイズ等のコストを小さく抑えることが要求

は将来的には，考慮する必要があるが，本研究の段階

される．

では，これらを無視できる状況を仮定している．

最 も ，原 始 的 な ル ー ティン グ 手 法 は ，Epidemic

DTN 研究の中には，宛先へのメッセージ到着確率を

Routing20) である．メッセージを出会ったノード間向上させるため，あるメッセージに対し複数のコピーで感染させていくことで，最終的に目的地にも届くを作成して配送する場合がある．我々の提案手法の中という楽観的な手法であるため，通信リソースやメッに，この考え方を導入することも考えられるが，現在セージプールへの負担は大きいが，メッセージの配送の研究段階では，メッセージのコピーを作成せずに，時間は最小にすることができる．Spray and Wait 方

メッセージを配送する方式のみを考えている．

式19) は転送開始時に，一定数のメッセージコピーをノードの位置およびその時間経過のことを本研究で作成しておき，それを送り出すことで，到着確率を高は行動パターンと呼ぶ．実際的な環境における行動パ

くする．一般に，メッセージのコピーを複数作成する

ターンは極めて複雑であり，本研究の中でそれらを網ことで，目的地まで到達する確率を高くし，到着まで羅的に扱うことは困難である．そこで本研究の段階での時間を短くすることができるが，各種リソースを消は，各ノードがそれぞれ特定の複数地点を巡回する状

費する傾向がある．

況を仮定し，その状況下で提案手法を用いると，自律ノードの接続関係を，将来にわたって予測し，メッ

分散的にメッセージの配送が可能になることを示すにセージの配送経路を最適化しようとする試みがある．

とどめる．

ここには，将来の動作が決定的 (i.e., 衛星のように軌

本論文では，まず PBR のシステムモデルを定義し，道計算が可能) な場合と，非決定的 (i.e., 人間の行動パ

その中でポテンシャルを自律分散的に生成する漸化式

ターンのように予測不可能) な場合によってアプロー

を提案，これを TCTR と呼ぶことにする．その後，チが異なる．Merugu らの提案15) では，与えられた決TCTR の動作および特性を述べる．実験では，プロト

定的なノードの行動モデルから時空間グラフを生成し，タイプシステムとシミュレータを作成し，プロトタイ

最小時間配送経路を導き出してメッセージを配送する．

プシステムを使って，(1) ポテンシャルの軌跡やメッ

一方，将来の動作が非決定的であっても，動作の傾向

セージの配送が期待通り行われるかどうか (すなわちを学習することでメッセージのルーティング効率を高TCTR の実現可能性) を確認し，(2) 実装時に考慮すべ

めるアプローチもある．Leguay らは，MobySpace10)

きメッセージ氾濫限界 (詳細は第 3.3 節で述べる) の計と呼ぶ高次元空間に，ノードの行動モデルを対応づけ，測を行う．また，シミュレータの妥当性をプロトタイ

ノードの存在確率を計算することで，メッセージを配プシステムを使って検証した後，2000[m] × 2000[m]送する手法を提案した．PROPHET12) や Francois4)の領域に 100 台のノードを展開し，(3) メッセージ配らも，手法は異なるが学習に基づき接続関係を予測す

送時間，(4) ノード間で交換されたメッセージ転送総る方式を取っている．我々の提案方式は，ポテンシャ

量，(5) メッセージプールサイズの評価を行う．

ル値の中に接続関係の情報を取り込むという点で，一以下，本論文の構成を記す．第 2 章で，関連研究を

種の学習型アルゴリズムと言える．

述べる．第 3 章で TCTR システムモデルを提案する．

本研究では，ポテンシャル値を考え，メッセージの第 4 章で実装方法，第 5 章で評価実験を示す．第 6 章

配送にこのポテンシャルの勾配を利用する．PBR はで実験結果などに対する考察を与え，第 7 章でまと

勾配検索法 (Gradient Descent Search) の派生系としめる．

て，Basu らによって，一般のネットワークにおけるトラフィックエンジニアリングの目的で使うことを念頭に提唱された1) ．その後，移動ネットワークや無線セ

Vol. 0No. 0

DTN 環境を想定したトポロジ変化に強いメッセージルーティング

3

ンサネットワークにおける Anycast での最適ノード選択への利用が試みられている9)11) ．Volcano Routing

Scheme(VRS)5) からは，PBR 的な考えがトポロジ変化の激しいネットワークに向いていることを読み取ることができる．PWave13) は電子回路における電位と電流の関係をポテンシャルとメッセージの配送に対応
づけ，無線センサネットワークに応用した．実フィール
ドでは，ZebraNet8) で提案されている History-based

Protocol から，PBR の考え方が具体的な DTN アプ
リケーションにおいて実際に利用されていることが読み取れる．

3. TCTR システムモデル
ここでは提案ルーティング手法である TCTR のシ
ステムモデルを数学的に定義する．本研究での PBRを定義した後，ポテンシャルの生成規則を提案し，こ

図 1 Potential-Based Routing(PBR)
Fig. 1 Potential-Based Routing(PBR)の手法の性質を述べる．TCTR を機器に実装する際に考えなければならない氾濫限界と転送スレッシュホ

時，メッセージの転送先は存在しないことを意味し (Φルドの関係についても述べる．

は空集合)，式 3 は，ノードに働く力が α を越えれば，本研究では，物理レベルで接続されたネットワーク

最大の力を与える近隣ノードを転送先とすることを意

グラフ G = (N, E) を考える．グラフ G 上のノード

味する?1 ．この規則で転送を繰り返し行うことで，ポn(∈ N ) に対し，nbr(n) で n の近隣ノードの集合を

テンシャル値が最も低い宛先 d に，最終的にメッセー表すことにする．いまノード n において，メッセージジが配送される．

の宛先ノード d(∈ N ) について考える．時刻 t におけ

図 1 に PBR におけるメッセージ転送および配送のる d 宛の n におけるポテンシャル値を定義し，これ様子を示す．この図では，あるネットワーク G の物理

を V d (n, t) と表記する．V d (n, t) はスカラー値であ的なノード間の接続関係を維持しながら，ノードの持り，それぞれの宛先 d に対して独立な値を持つ．

つポテンシャル値を縦にとっている．この状態におい

3.1 Potential-Based Routing(PBR)ては，n の近隣ノード k1 , k2 で最大の力を与えるもの

時刻 t において n に存在する宛先 d とラベルづけ

は k1 であるから，n にあるメッセージは，k1 に転送されたメッセージの集合 M d (n, t) に対し，近隣ノーされる．同様のことが繰り返し転送先で行われること

ド k ∈ nbr(n) 方向に働く力 Fkd (n, t) を次のように定で徐々に宛先 d へ近づき最終的には届く．メッセージ

義する．

が流れたパスのことを本研究では配送路と呼び，宛先

Fkd (n, t) ≡ −{V d (k, t) − V d (n, t)}(1)まで届けることを配送と呼ぶ．これに対し，転送は，次のノードへメッセージを送り出す処理である．

ここで，M d (n, t) の転送先 nexthopd (n, t) を，次PBR のメリットは，近隣ノードとの関係だけでメッの規則で与えるのが，本研究の PBR による転送規則

セージの転送先を計算できる点である．グローバルなである．

ネットワークトポロジに関する情報と必ずしも同期を∀k∈nbr(n) ,Fkd (n, t) ≤ α → nexthopd (n, t) = Φ

取らなくてもメッセージの配送が可能である．

(2)

3.2 ポテンシャル生成規則
PBR では，ポテンシャルが与えられていれば，式2,3 に従い，次の転送先を計算することができる．問∃k∈nbr(n) ,題はどのようにこのポテンシャルを生成するかであり，

Fkd (n, t) > α → nexthopd (n, t) ={k|Fkd (n, t) =maxk∈nbr(n)Fkd (n, t)}(3)

本研究では，下記の漸化式により自律的に生成する手法を提案する．

ここで α は正の定数で，転送スレッシュホルドと呼ぶことにする．式 2 は，ノードに働く力が α 以下の?1 複数の候補が見つかったときは一つを選び送信するものとする．

情報処理学会論文誌

4

図 2 物理的に接続されたネットワークにおける宛先ノード
d = n6 へのポテンシャルの形状とメッセージの流れ
Fig. 2 Potential formation and message delivery path fordestination d = n6 in a physically connected network.

??? 1959

n2 − n4 間のリンクが切断され，二つのネットワークに分離してしまった場合のポテンシャル形状; n0, n1, n2, n3 のポ
テンシャルは上昇を開始し，その速度は ρ に収束する．
Fig. 3 Potential formation when n2 − n4 link has been disrupted. Potentials of n0, n1, n2, n3 goes up withthe velocity of ρ.
図3

V d (n, t + 1) = V d (n, t) +Dmink∈nbr(n)する (c は定数)．

{0, V d (k, t) − V d (n, t)}(4)∀n∈N2 V d (n, t) → ρt + cd∀d∈N ∀tV (d, t) = 0(5)(t → ∞)∀n∈N V (n, 0) = 0(6)

図 3 の例では，{n0, ..., n3} のポテンシャルは ρ

+ρ
d

(7)

これは V (n, t) に対して，自分の持つポテンシャの速度で上昇する．このとき，{n0, ..., n3} にあルよりも低い最小のポテンシャルを持つノードが近隣

るメッセージは，各ノードのメッセージプールに

d

にあれば，
「そのノードとのポテンシャル差分に定数

D(0 < D < 1) をかけたもの」の分だけ自分のポテン
シャルを下げ，「定数 ρ(0 < ρ < D)」分だけ自分のポ蓄えられる．

• 物理的に分裂した二つのネットワークが再結合する場合 (図 4)

テンシャルを上げるようにするということである．式

図 4 では，n1 − n5 間のリンクが接続されたこと

5，式 6 は拘束条件で，それぞれ，宛先が自分自身でにより，二つのネットワークが再結合している．

あるならばポテンシャル値は 0，開始時のポテンシャ

ポテンシャルの低い方のネットワークに接続した

ル値は 0，を表している．

ノードから順にポテンシャルが降下し，図 4 の

こ の よ う な 形 式 で ポ テ ン シャル を 定 義 す れ ば ，ようなポテンシャルのカーブが生ずる．ここを伝dV (n, t) の性質を力学的な分析から明らかにするこ

わって {n0, ..., n3} のメッセージプールに蓄えらとができる．以下では，3 種類のネットワーク状態にれていたメッセージが一気に流れ出る．

おいてポテンシャルがどのような形を取るかを述べる．

• 物理的に接続された単一ネットワークの場合 (図ポテンシャルは宛先への到達性を表す，ある種の指

2)

標である．
「ポテンシャルがより小さい」と「宛先ノーポテンシャル値は収束し，距離ベクトル型のルードにより効率よくメッセージを配送できる」が等価とティングと等価な状態になる．図 2 左側のネット

なるネットワーク環境であれば，本提案手法は最大のワークに対して生成される，宛先 d = n6 へのポ

パフォーマンスを発揮する．

テンシャル V n6 (n, t) の収束値を図 2 の右側に示

実際，下記の状況が仮定できる環境 (i.e., ノードのす．n6 からホップ数が増えるごとにポテンシャル

接続関係，行動パターン) であれば，式 4 から生成さ値は増加し，メッセージはポテンシャルの低い方れるポテンシャル形状は，メッセージ配送に関して最向へ配送される．

適な形となる．

• ネットワークが物理的に分裂した場合 (図 3)
ネットワークが二つに分裂すると，宛先ノードが属さないネットワーク・ノードのポテンシャル値• 宛先 d の存在するネットワークから離れているよりは，接続されている方がメッセージは早く配送される環境が増加を開始する．一般に，分裂したネットワー• より近い過去に d の存在するネットワークから離クを G1 = (N1 , E1 ), G2 = (N2 , E2 ) とし，G1 にれたものが，より近い未来に再接続される確率が宛先ノードが存在する場合 (i.e., d ∈ N1 である

高い環境とき)，N2 のノードのポテンシャルは下記に収束Vol. 0DTN 環境を想定したトポロジ変化に強いメッセージルーティング

No. 0

5

n1 − n5 間のリンクが接続されたことにより，二つのネットワークが再結合する場合．n0,
n1, n2, n3 のポテンシャルが急降下すると共に，カーブが生まれ，メッセージが流れていく．
Fig. 4 When n1 − n5 link has been setup, potentials of n0, n1, n2, n3 goes downwith making message delivery curves.

図4

3.3 ポテンシャル伝播遅延とメッセージ氾濫現象
式 4 では，近隣ノード k ∈ nbr(n) が持つポテンシャ
ル V d (k, t) も時刻 t で取得できていることになっているが，実際に TCTR を実装する場合には，ノード間で定期的にポテンシャルを交換するため，ノード n に

Vkd (n, t) ≈ V (t) − ∆T∂V (t)∂t(10)

すなわち，式 1 より，Fkd (n, t) = ∆T∂V (t)∂t(11)

見える k が持つポテンシャル (以下，Vnd (k, t) と記述となって，ポテンシャル値が増加傾向にあるとき (⇔する) は，現時点での k が持つポテンシャル Vkd (k, t)∂V (T )
> 0) は，式 3 から，∂tdよりも少し古いものになる．この時間差を ∆T とする

nexthop (n, t) =と，変化したポテンシャル量に関して，

k

(12)

k∈nbr(n)となり，すべてのノードが近隣ノードの 1 つを選んでVkd (k, t) − Vkd (k, t − ∆T )= Vkd (k, t) − Vnd (k, t)(8)が成立する．従って，Vnd (k, t) ≈ Vkd (k, t) − ∆T∪

メッセージを転送する状態になる．結果，メッセージがネットワークの中を巡り続ける状況となってしまう．
本研究では，この現象をメッセージの氾濫現象と呼ん∂Vnd (n, t)(9)∂tとなり，ポテンシャル値の時間変化によって，観測される近隣ノードのポテンシャル値に変位が生じる．こでいる．
具体的な場面として，図 5 の状況を取り上げる．開始時には，ノード A, B, C はすべて相互に接続されて
いて，A，B における宛先 C のメッセージ転送先は，の変位が式 4 だけからは考えられなかった，メッセー

それぞれ A → C と B → C である．ある時点で，Cジの氾濫と呼ぶ現象を引き起こすことがある．

が切り離され遠くに行ってしまったとする．このとき，簡単な状況として，∀i∈N , Vid (i, t) = V (t) という，A, B の C へのポテンシャル値は，共に同じ値で増加

すべてのノードが平衡に同一ポテンシャル値 V(t) をを開始する．A が見る B のポテンシャル値は，B で持つ場合を想定しよう．これは，図 3 に示したようにの本来のポテンシャル値より小さい．そこで A は，C分離されたネットワークで実際に存在しうる状況であへのメッセージを B へ送り出そうとする．同様のこる．式 2,3 において α = 0 の場合，理想的な環境下でとは，B にも当てはまり，B は C へのメッセージをdは nexthop (n, t) = Φ となり，転送先は存在しない．

A へ送り出そうとする．そのため，メッセージはネッ

しかし，実際的な環境では，式 7 が成り立つため，

トワーク内を巡り続けるのである．
この問題現象を回避するために，実際のネットワー

情報処理学会論文誌

6??? 1959

図 5 メッセージ氾濫現象の一例
Fig. 5 An example of message overﬂow phenomenon

成を示す．4 種の機能ブロックで構成してある．以下，
このシステムがノード n として動いている状況を考え，各機能を解説する．

(1)

Advertisement Manager: UDP Multicast により，定期的に近隣ノード k ∈ nbr(n) とポテ
ンシャル V (k, t), V (n, t) を交換しあう．Multi-

cast Socket を通じ，近隣ノードから受け取った
ポテンシャル V (k, t) は，PotentialTable に送られる．一方，PotentialTable からは定期的に，このノード n の最新ポテンシャル V (n, t) が与

図 6 プロトタイプシステムの構成
Fig. 6 Prototype System Overview

えられ，これを UDP Multicast で広告する．

(2)

ンシャル ∀k∈nbr(n) V (k, t) をキャッシュし，こクでは，式 2,3 で定義した転送スレッシュホルド α を設定する．設定においては，氾濫限界 β を考え，β<αのノードのポテンシャル V (n, t) とあわせて

V (n, t + 1) を式 4 に従い計算する．

(13)となるように α を設定する．氾濫限界 β は式 9 より，(3)∂V (n, t)∂tで与えられ，式 4 によれば，(14)∂V (n, t)
=ρ
∂t

(15)

だから，

2，3 に従って，宛先 d ごとに転送先ノードを(4)

Message Manager: アプリケーションへのメッ
セージインタフェースを提供し，メッセージの転送処理も行う．アプリケーションは，Message

β = ρ∆T

(16)

である．

4. 実

Potential Table か ら

計算し，メッセージ転送表を作成する．

dmax

Forwarding Table:

V d (n, t) と ∀k∈nbr(n) V d (k, t) を与えられ，式dβ = ∆T max

Potential Table: すべての近隣ノードのポテManager に対して，メッセージの配送を委託する (Send)．Message Manager が n 宛のメッ

装

セージを受信すれば，アプリケーションへ通知
する (Receive)．通常は，n が受信したメッセー

本研究では，実際に無線端末で動作するプロトタイ

ジに対して，宛先 d をキーに Forwarding Ta-

プシステムと，仮想的に大規模なシナリオを再現でき

ble に転送先を問合せ，転送先が存在すればメッ

るシミュレータを開発した．

セージを転送する．転送が成功すると転送先か

4.1 プロトタイプシステム

ら応答として ACK が通知される．転送先が存

図 6 に本研究で開発したプロトタイプシステムの構

在しない場合や，転送に失敗したときは，そのVol. 0No. 0

DTN 環境を想定したトポロジ変化に強いメッセージルーティング

7

図 7 シミュレータの構成
Fig. 7 TCTR Simulator Overview

メッセージは Message Manager のメッセージ
プールに保存される．保存されているメッセー
ジは，定期的に再転送が試みられる．

図 8 実証実験におけるノードの行動パターン
Fig. 8 Mobility model used in the experiment

このプロトタイプシステムは，下記内容をログとして出力する．このログは，次の評価実験での解析に利• メッセージプールサイズ (定期的にログ出力)

用した．

• メッセージ転送イベント• ポテンシャル値 (定期的にログ出力)• メッセージ送信 (Send) イベント

• Forwarding Table の内容 (定期的にログ出力)• メッセージ受信 (Receive) イベント

• メッセージプールサイズ (定期的にログ出力)

本研究で開発したシミュレーション環境は，Java• メッセージ転送イベント

言語で実装した．実行には，JavaVM 1.5.0，OS は• メッセージ送信 (Send) イベント

Linux 2.6.15 を使用した．

• メッセージ受信 (Receive) イベント
ここで開発したプロトタイプシステムは C 言語で実装した．実験環境は，OS が Linux 2.6.22 で，無線
データリンクには 802.11g を使用している．

5. 評

価

次に述べる評価実験では，まず，プロトタイプシス
テムを使った実証実験により本提案システムが実現可

4.2 TCTR シミュレータ

能であることを確認し，シミュレータが実証実験での図 7 に，開発したシミュレータの構成を示す．3 種

結果を再現できることを確認した．次にプロトタイプの機能ブロックで構成してある．以下，それぞれの機システムによりメッセージ氾濫現象を観測，分析した．

能ブロックについて解説する．

シミュレータによる大規模なシナリオの検証では，配(1)

Node: 各 Node インスタンスが，仮想的に展開

送時間が最小となる Flooding-Based Routing(FBR)

されたノードに相当し，独立したスレッドによ方式と次の評価基準について比較を行った: (1) 配送

り動作する．Node の内部は，プロトタイプシ

時間，(2) メッセージ転送の総量，(3) メッセージプー

ステムとほぼ同様の構成となっている．ただし，ルサイズ (プールに保存されているメッセージ数)．

Node Locator を通じて，近隣ノードへのポテ
ンシャル通知 (広告) やメッセージ交換を行う．

(2)

Node Locator: Node インスタンスの (2 次元平面での) 位置管理を行う．通信可能範囲にあるノードの発見機能，位置の操作インタフェー(3)

下記実験は，D および ρ のパラメータに，それぞれD = 0.2，ρ = 0.02 を設定して行われた．
5.1 プロトタイプシステムによる実証実験およびシミュレータの妥当性
この実験では，物理的に隔離されたネットワーク間スなどを持つ．

をノードが行き来するシナリオにおいて，プロトタイ

Mobility Manager: 実験対象とする行動パター

プシステムによる動作の確認を行った．具体的には，ンを生成し，Node Locator を通じてノードのポテンシャル変化の様子やメッセージ配送の様子を観位置設定をする．

測し，それが期待通りのものであるか調べた．その後，出力ログは，プロトタイプシステムと同様に下記を出力する．このログを評価実験での解析に使用した．

• ポテンシャル値 (定期的にログ出力)• Forwarding Table の内容 (定期的にログ出力)

シミュレータで同様のシナリオを設定し，ほぼ同じ結果を得られることを確認した．
図 8 にこの実験で利用したノードの行動パターンを示す．Home A，Home B，Meeting Point を考え，

8

情報処理学会論文誌

図9

図 10

プロトタイプシステムによるポテンシャル変化とメッセージ
配送の様子
Fig. 9 Potential patterns with the prototype-based
experiment??? 1959

シミュレータによるポテンシャル変化とメッセージ配送の様子
Fig. 10 Potential patterns with the simulation-based
experiment

ノード 1，4 はそれぞれ Home A，B の固定ノード，

このメッセージ配送は自律的に行われた．そして，

ノード 2，3 は，Home A，B の住人が持つ移動ノード

この動作は期待通りのものであった．こうして TCTRとする．ノード 2，3 は，Meeting Point で定期的にルーティングが実現可能であることが実証された．

出会うことになっている．Home A, Meeting Point,

図 10 に，シミュレータで実験した結果得られた，Home B は十分に離れており，直接通信することはで各ノードにおける（ノード 1 への）ポテンシャル値

きない．無線の通信範囲は (建造物等による影響を考V 1 (n, t) の挙動と，メッセージ配送の様子を示す．プえ)20m ほどを想定している．図 8 に示すように，ノーロトタイプシステムの場合と同様に，時刻 t = 3600 か

ド 2，3 を行動させた．各所への滞在時間は 2 分であら t = 4800 までの様子を示した (時間軸は (t − 3600)

る．移動中は無線通信範囲を一度出ると，どのノードを表示している)．結果は，プロトタイプシステムのとも通信はできない．図 8 に示した移動のプロセスは

場合と，ほぼ同じだった．

20 分を周期に，繰り返される．この実験においては，
ノード 4 がノード 1 宛に，10 秒に 1 回，100 バイト
程度のメッセージを送信している．

こうして，シミュレータがプロトタイプシステムでの実験を再現できることを確認した．

5.2 メッセージ氾濫限界の計測

図 9 に，プロトタイプシステムで実験した結果得ら

ここでは図 5 のシナリオで，様々な転送スレッシュ

れた，各ノードにおける（ノード 1 への）ポテンシャ

ホルドを設定し，C 宛のメッセージの転送先がどのよ

ル値 V 1 (n, t) の挙動と，メッセージ配送の様子を示す．

うに収束するかを観測した．

実験開始後，時刻 t = 3600 から t = 4800 までの様子

式 16 によると，実験の環境 0 < ∆T < 1, ρ = 0.02を示しているが，図の時間軸は，わかりやすくするたにおいては，氾濫限界は，0.02 未満であることが予め (t − 3600) を表示している．ここで，n1 , n2 , n3 , n4測される．実際に α を {0.000, 0.010, 0.015, 0.020,

はそれぞれ，ノード 1, ノード 2，ノード 3，ノード 4

0.025, 0.030} に設定し，図 5 の状態を作ることで，生に対応している．

成される転送先を調べた．

時刻 t = 60 を過ぎて，しばらくすると n2 は n1 が

表 1 に実験結果を示す．各 α に対して 3 回ずつ図

近隣ノードでなくなったことを知り，V (n2 , t) は上昇

5 のシナリオを再現することで，Node A での転送先を開始した．t = 580 において，n3 は n2 と接続関係と Node B での転送先を調べた．この表には，そのになったことを知り，V (n3 , t) を降下させると共に，

結果および，その結果からわかるネットワークの状

保有しているメッセージ 122 通を n2 に転送した．そ態 (Status) が記載されている．”A”は転送先が Nodeの後，n2 と n3 は Meeting Point を離れ，t = 1140

A，”B”は転送先が Node B，”Φ”は転送先が存在しにおいて，n4 は n3 と，n2 は n1 と接続関係になったない，ことを意味する．状態について，”ループ”は，ことを知った．結果，n4 ，n2 はポテンシャルを降下

メッセージがネットワーク内を巡回する状態になったさせながら，それぞれ保有している n1 宛のメッセーことを意味し，”偏り”はいずれか片方のノードにメッ

ジ 105 通と 121 通を n3 ，n1 に転送した．

セージが集まる状態になったこと，”ホールド”はメッ

Vol. 0DTN 環境を想定したトポロジ変化に強いメッセージルーティング

No. 0

9

表 1 メッセージ氾濫限界の計測結果
Table 1 An Analysis of the Message Overﬂow Threshold

α
0.000
0.010
0.015
0.020
0.025
0.030

Node A での方向
1 回目
2 回目
3 回目
B
B
B
Φ
B
B
Φ
Φ
B
Φ
B
B
Φ
Φ
Φ
Φ
Φ
Φ

Node B での方向
1 回目
2 回目
3 回目
A
A
A
A
A
Φ
A
A
Φ
Φ
Φ
Φ
Φ
Φ
Φ
Φ
Φ
Φ

Statusループ
偏り ループ偏り
偏り ホールド
ホールド
ホールド

セージは転送されない状態になったことを意味している．複数の状態が観測された α に対しては，すべての状態を記載した．

”偏り”の状態は，片方のノードが氾濫現象を起こしていることを表している．α が 0.02 では氾濫現象はほぼ見られなくなり，この値を越えると現れなくなっている．

5.3 配送時間，転送総量，プールサイズ
この実験では，シミュレータを用いて，100 台規模のノードが存在する環境を仮想的に作り出し，メッセー
ジ配送時間，メッセージ転送総量，メッセージプール
サイズに関して評価を行っている．
評価においては，Flooding-Based Routing(FBR)

図 11 転送時間の関係
Fig. 11 Delivery Time Relationship between FBR and
TCTRとの比較を行った．実験に用いた FBR は，次の方法
でメッセージの配送を行う．いま，ノード A(∈ N ) と2000[m] × 2000[m] の２次元平面に，半径 0〜300[m]ノード B(∈ N ) を考え，A，B が保持しているメッの円運動をするノードを 100 個配置した．無線通信可能

セージの集合をそれぞれ MA ，MB とする．ノード A

半径は 150[m] で，回転周波数は，0〜0.01[Hz] である．

と B が出会ったときに，次の規則でメッセージ交換

行動パターンとしては，Random Way Point(RWP)2)を行う．

も考えられるのだが，本研究では，ノードが巡回的に

m ∈ MA ∧ ¬m ∈ MB→

行動する状況を考えているため RWP での評価は行っ

T ransf erA (m, B) (17)ていない．
時刻 t=0 から動作を開始し，t=10000 にすべてのm ∈ MB ∧ ¬m ∈ MA→

ノードがすべてのノードに対して一斉にメッセージを

T ransf erB (m, A) (18)

ここで，T ransf erX (m, Y ) は，ノード X がメッ
セージ m をノード Y に転送することを意味する．結果，∀m(m ∈ MA ↔ m ∈ MB )(19)送信する (t=10000 は，TCTR においてポテンシャル
情報が全体に行き渡るために十分な時間である)．

5.3.1 メッセージ配送時間
図 11 に，FBR 方式での配送時間 T ime(F BR) ととなる．各メッセージ m には，宛先ラベルがついてTCTR 方式での配送時間 T ime(T CT R) の関係を示す．

いて，宛先に到達したらそのメッセージはアプリケー

それぞれの点は (送信元:宛先) のペアに対応する．こションに届けられる．FBR 方式は，メッセージの配の図には，T ime(T CT R) = T ime(F BR) である線を書送にかかる時間を最小化することができる．本研究で込んである．各点は，T ime(T CT R) ≥ T ime(F BR) のは，FBR の配送時間と TCTR の配送時間を比較する

領域に存在することが読み取れる．

ことで，どの程度の効率があるかを調査した．いずれ

図 12 に，配送時間の倍率

T ime(T CT R)と，その倍T imeF BRの場合もメッセージの Time To Live(TTL) は無限大率に属したメッセージ配送処理の分布を示す．この図に設定している．

から，約 33%のメッセージが最適 (FBR) の場合の 2実験では，次のようにノードの行動パターンを設定

倍時間以内に配達されており，約 50%のメッセージがした (FBR と TCTR で同じ行動パターンを利用した)．

最適の場合の 3 倍時間以内に配達されていることが読情報処理学会論文誌10

図 12 配送時間の倍率とその分布
Fig. 12 Eﬃciency in Delivery Time and its Distribution??? 1959

図 14 メッセージプールの平均サイズ
Fig. 14 The Average Message Pool Size

5.3.3 メッセージプールの大きさ
図 14 に，FBR と TCTR における平均メッセージ
プール量の時間変化を示す (時刻は，メッセージ配送を開始した t = 10000 を 0 として表示している)．FBR
では，メッセージプールの大きさが時間の経過と共に増加し 10000 で安定しようとしている．一方，TCTR
では，メッセージプールが最初 97 まで増加したが，時間の経過と共に減少している．

FBR では，すべてのノードがネットワークに存在するすべてのメッセージをメッセージプールに保存す
る．100 個のノードから，100 箇所へメッセージが配図 13 メッセージ転送総量の変化
Fig. 13 The Total Message Transmission in the Network

送されたので，100 × 100 = 10000 に収束したのだと考えられる．TCTR の場合はメッセージは複製されず配送が完了すればネットワークから消えていくためみ取れる．10 倍時間以上かかる配送処理は，全体の5%程度であった．
5.3.2 メッセージ転送総量減少したのだと考えられる．

6. 考

察

図 13 に，FBR 方式と TCTR 方式でのメッセージ

本研究では，プロトタイプシステムによる実機で転送総量を示す (時刻は，メッセージ配送を開始したの動作検証と，シミュレータによる大規模な状況を想t = 10000 を 0 として表示している)．転送総量とは，定した評価実験を行った．同じ行動パターンを用意す

任意のノード a(∈ N ) からノード b(∈ N, a 6= b) へメッ

れば，プロトタイプシステムでのポテンシャルやメッ

セージ転送があった場合にカウントされるグローバル

セージ配送の挙動を，シミュレータによる実験で再現な変数である．この図から読み取れるように，FBR 方

できた．これはシミュレーション実験の結果にある程式では，TCTR に比べておよそ 10 倍のメッセージ転度の妥当性を与えるものである．

送を行った．FBR は，すべてのノード (=100 台) そ

プロトタイプシステムを使って実際にメッセージ氾

れぞれが 100 個のノードから発される 100 箇所への濫現象を観測し，氾濫限界 β が 3.3 節で与えたモデル

メッセージ転送処理すべてに加担するため，最終的にに従っていることが確認された．これにより TCTR

6

全体で約 10 回の転送を行ったと読み取れる．一方，を実環境に展開するときに，転送スレッシュホルド α

TCTR では，各ノードは，100 個のノードから発されの適性値を設計することが可能になったと言える．

る 100 箇所へのメッセージ転送の一部のみを行ったた
め，約 105 回の転送で済んだものと思われる．

シミュレータによる 100 台規模の環境の評価では，配送時間が最短となる FBR との比較を行った．結果，実験の環境では，およそ半数のメッセージは FBR のVol.0DTN 環境を想定したトポロジ変化に強いメッセージルーティング

No.0

3 倍時間以内に配送されることが観測された．ここでTCTR に対して，FBR は通信量にしておよそ 10 倍，
メッセージバッファ量に関しては 100 倍以上のコストがかかっている．配送時間の遅れが十分許容できるのであれば，TCTR を使ったほうが，リソースの消費が少なく済むと言える．
本研究では，巡回的な行動パターンについてのみ扱
い，一般的な行動パターンについては扱わなかった．
また，メッセージ単位の大きさ，通信帯域，トラフィッ
クの輻輳を考慮したメッセージ転送などは無視していた．メッセージ単位が大きく，通信帯域の狭い通信であれば，一つのメッセージの転送にかかる時間が無視できなってしまう7) ．将来的には，このような状況も想定する必要があると考えている．

7. お わ り に本研究では，DTN 環境向けに，トポロジ変化に強いルーティング手法である TCTR を提案した．メッ
セージの転送に PBR の勾配法を用い，ポテンシャルの生成を自律分散的に行う，時間に関する漸化式を定義した．
プロトタイプシステムを開発し，TCTR が実際に実装可能であることを示した．同時に，実装時に想定しなければならないメッセージ氾濫現象について言及
およびモデル化し，評価試験では，このモデルの検証も行った．

TCTR を用いると，特に巡回的にノードが行動するシナリオにおいて，自律的にポテンシャルを生成し，メッセージを効率よく配送できた．評価実験で述べた

100 台のノードが行動する環境において，配送時間が最小となる FBR 方式と比べ，約半数のメッセージが3 倍以内の時間で配送され，メッセージ転送総量は 10分の 1，メッセージプールサイズは 100 分の 1 以下にまで抑えられた．

参 考 文 献1) Basu, A., Lin, A. and Ramanathan, S.: Routing Using Potentials: A Dynamic Traﬃc-Aware
Routing Algorithm, ACM SIGCOMM 2003,
pp.37–48 (2003).
2) Bettstetter, C., Resta, G. and Santi, P.: The
Node Distribution of the Random Waypoint
Mobility Model for Wireless Ad Hoc Networks, IEEE Transactions on Mobile Computing, Vol.2, No.3, pp.257–269 (2003).
3) Fall, K.: A Delay-Tolerant Network Architecture for Challenged Internets, ACM SIG-

11

COMM 2003, pp.27–34 (2003).
4) Francois, J.-M. and Leduc, G.: Delivery Guarantees in Predictable Disruption Tolerant Networks, Lecture Nodes in Computer Science,
Vol.4479, pp.167–178 (2007).
5) Ganjali, Y. and McKeown, N.: Routing in a
Highly Dynamic Topology, IEEE SECON, pp.
164–175 (2005).
6) Iren, S., Amer, P.D. and Conrad, P.T.: The
Transport Layer: Tutorial and Survey, ACM
Computing Surverys, Vol.31, No.4, pp.360–404(1999).
7) Jain, S., Fall, K. and Patra, R.: Routing in
a Delay Tolerant Network, ACM SIGCOMM
2004, pp.145–158 (2004).
8) Juang, P., Oki, H., Wang, Y., Martonosi,
M., Peh, L.-S. and Rubenstein, D.: EnergyEﬃcient Computing for Wildlife Tracking: Design Tradeoﬀs and Early Experiences with ZebraNet, ACM SIGOPS, pp.96–107 (2002).
9) Kumar, P., Kuri, J., Nuggehalli, P., Strasser,M., May, M. and Plattner, B.: Connectivityaware Routing in Sensor Networks, IEEE SensorComm, pp.14–20 (2007).
10) Leguay, J., Friedman, T. and Conan, V.: DTN
Routing in a Mobility Pattern Space, ACM
SIGCOMM workshop on Delay-tolerant networking, pp.276–283 (2005).
11) Lenders, V., May, M. and Plattner, B.:
Density-based vs. Proximity-based Anycast
Routing for Mobile Networks, IEEE INFOCOM, pp.1–13 (2006).
12) Lindgren, A., Doria, A. and Schelen, O.: Probabilistic Routing in Intermittently Connected
Networks, Lecture Nodes in Computer Science,
Vol.3126, pp.239–254 (2004).
13) Liu, H., Zhang, Z.-L., Srivastava, J. andFiroiu, V.: PWave: A Multi-source Multi-sink
Anycast Routing Framework for Wireless Sensor Networks, Lecture Nodes in Computer Science, Vol.4479, pp.179–190 (2007).
14) Malkin, G.: RFC2453: RIP Version 2 (1998).
15) Merugu, S., Ammar, M. and Zegura, E.: Routing in Space and Time in Networks with Predictable Mobility, Technical report, Georgia Institute of Technology (2004).
16) Moy, J.: RFC2328: OSPF Version 2 (1998).
17) Perkins, C., Belding-Royer, E. and Das, S.:
RFC1058: Ad hoc On-Demand Distance Vector (AODV) Routing (2003).
18) Rosen, E., Viswanathan, A. and Callon, R.:
RFC3031: Multiprotocol Label Switching Architecture (2001).
19) Spyropoulos, T., Psounis, K. and Raghaven-

12

情報処理学会論文誌

dra, C.S.: Spray and Wait: An Eﬃcient Routing Scheme for Intermittently Connected Mobile Networks, ACM SIGCOMM workshop on
Delay-tolerant networking, pp.252–259 (2005).
20) Vahdat, A. and Becker, D.: Epidemic Routing for Partially-Connected Ad Hoc Networks,
Technical report, Duke University (2000).

??? 1959