セルラーネットワークとアドホックネットワークを併用した BitTorrent風動画

セルラーネットワークとアドホックネットワークを併用した
BitTorrent 風動画広告配信手法
花野博司†
村 田 佳 洋 ††
安 本 慶 一†
伊 藤
柴 田 直 樹
実†
†††
近年，携帯端末に動画コンテンツを配信するサービスが提供されている．その一つとして動画広告
を配信する場合，ユーザのコンテキストにあった広告を配信すると高い広告効果が期待できる．しか
し動画配信に利用できる帯域幅には制限があるため，多数のユーザがそれぞれ多様なコンテンツを要
求すると，それらすべてを満足する配信を行うことは困難となる．本研究では，多数のユーザの多様
なコンテンツ要求に対応できる動画広告配信を行うことを目的として，セルラーネットワークとアド
ホックネットワークを併用した動画広告配信手法を提案する．提案手法では，近隣の端末同士が協力
して効率的にダウンロードするためにファイルを断片に分割し，近隣の端末と交換することで基地局
以外からのファイルの入手を可能とする．これにより，基地局を経由した通信の頻度を低くできる．
多数の端末が存在する時にもうまく動作させるため，サーバによる集中制御は行わず，各端末が自律
的・確率的に取るべきアクションを決定するアルゴリズムを提案する．
Video Advertisement Delivery Method based on BitTorrent
through Both Cellular Network and WLAN-based Ad-Hoc Network
Hiroshi Hanano ,† Yoshihiro Murata ,†† Naoki Shibata ,†††
Keiichi Yasumoto † and Minoru Ito †
In this paper, we propose a video advertisement delivery method through both cellular
network and WLAN-based ad-hoc network to accommodate many users’ various requests.
In recent years，video delivery services are provided for cellular phone, and high advertising
effect can be expected by delivering advertising video according to the context of users. But,
due to bandwidth limitation of cellular network, it is difficult to deliver various video advertisements to many users. We propose a method which splits a file into pieces and lets each
node exchanges the pieces with neighbor nodes. By doing this, nodes can get part of files
via ad-hoc network and reduce usage of cellular network. In order to make the method work
effectively in dense node situations, we propose a probabilistic algorithm for mobile nodes
without a central control.
1. は じ め に
コンテンツの配信を要求すると，セルラーネットワー
クの電波資源を圧迫し，すべてのユーザに満足の行く
近年，携帯端末に動画コンテンツを配信するサービ
配信を行うことは困難となる．そのため，多数のユー
スが提供されている．その一つとして動画広告配信が
ザが多様な動画広告を要求する環境において，効率的
注目を集めている．動画広告配信において，高い広告
な動画広告配信手法が必要となる．現在行われている
効果を得るためにはユーザのコンテキストにあった動
待ち受け画面へのヘッドライン広告はセルラーネット
画の配信が重要となる．動画配信に利用できる帯域幅
ワークのみを通して配信されており，またコンテキス
には制限があるため，多数のユーザがそれぞれ多様な
トアウェアではない．セルラーネットワークの帯域は
† 奈良先端科学技術大学院大学 情報科学研究科
Graduate School of Information Science, Nara Institute
of Science and Technology
†† 広島市立大学 情報科学研究科システム工学専攻
††† 滋賀大学 経済学部情報管理学科
Department of Information Processing and Management, Shiga University
限られているため，同じ方法で多種多様な要求が発生
し，また必要な転送量の大きいコンテキストアウェア
な動画広告配信を行うことは困難である．
本稿では，多数のユーザの多様なコンテンツ要求に
対応できる動画広告配信を行うことを目的として，セ
ルラーネットワークとアドホックネットワークを併用
した動画広告配信手法を提案する．本稿では，多数の
アドホックネットワークのみを使用したものである．
ユーザが居る都市を対象とし，ユーザのコンテキスト
そのため端末同士の通信範囲が限られており，広域に
(スケジュールや生活パターン) によって端末が自動的
情報を伝えるのは伝達率などの面で実用上問題がある
に受信したいコンテンツとデッドライン (受信期限) を
と考えられる．
設定する．ユーザの携帯電話がセルラーネットワーク
とアドホックネットワークを同時に使用できる場合に，
セルラーネットワークの使用をできるだけ抑えつつ各
ノードが必要なコンテンツをデッドライン内に受信す
る方法を提案する．
提案手法を評価するために都市環境を模したシミュ
3. 提 案 手 法
本章では，提案手法の概要と問題設定について述べ
る．さらに，提案手法の詳細について説明する．
3.1 概
要
提案手法では，以下の 3 つの基本方針を採用する．
レーションによる評価実験を行った．その結果，デッ
(1) セルラーネットワークの通信帯域をできるだけ抑
ドラインを守った上でアドホックネットワークの併用
えるために，アドホックネットワークを併用してセル
によりセルラーネットワークの使用を最大約 52%抑え
ラーネットワークから得たコンテンツを端末同士で交
られた．
換する．(2) 多数の端末が存在する場合，集中制御で
2. 関 連 研 究
各端末の動作を決定すると，サーバの負荷，サーバと
の制御メッセージの量が増大し，スケーラビリティの
ユーザのコンテキストに合わせた動画広告配信を行
確保が難しくなる．これを改善するために各端末が自
いたい場合，同時に配信される動画の数が多数にな
律的・確率的に取るべきアクションを決定する．(3)
る．このためセルラーネットワークだけでは帯域が足
端末同士でコンテンツを交換する際にコンテンツの
りない．
ファイル全体を交換の単位にすると，完全なコンテン
セルラーネットワークの使用コストを抑えたり，通
ツを持っている端末しか貢献できない．コンテンツの
信帯域を補うためにアドホックネットワークを併用す
任意サイズの断片をブロードキャストできる様にす
る研究が行われている．Hongyi らはセルラーネット
ると，通信に係る手順が複雑になってしまう．そこで
ワークのセルが混雑する場合にアドホックネットワー
BitTorrent のようにコンテンツを同一サイズの断片
クを経由して隣接する軽負荷のセルを利用するシス
に分割し端末同士で交換する．
テムを提案している2) ．また，Haiyun らは 3G セル
ある端末がセルラーネットワークでダウンロードし
ラーネットワーク (1xEV-DO3) ) に IEEE802.11b に
た断片を他の端末がセルラーネットワークでダウン
よるアドホックネットワークを統合することで低デー
ロードすると重複して非効率である．これを解消する
タレートのユーザにもサービスを提供しつつセル全
ために何らかの方法で近隣の端末の需要を把握し，需
体の帯域を向上させる研究を行っている4) ．具体的に
要の多い断片を優先的にブロードキャストすることが
は基地局から通信品質の悪い端末へのパケットを通信
望ましい．そこで提案手法では，端末のアクション決定
品質の良い端末 (Proxy) に中継させている．しかし，
アルゴリズムにおいて他端末と情報を交換するフェー
両研究共に他端末がダウンロードするためにセルラー
ズ (情報交換フェーズ) と端末がアクションを決定す
ネットワークとアドホックネットワークを使って自端
るフェーズ (アクション決定フェーズ) を用意する．
末に関係の無いデータを中継している．
情報交換フェーズではアクション決定に必要な情報
Seung-Seok らは 3G セルラーネットワークとアド
を交換するために需要情報と断片情報を格納したハ
ホックネットワークを併用した場合に発生する誰がど
ローメッセージを各端末が定期的にブロードキャスト
のコンテンツをダウンロードしたか分かってしまうと
する．ハローメッセージを受信した端末は確率的に効
いう匿名性の問題を解決するための手法を提案してい
率的なアクションを取るためにその情報を蓄積する．
る5) ．しかし匿名性確保のためにオーバーヘッドが増
端末が取るアクションには，(1) 近隣に存在しない断片
大しダウンロード完了までの時間が長くなってしまう．
を得るためにセルラーネットワークでダウンロードす
Sundaram らは携帯端末で効率的にファイルの交換
るアクションと (2) 自分が持っている断片を近隣端末
を行うために P2P である BitTorrent の仕組みをア
と共有するためにアドホックネットワークでブロード
ドホックネットワークに実装した6) ．端末の移動性や
キャストするアクションがある．アクション決定フェー
ファイル断片サイズの検討が行われネットワークの分
ズでは，情報交換フェーズで得られた情報から自律的・
断にも強いことが述べられている．しかしこの手法は
確率的にアクションを決定する．電波資源を有効に使
うためにセルラーネットワークからある断片をダウン
ズについて述べる．
ロードする場合はその断片を必要としている端末数に
情報交換フェーズ
依存した確率でダウンロードする．すなわち，各断片
端末がアクションを決定するためには
について欲しがっている端末が多ければ確率を下げ少
• 端末の需要情報
なければ確率を上げる．例えば図 1 では 2 台の端末が
• 端末が所持している断片情報
コンテンツ A の同じ断片をダウンロードしているが，
といった情報が必要である．需要情報は端末がどのコ
提案手法では効率を改善するために図 2 の様にそれぞ
ンテンツをダウンロードしたいか，断片情報は端末が
れ異なる断片をダウンロードする様にする．
どの断片を所持しているかという情報である．これら
の情報を近隣端末に知らせるために図 3(a) の様にハ
ローメッセージとして定期的にブロードキャストする．
ハローメッセージを受け取った端末は確率的に効率的
なアクションをとるために図 3(b) の様にその情報を
図1
非効率的なセルラーネットワークの使用
蓄積する．
図 2 効率的なセルラーネットワークの使用
(a) 送信するハローメッセージ (b) 蓄積したハローメッセージ
ブロードキャストする場合も同様に断片を持ってい
図3
ハローメッセージ
る端末数に依存した確率でブロードキャストを行う．
すなわち，各断片を持っている端末が多ければ確率を
アクション決定フェーズ
下げ，持っている端末が少なければ確率を上げる．
近隣で高々1 台の端末がセルラーネットワークから
3.2 問 題 設 定
ダウンロードし，ブロードキャストするために，各ア
都市に多数のユーザの携帯端末 U = {u1 , u2 , · · · , un }
クションをとる確率をコントロールする．蓄積したハ
が存在し，端末がセルラーネットワークとアドホック
ネットワークを使用できる環境を想定する．
ユーザのスケジュールや生活パターンに合わせて，
端末が自動的に受信したいコンテンツを決定し，各コ
ローメッセージから分かる，ある断片 s を望んでいる
端末数を Nw (s) とするとセルラーネットワークから
その断片をダウンロードする重み wc (s) を式 1 により
決定する．
例えば映画を見に行くスケジュールを登録すると，自
1
(1)
Nw (s)
それぞれの端末がダウンロードした断片を欲しがっ
動的に映画のトレーラが選択され，デッドラインが行
ている他端末と共有するためにアドホックネットワー
きの電車に乗るまでに設定される．
クで断片をブロードキャストする．各端末がブロード
ンテンツに対してデッドライン(受信期限) を設定する．
wc (s) =
コンテンツは多数存在し，コンテンツの集合を C =
キャストする断片の重複を減らして効率を改善する
{c1 , c2 , · · · , cm } と表す．端末 ui が受信したいコンテ
ために任意の断片について近隣で高々１台の端末がブ
ンツの集合を ui .Req = {ui .req1 , ui .req2 · · · , ui .reqj ,
ロードキャストする様に，各断片を送信する確率をコ
· · · } ⊂ C ，受信したいコンテンツ ui .reqj に対する
ントロールする．蓄積したハローメッセージから分か
デッドラインを ui .reqj .deadline とする．デッドライ
る，ある断片 s を持っている端末数を Nh (s) とする
ンまでにコンテンツが受信できているとユーザに動画
とその断片をブロードキャストする重み wb (s) を式 2
広告を提示できる．
により決定する．
以上の情報が事前に与えられるとした場合に，各
ユーザ端末が他端末と協力してデッドライン内にダウ
ンロードが完了し，かつセルラーネットワークにより
ダウンロードされるデータ量 (セルラーネットワーク
利用コスト) を最小化するという問題を扱う．
3.3 詳
細
以下では，アクション決定アルゴリズムの各フェー
1
(2)
Nh (s)
各瞬間において，各端末は複数の断片について考え
wb (s) =
る必要がある．そこで，どの断片についてアクション
を起こすかを決定するために上記確率を重みとした
ルーレット選択を用いる．ルーレット選択では重み wi
の断片を選択する確率 ps は式 3 になる．
wi
ps = ∑N
w
k=1 k
値を計測した．
(3)
近隣端末との協調のためには，自端末が常にネット
ワークを使うことはできない．そこで上記 2 つのアク
ションを取らなかった時は何も行わない．
• シミュレーション時刻
• セルラーネットワークからダウンロードした断片
数の全端末平均
• ダウンロード率の全端末平均
端末 ui のダウンロード率 d(ui ) は，端末 ui が必
疑似コード
要としているコンテンツの全ての断片数 Ns (ui ) のう
情報交換フェーズとアクション決定フェーズの疑似
ち，セルラーネットワークとアドホックネットワーク
コードをリスト 1，2 に示す．2 つのコードはマルチス
送信したタイミングから一定時間が経つとハローメッ
を使って得た断片数を Nd (ui ) とすると式 4 になる．
Nd (ui )
× 100
(4)
d(ui ) =
Ns (ui )
全体のコンテンツ数は 4 種類で，1 つのコンテンツ
セージを再送する．アクション決定フェーズでは断片
は 1000 個の断片に分かれている．1 つの断片を 1.5kB
が送られてくるのを待ち続ける．セルラーネットワー
とし，コンテンツを 1.5MB とした．端末はコンテン
クとアドホックネットワークの使用割合を調整するた
ツ集合から 2 つのコンテンツをランダムに選択しダウ
めに確率 alpha と beta を導入し，確率 alpha でルー
ンロードする．デッドラインは全て 10 分とした．
レッドで並行して動作する．情報交換フェーズではハ
ローメッセージを待ち続け，前回ハローメッセージを
レット選択で選択した断片をセルラーネットワークで
セルラーネットワークの帯域制約を模するために 1
ダウンロードする．また，確率 beta でアドホックネッ
つの基地局は最大 64 台までの端末が同時に接続でき，
トワークを使ってルーレット選択で選択した断片をブ
上限に達している場合は接続できないこととした．接
ロードキャストする．
続できると 10 ミリ秒間通信を行い，断片をダウンロー
リスト 1 情報交換フェーズ
ドする．これはセルラーネットワークの通信速度を式
5 の様に 1.2Mbps としたためである．
1000
× 1.5kB × 8bit = 1.2M bps
(5)
10
端末のアドホックネットワークの通信距離は 200m
とし，減衰モデルとして仲上分布を用いた7) ．送信者
リスト 2 アクション決定フェーズ
と受信者の距離 d の 4 倍が crossover distance(=556,
CR) 以下の場合，受信確率 PR は式 6 になり，CR よ
り大きい場合式 7 になる．これをグラフに示すと図 4
の様になる．
4d
2
PR = e−3( CR ) (1 + 3(
PR = e−3γ(
4. 実
(4d)2 2
)
CR
4d 2 9 4d 4
) + (
) )
CR
2 CR
(1 + 3γ(
(6)
(4d)2 2 9 2 (4d)2 4
) + γ (
) )
CR
2
CR
(7)
験
デッドラインを満たした上で如何にセルラーネット
ワークの使用を抑えられるかを評価するために都市環
境を模したシミュレーションによる評価実験を行った．
4.1 シミュレーション実験の設定
図4
距離に対する受信確率
実験には独自に作成したシミュレータを用い，1 ミ
リ秒ごとにシミュレーションを行い 1 秒ごとに以下の
アドホックネットワークでブロードキャストする場
合一度に 6 ミリ秒間通信を行う．これはアドホック
ネットワークの通信速度を式 8 の様に 2Mbps とした
ためである．
1000
× 1.5kB × 8bit = 2M bps
(8)
6
アドホックネットワークでブロードキャストする場
合，通信中に他端末の電波が重なると衝突が発生する．
この衝突を模するために 2 つの通信範囲が重なる領域
の端末はそのパケットを受信できないこととした．ま
た，端末は CSMA/CA(Carrier Sense Multiple Ac-
cess/Collision Avoidance) が使用でき他端末の電波
を検出した時はアドホックネットワークを使用しない．
4.2 実 験 方 法
図 5 アドホックネットワーク使用率 β を変化させた時のダウン
ロード率の遷移 (500m 四方)
シミュレータの以下の 2 つのパラメータを変化させ
て効率を評価する．
• セルラーネットワーク使用率α
自端末がセルラーネットワークを使用していない
時にセルラーネットワークを使用する確率
• アドホックネットワーク使用率β
自端末がアドホックネットワークを使用する確率
α = 0.001 から 0.003 まで 0.001 刻み，β = 0.0005
から 2 倍ずつ 0.002 まで変化させて (1)500m 四方
に端末をランダムに 250 台配置した密度が高い時と
(2)1000m 四方に端末をランダムに 250 台配置した密
度が低い時について実験を行った．また，セルラー
ネットワークのみを使用した場合 (α = 1.0，β = 0.0)
も実験を行った．端末のハローメッセージ送信間隔は
3±0.1 秒とし，自端末は前回送信時からこの間隔が過
ぎていればハローメッセージを送信する．
4.3 実 験 結 果
パラメータを変化させた時のダウンロード率の平均
の遷移を図 5，6 に示す．α を大きくするとダウンロー
ド率の向上が早くなり，ダウンロードが早く完了した．
これはセルラーネットワークからのダウンロードが多
く行われ，断片の流通が早くなったためと考えられる．
β を大きくするとダウンロード率が改善するが大きく
しすぎると衝突が増えてダウンロード率が悪化した．
図 5，6 で立ち上がりに対してダウンロード完了直
前で収束が遅くなっていることが分かる．これは，近
隣の端末が断片を持っておりセルラーネットワークを
使用しなかったためと考えられる．また，欲しい断片
の残りが少なくなりブロードキャストされてくる断片
が自端末の欲しい断片と合致する確率が下がるためと
考えられる．
パラメータを変化させた時の全端末のダウンロード
完了時間とシミュレーション終了時点でのダウンロー
ド完了端末数を表 1 に示す．この結果から，端末の
図 6 アドホックネットワーク使用率 β を変化させた時のダウン
ロード率の遷移 (1000m 四方)
密度が高い方が全端末ダウンロード完了時間が改善し
た．また，全端末がダウンロード完了できない場合で
もデッドライン内に完了している端末数が多くなった．
これは密度が高いためアドホックネットワークで断片
を受け取る端末が多くなり各端末が多くの端末に貢献
できるためと考えられる．
図 7，8 にシミュレーション終了時のセルラーネット
ワークとアドホックネットワークの使用割合を示す．α
を大きくするとセルラーネットワークの使用割合が大
きくなった．α をさらに大きくしていくとダウンロー
ド完了時間は早くなるが使用割合も増大し帯域を消費
する．α を小さくしていくとダウンロード完了時間は
遅くなるが使用割合を減らすことができる．アドホッ
クネットワークを併用して全端末がデッドラインに間
に合った中では 500m 四方で α = 0.002，β = 0.001
の時に約 52%，1000m 四方で α = 0.003，β = 0.002
の時に約 45%，セルラーネットワークの使用割合を抑
えられた．10 分のデッドラインでは間に合わない設
定においても，デッドラインが長く取れる場合にはセ
ルラーネットワークの使用割合をさらに抑えてダウン
ロードが完了できると考えられる．
表 1 パラメータに対する完了時間・完了数の実験結果
フィールド
α
β
完了時間 [msec]
完了端末数
1.000
0.0000
0.0005
0.0010
0.0020
0.0005
0.0010
0.0020
0.0005
0.0010
0.0020
0.0005
0.0010
0.0020
0.0005
0.0010
0.0020
0.0005
0.0010
0.0020
78700
549320
461941
434594
492140
544336
464546
250/250
0/250
4/250
6/250
240/250
250/250
233/250
250/250
250/250
250/250
0/250
0/250
4/250
2/250
196/250
247/250
247/250
250/250
250/250
0.001
500m
四方
0.002
0.003
0.001
1000m
四方
0.002
0.003
図7
各パラメータでの両ネットワークの使用割合 (500m 四方)
図 8 各パラメータでの両ネットワークの使用割合 (1000m 四方)
5. お わ り に
本稿では，多数のユーザの多様なコンテンツ要求に
対応できる動画広告配信を行うことを目的として，セ
ルラーネットワークとアドホックネットワークを併用
した動画広告配信手法を提案した．また，提案手法を
設計しシミュレータに実装し実験を行った結果，デッ
ドラインを守った上でアドホックネットワークの併用
によりセルラーネットワークの使用を最大約 52%抑え
られることが分かった．
今後の課題として，環境に柔軟に適応するために，
現在固定しているアクション決定の確率やハローメッ
セージの送信間隔をハローメッセージの情報を元に動
的に変化させることが考えられる．また，端末の移動
性を考慮した場合の性能を評価するために端末にシナ
リオを持たせ，移動させてシミュレーションすること
が考えられる．さらに，より遠くの端末と協力して効
率を上げるために現状 1 ホップのハローメッセージや
断片のブロードキャストをマルチホップにすることも
考えられる．
参
考
文
献
1) BitTorrent: http://www.bittorrent.com/
2) Hongyi, W., Chunming, Q., Swades, D. and
Ozan, T.: ”Integrated Cellular and Ad Hoc Relaying Systems:iCAR,” Proc. of IEEE International Conference on Communications (ICC)
2001, (2001)
3) 3GPP2, C.S0024, ”cdma2000 High Rate
Packet Data Air Interface Specification”
4) Haiyun, L., Ramachandran, R., Prasun, S., Li,
L. and Songwu, L.: ”UCAN: A Unified Cellular
and Ad-Hoc Network Architecture,” Proc. of
the 9th annual international conference on Mobile computing and networking, pp. 353-367,
(2003)
5) Seung-Seok, K., Matt, W., Mutka and Li,
X.: ”Anonymous Content Sharing in Ad Hoc
Networks,” Proc. of Third IEEE International
Conference on Pervasive Computing and Communications (PerCom2005), (2005)
6) Sundaram, R. and Chien-Chung, S.: ”A Crosslayer Decentralized BitTorrent for Mobile Ad
hoc Networks,” Proc. of the 3rd Annual International Conference on Mobile and Ubiquitous
Systems: Networks and Services (MOBIQUITOUS 2006), CD-ROM, (2006)
7) Killat, M., Schmidt-Eisenlohr, F., Hartenstein, H., Rössel, C., Vortish, P., Assenmacher,
S. and Busch, F.: ”Enabling Efficient and Accurate Large-Scale Simulations of VANETs for
Vehicular Traffic Management,” Proc. of the
4th ACM Int’l workshop on Vehicular ad hoc
networks (VANET2007), pp. 29-38, (2007)