移動(dòng)邊緣計(jì)算網(wǎng)絡(luò)中聯(lián)合無(wú)線多播的服務(wù)功能鏈部署算法

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

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

1 引言

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

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

1) 與集中式網(wǎng)絡(luò)架構(gòu)中的云計(jì)算服務(wù)器不同，MEC 服務(wù)器的計(jì)算容量和存儲(chǔ)容量通常受限[5-7]；單個(gè)MEC 服務(wù)器只能部署SFC 中的部分網(wǎng)絡(luò)功能。如何協(xié)同利用受限的MEC 服務(wù)器資源，進(jìn)行虛擬網(wǎng)絡(luò)功能的有序部署，對(duì)SFC 部署算法帶來(lái)設(shè)計(jì)上的挑戰(zhàn)。

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

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

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

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

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

1) 面向內(nèi)容提供服務(wù)，建立邊緣網(wǎng)絡(luò)中聯(lián)合無(wú)線多播的SFC 部署模型。最大化系統(tǒng)中數(shù)據(jù)流開(kāi)銷和功耗開(kāi)銷，并滿足鏈路帶寬約束、處理容量約束、吞吐量需求約束、SFC 部署序列約束、波束向量與信號(hào)處理功能的耦合約束，以及最大發(fā)射功率約束。綜合考慮數(shù)據(jù)流、服務(wù)器功能維護(hù)功耗、服務(wù)器功能服務(wù)功耗和無(wú)線傳輸功耗這4 種系統(tǒng)開(kāi)銷，建立波束成形設(shè)計(jì)和SFC 部署的聯(lián)合優(yōu)化問(wèn)題。該問(wèn)題是一個(gè)NP（non-deterministic polynomial）難問(wèn)題，很難找到多項(xiàng)式時(shí)間求解算法。

2) 利用拉格朗日對(duì)偶分解技術(shù)，將原優(yōu)化問(wèn)題轉(zhuǎn)化為2 個(gè)獨(dú)立子問(wèn)題。利用基于Lp范數(shù)懲罰項(xiàng)的連續(xù)凸近似算法，將ILP 項(xiàng)式的SFC 部署問(wèn)題松弛為一個(gè)線性規(guī)劃（LP,linear programming）問(wèn)題，并給出了原問(wèn)題和松弛問(wèn)題的最優(yōu)解等價(jià)性證明；利用路徑跟隨技術(shù)，將非凸波束向量?jī)?yōu)化問(wèn)題轉(zhuǎn)化為一系列凸子問(wèn)題，并給出了算法的單調(diào)性分析。

3) 仿真結(jié)果表明，本文算法具有良好收斂性能。將本文算法與最優(yōu)單播SFC 部署算法和隨機(jī)多播SFC 部署算法進(jìn)行對(duì)比，驗(yàn)證了本文算法的有效性。

2 系統(tǒng)模型

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

圖1 多基站部署的邊緣網(wǎng)絡(luò)

2.1 SFC 模型和容量約束

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

2.2 多播模型

與協(xié)同多點(diǎn)傳輸（CoMP,coordinated multiple-point transmission）[15-20]技術(shù)不同，本文假設(shè)每個(gè)基站在自己的天線組內(nèi)獨(dú)立進(jìn)行多播波束成形，對(duì)每個(gè)基站分配正交的頻譜資源，從而有效消除了小區(qū)間干擾?；趩翁炀€CoMP 技術(shù)，文獻(xiàn)[18-19]提出了宏分集協(xié)同多點(diǎn)傳輸（MD-CoMP,macro diversity coordinated multi-point transmission）概念，將小區(qū)頻率復(fù)用因子設(shè)為1，通過(guò)對(duì)同小區(qū)用戶分配正交頻譜資源，以消除小區(qū)內(nèi)干擾。因此，用戶所受干擾為來(lái)自其他基站簇的小區(qū)間干擾。本文沒(méi)有考慮基站之間的CoMP，這是因?yàn)?，若考慮CoMP，則每個(gè)用戶將選擇多個(gè)接入基站，本文考慮的單服務(wù)路徑規(guī)劃問(wèn)題將成為一個(gè)多服務(wù)路徑規(guī)劃問(wèn)題，進(jìn)一步增大優(yōu)化問(wèn)題的求解難度。定義每個(gè)基站的無(wú)線頻譜帶寬為B，則用戶k從基站n處得到的接收信號(hào)信干噪比（SINR,signal to interference plus noise ratio）Γk,n為

2.3 問(wèn)題描述

一方面，為最小化SFC 路徑中的數(shù)據(jù)流開(kāi)銷，每條SFC 的功能應(yīng)集中部署在盡可能少的MEC 服務(wù)器中，然而受限于MEC 服務(wù)器的處理容量，同一SFC 的不同功能往往部署到不同的基站，這將不可避免地增大數(shù)據(jù)流開(kāi)銷。另一方面，不僅基站的發(fā)送天線帶來(lái)無(wú)線傳輸功耗開(kāi)銷，MEC 服務(wù)器的功能維護(hù)和功能服務(wù)也將導(dǎo)致服務(wù)器功耗開(kāi)銷。系統(tǒng)開(kāi)銷應(yīng)綜合考慮數(shù)據(jù)流開(kāi)銷和功耗開(kāi)銷。因此，可將系統(tǒng)總開(kāi)銷C定義為

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

為最小化SFC 部署的系統(tǒng)開(kāi)銷，節(jié)省邊緣網(wǎng)絡(luò)資源，將優(yōu)化問(wèn)題 P0描述如下。

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

1) 基站之間的SFC 部署將決定用戶的接入基站選取。邊緣網(wǎng)絡(luò)的SFC 部署將規(guī)劃邊緣網(wǎng)絡(luò)到用戶的端到端服務(wù)路徑，從而為每個(gè)用戶選取一個(gè)接入基站，以無(wú)線傳輸方式完成數(shù)據(jù)流到用戶的最后一跳。若只優(yōu)化基站之間的SFC 部署開(kāi)銷，不考慮用戶的接入基站選取，將導(dǎo)致無(wú)線傳輸功耗開(kāi)銷過(guò)高。

2) 用戶的接入基站選取將影響基站之間的SFC 部署。作為SFC 部署的最后一個(gè)服務(wù)節(jié)點(diǎn)，用戶的接入基站將數(shù)據(jù)流經(jīng)無(wú)線空口傳輸?shù)接脩?。同時(shí)，接入基站的位置將影響上一個(gè)服務(wù)基站的選取，從而依次逆序影響其他所有服務(wù)基站的選取。因此，若只考慮波束成形算法的無(wú)線傳輸功耗，不考慮用戶的接入基站選取，將導(dǎo)致基站之間SFC 部署開(kāi)銷過(guò)高。

因此，無(wú)線傳輸?shù)牟ㄊ尚魏突局g的SFC部署存在折中關(guān)系，需聯(lián)合優(yōu)化。

3 算法設(shè)計(jì)

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

3.1 拉格朗日對(duì)偶分解

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

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

3.2 基于懲罰項(xiàng)的SFC 部署算法

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

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

然后，根據(jù)Lp范數(shù)的上述性質(zhì)，將一個(gè)基于Lp范數(shù)的懲罰項(xiàng)Pε(y)疊加到 P2的目標(biāo)函數(shù)，并將變量松弛。則 P2可轉(zhuǎn)化為

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

3.4 計(jì)算復(fù)雜度分析

4 仿真分析

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

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

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

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

圖2 基于懲罰項(xiàng)的SFC 部署算法的收斂性能

圖3 給出了不同折中系數(shù)η下的基于路徑跟隨的波束成形算法的收斂性能。設(shè)用戶數(shù)為20，且等概率請(qǐng)求一項(xiàng)內(nèi)容服務(wù)，每項(xiàng)服務(wù)的SFC 均包含4 項(xiàng)有序功能。因?yàn)樵摬糠炙惴▋H涉及了基站的波束成形設(shè)計(jì)，所以使用無(wú)線傳輸功耗作為性能指標(biāo)。由圖3 可看出，在不同η設(shè)置下，本文算法均在迭代15 次之內(nèi)收斂，且功耗值單調(diào)遞減。這也驗(yàn)證了3.3 節(jié)有關(guān)算法單調(diào)性分析的正確性。

圖4 給出了不同折中系數(shù)η下的次梯度方法的收斂性能。用戶數(shù)和SFC 的設(shè)置均與圖2 和圖3 一致。為公平衡量算法性能，克服η過(guò)大或過(guò)小對(duì)問(wèn)題 P0的優(yōu)化目標(biāo)的影響，僅使用系統(tǒng)功耗開(kāi)銷作為性能指標(biāo)。首先，由圖4 可知，盡管次梯度方法相較于基于懲罰項(xiàng)的SFC 部署算法和基于路徑跟隨的波束成形算法的收斂性能較差，但均在迭代30次左右趨于穩(wěn)定值。其次，與圖3 相比，系統(tǒng)總功耗開(kāi)銷和無(wú)線傳輸功耗開(kāi)銷之間的差值表現(xiàn)為功能維護(hù)功耗開(kāi)銷和功能服務(wù)功耗開(kāi)銷。最后，隨著η的增大，系統(tǒng)總功耗開(kāi)銷逐漸降低。這是因?yàn)樵純?yōu)化問(wèn)題 P0的優(yōu)化目標(biāo)為最小化系統(tǒng)開(kāi)銷，η的增大將使功耗開(kāi)銷的權(quán)重增大，數(shù)據(jù)流開(kāi)銷的權(quán)重減小，從而使最優(yōu)值中的功耗部分降低。

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

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

圖5 給出了不同折中系數(shù)η下算法1 功耗開(kāi)銷?數(shù)據(jù)流開(kāi)銷折中曲線。與圖4 結(jié)論類似，當(dāng)η=106時(shí)，可認(rèn)為η趨近于無(wú)窮大，系統(tǒng)開(kāi)銷只考慮功耗開(kāi)銷，P0簡(jiǎn)化為功耗開(kāi)銷最小化問(wèn)題，而算法1 成為功耗開(kāi)銷最小化算法。因此，優(yōu)化目標(biāo)中不考慮數(shù)據(jù)流開(kāi)銷，η=106時(shí)數(shù)據(jù)流開(kāi)銷超過(guò)了60 Mbit/s。在η=10?6時(shí)，可認(rèn)為η趨近于無(wú)窮小，系統(tǒng)開(kāi)銷只考慮數(shù)據(jù)流開(kāi)銷，P0簡(jiǎn)化為數(shù)據(jù)流最小化問(wèn)題，優(yōu)化目標(biāo)中不涉及功耗開(kāi)銷，故η=10?6時(shí)功耗開(kāi)銷達(dá)到105 W。圖4 和圖5 的結(jié)論為合理、靈活選擇折中系數(shù)η提供了理論依據(jù)和經(jīng)驗(yàn)參考。

圖5 算法1 的功耗開(kāi)銷?數(shù)據(jù)流開(kāi)銷折中曲線

圖6 給出了本文算法和比較算法在不同用戶數(shù)下的系統(tǒng)總功耗性能。SFC 的設(shè)置均與圖2～圖4一致，η=103。由圖6 可看出，本文算法性能優(yōu)于最優(yōu)單播SFC 部署算法。這是因?yàn)?，若為每個(gè)用戶獨(dú)立分配一個(gè)波束向量，將顯著增大基站的無(wú)線傳輸功耗，使系統(tǒng)總功耗提升。同時(shí)，在只考慮系統(tǒng)功耗開(kāi)銷時(shí)，隨機(jī)多播SFC 部署算法的性能優(yōu)于本文算法。這是因?yàn)?，?103時(shí)本文算法需折中考慮功耗開(kāi)銷和數(shù)據(jù)流開(kāi)銷，最優(yōu)值中的數(shù)據(jù)流開(kāi)銷部分將導(dǎo)致功耗開(kāi)銷部分增大；而隨機(jī)多播SFC 部署算法不需要考慮數(shù)據(jù)流開(kāi)銷。

圖6 系統(tǒng)總功耗與用戶數(shù)之間關(guān)系

圖7 給出了本文算法和比較算法在不同用戶數(shù)下的數(shù)據(jù)流開(kāi)銷性能。SFC 的設(shè)置均與圖2～圖4一致，η=103。如圖7 所示，曲線呈分段線性的折線形式，這是因?yàn)?，?shù)據(jù)流開(kāi)銷需取U-vMOS 吞吐量需求的整數(shù)倍，無(wú)法像功率分配一樣取任意連續(xù)值。在只考慮系統(tǒng)數(shù)據(jù)流開(kāi)銷時(shí)，最優(yōu)單播SFC 部署算法的性能優(yōu)于本文算法。這是因?yàn)?，?103時(shí)本文算法需折中考慮功耗開(kāi)銷和數(shù)據(jù)流開(kāi)銷，最優(yōu)值中的功耗開(kāi)銷部分同樣會(huì)導(dǎo)致數(shù)據(jù)流開(kāi)銷部分的增大；而最優(yōu)單播SFC 部署算法不需要考慮功耗開(kāi)銷。

圖7 系統(tǒng)數(shù)據(jù)流開(kāi)銷與用戶數(shù)之間關(guān)系

5 結(jié)束語(yǔ)

本文提出了一種面向內(nèi)容的聯(lián)合無(wú)線多播的SFC 部署算法，建立了波束成形設(shè)計(jì)和SFC 映射的聯(lián)合優(yōu)化模型。利用拉格朗日對(duì)偶分解技術(shù)，將優(yōu)化問(wèn)題轉(zhuǎn)化為SFC 部署和波束成形設(shè)計(jì)2 個(gè)獨(dú)立子問(wèn)題；利用基于Lp范數(shù)懲罰項(xiàng)的連續(xù)凸近似算法，將整數(shù)形式的SFC 部署問(wèn)題松弛為一個(gè)等價(jià)線性規(guī)劃問(wèn)題，并給出了最優(yōu)解的等價(jià)性證明；利用路徑跟隨技術(shù)，將非凸波束向量?jī)?yōu)化問(wèn)題轉(zhuǎn)化為一系列凸優(yōu)化問(wèn)題，并給出了算法單調(diào)性分析。仿真結(jié)果表明，所提算法在系統(tǒng)開(kāi)銷方面優(yōu)于最優(yōu)單播SFC 部署算法和隨機(jī)多播SFC 部署算法。未來(lái)工作中，將進(jìn)一步研究聯(lián)合協(xié)作多播波束成形的多服務(wù)路徑SFC 部署問(wèn)題。

附錄 定理1 證明