移動邊緣計算網絡下的服務功能鏈部署優化設計

摘要：為解決移動邊緣計算網絡中面向用戶的服務功能鏈部署算法系統成本支出過大、響應時間長的難題，提出了針對服務功能鏈成本與時延聯合優化設計的方法。首先，在服務功能鏈構建階段，根據節點位置和資源狀況，選擇當前最佳節點減少虛擬網絡功能（virtualized network function，VNF）間的時延以提高服務功能鏈的響應時間。其次，在服務功能鏈部署階段，由于映射資源有限，在服務映射節點時應用節點選取算法確定最佳節點映射排列順序，并從中選取最短加權路徑作為各VNF間的通信鏈路。實驗仿真結果表明，相比于已有方案，該方法能有效降低時延和部署成本，并能顯著提高服務功能鏈部署的成功率。

關鍵詞：網絡功能虛擬化； 虛擬網絡功能鏈組成； 服務功能鏈； 運營成本； 可靠性

中圖分類號：TP301.6文獻標志碼：A文章編號：1001-3695（2022）10-035-3108-06

doi： 10.19734/j.issn.1001-3695.2022.01.0105

Optimization design of service function chain deployment under

mobile edge computing network

Chen Jialiang1， Wang Feng1， Zhang Xiao2

（1.School of Information Engineering， Guangdong University of Technology， Guangzhou 510006， China; 2.College of Computer Science， South-Central Minzu University， Wuhan 430074， China）

Abstract：

In order to solve the problems of excessive system cost and long response time of user-oriented service function chain deployment algorithm in mobile edge computing networks， this paper proposed a joint optimization design method for service function chain cost and delay. First， in the construction stage of the service function chain， accor-ding to the node location and resource status， the algorithm selected the current best node to reduce the delay between VNF to improve the response time of the service function chain. Secondly， in the service function chain deployment stage， due to the limited mapping resources， this paper used the node selection algorithm to determine the optimal node mapping order when serving the mapping nodes and selected the shortest weighted path as the communication link between VNFs. The experimental simulation results show that， compared with the existing solutions， the method can effectively reduce the delay and deployment cost， and can significantly improve the success rate of service function chain deployment.

Key words：network function virtualization（NFV）; virtual network function chain composition; service function chain（SFC）; operational expenditure; reliability

0引言

在現代網絡的發展進程中，網絡功能虛擬化（NFV）和軟件定義的網絡（software defined network，SDN）正扮演著越來越重要的角色。當前，網絡運營商使用大量的專用網絡中間件設備，提供不同的網絡功能，比如深度包檢測、防火墻和負載均衡器等。然而，這些專用網絡中間件設備的使用，面臨著諸多問題。例如，網絡升級需要巨大的費用，網絡框架缺乏靈活性，可管理性和可擴展性差等，很難滿足未來網絡發展要求［1］。與使用專用硬件來實現相應功能的傳統網絡不同，NFV是一種解耦硬件和軟件的關鍵技術［2］，以服務功能鏈（SFC）［3］的形式為實現硬件功能。NFV的目標是利用虛擬化技術，在通用服務器或虛擬機上實現網絡功能［4～6］，具有良好的靈活性和可擴展性。

在移動邊緣計算網絡中，計算資源和存儲資源靠近用戶設備的網絡（如無線接入網側），能有效降低網絡接入和計算服務延時［7］。然而，由于CPU資源、存儲資源和無線資源的強耦合性，移動邊緣計算網絡的NFV更具挑戰。一方面，邊緣網絡中的節點種類多樣化，它們的通信特征、計算能力和緩存能力有著很大的差異；另一方面，移動業務的數量和種類快速增長，對服務質量（如時延、吞吐量和可靠性）的要求各異，對網絡資源的需求具有顯著差別。NFV的架構分為由基礎硬件設施組成的物理網絡層和由VNF組成的虛擬網絡層兩層。一個物理網絡可以承載多個虛擬網絡，以有效利用資源［8，9］。為業務請求提供服務，需要完成相應SFC的部署，即在SFC系統性能準則下，在網絡基礎設施上設計VNF映射和路由方案［10］。SFC部署過程由VNF部署和虛擬鏈路映射組成。

