社団法人 電子情報通信学会
THE INSTITUTE OF ELECTRONICS,
INFORMATION AND COMMUNICATION ENGINEERS

信学技報
TECHNICAL REPORT OF IEICE.

品質多様性アルゴリズムを用いた 5G ネットワークにおける動的ネットワークスライシング制御手法の提案
大月

天渡†

小南

大智†

大歳

達也††

下西

英之††† 村田正幸†

† 大阪大学 大学院情報科学研究科 〒565–0879 大阪府吹田市山田丘 1–5†† 大阪大学 大学院経済学研究科 〒560–0043 大阪府豊中市待兼山 1–7††† 大阪大学 サイバーメディアセンター 〒560–0043 大阪府豊中市待兼山町 1–32
E-mail: †{a-otsuki,d-kominami,murata}@ist.osaka-u.ac.jp, ††t-otoshi@econ.osaka-u.ac.jp,†††shimonishi.cmc@osaka-u.ac.jp
あらまし 5G ネットワークにおいて多様な要件を持つ種々のアプリケーションを同時にホストする上で、複数の独立した専用の仮想ネットワークを提供するネットワークスライシング技術は重要な要素である。ネットワークスライス
に対する基盤資源の割り当てを最適化する問題は NSE 問題として定式化されており、NP 困難であるため既存研究ではヒューリスティクスが提案されている。現実的なシナリオでは複数の要件の異なるネットワークスライスを並列的に埋め込む必要があり、相互に要件を考慮しなければ全体最適は実現できない。一方で、統一的に制御する場合にはスライスの数に対して問題空間が指数的に増大するため、個別の制御が不可欠である。このため、個別に制御を行いながら全体最適化を図る必要がある。本稿では、生物進化モデルを応用した品質多様性アルゴリズムを用いて、ネットワークスライスを個別制御しながら協調的な動作によって全体最適化を実現する手法を提案する。また、計算機シ
ミュレーションを通して既存手法との比較評価を行い、提案手法の有効性およびその性質を明らかにした。
キーワード ネットワークスライシング、NSE (Network Slice Embedding)、品質多様性アルゴリズム

1. は じ め に
近年の 5G ネットワークのユースケースの多様化に伴い、ネットワークに対するサービス要件も多様化している。具体的には、自動運転や遠隔医療ロボットなどの高信頼かつ低遅延が求められる URLLC (Ultra-reliable and Low Latency Communications)、動画ストリーミングなどの高データレートが求められる eMBB (enhanced Mobile Broadband)、センサネット
ワークや IoT などの大規模ネットワークの同時通信が必要な
mMTC (Massive Machine Type Communications) といった
ユースケースが存在する [1]。それぞれの要件の衝突によるサー
ビス品質の低下を防ぐため、共有の基盤ネットワーク上の物理資源を仮想的に分割し、複数の仮想ネットワークを基盤ネット
ワーク上に構築するネットワークスライシング技術は最も重要な要素技術のひとつである。
複数のクライアントから様々な要件のネットワークスライスが要求される中で、ネットワークプロバイダは有限な物理資源上にそれらのスライスを配置することが求められる。より多くのスライスを限られた物理資源上に効率的に配置することはク
ライアント、プロバイダの双方にとって重要である。一方で、全体最適化を行うために全てのスライスを同時に最適化することは問題規模の増大化につながり、現実的な時間での求解が困難となる。そのため、スライスを個別に制御する中で、相互に連携し全体のスライス要求受容率を高めることが求められる。
5G ネットワークにおけるネットワークスライシングの制御を最適化問題として捉えるとき、様々なアルゴリズムの側面を持つが、そのうちの一つに資源割り当て問題としての側面がある [2]。文献 [3] ではネットワークスライスの最適化を Virtual
Network Embedding (VNE) 問題として定義しているが、制御の対象が基地局からコアクラウドまでとなっており、UE を含めた E2E 通信となっていない。また、文献 [4] では 5G ネット
ワーク上の E2E 通信を前提としてネットワークスライスの資図 1 5G ネットワークにおける E2E ネットワークスライシング

