Loading [MathJax]/jax/element/mml/optable/GeneralPunctuation.js
高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

基于深度Q网络的在线服务功能链部署方法

邱航 汤红波 游伟

王建新, 于贵智. Viterbi译码器回溯算法实现研究[J]. 电子与信息学报, 2007, 29(2): 278-282. doi: 10.3724/SP.J.1146.2005.00614
引用本文: 邱航, 汤红波, 游伟. 基于深度Q网络的在线服务功能链部署方法[J]. 电子与信息学报, 2021, 43(11): 3122-3130. doi: 10.11999/JEIT201009
Wang Jian-xin, Yu Gui-zhi. Study on Implementation of Traceback Algorithm in Viterbi Decoders[J]. Journal of Electronics & Information Technology, 2007, 29(2): 278-282. doi: 10.3724/SP.J.1146.2005.00614
Citation: Hang QIU, Hongbo TANG, Wei YOU. Online Service Function Chain Deployment Method Based on Deep Q Network[J]. Journal of Electronics & Information Technology, 2021, 43(11): 3122-3130. doi: 10.11999/JEIT201009

基于深度Q网络的在线服务功能链部署方法

doi: 10.11999/JEIT201009
基金项目: 国家自然科学基金(61801515, 61941114, 61521003)
详细信息
    作者简介:

    邱航:男,1994年生,博士生,主要研究方向为新一代移动通信网络技术、移动通信网络安全

    汤红波:男,1968年生,教授、博士生导师,主要研究方向为移动通信网络、新型网络体系结构

    游伟:男,1984年生,博士,讲师,主要研究方向为移动通信网络安全、新一代移动通信网络技术

    通讯作者:

    汤红波 hangsoon@foxmail.com

  • 中图分类号: TN915.07

Online Service Function Chain Deployment Method Based on Deep Q Network

