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

黃 茂， 張有光

（北京航空航天大學，北京 100191）

0 引言

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

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

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

1.1 新協議基本思想

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

喚醒期，讀寫器向處于休眠的標簽發送一定持續時間的喚醒信號使得標簽進入工作狀態。標簽收到來自讀寫器的喚醒信號后，進入接收狀態并響應讀寫器命令。

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

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

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

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

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

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

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

4）幀動態結束，根據空閑邏輯時隙與已識別標簽數作為幀動態結束的評判依據。

1.2 主從讀寫器包拯救機制

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

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

1.3 空閑時隙利用機制

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

1.4 協議算法流程

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

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

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

圖2 幀起始命令示意

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

圖3 接入期邏輯時隙

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

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

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

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

若計數器值為 0的標簽啟動隨機數發生器后，生成隨機數均為 1，則沒有發送。讀寫器檢測到無數據傳輸時，發送 SUCCESS命令。檢測無數據傳輸的方法是閱讀在接收狀態等待一個給定的時間門限，而非一個分組長度。所有標簽計數器減 1，之后計數器為0的標簽進行發送。

讀寫器在一次成功接收后發送SUCCESS，若在給定時間門限內未收標簽回復，發送新的邏輯時隙起始命令，結束當前邏輯時隙并開始新的邏輯時隙。

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

6)在接入期結束后，進入收集期，讀寫器會發送命令，這其中包含了收集期時隙間隔t，標簽能計算出自己的應該何時發送標簽信息(m-1)t,所有標簽完成與讀寫器通信，收集期結束。

2 仿真與結果

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

3 結語

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

[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].通信技術,2009,42(07):94-96.

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