基于負(fù)載均衡的無(wú)線虛擬網(wǎng)絡(luò)映射算法

高旗，呂娜，繆競(jìng)成

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

0 引言

為了滿足無(wú)線網(wǎng)絡(luò)用戶多樣化的業(yè)務(wù)需求，具有緊密耦合架構(gòu)的無(wú)線網(wǎng)絡(luò)只能基于已有的設(shè)備和服務(wù)進(jìn)行更新，而堆疊式的更新部署使得無(wú)線網(wǎng)絡(luò)出現(xiàn)結(jié)構(gòu)冗余、發(fā)展困難的僵化問(wèn)題［1］。

無(wú)線網(wǎng)絡(luò)虛擬化（Wireless Network Virtualization，WNV）是解決無(wú)線網(wǎng)絡(luò)僵化問(wèn)題的有效方式［2］，基本思想是解耦，通過(guò)統(tǒng)一的資源調(diào)度和網(wǎng)絡(luò)管理為用戶提供差異化網(wǎng)絡(luò)服務(wù)。無(wú)線網(wǎng)絡(luò)虛擬化將無(wú)線網(wǎng)絡(luò)抽象為基礎(chǔ)設(shè)施提供商（Infrastructure Provider，InP）和服務(wù)提供商（Service Provider，SP）。其中InP 負(fù)責(zé)底層物理網(wǎng)絡(luò)的管理和資源分配，SP 負(fù)責(zé)租賃使用資源為用戶提供服務(wù)，所有的SP 均向一個(gè)InP 請(qǐng)求網(wǎng)絡(luò)資源，實(shí)現(xiàn)資源共享。

在無(wú)線網(wǎng)絡(luò)虛擬化過(guò)程中，虛擬網(wǎng)絡(luò)映射（Virtual Network Embedding，VNE）是其中的重要手段［3］，解決如何將InP 的網(wǎng)絡(luò)資源分配給不同的SP 進(jìn)而提供服務(wù)的問(wèn)題。映射過(guò)程主要包括節(jié)點(diǎn)映射和鏈路映射，因此將虛擬網(wǎng)絡(luò)映射問(wèn)題抽象為如何在滿足約束條件的情況下，為虛擬網(wǎng)絡(luò)選擇合適的物理節(jié)點(diǎn)和鏈路。

相較于有線網(wǎng)絡(luò)，無(wú)線網(wǎng)絡(luò)鏈路資源有限且存在干擾，映射時(shí)需考慮干擾對(duì)資源分配以及服務(wù)質(zhì)量（Quality of Service，QoS）的影響，因此無(wú)線虛擬網(wǎng)絡(luò)映射算法主要針對(duì)優(yōu)化資源分配［4-10］、提高鏈路可靠性［11-12］以及保證服務(wù)質(zhì)量［13-17］等方面進(jìn)行研究。文獻(xiàn)［5］中將資源空間以卡諾圖的形式進(jìn)行劃分，通過(guò)動(dòng)態(tài)調(diào)整資源塊的位置提高資源利用率。文獻(xiàn)［6］中將拓?fù)鋭?shì)引入節(jié)點(diǎn)資源排序當(dāng)中，在節(jié)點(diǎn)映射階段綜合考慮當(dāng)前節(jié)點(diǎn)資源以及相鄰鏈路資源，保證映射成功率。文獻(xiàn)［18］中基于網(wǎng)絡(luò)虛擬化中不同功能對(duì)資源的需求不同，設(shè)計(jì)了資源分級(jí)管理系統(tǒng)，有效減少總體映射時(shí)間。上述文獻(xiàn)從資源優(yōu)化的角度出發(fā)，通過(guò)改變資源排序方式或?qū)①Y源分級(jí)映射來(lái)提高資源利用率，但并未考慮到無(wú)線網(wǎng)絡(luò)中功率和帶寬資源之間的互補(bǔ)性。

在無(wú)線虛擬網(wǎng)絡(luò)映射中，功率和帶寬資源具有互補(bǔ)性和替代性，為了實(shí)現(xiàn)負(fù)載均衡提高資源利用率，文獻(xiàn)［19］中提出一種聯(lián)合功率和帶寬的映射算法WVNE-JBP（Wireless Virtual Network Embedding-Joint Bandwidth and Power），但所求映射方案較為單一，沒(méi)有給出如何在功率、帶寬資源富余度不同情況下的映射方案。

