基于网络最大流的网络目标选择模型

喻飞飞,胡友涛,王 剑

(火箭军指挥学院,湖北 武汉 430012)

基于网络最大流的网络目标选择模型

喻飞飞,胡友涛,王 剑

(火箭军指挥学院,湖北 武汉 430012)

针对网络目标选择问题,引入网络最大流进行目标价值评估,结合网络阻断量和成本控制的限制性条件,构建网络目标选择模型。算例分析验证了模型的可操作性和实用性。该模型能够有效解决网络目标选择的价值衡量问题,并可作为对网络目标选择问题进行深入研究的基础。

网络目标选择;最大流;价值评估;模型

1 问题的提出

目标选择是作战筹划的重要内容,也是信息化条件下联合作战的首要问题,目标选择是否科学合理,直接影响战争的成败。新形势下的目标选择面对的往往不再是单一、孤立的目标,而是多个目标按照一定的秩序和内部联系进行组合形成的整体,即目标体系。由于政治影响、成本、附带毁伤风险等多方面的因素制约,我们不可能将整个目标体系列为打击目标,往往需要在目标体系中选择一些关键的节点性目标进行打击。实际上,只要选准了关键目标,就极有可能造成“无差别攻击”同样的效果。如美军认为,只要摧毁作战体系中20%的“关键目标”,整个体系就会陷入瘫痪或崩溃。这已经在科索沃战争和伊拉克战争中得到了证明。因此,目标选择的重点就在于如何找到这些“关键目标”。

从系统的角度来看,很多作战体系都是由节点和链路组成的网络,如指挥信息系统、情报获取系统、后勤运输系统等,都是由若干节点和链路进行有效组合,实现命令下达、信息传输、给养配送等功能。对这类网络系统,我们往往最关注的是切断或者尽量减少其网络传输量,进而造成该作战系统效能降低甚至完全失效。也就是说,对于网络系统的目标选择问题,我们可以通过系统内各节点目标对于整个网络传输的影响度来进行评估和选择,而节点目标的网络影响度则可以通过网络最大流的变化情况来进行分析和计算。

2 网络最大流

“流”通常是指物质在不同系统之间的转移运行。现实生活中,很多系统都包含了“流”的问题,如公交系统中有车辆流,供水系统中有水流,金融系统中有现金流,军事系统中有人流、信息流、物资流等。其共同的特点是,至少有一个出发点和收点,有若干个中间点,共同形成一个“流”的网络[1]。网络最大流是指从出发点到收点能“流”过的最大流量,它代表了网络系统实现某项功能的最大能力。以交通运输网为例,如图1所示,产品从产地V1到销地V6需要经过若干中间路线,路线旁的数字代表这条运输线的最大通过能力,则该网络的最大流就是从V1到V6的最大运输能力。

图1 交通运输网络的最大流

关于网络的最大流问题还有一些基本的概念需要了解,如可行流、增广链、截集、截量等,这些内容在相关文献中有详细介绍,本文不再详述。而求解网络最大流的方法有很多,如标号法、最短增广路算法、预留推进法、最高标号的预留推进法等,其中标号法的应用最为广泛,且更易理解。本文即采用标号法来求解网络的最大流,其基本思想为:逐步找出网络中存在的不饱和(每条线路上的流量均小于容量,或反向流量不为0)的方案流,即增广链;为该方案流增加流量至饱和,然后继续寻找增广链,直至找不到,则此时网络的实际流量(可行流)即为网络最大流。标号法求解网络最大流的基本步骤如图2所示。

图2 标号法的基本步骤

各步骤的具体内容如下:1)标号。从发点开始,逐个检查网络节点,标记两部分内容：第一部分标明该标号是从哪一点得到的,即确定检查的链路;第二部分标明该链路能够增加或减少的流量(反方向为减少),以便确定增广链的调整量。如果该链路能够增加或减少的流量均为0,则该点无法被标号。2)找增广链。一旦收点被标上号,就可以从收点开始沿着标号过程找到一条增广链。3)流量调整。增广链上各链路最大调整量的最小值即为调整量,用该调整量调整各条链路的实际流量。4)判断是否能重新标号。调整完毕后,观察判断能否继续完成标号,若能则重复步骤1)、2)、3),直至无法完成标号过程为止。5)计算最大流。计算经过调整后网络的实际流量,即为该网络的最大流。

3 基于网络最大流的目标价值评估

网络流的形成是为了方便物质的转移和运行,网络最大流越大,则物质的转移量越大,其运行也更加顺畅。因此,网络流内各目标的价值可以按照其对网络最大流的贡献程度来进行评估。基于网络最大流的目标价值评估,其基本思路为:首先计算完整状态下的网络最大流,并以此作为基数;然后去除网络流中的某一个目标,再计算去除后的网络最大流,对于该目标而言,网络最大流的改变量正是其在整个网络中的价值体现。因此,可以将网络最大流减少的百分比作为评估该目标价值的标准,其表达式如下[2]:

基于网络最大流的目标价值评估步骤如图3所示。

图3 基于网络最大流的目标价值评估步骤

4 引入网络阻断量与成本控制的目标选择模型

在目标选择的过程中,除了目标的价值外,我们还必须考虑其它的一些因素,如作战目的、作战成本、附带毁伤等,其中,指挥员最为关心的是作战目的及作战成本。因此,有必要在目标价值评估的基础上引入网络阻断量与成本控制进行综合考虑。网络阻断量,即根据作战目的确定的对网络功能的降低程度,比较常见的等级如退化、破坏、摧毁等,都对应着不同的网络阻断量。在指挥员作战筹划的过程中,必须要首先确定网络阻断量(作战目的),然后选择相应网络子目标进行打击。成本控制,即在目标选择的过程中,要使我方的作战成本最小化。虽然各类节点在网络内发挥的功能可能是相同的,但其打击成本可能并不相同(如节点的地理位置、防御程度等不同都可能引发打击成本的变化)。显然,网络阻断量与成本控制是目标选择的两个限制性条件。

引入网络阻断量与成本控制后,需要考虑如下两个问题:一是选择多少个目标，哪些目标或目标组合能够达到要求的网络阻断量？二是如何评判这些目标选择方案的优劣？第一个问题我们可以用达到预定的网络阻断量作为标准,来形成目标选择方案集;对于第二个问题,我们可以在形成目标选择方案集的基础上,用效费比来进行比较和选择。

4.1 生成目标选择方案集

要满足网络阻断量的要求,可能只需选择一个网络节点目标,也可能需要选择多个节点目标。为了生成目标选择方案集,通常的做法,是逐个将可能的移除目标组合进行检验,计算移除后是否能达到网络阻断量的要求。需要注意的是,由于节点之间的耦合作用,计算移除两个节点后的网络阻断量并不是分别移除单个节点后的网络阻断量之和,而应在移除后按照标号法重新计算。

对于某些节点过多、结构复杂的网络流,这种穷举法可能并不可取,因为需检验的移除目标组合将随着节点数量的增加呈几何级数增长,导致目标选择效率过低。此时,应放弃手工作业的标号法,而采取易于编程实现的预留推进法或增广路算法来计算网络最大流。连同判断是否达到网络阻断量这一条件一起通过计算机编程来实现。预留推进法和增广路算法的实现过程可参见文献[3-5]。

4.2 计算效费比

网络目标选择的效费比可以采用网络阻断量与打击成本的比值来实现。效费比计算公式如下:

其中,Si为第i个目标选择方案的效费比;Wi表示第i个目标选择方案的网络阻断量;j表示第i个目标选择方案选择的目标数;Ln表示其中第n个目标的打击成本。

得到各个方案的效费比后,即可选择效费比最高的方案目标作为最终选择的打击目标。

5 算例分析——指挥信息网络系统的目标选择问题

