面向大規(guī)模多跳網(wǎng)絡的虛擬網(wǎng)絡拓撲控制方法

羅 濤，王宏波，徐永慶，李澤旭

(1.中國電子科技集團公司第七研究所 網(wǎng)絡交換事業(yè)部，廣東 廣州 510310; 2.北京郵電大學 泛網(wǎng)無線通信教育部重點實驗室,北京 100876)

隨著無線網(wǎng)絡技術的不斷發(fā)展與進步，人類社會正在逐步朝萬物互聯(lián)的美好愿景邁進[1]。然而，海量物理通信設備的接入會嚴重制約現(xiàn)有通信網(wǎng)絡系統(tǒng)內(nèi)有效信息的識別準確性，并且進一步提升了對諸如節(jié)點位置、可用帶寬等存在較強時效屬性資源可管控方面的復雜度。因此，對物理網(wǎng)絡信息資源直接管控的傳統(tǒng)技術方案正在被逐步替代，由實體化向虛擬化的轉變已成為未來通信網(wǎng)絡發(fā)展的重要趨勢。

虛擬網(wǎng)絡是通過對實際物理網(wǎng)絡內(nèi)在邏輯關系進行抽象而得到的邏輯網(wǎng)絡。相較于實體網(wǎng)絡中節(jié)點的物理連接關系，虛擬網(wǎng)絡能夠更加靈活有效地進行統(tǒng)一化管理。因此，可以極大地降低多跳通信網(wǎng)絡信息管理過程的復雜度。目前，國內(nèi)外相關學者對虛擬網(wǎng)絡的構建方法展開了大量研究[2-6]。文獻[2]研究了無線多跳蜂窩網(wǎng)絡內(nèi)虛擬網(wǎng)絡嵌入問題，通過建立虛擬網(wǎng)絡嵌入模型充分利用網(wǎng)絡資源，從而有效提高用戶服務質量。文獻[3]提出了一種虛擬網(wǎng)絡資源管理方法以控制網(wǎng)絡內(nèi)的天線的發(fā)射功率，該方法能夠在最小化虛擬網(wǎng)絡之間的干擾的同時滿足多用戶需求。但是，現(xiàn)有的研究工作大多聚焦于虛擬網(wǎng)絡到物理網(wǎng)絡的映射[1]，缺乏對虛擬網(wǎng)絡本身結構優(yōu)化的研究。除此之外，對于虛擬網(wǎng)絡業(yè)務與實體網(wǎng)絡資源的映射的研究大多直接采用傳統(tǒng)路徑規(guī)劃方案[7-11]，而對網(wǎng)絡中業(yè)務分布與虛擬網(wǎng)絡拓撲結構直接影響的相關研究也較少涉及。這些問題會導致虛擬網(wǎng)絡構建不靈活、開銷大及資源可用性差等問題。

復雜網(wǎng)絡理論研究大規(guī)模網(wǎng)絡拓撲結構與網(wǎng)絡各項性能之間內(nèi)在聯(lián)系[12]。在通信網(wǎng)中構建良好的拓撲結構可有效延長網(wǎng)絡生命周期，實現(xiàn)負載均衡，增強網(wǎng)絡的魯棒性[13-15]。因此，通過對虛擬網(wǎng)絡節(jié)點間的連接關系進行調(diào)整就能有效優(yōu)化拓撲結構，提升網(wǎng)絡性能。小世界網(wǎng)絡作為一類典型的復雜網(wǎng)絡結構具有平均路徑長度較小而聚類系數(shù)較大的特點。較小的平均路徑能夠提高節(jié)點間數(shù)據(jù)傳輸?shù)男?，降低通信時延，減少節(jié)點能量消耗；較大的聚類系數(shù)可以提高網(wǎng)絡的容錯性，這些都是大規(guī)模多跳通信網(wǎng)絡所期望的[16]。大規(guī)模多跳網(wǎng)絡的虛擬網(wǎng)絡結構具備小世界特性，有利于提升網(wǎng)絡的性能。