為了解決映射過(guò)程中功率和帶寬資源使用不均衡的問(wèn)題，合理調(diào)配富足資源進(jìn)行映射，減少因其他資源短缺造成的映射失敗，本文基于負(fù)載均衡原理提出一種聯(lián)合資源分級(jí)的無(wú)線虛擬網(wǎng)絡(luò)映射（Joint Hierarchical Resource Virtual Network Embedding，JHR-VNE）算法，在映射虛擬網(wǎng)絡(luò)請(qǐng)求（Virtual Network Request，VNR）時(shí)綜合考慮功率資源和帶寬資源，通過(guò)修正系數(shù)將資源進(jìn)行分級(jí)，使得物理網(wǎng)絡(luò)在分配時(shí)側(cè)重不同資源，提高資源利用率。本文主要工作為：

1）提出新的節(jié)點(diǎn)資源排序方式，綜合考慮節(jié)點(diǎn)功率資源和相連鏈路平均帶寬資源，利用權(quán)值系數(shù)對(duì)資源進(jìn)行分級(jí)，在節(jié)點(diǎn)映射階段預(yù)先選擇具有不同資源側(cè)重的節(jié)點(diǎn)；

2）改進(jìn)成本函數(shù)，通過(guò)修正系數(shù)調(diào)整功率和帶寬資源單位成本，在鏈路映射階段進(jìn)一步選擇具有不同側(cè)重的資源分配方案，提高虛擬網(wǎng)絡(luò)請(qǐng)求接受率和資源利用率。

1 映射模型和問(wèn)題分析

無(wú)線虛擬網(wǎng)絡(luò)映射模型由物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)構(gòu)成，分別表示基礎(chǔ)設(shè)施提供商和服務(wù)提供商。

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

1.2 虛擬網(wǎng)絡(luò)模型

在映射時(shí)，物理網(wǎng)絡(luò)分配根據(jù)虛擬網(wǎng)絡(luò)請(qǐng)求分配一定的功率資源和帶寬資源，滿足虛擬網(wǎng)絡(luò)對(duì)傳輸速率的需求。

其中：σ2是信道高斯白噪聲；I(lS)是其他鏈路對(duì)當(dāng)前映射鏈路造成的干擾；g(lV)是信道增益；dis()表示節(jié)點(diǎn)間距離；k為增益系數(shù)。

無(wú)線虛擬網(wǎng)絡(luò)映射模型如圖1 所示，虛擬網(wǎng)絡(luò)中數(shù)字代表鏈路傳輸速率r(lV)，單位為Mb/s。物理網(wǎng)絡(luò)中物理節(jié)點(diǎn)上方數(shù)字代表具有的功率資源p(nS)，單位為W；物理鏈路旁的數(shù)字代表具有的帶寬資源b(lS)，單位為MHz。當(dāng)物理節(jié)點(diǎn)和鏈路滿足位置、資源約束條件后，即可映射相應(yīng)的虛擬網(wǎng)絡(luò)并提供服務(wù)。

1.3 約束條件

在映射過(guò)程中，同一個(gè)虛擬網(wǎng)絡(luò)請(qǐng)求的不同虛擬節(jié)點(diǎn)不能映射到同一個(gè)物理節(jié)點(diǎn)上，且物理節(jié)點(diǎn)需在虛擬節(jié)點(diǎn)映射范圍內(nèi)，被映射的物理節(jié)點(diǎn)和鏈路需具有足夠的資源，即滿足式（3）～（6）。

式（5）～（6）表示物理網(wǎng)絡(luò)在分配功率和帶寬資源以滿足虛擬網(wǎng)絡(luò)對(duì)傳輸速率需求時(shí)，即式（1），分配給虛擬節(jié)點(diǎn)m的功率資源不能超過(guò)被映射物理節(jié)點(diǎn)n能提供的資源，分配給虛擬鏈路lV的帶寬資源不能超過(guò)被映射物理鏈路lS能提供的帶寬資源。

1.4 干擾模型

考慮到無(wú)線網(wǎng)絡(luò)環(huán)境中，相鄰鏈路間存在干擾，本文采用文獻(xiàn)［19］中的鏈路干擾系數(shù)：

其中：dl為影響當(dāng)前映射鏈路lS的干擾鏈路數(shù)目，γ為常數(shù)。鏈路干擾系數(shù)dI(lS) 在進(jìn)行鏈路映射時(shí)作為權(quán)值用于選擇最短路徑。

式（1）中的干擾I(lS)，與鏈路間距離dis(lS，li)、鏈路兩端節(jié)點(diǎn)功率p(nS)以及鏈路增益g(lS)相關(guān)，具體計(jì)算過(guò)程見(jiàn)文獻(xiàn)［20］，公式如下：

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

VNR 接受率為已映射的VNR 數(shù)量與所有VNR 數(shù)量的比值，反映算法的全局優(yōu)化能力。

成本cost為反映底層網(wǎng)絡(luò)為虛擬網(wǎng)絡(luò)提供功率資源和帶寬資源所付出的代價(jià)。

其中：α(nS)和β(lS)為權(quán)值系數(shù)。

資源利用率η反映算法在分配功率資源和帶寬資源時(shí)的效率，其值為已分配的資源與總資源的比值。

2 JHR-VNE算法分析

2.1 節(jié)點(diǎn)資源排序及映射

在有線虛擬網(wǎng)絡(luò)映射過(guò)程中，虛擬節(jié)點(diǎn)對(duì)資源的需求是相對(duì)固定的，如計(jì)算資源、內(nèi)存等，而在無(wú)線虛擬網(wǎng)絡(luò)映射中，由于虛擬網(wǎng)絡(luò)的請(qǐng)求是針對(duì)傳輸速率，因此物理網(wǎng)絡(luò)在分配資源時(shí)的原則如式（1）所示，物理節(jié)點(diǎn)所具有的功率資源和物理鏈路所具有的帶寬資源均會(huì)影響映射成功率。

目前無(wú)線虛擬網(wǎng)絡(luò)映射相關(guān)研究采用擴(kuò)展節(jié)點(diǎn)資源的方式，將節(jié)點(diǎn)功率資源和與該節(jié)點(diǎn)相連的全部鏈路帶寬資源綜合計(jì)算進(jìn)行排序，以尋找同時(shí)滿足功率和帶寬要求的節(jié)點(diǎn)，提高映射成功率。

該排序方式將節(jié)點(diǎn)相連的全部鏈路資源計(jì)算在內(nèi)，但沒(méi)有考慮到鏈路的實(shí)際映射能力。本文基于此提出一種新的節(jié)點(diǎn)資源排序方式，如式（12）所示：

其中：ε為權(quán)值系數(shù)；Num() 表示與節(jié)點(diǎn)nS相連的鏈路數(shù)量；加號(hào)右邊表示與節(jié)點(diǎn)nS相連鏈路的平均帶寬。相較于全部帶寬，平均帶寬更能表示鏈路資源的可用性。

不同于有線虛擬網(wǎng)絡(luò)映射過(guò)程中物理網(wǎng)絡(luò)為虛擬網(wǎng)絡(luò)分配固定的計(jì)算資源或帶寬資源，無(wú)線虛擬網(wǎng)絡(luò)映射中，為滿足虛擬網(wǎng)絡(luò)不同的傳輸速率需求，受式（1）約束，在傳輸速率確定的條件下，物理網(wǎng)絡(luò)可以動(dòng)態(tài)選擇分配虛擬網(wǎng)絡(luò)的功率資源和帶寬資源，由此導(dǎo)致可用的資源分配方案數(shù)量激增。

為實(shí)現(xiàn)資源的高效利用，采用式（12）節(jié)點(diǎn)資源排序方式，在節(jié)點(diǎn)映射過(guò)程中同時(shí)考慮可用鏈路資源，通過(guò)調(diào)整ε值預(yù)先將虛擬網(wǎng)絡(luò)關(guān)于節(jié)點(diǎn)和鏈路資源的需求進(jìn)行分類(lèi)。在滿足最低傳輸速率時(shí)，高ε值的虛擬網(wǎng)絡(luò)會(huì)選擇具有較多帶寬資源的物理節(jié)點(diǎn)，低ε值的虛擬網(wǎng)絡(luò)會(huì)選擇具有較多功率資源的物理節(jié)點(diǎn)。映射時(shí)采用2.3 節(jié)的目標(biāo)函數(shù)，前者求得的最優(yōu)資源分配方案中消耗鏈路帶寬資源較多而消耗節(jié)點(diǎn)功率資源較少，后者則相反。通過(guò)該分級(jí)策略使得節(jié)點(diǎn)和鏈路資源負(fù)載均衡，避免直接求解最優(yōu)目標(biāo)函數(shù)時(shí)所有虛擬網(wǎng)絡(luò)對(duì)功率和帶寬資源的需求比例相似，導(dǎo)致功率資源使用接近上限而帶寬資源利用率低的情況。

2.2 鏈路映射

根據(jù)2.1 的節(jié)點(diǎn)資源排序方式選擇可用節(jié)點(diǎn)，由于VNR對(duì)資源需求的側(cè)重不同，在選擇鏈路時(shí)同樣綜合考慮帶寬資源和鏈路相連節(jié)點(diǎn)的功率資源。進(jìn)行鏈路映射時(shí)，采用路徑分離方法［21］，將傳輸速率r(lV) 分為i個(gè)相等的Δr，映射每個(gè)Δr均滿足式（1）。為提高VNR 的映射數(shù)量和映射成功率，物理網(wǎng)絡(luò)分配功率Δp(nV)和帶寬資源Δb(lV) 僅滿足最低傳輸速率要求，如式（13）所示，在考慮鏈路干擾的條件下采用最短路徑進(jìn)行鏈路映射。

2.3 目標(biāo)函數(shù)

無(wú)線虛擬網(wǎng)絡(luò)映射過(guò)程中，當(dāng)滿足虛擬網(wǎng)絡(luò)所需的傳輸速率要求時(shí)，物理網(wǎng)絡(luò)有多種方案分配功率和帶寬資源，為提高資源利用率和映射數(shù)量，以最小化成本為目標(biāo)函數(shù)，選擇合適的功率和帶寬資源進(jìn)行映射。目標(biāo)函數(shù)如式（14）所示，且滿足約束條件式（1）、式（3）～（6）。

其中：α(nS)和β(lS)為權(quán)值系數(shù)，分別表示使用功率和帶寬所需付出的代價(jià)，大小為單位資源成本，一般為可用資源的倒數(shù)。

為實(shí)現(xiàn)資源分級(jí)部署并提高利用率，將權(quán)值系數(shù)進(jìn)行修正，改進(jìn)后的成本如式（16）：

其中：λ為修正系數(shù)。δ代表VNR 的不同級(jí)別，δ小的VNR 所消耗的功率資源成本小，更傾向于使用大功率小帶寬；δ大的VNR 所消耗的帶寬資源成本小，更傾向于使用小功率大帶寬。

結(jié)合式（13）和式（16），成本化簡(jiǎn)如下：

在滿足約束條件（1）、式（3）～（6）的情況下，選擇使得成本最小的功率Δp(nV)，即求解目標(biāo)函數(shù)式（17）的極小值，使得Δp(nV)滿足cost函數(shù)的導(dǎo)數(shù)為零。為減少解的搜索時(shí)間，設(shè)置功率定義域的最小值Δpmin為當(dāng)Δb(lV)=b(lS)時(shí)（帶寬為鏈路最大可用帶寬）滿足式（13）的功率值。若功率的極小值點(diǎn)不在定義域范圍內(nèi)，令Δp(nV)=ηp(nS)為最終映射功率，η為修正系數(shù)，再根據(jù)式（13）求得此時(shí)的帶寬Δb(lV)，為當(dāng)前VNR 的映射資源方案。

2.4 算法流程

