Vehicular Ad hoc NETworks (VANETs) are a subclass of Mobile Ad hoc NETworks (MANETs) and represent a relatively new and very active field of research. Some particular characteristics of VANETs that make them unique are high-speed mobility, driver behavior depending on personality traits, and mobility constraints as cars move on roadways with set boundaries. VANETs will enable in the near future applications that will dramatically improve roadway safety and traffic efficiency and significantly improve the associated ecological impact. According to the Federal Highway Administration (FHWA) [1], the U.S. highway network was near completion by the late 1980s, there has been little construction of new roads and highways and the number of lane miles has been increased mainly by adding additional lanes to existing highways to carry more vehicles. From 1985 to 2006 the lane miles increased from 8 to 8.4 million while during the same period the vehicle miles traveled has doubled. From these figures and the familiar transit congestions that take place almost daily, it is clear that a new and intelligent approach is needed for optimizing road usage. Traffic assignment tries to distribute vehicles efficiently on the road network and in accordance with their origins and destinations [2-16]. Ant Colony Optimization (ACO) is a methaheuristic useful for obtaining minimum cost paths [17-24]. This methaheuristic has been applied successfully in different branches of engineering [25-35]. ACO has gained popularity recently for traffic assignment and many algorithms have been inspired by this metaheuristic [36-47]. In this paper we present a novel dynamic traffic assignment algorithm for VANET environments. The ACO inspired algorithm is decentralized and infrastructure-less. The algorithm employs a unique on the fly cluster system that minimizes maintenance overhead as clusters are formed just to report traffic incidents and vanish after the incident is reported. The algorithm avoids broadcast storm by blocking additional reports on the same road segment in a given aggregation period by setting a speed threshold in order not to report every speed reduction in the segment and by reporting only bad traffic conditions. The ant inspired algorithm differs from traditional ACO algorithms as ants know the whole road network map, are able to broadcast pheromone, and pheromone is used to mark bad trails. The rest of this paper is organized as follows. In Section 2, we introduce relevant related work. Section 3 presents an overview of traffic assignment. Section 4 introduces ant colony optimization and some of its applications. The proposed algorithm is presented in Section 5. The simulation setup is explained in Section 6. The results and analysis are presented in Section 7. Finally the conclusions are included in Section 8.

Traffic assignment is the process of assigning the traffic demand to the routes on a road network. Wardrop [2] defined two equilibrium criteria for the traffic flowing from a set of origins to a set of destinations: user equilibrium assignment (UE) and system Optimum Assignment (SO), depending on whether we optimize from the user’s point of view or from the system’s point of view. These criteria are also referred to as deterministic user equilibrium assignment (D-UE) and deterministic system Optimum Assignment (D-SO). Traffic assignment is commonly modeled by means of two different mathematical formulations, the static traffic assignment (STA), and the dynamic traffic assignment (DTA) depending on whether the traffic flow is constant or time dependent. An STA model for both Wardrop's principles was first presented in [3]. DTA originated from the seminal works of Yagar in 1971 [4,5], and Merchant and Nemhauser in 1978 [48,6]. DTA problems can be classified as mathematical programming formulations, optimal control formulations, variational inequalities formulations, and simulation-based models [6]. Heuristic approaches and simulation-based models are used in pursuit of realistic traffic solutions. Of great importance are the probabilistic or stochastic heuristic methods that in general provide more accurate results than the deterministic counterparts [7]. Achieving UE analytically is in general a very difficult task unless some simplifications are made. The Stochastic Network Loading (S-N-L) type of problems assumes that the measured travel times are independent of the link flows [7]. S-N-L problems can be approached with analytical methods [8] or by stochastic simulation [9]. Totally different approaches that do not make this assumption are based on the ants foraging behavior [17]. An Ant Colony Optimization (ACO) model using multiple ant colonies, one colony for every origin destination pair is used in [36] and [37], where stochastic user equilibrium (S-UE) algorithms for the fixed-point traffic assignment problem are proposed. Information on transportation fixed-point problems can be found in [10,16]. Approaches based on Ant Colony System (ACS) are presented in [38,49], for both S-UE and D-UE. An ACO approach for solving the Local Optimization of Signal Settings (LOSS) is presented in [39]. This problem deals with the local optimization of traffic light signals based on the vehicle route choices and the traffic flow on that particular intersection. An ACO algorithm for the Vehicle Routing Problem is presented in [41]. So far all of these ant-inspired algorithms are intended for the STA and there is a need for algorithms for the DTA. [40] Presents an ACO based algorithm for DTA by routing vehicles at intersections. However, this algorithm is centralized. Centralized algorithms for VANETs require the existence of an infrastructure that may not always be available and suffer from great computational complexity. Claes et al. [42] presents a DTA approach based on ACO inspired agents representing vehicles and roads. This system is decentralized but requires infrastructure. In [43] a local control of traffic lights is proposed along with an infrastructure supported, cluster organized system, where vehicles use ACO inspired algorithms for routing. In [44] a centralized system is proposed where ants going from a given origin to a destination select the 5 best routes and update pheromone just in those routes. In case of congestion ants choose alternate best routes until the situation is resolved. Tatomir et al., [45] presents a DTA system where the road map is divided into zones in a hierarchical way. Vehicles interchange information with infrastructure to allow travel time estimation and best route selection by ACO. In [46] two strategies to avoid congestion are presented using pheromone marks on a decentralized system of servers. [47] presents an infrastructure supported dynamic routing system to replace static routing such as Dijkstra's. The intersections contain routing tables based on history and on cars in the simulation. In Table 1 we illustrate the advantage of the proposed algorithm. The algorithm we present in this paper is for the DTA and is decentralized and infrastructure-less.

Table 1: Comparison of different ACO inspired algorithms with the proposed algorithm.

The road network is represented as a graph G = (N,L), where vector N represents the nodes (intersections) and vector L represents the links (lanes). For each arclεL we define the free travel time, as the minimum travel time required when traversing a at the maximal allowed speed. We represent with OD ⊂ N x N the set of fixed origins and destinations the road network. We use od to denote an origin destination pair, od ⊂ OD, and R_od to denote the set of all routes or paths that connect the origin of od with its destination. A route is an ordered sequence of consecutive links connecting the origin of certain od to its destination, where the end node of any link coincides with the start node of the next link. We represent road segments with edges. We define edge as a set of lanes, which physically run in parallel next to each other, connecting two adjacent nodes. As in real life, edges may include lanes with traffic flow in opposite directions.

Traffic assignment

There are two different models that can be identified when investigating road networks transit problems, the transportation planning models and the traffic flow models [11]. Transportation planning models deal with modeling the route and schedule decisions made by individuals who use the roads and the approaches used by researchers to optimize traffic. Traffic flow models deals with modeling the physical propagation of traffic flows. As physical tests can be difficult and expensive to implement Traffic flow models are used for testing the new traffic solutions proposed by researchers. When selecting the best routes in traffic assignment it is typical to assign a cost based on distance and/or time to the different edges and then use a shortest path algorithm such as Dijkstra’s algorithm [50]. Wardrop [2] established two equilibrium criteria relating to the traffic flow from a given origin to a certain destination using the available routes:

User equilibrium assignment (UE). The journey times on all the routes actually used are equal, and less than those which would be experienced by a single vehicle on any unused route [2].

System Optimum Assignment (SO). The average journey time is minimum [2].

These criteria are also referred to in the literature, as deterministic user equilibrium assignment (D-UE) and deterministic system Optimum Assignment (D-SO). In Figure 1 we can see this classification. We could say that in D-UE all decisions are made in an egoistic and rational way and all users have knowledge of the paths costs. In D-SO there may be cooperation among individuals or a centralized system coordinating the route assignment.

Figure 1: Traffic Equilibrium Classification.

The optimization of transportation on a road network is commonly formulated by means of two different mathematical formulations, the static traffic assignment (STA), and the dynamic traffic assignment (DTA). The STA approach deals with networks in equilibrium where the traffic demand and the edge flows are constant over time. On the other hand, the DTA deals with the more realistic situation of time dependent edge flows and congestion.

The static traffic assignment

The Static Traffic Assignment (STA) assigns routes to a set of drivers with fixed origins and destinations under steady state flow conditions. A model of the equilibrium assignment for both Wardrop's principles, the UE and the SO, was first presented by Martin Beckmann, Bartlett McGuire and Christopher Winsten (BMW) [3]. This solution became a standard in transportation planning since it was introduced. Currently as new approaches have emerged. Solutions based on dynamic traffic assignment have become available for dealing with congestion and variable conditions.

The dynamic traffic assignment

The dynamic traffic assignment (DTA) refers to a broad variety of problems that deals with time-varying flows and originated with the seminal works of Yagar in 1971 [4,5], and Merchant and Nemhauser in 1978 [6,48]. These models aim at representing the interaction between route choices, traffic flows, and time and cost metrics in a coherent fashion as time passes [12]. DTA problems can be classified as [6] mathematical programming formulations, Optimal control formulations, variational inequalities formulations, and Simulation-based models [6]. The first three types of approaches suffer from problems induced by the algorithms such as artificial delays at junctions [6,13], and first in first out (FIFO) violations [6,13,14]. These problems are not consistent with traffic realism [6]. Simulation-based models utilize traffic flow propagation models to model the critical constraints that regulate traffic flow. The simulation is used as an approach to produce realistic solutions that satisfy the FIFO constraint and prevent the artificial delays.

Heuristic stochastic approaches

Heuristic methods can be used for both STA and DTA. Much effort has been dedicated to heuristic approaches. These approaches can be subdivided into deterministic and probabilistic or stochastic methods. The first type usually fails on uncongested road networks where stochastic approaches provide more accurate results [7]. A new equilibrium criterion is needed for these approaches, the stochastic user equilibrium (S-UE). For the traffic flow from a given origin to a certain destination using the available routes, in S-UE no user believes he/she can improve his journey time by unilaterally changing routes [7]. In an S-UE system the vehicles have access to a graph representing the network where the edge costs are represented by a vector of stochastic and unobserved perceived travel times. In general these edge travel times may change in time and differ from vehicle to vehicle. Achieving UE analytically is in general a very difficult task unless some simplifications are made. For example, the Stochastic Network Loading (S-N-L) problems assume that the measured travel times are independent of the edge flows [7].

Simulation-based models are used to model realistically the critical constraints that regulate traffic flow. Social insects exhibit efficient behaviors for path selection [18], next we present Ant Colony Optimization (ACO), a metaheuristic that has proved to be useful in determining minimum cost paths [17] and may be used in simulation-based models.

Ant Colony Optimization (ACO) is a relatively new metaheuristic based on the social behavior of ants. These insects are very efficient in finding the best path/food-source combination. Their interesting methods are based on individuals with simple behaviors that interchange information indirectly by means of chemical compounds (pheromones) they use to mark their paths. Ant colony optimization was introduced by M. Dorigo and colleagues [19-21]. According to [21], this new metaheuristic was greatly inspired by the behavior of real ants [22-24]. Great effort has been dedicated to ACO applications in computer science and engineering. Several ACO algorithms have been proposed for the Traveling Salesman Problem (TSP) [25,26]. ACO approaches for the Job Shop Scheduling Problem (JSSP) and the Flexible Job Shop Scheduling Problem (FJSSP) have applications in controlling mechanical engineering machines [27,28]. ACO algorithms have been used in civil engineering for economic optimization of reinforced concrete [29].

Research in Ant Colony Optimization has also been conducted in digital image processing [30], electrical engineering where a system has been proposed for environmental/economic dispatch [31], as well as several routing protocols in computer engineering [32,33]. More information on ACO applications can be found in [34,35].

When natural ants are faced with a food source that can be reached only by crossing one of two bridges of different length, they usually choose the shortest bridge. At the beginning some ants may use the shortest bridge and others may choose the longest one. As the ants walk they drop pheromones to mark the path. Ants that started the shortest way will arrive earlier at the food source and will return following the scent on the trail they used while they drop more pheromones increasing the scent on the shortest trail faster. For the ants starting the process, the stronger scent will orient them towards the shortest path. The process is a little bit more complex and is affected by factors such as evaporation, dropping frequency modulated by the quality of the food source, system feedback, and sensors imperfection, among others. Evaporation is an important component that helps minimize the impact of wrong decisions and may also decrease interest on a route in case of food depletion.

The path selection mechanism has inspired software approaches with artificial ants for problems where a minimum cost path solution is required both in communications and in road networks [32,41]. The artificial ants travel the network and update the nodes information with artificial pheromone that can be sensed by other ants to make routing decisions. It is common that artificial ants mark the information of the arcs they visited only on the way back to the source according to equation (1). In this equation the pheromone concentration from node i to node j at node i, τ_ij, is updated by the traveling ant kwith pheromone deposit Δτ^kafter evaporation coefficient ρ is applied.

We propose a novel algorithm, Reverse Online Algorithm for the Dynamic-Traffic-Assignment Ant-Colony-Optimization inspired (Road-ACO) that assigns traffic as it evolves in real time, without prior knowledge of the traffic demand or the schedule of the cars that will enter the road network in the future. This novel decentralized online algorithm employs a new breed of ants which are position aware, capable of broadcasting pheromone information, have the road map in memory along with perceived edge costs, and execute shortest path algorithms in a selfish manner consistent with S-UE, just like a VANET enabled car. Additionally these ants differ from the traditional ants by the reverse way they use pheromone. Higher intensity indicates road segments of lesser quality, in contrast to better routes in traditional ants. Similar to traditional ants, the new breed of ants use pheromone subject to evaporation, and make routing decisions based on the pheromone concentration on the edges, although they make decisions based on the pheromone concentrations on the entire map and not just on the current node. In real life ants evaporation indicates routes becoming less appealing due to food quality depletion. In our case, evaporation is the mechanism that progressively increases the quality of routes as decreased pheromone concentration means less congestion. Using the terms ant and vehicles indistinctively, we now proceed to describe Road-ACO.

Algorithm variables

We now define the simulation variables which can be divided into global and local variables. The global variables are constant and have the same value for all vehicles. Local variables store data corresponding to the individual vehicles. We now list all the variables of interest.

Global variables

•Aggregation period (ap). Duration window which defines the time used by vehicles to determine travel conditions.

•Edge default travel time (edtt). The time it takes to travel that edge at the maximum allowed speed.

• ρ. Represents the pheromone evaporation. •Speed aggregation threshold (sat). Threshold used to trigger a vehicle to become a cluster head.

•Consensus threshold (ct). Threshold that triggers when a cluster head reports a traffic incident.

Local variables

Step counter. Used as a timer variable, to cycle through the Aggregation period.

• τ_ij.Represents the pheromone concentration or edge cost from node to node at node , as perceived by the individual vehicle.

• Δτ^k.Represents the pheromone intensity used by cluster head k to mark the edge it is currently in, in case of traffic incident.

•Speed moving average (sma). Stores the modified moving average of the vehicle speed.

•Aggregated average speed (aas). Used by cluster heads to aggregate the average speed of reporting vehicles.

•Aggregated travel time (att). Used by cluster heads to compute the pheromone intensity.

The algorithm

The algorithm can be subdivided into three sub algorithms, the speed aggregation, cluster, and the communication algorithms. The speed aggregation and the communication algorithms run concurrently at all times while the cluster algorithm is executed only when an abnormal traffic flow condition occurs. Each vehicle on the simulated road network independently executes these algorithms in a decentralized fashion.

The speed aggregation algorithm

Figure 2 illustrates the speed aggregation algorithm. When a vehicle enters into the simulated road network, the global variables are read, the step counter is set to 1, and the speed moving average is set to 0. At every time step thereafter the vehicle performs the following actions:

Figure 2: Speed aggregation algorithm.

•Applies evaporation to the perceived edge costs according to τ_ij=(1-ρ) τ_ij

•If, for a certain edge, the new τ_ij value is less than the edge default travel time, then τ_ij =default travel time is used.

•Acquires the current speed at which it is traveling and updates the speed moving average as:

sma(sma*(ap-1)+current speed)/ap.

•The step counter is incremented by 1.

•At the end of its aggregation period, the vehicle checks if the speed moving average falls under the speed aggregation threshold. If this is true the vehicle will execute the cluster algorithm.

The cluster algorithm

