基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射算法

吳譽(yù)蘭，舒建文

(1.南昌航空大學(xué)科技學(xué)院，江西南昌332020；2.南昌航空大學(xué)信息工程學(xué)院，江西南昌330063)

1 引言

節(jié)點(diǎn)多屬性網(wǎng)絡(luò)可以在底層的物理網(wǎng)絡(luò)內(nèi)，抽象出多個(gè)結(jié)構(gòu)不一致且獨(dú)立的網(wǎng)絡(luò)，并且能夠加快資源共享的速度[1]。在節(jié)點(diǎn)多屬性網(wǎng)絡(luò)內(nèi)，基礎(chǔ)設(shè)施供應(yīng)商主要負(fù)責(zé)供給可用的物理資源，網(wǎng)絡(luò)供應(yīng)商主要負(fù)責(zé)把資源轉(zhuǎn)化成網(wǎng)絡(luò)資源，服務(wù)商則會(huì)通過(guò)網(wǎng)絡(luò)資源為用戶提供服務(wù)。所有網(wǎng)絡(luò)資源都會(huì)經(jīng)過(guò)多種鏈路和節(jié)點(diǎn)組成[2]。但因?yàn)椴荒軣o(wú)限供應(yīng)資源，所以，在資源有限的情況下收取更多的網(wǎng)絡(luò)請(qǐng)求、同時(shí)提升資源使用率，成為當(dāng)前領(lǐng)域內(nèi)較為熱點(diǎn)研究話題。

文獻(xiàn)[3]根據(jù)業(yè)務(wù)類型，粗化虛擬網(wǎng)絡(luò)請(qǐng)求，計(jì)算請(qǐng)求優(yōu)先級(jí)，初步確定虛擬網(wǎng)絡(luò)映射順序，考慮鏈路帶寬資源需求，根據(jù)鏈路權(quán)重獲取優(yōu)先級(jí)，計(jì)算最佳映射路徑。該算法縮短了虛擬網(wǎng)絡(luò)請(qǐng)求等待時(shí)間，但該算法的平均鏈路映射長(zhǎng)度較長(zhǎng)。文獻(xiàn)[4]通過(guò)管理和編排網(wǎng)絡(luò)功能虛擬化及服務(wù)器，構(gòu)建兩級(jí)隊(duì)列動(dòng)態(tài)調(diào)度模型，感知并動(dòng)態(tài)調(diào)度目前隊(duì)列積壓狀態(tài)，并使其穩(wěn)定為較小值，利用Lyapunov隨機(jī)優(yōu)化方法，完成映射與時(shí)延控制。該算法能夠?qū)崿F(xiàn)最優(yōu)化資源調(diào)度，但網(wǎng)絡(luò)請(qǐng)求接受率和收益開(kāi)銷較低。

針對(duì)上述問(wèn)題，提出基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射算法，通過(guò)構(gòu)建拓?fù)浣Y(jié)構(gòu)與評(píng)價(jià)指標(biāo)，挑選網(wǎng)絡(luò)映射區(qū)域，依靠回溯型算法計(jì)算sumTR值，得到備選網(wǎng)絡(luò)節(jié)點(diǎn)集合進(jìn)行映射，實(shí)現(xiàn)節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射。

2 節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射問(wèn)題描述

2.1 形式化定義

定義3：節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射問(wèn)題即一種GV至Gs的映射過(guò)程，其能夠描述成M:GV其中，需要滿足與此外，RV與RE分別代表已經(jīng)將底層資源分配至屬性與節(jié)點(diǎn)中的數(shù)量。

在大多數(shù)狀態(tài)下，節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射問(wèn)題會(huì)通過(guò)節(jié)點(diǎn)映射節(jié)點(diǎn)與鏈接映射節(jié)點(diǎn)來(lái)構(gòu)成。

1)節(jié)點(diǎn)映射節(jié)點(diǎn)即在滿足CPU約束的基礎(chǔ)上，把節(jié)點(diǎn)屬性映射到底層節(jié)點(diǎn)中；

2)鏈路映射階段即在滿足帶寬約束的基礎(chǔ)上，把鏈接屬性映射到底層路徑中。

2.2 解決目標(biāo)

接收節(jié)點(diǎn)多屬性網(wǎng)絡(luò)的GV在時(shí)間t的收益能夠被擬定成

(1)

