技術要約: CFCO – 車載エッジコンピューティングにおけるタスク・オフローディングのための社会的福祉最大化型協調的提携形成手法

1. 問題提起

車載エッジコンピューティング（VEC）は、データソースの近くにリソースを提供することで、遅延に敏感で計算集約的なアプリケーション（自動運転、協調型知覚など）をサポートすることを目指している。しかし、既存のアプローチには以下のような重大な制限がある：

• ローカル計算: オンボードCPUの周波数、エネルギー予算、および熱制限によって制約を受ける。
• MECオフローディング: 不安定な車載インフラ間（V2I）リンク、道路の遮蔽、ハンドオーバーの失敗、および複数の車両が同時にオフロードを行う際の計算コアや帯域幅のリソース競合に悩まされる。
• D2D協調: 隣接する車両のアイドルリソースを活用する有望な手法であるが、提携形成、ヘッド（代表者）の選択、および安定性に課題がある。

既存の文献では、これらのモードを個別に扱うか、解釈性に欠ける複雑な学習（深層強化学習など）に依存することが多い。したがって、異種混合の車両タスク全体に対して、早期完了による利益、エネルギーコスト、および遅延ペナルティのバランスをとる指標である「社会的福祉（Social Welfare）」を最大化するように、ローカル計算、デバイス間（D2D）協調、およびMECオフローディングを統合的に最適化する解釈可能なフレームワークが必要とされている。

2. 手法: CFCOアルゴリズム

本論文では、反復的な提携構造の最適化を通じて社会的福祉を最大化するように設計されたヒューリスティックアルゴリズムであるCFCO（Collaborative Coalition Formation for Offloading）を提案する。

2.1 システムモデル

• ネットワークトポロジー: NGSIMデータセットからの実世界の軌跡を用いた、一次元の道路トポロジー。
• タスクモデル: 各車両 $i$ は、入力サイズ ($L_i$)、計算密度 ($\rho_i$)、デッドライン ($\tau^{\max}_i$)、遅延利益重み ($w_i$)、および遅延ペナルティ係数 ($\lambda_i$) によって定義されるタスクを持つ。デッドラインは車両の速度に連動しており、高速で移動する車両ほど感度が高くなることを反映している。
• 実行モード:
  1. ローカル計算: 車両自身のCPU上での実行。
  2. MECオフローディング: 帯域幅の共有と有限のコア混雑の影響を受ける、V2Iリンクを介したロードサイドユニット（RSU）へのオフロード。
  3. D2D協調: 非MEC車両による提携形成。最も高いCPU周波数を持つ車両が**提携ヘッド（Coalition Head）**として機能する。ヘッドは並列またはバッチモードでタスクを処理し、実行遅延は提携内の最大ワークロードによって決定され、ヘッドのエネルギーコストは総ワークロードの累積によって決定される。

2.2 最適化目的

目標は、個々の純福祉（$W$）の総和を最大化することである：
$$W = \sum_{i \in V} \left( w_i \max(0, \tau^{\max}_i - T_i) - E_i - \lambda_i T_i \right)$$
ここで、$T_i$ はタスク遅延、$E_i$ はエネルギー消費量である。この問題は、集合分割、離散的なモード選択、およびリンクの実現可能性制約を含む。

2.3 アルゴリズム設計

CFCOは、有限の状態空間における単調改善アルゴリズムとして動作する：

1. 初期化: 車両を単一要素（Singleton）として初期化する。保守的なチェックにより、すべての車両がオフロードを試みると仮定した混雑したMECシナリオと比較することで、初期のMECユーザーを決定する。
2. 結合（Merge）と分割（Split）:
   • 結合: 社会的福祉の利得が厳密に正である場合に、非MECの提携ペアを反復的に結合する。
   • 分割: 提携内の個々のローカル福祉の合計が提携の福祉を上回る場合、マルチメンバーの提携を単一要素へと分割する。
   • モード精査: 社会的福祉の総和を厳密に増加させる場合に、車両をMECと非MECの間（またはローカルとD2Dの間）で切り替える。
3. ローカル探索: ローカルな最適解から脱出するために、決定論的なローカル移動（MECの切り替え、または提携間の車両の移動）を実行する。
4. 終了: さらなる厳密な改善が見られなくなるか、最大反復回数に達したときに終了する。

