保持网络连通性的最优节点配置问题

许 珂 ，陆 疌

（1.上海微系统与信息技术研究所微系统技术重点实验室，上海200050；2.上海科技大学信息科学与技术学院，上海201210；3.中国科学院大学北京100049）

无线传感网络，移动机器人网络，通信网络等协同网络在现在的社会中有着广泛的应用，例如运动协调[1]，目标追踪[2]，资源分配[3]等。为了满足绝大多数的协同工作，都会要求网络本身能够保持连通的拓扑结构。到目前为止，许多学者对网络连通性的相关问题[4-10]展开了广泛研究。例如，Spanos等人提出几何连通的鲁棒性，提供了多智能网络中在保持连通性的情况下，智能体的可移动范围[4]。还有通过建立最大化网络的代数连通度模型（代数连通度是网络对应的Laplace矩阵的第二最小特征值，表示无向网络中连通程度）来解决保持网络连通性的问题[9-10]。

文中构造一个与上述方式不同的混合整数模型来解决网络连通性的问题。在保持放置节点的网络连通的同时，要求节点能够最优配置。

1 最优节点配置问题的实例

节点V={1,2,3}可以被放置在如图一所示的5个位置上，灰色的线段表示可能存在的边（当且仅当该条边的左右两个位置都放置了节点，该条边才存在）。为了简单起见，假设在这个例子中，不考虑每个节点放置到任一位置上的费用，即放置节点的费用都相同，则图二所表示的即为最优节点配置问题的一个最优解，位置1，2，4在放置节点后构成一个连通的网络。

图1 节点配置问题

图2 节点配置问题解

2 问题模型

假设网络G={C,E}是连通的（若网络不连通，则网络可根据其拓扑结构分为两个子网络，分别在两个子网络上求解原问题），C={1,2,...,C}表示网络中位置的集合，E⊂C×C即网络中位置之间边的集合。有V个节点V={1,2,...,V}和C个网络中的位置C={1,2,...,C}。对于每一个节点v∈V和网络中的位置i∈C，定义变量表示当节点v被放置到位置i上时定义(·)为节点v被放置到位置i上时的费用函数。在这里，我们定义一个子网络表示放置节点的位置构成的网络，其中即为分配 了 节 点 的 位 置 的 集 合即为和相关的边的集合。

2.1 目标函数

本问题的目标是最小化放置节点到网络中位置的费用，显而易见，通过上述对变量的定义，总费用如下：

2.2 函数约束

本问题的约束可以分为两个类型，资源分配约束和网络位置连通性约束。

2.2.1 资源配置约束

节点配置问题实际上就是资源配置问题的一种变形，因此，它保有常见资源配置问题的约束。

1）每个节点只能分配到一个位置；

2）每个位置上最多只能放置一个节点。

2.2.2 网络位置连通性约束

为了保证放置节点的网络可以保持连通性，我们需要增加相应的约束。对于无向图G={C,E}是连通图当且仅当对于任意的(i,j)∈E,i≠j，存在一条从i到j的路径。对于有向图G={C,E}是强连通图当且仅当对于任意的有序组合(i,j)∈E,i≠j，存在一条从i到j的有向路径。根据有向图和无向图关于网络连通性的定义，我们将此部分约束分为两类，在下一章节中详细介绍。

2.3 数学模型

最优节点配置问题可以被表示为：

s.t.约束（1）（2）

3 子图的连通性约束

现如今，有很多学者提出了建立不同的优化模型用来解决网络连通性问题[11-22]。例如Miller等人提出通过Miller-Tucker-Zemlin约束解决旅行商问题。他们提出的大部分方法是通过解决最小生成树问题转化为解决网络连通性问题。其中，单一商品流约束（Single-Commodity Flow Constraints，SCFC）被Neng Fan等人通过建立混合整数规划模型解决网络连通性的问题--连接支配集（Connected Dominating Set）和电力支配集（Power Dominating Set）问题[15]。文中运用单一商品流约束来构造最优节点配置问题中的连通性约束。

3.1 无向图的连通性约束

