一種5G網(wǎng)絡(luò)切片的編排算法

2017-09-03 09:21:15周恒暢志賢楊武軍郭娟

電信科學(xué) 2017年8期

關(guān)鍵詞：子圖切片路由

周恒，暢志賢，楊武軍，郭娟

（西安郵電大學(xué)通信與信息工程學(xué)院，陜西西安 710121）

一種5G網(wǎng)絡(luò)切片的編排算法

周恒，暢志賢，楊武軍，郭娟

（西安郵電大學(xué)通信與信息工程學(xué)院，陜西西安 710121）

網(wǎng)絡(luò)切片是基于SDN/NFV的5G網(wǎng)絡(luò)架構(gòu)實現(xiàn)按需組網(wǎng)的一種重要技術(shù)。通過分析5G主要場景，提出了SDN/NFV架構(gòu)下一種基于GA-PSO優(yōu)化的網(wǎng)絡(luò)切片編排算法。該算法利用粒子群算法能夠快速收斂于全局最優(yōu)解的特性，設(shè)計網(wǎng)絡(luò)切片性能的評價函數(shù)。并且利用遺傳算法快速隨機搜索的能力，實現(xiàn)對網(wǎng)絡(luò)切片的更新和優(yōu)化，利用粒子群追逐局部最優(yōu)解與全局最優(yōu)解得到最優(yōu)網(wǎng)絡(luò)切片。仿真實驗結(jié)果表明，該算法能夠?qū)崿F(xiàn)對多業(yè)務(wù)場景網(wǎng)絡(luò)切片的個性化創(chuàng)建，充分發(fā)揮SDN 的集中控制方式的優(yōu)點，在降低網(wǎng)絡(luò)能耗的同時，提高網(wǎng)絡(luò)資源利用率。

5G；網(wǎng)絡(luò)切片；GA-PSO；編排

1 引言

以用戶為中心是未來5G網(wǎng)絡(luò)架構(gòu)設(shè)計的主要理念，這要求5G網(wǎng)絡(luò)具有對各種業(yè)務(wù)場景進行按需組網(wǎng)和靈活部署的能力[1]，隨著用戶終端數(shù)量的增加、流量規(guī)模的增長和用戶需求的多樣化，當(dāng)前的核心網(wǎng)EPC（evolved packet core）逐漸變得難以處理越來越多樣化的服務(wù)要求。在5G時代，互聯(lián)網(wǎng)服務(wù)對象和應(yīng)用場景變得多樣化，為每一個服務(wù)建設(shè)一個專用的物理網(wǎng)絡(luò)，這既不現(xiàn)實也不高效，而網(wǎng)絡(luò)切片（network slicing，NS）技術(shù)可以實現(xiàn)從“one size fits all”向“one size per service”的過渡，為現(xiàn)有網(wǎng)絡(luò)提供了一個全新的解決方案[2]。網(wǎng)絡(luò)切片的先決條件是可以虛擬化各種不同的網(wǎng)絡(luò)元素和SDN的集中控制[3]，隨著網(wǎng)絡(luò)功能虛擬化（network function virtualization，NFV）技術(shù)的成熟，實現(xiàn)了軟硬件解耦、共享基礎(chǔ)設(shè)施資源和按需調(diào)度[4]，同時軟件定義網(wǎng)絡(luò)（software defined networking，SDN）將數(shù)據(jù)平面與控制平面解耦合，簡化了網(wǎng)絡(luò)管理，靈活了路由的配置[5]，因此在NFV和SDN的網(wǎng)絡(luò)架構(gòu)下，對網(wǎng)絡(luò)切片的編排和部署變得可行[6]。

一個網(wǎng)絡(luò)切片是 5G網(wǎng)絡(luò)中的一個端到端虛擬網(wǎng)絡(luò)，是一組邏輯網(wǎng)絡(luò)功能的集合。網(wǎng)絡(luò)切片主要控制和操作服務(wù)層（service layer）和基礎(chǔ)設(shè)施層（infrastructure layer）。服務(wù)層描述系統(tǒng)的邏輯結(jié)構(gòu)，包括網(wǎng)絡(luò)的功能模塊以及不同功能模塊之間的連接方式，提供網(wǎng)絡(luò)切片的定義、操作和部署方式的模板。基礎(chǔ)設(shè)施層從物理層面描述維持一個網(wǎng)絡(luò)切片運行所需要的網(wǎng)絡(luò)元素和資源，包括計算資源和網(wǎng)絡(luò)資源[7]。

