預(yù)警網(wǎng)絡(luò)優(yōu)化配置算法研究

曾 斌，王 睿，胡 煒

（1．海軍工程大學(xué)管理工程系，湖北武漢430033；2．海軍工程大學(xué)訓(xùn)練部圖書(shū)館，湖北武漢430033）

預(yù)警網(wǎng)絡(luò)優(yōu)化配置算法研究

曾 斌1，王 睿2，胡 煒1

（1．海軍工程大學(xué)管理工程系，湖北武漢430033；2．海軍工程大學(xué)訓(xùn)練部圖書(shū)館，湖北武漢430033）

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

預(yù)警網(wǎng)絡(luò)；優(yōu)化算法；監(jiān)測(cè)部署；入侵圖

0 引 言

重點(diǎn)海域（重點(diǎn)港口、重要航路、海上兵器試驗(yàn)場(chǎng)區(qū)、油氣資源）的警戒與防護(hù)是涉及國(guó)防安全的重要課題，近幾年來(lái)海上入侵滲透手段也逐漸增多，入侵方式主要有小型和袖珍的潛艇、水雷、水下特種部隊(duì)（蛙人）等，構(gòu)成多種威脅。

盡管多數(shù)港口及試驗(yàn)區(qū)在選址時(shí)考慮了安全問(wèn)題，但由于防護(hù)區(qū)域較大，水面水下情況復(fù)雜多變，過(guò)去常規(guī)監(jiān)視方法很難保證在各種突發(fā)情況下能很好地應(yīng)對(duì)事先經(jīng)過(guò)周密策劃與準(zhǔn)備的突然襲擊。重點(diǎn)水域、基地的水下警戒如全部依賴(lài)水面艦艇，一方面需要大量兵力，另一方面也難以達(dá)到全天候、全時(shí)候警戒的能力。因此，建立更加完善的重點(diǎn)水域安全與防護(hù)系統(tǒng)顯得非常迫切而且尤為重要。

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

當(dāng)前傳感器網(wǎng)絡(luò)和監(jiān)測(cè)網(wǎng)絡(luò)部署算法的一個(gè)主要目的是擴(kuò)大網(wǎng)絡(luò)的覆蓋率和聯(lián)通性［17－18］，而預(yù)警網(wǎng)絡(luò)的主要戰(zhàn)術(shù)性能指標(biāo)是縮短預(yù)警時(shí)間（入侵者進(jìn)入警戒區(qū)域到被發(fā)現(xiàn)之間的時(shí)間），以便攔截兵力能夠進(jìn)行充分的反應(yīng)和準(zhǔn)備。另外火力組網(wǎng)［19－20］和雷達(dá)組網(wǎng)［21］的優(yōu)化部署問(wèn)題也日益得到重視，但它們的優(yōu)化目標(biāo)與約束條件都與預(yù)警網(wǎng)絡(luò)有很大不同。

本文主要防護(hù)對(duì)象為港口或水中兵器試驗(yàn)區(qū)等重點(diǎn)水域，在選址時(shí)為安全考慮，一般背靠港灣，正面具備天然的島嶼、暗礁等復(fù)雜水文環(huán)境，再加上關(guān)鍵路徑上已部署的偵查站點(diǎn)，對(duì)入侵路線已具備一定的限制能力。但由于水域?qū)拸V和入侵手段的提高，也存在不少易被滲透的地點(diǎn)及路線，因此在執(zhí)行重要任務(wù)，例如艦艇出航及兵器試驗(yàn)時(shí)，有必要補(bǔ)充部署預(yù)警系統(tǒng)，對(duì)防護(hù)薄弱的區(qū)域?qū)嵤┽槍?duì)性警戒。

本文借鑒“藝術(shù)畫(huà)廊問(wèn)題”及傳感器部署問(wèn)題的方法，把警戒區(qū)域描述為一個(gè)封閉的幾何圖形，根據(jù)港口或水中兵器試驗(yàn)區(qū)的實(shí)際情況，把警戒力量劃分為固定監(jiān)測(cè)站、設(shè)定線路巡邏監(jiān)測(cè)站和隨機(jī)線路巡邏監(jiān)測(cè)站，將配置數(shù)量及分布位置作為優(yōu)化對(duì)象。優(yōu)化目標(biāo)為滿(mǎn)足一定侵入檢測(cè)率的條件下，最小化預(yù)警時(shí)間和部署開(kāi)銷(xiāo)。

