论文标题
最小化卫星网络中地面站的安装成本：复杂性，动态编程和近似算法
Minimizing the Installation Cost of Ground Stations in Satellite Networks: Complexity, Dynamic Programming and Approximation Algorithm
论文作者
论文摘要
在这封信中，我们研究了RF/光学卫星网络（SATNETS）中地面站（GSS）的最佳选择，以最大程度地降低停电概率要求下的整体安装成本，假设站点之间的独立天气条件。首先，我们表明，优化问题可以作为二进制线性编程问题提出，然后给出正式的NP硬度证明。此外，我们设计了具有全局优化保证的伪多项式复杂性的动态编程算法以及有效的（多项式时间）近似算法，并具有可证明的性能保证，并在已达到的客观值与全局最佳最佳距离的距离上进行了可证明的性能保证。最后，通过数值模拟验证了所提出的算法的性能。
In this letter, we study the optimum selection of ground stations (GSs) in RF/optical satellite networks (SatNets) in order to minimize the overall installation cost under an outage probability requirement, assuming independent weather conditions between sites. First, we show that the optimization problem can be formulated as a binary-linear-programming problem, and then we give a formal proof of its NP-hardness. Furthermore, we design a dynamic-programming algorithm of pseudo-polynomial complexity with global optimization guarantee as well as an efficient (polynomial-time) approximation algorithm with provable performance guarantee on the distance of the achieved objective value from the global optimum. Finally, the performance of the proposed algorithms is verified through numerical simulations.