如何將SFC高效地映射和放置在底層硬件網絡上，是當前廣泛關注的研究課題。目前的主流研究方向是考慮最小化成本開銷，最大化網絡收益。文獻［11］在跨層網絡場景下，提出采用隨機共享節點的方式來部署VNF，平均分攤資源，但未考慮負載均衡，導致資源利用率較低。文獻［12］提出了一種用于可靠性保障的SFC部署的子鏈協同保護模型，并且考慮VNF和鏈路的可靠性，提出了一種能實現較低部署成本的啟發式算法。文獻［13］采用PageRank算法對節點進行排序，對時延和可靠性實現全局優化，但未考慮節點時延。文獻［14］提出了一種基于中心點的高效益VNF放置和鏈接算法，目標以最小化供應商的成本方式找到最佳VNF數量及其地理位置。文獻［15］采用整數線性規劃（integer linear programming，ILP）模型建模，利用CPLEX等計算工具，優化的目標是最小化運營支出和資源碎片，包括VNF的部署成本以及能源消耗和流量開銷。文獻［16］提出了一種資源感知的服務功能鏈協同構建和映射方法，利用改進的遺傳粒子群算法，降低部署過程中的資源開銷成本。文獻［17］研究了時延約束的最小成本單播SFC設計，但未共享節點。文獻［18］研究了一種成本感知策略，在部署中心負載約束下，協調跨多個數據中心的SFC，建立了ILP模型，提出了一種成本感知SFC編排啟發式算法，降低總部署成本。由于資源約束或請求位置限制，組成SFC中的各VNF可能被分散分布在整個網絡中，尤其是在移動邊緣網絡，邊緣網絡在地理上被劃分成小的邊緣云局域網。邊緣云與邊緣云之間，核心云與邊緣云之間有著地理位置上的距離。當SFC分散在核心云和邊緣網絡中時，在地理上分離的VNF實例之間傳輸數據的時間成本很高［19］。因此，地理位置因素是在邊緣網絡中部署服務功能鏈時須考慮的關鍵問題。此外，上述研究工作缺乏基于時延和資源成本折中準則下的移動邊緣計算網絡SFC部署研究。

針對上述問題，為在移動邊緣計算網絡下更高效地映射和部署SFC，需要充分考慮不同VNF之間的資源協調分配，提高資源利用率，降低網絡部署成本。為此，在有線和無線混合網絡場景下，本文提出一種面向移動邊緣計算網絡的SFC高效可靠部署方法。首先，通過地理位置感知的節點共享算法，判斷部署過程中的各VNF位置是否滿足節點共享條件；其次，利用基于資源感知的節點選取算法，通過選取綜合評分排序靠前的節點，將VNF映射到物理節點上，降低時延、提高可靠性；最后，根據基于帶寬最小的虛擬鏈路映射方案，完成SFC最后的映射。

本文的主要創新總結如下：

a）基于移動邊緣網絡場景，本文提出支持無線功能的SFC優化模型和解決方案，優化不同地理位置的VNF資源配置，在保證用戶服務質量（如時延、可靠性等）的同時，使運營商的成本代價達到最小。首先，在移動邊緣網絡資源約束的背景下，建模用戶服務請求的延遲、VNF資源約束條件，建立SFC系統開銷成本模型。其次，可靠性是SFC系統性能的重要評價指標，由于架構設計等原因，邊緣網絡設備普遍缺乏容災備份等冗余措施，設備故障率遠高于核心云。本文引入可靠性作為約束條件，權衡可靠性與響應時間等客觀需求，合理部署SFC。

b）本文設計SFC底層網絡資源感知的節點選取算法，對當前時刻發起的SFC服務請求，確保SFC的服務請求滿足節點共享條件，在合并VNF時，確保滿足當前時刻物理節點的資源約束條件。針對VNF地理位置布局、路由路徑規劃，優化當前時刻資源分配，篩選可共享物理節點集合，設計虛擬鏈路映射算法，降低SFC的鏈路時延。

1網絡模型和問題描述

圖1顯示了本文系統模型，包括虛擬邏輯服務需求層和物理網絡層。在虛擬邏輯服務需求層，提供了SFC需求，從端源端點到目的端點的SFC請求由不同功能的VNF成鏈式組成，根據其資源需求，使用VNF映射算法映射到物理網絡層。在物理網絡層，提供硬件資源，包括計算硬件、存儲硬件和網絡硬件等資源。本文SFC部署優化方案將從兩層收集SFC需求和底層物理網絡資源信息，設計節點和鏈路從SFC需求到物理網絡映射的VNF嵌入策略。

1.1模型建立

建模物理層網絡為無向圖Euclid Math OneGAp=（Euclid Math OneNAp，Euclid Math OneEAp），其中Euclid Math OneNAp表示邊緣物理節點集合，Euclid Math OneEAp是物理鏈路集合。物理鏈路分為有線鏈路和無線鏈路。在無向圖Euclid Math OneGAp中，每個物理節點上可部署若干虛擬機，每臺虛擬機只實例化一種類型的VNF。記S={Sk|k=1，2，…，K}為SFC請求集合，SFC表示數據流遍歷的一系列網絡服務功能。考慮K個服務請求，每條SFC是由多種類型的VNF，可用Sk={v1，v2，…，vi|vi∈V}表示，V表示VNF集合。物理節點按順序編號，物理節點u表示為nu，具有無線功能的物理節點v表示為nwv。此外，連接節點nu和nv的物理鏈路被表示為e（u，v），無線鏈路則表示為ew（u，v）。本文考慮異構節點的情況，在不同時刻，不同節點具有不同的映射能力和資源量，節點nu∈Euclid Math OneNAp的閑置CPU資源為C（nu），閑置存儲資源M（nu），閑置轉發資源F（nu）。具有無線功能的節點的閑置CPU資源為C（nwv），無線資源包括天線數目A（nwv）、無線資源塊數目B（nwv）和發射功率P（nwv）。

