李曉琴

(山西省電子工業(yè)科學研究所，山西 太原 030006)

?

一種基于ID預測和二叉搜索的RFID標簽防碰撞算法

李曉琴

(山西省電子工業(yè)科學研究所，山西 太原 030006)

摘要：標簽防碰撞問題是RFID系統(tǒng)的重要研究課題之一，本文在研究經(jīng)典防碰撞算法的基礎上，提出一種基于ID預測和二叉搜索的RFID防碰撞算法IDPBS，使用自定義編碼方式，減少標簽之間的干擾，結合二叉搜索機制，利用堆棧尋找碰撞位并完成標簽識別。數(shù)據(jù)分析及實驗結果表明，本文算法可以正確有效地完成RFID標簽的識別。

關鍵詞：物聯(lián)網(wǎng)；RFID；防碰撞；二叉搜索

射頻識別(RFID)是一種基于無線通信的非接觸式標簽識別技術，目前已被廣泛用于識別、跟蹤和管理生物體或非生物體[1]。RFID與現(xiàn)有的條形碼識別技術類似，但功能更加豐富，例如RFID標簽具有更大的存儲容量、更遠的識別半徑以及多標簽識別能力。RFID系統(tǒng)一般包括信息載體(射頻標簽)、信息獲取裝置(射頻識讀器)、空中接口和邊緣服務器等部分[2]。標簽的能量來源包括有源、無源和半有源三種，其中，無源標簽的能量全部來自于射頻識讀器發(fā)射的電磁波，因此，無源標簽成本低、壽命長，應用最為廣泛[3]。

一般地，射頻識讀器通過射頻信號廣播數(shù)據(jù)收集請求，處于識讀區(qū)域內(nèi)的射頻標簽收到請求后通過無線電波應答，返回識讀器請求的數(shù)據(jù)。由于識讀器和標簽之間的無線信道是共享的，當多個標簽同時向識讀器發(fā)送應答數(shù)據(jù)時，就會導致信道擁塞，也就是多標簽碰撞[4]。多標簽碰撞將會迅速降低網(wǎng)絡吞吐量，造成帶寬浪費和能量消耗，并影響網(wǎng)絡的效率和可靠性。當前，已有一些學者對RFID標簽碰撞問題進行了研究，并設計了一些行之有效的防碰撞協(xié)議，這些協(xié)議的共同目標是減少閱讀器識別范圍內(nèi)全部標簽所需的時間，比較典型的算法有基于幀時隙的ALOHA類方法和基于搜索樹的二叉搜索類方法[5]。ALOHA類算法中，標簽以隨機方式響應，計算復雜度較低，實施成本低，但是在網(wǎng)絡規(guī)模較大時容易產(chǎn)生“Tag Starvation”現(xiàn)象，即部分標簽長時間不能被識別；而二叉搜索類算法采用逐位匹配的方式，如果運行足夠長的時間，可以識別全部的標簽，但是在標簽數(shù)量較大時，算法性能會大大降低。同時，大部分防碰撞算法沒有引入數(shù)據(jù)傳輸校驗機制，無法確定數(shù)據(jù)傳輸?shù)臏蚀_性。

本文在結合ALOHA類算法和二叉搜索類算法的優(yōu)點的基礎上，提出了一種基于ID預測和二叉搜索的IDPBS算法，首先在標簽中設計標記區(qū)，用于標簽預測和數(shù)據(jù)校驗，然后在標簽預測的基礎上，采用二叉搜索算法對標簽進行識別。實驗結果表明，對于存儲能力、計算能力均受限的無源RFID標簽，IDPBS可以有效減少識讀器的查詢次數(shù)和標簽回傳的數(shù)據(jù)量，具有更優(yōu)秀的性能。

1相關工作

1.1ALOHA類算法

ALOHA類算法是一類隨機接入方法，當標簽處于識別區(qū)域內(nèi)時，就主動向識讀器發(fā)送數(shù)據(jù)[6]。算法將傳輸時間分成多個離散的時間片，稱為時隙，時隙長不小于一個幀(標簽ID)傳輸所需時長。當某時隙中只有一個標簽發(fā)送數(shù)據(jù)時，該標簽就被成功識別。因此，每個時隙可能出現(xiàn)三種情況，即識別成功、標簽碰撞和時隙空閑，如圖1所示。

圖1　ALOHA算法思想

假設網(wǎng)絡吞吐量定義為一幀內(nèi)成功發(fā)送的平均標簽數(shù)。由于ALOHA算法在數(shù)學原理上是一個多重伯努利試驗，假設一個標簽發(fā)送成功的概率為P，則在未進行分片時，ALOHA算法在穩(wěn)定狀態(tài)下有如下公式：

S=G·P=Ge-2G.

(1)

時隙ALOHA算法規(guī)定標簽只能選擇時隙的分界處發(fā)送數(shù)據(jù)，這樣數(shù)據(jù)只可能成功發(fā)送或發(fā)生碰撞，時隙ALOHA算法在穩(wěn)定狀態(tài)下：

S=G·P=Ge-G.

(2)

可以看出，相比純ALOHA算法，時隙ALOHA算法系統(tǒng)吞吐量增大了一倍。在時隙算法的基礎上，有人提出了一種基于Gen-2協(xié)議的SR算法，為每個標簽設計一個隨機數(shù)生成器和一個時隙計數(shù)器。SR算法可以在一個識讀周期內(nèi)，使部分未識別的標簽調(diào)整數(shù)據(jù)發(fā)送時機，再次進行數(shù)據(jù)發(fā)送，增大標簽被識別的機會，提高識別效率[7]。在SR算法中，算法參數(shù)(Q值)可以進行動態(tài)調(diào)整，避免時隙范圍太大或太小引起的空閑時隙太多或者碰撞概率過大的問題。

1.2二進制搜索類算法

根據(jù)ISO/IEC 14443標準，RFID系統(tǒng)采用二進制搜索類算法時，應使用Manchester編碼規(guī)則，理想情況下識讀器可以同時獲得全部標簽返回的數(shù)據(jù)，并得到發(fā)生碰撞的位置的準確信息[8]。算法將處于沖突的標簽劃分為多個子集，然后對其中一個子集進行查詢，如果沒有產(chǎn)生沖突，那么可以正確識別一個標簽，如果產(chǎn)生沖突，那么就將當前集合再劃分為多個子集進行查詢，直至正確識別一個標簽。如圖2所示。

圖2　二進制搜索算法思想

在基本的二進制搜索防碰撞算法中，通常識讀器首先廣播一個與標簽ID等長的查詢序列QS，標簽在收到廣播信息后，將自身ID與QS進行比對，如果不發(fā)生沖突，則有一個標簽被成功識別，如果發(fā)生沖突，則根據(jù)沖突信號將QS中對應最高碰撞位的數(shù)值置0，再次進行查詢，重復此操作直至成功識別ID最小的標簽并使其進入靜默狀態(tài)，不再響應識讀器的廣播信息。重復以上步驟，直至所有標簽都被成功識別。

以基本的二進制搜索算法為基礎，有學者提出了回退二進制搜索算法、多叉樹混合搜索算法。由于二進制搜索類算法的計算過程與標簽ID位數(shù)相關，因此計算量會隨著ID位數(shù)的增長急劇上升，導致算法性能大幅下降，當ID為數(shù)過長時，二叉搜索算法無法保證在可接受的時間內(nèi)識別所有的標簽。

2算法設計

2.1標簽編碼設計

與條形碼編碼規(guī)則類似，RFID標簽ID為等長且唯一的“0”“1”序列，是RFID標簽的唯一標識。在傳統(tǒng)的ID編碼方式基礎上，參考IPA算法編碼方式，將ID分為標記區(qū)Tv與數(shù)據(jù)區(qū)Dv，其中標記區(qū)記錄的是數(shù)據(jù)區(qū)中“1”的個數(shù)。

10010101010標記區(qū)數(shù)據(jù)區(qū)

在這種編碼方式下，識讀器需要記錄的信息包括當前標簽的ID和已識別的“1”的個數(shù)N1T。

如果Tv-N1T=1，說明標簽T只有一個1未被識別，這個1可能處在發(fā)生沖突的任何位置，除了這個1所在的位置，其他位置均為0。

2.2通信命令設計

2.2.1識讀器命令設計

activate(null/prefix)激活命令，如果參數(shù)為null，激活當前查詢范圍內(nèi)的所有標簽；如果參數(shù)為prefix，激活當前查詢范圍內(nèi)的與此前綴匹配的所有標簽。

require(Tv,0)請求命令，收到命令的所有標簽響應，返回1，表明當前查詢范圍內(nèi)有與此前綴匹配的標簽。

require(Tv,prefix)請求命令，使處于active狀態(tài)的與prefix匹配的標簽響應，向識讀器發(fā)送數(shù)據(jù)位信息。

read(ID)讀取命令，讀取成功識別的標簽中存儲的信息。

slience(prefix)休眠命令，使當前查詢范圍內(nèi)的與此前綴匹配的所有標簽進入休眠狀態(tài)，這些標簽在下次收到激活命令時，才會進入激活狀態(tài)并響應識讀器的請求。

stackpush(posi,1)壓棧命令，將當前發(fā)生碰撞的最高位壓入碰撞棧中。

stackpop()出棧命令，將碰撞棧的當前最高位彈出棧。

2.2.2標簽狀態(tài)設計

active：表明當前標簽處于激活狀態(tài)，等待響應識讀器發(fā)布的指令。

sleep：表明當前標簽處于休眠狀態(tài)，本輪不再響應識讀器發(fā)布的指令，等待下一次激活后才對識讀器指令進行相應。

operative：表面當前標簽在識別過程中發(fā)生碰撞，正在識別過程中。

2.3算法工作流程設計

IDPBS算法偽代碼描述如下：

AlgorithmIDPBS(){//判斷當前區(qū)域是否有待識別標簽1activate(null);2if(noresponse)3end4 elsefor5(Tv=min(Tv);Tv

在IDPBS算法中，識讀器首先廣播激活命令activate(null)，區(qū)域內(nèi)全部標簽在收到此命令后，將自身的狀態(tài)置為active。識讀器廣播標記區(qū)所有可能的情況，如果標簽的標記區(qū)與識讀器詢問的相同，則向識讀器發(fā)回簡短的確認指令，表明當前區(qū)域有標記區(qū)為當前詢問值的標簽。然后對于每個識別出的Tv值，向?qū)臉撕灠l(fā)送read(ID)命令進行識別并校驗，識別過程可分為三種情況：1) 無碰撞現(xiàn)象，標簽被直接識別；2) 滿足2.1條件，標簽被快速識別；3) 其他標簽，采用二叉搜索算法進行識別。在識別并讀取標簽ID的過程中，識讀器根據(jù)標記區(qū)校驗數(shù)據(jù)，如果識別正確，發(fā)送slience(prefix)命令使其進入sleep狀態(tài)，如果檢測到ID識別錯誤，則將其丟棄。最后，IDPBS算法識別之前識別錯誤的標簽。

3實驗結果與分析

為驗證本文算法的正確性和有效性，隨機選取一組標簽進行測試。標簽采用Manchester編碼。假設標簽均處于識讀器的識別范圍內(nèi)，在數(shù)據(jù)傳輸過程中互不干擾。待識別標簽如表1所示。

表1　待識別標簽

標簽識別流程如下：

1) 識讀器廣播命令，8個標簽均嘗試發(fā)送標記區(qū)位數(shù)信息，表明當前區(qū)域有待識別標簽并說明Tv區(qū)域大小。

2) 識讀器廣播輪詢所有可能的Tv值，標簽收到廣播后與自身的標記區(qū)比對，如果匹配則向識讀器返回確認信息。識讀器將有確認信息的標記值保存，即001，010，100，101。

3) 識讀器廣播消息，要求標記區(qū)為“001”的標簽響應，即tag8。tag8被識別。

4) 識讀器廣播消息，要求標記區(qū)為“010”的標簽響應，即tag6和tag7響應。識讀器收到的標簽信息為“1X00000X”，對于tag6和tag7，識讀器計算可得Tv-N1T=1，tag6的沖突位中，只有一處可能為1，其他沖突位為0，識讀器更改查詢參數(shù)，識別tag6，并以同樣的方式識別tag7。

5) 識讀器廣播消息，要求標記區(qū)為“100”的標簽響應，即tag4和tag5響應。識讀器收到的標簽信息為“XXXX1010”，將沖突位信息從低位到高位依次壓入碰撞棧。識讀器修改require參數(shù)，執(zhí)行require(100,0)，此時只有tag4響應，tag4被識別。之后執(zhí)行出棧命令，產(chǎn)生新的請求命令require(100,0)，此時只有tag5響應，tag5被識別。

6) 識讀器廣播消息，要求標記區(qū)為“101”的標簽響應，即tag1,tag2,tag3響應，識讀器收到的標簽信息為“1XX101XX”，將沖突位信息從低位到高位依次壓入碰撞棧，修改require參數(shù)，執(zhí)行require(101,11)，此時只有tag2響應，tag2被識別。之后執(zhí)行出棧命令，產(chǎn)生新的請求命令，發(fā)生碰撞，將沖突為信息從低位到高位依次壓入碰撞棧，發(fā)送新的請求命令require(101,110010)此時只有tag3響應，tag3被識別。之后執(zhí)行出棧命令，識別tag1。

識讀器在讀取標簽ID后，根據(jù)標記區(qū)的信息校驗ID是否識別正確，如果校驗錯誤，則丟棄該標簽的ID信息，重新識別。

可以看出，IDPBS算法根據(jù)標簽標記區(qū)將標簽分為不同的分組，在組內(nèi)使用二叉搜素算法識別，在識別后對標簽ID進行校驗，丟棄錯誤數(shù)據(jù)，保證了標簽識別的效率和準確性。

4結論

本文針對RFID標簽碰撞問題進行了研究，在分析經(jīng)典防碰撞算法的基礎上，提出了一種基于ID預測和二叉搜索的RFID防碰撞算法IDPBS，在減小標簽識別沖突域的基礎上還增加了數(shù)據(jù)校驗功能，試驗結果表明，IDPBS算法能夠正確有效地識別區(qū)域內(nèi)全部RFID標簽。

參考文獻

[1]Namboodiri V,Desilva M,Deegala K,et al.An Extensive Study of Slotted Aloha-based RFID Anti-collision Protocols[J].Computer Communications,2012,35(16):1955-1966.

[2]黃玉蘭.物聯(lián)網(wǎng)射頻識別(RFID)核心技術詳解[M].北京：人民郵電出版社, 2010.

[3]Shahzad M,Liu A X.Probabilistic Optimal Tree Hopping for RFID Identification[J].Networking IEEE/ACM Transactions on,2015,23(1):796-809.

[4]岳克強.RFID多標簽防碰撞算法研究及應用[D].杭州：浙江大學,2014.

[5]潘昊，陳蒙.物聯(lián)網(wǎng)中無線射頻識別讀寫器系統(tǒng)防碰撞算法優(yōu)化[J].計算機應用,2015,35(1):23-26.

[6]史長瓊，肖瑞強，吳丹.改進的動態(tài)幀時隙ALOHA防碰撞算法[J].計算機工程與設計,2014,35(6):1897-1900.

[7]孫文勝，劉先寶.RFID系統(tǒng)標簽防碰撞的研究與改進[J].計算機工程與應用,2012(16):103-106.

[8]李聰，谷曉忱，李建成，等.一種對時鐘偏差不敏感的無源RFID標簽編解碼算法[J].國防科技大學學報,2013,35(3):126-131.

收稿日期：2015-12-11

作者簡介：李曉琴(1975- )，女，山西沁源人，助理工程師，主要從事無線電技術工作。

文章編號：1674- 4578(2016)02- 0017- 03

中圖分類號：TP391，TN92

文獻標識碼：A

An RFID Tag Anti-collision Algorithm Based on ID Prediction and Binary Search

Li Xiaoqin

(ShanxiProvinceElectronicIndustryScienceInstitute,TaiyuanShanxi030006,China)

Abstract:The tag anti-collision problem is an important research topic in RFID systems. This paper studies the classical anti-collision algorithm and proposes an RFID tag anti-collision algorithm IDPBS based on ID prediction and binary search. The IDPBS uses a custom encoding method to reduce the interference between tags, then uses the stack and binary search mechanism to find the collision position and completes the tag identification. The algorithm analysis and experimental results show that IDPBS can identify the RFID tags correctly and effectively.

Key words:Internet of Things; RFID; anti-collision; binary search