針對多跳網(wǎng)絡內(nèi)拓撲連接關系與其主要面向業(yè)務的對應關系，擬提出一種能夠根據(jù)當前業(yè)務需求及分布情況而自適應建立并調(diào)整虛擬網(wǎng)絡連接關系與資源分配策略的虛擬網(wǎng)絡拓撲控制方法。重點研究了面向專用網(wǎng)絡的虛擬網(wǎng)絡拓撲建立過程，用以解決虛擬網(wǎng)絡構建開銷大、資源用以配置不靈活的問題。該方法通過抽取物理網(wǎng)絡信息、優(yōu)化虛擬網(wǎng)絡拓撲、資源自適應分配與虛擬資源的物理映射等步驟，以期能夠有效減少虛擬網(wǎng)絡構建過程的資源開銷，為未來大型多跳通信系統(tǒng)的構建與管理提供一種新思路。

1 系統(tǒng)性能指標定義

針對復雜網(wǎng)絡，通常使用無向圖G(V,E)表示。其中：V表示網(wǎng)絡節(jié)點集合；E表示網(wǎng)絡中邊的集合。同時，基于復雜網(wǎng)絡理論，通常利用拓撲圖G(V,E)的特征參數(shù)評估網(wǎng)絡拓撲結構的性能。常見的網(wǎng)絡拓撲特征參數(shù)包括以下4個方面。

2)網(wǎng)絡直徑。網(wǎng)絡中任意兩個節(jié)點之間距離的最大值，記為D，即D=max(di,j)。網(wǎng)絡直徑刻畫了網(wǎng)絡的最大信息傳輸時滯特性，在通信網(wǎng)絡中，較小的平均路徑長度和網(wǎng)絡直徑有利于優(yōu)化網(wǎng)絡的路由，減少資源開銷。

4)介數(shù)。節(jié)點的介數(shù)是指網(wǎng)絡中所有的最短路徑中經(jīng)過該節(jié)點的數(shù)量；邊的介數(shù)含義與節(jié)點介數(shù)的含義類似。

相較于傳統(tǒng)的物理網(wǎng)絡拓撲，虛擬網(wǎng)絡是對物理網(wǎng)絡進行抽象后得到的邏輯網(wǎng)絡。物理網(wǎng)絡中通過多跳鏈路相連的兩個節(jié)點，在虛擬網(wǎng)絡中可以通過邏輯鏈路一跳相連。因此，基于物理網(wǎng)絡的特征參數(shù)無法準確描述虛擬網(wǎng)絡性能，需要在計算特征參數(shù)時結合網(wǎng)絡虛實映射關系。

2 虛擬網(wǎng)絡構建方法

根據(jù)組網(wǎng)請求中虛擬網(wǎng)絡節(jié)點數(shù)量，可以將虛擬網(wǎng)絡分為虛鏈路和虛擬網(wǎng)兩種類型，其中虛鏈路請求需要為用戶建立并維護端到端的虛擬鏈路形態(tài)，虛擬網(wǎng)請求需要為多用戶提供能夠兩兩互通的虛擬網(wǎng)絡。傳統(tǒng)虛擬網(wǎng)絡構建方案大多基于虛鏈路的組合，通過在兩兩用戶之間搭建虛鏈路實現(xiàn)虛擬網(wǎng)絡的構建。然而，這種方法沒有考慮網(wǎng)絡節(jié)點的路由轉發(fā)能力和業(yè)務分布，會導致虛擬網(wǎng)絡構建開銷大、冗余路徑多和資源利用率低等問題。

為改善上述問題，基于小世界理論，針對虛擬網(wǎng)絡鏈路效率與潛在業(yè)務需求的動態(tài)協(xié)調(diào)進行設計，提出一種靈活的虛擬網(wǎng)絡構建方法?；谔摂M網(wǎng)絡用戶需求及資源池信息，首先，建立以虛擬網(wǎng)絡用戶為端節(jié)點的符合組網(wǎng)需求的虛擬網(wǎng)絡拓撲，獲取節(jié)點間最大鏈路能力。然后，基于多跳網(wǎng)絡的小世界特性，對虛擬網(wǎng)絡拓撲進行優(yōu)化，在保證連通需求和網(wǎng)絡效率的前提下，提高鏈路資源利用率，降低網(wǎng)絡帶寬開銷。再通過網(wǎng)絡資源自適應分配，結合節(jié)點路由轉發(fā)能力靈活配置虛擬網(wǎng)絡資源。最后，基于多跳網(wǎng)絡物理拓撲結構及區(qū)域資源池信息，通過端到端的虛擬鏈路規(guī)劃，實現(xiàn)虛擬網(wǎng)到物理資源的映射，完成整個虛擬網(wǎng)絡構建。

