본문 바로가기
  • Home

Polynomial Time Algorithm for Multi-Beam SS/TDMA Satellite Communications Scheduling Problem with Frequency-Hopping Ground Stations

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2015, 20(7), pp.33-40
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

The time slot assignment problem (TSAP) or Satellite Communications scheduling problem (SCSP) for a satellite performs n ×n ground station data traffic switching has been known NP-hard problem. This paper suggests O(n2) time complexity algorithm for TSAP of a satellite that performs n2 × n2 ground station data traffic switching. This problem is more difficult than n × n TSAP as NP-hard problem. Firstly, we compute the average traffic for n -transponder's basic coverage zone and applies ground station exchange method that swap the ground stations until all of the transponders have a average value as possible. Nextly, we transform the D matrix to DLB traffic matrix that sum of rows and columns all of transponders have LB. Finally, we select the maximum traffic of row and column in DLB , then decide the duration of th switch mode to minimum traffic from selected values. The proposed algorithm can be get the optimal solution for experimental data.

Citation status

* References for papers published after 2022 are currently being built.