预警网络优化配置算法研究

曾 斌，王 睿，胡 炜

（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