[ Invited Paper ]
A Method for
Sharing Traffic Jam Information
using Inter-Vehicle Communication
Naoki Shibara, Takashi Terauchi*, Tomoya Kitani*,
Keiichi Yasumoto*, Minoru Ito* and Teruo Higashino**
Shiga University, JAPAN
*Nara Institute of Science and Technology (NAIST), JAPAN
**Osaka University, JAPAN
The 2nd International Workshop on
Vehicle-to-Vehicle Communications 2006 (V2VCOM 2006), 21 July, 2006
Background


$100 billion/year of economic loss by traffic jam
Existing services for alleviating traffic jam



VICS (Vehicle Information and Communication System)
 A service provided by Japanese government
 Provides traffic jam information of trunk roads
Cyber-Navi (Pioneer)
 An advanced car-navigation system
 Predicts traffic jam from information in the past
Weaknesses of the existing methods



Service area
Operation cost
Time lag / not up-to-date information
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
2
Purpose of the study

Autonomous collection of statistical traffic info.



Using GPS and inter-vehicle communication
No need for costly infrastructures
Prediction of arrival time using the gathered info.


Provides basic car-navigation system functions
Route navigation avoiding congested areas
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
3
Overview of the method (1/2)
The map is divided into areas.
A1
A2
A3
Granularity of area is decided
according to the amount of
traffic and road density.
A4
A5
A6
A7
A8
A9
Cars measure time to pass
through each area using GPS.
Traffic info. can be collected by
exchanging info. between cars.
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
4
Overview of the method (2/2)

Arrival time can be estimated by summing up
time to pass through areas
D
A1
tA2
tA4
tA5 A5
A4
tA7
S
A7
July 21, 2006
A2
A8
tA7’
tA8
tA2’
tA5’
A3
A6
1’20’’
1’40’’
A9
V2VCOM 2006 - N. Shibata et al.
5
Outline

Step 1. Collection of traffic info.





Collecting time to pass through each area
Propagation and retention of collected info.
Avoiding redundant processing of same data
Exchanging data with priorities
Step 2. Estimating arrival time
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
6
Challenges for accuracy
 Distinguishing
time between turning
right/left and going straight is crucial
 Especially, time needed to turn right is
largely influenced by the opposite lane
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
7
Problem of per-link measurement
• How can time to turn right/left and go
straight be distinguished?


Collecting info. on a per-lane basis is hard
Too much data by collecting on a per-link basis
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
8
Per-area measurement
Collecting data for each combination of
incoming and outgoing link

Time to turn at crossings is reflected
Area
border
24 sec
38 sec
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
9
Time to pass through area
Measuring time for each combination of two
links crossing area border
d
c
H
G
b
I
e
F
E
A
a
B
D
C
Red dotted lines are
area borders
Links
(a,b)
(a,e)
....
Measured time
150 sec
220 sec
For the area at the
center, time is measured
for each two
combination of blue
links
Blue links cross area border
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
10
Outline

Step 1. Collection of traffic info.





Collecting time to pass through each area
Propagation and retention of collected info.
Avoiding redundant processing of same data
Exchanging data with priorities
Step 2. Estimating arrival time
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
11
Exchanging info. between cars



When a car crosses area border, it broadcasts its info
When another car receives this info, it adds the info
into its memory
The car continues to broadcast data for some time
Area border
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
12
Retention and disposal of data
• Info. for an area adjacent to the area a car is running
at is retained.
Adjacent areas
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
The original area the
info is generated at
13
Retention and disposal of data
• Info. for an area adjacent to the area a car is running
at is retained.
• When a car goes off from these areas, it disposes the
corresponding data
Here, this car
disposes info.
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
14
Outline

Step 1. Collection of traffic info.





Collecting time to pass through each area
Propagation and retention of collected info.
Avoiding redundant processing of same data
Exchanging data with priorities
Step 2. Estimating arrival time
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
15
Redundant counting of same data

Average area passage time to be obtained


Data from multiple cars have to be collected
Data originated from one car is exchanged
through many cars, and treated as multiple data
A
A
July 21, 2006
(A+B)/2
(A+A+B+C)/4 ?!
(A+C)/2
V2VCOM 2006 - N. Shibata et al.
16
Avoiding the problem
 Avoiding redundant processing of area
