高级搜索

留言板

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

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

基于云雾混合计算的车联网联合资源分配算法

唐伦 肖娇 魏延南 赵国繁 陈前斌

唐伦, 肖娇, 魏延南, 赵国繁, 陈前斌. 基于云雾混合计算的车联网联合资源分配算法[J]. 电子与信息学报, 2020, 42(8): 1926-1933. doi: 10.11999/JEIT190306
引用本文: 唐伦, 肖娇, 魏延南, 赵国繁, 陈前斌. 基于云雾混合计算的车联网联合资源分配算法[J]. 电子与信息学报, 2020, 42(8): 1926-1933. doi: 10.11999/JEIT190306
Lun TANG, Jiao XIAO, Yannan WEI, Guofan ZHAO, Qianbin CHEN. Joint Resource Allocation Algorithms Based on Mixed Cloud/Fog Computing in Vehicular Network[J]. Journal of Electronics and Information Technology, 2020, 42(8): 1926-1933. doi: 10.11999/JEIT190306
Citation: Lun TANG, Jiao XIAO, Yannan WEI, Guofan ZHAO, Qianbin CHEN. Joint Resource Allocation Algorithms Based on Mixed Cloud/Fog Computing in Vehicular Network[J]. Journal of Electronics and Information Technology, 2020, 42(8): 1926-1933. doi: 10.11999/JEIT190306

基于云雾混合计算的车联网联合资源分配算法

doi: 10.11999/JEIT190306
基金项目: 国家自然科学基金(61571073),重庆市教委科学技术研究项目(KJZD-M201800601)
详细信息
    作者简介:

    唐伦:男,1973年生,教授,博士生导师,主要研究方向为新一代无线通信网络、异构蜂窝网络等

    肖娇:女,1995年生,硕士生,研究方向为蜂窝车联网络下的资源调度算法

    魏延南:男,1995年生,硕士生,研究方向为5G网络切片、虚拟资源分配、随机优化理论

    赵国繁:女,1993年生,硕士生,研究方向为5G网络切片中的资源分配,可靠性

    陈前斌:男,1967年生,教授,博士生导师,主要研究方向为个人通信、多媒体信息处理与传输、下一代移动通信网络、异构蜂窝网络等

    通讯作者:

    肖娇 Ir_xiao@163.com

  • 中图分类号: TN929.5

Joint Resource Allocation Algorithms Based on Mixed Cloud/Fog Computing in Vehicular Network

