| In recent years, with the maturity of inter satellite link (ISL) technology and the enhancement of on-board processing capability, the service of satellite system is no longer the simple "bent-pipe" model, constellation network has become an important trend in the development of satellite system. However, with the increasing number of satellites in outer space, the operation management on satellite system is becoming difficult. The ground station is not only a huge investment; operating costs are also extremely high. Therefore, how to optimize the network and reduce the demand of large increasingly constellation network for earth gateway station has become an important topic.In the second generation satellite system, using constellation network’s inter satellite link can effectively reduce the demand for resources on earth station. Under the support of inter satellite link and networking technologies, constellation system only needs to select the part of earth observation satellite to establish the link between satellite and earth. The direct link with earth station of satellite called gateway satellite, while the information is transmitted from one satellite to other satellite through the gateway satellite relay, which can not only break through the limitation of satellite services must be visible on earth, but also can save a lot of earth station resources.Gateway satellite selection problem refers to how to select a subset of the satellite as a gateway in the satellite visible set. In this paper, the gateway satellite selecting problem can be modeled by a constrained dominating set problem.and the complexity of gateway satellite selection problem is discussed. Due to the satellite network topology is highly dynamic and changeable, so the slow convergence of heuristic algorithm cannot be applied to gateway satellite selection problem. Our research focuses on approximation algorithm of the gateway satellite selection problem and its effective algorithm of the sub problems.The main study contents are as follows:(1) In constellation networks, to consume less ground station resources as well as getting lower latency of communications between satellites and ground stations, a gateway satellite selecting problem is proposed. The gateway satellite selecting problem can be modeled by a constrained dominating set problem.(2) The NP-completeness of the gateway satellite selecting problem.is proved by a polynomial time reduction from3-SAT problem.(3) Define a gateway satellite selection problem of sub problem-2limit-gateway satellite selection problems, and give polynomial time algorithm-matching algorithm.(4) Analysis of the causes of traditional greedy algorithm is not suitable for gateway satellite selection problems, and a greedy algorithm is designed. Theoretical analysis shows that when the maximum number of inter satellite links supported by a satellite is less than k, the greedy algorithm is H (k+1) approximation, where His harmonic function.(5) Based on the matching algorithm has improved the greedy algorithm, the performance of the improved greedy algorithm has enhanced.(6) The three algorithms are simulated; the simulation result shows that the data in the form of charts are analyzed. The experimental results show that:①The greedy algorithm can achieve nearly optimal performance when the scale of a constellation network is medium, the performance of the greedy algorithm is closed to H (k+1) approximating bound when the scale of a constellation network is huge. And in an average case, about20percent ground station resources can be saved if gateway satellites are chosen by the greedy algorithm.②Verified the performance of the matching algorithm.③The average performance of the greedy algorithm to hybrid algorithm is about2%of the ascension. Hybrid algorithm is adopted to improve the gateway satellite selection can further saving star-link resources.④When the satellite network topology structure is relatively simple, the performance of the improved greedy algorithm will be more obvious. |
PDF Full Text Request