您的位置:山东大学 -> 科技期刊社 -> 《山东大学学报(工学版)》

山东大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (2): 43-48.doi: 10.6040/j.issn.1672-3961.1.2014.011

• 机器学习与数据挖掘 • 上一篇    下一篇

网络可靠性分析中BFS策略与POS策略的性能比较

伍欢, 钟发荣, 莫毓昌, 潘竹生, 曾令国   

  1. 浙江师范大学数理与信息工程学院, 浙江 金华 321004
  • 收稿日期:2014-03-26 修回日期:2015-03-17 出版日期:2015-04-20 发布日期:2014-03-26
  • 通讯作者: 钟发荣(1963-),男,浙江龙游人,教授,博士,主要研究方向为网络可靠性研究,移动进程演算与Web服务组合.E-mail:zfr@zjnu.cn E-mail:zfr@zjnu.cn
  • 作者简介:伍欢(1989-),女,湖南益阳人,硕士研究生,主要研究方向为网络可靠性.E-mail:wuhuan_3892@163.com
  • 基金资助:
    国家自然科学基金资助项目(61272130);浙江省自然科学基金资助项目(Y1100689);浙江省教育厅一般科研资助项目(Y201328072,Y201328293);浙江省计算机软件与理论重中之重学科开放课题资助项目(ZSDZZZZXK24)

Performance comparison between breadth-first ordering and priority ordering in network reliability analysis

WU Huan, ZHONG Farong, MO Yuchang, PAN Zhusheng, ZENG Lingguo   

  1. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
  • Received:2014-03-26 Revised:2015-03-17 Online:2015-04-20 Published:2014-03-26

摘要: 为探究启发式边排序策略性能和网络结构特征的相关性,并建立网络结构特征依赖的边排序策略选择方法,基于4种常用的规则网络对BFS(breadth-first search) 和POS (priority ordering search)两种策略的性能展开研究。通过试验分析比较了4种网络下BFS和POS两种策略的BDD (binary decision diagram)尺度与总体运行时间等性能数据。研究结果表明:在规则网络结构中,不同的排序策略适用于不同的网络结构。在Torus和Square网络中BFS策略优于POS策略;在De Bruijn和Nearest-neighbor网络中POS策略普遍优于BFS策略。该结论为特定网络选取最优或次优启发式边排序策略提供了依据。

关键词: POS, 规则网络, BFS, BDD, 边排序策略

Abstract: In order to explore the correlation between edge ordering heuristics and characteristics of network structure, and to build the method of selecting heuristic relied on network structure, the performances of breadth-first search and priority ordering search were studied based on four kinds of regular network models. Some performance data, such as binary decision diagram size and runtime under two heuristics, were compared emphatically through the experiments. The experimental results showed that different ordering heuristics fitted different network structures: BFS was generally better than POS in the networks of Torus and Square, and POS was generally better than BFS in the De Bruijn and Nearest-neighbor networks. These results could provide reference for choosing the optimal or suboptimal edge ordering heuristic for the particular regular network.

Key words: breadth-first search, edge ordering heuristic, priority ordering search, regular networks, binary decision diagram

中图分类号: 

  • TB114