2.1 建立虛擬網(wǎng)絡拓撲

在虛擬網(wǎng)絡的建立過程中，需要完成實體物理節(jié)點向邏輯虛擬網(wǎng)絡的轉化。邏輯網(wǎng)絡在上報的物理信息中，將所需資源信息采取合并、刪減和填充等方式進行抽象，構建虛擬資源池信息并采用歸一化輸出結果進行資源池數(shù)據(jù)庫填充，從而完成虛擬網(wǎng)絡的初步構建。

在網(wǎng)絡拓撲結構的表達方式中，采用“節(jié)點”與“邊”組成的圖的方式是較為常見且直觀的。網(wǎng)絡的連通性、端到端的連接關系等通信網(wǎng)中較為關注的屬性能夠得到更為直觀的表達。因此，需要進一步將虛擬資源池中的資源信息抽象為通過圖表達的邏輯網(wǎng)絡。在資源池中，由于物理節(jié)點之間存在多種連接關系，可采用圖論中的最大流方法建立網(wǎng)絡拓撲關系。假設域內(nèi)節(jié)點數(shù)為M，虛擬網(wǎng)絡用戶數(shù)為N，經(jīng)過資源抽象及虛擬化后，資源池矩陣維度由原始的M×M維降低至N×N維，可顯著降低后續(xù)拓撲優(yōu)化和資源分配復雜度。具體的虛擬邏輯網(wǎng)絡構建過程如圖1所示。

圖1 虛擬邏輯網(wǎng)絡構建過程

由圖1可以看出，虛線表示的是節(jié)點間虛擬鏈路。在每兩個虛擬節(jié)點之間建立一條直接相連的虛擬鏈路，作為虛擬網(wǎng)絡的初始拓撲結構。

2.2 虛擬網(wǎng)絡拓撲結構優(yōu)化

虛擬網(wǎng)絡拓撲優(yōu)化是通過設計合理的網(wǎng)絡拓撲結構，實現(xiàn)可用資源數(shù)與網(wǎng)絡效率間的最優(yōu)均衡。以網(wǎng)絡效率閾值為限制條件，以最小化構建虛擬網(wǎng)絡帶寬開銷為目標，從初始兩兩相連的拓撲結構出發(fā)，對虛擬網(wǎng)絡進行遍歷，保留效率較高的鏈路關系并剔除效率低的虛擬鏈路，從而將有限的資源更合理地分配至虛擬網(wǎng)絡，在保證網(wǎng)絡效率的同時盡可能簡化虛擬網(wǎng)絡拓撲結構。當算法獲取到待優(yōu)化的虛擬網(wǎng)絡拓撲結構后，將獲取網(wǎng)絡系統(tǒng)內(nèi)每條邊的相關拓撲評估指標綜合匯總其存在價值。

虛擬網(wǎng)絡拓撲結構優(yōu)化算法主要是基于在冗余鏈路中刪除連接關系的思想進行拓撲優(yōu)化。根據(jù)當前網(wǎng)絡連接關系依次計算每條邊在此拓撲下的介數(shù)，然后將當前網(wǎng)絡內(nèi)介數(shù)最低的一條邊斷開其兩端節(jié)點的連接關系，從而得到新的網(wǎng)絡連接關系，并重復該過程，直至某一邊斷開導致網(wǎng)絡內(nèi)通行效率為零。通過該方法的不斷迭代，網(wǎng)絡內(nèi)對通信效率貢獻相對較小的邊先被斷開，貢獻較大的邊后斷開，從而保證了受限資源的有效分配。具體的基于小世界網(wǎng)絡理論的拓撲優(yōu)化算法的步驟如下。

步驟1獲取當前網(wǎng)絡連接關系。

