喻飛飛,胡友濤,王 劍

(火箭軍指揮學院,湖北 武漢 430012)

基于網(wǎng)絡最大流的網(wǎng)絡目標選擇模型

喻飛飛,胡友濤,王 劍

(火箭軍指揮學院,湖北 武漢 430012)

針對網(wǎng)絡目標選擇問題,引入網(wǎng)絡最大流進行目標價值評估,結(jié)合網(wǎng)絡阻斷量和成本控制的限制性條件,構(gòu)建網(wǎng)絡目標選擇模型。算例分析驗證了模型的可操作性和實用性。該模型能夠有效解決網(wǎng)絡目標選擇的價值衡量問題,并可作為對網(wǎng)絡目標選擇問題進行深入研究的基礎(chǔ)。

網(wǎng)絡目標選擇;最大流;價值評估;模型

1 問題的提出

目標選擇是作戰(zhàn)籌劃的重要內(nèi)容,也是信息化條件下聯(lián)合作戰(zhàn)的首要問題,目標選擇是否科學合理,直接影響戰(zhàn)爭的成敗。新形勢下的目標選擇面對的往往不再是單一、孤立的目標,而是多個目標按照一定的秩序和內(nèi)部聯(lián)系進行組合形成的整體,即目標體系。由于政治影響、成本、附帶毀傷風險等多方面的因素制約,我們不可能將整個目標體系列為打擊目標,往往需要在目標體系中選擇一些關(guān)鍵的節(jié)點性目標進行打擊。實際上,只要選準了關(guān)鍵目標,就極有可能造成“無差別攻擊”同樣的效果。如美軍認為,只要摧毀作戰(zhàn)體系中20%的“關(guān)鍵目標”,整個體系就會陷入癱瘓或崩潰。這已經(jīng)在科索沃戰(zhàn)爭和伊拉克戰(zhàn)爭中得到了證明。因此,目標選擇的重點就在于如何找到這些“關(guān)鍵目標”。

從系統(tǒng)的角度來看,很多作戰(zhàn)體系都是由節(jié)點和鏈路組成的網(wǎng)絡,如指揮信息系統(tǒng)、情報獲取系統(tǒng)、后勤運輸系統(tǒng)等,都是由若干節(jié)點和鏈路進行有效組合,實現(xiàn)命令下達、信息傳輸、給養(yǎng)配送等功能。對這類網(wǎng)絡系統(tǒng),我們往往最關(guān)注的是切斷或者盡量減少其網(wǎng)絡傳輸量,進而造成該作戰(zhàn)系統(tǒng)效能降低甚至完全失效。也就是說,對于網(wǎng)絡系統(tǒng)的目標選擇問題,我們可以通過系統(tǒng)內(nèi)各節(jié)點目標對于整個網(wǎng)絡傳輸?shù)挠绊懚葋磉M行評估和選擇,而節(jié)點目標的網(wǎng)絡影響度則可以通過網(wǎng)絡最大流的變化情況來進行分析和計算。

2 網(wǎng)絡最大流

“流”通常是指物質(zhì)在不同系統(tǒng)之間的轉(zhuǎn)移運行?，F(xiàn)實生活中,很多系統(tǒng)都包含了“流”的問題,如公交系統(tǒng)中有車輛流,供水系統(tǒng)中有水流,金融系統(tǒng)中有現(xiàn)金流,軍事系統(tǒng)中有人流、信息流、物資流等。其共同的特點是,至少有一個出發(fā)點和收點,有若干個中間點,共同形成一個“流”的網(wǎng)絡[1]。網(wǎng)絡最大流是指從出發(fā)點到收點能“流”過的最大流量,它代表了網(wǎng)絡系統(tǒng)實現(xiàn)某項功能的最大能力。以交通運輸網(wǎng)為例,如圖1所示,產(chǎn)品從產(chǎn)地V1到銷地V6需要經(jīng)過若干中間路線,路線旁的數(shù)字代表這條運輸線的最大通過能力,則該網(wǎng)絡的最大流就是從V1到V6的最大運輸能力。

