(57)【要約】【課題】衝突が発生した多数のＩＤの衝突ビットのパターンをそれぞれ衝突なしに認識して、多数個のＩＤを認識することによりリーダーとタグとの伝送回数を減らすことができるようになる。よって、ＲＦシステムの時間及び電力効率の向上を期することができるＩＤ衝突防止方法及びＲＦＩＤシステムを提供する。【解決手段】ＩＤを形成する記号のうち少なくとも一つを含むＩＤ要請値をリーダー１０から各タグ１〜４に伝送する段階と、リーダー１０が、各タグ１〜４のうちＩＤにＩＤ要請値を含むタグ１〜４からＩＤを伝送される段階と、伝送された複数のＩＤ間の衝突が発生した場合、リーダー１０がＩＤのうち衝突が発生した桁の値を各タグに要請する段階と、リーダー１０が、衝突が発生した桁の値を各タグから提供されてタグのＩＤを決定する段階とを含む。【選択図】図３Ａ
2006338675.tif 000002
【特許請求の範囲】
【請求項１】
リーダー及びそれぞれＩＤを有する少なくとも二つのタグを含むＲＦＩＤシステムのＩＤ衝突防止方法において、
前記ＩＤを形成する記号のうち少なくとも一つを含むＩＤ要請値を前記リーダーから前記各タグに伝送する段階と、
前記リーダーが前記各タグのうち前記ＩＤに前記ＩＤ要請値を含む少なくとも一つのタグからＩＤを伝送される段階と、
前記伝送された複数のＩＤ間の衝突が発生した場合、前記リーダーが、前記ＩＤのうち前記衝突が発生した桁の値を前記各タグに要請する段階と、
前記リーダーが、前記衝突が発生した桁の値を前記各タグから提供され前記タグのＩＤを決定する段階と、
を含むことを特徴とするＩＤ衝突防止方法。
【請求項２】
前記ＩＤは２進ビットで形成され、前記ＩＤ要請値は０または１であることを特徴とする請求項１に記載のＩＤ衝突防止方法。
【請求項３】
前記リーダーは、前記ＩＤ間の衝突が発生した場合、前記衝突が発生した桁を２進ビット以外の記号で認識することを特徴とする請求項１に記載のＩＤ衝突防止方法。
【請求項４】
前記ＩＤのうち前記衝突が発生した桁の値を要請する段階は、
前記リーダーが、前記衝突が発生したＩＤの桁を記号で表示した衝突ビット桁値を生成し前記タグに伝送する段階を含むことを特徴とする請求項１に記載のＩＤ衝突防止方法。
【請求項５】
前記ＩＤのうち前記衝突が発生した桁の値を要請する段階は、
前記ＩＤ要請値を伝送する段階を含むことを特徴とする請求項１に記載のＩＤ衝突防止方法。
【請求項６】
前記各タグで前記衝突が発生した桁の連続するビット値である衝突ビット決定値を生成する段階を含むことを特徴とする請求項１に記載のＩＤ衝突防止方法。
【請求項７】
前記衝突ビット決定値を生成する段階は、
前記衝突が発生した桁のビット値を１０進法の数に変換し、前記１０進法の数に該当する位置を０または１で表示した２進符号形態の衝突ビット決定値を生成する段階であることを特徴とする請求項６に記載のＩＤ衝突防止方法。
【請求項８】
前記衝突ビット決定値は予め設定された桁数だけ伝送可能であることを特徴とする請求項６に記載のＩＤ衝突防止方法。
【請求項９】
前記ＩＤを決定する段階は、
前記衝突ビット決定値が前記予め設定された桁数より小さいか等しい場合、前記衝突が発生した桁に前記衝突ビット決定値を順次代入して前記ＩＤを決定する段階を含むことを特徴とする請求項６に記載のＩＤ衝突防止方法。
【請求項１０】
前記ＩＤを決定する段階は、
前記衝突ビット決定値が前記予め設定された桁数より大きい場合、前記衝突が発生した桁に前記衝突ビット決定値を順次代入して前記ＩＤの一部を確定した推定ＩＤを生成する段階と、
前記推定ＩＤを前記ＩＤ要請値として前記各タグに伝送する段階と、
を含むことを特徴とする請求項６に記載のＩＤ衝突防止方法。
【請求項１１】
前記ＩＤ要請値である推定されたＩＤに対して、衝突が発生しなければＩＤを確定する段階を含むことを特徴とする請求項１０に記載のＩＤ衝突防止方法。
【請求項１２】
前記ＩＤ要請値である推定されたＩＤに対して衝突が発生すれば、前記衝突が発生した桁に対して前記衝突ビット桁値を再び生成し、前記推定されたＩＤと共に前記衝突が発生したタグに伝送する段階を含むことを特徴とする請求項１０に記載のＩＤ衝突防止方法。
【請求項１３】
リーダー及びそれぞれＩＤを有する少なくとも二つのタグを含むＲＦＩＤシステムにおいて、
前記各タグは、
前記リーダーからの要請によってＩＤを提供し、他タグとのＩＤ衝突が発生した場合に、前記ＩＤ衝突が発生したＩＤのうち衝突が発生した桁の値を前記リーダーに提供し、
前記リーダーは、
前記ＩＤを形成する記号のうち少なくとも一つを含むＩＤ要請値を前記各タグに伝送して前記タグからＩＤを提供され、前記ＩＤ間の衝突が発生した場合、前記タグから前記衝突が発生した桁の値を提供され前記ＩＤを決定することを特徴とするＲＦＩＤシステム。
【請求項１４】
前記ＩＤは２進ビットで形成され、前記ＩＤ要請値は０または１で形成されることを特徴とする請求項１３に記載のＲＦＩＤシステム。
【請求項１５】
前記リーダーは、前記ＩＤ間の衝突が発生した場合、前記衝突が発生した桁を２進ビット以外の記号で認識することを特徴とする請求項１３に記載のＲＦＩＤシステム。
【請求項１６】
前記リーダーは、前記衝突が発生したＩＤの桁を記号で表示した衝突ビット桁値を生成することを特徴とする請求項１３に記載のＲＦＩＤシステム。
【請求項１７】
前記リーダーは、前記ＩＤ間の衝突が発生すれば、前記衝突ビット桁値と前記ＩＤ要請値を前記各タグに伝送することを特徴とする請求項１６に記載のＲＦＩＤシステム。
【請求項１８】
前記タグは、前記衝突が発生した桁の連続するビット値である衝突ビット決定値を生成することを特徴とする請求項１３に記載のＲＦＩＤシステム。
【請求項１９】
前記タグは、前記衝突が発生した桁のビット値を１０進法の数に変換し、前記１０進法の数に該当する位置を０または１で表示した２進符号形態の衝突ビット決定値を生成することを特徴とする請求項１３に記載のＲＦＩＤシステム。
【請求項２０】
前記タグは、予め設定された桁数に該当する前記衝突ビット決定値を伝送することを特徴とする請求項１８に記載のＲＦＩＤシステム。
【請求項２１】
前記リーダーは、前記衝突ビット決定値が前記予め設定された桁数より小さいか等しい場合、前記ＩＤの衝突が発生した桁に前記衝突ビット決定値を順次代入して前記ＩＤを決定することを特徴とする請求項１８に記載のＲＦＩＤシステム。
【請求項２２】
前記リーダーは、前記衝突ビット決定値が前記予め設定された桁数より大きい場合、前記ＩＤの衝突が発生した桁に前記衝突ビット決定値を順次代入して前記ＩＤの一部を確定した推定ＩＤを生成し、前記推定ＩＤを前記ＩＤ要請値として前記各タグに伝送することを特徴とする請求項２１に記載のＲＦＩＤシステム。
【請求項２３】
前記リーダーは、前記ＩＤ要請値である推定されたＩＤに対して衝突が発生しなければ該当ＩＤを確定することを特徴とする請求項２２に記載のＲＦＩＤシステム。
【請求項２４】
前記リーダーは、前記ＩＤ要請値である推定されたＩＤに対して衝突が発生すれば、前記衝突が発生した桁に対して前記衝突ビット桁値を再び生成して前記衝突が発生したタグに伝送することを特徴とする請求項２２に記載のＲＦＩＤシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はＩＤ衝突防止方法及びＲＦＩＤシステムに係り、さらに詳しくは衝突ビット決定を通じた衝突防止方法及びＲＦＩＤシステムに関する。
【背景技術】
【０００２】
ＲＦＩＤは事物にタグを付着して電波を用いてタグの情報を読取る技術である。これを用いて事物の物類管理、保安、流通など多様な分野に応用することができる。既存の接触式バーコード（Ｂａｒｃｏｄｅ）をＲＦＩＤに代替することにより、バーコードより速い速度で情報を読み取ることができ、動作環境の距離的制限が緩和される利点の他、事物の知能化という別の利点が得られる（例えば、特許文献１〜３）。
【０００３】
一方、ユビキタスコンピューティング環境下では一つのリーダーの判読範囲内に数多くのタグが属することができ、この場合、リーダーの要請に対して多数個のタグが同時に応答できる。この際多数のタグの信号は互いに干渉を引き起こして衝突が発生する。
【０００４】
このようなタグの応答信号間の干渉を解決して各タグの応答を衝突なしに認識させる方法が求められるが、これが衝突防止アルゴリズム（Ａｎｔｉ−Ｃｏｌｌｉｓｉｏｎ  Ａｌｇｏｒｉｔｈｍ）である。
【０００５】
既存に多様な衝突防止アルゴリズムが使用されており、このうちタグに２進ＩＤを付与し、複数のタグのうち所望のタグを除いた他のタグを次第に除去することにより所望のタグを探し出す衝突防止アルゴリズムを説明すれば次の通りである。
【０００６】
まず、各タグはＮビット（ｂｉｔ）の２進ＩＤが割当てられ、リーダーは所望のＩＤを有するタグを探し出すため各タグにＩＤ要請信号を伝送する。この際、ＩＤ要請信号には２進数の‘０’または‘１’のＩＤ要請値が含まれる。ＩＤ要請信号を受けた各タグはＩＤ要請値と自分のＩＤの１番目ビットを比較し、この際ＩＤ要請値が自分のＩＤの１番目ビットと一致する場合自分のＩＤをリーダーに伝送する。すなわち、ＩＤ要請値が‘１’の場合はタグＩＤが‘１’から始まる全てのタグは自分のＩＤをリーダーに伝送し、ＩＤ要請信号が‘０’の場合、タグＩＤが‘０’から始まる全てのタグが自分のＩＤをリーダーに伝送する。
【０００７】
もし、ＩＤ要請信号に対して応答したタグが１個なら、該当タグはリーダーで所望のタグと判断される。しかし、多数個のタグが応答した場合、すなわちＩＤの１番目のビットに衝突が発生した場合、リーダーはＩＤの次のビットに対するＩＤ要請値で‘０’または‘１’を有するＩＤ要請信号を伝送する。この際、リーダーは応答しないタグをリセットさせて対象から除く。
【０００８】
次のビットのＩＤ要請値に対しても複数のタグが応答する場合、リーダーはその次のビットに対してＩＤ要請値を伝送し、このような過程はＩＤ要請信号に対して１個のタグだけが応答するまで繰り返す。ところが、このような従来の技術によれば、リーダーからタグにＩＤ要請時、ＩＤ要請値として一つのビットずつだけを伝送するので、多数のタグが応答する場合、すなわち衝突が発生したＩＤの桁数が多い場合は反復的にＩＤ要請信号を生成して伝送しなければならない。従って、ＩＤの確定のための時間が比較的長時間かかるという問題点がある。そして、ＩＤ要請信号に対してタグは衝突が発生したビットだけを伝送するのではなく、自分の全体ＩＤを伝送するようになる。従って、ＩＤの一部だけ伝送するよりは電力の消耗が大きくなる
【０００９】
このような従来の技術はＲＦＩＤシステムの運営において時間及び電力効率を低減させる問題点がある。
【特許文献１】特開２００４−２５９１２３号公報
【特許文献２】特開平１１−２０３４３０号公報
【特許文献３】特開２００３−１６８９９７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
本発明は前述した問題点を解決するために案出されたもので、その目的は衝突ビット決定値を用いたＩＤ衝突防止方法及びＲＦＩＤシステムを提供するところにある。
【課題を解決するための手段】
【００１１】
前述した目的を達成するための本発明に係るＩＤ衝突防止方法は、リーダー及びそれぞれＩＤを有する少なくとも二つのタグを含むＲＦＩＤシステムのＩＤ衝突防止方法において、前記ＩＤを形成する記号のうち少なくとも一つを含むＩＤ要請値を前記リーダーから前記各タグに伝送する段階と、前記各タグのうち前記ＩＤ要請値を含む少なくとも一つのタグからＩＤを伝送される段階と、前記伝送された複数のＩＤ間の衝突が発生した場合、前記ＩＤのうち前記衝突が発生した桁の値を前記各タグに要請する段階と、前記衝突が発生した桁の値を前記各タグから提供されて前記タグのＩＤを決定する段階とを含むことを特徴とする。
【００１２】
前記ＩＤは２進ビットで形成され、前記ＩＤ要請値を伝送する段階は、０または１を伝送する段階でありうる。
【００１３】
前記リーダーは、前記ＩＤ間の衝突が発生した場合、前記衝突が発生した桁を２進ビット以外の記号で認識することができる。
【００１４】
前記ＩＤのうち前記衝突が発生した桁の値を要請する段階は、前記衝突が発生したＩＤの桁を記号で表示した衝突ビット桁値を生成して前記タグに伝送する段階を含むことができる。
【００１５】
前記ＩＤのうち前記衝突が発生した桁の値を要請する段階は、前記ＩＤ要請値を伝送する段階を含むことが望ましい。
【００１６】
前記各タグで前記衝突が発生した桁の連続したビット値である衝突ビット決定値を生成する段階を含むことが望ましい。
【００１７】
前記衝突ビット決定値を生成する段階は、前記衝突が発生した桁のビット値を１０進数に変換し、前記１０進数に該当する位置を０または１で表示した２進符号形態の前記衝突ビット決定値を生成する段階でありうる。
【００１８】
前記衝突ビット決定値は予め設定された桁数ほど伝送可能である。
【００１９】
前記ＩＤを決定する段階は、前記衝突ビット決定値が前記予め設定された桁数より小さいか等しい場合、前記衝突が発生した桁に前記衝突ビット決定値を順次に代入して前記ＩＤを決定する段階を含むことが望ましい。
【００２０】
前記ＩＤを決定する段階は、前記衝突ビット決定値が前記予め設定された桁数より大きい場合、前記衝突が発生した桁に前記衝突ビット決定値を順次に代入して前記ＩＤの一部を確定した推定ＩＤを生成する段階と、前記推定ＩＤを前記ＩＤ要請値に前記各タグに伝送する段階とを含むことが望ましい。
【００２１】
前記ＩＤ要請値である推定されたＩＤに対して、衝突が発生しなければＩＤを確定する段階を含むことが望ましい。
【００２２】
前記ＩＤ要請値である推定されたＩＤに対して、衝突が発生すれば前記衝突が発生した桁に対して前記衝突ビット桁値を再び生成して前記推定されたＩＤと共に前記衝突が発生したタグに伝送段階を含むことが望ましい。
【００２３】
一方、前記目的は、本発明の他の分野によれば、リーダー及びそれぞれＩＤを有する少なくとも二つのタグを含むＲＦＩＤシステムにおいて、前記各タグは、前記リーダーから要請によりＩＤを提供され、他タグとのＩＤ衝突時前記ＩＤのうち衝突が発生した桁の値を前記リーダーに提供し、前記リーダーは、前記ＩＤを形成する記号のうち少なくとも一つを含むＩＤ要請値を前記各タグに伝送して前記タグからＩＤを提供され、前記ＩＤ間の衝突が発生した場合、前記タグから前記衝突が発生した桁の値を提供されて前記ＩＤを決定することを特徴とするＲＦＩＤシステムによっても達成することができる。
【発明の効果】
【００２４】
本発明によれば、リーダーでは衝突した桁だけを表示した衝突ビット桁値を生成及び伝送し、各タグでは衝突が発生した桁だけのビットである衝突ビット決定値を生成して伝送することにより、衝突が発生した多数のＩＤの衝突ビットのパターンをそれぞれ衝突することなく認識することができる。
【００２５】
従って、一回で多数個のＩＤを認識することにより、リーダーとタグとの伝送回数を減らすことができる。また、衝突ビット決定値はＩＤの長さより短いので、伝送時消費される電力の消耗を節減させることができる。その結果、ＲＦＩＤシステムの時間及び電力効率の向上が期待できる。
【発明を実施するための最良の形態】
【００２６】
以下、添付した図面に基づき発明を実施するための最良の形態を詳述する。
図１は、本実施形態に係るＩＤ衝突防止方法が具現されるＲＦＩＤシステムの構造を示した図面である。本実施形態に係るＩＤ衝突防止方法が具現されるＲＦＩＤシステムはリーダー１０と少なくとも一つのタグ２０を含む。
【００２７】
一般に、リーダー１０にはメモリが設けられており、メモリにはタグ２０のＩＤ要請時、タグ２０に提供する２進数よりなるＩＤ要請値が記録されている。そして、メモリにはＩＤの衝突時衝突されたビットにより予想可能なタグのＩＤが記録されている。メモリはスタックやキュー（Ｑｕｅｕｅ）などで設けられ、本実施形態ではキューを例として説明する。
【００２８】
図２は、本実施形態に係るＩＤ衝突防止方法の一実施形態の表を示す図面である。
本実施形態に係るＩＤ衝突防止方法は、一つのリーダー１０と４つのタグ２０がある場合について説明する。そして、それぞれのタグ２０のＩＤは８ビットであって、ＩＤが‘１０１１０１０１’であるタグ２０をタグ１、’ＩＤが‘１０１１０１００’であるタグ２０をタグ２、ＩＤが‘１００００１００’であるタグ２０をタグ３、及びＩＤが‘１０１００００１’であるタグ２０をタグ４と称する。
【００２９】
図２に示す表は本実施形態に係るＩＤ衝突防止方法を行なう過程を示しており、表２に示された各構成要素を説明すれば次の通りである。
【００３０】
‘Ｐｒｅｆｉｘ  Ｑｕｅｕｅ  Ｉｎｔｉａｌｌｙ  ０、１’に該当する行にはキューに記録された値が表示され、キューには初期に‘０’と‘１’が入力され、各タグ２０のＩＤ間衝突が発生した後には予想可能なＩＤ値である推定ＩＤが記録される。
【００３１】
ダウンリンク（Ｄｏｗｎｌｉｎｋ）にはリーダー１０からタグ２０へ伝送されるＩＤ要請値が順次に表示され、ＩＤ要請値としてはキューに記録された値が順次に使用される。
【００３２】
アップリンク（Ｕｐｌｉｎｋ）には各タグ２０からリーダー１０へ伝送された応答ＩＤが表示され、この際衝突が発生したビットについては’Ｘ’が表示される。
【００３３】
Ｔａｇ１、Ｔａｇ２、Ｔａｇ３、Ｔａｇ４の各行は、各タグ２０のＩＤと、ダウンリンクとアップリンクの過程を通じて各タグ２０のＩＤ確認時これを表示する。  
【００３４】
本実施形態に係るＩＤ衝突防止方法により、リーダー１０が自分に属する四つのタグのＩＤ２０を認識及び判断する過程について説明する。
【００３５】
まず、リーダー１０はＩＤ要請のためにＩＤ要請値（ＩＤｒｅｑ）として‘０’と‘１’を入力する。
【００３６】
リーダー１０はＩＤ要請値‘０’をキューから出力し（この際、キューに入力され記録されているＩＤ要請値‘０’は削除される。）、各タグ１〜４にＩＤ要請値‘０’を伝送する。これに各タグ１〜４は伝送されたＩＤ要請値‘０’が自分のＩＤと一致するかを判断する。すなわち、各タグ１〜４は自分のＩＤが‘０’から始まるか否かを判断する。
【００３７】
その結果、タグ１、タグ２、タグ３、タグ４はＩＤが全て‘１’から始まるので、各タグ１〜４はそれぞれ自分のＩＤが‘０’から始まらないことを確認し、リーダー１０に応答しない。リーダー１０は、所定の時間内にタグ１〜４から応答を受けなければ、その次に生成され記録されたＩＤ要請値である‘１’を出力する（この際、キューに入力され記録されているＩＤ要請値‘１’は削除される。）。リーダー１０は各タグ１〜４にＩＤ要請値‘１’を伝送し、これに各タグ１〜４は伝送されたＩＤ要請値‘１’が自分のＩＤと一致するか否かを判断する。すなわち、各タグ１〜４は自分のＩＤが‘１’から始まるか否かを判断する。
【００３８】
その結果、四つのタグ１〜４はそれぞれ自分のＩＤが‘１’から始まることを確認し、それぞれ自分のＩＤである‘１０１１０１０１’、‘１０１１０１００’、‘１００００１００’、及び‘１０１００００１’をリーダー１０に伝送する。
【００３９】
もし、伝送されたＩＤの衝突が発生しなければ、リーダー１０は伝送されたＩＤを通じて四つのタグ１〜４のＩＤが全て確定できる。
【００４０】
しかし、図２に示すように、１番目ビットを除いた残りビットのうち、タグ１〜４で同一なビット桁にＩＤ要請値である‘１’を有するＩＤ同士は衝突が発生する。タグ１は３番目、４番目、６番目、８番目ビットが‘１’であり、タグ２は３番目、４番目、６番目ビットが‘１’であり、タグ３は６番目ビットが‘１’であり、タグ４は３番目、８番目ビットが‘１’である。これにより、３番目、４番目、６番目、８番目ビットで衝突が発生する。リーダーは衝突が発生したＩＤビットを‘Ｘ’と認識し、リーダー１０で認識されるＩＤをビットの形態で表現すれば‘１０ＸＸ０Ｘ０Ｘ’になる。
【００４１】
このように認識されたＩＤを用いて、リーダー１０は衝突ビット桁値（ＣＢＤｒｅｑ：Ｃｏｌｌｉｓｉｏｎ  Ｂｉｔ  Ｄｅｔｅｒｍｉｎａｔｉｏｎ）を生成する。ここで、衝突ビット桁値（ＣＢＤｒｅｑ）は以後に各タグ１〜４のＩＤビットのうち衝突が発生したビット桁のビットだけを伝送すべく要請するために使用される。
【００４２】
衝突ビット桁値はリーダー１０で‘Ｘ’と認識されたビット、すなわち衝突が発生したビットを‘１’で示し、衝突が発生しないビットを‘０’で示す。その結果、リーダー１０が衝突により認識したＩＤビットの形態が‘１０ＸＸ０Ｘ０Ｘ’であれば、これにより生成された衝突ビット桁値は‘００１１０１０１’になる。
【００４３】
その後、リーダー１０がＩＤの衝突を誘導したＩＤ要請値である‘１’と衝突ビット桁値‘００１１０１０１’を各タグ１〜４に伝送するようになる。ＩＤ要請値である‘１’と衝突ビット桁値‘００１１０１０１’を伝送された各タグ１〜４は、まずＩＤ要請値である‘１’が自分のＩＤと一致するか否かを確認した後、一致する場合には伝送された衝突ビット桁値‘００１１０１０１’から衝突ビット決定値を生成する。
【００４４】
ここで衝突ビット決定値は自分のＩＤのうち衝突が発生したビットだけを集めた値になる。すなわち、タグ１は伝送された衝突ビット桁値により自分の衝突ビットで‘１１１１’を生成し、タグ２は衝突ビット桁値により自分の衝突ビットで‘１１１０’を生成し、タグ３は衝突ビット桁値により自分の衝突ビットで‘００１０’を生成し、タグ４は衝突ビット桁値により自分の衝突ビットで‘１００１’を生成する。
【００４５】
このような衝突ビット決定値をタグ１〜４からリーダー１０に伝送する時、伝送することのできる衝突ビット決定値のビット数が予め設定されている。例えば、既に設定されたビット数が‘３’である場合、各タグ１〜４は生成された衝突ビット決定値のうち最後のビットを除き、前から３桁の衝突ビット決定値だけをリーダー１０に伝送する。
【００４６】
すなわち、本実施形態に係る各タグ１〜４は生成した衝突ビット決定値の伝送時、タグ１は‘１１１’を、タグ２は‘１１１’を、タグ３は‘００１’を、タグ４は‘１００’を伝送する。そして、各タグは衝突ビット決定値の伝送時、各衝突ビット決定値間の衝突を防止するため、後述する他の形態の２進符号に変換して伝送することができる。
【００４７】
前述した実施形態において衝突ビット決定値の桁数が３個なので、各タグ１〜４から伝送される衝突ビット決定値を１０進数で表現すれば、これは０から７までの整数のうち一つになる。すなわち、タグ１とタグ２の衝突ビット決定値は７であり、タグ３の衝突ビット決定値は１、タグ４の衝突ビット決定値は４である。
【００４８】
このような衝突ビット決定値を２進符号に変更する場合、衝突ビット決定値が０から７で８個であるため２進符号を８桁で生成し、衝突ビット決定値の１０進法の数に該当する位置を０または１で表示する。従って、１０進法の数で表現された衝突ビット決定値が‘０’の場合は二進符号‘００００００００’で、１０進法の数で表現された衝突ビット決定値が‘１’の場合は二進符号‘００００００１０’で、１０進法の数で表現された衝突ビット決定値が‘２’の場合は二進符号‘０００００１００’で、１０進法の数で表現された衝突ビット決定値が‘３’の場合は二進符号‘００００１０００’で、１０進法の数で表現された衝突ビット決定値が‘４’の場合は二進符号‘０００１００００’で、１０進法の数で表現された衝突ビット決定値が‘５’の場合は二進符号‘００１０００００’で、１０進法の数で表現された衝突ビット決定値が‘６’の場合は二進符号‘０１００００００’で、１０進法の数で表現された衝突ビット決定値が‘７’の場合は二進符号‘１０００００００’で設定することができる。
【００４９】
すなわち、タグ１から伝送される衝突ビット決定値である‘１１１’は１０進数で表現すれば‘７’になるため二進符号‘１０００００００’を伝送する。タグ２から伝送される衝突ビット決定値である‘１１１’は１０進数で表現すれば‘７’になるため、二進符号‘１０００００００’を伝送する。
【００５０】
タグ３から伝送される衝突ビット決定値である‘００１’は１０進数で表現すれば‘１’になるため、二進符号‘００００００１０’を伝送する。タグ４から伝送される衝突ビット決定値である‘１００’は１０進数で表現すれば‘４’になるため、二進符号‘０００１００００’を伝送する。
【００５１】
リーダー１０は衝突ビット決定値が伝送されると、リーダー１０が前述した衝突により認識したＩＤビットの形態である‘１０ＸＸ０Ｘ０Ｘ’と、伝送された衝突ビット決定値を用いて、確定可能な範囲内でＩＤを推定する。この際、リーダー１０は伝送された衝突ビット決定値を‘１０ＸＸ０Ｘ０Ｘ’のＸ桁に順次代入してＩＤを推定する。
【００５２】
すなわち、伝送された衝突ビット決定値である‘１１１’、‘００１’、及び‘１００’を各Ｘ桁に順次代入すれば、‘１０１１０１０’、‘１００００１０’、及び‘１０１００００’がＩＤとして推定される。この際、各タグ２０から３桁の衝突ビット決定値を提供されたので、最後のＸ桁を除いた７ビットの桁だけを有するＩＤが推定される。その後、リーダー１０は推定されたＩＤである‘１０１１０１０’、‘１００００１０’、及び‘１０１００００’をＩＤ要請値としてキューに記録する。
【００５３】
‘１０１１０１０’がＩＤ要請値になると、タグＩＤが‘１０１１０１０’から始まる全てのタグ１〜４は自分のＩＤをリーダー１０に伝送する。
【００５４】
つまり、リーダー１０は生成したＩＤ要請値のうち最先に生成し、キューに記録したＩＤ要請値である‘１０１１０１０’を出力する（この際、キューに入力され記録されたＩＤ要請値‘１０１１０１０’は削除される。）。リーダー１０は各タグ１〜４にＩＤ要請値‘１０１１０１０’を伝送し、これに各タグ１〜４は伝送されたＩＤ要請値‘１０１１０１０’が自分のＩＤと一致するか否かを確認する。すなわち、各タグ１〜４は自分のＩＤが‘１０１１０１０’から始まるか否かを確認する。
【００５５】
その結果、四つのタグ１〜４のうちタグ１とタグ２はそれぞれ自分のＩＤが‘１０１１０１０’から始まることを確認し、それぞれ自分のＩＤである‘１０１１０１０１’、及び‘１０１１０１００’をリーダー１０に伝送するようになる。
【００５６】
もし、伝送したＩＤの衝突が発生しなければ、リーダー１０は伝送したＩＤを通じてタグ１とタグ２のＩＤを全て確定する。
【００５７】
しかし、本実施形態によれば、リーダー１０では伝送されたＩＤの衝突が生じ、リーダー１０は衝突が発生したＩＤビットを‘Ｘ’と認識する。これをＩＤビットの形態で表現すれば‘１０１１０１０Ｘ’になる。
【００５８】
これにより、リーダー１０は衝突ビット桁値（ＣＢＤｒｅｑ：Ｃｏｌｌｉｓｉｏｎ  Ｂｉｔ  Ｄｅｔｅｒｍｉｎａｔｉｏｎ）を再び生成するようになる。衝突ビット桁値（ＣＢＤｒｅｑ）は、前述した衝突ビット桁値と同様、追って各タグ１〜４のＩＤのビットのうち衝突が発生したビットだけを伝送すべく要請するために使用される。
【００５９】
前述した衝突ビット桁値は‘Ｘ’で認識された衝突が発生したビットを‘１’で表示し、衝突が発生しないビットを‘０’で表示する。その結果、リーダー１０が衝突により認識したＩＤビットの形態が‘１０１１０１０Ｘ’であれば、これにより生成された衝突ビット桁値は‘０００００００１’になる。
【００６０】
その後、リーダー１０はＩＤの衝突を誘導したＩＤ要請値である‘１０１１０１０’と衝突ビット桁値‘０００００００１’を各タグ１〜４に伝送するようになる。ＩＤ要請値である‘１０１１０１０’と衝突ビット桁値‘０００００００１’を伝送された各タグ１〜４は、まずＩＤ要請値である‘１０１１０１０’が自分のＩＤと一致するか否かを確認した後、一致する場合は伝送した衝突ビット桁値‘０００００００１’から衝突ビット決定値を生成する。
【００６１】
ここで衝突ビット決定値は自分のＩＤのうち衝突が発生したビットだけを集めた値になる。すなわち、タグ１は伝送された衝突ビット桁値により自分の衝突ビット決定値として‘１’を生成し、タグ２は衝突ビット桁値により自分の衝突ビット決定値として‘０’を生成する。
【００６２】
ここでも、タグ１とタグ２は自分の衝突ビット決定値を伝送するに当たって、既に設定されたビット数により制限される。すなわち、衝突ビット決定値を伝送するに当たって、既に設定されたビット数である‘３’より衝突ビット決定値が大きくないため、それぞれ‘１’、‘０’を衝突ビット決定値として伝送する。この場合はタグ１とタグ２のＩＤで発生した衝突ビット決定値が既に設定されたビット数より大きくないので、リーダー１０は伝送された衝突ビット決定値である‘１’と‘０’によりタグ１とタグ２のＩＤをそれぞれ‘１０１１０１０１’と‘１０１１０１００’と確定する。
【００６３】
またここでも、タグ１とタグ２は衝突ビット決定値を伝送するに当たって、各衝突ビット決定値を前述した方法により他の形態の２進形態に変換して伝送することもできる。
【００６４】
すなわち、タグ１から伝送される衝突ビット決定値である‘１’は１０進数で表現すれば‘１’になるため、二進符号‘００００００１０’を伝送する。タグ２から伝送される衝突ビット決定値である‘０’は１０進数で表現すれば‘０’になるため、二進符号‘００００００００’を伝送する。
【００６５】
タグ１とタグ２のＩＤを確定した後、リーダー１０は２番目に生成されキューに記録されたＩＤ要請値である‘１００００１０’を出力する（この際、キューに入力され記録されたＩＤ要請値‘１００００１０’は削除される。）。リーダー１０は各タグ１〜４にＩＤ要請値‘１００００１０’を伝送し、これに各タグ１〜４は伝送されたＩＤ要請値‘１００００１０’が自分のＩＤと一致することを確認する。すなわち、各タグ１〜４は自分のＩＤが‘１００００１０’から始まるか否かを確認する。
【００６６】
その結果、四つのタグ１〜４のうちタグ３は自分のＩＤが‘１００００１０’から始まることを確認し、自分のＩＤである‘１００００１００’がリーダー１０に伝送される。
【００６７】
この場合、伝送されたＩＤの衝突が発生しないので、リーダー１０は伝送されたＩＤを通じてタグ３のＩＤを‘１００００１００’と確定する。
【００６８】
タグ３のＩＤを確定した後、リーダー１０は３番目に生成されキューに記録されたＩＤ要請値である‘１０１００００’を出力する（この際、キューに入力され記録されたＩＤ要請値‘１０１００００’は削除される。）。
【００６９】
リーダー１０は各タグ１〜４にＩＤ要請値‘１０１００００’を伝送し、これに各タグ１〜４は伝送されたＩＤ要請値‘１０１００００’が自分のＩＤと一致するか否かを確認する。すなわち、各タグ１〜４は自分のＩＤが‘１０１００００’から始まるか否かを確認する。その結果、四つのタグ１〜４のうちタグ４は自分のＩＤが‘１０１００００’から始まることを確認し、自分のＩＤである‘１０１００００１’をリーダー１０に伝送する。この場合、伝送されたＩＤの衝突が発生しないので、リーダー１０は伝送されたＩＤを通じてタグ４のＩＤを‘１０１００００１’と確定する。
【００７０】
図３Ａは本発明に係るＲＦＩＤシステムにおけるリーダーの動作原理を示したフローチャートである。
【００７１】
まず、リーダー２０は、キューに‘０’及び‘１’をＩＤ要請値として入力し、タグ１〜４が伝送する衝突ビット数（Ｎ）を設定する（Ｓ５００）。
【００７２】
その後、キューが空いている（キューにＩＤ要請値が記録されていない）か否かを確認した後（Ｓ５０５）、キューが空いていると確認されれば（ステップＳ５０５で、「ＹＥＳ」）、タグ１〜４のＩＤ確定動作を終了する。
【００７３】
キューが空いていない場合（ステップＳ５０５で、「ＮＯ」）、キューに入力され記録されたＩＤ要請値‘０’を出力し、タグ１〜４に伝送してＩＤ要請値に一致するＩＤの伝送を要請する（Ｓ５１５）。この際キューに入力され記録されたＩＤ要請値の‘０’はキューから出力されながらキューから削除される。
【００７４】
リーダー２０はＩＤ要請値‘０’に一致するＩＤの伝送があるか否かを確認した後（Ｓ５２０）、ＩＤの伝送がない場合（ステップＳ５２０で、「ＮＯ」）は、再び前述したステップＳ５０５に戻って、キューが空いているか否かを確かめる。
【００７５】
キューが空いていないと確認されれば（ステップＳ５０５で、「ＮＯ」）、キューに記録されているＩＤ要請値‘１’を出力し、タグ１〜４に伝送してＩＤ要請値に一致するＩＤの伝送を要請する（Ｓ５１５）。この際、キューに入力され記録されたＩＤ要請値‘１’はキューから出力されながらキューから削除される。
【００７６】
リーダー２０はＩＤ要請値に一致するＩＤの伝送の存否を確認した後（Ｓ５２０）、ＩＤの伝送がある場合（ステップＳ５２０で、「ＹＥＳ」）は伝送されたＩＤの衝突の発生有無を確認する（Ｓ５２５）。
【００７７】
伝送されたＩＤの衝突が発生しない場合（ステップＳ５２５で、「ＮＯ」）は、伝送されたＩＤによりタグのＩＤを確定し（Ｓ５３０）、再び前述したＳ５０５段階に戻る。
【００７８】
伝送されたＩＤの衝突が発生した場合（ステップＳ５２５で、「ＹＥＳ」）は、衝突ビット桁値を生成し、生成された衝突ビット桁値及びＩＤ要請値を共に伝送する（Ｓ５３５）。
【００７９】
その後、リーダー１０は衝突が発生したＩＤの衝突ビット決定値を受信するようになり（Ｓ５４５）、衝突が発生したＩＤのビット数が前述したＳ５００段階で設定した伝送される衝突ビット数（Ｎ）より大きい値であるか否かを確認する（Ｓ５５０）。
【００８０】
ＩＤ衝突が発生したビット数が衝突ビット数（Ｎ）より大きくない場合（ステップＳ５５０で、「ＮＯ」）は、リーダー１０は受信した衝突ビット決定値によりそれぞれのＩＤを確定し（Ｓ５５５）、前述したＳ５０５段階に戻る。
【００８１】
ＩＤ衝突が発生したビット数がＮより大きい場合（ステップＳ５５０で、「ＹＥＳ」）、リーダー１０は受信した衝突ビット決定値を用いて、新たなＩＤ要請値を生成し、これをキューに記録する（Ｓ５６０）。その後再び前述したＳ５０５段階に戻る。
【００８２】
つまり、キューに記録されたＩＤ要請値が存在しなくなるまで、前述したＳ５０５ないしＳ５６０までのステップは繰り返し、キューに記録されたＩＤ要請値が存在しなくなれば、リーダー１０は全てのタグ１〜４のＩＤを確定した状態と判断する。
【００８３】
図３Ｂは本実施形態に係るＲＦＩＤシステムにおけるタグの動作原理を示したフローチャートである。
【００８４】
タグ１〜４はリーダー１０からのメッセージの送信されるまで待機する（Ｓ５６５）。タグ１〜４はリーダー１０のＩＤ要請値を受信したか否かを確認する（Ｓ５７０）。ＩＤ要請値を受信しない場合（Ｓ５７０で、「ＮＯ」）は、引き続きメッセージ待ち状態を維持する（Ｓ５６５）。
【００８５】
ＩＤ要請値を受信した場合（Ｓ５７０で、「ＹＥＳ」）は、ＩＤ要請値がタグＩＤと一致するか否か判断する（Ｓ５７５）。
【００８６】
受信したＩＤ要請値がタグＩＤと一致しない場合は再び待ち状態を維持し（Ｓ５６５）、受信したＩＤ要請値がタグＩＤと一致する場合は、ＩＤ要請値だけを受信したか、あるいはＩＤ要請値と衝突ビット桁値を全て受信したかを確かめる（Ｓ５８０）。
【００８７】
その結果、ＩＤ要請値だけを受信したならば（Ｓ５８０で、「ＮＯ」）、タグ１〜４は自分のＩＤを伝送する（Ｓ５８５）。
ＩＤ要請値と衝突ビット桁値を全て受信したならば（Ｓ５７０で、「ＹＥＳ」）、衝突ビット決定値を生成した後、最大限多数のビット数の衝突ビット決定値を予め設定されたビット数の範囲内で伝送する（Ｓ５９０）。衝突ビット決定値を伝送していないタグ１〜４は再び待ち状態に戻る（Ｓ５６５）。
【００８８】
図４は従来の技術と本実施形態に係るＩＤ衝突防止方法の実験結果を比較したグラフを示す図面である。
【００８９】
図４に示した実験では９６ビットＩＤを使用し、タグにより伝送される衝突ビット決定値のビット数は６で設定した。タグの個数が増えることによって、要請及び応答の回数が線形的に増加するが、従来のＩＤ衝突防止方法に係る要請及び応答回数の増加（５００）の傾きより本実施形態に係るＩＤ衝突防止方法に係る要請及び応答回数の増加（５５０）がその増加の傾きが小さいことを確認することができる。
【００９０】
タグの数がさらに増加すれば、本実施形態に係るＩＤ衝突防止方法に係る要請及び応答の回数は従来のＩＤ衝突防止方法に比べて著しく減少することが分かる。
【００９１】
図５は本実施形態に係るＩＤ衝突防止方法の他の実験結果のグラフを示す図面である。
図５に示す実験では９６ビットＩＤを使用したし、タグの個数は１０００と設定し、タグにより伝送される衝突ビット決定値のビット数を１から１７まで増加させながら、リーダーとタグとの間の要請及び応答の回数を測定した。その結果、タグにより伝送される衝突ビット決定値のビット数が６と設定された場合に要請及び応答の回数が最小数で測定された。これを通じて、９６ビットのＩＤを使用する場合はタグにより伝送される衝突ビット決定値の桁数を６と設定することが本発明の最も効率的な具現方法であることを確認することができる。
【００９２】
なお、発明を実施するための最良の形態では、４つのタグを用いて説明したが、タグの個数は複数であればよい。
また、本発明の技術的範囲は、特許請求の範囲に基づいて定められ、発明を実施するための最良の形態により限定して解釈されない。
【図面の簡単な説明】
【００９３】
【図１】本発明に係るＩＤ衝突防止方法が具現されるＲＦＩＤシステムの構造を示した図である。
【図２】本発明に係るＩＤ衝突防止方法の一実施形態を示す表である。
【図３Ａ】本実施形態に係るＲＦＩＤシステムにおけるリーダーの動作原理を示したフローチャートである。
【図３Ｂ】本実施形態に係るＲＦＩＤシステムにおけるタグの動作原理を示すフローチャートである。
【図４】従来の技術と本実施形態に係るＩＤ衝突防止方法の実験結果を比較したグラフを示すフローチャートである。
【図５】本実施形態に係るＩＤ衝突防止方法の他の実験結果のグラフを示す図面である。
【図１】
2006338675.tif 000003
【図２】
2006338675.tif 000004
【図３Ａ】
2006338675.tif 000005
【図３Ｂ】
2006338675.tif 000006
【図４】
2006338675.tif 000007
【図５】
2006338675.tif 000008