情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

推薦論文

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

system and TCTR simulator. TCTR has achieved message delivery over highlydynamic topology scenarios, which MANET protocols cannot be applied to.
We evaluated the performance of TCTR regarding to message delivery time,transmission cost and message pool size in comparison with Epidemic Routing,which provides tolerance for topology changes by ﬂooding mechanism.

1. は じ め に

落 合 秀

也†1

江

崎

浩†1

MANET，無線センサネットワーク，惑星間通信や潜水艦間通信など，接続関係が不安定な環境下でのメッセージ配送に Delay（or Disruption）Tolerant Networks（DTN）の技

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

Topology Change Tolerant Routing
for Delay Tolerant Networks
Hideya Ochiai†1 and Hiroshi Esaki†1

術を応用することが有望視されている．IP ネットワークの場合，TCP などでエンドツーエ
ンドのセッションを張るには安定したネットワーク特性が必要であり，先に述べた環境への適用は困難であった．一方，エンドツーエンドでセッションを張ることを想定しない DTN
は，このような環境下でもメッセージを効率的に配送することができるといわれている．
本研究の DTN 環境は，ノード（ルータ）間の物理的な通信回線が，接続状態と切断状態を繰り返す環境を意味することとする．DTN 環境においては，物理的なネットワーク・ト
ポロジが絶えず変化しており，“現在” の全体像を把握することは，困難である．これはネットワーク全体でコントロール信号などによる同期をとることが困難であることと等価である．ここからネットワーク全体で同期をとることで実現されていた従来型の経路制御プロト
コル（e.g.，RIP14) ，OSPF16) ，MPLS18) ，AODV17) ）が，DTN 環境には不向きであることが理解できる．
本研究は，上記の考察をふまえ，物理的なトポロジの変化により，ネットワーク全体の様子が把握できない環境下でも，近隣ノードとの関係を知るだけで，メッセージ配送を行う

Topology Change Tolerant Routing（TCTR）を提案する．本研究の提案する TCTR は，Potential-Based Routing（PBR）に分類される経路制御手法で，各ノードはポテンシャルと呼ばれるスカラー値を持ち，ポテンシャル値の低いノードへメッセージを繰り返し転送す

Delay (or Disruption) Tolerant Networks (DTN) are promised as an eﬃcientmessage 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 does not need global synchronizationin the network for message delivery. In fact, TCTR is an instance of PotentialBased Routing (PBR) which selects the next hop of messages only using therelative information with its neighbor nodes. We have developed a prototype

2312

ることで，宛先ノードまでメッセージを配送する形態をとっている．TCTR では，ポテン
シャルを自律分散的に生成し，ネットワーク全体の物理トポロジとは独立にメッセージ転送†1 東京大学
The University of Tokyo
本論文の内容は 2008 年 7 月のマルチメディア，分散，協調とモバイル（DICOMO2008）シンポジウムにて報告され，同プログラム委員長により情報処理学会論文誌ジャーナルへの掲載が推薦された論文である．

c 2009 Information Processing Society of Japan


2313

DTN 環境を想定したトポロジ変化に強いメッセージルーティングを可能にすることで，トポロジ変化に強いルーティングを実現する．
一般に DTN におけるメッセージは，Application Protocol Data Units（APDU）6) であ

2. 関 連 研 究り，IP パケットのような 1 キロバイト規模の小さなデータ単位とは限らない．数メガバイ

Delay（or Disruption）Tolerant Networks（DTN）3) は，大きな遅延や接続状態が不安

トや数ギガバイトのメッセージも対象となり，ノード間のメッセージ転送時間やストレージ

定な性質のデータリンク上であっても，メッセージを宛先まで配送することが可能なネットの大きさを考慮すべき状況も存在する．これらは将来的には，考慮する必要があるが，本研ワークである．本研究は，この分野の中でも特にルーティングについて扱っている．ルー

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

ティングに対しては，メッセージの配送時間，通信量，バッファサイズなどのコストを小さDTN 研究の中には，宛先へのメッセージ到着確率を向上させるため，あるメッセージにく抑えることが要求される．

対し複数のコピーを作成して配送する場合がある．我々の提案手法の中に，この考え方を導

最も，原始的なルーティング手法は，Epidemic Routing 20) である．メッセージを出会っ入することも考えられるが，現在の研究段階では，メッセージのコピーを作成せずに，メッたノード間で感染させていくことで，最終的に目的地にも届くという楽観的な手法であるたセージを配送する方式のみを考えている．

め，通信リソースやメッセージプールへの負担は大きいが，メッセージの配送時間は最小にノードの位置およびその時間経過のことを本研究では行動パターンと呼ぶ．実際的な環境することができる．Spray and Wait 方式19) は転送開始時に，一定数のメッセージコピー

における行動パターンはきわめて複雑であり，本研究の中でそれらを網羅的に扱うことは困を作成しておき，それを送り出すことで，到着確率を高くする．一般に，メッセージのコ難である．そこで本研究の段階では，各ノードがそれぞれ特定の複数地点を巡回する状況を

ピーを複数作成することで，目的地まで到達する確率を高くし，到着までの時間を短くする

仮定し，その状況下で提案手法を用いると，自律分散的にメッセージの配送が可能になるこことができるが，各種リソースを消費する傾向がある．
ノードの接続関係を，将来にわたって予測し，メッセージの配送経路を最適化しようとすとを示すにとどめる．
本論文では，まず PBR のシステムモデルを定義し，その中でポテンシャルを自律分散る試みがある．ここには，将来の動作が決定的（i.e.，衛星のように軌道計算が可能）な場

的に生成する漸化式を提案，これを TCTR と呼ぶことにする．その後，TCTR の動作お合と，非決定的（i.e.，人間の行動パターンのように予測不可能）な場合によってアプロー

よび特性を述べる．実験では，プロトタイプシステムとシミュレータを使って，OLSR やチが異なる．Merugu らの提案15) では，与えられた決定的なノードの行動モデルから時空

AODV などの MANET プロトコルが適用不可能なほどにトポロジの変化が起こる環境下で間グラフを生成し，最小時間配送経路を導き出してメッセージを配送する．一方，将来の動も，TCTR を使うと宛先までメッセージ配送を行うことができることを示す．そのうえで，作が非決定的であっても，動作の傾向を学習することでメッセージのルーティング効率を高シミュレーションにより，Epidemic Routing 手法とメッセージ配送時間，ノード間で交換