式中，CPU(vV)為節(jié)點(diǎn)vV需要的CPU，BW(eV)為鏈路eV需要的帶寬[6]。考慮到CPU與帶寬在不同應(yīng)用程序的關(guān)鍵性，因此擬定成一種因子α來(lái)調(diào)整式(1)，一種節(jié)點(diǎn)多屬性網(wǎng)絡(luò)的接收收益能夠擬定成

(2)

一種節(jié)點(diǎn)多屬性網(wǎng)絡(luò)的GV在時(shí)間t的接收代價(jià)能夠描述成式(3)，其也能夠用于擬定分配至底層路徑的資源

(3)

網(wǎng)絡(luò)的長(zhǎng)期收益平均值能夠擬定成

(4)

(5)

考慮訪問(wèn)控制機(jī)制[7]，在底層資源沒(méi)有被有效地分配至一種新到達(dá)的節(jié)點(diǎn)多屬性網(wǎng)絡(luò)中時(shí)，會(huì)拒絕對(duì)該網(wǎng)絡(luò)的訪問(wèn)。所以，擬定網(wǎng)絡(luò)的接收比例，其能夠描述成

(6)

式中，VNS為網(wǎng)絡(luò)請(qǐng)求被接收的總量，而VN代表達(dá)到節(jié)點(diǎn)多屬性網(wǎng)絡(luò)的請(qǐng)求數(shù)量。

3 基于拓?fù)浣Y(jié)構(gòu)感知的網(wǎng)絡(luò)模型與評(píng)測(cè)指標(biāo)

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

節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射過(guò)程如圖1所示。

圖1 節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射過(guò)程

在圖1中，a，b，c代表屬性節(jié)點(diǎn)，A，B，C，D，E，F(xiàn)代表物理節(jié)點(diǎn)，數(shù)字分別表示可用計(jì)算資源與節(jié)點(diǎn)計(jì)算資源，矩形框代表坐標(biāo)約束，框中的物理節(jié)點(diǎn)為可用的映射節(jié)點(diǎn)。節(jié)點(diǎn)的映射結(jié)果為{a→A，b→B，c→F}，鏈路映射的結(jié)果為{(a，b)→(A，B)，(a，c)→(A，D，E，F(xiàn))}。在節(jié)點(diǎn)多屬性網(wǎng)絡(luò)請(qǐng)求在底層物理網(wǎng)絡(luò)中存在的時(shí)間達(dá)到Tv時(shí)，底層物理網(wǎng)絡(luò)就會(huì)剔除被占用的資源。

3.2 評(píng)測(cè)指標(biāo)

節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射評(píng)測(cè)指標(biāo)如下所示

1)節(jié)點(diǎn)多屬性網(wǎng)絡(luò)的平均鏈路映射長(zhǎng)度，其運(yùn)算如式(7)所示

(7)

式中，h(ev)代表網(wǎng)絡(luò)鏈路映射至物理網(wǎng)絡(luò)中通過(guò)的跳數(shù)，|Ev|代表網(wǎng)絡(luò)鏈路的總量。

2)節(jié)點(diǎn)多屬性網(wǎng)絡(luò)的請(qǐng)求接受率，在T時(shí)間中，其運(yùn)算如式(8)所示

(8)

式中，VNrecv(T)代表實(shí)現(xiàn)映射的網(wǎng)絡(luò)請(qǐng)求總量，VNrecv(T)代表網(wǎng)絡(luò)請(qǐng)求的總量[8]，δ代表防止分母是0而擬定的無(wú)限接近于0的正數(shù)。

3)在t時(shí)刻，每映射一個(gè)網(wǎng)絡(luò)請(qǐng)求所產(chǎn)生的收益開(kāi)銷能夠擬定成

(9)

式中，參數(shù)α可以更改節(jié)點(diǎn)收益與鏈路收益權(quán)重，其取值是1。

4 節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射算法實(shí)現(xiàn)

4.1 挑選資源分配區(qū)域

回溯型算法的每次運(yùn)算即實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)分配資源[9]。第一個(gè)節(jié)點(diǎn)的宿主物理節(jié)點(diǎn)決定了該節(jié)點(diǎn)多屬性網(wǎng)絡(luò)在物理網(wǎng)絡(luò)內(nèi)的資源分配區(qū)域。優(yōu)先使用資源較為豐富的子區(qū)域進(jìn)行資源分配，可以有效地對(duì)物理網(wǎng)絡(luò)的負(fù)載進(jìn)行平衡，縮減瓶頸節(jié)點(diǎn)、鏈路與局部堵塞的出現(xiàn)[10]。因此，針對(duì)所有物理節(jié)點(diǎn)，運(yùn)算以該節(jié)點(diǎn)作為中心，以GV平均尺寸的一半作為半徑之中所有節(jié)點(diǎn)的和與sumTR值，挑選與值最大的物理節(jié)點(diǎn)作為第一個(gè)節(jié)點(diǎn)的宿主物理節(jié)點(diǎn)。

4.2 物理節(jié)點(diǎn)與網(wǎng)絡(luò)節(jié)點(diǎn)的選擇

本文算法中，網(wǎng)絡(luò)節(jié)點(diǎn)的映射順序與映射坐標(biāo)對(duì)算法運(yùn)行成功率與映射質(zhì)量存在較大的干擾。算法每次運(yùn)算首先獲得該次運(yùn)算的備選網(wǎng)絡(luò)節(jié)點(diǎn)集合，隨后從中挑選sumTR值最大的節(jié)點(diǎn)進(jìn)行映射。每次映射的備選網(wǎng)絡(luò)節(jié)點(diǎn)集合能夠描述成：

為了提升網(wǎng)絡(luò)鏈路的映射質(zhì)量，對(duì)這些預(yù)選的物理節(jié)點(diǎn)進(jìn)行排序時(shí)，除了需要考慮該節(jié)點(diǎn)的資源能力，還需要考慮目前被選取的網(wǎng)絡(luò)節(jié)點(diǎn)存在直接通信關(guān)系與已經(jīng)實(shí)現(xiàn)映射的網(wǎng)絡(luò)節(jié)點(diǎn)所映射到的物理節(jié)點(diǎn)。擬定一種備選物理節(jié)點(diǎn)n，其優(yōu)先級(jí)擬定成

(10)

4.3 節(jié)點(diǎn)多屬性分析

緊密中心度較高的節(jié)點(diǎn)不一定是處于整體網(wǎng)絡(luò)中心坐標(biāo)的固定節(jié)點(diǎn)，但和網(wǎng)絡(luò)內(nèi)其它節(jié)點(diǎn)的鏈接性一定是最好的。鏈路映射取決于已經(jīng)部署的物理節(jié)點(diǎn)，連接性較高的節(jié)點(diǎn)在鏈路部署的過(guò)程中存在更為豐富的選擇[12]。所以，在節(jié)點(diǎn)映射的階段，有限映射距離網(wǎng)絡(luò)中其它節(jié)點(diǎn)鏈接性較好的物理節(jié)點(diǎn)，這樣挑選的節(jié)點(diǎn)間的請(qǐng)求帶寬需求會(huì)更加容易滿足，縮減鏈路帶寬的開(kāi)銷。

物理節(jié)點(diǎn)的度值就是節(jié)點(diǎn)鄰接鏈路數(shù)，其能夠描述成

(11)

其中，lS→nS代表物理鏈路和物理節(jié)點(diǎn)的鏈接，綜合考慮物理節(jié)點(diǎn)的最短鏈接尺寸、可用資源與帶寬資源的實(shí)時(shí)拓?fù)鋵傩裕瑯?gòu)建物理節(jié)點(diǎn)的緊密中心度運(yùn)算模型

(12)

擬定存在t種物理節(jié)點(diǎn)，x代表已經(jīng)映射的物理節(jié)點(diǎn)總量，綜合考慮C(nS)，E(nS)，DC(nS)，CC(nS)與已經(jīng)映射節(jié)點(diǎn)的尺寸DI(nS)，其共存在k種評(píng)測(cè)指標(biāo)，k=4+x，那么節(jié)點(diǎn)多屬性評(píng)測(cè)指標(biāo)矩陣MPS能夠描述成

(13)

4.4 節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射

在對(duì)節(jié)點(diǎn)多屬性分析的基礎(chǔ)上，本文通過(guò)動(dòng)態(tài)拓?fù)涓兄c資源屬性組成了節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射方法，該方法能夠分成兩階段：鏈路映射與節(jié)點(diǎn)映射。

首先放置網(wǎng)絡(luò)節(jié)點(diǎn)，把該節(jié)點(diǎn)按照映射優(yōu)先級(jí)EP(nV)進(jìn)行排列，挑選出隊(duì)列首位的節(jié)點(diǎn)。把該節(jié)點(diǎn)的備用物理節(jié)點(diǎn)按映射優(yōu)先級(jí)EP(nS)降序排列。挑選EP(nS)值最大同時(shí)滿足節(jié)點(diǎn)資源需求的底層節(jié)點(diǎn)進(jìn)行部署。

在實(shí)現(xiàn)請(qǐng)求中所有節(jié)點(diǎn)的部署之后，以鏈路帶寬資源作為權(quán)重，使用k-最短路徑算法，挑選一條滿足虛擬鏈路帶寬，同時(shí)跳數(shù)最小的物理路徑部署虛擬鏈路，實(shí)現(xiàn)鏈路映射，由此完成基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射。

5 仿真分析

為了驗(yàn)證基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射算法的有效性，在仿真平臺(tái)MATLAB下進(jìn)行對(duì)比實(shí)驗(yàn)。設(shè)置節(jié)點(diǎn)個(gè)數(shù)為200個(gè)，運(yùn)行時(shí)間為40s，坐標(biāo)約束為300、600和900。分別采用文獻(xiàn)[3]算法、文獻(xiàn)[4]算法和所提算法進(jìn)行節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射，得到不同方法的平均鏈路映射長(zhǎng)度如表1所示。

表1 不同方法的平均鏈路映射長(zhǎng)度

根據(jù)表1中的數(shù)據(jù)可知，在不同坐標(biāo)約束下，所提算法的平均鏈路映射長(zhǎng)度均最小，文獻(xiàn)[4]算法的平均鏈路映射長(zhǎng)度次之，而文獻(xiàn)[3]算法的平均鏈路映射長(zhǎng)度最大，由此可知，所提算法能夠有效縮短鏈路映射長(zhǎng)度。

在此基礎(chǔ)上對(duì)比不同方法的請(qǐng)求接受率結(jié)果如圖2所示。

圖2 不同方法的請(qǐng)求接受率對(duì)比結(jié)果

通過(guò)圖2能夠看出，當(dāng)運(yùn)行時(shí)間達(dá)到40s時(shí)，文獻(xiàn)[3]算法的平均請(qǐng)求接受率為87%，文獻(xiàn)[4]算法的平均請(qǐng)求接受率為83%，而所提算法的平均請(qǐng)求接受率高達(dá)93%。由此可知，所提算法的請(qǐng)求接受率較高，這是因?yàn)樗崴惴ú捎猛負(fù)浣Y(jié)構(gòu)感知方法，受結(jié)構(gòu)的影響，在選取鏈接路徑時(shí)，將已經(jīng)選取過(guò)的路徑剔除，以防止路徑資源消耗過(guò)度，從而有效提高了請(qǐng)求接受率。

進(jìn)一步驗(yàn)證所提算法與文獻(xiàn)[3]算法、文獻(xiàn)[4]算法的鏈路映射收益開(kāi)銷比，對(duì)比結(jié)果如圖3所示。

圖3 不同方法的映射收益開(kāi)銷比對(duì)比結(jié)果

通過(guò)圖3能夠看出，當(dāng)運(yùn)行時(shí)間達(dá)到40s時(shí)，文獻(xiàn)[3]算法的平均映射收益開(kāi)銷比為0.76，文獻(xiàn)[4]算法的平均映射收益開(kāi)銷比為0.65，而所提算法的映射收益開(kāi)銷比為0.87。由此可知，所提算法的鏈路映射收益開(kāi)銷比相對(duì)較高，這是由于拓?fù)浣Y(jié)構(gòu)感知算法的資源濃度能夠綜合路徑啟發(fā)信息，以此來(lái)選取路徑，使得資源的消耗更為均勻，接受資源需求高的網(wǎng)絡(luò)幾率更大，從而提高鏈路映射收益開(kāi)銷比。

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

為了提高網(wǎng)絡(luò)請(qǐng)求接受率和收益開(kāi)銷，縮短平均鏈路映射長(zhǎng)度，提出基于拓?fù)浣Y(jié)構(gòu)感知的節(jié)點(diǎn)多屬性網(wǎng)絡(luò)映射算法，該算法能夠有效提高網(wǎng)絡(luò)請(qǐng)求接受率和收益開(kāi)銷，縮短平均鏈路映射長(zhǎng)度。但該方法通過(guò)拓?fù)浣Y(jié)構(gòu)感知模型依次計(jì)算節(jié)點(diǎn)與連接消耗大量的時(shí)間，導(dǎo)致映射效率下降。因此下一步的研究，在此基礎(chǔ)上加以優(yōu)化，進(jìn)而提升計(jì)算效率。