CN102892146B - Outbound wave beam scheduling processing method - Google Patents

Abstract

The present invention relates to an outbound beam scheduling processing method, comprising: when arranging an outbound beam for an outbound communication service, if it is detected that the outbound beam capable of receiving the outbound communication service receives the outbound communication service , the outbound beams in the system will have unbalanced load, then the step-by-step optimization method is used to schedule the outbound beams; the step-by-step optimization method includes the outbound The communication service is arranged into other corresponding redundant outbound beams in the system according to the shortest queue method, and the outbound communication service is arranged into the outbound beam. This method optimizes the load balancing problem of outbound beams to a certain extent.

Description

Outbound Beam Scheduling Processing Method

technical field

The invention relates to the field of satellite communication, in particular to an outbound beam scheduling processing method.

Background technique

Satellite microwave communication usually uses transponders to provide information forwarding services, and each satellite usually contains multiple transponders, each transponder corresponds to a beam, and each beam corresponds to a target user service area covering a certain area. During satellite communication, when the central station receives a communication service request from one user to another user, the communication service request is calculated by the central station and can be sent to more than one beam of the target user. At this time, the service areas of these beams will be There is some overlap, and there will also be a certain overlap between the beams corresponding to the multiple transponders of multiple satellites. These overlaps constitute the overlap of the beam service area, that is, there are more than one beams that can receive communication service requests. . We call the set of all beams that can receive the same communication service request a redundant beam, and the process of sending the communication service request to the target user through the beam is called the outbound service of the traffic service, and the beam is called outbound beam. When multiple satellites are in an information forwarding system, the beam selection problem will arise when the information is forwarded by the central station. Theoretically, any beam that covers the target user can be used as an outbound beam. However, under the condition of redundant beams, the redundant beam information of each user is different. How to choose a reasonable beam for each user according to the current user communication service request? The outbound beam of , then becomes a combinatorial optimization problem.

Currently, the prior art solution to this combinatorial optimization is to use the shortest queue method. The so-called shortest queue method is that when arranging an outbound communication service, the communication service is placed on the beam with the shortest queue among the outbound beams that can receive the communication service. But when the shortest queue method is used to arrange the outbound, it is very likely that the load will be unbalanced. Figure 1 is an example diagram in the prior art when the outbound beam load is unbalanced, as shown in Figure 1, the queue lengths of beam 1 and beam 3 are both 4, and the queue length of beam 2 is only 1, in this case There is a serious load unbalanced situation; Figure 2 is an example of the ideal situation of outbound beam load balancing on the basis of Figure 1. As shown in Figure 2, the queue lengths of beams 1, 2, and 3 are all 3. An ideal load balance is achieved. Below we give an example to illustrate the load imbalance when using the shortest queue method to schedule outbound beams. Fig. 3 is an example diagram after the outbound beams are scheduled using the shortest queue method in the prior art; as shown in Fig. 3, when the first 8 communication services arrange outbound beams according to the shortest queue method, the load between each beam Balanced, but when the 9th communication service appears, assuming that the outbound beams that the 9th communication service can receive are 2 or 3, at this time, the queue lengths of beam 2 and beam 3 are both 2, regardless of which Which of the two beams is outbound will cause beam load imbalance, because the queue length of beam 4 and beam 5 is only 1 at this time.

It can be seen that the shortest queue method only considers the shortest queue of outbound beams that can be received by the current communication service, and the shortest outbound beam is often not the shortest queue in the entire outbound beam. Therefore, this analysis and consideration It is obviously partial, and the outbound beam load will still be unbalanced, resulting in poor efficiency of the shortest queue method for load balancing optimization.

Contents of the invention

Aiming at the above defects in the prior art, an outbound beam scheduling processing method is provided, which optimizes the load balancing problem of outbound beams to a certain extent.

The outbound beam scheduling processing method provided by the embodiment of the present invention includes:

When arranging outbound beams for outbound communication services, if it is detected that if the outbound beams capable of receiving the outbound communication services receive the outbound communication services, load imbalance will occur among the outbound beams in the system , the step-by-step optimization method is used to schedule outbound beams;

The step-by-step optimization method includes arranging the outbound communication service that has been arranged in the outbound beam into other corresponding redundant outbound beams in the system according to the shortest queue method, and arranging the outbound communication service into the outbound beam.

The outbound beam scheduling processing method provided by the embodiment of the present invention reduces the difference between the queue lengths of the global outbound beams by adopting the step-by-step optimization method, so that the system can schedule more outbound communication services in the same time. station, which optimizes the load balancing problem of outbound beams to a certain extent.

Description of drawings

FIG. 1 is an example diagram in the prior art when the outbound beam load is unbalanced;

