一種新型的有源標(biāo)簽防碰撞算法

黃 茂， 張有光

（北京航空航天大學(xué)，北京 100191）

0 引言

射頻識(shí)別（RFID）是一種非接觸性自動(dòng)識(shí)別技術(shù)，其中有源系統(tǒng)具有讀寫距離遠(yuǎn)、可靠性高、數(shù)據(jù)量大、發(fā)射功率低、標(biāo)簽功能更加復(fù)雜等特點(diǎn)。與無源 RFID一樣，標(biāo)簽防碰撞也是有源系統(tǒng)中需要研究和解決的問題，一方面，有源場景運(yùn)用比無源場景要復(fù)雜，另一方面，由于有源標(biāo)簽帶有電池，有源標(biāo)簽再功能比無源標(biāo)簽更強(qiáng)大，這也為設(shè)計(jì)效率更高的算法提供了可能。

目前，有源標(biāo)簽防碰撞的國際標(biāo)準(zhǔn) ISO/IEC 18000-7[1]只給出了一個(gè)基于幀時(shí)隙 ALOHA的最基本的算法，在算法效率上是相當(dāng)?shù)偷?。有源?biāo)簽防碰撞算法都是基于隨機(jī)競爭機(jī)制[2]，算法較為簡單，但是容易產(chǎn)生標(biāo)簽餓死現(xiàn)象。DCMA[3]引進(jìn)了控制信道去解決碰撞，讀寫器需要在兩個(gè)信道中進(jìn)行切換同時(shí)，但采用多個(gè)信道也增加了硬件開支。在文獻(xiàn)[4]中，提出一種基于載波偵聽的防碰撞方法，被用來檢測在傳送數(shù)據(jù)包之前是否已經(jīng)有包在傳輸，并采用一種識(shí)別與通信分離機(jī)制，這樣減少碰撞的概率，但是文章并沒有對(duì)具體的識(shí)別期與收集期的算法進(jìn)行詳細(xì)定義。文獻(xiàn)[5]提出了一種跟RSSI估計(jì)標(biāo)簽數(shù)然后來動(dòng)態(tài)控制標(biāo)簽接入概率的方法，在這種算法下清點(diǎn)速率改善很大，但是文章只提出信號(hào)強(qiáng)度估計(jì)標(biāo)簽數(shù)，在實(shí)際情況中很難做到精確估計(jì)。文獻(xiàn)[6]提出一種動(dòng)態(tài)控制標(biāo)簽接入概率并進(jìn)行多階段競爭的機(jī)制，通過多次競爭提高包被識(shí)別的概率，但是這種方法只適用于用標(biāo)簽數(shù)較少的時(shí)候，文獻(xiàn)[7]和文獻(xiàn)[8]提出的算法都是基于二進(jìn)制樹搜索，對(duì)硬件資源要求高。這里將空閑時(shí)隙和碰撞時(shí)隙充分的利用起來，提出主從讀寫器包拯救機(jī)制和空閑時(shí)隙利用機(jī)制。

1 一種新穎的有源標(biāo)簽防碰撞算法

1.1 新協(xié)議基本思想

提出的協(xié)議將標(biāo)簽識(shí)別過程劃分為4個(gè)階段，喚醒期，接入期，收集期和會(huì)話期，每個(gè)階段系統(tǒng)工作內(nèi)容如圖1所示。

喚醒期，讀寫器向處于休眠的標(biāo)簽發(fā)送一定持續(xù)時(shí)間的喚醒信號(hào)使得標(biāo)簽進(jìn)入工作狀態(tài)。標(biāo)簽收到來自讀寫器的喚醒信號(hào)后，進(jìn)入接收狀態(tài)并響應(yīng)讀寫器命令。

接入期，標(biāo)簽產(chǎn)生16位的隨機(jī)碼作為唯一標(biāo)識(shí)與讀寫器通信，讀寫器執(zhí)行一種aloha與二進(jìn)制搜索結(jié)合算法完成多標(biāo)簽接入。在接入期中有若干幀，只有當(dāng)全部標(biāo)簽識(shí)別完成后才進(jìn)入收集期，每一幀又有若干邏輯時(shí)隙，在當(dāng)前幀接入的標(biāo)簽隨機(jī)選擇一個(gè)時(shí)隙，若邏輯時(shí)隙成功識(shí)別，則讀寫器發(fā)送確認(rèn)信息(ack)告知標(biāo)簽識(shí)別成功，若邏輯時(shí)隙空閑則進(jìn)入下一個(gè)邏輯時(shí)隙，若邏輯時(shí)隙碰撞，則當(dāng)即讓碰撞的多個(gè)標(biāo)簽進(jìn)行二進(jìn)制搜索(在二進(jìn)制時(shí)隙中進(jìn)行)，在二進(jìn)制搜索中成功識(shí)別的標(biāo)簽，讀寫器也回對(duì)其發(fā)送ack，二進(jìn)制搜索結(jié)束后進(jìn)入下一個(gè)邏輯時(shí)隙。

收集期，讀寫器逐時(shí)隙完成對(duì)已接入標(biāo)簽信息的收集。標(biāo)簽在收到讀寫器的收集指令后，按照在接入期獲得的序列號(hào)，在各自時(shí)隙內(nèi)回復(fù)讀寫器需要的信息，并接收讀寫器確認(rèn)命令。

會(huì)話期，讀寫器根據(jù)標(biāo)簽身份信息逐個(gè)與需要通信的標(biāo)簽完成信息交互。

由于不同的場景和需求喚醒期和會(huì)話期的長短會(huì)不同，所以在對(duì)協(xié)議效率評(píng)估的過程中，一般只考慮接入期和收集期，所以歸一化吞吐量的計(jì)算從接入期開始收集期結(jié)束。在本協(xié)議中，有如下主要思想：

1）接入與收集分離，將標(biāo)簽的識(shí)別與數(shù)據(jù)通信分離開來，避免了較長數(shù)據(jù)包多次通信浪費(fèi)掉的時(shí)間。

2）Q值調(diào)整標(biāo)簽接入概率，并不是所有未識(shí)別標(biāo)簽都會(huì)在當(dāng)前幀中接入，而是在[0,2Q-1]之間任意選擇，隨機(jī)值為0才在當(dāng)前幀中接入，而Q值是有一個(gè)初始值，并且動(dòng)態(tài)調(diào)整的。

3）Aloha與二進(jìn)制搜索結(jié)合，在邏輯時(shí)隙選擇上采用 Aloha，在碰撞后的小數(shù)量識(shí)別中采用二進(jìn)制搜索。

4）幀動(dòng)態(tài)結(jié)束，根據(jù)空閑邏輯時(shí)隙與已識(shí)別標(biāo)簽數(shù)作為幀動(dòng)態(tài)結(jié)束的評(píng)判依據(jù)。

1.2 主從讀寫器包拯救機(jī)制

這種機(jī)制利用從讀寫器，在主讀寫器中發(fā)生了碰撞了的包會(huì)在這里被挽救，做到每碰撞一次都能挽救一個(gè)包。

當(dāng)若干個(gè)標(biāo)簽選擇同一個(gè)時(shí)隙的時(shí)候，通常會(huì)發(fā)生碰撞，并且這幾個(gè)包就會(huì)退避，在后面時(shí)隙中再參與競爭，可以利用這樣的機(jī)制，即使是碰撞了也能利用主從讀寫器從碰撞的包中讀一個(gè)出來，這樣用到了2個(gè)讀寫器，一個(gè)主讀寫器，一個(gè)從讀寫器，一般情況下主讀寫器進(jìn)行工作，從讀寫器是在住讀寫器發(fā)送碰撞時(shí)才發(fā)生工作，這里認(rèn)為標(biāo)簽是有載波偵聽能力的，他能確切感知到信道中發(fā)生了碰撞，碰撞的標(biāo)簽隨即進(jìn)行包拯救，在從讀寫器的時(shí)隙上按照一定的機(jī)制進(jìn)行競爭，標(biāo)簽都以 p=1/3的概率發(fā)送 RN16，這樣從讀寫器就有可能在每次碰撞后都從碰撞的包中成功的識(shí)別出一個(gè)包，從讀寫器與主讀寫器有半個(gè)時(shí)隙的間隔，這樣避免兩個(gè)讀寫器之間的干擾。

1.3 空閑時(shí)隙利用機(jī)制

在識(shí)別期，每一個(gè)包被識(shí)別后，讀寫會(huì)當(dāng)即回復(fù)一個(gè) Ack，其中包含了標(biāo)簽在收集期的序號(hào)，而在空閑邏輯時(shí)隙，讀寫器則不作任何的工作，直到該時(shí)隙定時(shí)器到時(shí)，進(jìn)入下一時(shí)隙，這樣浪費(fèi)了很多時(shí)間，這里的機(jī)制是讀寫器中擁有一個(gè) Ack隊(duì)列，不再是標(biāo)簽識(shí)別后當(dāng)即發(fā)送，而是在遇到空閑時(shí)隙時(shí)，讀寫器在空閑時(shí)隙間隔內(nèi)發(fā)送出Ack隊(duì)列中最前面的一個(gè)，在一幀中所有邏輯時(shí)隙結(jié)束后再將Ack隊(duì)列中未發(fā)送完的包發(fā)送出去。

1.4 協(xié)議算法流程

為了方便對(duì)協(xié)議性能進(jìn)行對(duì)比，算法流程著重在接入期和收集期，在接入期中標(biāo)簽在回復(fù)讀寫器時(shí)是以 RN16作為唯一標(biāo)識(shí)的，接入期會(huì)有若干個(gè)幀，每一幀有N個(gè)邏輯時(shí)隙，而每一個(gè)邏輯時(shí)隙中發(fā)生碰撞時(shí)，就會(huì)進(jìn)行二進(jìn)制搜索，這樣就可能有k個(gè)二進(jìn)制時(shí)隙，在識(shí)別完全后才在收集期進(jìn)行標(biāo)簽具體信息的通信。

讀寫器控制一定數(shù)量的標(biāo)簽逐幀參與接入，在幀內(nèi)的每一邏輯時(shí)隙中，標(biāo)簽以二進(jìn)制樹算法接入。讀寫器設(shè)定一個(gè)固定的幀長N，并將該幀分成N個(gè)邏輯時(shí)隙。參與當(dāng)前幀的標(biāo)簽在該幀的N個(gè)邏輯時(shí)隙中任意選擇一個(gè)時(shí)隙等候接入。讀寫器發(fā)送命令起始和結(jié)束一個(gè)邏輯時(shí)隙，并逐時(shí)隙完成整個(gè)幀的接入。標(biāo)簽收到各自的時(shí)隙起始命令后，在各自的邏輯時(shí)隙內(nèi)以二進(jìn)制樹算法接入。

1)讀寫器發(fā)送幀起始命令，該命令中包含參數(shù)Q和幀長數(shù)N。標(biāo)簽收到Q值后，在[0,2Q-1]之間任選一個(gè)整數(shù)。選擇 0的標(biāo)簽參與當(dāng)前幀的接入，非0的標(biāo)簽等待下一次幀起始命令。選擇0的標(biāo)簽在[0，N-1]之間選擇一個(gè)邏輯時(shí)隙數(shù)，如圖 2所示。

圖2 幀起始命令示意

2)讀寫器發(fā)送命令起始一個(gè)邏輯時(shí)隙，該命令包含邏輯時(shí)隙序號(hào)信息。標(biāo)簽收到命令后，向讀寫器發(fā)送 RN16隨機(jī)碼，若邏輯時(shí)隙碰撞（如s2,s5），不進(jìn)行二進(jìn)制搜索，而是進(jìn)行從讀寫器包拯救，邏輯時(shí)隙成功識(shí)別（如s3,s7），不發(fā)送Ack，但別識(shí)別包進(jìn)入 Ack隊(duì)列，邏輯時(shí)隙空閑（如s4,s8），則在空閑內(nèi)發(fā)送 ack隊(duì)列中的 Ack包。在此過程中，若空閑邏輯時(shí)隙大于Nmin，或者識(shí)別標(biāo)簽大于Nmax，則該幀提前結(jié)束并調(diào)整Q值，進(jìn)入下一幀。任何一個(gè)標(biāo)簽在成功識(shí)別后，都會(huì)得到一個(gè)值作為該標(biāo)簽在收集期中的序列號(hào)m，如圖3所示。

圖3 接入期邏輯時(shí)隙

3)在N個(gè)邏輯時(shí)隙結(jié)束后，主讀寫器發(fā)送二進(jìn)制搜索命令分別對(duì)之前的碰撞包進(jìn)行二進(jìn)制搜索，這里被從讀寫器拯救的包不再進(jìn)行該環(huán)節(jié)，最后將Ack隊(duì)列中未發(fā)送的包發(fā)送出去，并進(jìn)入下一幀，如圖4所示。

4)二進(jìn)制樹算法：讀寫器發(fā)送邏輯時(shí)隙起始命令，標(biāo)簽收到該命令后將各自內(nèi)部計(jì)數(shù)器置為 0，并啟動(dòng)隨機(jī)數(shù)發(fā)生器。所有生成隨機(jī)數(shù)為 1的標(biāo)簽使計(jì)數(shù)器加 1；所有生成隨機(jī)數(shù)為 0的標(biāo)簽，計(jì)數(shù)器值保持不變（計(jì)數(shù)器值為 0）。計(jì)數(shù)器值為 0的標(biāo)簽立即回復(fù)標(biāo)簽信息。

若讀寫器檢測到碰撞或錯(cuò)誤，發(fā)送接收錯(cuò)誤響應(yīng)命令 FAIL。標(biāo)簽收到FAIL命令后，若其計(jì)數(shù)器不等于 0，其計(jì)數(shù)器值加 1；若其計(jì)數(shù)器為 0，啟動(dòng)隨機(jī)數(shù)發(fā)生器，生成隨機(jī)數(shù)為 1的標(biāo)簽將計(jì)數(shù)器值加 1，生成隨機(jī)數(shù)為 0的標(biāo)簽保持計(jì)數(shù)器為 0，并再次發(fā)送。

若讀寫器檢測到標(biāo)簽發(fā)送成功，讀寫器發(fā)送SUCCESS命令。標(biāo)簽收到 SUCCESS命令后，標(biāo)簽計(jì)數(shù)器減1。

若計(jì)數(shù)器值為 0的標(biāo)簽啟動(dòng)隨機(jī)數(shù)發(fā)生器后，生成隨機(jī)數(shù)均為 1，則沒有發(fā)送。讀寫器檢測到無數(shù)據(jù)傳輸時(shí)，發(fā)送 SUCCESS命令。檢測無數(shù)據(jù)傳輸?shù)姆椒ㄊ情喿x在接收狀態(tài)等待一個(gè)給定的時(shí)間門限，而非一個(gè)分組長度。所有標(biāo)簽計(jì)數(shù)器減 1，之后計(jì)數(shù)器為0的標(biāo)簽進(jìn)行發(fā)送。

讀寫器在一次成功接收后發(fā)送SUCCESS，若在給定時(shí)間門限內(nèi)未收標(biāo)簽回復(fù)，發(fā)送新的邏輯時(shí)隙起始命令，結(jié)束當(dāng)前邏輯時(shí)隙并開始新的邏輯時(shí)隙。

5)重復(fù) 1)～4)的流程，直達(dá)所有標(biāo)簽被識(shí)別，這個(gè)過程中Q調(diào)會(huì)進(jìn)行動(dòng)態(tài)調(diào)整，接入過程中幀長數(shù)可設(shè)置為N=8。Q調(diào)整門限值可設(shè)置為 1，Nmin=3,Nmax=16.當(dāng)讀寫器估計(jì)在一幀空閑邏輯時(shí)隙大于 3，結(jié)束該幀，并將Q值減少 1。當(dāng)讀寫器估計(jì)在一幀中識(shí)別出的標(biāo)簽數(shù)數(shù)目大于 16時(shí)，結(jié)束該幀，并將Q值增加1。Q初始值可設(shè)為 1。Q范圍[0,15]。

6)在接入期結(jié)束后，進(jìn)入收集期，讀寫器會(huì)發(fā)送命令，這其中包含了收集期時(shí)隙間隔t，標(biāo)簽?zāi)苡?jì)算出自己的應(yīng)該何時(shí)發(fā)送標(biāo)簽信息(m-1)t,所有標(biāo)簽完成與讀寫器通信，收集期結(jié)束。

2 仿真與結(jié)果

由于成幀二進(jìn)制樹形分解算法通過 Q值控制接入的標(biāo)簽數(shù)，通過幀時(shí)隙數(shù)對(duì)標(biāo)簽進(jìn)行散列，進(jìn)而減少發(fā)生碰撞的標(biāo)簽個(gè)數(shù)，且可以根據(jù)標(biāo)簽碰撞的情況，對(duì) Q值和幀時(shí)隙數(shù) N值進(jìn)行動(dòng)態(tài)調(diào)整，同時(shí)采取了空閑時(shí)隙利用機(jī)制和主從讀寫器包拯救機(jī)制，將碰撞時(shí)隙和空閑時(shí)隙充分利用起來。由圖 5可以看到，文中標(biāo)準(zhǔn)采用的防碰撞算法隨著標(biāo)簽數(shù)的增加逐漸上升，歸一化吞吐量最高可達(dá)到 0.40左右。相比而言，ISO/IEC 18000-7標(biāo)簽數(shù)很少的情況下，歸一化吞吐量較高,但標(biāo)簽數(shù)的增加，吞吐量逐漸減低，最終分別穩(wěn)定在0.32左右，與文中協(xié)議存在較大差距，在大標(biāo)簽數(shù)量的情況下，文中協(xié)議的性能較 ISO/IEC 18000-7有30%的提高。

3 結(jié)語

文中提出的一種新型的有源標(biāo)簽防碰撞算法，提出了主從讀寫器包拯救機(jī)制和空閑時(shí)隙利用機(jī)制，在有源標(biāo)簽防碰撞過程中，系統(tǒng)能夠敏感的調(diào)整標(biāo)簽接入概率和幀長度，并且充分利用了無效時(shí)隙，提高了防碰撞效率。在以前的研究場景中，標(biāo)簽數(shù)較少，在標(biāo)簽數(shù)多的情況下防碰撞效率不高，文中研究主要針對(duì)標(biāo)簽數(shù)大于100的情況，提高了系統(tǒng)大標(biāo)簽數(shù)情況下的效率，在密集標(biāo)簽場景下，這種算法有很好的使用價(jià)值。在動(dòng)態(tài)控制標(biāo)簽競爭概率上可以進(jìn)行進(jìn)一步研究。

[1] International Organization for Standardization.ISO/IEC TR 24730-2009,Information technology --Radio frequency identification for item management -- Part 7: Parameters for active air interface communications at 433 MHz[S].USA:[s.n.],2009

[2] YU H Y, LI O, ZHANG X Y. A Wireless Sensor Networks Theory Implementation[C]//Technique and Implementation Conferrence of Beijing:National Defense Industry.BeiJing:[s.n.],2008:88-92.

[3] LI N, DUAN X, WU Y. An Anti-Collision Algorithm for Active RFID[C]//International Conference on Wireless Communications,Networking and Mobile Computing 2006.Wuhan: IEEE，2006:22-24.

[4] YOON W J, CHUNG S H, KWON Y G. A Novel Tag Collection Algorithm using an Identified Slot Scan for Active RFID Systems[C]//IEEE.21st Annual IEEE International Symposium on Personal,Indoor and Mobile Radio Communications. Soul:IEEE,2010:26-30.

[5] XIE Z H,LAI S L.Design and Implementation of an Active RFID MAC Protocol[C]//IEEE.International Conference on wireless Communications.Networking and Mobile Computing 2007. Beijing:IEEE,2007:21-25.

[6] PALOMO-LóPEZ A.CSMA Multi-Stage Anti-collision Protocol for Active RFID Systems[C]//Proceedings of the 4th International Workshop on RFID Technology.Madrid:[s.n.],2010:108-111.

[7] 滕培俊,熊偉,梁青,等.一種基于二進(jìn)制樹的 RFID防沖突算法研究[J].通信技術(shù),2009,42(07):94-96.

[8] 禹士朋,范文兵,李建華,等.超高頻 RFID系統(tǒng)中的放碰撞算法研究[J].通信技術(shù)，2010，43(09):118-120.