面向停驻车辆辅助边缘计算的服务可靠增强算法

doi:10.12052/gdutxb.230104

摘要/Abstract

摘要： 停驻车辆辅助边缘计算(Parked Vehicle Assisted Edge Computing, PVEC) 可充分利用停驻车辆闲置资源，有效缓解车载边缘计算中的资源供需矛盾。然而，因停车行为具有不确定性，车主可突然中止车辆对外提供的计算服务。这将增大用户获取可靠计算服务的难度。为此，本文提出一个面向PVEC的服务可靠增强问题，并引入任务复制技术，将该问题转化为任务副本卸载问题，目标是最小化任务副本的平均服务时延。同时，证明了该问题的NP难解性。为求解问题，提出一种贪婪算法(Greedy Algorithm, GA)，优先为具有较大数据量的任务选取一组服务时延最小且满足其服务可靠需求的停驻车辆。此外，还提出一种增强遗传算法(Enhanced Genetic Algorithm, EGA)，以进一步优化算法GA的解。实验结果表明，针对用户服务可靠需求变化的情形，与现有的冗余最小化算法及非任务复制算法相比，算法EGA和GA有效降低了任务副本的平均服务时延。

关键词: 停驻车辆辅助边缘计算, 服务可靠增强, 任务复制, 任务副本卸载

Abstract: Parked vehicle assisted edge computing (PVEC) is effective to alleviate the imbalance between supply and demand of resources in vehicular edge computing, by utilizing the idle resources in parked vehicles (PVs). However, the computing services provided by the PVs can be abruptly aborted due to uncertain parking behaviours. This makes it hard to meet the requirements of users on service reliability. To address this issue, this paper formulates an optimization problem for service reliability guarantee. Then, a task replication technique is introduced to transform the formulated problem into a replication offloading problem, with the goal of minimizing the average completion time of task replications. The NP-hardness of the formulated problem is proved. A greedy algorithm (GA) is proposed to solve the formulated problem, by carefully offloading the replicas of the tasks with large data sizes to the PVs, which can provide the computing services with service guarantee and short completion time. Meanwhile, an enhanced genetic algorithm (EGA) is proposed to refine the solution generated by the proposed algorithm GA. Experimental results show that the proposed GA and EGA algorithms outperform the baseline algorithms in terms of the average completion time of task replications for different requirements of users on service reliability.

Key words: parked vehicle assisted edge computing, service reliability, task replication, replication offloading

中图分类号:

TP391

陈明秋, 黄家乐, 武继刚. 面向停驻车辆辅助边缘计算的服务可靠增强算法[J]. 广东工业大学学报, 2024, 41(04): 80-88.doi: 10.12052/gdutxb.230104

Chen Ming-qiu, Huang Jia-le, Wu Ji-gang. Algorithms for Service Reliability Guarantee in Parked Vehicle Assisted Edge Computing[J]. Journal of Guangdong University of Technology, 2024, 41(04): 80-88.doi: 10.12052/gdutxb.230104

参考文献