JHR-VNE 算法為最大化利用功率和帶寬，對(duì)映射資源進(jìn)行分級(jí)，采用新的節(jié)點(diǎn)資源排序方式，使用改進(jìn)的成本函數(shù)為目標(biāo)函數(shù)，通過(guò)最小化成本尋找合適的功率和帶寬分配方案，具體流程如下所示。

算法1 JHR-VNE。

JHR-VNE 算法主要包括節(jié)點(diǎn)映射和鏈路映射兩個(gè)部分。在一次映射中，節(jié)點(diǎn)映射計(jì)算主要集中在資源排序和節(jié)點(diǎn)選擇上，其時(shí)間復(fù)雜度為O(|NV│||NS|)，鏈路映射中計(jì)算最短路徑的時(shí)間復(fù)雜度為O(i|LS│|lb(|NS|))，計(jì)算極小值點(diǎn)的時(shí)間復(fù)雜度為O（n2）。綜上得出，在映射過(guò)程中JHR-VNE 算法的時(shí)間復(fù)雜度為O(|NV│||NS|+i|LS│|lb(|NS|)+n2)。

3 仿真實(shí)驗(yàn)與結(jié)果分析

通過(guò)仿真實(shí)驗(yàn)驗(yàn)證本文算法的有效性，在VNR 總體接受率、各級(jí)別VNR 接受率、資源利用率、成本等方面與WVNE-JBP 算法［19］進(jìn)行對(duì)比，分析算法優(yōu)劣性。

3.1 網(wǎng)絡(luò)參數(shù)設(shè)置

實(shí)驗(yàn)仿真平臺(tái)為Matlab，使用改進(jìn)SalamNet 生成物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)拓?fù)?。物理網(wǎng)絡(luò)共設(shè)置50 個(gè)節(jié)點(diǎn)，其位置隨機(jī)分布在200 km×200 km 的范圍內(nèi)，2 個(gè)物理節(jié)點(diǎn)間隨機(jī)生成一條物理鏈路。其中節(jié)點(diǎn)的功率資源服從均勻分布U（50，100），鏈路的帶寬資源服從均勻分布U（20，50），運(yùn)行總時(shí)間為5 000 時(shí)間窗。虛擬網(wǎng)絡(luò)生成節(jié)點(diǎn)個(gè)數(shù)服從均勻分布U（3，10），2 個(gè)虛擬節(jié)點(diǎn)間以0.5 概率形成虛擬鏈路。其中，虛擬網(wǎng)絡(luò)到達(dá)率服從0.05 的泊松分布，即100 個(gè)時(shí)間窗內(nèi)到達(dá)5 個(gè)虛擬網(wǎng)絡(luò)，傳輸速率服從均勻分布U（3，8），生存時(shí)間為100 時(shí)間窗。其他參數(shù)設(shè)置為λ=0.25，δ=0，1，2，?=（2*δ+3）/10，φ=100，η=0.618，信道增益中，k=4，σ2=10-8。

3.2 仿真結(jié)果分析

本文將所提JHR-VNE 算法與WVNE-JBP 算法［19］進(jìn)行對(duì)比，WVNE-JBP 算法的節(jié)點(diǎn)資源排序依據(jù)為當(dāng)前節(jié)點(diǎn)所具有的功率資源和與之相連鏈路的總帶寬資源，通過(guò)路徑分離選擇最短路徑進(jìn)行鏈路映射，其目標(biāo)函數(shù)為原始成本函數(shù)。

圖2 展示了JHR-VNE 算法與WVNE-JBP 算法［19］的VNR總體接受率，可以看出本文算法的接受率有較大提升，WVNE-JBP 算法總體接受率為58.5%，本文算法為70.2%，提高了11.7 個(gè)百分點(diǎn)。接受率曲線波動(dòng)原因?yàn)椴糠諺NR 生存時(shí)間到期，釋放相應(yīng)資源給新到達(dá)的VNR。

圖3 為兩種算法各級(jí)別VNR 接受率比較，δ變化時(shí)，JHR-VNE 算法映射VNR 消耗的資源存在變化，而對(duì)WVNEJBP 算法消耗資源沒(méi)有影響。

