基于節點最大剩余容量的負荷再分配策略研究

周添杰，蔣國平

(南京郵電大學 自動化學院，江蘇 南京 210023)

基于節點最大剩余容量的負荷再分配策略研究

周添杰，蔣國平

(南京郵電大學 自動化學院，江蘇 南京 210023)

主要研究目的是在復雜網絡發生相繼故障的過程中，設計一種合理有效的復雜網絡相繼故障的負荷再分配策略，有效減小網絡臨界閾值βm，提高網絡魯棒性。通過對比研究和仿真建模的方法，提出了基于節點最大剩余容量的負荷再分配策略：當網絡中節點發生故障時，故障節點的負荷分配給當前時刻網絡內剩余容量最大的部分節點，這部分節點的個數與故障節點的度在數值上相等，并且這部分節點所能分得的負荷與其自身的剩余容量有關，剩余容量越大的節點相對而言所能分得的負荷越多。選取人工網絡和實際網絡進行仿真對比研究，結果表明，所提出的負荷再分配策略能夠有效地減小臨界閾值βm，說明該策略是合理有效的，能夠提高網絡魯棒性。

復雜網絡；相繼故障；負荷再分配；網絡魯棒性

1 概 述

隨著科學技術的進步和發展,現代社會已然是一個網絡化的社會，人類的生產生活已經離不開網絡，時時刻刻都在接觸電力網[1]、互聯網[2]、交通網、信息網[2]、人際關系網[2]等各種各樣的網絡。在實際生產生活中，網絡中的極少部分節點在發生故障時，會通過網絡中節點與節點之間的耦合關系擴大故障規模，最終導致網絡中的大部分節點甚至整個網絡發生故障，稱這一現象為“網絡雪崩”[3]，也稱為復雜網絡的相繼故障。網絡的相繼故障具有很強的破壞性。例如，2003年8月，由美國俄亥俄州的3條高壓線路過載所引起的北美大停電事件[4]，使數千萬人陷入黑暗，并導致了無法估量的經濟損失。

為了采取有效措施來減小或抑制網絡相繼故障的規模，針對網絡相繼故障這一現象的研究有其必要性，近年來很多專家學者已經取得了積極的成果。就復雜網絡相繼故障的模型而言，有六類模型被各界學者廣為研究：負荷-容量模型、二值影響模型[5]、OPA模型[6]、沙堆模型[7]、CASCADE模型[8]、耦合映像格子模型[9]。其中，應用最為廣泛的是負荷-容量模型。Moreno等在文獻[3]中提出了一種研究BA無標度網絡的相繼故障模型，該模型是負荷-容量模型中的一種。他們利用Weibull分布，賦予網絡中每個節點一個安全閾值，并且假設每個節點承擔相同的負荷，一旦某個節點的負荷超出其閾值則說明該節點發生了故障。而Motter等在文獻[10]中提出并研究了另一種模型，也就是最經典的ML負荷模型。ML模型規定：對于一個給定的具有N個節點的網絡，如果信息或能量總是在節點對之間沿著最短路徑交換，那么定義節點的負荷為該節點的介數，它反映了網絡中通過該節點的最短路徑的數目。同時，定義節點容量與節點負荷呈線性關系。一旦節點負荷超過其自身容量，則該節點發生故障。文獻[11-12]在負荷-容量模型的基礎上對小世界網絡和無標度網絡的相繼故障傳播機制進行了研究，得出無標度網絡對隨機節點故障具有較高的魯棒性，但是對蓄意攻擊表現出高度的脆弱性。這表明相繼故障的傳播機制針對不同的網絡模型所表現出的特性是不一樣的。

