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

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

doi:10.11999/JEIT190306

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

doi: 10.11999/JEIT190306

1.
重庆邮电大学通信与信息工程学院重庆 400065
2.
重庆邮电大学移动通信技术重点实验室重庆 400065

基金项目: 国家自然科学基金(61571073)，重庆市教委科学技术研究项目(KJZD-M201800601)

详细信息

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

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

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

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

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

通讯作者:
肖娇　Ir_xiao@163.com

中图分类号: TN929.5
计量
- 文章访问数: 2133
- HTML全文浏览量: 758
- PDF下载量: 139
- 被引次数: 5
出版历程
- 收稿日期: 2019-04-30
- 修回日期: 2019-12-13
- 网络出版日期: 2020-07-01
- 刊出日期: 2020-08-18

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

1.
School of Communication and Information Engineering, Chongqing University of Post and Telecommunications, Chongqing 400065, China
2.
Key Laboratory of Mobile Communication Technology, Chongqing University of Post and Telecommunications, Chongqing 400065, China

Funds: The National Natural Science Foundation of China (61571073), The Science and Technology Research Program of Chongqing Municipal Education Commission (KJZD-M201800601)

摘要

摘要:
针对车联网业务的低时延、低功耗需求及海量设备计算卸载引起的网络拥塞问题，该文提出一种在云雾混合网络架构下的联合计算卸载、计算资源和无线资源分配算法(JODRAA)。首先，该算法考虑将云计算与雾计算结合，以最大时延作为约束，建立最小化系统能耗和资源成本的资源优化模型。其次，将原问题转化为标准二次约束二次规划(QCQP)问题，并设计一种低复杂度的联合卸载决策和计算资源分配算法。进一步，针对海量设备计算卸载引起的网络拥塞问题，建立卸载用户接入请求队列的上溢概率估计模型，提出一种基于在线测量的雾节点时频资源配置算法。最后，借助分式规划理论和拉格朗日对偶分解方法得到迭代的带宽和功率分配策略。仿真结果表明，该文算法可以在满足时延需求的前提下，最小化系统能耗和资源成本。
- 车联网 /
- 雾计算 /
- 计算卸载 /
- 资源分配
Abstract:
For the problems of low delay, low power requirement and access congestion caused by computational unloading of mass devices, a Joint Offloading Decision and Resource Allocation Algorithm (JODRAA) is proposed based on cloud-fog hybrid network architecture. Firstly, the algorithm considers the combination of cloud and fog computing, and establishes a resource optimization model to minimize system energy consumption and resource cost with maximum delay as constraint. Secondly, the original problem is transformed into a standard Quadratically Constrained Quadratic Program (QCQP) problem, and a low-complexity joint unloading decision-making and computational resource allocation algorithm is designed. Furthermore, considering the access congestion problem caused by massive computing of unloading devices, an estimation model of the overflow probability of unloading user access request queue is established, and an on-line measurement based time-frequency resource allocation algorithm for fog nodes is proposed. Finally, the iterative bandwidth and power allocation strategy is obtained by using fractional programming theory and Lagrange dual decomposition method. The simulation results show that the proposed algorithm can minimize the system energy consumption and resource cost on the premise of time delay.
- Vehicular network /
- Fog computing /
- Computation offload /
- Resource allocation

HTML全文

图 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

参考文献(16)

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.

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

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.

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.

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

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

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

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

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.

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.

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

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

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.

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.

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

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

施引文献

期刊类型引用(2)

1.	钟选明，李军野，廖成. 基于空频分解信号子空间向量的时间反演成像. 电子与信息学报. 2017(02): 494-498 . 本站查看
2.	陈秋菊，姜秋喜，曾芳玲，刘鑫. 稀疏阵列时间反演脉冲信号空间功率合成方法. 电波科学学报. 2016(03): 553-561 . 百度学术