工业物联网中大规模受损边缘计算网络修复机制

doi:10.11959/j.issn.1000-436x.20211100

通信学报 ›› 2021, Vol. 42 ›› Issue (4): 89-99.doi: 10.11959/j.issn.1000-436x.20211100

所属专题：边缘计算

• 专题：面向未来移动网络的大规模组网关键技术 • 上一篇下一篇

工业物联网中大规模受损边缘计算网络修复机制

田辉¹, 伍浩¹, 田洋¹, 任建阳¹, 崔亚娟¹, 艾文宝², 袁健华²

¹ 北京邮电大学网络与交换技术国家重点实验室，北京 100876
² 北京邮电大学理学院，北京 100876

修回日期:2021-04-08 出版日期:2021-04-25 发布日期:2021-04-01
作者简介:田辉（1963- ），女，河南郑州人，博士，北京邮电大学教授、博士生导师，主要研究方向为无线资源管理、智能边缘计算、移动社交网络。
伍浩（1994- ），男，江西新余人，北京邮电大学博士生，主要研究方向为工业物联网、无线资源管理、网络弹性、移动边缘计算、复杂网络。
田洋（1991- ），男，河南郑州人，北京邮电大学博士生，主要研究方向为大数据环境下的链路预测、复杂网络上的传播动力学等。
任建阳（1997- ），男，北京人，北京邮电大学硕士生，主要研究方向为边缘计算、无线资源管理等。
崔亚娟（1991- ），女，河南平顶山人，北京邮电大学博士生，主要研究方向为无人机网络、车联网、移动自组织网络等。
艾文宝（1962- ），男，江西高安人，博士，北京邮电大学教授、博士生导师，主要研究方向为最优化理论和算法及其应用。
袁健华（1979- ），女，湖南郴州人，博士，北京邮电大学教授、博士生导师，主要研究方向为最优化理论和算法、有限元方法及其工程应用。
基金资助:
国家自然科学基金资助项目(62071068);北京邮电大学优秀博士生创新基金资助项目(CX2019108)

Recovery mechanism of large-scale damaged edge computing network in industrial Internet of things

Hui TIAN¹, Hao WU¹, Yang TIAN¹, Jianyang REN¹, Yajuan CUI¹, Wenbao AI², Jianhua YUAN²

¹ State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China
² School of Sciences, Beijing University of Posts and Telecommunications, Beijing 100876, China

Revised:2021-04-08 Online:2021-04-25 Published:2021-04-01
Supported by:
The National Natural Science Foundation of China(62071068);The BUPT Excellent Ph.D.Students Founda-tion(CX2019108)

摘要/Abstract

摘要：

针对工业物联网中边缘计算网络与其余子网的相互依赖特性所导致的网络大规模级联故障问题，考虑到网络修复初期的资源有限性，提出了一种联合考量计算需求与修复开销的网络修复机制。考虑到受损网络结构（拓扑关系与链路容量）和动态特征（边缘计算节点计算需求），基于节点计算量守恒定理构建了链路修复策略集与网络计算迁移的联合分析框架。基于Benders分解算法，将原NP-hard问题转化为相互依赖的主问题与子问题，通过割平面的不断逼近，实现对原问题最优解在多项式时间内的高效探索。结合局部分支法，进一步保障Benders分解算法的上界在迭代过程中的非增特性，加快算法收敛速度。仿真结果表明，所提算法的系统总开销性能优于传统基于拓扑结构的修复算法，并且可以在多场景下保持其性能优势。

关键词: 工业物联网, 边缘计算, 网络修复, Benders分解算法, 局部分支法

Abstract:

