Research on Multi-task Partial Offloading Scheme in Vehicular Edge Computing
-
摘要: 现有车载应用设备对时延有更严苛的要求,车载边缘计算(VEC)能够充分利用网络边缘设备,如路边单元(RSU)进行协作处理,可有效地降低时延。现有研究多假设RSU计算资源充足,可提供无限的服务,但实际其计算资源会随着所需处理任务数量的增加而受限,对时延敏感的车载应用造成限制。该文针对此问题,提出一种车载边缘计算中多任务部分卸载方案,该方案在充分利用RSU的计算资源条件下,考虑邻近车辆的剩余可用计算资源,以最小化总任务处理时延。首先在时延限制和资源约束下分配各任务在本地、RSU和邻近车辆的最优卸载决策变量比例,其次以最小处理时延为目的在一跳通信范围内选择合适的空闲车辆作为处理部分任务的邻近车辆。仿真结果表明所提车载边缘计算中多任务部分卸载方案相较现有方案能较好地降低时延。Abstract: Nowadays, the existing vehicular applications have more stringent requirements for delay. Vehicular Edge Computing (VEC) is able to take advantage of network edges devices, such as Road Side Unit (RSU), for collaborative processing, which can effectively reduce the latency. Most existing studies assume that RSU has the sufficient computing resources to provide the unlimited services. But in fact, its computing resources will be limited with the increase of the number of processing tasks, which will restrict the delay sensitive vehicular applications. To solve this problem, a multi-task partial offloading scheme in vehicular edge computing is proposed in this paper. To minimize the total task processing delay, the remaining available computing resources of adjacent vehicles is considered under the condition of making full use of RSU computing resources in this scheme. Firstly, under the constrains of delay and resource, the optimal offloading decision variable ratio of local, RSU and adjacent vehicle for each task are allocated. Secondly, in order to minimize processing delay, the appropriate spare vehicle is selected in one-hop range as adjacent vehicles to process part of the task. Simulation results show the scheme proposed can reduce the delay better compared with other schemes.
-
表 1 部分符号
符号 描述 $ \alpha $ 本地计算所占任务比例 $ \beta $ RSU计算所占任务比例 $ \gamma $ 邻近车辆计算所占任务比例 $ {D_i} $ 车辆$ {V_i} $的任务数据大小 $ {C_i} $ 处理任务所需要的计算资源 $ t_i^{\max } $ 最大可容忍时延阈值 $ {t_{i,{\text{RSU}}}} $ 车辆$ {V_i} $在RSU内的最大传输时延 $ {t_{i,j}} $ 车辆$ {V_i} $在车辆$ {V_j} $覆盖范围内的可持续时延 $ t_i^{{\text{loc}}} $ 本地计算时延 $ T_{i,{\text{RSU}}}^{{\text{V2I}}} $ RSU计算时延 $ T_{i,j}^{{\text{V2V}}} $ 邻近车辆计算时延 $ {T_i} $ 车辆$ {V_i} $任务处理时延 $ {R_i}\left( t \right) $ V2I通信中信道传输速率 ${d_{i,{\text{RSU}}}}\left( t \right)$ V2I通信中随时间变化的距离变量 $ {t_{i,{\text{RSU}}}} $ V2I通信中车辆$ {V_i} $ 在RSU内的最大传输时延 ${ {\overline R_i} }$ V2I通信中平均传输速率 $ {R_{i,j}}\left( t \right) $ V2V通信中信道传输速率 ${d_{i,j}}\left( t \right)$ V2V通信中相对距离 ${t_{i,j}}$ V2V通信中车辆${V_i}$在车辆${V_j}$覆盖范围内的可持续时延 $ {\overline R _{i,j}} $ V2V通信中平均传输速率 算法1 选择合适邻近车辆算法 输入:任务型车辆${V_i}$的相关数据参数,服务型车辆${V_j}$的相关数据
参数输出:车辆${V_i}$的合适邻近车辆${V_{i,j}}$ (1) for ${V_i}\left( {i \in \left\{ {1,2, \cdots, n} \right\} } \right)$ do (2) 初始化:候选服务型车辆集合${\varGamma _{ {V_k} } } = \varnothing$ (3) for ${V_j}\left( {j \in \left\{ {1,2, \cdots, m} \right\} } \right)$ do (4) 根据$ l_i^0 $和$ l_j^0 $计算${V_i}$与${V_j}$两车之间的距离:
$ {\text{le}}{{\text{n}}_{i,j}} = \left| {l_i^0 - l_j^0} \right| $(5) if ${\text{le} }{ {\text{n} }_{i,j} } \le {r_{i,j} }$ (6) ${\varGamma _{ {V_k} } } = {\varGamma _{ {V_k} } } + {V_j}$ (7) end if (8) end for (9) for ${V_k} \in {\varGamma _{ {V_k} } }$ do (10) 初始化:候选车辆计算时延集合${\varPhi _T} = \varnothing$ (11) 从分配决策变量比例算法获取变量$ \gamma _i^1 $ (12) 通过式(5)计算出候选车辆计算时延$ {T_{i,k}} $ (13) ${\varPhi _T} = {\varPhi _T} + {T_{i,k} }$ (14) end for (15) ${V_{i,j} } = \min \left( { {\varPhi _T},{V_k} \in {\varGamma _{ {V_k} } } } \right)$ (16) return ${V_{i,j}}$ (17) end for 算法2 卸载算法 输入:任务型车辆$ {V_i} $的相关数据参数,路边单元RSU的相关数据
参数,合适邻近车辆${V_{i,j}}$,卸载决策变量$ {\alpha _i} $,$ {\beta _i} $,$ {\gamma _i} $,标志位
$ {\text{fla}}{{\text{g}}_i} $输出:总计算时延T (1) 初始化:$ T = 0 $ (2) for ${V_i}\left( {i \in \left\{ {1,2, \cdots, n} \right\} } \right)$ do (3) 从分配决策变量比例算法中获取变量$ {\alpha _i} $ (4) 通过式(1)计算本地计算时延$ t_i^{{\text{loc}}} $ (5) 从分配决策变量比例算法中获取变量$ {\beta _i} $ (6) 通过式(2)、式(4)计算RSU传输时延$t_{i,{\text{RSU} } }^{{\text{trans} } }$和执行时延
$ t_{i,{\text{RSU}}}^{{\text{cal}}} $(7) 从分配决策变量比例算法中获取变量$ {\text{fla}}{{\text{g}}_i} $ (8) if $ {\text{fla}}{{\text{g}}_i} = 0 $ (9) 等待时延$ t_{i,{\text{RSU}}}^{{\text{wait}}} = 0 $ (10) 通过式(8)计算RSU计算时延$T_{i,{\text{RSU}}}^{{\text{V2I}}}$ (11) else if $ {\text{fla}}{{\text{g}}_i} = 1 $ (12) 通过式(7)计算等待时延$ t_{i,{\text{RSU}}}^{{\text{wait}}} $ (13) 通过式(8)计算RSU计算时延$T_{i,{\text{RSU}}}^{{\text{V2I}}}$ (14) end if (15) if $T_{i,{\text{RSU} } }^{ {\text{V2I} } } \le {t_{i,{\text{RSU} } } }$ do (16) 处理完的结果直接发送给车辆$ {V_i} $ (17) else (18) 处理完的结果传输到离$ {V_i} $最近的RSU服务器,然后
RSU传输给$ {V_i} $(19) end if (20) 从分配决策变量比例算法中获取变量$ {\gamma _i} $ (21) 从算法2中获取变量$ {V_{i,j}} $ (22) 计算出V2V通信的平均传输速率$ {\overline R _{i,j}} $ (23) 通过式(9)、式(11)、式(14)计算出临近车辆计算时延$ T_{i,j}^{{\text{V2V}}} $ (24) 计算车辆$ {V_i} $、车辆$ {V_{i,j}} $的当前位置$ l_i^1 $,$ l_j^1 $ (25) if $ \left| {l_i^1 - l_j^1} \right| \leqslant {r_{i,j}} $ do (26) 处理完的结果直接发送给车辆 (27) else (28) 处理完的数据先传输到RSU服务器,再由RSU服务器转
送到车辆$ {V_i} $(29) $ {T_i} = \max \left( {t_i^{{\text{loc}}},T_{i,{\text{RSU}}}^{{\text{V2I}}},T_{i,j}^{{\text{V2V}}}} \right) $ (30) $ T = T + {T_i} $ (31) end for (32) return T -
[1] FENG Cheng and JING Weipeng. Deadline-constrained data aggregation scheduling in urban vehicular networks[C]. 19th Annual IEEE International Conference on e-Health Networking, Applications and Services (Healthcom), Dalian, China, 2017: 1–5. [2] MAO Yuyi, ZHANG Jun, and LETAIEF K B. Joint task offloading scheduling and transmit power allocation for mobile-edge computing systems[C]. IEEE Wireless Communications and Networking Conference (WCNC), San Francisco, USA, 2017: 1–6. [3] LIU Yongnan, GUAN Xin, PENG Yu, et al. Blockchain-based task offloading for edge computing on low-quality data via distributed learning in the internet of energy[J]. IEEE Journal on Selected Areas in Communications, 2022, 40(2): 657–676. doi: 10.1109/JSAC.2021.3118417 [4] DAI Yueyue, XU Du, MAHARJAN S, et al. Joint computation offloading and user association in multi-task mobile edge computing[J]. IEEE Transactions on Vehicular Technology, 2018, 67(12): 12313–12325. doi: 10.1109/TVT.2018.2876804 [5] HUANG C M, CHIANG M S, DAO D T, et al. V2V data offloading for cellular network based on the software defined network (SDN) inside mobile edge computing (MEC) architecture[J]. IEEE Access, 2018, 6: 17741–17755. doi: 10.1109/ACCESS.2018.2820679 [6] HOU Xueshi, LI Yong, CHEN Min, et al. Vehicular fog computing: A viewpoint of vehicles as the infrastructures[J]. IEEE Transactions on Vehicular Technology, 2016, 65(6): 3860–3873. doi: 10.1109/TVT.2016.2532863 [7] LIU Pengju, LI Junluo, and SUN Zhongwei. Matching-based task offloading for vehicular edge computing[J]. IEEE Access, 2019, 7: 27628–27640. doi: 10.1109/ACCESS.2019.2896000 [8] YANG Chao, LIU Yi, CHEN Xin, et al. Efficient mobility-aware task offloading for vehicular edge computing networks[J]. IEEE Access, 2019, 7: 26652–26664. doi: 10.1109/ACCESS.2019.2900530 [9] ZHANG Yifan, QIN Xiaoqi, and SONG Xianxin. Mobility-aware cooperative task offloading and resource allocation in vehicular edge computing[C]. IEEE Wireless Communications and Networking Conference Workshops, Seoul, Korea (South), 2020: 1–6. [10] 王寒松. 车联网中基于MEC的计算任务卸载策略研究[D]. [硕士论文], 北京邮电大学, 2019.WANG Hansong. Research of computing offloading scheme for MEC-enabled vehicular networks[D]. [Master dissertation], Beijing University of Posts and Telecommunications, 2019. [11] ZHAO Junhui, DONG Peiyang, MA Xiaoting, et al. Mobile-aware and relay-assisted partial offloading scheme based on parked vehicles in B5G vehicular networks[J]. Physical Communication, 2020, 42: 101163. doi: 10.1016/j.phycom.2020.101163 [12] LI Xin, DANG Yifan, AAZAM M, et al. Energy-efficient computation offloading in vehicular edge cloud computing[J]. IEEE Access, 2020, 8: 37632–37644. doi: 10.1109/ACCESS.2020.2975310 [13] LIU Yujiong, WANG Shangguang, ZHAO Qinglin, et al. Dependency-aware task scheduling in vehicular edge computing[J]. IEEE Internet of Things Journal, 2020, 7(6): 4961–4971. doi: 10.1109/JIOT.2020.2972041 [14] XIAO Zhu, DAI Xingxia, JIANG Hongbo, et al. Vehicular task offloading via heat-aware MEC cooperation using game-theoretic method[J]. IEEE Internet of Things Journal, 2020, 7(3): 2038–2052. doi: 10.1109/JIOT.2019.2960631 [15] LUO Quyuan, LI Changle, LUAN T H, et al. Self-learning based computation offloading for internet of vehicles: Model and algorithm[J]. IEEE Transactions on Wireless Communications, 2021, 20(9): 5913–5925. doi: 10.1109/TWC.2021.3071248 [16] LI Haotian, LI Xujie, ZHANG Mingyue, et al. Multicast-oriented task offloading for vehicle edge computing[J]. IEEE Access, 2020, 8: 187373–187383. doi: 10.1109/ACCESS.2020.3030943 [17] WANG Yanting, SHENG Min, WANG Xijun, et al. Mobile-edge computing: Partial computation offloading using dynamic voltage scaling[J]. IEEE Transactions on Communications, 2016, 64(10): 4268–4282. doi: 10.1109/TCOMM.2016.2599530 [18] REN Jinke, YU Guanding, CAI Yunlong, et al. Partial offloading for latency minimization in mobile-edge computing[C]. GLOBECOM 2017 - 2017 IEEE Global Communications Conference, Singapore, 2017: 1–6.