無線 LAN 環境における効率の良いオンデマンドストリーミング配信に関する研究

代表研究者

大坐畠智

電気通信大学

大学院情報理工学研究科准教授

1 はじめに
近年，ノート PC や携帯端末，タブレット端末にも無線 LAN インターフェースが広く搭載されており，無線LAN を通じて動画配信サイト等でのストリーミング配信される機会が増えてきている．しかし，複数の端末が同一の無線 LAN アクセスポイントを使用する時，ユニキャスト通信では帯域を分け合うため通信速度が低下する．そのため無線 LAN 環境において複数端末にコンテンツを効率よく配信する必要がある．
既存の技術として，送信元と送信先が 1 対複数で対応しているマルチキャストがある．また，マルチキャストでは ACK を返す仕様がなく，TCP の再送制御も用いられないため無線リンクなど，リンクの状況が他の端末と比較して悪い端末に対してマルチキャストを行う場合，スループットは最も小さい送信速度の端末に制限されてしまう．この問題に対し，文献[1]の方式ではリンク状態の悪い端末にはユニキャストを用いてデータを送信する事で対応している．さらにユニキャストを効率良く用いてマルチキャスト通信を実現する方式として，疑似マルチキャスト方式[2]-[3]が提案されている．疑似マルチキャスト方式では通信品質の悪い端末に対してユニキャストで通信を行い，そして他の同じコンテンツをダウンロードする端末はユニキャストのフローをオーバヒアすることで同一の通信内容を受信する．疑似マルチキャストはユニキャストを用いるため，MAC の再送制御と TCP の効果的な利用，そして端末側の無線通信状況に応じてユニキャストする端末を選択する事で通信速度の選択も可能となる．しかし，オーバヒアリングの範囲と MAC の通信速度を考慮しつつ効果的な宛先ノードの選択することは難しい．さらに，擬似マルチキャストでも通信はバイトストリームとして行われているため，コンテンツ最初から入手するためにはダウンロードの開始が全ての端末において同時に行われなければいけないという問題もある．
本研究では，無線 LAN 環境における非同期ストリーミング配信にて，クライアントにネットワークコーディングされたピースのキャッシュ機能を追加する事で，ネットワークコーディングピースをキャッシュし復号を行う方式の提案を行う．本研究における課題は，受け取った時点で復号できずに破棄されていたネット
ワークコーディングピースの受信端末によるキャッシュ機能の実装し，そしてキャッシュしたネットワークコーディングピースが復号可能になったとき，それを受信端末側において復号することである．

2 無線 LAN におけるファイルのピース分割とオーバヒアリングを用いた通信方式
2-1 ピース分割とオーバヒアリングを用いた柔軟かつ高速な通信
無線 LAN 環境において従来のマルチキャストを用いた方式では，コンテンツの信頼性を確保するための制御信号がオーバヘッドとなる．また，全ての端末が同期してダウンロードを進める必要があり，複数の端末が異なるタイミングでダウンロードを開始する場合や異なる通信品質である場合に適用する事が難しい．
横瀬ら[5]は，同じコンテンツをダウンロードしている他の端末宛の通信をオーバヒアリングしそのデータを利用する事により，無線ネットワークの帯域を消費する冗長な通信を削減し，多数の端末が効率よくコンテンツを入手する方式を提案した．また，コンテンツのピース分割により異なる通信品質を持った端末が異なるタイミングでダウンロードに参加する場合にも適応する．このとき配信サーバは端末のピースの所持状
況や通信状況などを考慮した送信ピース・送信宛先を選択する．横瀬らの方式の概要図を図 1 に示す．
図 1 は配信サーバが配信するコンテンツのデータをピース 1 から 4 まで分割した時，端末 A にピース 1 と2 を，端末 B に 3 と 4 を TCP で直接送信する．この時，端末 A にピース 1 と 2，端末 B には 3 と 4 のみでコンテンツを完全に受信できたわけではない．そこでそれぞれ TCP で直接送信したものを，もう片一方の端末がオーバヒアリングする事で，端末 A と B がそれぞれ直接受け取らなったピースを得ることが出来る．また，横瀬らのピース配信スケジューリング方式の 1 つにネットワークコーディング[7]を適用した方式がある．

1（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

図 1: ピース分割とオーバヒアリングを用いた柔軟かつ高速な通信

