BEST PAPER 4:

Title: Congestion detection and propagation in urban areas using histogram models
Journal: IEEE Internet of Things Journal
Impact factor: 10.6, Quartile Q1

Why the work is essential:

This work is crucial because the algorithm proposed in the paper uses the Intelligent Trans-
portation System (ITS) to provide a novel rerouting strategy for vehicles. The solution proposed
in this paper has been developed as a prototype and it is tested in the UAE roads and its per-
formance has been analyzed.

A short description of technical contribution:

In this paper, a new histogram-based model for the rerouting strategy has been proposed.
The proposed algorithm uses Intelligent Transportation System (ITS) technologies to provide
a novel rerouting strategy. The proposed model enables the microscopic visualization of the
traffic patterns for every individual lane to predict congestion and take action proactively. The
performance analysis shows that the proposed model addresses the congestion problem effec-
tively and improves the efficiency in the vehicular traffic environment.

The candidate contribution:

I am the second author, as well as the main contributor to this paper. The other author was
the PI of this project.
3672 IEEE INTERNET OF THINGS JOURNAL, VOL. 5, NO. 5, OCTOBER 2018

Congestion Detection and Propagation in Urban

Areas Using Histogram Models
Hesham El-Sayed and Gokulnath Thandavarayan

Abstract—Rapid growth of urbanization makes the roadways provide promising results to handle the congestion problems
exacerbate many problems like traffic congestion, road acci- and solve other transportation related issues. ITS enables var-
dents, and passenger discomfort. Many actions have been taken ious technologies to be integrated into a single cluster, for
globally to solve or reduce this impact but still the conges-
tion problem seems to be persistent globally. In this paper, we example, it uses vehicular ad-hoc network (VANET) technol-
propose a new histogram-based model for congestion detection. ogy for wireless communications, integrate global positioning
We subsequently extended our model with the base platform system (GPS) technology for positioning and uses various
concept and use Intelligent Transportation System (ITS) tech- sensors and cameras for detection schemes. Nevertheless,
nologies to provide a novel rerouting strategy. The proposed it has some limitations in real time implementation, where
model enables the microscopic visualization of the traffic pat-
terns for every individual lane and predicts the congestion in it demands more data exchange and processing power. As
priori and takes actions proactively. The rerouting strategy used the structure of the urban areas is heterogeneous in nature,
in our approach provides a novel solution to the congestion implementing a generic spatial–temporal model for congestion
problem by taking precaution measures prior to the critical detection could increase the complexity. In addition, most of
point of congestion occurrence. The proposed algorithm is com- the existing systems demand on-board unit and GPS module to
pared with various existing algorithms and the simulation results
show that the proposed model addresses the congestion problem be integrated on every vehicle, which makes the system costly.
effectively and provides better solution compared to existing Current route guidance models, which address congestion
algorithms. problem are based on considering the static information and
Index Terms—Congestion estimation, congestion propaga- initiate the route guidance reactively after the congestion hits
tion, histograms, intelligent transportation system (ITS), route the roadways. Unfortunately, this late detection schemes make
guidance. the route guidance ineffective and just shift the congestion
from one region to the other.
For the aforementioned reasons, there is a need for an
I. I NTRODUCTION intelligent congestion detection scheme, which detects the
RAFFIC congestion affects major cities and engenders
T pollution [1], high waiting time [2], and economic loss.
According to the recent survey presented by the traf-
congestion in advance and trigger the route guidance dynam-
ically. In this paper, a microscopic visualization model is
utilized which adapts a dynamic congestion estimation strat-
fic information company Inrix [3], it is estimated that, by egy to estimate the congestion for every lane. The congestion
2030 USA will be affected by $2.8 trillion loss due to detection technique is based on the lightweight histogram-
traffic congestion and in countries like France, U.K., and based model [6], which captures the higher order distribution
Germany each individual citizens need to spend $2902 annu- stochastic function for vehicles. The proposed model will char-
ally due to traffic. Road Transport Authority [4] from Dubai acterize the traffic behavior of urban areas using base-platform
has claimed a loss of 7.6 billion during the year 2006 to technology and analyze the congestion propagation in road-
2013 due to the traffic congestion in roadways. The conges- ways. Further, this information will be used to detect the
tion will also create negative consequences on passenger’s critical point of congestion for every lane and the rerouting
health. Sugiyama et al. [5] concluded that the prolonged travel strategy will be initiated before the congestion happens in the
time over 1 h per day increases cardio-metabolic disease risk network. Due to its simplicity and generality, the proposed
and increase major health problems. For these reasons, man- model requires minimum data transfer and can be easily imple-
aging the congestion in roadways is meant to be an open mented in urban areas for congestion estimation and route
problem for decades; many techniques have been proposed to guidance. A microscopic simulation model is created with dif-
address the congestion problem. Despite of all methods, recent ferent scenarios and compared with the existing algorithms.
technologies like the Intelligent Transportation System (ITS) The proposed model provides better solution than the existing
algorithms and keeps the trip time to be lower for vehicles.
Manuscript received September 14, 2016; revised January 16, 2017; Finally, to validate the robustness of the proposed model,
accepted January 31, 2017. Date of publication February 8, 2017; date
of current version November 14, 2018. This work was supported by the an optimized model called shortest path algorithm (SPA) is
Roadway, Transportation, and Traffic Safety Research Center of the United utilized for comparison. As the SPA model provides route
Arab Emirates University under Grant 31R058. guidance based on all the information about the entire network,
The authors are with the College of Information Technology, United Arab
Emirates University, Al Ain, UAE (e-mail: [email protected]). it demands a very complex system. It is practically less
Digital Object Identifier 10.1109/JIOT.2017.2665662 feasible to be implemented in roadways due to its high cost
2327-4662 c 2017 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission.
See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.
Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
EL-SAYED AND THANDAVARAYAN: CONGESTION DETECTION AND PROPAGATION IN URBAN AREAS USING HISTOGRAM MODELS 3673

and complexity. Promisingly, the results of the proposed model is high in the near future. Based on this new definition, it can
show that the proposed model works closely with the theoreti- classify the congested lane from the noncongested lane for the
cal model (SPA) and uses less processing and less complexity given time interval. Further, it estimates the short-term traffic
when compared with the theoretical model (SPA). The rest congestion forecasting for any given road. However, the model
of this paper is structured as follows. In Section II, we dis- assumes that every vehicle mounting an advanced PND inte-
cuss the existing related work and discuss its limitations. In grated with a GPS receiver and a full-duplex communication
Section III, a brief overview about the system is described. device, which is not practically possible to impede on every
Section IV presents the histogram data computing method- vehicle in urban areas. The second problem is that this mecha-
ology. Section V describes the network model. Section VI nism lacks the ability to predict how long a state of congestion
discusses the methodology for congestion detection in urban will last during the trip time. Terroso-Saenz et al. [13] put for-
areas. Section VII provides analysis and prediction of the warded an event-driven architecture (EDA) as a mechanism to
congestion propagation. Section VIII describes the rerouting detect different levels of traffic jams and also consider other
strategy. Section IX evaluates the performance of the proposed environmental data that come from external data sources, such
scheme. Finally, the conclusion is averred in Section X. as weather conditions. The problem in that paper is that it does
not take into account other traffic metrics that do not rely on
the penetration rate of the system and the EDA to use segments
II. R ELATED W ORK instead of a cluster bases digital map to divide the road dur-
Projects like Nav-N-Go [7], iGo-Navigation [8], and ing the CEP processing. Several studies exhibit that they use
Google-Auto [9] are introduced for vehicle navigation. In GPS devices as the important factor to collect traffic traces,
these projects, vehicles are equipped with various sensors, but in real time scenarios it would make the system open to
GPS modules and synchronized with the smart phones for more errors and complex calculations. As noticed in the exist-
navigation purposes. The system provides many services to ing systems, there can be a myriad of problems. In places like
use like route information, traffic update, and parking facili- urban area, there can be irregularities in GPS signals [14] due
ties. However, these projects heavily rely on the centralized to periods of high geometric activity. Accordingly, by having
server and expect that the vehicles need to be connected the amplitude fading and phase scintillations, it is difficult to
with Internet. These systems process the information based predict congestion in places like intersections and roundabouts.
on the static maps and rely on user’s information to deter- Furthermore, the existing schemes require special equipment,
mine the congestion. This makes the system less reliable to like OBU and GPS, to be installed in vehicles.
detect the real-time congestion in roadways. As the urban road- For the aforementioned reasons, there is no doubt that
ways have heterogeneous behavior, detecting the congestion there should be a cogent methodology to avoid the previous
and providing a reliable precautious measure should be based problems. In this paper, a novel congestion detection and prop-
on the higher order distribution function with dynamic update. agation scheme is presented based on the ITS technology. For
Further, the system should not demand any on-board devices conducting traffic analysis, we use a light-weight histogram-
on the vehicles, to keep the cost of vehicle less. based model with sliding window properties. The proposed
In recent years, many researchers have been working on scheme effectively detects the congestion level at every lane
the congestion detection problem using advanced technologies and predicts the congestion propagation patterns for enabling
that exploit the traffic behavior of urban areas. In this section, the rerouting strategy.
we sum up some of the related work based on the conges- The proposed methodology is cost effective and does not
tion detection problem. Leontiadis et al. [10] have proposed require any additional equipment to be installed in vehicles.
a system NavSys that enable vehicles to exchange the traffic By using the light-weight histogram models, the data exchange
traces using ad hoc technology. The degree of congestion was rate is greatly minimized and thus reducing the overhead in
reported by accessing the street section delay and the shortest the network.
path was estimated by the weighted graph. From entry and
exit of road segments, the system collects GPS information
of individual vehicles and stored it in the database. A gossip- III. OVERVIEW
based routing protocol is used to disseminate the information In this paper, we propose a light weight and efficient con-
to the network. Although the system collects data to find the gestion detection and congestion propagation scheme for urban
shortest path, it is dubitable to the interference problem and areas. As shown in Fig. 1, the system adapts a microscopic
processing heavy load of traffic information in a stipulated monitoring of vehicles in urban areas and detect the conges-
time. Likewise, Wang et al. [11] proposed an interactive visual tion for individual lanes. A base platform concept is utilized
analysis system to analyze traffic jams. It also uses GPS trajec- in individual lanes to monitor the traffic patterns. The degree
tories from taxis to build the flow speed for the road network, of congestion rate (CR) for every lane is computed period-
and uses map matching techniques for structured visualization ically by light weight histogram models and is used by the
of propagation graphs. However, the model uses static data for congestion propagation scheme to detect the lanes that will
computing relative low-speed detection that is nonpragmatic be congested in the near future. This information is dissem-
to urban areas. Marfia and Roccetti [12] proposed a new def- inated to all vehicles travelling in the network using simple
inition according to which a road is in a congested state only infrastructure-to-vehicle (I2V) and vehicle-to-vehicle commu-
when the likelihood of finding it in the same congested state nication mechanisms. Once the CR in any lane(s) increases

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
3674 IEEE INTERNET OF THINGS JOURNAL, VOL. 5, NO. 5, OCTOBER 2018

Fig. 2. Statistical histogram for class distribution shown in Table I.

Initially, the density pattern across the network data are col-
lected by sensors over the time called observation period (O).
Further, the observation period is fragmented into time slots of
sampling period (T) where the density is calculated. Therefore,
the number of sampling windows N within an observation
Fig. 1. Overview of the proposed system. period is equal to O/T. Therefore, the number of sampling
windows N within an observation period is equal to O/T.
TABLE I
E XAMPLE OF C LASS D ISTRIBUTION D URING Let V(t) be a discrete random variable representing the
A S INGLE O BSERVATION P ERIOD number of vehicles entering the street during the (tth) sam-
pling period. Hence, the total number of vehicles entering the
street during a sampling window V(t)|t ∈ {1, 2, . . . , N} can
be described as a discrete random process with a state space,
denoted as (I), which is a set of integers between 0 and the
maximum number (K) of vehicles held in the street. Note
that,V(t) can be obtained by on-side road traffic sensors. As
the statistical I := {0, 1, . . . , K} variable can vary over a big
range of values [0, K]. We divide this range into Nc limited
number of classes and compute the grouped probability distri-
bution (GPD) over each class. For example, Table I, shows
the statistics of number of vehicles on road that has been
analyzed using a sampling period of T = 15 s by a wire-
less sensor network over a total observation period of 5 min,
above certain threshold value, the adaptive rerouting strategy where N = 20 sampling interval. The range of the number
will be initiated to avoid the congested lanes. of vehicles during the observation period varies from (<15),
(15-19), (20-25), (>25) which is divided into Nc = 4 classes.
The bins used in the histograms are classified using the pro-
IV. H ISTOGRAM DATA C OMPUTING cess developed by Skycomp (Major highway performance
Congestion estimation is the act of estimating the con- rating and inventory—State of Maryland—spring 2008) [18].
tinuous density of a particular lane from a discrete sample The level-of-service for signalized intersection is grouped as
sets drawn from the corresponding lane individually. In urban light, moderate, heavy, and congested. Based on this group-
areas, the traffic pattern [15] created in every lane is unique ing, the (<15) bin denotes light, (15-19) bin denotes moderate,
and dynamic in nature. To analyze every characteristics of (20-25) bin denotes heavy, and (>25) bin denotes congested.
lane individually, a large amount of database should be used The histogram defined in this paper is a form of a bar graph
to track the congestion. In order to solve this problem, we representation of a GPD [19], which is shown in Fig. 2, repre-
propose a simple congestion estimation technique by using his- senting the number of vehicles in an observation window basis
tograms, which is usually presented in 1-D. Though seemingly against their corresponding probabilities (or frequencies). This
simple, the effective use of histograms can be surprisingly sub- is important, since C = (C, P) can be easily obtained by vehi-
tle. We present a simple nonparametric modeling approach cles moving on the road, and this statistical information is to
using Knuth’s rule [16], which is based on optimization be shared by all other vehicles through an ad hoc-based I2V
of a Bayesian fitness function across fixed-width bins. The network.
congestion estimation is done by choosing the bins suffi- Here, we note that the process of vehicles input into the
ciently large enough due to random sampling fluctuations. queuing system is stationary at a uniform rate, and the number

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
EL-SAYED AND THANDAVARAYAN: CONGESTION DETECTION AND PROPAGATION IN URBAN AREAS USING HISTOGRAM MODELS 3675

Fig. 3. Base platform on a single lane.

