宋俊輝, 謝 華, 高海龍

(1.信陽師范學院 計算機與信息技術學院, 河南 信陽 464000;2.信陽職業(yè)技術學院 檢驗學院, 河南 信陽 464000;3.中國人民解放軍68128部隊, 甘肅 武威 733200)

0 引言

隨著大數(shù)據(jù)、云計算等新型業(yè)務的快速發(fā)展，導致現(xiàn)有光網(wǎng)絡架構難以滿足網(wǎng)絡業(yè)務多樣、動態(tài)和突發(fā)等需求.網(wǎng)絡虛擬化應運而生，它可以靈活地為連接請求分配帶寬，無需對傳統(tǒng)網(wǎng)絡架構進行很大改動就能獲得較高的頻譜利用率，滿足用戶的多樣化需求.通過邏輯隔離的多個虛擬網(wǎng)絡共享底層物理網(wǎng)絡資源，可實現(xiàn)網(wǎng)絡資源的彈性管理，加快網(wǎng)絡新技術的開發(fā)與部署，有效地增加資源利用率[1,2].

近年來已經有越來越多的研究關注于彈性光網(wǎng)絡的虛擬化，并對其進行了深入研究.網(wǎng)絡虛擬化的難點在于如何設計高效的虛擬結點、鏈路的映射及頻譜分配方案以達到某種預期的目的[3].為解決虛擬網(wǎng)絡節(jié)點映射問題，文獻[4]提出了一種整數(shù)線性規(guī)劃模型和一種基于業(yè)務矩陣的映射算法以得到最優(yōu)的方案.文獻[5]研究了網(wǎng)絡虛擬化環(huán)境下的跨域虛擬網(wǎng)絡映射，分別提出了基于OWL及SWRL的資源匹配算法和基于遺傳算法的虛擬網(wǎng)絡劃分算法.文獻[6]根據(jù)虛擬網(wǎng)絡帶寬需求將物理網(wǎng)絡抽象為多個分層輔助圖，應用最短路徑算法在分層輔助圖上進行虛鏈路，提高鏈路映射效率，但是未考慮物理承載節(jié)點特性和鏈路負載對映射的影響.文獻[7]建立了兩個整數(shù)線性規(guī)劃模型，并提出了基于貪心策略的虛擬網(wǎng)絡映射算法，以減少最小化網(wǎng)絡的最大占用頻隙號.文獻[8]利用節(jié)點介數(shù)中心性，將實時感知的網(wǎng)絡狀態(tài)作為選路因子，采用K最短路算法進行映射虛鏈路.由于該算法并未考慮鏈路頻譜使用狀態(tài)的影響而導致部分物理鏈路承載過重.

已有相關文獻旨在最小化網(wǎng)絡的能耗或網(wǎng)絡最大占用頻隙號等目標，然而頻譜也是彈性光網(wǎng)絡中的一種重要資源，因此本文研究了最小化網(wǎng)絡中的占用資源數(shù)及最小化最大占用頻隙號為目標的虛擬網(wǎng)絡映射問題，建立了一個混合規(guī)劃模型，并提出了一種有效的全局優(yōu)化算法以得到最優(yōu)的虛擬結點映射、虛擬鏈路映射及選路方案.

1 問題描述與建模

1.1 網(wǎng)絡與業(yè)務描述

無向圖G=(V,E)表示一個物理彈性光網(wǎng)絡，其中V={v1,v2,…,vNv}表示物理彈性光網(wǎng)絡中的結點集合，N是物理網(wǎng)絡中結點的個數(shù).對于每個物理結點vi(vi∈V),都有h(vi)個虛擬機.E={Lij|vi,vj∈V}表示物理網(wǎng)絡中鏈路的集合，Lij是結點vi和結點vj之間的鏈路，NE是鏈路的條數(shù).F={f1,f2,…,fNf}是一系列可用頻隙，Nf是每個鏈路上可用頻隙的個數(shù)，假設每個頻隙具有相同的帶寬Cfs.

1.2 問題建模

本研究旨在為確定最優(yōu)的節(jié)點映射、鏈路映射及頻譜分配方案，以使得為所有業(yè)務請求分配頻譜后所占用總的頻隙最少.為此建立一個帶有約束的全局優(yōu)化模型，下面給出研究問題的數(shù)學模型.