2 基于NS劃分的路由模型

3GPP將5G的主要應(yīng)用場景分為三大類，分別是移動寬帶增強（enhanced mobile broadband， eMBB）、大規(guī)模機器型通信（massive machine-type communication，mMTC）、超高可靠超低時延通信（ultra-reliable and low-latency communication，uRLLC）[8,9]。mMTC和uRLLC是人與機器、機器與機器之間的通信，是物聯(lián)網(wǎng)的主要應(yīng)用場景；而eMBB主要是改善人與人之間的通信體驗，是在現(xiàn)有移動寬帶業(yè)務(wù)場景的基礎(chǔ)上，對于用戶的體驗等性能的進一步提升。3種主要業(yè)務(wù)場景需求不同、性能要求指標(biāo)也不同，因此在NFV和SDN的網(wǎng)絡(luò)架構(gòu)下，對切片的編排會直接影響網(wǎng)絡(luò)的負載、資源利用率和能耗等。

基于SDN技術(shù)，研究人員在優(yōu)化網(wǎng)絡(luò)切片編排、提高資源利用率方面做了很多研究。Koerner M等[10]提出利用SDN技術(shù)為每個服務(wù)建立自己的虛擬網(wǎng)絡(luò)，在網(wǎng)絡(luò)內(nèi)部實現(xiàn)負載均衡。Google則基于自己的數(shù)據(jù)中心，提出 B4架構(gòu)，實現(xiàn)了基于SDN的數(shù)據(jù)中心間的流量工程，鏈路利用率提高到接近100%[11]。吳一娜[12]提出基于切片劃分的網(wǎng)絡(luò)資源控制機制，通過貪婪策略對網(wǎng)絡(luò)需求進行排序，再逐一編排。這些研究方法都是建立在網(wǎng)絡(luò)狀態(tài)較為簡單的數(shù)據(jù)中心進行的網(wǎng)絡(luò)資源的優(yōu)化，沒有考慮到應(yīng)用服務(wù)在帶寬、時延和可靠性方面的復(fù)雜需求，并且大多僅針對網(wǎng)絡(luò)資源利用率或QoS等單個目標(biāo)，關(guān)于NS的編排算法也多從網(wǎng)絡(luò)局部的信息針對單一目標(biāo)進行算法的優(yōu)化，缺少對網(wǎng)絡(luò)整體考慮。

為了解決以上問題，提出一種基于 GA-PSO的網(wǎng)絡(luò)切片算法。具體地，本文將網(wǎng)絡(luò)的優(yōu)化轉(zhuǎn)化為對網(wǎng)絡(luò)切片的編排，通過對用戶流量的統(tǒng)計分析，知道整網(wǎng)的流量分布特征，預(yù)先構(gòu)造好基本切片，然后再對實時的流量分析負載和需求，構(gòu)造切片并將構(gòu)造的結(jié)果通過 OpenFlow協(xié)議流表的形式部署在交換節(jié)點上。

基于該算法的網(wǎng)絡(luò)資源控制模型具有以下特征：根據(jù)第3.2.2節(jié)中帶寬和時延分類閾值將需求相近的歸為一類，為同一種切片；NFV實現(xiàn)對物理資源的虛擬化，SDN控制器根據(jù)網(wǎng)絡(luò)負載和流量的情況生成路由策略；部署路由策略。

3 GA-PSO切片生成算法

在基于網(wǎng)絡(luò)切片劃分的路由模型中，切片劃分的優(yōu)劣直接決定了網(wǎng)絡(luò)的負載情況和資源利用率，因此切片的生成對基于NFV/SDN的網(wǎng)絡(luò)切片架構(gòu)系統(tǒng)來說至關(guān)重要。另外，現(xiàn)有的切片劃分算法一般是采用貪心策略，對網(wǎng)絡(luò)中的需求逐個進行資源的劃分和路由的選擇，缺少全局優(yōu)化，沒有將SDN掌握全局信息，集中控制的優(yōu)點發(fā)揮出來，并且當(dāng)網(wǎng)絡(luò)負載非常大的時候，逐個劃分的時間復(fù)雜度太大，很難滿足實時性需求。