文中提出基于節點最大剩余容量的負荷再分配策略，其實質也是一種全局負荷再分配策略。與以往的全局負荷再分配策略相比，當網絡中某一節點出現故障，故障節點的負荷不再分配給網絡內所有處于正常狀態的節點，而是選擇處于正常狀態節點中剩余容量最大的部分節點進行分配。這樣做的好處在于：以往的全局負荷再分配策略在網絡出現故障后，選擇所有處于正常狀態的節點作為可分配節點，但是這些節點中有些節點的負荷已經近乎滿容量。對于這部分節點它們已經沒有足夠大的剩余容量來處理所分得的負荷，這樣并不利于網絡魯棒性的提高。另一方面，舉電力網為例，把電能從一個地點輸送到另一個地點是會存在電能損耗的，對應到網絡模型中這部分損耗實際上是節點之間分配負荷所需的成本。顯然，文中所提出的負荷再分配策略選擇剩余容量最大的部分節點作為可分配節點，相比于以往的全局再分配策略，可分配節點個數變小，分配成本更低。

2 負荷再分配策略

假設網絡中節點i發生故障，節點j是當前時刻網絡內剩余容量最大的部分節點之一。定義節點j能從節點i處分得的負荷占故障節點i的負荷比例為pij：

(1)

其中，Cj-Lj表示節點j的剩余容量；ki表示節點i的度；Γki表示當節點i發生故障時網絡內剩余容量最大的前ki個節點所組成的集合，節點j∈Γki。

在節點i發生故障后，之所以選擇前ki個剩余容量最大的節點作為可分配節點，是因為網絡中度的大小通常是表示一個節點重要性的指標，直觀上看，一個節點的度越大意味著這個節點在某種意義上越“重要”。所以度越大的節點發生故障時，影響的節點個數應該越多，也就是故障節點選擇的可分配節點個數越多。相反，一個節點的度越小，影響的節點個數也越小，選擇的可分配節點個數越少。

節點j所能分得的負荷ΔLij為：

ΔLij=Lipij

(2)

(3)

此時節點j的負荷更新為：

Lj←Lj+ΔLij

(4)

當Lj>Cj，說明節點j所獲得的負荷已經超過其容量，則網絡的相繼故障開始觸發?；诠濣c最大剩余容量的負荷再分配策略由于在每次節點發生故障時，都是選擇網絡內剩余容量最大的部分節點，盡可能實現了負載均衡，所以能很好地提高網絡的魯棒性。

3 仿真分析

根據文中所提出的負荷再分配策略，主要在BA網絡和WS小世界兩種人工網絡上做了仿真研究。同時也在美國電力網絡的網絡拓撲上進行了研究。其中BA網絡從一個具有m0個節點的全連通網絡開始構造，每次引入一個新的節點連接到m個已經存在的節點上，網絡的最終節點個數為N。選取網絡節點個數N為500的BA網絡作為研究對象，其中BA1的初始節點數m0和連接節點數m都為3，BA2的初始節點數和連接節點數m都為4。

仿真過程中采用最大度攻擊方式[17]，即攻擊網絡中度最大的節點。同時利用網絡故障率bn[3]來量化攻擊網絡后網絡的故障規模。取ρ=1，τ=1.6，仿真過程中的網絡拓撲結構為鄰接矩陣A，aij為A中元素，若節點i和節點j之間有連邊，則aij=1，反之aij=0，網絡中不考慮自環的存在。分別對全局負荷再分配策略(GRS)和基于節點最大剩余容量的負荷再分配策略(BMRS)進行了仿真，如圖1和圖2所示。

圖1 β與bn的關系圖(BA1)

圖2 β與bn的關系圖(BA2)

以上仿真圖表示在兩種分配策略下，攻擊不同的BA網絡得到的β值和網絡故障率bn的關系。其中，β代表節點初始負荷和節點容量的倍數關系；網絡故障率bn是指網絡發生相繼故障之后，失效節點個數與原網絡節點個數的比值。

