論文
DBSJ Letters Vol.4, No.3――――――――――――――――――――――――――――――――――――
53.7sec

再生単位を考慮したスケジューリ
ング手法における使用チャネル数
について

S1

S1S1S1・・・ bps

C2 ・・・

S2,1

S2,2

S2,1

S2,2・・・ bps

C3 ・・・

S3,1

S3,2

S3,3

S3,1・・・ bps

C67

S67,1

S67,2

S67,3

S67,4

Time

義久 智樹♥
西尾 章治郎♠

塚本 昌彦♦

Tomoki YOSHIHISA Masahiko TSUKAMOTO
Shojiro NISHIO

近年の放送のデジタル化にともない，音楽や映画といった連続メディアデータの放送型配信に対する注目が高まっている．連続メディアデータ放送では，一般に，クライアントはデータの再生が開始されるまで待つ必要があるため，この待ち時間を短縮する様々な手法が提案されている．AHB 法
では，再生の単位を考慮することで待ち時間を効率的に短縮しているが，使用チャネル数が膨大になる．しかし，ハードウェアの仕様や，処理の簡単化といった理由から使用チャネル数には制限がある．そこで本稿では，使用チャネル数を調整できるように AHB 法を改良する．幾つかの改良方法が考えられるため，本稿では 4 個の改良方法について，性能比較を行う．
Due to the recent digitization of broadcasting systems,
broadcasting continuous media data such as music andmovies have attracted great attention. In continuous
media data broadcasting, since clients have to wait until
starting playing data, various methods to reduce thewaiting time are proposed. Although the AHB method
reduces the waiting time effectively by considering units
for playing, the number of available channels becomes
massive. However, for reasons of specifications of thehardware or facilitations of the process, the number ofavailable channels can be restricted. In this paper, weimprove the AHB method to be able to adjust the numberof channels. Since some improved methods are supposed,
we consider four improved methods and evaluate them.

1. はじめに
近年の放送のデジタル化にともない，音楽や映画といった連続メディアデータの放送型配信に対する注目が高まっている[2, 8]．放送型配信では，サーバが複数のクライアントにまとめてデータを配信できるため，クライアント数が非常♥

正会員 京都大学学術情報メディアセンター
yoshihisa@media.kyoto-u.ac.jp♦正会員 神戸大学工学部 tuka@kobe-u.ac.jp♠正会員 大阪大学大学院情報科学研究科
nishio@ist.osaka-u.ac.jp

1・・・

On the Number of Available Channels in a
Scheduling Method Considering Units forPlaying

5.00M

C1 ・・・

2.50M

1.67M

74.6kbps

図1 HB法の放送スケジュール例
Fig.1 An example of a broadcast schedule
under the HB methodに多い場合に有効だが，一般に同じデータを周期的に繰り返して放送するため，クライアントは所望のデータが放送されるまで待つ必要がある．このため，クライアントがデータを途切れずに再生できることを考慮したうえで，この待ち時間を短縮する様々な手法が提案されている[4-6, 8-11]．これらの手法のほとんどは，サーバやクライアントが使用するチャネル数に制限はないと想定しているが，使用チャネル数に制限がある以下の状況が考えられる．
z ハードウェアの仕様上，多くの物理チャネルから同時にデータを受信できない．
z 処理の簡単化のため，使用する論理チャネルの数を少なくする．
z 処理速度の都合上，多くのチャネルから同時にデータを受信できない．
これまで，待ち時間を効率的に短縮するAHB(Asynchronous Harmonic Broadcasting)法があったが，使用チャネル数が膨大になる[9]．そこで本稿では，使用チャネル数を調整できるようにAHB法を改良する．幾つかの改良方法が考えられるため，4個の改良手法について，各手法の性能評価を行う．筆者らは，これまで，幾つかの手法を提案してきたが，使用チャネル数について評価・考察したものはなかった[9,10]．評価の結果，使用チャネル数について，多いほど平均待ち時間を短縮でき，各チャネルの帯域幅を等しくする手法が平均待ち時間を効率的に短縮することを確認した．放送システムを作成する際の使用チャネル数および帯域幅決定の指標になり，十分な意義がある．以下，2章で関連研究について説明し，3章で改良手法を説明する．4章で評価を行い，5章で議論を行う．最後に6章で本稿をまとめる．

2. 関連研究HB(Harmonic Broadcasting)法では，連続メディアデー
タをN個の部分に等分割する[5]．分割したデータをセグメン
トと呼び，初めのセグメントから順にS1，…，SNで示す．さらにSi (i=1，…，N )をi個のサブセグメントSi,1，…，Si,iに等分割する．N個のチャネルC1，…，CNを用い，CiでSi,1，…，Si,iを繰り返して放送する．たとえば，MPEG2で符号化された5Mbpsの60分の連続メディアデータを衛星デジタル放送を想定した24 Mbpsの帯域幅を用いて放送する場合，放送ス
ケジュールは図1のようになる[2, 3]．この場合，N=67となり，67個のチャネルが必要になる．
CHB(Cautious Harmonic Broadcasting)法では，Sj ( j=4，…，N )をj-1個のサブセグメントに等分割する[6]．N-1個のチャネルを用い，C1でS1，C2でS2とS3，CkでSk+1 (k=3，…，N-1)を繰り返して放送する．たとえば，HB法と同じ例の場

日本データベース学会 Letters Vol.4, No.3

論文
DBSJ Letters Vol.4, No.3――――――――――――――――――――――――――――――――――――
87.8sec

S1

S1

S1・・・

5.00M
bps

C2 ・・・

S2

S3S2・・・

5.00M
bps

C3 ・・・

S4,1

S4,2

S4,3・・・

1.67M
bps

C40

S41,1・・・

C1 ・・・

S41,2

S41,3

125kbpsTime

図2 CHB法の放送スケジュール例
Fig.2 An example of a broadcast schedule
under the CHB method30.2sec

C1 ・・・

S1S1S1C2 ・・・S2S2S2C3 ・・・

S3

S3

S3C4 ・・・

S4S4

S4S4C5 ・・・

S5S5S5S5C6 ・・・

S6S6S6S6000

S1S2

S1S2S3・・・・・

C6000

S1

S1・・・

95.5kbps

・・・

93.8kbps

S5 ・・・

92.0kbps

・・・

90.4kbps

S3

S4

S699.3kbps

S2 ・・・ 97.4kbps

S2

S3・・・

S4

S5
S6Time827bps

図3 AHB法の放送スケジュール例
Fig.3 An example of a broadcast schedule
under the AHB method
合，放送スケジュールは図2のようになる．この場合，N=41となり，40個のチャネルが必要になる．
AHB法では，MPEG2のGOP(Goup of Pictures)やMP3のフレームといった再生の単位を考慮してスケジューリングすることで，HB法やCHB法より平均待ち時間を短縮している[9]．再生単位ごとにデータを分割するため，使用チャネル数は再生単位と同じ数になる．たとえば，先ほどと同じ例では，放送スケジュールは図3のようになる．再生の単位を0.6秒とすると、その数は6000個になり、使用チャネル数も6000個と膨大になる．
AHB法でプリフェッチを導入したAHB-PB法では，放送帯域が固定のうえで分割するデータサイズを決定し，再生単位をいくつかまとめたものにデータを分割しているが，まとめ方に関する考察が行われていない[10]．本稿では，再生単位のまとめ方が異なる幾つかの手法に対して比較評価を行う点が異なる．

3. 改良手法
従来のAHB法では，再生単位ごとに連続メディアデータを分割するため，使用チャネル数が多くなる．そこで，AHB法を改良し，再生単位をいくつかまとめたものにデータを分割する．使用チャネル数に合わせて分割することで，チャネル数に応じた放送スケジュールを作成できる．チャネル数を任意に変更できる点で，実運用に適した手法といえ，バッファに蓄えられた分割したデータを結合して再生できる機能がクライアントに備われば，実際のVOD(Video on Demand)システムに応用できると考える．

3.1 分割するデータサイズの決定手法
使用チャネル数をN，分割するデータサイズを初めから順2にa1，…，aNとする．分割したデータをセグメントと呼び，Si (i=1，…，N )で表す．サーバは連続メディアデータをSiのデータサイズがaiになるように分割する．使用する帯域幅をB，連続メディアデータの再生時間をD，再生レートをrとする．a1+…+aN=Drとなる．以下に，4種類のaiの決定手法を考案する．
3.1.1 BE-AHB(Bandwidth Equivalent-AHB)法
各チャネルの帯域幅が等しくなるように，aiを以下の式で与える．
(1)(1 + NrB )i −1
BD
ai =N

×

(1 + NrB )N − 1

3.1.2 IE-AHB(Interval Equivalent-AHB)法
各チャネルの放送周期が等しくなるように，aiを与える．
場合分けが多いため，ページの都合上，式は省略する．
3.1.3 SE-AHB(Segment Equivalent-AHB)法
各セグメントのデータサイズが等しくなるように，aiを以下の式で与える．
Dr(2)
ai =N
3.1.4 DE-AHB(Density Equivalent-AHB)法
各セグメントの再生中に受信するデータサイズが等しくなるように，aiを与える．場合分けが多いため，ページの都合上，式は省略する．

3.2 スケジューリング手順
3.1節のいずれかの手法で決定したaiの値を用いて，以下の手順に従って放送スケジュールを作成する．AHB法と同じス
ケジューリング手順ではあるが，読者の理解を深めるため，ここに記述する．
1. 連続メディアデータをデータサイズがa1，…，aNのN個のセグメントS1，…，SNに分割する．
2. N個のチャネルC1，…，CNを用い，C1の帯域幅をb1，Cj( j=2，…，N )の帯域幅bjを以下の式で与える．

bj = aaja +L+ a j −1
r(3)

1
b1 +1

3. CiでSiを繰り返し放送する．ただし，セグメントは途中から受信できないため，S1と同期して受信できるようにSjをS1の放送間隔と同じ間隔で放送できる幾つかのサブセグメントに分割して放送する．
b1の値は使用できる帯域幅に合わせて調整する．たとえば，
MPEG2 で符号化された 5Mbpsの 60 分の動画データ(D=60分， r=5Mbps)を 24Mbpsの衛星デジタル放送(B=24Mbps)
で 3 チャネル用いて(N=3)放送する場合の，各手法の放送スケジュールを図 4 に示す．値が等しくなる部分に濃淡をつけて示している．たとえば，BE-AHB法では、ユーザが時刻t1で受信要求を出すと，クライアントはS1の受信開始から 0.3 秒後のt2から再生を開始することで最後まで途切れずに再生できる．この待ち時間はシミュレーションによって算出される．
S1の再生時間は 217Mbytes×8/5Mbps=347 秒となり，受信にかかる時間より長く，S1の再生終了時刻t3=t2+347 秒となる．クライアントはt3までにS2の初めの部分を受信完了しており，S1の再生終了後も再生を続けられる．

4. 評価
評価には 60 分の連続メディアデータを MPEG2 で符号化した 5Mbps のデータを用い，GOP ごとに再生できるため，

日本データベース学会 Letters Vol.4, No.3

論文
DBSJ Letters Vol.4, No.3――――――――――――――――――――――――――――――――――――
217sec 347sec 903sec

5.00M

S2

8.00M
・・・ bps

S2565M

S3

C3 ・・・

8.00M
・・・ bps

1468M

t1 t2

S1
C1 ・・・ 189M
S1 S1 S1 ・・・ bps
S2・・・ 2.50M
C2 ・・・ S2 (189M)
bps

C3 ・・・

1872M

t3 BE-AHB

335sec1200sec

S3 ・・・ 16.5M
bps

S3

IE-AHB
250sec 355sec 457sec

1200sec

750M

750M

750M

S1 S S S S ・・・ 7.11M
C1 ・・・ 222M
1111bpsS1 S1 S1 S1 ・・・ 17.9M
C1 ・・・ 750M
bps C2 ・・・
C2 ・・・
C3 ・・・

S2(750M)

・・・

S3 (750M)

・・・

SE-AHBS2

3.78M
・・・ bps

S2286M

S3

3.91M
・・・
bps C3
2.19M
bps

・・・

1742M

BE-AHB
IE-AHB
SE-AHB
DE-AHB
改良 HB
改良 CHB

5Average Waiting Time (min)bytes

C2 ・・・

6303sec 303sec303sec

S

1C1 ・・・ 217M
S1 S1 S1 S1 ・・・ 8.00M
bps

13.1M
bps

43

2

1DE-AHB0

図4 改良案手法の放送スケジュール例
Fig.4 Examples of broadcast schedules
under improved methods

1520

BE-AHB
IE-AHB
SE-AHB
DE-AHB
改良 HB
改良 CHB

Average Waiting Time (min)53035

40Bandwidth (Mbps)

45505560

図6 帯域幅と平均待ち時間
Fig.6 Available bandwidth andthe average waiting time

7625

4321Tab.1

表1 各統計値の順位（N =10）
The rank order of each statistic (N =10)

順位123456

平均値
BE-AHB
DE-AHB
SE-AHB
IE-AHB
改良 HB
改良 CHB

最小値
SE-AHB
改良 HB
改良 CHB
DE-AHB
IE-AHB
BE-AHB

最大値
BE-AHB
DE-AHB
IE-AHB
SE-AHB
改良 HB
改良 CHB

分散
BE-AHB
DE-AHB
IE-AHB
SE-AHB
改良 HB
改良 CHB

012345678910111213

Number of Channels

14151617181920

図5 使用チャネル数と平均待ち時間
Fig.5 The number of available channels andthe average waiting time
GOP を再生単位とした．

4.1 使用チャネル数
24Mbpsの帯域幅を用いて放送する場合の平均待ち時間を
図 5 に示す．横軸は使用チャネル数とし，縦軸は平均待ち時
間 と し た ． 使用 チ ャ ネ ル 数が 7 よ り 大 き い 場 合 に は，DE-AHB法においてaiが算出できず，放送スケジュールが作成できないため 7 までしか描かれていない．
ʻ改良HBʼは，使用チャネル数を指定できるように改良したHB法であり，使用する帯域幅に合わせて各チャネルの帯域幅を数倍にしている．たとえば，HB法の放送スケジュールが図 1 のようになる例の場合，改良HB法で 3 チャネル用いて放送すると，
b1=13.1Mbps，b2=6.55Mbps，b3=4.37Mbpsとなる．また，従来のHB法とは異なり，平均待ち時間を短縮するために再生単位に合わせて分割位置を調整している．
ʻ改良CHBʼも，改良HB法と同様に，使用チャネル数を指定できるように改良した手法で，CHB法の各チャネルの帯域幅を数倍して帯域幅を調整し，再生単位に合わせて分割位置を調整している．
グラフより，使用チャネル数について，多いほど平均待ち時間を短縮でき，BE-AHB法が平均待ち時間を最短にすることが分かる．

4.2 帯域幅
10 個のチャネルを用いて放送する場合の平均待ち時間を
図 6 に示す．横軸は帯域幅とし，縦軸は平均待ち時間とした．
帯域幅が 26Mbpsより小さい場合には，DE-AHB法においてaiが算出できず，放送スケジュールが作成できいため 26 からしか描かれていない．このグラフより，使用する帯域幅は多いほど平均待ち時間を短縮でき，ほとんどの場合BE-AHB法が平均待ち時間を最短にすることが分かる．

3

5. 議論
5.1 改良手法と AHB 法の相異点
AHB法では再生単位のデータサイズをa1，…，aNとしているが，改良手法では再生単位をいくつかまとめてa1，…，aNとし，使用可能なチャネル数に合わせデータの分割数を決定している．改良手法では，クライアントが最後まで途切れずにデータを再生できるようになるまでの待ち時間を知る必要があり，AHB法よりも平均待ち時間は長くなるが，使用チャネル数を少なくできる．使用可能なチャネル数はシステムによって異なり，複数のチャネルを論理チャネルで実現する場合には数十，物理チャネルで実現する場合には数個のチャネルを用いると考える．BSデジタルテレビ放送では，スロットと呼ばれる論理チャネルを多くて 22 個，少なくても6 個使用している[1]．地上波デジタル放送では，セグメントと呼ばれる論理チャネルを 13 個使用している[2]．

5.2 各手法の比較
N=10 の場合の待ち時間の各種統計値をまとめて表 1 に示す．値が小さいほど上位に位置している．BE-AHB法は最小値以外の項目については高い性能を示しているが，最小値は最長である．これは，図 7 に示すように，Nが 5 以上の場合，BE-AHB法のC1の帯域幅b1が最小になっており，再生単位を受信完了するまでの時間が最長になるためである．たとえば，初めの再生単位が 300kバイトの場合，N=10 のBE-AHB法
ではb1=2.4Mbpsであるため，このデータの受信に 1 秒かかるが，SE-AHB法ではb1=12.2Mbpsであるため，0.2 秒で受信できる．このため，b1が小さいほど待ち時間の最小値が長いといえる．
IE-AHB 法はいずれの項目においても DE-AHB 法より性能が低いが，各チャネルの放送周期が等しいため，放送する際に各チャネルの送受信タイミングが合わせやすく，簡単なシステムに向いている．
SE-AHB 法は，待ち時間の最小値を最短にしている．ただし，他の項目については BE-AHB 法や DE-AHB 法よりも

日本データベース学会 Letters Vol.4, No.3

論文
DBSJ Letters Vol.4, No.3――――――――――――――――――――――――――――――――――――
25

6. まとめ義久 智樹

Bandwidth of Channel 1 (Mbps)

性能が低い．
DE-AHB 法はいずれの項目においても平均的な性能を示している．
以上より，平均待ち時間を最短にする場合には BE-AHB法，送受信処理を簡単化する場合には IE-AHB 法，待ち時間の最小値を BE-AHB 法より短くする場合には DE-AHB 法，他の性能は低くても最小値を最短にする場合には SE-AHB法が有効であると考える．

