宋瑞玲,高仲合
SONG Ruiling,GAO Zhonghe
曲阜師范大學 計算機科學學院,山東 日照276826
College of Computer Science,Qufu Normal University,Rizhao,Shandong 276826,China
射頻識別(Radio Frequency IDentification,RFID)是一種利用射頻信號通過空間電磁耦合實現(xiàn)無接觸式的自動識別技術(shù)[1]。作為物聯(lián)網(wǎng)的最核心技術(shù)之一,在物聯(lián)網(wǎng)技術(shù)的引領(lǐng)下RFID 技術(shù)必將獲得越來越大的發(fā)展空間。目前,RFID 技術(shù)以其特有的設(shè)備屬性已被廣泛應用于軍事、交通、工業(yè)、醫(yī)學以及日常生活的各個方面。
RFID 系統(tǒng)是由電子標簽、閱讀器、數(shù)據(jù)處理子系統(tǒng)等三部分[2]組成。當多個電子標簽同時進入閱讀器的閱讀范圍內(nèi)時就會產(chǎn)生信息碰撞問題,信息碰撞使系統(tǒng)不能正常工作,導致誤讀和漏讀等現(xiàn)象,限制了RFID 的實際應用。因此,需要一種防碰撞技術(shù)來解決碰撞問題,解決碰撞的算法稱為防碰撞算法。
RFID 防碰撞算法采用的是多路存取的防碰撞方式,主要有時分多址、頻分多址、碼分多址、空分多址[3]。在RFID 系統(tǒng)中應用最多的是時分多址方式。而目前基于時分多址的防碰撞算法是基于aloha 的隨機型防碰撞算法和基于二進制樹的確定型防碰撞算法。
aloha 協(xié)議最早被用在分組無線網(wǎng)絡(luò)中實現(xiàn)隨機訪問機制?;赼loha算法主要有純aloha算法[4]、時隙aloha算法(SA)[5-6]、幀時隙aloha算法(FSA)、動態(tài)幀時隙aloha算法(Dynamic Frame Slotted Aloha,DFSA)[7]、自適應動態(tài)幀時隙,其中,DFSA 算法由于操作簡單和性能良好,很多研究都是在該算法的基礎(chǔ)上進行研究改進的?;赼loha 機制的算法操作簡單、易于實現(xiàn),但是其性能不穩(wěn)定,識別效率不高,并且標簽數(shù)量大時,部分標簽在相當長的時間內(nèi)得不到識別,會出現(xiàn)“餓死”現(xiàn)象。
基于二進制樹的算法識別效率高,避免標簽“餓死”現(xiàn)象,但通信量大,且有相當長的時延?;诙M制樹[8-9]的改進算法有二進制搜索(BS)算法、動態(tài)二進制搜索(DBS)算法、后退式二進制(BBS)算法[10]、跳躍式動態(tài)二進制搜索(JDBS)算法。DBS 是在BS 算法基礎(chǔ)上改進的,它避免了標簽和閱讀器之間的冗余傳輸,但搜索次數(shù)依然很多。BBS 相對于BS 算法搜索次數(shù)有所減少,但閱讀器和標簽之間存在大量的冗余傳輸。JDBS是由BBS 和DBS 改進的,不但搜索次數(shù)減少,而且避免了標簽和閱讀器之間的冗余傳輸,但是當大量標簽被識別時,系統(tǒng)數(shù)據(jù)傳輸量很大,性能仍需進一步改進。動態(tài)調(diào)整二進制樹形搜素算法基于一位沖突直接識別,當只探測到一位碰撞時,可直接識別出兩個標簽[11]。相比JDBS 進一步減少了搜索次數(shù),但是當標簽數(shù)量大,且標簽ID 號較長時,出現(xiàn)一位碰撞概率相對較低,搜索次數(shù)減少不明顯。文獻[12]提出的一種算法是在動態(tài)調(diào)整算法基礎(chǔ)上改進的,該算法通過引入分組策略,當只有兩位碰撞位時即可直接識別,當標簽較多時,搜索次數(shù)減少比較明顯。本文結(jié)合以上各種算法的優(yōu)點提出一種具體的改進算法。
(1)算法是基于二進制樹搜索算法提出的,要求閱讀器能夠準確地識別出數(shù)據(jù)的碰撞位置,這里采用曼徹斯特編碼,該編碼約定邏輯‘1’對應信號含下降沿跳變,邏輯‘0’對應信號含上升沿跳變,若無狀態(tài)跳變,視為錯誤被識別。當兩個或多個標簽同時返回的某一數(shù)位有不同的值,則接收到的上升沿和下降沿相互抵消,以致出現(xiàn)“沒有變化”或變化被明顯消弱的狀態(tài),閱讀器由此可判斷該位出現(xiàn)了碰撞。
(2)標簽內(nèi)部設(shè)置了一個計數(shù)器R 用于存儲標簽ID中所有比特位的按位異或結(jié)果,R 的取值可在標簽制造時固化寫入,R 取值為0 和1 分別代表標簽ID 中‘1’的個數(shù)是偶數(shù)和奇數(shù)。
(3)引入以下5 種命令描述算法:
①請求命令Request(nul,0),R=0組標簽響應;Request(nul,1),R=1 組標簽響應。這里還引入一個電子標簽自身的標簽選擇計數(shù)器Counter,初始值設(shè)為-1,標簽響應請求命令后變?yōu)?。
②請求命令Request(x,y):x為檢測到的最高碰撞位;y為0/1 比特位。閱讀器向作用范圍內(nèi)的電子標簽發(fā)送此命令,Counter=0 標簽序列編碼第x位為y值的標簽則響應,將自身低于x位的序列編碼傳送各閱讀器;其余未進入休眠狀態(tài)的電子標簽將自身的Counter加1。
③選擇命令Select(ID):選擇標簽。
④讀命令Read(ID):讀取標簽信息。
⑤去選擇Unselect(ID):使標簽進入休眠狀態(tài)。
(1)閱讀器發(fā)出請求命令Request(nul,0),其作用范圍內(nèi)的所有R=0 組標簽響應請求命令并將自身ID 發(fā)給閱讀器,該組標簽的標簽選擇計數(shù)器Counter=0。
(2)閱讀器對這些序列編碼解碼,如果碰撞位超過2則轉(zhuǎn)到第(3)步;若沒有碰撞或只有2 位碰撞時,閱讀器即可成功識別出標簽:
①如果不存在碰撞直接識別,轉(zhuǎn)到(4)。
②當存在兩個標簽碰撞位時,閱讀器通過奇偶校驗位即可準確地識別出兩個標簽的序列編碼,轉(zhuǎn)到(4)。
(3)記錄最高碰撞位x,最高碰撞位之前的序列壓入堆棧記錄。閱讀器向其作用范圍內(nèi)的標簽發(fā)送Request(x,0)命令,標簽選擇計數(shù)器Counter=0 的標簽序列編碼第x位為0 值響應,并將自身低于x位的序列編碼傳送給閱讀器;其余未進入休眠狀態(tài)的R=0 組的電子標簽將自身的Counter加1,轉(zhuǎn)到(2)。
(4)讀寫器對識別的標簽相繼發(fā)出Select、Read 和Unselect 命令,完成對標簽的讀寫并使之進入休眠狀態(tài)。所有未進入休眠狀態(tài)R=0 組的標簽的Counter 減1。返回上一次碰撞節(jié)點,閱讀器發(fā)出Request(x,1)的命令,標簽選擇計數(shù)器Counter=0 的標簽序列編碼第x位為1 值則響應,將自身低于x位的序列編碼傳送個閱讀器;其余未進入休眠狀態(tài)的R=0 組的電子標簽將自身的Counter加1,轉(zhuǎn)入(2)。
(5)重復以上步驟,直到對R=0 組標簽全部識別,然后以同樣的方法識別R=1 組標簽。
假設(shè)閱讀器范圍內(nèi)有6 個標簽,各標簽的編碼A:10100000 B:10000100 C:10010000 D:10001000 E:00000001 F:00001000
(1)閱讀器發(fā)出Request(nul,0)命令,其作用范圍內(nèi)A、B、C、D 響應并將自身ID 發(fā)給閱讀器,Counter(A、B、C、D)=0。
(2)閱讀器對這些序列編碼解碼為10????00,最高碰撞位5,最高碰撞位之前的‘10’序列壓入堆棧。閱讀器向作用范圍內(nèi)的標簽發(fā)送Request(5,0),這時R=0 組內(nèi)的B、C、D 響應,并把低于第5 位的序列編碼傳送給閱讀器;而R=0 組內(nèi)A 的Counter值加1。
(3)閱讀器對這些序列編碼解碼為???00,最高碰撞位4,閱讀器再次向作用范圍內(nèi)的標簽發(fā)送Request(4,0),B、D 響應,將自身低于第4 位的序列編碼傳送個閱讀器,A、C 的Counter加1。
(4)閱讀器對這些序列編碼解碼為??00,所以B、D直接被識別。
(5)閱讀器對B、D 標簽完成讀寫并使之進入休眠狀態(tài)。R=0 組內(nèi)A、C 的Counter減1。
(6)閱讀器再次向作用范圍內(nèi)的標簽發(fā)送Request(4,1),只有C 標簽響應,被識別。
(7)閱讀器對C 標簽完成讀寫并使之進入休眠狀態(tài)。R=0 組內(nèi)A 的Counter 減1。閱讀器發(fā)出Request(5,1)命令,只有A 響應,直接識別。R=0 組標簽全部被識別。
(8)閱讀器發(fā)送Request(nul,1)命令,R=1 組內(nèi)的E、F 響應,返回自身ID。
(9)閱讀器對這些序列編碼解碼為0000?00?,只有兩位碰撞所以直接被識別。
標簽的識別過程如圖1 所示。
圖1 改進算法的標簽識別過程
對算法性能進行分析時主要考慮識別出所有標簽時命令發(fā)送的總次數(shù),命令參數(shù)長度和標簽響應數(shù)據(jù)長度,等效分析識別出所有標簽時命令發(fā)送的總次數(shù),閱讀器發(fā)送數(shù)據(jù)量和標簽發(fā)送數(shù)據(jù)量。
(1)后退式二進制搜索算法
識別閱讀器范圍內(nèi)的N個標簽所需要總的搜索次數(shù)[13]:
(2)分組策略
本算法基于動態(tài)調(diào)整算法,通過設(shè)置一位奇偶校驗寄存器實現(xiàn)分組,在識別過程中檢測到只有兩位碰撞位時即能直接識別標簽,減少了搜索次數(shù)。
假設(shè)在識別過程中檢測到M次只有2 個比特位發(fā)生碰撞時,采用本算法相當于在二叉樹上減少了M個葉子節(jié)點,即搜索次數(shù)減少了2M次。
算法的搜索次數(shù)為:
特別地,當用ID 數(shù)位中的n位來表示2n個標簽時,這時候搜索次數(shù)是2n-2。
這里取ID長度是64 bit借助Matlab工具對使用分組后不同數(shù)目標簽對應搜索次數(shù)進行統(tǒng)計,如表1 所示。
表1 不同數(shù)目標簽對應搜索次數(shù)
(1)標簽發(fā)送總的通信量
JDS算法識別過程中,標簽每次發(fā)送的數(shù)據(jù)平均長度[14]:
其中L是ID 號長度。
本文算法是基于JDS算法提出的,所以標簽的通信量:
(2)閱讀器發(fā)送的數(shù)據(jù)量
本算法中發(fā)送請求命令的第一個參數(shù)是最高碰撞位信息,與編碼長度L 無關(guān),與最高碰撞位P 有關(guān),標簽發(fā)送的二進制編碼長度為[15],得出本算法傳輸?shù)亩M制數(shù)據(jù)量:
標簽閱讀器之間總的數(shù)據(jù)通信量:
在Matlab 仿真平臺上對本算法、動態(tài)調(diào)整二進制搜索算法、跳躍式動態(tài)二進制搜(JDBS)和基于后退策略的二進制搜索算法進行仿真比較。仿真實驗中編碼位數(shù)n取64。
圖2是本文算法、動態(tài)調(diào)整二進制搜索算法、跳躍式動態(tài)二進制搜索(JDBS)和基于后退策略的二進制搜索算法閱讀器進行搜索次數(shù)的比較。由圖2 可以看出本算法相對其他算法搜索次數(shù)最少,當標簽數(shù)目越多時本算法的優(yōu)勢越明顯,這是因為本算法通過分組可以減少碰撞概率,并且僅有兩位碰撞即可識別減少了搜索次數(shù)。
圖2 不同算法搜索次數(shù)比較
圖3~圖5 是本算法、動態(tài)調(diào)整二進制搜索算法、跳躍式動態(tài)二進制搜索(JDBS)和基于后退策略的二進制搜索算法標簽數(shù)據(jù)通信量、閱讀器數(shù)據(jù)通信量以及閱讀器和標簽之間傳輸總的數(shù)據(jù)量進行的仿真結(jié)果。
圖3 標簽數(shù)據(jù)通信量
圖4 閱讀器數(shù)據(jù)通信量
圖3 表明算法標簽數(shù)據(jù)通信量最少的直接原因是搜索次數(shù)減少。圖4 表明算法閱讀器數(shù)據(jù)通信量最少的原因不但是搜索次數(shù)少,還有就是算法中發(fā)送請求命令的第一個參數(shù)是僅最高碰撞位信息也使數(shù)據(jù)通信量大大減少。圖5 閱讀器數(shù)據(jù)通信量和標簽閱讀器之間總的數(shù)據(jù)通信量取決于閱讀器數(shù)據(jù)通信量和標簽數(shù)據(jù)通信量,閱讀器數(shù)據(jù)通信量和標簽數(shù)據(jù)通信量的減少必然會使閱讀器數(shù)據(jù)通信量和標簽閱讀器之間總的數(shù)據(jù)通信量減少,由圖5 可以看出算法閱讀器和標簽之間傳輸總的數(shù)據(jù)量相比JDBS 減少量約50%,并且隨著標簽數(shù)目的增多減少量更明顯,遠多于50%。
圖5 閱讀器和標簽之間傳輸總的數(shù)據(jù)量
本文是基于二進制搜索算法提出的一種具體的改進算法,該算法在動態(tài)調(diào)整算法基礎(chǔ)上通過設(shè)置奇偶計數(shù)器來實現(xiàn)分組,一次搜索過程中所有響應的標簽計數(shù)器R 值都相等,等效于每個響應標簽ID 的‘1’的個數(shù)有相同的奇偶性,所以一次搜索過程中只有兩次比特位發(fā)生沖突可以直接識別,分組進一步減少了閱讀器的搜索次數(shù)。引入堆棧存放數(shù)據(jù)使請求命令參數(shù)簡化得以實現(xiàn),使閱讀器數(shù)據(jù)通信量減少。通過仿真實驗驗證該算法具有明顯的優(yōu)越性。
[1] 張學軍,王緒海,蔡文琦.基于分組碼的改進型防碰撞算法研究[J].計算機應用研究,2012,29(11):4265-4268.
[2] Ali K,Hassanein H,Tana A E M.RFID anti-collision protocol for dense passive tag environments[C]//Proceedings of the 32nd IEEE Conference on Local Compute Networks.Washington DC:IEEE Computer Society,2007:819-824.
[3] 朱軍,張元,盧小冬,等.基于分段搜索的多RFID 標簽抗沖突方法倡[J].計算機應用研究,2011,28(3):1031-1033.
[4] Abramson N.THE ALOHA SYSTEM:another alternative for computer communications[C]//Proceedings of the November 17-19,1970,F(xiàn)all Joint Computer Conference.ACM,1970:281-285.
[5] Maguire Y,Pappu R.An optimal Q-algorithm for the ISO 18000-6C RFID protocol[J].IEEE Transactions on Automation Science and Engineering,2009,6(1):16-24.
[6] Finkenzeller K.RFID handbook fundamentals and applications in contactless smart cards and identification[M].2nd ed.West Sussex:John Wiley & Sons Ltd,2003.
[7] Vogt H.Efficient object identification with passive RFID tags[C]//Proceedings of IEEE International Conference on System,Man and Cybernetics,2002:651-656.
[8] Chen Z,Liao M.An enhanced dynamic binary anti-collision algorithm[C]//2010 5th International Conference on Computer Science and Education(ICCSE),IEEE,2010:961-964.
[9] 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 Transaction on Industrial Information,2010,6(1):105-121.
[10] Ryu J,Lee H,Seok Y,et al.A hybrid query tree protocol for tag collision arbitration in RFID systems[C]//IEEE International Conference on Communications,2007:5981-5986.
[11] 謝振華,賴聲禮,陳鵬.標簽防沖撞算法設(shè)計[J].計算機工程,2008,34(6):90-92.
[12] 伍繼雄,江岸,黃生葉,等.RFID 系統(tǒng)中二叉樹防碰撞算法性能的提升[J].湖南大學學報:自然科學版,2010,37(12):82-86.
[13] 王雪,錢志鴻,胡正超,等.基于二叉樹的RFID 防碰撞算法的研究[J].通信學報,2010,31(6):49-57.
[14] 王亞奇,蔣國平.基于分組機制的跳躍式動態(tài)二進制防碰撞算法[J].自動化學報,2010,36(10):1390-1400.
[15] 吳躍前,辜大光,范振粵,等.RFID 系統(tǒng)防碰撞算法比較分析及其改進算法[J].計算機工程與應用,2009,45(3):210-213.