システム・運用#47

DSN運用スケジューリング — 有限のアンテナを数十のミッションが取り合う資源配分問題

34m/70mアンテナが世界にせいぜい十数基しかないDSNを、太陽系中を飛ぶ数十のミッションがどう分け合っているのか。パス要求を制約充足問題(CSP)として定式化し、火星探査機の混雑やクリティカルフェーズの優先度衝突を組合せ最適化の視点から読み解く。

前提知識: dsn

DSNスケジューリング組合せ最適化制約充足問題運用資源配分

この回で学ぶこと

前回、DSN(Deep Space Network)がゴールドストーン・マドリード・キャンベラの3局に分散した、34m級・70m級のパラボラアンテナ十数基からなる地球規模のシステムであることを見ました。そこでは主に「1本のアンテナがどれだけの利得 $G$ と感度 $G/T$ を実現できるか」というハードウェアの物理に焦点を当てましたが、実際のDSN運用にはもう1つ、まったく別種の難しさがあります。それはアンテナという物理的資源が有限個しかないのに対して、それを使いたいミッションの数がはるかに多いという問題です。

現在NASAが運用する惑星間ミッションだけでも数十機に及び、これに国際パートナー(ESA、JAXAなど)がクロスサポートを依頼するミッションも加わります。一方でDSNが持つアンテナは3局合計でも十数基しかありません。しかも各アンテナは、地球の自転のために1日のうち特定の時間帯しか特定の探査機を見晴らせず、さらに34mか70mか、S/X/Ka帯のどの周波数に対応しているかといった設備の違いもあります。つまり**「誰が」「いつ」「どのアンテナを」使うかを決める作業そのものが、電波工学というより組合せ最適化の問題**になっているのです。

この回では、視点を信号処理やアンテナ物理から一歩引き上げて、DSNのスケジューリング問題そのものを扱います。各ミッションの追跡要求を制約充足問題(CSP)ないしビンパッキング的な最適化問題として定式化し、なぜこの問題が計算量的に難しいのか、そして実務でどのように競合が生じ、どう優先順位付けされて解決されているのかを、数式とともに見ていきます。

直感的な全体像

まず具体的にイメージしてみましょう。ある1週間、DSNには次のような「パス要求(pass request)」が殺到しているとします。

火星探査機Aは、クリティカルな軌道修正マヌーバの直前直後で、確実にテレメトリを取得したいと高優先度の要求を出している。
火星探査機B、Cもちょうど同じ時間帯に地球方向の可視ウィンドウに入っており、定常運用のダウンリンク(蓄積した観測データの再生)を要求している。
木星圏を航行中の探査機Dは、電力の都合上、特定の34mアンテナでしか受信できない微弱な信号を送っており、長時間の連続追跡を必要としている。
さらに別のミッションEが、まさにこの期間に着陸(EDL: Entry, Descent and Landing)を行う予定で、着陸の数十分間だけは何があっても途切れなく地上局とのリンクを確保しなければならない。

これらの要求はすべて、同じ十数基のアンテナという共有資源を取り合っています。しかも、それぞれの要求には「この時間帯でなければ意味がない」という制約(探査機が地平線の上にいる時間、つまり幾何学的に決まる可視ウィンドウ)があり、「このアンテナでなければ受信できない」という制約(口径・周波数帯の対応)もあります。さらにミッションごとに「絶対に落とせない」ものから「多少ずれても構わない」ものまで優先度に幅があります。

このような、限られた資源(アンテナ×時間)を、時間窓・設備要件・優先度という複数の制約のもとで、多数の要求者に割り当てる問題は、まさに計算機科学でいう制約充足問題(Constraint Satisfaction Problem, CSP)や、資源割当を伴うスケジューリング問題の典型例です。以下ではこれを具体的な数式で定式化していきます。

パス要求の定式化: 誰が・いつ・どのアンテナを

まず登場人物を整理します。

