高巍巍

(黑龙江外国语学院 信息科学系, 哈尔滨 150025)

智能交通灯的调度算法研究

高巍巍

(黑龙江外国语学院 信息科学系, 哈尔滨 150025)

由于交通信号是保证道路十字路口安全驾驶的重要交通工具。各个交通流存在队列延迟破坏并降低了交通顺畅性，提出了一种智能的交通灯调度算法。该算法分析通行十字路口的各交通流的实时交通特征，同时又对各个交通灯的时相进行调度。通过减少信号十字路口的通行车辆的等待时间改善了交通顺畅，并且提升每秒穿过十字路口的车辆数。该算法的性能并与其它算法进行不同模拟场景的对比实验。实验表明，该算法可缩短队列延时，明显提高了交通灯信号调度方案的交通流畅性，而且提高了每个信号十字路口的通行量。

交通灯； 调度算法； 城市交通仿真平台； 车载自组网

0 引言

自80年代交通灯使用到现在，它一直负责调度、控制各个配置有信号灯周期调度系统的十字路口的交通流[1-3]。它们提供便于所有交通流共享道路十字路口的安全调度[4-7]。各十字路口的队列延迟使交通流顺畅性下降，降低了所有道路网络范围内的交通效率[8]。为能够改善交通效率，已有多名学者提出能对交通灯进行时间设定的调度智能算法[9-10]。每个交通灯的最佳调度使得信号十字路口的通行车辆的延迟达到最小。

众多学者已经对独立的交通灯路口进行过研究，他们对交通灯时相的设定都是根据周边车流的实时交通来进行[11]。各个交通灯的交通控制为不定序列时相周期，这个周期代表了将要穿过某个道路十字路口的各个交通流时间调度情况。对各个十字路口的序列时相周期进行调度时需要利用到这几个参数如：车辆数、交通速度以及各交通流的交通量[12]。各十字路口的平均延迟越短通过量就越大，算法的调度效率就越高。

智能交通信号灯考虑了周边的交通流量和道路十字路口的交通特性[13]，利用车辆的 Ad hoc 网络技术开发智能化的交通信号灯控制算法有几种，在过去的几年里，提出的自适应的智能交通灯的机制一直采用车载自组织网络(VANET)。krajzewicz等[14]基于车-车通讯开发了自适应交通信号控制系统。提出嵌入SUMO[15]仿真器中交通信号灯控制算法。该算法的目的是利用在交通灯前的堵塞长度作为输入，并且在每个交叉路口减少排队延迟。每个交通灯的尝试采用调度算法解决检测堵塞。此外，韦伯斯特[16]提出的一个交通信号灯实时控制算法。它利用网络收集和汇总的车辆实时位置和速度信息，并且在每个交叉路口优化交通灯控制。

自适应交通信号控制算法(OAF)通过对每个交通灯调度不同的时相最优序列，以最大限度地降低交叉路口的延迟。在每个交通流中调度采用先来先服务的原则，数学分析和仿真实现已经证明算法的正确性。本文把交通信号作为一个作业调度问题，其中每个任务对应一个车辆。本文提出智能的交通灯调度。该算法的目的在于通过缩短在各个十字路口的等待延迟时间而扩大通过量。首先对交通密度最大的交通流进行调度，不得超过该路口时相允许的最大绿灯时间。然后将车流准备通行的那个信号十字路口区域定义为“等候区”。这个概念的提出是为了确保在不超出最大允许的绿灯时间范围内平等共用十字路口。从实验结果可知，本文算法与其它的调度算法相比缩短了每个交通灯位置的队列延迟。而且，采用该算法后，每秒穿过信号十字路口的车流更多，通行量也更大。

1 交通灯路口

在分析本文算法及研究成果之前，首先说明独立交通灯的定义及特征。独立交通灯各自控制着各个路口的交通，不需要兼顾附近信号路口的情况。例如图1，是一个典型的十字路口，它由八个交通流共享，每两个交通流同时进行。十字路口的交通灯对不同时相序列进行控制和调度，同时显示不同交通流之间的冲突情况。每个交通灯的时间变量如周期长度、时相、间隔分割和补偿参数的设置都根据实时交通流特征来设定。表1提供了各信号十字路口的时间变量定义。

对不定顺序时相或跳跃时相可适用的十字路口时相进行设置的所有选择，如图1所示。

