그래프 채색에 의한 타임 슬롯 할당 알고리즘

국문 초록 (Abstract)

위성 통신 분야에서 널리 사용되는 시분할 다중 스위칭 시스템은 많은 저대역폭 가입자들로부터 발생되는 트랙픽을 반복되는 프레임에 타임 슬롯을 할당해야 한다. 본 논문에서는 타임 슬롯 할당을 위한 새로운 방법을 제안한다. 기존의 방법인 네트워크 흐름 모델을 사용하지 않고 새로운 방법인 그래프 채색방법을 사용하여 효율적인 타임 슬롯 할당 알고리즘을 제안하였다. 제안된 알고리즘은 주어진 트래픽의 프레임 길이가 2의 멱승일 경우 트래픽을 정확히 반으로 나누어 할당한다. 분할된 트래픽의 프레임 길이가 1이 될 때까지 이 과정을 계속적으로 반복해 분할한다. 제안된 알고리즘의 시간 복잡도는 프레임의 길이가 L이고 스위치 크기가 N인 경우에는 기존의 네트워크 흐름 모델을 사용한 최적의 타임 슬롯 할당 알고리즘의 시간 복잡도는 O (N<SUP>4.5</SUP>) 인데 반해 O (NLlog₂L)이다.

다국어 초록 (Multilingual Abstract)

A simple Time Division Multiplex(TDM) switching system which has been widely in satellite networks provides any size of bandwidth for a number of low bandwidth subscribers by allocating proper number of time slots in a frame. In this paper, we propose a new approach based on graph coloring model for efficient time slot assignment algorithm in contrast to network flow model in previous works. When the frame length of an initial matrix of time slot requests is 2's power, this matrix is divided into two matrices of time slot requests using binary divide and conquer method based on the graph coloring model. This process is continued until resulting matrices of time slot requests are of length one. While the most efficient algorithm proposed in the literature has time complexity of O (N<SUP>4.5</SUP>) , the time complexity of the proposed algorithm is O (NL log₂L ), where N is the number of input/output links and L is the number of time slot alloted to each link in the frame.

목차 (Table of Contents)

• 요약
• Abstract
• Ⅰ. 서론
• Ⅱ. 문제 정의
• Ⅲ. 그래프채색에 의한 TSA 알고리즘
• Ⅳ. 결론
• 참고문헌
• 저자소개

참고문헌 (Reference)

1 S. Kulkarni, "TDMA service for sensor network" 604-609, 2004

2 S. Suresh, "Scheduling multi-rate sessions in time division multiplexed wavelength-routing networks" 18 (18): 2000

3 K. T. Yiu, "Scheduling Satellite- Switched Time-Division Multiple Access With Geneneral Switching Modes" 12 (12): 2004

4 S. Chalasani, "Parallel Algorithms for Time-slot Assignment in TDM Switching System" 41 : 1736-1747, 1993

5 M. A. Bonuccelli, "Optimal Packet Scheduling in tree-structured LEO Satellite Cluster" 9 : 289-295, 2004

6 ISaac Keslassy, "On Guaranted Smooth Scheduling for Input-Queued Switches" 13 (13): 2005

7 M. A. Bonuccelli, "Incremental Time-Slot Assignment in SS/TDMA Satellite Systems" 39 : 1147-1156, 1991

8 K. Y. Eng, "Fundamental Conditions Governing TDM Switching Assignments in Terrestrial and Satellite Networks" 35 : 755-761, 1987

9 S. C Liew, "Comments on `Fundamental Conditions Governing TDM Switching Assignments in Terrestrial and Satellite Networks'" 37 : 187-189, 1989

10 S. Chalasani, "An improved Time-slot Assignment Algorithm for TDM Hierarchical Switching Systems" 41 : 312-317, 1993

11 K. T. Yiu, "A unified Algorithmic Framework for Variable-Rate TDM Switching Assignments" 9 (9): 2001

12 G. Haigang, "A Two Level TDMA Scheduling Protocol with Intra-cluster Coverage for Large Scale Wireless Sensor Network" 6 (6): 2006

13 M. A. Bonuccelli, ""A Fast Time-slot Assignment Algorithm for TDM Hierarchical Switching System" 37 : 870-874, 1989