基于云霧混合計(jì)算的車聯(lián)網(wǎng)聯(lián)合資源分配算法
doi: 10.11999/JEIT190306 cstr: 32379.14.JEIT190306
-
1.
重慶郵電大學(xué)通信與信息工程學(xué)院 重慶 400065
-
2.
重慶郵電大學(xué)移動(dòng)通信技術(shù)重點(diǎn)實(shí)驗(yàn)室 重慶 400065
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
-
摘要:
針對(duì)車聯(lián)網(wǎng)業(yè)務(wù)的低時(shí)延、低功耗需求及海量設(shè)備計(jì)算卸載引起的網(wǎng)絡(luò)擁塞問(wèn)題，該文提出一種在云霧混合網(wǎng)絡(luò)架構(gòu)下的聯(lián)合計(jì)算卸載、計(jì)算資源和無(wú)線資源分配算法(JODRAA)。首先，該算法考慮將云計(jì)算與霧計(jì)算結(jié)合，以最大時(shí)延作為約束，建立最小化系統(tǒng)能耗和資源成本的資源優(yōu)化模型。其次，將原問(wèn)題轉(zhuǎn)化為標(biāo)準(zhǔn)二次約束二次規(guī)劃(QCQP)問(wèn)題，并設(shè)計(jì)一種低復(fù)雜度的聯(lián)合卸載決策和計(jì)算資源分配算法。進(jìn)一步，針對(duì)海量設(shè)備計(jì)算卸載引起的網(wǎng)絡(luò)擁塞問(wèn)題，建立卸載用戶接入請(qǐng)求隊(duì)列的上溢概率估計(jì)模型，提出一種基于在線測(cè)量的霧節(jié)點(diǎn)時(shí)頻資源配置算法。最后，借助分式規(guī)劃理論和拉格朗日對(duì)偶分解方法得到迭代的帶寬和功率分配策略。仿真結(jié)果表明，該文算法可以在滿足時(shí)延需求的前提下，最小化系統(tǒng)能耗和資源成本。
-
關(guān)鍵詞:
- 車聯(lián)網(wǎng) /
- 霧計(jì)算 /
- 計(jì)算卸載 /
- 資源分配
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.
-
Key words:
- Vehicular network /
- Fog computing /
- Computation offload /
- Resource allocation
-
表 1 聯(lián)合卸載決策和基于二分法的計(jì)算資源調(diào)度算法
1. 初始化試驗(yàn)次數(shù)$J$，用戶數(shù)$M$，總帶寬$B_f^{\max }$及資源塊帶寬${B_{SC}}$
及總計(jì)算資源${F^{{\rm{fog}}}}$，初始化用戶參數(shù)${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. 利用凸優(yōu)化工具求解式(17)得到優(yōu)化解${{{Q}}^*}$ 3. 從優(yōu)化解${{{Q}}^{\rm{*}}}$中提取左上角$2M \times 2M$的子矩陣${{{Q}}^{'*}}$, ${{{Q}}^{'*}}$中的
對(duì)角線上的元素值為$\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. 根據(jù)式(18)從$\Pr $中提取卸載決策${{{v}}^j}$ 6. 執(zhí)行計(jì)算資源調(diào)度：初始化參數(shù)${\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} } } }}$ then9. ${\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)得到計(jì)算資源調(diào)度策略${{{f}}^{{\rm{fog}}}}$ 18. end for 
下載: 導(dǎo)出CSV
表 2 基于在線測(cè)量的接入控制算法
1. 初始化每個(gè)霧節(jié)點(diǎn)的資源塊配置數(shù)量$z$和剩余資源塊數(shù)量$B$，
在周期$n$上觀察每個(gè)霧節(jié)點(diǎn)$f$ 的接入請(qǐng)求隊(duì)列狀態(tài)$Q_n^f$2. for $f = 1;f < F;f + + $ do 3. 計(jì)算$a_{\rm o}^f$，估計(jì)${\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. 計(jì)算$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)執(zhí)行黃金分割搜索算法估計(jì)$\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
下載: 導(dǎo)出CSV
表 3 基于迭代的帶寬和功率資源調(diào)度
1. 初始化迭代次數(shù)${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. 對(duì)給定的${V^{{N_1}}}$，根據(jù)式(31)求得優(yōu)化的傳輸功率解 5. 在區(qū)間$[0,1]$內(nèi)執(zhí)行二分搜索方法求解${\varphi _m}({N_2})$，并將
${\varphi _m}({N_2})$代入式(34)求解帶寬資源調(diào)度方案6. 通過(guò)次梯度法分別更新拉格朗日乘子 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}$ then8. $\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. 輸出無(wú)線資源調(diào)度優(yōu)化解${{{p}}^*}$, ${{{\alpha}} ^*}$
下載: 導(dǎo)出CSV
表 4 仿真參數(shù)
參數(shù) 數(shù)值 系統(tǒng)帶寬 10 MHz(50PRBs) 路徑損耗模型 UrbanMicro(UMi) 最大傳輸功率 23 dBm 計(jì)算資源單價(jià) 0.10, 0.15, 0.20 unit/cycle 計(jì)算密度 297.62 cycle/bit 鏈路傳輸速率 1 Mb/s 參數(shù) 數(shù)值 卸載業(yè)務(wù)到達(dá) 泊松分布 萊斯因子 6 dB 滑動(dòng)窗口大小 60 ms 平滑指數(shù) 0.7 霧計(jì)算資源量 1 G cycle 云層計(jì)算能力 2 G cycle/s 參數(shù) 數(shù)值 比特到達(dá)速率 0.4 Mbit/ms 噪聲功率 –174 dBm/Hz PRB單價(jià) 1, 1.5, 2 unit/PRB 仿真時(shí)間 6000 ms 隊(duì)列上溢概率 0.2 單位$t$功率消耗 0.01 W
下載: 導(dǎo)出CSV
-
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 -
計(jì)量
- 文章訪問(wèn)數(shù): 2161
- HTML全文瀏覽量: 781
- PDF下載量: 141
- 被引次數(shù): 0
下載:
