[發(fā)明專利]一種用于RFID系統(tǒng)中的基于分組動(dòng)態(tài)幀及二叉樹搜索的多標(biāo)簽防碰撞方法

無效

• 申請?zhí)枺?/td>: 200810218611.8
• 申請日: 2008-10-24
• 公開（公告）號(hào): CN101393594A
• 公開（公告）日: 2009-03-25
• 發(fā)明（設(shè)計(jì)）人: 詹宜巨;楊健;蔡慶玲;王永華
• 申請（專利權(quán)）人: 中山大學(xué)
• 主分類號(hào): G06K7/00
• 分類號(hào): G06K7/00
• 代理公司: 廣州知友專利商標(biāo)代理有限公司
• 代理人: 李海波

技術(shù)領(lǐng)域

本發(fā)明涉及一種應(yīng)用于射頻識(shí)別(RFID)系統(tǒng)中的防碰撞方法，尤其涉及一種用于RIFD系統(tǒng)中的基于分組動(dòng)態(tài)幀及二叉樹搜索的多標(biāo)簽防碰撞方法。

背景技術(shù)

射頻識(shí)別(Radio?Frequency?Identification，RFID)是一種具有實(shí)時(shí)、快速、準(zhǔn)確采集等特點(diǎn)的自動(dòng)識(shí)別技術(shù)。RFID系統(tǒng)由讀寫器、標(biāo)簽和應(yīng)用程序三部分組成，讀寫器和標(biāo)簽之間采用非接觸方式通信。標(biāo)簽有主動(dòng)、半主動(dòng)和被動(dòng)三種，其中被動(dòng)標(biāo)簽由于其結(jié)構(gòu)簡單，成本較低，因而被廣泛應(yīng)用。

由于被動(dòng)標(biāo)簽結(jié)構(gòu)的簡單性，標(biāo)簽在接到讀寫器指令后會(huì)立即響應(yīng)讀寫器。但是當(dāng)多個(gè)標(biāo)簽同時(shí)響應(yīng)某個(gè)讀寫器時(shí)，標(biāo)簽數(shù)據(jù)間的相互干擾會(huì)導(dǎo)致讀寫器無法正常讀取任何一個(gè)標(biāo)簽數(shù)據(jù)，即發(fā)生所謂的標(biāo)簽沖突。傳統(tǒng)的標(biāo)簽防碰撞算法可分為ALOHA算法和樹形算法兩大類。ALOHA算法的復(fù)雜度較小，而樹形算法則相對較大。這兩種算法都存在各自的問題：ALOHA算法雖然復(fù)雜度及對標(biāo)簽的要求較低，但存在標(biāo)簽始終無法識(shí)別的可能，并且在標(biāo)簽數(shù)量龐大時(shí)算法的性能不佳，這是由于標(biāo)簽內(nèi)部寄存器的位數(shù)是有限而導(dǎo)致的；樹形算法的優(yōu)點(diǎn)是識(shí)別率可達(dá)100％，但是以增加算法的復(fù)雜度為代價(jià)的，這增加了讀寫器功耗并且減小了標(biāo)簽最大可識(shí)別距離。此外，這兩種算法還都存在著時(shí)隙浪費(fèi)的現(xiàn)象：ALOHA算法在識(shí)別過程后期存在大量的空閑時(shí)隙浪費(fèi)，這是由于幀長或分組數(shù)不能在識(shí)別過程中隨著標(biāo)簽的識(shí)別實(shí)時(shí)調(diào)整造成的；樹形算法在識(shí)別過程前期因同時(shí)響應(yīng)讀寫器的標(biāo)簽較多而導(dǎo)致碰撞時(shí)隙較多，而其中的查詢樹算法的性能還受到標(biāo)簽ID分布情況的影響較大。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種用于RFID系統(tǒng)中的基于分組動(dòng)態(tài)幀及二叉樹搜索的多標(biāo)簽防碰撞方法，該方法可以有效避免標(biāo)簽數(shù)據(jù)發(fā)生的碰撞次數(shù)，并且較大程度的降低識(shí)別時(shí)間和功耗。

為達(dá)上述目的，本發(fā)明通過采取以下技術(shù)方案予以實(shí)現(xiàn)：

一種用于RFID系統(tǒng)中的基于分組動(dòng)態(tài)幀及二叉樹搜索的多標(biāo)簽防碰撞方法，包括如下步驟：