圖1 交通運輸網(wǎng)絡的最大流

關(guān)于網(wǎng)絡的最大流問題還有一些基本的概念需要了解,如可行流、增廣鏈、截集、截量等,這些內(nèi)容在相關(guān)文獻中有詳細介紹,本文不再詳述。而求解網(wǎng)絡最大流的方法有很多,如標號法、最短增廣路算法、預留推進法、最高標號的預留推進法等,其中標號法的應用最為廣泛,且更易理解。本文即采用標號法來求解網(wǎng)絡的最大流,其基本思想為:逐步找出網(wǎng)絡中存在的不飽和(每條線路上的流量均小于容量,或反向流量不為0)的方案流,即增廣鏈;為該方案流增加流量至飽和,然后繼續(xù)尋找增廣鏈,直至找不到,則此時網(wǎng)絡的實際流量(可行流)即為網(wǎng)絡最大流。標號法求解網(wǎng)絡最大流的基本步驟如圖2所示。

圖2 標號法的基本步驟

各步驟的具體內(nèi)容如下:1)標號。從發(fā)點開始,逐個檢查網(wǎng)絡節(jié)點,標記兩部分內(nèi)容：第一部分標明該標號是從哪一點得到的,即確定檢查的鏈路;第二部分標明該鏈路能夠增加或減少的流量(反方向為減少),以便確定增廣鏈的調(diào)整量。如果該鏈路能夠增加或減少的流量均為0,則該點無法被標號。2)找增廣鏈。一旦收點被標上號,就可以從收點開始沿著標號過程找到一條增廣鏈。3)流量調(diào)整。增廣鏈上各鏈路最大調(diào)整量的最小值即為調(diào)整量,用該調(diào)整量調(diào)整各條鏈路的實際流量。4)判斷是否能重新標號。調(diào)整完畢后,觀察判斷能否繼續(xù)完成標號,若能則重復步驟1)、2)、3),直至無法完成標號過程為止。5)計算最大流。計算經(jīng)過調(diào)整后網(wǎng)絡的實際流量,即為該網(wǎng)絡的最大流。

3 基于網(wǎng)絡最大流的目標價值評估

網(wǎng)絡流的形成是為了方便物質(zhì)的轉(zhuǎn)移和運行,網(wǎng)絡最大流越大,則物質(zhì)的轉(zhuǎn)移量越大,其運行也更加順暢。因此,網(wǎng)絡流內(nèi)各目標的價值可以按照其對網(wǎng)絡最大流的貢獻程度來進行評估。基于網(wǎng)絡最大流的目標價值評估,其基本思路為:首先計算完整狀態(tài)下的網(wǎng)絡最大流,并以此作為基數(shù);然后去除網(wǎng)絡流中的某一個目標,再計算去除后的網(wǎng)絡最大流,對于該目標而言,網(wǎng)絡最大流的改變量正是其在整個網(wǎng)絡中的價值體現(xiàn)。因此,可以將網(wǎng)絡最大流減少的百分比作為評估該目標價值的標準,其表達式如下[2]:

基于網(wǎng)絡最大流的目標價值評估步驟如圖3所示。

圖3 基于網(wǎng)絡最大流的目標價值評估步驟

4 引入網(wǎng)絡阻斷量與成本控制的目標選擇模型