3. 主な貢献

1. 統合モデル: ローカル、D2D、およびMECモードを統合した一貫した実装モデル。CPU周波数に基づくD2D提携ヘッドと、帯域幅共有およびコア制限を介したMECの混雑を明示的にモデル化している。
2. 社会的福祉駆動型ヒューリスティック: 遅延やエネルギーのみを最適化する手法とは異なり、CFCOは複合的な福祉関数を共同で最適化する。これは、有限の状態空間において、事前の学習を必要とせずに単調な改善と収束を保証する。
3. トレース駆動型評価: 本研究では、合成的なトポロジーを超えて、現実的な空間クラスタリングと速度依存のデッドラインをマッピングするために、実世界のNGSIM車両軌跡（位置、速度、クラス）を利用している。
4. 統計的厳密性: 10個の独立したランダムシードによる平均値、95%信頼区間、ウィルコクソンの符号付順位検定、および整数線形計画法（ILP）解に対する小規模な厳密な最適性ギャップ研究を併用している。

4. 実験結果

実験は、$N=60$ 台の車両と V2I 可用確率 0.7 の条件下で行われた。CFCOを、MECのみ、Singleton（ローカルのみ）、Random、Greedy戦略、Matching、Simulated Annealing (SA)、およびBest-Response Local Search (BR-LS) を含む8つのベースラインと比較した。

4.1 パフォーマンス指標（平均値）

• 社会的福祉: CFCOは 481.28 を達成し、2番目に優れたベースライン（BR-LS: 480.24）を 0.2%、MECのみを 71.0% 上回った。
• 平均遅延: CFCOは 0.225 s を達成し、BR-LSと比較して 1.9%、MECのみと比較して 50.4% の削減を実現した。
• タスク成功率: 0.998 となり、ほぼ完璧であった。
• Jain公平性指数: 0.716 であり、車両間の福祉のバランスの取れた分布を示した。
• 実行モード分布: CFCOは、車両の 20.5% をローカル計算に、22.5% をMECに、57.0% をD2D提携に割り当てた。

4.2 効率性と最適性

• 実行時間: CFCOは 9.17秒 で収束し、これは同等の解の質を実現しながら、BR-LSベースライン（110.85秒）よりも 12倍高速 である。
• 最適性ギャップ: 正確なILPソルバーを用いた小規模な研究（$N=12$）において、CFCOは平均 0.03% のみという極めて低い最適性ギャップを示した。
• 統計的有意性: ペア・ウィルコクソン検定により、社会的福祉および平均遅延におけるCFCOの全ベースライン（BR-LSを含む）に対する改善が、統計的に有意（$p < 0.05$）であることが確認された。

4.3 パラメータ感度

CFCOは、以下の変動に対しても優れた性能を維持した：

• ローカルCPU周波数。
• D2D帯域幅（テストされたトポロジーにおいて、1 MHzを超えると収穫逓減を示す）。
• MEC容量。
• 車両密度。
• V2I信頼性（V2I信頼性が低下すると、CFCOは動的にローカルまたはD2Dモードに切り替わるが、MECのみの手法は、より多くの車両が同時にオフロードを試みることで混雑が発生し、性能が著しく低下する）。

5. 意義と主張

本論文は、CFCOがVECにおけるタスク・オフローディングのための実用的、解釈可能、かつ効率的なソリューションを提供すると主張している。その意義は以下の通りである：

• トレードオフの調整: 送信エネルギー、計算遅延、およびタスクデッドラインの間のトレードオフを巧みに制御し、単一目的最適化の落とし穴を回避している。
• リアリズム: NGSIMトレースを活用することで、評価は現実的な空間クラスタリングと車両ダイナミクスを反映しており、合成シミュレーションよりも信頼性の高い洞察を提供している。
• スケーラビリティ: アルゴリズムは、網羅的なローカル探索手法よりも大幅に低い計算オーバーヘッドで、ほぼ最適に近い結果を達成しており、動的な車両環境におけるオンライン意思決定に適している。

著者らは、静的なスナップショットの使用、D2Dヘッドにおける並列処理の抽象化、およびインセンティブ互換性のある支払いメカニズムの欠如といった限界も認めている。今後の課題として、連続的なモビリティ、逐次処理モデル、およびマルチRSU協調への対応が提案されている。