首页 理论教育网络重构的挑战与应对

网络重构的挑战与应对

【摘要】:而重新构建星间链路的代价较大,可能牵涉卫星姿态控制、星间波束对准、卫星轨道调整和收发功率调节等动作,既可能消耗大量的能量,也可能带来较大的重构时延。同样的,网络重构的原始最优化问题同样是一个MIP问题,作为非凸问题同样无法在多项式时间内求解。通过取消问题中的整型约束,可以得到问题的松弛形式,与初始化问题的松弛形式相同。

由于卫星的相对运动、定期关机以及卫星/链路的随机故障,空间信息网络在初始化之后,卫星的可视性关系和相对距离会不断发生变化,网络的可视性矩阵权重矩阵也会随之不断地改变。网络的动态性可以理解为:在某个参考时刻t 0,对应的可视性矩阵为开销矩阵为,经过持续时间t之后,在时刻t 1=t 0+t,由于卫星空间位置的变化,可视性矩阵变为χ、开销矩阵变为C。则t 0时的最优化拓扑不再最优,甚至不再可行。因此需要重新计算t 1时刻的最优或次优拓扑。

如果在t 1时刻按照网络初始化的方法来求解最优化问题,则得到的优化拓扑可能与t 0时刻的优化拓扑有很大差别,这就会导致网络中大量的链路需要重新构建。而重新构建星间链路的代价较大,可能牵涉卫星姿态控制、星间波束对准、卫星轨道调整和收发功率调节等动作,既可能消耗大量的能量,也可能带来较大的重构时延。因此,希望t 1时刻的计算结果能够尽量保持t 0时刻的拓扑结构,通过设置相应的约束条件尽量平滑掉可能变化很剧烈的星间位移情况,从而达到减少重构链路数量、降低能量开销和重构时延的目的。综合考虑网络重构时面临的拓扑控制问题,构建网络重构时的原始最优化问题为

式中,分别表示重构之后的加权代数连通度、权重矩阵、邻接矩阵和邻接矩阵中的元素;k表示网络重构前后允许调整的星间链路的数量;运算符“⊕”表示布尔计算中的异或(XOR)运算,所以表示重构前的最优化邻接矩阵A与重构后的最优化邻接矩阵之间不相同的元素数量不大于2k个,也就意味着重构前后变化的星间链路数量不大于k条。上述最优化问题考虑了重构之前的拓扑,并尽量延续原有的拓扑来降低网络重构的规模,从而降低网络拓扑更新的开销和时延。

同样的,网络重构的原始最优化问题同样是一个MIP问题,作为非凸问题同样无法在多项式时间内求解。采用穷举法虽然同样可以得到最优解,但是同样需要面对计算量过大的问题。通过取消问题中的整型约束,可以得到问题的松弛形式,与初始化问题的松弛形式相同。因此,同样采取贪婪算法,基于可视性条件变化后残余的链路,通过每次迭代增加一条“最佳”(即提高加权代数连通度最大)的链路,直至满足k条调整链路的约束,从而得到次优解。