移動邊緣計算網絡中聯合無線多播的服務功能鏈部署算法

王侃，趙楠，李軍懷，王懷軍

（1.西安理工大學計算機科學與工程學院，陜西 西安 710048；2.大連理工大學信息與通信工程學院，遼寧 大連 116024）

1 引言

5G 移動通信系統以其靈活性和高效性為用戶提供了超高吞吐量和超低時延的服務體驗[1]。作為5G 的關鍵技術，網絡功能虛擬化（NFV,network function virtualization）和移動邊緣計算（MEC,mobile edge computing）已得到學術界和工業界的廣泛關注[2-3]。不同于傳統網絡通過部署專門硬件來實現網絡功能，NFV 將軟硬件解耦，通過在商用服務器上部署虛擬網絡功能，構造面向各類業務需求的、將虛擬網絡功能有序排列的服務功能鏈（SFC,service function chain），為用戶提供差異化和定制化的服務[2]。MEC 將部分或全部網絡功能卸載到靠近用戶的邊緣網絡，將顯著提升服務的時延和吞吐量性能，有效降低核心網的業務擁塞[3]。

NFV 和MEC 相互補充，通過在邊緣網絡的基站中部署虛擬網絡功能，可使用戶就近接受網絡服務，從而增強了網絡管理的靈活性和可伸縮性[4]。然而，與云接入網（C-RAN,cloud radio access network）等集中式網絡架構相比，邊緣網絡中SFC部署問題將面臨如下特有挑戰。

1) 與集中式網絡架構中的云計算服務器不同，MEC 服務器的計算容量和存儲容量通常受限[5-7]；單個MEC 服務器只能部署SFC 中的部分網絡功能。如何協同利用受限的MEC 服務器資源，進行虛擬網絡功能的有序部署，對SFC 部署算法帶來設計上的挑戰。

2) 與核心網中SFC 部署不同，邊緣網絡中SFC的部署不僅涉及數據流在基站與基站之間基于有線鏈路的服務路徑選擇，而且需考慮執行完最后一項網絡功能后，數據流經基站到用戶的無線鏈路傳輸。

因此，基于上述挑戰，邊緣網絡SFC 部署問題面臨的關鍵技術包括服務路徑選擇技術和無線鏈路干擾消除技術。首先，針對實時服務請求，服務路徑選擇表示引導數據流依次通過能夠支持SFC中網絡功能的服務基站。其次，由于無線鏈路的廣播特性，在執行完SFC 的最后一項網絡功能后，數據流經基站到用戶的無線鏈路存在相互干擾；利用正交頻譜資源分配或波束成形技術以消除用戶間干擾，是邊緣網絡SFC 部署問題的另一項關鍵技術。如何針對差異化的用戶需求和有限的網絡資源，設計低開銷的、基于干擾消除的邊緣網絡SFC部署算法，已成為學術界和工業界的研究熱點。

已有研究工作通常關注端到端的、面向用戶的SFC 部署方案[8-11]，在網絡資源受限的約束下，實現虛擬網絡功能到MEC 服務器的有效映射，優化用戶的服務體驗。文獻[8]研究了邊緣網絡中SFC的服務遷移問題，基于用戶隨機游走模型，考慮了遷移代價和時延約束，提出了一種在線服務遷移算法，以最小化用戶的服務中斷概率。同樣基于用戶運動模型，文獻[9]研究了面向內容緩存服務的最短路由路徑的SFC 部署問題，將最短路徑問題建模為一個整數線性規劃（ILP,integer linear programming）問題，提出了一種低復雜度的啟發式算法。基于軟件定義的邊緣網絡，文獻[10]同時考慮了用戶的業務體驗和服務的可靠性需求，研究了端到端時延約束下系統的吞吐量優化問題，利用多路徑路由策略保障服務的可靠性，并利用主對偶方法找到每條可行路徑的分配帶寬。基于單路徑路由策略，文獻[11]同時考慮了節點處理容量和鏈路帶寬約束，研究了最小化數據流開銷的SFC 映射問題。綜上所述，已有的SFC 部署方案通常是面向用戶的，為每個用戶部署一條專用的、定制化的SFC。然而，隨著內容提供業務（例如，視頻、音樂和文件）的持續增長，邊緣網絡中的流行內容會被多個用戶重復下載[12-13]，此時，若對具有相同內容請求的多個用戶均部署定制化的SFC，不僅會增大邊緣網絡中數據流的開銷，造成業務擁塞，而且會導致額外的MEC 服務器功耗開銷。因此，研究基于內容分組的SFC 部署算法具有重要理論意義和現實價值。