TABLE II
of vehicles V(t)|t ∈ {1, 2, . . . , N} arriving in an observa- C LASSIFICATION OF C ONGESTION L EVELS BASED ON V EHICLE D ENSITY
tion period is independent and has a distribution modeled by
a histogram C = (C, P). Therefore, V(t)|t ∈ {1, 2, . . . , N} is
a stochastic process used to characterize the variable number
of vehicles input into the queue under investigation [6].
This paper indent was to estimate the congestion propaga-
tion and use it for the rerouting strategy. In urban areas, the
characteristics of each lane could vary with each other. For
example, the lane length would be different and the maxi-
mum speed limit would not be the same. It is difficult to have
a generalized method to identify a congested lane in partic- with regular intervals. Further, we divide the base-platform
ular. Initially, for validation, we developed a simple scenario into two regions called MDT and NDT , which are used for
using the SUMO [20] simulator using only one intersection rerouting strategy. Initially, the congestion starts building over
to justify our model. Further, the congestion created in every the region MDT followed by NDT . Where, vehicles become
single lane is measured using different volumes, and different full halt in the region MDT , while vehicles kept moving in the
speed scenarios. In this model, we use a base platform tech- region NDT . Further, the number of counted cars in the base-
nique, which computes the congestion probability index (CPI) platform is classified into four different bins, based on the level
value to determine whether the lane is congested or not. In of service provided for the congestion detection. The bins used
every lane, we select a particular portion called base platform to build the histograms have four ratings as shown in Table II
as shown in Fig. 3, and use it to estimate the congestion for (Skycomp2008) [18].
that particular lane. For every 15 s, the sensors count the vehicles presented
To begin with, each lane length is set as 1 km and two in the base platform and increment the frequency of the
induction loop sensors are implanted in every lane to analyze corresponding bin. For example, if the vehicle count is 17,
the traffic behavior. We considered that the traffic created near the frequency of the moderate-traffic bin (BIN-II) is increased
the intersection is due to the traffic signal and it will dis- by 1. This process is repeated for the stipulated time of 5 min
perse in the green signal period. The first sensor fixed after and the histograms are drawn. A new histogram is drawn every
300 m from the intersection, is due to the factor that we want 5 min; however, the first 5 min are considered as warm-up
to neglect the traffic created by traffic lights as we avoid the time, thus five different histograms are created for every 30-
vehicles waiting for green signal and consider it as the nor- min experiment. Fig. 4(a)–(e) shows the individual histograms
mal phenomena. The occurrences of vehicles waiting in the for source volume 700, and Fig. 4(f) shows the combined his-
traffic light during the red signal period are quite normal until tograms for all experiments, which provides a better visualiza-
it exceeds the limit of 300 m. If the vehicle queue length tion of the traffic distribution during the experiment. Different
exceeds after the 300 m from the intersection, we may predict source volumes vary from 50–1000 burst rate are simulated
that the lane is likely to be get congested in the near future. to analyze the traffic behavior. The cumulative graph for all
Only estimating the congestion index of that particular lane different source volumes is presented in Fig. 5. As we can see
could validate this prediction. Since congestions are always from Fig. 5(a) and (b), in source volume 500 and 600, the traf-
created near to the intersection and propagate backward over fic is nominal and most of the traffic is occurring between the
the period of time, it is well founded that the base platform light and moderate bins. When the source volume increases,
could be placed near to the intersection. The base platform traffic rate increases and congestion starts to build up.
should identify the congestion prior to the critical point and For example, when we increase the source volume to 900
we fix the base platform distance as 400 m. The second sen- and 1000, most traffic occurs in the heavy and congested
sor is placed in the distance of 700 m from the intersection bins. Thus, the volume injection rate is directly proportional
and validated that it is too early to detect the congestion if to congestion propagation.
we fix the sensor before 700 m and too late to fix the sensor
after 700 m. The sensors will count the number of vehicles in V. C ONGESTION D ETECTION
the base-platform to identify whether the lane is congested or In this section, we derive a congestion detection scheme,
not. We run the simulation for 30 min and build histograms which estimates whether a lane is congested or not. Congestion

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
3676 IEEE INTERNET OF THINGS JOURNAL, VOL. 5, NO. 5, OCTOBER 2018

Fig. 5. Histograms for different source volumes. (a) 500. (b) 600. (c) 700.
Fig. 4. Individual histograms and the cumulative graph for source
(d) 800. (e) 900. (f) 1000.
volume 700. (a) 5–10 min. (b) 10–15 min. (c) 15–20 min. (d) 20–25 min.
(e) 25–30 min. (f) Cumulative graph.

rerouting strategy in advance and make the system ineffi-

cient. If CPI is having higher value, the lanes are jam-packed
in roadways is problematic, where vehicles hinder with each and the rerouting strategy would never be triggered on time.
other and enter into a full halt or a stop and go fashion. Once Because congestion always happens when traffic increases in
the roadway capacity is full, every new vehicle imposes fur- the congested traffic bin (BIN-IV), the CPI is computed from
ther delay in the network. It affects the roadway passengers analyzing the congested-traffic (BIN-IV) only.
and tends to increase the total travel time, fuel wastage, and The  CR for every lane is computed by the formula
pollution problems. CR = ni=0 (a0 + a1 + . . . an )/100. Where a represents the
In the previous section, histograms for different source vol- frequency of occurrences in the congested-traffic bin (BIN-IV)
umes are computed for a single lane, and the CR for different on a window basis derived from the histograms. For exam-
source volumes can be identified by analyzing the histograms. ple, in Fig. 5(a), the congestion index for the source volume
Nevertheless, this scheme needs to be generalized for the 500, with lane maximum speed of 60 km/h, is computed
different lane characteristics. As the histograms provide an by CR = [(3 + 3 + 2 + 3 + 3)/100] and the value is 0.14.
overall traffic pattern for a single lane, it cannot be directly Similarly, in Fig. 5(f), the CR value is computed as CR =
used for congestion avoidance. To avoid congestion and enable [(7 + 7 + 6 + 6 + 7)/100] = 0.33. The CR for different
rerouting strategy, it is important to detect any congested lane source volume with different lane speed is computed by
well in advance before the congestion accumulates in that par- monitoring the congested-traffic (BIN-IV) as shown in the
ticular lane. Therefore, we compute a benchmark CPI to detect Table III.
whether a lane is congested or not. This benchmark CPI value We observe the CR varies based on source volume and the
can be applied to all type of lanes with different lane length, label speed. For example, when the source volume is 500, we
different speed and different volume rate. compute different CR values 0.14, 0.13, and 0.13 for different
To derive the benchmark CPI value, we use the test-bed lane speed. Furthermore, we observe that when the source vol-
shown in Fig. 3 and analyze the histograms obtained from ume is 500–800, we do not encounter any congestion during
different source volumes. Table III shows the discrete set of the experiments. When the source volume is 900, we encounter
samples collected from the base platform on a window time congestion when the lane speed is less than 60 km/h, while
basis with different source volume scenarios. The congestion we observe moderate flow when the lane speed is greater
severity can be estimated by monitoring the different bins. than 80 km/h. Moreover, when the source volume is 1000, we
It is apparent that congestion happens in roadways when the encounter congestion when the lane speed is less than 80 km/h.
vehicles are more than the available capacity. In order to find In real time, the lanes in urban areas have different charac-
the severe level of congestion in a lane, the congested-traffic teristics, some lanes have high speed limit as above 100 km/h
(BIN-IV) alone is taken into consideration. Choosing the right and some lanes have less speed limit as 40 km/h. For conges-
value for CPI benchmark is very important to predict the tion detection, a benchmark CPI value should be derived to
congestion. For instance, if the value CPI is selected low, detect the congestion of a lane irrespective of its lane charac-
the system will detect the congestion early and initiate the teristics. To derive a benchmark CPI value it is necessary to

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
EL-SAYED AND THANDAVARAYAN: CONGESTION DETECTION AND PROPAGATION IN URBAN AREAS USING HISTOGRAM MODELS 3677

TABLE III
CR FOR D IFFERENT S OURCE VOLUMES

Fig. 6. Congestion rates for different volume and speed.

correlate the relationship between speed and the vehicle flow Fig. 7. Graphical representation for CPI.
rate in the lane. We analyzed the different scenarios, where we
encountered congestion and realized that in all experiments the
CR value was greater than or equal to 0.3. used for identifying the congestion lane in advance and helps
We use the benchmark CPI value to be 0.3 as a median to to initiate the precautious measure.
monitor the congestion. The CR value computed from Table III The curve shown in Fig. 7 illustrates the traffic behavior of
with different source volume is implemented in the heat dia- each lane and is used to validate the benchmark CPI. Initially,
gram shown in Fig. 6. The diagram apparently shows that vehicles will move freely in a lane with its lane maximum
the congestion starts to build up from source volume 900 and speed and the flow rate will be represented as vector v0 . When
become more congested when there is an increase in the flow the flow rate v0 lies between the CRs I and D, the traffic is
rate. It also shows that the CPI index of 0.3 is a good prediction moderate and the lanes are well utilized. Further, when the
point for detecting congestion regardless of the value of the flow rate increases from D to J, the congestion in the lane
source volume and lane speed. This analysis could be further starts to build up. When the flow rate exceeds J and none of

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
3678 IEEE INTERNET OF THINGS JOURNAL, VOL. 5, NO. 5, OCTOBER 2018

Fig. 8. Grid network topology.

Fig. 9. Stages for predicting congestion propagation.

the precautious measures are implemented in the network, the
vehicles will keep entering the lane until the lane becomes
full halt at point Q. To prevent the vehicles from entering
the congested lane any further, the CR D will be indicated as avoid further congestion. By rerouting the vehicles, the uncon-
the CPI benchmark and the rerouting strategy will be initiated gested lanes (ULs) are utilized and the congested lanes are
accordingly. avoided. This greatly minimizes the frequency of congestion
occurrences and the make the congested lane takes less recov-
ery time to resumes its normal operation. The first observation
VI. N ETWORK M ODEL in the experiment focuses on the prediction of congested lane
In this section, we discuss the network model used in our among the urban area network. By identifying the congested
proposed system for congestion propagation and rerouting lanes among the network, we can understand the congestion
strategy. In the previous sections, we used our base-platform propagation and capture the fundamental phenomena for traf-
model with various source volumes to identify the benchmark fic occurrences. In this paper, we develop a new methodology
CPI value. Further, this CPI value is used to predict the conges- to study the empirical analysis of the congestion formation
tion propagation and initiate the rerouting strategy whenever and its propagation between the contiguous lanes as shown in
necessary. In real time, the urban roadway commonly has sev- Fig. 9. The model captures the sequence of congestion propa-
eral types of road junctions including traffic signals: 1) road gation by monitoring the traffic at fine granularity based on the
junction with roundabout and 2) road junction with flyover. traffic flow. The traffic network are clustered into regions with
To study the effectiveness of the congestion-detection respect to intersections, each lane is monitored individually to
scheme, a grid network model is utilized. We use I-sim simu- analyze the characteristic behavior of traffic flow.
lator to create the scenarios [25]. The scenarios were created Initially, all lanes are connected by intersection that can be
using various source volumes, varying link speed, and vary- mapped by the graph representation using the geometric func-
ing link length. A network model with 7 × 7 grid structure tion GS = (V, E), where V represents the vertices (nodes) and
is created as shown in Fig. 8. In the grid structure, the nodes E represents the edges (lanes) between the nodes. As discussed
are considered as intersections and the edges are considered in the network section, every node in the graph is the cumu-
as lanes. Each intersection is implemented with traffic light to lative summation of the individual lane lying adjacent to each
create the real time vehicle movement. Every node has one other in the grid and forms an intersection. Every edge repre-
or more lanes intersected to it. The vehicles initiate the trip sents the lane connected by at most two intersections. Edges
randomly from the edges and take the shortest route to reach are connected directly in a spatiotemporal region to define an
the corresponding destination. All the scenarios have identical intersection and each lane is fixed with a lane maximum speed.
49 nodes, in which 14 nodes are selected as origin were the The base-platform model is installed in every lane to compute
vehicles started their trip to defined 28 destinations. the congestion value CR individually. CPI is set as a bench-
mark for every lane to detect congestion a priori. During the
simulation, the congestion value CR is computed dynamically
VII. E STIMATION OF C ONGESTION P ROPAGATION for every lane based on histogram model and compared with
The congestion that happens in urban areas is usually the CPI value.
dynamic in nature and mainly based on the lane level implica- If the CR value exceeds the benchmark CPI index it is an
tion. The volatility of drivers and high dynamic movement of indication for congestion likely to occur in that particular lane.
traffic in network, makes the estimation task complicated. If This strategy will help to distinguish the congested lanes from
congestion persists for a long time it propagates to its adjacent free flowing lanes. By this differentiation, we classify the lanes
lanes and further makes congestion worse. To avoid further in two categories: 1) group A and 2) group B. Initially, all
congestion, the lanes that will be congested in near future the lanes are marked as UL and stored it in group A. Every
should be detected in prior and the vehicles can be rerouted to 5 min, a new histogram is built for every lane and the

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
EL-SAYED AND THANDAVARAYAN: CONGESTION DETECTION AND PROPAGATION IN URBAN AREAS USING HISTOGRAM MODELS 3679

Fig. 11. Grid scenario for congestion propagation.

overlaid with the main streets of the city. The histograms were
built for every five minutes and the CPI is used to predict for
the congested lane. The results obtained were promising and
show the starting point of congestion where it actually initi-
ated as shown in Fig. 12(a)–(f). The traffic of every lane can
be identified over the period of time by analyzing the scatter
diagram, this can be further used to find the capacity of every
lane and helpful for rerouting strategy in order to avoid the
congestion.
Fig. 10. Flowchart for detecting congested neighbor lanes.

VIII. R EROUTING S TRATEGY

If a traffic jam exists in a lane, it can be accumulated grad-
corresponding CR value is computed and compared with the ually and would spread through other lanes following latent
benchmark CPI value. If the lane CR value exceeds the bench- periods. If a lane is identified to become congested in near
mark index, the lane is marked as congested and moved to future, the vehicles ingress to the lane are to be rerouted with
group B. From group B, a lane is selected and the adjacent some intelligent measures. This could avoid the lane to be
intersections Vi and Vj are identified. Moreover, every lane E further congested and takes minimum time to recover from
connected to the nodes Vi and Vj is identified and its corre- the congestion. In our model, initially the vehicles are travel-
sponding CR value is compared with the benchmark CPI. If ing from source to destination using Dijkstra’s shortest path,
the congestion is detected the lane is moved to group B. and the lanes are given equal weightage. If all the routes are
This process is repeated for every 5 min and congestion stable without congestion, the rerouting strategy stays dor-
propagation is recorded. Fig. 10 shows the flowchart for the mant. If there is a commensurate rise in the CR value for
detection of congested lanes and the prediction of congestion a particular lane, it is an alarm that the lane likely to get con-
propagation. gested soon. Thus a reroute strategy is initiated which uses
Initially, the single lane roads of 1 km length are created the entropy-based backtracking heuristic algorithm [21] to find
using 7 × 7 roads connected with the intersections as shown the efficient alternative route to destination. To avoid further
in Fig. 8. To achieve the urban traffic behavior, the vehicles congestion, the reroute strategy employs to monitor the entire
injection frequency is randomly created with different patterns network on the window basis and update the CR value index
of platoons, and each platoon will range from 2 to 8 vehicles. value periodically.
The simulation runs for 30 min and the congestion propagation Initially, all the vehicles traveling in the network will have
is computed for individual lanes with 5-min time interval and predefined routes based on the Dijkstra’s SPA. Information
the contour diagram is plotted as shown in Fig. 11. From like the average travel time and the number of intersections is
the graph, we can estimate the initial congestion happens in the known. Once the vehicles start their trip randomly, the con-
base of the grid network and propagates backwards during the gestion starts to build up slowly. When the system detects
course of time. congestion in a lane based on the CR value, the congestion
A more realistic approach for the city of Al Ain is used for propagation is estimated. From the congestion propagation
analyzing the congestion propagation. The downtown of the model, we identify the lanes that are likely become congested
city is captured using the OpenStreetMap application and sim- in near future. The weightage of lanes is increased for the
ulated in SUMO for 60 min. More specifically, the behavior congested lanes and the predicted lanes. The routing informa-
of the peak hour is taken into consideration and the vehicle tion is revised for every vehicle and a new route is estimated
platoons were created to serve the nature of the traffic behav- based on the back tracking algorithm. The proposed algorithm
ior. The route is modeled with great detail to have the real checks the lane weightage and avoids lanes with high weigh-
time envision of the congestion propagation that particularly tage in the route computation. The new average travel time

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
3680 IEEE INTERNET OF THINGS JOURNAL, VOL. 5, NO. 5, OCTOBER 2018

Fig. 13. Average travel time.

Fig. 12. Congestion propagation in Al-Ain city center during six 10-
min observation intervals. (a) 0–10 Min. (b) 10–20 Min. (c) 20–30 Min.
(d) 30–40 Min. (e) 40–50 Min. (f) 50–60 Min.
time of every vehicle from source to destination is computed
and shown in Fig. 13. As the proposed model uses the heuristic
is computed based on the new route and compared with the backtracking algorithm for the rerouting, the travel time taken
existing route. If the new average travel time is less than the by every vehicle is minimum, when compared with the RkSP,
existing travel time the vehicles are recommended to take as shown in Fig. 13. The results show that the proposed model
the alternate path. establishes the rerouting strategy effectively and thus reducing
the trip time of vehicles.
By this analysis, an alternate route with minimum travel
time will be selected for rerouting the vehicles. The next sec-
tion will perform the comparative study with the other existing
models with different scenarios.

IX. E XPERIMENT R ESULTS

In this section, we compare the proposed algorithm with two
different existing algorithms: 1) IVC [23] and 2) HBA [24].
Three different scenarios with: 1) varying source volume;
2) varying link speed; and 3) varying link length are created
to measure the average travel time of the vehicles.

A. Source Volume Scenario

