2024/3/6

研究背景• 通信のユースケースの多様化

品質多様性アルゴリズムを用いた
5Gネットワークにおける動的ネットワークスライシング制御手法の提案: Application• サービスによって要件が大きく異なる• URLLC: 高信頼低遅延• eMBB: 高速大容量• mMTC:多数同時接続• ネットワークスライシング技術

大月 天渡: User Equipment

eMBB• 共有基盤資源を仮想的に分割• 要件に応じた柔軟な NW の構築

大阪大学 大学院情報科学研究科
情報ネットワーク学専攻 村田研究室

mMTC

E2E Network Slices

Substrate Network

URLLC

博士前期課程2年• 資源割り当て問題• 多様な要件のスライスを同時にホスト
図. ネットワークスライシングの概念図
2

1

12

先行研究の課題

研究目的と方針• 複数スライスの協調的な制御手法の実現• Network Slice Embedding (NSE) 問題• UE・アプリケーション間 E2E 通信• 組み合わせ最適化問題• NP困難• ヒューリスティクスの提案• 複数スライスの並列制御

𝑂 (𝑉2𝑁• 他のスライスの要件を考慮• 種々の環境変動に適応)

コントローラ• 新規スライス要求の到着• 他のコントローラによる割当の変更

𝑂( 𝑉 2 )Selection• 遺伝的アルゴリズム (GA)𝑁

• 生物進化モデルによる環境変動への適応• 目標関数の設計自由度を活用• 従来の GA では解の多様性が低下• スライス要求の数で組み合わせ爆発• 個別での制御が必要• 個別制御による全体最適化

Previous solutions

Crossover
Mutation
Next solutions• 品質多様性 (QD) アルゴリズム• 多様かつ優れた解を出力可能な GA• MAP-Elites アルゴリズムに注目

図. NSE問題空間のオーダー• 多様なスライス要件の考慮

図. 遺伝的アルゴリズム
33

4

4

MAP-Elites アルゴリズム

NSE 問題の定式化• 特徴空間上での多様な解の探索• アルゴリズム
1.
2.
3.
4.
5.
6.

無作為に初期集団を生成
個体を無作為に選択
個体を変異させ新しい個体を生成
新しい個体の評価値と特徴量を評価
対応するセルの既存解との競争
2～5を繰り返す• 基盤ネットワーク

Feature 2

4.

• 𝐺𝑆 = 𝑉𝑈 , 𝑉𝐶 , 𝐸𝑆
• UEノード, クラウドノード (CN), 物理リンク

Feature 1• ユーザー定義の特徴量で探索空間を設計• 特徴空間はある粒度のセルで分割• 各セルで最良の解を出力するように動作• CNと物理リンクは有限な資源を持つ• CPU, メモリ, スループット, レイテンシ

2.

• ネットワークスライス

5.

: 𝑀𝑁

∈ 𝑉𝐶: 𝑀𝐿

∈ 𝑉𝑈
∈ 𝑉𝑈′
∈ 𝑃𝑆

• 𝐺𝑅 = 𝑉𝑈′ , 𝑉𝐴 , 𝐸𝑅
• 一部のUE, アプリケーション (App), 仮想リンク

0100101010010101• Appと仮想リンクは資源要求量を持つ

3.

• 基盤資源を消費して要求を満たす• 2つの写像を決定

0100101011010101• 𝑀𝑁 : 𝑉𝐴 → 𝑉𝐶 , 𝑀𝐿 : 𝐸𝑅 → 𝑃𝑆 (𝑃𝑆 : 物理パス)

図. MAP-Elites の動作
55

∈ 𝑉𝐴

図. NSE問題のモデル

661

2024/3/6

解の符号化

適応度の定義• 解の遺伝型への符号化が必要• 𝐹 𝑔 = 𝑅 𝑔 − 𝜆𝑃 𝑔 + 𝜀𝐵 𝑔 − 𝑓𝑎 ⋅ 𝛿𝐷(𝑔)• 基盤 NW と スライスの対応を直接符号化• 𝑅 𝑔 : 総残余資源量

𝑎𝑖• 資源の効率的な利用• 探索空間の限定𝑐𝑚• 有限長の遺伝型での符号化• 𝐾 番目までに短い経路から選択

𝑐𝑛𝑐𝑗• 資源要求に対する残余資源の総不足量• スライスの資源要求の満足