將請求同一內容的用戶劃分到一組，設計面向內容的SFC 部署算法，使該組所有用戶共享一條SFC，可有效降低系統數據流開銷和功耗開銷。然而，與核心網不同，邊緣網絡無線信道的廣播特性使同一內容到多個用戶的多播傳輸存在相互干擾。基于正交頻譜資源分配，文獻[14]提出了一種兩階段協作多播機制，以降低系統傳輸功耗，并增強系統覆蓋率。首先，利用隨機幾何理論，采用基于平均接收信號強度的選擇合并技術，分析了基站傳輸功耗和系統傳輸功耗的相互關系；其次，提出了一種基于扇形環結構的移動中繼部署方案，進而推導了基于期望覆蓋率的最優基站傳輸功耗的表達式。基于波束成形技術，文獻[15]將請求同一內容的用戶進行組劃分，形成多播組，對組內所有用戶發送相同的數據符號，從而有效節省了無線頻譜資源，并降低了數據流開銷。文獻[16]研究了C-RAN 中運營商的收益優化問題，同時考慮了高帶寬和低時延2 種典型5G 業務，針對高帶寬的內容提供業務，利用波束成形技術實現組內用戶干擾抑制；針對低時延業務，利用正交頻譜資源消除用戶間干擾。同樣基于C-RAN，文獻[17]研究了基于混合時間尺度的內容緩存服務，利用協作多播技術以抑制組內用戶干擾，綜合考慮系統功耗和用戶吞吐量需求等約束，以最大化系統的長期收益。綜上所述，針對面向內容的無線多播技術的研究通常只考慮內容從接入基站到用戶的無線傳輸這一環節。然而，與云計算服務器相比，MEC 服務器的存儲和計算資源通常受限，單個接入基站只能部署SFC 中的部分功能。因此，基于內容分組，引導數據流依序通過多個服務基站，服務路徑規劃需聯合考慮基站之間的有線鏈路和接入基站到用戶的無線鏈路，構造“第一個服務基站→第二個服務基站→…→最后一個服務基站（接入基站）→用戶”的端到端服務路徑。

本文主要的研究工作如下。

1) 面向內容提供服務，建立邊緣網絡中聯合無線多播的SFC 部署模型。最大化系統中數據流開銷和功耗開銷，并滿足鏈路帶寬約束、處理容量約束、吞吐量需求約束、SFC 部署序列約束、波束向量與信號處理功能的耦合約束，以及最大發射功率約束。綜合考慮數據流、服務器功能維護功耗、服務器功能服務功耗和無線傳輸功耗這4 種系統開銷，建立波束成形設計和SFC 部署的聯合優化問題。該問題是一個NP（non-deterministic polynomial）難問題，很難找到多項式時間求解算法。

2) 利用拉格朗日對偶分解技術，將原優化問題轉化為2 個獨立子問題。利用基于Lp范數懲罰項的連續凸近似算法，將ILP 項式的SFC 部署問題松弛為一個線性規劃（LP,linear programming）問題，并給出了原問題和松弛問題的最優解等價性證明；利用路徑跟隨技術，將非凸波束向量優化問題轉化為一系列凸子問題，并給出了算法的單調性分析。

3) 仿真結果表明，本文算法具有良好收斂性能。將本文算法與最優單播SFC 部署算法和隨機多播SFC 部署算法進行對比，驗證了本文算法的有效性。

2 系統模型

在邊緣網絡中，通過在基站的MEC 服務器中部署NFV 技術，基站不僅能提供基帶處理單元（BBU,base-band unit）功能，而且可支持緩存、計算、防火墻和網絡地址轉換等多種虛擬網絡功能。考慮一個多基站部署的邊緣網絡，基站集合表示為N={1,2,…,N}，如圖1 所示。基站之間通過X2+鏈路實現互聯，同時每個基站配置I根天線和一個商用服務器。邊緣網絡中分布K個用戶，用集合K={1,2,…,K}表示。假設所有用戶均請求內容提供服務，并將請求同一內容的用戶分配到同一多播組。多播組用集合M={1,2,…,M}表示，而多播組m的所屬用戶集合用 G(m)表示。

圖1 多基站部署的邊緣網絡

2.1 SFC 模型和容量約束