步驟2依照邊的索引值依次判定網(wǎng)絡內(nèi)是否存在孤立節(jié)點。如果是，則跳轉至步驟6；如果否，則跳轉步驟3。

步驟3依照節(jié)點的索引值，依次計算該節(jié)點至其他所有節(jié)點的最短路徑，并且統(tǒng)計所有邊在該節(jié)點所有最短路徑內(nèi)的出現(xiàn)次數(shù)。

步驟4統(tǒng)計當前網(wǎng)絡拓撲的通信效率以及所有邊的介數(shù)，并對邊的介數(shù)進行逆序排列，最終刪除介數(shù)最小的一條邊。

步驟5更新網(wǎng)絡拓撲結構，并返回步驟2。

步驟6輸出統(tǒng)計結果。

為驗證算法可行性，仿真構建18個節(jié)點的網(wǎng)絡環(huán)境，驗證基于小世界網(wǎng)絡理論的拓撲優(yōu)化算法有效性。在仿真系統(tǒng)中檢驗所提算法“剪除的邊的數(shù)量”與“通信效率”的映射關系。在仿真實驗中，直觀地給出了通信效率與算法迭代剪除拓撲邊結構數(shù)量的內(nèi)在聯(lián)系。具體的加權介數(shù)逆序剪邊仿真結果如圖2所示。

圖2 加權介數(shù)逆序剪邊仿真結果

由圖2可以看出，仿真中存在兩個明顯的拐點，即圖中“第一拐點”與“第二拐點”。第一拐點前，該網(wǎng)絡拓撲通信效率隨著虛擬網(wǎng)絡邊數(shù)減少降低的較緩慢，但是第一拐點后，通信效率下降速度明顯增加，這是符合小世界網(wǎng)絡理論的。該仿真結果證明了基于小世界網(wǎng)絡特性相關理論的虛擬網(wǎng)絡構建方法中，明顯的拐點信息是存在的。而在第二拐點后網(wǎng)絡無法保證全連通，因此通信效率驟降為0。仿真結果表明，所提拓撲優(yōu)化算法能夠在保證一定網(wǎng)絡效率的同時，盡可能地減少虛擬網(wǎng)絡邊數(shù)，證明了該算法的有效性。

通過觀察網(wǎng)絡拓撲結構可以更加直觀地認識其連接關系，不同連接關系下的網(wǎng)絡拓撲結構如圖3所示。

圖3 加權介數(shù)逆序剪邊仿真網(wǎng)絡拓撲

由圖2和圖3可知，刪除125條邊后，網(wǎng)絡仍能保證80%的網(wǎng)絡效率。所提虛擬網(wǎng)絡拓撲優(yōu)化算法在保障一定網(wǎng)絡性能的同時，能夠顯著簡化網(wǎng)絡拓撲，降低后續(xù)虛擬網(wǎng)絡構建的帶寬開銷。

2.3 虛擬網(wǎng)絡資源的自適應分配

虛擬網(wǎng)絡資源自適應分配的主要任務是在完成初步的虛擬網(wǎng)絡鏈路結構建立后，采用歷史統(tǒng)計數(shù)據(jù)不斷修正虛擬網(wǎng)絡各條虛擬鏈路的資源配置。在該方法中，首先，基于構建好的虛擬網(wǎng)絡拓撲結構計算能保證連通的初始化最低資源量，并為初始化拓撲的每條鏈路依次賦予等額帶寬資源。其次，統(tǒng)計每條鏈路單位時間內(nèi)傳輸?shù)臉I(yè)務數(shù)量，將其作為鏈路價值函數(shù)衡量用戶對不同虛擬鏈路的資源需求程度。根據(jù)統(tǒng)計數(shù)據(jù)自適應調(diào)整鏈路預留資源，為高價值虛擬鏈路賦予更多資源，以提升網(wǎng)絡資源可用性。最后，將統(tǒng)計結果作為輸入反饋的資源控制模塊，從而指導下一批次的預留資源分配方法，即預留資源分配的數(shù)量與鏈路內(nèi)并行業(yè)務數(shù)成正比。具體虛擬網(wǎng)絡資源的自適應分配算法的步驟如下。

