Advanced Leader Election for Virtual Traffic Lights

(Institute of Computer Science，University of Innsbruck，Technikerstr.21a，6020 Innsbruck，Austria)

Advanced Leader Election for Virtual Traffic Lights

Florian Hagenauer,Patrick Baldemaier,Falko Dressler,and Christoph Sommer

(Institute of Computer Science，University of Innsbruck，Technikerstr.21a，6020 Innsbruck，Austria)

We examine the network performance of algorithms for self?organized traffic management.In particular，we focus on wireless net?working between cars.One of many technologies that make road traffic safer and more efficient is the Virtual Traffic Light(VTL) system，which is able to coordinate the traffic flow at intersections without the need for physical lights.VTL takes a leading vehi?cle at an intersection and uses it to control the traffic lights.We developed algorithms for leader election and traffic light computa?tion in realistic vehicular networking scenarios.Our key contribution is the extension of this algorithm to support arbitrary inter?section layouts.We investigated the proposal in synthetic and realistic scenarios.The results show that，overall，VTLs use network resources efficiently and positively influences driving experience.It performs better than stationary traffic lights for a low to medi?um network load.We also identify potential optimizations to deal with high network load and to improve fairness.

virtual traffic lights;self?organization;vehicular networks

1 Introduction

Away to safer，more efficient traffic is hinted at in the 2010 reportTowards a computational transpor?tation science[1].This report introduces a new sci?entific discipline in which the work of computer sci?entists and transportation experts is combined to produce more useful models and technologies for future transportation.

Safety at intersections has become a key research challenge within the inter?vehicle communication(IVC)community.Solu?tions range from intersection warnings to more intelligent assis?tant systems[2]-[5].

In the U.S.，more than 240，000 traffic lights regulate inter?sections[6].Of these，more than 50%are in need of repair[7]. Others are running at suboptimal levels，leading to raffic de?lays of up to 40%in excess of what they would normally be if the lights were optimally configured[6].Repairing and/or re?configuring these traffic lights is costly，and many intersections (up to 99.5%in the U.S.[8])are simply left without traffic lights.

A completely new approach to complementing(or even re?placing)physical traffic lights is the Virtual Traffic Light (VTL)system[8]-[10].Vehicles approaching an intersection exchange messages wirelessly and cooperate to create a dynam?ic traffic light program for the junction.This information is then presented to the driver on an in?vehicle display;thus，physical traffic lights are replaced.

The VTL approach offers numerous benefits，including elim? inating the cost of deploying traffic light infrastructure on ev?ery street.VTLs can also react quicker than normal traffic lights to microscopic traffic conditions.

One of many different wireless technologies that VTL can be built on is the IEEE 802.11p standard[11].Based on this，IEEE DSRC/WAVE and ETSI ITS G5 are being standardized for vehicular networking.We are now in an era of radical change in terms of car manufacturing and road traffic manage?ment.Such changes are supported by the U.S.federal govern?ment’s National Highway Traffic Safety Administration(NHT?SA)，which announced in February 2014 that it plans to re?quire all new cars to have wireless technology that broadcasts the car’s location，speed，direction，and other data so that driv?ers can be warned of an impending collision[12].This an?nouncement coincides with the final standardization of higher?layer networking protocols in Europe by the European Tele?communications Standards Institute(ETSI).

In this paper，we extend the model we developed in[13]. This allows us to investigate the feasibility of using current ve?hicular?networking proposals to realize VTL on a larger scale. In particular，we focus on the networking aspect and investi?gate the feasibility of establishing both the VTL and car clus?ters in a reliable way.Our new leader?election and traffic?light?computation algorithm now supports arbitrary intersection lay?outs.We investigated this extended algorithm in a realistic sce?nario.We found that VTL uses network resources efficiently and positively impacts the driving experience.VTL performs better than stationary traffic lights for a low to medium network

load.We also identified optimization potential to deal with high network load and improve fairness.

2 Related Work

VTLs have been repeatedly worked towards in the literature. One of the first examples is by Dresner et al.[10]，which de?scribes a system that allows vehicles to wirelessly coordinate when they pass at intersections.This eliminates the need for physical traffic lights.Using a custom?built road traffic simula?tor，the authors show a large increase in efficiency.

Gradinescu et al.[9]describe adaptive traffic lights that gather data from approaching cars and adapt green time.How?ever，this research is primarily concerned with physical traffic lights.Using a custom built discrete?event simulation tool，they show that the average delay of vehicles decreases signifi?cantly if traffic lights can make use of wirelessly exchanged in?formation.

Avin et al.[14]introduce a scheme to place another traffic light in front of intersections.These traffic lights should be dy?namically placed and synchronized to allow a vehicle to pass through an intersection much quicker.To ease repositioning traffic lights virtual counterparts are introduced.From micro?scopic road traffic simulation using SUMO，Avin et al.show that this scheme reduces the number of delayed vehicles by up to 20%.

The most complete proposal for VTLs to date，and the one that we build on，is that of Ferreira et al.[8].By running simu?lations，they show that VTLs have the potential to reduce CO2emissions by up to 18%[15].Simulations were run using DI?VERT in conjunction with NS?3.The impact of different human?machine interfaces for VTLs was investigated by Olaverri?Monreal et al.[16].The authors showed that brake activity when VTLs are used is similar to brake activity when physical traffic lights are used.Viriyasitavat and Tonguz[17]ran simu?lations on SUMO to show that emergency vehicles can reach their destination minutes earlier when VTLs are used.

We complement these studies by using a state?of?the?art combined network and traffic?simulation environment.The Veins framework connects the well?established network simula?tor OMNeT++with the detailed vehicular simulation SUMO [18].In our earlier work，we already developed algorithms for leader election and traffic light computation in realistic vehicu?lar networking scenarios[13].Our main contribution in this pa?per is the extension of this algorithm to support arbitrary inter?section layouts and to investigate its performance in more real?istic simulations.

3 Architecture

3.1 General Architecture

The basic idea for the VTL algorithm is proposed by Fer? reira et al.[8].To support a system using the algorithms，vehi?cles have to have a wireless networking device and the means of determining their current position.IEEE 802.11p and GPS support these needs and can be used to make VTL work.GPS is already used in many vehicles nowadays，and it can be safe?ly assumed that cars are equipped with it.Dedicated short?range communications(DSRC)technologies are not widely de?ployed yet，but the recent NHSTA announcment paves the way for mandating this technology in the U.S.[12].

The following occurs when VTL is active at an intersection:

1)Vehicles broadcast data about their current position to other cars in close proximity.In the future，other information，such as speed and acceleration，may be broadcast.The data is stored in a neighbor table and is updated if newer informa?tion is received.It is envisioned that such information will be automatically provided by basic services of vehicular net?works，e.g.，local dynamic maps(LDMs)maintained by coop?erative awareness messages(CAMs)in ETSI ITS G5.

2)If a crossing conflict is detected at an intersection，a virtual traffic light has to be calculated.Such a conflict occurs when two vehicles approach an intersection and a collision is imminent.In this case，a leader needs to be selected to de?termine the traffic light program.

3)The vehicles select a single car to be the leader at the inter?section.This vehicle generates a traffic light program and sends the information to the other vehicles.

4)Vehicles receive traffic light data that is displayed inside the vehicle to the driver.

5)If the traffic light program changes，the leader sends an up?date.

6)When the leader crosses the intersection，a new leader has to be selected.This can be done by the old leader automati?cally selecting a leader or by initiating a new election.In this case，the algorithm continues at step 3.

An early work describing VTL approaches[8]provides a very good introduction to the general VTL concept，but de?tailed explanation about leader election is lacking.In[8]，a simple table?based scheme is used for traffic?light program cal?culation.In[13]we addressed these issues and proposed a de?tailed leader?election scheme and a more dynamic traffic light program in which a single vehicle announces an election and others reply with their distance to the intersection.After a time?out，the vehicle closest to the intersection is selected as the new leader and determines the new traffic light program.If multiple elections are initiated by different vehicles，every ve?hicle has a single，comparable ID to break ties.This may be，for example，the network address.For a more detailed descrip?tion of the algorithm，we refer to[13].The used model had two deficiencies，which we address in this paper:

1)A simulated physical traffic light was used by the road traf?fic simulation and was controlled by the VTL leader.This meant that the traffic light program was directly obeyed in the road traffic simulation without the need to send it to

each vehicle approaching the intersection.Therefore，it was not possible to simulate effects introduced by multiple lead?ers.

2)The algorithm was not aware of non?conflicting lanes.Such lanes can be given a green light without the possibility of any crashes.With our first model，only a single lane was giv?en a green light while others had to wait.Such a scenario produces unnecessary delay for the drivers.

3.2 Improved Features

After analyzing the problems with our first proposal，we start?ed to develop an updated version that solves these problems. The first thing we did was to remove the dependency from SU?MO traffic lights.We configured SUMO so that it always keeps all traffic lights red and forces vehicles to stop.We selectively allowed any vehicles with a VTL state of green to ignore the traffic light.With this in place，cars only followed a local traf?fic light state table that stores information about the next inter?section.Until a traffic light broadcast is received，a vehicle as?sumes the state unknown for a VTL.If this happens，the vehi?cles stop at the intersection.In this case，a timeout is initiated，and afterwards，the current state is requested by the intersec?tion’s leader.This is done to prevent vehicles waiting unneces?sarily at the intersection.

Second，it is now possible to give a green light to multiple non?conflicting lanes.Our proposed protocol for VTL can de?tect such lanes and give a green light to multiple lanes at the same time.This is done by selecting one lane as before and it?erating over all other lanes，adding them to the set of lanes to be given a green to if there is no conflict.

Third，an update enables vehicles to store a simplified topol?ogy of the road network.In this view on the street network，lanes(which share the same endpoint and do not branch)are grouped together.This additional topology helps them quickly identify which(if any)is the next traffic light that VTL needs to be performed for.

Finally，we further improved the election algorithm present?ed in[13]，by adding fast leader hand?off:when a VTL leader crosses an intersection，it preferably hands?off the task of lead?er to a vehicle that is stopped in order to reduce rapid leader switching.

4 Evaluation

We evaluated the performance of our proposed VTL protocol in a synthetic scenario and a realistic scenario.

Our synthetic scenario involved a simple four?way intersec?tion in which each road was 400 m long.To force the intersec?tion to have a very high load without substantially hindering traffic flow，we made each road twelve lanes wide(six lanes each direction)(Fig.1)and forced vehicles to only go straight through the intersection at a speed limit of 50 km/h.For the same reason，we did not include buildings，which would ob? struct communication between vehicles.This scenario enabled us to study VTL with arbitrary，uniform traffic flows.We picked a range of 225 to 2700 vehicles per hour passing through the intersection and investigated the impact of network load on VTL performance.

The first metric we used in this investigation was mean total travel time，that is，how long a vehicle took on average to pass through the intersection.This metric included the time it took for a vehicle to travel the 400 m to the intersection and the time it took to travel the 400 m after it.We compared travel times for an intersection managed by conventional traffic lights and for the same intersection managed by our proposed proto?col extending VTL.With the conventional traffic lights，we con?figured standard fixed durations of 31 s green，6 s yellow，and 37 s red.

Fig.2shows the results for seven different traffic densities. It shows the mean value across all repetitions and the 95%con?fidence interval of the mean.When traffic density is low，aver?age travel time is improved if the intersection is managed with VTL.When conventional traffic lights are used to regulate traf?fic，cars take up to 20%longer to reach their destination.How?ever，when traffic density is higher，this benefit becomes less pronounced.In fact，VTL and conventional traffic lights per?form at about the same level when 1800 vehicles per hour pass through the intersection.VTL performs slightly worse than con?ventional traffic lights for higher?density traffic.This is not be?cause the intersection cannot handle this amount of traffic.For the simulated densities，the mean travel time does not vary with respect to traffic density if the intersection is managed by conventional traffic lights.Therefore，the reduced effectiveness

of VTL must be due to some other effect.

▲Figure 1.Synthetic simulation scenario:multi?lane four?way intersection.

We therefore investigate a second metric which is indicative of the system network performance:the channel access success ratio.This metric shows how often the channel is found to be idle when trying to send a packet(as opposed to finding the channel busy and triggering a back?off).

Fig.3shows the mean value of this metric as traffic density increases.The probability of finding the channel empty de?creases linearly as traffic density increases.This probability decreases from almost 100%for 225 vehicles per hour to just above 90%for 1800 vehicles per hour and approximately 85% for 2700 vehicles per hour.Taken together with previous re?sults，this means that leader election and traffic?light?program dissemination are very efficient(after all，the decrease is only linear).Still，even with as few as 10%failed channel access at?tempts，the proposed protocol is already no more efficient than conventional traffic lights.

This points to various avenues for future work.While it can be argued that VTLs are unlikely to be needed in regions with high traffic densities，the results point to a strong relationship between available network capacity and VTL performance.

For now，we restrict our analysis to favorable network condi?tions;that is，low traffic density where the full network capaci?ty is available to the VTL system.We turn to the potential im?pact of VTL on traffic within a city.Rather than considering a scenario with one simple intersection，we now simulate VTL in a more realistic traffic scenario.

The realistic scenario is based on real geodata from Open?StreetMap of Ingolstadt，Germany.The data accurately reflects road and building topology and geometry，speed limits，right of way，and one?way streets.We took great care to accurately model intersection topologies;that is，we added correct turning lanes，configured traffic signal timing，and added buildings that attenuate radio propagation.As in earlier work[19]，we simulated traffic throughout the whole of Ingolstadt，but only investigated nodes driving within a 1.5 km2Region of Interest(ROI)(Fig.4).This ROI contains a typical mix of high?ca?pacity and low?capacity roads，traffic lights，and un?regulated intersections as well as high and low node density areas.We generated traffic flows according to low demand，an average of 25 vehicles per square kilometer.This realistic scenario enabled us to get an idea of the impact of the designed VTL system on urban traffic flow.We compared a city managed by conventional traffic lights to the same city man?aged entirely with VTLs.In the interest of fairness，we only used VTLs on those seven intersections that used to have conventional traffic lights.All other in?tersections remained unmanaged with vehicles fol?lowing the city’s right of way rules(yield to priority road or yield to right).

▲Figure 2.Synthetic scenario:traffic density vs.travel time.

▲Figure 3.Synthetic scenario:traffic density vs.ratio of successfulchannel accesses(out of all packets sent).

▲Figure 4.Realistic simulation scenario:1.5 km2Region of Interest(ROI)in the city of Ingolstadt.

▲Figure 5.Ingolstadt:travel time.

Fig.5shows the results for the first metric we in? vestigated;that is，the total time vehicles took to reach their destination(or to leave the ROI).The results are plotted as an empirical cumulative density function(eCDF)over all simula?tion runs to show the actual distribution.Both distributions have the same features:travel times are either extremely short (resembling vehicles that only briefly passed through a small part of the ROI)or are approximately normal，distributed around approximately 110 s and 130 s(mirroring the 20%dif?ference observed in our simulations of a single intersection). There is also a pronounced right tail;that is，some vehicles are substantially slower，particularly in the scenario where vehi?cles relied on VTL to coordinate crossing.

▲Figure 6.Ingolstadt:waiting time.

To determine the reason for this，we investigate a new met?ric:the cumulative time that each vehicle spent waiting，that is，moving less than 0.1 m/s(0.36 km/h)(Fig.6).The propor?tion of vehicles that did not have to wait at all increased from 36%to 74%when some intersections were managed with VTLs，and overall waiting times decreased substantially.Yet this metric also explains the reason for the pronounced right tail in the distribution of travel times.A very small number (0.7%)of vehicles had to wait twice as long as even the longest waiting time incurred when conventional traffic lights were used.Closer investigation reveals that these vehicles are(un?fortunately)VTL leaders on unfrequented streets.It took a long time for enough vehicles to queue behind the leader on the un?frequented street to outweigh the amount of traffic on the major road.Therefore，our na?ve VTL traffic light program caused ma?jor delays for these vehicles.Although traffic flow was substan?tially smoother overall，this 0.7%of drivers might feel unfairly treated by VTL.

5 Conclusion

In this paper，we evaluated an improved VTL system that can manage arbitrary intersection geometries.Using two sce?narios—a realistic urban road network and a synthetic single intersection—we investigated the impact of VTLs on traffic flow within a city as well as the overall network performance of VTLs.

We showed that，overall，VTLs positively affected the driv?ing experience of our simulated vehicles，cutting total travel time(by approximately 20%)and wait times(74%of vehicles did not have to wait at all).However，we also identified optimi?zation potential:a few vehicles had significantly longer wait times.This points to a lack of consideration of fairness in the proposed algorithm.We further showed that our proposed pro?tocol for VTL uses network resources efficiently:channel load scales linearly with traffic density.Still，a deterioration of its performance in scenarios with than 10%of channel load points to optimization potential in this area as well.

Future work might also include improved optimizations of which lanes to give green to，exploiting the full potential of combining multiple non?conflicting lanes into one green phase.

[1]S.Winter，M.Sester，O.Wolfson，and G.Geers，"Towards a computational trans?portation science，"Journal of Spatial Information Science，vol.2，no.1，pp.119-126，2011.doi:10.1145/1942776.1942785.

[2]S.?H.Chang，C.?Y.Lin，C.?C.Hsu，C.?P.Fung，and J.?R.Hwang，"The effect of a collision warning system on the driving performance of young drivers at intersec?tions，"Transportation Research Part F:Traffic Psychology and Behaviour，vol. 12，no.5，pp.371-380，2009.doi:10.1016/j.trf.2009.05.001.

[3]H.Berndt，S.Wender，and K.Dietmayer，"Driver Braking Behavior during Inter?section Approaches and Implications for Warning Strategies for Driver Assistant Systems，"inIEEE Intelligent Vehicles Symposium(IV’07)，Istanbul，Turkey: IEEE，Jun.2007，pp.245-251.doi:10.1109/IVS.2007.4290122.

[4]S.Joerer，M.Segata，B.Bloessl，R.Lo Cigno，C.Sommer，and F.Dressler，"To crash or not to crash:estimating its likelihood and potentials of beacon?based IVC systems，"in4th IEEE Vehicular Networking Conference(VNC 2012). Seoul，Korea:IEEE，Nov.2012，pp.25-32.doi:10.1109/VNC.2012.6407441.

[5]S.Joerer，M.Segata，B.Bloessl，R.Lo Cigno，C.Sommer，and F.Dressler，"A ve?

hicular networking perspective on estimating vehicle collision probability at In?tersections，"IEEE Transactions on Vehicular Technology，2014，to appear.

[6]"National traffic signal report card，"National Transportation Operations Coali?tion(NTOC)，Report 2012，2012.

[7]P.Koonce，W.Kittelson，L.Rodegerdts，K.Lee，C.Swartz，J.Bonneson，P.Tar?noff，B.DeRoche，D.Bullock，and W.Tighe，"Traffic signal timing manual，"U. S.Department of Transportation，Publication FHWA?HOP?08?024，Jun.2008.

[8]M.Ferreira，R.Fernandes，H.Concei??o，W.Viriyasitavat，and O.K.Tonguz，"Self?organized traffic control，"in7th ACM International Workshop on Vehicu?lar Internetworking(VANET 2010)，Chicago，IL:ACM，Sep.2010，pp.85-90. doi:10.1145/1860058.1860077.

[9]V.Gradinescu，C.Gorgorin，R.Diaconescu，V.Cristea，and L.Iftode，"Adaptive traffic lights using car?to?car communication，"in65th IEEE Vehicular Technolo?gy Conference(VTC2007?Spring)，Dublin，Ireland:IEEE，Apr.2007，pp.21-25. doi:10.1109/VETECS.2007.17.

[10]K.Dresner and P.Stone，"Multiagent traffic management:a reservation?based intersection control mechanism，"in3rd International Joint Conference on Au?tonomous Agents and Multiagent Systems(AAMAS 2004).New York，NY: IEEE，Jul.2004，pp.530-537.doi:10.1109/AAMAS.2004.190

[11]Wireless Access for Vehicular Environments，IEEE Draft Standard P802.11p/ D4.0，Mar.2008.

[12]M.L.Wald，"U.S.plans car?to?car warning system，"The New York Times，p. B3，Feb.4 2014.

[13]C.Sommer，F.Hagenauer，and F.Dressler，"A networking perspective on self?organizing intersection management，"inIEEE World Forum on Internet of Things(WF?IoT 2014).Seoul:IEEE，Mar.2014.

[14]C.Avin，M.Borokhovich，Y.Haddad，and Z.Lotker，"Optimal virtual traffic light placement，"in8th International Workshop on Foundations of Mobile Computing(FOMC 2012).Madeira，Portugal:ACM，Jul.2012.doi:10.1145/ 2335470.2335476.

