臺灣博碩士論文加值系統

本文主旨在建構一套較可行的「網路服務可靠度評估系統」，同時探討如何提昇推導可靠度評估公式之效率。首先，分別介紹網路可靠度（NR）與網路服務可靠度（NSR）的架構，說明兩者最大的差別在於所探討路徑集合涵蓋的範圍不同；接著，針對NSR，配合各節點座標，搜尋服務型路徑集合（SP），利用各節點與終止節點的相對位置，找出較有效率的可通通路，繼而從中決定最佳的通路組合，每次選擇出最適當的兩（或三）條可通路徑，同時進行傳送，藉以提昇兩節點間的服務品質。在理論探討方面，有別於串/並聯系統，由於推導網路系統（如NR或NSR）的可靠度評估公式屬於NP#問題，求解不易，而目前提出的方法也皆不盡理想。本研究應用對於處理布林方程式十分有效率的表格式代數（Tabular Algebra，TA）作為標記法（0，1或-），配合相關法則，利用其簡潔與易電腦化的優點，大幅縮短由路徑集合推導評估公式所耗用的時間；然而，TA的缺點在於該評估公式在型式上並非是標準的（canonical），不易進行等值測試或其他分析；因此，本文再採行降階積之和型式（ROSOP）來運算唯一的（unique）可靠度評估公式，並比較此兩種演算法的實作結果與分析。

The goals of this thesis are not only to construct a complete and practicable Network Service Reliability Evaluation System (NSR Evaluation System), but also to discuss the methods that can enhance the efficiency of calculating the evaluation formula. First of all, we introduce the frameworks of Network Reliability (NR) and Network Service Reliability (NSR) respectively. The most difference between NR and NSR is the composition of the Pathset. In NSR, we search Service Pathset (SP). SP are much more efficient passages than other ones and we can find SP by the correlation between each node and the terminal node. Then, we decide the optimal passages combination from SP. It means the combination of two (or three) suitable passages. Moreover, we can improve the service quality between two nodes by applying the passages at the same time. In theory, other than Series/Parallel Systems, the reliability evaluation formula for Network System is very difficult to get. It belongs to a NP# problem and the proposed solutions for this kind of question are inapplicable for the time being. In This thesis, we take Tabular Algebra (TA) as the notation, e.g. 0, 1, or -, and TA’s main advantages are compactness and generality. In addition, the computation efficiency is greatly enhanced by applying TA. However, the type of TA result is not canonical. It is not good for Equivalence Testing or some analyses. For this reason, we propose another algorithm, ROSOP, to get the unique type of the reliability evaluation formula. Finally, we implement TA and ROSOP by C programming language and compare with the experimental results.

中文摘要 Ⅰ
英文摘要 Ⅱ
致謝 Ⅲ
目錄 Ⅳ
圖目錄 Ⅵ
表目錄 Ⅶ
第一章 緒論 1
1.1 研究動機與背景 1
1.2 研究目的 4
第二章 文獻探討 5
2.1 網路服務可靠度（NSR） 5
2.2 表格式代數（TA） 6
2.3 降階積之和型式（ROSOP） 8
第三章 研究架構 9
3.1 研究架構 9
3.2 開發工具與電腦設備 12
第四章 服務型路徑集合（SP） 13
4.1 定義相關名詞 13
4.2 界定合理選取範圍 14
4.3 SP之搜尋演算法 16
4.4 SP之進階討論 20
第五章 TA與ROSOP之應用 21
5.1 TA之應用 21
5.2 ROSOP之應用 26
5.3 實作結果比較與分析 31
5.4 歸納整理 38
第六章 最佳通路組合 39
6.1 定義相關符號 39
6.2 最佳通路組合表 40
6.3 實作結果分析 42
第七章 結論與建議 44
7.1 結論與貢獻 44
7.2 未來發展與建議 46
參考文獻 47

參考文獻
[1]Aborhey, S., “Binary Decision Graph Reduction,” IEE Proceedings, Vol. 136, No. 4, pp. 277-283, 1989.
[2]Abraham, J.A., “An Improved Algorithm for Network Reliability,” IEEE Transactions on Reliability, Vol. R-28, No. 1, pp. 58-61, 1979.
[3]Arnborg, S., “A Reduced State Enumeration-Another Algorithm for Reliability Evaluation,” IEEE Transactions on Reliability, Vol. 27, pp. 101-105, 1978.
[4]Bronson, G. J., Algorithm Development and Program Design Using C, West Publishing Company, New York, 1996.
[5]Brown, D., “A Computerized Algorithm for Determining the Reliability of Redundant Configurations,” IEEE Transactions on Reliability, Vol. 20, pp. 121-124, 1971.
[6]Ebeling, C. E., An Introduction to Reliability and Maintainability Engineering, The McGraw-Hill Companies, Inc., New York, 1997.
[7]Fratta, L. and U. G. Montanari, “A Boolean Algebra Method for Computing the Terminal Reliability in a Communication Network,” IEEE Transactions on Circuit Theory, Vol. CT-20, pp. 203-211, 1973.
[8]Gihyun, J, C. Hwaja, and Y. Kangbin, “Method for Solving Switching Equations Based on Tabular Algebra,” Electronics Letters, Vol. 30, No. 21, pp. 1749-1750, 1994.
[9]Jung, G., “Comments on “Some Additions to Solution of Switching Equations Based on a Tabular Algebra”,” IEEE Transactions on Computers, Vol. 44, No. 11, pp. 1357-1358, 1995.
[10]Horowitz, E., S. Sartaj, and A.-F. Susan, Fundamentals of Data Structures in C, Computer Science Press, New York, 1993.
[11]Luo, T. and K. S. Trivedi, “An Improved Algorithm for Coherent-System Reliability,” IEEE Transactions on Reliability, Vol. 47, No. 1, pp. 73-78, 1998.
[12]McHugh, J. A., Algorithmic Graph Theory, Prentice-Hall, Inc., New Jersey, 1990.
[13]Perry G., C by Example, Que Corporation, Indiana, 2000.
[14]Taha, H. A., Operations Research, Sixth Edition, Prentice-Hall, Inc., 1997.
[15]Trabado, P. P., L.-R. Antonio, and O.-L. Julio, “Solution of Switching Equations Based on a Tabular Algebra,” IEEE Transactions on Computers, Vol. 42, No. 5, pp. 591-596, 1993.
[16]Wang, C.-C. and W.-D. Chen, “A New Pathset Generation Method for a Complex Reliability Network”, 1998.
[17]Wang, Y. and C. McCrosky, “Solving Boolean Equations Using ROSOP Forms,” IEEE Transactions on Computers, Vol. 47, No. 2, pp. 171-177, 1998.
[18]Wilf, H. S., Algorithms and Compexity, Prentice-Hall International, Inc., New Jersey, 1986.
[19]王清正，符號運算式之網路可靠度矩陣分析，行政院國科會補助專題研究計劃成果報告，2001.
[20]王韞清，評估網路站對間之可靠度的布林代數符號運算方法，碩士論文，國立成功大學製造工程研究所，2001.
[21]李毓仁，使用程序性電腦語言做網路可靠度評估系統，碩士論文，國立成功大學製造工程研究所，2001.
[22]陳文德，適用於自動評估複雜系統之可靠度的兩階段演算法，碩士論文，國立成功大學製造工程研究所，1997.