繆競(jìng)成, 呂 娜,*, 高 旗, 陳柯帆

(1. 空軍工程大學(xué)信息與導(dǎo)航學(xué)院, 陜西 西安 710077;2. 中國(guó)人民解放軍94860部隊(duì), 江蘇 南京 210000)

0 引 言

航空網(wǎng)絡(luò)是由大規(guī)模有人或無(wú)人飛行器組成的無(wú)線(xiàn)多跳自組織網(wǎng)絡(luò),能夠?yàn)轳R賽克戰(zhàn)下的協(xié)同作戰(zhàn)提供高效的通信服務(wù)[1]。作為航空網(wǎng)絡(luò)的基本組成節(jié)點(diǎn),有人或者無(wú)人飛行器由于環(huán)境干擾、電子阻斷、物理摧毀等因素,會(huì)短時(shí)間或者永久失效。為了應(yīng)對(duì)節(jié)點(diǎn)故障,航空網(wǎng)絡(luò)必須及時(shí)調(diào)度網(wǎng)絡(luò)資源,替換故障節(jié)點(diǎn),以保證任務(wù)順利完成。但是,傳統(tǒng)航空網(wǎng)絡(luò)受限于“煙囪式”、“一站式”的體系設(shè)計(jì)思路,垂直集成的網(wǎng)絡(luò)僵化問(wèn)題日益突出[2-3]。其現(xiàn)有的網(wǎng)絡(luò)靈活性、開(kāi)放性和互操作性水平,難以在節(jié)點(diǎn)故障下快速調(diào)度網(wǎng)絡(luò)資源,從而及時(shí)恢復(fù)網(wǎng)絡(luò)服務(wù)。

網(wǎng)絡(luò)虛擬化作為解決網(wǎng)絡(luò)僵化問(wèn)題的未來(lái)網(wǎng)絡(luò)關(guān)鍵技術(shù),能夠克服網(wǎng)絡(luò)結(jié)構(gòu)變化,靈活調(diào)度網(wǎng)絡(luò)資源[4]。因此,網(wǎng)絡(luò)虛擬化可以為承載戰(zhàn)術(shù)任務(wù)的航空網(wǎng)絡(luò)提供具備更高靈活性、互操作性的資源共享水平。網(wǎng)絡(luò)虛擬化環(huán)境下的航空網(wǎng)絡(luò)中,不同的戰(zhàn)術(shù)任務(wù)應(yīng)用能夠共享具有統(tǒng)一網(wǎng)絡(luò)資源的物理網(wǎng)絡(luò)。同時(shí),在實(shí)際應(yīng)用中,軟件定義網(wǎng)絡(luò)被認(rèn)為是支持網(wǎng)絡(luò)虛擬化的理想平臺(tái)[5]。它能夠通過(guò)網(wǎng)絡(luò)控制器,根據(jù)不同的任務(wù)應(yīng)用需求靈活提供端到端的服務(wù)切片,進(jìn)而減少虛擬化通道的開(kāi)銷(xiāo)[6]。

虛擬網(wǎng)絡(luò)映射[7]是實(shí)現(xiàn)網(wǎng)絡(luò)虛擬化的關(guān)鍵環(huán)節(jié),也是網(wǎng)絡(luò)虛擬化面臨的重大挑戰(zhàn)之一。它需要在虛擬節(jié)點(diǎn)和鏈路的資源約束條件下,將不同的虛擬網(wǎng)絡(luò)映射到統(tǒng)一的底層物理網(wǎng)絡(luò)中,已經(jīng)被證明是多項(xiàng)式復(fù)雜程度的非確定性(nondeterminism polynominal-hard, NP-hand)問(wèn)題?，F(xiàn)有的大量研究[8-13]旨在設(shè)計(jì)高效的啟發(fā)式算法,以提高虛擬網(wǎng)絡(luò)的映射成功率和底層物理網(wǎng)絡(luò)的資源利用率。但是,這些研究主要集中于有線(xiàn)網(wǎng)絡(luò),并且假設(shè)底層物理網(wǎng)絡(luò)無(wú)故障[8-10]。同時(shí),無(wú)線(xiàn)虛擬網(wǎng)絡(luò)映射研究主要考慮鏈路干擾和噪聲[11-12],較少關(guān)注物理網(wǎng)絡(luò)節(jié)點(diǎn)或鏈路故障問(wèn)題[13]。其中,文獻(xiàn)[13]針對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)虛擬化中的鏈路故障問(wèn)題,基于多目標(biāo)遺傳算法為虛擬鏈路重新選擇合適的路徑,但是沒(méi)有考慮節(jié)點(diǎn)故障和無(wú)線(xiàn)干擾對(duì)虛擬網(wǎng)絡(luò)映射的影響。由于無(wú)線(xiàn)傳輸?shù)臄?shù)據(jù)重傳特性,無(wú)線(xiàn)傳輸?shù)墓?jié)點(diǎn)故障問(wèn)題比鏈路故障問(wèn)題更為突出。另一方面,節(jié)點(diǎn)故障會(huì)導(dǎo)致所映射的虛擬節(jié)點(diǎn)和承載的虛擬鏈路無(wú)法提供正常服務(wù),進(jìn)而嚴(yán)重降低虛擬網(wǎng)絡(luò)的映射成功率和物理網(wǎng)絡(luò)的資源利用率。因此,在航空網(wǎng)絡(luò)虛擬化的無(wú)線(xiàn)網(wǎng)絡(luò)環(huán)境下,針對(duì)節(jié)點(diǎn)故障問(wèn)題,研究高效可靠的虛擬網(wǎng)絡(luò)映射算法具有重要意義。

