基于流量強度的復雜保障網(wǎng)絡抗毀性研究

基于流量強度的復雜保障網(wǎng)絡抗毀性研究

節(jié)點級聯(lián)失效在現(xiàn)代戰(zhàn)爭中，軍事物流是決定戰(zhàn)爭結果的重要因素。當前的保障網(wǎng)絡系統(tǒng)是以各種不同屬性的倉庫、轉(zhuǎn)運中心、存儲中心和交通樞紐為節(jié)點,以各種交通線路為邊,以各種補給、保障物資為負載,所構成的一個節(jié)點數(shù)目龐大,連接方式多樣的復雜網(wǎng)絡,這種網(wǎng)絡稱之為復雜保障網(wǎng)絡,也是敵方攻擊的主要目標之一。因此,采用復雜網(wǎng)絡理論來研究其抗毀性有非常重要的理論和現(xiàn)實意義。復雜網(wǎng)絡抗毀性研究主要包括網(wǎng)絡拓撲結構靜態(tài)抗毀性研究和基于負載的復雜網(wǎng)絡抗毀性研究。早期的復雜網(wǎng)絡抗毀性研究主要關注靜態(tài)的抗毀性,不考慮節(jié)點(邊)失效的動態(tài)關聯(lián),即總是假設一個節(jié)點(邊)的失效不會導致其他節(jié)點(邊)的失效。這方面研究最重要的成果就是無標度網(wǎng)絡的雙重性:面對隨機性的損傷,無標度網(wǎng)絡比隨機網(wǎng)絡有著更好的抗毀性,但面對選擇性型打擊,無標度網(wǎng)絡卻顯得異常脆弱,在這種假設下,少數(shù)幾個節(jié)點的失效不會導致整個網(wǎng)絡的崩潰,然而事實并非如此,實際上大多數(shù)網(wǎng)絡上是有負載的,這些負載可以是物質(zhì)、信息或能量,可以是具體的,也可以是抽象的,網(wǎng)絡上的負載是動態(tài)變化的,特別是當網(wǎng)絡結構發(fā)生改變,如節(jié)點的加入、移除,網(wǎng)絡上的負載將重新分配,一般來說,網(wǎng)絡中節(jié)點的容量是有限的,有限的容量和負載的重新分配使得負載網(wǎng)絡的抗毀性問題變得更加復雜:一個節(jié)點的失效導致網(wǎng)絡負載的重分配,負載的重分配可能使得某些節(jié)點上的負載超過其容量而失效,這些節(jié)點的失效又可能導致其他節(jié)點的“級聯(lián)失效(cascadingfailure)”,如果開始移除的是一個重要的“關鍵節(jié)點”,它的移除可能觸發(fā)整個網(wǎng)絡的崩潰,稱之為“級聯(lián)崩潰(cascadingbreakdown)”。這種現(xiàn)象比故意攻擊網(wǎng)絡的后果更嚴重。級聯(lián)失效的本質(zhì)是一種相關失效,而網(wǎng)絡安全中的相關失效行為一直是一個非常棘手的問題,這源于對網(wǎng)絡中相關失效機理知之甚少,特別是定量分析方法非常缺乏。復雜網(wǎng)絡上的級聯(lián)失效研究近年來得到了很大關注。2002年,Watts給出了一個級聯(lián)失效過程的簡單模型,它能轉(zhuǎn)換到一類滲流模型之上,從而可以利用與針對簡單頂點刪除過程而言類似的生成函數(shù)方法來解決。Moreno等人提出一種研究BA無標度網(wǎng)絡中的相繼故障模型,發(fā)現(xiàn)節(jié)點容量閾值分布較均勻的網(wǎng)絡對故障更有承受能力。Motter研究發(fā)現(xiàn)非同質(zhì)拓撲結構中級聯(lián)失效對選擇性打擊的敏感性,并在2004年研究了級聯(lián)失效的防御和控制,Dobson等研究了電力網(wǎng)中的級聯(lián)失效問題,汪小帆研究了耦合映象格子中的級聯(lián)失效。2006年,Schafer等提出了一種增加網(wǎng)絡級聯(lián)失效抗毀性的設計方法,該方法通過負載和權重的轉(zhuǎn)換使得網(wǎng)絡負載分布更均勻,并通過減少網(wǎng)絡總負載提高網(wǎng)絡抗毀性。2007年,WANGBing等提出了一種低代價下的高抗毀性模型。已有的基于級聯(lián)失效抗毀性模型大多假設所有節(jié)點對之間發(fā)送的流量相同,都為一個單位,很少考慮網(wǎng)絡中節(jié)點之間流量的差異性。實際的網(wǎng)絡中(例如通信網(wǎng)路,交通網(wǎng)絡等),不同的時刻(例如流量高峰期和非高峰期)網(wǎng)絡的流量強度不同,在同一時刻,不同的節(jié)點對之間(例如交通網(wǎng)絡中的商業(yè)區(qū)之間的節(jié)點對和郊區(qū)間的節(jié)點對)發(fā)送的流量也不相同。針對復雜保障網(wǎng)絡流量的特點,本文通過引入流量強度指數(shù)和流量分布指數(shù)等建立了不同流量下的復雜保障網(wǎng)絡級聯(lián)失效抗毀性模型,分析了復雜保障網(wǎng)絡在不同流量強度和不同流量分布下的抗毀性。1復雜保障網(wǎng)絡的組成1.1車站、機場、公路路口在復雜保障網(wǎng)絡中,盡管基地、兵站、綜合倉庫、彈藥庫、修理所、醫(yī)院等保障實體在功能上有所不同,有的實體在功能上還相互包含,但是,它們有一個共同的特點就是發(fā)出或接收資源,并且,在某段時間內(nèi),各保障實體在地域上具有相對固定的關系。我們把所有的保障實體、路口以及被保障實體抽象為節(jié)點。路口包括:火車站、汽車站、中轉(zhuǎn)站以及公路路口等。抽象后的網(wǎng)絡節(jié)點可以分為兩類:連通節(jié)點、倉庫節(jié)點。連通節(jié)點,是指該節(jié)點毀傷以后,連接到該節(jié)點的路徑即在該位置失效,如果該節(jié)點連接到保障倉庫,則所有資源在該節(jié)點恢復連通之前將不能通過該節(jié)點運出;如果連接到該節(jié)點的邊上有向該節(jié)點運送的物資,則這些物資原路返回,到前一節(jié)點重新路由或者等待。例如交通要道上的立交橋,一旦被炸毀,則所有連接到該橋梁的道路不能夠再運輸資源,如果有一保障倉庫只能通過一條道路連接到該橋梁,而與其他道路沒有連接,則該資源將被封閉在庫所內(nèi),直到橋梁修復方可進行運輸,如果有其他正常的交通路口節(jié)點與之連接,從該交通路口節(jié)點到損壞的立交橋節(jié)點之間的物資源路返回;倉庫節(jié)點又可分為源倉庫節(jié)點和匯倉庫節(jié)點,源倉庫節(jié)點是指保障實體倉庫,為發(fā)送物資倉庫;匯倉庫節(jié)點是指被保障實體倉庫,為接收物資倉庫。有些倉庫既是源倉庫節(jié)點又是匯倉庫節(jié)點,因為它們可以作為上一級保障系統(tǒng)中的被保障實體,又可以作為下一級保障系統(tǒng)中的保障實體。1.2節(jié)點/邊負載量各節(jié)點之間相互連接依靠的是傳輸線路,如:公路、鐵路、水路、航線、管線。這些傳輸線路就是網(wǎng)絡的邊,與節(jié)點一起構成復雜保障網(wǎng)絡。負載量是指在某一時刻,網(wǎng)絡上的節(jié)點或者邊上運載物資的量,分別稱為節(jié)點負載量和邊負載量。容量是網(wǎng)絡中節(jié)點和邊可承受的最大的負載量。1.3交通網(wǎng)絡拓撲特性復雜保障網(wǎng)絡主要由民用交通網(wǎng)絡(鐵路網(wǎng)、公路網(wǎng)和水路網(wǎng)等)和不同級別的保障實體構成,復雜保障網(wǎng)絡的拓撲特性依賴交通網(wǎng)絡的拓撲特性,已有的研究中已經(jīng)發(fā)現(xiàn)公路網(wǎng)和鐵路網(wǎng)的節(jié)點度分布服從衰減指數(shù)分布,本文以某團的保障網(wǎng)絡(圖1)為研究對象,節(jié)點表示交通樞紐和保障實體,邊表示高速公路、國道、省級公路和縣級公路,邊和節(jié)點的位置和地圖近似,但不完全重合,邊長也不代表道路實際長度。2有向加權連通復雜網(wǎng)絡抗毀性研究中,用圖G=(V,E)來表示網(wǎng)絡。假設G是一個無向的加權連通圖,有n個節(jié)點,m條邊,其中V={v1,v2,v3,…,vn}代表節(jié)點集合E={e1,e2,e3,…,em}?V×V,代表邊的集合。2.1節(jié)點度大小的變化本模型中,定義網(wǎng)絡流量強度為某一時刻進入網(wǎng)絡的流量總和,即在某一時刻所有節(jié)點對之間發(fā)送流量的總和。定義網(wǎng)絡流量分布為網(wǎng)絡中所有節(jié)點對之間發(fā)送流量的空間分布。網(wǎng)絡流矩陣為U=[f11?f1k?f1n?fj1?fjk?fjn?fn1?fnk?fnn](1)fjk為運載函數(shù),表示節(jié)點vj發(fā)送給節(jié)點vk的流量。流量強度NF=∑fjk,表示所有發(fā)送流量的總和。本文中假設:fjk={α×(dβj/2+dβk/2)?nn∑j=1dβj(j≠k,0≤α≤1)0(j=k)(2)dj和dk分別表示節(jié)點vj和vk的度。α為流量強度指數(shù),用來調(diào)節(jié)發(fā)送流量的多少。當α=1,fjk=fmaxjk表示節(jié)點對vj,vk之間發(fā)送最大流量。β為流量分布指數(shù),用來表示運載函數(shù)和度的關聯(lián)程度。這樣可以得到:ΝF=∑fjk=∑j≠kα×(dβj/2+dβk/2)?nn∑j=1dβj=α.nn∑j=kdβj×∑j∑k≠j(dβj/2+dβk/2)=α.n2n∑j=1dβj×∑j((n-2)dβj+n∑k=1dβk)=α.n2n∑j=1dβj×((n-2)×n∑j=1dβj+n×n∑k=1dβk)=α.n2n∑j=1dβj×(2n-2)n∑j=1dβj=α.n(n-1)(3)流量強度NF由網(wǎng)絡的大小n和流量強度指數(shù)α決定,跟β無關。這樣改變α的大小就可以改變流量強度。當β>0時表示fjk跟節(jié)點的度正相關,節(jié)點的度越大,該節(jié)點越重要,發(fā)送的流量越多,這時,稱網(wǎng)絡流量分布跟網(wǎng)絡度分布同配;β<0時表示fjk跟節(jié)點的度負相關,節(jié)點的度越大,該節(jié)點越不重要,發(fā)送的流量越少,這時,稱網(wǎng)絡流量分布跟網(wǎng)絡度分布異配;當β=0,α=1,就表示所有節(jié)點對之間發(fā)送的流量都為一個單位,和已有模型的假設一致。本模型中,在流量強度NF不變(α值不變)的條件下,改變β值,可以改變網(wǎng)絡的流量分布。2.2節(jié)點之間的流量本模型中,定義節(jié)點vi的負載量Fi(i=1,2,3,…,n),為所有節(jié)點對vj,vk之間按照最短路(如時間最短、距離最短)原則發(fā)送的物資,經(jīng)過節(jié)點vi的流量的和Fi=∑j≠kfjk(i)(i=1,2,3??,n)(4)fjk(i)為節(jié)點對vj,vk之間發(fā)送fjk的物資經(jīng)過節(jié)點vi的流量。2.3節(jié)點容量計算節(jié)點的容量表示節(jié)點可以承受的最大負載量。本模型中,定義節(jié)點vi的容量Ci=Fmaxi=∑j≠kfmaxjk(i)(i=1,2,3,?,n)(5)fmaxjk(i)表示所有節(jié)點對vj,vk之間發(fā)送最大物資量fmaxjk(α=1)時經(jīng)過節(jié)點vi的流量。2.4節(jié)點或和邊故障的網(wǎng)絡負載重分配基于級聯(lián)失效的抗毀性模型的負載重分配策略有很多形式。在本模型中,假設當某個節(jié)點或(和)邊出現(xiàn)故障的時候,經(jīng)過這些損壞節(jié)點或邊的運輸物資將按重新計算出來的最短路運輸,實現(xiàn)了網(wǎng)絡負載重分配。2.5級聯(lián)故障的形成過程在本模型中,節(jié)點的“初始攻擊(initialdamage)”被處理為刪除一個節(jié)點,初始節(jié)點的刪除將導致網(wǎng)絡負載的重分配,由于網(wǎng)絡中節(jié)點的最大容量是確定的,重分配的負載可能會超過某些節(jié)點的容量,從而使這些節(jié)點出現(xiàn)級聯(lián)故障,這些級聯(lián)故障節(jié)點又可能產(chǎn)生下一輪的負載重分配,繼而出現(xiàn)新的級聯(lián)故障,這個級聯(lián)過程可延續(xù)到?jīng)]有新的級聯(lián)故障節(jié)點出現(xiàn)才會停止。在剩余網(wǎng)絡(節(jié)點刪除以后的網(wǎng)絡)中,網(wǎng)絡可能被分割成一些不連通的子網(wǎng)和孤立節(jié)點,子網(wǎng)內(nèi)部可以實現(xiàn)相互間的流量發(fā)送,而孤立節(jié)點則不具備流量的發(fā)送和接收能力。2.6形成網(wǎng)絡攻擊的抗毀性在本文中,用級聯(lián)失效后網(wǎng)絡的最大連通片尺寸與網(wǎng)絡尺寸之比R來度量網(wǎng)絡的抗毀性,即N表示網(wǎng)絡在攻擊以前網(wǎng)絡節(jié)點的數(shù)目,N′表示在攻擊以后最大連通尺寸中節(jié)點的數(shù)目。3模擬分析3.1模擬設計仿真設計主要包括網(wǎng)絡結構、攻擊形式的設計,以及對網(wǎng)絡在不同流量強度和不同流量分布下抗毀性的比較分析。3.1.1隨機網(wǎng)絡模型本文主要關心網(wǎng)絡流量對不同的拓撲結構網(wǎng)絡的抗毀性影響,分別以BA模型生成的無標度網(wǎng)絡、ER模型生成的隨機網(wǎng)絡和團一級的復雜保障網(wǎng)絡作為研究對象。在本文中,BA網(wǎng)絡初始節(jié)點n0=2,每個時間步增加一個節(jié)點和m=2條邊,平均度ˉdk≈4。ER隨機網(wǎng)絡中任意兩節(jié)點的連接概率p=0.04,平均度djˉ≈4。復雜保障網(wǎng)絡平均度diˉ≈4。3.1.2仿真過程中故意攻擊本文主要考慮網(wǎng)絡在故意攻擊和隨機失效兩種條件下的抗毀性。在仿真過程中故意攻擊是指移除網(wǎng)絡中負載量最大的單個節(jié)點;隨機失效是指隨機的移除網(wǎng)絡中的單個節(jié)點。3.1.3節(jié)點的抗毀性首先比較分析不同的流量強度下(不同α)每種網(wǎng)絡對于單個節(jié)點移除的抗毀性;然后比較分析不同的流量分布下(不同β)每種網(wǎng)絡對于單個節(jié)點移除的抗毀性,模型中,α的取值范圍是0<α≤1,α=1表示滿負荷運行,節(jié)點對之間最大量的發(fā)送流量,所有節(jié)點的負載都達到容量的極限,β的取值范圍是-3<β<3,這是由于實際網(wǎng)絡中節(jié)點的度相差很大,發(fā)送流量的差將以指數(shù)的形式縮放(如節(jié)點vj,vk的度都為1,節(jié)點vm,vn的度都為10,β=3時,vm,vn的流量將是vj,vk流量的1000倍),對于復雜保障網(wǎng)絡而言,-1<β<1更符合實際情況。3.2模擬結果3.2.1流量強度e的影響圖2中,(a)圖表示ER隨機網(wǎng)絡在不同的流量強度下對于單個節(jié)點移除的抗毀性;(b)圖表示BA網(wǎng)絡在不同流量強度下對于單個節(jié)點移除的抗毀性;(c)圖表示復雜保障網(wǎng)絡在不同流量強度下對于單個節(jié)點移除的抗毀性。其中空心圓表示故意攻擊(IntentionalAttacks);實心圓表示隨機失效(RandomFailure)。圖的橫軸表示α,用來度量流量強度,圖的縱軸表示最大連通片比R,用來度量網(wǎng)絡的抗毀性。通過分析仿真結果發(fā)現(xiàn):隨機網(wǎng)絡(圖2(a))在流量強度不大的時候?qū)蝹€節(jié)點的移除表現(xiàn)出很強的抗毀性,在α的一段變化區(qū)間內(nèi)(α<0.5),網(wǎng)絡隨著α的變化,抗毀性曲線幾乎沒有變化;隨機失效和故意攻擊都存在一個α臨界點α*,當α<α*,網(wǎng)絡完好,當α>α*,網(wǎng)絡開始級聯(lián)失效,隨機失效中α*≈0.7,故意攻擊中α*≈0.5。無標度網(wǎng)絡(圖2(b))中,網(wǎng)絡對于隨機失效和故意攻擊的抗毀性差異很大,隨機失效在α=0.7的時候網(wǎng)絡的抗毀性仍然很好(R>0.9),甚至在網(wǎng)絡接近飽和狀態(tài)時(α=0.9),網(wǎng)絡的抗毀性指標還可以達到70%以上;相反,故意攻擊在流量強度很小的時候就出現(xiàn)級聯(lián)失效(α*=0.2),在α=0.7的時候,網(wǎng)絡幾乎崩潰(R<0.15)。復雜保障網(wǎng)絡(圖2(c))中,故意攻擊的α臨界點在α很小的時候就出現(xiàn)了(α*≈0.1),在α=0.4時,網(wǎng)絡抗毀性指標(R)已經(jīng)降到40%以下;隨機失效的α臨界點為α*≈0.7,在流量強度達到滿負荷時(α≈1),保障網(wǎng)絡對于隨機失效的抗毀性指標(R)依然能達到50%以上,這說明復雜保障網(wǎng)絡對于隨機失效有較好的抗毀性,對于故意攻擊的抗毀性很差。3.2.2無標度網(wǎng)絡、復雜保障網(wǎng)絡的抗毀性本文旨在研究復雜保障網(wǎng)絡中流量分布對于抗毀性的影響,在模型中,通過改變β,可以改變網(wǎng)絡流量分布,如圖3所示,這里主要關注-1<β<1。通過仿真結果可以發(fā)現(xiàn):在同樣的網(wǎng)絡流量強度不同的流量分布下(不同β)網(wǎng)絡對于隨機失效的抗毀性差異很大,隨機網(wǎng)絡(圖3(a))中,網(wǎng)絡抗毀性隨β遞增而遞減。無標度網(wǎng)絡(圖3(b))的曲線是先遞減后遞增的,在β=1附近出現(xiàn)最小值。但對于-1<β<1區(qū)間,曲線也是明顯遞減的。復雜保障網(wǎng)絡(圖3(c))曲線的變化趨勢沒有前面兩個那么明顯,變化幅度也沒有那么大,但是仍然呈先減后增的趨勢。在β=-1時,抗毀性要比β=1時好。