Stochastic dynamic network interdiction games
Stochastic dynamic network interdiction games
复制标题
随机动态网络拦截博弈
DOI：
10.1109/acc.2012.6315444
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
D. Castañón
中科院分区：
文献类型：
--
作者：
Jiefu Zheng;D. Castañón
网络拦截问题包括攻击者和智能网络之间的博弈，攻击者试图降低网络运行，而网络则调整其运行以抵消攻击者的影响。近年来，由于与军事问题和网络安全相关，这个问题受到了极大的关注。当攻击者的行为达到不确定的效果时，所产生的问题成为随机网络拦截问题，并允许玩家适应在游戏过程中收集到的新信息。本文研究随机网络拦截对策，其中攻击者有一个或两个阶段攻击网络，并且可以收集先前攻击结果的信息。对于单阶段问题，我们开发了一种新的求解算法，该算法基于分支和界技术的简约积分，下界越来越精确，求解速度明显快于以往文献中的方法。我们将单阶段公式推广到两阶段公式，并为该问题开发了一组新的性能界。我们将这些边界集成到一个改进的分支和绑定过程中，该过程将单阶段方法扩展到两个阶段。通过前人研究的网络模拟实验证明了新算法的有效性。
Network interdiction problems consist of games between an attacker and an intelligent network, where the attacker seeks to degrade network operations while the network adapts its operations to counteract the effects of the attacker. This problem has received significant attention in recent years due to its relevance to military problems and network security. When the attacker's actions achieve uncertain effects, the resulting problems become stochastic network interdiction problems, and allow the players to adapt to new information collected during the game. In this paper, we study stochastic network interdiction games where the attacker has one or two stages to attack the network, and can collect information on the outcomes of previous attacks. For the single stage problem, we develop a new solution algorithm, based on parsimonious integration of branch and bound techniques with increasingly accurate lower bounds, that obtains solutions significantly faster than previous approaches in the literature. We extend the single stage formulation to a two stage formulation, and develop a new set of performance bounds for this problem. We integrate these bounds into a modified branch and bound procedure that extends the single stage approach to two stages. The efficacy of the new algorithms is shown using simulated experiments with networks studied in previous papers.