The Journal of Korean Institute of Information Technology (한국정보기술학회논문지)

Korean Institute of Information Technology (한국정보기술학회)
권호 표지
DOI QR코드

DOI QR Code

Polynomial Time Algorithm for Multi-Satellite Communications Scheduling Problem with Intersatellite Links

위성 간 링크된 다중통신위성 일정계획 문제의 다항시간 알고리즘

  • Lee, Sang-Un (Dept. of Multimedia Engineering, Gangneung-Wonju National University)
  • 이상운 (강릉원주대학교 멀티미디어공학과)
  • Received : 2015.01.20
  • Accepted : 2015.02.19
  • Published : 2015.08.31
⟨ Previous Next ⟩

Abstract

This paper deals with the time slot assignment problem (TSAP) that multi-satellite with intersatellite links (ISL) switches to traffic between 2n ground stations using on-board switching modes in SS/TDMA system. For this problem, there is only used to the linear programming (LP) or heuristic methods because there has been unknown the polynomial time algorithm to solve the optimal solution thus this problem has been classified as NP-hard. This paper suggests the algorithm with $O(n^2)$ time complexity to solve the optimal solution for this problem. Firstly, the proposed algorithm transforms the $2n{\times}2n$ traffic matrix D into normalized D(ND) with all the rows and columns have the lower bound (LB) that is a maximum sum of traffic of rows or columns. Nextly, we select the maximum traffic of row and column in ISL first from ND matrix, then we select the other maximum traffic in nonoverlapping rows and columns. We decide the kth switch mode and the duration from the minimum traffic in the selected traffics. The proposed algorithm can be get the optimal solution for experimental data.

본 논문은 통신위성 간 링크 (ISL)를 가진 SS/TDMA 기법을 적용한 다중통신위성으로 2n개 지구국 상호간 데이터 전송을 수행하는 ISL-시간대 배정 문제 (ISL-TSAP)를 다룬다. 본 문제는 NP-난제로 최적 해를 다항시간으로 구하는 알고리즘이 알려져 있지 않아 선형계획법 (LP)이나 휴리스틱 방법들이 적용되고 있다. 본 논문은 ISL-TSAP에 대해 $O(n^2)$ 수행 복잡도로 최적 해를 얻을 수 있는 알고리즘을 제안한다. 제안된 방법은 먼저, $2n{\times}2n$ 트래픽 행렬 D를 행과 열의 최대값을 하한값 (LB)으로 정규화시킨 ND 행렬로 만드는 방법을 제안하였다. 다음으로 ND 행렬에서 ISL의 최대값을 우선 선택하고, 중첩되지 않은 나머지 행과 열의 최대값을 선택한 후, 선택된 트래픽들 중에서 최소값으로 k번째 스위치 모드의 길이를 결정하였다. 제안된 알고리즘을 실험 데이터에 적용한 결과 최적 해를 얻었다.

Keywords

References

  1. K. Feher, "Digital Communications: Satellite/Earth Station Engineering", Noble Publishing Corporation, Dec. 1997.
  2. T. H. Lee and S. S. Park, "An Integer Programming Approach to the Time Slot Assignment Problem in SS/TDMA Systems with Intersatellite Links", European Journal of Operational Research, Vol. 135, No. 1, pp. 57-66, Nov. 2001. https://doi.org/10.1016/S0377-2217(00)00291-5
  3. K. L. Yeung, "Efficient Time Slot Assignment Algorithms for TDM Hierarchical and Nonhierarchical Switching Systems", IEEE Transactions on Communications, Vol. 49, No. 2, pp. 351-359, Feb. 2001. https://doi.org/10.1109/26.905898
  4. G. Rote and A. Vogel, "A Heuristic for Decomposing Traffic Matrics in TDMA Satellite Communication", Zeitschrift fur - Methods and Models of Operations Research, Vol. 38, No. 3, pp. 281-307, Oct. 1993. https://doi.org/10.1007/BF01416610
  5. S. H. Kim and S. H. Kim, "An Efficient Algorithm for Generalized SS/TDMA Scheduling with Satellite Cluster and Intersatellite Links", International Journal of Satellite Communications, Vol. 13, No. 1, pp. 31-37, Jan. 1995. https://doi.org/10.1002/sat.4600130104
  6. S. H. Kim and S. H. Kim, "An Efficient Algorithm for Generalized SS/TDMA Scheduling with Satellite Cluster", The Spring Conference of Korean Institute of Industrial Engineers, pp. 13-20, Apr. 1994.
  7. A. Ganz and Y. Gao, "SS/TDMA Scheduling for Satellite Clusters", IEEE Transactions on Communications, Vol. 40, No. 3, pp. 597-603, Mar. 1992. https://doi.org/10.1109/26.135730
  8. A. Ganz and Y. Gao, "TDMA Communication for SS/TDMA Satellites with Optical Intersatellite Links", IEEE International Conference on Communications, Atlanta, GA, pp. 1081-1085, Apr. 1990.
  9. B. M. Nyambo and G. K. Janssens, "A Solution Method for the Time Slot Assignment Problem in SS/TDMA Systems with Intersatellite Links", Proceedings of the Sixth IASTED International Conference on Modelling, Simulation, and Optimization: Science and Technology for Development in the 21st Centry, pp. 239-242, Sep. 2006.
  10. M. El-Soudani and M. El-Ghonemi, "An Optimal Time Slot Assignment Algorithm in SS/TDMA System with Intersatellite Link", Proceedings of 6th Mediterranean Electrotechnical Conference, pp. 633-636, May 1991.
  11. A. A. Bertossi, G. Bongiovanni, and M. A. Bonuccelli, "Time Slot Assignment in SS/TDMA Systems with Intersatellite Links", IEEE Transactions on Communications, Vol, COM-35, No. 6, pp. 602-608, June 1987.
  12. D. L. Adamy, "EW 102: A Second Course in Electronic Warfare, Chapter 7: Communication Satellite Links", Horizon House Publications, Inc. 2004.
  13. M. Minoux and C. Brouder, "Models and Algorithms for Optimal Traffic Assignment in SS/TDMA Switching Systems", International Journal of Satellite Communications, Vol. 5, No. 1, pp. 33-47, Jan. 1987. https://doi.org/10.1002/sat.4600050106
  14. X. Wan, F. Shan, and Z. Shen, "An Optimal Algorithm for Time-slot Assignment in SS/TDMA Satellite Systems", IEEE 22nd International Conference on Computer Communications and Networks (ICCCN), pp. 1-6, July 2013.
  15. T. Gonzalez and S. Sahni, "Open-Shop Scheduling to Minimize Finish Time", Journal of the ACM, Vol. 23, No. 4, pp. 665-679, Oct. 1976. https://doi.org/10.1145/321978.321985
  16. C. Gueret, X. Prins, and M. Sevaux, "Applications of Optimization with Xpress-MP: 12.5 Scheduling of Telecommunications via Satellite", Dash Optimization Ltd., pp. 185-190, Feb. 2005.
  17. S. U. Lee, "Job Shop Scheduling Algorithm", Journal of KIIT, Vol. 11, No. 5, pp. 158-166, May 2013.
  18. S. U. Lee, "A Minimization of Makespan Algorithm for Identical Processing Machines", Journal of KIIT, Vol. 12, No. 5, pp. 123-130, May 2014.