时变网络中最短路径的故障修复问题

Fault Repair of the Shortest Path in the Time-Varying Networks

摘要: 在交通和通信网络中，最短路径及其相关优化问题具有广阔的应用前景。而基于大规模网络的时变特性，时变最短路问题被逐渐关注并且进行了广泛研究。另外，为保证传输性能，当最短路径中存在链路或节点故障时，就需要对该路径进行快速恢复和重建，即需要根据故障影响范围制定切实可行的恢复机制使网络正常运行。进一步，为了提高网络服务质量，需要尽量降低路径恢复成本。因此，本文对时变网络中含有一条故障边的最短路径快速修复问题进行了研究，并提出了有效算法。该算法不仅保证了时变网络中沿路径经过时边赋权函数的时间连续性，而且充分利用了时变最短路子图，在保证传输连续性的基础上减少计算复杂度。最后得出，对于具有n个顶点和m条边的时变网络，算法的时间复杂度为，其中表示路径所有出发时间区间内受影响区间点数目的最大值，表示所有出发时间区间内受影响区间点和受影响区间边总数的最大值。

Abstract: In transportation and communication networks, the shortest path and its related optimization problems have broad application prospects. Based on the time-varying feature of large-scale networks, the time-varying shortest path problem has been gradually concerned and widely studied. In addition, in order to ensure the transmission performance, when there is a link or node failure in the shortest path, it is necessary to quickly recover and reconstruct the path, that is, it is necessary to formulate a feasible recovery mechanism according to the occurrence of failure to make the network operate normally. Further, in order to improve the quality of network service, it is necessary to minimize the cost of path recovery. Therefore, this paper studies the shortest path fast repair problem with a fault edge in time-varying networks, and proposes an effective algorithm. The algorithm not only ensures the time continuity between edges along the path in the time-varying network, but also makes full use of the time-varying shortest path subgraph to reduce the computational complexity. Finally, for the time-varying network with n vertices and m edges, the time complexity of the algorithm is , in which represents the maximum number of affected interval nodes in all departure time intervals of the path, and represents the maximum number of affected interval nodes and affected interval edges in all departure time intervals.