passage time

Measured time by each car is not processed
until a car gets a sufficient number of data
Then, data are converted to statistical data

Ignore received data if it has a same set of data
as data retained.
 Avoiding redundant processing of
statistical data

July 21, 2006
Distinguish redundant data by hash value
V2VCOM 2006 - N. Shibata et al.
17
Avoiding redundant counting
7 sets of data
5 sets of data
A
July 21, 2006
A
V2VCOM 2006 - N. Shibata et al.
18
Avoiding redundant counting
A
A
If a same set of data is included in the
received data, it's ignored.
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
19
Exchanging data between cars
The case when threshold C = 10
5 sets of data
July 21, 2006
7 sets of data
V2VCOM 2006 - N. Shibata et al.
20
Exchanging data between cars
The case when threshold C = 10
7 sets of data
5 sets of data
10
C sets of data is converted to one statistical data
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
Remainder
21
Avoiding redundant processing of stat. data

Each stat. data include hash value
calculated from car IDs
A
A
A
Stat. data
Compare hash value, and discard if
it has already the same data
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
22
Outline

Step 1. Collection of traffic info.





Collecting time to pass through each area
Propagation and retention of collected info.
Avoiding redundant processing of same data
Exchanging data with priorities
Step 2. Estimating arrival time
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
23
Exchanging information


All information cannot be exchanged due to
bandwidth limitation
Data is prioritized based on where the car is
running at, and how the areas are congested
July 21, 2006
Mid
High
High
Low
Mid
High
Low
Low
Mid
V2VCOM 2006 - N. Shibata et al.
Position of
the car
24
Evaluation

Experiment 1


Experiment 2


Gain of accuracy by avoiding redundant processing
Gain of accuracy by prioritized data transmission
Experiment 3

Overall accuracy of estimated arrival time
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
25
Common configurations










Area size
300 m×300 m
Radio range
100 m
Max speed of cars
16.6 m/s (60 km/h)
Threshold C
5
Size of packet
1500 byte
Max # of packets sent by a car
0.3 packets / sec
Duration of each packet 0.01 sec
Duration of simulation 1 hour
Time to live of info.
30 minutes
Number of cars
300 at maximum
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
26
Traffic simulator
:NETSTREAM by TOYOTA
Map size
:1.2km×1.2km
The number of nodes :
21
The number of links :
78
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
27
Gain of accuracy by
avoiding redundant processing
Passage Time (sec.)
120
100
No avoidance
Our method
80
Actual time
60
40
20
0
A
B
C
D
E
F
Link Pair
G
H
I
If no avoidance, obtained time is much closer to the mode
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
28
Gain of accuracy by
prioritized data transmission
No prioritizing
Passage Time (sec.)
100
Only two cars have
data
Our method
80
Actual time
60
Data is lost
40
20
0
A
B
C
D
E
F
G
H
I
Link Pair
Loss of information is avoided by prioritizing
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
29
Estimated time vs actual time
140
Estimated
Passage Time (sec.)
120
B
A
O
P
C
A1
A2
Actual
100
80
60
40
20
Q
0
(A,O) (B,P)
(C,Q) (D,R)
(E,S)
(F,T)
(G,U)
(Area 1, Area 2)
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
30
Conclusion



We proposed an autonomous collection
method for traffic information
We evaluated our method using the
traffic simulator NETSTREAM
Future works include


Dissipating information to further area
Making it works correctly with very few cars
on the road
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
31
Thank you!
Any questions?
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
32
Situation where Step 1 is not sufficient
C-1 sets of info.
+ info. from car X
C-1 sets of the
same info. + info.
from car Y
July 21, 2006
Stat Info
A
Stat Info
B
Redundancy
V2VCOM 2006 - N. Shibata et al.
33
タイムスロットの導入
1秒をスロットに分割
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
34
情報の衝突判定
衝突
•通信範囲内の車両にパケットを送信
•各車両の送った1パケットが1タイムスロットを占有
•同じタイミングでパケットを受けた場合,受信しない
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
35
距離による通信成功判定
衝突しなかったパケットを
通信の成否の判定式にかける
X
P  0.98 1 
D
(
)
P・・・通信の成功確率
X・・・2車両間の距離
D・・・無線の最大到達範囲
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
36
実験結果
提案方式で得られたあるエリアのデータ
Passeage Time (sec)
100
80
最新10分の
実時間平均が59秒(10台)
60
40
59秒
最新10分の
通過車両が2台
20
0
A
B
C
各車両の持つ平均
統計情報の平均
July 21, 2006
実際の通過時間
D
E
F
Link Pairs
V2VCOM 2006 - N. Shibata et al.
G
H
I
37
提案方式で得られた2エリア通過時間
エリア境界
リンクペアO
リンクペアA
リンクペアB
経路1 = (A,O)
July 21, 2006
リンクペアP
経路2 = (B,P)
V2VCOM 2006 - N. Shibata et al.
38
# of passed cars
実際の平均時
間
8
7
6
5
4
3
2
1
0
提案方式
~60 70
July 21, 2006
80
完全な重複削除
を
行わなかった場
合
90 100 110 120 130 140~
Passage Time(sec)
V2VCOM 2006 - N. Shibata et al.
39
考察

所持する情報をランダムに送信すると,消
失や正しく伝わらない可能性

集めた情報は重複の完全削除を目指すと
平均値に,そうでない場合最頻値に近づく
可能性が高い
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
40
情報の重み付け
通信の帯域とパケットのサイズを考慮
効率的な情報送信を行う必要性
情報の重み付け
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
41
ステップ2:統計情報の重複回避
作成した統計情報自体に重複回避の仕組みが存在しない
統計情報に含まれる情報の
全車両IDから作成するハッシュ値を統計情報に含める
統計情報交換の際にハッシュ値を比較・重複データを削除
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
42
ステップ1:情報を一定数所持しての重複回避
例:閾値 C = 10 の場合
両車両は( 7+5 )個のエリア通過情報を取得する
Cを超えたので,統計情報を作成する
→ 1 個の統計情報と 2 個のエリア通過情報となる.
この情報交換の際に,エリア通過情報の重複を削除する
余り
C個の通過時間の平均値を1つの統計値にする
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
43
提案手法
エリアID:A6
エリアID:A5
(入リンク,出リンク)
(α,β)
(α,γ)
...
(ε,α)
40秒
...
(ε,δ)
通過時間
150秒
220秒
30秒
(入リンク,出リンク) 通過時間
(β,ζ)
20秒
(β,η)
40秒
...
(η,β)
100秒
...
(ζ,β)
500秒
通過時間の情報は各エリアの各リンクペアごとに記録
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
44
研究の目的

提案手法



GPSと車車間通信を用いた自律的な渋滞情報の収集と
提供
実際の環境を想定した設計
アプローチ

システムの設置・運用コストの削減


タイムリーかつ詳細な情報取得


インフラや管理センターを使用せず車車間通信のみで実現
目的地までの到着時間を提供
広いサービス提供エリア

July 21, 2006
VICSが対応できない場所の情報も取得・提供
V2VCOM 2006 - N. Shibata et al.
45
統計情報の作成
エリアID (入リンク,出リンク)
A5
(α,β)
通過時間
30秒
C台分の
80秒
データ
...
40秒
...
30秒
平均通過時間
41秒
統計情報
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
46
Outline

Step 1. Collection of traffic info.





Collecting time to pass through each area
Propagation and retention of collected info.
Avoiding redundant processing of same data
Exchanging data with priorities
Step 2. Estimating arrival time
July 21, 2006
V2VCOM 2006 - N. Shibata et al.
47
Arrival time estimation

Arrival time can be estimated by summing up
time to pass through areas
D
A1
a
S
A4
A7
July 21, 2006
g
b
d
A2
A5
e
A8
A3
f
Areas A7+A4+A5+A2
= Link pairs (S, a) + (a,
b) + (b, g) + (r, d)
A6
A9
V2VCOM 2006 - N. Shibata et al.
Areas A7+A8+A5+A2
= Link pairs (S, d) +
(d, e) + (e, f) + (f, d)
48
ダウンロード

V2VCOM 2006