めるアプローチもある．Leguay らは，MobySpace 10) と呼ぶ高次元空間に，ノードの行動されたメッセージ転送総量，メッセージプールサイズの比較を行う．Epidemic Routing は，モデルを対応づけ，ノードの存在確率を計算することで，メッセージを配送する手法を提案

原始的な Flooding 手法なため結果的にトポロジの変化に強いメッセージ配送手法となってした．PROPHET 12) や Francois ら4) も，手法は異なるが学習に基づき接続関係を予測すいるが効率に関して問題がある．そのため，Epidemic Routing はよき比較対象であり，本る方式をとっている．我々の提案方式は，ポテンシャル値の中に接続関係の情報を取り込む

研究の段階では TCTR と Epidemic Routing との間で性能比較することとした．なお，途という点で，一種の学習型アルゴリズムといえる．

中，実装時に考慮すべきメッセージ氾濫限界（詳細は 3.3 節で述べる）について言及し，実本研究では，ポテンシャル値を考え，メッセージの配送にこのポテンシャルの勾配を利用する．PBR は勾配検索法（Gradient Descent Search）の派生系として，Basu らによって，験を行っている．
以下，本論文の構成を記す．2 章で，関連研究を述べる．3 章で TCTR システムモデル

一般のネットワークにおけるトラフィックエンジニアリングの目的で使うことを念頭に提唱を提案する．4 章で実装方法，5 章で評価実験を示す．6 章で実験結果などに対する考察をされた1) ．その後，移動ネットワークや無線センサネットワークにおける Anycast での最適与え，7 章でまとめる．

ノード選択への利用が試みられている9),11) ．Volcano Routing Scheme（VRS）5) からは，

PBR 的な考えがトポロジ変化の激しいネットワークに向いていることを読み取ることがで

情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2314

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

きる．PWave 13) は電子回路における電位と電流の関係をポテンシャルとメッセージの配送に対応づけ，無線センサネットワークに応用した．実フィールドでは，ZebraNet 8) で提案されている History-based Protocol から，PBR の考え方が具体的な DTN アプリケーションにおいて実際に利用されていることが読み取れる．

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

TCTR を機器に実装する際に考えなければならない氾濫限界と転送スレッシュホルドの関係についても述べる．
本研究では，物理レベルで接続されたネットワークグラフ G = (N, E) を考える．グラフ

G 上のノード n（∈ N ）に対し，nbr(n) で n の近隣ノードの集合を表すことにする．便宜上 n は nbr(n) に含まれる（n ∈ nbr(n)）とする．いまノード n において，メッセージの宛
先ノード d（∈ N ）について考える．時刻 t における d 宛の n におけるポテンシャル値をdd

図 1 Potential-based routing（PBR）
Fig. 1 Potential-based routing (PBR).

定義し，これを V (n, t) と表記する．V (n, t) はスカラー値であり，それぞれの宛先 d には，ノードに働く力が α を超えれば，最大の力を与える近隣ノードを転送先とすることを対して独立な値を持つ．

意味する1 ．この規則で転送を繰り返し行うことで，ポテンシャル値が最も低い宛先 d に，

3.1 Potential-Based Routing（PBR）
d

時刻 t において n に存在する宛先 d とラベルづけされたメッセージの集合 M (n, t) に対し，近隣ノード k ∈ nbr(n) 方向に働く力 Fkd (n, t) を次のように定義する．

Fkd (n, t) ≡ −{V d (k, t) − V d (n, t)}

最終的にメッセージが配送される．
図 1 に PBR におけるメッセージ転送および配送の様子を示す．この図では，あるネット(1)

ここで，M d (n, t) の転送先 nexthopd (n, t) を，次の規則で与えるのが，本研究の PBR

ワーク G の物理的なノード間の接続関係を維持しながら，ノードの持つポテンシャル値を縦にとっている．この状態においては，n の近隣ノード k1 ，k2 で最大の力を与えるものは

k1 であるから，n にあるメッセージは，k1 に転送される．同様のことが繰り返し転送先で行われることで徐々に宛先 d へ近づき最終的には届く．メッセージが流れたパスのことを本による転送規則である．

研究では配送路と呼び，宛先まで届けることを配送と呼ぶ．これに対し，転送は，次のノー∀k∈nbr(n) ,Fkd (n, t) ≤ α → nexthopd (n, t) = Φ(2)

ドへメッセージを送り出す処理である．

PBR のメリットは，近隣ノードとの関係だけでメッセージの転送先を計算できる点である．グローバルなネットワークトポロジに関する情報と必ずしも同期をとらなくてもメッ∃k∈nbr(n) ,Fkd (n, t) > α → nexthopd (n, t) = {k|Fkd (n, t) =maxk∈nbr(n)Fkd (n, t)}(3)

セージの配送が可能である．
この方式を使えば，理論的には短時間（i.e.，ノードのポテンシャル値の変化がきわめて

ここで α は正の定数で，転送スレッシュホルドと呼ぶことにする．式 (2) は，ノードに働く力が α 以下のとき，メッセージの転送先は存在しないことを意味し（Φ は空集合），式 (3)情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)1 複数の候補が見つかったときは 1 つを選び送信するものとする．

c 2009 Information Processing Society of Japan


2315

DTN 環境を想定したトポロジ変化に強いメッセージルーティング少ない間）にメッセージが複数のノードの間でループすることはない．証明は付録の定理 1
を参照のこと．

3.2 ポテンシャル生成規則
PBR では，ポテンシャルが与えられていれば，式 (2)，(3) に従い，次の転送先を計算することができる．問題はどのようにこのポテンシャルを生成するかであり，本研究では，下記の漸化式により自律的に生成する手法を提案する．

V d (n, t + 1) = V d (n, t) + D

min {V d (k, t) − V d (n, t)} + ρ(4)k∈nbr(n)∀d∈N ∀tV d (d, t) = 0(5)d∀n∈N V (n, 0) = 0(6)

これは，下記（式 (7)）の離散系での拡散方程式を改良したもので，D （0 < D < 1）は

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

拡散定数を表す．この方程式は，金網上を温度が拡散する様子を記述していると見ることができる．接続されたネットワークは 1 枚の金網に相当する．2 枚の金網が接することによっにすべての宛先ノードに対するポテンシャル値を持つことができる．近隣ノード間で交換さて，その接点から他方へ温度が拡散していく．