毫无疑问的，如果一个无向图是连通的，当且仅当它包含一棵生成树。SCFC就是通过构造一棵生成树的方式来保证网络的连通性。首先，我们将放置节点“1”的网络位置定义为所构造生成树的根，由根向放置了节点的其他位置发出|V|-1个单位流，流经每一个放置节点的位置都会消耗一个单位流，其他位置不消耗流。为了构造这样的流结构，引入一组辅助变量fij∈R，对于每一条边(i,j)∈E，fij是从位置i到j流经的流数目。

保持连通性的约束如下：

约束（5）确保每条边上的流是非负的；约束（6）表示当网络中位置i，j中有任一位置没有放置节点时，变量fij等于0；而约束（7）保证流入根的流的总和为0；最后，约束（8）确保了每个位置上流的流入流出是平衡的，如果位置i放置节点“1”（即为根），那么位置i流入流出流的差值等于1-|V|，如果位置i上放置某一节点（除了节点“1”），流入流出的流的差值应当为-1，其他的情况，流入流出的流的差为0。

所有满足SCFC约束的最优节点配置问题的可行解都可以保证：每一个被放置节点的位置（除了被选中为生成树根的位置）都会消耗一个来自根的单位流，因此网络的连通性也可以保障。

考虑到之前节点配置问题提出的约束（1）-（2），在这个模型中，总共有|V||C|+||E个变量和|V|+3|C|+3|E|=O(|V|+|C|+|E|)个约束，其中整数变量为|V||C|个。

3.2 有向图的连通性约束

在3.1中，对于无向图，我们只需要构造一个生成树来保证网络连通性，但在有向图中，仅仅构造一个生成树是不能满足强连通条件的。因此，在单一商品流约束的基础上，要求每个放置了节点的位置都需要作为生成树的根，构造|V|棵对应的生成树，按照放置节点的顺序分别称为生成树1,2,3,...,|V|。

保持连通性的约束如下：

约束（9）是确保放置节点k∈V的位置作为生成树k的根时，每条边上的流是非负的；约束（10）表示当网络中位置i，j中有任一位置没有放置节点时，在构造的每一个生成树中，流过(i,j)的流为0，即变量等于0；而约束（11）是对应于构造的每一棵生成树k的根，流入根的流的总和为0；最后，约束（12）确保了对于每一棵生成树k，每个位置上流的流入流出是平衡的，如果位置i放置节点k（即作为生成树k的根，=1），那么对于生成树k有3种情况，一是位置i流入流出流的差等于1-|V|，二是位置i上放置某一节点（除了节点k），流入流出流的差值应当为-1，其他的情况，流入流出的流为0。

考虑到之前节点配置问题提出的约束（1）-（2），在这个模型中，总共有|V||C|+|E||V|个变量和|V|+(1+2|V|)|C|+3|E||V|个约束，其中，整数变量为|V||C|。

4 仿真实验

首先，我们使用现有的优化软件包来仿真验证模型的正确性。仿真环境是在matlab 2012a。使用传统的分支界定算法求解该问题，并验证结果的正确性[23]。

以无向图对应的模型为例，我们考虑这样一个网络结构：14个网络位置和6个节点，如图3所示。简单起见，令费用函数为线性函数，节点放置不同位置上对应的费用如表1所示。通过解决包含SCFC约束的最优节点配置问题对应混合整数模型[24]，最优值为105，对应的最优解为（位置-节点）：{1-4，2-3，3-6，5-1，6-2，11-5}。

图3 节点配置问题例子

下一步，我们尝试了解决若干不同规模的网络和节点数量的问题。以无向图的模型为例，仿真结果如下图所示，横轴表示构造的模型中整数变量的个数，纵轴表示的是通过分支界定算法寻找到最优解的迭代次数。所有的规模都在有限次迭代中找到的最优解，但显而易见，随着整数变量个数的增加，所需的迭代次数也飞速增加。

表1 放置节点的费用

图4 仿真数据

5 结论

文中建立了一个保持网络连通性的最优节点配置问题的优化模型。在此基础上，分别考虑了无向图和有向图的两种网络拓扑结构，提出了基于单一商品流约束构造混合整数规划的方法。最后使用用传统的分支界定算法求解此问题的最优解。通过解决这样数学问题，我们可以解决很多真实世界中的具体工程问题，例如物流上的站点分配，无线传感网络中和连通性相关的传感器配置等问题。