ミッション(探査機)の集合を $M = \{1, \dots, N\}$ とします。
DSNのアンテナの集合を $A = \{1, \dots, K\}$ とします(34m/70m級、3局合計で $K$ はせいぜい十数程度)。
計画対象期間 $[0, T]$ を、実際の長期計画で用いられる粒度(たとえば1時間刻み)で離散化し、時間スロットの集合を $\mathcal{T} = \{1, \dots, T\}$ とします。

各ミッション $m$ は、この期間中にいくつかの**パス要求(pass request)**を発行します。1つの要求 $r$ は次のタプルで表せます。

r = \big(\, m(r),\; [e_r, l_r],\; d_r,\; A_r,\; w_r \,\big)

$m(r) \in M$ : この要求を出したミッション
$[e_r, l_r] \subseteq \mathcal{T}$ : 可視ウィンドウ。探査機が対象局から見て使用可能な仰角(大気減衰や山岳遮蔽を避けられる高度)以上にある時間帯で、これは軌道力学と地球の自転から純粋に幾何学的に決まり、スケジューラの意思では動かせない
$d_r$ : 要求される追跡時間の長さ(たとえば時間単位)
$A_r \subseteq A$ : 適格アンテナ部分集合(サブネット)。この要求を満たせるアンテナの集合で、口径(34m/70m)と周波数帯(S/X/Ka)の対応、さらに局自体が地理的にその時間その探査機を視野に収めているかによって決まる
$w_r > 0$ : この要求の優先度重み

これらすべての要求を集めた集合を $R = \bigcup_{m \in M} R_m$ と書きます。

制約充足問題(CSP)としての定式化

スケジューリングの目標は、各要求 $r$ に対して「どのアンテナの、どの時間スロットを割り当てるか」を決めることです。決定変数を次のように置きます。

x_{r,a,t} \in \{0, 1\}, \qquad x_{r,a,t} = 1 \iff \text{要求 } r \text{ がアンテナ } a \text{ でスロット } t \text{ に追跡される}

この変数に対して、次の制約が課されます。

(a) 可視性・適格性制約。 要求 $r$ を、それに合わない局や時間に割り当てることはできません。

x_{r,a,t} = 0 \quad \text{unless} \quad a \in A_r \ \text{ かつ } \ t \in [e_r, l_r]

(b) アンテナの排他利用制約(ダブルブッキング禁止)。 1本のアンテナは(複数機を同時に受信できるMSPAのような特殊運用を除けば)同時に1つのミッションしか追跡できません。

\sum_{r \in R} x_{r,a,t} \le 1 \qquad \forall a \in A,\ \forall t \in \mathcal{T}

(c) 追跡時間の充足制約。 要求 $r$ が「満たされた」とみなされるかどうかを表す指示変数 $y_r \in \{0,1\}$ を導入すると、

\sum_{a \in A} \sum_{t \in \mathcal{T}} x_{r,a,t} \;\ge\; d_r\, y_r

つまり、必要な追跡時間 $d_r$ 以上が実際に割り当てられて初めて $y_r=1$ とみなせます。

これで、CSPとしての基本形が揃いました。「すべての要求について $y_r=1$ にできる割当 $x$ は存在するか」を問うのが、最も単純なフィージビリティ判定としてのCSPです。しかし実際のDSNでは、要求の総量が資源を上回る(=全要求を同時に満たすことは不可能)のが常態なので、実務上はフィージビリティ判定ではなく、次に述べる最適化問題として扱われます。

優先度付き最適化としての目的関数とNP困難性

全要求を満たせない以上、「どれを優先して満たすか」を決める必要があります。ここで優先度重み $w_r$ を使った目的関数

\max_{x,\,y} \; \sum_{r \in R} w_r\, y_r \qquad \text{s.t. (a), (b), (c),} \quad x_{r,a,t}, y_r \in \{0,1\}

を立てます。これは典型的な**0-1整数計画問題(0-1 Integer Program, IP)**です。この定式化がどれくらい「難しい」問題なのかを、2つの極端なケースで確認してみましょう。