步驟1獲取當前虛擬網(wǎng)絡可分配虛擬資源總數(shù)，并計算維持虛擬網(wǎng)絡最低資源數(shù)量。

步驟2在初始化時刻，將維持虛擬網(wǎng)絡最低數(shù)量資源等額分配給每條虛鏈路。

步驟3統(tǒng)計每條虛擬鏈路單位時間內(nèi)并行業(yè)務傳輸數(shù)量，將其作為鏈路價值函數(shù)。

步驟4將鏈路資源池內(nèi)剩余資源按統(tǒng)計價值函數(shù)比例靈活分配給每條鏈路。

步驟5判斷時刻是否結束，如果結束跳轉至步驟6，否則返回到步驟3。

步驟6輸出分配結果。

虛擬網(wǎng)絡的自適應性優(yōu)化策略的目的是保證普通業(yè)務與并行模式都能夠在該網(wǎng)絡內(nèi)得到保證。其中，初始化時刻的虛擬網(wǎng)絡鏈路資源應配置為能夠滿足最低組網(wǎng)需求，然后基于業(yè)務統(tǒng)計靈活分配預留資源逐漸自適應當前業(yè)務狀況，最終成功實現(xiàn)整體虛擬網(wǎng)絡的優(yōu)化。

2.4 虛擬網(wǎng)絡的實體映射

物理網(wǎng)絡資源經(jīng)過抽象、結構優(yōu)化和資源分配過程后，得到了優(yōu)質的虛擬連接關系，但實際作為物理業(yè)務載體的還是物理網(wǎng)絡。因此，還需要完成由虛擬網(wǎng)絡向實體物理網(wǎng)絡的映射工作，才能真正承接節(jié)點真實業(yè)務。

在虛擬網(wǎng)絡的拓撲結構中，每一條一跳直連的虛鏈路在物理網(wǎng)絡中都是通過一跳或多跳連接的。那么，可以在每兩個具有虛擬連接關系的節(jié)點之間尋找最優(yōu)物理路徑。因此，虛擬網(wǎng)絡的映射過程實際上可以看作是每條虛鏈路尋找物理路由的問題。目前，針對多跳網(wǎng)絡路由問題研究相對廣泛，常用的路由算法包括主動式路由、反應式路由[17]以及基于強化學習的智能路由算法[18-19]等。該問題不是研究的重點，因此所提虛擬網(wǎng)絡構建方法采用基于迪杰斯特拉的最小跳算法求解虛實映射問題。

3 建模與仿真分析

為了驗證所提虛擬網(wǎng)絡拓撲控制方法的可行性，搭建了100個骨干網(wǎng)節(jié)點的多跳網(wǎng)絡通信系統(tǒng)，采用數(shù)值模擬的方式模擬真實的節(jié)點和物理環(huán)境。下面介紹仿真環(huán)境的相關配置，并對仿真結果進行分析。

3.1 仿真環(huán)境

選取節(jié)點規(guī)模為100個的骨干側多跳網(wǎng)絡通信系統(tǒng)作為仿真對象，將100個骨干網(wǎng)節(jié)點劃分為4個域，每個域包含一個簇首節(jié)點。將簇首節(jié)點作為每個域的控制節(jié)點，根據(jù)域內(nèi)用戶的請求進行集中的調(diào)度與管理。在網(wǎng)絡仿真軟件中選取一個域中的5個或10個節(jié)點模擬建立虛擬網(wǎng)絡，具體的多跳通信網(wǎng)絡的單域節(jié)點仿真網(wǎng)絡拓撲示意圖如圖4所示。 其中，node_0,node_1,…,node_20表示網(wǎng)絡節(jié)點。

圖4 仿真網(wǎng)絡拓撲示意圖

