PMC模型下An,k和Sn,k的條件診斷度.pdf

1、多處理器系統(tǒng)中，故障診斷是一個通過相互測試來識別出系統(tǒng)中的故障處理器的過程，在保障系統(tǒng)可靠度方面起到相對大的作用，并且被許多學者所研究。在1976年，Prepara et al.等人提出一種稱為PMC模型的診斷方法，使得在故障診斷有了進一步的發(fā)展。由于傳統(tǒng)的診斷方法存在一定的缺陷，在2005年，Lai et al.等人提出一種新的故障診斷方法——條件診斷。條件錯誤診斷度的大小比傳統(tǒng)的診斷度大的多，因此條件錯誤診斷度能更好地衡量一個正則的

2、互連拓撲結(jié)構(gòu)的診斷問題。
　　本文主要研究的是網(wǎng)絡拓撲結(jié)構(gòu)圖——排列圖An,k和（n，k)-star圖在PMC模型下的條件診斷度。排列圖An，k和（n，k）-star圖作為星圖的兩種不同的推廣，它們不僅保留了星圖的許多優(yōu)點，如具有點對稱性、最大的錯誤容錯性、最短的簡單路徑和層次化結(jié)構(gòu)，而且由于這兩個圖有兩個參數(shù)，因此在設計網(wǎng)絡中選擇主要涉及參數(shù)，如度、直徑和控制結(jié)點總數(shù)上比星圖更具有靈活性。根據(jù)兩個圖的定義可知，當k=1時排列圖A

3、n,1同構(gòu)于（n，1）-star圖，且均同構(gòu)于完全圖Kn，因此研究其診斷度不具有實際意義。本文主要利用計算機算法搜索構(gòu)造和數(shù)學推理證明的方法確定了排列圖An,k和（n，k）-star圖兩個圖在PMC模型下的條件診斷度。我們得到的結(jié)論如下:
　　對于排列圖An,k:
　　(1)當k=2時，排列圖An，k的條件診斷度tc（An，2）=4n-10，其中n≥5。
　　(2)當k≥3時，排列圖An,k的條件診斷度tc（An,k）