ケース1: アンテナが1本だけ( $K=1$ )で、各要求の割当時間がウィンドウの長さと一致する場合。 これは古典的な**重み付き区間スケジューリング問題(Weighted Interval Scheduling)**そのものです。区間を終了時刻順にソートし、動的計画法(DP)

\mathrm{OPT}(i) = \max\big(\mathrm{OPT}(i-1),\; w_i + \mathrm{OPT}(p(i))\big)

( $p(i)$ は区間 $i$ と重ならない最後の区間のインデックス)を使えば、 $O(n\log n)$ で厳密な最適解が求まります。これは計算量的に「易しい」部類の問題です。

ケース2: アンテナが複数本あり( $K>1$ )、かつ適格集合 $A_r$ がミッションごとに異なる場合。 状況は一変します。この定式化は、時間窓付き・機械適格性制約付きの並列機械スケジューリング問題(unrelated parallel machine scheduling with time windows and eligibility constraints)の一種であり、これはNP困難であることが知られています。直感的に理解するには、ビンパッキング問題との類似で考えるとわかりやすいでしょう。各アンテナの1日あたりの使用可能時間(前回で見た通り、地球の自転のため実用的にはおよそ8〜12時間程度)を「容量」とするビンとみなし、各要求 $r$ を大きさ $d_r$ の「アイテム」とみなすと、DSNスケジューリングは「アイテムを、それぞれ適格なビンの集合 $A_r$ の中で、かつ時間窓 $[e_r,l_r]$ と重なる位置にだけ詰め込む」という時間窓制約付きビンパッキングに相当します。ビンパッキング自体がNP困難な問題であり、DSNスケジューリングはそれに可視性・適格性という追加の制約を重ねた、さらに難しい問題になっています。

この計算量的な困難さが持つ実務的な意味は重要です。ミッション数十、計画期間数週間〜数か月、時間スロットを1時間刻みにしただけでも変数 $x_{r,a,t}$ の総数は容易に数万〜数十万のオーダーに膨れ上がり、厳密な整数計画法(ILPソルバによる完全最適化)を毎回そのまま解くのは現実的な時間で終わらないことがあります。そのためDSNの実運用では、後述するように人間同士の交渉(peer-to-peer negotiation)を主軸としつつ、制約充足に基づく局所探索やヒューリスティックなアルゴリズムで支援する、という現実的なアプローチが取られています。

競合の典型パターン: 火星ミッションの混雑とクリティカルフェーズ

CSPの言葉で定式化すると、実際の運用でどのような競合が起きやすいかも見通しよく説明できます。代表的な2つのパターンを見てみましょう。

パターン1: 複数の火星探査機による混雑

現在、火星の周回・着陸探査を行っているミッションは(NASAだけでなく国際的に見ても)複数存在します。これらの探査機は地球から見るとほぼ同じ方向(火星の方向)に位置しているため、天球上の見かけの位置がほぼ一致します。これはCSPの言葉で言えば、複数の要求 $r_1, r_2, \dots$ について、可視ウィンドウ $[e_{r_1}, l_{r_1}], [e_{r_2}, l_{r_2}], \dots$ がほぼ完全に重なり、しかも適格集合 $A_{r_1}, A_{r_2}, \dots$ もほぼ同じ(同じ局・同じ帯域のアンテナ群)になるということを意味します。制約(b)(アンテナの排他利用)により、これらの要求は互いに強く競合し、同時にすべてを満たすことができません。この「火星探査機が集中する時間帯の混雑」は、DSNスケジューリングにおいて繰り返し発生する典型的なボトルネックとして知られています。

パターン2: クリティカルフェーズと定常運用の衝突

打ち上げ直後、軌道投入、着陸(EDL)、フライバイといったクリティカルフェーズにあるミッションの要求は、他とは性質が異なります。この種の要求は実質的に

d_r \approx l_r - e_r, \qquad w_r \to \text{非常に大きい値(実務上はほぼハード制約)}

として扱われます。つまり可視ウィンドウのほぼ全時間を占有することを要求し、かつその優先度は通常の重み付き最適化の枠を超えて「他の何を犠牲にしても確保する」という、事実上のハード制約として扱われます。これがスケジュールに投入されると、同じ時間・同じ適格アンテナを希望していた低優先度の定常運用要求(たとえば単なる蓄積データのダウンリンク)は、制約(b)により押し出されます。