目標函數(shù)：為所有業(yè)務請求分配頻譜后所占用的頻譜數(shù)最少且最大占用頻隙號最小.目標函數(shù)可以表示為

(1)

虛擬結點映射滿足的約束條件：(1)所有的虛擬節(jié)點必須映射到一個物理結點上；(2)同一個虛擬網(wǎng)中的虛擬結點不能映射到同一個物理結點上；(3)映射到同一個物理結點上的虛擬結點數(shù)不大于該物理結點上的虛擬機的數(shù)量.因此有：

研究手段：以錯誤分析理論為指導在整個學年的口譯課上，對老師當堂布置的口譯任務中學生出現(xiàn)的錯誤進行記錄，同時對整個學年當中，學生課后口譯錄音作業(yè)中所出現(xiàn)的錯誤也進行了記錄，最后分類、歸納、整理。

(2)

(3)

(4)

頻譜分配滿足約束條件：(a)業(yè)務請求只能占用聯(lián)通原結點和宿結點所有通路中的一條路徑；(b)業(yè)務在所占路徑中的不同鏈路上具有相同的的起始頻隙號；(c)一個業(yè)務請求必須占用若干個連續(xù)的頻隙；(d)任意兩個業(yè)務所占用的頻譜無重疊.

(5)

(6)

(7)

(8)

2 全局優(yōu)化遺傳算法

遺傳算法在工程技術領域等實際應用問題中得到了廣泛的應用，尤其是解決NP組合優(yōu)化問題中更是表現(xiàn)出了其優(yōu)良的性能[9].因此，本文設計了一種新的全局優(yōu)化遺傳算法來求解本文提出的最大化服務質量的可分任務調度模型.

2.1 編碼與解碼

采用首次適應策略(First Fit, FF)進行頻譜分配，因此只需要對虛擬節(jié)點映射和選路進行編碼.

(9)

(10)

2.2 交叉與變異算子

交叉操作是遺傳算法的主要進化手段，通過兩兩染色體基因交叉互換，繁殖兩個新的子代個體，并將父代好的基因遺傳至子代個體，產生的子代個體可能會優(yōu)于父代個體.交叉操作保持了遺傳算法種群個體的多樣性和全局搜索能力.本文采用兩點交叉方式生成新個體：隨機生成兩個整數(shù)j1和j2滿足2≤j1≤j2≤N′(對選路個體進行交叉時2≤j1≤j2≤NR′)作為交叉點，將兩個父代個體交叉點之間的基因進行交換，生成兩個后代個體.

變異算子通過一定概率的基因變異，可以在一定程度上提高多樣性，強化了算法搜索到最優(yōu)解的能力.本文采用單點變異方式生成新個體：隨機生成一個整數(shù)j1滿足2≤j3≤N′(對選路個體進行交叉時2≤j3≤NR′)作為變異點，將個體在該點的基因位取反，產生新的后代個體.

2.3 不可行解可行化

由于物理結點vi(?vi∈V)只有h(vi)個虛擬機，因此只能有不超過h(vi)個虛擬結點映射到物理結點vi上，然而在交叉變異過程中,會使得某些結點上映射的虛擬結點數(shù)超過其所擁有的虛擬機的數(shù)量,導致該虛擬結點映射個體成為一個不可行解，因此本文設計了一個可以將虛擬結點映射的不可行解進行可行化的可行化算子，如算法1所示.

算法1：不可行解可行化

輸入：結點映射個體x;

輸出：新的結點映射個體x′;

x′=x;

fori=1 toNvdo

Cap(1,i)=h(vi);

end

forj=1 toN′ do

c(j)是xj在個體x出現(xiàn)的次數(shù)，即映射到結點vxj上虛擬結點的個數(shù)；

diffCap(1,j)=h(vxj)-c(j);

end

forj=1 toN′ do

ifdiffCap(1,j)<0 do

η是diffCap中最大值所在的位置；

end

end

2.4 適應度函數(shù)

適應度函數(shù)是一個衡量個體好壞的標準，本文所建立的優(yōu)化模型中的目標函數(shù)是最小化最大占用頻隙號.因此本文采用的適應度函數(shù)為式(11)所示.