1 問(wèn)題描述

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

1．1 警戒力量的數(shù)學(xué)描述

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

警戒力量的職責(zé)是：當(dāng)入侵者進(jìn)入其偵查范圍時(shí)及時(shí)發(fā)出預(yù)警信號(hào)，該信號(hào)的產(chǎn)生依賴(lài)于偵查器材、目標(biāo)辨識(shí)人員及當(dāng)時(shí)的水文條件等諸多情況，為此本文用警報(bào)事件的產(chǎn)生概率來(lái)進(jìn)行描述。這里考慮三種類(lèi)型的警戒力量。

固定監(jiān)測(cè)站Ss＝｛a1，a2，…，ap｝：可以部署在除vs和vd之外的頂點(diǎn)位置。

設(shè)定線路巡邏監(jiān)測(cè)站Sf＝｛f1，f2，…，fq｝：按照預(yù)先規(guī)劃線路在G上航行的移動(dòng)監(jiān)測(cè)站。

隨機(jī)線路巡邏監(jiān)測(cè)站Sr＝｛r1，r2，…｝：在圖G上隨機(jī)巡視的移動(dòng)監(jiān)測(cè)站，由于其最大航線數(shù)量無(wú)法事先設(shè)定，所以它的數(shù)量也無(wú)法設(shè)置上限。

由于固定監(jiān)測(cè)站和設(shè)定線路巡邏監(jiān)測(cè)站的位置可以事先部署，都具有靜態(tài)性，所以本文把二者統(tǒng)一稱(chēng)為確定路徑監(jiān)測(cè)站，即Sd：＝Ss∪Sf，因此監(jiān)測(cè)站的配置集合為：U＝2Sd＋Sr。

針對(duì)各類(lèi)監(jiān)測(cè)站的入侵監(jiān)測(cè)時(shí)間，本文定義了以下3種隨機(jī)變量：

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

Tdi≥0：確定路徑監(jiān)測(cè)站di的入侵檢測(cè)時(shí)間；

Tri≥0：隨機(jī)巡視監(jiān)測(cè)站ri的入侵檢測(cè)時(shí)間。

對(duì)任一監(jiān)測(cè)站部署方案S∈U，定義它的檢測(cè)時(shí)間集合為T(mén)S＝｛Ts：s∈S｝，則該方案最早的入侵檢測(cè)時(shí)間（預(yù)警時(shí)間）為WT（S）：＝min（TS）。

在這里設(shè)監(jiān)測(cè)站的入侵檢測(cè)時(shí)間為同一獨(dú)立分布，因此滿(mǎn)足以下兩個(gè)條件：

（1）服從同一聯(lián)合概率分布，即對(duì)任意整數(shù)i，j，有

（2）本身服從獨(dú)立分布

監(jiān)測(cè)站配置方案的整體部署開(kāi)銷(xiāo)為方案中每個(gè)監(jiān)測(cè)站部署開(kāi)銷(xiāo)的總和，即有

1．2 優(yōu)化目標(biāo)的建立

優(yōu)化目標(biāo)為在滿(mǎn)足一定入侵檢測(cè)概率的條件下，兼顧最小化預(yù)警時(shí)間和部署開(kāi)銷(xiāo)。為此引入兩個(gè)變量：

pd（S）：在侵入者到達(dá)目標(biāo)vd之前，S中監(jiān)測(cè)站至少發(fā)出一個(gè)警報(bào)事件的概率，它與網(wǎng)絡(luò)的覆蓋率有關(guān)；

E（WT（S））：S發(fā)現(xiàn)入侵者最早時(shí)間的期望值，本文用它表示預(yù)警時(shí)間。

由此預(yù)警網(wǎng)絡(luò)的監(jiān)測(cè)站配置問(wèn)題（warning network monitor configuration problem，WNMCP）的優(yōu)化目標(biāo)函數(shù)建立如下：