[15]M.Ferreira and P.d’Orey，"On the impact of virtual traffic lights on carbon emissions mitigation，"IEEE Transactions on Intelligent Transportation Sys?tems，vol.99，no.10，pp.1-12，Oct.2011.doi:10.1109/TITS.2011.2169791.

[16]C.Olaverri?Monreal，P.Gomes，M.Silveria，and M.Ferreira，"In?vehicle virtual traffic lights:a graphical user interface，"in7th Iberian Conference on Informa?tion Systems and Technologies(CISTI 2012).Madrid，Spain:IEEE，Jun.2012，pp.471-476.

[17]W.Viriyasitavat and O.Tonguz，"Priority management of emergency vehicles at intersections using self?organized traffic control，"inVehicular Technology Conference(VTC2012?Fall)，Quebec City，Canada:IEEE，Sep.2012，pp.1-4. doi:10.1109/VTCFall.2012.6399201.

[18]C.Sommer，R.German，and F.Dressler，"Bidirectionally coupled network and road traffic simulation for improved IVC analysis，"IEEE Transactions on Mo?bile Computing，vol.10，no.1，pp.3-15，Jan.2011.doi:10.1109/ TMC.2010.133.

[19]C.Sommer，D.Eckhoff，and F.Dressler，"IVC in cities:signal attenuation by buildings and how parked cars can improve the situation，"IEEE Transactions on Mobile Computing，2014，to appear.

Manuscript received:February 17，2014

Biograpphhiieess

Florian Hagenauer(hagenauer@ccs?labs.org)received his BSc and MSc degrees in computer science from the University of Innsbruck，Austria，in 2011 and 2013，re?spectively.In October 2013，he joined the Computer and Communication Systems Group to work on problems in Car?to?X communication.

Patrick Baldemaier(patrick.baldemaier@ccs?labs.org)received his BSc in comput?er science from the University of Innsbruck，Austria，in 2012.Since October 2013，he has been working on his master thesis"Simulation of Self?Organizing Intersec?tion Management"at the Computer and Communication Systems Group.

Falko Dressler(dressler@ccs?labs.org)is a full professor of computer science and head of the Computer and Communication Systems Group at the Institute of Comput?er Science，University of Innsbruck.Dr.Dressler received his MSc and PhD degrees in computer science from the Department of Computer Science，University of Erlan?gen，in 1998 and 2003.He is an editor for IEEE Trans.on Mobile Computing，Else?vier Ad Hoc Networks，ACM/Springer Wireless Networks(WINET)，and Elsevier Na?no Communication Networks.He regularly serves in the TPC of networking confer?ences such as IEEE INFOCOM，IEEE ICC，IEEE GLOBECOM，and IEEE WCNC. Dr.Dressler has written textbooks，including"Self?Organization in Sensor and Actor Networks，"which was published by Wiley in 2007.Dr.Dressler is an IEEE Distin?guished Lecturer in the fields of inter?vehicular communication，self?organization，and bio?inspired and nano?networking.Dr.Dressler is a Senior Member of the IEEE (COMSOC，CS，VTS)as well as a senior member of ACM(SIGMOBILE)，and mem?ber of GI(KuVS).His research activities are focused on adaptive wireless network?ing and self?organization methods with applications in wireless ad hoc and sensor networks，inter?vehicular communication，bio?inspired and nano?networking，and network security.

Christoph Sommer(sommer@ccs?labs.org)received his PhD degree in engineering (Dr.?Ing.，with distinction)and his MSc degree in computer science(Dipl.?Inf. Univ.)from the University of Erlangen in 2011 and 2006，respectively.In 2010，he was a visiting scholar with the research group of Ozan K.Tonguz at the Electrical and Computer Engineering Department of Carnegie Mellon University(CMU).In 2012，he was a visiting scholar with the research group of Mario Gerla at the Com?puter Science Department of the University of California，Los Angeles(UCLA).He is currently a postdoctoral researcher with the Computer and Communication Sys?tems group at the University of Innsbruck.Since 2011，he has been a member of the ACM/Springer Wireless Networks(WINET)editorial board.His research is focused on questions regarding traffic efficiency and safety，as well as on security aspects of Car?to?X communication in heterogeneous environments.