源割り当て制御の実装を行っているが、スライスの埋め込みは制御の対象となっておらず、また資源割り当てのアルゴリズム
は最適化を前提としていない。文献 [5] は UE を含めた E2E 通信を対象とするネットワークスライスの埋め込みの最適化を、
VNE 問題を拡張した NSE 問題として定義している。
NSE 問題において基盤ネットワークとネットワークスライ
スはそれぞれ無向グラフとしてモデル化され、基盤ネットワー
クを構成するノードは UE とクラウドノード、ネットワークス
ライスを構成するノードは UE とアプリケーションに分類される。クラウドノードとリンクは有限の資源を持ち、これを消費してアプリケーションおよび UE・アプリケーション間の通信をホストする。NSE 問題はこの資源制約下において、複数のネットワークスライスの要求に対してどの要求を受容するか、またそのスライスへの資源割り当てを決定する問題である。また、文献 [6] ではアプリケーション間の接続を含めた NSE 問題
を定式化しており、本論文での NSE 問題は主にこの文献での記述に準ずる。ただし、この文献で新たに定義されている可用性や信頼性の項目は除外する。
文献 [5] では VNE 問題におけるヒューリスティクスである
NodeRank 法 [7] を拡張した手法を提案しており、既存の整数—1—

Algorithm 1 Pseudocode of MAP-Elites [8]procedure MAP-Elites
F ← ∅, X ← ∅for iter ← 1, I do
if iter < G thenx′ ← random solution()elsex ← random selection(X )x′ ← random variation(x)b′ ← f eature descriptor(x′ )f ′ ← f itness(x′ )if F (b′ ) = null or F (b′ ) < f ′ thenF (b′ ) ← f ′X (b′ ) ← x′
return f eature-f itness map (F and X )線形計画法による手法と比較して同程度のスライス要求受容率
でありながら、計算時間に関して高いスケーラビリティを示している。一方で、この文献ではスライスの要件にレイテンシを含めているにもかかわらず、提案手法ではレイテンシを考慮していない。また、複数のネットワークスライスを並列的に埋め込むことを想定しているが、経時的に変化するネットワーク資源状況や他のスライスの情報をランキングに組み込んでおらず、全体最適化を考慮しないものとなっている。
本研究はスケーラビリティを確保するためネットワークスラ
イスを個別に制御しながら、全体最適化を図る最適化手法の実現を目的とする。提案手法では品質多様性アルゴリズム、特にその一つである MAP-Elites の適応度（目標関数）の設計の自
由度、および探索空間の設計の自由度の高さに着目し、レイテンシ要件や他のスライスを管理するコントローラとの連携に必要な項を適応度に組み込み、またその適応度の向上に効果的な探索空間を設計することで効率的な全体最適化を図る。

2. 関 連 研 究
2. 1 MAP-Elites Algorithm
MAP-Elites [8] は品質多様性アルゴリズムのひとつであり、高次元の探索空間に対して低次元の特徴空間で最大適応度の分
布を可視化できる特徴がある。ユーザーは問題の対象から関心のある特徴を複数選択することができ、MAP-Elites はそれらを変量とする次元の特徴空間を任意の粒度で分割し、それぞれのセルで最も適応度の高い解を出力する。MAP-Elites は特徴
空間のより広い領域で適応度の高い個体を並列的に計算し、その結果を元に新たな解を生成していくため、既存の進化的アルゴリズムと比較して局所解に陥りにくいことが報告されている。
MAP-Elites の疑似コードを Algorithm 1 に示す。P, X はそれぞれ適応度と個体のマップを表す。マップの各セルには探索された個体の中で最も適応度の高い個体が入る。各イテレーションで個体群から無作為に選択した個体に random variation (mutation and crossover) を適用し、変異後の特徴量に対応するセル上の個体と比較、より適応度が高ければ置換する
ことで進化を進める。

