Found in the shuffle

Researchers see if a system in which vehicles collect and share traffic information can improve the performance of the entire network

Transportation Management Article May 14, 2015
Printer-friendly version

Road congestion results in a huge waste of time and productivity for millions of people. In 2005, traffic congestion cost an estimated $78.2 billion in 437 urban areas in the U.S., according to the Texas Transportation Institute’s 2007 Urban Mobility Report. The travel-time index, which is the ratio of travel time in rush hours to travel time at quiet periods, has increased from 1.09 in 1982 to 1.26 in 2005.



This trend has led to the development of intelligent transportation system (ITS) technologies. Most of these systems allow transportation authorities to collect both real-time and historical traffic information in order to load-balance traffic during peak times. Such traffic information is usually gathered by relying on static sensors, such as induction loops and video cameras, placed at specific road locations. Afterward, traffic updates can be used to modify traffic light priorities or can even be directly distributed to the drivers (e.g., via radio traffic reports, traffic management center broadcasts).


During the last few years, a wealth of research has studied how to optimize the internetworking of vehicles utilizing short-range radios (e.g., WiFi and dedicated short-range radios). This will enable vehicles to directly communicate between each other (V2V) or with roadside fixed infrastructure (V2I). These vehicles can then form a special class of wireless networks, known as vehicular ad-hoc networks (VANETs). Researchers and the automotive industry are envisioning the deployment of a large spectrum of applications running on VANETs, including road-safety systems, vehicle coordination platforms, notification services to warn drivers about accidents, etc.


VANETs can also contribute toward alleviating traffic congestion. In particular, ITSs could benefit from the use of VANETs by enabling every vehicle to act as a traffic probe that measures and afterward spreads traffic-related information.


Clearly, the advantages deriving from the deployment of VANET-based ITSs are manifold. Many more streets than those nowadays equipped with a monitoring infrastructure could be easily observed without requiring additional costs. Currently, only major urban areas can afford monitoring infrastructure. Furthermore, many more services that may utilize the same VANET infrastructure could be provided (e.g., pollution management and accident prevention), requiring only limited additional investments.


While cellular networks can be used to offer some of these services, this solution can also create a number of issues. First, the service providers in each country impose different rules and restrictions as to what kind of data can be exchanged through their network or even what type of applications can access it, making it impossible for vehicular applications to be globally deployed (e.g., at least a per-country agreement will be required).


Additionally, the cost of cellular data communication is restrictively high, as it can reach a few pence per kilobyte. Even expensive “unlimited” plans are usually capped to a few gigabytes per month, making large-scale communication (such as real-time, fine-grained traffic information) between millions of vehicles unfeasible. Furthermore, although third-generation (3G) connections can support up to 128 kilobytes/sec inside a moving vehicle, the bandwidth is shared between all users inside the cell. Even today, when 3G is not widely used, the network is swamped by traffic, resulting in very low throughput in densely populated areas. Finally, ad hoc connectivity is more sensible to disseminate local information such as local traffic updates.


Satellite navigation systems (SatNavs) can be aided in navigation by continuously assessing and correcting the best route prediction to a destination based on the information that is collected via the VANET. To do this, each vehicle should be capable of sensing, aggregating and sharing traffic information with neighboring vehicles. Furthermore, a vehicle should be able to dynamically recompute the fastest route to its destination based on the information that each one individually collected. Therefore, a navigation system essentially becomes an element of a distributed system that cooperatively collects and exchanges
traffic conditions and, at the same time, a sophisticated traffic estimator, based on the flow of real-time information.


Recently, researchers from the University of Cambridge, University of Bologna and University of California Los Angeles, developed a VANET-based ITS, named CATE, with the goal of evaluating its feasibility and performance. CATE allows vehicles to crowd-source traffic information. It is composed of three core modules: traffic sensing, traffic information dissemination and traffic estimation.


Traffic sensing

Each vehicle acts as a traffic sensor. Travel delay is widely accepted as one of the most effective measures of the degree of congestion. The Global Positioning System (GPS) and the local map can be used to measure the time that a vehicle requires to traverse a road segment. In CATE, every time a vehicle exits a road segment, it creates a traffic sample. Therefore the vehicular navigation problem is modeled as a weighted graph: street sections are links, intersections are nodes and a link’s weight is given by the time required to traverse it.


Traffic information dissemination

Vehicles exchange the sampled information in an ad hoc manner. The appropriate traffic information should reach the right vehicles with the minimum delay. Excessive redundancy risks congesting the feedback channel; too little can lead to uninformed decisions. Gossip-based routing schemes are very effective in disseminating large amounts of information in dense networks: periodically each vehicle selects a subset of the information that is available and exchanges it with its neighbors. One-hop neighbors will combine the received information with what they already know and later spread it even further.