由圖4可以看出，其中的仿真域包含21個節(jié)點，各節(jié)點之間通過無線鏈路或有線鏈路通信。為符合實際應用場景，仿真設置兩種具有不同覆蓋范圍和通信能力的節(jié)點類型。其中，20號節(jié)點能夠覆蓋當前所在域，與其他節(jié)點之間均通過無線鏈路連接，且鏈路帶寬較窄。其余節(jié)點均具備無線和有線通信能力，無線鏈路的帶寬為2.4 kB、9.6 kB、8 MB以及2 MB，有線鏈路帶寬則固定為20 MB。所仿真的多跳網(wǎng)絡的業(yè)務，主要包括報文、環(huán)境信息、文件傳輸以及話音等業(yè)務。需要說明的是，包含100個骨干網(wǎng)節(jié)點的通信系統(tǒng)，每個域的拓撲結構是類似的。不失一般性，虛擬網(wǎng)絡化之后的性能測試在包含100個骨干節(jié)點的多域多跳通信系統(tǒng)場景下進行仿真。具體的多跳網(wǎng)絡通信系統(tǒng)參數(shù)如表1所示。

表1 多跳網(wǎng)絡通信系統(tǒng)參數(shù)

通信效率下降門限指的是在刪除虛擬網(wǎng)絡鏈路之后，網(wǎng)絡效率需要始終高于通信效率下降門限。不可用鏈路帶寬指的是該條鏈路對應的兩個節(jié)點之間無直連鏈路。路由有效時間指的是實體網(wǎng)絡中每條路由的有效時間。

3.2 仿真結果分析

單域內(nèi)5個虛擬網(wǎng)絡節(jié)點通信效率隨刪邊個數(shù)變化情況如圖5所示。5個虛擬網(wǎng)絡節(jié)點分別為node_3、node_0、node_8、node_11和node_16。

圖5 5個節(jié)點通信效率隨刪邊數(shù)目變化情況

由圖5可以看出，邊介數(shù)逆序刪邊算法的通信效率下降曲線存在兩個拐點，并且與隨機刪邊通信效率下降曲線相比，通信效率下降更慢。邊介數(shù)逆序刪邊算法在每次刪邊時選擇邊介數(shù)最小的邊，對網(wǎng)絡的整體通信效率影響較小。為保證每次刪邊后的通信效率不低于初始效率的80%，在刪除5條邊后終止。而隨機刪邊通信效率下降趨勢不固定，為保證每次刪邊后的通信效率不低于初始效率的80%，在刪除4條邊后終止。

圖6為單域內(nèi)10個虛擬網(wǎng)絡節(jié)點通信效率隨刪邊個數(shù)變化的情況。10個虛擬網(wǎng)絡節(jié)點分別為node_1、node_6、node_18、node_3、node_0、node_8、node_11、node_12、node_16和node_19。

圖6 10個節(jié)點通信效率隨刪邊數(shù)目變化情況

由圖6可以看出，邊介數(shù)逆序刪邊算法的通信效率下降曲線存在兩個拐點，并且與隨機刪邊通信效率下降曲線相比，通信效率下降更慢。為保證每次刪邊后的通信效率不低于初始效率的80%，在刪除26條邊后終止。而隨機刪邊通信效率下降趨勢不固定，為保證每次刪邊后的通信效率不低于初始效率的80%，在刪除16條邊后終止。

為了驗證虛擬網(wǎng)絡的有效性，進一步對構建的虛擬網(wǎng)絡進行多業(yè)務性能測試。設置仿真時間為1 700 s，在仿真過程中，虛擬網(wǎng)絡節(jié)點隨機發(fā)起調(diào)度請求，并接收其他虛擬網(wǎng)絡節(jié)點傳輸?shù)臉I(yè)務。以最小生成樹、全連接拓撲作為對比方案，假設仿真過程中使用不同方法生成的業(yè)務數(shù)量相等，則不同虛擬網(wǎng)絡拓撲下5個虛擬網(wǎng)絡用戶的業(yè)務的拒絕數(shù)和不同拓撲下5個虛擬網(wǎng)絡用戶的業(yè)務時延分別如圖7和圖8所示。

圖7 不同拓撲5個虛擬網(wǎng)絡用戶的業(yè)務拒絕數(shù)

