疫学的ルーティングとSpray-and-Wait — 接触機会が予測できないDTN環境の経路制御

この回で学ぶこと

前回、私たちは Contact Graph Routing (CGR) という、深宇宙ネットワークにおける経路制御アルゴリズムを学びました。CGRの美しさは、周回機の軌道やアンテナの可視時間帯が軌道力学によってあらかじめ正確に予測できるという事実を全面的に活用し、「時刻表を見ながら乗り継ぎを計算する」という発想でダイクストラ法を時間依存グラフの上に拡張したことにありました。CGRが最適に機能するのは、まさにこの接触機会のスケジュールが既知であるという前提が成り立つ場合に限られます。

しかし、DTN(Delay/Disruption Tolerant Networking)が想定する環境は、必ずしもそこまで行儀の良いものばかりではありません。月面や火星表面を移動する複数のローバーが、互いにどこにいて、いつ無線の届く距離まで近づくのかを事前に正確に予測することは、軌道力学ほど簡単ではありません。地形による回り道、科学観測のためのその場停止、通信途絶からの経路変更——ローバーの移動計画は地上のミッションチームによってある程度は事前に決められるものの、実際の移動は不確実性を伴います。さらに視野を広げれば、DTNはもともと地上の**モバイルアドホックネットワーク(MANET)**や、野生動物の行動追跡、災害時の断続的通信網など、ノードの動きがほとんど予測不能な環境のために生まれてきた研究分野でもあります。

この回では、CGRとは正反対の前提——接触機会がいつ発生するか全く予測できない——の上で設計された2つの代表的なDTNルーティングアルゴリズム、疫学的ルーティング(Epidemic Routing)とSpray-and-Waitを扱います。どちらも「出会ったノードにデータのコピーを渡す」という素朴な発想を出発点にしますが、そのコピーの配り方によって、到達性・遅延・資源消費のトレードオフがまったく異なる姿を見せます。CGRの厳密な最適性と対比しながら、この2つのアルゴリズムを数式で追い、最後に「どの環境でどの戦略を選ぶべきか」という設計判断の軸を整理します。

直感的導入: 時刻表・うわさ話・チラシ配り

CGRを「時刻表を見ながら乗り継ぎを計算する旅行者」に例えるなら、この回で扱う2つのアルゴリズムは、時刻表そのものが存在しない世界での情報の伝わり方に例えられます。

疫学的ルーティングは「うわさ話」です。 ある人が面白いニュースを知ったとします。この人は、道で偶然すれ違った知り合い全員にそのニュースを話します。話を聞いた人もまた、次に出会った人全員に話します。誰がいつ誰に出会うかは予測できませんが、うわさ話は指数関数的に広がっていき、やがて(十分な時間があれば)ほぼ全員がそのニュースを知ることになります。感染症が接触によって指数的に広がっていく様子——**疫学(epidemiology)**のSIモデル——とまったく同じ数理構造を持つため、この名前が付いています。データを持っているノードが「感染している」、まだ持っていないノードが「感受性がある(susceptible)」というわけです。

Spray-and-Waitは「限られた枚数のチラシ配り」です。 街頭で新製品の宣伝チラシを配るとします。印刷できるチラシの枚数には予算の上限があるので、無限にコピーして配るわけにはいきません。そこで、最初に決めた枚数 $L$ 枚だけを、出会った人に次々と(半分ずつ)手渡していきます。チラシが尽きたら、あとは自分の手元の1枚を、目当ての本人に直接会えたときだけ渡す——という戦略です。うわさ話ほど広くは伝わりませんが、印刷コスト(=ネットワークの帯域とバッファという有限資源)を使い切ることなく、それなりの確率で目的の人にニュースを届けられます。

以下では、この2つの直感を、CGRのときと同じように数式で厳密に定式化していきます。

疫学的ルーティング: 出会うノード全てにコピーを渡す

アルゴリズムの定義

疫学的ルーティング(Vahdat & Becker, 2000)のルールは単純です。各ノードは、自分が保持しているバンドル(メッセージ)のID一覧をサマリベクトルとして持ち、他のノードと通信可能な範囲に入るたびに、互いのサマリベクトルを交換します(この手続きをアンチエントロピーと呼びます)。交換の結果、相手が持っていないバンドルがあれば、そのコピーを渡します。重要なのは、コピーを渡した後も、渡した側は自分の手元のコピーを消さないという点です。つまり、あるバンドルを保持しているノードの数は、接触が起きるたびに単調に増加していきます。