2-2 ピ ー ス 分 割 と オ ー バ ヒ ア リ ン グ を 用 い た 非 同 期 ス ト リ ー ミ ン グ 配 信 方 式
金山らの研究[4]の目的は無線 LAN 内の複数端末での同一ストリーミングコンテンツの視聴における，コンテンツ再生中の中断時間の削減である．横瀬らの研究をストリーミングコンテンツへ適応すると同時に快適に視聴するためのスケジューリング方式についての提案を行っている．ストリーミングコンテンツは再生を始める際にコンテンツ全てをダウンロードしておく必要が無く，かつコンテンツの再生を行いつつその先のダウンロードが可能にしているという点を考慮している．
スケジューリング方式は受信端末を順に決めるラウンドロビン方式，受信端末のピースの受信地点と再生地点が近いものを選択するバッファ重視方式，受信端末ごとのピースの受信率を考慮した効率重視方式の 3
つに加えて，バッファ重視方式と効率重視方式の折衷案を提案されている．はサーバからの配信が始まり，端末情報を受け取った際に再生が停止中の端末が存在するかどうかを探す．いた場合はその端末へ最優先に宛先の受信地点+1 のピースを送信する．複数停止中の端末がいた場合は，バッファ数が最小の端末を優先する．停止中の端末が存在しないとき，事前に設定した閾値未満のバッファを持つ端末がいた場合，その中でバッファが最小の端末に受信地点+1 のピースを送信する．ネットワーク内の端末全てが停止しておらず，かつバッファが閾値以上である場合は，宛先端末はオーバヒア確率が一番低い端末となり，送信されるピースはもっとも拡散されやすいピースが選ばれ送信される．

2-3 オ ー バ ヒ ア リ ン グ を 用 い た コ ン テ ン ツ 配 信 方 式 に お け る ネ ッ ト ワ ー ク コ ー デ ィ ン グ さ れ た
ピースのキャッシュを考慮したスケジューリング方式
先行研究として横瀬らの研究[5]にキャッシュを考慮した方式が提案されている．文献[6]によると文献[5]ではダウンロード開始時刻の違いにおいてネットワークコーディングによるピースの受信数を評価したが，各端末が一定間隔にダウンロードを開始した時，所持しているピースが共通しない場合が多い，符号化ピースを復号するピースを持たない場合が多い，等からネットワークコーディングの効果が得難く，ダウンロード終盤の速度改善となりにくいとされていた．この原因として，符号化ピースを復号可能なピースを持たなかった時，端末側でネットワークコーディングされたピースが破棄されていたことが指摘されている．そのため文献[6]では符号化ピースのキャッシュを考慮したスケジューリング方式を提案した．
図 2 にネットワークコーディングされたキャッシュされなかった時とキャッシュされた時の概要を示す．
図 2〜4 において一番通信状態が悪い端末 C とユニキャスト通信を行い，他の端末はオーバヒアリングによって通信を行う．この時端末 A から C までで要求率の高いピースを配信すると，ピース 4 と 5 を XOR を用いてネットワークコーディングされたピース x が配信される．端末 A と B ではそれぞれピース 4，ピース 5 と xが復号されて所持していないピースを手に入れることが出来るが，端末 C では x を復号するためのピース 4，5 をともに所持していないため復号できない．横瀬らの研究ではこの時復号できないネットワークコーディングピースは破棄されていた．

2（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

図 2: NC されたピースを破棄する場合

図 3:NC されたピース x をキャッシュする場合

図:4 NC されたピース y が届いた時の連鎖復号
しかし小笠原らの研究において，図 3 では端末 C でネットワークコーディングされたピースが復号されなかった時，キャッシュを行う事で，一時的に端末 C でピース x を保持している．図 4 で次に要求率の高いピース 2 と 4 をネットワークコーディングしたピース y が配信された時，端末 B はそのまま復号される．端末
C も元々ピース 2 を所持していたのでピース y を復号し，ピース 4 を手に入れる．この時，キャッシュしていたピース x はピース 4 とピース 5 のネットワークコーディングされたものであるので，新たに手に入れたピース 4 によって更にピース x を復号して，ピース 5 を手に入れる．
結果として，最初復号できなかったピース x をキャッシュしたことでピース 4 とピース 5 の二つのピースを同時に手に入れることができる．

2-4 疑 似 マ ル チ キ ャ ス ト に よ る 非 同 期 ス ト リ ー ミ ン グ 配 信 に お け る キ ャ ッ シ ュ さ れ た ネ ッ ト ワ
ークコーディングピースの有効活用
本研究では金山らの方式[4]に小笠原らの方式[6]のキャッシュ保持機能を加える．金山方式ではネットワ

3（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