れるポテンシャル値は，宛先ごとのベクトルとして表現され，その送信コストは，単位時間dd

V (n, t + 1) = V (n, t) + D



d

d

{V (k, t) − V (n, t)}(7)

あたり O(n) で実装することができる（Multicast で実装した場合．n はネットワーク全体のノード数）．

k∈nbr(n)

本研究で提案するポテンシャル生成規則では，上記の “温度” をポテンシャルと考え，ポこのような形式でポテンシャルを定義すれば，V d (n, t) の性質を力学的な分析から明らかを min に変換し，定数 ρ（0 < ρ < D）をにすることができる．以下では，3 種類のネットワーク状態においてポテンシャルがどのよ

テンシャルの拡散を定義している．ただし，追加した．これは，温度でいえば，低い温度成分だけ金網上を伝播させるようにし，一方で，金網全体に対して単位時間あたり ρ の熱量を加えている状況に相当する．境界条件式 (5) にうな形をとるかを述べる．

• 物理的に接続された単一ネットワークの場合（図 2）

より，宛先の温度をつねに 0 に保ち，その周囲の温度は距離が離れるに従って高くなること

ポテンシャル値は収束し，距離ベクトル型のルーティングと等価な状態になる．図 2 左になる．すなわち，宛先のポテンシャルは 0 で，距離が離れるごとにその周囲のポテンシャ

側のネットワークに対して生成される，宛先 d = n6 へのポテンシャル V n6 (n, t) の収ルが上昇するポテンシャル場が形成される．物質上の温度分布が自律分散的に作成される

束形態を図 2 の右側に示す．n6 からホップ数が増えるごとにポテンシャル値は増加し，ように，この方式を使えば，ポテンシャル場の生成も自律分散的に実現することができる．

メッセージはポテンシャルの低い方向へ配送される．この収束形態に関する証明を付録

式 (6) の初期条件は実際的な状況では必ずしも必要なく，ポテンシャル計算の開始時刻がすべてのノードで同一である必要もない．これは，この式の場合，時間変化に対して，初期条の定理 2 で述べる．

• ネットワークが物理的に分裂した場合（図 3）

件がポテンシャル値に及ぼす効果は急激に小さくなるからである（i.e.，任意の初期値からネットワークが 2 つに分裂すると，宛先ノードが属さないネットワーク・ノードのポ

始めても最終的には同じポテンシャル値を持つようになる）．

テンシャル値が増加を開始する．一般に，分裂したネットワークを G1 = (N1 , E1 )，ポテンシャル場はダイナミックに変化するものであり，各ノードはすべての宛先に対するポテンシャル値をつねに計算し続けるものである．開始時にすべての宛先ノードを知らなくG2 = (N2 , E2 ) とし，G1 に宛先ノードが存在する場合（i.e.，d ∈ N1 であるとき），N2のノードのポテンシャルは下記に収束する（c は定数）．

てもよいが，近隣ノードどうしでそれぞれの持つポテンシャル値を交換することで，最終的情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2316

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

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

∀n∈N2 V d (n, t) → ρt + c(t → ∞)(8)

図4

n1 − n5 間のリンクが接続されたことにより，2 つのネットワークが再結合する場合．n0，n1，n2，n3 で構成されるポテンシャル場に傾きが生まれ，メッセージが流れ出る
Fig. 4 Potential-ﬁeld and message delivery when n1 − n5 link has been setup, potentials of n0, n1,n2, n3 go down with making message delivery slopes.

においては最適な解を与えているといえる．式 (4) の方式に従えば，宛先 d が接続されたネットワーク内に存在していれば，実際に，そのような（i.e.，ポテンシャルの低い方にメッ

図 3 の例では，{n0, . . . , n3} のポテンシャルは ρ の速度で上昇する．このとき，{n0,セージを預けた方が，確かに宛先ノードに届きやすくなっている）ポテンシャル形状になる. . . , n3} にあるメッセージは，各ノードのメッセージプールに蓄えられる．

し，宛先 d がたとえ離れたところにあっても，周期的に宛先 d の近くに行くノードのポテ• 物理的に分裂した 2 つのネットワークが再結合する場合（図 4）
図 4 では，n1 − n5 間のリンクが接続されたことにより，2 つのネットワークが再結合

ンシャルは低めに保たれ，結果として，そのノードをリレーノードとして使うことにより，メッセージを効率的に運ぶことができる．

している．ポテンシャルの低い方のネットワークに接続したノードから順にポテンシャ

3.3 ポテンシャル伝播遅延とメッセージ氾濫現象

ルが降下し，図 4 のようにポテンシャルに傾きが生ずる．ここを伝わって {n0, . . . , n3}

ポテンシャルが一定速度で上昇する状況においては，周囲のポテンシャルは実際よりも低のメッセージプールに蓄えられていたメッセージが一気に流れ出る．

く観測される．これにより，メッセージを周囲に送り出そうとする力が働き，メッセージがこのルーティング手法を用いる場合，ポテンシャル場に谷（i.e.，極小値）が生ずる状況が周囲に対して吐き出される，いわば，氾濫と見受けられる現象が発生する．本提案では，こ存在しうる．メッセージは谷となっている場所に集まり，そのノードに保存されていく．この観測誤差により発生する「周囲にメッセージを送り出そうとする力」を，転送スレッシュのような場合でも式 (4) の力学により，時間が経つにつれ谷は消えて斜面となり，再びメッ

ホルド α（式 (2)，(3) で定義した）により相殺させることで，氾濫現象を回避しようとす

セージは流れ出すようになる．ポテンシャル場は，温度分布がダイナミックに変化するのとる．また，提案手法が適切に動作するための α の範囲（i.e.，下限値および上限値）につい同じようにダイナミックに変化し，全体的にメッセージが宛先に到達するように働く．

て言及する．

ノードとノードが出会うことによって，ポテンシャルの高い方から低い方へメッセージが式 (4) では，理論的には近隣ノード k ∈ nbr(n) が持つポテンシャル V d (k, t) も時刻 t で転送される．ここで「ポテンシャルの低い方にメッセージを預けた方が，確かに宛先ノード

取得できていることになっているが，実際に TCTR を実装する場合には，ノード間で定期的に届きやすくなっている」のであれば，本論文で提案する手法は，そのノードの行動モデルにポテンシャルを交換するため，ノード n に見える「k が持つポテンシャル（以下，Vnd (k, t)

