LAUSR

Abstract In this paper, we first propose a distributed minimum spanning tree (DMST) algorithm for optical satellite networks (OSNs). The OSNs are characterized by high dynamic topology, long-distance beam, directional links and supported up to several Gbps data rates. In addition, each satellite node has limited optical transceivers. The problem of constructing a minimum weight spanning tree (MST) in a network is NP-hard due to the transceiver limitation. What makes this problem more challenging is the requirement to deploy the network topology in a distributed scenario, since each node can have only direct information of its neighbors. A fully distributed approximation algorithm is developed, which constructs a spanning tree with approximate minimum average edge weight. We prove that the proposed algorithm can definitely produce a feasible solution. And then, based on the MST constructed by proposed algorithm, we also develop a connectivity guarantee (CG) algorithm to construct a robust topology. The CG algorithm can guarantee the requirement of number of incident links to each node, in order to postpone the performance degradation when a topology variation is taking place. Simulation results show that, compared with existing technologies, the proposed algorithms can achieve better performance with low computational complexity.