图1 十字路口相态的选择

在一个典型的控制机制里，安装工作一旦结束，就需要对每个交通灯的周期长度、时相长度以及时相的个数和顺序长期进行设置。工程人员利用交通特征的所有相关统计数据来设置这些参数。

另一方面，引进交通感应控制系统来根据当前交通特征对各个时相的定时值进行控制。需要配置实时探测器对每个独立的交通灯针对性开发出半感应以及全感应控制系统。一般情况下，应根据数学模型来对绿灯及同行间隔设定时间。这些操作要考虑的因素有交通速度、十字路口的容纳能力和有序的交通流动情况，如表1所示。

表1 交通信号灯时间变量定义

车辆自组织技术能对各个信号十字路口的各种交通流的交通特征进行评估和报道,它是一种实时探测器。许多自适应智能交通调度算法被用来提升十字路口的通行量以及所有相关交通的顺畅性。

2 智能交通灯调度算法

本节说明一种交通灯智能调度算法。此算法分析各信号十字路口周边各段道路的实时交通特征。本文以一个典型的十字路口进行距离分析，如图1所示。在本文算法中，十字路口被看作是一个由8个交通流共享的一个处理器。车辆在不同预测时间抵达十字路口，所以每个交通流就是一组连续的进程。每个进程包含绿灯时相范围内穿过十字路口的一台或多台车辆。根据数据采集阶段等候区车辆的数量(即各个交通流的交通密度)来确定各个进程的大小。

等候区是针对各个十字路口而设定的一个虚拟区域，如图2所示。

图2 交通灯等候区

各等候区的界限根据允许的最长绿灯时间来设定。等候区保证了相互竞争的交通流能平等共用十字路口。目的是将连续的进程分散到各个交通流。每台通行的车辆和每个位置的交通灯均配备一台无线收发器和GPS装置。各独立十字路口的智能交通灯定期发布等候区的界限数据。于是，通行的车辆就会注意到自己是否已进入等候区，而且根据当前位置判断出自己处在哪个交通流。等候区界限内的通行车辆需将各交通流的实时交通特征传达给对应位置的智能交通灯。

每个车辆在道路行驶周期性地广播的基本数据(如位置、速度、方向、目的地等)。车辆会接收到来自周边车辆的交通数据。根据每台发送车辆的位置，接收车辆会做出判断它们是否同时处在同一个交通流(同一个进程)。等候区内各交通流的交通密度di、交通速度si以及预计通行时间ti,可根据[17]求得。对于每个交通流，靠近交通灯最近的车辆负责将对应交通流的交通特征传达给智能交通灯。任何进程里所有车辆通过交通灯所需要的时间(T)由公式1计算，得到式(1)。

(1)

其中，α是一个常数，指一个进程里聚集的各组车辆里速度第一的车辆的启动延时；它的最佳值根据实际经验来设定；Fd是进程离十字路口交通灯最远的车辆与该交通灯之间的距离；位于交通灯与等候区(Lra)界限之间的这个距离要根据各交通流(Stf)的交通速度来设定。时间T的值应不超出允许的最长绿灯时间。数据采集过程中所有聚集在等候区的车辆应在绿灯切换之前能够通行完毕。

对于含八个交通流的十字路口，对各个时相的定时周期都采取八种双线程执行的做法是不可取的。这些时相包括：P15(1+5),P25(2+5),P16(1+6),P26(2+6),P37(3+7),P47(4+7),P38(3+8)和P48(4+8)，如图1所示。

本文提出算法中，所有交通流的调度都是从最大密度(Max(di))开始的。根据十字路口与各个进程中距离最远车辆之间的距离设定各时相时间。算法1统计出调度算法的所有序列时相。一个交通流经过十字路口，将交通密度及其对应的预计通行时间均设为0。智能交通灯从最大的密度开始循环对竞争的交通流进行调度直至所有交通流密度为0。然后，交通灯再对等候区所有交通的最新交通特征执行算法操作。

算法1：智能交通灯的调度算法(TLSA)

输入：交通灯(TL), 等候区(RA),RA交通流i的交通密度(di)，RA所有车辆所需时间(ti)

输出：计算RA中所有交通流di和ti

1 While TL中任意交通流di>0do

2 设j为交通流，最大交通密度dj

3 设i1和i2为模拟穿过交通十字路口的交流流量

4 Ifdi1>di2then

Pji1=schedule (j,i1);dj=0.0;di1=0.0;tj=0.0;ti1=0.0;

5 Else

Pji2=schedule (j,i2);dj=0.0;di2=0.0;tj=0.0;ti2=0.0;

6 IF结束

7 调整等候区内所有其它交通流tk；

8 While结束

在每个交通灯周期，从八个候选时相中选出四个来对所有交通流进行处理。TLSA提升了十字路口的通行量并缩短通行车辆的队列延时。主要是第一个时相期间在各个交通流等候的车辆数减少的缘故。而且，每个绿灯时相过去后要对各个交通流的调度时间及时进行调整，从而后续时相通行车辆所等候的时间就会更少。根据各交通流距离最远车辆的当前预计位置设置调整时间。该车辆的当前位置根据最近传送数据以及交通流的交通速度进行估算。但是，如果该车辆的预计位置靠近十字路口，说明该个交通流等候区的所有探测车辆均在十字路口等候。这时，交通流的绿灯时间就主要根据排在最远车辆之前的通行车辆数进行设定。

前面提到在各个调度时相，可设两个交通流同时穿过十字路口。这时绿灯时间的设定要根据两个进程交通流之间的最大预计设定通行时间来。算法2统计了各时相的时间调度函数。

算法2：各时相的时间调度函数

输入：交通流量i和j

1 Ifti>tjthen

返回ti

2 Else

返回tj

3IF结束；

3 实验分析和结果

本文算法采用城市交通仿真平台(SUMO)制作几个实验场景。SUMO是由德国宇航中心开发的，微观、连续的道路交通仿真架构和模型基础.通过道路交通微观仿真软件包，可以处理大量的道路网络。在这些场景中，通行车辆试图穿过由独立的智能交通信号灯控制一个十字路口。对各个场景使用不同的通行车辆数来研究交通密度的效果。

本文主要将TLSA与自适应交通信号控制机制(OAF)进行比较，得出本文算法在车载自组网(VANET)启用的车辆感应控制、VANET启用的Webster’s以及最优定时信号控制方面有很好的性能，能够缩短每台车辆的平均延时。

在实验中，首先比较由于交通灯队列延迟导致的车辆延时；然后对一定时间内在等候区准备通行十字路口的所有待检测车辆的总延时进行比较；最后，计算十字路口每秒通行的车辆数来评估各个机制的通行量。表2给出了实验的主要参数，如表2所示。

表2 仿真参数

TLSA与OAF方法的性能比较结果，如图3所示。

(a) 交通灯上每辆车的延时

(b) 等待区通过交通灯的车辆的总延时

(c) 交通灯的吞吐量 图3 OAF和TLSA的性能评估

对30个不同场景分别进行了实验。每个实验的置信区间是95%。图3(a)是每台车辆的平均延时对比结果，其中TLSA较之于OAF将每台通行车辆的平均延时降低30%。说明采用TLSA后每台车辆在十字路口的等候时间平均要减少30%。

对某一时间点要经过十字路口的所有待检测车辆的总延时进行分析。TLSA得到的总延时要比OAF的减少25%，如图3(b)所示。由图3(a)和3(b)可知，在所有交通密度场景下，TLSA要比OAF使通行车辆的队列延时减少25%。另一方面，图3(c)比较了TLSA与OAF对交通灯信号时相进行调度后，交通十字路口的通行量情况。显然，采用TLSA后每秒通过十字路口的车辆数比OAF的要多出30%，由于TLSA最大密度优先调度原理，将最长绿灯时相分配给在交通流密度最小的交通流，这样能探测到密度最大而数量较少的车辆。

4 总结

本文提出了一种智能交通灯调度算法(TLSA)。该算法利用到车辆自组技术来收集周边各交通流的实时交通特征。利用最大密度优先调度原理来对各交通灯周期的时相进行设置。将等候区定义在信号十字路口的附近区域，根据它可以判断各个时相的最大许可时间，但这个时间不得超出最长绿灯时间。各个时相的实际时间要根据各个交通流进程位置最远的车辆距离进行确定。通过实验得出TLSA算法要优于OAF算法。采用该算法后，各个车辆通行信号十字路口的延时平均减少20%；同时它还将各十字路口的通行量提高了30%。

[1] 文孟飞. 城市智能交通系统交通流协同优化与诱导关键技术研究[D].长沙：中南大学,2013:23-34.

[2] 王彬. 基于车路协同技术的交叉口协调方法研究[D].北京：北京工业大学,2013:56-70.

[3] 折志伟. 城市交通系统路口车流量的最优化控制[D].河北科技大学,2010:12-34.

[4] 张永灿,黄海平,曹雍,王汝传. 基于无线传感网的智能交通灯自适应算法[J]. 计算机技术与发展,2015(2):199-203.

[5] 孙卫真,王秀锦,徐远超. 交通信息分布式处理中的Hadoop调度算法优化[J]. 计算机工程与设计,2014(4):1269-1273.

[6] 许其清,朱炼,孙方南,朱袁峰. 多路口联控智能交通灯的设计与实现[J]. 控制工程,2009(4):34-38.

[7] 马骏,蔡延光,汤雅连,梁秉毅. 智能交通系统中车辆调度问题的自适应蚁群算法[J]. 北京联合大学学报(自然科学版),2015(1):75-80.

[8] 李慧,郭爱煌. 交通信号的实时公平调度及其仿真[J]. 计算机应用,2012(4):1161-1164.

[9] Priemer C, Friedrich B. A Decentralized Adaptive Traffic Signal Control Using V2I Communication Datas, Intelligent Transportation Systems[C].the 12th International IEEE Conference,2009: 1-7.

[10] Barba C T, Mateos M A, Soto P R, et al. Smart City for VANETs Using Warning Messages, Traffic Statistics and Intelligent Traffic Lights[J]. IEEE Intelligent Vehicles Symposium, 2012, 6(20):902-907.

[11] Mirchandani P, Head L. A Real-time Traffic Signal Control System:Architecture, Algorithms, and Analysis, Transportation Research [J].Emerging Technologies.2001,6(9):415-432,

[12] Baskar L D, De Schutter B, Hellendoorn J, et al. Traffic Control and Intelligent Vehicle Highway Systems: A Survey[J].Intelligent Transport Systems,2011,5(1):38-52.

[13] Krajzewicz D, Erdmann J, Behrisch M, et al. Recent De-velopment and Applications of SUMO Simulation of Urban Mobility[J].International Journal on Advances in Systems and Measurements, 2012, 5(4):128-138.

[14] Gradinescu V, Gorgorin C, Diaconescu R, et al. Adaptive Traffic Lights Using Car-to-Car Communication[J].Vehicular Technology:2007,65(2):21-25.

[15] Behrisch M, Bieker L, Erdmann J, et al. SUMO Simulation of Urban Mobility[C]. The Third International Conference on Advances in System Simulation, Barcelona, Spain,2011:63-68.

[16] Pandit K, Ghosal D, Zhang H M, et al. Adaptive Traffic Signal Control With Vehicular Ad hoc Networks, Vehicular Technology[J].IEEE Transactions, 2013,42(4): 1459-1471.

[17] Bani Younes M, Boukerche A. Efficient Traffic Congestion Detection Protocol for Next Generation VANETs[C]. 2013 IEEE International Conference on Communications (ICC), 2013, 9(13): 3764-3768.

Research on Scheduling Algorithm of Intelligent Traffic Light

Gao Weiwei

(The Department of Information Science, Heilongjiang International University, Harbin 150025, China)

The traffic signal is essential to guarantee safe driving at road intersection. Queuing delay of traffic flow damages and reduces the smooth smoothness ness of traffic flow. This paper proposed a scheduling algorithm of intelligent traffic light control (TLSA). First, it analyzed the real-time traffic characteristics of the traffic flow in an intersection, and the each traffic light time was scheduled. Secondly, in the intersection the traffic flow becomes easy and smooth by reducing waiting time of vehicles, hence, the crossing number of vehicles increases in every second. Finally, we compare TLSA to previous algorithms in this field by simulating different scenarios. Experiments show that this algorithm can not only shorten the queuing delay and improve the traffic flow signal scheduling, but also improve the traffic capacity of each signal intersection.

Traffic lights； Scheduling algorithm； Simulation platform of city traffic； Vehicular ad hoc network

黑龙江省教育厅科学技术研究项目(12543076)

高巍巍(1976-)，女,汉,副教授,硕士, CCF会员，研究方向：人工智能应用.

1007-757X(2017)04-0020-04

TP301.6

A

2016.05.12)