在基于NFV 技術的邊緣網絡中，每項內容提供服務可映射為一條端到端的SFC 部署，即“第一個服務基站→第二個服務基站→…→最后一個服務基站（接入基站）→用戶”的端到端服務路徑。在多播組m中，任一數據流在被基站天線發送到用戶之前，需遍歷SFC 的每一項網絡功能。分別用和表示該條SFC 中第一和最后一項功能，則可用來描述該條SFC。多播組m的任一數據流需起源于（例如，圖1 中的內容1 和內容2 的MEC 服務器)，依序遍歷 F(m)中其他功能，最終以（例如，圖1 中部署BBU1和BBU2的MEC 服務器）終止服務。如圖1 所示，邊緣網絡中部署了2 條基于內容提供服務的SFC，每個數據流需依次遍歷緩存功能、計算功能和信號處理功能，最終由基站無線傳輸到終端用戶。

2.2 多播模型

與協同多點傳輸（CoMP,coordinated multiple-point transmission）[15-20]技術不同，本文假設每個基站在自己的天線組內獨立進行多播波束成形，對每個基站分配正交的頻譜資源，從而有效消除了小區間干擾。基于單天線CoMP 技術，文獻[18-19]提出了宏分集協同多點傳輸（MD-CoMP,macro diversity coordinated multi-point transmission）概念，將小區頻率復用因子設為1，通過對同小區用戶分配正交頻譜資源，以消除小區內干擾。因此，用戶所受干擾為來自其他基站簇的小區間干擾。本文沒有考慮基站之間的CoMP，這是因為，若考慮CoMP，則每個用戶將選擇多個接入基站，本文考慮的單服務路徑規劃問題將成為一個多服務路徑規劃問題，進一步增大優化問題的求解難度。定義每個基站的無線頻譜帶寬為B，則用戶k從基站n處得到的接收信號信干噪比（SINR,signal to interference plus noise ratio）Γk,n為

2.3 問題描述

一方面，為最小化SFC 路徑中的數據流開銷，每條SFC 的功能應集中部署在盡可能少的MEC 服務器中，然而受限于MEC 服務器的處理容量，同一SFC 的不同功能往往部署到不同的基站，這將不可避免地增大數據流開銷。另一方面，不僅基站的發送天線帶來無線傳輸功耗開銷，MEC 服務器的功能維護和功能服務也將導致服務器功耗開銷。系統開銷應綜合考慮數據流開銷和功耗開銷。因此，可將系統總開銷C定義為

其中，η為平衡數據流開銷和功耗開銷的折中系數，Pf,n為基站n維護功能f的功耗，為基站為多播組m提供功能的服務功耗。式(10)中，系統開銷分別為數據流開銷、服務器功能維護功耗開銷、服務器功能服務功耗開銷和無線傳輸功耗開銷。首先，相鄰2 個網絡功能之間的數據傳輸將導致數據流開銷；為實現SFC 的有序部署，每個基站需為多播組的服務請求提供網絡功能，將導致功能維護開銷和功能服務開銷。上述3 種功耗發生在邊緣網絡的MEC服務器中或基站之間的有線鏈路中。其次，為實現端到端（從邊緣網絡基站到多播用戶）的數據傳輸，多播組的任一數據流需遍歷SFC 中的每一項網絡功能，最終到達用戶的所屬服務基站，使用波束成形等信號處理，通過無線多播的方式到達用戶。因此，無線傳輸功耗發生在無線多播環境中服務基站到多播用戶的最后一跳中。4 種系統開銷的關系如圖1 所示。

為最小化SFC 部署的系統開銷，節省邊緣網絡資源，將優化問題 P0描述如下。

觀察 P0可得，波束成形和基站間的SFC 部署之間存在如下折中關系。

1) 基站之間的SFC 部署將決定用戶的接入基站選取。邊緣網絡的SFC 部署將規劃邊緣網絡到用戶的端到端服務路徑，從而為每個用戶選取一個接入基站，以無線傳輸方式完成數據流到用戶的最后一跳。若只優化基站之間的SFC 部署開銷，不考慮用戶的接入基站選取，將導致無線傳輸功耗開銷過高。

2) 用戶的接入基站選取將影響基站之間的SFC 部署。作為SFC 部署的最后一個服務節點，用戶的接入基站將數據流經無線空口傳輸到用戶。同時，接入基站的位置將影響上一個服務基站的選取，從而依次逆序影響其他所有服務基站的選取。因此，若只考慮波束成形算法的無線傳輸功耗，不考慮用戶的接入基站選取，將導致基站之間SFC 部署開銷過高。

因此，無線傳輸的波束成形和基站之間的SFC部署存在折中關系，需聯合優化。

