Due to the limited transmission range of airborne nodes, aeronautical ad hoc network suffers from frequent network partitioning in the highly-dynamic environment, which may affect the operation of network applications. In order to guarantee end-to-end connectivity, aeronautical ad hoc network should have the ability of fault-tolerance against link or node failures. Therefore, one or more relay nodes are required for constructing such a fault-tolerant network. As airborne nodes move, relay nodes need to move as well in order to re-establish the topology as quickly as possible. An online algorithm is proposed for relay nodes’ speed control to realize the network fault-tolerant during running time. Based on the network’s actual state, the online algorithm calculates relay nodes’ velocities such that the network can keep fault-tolerance and relay nodes, can travel a short total distance during the running time. Simulations demonstrate that the proposed algorithm is of great potential to be applied to aeronautical ad hoc networks.