面向大規模多跳網絡的虛擬網絡拓撲控制方法

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

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

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

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

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

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

1 系統性能指標定義

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

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

4)介數。節點的介數是指網絡中所有的最短路徑中經過該節點的數量；邊的介數含義與節點介數的含義類似。

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

2 虛擬網絡構建方法

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

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

2.1 建立虛擬網絡拓撲

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

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

圖1 虛擬邏輯網絡構建過程

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

2.2 虛擬網絡拓撲結構優化

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

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

步驟1獲取當前網絡連接關系。

步驟2依照邊的索引值依次判定網絡內是否存在孤立節點。如果是，則跳轉至步驟6；如果否，則跳轉步驟3。

步驟3依照節點的索引值，依次計算該節點至其他所有節點的最短路徑，并且統計所有邊在該節點所有最短路徑內的出現次數。

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

步驟5更新網絡拓撲結構，并返回步驟2。

步驟6輸出統計結果。

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

圖2 加權介數逆序剪邊仿真結果

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

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

圖3 加權介數逆序剪邊仿真網絡拓撲

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

2.3 虛擬網絡資源的自適應分配

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

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

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

步驟3統計每條虛擬鏈路單位時間內并行業務傳輸數量，將其作為鏈路價值函數。

步驟4將鏈路資源池內剩余資源按統計價值函數比例靈活分配給每條鏈路。

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

步驟6輸出分配結果。

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

2.4 虛擬網絡的實體映射

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

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

3 建模與仿真分析

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

3.1 仿真環境

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

圖4 仿真網絡拓撲示意圖

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

表1 多跳網絡通信系統參數

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

3.2 仿真結果分析

單域內5個虛擬網絡節點通信效率隨刪邊個數變化情況如圖5所示。5個虛擬網絡節點分別為node_3、node_0、node_8、node_11和node_16。

圖5 5個節點通信效率隨刪邊數目變化情況

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

圖6為單域內10個虛擬網絡節點通信效率隨刪邊個數變化的情況。10個虛擬網絡節點分別為node_1、node_6、node_18、node_3、node_0、node_8、node_11、node_12、node_16和node_19。

圖6 10個節點通信效率隨刪邊數目變化情況

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

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

圖7 不同拓撲5個虛擬網絡用戶的業務拒絕數

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

圖8 不同拓撲下5個虛擬網絡用戶的業務時延

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

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

4 結語

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