網(wǎng)絡(luò)切片下基于遺傳算法的虛擬網(wǎng)資源分配算法

王井龍

中國(guó)電信股份有限公司

0 引言

隨著5G網(wǎng)絡(luò)的快速建設(shè)和應(yīng)用，各種基于5G網(wǎng)絡(luò)的業(yè)務(wù)和應(yīng)用快速增加。為提高基礎(chǔ)網(wǎng)絡(luò)的資源利用率，節(jié)約網(wǎng)絡(luò)建設(shè)的成本，網(wǎng)絡(luò)切片技術(shù)已成為網(wǎng)絡(luò)運(yùn)營(yíng)商普遍采用的關(guān)鍵技術(shù)。在網(wǎng)絡(luò)切片環(huán)境下，傳統(tǒng)的基礎(chǔ)網(wǎng)絡(luò)被劃分為底層網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)兩個(gè)部分。其中，底層網(wǎng)絡(luò)包括底層節(jié)點(diǎn)和底層鏈路。虛擬網(wǎng)絡(luò)服務(wù)提供商通過(guò)租用底層網(wǎng)絡(luò)的資源，構(gòu)建虛擬網(wǎng)絡(luò)，為用戶(hù)提供特定的業(yè)務(wù)和服務(wù)。在網(wǎng)絡(luò)切片環(huán)境下，如何提高底層網(wǎng)絡(luò)資源的利用率是一個(gè)重要的研究?jī)?nèi)容。

通過(guò)對(duì)已有研究分析可知，已有研究已經(jīng)采取了較多的策略，用于提高底層網(wǎng)絡(luò)的資源利用率。但是，已有研究主要采用貪婪或隨機(jī)的策略，基于網(wǎng)絡(luò)特性進(jìn)行資源分配，這種資源分配策略容易導(dǎo)致算法獲得的解不是全局最優(yōu)解。另外，部分智能化算法已被應(yīng)用到資源分配，但是這些算法沒(méi)有利用網(wǎng)絡(luò)特征進(jìn)行資源分配，給算法的運(yùn)行帶來(lái)較大的開(kāi)銷(xiāo)，也較難獲得全局最優(yōu)解。為解決此問(wèn)題，本文首先分析網(wǎng)絡(luò)特征，其次基于網(wǎng)絡(luò)特征采取遺傳算法進(jìn)行資源分配。本文首先為需求資源較多的虛擬網(wǎng)絡(luò)分配資源，這樣可以降低因底層網(wǎng)絡(luò)資源缺少導(dǎo)致資源分配失敗的概率。其次，采用遺傳算法，為每個(gè)虛擬網(wǎng)請(qǐng)求智能化求解最優(yōu)的資源分配算法。

1 問(wèn)題描述

網(wǎng)絡(luò)切片環(huán)境下，為了提高底層網(wǎng)絡(luò)的資源利用率，需要根據(jù)底層網(wǎng)絡(luò)拓?fù)涞奶攸c(diǎn)和虛擬網(wǎng)請(qǐng)求的資源特征，實(shí)現(xiàn)資源的高效率分配。本文使用GS=(NS,ES)表示底層網(wǎng)絡(luò)拓?fù)洹S=(NS,ES)包括底層節(jié)點(diǎn)集合NS和底層鏈路集合ES。底層節(jié)點(diǎn)集合NS由底層節(jié)點(diǎn)構(gòu)成，每個(gè)底層節(jié)點(diǎn)包括計(jì)算資源屬性和位置屬性，分別用和表示。底層鏈路集合ES由底層鏈路構(gòu)成，每條底層鏈路的屬性是帶寬資源，使用表示。在虛擬網(wǎng)拓?fù)浞矫?，使用GV=(NV,EV)表示虛擬網(wǎng)絡(luò)拓?fù)?。GV=(NV,EV)由虛擬節(jié)點(diǎn)集合NV和虛擬鏈路集合EV構(gòu)成。每個(gè)虛擬節(jié)點(diǎn)包括計(jì)算資源屬性和位置屬性，分別使用表示。在底層節(jié)點(diǎn)為虛擬節(jié)點(diǎn)分配資源時(shí)，需要同時(shí)滿(mǎn)足計(jì)算資源屬性和位置屬性的限制。在計(jì)算資源屬性限制方面，底層節(jié)點(diǎn)為虛擬節(jié)點(diǎn)分配的計(jì)算資源容量需要滿(mǎn)足虛擬節(jié)點(diǎn)的計(jì)算資源需求量。在位置屬性的限制方面，底層節(jié)點(diǎn)的位置需要在虛擬節(jié)點(diǎn)位置屬性的半徑范圍內(nèi)。

