데이터 방송 시스템에서 서버는 방송 채널을 통하여 데이터들을 지속적으로 전파하고, 이동 클라이언트는 자신이 원하는 데이터가 방송 채널에 나타나기를 기다리기만 하면 된다. 그러나 방송 채널은 많은 데이터들에 의해 공유되어야 하므로, 원하는 데이터를 수신하기까지 예상 지연시간이 증가할 수 있다. 본 논문은 전체 데이터들의 예상 지연시간을 최소화하기 위하여 다중 방송 채널에 적절하게 데이터를 할당하기 위한 주제를 연구하여 TLBP(Two Level Bin-Packing)로 명명된 새로운 데이터 할당 기법을 제안한다. 본 논문은 우선 평균 예상지연시간의 이론적 하한 값을 소개하고, 이 값에 기초하여 저장소의 용량을 결정한다. TLBP 기법은 저장소-적재 알고리즘을 이용하여 전체 데이터들을 다수 개의 그룹으로 분할하고, 각 그룹의 데이터들을 각 채널에 배정한다. TLBP는 저장소-적재 알고리즘을 두 단계로 적용함에 의해, 동일 방송 채널에 할당된 데이터들의 액세스 확률의 차이를 방송 스케줄에 반영할 수 있어 성능을 향상시킬 수 있다. TLBP와 세가지의 기존 기법과 성능을 비교하기 위하여 시뮬레이션이 수행되었다. 시뮬레이션 결과에 의하면 TLBP는 합리적인 실행부담을 가지면서도 평균 예상지연시간의 성능에 있어서 다른 기법보다 우수한 성능을 보인다.
데이터 방송 시스템에서 서버는 방송 채널을 통하여 데이터들을 지속적으로 전파하고, 이동 클라이언트는 자신이 원하는 데이터가 방송 채널에 나타나기를 기다리기만 하면 된다. 그러나 방송 채널은 많은 데이터들에 의해 공유되어야 하므로, 원하는 데이터를 수신하기까지 예상 지연시간이 증가할 수 있다. 본 논문은 전체 데이터들의 예상 지연시간을 최소화하기 위하여 다중 방송 채널에 적절하게 데이터를 할당하기 위한 주제를 연구하여 TLBP(Two Level Bin-Packing)로 명명된 새로운 데이터 할당 기법을 제안한다. 본 논문은 우선 평균 예상지연시간의 이론적 하한 값을 소개하고, 이 값에 기초하여 저장소의 용량을 결정한다. TLBP 기법은 저장소-적재 알고리즘을 이용하여 전체 데이터들을 다수 개의 그룹으로 분할하고, 각 그룹의 데이터들을 각 채널에 배정한다. TLBP는 저장소-적재 알고리즘을 두 단계로 적용함에 의해, 동일 방송 채널에 할당된 데이터들의 액세스 확률의 차이를 방송 스케줄에 반영할 수 있어 성능을 향상시킬 수 있다. TLBP와 세가지의 기존 기법과 성능을 비교하기 위하여 시뮬레이션이 수행되었다. 시뮬레이션 결과에 의하면 TLBP는 합리적인 실행부담을 가지면서도 평균 예상지연시간의 성능에 있어서 다른 기법보다 우수한 성능을 보인다.
In data broadcasting systems, servers continuously disseminate data items through broadcast channels, and mobile client only needs to wait for the data of interest to present on a broadcast channel. However, because broadcast channels are shared by a large set of data items, the expected delay of re...
In data broadcasting systems, servers continuously disseminate data items through broadcast channels, and mobile client only needs to wait for the data of interest to present on a broadcast channel. However, because broadcast channels are shared by a large set of data items, the expected delay of receiving a desired data item may increase. This paper explores the issue of designing proper data allocation on multiple broadcast channels to minimize the average expected delay time of all data items, and proposes a new data allocation scheme named two level bin-packing(TLBP). This paper first introduces the theoretical lower-bound of the average expected delay, and determines the bin capacity based on this value. TLBP partitions all data items into a number of groups using bin-packing algorithm and allocates each group of data items on an individual channel. By employing bin-packing algorithm in two step, TLBP can reflect a variation of access probabilities among data items allocated on the same channel to the broadcast schedule, and thus enhance the performance. Simulation is performed to compare the performance of TLBP with three existing approaches. The simulation results show that TLBP outperforms others in terms of the average expected delay time at a reasonable execution overhead.
In data broadcasting systems, servers continuously disseminate data items through broadcast channels, and mobile client only needs to wait for the data of interest to present on a broadcast channel. However, because broadcast channels are shared by a large set of data items, the expected delay of receiving a desired data item may increase. This paper explores the issue of designing proper data allocation on multiple broadcast channels to minimize the average expected delay time of all data items, and proposes a new data allocation scheme named two level bin-packing(TLBP). This paper first introduces the theoretical lower-bound of the average expected delay, and determines the bin capacity based on this value. TLBP partitions all data items into a number of groups using bin-packing algorithm and allocates each group of data items on an individual channel. By employing bin-packing algorithm in two step, TLBP can reflect a variation of access probabilities among data items allocated on the same channel to the broadcast schedule, and thus enhance the performance. Simulation is performed to compare the performance of TLBP with three existing approaches. The simulation results show that TLBP outperforms others in terms of the average expected delay time at a reasonable execution overhead.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문은 단일 데이터를 액세스하는 환경에서 지연시간을 줄이기 위한 연구를 진행하였다. 향후 과제로는 동시에 다수의 데이터를 액세스하는 환경과 클라이언트 캐쉬가 존재하는 환경을 고려한 스케줄링 기법에 관한 연구를 진행할 것이다.
성능 평가에서는 기존 기법들과의 비교와 더불어, 제안된 기법이 최적 평균 지연시간의 성능에 얼마나 근접하는 지를 파악하기 위하여 식 (2)에 의해 계산되는 이론적 하한 값과의 성능 비교도 실시한다. 본 논문은 이 이론적 하한 값의 성능을 발휘하는 가상적인 기법을 OPT(optimal)로 표현한다.
그러나 많은 데이터를 방송해야 할 경우에 방송 채널의 순차성으로 인하여 클라이언트가 원하는 데이터를 수신하기까지의 예상지연시간이 크게 증가할 수 있다. 본 논문은 이 지연시간을 줄이기 위하여 다중 방송채널 환경을 위한 데이터 할당 기법에 대한 연구를 진행하였다. 본 논문은 이론적 평균 예상지연시간의 성능을 계산한 후, 이를 각 채널이 균등하게 배분하여 담당할 때 최적의 AED 성능을 발휘할 것이라는 휴리스틱을 적용하였다.
본 논문은 이와 같은 기존 기법들의 단점을 개선하기 위하여 동일 채널의 데이터들도 다른 빈도로 방송할 수 있게 하는 데이터 할당 기법에 대해 연구한다. [12]의 연구는 K개의 방송 채널을 통하여 N개의 데이터들을 방송할 때 AED의 이론적 하한 값이 # 라는 사실을 증명했다.
전형적인 저장소-적재(Bin-Packing) 알고리즘은 일련의 개체들과 이들의 크기 및 저장소(Bin)의 용량이 주어졌을 때, 최소 개수의 저장소를 사용하면서 이들을 저장소에 적재하는 문제를 다룬다[13]. 본 논문은 저장소-적재와 유사한 개념을 도입하여 각 방송 채널이 방송할 데이터들을 결정한다. 본 논문은 각 채널에서 방송되는 데이터들을 그룹화하기 위하여 저장소와 서브저장소(Sub Bin: SBin)의 두 종류의 저장소를 운영하고, 전체 데이터들을 두 단계로 나누어 저장소에 적재한다.
본 논문은 최적 성능인 AEDoptimal 실현을 목표로 하고 있다. 만일 각 채널이 자신에게 할당된 데이터들을 이상적으로 방송한다면, AEDoptimal을 각 채널이 균등하게 배분하여 담당할 때 최적 성능을 발휘할 것이다.
가설 설정
로 표현한다. 그리고 전체 데이터들은 pq의 내림차순으로 정렬되어 있다고 가정한다.
이 연구들은 모두 다음과 같은 동일한 시스템 모델을 가정하고 있다. 방송 데이터들은 동일한 크기를 가진 N 개의 데이터로 구성되며, 유사한 액세스 확률을 가진 데이터들을 동일 채널에 배정하기 위하여 각 데이터들은 액세스 확률의 내림차순으로 정렬되어 있다고 가정한다. 그리고 방송 서버에는 동일 대역폭을 갖는 K개의 방송 채널이 존재하고, 같은 채널에 할당된 데이터들은 평형 방식으로 동일 빈도로 방송된다.
서버가 방송하는 각 데이터는 그 크기가 동일하고, 각 데이터의 액세스 확률은 불균등한 액세스 형태를 모델링하기 위해 많이 사용되는 zipf 분포 모델을[1,4,5] 따른다고 가정한다. zipf 분포 모델에서 각 데이터의 액세스 확률은 θ 값에 의해 결정되는데, θ 값은 각 데이터들의 액세스 확률이 어느 정도 편향되어 있는지를 나타내는 인수로서 θ 값이 커질수록 불균등한 액세스의 정도가 심화된다.
제안 방법
그러나 BP 기법은 액세스 확률이 높은 데이터들을 확률 대비 너무 자주 방송함으로써 상대적으로 액세스 확률이 낮은 데이터들의 지연시간이 증가하게 된다. BP 기법이 Flat과 유사한 성능을 보이는 이유를 해석적으로 분석하기 위해, BP에서 각 CHi에 배정된 데이터 수와 액세스 확률의 합을 Ni와 Si라 하자. CHi의 방송주기는 Ni이므로 CHi의 데이터를 액세스하려면 평균 Ni/2를 기다려야 한다.
TLBP 기법은 각 채널의 데이터들을 이상적으로 방송한다는 전제하에 Bin 용량을 결정하고, 전체 데이터들을 분할하여 각 채널에 할당한다. 그리고 각 채널의 데이터들을 다시 J 개의 그룹으로 분할하여 SBIN에 할당하고, 각 SBIN 별로 평형 방송한다. 그런데 J 값을 작게 설정할 경우에는 각 채널의 데이터들을 최적으로 방송하지 못하게 된다.
본 논문은 이 휴리스틱(heuristic)을 제안된 기법의 데이터 할당 정책에 적용하고, 저장소-적재(bin-packing) 알고리즘에[13] 기초하여 각 채널에서 방송할 데이터들을 결정한다. 그리고 동일 채널에서 방송될 데이터들을 저장소-적재 알고리즘을 이용하여 한번 더 분할하여 각 그룹별로 다른 빈도로 방송한다. 제안된 기법은 전체 데이터들을 두 단계로 세밀하게 분할하기 때문에 동일 채널에 할당된 데이터들을 인기도를 반영하여 다른 빈도로 방송할 수 있다.
본 논문은 이론적 평균 예상지연시간의 성능을 계산한 후, 이를 각 채널이 균등하게 배분하여 담당할 때 최적의 AED 성능을 발휘할 것이라는 휴리스틱을 적용하였다. 그리고 저장소-적재 알고리즘을 두 단계로 적용하여 TLBP로 명명된 새로운 데이터 할당 기법을 제안하고 성능 평가를 실시하였다. 제안된 기법은 다른 기법과 비교하여 채널에 데이터를 할당하기 위한 합리적인 실행 부담을 보이면서도 우수한 AED 성능을 발휘하는데, 특히 물리적 채널의 수가 적을 경우에 다른 기법보다 훨씬 우수한 성능을 보인다.
여기서 j는 SBin 번호로서 방송 스케줄링 알고리즘을 기동시킬 때 이 값을 0으로 초기화한다. 방송 스케줄러는 각 SBin을 J tick 주기마다 선택하며, 동일 SBin에 할당된 데이터들을 공평하게 선정하여 방송한다. 따라서 동일 SBin에 할당된 데이터들은 방송채널 대역폭의 1/J을 사용하며 동일 빈도로 방송된다.
본 논문은 저장소-적재와 유사한 개념을 도입하여 각 방송 채널이 방송할 데이터들을 결정한다. 본 논문은 각 채널에서 방송되는 데이터들을 그룹화하기 위하여 저장소와 서브저장소(Sub Bin: SBin)의 두 종류의 저장소를 운영하고, 전체 데이터들을 두 단계로 나누어 저장소에 적재한다. 따라서 본 논문이 제안하는 기법을 TLBP(Two Level Bin-Packing)로 명명한다.
만일 각 채널이 이상적으로 데이터들을 방송한다면, AEDoptimal을 균등하게 배분하여 각 채널의 예상 지연시간이 AEDoptimal/K가 되도록 각 채널에 데이터를 배정할 때 최적 성능을 발휘할 것이다. 본 논문은 이 휴리스틱(heuristic)을 제안된 기법의 데이터 할당 정책에 적용하고, 저장소-적재(bin-packing) 알고리즘에[13] 기초하여 각 채널에서 방송할 데이터들을 결정한다. 그리고 동일 채널에서 방송될 데이터들을 저장소-적재 알고리즘을 이용하여 한번 더 분할하여 각 그룹별로 다른 빈도로 방송한다.
본 논문은 이 지연시간을 줄이기 위하여 다중 방송채널 환경을 위한 데이터 할당 기법에 대한 연구를 진행하였다. 본 논문은 이론적 평균 예상지연시간의 성능을 계산한 후, 이를 각 채널이 균등하게 배분하여 담당할 때 최적의 AED 성능을 발휘할 것이라는 휴리스틱을 적용하였다. 그리고 저장소-적재 알고리즘을 두 단계로 적용하여 TLBP로 명명된 새로운 데이터 할당 기법을 제안하고 성능 평가를 실시하였다.
따라서 제안된 기법은 다른 기법들에[7-11] 비해 크게 향상된 AED 성능을 발휘할 수 있고, 대부분의 환경에서 거의 최적에 필적하는 성능을 보일 수 있다. 본 논문은 제안된 기법의 성능을 평가하기 위하여 시뮬레이션 모델에 기초하여 제안된 기법과, 기존 기법, 그리고 이론적 하한 값의 성능을 비교한다.
본 실험은 채널의 수를 1~64까지 변화시키면서, 각 기법의 평균 지연시간의 성능추이를 살펴보았다. θ 값은 편향적인 액세스 형태를 모델링하기 위한 대표 값으로 많이 사용되는 0.
최근에는 다중 채널 환경을 위한 연구들이 많이 수행되었는데, 이들은 대부분 전체 데이터들을 어떻게 분할하여 각 채널에 할당할 것인가에 치중하여 연구를 수행하였다[7-11]. 이 연구들은 평균 예상지연시간이 최소화될 수 있는 방향으로 전체 데이터들을 액세스 확률에 근거하여 채널 수만큼 다수 개의 그룹으로 분할하여 각 채널에 할당하였다. 그리고 같은 채널에 할당된 데이터들을 라운드-로빈(round-robin) 방식으로 동일 빈도로 방송하는 방법을 채택했다.
그리고 동일 채널에서 방송될 데이터들을 저장소-적재 알고리즘을 이용하여 한번 더 분할하여 각 그룹별로 다른 빈도로 방송한다. 제안된 기법은 전체 데이터들을 두 단계로 세밀하게 분할하기 때문에 동일 채널에 할당된 데이터들을 인기도를 반영하여 다른 빈도로 방송할 수 있다. 따라서 제안된 기법은 다른 기법들에[7-11] 비해 크게 향상된 AED 성능을 발휘할 수 있고, 대부분의 환경에서 거의 최적에 필적하는 성능을 보일 수 있다.
대상 데이터
이 장은 TLBP 기법의 성능을 평가하고 그 결과를 분석한다. Flat은 가장 기본이 되는 기법이며, DP는 각 채널의 데이터가 평형 방송되는 시스템 모델에서 최적 성능을 발휘하며, BP는 본 논문과 같이 저장소 개념을 사용하기 때문에 이 세 기법을 비교 대상으로 선정하였다. 성능평가 대상이 되는 각 기법은 C 언어로 구현하였으며, 각 실험은 인텔 Core2 Duo 2.
데이터처리
이 절은 채널에 데이터를 할당하기 위한 실행시간을 비교 분석한다. 실행시간 결과는 각 실험을 10번 실행하여 측정한 시간의 평균 값으로 제시하였다. 본 실험에서 θ 값은 실행시간에 큰 영향을 주지 않기 때문에 0.
이론/모형
이 연구들은 평균 예상지연시간이 최소화될 수 있는 방향으로 전체 데이터들을 액세스 확률에 근거하여 채널 수만큼 다수 개의 그룹으로 분할하여 각 채널에 할당하였다. 그리고 같은 채널에 할당된 데이터들을 라운드-로빈(round-robin) 방식으로 동일 빈도로 방송하는 방법을 채택했다. 그런데 이동 컴퓨팅 환경의 특성상 방송해야 될 데이터 수는 방송 채널의 수에 비해서 매우 크기 때문에 한 채널에는 많은 수의 데이터가 배정된다.
본 논문은 각 채널에서 방송되는 데이터들을 그룹화하기 위하여 저장소와 서브저장소(Sub Bin: SBin)의 두 종류의 저장소를 운영하고, 전체 데이터들을 두 단계로 나누어 저장소에 적재한다. 따라서 본 논문이 제안하는 기법을 TLBP(Two Level Bin-Packing)로 명명한다. TLBP에서 저장소의 개수는 고정되어 있고, AED 시간이 최소화될 수 있도록 저장소의 용량을 결정하고 전체 방송 데이터들을 적절히 분할하여 저장소에 적재한다.
만일 각 채널이 자신에게 할당된 데이터들을 이상적으로 방송한다면, AEDoptimal을 각 채널이 균등하게 배분하여 담당할 때 최적 성능을 발휘할 것이다. 본 논문은 이 휴리스틱(heuristic)을 TLBP 기법의 데이터 할당 정책에 적용한다. 이를 위해서는 각 채널이 AEDoptimal/K의 예상지연시간을 갖도록 데이터가 할당되어야 한다.
성능/효과
K의 변화에 따른 평균 지연시간의 성능이 그림 1에 있는데, TLBP, DP, BP 그리고 Flat 기법 순으로 우수한 성능을 보인다. TLBP는 다른 기법들에 비해 매우 우수한 성능을 보일 뿐만 아니라, OPT에 거의 필적하는 성능을 발휘하는 것을 알 수 있다. 참고로 K가 3 이상이 되면 TLBP와 OPT는 1% 이내의 성능 차이를 보인다.
제안된 기법은 전체 데이터들을 두 단계로 세밀하게 분할하기 때문에 동일 채널에 할당된 데이터들을 인기도를 반영하여 다른 빈도로 방송할 수 있다. 따라서 제안된 기법은 다른 기법들에[7-11] 비해 크게 향상된 AED 성능을 발휘할 수 있고, 대부분의 환경에서 거의 최적에 필적하는 성능을 보일 수 있다. 본 논문은 제안된 기법의 성능을 평가하기 위하여 시뮬레이션 모델에 기초하여 제안된 기법과, 기존 기법, 그리고 이론적 하한 값의 성능을 비교한다.
적절하게 J 값을 설정하는 것이 성능에 영향을 미치는데, 이 값은 Bin에 할당된 데이터 수와 θ 값을 고려하여 결정해야 한다. 본 논문의 실험에서는 J 값을 10~20 정도로 설정할 때 우수한 성능을 보인다. Bin에 배정된 데이터 수에 따라 각 Bin 별로 SBin의 수를 다르게 설정하는 것이 가장 우수한 성능을 발휘하지만, 그 성능 차이가 크지 않기 때문에 본 논문은 모든 Bin의 J값을 동일하게 설정하였다.
각 Bin의 데이터들은 액세스 확률의 내림차순으로 정렬을 유지한다. 본 연구는 전체 데이터들이 액세스 확률의 내림차순으로 정렬되어 있다고 가정하고 데이터는 d1~ dN의 순서로 할당하므로, 각 Bin에 데이터가 저장되는 순서를 유지하기만 하면 Bin의 정렬 특성을 쉽게 유지할 수 있다. 이와 같은 방식으로 Bin1~BinK에 데이터를 할당하는 알고리즘이 표 2에 제시되어 있는데, 여기서 NextDataAllocI는 Bin에 할당할 다음 데이터의 인덱스를 의미한다.
그리고 저장소-적재 알고리즘을 두 단계로 적용하여 TLBP로 명명된 새로운 데이터 할당 기법을 제안하고 성능 평가를 실시하였다. 제안된 기법은 다른 기법과 비교하여 채널에 데이터를 할당하기 위한 합리적인 실행 부담을 보이면서도 우수한 AED 성능을 발휘하는데, 특히 물리적 채널의 수가 적을 경우에 다른 기법보다 훨씬 우수한 성능을 보인다. 그리고 TLBP 기법은 AED의 이론적 하한 값에 거의 필적할 정도로 우수한 성능을 보인다.
따라서 TLBP는 다른 기법에 비하여 우수한 성능을 보인다. 참고로 K가 4인 경우에 TLBP는 DP 기법보다 11% 이상 우수한 성능을 보이며, BP나 Flat 기법보다 100% 이상 향상된 성능을 보인다.
후속연구
본 논문은 단일 데이터를 액세스하는 환경에서 지연시간을 줄이기 위한 연구를 진행하였다. 향후 과제로는 동시에 다수의 데이터를 액세스하는 환경과 클라이언트 캐쉬가 존재하는 환경을 고려한 스케줄링 기법에 관한 연구를 진행할 것이다.
질의응답
핵심어
질문
논문에서 추출한 답변
평균 예상지연 시간이란 무엇인가?
그러나 방송 시스템에서 서버는 제한된 방송 대역폭을 통하여 많은 데이터들을 일방적으로 방송하므로 클라이언트가 어떤 데이터를 액세스하려면 그 데이터가 방송되기를 기다려야 한다. 방송 시스템의 주요 성능지수는 평균 예상지연(average expected delay: AED) 시간인데, 이는 클라이언트가 어떤 데이터를 액세스하는데 필요한 평균 대기시간을 의미한다. AED 성능은 채널에 데이터를 할당하는 정책 및 방송 스케줄링(data broadcast scheduling) 기법에 크게 영향을 받기 때문에 이에 대한 많은 연구들이 수행되었다.
현재 사용하는 방송 방식의 데이터 전달 기법의 한계점은 무엇인가?
방송 방식의 데이터 전달 기법은 방대한 클라이언트들을 지원해야 하는 환경이나 이동 컴퓨팅 환경에서 정보 전달을 위한 주요 기술로 인정받고 있다. 그러나 많은 데이터를 방송해야 할 경우에 방송 채널의 순차성으로 인하여 클라이언트가 원하는 데이터를 수신하기까지의 예상지연시간이 크게 증가할 수 있다. 본 논문은 이 지연시간을 줄이기 위하여 다중 방송채널 환경을 위한 데이터 할당 기법에 대한 연구를 진행하였다.
방송 시스템의 주요 성능지수는 무엇인가?
그러나 방송 시스템에서 서버는 제한된 방송 대역폭을 통하여 많은 데이터들을 일방적으로 방송하므로 클라이언트가 어떤 데이터를 액세스하려면 그 데이터가 방송되기를 기다려야 한다. 방송 시스템의 주요 성능지수는 평균 예상지연(average expected delay: AED) 시간인데, 이는 클라이언트가 어떤 데이터를 액세스하는데 필요한 평균 대기시간을 의미한다. AED 성능은 채널에 데이터를 할당하는 정책 및 방송 스케줄링(data broadcast scheduling) 기법에 크게 영향을 받기 때문에 이에 대한 많은 연구들이 수행되었다.
참고문헌 (14)
S. Acharya, "Broadcast Disks: Disseminationbased Data Management for Asymmetric Communication Environments," Ph.D. thesis, Brown University, 1998.
M. Franklin and S. Zdonik, "A Framework for Scalable Dissemination-Based Systems," Proc. ACM OOPSLA Conf., pp. 94-105, 1997.
M. Franklin and S. Zdonik, "Data in Your Face: Push Technology in Perspective," Proc. ACM SIGMOD Conf., pp. 516-519, 1998.
S. Acharya, R. Alonso, M. Franklin, and S. Zdonik, "Broadcast Disks: Data Management for Asymmetric Communications environments," Proc. ACM SIGMOD Conf., pp. 199- 210, 1995.
N.H. Vaidya and S. Hameed, "Scheduling Data Broadcast in Asymmetric Communication Environments," Wireless Networks, Vol.5, No.3, pp. 171-182, 1999.
J.H. Min, J.Y.Hwang, and D.W. Paik, "A Data Scheduling Algorithm Considering the Request Probability for Data Broadcasting," Journal of Korea Multimedia Society Vol.11, No.3, pp. 398-403, 2008.
K. Prabhakara, K. A. Hua, and J. Oh "Multi- Level Multi-Channel Air Cache Designs for Broadcasting in a Mobile Environment," Proc. Int'l Conf. Data Eng. (ICDE), 2000.
W.C. Peng and M.S. Chen, "Efficient Channel Allocation Tree Generation for Data Broadcasting in A Mobile Computing Environment," Wireless Networks, Vol.9, No.2, pp. 117-129, 2003.
W.G. Yee, S. Navathe, E. Omiecinski, and C. Jermaine, "Efficient Data Allocation over Multiple Channels at Broadcast Servers," IEEE Trans. on Computers, Vol.51, No.10, pp. 1231-1236, 2002.
S. Wang and H.L. Chen, "An O(N log K) Restricted Dynamic Programming Algorithm for Data Allocation over Multiple Channels," IEICE trans. on communications, Vol.E88-B, No.9, pp. 3756-3764, 2005.
C. Hsu, G. Lee, and A.L.P. Chen, "A Near Optimal Algorithm for Generating Broadcast Programs on Multiple Channels," Proc. ACM 10th Int'l Conf. CIKM, pp. 303-309, 2001.
D. Johnson, A. Demers, J. Ullman, M. Garey, and M. Graham, "Worst-Case Performance Bounds for Simple one Dimensional Bin Packing Algorithms," SIAM J. on Computing, Vol. 3, No.4, pp. 299-325, 1974.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.