有关静态监控设备位置优化的研究

秦瑛

（建设综合勘查研究设计院有限公司北京市100007）

摘要：网络监控技术的提升已变得越来越重要，主要体现在监控服务器的性能评估与监控设备的布置等方面。比较常见的两种监控策略分别是静态监控与动态监控，而关键的问题是要将支持监控的硬件、软件以及维护成本尽可能最小化。本文对有关静态监控设备位置优化的问题进行了深入分析，并用整数规划的方法对其进行数学建模并实现得出近似最优解。

关键词：静态监控，成本最小化，整数规划。

0.引言

本文试图对静态监控的成本进行优化，具体体现在对静态监控设备位置的选取上。本文提出了基于组合数学观点的数学模型，并给出了其复杂性与近似解。本文还提出了一个有效的整数规划的方法，这个方法不仅将成本最小化，而且同时也将监视的范围做到了最大化。另外，这个方法允许我们做一些细微的改变，去解决其它问题。比如寻找增益解，在现有的监控设备布置中添加新的监控设备，评估添加设备所能获得的预期的效益[2，3]。

1.静态监控设备位置优化模型的阐述

本章将介绍静态监控。静态监控不进行对现场之后可能会发生的情形的预判，而且由于数据处理与存储的要求，监控设备的运行可能会非常昂贵。于是，在保证监控质量的前提下，将监控设备的数量最小化就显得尤为重要。我们提出了一个契合实际的解决方案，并用整数规划的方法阐述其数学模型。

首先引出“最小集合覆盖”的概念。给定全集U和它的的一组子集组成的集合S。则“最小集合覆盖”问题是指寻找一个最小的C，，并且C的并集为全集U。在静态监控环境中，集合S中的任一元素代表监控区域中的其中一条走廊或通道。于是，通过“最小集合覆盖”问题，我们可以构造出一个数学模型，使我们达到安装最少的监控设备，并且监控到完整区域的目的。换句话说，解决“用最少的监控设备监控完整区域”的问题，与求“最小集合覆盖”的问题是等价的。我们给出其详细证明过程：

证明：设G是一个图，它的边的集合E的定义如下：

1.对任意，E中都包含一条边。

2.如果，则E中包含两条边与，他们与和相邻并且与他们一同构成一个环路。

现在，我们假设是布置监控设备的最优解。于是我们可以通过如下的方法，从推导出最小集合覆盖：

由于最小集合覆盖问题是一个完全性问题，因此本文所提出的静态监控设备位置优化的问题也是一个完全性问题。于是，在计算该问题的最优解时，我们通常会选择去计算近似解。一个k次近似解是问题的一个可行解，它的计算成本总是介于k倍的最优解的计算成本之下。如果采用简单的贪婪算法求解，则最小集合覆盖问题的计算成本近似于。在求解静态监控设备位置优化的问题时，一个等价的结果可以通过采用次近似算法得到[4]。

然而，一个更为有效的求解方法是将问题转化为“最小成本最大流”问题[1]，并用整数规划的方法进行求解。我们来定义这个“最小成本最大流”问题，首先定义一个起辅助作用的有向图：

4.从顶点S到任一顶点，A中都包含一个不限流量且成本为1的弧，进而每一条弧都对应监控场景来里的其中一条边e。

5.A中存在一条从到的弧，当且仅当通路经p过边e。这些弧的成本为0，且不限流量，代表着监控场景中通路与边的对应关系。

6.从任一顶点到顶点T，A中都包含一个流量为且成本为0的弧。

于是，我们的目标变为寻找一条从S到T的通路，且它的流量与监控场景中的流量相等，即。接下来，我们证明在上解决“最小成本最大流”问题与在G上解决“用最少的监控设备监控完整区域”的问题是等价的。我们给出其证明过程：

因此，如果是最小成本最大流问题的最优解，则它也是静态监控设备位置优化问题的最优解。否则，假设是后者的最优解，由于最小成本最大流问题的任何一个解都是静态监控设备位置优化问题的一个解，则。而基于我们构造的图，我们可以看出对于任何，都成立，进而产生矛盾。

另一方面，最小成本最大流问题的解可以通过构造出来。我们注意到在顶点与之间只存在一条通路，记为。对于任何一条边，如果通路p在解中经过边e，我们就在通路添加一个流量。在最小成本最大流问题中，弧上的流量限制是给定的。由于监控场景中的流量至少为，因此最小成本最大流问题的流量值也至少为。因此，这个解是该最小成本最大流问题的解，但它的成本小于，进而产生矛盾。证毕。

至此，我们便可以运用整数规划的方法构造数学模型了。整个数学模型基于弧与通路之间的关系，并添加了一个0-1变量用来表示某个通路是否是非0通路。我们用表示共同经过顶点与的流，则具体数学模型如下：

我们用CPLEX来对其进行仿真，根据监控服务器数量的不同得到如下结果：

因此，我们得出使用10台监控服务器与11台监控设备的方案是最为有效的。

2.结语

本文对有关静态监控设备位置优化的问题进行了深入分析，并将其转化为等价的最小合集覆盖问题，随后用最小成本最大流问题将最小集合覆盖问题进行转化，并用整数规划的方法对其进行数学建模并实现得出结论。整数规划的方法非常的灵活，它可以在场景出现改变时做出简单的调整即可，不需要重新构建新的模型。

参考文献:

[1].G.Even,G.Kortsarz,andW.Slany.Onnetworkdesignproblems:fixedcostflowsandthecoveringSteinerproblem.TransactionsonAlgorithms,2004.

[2].梁华。智能建筑弱电工程设计与安装。北京，中国建筑工业出版社，2011.

[3].马秀林，徐岩，王增平。静态优化法编号在潮流计算中的应用。电力科学与工程，第23卷第2期，2007.

[4].KyoungwonSuh,YangGuo,JimKurose,andDonTowsley.Locatingnetworkmonitors:complexity,heuristics,andcoverage.ProceedingsofIEEEInfocom,Miami,USA,2005.