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

高旗，呂娜，繆競成

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

0 引言

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

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

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

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

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

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

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

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

1 映射模型和問題分析

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

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

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

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

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

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

1.3 約束條件

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

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

1.4 干擾模型

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

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

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

1.5 評價指標

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

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

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

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

2 JHR-VNE算法分析

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

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

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

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

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

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

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

2.2 鏈路映射

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

2.3 目標函數(shù)

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

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

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

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

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

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

2.4 算法流程

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

算法1 JHR-VNE。

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

3 仿真實驗與結(jié)果分析

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

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

實驗仿真平臺為Matlab，使用改進SalamNet 生成物理網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)拓撲。物理網(wǎng)絡(luò)共設(shè)置50 個節(jié)點，其位置隨機分布在200 km×200 km 的范圍內(nèi)，2 個物理節(jié)點間隨機生成一條物理鏈路。其中節(jié)點的功率資源服從均勻分布U（50，100），鏈路的帶寬資源服從均勻分布U（20，50），運行總時間為5 000 時間窗。虛擬網(wǎng)絡(luò)生成節(jié)點個數(shù)服從均勻分布U（3，10），2 個虛擬節(jié)點間以0.5 概率形成虛擬鏈路。其中，虛擬網(wǎng)絡(luò)到達率服從0.05 的泊松分布，即100 個時間窗內(nèi)到達5 個虛擬網(wǎng)絡(luò)，傳輸速率服從均勻分布U（3，8），生存時間為100 時間窗。其他參數(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］進行對比，WVNE-JBP 算法的節(jié)點資源排序依據(jù)為當前節(jié)點所具有的功率資源和與之相連鏈路的總帶寬資源，通過路徑分離選擇最短路徑進行鏈路映射，其目標函數(shù)為原始成本函數(shù)。

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

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

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

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

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

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

4 結(jié)語

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