李波

(華南理工大學(xué)電子與信息學(xué)院，廣東廣州510640)

射頻識(shí)別(RFID)技術(shù)作為一種新的自動(dòng)識(shí)別技術(shù)，以其快速、實(shí)時(shí)、準(zhǔn)確采集的特點(diǎn)在眾多領(lǐng)域得到廣泛應(yīng)用［1-2］.RFID系統(tǒng)主要由閱讀器、標(biāo)簽和數(shù)據(jù)處理3部分組成，其中閱讀器和標(biāo)簽之間采用非接觸工作方式交互信息.在RFID系統(tǒng)中標(biāo)簽有3種類型:主動(dòng)、被動(dòng)和半主動(dòng)［3-5］.文中主要討論被動(dòng)類型的標(biāo)簽.被動(dòng)標(biāo)簽本身是無源的，其工作所需的能量是靠閱讀器傳輸給它的［2］，且標(biāo)簽之間不能交互，多個(gè)標(biāo)簽同時(shí)發(fā)送數(shù)據(jù)會(huì)導(dǎo)致閱讀器讀取數(shù)據(jù)沖突.防碰撞算法就是用來避免這種情況的發(fā)生、協(xié)調(diào)標(biāo)簽之間順序工作的.目前主要有兩種防碰撞算法:二叉樹算法和ALOHA算法［6-7］.

ALOHA算法是標(biāo)簽在每個(gè)時(shí)隙開始時(shí)競(jìng)爭(zhēng)信道，競(jìng)爭(zhēng)到信道的標(biāo)簽發(fā)送數(shù)據(jù)，沒有競(jìng)爭(zhēng)到的會(huì)隨機(jī)地等待一段時(shí)間后再次競(jìng)爭(zhēng)信道［5，8］.Deng等［9］提出一種可以自適應(yīng)調(diào)整時(shí)隙的算法，該算法能夠根據(jù)未識(shí)別的標(biāo)簽數(shù)量調(diào)整時(shí)隙的數(shù)量，使得識(shí)別吞吐量達(dá)到最大值.二叉樹算法中，閱讀器通過要求標(biāo)簽不斷地選擇0和1來使標(biāo)簽有序地發(fā)送數(shù)據(jù).這兩種算法雖然能解決標(biāo)簽的沖突問題，但交互過程過多，且隨機(jī)性很強(qiáng)，當(dāng)標(biāo)簽數(shù)量較多時(shí)，識(shí)別效率會(huì)嚴(yán)重下降［1，5，8，10-11］.鄧輝舫等［12］對(duì)二叉樹算法進(jìn)行了改進(jìn)，使算法保持后退式二進(jìn)制樹形搜索算法的后退機(jī)理，實(shí)現(xiàn)標(biāo)簽的有序讀取.在這兩種算法的基礎(chǔ)上，Wang等［13］提出了一種基于ALOHA的分組識(shí)別算法.該算法先利用循環(huán)過程來預(yù)識(shí)別所有的標(biāo)簽，然后將所要識(shí)別的標(biāo)簽進(jìn)行分組，分組結(jié)束后再利用ALOHA算法識(shí)別各組中的標(biāo)簽.

為減少可讀取標(biāo)簽的數(shù)量并自適應(yīng)地改變標(biāo)簽應(yīng)答時(shí)隙的數(shù)量以提高系統(tǒng)的識(shí)別效率，文中依據(jù)概率統(tǒng)計(jì)理論和代數(shù)理論提出了基于標(biāo)簽信息分組的防碰撞算法.

1 算法描述