Given the limited resources at early stages for recovery, a failure recovery mechanism of the edge computing network considering both computational demands and repair costs was proposed, which intends to tackle the problem of the high probability of large-scale cascading failure caused by the interdependence between the edge computing network and other subnetworks in industrial Internet of things (IIoT).Considering the network structure (topology and link capacity) and network dynamics (computational demands), a joint link recovery selection and computation migration optimization problem was formulated under the conservation of node computing requirements.By leveraging the Benders decomposition algorithm, the NP-hard problem was transformed into a main problem and a sub-problem, which were interdependent and could be solved in polynomial time through the approximation of cutting planes.A local branching method was further introduced to guarantee the non-increasing nature of the Benders upper bound, thus accelerating the convergence of Benders decomposition.Simulation results demonstrate that the proposed algorithm outperforms the conventional topology-based recovery algorithm in system utility, and can perform well in multiple scenarios.

Key words: industrial Internet of things, edge computing, network recovery, Benders decomposition algorithm, local branching

中图分类号:

TN92

田辉, 伍浩, 田洋, 任建阳, 崔亚娟, 艾文宝, 袁健华. 工业物联网中大规模受损边缘计算网络修复机制[J]. 通信学报, 2021, 42(4): 89-99.

Hui TIAN, Hao WU, Yang TIAN, Jianyang REN, Yajuan CUI, Wenbao AI, Jianhua YUAN. Recovery mechanism of large-scale damaged edge computing network in industrial Internet of things[J]. Journal on Communications, 2021, 42(4): 89-99.

图/表 9

表1

系统参数"

参数	含义
N	边缘计算网络节点数量
Ε	边缘计算网络所有链路集合
Ε⁰	边缘计算网络所有受损链路集合
Ε¹	边缘计算网络所有正常链路集合
q	受损链路占所有链路的百分比
c _ij	链路ij 的修复成本
c_i	节点i丢弃每单位数据的代价
p_i	节点i的本地计算数据计算量
$\bar{p_{i}}$	节点i的最大计算能力
r_i	节点i的本地数据计算量需求
d_i	节点i丢弃的计算数据量
f _ij	节点i到节点 j的计算迁移量
$\bar{f_{i j}}$	链路ij 的链路容量
e _ij	是否修复链路ij 的决策变量
t	Benders分解的迭代次数
θ^t	子问题在第t次迭代中的目标函数的最优值
Δ^t	第t次迭代时的左枝问题阈值

表1

图1

图2

图3

图4

图5

图6

图7

图8

参考文献 33