通過(guò)對(duì)已有虛擬網(wǎng)資源分配算法分析可知，對(duì)于虛擬節(jié)點(diǎn)的資源分配，虛擬網(wǎng)資源分配失敗的原因主要是底層網(wǎng)絡(luò)的節(jié)點(diǎn)資源不能滿(mǎn)足虛擬節(jié)點(diǎn)資源需求。為解決此問(wèn)題，本文將優(yōu)先為資源需求較大的虛擬網(wǎng)絡(luò)分配資源，從而降低因底層節(jié)點(diǎn)資源缺少導(dǎo)致的資源分配失敗問(wèn)題。

2 基于遺傳算法的虛擬網(wǎng)最優(yōu)資源分配算法

根據(jù)遺傳算法的基本原理，如果將遺傳算法應(yīng)用于虛擬網(wǎng)資源分配問(wèn)題，需要解決染色體編碼、種群初始化、適應(yīng)度函數(shù)定義、選擇操作定義、交叉操作定義、變異操作定義6個(gè)關(guān)鍵問(wèn)題。

2.1 遺傳算法參數(shù)分析

在染色體編碼方面，將每個(gè)虛擬網(wǎng)的映射方案建模為一個(gè)染色體。對(duì)于虛擬網(wǎng)，染色體編碼表示為表示虛擬網(wǎng)的D個(gè)虛擬節(jié)點(diǎn)所映射的底層網(wǎng)絡(luò)節(jié)點(diǎn)的編號(hào)。

在種群初始化方面，根據(jù)網(wǎng)絡(luò)規(guī)模，采用種群初始化方法生成初始種群，作為算法的起始解。初始化種群的規(guī)模與虛擬網(wǎng)的規(guī)模相關(guān)，取值為虛擬網(wǎng)包含的虛擬節(jié)點(diǎn)數(shù)量的n倍。本文初始化種群的規(guī)模取10倍。例如，當(dāng)虛擬網(wǎng)絡(luò)包括10個(gè)虛擬節(jié)點(diǎn)，初始化種群的數(shù)量為100個(gè)。

在適應(yīng)度函數(shù)定義方面，當(dāng)算法完成一個(gè)虛擬網(wǎng)資源分配后，底層網(wǎng)絡(luò)開(kāi)銷(xiāo)與算法的優(yōu)劣相關(guān)。當(dāng)算法比較優(yōu)化時(shí)，可以減少底層網(wǎng)絡(luò)資源的開(kāi)銷(xiāo)。所以，本文將底層網(wǎng)絡(luò)開(kāi)銷(xiāo)與適應(yīng)度函數(shù)進(jìn)行關(guān)聯(lián)。由于優(yōu)化的目標(biāo)是選擇適應(yīng)度值盡可能大的染色體，為便于計(jì)算，當(dāng)映射成功虛擬網(wǎng)后，本文將映射成功虛擬網(wǎng)的適應(yīng)度函數(shù)定義為底層網(wǎng)絡(luò)開(kāi)銷(xiāo)的倒數(shù)，如公式（4）所示。根據(jù)公式（4）的定義可知，適應(yīng)度取值越大，說(shuō)明底層網(wǎng)絡(luò)的開(kāi)銷(xiāo)越小。

在選擇操作定義方面，為了優(yōu)化和更新種群，需要從已有種群中選擇部分較優(yōu)化的個(gè)體加入到新種群。在選擇個(gè)體時(shí)，本文按照個(gè)體的適應(yīng)度值進(jìn)行降序排列，選擇適應(yīng)度值較大的個(gè)體加入新的種群中。在交叉操作定義方面，從較優(yōu)化的個(gè)體中選擇兩個(gè)個(gè)體作為交叉操作中的父代，之后將兩個(gè)父代進(jìn)行部分替換，替換后根據(jù)同一虛擬網(wǎng)不能有兩個(gè)虛擬節(jié)點(diǎn)映射到相同底層節(jié)點(diǎn)的約束，對(duì)兩個(gè)新個(gè)體進(jìn)行調(diào)整，得到新的兩個(gè)個(gè)體。在變異操作定義方面，從較優(yōu)化的個(gè)體中選擇一個(gè)個(gè)體作為變異操作的父代，之后將父代中的底層節(jié)點(diǎn)編號(hào)進(jìn)行互換，從而生成新的個(gè)體。

2.2 資源分配算法