𝑝1𝑛,𝑚𝑔1• 𝐵 𝑔 : 利用資源の残余資源量• スライスに割り当てた基盤要素の残余資源の総和• 協調動作１（負荷分散）: 資源の断片化の抑制• 符号化方法• 𝑀𝑁 𝑎𝑖 = 𝑐𝑗 ⇒ 𝑔𝑖 = 𝑗𝑘
• 𝑀𝐿 𝑙𝑑 = 𝑝𝑛,𝑚
⇒ 𝑔𝑑+|𝑉𝐴| = 𝑘(𝑙𝑑 = 𝑖, 𝑗 , 𝑛 = 𝑀𝑁 𝑖 , 𝑚 = 𝑀𝑁 (𝑗))𝐷 𝑔 𝑜𝑝𝑡• 𝑃 𝑔 : 資源要求違反ペナルティ𝑙𝑑• 𝐷 𝑔 : 利用資源の総需要(𝑔0 , … , 𝑔𝑖−1 , 𝑗, … , 𝑔 𝑉𝐴 , … , 𝑔𝑑−1+ 𝑉𝐴 , 1, … , 𝑔 𝑉𝐴 +|𝐸𝑅 | )𝑀𝑁• 需要：未割当スライスの最適解による要求量

𝑀𝐿𝑔 𝑜𝑝𝑡𝑔2
𝐷

図. 需要による解の変更• 最も受容可能性の高い解が要求する資源• 協調動作２（譲歩）: 他のスライスを優先した解への変更

図. 解の符号化

7788

特徴空間の設計

シミュレーション設定• 効率的な解探索のために重要• 比較評価のため３つのアルゴリズムを評価• 多様な実行可能解が広範に存在する空間• 環境によって最適な値が異なる特徴量• MAP-Elites, GA, NodeRank• 適応度の項の有無でも比較• 協調動作の有効性の検証
特徴量 2• 特徴量 1: 割当ノードの総資源量• ノードの種類によって資源量が大きく異なる• ノード選択の多様化につながる• 特徴量 2: 割当経路の総レイテンシ• 任意の経路選択を区別し多様化• 負荷分散や高需要資源の利用回避につながる• 3タイプのスライス要求• URLLC, mMTC, eMBB

特徴量 1

• 特徴空間の定義• 2つのシナリオでシミュレーション𝑡• 動的シナリオ• ポアソン過程でモデル化• 平均 40 個のスライスを並列制御

図. 特徴空間図. 経時的なスライス要求の到着とコントローラの割当• 静的シナリオ• 10×10 のセルに分割• 100個のスライスを一斉制御
991010

動的シナリオでの評価結果

動的シナリオでの評価結果• スライス受容率の比較• 平均収益の比較• 提案手法群が比較手法より高い• 収益: スライスの総要求資源量• 手法 ME-C・ME-GW が高い• より多くのスライスを受容• 協調的な動作による全体最適化が実現

NR: 51.3%

NR: 2102.7• 譲歩行動が収益性の向上に寄与• 提案手法間の需要率は同程度• 受容率は同程度• 収益の大きいスライスの優先的な受容

表. 手法名の表記法

アルゴリズムMEMAP-Elites

GA

従来型遺伝的アルゴリズム

NR

NodeRank(既存手法)

表. 手法名の表記法

アルゴリズム𝜺𝜹-C10−5102

ME

MAP-Elites

GA

従来型遺伝的アルゴリズム

NR

NodeRank(既存手法)-LB

10−50-GW0102-I00

𝐹 𝑔 = 𝑅 𝑔 − 𝜆𝑃 𝑔 + 𝜀𝐵 𝑔 − 𝑓𝑎 ⋅ 𝛿𝐷(𝑔)提案手法

図. スライス受容率の比較

𝜹10−5102-LB

10−50-GW0102-I00𝐹 𝑔 = 𝑅 𝑔 − 𝜆𝑃 𝑔 + 𝜀𝐵 𝑔 − 𝑓𝑎 ⋅ 𝛿𝐷(𝑔)1111𝜺-C提案手法

図. 長期的平均収益の比較
12122

2024/3/6

静的シナリオでの評価結果

まとめと今後の課題• 提案手法間での受容率推移の比較• NSE問題の全体最適化手法の提案• ME-C, ME-LB の増加が急峻• 個別最適化に協調的な動作を組み込み実現• 高需要資源利用の回避が他の受容を促進• 効率的な実行可能解の発見• 比較評価により協調的な動作の効果を検証• 平均受容率・収益の向上を確認• 最終的な受容率はME-LBが最大• 提案手法ごとの性質の違いを評価• 資源の断片化の抑制効果• 譲歩行動：スライスの迅速な受容・収益性の高いスライスの優先的な受容• 負荷分散：最終的なスライス需要個数の増加

表. 手法名の表記法

アルゴリズム𝜺𝜹ME

MAP-Elites-C10−5102GA

従来型遺伝的アルゴリズム-LB

10−50-GW0102-I00NR

NodeRank(既存手法)

𝐹 𝑔 = 𝑅 𝑔 − 𝜆𝑃 𝑔 + 𝜀𝐵 𝑔 − 𝑓𝑎 ⋅ 𝛿𝐷(𝑔)• 今後の課題• 行列演算での定式化による実行時間の削減• 大規模シミュレーションでの統計的な解析による性質の評価• 適応度内のパラメータ変更による影響の調査

図. 受容スライス数の推移
131314143