The experiment is carried out with various source rates that
vary from 500 to 2000 vehicle/h. The maximum speed limit
for every lane is fixed at 80 km/h. The vehicles are created
randomly using 14 origins which closely mimic with the real
time environment. The vehicle platoons are created at the start-
ing point of the lane; however, they may change during the
course of the trip time by various factors. All trip parameters
of every vehicle (destination, speed, and type) are stored into
the OD matrix and given as input to the simulation. The sim-
In order to verify the effectiveness of the rerouting strategy, ulation ran for 60 min and the average travel time from source
we employ the proposed model in the SUMO simulator and to destination is recorded for every vehicle.
compare it with an existing model in literature called random K The proposed model uses Dijkstra’s algorithm to find the
shortest path (RkSP) [22]. Initially, the map for downtown of shortest path from source to destination until the congestion
Al Ain city was downloaded from OpenStreetMap as an osm happens, then the rerouting strategy is initiated to avoid fur-
format, then it is converted to SUMO application format using ther congestion. The performance of the proposed algorithm is
a command line application called Netconvert and Polyconvert. compared with the existing algorithms as shown Fig. 14. The
A fixed volume of 1000 cars will be randomly generated and recorded average travel time shows that the proposed algorithm
the simulation run is fixed for 1000 s. The average traveling gives better results than the HBA and IVC algorithm.

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
EL-SAYED AND THANDAVARAYAN: CONGESTION DETECTION AND PROPAGATION IN URBAN AREAS USING HISTOGRAM MODELS 3681

Fig. 14. Source volume scenario.

Fig. 17. Performance comparison with SPA—source volume scenario.

Fig. 15. Link speed scenario.

Fig. 18. Performance comparison with SPA—link speed scenario.

to the 28 destinations. The simulation ran for 60 min and the

average travel time of vehicles is recorded. From the results
shown in Fig. 15, it is clearly evident that the proposed algo-
rithm has better results for different lane speed when compared
with the existing ones.

C. Link Length Scenario

In this experiment, three different scenarios were created
with different lane lengths. The lane speed is kept at 80 km/h
in all scenarios, the source volume demand rate is fixed at
2000 vehicle/h, and the simulation is run for 60 min.
Fig. 16 shows that the proposed algorithm makes the con-
gestion to be abated for every lane and makes the total
Fig. 16. Link length scenario.
traveling time less when compared with two other existing
algorithms. The above scenarios clearly show that the proposed
B. Link Speed Scenario algorithm performs better than the existing ones.
In urban areas, the lane speed is almost the same for all
roadways connecting with each other, however, the speed limit D. Comparing With Optimal Algorithm SPA
will vary from region to region. It makes the interesting factor To check the robustness and efficiency of the proposed
to measure the impact of speed limit in urban areas. In our model, we compare it with the optimal dynamic SPA. The
scenario three different speed limits were set to lanes in the SPA is a theoretical model that provides the optimal solution
grid network form 60, 80, and 100 km/h. The source volume is for the congestion problem. Nevertheless, it assumes the avail-
fixed as 2000 vehicle/h for all the three scenarios, the vehicles ability of all information about the road traces. This is practi-
were injected randomly from 14 origins and equally distributed cally impossible using current technology as it demands very

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.
3682 IEEE INTERNET OF THINGS JOURNAL, VOL. 5, NO. 5, OCTOBER 2018