情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2317

DTN 環境を想定したトポロジ変化に強いメッセージルーティングと記述する）」は，現時点での k が持つポテンシャル Vkd (k, t) よりも少し古いものになる．
この時間差を ΔT （0 ≤ ΔT < 1）とすると，変化したポテンシャル量に関して，Vkd (k, t) − Vkd (k, t − ΔT ) = Vkd (k, t) − Vnd (k, t)(9)が成立する．したがって，

Vnd (k, t) ≈ Vkd (k, t) − ΔT

∂Vnd (n, t)
∂t

(10)

となり，ポテンシャル値の時間変化によって，観測される近隣ノードのポテンシャル値に変
図 5 メッセージ氾濫現象の一例
Fig. 5 An example of message overﬂow phenomenon.

位が生じる．この変位が式 (4) だけからは考えられなかった，メッセージの氾濫と呼ぶ現象
を引き起こすことがある．
簡単な状況として，∀i∈N , Vid (i, t) = V (t) という，すべてのノードが平衡に同一ポテン
シャル値 V(t) を持つ場合を想定しよう．これは，図 3 に示したように分離されたネットワー

B へ送り出そうとする．同様のことは，B にもあてはまり，B は C へのメッセージを A へ

クで実際に存在しうる状況である．式 (2)，(3) において α = 0 の場合，理想的な環境下で送り出そうとする．そのため，メッセージはネットワーク内を巡り続けるのである．

は nexthopd (n, t) = Φ となり，転送先は存在しない．しかし，実際的な環境では，式 (10)

Vkd (n, t) ≈ V (t) − ΔT

∂V (t)∂t(11)

すなわち，式 (1) より，Fkd (n, t) = ΔT

氾濫現象を回避するために，観測誤差によって生ずる「周囲にメッセージを送り出そうとする力」よりも，大きな相殺力（転送スレッシュホルド α）を設定することを考える．このが成り立つため，とにすると，β<α∂V (t)∂t(12)∂V (T )となって，ポテンシャル値が増加傾向にあるとき（⇔ ∂t > 0）は，式 (3) から，

nexthopd (n, t) =「周囲にメッセージを送り出そうとする力」の最大値を β とおき，これを氾濫限界と呼ぶこ



{k}

(13)

k∈nbr(n)となり，すべてのノードが近隣ノードの 1 つを選んでメッセージを転送する状態になる．結となるように α を設定すればよい．氾濫限界 β は式 (10) より，

β = ΔT max

maxと B → C である．ある時点で，C が切り離され遠くに行ってしまったとする．このとき，(15)∂V d (n, t)= max{V d (n, t + 1) − V d (n, t)}∂t= max{D min {V d (k, t) − V d (n, t)} + ρ}k∈nbr(n)=ρ

象をメッセージの氾濫現象と呼んでいる．
具体的な場面として，図 5 の状況を取り上げる．開始時には，ノード A，B ，C はすべ∂V d (n, t)∂tで与えられ，式 (4) を用いることで（min 項はつねに 0 以下である），

果，メッセージがネットワークの中を巡り続ける状況となってしまう．本研究では，この現て相互に接続されていて，A，B における宛先 C のメッセージ転送先は，それぞれ A → C

(14)

(16)

だから，

β = ρΔT

(17)

である．

A，B の C へのポテンシャル値は，ともに同じ値で増加を開始する．A が見る B のポテン

したがって，観測誤差によって生ずる力の最大値が β = ρΔT となる（式 (17)）で，こシャル値は，B での本来のポテンシャル値より小さい．そこで A は，C へのメッセージをれを越えるように α を設定すること（式 (14)：β < α）で，「V (t) = ρt でポテンシャル

情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2318

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

値が上昇する状況（分離したネットワークで実際に起こる）」においても，式 (12) から

Fkd (n, t) = ΔT (∂V (t)/∂t) = ΔT ρ ≤ β （< α），とメッセージに働く力 F を α より小さく抑えることができる．すなわち，Fkd (n, t) < α であるから，式 (2) より，nexthop = Φ となり，メッセージが周囲に吐き出されず，氾濫現象を回避することができる．

α の上限値は，安定的に接続されたネットワークでのポテンシャル場の傾斜から求めるこρとができる．安定接続時には，宛先ノードから 1 ホップ離れるごとに， D
だけポテンシャρ
でなければならない．
ル値が上昇するため（付録の定理 2 を参照），α < D

3.4 動作条件のまとめ
本提案手法が適切に動作するための設定パラメータに関して，以下にまとめる．

(1)

定数 α，ρ，D はネットワーク全体で同一の値をとる．

(2)0 < ρ < D < 1 であるように定数 ρ，D を設定する．

(3)

ρ
ρΔT < α < Dであるように定数 α を設定する（ただし ΔT は 0 ≤ ΔT < 1 の範囲
ρとなるように設定するのが現実的であるとをとりうるため，実際には，ρ < α < D

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

思われる）．

(4)

十分に大きな値を取り扱うことが可能な型でポテンシャル値を表現する．

4. 実

(3)

装

Forwarding Table：Potential Table から V d (n, t) と ∀k∈nbr(n) V d (k, t) を与えられ，
式 (2)，(3) に従って，宛先 d ごとに転送先ノードを計算し，メッセージ転送表を作

本研究では，実際に無線端末で動作するプロトタイプシステムと，仮想的に大規模なシナリオを再現できるシミュレータを開発した．

成する．

(4)

Message Manager：アプリケーションへのメッセージインタフェースを提供し，メッ

4.1 プロトタイプシステム

セージの転送処理も行う．アプリケーションは，Message Manager に対して，メッ

図 6 に本研究で開発したプロトタイプシステムの構成を示す．4 種の機能ブロックで構

セージの配送を委託する（Send）．Message Manager が n 宛のメッセージを受信す成してある．以下，このシステムがノード n として動いている状況を考え，各機能を解説

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

対して，宛先 d をキーに Forwarding Table に転送先を問い合わせ，転送先が存在(1)