3.1 PSO算法

粒子群優(yōu)化（particle swarm optimization，PSO），是由Kennedy J和Eberhart R C等人[13]于1995年開發(fā)的一種群智能算法。在PSO算法中每個優(yōu)化問題的解都是搜索空間的一只鳥，被抽象為沒有質(zhì)量和體積的粒子，粒子的位置代表被優(yōu)化空間在搜索空間中的潛在解，所有粒子都有一個評價函數(shù)決定的適應(yīng)值。每個粒子根據(jù)自身和周圍粒子的經(jīng)驗在搜索空間中調(diào)整自己的位置和速度?；A(chǔ)的PSO算法定義了兩個非常重要的參數(shù)：某一代種群中，粒子適應(yīng)度最高的稱為pbest；所有種群的粒子至今為止發(fā)現(xiàn)的全局最優(yōu)解稱為gbest。并且將其所找到的位置保存下來，用于引導(dǎo)和更新粒子的位置和速度。位置xi,j(t+ 1)和速度 vi,j(t + 1)更新方程如下：

其中，w為慣性權(quán)重，1c和2c為正的學(xué)習(xí)因子，1r和2r為0到1之間均勻分布的隨機數(shù)。

3.2 GA-PSO 算法

3.2.1 算法的基本思想

PSO最初被用于函數(shù)優(yōu)化方面，而5G中網(wǎng)絡(luò)切片的劃分問題本身是為所有用戶的流量需求計算出一個合理的路由方案，屬于網(wǎng)絡(luò)路由問題，因此需要重新設(shè)計評價函數(shù)和粒子更新算法。針對以上問題，本文借鑒GA（genetic algorithm，遺傳算法）[14]中的雜交和變異的思想，首次將雜交和變異的思想應(yīng)用于切片優(yōu)化，一個切片本身作為一個子圖代表一個可行解，因此種群的進化和粒子的遷徙就轉(zhuǎn)化為子圖雜交的過程。

算法的基本思想是根據(jù)3GPP提出的3種主要應(yīng)用場景得到兩類原始粒子，再由這兩類原始基本粒子進一步初始化得到一定數(shù)量的基本粒子，形成初始的種群。每個粒子代表一個拓撲子圖，評價每個粒子的適應(yīng)度，存儲當(dāng)前個體最優(yōu)的粒子和全局最優(yōu)粒子，按照雜交和變異的思想對子圖進行更新優(yōu)化，產(chǎn)生新的拓撲子圖。粒子群追隨當(dāng)前最優(yōu)粒子在解空間中搜索，即通過迭代找到最優(yōu)子圖作為最終的路由方案。

3.2.2 基本粒子初始化

根據(jù)3GPP提出的3種主要應(yīng)用場景，本文給出如下定義。

定義1（QoS流量類）有相同或相近QoS需求的用戶流量集合。設(shè)用戶x的流量（flow）用 fx表示，則流量類集合 F ={ f1, f2, f3,...,fn}為一種QoS流量類型，其中:

定義2（點到點流量矩陣[15,16]）流量矩陣表示網(wǎng)絡(luò)中源—目的（original-destination，OD）節(jié)點之間每個流的分布情況，流量矩陣的維數(shù)等于網(wǎng)絡(luò)中所有OD流的數(shù)目，它從全局的觀點來描述整個網(wǎng)絡(luò)的數(shù)據(jù)流動情況，是網(wǎng)絡(luò)決策的重要依據(jù)。點到點流量矩陣（point-to-point traffic matrix）表示源（O）節(jié)點和目的（D）節(jié)點之間的流量 V（O, D），它表示網(wǎng)絡(luò)中所有OD節(jié)點對間的流量，描述了網(wǎng)絡(luò)流量在各個OD節(jié)點對間的分布情況。

定義3（低時延網(wǎng)絡(luò)切片）能夠為特定的QoS流量類提供最小時延保障的一個虛擬邏輯網(wǎng)絡(luò)，由一系列網(wǎng)絡(luò)功能、運行這些網(wǎng)絡(luò)功能的資源以及這些網(wǎng)絡(luò)功能特定的配置所組成。

定義4（高帶寬網(wǎng)絡(luò)切片）能夠為特定的QoS流量類提供最小帶寬保障的一個虛擬邏輯網(wǎng)絡(luò)。

