具有高可靠特征的無線虛擬網(wǎng)絡(luò)映射方法研究

高航航，趙尚弘，王 翔，彭 聰

空軍工程大學(xué) 信息與導(dǎo)航學(xué)院，西安710077

1 引言

網(wǎng)絡(luò)虛擬化[1-2]被認(rèn)為是未來網(wǎng)絡(luò)中的一項(xiàng)關(guān)鍵技術(shù)，是一種應(yīng)對(duì)當(dāng)前互聯(lián)網(wǎng)僵化問題的重要方法，其有效地增強(qiáng)了網(wǎng)絡(luò)的靈活性，可以使不同的虛擬網(wǎng)絡(luò)請(qǐng)求（Virtual Network Request，VNR）共存于同一個(gè)底層物理網(wǎng)絡(luò)中，共享底層物理網(wǎng)絡(luò)資源，并且這些虛擬網(wǎng)絡(luò)請(qǐng)求之間相互隔離，在安全性方面也有一定的保證。網(wǎng)絡(luò)虛擬化改變了傳統(tǒng)的網(wǎng)絡(luò)服務(wù)與資源緊密耦合的特性，實(shí)現(xiàn)了網(wǎng)絡(luò)服務(wù)與資源靈活且有效的利用。虛擬網(wǎng)絡(luò)映射[3-5]作為網(wǎng)絡(luò)虛擬化當(dāng)中的一項(xiàng)關(guān)鍵技術(shù)，是指將底層物理網(wǎng)絡(luò)資源分配給虛擬網(wǎng)絡(luò)中帶有約束條件的虛擬節(jié)點(diǎn)以及虛擬鏈路的過程，目前已被證明是NP難問題[6-7]。虛擬網(wǎng)絡(luò)映射目前主要面臨著資源約束、準(zhǔn)入控制、在線請(qǐng)求和拓?fù)涠鄻拥葐栴}[8]，且由于VNR的到達(dá)時(shí)間、持續(xù)時(shí)間和服務(wù)需求不可預(yù)知，當(dāng)?shù)讓泳W(wǎng)絡(luò)拓?fù)漭^大時(shí)，采用傳統(tǒng)方法求解將會(huì)產(chǎn)生龐大的搜索空間，難以在有限時(shí)間內(nèi)滿足VNR的各種需求。