敌某个指挥信息网络的系统结构如图4所示,从指挥端A到指令终端H需要经过多个通信节点的传输,图中括号内前面的数据代表线路的通信容量,后面的数据代表某个时刻的实际流量。现要对该信息网络进行导弹攻击,考虑到通信线路的快速修复能力,一般不选择通信线路进行打击,而应选择通信节点。且各类节点的打击成本如表1所示(已经过无量纲处理)。考虑如下两种情况:一是只发射1枚导弹打击1个目标;二是不明确导弹数量,而是使该信息网络传输功能降低50%。两种情况下分别应如何选择相应的打击目标。

图4 敌指挥信息网络的系统结构

表1 各节点目标的打击成本

1)对于第一种情况,只能发射1枚导弹,即只能选择一个打击目标。根据上述目标选择模型,此时只需进行单个节点的目标价值评估并计算效费比即可。计算过程如下:

首先计算当前通信网络的最大流。按照“标号法”,并依次选择ADCFH、ACFEH、ABEH、ABCGH、ACEFH、ACFGH、ADGH作为增广链,流量调整后可以得到当前网络的最大流为16。随后,依次选取各通信节点作为目标,并计算移除该节点后的网络最大流。得到各通信节点的网络阻断量(目标价值),用该阻断量除以相对应的打击成本即可得到各目标的打击效费比,计算结果如表2所示。

表2 单个节点目标效费比

分析可知,当仅选择一个目标时,显然指挥端节点A和终端节点H的价值最高,网络阻断量达到100%,但由于其打击成本过大,效费比反而较低。这是符合客观情况的,一般而言,敌对其指挥端的防护肯定非常严密,而终端节点则存在机动性,这些都增加了打击成本。总体比较而言,目标G的效费比最高,因此应选择节点G作为打击目标。

2)对于第二种情况,我们需要逐个找出满足“功能降低50%”这一条件的目标组合。计算可知,当选取一个目标时,节点A、C、H满足这一要求;当选取二个目标时,除节点B、E组合和D、G组合外,其余组合均满足要求。于是可以在B、E组合和D、G组合的基础上考虑选择三个目标的情况。整个计算结果如表3所示。

表3 网络阻断量达到50%的目标组合效费比

比较可知,当选择节点E、G时,效费比最大,达到0.344。因此,应选择节点E、G作为打击目标。

6 结束语

本文将网络最大流问题应用于网络目标价值评估,结合网络阻断量和成本控制,构建了网络目标选择模型,最后用算例进行了验证,显示了较好的应用效果。需要指出的是,本文的研究仅考虑了网络目标选择的军事价值和成本因素,而在具体的军事实践过程中,目标选择问题往往还会涉及政治因素、战争潜力因素、人道主义因素等。如果要更加全面地考虑网络目标选择问题,还需要在本模型的基础上作进一步的深化研究,这也是下一步需要解决的问题。

[1] 钱颂迪.运筹学[M].北京：清华大学出版社,2012.

[2] 张最良.军事战略运筹分析方法[M].北京：军事科学出版社,2009.

[3] 张永军.最大流算法及其应用[J].中国科技信息,2007(24):322-323.

[4] 赵礼峰,孟晓婉.基于深度优先的一种网络最大流求解法[J].计算机技术与发展,2012，22(10):167-164.

[5] 马毅,严余松,户佐安.网络优化的最大利润问题及其增广路算法[J].计算机工程与应用,2015(1):1-4.

Model of Network Target Selection Based on Maximum Flow in Network

YU Fei-fei, HU You-tao, WANG Jian

(The PLA Rocket Force Command College,Wuhan 430012,China)

Aiming at the problem of network target selection, the paper introduces the maximum flow in network into target value assess, then it integrates the restricted factor with network interdiction and cost control, constructs the model of network target selection. The account case tests and verifies the operability and practicability of the model. The model can solve the problem of value assess in network target selection effectively, and could become the basis of thorough research in the problem of network target selection.

network target selection; the maximum flow; value assess; model

2016-11-24

喻飞飞(1982-),男,湖北公安人,博士研究生,研究方向为军事运筹。 胡友涛(1983-),男,博士研究生。 王 剑(1983-),男,博士研究生。

1673-3819(2017)01-0016-04

E835；E917

A

10.3969/j.issn.1673-3819.2017.01.004

修回日期： 2016-12-15