無(wú)線射頻識(shí)別技術(shù)（RFID）是一種利用射頻信號(hào)進(jìn)行非接觸自動(dòng)識(shí)別的技術(shù)，廣泛應(yīng)用于物流、供應(yīng)鏈管理、商業(yè)零售和交通運(yùn)輸?shù)阮I(lǐng)域。RFID系統(tǒng)一般由具有電子編碼（ID）的標(biāo)簽和閱讀器組成，它們利用無(wú)線信道實(shí)現(xiàn)相互通信來(lái)交換信息。當(dāng)系統(tǒng)中有多個(gè)標(biāo)簽同時(shí)向閱讀器發(fā)送數(shù)據(jù)時(shí)，將會(huì)產(chǎn)生相互干擾，使閱讀器不能正確接收信息，這就是標(biāo)簽碰撞。防碰撞算法能夠有效解決標(biāo)簽的碰撞問(wèn)題，實(shí)現(xiàn)閱讀器高效、快速地讀取標(biāo)簽信息。
　目前主要存在兩種類型的標(biāo)簽：有源標(biāo)簽和無(wú)源標(biāo)簽。前者通過(guò)電源提供能量來(lái)計(jì)算和發(fā)送信息，計(jì)算能力強(qiáng)，但使用成本高；后者通過(guò)接收閱讀器發(fā)送的電磁波獲得能量，計(jì)算能力有限，所以傳統(tǒng)網(wǎng)絡(luò)中的許多防碰撞技術(shù)難以直接應(yīng)用，但較低的成本更利于其在RFID系統(tǒng)中推廣使用。本文研究的是無(wú)源標(biāo)簽在RFID系統(tǒng)中的防碰撞問(wèn)題，并基于ALOHA提出了一種改進(jìn)算法，它能夠迅速處理當(dāng)前識(shí)別循環(huán)中發(fā)生的碰撞，從而有效降低此后在循環(huán)中發(fā)生標(biāo)簽碰撞的概率。仿真結(jié)果表明該方法效率較高，尤其在標(biāo)簽數(shù)量較大時(shí)相比動(dòng)態(tài)幀時(shí)隙算法（DFSA）消耗時(shí)隙更少。
1 幾種主要的防碰撞算法
　目前，RFID系統(tǒng)中的標(biāo)簽防碰撞算法主要分為基于ALOHA的算法和基于樹(shù)的算法兩大類。基于ALOHA的算法是隨機(jī)算法，該算法中標(biāo)簽利用隨機(jī)時(shí)間響應(yīng)閱讀器的命令。此類算法主要有時(shí)隙ALOHA算法、固定幀時(shí)隙算法、動(dòng)態(tài)幀時(shí)隙算法等，其中系統(tǒng)效率最高的是動(dòng)態(tài)幀時(shí)隙算法（DFSA）。算法中的“幀”是由閱讀器定義的一段時(shí)間長(zhǎng)度，其中包含若干時(shí)隙，每個(gè)時(shí)隙長(zhǎng)度等于標(biāo)簽的數(shù)據(jù)幀長(zhǎng)度。在ALOHA算法中標(biāo)簽需要具備產(chǎn)生隨機(jī)數(shù)的功能。
　　固定幀時(shí)隙算法是一種基本算法，每幀的時(shí)隙數(shù)相同。在開(kāi)始識(shí)別時(shí)，由閱讀器向作用范圍內(nèi)所有標(biāo)簽發(fā)送包含時(shí)隙數(shù)N的命令。標(biāo)簽收到命令后，將其時(shí)隙計(jì)數(shù)器置為1，開(kāi)始記錄時(shí)隙數(shù)，同時(shí)產(chǎn)生一個(gè)介于1和N的數(shù)作為其隨機(jī)選擇的時(shí)隙數(shù)值。當(dāng)時(shí)隙計(jì)數(shù)器值與標(biāo)簽隨機(jī)選擇的時(shí)隙數(shù)值相同時(shí)，向閱讀器發(fā)送應(yīng)答消息。若標(biāo)簽被閱讀器成功識(shí)別，則以后不再響應(yīng)閱讀器。一個(gè)幀結(jié)束后，閱讀器開(kāi)始識(shí)別時(shí)隙數(shù)同樣為N的新幀。該算法雖然簡(jiǎn)單但識(shí)別效率不高，由于幀長(zhǎng)固定，當(dāng)標(biāo)簽數(shù)遠(yuǎn)小于時(shí)隙數(shù)時(shí)，會(huì)產(chǎn)生較多的空閑時(shí)隙，浪費(fèi)系統(tǒng)資源；反之，則會(huì)產(chǎn)生過(guò)多的碰撞，大大降低系統(tǒng)效率。只有在標(biāo)簽數(shù)目與時(shí)隙數(shù)相差不大時(shí)，才會(huì)有較好的系統(tǒng)效率。由于該算法的時(shí)隙數(shù)不能隨著標(biāo)簽數(shù)目的變化而改變，因此，無(wú)法獲得穩(wěn)定的系統(tǒng)效率。
　動(dòng)態(tài)幀時(shí)隙算法(DFSA)是一種改進(jìn)的幀時(shí)隙算法，具有較高的效率。其每幀的時(shí)隙數(shù)會(huì)根據(jù)標(biāo)簽數(shù)目的不同而變化，主要執(zhí)行過(guò)程如下：(1)閱讀器估計(jì)在其作用范圍內(nèi)未識(shí)別的標(biāo)簽數(shù)目，從而決定下一幀需要的時(shí)隙數(shù)值N；(2)閱讀器發(fā)送包含N個(gè)時(shí)隙的幀，標(biāo)簽隨機(jī)選擇一個(gè)時(shí)隙向閱讀器發(fā)送應(yīng)答消息，在此過(guò)程中已被成功識(shí)別的標(biāo)簽將不再響應(yīng)閱讀器。重復(fù)執(zhí)行(1)、(2)的操作直至成功識(shí)別所有標(biāo)簽。該算法的效率在34.6%和36.8%之間[1]。
　二進(jìn)制樹(shù)算法系統(tǒng)效率高，但系統(tǒng)的設(shè)計(jì)復(fù)雜。其算法的基本思想是：將處于碰撞的標(biāo)簽分為左右兩個(gè)子集0和1，先查詢子集0，如果沒(méi)有碰撞，則正確識(shí)別標(biāo)簽，若仍然存在碰撞則再次分裂，把子集0分成00和01兩個(gè)子集，以此類推直到成功識(shí)別子集0中的所有標(biāo)簽，再按上述步驟查詢子集1。該算法雖然不存在錯(cuò)誤判決，但是整個(gè)識(shí)別過(guò)程需要逐一檢查標(biāo)簽ID前綴是否匹配，如果一個(gè)標(biāo)簽集中各個(gè)標(biāo)簽的ID非常相近，則完成整個(gè)識(shí)別過(guò)程需要花費(fèi)過(guò)長(zhǎng)的時(shí)間。
2 改進(jìn)的方法
　本文提出一種基于ALOHA協(xié)議的簡(jiǎn)單高效防碰撞算法，該算法能夠迅速處理標(biāo)簽發(fā)生的碰撞。當(dāng)發(fā)生碰撞時(shí)，系統(tǒng)會(huì)立刻開(kāi)始一個(gè)新的識(shí)別過(guò)程，此時(shí)閱讀器需要先估計(jì)發(fā)生碰撞的標(biāo)簽數(shù)目，然后向碰撞標(biāo)簽發(fā)送重新設(shè)置的時(shí)隙數(shù)值，而標(biāo)簽也會(huì)產(chǎn)生一個(gè)隨機(jī)選擇的時(shí)隙數(shù)值，當(dāng)該隨機(jī)數(shù)等于其時(shí)隙計(jì)數(shù)器時(shí)，向閱讀器發(fā)送應(yīng)答消息。如果在這個(gè)新的識(shí)別過(guò)程中再次發(fā)生碰撞，則重復(fù)執(zhí)行上述步驟，這樣可以減少如下情況的發(fā)生：當(dāng)前發(fā)生碰撞的標(biāo)簽在下一次循環(huán)中可能再次發(fā)生碰撞從而在系統(tǒng)中產(chǎn)生更多的碰撞。
　實(shí)驗(yàn)中假定有n個(gè)不同電子編碼(ID)的無(wú)源標(biāo)簽，閱讀器可以估計(jì)標(biāo)簽數(shù)目但是不知道其確切的值。設(shè)初始時(shí)隙數(shù)為Ni，當(dāng)開(kāi)始識(shí)別時(shí)，閱讀器向所有標(biāo)簽發(fā)送包含Ni的消息，標(biāo)簽收到后將產(chǎn)生一個(gè)介于1和Ni之間的隨機(jī)數(shù)，當(dāng)標(biāo)簽的時(shí)隙計(jì)數(shù)器值與其隨機(jī)產(chǎn)生的時(shí)隙數(shù)值相同時(shí)，將向閱讀器發(fā)送應(yīng)答消息。若此過(guò)程中沒(méi)有發(fā)生碰撞，則閱讀器就能成功識(shí)別標(biāo)簽。上述過(guò)程與ALOHA算法類似。但如果標(biāo)簽發(fā)生碰撞，閱讀器則放棄之前已經(jīng)成功識(shí)別的時(shí)隙，開(kāi)始一個(gè)新的識(shí)別過(guò)程(此處假定閱讀器和標(biāo)簽?zāi)軌虺晒ν瓿梢?guī)定的動(dòng)作)。在此過(guò)程中，閱讀器估計(jì)發(fā)生碰撞的標(biāo)簽數(shù)目nc[2]，通過(guò)nc來(lái)確定新設(shè)置的時(shí)隙數(shù)Nc，標(biāo)簽收到包含該數(shù)的消息后產(chǎn)生一個(gè)介于1和Nc之間的隨機(jī)數(shù)，重復(fù)執(zhí)行此過(guò)程直到不再發(fā)生碰撞。圖1是本文方法的流程圖，圖中閱讀器初始時(shí)發(fā)送包含Ni的消息，當(dāng)發(fā)生碰撞時(shí)，能夠迅速進(jìn)行處理。剩余的標(biāo)簽將在第一組碰撞標(biāo)簽處理完成后再進(jìn)行識(shí)別。

    前面在描述DFSA算法時(shí)提到，閱讀器會(huì)在第一輪識(shí)別完成后發(fā)送一個(gè)新設(shè)置的時(shí)隙數(shù)值給所有發(fā)生碰撞的標(biāo)簽，這些標(biāo)簽分別產(chǎn)生隨機(jī)選擇的時(shí)隙數(shù)。但是可以發(fā)現(xiàn)，第一輪識(shí)別中發(fā)生碰撞的標(biāo)簽同樣可能在之后的識(shí)別輪次中再次發(fā)生碰撞，而本文的方法能夠迅速處理標(biāo)簽的碰撞，降低碰撞標(biāo)簽以后再次發(fā)生碰撞的概率。閱讀器本身無(wú)法知道發(fā)生碰撞標(biāo)簽數(shù)目，但是可以通過(guò)估計(jì)得到nc，由nc確定重新設(shè)置的時(shí)隙數(shù)值Nc并開(kāi)始新的循環(huán)。為了獲得較優(yōu)的系統(tǒng)吞吐率，本文根據(jù)不同范圍的標(biāo)簽數(shù)由表1來(lái)確定Nc[3]。