Funds: The National Natural Science Foundation of China (61571073), The Science and Technology Research Program of Chongqing Municipal Education Commission (KJZD-M201800601)
  • 摘要: 针对车联网业务的低时延、低功耗需求及海量设备计算卸载引起的网络拥塞问题,该文提出一种在云雾混合网络架构下的联合计算卸载、计算资源和无线资源分配算法(JODRAA)。首先,该算法考虑将云计算与雾计算结合,以最大时延作为约束,建立最小化系统能耗和资源成本的资源优化模型。其次,将原问题转化为标准二次约束二次规划(QCQP)问题,并设计一种低复杂度的联合卸载决策和计算资源分配算法。进一步,针对海量设备计算卸载引起的网络拥塞问题,建立卸载用户接入请求队列的上溢概率估计模型,提出一种基于在线测量的雾节点时频资源配置算法。最后,借助分式规划理论和拉格朗日对偶分解方法得到迭代的带宽和功率分配策略。仿真结果表明,该文算法可以在满足时延需求的前提下,最小化系统能耗和资源成本。
  • 图  1  云雾混合车联网网络架构

    图  2  节省能量与时延阈值的关系

    图  3  平均资源成本与雾节点数量的关系

    图  4  总能量消耗与雾节点用户数的关系

    图  5  平均时延与雾节点数量的关系

    图  6  违反概率与卸载用户数的关系

    表  1  联合卸载决策和基于二分法的计算资源调度算法

     1. 初始化试验次数$J$,用户数$M$,总带宽$B_f^{\max }$及资源块带宽${B_{SC}}$
       及总计算资源${F^{{\rm{fog}}}}$,初始化用户参数${D_m}$, ${u_m}$, $f_m^{{\rm{loc}}}$, $p_m^{\max }$,
    $p_m^{{\rm{id}}}$, $p_m^{{\rm{loc}}}$, $R_m^{{\rm{fc}}}$, $f_m^c$, $d_m^{\max }$,初始化式(17)中的所有矩阵
     2. 利用凸优化工具求解式(17)得到优化解${{{Q}}^*}$
     3. 从优化解${{{Q}}^{\rm{*}}}$中提取左上角$2M \times 2M$的子矩阵${{{Q}}^{'*}}$, ${{{Q}}^{'*}}$中的
      对角线上的元素值为$\Pr = \left[ { {\rm{pr} }_1^f,{\rm{pr} }_1^{\rm c},...,{\rm{pr} }_M^f,{\rm{pr} }_M^{\rm c}} \right]$
     4. for $j = 1;j \le J;j + + $ do
     5.  根据式(18)从$\Pr $中提取卸载决策${{{v}}^j}$
     6.  执行计算资源调度:初始化参数${\chi ^{\min }} = \max \{ {S_m}\} ,\,{\chi ^{\max } } = $
       $ \displaystyle\sum\limits_m {\left( {\frac{ { {C_m}p_m^{ {\rm{id} } }M} }{ { {F^{ {\rm{fog} } } } } } + {S_m} } \right)}$,于是有${\chi ^{\min }} \le {\chi ^{{\rm{opt}}}} \le {\chi ^{\max }}$,最大
       可容忍误差$\varepsilon > 0$, ${\chi ^j}{\rm{ = (}}{\chi ^{\min }} + {\chi ^{\max }}{\rm{)/2}}$
     7. while $|{\chi ^{\max }} - {\chi ^{\min }}| \ge \varepsilon $ do
     8.   if $\displaystyle\sum\limits_{m \in M} {\frac{ { {C_m}p_m^{ {\rm{id} } } }}{ { {\chi ^j} - {S_m} } } > {F^{ {\rm{fog} } } }}$ then
     9.    ${\chi ^{\min }} = {\chi ^j}$
     10.   else
     11.    ${\chi ^{\max }} = {\chi ^j}$
     12.   end if
     13. end while
     14.  if $|{\chi ^{\max }} - {\chi ^{\min }}| \le \varepsilon $ then
     15.   ${\chi ^{{\rm{opt}}}} = {\chi ^j}$
     16. end if
     17. 将得到的${\chi ^{{\rm{opt}}}}$代入式(21)得到计算资源调度策略${{{f}}^{{\rm{fog}}}}$
     18. end for
    下载: 导出CSV

    表  2  基于在线测量的接入控制算法

     1. 初始化每个雾节点的资源块配置数量$z$和剩余资源块数量$B$,
    在周期$n$上观察每个雾节点$f$ 的接入请求队列状态$Q_n^f$
     2. for $f = 1;f < F;f + + $ do
     3.  计算$a_{\rm o}^f$,估计${\mathop m\limits^{\wedge} } _{\rm o}^f$
     4. while $Q_n^f \ge B_H^f$ or $B = \emptyset $ do
     5.  $z \leftarrow z + 1$,${C_f}(n) \leftarrow z\mathop r\limits^\_ $,$B \leftarrow B - 1$
     6. end while
     7. 计算$a_{\rm o}^f$及$\hat m_{\rm o}^f$
     8. if $Q_n^f < B_H^f$ & $\hat m_{\rm o}^f \ge a_{\rm o}^f$ then
     9. $z \leftarrow z + {\Delta _1}$,${C_f}(n) \leftarrow z\mathop r\limits^\_ $,$B \leftarrow B - {\Delta _1}$
     10.  else if $Q_n^f < B_H^f$ & $\hat m_{\rm o}^f \ge a_{\rm o}^f$ then
     11.   式(24)执行黄金分割搜索算法估计$\hat P_{n + N}^f$
     12.   if $\hat P_{n + N}^f \ge {\varepsilon _f}$ then
     13.   $z \leftarrow z + {\Delta _2}$, ${C_f}(n) \leftarrow z\mathop r\limits^\_ $, $B \leftarrow B - {\Delta _2}$
     14.   end if
     15.  end if
     16. end if
     17. end for
    下载: 导出CSV

    表  3  基于迭代的带宽和功率资源调度

     1. 初始化迭代次数${N_1}{\rm{ = }}0$和${N_2}{\rm{ = }}0$,误差精度${\delta _1}$和${\delta _2}$, ${V^{{N_1}}}{\rm{ = }}1$
     2. while ${N_1} < {N_{1\max }}$ do
     3.  while ${N_2} < {N_{2\max }}$ do
     4.   对给定的${V^{{N_1}}}$,根据式(31)求得优化的传输功率解
     5.   在区间$[0,1]$内执行二分搜索方法求解${\varphi _m}({N_2})$,并将
        ${\varphi _m}({N_2})$代入式(34)求解带宽资源调度方案
     6.    通过次梯度法分别更新拉格朗日乘子
     7.   if ${\rm{||}}\beta ({N_2} + 1) - \beta ({N_2})|{|_2} < {\delta _2}$,
        $||\eta ({N_2} + 1) - \eta ({N_2})|{|_2} < {\delta _2}$,
        $||\mu ({N_2} + 1) - \mu ({N_2})|{|_2} < {\delta _2}$,
        $||\pi ({N_2} + 1) - \pi ({N_2})|{|_2} < {\delta _2}$ then
     8.     $\alpha _m^{{N_1}} = {\alpha _m}({N_2})$, $p_m^{{\rm{com}}{{\rm{N}}_1}} = p_m^{{\rm{com}}}\left( {{N_2}} \right)$, break
     9.  else
     10.   ${N_2} = {N_2} + 1$
     11.  end if
     12.  end while
     13.  if $\left| { {D_m}p_m^{ {\rm{com} }{ {\rm{N} }_{\rm{1} } } } - {V^{ {N_1} } }\alpha _m^{ {N_1} }\lg \left( {1 + \dfrac{ {p_m^{ {\rm{com} }{ {\rm{N} }_{\rm{1} } } }{h_m} } }{ {\alpha _m^{ {N_1} }{N_0}{B_{ {\rm{SC} } } } } } } \right)} \right| < {\delta _1}$ then
     14.    $\{ {{{p}}^*},{{{\alpha}} ^*}\} = \{ {{{p}}^{{\rm{com}}{{\rm{N}}_{\rm{1}}}}},{{{\alpha}} ^{{N_1}}}\} $
     15.  else
     16.    令${V^{ {N_1} + 1} } \!\!=\! {D_m}p_m^{ {\rm{com} }{ {\rm{N} }_{\rm{1} } } }/\alpha _m^{ {N_1} }{B_{ {\rm{SC} } } }\lg \!\left( {1 \!+\! \dfrac{ {p_m^{ {\rm{com} }{ {\rm{N} }_{\rm{1} } } }{h_m} } }{ {\alpha _m^{ {N_1} }{N_0}{B_{ {\rm{SC} } } } } } } \right)$
     17.   end if
     18. end while
     19. 输出无线资源调度优化解${{{p}}^*}$, ${{{\alpha}} ^*}$
    下载: 导出CSV

    表  4  仿真参数

    参数数值
    系统带宽10 MHz(50PRBs)
    路径损耗模型UrbanMicro(UMi)
    最大传输功率23 dBm
    计算资源单价0.10, 0.15, 0.20 unit/cycle
    计算密度297.62 cycle/bit
    链路传输速率1 Mb/s
    参数数值
    卸载业务到达泊松分布
    莱斯因子6 dB
    滑动窗口大小60 ms
    平滑指数0.7
    雾计算资源量1 G cycle
    云层计算能力2 G cycle/s
    参数数值
    比特到达速率0.4 Mbit/ms
    噪声功率–174 dBm/Hz
    PRB单价1, 1.5, 2 unit/PRB
    仿真时间6000 ms
    队列上溢概率0.2
    单位$t$功率消耗0.01 W
    下载: 导出CSV
  • [1] MEBREK A, MERGHEM-BOULAHIA L, and ESSEGHIR M. Efficient green solution for a balanced energy consumption and delay in the IoT-Fog-Cloud computing[C]. The 16th IEEE International Symposium on Network Computing and Applications, Cambridge, USA, 2017: 1–4. doi: 10.1109/NCA.2017.8171359.
    [2] BACCARELLI E, NARANJO P G V, SCARPINITI M, et al. Fog of everything: Energy-efficient networked computing architectures, research challenges, and a case study[J]. IEEE Access, 2017, 5: 9882–9910. doi:  10.1109/ACCESS.2017.2702013
    [3] LIU Kaiyang, PENG Jun, ZHANG Xiaoyong, et al. A combinatorial optimization for energy-efficient mobile cloud offloading over cellular networks[C]. 2016 IEEE Global Communications Conference, Washington, USA, 2016: 1–6. doi: 10.1109/GLOCOM.2016.7841488.
    [4] YANG Lei, CAO Jiannong, TANG Shaojie, et al. A framework for partitioning and execution of data stream applications in mobile cloud computing[C]. The 5th IEEE International Conference on Cloud Computing, Honolulu, USA, 2012: 794–802. doi: 10.1109/CLOUD.2012.97.
    [5] LIU Mengyu and LIU Yuan. Price-based distributed offloading for mobile-edge computing with computation capacity constraints[J]. IEEE Wireless Communications Letters, 2018, 7(3): 420–423. doi:  10.1109/LWC.2017.2780128
    [6] CAO Xiaowen, WANG Feng, XU Jie, et al. Joint computation and communication cooperation for energy-efficient mobile edge computing[J]. IEEE Internet of Things Journal, 2019, 6(3): 4188–4200. doi:  10.1109/JIOT.2018.2875246
    [7] MENG Xianling, WANG Wei, and ZHANG Zhaoyang. Delay-constrained hybrid computation offloading with cloud and fog computing[J]. IEEE Access, 2017, 5: 21355–21367. doi:  10.1109/ACCESS.2017.2748140
    [8] GU H Y, YANG C Y, and FONG B. Low-complexity centralized joint power and admission control in cognitive radio networks[J]. IEEE Communications Letters, 2009, 13(6): 420–422. doi:  10.1109/LCOMM.2009.082173
    [9] JIANG Menglan, CONDOLUCI M, and MAHMOODI T. Network slicing management & prioritization in 5G mobile systems[C]. The 22th European Wireless Conference, Oulu, Finland, 2016: 1–6.
    [10] YAQOOB S, ULLAH A, AKBAR M, et al. Fog-assisted congestion avoidance scheme for internet of vehicles[C]. The 14th International Wireless Communications & Mobile Computing Conference, Limassol, Cyprus, 2018: 618–622. doi: 10.1109/IWCMC.2018.8450402.
    [11] LI Jian, PENG Mugen, YU Yuling, et al. Energy-efficient joint congestion control and resource optimization in heterogeneous cloud radio access networks[J]. IEEE Transactions on Vehicular Technology, 2016, 65(12): 9873–9887. doi:  10.1109/TVT.2016.2531184
    [12] LIU Yiming, YU F R, LI Xi, et al. Distributed resource allocation and computation offloading in fog and cloud networks with non-orthogonal multiple access[J]. IEEE Transactions on Vehicular Technology, 2018, 67(12): 12137–12151. doi:  10.1109/TVT.2018.2872912
    [13] LI Qiuping, ZHAO Junhui, GONG Yi, et al. Energy-efficient computation offloading and resource allocation in fog computing for internet of everything[J]. China Communications, 2019, 16(3): 32–41.
    [14] SHAHZADI R, NIAZ A, ALI M, et al. Three tier fog networks: Enabling IoT/5G for latency sensitive applications[J]. China Communications, 2019, 16(3): 1–11.
    [15] SOOKHAK M, YU F R, HE Ying, et al. Fog vehicular computing: Augmentation of fog computing using vehicular cloud computing[J]. IEEE Vehicular Technology Magazine, 2017, 12(3): 55–64. doi:  10.1109/MVT.2017.2667499
    [16] LI Di, KAR S, and CUI Shuguang. Distributed quickest detection in sensor networks via two-layer large deviation analysis[J]. IEEE Internet of Things Journal, 2018, 5(2): 930–942. doi:  10.1109/JIOT.2018.2810825
  • [1] 吴大鹏, 郑豪, 崔亚平.  面向服务的车辆网络切片协调智能体设计, 电子与信息学报. doi: 10.11999/JEIT190635
    [2] 李波, 牛力, 黄鑫, 丁洪伟.  基于移动路径预测的车载边缘计算卸载切换策略研究, 电子与信息学报. doi: 10.11999/JEIT190483
    [3] 赵星, 彭建华, 游伟, 陈璐.  基于k-匿名的隐私保护计算卸载方法, 电子与信息学报. doi: 10.11999/JEIT191046
    [4] 胡荣磊, 陈雷, 段晓毅, 于秉琪.  一种适用于雾计算的终端节点切换认证协议, 电子与信息学报. doi: 10.11999/JEIT200005
    [5] 赵海涛, 朱银阳, 丁仪, 朱洪波.  车联网中基于移动边缘计算的内容感知分类卸载算法研究, 电子与信息学报. doi: 10.11999/JEIT190594
    [6] 张海波, 程妍, 刘开健, 贺晓帆.  车联网中整合移动边缘计算与内容分发网络的移动性管理策略, 电子与信息学报. doi: 10.11999/JEIT190571
    [7] 刘通, 唐伦, 何小强, 陈前斌.  融合区块链与雾计算系统中基于网络时延和资源管理的优化任务卸载方案, 电子与信息学报. doi: 10.11999/JEIT190654
    [8] 钱志鸿, 阎双叶, 田春生, 王鑫.  LTE-A网络中D2D通信的资源分配算法研究, 电子与信息学报. doi: 10.11999/JEIT180043
    [9] 唐伦, 张亚, 梁荣, 陈前斌.  基于网络切片的网络效用最大化虚拟资源分配算法, 电子与信息学报. doi: 10.11999/JEIT161322
    [10] 孟洛明, 孙康, 韦磊, 郭少勇, 徐思雅.  一种面向电力无线专网的虚拟资源优化分配机制, 电子与信息学报. doi: 10.11999/JEIT161043
    [11] 李钊, 李意文.  基于多维资源自适应分配的协作认知传输机制, 电子与信息学报. doi: 10.11999/JEIT151286
    [12] 曹龙, 赵杭生, 鲍丽娜, 张建照.  分层认知无线电网络中基于稳定匹配的资源分配算法, 电子与信息学报. doi: 10.11999/JEIT151460
    [13] 张海波, 穆立雄, 陈善学, 彭焦阳.  OFDMA毫微微小区双层网络中基于分组的资源分配, 电子与信息学报. doi: 10.11999/JEIT150699
    [14] 李东生, 高杨, 雍爱霞.  基于改进离散布谷鸟算法的干扰资源分配研究, 电子与信息学报. doi: 10.11999/JEIT150726
    [15] 胡莹, 黄永明, 俞菲, 杨绿溪.  多用户大规模MIMO系统能效资源分配算法, 电子与信息学报. doi: 10.11999/JEIT150088
    [16] 黄博, 方旭明, 陈煜.  OFDMA中继网络变时域节能资源分配策略, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.01180
    [17] 左勇, 刘学勇, 刘海洋, 陈杰.  基于对偶分解的OFDMA系统资源分配算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2012.00326
    [18] 陈瑾平, 李春国, 杨绿溪.  比例速率约束下OFDMA系统近似最优的资源分配算法, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.00934
    [19] 刘蓓邱玲, Qiu-Ling, Qiu,L., Qiu-Ling, Qiu.  时变信道下基于有效容量的OFDMA系统资源分配方案, 电子与信息学报. doi: 10.3724/SP.J.1146.2010.01409
    [20] 盛煜, 彭木根, 王文博.  基于QoS保证的广播/组播OFDM系统资源分配策略, 电子与信息学报. doi: 10.3724/SP.J.1146.2007.00847
  • 加载中
  • 图(6) / 表ll (4)
    计量
    • 文章访问数:  233
    • HTML全文浏览量:  144
    • PDF下载量:  26
    • 被引次数: 0
    出版历程
    • 收稿日期:  2019-04-30
    • 修回日期:  2019-12-13
    • 网络出版日期:  2020-07-01
    • 刊出日期:  2020-08-10

    目录

      /

      返回文章
      返回

      官方微信,欢迎关注