式中，p＊為預(yù)設(shè)的入侵檢測(cè)率閾值。由于增加監(jiān)測(cè)站數(shù)量可以大幅度縮短預(yù)警時(shí)間，所以需要在部署開(kāi)銷(xiāo)c（S）和預(yù)警時(shí)間E（WT（S））之間折中考慮。

定理1 WNMCP為NP難問(wèn)題。

證明 給定入侵圖G，對(duì)WNMCP問(wèn)題進(jìn)一步簡(jiǎn)化，設(shè)P＊＝1，而且只考慮在V中部署固定監(jiān)測(cè)站，固定監(jiān)測(cè)站的部署開(kāi)銷(xiāo)為1，且假設(shè)只要侵入者經(jīng)過(guò)固定監(jiān)測(cè)站所管轄的節(jié)點(diǎn)，就會(huì)觸發(fā)警報(bào)事件，并設(shè)w＝0，則WNMCP可簡(jiǎn)化為如下問(wèn)題：

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

2 算法描述

本數(shù)據(jù)為X＝（x1，x2，…，xN），其中）。這里為T(mén)di的第k次迭代樣本，為T(mén)r的第k次迭代樣本，為T(mén)o的第k次迭代樣本。

圖1 基于仿真的優(yōu)化算法流程圖

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

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

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

首先引入4個(gè)中間參量，可通過(guò)仿真抽樣近似計(jì)算：

PMsd（To）＝P［min（TSsd）≥To］：部署了Ssd集合內(nèi)的監(jiān)測(cè)站后的入侵漏檢率；

PMsd，s（To）＝P［min（TSsd∪｛s｝）≥To］：在Ssd基礎(chǔ)上增加部署s監(jiān)測(cè)站后的漏檢率；

PCr｜sd（To）＝P［Tr≥To｜min（TSsd）≥To］：在Ssd個(gè)監(jiān)測(cè)站部署完畢后，如果全部漏檢，隨機(jī)監(jiān)測(cè)站r的漏檢率；

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

這4個(gè)參量可以通過(guò)對(duì)樣本X進(jìn)行簡(jiǎn)單的計(jì)數(shù)運(yùn)算進(jìn)行預(yù)估。

2．1 約束值的計(jì)算

首先有約束值

這時(shí)考慮以下兩種情況：

（1）當(dāng)s∈Sd時(shí)，即s為確定性監(jiān)測(cè)站，所有監(jiān)測(cè)站服從同一獨(dú)立分布，見(jiàn)式（1）和式（2），可得

對(duì)于分子有

應(yīng)用同一獨(dú)立分布性質(zhì)，分母同樣可以轉(zhuǎn)化為PCr｜sd（To）和PMsd（To）的函數(shù)

因此約束值可得

（2）當(dāng)s＝r時(shí)，即s為隨機(jī)性監(jiān)測(cè)站

2．2 目標(biāo)函數(shù)值的計(jì)算

目標(biāo)函數(shù)主要包含兩個(gè)部分：監(jiān)測(cè)站的部署開(kāi)銷(xiāo)以及最早預(yù)警時(shí)間的期望值。部署開(kāi)銷(xiāo)容易計(jì)算，這里重點(diǎn)介紹如何估算預(yù)警時(shí)間。

通過(guò)式（10），可得

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

2．3 啟發(fā)式搜索算法

啟發(fā)式算法主程序?yàn)閃NMCP，子程序?yàn)閒min，其中fmin根據(jù)第2．1節(jié)和第2．2節(jié)的算式計(jì)算目標(biāo)函數(shù)值。主程序WNMCP的輸入?yún)?shù)如下：

1∶n′s＝min（pd（s1∶n∪Ssd∪r1∶m）≥p＊）；∥計(jì)算滿(mǎn)足預(yù)設(shè)入侵檢測(cè)概率的監(jiān)測(cè)站數(shù)量的最小值

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

3：fest＝fWT，c（s1∶n＊∪Ssd∪r1∶m，w）；∥最小目標(biāo)函數(shù)值

4：fsel＝fWT，c（｛s｝∪Ssd∪r1∶m，w）；∥監(jiān)測(cè)站配置為｛s｝∪Ssd∪r1∶m時(shí)的目標(biāo)函數(shù)值