考慮一個時隙系統，其中t∈{1，2，…}表示時隙序號。在邊緣網絡環境中，根據用戶服務請求，VNF將根據一定的功能順序進行組合，組成服務功能鏈。定義VNF流量改變因子為

η（vi）=routrin（1）

其中：rin和rout分別是服務功能VNF輸入流量和輸出流量。VNF節點需要部署資源。例如，與渲染視頻相關的VNF比普通VNF需要更多的GPU資源，而編輯圖像則需要更多的邊緣服務器中的CPU資源。

記無線傳輸時延為Dwi，有線鏈路時延為De（u，v）。首先，無線傳輸時延定義為用戶下行流量與無線節點能夠提供的無線處理速度之比［11］，即

Dwi=in×∏i∈V，k，j∈Euclid Math OneNApη（vi）C（nk，j）（2）

其中：in表示為發送的數據包長度；C（nk，j）表示經由節點nwk傳輸到節點nj的無線鏈路傳輸速率［20］，即

C（nk，j）=Bk，jlog2（1+pkhk，j2σ2j）k≠j∈Euclid Math OneNAp（3）

其中：pk表示節點nwk的無線發射功率；hk，j表示從節點nwk到nj的無線信道系數［11］；Bk，j表示從節點nwk到nj的無線信道帶寬，σ2j則表示節點nj的接收機噪聲方差。

其次，有線節點nu和nv之間的有線鏈路傳輸時延De（u，v）定義為

De（u，v）=in×∏i∈V，j∈Euclid Math OneNApη（vi）Tre（u，v）（4）

其中：Tre（u，v）表示有線鏈路傳輸速率。

在t時刻，記節點nj∈Euclid Math OneNAp的可用資源為

Rj（t）=Cj（t）+Mj（t）+Fj（t）（5）

其中：Cj（t）、Mj（t）、Fj（t）分別是節點可用的CPU、存儲和傳輸資源。在移動邊緣計算網絡環境下，節點nwj∈Euclid Math OneNAp具有無線功能，需要優化設計基站天線數Awj（t）、無線資源塊Bwj（t）以及無線傳輸功率Pwj（t）。記節點nwj∈Euclid Math OneNAp的無線資源為

Rwj（t）=Awj（t）+Bwj（t）+Pwj（t）（6）

記SFC sk的VNF節點部署資源成本為

Cnode=∑vi∈VαC（vi）+βM（vi）+γF（vi）（7）

其中：α、β和γ分別表示CPU、存儲和轉發資源的加權系數。

在NFV環境中，定義組件（VNF或物理節點）的可靠性。記rij表示組件提供服務的平均時間與組件提供服務的平均時間和組件停機維修的平均時間之和的比率，即該組件在規定的時間段內可以無故障地提供服務的概率［21］。

rij=ρρ+ξ（8）

其中：ρ代表組件故障之間的平均時間；ξ代表修復故障組件的平均時間。因此，SFC的可靠性寫成［22］。

Qsk=∏nj∈Nrnj（9）

記虛擬鏈路集合為L=（li，0，li，1，…，li，n），li，i+1表示VNF vi與vi+1之間的虛擬鏈路。用li，0表示為起點和ns之間的虛擬鏈路，li，n是ns和終點之間的虛擬鏈路。

用xi，j表示VNF vi是否部署在邊緣節點nj，yi，j表示虛擬鏈路li是否通過物理鏈路ej部署到底層物理網絡。

xi，j=1vi部署在邊緣節點nj0其他 （10）

yi，j=1li部署在無線鏈路ej0其他（11）

將虛擬鏈路映射到物理鏈路需要一定的帶寬資源，不同節點組成的鏈路不同、不同的映射方法都會產生不同的鏈路成本。記SFC sk的映射成本為

Cmap=∑e（u，v）Euclid Math OneEApin∏viηvki+φe（u，v）+τe（u，v）hop×be（u，v）（12）

其中：第一項表示VNF vi映射在節點（u，v）上，其物理鏈路e（u，v）的映射帶寬資源和服務請求sk的鏈路成本；第二項φe（u，v）表示鏈路e（u，v）之間的固有鏈路消耗；第三項表示鏈路帶寬開銷，be（u，v）為鏈路e（u，v）∈Euclid Math OneEAp的剩余帶寬，τe（u，v）hop表示當前節點到下一個節點的最短跳數。

為避免數據傳輸堵塞和發生硬件故障，考慮物理節點資源的負載均衡。定義無線物理節點nwj的資源成本［23］為

Cwir=∑vi∈V ∑nj∈Euclid Math OneNApH（vi）cwi（nwj）xi，j（13）