傳統(tǒng)虛擬網(wǎng)絡(luò)映射算法將節(jié)點(diǎn)映射階段與鏈路映射階段完全分離，忽略了鏈路映射結(jié)果對(duì)物理節(jié)點(diǎn)排序的影響，導(dǎo)致高映射成本和虛擬節(jié)點(diǎn)在底層物理網(wǎng)絡(luò)上的分布式分布，針對(duì)這些問題，文獻(xiàn)[9]提出了一種基于節(jié)點(diǎn)屬性和網(wǎng)絡(luò)單純形的雙層虛擬網(wǎng)絡(luò)映射算法Simplex-VNM，在節(jié)點(diǎn)映射層中采用一種考慮拓?fù)鋵傩?、全局網(wǎng)絡(luò)資源和映射物理節(jié)點(diǎn)信息的新節(jié)點(diǎn)排序方法以此為鏈路映射層提供候選節(jié)點(diǎn)和節(jié)點(diǎn)映射成本，在鏈路映射階段中，通過引入與傳統(tǒng)最短路徑算法相比具有較小時(shí)間復(fù)雜度的網(wǎng)絡(luò)單純形算法，以在節(jié)點(diǎn)映射層的結(jié)果下找到最優(yōu)鏈路映射解決方案，最后根據(jù)兩層結(jié)果以最小的總映射成本映射虛擬節(jié)點(diǎn)和相關(guān)鏈路，仿真表明本文算法在考慮節(jié)點(diǎn)屬性和使用最短路徑算法下的總映射成本和映射時(shí)間性能方面優(yōu)于其他四種算法；當(dāng)前大多數(shù)虛擬網(wǎng)絡(luò)映射算法主要面向底層網(wǎng)絡(luò)無故障環(huán)境下如何以提高網(wǎng)絡(luò)資源利用率、Vn請(qǐng)求接受率等指標(biāo)，如文獻(xiàn)[10]在馬爾科夫隨機(jī)模型中采用K分解技術(shù)將VNR分割為核心網(wǎng)絡(luò)和邊緣網(wǎng)絡(luò)，并提出一種ViNEYard算法，算法通過協(xié)調(diào)節(jié)點(diǎn)映射和鏈路映射兩個(gè)過程并優(yōu)先映射生存時(shí)間短的VNR，結(jié)果表明所提算法有效地提高了Vn接受率和網(wǎng)絡(luò)收益；針對(duì)物理節(jié)點(diǎn)負(fù)載不均衡問題，文獻(xiàn)[11]采用一種基于最小節(jié)點(diǎn)負(fù)載優(yōu)先的映射算法進(jìn)行求解，算法通過計(jì)算底層網(wǎng)絡(luò)中各節(jié)點(diǎn)的負(fù)載強(qiáng)度，得到具有剩余資源大和負(fù)載小的物理節(jié)點(diǎn)作為承載節(jié)點(diǎn)進(jìn)行映射，并采用k最短路徑法完成鏈路映射，結(jié)果表明文中算法在資源利用率、鏈路均衡度方面均得到有效提升；文獻(xiàn)[12]為解決底層網(wǎng)絡(luò)在映射中所存在的能耗過高問題，提出一種基于鏈路可分割的鏈路休眠算法，在網(wǎng)絡(luò)低負(fù)載階段中由于部分鏈路資源不能得到充分利用，從而將低資源利用率的虛擬鏈路重映射到高資源利用率的鏈路上，并將資源利用率低的鏈路進(jìn)行休眠操作，結(jié)果表明該算法在提升鏈路資源利用率的同時(shí)也增大了Vn映射成功率，但也帶來了通信延遲等問題；文獻(xiàn)[13]主要討論了分布式和混合云環(huán)境中的網(wǎng)絡(luò)資源映射問題，為解決數(shù)千個(gè)節(jié)點(diǎn)的大型虛擬和物理網(wǎng)絡(luò)的復(fù)雜性和可擴(kuò)展性，文中提出了一種依靠拓?fù)淠Ｊ胶投制ヅ涞母咝l(fā)式改進(jìn)算法以獲得最優(yōu)映射方案，通過將虛擬資源分離到不同的物理節(jié)點(diǎn)并在相同的物理節(jié)點(diǎn)中同定位，最終算法采用虛擬分解技術(shù)和物理模式圖的二分匹配法以在線性時(shí)間內(nèi)解決該虛擬映射問題；在動(dòng)態(tài)網(wǎng)絡(luò)拓?fù)渲校捎诠?jié)點(diǎn)的移動(dòng)性導(dǎo)致無線鏈路易發(fā)生中斷，造成映射在該鏈路上的Vn失效，使得相應(yīng)的網(wǎng)絡(luò)服務(wù)無法完成，此外，底層節(jié)點(diǎn)發(fā)生故障也會(huì)造成Vn失效，文獻(xiàn)[14]針對(duì)底層網(wǎng)絡(luò)單節(jié)點(diǎn)失效問題提出一種拓?fù)涓兄墓?jié)點(diǎn)映射策略和一種基于禁忌搜索算法的鏈路映射策略，仿真表明虛擬請(qǐng)求失效時(shí)所提算法在獲得較高映射成功率的同時(shí)也能達(dá)到較高的網(wǎng)絡(luò)收益和資源利用率；文獻(xiàn)[15]針對(duì)底層多節(jié)點(diǎn)故障問題提出一種基于拓?fù)涓兄奶摂M映射方法，文中首先在Vn到來之前為底層節(jié)點(diǎn)構(gòu)建候選集，當(dāng)Vn到來時(shí)利用可恢復(fù)性的映射策略對(duì)Vn的主要資源進(jìn)行分配，將重要度較大的虛擬節(jié)點(diǎn)映射到可恢復(fù)性較好的物理節(jié)點(diǎn)上，當(dāng)物理節(jié)點(diǎn)發(fā)生故障時(shí)采用利益驅(qū)動(dòng)的重映射算法對(duì)受影響的Vn進(jìn)行恢復(fù)；文獻(xiàn)[16]針對(duì)無線鏈路可靠性差提出一種基于鏈路可靠性的虛擬網(wǎng)絡(luò)分配算法，算法允許同一虛擬請(qǐng)求中不同節(jié)點(diǎn)映射到同一物理節(jié)點(diǎn)，并利用Q因子對(duì)稀疏拓?fù)浞峙鋾r(shí)Vn映射成功率低進(jìn)行改進(jìn)，仿真表明該算法可獲得較高的Vn構(gòu)建成功率和資源利用率；文獻(xiàn)[17]針對(duì)底層鏈路故障問題分別提出鏈路恢復(fù)和路徑恢復(fù)兩種方法，文中采用一種混合策略的啟發(fā)式算法用來解決可生存性虛擬網(wǎng)絡(luò)映射問題，算法預(yù)先計(jì)算每條物理鏈路的備份繞道路徑，并對(duì)到達(dá)的Vn執(zhí)行節(jié)點(diǎn)映射和鏈路映射操作，當(dāng)?shù)讓泳W(wǎng)絡(luò)出現(xiàn)故障時(shí)，直接在備份繞道路徑中為失效的鏈路重新路由，仿真表明該算法在Vn接受率、網(wǎng)絡(luò)收益和算法復(fù)雜度等方面要優(yōu)于一般算法；針對(duì)可生存性的虛擬網(wǎng)絡(luò)映射問題，文獻(xiàn)[18]在文中將網(wǎng)絡(luò)鏈路資源分為主要流量資源和次要流量資源以滿足資源保護(hù)要求，并引入了全局資源容量這一指標(biāo)，該指標(biāo)可用于測(cè)量節(jié)點(diǎn)映射容量以改善網(wǎng)絡(luò)的負(fù)載平衡，最后提出一種基于全局資源容量的啟發(fā)式生存虛擬網(wǎng)絡(luò)映射算法GRC-SVNE，算法在節(jié)點(diǎn)映射階段通過計(jì)算所有節(jié)點(diǎn)的映射容量，并選擇部分節(jié)點(diǎn)作為虛擬網(wǎng)絡(luò)映射的候選節(jié)點(diǎn)以提高映射成功率，之后使用Dijkstra算法進(jìn)行鏈路映射，結(jié)果表明文中算法與傳統(tǒng)GREEDY、R-ViNE和D-ViNE算法相比不僅實(shí)現(xiàn)了虛擬網(wǎng)絡(luò)的可生存性，在網(wǎng)絡(luò)負(fù)載均衡和收益方面也獲得了較優(yōu)解；文獻(xiàn)[19]在計(jì)算容量約束和網(wǎng)絡(luò)容量約束下針對(duì)單個(gè)云請(qǐng)求的可生存性映射問題提出一種VSMF啟發(fā)式算法，文中算法共分為兩個(gè)階段，在第一階段中將虛擬網(wǎng)絡(luò)劃分為一組星類，每個(gè)星類都使用一個(gè)虛擬節(jié)點(diǎn)作為中心，第二階段中通過允許一個(gè)虛擬節(jié)點(diǎn)映射一個(gè)或多個(gè)物理節(jié)點(diǎn)以放寬虛擬節(jié)點(diǎn)映射約束，使得共享相同虛擬節(jié)點(diǎn)的虛擬鏈路可共享相同的物理節(jié)點(diǎn)，結(jié)果表明所提VSMF算法在小規(guī)模網(wǎng)絡(luò)和大規(guī)模網(wǎng)絡(luò)中均可獲得比傳統(tǒng)算法更低的成本和阻塞概率；文獻(xiàn)[20]針對(duì)無線網(wǎng)絡(luò)移動(dòng)性提出一種近似算法BIRD-VNE，由于底層節(jié)點(diǎn)的移動(dòng)性導(dǎo)致節(jié)點(diǎn)間的連接關(guān)系發(fā)生改變，使得已經(jīng)被虛擬鏈路使用的物理路徑資源不足或發(fā)生故障，文中算法可以有效捕獲到節(jié)點(diǎn)移動(dòng)和拓?fù)渥兓?，并能夠減小由于底層節(jié)點(diǎn)的移動(dòng)性所導(dǎo)致的Vn重映射所產(chǎn)生的開銷，結(jié)果表明該算法在獲得最佳虛擬映射收益的同時(shí)能夠減少由于節(jié)點(diǎn)移動(dòng)所造成的Vn遷移個(gè)數(shù)，有效地減小了網(wǎng)絡(luò)拓?fù)湟苿?dòng)性對(duì)虛擬網(wǎng)絡(luò)遷移的影響。