依上述定義，本文根據(jù) QoS流量需求使用最短路徑算法，生成兩個基類NS：低時延類切片、高帶寬類切片，組成雜交池，按照第3.2.4節(jié)所述子圖雜交和子圖變異方法進行兩兩隨機雜交，產(chǎn)生 N個基本粒子，構(gòu)成初始化種群。一個子圖粒子G是一個N×N的鄰接矩陣，代表一個潛在的解，即一個可選的路由方案，也就是一個潛在的網(wǎng)絡(luò)切片，其中，N為網(wǎng)絡(luò)拓撲中的節(jié)點的個數(shù)。

3.2.3 基本粒子適應(yīng)度評價函數(shù)

《5G白皮書》[9]中將未來移動互聯(lián)網(wǎng)和物聯(lián)網(wǎng)的主要應(yīng)用場景分為連續(xù)廣域覆蓋、熱點大容量、低功耗大連接和低時延高可靠，各場景需要的關(guān)鍵能力指標(biāo)為高帶寬的體驗速率、超高的流量密度、超高的連接密度、低時延高可靠。

綜合這4種關(guān)鍵能力指標(biāo)，本文選用時延、帶寬兩個參數(shù)來刻畫未來5G應(yīng)用場景的性能指標(biāo)。

網(wǎng)絡(luò)切片的性能由不同的性能參數(shù)表征。但不同的參數(shù)具有不同的取值范圍和單位，因此無法進行量化比較與分析，本文采用0均值歸一化方法將不同的傳輸參數(shù)歸一化（normalization），歸一化計算式為:

其中，v 為性能參數(shù)歸一化值；v為性能參數(shù)；μ為性能參數(shù)的均值；σ為性能參數(shù)的方差。

評價一個粒子的適應(yīng)度是根據(jù)它所代表的切片的傳輸參數(shù)做出的，也就是說粒子的適應(yīng)度即NS的適應(yīng)度?；谏鲜鲂阅軈?shù)歸一化，使得對NS的量化分析變得可行，同時考慮到5G應(yīng)用場景的分類和傳輸參數(shù)的選擇以及對微小變化的反映，本文以指數(shù)函數(shù)為基礎(chǔ)設(shè)計的粒子適應(yīng)度評價函數(shù)如下：

其中，D為歸一化后的一個子圖中時延最大的路徑時延值；B為歸一化后的一個子圖中鏈路的最小帶寬；α為低時延需求類切片占所有切片的比例；β為高帶寬需求類切片占所有切片的比例。

3.2.4 基本粒子更新

標(biāo)準(zhǔn)PSO算法中的粒子通過式（1）、式（2）跟蹤粒子本身所找到的最優(yōu)解和整個種群目前找到的最優(yōu)解更新自己。本文中，根據(jù)網(wǎng)絡(luò)切片的實際問題特點對傳統(tǒng)的方法進行改進，借鑒 GA中的雜交和變異的思想，將雜交和變異的思想應(yīng)用于子圖優(yōu)化。

（1）子圖雜交

將當(dāng)前的粒子所代表的子圖依次與局部最優(yōu)子圖和全局最優(yōu)子圖雜交，然后對雜交后的子圖進行優(yōu)化。雜交步驟如下。

步驟 1 找出當(dāng)前粒子與局部最優(yōu)子圖、全局最優(yōu)子圖相同的節(jié)點。

步驟2 如果當(dāng)前粒子與局部最優(yōu)子圖相同節(jié)點數(shù)小于4個并且與全局最優(yōu)子圖相同節(jié)點數(shù)也小于4個，則進入第3.2.4節(jié)的子圖變異。

步驟 3 如果當(dāng)前粒子與局部最優(yōu)子圖相同節(jié)點數(shù)大于3個，則隨機在相同的節(jié)點中選擇兩個節(jié)點，交換這兩個節(jié)點之間的路由，并保持連通性，否則進入步驟4。

步驟4 如果當(dāng)前粒子與全局最優(yōu)子圖相同節(jié)點數(shù)大于 3個，則隨機在相同的節(jié)點中選擇兩個節(jié)點，交換這兩個節(jié)點之間的路由，并保持連通性。

步驟5 刪除所有既不是源節(jié)點也不是目標(biāo)節(jié)點的葉子節(jié)點。

步驟6 輸出這個雜交后的新子圖。

（2）子圖變異

根據(jù)變異概率，隨機選擇一個不在切片路由內(nèi)的點，就近接入路由內(nèi)。變異本身是一種局部隨機搜索，與雜交算子結(jié)合在一起，保證了種群更新的有效性，增強了粒子群的局部隨機搜索能力；同時使得粒子群能夠保持多樣性，防止局部過早收斂。因為設(shè)置的變異概率 Pm非常小，所以可以避免算法退化為隨機搜索。變異步驟如下。

步驟1 初始化一個隨機值。

步驟2 比較這個值與變異概率 Pm的大小，如果大于 Pm，則進入步驟3；否則，轉(zhuǎn)入步驟4。

步驟3 隨機選擇不在路由路徑中的一個點，選擇適應(yīng)度最高的兩條路接入子圖。

步驟4 輸出切片。

3.2.5 算法實施步驟

本文基于GA-PSO優(yōu)化的網(wǎng)絡(luò)切片編排算法具體步驟如下。

步驟 1 歸一化表征網(wǎng)絡(luò)切片性能的傳輸參數(shù)，歸一化方法按照式（3）。

步驟 2 使用最短路徑算法生成 3個基類NS：低時延類切片、高帶寬類切片和高可靠類切片，組成雜交池，池內(nèi)切片按照第3.2.4節(jié)的雜交和變異算法隨機兩兩雜交，初始化2n個粒子，每個粒子即一個NS，代表一個拓撲子圖G。

步驟3 每類切片，選擇合適的參數(shù)，按照Fitness( α, β, D, B)計算種群粒子的適應(yīng)度，并進行排序，選擇適應(yīng)度最高的n個粒子組成初始化種群。

步驟4 記錄步驟 3適應(yīng)度最高的切片，為局部最優(yōu)粒子 Gpb，同時也是全局最優(yōu)粒子 Ggb。

步驟5 設(shè)置迭代次數(shù)m和描述最優(yōu)解穩(wěn)定性的最優(yōu)解控制閾值threshold。

步驟6 按照第3.2.4節(jié)的算法，根據(jù)局部最優(yōu)NS和全局最優(yōu)NS，采用雜交、變異的方式更新粒子群中的所有粒子。

步驟 7 按照 Fitness( α , β, D, B)計算種群粒子的適應(yīng)度，更新局部最優(yōu)粒子 Gpb，如果當(dāng)前的局部最優(yōu)粒子 Gpb的適應(yīng)值高于當(dāng)前的全局最優(yōu)粒子 Gg,b，則更新全局最優(yōu)粒子；否則最優(yōu)解控制計數(shù)器加1。

步驟 8 檢查迭代終止條件，如果迭代次數(shù)達到m次或者最優(yōu)解控制計數(shù)器的值大于最優(yōu)解控制閾值 threshold，則進入步驟 9，否則進入返回步驟6。

步驟9 輸出最優(yōu)子圖 Ggb。

4 實驗分析

4.1 實驗環(huán)境

為了驗證本文所提出的基于GA-PSO優(yōu)化的網(wǎng)絡(luò)切片編排算法的性能，設(shè)計了實驗環(huán)境，拓撲結(jié)構(gòu)如圖1所示。網(wǎng)絡(luò)環(huán)境中源（O）節(jié)點O1、O2、…、On為接納用戶流量的節(jié)點，負責(zé)接納用戶的流量，D1、D2、…、Dn為目的（D）節(jié)點；S1、S2、S3、…、Sm為運行OpenFlow協(xié)議的交換機；控制器為整個SDN的控制器。本文通過在相同環(huán)境下實現(xiàn)基于網(wǎng)絡(luò)切片的 GA-PSO和貪心策略算法以及不使用網(wǎng)絡(luò)切片而選擇優(yōu)先級較高路徑轉(zhuǎn)發(fā)的傳統(tǒng)OSPF算法，比較不同網(wǎng)絡(luò)規(guī)模下，網(wǎng)絡(luò)路由生成所用時間，并將每種算法的路由策略部署于實驗網(wǎng)絡(luò)，根據(jù)源節(jié)點接入業(yè)務(wù)流量的不同，測量不同負載時整個網(wǎng)絡(luò)的資源利用率，以驗證本文算法的穩(wěn)定性和高效性。

圖1 實驗環(huán)境拓撲示意

4.2 實驗設(shè)計與結(jié)果分析

本文選擇兩種算法與提出的 GA-PSO進行對比。方法一為OSPF算法：它是數(shù)據(jù)鏈路狀態(tài)路由協(xié)議，采用最小生成樹算法。即在傳統(tǒng)網(wǎng)絡(luò)不使用網(wǎng)絡(luò)切片，按最短路徑轉(zhuǎn)發(fā)，不考慮負載均衡；方法二為貪心策略：在使用網(wǎng)絡(luò)切片情形下，采用貪心策略進行QoS需求（切片）排序，再針對每個切片進行路由選擇[12]。在下面的實驗分析過程中，首先保持流量需求即切片總量不變，通過增加網(wǎng)絡(luò)的節(jié)點（網(wǎng)絡(luò)規(guī)模變化）來比較 3種算法在生成路由策略所用時間和部署路由之后的能耗；然后又使用相同的網(wǎng)絡(luò)拓撲（網(wǎng)絡(luò)規(guī)模不變），針對不斷變化的各類流量需求，對 3種算法在能耗和資源利用率方面的性能進行分析。

4.2.1 不同網(wǎng)絡(luò)規(guī)模的影響

在流量需求數(shù)目相同的情況（本文取流量數(shù)目為30）下，本文比較不同的網(wǎng)絡(luò)規(guī)模下，3種方法的性能。

（1）時間復(fù)雜度

在未來5G網(wǎng)絡(luò)中，無論是熱點大容量還是低時延高可靠的業(yè)務(wù)場景，對于大量新到來的流量需求，控制器必須盡可能快地部署路由策略，否則會嚴(yán)重影響服務(wù)質(zhì)量，因此算法的時間復(fù)雜度是一個非常重要的指標(biāo)，它標(biāo)志著算法在實際部署環(huán)境下能否達到預(yù)期效果。從圖2可以看出，OSPF算法僅基于鏈路狀態(tài)進行最短路徑路由轉(zhuǎn)發(fā)，不考慮各鏈路間負載均衡，相對時間復(fù)雜度較低，但是當(dāng)實際中進行網(wǎng)絡(luò)部署時網(wǎng)絡(luò)規(guī)模增大帶來的整體負載不均衡將影響網(wǎng)絡(luò)性能。采用貪心策略的算法在網(wǎng)絡(luò)規(guī)模較小時，與 GA-PSO時間復(fù)雜度相近甚至優(yōu)于 GA-PSO，但隨著網(wǎng)絡(luò)規(guī)模所用時間也迅速增加，性能惡化，這主要由于采用貪心策略的算法，對到來的流量先進行排序操作，再逐個求解，這大量重復(fù)了路由的計算和選擇，浪費大量時間。GA-PSO算法雖然在網(wǎng)絡(luò)規(guī)模較小所用時間并不是特別少，但隨著網(wǎng)絡(luò)規(guī)模的增大其所用時間增長緩慢，具有良好的針對不同規(guī)模網(wǎng)絡(luò)的耗時穩(wěn)定性，明顯優(yōu)于基于貪心策略的排隊算法。

圖2 不同的網(wǎng)絡(luò)規(guī)模下3種算法的時間復(fù)雜度

（2）能耗

隨著未來移動互聯(lián)網(wǎng)和物聯(lián)網(wǎng)的發(fā)展，大量網(wǎng)絡(luò)設(shè)備接入網(wǎng)絡(luò)，節(jié)能問題成為不可回避的重要問題。因此，通過對比3種算法在不同網(wǎng)絡(luò)規(guī)模下的能耗，進一步證明本文算法的有效性和實用性。從圖3可以看出，隨著網(wǎng)絡(luò)規(guī)模的擴大，能耗都在持續(xù)增加。傳統(tǒng)的 OSPF算法，隨著網(wǎng)絡(luò)規(guī)模的擴大，能耗急劇上升。同時，基于貪心策略的排序優(yōu)化算法，能耗雖然也在持續(xù)升高但明顯低于OSPF算法，但又比GA-PSO算法的能耗高很多，這主要因為基于貪心策略的排序優(yōu)化算法缺少全局的考慮，只是局部選擇最優(yōu)路徑，因此無法從整體上優(yōu)化網(wǎng)絡(luò)的能耗。GA-PSO利用粒子的不斷變遷，通過群智能從整體上優(yōu)化網(wǎng)絡(luò)路由，從而降低網(wǎng)絡(luò)能耗，從圖 3可以看出，網(wǎng)絡(luò)規(guī)模越大，GA-PSO算法較另外兩種算法的能耗優(yōu)勢越明顯，同時隨著網(wǎng)絡(luò)規(guī)模的增大，GA-PSO算法的網(wǎng)絡(luò)能耗增長緩慢，表現(xiàn)出對良好的均衡能力，能耗具有穩(wěn)定性。雖然從圖2上看，在網(wǎng)絡(luò)規(guī)模為350時，GA-PSO的耗時比OSPF多14%左右，但圖3所示節(jié)能32%左右。

