タグを認識する方法及びこれを用いたＲＦＩＤタグ
【課題】ＲＦＩＤシステムにおいてタグ認識方法を提供する。
【解決手段】ＲＦＩＤリーダとタグ間のクエリ応答に応じてクエリツリーを生成して上記タグを認識するタグ認識方法は、上記ＲＦＩＤリーダが上記タグでクエリメッセージを伝送する段階、及び上記タグから上記クエリメッセージに対する応答メッセージを受信する段階を含み、上記タグが有する文字列（ｓｔｒｉｎｇ）の逆順に上記クエリツリーを生成する。クエリツリー基盤プロトコルにおいてタグが有するＩＤに対して逆順にクエリツリーを生成してタグ間の衝突回数を減らしてＲＦＩＤリーダの認識領域内の全てのタグを認識するときにかかる時間を短縮させることができる。
【解決手段】ＲＦＩＤリーダとタグ間のクエリ応答に応じてクエリツリーを生成して上記タグを認識するタグ認識方法は、上記ＲＦＩＤリーダが上記タグでクエリメッセージを伝送する段階、及び上記タグから上記クエリメッセージに対する応答メッセージを受信する段階を含み、上記タグが有する文字列（ｓｔｒｉｎｇ）の逆順に上記クエリツリーを生成する。クエリツリー基盤プロトコルにおいてタグが有するＩＤに対して逆順にクエリツリーを生成してタグ間の衝突回数を減らしてＲＦＩＤリーダの認識領域内の全てのタグを認識するときにかかる時間を短縮させることができる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＲＦＩＤタグに関し、より詳しくは、タグ間の衝突を防止してタグを認識する方法及びこれを用いたＲＦＩＤタグに関する。
【背景技術】
【０００２】
ＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）技術は、非接触無線認識技術であって、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）チップと無線通信のためのアンテナを内蔵したタグ（ｔａｇ）に必要な情報を格納し、タグの情報を収集できるＲＦＩＤリーダ（ｒｅａｄｅｒ）がラジオ周波数帯域を介してタグと通信する技術である。
【０００３】
ＲＦＩＤ技術はバーコード方式に比べて多様な長所を有している。
第一に、タグはバーコードのように表面に印刷する必要がないため、汚染に対する心配がない。第二に、ＲＦＩＤ技術は、無線通信を使用するため、タグをＲＦＩＤリーダに一つずつ近接させなくてもよい。第三に、ＲＦＩＤ技術は、多重認識技術を提供するため、短い時間に多数のタグ情報を認識できる。第四に、単純な識別コードだけが印刷されるバーコードとは違ってタグには多量の情報を入力することができる。第五に、バーコード方式は、同じ種類の製品に同じ識別コードを使用するが、ＲＦＩＤ技術は各々の製品ごとに固有な識別コードを使用することができるため、製品販売や在庫管理の側面で正確且つ迅速な管理を行うことができる。
【０００４】
ＲＦＩＤリーダは、無線通信環境で多数のタグ情報を認識しなければならず、この過程で多数のタグ間の衝突（ｃｏｌｌｉｓｉｏｎ）問題が発生する。タグはＲＦＩＤリーダから受けたクエリ（ｑｕｅｒｙ）に対応する情報を報告しなければならず、タグは現在の無線チャネルの使用状態を確認できる機能がない。また、多数のタグは無線チャネルを共有するため、一つ以上のタグがＲＦＩＤリーダに同時にデータを伝送でき、同じチャネルを介して多数のタグから同時にデータが伝送されれば、ＲＦＩＤリーダはタグ情報を認識できない。これをＲＦＩＤシステムにおいてタグ間衝突といい、衝突を防止するためのＲＦＩＤリーダとタグ間のプロトコルを衝突防止（ａｎｔｉ-ｃｏｌｌｉｓｉｏｎ）プロトコルという。
【０００５】
衝突防止プロトコルは、大きくアロハ(ＡＬＯＨＡ)基盤プロトコル及びツリー（ｔｒｅｅ）基盤プロトコルに分かれる。アロハ基盤プロトコルは、時間をスロット単位に分けて一つの時間スロットに一つのタグだけが無作為で応答するようにして、ＲＦＩＤリーダがタグを認識するようにするプロトコルである。アロハ基盤プロトコルは、無作為という確率の不確実性に基礎をおいているため、ＲＦＩＤリーダが全てのタグを認識できないこともあって、全てのタグを認識するのにかかる時間を予測するのは難しい。
【０００６】
ツリー基盤プロトコルは、タグの固有なＩＤを使用してタグ認識過程を進行しつつツリーを作るプロトコルである。ツリー基盤プロトコルを使用するＲＦＩＤリーダは、全てのタグを認識でき、その過程を予測できるのに対し、類似のＩＤを有したタグが多い場合、ツリーを生成する間、衝突が頻繁に発生し、これに伴ってツリーが深くなってタグを認識する時間が長くかかるという短所がある。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明の解決しようとする技術的課題は、ＲＦＩＤシステムにおいてタグを認識する時間を減らすことができるタグ認識方法、衝突防止方法及びこれを用いたＲＦＩＤタグを提供することである。
【課題を解決するための手段】
【０００８】
本発明の一実施例に係るＲＦＩＤリーダとタグ間のクエリ応答に応じてクエリツリーを生成して上記タグを認識するタグ認識防止方法は、上記ＲＦＩＤリーダが上記タグでクエリメッセージを伝送する段階、及び上記タグから上記クエリメッセージに対する応答メッセージを受信する段階を含み、上記タグが有する文字列（ｓｔｒｉｎｇ）の逆順に上記クエリツリーを生成する。上記クエリメッセージは、上記文字列のサフィックス（ｓｕｆｆｉｘ）である。上記応答メッセージが、他のタグからの応答メッセージと衝突が発生すれば、上記ＲＦＩＤリーダは、上記サフィックスに追加文字を加えた文字列をキュー（ｑｕｅｕｅ）に生成させることができる。上記タグは、上記文字列のＬＳＢ（Ｌｅａｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）への順に上記クエリメッセージと上記文字列を比較して上記応答メッセージを伝送できる。上記タグは、自分のＩＤ（ＩＤｅｎｔｉｆｉｅｒ）に対する逆順ＩＤを生成して上記クエリメッセージと比較できる。
【０００９】
本発明のもう一つの実施例に係るクエリツリープロトコルを用いるＲＦＩＤリーダからのクエリに対して応答するＲＦＩＤタグは、ＲＦＩＤリーダからのクエリメッセージを受信して復調する復調部、タグＩＤを上記クエリメッセージに含まれた文字列と逆順に比較して一致すれば、応答メッセージを生成する制御部、及び上記応答メッセージを変調して伝送する変調部、を含む。上記応答メッセージは上記タグＩＤである。
【００１０】
本発明の他の実施例に係るタグ間の衝突を防止するための衝突防止方法は、タグがＲＦＩＤリーダから第１のサフィックスを受信する段階、上記第１のサフィックスを上記タグのＩＤと逆順に比較して第１の応答メッセージを伝送する段階、上記第１の応答メッセージを伝送した後、上記第１のサフィックスより長い第２のサフィックスを受信する段階、及び上記第２のサフィックスを上記タグのＩＤと逆順に比較して第２の応答メッセージを伝送する段階、を含む。上記第１のサフィックスは、上記タグのＩＤのＬＳＢからｍ番目ビットまでの文字列であり、上記第２のサフィックスは、上記タグのＩＤのＬＳＢからｎ番目ビットまでの文字列である（ｎ＞ｍであり、ｎ、ｍ＞０である整数）。
【発明の効果】
【００１１】
クエリツリー基盤プロトコルにおいてタグが有するＩＤに対して逆順にクエリツリーを生成してタグ間の衝突回数を減らして、ＲＦＩＤリーダの認識領域内の全てのタグを認識するにかかる時間を短縮することができる。
【図面の簡単な説明】
【００１２】
【図１】ＲＦＩＤシステムの一例を示したブロック図である。
【図２】ＲＦＩＤリーダの構成の一例を示したブロック図である。
【図３】タグの構成の一例を示したブロック図である。
【図４】ＲＦＩＤリーダがタグを認識する過程を示した流れ図である。
【図５】本発明の一実施例に係る命令メッセージを示したブロック図である。
【図６】一般的なクエリツリープロトコル（ＱＴ）でクエリツリーの一例を示した例示図である。
【図７】本発明の一実施例に係る逆順クエリツリープロトコル（ＱＴＲ）でクエリツリーを示した例示図である。
【図８】一般的なクエリツリープロトコル（ＱＴ）及び逆順クエリツリープロトコル（ＱＴＲ）でクエリメッセージの伝送回数を示したグラフである。
【図９】一般的なクエリツリープロトコル（ＱＴ）及び逆順クエリツリープロトコル（ＱＴＲ）で伝送されるビット数を示したグラフである。
【発明を実施するための形態】
【００１３】
図１は、ＲＦＩＤシステムの一例を示したブロック図である。
図１を参照すると、ＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）システムは、ＲＦＩＤリーダ（ＲＦＩＤ ｒｅａｄｅｒ；１０）及び少なくとも一つのタグ（ｔａｇ；２０）を含む。タグ（２０）の数には制限がない。
【００１４】
ＲＦＩＤリーダ（１０）は、質問器（ｉｎｔｅｒｒｏｇａｔｏｒ）、タグ認識装置（ｔａｇ ｉｄｅｎｔｉｆｙ ａｐｐａｒａｔｕｓ）、タグ検出器（ｔａｇ ｄｅｔｅｃｔｏｒ）など、他の名称で呼称することができる。ＲＦＩＤリーダ（１０）はタグ（２０）の情報を読み出すためにタグ（２０）と通信する。ＲＦＩＤリーダ（１０）は、データをインコーディングしてラジオチャネルを介してタグ（２０）に伝送し、タグ（２０）から伝送される信号をデコーディングしてタグ（２０）の固有情報を認識する。ＲＦＩＤリーダ（１０）は固定型ＲＦＩＤリーダであってもよく、移動型ＲＦＩＤリーダであってもよい。
【００１５】
タグ（２０）はＩＣ（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）チップとアンテナを含む。タグは固有情報であるＩＤ（ＩＤｅｎｔｉｆｉｅｒ）を有する。ＩＤは二進文字列（ｂｉｎａｒｙ ｓｔｒｉｎｇ）形態で記録されることができる。タグのＩＤは一般的に複数のフィールド（ｆｉｅｌｄ）からなる。例えば、供給業体の特定物品の固有識別番号を表すＥＰＣ（Ｅｌｅｃｔｒｏｎｉｃ Ｐｒｏｄｕｃｔ Ｃｏｄｅ）はヘッダ（ｈｅａｄｅｒ）、会社ＩＤ、製品ＩＤ及びシリアルナンバ（ｓｅｒｉａｌ ｎｕｍｂｅｒ）など、４つのフィールドで構成される。ヘッダはＥＰＣの長さ及び構成を定義して、会社ＩＤは会社ごとに固有番号で決められ、製品ＩＤは会社で製品の種類に応じて固有番号で与えられる。従って、各製品に相異のシリアルナンバが与えられる。即ち、各製品に相異のＥＰＣを有したタグ（２０）が付着されて各製品を区分できる。
【００１６】
タグ（２０）はＲＦＩＤリーダ（１０）からクエリ（ｑｕｅｒｙ）メッセージを受信すれば、固有情報または固有情報から計算した値をＲＦＩＤリーダ（１０）に応答する。タグは、それ自体バッテリーを有する能動型タグ（ａｃｔｉｖｅ ｔａｇ）であってもよく、バッテリーを有しない受動型タグ（ｐａｓｓｉｖｅ ｔａｇ）であってもよい。
【００１７】
ＲＦＩＤリーダ（１０）からタグ（２０）への伝送を伝送リンク（ｆｏｒｗａｒｄ ｌｉｎｋ）といい、タグ（２０）からＲＦＩＤリーダ（１０）への伝送を搬送リンク（ｒｅｔｕｒｎ ｌｉｎｋ）という。ＲＦＩＤリーダ（１０）が伝送リンクで信号を伝送できる範囲は制限され、タグ（２０）が搬送リンクで伝送できる範囲は制限される。ＲＦＩＤリーダ（１０）は、伝送リンクの範囲及び搬送リンクの範囲内にあるタグ（２０）とデータを送受信できる。ＲＦＩＤリーダ（１０）がタグ（２０）とデータを送受信できる範囲をＲＦＩＤリーダ（１０）の認識領域という。
【００１８】
図２は、ＲＦＩＤリーダの構成の一例を示したブロック図である。
図２を参照すると、ＲＦＩＤリーダ（１００）は、アンテナ（１１０）、通信部（１２０）、格納部（１３０）、インターフェース部（１４０）及び制御部（１５０）を含む。
【００１９】
通信部（１２０）は、ＲＦモジュール(不図示)及び変復調モジュール(不図示)を含み、タグと高周波信号で通信を遂行する。ＲＦモジュールは、データ信号を高周波信号に変換してアンテナ（１１０）を介して送信したり、アンテナ（１１０）から受信される高周波信号を一定帯域のデータ信号に変換する。変復調モジュールは、タグで伝送するデータをデータ信号に変調したり、タグから受信されるデータ信号をデータに復調する。
【００２０】
格納部（１３０）はタグの認識のために必要な情報を格納する。格納部（１３０）は、タグから受信したタグＩＤ、タグＩＤに対応する物品情報、各種命令メッセージなどを格納する。
【００２１】
インターフェース部（１４０）は特定インターフェースを含んで外部のシステムとデータを送受信する。インターフェース部（１４０）は、直列通信インターフェース、並列通信インターフェース、ＵＳＢインターフェース、イーサネット（登録商標）インターフェースなどを含むことができる。
【００２２】
制御部（１５０）は、通信部（１２０）、格納部（１３０）、インターフェース部（１４０）を制御する。制御部（１５０）は、タグから受信される信号らの衝突状態を感知し、タグ間の衝突を解決するための多様なプロセッサを遂行する。ツリー基盤プロトコルにおいて制御部（１５０）はツリーを生成して管理する。制御部（１５０）は、キュー（ｑｕｅｕｅ）の文字列（ｓｔｒｉｎｇ）を生成し、クエリメッセージに文字列を載せて伝送する。制御部（１５０）は、タグの有する文字列（タグＩＤ）に対して逆順にツリーを生成できる。これに対する詳細な説明は後述する。
【００２３】
図３は、タグの構成の一例を示したブロック図である。
図３を参照すると、タグ（２００）は、受信アンテナ（２１０）、送信アンテナ（２２０）、復調部（２３０）、ＲＦ-ＤＣ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ-Ｄｉｒｅｃｔ Ｃｕｒｒｅｎｔ）整流部（２４０）、変調部（２５０）、制御部（２６０）及びＩＤ格納部（２７０）を含む。
【００２４】
受信アンテナ（２１０）は、ＲＦＩＤリーダからの高周波信号を受信してＲＦ-ＤＣ整流部（２４０）に送る。ＲＦ-ＤＣ整流部（２４０）は、高周波信号から電源を発生させて復調部（２３０）、変調部（２５０）、制御部（２６０）及びＩＤ格納部（２７０）に電源を供給する。
【００２５】
復調部（２３０）は受信アンテナ（２１０）を介して受信される受信信号を復調する。変調部（２５０）は、ＲＦＩＤリーダに伝送するデータをデータ信号に変調して送信アンテナ（２２０）を介してＲＦＩＤリーダに伝送する。
【００２６】
ＩＤ格納部（２７０）はタグの固有認識ＩＤを格納する。制御部（２６０）はＲＦＩＤリーダから受信される命令メッセージ、クエリメッセージなどに応じて応答信号を生成する。制御部（２６０）はＲＦＩＤリーダから受信される命令メッセージに応じて応答方式を決定できる。ツリー基盤プロトコルにおいて、制御部（２６０）は、ＲＦＩＤリーダからクエリメッセージを受信すれば、ＩＤ格納部（２７０）に格納されたタグＩＤと、クエリメッセージに含まれた文字列とを、お互いに比較して応答メッセージを生成して伝送できる。制御部（２６０）は、クエリメッセージに含まれた文字列をタグＩＤと逆順に比較して応答できる。制御部（２６０）は逆順ＩＤを生成してクエリメッセージに含まれた文字列と比較できる。
【００２７】
以下、ＲＦＩＤリーダとタグ間のツリー基盤プロトコルについて説明する。
図４は、ＲＦＩＤリーダがタグを認識する過程を示した流れ図である。ツリー基盤プロトコルを表す。
【００２８】
図４を参照すると、ＲＦＩＤリーダは命令（ｃｏｍｍａｎｄ）メッセージを伝送する（Ｓ１１０）。命令メッセージは、ＲＦＩＤリーダの認識範囲内にあるタグ間の衝突または複数のＲＦＩＤリーダ間の衝突を防止するために、タグの状態（ｓｔａｔｕｓ）を制御するメッセージである。また、命令メッセージは、タグの伝送する応答メッセージの類型、応答時間、応答方式などに対する制御情報を含む。
【００２９】
ＲＦＩＤリーダはクエリ（ｑｕｅｒｙ）メッセージをタグに伝送する（Ｓ１２０）。クエリメッセージは、ブロードキャスト（ｂｒｏａｄｃａｓｔ）方式にＲＦＩＤリーダの伝送リンクの範囲内にあるタグに伝送される。ツリー基盤プロトコルにおいてＲＦＩＤリーダは、１ないし数ビットの大きさを有する文字列（ｓｔｒｉｎｇ）をクエリメッセージで伝送し、伝送された文字列より１ビット大きい文字列をキュー（ｑｕｅｕｅ）に維持する。初期キューは文字列（ｓｔｒｉｎｇ）０と１を有する。ＲＦＩＤリーダはキューの文字列の長さを順次増加させながらツリー（ｔｒｅｅ）を生成して多数のタグを認識する。ツリーの生成方法に対しては後述する。
【００３０】
タグはクエリメッセージに対する応答（ｒｅｓｐｏｎｓｅ）メッセージをＲＦＩＤリーダに伝送する（Ｓ１３０）。タグは、０または１をランダムに生成してクエリメッセージと比較して応答でき、これをバイナリツリープロトコル（ｂｉｎａｒｙ ｔｒｅｅ ｐｒｏｔｏｃｏｌ）という。タグは、自分の有したＩＤとクエリメッセージを比較して応答でき、これをクエリツリープロトコル（ｑｕｅｒｙ ｔｒｅｅ ｐｒｏｔｏｃｏｌ）という。
【００３１】
以下、クエリツリープロトコルにおいてクエリメッセージの特徴について説明する。
クエリメッセージに含まれる文字列はタグＩＤ（文字列）のプリフィックス（ｐｒｅｆｉｘ）であってもよい。プリフィックスは、１ビットまたはｎビットの大きさを有することができ（ｎ＞１である整数）、タグが有する文字列（ＩＤ）の前部を占める。即ち、プリフィックスは、ＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）またはＭＳＢからｎ番目ビットまでの文字列である。タグは、自分のＩＤの前部がクエリメッセージに含まれたプリフィックスと一致すれば応答する。例えば、プリフィックスが‘０１’である場合に‘０１ｘｘｘ’のＩＤを有するタグが応答する。
【００３２】
クエリメッセージに含まれる文字列は、タグＩＤ（文字列）のサフィックス（ｓｕｆｆｉｘ）であってもよい。サフィックスは、１ビットまたはｍビットの大きさを有することができ（ｍ＞１である整数）、タグが有する文字列（ＩＤ）の後部を占める。即ち、サフィックスは、ＬＳＢ（Ｌｅａｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）またはＬＳＢからｍ番目ビットまでの文字列である。タグは、自分のＩＤの後部がクエリメッセージに含まれたサフィックスと一致すれば応答する。例えば、サフィックスが‘０１’である場合に‘ｘｘｘ０１’のＩＤを有するタグが応答する。
【００３３】
プリフィックスを使用してクエリツリーを生成する方式を一般的なクエリツリープロトコル（ＱＴ）といい、サフィックスを使用してクエリツリーを生成する方式を逆順クエリツリープロトコル（ＱＴＲ）という。
【００３４】
図５は、本発明の一実施例による命令メッセージを示したブロック図である。
図５を参照すると、命令メッセージは、プレアンブル検出（Ｐｒｅａｍｂｌｅ Ｄｅｔｅｃｔ）フィールド、プレアンブル（Ｐｒｅａｍｂｌｅ）フィールド、区分文字（Ｄｅｌｉｍｉｔｅｒ）フィールド、命令（Ｃｏｍｍａｎｄ）フィールド、ＱＴＲ指示フィールド及びＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｎｃｙ Ｃｈｅｃｋ）フィールドを含む。
【００３５】
プレアンブル検出フィールドは、プレアンブルの検出のためのフィールドであり、一般的に４００μｍ間変調されない一定の搬送波で構成される。プレアンブルフィールドはＮＲＺ（Ｎｏｎ−Ｒｅｔｕｒｎ ｔｏ Ｚｅｒｏ）形式にマンチェスターコードを使用することができる。ＮＲＺは‘１’と‘０’の二進値の各々を正（＋）の電圧値と負（−）の電圧値に変換するインコーディングの形態である。区分文字フィールドはデータの開始を知らせるフィールドであり、多様な区分文字が入力されることができる。
【００３６】
命令フィールドは、タグが伝送する応答メッセージの類型、応答時間、応答方式などに対する制御情報が載せるフィールドである。ＱＴＲ指示フィールドは、逆順クエリツリープロトコル（ＱＴＲ）の遂行状態を指示するフィールドである。逆順クエリツリープロトコルに対しては後述する。ＱＴＲ指示フィールドは、１ビットの大きさで逆順クエリツリープロトコルの遂行状態を指示できる。例えば、ＱＴＲ指示フィールドの値が‘１’である場合、逆順クエリツリープロトコルを遂行することを意味し、このとき、タグは、ＲＦＩＤリーダからのクエリメッセージに対して自分のＩＤを逆順に比較して応答メッセージを伝送する。また、ＱＴＲ指示フィールドの値が‘０’である場合、逆順クエリツリープロトコルを遂行せず、一般的なクエリツリープロトコルを遂行することを意味し、このとき、タグはＲＦＩＤリーダからのクエリメッセージに対して自分のＩＤをＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）から順に比較して応答メッセージを伝送する。ＣＲＣフィールドは、データ伝送過程で発生する誤謬を検出するために、循環二進符号が入力されるフィールドである。各フィールドの配置は例示に過ぎず、制限ではない。特に、区分文字フィールド、命令フィールド及びＱＴＲ指示フィールドはお互いに位置が変えられることができる。
【００３７】
以下、一般的なクエリツリープロトコル（ＱＴ）でクエリツリーを生成してタグを認識する方法について説明する。
【００３８】
図６は、一般的なクエリツリープロトコルにおいてクエリツリーの一例を示した例示図である。
図６を参照すると、ＲＦＩＤリーダの認識領域に５つのタグが位置し、各タグのＩＤが｛０１００１，０１０１０，０１０１１，０１１００，０１１０１｝であると仮定する。
【００３９】
表１は、一般的なクエリツリープロトコル（ＱＴ）を用いて５つのタグを全部認識する間クエリ（ｑｕｅｒｙ）及び応答（ｒｅｓｐｏｎｓｅ）を表す。ラウンド（ｒｏｕｎｄ；Ｒ）は、クエリ及び応答に使用される同じ長さの文字列が使われる区間であり、使われる文字列の長さまたはツリーの深さを意味する。ステップ（ｓｔｅｐ）はクエリ及び応答の回数を表す。
【００４０】
【表１】
【００４１】
ＲＦＩＤリーダは初期キューに０と１を有する。ＲＦＩＤリーダはキューにある文字列を一つずつ取り出してプリフィックスとしてクエリする。
【００４２】
１Ｓｔｅｐ：ＲＦＩＤリーダがキューで０を取り出してタグにクエリすれば、タグはこれを自分の有したＩＤ(文字列)のＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）の値と比較する。ＭＳＢは文字列の一番目の（左側から）ビットである。ＲＦＩＤリーダのクエリと自分のＭＳＢ値が一致するため、５つのタグの全部が自分のＩＤで応答する。タグの応答は、一番目のビット値は一致するが、残りのビット値は一致しないため、ＲＦＩＤリーダがタグの応答を認識できない衝突（ｃｏｌｌｉｓｉｏｎ）が発生する。ＲＦＩＤリーダは衝突が発生すれば、０に引き続いて０及び１を加えてキューに‘００’及び‘０１’を生成する。
【００４３】
２Ｓｔｅｐ：ＲＦＩＤリーダはキューで１を取り出してタグにクエリする。タグはクエリと自分のＭＳＢ値が一致しないため応答しない（ｎｏ ｒｅｓｐｏｎｓｅ）。応答のない場合、ＲＦＩＤリーダは何もせず、キューに待機中である次の文字列でクエリを続ける。ＲＦＩＤリーダは初期キューの０と１を全て使用して１ラウンドを終了し、このとき、ツリーの深さは１となる。
【００４４】
３Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘００’を取り出してタグにクエリする。タグはＭＳＢから二度目のビットまでの値をＲＦＩＤリーダのクエリと比較する。タグはクエリと自分のＭＳＢ値が一致しないため応答しない（ｎｏ ｒｅｓｐｏｎｓｅ）。
【００４５】
４Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘０１’を取り出してタグにクエリする。５つのタグの全部が応答して衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。ＲＦＩＤリーダは、０１に引き続いて０及び１を加えて、キューに‘０１０’及び‘０１１’を生成する。２ラウンドが終了してツリーの深さは２となる。
【００４６】
５Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘０１０’をタグにクエリし、ＩＤ＝｛０１００１，０１０１０，０１０１１｝であるタグから応答を受けて衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。キューには‘０１００’及び‘０１０１’が生成される。
【００４７】
６Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘０１１’をタグにクエリし、ＩＤ＝｛０１１００，０１１０１｝であるタグから応答を受けて衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。キューには‘０１１０’及び‘０１１１’が生成される。３ラウンドが終了してツリーの深さは３となる。
【００４８】
７Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘０１００’をタグにクエリし、ＩＤ＝｛０１００１｝であるタグから応答を受けてタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。タグを認識したＲＦＩＤリーダはキューに待機中である次の文字列でクエリを続ける。
【００４９】
このように、ＲＦＩＤリーダは、初期キューに文字列０及び１を有し、プリフィックスを伝送して衝突が発生すれば、文字列の長さを１ビット増加させてキューに新しい文字列を生成し、タグから応答がなかったり、一つのタグを認識するようになれば、キューにある次の文字列でクエリを続ける。ＲＦＩＤリーダはキューに待機中である文字列がなくなる時までクエリを繰り返して全てのタグを認識するようになる。
【００５０】
ここではキューに待機中である文字列がなくなる時まで、即ち、５つの全てのタグを認識する時まで、１４回のクエリ及び応答が遂行され、ツリーの深さは５となる。
【００５１】
以下、逆順クエリツリープロトコル（ＱＴＲ）でクエリツリーを生成してタグを認識する方法について説明する。
【００５２】
図７は、本発明の一実施例に係る逆順クエリツリープロトコルにおいてクエリツリーを示した例示図である。
図７を参照すると、図６と同様に、ＲＦＩＤリーダの認識領域に５つのタグが位置して、各タグのＩＤが｛０１００１，０１０１０，０１０１１，０１１００，０１１０１｝であると仮定する。
【００５３】
表２は、逆順クエリツリープロトコル（ＱＴＲ）を用いて５つのタグを全部認識する間クエリ（ｑｕｅｒｙ）及び応答（ｒｅｓｐｏｎｓｅ）を表す。ラウンド（ｒｏｕｎｄ；Ｒ）は、クエリ及び応答に使われる同じ長さの文字列が使われる区間であり、使われる文字列の長さまたはツリーの深さを意味する。ステップ（ｓｔｅｐ）はクエリ及び応答の回数を表す。
【００５４】
【表２】
【００５５】
ＲＦＩＤリーダは初期キューに０と１を有する。ＲＦＩＤリーダはキューにある文字列を一つずつ取り出してサフィックスとしてクエリする。タグは自分のＩＤを逆順にＲＦＩＤリーダのサフィックスと比較する。タグはＲＦＩＤリーダのサフィックスと逆順ＩＤを比較する。タグのＩＤをＬＳＢからＭＳＢへの順に読むものを逆順ＩＤという。各タグの逆順ＩＤ（ｒｅｖｅｒｓｅｄ ＩＤ）は｛１００１０，０１０１０，１１０１０，００１１０，１０１１０｝となる。タグはＲＦＩＤリーダのクエリ（サフィックス）を逆順ＩＤと比較し、自分の逆順ＩＤがサフィックスと一致すれば、自分のＩＤで応答する。
【００５６】
下の表３は逆順クエリツリープロトコル（ＱＴＲ）のアルゴリズムの一例を表す。
【００５７】
【表３】
【００５８】
ＲＦＩＤリーダは、初期キューに文字列０及び１を有し、サフィックスを伝送して衝突が発生すれば、文字列の長さを１ビット増加させ、キューに新しい文字列を生成し、タグから応答がなかったり、一つのタグを認識するようになれば、キューにある次の文字列でクエリを続ける。ＲＦＩＤリーダはキューに待機中である文字列がなくなる時までクエリを繰り返して全てのタグを認識するようになる。
【００５９】
逆順クエリツリープロトコル（ＱＴＲ）に従って、１Ｓｔｅｐ：ＲＦＩＤリーダがキューで０を取り出してタグにクエリすれば、タグはこれを自分の逆順ＩＤのＭＳＢ値と比較する。逆順ＩＤのＭＳＢはＩＤのＬＳＢに対応する。逆順ＩＤのＭＳＢ値が０であるＩＤ＝｛０１１００，０１０１０｝であるタグが応答して衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。ＲＦＩＤリーダは０に引き続いて０及び１を加えてキューに‘００’及び‘０１’を生成する。
【００６０】
２Ｓｔｅｐ：ＲＦＩＤリーダがキューで１を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢ値が１であるＩＤ＝｛０１００１，０１１０１，０１０１１｝であるタグが応答して衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。ＲＦＩＤリーダは１に引き続いて０及び１を加えてキューに‘１０’及び‘１１’を生成する。１ラウンドが終了してツリーの深さは１となる。
【００６１】
３Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘００’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから二度目のビットまでの値が００であるＩＤ＝｛０１１００｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。
【００６２】
４Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘０１’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから二度目のビットまでの値が０１であるＩＤ＝｛０１０１０｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。
【００６３】
５Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘１０’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから二度目のビットまでの値が１０であるＩＤ＝｛０１００１、０１１０１｝であるタグから応答を受信して衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。ＲＦＩＤリーダは１０に引き続いて０及び１を加えてキューに‘１００’及び‘１０１’を生成する。
【００６４】
６Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘１１’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから二度目のビットまでの値が１１であるＩＤ＝｛０１０１１｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。２ラウンドが終了してツリーの深さは２となる。
【００６５】
７Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘１００’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから三番目のビットまでの値が１００であるＩＤ＝｛０１００１｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。
【００６６】
８Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘１０１’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから三番目のビットまでの値が１０１であるＩＤ＝｛０１１０１｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。３ラウンドが終了してツリーの深さは３となる。ＲＦＩＤリーダはキューに待機中である文字列がないため、タグの認識過程を終了する。ＲＦＩＤリーダが５つの全てのタグを認識する時まで８回のクエリ及び応答が遂行される。
【００６７】
逆順クエリツリープロトコル（ＱＴＲ）が一般的なクエリツリープロトコル（ＱＴ）に比べてツリーの深さも少なく、クエリ及び応答の回数も少ない。即ち、逆順クエリツリープロトコル（ＱＴＲ）を用いて、ＲＦＩＤリーダはさらに短い時間にＲＦＩＤリーダの認識領域にある全てのタグを認識できる。また、逆順クエリツリープロトコル（ＱＴＲ）で、タグがＲＦＩＤリーダのクエリを逆順に認識して応答し、ＲＦＩＤリーダは一般的なクエリツリープロトコル（ＱＴ）でと同じ方式にクエリツリーを生成できるため、ＲＦＩＤリーダに追加的なプロセッサが必要ない。
【００６８】
図８は、一般的なクエリツリープロトコル（ＱＴ）及び逆順クエリツリープロトコル（ＱＴＲ）でクエリメッセージの伝送回数を表したグラフである。
図８を参照すると、タグのＩＤが連続的（ｓｅｑｕｅｎｔ；Ｓｅｑ）である場合と、任意的（ｒａｎｄｏｍ；Ｒｄｍ）である場合、タグの数に応ずるクエリの数を表す。一般的なクエリツリープロトコル（ＱＴ）より逆順クエリツリープロトコル（ＱＴＲ）の方がクエリの数が少ないため、より一層効果的にタグを認識することができる。
【００６９】
複数のタグＩＤが連続された整数と仮定し、ＲＦＩＤリーダとタグ間の通信でクエリの数に対して説明する。Ａ＝｛ｂ０，ｂ１，・・・，ｂｎ−１｝は同じ長さの文字列の集合とする。キュー（Ａ）は、Ａにクエリツリープロトコルが適用されて得られるクエリツリーで定義される。キュー（Ａ）は、Ａに応じて決定される。ｅ（Ａ）は、キュー（Ａ）のエッジ（ｅｄｇｅ）の数、即ち、ＲＦＩＤリーダによるクエリの数である。数学式１は一般的なクエリツリープロトコル（ＱＴ）でＲＦＩＤリーダによるクエリの数を表す。数学式２は逆順クエリツリープロトコル（ＱＴＲ）でＲＦＩＤリーダによるクエリの数を表す。
【００７０】
【数１】
【００７１】
【数２】
【００７２】
ここで、ＡＲはＡの文字列を逆順に読む逆順文字列を意味する。Ｂ＝｛ｄ０，ｄ１，・・・，ｄｎ−１｝で、ｂｉ＝ｃｄｉ（０＝ｉ＝ｎ−１）である。ｃｄｉは文字列ｃに続いてｄｉがついて形成される文字列である。ＨはタグＩＤの長さ、ｈはｄ０の長さ、ｎはタグＩＤの数を表す。ｅ（ＢＲ）＝２（ｎ−１）ｎ個のタグＩＤに対した最小限のクエリの数を意味する。従って、ｅ（Ｂ）＝ｅ（ＢＲ）とし、ｅ（Ａ）＝ｅ（ＡＲ）となる。即ち、逆順クエリツリープロトコル（ＱＴＲ）におけるクエリの数が一般的なクエリツリープロトコル（ＱＴ）におけるクエリの数より少ない。
【００７３】
図９は、一般的なクエリツリープロトコル（ＱＴ）及び逆順クエリツリープロトコル（ＱＴＲ）で伝送されるビット数を表したグラフである。
図９を参照すると、タグのＩＤが連続的（Ｓｅｑ）である場合にタグの数に応じて伝送されるビット数を表す。一般的なクエリツリープロトコル（ＱＴ）より逆順クエリツリープロトコル（ＱＴＲ）の方が、伝送ビット数が少ないため、より一層効果的にタグを認識することができる。
【００７４】
逆順クエリツリープロトコルは、ＥＰＣコードのように同じ会社ＩＤ、製品ＩＤなどがタグＩＤの前部を占めて、後部にシリアルナンバがつく時、少ない数のクエリで多くの数のタグを効率的に認識するものとして使用することができる。よって、類似のＩＤを有するタグが多く使われる供給業体で連続的なＩＤのタグが付着された物品を管理する時に効率的に使用することができる。
【００７５】
以上、タグが有するＩＤの長さを５ビットとして例を上げたが、これは例示に過ぎず、タグＩＤの長さには制限がない。また、タグのＩＤを二進数で表現したが、これに限定されず、タグのＩＤを本実施例とは異なる方法で表現しても逆順クエリツリープロトコルは同一に適用することができる。
【００７６】
以上、本発明について実施例を参照して説明したが、該当技術分野における通常の知識を有した者は、本発明の技術的思想及び領域から外れない範囲内で、本発明を多様に修正及び変更させて実施することが可能である。従って、上述した実施例に限定することなく、本発明は特許請求範囲の範囲内の全ての実施例を含む。
【符号の説明】
【００７７】
１０、１００ ＲＦＩＤリーダ
２０、２００ タグ
１１０ アンテナ
１２０ 通信部
１３０ 格納部
１４０ インターフェース部
１５０、２６０ 制御部
２１０ 受信アンテナ
２２０ 送信アンテナ
２３０ 復調部
２４０ ＲＦ-ＤＣ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ−Ｄｉｒｅｃｔ Ｃｕｒｒｅｎｔ）整流部
２５０ 変調部
２７０ ＩＤ格納部
【技術分野】
【０００１】
本発明は、ＲＦＩＤタグに関し、より詳しくは、タグ間の衝突を防止してタグを認識する方法及びこれを用いたＲＦＩＤタグに関する。
【背景技術】
【０００２】
ＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）技術は、非接触無線認識技術であって、ＩＣ（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）チップと無線通信のためのアンテナを内蔵したタグ（ｔａｇ）に必要な情報を格納し、タグの情報を収集できるＲＦＩＤリーダ（ｒｅａｄｅｒ）がラジオ周波数帯域を介してタグと通信する技術である。
【０００３】
ＲＦＩＤ技術はバーコード方式に比べて多様な長所を有している。
第一に、タグはバーコードのように表面に印刷する必要がないため、汚染に対する心配がない。第二に、ＲＦＩＤ技術は、無線通信を使用するため、タグをＲＦＩＤリーダに一つずつ近接させなくてもよい。第三に、ＲＦＩＤ技術は、多重認識技術を提供するため、短い時間に多数のタグ情報を認識できる。第四に、単純な識別コードだけが印刷されるバーコードとは違ってタグには多量の情報を入力することができる。第五に、バーコード方式は、同じ種類の製品に同じ識別コードを使用するが、ＲＦＩＤ技術は各々の製品ごとに固有な識別コードを使用することができるため、製品販売や在庫管理の側面で正確且つ迅速な管理を行うことができる。
【０００４】
ＲＦＩＤリーダは、無線通信環境で多数のタグ情報を認識しなければならず、この過程で多数のタグ間の衝突（ｃｏｌｌｉｓｉｏｎ）問題が発生する。タグはＲＦＩＤリーダから受けたクエリ（ｑｕｅｒｙ）に対応する情報を報告しなければならず、タグは現在の無線チャネルの使用状態を確認できる機能がない。また、多数のタグは無線チャネルを共有するため、一つ以上のタグがＲＦＩＤリーダに同時にデータを伝送でき、同じチャネルを介して多数のタグから同時にデータが伝送されれば、ＲＦＩＤリーダはタグ情報を認識できない。これをＲＦＩＤシステムにおいてタグ間衝突といい、衝突を防止するためのＲＦＩＤリーダとタグ間のプロトコルを衝突防止（ａｎｔｉ-ｃｏｌｌｉｓｉｏｎ）プロトコルという。
【０００５】
衝突防止プロトコルは、大きくアロハ(ＡＬＯＨＡ)基盤プロトコル及びツリー（ｔｒｅｅ）基盤プロトコルに分かれる。アロハ基盤プロトコルは、時間をスロット単位に分けて一つの時間スロットに一つのタグだけが無作為で応答するようにして、ＲＦＩＤリーダがタグを認識するようにするプロトコルである。アロハ基盤プロトコルは、無作為という確率の不確実性に基礎をおいているため、ＲＦＩＤリーダが全てのタグを認識できないこともあって、全てのタグを認識するのにかかる時間を予測するのは難しい。
【０００６】
ツリー基盤プロトコルは、タグの固有なＩＤを使用してタグ認識過程を進行しつつツリーを作るプロトコルである。ツリー基盤プロトコルを使用するＲＦＩＤリーダは、全てのタグを認識でき、その過程を予測できるのに対し、類似のＩＤを有したタグが多い場合、ツリーを生成する間、衝突が頻繁に発生し、これに伴ってツリーが深くなってタグを認識する時間が長くかかるという短所がある。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明の解決しようとする技術的課題は、ＲＦＩＤシステムにおいてタグを認識する時間を減らすことができるタグ認識方法、衝突防止方法及びこれを用いたＲＦＩＤタグを提供することである。
【課題を解決するための手段】
【０００８】
本発明の一実施例に係るＲＦＩＤリーダとタグ間のクエリ応答に応じてクエリツリーを生成して上記タグを認識するタグ認識防止方法は、上記ＲＦＩＤリーダが上記タグでクエリメッセージを伝送する段階、及び上記タグから上記クエリメッセージに対する応答メッセージを受信する段階を含み、上記タグが有する文字列（ｓｔｒｉｎｇ）の逆順に上記クエリツリーを生成する。上記クエリメッセージは、上記文字列のサフィックス（ｓｕｆｆｉｘ）である。上記応答メッセージが、他のタグからの応答メッセージと衝突が発生すれば、上記ＲＦＩＤリーダは、上記サフィックスに追加文字を加えた文字列をキュー（ｑｕｅｕｅ）に生成させることができる。上記タグは、上記文字列のＬＳＢ（Ｌｅａｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）への順に上記クエリメッセージと上記文字列を比較して上記応答メッセージを伝送できる。上記タグは、自分のＩＤ（ＩＤｅｎｔｉｆｉｅｒ）に対する逆順ＩＤを生成して上記クエリメッセージと比較できる。
【０００９】
本発明のもう一つの実施例に係るクエリツリープロトコルを用いるＲＦＩＤリーダからのクエリに対して応答するＲＦＩＤタグは、ＲＦＩＤリーダからのクエリメッセージを受信して復調する復調部、タグＩＤを上記クエリメッセージに含まれた文字列と逆順に比較して一致すれば、応答メッセージを生成する制御部、及び上記応答メッセージを変調して伝送する変調部、を含む。上記応答メッセージは上記タグＩＤである。
【００１０】
本発明の他の実施例に係るタグ間の衝突を防止するための衝突防止方法は、タグがＲＦＩＤリーダから第１のサフィックスを受信する段階、上記第１のサフィックスを上記タグのＩＤと逆順に比較して第１の応答メッセージを伝送する段階、上記第１の応答メッセージを伝送した後、上記第１のサフィックスより長い第２のサフィックスを受信する段階、及び上記第２のサフィックスを上記タグのＩＤと逆順に比較して第２の応答メッセージを伝送する段階、を含む。上記第１のサフィックスは、上記タグのＩＤのＬＳＢからｍ番目ビットまでの文字列であり、上記第２のサフィックスは、上記タグのＩＤのＬＳＢからｎ番目ビットまでの文字列である（ｎ＞ｍであり、ｎ、ｍ＞０である整数）。
【発明の効果】
【００１１】
クエリツリー基盤プロトコルにおいてタグが有するＩＤに対して逆順にクエリツリーを生成してタグ間の衝突回数を減らして、ＲＦＩＤリーダの認識領域内の全てのタグを認識するにかかる時間を短縮することができる。
【図面の簡単な説明】
【００１２】
【図１】ＲＦＩＤシステムの一例を示したブロック図である。
【図２】ＲＦＩＤリーダの構成の一例を示したブロック図である。
【図３】タグの構成の一例を示したブロック図である。
【図４】ＲＦＩＤリーダがタグを認識する過程を示した流れ図である。
【図５】本発明の一実施例に係る命令メッセージを示したブロック図である。
【図６】一般的なクエリツリープロトコル（ＱＴ）でクエリツリーの一例を示した例示図である。
【図７】本発明の一実施例に係る逆順クエリツリープロトコル（ＱＴＲ）でクエリツリーを示した例示図である。
【図８】一般的なクエリツリープロトコル（ＱＴ）及び逆順クエリツリープロトコル（ＱＴＲ）でクエリメッセージの伝送回数を示したグラフである。
【図９】一般的なクエリツリープロトコル（ＱＴ）及び逆順クエリツリープロトコル（ＱＴＲ）で伝送されるビット数を示したグラフである。
【発明を実施するための形態】
【００１３】
図１は、ＲＦＩＤシステムの一例を示したブロック図である。
図１を参照すると、ＲＦＩＤ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ ＩＤｅｎｔｉｆｉｃａｔｉｏｎ）システムは、ＲＦＩＤリーダ（ＲＦＩＤ ｒｅａｄｅｒ；１０）及び少なくとも一つのタグ（ｔａｇ；２０）を含む。タグ（２０）の数には制限がない。
【００１４】
ＲＦＩＤリーダ（１０）は、質問器（ｉｎｔｅｒｒｏｇａｔｏｒ）、タグ認識装置（ｔａｇ ｉｄｅｎｔｉｆｙ ａｐｐａｒａｔｕｓ）、タグ検出器（ｔａｇ ｄｅｔｅｃｔｏｒ）など、他の名称で呼称することができる。ＲＦＩＤリーダ（１０）はタグ（２０）の情報を読み出すためにタグ（２０）と通信する。ＲＦＩＤリーダ（１０）は、データをインコーディングしてラジオチャネルを介してタグ（２０）に伝送し、タグ（２０）から伝送される信号をデコーディングしてタグ（２０）の固有情報を認識する。ＲＦＩＤリーダ（１０）は固定型ＲＦＩＤリーダであってもよく、移動型ＲＦＩＤリーダであってもよい。
【００１５】
タグ（２０）はＩＣ（Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）チップとアンテナを含む。タグは固有情報であるＩＤ（ＩＤｅｎｔｉｆｉｅｒ）を有する。ＩＤは二進文字列（ｂｉｎａｒｙ ｓｔｒｉｎｇ）形態で記録されることができる。タグのＩＤは一般的に複数のフィールド（ｆｉｅｌｄ）からなる。例えば、供給業体の特定物品の固有識別番号を表すＥＰＣ（Ｅｌｅｃｔｒｏｎｉｃ Ｐｒｏｄｕｃｔ Ｃｏｄｅ）はヘッダ（ｈｅａｄｅｒ）、会社ＩＤ、製品ＩＤ及びシリアルナンバ（ｓｅｒｉａｌ ｎｕｍｂｅｒ）など、４つのフィールドで構成される。ヘッダはＥＰＣの長さ及び構成を定義して、会社ＩＤは会社ごとに固有番号で決められ、製品ＩＤは会社で製品の種類に応じて固有番号で与えられる。従って、各製品に相異のシリアルナンバが与えられる。即ち、各製品に相異のＥＰＣを有したタグ（２０）が付着されて各製品を区分できる。
【００１６】
タグ（２０）はＲＦＩＤリーダ（１０）からクエリ（ｑｕｅｒｙ）メッセージを受信すれば、固有情報または固有情報から計算した値をＲＦＩＤリーダ（１０）に応答する。タグは、それ自体バッテリーを有する能動型タグ（ａｃｔｉｖｅ ｔａｇ）であってもよく、バッテリーを有しない受動型タグ（ｐａｓｓｉｖｅ ｔａｇ）であってもよい。
【００１７】
ＲＦＩＤリーダ（１０）からタグ（２０）への伝送を伝送リンク（ｆｏｒｗａｒｄ ｌｉｎｋ）といい、タグ（２０）からＲＦＩＤリーダ（１０）への伝送を搬送リンク（ｒｅｔｕｒｎ ｌｉｎｋ）という。ＲＦＩＤリーダ（１０）が伝送リンクで信号を伝送できる範囲は制限され、タグ（２０）が搬送リンクで伝送できる範囲は制限される。ＲＦＩＤリーダ（１０）は、伝送リンクの範囲及び搬送リンクの範囲内にあるタグ（２０）とデータを送受信できる。ＲＦＩＤリーダ（１０）がタグ（２０）とデータを送受信できる範囲をＲＦＩＤリーダ（１０）の認識領域という。
【００１８】
図２は、ＲＦＩＤリーダの構成の一例を示したブロック図である。
図２を参照すると、ＲＦＩＤリーダ（１００）は、アンテナ（１１０）、通信部（１２０）、格納部（１３０）、インターフェース部（１４０）及び制御部（１５０）を含む。
【００１９】
通信部（１２０）は、ＲＦモジュール(不図示)及び変復調モジュール(不図示)を含み、タグと高周波信号で通信を遂行する。ＲＦモジュールは、データ信号を高周波信号に変換してアンテナ（１１０）を介して送信したり、アンテナ（１１０）から受信される高周波信号を一定帯域のデータ信号に変換する。変復調モジュールは、タグで伝送するデータをデータ信号に変調したり、タグから受信されるデータ信号をデータに復調する。
【００２０】
格納部（１３０）はタグの認識のために必要な情報を格納する。格納部（１３０）は、タグから受信したタグＩＤ、タグＩＤに対応する物品情報、各種命令メッセージなどを格納する。
【００２１】
インターフェース部（１４０）は特定インターフェースを含んで外部のシステムとデータを送受信する。インターフェース部（１４０）は、直列通信インターフェース、並列通信インターフェース、ＵＳＢインターフェース、イーサネット（登録商標）インターフェースなどを含むことができる。
【００２２】
制御部（１５０）は、通信部（１２０）、格納部（１３０）、インターフェース部（１４０）を制御する。制御部（１５０）は、タグから受信される信号らの衝突状態を感知し、タグ間の衝突を解決するための多様なプロセッサを遂行する。ツリー基盤プロトコルにおいて制御部（１５０）はツリーを生成して管理する。制御部（１５０）は、キュー（ｑｕｅｕｅ）の文字列（ｓｔｒｉｎｇ）を生成し、クエリメッセージに文字列を載せて伝送する。制御部（１５０）は、タグの有する文字列（タグＩＤ）に対して逆順にツリーを生成できる。これに対する詳細な説明は後述する。
【００２３】
図３は、タグの構成の一例を示したブロック図である。
図３を参照すると、タグ（２００）は、受信アンテナ（２１０）、送信アンテナ（２２０）、復調部（２３０）、ＲＦ-ＤＣ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ-Ｄｉｒｅｃｔ Ｃｕｒｒｅｎｔ）整流部（２４０）、変調部（２５０）、制御部（２６０）及びＩＤ格納部（２７０）を含む。
【００２４】
受信アンテナ（２１０）は、ＲＦＩＤリーダからの高周波信号を受信してＲＦ-ＤＣ整流部（２４０）に送る。ＲＦ-ＤＣ整流部（２４０）は、高周波信号から電源を発生させて復調部（２３０）、変調部（２５０）、制御部（２６０）及びＩＤ格納部（２７０）に電源を供給する。
【００２５】
復調部（２３０）は受信アンテナ（２１０）を介して受信される受信信号を復調する。変調部（２５０）は、ＲＦＩＤリーダに伝送するデータをデータ信号に変調して送信アンテナ（２２０）を介してＲＦＩＤリーダに伝送する。
【００２６】
ＩＤ格納部（２７０）はタグの固有認識ＩＤを格納する。制御部（２６０）はＲＦＩＤリーダから受信される命令メッセージ、クエリメッセージなどに応じて応答信号を生成する。制御部（２６０）はＲＦＩＤリーダから受信される命令メッセージに応じて応答方式を決定できる。ツリー基盤プロトコルにおいて、制御部（２６０）は、ＲＦＩＤリーダからクエリメッセージを受信すれば、ＩＤ格納部（２７０）に格納されたタグＩＤと、クエリメッセージに含まれた文字列とを、お互いに比較して応答メッセージを生成して伝送できる。制御部（２６０）は、クエリメッセージに含まれた文字列をタグＩＤと逆順に比較して応答できる。制御部（２６０）は逆順ＩＤを生成してクエリメッセージに含まれた文字列と比較できる。
【００２７】
以下、ＲＦＩＤリーダとタグ間のツリー基盤プロトコルについて説明する。
図４は、ＲＦＩＤリーダがタグを認識する過程を示した流れ図である。ツリー基盤プロトコルを表す。
【００２８】
図４を参照すると、ＲＦＩＤリーダは命令（ｃｏｍｍａｎｄ）メッセージを伝送する（Ｓ１１０）。命令メッセージは、ＲＦＩＤリーダの認識範囲内にあるタグ間の衝突または複数のＲＦＩＤリーダ間の衝突を防止するために、タグの状態（ｓｔａｔｕｓ）を制御するメッセージである。また、命令メッセージは、タグの伝送する応答メッセージの類型、応答時間、応答方式などに対する制御情報を含む。
【００２９】
ＲＦＩＤリーダはクエリ（ｑｕｅｒｙ）メッセージをタグに伝送する（Ｓ１２０）。クエリメッセージは、ブロードキャスト（ｂｒｏａｄｃａｓｔ）方式にＲＦＩＤリーダの伝送リンクの範囲内にあるタグに伝送される。ツリー基盤プロトコルにおいてＲＦＩＤリーダは、１ないし数ビットの大きさを有する文字列（ｓｔｒｉｎｇ）をクエリメッセージで伝送し、伝送された文字列より１ビット大きい文字列をキュー（ｑｕｅｕｅ）に維持する。初期キューは文字列（ｓｔｒｉｎｇ）０と１を有する。ＲＦＩＤリーダはキューの文字列の長さを順次増加させながらツリー（ｔｒｅｅ）を生成して多数のタグを認識する。ツリーの生成方法に対しては後述する。
【００３０】
タグはクエリメッセージに対する応答（ｒｅｓｐｏｎｓｅ）メッセージをＲＦＩＤリーダに伝送する（Ｓ１３０）。タグは、０または１をランダムに生成してクエリメッセージと比較して応答でき、これをバイナリツリープロトコル（ｂｉｎａｒｙ ｔｒｅｅ ｐｒｏｔｏｃｏｌ）という。タグは、自分の有したＩＤとクエリメッセージを比較して応答でき、これをクエリツリープロトコル（ｑｕｅｒｙ ｔｒｅｅ ｐｒｏｔｏｃｏｌ）という。
【００３１】
以下、クエリツリープロトコルにおいてクエリメッセージの特徴について説明する。
クエリメッセージに含まれる文字列はタグＩＤ（文字列）のプリフィックス（ｐｒｅｆｉｘ）であってもよい。プリフィックスは、１ビットまたはｎビットの大きさを有することができ（ｎ＞１である整数）、タグが有する文字列（ＩＤ）の前部を占める。即ち、プリフィックスは、ＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）またはＭＳＢからｎ番目ビットまでの文字列である。タグは、自分のＩＤの前部がクエリメッセージに含まれたプリフィックスと一致すれば応答する。例えば、プリフィックスが‘０１’である場合に‘０１ｘｘｘ’のＩＤを有するタグが応答する。
【００３２】
クエリメッセージに含まれる文字列は、タグＩＤ（文字列）のサフィックス（ｓｕｆｆｉｘ）であってもよい。サフィックスは、１ビットまたはｍビットの大きさを有することができ（ｍ＞１である整数）、タグが有する文字列（ＩＤ）の後部を占める。即ち、サフィックスは、ＬＳＢ（Ｌｅａｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）またはＬＳＢからｍ番目ビットまでの文字列である。タグは、自分のＩＤの後部がクエリメッセージに含まれたサフィックスと一致すれば応答する。例えば、サフィックスが‘０１’である場合に‘ｘｘｘ０１’のＩＤを有するタグが応答する。
【００３３】
プリフィックスを使用してクエリツリーを生成する方式を一般的なクエリツリープロトコル（ＱＴ）といい、サフィックスを使用してクエリツリーを生成する方式を逆順クエリツリープロトコル（ＱＴＲ）という。
【００３４】
図５は、本発明の一実施例による命令メッセージを示したブロック図である。
図５を参照すると、命令メッセージは、プレアンブル検出（Ｐｒｅａｍｂｌｅ Ｄｅｔｅｃｔ）フィールド、プレアンブル（Ｐｒｅａｍｂｌｅ）フィールド、区分文字（Ｄｅｌｉｍｉｔｅｒ）フィールド、命令（Ｃｏｍｍａｎｄ）フィールド、ＱＴＲ指示フィールド及びＣＲＣ（Ｃｙｃｌｉｃ Ｒｅｄｕｎｄａｎｃｙ Ｃｈｅｃｋ）フィールドを含む。
【００３５】
プレアンブル検出フィールドは、プレアンブルの検出のためのフィールドであり、一般的に４００μｍ間変調されない一定の搬送波で構成される。プレアンブルフィールドはＮＲＺ（Ｎｏｎ−Ｒｅｔｕｒｎ ｔｏ Ｚｅｒｏ）形式にマンチェスターコードを使用することができる。ＮＲＺは‘１’と‘０’の二進値の各々を正（＋）の電圧値と負（−）の電圧値に変換するインコーディングの形態である。区分文字フィールドはデータの開始を知らせるフィールドであり、多様な区分文字が入力されることができる。
【００３６】
命令フィールドは、タグが伝送する応答メッセージの類型、応答時間、応答方式などに対する制御情報が載せるフィールドである。ＱＴＲ指示フィールドは、逆順クエリツリープロトコル（ＱＴＲ）の遂行状態を指示するフィールドである。逆順クエリツリープロトコルに対しては後述する。ＱＴＲ指示フィールドは、１ビットの大きさで逆順クエリツリープロトコルの遂行状態を指示できる。例えば、ＱＴＲ指示フィールドの値が‘１’である場合、逆順クエリツリープロトコルを遂行することを意味し、このとき、タグは、ＲＦＩＤリーダからのクエリメッセージに対して自分のＩＤを逆順に比較して応答メッセージを伝送する。また、ＱＴＲ指示フィールドの値が‘０’である場合、逆順クエリツリープロトコルを遂行せず、一般的なクエリツリープロトコルを遂行することを意味し、このとき、タグはＲＦＩＤリーダからのクエリメッセージに対して自分のＩＤをＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）から順に比較して応答メッセージを伝送する。ＣＲＣフィールドは、データ伝送過程で発生する誤謬を検出するために、循環二進符号が入力されるフィールドである。各フィールドの配置は例示に過ぎず、制限ではない。特に、区分文字フィールド、命令フィールド及びＱＴＲ指示フィールドはお互いに位置が変えられることができる。
【００３７】
以下、一般的なクエリツリープロトコル（ＱＴ）でクエリツリーを生成してタグを認識する方法について説明する。
【００３８】
図６は、一般的なクエリツリープロトコルにおいてクエリツリーの一例を示した例示図である。
図６を参照すると、ＲＦＩＤリーダの認識領域に５つのタグが位置し、各タグのＩＤが｛０１００１，０１０１０，０１０１１，０１１００，０１１０１｝であると仮定する。
【００３９】
表１は、一般的なクエリツリープロトコル（ＱＴ）を用いて５つのタグを全部認識する間クエリ（ｑｕｅｒｙ）及び応答（ｒｅｓｐｏｎｓｅ）を表す。ラウンド（ｒｏｕｎｄ；Ｒ）は、クエリ及び応答に使用される同じ長さの文字列が使われる区間であり、使われる文字列の長さまたはツリーの深さを意味する。ステップ（ｓｔｅｐ）はクエリ及び応答の回数を表す。
【００４０】
【表１】
【００４１】
ＲＦＩＤリーダは初期キューに０と１を有する。ＲＦＩＤリーダはキューにある文字列を一つずつ取り出してプリフィックスとしてクエリする。
【００４２】
１Ｓｔｅｐ：ＲＦＩＤリーダがキューで０を取り出してタグにクエリすれば、タグはこれを自分の有したＩＤ(文字列)のＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）の値と比較する。ＭＳＢは文字列の一番目の（左側から）ビットである。ＲＦＩＤリーダのクエリと自分のＭＳＢ値が一致するため、５つのタグの全部が自分のＩＤで応答する。タグの応答は、一番目のビット値は一致するが、残りのビット値は一致しないため、ＲＦＩＤリーダがタグの応答を認識できない衝突（ｃｏｌｌｉｓｉｏｎ）が発生する。ＲＦＩＤリーダは衝突が発生すれば、０に引き続いて０及び１を加えてキューに‘００’及び‘０１’を生成する。
【００４３】
２Ｓｔｅｐ：ＲＦＩＤリーダはキューで１を取り出してタグにクエリする。タグはクエリと自分のＭＳＢ値が一致しないため応答しない（ｎｏ ｒｅｓｐｏｎｓｅ）。応答のない場合、ＲＦＩＤリーダは何もせず、キューに待機中である次の文字列でクエリを続ける。ＲＦＩＤリーダは初期キューの０と１を全て使用して１ラウンドを終了し、このとき、ツリーの深さは１となる。
【００４４】
３Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘００’を取り出してタグにクエリする。タグはＭＳＢから二度目のビットまでの値をＲＦＩＤリーダのクエリと比較する。タグはクエリと自分のＭＳＢ値が一致しないため応答しない（ｎｏ ｒｅｓｐｏｎｓｅ）。
【００４５】
４Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘０１’を取り出してタグにクエリする。５つのタグの全部が応答して衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。ＲＦＩＤリーダは、０１に引き続いて０及び１を加えて、キューに‘０１０’及び‘０１１’を生成する。２ラウンドが終了してツリーの深さは２となる。
【００４６】
５Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘０１０’をタグにクエリし、ＩＤ＝｛０１００１，０１０１０，０１０１１｝であるタグから応答を受けて衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。キューには‘０１００’及び‘０１０１’が生成される。
【００４７】
６Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘０１１’をタグにクエリし、ＩＤ＝｛０１１００，０１１０１｝であるタグから応答を受けて衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。キューには‘０１１０’及び‘０１１１’が生成される。３ラウンドが終了してツリーの深さは３となる。
【００４８】
７Ｓｔｅｐ：ＲＦＩＤリーダはキューに待機中である‘０１００’をタグにクエリし、ＩＤ＝｛０１００１｝であるタグから応答を受けてタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。タグを認識したＲＦＩＤリーダはキューに待機中である次の文字列でクエリを続ける。
【００４９】
このように、ＲＦＩＤリーダは、初期キューに文字列０及び１を有し、プリフィックスを伝送して衝突が発生すれば、文字列の長さを１ビット増加させてキューに新しい文字列を生成し、タグから応答がなかったり、一つのタグを認識するようになれば、キューにある次の文字列でクエリを続ける。ＲＦＩＤリーダはキューに待機中である文字列がなくなる時までクエリを繰り返して全てのタグを認識するようになる。
【００５０】
ここではキューに待機中である文字列がなくなる時まで、即ち、５つの全てのタグを認識する時まで、１４回のクエリ及び応答が遂行され、ツリーの深さは５となる。
【００５１】
以下、逆順クエリツリープロトコル（ＱＴＲ）でクエリツリーを生成してタグを認識する方法について説明する。
【００５２】
図７は、本発明の一実施例に係る逆順クエリツリープロトコルにおいてクエリツリーを示した例示図である。
図７を参照すると、図６と同様に、ＲＦＩＤリーダの認識領域に５つのタグが位置して、各タグのＩＤが｛０１００１，０１０１０，０１０１１，０１１００，０１１０１｝であると仮定する。
【００５３】
表２は、逆順クエリツリープロトコル（ＱＴＲ）を用いて５つのタグを全部認識する間クエリ（ｑｕｅｒｙ）及び応答（ｒｅｓｐｏｎｓｅ）を表す。ラウンド（ｒｏｕｎｄ；Ｒ）は、クエリ及び応答に使われる同じ長さの文字列が使われる区間であり、使われる文字列の長さまたはツリーの深さを意味する。ステップ（ｓｔｅｐ）はクエリ及び応答の回数を表す。
【００５４】
【表２】
【００５５】
ＲＦＩＤリーダは初期キューに０と１を有する。ＲＦＩＤリーダはキューにある文字列を一つずつ取り出してサフィックスとしてクエリする。タグは自分のＩＤを逆順にＲＦＩＤリーダのサフィックスと比較する。タグはＲＦＩＤリーダのサフィックスと逆順ＩＤを比較する。タグのＩＤをＬＳＢからＭＳＢへの順に読むものを逆順ＩＤという。各タグの逆順ＩＤ（ｒｅｖｅｒｓｅｄ ＩＤ）は｛１００１０，０１０１０，１１０１０，００１１０，１０１１０｝となる。タグはＲＦＩＤリーダのクエリ（サフィックス）を逆順ＩＤと比較し、自分の逆順ＩＤがサフィックスと一致すれば、自分のＩＤで応答する。
【００５６】
下の表３は逆順クエリツリープロトコル（ＱＴＲ）のアルゴリズムの一例を表す。
【００５７】
【表３】
【００５８】
ＲＦＩＤリーダは、初期キューに文字列０及び１を有し、サフィックスを伝送して衝突が発生すれば、文字列の長さを１ビット増加させ、キューに新しい文字列を生成し、タグから応答がなかったり、一つのタグを認識するようになれば、キューにある次の文字列でクエリを続ける。ＲＦＩＤリーダはキューに待機中である文字列がなくなる時までクエリを繰り返して全てのタグを認識するようになる。
【００５９】
逆順クエリツリープロトコル（ＱＴＲ）に従って、１Ｓｔｅｐ：ＲＦＩＤリーダがキューで０を取り出してタグにクエリすれば、タグはこれを自分の逆順ＩＤのＭＳＢ値と比較する。逆順ＩＤのＭＳＢはＩＤのＬＳＢに対応する。逆順ＩＤのＭＳＢ値が０であるＩＤ＝｛０１１００，０１０１０｝であるタグが応答して衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。ＲＦＩＤリーダは０に引き続いて０及び１を加えてキューに‘００’及び‘０１’を生成する。
【００６０】
２Ｓｔｅｐ：ＲＦＩＤリーダがキューで１を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢ値が１であるＩＤ＝｛０１００１，０１１０１，０１０１１｝であるタグが応答して衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。ＲＦＩＤリーダは１に引き続いて０及び１を加えてキューに‘１０’及び‘１１’を生成する。１ラウンドが終了してツリーの深さは１となる。
【００６１】
３Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘００’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから二度目のビットまでの値が００であるＩＤ＝｛０１１００｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。
【００６２】
４Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘０１’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから二度目のビットまでの値が０１であるＩＤ＝｛０１０１０｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。
【００６３】
５Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘１０’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから二度目のビットまでの値が１０であるＩＤ＝｛０１００１、０１１０１｝であるタグから応答を受信して衝突が発生する（ｃｏｌｌｉｓｉｏｎ）。ＲＦＩＤリーダは１０に引き続いて０及び１を加えてキューに‘１００’及び‘１０１’を生成する。
【００６４】
６Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘１１’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから二度目のビットまでの値が１１であるＩＤ＝｛０１０１１｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。２ラウンドが終了してツリーの深さは２となる。
【００６５】
７Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘１００’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから三番目のビットまでの値が１００であるＩＤ＝｛０１００１｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。
【００６６】
８Ｓｔｅｐ：ＲＦＩＤリーダがキューに待機中である‘１０１’を取り出してタグにクエリすれば、逆順ＩＤのＭＳＢから三番目のビットまでの値が１０１であるＩＤ＝｛０１１０１｝であるタグから応答を受信してタグを認識する（ｉｄｅｎｔｉｆｉｅｄ）。３ラウンドが終了してツリーの深さは３となる。ＲＦＩＤリーダはキューに待機中である文字列がないため、タグの認識過程を終了する。ＲＦＩＤリーダが５つの全てのタグを認識する時まで８回のクエリ及び応答が遂行される。
【００６７】
逆順クエリツリープロトコル（ＱＴＲ）が一般的なクエリツリープロトコル（ＱＴ）に比べてツリーの深さも少なく、クエリ及び応答の回数も少ない。即ち、逆順クエリツリープロトコル（ＱＴＲ）を用いて、ＲＦＩＤリーダはさらに短い時間にＲＦＩＤリーダの認識領域にある全てのタグを認識できる。また、逆順クエリツリープロトコル（ＱＴＲ）で、タグがＲＦＩＤリーダのクエリを逆順に認識して応答し、ＲＦＩＤリーダは一般的なクエリツリープロトコル（ＱＴ）でと同じ方式にクエリツリーを生成できるため、ＲＦＩＤリーダに追加的なプロセッサが必要ない。
【００６８】
図８は、一般的なクエリツリープロトコル（ＱＴ）及び逆順クエリツリープロトコル（ＱＴＲ）でクエリメッセージの伝送回数を表したグラフである。
図８を参照すると、タグのＩＤが連続的（ｓｅｑｕｅｎｔ；Ｓｅｑ）である場合と、任意的（ｒａｎｄｏｍ；Ｒｄｍ）である場合、タグの数に応ずるクエリの数を表す。一般的なクエリツリープロトコル（ＱＴ）より逆順クエリツリープロトコル（ＱＴＲ）の方がクエリの数が少ないため、より一層効果的にタグを認識することができる。
【００６９】
複数のタグＩＤが連続された整数と仮定し、ＲＦＩＤリーダとタグ間の通信でクエリの数に対して説明する。Ａ＝｛ｂ０，ｂ１，・・・，ｂｎ−１｝は同じ長さの文字列の集合とする。キュー（Ａ）は、Ａにクエリツリープロトコルが適用されて得られるクエリツリーで定義される。キュー（Ａ）は、Ａに応じて決定される。ｅ（Ａ）は、キュー（Ａ）のエッジ（ｅｄｇｅ）の数、即ち、ＲＦＩＤリーダによるクエリの数である。数学式１は一般的なクエリツリープロトコル（ＱＴ）でＲＦＩＤリーダによるクエリの数を表す。数学式２は逆順クエリツリープロトコル（ＱＴＲ）でＲＦＩＤリーダによるクエリの数を表す。
【００７０】
【数１】
【００７１】
【数２】
【００７２】
ここで、ＡＲはＡの文字列を逆順に読む逆順文字列を意味する。Ｂ＝｛ｄ０，ｄ１，・・・，ｄｎ−１｝で、ｂｉ＝ｃｄｉ（０＝ｉ＝ｎ−１）である。ｃｄｉは文字列ｃに続いてｄｉがついて形成される文字列である。ＨはタグＩＤの長さ、ｈはｄ０の長さ、ｎはタグＩＤの数を表す。ｅ（ＢＲ）＝２（ｎ−１）ｎ個のタグＩＤに対した最小限のクエリの数を意味する。従って、ｅ（Ｂ）＝ｅ（ＢＲ）とし、ｅ（Ａ）＝ｅ（ＡＲ）となる。即ち、逆順クエリツリープロトコル（ＱＴＲ）におけるクエリの数が一般的なクエリツリープロトコル（ＱＴ）におけるクエリの数より少ない。
【００７３】
図９は、一般的なクエリツリープロトコル（ＱＴ）及び逆順クエリツリープロトコル（ＱＴＲ）で伝送されるビット数を表したグラフである。
図９を参照すると、タグのＩＤが連続的（Ｓｅｑ）である場合にタグの数に応じて伝送されるビット数を表す。一般的なクエリツリープロトコル（ＱＴ）より逆順クエリツリープロトコル（ＱＴＲ）の方が、伝送ビット数が少ないため、より一層効果的にタグを認識することができる。
【００７４】
逆順クエリツリープロトコルは、ＥＰＣコードのように同じ会社ＩＤ、製品ＩＤなどがタグＩＤの前部を占めて、後部にシリアルナンバがつく時、少ない数のクエリで多くの数のタグを効率的に認識するものとして使用することができる。よって、類似のＩＤを有するタグが多く使われる供給業体で連続的なＩＤのタグが付着された物品を管理する時に効率的に使用することができる。
【００７５】
以上、タグが有するＩＤの長さを５ビットとして例を上げたが、これは例示に過ぎず、タグＩＤの長さには制限がない。また、タグのＩＤを二進数で表現したが、これに限定されず、タグのＩＤを本実施例とは異なる方法で表現しても逆順クエリツリープロトコルは同一に適用することができる。
【００７６】
以上、本発明について実施例を参照して説明したが、該当技術分野における通常の知識を有した者は、本発明の技術的思想及び領域から外れない範囲内で、本発明を多様に修正及び変更させて実施することが可能である。従って、上述した実施例に限定することなく、本発明は特許請求範囲の範囲内の全ての実施例を含む。
【符号の説明】
【００７７】
１０、１００ ＲＦＩＤリーダ
２０、２００ タグ
１１０ アンテナ
１２０ 通信部
１３０ 格納部
１４０ インターフェース部
１５０、２６０ 制御部
２１０ 受信アンテナ
２２０ 送信アンテナ
２３０ 復調部
２４０ ＲＦ-ＤＣ（Ｒａｄｉｏ Ｆｒｅｑｕｅｎｃｙ−Ｄｉｒｅｃｔ Ｃｕｒｒｅｎｔ）整流部
２５０ 変調部
２７０ ＩＤ格納部
【特許請求の範囲】
【請求項１】
ＲＦＩＤリーダとタグ間のクエリ応答に応じてクエリツリーを生成して上記タグを認識するタグ認識方法において、
上記ＲＦＩＤリーダが上記タグでクエリメッセージを伝送する段階；及び、
上記タグから上記クエリメッセージに対する応答メッセージを受信する段階を含み、上記タグが有する文字列（ｓｔｒｉｎｇ）の逆順に上記クエリツリーを生成するタグ認識方法。
【請求項２】
請求項１において、
上記クエリメッセージは、上記文字列のサフィックス（ｓｕｆｆｉｘ）であるタグ認識方法。
【請求項３】
請求項２において、
上記応答メッセージが、他のタグからの応答メッセージと衝突が発生すれば、上記ＲＦＩＤリーダは、上記サフィックスに追加文字を加えた文字列をキュー（ｑｕｅｕｅ）に生成させるようにするタグ認識方法。
【請求項４】
請求項１において、
上記タグは、上記文字列のＬＳＢ（Ｌｅａｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）への順に上記クエリメッセージと上記文字列を比較して上記応答メッセージを伝送するタグ認識方法。
【請求項５】
請求項１において、
上記タグは、自分のＩＤ（ＩＤｅｎｔｉｆｉｅｒ）に対する逆順ＩＤを生成して上記クエリメッセージと比較するタグ認識方法。
【請求項６】
ＲＦＩＤリーダから第１のサフィックスを受信し；
上記第１のサフィックスをタグＩＤと逆順に比較して第１の応答メッセージを伝送し；
上記第１の応答メッセージを伝送した後、上記第１のサフィックスより長い第２のサフィックスを受信し；及び、
上記第２のサフィックスを上記タグＩＤと逆順に比較して第２の応答メッセージを伝送するタグの衝突防止方法。
【請求項７】
請求項６において、
上記第１のサフィックスは、上記タグのＩＤのＬＳＢからｍ番目ビットまでの文字列であり、上記第２のサフィックスは、上記タグのＩＤのＬＳＢからｎ番目ビットまでの文字列であり、上記“ｎ＞ｍ”であり、上記“ｎとｍ＞０である整数”であるタグの衝突防止方法。
【請求項８】
ＲＦＩＤリーダからのクエリメッセージを受信して復調する復調部；
上記クエリメッセージに含まれた文字列とタグＩＤを逆順に比較して一致すれば、応答メッセージを生成する制御部；及び、
上記応答メッセージを変調して伝送する変調部を含むことを特徴とするＲＦＩＤタグ。
【請求項９】
請求項８において、
上記応答メッセージは上記タグＩＤであるＲＦＩＤタグ。
【請求項１】
ＲＦＩＤリーダとタグ間のクエリ応答に応じてクエリツリーを生成して上記タグを認識するタグ認識方法において、
上記ＲＦＩＤリーダが上記タグでクエリメッセージを伝送する段階；及び、
上記タグから上記クエリメッセージに対する応答メッセージを受信する段階を含み、上記タグが有する文字列（ｓｔｒｉｎｇ）の逆順に上記クエリツリーを生成するタグ認識方法。
【請求項２】
請求項１において、
上記クエリメッセージは、上記文字列のサフィックス（ｓｕｆｆｉｘ）であるタグ認識方法。
【請求項３】
請求項２において、
上記応答メッセージが、他のタグからの応答メッセージと衝突が発生すれば、上記ＲＦＩＤリーダは、上記サフィックスに追加文字を加えた文字列をキュー（ｑｕｅｕｅ）に生成させるようにするタグ認識方法。
【請求項４】
請求項１において、
上記タグは、上記文字列のＬＳＢ（Ｌｅａｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）からＭＳＢ（Ｍｏｓｔ Ｓｉｇｎｉｆｉｃａｎｔ Ｂｉｔ）への順に上記クエリメッセージと上記文字列を比較して上記応答メッセージを伝送するタグ認識方法。
【請求項５】
請求項１において、
上記タグは、自分のＩＤ（ＩＤｅｎｔｉｆｉｅｒ）に対する逆順ＩＤを生成して上記クエリメッセージと比較するタグ認識方法。
【請求項６】
ＲＦＩＤリーダから第１のサフィックスを受信し；
上記第１のサフィックスをタグＩＤと逆順に比較して第１の応答メッセージを伝送し；
上記第１の応答メッセージを伝送した後、上記第１のサフィックスより長い第２のサフィックスを受信し；及び、
上記第２のサフィックスを上記タグＩＤと逆順に比較して第２の応答メッセージを伝送するタグの衝突防止方法。
【請求項７】
請求項６において、
上記第１のサフィックスは、上記タグのＩＤのＬＳＢからｍ番目ビットまでの文字列であり、上記第２のサフィックスは、上記タグのＩＤのＬＳＢからｎ番目ビットまでの文字列であり、上記“ｎ＞ｍ”であり、上記“ｎとｍ＞０である整数”であるタグの衝突防止方法。
【請求項８】
ＲＦＩＤリーダからのクエリメッセージを受信して復調する復調部；
上記クエリメッセージに含まれた文字列とタグＩＤを逆順に比較して一致すれば、応答メッセージを生成する制御部；及び、
上記応答メッセージを変調して伝送する変調部を含むことを特徴とするＲＦＩＤタグ。
【請求項９】
請求項８において、
上記応答メッセージは上記タグＩＤであるＲＦＩＤタグ。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公表番号】特表２０１０−５０７８７７（Ｐ２０１０−５０７８７７Ａ）
【公表日】平成２２年３月１１日（２０１０．３．１１）
【国際特許分類】
【出願番号】特願２００９−５４９０１４（Ｐ２００９−５４９０１４）
【出願日】平成２０年１０月１６日（２００８．１０．１６）
【国際出願番号】ＰＣＴ／ＫＲ２００８／００６０９４
【国際公開番号】ＷＯ２００９／０８８１５３
【国際公開日】平成２１年７月１６日（２００９．７．１６）
【出願人】（５０７４１５３０３）チュン−アン ユニバーシティー インダストリー−アカデミー コーポレーション ファンデーション (4)
【Ｆターム（参考）】
【公表日】平成２２年３月１１日（２０１０．３．１１）
【国際特許分類】
【出願日】平成２０年１０月１６日（２００８．１０．１６）
【国際出願番号】ＰＣＴ／ＫＲ２００８／００６０９４
【国際公開番号】ＷＯ２００９／０８８１５３
【国際公開日】平成２１年７月１６日（２００９．７．１６）
【出願人】（５０７４１５３０３）チュン−アン ユニバーシティー インダストリー−アカデミー コーポレーション ファンデーション (4)
【Ｆターム（参考）】
[ Back to top ]