cwi（nwj）=a+A（nwj）Aall（nwj）+B（nwj）Ball（nwj）+P（nwj）Pall（nwj）（14）

其中：H（vi）表示虛擬網絡功能vi請求的無線資源；a表示使用具有無線功能的物理節點啟用虛擬功能的固有成本；B（nwj）表示物理節點nwj的無線資源塊；Ball（nwj）表示物理節點nwj的無線資源塊總數；P（nwj）表示物理節點nwj占用的無線功率；Pall（nwj）表示物理節點nwj最大無線功率。

綜上所述，網絡服務的部署代價表示為

Ψcost=ω1Cnode+ω2Cmap+ω3Cwir（15）

其中：ω1、ω2、ω3表示加權系數。

1.2評價指標

對于移動邊緣計算網絡的SFC部署問題，本文考慮資源消耗、請求到達平均時延、請求到達率、平均可靠性、帶寬開銷、重映射鏈路以及算法運行時間等系統性能指標［24，25］。

1）部署成本

在SFC部署中，映射成本建模為物理鏈路中的帶寬損耗。結合SFC部署成本式（15）和帶寬資源開銷，記SFC部署成本為

Δcost=Ψcost+ω4∑li∈Lτhop×b（li）（16）

其中：ω4表示部署成本的權重系數；τhop表示源節點到目的節點之間跳數；b（li）則表示為虛擬鏈路所需帶寬資源。

2）部署成功率

SFC部署成功率定義為在一定時間內到達的SFC請求數量與成功部署的SFC請求數量，即

σsucc=limT→∞∑Tt=0SFCsucc（t）∑Tt=0SFCall（t）（17）

其中：分母表示在總運行時間T中到達SFC請求的總數量；分子表示總運行時間T中成功部署SFC請求的總數量。

3）平均可靠性

基于節點的獨立部署特性，SFC sk的可靠性函數為

Rk=∏vi∈VQsk（18）

本文考慮SFC的平均可靠性概率為

R=∑SFCsucck=1RkSFCsucc（19）

4）請求到達平均時延

定義SFC請求到達平均時延為總的時延與SFC成功部署數量的比值。SFC的時延等于傳輸時延、節點時延、虛擬鏈路所部署鏈路的時延之和：

Dsk=∑i∈V ∑e∈Euclid Math OneEApDi+De（u，v）+dnj+dli（20）

則SFC請求到達平均時延為

D=∑SFCsucck=1DskSFCsucc（21）

5）帶寬開銷

SFC請求到成功部署的過程中所需要的帶寬定義為

Bband=∑SFCsucck=1bskSFCsucc（22）

其中：bsk表示SFC sk成功部署所需要的帶寬消耗。

2系統模型

2.1目標函數

在部署網絡服務需求時，根據可用資源計算最優的網絡功能部署位置，使節點部署的總成本最小。同時，為了滿足業務的SFC可靠性的要求，所選鏈路的時延需滿足用戶時延條件。建立SFC部署的優化目標函數如下：

minμ1Dsk+μ2Δcost（23）

其中：μ1表示SFC服務請求時延的加權系數；μ2表示SFC部署成本的加權系數。

2.2約束條件

任意SFC上的VNF都可以部署在物理層無線或有線網絡上，但只能放在一個物理節點來實例化：

∑nj∈Euclid Math OneNAp，vi∈Vxi，j=1（24）

為了成功保證SFC業務請求的順暢，規定每條物理鏈路最多只能映射一次相同的SFC虛擬鏈路，即

∑lj∈Lyi，j≤1（25）

在每個節點上映射所有VNF所消耗的資源，不能超過節點的最大資源容量。令每個VNF的映射成本為Cvi。物理節點nj提供給VNF映射資源的總容量Cnj，滿足

∑iCvi≤Cnj（26）

為滿足通信資源約束，虛擬鏈路部署時所需要的帶寬不能超過當前時刻鏈路中閑置的帶寬資源，即

∑i（in∏viηvi）π（vi－1，vi）e（u，v）≤be（u，v）（27）

其中：π（vi，vj）e（u，v）∈{0，1}表示是否將虛擬鏈路映射至物理鏈路e（u，v）的離散變量，當值為1時將虛擬鏈路映射至物理鏈路。

當SFC虛擬功能VNF映射到物理節點時，有線鏈路和無線鏈路產生的時延之和需小于規定的用戶時延D0（li），即

Dsk≤D0（li）li∈L（28）

將服務鏈映射到底層邊緣網絡時，SFC必須滿足可靠性條件，即

Qi≥R（29）

對于節點nwj，部署所有VNF所需的無線資源塊、天線數和無線功率不能超過其所能提供的范圍，即

∑vi∈VBl（i）·xi，j≤MBN（j）j∈Euclid Math OneEAp（30）

∑vi∈VAer（i）·xi，j≤MAN（j）j∈Euclid Math OneEAp（31）

∑vi∈VPow（i）·xi，j≤MPN（j）j∈Euclid Math OneEAp（32）

其中：MBN（j）、MAN（j）和MPN（j）分別表示無線節點nwj可以提供的無線資源塊的最大數量、天線最大數目、基站最大功率。

3算法設計

SFC部署問題式（23）屬于一類虛擬化網絡嵌入問題［26］，是NP難問題，求解復雜度非常高。為滿足移動邊緣計算網絡的低時延業務需求，需要低計算復雜度的SFC部署方案。首先，在t時刻隨機SFC請求到達時，對SFC類型進行分類，區分有線類型SFC以及混合有線和無線網絡場景下的SFC，本文提出一種基于地理位置感知的服務功能鏈放置優化算法，判斷該SFC中的VNF位置以及類型，是否滿足共享初始條件，以減少VNF間的時延，提高服務功能鏈的響應時間。若不滿足，按照普通情況進行部署。其次，在當前映射資源約束條件下，使用基于資源感知的節點選取算法，對滿足資源約束條件的節點集合進行篩選評價，確定最佳節點映射排列順序。最后，利用基于帶寬需求感知的虛擬鏈路映射算法，篩選候選路徑集合中滿足帶寬和開銷最小的路徑，選取最短加權路徑作為各VNF間的通信鏈路。

3.1基于地理感知的節點共享算法

在邊緣網絡下，通過共享節點的方式不僅能提高SFC的可靠性，而且將相鄰VNF的數據轉換為節點內部間數據傳輸，還能降低傳輸的時延，減少帶寬壓力。

為此，需要感知SFC中的VNF位置是否屬于同類型VNF，降低地理位置造成的通信延遲。相鄰VNF選擇共享節點時，需要考慮是否屬于同一類型的VNF，即有線或無線VNF。當SFC請求到達時，本文提出基于地理感知的節點共享算法。首先，根據SFC請求搜尋當前SFC中的各位置VNF是否滿足共享初始條件，即相鄰VNF是否功能互斥。然后，根據各VNF的流量改變因子，判斷是否存在合并條件，在功能互相契合的VNF順序集合中，將流量改變因子乘積滿足條件的VNF 進行合并，同時合并對應的VNF資源需求，再進行節點共享。

算法1基于地理感知的節點共享算法

輸入：邊緣信息網絡Euclid Math OneGAp；SFC請求sk中的VNF位置信息。

輸出：待共享節點的VNF集合Temp′。

for 所有待部署的VNF

if當前位置的VNF滿足共享初始條件

進入下一步共享

else

退出共享，按普通情況部署

end if

end for

if 當前SFC是否具有無線功能

for sk中的所有待部署的VNF vwi/vwi

篩選當前位置下滿足無線vwi和vwi+1…或有線vwi和vwi+1…功能性約束的連續VNF集合，進入待合并隊列Temp

for Temp中每個集合的VNF

if η（vii）gt;1amp;η（vii+1）lt;1amp;η（vii+2）lt;1或η（vwii）gt;1 amp; η（vwii+1）lt;1 amp; η（vwii+2）lt;1

進入合并隊列集合Temp′

else 解散當前Temp中的集合

end if

end for

else

for 有線sk中的每一個VNF vi

篩選滿足有線vi和vi+1…功能性約束的連續VNF集合，進入待合并隊列 Temp

for Temp中每個集合的VNF

if η（vii）gt;1amp;η（vii+1）lt;1amp;η（vii+2）lt;1

進入合并隊列集合Temp′

else 解散當前Temp中的集合

end if

end for

end if

3.2基于資源感知的節點選取算法

在對底層網絡資源以及VNF地理位置感知后，遍歷當前SFC的VNF集合，首先篩選出滿足資源約束的VNF節點集合，比如CPU、存儲和轉發等資源。若VNF節點具有無線功能，需要確保滿足無線資源約束條件。其次，利用線性加權分析法，對當前SFC中需要部署的VNF到對應的物理節點進行評分排序，將當前VNF節點部署在綜合評分最高的物理節點，依此類推，直至SFC中所有的VNF部署完成，其中物理節點的評分指標包括節點可靠性、排隊時延、處理時延和發送時延。最后，更新當前時刻下，SFC部署所占用物理節點的剩余資源。

算法2基于資源感知的節點選取算法

輸入：經合并處理后的SFC請求sk。

輸出：服務功能鏈sk構建方案。

for 合并后的集合中的每一個VNF

if 當前VNF不具有無線功能

for 集合Euclid Math OneNAp中的每一個節點nj

篩選滿足CPU、存儲、轉發資源約束的節點集合Θ1

去除源節點、目標節點、無線節點后的集合Θ2

去除已被映射節點后的集合Θ3

在集合Θ3中篩選出評價指標最高的節點進行映射當前VNF

更新各物理節點剩余資源

end for

else

for 集合Euclid Math OneNAp中的每一個節點nwj

篩選滿足CPU、存儲、轉發資源以及無線資源（天線、無線資源塊、功率）約束的節點集合Θ1

去除源節點、目標節點的集合Θ2

去除已被映射節點后的集合Θ3

計算當前無線節點集合Θ3中針對該VNF所產生的時延

利用當前節點可靠性與時延計算加權決策矩陣，篩選出指標最高的節點進行映射該無線VNF

更新各物理節點剩余資源

end for

end if

end for

3.3基于帶寬需求感知的虛擬鏈路映射算法

在VNF部署成功后進行路由選擇，對相應的鏈路進行映射，具體算法步驟如算法3所示。首先，當SFC中所有VNF已經確定好最佳映射物理節點，根據當前時刻的帶寬矩陣，將其轉換為稀疏矩陣格式，刪除所有不滿足當前SFC帶寬要求以及待映射最佳節點間不互通的鏈路，節省內存，提高搜索效率。利用最短路徑算法尋找待映射物理節點間的最短路徑，相應地部署虛擬鏈路。最后，當虛擬鏈路映射完成后，計算當前映射路徑下該SFC的總時延，若不滿足服務最短時延要求，則拒絕該SFC的請求。

算法3基于帶寬需求感知的虛擬鏈路映射算法

輸入：服務功能鏈sk構建方案。

輸出：服務功能鏈sk映射方案。

for sk中所有映射的節點之間組成的鏈路

利用最短路徑算法計算相應的加權路徑帶寬矩陣

得出最短路徑跳數d和途徑節點集合p

計算消耗帶寬以及重復映射鏈路

end for

if該sk不具有無線功能

for sk構建方案中的節點與VNF

計算有線時延

end for

else

for sk構建方案中的節點與VNF

if 當前VNF不具有無線功能

計算有線時延

else

計算無線時延

end if

end for

end if

計算當前映射方案的總時延

if 當前SFC sk的時延不滿足其時延要求

映射失敗，SFC請求未到達

else

映射成功，SFC請求到達，更新鏈路帶寬剩余資源

end if

4仿真實驗

在配置參數為Intel Core i5-10500 CPU和16 GB RAM臺式計算機上，搭建SFC部署仿真平臺。為了較為全面地評估驗證算法的性能，考慮SFC部署資源消耗、請求到達率、平均可靠性、平均帶寬開銷、平均請求時延、重映射的鏈路數量和算法運行時間等性能指標。在實驗中，將隨機算法、遍歷—選擇算法［11］、動態SFC部署算法［13］以及貪婪算法［17］作為基準對比方案。其中，隨機算法共享節點，但不進行最短加權鏈路映射。

在仿真平臺上，邊緣網絡由100個節點生成，其中40個節點啟用無線功能。假設SFC請求動態到達，服從到達率為0.05的泊松分布。為減少隨機因素的影響，仿真結果采取100次實驗后的平均值，其中每次實驗需要50 000個時間單位，如表1所示。

圖2顯示了SFC請求成功部署數量變化對資源利用的影響情況。圖2（a）顯示隨著SFC請求成功部署數量的增加，本文方法的部署資源消耗均小于另外四種方法。文獻［17，13］部署時未共享節點，沒有考慮節點的負載均衡，故資源消耗較多。文獻［11］隨機選擇SFC的一部分進行共享節點，但忽略負載均衡，導致消耗的資源比較多。本文算法根據邊緣網絡資源有限，將物理節點共享給更多的VNF，降低了節點與節點之間不必要的跳數，同時算法3優化了鏈路資源配置，故部署資源開銷最小。圖2（b）顯示SFC成功部署后的平均時延對比關系。本文算法和基準隨機算法明顯優于其他兩種算法，這是因為節點共享可將VNF之間的數據變成節點內部的數據傳輸，降低了一定的傳輸時延。本文算法考慮邊緣網絡中節點和鏈路容量限制，將綜合部署時延納入節點篩選權重算法中，能獲得更低的節點時延。在節點排序評價權重中，文獻［17，11］在部署過程中考慮了時延權重，故性能優于未考慮部署鏈路時延的文獻［13］。圖2（c）顯示，由于本文算法根據約束條件，對節點進行共享，并使用映射算法考慮了負載的均衡，使得帶寬開銷更少。基準隨機算法也進行了節點共享處理，優于其他三種基準算法，但因為部署時未進行最短加權鏈路映射，改進的效果并不明顯。最后，圖2（d）中本文映射算法利用最短加權鏈路映射，在搜索最短路徑過程中使用帶寬矩陣約束，對節點間路徑避免出現循環有一定的幫助，使得重映射鏈路的數量少于另外四種方法。