　當(dāng)未被識(shí)別的標(biāo)簽數(shù)目很少時(shí)就不需要采用過(guò)大的時(shí)隙數(shù)值，反之如果標(biāo)簽數(shù)目很多而時(shí)隙數(shù)過(guò)小時(shí)，則發(fā)生碰撞的概率將會(huì)增加。當(dāng)設(shè)置的時(shí)隙數(shù)與需要識(shí)別的標(biāo)簽數(shù)目相等時(shí)，可以獲得最大系統(tǒng)效率[4]。因此，選擇合適的時(shí)隙數(shù)非常重要。在本文的方法中，將根據(jù)表1的數(shù)據(jù)來(lái)確定識(shí)別過(guò)程中不斷改變的時(shí)隙數(shù)值。
　為了執(zhí)行本文的方法，需先定義一個(gè)特殊的命令“throw_away”，它表示開(kāi)始執(zhí)行該方法的各個(gè)步驟，程序1所示是閱讀器需執(zhí)行程序的偽碼，描述了當(dāng)閱讀器檢測(cè)到標(biāo)簽碰撞時(shí)將會(huì)發(fā)生的動(dòng)作。當(dāng)c>0時(shí)，表示發(fā)生碰撞，閱讀器將發(fā)送throw_away命令給碰撞標(biāo)簽；ad是針對(duì)碰撞標(biāo)簽的計(jì)數(shù)值，當(dāng)發(fā)生碰撞時(shí)，ad的值加1；在此之后閱讀器將通過(guò)估計(jì)碰撞標(biāo)簽數(shù)目來(lái)確定Nc。
    程序1 檢測(cè)到碰撞時(shí)閱讀器執(zhí)行的程序