目前,針對(duì)節(jié)點(diǎn)故障的虛擬網(wǎng)絡(luò)映射算法主要基于有線(xiàn)網(wǎng)絡(luò),分為重構(gòu)策略[14-16]和保護(hù)策略[17-19]。重構(gòu)策略是指物理節(jié)點(diǎn)故障后,對(duì)不能正常服務(wù)的虛擬節(jié)點(diǎn)和虛擬鏈路進(jìn)行重新映射。文獻(xiàn)[15]針對(duì)軟件定義網(wǎng)絡(luò)中的單節(jié)點(diǎn)故障問(wèn)題,提出采用區(qū)塊鏈技術(shù)及時(shí)檢測(cè)故障節(jié)點(diǎn)的映射算法。文獻(xiàn)[16]針對(duì)多個(gè)虛擬網(wǎng)絡(luò)組節(jié)點(diǎn)故障問(wèn)題,提出基于平均估計(jì)和優(yōu)先級(jí)的兩種重構(gòu)方法。上述基于重構(gòu)策略的映射算法,存在恢復(fù)時(shí)延長(zhǎng)且成功率難以保證的問(wèn)題。保護(hù)策略是指提前預(yù)備網(wǎng)絡(luò)資源,為關(guān)鍵虛擬節(jié)點(diǎn)和相關(guān)虛擬鏈路提供保護(hù)備份,從而在節(jié)點(diǎn)故障后快速恢復(fù)關(guān)鍵虛擬節(jié)點(diǎn)和相關(guān)虛擬鏈路。文獻(xiàn)[17]為彈性光網(wǎng)絡(luò)虛擬化提出一種針對(duì)單節(jié)點(diǎn)故障的保護(hù)策略,以最小重映射成本為目標(biāo),構(gòu)建輔助拓?fù)浔Ｗo(hù)節(jié)點(diǎn)。為了降低備份資源消耗,可利用P圈保護(hù)技術(shù)恢復(fù)虛擬網(wǎng)絡(luò)映射中節(jié)點(diǎn)或者鏈路故障[18,20]。文獻(xiàn)[18]構(gòu)建P圈為虛擬鏈路映射路徑上的物理節(jié)點(diǎn)提供有效保護(hù)。上述節(jié)點(diǎn)保護(hù)策略需要預(yù)置網(wǎng)絡(luò)資源進(jìn)行節(jié)點(diǎn)保護(hù),一定程度上影響到虛擬網(wǎng)絡(luò)的初始映射,從而降低了映射成功率?？梢缘贸?無(wú)論是選擇重構(gòu)策略或者保護(hù)策略,都會(huì)分別存在恢復(fù)時(shí)延長(zhǎng)或者消耗資源過(guò)多、進(jìn)而降低映射成功率的問(wèn)題。因此,可以采用重構(gòu)與保護(hù)的混合策略,達(dá)到以較低的資源消耗和恢復(fù)時(shí)延提高節(jié)點(diǎn)故障下虛擬網(wǎng)絡(luò)映射成功率的目的。同時(shí),對(duì)于無(wú)線(xiàn)網(wǎng)絡(luò)虛擬化環(huán)境,無(wú)論是重構(gòu)策略還是保護(hù)策略,都必須考慮無(wú)線(xiàn)干擾。

綜上所述,縮短恢復(fù)時(shí)延,降低資源消耗,提高節(jié)點(diǎn)干擾可靠性,是針對(duì)節(jié)點(diǎn)故障的無(wú)線(xiàn)虛擬網(wǎng)絡(luò)映射算法的關(guān)鍵研究點(diǎn)。本文針對(duì)航空網(wǎng)絡(luò)虛擬化中的節(jié)點(diǎn)故障問(wèn)題,提出一種節(jié)點(diǎn)可靠感知的差異保護(hù)虛擬航空網(wǎng)絡(luò)映射(node reliability-aware protection-differentiated virtual airborne network embedding, NRPD-VANE)算法。首先,為了提高節(jié)點(diǎn)干擾可靠性,采用新的節(jié)點(diǎn)重要度評(píng)價(jià)方法,在節(jié)點(diǎn)映射時(shí),綜合感知無(wú)線(xiàn)干擾、網(wǎng)絡(luò)資源和故障可能,選擇可靠的物理節(jié)點(diǎn)映射虛擬節(jié)點(diǎn);其次,為了縮短恢復(fù)時(shí)延和降低消耗資源,采用重構(gòu)與保護(hù)的混合策略:針對(duì)映射虛擬節(jié)點(diǎn)的物理節(jié)點(diǎn)故障問(wèn)題,重新映射虛擬節(jié)點(diǎn)及其鏈路,重新選擇高可靠的物理節(jié)點(diǎn)和路徑;針對(duì)虛擬鏈路映射路徑節(jié)點(diǎn)故障問(wèn)題,對(duì)于路徑上的不可靠節(jié)點(diǎn),根據(jù)物理節(jié)點(diǎn)重要度,采用P圈保護(hù)技術(shù)預(yù)置網(wǎng)絡(luò)資源,進(jìn)行分級(jí)差異保護(hù)。實(shí)驗(yàn)表明,本文提出的算法在保持較低恢復(fù)時(shí)延的同時(shí),提高了映射成功率。

1 網(wǎng)絡(luò)模型及評(píng)價(jià)指標(biāo)

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