$$\text{(ノード } i \text{ が持つバンドル)} \xrightarrow{\text{接触}} \text{(ノード } i \text{ も } j \text{ も両方が保持)}$$

これを繰り返せば、宛先ノードが他のどれか1つのコピー保持ノードと接触機会さえ持てれば、バンドルは確実に届きます。CGRが「経路をあらかじめ計算してから送る」のに対し、疫学的ルーティングは「経路を計算せず、ひたすら複製して拡散させることで、結果的にどこかの経路がつながることに賭ける」という、まったく逆方向のアプローチです。

平均場近似によるSIモデル

このコピー数の増え方を定量的に見てみましょう。ノード総数を $N$(宛先ノードを含む)とし、任意の2ノードが単位時間あたり平均 $\lambda$ 回の割合で独立に出会う(接触機会を持つ)と仮定します。これは、ノードの移動をランダムウェイポイントやランダム方向モデルで近似したときによく使われる指数分布接触モデルで、DTN性能解析の標準的な出発点です。

時刻 $t$ において、あるバンドルのコピーを保持しているノードの数を $I(t)$(疫学モデルでいう「感染者数」)とします。$I(t)$ 人の保持者のそれぞれが、まだ保持していない $N - I(t)$ 人のいずれかと、率 $\lambda$ で接触する可能性があるので、コピー保持者数の増加率は次の常微分方程式(平均場近似)で近似できます。

$$\frac{dI(t)}{dt} = \lambda\, I(t)\,\big(N - I(t)\big), \qquad I(0) = 1$$

これは標準的なロジスティック方程式であり、厳密解は

$$I(t) = \frac{N}{1 + (N-1)\,e^{-\lambda N t}}$$

となります。

コピー数の指数的増加

この解の振る舞いを2つの領域に分けて見ると、疫学的ルーティングの特徴がよく分かります。

初期(コピー数が少ない)領域: $I(t) \ll N$ のとき、分母の $(N-1)e^{-\lambda N t}$ が支配的になるため、上の解は近似的に

$$I(t) \approx e^{\lambda N t}$$

と書けます。つまりコピー保持者数は時間に対して指数関数的に増加します。これは、ネットワーク全体のノード数 $N$ が大きいほど、拡散の実効的な速さ $\lambda N$ も速くなることを意味します——ちょうど、感染症の基本再生産数が大きいほど流行が急速に立ち上がるのと同じ構造です。

後期(飽和)領域: $t$ が十分大きくなると $I(t) \to N$ に収束し、増加は頭打ちになります(ロジスティック曲線特有のS字カーブ)。

資源消費のトレードオフ

疫学的ルーティングの利点は明白です。$I(t) \to N$ に向かって指数的に広がっていくため、宛先が生きてネットワークのどこかに存在する限り、到達性はほぼ最大化されます。CGRのように厳密なスケジュール情報を必要とせず、ノードは自分の出会った相手と単純なルールでやり取りするだけで済みます。

しかし代償も同じ数式から読み取れます。1つのバンドルが最終的に保持されるノード数の期待値は最大で $N$ に達するので、

$$(\text{総バッファ消費量}) \sim O(N) \times (\text{バンドルサイズ}), \qquad (\text{総送信回数}) \sim O(N)$$

というオーダーで、ネットワーク規模 $N$ に比例して膨れ上がります。宛先が1つしかないメッセージのために、ネットワーク中のほぼ全ノードのバッファと帯域を消費してしまうという、著しい資源効率の悪さがここに定量的に表れています。ノード数が数百・数千に及ぶセンサーネットワークやモバイルアドホックネットワークでは、この $O(N)$ という資源消費は現実的な制約(限られたフラッシュメモリ容量、限られた無線帯域)にすぐに突き当たります。

Spray-and-Wait: コピー数に上限を設ける

Binary Spray and Wait アルゴリズム

