Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks

Ruisong Wang; Weichen Zhu; Gongliang Liu

doi:10.1007/978-3-031-04245-4_1

Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks

Ruisong Wang
, Weichen Zhu
, Gongliang Liu^*

^*Corresponding author for this work

Harbin Institute of Technology Weihai

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

Satellite networks have attracted a lot of attention due to their unique advantages such as wide coverage and high data rate. However, the increasing number of satellites make the design of inter-satellite links become more difficult and further lead to low resource utilization rate. Therefore, this paper aims to design an efficient but low complexity inter-satellite links establishment scheme. The energy consumption optimization problem is first formulated as a mixed integer linear programming. Then, a Lagrange relaxation method is used to decompose the optimization problem into two subproblems, i.e., routing problem and inter-satellite links design problem. The optimal routing scheme can be obtained by solving a min-cost max-flow problem. The inter-satellite links design problem can be solved by using branch and bound method in parallel. The suboptimal solution of original problem can be obtained through solving these subproblems. Finally, the simulation results have be given to verify the effectiveness of proposed algorithm.

Original language	English
Title of host publication	6GN for Future Wireless Networks - 4th EAI International Conference, 6GN 2021, Proceedings
Editors	Shuo Shi, Ruofei Ma, Weidang Lu
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	3-15
Number of pages	13
ISBN (Print)	9783031042447
DOIs	https://doi.org/10.1007/978-3-031-04245-4_1
State	Published - 2022
Externally published	Yes
Event	4th EAI International Conference on 6G for Future Wireless Networks, 6GN 2021 - Huizhou, China Duration: 30 Oct 2021 → 31 Oct 2021

Publication series

Name	Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST
Volume	439 LNICST
ISSN (Print)	1867-8211
ISSN (Electronic)	1867-822X

Conference

Conference	4th EAI International Conference on 6G for Future Wireless Networks, 6GN 2021
Country/Territory	China
City	Huizhou
Period	30/10/21 → 31/10/21

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

Inter-satellite link
Lagrange relaxation method
Satellite networks

Access to Document

10.1007/978-3-031-04245-4_1

Cite this

Wang, R., Zhu, W., & Liu, G. (2022). Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks. In S. Shi, R. Ma, & W. Lu (Eds.), 6GN for Future Wireless Networks - 4th EAI International Conference, 6GN 2021, Proceedings (pp. 3-15). (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST; Vol. 439 LNICST). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-04245-4_1

Wang, Ruisong ; Zhu, Weichen ; Liu, Gongliang. / Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks. 6GN for Future Wireless Networks - 4th EAI International Conference, 6GN 2021, Proceedings. editor / Shuo Shi ; Ruofei Ma ; Weidang Lu. Springer Science and Business Media Deutschland GmbH, 2022. pp. 3-15 (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST).

@inproceedings{5952a022532847c39cc8acbe6267f6fc,

title = "Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks",

abstract = "Satellite networks have attracted a lot of attention due to their unique advantages such as wide coverage and high data rate. However, the increasing number of satellites make the design of inter-satellite links become more difficult and further lead to low resource utilization rate. Therefore, this paper aims to design an efficient but low complexity inter-satellite links establishment scheme. The energy consumption optimization problem is first formulated as a mixed integer linear programming. Then, a Lagrange relaxation method is used to decompose the optimization problem into two subproblems, i.e., routing problem and inter-satellite links design problem. The optimal routing scheme can be obtained by solving a min-cost max-flow problem. The inter-satellite links design problem can be solved by using branch and bound method in parallel. The suboptimal solution of original problem can be obtained through solving these subproblems. Finally, the simulation results have be given to verify the effectiveness of proposed algorithm.",

keywords = "Inter-satellite link, Lagrange relaxation method, Satellite networks",

author = "Ruisong Wang and Weichen Zhu and Gongliang Liu",

note = "Publisher Copyright: {\textcopyright} 2022, ICST Institute for Computer Sciences, Social Informatics and Telecommunications Engineering.; 4th EAI International Conference on 6G for Future Wireless Networks, 6GN 2021 ; Conference date: 30-10-2021 Through 31-10-2021",

year = "2022",

doi = "10.1007/978-3-031-04245-4\_1",

language = "英语",

isbn = "9783031042447",

series = "Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "3--15",

editor = "Shuo Shi and Ruofei Ma and Weidang Lu",

booktitle = "6GN for Future Wireless Networks - 4th EAI International Conference, 6GN 2021, Proceedings",

address = "德国",

}