[1] SHELDON B AKERS. Binary decision diagrams[J]. IEEE Transactions on Computers, 1978, C-27(6):509-516.
[2] RANDAL E BRYANT. Symbolic boolean manipulation with ordered binary-decision diagrams[J]. ACM Computing Surveys, 1992, 24(3):293-318.
[3] RANDAL E BRYANT. Graph-based algorithms for boolean function manipulation[J]. IEEE Transactions on Computers, 1986, C-35(8):677-691.
[4] SIELING D, WEGEBER I. Reduction of OBDDs in linear time[J]. Information Processing Letters, 1993, 48(3):139-144.
[5] GAREY M R, JOHNSON D S. Computers and intractability: a guide to the theory of NP-completeness[M]. San Francisco, USA: WH Freeman & Company, 1979:45-65.
[6] BOLLIG B, WEGENER I. Improving the variable ordering of OBDDs is NP-complete[J]. IEEE Transactions on Computers, 1996, 45(9):993-1002.
[7] STEVEN J FRIEDMAN, KENNETH J SUPOWIT. Finding the optimal variable ordering for binary decision diagrams[J]. IEEE Transactions on Computers, 1990, 39(5):710-713.
[8] BUTLER K M, ROSS D E, KAPUR R, et al. Heuristics to compute variable orderings for efficient manipulation of ordered binary decision diagrams[C]//Proceedings of the 28th ACM/IEEE Design Automation Conference. San Francisco, USA: ACM, 1991: 417-420.
[9] FUJITA M, FUJISAWA H, KAWATO N. Evaluation and improvements of boolean comparison method based on binary decision diagrams[C]//IEEE International Conference on Computer-Aided Design. Santa Clara, USA: IEEE, 1988:2-5.
[10] FUJITA M, MATSUNAGA Y, KAKUDA T. On variable ordering of binary decision diagrams for the application of multi-level logic synthesis[C]//Proceedings of the Conference on European Design Automation. Amsterdam, Holland: IEEE, 1991:50-54.
[11] MERCER M R, KAPUR R, ROSS D E. Functional approaches to generating orderings for efficient symbolic representation[C]//Proceedings of the 29th ACM/IEEE Design Automation Conference. Anaheim, USA: IEEE, 1992:624-627.
[12] BOUISSOU M. An ordering heuristic for building binary decision diagrams from fault-trees[C]//Reliability and Maintainability Symposium, Proceedings of the International Symposium on Product Quality and Integrity. Las Vegas, USA: IEEE, 1996:208-214.
[13] BOUISSOU M, BRUYERE F, RAUZY A. BDD based fault-tree processing: a comparison of variable ordering heuristics[C]//Proceedings of European Safety and Reliability Association Conference. Lisboa, Portuguesa: Elsevier, 1997.
[14] GARY HARDY, CORINNE LUCET, NIKOLAOS LIMNIOS. Computing all-terminal reliability of stochastic networks with binary decision diagrams[C]//Proceedings of the 11th International Symposium on Applied Stochastic Models and Data Analysis. Brest, France: ASMDA, 2005:1468-1474.
[15] GARY HARDY, CORINNE LUCET, NIKOLAOS LIMNIOS. K-terminal network reliability measures with binary decision diagrams[J]. IEEE Transactions on Reliability, 2007, 56(3):506-515.
[16] FU MIN YEH, SY YEN KUO. OBDD-based network reliability calculation[J]. Electronics Letters, 1997, 33(9):759-760.
[17] SY YEN KUO, SHYUE KUNG LU, FU MIN YEH. Determining terminal-pair network reliability based on edge expansion diagrams using OBDD[J]. IEEE Transactions on Reliability, 1999, 48(3):234-246.
[18] FU MIN YEH, SHYUE KUNG LU, SY YEN KUO. OBDD-based evaluation of k-terminal network reliability[J]. IEEE Transactions on Reliability, 2002, 51(4):443-451.
[19] 潘竹生, 莫毓昌, 赵建民. 优先级边排序策略及其性能分析[J]. 计算机科学, 2014, 41(8):81-84. PAN Zhusheng, MO Yuchang, ZHAO Jianmin. Priority edge ordering strategy and performance analysis[J]. Computer Science, 2014, 41(8):81-84.
[20] ADIGA N R, BLUMRICH M A, CHEN D, et al. Blue Gene/L torus interconnection network[J]. IBM Journal of Research and Development, 2005, 49(2/3):265-276.
[21] BARRENRTXEA G, BEFERULL LOZANO B, VETTERLI M. Lattice networks: capacity limits, optimal routing, and queueing behavior[J]. IEEE/ACM Transactions on Networking, 2006, 14(3):492-505.
[22] SRIDHAR M A, RAGHAVENDRA C S. Fault-tolerant networks based on the de bruijn graph[J]. IEEE Transactions on Computers, 1991, 40(10):1167-1174.
[1] 刘玉振,徐承强 . 多晶体材料三维微结构有限元分析的后处理[J]. 山东大学学报(工学版), 2008, 38(2): 13-17 .
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!