疫学的ルーティングの資源浪費を抑えつつ、経路情報なしでも動作するという利点は保ちたい——そこで提案されたのが Spray-and-Wait(Spyropoulos, Psounis, Raghavendra, 2005)です。発想はチラシ配りの比喩の通り、最初に上限 $L$ 個のコピーだけを用意し、それ以上は絶対に増やさないという制約を課すことです。

アルゴリズムは2つのフェーズからなります。

Spray(散布)フェーズ: 発信元ノードは $L$ 個のコピーを持って出発します。あるノードが $n > 1$ 個のコピーを保持しているとき、まだ1個もコピーを持っていないノードと出会うと、そのうち $\lfloor n/2 \rfloor$ 個を相手に渡し、自分は $\lceil n/2 \rceil$ 個を保持し続けます(Binary Spray and Wait)。

$$(n) \xrightarrow{\text{接触}} \big(\lceil n/2 \rceil,\ \lfloor n/2 \rfloor\big)$$

この「半分ずつ分配」を繰り返していくと、コピー保持者数は二分木状に倍々で増えていき、最終的に $L$ 人のノードがそれぞれちょうど1個ずつコピーを持つ状態に到達します。

Wait(待機)フェーズ: コピーを1個だけ持つノードになった時点で、そのノードはもう他のノードにコピーを分配しません。宛先ノード本人と直接出会ったときにのみバンドルを渡す(direct transmission)、という受動的な状態に移行します。

疫学的ルーティングとの決定的な違いは、$n=1$ になったノードがそれ以上コピーを複製しないという規則にあります。これにより、ネットワーク中を漂うコピーの総数は常に高々 $L$ 個に保たれ、$N$ に依存しません。

$$(\text{系全体のコピー総数}) \le L \quad (\text{時刻によらず一定})$$

コピー数の保存と配送遅延の近似

Spray-and-Waitの性能を、疫学的ルーティングと同じ平均場近似の枠組みで見積もってみましょう。Spray フェーズの間、コピー保持者数 $m(t)$ の増え方は、$m \ll N$ の範囲では疫学的ルーティングとまったく同じ力学に従います(まだ相手ノードのほとんどが未保持なので、区別がつかないからです)。

$$m(t) \approx e^{\lambda N t} \qquad (m(t) \ll N)$$

ただし疫学的ルーティングと違い、この増加は $m(t) = L$ に到達した時点で強制的に止まります(それ以上分配できるコピーが残っていないため)。したがって Spray フェーズにかかる時間 $t_{spray}$ は、$m(t_{spray}) = L$ を上の近似式に代入して、

$$t_{spray} \approx \frac{\ln L}{\lambda N}$$

と見積もれます。Spray フェーズが終わると、$L$ 人のコピー保持者がそれぞれ独立に、率 $\lambda$ で宛先ノードと接触する可能性を持つ Wait フェーズに入ります。$L$ 個の独立な指数分布(それぞれ率 $\lambda$)の最小値もまた指数分布に従い、その平均は

$$\mathbb{E}[t_{wait}] \approx \frac{1}{\lambda L}$$

です(直感的には、$L$ 人が同時に宛先を探しているので、実効的な出会いの率が $L$ 倍になる)。以上より、Spray-and-Waitの配送遅延の期待値はおおよそ

$$\mathbb{E}[D_{SW}] \approx \underbrace{\frac{\ln L}{\lambda N}}_{\text{Sprayフェーズ}} + \underbrace{\frac{1}{\lambda L}}_{\text{Waitフェーズ}}$$

と近似できます。この式は、$L$ の選び方が持つトレードオフを明確に示しています。$L$ を大きくすれば Wait フェーズの待ち時間 $1/(\lambda L)$ は短くなり疫学的ルーティングの性能に近づいていきますが、同時にネットワークに撒くコピー数(=資源消費)も増えます。逆に $L$ を小さくすれば資源消費は減りますが、Wait フェーズで宛先に出会うまでの待ち時間が長くなります。$L=1$ は「発信元が宛先と直接出会うまで待つだけ」という最も資源効率の良い(しかし最も遅い)戦略に一致し、$L \to N$ は疫学的ルーティングに漸近していきます。実際、移動モデルに関する既存の解析では、総送信回数をおよそ $O(\sqrt{N})$ に抑えつつ、疫学的ルーティングの遅延の定数倍以内に収める(すなわち $O(N)$ の資源を使わずに近い性能を得る)最適なコピー数のオーダーが $L^\ast = O(\sqrt{N})$ 程度になることが知られています。

