EFFECTIVE PROBE DATA TRANSMITTAL WITH
DETECTION OF CONGESTION PATTERN
Ryota Horiguchi
Representative Manager, i-Transport Lab. Co., Ltd.
2-12-404 Ageba-cho, Shinjuku-ku, Tokyo 162-0824, Japan
Phone/Fax: +81-3-5261-3077, E-mail: horiguchi@i-transportlab.jp
Koji Wada
Research Manager, Japan Automobile Research Institute1-1-30 Shiba-Daimon, Minato-ku, Tokyo 105-0012, Japan
Phone:03-3519-4396, Fax:03-3501-5685, E-mail: kwada@jari.or.jp

ABSTRACTThis research proposes a methodology to effectively transmit probe data in terms ofcongestion detection. By using “short-trip (ST)” and “short-stop (SS)”, which represents avehicle trajectory as piecewise linear shape in time-distance space, it is possible to detectcongestion status of traffic with quick response. This allows us to transmit probe data en
bloc within a transaction containing ST+SS sequences only recorded in congested traffic
conditions, and to reduce the cost with less number of data transmittal. We have validated
the proposed methodology through IPCar probe experiment in Yokohama-city.

INTRODUCTION
This research proposes a methodology to effectively transmit probe data in terms ofcongestion detection. From the sake of business aspects of traffic informative service, aprobe vehicle will send its trajectory data to the probe information center by some electriccommunication in real time. Since the capacity of communication network is limited andthe communication is often costly, probe data collection system is strongly required to reduce
data transmittal cost as much as possible.
We have so far carried out an experiment for probe data collection in Yokohama-city (IPCar)
since 2001. The expression of the probe data in IPCar experiment is based on the idea of“short-trip (ST)” and “short-stop (SS)”, which divides a vehicle trajectory in time-space
diagram into “running” or “stopping” sections (Figure 1). Through the experiment, ST/SS
expression was validated that it can provide a good quality of data to measure section travel1

times as much as 1 second
interval data, and can compress
the volume of the data less than
30 seconds interval data.
Combining the event records
such as blinker switching or
hand break on/off with ST/SS,
we can cleanse the probe dataof non “en-trip” data sections[1].

Distance
congested flow region

Sequence of ST+SS
SSST

Free flow region

T ime
Another utility of ST/SS
Figure 1: Piecewise linear trajectory with ST and SS.
expression is to help theinterpretation of traffic conditions
surrounding a probe vehicle.
Non-congested section
Suppose a probe vehicle runningin a congestion section, thesurrounding vehicles with hightraffic density rob the probe ofmovablespace,
andtheA congested section consistsof small ST+SS sequences.
shockwaves propagating in thecongestionmay
repeatedlyTime
enforce small stop-and-go upon
Figure 2: Appearance of ST+SS in congested sections.
the probe (Figure 2).
Suchsituation can be detected by watching the sequence of ST and SS records [2].
4737000

4736500

4736000

Distance

4735500

4735000

4734500

4734000
16:50:53

16:53:46

16:56:38

16:59:31

17:02:24

17:05:17

17:08:10

17:11:02

17:13:55

When a probe detects a border of congestion and non-congestion sections, it can change thepolicy of data transmittal. For instance, it might be enough to send data only in congested
traffic for travel time information services. Therefore, how much we can reduce thetransmittal cost depends on how we can properly identify the congestion sections.
In the following chapters, the outline of the procedure to detect congestion section using
pattern classification of ST+SS sequences, at first. Secondly, couple of strategies to delimit“transactions”, which is to be considered as evenly congested or non-congested trafficcondition, are proposed. Then, those transaction strategies are evaluated their performancesin terms of the reduction of data transmittal opportunities with real world probe data. Finally,
the paper concludes the best strategy for the probe data collection for travel time information
service.

2

CONGESTION DETECTION WITH ST+SS SEQUENCESPATTERN CLASSIFICATION OF ST+SS SEQUENCES
The basic idea of congestion detection uses pattern classification of ST+SS sequences. The
reason why we do not simply use the average speed within a certain period, e.g. every 30
seconds, is that there is no guarantee the low speed means congestion nor the high speedmeans non-congestion. On arterial roads, a vehicle may be stopped for a minute or so at asignalized intersection. Especially for the roads in city center, the lengths of links are
relatively short and it is difficult for a vehicle to run long distance even in non-congested
situation. Indeed, the average speed of the recent period could be very low once the probevehicle is stopped for a while. Similarly, a vehicle in a congested section may run at somespeed when it is enforced stop-and-go by the shockwave propagation. If the periodic survey
misses the 'stop', the average speed of the vehicle will be recorded at somehow higher speed.

A sequence of ST+SS provides us not only the average speed but also the additional
information "how the probe stops", so that let us classify the sequences with two features, theduration of SS and the average speed of the sequence as shown in Figure 3. Figure 4
illustrates the contour of the appearance of ST+SS sequences with those two features and fourclusters, Pattern 'A'~'D', are found in the figure. If we transform a trajectory expressed withST and SS to a string using the symbols of those patterns, such as "BCCAACDD...", we cannow approach the statistical character of the appearance of each pattern. Although the detailof the analysis is left out from the sake of pages, each pattern can be interpreted as follows.
'A' : is a congested pattern that repeatedly appears in a congested section.
'B' : is an ambiguous pattern that independently appears either in a congested or a
non-congested section.

Figure 3: A sequence of ST+SS

20_22.5

D

15_17.5
10_12.5

A

5_7.5
90_95

80_85

70_75

60_65

50_55

C
40_45

TimeB

30_35

Av. Speed of SQ

25_27.5

20_25

Dist.

30_32.5

10_15

ST

35_37.5

0_5

SS

4.5%-5.0%
4.0%-4.5%
3.5%-4.0%
3.0%-3.5%
2.5%-3.0%
2.0%-2.5%
1.5%-2.0%
1.0%-1.5%
0.5%-1.0%
0.0%-0.5%-0.5%-0.0%

ST+SS AvSpeed [km/hr]

SS duration vs ST+SS AvSpeed (14:00 - 18:00, cleansed)

Duration of SS

0_2.5

SS Duration [sec]Figure 4: Pattern classification of ST+SS sequences.

3

'C' : is a congested pattern that independently appears in a congested section, but lessfrequent than 'A'.
'D' : is a non-congested pattern that repeatedly appears in a non-congested section.

STRATEGIES TO EXTRACT TRANSACTION FOR DATA TRANSMITTAL
Those characteristics of ST+SS sequences will be helpful to delimit probe trajectory data at
the boundaries between congested and non-congested sections. Now, let us introduce atransaction, a unit of data transmittal, which consists of a series of continuing ST+SS
sequences of which the traffic condition can be regarded as homogeneous, ie. congested ornon-congested. If we are interested only in traffic congestion and do not take notice fornon-congested sections, we may change the policy of data transmittal from a vehicle to acenter whether the vehicle is running in congested sections or not. For example, the mostexcessive way is to discard the data in non-congested transactions and to send the data only incongested transactions, in order to reduce the transmittal cost.
According to the interpretation of 'A'~'D' in the previous section, the basic strategy to delimit
a trajectory is to know the change of traffic status by the appearance of the pattern 'A' or 'D',
because they have clear meanings. However, as there are ambiguous patterns, 'B' and 'C', thefollowing two strategies are to be considered.
Strategy-1 : Ignoring 'B' and 'C', let the section where 'A' is continuing be a congested
transaction and where 'D' is continuing be a non-congested transaction.
Strategy-2 : Ignoring 'B', let the section where 'A' and 'C' are continuing be a congested
transaction and where 'D' is continuing be a non-congested transaction.
The performance of each strategy for the reduction of data transmittal cost is validated withreal data collected within IPCar2003 project, as described in the next chapter.

EVALUATION OF DATA TRANSMITTAL STRATEGIESOUTLINE OF FIELD EXPERIMENT
For a couple of recent years, Japan Automobile Research Institute (JARI) has been working
for the experiments of probe data collection system via Internet on Mobile IPv6. The latest
experiment in 2003 was carried out in Yokohama-city and Nagoya-city, with the purpose toadvance the probe applications for road and traffic administration works [3]. Using the4probe data collected in Yokohama-city (IPCar2003-Y), the performances of the proposed
strategies were evaluated.
The outline of the data and the subjective field are shown in Table 1 and Figure 5. The raw
data is recorded every 1 second and stored on HDD in 'Integrated Probe Equipment' andtransferred to the data server in bulk at the begging of a day via Internet. In this research, theraw data is used for the validation of transactions, but specially, 'Integrated Probe Equipment'
can transmit the processed data immediately when it is generated from the raw data.
Table 1: Outline of collected data (IPCar2004-Y)
Period of data collection
Sept. 2003 - Jan. 2004
Number of probes

5 buses serving for Line #13 of Yokohama-city Bus.

Number of probe trips

about 2,000 for each up and down of Line #13.

Raw data (1 Hz)

Location (LBH), speed, odometer, blinker status, etc.

Processed data

ST, SS by traffic signals, SS at bus stops, etc.

For Tsunashima
City ring-road 2
Kami-Sueyoshi

Tsurumizo road

R1
Shimo-Sueyoshi

Bus stop
Traffic signal
JR Tsurumi Sta.
Keiyu Tsurumi Sta.

3.5km
MikadoEast of Tsurumi Sta.
R15

For Benten-cho

Figure 5: Subjective field of IPCar2003-Y.

COMPARISON OF TRANSACTION STRATEGIESThe performances of two transaction strategies explained in the previous chapter are
evaluated regarding how they reduce the opportunities of data transmittal. Table 2 shows thenumber of appearances for both congested and non-congested transactions. The result says
'Strategy-1' takes the advantage to reduce the number of opportunities to transmit data.
5

Table 2: Number of extracted transactions with each delimitation strategy.
# of congested tranx.
# of non-congested tranx.
Strategy-11596

2070

Strategy-23128

4083

Let us see more detail in terms of the duration and the average speed of transactions. Figure
6 and Figure 7 compares the cumulative percentage of the appearances for each strategy.
For 'Strategy-1', though we find some curious "non-congested" transactions at low speed
range, the durations of non-congested transactions are mostly longer, and the durations ofcongested transactions are mostly shorter than the ones of 'Strategy-2'. This implies'Strategy-1' would be preferable to 'Strategy-2' for traffic informative services, because wemay expect quick and dense information in congested sections in where we are interested andvice-versa in non-congested sections.

トランザクションの継続時間分布 (戦略１)
Durationof Tranx. with Strategy-1

トランザクションの旅行速度分布 (戦略１)
Av.Sppedof Tranx. with Strategy-1

100%100%Congested

30%
20%

384040<

旅行速度 [km/hr]

Duration of Tranx.
渋滞区間 (1596回)

3436

90
12015018021024027030
0330360390420450
48051
054057060
0

継続時間[秒]30
320%
26280%“Non-congested” transactions
at low speed.
22
2410%

010%

182020%Non-congested

40%

1416

Non-congested

30%

50%

810
1240%

60%

650%

70%

460%

Cum.%
of Appr.
累積頻度分布

80%

70%

03060

Cum.%
of Appr.
累積出現確率Congested

90%

80%

290%

Av. Speed of Tranx.

非渋滞区間 (2070回)

渋滞区間 (1596回)

非渋滞区間 (2070回)

Figure 6: Distribution of the duration and the average speed of transactions with 'Strategy-1'.

トランザクショの継続時間分布(戦略２)
Durationof ンTranx.
withStrategy-2

