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

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

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

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

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

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

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

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

1 引言

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

一個(gè)網(wǎng)絡(luò)切片是 5G網(wǎng)絡(luò)中的一個(gè)端到端虛擬網(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è)施層從物理層面描述維持一個(gè)網(wǎng)絡(luò)切片運(yùn)行所需要的網(wǎng)絡(luò)元素和資源，包括計(jì)算資源和網(wǎng)絡(luò)資源[7]。

2 基于NS劃分的路由模型

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

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

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

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

3 GA-PSO切片生成算法

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

3.1 PSO算法

粒子群優(yōu)化（particle swarm optimization，PSO），是由Kennedy J和Eberhart R C等人[13]于1995年開發(fā)的一種群智能算法。在PSO算法中每個(gè)優(yōu)化問題的解都是搜索空間的一只鳥，被抽象為沒有質(zhì)量和體積的粒子，粒子的位置代表被優(yōu)化空間在搜索空間中的潛在解，所有粒子都有一個(gè)評(píng)價(jià)函數(shù)決定的適應(yīng)值。每個(gè)粒子根據(jù)自身和周圍粒子的經(jīng)驗(yàn)在搜索空間中調(diào)整自己的位置和速度。基礎(chǔ)的PSO算法定義了兩個(gè)非常重要的參數(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之間均勻分布的隨機(jī)數(shù)。

3.2 GA-PSO 算法

3.2.1 算法的基本思想

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

算法的基本思想是根據(jù)3GPP提出的3種主要應(yīng)用場景得到兩類原始粒子，再由這兩類原始基本粒子進(jìn)一步初始化得到一定數(shù)量的基本粒子，形成初始的種群。每個(gè)粒子代表一個(gè)拓?fù)渥訄D，評(píng)價(jià)每個(gè)粒子的適應(yīng)度，存儲(chǔ)當(dāng)前個(gè)體最優(yōu)的粒子和全局最優(yōu)粒子，按照雜交和變異的思想對(duì)子圖進(jìn)行更新優(yōu)化，產(chǎn)生新的拓?fù)渥訄D。粒子群追隨當(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（點(diǎn)到點(diǎn)流量矩陣[15,16]）流量矩陣表示網(wǎng)絡(luò)中源—目的（original-destination，OD）節(jié)點(diǎn)之間每個(gè)流的分布情況，流量矩陣的維數(shù)等于網(wǎng)絡(luò)中所有OD流的數(shù)目，它從全局的觀點(diǎn)來描述整個(gè)網(wǎng)絡(luò)的數(shù)據(jù)流動(dòng)情況，是網(wǎng)絡(luò)決策的重要依據(jù)。點(diǎn)到點(diǎn)流量矩陣（point-to-point traffic matrix）表示源（O）節(jié)點(diǎn)和目的（D）節(jié)點(diǎn)之間的流量 V（O, D），它表示網(wǎng)絡(luò)中所有OD節(jié)點(diǎn)對(duì)間的流量，描述了網(wǎng)絡(luò)流量在各個(gè)OD節(jié)點(diǎn)對(duì)間的分布情況。

定義3（低時(shí)延網(wǎng)絡(luò)切片）能夠?yàn)樘囟ǖ腝oS流量類提供最小時(shí)延保障的一個(gè)虛擬邏輯網(wǎng)絡(luò)，由一系列網(wǎng)絡(luò)功能、運(yùn)行這些網(wǎng)絡(luò)功能的資源以及這些網(wǎng)絡(luò)功能特定的配置所組成。

定義4（高帶寬網(wǎng)絡(luò)切片）能夠?yàn)樘囟ǖ腝oS流量類提供最小帶寬保障的一個(gè)虛擬邏輯網(wǎng)絡(luò)。

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

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

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

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

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

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

評(píng)價(jià)一個(gè)粒子的適應(yīng)度是根據(jù)它所代表的切片的傳輸參數(shù)做出的，也就是說粒子的適應(yīng)度即NS的適應(yīng)度。基于上述性能參數(shù)歸一化，使得對(duì)NS的量化分析變得可行，同時(shí)考慮到5G應(yīng)用場景的分類和傳輸參數(shù)的選擇以及對(duì)微小變化的反映，本文以指數(shù)函數(shù)為基礎(chǔ)設(shè)計(jì)的粒子適應(yīng)度評(píng)價(jià)函數(shù)如下：

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