圖3（a）中，當(dāng)δ=0時(shí)，本文算法映射VNR 傾向于消耗較大功率資源和較小帶寬資源，接受率相較于WVNE-JBP算法提高了11.8 個(gè)百分點(diǎn)。圖3（b）中，當(dāng)δ=1時(shí)，兩種算法映射VNR 消耗功率資源和帶寬資源比例類(lèi)似，接受率沒(méi)有明顯差距，最終本文算法相較于WVNE-JBP 算法提高了5.5個(gè)百分點(diǎn)。圖3（c）中，當(dāng)δ=2時(shí)，本文算法映射VNR 傾向于消耗較多帶寬資源和較少功率資源，此時(shí)接受率提高了17.8 個(gè)百分點(diǎn)。對(duì)比圖3，本文算法調(diào)整消耗功率資源和帶寬資源的占比后，VNR 接受率有明顯提高，其中帶寬資源為主要占用資源時(shí)接受率提升最大。

圖4 和圖5 分別表示功率和帶寬的資源利用率情況，JHR-VNE 算法在約44%的時(shí)間內(nèi)具有80%以上的功率利用率，約49%的時(shí)間內(nèi)具有50%以上的帶寬利用率，約15%的時(shí)間內(nèi)具有60%以上的帶寬利用率，平均功率利用率為76.6%，平均帶寬利用率為49.8%。WVNE-JBP 算法在約23%的時(shí)間內(nèi)具有80%以上的功率利用率，約51%的時(shí)間內(nèi)具有50%以上的帶寬利用率，約18%的時(shí)間內(nèi)具有60%以上的帶寬利用率，平均功率利用率為72.2%，平均帶寬利用率為48.2%?？梢钥闯霰疚乃惴ㄔ谄骄β世寐噬咸嵘?.4 個(gè)百分點(diǎn)，而在平均帶寬利用率方面提升了1.6 個(gè)百分點(diǎn)。這是因?yàn)閮煞N算法均采用路徑分離方式，將帶寬資源的需求壓力分?jǐn)傊磷渔溌飞?，此時(shí)映射受制于節(jié)點(diǎn)的功率資源大小。

將圖3（c）、圖4～5 結(jié)合可以看出，節(jié)點(diǎn)的功率資源利用率較高而鏈路的帶寬資源利用率較低，即使增大了映射過(guò)程占用帶寬資源的比例，該級(jí)別VNR 接受率仍小于其他級(jí)別，即功率資源是影響VNR 接受率的主要因素。

圖6 為兩種算法的成本對(duì)比，可以看出相較于WVNEJBP 算法，JHR-VNE 算法具有較穩(wěn)定的成本開(kāi)銷(xiāo)，原因是本文算法根據(jù)修正后的成本函數(shù)分配資源，不同級(jí)別VNR 消耗功率和帶寬資源的單位成本有所差異，通過(guò)調(diào)整資源分配方案使得總體成本消耗處在相對(duì)穩(wěn)定的水平，且與修正前成本相差不大，但VNR 接受率和資源利用率有所提升。

4 結(jié)語(yǔ)

本文提出的JHR-VNE 算法采用新的節(jié)點(diǎn)資源排序方式，將節(jié)點(diǎn)功率資源和與之相連的平均鏈路帶寬作為節(jié)點(diǎn)映射選擇依據(jù)，利用權(quán)重系數(shù)對(duì)功率和帶寬資源進(jìn)行分級(jí)，平衡節(jié)點(diǎn)和鏈路負(fù)載；修正成本函數(shù)，物理網(wǎng)絡(luò)為不同級(jí)別VNR 分配資源時(shí)消耗功率和帶寬資源的單位成本不同，以達(dá)到提高資源利用率的目的。經(jīng)過(guò)仿真實(shí)驗(yàn)驗(yàn)證，本文算法能夠解決功率、帶寬資源使用不均衡的問(wèn)題，在總體VNR 接受率、各級(jí)別VNR 接受率以及資源利用率方面有明顯提升。下一步將結(jié)合強(qiáng)化學(xué)習(xí)算法，在與網(wǎng)絡(luò)交互過(guò)程中獲取資源的實(shí)時(shí)狀態(tài)，進(jìn)一步提高功率和資源的利用率。