용량 제약 송수신기 통신위성 일정계획 문제의 다항시간 알고리즘
Polynomial Time Algorithm for Satellite Communications Scheduling Problem with Capacity Constrainted Transponder
1
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (20)
- T. Inukai, "An Efficient SS", TDMA Time Slot Assignment Algorithm, 1979, pp.COM-27(10), 1449~1455
- G. Rote, "A Heuristic for Decomposing Traffic Matrics in TDMA Satellite Communication", Zeitschrift für-Methods and Models of Operations Research, 38(3), pp.281~307 (1993)
- K. L. Yeung, "Efficient Time Slot Assignment Algorithms for TDM Hierarchical and Nonhierarchical Switching Systems", IEEE Transactions on Communications, 49(2), pp.351~359 (2001)
- X. Wan, "An Optimal Algorithm for Time-slot Assignment in SS", TDMA Satellite Systems, 2013, 1~6
- D. Werra, "A Note on SS", TDMA Satellite Communication, 1990, pp.135, 69~77
- C. Guéret, "Applications of Optimization with Xpress-MP : 12. 5 Scheduling of Telecommunications via Satellite", pp.185~190 (2005), Dash Optimization Ltd
- "Publicity Campaign" (2009)[URL]
- T. H. Lee, "An Integer Programming Approach to the Time Slot Assignment Problem in SS", TDMA Systems with Intersatellite Links, 2001, pp.135(1), 57~66
- J. P. Jue, "Lightpath Establishment in Wavelength- Routed WDM Optical Networks", pp.99~122 (2001), Kluwer Academic Publishers
- 이상운, "통신위성 일정계획 문제의 다항시간 알고리즘", 한국정보기술학회논문지, 13(4), pp.27~36 (2015), 한국정보기술학회[DOI]
- 이상운, "Polynomial Time Algorithm for Multi-Beam SS", TDMA Satellite Communications Scheduling Problem with Frequency-Hopping Ground Stations, 2015, pp.20(7), 33~40[DOI]
- 이상운, "위성 간 링크된 다중통신위성 일정계획 문제의 다항시간 알고리즘", 한국정보기술학회논문지, 13(8), pp.29~37 (2015), 한국정보기술학회[DOI]
- R. A. Brualdi, "Some Applications of Doubly Stochastic Matrices", Linear Algebra and Its Applications, 107, pp.77~100 (1988)
- A. S. Acampora, "Efficient Utilization of Satellite Transponders via Time-Division Multibeam Scanning", The Bell System Technical Journal, 57(8), pp.2901~2914 (1978)
- K. T. Huang, "A Traffic Reallocation Algorithm for an SS", TDMA System with Frequency-Hopping Earth Stations, 2000, pp.2, 1606~1610
- D. L. Adamy, "EW 102: A Second Course in Electronic Warfare, Chapter 7: Communication Satellite Links" (2004), Horizon House Publications, Inc
- G. Maral, "Performance of Fully Variable Demand Assignment SS", TDMA Satellite Systems, 1987, pp.5(1), 279~290
- T. Gonzalez, "Open-Shop Scheduling to Minimize Finish Time", Journal of the ACM, 23(4), pp.665~679 (1976)
- S. Martello, "Jenö Egerváry : From the Origins of the Hungarian Algorithm to Satellite Communication", Central European Journal of Operations Research, 18(1), pp.47~57 (2010)
- S. G. Petridou, "An Efficient Clustering Oriented Algorithm for Message Scheduling on WDM Star Networks", 14th IEEE Symposium on Communications and Vehicular Technology, Benelux, pp.143~147 (2007)