電子標(biāo)簽是識(shí)別對(duì)象的數(shù)據(jù)承載體，存儲(chǔ)識(shí)別對(duì)象和標(biāo)簽的信息，并在數(shù)據(jù)寫入標(biāo)簽后對(duì)這些數(shù)據(jù)序列生成一個(gè)循環(huán)冗余校驗(yàn)(CRC)碼，用于在數(shù)據(jù)通信中校驗(yàn)序列［14］.分組識(shí)別算法就是以標(biāo)簽的CRC碼作為分組依據(jù).算法中利用這些已生成的CRC碼再生成更低位的CRC碼值作為每個(gè)標(biāo)簽的組號(hào)，而每個(gè)組中的標(biāo)簽以自身的標(biāo)簽序號(hào)作為隨機(jī)算法的種子，生成隨機(jī)數(shù)并作為它占用的時(shí)隙序號(hào)，其中每個(gè)組的時(shí)隙總數(shù)為2l，l為標(biāo)簽序號(hào)的位數(shù).然后，閱讀器按照分組順序依次識(shí)別這些標(biāo)簽，在組內(nèi)按照標(biāo)簽所選擇的時(shí)隙號(hào)依次讀取數(shù)據(jù).

1.1 標(biāo)簽狀態(tài)的遷移

標(biāo)簽在識(shí)別的過程中處于不同的狀態(tài)，根據(jù)閱讀器的請(qǐng)求命令從一個(gè)狀態(tài)遷移到另一個(gè)狀態(tài).文中算法定義了標(biāo)簽在識(shí)別過程中的5種狀態(tài):

(1)激活狀態(tài)標(biāo)簽選擇了一個(gè)時(shí)隙，正在與閱讀器進(jìn)行交互.

(2)休眠狀態(tài)標(biāo)簽已選擇了時(shí)隙，在等待閱讀器的喚醒請(qǐng)求.

(3)已識(shí)別狀態(tài)標(biāo)簽已被成功讀取，處于該狀態(tài)的標(biāo)簽不再響應(yīng)任何閱讀器命令.

(4)等待狀態(tài)處于該狀態(tài)的標(biāo)簽表示該標(biāo)簽所在的組還沒有被閱讀器選中并進(jìn)行識(shí)別，在等待閱讀器的REQ-Start請(qǐng)求.

(5)沖突狀態(tài)當(dāng)標(biāo)簽所選擇的時(shí)隙與其它標(biāo)簽相同時(shí)所具有的狀態(tài).

標(biāo)簽狀態(tài)遷移過程如圖1所示.所有的標(biāo)簽在識(shí)別開始時(shí)全部處于激活狀態(tài)，分組結(jié)束后，沒有被選擇識(shí)別的組遷移到等待狀態(tài)，而被選中的標(biāo)簽組則保持激活狀態(tài)，完成時(shí)隙選擇后遷移到休眠狀態(tài)，直到閱讀器喚醒標(biāo)簽開始識(shí)別.所有沖突的標(biāo)簽在一次輪詢識(shí)別結(jié)束后響應(yīng)閱讀器的請(qǐng)求返回激活狀態(tài)，重新開始選擇時(shí)隙，直到被成功讀取，響應(yīng)REQ_Kill請(qǐng)求遷移到已識(shí)別狀態(tài).其它保持等待狀態(tài)的標(biāo)簽要在被識(shí)別的組中的所有標(biāo)簽都遷移到已識(shí)別狀態(tài)后，才會(huì)被閱讀器喚醒.

圖1 標(biāo)簽狀態(tài)遷移示意圖Fig.1 Schematic diagram of state transition of tag

1.2 標(biāo)簽分組與時(shí)隙選擇

現(xiàn)有的RFID標(biāo)準(zhǔn)中一般采用16位的CRC碼作為校驗(yàn)碼，故文中以16位CRC為例進(jìn)行討論.當(dāng)閱讀器檢測(cè)到有新標(biāo)簽進(jìn)入其射頻場(chǎng)后，先鎖定標(biāo)簽，并在后續(xù)識(shí)別過程中只識(shí)別這些鎖定的標(biāo)簽，防止有新的標(biāo)簽進(jìn)入時(shí)擾亂正在進(jìn)行的識(shí)別過程.標(biāo)簽收到開始識(shí)別的請(qǐng)求后，提取自身的16位CRC碼值，采用模2除法去除4位CRC碼，生成多項(xiàng)式G(x)=x4+x+1［15］，并求得4位CRC碼，這樣每個(gè)標(biāo)簽所在組即被唯一確定.4位CRC碼值可表示的范圍是0～15，所以所有的標(biāo)簽被分配到16個(gè)組中.

在識(shí)別過程中每個(gè)組有2n(2≤n≤l/2)個(gè)時(shí)隙供標(biāo)簽進(jìn)行選擇，其中n的值取決于每次輪詢結(jié)束后沖突時(shí)隙、空時(shí)隙和成功讀取時(shí)隙的統(tǒng)計(jì)結(jié)果.標(biāo)簽采用偽隨機(jī)數(shù)生成(PRNG)算法生成一個(gè)隨機(jī)數(shù)作為該標(biāo)簽選擇的時(shí)隙號(hào)碼.但要求RNG生成的隨機(jī)數(shù)序列是均勻分布的，以保證標(biāo)簽不會(huì)過度集中地選擇某個(gè)時(shí)隙.線性同余算法是一種簡(jiǎn)單可行的隨機(jī)數(shù)生成算法，在參數(shù)正確設(shè)置的前提下，它所產(chǎn)生的隨機(jī)序列分布均勻，其形式如下:

式中:r為隨機(jī)數(shù);I為隨機(jī)算法的種子;λ為整數(shù)乘子;c為整數(shù)常量;m為每次輪詢的時(shí)隙總數(shù)，m=2n.由文獻(xiàn)［16-19］可知，式(1)中的參數(shù)按如下設(shè)置時(shí)所產(chǎn)生的隨機(jī)序列具有很好的分布性:(a)λ和m互為質(zhì)數(shù);(b)如果λ-1是質(zhì)數(shù)p的倍數(shù)，那么p是λ-1和m的公約數(shù).

由于標(biāo)簽采用線性同余的方法產(chǎn)生一個(gè)隨機(jī)數(shù)作為時(shí)隙號(hào)碼，而不是產(chǎn)生一個(gè)序列，因此種子I決定了每組中標(biāo)簽選擇時(shí)隙的分布情況.從式(1)可知，當(dāng)兩個(gè)標(biāo)簽選擇的種子相同時(shí)，生成的時(shí)隙號(hào)碼是相同的.文中采用標(biāo)簽序號(hào)作為隨機(jī)算法的種子源，其中s表示種子位數(shù)，s等于本次輪詢時(shí)隙總數(shù)2n的冪，則取種子步驟如下:

1)第1次輪詢時(shí)，直接取標(biāo)簽序號(hào)的后s位作為種子;

2)在第k次輪詢時(shí)，按順序從后向前取k串s位的子串，將這k串子串的異或值作為種子;

3)若k-1，則按第1次輪詢時(shí)的方法取種子.

1.3 輪詢識(shí)別過程

閱讀器中設(shè)置3個(gè)計(jì)數(shù)器，分別記錄沒有被選中的時(shí)隙(es計(jì)數(shù)器)、成功讀取的時(shí)隙(ss計(jì)數(shù)器)、發(fā)生沖突的時(shí)隙(cs計(jì)數(shù)器).在輪詢之前，3個(gè)計(jì)數(shù)器均初始化為0，當(dāng)一次輪詢結(jié)束后，閱讀器可以根據(jù)這3個(gè)計(jì)數(shù)器的情況判斷是否將當(dāng)前組內(nèi)的標(biāo)簽讀取完畢，以及是否調(diào)整下一輪輪詢中標(biāo)簽的可選擇時(shí)隙范圍.

在標(biāo)簽選擇完時(shí)隙后，閱讀器開始對(duì)這一組的2n個(gè)時(shí)隙進(jìn)行輪詢識(shí)別.當(dāng)有標(biāo)簽選擇的時(shí)隙與其它標(biāo)簽相同時(shí)，碰撞就會(huì)發(fā)生，此時(shí)閱讀器不作處理，繼續(xù)識(shí)別后面的時(shí)隙.所有2n個(gè)時(shí)隙識(shí)別完畢后，若有碰撞發(fā)生，則請(qǐng)求標(biāo)簽重新計(jì)算種子，然后開始下一次輪詢.一次輪詢算法的步驟如下:

1)發(fā)送REQ_Query請(qǐng)求，其中包括閱讀器所要讀取的時(shí)隙號(hào)碼.

2)如果收到ACK_Query響應(yīng)且沒有沖突發(fā)生，則讀取成功，轉(zhuǎn)步驟3);如果收到ACK_Query響應(yīng)且有沖突發(fā)生，則轉(zhuǎn)步驟4);如果沒有任何響應(yīng)，表明該時(shí)隙沒有標(biāo)簽被選中，則es計(jì)數(shù)器(空時(shí)隙計(jì)數(shù)器)加1，轉(zhuǎn)步驟5).

3)發(fā)送REQ_Kill請(qǐng)求，將被成功讀取的標(biāo)簽鎖死，ss計(jì)數(shù)器(獨(dú)占時(shí)隙計(jì)數(shù)器)加1，轉(zhuǎn)步驟5).

4)cs計(jì)數(shù)器(沖突時(shí)隙計(jì)數(shù)器)加1.

5)閱讀器中時(shí)隙計(jì)數(shù)器加1，準(zhǔn)備讀取下一個(gè)時(shí)隙，返回步驟1).

一次輪詢識(shí)別結(jié)束后，閱讀器根據(jù)3個(gè)計(jì)數(shù)器的結(jié)果進(jìn)行估計(jì)判定，調(diào)整時(shí)隙總數(shù)，然后讀取該組剩下的標(biāo)簽，判定準(zhǔn)則如下:

1)如果cs計(jì)數(shù)器為0，則表示當(dāng)前這一組所有標(biāo)簽讀取完畢，準(zhǔn)備讀取下一組標(biāo)簽.

2)如果cs計(jì)數(shù)器不為0，有以下2種情況，其中r表示上一次輪詢的時(shí)隙總數(shù).

(a)當(dāng)es=0時(shí)，若cs＞ss，則表明沖突嚴(yán)重，若n=32則時(shí)隙總數(shù)保持不變，否則在下一次輪詢時(shí)時(shí)隙總數(shù)設(shè)為2n+1;若cs≤r/2，則時(shí)隙總數(shù)保持不變.

(b)當(dāng)es≠0時(shí)，若cs＞es+ss，則時(shí)隙總數(shù)保持不變;若cs≤r/2且n=2，則時(shí)隙總數(shù)保持不變，否則時(shí)隙總數(shù)設(shè)為2n-1.

算法分組過程如圖2所示.兩種準(zhǔn)則分別根據(jù)碰撞情況調(diào)整時(shí)隙總數(shù)，從而提高系統(tǒng)的識(shí)別效率.

圖2 分組示意圖Fig.2 Schematic diagram of splitting

2 算法分析

文中算法最關(guān)鍵的兩個(gè)步驟是標(biāo)簽分組和時(shí)隙選擇，因?yàn)樗惴ㄊ腔跇?biāo)簽自身攜帶的信息進(jìn)行劃分的，而所有的信息是不可預(yù)知的，那么所有的標(biāo)簽是否可以利用CRC碼進(jìn)行分組?在每個(gè)小組中標(biāo)簽是采用線性同余法選擇時(shí)隙，是否會(huì)出現(xiàn)某個(gè)時(shí)隙無限重復(fù)被選的情況?文中分別討論這兩個(gè)問題.

2.1 分組效率問題

文中討論分組識(shí)別算法時(shí)，以標(biāo)簽中攜帶16位CRC碼為例，利用生成多項(xiàng)式G(x)=x4+x+1產(chǎn)生4位CRC碼.

隨機(jī)均勻地產(chǎn)生t個(gè)標(biāo)簽，令X1，X2，…，Xt分別表示它們所攜帶的16位CRC碼，則Xi∈{0，1，…，216-1}，i=1，2，…，t，且Xi以等概率取值.令RXi表示Xi對(duì)G(x)求模取得的余數(shù)，則RXi∈{0，1，…，24-1}，且以等概率取值.在算法中，RXi是各個(gè)標(biāo)簽的分組號(hào)，因此各個(gè)標(biāo)簽被分配到16個(gè)組中，且被分配到其中一個(gè)組的概率相同.可見文中算法可以將所要識(shí)別的標(biāo)簽相對(duì)均勻地分配到16個(gè)組中.

分組過程是在標(biāo)簽接收到閱讀器的分組命令后開始的.所有的標(biāo)簽接收到閱讀器的分組命令后，同時(shí)開始進(jìn)行除法運(yùn)算產(chǎn)生分組號(hào)，因此所有標(biāo)簽的分組過程所消耗的時(shí)間等于一個(gè)標(biāo)簽進(jìn)行除法運(yùn)算的時(shí)間，即分組過程的算法復(fù)雜度相當(dāng)于一次除法運(yùn)算的算法復(fù)雜度.求取CRC的移位除法運(yùn)算的復(fù)雜度為O(d)，即分組過程的復(fù)雜度為O(d)［15］，其中d為被除數(shù)的位數(shù)，在分組過程中用16位CRC產(chǎn)生4位CRC碼，因此d為16.

2.2 時(shí)隙分配問題

由式(1)可知，若參數(shù)確定，線性同余算法產(chǎn)生的隨機(jī)數(shù)是由種子I確定的，并且若I是周期m內(nèi)的一個(gè)整數(shù)，那么產(chǎn)生的隨機(jī)數(shù)是由種子唯一確定的.也就是說，假如一個(gè)標(biāo)簽采用的種子與其它標(biāo)簽不同，則該標(biāo)簽占用的時(shí)隙也與其它標(biāo)簽不同.假設(shè)第k次輪詢時(shí)種子位數(shù)為s位，那么第k次輪詢的種子是標(biāo)簽序號(hào)中從后向前取k個(gè)s位長(zhǎng)的子串的異或值.

設(shè)X1和X2分別表示同一組中任意兩個(gè)標(biāo)簽的l位長(zhǎng)的序號(hào)(由0、1組成的混合序列)，且X1≠X2，S1和S2分別是它們的種子，位數(shù)為s.設(shè)這兩個(gè)標(biāo)簽的序號(hào)具有以下形式:

其中“×”表示一個(gè)s位子串，共有?l/s」個(gè)子串.X1中第i-1和i個(gè)子串分別是a和b，X2中第i-1和i個(gè)子串分別是c和d.若在前i次輪詢中這兩個(gè)標(biāo)簽產(chǎn)生的種子一樣，由式(2)可知，X1和X2的前i個(gè)s位子串必是式(3)-(6)所示的4種形式之一，其中設(shè)兩個(gè)標(biāo)簽的后l-si位任意取值，令和分別表示兩個(gè)標(biāo)簽的第j個(gè)s位子串表示對(duì)子串求反，P(i)表示第i(i=1，2，3，4)種情況的概率.

當(dāng)i=n/l時(shí)，第2種情況中X1=X2，由于序號(hào)的唯一性，所以第2種情況不會(huì)導(dǎo)致兩個(gè)標(biāo)簽無限地產(chǎn)生同樣的種子;在第3和第4種情況中，由于只有當(dāng)i為偶數(shù)時(shí)才有，當(dāng)i為奇數(shù)時(shí)兩個(gè)標(biāo)簽不會(huì)沖突，所以也不會(huì)導(dǎo)致兩個(gè)標(biāo)簽始終產(chǎn)生同樣的種子.

對(duì)于第1種情況，當(dāng)i=l時(shí)，標(biāo)簽的兩個(gè)序號(hào)且X1≠X2.由于第1次輪詢是直接取序號(hào)的后s位作為種子，若第1次輪詢時(shí)這兩個(gè)標(biāo)簽均不能被識(shí)別，則由式(2)可以知道在后續(xù)的輪詢中這兩個(gè)標(biāo)簽產(chǎn)生的種子是一樣的，出現(xiàn)無限選擇同一時(shí)隙的情況，那么對(duì)于任意兩個(gè)標(biāo)簽序號(hào)其不能被識(shí)別的概率為

文中是假設(shè)標(biāo)簽序號(hào)為32位進(jìn)行討論的，則PX1=ˉX2=2-32.在現(xiàn)有的RFID標(biāo)準(zhǔn)中標(biāo)簽大多采用64位或更高的序號(hào)，因此不能被識(shí)別的概率更低.可以通過減少有效射頻范圍內(nèi)標(biāo)簽數(shù)量的方法來避免標(biāo)簽無法被識(shí)別的情況發(fā)生.

3 仿真實(shí)驗(yàn)

是否可以識(shí)別所有的標(biāo)簽和識(shí)別的快慢是判斷算法好壞的兩個(gè)關(guān)鍵指標(biāo).由于仿真環(huán)境與真實(shí)的識(shí)別環(huán)境有區(qū)別，所以文中將識(shí)別過程中閱讀器與標(biāo)簽之間發(fā)送、接收的命令數(shù)量作為判斷算法識(shí)別效率的依據(jù).文中算法利用16位的CRC碼進(jìn)行分組識(shí)別，因此在仿真過程中主要是利用隨機(jī)算法產(chǎn)生均勻分布的16位數(shù)據(jù)來模擬標(biāo)簽中的16位CRC碼.仿真用14組標(biāo)簽數(shù)據(jù)，標(biāo)簽數(shù)量逐步增加，每組標(biāo)簽數(shù)量為100k'，k'為組號(hào).王鋮岑［5］和江岸等［7］已對(duì)ALOHA算法和二叉樹算法的性能進(jìn)行了比較，結(jié)果表明二叉樹算法優(yōu)于ALOHA算法，因此僅將文中算法與二叉樹算法的性能進(jìn)行對(duì)比.

從1.3節(jié)的算法步驟可知，時(shí)隙分配時(shí)初始的時(shí)隙數(shù)為2n(n與標(biāo)簽ID有關(guān))，在識(shí)別過程中每次輪詢結(jié)束后，閱讀器會(huì)根據(jù)3個(gè)計(jì)數(shù)器(es，ss，cs)來調(diào)整時(shí)隙數(shù)，那么在第1次輪詢時(shí)的初始時(shí)隙數(shù)(即最小時(shí)隙)會(huì)影響算法的識(shí)別效率:若最小時(shí)隙設(shè)置偏小，則當(dāng)標(biāo)簽數(shù)量較多時(shí)沖突時(shí)隙出現(xiàn)的概率較大，增加輪詢的次數(shù)而消耗更多的時(shí)間;若最小時(shí)隙設(shè)置偏大，則當(dāng)標(biāo)簽數(shù)量較少時(shí)空置時(shí)隙出現(xiàn)的概率較大，降低了算法的識(shí)別效率.文中仿真使用的數(shù)據(jù)標(biāo)簽最大達(dá)到1400個(gè)，若設(shè)置很大的初始時(shí)隙勢(shì)必造成更多的空閑時(shí)隙，因此最大初始時(shí)隙設(shè)為64.文中利用上述14組標(biāo)簽數(shù)據(jù)對(duì)最小時(shí)隙為4、8、16、32、64時(shí)的5種情況分別進(jìn)行仿真計(jì)算，結(jié)果如圖3所示.

從圖3中可以看到，當(dāng)標(biāo)簽數(shù)量較少時(shí)，最小時(shí)隙較小的識(shí)別過程識(shí)別的速度較快，這是因?yàn)樵跇?biāo)簽數(shù)量較少而最小時(shí)隙較大時(shí)，空時(shí)隙的數(shù)量會(huì)比較多，此時(shí)算法在空時(shí)隙上會(huì)花費(fèi)較多的時(shí)間.隨著標(biāo)簽數(shù)量的增多，碰撞發(fā)生的概率也隨之增加，所以最小時(shí)隙較小的識(shí)別過程會(huì)越來越慢.當(dāng)標(biāo)簽數(shù)量增加到一定程度時(shí)，最小時(shí)隙大的識(shí)別過程明顯地比最小時(shí)隙小的識(shí)別過程要快很多.Deng等［9］也指出了類似的情況，即在時(shí)隙數(shù)量較少時(shí)，隨著標(biāo)簽的增加，折線發(fā)散得較快，因此在算法應(yīng)用中可以根據(jù)實(shí)際情況設(shè)定最小時(shí)隙.從圖3中還可以看到，不同的最小時(shí)隙需要幾乎相同的命令數(shù)量，如在標(biāo)簽數(shù)量達(dá)到600時(shí)，最小時(shí)隙4和最小時(shí)隙8的命令數(shù)量相當(dāng).這可能是標(biāo)簽在每次輪詢前選擇時(shí)隙后空時(shí)隙或沖突時(shí)隙較多，算法不斷調(diào)整時(shí)隙總數(shù)，導(dǎo)致命令數(shù)量增加.

圖3 不同最小時(shí)隙下文中算法的仿真結(jié)果比較Fig.3 Comparison of simulation results obtained by proposed algorithm with differentminimum slots

綜上所述，當(dāng)需要識(shí)別的標(biāo)簽較多時(shí)，可以增大最小時(shí)隙;當(dāng)標(biāo)簽較少時(shí)，可以減小最小時(shí)隙以提高識(shí)別效率.

以相同的標(biāo)簽數(shù)據(jù)對(duì)二叉樹算法和文中算法進(jìn)行仿真，結(jié)果如圖4所示.其中二叉樹算法的實(shí)驗(yàn)結(jié)果是多次仿真結(jié)果的平均值;文中算法的結(jié)果是5種初始時(shí)隙實(shí)驗(yàn)中識(shí)別效率取得較好時(shí)的實(shí)驗(yàn)結(jié)果.從圖4中可知，二叉樹算法的識(shí)別速率隨著標(biāo)簽數(shù)量的增加呈近似線性的上升，而在同樣測(cè)試數(shù)據(jù)的前提下文中算法的識(shí)別速率比二叉樹算法快.

圖4 二叉樹算法與文中算法的仿真結(jié)果對(duì)比Fig.4 Comparison of simulation results between proposed algorithm and binary-tree algorithm

4 結(jié)語

文中提出了一種基于標(biāo)簽信息分組的射頻識(shí)別防碰撞算法，將標(biāo)簽分成多個(gè)組，然后按組的順序依次識(shí)別這些標(biāo)簽，以減少同一時(shí)刻響應(yīng)閱讀器請(qǐng)求的標(biāo)簽數(shù)量，從而降低碰撞發(fā)生的概率.算法中分組和時(shí)隙選擇是最關(guān)鍵的兩個(gè)因素，文中對(duì)這兩個(gè)因素從理論上進(jìn)行了證明，結(jié)果表明:標(biāo)簽?zāi)軌蛳鄬?duì)均勻地分到各組中，從而保證了分組效率;標(biāo)簽在時(shí)隙選擇上也相對(duì)分散，不會(huì)過度集中到其中一些時(shí)隙上;算法能夠根據(jù)前一輪的輪詢結(jié)果自適應(yīng)地調(diào)整可選擇時(shí)隙的范圍.仿真實(shí)驗(yàn)結(jié)果表明:當(dāng)標(biāo)簽總量較少、初始時(shí)隙范圍較小時(shí)，算法性能較優(yōu)，但隨著標(biāo)簽數(shù)量的增加，初始時(shí)隙的范圍越大越好;文中算法的性能要優(yōu)于二叉樹算法.從仿真結(jié)果看，文中算法具有一定的分組識(shí)別效率，但不是十分明顯，從算法的結(jié)構(gòu)看還有可以優(yōu)化的空間，即輪詢結(jié)束后，如果算法能更好地調(diào)整時(shí)隙選擇范圍，那么算法的分組識(shí)別效率會(huì)更優(yōu).今后將采用優(yōu)化理論對(duì)算法進(jìn)行優(yōu)化，進(jìn)一步分析文中算法的分組效率和識(shí)別性能，使其性能能夠達(dá)到最優(yōu).

［1］Sarma S，Brock D，Engels D.Radio frequency identification and the electronic product code［J］.IEEE Micro，2001，21(6):50-54.

［2］Jihoon Myung，Lee Wonjun.Adaptive binary splitting:a RFID tag collision arbitration protocol for tag identification［J］.Communications Letters，2006，10(3):144-146.

［3］Waldrop J，Engels D，Sarma S.Colorwave:an anti-collision algorithm for the reader collision problem［C］∥Proceedings of IEEE International Conference on Communications.Anchorage:IEEE，2003:1206-1210.

［4］EPGglobal Inc.EPCTMradio-frequency identification protocols class-1 generation-2 UHF RFID protocol for communications at860MHz-960MHz Version 1.0.9［S］.

［5］王鋮岑.RFID系統(tǒng)防碰撞算法［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2010，20(1):29-32，35.Wang Cheng-cen.Anti-collision algorithm on RFID system［J］.Computer Technology and Development，2010，20(1):29-32，35.

［6］Cha Jae-ryong，Kim Jae-hyun.Dynamic framed slotted ALOHA algorithms using fast tag estimation method for RFID system［C］∥Proceedings of IEEE Consumer Communications and Networking Conference.Las Vegas:IEEE，2006:768-772.

［7］江岸，伍繼雄，黃生葉，等.改進(jìn)的RFID二進(jìn)制搜索防碰撞算法［J］.計(jì)算機(jī)工程與應(yīng)用，2009，45(5):229-235.Jiang An，Wu Ji-xiong，Huang Sheng-ye，et al.Improved RFID binary search anti-collision algorithm［J］.Computer Engineering and Applications，2009，45(5):229-235.

［8］Hush Don R，Wood Cliff.Analysis of tree algorithms for RFID arbitration［C］∥Proceedings of IEEE International Symposium on Information Theory.Cambridge:IEEE，1998:107.

［9］Deng Huifang，Liu Jinqiao，Deng Chunhui，et al.RFID multi-tags anti-collision algorithm with adaptive Q leading to the maximum throughput［C］∥Proceedings of the Third Pacific-Asia Conference on Web Mining and Webbased Application.Guilin:IEEE，2010:166-169.

［10］萬紅，楊延昭.RFID防碰撞算法研究與改進(jìn)［J］.微計(jì)算機(jī)信息，2009，25(2/3):230-232.Wan Hong，Yang Yan-zhao.Research and improvement on anti-collision algorithm for RFID system［J］.Microcomputer Information，2009，25(2/3):230-232.

［11］武強(qiáng)，李宏生，楊宇，等.UHF RFID系統(tǒng)防碰撞算法研究［J］.儀表技術(shù)，2008(2):16-18，20.Wu Qiang，Li Hong-sheng，Yang Yu，et al.Research on anti-collision algorithm of UHF RFID system［J］.Instrumentation Technology，2008(2):16-18，20.

［12］鄧輝舫，劉金橋.RFID系統(tǒng)防碰撞中的二進(jìn)制矩陣搜索［J］.微計(jì)算機(jī)信息，2009，25(10-2):4-5，3.Deng Hui-fang，Liu Jin-qiao.Binary-matrix search in anticollision of RFID system［J］.Micro-computer Information，2009，25(10-2):4-5，3.

［13］Wang Chun-yi，Lee Chi-chung.A grouping-based dynamic framed slotted ALOHA anti-collision method with fine groups in RFID systems［C］∥Proceedings of the 5th International Conference on Future Information Technology.Busan:IEEE，2010:1-5.

［14］ISO/IEC FDIS 18000-6，Information technology automatic identification and data capture techniques—radio frequency identification for item management air interface—part6:parameters for air interface communications at860-960MHz［S］.

［15］Tanenbaurn A S.計(jì)算機(jī)網(wǎng)絡(luò)［M］.熊桂喜，王小虎，譯.3版.北京:清華大學(xué)出版社，1997:137-142.

［16］Rotenberg A.A new pseudo-random number generator［J］.Journal of the ACM，1960，7(1):75-77.

［17］Covyou R R.Serial correlation in the generation of pseudo-random numbers［J］.Journal of the ACM，1960，7(1):72-74.

［18］Gereenberger M.Notes on a new pseudo-random number generator［J］.Journal of the ACM，1961，8(2):163-167.

［19］ITU recommendation G.704，Synchronous frame structures used at primary and secondary hierarchical［S］.