다중 방송 채널 환경을 위한 서브 채널별 평형 방송과 제곱근 법칙에 기초한 효율적인 방송 스케줄링 기법 = An Efficient Broadcast Scheduling Algorithm based on Flat Broadcast per Sub-channel and a Square Root Rule for Multiple Broadcast-channel Environments

국문 초록 (Abstract)

데이터 방송 시스템에서 방송채널은 많은 데이터에 의해 공유되므로, 원하는 데이터를 수신하기까지의 지연시간이 증가할 수 있다. 이 시간을 줄이기 위해 본 논문은 다중 채널을 통한 데이터 방송의 문제를 연구하여 EBSA(Efficient Broadcast Scheduling Algorithm)로 명명된 새로운 방송 스케줄링 기법을 제안한다. 제안된 기법은 동일 방송채널에 할당된 데이터들을 인기도를 반영해 다른 빈도로 방송하기 위해 서브채널 별로 평형 방송하는 시스템 모델을 채택한다. EBSA는 평균 예상지연의 이론적 최적 값을 계산하고, 이 값을 각 채널에 균등하게 배분하는 간단한 정책을 사용해 데이터들을 다수 개의 그룹으로 분할한다. 따라서 EBSA는 DP에 기초한 기법에 비해 데이터 분할을 위한 실행부담을 크게 줄일 수 있다. 그리고 AED가 최소화되도록 각 방송채널의 서브채널 수를 적절히 설정하므로 과할당 현상을 줄일 수 있다. 이와 같은 요인의 조합으로 인해 제안된 기법은 매우 적은 실행부담으로 이론적 최적 AED에 거의 근접하는 성능을 보일 수 있다.

다국어 초록 (Multilingual Abstract)

In data broadcasting systems, the delay time of receiving a desired data item may increase since broadcast channels are shared by a large set of data items. This paper explores the problem of data broadcast over multiple channels to reduce this wait time, and proposes a new broadcast scheduling scheme named EBSA(Efficient Broadcast Scheduling Algorithm). The proposed scheme employs a flat broadcast system model per sub-channel to broadcast data items on the same channel in different frequencies reflecting their popularities. EBSA calculates the theoretical optimal value of average expected delay(AED), and then partitions data items in a number of data groups by using a simple policy of equally distributing the optimal AED on each channel. Therefore, it can significantly reduce the execution overhead compared to DP-based algorithms. In addition, EBSA is capable of reducing over-allocation phenomena by properly setting the number of sub-channels of each broadcast channel so that the AED can be minimized. By the combination of these factors, the proposed scheme can show the performance nearly close to the theoretically optimal AED at a very low execution overhead.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 새로운 방송 스케줄링 기법
• 4. 성능 평가 및 분석
• 5. 결론
• References

참고문헌 (Reference)

• 1 권혁민, "서브 채널별 평형 방송과 동적 프로그래밍에 기초한 유사 최적화 방송 스케줄링 기법" 한국정보과학회 38 (38): 325-330, 2011
• 2 N.H. Vaidya, "Scheduling data broadcast in asymmetric communication environments" 5 (5): 171-182, 1999
• 3 S. Wang, "Near-optimal data allocation over multiple broadcast channels" Elsevier Science 29 (29): 1341-1349, 2006
• 4 W.C. Peng, "Efficient channel allocation tree generation for data broadcasting in a mobile computing environment" 9 (9): 117-129, 2003
• 5 W.G. Yee, "Efficient Data Allocation over Multiple Channels at Broadcast Servers" 51 (51): 1231-1236, 2002
• 6 S. Y. Yi, "Effective generation of data broadcast schedules with different allocation numbers for multiple wireless channels" 20 (20): 668-677, 2008
• 7 S. Acharya, "Broadcast Disks: Dissemination-based Data Management for Asymmetric Communication Environments" Brown Univ 1998
• 8 S. Acharya, "Broadcast Disks: Data Management for Asymmetric communications environments" 199-210, 1995
• 9 J.W. Wong, "Broadcast Delivery" 76 (76): 1566-1577, 1988
• 10 S. Wang, "An O(N log K) Restricted Dynamic Programming Algorithm for Data Allocation over Multiple Channels" E88-B (E88-B): 3756-3764, 2005
• 11 C. Hsu, "A near optimal algorithm for generating broadcast programs on multiple channels" 303-309, 2001
• 12 H. M. Kwon, "A Near Optimal Data Allocation Scheme for Multiple Broadcast-Channel Environments" 12 (12): 17-27, 2012