基于NNVD的網(wǎng)絡(luò)化軟件多步控制算法研究

馬迎輝+彭成+張文佳+薛志山+滿君豐

摘??要：網(wǎng)絡(luò)化軟件系統(tǒng)規(guī)模的增大不僅增加了理解和優(yōu)化系統(tǒng)的難度，而且一個(gè)小的異常就有可能引發(fā)整個(gè)系統(tǒng)的崩潰。因此，針對(duì)網(wǎng)絡(luò)化軟件系統(tǒng)的異常行為，本文提出了一種基于NNVD（network?node?value?degree）的網(wǎng)絡(luò)化軟件多步控制算法，該算法從節(jié)點(diǎn)路徑長(zhǎng)度范圍的角度去研究異常行為傳播的局域控制，通過(guò)網(wǎng)絡(luò)化軟件節(jié)點(diǎn)的重要程度選擇控制節(jié)點(diǎn)，分析了在無(wú)標(biāo)度網(wǎng)絡(luò)軟件系統(tǒng)中進(jìn)行局域多步控制的有效性。研究表明，該算法能夠在一定程度上抑制異常行為的傳播，使異常能夠在一定的范圍內(nèi)得到有效的控制。

關(guān)鍵詞：網(wǎng)絡(luò)化軟件;軟件異常行為;多步控制算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A

The?Network?Software?Multistep?Control?Algorithm?Based?on?NNVD?Research

MA?Ying-hui，?PENG?Cheng，?ZHANG?Wen-jia，?XUE?Zhi-shan，?MAN?Jun-feng，

（College?of?Computer?and?Communication，?Hunan?University?of?Technology，?Zhuzhou，?Hunan?412000，China）

Abstract：?The?increasing?scale?of?networked?software?system?not?only?increases?the?difficulty?to?understand?and?optimize?the?system，?but?a?small?anomaly?is?likely?to?cause?the?collapse?of?the?whole?system.?Therefore，?in?view?of?the?abnormal?behavior?of?networked?software?system，?this?paper?proposed?a?networked?software?based?on?NNVD?multistep?control?algorithm，?the?algorithm?from?the?perspective?of?the?node?path?length?range?to?study?the?spread?of?the?abnormal?behavior?of?local?control，?through?the?network?selection?to?the?importance?of?the?control?software?node，?in?a?scale-free?network?software?system?are?analyzed?in?local?multistep?control?effectiveness.?Studies?show?that?the?proposed?algorithm?can?restrain?the?spread?of?abnormal?behavior?to?a?certain?extent，?make?exceptions?can?get?effective?control?in?a?certain?scope.

Key?words：?networked?software;?software?abnormal?behavior;?Multi-step?control?algorithm

1??引言

隨著Internet的發(fā)展以及計(jì)算機(jī)Internet網(wǎng)絡(luò)和自動(dòng)控制技術(shù)在經(jīng)濟(jì)、社會(huì)和國(guó)防等領(lǐng)域的信息化應(yīng)用，軟件系統(tǒng)呈現(xiàn)出兩個(gè)轉(zhuǎn)變：（1）軟件運(yùn)行平臺(tái)從集中、封閉單機(jī)環(huán)境向開(kāi)放、動(dòng)態(tài)和多變網(wǎng)絡(luò)環(huán)境轉(zhuǎn)變;（2）軟件系統(tǒng)的功能向各種應(yīng)用領(lǐng)域和為大眾用戶提供綜合服務(wù)轉(zhuǎn)變。這使得軟件系統(tǒng)呈現(xiàn)出網(wǎng)絡(luò)化的新特征，軟件的規(guī)模和復(fù)雜性劇增。對(duì)于網(wǎng)絡(luò)化軟件而言，我們面對(duì)的不單單是像Internet這樣的單個(gè)網(wǎng)絡(luò)和系統(tǒng)，而是一個(gè)系統(tǒng)的系統(tǒng)。由群體用戶行為驅(qū)動(dòng)的各層元素間的錯(cuò)綜復(fù)雜的聯(lián)系和交互，構(gòu)成了一個(gè)龐大而又復(fù)雜的網(wǎng)，確切地說(shuō)是一個(gè)動(dòng)態(tài)變化的多尺度網(wǎng)絡(luò)的網(wǎng)絡(luò)，而且其中的節(jié)點(diǎn)（既可以是路由器、網(wǎng)頁(yè)、web服務(wù)，也可以是用戶或者agent）和邊的含義不盡相同。因此，網(wǎng)絡(luò)化軟件系統(tǒng)中的任何節(jié)點(diǎn)發(fā)生故障，都有可能引發(fā)多米諾效應(yīng)，最終導(dǎo)致系統(tǒng)崩潰[1]。據(jù)此，研究網(wǎng)絡(luò)化軟件局域范圍內(nèi)的多步控制方法刻不容緩，以期在系統(tǒng)崩潰之前對(duì)其進(jìn)行多步控制，維持系統(tǒng)穩(wěn)定正常的運(yùn)行。