Advertisement Manager：UDP Multicast により，定期的に近隣ノード k ∈ nbr(n)すればメッセージを転送する．転送が成功すると転送先から応答として ACK が通とポテンシャル V (k, t)，V (n, t) を交換しあう．Multicast Socket を通じ，近隣ノー知される．転送先が存在しない場合や，転送に失敗したときは，そのメッセージはドから受け取ったポテンシャル V (k, t) は，PotentialTable に送られる．一方，Po-

Message Manager のメッセージプールに保存される．保存されているメッセージは，

tentialTable からは定期的に，このノード n の最新ポテンシャル V (n, t) が与えられ，
これを UDP Multicast で広告する．

(2)

Potential Table：すべての近隣ノードのポテンシャル ∀k∈nbr(n) V (k, t) をキャッシュ

定期的に再転送が試みられる．
このプロトタイプシステムは，下記内容をログとして出力する．このログは，次の評価実験での解析に利用した．

し，このノードのポテンシャル V (n, t) とあわせて V (n, t + 1) を式 (4) に従い計算• ポテンシャル値（定期的にログ出力）

する．

• Forwarding Table の内容（定期的にログ出力）

情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2319

DTN 環境を想定したトポロジ変化に強いメッセージルーティング• メッセージプールサイズ（定期的にログ出力）• メッセージ転送イベント• メッセージ送信（Send）イベント• メッセージ受信（Receive）イベント
本研究で開発したシミュレーション環境は，Java 言語で実装した．実行には，JavaVM

1.5.0，OS は Linux 2.6.15 を使用した．
図 7 シミュレータの構成
Fig. 7 TCTR simulator overview.

5. 評

価

次に述べる評価実験では，OLSR や AODV などの MANET プロトコルがそもそも使えないようなトポロジが変化する環境を作り出し，その中で TCTR を用いてメッセージを• メッセージプールサイズ（定期的にログ出力）

ルーティングできることを示す．そのうえで，TCTR がどれだけ効率良くメッセージをルー• メッセージ転送イベント

ティングできるかを調査するため，その特性上，原始的な手法によりトポロジ変化に強い• メッセージ送信（Send）イベント

ルーティングを実現できる Epidemic Routing（ただしこの手法は効率に問題がある）と，• メッセージ受信（Receive）イベント(1) 配送時間，(2) メッセージ転送の総量，(3) メッセージプールサイズ（プールに保存されここで開発したプロトタイプシステムは C 言語で実装した．実験環境は，OS が Linuxているメッセージ数）に関して比較分析を行う．

2.6.22 で，無線データリンクには 802.11g を使用している．

各節の構成は以下のようになっている．5.1 節では，プロトタイプシステムを使った実証

4.2 TCTR シミュレータ

実験により，シミュレータが実証実験の結果を再現できることを確認する．5.2 節では，プ

図 7 に，開発したシミュレータの構成を示す．3 種の機能ブロックで構成してある．以

ロトタイプシステムでメッセージ氾濫現象を観測，分析する．5.3 節では，シミュレータを下，それぞれの機能ブロックについて解説する．

(1)

対象とする実験環境（オーダ 100 秒程度の間隔をおいて，切断・再接続が発生する環境）

レッドにより動作する．Node の内部は，プロトタイプシステムとほぼ同様の構成とでは，ポテンシャルを滑らかに変化させるためには，D = 0.2，ρ = 0.02 ぐらいが適切だっなっている．ただし，Node Locator を通じて，近隣ノードへのポテンシャル通知（広たので，その設定値で実験を行った．
特に明示的な記述がない場合，実験では α = 0.02 を用いている．これは式 (16) による告）やメッセージ交換を行う．

(2)
(3)

使って大規模なシナリオで Epidemic Routing 手法との効率を比較分析する．

Node：各 Node インスタンスが，仮想的に展開されたノードに相当し，独立したス

Node Locator：Node インスタンスの（2 次元平面での）位置管理を行う．通信可能と，実験の環境 0 < ΔT < 1，ρ = 0.02 においては，氾濫限界 β は 0.02 未満であることが範囲にあるノードの発見機能，位置の操作インタフェースなどを持つ．

予測されることによる．

Mobility Manager：実験対象とする行動パターンを生成し，Node Locator を通じてノードの位置設定をする．

この実験では，物理的に隔離されたネットワーク間をノードが行き来するシナリオにおい

出力ログは，プロトタイプシステムと同様に下記を出力する．このログを評価実験での解析に使用した．

て，プロトタイプシステムによる動作の確認を行った．具体的には，ポテンシャル変化の様
子やメッセージ配送の様子を観測し，それが期待どおりのものであるか調べた．その後，シ• ポテンシャル値（定期的にログ出力）• Forwarding Table の内容（定期的にログ出力）

情報処理学会論文誌

5.1 プロトタイプシステムによる実証実験およびシミュレータの妥当性

Vol. 50

No. 9

2312–2326 (Sep. 2009)

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

c 2009 Information Processing Society of Japan


2320

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

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

Point を考え，ノード 1，4 はそれぞれ Home A，B の固定ノード，ノード 2，3 は，Home

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

A，B の住人が持つ移動ノードとする．ノード 2，3 は，Meeting Point で定期的に出会うことになっている．Home A，Meeting Point，Home B は十分に離れており，直接通信すたことを知った．結果，n4 ，n2 がそれぞれ保有していた n1 宛のメッセージ 105 通と 121

ることはできない．無線の通信範囲は（建造物などによる影響を考え）20 m ほどを想定し通を n3 ，n1 に転送し，両者はポテンシャルを降下させた．

ている．図 8 に示すように，ノード 2，3 を行動させた．各所への滞在時間は 2 分である．
移動中は無線通信範囲を 1 度出ると，どのノードとも通信はできない．図 8 に示した移動のプロセスは 20 分を周期に，繰り返される．この実験においては，ノード 4 がノード 1 宛に，10 秒に 1 回，100 バイト程度のメッセージを送信している．
図 9 に，プロトタイプシステムで実験した結果得られた，各ノードにおける（ノード1 への）ポテンシャル値 V 1 の挙動と，メッセージ配送の様子を示す．実験開始後，時刻t = 3600 から t = 4800 までの様子を示しているが，図の時間軸は，分かりやすくするため