在目標選擇的過程中,除了目標的價值外,我們還必須考慮其它的一些因素,如作戰(zhàn)目的、作戰(zhàn)成本、附帶毀傷等,其中,指揮員最為關(guān)心的是作戰(zhàn)目的及作戰(zhàn)成本。因此,有必要在目標價值評估的基礎(chǔ)上引入網(wǎng)絡阻斷量與成本控制進行綜合考慮。網(wǎng)絡阻斷量,即根據(jù)作戰(zhàn)目的確定的對網(wǎng)絡功能的降低程度,比較常見的等級如退化、破壞、摧毀等,都對應著不同的網(wǎng)絡阻斷量。在指揮員作戰(zhàn)籌劃的過程中,必須要首先確定網(wǎng)絡阻斷量(作戰(zhàn)目的),然后選擇相應網(wǎng)絡子目標進行打擊。成本控制,即在目標選擇的過程中,要使我方的作戰(zhàn)成本最小化。雖然各類節(jié)點在網(wǎng)絡內(nèi)發(fā)揮的功能可能是相同的,但其打擊成本可能并不相同(如節(jié)點的地理位置、防御程度等不同都可能引發(fā)打擊成本的變化)。顯然,網(wǎng)絡阻斷量與成本控制是目標選擇的兩個限制性條件。

引入網(wǎng)絡阻斷量與成本控制后,需要考慮如下兩個問題:一是選擇多少個目標，哪些目標或目標組合能夠達到要求的網(wǎng)絡阻斷量？二是如何評判這些目標選擇方案的優(yōu)劣？第一個問題我們可以用達到預定的網(wǎng)絡阻斷量作為標準,來形成目標選擇方案集;對于第二個問題,我們可以在形成目標選擇方案集的基礎(chǔ)上,用效費比來進行比較和選擇。

4.1 生成目標選擇方案集

要滿足網(wǎng)絡阻斷量的要求,可能只需選擇一個網(wǎng)絡節(jié)點目標,也可能需要選擇多個節(jié)點目標。為了生成目標選擇方案集,通常的做法,是逐個將可能的移除目標組合進行檢驗,計算移除后是否能達到網(wǎng)絡阻斷量的要求。需要注意的是,由于節(jié)點之間的耦合作用,計算移除兩個節(jié)點后的網(wǎng)絡阻斷量并不是分別移除單個節(jié)點后的網(wǎng)絡阻斷量之和,而應在移除后按照標號法重新計算。

對于某些節(jié)點過多、結(jié)構(gòu)復雜的網(wǎng)絡流,這種窮舉法可能并不可取,因為需檢驗的移除目標組合將隨著節(jié)點數(shù)量的增加呈幾何級數(shù)增長,導致目標選擇效率過低。此時,應放棄手工作業(yè)的標號法,而采取易于編程實現(xiàn)的預留推進法或增廣路算法來計算網(wǎng)絡最大流。連同判斷是否達到網(wǎng)絡阻斷量這一條件一起通過計算機編程來實現(xiàn)。預留推進法和增廣路算法的實現(xiàn)過程可參見文獻[3-5]。

4.2 計算效費比

網(wǎng)絡目標選擇的效費比可以采用網(wǎng)絡阻斷量與打擊成本的比值來實現(xiàn)。效費比計算公式如下:

其中,Si為第i個目標選擇方案的效費比;Wi表示第i個目標選擇方案的網(wǎng)絡阻斷量;j表示第i個目標選擇方案選擇的目標數(shù);Ln表示其中第n個目標的打擊成本。

得到各個方案的效費比后,即可選擇效費比最高的方案目標作為最終選擇的打擊目標。

5 算例分析——指揮信息網(wǎng)絡系統(tǒng)的目標選擇問題

敵某個指揮信息網(wǎng)絡的系統(tǒng)結(jié)構(gòu)如圖4所示,從指揮端A到指令終端H需要經(jīng)過多個通信節(jié)點的傳輸,圖中括號內(nèi)前面的數(shù)據(jù)代表線路的通信容量,后面的數(shù)據(jù)代表某個時刻的實際流量?，F(xiàn)要對該信息網(wǎng)絡進行導彈攻擊,考慮到通信線路的快速修復能力,一般不選擇通信線路進行打擊,而應選擇通信節(jié)點。且各類節(jié)點的打擊成本如表1所示(已經(jīng)過無量綱處理)。考慮如下兩種情況:一是只發(fā)射1枚導彈打擊1個目標;二是不明確導彈數(shù)量,而是使該信息網(wǎng)絡傳輸功能降低50%。兩種情況下分別應如何選擇相應的打擊目標。