目前，復(fù)雜網(wǎng)絡(luò)中的三種典型的免疫控制算法包括random?immunization（隨機(jī)免疫）策略[2]、targeted?immunization（目標(biāo)免疫）策略[3]和acquaintance?immunization（熟人免疫）策略[4]。隨機(jī)免疫指為了預(yù)防控制病毒的擴(kuò)散，隨機(jī)地選擇網(wǎng)絡(luò)中的部分節(jié)點(diǎn)并對(duì)其進(jìn)行免疫，此種策略沒(méi)有考慮網(wǎng)絡(luò)節(jié)點(diǎn)間的差異性，網(wǎng)絡(luò)中的所有節(jié)點(diǎn)被同等看待，節(jié)點(diǎn)被選中的概率是相同的。但是在無(wú)標(biāo)度網(wǎng)絡(luò)中采用隨機(jī)免疫策略需要對(duì)網(wǎng)絡(luò)中幾乎所有的節(jié)點(diǎn)進(jìn)行免疫，這在現(xiàn)實(shí)的復(fù)雜網(wǎng)絡(luò)中，幾乎是不可能的。目標(biāo)免疫是依據(jù)無(wú)標(biāo)度網(wǎng)絡(luò)中度分布的不均勻性，順序地選擇部分度大的節(jié)點(diǎn)并對(duì)其進(jìn)行免疫。一旦這些度大的節(jié)點(diǎn)被免疫，那么與它們連接的邊則從網(wǎng)絡(luò)中剔除，很大程度上減少了病毒傳播的途徑。但是這種策略需要事先了解網(wǎng)絡(luò)的拓?fù)浜途W(wǎng)絡(luò)中節(jié)點(diǎn)的度。因此，對(duì)于一些規(guī)模較大的動(dòng)態(tài)網(wǎng)絡(luò)來(lái)說(shuō)也是不現(xiàn)實(shí)的。Cohen等人提出的熟人免疫屬于一種局域控制策略，它不需要知道網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和全局信息，其目的在于找出度數(shù)大的節(jié)點(diǎn)進(jìn)行免疫。

鑒于此，本文提出了一種基于NNVD（network?node?value?degree）的網(wǎng)絡(luò)化軟件局部控制免疫算法。該算法從異常源點(diǎn)出發(fā)，然后對(duì)異常源點(diǎn)周圍的各鄰居節(jié)點(diǎn)的重要程度進(jìn)行計(jì)算，選出重要度大的節(jié)點(diǎn)依次進(jìn)行免疫。在異常源點(diǎn)周圍一定的距離范圍內(nèi)對(duì)異常源點(diǎn)進(jìn)行局域控制，從而控制異常行為在網(wǎng)絡(luò)化軟件系統(tǒng)中的蔓延。最后，通過(guò)仿真實(shí)驗(yàn)對(duì)本文的算法進(jìn)行認(rèn)證，證明了該算法的準(zhǔn)確性和有效性，為后續(xù)的工作提供了理論基礎(chǔ)。

2??相關(guān)工作

近年來(lái)，國(guó)內(nèi)外學(xué)者都以已有的ER隨機(jī)網(wǎng)絡(luò)（Random?network）[5]、WS小世界網(wǎng)絡(luò)（Small?world?network）[6]和BA無(wú)標(biāo)度網(wǎng)絡(luò)（Scale-free?network）[7]等復(fù)雜網(wǎng)絡(luò)模型為依托來(lái)研究病毒傳播的規(guī)律。隨后，一些經(jīng)典的傳播模型也被相繼提出，比較經(jīng)典的有SI模型[8]、SIS模型[9]、SIR模型[10]等。在復(fù)雜的網(wǎng)絡(luò)系統(tǒng)中，為了更好的理解網(wǎng)絡(luò)結(jié)構(gòu)與網(wǎng)絡(luò)性能之間的關(guān)系，復(fù)雜網(wǎng)絡(luò)方面的控制成了近年來(lái)研究的熱點(diǎn)。Wang和Chen等[11]作了初步嘗試，將控制策略首次應(yīng)用到無(wú)標(biāo)度復(fù)雜混沌動(dòng)態(tài)網(wǎng)絡(luò)中，由于BA網(wǎng)絡(luò)結(jié)構(gòu)具有非均勻行的特征，因此可以通過(guò)對(duì)網(wǎng)絡(luò)中少數(shù)節(jié)點(diǎn)進(jìn)行控制，最終達(dá)到網(wǎng)絡(luò)結(jié)構(gòu)穩(wěn)定性的目的。隨后，Li等[12]在復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)牽制控制方面，使用狀態(tài)反饋控制使系統(tǒng)達(dá)到平衡狀態(tài)，并且可以在不同的網(wǎng)絡(luò)耦合強(qiáng)度下驗(yàn)證得到的是系統(tǒng)漸進(jìn)穩(wěn)定的充分條件。Liu等[13]利用局部反饋控制給出連續(xù)離散時(shí)間的復(fù)雜網(wǎng)絡(luò)牽制控制結(jié)論。雖然以上這些關(guān)于控制方面的研究取得了很好的進(jìn)展，但是這些研究都是集中在復(fù)雜網(wǎng)絡(luò)系統(tǒng)方面，在網(wǎng)絡(luò)化軟件方面確鮮有涉及。

