[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]
点击复制

星座网络的网关卫星选择问题()
分享到:

《东南大学学报(自然科学版)》[ISSN:1001-0505/CN:32-1178/N]

卷:
43
期数:
2013年第6期
页码:
1152-1156
栏目:
计算机科学与工程
出版日期:
2013-11-20

文章信息/Info

Title:
Gateway satellite selection problem in constellation networks
作者:
吴俊陆延李斌
扬州大学信息工程学院, 扬州 225000
Author(s):
Wu Jun Lu Yan Li Bin
School of Information and Engineering, Yangzhou University, Yangzhou 225000, China
关键词:
网关卫星 NP完全性 贪婪算法
Keywords:
gateway satellite NP(nondeterministic polynomial time)-complete greedy algorithm
分类号:
TP393
DOI:
10.3969/j.issn.1001-0505.2013.06.004
摘要:
为了既能获得较好的星座网络星-地通信延迟性能又能较少地占用地面站资源,提出了网关卫星选择问题.将网关选择问题建模成一种受限的支配集模型,对该问题的复杂性和贪心选择算法进行了研究.通过将3-SAT问题多项式时间规约到网关卫星选择问题,从而证明了网关卫星选择问题是NP完全的.同时,设计了网关卫星选择问题的贪心算法,理论分析表明,若每颗卫星最多支持k条星间链路,则贪心选择算法是H(k+1)近似的,其中H表示调和函数.仿真实验结果表明,贪心算法在星座规模中等时性能接近最优解,在星座规模相对较大时性能接近H(k+1)的近似界.在平均规模情况下,采用贪心算法进行网关卫星选择能节省20%左右的星-地链路资源.
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.

备注/Memo

备注/Memo:
作者简介: 吴俊(1970—),男,博士,副教授, wujun@yzu.edu.cn.
基金项目: 国家自然科学基金资助项目( 61070210,61070133)、江苏省网络与信息安全重点实验室开放课题基金资助项目(BM2003201-201001).
引文格式: 吴俊,陆延,李斌.星座网络的网关卫星选择问题[J].东南大学学报:自然科学版,2013,43(6):1152-1156. [doi:10.3969/j.issn.1001-0505.2013.06.004]
更新日期/Last Update: 2013-11-20