分析以上的仿真圖，β從1開始增大，兩種分配方式下的網絡故障率bn一開始都為1，表明網絡在受到攻擊后，所有節點都發生了故障，網絡中并不存在連通子圖，也就是說整個網絡已經崩潰。這是因為β的值還不夠大，節點的剩余容量比較小，節點不具備處理額外負荷的能力?？梢赃@么理解，一個網絡雖然處于正常狀態，但是它的每個節點的負荷已經近乎滿容量，那么該網絡在受到攻擊以后很容易會使整個網絡發生崩潰。隨著β的增大，兩種分配方式下的bn都會在β達到一個定值后從1開始減小，這表明網絡在遭受攻擊以后，不會使整個網絡發生崩潰，網絡中存在連通子圖，表明此時網絡內部節點已經可以處理部分額外負荷。而當bn達到最小值，此時的β所對應的值為βm。表明網絡遭受攻擊以后，只有遭受攻擊的節點，或者極少部分的節點會從網絡中斷開成為失效節點，而并不會引起網絡大規模的相繼故障，說明此時網絡已經完全有能力處理額外負荷。當β≥βm，由于網絡中每個節點都有能力來處理額外負荷，bn不變，相繼故障將不會出現在網絡中，顯然βm是網絡避免相繼故障出現的一個重要指標。βm被稱為臨界閾值[15]，在一些實際網絡里βm和網絡的設計成本呈正相關的關系。βm越小，網絡的設計成本越低，網絡魯棒性越強。

通過仿真得到，在網絡BA1中，由BMRS得到的βm為1.50，由GRS得到的βm為1.61。在網絡BA2中，由BMRS得到的βm為1.36，由GRS得到的βm為1.44。這說明同一個網絡受到攻擊時，采用BMRS相比于GRS所能得到的臨界閾值更小。說明文中所提出的負荷再分配策略能有效減小網絡的臨界閾值βm，提高網絡魯棒性。

對小世界網絡也進行了仿真。在構造WS小世界網絡時，初始時刻的網絡模型是最近鄰耦合網絡，網絡中的每個節點與左右相鄰的各K/2個節點相連，p為重連概率。這里同樣選取節點個數N為500的WS小世界網絡作為研究對象。其中，WS1的初始K值為4，WS2的初始K值為6，所有WS小世界網絡的重連概率p都為0.01。采用最大度攻擊方式，仿真結果如圖3和圖4所示。

圖3 β與bn的關系圖

在網絡WS1中，由BMRS得到βm為1.43，由GRS得到的βm為1.49。在網絡WS2中，由BMRS得到的βm為1.23，由GRS得到的βm為1.33?？梢园l現BMRS能有效減小臨界閾值，仿真結果與BA網絡的情況相同。

圖4 β與bn的關系圖(WS2)

為了使結論更具說服力，又選用了美國電力網的網絡拓撲進行了仿真。該網絡拓撲的節點個數為4 941，邊數為6 594，平均度為2.67，仿真結果如圖5所示。

圖5 美國電力網β和bn的關系

同樣得到了和人工網絡中相同的結論，BMRS能夠減小臨界閾值、提高網絡魯棒性。

4 結束語

文中提出了基于節點最大剩余容量的負荷再分配策略，相比于以往的全局負荷再分配策略，選擇當前時刻剩余容量最大的部分節點作為可分配節點，減少了可分配節點的數量，降低了分配成本。同時由仿真可得，該策略也減小了臨界閾值βm，提高了網絡魯棒性。與全局負荷再分配策略相比有其優越性。

然而文中的研究主要針對的是BA無標度網絡、WS小世界網絡以及美國電力網，并沒有對更多的網絡模型作深入探討。在基于節點最大剩余容量的負荷再分配方式下，網絡平均路徑長度的增大會不會對臨界閾值有顯著影響，如果有影響又會是一種怎樣的方式，這種分配方式運用到其他的實際網絡模型中又有哪些不足，這些都是后續要進一步研究的內容。

[1]AlbertR,AlbertI,NakaradoGL.StructuralvulnerabilityoftheNorthAmericanpowergrid[J].PhysicalReviewE,2004,69(2):025103.

[2]StrogatzSH.Exploringcomplexnetworks[J].Nature,2001,410(6825):268-276.

[3]MorenoY,GómezJB,PachecoAF.Instabilityofscale-freenetworksundernode-breakingavalanches[J].EPL,2002,58(4):630.

[4]DobsonI,CarrerasBA,LynchVE,etal.Complexsystemsanalysisofseriesofblackouts:cascadingfailure,criticality,andself-organization[J].BulkPowerSystemDynamicsandControl-VI,Cortinad’AmpezzoItaly,2002,17(2):438-451.