3. NSE 問題
本研究では論文 [5] [6] に倣い NSE 問題を定式化した。基盤
ネットワークおよびネットワークスライス要求はそれぞれ無向グラフとしてモデル化する。無向グラフは一般に G = (V, E) の
順序対で表され、V は頂点集合、E は辺集合である。また、2 頂
点 vi , vj ∈ V 間の辺を ei,j = (vi , vj ) と表記する。基盤ネット
ワークをモデル化した無向グラフを NS = (VS , ES ) とする。ここで、基盤ネットワークの頂点は UE とクラウドノードに類別され、それぞれを VU , VC とすると、VS = VU ∪ VC である。また、ES は基盤ネットワーク上の有線・無線リンクを表し、UE 間の接続は存在しない。すなわち、∀ei,j ∈ ES (vi ∈ VC ∨ vj ∈ VC )である。クラウドノードと有線・無線リンクはそれぞれ有限の資源を持ち、本研究ではノードの CPU リソースとメモリ容量、およびリンクのスループットとレイテンシを考慮する。v ∈ VCの CPU リソースを C(v)、メモリ容量を M (v)、また e ∈ ESのスループットを T (e)、レイテンシを L(e) とする。ただし、全てのクラウドノードはレイテンシがゼロかつスループット
が無限のループ辺を持つ。これは、各クラウドノードが複数のノードによって構成され、それぞれが個別にアプリケーション
をホストできる状況を想定している。
同様に、要求されるネットワークスライスをモデル化した無向グラフを NR = (VR , ER ) とする。ネットワークスライス
は基盤ネットワーク上の UE の一部と、クラウドノード上でホストされるアプリケーションで構成される。そのため、このネットワークスライスで使用する UE の集合を VU′ ⊂ VU 、
アプリケーションの集合を VA とすると、VR = VU′ ∪ VA である。ER は UE およびアプリケーション間の仮想リンクの集合であり、UE 間の仮想リンクは存在しない。すなわち、∀ei,j ∈ ER (vi ∈ VA ∨ vj ∈ VA ) である。ネットワークスライ
スのアプリケーションおよび仮想リンクはそれぞれ基盤資源に対応する資源要求量の属性を持つ。

図 2 NSE 問題の概要図

