黃 茂， 張有光

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

0 引言

射頻識別（RFID）是一種非接觸性自動識別技術(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)有包在傳輸，并采用一種識別與通信分離機(jī)制，這樣減少碰撞的概率，但是文章并沒有對具體的識別期與收集期的算法進(jìn)行詳細(xì)定義。文獻(xiàn)[5]提出了一種跟RSSI估計(jì)標(biāo)簽數(shù)然后來動態(tài)控制標(biāo)簽接入概率的方法，在這種算法下清點(diǎn)速率改善很大，但是文章只提出信號強(qiáng)度估計(jì)標(biāo)簽數(shù)，在實(shí)際情況中很難做到精確估計(jì)。文獻(xiàn)[6]提出一種動態(tài)控制標(biāo)簽接入概率并進(jìn)行多階段競爭的機(jī)制，通過多次競爭提高包被識別的概率，但是這種方法只適用于用標(biāo)簽數(shù)較少的時(shí)候，文獻(xiàn)[7]和文獻(xiàn)[8]提出的算法都是基于二進(jìn)制樹搜索，對硬件資源要求高。這里將空閑時(shí)隙和碰撞時(shí)隙充分的利用起來，提出主從讀寫器包拯救機(jī)制和空閑時(shí)隙利用機(jī)制。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)若干個(gè)標(biāo)簽選擇同一個(gè)時(shí)隙的時(shí)候，通常會發(fā)生碰撞，并且這幾個(gè)包就會退避，在后面時(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，這樣從讀寫器就有可能在每次碰撞后都從碰撞的包中成功的識別出一個(gè)包，從讀寫器與主讀寫器有半個(gè)時(shí)隙的間隔，這樣避免兩個(gè)讀寫器之間的干擾。

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

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

1.4 協(xié)議算法流程

為了方便對協(xié)議性能進(jìn)行對比，算法流程著重在接入期和收集期，在接入期中標(biāo)簽在回復(fù)讀寫器時(shí)是以 RN16作為唯一標(biāo)識的，接入期會有若干個(gè)幀，每一幀有N個(gè)邏輯時(shí)隙，而每一個(gè)邏輯時(shí)隙中發(fā)生碰撞時(shí)，就會進(jìn)行二進(jìn)制搜索，這樣就可能有k個(gè)二進(jìn)制時(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í)隙序號信息。標(biāo)簽收到命令后，向讀寫器發(fā)送 RN16隨機(jī)碼，若邏輯時(shí)隙碰撞（如s2,s5），不進(jìn)行二進(jìn)制搜索，而是進(jìn)行從讀寫器包拯救，邏輯時(shí)隙成功識別（如s3,s7），不發(fā)送Ack，但別識別包進(jìn)入 Ack隊(duì)列，邏輯時(shí)隙空閑（如s4,s8），則在空閑內(nèi)發(fā)送 ack隊(duì)列中的 Ack包。在此過程中，若空閑邏輯時(shí)隙大于Nmin，或者識別標(biāo)簽大于Nmax，則該幀提前結(jié)束并調(diào)整Q值，進(jìn)入下一幀。任何一個(gè)標(biāo)簽在成功識別后，都會得到一個(gè)值作為該標(biāo)簽在收集期中的序列號m，如圖3所示。

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

3)在N個(gè)邏輯時(shí)隙結(jié)束后，主讀寫器發(fā)送二進(jìn)制搜索命令分別對之前的碰撞包進(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，并啟動隨機(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，啟動隨機(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)簽啟動隨機(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)簽被識別，這個(gè)過程中Q調(diào)會進(jìn)行動態(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ì)在一幀中識別出的標(biāo)簽數(shù)數(shù)目大于 16時(shí)，結(jié)束該幀，并將Q值增加1。Q初始值可設(shè)為 1。Q范圍[0,15]。

6)在接入期結(jié)束后，進(jìn)入收集期，讀寫器會發(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ù)對標(biāo)簽進(jìn)行散列，進(jìn)而減少發(fā)生碰撞的標(biāo)簽個(gè)數(shù)，且可以根據(jù)標(biāo)簽碰撞的情況，對 Q值和幀時(shí)隙數(shù) N值進(jìn)行動態(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ù)多的情況下防碰撞效率不高，文中研究主要針對標(biāo)簽數(shù)大于100的情況，提高了系統(tǒng)大標(biāo)簽數(shù)情況下的效率，在密集標(biāo)簽場景下，這種算法有很好的使用價(jià)值。在動態(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.