圖3顯示了算法性能變化的影響。圖3（a）顯示了五種不同部署算法的SFC請求到達率隨時間變化曲線。文獻［13］未綜合考慮部署過程中各部分時延，基準隨機算法和文獻［17］部署過程中都不能同時滿足可靠性以及時延的約束，故請求到達率較低。文獻［11］雖有共享節點資源，但因隨機選擇SFC的部分共享，沒有考慮負載均衡，資源消耗增加，故請求到達率最低。本文算法部署時考慮了節點的負載均衡，利用流量改變因子的特征將部分VNF合并在同一個物理節點，共享其資源，降低部署開銷，提高了請求到達率。圖3（b）顯示了平均SFC可靠性隨成功部署的SFC數目的變化曲線。本文算法和基準隨機算法的平均可靠性系數高于0.8。這是因為節點共享算法考慮了節點可靠性的權重，優先選擇可靠性較高的節點。多個VNF合并部署到一個物理節點上，在篩選節點排序時會增加一定的權重，有助于提高SFC的可靠性。文獻［11］部署過程中選擇性地共享節點，增加了SFC的可靠性，故優于剩下的兩種基準算法。文獻［13］考慮了網絡拓撲和可靠性，但未將節點共享。文獻［17］未考慮節點可靠性，在篩選節點集合時，無法保證可靠性。圖3（c）顯示了本文算法具有最小的時間復雜度。在VNF部署的最佳候選節點篩選時，本文算法和基準算法的時間復雜度均為O（N），其中N表示物理節點數目。然而，在最短路徑映射過程中，不同于基準算法方案，本文算法將當前路徑矩陣轉換為稀疏矩陣，極大降低了最短路徑生成的時間復雜度。

5結束語

本文研究了移動邊緣計算網絡的SFC部署問題，開發了一種成本與時延聯合優化設計的方法。在SFC構建階段，根據節點位置和資源狀況，選擇當前最佳節點減少VNF間的時延以提高服務功能鏈的響應時間。在SFC部署階段，由于映射資源有限，在服務映射節點時應用節點選取算法確定最佳節點映射排列順序，并從中選取最短加權路徑作為各VNF間的通信鏈路。實驗結果表明，相比已有方案，本文算法能有效降低SFC服務請求時延，提高SFC可靠部署成功率。下一步研究方向將針對設備直通（device to device，D2D）無線通信網絡，考慮無線信道衰落和用戶干擾，設計低功耗SFC部署方案與資源管理算法。

參考文獻：

［1］祖家琛，胡谷雨，嚴佳潔，等. 網絡功能虛擬化下服務功能鏈的資源管理研究綜述［J］. 計算機研究與發展，2021，58（1）： 137-152. （Zu Jiachen，Hu Guyu，Yan Jiajie，et al. Resource management research of service function chain under network function virtualization［J］. Computer Research and Development，2021，58（1）： 137-152.）

［2］De Sousa N F S，Lachos P D A，Rosa R V，et al. Network service orchestration： a survey ［J］. Computer Communications，2019，142： 69-94.

［3］Hantouti H，Benamar N，Taleb T，et al. Traffic steering for service function chaining［J］. IEEE Communications Surveys amp; Tutorials，2018，21（1）： 487-507.

［4］Han Bo，Gopalakrishnan V，Ji Lusheng，et al. Network function virtualization： challenges and opportunities for innovations ［J］. IEEE Communications Magazine，2015，53（2）： 90-97.

［5］ETSI. ETSI GR NFV 001，Network functions virtualisation（NFV） ; use cases［S］. ［S.l.］： ETSI World Class Standards，2021.

［6］Yeganeh S H，Tootoonchian A，Ganjali Y. On scalability of software-defined networking［J］. IEEE Communications Magazine，2013，51（2）： 136-141.

［7］Wang Feng，Xu Jie，Ding Zhiguo. Multi-antenna NOMA for computation offloading in multiuser mobile edge computing systems［J］. IEEE Trans on Communications，2018，67（3）： 2450-2463.

［8］Yu Minlan，Yi Y，Rexford J，et al. Rethinking virtual network embedding： substrate support for path splitting and migration［J］. ACM SIGCOMM Computer Communication Review，2008，38（2）： 17-29.

［9］Hu Qian，Wang Yang，Cao Xiaojun. Resolve the virtual network embedding problem： a column generation approach［C］// Proc of IEEE INFOCOM. Piscataway，NJ： IEEE Press，2013： 410-414.

［10］Siasi N，Jasim M，Crichigno J，et al. Container-based service function chain mapping［C］// Proc of SoutheastCon. Piscataway，NJ： IEEE Press，2019： 1-6.

［11］Chen Jia，Liu Hongqiao，Jia Haiyu. Cross-layer resource allocation in wireless-enabled NFV［J］. IEEE Wireless Communications Letters，2020，9（6）： 879-883.

［12］Zhang Yuncan，He Fujun，Oki E. Availability-aware service chain provisioning with sub-chain-enabled coordinated protection［C］// Proc of IFIP/IEEE International Symposium on Integrated Network Management. Piscataway，NJ： IEEE Press，2021： 638-642.