この押し出された要求がどうなるかは、その要求が持つ代替可能性に依存します。

探査機の搭載レコーダにまだ十分な空き容量があれば、そのミッションのダウンリンクは単に後の可視パスに延期すればよく、実害は小さい。
一方でレコーダの空き容量が逼迫している(次のパスまでに新しい観測データで上書きされてしまうリスクがある)場合、そのミッションの優先度重み $w_r$ は時間とともに実質的に上昇していく、と考えることができます。これは「データ逼迫度」を動的な優先度として組み込む発想であり、実際のDSN運用でもオンボードデータの蓄積状況は優先順位判断の材料になります。
また、その要求の適格集合 $|A_r|$ が大きい(複数のアンテナで代替が利く)ミッションほど、衝突が生じても他のアンテナ・他の局に回避できる余地が大きく、実質的な競合圧力は小さくなります。逆に、極めて遠方にあり信号が微弱で、70mアンテナ(あるいは複数34mのアレイ合成)でなければ受信できないミッションは $|A_r|$ が小さく、慢性的に競合の的になりやすい資源です。

実務での使われ方

JPLのDSNスケジューリングは、この節で述べた最適化問題を、段階的な時間スケールでの人間参加型プロセスとして運用しています。

ロングレンジプランニング(数か月〜1年以上先)。 各ミッションは打ち上げ前から、将来必要になるであろうアンテナ時間(アパーチャ・アワー)の見込みをDSNに申告します。この段階では個々の時間スロットまで確定させるのではなく、DSN全体の需要が供給(アンテナの総稼働可能時間)を超過していないか、将来的にどのミッションの組み合わせが特に混雑を招きそうかといった、マクロな資源計画(キャパシティプランニング)が行われます。ここで見えてくる「この時期は複数の火星ミッションが集中しそうだ」といった予測が、後段の詳細スケジューリングへの重要な入力になります。

中期スケジューリング(数週間先の確定作業)。 実行日の数週間前になると、各ミッションのスケジューリング担当者(ミッション側の「スケジューリングエンジニア」)が、共有されたドラフトスケジュールをもとにピア・ツー・ピアで交渉し、競合を解消していきます。これは中央集権的なアルゴリズムが一方的に割り当てを決めるのではなく、この節で定式化したCSPの制約充足を支援するツール(コンフリクトを自動検出し候補割当を提示する制約ベースのスケジューリング支援システム)を使いながら、最終的には人間同士の合意で確定させるという、計算機支援と交渉のハイブリッドなプロセスです。ここで固まったスケジュールが「ベースライン」として実行に移されます。

直前のコンフリクト解消(数日〜当日)。 ベースラインが確定した後でも、探査機の異常(セーフモードへの移行など、予定外の高優先度パスが突発的に必要になる)、DSN側の設備トラブルや保守作業、あるいは他ミッションのクリティカルフェーズの前倒し・延期などにより、直前になってスケジュールの再調整が必要になることが常に起こります。この段階では最適化よりも、限られた時間の中で「今ある制約下で実行可能な代替案を素早く見つける」という、CSPのフィージビリティ回復に近い作業が行われます。

MSPA(Multiple Spacecraft Per Antenna)による緩和。 制約(b)の「1アンテナ1ミッション」という制約そのものを部分的に緩和する運用技術として、MSPAがあります。複数の探査機がアンテナのビーム幅に収まるほど天球上で近接しており(たとえば火星を周回する複数の探査機どうし)、かつダウンリンク周波数が互いに分離されていれば、1本の受信アンテナで複数機のテレメトリを同時に受信できます(アップリンクによるコマンド送信は原則として1機ずつです)。これは前節で述べた「火星ミッションの混雑」パターンに対する実務上の緩和策の1つであり、CSPの言葉で言えば制約(b)を「同時に受信できるダウンリンクは複数までOK」という、より緩い制約に置き換えることに相当します。