Fig. 2 is an example diagram in the ideal case of realizing outbound beam load balancing on the basis of Fig. 1;

FIG. 3 is an example diagram of scheduling outbound beams using the shortest queue method in the prior art;

FIG. 4 is an example diagram after scheduling outbound beams using a step-by-step optimization method on the basis of FIG. 3;

Fig. 5 is an example diagram after adding two outbound communication services on the basis of Fig. 4;

Fig. 6 is an example diagram after scheduling outbound beams using the genetic simulated annealing optimization method on the basis of Fig. 5;

FIG. 7 is a flow chart of an embodiment of the present invention using a step-by-step optimization method to schedule outbound beams;

FIG. 8 is a flowchart of an embodiment of scheduling outbound beams by using the genetic simulated annealing optimization method in the present invention.

Detailed ways

The failure of the shortest queue method is because only the local shortest outbound beam queue is considered. If the consideration of the length of all global queues can be added to the algorithm, the effect of load balancing optimization will be greatly improved. The idea of the step-by-step tuning method is that when selecting an outbound beam for an outbound communication service, if the queues of outbound beams that can receive this outbound communication service are very long, adding this outbound communication service will cause load unbalanced, first examine the outbound communication services that have been queued on these outbound beams, select the outbound communication services that can join the global shortest queue and adjust them to the global shortest outbound beam, and then transfer the current outbound communication service Communication services are placed into adjusted outbound beams.

Fig. 7 is a flowchart of an embodiment of the present invention using a step-by-step optimization method to schedule outbound beams. As shown in Fig. 7, the specific steps of using the step-by-step optimization method in the embodiment of the present invention include:

Step 101: When arranging outbound beams for outbound communication services, determine whether each outbound beam in the system will be loaded if the outbound beams capable of receiving the outbound communication services receive the outbound communication services unbalanced; if load imbalance occurs, execute step 102; if load imbalance does not occur, execute step 103.

Specifically, when a new outbound communication service is received, it is necessary to arrange an outbound beam for the outbound communication service to send it out. In order to ensure the load balance of each outbound beam in the entire system, first check whether the outbound beams in the system have load imbalance when the outbound beam that can receive the outbound communication service receives the outbound communication service situation to make a judgment.

Step 102: arrange the outbound communication service that has been arranged in the outbound beam into other corresponding redundant outbound beams in the system according to the shortest queue method, and arrange the outbound communication service in the outbound in the beam.

If it is determined that the load is unbalanced, the embodiment of the present invention uses a step-by-step optimization method to schedule outbound beams, so that the load is as balanced as possible. The step-by-step optimization method is specifically: arrange the outbound communication services that have been originally arranged in the outbound beams to other corresponding redundant outbound beams in the system according to the shortest queue method, and then arrange the outbound communication services in the system Outbound communication services are arranged in the outbound beams, so that the outbound communication service queues in the outbound beams do not increase, and the load is borne by other outbound beams in the overall system, and balance is ensured.

Step 103: When the outbound condition is reached, outbound processing is performed on the outbound communication services of each outbound beam type.

Specifically, when the outbound condition is met, all outbound traffic services arranged on the outbound beams are subjected to outbound processing.

The step-by-step optimization method adopted in the embodiment of the present invention takes into account the factor of the global queue length, and schedules the global outbound communication service to a certain extent, so that the load of the outbound beam is balanced and optimized to a certain extent.

When the shortest queue method is used to schedule the outbound communication service in Figure 3, the load imbalance will occur, and in order to achieve load balance of the outbound beam, the step-by-step optimization method can be used to schedule the outbound communication service in Figure 3 Scheduling of outbound communication services; Figure 4 is an example diagram of scheduling outbound beams using the step-by-step optimization method on the basis of Figure 3. As shown in Figure 4, an original outbound communication service on beam 2 The service (the outbound beam that can be received by the outbound communication service is 2 or 4 or 5) is scheduled to beam 4, and then the outbound communication service that is about to enter the station (the outbound beam that the outbound communication service can be received The station beam is 2 or 3) into the outbound beam 2, so that the queue length of the beam 2 does not increase, so, to a certain extent, the state of load balancing is achieved.

However, although the step-by-step tuning method considers the factor of the global outbound beam queue length, it has greatly improved compared with the shortest queue method, but the global consideration of the step-by-step tuning method is single-step, and its adjustment still has limitations However, it is still difficult to deal with more complex load balancing problems. For example, accompanying drawing 5 is an example diagram when two outbound communication services are added on the basis of accompanying drawing 4. As shown in FIG. At this time, there is no outbound communication service that can be adjusted to the current global shortest queue (the queue of beam 5) in the queues of beam 2 and beam 3, so the load imbalance will occur.