上述研究?jī)?nèi)容主要針對(duì)底層節(jié)點(diǎn)或鏈路發(fā)生故障時(shí)VNR的可生存性映射問題，主要以虛擬節(jié)點(diǎn)或虛擬鏈路重映射為主，而未考慮底層網(wǎng)絡(luò)中節(jié)點(diǎn)資源與鏈路資源間的關(guān)系。本文分別在節(jié)點(diǎn)映射和鏈路映射階段引入節(jié)點(diǎn)擴(kuò)展資源和物理鏈路代價(jià)這一概念，建立一種高可靠性的虛擬網(wǎng)絡(luò)映射方案，并針對(duì)網(wǎng)絡(luò)故障設(shè)計(jì)一種可恢復(fù)的重映射方案，結(jié)果表明所提算法能夠獲得較優(yōu)結(jié)果，其性能要優(yōu)于一般算法。

2 模型分析

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

用加權(quán)無向圖GS=(NS,ES)表示底層物理網(wǎng)絡(luò)拓?fù)?，其中ns∈NS表示物理節(jié)點(diǎn)，其屬性包括節(jié)點(diǎn)計(jì)算能力cpu(ns)、節(jié)點(diǎn)位置信息loc(ns)；ls∈ES表示物理鏈路，其屬性包括帶寬資源b(ls)，用P表示底層物理網(wǎng)絡(luò)無環(huán)路徑集合，對(duì)于路徑ps∈PS，其可用帶寬資源b(ps)大小由該路徑所經(jīng)過的各鏈路最小帶寬資源所決定。底層物理網(wǎng)絡(luò)承載多個(gè)虛擬請(qǐng)求，在一段時(shí)間內(nèi)，新虛擬請(qǐng)求到達(dá)的同時(shí)也存在某虛擬請(qǐng)求完成釋放物理網(wǎng)絡(luò)資源，故底層物理網(wǎng)絡(luò)中的資源是動(dòng)態(tài)變化的，其數(shù)學(xué)表達(dá)式如下：

其中，式（1）表示物理節(jié)點(diǎn)資源能力，式（2）和式（3）分別表示物理鏈路帶寬和物理路徑帶寬能力，且路徑帶寬能力由該路徑所經(jīng)過各鏈路的最小帶寬能力所決定。

用加權(quán)無向圖GV=(NV,EV,T)表示虛擬網(wǎng)絡(luò)請(qǐng)求VNR，其中nv∈NV為虛擬網(wǎng)絡(luò)節(jié)點(diǎn)，其屬性包括節(jié)點(diǎn)計(jì)算能力需求cpu(nv)、位置需求loc(nv)；lv∈EV為虛擬網(wǎng)絡(luò)鏈路，其屬性包括帶寬需求b(lv),T表示該虛擬網(wǎng)絡(luò)請(qǐng)求的生存時(shí)間。

2.2 虛擬映射約束條件

將節(jié)點(diǎn)間映射關(guān)系用矩陣FN表示，其中行向量表示虛擬節(jié)點(diǎn)，列向量表示物理節(jié)點(diǎn)，當(dāng)虛擬節(jié)點(diǎn)i映射到物理節(jié)點(diǎn)m，即,FN(i,m)=1，否則為0，節(jié)點(diǎn)資源約束條件如下：

其中，式（4）表示物理節(jié)點(diǎn)資源能力大于VNR節(jié)點(diǎn)資源請(qǐng)求能力；式（5）表示同一個(gè)虛擬請(qǐng)求中的不同節(jié)點(diǎn)不能被映射到同一個(gè)物理節(jié)點(diǎn)上；式（6）表示若一個(gè)虛擬節(jié)點(diǎn)屬于不同虛擬網(wǎng)絡(luò)請(qǐng)求，則該節(jié)點(diǎn)只能被映射到同一物理節(jié)點(diǎn)上。

與節(jié)點(diǎn)映射矩陣類似，鏈路間的映射關(guān)系用矩陣FL表示，其中行向量代表虛擬鏈路，列向量代表物理鏈路，當(dāng)虛擬節(jié)點(diǎn)i和j分別映射到物理節(jié)點(diǎn)m和n上，(i,j)間的鏈路映射到(m,n)間的路徑時(shí)，即,FL(ij,mn)=1，否則為0。此外，虛擬鏈路映射的所有物理鏈路組成了物理節(jié)點(diǎn)m,n之間的一條無環(huán)路徑p(m,n)，鏈路資源約束條件如下：