本文提出的網(wǎng)絡(luò)切片下基于遺傳算法的虛擬網(wǎng)最優(yōu)資源分配算法（Virtual Network Resource Allocation Algorithm based on Genetic Algorithm，VNRAAoGA）如表1所示。該算法包括虛擬網(wǎng)的節(jié)點(diǎn)資源需求評(píng)估及降序排列、對(duì)于集合中的每個(gè)虛擬網(wǎng)請(qǐng)求分配資源兩個(gè)過(guò)程。虛擬網(wǎng)的節(jié)點(diǎn)資源需求評(píng)估及降序排列步驟，主要用于分析虛擬網(wǎng)節(jié)點(diǎn)資源需求的數(shù)量。如果虛擬網(wǎng)需求的節(jié)點(diǎn)資源較多，需要優(yōu)先分配資源，從而防止部分虛擬節(jié)點(diǎn)因資源需求太大不能被滿(mǎn)足導(dǎo)致資源分配失敗的情況發(fā)生。

表1 基于遺傳算法的虛擬網(wǎng)資源分配算法

3 性能分析

實(shí)驗(yàn)環(huán)境方面，使用GT-ITM工具生成網(wǎng)絡(luò)拓?fù)?。生成的網(wǎng)絡(luò)拓?fù)浒ǖ讓泳W(wǎng)絡(luò)拓?fù)浜吞摂M網(wǎng)絡(luò)拓?fù)洹５讓泳W(wǎng)絡(luò)拓?fù)浒?00個(gè)底層網(wǎng)絡(luò)節(jié)點(diǎn)。底層網(wǎng)絡(luò)的網(wǎng)絡(luò)鏈路由任意兩個(gè)節(jié)點(diǎn)之間以0.3的概率連接生成。每個(gè)底層網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算資源、每條鏈路的帶寬資源服從[15，35]的均勻分布。虛擬網(wǎng)絡(luò)拓?fù)浒ǖ奶摂M節(jié)點(diǎn)服從[3，10]的均勻分布。虛擬網(wǎng)絡(luò)的虛擬鏈路由任意兩個(gè)虛擬節(jié)點(diǎn)之間以0.2的概率連接生成。每個(gè)虛擬網(wǎng)絡(luò)節(jié)點(diǎn)的計(jì)算資源服從[1，3]的均勻分布。每條虛擬鏈路的帶寬資源服從[1，6]的均勻分布。

實(shí)驗(yàn)中使用固定的時(shí)間段進(jìn)行網(wǎng)絡(luò)環(huán)境更新和生成虛擬網(wǎng)資源分配請(qǐng)求。實(shí)驗(yàn)中生成的虛擬網(wǎng)資源分配請(qǐng)求數(shù)量為2 000個(gè)。每個(gè)虛擬網(wǎng)請(qǐng)求的到達(dá)服從2個(gè)時(shí)間單位的泊松分布。每個(gè)虛擬網(wǎng)的生命時(shí)長(zhǎng)為12個(gè)時(shí)間單位。實(shí)驗(yàn)運(yùn)行的總時(shí)長(zhǎng)為3 000個(gè)時(shí)間單位。

在算法性能分析方面，將本文算法VNRAAoGA與基于貪婪策略的虛擬網(wǎng)資源分配算法（Virtual Network Resource Allocation Algorithm based on Greedy Strategy，VNRAAoGS）進(jìn)行比較。VNRAAoGS算法在為每個(gè)虛擬網(wǎng)分配資源時(shí)，采用隨機(jī)搜索策略，查找最優(yōu)的資源分配策略。為驗(yàn)證算法的性能，實(shí)驗(yàn)中從底層網(wǎng)絡(luò)開(kāi)銷(xiāo)、底層網(wǎng)絡(luò)收益、虛擬網(wǎng)絡(luò)映射成功率3個(gè)維度對(duì)兩個(gè)算法進(jìn)行比較。在底層網(wǎng)絡(luò)開(kāi)銷(xiāo)對(duì)比分析時(shí)，考慮到分配給虛擬網(wǎng)的資源之和較大，不便于分析。本文采取max-min歸一化方法將底層網(wǎng)絡(luò)資源開(kāi)銷(xiāo)進(jìn)行歸一化處理，為了保證資源開(kāi)銷(xiāo)大的資源分配策略在歸一化后的取值仍然較大，在采用max-min歸一化方法時(shí)，使用底層網(wǎng)絡(luò)開(kāi)銷(xiāo)值減去最小的開(kāi)銷(xiāo)值作為歸一化方法的分子部分。