トランザクションの旅行速度分布)
Av.Sppedof Tranx.
with(戦略２
Strategy-2
100%

70%

70%

50%
40%

384040<9012015018021024027030
033036039
042045048
051
054057060
0

継続時間[秒]

34360%
30
32

10%

0%

262820%10%222420%Non-congested

182030%

030%

1416

Non-congested

60%

101250%860%

2

累積頻度分布80%

40%Congested90%

6Congested

80%03060Cum.%of Appr.
累積出現確率90%4100%

旅行速度 [km/hr]

Durationof Tranx.
渋滞区間 (3128回)
非渋滞区間 (4083回)

Av.
Speed
渋滞区間(3128回)of Tranx.
非渋滞区間 (4083回)

Figure 7: Distribution of the duration and the average speed of transactions with 'Strategy-2'.

6UTILITY OF TRANSACTIONS TO REDUCE THE COST OF DATA TRANSMITTALIn order to highlight the utility of transactions, let us compare the number of data transmittaland the amount of data volume with different way of data transmittal strategies. Table 3
explains two ways, "ST+SS sequence" and "transaction", of probe data approximation to raw
data. The items in a record are chosen so as to contain as equivalent information to bevaluable for link travel time estimation as possible.
Table 3: The way of probe data approximation
Items in a record
Rec. size
Update frequency in average

Data approximation
Raw datatime and position.

16 byte1 second

ST+SS sequencetime, position of SS, duration of28 byte

Apprx. 50 seconds

40 byteApprx. 80 seconds (congested)

SS, duration of ST, and distance ofST.
Transaction

time, head position, tail position,duration, distance, number of SS

Apprx. 270 seconds

and duration of SS.

(non-congested)

Here, let us consider the following data transmittal strategies.
(a) sending raw data in bulk at every 30 seconds.
(b) sending every ST+SS sequences.
(c) sending every transactions extracted by 'Strategy-1'.
Table 4 shows the result of the performance of each strategy. Let the strategy '(a)' be thebase of comparison, '(b)' reduces the number of transmittal almost a half and retrench 97% ofdata volume. Furthermore, the strategy '(c)' saves 97% of transmittal opportunities andsends equivalent data with only 0.25% volume of raw data.
Table 4: Comparison of data transmittal strategies.
Data approximation
Transmittal unit
# of transmittal

Amount of data(a) Raw data

every 30 seconds

135,038100%

61.8 MB

100%(b) ST+SS sequence

every sequence

77,53457%

2.07 MB

3%(c) Transaction

every transaction.

3,666

2.7%

150 KB

0.25%

Regarding to the time lag to detect congestion traffic, '(c)' takes about 80 seconds in average,
while '(a)' takes 30 seconds and '(b)' takes about 50 seconds. This much of the time lag ofeither '(b)' or '(c)' would be acceptable if we attach importance to the reduction of transmittal
7cost.

CONCLUSION
In this paper, the basic concept of congestion detection using ST+SS sequence was explained.
Delimiting a trajectory into congested and non-congested 'transactions', we may change thepolicy of data transmittal and reduce the transmittal cost. Through the experiment ofIPCar2003 in Yokohama-city, we have validated the performance of data reduction for acouple of transaction strategies. We have concluded that a good strategy with transactions
can reduce 97% of the transmittal opportunities and 99.7% of the amount of data volume
comparing to raw data collected every 1 second, even though a transaction contains almost
equivalent information to the raw data. The time lag to detect congested traffic is about 80
seconds in average, and we may accept this much of delay.
For the future scope, the transaction strategy will be implemented onto 'integrated probe
equipments' and validated its performance in the next IPCar2004 experiment.

REFERENCES[1] E. Chung, M. Sarvi, Y. Murakami, R. Horituchi and M. Kuwahara: “Cleansing of Probe
Car Data to Determine Trip OD”, Presented at 21st ARRB Conference in Cairns, Austraria,
2003.
[2] M. Sarvi, R. Horiguchi, M. Kuwahara, Y. Shimizu, A. Sato and Y. Sugisaki: “AMethodology to Identiry Traffic Congestion Using Intelligent Probe Vehicles”, Proceedings of10th World Congress on Intelligent Transport Systems, Madrid, 2003.
[3] K. Wada: "Research Development and Field Testing of the Probe Car Information System(IV), will be included in Proceedings of 11th World Congress on Intelligent Transport
Systems, Nagoya, 2004.

8