[1]	WU H , TIAN H , NIE G F ,et al. Wireless powered mobile edge computing for industrial Internet of Things systems[J]. IEEE Access, 2020,8: 101539-101549.
[2]	XIE G Q , YANG K H , XU C ,et al. Digital twinning based adaptive development environment for automotive cyber-physical systems[J]. IEEE Transactions on Industrial Informatics, 2021,PP(99): 1.
[3]	WU H , LYU X C , TIAN H . Online optimization of wireless powered mobile-edge computing for heterogeneous industrial Internet of things[J]. IEEE Internet of Things Journal, 2019,6(6): 9880-9892.
[4]	XING L D . Cascading failures in Internet of things:review and perspectives on reliability and resilience[J]. IEEE Internet of Things Journal, 2021,8(1): 44-64.
[5]	PROKHORENKO V , ALI BABAR M . Architectural resilience in cloud,fog and edge systems:a survey[J]. IEEE Access, 2020,8: 28078-28095.
[6]	AYOUBI S , ASSI C , CHEN Y H ,et al. Restoration methods for cloud multicast virtual networks[J]. Journal of Network and Computer Applications, 2017,78: 180-190.
[7]	SATRIA D , PARK D , JO M . Recovery for overloaded mobile edge computing[J]. Future Generation Computer Systems, 2017,70: 138-147.
[8]	TENG R , LI H B , MIURA R . Dynamic recovery of wireless multi-hop infrastructure with the autonomous mobile base station[J]. IEEE Access, 2016,4: 627-638.
[9]	LI P D , YANG X F . On dynamic recovery of cloud storage system under advanced persistent threats[J]. IEEE Access, 2019,7: 103556-103569.
[10]	BAXTER G J , TIMáR G , MENDES J F F . Targeted damage to interdependent networks[J]. Physical Review E, 2018,98(3): 032307.
[11]	BRUMMITT C D , D'SOUZA R M , LEICHT E A . Suppressing cascades of load in interdependent networks[J]. Proceedings of the National Academy of Sciences, 2012,109(12): 680-689.
[12]	MORONE F , MAKSE H A . Influence maximization in complex networks through optimal percolation[J]. Nature, 2015,524(7563): 65-68.
[13]	RUDNICK H , MOCARQUER S , ANDRADE E ,et al. Disaster management[J]. IEEE Power and Energy Magazine, 2011,9(2): 37-45.
[14]	PUNZO G , TEWARI A , BUTANS E ,et al. Engineering resilient complex systems:the necessary shift toward complexity science[J]. IEEE Systems Journal, 2020,14(3): 3865-3874.
[15]	WU H , TIAN H , FAN S S ,et al. Data age aware scheduling for wireless powered mobile-edge computing in industrial Internet of things[J]. IEEE Transactions on Industrial Informatics, 2021,17(1): 398-408.
[16]	SMITH A M , PóSFAI M , ROHDEN M ,et al. Competitive percolation strategies for network recovery[J]. Scientific Reports, 2019,9: 11843.
[17]	QIN J , MIAO L X . Combined simulated annealing algorithm for logistics network design problem[C]// 2009 International Workshop on Intelligent Systems and Applications. Piscataway:IEEE Press, 2009: 1-4.
[18]	KHELIFI M , SAIDI M Y , BOUDJIT S . Genetic algorithm based model for capacitated network design problem[C]// 2016 24th International Conference on Software,Telecommunications and Computer Networks. Piscataway:IEEE Press, 2016: 1-6.
[19]	LIAN H B . Network design problems,formulations and solutions[D]. Richardson:The University of Texas at Dallas, 2012.
[20]	LI D Q , ZHANG Q , ZIO E ,et al. Network reliability analysis based on percolation theory[J]. Reliability Engineering ＆ System Safety, 2015,142: 556-562.
[21]	LYU X C , REN C S , NI W ,et al. Distributed optimization of collaborative regions in large-scale inhomogeneous fog computing[J]. IEEE Journal on Selected Areas in Communications, 2018,36(3): 574-586.
[22]	ZHAO P T , TIAN H , QIN C ,et al. Energy-saving offloading by jointly allocating radio and computational resources for mobile edge computing[J]. IEEE Access, 2017,5: 11255-11268.
[23]	ZHAO P T , TIAN H , CHEN K C ,et al. Context-aware TDD configuration and resource allocation for mobile edge computing[J]. IEEE Transactions on Communications, 2020,68(2): 1118-1131.
[24]	CODATO G , FISCHETTI M . Combinatorial Benders' cuts for mixedinteger linear programming[J]. Operations Research, 2006,54(4): 756-766.
[25]	RAHMANIANI R , CRAINIC T G , GENDREAU M ,et al. The Benders decomposition algorithm:a literature review[J]. European Journal of Operational Research, 2017,259(3): 801-817.
[26]	WU H , TIAN H , NIE G F . Energy-efficient inter-frequency small cell discovery in dense urban environments[J]. IEEE Wireless Communications Letters, 2019,8(1): 41-44.
[27]	F PEREIRA M V , V G PINTO L M , F CUNHA S H ,et al. A decomposition approach to automated generation/transmission expansion planning[J]. IEEE Transactions on Power Apparatus and Systems, 1985,104(11): 3074-3083.
[28]	ERICKSON J . Algorithms[M]. Illinois: Independently Published, 2019.
[29]	OLIVEIRA F , GROSSMANN I E , HAMACHER S . Accelerating Benders stochastic decomposition for the optimization under uncertainty of the petroleum product supply chain[J]. Computers ＆ Operations Research, 2014,49: 47-58.
[30]	运筹学教材编写组. 运筹学:本科版[M]. 第4版.北京: 清华大学出版社, 2013.
	Textbook Compilation Team. Operations research[M]. Beijing: Tsinghua University Press, 2013.