Funds: The National Natural Science Foundation of China (61801515, 61941114, 61521003)
  • 摘要: 针对5G网络资源状态动态变化和网络模型高维度下服务功能链部署的复杂性问题,该文提出一种基于深度Q网络的在线服务功能链部署方法(DeePSCD)。首先,为描述网络资源动态变化的特征,将服务功能链部署建模成马尔可夫决策过程,然后,针对系统资源模型的高维度问题采用深度Q网络的方法进行在线服务功能链部署策略求解。该方法可以有效描述网络资源状态的动态变化,特别是深度Q网络能有效克服求解复杂度,优化服务功能链的部署开销。仿真结果表明,所提方法在满足服务时延约束条件下降低了服务功能链的部署开销,提高了运营商网络的服务请求接受率。
  • 超导材料的发展推动了智能超表面(Reconfigurable Intelligent Surface, RIS)的研究,在大量廉价天线的帮助下,可以有效地重新配置无线通信环境。作为一种新范式,RIS为未来无线通信带来了一些潜在的好处,如覆盖范围的增强、数据速率的增加和谱效/能效的提升[1-5]。移动边缘计算(Mobile Edge Computing, MEC)具有更接近网络边缘的分布式计算优势,可以显著地提高用户计算体验质量,填补了集中式远端云和终端用户之间的鸿沟[6]。RIS和MEC是近年来富有前景的两种新技术,它们通过重新配置无线传播环境和任务卸载来提高通信和计算能力[7],受到了学术界和工业界的广泛重视。因此,RIS协同MEC正成为有效兼顾计算和通信双重效益的一个热点话题。

    目前关于RIS的研究已取得了许多有价值的研究成果。譬如,文献[8]通过联合优化基站发射功率、RIS相移以及保证用户服务质量,提出了一种系统能效最大化资源分配算法。文献[9]考虑了用户安全速率约束,提出了一种安全通信下的系统能效最大化资源分配算法。文献[10]将多个RIS引进无线网络中,提出了一种基于多个RIS的能效最大化资源分配算法。文献[11]将多个RIS引入安全通信网络中,提出了一种最大化用户速率的资源分配算法。

    在RIS协同MEC框架中,RIS可以增强覆盖和通信能力,MEC可以扩展计算的深度和维度进行数据处理。未来,RIS在MEC系统中的实际应用可以在芯片技术发展基础上,实现功能可重构。然而将RIS应用到MEC系统中有一些技术挑战需要解决,如何联合调度MEC服务器与RIS实现互利共赢?如何通过对RIS反射元的重新配置来提高MEC服务器的性能?因此,通过协同RIS和MEC来进一步提高系统的数据速率、降低时延以及系统能耗是非常重要的。最近,文献[12]为了解决任务卸载速率低的问题,将RIS引入MEC系统中,通过联合优化任务卸载量、边缘服务器的计算资源以及RIS相移实现时延最小化。在能耗和时延约束下,文献[13]研究了用户最大卸载量的问题。文献[14]在保证用户服务质量及用户功率约束下,提出了一种能效最大化的资源分配算法。文献[15]联合优化了任务卸载量、边缘服务器的计算资源、用户发射功率以及RIS相移,提出了一种能耗最小化资源分配算法。文献[16]考虑了用户安全卸载速率约束,提出了一种安全卸载速率下的能耗最小化的资源分配算法。文献[17]考虑了多RIS辅助的联邦学习系统,联合优化了用户发射功率和RIS相移,提出了一种最小化最小均方误差的资源分配算法。文献[18]考虑了RIS辅助的边缘智能系统,通过联合优化用户发射功率、任务卸载量和RIS相移,提出了一种最小化训练误差的资源分配算法。

    上述工作中,大部分考虑了单个RIS辅助无线网络的情况,也有一些工作考虑了多个RIS辅助无线网络的情况。但是,在多个RIS辅助无线网络工作中,由于RIS彼此之间假设不存在反射链路,所以多个RIS之间彼此独立,故多RIS之间仍旧可以当作单个RIS处理。因此,上述工作并没有考虑RIS之间的协作关系。基于此,文献[19]考虑了两个RIS之间的协作关系,并证明了其产生的链路增益远优于部署单个RIS的情况。文献[20]在文献[19]的基础上,分别从信噪比和信干噪比两个角度研究了两个RIS协作下对系统的影响。上述两项工作为研究RIS赋能MEC系统能耗优化问题提供了有价值的指导。为此,本文提出了一种双RIS协作下的MEC系统,如何有效地进行计算任务的卸载是需要解决的关键问题。其主要贡献如下:

    (1) 本文将两个RIS之间的协作引入MEC系统中,并在部分卸载的基础上,联合优化终端用户的发射功率、终端用户的卸载速率、任务卸载量、卸载时间的分配以及RIS相移,构建一个非线性、多变量耦合的能耗最小化问题。

    (2) 为了求解该非凸优化问题,本文采用交替迭代算法,将原非凸问题分解为两个子问题,并利用Dinkelbach方法和最优性条件进行求解。最后,提出一种基于迭代的能耗最小化资源分配算法。

    (3) 仿真结果表明,本文算法具有快速收敛特性以及在降低系统能耗方面的有效性。

    考虑如图1所示的双RIS协同MEC系统,该系统包括1个N根天线并搭载MEC计算服务器的基站,K个单天线用户,在用户端部署1个含有M1个反射元的RIS 1,在基站端部署1个含有M2个反射单元的RIS 2。假设所有信道的信道状态在基站处是完全已知的,用户与基站由于障碍物的遮挡无法进行直接通信,由于电磁波在传播中的损耗,本文不考虑从用户到RIS 2反射RIS 1再到基站端链路的情况。K个用户通过时分多址接入(Time Division Multiple Access, TDMA)的方式以及只通过RIS辅助的反射链路卸载计算密集型任务到边缘服务器。为了方便分析,用户、RIS和反射单元集合分别定义为kK{1,2,,K}miMi{1,2,,Mi}iI{1,2}wkCN×1表示用户k到基站的接收波束成形矢量,pk表示用户k的发射功率。记任务卸载周期为T,用户k卸载任务的时间为tk且满足Kk=1tkT。用u1,kCM1×1u2,kCM2×1DkCM2×M1G1CN×M1G2CN×M2分别为用户k到RIS 1,用户k到RIS 2,RIS 1到RIS 2,RIS 1到基站,RIS 2到基站的信道增益。Θkidiag(ejθki,1,ejθki,2,,ejθki,Mi)表示RISi的相移矩阵,其中θki,mi[0,2π)代表RISi上第mi个反射单元的相移。记vki,mi=ejθki,mi,则|vki,mi|=1。根据上述分析,用户k到基站的信道增益可表示为

    图 1  系统模型图
    hk=G2Θk2DkΘk1u1,k+G2Θk2u2,k+G1Θk1u1,k=G2Θk2DkΘk1u1,k+H2,kvk2+H1,kvk1 (1)

    其中,H2,k=G2diag(u2,k)为用户k通过RIS 2到基站的信道增益(不包括RIS 2的相移),H1,k=G1diag(u1,k)为用户k通过RIS 1到基站的信道增益(不包括RIS 1的相移)。定义˜Dk[˜dk,1,˜dk,2,,˜dk,M1]=Dkdiag(u1,k),式(1)可以进一步写为如下形式

    hk=G2Θk2˜Dkvk1+H2,kvk2+H1,kvk1=G2[Θk2˜dk,1,Θk2˜dk,2,,Θk2˜dk,M1]vk1+H2,kvk2+H1,kvk1=G2[diag(˜dk,1)vk2,diag(˜dk,2)vk2,,diag(˜dk,M1)vk2]vk1+H2,kvk2+H1,kvk1=M1m=1G2diag(˜dk,m)vk2vk1,m+H2,kvk2+H1,kvk1 (2)

    其中,Qk,m=G2diag(˜dk,m)为用户k通过RIS 1反射到RIS 2,然后到基站的信道增益(不包括RIS 1和RIS 2的相移)。

    在上行链路数据传输期间,基站处的接收信号为yk=hksk+nk,其中,nkCN(0,σ2kI)为高斯加性白噪声。在接收yk时,基站采用线性接收波束成形矢量wk,得到式子˜yk=wHkhksk+wHknk

    根据香农定理,用户k的卸载速率为

    Rk=Blog2(1+pk|wHkhk|2σ2kwHkwk), (3)

    其中,B为系统带宽。

    由于用户的计算能力和电池容量有限,需要将部分任务卸载到MEC服务器上进行处理。假设用户k的任务总数为Lk,并且可以任意划分为两个独立的任务。所有用户都采用部分卸载策略,即用户k将会把任务总数Lk分成两部分,一部分比特数lk在用户k本地进行计算,剩余比特数(Lklk)卸载至MEC服务器上进行计算。通常MEC服务器有强大的计算能力,计算结果的数据往往较小,因此本文忽略了MEC服务器计算卸载任务的时延和计算结果回传给终端用户的时延。假设本地计算将采用动态电压缩放(Dynamic Voltage Scaling, DVS)模型,使用DVS技术,用户可以自适应地调整其计算速度,以减少能耗或缩短计算时延[21]。定义ck为用户k的CPU计算每比特数所需的周期数,κ为用户的有效电容系数,取决于其处理器芯片的结构。因此,用户k本地计算的能耗可以表示为Elk=κc3kl3kT2,用户k到MEC服务器的卸载能耗可以表示为Eok=pktk。故用户k的总能耗为Ek=Elk+Eok

    在本文中,通过联合优化每个用户发射功率、用户间的卸载时间分配、用户的本地任务计算量、RIS无源波束成形以及基站端接收波束成形设计,以便用户的总能耗最小化。具体优化问题建模为

    minW,p,t,V1,V2,lKk=1Eks.t.C1:RkLklktk,kK,C2: 0pkPmaxk,kK,C3: 0tkTk,kK,C4: 0lklmaxk,kK,C5: |vki,mi|=1,kK,iI,miMi,} (4)

    其中,W=[w1,w2,,wK]p=[p1,p2,,pK]t=[t1,t2,,tK]V1=[v11,v21,,vK1]V2=[v12,v22,,vK2]l=[l1,l2,,lK]Pmaxk表示用户k的最大发射功率,lmaxk表示用户k最大本地任务量。限制条件C1确保在tk时间内部分任务卸载,限制条件C2表示发射功率约束,限制条件C3表示任务卸载时间约束,限制条件C4表示本地的任务量,限制条件C5表示RIS的单位模约束。由于目标函数的非线性和约束条件的非凸性,问题式(4)是一个多变量耦合的非凸优化问题,很难直接求得最优解。

    由于所有终端用户在每个时隙内是相互独立的,所以本文只分析用户k的能量消耗。该分析方案可以拓展到多个用户,因此问题式(4)可以简化为问题式(5):

    minwk,pk,tk,vk1,vk2,lkEks.t.C6:RkLklktk,C7: 0pkPmaxk,C8: 0tkTK,C9: 0lklmaxk,C10: |vki,mi|=1,iI,miMi.} (5)

    根据问题式(5)可知,当终端用户k卸载时间满足tk=(Lklk)/Rk时,终端用户的总能耗最小。因此问题式(5)可等价式(6)问题:

    minwk,pk,vk1,vk2,lkκc3kl3kT2+pkLklkRks.t.C9:0lklmaxk,C10: |vki,mi|=1,iI,miMi,C11:pminkpkPmaxk,} (6)

    其中,pmink=(2K(Lklk)(BT)11)a1kak=|wHk(M1m=1Qk,mvk2vk1,m+H2,kvk2+H1,kvk1)|2/(σ2kwHkwk)。通过关系式(Lklk)/RkT/K,可以得到约束条件C11中的pminkpk

    由于上述问题是一个变量高度耦合的非凸问题,无法直接进行求解。为了有效求解该问题,将问题式(6)分解为两个子问题,然后提出了一种交替优化算法。具体地,根据RIS相移和波束成形及用户的发射功率和本地任务量,将问题式(6)划分为两个子问题。其次,在给定用户发射功率和本地任务量的情形下,优化RIS相移和波束成形矢量;然后在给定已获得的RIS相移和波束成形矢量情况下,优化用户发射功率和本地任务量。

    通过固定发射功率和本地任务量,优化RIS无源波束成形矢量vk1vk2和基站端接收波束成形矢量wk。去掉目标函数和约束条件中与相移矩阵和波束成形矢量无关的部分。因此,优化RIS无源波束成形矢量vk1vk2和基站端接收波束成形矢量wk的子问题可表示为

    maxwk,vk1,vk2|wHk(M1m=1Qk,mvk2vk1,m+H2,kvk2+H1,kvk1)|2s.t.C9:|vki,mi|=1,iI,miMi, (7)

    上述问题是一个非凸问题,很难直接求出最优解。固定变量vk1wk,问题式(7)的目标函数转换为

    |wHk(M1m=1Qk,mvk2vk1,m+H2,kvk2+H1,kvk1)|2=|wHk(M1m=1vk1,mQk,m+H2,k)vk2+wHkH1,kvk1|2. (8)

    此外,式(8)有如下不等式:

    |wHk(M1m=1vk1,mQk,m+H2,k)vk2+wHkH1,kvk1||wHk(M1m=1vk1,mQk,m+H2,k)vk2|+|wHkH1,kvk1| (9)

    bHk=wHk(M1m=1vk1,mQk,m+H2,k)bk0=wHkH1,kvk1。根据三角不等式,式(9)成立,当且仅当(bHkvk2)=(bk0)取等号。根据式(9)并且固定vk1wk,问题式(7)等价于:

    maxvk2|bHkvk2|2s.t.ˆC9:|vk2,m2|=1,m2M2lC12:(bHkvk2)=(bk0)} (10)

    于是,问题式(10)的最优解可为

    (vk2)=ej((bk0)(bk)) (11)

    接下来固定vk2wk,优化vk1,问题式(7)可重构为如下形式

    |wHk(M1m=1Qk,mvk2vk1,m+H2,kvk2+H1,kvk1)|2=|wHk(ˉQk+H1,k)vk1+wHkH2,kvk2|2 (12)

    其中,ˉQk[Qk,1vk2,Qk,2vk2,,Qk,M1vk2]。重复上述处理过程,vk1的最优解为

    (vk1)=ej((sk0)(sk)) (13)

    其中,sHwHk(ˉQk+H1,k)s0wHkH2,kvk2

    最终,给定vk1vk2后,采用合并最大比准则,最佳接收波束成形的表述形式为[20]

    wk=M1m=1Qk,mvk2vk1,m+H2,kvk2+H1,kvk1 (14)

    给定波束成形矢量和相移矩阵,优化发射功率和本地任务量。首先固定本地任务量,优化发射功率。优化问题表示为

    \left.\begin{gathered} \mathop {\min }\limits_{{p_k}} \;\;\frac{{{L_k} - {l_k}}}{B}\frac{{{p_k}}}{{{{\log }_2}\left( {1 + {p_k}{a_k}} \right)}} \\ {\text{s}}{\text{.t}}{\text{.}}\;\;{\text{C11:}}\;\;p_k^{\min } \le {p_k} \le P_k^{\max } \end{gathered}\right\} (15)

    基于上述问题的非凸性,本文使用Dinkelbach方法[16]改变目标函数的分式结构,通过引入松弛变量\eta ,问题式(15)重构为

    \left.\begin{split} &\mathop {\min }\limits_{{p_k}} \;\;\frac{{{L_k} - {l_k}}}{B}\left( {{p_k}\eta - {{\log }_2}\left( {1 + {p_k}{a_k}} \right)} \right) \\ &{\text{s}}{\text{.t}}{\text{.}}\;\;{\text{C11:}}\;\;p_k^{\min } \le {p_k} \le P_k^{\max } \end{split}\right\} (16)

    其中,\eta = p_k^{ - 1}{\log _2}\left( {1 + {p_k}{a_k}} \right)。对于固定\eta ,定理1给出了问题的最优解。

    定理1 固定\eta ,最优发射功率p_k^*的值为

    p_k^* = \left\{ \begin{aligned} & {{p'}_k},\quad \;p_k^{\min } < {{p'}_k} < P_k^{\max } \\ & p_k^{\min },\;\;\, p_k^{\min } \ge {{p'}_k} \\ & P_k^{\max },\;\;p_k^{\max } \le {{p'}_k} \\ \end{aligned} \right. (17)

    其中,p_k^{\min } = ({2^{K({L_k} - {l_k}){{(BT)}^{ - 1}}}} - 1)a_k^{ - 1}为最小发射功率,{p'_k} = ({a_k}{\log _2}e - \eta ){(\eta {a_k})^{ - 1}}为目标函数极值。

    证明 令{F_1} = ({L_k} - {l_k}){B^{ - 1}}\left( {p_k}\eta - {{\log }_2}\left( 1 + {p_k} {a_k} \right) \right),该函数为两个凸函数的求和,因此{F_1}为凸函数。根据最优性条件求解该问题,即

    \frac{{\partial {F_1}}}{{\partial {p_k}}} = \eta - \frac{{{a_k}}}{{\left( {1 + {p_k}{a_k}} \right)\ln 2}} = 0, (18)

    解得{p'_k} = ({a_k}{\log _2}e - \eta ){(\eta {a_k})^{ - 1}}。函数{F_1}\left( {0,{{p'}_k}} \right)单调递减,在\left( {{{p'}_k}, + \infty } \right)单调递增,因此{p'_k}为极小值。当 p_k^{\min } < {p'_k} < P_k^{\max } 时, p_k^* = {p'_k} ;当p_k^{\min } \;\ge\; {p'_k}时,p_k^* \;=\; p_k^{\min };当P_k^{\max } \;\le\; {p'_k}时, p_k^* = P_k^{\max } 。 证毕

    固定发射功率,优化本地任务量。基于式(18),可以得到l_k^*。情况1:当p_k^* = p'p_k^* = P_k^{\max }时,p_k^*表达式与{l_k}无关,将p_k^*代入目标函数中得到优化问题。情况2:当p_k^* = p_k^{\min }时,p_k^*表达式和{l_k}相关,将p_k^*代入目标函数中得到优化问题。下面将分两种情况进行讨论。

    情况1:当p_k^* = p'p_k^* = P_k^{\max }时,优化问题为

    \left.\begin{split} & \mathop {\min }\limits_{{l_k}} \;\;\frac{{\kappa c_k^3l_k^3}}{{{T^2}}} + {p_k}\frac{{{L_k} - {l_k}}}{{{R_k}}} \\ &\;{\text{s}}{\text{.t}}{\text{.}}\;\;{\text{C9:}}\;\;0 \le {l_k} \le l_k^{\max }, \end{split} \right\} (19)

    根据最优性条件可知,{l_k} = \sqrt {{p_k}{T^2}{{(3{R_k}\kappa c_k^3)}^{ - 1}}} 。所以,最优解为l_k^* = \min \left( {{l_k},l_k^{\max }} \right)

    情况2:当p_k^* = p_k^{\min }时,优化问题为

    \left. \begin{split} &\mathop {\min }\limits_{{l_k}} \;\;\frac{{\kappa c_k^3l_k^3}}{{{T^2}}} + \frac{T}{K}\frac{{{2^{\frac{{K\left( {{L_k} - {l_k}} \right)}}{{BT}}}} - 1}}{{{a_k}}} \\ &\;{\text{s}}{\text{.t}}{\text{.}}\;\;{\text{C9:}}\;\;0 \le {l_k} \le l_k^{\max } \end{split}\right\} (20)

    {F_2} = \kappa c_k^3l_k^3{T^{ - 2}} + T{(K{a_k})^{ - 1}}({2^{K({L_k} - {l_k}){{(BT)}^{ - 1}}}} - 1),由于目标函数是两个凸函数的和,因此问题式(20)是凸优化问题。其最优解由式(21)给出

    \frac{{\partial {F_2}}}{{\partial {l_k}}} = \frac{{3\kappa c_k^3l_k^2}}{{{T^2}}} - \frac{1}{{{a_k}B}}{2^{\frac{{K\left( {{L_k} - {l_k}} \right)}}{{BT}}}} = 0, (21)

    上述方程的目标函数是个凸函数,故式(21)关于 {l_k} 单调。本文采取二分法求其数值解{l_0},并记其最优解为l_k^* = \min \left( {{l_0},l_k^{\max }} \right)

    定理2 如果p_k^* = p'p_k^* = P_k^{\max },则l_k^* = \min \left( {\sqrt {{p_k}{T^2}{{(3{R_k}\kappa c_k^3)}^{ - 1}}} ,l_k^{\max }} \right);当p_k^* = p_k^{\min }时,l_k^* = \min \left( {{l_0},l_k^{\max }} \right),其中{l_0}由二分法得到。证明略。

    本文提出的交替优化算法具体步骤如表1所示。

    表 1  交替优化算法(算法1)
     输入:初始化\left( {{\mathbf{v}}_1^k,{\mathbf{v}}_2^k,{{\mathbf{w}}_k},{p_k},{l_k},{t_k}} \right)
     步骤1:for i = 1:{I_0}
        根据(11)计算{\mathbf{v}}_2^k
        根据(13)计算{\mathbf{v}}_1^k
        根据(14)计算{{\mathbf{w}}_k}
     步骤2:for i = 1:{I_1}
        根据式(17)计算{p_k}
        根据定理2计算{l_k}
        更新{\eta ^{(i)}} = {\log _2}\left( {1 + p_k^{(i)}{a_k}} \right)/p_k^{(i)}
        更新t_k^{(i)} = ({L_k} - l_k^{(i)})/R_k^{(i)}
     步骤3:输出\left( {{\mathbf{v}}_1^k,{\mathbf{v}}_2^k,{{\mathbf{w}}_k},{p_k},{l_k},{t_k}} \right)
    下载: 导出CSV 
    | 显示表格

    复杂度分析:在算法1中,步骤1的时间复杂度由文献[20]可知为\mathcal{O}\left( {{I_0}\left( {N + M} \right)} \right),步骤2的时间复杂度由计算发射功率 \mathcal{O}\left( {{I_1}} \right) 和本地任务量 \mathcal{O}\left( {{I_1} \times \max \left( {1,{{\log }_2}(1/\varepsilon )} \right)} \right) 组成,因此步骤2的时间复杂度为 \mathcal{O}\left( {{I_1} + {I_1} \times \max \left( {1,{{\log }_2}(1/\varepsilon )} \right)} \right) 。综上,算法1的总时间复杂度为\mathcal{O}\left( {I_0}\left( {N + M} \right) + {I_1} + {I_1} \times \max \left( {1,{{\log }_2}(1/\varepsilon )} \right) \right),其中{I_0}{I_1}是算法的迭代次数,\varepsilon 为二分法解的精度。

    收敛性分析:假设{E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^k,{\boldsymbol{v}}_2^k,{{\boldsymbol{w}}_k},{p_k},{l_k}} \right)表示问题式(6)的目标函数值,由于步骤1和步骤2独立,因此,本文分别分析步骤1和步骤2的收敛性,最终给出整体算法的收敛性。在步骤1,第i次迭代有

    \begin{split} &{E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^{k,i},{\boldsymbol{v}}_2^{k,i},{\boldsymbol{w}}_k^i,{p_k},{l_k},{t_k}} \right)\\ & \quad\mathop \ge \limits^{\left( {\rm{a}} \right)} {E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^{k,i},{\boldsymbol{v}}_2^{k,i + 1},{\boldsymbol{w}}_k^i,{p_k},{l_k},{t_k}} \right) \\ & \quad\mathop \ge \limits^{\left( {\rm{b}} \right)} {E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^{k,i + 1},{\boldsymbol{v}}_2^{k,i + 1},{\boldsymbol{w}}_k^i,{p_k},{l_k},{t_k}} \right)\\ & \quad\mathop \ge \limits^{\left( {\rm{c}} \right)} {E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^{k,i + 1},{\boldsymbol{v}}_2^{k,i + 1},{\boldsymbol{w}}_k^{i + 1},{p_k},{l_k},{t_k}} \right) \end{split} (22)

    其中,不等式(a),(b)和(c)成立的条件在于每个子问题都可获得最优解,从而确保目标函数值在迭代过程中单调非增。又因为优化变量存有下界,因此步骤1收敛。

    在步骤2中,第j次迭代有

    \begin{split} & {E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^{k,{I_0}},{\boldsymbol{v}}_2^{k,{I_o}},{\boldsymbol{w}}_k^{{I_0}},p_k^j,l_k^j,t_k^j} \right)\\ & \quad\mathop \ge \limits^{\left( {\rm{d}} \right)} {E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^{k,{I_0}},{\boldsymbol{v}}_2^{k,{I_o}},{\boldsymbol{w}}_k^{{I_0}},p_k^{j + 1},l_k^j,t_k^j} \right) \\ & \quad\mathop \ge \limits^{\left( {\rm{e}} \right)} {E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^{k,{I_0}},{\boldsymbol{v}}_2^{k,{I_o}},{\boldsymbol{w}}_k^{{I_0}},p_k^{j + 1},l_k^{j + 1},t_k^j} \right)\\ & \quad\mathop \ge \limits^{\left( {\rm{f}} \right)} {E_{{\text{total}}}}\left( {{\boldsymbol{v}}_1^{k,{I_0}},{\boldsymbol{v}}_2^{k,{I_o}},{\boldsymbol{w}}_k^{{I_0}},p_k^{j + 1},l_k^{j + 1},t_k^{j + 1}} \right) \end{split} (23)

    同理,不等式(d),(e)和(f)成立的条件在于每个子问题都可获得最优解,从而确保目标函数值在迭代过程中单调非增。由于目标函数关于\eta 是单调非减的,所以Dinkelbach方法是收敛的。并且目标函数有一个有限的上界,因此步骤2收敛。

    由于步骤1使得目标函数下降,并且步骤2是单调非增的,因此整个迭代过程是单调非增的,而原问题必然存在下界,因此提出的交替优化算法能够保证收敛。

    本小节将通过MATLAB来验证所提算法的有效性。所有终端用户坐落在一个半径为10 m的圆内,用户群圆心与RIS 1的距离为10 m,基站与用户群圆心的距离为50 m,基站与RIS 2的距离为5 m。本文采用文献[20]的信道模型,并且信道模型的参数设置与文献[20]保持一致。带宽B{10^6}Hz,噪声功率σ2为–140 dBm·Hz–1,CPU电容系数κ为10–24,单位比特平均计算次数ck为750 cycles/bit,任务总量Lk为2×105 bit,最大本地计算任务量l k max为105 bit,卸载时间T为1 s,用户数K为5。

    图2给出了用户总功耗的迭代收敛曲线。在两个RIS协同作用的时候,随着迭代次数的增加,用户总能耗逐渐减少,并在第5步收敛到最优值,这体现了本文算法在满足约束条件的情况下具有快速的收敛性。在固定用户最大发射功率的条件下,改变RIS反射元数目时,RIS反射元数目越多,用户的能耗越低。在固定RIS反射元数目时,最大功率的改变只会改变初值,最终随着迭代的进行收敛到最优值。

    图 2  系统总能耗迭代收敛图

    图3描述了RIS数目与RIS反射元数目和本地计算比例的关系。在RIS数目固定的情况下,随着RIS反射元数目的增加,链路增益逐渐增大,用户卸载速率不断提升,因此卸载到基站端的任务不断增多,本地的任务量减小。固定RIS反射元数目,当只保留用户端的RIS({M_2} = 0)时,用户的本地任务量低于基站端只保留RIS ({M_1} = 0)情况下的任务量。这说明当单个RIS距离用户更近时,可带来更好的链路增益。当两个RIS之间协作时,用户的本地任务量远远低于单个RIS的情况,即更多的任务卸载到了MEC服务器。进而验证了两个RIS之间协作时,更有利于任务的卸载。

    图 3  RIS数目与RIS反射元数目和本地计算比例的关系

    图4刻画了RIS数目与不同卸载方案与用户总能耗间的关系。现将3个基准方案设计如下,全部卸载方案、二元卸载方案和固定比例卸载方案。在全部卸载方案中,每个终端用户都需要将自身的任务量全部卸载到MEC服务器,终端用户的能耗来源于终端用户卸载任务的过程。在二元卸载方案中,任务要么全部在本地执行,要么全部卸载到MEC服务器中。在固定比例卸载方案中,假设25%的任务量留在本地计算,剩余任务卸载到MEC服务器中。如图所示,在两个RIS的反射元保持相同情况下,随着RIS数量的增多,用户总能耗逐渐降低。这是因为终端用户的总能耗由两部分组成,分别为本地计算产生的能耗和卸载到MEC服务器而产生的能耗,本文所提方案权衡了两种能耗,从而达到最优。就用户总能耗而言,本文所提的部分卸载方案总是优于其它3种对比方案。从而进一步验证了本文所提方案的优越性。

    图 4  RIS数目与不同卸载方案和用户总能耗间的关系

    图5描述了离散相位RIS与RIS反射元数目和用户总能耗间的关系。由于在实际系统中,RIS的反射元件的相位调节是离散的,且离散的分辨率取决于量化的比特数,因此文中进行了连续相移和不同分辨率下的离散相移的性能比较。具体而言,在第t次迭代时,优化过的连续相移量化成离其最近的离散值,并将B比特量化下的离散值的集合记为 \left\{ {0,2\pi \times {2^{ - B}}, \cdots ,2\pi \times \left( {1 - {2^{ - B}}} \right)} \right\} 。从图中观察到,具有离散相移RIS的系统的用户总能耗高于连续相移RIS的系统的用户总能耗,随着RIS上反射元数目的增多,离散相移RIS和连续相移RIS的性能差异逐渐降低。在RIS反射元数目固定时,随着量化比特数的增加,用户总能耗降低。对于4 bit量化离散RIS实际上足以实现与连续RIS几乎相同的性能。

    图 5  离散相位RIS与RIS反射元数目和用户总能耗的关系

    本文研究了双智能超表面赋能移动边缘计算网络部分任务卸载及资源分配算法。首先,分析了两个智能超表面之间的反射对链路增益的影响,建立通信模型和计算模型。通过联合优化智能超表面相移、波束成形矢量、卸载时间分配、发射功率和本地任务量,实现终端用户能耗最小化。其次,为有效求解这个耦合约束的非凸问题,将原非凸问题分解为两个子问题,并采用Dinkelbach方法和最优性条件进行求解。最后,通过仿真验证了所提迭代算法的快速收敛特性与有效性,并且表明了两个智能超表面协作的情况下,对系统能耗的降低远远优于部署单个智能超表面的情况。本文所提算法对智能超表面协作移动边缘计算的研究具有重要的理论与现实意义,后续将引入智能超表面与智能超表面之间信道的不确定性,对智能超表面作进一步研究。

  • 图  1  服务功能链部署示意图

    图  2  网络服务部署架构

    图  3  DQN训练流程

    图  4  不同学习率对奖励函数的影响

    图  5  不同抽取样本批量大小对奖励函数的影响

    图  6  不同请求强度下的平均部署开销

    图  7  不同请求强度下的请求接受率

    图  8  不同请求强度下的平均时延

    表  1  算法1 基于DQN的在线服务链部署算法

     输入:服务链信息{G_r} = \left( {N_r^{'},L_r^{'}} \right)和当前网络状态{s_t}
     输出:服务链部署策略\pi _Q^*
     (1) 初始化经验复用池{{D} }的容量{{M} }
     (2) 初始化动作对应的Q值为随机值
     (3) 初始化选择策略\pi
     (4) for episode in range(EPISODES):
     (5)  初始化状态s
     (6)  for step in range(STEPS):
     (7)   检查底层网络资源状态,生成满足条件服务器节点集合\varPhi
     (8)   以\varepsilon 的概率随机选择一个动作{a_t}
     (9)   否则选择{a_t} = {\max _a}{Q^*}\left( {{s_t},a;\theta } \right)
     (10)   在服务链部署模拟器中执行动作{a_t}并观察对应的奖励
          {r_t}和下一个状态{s_{t + 1}}
     (11)   在经验复用池中存储样本{e_t} = \left( {{s_t},{a_t},{r_t},{s_{t + 1}}} \right)
     (12)   从经验复用池中随机抽取小批量的样本\left( {s_j},{a_j},{r_j},\right.
          \left.{s_{j + 1}} \right)
     (13)   令{y_j} = \left\{ {\begin{array}{*{20}{c} } { {r_j} },& { {r_j} = {\rm{end} } } \\ { {r_j} + \gamma { {\max }_{a'} }Q\left( { {s_{j + 1} },a';\theta } \right)},& { {r_j} \ne {\rm{end} } } \end{array} } \right.
     (14)   在{\left( {{y_j} - Q\left( {{s_{j + 1}},a;\theta } \right)} \right)^2}上执行梯度下降
     (15)   每L步更新目标网络参数{\theta ^ - }
     (16)  end
     (17) end
     (18) 根据{Q^*}\left( {{s_t},a;\theta } \right)计算服务链部署方案{\pi ^*}及其开销R
    下载: 导出CSV
  • [1] ETSI. Network Functions Virtualisation (NFV)[EB/OL]. https://www.etsi.org/technologies/nfv, 2020.
    [2] YI Bo, WANG Xingwei, LI Keqin, et al. A comprehensive survey of network function virtualization[J]. Computer Networks, 2018, 133: 212–262. doi: 10.1016/j.comnet.2018.01.021
    [3] ERAMO V, MIUCCI E, AMMAR M, et al. An approach for service function chain routing and virtual function network instance migration in network function virtualization architectures[J]. IEEE/ACM Transactions on Networking, 2017, 25(4): 2008–2025. doi: 10.1109/TNET.2017.2668470
    [4] KARAKUS M and DURRESI A. A survey: Control plane scalability issues and approaches in Software-Defined Networking (SDN)[J]. Computer Networks, 2017, 112: 279–293. doi: 10.1016/j.comnet.2016.11.017
    [5] BHAMARE D, JAIN R, SAMAKA M, et al. A survey on service function chaining[J]. Journal of Network and Computer Applications, 2016, 75: 138–155. doi: 10.1016/j.jnca.2016.09.001
    [6] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Network function virtualization: State-of-the-art and research challenges[J]. IEEE Communications Surveys & Tutorials, 2016, 18(1): 236–262. doi: 10.1109/COMST.2015.2477041
    [7] BARI M F, CHOWDHURY S R, AHMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 725–739. doi: 10.1109/TNSM.2016.2569020
    [8] LIU Jiaqiang, LI Yong, ZHANG Ying, et al. Improve service chaining performance with optimized middlebox placement[J]. IEEE Transactions on Services Computing, 2017, 10(4): 560–573. doi: 10.1109/TSC.2015.2502252
    [9] KUO T W, LIOU B H, LIN K C J, et al. Deploying chains of virtual network functions: On the relation between link and server usage[C]. IEEE INFOCOM 2016 - the 35th Annual IEEE International Conference on Computer Communications, San Francisco, USA, 2016: 1–9. doi: 10.1109/INFOCOM.2016.7524565.
    [10] SUN Quanying, LU Ping, LU Wei, et al. Forecast-assisted NFV service chain deployment based on affiliation-aware vNF placement[C]. 2016 IEEE Global Communications Conference (GLOBECOM), Washington, USA, 2016: 1–6. doi: 10.1109/GLOCOM.2016.7841846.
    [11] LI Defang, HONG Peilin, XUE Kaiping, et al. Virtual network function placement considering resource optimization and SFC requests in cloud datacenter[J]. IEEE Transactions on Parallel and Distributed Systems, 2018, 29(7): 1664–1677. doi: 10.1109/TPDS.2018.2802518
    [12] HAWILO H, JAMMAL M, and SHAMI A. Network function virtualization-aware orchestrator for service function chaining placement in the cloud[J]. IEEE Journal on Selected Areas in Communications, 2019, 37(3): 643–655. doi: 10.1109/JSAC.2019.2895226
    [13] TANG Hong, ZHOU D, and CHEN Duan. Dynamic network function instance scaling based on traffic forecasting and VNF placement in operator data centers[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(3): 530–543. doi: 10.1109/TPDS.2018.2867587
    [14] QI Dandan, SHEN Subin, and WANG Guanghui. Towards an efficient VNF placement in network function virtualization[J]. Computer Communications, 2019, 138: 81–89. doi: 10.1016/j.comcom.2019.03.005
    [15] SINGH S, OKUN A, and JACKSON A. Learning to play Go from scratch[J]. Nature, 2017, 550(7676): 336–337. doi: 10.1038/550336a
    [16] 袁泉, 汤红波, 黄开枝, 等. 基于Q-learning算法的vEPC虚拟网络功能部署方法[J]. 通信学报, 2017, 38(8): 172–182. doi: 10.11959/j.issn.1000-436x.2017173

    YUAN Quan, TANG Hongbo, HUANG Kaizhi, et al. Deployment method for vEPC virtualized network function via Q-learning[J]. Journal on Communications, 2017, 38(8): 172–182. doi: 10.11959/j.issn.1000-436x.2017173
    [17] XIAO Yikai, ZHANG Qixia, LIU Fangming, et al. NFVdeep: Adaptive online service function chain deployment with deep reinforcement learning[C]. Proceedings of the International Symposium on Quality of Service, Arizona, USA, 2019: 1–10. doi: 10.1145/3326285.3329056.
    [18] QUANG P T A, HADJADJ-AOUL Y, and OUTTAGARTS A. A deep reinforcement learning approach for VNF forwarding graph embedding[J]. IEEE Transactions on Network and Service Management, 2019, 16(4): 1318–1331. doi: 10.1109/TNSM.2019.2947905
    [19] KINGMAN J F C. Poisson Processes[M]. ARMITAGE P and COLTON T. Encyclopedia of Biostatistics. Chichester: John Wiley & Sons, 2005. doi: 10.1002/0470011815.b2a07042.
    [20] HOWARD R A. Dynamic programming and Markov processes[J]. Technometrics, 1961, 3(1): 120–121. doi: 10.2307/1266484
    [21] The University of Adelaide. The internet topology zoo[EB/OL]. http://www.topology-zoo.org/dataset.html, 2012.
    [22] Networkx. Network analysis in python: Important structures and bipartite graphs[EB/OL]. https://coderzcolumn.com/tutorials/data-science/network-analysis-in-python-important-structures-and-bipartite-graphs-networkx, 2020.
    [23] YALA L, FRANGOUDIS P A, LUCARELLI G, et al. Cost and availability aware resource allocation and virtual function placement for CDNaaS provision[J]. IEEE Transactions on Network and Service Management, 2018, 15(4): 1334–1348. doi: 10.1109/TNSM.2018.2874524
    [24] OCHOA-ADAY L, CERVELLÓ-PASTOR C, FERNÁNDEZ-FERNÁNDEZ A, et al. An online algorithm for dynamic NFV placement in cloud-based autonomous response networks[J]. Symmetry, 2018, 10(5): 163. doi: 10.3390/sym10050163
    [25] MAROTTA A, ZOLA E, D’ANDREAGIOVANNI F, et al. A fast robust optimization-based heuristic for the deployment of green virtual network functions[J]. Journal of Network and Computer Applications, 2017, 95: 42–53. doi: 10.1016/j.jnca.2017.07.014
    [26] SHI Runyu, ZHANG Jia, CHU Wenjing, et al. MDP and machine learning-based cost-optimization of dynamic resource allocation for network function virtualization[C]. 2015 IEEE International Conference on Services Computing, New York, USA, 2015: 65–73. doi: 10.1109/SCC.2015.19.
  • 加载中
图(8) / 表(1)
计量
  • 文章访问数:  1074
  • HTML全文浏览量:  741
  • PDF下载量:  110
  • 被引次数: 0
出版历程
  • 收稿日期:  2020-12-02
  • 修回日期:  2021-06-30
  • 网络出版日期:  2021-08-10
  • 刊出日期:  2021-11-23

目录

/

返回文章
返回