1. No category

2014/5/31
Higashino Lab.
効率的な車両間情報共有のための
V2Xコンテンツ配送スケジューリング
安達 佳明*1，梅津 高朗*2 ，山口 弘純*1 ，東野 輝夫*1
*1 大阪大学 大学院情報科学研究科
*2 滋賀大学 経済学部
1
2014/5/31
Higashino Lab.
研究背景

スマートフォンや車載器カメラが撮影した映像の車両間共有
サービスの登場


渋滞，交通規制，雪道などを撮影した映像を車両間で共有
ドライバーは渋滞の回避，運転時間の短縮，安全な経路の選択など
に映像を活用
コンテンツは
サーバが管理
先行車が撮影した映像
３G/LTE
先行車が撮影
カーナビに表示
ドライバーは経路を判断
この先の交通状況を詳細に知りたい
実際にパイオニア社は3G回線を用いてCyberNaviで同様のサービスを運用中
2014/5/31
2
1
2014/5/31
Higashino Lab.
現状の問題点と考えられる対策

問題：サイズの大きなコンテンツは携帯電話網に負荷がかかる
サービスの普及には携帯電話網(3G)だけでは困難


アプローチ：車車間DTN通信を併用して携帯の負荷を軽減

車車間通信：車両間の無線アドホック通信

標準規格：WAVE/DSRC
 路車間通信，車車間通信で利用可能な通信プロトコル
 身近なところではETCで利用

自動運転の登場により再注目されており，近隣の情報を局所的に共有可能
3
2014/5/31
Higashino Lab.
車車間DTN通信の課題

車車間DTN通信では特定時刻までに，特定車両にコンテンツ
を届けることは難しい（可用性の課題）

車両がコンテンツを欲しいタイミングに取得できないこともあり得る
高コスト
高コスト
転送
もう欲しくない
遅延
転送
転送
通信容量
遅延
到達しない
2014/5/31
携帯電話通信：3G
車車間通信(WAVE/DSRC)を用いたDTN
必要な交換を判断し，最も効率良く交換を行うための
スケジューリングをすることでこの課題をある程度克服
4
2
2014/5/31
Higashino Lab.
携帯電話網と車車間DTN通信のメリットとデメリット


携帯電話網：広域通信のため，コストは高いが使いやすい
車車間DTN通信：狭域通信のため，使いにくいが拡張性に優
れる
携帯電話網
車車間DTN通信
通信コスト
△
○
通信の可用性
（どこでも通信可能か？）
◎
△
通信の確実性
（成功しやすいか？）
○
△
それぞれの課題を補い，効率の良い情報共有システムを目指す
5
2014/5/31
Higashino Lab.
研究目的と研究内容

研究目的


車へ少ない通信コストで，確実に多くのコンテンツを配送したい
研究内容
遭遇確率を用いた通信コストを最適化するコンテンツ交換のスケジューリング
 車両間の確率的な遭遇予測を元に，
コンテンツ交換のモデルを整数線形計画問題として定式化
 問題をリアルタイムに解くためのアルゴリズムを提案
車両の移動予測
VICS情報など
コンテンツ
携帯電話通信
例えば：遭遇確率が高ければ
要求車
サーバ
中継車
保持車
2014/5/31
車車間通信を用いたDTN
予測より最適な交換をリアルタイムに計算する必要
6
3
2014/5/31
Higashino Lab.
想定するシステムの概要
どのコンテンツを，誰から誰に，
いつ，どこで，どのように渡すか
車両移動予測
コンテンツ交換
スケジューリング
VICSなど
混雑把握に利用
コンテンツ管理
生成・削除
インデックス
スケジュール指示
一部のコンテンツ
車両情報
コンテンツ
コンテンツインデックス
位置情報
一部のコンテンツ
3G
コンテンツ
コンテンツ（映像）
WAVE/DSRC
コンテンツ
2014/5/31
保持
7
生成
交換・中継
Higashino Lab.
スケジューリング問題の入出力

車両の移動予測
車両が定期的に送信する位置から計算した150秒程度の移動確率
 地図をセルに分割し，時刻τのセルgへの移動確率P(i,g, )
入
力

コンテンツの要求とデッドライン




各通信の通信容量

出
力

数百m
移動確率P(i,g, )より計算
要求：セルへの到達確率
デッドライン：セルへの到達時間の期待値
1セルで1時刻に交換できるコンテンツ数
スケジュール

0.2
0.6 0.1
0.1
セル内の数字はある時刻τの移動確率
コンテンツを交換する時刻，場所，コンテンツID，車両
2014/5/31
8
4
2014/5/31
Higashino Lab.
スケジューリング問題の定式化 (1)

車車間通信によるDTNとサーバを介した携帯電話通信
コンテンツの保持
h(i,c, τ)：時刻τ において
ノードi がコンテンツc を保持
要求の満足
z(i,c) : ノードi がコンテンツc を
デッドラインD (定数)までに保持
コンテンツ
サーバ
車両がある場所で
コンテンツを作成
要求車
中継車
保持車
要求車はコンテンツをその場所に
到達するまでに受け取りたい
コンテンツの交換
t(i,j,c,g,τ):時刻τ ，場所(セル)g において
ノードi からノードj へコンテンツc の交換
9
2014/5/31
Higashino Lab.
スケジューリング問題の定式化 (2)

入力





R(i,c)
D(i,c)
要求
デッドライン
t(i,j,c,g,t)
通信の有無
制約式（一部抜粋）

∑
, ,
,
, ,



,
,
デッドラインまでにコンテンツを取得
, ,
, , , ,
2ノードの遭遇
k(・) は2値化関数
,


移動確率
通信容量
出力


P(i,g, )
Bs(g, )
∑,
, , , ,
,
通信容量内で通信
通信方法ごとに設定
目的関数

max ∑,
,
満足度：利益
2014/5/31
∑,
, , ,
, , , ,
通信：コスト
wz，wt : 結合の重み
wij : 通信の重み
実際のシステムではリアルタイムに解く必要がある
10
5
2014/5/31
Higashino Lab.
スケジューリングアルゴリズム

スケジューリング問題は整数線形計画問題

ノードの組合せ数は膨大



例えば4km × 4km に車は1000台以上いることも
その中からリアルタイムに最適な経路を選択しなければならない
コンテンツ単位で逐次的にスケジュールを求める

計算するノードをコンテンツの保持車，要求車，中継車（サーバ含む）
に限定
サーバの計算リソース
コンテンツ
C1
C2
数秒
スケジューリング
C3
C4
C5
時刻
次々とスケジューリング
この際，通信容量を更新
11
2014/5/31
Higashino Lab.
シミュレーションによる評価 - 環境 
評価の内容


スケジューリングアルゴリズムを用いたコンテンツ交換の効率
評価環境


交通流の生成：Vissim
ネットワークシミュレーション：Scenargie



評価対象




スケジュール計算：CPLEX （Scenargie内部で利用）
電波伝搬モデル： ITU-R_P.1411
格子状の道路環境を想定（15×15, 1リンク200m）
シミュレーション時間：1時間
シミュレーションマップ
発生車両台数：約13000台（うち1, 5, 10, 15%がシステム参加車と仮定）
想定プロトコル

車車間通信:IEEE802.11p （300ms間隔で要求リストをブロードキャスト）

携帯電話通信：通信帯域のみ制限した理想的なモデル


2014/5/31
通信範囲：最大300m，送信レート：3Mbps
送受信レート:500kbps
12
6
2014/5/31
Higashino Lab.
シミュレーションによる評価 – 評価方法 
車両にコンテンツを要求させ，配送率と携帯トラフィックを比較する

車両は自身が将来行くセルのコンテンツを要求

評価の為，要求はVISSIMの軌跡情報から作成
コンテンツは生成から5分ほど有効
コンテンツ
120秒
150秒
車両はセルへの到達時間が120s～150s以内のコンテンツを要求

コンテンツ配送の条件
 要求コンテンツのセルへの到達30秒前をデッドラインとする
 配送率 = コンテンツ配送数 / コンテンツ要求数
13
2014/5/31
Higashino Lab.
シミュレーションによる評価 –配送率評価指標


コンテンツの配送数と配送率
約21%の
コンテンツを
車車間通信で
取得
100%
結果
14000
コンテンツの配送数
12000
80%
10000
8000
60%
6000
40%
4000
20%
2000
0%
0
1%
2014/5/31
配送率

携帯による配送数
提案手法の配送率
5%
10%
システム参加率
15%
V2Vによる配送数
携帯のみのシステムの配送率
14
7
2014/5/31
Higashino Lab.
シミュレーションによる評価 –トラフィック量
評価指標

配送コンテンツあたりの携帯電話通信の総トラフィック量
（アップロードとダウンロードのトラフィック）
通信量を
結果
16%程度削減
4500
20%
4000
16%
3500
3000
12%
2500
2000
8%
1500
1000
削減率
配送コンテンツあたりの
携帯電話のトラフィック[kbytes]

4%
500
0
0%
1%
5%
10%
システム参加率
15%
1コンテンツあたりのトラフィック
2014/5/31
削減率
15
Higashino Lab.
シミュレーションによる評価 –計算時間–
評価項目



計算時間とスケジュール上のコンテンツ配送数
1コンテンツあたり17台ほどが要求
結果
配送数は同程度
80
45
40
35
30
25
20
15
10
5
0
計算時間[s]
70
60
50
40
30
20
10
0
1
2
3
4
5
6
7
8
一度に計算するコンテンツの種類
全計算の計算時間
2014/5/31全計算の配送数
9
10
提案手法の計算時間
提案手法の配送数
スケジューリング上での
配送数

提案手法は
１コンテンツずつ
解くため，線形に増加
16
8
2014/5/31
Higashino Lab.
まとめと今後の課題

まとめ

車車間DTN通信と携帯電話網を用いたコンテンツ交換のスケジューリ
ングアルゴリズムを提案

提案手法により，最大21%のコンテンツ交換を車車間DTN通信により
実現



車両間の遭遇予測を利用
携帯電話通信の総通信量の約16%程度を削減
今後の課題


プローブデータでの検証
路車間通信を考慮したスケジューリング
2014/5/31
17
9