智能交通ETC系统中电子标签的防碰撞算法研究

张 楠，方翰松

（1.山西大同大学煤炭工程学院，山西大同 037003；2.同济大学电信学院，上海 200223）

智能交通ETC系统中电子标签的防碰撞算法研究

张 楠1，方翰松2

（1.山西大同大学煤炭工程学院，山西大同 037003；2.同济大学电信学院，上海 200223）

公路的人工收费方式已经成为我国公路车辆快速通行的瓶颈之一，使得研究与推广不停车收费（ETC）系统成为我国公路交通的迫切需要。由于在实际情况下要求读卡器能识别多个同时进入ETC车道的电子标签，所以需采取合适的防碰撞算法。 探讨了一种基于CSMA/CA技术的电子标签防碰撞设计，并进行分析，提出合适的防碰撞方法，满足了实际要求。

不停车收费系统；CSMA/CA；防碰撞；读卡器；标签

电子不停车收费（Electronic Toll Collection，简称ETC）是国际上正在努力开发并推广普及的一种用于道路交通的高效电子收费方式，是智能交通领域中的一个重要方面，它的最大特点是携带了电子标签的车辆可以以较高的速度通过路网中各收费口，而无须停车交费［1］。本文基于CSMA/CA技术设计了一种多标签防碰撞算法，可有效解决ETC系统中多标签识别的碰撞问题。

1 载波监听多路访问/冲突避免

总线型局域网在MAC层的标准协议是CSMA/CD，但由于无线产品的适配器不易检测信道是否存在冲突，因此802.11全新定义了一种新的协议，即载波侦听多点接入/避免冲撞CSMA/CA（Carrier Sense Multiple Access With Collision Aviodance）。一方面，载波侦听——查看信道是否空闲；另一方面，避免冲撞——通过随机的时间等待，使信号冲突发生的概率减到最小，当信道被侦听到空闲时，优先发送。不仅如此，为了系统更加稳固，提供了带确认帧ACK信号的CSMA/CA。在一旦遭受其他噪声干扰，或者由于侦听失败时，信号冲突就有可能发生，而这种工作于MAC层的ACK信号此时能够提供快速的恢复能力［2］。CSMA/CA工作如下：

1）当一个节点有帧要发送时，首先侦听信道。

2）如果一开始就侦听到信道空闲，则发送该帧。

3）若信道忙，则选取一个随机的回退值，并在侦听到信道空闲时开始递减该值。在此过程中若侦听到信道忙，则停止递减，并保持计数值不变。

4）当计数值减为0时（仅可能发生在侦听到信道为空闲时），该节点发送整个帧并等待确认。

5）若收到确认帧，表明帧发送成功。若还要发送下一个帧，从第2步开始CSMA/CA协议。若未收到确认，节点重新进入第2步中的回退阶段，并从一个更大的范围内选取随机值［3］。

在使用CSMA/CA技术时，需要给电子标签规定最大重发次数，即退避次数。具体流程如图1所示。

图1 CSMA/CA防碰撞算法流程图

2 电子标签的防碰撞

基于我国高速公路规定，系统要求车辆以30km/h～50km/h的速度通过读卡器的圆形无线传输区域的直径距离，为尽量减少因碰撞而造成的漏读，使读卡器的漏读率不大于10-4。因此，根据我国国情，根据《公路路线设计规范》，ETC车道的设计车速一般定为40km/h［4］。本系统中无线芯片选用的是CC2420，CC2420采用圆极化贴片陶瓷天线，在输出功率为-10dBm的情况下，无障碍环境中的通信距离可达30m以上。我们假设汽车是以40km/h的速度通过收费站，圆形通信区域的直径是60m，则读卡器能检测到所有的电子标签的最大时长为：t＝60m/11m/s＝5.4s。

根据这一基本要求，系统设计时，就要保证在车载电子标签通过读卡器有效接收区域的过程中，所有电子标签被读卡器成功接收。但是，当两个或多个标签同时发送时，读卡器往往不能识别出两个标签的信息，会造成数据的丢失，这就是ETC系统中的并发碰撞问题。为了解决并发碰撞问题，就要对无线并发碰撞的概率进行研究。算法的实现流程如图2所示。图中SRXON和STXONCCA是单片机通过SPI总线发给CC2420的命令，STXONCCA的作用是检测信道为空则发射，SRXON的作用是设置CC2420发射完后单片机进入休眠模式。

图2 算法的实现流程图

3 电子标签碰撞概率分析

3.1 两个电子标签的碰撞概率

设电子标签的工作周期为T，电子标签的CSMA/CA侦听时间为tL，判断信道忙碌通常通过信道中载波信号电压的大小作为侦听依据，电子标签必须听满tL时间才能确认信道忙碌。电子标签的发送时间为tS，休眠时间为tW，两个电子标签分别为MA和MB，它们的发送时间点处于不同位置时的工作状况如图3所示。

图3中MB1，MB2，MB3，MB4表示电子标签MB四个不同的发送时间的状态。MA'和MB4'分别表示MA和MB4检测到信道忙碌退避发送的状态。图中时间段T为电子标签的正常工作周期。

当MB的发送时间在时间点t1和t2之间（即图中MB1到MB2）时，MB能够发送成功，MA会侦听到信道忙碌，随机退避1到4个tS时长，在如图MA'虚线位置发送无线信号；当MB从时间点t4移动到t5（即图中MB3到MB4）时，MA能够发送成功，MB会侦听到信道忙碌退避，如图3所示；MB在MB4时间点侦听到信道忙碌，会延时至MB4'发送。如果退避后信道空闲，MB可成功发送［5］。

而当MB从时间点t2移动到t4时（即图中MB2到MB3），MA和MB会因为侦听的无线信号发送时间不够长，将忙碌的信道认为空闲，两个电子标签同时发送数据，造成无线并发碰撞，产生误码。此时，读卡器会将这两个电子标签产生的误码过滤掉。所以，在这个工作周期内，电子标签MA和MB都不能被读卡器识别。

在电子标签一个工作周期时长内，设两个电子标签相撞的概率为P（2），若电子标签侦听信道忙碌时，不退避发送，直接进入休眠状态，根据以上分析，MB在时间段MB1到MB4之间会和MA发生碰撞，可以得出两个电子标签并发碰撞的概率为：

图3 两个电子标签不同置时的工作状况

3.2 多个电子标签碰撞概率

将以上分析推广到n个电子标签的情况，设其中有i个电子标签同时碰撞的概率为Pi，则有：

设n个电子标签并发的概率P（n）为，则这些电子标签碰撞的概率：

将（2）式代入（3）式并化简得一个工作周期时长内n个电子标签并发碰撞的概率：

据此可以认为，碰撞概率随电子标签个数增加近似线性增大。

3.3 电子标签退避i次的漏读率

根据图3进一步分析，当电子标签并发碰撞的时候，存在两种情况。第一种情况是其中一个电子标签侦听到信道忙碌退避发送，如图3中MB1到MB2，以及MB3到MB4时间段所示。该电子标签可能发送成功，不会被漏读；第二种情况是电子标签同时发送，因无法侦听到信道忙碌不退避，无线碰撞产生误码被读卡器过滤，造成两个电子标签都被漏读，如图3中MB2到MB3的时间段所示。

设n个电子标签，若有并发碰撞就退避发送，再发生碰撞则继续退避，直到i次为止，这时的总的碰撞概率为P（n，i），上述两种情况的概率分别为P1（n，i）和P2（n，0）（第二种情况，电子标签不会退避重发），那么有：

根据前面的讨论可以得到：

即P1（n，0）与P2（n，0）两者之和等于电子标签不退避的碰撞概率。

当电子标签的最大退避次数为i，根据（6）式，第一种情况下，可以计算出电子标签退避i次仍发送失败的概率P1（n，i）：

由于第二种情况，每次碰撞会造成两个电子标签发送失败，而第一种情况的电子标签发送失败不会影响到其它电子标签工作，那么设一个工作周期内，退避i次漏读率为Q（n，i）。根据（6）式和（7）式可以算出：

4 电子标签漏读率分析

根据CC2420芯片数据手册可知电子标签侦听、发送时间等参数如表1所示［6］。

表1 CC2420参数

根据电子标签参数和公式（8）可知，多个电子标签并发识别（时假设有6辆车在射频区域），根据6个标签以11m/s的速度通过读卡器的覆盖区域这一标准，计算出读卡器读完6个标签的最大时间为5.4s，即在5.4s内每个标签发送成功。分别计算电子标签不退避、退避1次、退避2次，休眠时间1s，2s，3s时的漏读率如表2所示。

表2 不同休眠时间电子标签漏读率

由表2看出，在一个工作周期内，随着休眠时间的增大，电子标签并发漏读率会减小。采用退避算法比不采用退避算法的漏读率小很多，但是增加退避次数对减小漏读率的效果并不明显，所以在实际应用中并不是退避次数越多越好。

要求读卡器在6s内读完电子标签，当电子标签的睡眠时间较短时，可在6s内发送多次无线信号。设电子标签在5.4s内至少发送k次无线信号，电子标签一个工作周期的漏读率为Q（n，i），5.4s内电子标签的漏读率为（n，i），那么：

根据（9）式和表2可以算出5.4s内电子标签并发的漏读率如表3所示：

通过表3可以看出，5.4s之内的漏读率小于10-4，休眠时间可为2s和1s。考虑到系统的无线稳定性的要求，休眠时间我们定为2s，退避次数i＝1。

为了适应今后高速公路的发展，如果车辆是以更快的速度经过识别区域，我们以100km/h和150km/h这两个速度再进一步分析电子标签的漏读率。当车辆以100km/h的速度经过读卡器识别区域时只需要2.2s，分别计算电子标签不退避、退避1次、退避2次，休眠时间0.2s，0.5s，1s时的漏读率如表4所示。当车辆以150km/h的速度经过读卡器识别区域时只需要1.4s，分别计算电子标签不退避、退避1次、退避2次，休眠时间0.2s，0.5s，1s时的漏读率如表5所示。

表3 5.4s电子标签漏读率

表4 2.2s电子标签漏读率

表5 1.4s电子标签漏读率

根据以上分析可知，当车辆以150km/h的速度驶入读卡器识别区域时，只要将标签的休眠时间改为0.5s或更低，退避一次以上，依然可以保证漏读率满足要求，考虑到系统无线稳定性以及芯片自身性能的限制，休眠时间我们不能设置太小，要和芯片的实际收发时间相适应。通过实际测量可知，CC2420的发射时间大约是1.6ms，所以选择休眠0.5s，退避1次是可行的。

5 总结

文中详细讲解CSMA/CA算法和工作原理，以此为基础设计了符合本系统要求的防碰撞算法，可以达到5.4s内识别多个电子标签的要求；并进一步分析车速提高到100km/h和150km/h时电子标签的漏读率。

［1］黎培兴，田明忠，贺亦军，等.感应式IC卡路桥不停车收费的完美实现［J］.工业工程，1998，1（2）：53-56.

［2］温炳.不停车收费系统（ETC）及其应用［J］.山西交通科技，2003（1）：129-131.

［3］胡建，李强，阂昊，等.时隙ALOHA法在RFID系统防碰撞问题中的应用［J］.应用科学学报，2005，23（5）：489-492.

［4］白浩.高速公路不停车收费系统的研制［D］.郑州：郑州大学，2006.11.

［5］LEE S R，JOO S D，LEE C W.An enhanced dynamic framed slotted ALOHA algorithm for RFID Tag［A］.Proceeding of the Second Annual International Conference on Mobile and Ubiquitous Systems：Networking and Services［C］.2005：166-172.

［6］CC2420datashee［tDB/OL］.（2010-01-06）［2010-09-20］.http://www.issi.com/index.html.

〔编辑 石白云〕

Tag Anti-collision Designment of ETC System

ZHANG Nan1，FANG Han-song2
（1.School of Coal Engineering，Shanxi Datong University，Datong Shanxi，037003；2.Institute of Electrical Information，Tongji University，Shanghai，200092）

Highway artificial charging methods have become road vehicles to pass on one of the bottlenecks，make development and research of electronic toll collection system become an urgent need for road transport.In fact，as the reader can simultaneously identify multiple tags into the ETC lane，the system need to take the appropriate anti-collision algorithm，this paper uses CSMA/CA technology，make appropriate anti-collision algorithm to meet the system requirements.

Electronic Toll Collection（ETC）；CSMA/CA；anti-collision；reader；tagv

TP393

A

1674-0874（2011）01-080-04

2010-11-12

张楠（1981-），男，山西大同人，讲师，研究方向：监控系统。