預警網絡優化配置算法研究

曾 斌，王 睿，胡 煒

（1．海軍工程大學管理工程系，湖北武漢430033；2．海軍工程大學訓練部圖書館，湖北武漢430033）

預警網絡優化配置算法研究

曾 斌1，王 睿2，胡 煒1

（1．海軍工程大學管理工程系，湖北武漢430033；2．海軍工程大學訓練部圖書館，湖北武漢430033）

由于我國軍事防護海域及試驗場區眾多且較分散，當前迫切需要采用經濟有效的方法建立預警網絡，提早發現異常并立即告警和處理。為此首先借鑒入侵圖思想構造警戒區域的有向圖模型，以此描述可能的入侵路線及監測站候選部署位置。隨后針對預警網絡中固定監測站和移動監測站的部署數量、位置及巡邏航線等配置問題，建立了隨機性數學模型，旨在保證一定目標檢測概率的條件下盡量縮短預警時間，并提出了一個基于仿真抽樣的啟發式優化算法對該模型求解。最后通過仿真實驗證明，相較于隨機部署和層次部署方法，優化配置算法具有較高的預警性能。

預警網絡；優化算法；監測部署；入侵圖

0 引 言

重點海域（重點港口、重要航路、海上兵器試驗場區、油氣資源）的警戒與防護是涉及國防安全的重要課題，近幾年來海上入侵滲透手段也逐漸增多，入侵方式主要有小型和袖珍的潛艇、水雷、水下特種部隊（蛙人）等，構成多種威脅。

盡管多數港口及試驗區在選址時考慮了安全問題，但由于防護區域較大，水面水下情況復雜多變，過去常規監視方法很難保證在各種突發情況下能很好地應對事先經過周密策劃與準備的突然襲擊。重點水域、基地的水下警戒如全部依賴水面艦艇，一方面需要大量兵力，另一方面也難以達到全天候、全時候警戒的能力。因此，建立更加完善的重點水域安全與防護系統顯得非常迫切而且尤為重要。

近年來不少學者從不同角度開展了入侵監測系統及預警網絡優化配置領域的研究［1－2］。第1類可稱之為“藝術畫廊問題”［3］，該問題把藝術畫廊抽象為復雜的多邊形區域，通過搜索最少的頂點來部署警報器，以便監測畫廊的每一個角落。該研究可歸類為解決確定性的區域覆蓋性問題［4－5］，而本文重點研究非確定性條件下的隨機優化問題。第2類稱為“基于概率的警報器部署問題”，把警戒區域細分為多個網格，假定知道每個網格的入侵檢測概率，通過貝葉斯網絡［6］、馬爾可夫鏈甚至博弈論［7－8］估算入侵者最有可能的入侵路線，從而得到預警網絡的配置方案。值得注意的是入侵圖最早在計算機網絡入侵檢測研究中提出［9］，現在在物理入侵檢測中也已得到廣泛使用，作為入侵路線的重要分析工具之一。這種方法的預警精度依賴于事先建立的入侵方案預測模型（條件概率）［10］，而且沒有考慮移動警報器的部署。第3類通過部署傳感器網絡進行入侵監測，其中大部分研究采用的方法是隨機地把傳感節點拋撒在監測區域內，節點到達地面以后自組成網［11－12］。也有部分是定點部署［13］，但這些方法假設傳感器價格便宜且監測區域內部各處目標檢測概率均勻分布［14－15］，而海上預警網絡所要監測區域范圍廣闊且不同地方傳感半徑和通信信道區別較大，網格劃分法不再適用［7］；監測站（如高精度聲納）價格昂貴，也不宜采用這種大密度部署方式。另外也有部分研究提出利用移動傳感器網絡的協同監測算法，通過移動傳感器來優化監測覆蓋范圍［16］，但主要還是研究確定條件下的部署問題，而且沒有對移動傳感器數量進行優化。

