基于NNVD的網絡化軟件多步控制算法研究

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

摘??要：網絡化軟件系統規模的增大不僅增加了理解和優化系統的難度，而且一個小的異常就有可能引發整個系統的崩潰。因此，針對網絡化軟件系統的異常行為，本文提出了一種基于NNVD（network?node?value?degree）的網絡化軟件多步控制算法，該算法從節點路徑長度范圍的角度去研究異常行為傳播的局域控制，通過網絡化軟件節點的重要程度選擇控制節點，分析了在無標度網絡軟件系統中進行局域多步控制的有效性。研究表明，該算法能夠在一定程度上抑制異常行為的傳播，使異常能夠在一定的范圍內得到有效的控制。

關鍵詞：網絡化軟件;軟件異常行為;多步控制算法

中圖分類號：TP301.6 文獻標識碼：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的發展以及計算機Internet網絡和自動控制技術在經濟、社會和國防等領域的信息化應用，軟件系統呈現出兩個轉變：（1）軟件運行平臺從集中、封閉單機環境向開放、動態和多變網絡環境轉變;（2）軟件系統的功能向各種應用領域和為大眾用戶提供綜合服務轉變。這使得軟件系統呈現出網絡化的新特征，軟件的規模和復雜性劇增。對于網絡化軟件而言，我們面對的不單單是像Internet這樣的單個網絡和系統，而是一個系統的系統。由群體用戶行為驅動的各層元素間的錯綜復雜的聯系和交互，構成了一個龐大而又復雜的網，確切地說是一個動態變化的多尺度網絡的網絡，而且其中的節點（既可以是路由器、網頁、web服務，也可以是用戶或者agent）和邊的含義不盡相同。因此，網絡化軟件系統中的任何節點發生故障，都有可能引發多米諾效應，最終導致系統崩潰[1]。據此，研究網絡化軟件局域范圍內的多步控制方法刻不容緩，以期在系統崩潰之前對其進行多步控制，維持系統穩定正常的運行。

目前，復雜網絡中的三種典型的免疫控制算法包括random?immunization（隨機免疫）策略[2]、targeted?immunization（目標免疫）策略[3]和acquaintance?immunization（熟人免疫）策略[4]。隨機免疫指為了預防控制病毒的擴散，隨機地選擇網絡中的部分節點并對其進行免疫，此種策略沒有考慮網絡節點間的差異性，網絡中的所有節點被同等看待，節點被選中的概率是相同的。但是在無標度網絡中采用隨機免疫策略需要對網絡中幾乎所有的節點進行免疫，這在現實的復雜網絡中，幾乎是不可能的。目標免疫是依據無標度網絡中度分布的不均勻性，順序地選擇部分度大的節點并對其進行免疫。一旦這些度大的節點被免疫，那么與它們連接的邊則從網絡中剔除，很大程度上減少了病毒傳播的途徑。但是這種策略需要事先了解網絡的拓撲和網絡中節點的度。因此，對于一些規模較大的動態網絡來說也是不現實的。Cohen等人提出的熟人免疫屬于一種局域控制策略，它不需要知道網絡的拓撲結構和全局信息，其目的在于找出度數大的節點進行免疫。

鑒于此，本文提出了一種基于NNVD（network?node?value?degree）的網絡化軟件局部控制免疫算法。該算法從異常源點出發，然后對異常源點周圍的各鄰居節點的重要程度進行計算，選出重要度大的節點依次進行免疫。在異常源點周圍一定的距離范圍內對異常源點進行局域控制，從而控制異常行為在網絡化軟件系統中的蔓延。最后，通過仿真實驗對本文的算法進行認證，證明了該算法的準確性和有效性，為后續的工作提供了理論基礎。

2??相關工作

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

3??網絡化軟件多步控制算法

3.1相關定義

定義1（SIR模型）網絡化軟件系統里的節點分為三類：健康節點（S）、感染節點（I，隱含錯誤節點，如內存溢出等）和免疫節點（R）。在異常行為傳播初期，軟件系統中某些健康節點受到異常節點感染，并通過一定的概率將異常傳播到其鄰居節點。一旦S類節點被感染，則成為I類節點。這些I類節點又會變成新的感染源去感染其它節點。R類節點為免疫節點，是已經恢復為健康節點并且獲得免疫能力的節點，在網絡化軟件系統里表現為不能被感染并且也不能感染其鄰居節點。

定義2（異常節點間故障傳播概率）異常節點間的故障傳播概率e（m，n）定義為：

當擴散比率小于某一閾值δ時，異常源點的擴散對系統幾乎沒有影響，則免疫停止。

4??實驗及分析

為了驗證本文算法的有效性，需要進行相關的實驗分析。本文使用MATLAB仿真軟件分析了本文算法的有效性。

由于網絡化軟件具有較為復雜的網絡特性，本文只考慮網絡化軟件的無標度網絡特性。又因為無標度網絡的冪率參數與網絡結構和性能特征具有較強的關聯性，本文實驗取=2-3.5作為網絡結構參數。本文算法的免疫節點選擇方法，在確保免疫節點定位精度的前提下，極大降低了網絡的能量消耗，并且構建了網絡免疫節點的最佳路徑。本文算法免疫效果的仿真結果如圖1所示：

圖1???從節點的能耗量方面考慮的免疫效果圖

穩態感染率以及故障傳播速度是評估網絡免疫效果的指標。因此本文在模型網絡以及實際網絡中進行了仿真分析，用圖2描述。采用SIR模型，感染率v=0.03，回復率=0.01，只考慮網絡化軟件的無標度網絡特性，N=1000，L=4000。仿真結果取50次的平均值。

圖2???無尺度網絡中免疫度

為了進一步分析本文算法的免疫效果，實驗對本文算法進行了多次的仿真分析，獲取的平均統計結果如圖3所示。結果參數對本文算法有一定的影響，這是由無尺度網絡的特性決定的，越大，本文算法的免疫效果越好。

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

5??結束語

研究網絡化軟件異常行為的多步控制算法，對提高這種新型軟件系統的穩定性和可靠性起重要作用。本文提出了一種基于網絡節點重要程度的多步控制算法，并給出了詳細的定義和計算方法。實驗結果表明，該算法能夠準確獲取網路化軟件系統中的免疫節點，達到控制異常行為傳播的目的。本算法的創新之處在于其填補了網絡化軟件在異常行為控制方面的空白，但是相對于復雜網絡中的一些免疫算法，在算法性能方面仍有很多不足之處。因此，如何改進并且提高算法的性能是我們下一步亟待需要解決的問題。

參考文獻：

[1]?馬于濤，何克清，李兵，劉婧.網絡化軟件的復雜網絡特征實證[J].軟件學報，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]?彭成，楊路明，滿君豐.網絡化軟件異常行為傳播研究[j].電子學報，2013，41（10）：2074-2081

[15]?彭成，楊路明，滿君豐.網絡化軟件交互行為動態建模[J].電子學報，2013，41（2）：314-320