(1) 航空網(wǎng)絡(luò)虛擬化模型。航空網(wǎng)絡(luò)受限于“煙囪式”、“一站式”的體系設(shè)計(jì)思路,網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)日益復(fù)雜僵化。網(wǎng)絡(luò)虛擬化技術(shù)可以克服結(jié)構(gòu)變化,靈活調(diào)度網(wǎng)絡(luò)資源。受到軟件定義航空集群機(jī)載戰(zhàn)術(shù)網(wǎng)絡(luò)[21]和虛擬智能工業(yè)無(wú)線(xiàn)網(wǎng)絡(luò)[6]的啟發(fā),設(shè)計(jì)如圖1所示的航空網(wǎng)絡(luò)虛擬化模型。模型由下及上為物理層、虛擬層和應(yīng)用層。

圖1 航空網(wǎng)絡(luò)虛擬化模型Fig.1 Model of airborne network virtualization

首先,在物理層中,有人或無(wú)人飛行器以編隊(duì)形式大量部署在作戰(zhàn)空域。其中,長(zhǎng)機(jī)裝載支持軟件定義網(wǎng)絡(luò)的設(shè)備,進(jìn)而組成大規(guī)模的無(wú)線(xiàn)多跳網(wǎng)絡(luò),稱(chēng)為航空底層網(wǎng)絡(luò)(airborne substrate network, ASN)。其次,在虛擬層中,管理者統(tǒng)一抽象ASN的網(wǎng)絡(luò)資源,服務(wù)于戰(zhàn)術(shù)任務(wù)應(yīng)用。其中,戰(zhàn)術(shù)云代表戰(zhàn)術(shù)數(shù)據(jù)中心,具備強(qiáng)大算力,能夠傳達(dá)部署戰(zhàn)術(shù)任務(wù)和收集處理態(tài)勢(shì)信息,運(yùn)行虛擬網(wǎng)絡(luò)映射算法,以重疊的方式編排多個(gè)戰(zhàn)術(shù)任務(wù)應(yīng)用切片。最后,在應(yīng)用層中,多樣化戰(zhàn)術(shù)任務(wù)應(yīng)用可以抽象為相互隔離、邏輯自定義的航空虛擬網(wǎng)絡(luò)(airborne virtual network, AVN),并配備專(zhuān)用軟件定義網(wǎng)絡(luò)控制器,以支持AVN更改拓?fù)?定制應(yīng)用服務(wù)需求。例如,AVN1抽象于某偵察任務(wù),由飛行器節(jié)點(diǎn)2、3、4、5和云端接入節(jié)點(diǎn)1以及之間的無(wú)線(xiàn)鏈路組成。虛擬層的管理者將AVN1的虛擬節(jié)點(diǎn)和鏈路映射至ASN的相應(yīng)物理節(jié)點(diǎn)和路徑中。因此,AVN1能夠利用統(tǒng)一的航空網(wǎng)絡(luò)資源,高效收集態(tài)勢(shì)信息,及時(shí)完成任務(wù)。

(2) ASN和AVN。ASN用賦權(quán)無(wú)向圖GS=(NS,LS)表示,NS和LS分別表示物理節(jié)點(diǎn)集合和物理鏈路集合。物理節(jié)點(diǎn)n的屬性包括傳輸功率tpS和位置loc(n)。其中,tpS包括編隊(duì)內(nèi)傳輸功率tpb(n)和編隊(duì)間傳輸功率tp(n)。物理鏈路的lS屬性包括鏈路傳輸帶寬b(lS)和相對(duì)位置loc(lS)。同時(shí),pS表示一條無(wú)環(huán)物理路徑。同樣,AVN用賦權(quán)無(wú)向圖GV=(NV,LV)表示,NV和LV分別表示虛擬節(jié)點(diǎn)集合和虛擬鏈路集合。虛擬節(jié)點(diǎn)v的屬性包括位置loc(v)和映射范圍φV。虛擬鏈路lV的屬性為傳輸速率TR(lV)。在A(yíng)VN的映射過(guò)程中,同一虛擬網(wǎng)絡(luò)的不同虛擬節(jié)點(diǎn)應(yīng)映射到不同的物理節(jié)點(diǎn)上,且一個(gè)虛擬節(jié)點(diǎn)只能映射至一個(gè)物理節(jié)點(diǎn)。

(3) 虛擬網(wǎng)絡(luò)映射過(guò)程和節(jié)點(diǎn)故障影響。虛擬網(wǎng)絡(luò)映射包括節(jié)點(diǎn)映射和鏈路映射,要在滿(mǎn)足節(jié)點(diǎn)和鏈路資源的約束條件下,將虛擬節(jié)點(diǎn)和鏈路分別映射到物理網(wǎng)絡(luò)的相關(guān)節(jié)點(diǎn)和路徑上。物理節(jié)點(diǎn)故障會(huì)同時(shí)影響到已經(jīng)映射的虛擬節(jié)點(diǎn)和鏈路,從而導(dǎo)致虛擬網(wǎng)絡(luò)映射失敗。如圖2所示,AVN1和AVN2共同映射到ASN上。虛擬鏈路上的數(shù)字代表傳輸速率,物理鏈路上的數(shù)字代表傳輸帶寬,物理節(jié)點(diǎn)旁的數(shù)字代表編隊(duì)間傳輸功率。以AVN1為例,節(jié)點(diǎn)映射方案為{x→C,y→E,z→B},鏈路映射方案為{(x,y)→(C,G,E),(x,z)→(C,D,B)}。同時(shí),物理節(jié)點(diǎn)E出現(xiàn)故障后,其鄰接物理鏈路隨之失效。對(duì)于A(yíng)VN1,虛擬節(jié)點(diǎn)y和虛擬鏈路(x,y)失效。對(duì)于A(yíng)VN2,由于E為虛擬鏈路(a,c)的所映射路徑(F,E,G)上的轉(zhuǎn)發(fā)節(jié)點(diǎn),虛擬鏈路(a,c)失效。

