基于有限资源提升网络可生存性的拓扑重构方法

李黎; 郑庆华; 管晓宏

doi:10.7498/aps.63.170201

摘要

给定网络拓扑结构和有限添加边资源，如何优化配置添加边使重构后的网络拓扑结构具有最优可生存性是非常有价值的研究问题. 本文首先明确网络可生存性的量化评估指标，以移除节点后网络结构的鲁棒性和有效性为优化目标，提出网络拓扑重构优化问题的建模与分析方法. 同时在给定资源代价的约束下，为实现添加边资源配置效率的最大化，提出优先配置节点加强保护圈的启发式算法. 仿真实验表明，该算法在有限资源约束的随机局部故障和选择性攻击环境中，能兼顾改善网络鲁棒性和传输效率，有效提升网络结构的可生存性.

关键词:

Abstract

For an existing network and in limited link addition resources, it is a valuable task to determine optimally the new link resources such that the resulting network is the most robust and efficient. In this paper, we investigate the modeling and analysing of network topological reconfiguration optimization with limited link addition (NTRLA). The network survivability metric is proposed to quantitatively characterize the robustness and efficiency of a network. To approximately solve the NTRLA problem, a heuristic algorithm based on the preferential configuration of enhanced node-protecting cycles (PCNC) is proposed. Simulation results show that the PCNC method can effectively improve the network robustness and communication efficiency at the cost of the least added link resources under either random or targeted attack.

Keywords:

robust connectivity and communication efficiency /
network topology reconfiguration /
limited resource configuration /
optimization model

作者及机构信息

1.
西安交通大学电信学院, 智能网络与网络安全教育部重点实验室, 西安 710049;

2.
陕西师范大学计算机科学学院, 西安 710062

基金项目: 国家自然科学基金（批准号：61303092，61221063，61173112，61173190）、教育部创新团队发展计划（批准号：IRT13035）﹑陕西省自然基础研究（批准号：2014JQ8305）和中央高校基本科研业务费专项资金（批准号：GK201401002）资助的课题.

Authors and contacts

1.
Key Laboratory for Intelligent Network and Network Security of Ministry of Education, Xi'an Jiaotong University, Xi'an 710049, China;

2.
School of Computer Science and Technology, Shaanxi Normal University, Xi'an 710062, China

Funds: Project supported by the National Natural Science Foundation of China (Grant Nos. 61303092, 61221063, 61173112, 61173190), the Innovative Research Team in University of Ministry of Education of China (Grant No. IRT13035), the Natutal Science Foundation of Shaanxi Province of China (Grand No. 2014JQ8305), and the Fundamental Research Funds for the Central Universities of Ministry of Education of China (Grant No.GK201401002).

参考文献

[1]	Albert R, Jeong H, Barabasi A L 2000 Nature 406 378
[2]	Beygelzimer A, Grinstein G, Linsker R, Rish I 2005 Physica A 357 593
[3]
[4]
[5]	Zhao J C, Xu K 2009 Phys. A: Math. Theor. 42 195003
[6]	Sekiyama K, Araki H 2007 Proceedings of the 2nd International Workshop on Self-Organizing System (IWSOS 2007) The Lake District, UK, September 11-13, 2007 p119
[7]
[8]
[9]	Wang H J, Mieghem P V 2008 Proceedings of the 3rd International Conference on Bio-Inspired Models of Network, Information, and Computing Systems (Bionetics 2008) Hyogo, Japan, November 25-28, 2008
[10]
[11]	Martinez M C S 2009 Ph. D. Dissertation (Delft, Delft University of Technology)
[12]
[13]	Li L, Jia Q S, Guan X H, Wang H T 2012 KSⅡ T Internet Info 6 1333
[14]
[15]	Wang H T, Zhao Q C, Jia Q S, Guan X H, Li L 2013 IEEE Trans. on Wireless Communications 12 4518
[16]	Huang W, Chow T W S 2010 Chaos 20 033123
[17]
[18]	Zhang G Q, Wang D, Li G 2007 Phys. Rev. E 76 017101
[19]
[20]	Zhang G Q, Cheng S Q 2012 Sci. Sin. Infom. 42 149 (in Chinese)[张国清, 程苏琦 2012 中国科学 42 149]
[21]
[22]	Cai J, Yu S Z 2013 Acta Phys. Sin. 62 058901 (in Chinese)[蔡君余顺争 2013 62 058901]
[23]
[24]	Schoone A A, Bodlaeder H L, Leeuwen J V 1987 Journal of Graph Theory 11 409
[25]
[26]
[27]	Kiaei M S, Assi C, Jaumard B 2009 IEEE Communications Survey {m Tutorials 11 53
[28]	Zhou X, Zhang F M, Zhou W P, Zou W P, Yang F 2012 Acta Phys. Sin. 61 190201 (in Chinese)[周漩, 张凤鸣, 周卫平, 邹伟, 杨帆 2012 61 190201]
[29]
[30]
[31]	Yu X, Li Y H, Zheng X P, Zhang H Y, Guo Y L 2008 J Tsinghua Univ (Sci Tech) 48 541 (in Chinese)[余新, 李艳和, 郑小平, 张汉一, 郭奕理2008 清华大学学报(自然科学版) 48 541]
[32]
[33]	Holme P, Saramaki J 2012 Phys. Rep. 519 97
[34]	Liu J G, Ren Z M, Guo Q, Wang P H 2013 Acta Phys. Sin. 62 178901 (in Chinese)[刘建国, 任卓明, 郭强, 汪秉宏 2013 62 178901]
[35]
[36]
[37]	Ren Z M, Shao F, Liu J G, Guo Q, Wang P H 2013 Acta Phys. Sin. 62 128901 (in Chinese)[任卓明, 邵凤, 刘建国, 郭强, 汪秉宏 2013 62 128901]
[38]
[39]	Hu Q C, Yin Y S, Ma P F, G Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese)[胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 62 140101]
[40]
[41]	Zhang D Y, Hu M Z, Zhang H L 2006 Journal on Communications 27 74 (in Chinese)[张冬艳, 胡铭曾, 张宏莉 2006 通信学报 27 74]

施引文献

[1]	Albert R, Jeong H, Barabasi A L 2000 Nature 406 378
[2]	Beygelzimer A, Grinstein G, Linsker R, Rish I 2005 Physica A 357 593
[3]
[4]
[5]	Zhao J C, Xu K 2009 Phys. A: Math. Theor. 42 195003
[6]	Sekiyama K, Araki H 2007 Proceedings of the 2nd International Workshop on Self-Organizing System (IWSOS 2007) The Lake District, UK, September 11-13, 2007 p119
[7]
[8]
[9]	Wang H J, Mieghem P V 2008 Proceedings of the 3rd International Conference on Bio-Inspired Models of Network, Information, and Computing Systems (Bionetics 2008) Hyogo, Japan, November 25-28, 2008
[10]
[11]	Martinez M C S 2009 Ph. D. Dissertation (Delft, Delft University of Technology)
[12]
[13]	Li L, Jia Q S, Guan X H, Wang H T 2012 KSⅡ T Internet Info 6 1333
[14]
[15]	Wang H T, Zhao Q C, Jia Q S, Guan X H, Li L 2013 IEEE Trans. on Wireless Communications 12 4518
[16]	Huang W, Chow T W S 2010 Chaos 20 033123
[17]
[18]	Zhang G Q, Wang D, Li G 2007 Phys. Rev. E 76 017101
[19]
[20]	Zhang G Q, Cheng S Q 2012 Sci. Sin. Infom. 42 149 (in Chinese)[张国清, 程苏琦 2012 中国科学 42 149]
[21]
[22]	Cai J, Yu S Z 2013 Acta Phys. Sin. 62 058901 (in Chinese)[蔡君余顺争 2013 62 058901]
[23]
[24]	Schoone A A, Bodlaeder H L, Leeuwen J V 1987 Journal of Graph Theory 11 409
[25]
[26]
[27]	Kiaei M S, Assi C, Jaumard B 2009 IEEE Communications Survey {m Tutorials 11 53
[28]	Zhou X, Zhang F M, Zhou W P, Zou W P, Yang F 2012 Acta Phys. Sin. 61 190201 (in Chinese)[周漩, 张凤鸣, 周卫平, 邹伟, 杨帆 2012 61 190201]
[29]
[30]
[31]	Yu X, Li Y H, Zheng X P, Zhang H Y, Guo Y L 2008 J Tsinghua Univ (Sci Tech) 48 541 (in Chinese)[余新, 李艳和, 郑小平, 张汉一, 郭奕理2008 清华大学学报(自然科学版) 48 541]
[32]
[33]	Holme P, Saramaki J 2012 Phys. Rep. 519 97
[34]	Liu J G, Ren Z M, Guo Q, Wang P H 2013 Acta Phys. Sin. 62 178901 (in Chinese)[刘建国, 任卓明, 郭强, 汪秉宏 2013 62 178901]
[35]
[36]
[37]	Ren Z M, Shao F, Liu J G, Guo Q, Wang P H 2013 Acta Phys. Sin. 62 128901 (in Chinese)[任卓明, 邵凤, 刘建国, 郭强, 汪秉宏 2013 62 128901]
[38]
[39]	Hu Q C, Yin Y S, Ma P F, G Y, Zhang Y, Xing C X 2013 Acta Phys. Sin. 62 140101 (in Chinese)[胡庆成, 尹龑燊, 马鹏斐, 高旸, 张勇, 邢春晓 2013 62 140101]
[40]
[41]	Zhang D Y, Hu M Z, Zhang H L 2006 Journal on Communications 27 74 (in Chinese)[张冬艳, 胡铭曾, 张宏莉 2006 通信学报 27 74]

[1]	朱佳莉, 曹原, 张春辉, 王琴. 实用化量子密钥分发光网络中的资源优化配置. , 2023, 72(2): 020301. doi: 10.7498/aps.72.20221661
[2]	韩伟涛, 伊鹏, 马海龙, 张鹏, 田乐. 异质弱相依网络鲁棒性研究. , 2019, 68(18): 186401. doi: 10.7498/aps.68.20190761
[3]	李涛, 关宏志, 梁科科. 有限理性视野下网络交通流逐日演化规律研究. , 2016, 65(15): 150502. doi: 10.7498/aps.65.150502
[4]	韩忠明, 陈炎, 李梦琪, 刘雯, 杨伟杰. 一种有效的基于三角结构的复杂网络节点影响力度量模型. , 2016, 65(16): 168901. doi: 10.7498/aps.65.168901
[5]	陈世明, 吕辉, 徐青刚, 许云飞, 赖强. 基于度的正/负相关相依网络模型及其鲁棒性研究. , 2015, 64(4): 048902. doi: 10.7498/aps.64.048902
[6]	陈世明, 邹小群, 吕辉, 徐青刚. 面向级联失效的相依网络鲁棒性研究. , 2014, 63(2): 028902. doi: 10.7498/aps.63.028902
[7]	圣宗强, 舒良萍, 孟影, 胡继刚, 钱建发. 有效液滴模型对超铅区结团放射性的研究. , 2014, 63(16): 162302. doi: 10.7498/aps.63.162302
[8]	周漩, 张凤鸣, 周卫平, 邹伟, 杨帆. 利用节点效率评估复杂网络功能鲁棒性. , 2012, 61(19): 190201. doi: 10.7498/aps.61.190201
[9]	周婷婷, 金宁德, 高忠科, 罗跃斌. 基于有限穿越可视图的时间序列网络模型. , 2012, 61(3): 030506. doi: 10.7498/aps.61.030506
[10]	霍雅静, 李军刚. 利用因式化纠缠模拟纠缠动力学行为的有效性研究. , 2012, 61(21): 210304. doi: 10.7498/aps.61.210304
[11]	郝大鹏, 唐刚, 夏辉, 韩奎, 寻之朋. 含遮蔽抛射沉积模型的有限尺寸效应. , 2011, 60(3): 038102. doi: 10.7498/aps.60.038102
[12]	赵丽霞, 张鹤鸣, 胡辉勇, 戴显英, 宣荣喜. 应变Si电子电导有效质量模型. , 2010, 59(9): 6545-6548. doi: 10.7498/aps.59.6545
[13]	曾高荣, 裘正定. 数字水印的鲁棒性评测模型. , 2010, 59(8): 5870-5879. doi: 10.7498/aps.59.5870
[14]	杨鹏飞, 白晋涛, 杨小鹏. 有限厚无限大平板超导体模型场分布的严格解. , 2007, 56(9): 5033-5036. doi: 10.7498/aps.56.5033
[15]	余学才, 叶玉堂, 程琳. 势阱中玻色-爱因斯坦凝聚气体的势场有效性和粒子数极限判据. , 2006, 55(2): 551-554. doi: 10.7498/aps.55.551
[16]	段鹤, 陈效双, 孙立忠, 周孝好, 陆卫. 闪锌矿结构CdTe和ZnTe能带结构和有效质量的第一性原理计算. , 2005, 54(11): 5293-5300. doi: 10.7498/aps.54.5293
[17]	张晓明, 彭建华, 张入元. 利用线性可逆变换增强延迟反馈方法控制混沌的有效性. , 2005, 54(7): 3019-3026. doi: 10.7498/aps.54.3019
[18]	史庆藩, 李粮生, 张　梅. “禁忌”3-磁振子相互作用哈密顿项的有效性分析. , 2004, 53(11): 3916-3919. doi: 10.7498/aps.53.3916
[19]	谢彦波, 汪秉宏, 全宏俊, 杨伟松, 王卫宁. EZ模型中的有限尺寸效应. , 2003, 52(10): 2399-2403. doi: 10.7498/aps.52.2399
[20]	张耀中. 手征QCD2模型的有效拉氏量和质量生成. , 1987, 36(11): 1513-1518. doi: 10.7498/aps.36.1513

计量

文章访问数: 6384
PDF下载量: 736
被引次数: 0

姓名
邮箱
手机号码
标题
留言内容
验证码

搜索

留言板