3??網(wǎng)絡(luò)化軟件多步控制算法

3.1相關(guān)定義

定義1（SIR模型）網(wǎng)絡(luò)化軟件系統(tǒng)里的節(jié)點(diǎn)分為三類：健康節(jié)點(diǎn)（S）、感染節(jié)點(diǎn)（I，隱含錯(cuò)誤節(jié)點(diǎn)，如內(nèi)存溢出等）和免疫節(jié)點(diǎn)（R）。在異常行為傳播初期，軟件系統(tǒng)中某些健康節(jié)點(diǎn)受到異常節(jié)點(diǎn)感染，并通過(guò)一定的概率將異常傳播到其鄰居節(jié)點(diǎn)。一旦S類節(jié)點(diǎn)被感染，則成為I類節(jié)點(diǎn)。這些I類節(jié)點(diǎn)又會(huì)變成新的感染源去感染其它節(jié)點(diǎn)。R類節(jié)點(diǎn)為免疫節(jié)點(diǎn)，是已經(jīng)恢復(fù)為健康節(jié)點(diǎn)并且獲得免疫能力的節(jié)點(diǎn)，在網(wǎng)絡(luò)化軟件系統(tǒng)里表現(xiàn)為不能被感染并且也不能感染其鄰居節(jié)點(diǎn)。

定義2（異常節(jié)點(diǎn)間故障傳播概率）異常節(jié)點(diǎn)間的故障傳播概率e（m，n）定義為：

當(dāng)擴(kuò)散比率小于某一閾值δ時(shí)，異常源點(diǎn)的擴(kuò)散對(duì)系統(tǒng)幾乎沒(méi)有影響，則免疫停止。

4??實(shí)驗(yàn)及分析

為了驗(yàn)證本文算法的有效性，需要進(jìn)行相關(guān)的實(shí)驗(yàn)分析。本文使用MATLAB仿真軟件分析了本文算法的有效性。

由于網(wǎng)絡(luò)化軟件具有較為復(fù)雜的網(wǎng)絡(luò)特性，本文只考慮網(wǎng)絡(luò)化軟件的無(wú)標(biāo)度網(wǎng)絡(luò)特性。又因?yàn)闊o(wú)標(biāo)度網(wǎng)絡(luò)的冪率參數(shù)與網(wǎng)絡(luò)結(jié)構(gòu)和性能特征具有較強(qiáng)的關(guān)聯(lián)性，本文實(shí)驗(yàn)取=2-3.5作為網(wǎng)絡(luò)結(jié)構(gòu)參數(shù)。本文算法的免疫節(jié)點(diǎn)選擇方法，在確保免疫節(jié)點(diǎn)定位精度的前提下，極大降低了網(wǎng)絡(luò)的能量消耗，并且構(gòu)建了網(wǎng)絡(luò)免疫節(jié)點(diǎn)的最佳路徑。本文算法免疫效果的仿真結(jié)果如圖1所示：

圖1???從節(jié)點(diǎn)的能耗量方面考慮的免疫效果圖

穩(wěn)態(tài)感染率以及故障傳播速度是評(píng)估網(wǎng)絡(luò)免疫效果的指標(biāo)。因此本文在模型網(wǎng)絡(luò)以及實(shí)際網(wǎng)絡(luò)中進(jìn)行了仿真分析，用圖2描述。采用SIR模型，感染率v=0.03，回復(fù)率=0.01，只考慮網(wǎng)絡(luò)化軟件的無(wú)標(biāo)度網(wǎng)絡(luò)特性，N=1000，L=4000。仿真結(jié)果取50次的平均值。

