计算机科学
超图
网络拓扑
资源配置
邻接矩阵
分布式计算
调度(生产过程)
时间复杂性
邻接表
数学优化
拓扑(电路)
图形
理论计算机科学
算法
计算机网络
数学
离散数学
组合数学
作者
Qi Hao,Di Zhou,Min Sheng,Shi Yan,Jiandong Li
标识
DOI:10.1109/icc45855.2022.9839274
摘要
As the spaceborne resources are heterogeneous and the satellite network topology changes constantly, various time-varying derivative graphs are designed to represent the data acquisition and delivery process in satellite-terrestrial integrated networks (STNs). However, the time complexity of resource allocation approaches based on assorted time-varying graphs is remaining obstinately exponential. Derived from the satellite vertical coverage feature, we design a more general relationship to involve a group of nodes in a hyperedge rather than the bilateral relationship between two nodes. In this paper, we propose a time-expanded hypergraph (TEH) to contract the adjacency matrix of the network topology. Based on the proposed TEH, the problem is formulated to minimize the consumption of the communication resource in the resource-limited STN while completing the same number of tasks. Since the problem is intractable by exhaustive search, we further propose a hybrid hyperedge and Lagrangian relaxation algorithm to perform optimal resource allocation through an oriented search for the feasible hyperedges to reduce the scale of searching. The simulation results validate that the proposed algorithm can effectively complete the tasks with lower time complexity.
科研通智能强力驱动
Strongly Powered by AbleSci AI