ルーティング戦略の選択基準

ここまでの議論を、接触機会の予測可能性という1つの軸に沿って整理し直すと、次のように見通しが良くなります。

	接触機会の性質	代表的な適用領域
CGR	軌道力学により将来まで正確に予測可能	深宇宙探査機↔中継衛星↔地上局、月・火星の周回機ネットワーク
疫学的ルーティング	完全に予測不能、移動はランダムに近い	野生動物追跡、都市部の歩行者間通信、災害直後の断続ネットワーク
Spray-and-Wait	予測不能だが資源が乏しい	センサーネットワーク、バッテリー・帯域が限られたモバイル端末群

CGRが前回学んだように最適に機能するのは、接触機会の $t_{start}, t_{end}, R_{ij}$ を含むコンタクトプランが事前に配布できる場合に限られます。逆に言えば、コンタクトプランを作ること自体が不可能——ノードの位置や移動経路がミッション計画側の統制の外にある——環境では、CGRは原理的に適用できません。疫学的ルーティングとSpray-and-Waitは、まさにこの「コンタクトプランが存在しない」領域を埋めるために設計された、根本的に異なる思想のアルゴリズムです。

重要なのは、これらは互いに排他的な選択肢ではなく、同じネットワークの中に両方の性質を持つ区間が混在しうるということです。次節で見るように、実際の惑星探査ミッションではこの混在こそが現実的な課題になります。

実務での使われ方

地上・海洋・野生生物追跡での疫学的ルーティングとSpray-and-Wait

疫学的ルーティングとSpray-and-Waitは、もともと深宇宙用途ではなく、地上のモバイルアドホックネットワーク研究から生まれたアルゴリズムです。プリンストン大学とラトガース大学のZebraNetプロジェクトは、ケニアの平原に生息するシマウマにGPS付きの首輪型センサーノードを装着し、シマウマ同士がすれ違うたびにデータを転送し合うことで、基地局まで観測データを運ぶという、疫学的ルーティングに近い発想の野生動物追跡ネットワークを実証しました。また、農村部でのインターネットアクセスを目的としたDakNetプロジェクト(MITメディアラボ)は、路線バスに搭載した無線ノードが村の中継局と都市部のインターネット拠点の間をデータの「運び屋(データミュール)」として往復する、ストア・アンド・フォワード型の接続を実現しています。

学術的な性能評価には、ヘルシンキ工科大学(現アールト大学)が開発した ONE Simulator (Opportunistic Network Environment Simulator) がデファクトスタンダードとして広く使われており、疫学的ルーティング、Spray-and-Wait、そしてこの回では扱わなかった多数の亜種アルゴリズム(PRoPHET、MaxPropなど)の配送率・遅延・オーバーヘッドをさまざまな移動モデルの上で比較できます。

惑星表面ローバー群のハイブリッドルーティング

深宇宙分野に話を戻すと、CCSDSやNASA/JPLの研究コミュニティでは、単一のローバーと単一の周回機という構図を超えた、複数ローバーが協調する惑星表面ネットワークの構想が議論されています。将来の火星・月面ミッションで複数台のローバー(あるいはローバーとヘリコプター型探査機、固定型の科学ステーションなど)が同じ地域で活動する場合、ローバー間の通信機会には2つの性質が混在します。

• ローバーが地上からアップロードされた移動計画に従って走行している近未来の区間では、互いの相対位置はある程度予測可能で、CGR的なコンタクトプランに近いスケジューリングが可能です。
• 一方、障害物回避による経路変更や、予定外の科学観測での停止、通信途絶からの再接続などにより、実際の接触タイミングは計画から外れることが避けられません。

このような部分的に予測可能・部分的に予測不能な環境では、既知のスケジュール区間はCGRで、予測が外れた場合や計画外の遭遇はSpray-and-Wait的な「保険」の複製戦略で補う、というハイブリッドルーティングが現実的な解になると考えられています。ローバーが周回機との定時交信機会にはCGRの経路計算を、ローバー同士のすれ違いには少数コピーのSpray-and-Waitを併用する構成は、次回学ぶメッシュネットワーキングの文脈でも重要な設計要素になります。

