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

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

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

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

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

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

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

0 引言

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

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

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

1 二進制搜索算法

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

1.1 基本二進制搜索算法

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

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

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

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

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

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

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

1.2 后退式二進制搜索算法

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

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

1.3 動態(tài)二進制搜索算法

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

表2 動態(tài)二進制搜索算法具體識別過程

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

2 改進的二進制搜索算法

2.1 算法基本思想

已有的幾種二進制搜索算法都是按照某種規(guī)則自頂向下構(gòu)建識別樹，中間節(jié)點的構(gòu)建和訪問識別樹的子葉以及如何動態(tài)調(diào)整閱讀器發(fā)送的命令都是搜索過程當中非常重要的環(huán)節(jié)。本算法基于二進制算法做出了以下幾個方面的改進。

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

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

2.2 算法流程

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

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

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

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

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

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

3 仿真實驗與分析

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

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

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

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

傳輸數(shù)據(jù)的長度為:

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

系統(tǒng)的吞吐率為：

針對動態(tài)二進制搜索算法的特點，識別N個標簽的次數(shù)為:

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

傳輸數(shù)據(jù)的長度為:

系統(tǒng)的吞吐率為：

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

T3(N)=2N-1

傳輸數(shù)據(jù)的長度為:

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

系統(tǒng)的吞吐率為：

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

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

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

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

傳輸數(shù)據(jù)的長度為：

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

系統(tǒng)的吞吐率為：

以閱讀器搜索的次數(shù)和標簽傳輸?shù)男畔⒘恳约跋到y(tǒng)的吞吐率為例，對以上幾種算法對比分析。閱讀器對標簽的搜索次數(shù)對比如圖1所示。當碰撞的標簽的數(shù)量較少時，改進的二進制搜索算法優(yōu)勢并不明顯，且閱讀器發(fā)送的指令增加了標簽設(shè)計的復雜性，消耗了標簽的能量。當碰撞的標簽數(shù)量較多時，改進的二進制搜索算法能夠較大幅地減少閱讀器的搜索次數(shù)，其優(yōu)勢對比更加明顯。碰撞標簽與閱讀器之間傳輸?shù)男畔⒘繉Ρ热鐖D2所示。

圖1 四種搜索算法搜索次數(shù)對比分析

圖2 四種算法傳輸?shù)臄?shù)據(jù)總量對比分析

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

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

4 結(jié)論

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

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

[4] 吳躍前,辜大光,范振粵,等. RFID系統(tǒng)防碰撞算法比較分析及其改進算法[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-)，男，教授，主要研究方向：物聯(lián)網(wǎng)。

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