基于分組策略的RFID自適應(yīng)防碰撞算法的研究

李 云，謝 剛，鄭 重，楊江波

(太原理工大學(xué)信息工程學(xué)院，山西 太原 030024)

責(zé)任編輯:薛 京

射頻識(shí)別(Radio Frequency Identification，RFID)系統(tǒng)運(yùn)行時(shí)，當(dāng)讀寫器作用區(qū)域內(nèi)多個(gè)標(biāo)簽同時(shí)向讀寫器發(fā)送信號(hào)，會(huì)產(chǎn)生信號(hào)相互干擾的現(xiàn)象，這種現(xiàn)象稱為標(biāo)簽的碰撞，而解決此類碰撞的算法則稱為標(biāo)簽防碰撞算法。目前，現(xiàn)有的時(shí)分多路(TDMA)標(biāo)簽防碰撞算法可以分為基于ALOHA機(jī)制的隨機(jī)性算法和基于二進(jìn)制樹的確定性算法兩種類型［1］。基于ALOHA機(jī)制的算法操作簡單、易于實(shí)現(xiàn)，但當(dāng)標(biāo)簽數(shù)目較大時(shí)，部分標(biāo)簽可能會(huì)在相當(dāng)長的一段時(shí)間內(nèi)得不到識(shí)別，出現(xiàn)“餓死”現(xiàn)象［2］。目前研究較多的是幀時(shí)隙ALOHA算法［3-4］，主要是通過估計(jì)標(biāo)簽數(shù)量來確定幀長從而減少碰撞，但仍未解決標(biāo)簽“餓死”問題。基于二進(jìn)制樹的算法［5-9］識(shí)別率高，避免了標(biāo)簽“餓死”現(xiàn)象，適應(yīng)標(biāo)簽數(shù)目較大的場(chǎng)合，但通信量大，且有相當(dāng)長的延時(shí)。文獻(xiàn)［5-6］通過后退策略降低了通信量，但是碰撞時(shí)隙較多，仍有相當(dāng)長的延時(shí)。文獻(xiàn)［7］是通過啟發(fā)式函數(shù)h(x)的大小來估計(jì)節(jié)點(diǎn)內(nèi)待識(shí)別的標(biāo)簽數(shù)量，由于每次搜索都要計(jì)算h(x)，雖然減少了搜索次數(shù)，但通信量仍然很大。文獻(xiàn)［8］規(guī)定只有1位碰撞位時(shí)直接識(shí)別2個(gè)標(biāo)簽，文獻(xiàn)［9］規(guī)定只有2位碰撞位時(shí)直接識(shí)別，兩種改進(jìn)都減少了搜索次數(shù)，但當(dāng)標(biāo)簽較少時(shí)出現(xiàn)符合規(guī)定的概率較小。

本文針對(duì)以上算法存在的不足，提出了一種新的基于分組策略的RFID自適應(yīng)防碰撞算法(AGS)，該算法在二叉樹搜索算法的基礎(chǔ)上引入分組策略、后退策略和自適應(yīng)地選擇四叉樹搜索策略，大幅度地降低了讀寫器的搜索次數(shù)，減少了標(biāo)簽與讀寫器間的通信量與延時(shí)，提高了識(shí)別效率。

1 AGS算法原理

根據(jù)標(biāo)簽內(nèi)部的計(jì)數(shù)器R的值將標(biāo)簽分為兩組:A組(R=0)標(biāo)簽ID中“1”的個(gè)數(shù)為偶數(shù);B組(R=1)標(biāo)簽ID中“1”的個(gè)數(shù)為奇數(shù)。讀寫器首先對(duì)A組標(biāo)簽發(fā)出搜索命令，符合條件的標(biāo)簽將自身的ID值傳送給讀寫器，讀寫器根據(jù)曼切斯特解碼檢測(cè)本次響應(yīng)標(biāo)簽的碰撞情況。若無碰撞，直接識(shí)別，讀寫器再對(duì)B組標(biāo)簽發(fā)出搜索命令;若有碰撞，則根據(jù)連續(xù)碰撞位的信息將該組標(biāo)簽分為不同的子集，即如果檢測(cè)到有3位連續(xù)的比特位發(fā)生碰撞，則立刻停止對(duì)ID進(jìn)行編解碼，將該組標(biāo)簽分為“00”，“01”，“10”，“11”共4 個(gè)子集，并將已識(shí)別的比特位壓棧;如果檢測(cè)到3個(gè)非連續(xù)的比特位發(fā)生碰撞，則根據(jù)最高碰撞位的位置將該組標(biāo)簽分為“0”，“1”共2個(gè)子集。讀寫器繼續(xù)發(fā)出命令，直到標(biāo)簽信息不再發(fā)生碰撞，標(biāo)簽被成功識(shí)別，讀寫器采用后退策略，繼續(xù)發(fā)出前一條搜索命令，直到該組標(biāo)簽全部識(shí)別成功。具體算法流程如圖1所示。

圖1 AGS算法流程圖

2 算法協(xié)議

為便于實(shí)現(xiàn)和描述該算法，提出如下算法協(xié)議對(duì)算法進(jìn)行約束。

1)請(qǐng)求命令Request。命令有3種形式:Request(null，p)，Request(x，q)和 Request(x，y，q)。

Request(null，p)中p為0或1，讀寫器第一次搜索時(shí)發(fā)送，要求讀寫器作用區(qū)域內(nèi)所有計(jì)數(shù)器R的值與p的值相同的標(biāo)簽響應(yīng);Request(x，q)中x為0或1，q為上一次搜索過程檢測(cè)到的最高碰撞位;Request(x，y，q)中x，y分別為0或1，q為最高碰撞位，當(dāng)上一次搜索過程檢測(cè)到連續(xù)的3位碰撞位時(shí)使用此命令。

2)如果讀寫器檢測(cè)到只有2個(gè)比特位發(fā)生碰撞時(shí)，讀寫器直接識(shí)別這2個(gè)標(biāo)簽。

3)當(dāng)讀寫器檢測(cè)到有3個(gè)比特位發(fā)生碰撞時(shí)，則立刻停止對(duì)ID進(jìn)行編解碼。

4)根據(jù)檢測(cè)最高碰撞位連續(xù)個(gè)數(shù)自適應(yīng)地確定搜索樹的分叉數(shù)，即在某分支下檢測(cè)出最高碰撞位連續(xù)的個(gè)數(shù)大于等于3時(shí)，則選擇四叉樹搜索，否則選擇二叉樹搜索。

3 算法步驟

假設(shè)讀寫器作用區(qū)域內(nèi)有8個(gè)標(biāo)簽，各個(gè)標(biāo)簽的編碼及其識(shí)別過程如圖2所示。

圖2 算法的搜索識(shí)別過程

1)讀寫器發(fā)送命令Request(null，0)，讀寫器作用區(qū)域內(nèi)計(jì)數(shù)器R=0的所有標(biāo)簽均作出響應(yīng)。本例中，D7D6D5均發(fā)生碰撞，則q=7。

2)讀寫器發(fā)送命令Request(0，0，7)，即選擇D7D6為“00”的待命態(tài)標(biāo)簽，只有Tag4滿足條件，不存在沖突問題而直接識(shí)別。

3) 讀寫器發(fā)送命令 Request(0，1，7)，Tag3，Tag5 滿足條件并作出響應(yīng)。此時(shí)，讀寫器解碼得:1000??，只有2位碰撞位，由算法協(xié)議2)可知:讀寫器不必發(fā)送請(qǐng)求命令而直接識(shí)別 Tag3，Tag5。

4) 讀寫器發(fā)送命令 Request(1，0，7)，Tag1，Tag6，Tag7滿足條件并作出響應(yīng)。此時(shí)讀寫器解碼得:1?0??，最高碰撞位為D4。

5) 讀寫器發(fā)送命令Request(0，4)，Tag6，Tag7 滿足條件，并作出響應(yīng)。此時(shí)，讀寫器解碼得:000??，只有2位碰撞位，從而直接識(shí)別Tag6，Tag7。

6)讀寫器發(fā)送命令Request(1，4)，此時(shí)只有Tag1滿足條件，不存在沖突問題直接識(shí)別。

7)讀寫器發(fā)送命令Request(1，1，7)，此時(shí)只有Tag2滿足條件，直接識(shí)別。

8)讀寫器發(fā)送命令Request(null，1)，讀寫器作用區(qū)域內(nèi)計(jì)數(shù)器R=1的所有標(biāo)簽均作出響應(yīng)，此時(shí)只有Tag8滿足條件，不存在沖突問題而直接識(shí)別。

4 算法仿真分析

設(shè)讀寫器作用區(qū)域內(nèi)存在N個(gè)標(biāo)簽，標(biāo)簽ID為n位，由標(biāo)簽計(jì)數(shù)器R的值將N個(gè)標(biāo)簽分為兩組:R值為0的標(biāo)簽個(gè)數(shù)為N1個(gè);R值為1的標(biāo)簽個(gè)數(shù)為N2個(gè)。讀寫器識(shí)別兩組標(biāo)簽的過程中，檢測(cè)到只有2個(gè)碰撞位的情況分別為M1，M2次，使用四叉樹時(shí)出現(xiàn)如圖3a的情況分別為 P1，P2次，出現(xiàn)如圖3c的情況分別為Q1，Q2次。

圖3 四叉樹代替二叉樹可能出現(xiàn)的3種情況

策略1:后退策略

基于后退策略的二進(jìn)制搜索算法識(shí)別N個(gè)標(biāo)簽所需搜索次數(shù)為

策略2:自適應(yīng)策略

出現(xiàn)連續(xù)3位碰撞位時(shí)，采用四叉樹代替二叉樹有如圖3所示的3種情況。假如讀寫器作用區(qū)域內(nèi)存在00011101和00000001兩個(gè)標(biāo)簽時(shí)，產(chǎn)生如圖3a所示的情況，此時(shí)采用四叉樹比二叉樹增加了2次搜索;假如讀寫器作用區(qū)域內(nèi)存在00011101，00000001和00001001這3個(gè)標(biāo)簽時(shí)，產(chǎn)生如圖3b所示左邊的情況，此時(shí)采用四叉樹的搜索次數(shù)與二叉樹的搜索次數(shù)相同;假如讀寫器作用區(qū)域內(nèi)存在00011101，000110001，00000001和00001101這4個(gè)標(biāo)簽時(shí)，產(chǎn)生如圖3c所示的情況，此時(shí)采用四叉樹，比二叉樹減少了2次搜索。

策略3:分組策略

由算法協(xié)議2)可知，在識(shí)別A組標(biāo)簽的過程中檢測(cè)到M1次只有2個(gè)比特位發(fā)生碰撞時(shí)，采用本算法相當(dāng)于在二叉樹上減少了M1個(gè)葉子節(jié)點(diǎn)，即搜索次數(shù)減少2×M1次。

本算法將以上3種策略結(jié)合在一起，讀寫器識(shí)別計(jì)數(shù)器R=0的所有標(biāo)簽需要搜索次數(shù)為

同樣，讀寫器識(shí)別計(jì)數(shù)器R=1的所有標(biāo)簽需要搜索次數(shù)為

因此，采用本算法讀寫器識(shí)別其作用區(qū)域內(nèi)的所有標(biāo)簽所需的搜索次數(shù)為

本算法的吞吐率可表示為

在MATLAB仿真平臺(tái)上對(duì)本算法、四叉樹搜索算法、基于后退策略的二進(jìn)制搜索算法、動(dòng)態(tài)調(diào)整二進(jìn)制搜索算法［8］和PDBS［9］進(jìn)行仿真。目前 EPC 編碼體系中使用較多的是EPC-64。在仿真實(shí)驗(yàn)中編碼位數(shù)n由標(biāo)簽數(shù)量決定。現(xiàn)取n=8，n=16兩種情況分別對(duì)讀寫器發(fā)出的搜索次數(shù)和系統(tǒng)的吞吐率進(jìn)行仿真，結(jié)果如圖4～圖7所示。

1)由圖4和圖5可看出:當(dāng)標(biāo)簽數(shù)目大于100時(shí)，與其余4種算法相比，本文算法的搜索次數(shù)明顯減少，吞吐率增幅很大。

圖7 n=16時(shí)吞吐率比較

2)由圖6和圖7可看出:當(dāng)標(biāo)簽位數(shù)和標(biāo)簽數(shù)目一定時(shí)，本文算法和PDBS算法明顯優(yōu)于四叉樹搜索算法、基于后退策略的二進(jìn)制搜索算法和動(dòng)態(tài)調(diào)整二進(jìn)制搜索算法;隨著標(biāo)簽數(shù)目的增加，本文算法的吞吐率較PDBS算法及其他算法越來越高。

3)由圖4～圖7可看出:當(dāng)標(biāo)簽位數(shù)一定時(shí)，隨著標(biāo)簽數(shù)目的增加，將后退策略、分組策略和自適應(yīng)策略相結(jié)合的算法所得到的系統(tǒng)吞吐率明顯高于單純地選用四叉樹策略、后退策略或分組策略所得到的系統(tǒng)吞吐率。即當(dāng)標(biāo)簽位數(shù)一定時(shí)，隨著讀寫器作用區(qū)域內(nèi)的標(biāo)簽數(shù)量N的增大，檢測(cè)出只有2位比特位發(fā)生碰撞的概率越大，發(fā)生圖3c的概率也將遠(yuǎn)大于發(fā)生圖3a的概率，即算法的吞吐率越大。

5 結(jié)束語

本文提出了一種基于分組策略的RFID自適應(yīng)防碰撞算法，該算法在二進(jìn)制搜索算法的基礎(chǔ)上加入了分組策略、后退策略和自適應(yīng)策略。分組策略和自適應(yīng)策略的引入，有效地降低了標(biāo)簽間的碰撞次數(shù)，大幅地提高了讀寫器的吞吐率，再加上后退策略，又更進(jìn)一步地減少了讀寫器與標(biāo)簽間的通信量。通過對(duì)新算法的性能分析及對(duì)仿真結(jié)果的比較證明，新算法更高效地解決了標(biāo)簽的碰撞問題，具有良好的應(yīng)用前景。

［1］劉云浩.物聯(lián)網(wǎng)導(dǎo)論［M］.北京:科學(xué)出版社，2011:33-37.

［2］王春華，許靜，彭關(guān)超，等.改進(jìn)的RFID標(biāo)簽識(shí)別防沖突算法［J］.計(jì)算機(jī)工程與應(yīng)用，2011，47(31):104-107.

［3］FINKENZELLER K.RFID handbook fundamentals and applications in contactless smart cards and identification［M］.2nd ed.West Sussex:John Wiley ＆ Sons Ltd.，2003.

［4］郭志濤，程林林，周艷聰，等.動(dòng)態(tài)幀時(shí)隙 ALOHA算法的改進(jìn)［J］.計(jì)算機(jī)應(yīng)用研究，2012，29(3):907-909.

［5］RYU J，LEE H，SEOK Y，et al.A hybrid query tree protocol for tag collision arbitration in RFID systems［C］//Proc.IEEE International Conference on Communications.［S.l.］:IEEE Press，2007:5981-5986.

［6］CHEN Y H，HORNG S J，RUN R S，et al.A novel anti-collision algorithm in RFID systems for identifying passive tags［J］.IEEE Trans.Industrial Information，2010，6(1):105-121.

［7］丁治國，朱學(xué)永，雷迎科，等.基于啟發(fā)式函數(shù)的多叉樹防碰撞算法［J］. 計(jì)算機(jī)應(yīng)用，2012，32(3):665-668.

［8］謝振華，賴聲禮，陳鵬.RFID技術(shù)和防碰撞算法［J］.計(jì)算機(jī)工程與應(yīng)用，2007，43(6):223-225.

［9］伍繼雄，江岸，黃生葉，等.RFID系統(tǒng)中二叉樹防碰撞算法性能的提升［J］.湖南大學(xué)學(xué)報(bào):自然科學(xué)版，2010，39(12):82-86.