5：psel＝pd（｛s｝∪Ssd∪r1∶m，w）；∥監(jiān)測(cè)站配置為｛s｝∪Ssd∪r1∶m時(shí)的入侵檢測(cè)概率

WNMCP算法的第11行到第16行遍歷入侵圖中尚未部署監(jiān)測(cè)站的節(jié)點(diǎn)（候選節(jié)點(diǎn)），依次調(diào)用fmin函數(shù)計(jì)算在候選節(jié)點(diǎn)處部署監(jiān)測(cè)站后的目標(biāo)函數(shù)值，并把當(dāng)前能取得最小目標(biāo)值的監(jiān)測(cè)站位置保存到s＊中。

由于隨著部署的監(jiān)測(cè)站數(shù)量增加，入侵預(yù)警時(shí)間單調(diào)降低，而部署開(kāi)銷(xiāo)單調(diào)升高（這里省略數(shù)學(xué)證明），因此目標(biāo)函數(shù)fWT，c（s1∶n＊∪Ssd∪r1∶m，w）為n的凸函數(shù)，所以在fmin中可以通過(guò)線性搜索找到最優(yōu)的監(jiān)測(cè)站數(shù)量s＊。

WNMCP算法的第17行判別s＊是否應(yīng)該加入部署方案Ssd∪｛r1，r2，…，rm｝中，該判別條件有兩條：①以前迭代得到的部署方案無(wú)法滿(mǎn)足預(yù)設(shè)的入侵檢測(cè)率（pold＜p＊）；②前面部署方案的目標(biāo)值不小于加入s＊后的目標(biāo)值（fold≤fcur）。也就是說(shuō)算法通過(guò)條件1滿(mǎn)足約束條件，通過(guò)條件2降低目標(biāo)值。當(dāng)兩個(gè)條件都不滿(mǎn)足時(shí)，算法返回得到的部署方案S＊，否則表明還有優(yōu)化的余地，把s＊加入方案中。

下面證明算法得出的配置方案為局部最優(yōu)解，首先證明如下假設(shè)。

假設(shè)1 算法返回配置方案S＊后，對(duì)于沒(méi)有入選S＊的候選監(jiān)測(cè)站集合中任意一個(gè)監(jiān)測(cè)站s∈｛Sd＼S＊｝∪｛r｝，有

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

這里n′s＝min（pd（S＊∪s1∶n）≥p＊），因?yàn)閜d（S＊）≥p＊，所以對(duì)于s∈｛Sd＼S＊｝∪｛r｝，有n′s＝1。

因此可得

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

從以上兩個(gè)不等式可得

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

這與式（12）矛盾。證畢

如果假設(shè)1成立，即對(duì)最優(yōu)解S＊新增加任何一個(gè)監(jiān)測(cè)節(jié)點(diǎn)都會(huì)導(dǎo)致目標(biāo)函數(shù)值增加，再結(jié)合WNMCP算法第17行的判別條件，可以得出S＊是WNMCP問(wèn)題的局部最優(yōu)解。

3 仿真結(jié)果分析

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

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

因?yàn)楣潭ūO(jiān)測(cè)站需要專(zhuān)門(mén)部署在海上并需要定期派人維護(hù)，所以開(kāi)銷(xiāo)較大，而對(duì)于移動(dòng)監(jiān)測(cè)站，可以在有試驗(yàn)任務(wù)時(shí)把監(jiān)測(cè)裝備安裝在艦艇上，維護(hù)也較為方便，所以開(kāi)銷(xiāo)較小。

把仿真樣本輸入算法，表1給出了當(dāng)權(quán)重w變化時(shí)計(jì)算出的監(jiān)測(cè)站優(yōu)化部署方案，其中最小檢測(cè)概率閾值p＊設(shè)置為0．95。表1中｜Ss｜、｜Sf｜和｜Sr｜分別表示計(jì)算出的固定監(jiān)測(cè)站、設(shè)定路徑監(jiān)測(cè)站和隨機(jī)路徑監(jiān)測(cè)站的數(shù)量。

表1 算法計(jì)算結(jié)果比較

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

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