(1)讀寫器對未識(shí)別標(biāo)簽數(shù)量進(jìn)行估計(jì)，并計(jì)算該標(biāo)簽數(shù)量下的最優(yōu)分組數(shù)和最優(yōu)幀長：首先，讀寫器設(shè)置初始分組和初始幀長，將標(biāo)簽隨機(jī)分到所設(shè)的若干組內(nèi)，每組的幀長為所設(shè)長度(即每組的幀周期包含的時(shí)隙數(shù)量)；然后，讀寫器依次將所有分組幀周期的時(shí)隙輪詢一遍，并統(tǒng)計(jì)空閑時(shí)隙、單標(biāo)簽時(shí)隙和碰撞時(shí)隙的數(shù)量，據(jù)此估計(jì)未識(shí)別標(biāo)簽的數(shù)量，并計(jì)算出該標(biāo)簽數(shù)量下的最優(yōu)分組數(shù)和最優(yōu)幀長；

(2)讀寫器以最優(yōu)分組數(shù)和最優(yōu)幀長為參數(shù)開始新一輪輪詢，依次對當(dāng)前組幀周期的每個(gè)時(shí)隙內(nèi)的標(biāo)簽進(jìn)行識(shí)別：讀寫器按最優(yōu)分組將未識(shí)別標(biāo)簽重新隨機(jī)分組，每組的幀周期長度為最優(yōu)幀長，開始輪詢后，讀寫器對每個(gè)時(shí)隙狀態(tài)進(jìn)行判斷，若為空閑時(shí)隙，則直接進(jìn)入下一時(shí)隙，若為單標(biāo)簽時(shí)隙，則識(shí)別該標(biāo)簽，然后進(jìn)入下一時(shí)隙，若為碰撞時(shí)隙，則采用二叉樹搜索識(shí)別出該碰撞時(shí)隙內(nèi)所有的標(biāo)簽，然后進(jìn)入下一時(shí)隙，直到當(dāng)前組幀周期結(jié)束；

(3)讀寫器將最優(yōu)分組數(shù)遞減1，并以最優(yōu)幀長和更新后的最優(yōu)分組數(shù)開始新一輪輪詢，依次對當(dāng)前組幀周期的每個(gè)時(shí)隙內(nèi)的標(biāo)簽進(jìn)行識(shí)別，直到最優(yōu)分組數(shù)遞減至0。

步驟(1)中所述的標(biāo)簽按讀寫器對未識(shí)別標(biāo)簽數(shù)量進(jìn)行估計(jì)后計(jì)算出的該標(biāo)簽數(shù)量下的最優(yōu)分組數(shù)進(jìn)行分組的具體過程為：讀寫器將所設(shè)分組數(shù)、所設(shè)幀長和一個(gè)隨機(jī)數(shù)插入到修改指令，并發(fā)送給標(biāo)簽，收到該指令后，標(biāo)簽根據(jù)該指令中的隨機(jī)數(shù)和標(biāo)簽ID產(chǎn)生一新的隨機(jī)數(shù)，并將其對指令中的分組數(shù)取余，只有余數(shù)為0的標(biāo)簽才在當(dāng)前組的幀周期內(nèi)活動(dòng)，從而實(shí)現(xiàn)標(biāo)簽的分組；標(biāo)簽還根據(jù)該指令中的所設(shè)幀長隨機(jī)產(chǎn)生一不大于該幀長的正整數(shù)作為標(biāo)簽所屬時(shí)隙存儲(chǔ)，只有輪詢到該時(shí)隙時(shí)，該標(biāo)簽才允許響應(yīng)讀寫器。

步驟(1)中所述的未識(shí)別標(biāo)簽數(shù)量的估計(jì)的具體過程為：計(jì)算出當(dāng)前幀長、不同標(biāo)簽數(shù)量下，空時(shí)隙數(shù)、單標(biāo)簽的時(shí)隙數(shù)和碰撞時(shí)隙數(shù)的期望值，與相應(yīng)統(tǒng)計(jì)值距離最近時(shí)的標(biāo)簽數(shù)量即被認(rèn)為是識(shí)別過程開始時(shí)的未識(shí)別標(biāo)簽的數(shù)量，減去單標(biāo)簽時(shí)隙計(jì)數(shù)便是當(dāng)前未識(shí)別標(biāo)簽的數(shù)量。

步驟(1)中所述的計(jì)算最優(yōu)分組數(shù)和最優(yōu)幀長的具體過程為：當(dāng)未識(shí)別標(biāo)簽數(shù)量不大于最大幀長時(shí)，設(shè)置幀長等于未識(shí)別標(biāo)簽數(shù)量，并設(shè)置分組數(shù)為1；當(dāng)未識(shí)別標(biāo)簽數(shù)量大于最大幀長時(shí)，將標(biāo)簽分組且每組幀長等于最大幀長，其中分組數(shù)采取倍增或減半的更改方式，且由k＝n_k/354決定，其中分組數(shù)k取大于0的整數(shù)，n_k為該分組數(shù)下的標(biāo)簽數(shù)量的上限。

步驟(2)中所述的碰撞時(shí)隙內(nèi)的二叉樹搜索識(shí)別的主要步驟為：