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

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

Abstract

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

CLC Number:

TN92

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.

Figures/Tables 9

参数	含义
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次迭代时的左枝问题阈值

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

RichHTML

PDF

PDF (ENGLISH)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 33

Related Articles 15

Metrics

Recommended 0

[1]	Weifeng LU, Ning LI, Jia XU, Lijie XU, Jian XU. Joint scheduling algorithm for correlative tasks in multi-access edge computing [J]. Journal on Communications, 2023, 44(4): 87-98.
[2]	Xin SUN, Guifu ZHANG, Hongyan XING, Wang Zenghui. Research on intrusion detection for maritime meteorological sensor network based on balancing generative adversarial network [J]. Journal on Communications, 2023, 44(4): 124-136.
[3]	Renchao XIE, Wen WEN, Qinqin TANG, Yunlong LIU, Gaochang XIE, Tao HUANG. Survey on rail transit mobile edge computing network security [J]. Journal on Communications, 2023, 44(4): 201-215.
[4]	Xueyong YU, Lixiang QIU, Jianing SONG, Hongbo ZHU. Security communication and energy efficiency optimization strategy in UAV-aided edge computing [J]. Journal on Communications, 2023, 44(3): 45-54.
[5]	Wei FAN, Cheng PENG, Dali ZHU, Yuqing WANG. Research on intrusion response strategy based on static Bayesian game in mobile edge computing network [J]. Journal on Communications, 2023, 44(2): 70-81.
[6]	Shuxu ZHAO, Ping WEI, Xiaolong WANG. Optimal coalition structure generation strategy in multi-task concurrent edge computing environment [J]. Journal on Communications, 2023, 44(2): 172-184.
[7]	Long LONG, Zichen LIU, Zaiwang LU, Yucheng ZHANG, Lei LI. Joint optimization strategy of service cache and resource allocation in mobile edge network [J]. Journal on Communications, 2023, 44(1): 64-74.
[8]	Yu ZHANG, Min CHENG. Joint optimization of edge computing and caching in NDN [J]. Journal on Communications, 2022, 43(8): 164-175.
[9]	Ziyuan WANG, Ruizhong DU. Certificateless public key cryptography based provable data possession scheme in edge environment [J]. Journal on Communications, 2022, 43(7): 62-72.
[10]	Xiaodong YANG, Tian TIAN, Jiaqi WANG, Meijuan LI, Caifen WANG. Certificateless ciphertext retrieval scheme with multi-user and multi-keyword based on cloud-edge collaboration [J]. Journal on Communications, 2022, 43(5): 144-154.
[11]	Zijia MO, Zhipeng GAO, Yang YANG, Yijing LIN, Shan SUN, Chen ZHAO. Efficient distributed model sharing strategy for data privacy protection in Internet of vehicles [J]. Journal on Communications, 2022, 43(4): 83-94.
[12]	Jifeng WANG, Guofeng WANG. Research on ciphertext search and sharing technology in edge computing mode [J]. Journal on Communications, 2022, 43(4): 227-238.
[13]	Haili SUN, Xiang LONG, Lansheng HAN, Yan HUANG, Qingbo LI. Overview of anomaly detection techniques for industrial Internet of things [J]. Journal on Communications, 2022, 43(3): 196-210.
[14]	Dun CAO, Yingbao ZHANG, Dian ZOU, Jin WANG, Qiang TANG, Baofeng JI. Multi-node cooperative distributed offloading strategy in V2X scenario [J]. Journal on Communications, 2022, 43(2): 185-195.
[15]	Yan SUN, Ao XIONG, Chengling JIANG, Wei WANG, Dongxiao YU, Shaoyong GUO. Blockchain-based computing and wireless communication resource joint management double auction model [J]. Journal on Communications, 2022, 43(11): 14-25.