圖2 AVN映射過(guò)程和節(jié)點(diǎn)故障影響Fig.2 Embedding process of AVN and impacts of node failure

1.2 主要評(píng)價(jià)指標(biāo)

(1) 映射成功率。虛擬網(wǎng)絡(luò)映射成功率是表示映射效率的重要指標(biāo)。其表達(dá)式如下所示:

(1)

式中:NUMEmb(t)是在t時(shí)刻已經(jīng)成功映射并在節(jié)點(diǎn)故障下正常運(yùn)行的虛擬網(wǎng)絡(luò)集合數(shù);NUMv(t)是t時(shí)刻到達(dá)的虛擬網(wǎng)絡(luò)請(qǐng)求集合數(shù);δ為無(wú)限接近于零的常數(shù)。

(2) 平均恢復(fù)時(shí)延。平均恢復(fù)時(shí)延能夠衡量因物理節(jié)點(diǎn)故障而失效的虛擬節(jié)點(diǎn)和鏈路的恢復(fù)速度。與式(1)類(lèi)似,對(duì)于成功恢復(fù)的受影響的虛擬節(jié)點(diǎn)和鏈路,平均恢復(fù)時(shí)延表示為在t時(shí)刻其總恢復(fù)時(shí)延與總數(shù)目之間的比值。

(3) 平均收益開(kāi)銷(xiāo)比。平均收益開(kāi)銷(xiāo)比表示虛擬網(wǎng)絡(luò)映射收益與映射成本之間的比值,是衡量資源利用效率的重要指標(biāo),具體表示如下:

(2)

式中:T表示虛擬網(wǎng)絡(luò)的總持續(xù)時(shí)間;VNmap(t)是t時(shí)刻已經(jīng)成功映射的虛擬網(wǎng)絡(luò)集合;R(GV,t)和C(GV,t)分別表示為

(3)

(4)

式中:R(GV,t)表示t時(shí)刻虛擬網(wǎng)絡(luò)映射的收益;β表示平衡節(jié)點(diǎn)功率資源和鏈路帶寬資源的系數(shù);p(n)|v→n表示映射虛擬節(jié)點(diǎn)v、物理節(jié)點(diǎn)n使用的功率資源;b(lS)|lV→pS表示映射虛擬鏈路lV、物理路徑pS上某鏈路lS使用的帶寬資源;|pS|為pS上的鏈路集合數(shù);C(GV,t)表示t時(shí)刻虛擬網(wǎng)絡(luò)映射的成本,相比于R(GV,t),需要考慮映射路徑上占用的所有鏈路帶寬資源;α與β類(lèi)似,同為系數(shù)。

2 NRPD-VANE算法

本文提出的NRPD-VANE算法,采用新的節(jié)點(diǎn)重要度評(píng)價(jià)方法,綜合感知無(wú)線(xiàn)干擾、網(wǎng)絡(luò)資源和故障可能,全面評(píng)價(jià)物理節(jié)點(diǎn)的重要度,為虛擬節(jié)點(diǎn)映射可靠的物理節(jié)點(diǎn)。同時(shí),根據(jù)物理節(jié)點(diǎn)重要度,對(duì)虛擬鏈路映射路徑上的不可靠物理節(jié)點(diǎn)實(shí)行差異化保護(hù)。

2.1 節(jié)點(diǎn)可靠感知

為了提高節(jié)點(diǎn)干擾的可靠性,節(jié)點(diǎn)映射需要綜合感知無(wú)線(xiàn)干擾和故障可能下的物理節(jié)點(diǎn)狀態(tài)信息,考慮無(wú)線(xiàn)干擾、網(wǎng)絡(luò)資源和故障可能,以評(píng)價(jià)物理節(jié)點(diǎn)的重要程度,從而為虛擬節(jié)點(diǎn)選擇重要度高(即相對(duì)可靠)的物理節(jié)點(diǎn)。

虛擬節(jié)點(diǎn)重要度NoV(v)和物理節(jié)點(diǎn)重要度NoV(n),分別表示為

(5)

(6)

式中:Lv為虛擬節(jié)點(diǎn)v的鄰接虛擬鏈路集合;Ln為物理節(jié)點(diǎn)n的鄰接物理鏈路集合;SF(n)為故障因子,表示物理節(jié)點(diǎn)的故障程度;TR(lS)為物理節(jié)點(diǎn)鄰接鏈路lS在復(fù)雜干擾條件下可能達(dá)到的傳輸速率。TR(lS)和SF(n)的具體表示分別為

(7)

(8)

