带长度约束的k端网络可靠性分析

J4 ›› 2016, Vol. 38 ›› Issue (01): 84-88.

带长度约束的k端网络可靠性分析

宋凤,莫毓昌,潘竹生,钟发荣

（浙江师范大学数理与信息工程学院,浙江金华 321004）

收稿日期:2015-08-17 修回日期:2015-10-24 出版日期:2016-01-25 发布日期:2016-01-25

kterminal network reliability analysis with length constraint

SONG Feng,MO Yuchang,PAN Zhusheng,ZHONG Farong

(College of Mathematics,Physics and Information Engineering,Zhejiang Normal University,Jinhua 321004,China)

Received:2015-08-17 Revised:2015-10-24 Online:2016-01-25 Published:2016-01-25

摘要/Abstract

摘要：

在网络视频和实时通信应用中需要研究带长度约束的k端网络可靠性分析问题,即任意两端点之间在给定时间延迟D约束内的k端网络可靠性。对带长度约束的k端网络可靠性问题进行了研究，主要是在传统不带路径约束的双端和k端网络可靠性研究基础上，提出了基于截断的路径约束方法；并根据该方法构造二元决策图BDD模型进行带约束的k端网络可靠性分析。该算法针对k端点对点信息流在一定时间延迟下完成传输问题，具有较强的实际意义。实例分析结果验证了本方法的可行性和有效性。

关键词: 长度约束, k端网络, 延迟约束, 网络可靠性

Abstract:

Kterminal network reliability analysis with length constraint has many applications in online video and realtime communications. Basically, we calculate kterminal network reliability under the condition that the length between any terminalpair of kterminals is within a given time delay constraint called D. We study k terminal network reliability with length constraint, and propose a truncationbased path constraint method on the basis of the traditional terminalpair and kterminal network reliability algorithms. We also build a binary decision diagram (BDD) model to analyze kterminal network reliability with constraints. The proposed algorithm has strong practical significance for k terminal pointtopoint information flow to accomplish transmission under a certain time delay. Experimental results validate the feasibility and effectiveness of this method.

Key words: length constraint;kterminal network;delay constraints;network reliability

宋凤,莫毓昌,潘竹生,钟发荣. 带长度约束的k端网络可靠性分析[J]. J4, 2016, 38(01): 84-88.

SONG Feng,MO Yuchang,PAN Zhusheng,ZHONG Farong. kterminal network reliability analysis with length constraint [J]. J4, 2016, 38(01): 84-88.

参考文献［16］

［1］	Jiang Yinan,Li Ruiying,Huang Ning,et al.Survey on network reliability evaluation methods ［J］.Computer Science,2012,39(5):918.(in Chinese)
［2］	Feng Hailin.The study of reliability problems of the network system ［D］.Xi’an:Xidian University,2004.(in Chinese)
［3］	Yeh Fumin,Lu Shyuekung,Kuo Syyen.OBDDbased evaluation of kterminal network reliability ［J］.IEEE Transactions on Reliability,2002,51(4):443451.
［4］	Yeh Fumin,Lu Shyuekung,Kuo Syyen.Determining terminalpair reliability based on edge expansion diagrams using OBDD［J］.IEEE Transactions on Reliability,1999,48(3):234246.
［5］	Louis P.A diameterconstrained network reliability model to determine the probability that a communication network meets delay constraints ［J］.WSEAS Transactions on Communications,2008,7(6):574583.
［6］	Ian C, Oskar S,Brandon W,et al.Freenet:A distributed anonymous information storage and retrieval system［C］∥Proc of International Workshop on Design Issues in Anonymity and Unobservability,2000:2526.
［7］	Hoong Pookuan,Hiroshi M.Pushpull incentivebased P2P live media streaming system ［J］.WSEAS Transactions on Communications,2008,7(2):3342.
［8］	Gopal P,Raghavan R,Eli U.Building lowdiameter peertopeer networks ［J］.IEEE Journal on Selected Areas in Communications,2003,21(6):9951002.
［9］	Masahiro S,Naoki W,Masayuki M.Adaptive and robust P2P media streaming ［J］.WSEAS Transactions on Communications,2005,4(7):425430.
［10］	Lu Yan, Kaisa S, Zhou Xinrong. Peertopeer networking with firewalls ［J］.WSEAS Transactions on Computers,2003,2(3):566571.
［11］	Mo Yuchang.New insights into the BDDbased reliability analysis of phased mission systems［J］.IEEE Transactions on Reliability,2009,58(4):667678.
［12］	Pan Zhusheng,Chen Ronggen,Mo Yuchang.Computing network reliability based on pathfunction and BDD ［J］.Micrlelectronics & Computer,2012,29(12):157162.(in Chinese)
［13］	Gu Tianlong,Xu Zhoubo.Ordered binary decision diagram and its application［M］.Beijing:Science Press,2009:2256.(in Chinese)
［14］	Yang Yi,Pan Zhongliang.A BDDbased method for computing network reliability［J］.Journal of South China Normal University(Natural Science Edition),2004(3):5358.(in Chinese)
［15］	Chen Ronggen,Mo Yuchang,Pan Zhusheng,Isomorphism check in BDDbased network reliability analysis［J］.Advances in Information Sciences and Service Sciences,2013,5(3):562569.
［16］	Sun Yun,Zhong Farong,Mo Yuchang,et al.Computing approximate network reliability based on truncated edge expansion diagram［J］.Computer Science,2015,42(7):122124.(in Chinese)
	附中文参考文献：
［1］	江逸楠,李瑞莹,黄宁,等.网络可靠性评估方法综述［J］.计算机科学,2012,39(5):918.
［2］	冯海林.网络系统中可靠性问题的研究［D］.西安:西安电子科技大学,2004.
［12］	潘竹生,陈荣根,莫毓昌.基于路径函数和BDD的网络可靠度分析［J］.微电子学与计算机,2012,29(12):157162.
［13］	古天龙,徐周波.有序二叉决策图及应用［M］.北京:科学出版社,2009:2256.
［14］	杨意,潘中良.一种用二元判决图求网络可靠度的方法［J］.华南师范大学学报（自然科学版）,2004(3):5358.
［16］	孙云,钟发荣,莫毓昌,等.基于截断边扩展图的网络可靠度近似分析［J］.计算机科学,2015,42(7):122124.