许 珂 ，陆 疌

（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即网络中位置之间边的集合。……