For this reason, the embodiment of the present invention further provides a genetic simulated annealing optimization method for outbound load balance optimization. The basic idea of the algorithm is to generate and maintain a certain scale of outbound scheduling scheme groups, and then through repeated annealing, cross-mutation and elimination processes, a better outbound scheduling scheme is finally obtained.

After the scheduling process is performed according to the step-by-step optimization method, the outbound beam scheduling process is performed according to the genetic simulated annealing optimization method, and accompanying drawing 8 is a diagram of an embodiment of the present invention that uses the genetic simulated annealing optimization method to schedule outbound beams Flow chart, as described in Figure 8, the method includes the following steps:

Step 201: Use the outbound scheduling scheme obtained according to the step-by-step optimization method as an initial individual.

Specifically, a step-by-step optimization method is used to obtain an outbound scheduling scheme including all current outbound communication services, and this scheme is regarded as an initial individual.

Step 202: Based on the initial individual, randomly exchange 10 outbound communication services to the corresponding redundant outbound beams according to the redundant beam information of all the outbound beams in the system, and obtain the corresponding new individual; repeat Execute 29 times to obtain 29 new individuals; use the initial individual and the 29 new individuals as the first group.

Specifically, starting from the initial individual, randomly select 10 outbound communication services from the initial individual, and then schedule these 10 outbound communication services to other redundant outbound beams according to their redundant beam information, so A new individual is generated, and this action is repeated 29 times to obtain 29 such new individuals. The queue length of these 29 new individuals has changed, and they no longer have the equilibrium state held by the step-by-step tuning method , which together with the initial individuals constitute an initial population of size 30;

Step 203: annealing processing: the annealing processing includes scheduling outbound beams for each individual in the first group by using the stepwise optimization method.

Specifically, the 30 individuals in the group are optimized using the step-by-step optimization method, so that the longest queue length of the outbound beam is reduced.

Step 204: Cross-mutation processing: The cross-mutation processing includes, based on each individual generated after annealing in the first population, arbitrarily exchanging 10 beams according to the redundant beam information of all outbound beams in the system The outbound service is sent to the corresponding redundant outbound beam, and corresponding 30 new individuals are obtained to form a second group; the first group and the second group are taken together as a third group.

Specifically, for the annealed 30 individuals in the group, randomly select 10 outbound communication services from each individual, and exchange these 10 outbound communication services to other redundant beam information according to their respective redundant beam information. On the outbound beam, another 30 new individuals are generated in this way, and these other 30 new individuals are added to the current group, so that the size of the group expands to 60.

Step 205: Elimination processing: the elimination processing includes selecting the best 20 individuals from the third group, and then randomly selecting 10 individuals from the remaining individuals as the new first group; annealing treatment, the cross-mutation treatment and the elimination treatment.

Specifically, select the best 20 individuals from a group with a size of 60, and randomly select 10 different individuals from the remaining 40 individuals, and form these 30 individuals into a new first group, so that the size of the group Maintain at 30; repeatedly execute steps 203-205.

In the elimination operation, in addition to selecting the best 20 individuals from the group, another 10 different individuals are randomly selected in order to avoid the situation that the optimization cannot be continued when encountering a local optimal dilemma. The so-called local optimal dilemma means that if all the optimal solutions in the current group point to a certain local optimal area, then when continuing to explore outward from this local optimal area, it may not be possible to find a better path, and the local optimal The optimal area cannot meet the load balancing requirements of the algorithm, and the algorithm will fall into a local optimum dilemma. Randomly selecting 10 different individuals to join the current group can provide 10 different paths outside the optimal solution of the current group, and it is very likely to help the algorithm get out of the local optimal dilemma.

Step 206: Until the difference between the queue lengths of the largest and smallest outbound beams in an individual in the group is less than a preset value, or the scheduling processing method times out, select the optimal individual among them as the outbound scheduling scheme.

Specifically, when an individual appears in the group, and the length difference between the longest queue of one outbound beam and the shortest queue of another outbound beam in this individual is less than the preset value, this individual is used as the final scheduling scheme; or when When annealing, cross-mutation, and elimination are repeatedly performed, the time to execute the algorithm has arrived, and even if the optimal solution has not been found, the current optimal solution will be used as the outbound scheduling scheme.

When implementing the genetic simulated annealing optimization method, considering its complex calculation and long time-consuming, the timing of using this algorithm should be controlled to a certain extent, so as to achieve a satisfactory load balancing optimization effect as much as possible without increasing the computational burden of the system. . A more reasonable time to enable the algorithm is:

