基于GSA算法的WVN資源映射數(shù)學(xué)模型

王曉霞，鄭大釗

(齊齊哈爾大學(xué)理學(xué)院，黑龍江齊齊哈爾161005)

1 引言

虛擬網(wǎng)絡(luò)資源映射是網(wǎng)絡(luò)虛擬化技術(shù)的重要部分，虛擬網(wǎng)絡(luò)資源映射是將移動(dòng)網(wǎng)絡(luò)中的虛擬網(wǎng)絡(luò)映射至物理網(wǎng)絡(luò)中，依據(jù)固定映射算法分配移動(dòng)網(wǎng)絡(luò)物理資源，令網(wǎng)絡(luò)資源實(shí)現(xiàn)良好分配[1-3]。通常將映射成功率、收益與開銷設(shè)置為網(wǎng)絡(luò)資源映射目標(biāo)。目前，網(wǎng)絡(luò)結(jié)構(gòu)存在較大缺陷，容易出現(xiàn)網(wǎng)絡(luò)僵化問題，嚴(yán)重影響互聯(lián)網(wǎng)技術(shù)發(fā)展。網(wǎng)絡(luò)缺少地址資源、無法充分利用網(wǎng)絡(luò)資源等情況嚴(yán)重影響了網(wǎng)絡(luò)發(fā)展。

眾多研究學(xué)者提出資源預(yù)留等技術(shù)雖對(duì)資源利用問題有所改善，但仍無法從根本解決網(wǎng)絡(luò)僵化問題。朱國(guó)暉[4]等人提出一種基于兩次優(yōu)先級(jí)排序的虛擬網(wǎng)絡(luò)映射算法，首次排序中，計(jì)算請(qǐng)求優(yōu)先級(jí)，判斷虛擬網(wǎng)絡(luò)映射順序，二次排序中，依據(jù)鏈路權(quán)重獲取優(yōu)先級(jí)，結(jié)合兩次排序?qū)ψ罴延成渎窂竭M(jìn)行計(jì)算。實(shí)驗(yàn)結(jié)果表明，該算法有效降低了網(wǎng)絡(luò)請(qǐng)求的等待時(shí)間，但是存在剩余帶寬和請(qǐng)求接受率較低的問題。王明[5]等人分別將兩次優(yōu)先級(jí)排序方法以及元胞遺傳機(jī)制應(yīng)用于虛擬網(wǎng)絡(luò)映射中，但是該方法存在底層鏈路利用率和部署成本較高的缺陷。

針對(duì)傳統(tǒng)方法存在的問題，研究基于GSA算法的無線虛擬網(wǎng)絡(luò)資源映射數(shù)學(xué)模型，GSA算法是遺傳算法與模擬退火算法結(jié)合的算法，廣泛應(yīng)用于求解最優(yōu)化問題中。建立無線虛擬網(wǎng)絡(luò)資源映射數(shù)學(xué)模型，利用GSA算法實(shí)現(xiàn)模型高效求解，獲取最優(yōu)無線虛擬網(wǎng)絡(luò)資源映射結(jié)果。

2 無線虛擬網(wǎng)絡(luò)資源映射數(shù)學(xué)模型

2.1 網(wǎng)絡(luò)模型

1)物理網(wǎng)絡(luò)

選取帶權(quán)無向圖GS=(NS，LS)表示物理網(wǎng)絡(luò)，其中，NS表示物理節(jié)點(diǎn)集合，LS表示鏈路集合。利用節(jié)點(diǎn)位置、信任度以及CPU資源表示物理節(jié)點(diǎn)nS∈NS的屬性。loc(ns)與cpu(ns)分別為節(jié)點(diǎn)地理位置以及可用CPU資源；二維節(jié)點(diǎn)坐標(biāo)用(xs，ys)表示；trl(ns)為節(jié)點(diǎn)信任度等級(jí)，trd(ns)為節(jié)點(diǎn)信任度需求。用帶寬lS∈LS表示物理鏈路屬性，可用帶寬資源用b(ls)表示。

2)虛擬網(wǎng)絡(luò)請(qǐng)求

用VNR(t)=(Gv，t，td)與GV=(NV，LV)分別表示時(shí)間為t時(shí)虛擬網(wǎng)絡(luò)請(qǐng)求以及虛擬網(wǎng)絡(luò)拓?fù)?，其中，td與NV分別表示虛擬網(wǎng)絡(luò)生存時(shí)間以及虛擬節(jié)點(diǎn)集合，LV表示虛擬鏈路集合。cpu(nv)表示虛擬節(jié)點(diǎn)資源需求，trl(nv)與trd(nv)分別表示虛擬節(jié)點(diǎn)信任度等級(jí)以及信任度需求；D(nv)與loc(nv)分別表示可最遠(yuǎn)被映射至位置需求的距離以及虛擬節(jié)點(diǎn)地理位置需求，虛擬鏈路帶寬資源需求用b(lv)表示。

3)安全虛擬網(wǎng)絡(luò)映射

2.2 映射目標(biāo)

底層物理網(wǎng)絡(luò)在無線虛擬網(wǎng)絡(luò)資源映射過程中需滿足成本最小需求，實(shí)現(xiàn)最大化虛擬網(wǎng)絡(luò)請(qǐng)求的映射，增加物理網(wǎng)絡(luò)供應(yīng)商收益以及資源利用率[6]。將虛擬網(wǎng)絡(luò)請(qǐng)求接受率、物理網(wǎng)絡(luò)映射收益以及物理網(wǎng)絡(luò)映射成本作為無線虛擬網(wǎng)絡(luò)資源映射目標(biāo)。

1)映射成本以及映射收益

時(shí)間為t時(shí)，VNR(t)映射收益表達(dá)式如下

(1)

根據(jù)式(1)可以看出，虛擬網(wǎng)絡(luò)資源需求總和即虛擬網(wǎng)絡(luò)請(qǐng)求映射收益[7]，在信任度需求提高的條件下，虛擬網(wǎng)絡(luò)映射總收益的安全收益有所提升。

時(shí)間為t時(shí)，VNR(t)映射成本表達(dá)式如下

(2)

2)虛擬網(wǎng)絡(luò)請(qǐng)求接受率

在固定時(shí)間段T內(nèi)，總虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量與虛擬網(wǎng)絡(luò)成功映射請(qǐng)求數(shù)之比即虛擬網(wǎng)絡(luò)請(qǐng)求接收率，其表達(dá)式如下

(3)

式(3)中，VNR表示達(dá)到的虛擬網(wǎng)絡(luò)請(qǐng)求總量，VNRsuccess表示時(shí)間段T內(nèi)成功映射的虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量。根據(jù)式(3)可以看出，固定時(shí)間段內(nèi)，虛擬網(wǎng)絡(luò)請(qǐng)求接受率越高，成功映射的虛擬網(wǎng)絡(luò)請(qǐng)求數(shù)量越高[9]，且無線虛擬網(wǎng)絡(luò)資源總映射收益越高。

2.3 建立數(shù)學(xué)模型

將虛擬網(wǎng)絡(luò)映射成本最低作為映射目標(biāo)，滿足無線虛擬網(wǎng)絡(luò)資源映射安全需求以及資源需求作為約束，利用混合整數(shù)線性規(guī)劃模型表示無線虛擬網(wǎng)絡(luò)資源映射問題，建立目標(biāo)函數(shù)如下

(4)

式(4)中，nj表示底層節(jié)點(diǎn)，ni表示虛擬節(jié)點(diǎn)。

設(shè)置約束條件如下：

1)節(jié)點(diǎn)CPU資源約束

?ni∈Nv，?nj∈Ns，令

(5)

利用式(5)令虛擬節(jié)點(diǎn)CPU資源需求小于物理節(jié)點(diǎn)可用CPU資源。

2)節(jié)點(diǎn)映射位置約束

(6)

3)鏈路帶寬資源約束

(7)

4)鏈路連通性約束

?nj∈Ns，?luv∈Lv，令

(8)

5)節(jié)點(diǎn)信任度安全約束

?ni∈Nv，?nj∈Ns，令

(9)

式(9)中，Φ(nj)表示承載于物理節(jié)點(diǎn)nj中的虛擬節(jié)點(diǎn)集合。

6)同一物理節(jié)點(diǎn)不可映射差異虛擬節(jié)點(diǎn)

(10)

7)同一物理節(jié)點(diǎn)僅可映射一個(gè)虛擬節(jié)點(diǎn)

(11)

8)變量域約束

(12)

(13)

2.4 基于GSA算法的資源映射實(shí)現(xiàn)

GSA算法是遺傳算法與模擬退火算法結(jié)合的組合算法，利用GSA算法可快速獲取無線虛擬網(wǎng)絡(luò)資源映射數(shù)學(xué)模型最優(yōu)解，采用GSA算法求解無線虛擬網(wǎng)絡(luò)資源映射數(shù)學(xué)模型流程如下：

1)編碼

選取順序編碼方式對(duì)無線虛擬網(wǎng)絡(luò)資源映射節(jié)點(diǎn)號(hào)碼以及物理網(wǎng)絡(luò)節(jié)點(diǎn)實(shí)施編碼。

2)參數(shù)初始化

用MaxPOP表示群體規(guī)模，k表示迭代次數(shù)，tk與POP(k)分別表示初始溫度以及群體，對(duì)以上參數(shù)實(shí)施初始化[10]，設(shè)置POP(k)內(nèi)包含符合約束條件的可行解。

3)模擬退火操作

符合所設(shè)定終止規(guī)則時(shí)，終止運(yùn)算；設(shè)染色體i存在于群體POP(k)中，隨機(jī)選取狀態(tài)j∈POP(k)，可得該操作接受概率如下

(14)

當(dāng)f(j)random(0，1)時(shí)，接受j，狀態(tài)i的目標(biāo)值用f(i)表示，f(i)值為合法映射所獲取的值。需進(jìn)行MaxPOP次迭代模擬退火操作，利用所接受個(gè)體與POP(k)內(nèi)個(gè)體共同建立新種群，用NewPOP(k)表示。

4)選取種群

新種群內(nèi)個(gè)體適應(yīng)函數(shù)表達(dá)式如下

(15)

式(15)中，fmin表示最小目標(biāo)函數(shù)值。依據(jù)通過式(15)所獲取的概率分布隨機(jī)于新種群個(gè)體中選取染色體，利用所形成染色體生成新種群NewPOP(k+1)。

5)交叉與變異

將交叉概率Pc依據(jù)遺傳算法交叉操作獲取CrossPOP(k+1)，通過變異操作變異率Pm獲取MutPOP(k+1)。選取不變位法實(shí)施交叉操作過程如下：形成可表示父代個(gè)體需交叉基因的二進(jìn)制向量，所生成二進(jìn)制向量存在相同維數(shù)染色體編碼，用1與0分別表示不變以及需要改變的基因，不變基因以及變化基因分別遺傳到子代。

采用逆序變異法實(shí)施變異操作，首先需明確待變異父代，逆序操作隨機(jī)選取的基因位生成新染色體。

通過自適應(yīng)遺傳算法交叉以及變異操作獲取交叉率以及變異率公式如下

(16)

(17)

以上公式中，0≤ki≤1，F(xiàn)max與Favg分別表示群體最大適應(yīng)度以及平均適應(yīng)度；F與F′分別表示交叉?zhèn)€體中較大適應(yīng)度以及將變異的個(gè)體適應(yīng)度。

6)退火操作

設(shè)置tk+1=d(tk)，k=k+1，POP(k)-mutPOP(k)，轉(zhuǎn)回至步驟3)。存在下降溫度個(gè)體時(shí)，需采用以下公式處理：

tk+1=tk(1+σtk)-1

(18)

式(18)中，退火系數(shù)σ求解公式如下：

(19)

式(19)中，tf與N分別表示固定值以及可下降溫度的最大次數(shù)，選取非時(shí)齊算法獲取不同溫度下的迭代次數(shù)。

通過以上過程求解無線虛擬網(wǎng)絡(luò)資源映射數(shù)學(xué)模型，完成無線虛擬網(wǎng)絡(luò)資源有效映射。

3 模型測(cè)試

為了驗(yàn)證基于GSA算法的無線虛擬網(wǎng)絡(luò)資源映射數(shù)學(xué)模型的有效性與全面性，選取GT-ITM軟件生成底層物理網(wǎng)絡(luò)拓?fù)?，該網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中包含節(jié)點(diǎn)數(shù)量為20個(gè)，各底層物理節(jié)點(diǎn)處理能力處于[100，200]個(gè)單元間，各物理鏈路帶寬資源處于[100，200]個(gè)帶寬單位間。設(shè)所建立物理網(wǎng)絡(luò)拓?fù)渲懈骶W(wǎng)絡(luò)請(qǐng)求功能數(shù)量處于2-16間。

統(tǒng)計(jì)采用本文模型實(shí)施無線虛擬網(wǎng)絡(luò)資源映射處理時(shí)間結(jié)果如表1所示。

表1 網(wǎng)絡(luò)功能處理時(shí)間

表1實(shí)驗(yàn)結(jié)果可以看出，采用本文方法可實(shí)現(xiàn)無線虛擬網(wǎng)絡(luò)資源有效映射，且映射所需處理時(shí)間較短。

選取兩次優(yōu)先級(jí)模型(參考文獻(xiàn)[4])以及元胞遺傳模型(參考文獻(xiàn)[5])作為對(duì)比模型，采用不同模型實(shí)施無線虛擬網(wǎng)絡(luò)資源映射部署成本對(duì)比結(jié)果如圖1所示。

圖1 部署成本對(duì)比

圖1實(shí)驗(yàn)結(jié)果可以看出，采用本文模型實(shí)現(xiàn)無線虛擬網(wǎng)絡(luò)資源映射，不同迭代次數(shù)情況下的部署成本均為最低。采用本文模型實(shí)現(xiàn)無線虛擬網(wǎng)絡(luò)資源映射，不僅可有效滿足資源映射的業(yè)務(wù)需求，而且可降低移動(dòng)網(wǎng)絡(luò)運(yùn)營(yíng)商成本，提升運(yùn)營(yíng)商收益。

統(tǒng)計(jì)采用三種模型實(shí)現(xiàn)無線虛擬網(wǎng)絡(luò)資源映射，虛擬網(wǎng)絡(luò)中不同網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量時(shí)所使用物理節(jié)點(diǎn)數(shù)量，統(tǒng)計(jì)結(jié)果如圖2所示。

圖2 物理節(jié)點(diǎn)數(shù)量對(duì)比

圖2實(shí)驗(yàn)結(jié)果可以看出，隨著虛擬網(wǎng)絡(luò)中所包含網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量的提升，三種模型的底層物理節(jié)點(diǎn)數(shù)量均有所提升，但是本文模型的底層物理節(jié)點(diǎn)數(shù)量低于傳統(tǒng)方法。說明本文模型所需底層物理節(jié)點(diǎn)數(shù)量較少，再次驗(yàn)證本文模型可降低虛擬網(wǎng)絡(luò)部署成本，節(jié)省運(yùn)營(yíng)商運(yùn)行成本。

統(tǒng)計(jì)不同網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量時(shí)三種模型的平均底層物理鏈路利用率，統(tǒng)計(jì)結(jié)果如圖3所示。

圖3 物理鏈路利用率

圖3實(shí)驗(yàn)結(jié)果可以看出，隨著網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量的提升，不同模型的底層鏈路利用率均有所提升。采用本文模型映射無線虛擬網(wǎng)絡(luò)資源，在不同網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量情況下，底層鏈路利用率均明顯低于另兩種模型。本文模型可有效節(jié)省底層鏈路利用情況，提升無線虛擬網(wǎng)絡(luò)資源映射有效性，節(jié)省映射資源。本文模型底層物理鏈路利用率較低，可避免網(wǎng)絡(luò)出現(xiàn)擁塞情況，網(wǎng)絡(luò)應(yīng)用終端連接數(shù)量多以及節(jié)點(diǎn)密度大時(shí)，仍具有良好的傳輸性能。

統(tǒng)計(jì)不同網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量時(shí)三種模型實(shí)施無線虛擬網(wǎng)絡(luò)資源映射的剩余帶寬資源，對(duì)比結(jié)果如表2所示。

表2 剩余帶寬對(duì)比

表2實(shí)驗(yàn)結(jié)果可以看出，本文模型在不同網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量時(shí)剩余帶寬均明顯高于另兩種模型，剩余帶寬均高于80%；另兩種模型在不同網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量時(shí)剩余帶寬均低于80%。對(duì)比結(jié)果有效驗(yàn)證本文模型映射無線虛擬網(wǎng)絡(luò)節(jié)點(diǎn)剩余帶寬較高，這是因?yàn)楸疚哪Ｐ筒捎肎SA算法具有較高的計(jì)算效率，可快速獲取最優(yōu)解，具有較高的運(yùn)算效率，可實(shí)現(xiàn)無線虛擬網(wǎng)絡(luò)資源良好映射。

統(tǒng)計(jì)不同網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量時(shí)三種模型的虛擬網(wǎng)絡(luò)請(qǐng)求接受率，對(duì)比結(jié)果如表3所示。

表3 請(qǐng)求接受率對(duì)比

表3實(shí)驗(yàn)結(jié)果可以看出，本文模型可為所映射虛擬網(wǎng)絡(luò)良好分配資源，初始映射時(shí)具有較高的物理網(wǎng)絡(luò)可用資源，因此三種模型的虛擬網(wǎng)絡(luò)請(qǐng)求接受率均較高。隨著網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量的增加，三種模型的虛擬網(wǎng)絡(luò)請(qǐng)求接受率均有所降低，采用本文模型實(shí)施無線虛擬網(wǎng)絡(luò)資源映射，不同網(wǎng)絡(luò)功能節(jié)點(diǎn)數(shù)量時(shí)虛擬網(wǎng)絡(luò)請(qǐng)求接受率均高于92%，驗(yàn)證本文模型具有較高的映射性能。

4 結(jié)論

構(gòu)建無線虛擬網(wǎng)絡(luò)資源映射數(shù)學(xué)模型，充分考慮信任度問題，提升無線虛擬網(wǎng)絡(luò)安全性。選取GSA算法實(shí)現(xiàn)模型高效求解，通過實(shí)驗(yàn)驗(yàn)證所研究模型可有效實(shí)現(xiàn)無線虛擬網(wǎng)絡(luò)資源有效映射，該模型在映射收益、請(qǐng)求接受率等方面均具有較高的優(yōu)勢(shì)，體現(xiàn)了該模型的映射效率。所研究模型可有效改善以往無線虛擬網(wǎng)絡(luò)資源映射所具有的映射效率低的缺陷，可滿足5G移動(dòng)網(wǎng)絡(luò)多樣化應(yīng)用場(chǎng)景需求。