其中，式（7）表示物理路徑可用資源大小為該路徑所經(jīng)過的物理鏈路中最小可用資源值；式（8）表示虛擬鏈路資源需求小于物理路徑所提供的可用帶寬資源。在考慮鏈路資源約束的同時(shí)也需要考慮鏈路的連通性約束，如式（9）所示：

若某物理鏈路包含虛擬鏈路的源節(jié)點(diǎn)，式（9）值為1時(shí)表示源節(jié)點(diǎn)流出流量為1、流入流量為0；若某物理鏈路包含虛擬鏈路的目的節(jié)點(diǎn)，式（9）值為-1時(shí)表示目的節(jié)點(diǎn)流出流量為0、流入流量為1；若某物理鏈路不包含虛擬鏈路的源節(jié)點(diǎn)和目的節(jié)點(diǎn)，則流入流量和流出流量平衡，且均為0。

2.3 物理節(jié)點(diǎn)故障分析

當(dāng)某虛擬網(wǎng)絡(luò)請(qǐng)求VNR到達(dá)后，底層物理網(wǎng)絡(luò)判斷是否接受該VNR，若當(dāng)前條件不允許，則拒絕該VNR，不提供物理資源進(jìn)行映射；若當(dāng)前條件允許接受，則物理網(wǎng)絡(luò)要從自身中選擇滿足虛擬網(wǎng)絡(luò)需求的物理節(jié)點(diǎn)和鏈路，映射問題定義為F:(GV→GS*,GS*?GS)，包括節(jié)點(diǎn)映射和鏈路映射兩方面。在節(jié)點(diǎn)映射中通常優(yōu)先選擇可用資源較多的物理節(jié)點(diǎn)作為映射節(jié)點(diǎn)，但與該節(jié)點(diǎn)相連的物理鏈路資源不一定滿足虛擬鏈路映射所需求的資源，如圖（1）所示，圖1（a）中虛擬網(wǎng)絡(luò)請(qǐng)求包含兩個(gè)虛擬節(jié)點(diǎn)和一條虛擬鏈路，圖中數(shù)字表示節(jié)點(diǎn)和鏈路資源需求，圖1（b）所示為物理網(wǎng)絡(luò)，圖中數(shù)字為節(jié)點(diǎn)和鏈路可提供資源。一種節(jié)點(diǎn)映射方案為{a→C,b→A}，但此時(shí)物理鏈路(A,C)間帶寬資源不足以提供給虛擬鏈路(a,b)，導(dǎo)致該虛擬鏈路(a,b)推遲映射，當(dāng)其余虛擬請(qǐng)求完成后，其占用的物理鏈路資源將被釋放掉，釋放的資源再用于對(duì)該鏈路進(jìn)行映射。

圖1 鏈路映射請(qǐng)求推遲

在鏈路映射中，每條物理鏈路的帶寬資源可以被多個(gè)虛擬鏈路所共享，因而會(huì)存在多條虛擬鏈路被映射到同一條物理鏈路這種情況。假如此時(shí)某個(gè)物理節(jié)點(diǎn)發(fā)生故障，則會(huì)導(dǎo)致與該物理節(jié)點(diǎn)相連的周邊物理鏈路失效，使得這些物理鏈路所承載的虛擬鏈路隨之失效，進(jìn)而導(dǎo)致該虛擬網(wǎng)絡(luò)不再連通。如圖2所示為一種虛擬網(wǎng)絡(luò)映射案例，圖2（a）表示某虛擬網(wǎng)絡(luò)請(qǐng)求VNR，圖2（b）代表一種虛擬網(wǎng)絡(luò)映射方案，其中節(jié)點(diǎn)映射方案為{a→A,b→D,c→C},鏈路映射方案為{(a,b)→(A,D),(b,c)→(D,C),(a,c)→(A,D,C)}，假如當(dāng)物理節(jié)點(diǎn)D失效，則導(dǎo)致與其相連的物理鏈路(A,D),(D,C)均失效，進(jìn)而使得映射在其上的虛擬鏈路(a,b),(a,c),(b,c)全部失效，造成虛擬網(wǎng)絡(luò)失去連通性；若使用圖2（c）所示的映射方案，將虛擬鏈路(a,c)映射到(A,B,E,C)，當(dāng)物理節(jié)點(diǎn)D失效時(shí)，虛擬網(wǎng)絡(luò)中a,c之間仍保持連通；如果采用圖2（d）所示的映射方案將虛擬鏈路(a,c)映射到(A,E,C)，相比較方案2而言，虛擬網(wǎng)絡(luò)中a,c之間在保持連通的基礎(chǔ)上占用了較小的開銷，該方案可以取得較理想的結(jié)果。

圖2 虛擬網(wǎng)絡(luò)映射案例

2.4 節(jié)點(diǎn)與鏈路指標(biāo)分析

（1）物理節(jié)點(diǎn)擴(kuò)展資源

在虛擬網(wǎng)絡(luò)節(jié)點(diǎn)映射過程中通常優(yōu)先選擇可用資源較多的物理節(jié)點(diǎn)作為承載節(jié)點(diǎn)，再進(jìn)行鏈路映射，然而這種節(jié)點(diǎn)映射和鏈路映射相互獨(dú)立的方法，會(huì)出現(xiàn)與已映射節(jié)點(diǎn)相連的物理鏈路剩余資源小于虛擬鏈路請(qǐng)求資源的情況，進(jìn)而造成某鏈路映射推遲甚至無法完成鏈路映射。針對(duì)這一問題，文中引入物理節(jié)點(diǎn)擴(kuò)展資源，如式（10）所示：

