標(biāo)簽反碰撞的自適應(yīng)K路分裂和預(yù)信號(hào)

Adaptivek-WaySplittingandPre-SignalingforRFIDTagAnti-CollisionRFID標(biāo)簽反碰撞的自適應(yīng)K路分裂和預(yù)信號(hào)Abstract在RFID系統(tǒng)，閱讀器通過共享的無(wú)線信道通信查詢標(biāo)簽來(lái)識(shí)別標(biāo)簽。當(dāng)多個(gè)標(biāo)簽同時(shí)把它們的ID發(fā)送到閱讀器，碰撞就會(huì)發(fā)生，這大大影響了標(biāo)簽識(shí)別的性能。因此如何去減少標(biāo)簽碰撞從而加快識(shí)別速度是非常重要的。現(xiàn)有幾種協(xié)議防止標(biāo)簽碰撞?？梢园阉鼈兎譃槿悾夯続LOHA、基本樹型和基于計(jì)數(shù)器。其中基于計(jì)數(shù)器的協(xié)議有相對(duì)較好的性能。本文使用自適應(yīng)K路分開和預(yù)信號(hào)的概念提出一個(gè)基于計(jì)數(shù)器的反碰撞算法。我們同樣進(jìn)行仿真實(shí)驗(yàn)，將該算法與ISO/IEC18000-6B反碰撞協(xié)議進(jìn)行比較，證明該算法的先進(jìn)性。關(guān)鍵詞:RFID,反碰撞,ISO/IEC18000-6B1.引言基于ALOHA的協(xié)議比較簡(jiǎn)單，但它有標(biāo)簽饑餓的問題，這使得它們的應(yīng)答經(jīng)常相碰撞，它們很難識(shí)別?；跇湫团c基于計(jì)算器的協(xié)議沒有標(biāo)簽饑餓的問題。這兩類協(xié)議的基本思想是重復(fù)地把碰撞的標(biāo)簽分裂為幾組直到組里只有一個(gè)標(biāo)簽。區(qū)別在于前者靜態(tài)地依靠于分裂的標(biāo)簽ID，后者動(dòng)態(tài)地依靠于變化的計(jì)數(shù)器。前者有確定性的分裂，可能有相對(duì)較長(zhǎng)的查詢時(shí)延；后者有機(jī)率性的分裂，時(shí)延較短。ISO/IEC18000-6B是一個(gè)采用基于計(jì)數(shù)器的反碰撞算法的標(biāo)準(zhǔn)。

2．相關(guān)工作

在這個(gè)部分里我們簡(jiǎn)單介紹三類反碰撞協(xié)議：基于ALOHA協(xié)議、基于樹型協(xié)議、基于計(jì)數(shù)器協(xié)議。A．基于ALOHA的協(xié)議基于ALOHA的協(xié)議比較簡(jiǎn)單，適用于只讀標(biāo)簽。不過它們存在標(biāo)簽饑餓問題，致使標(biāo)簽因應(yīng)答信號(hào)的碰撞而不能被識(shí)別。B．基于樹型的協(xié)議基于樹型的協(xié)議存在一個(gè)確定性識(shí)別過程，其中一些算法假設(shè)標(biāo)簽有存儲(chǔ)器，另一些沒作這種假設(shè)。例如查詢樹型算法沒有基于標(biāo)簽存儲(chǔ)器，而bit-by-bit二進(jìn)制樹型協(xié)議通過利用標(biāo)簽存儲(chǔ)器來(lái)提高識(shí)別性能。沒有存儲(chǔ)器的標(biāo)簽比較便宜，但會(huì)導(dǎo)致比較差的識(shí)別性能。

2．相關(guān)工作

C．基于計(jì)數(shù)器的協(xié)議ISO/IEC18000-6B是一個(gè)采用基于計(jì)數(shù)器反碰撞算法的標(biāo)準(zhǔn)。在ISO/IEC18000-6B里，每個(gè)標(biāo)簽使用一個(gè)動(dòng)態(tài)改變的計(jì)數(shù)器和一個(gè)隨機(jī)位產(chǎn)生器。全部計(jì)數(shù)器初始化為0，計(jì)數(shù)器為0的標(biāo)簽可以將它們的ID發(fā)送出去，當(dāng)碰撞發(fā)生后，閱讀器就會(huì)通知碰撞的標(biāo)簽，計(jì)數(shù)器值大于0的標(biāo)簽就把計(jì)數(shù)值加1，而計(jì)數(shù)器為0的標(biāo)簽隨機(jī)產(chǎn)生一個(gè)位0或1，并把這個(gè)位加到計(jì)數(shù)值。通過這種方法可以將發(fā)生碰撞的標(biāo)簽分為兩種。這個(gè)過程一直執(zhí)行到計(jì)數(shù)值為0的標(biāo)簽只有一個(gè)為止。當(dāng)成功識(shí)別一個(gè)標(biāo)簽后，這個(gè)標(biāo)簽將保持沉默不再參與識(shí)別。當(dāng)沒有碰撞時(shí)，閱讀器會(huì)通知其它標(biāo)簽的計(jì)數(shù)值減1。當(dāng)標(biāo)簽數(shù)目比較小時(shí)，基于計(jì)數(shù)器的協(xié)議時(shí)延較小，當(dāng)標(biāo)簽數(shù)目較大時(shí)，其性能也是可以接受的。3．提出算法

