改進(jìn)的二進(jìn)制搜索防碰撞算法*

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

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

改進(jìn)的二進(jìn)制搜索防碰撞算法*

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

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

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

RFID；二進(jìn)制搜索；防碰撞算法；碰撞位

0 引言

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

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

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

1 二進(jìn)制搜索算法

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

1.1 基本二進(jìn)制搜索算法

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

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

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

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

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

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

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

1.2 后退式二進(jìn)制搜索算法

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

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

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

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

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

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

2 改進(jìn)的二進(jìn)制搜索算法

2.1 算法基本思想

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

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

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

2.2 算法流程

改進(jìn)的二進(jìn)制搜索算法流程如下：

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

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

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

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

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

3 仿真實驗與分析

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

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

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

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

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

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

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

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

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

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

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

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

T3(N)=2N-1

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

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

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

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

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

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

(3)假設(shè)L-1個標(biāo)簽碰撞位時等式成立，即T4(N)=2L-1-1+1，則增加一位標(biāo)簽碰撞位，增加的標(biāo)簽碰撞位與之前的標(biāo)簽碰撞位位置完全不同，需要增加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ù)和標(biāo)簽傳輸?shù)男畔⒘恳约跋到y(tǒng)的吞吐率為例，對以上幾種算法對比分析。閱讀器對標(biāo)簽的搜索次數(shù)對比如圖1所示。當(dāng)碰撞的標(biāo)簽的數(shù)量較少時，改進(jìn)的二進(jìn)制搜索算法優(yōu)勢并不明顯，且閱讀器發(fā)送的指令增加了標(biāo)簽設(shè)計的復(fù)雜性，消耗了標(biāo)簽的能量。當(dāng)碰撞的標(biāo)簽數(shù)量較多時，改進(jìn)的二進(jìn)制搜索算法能夠較大幅地減少閱讀器的搜索次數(shù)，其優(yōu)勢對比更加明顯。碰撞標(biāo)簽與閱讀器之間傳輸?shù)男畔⒘繉Ρ热鐖D2所示。

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

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

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

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

4 結(jié)論

本文針對RFID系統(tǒng)中已有的二進(jìn)制搜索算法的冗余度高、傳輸數(shù)據(jù)量大、識別效率低的問題，提出了一種改進(jìn)的二進(jìn)制搜索算法。該算法只處理碰撞位的信息，在一定程度上減少了閱讀器發(fā)送的信息量，從而提高了標(biāo)簽的識別效率。通過MATLAB模擬仿真表明，改進(jìn)的二進(jìn)制搜索算法與其他二進(jìn)制搜索算法相比，該算法在標(biāo)簽的識別次數(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]. 計算機(jī)應(yīng)用,2012,32(1):288-291.

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

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

[6] 李飛,曹敦,傅明. 一種BIBD編碼的RFID防碰撞算法的改進(jìn)[J]. 計算機(jī)應(yīng)用與軟件,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ìn)的二進(jìn)制搜索防碰撞算法[J].微型機(jī)與應(yīng)用，2017,36(16)：23-25,29.

2017-02-28)

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

沈岳(1965-)，男，教授，主要研究方向：物聯(lián)網(wǎng)。

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