1) Default value: When the outbound queue is relatively empty, the outbound can be performed smoothly without outbound load balancing optimization, and the calculation of the genetic simulated annealing algorithm will increase unnecessary calculation overhead. Only in the outbound queue Only when it is relatively full can better input and output be obtained, that is, when the difference between the queue lengths of the largest and smallest two outbound beams in an individual in the group is less than the preset value, the genetic simulated annealing optimization method is used.

2) Timeout of the scheduling processing method: because the genetic simulated annealing algorithm is complex to calculate and takes a long time, and the business outbound has strict time requirements, so the genetic simulated annealing may only be enabled when the interval from the final outbound is greater than the threshold t Optimization method, so as not to cause the situation that the exit cannot be completed at the specified time.

Accompanying drawing 6 is an example diagram after using the genetic simulated annealing optimization method to schedule outbound beams on the basis of Fig. 5. As shown in Fig. 6, the outbound communication in Fig. 5 is After service scheduling, the queue length difference between the longest outbound beam and the shortest outbound beam is 1. After scheduling by genetic simulated annealing optimization method, the number of the longest queue is reduced, and the number of the shortest queue is also reduced , thereby optimizing the load imbalance of the outbound beam to a certain extent.

The main features of the genetic simulated annealing optimization method are:

1) Outbound load balancing optimization is an NP-hard combinatorial optimization problem. The genetic simulated annealing algorithm is not to find the optimal solution, but to find an acceptable better solution under a certain combination search range and search depth. Therefore, the group If there is one individual among them, the difference between the maximum and minimum queue lengths is not greater than the preset value, or the calculation ends when the algorithm times out.

2) Compared with the step-by-step optimization method, the genetic simulated annealing algorithm has a mutation depth of N each time the cross mutation is performed, and N is a positive integer, and after multiple annealing, mutation, and elimination, the optimization considered by the genetic simulated annealing algorithm is actually The number of steps is far more than N, and the step-by-step optimization method can only consider the current one-step optimization. Therefore, the performance of the genetic simulated annealing algorithm is much higher than that of the step-by-step optimization method, and it can adapt to more complex load balancing optimization problems.

The embodiment of the present invention optimizes the outbound mode of the beam, and the load of the outbound beam optimized by the embodiment of the present invention avoids serious unbalanced situations, and achieves a relatively ideal load balance.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than to limit them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: it can still be Modifications are made to the technical solutions described in the foregoing embodiments, or equivalent replacements are made to some of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the spirit and scope of the technical solutions of the various embodiments of the present invention.

Claims (1)

1. set off a beam dispath processing method, it is characterized in that, comprising:

When to outbound data service arrangement departures wave beam, the departures wave beam that can receive the service of described outbound data if know if detect is after the described outbound data service of reception, to there is load imbalance in intrasystem each departures wave beam, then adopt stepping evolutionary method to carry out the dispatch deal of departures wave beam;

Other redundancies that described stepping evolutionary method comprises the outbound data be arranged in described departures wave beam service is arranged into correspondence in system according to the shortest queue method set off in wave beam, and by described outbound data service arrangement in described departures wave beam;

After the process that works as dispatcher according to stepping evolutionary method, then carry out the dispatch deal of departures wave beam according to genetic simulated annealing evolutionary method;

Described genetic simulated annealing evolutionary method comprises:

Using the departures scheduling scheme that obtains according to described stepping evolutionary method as initial individuals;

Based on described initial individuals, exchange arbitrarily N number of outbound data according to the redundancy beam information of departures wave beams all in described system and serve in the redundancy departures wave beam of correspondence, obtain corresponding new individuality; Repeat M-1 time, obtain M-1 described new individuality; As the first colony together with described initial individuals and described M-1 described new individuality; Wherein, described M>N, and be positive integer;

Annealing in process: described annealing in process comprises and all adopts described stepping evolutionary method to carry out the dispatch deal of wave beam of setting off to each individuality in described first colony;

Cross and variation process: described cross and variation process comprises based on the individuality that each annealing in described first colony produces afterwards, again exchanging arbitrarily N number of outbound data according to the redundancy beam information of departures wave beams all in described system serves in the redundancy departures wave beam of correspondence, obtain corresponding M new individuality, form the second colony; Using described first colony together with described second colony as the 3rd colony;

Eliminate process: described superseded process comprises chooses M-N optimum individuality from described 3rd colony, then in remaining individuality, chooses individuality arbitrarily again, as the first new colony;

Repeat described annealing in process, described cross and variation process and described superseded process, until the difference of the queue length of two departures wave beams maximum with minimum in an individuality in colony is less than preset value, or scheduling processing method time-out, select wherein optimum individuality as departures scheduling scheme.