其中，μ1和μ2為常數(shù)，表示節(jié)點(diǎn)和鏈路資源的重要度，ES⊕ns表示與節(jié)點(diǎn)ns相連的鏈路集。在映射節(jié)點(diǎn)時(shí)，選擇物理節(jié)點(diǎn)擴(kuò)展資源較大的節(jié)點(diǎn)能夠很大程度上避免當(dāng)虛擬節(jié)點(diǎn)映射成功后，由于與映射節(jié)點(diǎn)相連的物理鏈路資源不足而導(dǎo)致的鏈路映射請(qǐng)求被推遲問題。

（2）物理鏈路代價(jià)L(ls)

在無線網(wǎng)絡(luò)中鏈路存在頻繁失效，故需要重點(diǎn)考慮鏈路中斷這一因素，文中綜合考慮鏈路中斷概率、鏈路剩余帶寬和鏈路重要度，并定義如下物理鏈路代價(jià)：

式（11）中bmax(ls)為剩余鏈路中最大帶寬，pmin(ls)為剩余鏈路最小中斷概率，δ(ls)為鏈路ls重要度，λ1和λ2為系數(shù)。式（12）中定義為鏈路標(biāo)識(shí)符，表示鏈路ls是否在已映射的物理路徑h中，若在則為1，否則為0。在映射路徑時(shí)，要選擇那些代價(jià)小的物理鏈路構(gòu)成物理路徑，能夠最大程度上保證該路徑性能最佳。

（3）候選節(jié)點(diǎn)集合Ran(ms)

物理節(jié)點(diǎn)ms發(fā)生故障后，映射在其上的虛擬節(jié)點(diǎn)隨之失效，為保證虛擬請(qǐng)求的正常工作，需要對(duì)失效的虛擬節(jié)點(diǎn)重新映射。在重映射階段，對(duì)故障節(jié)點(diǎn)ms構(gòu)建候選節(jié)點(diǎn)集合可以有效地減少映射時(shí)間，進(jìn)而使虛擬請(qǐng)求得到及時(shí)響應(yīng)，候選節(jié)點(diǎn)集合如式（13）所示，表示與節(jié)點(diǎn)ms間距離不超過δ跳的物理節(jié)點(diǎn)集合：（

4）節(jié)點(diǎn)備用系數(shù)Alter(ns)

虛擬節(jié)點(diǎn)重映射時(shí)，候選節(jié)點(diǎn)集合Ran(ms)中往往存在多個(gè)節(jié)點(diǎn)，而發(fā)生故障次數(shù)多、承載較多虛擬節(jié)點(diǎn)的物理節(jié)點(diǎn)很有可能再次發(fā)生故障，為避免重映射后的節(jié)點(diǎn)發(fā)生故障，文中使用節(jié)點(diǎn)備用系數(shù)Alter(ns)作為選取重映射節(jié)點(diǎn)的依據(jù)，其表達(dá)式如下所示：

式中，numfa(ns)表示節(jié)點(diǎn)發(fā)生故障次數(shù)，numem(ns)表示映射在該節(jié)點(diǎn)上的虛擬節(jié)點(diǎn)個(gè)數(shù)，ω1和ω2分別為二者的比例系數(shù)。在節(jié)點(diǎn)重映射時(shí)，應(yīng)當(dāng)選擇那些故障次數(shù)少、承載較少虛擬節(jié)點(diǎn)的備用節(jié)點(diǎn)進(jìn)行映射。在實(shí)際映射過程中，由于節(jié)點(diǎn)故障次數(shù)和承載節(jié)點(diǎn)個(gè)數(shù)二者在映射過程中均會(huì)存在，且對(duì)于節(jié)點(diǎn)選擇的影響均不可忽略，其重要性程度相差較小。

2.5 評(píng)價(jià)指標(biāo)

（1）虛網(wǎng)請(qǐng)求接受率

在虛擬網(wǎng)絡(luò)請(qǐng)求VNR到來時(shí)，底層網(wǎng)絡(luò)將為其提供物理網(wǎng)絡(luò)資源以供映射，同時(shí)也存在某節(jié)點(diǎn)或鏈路資源受限使得VNR推遲映射或映射失敗問題，文中用虛網(wǎng)請(qǐng)求接受率ξacc衡量VNR成功映射的情況，其表達(dá)式如下：

其中，VNRarr表示在一定時(shí)間內(nèi)到達(dá)的VNR個(gè)數(shù)，VNRacc表示成功映射的VNR個(gè)數(shù)，T表示VNR的生存時(shí)間。

（2）虛擬網(wǎng)絡(luò)恢復(fù)成功率

當(dāng)?shù)讓泳W(wǎng)絡(luò)節(jié)點(diǎn)發(fā)生故障時(shí)，映射在該節(jié)點(diǎn)上的VNR將會(huì)中斷，為了保證VNR服務(wù)的連續(xù)性，該請(qǐng)求需要重新映射至正常的物理節(jié)點(diǎn)和路徑上，文中用虛擬網(wǎng)絡(luò)恢復(fù)成功率ξres表示故障VNR成功恢復(fù)映射的情況：

其中，VNRerr表示因物理節(jié)點(diǎn)發(fā)生故障而失效的VNR個(gè)數(shù)，VNRres表示發(fā)生故障后成功重映射的VNR個(gè)數(shù)。

（3）物理網(wǎng)絡(luò)資源負(fù)載利用率