A key element of the dissemination module is the sample selection algorithm: how to select which subset of information to broadcast, assuming only a fraction of a vehicle’s knowledge can be sent within given bandwidth restrictions. Therefore, CATE uses a number of mechanisms to prioritize and aggregate the samples. To make these decisions, each sample is ranked with the help of a utility function, which is a metric that represents the effectiveness of each sample for a given geographic area. Afterward, the K samples with the highest utility are broadcast to the neighbors.


Traffic estimation

Finally, each vehicle independently evaluates the traffic conditions based on the traffic samples received through the network. Raw samples are filtered and transformed in correct traffic estimates about the current and possibly future conditions.


The problem of estimating traffic conditions based on the collected samples is not trivial. Firstly, there might be noise in the observations. Although traffic conditions do not rapidly change over time (a traffic jam’s dynamics are relatively slow), measurements might have significant deviations as vehicles may drive at a different pace. For example, some vehicles may stop at a traffic light or to pick up a passenger, whereas other vehicles might just rush through the street segment. The result is that samples may significantly vary, although collected close in time.


Secondly, samples may be received at different rates for a given area. For example, a vehicle may receive multiple old samples and just a few fresh samples. One key problem is how to weigh this information (age of samples) to calculate the best possible estimation of the current conditions.


Thirdly, the last issue is how to treat the absence of information when no recent information may be received for some road sections. CATE uses a number of solutions to interpret the collected samples and to provide an accurate estimation of the current traffic conditions.


Finally, CATE enables each vehicle to independently re-evaluate the estimated traffic conditions and dynamically reroute around traffic congestion. A modified version of Dijkstra’s algorithm is periodically used on the traffic estimation graph.


However, although there is a general consensus about the role ITSs may play in reducing traffic, such systems are not necessarily guaranteed to succeed in reducing congestion. There has been some debate on whether these high-tech systems actually work, that is, whether they minimize the overall average travel time of all vehicles in a traffic network. Some studies during the past several decades have shown that even having perfect traffic information (i.e., all vehicles have a complete knowledge of traffic at all times) does not necessarily guarantee lower congestion. Furthermore, VANET-based ITS systems require further assessments, as their beneficial effects on traffic conditions are not yet fully understood. In fact, in a fully decentralized ITS, each vehicle bases its own traffic knowledge and routing decisions on only partial data, as only part of the generated traffic information could be received.


In this context, the main focus of the researchers was to examine the effects of such a distributed system on traffic. An evaluation platform was implemented that is based on two realistic simulators: (1) a mobility simulator that is able to simulate thousands of vehicles on real maps, and (2) a network simulator that is used to build the mobile ad hoc network using short-range radio communication.


These two simulators constantly interact and depend, at each step, on the output of each other. Future mobility decisions are influenced by the network dissemination (e.g., collected information), and the network dissemination is influenced by the mobility patterns (location and previous route of the vehicles). A real urban topology and realistic traffic flows were used to evaluate this system. In fact, origin–destination pairs of all vehicles were derived from large-scale surveys on the population of Portland, Ore. Finally, as demonstrated by experiments at UCLA’s Campus Vehicular Testbed (C-VeT), the low data rates that the technology requires can easily be supported by personal wireless devices.


More specifically, the researchers evaluated various algorithms that can be used to collect and disseminate the information, to predict the traffic conditions and to dynamically reroute the vehicles. Their results show that, with the best algorithms, 64% of vehicles reduced their travel time by more than 10%. Of the rest, 23% had trip times within 10% of their times without the information (and so were considered to not really be affected), and the remaining 13% required more time than without the information.


The researchers attribute the increased time to the fact that some traffic was being diverted into relatively open roads that consequently became busier than before. Still, the overall average trip time was significantly reduced when the CATE navigation system was used. The researchers also found that, when just 34% of the vehicles used CATE, the performance of the traffic network was comparable to the performance when up to 100% of the vehicles used the system.


The results show that such a system, in which vehicles collect and share traffic information with each other, can decrease the average travel time of all vehicles in a traffic network. In contrast to some of the previous studies, this study dealt with a fully decentralized, crowd-sourced system rather than sensors located at specific road locations. It also tested the system using real-life experiments and simulations of more complex, realistic traffic flows compared with the simpler models in previous studies.


The fact that CATE can be deployed with off-the-shelf equipment and the computation power available in any navigation system or personal digital assistant makes such systems quite appealing. Moreover, the bandwidth provided by available wireless technologies is more than sufficient to support the low data rates that such a system would require.


These results could lead to significant economic savings. This study also opens up new research directions, such as investigating the impact of different algorithms and flow intensities on the average travel time. Other areas for improvement include better algorithms, ways to lower bandwidth and implementing various mechanisms to tackle possible security and privacy issues. TM&E

About the author: 
Leontiadis is a research associate with the Computer Laboratory, University of Cambridge, Cambridge, U.K. Marfia is a postdoctoral research fellow with the Department of Computer Science, University of Bologna, Bologna, Italy. Mack is also with the Comput
Overlay Init