NSE 問題では複数のネットワークスライス要求について、その受容の可否と割り当て方法を決定する。ある時点における要求された N 個のネットワークスライスの集合を R とすると、kkk)(1 ≤ k ≤ N ) に) = (VU′k ∪ VAk , ER
= (VRk , ER
その各要素 NR
ついて、受容の可否を以下の写像 MA : R → {0, 1} を用いて表す。また、受容されたネットワークスライスの番号の集合をk) = 1} とする。
NA = {k | MA (NR{kis accepted
1 if NRk
MA (NR ) :=0 otherwisek
受容されたネットワークスライスの集合 RA = {NR∈R|kk
MA (NR ) = 1} の各要素 NR について、アプリケーションのクk
ラウドノードへの割り当てを写像 MN: VAk → VC と表す。ま′kた、一般化のため次の写像 MN: VRk → VS を定義する。なお、一般的な VNE 問題におけるノード割り当てとは異なり、写像kMNは単射である必要はない。
{
kMN(n) (n ∈ VAk )′k
MN (n) :=n(n ∈ VU′k )k仮想リンクから基盤経路への割り当てを写像 MLk : ER
→ PSと表す。ここで、PS は基盤ネットワーク上の全ての経路の集合であり、経路は頂点の有限な列である。経路 p の k 番目の項
（頂点）は pk 、長さは |p| と書く。また、辺 ei,j が経路 p 上にinあることを ei,j ∼ p、経路 p 全体のレイテンシを LP (p) と表記する。すなわち、以下のように定義される。
indefei,j ∼ p ⇔ ∃q ((pq = vi ∧ pq+1 = vj ) ∨ (pq = vj ∧ pq+1 = vi ))|p|−1LP (p) :=∑L ((pk , pk+1 ))

k=1

—2—

接続する UE は同一の RAN を介して接続することで利用可
能なスループットが共有されるように変更した。このとき、|VN B | = |VRAN | ∧ ∀vi ∈ VN B ∃!vj ∈ VRAN (ei,j ∈ ES ) である。また、Node B・RAN 間のリンクは有限のスループットとゼロのレイテンシを持ち、UE・RAN 間のリンクは無限のス
ループットと一定のレイテンシを持つようモデル化する。

図3層型ネットワークモデル

この時、要求されたネットワークスライスと割り当てられた
ネットワークスライスは同一のトポロジを持つ必要があり、この制約は条件式 (1) で表される。

(

k∀k ∈ NA ∀ei,j ∈ ER′k
MLk (ei,j )1 = MN(vi )∧′k
MLk (ei,j )|M k (ei,j )| = MN
(vj )

)

L

(1)

また、各クラウドノードはホストするアプリケーションの資源要求を満たす必要があり、この制約は条件式 (2) で表される。

∀c ∈ VC ∀Attr ∈ {C, M } ∑∑Attr(a) < Attr(c)

k∈NA a∈V k (c)Akwhere VAk (c) = {a ∈ VAk | MN(a) = c}(2)
同様に、各基盤リンクはその上に確立される仮想リンクの資源要求を満たす必要があり、この制約は条件式 (3) および (4)で表される。
∑∑∀ei,j ∈ ES 
T (er ) < T (ei,j )
(3)k∈NA er ∈E k (ei,j )
R

in
k
k
where ER(ei,j ) = {er ∈ ER
| ei,j ∼ MLk (er )}()
k∀k ∈ NA ∀er ∈ ER
LP (MLk (er )) < L(er )(4)

図 4 RAN ノードの追加

3. 2 ネットワークスライスの到着モデル
ネットワークスライス要求は各クライアントが個別に発行するものであり、それらは相互に独立したイベントであると考えられ、このような過程はポアソン過程としてモデル化することができる。各ネットワークスライスがホストされてからディア
クティベートされるまでの時間を寿命と定義する。ここで、ポアソン過程においてイベントの発生間隔は指数分布に従うことが知られている。平均 n 個のネットワークスライスが並列的に要求されるようなモデルは、単位時間当たりに平均 λ/n 回発生するイベントの間隔と同じ分布に従う乱数を各スライスの寿命に設定することで実現できる。したがって、各ネットワークス
ライスの寿命を、母数が λ/n の指数分布に従う乱数として生成する。

4. 提 案 手 法k, MLk の最適化
本稿では、NSE 問題の解である写像 MA , MN
を MAP-Elites を用いて行う。以降では、ネットワークスライkを制御するコントローラは C k として記述される。
ス NR

C k = (P k , F k , Ak )ここで、P k は MAP-Elites アルゴリズムにおける個体群を表し、特徴空間上の各セルが格納している個体 (占有者) の遺伝型の集合である。また、F k , Ak はそれぞれ P k の各セルの遺伝型に対して適応度とその遺伝型が実行可能解であるかどうかを示す値を返す写像である。ここで、実行可能解とは条件
式 (1)–(4) を満たす解のことであり、遺伝型 g が実行可能解であるとき Ak (g) = 1、そうでないとき Ak (g) = 0 である。写像 F k , Ak の詳細は 4. 2 節で述べる。P k はアルゴリズム 1 のイテレーションごとに変化するため、ある時刻 t におけるコン
トローラの状態を Ctk = (Ptk , F k , Ak ) とする。このとき、時刻t における写像 MA を次のように定義する。
{
1 if ∃i ≤ t ∃g ∈ Pik (Ak (g, i) = 1)k
MA (NR | t) :=0 otherwisek
NSE 問題は、これらの条件式を満たす写像 MA , MN
, MLk を決定する問題として定義される。以降に本研究の評価で想定した NSE 問題に関するより詳細なモデルについて説明する。
3. 1 基盤ネットワークモデル
本稿では基盤ネットワークの構造を文献 [5] [9] に倣い、
UE、Node B、エッジクラウド、セントラルクラウドの 4 層からなる層型ネットワークとする。UE 以外はクラウドノー
ドに分類され、順に資源量は大きくなり、基盤ネットワークに占めるノード数は小さくなる。また、リンクは隣接する層間を接続するものに限られ、同一層内の接続および隣接しない層間の接続はない。すなわち、Node B、エッジクラウ
ド、セントラルクラウドの集合をそれぞれ VN B , VEC , VCCと す る と き 、VC = VN B ∪ VEC ∪ VCC で あ り 、∀ei,j ∈この定義は時刻 t までにコントローラ C k が実行可能解を発見
ES ((i ∈ VU ∧ j ∈ VN B ) ∨ (i ∈ VN B ∧ j ∈ VEC ) ∨ (i ∈ VEC ∧ j ∈ VCC ))k
していれば、ネットワークスライス NRが受容されることをである。
k意味している。また、個体群 Pt の要素である遺伝型は 4. 1 に文献 [5] では UE と Node B 間の無線接続を他のノード
k示す手続きによって MN, MLk に対応する写像の組に変換でき
間 の 接 続 と 同 様 に モ デ ル 化 し て い る が 、実 際 に は 同 一 のる。この手続きを写像 deck と定義すると、時刻 t における写
Node B に接続する UE 間では利用可能な帯域は共有されk
像 MN, MLk は以下のように決定できる。
るため、基盤資源であるスループットも共有されるようにモデル化すべきである。本稿では UE 層と Node B 層の間kk
MN(a | t) := MNt (a)に RAN を表現する層 VRAN を追加し、同一の Node B に—3—k
MLk (l | t) := MLt(l)k
また、写像の組 deck (g) に基づいてネットワークスライス NRを埋め込んだ際の c ∈ VC への要求資源量 QN および e ∈ ESへの要求スループット QL を定義する。
∑
QN (c, Attr, k, g) :=Attr(a)



k
k
k
(MN
argmax F k (g, t′ )
t , MLt ) = dec
g∈Ak′
t

′

where t = max{i ≤ t | ∃g ∈ Pik (Ak (g, i) = 1)},k (c|g)a∈VA

Akt′ = {g ∈ Ptk′ | Ak (g, t′ ) = 1}

QL (e, k, g) :=R

where VAk (c | g) = {a ∈ VAk | ϕkg (a) = c},
in

k
k
ER
(e | g) = {er ∈ ER
| e ∼ ψgk (er )}NSE 問題におけるもっとも基本的な要件は条件式 (1)–(4) を満たすことであり、これらの要件に違反するほど適応度が低下するように定義することで個体群は条件式を満足するように進化する。条件式 (1) は 4. 1 節で述べた遺伝型の定義により満足されるため、条件式 (2)–(4) についてそのような値を定義すればよい。したがって、要求資源量に対しての残余資源の不足量をペナルティ項 P k として以下のように定義する。なお、条件
式 (4) は他のスライスの埋め込みに対して独立であり最優先で満足するべき条件であるため、レイテンシに関する項が相対的に大きくなるように重み付けをするべきである。このため、定数 µ を十分に大きく設定することで、レイテンシ制約が優先的に達成されるように進化を方向づける。
∑

P k (g | t) :=∑k)(l = (i, j) ∈ ER
表記するとして、MLk (ld ) = ph
M k (a ),M k (a ) dX∈{C,M } c∈VCであるとき、g|VA |+d = h とすることで表現する。すなわち、任+N意の遺伝型は集合 G

k

i

N

j

k
|
|E k ||VA
× N⩽KR の要素であり、遺伝的= N⩽|VC|k

アルゴリズムの探索空間は集合 G である。
k
逆に、遺伝型 g ∈ G k を写像 MN, MLk に復号する場合には、
遺伝型 g の各要素を写像によって対応付けられる N S の要素の表現として解釈すればよい。すなわち、写像 deck を以下のように定義する。

deck (g) := (ϕkg , ψgk )ϕkg (ai ) := cgig|V k |+dAψgk (ld ) = ψgk ((ai , aj )) := pϕk (a),ϕk (a )
g

i

g

j

ただし、写像 deck によって復号された写像の組 ϕkg , ψgk は必
ずしも条件式 (1)–(4) を満たさず、そのようなものは NSE 問
題の解ではない。
4. 2 適 応 度
遺伝的アルゴリズムを用いるにあたり、最適化要件を反映するためには目的関数である適応度を適切に定義する必要がある。
本手法では複数のネットワークスライスを並列的に最適化する
ため、コントローラ C k において個体の評価を行う際には、他のコントローラが制御するスライスはその時点でそれらが決定した解によって埋め込まれているべきである。時刻 t におけるc ∈ VC の残余資源量 RN および e ∈ ES の残余スループット
RL は以下のように定義される。
∑∑
RN (c, Attr, k, t) := Attr(c) −Attr(a)na∈VA (c|t)
n∈NkA

RL (e, k, t) := T (e) −∑∑T (er )

er ∈ER (e|t)
n∈Nk
A
n

n
where Attr ∈ {C, M }, NkA = {n | n ̸= k ∧ MA (NR| t) = 1},n
VAn (c | t) = {a ∈ VAn | MN
(a | t) = c},
in

n
n
ER
(e | t) = {er ∈ ER
| e ∼ MLn (er | t)}

T (er )k (e|g)er ∈ER′

この式は、実行可能解が個体群に存在する最近の時刻 t における、実行可能解のうち最も適応度の高い個体の遺伝型を復号して時刻 t での解とすることを意味している。
4. 1 解のエンコード
遺伝的アルゴリズムを用いて組み合わせ最適化問題を扱う上で、遺伝型の定義とそれを表現型として解に復号する方法の定義が必要である。MAP-Elites においてはパラメータを直接的に符号化して遺伝型とすることが効果的であると知られており [10]、
本研究でも NSE 問題の解のパラメータを直接的に遺伝型としてk用いる。ネットワークスライス NRの最適化におけるパラメーkkk
タは、写像 MN , ML そのものであり、頂点 a ∈ VAk と辺 l ∈ ERに対応付ける要素を表す値を並べた組を遺伝型 g とすることがk
できる。頂点については、MN(ai ) = cj (ai ∈ VAk , cj ∈ VCk ) であるとき、gi = j とすることで表現する。また、辺については、
経路探索の候補を各リンクの端点に対応するノード間の K 個の最短経路に絞り、何番目に短い経路を選ぶかをパラメータとして用いる。すなわち、2 頂点 ci , cj 間の第 h 最短経路を phi,j 、まkの各要素について一意の番号 d ∈ N⩽|E k | を用いて ld と
た ER

∑

∑

max {QL (e, k, g) − RL (e, k, t), 0}

e∈ES

+µ

max {QN (c, X, k, g) − RN (c, X, k, t), 0}∑{}
max LP (ψgk (er )) − L(er ), 0ker ∈ER

ここで、P k (g | t) = 0 であるとき、写像の組 deck (g) は NSE
問題の実行可能解である。したがって、写像 Ak は以下のように定義される。
{
1 if P k (g | t) = 0
Ak (g, t) :=0 otherwise
また、NSE 問題における基本的な最適化要件としてスライスのホストにかかるコストの低減がある。これは資源要求量の総和を最小化することで達成されるが、アプリケーションによるクラウドノードの資源の消費量は一定であるため、仮想リンクによるスループットの消費のみを考慮すればよい。したがって、これらの要件を反映した適応度は以下のように構成できる。
∑−ρP k (g | t) −QL (e, k, g)e∈ES

ここで、ρ は定数でありこれを十分に大きく設定することで、個体群は制約条件の達成を優先して進化する。
しかし、この適応度の定義は他のスライスを考慮しておらずkNRに関する個別最適化の範疇に留まっており、全体最適化を達成できない。このため、非利己的な評価値を別に定義し適応度に組み込むことで、他のスライスを考慮した協調的な動作を実現し全体最適化を行う。
4. 2. 1 Load Balancing
基本的に他のスライスが受容されやすくなるためには、ボト
ルネックとなるような残余資源量が少ない要素を減らすことが重要である。これは、残余資源が潤沢である要素を優先的に利用することで実現できる。すなわち、スライスに割り当てた要素の残余資源量の総和を適応度に組み込めば、そのような解が優先的に選択される。したがって、写像 B k を以下のように定

—4—

義する。

表1

∑

B k (g | t) :=∑∑NotationA

RL (e, k, t)

k e∈E (ψ k (e ))er ∈ERrS
gin

where ES (p) = {e ∈ ES | e ∼ p}
4. 2. 2 他スライスの資源要求の考慮k
MA (NR| t) = 1 であるときには、コントローラ C k は他の受容されていないスライスからの需要が集中している基盤ネット
ワークの要素を利用しない実行可能解を探索することで、より多くのスライスが受容されることが期待できる。このとき、各コントローラにおいて最も適応度の高い個体は、ペナルティ項が小さいためその時点の資源状況に最も適合している埋め込みであり、将来的に受容される可能性が高い。したがって、このような埋め込みにおける要求資源量を、基盤ネットワークの要
素の需要として設定する。すなわち、時刻 t における c ∈ VC
および e ∈ ES の需要を表す値をそれぞれ DN , DL として以下のように定義する。
∑∑∑
DN (c, k, t) :=Attr(a)n (c|t)X∈{C,M } n∈Nk a∈VA
R

DL (e, k, t) := T (e) −∑∑T (er )

er ∈ER (e|t)
n∈Nk
R
n

n
where NR = {n | MA (NR| t) = 0},

VAn (c | t) = {a ∈ VAn | ϕngtn (a) = c},
in

n
n
ER
(e | t) = {er ∈ ER
| e ∼ ψgntn (er )}, gtn = argmax F k (g, t)g∈Ptn

コントローラ C k は、これらの値が小さい基盤ネットワークの要
素を利用する実行可能解を優先的に探索したく、これはスライ
スに割り当てた要素の需要の総和を最小化するように進化するということである。ここで、写像 D k を以下のように定義する。
∑∑∑
DN (ϕkg (a), k, t) +DL (e, k, t)
Dk (g | t) :=k e∈E (ψ k (e ))er ∈ER
r
S
g

k
a∈VA

Parameter

RN (ϕkg (a), X, k, t)+

X∈{C,M } a∈V k

∑

比較手法

in

where ES (p) = {e ∈ ES | e ∼ p}
4. 2. 3 協調的制御
以上で定義した項を用いて、適応度を返す写像 F k を以下のように定義する。
∑
F k (g, t) := −QL (e, k, g) − ρP k (g | t) + ϵB k (g | t)−e∈ESk
MA (NR| t) · δD k (g | t)ここで、ϵ, δ は定数であり、ϵ は第三項が他の最適化要件に影響を及ぼさないようにするために十分小さく設定すべきである。
また、右辺の第四項はコントローラ C k において実行可能解が既に発見されているときにのみ有効であり、δ は十分に大きく設定することで他のスライスを考慮した実行可能解の探索を優先させることができる。
4. 3 特徴量空間の設計
MAP-Elites アルゴリズムでは解探索を特徴空間上で行うため、探索空間上に分布した優れた解を効率的に探索するためにはそれらを捉えやすい特徴空間を設計することが重要である。
また、動的 NSE 問題において生じる環境変動に対して柔軟に適応するには、環境によって最適な値が異なるような特徴量を変数とすることが有効である。これを踏まえ、本手法では以下の特徴量を利用する。

Algorithm

ρ

ϵ

δ

104

102

10−5
10−5
0
0

102
0
102
0

EGA

104

102

10−5
0

102
0

RW-BFS [7]

-

-

-

-

*ME-C
*ME-LB*ME-GW
ME-I

MAP-Elites

GA-C
GA-I
NR

µ

（ 1 ） 割当ノードの総資源量— 各アプリケーションに割り当てられたクラウドノードの物理資源量の総量。3. 1 節で定義した基盤ネットワークモデル
においてはクラウドノードの種類に応じて資源量が大きく異なるため、この特徴量はどの種類のノードを主に利用するかを意味する。そのスライスのサービス要件とその時点での物理資源利用状況によって最適なノード利用は異なると考えられるため、この特徴量において分散して解を探索することは動的 NSE において効果的である。ただし、この値を変数とする次元での解の分布は不均一であり、解探索効率の低下を招くため代理として以下の値 F1 を用いる。ここで、基盤ノードの番号は Node
B、エッジクラウド、セントラルクラウドの順に割り当てられているとする。
（ 2 ） 合計レイテンシ— スライスの各リンクに割り当てられたパスの合計のレイテンシ。この値は主にパスのホップ長に相関を持つが、同じホップ長のネットワークについてもレイテンシの値によって区別することができ、経路選択の多様化を促す。経路選択の多様化は需要が高い資源の利用の回避などにつながるため、動的NSE において効果的であると思われる。この値においても同様の理由で代理として以下の値 F2 を用いる。
k
|ER
|

k
|VA
|

F1 (g, k) :=∑i=1

gi , F2 (g, k) :=∑g|V k |+iA

i=1

5. 評 価 結 果
複数のネットワークスライスを個別のコントローラで制御する動的 NSE 問題について、計算機シミュレーションを通して提案手法および比較手法の評価を行った。提案手法において、
単位時間あたりに 100 個の解候補を評価し、受容率および受容率の推移を比較する。なお、本研究では並列化などによるプ
ログラムの最適化を行っていないため、実時間的な実行速度についての評価は行わないが、いずれの手法においても解候補の評価プロセスは基本的に同じであるため、実行速度において差はないと考えらえる。スライス要求到着モデルのパラメータは λ = 0.2, n = 40 に設定し、一回のシミュレーション期間は1000 単位時間とした。また、タイムアウト時間として 100 単
位時間を設定しており、各コントローラにおいてこれを超過す
るとそのネットワークスライス要求は却下される。
評価で用いた手法の一覧を表 1 に示す。ノーテーションの前に*がついているものが提案手法である。表中のパラメータは式 4. 2. 3 中の定数であり、これらの値に応じて各最適化要件の影響度が変化する。Elitism-based Genetic Algorithm (EGA)
は基本的な遺伝的アルゴリズムにエリート選択を用いて進化を安定させたものであり、QD アルゴリズムに対する従来の遺伝的アルゴリズムとして比較で用いる。また、手法 NR は文献 [5]で提案されているヒューリスティクスと同様に、VNE 問題のヒューリスティクスである RW-BFS [7] を本問題に適用したものである。
基盤ネットワークは 3. 1 節で定義した層型基盤ネットワー

—5—

表2

基盤ネットワークのパラメータ

Node Type
VU
|V |
C, M

VN B

90
-

VEC

VCC

30
10
1
[100, 200] [200, 700] [5000, 10000]
Link Type|E|
T
L

EU,N B

EN B,EC

EEC,CC[1, 3][50, 80][3, 7][2, 6][80, 150][3, 5][1, 1][200, 500]
[2, 4]
図5

表3

受容されたスライス数

サービスタイプごとのスライス要件

Service Type
URLLC

eMBB

[1, 10][1, 5][3, 15][5, 15][10, 30][1, 10] [15, 30][1, 10][1, 5][10, 40][1, 3][10, 20][1, 5][25, 50] [50, 100]

|VU′ |
|VA |
C, M
T
L
表4

ME-C
Mean 123.73
SD
3.02

mMTC

受容されたリクエスト数

ME-LB ME-GW

ME-I

GA-I

NR

123.27
3.02

121.63 117.80 115.70
2.68
3.00
3.27

97
-

122.573.03

GA-C

クモデルに基づいて生成する。シミュレーションで用いた基盤
ネットワークに関する変数の設定を表 2 に示す。なお、表中のEA,B は VA , VB の要素間のリンクの集合であり、|E| は VA の各要素と接続される VB の要素の個数を表す。また、EU,N B の要素は実際には VRAN を介する。
シミュレーションにおけるネットワークスライス要求に関するパラメータ設定を表 3 に示す。
一回のシミュレーションを通して受容されたネットワークス
ライス数を表 4 および図 5 に示す。NR 以外の手法については、同じ設定のシミュレーションを 30 回試行した結果をまとめており、またいずれのシミュレーションにおいてもネットワークス
ライス要求とその到着タイミングは同一である。MAP-Elites
アルゴリズムを用いた手法群の平均受容個数は他の手法と比較
していずれも多く、動的 NSE 問題において最も効率的に実行可能解を探索していることが分かる。また、その中でも提案手
法 ME-C の平均受容個数が最も多く、非利己的な動作による協調的な制御によって最大受容個数が向上することを示している。また、単位時間ごとの平均受容個数の推移を図 6 に示す。
どの時刻においても基本的に同様の結果が示されており、複数のネットワークスライスの並列最適化における MAP-Elites ア
ルゴリズムおよび協調的な動作の有効性が確認できる。

6. お わ り に様々な要件を持つ複数のネットワークスライスを同時に扱う
動的 NSE 問題について、各ネットワークスライスを協調的に動作する個別のコントローラで並列的に最適化し、全体最適化する手法を提案した。遺伝的アルゴリズムの目的関数の設計の自由度を利用し、協調的な動作を実現するための非利己的な指標を適応度に導入することで、個別のコントローラでの最適化
でありながら全体最適化を可能にした。計算機シミュレーショ
ンを通して比較評価を行い、提案手法の優位性およびその最適化項ごとの性質を明らかにした。評価シナリオでの受容個数の差は顕著ではなかったが、実行可能解の発見速度の点での差を

図6

平均受容数

現在確認できており、今後、受容個数の差がより大きく現れる
条件を明らかにしていく。
文
献[1] NGMN, 5G white paper 2, NGMN Alliance, July 2020.
[2] F. Debbabi, R. Jmal, L.C. Fourati, and A. Ksentini, “Algorithmics and modeling aspects of network slicing in 5G andbeyonds network: Survey,” IEEE Access, vol.8, pp.162748–
162762, 2020.
[3] S. Vassilars, et al., “The algorithmic aspects of network
slicing,” IEEE Communications Magazine, vol.55, no.8,
pp.112–119, 2017.
[4] H.-T. Chien, et al., “End-to-end slicing as a service
with computing and communication resource allocation for
multi-tenant 5G systems,” IEEE Wireless Communications,vol.26, no.5, pp.104–112, 2019.
[5] K. Ludwig, A. Fendt, and B. Bauer, “An eﬃcient online
heuristic for mobile network slice embedding,” Proceedingsof Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN), pp.139–143, 2020.
[6] A. Fendt, C. Mannweiler, L.C. Schmelz, and B. Bauer, “Aformal optimization model for 5G mobile network slice resource allocation,” Proceedings of IEEE Annual Information Technology, Electronics and Mobile Communication
Conference (IEMCON), pp.101–106, 2018.
[7] X. Cheng, et al., “Virtual network embedding throughtopology-aware node ranking,” ACM SIGCOMM Computer
Communication Review, vol.41, no.2, p.38–47, April 2011.
[8] J.-B. Mouret and J. Clune, “Illuminating search spaces bymapping elites,” arXiv preprint arXiv:1504.04909, 2015.
[9] P. Labrador, et al., “5G NORMA network architecture –intermediate report,” Jan. 2017.
[10] D. Tarapore, J. Clune, A. Cully, and J.-B. Mouret, “How do
diﬀerent encodings inﬂuence the performance of the mapelites algorithm?,” Proceedings of the Genetic and Evolutionary Computation Conference, p.173–180, 2016.

—6—