演習問題

1. ノード数 $N = 50$、接触率 $\lambda = 0.002$(1分あたりの任意の2ノード間の接触回数)の疫学的ルーティングにおいて、$I(t) \ll N$ が成り立つ初期領域での近似式 $I(t) \approx e^{\lambda N t}$ を用いて、コピー保持者数が $I(t) = 10$ に達するまでのおおよその時間 $t$(分)を求めよ。またこの近似が破綻し始めるのは $I(t)$ がおよそいくつを超えたあたりか、ロジスティック方程式の形から論じよ。

2. 上と同じ $N=50$, $\lambda=0.002$ の環境で、Spray-and-Wait を $L=8$ で運用するとする。本文の近似式を用いて Spray フェーズの所要時間 $t_{spray}$ と、Wait フェーズの期待待ち時間 $\mathbb{E}[t_{wait}]$ をそれぞれ計算し、合計の期待配送遅延 $\mathbb{E}[D_{SW}]$ を求めよ。

3. 総送信回数(=資源消費)の観点で、疫学的ルーティング($O(N)$)とSpray-and-Wait($O(L)$、$L$ は固定)を比較したとき、$N$ が10倍に増えると両者の資源消費はそれぞれどう変化するか。この違いが、ネットワーク規模が大きくなるほど深刻になる理由を、本文の数式に基づいて説明せよ。

4. CGRが疫学的ルーティングやSpray-and-Waitに対して原理的に持つ優位性は何か、逆にCGRが原理的に適用できない状況とは何か。惑星表面のローバー群を例に、両者を組み合わせるハイブリッドルーティングがなぜ必要になるのかを自分の言葉で説明せよ。

まとめと次回予告

CGRが「接触機会のスケジュールを正確に知っている」という強い前提の上に成り立つ最適な経路計算だったのに対し、疫学的ルーティングとSpray-and-Waitは、その前提が崩れた世界——出会いがランダムにしか起こらない世界——でどう振る舞うべきかという、まったく異なる問いに対する答えでした。疫学的ルーティングはコピー数を $O(N)$ まで指数的に増やすことで到達性を最大化し、Spray-and-Waitはコピー数の上限 $L$ を固定することでその資源消費を抑える、という対照的なトレードオフを、ロジスティック方程式という共通の数理モデルの中で対比できることを見てきました。接触機会の予測可能性という1本の軸の上に、CGR・疫学的ルーティング・Spray-and-Waitという3つのアルゴリズムを並べて理解できたことが、この回の核心です。

次回は、こうしたルーティングの発想をさらに一歩進め、宛先を「特定のノードのアドレス」ではなく「欲しいデータの名前そのもの」で指定する**情報指向ネットワーキング(Information-Centric Networking, ICN / NDN: Named Data Networking)**が、宇宙通信にどう応用され得るかを簡単に紹介します。

参考文献

• A. Vahdat, D. Becker, “Epidemic Routing for Partially-Connected Ad Hoc Networks,” Duke University Technical Report CS-2000-06, 2000
• T. Spyropoulos, K. Psounis, C. S. Raghavendra, “Spray and Wait: An Efficient Routing Scheme for Intermittently Connected Mobile Networks,” Proc. ACM SIGCOMM Workshop on Delay-Tolerant Networking (WDTN), 2005
• X. Zhang, G. Neglia, J. Kurose, D. Towsley, “Performance Modeling of Epidemic Routing,” Computer Networks, vol. 51, no. 10, 2007
• P. Juang et al., “Energy-Efficient Computing for Wildlife Tracking: Design Tradeoffs and Early Experiences with ZebraNet,” ASPLOS, 2002
• A. Pentland, R. Fletcher, A. Hasson, “DakNet: Rethinking Connectivity in Developing Nations,” IEEE Computer, vol. 37, no. 1, 2004
• A. Keränen, J. Ott, T. Kärkkäinen, “The ONE Simulator for DTN Protocol Evaluation,” Proc. SIMUTools, 2009
• S. Burleigh, “Contact Graph Routing,” IETF Internet-Draft (draft-burleigh-dtnrg-cgr)
• K. Fall, “A Delay-Tolerant Network Architecture for Challenged Internets,” Proc. ACM SIGCOMM, 2003