圖3 不同網(wǎng)絡(luò)規(guī)模下3種算法的能耗

4.2.2 不同網(wǎng)絡(luò)需求的影響

為了進一步評價算法性能，本文在200個網(wǎng)絡(luò)節(jié)點的前提下，考慮不同網(wǎng)絡(luò)負載時的能耗和鏈路平均利用率。

（1）能耗

從圖 4可以看出，隨著網(wǎng)絡(luò)負載的增加，OSPF算法的能耗在持續(xù)增加，并且明顯高于另外兩種算法?；谪澬牟呗缘乃惴?，雖然能耗也在增加，但增長速度較 OSPF明顯放緩。GA-PSO算法在負載不大時，并不明顯優(yōu)于基于貪心策略的算法，但負載越高，GA-PSO的優(yōu)勢越明顯，這主要還是由于基于貪心策略的算法缺少整體觀，在負載較小時缺點不明顯，但一旦負載變大，則將十分嚴(yán)重地影響整個網(wǎng)絡(luò)的能耗。

圖4 不同網(wǎng)絡(luò)負載下3種算法的能耗

（2）網(wǎng)絡(luò)資源利用率

從圖5可以看出，本文算法使得鏈路平均利用率保持在70%左右，并且隨著負載的增加鏈路平均利用率波動不大，說明有較好的負載均衡效果和穩(wěn)定性。OSPF算法盡量選擇最短路徑，會使得個別路徑負載過高，鏈路平均利用率偏低。基于貪心策略的算法，比傳統(tǒng)OSPF有了顯著提高，但在全局負載均衡方面仍然遜色于GA-PSO算法。

圖5 不同網(wǎng)絡(luò)負載下3種算法的網(wǎng)絡(luò)資源利用率

5 結(jié)束語

本文通過對當(dāng)前主要應(yīng)用場景的分析和對網(wǎng)絡(luò)切片的算法研究，提出基于GA-PSO優(yōu)化的網(wǎng)絡(luò)切片編排算法，該算法的特點是：借鑒GA算法中雜交和變異的思想，對傳統(tǒng)的PSO算法進行了改進，將PSO的群智能特點應(yīng)用于網(wǎng)絡(luò)子圖的優(yōu)化問題，使得算法的全局搜索性能得到了實質(zhì)的提高，充分發(fā)揮了SDN架構(gòu)的集中控制優(yōu)越性。實驗數(shù)據(jù)表明，該算法對于大規(guī)模網(wǎng)絡(luò)的高負載流量的優(yōu)化有著良好的效果。

[1]尤肖虎, 潘志文, 高西奇, 等. 5G移動通信發(fā)展趨勢與若干關(guān)鍵技術(shù)[J]. 中國科學(xué):信息科學(xué), 2014(5): 551-563. YOU X H, PAN Z W, GAO X Q, et al. The 5G mobile communication: the development trends and its emerging key techniques[J]. Scientia Sinica(Informationis), 2014(5): 551-563.

[2]SAMA M R, AN X, WEI Q, et al. Reshaping the mobile core network via function decomposition and network slicing for the 5G era[C]//2016 Wireless Communications and Networking Conference Workshops (WCNCW), April 3-6, 2016, Doha, Qatar. New Jersey: IEEE Press, 2016: 90-96.

[3]PRIES R, MORPER H J, GALAMBOSI N, et al. Network as a service-a demo on 5G Network slicing[C]//2016 28th International Teletraffic Congress (ITC 28), Sept 12-16, 2016, Würzburg, Germany. New Jersey: IEEE Press, 2016: 209-211.

