改進的二進制搜索防碰撞算法*

賈 浩，沈 岳,2，匡迎春，王 金

(1.湖南農業大學 信息科技學院，湖南 長沙 410128； 2.湖南省農村農業信息化工程技術研究中心，湖南 長沙 410128)

改進的二進制搜索防碰撞算法*

賈 浩1，沈 岳1,2，匡迎春1，王 金1

(1.湖南農業大學 信息科技學院，湖南 長沙 410128； 2.湖南省農村農業信息化工程技術研究中心，湖南 長沙 410128)

針對射頻識別(Radio Frequency Identification,RFID)系統中多個標簽同時與閱讀器交互所產出的碰撞以及二進制搜索算法中出現的信息冗余和搜索效率低的問題，提出了一種改進二進制搜索防碰撞算法。該算法動態地調整閱讀器發送的指令，利用標簽沖突位構建識別樹，從而大幅降低了閱讀器與標簽的交互次數及傳輸的數據量，有效地提高了標簽識別的效率。通過MATLAB對系統的吞吐率、搜索次數以及閱讀器發送的信息量進行仿真，仿真結果表明該算法與已有的二進制搜索算法相比，具有一定優勢。

RFID；二進制搜索；防碰撞算法；碰撞位

0 引言

射頻識別(Radio Frequency Identification，RFID) 是一種通過無線電信號識別特定目標并讀寫相關數據的非接觸式的自動識別技術。當射頻識別系統開始工作時，閱讀器通過天線發射射頻信號，并產生電磁場區域。在電磁場區域內，多個標簽同時向閱讀器傳遞信息時，造成了信息的沖突，就會出現標簽的識別沖突，使閱讀器不能高效、準確、實時地識別標簽的問題，即標簽碰撞問題。

RFID防碰撞算法主要有以 ALOHA 算法為代表的概率性算法和以二進制搜索算法為代表的確定型算法[1]。當大量標簽并存時，ALOHA 算法的幀沖撞嚴重，易引起性能急劇惡化，不適宜大規模標簽讀取[2]。二進制搜索算法解決了“標簽饑餓”問題，同時解決了時隙大量浪費的問題，因此以二進制搜索算法為基礎的改進算法到了廣泛應用[3]。

二進制搜索算法雖然解決了時隙大量浪費以及標簽識別準確率低的問題，但是在搜索過程中產生了大量的冗余信息以及部分重復路徑，造成了閱讀器識別的效率較低。因此本文提出了一種改進的二進制搜索防碰撞算法。該算法能夠動態地對閱讀器發送的指令進行調整，在保證標簽正確識別的基礎上，減少閱讀器與標簽之間的搜索路徑以及閱讀器發送的冗余信息，極大地提高了標簽的識別效率。

1 二進制搜索算法

二進制搜索算法中采用曼徹斯特(Manchester)編碼實現閱讀器確定標簽碰撞的準確比特位置。曼徹斯特編碼用電平跳變(上升沿/下降沿)來表示數值位,可在多個標簽同時響應時按位識別出碰撞位。同時根據標簽碰撞的位置，按一定規則重新搜索標簽。

1.1 基本二進制搜索算法

基本二進制搜索算法以標簽的ID號為識別基礎。首先閱讀器發送全“1”的序列號，各個標簽將接收的序列號與自身的ID號比較。若標簽的ID的二進制數值小于或等于閱讀器發送的序列號，則該標簽將自身的ID回傳給閱讀器，否則不作響應。基本二進制搜索算法具體步驟如下：

(1)閱讀器發送一個全“1”的序列號請求命令，工作區域內的所有標簽同時收到請求命令后，將其自身的ID回傳給閱讀器。

(2)閱讀器對接收到的標簽的ID進行逐一檢測，判斷有無碰撞位。