[31]	FISCHETTI M , LODI A . Local branching[J]. Mathematical Programming, 2003,98(1/2/3): 23-47.
[32]	SANTOSO T , AHMED S , GOETSCHALCKX M ,et al. A stochastic programming approach for supply chain network design under uncertainty[J]. European Journal of Operational Research, 2005,167(1): 96-115.
[33]	YU A Q , WANG N , WU N . Scale-free networks:characteristics of the time-variant robustness and vulnerability[J]. IEEE Systems Journal, 2020,PP(99): 1-11.

工业物联网中大规模受损边缘计算网络修复机制

Recovery mechanism of large-scale damaged edge computing network in industrial Internet of things

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 33

相关文章 15

Metrics

推荐阅读 0

[1]	鲁蔚锋, 李宁, 徐佳, 徐力杰, 徐建. 多接入边缘计算中相关性任务的联合调度算法[J]. 通信学报, 2023, 44(4): 87-98.
[2]	苏新, 张桂福, 行鸿彦, Zenghui Wang. 基于平衡生成对抗网络的海洋气象传感网入侵检测研究[J]. 通信学报, 2023, 44(4): 124-136.
[3]	谢人超, 文雯, 唐琴琴, 刘云龙, 谢高畅, 黄韬. 轨道交通移动边缘计算网络安全综述[J]. 通信学报, 2023, 44(4): 201-215.
[4]	余雪勇, 邱礼翔, 宋家宁, 朱洪波. 无人机辅助边缘计算中安全通信与能效优化策略[J]. 通信学报, 2023, 44(3): 45-54.
[5]	范伟, 彭诚, 朱大立, 王雨晴. 移动边缘计算网络下基于静态贝叶斯博弈的入侵响应策略研究[J]. 通信学报, 2023, 44(2): 70-81.
[6]	赵庶旭, 韦萍, 王小龙. 多任务并发边缘计算环境中最优联盟结构生成策略[J]. 通信学报, 2023, 44(2): 172-184.
[7]	龙隆, 刘子辰, 陆在旺, 张玉成, 李蕾. 移动边缘网络下服务缓存与资源分配联合优化策略[J]. 通信学报, 2023, 44(1): 64-74.
[8]	张宇, 程旻. NDN中边缘计算与缓存的联合优化[J]. 通信学报, 2022, 43(8): 164-175.
[9]	王子园, 杜瑞忠. 边缘环境下基于无证书公钥密码的数据完整性审计方案[J]. 通信学报, 2022, 43(7): 62-72.
[10]	杨小东, 田甜, 王嘉琪, 李梅娟, 王彩芬. 基于云边协同的无证书多用户多关键字密文检索方案[J]. 通信学报, 2022, 43(5): 144-154.
[11]	莫梓嘉, 高志鹏, 杨杨, 林怡静, 孙山, 赵晨. 面向车联网数据隐私保护的高效分布式模型共享策略[J]. 通信学报, 2022, 43(4): 83-94.
[12]	杨力, 潘成胜, 孔相广, 黄琦龙, 戚耀文. 5G融合卫星网络研究综述[J]. 通信学报, 2022, 43(4): 202-215.
[13]	王继锋, 王国峰. 边缘计算模式下密文搜索与共享技术研究[J]. 通信学报, 2022, 43(4): 227-238.
[14]	孙海丽, 龙翔, 韩兰胜, 黄炎, 李清波. 工业物联网异常检测技术综述[J]. 通信学报, 2022, 43(3): 196-210.
[15]	曹敦, 张应宝, 邹电, 王进, 汤强, 冀保峰. V2X多节点协同分布式卸载策略[J]. 通信学报, 2022, 43(2): 185-195.