圖2???無(wú)尺度網(wǎng)絡(luò)中免疫度

為了進(jìn)一步分析本文算法的免疫效果，實(shí)驗(yàn)對(duì)本文算法進(jìn)行了多次的仿真分析，獲取的平均統(tǒng)計(jì)結(jié)果如圖3所示。結(jié)果參數(shù)對(duì)本文算法有一定的影響，這是由無(wú)尺度網(wǎng)絡(luò)的特性決定的，越大，本文算法的免疫效果越好。

圖3?算法的解析值與仿真值比較

5??結(jié)束語(yǔ)

研究網(wǎng)絡(luò)化軟件異常行為的多步控制算法，對(duì)提高這種新型軟件系統(tǒng)的穩(wěn)定性和可靠性起重要作用。本文提出了一種基于網(wǎng)絡(luò)節(jié)點(diǎn)重要程度的多步控制算法，并給出了詳細(xì)的定義和計(jì)算方法。實(shí)驗(yàn)結(jié)果表明，該算法能夠準(zhǔn)確獲取網(wǎng)路化軟件系統(tǒng)中的免疫節(jié)點(diǎn)，達(dá)到控制異常行為傳播的目的。本算法的創(chuàng)新之處在于其填補(bǔ)了網(wǎng)絡(luò)化軟件在異常行為控制方面的空白，但是相對(duì)于復(fù)雜網(wǎng)絡(luò)中的一些免疫算法，在算法性能方面仍有很多不足之處。因此，如何改進(jìn)并且提高算法的性能是我們下一步亟待需要解決的問(wèn)題。

參考文獻(xiàn)：

[1]?馬于濤，何克清，李兵，劉婧.網(wǎng)絡(luò)化軟件的復(fù)雜網(wǎng)絡(luò)特征實(shí)證[J].軟件學(xué)報(bào)，2011，22（3）：381-407.

[2]?Yu?L，?Xue?H，Gao?X，et?al.Epidemic?spread?model?based?on?cellular?automata[J].Computer?Engineering?and?Aplications，2007，43（2）：196-237

[3]?Gomez-Gardenes?J，?Echenique?P，?Moreno?Y.?Immunization?of?real?complex?communication?networks[J].European?Physical?Journal?B，2006，49（2）：259-264

[4]?Gallos?L?K，?Liljeros?F，?Argyrakis?P，?et?al.?Improving?immunization?strategies[J].Physical?Review?E（Statistical，?Nonlinear，?and?Soft?Matter?Physics），2007，75（4）：45104-1

[5]?Eedǒs?P，?Rényi?A.?On?the?evolution?of?random?graphs[J].Publ.?Math.?Inst.?Hung.?Acad.?Sci，?1960，?5：?17～61.

[6]?D.J.?Watts，?S.?H.?Strogatz.?Collection?dynamics?of?small-world?networks[J].?Nature，?1998，393（6684）：440-442.

[7]?A.-L.?Barabási，?R.?Albert.?Emergence?of?scaling?in?random?networks[J].Science，1999，286（5439）：509-512.

[8]?Pastor-Satorras，?R，?Vespignani，?A.?Epidemic?Spreading?in?Scale-free?Networks[J].Physical?Review?Letters，?2001，?86（14）：3200-3203.

[9]?Eguiluz?V?M，?Klemm，?K..?Epidemic?Threshold?in?Structured?Scale-Free?Netwoks[J].?Physical?Review?Letters，?2002，89（10）：108701.

[10]?Moore?C，?Newman，?M?E?J.?Epidemics?and?Percolation?in?Small-world?Network?[J].?Physical?Review?E，?2000，?61（5）：5678-5682.

[11]?Wang?X?F，?Chen?G.?Pinning?control?of?scale-free?dynamical?networks.?Physica?A，?2002，310?（3-4）：521-531.

[12]?Li?X，?Wang?X?F，?Chen?G.?Pinning?a?complex?dynamical?networks?to?its?equilibrium.?IEEE?International?Symposium?on?Circuit?System-I，2004，51（10）：2074-2087.

[13]?Liu?Z?X，?Chen?Z?Q，?et?al.?Pinning?control?of?weighted?general?complex?dynamical?networks?with?time?delay.?Physica?A，2007，375（1）：345-354.

[14]?彭成，楊路明，滿君豐.網(wǎng)絡(luò)化軟件異常行為傳播研究[j].電子學(xué)報(bào)，2013，41（10）：2074-2081

[15]?彭成，楊路明，滿君豐.網(wǎng)絡(luò)化軟件交互行為動(dòng)態(tài)建模[J].電子學(xué)報(bào)，2013，41（2）：314-320