虛擬網(wǎng)絡(luò)請(qǐng)求映射成功后，底層網(wǎng)絡(luò)的資源被暫時(shí)分配出去從而造成剩余資源減少，若此時(shí)下一個(gè)VNR到達(dá)，則可能發(fā)生某節(jié)點(diǎn)或鏈路的物理剩余資源不足，進(jìn)而導(dǎo)致該VNR映射的時(shí)間變長(zhǎng)。文中定義節(jié)點(diǎn)資源負(fù)載利用率和帶寬資源負(fù)載利用率，若資源負(fù)載利用率越大則代表當(dāng)前底層網(wǎng)絡(luò)資源大部分被占用，VNR映射需要等待的可能性越大。

3 算法設(shè)計(jì)

3.1 虛擬網(wǎng)絡(luò)映射方案

在無線網(wǎng)絡(luò)中，節(jié)點(diǎn)間利用激光或微波鏈路傳輸數(shù)據(jù)，當(dāng)物理網(wǎng)絡(luò)拓?fù)湓谝欢▍^(qū)域時(shí)，由于激光或微波的傳輸特性，一方面可忽略數(shù)據(jù)在鏈路中的傳輸時(shí)延，另一方面需要考慮鏈路中斷在鏈路映射中所帶來的影響[21]。因此文中在虛擬鏈路映射階段不考慮在網(wǎng)絡(luò)鏈路中所產(chǎn)生的時(shí)延，即路徑最短距離由該路徑中所包含的節(jié)點(diǎn)跳數(shù)決定，節(jié)點(diǎn)跳數(shù)越多，則認(rèn)為該路徑距離越長(zhǎng)；此外，無線網(wǎng)絡(luò)鏈路由于受外界干擾或節(jié)點(diǎn)間距離遠(yuǎn)而發(fā)生鏈路中斷，若某鏈路中斷概率越小，則認(rèn)為該鏈路越可靠。

由上述分析，本文提出一種高可靠性的無線虛擬網(wǎng)絡(luò)映射算法（WVNEA-HR），其中該算法包括基于擴(kuò)展資源的節(jié)點(diǎn)映射階段和最小鏈路代價(jià)的鏈路映射階段。針對(duì)無線虛擬網(wǎng)絡(luò)映射問題中的節(jié)點(diǎn)映射和鏈路映射兩個(gè)階段，算法綜合考慮了節(jié)點(diǎn)擴(kuò)展資源以及鏈路中斷概率，WVNEA-HR通過對(duì)虛擬網(wǎng)絡(luò)請(qǐng)求VNR和物理網(wǎng)絡(luò)資源進(jìn)行預(yù)處理，使兩個(gè)映射階段時(shí)間減少，進(jìn)而在一定時(shí)間內(nèi)虛擬網(wǎng)絡(luò)映射的個(gè)數(shù)增多。該虛擬網(wǎng)絡(luò)映射算法主要包括3個(gè)模塊，分別為預(yù)處理模塊、節(jié)點(diǎn)映射模塊和鏈路映射模塊，具體WVNEA-HR算法偽代碼如下所示：

1. for all nv,lv∈VNR do

2.Sort{nv∈VnNodeList,lv∈VnLinkList}//根據(jù)虛擬資源排序

3.end for

4. for all ns,ls∈GSdo

5. if Resource(ns)＞Resourcemin(nv∈VnNodeList)then

6.UtilisablePhysicalNodeList←ns//節(jié)點(diǎn)加入該集合

7. Sort{ns∈UtilisablePhysicalNodeList}//按物理資源排序

8. else VNRList.Last←VNR //推遲映射

9. if Resource(ls)＞Resourcemin(lv∈VnLinkList)then

10. UtilisablePhysicalLinkList←ls

11. Sort{ls∈UtilisablePhysicalLinkList}

12.else VNRList.Last←VNR

13.end for

14.for all nv∈VnNodeListNode(Failure)do

15. if nv=then//最大資源需求的虛擬節(jié)點(diǎn)

16. k=0//設(shè)置虛擬節(jié)點(diǎn)個(gè)數(shù)變量

17. if k＜Num.VnNodeList then

18. for all ns∈UtilisablePhysicalNodeList do

19. if ns＞then//節(jié)點(diǎn)資源是否滿足映射條件

20. NodeSet←ns

21. if NodeSet≠? then

22. Compute cpuex(ns∈NodeSet)//節(jié)點(diǎn)擴(kuò)展資源

23. if cpuex(ns)=cpuex(ns(max))then

24. ns→//節(jié)點(diǎn)映射成功

26. k=k+1

27. update//更新物理節(jié)點(diǎn)資源

28. end if

31. end if

32. end for

33. else Embedded NodeSet←Node(Success)//節(jié) 點(diǎn)映射完畢

34. end if

35. end for

36. for all lv∈VnLinkListLink(Failure)do

37. if lv=then

38. t=0

39. for all t＜Num.VnLinkList do

45. end if

46. if LinkSet≠? then

50. t=t+1

51. update//更新物理鏈路資源

54. end if

55. end if

56. end for

57.end if

58.end for

3.2 失效節(jié)點(diǎn)和鏈路恢復(fù)策略

當(dāng)?shù)讓泳W(wǎng)絡(luò)節(jié)點(diǎn)發(fā)生故障時(shí)，映射在該節(jié)點(diǎn)上的虛擬節(jié)點(diǎn)失效，與其相連的虛擬鏈路也將失效，為了保證虛擬請(qǐng)求的正常工作，需要對(duì)失效節(jié)點(diǎn)以及相連鏈路進(jìn)行重映射。在節(jié)點(diǎn)重映射時(shí)，考慮到虛擬請(qǐng)求的恢復(fù)時(shí)間，因此在故障節(jié)點(diǎn)的臨近范圍內(nèi)選取備用節(jié)點(diǎn)進(jìn)行映射，備用節(jié)點(diǎn)范圍如式（13）所示，其含義為節(jié)點(diǎn)m,n間距離不超過δ跳。節(jié)點(diǎn)恢復(fù)策略如下所示：