底層網(wǎng)絡(luò)開(kāi)銷(xiāo)比較結(jié)果如圖1所示。X軸表示虛擬網(wǎng)請(qǐng)求的數(shù)量從100個(gè)增加到600個(gè)。Y軸表示底層網(wǎng)絡(luò)開(kāi)銷(xiāo)的取值。從圖可知，隨著虛擬網(wǎng)請(qǐng)求數(shù)量的增加，兩種算法下底層網(wǎng)絡(luò)的開(kāi)銷(xiāo)快速增加。這是因?yàn)樘摂M網(wǎng)請(qǐng)求數(shù)量的增加，需要底層網(wǎng)絡(luò)為其分配的資源數(shù)量快速增加。比較兩種算法，不同的虛擬網(wǎng)請(qǐng)求數(shù)量下，本文算法的底層網(wǎng)絡(luò)開(kāi)銷(xiāo)較小。這說(shuō)明本文算法為虛擬網(wǎng)分配了更加優(yōu)化的底層網(wǎng)絡(luò)資源，從而減少了底層網(wǎng)絡(luò)的開(kāi)銷(xiāo)。

圖1 底層網(wǎng)絡(luò)開(kāi)銷(xiāo)比較

底層網(wǎng)絡(luò)收益比較的結(jié)果如圖2所示。圖中，X軸表示虛擬網(wǎng)資源分配算法的運(yùn)行時(shí)長(zhǎng)。Y軸表示底層網(wǎng)絡(luò)的收益。從圖可知，隨著虛擬網(wǎng)資源分配算法的運(yùn)行時(shí)間增加，兩個(gè)算法下獲得的底層網(wǎng)絡(luò)收益都在降低并趨于穩(wěn)定。這是因?yàn)殡S著算法運(yùn)行時(shí)間增加，底層網(wǎng)絡(luò)的剩余資源越來(lái)越少，不能滿(mǎn)足新的虛擬網(wǎng)請(qǐng)求。同時(shí)，由于底層網(wǎng)絡(luò)的剩余資源規(guī)模也逐漸變小，不能滿(mǎn)足大容量的資源請(qǐng)求。兩個(gè)算法的性能比較方面，本文算法下底層網(wǎng)絡(luò)獲得了較大的收益，說(shuō)明本文算法可以提高虛擬網(wǎng)的資源分配成功率，從而提升底層網(wǎng)絡(luò)的收益。

圖2 底層網(wǎng)絡(luò)收益比較

虛擬網(wǎng)絡(luò)映射成功率比較結(jié)果如圖3所示。X軸表示虛擬網(wǎng)資源分配算法的運(yùn)行時(shí)長(zhǎng)。Y軸表示虛擬網(wǎng)映射成功率。從圖可知，隨著虛擬網(wǎng)算法運(yùn)行時(shí)間增加，兩個(gè)算法的虛擬網(wǎng)映射成功率都趨于穩(wěn)定。相對(duì)于傳統(tǒng)算法，在本文算法下，虛擬網(wǎng)映射成功率較高，表明本文算法為虛擬網(wǎng)分配了比較優(yōu)化的底層網(wǎng)絡(luò)資源，從而使更多的虛擬網(wǎng)能夠映射成功。

圖3 虛擬網(wǎng)絡(luò)映射成功率比較

4 結(jié)束語(yǔ)

網(wǎng)絡(luò)切片技術(shù)是提升網(wǎng)絡(luò)資源利用率的關(guān)鍵技術(shù)之一。為合理利用底層網(wǎng)絡(luò)資源，虛擬網(wǎng)絡(luò)的資源分配問(wèn)題成為研究重點(diǎn)。為降低底層網(wǎng)絡(luò)開(kāi)銷(xiāo)、提升虛擬網(wǎng)資源分配的成功率，本文提出了基于遺傳算法的虛擬網(wǎng)資源分配算法。在實(shí)驗(yàn)部分，從底層網(wǎng)絡(luò)的開(kāi)銷(xiāo)、底層網(wǎng)絡(luò)的收益、虛擬網(wǎng)映射成功率3個(gè)方面，將本文算法與傳統(tǒng)算法進(jìn)行比較，驗(yàn)證了本文算法較好地提升了虛擬網(wǎng)資源分配算法的性能?？紤]到網(wǎng)絡(luò)切片環(huán)境下虛擬網(wǎng)業(yè)務(wù)的優(yōu)先級(jí)越來(lái)越重要，為了保證高優(yōu)先級(jí)業(yè)務(wù)的虛擬網(wǎng)能夠優(yōu)先獲得底層網(wǎng)絡(luò)資源，需要在本文研究的基礎(chǔ)上增加虛擬網(wǎng)優(yōu)先級(jí)因素。下一步工作將基于本文研究成果，研究基于虛擬網(wǎng)業(yè)務(wù)優(yōu)先級(jí)的資源分配算法，從而提升高優(yōu)先級(jí)虛擬網(wǎng)的服務(wù)質(zhì)量。