Home
>
Explore Content
>
All Issues
>
Article View
Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder
Journal of The Korea Society of Computer and Information
Abbr :
JKSCI
2016, 21(6), pp.47-53
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
2016, 21(6), pp.47-53
Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science
-
This paper deals with the capacity constrained time slot assignment problem(CTSAP) that a satellite switches to traffic between × ground stations using on-board ≤ min -transponders switching modes in SS/TDMA time-division technology. There was no polynomial time algorithm to solve the optimal solution thus this problem classified by NP-hard. This paper suggests a heuristic algorithm with time complexity to solve the optimal solution for this problem. Firstly, the proposed algorithm selects maximum packet lengths of combination and transmits the cut of minimum packet length in each switching mode(MSMC). In the case of last switching mode with inefficient transmission, we applies a compensation strategy to obtain the minimum number of switching modes and the minimum makespan. The proposed algorithm finds optimal solution in polynomial time for all of the experimental data.
85
Viewed
Print this page
Download PDF