Premium
Evaluation of algorithms for efficient partitioning and scheduling of data bursts in satellite communications
Author(s) -
Jutty A. K.,
Ghawghawe S. N.,
Ghose D.,
Mani V.
Publication year - 2005
Publication title -
international journal of satellite communications and networking
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.388
H-Index - 39
eISSN - 1542-0981
pISSN - 1542-0973
DOI - 10.1002/sat.822
Subject(s) - computer science , algorithm , heuristics , scheduling (production processes) , greedy algorithm , schedule , computation , heuristic , mathematical optimization , mathematics , artificial intelligence , operating system
We evaluate four scheduling algorithms for satellite communications that use the Time Division Multiple Access methodology. All the algorithms considered are based on the open‐shop model. The open‐shop model is suitably represented or modified to exploit some existing algorithms to solve the satellite communication problem. In the first two algorithms, namely pre‐emptive scheduling with no intersatellite links and greedy heuristics with two intersatellite links, a (traffic) matrix representation of the open‐shop model is used to get a near optimal schedule. In the next two algorithms, generalized heuristic algorithm and the branch and bound algorithm, the open‐shop model is modified to accommodate the inter‐satellite link and this modified open‐shop model is used to solve for a near optimal schedule. The basic methodology of all the algorithms are briefly described and their performance was evaluated through extensive simulations. The performance criteria to evaluate the algorithms are—run time of the algorithms, schedule lengths, and optimality of the algorithm against theoretical bounds. Three of the above‐mentioned algorithms are evaluated by comparing the performance criteria under similar conditions. Optimal branch and bound algorithm is not evaluated due to its high complexity. The general heuristic algorithm is found to give a good trade off between computation time and optimality. The computation time is comparable with the pre‐emptive scheduling algorithm and greedy heuristic algorithm and the schedule length achieved is near to the lower bound value. Copyright © 2005 John Wiley & Sons, Ltd.