復雜多態(tài)系統(tǒng)的冗余備份元件優(yōu)化①

付 林, 史小宏

(上海海事大學 信息工程學院, 上海 201306)

復雜多態(tài)系統(tǒng)的冗余備份元件優(yōu)化①

付 林, 史小宏

(上海海事大學 信息工程學院, 上海 201306)

在復雜的多態(tài)系統(tǒng)中, 系統(tǒng)可靠性非常重要, 最常見的是冷熱備份模式來實現(xiàn)系統(tǒng)的可靠性. 本文中我們提出了混合冗余備份模式, 計算復雜系統(tǒng)的可靠性和任務成本, 解決復雜系統(tǒng)中的備份元件優(yōu)化分布和初始化問題. 本文主要是通過離散數(shù)學的概率分布計算復雜系統(tǒng)中元件的可靠性和任務成本, 利用量子遺傳算法來解決冗余備份元件的優(yōu)化分布問題. 最后同時通過仿真實驗來計算出系統(tǒng)的可靠性和預期的任務成本,以及冗余備分元件的優(yōu)化分布, 得出了復雜系統(tǒng)可靠性與成本的平衡關系.

冗余備份; 冷熱備份; 量子遺傳算法; 可靠性; 任務成本

1 引言

傳統(tǒng)類型的冗余備份主要是利用元件備份來做系統(tǒng)可靠性保障的[1], 這類備份只是單純的靠元件的替換來滿足可靠性要求, 而你沒有考慮成本損耗問題,另外就是冷備份和熱備份[2]. 這類備份模式雖然也是利用多余的元件來做備份, 不過考慮到了成本損耗問題, 沒有進一步的去探討元件的優(yōu)化分對于系統(tǒng)可靠性和成本的影響. 元件處于熱冗余備份模式下的時候,當有運行操作的元件故障的時候, 可以快速的替換掉故障元件, 從而提供快速恢復, 為了保證能夠隨時替換出故障的運行操作元件, 就需要時刻補充處于熱備份模式的備用元件, 這就增加了整個系統(tǒng)的成本開支,相比之下, 冷備份模式下的元件, 就不會有這樣的消耗, 但是冷備份元件替換故障元件的時候, 需要很長的恢復延遲時. 系統(tǒng)中熱備份冗余相關的成本消耗和系統(tǒng)可靠性高于冷備份冗余元件. 因此需要在可靠性和成本之間做一個平衡[3]. 一個好的辦法是可以通過在同一個系統(tǒng)中設計兩種類型的冗余, 即讓一部分備用元件處于熱備份模式下, 讓大多數(shù)備份元件處于冷備份模式下可以減少維護成本, 同時熱冗余備份元件又可以保證一定的系統(tǒng)可靠性, 最后對系統(tǒng)的可靠性和成本的需求不同, 冷熱備份模式中系統(tǒng)元素的分布和備用元素啟動的順序會嚴重影響系統(tǒng)的可靠性以及任務的成本[4]. 冷和熱備份中元件的分布以及初始化序列的選擇可以使得系統(tǒng)滿足一定的可靠性同時成本最小化, 在本文中我們將使用可靠性和預期成本算法計算復雜系統(tǒng)的可靠性和預期任務成本, 利用冗余元件來滿足系統(tǒng)可靠性的同時, 計算系統(tǒng)的任務成本,同時在文中我們使用量子遺傳算法去優(yōu)化系統(tǒng)中備份元件的初始化順序, 研究冗余元件在系統(tǒng)中的分布不同對系統(tǒng)的可靠性和成本的影響, 從而在滿足一定的可靠性基礎上計算系統(tǒng)的可靠行和成本, 并找出對應的備份元素的初始化順序.

2 元件的混合冗余備份模型