[1] KESHAVAMURTHY P, PATEROMICHELAKIS D, DAHLHAUS D, et al. Edge cloud-enabled radio resource management for cooperative automated driving [J]. IEEE Journal on Selected Areas in Communications, 2020, 38(7): 1515-1530.
[2] WU Y L, WU J G, CHEN L, et al. Fog computing model and efficient algorithms for directional vehicle mobility in vehicular network [J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(5): 2599-2614.
[3] WU Y L, WU J G, CHEN L, et al. Load balance guaranteed vehicle-to-vehicle computation offloading for min-max fairness in VANETs [J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(8): 11994-12013.
[4] WANG X J, NING Z L, GUO S, et al. Imitation learning enabled task scheduling for online vehicular edge computing [J]. IEEE Transactions on Mobile Computing, 2022, 21(2): 598-611.
[5] LITMAN T. Parking management: strategies, evaluation and planning[M]. Victoria, BC, Canada: Victoria Transport Policy Institute, 2006.
[6] HUANG X M, YE D D, YU R, et al. Securing parked vehicle assisted fog computing with blockchain and optimal smart contract design [J]. IEEE/CAA Journal of Automatica Sinica, 2020, 7(2): 426-441.
[7] HUANG X M, YU R, XIE S, et al. Task-container matching game for computation offloading in vehicular edge computing and networks [J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 22(10): 6242-6255.
[8] ZHOU A, WANG S, CHENG B, et al. Cloud service reliability enhancement via virtual machine placement optimization [J]. IEEE Transactions on Services Computing, 2017, 10(6): 902-913.
[9] SILIC M, DELAC G, SRBLJIC S, et al. Prediction of atomic web services reliability for QoS-aware recommendation [J]. IEEE Transactions on Services Computing, 2015, 8(3): 425-438.
[10] DONGARRA J, JEANNOT E, SAULE E, et al. Bi-objective scheduling algorithms for optimizing makespan and reliability on heterogeneous systems[C]// ACM Symposium on Parallel Algorithms and Architectures. San Diego: ACM, 2007: 280-288.
[11] CHEN L, XU J. Task replication for vehicular cloud: contextual combinatorial bandit with delayed feedback[C]// IEEE Conference on Computer Communications. Paris: IEEE, 2019: 748-756.
[12] SUN Y, ZHOU S, NIU Z. Distributed task replication for vehicular edge computing: performance analysis and learning-based algorithm [J]. IEEE Transactions on Wireless Communications, 2021, 20(2): 1138-1151.
[13] ZHOU Z Y, LIU P J, FENG J H, et al. Computation resource allocation and task assignment optimization in vehicular fog computing: a contract-matching approach [J]. IEEE Transactions on Vehicular Technology, 2019, 68(4): 3113-3125.
[14] PHAM X Q, HUYNH T, HUH E, et al. Partial computation offloading in parked vehicle-assisted multi-access edge computing: a game-theoretic approach [J]. IEEE Transactions on Vehicular Technology, 2022, 71(9): 10220-10225.
[15] HUANG X M, LI P, YU R. Social welfare maximization in container-based task scheduling for parked vehicle edge computing [J]. IEEE Communications Letters, 2019, 23(8): 1347-1351.
[16] AHMED J K, JABER I N. Proactive load balancing mechanism for fog computing supported by parked vehicles in IoV-SDN [J]. China Communications, 2021, 18(2): 271-289.
[17] HUANG X, LI P, YU R, et al. Fedparking: a federated learning based parking space estimation with parked vehicle assisted edge computing [J]. IEEE Transactions on Vehicular Technology, 2021, 70(9): 9355-9368.
[18] LI C, WANG Y, TANG H, et al. Flexible replica placement for enhancing the availability in edge computing environment [J]. Computer Communications, 2019, 146: 1-14.
[19] SHAO Y L, LI C L, FU Z, et al. Cost-effective replication management and scheduling in edge computing [J]. Journal of Network and Computer Applications, 2019, 129: 46-61.
[20] LI C, WANG Y, TANG H, et al. Dynamic multi-objective optimized replica placement and migration strategies for SaaS applications in edge cloud [J]. Future Generation Computer Systems, 2019, 100: 921-937.
[21] LI C, SONG M, ZHANG M, et al. Effective replica management for improving reliability and availability in edge-cloud computing environment [J]. Journal of Parallel and Distributed Computing, 2020, 143: 107-128.
[22] TAO M, OTA K, DONG M. DSARP: dependable scheduling with active replica placement for workflow applications in cloud computing [J]. IEEE Transactions on Cloud Computing, 2020, 8(4): 1069-1078.
[23] WU Y L, WU J G, CHEN L, et al. Efficient task scheduling for servers with dynamic states in vehicular edge computing [J]. Computer Communications, 2020, 150: 245-253.
[24] KELLERER H, PFERSCHY U, PISINGER D. Knapsack problems[M]. Berlin: Springer, 2004.
[25] ACT Government Open Data Portal dataACT, Smart parking lots[EB/OL]. (2017-07-28) [2023-05-25]. https://www.data.act.gov.au/Transport/ Smart-Parking-Stays/3vsj-zpk7.
[26] Cambridgeshire Insight Open Data, Cambridge city parking data[EB/OL]. (2019-11-12) [2023-09-18]. https://data.cambridgeshireinsight.org.uk/dataset/cambridge-city-parking-data.
[27] LIU X Y, JIANG J H, LI L. Computation offloading and task scheduling with fault-tolerance for minimizing redundancy in edge computing[C]// IEEE International Symposium on Software Reliability Engineering Workshops. Wuhan: IEEE, 2021: 198-209.

相关文章 15

[1]	谢光强, 万梓坤, 李杨. 基于分层邻域选择的切换拓扑多智能体系统一致性协议[J]. 广东工业大学学报, 2024, 41(04): 44-51.
[2]	陈永锋, 刘劲, 杨志景, 陈锐涵, 谭俊鹏. 基于样本对语义主动挖掘的图文匹配算法[J]. 广东工业大学学报, 2024, 41(04): 89-97.
[3]	罗成, 张军. 基于深度学习的自适应采样及记忆增强压缩感知方法[J]. 广东工业大学学报, 2024, 41(04): 114-121.
[4]	林浩, 陈平华. 基于因子级特征与属性偏好联合学习的会话推荐[J]. 广东工业大学学报, 0, (): 5-0.
[5]	李雪森, 谭北海, 余荣, 薛先斌. 基于YOLOv5的轻量化无人机航拍小目标检测算法[J]. 广东工业大学学报, 2024, 41(03): 71-80.
[6]	曾嘉琪, 吴焯婷, 吴泽楷, 杨振国, 刘文印. 用于文本验证码生成的随机扰动优化网络[J]. 广东工业大学学报, 2024, 41(03): 81-90.
[7]	李卓璋, 许柏炎, 蔡瑞初, 郝志峰. 说话人感知的交叉注意力说话人提取网络[J]. 广东工业大学学报, 2024, 41(03): 91-101.
[8]	郑侠聪, 程良伦, 黄国恒, 王敬超. 嵌入拓扑特征的自然场景文本检测方法[J]. 广东工业大学学报, 2024, 41(03): 102-109.
[9]	熊荣盛, 王帮海, 杨夏宁. 基于蓝图可分离残差蒸馏网络的图像超分辨率重建[J]. 广东工业大学学报, 2024, 41(02): 65-72.
[10]	郭傲, 许柏炎, 蔡瑞初, 郝志峰. 基于时序对齐的风格控制语音合成算法[J]. 广东工业大学学报, 2024, 41(02): 84-92.
[11]	何森柏, 程良伦, 黄国恒, 伍志超, 叶颂航. SR-Det：面向工业场景下细长和旋转目标的鲁棒检测[J]. 广东工业大学学报, 2024, 41(02): 93-100.
[12]	涂泽良, 程良伦, 黄国恒. 基于局部正交特征融合的小样本图像分类[J]. 广东工业大学学报, 2024, 41(02): 73-83.
[13]	陈睿, 蔡念, 罗智浩, 刘璇, 黎剑. 基于多任务循环神经网络带状回归模型的乳腺癌个体生存分析[J]. 广东工业大学学报, 2024, 41(01): 34-40.
[14]	杨镇雄, 谭台哲. 基于生成对抗网络的低光照图像增强算法[J]. 广东工业大学学报, 2024, 41(01): 55-62.
[15]	邝永年, 王丰. 基于前景区域生成对抗网络的视频异常行为检测研究[J]. 广东工业大学学报, 2024, 41(01): 63-68,92.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed