改進(jìn)的基于多比特識(shí)別的射頻識(shí)別標(biāo)簽防碰撞的技術(shù)條件

1、改進(jìn)的基于多比特識(shí)別的射頻識(shí)別標(biāo)簽防碰撞的技術(shù)條件0 引言射頻識(shí)別（Radio Frequency Identification， RFID）作為一種無線通信技術(shù)，目前已經(jīng)被廣泛地應(yīng)用到供應(yīng)鏈管理、追蹤和定位系統(tǒng)中。與傳統(tǒng)的條形碼相比，它具備較長(zhǎng)的識(shí)別距離、較高的傳輸速率等優(yōu)點(diǎn)【1】。隨著RFID技術(shù)的廣泛應(yīng)用，經(jīng)常會(huì)有識(shí)別多個(gè)標(biāo)簽的需求。然而，當(dāng)多個(gè)標(biāo)簽同時(shí)響應(yīng)讀寫器的請(qǐng)求時(shí)會(huì)發(fā)生碰撞，這使得讀寫器無法正確地識(shí)別標(biāo)簽的傳輸信息，浪費(fèi)了通信帶寬以及延長(zhǎng)了識(shí)別時(shí)間。RFID防碰撞算法就是致力于解決標(biāo)簽碰撞問題。目前的RFID防碰撞算法主要分3類【2】：基于ALOHA的防碰撞算法、基于樹的算法以及

2、混合類型的防碰撞算法?；贏LOHA的算法，如幀時(shí)隙ALOHA（Framed Slotted ALOHA， FSA）算法【3】、動(dòng)態(tài)幀時(shí)隙ALOHA算法（Dynamic Framed Slotted ALOHA， DFSA）等，將傳輸時(shí)間分成許多個(gè)時(shí)隙，并將多個(gè)時(shí)隙組裝在一個(gè)幀中，處在讀寫器讀寫范圍的標(biāo)簽隨機(jī)選擇一個(gè)時(shí)隙傳輸響應(yīng)信息，從而降低了碰撞的可能性。但是，會(huì)出現(xiàn)標(biāo)簽餓死;現(xiàn)象，即一個(gè)標(biāo)簽在很長(zhǎng)時(shí)間內(nèi)無法識(shí)別的現(xiàn)象。此外，基于ALOHA的算法的性能還受標(biāo)簽數(shù)量、初始幀大小以及標(biāo)簽估計(jì)算法的影響?；跇涞乃惴?，如查詢樹（Query Tree， QT）算法【6】、二進(jìn)制樹（Binary Tr

3、ee， BT）算法以及碰撞樹（Collision Tree， CT）算法等，通過利用標(biāo)簽的ID信息或者標(biāo)簽選擇的隨機(jī)數(shù)來不斷地將碰撞的標(biāo)簽進(jìn)行分組直到所有標(biāo)簽均被識(shí)別。這類算法簡(jiǎn)單，易于實(shí)施，且能夠避免標(biāo)簽餓死;現(xiàn)象；但是存在識(shí)別效率較低、通信量較大等缺點(diǎn)。近年來，有許多學(xué)者提出混合類型的防碰撞算法，通過將ALOHA類算法和基于樹的算法的優(yōu)勢(shì)結(jié)合起來，同時(shí)借助標(biāo)簽估計(jì)算法、比特追蹤技術(shù)以及比特恢復(fù)技術(shù)，能夠在避免標(biāo)簽餓死;的同時(shí)，以較高的識(shí)別效率對(duì)標(biāo)簽進(jìn)行識(shí)別。比如，文獻(xiàn)【2】提出的指定樹時(shí)隙ALOHA（Assigned Tree Slotted ALOHA， ATSA）算法，采用幀時(shí)隙的結(jié)構(gòu)

4、，每一幀有一個(gè)幀前綴，每一個(gè)時(shí)隙有時(shí)隙前綴，標(biāo)簽通過匹配幀前綴和時(shí)隙前綴決定響應(yīng)與否，該算法能有效地減少碰撞，因此算法具有較高的效率。此外，由于標(biāo)簽只需要響應(yīng)除去匹配的幀前綴和時(shí)隙前綴部分外的ID，因此標(biāo)簽的通信開支也較小。最近，文獻(xiàn)提出多比特標(biāo)簽識(shí)別（MultiBit Identification， MBI）協(xié)議，協(xié)議以一定長(zhǎng)度為單位對(duì)標(biāo)簽的響應(yīng)進(jìn)行識(shí)別，當(dāng)讀取的段內(nèi)有多比特碰撞時(shí)，通過開啟特殊的時(shí)隙對(duì)當(dāng)前時(shí)隙內(nèi)所有標(biāo)簽的ID段進(jìn)行恢復(fù)，減小了這些標(biāo)簽在下一幀中繼續(xù)發(fā)生碰撞的概率，進(jìn)而提高了識(shí)別效率；但是，它存在查詢前綴重復(fù)發(fā)送，以及標(biāo)簽端通信開支較大等問題。本文在文獻(xiàn)的基礎(chǔ)上，提出了一種改

5、進(jìn)的多比特識(shí)別（Enhanced MultiBit Identification， EnMBI）協(xié)議，通過采用幀時(shí)隙的結(jié)構(gòu)和僅對(duì)碰撞比特進(jìn)行恢復(fù)的方法，能夠很好地降低識(shí)別過程的通信開支；此外，本文算法也不需要標(biāo)簽存儲(chǔ)編碼方案。仿真實(shí)驗(yàn)的結(jié)果表明，該算法具有相對(duì)較低的通信開支。1 相關(guān)工作本章簡(jiǎn)要地介紹基于單比特碰撞恢復(fù)的碰撞樹（CT）算法以及文獻(xiàn)提出的基于多比特識(shí)別（MBI）的算法。1.1 CT算法CT算法是在QT算法上改進(jìn)的一種樹型算法，它們都使用標(biāo)簽的ID去區(qū)分碰撞的標(biāo)簽。區(qū)別是：CT算法使用曼徹斯特編碼對(duì)標(biāo)簽響應(yīng)的第一個(gè)碰撞比特進(jìn)行定位，并將下一次的查詢前綴變更為prefix+C0&he

6、llip;Cn-1+0和prefix+C0…Cn-1+1。其中：prefix為當(dāng)前查詢前綴，C0…Cn-1為第一碰撞位之前的響應(yīng)比特。這樣減小了空閑時(shí)隙的個(gè)數(shù)，CT算法具有較低的識(shí)別延遲。1.2 MBIMBI在讀寫器端以Lb為單位檢測(cè)標(biāo)簽的響應(yīng)，在當(dāng)前檢測(cè)單元內(nèi)出現(xiàn)多比特碰撞時(shí)，其開啟一個(gè)多比特時(shí)隙即可恢復(fù)出所有參與碰撞的標(biāo)簽ID段。為了在一個(gè)時(shí)隙中識(shí)別出多個(gè)標(biāo)簽ID段，MBI提出一種可區(qū)分的分組方案，它利用群論的知識(shí)將所有的Lb ID段劃分為2L/L組，使得同一組的ID段在同一時(shí)隙傳輸能被同時(shí)識(shí)別出。表1為一種識(shí)別長(zhǎng)度L=4的ID段分組方案。表1中，每一列為一組，

7、且每一組有一個(gè)代表元位于該列下方。同一個(gè)組內(nèi)的ID段滿足只有1b不同于代表元，每個(gè)ID段的不同于代表元的那1b被稱為特征比特。關(guān)于其他L時(shí)的分組方法，可參考文獻(xiàn)中的詳細(xì)說明。識(shí)別開始時(shí)，讀寫器發(fā)送一個(gè)前綴和1bit 0;1比特01比特0;？此句何意？請(qǐng)明確。是否未說明完整。表明當(dāng)前時(shí)隙是一個(gè)基本查詢時(shí)隙，初始時(shí)前綴為空。處于讀寫器讀寫范圍的標(biāo)簽收到查詢請(qǐng)求后，先利用ID匹配前綴，如果匹配，則響應(yīng)剩余的ID比特。讀寫器在接收到標(biāo)簽響應(yīng)后，以Lb為單元檢測(cè)響應(yīng)，對(duì)于每一個(gè)單元Wi，有以下3種情形：情形1 Wi單元內(nèi)沒有碰撞，此時(shí)讀寫器將當(dāng)前查詢前綴變?yōu)閜refix+Wi并繼續(xù)檢測(cè)下一單元Wi+1，

8、直到prefix長(zhǎng)度達(dá)到ID的長(zhǎng)度。情形2 Wi單元內(nèi)只有1b碰撞，此時(shí)讀寫器將碰撞比特分別用0和1替換得到Wi0和Wi1，并分別添加到prefix上，若沒有達(dá)到ID的長(zhǎng)度，則將得到的兩個(gè)查詢前綴存入棧中進(jìn)行下一次查詢；否則，將識(shí)別的兩個(gè)ID存入已識(shí)別的ID隊(duì)列中。情形3 Wi單元內(nèi)有兩個(gè)或多個(gè)碰撞比特，此時(shí)，讀寫器發(fā)送帶有prefix和1bit 1;1比特1同上一個(gè)問題。的查詢命令開啟一個(gè)多比特識(shí)別時(shí)隙。在多比特識(shí)別時(shí)隙中，收到命令的標(biāo)簽先利用ID匹配前綴，如果匹配，則取出prefix后的Lb，記為C，并利用C計(jì)算響應(yīng)G。標(biāo)簽用C逐個(gè)異或分組方案中每一組的代表元;，如果異或結(jié)果中只有1b為1

9、，則將異或結(jié)果追加到G上；否則將Lb 0追加到G上，待與所有分組的代表元比較完成后，響應(yīng)2Lb G。讀寫器在收到響應(yīng)時(shí)，同樣以Lb為檢測(cè)單元，從0單元開始檢測(cè)。如果當(dāng)前單元Ui沒有碰撞時(shí)，則轉(zhuǎn)向檢測(cè)下一單元。如果有碰撞，則找出第i組中以當(dāng)前碰撞位置為特征比特的所有ID段，直到整個(gè)響應(yīng)被檢測(cè)完。將所有恢復(fù)出的ID段分別添加到prefix上判斷是否需要繼續(xù)查詢。最后，讀寫器判斷當(dāng)前查詢命令棧是否為空，若為空，則識(shí)別完成，停止查詢；否則，繼續(xù)上述查詢過程。由于MBI采用多時(shí)隙恢復(fù)標(biāo)簽的碰撞，因此能加快查詢過程，但是當(dāng)在基本單元中檢測(cè)到多比特碰撞時(shí)，不管碰撞比特的多少，都開啟一個(gè)M時(shí)隙進(jìn)行查詢，這樣即

10、使碰撞標(biāo)簽很少，參與碰撞的標(biāo)簽都需要響應(yīng)長(zhǎng)為2Lb的串，這使得標(biāo)簽端的通信量太大。此外，在一個(gè)多比特時(shí)隙結(jié)束后，如果恢復(fù)出m個(gè)ID段，并需要再次查詢時(shí)，相同的查詢前綴重復(fù)發(fā)送m次，從而導(dǎo)致了很大的通信開支。2 改進(jìn)的多比特識(shí)別算法本章將介紹改進(jìn)的多比特識(shí)別（EnMBI）算法。EnMBI采用與MBI不同的幀時(shí)隙的結(jié)構(gòu)，在每一幀中，標(biāo)簽先用ID匹配幀前綴，如果匹配，則再繼續(xù)匹配時(shí)隙前綴從而確定在哪一個(gè)時(shí)隙發(fā)送響應(yīng)。此外，EnMBI不要求標(biāo)簽存儲(chǔ)任何標(biāo)簽分組信息。2.1 算法的描述為了能夠在讀寫器端準(zhǔn)確的檢測(cè)標(biāo)簽響應(yīng)的碰撞位置，EnMBI也采用曼徹斯特編碼。同時(shí)，讀寫器端需要命令隊(duì)列（Command

11、 Queue， CQ）和ID隊(duì)列（記為IDmemory）分別存儲(chǔ)查詢信息以及已經(jīng)識(shí)別的標(biāo)簽ID。表2列舉了算法中用到的一些符號(hào)和命令。3）讀寫器取出命令（0000，0，SQ），并從SQ中取出一個(gè)時(shí)隙前綴，發(fā)送Query（0000，0，0010），所有標(biāo)簽均匹配幀前綴，但只有標(biāo)簽B、E響應(yīng)。讀寫器收到響應(yīng)G后發(fā)現(xiàn)只有1b碰撞，B和E被成功識(shí)別，并在以后的查詢中不再響應(yīng)。讀寫器檢測(cè)到當(dāng)前時(shí)隙隊(duì)列SQ非空，于是在接下來兩個(gè)時(shí)隙中發(fā)送QueryRep（0110）和QueryRep（0111）命令，分別對(duì)應(yīng)標(biāo)簽A、C、D和F、G響應(yīng)。時(shí)隙2中只有1b碰撞，因此F和G被識(shí)別。時(shí)隙1中出現(xiàn)多比特碰撞，因此先

12、將xx1x壓入隊(duì)列S中，后將（00000110，1，S）壓入CQ中。4）讀寫器發(fā)送Query（00000110，1，xx1x），標(biāo)簽A、C、D匹配幀前綴，取出ID的第8，9，11位的3b，按步驟2）中方式編碼成8b的串返回。在讀寫器端檢測(cè)到響應(yīng)的第1b，6b，7b有碰撞，于是恢復(fù)出碰撞位信息001，110，111，最終得到恢復(fù)的ID串0011，1110，1111。隨后將其壓入隊(duì)列S，并將（00000110，0，S）壓入隊(duì)列CQ。5）讀寫器取出命令（00000110，0，SQ），并從SQ中取出一個(gè)時(shí)隙前綴，發(fā)送Query（0000，0，1110），標(biāo)簽A被識(shí)別。之后，發(fā)送QueryRep（001

13、1）和QueryRep（1111），標(biāo)簽C和D相繼被識(shí)別。6）讀寫器檢測(cè)到命令隊(duì)列CQ為空，查詢結(jié)束。3 算法仿真及分析實(shí)驗(yàn)采用Monte Carlo的仿真方法，通過C+和Matlab模擬實(shí)現(xiàn)了算法的運(yùn)行過程。仿真涉及1個(gè)讀寫器和多個(gè)標(biāo)簽。標(biāo)簽的數(shù)量從100到2000，步長(zhǎng)100，標(biāo)簽ID長(zhǎng)度為96b。對(duì)于每個(gè)標(biāo)簽數(shù)量仿真50次，取平均值作為最后的實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)涉及本文提出的EnMBI算法、MBI算法、QT【6】、CT以及ATSA【2】算法。下面分別從通信開支和總的時(shí)隙數(shù)兩個(gè)方面對(duì)算法仿真結(jié)果進(jìn)行分析。3.1 通信開支防碰撞算法通信開支通常涉及標(biāo)簽端的通信開支和總的通信開支兩種：標(biāo)簽端的通信開

14、支指在一次識(shí)別過程中平均每一個(gè)標(biāo)簽需要發(fā)送的比特?cái)?shù)；總的通信開支包括閱讀器端的通信開支和標(biāo)簽端的通信開支。為了降低標(biāo)簽的復(fù)雜性及能量消耗，標(biāo)簽開支需要越小越好。其次，為了使得識(shí)別時(shí)間較小且能量消耗較少，總的通信開支也應(yīng)盡量地小。圖23分別是改進(jìn)的EnMBI算法和MBI算法在L=4和L=8兩種情況下的通信開支比較。仿真圖中將L=4和L=8的EnMBI算法分別記為EnMBI（4）和EnMBI（8）。從圖2可以看出，改進(jìn)的EnMBI算法比MBI算法有較小的標(biāo)簽通信開支，這主要得益于EnMBI僅對(duì)檢測(cè)單元里的碰撞比特進(jìn)行恢復(fù)而MBI對(duì)碰撞和非碰撞比特均進(jìn)行恢復(fù)。當(dāng)L=4時(shí)效果不明顯，這是因?yàn)楫?dāng)L較小且

15、標(biāo)簽數(shù)量較大時(shí)，檢測(cè)單元W內(nèi)有很大的幾率出現(xiàn)3b或4b碰撞，這時(shí)EnMBI的優(yōu)勢(shì)不明顯。當(dāng)L=8時(shí)，EnMBI對(duì)應(yīng)每個(gè)標(biāo)簽的通信量可相對(duì)MBI最多減小100b，隨著標(biāo)簽數(shù)量的增加，L=8檢測(cè)單元內(nèi)碰撞數(shù)目增加，因此減少的比特?cái)?shù)也相應(yīng)減少。從圖3可以看出，EnMBI相比MBI有較小的總通信開支，當(dāng)L=4時(shí)，約減少10%；當(dāng)L=8時(shí)，約減少20%。這是由于EnMBI減少了MBI的重復(fù)前綴發(fā)送以及多比特時(shí)隙的響應(yīng)比特?cái)?shù)。為了進(jìn)一步驗(yàn)證EnMBI算法的優(yōu)勢(shì)，圖4和圖5分別是EnMBI和其他3種算法（QT、CT及ATSA算法）在標(biāo)簽端開支和總通信開支方面的比較。為了進(jìn)行公平的比較，QT以及CT的Quer

16、y命令長(zhǎng)度為18b，EnMBI和ATSA由于需要在Query中指明幀的大小，因此需要22b。此外EnMBI還需要額外的1b來表明當(dāng)前的時(shí)隙類型?？紤]到空閑時(shí)隙通常比碰撞時(shí)隙和可讀時(shí)隙持續(xù)時(shí)間要短，因此將QT和ATSA中空間時(shí)隙維持時(shí)間設(shè)為6b信號(hào)的傳輸時(shí)間。因此將QT和ATSA中空閑時(shí)隙維持時(shí)間設(shè)為6b此句中，維持時(shí)間的單位是bit嗎？是否是表達(dá)錯(cuò)誤，請(qǐng)作相應(yīng)調(diào)整。從圖4可以看出，QT的標(biāo)簽通信開支最大，CT較QT有所減少，這是因?yàn)镼T算法中標(biāo)簽每次發(fā)送整個(gè)ID，而CT中只需要發(fā)送除去匹配前綴后的ID。EnMBI擁有比CT和QT較少的標(biāo)簽通信開支是因?yàn)镋nMBI在一個(gè)時(shí)隙中可以恢復(fù)出多個(gè)標(biāo)簽，

17、從而減少了標(biāo)簽在下一時(shí)隙發(fā)生碰撞的概率，而CT和QT在發(fā)生碰撞時(shí)只根據(jù)標(biāo)簽ID的1b進(jìn)行區(qū)分，后續(xù)識(shí)別過程中碰撞概率仍然很大。ATSA由于利用多比特對(duì)碰撞標(biāo)簽進(jìn)行分組，且每次標(biāo)簽回復(fù)匹配后的剩余比特，因此擁有最小的標(biāo)簽通信開支。從圖5可以看出，EnMBI的總通信開支優(yōu)于QT和CT，主要得益于其利用多時(shí)隙恢復(fù)多個(gè)碰撞標(biāo)簽的方式以及采用幀時(shí)隙的方式減小了查詢前綴的重復(fù)發(fā)送。此外，ATSA和EnMBI（4）擁有接近的總的通信開支，當(dāng)標(biāo)簽數(shù)量大于1000時(shí)，EnMBI稍優(yōu)于ATSA。3.2 總的時(shí)隙數(shù)在標(biāo)簽數(shù)量一定時(shí)，總的時(shí)隙數(shù)是衡量防碰撞算法性能的重要指標(biāo)，其為識(shí)別標(biāo)簽的過程中所需的空閑時(shí)隙、可讀時(shí)

18、隙以及碰撞時(shí)隙的總和。由于EnMBI和MBI算法的效率僅在總通信開支和標(biāo)簽端通信開支上不同，因此本節(jié)只繪制了EnMBI和其他方案的總時(shí)隙比較。圖6是幾種算法的總時(shí)隙比較。從圖6可以看出，EnMBI（8）在識(shí)別相同數(shù)量標(biāo)簽時(shí)需要最少的總時(shí)隙數(shù)，因而也具有最高的效率。這主要得益于EnMBI（8）以L=8為識(shí)別單元，當(dāng)識(shí)別單元內(nèi)有碰撞時(shí)，可以通過1個(gè)多比特識(shí)別時(shí)隙解決該單元內(nèi)的所有碰撞，因此花費(fèi)的時(shí)隙較少。此外，EnMBI（4）和ATSA有接近的總時(shí)隙數(shù)。CT的總時(shí)隙數(shù)較QT少，是因?yàn)镃T采用曼徹斯特編碼消除了QT中出現(xiàn)的不必要的空閑時(shí)隙。4 結(jié)語(yǔ)基于單碰撞比特恢復(fù)的防碰撞算法能夠避免不必要的空閑時(shí)

19、隙，但是解決碰撞過程較慢，會(huì)產(chǎn)生較多的碰撞時(shí)隙。采用多比特識(shí)別的方法能夠較快地解決碰撞，但是存在標(biāo)簽端通信開支和總通信延遲太大的問題，本文提出了一種改進(jìn)的多比特識(shí)別算法。該算法利用了幀時(shí)隙結(jié)構(gòu)的優(yōu)點(diǎn)，同時(shí)僅對(duì)碰撞比特進(jìn)行恢復(fù)，能夠在不增加總的識(shí)別時(shí)隙的情況下降低標(biāo)簽端和總的通信量。此外，標(biāo)簽并不需要存儲(chǔ)任何有關(guān)分組的信息。通過仿真分析可以看出，改進(jìn)的多比特識(shí)別算法具有較小的通信開支，此外在所需總時(shí)隙數(shù)目上也具有明顯優(yōu)勢(shì)。參考文獻(xiàn)：【1】LAI YC， HSIAO LY， CHEN HJ. A novel query tree protocol with bit tracking in RFID

20、 tag identification . IEEE Transactions on Mobile Computing， 2013， 12（10）： 2063-2074.【2】ZHANG L， ZHANG J， TANG X. Assigned tree slotted ALOHA RFID tag anticollision protocols . IEEE Transactions on Wireless Communications， 2013， 12（11）： 5493-5505.【3】SCHOUTE F C. Dynamic frame length ALOHA . IEEE Transactions on Communications， 1983， 31（4）： 565-568.【4】VOGT H. Efficient object identification with passive RFID tags / Proceedings of the First International Conference on Pervasive Computing. Berlin： Springer