［13］唐倫，趙培培，趙國繁，等. 基于QoS保障的服務功能鏈動態部署算法［J］. 北京郵電大學學報，2018，41（6）： 90-96. （Tang Lun，Zhao Peipei，Zhao Guofan，et al. Dynamic deployment algorithm of service function chain based on QoS guarantee［J］. Journal of Beijing University of Posts and Telecommunications，2018，41（6）： 90-96.）

［14］Ahvar S，Phyu H P，Buddhacharya S M，et al. CCVP： cost-efficient centrality-based VNF placement and chaining algorithm for network service provisioning［C］// Proc of IEEE Conference on Network Softwarization. Piscataway，NJ： IEEE Press，2017： 1-9.

［15］Bari F，Chowdhury S R，Ahmed R，et al. Orchestrating virtualized network functions ［J］. IEEE Trans on Network and Service Ma-nagement，2016，13（4）： 725-739.

［16］孫士清，彭建華，游偉，等. 5G網絡下資源感知的服務功能鏈協同構建和映射算法［J］. 西安交通大學學報，2020，54（8）： 140-148. （Sun Shiqing，Peng Jianhua，You Wei，et al. Collaborative construction and mapping algorithm of resource-aware service function chain under 5G network［J］. Journal of Xi’an Jiaotong University，2020，54（8）： 140-148.）

［17］Yuan Bo，Ren Bangbang. Embedding the minimum cost SFC with end-to-end delay constraint ［C］// Proc of the 5th International Conference on Mechanical，Control and Computer Engineering. Piscata-way，NJ： IEEE Press，2020： 2299-2303.

［18］Zhong Xuxia，Wang Ying，Qiu Xuesong，et al. Cost-aware service function chain orchestration across multiple data centers ［C］// Proc of NOMS-IEEE/IFIP Network Operations and Management Sympo-sium. Piscataway，NJ： IEEE Press，2018： 1-7.

［19］牛夢. 邊緣網絡中面向可靠性和響應時間的服務功能鏈調度機制研究［D］. 北京：北京郵電大學，2021. （Niu Meng. Research on service function chain scheduling mechanism for reliability and response time in edge networks ［D］. Beijing： Beijing University of Posts and Telecommunications，2021.）

［20］Shannon C E. A mathematical theory of communication［J］. The Bell System Technical Journal，1948，27（3）： 379-423.

［21］Qu Long，Khabbaz M，Assi C. Reliability-aware service chaining in carrier-grade softwarized networks ［J］. IEEE Journal on Selected Areas in Communications，2018，36（3）： 558-573.

［22］Ayoubi S，Zhang Yanhong，Assi C. RAS： reliable auto-scaling of virtual machines in multi-tenant cloud networks［C］// Proc of the 4th International Conference on Cloud Networking. Piscataway，NJ： IEEE Press，2015： 1-6.

［23］賈海宇. 智慧協同無線網絡下面向服務需求的功能動態部署機制研究 ［D］. 北京：北京交通大學，2019.（Jia Haiyu. Research on the dynamic deployment mechanism of service demand-oriented functions in smart collaborative wireless networks［D］. Beijing： Beijing Jiaotong University，2019.）

［24］翟東，孟相如，康巧燕，等. 面向時延與可靠性優化的服務功能鏈部署方法［J］. 電子與信息學報，2020，42（10）： 2386-2393. （Zhai Dong，Meng Xiangru，Kang Qiaoyan，et al. Service function chain deployment method for delay and reliability optimization［J］. Journal of Electronics and Information，2020，42（10）： 2386-2393.）

［25］陽勇，孟相如，康巧燕，等. 基于流量優化的可靠服務功能鏈部署方法［J］. 系統工程與電子技術，2021，43（10）： 3017-3025. （Yang Yong，Meng Xiangru，Kang Qiaoyan，et al. Deployment method of reliable service function chain based on traffic optimization［J］. System Engineering and Electronic Technology，2021，43（10）： 3017-3025.）

［26］Amaldi E，Coniglio S，Koster A M，et al. On the computational complexity of the virtual network embedding problem［J］. Electronic Notes in Discrete Mathematics，2016，52： 213-220.

收稿日期：2022-01-25；修回日期：2022-03-07基金項目：國家自然科學基金資助項目（61901124，61902437）；廣東省自然科學基金資助項目（2021A1515012305）；湖北省自然科學基金資助項目（2020CFB629）

作者簡介：陳嘉亮（1997-），男，廣東梅州人，碩士研究生，主要研究方向為網絡功能虛擬化、邊緣計算；王豐（1987-），男（通信作者），廣東廣州人，副教授，碩導，博士，主要研究方向為移動邊緣計算、機器學習與凸優化理論應用（fengwang13@gdut.edu.cn）；張瀟（1986-），男，湖北武漢人，教授，主要研究方向為無線傳感及無人機網絡、算法設計與分析.