式中:g(lS)為鏈路lS的信道增益;Inf(n)為節(jié)點(diǎn)n受到的干擾的功率大小;Inf(lS)為鏈路lS受到干擾的功率大小。該式利用香農(nóng)公式,考慮了環(huán)境干擾和網(wǎng)絡(luò)資源。其中,環(huán)境干擾體現(xiàn)在節(jié)點(diǎn)和鏈路受到的干擾功率,網(wǎng)絡(luò)資源體現(xiàn)在節(jié)點(diǎn)功率資源p(n)和鄰接鏈路帶寬資源b(lS);h為物理節(jié)點(diǎn)n的故障次數(shù);σ為常數(shù);Φ為故障的物理節(jié)點(diǎn)集合;dij為物理節(jié)點(diǎn)ni和nj之間的跳數(shù)距離。當(dāng)h=0時(shí),物理節(jié)點(diǎn)ni在映射當(dāng)前虛擬網(wǎng)絡(luò)之前沒(méi)有故障,故SF(ni)=1,ni在一定程度上是可靠的;當(dāng)h>0時(shí),ni至少出現(xiàn)過(guò)一次故障,同時(shí)故障的次數(shù)越多或者越處于故障節(jié)點(diǎn)集合的中心,SF(ni)越小,即ni越不可靠。

綜合式(6)、式(7)和式(8),物理節(jié)點(diǎn)重要度NoV(n)表示為

(9)

物理節(jié)點(diǎn)重要度綜合考慮了無(wú)線(xiàn)干擾、網(wǎng)絡(luò)資源和故障可能,全面量化評(píng)價(jià)了物理節(jié)點(diǎn)在無(wú)線(xiàn)干擾和故障可能下的重要度。

2.2 節(jié)點(diǎn)差異化保護(hù)

鏈路映射將AVN的虛擬鏈路映射到ASN的物理路徑上。路徑節(jié)點(diǎn)故障會(huì)導(dǎo)致虛擬鏈路失效。根據(jù)節(jié)點(diǎn)可靠感知得到物理節(jié)點(diǎn)重要度,采用P圈保護(hù)技術(shù),對(duì)路徑上的不可靠節(jié)點(diǎn)進(jìn)行差異化保護(hù)。

2.2.1 路徑節(jié)點(diǎn)故障問(wèn)題及P圈保護(hù)策略

對(duì)于路徑上的不可靠節(jié)點(diǎn),P圈技術(shù)能夠預(yù)備網(wǎng)絡(luò)資源進(jìn)行主動(dòng)保護(hù),提供徑上保護(hù)和跨徑保護(hù)兩種保護(hù)策略,資源配置效率高、恢復(fù)速度快。

(1) 徑上保護(hù)

將映射路徑上的不可靠節(jié)點(diǎn)置于P圈之上。如圖3(a)所示,P圈{D,B,F,I,E,D}為不可靠節(jié)點(diǎn)E提供保護(hù)。當(dāng)節(jié)點(diǎn)E出現(xiàn)故障后,{D,E,I}可由{D,B,F,I}替換,映射路徑可恢復(fù)工作。

圖3 P圈的兩種保護(hù)策略Fig.3 Two protection strategies of P-Cycle technology

(2) 跨徑保護(hù)

將映射路徑上的不可靠節(jié)點(diǎn)置于備份路徑的跨接路徑之上。如圖3(b)所示,P圈{D,B,F,I,E,G,C,D}為跨接路徑{D,E,I}上的不可靠節(jié)點(diǎn)E提供保護(hù)。當(dāng)節(jié)點(diǎn)E出現(xiàn)故障后,{D,E,I}可由{D,B,F,I}或{D,C,G,I}替換。

相比于徑上保護(hù),跨徑保護(hù)可以提供雙重保護(hù)路徑,但需要預(yù)置更多的網(wǎng)絡(luò)資源。在資源有限的物理網(wǎng)絡(luò)中,對(duì)所有不可靠的映射路徑節(jié)點(diǎn)采用跨徑保護(hù),將會(huì)消耗大量網(wǎng)絡(luò)資源,影響其他正常虛擬網(wǎng)絡(luò)的成功映射。同時(shí),如果都采用徑上保護(hù),難以對(duì)不可靠節(jié)點(diǎn)進(jìn)行充分的保護(hù),降低故障恢復(fù)成功率。所以,為路徑節(jié)點(diǎn)提供有效的分級(jí)保護(hù),具有重要意義。同時(shí),P圈的建立,需要尋找節(jié)點(diǎn)故障影響下的可靠路徑。

2.2.2 路徑節(jié)點(diǎn)差異保護(hù)

對(duì)于映射路徑上的物理節(jié)點(diǎn),根據(jù)節(jié)點(diǎn)重要度NoV(n),將節(jié)點(diǎn)風(fēng)險(xiǎn)程度NoV%(n)定義為

(10)

本文根據(jù)節(jié)點(diǎn)風(fēng)險(xiǎn)程度NoV%(n),分級(jí)確定不可靠節(jié)點(diǎn)的保護(hù)策略PS(n),定義如下:

(11)

式中:數(shù)字0表示節(jié)點(diǎn)無(wú)保護(hù);數(shù)字1表示節(jié)點(diǎn)徑上保護(hù);數(shù)字2表示節(jié)點(diǎn)跨徑保護(hù);Γ1和Γ2均表示保護(hù)策略的選擇變量,可根據(jù)網(wǎng)絡(luò)虛擬化環(huán)境進(jìn)行設(shè)定。

PS(n)=0時(shí),路徑節(jié)點(diǎn)風(fēng)險(xiǎn)較低,不配置保護(hù)路徑,節(jié)點(diǎn)故障時(shí),重新尋找可靠節(jié)點(diǎn)為路徑替換故障節(jié)點(diǎn);PS(n)=1,路徑節(jié)點(diǎn)風(fēng)險(xiǎn)較高,構(gòu)建P圈,配置如圖3(a)所示的單條保護(hù)路徑;PS(n)=2時(shí),路徑節(jié)點(diǎn)風(fēng)險(xiǎn)很高,構(gòu)建P圈,配置如圖3(b)所示的雙重保護(hù)路徑。

