Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder

Sang-Un, Lee

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

Sang-Un, Lee ¹

¹강릉원주대학교

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.
KEYWORDS

Time slot, Makespan, Switch mode, Duration, Capacity constrainted
REFERENCES (20)

[journal] T. Inukai / 1979 / An Efficient SS/TDMA Time Slot Assignment Algorithm / IEEE Transactions on Communications COM-27(10) : 1449~1455

[journal] G. Rote / 1993 / A Heuristic for Decomposing Traffic Matrics in TDMA Satellite Communication / Zeitschrift für-Methods and Models of Operations Research 38(3) : 281~307

[journal] K. L. Yeung / 2001 / Efficient Time Slot Assignment Algorithms for TDM Hierarchical and Nonhierarchical Switching Systems / IEEE Transactions on Communications 49(2) : 351~359

[confproc] X. Wan / 2013 / An Optimal Algorithm for Time-slot Assignment in SS/TDMA Satellite Systems / IEEE 22nd International Conference on Computer Communications and Networks (ICCCN) : 1~6

[journal] D. Werra / 1990 / A Note on SS/TDMA Satellite Communication / Linear Algebra and Its Applications 135 : 69~77

[book] C. Guéret / 2005 / Applications of Optimization with Xpress-MP : 12. 5 Scheduling of Telecommunications via Satellite / Dash Optimization Ltd : 185~190

[web] M. Edvall / 2009 / Publicity Campaign / Tomlab Optimization Inc / http://tomsym.com/examples/tomsym_satellitecomm.html

[journal] T. H. Lee / 2001 / An Integer Programming Approach to the Time Slot Assignment Problem in SS/TDMA Systems with Intersatellite Links / European Journal of Operational Research 135(1) : 57~66

[book] J. P. Jue / 2001 / Lightpath Establishment in Wavelength- Routed WDM Optical Networks / Kluwer Academic Publishers : 99~122

[journal] 이상운 / 2015 / Polynomial Time Algorithm for Satellite Communications Scheduling Problem / 한국정보기술학회논문지 / 한국정보기술학회 13(4) : 27~36 / http://dx.doi.org/10.14801/jkiit.2015.13.4.27

[journal] 이상운 / 2015 / Polynomial Time Algorithm for Multi-Beam SS/TDMA Satellite Communications Scheduling Problem with Frequency-Hopping Ground Stations / 한국컴퓨터정보학회논문지 / 한국컴퓨터정보학회 20(7) : 33~40

[journal] 이상운 / 2015 / Polynomial Time Algorithm for Multi-Satellite Communications Scheduling Problem with Intersatellite Links / 한국정보기술학회논문지 / 한국정보기술학회 13(8) : 29~37 / http://dx.doi.org/10.14801/jkiit.2015.13.8.29

[journal] R. A. Brualdi / 1988 / Some Applications of Doubly Stochastic Matrices / Linear Algebra and Its Applications 107 : 77~100

[journal] A. S. Acampora / 1978 / Efficient Utilization of Satellite Transponders via Time-Division Multibeam Scanning / The Bell System Technical Journal 57(8) : 2901~2914

[confproc] K. T. Huang / 2000 / A Traffic Reallocation Algorithm for an SS/TDMA System with Frequency-Hopping Earth Stations / Proceedings of IEEE Vehicular Technology, Tokyo, Japan 2 : 1606~1610

[book] D. L. Adamy / 2004 / EW 102: A Second Course in Electronic Warfare, Chapter 7: Communication Satellite Links / Horizon House Publications, Inc

[journal] G. Maral / 1987 / Performance of Fully Variable Demand Assignment SS/TDMA Satellite Systems / International Journal of Satellite Communications 5(1) : 279~290

[journal] T. Gonzalez / 1976 / Open-Shop Scheduling to Minimize Finish Time / Journal of the ACM 23(4) : 665~679

[journal] S. Martello / 2010 / Jenö Egerváry : From the Origins of the Hungarian Algorithm to Satellite Communication / Central European Journal of Operations Research 18(1) : 47~57

[confproc] S. G. Petridou / 2007 / An Efficient Clustering Oriented Algorithm for Message Scheduling on WDM Star Networks / 14th IEEE Symposium on Communications and Vehicular Technology, Benelux : 143~147
KCI Citation (0)

KJC Korea
Journal Central

Statistics

Tools