基于網絡最大流的網絡目標選擇模型

喻飛飛,胡友濤,王 劍

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

基于網絡最大流的網絡目標選擇模型

喻飛飛,胡友濤,王 劍

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

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

網絡目標選擇;最大流;價值評估;模型

1 問題的提出

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

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

2 網絡最大流

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

圖1 交通運輸網絡的最大流

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

圖2 標號法的基本步驟

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

3 基于網絡最大流的目標價值評估

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

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

圖3 基于網絡最大流的目標價值評估步驟

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

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

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

4.1 生成目標選擇方案集

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

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

4.2 計算效費比

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

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

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

5 算例分析——指揮信息網絡系統的目標選擇問題

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

圖4 敵指揮信息網絡的系統結構

表1 各節點目標的打擊成本

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

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

表2 單個節點目標效費比

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