Wang, R, Zhu, W & Liu, G 2022, Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks. in S Shi, R Ma & W Lu (eds), 6GN for Future Wireless Networks - 4th EAI International Conference, 6GN 2021, Proceedings. Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST, vol. 439 LNICST, Springer Science and Business Media Deutschland GmbH, pp. 3-15, 4th EAI International Conference on 6G for Future Wireless Networks, 6GN 2021, Huizhou, China, 30/10/21. https://doi.org/10.1007/978-3-031-04245-4_1

Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks. / Wang, Ruisong; Zhu, Weichen; Liu, Gongliang.
6GN for Future Wireless Networks - 4th EAI International Conference, 6GN 2021, Proceedings. ed. / Shuo Shi; Ruofei Ma; Weidang Lu. Springer Science and Business Media Deutschland GmbH, 2022. p. 3-15 (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST; Vol. 439 LNICST).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks

AU - Wang, Ruisong

AU - Zhu, Weichen

AU - Liu, Gongliang

PY - 2022

Y1 - 2022

N2 - Satellite networks have attracted a lot of attention due to their unique advantages such as wide coverage and high data rate. However, the increasing number of satellites make the design of inter-satellite links become more difficult and further lead to low resource utilization rate. Therefore, this paper aims to design an efficient but low complexity inter-satellite links establishment scheme. The energy consumption optimization problem is first formulated as a mixed integer linear programming. Then, a Lagrange relaxation method is used to decompose the optimization problem into two subproblems, i.e., routing problem and inter-satellite links design problem. The optimal routing scheme can be obtained by solving a min-cost max-flow problem. The inter-satellite links design problem can be solved by using branch and bound method in parallel. The suboptimal solution of original problem can be obtained through solving these subproblems. Finally, the simulation results have be given to verify the effectiveness of proposed algorithm.

AB - Satellite networks have attracted a lot of attention due to their unique advantages such as wide coverage and high data rate. However, the increasing number of satellites make the design of inter-satellite links become more difficult and further lead to low resource utilization rate. Therefore, this paper aims to design an efficient but low complexity inter-satellite links establishment scheme. The energy consumption optimization problem is first formulated as a mixed integer linear programming. Then, a Lagrange relaxation method is used to decompose the optimization problem into two subproblems, i.e., routing problem and inter-satellite links design problem. The optimal routing scheme can be obtained by solving a min-cost max-flow problem. The inter-satellite links design problem can be solved by using branch and bound method in parallel. The suboptimal solution of original problem can be obtained through solving these subproblems. Finally, the simulation results have be given to verify the effectiveness of proposed algorithm.

KW - Inter-satellite link

KW - Lagrange relaxation method

KW - Satellite networks

UR - https://www.scopus.com/pages/publications/85130387761

U2 - 10.1007/978-3-031-04245-4_1

DO - 10.1007/978-3-031-04245-4_1

M3 - 会议稿件

AN - SCOPUS:85130387761

SN - 9783031042447

T3 - Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST

SP - 3

EP - 15

BT - 6GN for Future Wireless Networks - 4th EAI International Conference, 6GN 2021, Proceedings

A2 - Shi, Shuo

A2 - Ma, Ruofei

A2 - Lu, Weidang

PB - Springer Science and Business Media Deutschland GmbH

T2 - 4th EAI International Conference on 6G for Future Wireless Networks, 6GN 2021

Y2 - 30 October 2021 through 31 October 2021

ER -

Wang R, Zhu W, Liu G. Lagrange Relaxation Based Inter-satellite Links Scheduling for Satellite Networks. In Shi S, Ma R, Lu W, editors, 6GN for Future Wireless Networks - 4th EAI International Conference, 6GN 2021, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 3-15. (Lecture Notes of the Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering, LNICST). doi: 10.1007/978-3-031-04245-4_1