(3)確定標簽發生碰撞時，將閱讀器發送的序列號請求命令的最高碰撞位置“0”，并作為新的命令由閱讀器發送，對標簽進行逐一檢測。若標簽ID的二進制數值小于或等于閱讀器發送的序列號，則作出響應。若標簽繼續存在碰撞，則繼續修改閱讀器發送的命令序列號，直到沒有碰撞產生。

(4)閱讀器通過發送的命令，篩選出響應的標簽并直接讀取標簽的信息，然后將標簽置為“去選擇”狀態。在閱讀器工作范圍內，只有當標簽被閱讀器激活，才能再次對閱讀器發送的請求命令作出響應。

(5)重復步驟(1)～(4)，即可識別出全部標簽。

分析基本二進制搜索算法的搜索過程發現兩方面的冗余信息。第一，閱讀器每識別一個標簽后，重新發送新的命令，從頭開始進行新一輪的搜索，沒有利用之前搜索過程中獲取的標簽信息，增加了標簽的搜索路徑。第二，基本二進制搜索算法中將閱讀器發送的序列號中的最高碰撞位后的所有比特位都置為“1”，而這部分編碼不能提供關于標簽的任何信息，產生了大量的冗余信息[4]。

1.2 后退式二進制搜索算法

后退式二進制搜索算法針對基本二進制搜索算法中每識別一個標簽都要從頭開始進行新一輪搜索的問題進行了改進。將后退式二進制搜索算法識別標簽的過程用二叉樹來描述，其主要的改進點為：后退二進制算法完成一個標簽的識別后不返回根節點，而是從離此標簽最近的有待識別標簽的內部節點開始搜索，直到該分支點以下標簽全部搜索完畢，然后繼續向上返回進行搜索[5]。具體識別過程如表1所示。

針對后退式二進制搜索算法的搜索過程進行分析，該算法縮短了閱讀器的搜索路徑，極大地加快了識別的過程。然而，后退式二進制搜索算法中將閱讀器發送的序列號中的最高碰撞位后的所有比特位都置為“1”，而這部分編碼不能提供關于標簽的任何信息，產生了大量的冗余信息。同時，標簽回傳給閱讀器的最高碰撞位之前的信息，對于閱讀器也是已知的。

1.3 動態二進制搜索算法

動態二進制搜索算法針對基本二進制搜索算法中閱讀器發送的序列號中包含大量冗余信息的問題進行了改進：讀寫器在發出指令(Request)得到碰撞位后，會以已知部分(L-1～X,X)作為搜索依據，X為當前最高沖突位，L為標簽序列號長度。序列號前X位與L-1～X相同的標簽將剩下的X-1～0位返回給讀寫器[6]，該算法的識別過程如表2所示。

表2 動態二進制搜索算法具體識別過程

針對動態二進制搜索算法的搜索過程進行分析，該算法極大地減少了傳輸的數據量和搜索所需的時間，提高了標簽識別的效率。然而，動態二進制搜索算法中閱讀器每識別一個標簽后，重新發送新的命令，從頭開始進行新一輪的搜索，沒有利用之前搜索過程中獲取的標簽信息，增加了標簽的搜索路徑。

2 改進的二進制搜索算法

2.1 算法基本思想

已有的幾種二進制搜索算法都是按照某種規則自頂向下構建識別樹，中間節點的構建和訪問識別樹的子葉以及如何動態調整閱讀器發送的命令都是搜索過程當中非常重要的環節。本算法基于二進制算法做出了以下幾個方面的改進。

(1)閱讀器發送的信息量減少。本算法采用了動態二進制算法的思想：閱讀器發送的命令序列號是動態改變的。但是，改進的二進制算法中閱讀器發送的命令序列號的長度是固定的，只是閱讀器發送的內容發生了改變。此外，閱讀器內容的改變也是有規律的。改進算法發送的命令序列號為兩位，默認為“00”，每識別一個電子標簽后自動加“1”，變為“01”，依此規律，直到閱讀器發送的命令序列號為“11”或標簽全部被識別。改進的二進制算法在保證閱讀器科學、準確、高效識別電子標簽的前提下，有效地減少了閱讀器發送的總的信息量。

(2)閱讀器搜索次數的減少。這主要通過對標簽碰撞位中“0”的個數識別標簽，隨后以標簽碰撞位的數據為子葉節點，構建自底向上的識別樹，通過計算識別數的葉子節點中“0”的個數即可實現標簽的識別。該方法減少了識別樹中間節點的個數，有效降低了識別樹的復雜度，縮短了標簽識別的過程，減少了閱讀器搜索的次數。

2.2 算法流程

改進的二進制搜索算法流程如下：

(1)閱讀器發送Request(1)命令，閱讀器工作區域內的標簽將自己的ID號回傳給閱讀器，并檢測出標簽的碰撞位，依此設定碰撞設定命令CID。

(2)當標簽發生碰撞時，根據碰撞位中“0”的唯一個數來識別標簽，篩選出“0”的個數唯一的發生碰撞的電子標簽。

(3)閱讀器初始化發送的命令序列號，發送的命令序列號的信息為碰撞設定命令CID，默認為“00”。標簽根據CID確定對比的碰撞位，確保閱讀器發送的序列號只與標簽的最高兩位碰撞位信息進行比較。

(4)閱讀器發送Request(CUID)，CUID自動累加1，標簽將自身的最高兩位碰撞位與CUID比較，若標簽最高兩位碰撞位小于或等于CUID，則標簽作出響應；否則，標簽不予響應。

(5)直至CUID重新置為“00”或標簽沒有碰撞時，識別結束。

3 仿真實驗與分析

本文對基本二進制搜索算法、后退式二進制搜索算法、動態二進制搜索算法以及本文提出的改進二進制搜索算法針對標簽數量較大、標簽碰撞位連續及標簽碰撞位不連續等幾種情況進行對比分析。

假設閱讀器工作范圍內有N個標簽，標簽的序列號為M位，標簽的碰撞位數為L(L=Log2N)位。

針對于二進制算法的特點，需要循環遍歷搜索。因此，識別N個標簽所需的次數為:

T1(N)=N*(log2N+1)

傳輸數據的長度為:

L1(N)=M*[N*(log2N+1)]

系統的吞吐率為：

針對動態二進制搜索算法的特點，識別N個標簽的次數為:

T2(N)=N*(log2N+1)

傳輸數據的長度為:

系統的吞吐率為：

針對后退式二進制搜索算法的特點，識別N個標簽的次數為:

T3(N)=2N-1

傳輸數據的長度為:

L3(N)=M(2N-1)

系統的吞吐率為：

針對改進的二進制搜索算法，假設閱讀器搜索N個標簽的次數為T4(N)=2L-1+1,采用數學歸納法證明：

(1)當L=1時，即標簽只有一位碰撞位，閱讀器的工作范圍內只有兩個標簽，根據算法流程，即T4(1)=2。

(2)當L=2時，表示標簽有兩位碰撞位，閱讀器的工作范圍內有4個標簽，根據算法流程，即T4(2)=3；

(3)假設L-1個標簽碰撞位時等式成立，即T4(N)=2L-1-1+1，則增加一位標簽碰撞位，增加的標簽碰撞位與之前的標簽碰撞位位置完全不同，需要增加2L-1-1次搜索操作才能全部識別，即T4(N)= 2L-1-1+1+ 2L-1-1=2L-1+1,等式成立。

傳輸數據的長度為：

L4(N)=2*(2L-1+1)

系統的吞吐率為：

以閱讀器搜索的次數和標簽傳輸的信息量以及系統的吞吐率為例，對以上幾種算法對比分析。閱讀器對標簽的搜索次數對比如圖1所示。當碰撞的標簽的數量較少時，改進的二進制搜索算法優勢并不明顯，且閱讀器發送的指令增加了標簽設計的復雜性，消耗了標簽的能量。當碰撞的標簽數量較多時，改進的二進制搜索算法能夠較大幅地減少閱讀器的搜索次數，其優勢對比更加明顯。碰撞標簽與閱讀器之間傳輸的信息量對比如圖2所示。

圖1 四種搜索算法搜索次數對比分析

圖2 四種算法傳輸的數據總量對比分析

搜索算法明顯低于二進制搜索算法和動態二進制搜索算法，且比后退式二進制算法減少一半以上。當標簽的碰撞位較少，而碰撞的標簽較多時，改進的二進制搜索算法減少的閱讀器與標簽之間的通信量將會更加明顯。系統的吞吐率如圖3所示。當標簽的數目少于100時，改進的二進制搜索算法的系統吞吐率極大地優于其他幾種算法，提高了系統識別的效率。

圖3 四種算法吞吐效率對比分析

4 結論

本文針對RFID系統中已有的二進制搜索算法的冗余度高、傳輸數據量大、識別效率低的問題，提出了一種改進的二進制搜索算法。該算法只處理碰撞位的信息，在一定程度上減少了閱讀器發送的信息量，從而提高了標簽的識別效率。通過MATLAB模擬仿真表明，改進的二進制搜索算法與其他二進制搜索算法相比，該算法在標簽的識別次數和閱讀器發送的通信量以及系統的吞吐率方面都體現出一定的優勢，具有較高的識別效率。

[1] Liu Xiaohui, Qian Zhihong, Wang Guiqin, et al. An improved RFID anti-collision algorithm[J]. Advanced Materials Research, 2013, 791-793:1243-1246.

[2] Zhang Lijuan, Zhang Jin, Tang Xiaohu. Assigned tree slotted aloha RFID tag anti-collision protocols[J]. IEEE Transactions on Wireless Communications, 2013, 12(11):5493-5505.

[3] 馮娜,潘偉杰,李少波,等. 基于新穎跳躍式動態搜索的RFID防碰撞算法[J]. 計算機應用,2012,32(1):288-291.

[4] 吳躍前,辜大光,范振粵,等. RFID系統防碰撞算法比較分析及其改進算法[J]. 計算機工程與應用,2009,45(3):210-213.

[5] 周艷聰,孫曉晨,顧軍華. 一種改進二進制防碰撞算法研究[J]. 計算機應用研究,2012,29(1):256-259,262.

[6] 李飛,曹敦,傅明. 一種BIBD編碼的RFID防碰撞算法的改進[J]. 計算機應用與軟件,2012,29(6):151-154,166.

Improved binary search anti-collision algorithm in RFID system

Jia Hao1, Shen Yue1,2, Kuang Yingchun1, Wang Jing1

(1. College of Information Science and Technology, Hunan Agricultural University, Changsha 410128, China;2. Hunan Research Center of Rural and Agricultural Informatization Engineering Technology, Changsha 410128, China)

Aiming at the issues of the RFID(Radio Frequency Identification) system such as the generated collision when multiple tags and reader inteact as well as the information redundancy and the low search efficiency in the process of binary search algorithm，this essay carries out an improved binary search algorithm for avoiding collision. The algorithm reduces the data quantity of interaction times and transmission of multiple tags and reader by adjusting the transferred instruction of reader and constructing recognition tree through using tag collision bit, therefore, it improves the efficiency of label recognition. Through the use of MATLAB, the throughput, search times of the system and the amount of information transmitted by the reader are simulaled. The result shows that compared to the existed binary search algorithm, the improved algorithm has certain advantages.

RFID; binary search; anti-collision algorithm; collision bit

國家科技支撐計劃(2012BAD35B05)

TP301

A

10.19358/j.issn.1674- 7720.2017.16.007

賈浩，沈岳，匡迎春，等.改進的二進制搜索防碰撞算法[J].微型機與應用，2017,36(16)：23-25,29.

2017-02-28)

賈浩(1990-)，男，碩士，主要研究方向：射頻識別。

沈岳(1965-)，男，教授，主要研究方向：物聯網。

匡迎春(1971-)，女，博士，教授，主要研究方向：單片機。