當前傳感器網絡和監測網絡部署算法的一個主要目的是擴大網絡的覆蓋率和聯通性［17－18］，而預警網絡的主要戰術性能指標是縮短預警時間（入侵者進入警戒區域到被發現之間的時間），以便攔截兵力能夠進行充分的反應和準備。另外火力組網［19－20］和雷達組網［21］的優化部署問題也日益得到重視，但它們的優化目標與約束條件都與預警網絡有很大不同。

本文主要防護對象為港口或水中兵器試驗區等重點水域，在選址時為安全考慮，一般背靠港灣，正面具備天然的島嶼、暗礁等復雜水文環境，再加上關鍵路徑上已部署的偵查站點，對入侵路線已具備一定的限制能力。但由于水域寬廣和入侵手段的提高，也存在不少易被滲透的地點及路線，因此在執行重要任務，例如艦艇出航及兵器試驗時，有必要補充部署預警系統，對防護薄弱的區域實施針對性警戒。

本文借鑒“藝術畫廊問題”及傳感器部署問題的方法，把警戒區域描述為一個封閉的幾何圖形，根據港口或水中兵器試驗區的實際情況，把警戒力量劃分為固定監測站、設定線路巡邏監測站和隨機線路巡邏監測站，將配置數量及分布位置作為優化對象。優化目標為滿足一定侵入檢測率的條件下，最小化預警時間和部署開銷。

1 問題描述

借鑒入侵圖的建模方法，警戒區域描述為一個有向圖G＝（V，E），V中的頂點為入侵對象所有可能的潛入路線上的中間點，即監測站可能需要巡邏或部署的位置，可以由水警區在海圖上根據水文地理條件事先設定。但與入侵圖不同的是，不要求給出入侵路線的條件概率，這在實際也很難計算。因此圖中路徑可定義為頂點序列v1，v2，…，vn，（vi，vi＋1）∈E。航行時間定義為路徑函數：t（v1，v2，…，vn）＝t［（v1，v2）］＋…＋t［（vn－1，vn）］。為了優化算法計算方便，對圖G做了進一步擴展，引入了兩個虛擬頂點vs和vd，分別表示入侵對象的起止位置。設Vs?V為警戒區域邊緣可能被潛入的初始位置集合，則vs到Vs的航線時間設為0，同樣設Vd為警戒區域內部的防護目標集合，Vd到vd的航線時間也設為0。

1．1 警戒力量的數學描述

首先入侵者o可看作一個移動對象，其目的為在給定入侵策略的指導下完成一條從vs到vd的航線路徑。

警戒力量的職責是：當入侵者進入其偵查范圍時及時發出預警信號，該信號的產生依賴于偵查器材、目標辨識人員及當時的水文條件等諸多情況，為此本文用警報事件的產生概率來進行描述。這里考慮三種類型的警戒力量。

固定監測站Ss＝｛a1，a2，…，ap｝：可以部署在除vs和vd之外的頂點位置。

設定線路巡邏監測站Sf＝｛f1，f2，…，fq｝：按照預先規劃線路在G上航行的移動監測站。

隨機線路巡邏監測站Sr＝｛r1，r2，…｝：在圖G上隨機巡視的移動監測站，由于其最大航線數量無法事先設定，所以它的數量也無法設置上限。

由于固定監測站和設定線路巡邏監測站的位置可以事先部署，都具有靜態性，所以本文把二者統一稱為確定路徑監測站，即Sd：＝Ss∪Sf，因此監測站的配置集合為：U＝2Sd＋Sr。

針對各類監測站的入侵監測時間，本文定義了以下3種隨機變量：

To≥0：侵入者從vs到vd的航線時間；

Tdi≥0：確定路徑監測站di的入侵檢測時間；

Tri≥0：隨機巡視監測站ri的入侵檢測時間。

對任一監測站部署方案S∈U，定義它的檢測時間集合為TS＝｛Ts：s∈S｝，則該方案最早的入侵檢測時間（預警時間）為WT（S）：＝min（TS）。

在這里設監測站的入侵檢測時間為同一獨立分布，因此滿足以下兩個條件：

（1）服從同一聯合概率分布，即對任意整數i，j，有

（2）本身服從獨立分布

監測站配置方案的整體部署開銷為方案中每個監測站部署開銷的總和，即有

1．2 優化目標的建立

優化目標為在滿足一定入侵檢測概率的條件下，兼顧最小化預警時間和部署開銷。為此引入兩個變量：

pd（S）：在侵入者到達目標vd之前，S中監測站至少發出一個警報事件的概率，它與網絡的覆蓋率有關；

E（WT（S））：S發現入侵者最早時間的期望值，本文用它表示預警時間。

由此預警網絡的監測站配置問題（warning network monitor configuration problem，WNMCP）的優化目標函數建立如下：

式中，p＊為預設的入侵檢測率閾值。由于增加監測站數量可以大幅度縮短預警時間，所以需要在部署開銷c（S）和預警時間E（WT（S））之間折中考慮。

定理1 WNMCP為NP難問題。

證明 給定入侵圖G，對WNMCP問題進一步簡化，設P＊＝1，而且只考慮在V中部署固定監測站，固定監測站的部署開銷為1，且假設只要侵入者經過固定監測站所管轄的節點，就會觸發警報事件，并設w＝0，則WNMCP可簡化為如下問題：

這時WNMCP可簡化為：在入侵圖G中搜索最多K個固定監測站，使其滿足pd（S）＝1。如果侵入者的目標是從vs到vd，則當且僅當G中任意一條邊E上某一節點部署了監測點時pd（S）＝1。視監測站為頂點覆蓋中的成員，則WNMCP的簡化版本可轉化為頂點覆蓋問題，由于頂點覆蓋屬于NP難問題，WNMCP則為NP難問題。證畢

2 算法描述

本數據為X＝（x1，x2，…，xN），其中）。這里為Tdi的第k次迭代樣本，為Tr的第k次迭代樣本，為To的第k次迭代樣本。

圖1 基于仿真的優化算法流程圖

由于預警網絡配置不僅屬于NP難問題，而且目標函數帶有隨機變量，所以一般啟發式算法不再適用，這種情況下，基于仿真的優化方法是復雜優化問題的唯一選擇。本文先利用仿真輸出的樣本計算目標函數中的隨機變量，再利用啟發式算法搜索最優配置方案。圖1為算法流程，仿真中監測站的配置方案為＾S＝Sd∪｛r｝，也就是仿真時部署所有可能的固定監測站和設定路徑監測站，但只部署一個隨機監測站r讀取隨機監測站樣本數據。設仿真輸出的樣

定義Ssd∪｛r1，r2，…，rnr｝?Sd為當前監測站部署方案，其中Ssd為已選擇部署的確定性監測站，｛r1，r2，…，rnr｝為服從同一獨立分布的隨機移動監測站。算法每次迭代都從尚未選擇的監測站集合選擇一個監測站s，s∈（Sd∪rnr＋1）＼Ssd，評估其預警性能以決定是否將它納入配置方案中。評估公式如下：

約束條件為：pd（s1∶n∪Ssd∪r1∶nr）≤p＊，其中s1∶n為當前尚未部署的確定監測站，服從同一獨立分布。fWT，c（S，w）＝w·E（WT（S））＋（1－w）·c（S），該函數包含兩個參量需要計算：pd（s1∶n∪Ssd∪r1∶nr）和E（WT（s1∶n∪Ssd∪r1∶m））。下面介紹如何通過仿真樣本計算這兩個參量。

首先引入4個中間參量，可通過仿真抽樣近似計算：

PMsd（To）＝P［min（TSsd）≥To］：部署了Ssd集合內的監測站后的入侵漏檢率；

PMsd，s（To）＝P［min（TSsd∪｛s｝）≥To］：在Ssd基礎上增加部署s監測站后的漏檢率；

PCr｜sd（To）＝P［Tr≥To｜min（TSsd）≥To］：在Ssd個監測站部署完畢后，如果全部漏檢，隨機監測站r的漏檢率；

PCr｜sd，s（To）＝P［Tr≥To｜min（TSsd∪｛s｝）≥To］：監測站Ssd、s和r部署后，如果確定性監測站Ssd、s漏檢后，r的漏檢率。

這4個參量可以通過對樣本X進行簡單的計數運算進行預估。

2．1 約束值的計算

首先有約束值

這時考慮以下兩種情況：

（1）當s∈Sd時，即s為確定性監測站，所有監測站服從同一獨立分布，見式（1）和式（2），可得

對于分子有

應用同一獨立分布性質，分母同樣可以轉化為PCr｜sd（To）和PMsd（To）的函數

因此約束值可得

（2）當s＝r時，即s為隨機性監測站

2．2 目標函數值的計算

目標函數主要包含兩個部分：監測站的部署開銷以及最早預警時間的期望值。部署開銷容易計算，這里重點介紹如何估算預警時間。

通過式（10），可得

因此E（WT（s1∶n∪Ssd∪r1∶m））也可由仿真樣本近似計算得到。

2．3 啟發式搜索算法

啟發式算法主程序為WNMCP，子程序為fmin，其中fmin根據第2．1節和第2．2節的算式計算目標函數值。主程序WNMCP的輸入參數如下：

1∶n′s＝min（pd（s1∶n∪Ssd∪r1∶m）≥p＊）；∥計算滿足預設入侵檢測概率的監測站數量的最小值

2：ns＊＝arg min｛fWT，c（s1∶n∪Ssd∪r1∶m，w）：n≥n′s｝；∥即滿足預設入侵檢測概率，且能取得最小目標值的監測站數量的最小值

3：fest＝fWT，c（s1∶n＊∪Ssd∪r1∶m，w）；∥最小目標函數值

4：fsel＝fWT，c（｛s｝∪Ssd∪r1∶m，w）；∥監測站配置為｛s｝∪Ssd∪r1∶m時的目標函數值

5：psel＝pd（｛s｝∪Ssd∪r1∶m，w）；∥監測站配置為｛s｝∪Ssd∪r1∶m時的入侵檢測概率

WNMCP算法的第11行到第16行遍歷入侵圖中尚未部署監測站的節點（候選節點），依次調用fmin函數計算在候選節點處部署監測站后的目標函數值，并把當前能取得最小目標值的監測站位置保存到s＊中。

由于隨著部署的監測站數量增加，入侵預警時間單調降低，而部署開銷單調升高（這里省略數學證明），因此目標函數fWT，c（s1∶n＊∪Ssd∪r1∶m，w）為n的凸函數，所以在fmin中可以通過線性搜索找到最優的監測站數量s＊。

WNMCP算法的第17行判別s＊是否應該加入部署方案Ssd∪｛r1，r2，…，rm｝中，該判別條件有兩條：①以前迭代得到的部署方案無法滿足預設的入侵檢測率（pold＜p＊）；②前面部署方案的目標值不小于加入s＊后的目標值（fold≤fcur）。也就是說算法通過條件1滿足約束條件，通過條件2降低目標值。當兩個條件都不滿足時，算法返回得到的部署方案S＊，否則表明還有優化的余地，把s＊加入方案中。

下面證明算法得出的配置方案為局部最優解，首先證明如下假設。

假設1 算法返回配置方案S＊后，對于沒有入選S＊的候選監測站集合中任意一個監測站s∈｛Sd＼S＊｝∪｛r｝，有

證明 采用反證法，設存在s∈｛Sd＼S＊｝∪｛r｝有f（S＊，w）≤f（S＊∪｛s｝，w）。從fmin算法第1行和第2行可以得到

這里n′s＝min（pd（S＊∪s1∶n）≥p＊），因為pd（S＊）≥p＊，所以對于s∈｛Sd＼S＊｝∪｛r｝，有n′s＝1。

因此可得

從WNMCP算法第13行，則得到的｛s＊｝有

從以上兩個不等式可得

而從WNMCP算法第17行，S＊作為返回的配置方案，必須滿足以下兩個條件，其中第2條即為

這與式（12）矛盾。證畢

如果假設1成立，即對最優解S＊新增加任何一個監測節點都會導致目標函數值增加，再結合WNMCP算法第17行的判別條件，可以得出S＊是WNMCP問題的局部最優解。

3 仿真結果分析

為了驗證算法的性能，建立了一個包含162個頂點和541條有向邊的入侵網絡圖，圖中包含2個被保護目標頂點。如上所述監測站包括3種類型，每一個頂點都為固定監測站的候選部署位置，即候選監測站集合Ss＝｛s1，s2，…，s162｝。另外仿真場景中還包括9個設定路徑巡邏監測站Sf＝｛f1，f2，…，f9｝，1個隨機路徑監測站r。入侵者o可以以圖中任意一個外圍頂點作為起始源點，終點從2個目標頂點中隨機選擇，在仿真實驗中入侵者采用的航行策略為最短路徑優先。

采用上述部署方案Ss∪Sf∪｛r｝進行多次仿真，采集其中1 000次仿真的結果X＝（x1，x2，…，x1000）作為樣本數據，每一個樣本的格式見第2節，這里出于安全考慮省略了監測站性能參數的具體數據。計算目標函數時采用的部署開銷如下：

因為固定監測站需要專門部署在海上并需要定期派人維護，所以開銷較大，而對于移動監測站，可以在有試驗任務時把監測裝備安裝在艦艇上，維護也較為方便，所以開銷較小。

把仿真樣本輸入算法，表1給出了當權重w變化時計算出的監測站優化部署方案，其中最小檢測概率閾值p＊設置為0．95。表1中｜Ss｜、｜Sf｜和｜Sr｜分別表示計算出的固定監測站、設定路徑監測站和隨機路徑監測站的數量。

表1 算法計算結果比較

從表1中可以看出，隨著w的增加，WNMCP算法會部署更多的固定監測站，分析其原因是相比于其他類型監測站，固定監測站對降低預警時間更為有效。相反，隨著w的減少，WNMCP對部署開銷越來越敏感，在增加預警時間的代價下，傾向于部署更多的移動監測站。例如當w＝0．4時，算法部署了18個固定監測站，5個設定路徑監測站和23個隨機路徑監測站，與w＝0．8時相比，部署開銷從161降低到102，但入侵預警時間的期望值卻從62s增加到148s。隨著w的進一步減少，算法部署的隨機監測站數量也相應增多，例如當w＝0．2時，算法僅部署了4個固定監測站，2個設定路徑監測站，但卻部署了37個隨機路徑監測站，與w＝0．8時相比，部署開銷節約了108，卻延遲了200s的預警時間。

下面對算法性能進一步進行了比較性驗證。由于本文算法目的是在監測性能非均勻分布的環境下盡快縮短預警時間，如引言中所述，現有大部分旨在提高覆蓋率的傳感器部署算法不再適用該背景，所以選用了兩個算法做比較。一個為現在廣泛采用的層次部署方案，實驗里采用3層布防，每層監測站數量與該層到保護目標的距離成正比。在監測器數量一定的情況下，層數越多，入侵檢測率就越高，但預警時間也會延長。第二個為隨機部署方案，隨機選擇候選地址來部署監測站。本實驗只考慮固定監測站的部署，所以簡化了WNMCP算法，取消了對移動監測站的支持，另外由于兩個對比算法還不支持監測站數量的優化，所以實驗中刪除了fmin函數的第1行和第2行。

圖2為隨著監測節點（選擇部署于圖節點的監測站）數量變化，3個算法預警時間的變化情況。隨著監測節點數量增加，預警時間都相應減少。由于WNMCP算法針對預警時間進行了優化，所以預警時間最短。而層次部署更多地把監測站部署在監測區域外圍，所以預警時間相較于隨機部署也有顯著縮短。

圖2 監測節點數量對預警時間的影響

從圖3可以看出，隨著監測節點數量增加，入侵檢測概率都相應提高。這里WNMCP算法的檢測率下限設置為0．9，所以檢測率盡管提高幅度不高，但比較穩定。而另外兩種算法由于缺少對檢測率的優化，都比較低。特別是某些配置方案下層次部署甚至比隨機部署還要低，這可能因為它在保護目標外圍部署較多監測站，一旦入侵者突防成功后，內部區域則缺少有效的監測兵力。

圖3 監測節點數量對入侵檢測率的影響

4 結 論

針對廣域空間入侵檢測問題，本文提出了一個異構稀疏傳感器／監測站的配置算法，該算法的設計框架具有良好的適應性，能夠根據優化目標、監測站類型、入侵對象以及應用環境的變化方便地進行擴展。下一步工作主要集中在兩個方面：一是如何利用數學規劃及組合優化方法來改進算法的運行效率，另外需要積極收集監測站點的虛警率及誤判率數據，提高仿真優化算法的容錯能力。以此為基礎，建立一個預警力量部署輔助決策支持系統，能夠對預警方案進行推演仿真和性能評估，并給出優化結果。

［1］Chang D B，Young C S．Probabilistic estimates of vulnerability to explosive overpressures and impulses［J］．Journal of Physical Security，2010，4（2）：10－29．

［2］Vejandla P，Dasgupta D，Kaushal A，et al．Evolving gaming strategies for attacker－defender in a simulated network environment［C］∥Proc．of the IEEE International Conference on Privacy，Security，Risk and Trust，2010：889－896．

［3］Durocher S，Filtser O，Fraser R，et al．Approximation algorithm for guarding orthogonal art galleries with sliding cameras［C］∥Proc．of Theoretical Informatics Lecture Notes in Computer Science，2014：294－305．

［4］Jens M．Perfect graphs and guarding rectilinear art galleries［J］．Discrete ＆Computational Geometry，2014，51（3）：569－577．

［5］Marcelo C C，Pedro J D，Cid C D．An exact algorithm for minimizing vertex guards on art galleries［J］．International Transactions in Operational Research，2011，18（4）：425－448．

［6］Pourali M，Mosleh A．A Bayesian approach to sensor placement optimization and system reliability monitoring［J］．Journal of Risk and Reliability，2013，227（3）：327－347．

［7］Erik F G，Sumita M，Nirmala S．An underwater sensor allocation scheme for a range dependent environment［J］．Computer Networks，2010，54（3）：404－415．

［8］Erik F G，Carl V L，David S R，et al．An underwater sensor allocation scheme for noncircular sensing coverage regions［J］．International Scholary Research Notices Sensor Networks，2013，13（11）：1－7．

［9］Dhaya R，Deepika D．Inspection of vulnerabilities through attack graphs and analyzing security metrics used for measuring security in a network［J］．International Journal of Innovative Research in Computer and Communication Engineering，2014，2（s1）：15－20．

［10］Chejara P，Garg U，Singh G．Vulnerability analysis in attack graphs using conditional probability［J］．International Journal of Soft Computing and Engineering，2013，3（2）：18－21．

［11］Heidemann J，Stojanovic M，Zorzi M．Underwater sensor networks：applications，advances and challenges［J］．Philosophical Transactions of the Royal Society A：Mathematical，Physical and Engineering Sciences，2012，370（5）：158－175．

［12］Senel F，Akkaya K．Autonomous deployment of sensors for maximized coverage and guaranteed connectivity in underwater acoustic sensor networks［C］∥Proc．of the 38th IEEE Conference on Local Computer Networks，2013：211－218．

［13］Liu L F．A deployment algorithm for underwater sensor networks in ocean environment［J］．Journal of Circuits，Systems and Computers，2011，20（6）：1051－1066．

［14］Huang J J，Sun L J，Wang R C，et al．Improved virtual potential field algorithm based on probability model in three－dimensional directional sensor networks［J］．International Journal of Distributed Sensor Networks，2012，21（6）：45－53．

［15］Pandey P，Pompili D．Distributed computing framework for underwater acoustic sensor networks［C］∥Proc．of the IEEE International Conference on Distributed Computing in Sensor Systems，2013：318－320．

［16］Ahmed M E，Alaa M K，Fakhri O K．Market－based approach to mobile surveillance systems［J］．Journal of Robotics，2012，12（9）：1－14．

［17］Huang J J，Sun L J，Wei X．Redundancy model and boundary effects based coverage－enhancing algorithm for 3Dunderwater sensor networks［J］．International Journal of Distributed Sensor Networks，2014，14（4）：1－12．

［18］Isbitiren G，Akan O B．Three－dimensional underwater target tracking with acoustic sensor networks［J］．IEEE Trans．on Vehicular Technology，2011，60（8）：3897－3906．

［19］Liu L J，Li X M，Yan J．Key－points air defense fan－shaped deployment with large－dimensional multi－objective multi－constraint group divided optimization［J］．Systems Engineering and Electronics，2013，35（12）：2513－2520．（劉立佳，李相民，顏驥．基于高維多目標多約束分組優化的要地防空扇形優化部署［J］．系統工程與電子技術，2013，35（12）：2513－2520．）

［20］Chen J，Chen C，Zhang J，et al．Deployment optimization for point air defense based on Memetic algorithm［J］．Acta Automatic Sinica，2010，36（2）：242－248．（陳杰，陳晨，張娟，等．基于Memetic算法的要地防空優化部署方法［J］．自動化學報，2010，36（2）：242－248．）

［21］Tan J X，Wang J X，Chen C．A model of radar and IR joint disposition and its optimized solution［J］．Fire Control ＆Command Control，2011，36（4）：131－134．（譚錦，王凈西，陳晨．一種雷達紅外聯合部署模型及優化求解方法［J］．火力與指揮控制，2011，36（4）：131－134．）

E－mail：zbtrueice＠163．com

王 睿（1975－），女，館員，碩士，主要研究方向為信息管理。

E－mail：kingwis＠163．com

胡 煒（1995－），男，碩士研究生，主要研究方向為信息管理。

E－mail：majunchao92＠163．com

Optimal configuration algorithm for early warning network

ZENG Bin1，WANG Rui2，HU Wei1
（1．Department of Management Engineering，Naval University of Engineering，Wuhan 430033，China；2．Library of Training Department，Naval University of Engineering，Wuhan 430033，China）

It is necessary and urgent to set up an effective and economic early warning network to defend the critical targets in a harsh environment by detecting the intruders in a short time．A direct graph model based on the attack graph is established to descript the intruding plots and potential deployment locations of detectors．In order to deal with the configuration of the fixed and mobile monitors，a stochastic mathematical model is presented to minimize the early warning time and deployment cost while satisfying the detection probability threshold．Therefore，a simulation based optimization algorithm is proposed to solve the configuration problems．The simulation results show that the optimization algorithm can obtain a better performance gain compared with the random or hierarchical deployment methods．

early warning network；optimization algorithm；detector deployment；attack graph

E 955

A

10．3969／j．issn．1001－506X．2015．06．11

曾 斌（1970－），男，教授，博士，主要研究方向為傳感器網絡部署、裝備保障。

1001－506X（2015）06－1294－06

2014－07－02；

2014－11－10；網絡優先出版日期：2014－12－09。

網絡優先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20141209．0116．003．html