3.2.4 基本粒子更新

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

（1）子圖雜交

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

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

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

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

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

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

步驟6 輸出這個(gè)雜交后的新子圖。

（2）子圖變異

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

步驟1 初始化一個(gè)隨機(jī)值。

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

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

步驟4 輸出切片。

3.2.5 算法實(shí)施步驟

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

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

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

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

步驟4 記錄步驟 3適應(yīng)度最高的切片，為局部最優(yōu)粒子 Gpb，同時(shí)也是全局最優(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)計(jì)算種群粒子的適應(yīng)度，更新局部最優(yōu)粒子 Gpb，如果當(dāng)前的局部最優(yōu)粒子 Gpb的適應(yīng)值高于當(dāng)前的全局最優(yōu)粒子 Gg,b，則更新全局最優(yōu)粒子；否則最優(yōu)解控制計(jì)數(shù)器加1。

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

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

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)環(huán)境

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

圖1 實(shí)驗(yàn)環(huán)境拓?fù)涫疽?/p>

4.2 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

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

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

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

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

（2）能耗

隨著未來移動(dòng)互聯(lián)網(wǎng)和物聯(lián)網(wǎng)的發(fā)展，大量網(wǎng)絡(luò)設(shè)備接入網(wǎng)絡(luò)，節(jié)能問題成為不可回避的重要問題。因此，通過對(duì)比3種算法在不同網(wǎng)絡(luò)規(guī)模下的能耗，進(jìn)一步證明本文算法的有效性和實(shí)用性。從圖3可以看出，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，能耗都在持續(xù)增加。傳統(tǒng)的 OSPF算法，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，能耗急劇上升。同時(shí)，基于貪心策略的排序優(yōu)化算法，能耗雖然也在持續(xù)升高但明顯低于OSPF算法，但又比GA-PSO算法的能耗高很多，這主要因?yàn)榛谪澬牟呗缘呐判騼?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)勢越明顯，同時(shí)隨著網(wǎng)絡(luò)規(guī)模的增大，GA-PSO算法的網(wǎng)絡(luò)能耗增長緩慢，表現(xiàn)出對(duì)良好的均衡能力，能耗具有穩(wěn)定性。雖然從圖2上看，在網(wǎng)絡(luò)規(guī)模為350時(shí)，GA-PSO的耗時(shí)比OSPF多14%左右，但圖3所示節(jié)能32%左右。

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

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

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

（1）能耗

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

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

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

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

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

5 結(jié)束語

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

[1]尤肖虎, 潘志文, 高西奇, 等. 5G移動(dòng)通信發(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ò)資源控制機(jī)制的研究與實(shí)現(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）

TN929.5

A

10.11959/j.issn.1000?0801.2017218

周恒（1996?），男，西安郵電大學(xué)通信與信息工程學(xué)院在讀，主要研究方向?yàn)閷拵o線通信和SDN。

暢志賢（1981?），女，博士，西安郵電大學(xué)通信與信息工程學(xué)院講師，主要研究方向?yàn)閷拵o線通信與SDN技術(shù)。

楊武軍（1969?），男，西安郵電大學(xué)通信與信息工程學(xué)院通信工程系主任、副教授，主要研究方向?yàn)橐苿?dòng)互聯(lián)網(wǎng)與SDN。

郭娟（1973?），女，西安郵電大學(xué)通信與信息工程學(xué)院通信工程系副主任、副教授，主要研究方向?yàn)閷拵ㄐ啪W(wǎng)與SDN。

2017?03?27；

2017?07?06

暢志賢，changzhixian@xupt.edu.cn

國家自然科學(xué)基金資助項(xiàng)目(No.61501371)；陜西省科技廳工業(yè)攻關(guān)項(xiàng)目 (No.2014K09-14)；陜西省科技廳國際合作項(xiàng)目(No.2014KW02-02)；陜西省教育廳項(xiàng)目(No.16JK1685)