在這個(gè)部分里，我們提出一個(gè)新的基于計(jì)數(shù)器的反碰撞算法，稱為AKS，使用了自適應(yīng)K路分裂和預(yù)信號(hào)這兩種方法來(lái)減少標(biāo)簽碰撞和閱讀器與標(biāo)簽之間的信息傳輸。下面我們分別介紹這兩種方法。3.提出算法A.自適應(yīng)K路分裂假設(shè)有N個(gè)標(biāo)簽在一個(gè)閱讀器的工作域，依照ISO18000-6B標(biāo)準(zhǔn)，如果只有一個(gè)標(biāo)簽的計(jì)數(shù)值為0，它就會(huì)被成功地識(shí)別，但當(dāng)有兩個(gè)以上的標(biāo)簽計(jì)數(shù)值為0，它們就會(huì)再隨機(jī)就分為兩組。AKS不同的地方就是把它們分為K組，而不是兩組，此處K為標(biāo)簽數(shù)目的估計(jì)值。原始分裂組（PSG）對(duì)自適應(yīng)K路分裂是必要的。如圖1所示，把它們從上到下編號(hào)為PSG1,,PSG2,...PSG里的標(biāo)簽再分為帶有不同計(jì)數(shù)值的小組，如圖2所示。閱讀器動(dòng)態(tài)地跟隨每個(gè)PSG的最小計(jì)數(shù)值從而使標(biāo)簽可以分到合適的PSG。3.提出算法自適應(yīng)K路分裂的基本思想是把一個(gè)PSG組再分為K組，K等于PSG里的標(biāo)簽數(shù)。從參考文獻(xiàn)[3]我們可知當(dāng)PSG里有K個(gè)標(biāo)簽時(shí)K路分裂的性能最好。我們不知道PSG組里的標(biāo)簽確切數(shù)目K。可以有技巧地通過已經(jīng)識(shí)別的標(biāo)簽數(shù)來(lái)估計(jì)K。3.提出算法在估計(jì)到K后，把PSG分為K組，PSG標(biāo)簽隨機(jī)選擇從0到K的數(shù)字然后加到計(jì)數(shù)值上，這樣就可以分為K組。其它不在此PSG組的標(biāo)簽將它們的計(jì)數(shù)值增加K，如圖3所示。當(dāng)應(yīng)用了自適應(yīng)K路分裂法后，在一小組里只有一個(gè)標(biāo)簽的可能性極大。

3．提出算法

B．預(yù)信號(hào)為了提高識(shí)別的性能，我們?cè)诩僭O(shè)閱讀器可以通過檢測(cè)信號(hào)強(qiáng)度來(lái)監(jiān)測(cè)碰撞的基礎(chǔ)上，提出了預(yù)信號(hào)。在ISO/IEC18000-6B里，只有計(jì)數(shù)值為0的標(biāo)簽才可以響應(yīng)。而在預(yù)信號(hào)方案里每個(gè)計(jì)數(shù)值為1的標(biāo)簽把1發(fā)送到響應(yīng)窗口的前面，這些位稱為預(yù)信號(hào)位，而計(jì)數(shù)值為0的響應(yīng)信號(hào)緊跟其后，預(yù)信號(hào)位的值可以有空、1個(gè)1和多個(gè)1的值Is三種情況。（情況1）預(yù)信號(hào)位值為空。意味著沒有標(biāo)簽計(jì)數(shù)值為1。在所有計(jì)數(shù)值為0的標(biāo)簽被識(shí)別后，閱讀器會(huì)通知所有未識(shí)別的標(biāo)簽將計(jì)數(shù)值減2。這樣可以減少一個(gè)沒有響應(yīng)的周期。3．提出算法