3 算法設計

問題 P0可規約為一個無容量約束設施選址（UFL,uncapacitatedutilitylocation）問題，而UFL問題已被證明是一個NP難問題[9]，因此，P0也是一個NP 難問題，很難找到多項式時間求解算法。通過觀察所有約束，發現波束變量和功能部署變量只在式(7)相耦合。因此，本文采用拉格朗日對偶分解技術，通過將wm,n和解耦合，從而將 P0分解為2 個獨立的子問題。

3.1 拉格朗日對偶分解

首先，引入拉格朗日對偶乘子λ={λm,n}，將式(7)疊加到 P0的目標函數，即

然而，P2和 P3均難以求解。首先，P2仍可規約為NP 難的UFL 問題；其次，盡管 P3的優化目標是一個凸函數，但式(9)是一個非凸約束。因此，本文提出基于懲罰項的SFC 部署算法和基于路徑跟隨播波束成形算法，分別求解 P2和 P3。

3.2 基于懲罰項的SFC 部署算法

因為 P2為一個ILP 問題，將 P2中的變量x、y和z松弛，則 P2將成為一個LP 問題。然而，P2通常和其LP 形式不等價，求解 P2對應的LP 問題無法確保其最優解為二進制變量。而求解ILP 問題通常采用分支定界法或割平面法[21-22]，計算復雜度較高，難以求解較大網絡規模的SFC 部署問題。因此，本文采用基于Lp(0

其中，p∈(0,1)且ε為任意正數。由文獻[11]可知，盡管式(18)的可行域已被松弛，但其最優解仍為二進制變量。因此，式(18)的最優值計算如下。

然后，根據Lp范數的上述性質，將一個基于Lp范數的懲罰項Pε(y)疊加到 P2的目標函數，并將變量松弛。則 P2可轉化為

3.3 基于路徑跟隨的波束成形算法

3.4 計算復雜度分析

4 仿真分析

為驗證本文算法的有效性，首先分別驗證基于懲罰項的SFC 部署算法、基于凹函數近似的波束成形算法和次梯度方法的收斂性能。其次，將本文算法與文獻[9]中的最優單播SFC 部署算法和文獻[15]中的隨機多播SFC 部署算法進行對比。文獻[15]中并未考慮SFC 的最優部署，所以將文獻[15]中的多播波束成形機制和SFC 的隨機部署相結合。

本文采用的仿真工具是MATLAB R2014b，并使用了凸優化工具包CVX。網絡模型為一個經典的六邊形七小區蜂窩網絡[15,25]，基站間隔設為200 m，每個基站配置10 根天線和5 MHz 頻譜帶寬，基站最大發射功率為46 dBm。針對信道模型，用戶和基站之間的路徑損耗模型為PL=32.45+10lgd，PL 單位為dB，d單位為m，小尺度衰落模型服從瑞利分布，對數陰影衰落設置為8 dB，信道熱噪聲功率譜密度為?174 dBm/Hz。針對內容緩存，使用U-vMOS 視頻體驗標準[12]的前5 種等級，假設系統存在5 種不同內容，其吞吐量需求分別為0.5 Mbit/s、1 Mbit/s、4 Mbit/s、5 Mbit/s 和10 Mbit/s；每個基站的MEC 服務器隨機選取2 項內容進行緩存。針對內容緩存之外的其他功能，假設系統中存在6 項功能，每個MEC 服務器隨機選取3 項功能，每項功能的處理容量服從5～15 Mbit/s 的隨機均勻分布，每項功能的維護功耗和服務功耗服從1～4 W的均勻分布。針對有限鏈路，任意2 個基站之間的鏈路帶寬服從10～50 Mbit/s 的均勻分布。

算法參數設置中，算法1 中次梯度方法的初始步長設為100，并按照0.4 的衰減系數逐次衰減；算法2 中，ε和σ的初始值分別設為0.01 和10，乘數因子o=0.8，?=3。

圖2 給出了不同折中系數η下的基于懲罰項的SFC 部署算法的收斂性能。設用戶數為20，每個用戶等概率請求一項內容服務，每項服務的SFC 中均包含4 項有序功能。為衡量算法性能，使用相鄰兩次 P2-Lp問題的最優解的范數差，即，作為性能指標。如圖2 所示，在不同η設置下，本文算法均具有良好收斂性能，在迭代10 次之內達到穩定值。

圖2 基于懲罰項的SFC 部署算法的收斂性能

圖3 給出了不同折中系數η下的基于路徑跟隨的波束成形算法的收斂性能。設用戶數為20，且等概率請求一項內容服務，每項服務的SFC 均包含4 項有序功能。因為該部分算法僅涉及了基站的波束成形設計，所以使用無線傳輸功耗作為性能指標。由圖3 可看出，在不同η設置下，本文算法均在迭代15 次之內收斂，且功耗值單調遞減。這也驗證了3.3 節有關算法單調性分析的正確性。

圖4 給出了不同折中系數η下的次梯度方法的收斂性能。用戶數和SFC 的設置均與圖2 和圖3 一致。為公平衡量算法性能，克服η過大或過小對問題 P0的優化目標的影響，僅使用系統功耗開銷作為性能指標。首先，由圖4 可知，盡管次梯度方法相較于基于懲罰項的SFC 部署算法和基于路徑跟隨的波束成形算法的收斂性能較差，但均在迭代30次左右趨于穩定值。其次，與圖3 相比，系統總功耗開銷和無線傳輸功耗開銷之間的差值表現為功能維護功耗開銷和功能服務功耗開銷。最后，隨著η的增大，系統總功耗開銷逐漸降低。這是因為原始優化問題 P0的優化目標為最小化系統開銷，η的增大將使功耗開銷的權重增大，數據流開銷的權重減小，從而使最優值中的功耗部分降低。

圖3 基于路徑跟隨的波束成形算法的收斂性能

圖4 次梯度方法的收斂性能

圖5 給出了不同折中系數η下算法1 功耗開銷?數據流開銷折中曲線。與圖4 結論類似，當η=106時，可認為η趨近于無窮大，系統開銷只考慮功耗開銷，P0簡化為功耗開銷最小化問題，而算法1 成為功耗開銷最小化算法。因此，優化目標中不考慮數據流開銷，η=106時數據流開銷超過了60 Mbit/s。在η=10?6時，可認為η趨近于無窮小，系統開銷只考慮數據流開銷，P0簡化為數據流最小化問題，優化目標中不涉及功耗開銷，故η=10?6時功耗開銷達到105 W。圖4 和圖5 的結論為合理、靈活選擇折中系數η提供了理論依據和經驗參考。

圖5 算法1 的功耗開銷?數據流開銷折中曲線

圖6 給出了本文算法和比較算法在不同用戶數下的系統總功耗性能。SFC 的設置均與圖2～圖4一致，η=103。由圖6 可看出，本文算法性能優于最優單播SFC 部署算法。這是因為，若為每個用戶獨立分配一個波束向量，將顯著增大基站的無線傳輸功耗，使系統總功耗提升。同時，在只考慮系統功耗開銷時，隨機多播SFC 部署算法的性能優于本文算法。這是因為，η=103時本文算法需折中考慮功耗開銷和數據流開銷，最優值中的數據流開銷部分將導致功耗開銷部分增大；而隨機多播SFC 部署算法不需要考慮數據流開銷。

圖6 系統總功耗與用戶數之間關系

圖7 給出了本文算法和比較算法在不同用戶數下的數據流開銷性能。SFC 的設置均與圖2～圖4一致，η=103。如圖7 所示，曲線呈分段線性的折線形式，這是因為，數據流開銷需取U-vMOS 吞吐量需求的整數倍，無法像功率分配一樣取任意連續值。在只考慮系統數據流開銷時，最優單播SFC 部署算法的性能優于本文算法。這是因為，η=103時本文算法需折中考慮功耗開銷和數據流開銷，最優值中的功耗開銷部分同樣會導致數據流開銷部分的增大；而最優單播SFC 部署算法不需要考慮功耗開銷。

圖7 系統數據流開銷與用戶數之間關系

5 結束語

本文提出了一種面向內容的聯合無線多播的SFC 部署算法，建立了波束成形設計和SFC 映射的聯合優化模型。利用拉格朗日對偶分解技術，將優化問題轉化為SFC 部署和波束成形設計2 個獨立子問題；利用基于Lp范數懲罰項的連續凸近似算法，將整數形式的SFC 部署問題松弛為一個等價線性規劃問題，并給出了最優解的等價性證明；利用路徑跟隨技術，將非凸波束向量優化問題轉化為一系列凸優化問題，并給出了算法單調性分析。仿真結果表明，所提算法在系統開銷方面優于最優單播SFC 部署算法和隨機多播SFC 部署算法。未來工作中，將進一步研究聯合協作多播波束成形的多服務路徑SFC 部署問題。

附錄 定理1 證明