このメッセージ配送は自律的に行われた．そして，この動作は期待どおりのものであった．
こうして TCTR ルーティングが実現可能であることが実証された．
図 10 に，シミュレータで実験した結果得られた，各ノードにおける（ノード 1 への）ポ
テンシャル値 V 1 (n, t) の挙動と，メッセージ配送の様子を示す．プロトタイプシステムの場合と同様に，時刻 t = 3600 から t = 4800 までの様子を示した（時間軸は t = t − 3600を表示している）．結果は，プロトタイプシステムの場合と，ほぼ同じだった．
こうして，シミュレータがプロトタイプシステムでの実験を再現できることを確認した．

t = t − 3600 を表示している．ここで，n1 ，n2 ，n3 ，n4 はそれぞれ，ノード 1，ノード 2，

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

ノード 3，ノード 4 に対応している．

ここでは図 5 のシナリオで，様々な転送スレッシュホルドを設定し，C 宛のメッセージ

時刻 t = 60 を過ぎて，しばらくすると n2 は n1 が近隣ノードでなくなったことを知り，
1

V (n2 , t) は上昇を開始した．t = 580 において，n3 は n2 と接続関係になったことを知り，


保有していたメッセージ 122 通（これは，t = −1140 から t = 60 の間に n4 で生成され1n3 に転送されていた）を n2 に転送した．そして V (n3 , t) を降下させた．その後，n2 とn3 は Meeting Point を離れ，t = 1140 において，n4 は n3 と，n2 は n1 と接続関係になっ情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)の転送先がどのように収束するかを観測した．
式 (16) によると，実験の環境 0 < ΔT < 1，ρ = 0.02 においては，氾濫限界は，0.02 未
満であることが予測される．実際に α を {0.000, 0.010, 0.015, 0.020, 0.025, 0.030} に設定
し，図 5 の状態を作ることで，生成される転送先を調べた．
表 1 に実験結果を示す．各 α に対して 3 回ずつ図 5 のシナリオを再現することで，Nodec 2009 Information Processing Society of Japan


2321

DTN 環境を想定したトポロジ変化に強いメッセージルーティング“偏り” の状態は，片方のノードが氾濫現象を起こしていることを表している．α が 0.02
では氾濫現象はほぼ見られなくなり，この値を超えると現れなくなっている．

5.3 配送時間，転送総量，プールサイズ
この実験では，シミュレータを用いて，100 台規模のノードが存在する環境を仮想的に作り出し，メッセージ配送時間，メッセージ転送総量，メッセージプールサイズに関して評価を行っている．
評価においては，Epidemic Routing との比較を行った．実験に用いた Epidemic 方式は，次の方法でメッセージ配送を行う．いま，ノード A（∈ N ）とノード B（∈ N ）を考え，A，B が保持しているメッセージの集合をそれぞれ MA ，MB とする．ノード A と B が出会ったときに，次の規則でメッセージ交換を行う．

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

m ∈ MA ∧ ¬m ∈ MB → T ransf erA (m, B)(18)m ∈ MB ∧ ¬m ∈ MA → T ransf erB (m, A)(19)

ここで，T ransf erX (m, Y ) は，ノード X がメッセージ m をノード Y に転送することを意味する．結果，∀m(m ∈ MA ↔ m ∈ MB )表 1 メッセージ氾濫限界の計測結果
Table 1 An analysis of message overﬂow limit.

α
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
Φ
Φ
Φ
Φ
Φ
Φ
Φ
Φ
Φ
Φ

(20)

となる．各メッセージ m には，宛先ラベルがついていて，宛先に到達したらそのメッセー
Statusジはアプリケーションに届けられる．Epidemic 方式は，メッセージの配送にかかる時間を最小化することができる．本研究では，Epidemic 方式の配送時間と TCTR の配送時間をループ
偏り ループ偏り
偏り ホールド
ホールド
ホールド

比較することで，どの程度の効率があるかを調査した．いずれの場合もメッセージの Time

To Live（TTL）は無限大に設定している．
実験では，次のようにノードの行動パターンを設定した（Epidemic と TCTR で同じ行動パターンを利用した）．2000 [m] × 2000 [m] の 2 次元平面に，半径 0〜300 [m] の円運動をするノードを 100 個配置した．無線通信可能半径は 150 [m] で，回転周波数は，0〜0.01 [Hz]である．行動パターンとしては，Random Way Point（RWP）2) も考えられるのだが，本研

A での転送先と Node B での転送先を調べた．この表には，その結果および，その結果か

究では，ノードが巡回的に行動する状況を考えているため RWP での評価は行っていない．

ら分かるネットワークの状態（Status）が記載されている．“A” は転送先が Node A，“B”

時刻 t = 0 から動作を開始し，t = 10000 にすべてのノードがすべてのノードに対しては転送先が Node B，“Φ” は転送先が存在しない，ことを意味する．状態について，“ルーいっせいにメッセージを送信する（t = 10000 は，TCTR においてポテンシャル情報が全プ” は，メッセージがネットワーク内を巡回する状態になったことを意味し，“偏り” はいず

体に行きわたるために十分な時間である）．

れか片方のノードにメッセージが集まる状態になったこと，“ホールド” はメッセージは転送されない状態になったことを意味している．複数の状態が観測された α に対しては，すVol. 50

図 11 に，Epidemic 方式での配送時間 T ime(Epidemic) と TCTR 方式での配送時間

T ime(T CT R) の関係を示す．それぞれの点は（送信元：宛先）のペアに対応する．この図にべての状態を記載した．

情報処理学会論文誌

5.3.1 メッセージ配送時間

No. 92312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2322

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

図 11 転送時間の関係
Fig. 11 Delivery latency correlation between Epidemic and TCTR.

図 12

配送時間の倍率とその分布
T ime(T CT R)

Fig. 12 The rate of delivery latencies T ime(Epidemic)

and its distribution.

は，T ime(T CT R) = T ime(Epidemic) である線を書き込んである．各点は，T ime(T CT R) ≥T ime(Epidemic) の領域に存在することが読み取れる．
T ime

図 12 に，配送時間の倍率 T ime (T CT R)(Epidemic)と，その倍率に属したメッセージ配送処理の分布を示す．この図から，最短時間で運ばれる（Epidemic の）場合と比べ，2 倍の時間内に約 33%のメッセージが配送され，3 倍の時間内に約 50%のメッセージが配送されたことが分かった．10 倍以上の時間がかかって配送されたメッセージは，全体の 5%程度であることも分かった．