[4]GIANNOULAKIS I, KAFETZAKIS E, XYLOURIS G, et al. On the applications of efficient NFV management towards 5G networking[C]//2014 1st International Conference on 5G for Ubiquitous Connectivity (5GU), Nov 26-28, 2014, Akaslompolo, Finland. New Jersey: IEEE Press, 2014: 1-5.

[5]KSENTINI A, BAGAA M, TALEB T. On using SDN in 5G: the controller placement problem[C]//GLOBECOM 2016, IEEE Global Communications Conference, Exhibition and Industry Forum, December 4-8, 2016, Washington, USA. New Jersey: IEEE Press, 2016: 1.

[6]ZHANG J, XIE W, YANG F. An architecture for 5G mobile network based on SDN and NFV[C]//6th International Conference on Wireless, Mobile and Multi-Media (ICWMMN 2015), Nov 20-23, 2015, Beijing, China. New Jersey: IEEE Press, 2015: 87-92.

[7]DEMESTICHAS P, GEORGAKOPOULOS A, KARVOUNAS D, et al. 5G on the horizon: key challenges for the radio-access network[J]. IEEE Vehicular Technology Magazine, 2013, 8(3): 47-53.

[8]NAKAO A, DU P, KIRIHA Y, et al. End-to-end network slicing for 5G mobile networks[J]. Journal of Information Processing, 2017(25): 153-163.

[9]NGMN. 5G white paper[R]. 2015.

[10]KOERNER M, KAO O. Multiple service load-balancing with OpenFlow[C]//2012 IEEE 13th International Conference on High Performance Switching and Routing (HPSR), June 24-27, 2012, Belgrade, Serbia. New Jersey: IEEE Press, 2012: 210-214.

[11]JAIN S, KUMAR A, MANDAL S, et al. B4: Experience with a globally-deployed software defined WAN[J]. Computer Communication Review, 2013, 43(4): 3-14.

[12]吳一娜. 基于切片劃分的網(wǎng)絡(luò)資源控制機制的研究與實現(xiàn)[D]. 南京: 東南大學(xué), 2016. WU Y N. Research and implementation on resource control mechanism based on network slicing[D]. Nanjing: Southeast University, 2016.

[13]KENNEDY J. Particle swarm optimization[M]//Encyclopedia of machine learning. New York: Springer US, 2011: 760-766.

[14]DEB K, PRATAP A, AGARWAl S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[15]MEDINA A, TAFT N, SALAMATIAN K, et al. Traffic matrix estimation: existing techniques and new directions[J]. ACM SIGCOMM Computer Communication Review, 2002, 32(4): 161-174.

[16]SOULE A, LAKHINA A, TAFT N, et al. Traffic matrices: balancing measurements, inference and modeling[C]//ACM SIGMETRICS Performance Evaluation Review, June 6-10, 2005, Banff, Alberta, Canada. New York: ACM Press, 2005: 362-373.

An orchestration algorithm of 5G network slicing

ZHOU Heng, CHANG Zhixian, YANG Wujun, GUO Juan School of Communications and Information Engineering,
Xi’an University of Posts & Telecommunications, Xi’an 710121, China

The network slicing is an important technology for 5G to implement the on-demand networking based on SDN/NFV network architecture. According to the main scene of 5G, a network segmentation algorithm based on GA-PSO was proposed in SDN/NFV architecture. The merit of quick converging to the global optimal solution was used to design the evaluation function of the network slicing. Using the ability of the fast random search of genetic algorithm, the updating and optimization of the network slices could be realized by using the particle swarm to chase the local optimal solution and the global optimal solution. The simulation results show that the algorithm can realize the personalized creation of multi-service scene network slices, and give full play to the advantages of SDN centralized control mode. It can reduce the energy consumption of the network and improve the utilization rate of cyber source at the same time.

5G, network slicing, genetic algorithm-particle swarm optimization, orchestration

s：The National Natural Science Foundation of China(No.61501371), Industrial Research Project of Science and Technology Department of Shaanxi Province(No.2014K09-14) , International Cooperation Project of Shaanxi Province Science and Technology Department(No.2014KW02-02), Education Department Foundation of Shaanxi Province（No.16JK1685）