李曉琴

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

?

一種基于ID預(yù)測(cè)和二叉搜索的RFID標(biāo)簽防碰撞算法

李曉琴

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

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

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

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

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

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

1相關(guān)工作

1.1ALOHA類算法

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

圖1　ALOHA算法思想

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

S=G·P=Ge-2G.

(1)

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

S=G·P=Ge-G.

(2)

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

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

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

圖2　二進(jìn)制搜索算法思想

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

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

2算法設(shè)計(jì)

2.1標(biāo)簽編碼設(shè)計(jì)

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

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

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

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

2.2通信命令設(shè)計(jì)

2.2.1識(shí)讀器命令設(shè)計(jì)

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

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

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

read(ID)讀取命令，讀取成功識(shí)別的標(biāo)簽中存儲(chǔ)的信息。

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

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

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

2.2.2標(biāo)簽狀態(tài)設(shè)計(jì)

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

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

operative：表面當(dāng)前標(biāo)簽在識(shí)別過(guò)程中發(fā)生碰撞，正在識(shí)別過(guò)程中。

2.3算法工作流程設(shè)計(jì)

IDPBS算法偽代碼描述如下：

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

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

3實(shí)驗(yàn)結(jié)果與分析

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

表1　待識(shí)別標(biāo)簽

標(biāo)簽識(shí)別流程如下：

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

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

3) 識(shí)讀器廣播消息，要求標(biāo)記區(qū)為“001”的標(biāo)簽響應(yīng)，即tag8。tag8被識(shí)別。

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

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

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

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

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

4結(jié)論

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

參考文獻(xiàn)

[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)射頻識(shí)別(RFID)核心技術(shù)詳解[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]岳克強(qiáng).RFID多標(biāo)簽防碰撞算法研究及應(yīng)用[D].杭州：浙江大學(xué),2014.

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

[6]史長(zhǎng)瓊，肖瑞強(qiáng)，吳丹.改進(jìn)的動(dòng)態(tài)幀時(shí)隙ALOHA防碰撞算法[J].計(jì)算機(jī)工程與設(shè)計(jì),2014,35(6):1897-1900.

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

[8]李聰，谷曉忱，李建成，等.一種對(duì)時(shí)鐘偏差不敏感的無(wú)源RFID標(biāo)簽編解碼算法[J].國(guó)防科技大學(xué)學(xué)報(bào),2013,35(3):126-131.

收稿日期：2015-12-11

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

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

中圖分類號(hào)：TP391，TN92

文獻(xiàn)標(biāo)識(shí)碼：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