본문 바로가기
  • Home

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 : Engineering > Computer Science

Sang-Un, Lee 1

1강릉원주대학교

Accredited

ABSTRACT

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.

Citation status

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