[發(fā)明專利]一種基于元胞自動(dòng)機(jī)的軟件故障傳播規(guī)律發(fā)現(xiàn)方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310706727.7
• 申請(qǐng)日: 2013-12-19
• 公開（公告）號(hào): CN104734870B
• 公開（公告）日: 2019-03-29
• 發(fā)明（設(shè)計(jì)）人: 張琨;王琦;陳旋;卞雪雯;劉藝
• 申請(qǐng)（專利權(quán)）人: 南京理工大學(xué)
• 主分類號(hào): H04L12/24
• 分類號(hào): H04L12/24
• 代理公司: 南京理工大學(xué)專利中心 32203
• 代理人: 朱顯國(guó)

1.一種基于元胞自動(dòng)機(jī)的軟件故障傳播規(guī)律發(fā)現(xiàn)方法，其特征在于步驟如下：

（一）建立元胞自動(dòng)機(jī)CA，定義軟件網(wǎng)絡(luò)化得到的拓?fù)鋱D中的節(jié)點(diǎn)即為元胞，節(jié)點(diǎn)數(shù)目記為M，則CA模型通過(guò)一個(gè)四元組定義為CA=(C，Q，V，f)，其中C表示元胞空間，此時(shí)擴(kuò)展為平面空間，元胞不再局限于空間的某一特定位置，而是散布在平面空間上；Q表示元胞狀態(tài)，一個(gè)離散的有限集合 ；V表示中心元胞的鄰居集合，此時(shí)不再局限為空間上相鄰的元胞，而是擴(kuò)展為有邊相連即為鄰居；f為狀態(tài)轉(zhuǎn)換規(guī)則；

（二）根據(jù)上述元胞自動(dòng)機(jī)建立軟件故障傳播模型；該模型將節(jié)點(diǎn)狀態(tài)劃分為兩種狀態(tài)，N表示節(jié)點(diǎn)正常狀態(tài)，F(xiàn)表示節(jié)點(diǎn)故障狀態(tài)，軟件網(wǎng)絡(luò)化得到的拓?fù)鋱D中一個(gè)節(jié)點(diǎn)對(duì)應(yīng)元胞自動(dòng)機(jī)的一個(gè)元胞，正常狀態(tài)用0表示，故障狀態(tài)用1表示，令狀態(tài)集Q＝{0,1}，節(jié)點(diǎn)i在t時(shí)刻的狀態(tài)變量用Si(t)(Si(t)∈Q)表示，則有

狀態(tài)轉(zhuǎn)換規(guī)則f可以定義為：在t時(shí)刻狀態(tài)為N的節(jié)點(diǎn)i，在t+1時(shí)刻以概率Pi轉(zhuǎn)換狀態(tài)為F；一旦節(jié)點(diǎn)狀態(tài)為F，則不再影響其鄰居元胞，其中：

α為故障傳播概率；β為節(jié)點(diǎn)自身的容錯(cuò)率，故障傳播概率α和節(jié)點(diǎn)的容錯(cuò)率β都為系統(tǒng)預(yù)設(shè)值；α(1-β)為中心元胞受到一個(gè)故障元胞影響時(shí)，自身狀態(tài)轉(zhuǎn)變的概率；sum_i(t) 為在t時(shí)刻，中心元胞i的鄰居中故障元胞的個(gè)數(shù)；

（三）對(duì)建立好的軟件故障傳播模型進(jìn)行仿真，每個(gè)時(shí)刻對(duì)模型中所有元胞進(jìn)行遍歷，直到模型中故障元胞個(gè)數(shù)不再增加，則跳出循環(huán)；

所述步驟三中，對(duì)建立好的軟件故障傳播模型進(jìn)行仿真的具體過(guò)程如下：利用元胞自動(dòng)機(jī)模擬軟件網(wǎng)絡(luò)中故障傳播過(guò)程，根據(jù)元胞自動(dòng)機(jī)建立的軟件故障傳播模型轉(zhuǎn)換規(guī)則f，在每個(gè)時(shí)刻中對(duì)所有元胞進(jìn)行狀態(tài)更新，具體過(guò)程如下：

1)初始化時(shí)刻t=0和t時(shí)刻的故障節(jié)點(diǎn)個(gè)數(shù)I(t)=0，給故障傳播概率α∈(0,1)和節(jié)點(diǎn)的容錯(cuò)率β∈(0,1)賦值，計(jì)算各元胞的鄰居矩陣；

2)在t＝k(k≥0)時(shí)刻時(shí)，選擇軟件網(wǎng)絡(luò)中n(n＜M)個(gè)節(jié)點(diǎn)為初始故障節(jié)點(diǎn)，并把節(jié)點(diǎn)對(duì)應(yīng)的元胞狀態(tài)置為F，即元胞此時(shí)刻發(fā)生故障，則I(t)=n；

3)在t＝k+1時(shí)刻，遍歷所有元胞，每個(gè)元胞根據(jù)周圍鄰居元胞的狀態(tài)和自身狀態(tài)，計(jì)算狀態(tài)轉(zhuǎn)化概率Pi，更新其元胞狀態(tài)，元胞狀態(tài)從N轉(zhuǎn)變?yōu)镕，則I(t)=I(t)+1，并把上一時(shí)刻故障的元胞鄰居矩陣置為0；

4)t=t+1，判斷I(t+1)是否等于I(t)，如果相等就說(shuō)明故障元胞不再增加，則退出循環(huán)，否則執(zhí)行步驟3)。