張 楠，方翰松

（1.山西大同大學(xué)煤炭工程學(xué)院，山西大同 037003；2.同濟大學(xué)電信學(xué)院，上海 200223）

智能交通ETC系統(tǒng)中電子標(biāo)簽的防碰撞算法研究

張 楠1，方翰松2

（1.山西大同大學(xué)煤炭工程學(xué)院，山西大同 037003；2.同濟大學(xué)電信學(xué)院，上海 200223）

公路的人工收費方式已經(jīng)成為我國公路車輛快速通行的瓶頸之一，使得研究與推廣不停車收費（ETC）系統(tǒng)成為我國公路交通的迫切需要。由于在實際情況下要求讀卡器能識別多個同時進入ETC車道的電子標(biāo)簽，所以需采取合適的防碰撞算法。 探討了一種基于CSMA/CA技術(shù)的電子標(biāo)簽防碰撞設(shè)計，并進行分析，提出合適的防碰撞方法，滿足了實際要求。

不停車收費系統(tǒng)；CSMA/CA；防碰撞；讀卡器；標(biāo)簽

電子不停車收費（Electronic Toll Collection，簡稱ETC）是國際上正在努力開發(fā)并推廣普及的一種用于道路交通的高效電子收費方式，是智能交通領(lǐng)域中的一個重要方面，它的最大特點是攜帶了電子標(biāo)簽的車輛可以以較高的速度通過路網(wǎng)中各收費口，而無須停車交費［1］。本文基于CSMA/CA技術(shù)設(shè)計了一種多標(biāo)簽防碰撞算法，可有效解決ETC系統(tǒng)中多標(biāo)簽識別的碰撞問題。

1 載波監(jiān)聽多路訪問/沖突避免

總線型局域網(wǎng)在MAC層的標(biāo)準(zhǔn)協(xié)議是CSMA/CD，但由于無線產(chǎn)品的適配器不易檢測信道是否存在沖突，因此802.11全新定義了一種新的協(xié)議，即載波偵聽多點接入/避免沖撞CSMA/CA（Carrier Sense Multiple Access With Collision Aviodance）。一方面，載波偵聽——查看信道是否空閑；另一方面，避免沖撞——通過隨機的時間等待，使信號沖突發(fā)生的概率減到最小，當(dāng)信道被偵聽到空閑時，優(yōu)先發(fā)送。不僅如此，為了系統(tǒng)更加穩(wěn)固，提供了帶確認幀ACK信號的CSMA/CA。在一旦遭受其他噪聲干擾，或者由于偵聽失敗時，信號沖突就有可能發(fā)生，而這種工作于MAC層的ACK信號此時能夠提供快速的恢復(fù)能力［2］。CSMA/CA工作如下：

1）當(dāng)一個節(jié)點有幀要發(fā)送時，首先偵聽信道。

2）如果一開始就偵聽到信道空閑，則發(fā)送該幀。

3）若信道忙，則選取一個隨機的回退值，并在偵聽到信道空閑時開始遞減該值。在此過程中若偵聽到信道忙，則停止遞減，并保持計數(shù)值不變。

4）當(dāng)計數(shù)值減為0時（僅可能發(fā)生在偵聽到信道為空閑時），該節(jié)點發(fā)送整個幀并等待確認。

5）若收到確認幀，表明幀發(fā)送成功。若還要發(fā)送下一個幀，從第2步開始CSMA/CA協(xié)議。若未收到確認，節(jié)點重新進入第2步中的回退階段，并從一個更大的范圍內(nèi)選取隨機值［3］。

在使用CSMA/CA技術(shù)時，需要給電子標(biāo)簽規(guī)定最大重發(fā)次數(shù)，即退避次數(shù)。具體流程如圖1所示。

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

2 電子標(biāo)簽的防碰撞

基于我國高速公路規(guī)定，系統(tǒng)要求車輛以30km/h～50km/h的速度通過讀卡器的圓形無線傳輸區(qū)域的直徑距離，為盡量減少因碰撞而造成的漏讀，使讀卡器的漏讀率不大于10-4。因此，根據(jù)我國國情，根據(jù)《公路路線設(shè)計規(guī)范》，ETC車道的設(shè)計車速一般定為40km/h［4］。本系統(tǒng)中無線芯片選用的是CC2420，CC2420采用圓極化貼片陶瓷天線，在輸出功率為-10dBm的情況下，無障礙環(huán)境中的通信距離可達30m以上。我們假設(shè)汽車是以40km/h的速度通過收費站，圓形通信區(qū)域的直徑是60m，則讀卡器能檢測到所有的電子標(biāo)簽的最大時長為：t＝60m/11m/s＝5.4s。

根據(jù)這一基本要求，系統(tǒng)設(shè)計時，就要保證在車載電子標(biāo)簽通過讀卡器有效接收區(qū)域的過程中，所有電子標(biāo)簽被讀卡器成功接收。但是，當(dāng)兩個或多個標(biāo)簽同時發(fā)送時，讀卡器往往不能識別出兩個標(biāo)簽的信息，會造成數(shù)據(jù)的丟失，這就是ETC系統(tǒng)中的并發(fā)碰撞問題。為了解決并發(fā)碰撞問題，就要對無線并發(fā)碰撞的概率進行研究。算法的實現(xiàn)流程如圖2所示。圖中SRXON和STXONCCA是單片機通過SPI總線發(fā)給CC2420的命令，STXONCCA的作用是檢測信道為空則發(fā)射，SRXON的作用是設(shè)置CC2420發(fā)射完后單片機進入休眠模式。

圖2 算法的實現(xiàn)流程圖

3 電子標(biāo)簽碰撞概率分析

3.1 兩個電子標(biāo)簽的碰撞概率

設(shè)電子標(biāo)簽的工作周期為T，電子標(biāo)簽的CSMA/CA偵聽時間為tL，判斷信道忙碌通常通過信道中載波信號電壓的大小作為偵聽依據(jù)，電子標(biāo)簽必須聽滿tL時間才能確認信道忙碌。電子標(biāo)簽的發(fā)送時間為tS，休眠時間為tW，兩個電子標(biāo)簽分別為MA和MB，它們的發(fā)送時間點處于不同位置時的工作狀況如圖3所示。

圖3中MB1，MB2，MB3，MB4表示電子標(biāo)簽MB四個不同的發(fā)送時間的狀態(tài)。MA'和MB4'分別表示MA和MB4檢測到信道忙碌退避發(fā)送的狀態(tài)。圖中時間段T為電子標(biāo)簽的正常工作周期。

當(dāng)MB的發(fā)送時間在時間點t1和t2之間（即圖中MB1到MB2）時，MB能夠發(fā)送成功，MA會偵聽到信道忙碌，隨機退避1到4個tS時長，在如圖MA'虛線位置發(fā)送無線信號；當(dāng)MB從時間點t4移動到t5（即圖中MB3到MB4）時，MA能夠發(fā)送成功，MB會偵聽到信道忙碌退避，如圖3所示；MB在MB4時間點偵聽到信道忙碌，會延時至MB4'發(fā)送。如果退避后信道空閑，MB可成功發(fā)送［5］。

而當(dāng)MB從時間點t2移動到t4時（即圖中MB2到MB3），MA和MB會因為偵聽的無線信號發(fā)送時間不夠長，將忙碌的信道認為空閑，兩個電子標(biāo)簽同時發(fā)送數(shù)據(jù)，造成無線并發(fā)碰撞，產(chǎn)生誤碼。此時，讀卡器會將這兩個電子標(biāo)簽產(chǎn)生的誤碼過濾掉。所以，在這個工作周期內(nèi)，電子標(biāo)簽MA和MB都不能被讀卡器識別。

在電子標(biāo)簽一個工作周期時長內(nèi)，設(shè)兩個電子標(biāo)簽相撞的概率為P（2），若電子標(biāo)簽偵聽信道忙碌時，不退避發(fā)送，直接進入休眠狀態(tài)，根據(jù)以上分析，MB在時間段MB1到MB4之間會和MA發(fā)生碰撞，可以得出兩個電子標(biāo)簽并發(fā)碰撞的概率為：

圖3 兩個電子標(biāo)簽不同置時的工作狀況

3.2 多個電子標(biāo)簽碰撞概率

將以上分析推廣到n個電子標(biāo)簽的情況，設(shè)其中有i個電子標(biāo)簽同時碰撞的概率為Pi，則有：

設(shè)n個電子標(biāo)簽并發(fā)的概率P（n）為，則這些電子標(biāo)簽碰撞的概率：

將（2）式代入（3）式并化簡得一個工作周期時長內(nèi)n個電子標(biāo)簽并發(fā)碰撞的概率：

據(jù)此可以認為，碰撞概率隨電子標(biāo)簽個數(shù)增加近似線性增大。

3.3 電子標(biāo)簽退避i次的漏讀率

根據(jù)圖3進一步分析，當(dāng)電子標(biāo)簽并發(fā)碰撞的時候，存在兩種情況。第一種情況是其中一個電子標(biāo)簽偵聽到信道忙碌退避發(fā)送，如圖3中MB1到MB2，以及MB3到MB4時間段所示。該電子標(biāo)簽可能發(fā)送成功，不會被漏讀；第二種情況是電子標(biāo)簽同時發(fā)送，因無法偵聽到信道忙碌不退避，無線碰撞產(chǎn)生誤碼被讀卡器過濾，造成兩個電子標(biāo)簽都被漏讀，如圖3中MB2到MB3的時間段所示。

設(shè)n個電子標(biāo)簽，若有并發(fā)碰撞就退避發(fā)送，再發(fā)生碰撞則繼續(xù)退避，直到i次為止，這時的總的碰撞概率為P（n，i），上述兩種情況的概率分別為P1（n，i）和P2（n，0）（第二種情況，電子標(biāo)簽不會退避重發(fā)），那么有：

根據(jù)前面的討論可以得到：

即P1（n，0）與P2（n，0）兩者之和等于電子標(biāo)簽不退避的碰撞概率。

當(dāng)電子標(biāo)簽的最大退避次數(shù)為i，根據(jù)（6）式，第一種情況下，可以計算出電子標(biāo)簽退避i次仍發(fā)送失敗的概率P1（n，i）：

由于第二種情況，每次碰撞會造成兩個電子標(biāo)簽發(fā)送失敗，而第一種情況的電子標(biāo)簽發(fā)送失敗不會影響到其它電子標(biāo)簽工作，那么設(shè)一個工作周期內(nèi)，退避i次漏讀率為Q（n，i）。根據(jù)（6）式和（7）式可以算出：

4 電子標(biāo)簽漏讀率分析

根據(jù)CC2420芯片數(shù)據(jù)手冊可知電子標(biāo)簽偵聽、發(fā)送時間等參數(shù)如表1所示［6］。

表1 CC2420參數(shù)

根據(jù)電子標(biāo)簽參數(shù)和公式（8）可知，多個電子標(biāo)簽并發(fā)識別（時假設(shè)有6輛車在射頻區(qū)域），根據(jù)6個標(biāo)簽以11m/s的速度通過讀卡器的覆蓋區(qū)域這一標(biāo)準(zhǔn)，計算出讀卡器讀完6個標(biāo)簽的最大時間為5.4s，即在5.4s內(nèi)每個標(biāo)簽發(fā)送成功。分別計算電子標(biāo)簽不退避、退避1次、退避2次，休眠時間1s，2s，3s時的漏讀率如表2所示。

表2 不同休眠時間電子標(biāo)簽漏讀率

由表2看出，在一個工作周期內(nèi)，隨著休眠時間的增大，電子標(biāo)簽并發(fā)漏讀率會減小。采用退避算法比不采用退避算法的漏讀率小很多，但是增加退避次數(shù)對減小漏讀率的效果并不明顯，所以在實際應(yīng)用中并不是退避次數(shù)越多越好。

要求讀卡器在6s內(nèi)讀完電子標(biāo)簽，當(dāng)電子標(biāo)簽的睡眠時間較短時，可在6s內(nèi)發(fā)送多次無線信號。設(shè)電子標(biāo)簽在5.4s內(nèi)至少發(fā)送k次無線信號，電子標(biāo)簽一個工作周期的漏讀率為Q（n，i），5.4s內(nèi)電子標(biāo)簽的漏讀率為（n，i），那么：

根據(jù)（9）式和表2可以算出5.4s內(nèi)電子標(biāo)簽并發(fā)的漏讀率如表3所示：

通過表3可以看出，5.4s之內(nèi)的漏讀率小于10-4，休眠時間可為2s和1s?？紤]到系統(tǒng)的無線穩(wěn)定性的要求，休眠時間我們定為2s，退避次數(shù)i＝1。

為了適應(yīng)今后高速公路的發(fā)展，如果車輛是以更快的速度經(jīng)過識別區(qū)域，我們以100km/h和150km/h這兩個速度再進一步分析電子標(biāo)簽的漏讀率。當(dāng)車輛以100km/h的速度經(jīng)過讀卡器識別區(qū)域時只需要2.2s，分別計算電子標(biāo)簽不退避、退避1次、退避2次，休眠時間0.2s，0.5s，1s時的漏讀率如表4所示。當(dāng)車輛以150km/h的速度經(jīng)過讀卡器識別區(qū)域時只需要1.4s，分別計算電子標(biāo)簽不退避、退避1次、退避2次，休眠時間0.2s，0.5s，1s時的漏讀率如表5所示。

表3 5.4s電子標(biāo)簽漏讀率

表4 2.2s電子標(biāo)簽漏讀率

表5 1.4s電子標(biāo)簽漏讀率

根據(jù)以上分析可知，當(dāng)車輛以150km/h的速度駛?cè)胱x卡器識別區(qū)域時，只要將標(biāo)簽的休眠時間改為0.5s或更低，退避一次以上，依然可以保證漏讀率滿足要求，考慮到系統(tǒng)無線穩(wěn)定性以及芯片自身性能的限制，休眠時間我們不能設(shè)置太小，要和芯片的實際收發(fā)時間相適應(yīng)。通過實際測量可知，CC2420的發(fā)射時間大約是1.6ms，所以選擇休眠0.5s，退避1次是可行的。

5 總結(jié)

文中詳細講解CSMA/CA算法和工作原理，以此為基礎(chǔ)設(shè)計了符合本系統(tǒng)要求的防碰撞算法，可以達到5.4s內(nèi)識別多個電子標(biāo)簽的要求；并進一步分析車速提高到100km/h和150km/h時電子標(biāo)簽的漏讀率。

［1］黎培興，田明忠，賀亦軍，等.感應(yīng)式IC卡路橋不停車收費的完美實現(xiàn)［J］.工業(yè)工程，1998，1（2）：53-56.

［2］溫炳.不停車收費系統(tǒng)（ETC）及其應(yīng)用［J］.山西交通科技，2003（1）：129-131.

［3］胡建，李強，閡昊，等.時隙ALOHA法在RFID系統(tǒng)防碰撞問題中的應(yīng)用［J］.應(yīng)用科學(xué)學(xué)報，2005，23（5）：489-492.

［4］白浩.高速公路不停車收費系統(tǒng)的研制［D］.鄭州：鄭州大學(xué)，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，F(xiàn)ANG 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-），男，山西大同人，講師，研究方向：監(jiān)控系統(tǒng)。