Broadcasting, Vol. 43, No. 3, pp. 268-271 (1997).
[6] Paris, J.-F., Carter, S. W., Long, D. D. E.: “Efficient
broadcasting protocols for video on demand”, in Proc. of
the Int. Symposium on Modeling, Analysis andSimulation of Computer and Telecommunication
Systems (MASCOTS'98), pp. 127-132 (1998).
[7] 総務省：“情報通信白書平成 16 年版”，
http://www.johotsusintokei.soumu.go.jp/whitepaper/ja/
h16/pdf/index.html (2004)．
[8] Viswanathan, S. and Imilelinski, T.: “Pyramidbroadcasting for video on demand service”, in Proc. of
the SPIE Multimedia Computing and Networking Conf.
(MMCN'95), pp. 66-77 (1995).
[9] 義久智樹，塚本昌彦，西尾章治郎：“データの分割に関する制約を考慮した連続メディアデータ放送におけるスケジューリング手法”，情報処理学会論文誌：データベー
ス，Vol. 44, No. SIG3(TOD17), pp. 33-42 (2003)．
[10] 義久智樹，塚本昌彦，西尾章治郎：“プリフェッチを伴う連続メディアデータ放送における待ち時間短縮のためのスケジューリング手法”，日本データベース学会Letters，Vol. 4, No. 1, pp. 101-104 (2005)．
[11] Zhao, Y., Eager, D. L., Vernon, M. K.: “Scalableon-demand streaming of non-linear media”, in Proc. ofthe IEEE INFOCOM’04 (2004).

BE-AHB
IE-AHB
SE-AHB
DE-AHB
改良 HB
改良 CHB

2015105012345678910111213

Number of Channels

14151617181920

図7 使用チャネル数とチャネル1の帯域幅（B =24Mbps）
Fig.7 The number of available channels and thebandwidth of channel 1 (B =24Mbps)

再生単位を考慮した手法 AHB 法では，使用チャネル数が膨大になる．しかし，ハードウェアの仕様や，処理の簡単化といった理由から,一般に，使用チャネル数には制限がある．
そこで，本稿では，使用チャネル数を調整できるように AHB法を改良し，評価を行った．評価の結果，表 1 より，使用チャネル数を考慮した手法の中では，各チャネルの帯域幅を等しくする手法（BE-AHB 法）が平均待ち時間の短縮に関して有効であることを確認した．放送システムを作成する際の使用チャネル数および帯域幅決定の指標となる．今後，選択クイズ番組のようにクライアントが再生するコンテンツを選択する場合や，実システムによる評価を考えている．

[謝辞]
本研究は，文部科学省21世紀COEプログラム「ネットワーク共生環境を築く情報技術の創出」，および科学研究費補助金(基盤研究(B)(2))「大規模な仮想空間システムを構築する放送型サイバースペースに関する研究」(プロジェクト番号：15300033)の研究助成によるものである．ここに記して謝意を表す．

[文献］[1] 映像情報メディア学会：“デジタル放送局システムのしくみ”，オーム社，東京 (2001)．
[2] 橋本和彦：“ディジタル衛星放送の技術と動向”，電子情報通信学会誌，Vol. 81, No. 1, pp. 86-88 (1998)．
[3] 藤原洋：“最新MPEG教科書”，マルチメディア通信研究会，アスキー出版局，東京，p. 152 (1997)．
[4] Janakiraman, R. and Waldvogel, M.: “Fuzzycast:efficient video-on-demand over multicast”, in Proc. of
the IEEE INFOCOM’02, pp. 920-929 (2002).
[5] Juhn, L.-S. and Tseng, L. M.: “Harmonic broadcastingfor video-on-demand service”, IEEE Trans. on4

Tomoki YOSHIHISA

2002 年大阪大学工学部電子情報エネルギー工学科卒業．
2003 年同大学院情報科学研究科マルチメディア工学専攻博士前期課程修了．2005 年同専攻博士後期課程修了後，京都大学学術情報メディアセンター助手となり，現在に至る．博士（情報科学）．地上波デジタル放送に興味をもつ．日本データベース学会正会員，情報処理学会，電子情報通信学会，各会員．

塚本 昌彦

Masahiko TSUKAMOTO

1987 年京都大学工学部数理工学科卒業．1989 年同大学院工学研究科博士前期課程修了．同年，シャープ（株）入社．1995年大阪大学大学院工学研究科情報システム工学専攻講師，
1996 年同専攻助教授，2002 年同大学院情報科学研究科マルチメディア工学専攻助教授，2004 年神戸大学工学部電気電子工学科教授となり，現在に至る．工学博士．NPO 法人ウェアラブルコンピュータ研究開発機構の理事長を務める．ウェアラブルコンピューティング・ユビキタスコンピューティ
ングに興味を持つ．ACM，IEEE など 8 学会の会員．

西尾 章治郎Shojiro NISHIO

1975 年京都大学工学部数理工学科卒業．1980 年同大学院工学研究科博士後期課程修了．工学博士．京都大学工学部助手，大阪大学基礎工学部および情報処理教育センター助教授，大阪大学大学院工学研究科情報システム工学専攻教授を経て，2002 年より同大学院情報科学研究科マルチメディア工学専攻教授となり，現在に至る．2000 年より大阪大学サイバーメディアセンター長，2003 年より大阪大学大学院情報科学研究科長を併任．この間，カナダ・ウォータールー大学，ビクトリア大学客員．データベース，マルチメディアシステムの研究に従事．現在，Data & Knowledge Engineering などの論文誌編集委員．本学会監事，情報処理学会フェロー，電子情報通信学会フェローをはじめ，ACM，IEEE を含め 8 学会の会員．

日本データベース学会 Letters Vol.4, No.3