圖4 敵指揮信息網(wǎng)絡的系統(tǒng)結(jié)構(gòu)

表1 各節(jié)點目標的打擊成本

1)對于第一種情況,只能發(fā)射1枚導彈,即只能選擇一個打擊目標。根據(jù)上述目標選擇模型,此時只需進行單個節(jié)點的目標價值評估并計算效費比即可。計算過程如下:

首先計算當前通信網(wǎng)絡的最大流。按照“標號法”,并依次選擇ADCFH、ACFEH、ABEH、ABCGH、ACEFH、ACFGH、ADGH作為增廣鏈,流量調(diào)整后可以得到當前網(wǎng)絡的最大流為16。隨后,依次選取各通信節(jié)點作為目標,并計算移除該節(jié)點后的網(wǎng)絡最大流。得到各通信節(jié)點的網(wǎng)絡阻斷量(目標價值),用該阻斷量除以相對應的打擊成本即可得到各目標的打擊效費比,計算結(jié)果如表2所示。

表2 單個節(jié)點目標效費比

分析可知,當僅選擇一個目標時,顯然指揮端節(jié)點A和終端節(jié)點H的價值最高,網(wǎng)絡阻斷量達到100%,但由于其打擊成本過大,效費比反而較低。這是符合客觀情況的,一般而言,敵對其指揮端的防護肯定非常嚴密,而終端節(jié)點則存在機動性,這些都增加了打擊成本?？傮w比較而言,目標G的效費比最高,因此應選擇節(jié)點G作為打擊目標。

2)對于第二種情況,我們需要逐個找出滿足“功能降低50%”這一條件的目標組合。計算可知,當選取一個目標時,節(jié)點A、C、H滿足這一要求;當選取二個目標時,除節(jié)點B、E組合和D、G組合外,其余組合均滿足要求。于是可以在B、E組合和D、G組合的基礎(chǔ)上考慮選擇三個目標的情況。整個計算結(jié)果如表3所示。

表3 網(wǎng)絡阻斷量達到50%的目標組合效費比

比較可知,當選擇節(jié)點E、G時,效費比最大,達到0.344。因此,應選擇節(jié)點E、G作為打擊目標。

6 結(jié)束語

本文將網(wǎng)絡最大流問題應用于網(wǎng)絡目標價值評估,結(jié)合網(wǎng)絡阻斷量和成本控制,構(gòu)建了網(wǎng)絡目標選擇模型,最后用算例進行了驗證,顯示了較好的應用效果。需要指出的是,本文的研究僅考慮了網(wǎng)絡目標選擇的軍事價值和成本因素,而在具體的軍事實踐過程中,目標選擇問題往往還會涉及政治因素、戰(zhàn)爭潛力因素、人道主義因素等。如果要更加全面地考慮網(wǎng)絡目標選擇問題,還需要在本模型的基礎(chǔ)上作進一步的深化研究,這也是下一步需要解決的問題。

[1] 錢頌迪.運籌學[M].北京：清華大學出版社,2012.

[2] 張最良.軍事戰(zhàn)略運籌分析方法[M].北京：軍事科學出版社,2009.

[3] 張永軍.最大流算法及其應用[J].中國科技信息,2007(24):322-323.

[4] 趙禮峰,孟曉婉.基于深度優(yōu)先的一種網(wǎng)絡最大流求解法[J].計算機技術(shù)與發(fā)展,2012，22(10):167-164.

[5] 馬毅,嚴余松,戶佐安.網(wǎng)絡優(yōu)化的最大利潤問題及其增廣路算法[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