在式(11)中,對(duì)于路徑節(jié)點(diǎn)n,當(dāng)節(jié)點(diǎn)風(fēng)險(xiǎn)程度NoV%(n)不大于Γ2時(shí),PS(n)=1或PS(n)=2,相應(yīng)地需要構(gòu)建P圈進(jìn)行徑上保護(hù)或跨徑保護(hù)。本文采用最短路徑Dijkstra算法構(gòu)建P圈保護(hù)路徑,其鏈路權(quán)值定義為

(12)

2.3 算法流程

如算法1所示,NRPD-VANE算法流程分為可靠映射(第1行至第21行)和故障恢復(fù)(第22行至第25行)兩個(gè)階段。在可靠映射階段,本文采用一階段式映射,即在節(jié)點(diǎn)映射的同時(shí)考慮鏈路映射,以提高虛擬網(wǎng)絡(luò)映射的長(zhǎng)期收益。對(duì)于節(jié)點(diǎn)映射(第3行至第6行),采用貪婪式映射方法,選擇重要度最大的虛擬節(jié)點(diǎn)和物理節(jié)點(diǎn)進(jìn)行匹配。對(duì)于鏈路映射(第7行至第20行),采用文獻(xiàn)[3]中的無(wú)線(xiàn)鏈路映射方法,為虛擬鏈路尋找可靠路徑。同時(shí),由式(11)確定路徑上風(fēng)險(xiǎn)節(jié)點(diǎn)的差異保護(hù)策略。在故障恢復(fù)階段,在節(jié)點(diǎn)故障時(shí),對(duì)受到影響的虛擬節(jié)點(diǎn)和鏈路,依據(jù)差異保護(hù)策略進(jìn)行恢復(fù)。

NRPD-VANE算法的時(shí)間復(fù)雜度主要包括可靠映射的時(shí)間復(fù)雜度和故障恢復(fù)的時(shí)間復(fù)雜度。由于故障恢復(fù)的最大時(shí)間復(fù)雜度在于重新進(jìn)行可靠映射,即將所有虛擬節(jié)點(diǎn)和鏈路重新映射。所以,NRPD-VANE算法的時(shí)間復(fù)雜度主要由可靠映射的時(shí)間復(fù)雜度決定?？煽坑成涞臅r(shí)間復(fù)雜度主要包括節(jié)點(diǎn)映射時(shí)間復(fù)雜度和鏈路映射時(shí)間復(fù)雜度。節(jié)點(diǎn)映射時(shí)間復(fù)雜度為O(|NS|2),其中|NS|表示物理節(jié)點(diǎn)總數(shù)。鏈路映射時(shí)間復(fù)雜度為O(|LV||NS|(|LS|+|NS|log2(|NS|))),其中|LS|和|LV|分別為物理鏈路和虛擬鏈路總數(shù)。由于采用一階段式映射,故可靠映射的時(shí)間復(fù)雜度為O(|NV|(|NS|2+|LV||NS|(|LS|+|NS|log2(|NS|)))),其中|NV|為虛擬節(jié)點(diǎn)總數(shù)。因此,本文所提NRPD-VANE算法的總時(shí)間復(fù)雜度為O(|NV|(|NS|2)+|LV||NS|·(LS+|NS|log2(|NS|))))。

3 實(shí)驗(yàn)仿真

本節(jié)通過(guò)映射成功率、平均收益開(kāi)銷(xiāo)比、平均恢復(fù)時(shí)延等3個(gè)重要評(píng)價(jià)指標(biāo),進(jìn)行不同算法的對(duì)比,驗(yàn)證所提NRPD-VANE算法的綜合性能。

3.1 仿真環(huán)境設(shè)置

ASN和AVN的網(wǎng)絡(luò)拓?fù)溆筛倪M(jìn)的Salam網(wǎng)絡(luò)拓?fù)潆S機(jī)生成算法[22]生成。該網(wǎng)絡(luò)生成算法使用K均值聚類(lèi)提高網(wǎng)絡(luò)拓?fù)溥B通性和均勻性,同時(shí)具有豐富的網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)。ASN在200 km×200 km范圍內(nèi)生成均勻分布的50個(gè)節(jié)點(diǎn)和139條鏈路。物理節(jié)點(diǎn)設(shè)定具有足夠的編隊(duì)內(nèi)傳輸功率資源,其編隊(duì)間傳輸功率資源tp(n)服從[50, 100]的均勻分布,單位為W。無(wú)線(xiàn)鏈路的帶寬資源服從[20, 50]的均勻分布,單位為MHz。AVN到達(dá)服從泊松分布,到達(dá)時(shí)間單元為100,到達(dá)個(gè)數(shù)期望為5。AVN的生存時(shí)間服從期望為1 000個(gè)時(shí)間單元的指數(shù)分布。虛擬節(jié)點(diǎn)的數(shù)目服從[3, 5]的均勻分布,假設(shè)任意虛擬節(jié)點(diǎn)的映射范圍為100 km。虛擬鏈路的傳輸速率需求服從[3, 8]的均勻分布,單位為Mbit/s。

在式(3)、式(4)、式(8)和式(12)中,α、β、σ和γ均設(shè)為1。式(7)中,g(lS)=d-k,其中d為無(wú)線(xiàn)鏈路終端節(jié)點(diǎn)之間的歐式距離,k表示信道衰落系數(shù),k設(shè)為4。每個(gè)物理節(jié)點(diǎn)設(shè)有故障值Inf(n)+10-4Rf(n),其中Rf(n)服從[1, 10]的均勻分布。仿真實(shí)驗(yàn)運(yùn)行總時(shí)間為20 000個(gè)時(shí)間單元。為了消除隨機(jī)因素影響,共進(jìn)行10次實(shí)驗(yàn),取其平均值作為最終仿真結(jié)果。仿真設(shè)定,每過(guò)2 000個(gè)時(shí)間單元,故障值最高的物理節(jié)點(diǎn)會(huì)發(fā)生故障,同時(shí)以50%的概率在故障發(fā)生后的1 000個(gè)時(shí)間單元內(nèi)恢復(fù)。

3.2 不同算法對(duì)比

本文對(duì)比分析了4種針對(duì)節(jié)點(diǎn)故障的虛擬網(wǎng)絡(luò)映射算法(見(jiàn)表1),且都是在相同的ASN上接受處理AVN。由于部分算法是在有線(xiàn)網(wǎng)絡(luò)中考慮節(jié)點(diǎn)故障,為了消除有線(xiàn)虛擬網(wǎng)絡(luò)映射方法對(duì)仿真結(jié)果的影響,所有有線(xiàn)虛擬網(wǎng)絡(luò)節(jié)點(diǎn)映射方法均采用文獻(xiàn)[3]作為基本的虛擬網(wǎng)絡(luò)映射方法。同時(shí),部分算法未考慮節(jié)點(diǎn)故障對(duì)虛擬節(jié)點(diǎn)映射節(jié)點(diǎn)和鏈路映射路徑上節(jié)點(diǎn)的影響,則統(tǒng)一設(shè)定為重新映射受到影響的虛擬節(jié)點(diǎn)或鏈路。

表1 算法對(duì)比

在仿真環(huán)境中,干擾表示tpb(n)/Inf(n)=1, 即由S/N=101g(tpb(n)/Inf(n))為0 dB。實(shí)驗(yàn)結(jié)果如圖4～圖7所示。在圖4～圖6中,對(duì)于NRPD-VANE算法,Γ1=10%,Γ2=20%。圖7表示NRPD-VANE算法在不同的Γ1和Γ2下映射成功率的變化情況。

圖4 不同算法的映射成功率變化情況Fig.4 Change of the embedding success rate of different algorithms

圖4為4種算法在相同實(shí)驗(yàn)條件下映射成功率隨時(shí)間的變化圖。SVNE-ORP算法的映射成功率較低,穩(wěn)定狀態(tài)保持在0.46左右。這是因?yàn)?SVNE-ORP算法需要為虛擬節(jié)點(diǎn)及其鄰接鏈路預(yù)置備份虛擬節(jié)點(diǎn)及相關(guān)鏈路,消耗大量網(wǎng)絡(luò)資源,沒(méi)有足夠資源映射新到達(dá)的虛擬網(wǎng)絡(luò)。VNM-CNLP算法只為虛擬鏈路、消耗網(wǎng)絡(luò)資源配置P圈,相比于SVNE-ORP算法消耗較少的網(wǎng)絡(luò)資源,故其映射成功率高于SVNE-ORP算法,穩(wěn)定狀態(tài)保持在0.53左右。Fast-ReNoVatE算法不為虛擬節(jié)點(diǎn)或鏈路預(yù)置節(jié)點(diǎn),有相對(duì)足夠的網(wǎng)絡(luò)資源對(duì)新到達(dá)的虛擬網(wǎng)絡(luò)進(jìn)行映射,故映射成功率保持在0.57左右。本文提出的NRPD-VANE算法,為虛擬節(jié)點(diǎn)選擇可靠性高的物理節(jié)點(diǎn),同時(shí)采用混合保護(hù)策略,重映射節(jié)點(diǎn)故障影響的虛擬節(jié)點(diǎn),差異化保護(hù)路徑節(jié)點(diǎn),降低了配置P圈的網(wǎng)絡(luò)資源消耗。而Fast-ReNoVatE算法由于只采用重映射的方式,在網(wǎng)絡(luò)資源利用率接近飽和的仿真中后期,在受到節(jié)點(diǎn)故障影響時(shí),難以成功恢復(fù)失效的虛擬節(jié)點(diǎn)或鏈路。故NRPD-VANE算法的映射成功率在穩(wěn)定狀態(tài)下最高,保持在0.63左右。

圖5為4種算法平均收益開(kāi)銷(xiāo)比的比較。SVNE-ORP算法需要消耗網(wǎng)絡(luò)資源,為虛擬節(jié)點(diǎn)及鄰接虛擬鏈路配置物理節(jié)點(diǎn)和路徑,進(jìn)行備份保護(hù),具有較大的映射開(kāi)銷(xiāo)。同時(shí),SVNE-ORP算法具有較低的映射成功率,收益也相對(duì)較低。根據(jù)式(2)可知,SVNE-ORP算法的平均收益開(kāi)銷(xiāo)比較低,穩(wěn)定狀態(tài)只保持在0.41左右。VNM-CNLP算法只為虛擬鏈路消耗資源配置P圈,減小了開(kāi)銷(xiāo),平均收益開(kāi)銷(xiāo)比得到了一定程度的提高,穩(wěn)定狀態(tài)保持在0.45左右。Fast-ReNoVatE算法只采用重構(gòu)策略,開(kāi)銷(xiāo)較少,平均收益開(kāi)銷(xiāo)比有進(jìn)一步的提高,穩(wěn)定狀態(tài)保持在0.48左右。本文所提的NRPD-VANE算法,采用差異化保護(hù),提高了資源利用率,相比于SVNE-ORP算法和VNM-CNLP算法降低了開(kāi)銷(xiāo),同時(shí)映射成功率最高,相比于Fast-ReNoVatE算法增加了收益,故平均收益開(kāi)銷(xiāo)比最高,穩(wěn)定狀態(tài)保持在0.52左右。

圖5 不同算法的平均收益開(kāi)銷(xiāo)比變化情況Fig.5 Change of the average revenue to cost ratio of different algorithms

圖6比較了4種算法在相同實(shí)驗(yàn)條件下的平均恢復(fù)時(shí)延。

圖6 不同算法的平均恢復(fù)時(shí)延變化情況Fig.6 Change of the average recovery delay of different algorithms

由圖6可知,Fast-ReNoVatE算法的平均恢復(fù)時(shí)延較長(zhǎng),穩(wěn)定狀態(tài)保持在29.2 ms左右。這是因?yàn)镕ast-ReNoVatE算法在節(jié)點(diǎn)故障時(shí)只采用重映射策略,需要花費(fèi)一定的時(shí)間為受到影響的虛擬節(jié)點(diǎn)或鏈路找到合適的物理節(jié)點(diǎn)或路徑。VNM-CNLP算法為虛擬鏈路預(yù)置網(wǎng)絡(luò)資源構(gòu)建P圈保護(hù)路徑,在節(jié)點(diǎn)故障時(shí)只需要激活P圈,花費(fèi)的時(shí)間較少,平均恢復(fù)時(shí)延較短,穩(wěn)定狀態(tài)保持在14.3 ms左右。SVNE-ORP算法為關(guān)鍵虛擬節(jié)點(diǎn)及其鄰接鏈路預(yù)配置備用物理節(jié)點(diǎn)及路徑,節(jié)點(diǎn)故障時(shí)只需要激活節(jié)點(diǎn)及路徑,平均恢復(fù)時(shí)延更短,穩(wěn)定狀態(tài)保持在12.5 ms左右。本文提出的NRPD-VANE算法,平均恢復(fù)時(shí)延穩(wěn)定狀態(tài)保持在13.3 ms左右。相比VNM-CNLP算法,對(duì)虛擬鏈路的對(duì)應(yīng)路徑節(jié)點(diǎn)進(jìn)行差異保護(hù),提高了資源利用率,有更多網(wǎng)絡(luò)資源以便重新映射受到節(jié)點(diǎn)故障影響的虛擬節(jié)點(diǎn),故穩(wěn)定狀態(tài)下的平均恢復(fù)時(shí)延減少。相比SVNE-ORP算法,未給虛擬節(jié)點(diǎn)進(jìn)行備份保護(hù),故平均恢復(fù)時(shí)延有所升高。

圖7比較了NRPD-VANE算法在不同Γ1和Γ2下的映射成功率。

圖7 不同的Γ1和Γ2下映射成功率的變化情況Fig.7 Change of the embedding success rate under different Γ1 and Γ2

在圖7中,藍(lán)色圓形標(biāo)記的折線(xiàn)表示NRPD-VANE算法對(duì)路徑上的不可靠節(jié)點(diǎn)只采用跨徑保護(hù)策略,其穩(wěn)定狀態(tài)的映射成功率隨Γ1變化的情況。當(dāng)Γ1達(dá)到15%左右時(shí),NRPD-VANE算法能夠達(dá)到的穩(wěn)定狀態(tài)下映射成功率最高,約為0.61。同時(shí),紅色方框標(biāo)記的折線(xiàn)表示只采用徑上保護(hù)策略時(shí)穩(wěn)定狀態(tài)的映射成功率隨Γ2變化的情況。當(dāng)Γ2達(dá)到25%左右時(shí),NRPD-VANE算法能達(dá)到的穩(wěn)定狀態(tài)下映射成功率最高,約為0.60。結(jié)合圖4可知,只采用徑上保護(hù)或跨徑保護(hù),難以進(jìn)一步提高節(jié)點(diǎn)故障影響下的映射成功率。所以,本文設(shè)置Γ1=10%和Γ2=20%,可以使NRPD-VANE算法的映射成功率穩(wěn)定狀態(tài)達(dá)到0.63左右。

4 結(jié) 論

為解決航空網(wǎng)絡(luò)虛擬化節(jié)點(diǎn)故障下的可靠映射問(wèn)題,本文提出一種網(wǎng)絡(luò)虛擬化環(huán)境下的節(jié)點(diǎn)差異保護(hù)映射算法。該算法的優(yōu)勢(shì)與特點(diǎn)如下:首先,節(jié)點(diǎn)映射綜合感知了故障可能、環(huán)境干擾和網(wǎng)絡(luò)資源,為虛擬節(jié)點(diǎn)尋找可靠的物理節(jié)點(diǎn)。然后,鏈路映射根據(jù)節(jié)點(diǎn)重要度,采用P圈保護(hù)技術(shù),為映射路徑上的不可靠節(jié)點(diǎn)提供差異化保護(hù),提高了資源利用率。最后,由仿真對(duì)比可知,所提算法在具有較低的故障恢復(fù)時(shí)延的同時(shí),在一定程度上提高了映射成功率和平均收益開(kāi)銷(xiāo)比,具有工程應(yīng)用價(jià)值。