[5]WattsDJ.Asimplemodelofglobalcascadesonrandomnetworks[J].ProceedingsoftheNationalAcademyofSciencesoftheUnitedStatesofAmerica,2002,99(9):5766-5771.

[6]DobsonI,ChenJ,ThorpJS,etal.Examiningcriticalityofblackoutsinpowersystemmodelswithcascadingevents[C]//Proceedingsof35thHawaiiinternationalconferenceonsystemsciences.Hawaii:[s.n.],2002:63-72.

[7]GohKI,LeeDS,KahngB,etal.Sandpileonscale-freenetworks[J].PhysicalReviewLetters,2003,91(14):148701.

[8]DobsonI,CarrerasBA,NewmanDE.Aprobabilisticloading-dependentmodelofcascadingfailureandpossibleimplicationsforblackouts[C]//Proceedingsof35thHawaiiinternationalconferenceonsystemsciences.Hawaii:[s.n.],2003:1-8.

[9]WangXF,XuJ.Cascadingfailuresincoupledmaplattices[J].PhysicalReviewE,2004,70(5):056113.

[10]MotterAE,LaiYC.Cascade-basedattacksoncomplexnetworks[J].PhysicalReviewE,2003,66(6):114-129.

[11]ZhaoL,ParkK,LaiYC.Attackvulnerabilityofscale-freenetworksduetocascadingbreakdown[J].PhysicalReviewE,2004,70(3):035101.

[12]ZhaoL,ParkK,LaiYC,etal.Toleranceofscale-freenetworksagainstattack-inducedcascades[J].PhysicalReviewEStatisticalNonlinear&SoftMatterPhysics,2005,72(2):025104.

[13]XiaY,FanJ,HillD.CascadingfailureinWatts-Strogatzsmall-worldnetworks[J].PhysicaA:StatisticalMechanics&ItsApplications,2010,389(6):1281-1285.

[14]WangWX,ChenG.Universalrobustnesscharacteristicofweightednetworksagainstcascadingfailure[J].PhysicalReviewE,2008,77(2):026101.

[15]WangJ,RongL,ZhangL.Amodelforcascadingfailuresincomplexnetworkswithatunableparameter[J].ModernPhysicsLettersB,2009,23(10):1323-1332.

[16]DuanDL,LingXD,WuXY,etal.Criticalthresholdsforscale-freenetworksagainstcascadingfailures[J].PhysicaA:StatisticalMechanics&ItsApplications,2014,416:252-258.

[17]AlbertR,JeongH,BarabásiAL.Errorandattacktoleranceofcomplexnetworks[J].Nature,2000,406(6794):378-382.

Research on Load Redistribution Strategy Based on Maximum Remaining Capacity of Node

ZHOU Tian-jie,JIANG Guo-ping

(School of Automation,Nanjing University of Posts and Telecommunications,Nanjing 210023,China)

In order to improve the network robustness in the process of cascading failure,a reasonable and effective load redistribution strategy of the cascading failure nodes in the network is designed,so that the critical thresholdβmcanbedecreased.Throughcomparativestudyandsimulationmodelingmethod,aloadredistributionstrategybasedonthemaximumremainingcapacityofthenodeisputforward.Theloadofafailurenodewillbedistributedtothenodesthathavethemaximumremainingcapacityinthenetwork,andthenumberofthesenodesisthedegreeofthefaultnode,andtheextraloadwhichthesenodessharedependsontheirremainingcapacity.Throughthesimulationbetweentheartificialnetworkandactualnetwork,theresultsshowthattheproposedstrategyoftheloadredistributioncaneffectivelydecreasethecriticalthresholdβm,soastoshowtheeffectivenessofthestrategyandimprovetherobustnessofthenetwork.

complex networks;cascading failures;load redistribution;network robustness

2016-01-20

2016-05-11

時間：2016-10-24

國家自然科學基金資助項目(61374180)

周添杰(1990-)，男，碩士研究生，研究方向為復雜系統和網絡控制；蔣國平，教授，博士生導師，研究方向為混沌系統同步與控制、混沌信息處理與混沌通信系統設計、復雜網絡理論。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1113.034.html

TP

A

1673-629X(2016)11-0063-04

10.3969/j.issn.1673-629X.2016.11.014