（情況2）預(yù)信號(hào)位為1個(gè)1。意味著只有一個(gè)標(biāo)簽的計(jì)數(shù)值為1，這個(gè)標(biāo)簽在下一個(gè)周期可以成功地被識(shí)別而不會(huì)發(fā)生碰撞，這種情況閱讀器按原計(jì)劃運(yùn)行。（情況3）預(yù)信號(hào)位為多個(gè)1。意味著計(jì)數(shù)值為1的標(biāo)簽有多個(gè)，閱讀器在識(shí)別完所有計(jì)數(shù)值為0的標(biāo)簽后立刻通知這些標(biāo)簽進(jìn)行分組，此時(shí)這些標(biāo)簽就可以隨機(jī)分為計(jì)數(shù)值為0和1兩組，省去了原始標(biāo)準(zhǔn)閱讀器通知各標(biāo)簽計(jì)數(shù)值減1、等待響應(yīng)、檢測(cè)到碰撞、通知此組標(biāo)簽計(jì)數(shù)值隨機(jī)加0或1而其它組標(biāo)簽計(jì)數(shù)值加1這幾個(gè)步驟。借助于預(yù)信號(hào)位，閱讀器與標(biāo)簽間的信號(hào)傳輸可以大大減少。自適應(yīng)K路算法和預(yù)信號(hào)方法都應(yīng)用的話就可以顯著地提升標(biāo)簽識(shí)別的性能。我們將通過下一部分的仿真表示出來(lái)。4．仿真本部分中我們對(duì)AKS進(jìn)行仿真，并比較它與ISO/IEC18000-6B采納的反碰撞算法的標(biāo)簽碰撞次數(shù)、識(shí)別所有標(biāo)簽所需的閱讀器與標(biāo)簽間的通信次數(shù)。仿真程序用java語(yǔ)言編寫，小數(shù)目（小于500）和大數(shù)目（大于500）的標(biāo)簽識(shí)別分別執(zhí)行了1000次。4．仿真A．碰撞次數(shù)如圖4和圖5所示，當(dāng)標(biāo)簽數(shù)為500時(shí)，AKS的碰撞次數(shù)為ISO18000-6B的30.3%。從圖4和圖5的里我們還可以看出標(biāo)簽越多AKS協(xié)議越有效。B．閱讀器發(fā)信號(hào)次數(shù)當(dāng)閱讀器準(zhǔn)備好去查詢標(biāo)簽和接收標(biāo)簽的響應(yīng)時(shí)，它就發(fā)出選擇命令。計(jì)數(shù)值為0的標(biāo)簽把它們的ID回應(yīng)到閱讀器。閱讀器會(huì)發(fā)出成功或失敗的命令通知標(biāo)簽它們的響應(yīng)狀態(tài)。成功命令表明只有一個(gè)或沒有響應(yīng)，而失敗命令表明有多個(gè)響應(yīng)。由圖6和圖7，當(dāng)標(biāo)簽數(shù)為500時(shí)，AKS閱讀器發(fā)信號(hào)的次數(shù)只是ISO18000-6B的62.9%。還可以看出標(biāo)簽越多，AKS的效率越高。如果我們只計(jì)算由標(biāo)簽碰撞和無(wú)碰撞響應(yīng)產(chǎn)生的額外命令，而不計(jì)算標(biāo)簽識(shí)別成功的命令，當(dāng)標(biāo)簽數(shù)為5000時(shí)，AKS閱讀器發(fā)信號(hào)的次數(shù)只是ISO18000-6B的41%。4.仿真C．標(biāo)簽識(shí)別時(shí)延比較AKS與ISO/IEC18000-6B反碰撞算法的標(biāo)簽識(shí)別時(shí)延，即完成所有標(biāo)簽識(shí)別所消耗的時(shí)間Td，式（4）中各縮寫的意思如表1所示，參數(shù)按ISO/IEC18000-6B的設(shè)定(表2)，設(shè)閱讀器發(fā)送命令的時(shí)間為1.5ms，標(biāo)簽響應(yīng)信號(hào)的時(shí)間為2.7ms，無(wú)響應(yīng)時(shí)間為0.5ms。表3是仿真結(jié)果，從表中我們可以看出AKS只用了ISO18000-6B標(biāo)準(zhǔn)的60%時(shí)間來(lái)識(shí)別所有標(biāo)簽。5．結(jié)論

本文我們提出一個(gè)新的基于計(jì)數(shù)器的反碰撞協(xié)議AKS，使用了兩個(gè)方法：自適應(yīng)K路分裂和