5.3.2 メッセージ転送総量
図 13 に，Epidemic 方式と TCTR 方式でのメッセージ転送総量を示す（時刻は，メッ
セージ配送を開始した t = 10000 を 0 として表示している）．転送総量とは，任意のノードa（∈ N ）からノード b（∈ N, a = b）へメッセージ転送があった場合にカウントされるグ
ローバルな変数である．この図から読み取れるように，Epidemic 方式では，TCTR に比べておよそ 10 倍のメッセージ転送を行った．Epidemic 方式は，すべてのノード（= 100 台）
それぞれが 100 個のノードから発される 100 カ所へのメッセージ転送処理すべてに加担するため，最終的に全体で約 106 回の転送を行ったと読み取れる．一方，TCTR では，各ノー

図 13 メッセージ転送総量の変化
Fig. 13 The total message transmissions in the network.

ドは，100 個のノードから発される 100 カ所へのメッセージ転送の一部のみを行ったため，情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2323

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

プロトタイプシステムを使って実際にメッセージ氾濫現象を観測し，氾濫限界 β が 3.3 節
で与えたモデルに従っていることが確認された．これにより TCTR を実環境に展開するときに，転送スレッシュホルド α の適性値を設計することが可能になったといえる．
シミュレータによる 100 台規模の環境の評価では，配送時間が最短となる Epidemic Rout-ing との比較を行った．結果，実験の環境では，Epidemic 方式でかかる時間の 3 倍以内の時間で，およそ半数のメッセージが配送された．ここで TCTR に対して，Epidemic 方式は通信量にしておよそ 10 倍，メッセージバッファ量に関しては 100 倍以上のコストがかかっている．配送時間の遅れが十分許容できるのであれば，TCTR を使ったほうが，リソースの消費が少なく済むといえる．
本研究では，巡回的な行動パターンについてのみ扱い，一般的な行動パターンについては扱わなかった．また，メッセージ単位の大きさ，通信帯域，トラフィックの輻輳を考慮した
図 14 メッセージプールの平均サイズ
Fig. 14 The average number of stored messages.

メッセージ転送などは無視していた．メッセージ単位が大きく，通信帯域の狭い通信であれ
ば，1 つのメッセージの転送にかかる時間が無視できなくなってしまう7) ．将来的には，このような状況も想定する必要があると考えている．

約 105 回の転送で済んだものと思われる．

5.3.3 メッセージプールの大きさ

7. お わ り に図 14 に，Epidemic 方式と TCTR における平均メッセージプール量の時間変化を示す

本研究では，DTN 環境向けに，トポロジ変化に強いルーティング手法である TCTR を（時刻は，メッセージ配送を開始した t = 10000 を 0 として表示している）．Epidemic 方式提案した．メッセージの転送に PBR の勾配法を用い，ポテンシャルの生成を自律分散的にでは，メッセージプールの大きさが時間の経過とともに増加し 10000 で安定しようとして行う，時間に関する漸化式を定義した．

いる．一方，TCTR では，メッセージプールが最初 97 まで増加したが，時間の経過ととも

プロトタイプシステムを開発し，TCTR が実際に実装可能であることを示した．そして，

OLSR や AODV などの MANET プロトコルを適用できないようなトポロジが変化する環に減少している．

Epidemic 方式では，すべてのノードがネットワークに存在するすべてのメッセージをメッ

境においても TCTR であればメッセージを宛先まで配送できることを示した．本論文の中セージプールに保存する．100 個のノードから，100 カ所へメッセージが配送されたので，では，実装時に想定しなければならないメッセージ氾濫現象について言及およびモデル化

100 × 100 = 10000 に収束したのだと考えられる．TCTR の場合はメッセージは複製されし，評価試験では，このモデルの検証も行った．

ず配送が完了すればネットワークから消えていくため減少したのだと考えられる．

6. 考

原始的な手法でメッセージを配送する Epidemic Routing は，その特性上，トポロジ変化に強いルーティング手法となっているが，Flooding するため，効率に関して問題がある．

察

本研究では，Epidemic Routing と TCTR との間での性能の評価を行った．TCTR を用い本研究では，プロトタイプシステムによる実機での動作検証と，シミュレータによる大規

ると，特に巡回的にノードが行動するシナリオにおいて，自律的にポテンシャルを生成し，模な状況を想定した評価実験を行った．同じ行動パターンを用意すれば，プロトタイプシス

メッセージを効率良く配送できた．ノード数 100 台の環境において，Epidemic Routing とテムでのポテンシャルやメッセージ配送の挙動を，シミュレータによる実験で再現できた．

比較した結果，約半数のメッセージが最短の 3 倍以内の時間で配送され，メッセージ転送総これはシミュレーション実験の結果にある程度の妥当性を与えるものである．

量は 10 分の 1，メッセージプールサイズは 100 分の 1 以下にまで抑えられた．

情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2324

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

参

考

文

献

1) Basu, A., Lin, A. and Ramanathan, S.: Routing Using Potentials: A DynamicTraﬃ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 Trans. Mobile Computing, Vol.2, No.3, pp.257–269 (2003).
3) Fall, K.: A Delay-Tolerant Network Architecture for Challenged Internets, ACM
SIGCOMM 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, IEEESECON, 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.:
Energy-Eﬃ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.:
Connectivity-aware 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. and Firoiu, V.: PWave: A Multi-source Multisink 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).

情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)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 Raghavendra, C.S.: Spray and Wait: An EﬃcientRouting 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).

付

録

この付録では，経路にループが生じないこと，および，ポテンシャル値の収束に関する証明を行う．ノード間の接続状態に応じてポテンシャル値はダイナミックに変化するため，すべてのノードの行動モデルに対して，網羅的に証明することは不可能である．なお，収束値に関する厳密な証明は本論文の範囲を越えると判断し，簡潔な証明にとどめる．
本論文では，短時間という条件の下で，経路ループが発生しないことを示し（定理 1），ト
ポロジが安定的に接続されているといった限定的な条件のもとポテンシャルの収束値について述べ，簡単な証明を行う（定理 2）．
定理 1：短時間にメッセージがループする経路は発生しない
ただし，短時間とは，近似的にポテンシャルの変化がないものとして扱えることを表すものとする．
証明）背理法により証明する．
今，経路にループがあると仮定しよう．つまり，x1 → x2 → . . . → xn （= x1 ）の順でメッセージが配送されると仮定する．
式 (3) より，V d (x1 ) > V d (x2 ) > . . . > V d (xn ) が成立しなければならないが，V (xn ) = V (x1 ) であるから，これは成立しえない．
ゆえに，経路にループが存在することはない．
定理 2：ポテンシャル値の収束
ノード d から h ホップ目のノード集合を hoph (d) と定義するとき（h ≥ 0），トポロジが安定的に接続されているネットワークにおいては，n ∈ hoph (d) のポテンシャル値 V d (n, t)
に関して，