假設系統(tǒng)中有N個元件h( 1),h(2),...,h(N), 假定最開始的H個元件是處于熱備份模式下, 因此在任務開始的時候元件h(1),h(2),...,h(H)就開始初始化了, 剩下的N-H個元件h(H+1),...,h(N)處于冷備份模式下,所有處于熱備份模式下的元件在任務開始的時候就被初始化了, 當處于操作狀態(tài)的元件故障后熱備份模式下的一個元件就會替換掉故障的元件, 當所有熱備份模式下的備用元件都替換完之后, 緊接著就將冷備份模式中的元件初始化, 如果所有元件在任務結束時間之前都故障了, 那么整個系統(tǒng)任務就失敗了.

為了計算系統(tǒng)的可靠性我們做出如下假設[5]:

1) 系統(tǒng)中的各個元件是相互獨立的

2) 在替故障元件到系統(tǒng)恢復這段時延跟整個任務時間相比可以忽略不計

3) 由于熱備份模式下的元件壓力跟操作狀態(tài)下一樣, 所以維護成本用操作成本來計算

4) 系統(tǒng)中的元件數(shù)量和類型是固定

5) 系統(tǒng)和元件故障是不可修復的

2.1 操作時間段內(nèi)的故障元件的概率計算

我們假設系統(tǒng)的任務時間是t, 將任務時間t劃分成m個相等的時間間隔, 每個時間間隔是Δ=t /m, 元件j在第i時間間隔故障的概率分布函數(shù)pj(i)可以通過累計故障分布函數(shù)Fj(t)來獲得, 其中第i時間間隔為Δi=Δ(i+1)-Δ(i), 對應的累計分布函數(shù)為Fj(Δ(i+1))-Fj(Δi)

對于元件故障時間分布滿足故障指數(shù)為λj的指數(shù)分布的時候, 則元件j的故障累積時間分布函數(shù)就可以用下面公式表示:

對應的元件j在第i時間間隔故障的概率分布函數(shù)pj(i)就可以通過對分布函數(shù)求導得到, 如下式:

對應的比例參數(shù)αj和形狀參數(shù)βj的威布爾分布函數(shù)和概率密度函數(shù)為:

在我們的系統(tǒng)模型中元件的故障時間分布式離散的而不是連續(xù)的, 那么整個任務時間段內(nèi)元件j的離散時間可以Tj就可以用向量Pj=(pj(0),...,pj(m))來表示, 其中pj(i) =Pr{Tj=Δi} 是時間間隔為Δi(0≤i≤m)的故障概率. 因為沒有元件的操作時間比總的任務時間t要長, 因此元件j在時間內(nèi)不出現(xiàn)故障的概率pj(m)=Pr{Tj≥t=Δm}, 就可以表示為

2.2 系統(tǒng)元件的故障時間分布計算

對于任意一組給定的元件序列h( 1),h(2),...,h(N),我假定最開始的H個元件是處于熱備份模式下, 因此在任務開始的時候元件h(1),h(2),...,h(H)就開始初始化了, 剩下的N-H個元件處于冷備份模式下. 對于任意一個j＞H處于冷備份的元件在系統(tǒng)中j-1個元件出故障的時候開始初始化,h(j)該元件在系統(tǒng)中初始化的索引序列. 那么系統(tǒng)中第j個在任務開始到時間Xj出現(xiàn)故障就可以表示為向量Qj=(Qj(0),...,Qj(m)), 其中Qj(i)=Pr{Xj=Δi} . 那么元件h(1)在時間任務開始的時候初始化, 就有X1=Th(1)和Q1(i)=ph(1)(0≤i≤m). 所有的熱備份下的元件都是在任務開始的時候初始化的, 因此熱備份模式下的元件有Xj=max(Xj-1,Th(j)), 進而獲得可靠性如下:

對于冷備份下的元件, 要等到熱備份下的元件都出現(xiàn)故障后才會去初始化, 因此有Xj=Xj-1+Th(1),進而獲得冷備份下元件的可靠性如下:

2.3 可靠性與預期任務成本計算算法

3 量子遺傳算法優(yōu)化元件分布與初始化序列

3.1 量子遺傳算法的思想

系統(tǒng)的元件的分布與初始化序列優(yōu)化問題是一個復雜的組合優(yōu)化問題[6], 有N*N!個可能的解決方法, 要去詳盡的檢測每一種可能來確定一個相對最優(yōu)的方法是不可能, 傳統(tǒng)的啟發(fā)式算法計算量比較復雜并且得到的解的誤差比較大[7], 利用遺傳算法來搜尋的時候不用去考慮下一步的搜尋方向來找到一個最優(yōu)的解.

遺傳算法來自于生物進化論, 通過模擬自然界的生物進化, 用編碼串也就是生物進化里面的“染色體”對問題進行優(yōu)化. 將問題的所有的解的集合在一起,形成一個種群, 利用選擇, 交叉, 變異對種群的解進行優(yōu)化, 每個染色體都對應有一個解值. 采用用遺傳算法解決問題時, 需要確定以下幾個要素[8,9]:

1) 通過對染色體上的基因進行編碼將問題的解體現(xiàn)出來確定染色體的編碼.

2) 將適應度高的個體遺傳到下一代群體當中去建立個體的適應度函數(shù).

3) 初始化種群.

4) 對基因進行復制, 交叉, 變異等遺傳操作產(chǎn)生下一代群體, 確定遺傳算子.

5) 確定群體規(guī)模, 終止進化代數(shù), 交叉率pc, 變異概率pm.

量子遺傳算法是將量子計算和遺傳算法結合起來.對比傳統(tǒng)的遺傳算法和量子遺傳算法, 研究人員發(fā)現(xiàn)量子遺傳算法能夠種群規(guī)模很小的情況下, 用很小的代價找出相關問題的最優(yōu)解[10]. 量子遺傳算法采用的編碼方式與傳統(tǒng)的遺傳算法編碼方法有很大的不同,量子遺傳算法利用量子位染色體編碼, 而且利用量子門來完成種群的更新, 從而產(chǎn)生新的最優(yōu)種群[11], 這里就是找到最優(yōu)的解集.

3.2 量子遺傳算法的優(yōu)化過程

第一步: 用量子比特表示最小的信息單元. 一個量子比特的狀態(tài)可表示為在量子遺傳算法中第t代染色體種群可以表示為Q(t)=[q1(t),q2(t),...,qn(t)], 其中,

第二步: 量子算子的定義, 選擇算子: 采用跟遺傳算法類似的輪盤賭來確定遺傳算子. 變異算子: 在量子遺傳算法中通過量子旋轉門的旋轉角來表示量子染色體中的變異操作, 下面的式子是本文用到的量子變異算子[12].

交叉算子: 在量子遺傳算法中采用量子的相干性的特性進行全干擾交叉操作[13], 使得種群中的個體都能夠參與到進化中而不是局部的進化. 以種群規(guī)模為5計算, 染色體的長度為5計算, 用A, B, C, D, E表示交叉后獲得的新的染色體如表1所示.

表1 全干擾交叉

所謂的元素分布與優(yōu)化問題就是找出一組元素初始化列, 使得在滿足一定的可靠性級別R*的時候系統(tǒng)的成本最小[14].

對于任何染色體代表的元件的初始化順序, 我們可以找出處于熱備份模式和冷備份模式下的元件, 利用利用上面的求可靠性和任務成本的算法, 我們可以求出系統(tǒng)中元件處于該順序的時候的可靠性R和預期的任務成本C, 這樣的話我們再利用公式(8), 我們可以定義一個值,式中M是一個足夠大的整數(shù), 我們可以利用這個公式解決系統(tǒng)的優(yōu)化問題, 當σ=0的時候, 就可以求出最小任務成本, 當σ比較大而R*=1的時候, 問題就轉化為了求系統(tǒng)的最大可靠性問題. 在量子遺傳算法的開始的時候用一組0到N的任意數(shù)字代表一組解決方法, 隨機產(chǎn)生的數(shù)字代表了系統(tǒng)中冗余備份元件的初始化順序, 比如2,3,5,6,1,4這組數(shù)字, 2,3,5就代表了熱備份元件的初始順序, 通過交叉和變異過程獲得新的的解決方方法, 根據(jù)求解的方法來求適應度函數(shù)的值, 將得到的初始化順序代入到2.3節(jié)的可靠性和預期任務成本算法中去, 計算這種情況下的可靠性和任務成本,帶入到公式(8)中去比較求得適應度值是否滿足要求,然后操作量子旋轉門, 調(diào)整種群的個體, 獲得新的個體保留最優(yōu)解, 之道量子遺傳算法跌代到求出一組初始化序列, 并且求得此時的可靠性滿足公式(8), 量子遺傳算法結束, 記錄下得到最優(yōu)解情況下的備份元件的初始化序列.

4 仿真結果與分析

4.1 模型計算結果與分析

我們可以通過一個例子來驗證一下模型, 假設一個復雜系統(tǒng)中含有10個元件, 我們利用威布爾失效時間分布模型來描述系統(tǒng)中元件的故障狀態(tài), 并且在表2中給出了威布爾規(guī)模參數(shù)αj和狀態(tài)參數(shù)βj. 同時在表2中給出了冷備份和熱備份模式下的元件啟動成本, 假設系統(tǒng)的任務時間是t=400, m=500的時候前五個元件處于熱備份模式下, 后五個元件處于冷備份模式下, 這樣我們利用上面的算法就可以計算出系統(tǒng)的任務成本C=22656和可靠性R=0.8109.

表2 系統(tǒng)中元件的各種參數(shù)

2 100 1.0 2050 5 40 15 3 150 1.1 2150 9 70 13 4 80 1.0 2000 4 50 9 5 110 1.3 2200 6 80 12 6 75 1.0 2050 5 90 10 7 120 1.0 2150 6 70 12 8 130 1.1 2080 9 70 13 9 110 1.0 2150 3 90 9 10 140 1.1 2080 4 60 8

同時為了研究不同任務時間段m對系統(tǒng)可靠性和成本的影響, 假設五個元件處于熱備份模式下, 另外五個元件處于冷備份模式下, 我們可以通過圖1看出不同任務時間段對可靠性和成本的影響.

圖1 可靠性和任務成本任務隨時間段m的變化

4.2 元件分布優(yōu)化與初始化序列結果與分析

我們假設系統(tǒng)中有10個元件, 利用表2中給的參數(shù)和模型中提出的可靠性與成本計算算法, 利用量子遺傳算法來優(yōu)化處理, 我們可以得出系統(tǒng)中元件最優(yōu)元素分布隨著遺傳代數(shù)而變化, 最優(yōu)解達到一個穩(wěn)定的趨勢如圖2所示.

圖2 系統(tǒng)中元件的分布隨著遺傳代數(shù)的變化

同時我們可以求出在滿足不同的可靠性R*的時候,利用量子遺傳算法計算出系統(tǒng)的可靠性和預期任務成本以及系統(tǒng)中元件的初始化序列如表3所示.

表3 對于滿足不同的可靠性R*得到的元件序列

最后我們可以得到不同的可靠性與預期任務成本的一個平衡曲線如圖3, 根據(jù)這個圖可以幫助我們來設計系統(tǒng)的混合冗余備份, 可以根據(jù)對成本和可靠性需求的要求來分配備份元件.

圖3 可靠性和預期任務成本的平衡

5 結語

在本文中我們主要解決的是系統(tǒng)元件不可修復的情況, 通過對系統(tǒng)中冗余備份模式的分析, 提出了我們的算法, 并且通過實例來計算出了混合備份模式下系統(tǒng)的可靠性和預期成本, 在論文的后半部分利用量子遺傳算法對系統(tǒng)中元件分布進行處理, 找出了在滿足一定可靠性和預期成本的時候系統(tǒng)中元件的一組初始化序列, 通過圖三直觀的顯示了系統(tǒng)可靠性跟預期成本之間的關系, 為系統(tǒng)元件分布和優(yōu)化提供了依據(jù).

1 祝春標.基于多部件的冗余備份計算機通信系統(tǒng)分析.信息與電腦:理論版,2010(5).

2 葛晶晶.基于Markov過程的網(wǎng)絡控制系統(tǒng)冗余技術研究[碩士學位論文].大連:大連理工大學,2014.

3 Levitin G, Xing L, Dai Y. Cold vs. hot standby mission operation cost minimization for 1-out-of-N systems. European Journal of Operational Research, 2014, 234(1): 155–162.

4 黎湘,郁文賢,莊釗文,等.決策層信息融合的神經(jīng)網(wǎng)絡模型與算法研究.電子學報,1997,(9):117–120.

5 吳頔.不可修復如新的多狀態(tài)串聯(lián)系統(tǒng)可靠性分析[碩士學位論文].武漢:武漢科技大學,2013.

6 許傳玉,朱若男,梁穎紅,等.遺傳算法在復雜系統(tǒng)可靠性優(yōu)化中的應用.哈爾濱理工大學學報,2000,5(3):90–93.

7 汪松泉.遺傳算法在組合優(yōu)化中的應用研究[碩士學位論文].合肥:安徽大學,2010.

8 邵軍,程華,徐軍.遺傳算法在結構可靠性優(yōu)化中的應用.四川建筑科學研究,2001,27(2):4-5.

9鄭世玨,陳曉燕,高麗.基于量子遺傳算法的傳感器節(jié)點優(yōu)化部署方法.計算機工程與設計,2008,29(7):1681–1683.

10 周殊,潘煒,羅斌,等.一種基于粒子群優(yōu)化方法的改進量子遺傳算法及應用.電子學報,2006,34(5):897–901.

11 周傳華,錢鋒.基于改進量子遺傳算法的小波神經(jīng)網(wǎng)絡優(yōu)化及其軟測量應用.華東理工大學學報:自然科學版,2008, 34(6):850–853.

12 陳曉燕.基于量子遺傳算法的無線傳感器網(wǎng)絡節(jié)點定位算法研究[碩士學位論文].武漢:華中師范大學,2009.

13 楊玉,戴紅偉,李存華.量子干擾交叉遺傳算法及其應用研究.2011年江蘇省人工智能學術會議,2011.

14 張鐵柱,滕春賢,韓志剛.遺傳算法在系統(tǒng)可靠性優(yōu)化中的應用.控制與決策,2002,17(3):378–380.

Optimization of Redundant Backup Components in Complex Polymorphic System

FU Lin, SHI Xiao-Hong
(College of Information Engineering, Shanghai Maritime University, Shanghai 201306, China)

In the complex polymorphic system, system reliability is very important, and the most common mode to realize the system reliability is the cold and hot backup mode. In this paper we propose a hybrid redundant backup mode, to calculate the reliability of complex systems and task cost, and to solve the problems of optimization distribution and initialization of backup components in complex system. With the probability distribution of discrete mathematics, this paper mainly calculates the reliability and task cost of components in complex system. Then, use quantum genetic algorithm to solve the problem of redundancy backup element optimization distribution. Finally, simulation is implemented to calculate the reliability of the system, the expected task cost, and optimization distribution of redundant backup devices. It concludes the balance relationship between reliability and task cost of complex system.

redundancy backup; cold and hot backup; quantum genetic algorithm; reliability; task cost

2016-03-26;收到修改稿時間:2016-05-05

10.15888/j.cnki.csa.005497