　　/*Reader:*/
　　    /*發(fā)送”throw_away”命令*/
　　    if (c>0)  /* 發(fā)生碰撞*/
    /* 閱讀器發(fā)送throw_away命令給發(fā)生碰撞的標(biāo)簽 */
　　    tag_respond = tag (throw_away);   
　　　　if ( tag_respond > 0 )  /* 命令發(fā)送成功 */
　　        ad = ad + 1;  /*當(dāng)發(fā)生碰撞時(shí)ad的值增加1 */
　　    tag (ad);  /* 將ad的值發(fā)送給標(biāo)簽 */
　　    start a new round;
　　    broadcast Nc;
    程序2所示是標(biāo)簽需執(zhí)行程序的偽碼，描述了碰撞標(biāo)簽收到閱讀器發(fā)送的throw_away命令后將會(huì)發(fā)生的動(dòng)作。通過(guò)設(shè)置ct的值來(lái)限制碰撞標(biāo)簽應(yīng)答閱讀器，當(dāng)標(biāo)簽接收到throw_away命令時(shí)其值加1；當(dāng)標(biāo)簽隨機(jī)選擇的時(shí)隙數(shù)等于其時(shí)隙計(jì)數(shù)器值，并且ad與ct相等時(shí)，發(fā)送應(yīng)答消息給閱讀器，同時(shí)ct值置0，標(biāo)簽再次收到throw_away命令之前不再響應(yīng)閱讀器。
    程序2 接收到throw_away命令時(shí)標(biāo)簽執(zhí)行的程序
