系统工程与电子技术 ›› 2022, Vol. 44 ›› Issue (4): 1343-1353.doi: 10.12305/j.issn.1001-506X.2022.04.33

• 通信与网络 • 上一篇    下一篇

卫星网络时隙分配算法与路由规划优化

王瑞松1, 马若飞1, 王琦2, 钟志聪1, 刘功亮1,*, 张杨3   

  1. 1. 哈尔滨工业大学(威海)信息科学与工程学院, 山东 威海 264209
    2. 北京跟踪与通信技术研究所, 北京 100094
    3. 航天东方红卫星有限公司, 北京 100094
  • 收稿日期:2021-02-03 出版日期:2022-04-01 发布日期:2022-04-01
  • 通讯作者: 刘功亮
  • 作者简介:王瑞松(1996—), 男, 博士研究生, 主要研究方向为卫星通信、网络编码、资源优化分配|马若飞(1984—), 男, 副教授, 博士, 主要研究方向为D2D通信、智能互联车辆、水下通信和网络|王琦(1984—), 女, 助理研究员, 硕士, 主要研究方向为星间链路技术|钟志聪(1997—), 男, 硕士研究生, 主要研究方向为卫星通信、网络编码|刘功亮(1979—), 男, 教授, 博士, 主要研究方向为无线通信与网络、卫星通信、水下通信|张杨(1981—), 女, 工程师, 硕士, 主要研究方向为卫星通信
  • 基金资助:
    国家自然科学基金(61971156);国家自然科学基金(61801144);山东省自然科学基金(ZR2019MF035);山东省自然科学基金(ZR2019QF003);山东省自然科学基金(ZR2020MF141);中央高校基本科研业务费专项(HIT.NSRIF.2019081);哈尔滨工业大学(威海)科研创新基金(2019KYCXJJYB06)

Optimization of time slot allocation algorithm and routing scheduling for satellite network

Ruisong WANG1, Ruofei MA1, Qi WANG2, Zhicong ZHONG1, Gongliang LIU1,*, Yang ZHANG3   

  1. 1. School of Information Science and Engineering, Harbin Institute of Technology, Weihai 264209, China
    2. Beijing Institute of Tracking and Telecommunications Technology, Beijing 100094, China
    3. Aerospace Dongfanghong Satellite Co., Ltd., Beijing 100094, China
  • Received:2021-02-03 Online:2022-04-01 Published:2022-04-01
  • Contact: Gongliang LIU

摘要:

星间链路的应用在增加网络连通性和提升网络性能方面是至关重要的。然而, 对于大规模、高动态的卫星网络, 实时的星间链路设计和路由规划变得非常有挑战性。为了克服这个难点, 本文研究了动态卫星网络中的时隙分配与路由规划问题, 并将其建模为一个整数线性规划问题。为了降低问题求解的复杂度, 该问题被近似地分解为两个独立的子问题, 包括时隙分配问题与路由规划问题。第一个子问题仍然是一个整数规划问题, 本文结合匹配理论与拉格朗日松弛方法设计了一个低复杂度但是高效的求解算法。然后, 针对第二个子问题, 考虑业务的优先级, 设计了一个低花费的路由算法。最后, 仿真结果验证了方法的可行性与有效性。

关键词: 卫星网络, 拉格朗日松弛, 时隙分配, 路由规划

Abstract:

The inter-satellite links play a crucial role in increasing network connectivity and improving network performance. However, it is very challenging to design the real time inter-satellite links and routing scheme for large scale and high dynamic satellite networks. To overcome this difficulty, this paper studies the time slot allocation and routing scheduling problem for dynamic satellite networks, and then formulates it as an integer linear programming problem. To decrease the solving complexity, the proposed problem is approximatively decomposed into two independent subproblems, namely, the time slot allocation problem and the routing scheduling problem. To deal with the integer programming in the first subproblem, the matching theory and the Lagrangian relaxation method are used to design a low complexity but efficient algorithm. Moreover, for the second subproblem, we design a low cost routing algorithm considering the priorities of the missions. Finally, the simulation results verify the feasibility and effectiveness of the proposed method.

Key words: satellite network, Lagrange relaxation, time slot allocation, routing scheduling

中图分类号: