一種新型的有源標簽防碰撞算法

黃 茂， 張有光

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

0 引言

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

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

1 一種新穎的有源標簽防碰撞算法

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

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

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

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

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

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

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

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

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

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

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

1.2 主從讀寫器包拯救機制

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

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

1.3 空閑時隙利用機制

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

1.4 協(xié)議算法流程

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

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

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

圖2 幀起始命令示意

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

圖3 接入期邏輯時隙

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

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

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

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

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

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

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

6)在接入期結(jié)束后，進入收集期，讀寫器會發(fā)送命令，這其中包含了收集期時隙間隔t，標簽?zāi)苡嬎愠鲎约旱膽?yīng)該何時發(fā)送標簽信息(m-1)t,所有標簽完成與讀寫器通信，收集期結(jié)束。

2 仿真與結(jié)果

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

3 結(jié)語

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

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

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