技术领域Technical Field
本发明涉及一种低时延业务天基计算方法，属于天基计算技术领域。The invention relates to a low-latency service space-based computing method, and belongs to the technical field of space-based computing.
背景技术Background technique
低轨组网星座发展迅速，通过低轨星座完成军用民用业务的需求不断增加，其中包含卫星低时延处理传输业务，例如目标快速提取、环境快速感知等军事应用以及搜救等应急救援应用，在这些应用中，传感器产生的数据量越来越大，数据处理计算越来越复杂，计算依赖越来越严重，与业务的低时延要求形成矛盾。同时，地域和时区差异、星座运转及地球自转导致卫星通信网承载分布不均衡，流量负载具有时变特性。单颗星既可能覆盖流量稀少的区域，如极地区域和海洋，也可能覆盖人口密集且数据量密集的区域，如发达国家的主要城市。导致卫星计算和通信资源的使用极不平衡，部分卫星高负载运行，部分卫星计算通信资源闲置。Low-orbit network constellations are developing rapidly, and the demand for completing military and civilian services through low-orbit constellations is increasing, including satellite low-latency processing and transmission services, such as military applications such as rapid target extraction and rapid environmental perception, as well as emergency rescue applications such as search and rescue. In these applications, the amount of data generated by sensors is increasing, data processing calculations are becoming more and more complex, and the computing dependence is becoming more and more serious, which is in conflict with the low-latency requirements of the services. At the same time, differences in regions and time zones, constellation operations, and the rotation of the earth lead to uneven distribution of satellite communication network loads, and traffic loads have time-varying characteristics. A single satellite may cover areas with sparse traffic, such as polar regions and oceans, or it may cover densely populated and data-intensive areas, such as major cities in developed countries. This leads to extremely unbalanced use of satellite computing and communication resources, with some satellites operating at high loads and some satellite computing and communication resources idle.
随着卫星在轨处理技术的发展，可提供一定程度的计算能力，然而，由于其尺寸、功耗的限制，天基计算平台存在诸如计算能力弱、存储空间小等资源受限的问题，单个卫星节点难以满足低时延的计算要求，因此，如何基于有限的天基计算资源，通过多个卫星节点的协同，同时实现低时延业务的处理传输成为需要迫切解决的问题。With the development of satellite on-orbit processing technology, a certain degree of computing power can be provided. However, due to the limitations of its size and power consumption, the space-based computing platform has resource-limited problems such as weak computing power and small storage space. A single satellite node is difficult to meet the low-latency computing requirements. Therefore, how to achieve low-latency business processing and transmission through the collaboration of multiple satellite nodes based on limited space-based computing resources has become an urgent problem that needs to be solved.
现有天基路由算法以数据通信为主，在数据传输过程中不考虑数据内容，不对数据进行业务处理，没有充分利用天基计算平台计算资源，传输数据量大、传输时延长。The existing space-based routing algorithms are mainly based on data communication. They do not consider the data content during data transmission, do not perform business processing on the data, do not fully utilize the computing resources of the space-based computing platform, and transmit large amounts of data and long transmission times.
发明内容Summary of the invention
本发明的技术解决问题是：克服现有技术的不足，提供了一种低时延业务天基计算方法，解决了传统方法业务计算时间长的问题，满足低时延业务的需求。The technical problem solved by the present invention is: to overcome the deficiencies of the prior art, to provide a low-latency service space-based calculation method, to solve the problem of long service calculation time in traditional methods, and to meet the needs of low-latency services.
本发明的技术解决方案是：The technical solution of the present invention is:
一种低时延业务天基计算方法，步骤如下：A low-latency space-based computing method, the steps are as follows:
1)设任务源节点卫星Ss的待传输处理任务为任务T(D，R)，其中D为任务T待处理的输入数据，R为任务T处理后的输出数据；将T分解为多个并行子任务，当T的各个子任务均完成时，则任务T完成；1) Assume that the task to be transmitted and processed by the task source node satelliteSs is task T(D, R), where D is the input data to be processed by task T, and R is the output data after processing by task T; decompose T into multiple parallel subtasks, and when all subtasks of T are completed, task T is completed;
2)低轨网络中每颗卫星周期性向高轨卫星上报自身的网络状态，高轨卫星周期性广播低轨卫星网络状态；2) Each satellite in the low-orbit network periodically reports its network status to the high-orbit satellite, and the high-orbit satellite periodically broadcasts the network status of the low-orbit satellite;
低轨网络每颗卫星具有轨内前后2条、轨间左右2条共4条星间链路，第i个卫星Si上报内容包括四条星间链路的可用带宽集合Bi Mbps以及当前自身可用计算资源Mflops；Bi＝{Bi,1,Bi,2,Bi,3,Bi,4}，其中Bi,1为第i个卫星Si的第一条星间链路的可用带宽，Bi,2为第i个卫星Si的第二条星间链路的可用带宽，Bi,3为第i个卫星Si的第三条星间链路的可用带宽，Bi,4为第i个卫星Si的第四条星间链路的可用带宽；Each satellite in the low-orbit network has four inter-satellite links, two in front and back of the orbit and two in the left and right of the orbit. The i-th satellite Si reports the available bandwidth set Bi Mbps of the four inter-satellite links and its current available computing resources. Mflops;Bi = {Bi,1 , Bi,2 , Bi,3 , Bi,4 }, where Bi,1 is the available bandwidth of the first intersatellite link of the i-th satellite Si ,Bi,2 is the available bandwidth of the second intersatellite link of the i-th satellite Si, Bi,3 is the available bandwidth of the third intersatellite link of the i-th satellite Si , and Bi,4 is the available bandwidth of the fourth intersatellite link of the i-th satellite Si ;
3)根据低轨卫星网络状态确定候选传输路径节点集合，根据步骤1)分解的子任务及子任务属性，对子任务进行排序，然后按排序在候选传输路径节点集合上对子任务进行编排，将子任务映射到对应的卫星节点上；3) Determine a candidate transmission path node set according to the low-orbit satellite network status, sort the subtasks according to the subtasks and subtask attributes decomposed in step 1), and then arrange the subtasks on the candidate transmission path node set according to the sorting, and map the subtasks to the corresponding satellite nodes;
4)根据编排结果，将子任务待处理的输入数据发送至相应卫星节点，卫星节点根据子任务计算要求加载处理程序，对接收的子任务数据进行处理并将处理结果发送至目标节点，处理结果设置为高优先级业务，通过预留带宽发送；4) According to the arrangement result, the input data to be processed by the subtask is sent to the corresponding satellite node. The satellite node loads the processing program according to the subtask calculation requirements, processes the received subtask data and sends the processing result to the target node. The processing result is set as a high-priority service and sent through the reserved bandwidth;
5)每个子任务正确执行后反馈给任务源节点，对于执行失败的任务，由任务源节点重新分配传输计算过程，直至计算结果正确，所有子任务正确执行后在目标节点汇聚，完成整个任务的传输计算。5) After each subtask is executed correctly, it is fed back to the task source node. For tasks that fail to execute, the task source node reallocates the transmission calculation process until the calculation result is correct. After all subtasks are executed correctly, they converge at the target node to complete the transmission calculation of the entire task.
所述步骤3)中，按照如下方法对子任务进行排序：In step 3), the subtasks are sorted as follows:
设第j个子任务的排序因子为λj，Assume the ranking factor of the j-th subtask is λj ,
取λj＝size(Dj)/size(Dmax)-ctask_j/cmax，其中Dj为第j个子任务待处理的输入数据，size(Dj)为第j个子任务待处理的输入数据大小，Dmax为子任务集合中待处理的输入数据大小最大的子任务对应的待处理输入数据，ctask_j为处理第j个子任务所需的计算量，cmax为子任务集合中所需计算量最大的子任务的计算量，λj为任务排序因子；Take λj =size(Dj )/size(Dmax )-ctask_j /cmax , where Dj is the input data to be processed by the j-th subtask, size(Dj ) is the size of the input data to be processed by the j-th subtask, Dmax is the input data to be processed corresponding to the subtask with the largest size of input data to be processed in the subtask set, ctask_j is the computational amount required to process the j-th subtask, cmax is the computational amount of the subtask with the largest computational amount in the subtask set, and λj is the task sorting factor;
按照排序因子从大到小对每个子任务排序。Sort each subtask by sorting factor from largest to smallest.
所述步骤3)中，确定候选传输路径节点集合的方法如下：In step 3), the method for determining the candidate transmission path node set is as follows:
将低轨卫星网络抽象为2维mesh网络，从任务源节点Ss到目标节点Sd的最少跳数路径集合中包含的所有节点构成候选传输路径节点集合，集合中节点总个数为L。The low-orbit satellite network is abstracted as a 2D mesh network. All nodes included in the minimum hop path set from the mission source nodeSs to the target nodeSd constitute the candidate transmission path node set, and the total number of nodes in the set is L.
设任务源节点Ss到目标节点Sd候选传输路径节点集合为S＝{Si}，低轨卫星网络抽象为2维mesh网络，在2维mesh网络拓扑中，记轨间链路为x轴方向，轨内链路为y轴方向；对某次通信，设任务源节点Ss坐标为(xs,ys)，目标节点Sd坐标为(xd,yd)；Suppose the set of candidate transmission path nodes from the task source node Ss to the target node Sd is S = {Si }, the low-orbit satellite network is abstracted as a 2D mesh network. In the 2D mesh network topology, the inter-orbit link is the x-axis direction, and the intra-orbit link is the y-axis direction. For a certain communication, the coordinates of the task source node Ss are (xs ,ys ), and the coordinates of the target node Sd are (xd ,yd );
则如果是没有反向缝的星座，任务源节点Ss、目标节点Sd两者间的x与y方向通信逻辑距离差为：If there is no reverse seam in the constellation, the communication logical distance difference between the task source node Ss and the target node Sd in the x and y directions is:
如果是有反向缝的星座，任务源节点Ss、目标节点Sd两者间的x与y方向通信逻辑距离差为：If the constellation has a reverse seam, the communication logical distance difference between the task source node Ss and the target node Sd in the x and y directions is:
其中N为轨道面数量，M为一个轨道面上的卫星数；Where N is the number of orbital planes, and M is the number of satellites on one orbital plane;
那么从Ss到Sd最多共有条最少跳数路径，其跳数距离为Δx+Δy；这些路径上节点构成的集合为候选传输路径节点集合，最少跳数路径集合构成候选传输路径集合。Then from Ss to Sd, there are at most The minimum hop paths have a hop distance of Δx+Δy; the set of nodes on these paths is the candidate transmission path node set, and the minimum hop path set constitutes the candidate transmission path set.
如果是没有反向缝的星座，最少跳数路径中x轴方向的路径为：If it is a constellation without a reverse seam, the path in the x-axis direction in the minimum hop path is:
(a)如果|xd-xs|≤N-|xd-xs|，则x轴方向的路径为：(a) If |xd -xs |≤N-|xd -xs |, then the path along the x-axis is:
当xs>xd时，xs→xs-1→xs-2→…→xd；Whenxs >xd ,xs →xs -1→xs -2→…→xd ;
当xs≤xd时，xs→xs+1→xs+2→…→xd；Whenxs≤xd ,xs →xs +1→xs +2→…→xd ;
(b)如果|xd-xs|>N-|xd-xs|，则x轴方向的路径为：(b) If |xd -xs |>N-|xd -xs |, then the path along the x-axis is:
当xs≤xd时，xs→xs-1→xs-2→…→1→N→…→xd；Whenxs≤xd ,xs →xs -1→xs- 2→…→1→N→…→xd ;
当xs>xd时，xs→xs+1→xs+2→…→N→1→…→xd。Whenxs >xd ,xs →xs +1→xs +2→…→N→1→…→xd .
否则如果是有反向缝的星座：Otherwise if it is a constellation with reverse seams:
当xs>xd时，xs→xs-1→xs-2→…→xd；Whenxs >xd ,xs →xs -1→xs -2→…→xd ;
当xs≤xd时，xs→xs+1→xs+2→…→xd。Whenxs≤xd ,xs →xs +1→xs +2→…→xd .
没有反向缝的星座和有反向缝的星座，在Y轴方向的路径相同，均为The paths of the constellations without and with reverse seams are the same in the Y-axis direction, both of which are
(a)如果|yd-ys|≤M-|yd-ys|，则y轴方向的路径为：(a) If |yd -ys |≤M-|yd -ys |, then the path along the y-axis is:
当ys>yd时，ys→ys-1→ys-2→…→yd；Whenys >yd ,ys →ys -1→ys -2→…→yd ;
当ys≤yd时，ys→ys+1→ys+2→…→yd；Whenys≤yd ,ys →ys +1→ys +2→…→yd ;
(b)如果|yd-ys|>M-|yd-ys|，则y轴方向的路径为：(b) If |yd -ys |>M-|yd -ys |, then the path along the y-axis is:
当ys≤yd时，ys→ys-1→ys-2→…→1→M→…→yd；Whenys≤yd ,ys →ys -1→ys -2→…→1→M→…→yd ;
当ys>yd时，ys→ys+1→ys+2→…→M→1→…→yd。Whenys >yd ,ys →ys +1→ys +2→…→M→1→…→yd .
所述步骤3)中，对子任务进行编排方法如下：In step 3), the method for arranging the subtasks is as follows:
对排序后的每一个子任务：For each sorted subtask:
针对候选传输路径节点集合中每一个卫星节点Sk，k＝1,...,L，k＝1时S1为源节点Ss，k＝L时SL为目标节点Sd，进行如下处理：For each satellite node Sk in the candidate transmission path node set, k=1,...,L, when k=1 S1 is the source node Ss , when k=L SL is the target node Sd , the following processing is performed:
为节点Sk分配给第j个子任务的计算资源大小，为节点Sk的可用计算资源大小； The size of computing resources allocated to the jth subtask by nodeSk , is the available computing resource size of nodeSk ;
为所有从源节点Ss到节点Sk的候选传输路径集合中的最大可用带宽，最大可用带宽由步骤2)中星间链路可用带宽确定，为从源节点Ss到节点Sk候选传输路径上分配第j个子任务的通信带宽，为将第j个子任务放置于节点Sk执行所能减小的时延，switch为源节点Ss到节点Sk传输路径上卫星节点数据交换的总时延，size(Dj)为第j个子任务待处理的输入数据大小，Task为所有子任务集合，ctask_j为处理第j个子任务所需的计算量； is the maximum available bandwidth in the set of candidate transmission paths from the source nodeSs to the nodeSk , and the maximum available bandwidth is determined by the available bandwidth of the intersatellite link in step 2). Assign the communication bandwidth of the jth subtask to the candidate transmission path from the source nodeSs to the nodeSk , is the delay that can be reduced by placing the jth subtask on the nodeSk for execution, switch is the total delay of satellite node data exchange on the transmission path from the source nodeSs to the nodeSk , size(Dj ) is the input data size to be processed by the jth subtask, Task is the set of all subtasks, andctask_j is the computational effort required to process the jth subtask;
如果则将第j个子任务安排到节点Sk上执行，并对系统状态做如下更新：if Then the jth subtask is scheduled to be executed on the nodeSk , and the system status is updated as follows:
Task＝Task-{子任务j}Task = Task - {subtask j}
对所有在节点Ss到节点Sk最大带宽路径上的节点Si：For all nodes Si on the maximum bandwidth path from nodeSsto nodeSk :
否则将第j个子任务安排到源节点自身执行，并对系统状态做如下更新：Otherwise, the jth subtask is scheduled to be executed on the source node itself, and the system status is updated as follows:
Task＝Task-{子任务j}Task = Task - {subtask j}
本发明与现有技术相比的有益效果是：The beneficial effects of the present invention compared with the prior art are:
(1)本发明结合路由及业务计算分配，将数据传输时延、任务计算时延、结果汇聚时延结合起来，全局考虑任务执行的时效性，缩短信息生成周期，降低业务整体时延。(1) The present invention combines routing and business calculation allocation, combines data transmission delay, task calculation delay, and result aggregation delay, globally considers the timeliness of task execution, shortens the information generation cycle, and reduces the overall business delay.
(2)本发明将低轨星座抽象为自组织mesh网络，结合分布式计算思路将卫星计算任务并行化、分布式化，以提升任务执行的时效性及容错性。(2) The present invention abstracts the low-orbit constellation into a self-organizing mesh network and combines distributed computing ideas to parallelize and distribute satellite computing tasks to improve the timeliness and fault tolerance of task execution.
(3)本发明联合考虑通信负载和计算负载，根据网络状态进行按需分配，可实现天基节点的负载均衡，提高计算效率和通信效率。(3) The present invention considers the communication load and the computing load together and distributes them on demand according to the network status, thereby achieving load balancing of space-based nodes and improving computing efficiency and communication efficiency.
附图说明BRIEF DESCRIPTION OF THE DRAWINGS
图1为本发明流程图；Fig. 1 is a flow chart of the present invention;
图2为本发明实施例场景图。FIG. 2 is a scene diagram of an embodiment of the present invention.
具体实施方式Detailed ways
下面结合附图对本发明的具体实施方式进行进一步的详细描述。The specific embodiments of the present invention are further described in detail below with reference to the accompanying drawings.
本发明提出一种低时延业务天基计算方法，根据流量负载、计算负载等情况，提出路由及计算策略，实时选择路径，能够适应网络流量变化和节点计算负载变化，自适应性强，通过充分利用天基计算及通信资源，实现信息从数据获取、信息提取到信息传输的低时延处理方法，解决低轨卫星计算平台低时延业务的高效处理传输问题。本发明方法能够提高星上通信、计算资源的使用效率，同时降低业务传输处理时延，满足低时延业务的服务质量要求。The present invention proposes a low-latency space-based computing method for services. According to the traffic load, computing load, etc., a routing and computing strategy is proposed, and a path is selected in real time. The method can adapt to changes in network traffic and node computing load, and has strong adaptability. By making full use of space-based computing and communication resources, a low-latency processing method for information from data acquisition, information extraction to information transmission is realized, and the problem of efficient processing and transmission of low-latency services of low-orbit satellite computing platforms is solved. The method of the present invention can improve the efficiency of on-board communication and computing resources, while reducing the service transmission processing delay, and meet the service quality requirements of low-latency services.
如图1所示，一种低时延业务天基计算方法，步骤如下：As shown in FIG1 , a low-latency service space-based calculation method includes the following steps:
11)任务分解11) Task decomposition
设卫星Ss的待传输处理任务为任务T(D，R)，D为任务T待处理的输入数据，R任务T的处理后输出数据。将T分解为并行子任务，共同完成任务T。当T的各个子任务均完成时，则任务T完成。Assume that the task to be transmitted and processed by satelliteSs is task T(D, R), D is the input data to be processed by task T, and R is the processed output data of task T. Decompose T into parallel subtasks to complete task T together. When all subtasks of T are completed, task T is completed.
12)为了实现路径获取和计算节点选择需要进行网络状态获取如下12) In order to achieve path acquisition and calculation node selection, the network status needs to be acquired as follows
低轨网络每颗卫星具有轨内前后2条、轨间左右2条共4条星间链路，低轨网络中所有卫星Si周期性向高轨卫星上报自身的网络负载，上报内容包括四条星间链路的可用带宽Bi＝{Bi,1,Bi,2,Bi,3,Bi,4}Mbps、当前自身可用计算能力CiMflops。Each satellite in the low-orbit network has four inter-satellite links, including two front and rear links within the orbit and two left and right links between the orbits. All satellitesSi in the low-orbit network periodically report their own network loads to the high-orbit satellites. The reported content includes the available bandwidth of the four inter-satellite linksBi = {Bi,1 , Bi,2 , Bi,3 , Bi,4 } Mbps and their current available computing powerCi Mflops.
高轨卫星周期性广播低轨卫星网络状态。High-orbit satellites periodically broadcast the network status of low-orbit satellites.
13)计算节点和传输路径选择方法如下13) The calculation node and transmission path selection method are as follows
根据2)获取的网络状态，和1)分解的子任务及子任务属性，首先对子任务进行排序，然后按顺序在候选传输路径上对任务进行编排，将子任务映射到对应的卫星节点上；According to the network status obtained in 2) and the subtasks and subtask attributes decomposed in 1), the subtasks are first sorted, and then the tasks are arranged in sequence on the candidate transmission paths, and the subtasks are mapped to the corresponding satellite nodes;
14)传输和计算14) Transmission and calculation
根据3)的编排结果，将子任务相应待处理任务数据发送至相应卫星节点，卫星节点根据子任务计算要求加载处理程序，对接收的子任务数据进行处理并将处理结果发送至目标节点。处理结果设置为高优先级业务，通过预留带宽发送。According to the arrangement result of 3), the task data to be processed corresponding to the subtask is sent to the corresponding satellite node. The satellite node loads the processing program according to the subtask calculation requirements, processes the received subtask data and sends the processing results to the target node. The processing results are set as high-priority services and sent through the reserved bandwidth.
15)子任务汇聚15) Subtask aggregation
每个子任务正确执行后反馈给任务源节点，对于执行失败的任务。由任务源节点重新分配传输计算过程，直至计算结果正确，所有子任务正确执行后在目标节点汇聚，完成整个任务的传输计算。After each subtask is correctly executed, it will be fed back to the task source node. For tasks that fail to execute, the task source node will redistribute the transmission calculation process until the calculation result is correct. After all subtasks are correctly executed, they will converge at the target node to complete the transmission calculation of the entire task.
2.步骤1中13)所述的排序方法如下：2. The sorting method described in step 13) is as follows:
设第j个子任务的排序因子为λj，Assume the ranking factor of the j-th subtask is λj ,
取λj＝size(Dj)/size(Dmax)-ctask_j/cmax，其中Dj为任务j的待处理数据，size(Dj)为数据大小，size(Dmax)为输入数据大小最大的子任务对应的待处理输入数据大小，ctask_j为处理任务j所需的计算量，cmax为所需计算量最大的子任务的计算量。Take λj =size(Dj )/size(Dmax )-ctask — j /cmax , where Dj is the data to be processed of task j, size(Dj ) is the data size, size(Dmax ) is the size of the input data to be processed corresponding to the subtask with the largest input data size, ctask — j is the computational amount required to process task j, and cmax is the computational amount of the subtask with the largest computational amount.
按照排序因子从大到小对每个子任务排序。Sort each subtask by sorting factor from largest to smallest.
3.候选传输路径节点集合的获取方法为：3. The method for obtaining the candidate transmission path node set is:
将低轨卫星网络抽象为2维mesh网络，从任务源节点Ss到目标节点Sd的最少跳数路径集合中包含的所有节点构成候选传输路径节点集合，集合中节点总个数为L。The low-orbit satellite network is abstracted as a 2D mesh network. All nodes included in the minimum hop path set from the mission source nodeSs to the target nodeSd constitute the candidate transmission path node set, and the total number of nodes in the set is L.
设源节点Ss到目标节点Sd最少跳数路径范围内的所有节点集合为S＝{Si}，低轨卫星网络可以抽象为到2维mesh网络，在2维mesh网络拓扑中，记轨间链路为x轴方向，轨内为y轴方向。对某次通信，数据通信源节点为Ss(xs,ys)，目的节点为Sd(xd,yd)，则如果是没有反向缝的星座，任务源节点Ss、目标节点Sd两者间的x与y方向通信逻辑距离差为：Assume that the set of all nodes within the minimum hop path from source nodeSs to target nodeSd is S={Si }. The low-orbit satellite network can be abstracted into a 2D mesh network. In the 2D mesh network topology, the inter-track link is the x-axis direction and the intra-track link is the y-axis direction. For a certain communication, the data communication source node isSs (xs ,ys ) and the destination node isSd (xd ,yd ). If it is a constellation without a reverse seam, the difference in the x- and y-direction communication logical distances between the task source nodeSs and the target nodeSd is:
如果是有反向缝的星座，任务源节点Ss、目标节点Sd两者间的x与y方向通信逻辑距离差为：If the constellation has a reverse seam, the communication logical distance difference between the task source node Ss and the target node Sd in the x and y directions is:
其中N为轨道面数量，M为一个轨道面上的卫星数；Where N is the number of orbital planes, and M is the number of satellites on one orbital plane;
那么从Ss到Sd最多共有条最少跳数路径，其跳数距离为Δx+Δy；这些路径上节点构成的集合为候选传输路径节点集合，最少跳数路径集合构成候选传输路径集合。Then from Ss to Sd, there are at most The minimum hop paths have a hop distance of Δx+Δy; the set of nodes on these paths is the candidate transmission path node set, and the minimum hop path set constitutes the candidate transmission path set.
如果是没有反向缝的星座，最少跳数路径中x轴方向的路径为：If it is a constellation without a reverse seam, the path in the x-axis direction in the minimum hop path is:
(a)如果|xd-xs|≤N-|xd-xs|，则x轴方向的路径为：(a) If |xd -xs |≤N-|xd -xs |, then the path along the x-axis is:
当xs>xd时，xs→xs-1→xs-2→…→xd；Whenxs >xd ,xs →xs -1→xs -2→…→xd ;
当xs≤xd时，xs→xs+1→xs+2→…→xd；Whenxs≤xd ,xs →xs +1→xs +2→…→xd ;
(b)如果|xd-xs|>N-|xd-xs|，则x轴方向的路径为：(b) If |xd -xs |>N-|xd -xs |, then the path along the x-axis is:
当xs≤xd时，xs→xs-1→xs-2→…→1→N→…→xd；Whenxs≤xd ,xs →xs -1→xs- 2→…→1→N→…→xd ;
当xs>xd时，xs→xs+1→xs+2→…→N→1→…→xd。Whenxs >xd ,xs →xs +1→xs +2→…→N→1→…→xd .
否则如果是有反向缝的星座：Otherwise if it is a constellation with reverse seams:
当xs>xd时，xs→xs-1→xs-2→…→xd；Whenxs >xd ,xs →xs -1→xs -2→…→xd ;
当xs≤xd时，xs→xs+1→xs+2→…→xd。Whenxs≤xd ,xs →xs +1→xs +2→…→xd .
没有反向缝的星座和有反向缝的星座，在Y轴方向的路径相同，均为The paths of the constellations without and with reverse seams are the same in the Y-axis direction, both of which are
(a)如果|yd-ys|≤M-|yd-ys|，则y轴方向的路径为：(a) If |yd -ys |≤M-|yd -ys |, then the path along the y-axis is:
当ys>yd时，ys→ys-1→ys-2→…→yd；Whenys >yd ,ys →ys -1→ys -2→…→yd ;
当ys≤yd时，ys→ys+1→ys+2→…→yd；Whenys≤yd ,ys →ys +1→ys +2→…→yd ;
(b)如果|yd-ys|>M-|yd-ys|，则y轴方向的路径为：(b) If |yd -ys |>M-|yd -ys |, then the path along the y-axis is:
当ys≤yd时，ys→ys-1→ys-2→…→1→M→…→yd；Whenys≤yd ,ys →ys -1→ys -2→…→1→M→…→yd ;
当ys>yd时，ys→ys+1→ys+2→…→M→1→…→yd。Whenys >yd ,ys →ys +1→ys +2→…→M→1→…→yd .
4.对排序后的每一个子任务：4. For each sorted subtask:
针对候选传输路径节点集合中每一个卫星节点Sk(k＝1,...,L),k＝1,...,L，k＝1时S1为源节点Ss，k＝L时SL为目标节点Sd，进行如下处理：For each satellite node Sk (k=1,...,L) in the candidate transmission path node set, k=1,...,L, when k=1 S1 is the source node Ss , when k=L SL is the target node Sd , the following processing is performed:
为节点Sk分配给第j个子任务的计算资源大小，为节点Sk的可用计算资源大小； The size of computing resources allocated to the jth subtask by nodeSk , is the available computing resource size of nodeSk ;
为所有从源节点Ss到节点Sk的候选传输路径集合中的最大可用带宽，最大可用带宽由步骤12)中星间链路可用带宽确定，为从源节点Ss到节点Sk候选传输路径上分配第j个子任务的通信带宽，为将第j个子任务放置于节点Sk执行所能减小的时延，switch为源节点Ss到节点Sk传输路径上卫星节点数据交换的总时延，size(Dj)为第j个子任务待处理的输入数据大小，Task为所有子任务集合，ctask_j为处理第j个子任务所需的计算量； is the maximum available bandwidth in the set of candidate transmission paths from the source nodeSs to the nodeSk , the maximum available bandwidth is determined by the available bandwidth of the intersatellite link in step 12), Assign the communication bandwidth of the jth subtask to the candidate transmission path from the source nodeSs to the nodeSk , is the delay that can be reduced by placing the jth subtask on the nodeSk for execution, switch is the total delay of satellite node data exchange on the transmission path from the source nodeSs to the nodeSk , size(Dj ) is the input data size to be processed by the jth subtask, Task is the set of all subtasks, andctask_j is the computational effort required to process the jth subtask;
如果则将第j个子任务安排到节点Sk上执行，并对系统状态做如下更新：if Then the jth subtask is scheduled to be executed on the nodeSk , and the system status is updated as follows:
Task＝Task-{子任务j}Task = Task - {subtask j}
对所有在节点Ss到节点Sk最大带宽路径上的节点Si：For all nodes Si on the maximum bandwidth path from nodeSsto nodeSk :
否则将第j个子任务安排到源节点自身执行，并对系统状态做如下更新：Otherwise, the jth subtask is scheduled to be executed on the source node itself, and the system status is updated as follows:
Task＝Task-{子任务j}Task = Task - {subtask j}
重复子任务处理过程，直至所有子任务编排完毕。Repeat the subtask processing process until all subtasks are arranged.
实施例场景如图2所示，其为星座中的一部分，整个星座包括24个轨道面，每个轨道面24颗卫星。其中卫星51611产生数据，经过处理后的数据，通过卫星51712发送到其下属节点。The embodiment scenario is shown in FIG2 , which is a part of a constellation. The entire constellation includes 24 orbital planes, each with 24 satellites. Satellite 51611 generates data, and the processed data is sent to its subordinate nodes via satellite 51712 .
低时延业务天基计算方法步骤如下：The steps of the low-latency space-based calculation method are as follows:
11)任务分解11) Task decomposition
卫星51611的待传输处理任务T为遥感图像中目标识别，输入数据D为2000*10000*8bit的遥感数据。将T分解为2个子任务{Ta1，Ta2}，共同完成任务T。每个子任务的数据量都为2000*5000*8bit＝80Mbit，每个子任务处理所需计算量为100Gflops。当T的各个子任务均完成时，则任务T完成。The task T to be transmitted and processed by satellite 51611 is target recognition in remote sensing images, and the input data D is 2000*10000*8bit remote sensing data. Decompose T into 2 subtasks {Ta1 , Ta2 }, and complete task T together. The data volume of each subtask is 2000*5000*8bit＝80Mbit, and the computing power required for processing each subtask is 100Gflops. When all subtasks of T are completed, task T is completed.
12)为了实现路径获取和计算节点选择需要进行网络状态获取如下12) In order to achieve path acquisition and calculation node selection, the network status needs to be acquired as follows
低轨网络中所有卫星Si周期性向高轨卫星上报自身的网络负载，上报内容包括四条星间链路的可用带宽Bi＝{Bi,1,Bi,2,Bi,3,Bi,4}Mbps、当前自身可用计算能力CiMflops。All satellitesSi in the low-orbit network periodically report their own network load to the high-orbit satellite. The reported content includes the available bandwidth of the four inter-satellite linksBi = {Bi,1 , Bi,2 , Bi,3 , Bi,4 } Mbps and the current available computing powerCi Mflops.
高轨卫星周期性广播低轨卫星网络状态。High-orbit satellites periodically broadcast the network status of low-orbit satellites.
各卫星当前的计算能力及通信能力如表1、表2所示。The current computing and communication capabilities of each satellite are shown in Tables 1 and 2.
表1卫星节点计算能力CTable 1 Satellite node computing capacity C
表2卫星间可用带宽BTable 2 Available bandwidth B between satellites
13)计算节点和传输路径选择方法如下13) The calculation node and transmission path selection method are as follows
根据2)获取的网络状态，和1)分解的子任务及子任务需求，首先对子任务进行排序，然后按排序在候选传输路径上对任务进行编排，将子任务映射到对应的卫星节点上；According to the network status obtained in 2) and the subtasks and subtask requirements decomposed in 1), the subtasks are first sorted, and then the tasks are arranged on the candidate transmission paths according to the sorting, and the subtasks are mapped to the corresponding satellite nodes;
14)传输和计算14) Transmission and calculation
根据3)的编排结果，将子任务相应待处理任务数据发送至相应卫星节点，卫星节点根据子任务计算要求加载处理程序，对接收的子任务数据进行处理并将处理结果发送至目标节点。处理结果设置为高优先级业务，通过预留带宽发送。According to the arrangement result of 3), the task data to be processed corresponding to the subtask is sent to the corresponding satellite node. The satellite node loads the processing program according to the subtask calculation requirements, processes the received subtask data and sends the processing results to the target node. The processing results are set as high-priority services and sent through the reserved bandwidth.
15)子任务汇聚15) Subtask aggregation
每个子任务正确执行后反馈给任务源节点，对于执行失败的任务。由任务源节点重新分配传输计算过程，直至计算结果正确，所有子任务正确执行后在目标节点汇聚，完成整个任务的传输计算。After each subtask is correctly executed, it will be fed back to the task source node. For tasks that fail to execute, the task source node will redistribute the transmission calculation process until the calculation result is correct. After all subtasks are correctly executed, they will converge at the target node to complete the transmission calculation of the entire task.
2.步骤1中13)所述的排序方法结果如下：2. The results of the sorting method described in step 13) are as follows:
本实例中λ1＝λ2，即排序为{Ta1，Ta2}。In this example, λ1 =λ2 , that is, the order is {Ta1 , Ta2 }.
3.根据本发明方法，候选传输路径节点集合为{Satellite51611、Satellite51612、Satellite51613、Satellite51710、Satellite51711、Satellite51712}，3. According to the method of the present invention, the candidate transmission path node set is {Satellite51611, Satellite51612, Satellite51613, Satellite51710, Satellite51711, Satellite51712},
候选传输路径为：The candidate transmission paths are:
本实例中为卫星51611到卫星51712的条最短路径，跳数为3:In this example, it is from satellite 51611 to satellite 51712 The shortest path with 3 hops is:
Satellite51611->Satellite51612->Satellite51613->Satellite51712,Satellite51611->Satellite51612->Satellite51613->Satellite51712,
Satellite51611->Satellite51612->Satellite51711->Satellite51712Satellite51611->Satellite51612->Satellite51711->Satellite51712
Satellite51611->Satellite51710->Satellite51711->Satellite51712Satellite51611->Satellite51710->Satellite51711->Satellite51712
4.根据本发明步骤1所述的编排方法所得如下：4. The following is obtained according to the arrangement method described in step 1 of the present invention:
考虑到传播时延为ms量级，而计算和传输时延为秒级，因此在此实施例中忽略传播时延。Considering that the propagation delay is in the order of ms, while the calculation and transmission delays are in the order of seconds, the propagation delay is ignored in this embodiment.
Satellite51611将子任务Ta1分配给各个节点上，计算出的Δt如表3所示，分别为Satellite51611 assigns subtask Ta1 to each node, and the calculated Δt is shown in Table 3.
表3任务1时延Table 3 Task 1 delay
因为所以将子任务Ta1安排至节点Satellite51612进行计算。更新信息为：because Therefore, subtask Ta1 is scheduled to node Satellite51612 for calculation. The updated information is:
表4卫星节点计算能力Table 4 Satellite node computing capabilities
表5卫星间可用带宽及传播时延Table 5 Available bandwidth and propagation delay between satellites
Satellite51611将子任务Ta2分配给各个节点上，计算出的Δt分别为Satellite51611 assigns subtask Ta2 to each node, and the calculated Δt is
表6任务2时延Table 6 Task 2 delay
因为故此子任务Ta2被分配至卫星Satellite51711上。because Therefore, subtask Ta2 was assigned to satellite Satellite51711.
本发明获得的任务执行总时延为max{100/5+80/21，100/5.5+50/12}＝23.810秒。The total task execution delay obtained by the present invention is max{100/5+80/21, 100/5.5+50/12}=23.810 seconds.
上述实施例说明本发明相比传统计算通信独立处理方式能够有效降低业务时延。The above embodiments illustrate that the present invention can effectively reduce service delays compared to the traditional independent processing method of computing and communicating.
本发明说明书中未作详细描述的内容属于本领域专业技术人员的公知技术。The contents not described in detail in the specification of the present invention belong to the common knowledge of professionals in the field.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110987485.8ACN113938176B (en) | 2021-08-26 | 2021-08-26 | Low-delay service space-based calculation method |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202110987485.8ACN113938176B (en) | 2021-08-26 | 2021-08-26 | Low-delay service space-based calculation method |
| Publication Number | Publication Date |
|---|---|
| CN113938176A CN113938176A (en) | 2022-01-14 |
| CN113938176Btrue CN113938176B (en) | 2024-07-12 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202110987485.8AActiveCN113938176B (en) | 2021-08-26 | 2021-08-26 | Low-delay service space-based calculation method |
| Country | Link |
|---|---|
| CN (1) | CN113938176B (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN117707793B (en)* | 2024-02-05 | 2024-05-03 | 太平金融科技服务（上海）有限公司 | Computing task processing method, device, equipment and medium |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6366761B1 (en)* | 1998-10-06 | 2002-04-02 | Teledesic Llc | Priority-based bandwidth allocation and bandwidth-on-demand in a low-earth-orbit satellite data communication network |
| US7382765B2 (en)* | 2003-04-30 | 2008-06-03 | Harris Corporation | Predictive routing in a moble ad hoc network |
| US9444721B2 (en)* | 2013-09-30 | 2016-09-13 | Juniper Networks, Inc. | Two-part metric for link state routing protocols |
| BR112016022491A2 (en)* | 2014-03-31 | 2017-08-15 | Intelsat Corp | METHOD FOR RELEASE OF CONTENT, AND, APPLIANCE |
| US10833756B2 (en)* | 2015-12-14 | 2020-11-10 | Higher Ground Llc | Satellite communication for the Internet of Things |
| US10666352B2 (en)* | 2016-08-30 | 2020-05-26 | Worldvu Satellites Limited | Satellite system comprising satellites in LEO and other orbits |
| CN106385387B (en)* | 2016-09-27 | 2019-08-02 | 中国科学院空间应用工程与技术中心 | A kind of resource regulating method, system and the application of Information Network link |
| US10749841B2 (en)* | 2017-04-10 | 2020-08-18 | At&T Intellectual Property I, L.P. | Border gateway protocol multipath scaled network address translation system |
| CN107733518A (en)* | 2017-09-30 | 2018-02-23 | 南京理工大学 | The optimal income method for routing of LEO satellite network based on cooperative game |
| IL255043B (en)* | 2017-10-16 | 2019-05-30 | Oscar Glottmann | Ad hoc network routing |
| CN108307435B (en)* | 2018-01-29 | 2021-02-19 | 大连大学 | A Multitask Routing Method Based on SDSIN |
| CN108650010A (en)* | 2018-03-26 | 2018-10-12 | 西南电子技术研究所（中国电子科技集团公司第十研究所） | Intelligent monitoring communications network system |
| CN109818669B (en)* | 2019-01-18 | 2021-04-27 | 中国科学院空间应用工程与技术中心 | Virtualization-based satellite service processing method, system and storage medium |
| CN109936619B (en)* | 2019-01-18 | 2021-07-20 | 中国科学院空间应用工程与技术中心 | A spatial information network architecture, method and readable storage medium based on fog computing |
| US11017773B2 (en)* | 2019-07-09 | 2021-05-25 | Bank Of America Corporation | Voice-based time-sensitive task processing over a high generation cellular network |
| CN111934916B (en)* | 2020-07-23 | 2023-05-09 | 中国科学院空间应用工程与技术中心 | A network scheduling method and system based on mixed service transmission |
| CN112260743B (en)* | 2020-09-16 | 2022-08-12 | 西安空间无线电技术研究所 | A computing resource allocation method and device |
| CN112311441B (en)* | 2020-09-30 | 2022-09-27 | 中国人民解放军陆军工程大学 | Congestion Avoidance Routing Methods in Low Orbit Constellation Networks |
| CN112187342B (en)* | 2020-09-30 | 2021-10-01 | 西安交通大学 | A satellite traffic routing method and system based on energy sensing and load balancing |
| CN112737665B (en)* | 2020-12-25 | 2022-05-31 | 中国人民解放军国防科技大学 | Routing resource control method suitable for double-layer satellite optical network data relay system |
| CN112799784B (en)* | 2021-02-01 | 2024-04-26 | 军事科学院系统工程研究院系统总体研究所 | Low-orbit satellite network optimal task allocation method based on decentralized computing |
| CN113067625B (en)* | 2021-03-17 | 2022-03-04 | 西安电子科技大学 | Satellite network multi-service QoS routing method based on region division |
| CN112953625B (en)* | 2021-04-26 | 2022-12-27 | 南京大学 | Super-large-scale low-orbit satellite network operation and maintenance and resource control method |
| Publication number | Publication date |
|---|---|
| CN113938176A (en) | 2022-01-14 |
| Publication | Publication Date | Title |
|---|---|---|
| Zhang et al. | Aerial edge computing on orbit: A task offloading and allocation scheme | |
| Zhai et al. | FedLEO: An offloading-assisted decentralized federated learning framework for low earth orbit satellite networks | |
| Qu et al. | Elastic collaborative edge intelligence for UAV swarm: Architecture, challenges, and opportunities | |
| CN114819702B (en) | Remote sensing constellation task management and control system based on multiple agents | |
| CN108337710B (en) | Method and system based on high-low orbit satellite communication | |
| CN108259078B (en) | Resource allocation method and system for on-satellite integrated electronic system | |
| CN118157740A (en) | A satellite-borne edge cloud task scheduling method and system | |
| CN113938176B (en) | Low-delay service space-based calculation method | |
| Zhang et al. | Urban internet of electric vehicle parking system for vehicle-to-grid scheduling: Formulation and distributed algorithm | |
| CN118283124B (en) | Hierarchical resource scheduling method for cross-domain measurement and control network | |
| CN107454148B (en) | Tactical edge-oriented mobile cloud control system | |
| CN115001971A (en) | Virtual network mapping method for improving community discovery under heaven-earth integrated information network | |
| CN115049225A (en) | Multitask-oriented constellation time window collaborative planning utilization system and method | |
| Zhang et al. | A service function chain mapping scheme based on functional aggregation in space-air-ground integrated networks | |
| CN114500579B (en) | A subscription-publishing autonomous service discovery and collaboration method for space-based computing | |
| CN114422455B (en) | Multidimensional resource management architecture and method based on space-air-ground integrated network | |
| Elmahallawy et al. | Stitching satellites to the edge: Pervasive and efficient federated leo satellite learning | |
| CN115551014A (en) | Task unloading scheduling method in air-ground cooperative unmanned aerial vehicle edge computing network | |
| CN113220425B (en) | A Distributed Reconfigurable Satellite System Organization Method Based on Mosaic Splicing | |
| Huang et al. | A survey on task partitioning and scheduling for vehicular edge computing | |
| CN118523828A (en) | Star grouping method, device, equipment, medium and program product | |
| CN117650831A (en) | Edge computing and unloading method, system, chip and equipment for large-scale satellite constellation | |
| CN118473498A (en) | A satellite computing network and control method based on task scheduling | |
| Lai et al. | A UAV-enabled mobile edge computing paradigm for dependent tasks based on a computing power pool | |
| CN116582173A (en) | Method, device and storage medium for processing data by satellite-based distributed network |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |