吳必造，楊曉嬌

（1 中移物聯(lián)網(wǎng)有限公司，重慶 401336；2 重慶交通大學(xué)信息技術(shù)中心，重慶 400074）

面向物聯(lián)網(wǎng)的RFID碰撞問(wèn)題分析

吳必造1，楊曉嬌2

（1 中移物聯(lián)網(wǎng)有限公司，重慶 401336；2 重慶交通大學(xué)信息技術(shù)中心，重慶 400074）

文中首先介紹了RFID系統(tǒng)中3種不同的碰撞的產(chǎn)生原理，然后研究了最常見(jiàn)的多標(biāo)簽碰撞問(wèn)題及其對(duì)應(yīng)的防碰撞算法，并重點(diǎn)研究了兩種目前工程中較常用的防碰撞算法DFS-ALOHA和Q-ALOHA算法的性能及其應(yīng)用場(chǎng)景。希望文中介紹對(duì)需要解決標(biāo)簽碰撞問(wèn)題的讀者具有一定的啟發(fā)作用。

物聯(lián)網(wǎng)；RFID；多標(biāo)簽防碰撞

物聯(lián)網(wǎng)作為下一代網(wǎng)絡(luò)的關(guān)鍵組成部分，核心是實(shí)現(xiàn)萬(wàn)物的互聯(lián)與信息間的相互傳遞，因此若要實(shí)現(xiàn)物聯(lián)網(wǎng)就需要實(shí)現(xiàn)物聯(lián)網(wǎng)中物與物的互聯(lián)，即首先要使用自動(dòng)識(shí)別技術(shù)對(duì)接入物聯(lián)網(wǎng)的物體進(jìn)行識(shí)別。隨著物聯(lián)網(wǎng)的不斷發(fā)展自動(dòng)識(shí)別技術(shù)已經(jīng)成為物聯(lián)網(wǎng)的核心技術(shù)之一[1]。

物聯(lián)網(wǎng)中的自動(dòng)識(shí)別技術(shù)需要具有“海量存儲(chǔ)”以及“廣泛感知”的主要特點(diǎn)。RFID技術(shù)具有非接觸、精度高、壽命長(zhǎng)、抗污染能力強(qiáng)、數(shù)據(jù)存儲(chǔ)容量大、安全性較高、多目標(biāo)快速識(shí)別等優(yōu)點(diǎn)，而從眾多自動(dòng)識(shí)別技術(shù)中脫穎而出被廣泛應(yīng)用于物聯(lián)網(wǎng)的接入層[2]。目前RFID技術(shù)已廣泛應(yīng)用于身份識(shí)別、零售業(yè)、物流管理、藥品防偽、公共交通管理等物聯(lián)網(wǎng)領(lǐng)域。是物聯(lián)網(wǎng)接入層中應(yīng)用最廣泛的自動(dòng)識(shí)別技術(shù)。

綜上，RFID技術(shù)未來(lái)發(fā)展前景無(wú)限，但是仍然存在諸如制造成本、協(xié)議的標(biāo)準(zhǔn)化、數(shù)據(jù)安全性、數(shù)據(jù)完整以及正確性等關(guān)鍵問(wèn)題制約著RFID技術(shù)的進(jìn)一步普及。數(shù)據(jù)完整以及正確性是決定RFID系統(tǒng)性能的重要因素，也是本文研究的重點(diǎn)[3]。導(dǎo)致這個(gè)問(wèn)題的關(guān)鍵是碰撞。碰撞又分為標(biāo)簽碰撞和閱讀器碰撞，在閱讀器作用域內(nèi)多個(gè)標(biāo)簽同時(shí)向閱讀器發(fā)送數(shù)據(jù)或者一個(gè)閱讀器在另一個(gè)閱讀器的作用域內(nèi)時(shí)，信號(hào)間發(fā)生相互干擾，導(dǎo)致閱讀器接收到的數(shù)據(jù)錯(cuò)誤，即無(wú)法完整的識(shí)別出標(biāo)簽，或者識(shí)別出錯(cuò)誤的標(biāo)簽。因此多目標(biāo)識(shí)別既是RFID的最大優(yōu)勢(shì)，也是急需解決的技術(shù)難點(diǎn)。

因此，本文首先探討RFID中碰撞的分類及其相對(duì)應(yīng)的解決方法，然后探討了RFID算法的常用協(xié)議及其對(duì)應(yīng)的RFID防碰撞算法，通過(guò)比較分析發(fā)現(xiàn)ALOHA算法是最常用的多標(biāo)簽碰撞算法，重點(diǎn)對(duì)比分析了兩種ALOHA算法DFS-ALOHA和Q-ALOHA算法，并通過(guò)仿真算法執(zhí)行的過(guò)程說(shuō)明了算法的優(yōu)劣及應(yīng)用場(chǎng)景。

1 RFID碰撞分類

1.1 標(biāo)簽碰撞

當(dāng)閱讀器R1作用域內(nèi)存在多個(gè)標(biāo)簽時(shí)，閱讀器發(fā)送尋呼命令后，閱讀器作用域內(nèi)多個(gè)標(biāo)簽同時(shí)向閱讀器發(fā)送信號(hào)時(shí)，會(huì)相互發(fā)生干擾，導(dǎo)致閱讀器讀取的數(shù)據(jù)錯(cuò)誤或者不完整即發(fā)生了碰撞。如圖1所示。

圖1 多標(biāo)簽碰撞示意圖

解決標(biāo)簽碰撞的標(biāo)簽防碰撞算法主要有Framed Slotted ALOHA、Btree、Random Slotted、Splitting Algorithm等算法。在本文第二部分會(huì)詳細(xì)介紹算法流程以及應(yīng)用場(chǎng)景。

1.2 閱讀器碰撞

當(dāng)使用相同頻率進(jìn)行通信的閱讀器R1、R2同時(shí)發(fā)送尋呼命令后，處在閱讀器RI、R2的交疊區(qū)域內(nèi)的標(biāo)簽T3將同時(shí)接收到兩個(gè)命令導(dǎo)致標(biāo)簽T3不能正確識(shí)別任何一個(gè)閱讀器的尋呼命令，而導(dǎo)致T3無(wú)法被識(shí)別。這就是閱讀器碰撞。如圖2所示。

圖2 閱讀器碰撞示意圖

閱讀器標(biāo)簽碰撞解決算法主要是Slotted Scheduled Tag Access算法，即閱讀器建需要時(shí)間同步，通過(guò)將時(shí)間分為時(shí)隙段的方式，每個(gè)閱讀器占用一個(gè)時(shí)間段，當(dāng)一個(gè)閱讀器工作時(shí)其余閱讀器休眠，就避免了閱讀器碰撞問(wèn)題。

2 標(biāo)簽碰撞算法

按照標(biāo)簽的應(yīng)用場(chǎng)景不同，RFID技術(shù)采用頻段也不同，常用的主要有如下幾種協(xié)議ISO是國(guó)際化標(biāo)準(zhǔn)組織提出的協(xié)議，以及美國(guó)EPC[4]提出的EPC[5]協(xié)議。下面將常用的協(xié)議以及對(duì)應(yīng)的防碰撞算法總結(jié)如表1所示。

表1 RFID標(biāo)準(zhǔn)及其對(duì)應(yīng)的防碰撞算法

由表1可知碰撞算法主要分為ALOHA算法和Binary Tree（二進(jìn)制樹(shù)算法），而ALOHA算法實(shí)現(xiàn)的硬件成本低，算法復(fù)雜度較低，因此成為RFID領(lǐng)域內(nèi)應(yīng)用最廣泛的防碰撞算法，廣泛應(yīng)用于倉(cāng)儲(chǔ)物流，動(dòng)物識(shí)別，車(chē)聯(lián)網(wǎng)中，同時(shí)也是接下來(lái)研究的重點(diǎn)。

2.1 ALOHA算法

ALOHA算法又稱隨即算法或不去定算法。在EPC和ISO協(xié)議的標(biāo)準(zhǔn)中涵蓋了從低頻中頻以及高頻各個(gè)頻段的多種協(xié)議規(guī)定的防碰撞算法都是ALOHA及其改進(jìn)算法。因此ALOHA算法是目前應(yīng)用最廣泛的標(biāo)簽防碰撞算法之一。目前很多的文章對(duì)標(biāo)簽估計(jì)都進(jìn)行了研究，但大多標(biāo)簽估計(jì)算法復(fù)雜度高，加重了閱讀器的負(fù)擔(dān)，增加了讀取時(shí)間。在工程中實(shí)用性較差，而實(shí)際中運(yùn)用最多的ALOHA算法主要有DFS-ALOHA和Q-ALOHA下面具體介紹兩種常見(jiàn)的ALOHA算法。

2.2 DFS-ALOHA算法

DFS(Dynamic Framed Slot)-ALOHA算法就是動(dòng)態(tài)幀時(shí)隙ALOHA算法。如圖3所示，將時(shí)間分為幀的形式，幀長(zhǎng)N=2QT（Q為正整數(shù)，T為閱讀器識(shí)別一個(gè)標(biāo)簽所需時(shí)間即單位時(shí)間），閱讀器作用域內(nèi)參與識(shí)別的n個(gè)標(biāo)簽隨機(jī)選擇N個(gè)時(shí)隙中的任意一個(gè)時(shí)隙[6]。當(dāng)n個(gè)標(biāo)簽中超過(guò)一個(gè)標(biāo)簽選擇了某個(gè)時(shí)隙即發(fā)生了碰撞如圖3所示。

很多文獻(xiàn)中對(duì)幀長(zhǎng)N的選取都有探討，可以得出當(dāng)N=閱讀器作用域內(nèi)標(biāo)簽個(gè)數(shù)時(shí)算法的吞吐率最高，而實(shí)際應(yīng)用中閱讀器不知道其作用域內(nèi)的標(biāo)簽個(gè)數(shù)，只能通過(guò)閱讀器收到的一幀中碰撞，空閑以及成功時(shí)隙的個(gè)數(shù)來(lái)估計(jì)標(biāo)簽個(gè)數(shù)[7]。如圖4中就是通過(guò)收到的時(shí)隙數(shù)來(lái)調(diào)整幀長(zhǎng)。

圖3 動(dòng)態(tài)幀時(shí)隙ALOHA算法時(shí)隙選擇圖

圖4 DFS-ALOHA算法幀長(zhǎng)改變流程圖

DFS-ALOHA算法的特點(diǎn)是在算法執(zhí)行過(guò)程中運(yùn)用的命令較簡(jiǎn)單，即只需應(yīng)用到協(xié)議中規(guī)定的命令：Query(Q)幀尋呼命令；QueryAdjust(Q)更新Q值命令；QueryPep幀內(nèi)尋呼下一時(shí)隙命令。沒(méi)有像很多改進(jìn)算法一樣額外的增加尋呼命令而造成閱讀器的負(fù)擔(dān)。具體命令的用法讀者可以參照ISO標(biāo)準(zhǔn)，由于版面有限這里就不再累述。DFS-ALOHA算法的思想是：當(dāng)一幀所有時(shí)隙識(shí)別完成后，通過(guò)統(tǒng)計(jì)得出的碰撞時(shí)隙NC，空閑時(shí)隙NI進(jìn)行計(jì)算判斷若Pc=(NC/N)＞0.75或者PI=(NI/N)＞0.3調(diào)整幀長(zhǎng)，直至幀長(zhǎng)N=0，即識(shí)表示識(shí)別完所有標(biāo)簽為止。由于這類算法易實(shí)現(xiàn)且對(duì)硬件要求較低，不許復(fù)雜的運(yùn)算以及浮點(diǎn)運(yùn)算，因此這類算法是工程中最常用的ALOHA算法[8]。

2.3 Q-ALOHA算法

Q算法本質(zhì)也是ALOHA算法，Q-ALOHA算法和DFS-ALOHA算法的區(qū)別主要是幀長(zhǎng)的調(diào)整方式不同，區(qū)別是Q算法通過(guò)引入浮點(diǎn)數(shù)Qfp和C來(lái)動(dòng)態(tài)調(diào)整幀長(zhǎng)，當(dāng)Q值達(dá)到需要調(diào)整的閾值時(shí)不論本幀是否識(shí)別完畢，都結(jié)束對(duì)當(dāng)前幀的識(shí)別，立即采用QueryAdjust(Q)調(diào)整幀長(zhǎng)，因此Q算法對(duì)幀長(zhǎng)的調(diào)整更加靈活。

如圖5中可以看出當(dāng)檢測(cè)到碰撞時(shí)隙時(shí)浮點(diǎn)數(shù)Qfp值增加C，檢測(cè)到空閑時(shí)隙時(shí)Qfp值減少C，EPC標(biāo)準(zhǔn)中建議C值的選取為0.2～0.5。每結(jié)束一個(gè)時(shí)隙就對(duì)Qfp值四舍五入取整，若取整后Q值相較之前值發(fā)生了變化則立即停止當(dāng)前幀的識(shí)別過(guò)程，用QueryAdjust(Q)命令更改幀長(zhǎng)。本算法相較于DFS-ALOHA算法不同的是引入了浮點(diǎn)數(shù)Qfp和C來(lái)及時(shí)的改變幀長(zhǎng)Q，隨著浮點(diǎn)數(shù)的引入就增加了浮點(diǎn)運(yùn)算，因此需要射頻芯片支持浮點(diǎn)運(yùn)算，當(dāng)然目前基本主流的射頻芯片都支持浮點(diǎn)運(yùn)算。由于算法適應(yīng)性更好因此運(yùn)算效率較高。但由于需要進(jìn)行浮點(diǎn)運(yùn)算因此算法的復(fù)雜度也較高。

圖5 Q-ALOHA算法幀長(zhǎng)改變流程圖

3 算法性能對(duì)比

在Matlab7.0平臺(tái)上，模擬兩種算法的實(shí)際執(zhí)行過(guò)程，以閱讀器范圍內(nèi)標(biāo)簽個(gè)數(shù)為n個(gè)（x軸），識(shí)別晚閱讀器內(nèi)n個(gè)標(biāo)簽需要的時(shí)隙數(shù)N個(gè)（y軸），反復(fù)運(yùn)行50次求平均值。

Q-ALOHA算法識(shí)別相同的標(biāo)簽需要的時(shí)隙數(shù)總體是少于DFS-ALOHA算法的，在標(biāo)簽數(shù)少于100時(shí)，差距不大，但是隨著標(biāo)簽個(gè)數(shù)的增加時(shí)隙數(shù)相差越來(lái)越大。因此在工程中可以根據(jù)實(shí)際應(yīng)用場(chǎng)景選取合適的算法，如果待識(shí)別標(biāo)簽少于100建議采用DFS-ALOHA算法，當(dāng)標(biāo)簽大于100時(shí)為了減少識(shí)別時(shí)間，提高準(zhǔn)確率可以采用Q-ALOHA算法。

4 小結(jié)

本文首先分析了物聯(lián)網(wǎng)中自動(dòng)識(shí)別技術(shù)RFID中碰撞產(chǎn)生的原因及分類，然后針對(duì)RFID技術(shù)中最常見(jiàn)的碰撞類型——多標(biāo)簽碰撞進(jìn)行了分析，針對(duì)工程實(shí)際中較常用的標(biāo)簽碰撞算法DFS-ALOHA以及Q-ALOHA算法的工作流程進(jìn)行分析，并通過(guò)Matlab模擬算法的實(shí)際執(zhí)行過(guò)程，對(duì)比分析了算法的效率實(shí)用性，應(yīng)用場(chǎng)合等。

[1] 游戰(zhàn)清. 無(wú)線射頻技術(shù)(RFID)理論與應(yīng)用[M]. 北京：電子工業(yè)出版社，2004,30-38.

[2] 黃玉蘭. 射頻識(shí)別(RFID)核心技術(shù)詳解[M]. 北京：人民郵電出版社，2010.

[3] 中國(guó)行業(yè)研究網(wǎng). 未來(lái)超高頻RFID發(fā)展趨勢(shì)分析[EB/OL]. http://www.chinairn.com. Xiao X, Wang WP, Yang L M, et al. Wireless broadcasting retransmission approach based on network coding[J]. Journal on Communications,2009,30(9):69-75.

[4] EPC Global. EPC Radio-Frequency Identity Protocols Gengernation-1[S].

[5] ISO/IEC. TR 24729-1-2008.Information technology-Radio frequency identification for item management-Implementation guidelines-Part 1[S].

[6] Lee S R, Joo S D, Lee C W. An enhanced dynamic framed slotted ALOHA algorithm for RFID tag identification[C]. Mobile and Ubiquitous Systems: Networking and Services, 2005. MobiQuitous 2005. The Second Annual International Conference on[C]. IEEE, 2005: 166-172.

[7] 梁釗. ALOHA隨機(jī)多址通信技術(shù)-從純ALOHA到擴(kuò)展ALOHA[J].移動(dòng)通信, 1999(5):17-20.

[8] 吳春華, 陳軍. 動(dòng)態(tài)ALOHAX法在解決RFID反碰撞問(wèn)題中的應(yīng)用[J]. 電子器件, 2003,26(2):173-176.

Introduction of collisions of RFID in Internet of Things

WU Bi-zao1, YANG Xiao-jiao2
(1 China Mobile IoT Company Limited, Chongqing 401336, China; 2 Information Technology Centre, Chongqing Jiaotong University, Chongqing 400074, China)

This paper introduce the collision cause of radio frequency identif i cation system, then discussed the most common collision form that is multi-tag collision and its anti-collision algorithm. This paper mainly focus on the performance and the application scenarios of dynamic framed slot ALOHA and query ALOHA algorithm whichmostly used in engineering. Therefore I hope that through this paper will enlighten those readers which need to solve multi-tag collision problem.

Internet of Things; radio frequency of identif i cation; multi-tag anti-collision

TP393

A

1008-5599（2017）05-0022-04

2017-04-10