This algorithm is executed when the speed moving average falls under the speed aggregation threshold in the speed aggregation algorithm. Figure 3 illustrates this algorithm. The vehicle that satisfies the mentioned condition organizes a cluster on the edge it is currently in by broadcasting a request message and becoming the cluster head. Each cluster member will reply with a reply message containing the member's average speed. During an entire aggregation cycle the cluster head aggregates the received average speeds sent by the cluster members into aggregated average speed. At the end of this cycle, if the ratio of number of reply messages in consensus with the low speed condition (nrmc) to the total number of reply messages (TNRM) exceeds the consensus threshold, a pheromone drop is broadcasted in a traffic incident message and the cluster dissolves. The pheromone drop intensity is calculated according to:

Figure 3: Cluster Algorithm

Δτ^k← (edtt +att*(nrmc -1)/TNRM

The formula above produces pheromone drop intensity increasing with the number of reply messages in consensus. If the total number of reply messages is large but the number of reply messages in consensus is small, the drop has low intensity as one would expect and could be negligible. The cluster formation process is explained in the communication algorithm.

The communication algorithm

Figure 4 illustrates the communication algorithm. Vehicles on the simulated road network continuously monitor the communication channel waiting for two different kind of messages, request messages and traffic incident messages. Every vehicle on the same edge as the cluster head that receives the request message will send a reply message containing its average speed and resets its step counter to 1 to prevent broadcasting any new request message until the end of the new aggregation cycle. Every vehicle receiving the traffic incident message will update the edge cost according to and execute a shortest path algorithm using its internal map and the perceived costs in memory. The vehicle will reroute if a better route is found.

Figure 4: Communication Algorithm.

Adverse scenarios

There are two situations that may impair the operation of the algorithm:

•Road blockages. In the presence of a total road blockage the algorithm will not work. Given the way road networks are structured usually with multiple lanes and alternate roads, a total blockage is not likely to happen. As mentioned before, in Wardrop's UE users make routing decisions in an egoistic and rational way and all users have knowledge of the paths costs. Our algorithm uses egoistic routing with knowledge of the paths costs as in Wardrop's UE. In the case of a partial blockage, where vehicles can use alternate routing options, our algorithm will approach a new Wardrop's UE corresponding to the new network conditions.

Delayed information. The performance of the algorithm can be impaired if the paths costs information is not updated frequently. This may lead to oscillations as routing based on old information may send incoming vehicles to selected roads for long periods of time increasing congestion on those roads. When these new levels of congestion are reported it will favor alternate routes and repeat the process while the traffic on the previous roads subsides. To avoid this problem we chose a sufficiently small update period (5 seconds). As an example, at 70 MPH and a headway of 1 second, just 4 cars per lane will arrive at an intersection during a 5 second window. In the future we will investigate the impact of this parameter on the algorithm performance.

Next we proceed to explain our simulation details.

Setup

We evaluate the algorithm performance in a simulation environment composed of OMNET++ [51], SUMO [52], and Veins [53], similar to the environment described in [54]. The simulation is performed according to IEEE 1609.4 as implemented in Veins. In the next section, we describe the simulated environment, state the assumptions, and define the input and output parameters.

Simulated environment

Figure 5 and Table 2 show the simulated road network. As we explain bellow, some vehicles may need to reroute to improve their travel times. All roads have two lanes in each direction, a maximum speed of 40 MPH, and U turns are permitted. The horizontal edges are 495 ftlong, and all other edges are 720 ft long. The road network contains 5 nodes: -4, -6, -8, - 10, -12, -14, (-n denotes node n). Nodes -10, -14 are origins and node -4 is the only destination. From each origin node, -10, and -14, 1,000 vehicles depart to the common destination -4. When vehicles depart they have a planed route based on a shortest route algorithm (SR). Even though this road network is very symmetric and would suggest that all vehicles should use the shortest routes, differences in the traffic light signals and the allowed lane changes make the top route faster and vehicles may need to reroute to improve their travel times. The upper route is more favorable because: first, the traffic lights at nodes-8 and -6 both offer green light in sync to the incoming vehicles, while for the lower route when the traffic light at junction-12 is green, the traffic light at junction-6 has the red light on. Second, the intersection-6 favors the upper edge as the two lanes on it allow travel towards the destination while just one lane from the bottom route allows transit to the destination, since the other lane is forced to turn left. Figure 6 illustrates these lane details. All the traffic lights in the direction towards the destination have the following cycle: green, yellow, red, equal to 31, 6, and 49 seconds respectively. This was the default cycle assigned by SUMO.

Figure 5: Road Network Description.

Table 2: Road Network Description.

Figure 6: Lane Connection Detail, intersection-6.

Simulation assumptions

It is assumed that the algorithm messages would be broadcasted using regular IEEE1609 standard beacons. All vehicles are 16.4 ft long and acceleration and deceleration are 8.53 and 14.76 ft/s² respectively.

Input parameters

The number of vehicles entering the simulated road network from each origin. Vehicles enter the network as fast as the congestion of the roads allows. For our simulation we used 1,000 vehicles per origin. This number was selected based on reasonable simulation time and because it produces significant traffic congestion when routing by SR.

The evaporation. Several values of this parameter are tested to assess the impact on the solution of the speed at which pheromone vanishes when recovering from wrong decisions and congestion. The value of this variable was systematically changed to obtain the greatest traffic flow improvement.

The speed aggregation threshold. This parameter is varied to assess the impact of ignoring certain values of congestion level over the solution. The value of this variable was systematically changed to determine how much of congestion can be ignored and still obtain significant traffic flow improvements.

Output parameters

The outputs of the simulation are the vehicle’s average traveling time, and the total time, measured from the start of the simulation to the moment that the last vehicle reaches its destination. The values of these two parameters are obtained for the cases of route selected by SR, UE as calculated by traffic simulator SUMO (SUMO-DTA), and with the proposed algorithm for several different input parameters. The Veins framework which controls the simulation keeps record of many and diverse simulation results, from there we were able to obtain our parameters of interest, average traveling time and the total time. In the next section the simulation results are analyzed.

Evaluating the performance of a DTA algorithm under UE, by using the definition of UE, is a difficult task as this equilibrium implies that no vehicle can improve its travel time by changing routes and that is hard to assess. We base our evaluation on average trip times. A solution that seeks UE should have average trip times close to that of the optimal UE. Otherwise some vehicles could be able to reduced their individual travel times, contradicting the definition of UE. Our algorithm does not minimize average trip times as that would produce SO and not UE, however it is known that UE, even though less efficient, is practical to achieve and not so far from SO [15]. Table 3 contains the 24 simulation results. Row 1 contains the data for the case when shortest route algorithm is used; it is the worst case as it shows the largest simulation and average trip times. On the other hand, row 2 shows the data for the case of SUMO-DTA. This solution presents the best simulation and average trip times with an improvement of 34.97% in average trip times. The rest of the rows show the data for the proposed algorithm for different input parameters. All of the proposed algorithm trials show improvement over the average trip times of the SR. If any two solutions present similar average trip time, we prefer the one with the lowest simulation time. The best outcome is 29.17% for an evaporation of 25% and speed aggregation threshold of 50%. Evaporation of 25% appears to be a good choice in this scenario as the three best outcomes include this value. The best solution has a speed aggregation threshold value of 50%, this implies less use of the communication channel and prevents unnecessary rerouting.

Table 3: Simulation Results. ct=25%, ap=5.

We introduce and evaluate Road-ACO, a novel decentralized algorithm to alleviate traffic congestions on road networks and to fill the void left by current algorithms which are either static, centralized, or require infrastructure. Road-ACO is an algorithm inspired by Ant Colony Optimization for the Dynamic Traffic Assignment in VANETS. Initial results indicate a promising future for approaches based on this algorithm. Simulation results for the algorithm show an improvement on travel time of 29.17%, over the SR case, which is fairly close to the improvement introduced by SUMO-DTA (34.97%). It is important to indicate that Road-ACO is a realistic approach as it improves traffic as it evolves, in real time, without prior knowledge of the traffic demand or the schedule of the cars that will enter the road network in the future. Also Road-ACO enjoys the benefits of being decentralized and infrastructure-less. We expect the algorithm to perform well if we increase the road network complexity and the number of vehicles. However, in this case the algorithm needs to be modified to include multi-hops and Time To Live (TTL). Our main concern is the simulation time as the interactions between simulators SUMO and OMNET++ are time consuming. We plan to address this problem by reducing the number of interactions by including in OMNET++ some of the functions that are currently executed by SUMO like the case of changing the oute to the one with the lowest cost. In the near future we will continue to investigate the performance Road-ACO in larger and more complex road networks.