Research On Real-Time Packet Scheduling In Satellite Network

In recent years, with the developing of satellite system technology, the operation management on satellite system is becoming more important, its’main task is to perform data communication scheduling between earth stations and satellites. For satellite network communication scheduling, we take the way of model-building as the primary manner. The traditional SRS (Satellite Range Scheduling) scheduling model:which characteristic is use the integer programming technology to achieve automatic scheduling, its’scheduling period is usually measured by day, and the service of satellite system is basically following the bending model. With the rapid development of satellite system technology, constellation networks have become highlight technology of the next generation satellite system, the key problem of the constellation maintenance is the communication scheduling among satellite systems.The development of constellation networks have make satellite network generate new demands. Because constellation networks bring ISLs transmit ability in earth station-satellite communication data scheduling, make the dependence on earth station in satellite system greatly decreased, and to satisfy the second generation satellite system controlling the information refresh frequent demands in real-time, and improving the adaptive ability of satellite system, we need to implement the short period scheduling by minutes in real-time.Because the traditional SRS scheduling model has not considered about ISLs and has lots of problems like long period, its communication tasks scheduling is no longer adapted to the latest constellation networks, we need to find a new ISLs scheduling model, so we come up with the SNRS (Satellite Network Range Scheduling) scheduling model, which advantage is the use of ISLs, and when there are great difference between the satellite network communication scheduling model and the traditional satellite system, it can realize some new communication needs about its’control tasks in constellation networks. In SNRS scheduling model, satellite communication task is not simply between target star and earth station, communication tasks can be scheduled between each target star. In order to ensure the link task scheduling be feasibility and the control of satellite system, we need to design good algorithms to guarantee the time limit of task scheduling. This is the real-time packet schedule in satellite network which we are going to research on.The main research contents are as follows:(1) According to the new demands of constellation networks, which realize the information control in real-time and improve the transmit ability of ISLs, we establish the new scheduling model SNRS of constellation networks.(2) By reduce the integer division problem to SNRS in polynomial time, we prove that the SNRS problem is NP complete. (3) By reduce the Three-Partitioning problem to period task scheduling problem in polynomial time; we prove that the period task scheduling problem is NP complete.(4) By the proof of task scheduling problem on fixed priority, we get the conclusions as follows;①Two simple tasks with different periods in non preemptive scheduling, we take the scheduling with short period as priority as optimal scheduling on fixed priority;②Two simple tasks with same periods in non preemptive scheduling, we take the scheduling with long execution time as priority as optimal scheduling on fixed priority;③Two simple tasks with different phases and different periods in non preemptive scheduling, we take the scheduling with short period as priority as optimal scheduling on fixed priority;④Two simple tasks with different phases but same periods in non preemptive scheduling, we take the scheduling with long execution time as priority as optimal scheduling on fixed priority;⑤Lots of tasks with different periods in non preemptive scheduling, we take the scheduling with short period as priority as optimal scheduling on fixed priority;⑥Lots of tasks with same periods in non preemptive scheduling, we take the scheduling with long execution time as priority as optimal scheduling on fixed priority;(5) By the simulation of static priority, dynamic priority and SNRS, we get the conclusions as follows:①Three circumstances in static priority scheduling, that is phase is zero, deadline equal to period, phase is not zero, deadline equal to period and phase is zero, deadline not equal to period, we take the scheduling with short period as priority as optimal scheduling;②EDF(Earliest-Deadline-First) scheduling strategy is better than LST(Least-Slack-Time-First) scheduling strategy in dynamic priority scheduling;③EDF is better than random strategy in the stage of deciding task order, and minimum distance route is better than random route;④Task order route has more important and effective choice scheduling performance than route choice;⑤EDF-minimum distance algorithm and EDF random algorithm has more than50%normal throughput in any load.