f=ρ+δ×ω,

(11)

其中δ是一個布爾型變量，當且僅當結點映射個體x和行路個體y組合形成一個解(x,y)是問題的可行解時δ=0，否則δ=1.ω是一個常數(shù)(該常數(shù)只要大于1即可，本文取ω=100).

3 實驗與分析

3.1 參數(shù)設置

在仿真實驗中，采用兩種網(wǎng)絡拓撲：網(wǎng)絡拓撲1是包含13個節(jié)點和21個鏈路的NSFNET(如圖1所示)， 網(wǎng)絡拓撲2是包含20和節(jié)點和32個鏈路的ARPANET(如圖2所示)， 鏈路上的數(shù)據(jù)表示網(wǎng)絡節(jié)點間的距離.

圖1 NFSNET拓撲Fig. 1 Topology of NFSNET

圖2 ARPANET拓撲Fig. 2 Topology of ARPANET

仿真實驗中假定每個頻隙(Frequency Slots, FSs)為12.5 GHz，4種調制格式BPSK，QPSK，8QAM和16QAM的傳輸距離分別設置為9600、4800、2400和1200 km[10,11].物理網(wǎng)絡中的每個物理結點上有10～20個虛擬機，當一個虛擬結點映射到物理結點上時需要占用該物理結點上的一個虛擬機.每一個虛擬網(wǎng)中有3～7個虛擬結點， 每兩個虛擬結點之間有業(yè)務請求的概率是0.5.遺傳算法中參數(shù)設置如下：種群規(guī)模Psize=100，交叉概率Pc=0.85，變異概率Pm=0.15，精英保留個數(shù)E=5，終止條件為進化代數(shù)Gmax=5000.

3.2 實驗結果

為了驗證算法的有效性，本文提出的算法(用GA表示)和文獻[12]提出的算法(用LL表示)在不同的情況下進行對比.在本文設計的算法中，首先對業(yè)務按照某種策略排序，根據(jù)不同的排序策略可以產生不同的算法.本文采用三種常用的排序策略，即MSF(Most Subcarrier First, MSF)、LPF(Longest Path First, LPF)、EMkPSF(Extended Most K Path Subcarrier First, EMkPSF)，與本文提出的遺傳算法結合可以得到三種算法，即GA-MSF、GA-LPF、GA-EMkPSF.圖3和圖4分別給出了α=0，β=1時在NSFNET和ARPANET中的實驗結果；圖5和圖6分別給出了α=0.5，β=0.5時在NSFNET和ARPANET中的實驗結果.圖7和圖8分別給出了α=1，β=0時在NSFNET和ARPANET中的實驗結果.

圖3 NSFNET中對比圖(α=0，β=1)Fig. 3 Compared in NSFNET(α=0，β=1)

圖4 ARPANET中對比圖(α=0，β=1)Fig. 4 Compared in ARPANET(α=0，β=1)

3.3 實驗結果分析

圖5 NSFNET中對比圖(α=0.5，β=0.5)Fig. 5 Compared in NSFNET(α=0.5，β=0.5)

圖6 ARPANET中對比圖(α=0.5，β=0.5)Fig. 6 Compared in ARPANET(α=0.5，β=0.5)

圖7 NSFNET中對比圖(α=1，β=0)Fig. 7 Compared in NSFNET(α=1，β=0)

圖8 ARPANET中對比圖(α=1，β=0)Fig. 8 Compared in ARPANET(α=1，β=0)

4 結論

本文針對虛擬彈性光網(wǎng)絡中虛擬結點的映射及選路、頻譜分配等問題進行了研究，建立了一個最小化占用頻譜數(shù)及最小化最大占用頻隙號為目標的全局約束優(yōu)化模型.為有效地求解該約束優(yōu)化模型，設計了全局優(yōu)化算法.通過在不同的網(wǎng)絡拓撲中進行仿真實驗，實驗結果表明：本文設計的算法可以有效降低網(wǎng)絡中占用的頻隙數(shù)和最大頻隙號.但是算法的復雜度較大，因此在后續(xù)的研究中我們將降低計算復雜度，以快速地確定最優(yōu)的虛擬節(jié)點映射及選路、頻譜分配方案.