輸入：物理網(wǎng)絡(luò)拓?fù)銰S,故障節(jié)點(diǎn)m,節(jié)點(diǎn)跳數(shù)δ輸出：備用節(jié)點(diǎn)n

（1）構(gòu)造備用節(jié)點(diǎn)集合Ran(m)

（2）判斷集合Ran(m)中節(jié)點(diǎn)資源是否滿足虛擬節(jié)點(diǎn)資源需求，將不符合條件的節(jié)點(diǎn)刪除；若集合Ran(m)中的節(jié)點(diǎn)均不滿足，則轉(zhuǎn)向步驟（6）

（3）計(jì)算集合Ran(m)中節(jié)點(diǎn)的備用系數(shù)Alter(ns)，并將結(jié)果按照從小到大排列，選取節(jié)點(diǎn)備用系數(shù)最小的節(jié)點(diǎn)作為虛擬重映射節(jié)點(diǎn)

（4）更新節(jié)點(diǎn)資源

（5）虛擬節(jié)點(diǎn)映射成功

（6）虛擬節(jié)點(diǎn)映射請(qǐng)求被推遲

重映射的節(jié)點(diǎn)在備用節(jié)點(diǎn)集合Ran(m)中產(chǎn)生，這樣在恢復(fù)虛擬網(wǎng)絡(luò)請(qǐng)求的同時(shí)可以減少映射時(shí)間，構(gòu)造備用節(jié)點(diǎn)集合Ran(m)可通過設(shè)置合適的跳數(shù)實(shí)現(xiàn)。虛擬鏈路重映射與鏈路映射方法類似，當(dāng)失效節(jié)點(diǎn)重映射后，針對(duì)失效鏈路，同樣采取基于鏈路代價(jià)的方法對(duì)其進(jìn)行映射，若當(dāng)前資源不允許，則該虛擬鏈路重映射被推遲，等待有足夠資源時(shí)再進(jìn)行修復(fù)。

可以看出，在虛擬節(jié)點(diǎn)初始映射階段對(duì)于節(jié)點(diǎn)的選取是基于節(jié)點(diǎn)擴(kuò)展資源的，而在故障生存重映射階段對(duì)于節(jié)點(diǎn)的選取則是基于節(jié)點(diǎn)備用系數(shù)的，這是因?yàn)樵诔跏茧A段底層網(wǎng)絡(luò)主要是以接受VNR為主，為提高VNR映射成功率，需要重點(diǎn)考慮底層網(wǎng)絡(luò)資源；而在重映射階段由于網(wǎng)絡(luò)故障使得需要重點(diǎn)考慮節(jié)點(diǎn)可靠性，以此確保映射的成功率。

4 仿真結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)置

本文中虛擬網(wǎng)絡(luò)拓?fù)浜臀锢砭W(wǎng)絡(luò)拓?fù)渚捎肎T-ITM工具生成，其中物理網(wǎng)絡(luò)中包含100個(gè)節(jié)點(diǎn)和400條鏈路，每對(duì)節(jié)點(diǎn)之間相連的概率在區(qū)間[0.3，0.6]內(nèi)，物理節(jié)點(diǎn)的計(jì)算資源和鏈路帶寬資源分別服從[30，70]和[30，100]之間的均勻分布。每個(gè)虛擬請(qǐng)求都是隨機(jī)生成的，本文假設(shè)虛擬請(qǐng)求的到達(dá)率滿足每100個(gè)時(shí)間單位到達(dá)4個(gè)的泊松分布，每個(gè)虛擬請(qǐng)求的生存時(shí)間滿足1 000個(gè)時(shí)間單位的指數(shù)分布。虛擬網(wǎng)絡(luò)請(qǐng)求中節(jié)點(diǎn)的計(jì)算資源需求和鏈路帶寬資源需求分別服從[1，10]和[1，20]之間的均勻分布，虛擬請(qǐng)求節(jié)點(diǎn)個(gè)數(shù)服從[2，6]之間的均勻分布，每一對(duì)虛擬節(jié)點(diǎn)之間以0.5的概率相連。在每次仿真實(shí)驗(yàn)中運(yùn)行50 000個(gè)時(shí)間單位，大約包含2 000個(gè)虛擬請(qǐng)求。節(jié)點(diǎn)的失效間隔設(shè)為20 000個(gè)單位，并假定在下一個(gè)節(jié)點(diǎn)失效到來之前上一個(gè)失效節(jié)點(diǎn)已經(jīng)被修復(fù)。將物理節(jié)點(diǎn)擴(kuò)展資源中μ1和μ2分別設(shè)置為0.4和0.6，物理鏈路代價(jià)中λ1和λ2均設(shè)置為0.5，候選節(jié)點(diǎn)集合中跳數(shù)δ設(shè)置為10，為簡(jiǎn)化計(jì)算，節(jié)點(diǎn)備用系數(shù)中ω1和ω2設(shè)置為0.5。

4.2 實(shí)驗(yàn)結(jié)果分析

本文以虛擬請(qǐng)求接受率、虛擬網(wǎng)絡(luò)恢復(fù)成功率、虛擬請(qǐng)求重映射接受率、節(jié)點(diǎn)和鏈路負(fù)載利用率作為算法性能的評(píng)價(jià)指標(biāo)，分別與算法DP-VNE[22]、SVNE-Hybird[23]、VNM-SM[24]進(jìn)行對(duì)比分析，表1所示為幾種算法對(duì)比。