由圖7可以看出，最小生成樹虛擬網(wǎng)絡拓撲下，業(yè)務的拒絕率為31.42%；基于邊介數(shù)逆序刪邊算法的虛擬網(wǎng)絡拓撲中，業(yè)務的拒絕率為23.74%；全連接的虛擬網(wǎng)絡拓撲中，業(yè)務的拒絕率為15.08%。基于邊介數(shù)逆序刪邊算法的虛擬網(wǎng)絡拓撲和最小生成樹虛擬網(wǎng)絡拓撲的鏈路數(shù)目基本相同，而前者的業(yè)務拒絕率比后者低了7.68%。這說明基于邊介數(shù)進行刪邊可以在盡可能不影響網(wǎng)絡效率的前提下刪除冗余的鏈路。同時，全連接虛擬網(wǎng)絡拓撲的鏈路數(shù)目是基于邊介數(shù)逆序刪邊算法的虛擬網(wǎng)絡拓撲的鏈路數(shù)目的二倍，而前者的業(yè)務拒絕率只比后者低了8.66%。這進一步說明了基于邊介數(shù)進行刪邊時刪去的邊對網(wǎng)絡效率影響較小。綜合考慮業(yè)務拒絕率和鏈路數(shù)目，基于邊介數(shù)逆序刪邊后動態(tài)分配帶寬的虛擬網(wǎng)絡拓撲性能更優(yōu)。

圖8 不同拓撲下5個虛擬網(wǎng)絡用戶的業(yè)務時延

由圖8可以看出，3種拓撲的平均時延相差不大，最小生成樹虛擬網(wǎng)絡拓撲、基于邊介數(shù)逆序刪邊算法的虛擬網(wǎng)絡拓撲和全連接的虛擬網(wǎng)絡拓撲的業(yè)務平均時延分別為0.543 9 s、0.60 s和0.50 s。這說明了在為不同虛擬網(wǎng)絡拓撲中的業(yè)務提供服務時，所提方法是很穩(wěn)定的。

在搭建的具有100個骨干網(wǎng)節(jié)點的多跳網(wǎng)絡通信系統(tǒng)中進行虛擬網(wǎng)絡拓撲構建、優(yōu)化以及資源自適應分配，通過網(wǎng)絡初始化時對虛擬網(wǎng)絡進行刪邊和網(wǎng)絡運行時的多業(yè)務仿真，驗證了虛擬網(wǎng)絡構建方法的有效性。圖5和圖6中的仿真結果表明，基于邊介數(shù)逆序進行刪邊時，通信效率下降速度逐漸增快，并且具有拐點。邊介數(shù)逆序刪邊算法與隨機刪邊算法相比，可刪除更多冗余鏈路，提升帶寬資源的利用率。圖7和圖8是虛擬網(wǎng)絡的多業(yè)務測試，虛擬網(wǎng)絡構建方法可在盡可能提高帶寬利用率的前提下有效降低虛擬網(wǎng)絡用戶業(yè)務的拒絕率。

4 結語

針對無線資源受限的多跳網(wǎng)絡環(huán)境下，網(wǎng)絡資源與業(yè)務需求難匹配的問題，提出了虛擬網(wǎng)絡構建及拓撲控制方法。將實體網(wǎng)絡中的繁雜信息抽象為虛擬網(wǎng)絡拓撲，并根據(jù)業(yè)務分布和組網(wǎng)需求優(yōu)化拓撲結構使其具備小世界網(wǎng)絡特性。進行端到端的虛擬鏈路資源預留，實現(xiàn)虛擬網(wǎng)到物理資源的映射，完成多跳網(wǎng)絡中海量物理資源的高效管控。最后，選擇節(jié)點規(guī)模為100的多跳網(wǎng)絡通信系統(tǒng)作為仿真對象，選取其中的5個和10個節(jié)點作為虛擬網(wǎng)絡節(jié)點。結合實際參數(shù)，仿真分析了所提虛擬網(wǎng)絡拓撲控制方法在業(yè)務拒絕率方面的有效性。仿真結果表明，邊介數(shù)逆序刪邊算法與隨機刪邊算法相比，可刪除更多冗余鏈路，提升帶寬資源的利用率。面向大規(guī)模多跳網(wǎng)絡的虛擬網(wǎng)絡拓撲結構控制方法能夠為用戶合理預留帶寬，在提高帶寬利用率的同時盡可能地降低用戶業(yè)務的拒絕率。