[2] C. Buchanan and S. Gunn, Traffic in Towns: A Study of The Long Term
Problems of Traffic in Urban Areas. London, U.K.: Routledge, 2015.
[3] D. Schrank, B. Eisele, and T. Lomax, “Urban mobility report: Powered
by INRIX traffic data,” Texas A&M Transp. Inst., Texas A&M Univ.
Syst., College Station, TX, USA, Tech. Rep. SWUTC/15/161302-1,
2015.
[4] Road Traffic Authority. Traffic Congestion Costs More Than Dh
700,000 Per Kilometer in Dubai. Accessed on Feb. 7, 2015. [Online].
Available: http://gulfnews.com/news/uae/traffic-congestion-costs-more-
than-dh700-000-per-kilometre-in-dubai-1.1452783
[5] T. Sugiyama et al., “Adverse associations of car time with markers of
cardio-metabolic risk,” Prev. Med., vol. 83, pp. 26–30, Feb. 2016.
[6] H. El-Sayed, L. Zhang, Y. Hawas, and H. El Kassabi, “A histogram-
based model for road traffic characterization in VANET,” in Proc. Int.
Conf. Internet Veh., Beijing, China, Aug. 2014, pp. 42–55.
[7] Navigation Fusion Platform. Accessed on Jun. 10, 2016. [Online].
Available: http://www.nng.com/navfusion-platform
[8] IGo Navigation. Accessed on Mar. 19, 2016. [Online]. Available:
http://www.igonavigation.com
[9] Google Auto. Accessed on Apr. 20, 2016. [Online]. Available:
https://www.android.com/auto
[10] I. Leontiadis et al., “On the effectiveness of an opportunistic traffic
Fig. 19. Performance comparison with SPA—link length scenario. management system for vehicular networks,” IEEE Trans. Intell. Transp.
Syst., vol. 12, no. 4, pp. 1537–1548, Dec. 2011.
[11] Z. Wang, M. Lu, X. Yuan, J. Zhang, and H. van de Wetering, “Visual
powerful resources and high implementation cost. We compare traffic jam analysis based on trajectory data,” IEEE Trans. Vis. Comput.
the performance of our proposed algorithm with that of the Graphics, vol. 19, no. 12, pp. 2159–2168, Dec. 2013.
SPA to show that the proposed model achieves close to opti- [12] G. Marfia and M. Roccetti, “Vehicular congestion detection and short-
term forecasting: A new model with results,” IEEE Trans. Veh. Technol.,
mal performance with very less resources. Figs. 17–19 clearly vol. 60, no. 7, pp. 2936–2948, Sep. 2011.
show that our proposed model performs closely to the opti- [13] F. Terroso-Saenz, M. Valdes-Vela, C. Sotomayor-Martinez,
mal theoretical model (SPA), under different scenarios. Since R. Toledo-Moreo, and A. F. Gomez-Skarmeta, “A cooperative approach
to traffic congestion detection with complex event processing and
the proposed algorithm use histogram models to characterize VANET,” IEEE Trans. Intell. Transp. Syst., vol. 13, no. 2, pp. 914–929,
traffic and estimate congestion, the resource utilization and Jun. 2012.
[14] S. Skone, M. El-Gizawy, and S. Shrestha, “Limitations in GPS posi-
time-delay are effortlessly reduced. Further, the reroute strat- tioning accuracies and receiver tracking performance during solar
egy is established only if the lane exceeds the CPI value. This maximum,” in Int. Symp. Kinematic Syst. Geomat., Navigat., Banff, AB,
makes the system more robust and free from getting choked Canada, Jun. 2001, pp. 5–8.
[15] A. M. Voorhees, “A general theory of traffic movement,” Transportation,
at some point. By its erudite, and smart precautious mea- vol. 40, no. 6, pp. 1105–1116, 2013.
sure to avoid congestion, the proposed model can be widely [16] K. H. Knuth. (2000). Optimal Data-Based Binning for Histograms.
implemented in urban areas. [Online]. Available: http://adsabs.harvard.edu/abs/2006physics
[17] M. Boullé, “Functional data clustering via piecewise constant
nonparametric density estimation,” Pattern Recognit., vol. 45, no. 12,
X. C ONCLUSION pp. 4389–4401, 2012.
[18] R. Bauza, J. Gozalvez, and J. Sanchez-Soriano, “Road traffic conges-
In this paper, a novel congestion detection schema tion detection through cooperative vehicle-to-vehicle communications,”
and rerouting algorithm are presented based on histogram in Proc. IEEE 35th Conf. Local Comput. Netw., Denver, CO, USA, 2010,
pp. 610–612.
modeling and the base platform concept. The detection scheme [19] B. Jiang, J. Pei, Y. Tao, and X. Lin, “Clustering uncertain data based
can be implemented effectively in real time with less resource on probability distribution similarity,” IEEE Trans. Knowl. Data Eng.,
vol. 25, no. 4, pp. 751–763, Apr. 2013.
utilization. Using the proposed scheme, we predict the lanes [20] M. Behrisch, L. Bieker, J. Erdmann, and D. Krajzewicz, “Sumo–
that could be congested in near future and estimate the simulation of urban mobility,” in Proc. 3rd Int. Conf. Adv. Syst. Simulat.,
congestion levels. To make the system more efficient, a rerout- Barcelona, Spain, 2011, pp. 63–68.
[21] H. El-Hussieny, S. F. Assal, and M. Abdellatif, “Robotic exploration:
ing strategy based on heuristic backtracking algorithm is New heuristic backtracking algorithm, performance evaluation and
employed to reroute the vehicles away from potential con- complexity metric,” Int. J. Adv. Robot Syst., vol. 12, no. 4, p. 33,
gestion. Furthermore, the rerouting scheme avoids further Apr. 2015.
[22] J. Pan, M. A. Khan, I. S. Popa, K. Zeitouni, and C. Borcea, “Proactive
congestion by utilizing the ULs during the recovery time. vehicle re-routing strategies for congestion avoidance,” in Proc IEEE
This countermeasure activity enables the proposed algorithm 8th Int. Conf. Distrib. Comput. Sensor Syst., Hangzhou, China, 2012,
to guide vehicles to choose the best path with minimum travel pp. 265–272.
[23] Y. E. Hawas and H. El-Sayed, “Autonomous real time route guidance in
time. The simulation results show that the proposed approach inter-vehicular communication urban networks,” Veh. Commun., vol. 2,
outperforms the existing approaches in literature. This proac- no. 1, pp. 36–46, 2015.
tive approach along with the VANET technology can carry [24] H. El-Sayed, L. Zhang, G. Thandavarayan, and Y. Hawas, “HBA-
histogram based algorithm for real time route forecasting in urban area,”
out the congestion problem effectively and keep the resource in Proc. IEEE Int. Conf. Commun., Kuala Lumpur, Malaysia, May 2016,
utilization at minimum. pp. 1–6.
[25] Y. E. Hawas, “A microscopic simulation model for incident modeling in
urban networks,” Transp. Plan. Technol., vol. 30, nos. 2–3, pp. 289–309,
R EFERENCES 2007.

[1] A. Elkafoury, A. M. Negm, M. H. Aly, M. F. Bady, and T. Ichimura, Hesham El-Sayed, photograph and biography not available at the time of
“Develop dynamic model for predicting traffic CO emissions in urban publication.
areas,” Environ. Sci. Pollution Res., vol. 23, no. 16, pp. 15899–15910, Gokulnath Thandavarayan, photograph and biography not available at the
2016. time of publication.

Authorized licensed use limited to: Univerdad Miguel Hernandez. Downloaded on April 20,2024 at 09:17:15 UTC from IEEE Xplore. Restrictions apply.