圖3所示為虛擬映射接受率曲線，由于初始階段虛擬網(wǎng)絡(luò)請(qǐng)求少，因而幾種算法都獲得了較高的映射接受率，隨著時(shí)間的推移，幾種算法的性能逐漸趨于平穩(wěn)?？梢钥闯觯琒VNE-Hybird算法初始時(shí)性能略優(yōu)于VNM-SM，這是由于VNM-SM針對(duì)不同服務(wù)采取不同策略，而初始時(shí)刻由于Vn個(gè)數(shù)較少，故性能略低于SVNE-Hybird，而隨著Vn個(gè)數(shù)的增多，SVNE-Hybird算法由于采用備份鏈路策略，因而一定程度上占用了剩余資源，導(dǎo)致其性能低于VNM-SM算法，本文算法WVNEA-HR性能總體上優(yōu)于其余三種算法，是由于在虛擬節(jié)點(diǎn)映射過程中除節(jié)點(diǎn)資源外還考慮與之相連物理鏈路的資源，一定程度上確保了鏈路映射的可靠性，如當(dāng)仿真時(shí)間為10 min時(shí)，DP-VNE算法的接受率降到56%左右，本文所提算法的接受率逐漸穩(wěn)定在67%左右。

表1 算法比較

圖3 虛擬請(qǐng)求接受率

圖4 所示為虛擬網(wǎng)絡(luò)恢復(fù)成功率隨時(shí)間的變化情況，初始映射階段到達(dá)的Vn較少，發(fā)生故障后底層網(wǎng)絡(luò)有足夠多的資源供生存恢復(fù)使用，因而初始階段的恢復(fù)成功率較高，隨著時(shí)間的推移，底層網(wǎng)絡(luò)的資源逐漸被使用，能夠提供的資源減少，因而恢復(fù)成功率變小最終趨于穩(wěn)定。DP-VNE算法的恢復(fù)成功率最低，VNM-SM和本文算法的恢復(fù)成功率相近，文中算法采取了節(jié)點(diǎn)候選集合，當(dāng)物理節(jié)點(diǎn)發(fā)生故障后能夠快速找到其遷移的物理節(jié)點(diǎn)，因而使得發(fā)生失效的虛擬請(qǐng)求能夠迅速恢復(fù)，可以看出，本文算法的恢復(fù)成功率最終穩(wěn)定在66%左右。

圖4 虛擬請(qǐng)求恢復(fù)成功率

圖5 所示為隨著候選集合節(jié)點(diǎn)跳數(shù)的變化虛擬請(qǐng)求重映射接受率的情況，可以看出，虛擬網(wǎng)絡(luò)重映射能否成功在很大程度上取決于網(wǎng)絡(luò)中節(jié)點(diǎn)跳數(shù)的選取。仿真顯示出隨著節(jié)點(diǎn)跳數(shù)的增加(h=5,8,11)，虛擬請(qǐng)求重映射接受率呈現(xiàn)出增大的趨勢(shì)，當(dāng)節(jié)點(diǎn)跳數(shù)h分別為5、8、11時(shí)，對(duì)應(yīng)的請(qǐng)求接受率依次在64%、59%和49%左右，這是由于候選集合中的節(jié)點(diǎn)個(gè)數(shù)增多，使得故障節(jié)點(diǎn)有更多候選節(jié)點(diǎn)資源使用，一定程度上提高了請(qǐng)求接受率。

圖5 虛擬請(qǐng)求重映射接受率

圖6 節(jié)點(diǎn)負(fù)載利用率

圖7 鏈路負(fù)載利用率

節(jié)點(diǎn)資源負(fù)載利用率和鏈路資源負(fù)載利用率仿真如圖6和圖7所示，可以看出，在三種算法的負(fù)載利用率曲線中，本文提出的算法具有較優(yōu)的性能，由于WVNEAHR在節(jié)點(diǎn)映射方面綜合考慮節(jié)點(diǎn)資源和擴(kuò)展資源，使得節(jié)點(diǎn)擴(kuò)展資源較小的節(jié)點(diǎn)被排除，故節(jié)點(diǎn)資源負(fù)載利用率略小于VNM-SM算法，而在鏈路映射階段由于采用最小鏈路代價(jià)策略，有效地避免了底層某條鏈路被多次映射，故其鏈路負(fù)載利用率優(yōu)于其余算法，SVNEHybird算法的負(fù)載利用率高于DP-VNE，DP-VNE算法簡(jiǎn)單將每條虛擬鏈路映射到底層不交叉的鏈路上，沒有更進(jìn)一步的約束條件，其效率最低?？傮w而言，本文算法具有較高的網(wǎng)絡(luò)資源利用率。

5 結(jié)束語

本文主要針對(duì)虛擬網(wǎng)絡(luò)映射過程中鏈路映射階段資源不足以及網(wǎng)絡(luò)故障問題進(jìn)行研究，為確保鏈路映射的成功率，在節(jié)點(diǎn)映射階段采用基于節(jié)點(diǎn)擴(kuò)展資源的映射策略，以此提高鏈路映射成功率，在鏈路映射階段則采用最小鏈路代價(jià)的映射方法。此外在底層網(wǎng)絡(luò)節(jié)點(diǎn)發(fā)生故障時(shí)，文中所提映射算法能夠最大程度保證虛擬請(qǐng)求的連通性，并能夠完成對(duì)虛擬請(qǐng)求失效部分的重映射，結(jié)果表明本文所提算法在滿足虛擬請(qǐng)求可靠映射的同時(shí)，能夠提高虛擬映射接受率和虛擬請(qǐng)求恢復(fù)成功率。現(xiàn)階段關(guān)于虛擬網(wǎng)絡(luò)可靠性映射的研究主要圍繞單節(jié)點(diǎn)失效，關(guān)于多節(jié)點(diǎn)失效和多域映射的研究較少，今后將在現(xiàn)階段的基礎(chǔ)上進(jìn)一步關(guān)于多節(jié)點(diǎn)失效和多域映射展開研究。