Optimization scheduling of MPEG-4 FGS video coding stream under the feasible mandatory constraint

MPEG-4 video coding stream with Fine Granularity Scalability (FGS) can be flexibly dropped by very fine granularity so as to adapt to the available network bandwidth. The MPEG-4 FGS model is similar to the imprecise computation model originally proposed in the real-time scheduling field. In both models, it is required that all the mandatory tasks be completely scheduled before their deadlines even in the worst case, which is called the feasible mandatory constraint. The problem is how to maximize the number of the scheduled tasks based on the importance of tasks and to satisfy the feasible mandatory constraint. We adapt the existing unit-time tasks scheduling algorithm to address the problem by using a weighted assignment scheme that adds constant weights to mandatory tasks. Under the feasible mandatory constraint, we prove that the proposed algorithm maximizes the total weights of the scheduled tasks, and all mandatory tasks are guaranteed to be completely scheduled before their deadlines. The experimental results show the performance of the video quality for our scheduling algorithm by the measurements of Peak Signal to Noise Ratio (PSNR).