　　/*  Tag:  */
　　/* 從閱讀器處獲取初始參數(shù) */
　　ct = 1;
　　transmission;
　　receive the number of slots;
　　generate random numbers;
　　if ( slot = = ti && ct = = ad )
　　　　transmit message;  /* 標(biāo)簽發(fā)送應(yīng)答消息 */
　　　　ct = 0;   /* 發(fā)送完成后ct置0 */
　　if (receive “throw_away”)
　　　　ct = ct + 1;
　　    goto transmission;
    如果在最后一個(gè)時(shí)隙中發(fā)生標(biāo)簽碰撞，系統(tǒng)將會(huì)放棄之前已經(jīng)成功識(shí)別的時(shí)隙。若此情況經(jīng)常出現(xiàn)，則系統(tǒng)效率會(huì)降低很多，這是應(yīng)用本文方法理論上可能會(huì)發(fā)生的最壞情況。圖2的仿真結(jié)果是這種情況發(fā)生的概率，從中可以看出當(dāng)標(biāo)簽數(shù)量較大時(shí)，這種最壞的情況發(fā)生概率其實(shí)很小。因此，當(dāng)標(biāo)簽數(shù)目較多時(shí)，這種最壞的情況幾乎不會(huì)發(fā)生，而應(yīng)用本文的方法就可以減少識(shí)別過(guò)程中的時(shí)隙消耗。

3 仿真結(jié)果
    大量標(biāo)簽向閱讀器發(fā)送消息時(shí)產(chǎn)生碰撞，假定標(biāo)簽數(shù)從10增加到300，圖3是應(yīng)用本文方法進(jìn)行仿真得到的結(jié)果。從中可以看出本文方法比DFSA算法耗費(fèi)的時(shí)隙少，并且標(biāo)簽數(shù)目越多差別越明顯。這表明對(duì)比DFSA算法，本文方法節(jié)約了時(shí)隙資源。

　為獲得較高的系統(tǒng)效率，仿真時(shí)設(shè)初始時(shí)隙數(shù)Ni為16，約為開(kāi)始時(shí)的標(biāo)簽數(shù)目。可以通過(guò)改變初始時(shí)隙數(shù)Ni來(lái)觀察所產(chǎn)生的影響，圖4表明，當(dāng)初始時(shí)隙數(shù)變?yōu)?4時(shí)，即使標(biāo)簽數(shù)目增加，系統(tǒng)效率也不會(huì)有明顯的變化；但標(biāo)簽數(shù)目較少時(shí)，較大的初始時(shí)隙數(shù)Ni對(duì)應(yīng)較小的碰撞發(fā)生概率,此時(shí)，Ni=128時(shí)的系統(tǒng)效率比Ni=16和Ni=64時(shí)低。上述結(jié)果表明初始時(shí)隙數(shù)Ni設(shè)為16，可以應(yīng)用于標(biāo)簽數(shù)較多的情況。
　設(shè)初始幀長(zhǎng)Ni為16，持續(xù)增加標(biāo)簽數(shù)目，仿真結(jié)果如圖5所示。可以看出，當(dāng)標(biāo)簽數(shù)持續(xù)增加時(shí)，本文方法耗費(fèi)的時(shí)隙數(shù)明顯小于DFSA算法；而當(dāng)標(biāo)簽數(shù)較少時(shí)，這種差異并不明顯。綜上，本文提出的方法系統(tǒng)效率優(yōu)于DFSA算法，并且耗費(fèi)更少的時(shí)隙。

　本文提出了一種基于ALOHA協(xié)議的簡(jiǎn)單高效RFID系統(tǒng)防碰撞算法。閱讀器先給標(biāo)簽發(fā)送一個(gè)包含初始時(shí)隙數(shù)的消息，標(biāo)簽收到后隨機(jī)選擇一個(gè)時(shí)隙同時(shí)將自己的時(shí)隙計(jì)數(shù)器置為1。當(dāng)標(biāo)簽隨機(jī)選擇的時(shí)隙數(shù)等于時(shí)隙計(jì)數(shù)器時(shí)，回復(fù)其電子編碼(ID)給閱讀器，如果發(fā)生碰撞，閱讀器將放棄已經(jīng)成功識(shí)別的時(shí)隙而開(kāi)始新的識(shí)別循環(huán)，這樣使碰撞標(biāo)簽?zāi)艿玫窖杆偬幚怼Ｔ摲椒ㄖ虚喿x器能夠在新的識(shí)別循環(huán)中首先鑒別出碰撞標(biāo)簽，然后再識(shí)別其余的標(biāo)簽。當(dāng)標(biāo)簽數(shù)增加到1 000時(shí)，本文方法比DFSA算法少耗費(fèi)約54%的時(shí)隙，并且系統(tǒng)效率可以穩(wěn)定在35%左右，相比DFSA算法此時(shí)約20%[5]的效率也有較大提高。
參考文獻(xiàn)
[1] 許武忠，胡斌杰. 一種新穎快速的二進(jìn)制搜索防碰撞算法[J].中國(guó)電子商情(RFID技術(shù)與應(yīng)用)，2008(3):26－28.
[2] VOGT H. Efficient object identification with passive RFID tags[C]. International Conference on Pervasive Computing. LNCS, Springer-Verlag,2002.
[3] 程良倫，林偉勇. 一種穩(wěn)定高效的動(dòng)態(tài)幀時(shí)隙ALOHA算法[J]. 計(jì)算機(jī)應(yīng)用研究,2009,26(1):85－91.
[4] VOGT H. Multiple object identification with passive RFID tags[C]. Systems, Man and Cybernetics, 2002 IEEE International Conference, 2002,10(3):6－9.
[5] 張頗，崔喆. RFID系統(tǒng)中的一種改進(jìn)的防碰撞算法[J].計(jì)算機(jī)應(yīng)用, 2008,28(8):2141－2143.