# [1]吴俊,陆延,李斌.星座网络的网关卫星选择问题[J].东南大学学报(自然科学版),2013,43(6):1152-1156.[doi:10.3969/j.issn.1001-0505.2013.06.004] 　Wu Jun,Lu Yan,Li Bin.Gateway satellite selection problem in constellation networks[J].Journal of Southeast University (Natural Science Edition),2013,43(6):1152-1156.[doi:10.3969/j.issn.1001-0505.2013.06.004] 点击复制 星座网络的网关卫星选择问题() 分享到： var jiathis_config = { data_track_clickback: true };

43

2013年第6期

1152-1156

2013-11-20

## 文章信息/Info

Title:
Gateway satellite selection problem in constellation networks

Author(s):
School of Information and Engineering, Yangzhou University, Yangzhou 225000, China

Keywords:

TP393
DOI:
10.3969/j.issn.1001-0505.2013.06.004

Abstract:
In constellation networks, to consume less ground station resources and get lower latency of communications between satellites and ground stations, a gateway satellite selecting problem is proposed. The complexity and the greedy algorithm of this problem is thoroughly investigated by modeling the gateway satellite selecting problem as a constrained dominating set problem. The NP(nondeterministic polynomial time)-completeness of the gateway satellite selecting problem is proved by a polynomial time reduction from 3-SAT(satisfiability)problem. To deal with the difficulty of the problem, a greedy algorithm is designed. The theoretical analysis results show 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 H is the harmonic function. The simulation results show that the greedy algorithm is nearly optimal when the scale of a constellation network is medium. However, the number of gateway satellites found by the greedy algorithm is about H(k+1)times that of optimal solution when the scale of a constellation network is huge. In an average scale of the constellation network, about 20% ground station resources can be saved when gateway satellites are chosen by the greedy algorithm.

## 参考文献/References:

[1] 王振永, 王平,顾学迈,等.卫星网络中永久星间链路的设计方法研究[J].通信学报,2006,27(8): 129-133.
Wang Zhenyong, Wang Ping, Gu Xuemai, et al. Research on design of permanent inter-satellite-links in satellite networks [J]. Journal of Communication, 2006, 27(8):129-133.(in Chinese)
[2] Shahriar A M, Atiquzzaman M, Ivancic W. Network mobility in satellite networks: architecture and the protocol[J]. International Journal of Communication Systems, 2013, 26(2): 177-197.
[3] Liu Z G, Xu K, Pan C S. Optimized resource in satellite network based on genetic algorithm[J]. International Journal of Innovative Computing Information and Control, 2012, 8(12): 8249-8256.
[4] Alagoz F, Korcak O, Jamalipour A. Exploring the routing strategies in next-generation satellite networks [J]. Wireless Communications, 2007, 14(3):79-88.
[5] Aftab F, Younas S, Aftab K. Communication issues in satellite links: a comprehensive survey[C]//Proceedings of 4th International Conference on Wireless Communications, Networking and Mobile Computing(WiCOM’08). Dalian, China, 2008: 1-6.
[6] Pacheco D M L, Thai T T. An IP-ERN architecture to enable hybrid E2E/ERN protocol and application to satellite networking[J]. Computer Networks, 2012, 56(11):2700-2713.
[7] Zhang Zhu, Guo Qing. An IP mobility management scheme with dual location areas for IP/LEO satellite network[J]. Journal of Zhejiang University-Science C: Computers & Electronics, 2012, 13(5):355-364.
[8] Gamvros I, Raghavan S. Multi-period traffic routing in satellite networks[J]. European Journal of Operational Research, 2012, 219(3):738-750.
[9] Yang D N, Liao W J. On multicast routing using rectilinear steiner trees for LEO satellite networks [J]. IEEE Transactions on Vehicular Technology, 2008, 57(4): 288-300.
[10] 吴国强,孙兆伟, 赵丹,等. 编队小卫星星间通信系统的发展和趋势[J].哈尔滨工业大学学报, 2007, 39(11):1699-1703.
Wu Guoqiang, Sun Zhaowei, Zhao Dan, et al. Development and trend research of inter-satellite communication system on formation small satellites[J]. Journal of Harbin Institute of Technology, 2007, 39(11):1699-1703.(in Chinese)
[11] 堵丁柱,葛可一,胡晓东.近似算法的设计与分析 [M].北京:高等教育出版社,2011:52.