圖2為隨著監(jiān)測(cè)節(jié)點(diǎn)（選擇部署于圖節(jié)點(diǎn)的監(jiān)測(cè)站）數(shù)量變化，3個(gè)算法預(yù)警時(shí)間的變化情況。隨著監(jiān)測(cè)節(jié)點(diǎn)數(shù)量增加，預(yù)警時(shí)間都相應(yīng)減少。由于WNMCP算法針對(duì)預(yù)警時(shí)間進(jìn)行了優(yōu)化，所以預(yù)警時(shí)間最短。而層次部署更多地把監(jiān)測(cè)站部署在監(jiān)測(cè)區(qū)域外圍，所以預(yù)警時(shí)間相較于隨機(jī)部署也有顯著縮短。

圖2 監(jiān)測(cè)節(jié)點(diǎn)數(shù)量對(duì)預(yù)警時(shí)間的影響

從圖3可以看出，隨著監(jiān)測(cè)節(jié)點(diǎn)數(shù)量增加，入侵檢測(cè)概率都相應(yīng)提高。這里WNMCP算法的檢測(cè)率下限設(shè)置為0．9，所以檢測(cè)率盡管提高幅度不高，但比較穩(wěn)定。而另外兩種算法由于缺少對(duì)檢測(cè)率的優(yōu)化，都比較低。特別是某些配置方案下層次部署甚至比隨機(jī)部署還要低，這可能因?yàn)樗诒Ｗo(hù)目標(biāo)外圍部署較多監(jiān)測(cè)站，一旦入侵者突防成功后，內(nèi)部區(qū)域則缺少有效的監(jiān)測(cè)兵力。

圖3 監(jiān)測(cè)節(jié)點(diǎn)數(shù)量對(duì)入侵檢測(cè)率的影響

4 結(jié) 論

針對(duì)廣域空間入侵檢測(cè)問(wèn)題，本文提出了一個(gè)異構(gòu)稀疏傳感器／監(jiān)測(cè)站的配置算法，該算法的設(shè)計(jì)框架具有良好的適應(yīng)性，能夠根據(jù)優(yōu)化目標(biāo)、監(jiān)測(cè)站類(lèi)型、入侵對(duì)象以及應(yīng)用環(huán)境的變化方便地進(jìn)行擴(kuò)展。下一步工作主要集中在兩個(gè)方面：一是如何利用數(shù)學(xué)規(guī)劃及組合優(yōu)化方法來(lái)改進(jìn)算法的運(yùn)行效率，另外需要積極收集監(jiān)測(cè)站點(diǎn)的虛警率及誤判率數(shù)據(jù)，提高仿真優(yōu)化算法的容錯(cuò)能力。以此為基礎(chǔ)，建立一個(gè)預(yù)警力量部署輔助決策支持系統(tǒng)，能夠?qū)︻A(yù)警方案進(jìn)行推演仿真和性能評(píng)估，并給出優(yōu)化結(jié)果。

［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，F(xiàn)iltser O，F(xiàn)raser 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，F(xiàn)akhri 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．（劉立佳，李相民，顏驥．基于高維多目標(biāo)多約束分組優(yōu)化的要地防空扇形優(yōu)化部署［J］．系統(tǒng)工程與電子技術(shù)，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算法的要地防空優(yōu)化部署方法［J］．自動(dòng)化學(xué)報(bào)，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．（譚錦，王凈西，陳晨．一種雷達(dá)紅外聯(lián)合部署模型及優(yōu)化求解方法［J］．火力與指揮控制，2011，36（4）：131－134．）

E－mail：zbtrueice＠163．com

王 睿（1975－），女，館員，碩士，主要研究方向?yàn)樾畔⒐芾怼?/p>

E－mail：kingwis＠163．com

胡 煒（1995－），男，碩士研究生，主要研究方向?yàn)樾畔⒐芾怼?/p>

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－），男，教授，博士，主要研究方向?yàn)閭鞲衅骶W(wǎng)絡(luò)部署、裝備保障。

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

2014－07－02；

2014－11－10；網(wǎng)絡(luò)優(yōu)先出版日期：2014－12－09。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www．cnki．net／kcms／detail／11．2422．TN．20141209．0116．003．html