Long-Horizon Wireless Link Scheduling with State-Augmented Graph Neural Networks

技術要約：状態拡張グラフニューラルネットワークを用いた長期間無線リンクスケジューリング

問題定式化
本論文は、大規模なデバイス間（D2D）無線ネットワークにおける最適なリンクスケジューリングの問題を扱う。目的は、時間ホライゾン $T$ にわたる長期的な平均総レートを最大化しつつ、すべてのリンク $i$ が最小平均レート要件 $\Delta_i$ を達成するようにすることである。瞬時の総レートの最大化に焦点を当てる従来のプローチとは異なり、この問題は、時間的な制約を満たし、かつ干渉を回避するために、時変（time-varying）なポリシーを必要とする。

ネットワークは、2つのリンクが共通のデバイスを共有する場合に干渉すると定義される主要な干渉モデルの下でモデル化されており、これは隣接行列 $A$ を持つ衝突グラフ $G(V, E)$ として表現される。スケジューリング問題は、各タイムスロット $t$ における決定変数 $s(t) \in \{0, 1\}^K$ を持つ、制約付き組合せ最適化問題（式3）として定式化される。全探索空間は、リンク数 $K$ と時間ホライゾン $T$ の積に対して組合せ爆発的に増加するため、大規模ネットワークにおいて厳密解を求めることは計算量的に困難である。

手法
著者らは、ラグランジュ双対性と状態拡張に基づいた学習ベースのアプローチを提案している。その手法は、以下の3つの理論的および実践的なステップで進行する。

1. 双対領域解析と原始問題の実行不能性：
   著者らは、まずラグランジュ双対を用いて問題を分析する。彼らは、固定された双対変数 $\lambda$ に対して、ラグランジュ最大化因子は時間不変であることを証明している（命題1）。すなわち、最適なスケジュール $s^\dagger(t, \lambda)$ は時間によって変化しない。したがって、単一の最適な双対変数 $\lambda^\star$ から導出された静的なポリシーでは、干渉を避けるために送信を交互に行うことができないため、すべてのリンクの最小レート要件を同時に満たすことはできない。これにより、単一の最適な $\lambda^\star$ とそれに対応する静的なスケジュールを見つけるという標準的な原始・双対アプローチは、長期間のホライゾン問題に対して不十分であることが示される。

2. 双対勾配降下ダイナミクス：
   この時間不変性の限界を克服するために、本論文では双対勾配降下ダイナミクスを調査する。アルゴリズムは、制約違反（劣勾配）に基づいて双対変数 $\lambda(u)$ を反復的に更新し、各ステップで対応するラグランジュ最大化因子 $s^\ddagger(u)$ を計算することで、一連のスケジュールを生成する。理論的分析（命後3）によれば、この一連のスケジュールに含まれる個々のスケジュールは最適ではない可能性があるものの、そのシーケンス $s^\ddagger(1:T)$ の平均レートは、$T \to \infty$ において漸近的に最適かつ実行可能である。これは、長期間のホライゾンの問題の解が、双対勾配降下の軌跡を模倣するポリシーを学習することにあることを示唆している。

3. 状態拡張グラフニューラルネットワーク (SAGNN)：
   各ステップでNP困難なラグランジュ最大化を解くことなくこれを効率的に実装するために、著者らはグラフニューラルネットワーク（GNN）を用いたパラメータ化されたポリシー $\Phi(A, \lambda; H)$ を提案している。

• 状態拡張： 本手法の鍵となる革新は、ネットワークトポロジー $A$ と並んで、双対変数 $\lambda(t)$ をGNNの内部状態（または入力信号）として扱うことである。これにより、現在の制約違反のレベルに基づいて、ポリシーがスケジューリング決定を動的に適応させることが可能になる。
• 学習（オフライン）： GNNのパラメータ $H$ は、様々なネットワークトポロジーと双対変数の分布に対して、瞬時ラグランジュ関数 $M(s, \lambda)$ を最大化するようにオフラインで訓練される。損失関数は、サンプリングされた $\lambda$ によって重み付けされた制約違反に対してペナルティを課す。
• 実行（オンライン）： 実行時、訓練されたGNNは、現在のネットワーク状態 $A$ と現在の双対変数 $\lambda(t)$ に基づいてスケジュール $s(t)$ を生成する。その後、双対変数は制約違反の劣勾配（式21）を用いてオンラインで更新され、双対勾配降下ダイナミクスを模倣するクローズドループシステムが構築される。

主な貢献

• 理論的洞察： 本論文は、ラグランジュ最大化因子は時間不変であり、したがって制約付きの長期間ホライゾン問題に対して実行不能であるが、双対勾配降下によって生成される最大化因子の「シーケンス」が漸近的に最適な平均レートをもたらすことを確立した。
• アルゴリズム設計： 著者らは、ラグランジュ最大化因子を近似することを学習する状態拡張GNN（SAGNN）を導入した。双対変数を動的な入力として組み込むことで、ポリシーは時間の経過とともにスケジューリング決定を変化させ、制約充足と性能最大化を効果的にバランスさせることを学習する。
• スケーラビリティ： 提案手法は、学習パラメータ化から時間ホライゾン $T$ の複雑さを切り離している。GNNは単一のタイムステップに対するマッピングを学習するため、長さ $T$ のシーケンスを直接学習する必要がなく、計算コストを抑えることができる。

結果
約500のリンクを持つランダム幾何グラフ（RGG）を用いて、広範な数値シミュレーションが行われた。

• 制約充足： 提案アルゴリズムは、大多数のリンクに対して最小レート制約を正常に満たしている。スケジューリングが不足している少数のリンクについても、制約違反は軽微である。
• 性能： 本手法は、平均総レートにおいていくつかのベースライン・ヒューリスティックを上回り、より高速な実行時間を達成している。
• 汎用性： 学習されたポリシーは、異なる伝送要件に対して汎用性を示し、効果的に適応する堅牢性を備えている。ポリシーは、双対変数が進化するにつれて、制約違反レベルが高いリンクを優先しながら、非干渉リンク間をうまく交互に切り替えることに成功している。

意義と主張
本論文の主な意義は、双対勾配降下の理論的な最適性と、効率的な学習ベースのスケジューリング・ポリシーへの実用的なニーズとの間の溝を埋めることにある。著者らは、状態拡張が、標準的な時間不変ポリシーや（計算コストが高すぎる）直接的なシーケンス学習では効果的に解決できない、長期間の制約に必要な時変ポリシーをGNNに学習させるための不可欠な技術であると主張している。本研究は、双対ダイナミクスを模倣するように学習することが、無線ネットワークにおける高次元の制約付き組合せ問題に対し、計算効率の高い方法で解を導くことを検証している。