演習問題

あるアンテナ1本について、次の3つのパス要求が候補に挙がっているとする(時間は共通の1つのアンテナのタイムライン上での開始・終了スロット、重みは優先度)。

要求開始終了重み $w_r$
$r_1$ 0 4 5
$r_2$ 3 7 6
$r_3$ 5 9 4

これらは互いに時間が重なるため、同じアンテナでは同時に2つ以上を満たせない。重み付き区間スケジューリングのDPを使って、重みの合計を最大化する要求の組み合わせを求めよ。
あるDSN局が1日に実用的に追跡できる時間を10時間、局全体でアンテナが4本あるとする。この局に対して、ある週(7日間)にわたって、それぞれ平均6時間の追跡を要求するミッションが12機ある(要求の合計時間 = $12 \times 6 = 72$ 時間/週)とき、この局が供給できる総アンテナ時間(時間/週)と比較し、需要が供給を上回るか(過負荷かどうか)を判定せよ。また、もし過負荷であれば、この状況を緩和する実務的な手段を、本文中で触れた選択肢から2つ挙げて説明せよ。
あるミッションのクリティカルフェーズ要求(着陸)が、可視ウィンドウ $[e_r, l_r]$ のほぼ全域( $d_r \approx l_r - e_r$ )を占有し、かつ他の3つの定常運用要求(同じアンテナ・同じ時間帯を希望)を押し出すとする。この3つの要求がそれぞれ異なる $|A_r|$ (代替可能なアンテナ数)を持つ場合、どの要求から先に「別の局・別の時間帯」への再割当を検討すべきか、本文の議論に基づいて優先順位とその理由を述べよ。
なぜ「複数の火星探査機による混雑」は、木星や土星など火星以外の探査機を含めたスケジュール全体の中でも、特に繰り返し起こりやすい構造的な問題なのか。可視ウィンドウ $[e_r, l_r]$ と適格集合 $A_r$ の重なりという、この回で導入したCSPの言葉を使って説明せよ。

要求	開始	終了	重み $w_r$
$r_1$	0	4	5
$r_2$	3	7	6
$r_3$	5	9	4

まとめと次回予告

この回では、DSNを「アンテナという有限の物理資源を、数十のミッションが取り合う組合せ最適化問題」として捉え直しました。各ミッションのパス要求を可視ウィンドウ・適格アンテナ集合・優先度重みのタプルとして定式化し、割当変数 $x_{r,a,t}$ に対する可視性・排他利用・時間充足の制約を課すCSP/0-1整数計画として書き下しました。アンテナが1本だけの単純なケースは古典的な重み付き区間スケジューリングとしてDPで効率よく解ける一方、複数アンテナ・複数の適格性制約が絡む現実のDSNスケジューリングは、時間窓付きビンパッキングに相当するNP困難な問題であることも見ました。実務では、この困難さに対してロングレンジプランニング・中期の交渉ベースのスケジューリング・直前のコンフリクト解消という段階的なプロセスと、MSPAのような制約緩和の運用技術を組み合わせて対応していることを確認しました。

次回は、これまでほとんど触れてこなかったKa帯の運用上の難しさに軽く触れます。Ka帯はXバンドよりもさらに高い周波数を使うことで帯域幅とデータレートを稼げる一方、地球大気(特に降雨)による減衰の影響を強く受けます。この「Ka帯の降雨減衰」が、リンクバジェットの設計や、ひいては今回見たようなスケジューリング(悪天候時に代替アンテナへ切り替える判断など)にどう関わってくるのかを見ていきます。

参考文献

M. D. Johnston, “Multi-Objective Scheduling for NASA’s Deep Space Network Array,” International Workshop on Planning and Scheduling for Space (IWPSS)
DSN Telecommunications Link Design Handbook, DSN No. 810-005
J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76
M. Pinedo, Scheduling: Theory, Algorithms, and Systems, Springer
NASA/JPL, Deep Space Network 公式解説資料(局構成・複数ミッション運用に関する記述)