c 2009 Information Processing Society of Japan


2325

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

lim {V d (n, t)} = h

t→∞

ρ
D

(21)

γ = lim { min {V d (l, t)}} +t→∞ l∈nbr(j)

ρ
D

(31)

があげられる．もし，一定時間後（⇔ ある時刻以降）に，となる．
証明） 帰納法により証明する．

∀i ∈ hopk (d), ∀m ∈ hopk+2 (d), V d (i, t) < V d (m, t)

h = 0 のとき，

(32)

lim {V d (n, t)} = lim {V d (d, t)} = 0(22)となれば，minl∈nbr(j) {V d (l, t)} は V d (i, t)（∃i ∈ hopk (d)）となり，V d (i, t) は収束し，

ρ
=0
D

(23)

0 < D < 1 なので，V d (j, t) は γ に収束する．したがって，式 (31) の第 1 項に関して，ρ
lim { min {V d (l, t)}} = lim {{V d (i, t)}} = k(33)t→∞ l∈nbr(j)
t→∞
D

t→∞

h

t→∞

なので成立．

h = k のとき（k ≥ 0）なので，V (j, t) の収束値は，

式 (21) が成立する，すなわち，hopk (d) のノード i のポテンシャル値が，lim {V d (i, t)} = k

t→∞

ρ
D

lim {V d (j, t)} = k(24)となると仮定する．このとき，t→∞である（ここで j ∈ hopk+1 (d) である）．ゆえに，h = k + 1 のときも，成立することが示
なお，一定時間後に，式 (32) が成立することは，次のようにして示される．

lim {V d (j, t)} = (k + 1)

t→∞

ρ
D

(25)

宛先 d から k ホップ以上のノードが持つポテンシャル値の最小値について考え，これが，一定時間後に必ず k ホップ目のノードが最小値を与えるようになることを利用し，証明する．

となることを証明すればよい（ここで，ノード j ∈ hopk+1 (d) である）．さて，式 (4) に代入した，

今，宛先 d から k ホップ以上のノードの集合を，

Z d (k) =dddV (j, t + 1) = V (j, t) + D min {V (l, t) − V (j, t)} + ρ(26)l∈nbr(j)V d (j, t + 1) = V d (j, t) = γ

(27)

(28)

l∈nbr(j)ρmin {γ − V (l, t)} =Dl∈nbr(j)ρ
γ = min {V d (l, t)} +Dl∈nbr(j)dhopx (d)

(35)

x≥k

とする．n ∈ Z d (k) において，V d (n, t) を最小にする n を考える．
る．これは，最小値を与えたノード（Z d (k + 1) にあった場合）は，次の時間には ρ 分
増加することを意味する．

n が Z d (k + 1) に含まれない場合：この場合は，n が hopk (d) に含まれている場合と同値が成立するので，γ の候補値としては，

γ = γ + D min {V d (l, t) − γ} + ρn が Z d (k + 1) に含まれる場合：その n に対して，V d (n, t + 1) = V d (n, t) + ρ が成立すから，まず収束値 γ の候補を求めよう．収束状態においては，である．次の時間においても，n ∈ hopk (d) のノード n （n = n の場合もある）が最小値を与える．これは，式 (4) に従えば，hopk (d) のノードが Z d (k) 内で最小値を持て(29)ば Z d (k + 1) のノードのポテンシャル値は，それよりも小さくなりえないためである(30)（証明省略）．
上記の 2 つから，最終的には，hopk (d) のノードが最小値を持つようになり，hopk (d) のρに収束する．この状態になると，式 (4) に従え
ノードのポテンシャル値は，仮定により k D

すなわち，

情報処理学会論文誌

(34)

された．

h = k + 1 の場合に

d

ρ
ρ
ρ
+
= (k + 1)
D
D
D

Vol. 50

No. 9

2312–2326 (Sep. 2009)

c 2009 Information Processing Society of Japan


2326

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

ば，Z(k) のノードで hopk (d) 以外のノードは，この値をとることはない（証明省略）．し落合 秀也（学生会員）

たがって，上記の式 (32) は成立する．

昭和 58 年生．平成 18 年東京大学工学部電子情報工学科卒業．平成 20

ゆえに，h = k + 1 の場合も成立する．

年東京大学大学院情報理工学系研究科修士課程修了．同年同大学院同研究

以上，数学的帰納法により，定理 2 の成立することは証明された．

科博士後期課程，現在に至る．ファシリティマネージメントシステム，広(平成 20 年 12 月 25 日受付)

域センサネットワーク，耐遅延ネットワークの研究に従事．

(平成 21 年 6 月 4 日採録)

推 薦 文

江崎

本論文は，ノード間の接続が不安定な環境下で効率良くメッセージ配送をするために，

浩

昭和 38 年生．昭和 62 年九州大学大学院工学系研究科電子工学専攻修士

Potential-Based Routing の概念を導入した新しいルーティングプロトコルを提案している．

課程修了．同年（株）東芝入社．平成 2 年米国ニュージャージ州ベルコア

ルーティングプロトコルとしての理論的な検討とともに，シミュレーション・実証実験を行社．平成 6 年コロンビア大学客員研究員．平成 10 年東京大学大型計算

いその特性を明らかにしており，MANET，無線センサネットワークなどの研究に大きく寄機センター助教授．平成 13 年同大学大学院情報理工学系研究科助教授．

与することが期待されるため，論文誌の推薦論文としてふさわしい．

平成 17 年同大学院同研究科教授，現在に至る．工学博士（東京大学）．

（マルチメディア，分散，協調とモバイル（DICOMO2008）シンポジウム
プログラム委員長 串間和彦）

情報処理学会論文誌

Vol. 50

No. 9

2312–2326 (Sep. 2009)

MPLS-JAPAN 代表，IPv6 普及・高度化推進協議会専務理事，WIDE プロジェクトボード
メンバ，JPNIC 副理事長，ISOC 理事．

c 2009 Information Processing Society of Japan