ークコーディングを用いていないため，ネットワークコーディングピースのキャッシュ機能を保持していな
い．本研究ではそれぞれの端末が異なるピースを必要としている時，複数のピースにネットワークコーディングとオーバヒアリングを用いて，ネットワーク内の端末へと送信する．ピースを受信した後，通信の種類を問わず，受信した端末でネットワークコーディングピースの復号を試みる．コーディングピースの復号に用いるピースを端末が所持していなかった場合，ピースは復号できないのでそのままキャッシュをし，後のピース配信にて復号可能なピースを得た時に改めて復号を行う．今までストリーミングコンテンツの配信方式において破棄されていたコーディングピースをキャッシュすることで，通信状況などによって受信ピースが歯抜けとなったとき，復号することでバッファを伸ばすことを可能にさせる．
また，金山らの方式ではネットワークコーディングピースを保持していなかったため，新たにピースが届いても，ピースの受信地点にバッファが足りずに再生が中断されてしまうことがある．提案手法を用いて，事前にネットワークコーディングピースをキャッシュすることで受信地点を伸ばし，再生が受信地点に辿り着かなくさせることで，コンテンツの中断回数や中断時間を削減できる．
キャッシュテーブルは配列によって管理され，キャッシュするネットワークコーディングピースを構成するピース番号に基づいて格納する．これによって，新たにピースを取得したときそのピース番号を参照し，ネットワークコーディングピースキャッシュテーブルで該当するインデックスにキャッシュ情報が記されていた場合，復号を行う．キャッシュテーブルは配列によって管理され，キャッシュするネットワークコーディングピースを構成するピース番号に基づいて格納する．図 5 に例を示す．

図:5 ネットワークコーディングピースキャッシュテーブル
図 5 ではその時点では復号されずにキャッシュするネットワークコーディングピースが，ピース番号 1と 2 のピースで構成されている時の状況を示している．ネットワークコーディングピースキャッシュテーブ
ルに格納する際，ピース番号と同じ値のインデックスの要素に任意の数値を格納する．図ではピース番号 1と 2 で構成されたピースが来たとき，キャッシュテーブルのそれぞれのインデックス 1 と 2 に当たる要素に数値を格納する．これによって，新たにピースを取得したときそのピース番号を参照し，ネットワークコーディングピースキャッシュテーブル内に対象ピースと組み合わせられたピースが記録されていた場合，復号を行う．

1.1

実験結果

実験で用いた端末数は 3 台であり，端末 1 を配信サーバ，端末 2 と 3 を受信端末とする．端末配置は端末2 が配信サーバから 2m 程度，端末 3 が配信サーバから 12m 程度の位置とした．実験においてオーバヒアリン
グ，ネットワークコーディングをより発生させやすくするため，配信サーバにより遠い遠くの通信品質が悪い端末に直接ピースを送ることで，近くの端末にネットワークコーディングピースを含めオーバヒアリング

4（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

率を高める目的である．以下に実験結果を示す．
端末 3 のピースの総受信数，受信地点，再生地点の推移を図 6，図 7，図 8 に示す．図 6，7，8 はそれぞれネットワークコーディングを適用しなかった方式，ネットワークコーディングを適用したがキャッシュしていない方式，ネットワークコーディングとキャッシュを適用した方式である．
端末 3 の平均スループットはそれぞれ 11.634Mbps，5.4325Mbps，11.138Mbps となった．ネットワークコー
ディングとキャッシュの両方を適用した評価として，ピースのキャッシュ数は 1094 個，キャッシュしていたネットワークコーディングピースを復号して新たに得たピース数は 547 個確認できた．図 6，図 7 では復号されないネットワークコーディングピースのキャッシュを行っていないため，ピースの総受信数とピースの受信地点はほぼ一致している．しかし図 8 においてピースの受信地点と総受信数に差がある個所は復号されなかったネットワークコーディングピースをキャッシュしている地点であり、受信地点において横軸に対して直角に伸びている箇所は，キャッシュされたピースが復号されたことによって受信地点が急激に伸びている地点である．受信が完了した時間を見ると，それぞれ 68.763 秒，147.26 秒，71.826 秒となった。ネット
ワークコーディングを適用しなかった方式と，ネットワークコーディングとキャッシュの両方を適用した方式がほぼ同様の結果を得られた．
しかし，今回の実験において復号されないネットワークコーディングピースのキャッシュ機能と復号機能における動作は確認できたものの，ネットワークコーディングを用いない方式とほぼ同様の結果となったた
め，サーバ側でネットワークコーディングをより効率的に配信するスケジューリングを考える必要がある．

図 6: 端末 3 における受信状況(ネットワークコーディング無し)

5（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

図 7: 端末 3 における受信状況(ネットワークコーディング有り・キャッシュ無し)

図 8: 端末 3 における受信状況(ネットワークコーディング有り・キャッシュ有り)

6（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

図 9: サーバが送信したピースの総数
図 9 にサーバが各受信端末に送信したピースの総数の推移を示す．それぞれピースの送信数はネットワー
クコーディングを適用しない方式が 877 個，ネットワークコーディングを適用したがキャッシュしていない方式が 2052 個，提案方式が 1207 個となっている．ネットワークコーディングを適用しなかった方式に比べて，提案方式の送信ピース数が多い事が分かる．これはネットワークコーディングとキャッシュ機能・復号機能を適用したことで，復号するためのピースの送信もされているため，ネットワークコーディングを用いない方式よりも送信ピース数が多いと考えられる．通信が終了した時間はそれぞれ図 6，7，8 と同じである．
これにより，提案方式はネットワークコーディングを用いなかった方式と比べて送信ピース数は多いが，同程度の時間で受信が完了していることが分かる．

3 まとめ
本研究では，無線 LAN 環境における疑似マルチキャストを用いた非同期ストリーミング配信において，ネットワークコーディングピースの復号失敗の際に破棄するピースをキャッシュすることで，ネットワークコーディングの効果向上を目指し，バッファリングをより伸ばす方式を提案し，実装，評価を行った．提案方式において，その場で復号することが出来ないネットワークコーディングピースを破棄せずにキャッシュを行い，後に受信したピースを用いて復号を行う．また，キャッシュしたネットワークコーディングピースを復号する事で得たピースを用いて，他にキャッシュしたネットワークコーディングピースの復号によってネットワークコーディングの効果向上，そしてバッファリングの増加を図った．実験の結果，金山らのバッフ
ァリング重視方式にネットワークコーディングを加えた方式で評価した際，キャッシュしたネットワークコーディングピース数、そして復号したことで新たに得られたピースをそれぞれ確認し，新たに 1 つのピースを取得した後で復号することによって，歯抜けだったピースを埋めることができ，受信地点を伸びたことを確認した．
本研究では，宛先端末の選択スケジューリング方式にバッファリングが 一番短い端末を選択し，またネットワークコーディングは，送信ピースが直近 100 回で送ったピースだった場合，受信地点の 2 つ先のピースと行われる方式を採用した．ネットワークコーディングピースのキャッシュ，そして復号することで受信地点を伸ばすことができた点を確認でき，ネットワークコーディングを用いない方式と提案方式でピースの受信完了時間がほぼ同様だったが，サーバが送信した総ピース数は提案方式の方が多く送っていたことが分かった．これらのことから，ストリーミング配信コンテンツにおいて，ネットワークコーディングピースの7（公財）電気通信普及財団 研究調査助成報告書 No.32 2017

キャッシュと復号を有効利用するためには，より多くネットワークコーディングピースを生成し，かつ受信地点を効率よく伸ばせるようなピースの配信スケジューリング方式を考える必要がある．

【参考文献】[1] Holland and H. Aghvami, “Dynamic Switching between One-to-Many Download Methods in“All-IP” Cellular Networks,” IEEE Trans. Mobile Computing, 5 (3), pp. 274–287, 2006.
[2] D. Dujovne and T. Turletti, “Multicast in 802.11 WLANs: experimental study,” Proc. the 9th
ACM MSWiM, pp. 130–138, 2006.
[3] R. Chandra, S. Karanth, T. Moscibroda, V. Navda, J. Padhye, R. Ram-jee, and L.
Ravindranath, “DirCast: A practical and efficient Wi-Fi multicast system,” Proc. of IEEE
ICNP pp.161–170, 2009.
[4] A. Kanayama, S. Ohzahata, T. Kato, “Piece Distribution Scheduling for Streaming Content
Delivery with Pseudo-Multicast over Wireless LAN,” Proc. of IEEE CCNC 2016, 2 pages,2016.
[5] Hiroaki Yokose, Koji Nitta, Satoshi Ohzahata, Toshihiko Kato, “A Practical and Efficient
Overhearing Strategy for Reliable Content Distribution over a Single Hop Ad Hoc Network”
Journal of Information Processing Vol.24 No.1 pp. 1-10, 2016.
[6] 小笠原優, 大坐畠智，加藤聰彦，“オーバヒアリングを用いたコンテンツ配信方式における受信ピースのキャッシュを考慮したスケジューリング方式の検討,” 電子情報通信学会 ソサイエティ大会, BS-3-5, 2015.

〈発題名

疑似マルチキャストによる非同期スト
リーミング配信においてキャッシュされたネットワークコーディングピースの有効活用表資料〉

掲載誌・学会名等

電子情報通信学会

信学技報

発表年月

2017 年 3 月

8（公財）電気通信普及財団 研究調査助成報告書 No.32 2017