A Real-Time Algorithm for Timeslot Assignment in ISM System with DVB-RCS

ETRI Journal

关键词: timeslot scheduling;    MF-TDMA;    DVB-RCS;    Interactive satellite multimedia;   

Others  :  1185560
DOI  :  10.4218/etrij.07.0105.0264

【 摘 要 】

This paper considers a timeslot assignment problem in an interactive satellite multimedia (ISM) system with digital video broadcast-return channel via satellite (DVB-RCS). The timeslot assignment problem is formulated as a binary integer programming to maximize the overall weighted throughput and is shown to be NP-hard. Thus, three real-time heuristic algorithms including ratio-based, packet-size (PS)-based, and transmission gain (TG)-based are derived, and some computational experiments are made. Considering the results, the ratio-based heuristic algorithm is demonstrated to be the most effective and efficient. We propose adapting the ratio-based heuristic algorithm to the timeslot assignment problem to greatly improve the ISM system utilization.

   

【 参考文献 】

• [1]A. Jamalipour, "Broadband Satellite Networks: The Global IT Bridge," Proc. IEEE, vol. 89, Jan. 2001, pp. 88-104.
• [2]T. Le-Ngoc, V. Leung, P. Takats, and P. Garland, "Interactive Multimedia Satellite Access Communications," IEEE Commun. Mag., vol. 41, no. 7, July 2003, pp. 78-85.
• [3]J. Neale, R. Green, and J. Landovskis, "Interactive Channel for Multimedia Satellite Networks," IEEE Commun. Mag., Mar. 2001.
• [4]Digital Video Broadcasting (DVB); Interaction Channel for Satellite Distribution Systems, ETSI EN 301 790 (V1.2.2), 2000.
• [5]Y. H. Cho and H.J. Lee, "Broadband Satellite Access Network (BSAN) System for Interactive Multimedia Services," 2nd ETRI-CRL Joint Conf., Japan, 2001.
• [6]SatNews Online. (2001). http://www.satnews.com/stories2/ 4nov2001-3.html [Online]
• [7]K.D. Lee, Y.H. Cho, S.J. Lee, and H.J. Lee, "Optimal Design of Superframe Pattern for DVB-RCS Return Link," ETRI J., vol. 24, no. 3, 2002, pp. 251-254.
• [8]K.D. Lee, H.J. Lee, Y.H. Cho, and D.G. Oh, "Throughput-Maximizing Timeslot Scheduling for Interactive Satellite Multiclass Services," IEEE Commun. Lett., vol. 7, June 2003, pp. 263-265.
• [9]K.D. Lee, Y.H. Cho, H.J. Lee, and D.G. Oh, "Improving Efficiency of Timeslot Assignment for Non-realtime Data in a DVB-RCS Return Link: Modeling and Algorithm," ETRI J., vol. 25, no. 4, Aug. 2003, pp. 211-218.
• [10]K.D. Lee, "Delay Control for Non-Real-Time Data in Interactive Multimedia Satellite Networks," IEEE Commun. Lett., vol. 8, Nov. 2004, pp. 665-667.
• [11]M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.