面向最短路的網絡阻斷問題研究.pdf

1、重要網絡的攻擊和防護問題通常可以用網絡阻斷模型來建模。經典的網絡阻斷問題是單一目標的，面向單層網絡的，可能導致在達到阻斷效果最大化時資源的消耗不是最優(yōu)，突出表現(xiàn)在存在多組解的情況下，模型并不能自動給出資源消耗更少的解。現(xiàn)實世界中的網絡系統(tǒng)越來越呈現(xiàn)出多層重疊(Overlay Networks)特性即多個網絡系統(tǒng)相互耦合，之前的研究大多將網絡分開來建?；蛘邇H僅考慮網絡之間很少的可認知的相互關系，如地理重疊關系；目前的網絡模型都不能很好的描

2、述存在相互依賴關系的多層網絡。在本研究中，我們首先基于最短路阻斷問題提出了一個新的阻斷問題變種—MINIR，即在限制對手網絡能力達到我方滿意的閾值的情況下，阻斷資源的消耗最少的問題。我們首先基于單層網絡構建了基本模型；按照對偶和分解兩種求解思路，分別提出了基于拉格朗日松弛的基本對偶算法和基于Be nde rs分解的基本分解算法，并分別對兩種算法分別進行了拓展。然后嘗試研究了多層網絡阻斷問題的研究思路，對于層間關系我們選取了具有代表性的反

3、饋關系，并給出了雙層網絡閾值最短路的阻斷模型，然后進行了求解。最后我們利用構建的不同類型的測試網絡對算法本身的性質和效率進行了測試，并在實際路網上對算法進行了模擬。
　　對于大型的多層網絡，即便是存在求解模型，也是極為復雜難以在有效的時間內求解和分析的。目前對于層間關系的描述方法大多數(shù)采用的是復雜網絡的方法，不能給出軍事行動中所需求的準確的、清晰的阻斷方案。文章采用運籌學優(yōu)化的方法清晰的表示出網絡間相互依賴關系，在此基礎上完成面向