如何解决网络初始化问题：优化方法

2023-07-02 理论教育版权反馈

【摘要】：空间信息网络加权代数连通度最大化拓扑控制的初始化问题指的是：在网络初始状态下或网络需要完全重新构建时，构建具有最大加权代数连通度的网络拓扑问题。与原始问题相比，由于放宽了约束条件，松弛问题的可行解集更大，因此其最优解能够表示原始问题解的上界。另一方面，对于小规模的空间信息网络，可以采用穷举法来获得原始问题的最优解。

空间信息网络加权代数连通度最大化拓扑控制的初始化问题指的是：在网络初始状态下或网络需要完全重新构建时，构建具有最大加权代数连通度的网络拓扑问题。该问题需要在满足上述约束条件的情况下最大化网络的加权代数连通度。因此，原始问题可以构建为

式中，优化参数为A和W，输入参数包括所有节点的瞬时位置、可视性矩阵χ、自由度约束向量d、开销矩阵C、单星资源总量向量C lim和权重分布区间［α，β］。而目标函数maxλ2是一个严格凹函数，因为根据Courant-Fischer定理，maxλ2事实上是W对应的拉普拉斯矩阵的一个线性函数集的逐点上确界：

式中，‖y‖表示向量y的模。另外，由于邻接矩阵A中的元素aij为0-1变量，因此该问题为一类混合整型规划（MIP）问题，此类问题已被证明是NP-hard问题，无法在多项式时间内求得最优解。

为了在多项式时间内求得问题的次优解，将原始问题中有关整型约束的条件取消，从而将问题松弛为凸优化形式：

值得注意的是，由于取消了整型约束，该问题中的邻接矩阵A中的元素aij不再被约束为0-1变量，而是允许在［0，1］区间内任意取值。该问题可以采用凸优化方法在多项式时间内精确求解。与原始问题相比，由于放宽了约束条件，松弛问题的可行解集更大，因此其最优解能够表示原始问题解的上界。但是，由于取消了整型约束，松弛问题解出的上界往往远大于实际最优解，因此该上界对求取问题的最优解或次优解并无实际意义。

另一方面，对于小规模的空间信息网络，可以采用穷举法来获得原始问题的最优解。在穷举法中，满足约束条件的所有可能性拓扑都将作优化计算，即根据可视性矩阵χ和自由度约束向量d，穷举所有满足A≤χ和Ae=d的邻接矩阵A，而针对每个给定的邻接矩阵，求解其加权代数连通度最大化解则退化为求解凸优化问题：

在这个退化的凸优化问题中，邻接矩阵A作为输入参数不再需要优化。对每个邻接矩阵A求得对应的最优解maxλ2（A）后，选取其中的最大值对应的A和W作为当前可视性和自由度约束条件下的最优化的拓扑，就可以得到原始问题的精确最优解。

然而，该穷举算法由于对每个可视性条件下的每种拓扑组合进行优化计算，因此需要极大的计算量。事实上，每个可视性条件下，采用穷举算法需要计算约次最优化计算，其中为每个可视性条件内的所有潜在边的数量。再考虑到可视性情况随着时间不断变化，因此当网络规模较小时，穷举算法能够作为最优解的求取方法；而当网络规模较大时，穷举算法因其呈指数增长的计算量而变得不再适用。