無線タグリーダ、無線タグシステム、プログラムおよび無線通信方法
【課題】 検出可能領域内の無線タグを短時間で検出する。
【解決手段】 各々タグ情報を保持した複数の無線タグと、無線タグリーダとが通信する。前記無線タグリーダが、前記複数の無線タグに読み出し要求信号を同時に送信し、各前記無線タグが、あらかじめ保持する、前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信し、前記無線タグリーダが、前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得し、前記衝突ブルームフィルタ信号を復号して各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得し、前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証する。
【解決手段】 各々タグ情報を保持した複数の無線タグと、無線タグリーダとが通信する。前記無線タグリーダが、前記複数の無線タグに読み出し要求信号を同時に送信し、各前記無線タグが、あらかじめ保持する、前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信し、前記無線タグリーダが、前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得し、前記衝突ブルームフィルタ信号を復号して各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得し、前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線タグリーダ、無線タグシステム、プログラムおよび無線通信方法に関する。
【背景技術】
【０００２】
近年、物品の効率的な管理を行うために無線タグシステムを導入するケースが増えてきている。無線タグシステムでは、管理対象となる物品に埋め込まれるRFIDタグと、RFIDタグからデータを読み出すリーダライタとを使用する。この無線タグシステムにおいて、リーダライタによるデータ読出し時に、複数のRFIDタグから同時に応答があると、データの衝突（コリジョン）が発生する問題がある。
【０００３】
従来におけるアンチコリジョン（Anti-Collision） 技術としては、ALOHA 系と二分木探索とが有力であった。
【０００４】
ALOHA 系は、リーダライタ が、RFIDタグへの問い合わせに対する返答信号に衝突を検出した場合、RFIDタグのタグID の最上位ビット（MSB） から順番に条件を絞った問い合わせを行い、衝突の原因となるRFIDタグのうち1つのみが反応する条件になるまでこれを繰り返す方式である。このALOHA系は、RFIDタグに搭載すべきロジック回路が簡易である点が特徴である。しかし、この方式では、同時に反応するRFIDタグが１つになるまで、複数ステップによる絞り込み手続きを行うため、ステップ数が多くなると読み出しに時間がかかるという欠点がある。
【０００５】
一方、二分木探索は、異なるタグID を持つRFIDタグが同時に応答した場合に、タグID のうち差分部分（ビット値が異なる部分）のみがリーダライタ によって衝突信号として検出でき、且つ、共通部分（ビット値が同一の部分）についてはそのまま読み出しが可能である符号化方式の場合に適用できる。例えばマンチェスター符号化の場合は、0と1とが同時に送信された場合は衝突を検出できる。この二分木探索を用いる場合も、複数ステップによる絞り込み手続きを行うため、ステップ数が多くなると読み出しに時間がかかるという欠点がある。
【０００６】
以上の他、従来におけるアンチコリジョン技術を示した文献として特開2004-62665号（特許文献１）がある。
【０００７】
この特許文献１におけるアンチコリジョン機構は、従来のアルゴリズム(JIS-X6323-3, ISO/IEC15693-3) をベースに、衝突が発生した場合はRFIDタグの応答スロット開始位置をずらすという簡易なアルゴリズムで、アンチコリジョン機能を実現する。単にスロットをずらしただけでは再び衝突が起きる可能性があるが、十分なID 空間があれば(特許文献１の説明では56bit 以上としている) 再び衝突が起きる可能性は低く、数回の試行でタグID が取得できるとしている。
【０００８】
しかし、この特許文献１に記載の技術でも、数回の試行でタグIDを１つ取得できるのみである。従って、リーダライタによる検出可能領域内の全てのRFIDタグからタグIDを取得するには、すなわち、検出可能領域内に存在する全てRFIDタグを検出するには、多くの時間を要するという問題がある。
【特許文献１】特開2004-62665公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、検出可能領域内に存在する無線タグを短時間で検出できる無線タグリーダ、無線タグシステム、プログラムおよび無線通信方法を提供する。
【課題を解決するための手段】
【００１０】
本発明の一態様としての無線タグリーダは、各々タグ情報と前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタとを保持した複数の無線タグと通信する無線タグリーダであって、前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段と、前記複数の無線タグの各々からのブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得する受信手段と、前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段と、タグ情報を格納するデータ格納手段と、前記合成ブルームフィルタに対し前記データ格納部内のタグ情報を検証するフィルタ検証手段と、を備える。
【００１１】
本発明の一態様としての無線タグシステムは、複数の無線タグと前記複数の無線タグと通信する無線タグリーダとを備えた無線タグシステムであって、各前記無線タグは、前記タグ情報と、前記タグ情報からブルームフィルタアルゴリズムにより生成されたブルームフィルタとを格納したメモリ手段と、前記無線タグリーダから前記ブルームフィルタの読み出し要求を受けた場合は、前記メモリ手段内の前記ブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信する応答手段と、を有し、前記無線タグリーダは、前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段と、前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタを取得する受信手段と、前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段と、タグ情報を格納するデータ格納手段と、前記合成ブルームフィルタに対し前記データ格納部内のタグ情報を検証するフィルタ検証手段と、を有した、ことを特徴とする。
【００１２】
本発明の一態様としてのプログラムは、各々タグ情報と前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタとを保持した複数の無線タグと通信する手段としてコンピュータを機能させるプログラムであって、前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段、前記複数の無線タグの各々からのブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得する受信手段、前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段、前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証するフィルタ検証手段、として前記コンピュータを機能させる。
【００１３】
本発明の一態様としての無線通信方法は、各々タグ情報を保持した複数の無線タグと、無線タグリーダとが通信する無線通信方法であって、前記無線タグリーダが、前記複数の無線タグに読み出し要求信号を同時に送信し、各前記無線タグが、あらかじめ保持する、前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信し、前記無線タグリーダが、前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を得、前記衝突ブルームフィルタ信号を復号して各前記ブルームフィルタの論理和をとった合成ブルームフィルタを得、前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証する、ことを特徴とする。
【発明の効果】
【００１４】
本発明により、検出可能領域内に存在する無線タグを短時間で検出できる。
【発明を実施するための最良の形態】
【００１５】
図１は、本発明の実施の形態に従った無線タグシステムの構成を概略的に示すブロック図である。
【００１６】
この無線タグシステムは、複数のRFIDタグ１１と、検出可能領域２１に存在するRFIDタグ１１と通信するリーダライタ３１と、リーダライタ３１に対し検出可能領域２１内に存在するRFIDタグを検出することを指示するアプリケーション装置４１とを備える。
【００１７】
RFIDタグ１１は、メモリ部１２と、リーダライタ３１からの読み出し要求に応じてメモリ部１２内のデータを読み出し読み出したデータをリーダライタ３１に返すタグ回路１３とを備える。
【００１８】
メモリ部１２内には、RFIDタグ１１に固有に割り当てられたタグIDと、このタグIDから生成されたブルームフィルタ（後述）と、ブルームフィルタのビット列から生成されたCRCまたはパリティとが格納されている。この他、メモリ部１２内には、RFIDタグ１１が取り付けられる物品の物品情報 (例えば服飾品のサイズ等)が格納されてもよい。
【００１９】
RFIDタグ１１におけるタグ回路１３は、リーダライタ３１からの読み出し要求を受けると、メモリ部１２内のブルームフィルタと、CRC、パリティまたはIDタグとを読み出し、符号化および変調を施して、リーダライタ３１に送信する。ブルームフィルタのみを送信しても良い。送信の際の変調方式としては、例えばＡＳＫ、ＦＳＫ等を用いることができる。
【００２０】
図２（Ａ）は、RFIDタグ１１からリーダライタ３１へ送信するデータ内容の一例を示す。図２（Ｂ）は、図２（Ａ）のデータをNRZ符号化して生成した符号化信号を示し、この符号化信号がさらに変調されることでリーダライタ３１に送信される。
【００２１】
符号化方式には、他の送信信号との衝突時に、ビット単位でＯＲ演算となることが要求される。上記NRZ符号化方式にはこの性質を持たせることができる。なお、データの送信方向は、ブルームフィルタ側およびCRC（orタグID）側のどちらからでも良い。
【００２２】
ここでブルームフィルタについて簡単に説明する。なお、ブルームフィルタの詳細については、Broder et al., Network Applications of Bloom Filters: A Survey 等を参照されたい。
【００２３】
ブルームフィルタとは、ある任意のデータdがデータ集合X に含まれるかどうかをハッシュ関数の応用により確率的に検査するためのフィルタである。
【００２４】
データ集合Xより生成されたブルームフィルタBF-Xに対して、定められた手続きを行うことで、あるデータd がデータ集合Xに含まれるか否かを「検証」することができる。手続きの結果、positive(陽性) ないしnegative(陰性) という２通りの結果が得られる。
【００２５】
陰性の結果が得られた場合は、データ集合X にデータd が含まれている可能性は無い。一方、陽性の結果が得られた場合は、データ集合Xにデータd が含まれる可能性が高い。すなわち、陽性の結果が得られても、必ずしもデータ集合X にデータd が含まれているとは限らない。データ集合Xにデータdが含まれていないにも拘わらず陽性の結果が得られる場合を偽陽性と呼ぶ。
【００２６】
以下、このような性質を有するブルームフィルタの生成方法について説明する。
【００２７】
ブルームフィルタの生成には以下のパラメータを用いる。
【００２８】
・m：フィルタの長さ
・k：繰り返し回数（用意するハッシュ関数の個数）
ブルームフィルタの生成は以下の手順に従う。
【００２９】
（１）ブルームフィルタの生成手順
１．長さmのビット列Fを用意し、全て0にセットする。
２．値域が[1,m] となる、k 個の独立したハッシュ関数hn() (ただしn=1・・・k ) を用意する。同一のハッシュアルゴリズムに対してそれぞれ異なる定数(salt) を与えることでk 個の独立したハッシュ関数hn()を用意しても良い。
３．入力データ集合X の各要素xi に対して、次の処理を行う。
(a) p = 1 とする
(b) もしp > k ならば終了
(c) ２．で用意したハッシュ関数hp() を用い、idx ＝ hp(xi) を計算
(d) ビット列F のidx ビット目を1 にする（既に１が立っていた場合は、ビット値をそのまま１とする）
(e) p に1 を加える
(f) 手順３．(b) へ戻る
【００３０】
要するに、入力データ集合Ｘの要素xiの各々について、ｋ個のハッシュ関数からそれぞれハッシュ値idxを求め、ビット列Ｆのidxビット目にそれぞれ１を立てることでブルームフィルタを生成する。
【００３１】
次に、入力データ集合Xにデータdが含まれるか否かの検証（フィルタ検証）は以下の手順で行う。
【００３２】
（２）フィルタ検証の手順
１．p = 1 とする。
２．もしp>k ならば陽性を返す。
３．検証したいデータd について、idx ＝ hp(d)を計算。
４．ビット列F のidx ビット目を調べ、0 ならば陰性を返す。
５．p に1 を加える。
６．手順２．に戻る。
【００３３】
要するに、k個のハッシュ関数にそれぞれデータｄを入力し、各々のハッシュ関数の出力idxに対応するビット位置が全て１であれば陽性を返し、各々のハッシュ関数の出力idxに対応するビット位置の少なくともいずれかが０であれば陰性を返す。
【００３４】
ここで、偽陽性が発生する場合、すなわち、データ集合Xにデータdが含まれないにも拘わらず手順２．において陽性が返される場合は、各々のハッシュ関数の出力idxに対応するビット位置がたまたま全て１であった場合である。例えばデータAおよびデータBからなるデータ集合Yから生成されたブルームフィルタBF-Yがあるとする。このブルームフィルタBF-Yにおける１の位置、すなわちデータAに基づく１の位置とデータBに基づく１の位置とのＯＲをとった位置が、データｄに基づく１の位置を包含する場合がある。このような場合に、ブルームフィルタBF-Yを用いてデータdの検証を行うと、偽陽性が発生することとなる。
【００３５】
ここで、偽陽性の発生確率Rfp は、Rfp=sk・・・（式１）として表される。ただし、sはブルームフィルタ内の全ビットのうち1 になっているビットの比率を表すサチュレーション（saturation）である。例えば、k = 10 かつs = 0.5の場合はRfp = 0.510となる。
【００３６】
上述したように、RFIDタグ１１におけるメモリ部１２内には、RFIDタグ１１のタグIDから生成されたブルームフィルタが格納されている。つまり、このブルームフィルタは１つのデータ（タグID）から生成されたものである。なお、タグID からのブルームフィルタの生成では、フィルタ長mに対し、用意するハッシュ関数の個数kが小さく設定されることが好ましい。この場合、生成されるブルームフィルタのビットのほとんどが0となる。
【００３７】
図１において、リーダライタ３１における制御部３２は、アプリケーション装置４１からRFIDタグの検出指示を受け取ると、RFIDタグ１１と通信を行う通信部３３に対し、検出可能領域２１内のRFIDタグ１１からデータを読み出すことを指示する。
【００３８】
通信部３３は、検出可能領域２１に読み出し要求信号を送信する。通信部３３は、読み出し要求信号を受け取った単数または複数のRFIDタグ１１から返されるデータ信号を受信する。通信部３３は、受信したデータ信号を復調および復号する。複数のRFIDタグ１１からデータ信号が返された場合、すなわち通信部３３が複数のRFID１１からのデータ信号を同時に受信した場合、衝突（コリジョン）が発生する。
【００３９】
図３は、２つのRFIDタグ１１（第１および第２のRFIDタグ）から同時に応答があった場合に生じるコリジョンを説明する図である。
【００４０】
図３（Ａ）は、各RFIDタグの送信データの内容を示す。図３（Ｂ）は第１のRFIDタグの送信データをNRZ符号化して生成した符号化信号を示す。図３（Ｃ）は第２のRFIDタグの送信データをNRZ符号化して生成した符号化信号を示す。図３（Ｄ）は通信部３３において受信された衝突信号を復調して得た符号化信号（観測信号）を示す。
【００４１】
図３（Ｄ）から理解されるように、通信部３３において得た符号化信号は、第１のRFIDタグから送信されたNRZ符号化信号と、第２のRFIDタグから送信されたNRZ符号化信号とのOR合成値となる。
【００４２】
以降の説明では、通信部３３は、ブルームフィルタとCRCとからなるデータを、単数のRFIDタグ１１から受信、または複数のRFIDタグ１１から同時に受信したとする。
【００４３】
通信部３３は、受信したデータ（単数のRFIDタグ１１からのデータまたは複数のRFIDタグ１１からのデータをOR合成した合成データ）におけるCRC（受信CRC）と、受信したデータにおけるブルームフィルタ（受信フィルタ）とが整合するか否かを検査する。
【００４４】
整合する場合は、通信部３３は、単数のRFID１１タグからデータを受信したと（コリジョンが発生していないと）判断し、整合しない場合は複数のRFID１１タグからデータを受信したと（コリジョンが発生したと）判断する。通信部３３が、複数のRFIDタグ１１からデータを受信したと判断した場合、受信CRCは、各RFIDタグ１１からのCRCのOR合成値（合成CRC）となり、受信フィルタは、各RFIDタグ１１からのブルームフィルタのOR合成値（合成フィルタ）となる。通信部３３は、コリジョンの発生の有無を制御部３２に通知し、また、コリジョンの発生の有無と受信フィルタとをフィルタ検証部３４に渡す。
【００４５】
リーダライタ３１におけるデータ格納部３５は、既知のタグIDを複数格納している。また、データ格納部３５内には、タグIDの各々から生成されたブルームフィルタが、各タグIDに対応づけられて格納されている。なお、RFIDタグの生産時には、全く同じフィルタが生成されるタグID を持つRFIDタグを排除するように管理することが望ましい。
【００４６】
フィルタ検証部３４は、通信部３３からコリジョンが発生している旨を受け取った場合は、上述したフィルタ検証の手順に従い、受信フィルタ（合成フィルタ）に対してデータ格納部３５内の各タグIDを検証する。フィルタ検証部３４は、検証の結果が陽性であるタグIDを全て検出し、検出したタグIDを制御部３２に渡す。
【００４７】
ここで、フィルタ検証部３４は、フィルタ検証の際、合成フィルタにおいて参照したビット位置を記憶しておく。フィルタ検証部３４は、フィルタ検証の後、合成フィルタにおいて参照されなかったビット位置が存在するか否かを検査し、存在する場合、そのビット位置に１が立っているか否かを検査する。フィルタ検証部３４は、１が立っている場合、未知のタグIDを持つRFIDタグ１１が検出可能領域２１内に存在することを決定する。ただし、ハッシュ衝突が発生した場合は、未知のタグIDを持つRFIDタグ１１が存在したとしてもその存在が隠れてしまう可能性がある。すなわち、既知の複数のタグIDによる複数のブルームフィルタのOR合成値が、ある未知のタグIDによるブルームフィルタを包含する場合は、仮に未知のタグIDを持つRFIDタグが存在したとしても、その存在が隠れてしまう。フィルタ検証部３４は、未知のタグIDを持つRFIDタグ１１が存在すると判断した場合は、その旨を制御部３２に通知しても良い。
【００４８】
一方、フィルタ検証部３４は、通信部３３からコリジョンが発生していない旨を受け取った場合は、受信フィルタと同一のフィルタを持つタグIDをデータ格納部３５から検出し、検出したタグIDを制御部３２に渡す。なお、上述と同様に、この受信フィルタに対してデータ格納部３５内の各タグIDを検証して、検証の結果が陽性であるタグIDを検出し、検出したタグIDを制御部３２に渡しても良い。
【００４９】
制御部３２は、フィルタ検証部３４から受け取ったタグIDと、通信部３３から受け取ったコリジョンの発生の有無とを、アプリケーション装置４１に渡す。制御部３２は、フィルタ検証部３４から未知のタグIDを持つRFIDタグ１１が存在する旨を受けとった場合は、その旨もアプリケーション装置４１に渡す。
【００５０】
以上では、RFIDタグ１１から読み出すデータはブルームフィルタおよびCRCである例を説明したが、RFIDタグ１１から読み出すデータがブルームフィルタおよびタグIDである場合は例えば以下のようになる。
【００５１】
通信部３３は、単数のRFIDタグ１１からのデータ、または複数のRFIDタグ１１からのデータをOR合成した合成データにおける、受信フィルタおよび受信タグIDをフィルタ検証部３４に渡す。
【００５２】
フィルタ検証部３４は、受信タグIDと同一のタグIDがデータ格納部３５に存在するか否かを検査し、存在しない場合はコリジョンが発生したと判断する。この場合、フィルタ検証部３４は、受信フィルタに対してデータ格納部３５内の各タグIDを検証する。フィルタ検証部３４は、検査の結果、陽性であった全てのタグIDと、コリジョンが発生した旨とを、制御部３２に渡す。
【００５３】
一方、フィルタ検証部３４は、受信タグIDと同一のタグIDがデータ格納部３５に存在する場合は、コリジョンが発生していないと判断する。この場合、フィルタ検証部３４は、このタグIDと、コリジョンが発生していない旨とを制御部３２に渡す。これによりフィルタ検証等を行わずに済むため、処理を高速化できる。
【００５４】
制御部３２は、フィルタ検証部３４から受け取ったタグIDと、コリジョンの発生の有無とをアプリケーション装置４１へ返す。
【００５５】
ところで、上述したように、フィルタ検証部３４におけるフィルタ検証では、偽陽性が発生し得る。偽陽性発生確率Rfpは、上記（式１）に示したように、受信フィルタ（例えば合成フィルタ）のサチュレーション（１の占める割合）sと、ブルームフィルタ生成時に用いるハッシュ関数の個数kとを用いて、Rfp=skとして、計算できる。
【００５６】
そこで、本実施の形態では、この偽陽性発生確率Rfpを用いて、受信フィルタの品質がアプリケーションの要求を満たすか否かを判断する。より詳細には、アプリケーション装置４１からリーダライタ３１に偽陽性発生数許容閾値ANFP(acceptable numberof false positives)を与え、この偽陽性発生数許容閾値ANFPと、データ格納部３５内の既知のタグIDの数（Nとする）と、上記偽陽性発生確率Rfpとに基づき、受信フィルタの品質がアプリケーションの要求を満たすか否かを判断する。以下これについてさらに詳しく説明する。
【００５７】
制御部３２は、アプリケーション装置４１から偽陽性発生数許容閾値ANFPを受け取る。
【００５８】
また、制御部３２は、フィルタ検証部３４から受信フィルタを受け取り、上記（式１）に従って、偽陽性発生確率Rfpを計算する。kの値は例えばあらかじめフィルタ検証部３４に保持されている。
【００５９】
また、制御部３２は、データ格納部３５に格納されたタグIDの数Nをあらかじめ保持しているか、またはタグIDの数Nをフィルタ検証部３４から受け取る。
【００６０】
制御部３２は、計算した偽陽性発生確率Rfp と、既知のタグIDの数Nとを乗算して偽陽性発生の期待値E（=Rfp×N）を計算する。制御部３２は、計算した期待値Eと、偽陽性発生数許容閾値ANFPとを比較する。期待値Eが偽陽性発生数許容閾値ANFP を上まわる場合は、既存の衝突回避方式またはこれに類似した方式を用いて、同時に応答するRFIDタグの個数を制限する。例えば、リーダライタ３１は、受信フィルタのサチュレーションsを下げるため、タグIDにおける特定ビット（例えば最上位ビット）が0であるRFIDタグのみが返答することを要請する読み出し要求信号を送信する。この結果、検出可能領域に存在するRFIDタグのうち、応答するRFIDタグをおよそ半数にできる。これにより、品質の高い受信フィルタを得ることができる。受信フィルタの品質が極端に悪い場合は、複数ビットを条件付けすることにより反応するRFIDタグの数をさらに絞り込んでもよい。
【００６１】
ただし、条件付けするビット数が１個の場合は２回、２個の場合は４回、３個の場合は８回と、条件付けするビット数が多くなるほど、多くの読み出し回数が必要になる。すなわち、条件付けするビット数が多すぎると、本実施の形態の利点であるRFIDタグ検出の高速さを損なう可能性がある。このため、RFIDタグが保有するブルームフィルタ長を十分長いものとして、十分多数のRFIDタグからの同時読み出しを行った場合でも、受信フィルタのサチュレーションが十分低くなるようにすることが望ましい。
【００６２】
以上に説明した本実施の形態では、タグIDから生成されたブルームフィルタと、CRC（orタグID、パリティ）とをRFIDタグから読み出したが、これに代えて、以下のようにしても良い。例えば、物品情報から生成したブルームフィルタをRFIDタグに格納しておき、RFIDタグからブルームフィルタと物品情報（またはCRC、パリティ）とを読み出すようにしても良い。この場合、各RFIDタグの物品情報を格納した格納部をリーダライタ内に設けておく必要がある。これについては、以降に説明する実施例（第２の例）において、詳しく説明する。
【００６３】
以下に、本発明の代表的な実施例を２つ示す。
【００６４】
（第１の例：パレットIDの読み出しによる検品の例）
物流過程において、検品は手間がかかる重要な作業の一つである。一方で、物流の各段階におけるコスト圧縮や速度の向上への要求は非常に強い。ここで、RFIDタグを用いて検品を行う方式を考える。例えば、部品等の検品を行う場合に、部品を格納するパレットにRFID タグを格納する。
【００６５】
ここで、部品やパレットが十分に大きい場合は、リーダライタが同時に読み取れるタグの個数は少ないため、個々に読み出しを行ってもそれほど大きな時間がかかるわけではない。
【００６６】
一方で、例えば電子部品の場合のように、パレットのサイズが小さく相対的に同時に読みとれるRFIDタグの個数が多い場合（例えば100個程度）は、従来のアンチコリジョンの手続きでは、読み出しに時間がかかってしまう。
【００６７】
パレットの検品の場合は、現在の検出可能領域にどのRFIDタグが「あるべき」かが、リーダライタによってあらかじめ判っている。ここで、ブルームフィルタを格納したRFIDタグをパレットに貼り付け、本発明を実施すると、本発明のコリジョン耐性の効果により、少数（例えば１回）の読み出し操作によって、リーダライタの検出可能領域に存在すべきRFIDタグが全て揃っているか否かを検証できる。
【００６８】
ここで、タグIDを64ビットとし、このタグIDから生成されたブルームフィルタの長さmを2048ビット、ハッシュ関数の個数kを10、同時に読み出すRFIDタグの数nを100とすると、合成フィルタにおけるビット０の占める割合は、以下のようになる。
【数１】
【００６９】
この結果と、上記式（１）とに基づき、偽陽性発生確率Rfpを計算すると、以下の通りである。
【数２】
【００７０】
この偽陽性発生確率が所望の精度に満たない場合は、前述した本発明の実施の形態で述べたように、ビットを条件付けすることにより読み出しを２度以上に分割したり、あるいは一度に読み出す個数を減らしたりするなど、システム全体の工夫で対応可能である。
【００７１】
（第２の例：靴屋の例）
靴屋の小売店舗を考える。靴屋では、店舗倉庫に様々な種類、様々なサイズの靴を揃える必要がある。例えば、店舗倉庫に1000足の靴が格納され、入荷および販売が繰り返されているものとする。
【００７２】
店員は客のサイズを聞いた上で、PDA（アプリケーション装置）と組み合わされた電子タグリーダ（リーダライタ）に靴の型式とサイズとの情報を入力する。この時、靴の型式およびサイズは、店頭に展示されている靴に付けられたRFIDタグから読み取っても良い。この後、電子タグリーダを持った店員は、店舗倉庫へと移動する。
【００７３】
店舗倉庫内の各靴箱にはRFIDタグが貼り付けられ、RFIDタグには、(ID, 型式, サイズ)が記録されている。また、RFIDタグには、この組み合わせのうち、(型式, サイズ)から生成されたブルームフィルタが記録されている。
【００７４】
各々のRFIDタグは、電子タグリーダからの読み出し要求に対して、保持するブルームフィルタと、その生成元となった(型式, サイズ)との組み合わせを返信する。
【００７５】
店舗倉庫内では、電子タグリーダはこの読み出し要求を１回または複数回行って、電子タグリーダの読み出し範囲（検出可能範囲）内に、目的の (型式, サイズ) を持つRFIDタグが存在するか否かを検証する。目的の(型式, サイズ) を持つRFIDタグが存在する場合は、電子タグリーダはその旨を店員に通知する。この際、電子タグリーダの出力レベルを徐々に下げて読み出し範囲を狭め、これにより目的の（型式、サイズ）を持つRFIDタグの存在箇所をさらに絞り込んでもよい。なお、靴箱に取り付けられたRFIDタグは、会計時に、POSレジスタ 等でも読み取りの対象となり得る。
【００７６】
以上のように、本発明の実施の形態によれば、複数のRFIDタグの同時応答信号から、各RFIDタグに保持されるブルームフィルタをＯＲ合成した合成ブルームフィルタを取得し、この合成ブルームフィルタに対し、あらかじめ保持しているタグ情報（タグIDや物品情報等）を検証するようにしたため、検出可能領域内に存在するRFIDタグを短時間で検出することができる。
【００７７】
また、本実施の形態によれば、ブルームフィルタにCRC等のエラー検出コードまたはタグIDを付加してリーダライタに送信するようにしたため、コリジョンが発生したか否かをリーダライタにおいて簡易に検出できる。
【００７８】
また、本実施の形態によれば、偽陽性発生確率を計算し、計算した偽陽性発生確率が偽陽性発生数許容閾値を満たさない場合は、ビットによる条件付けを行って読み出しを行うようにしたため、所望の検出精度を維持しつつ、データ読出しが可能となる。
【００７９】
また、本実施の形態によれば、フィルタ検証の際ブルームフィルタにおいて参照されなかったビット位置にビット１が立っているか否かを検査するため、あらかじめ保持しているタグ情報以外のタグ情報を持つRFIDタグが、検出可能領域内に存在するか否かを判断できる。
【図面の簡単な説明】
【００８０】
【図１】本発明の実施の形態に従った無線タグシステムの構成を概略的に示すブロック図である。
【図２】図２（Ａ）は、送信データの内容の一例を示し、図２（Ｂ）は図２（Ａ）のデータをNRZ符号化して生成した符号化信号の一例を示す。
【図３】複数のRFIDタグから同時に応答があった場合に生じるコリジョンを説明する図である。
【符号の説明】
【００８１】
１１：RFIDタグ
１２：メモリ部
１３：タグ回路
３１：リーダライタ（無線タグリーダ）
３２：制御部
３３：通信部
３４：フィルタ検証部
３５：データ格納部
４１：アプリケーション装置。
【技術分野】
【０００１】
本発明は、無線タグリーダ、無線タグシステム、プログラムおよび無線通信方法に関する。
【背景技術】
【０００２】
近年、物品の効率的な管理を行うために無線タグシステムを導入するケースが増えてきている。無線タグシステムでは、管理対象となる物品に埋め込まれるRFIDタグと、RFIDタグからデータを読み出すリーダライタとを使用する。この無線タグシステムにおいて、リーダライタによるデータ読出し時に、複数のRFIDタグから同時に応答があると、データの衝突（コリジョン）が発生する問題がある。
【０００３】
従来におけるアンチコリジョン（Anti-Collision） 技術としては、ALOHA 系と二分木探索とが有力であった。
【０００４】
ALOHA 系は、リーダライタ が、RFIDタグへの問い合わせに対する返答信号に衝突を検出した場合、RFIDタグのタグID の最上位ビット（MSB） から順番に条件を絞った問い合わせを行い、衝突の原因となるRFIDタグのうち1つのみが反応する条件になるまでこれを繰り返す方式である。このALOHA系は、RFIDタグに搭載すべきロジック回路が簡易である点が特徴である。しかし、この方式では、同時に反応するRFIDタグが１つになるまで、複数ステップによる絞り込み手続きを行うため、ステップ数が多くなると読み出しに時間がかかるという欠点がある。
【０００５】
一方、二分木探索は、異なるタグID を持つRFIDタグが同時に応答した場合に、タグID のうち差分部分（ビット値が異なる部分）のみがリーダライタ によって衝突信号として検出でき、且つ、共通部分（ビット値が同一の部分）についてはそのまま読み出しが可能である符号化方式の場合に適用できる。例えばマンチェスター符号化の場合は、0と1とが同時に送信された場合は衝突を検出できる。この二分木探索を用いる場合も、複数ステップによる絞り込み手続きを行うため、ステップ数が多くなると読み出しに時間がかかるという欠点がある。
【０００６】
以上の他、従来におけるアンチコリジョン技術を示した文献として特開2004-62665号（特許文献１）がある。
【０００７】
この特許文献１におけるアンチコリジョン機構は、従来のアルゴリズム(JIS-X6323-3, ISO/IEC15693-3) をベースに、衝突が発生した場合はRFIDタグの応答スロット開始位置をずらすという簡易なアルゴリズムで、アンチコリジョン機能を実現する。単にスロットをずらしただけでは再び衝突が起きる可能性があるが、十分なID 空間があれば(特許文献１の説明では56bit 以上としている) 再び衝突が起きる可能性は低く、数回の試行でタグID が取得できるとしている。
【０００８】
しかし、この特許文献１に記載の技術でも、数回の試行でタグIDを１つ取得できるのみである。従って、リーダライタによる検出可能領域内の全てのRFIDタグからタグIDを取得するには、すなわち、検出可能領域内に存在する全てRFIDタグを検出するには、多くの時間を要するという問題がある。
【特許文献１】特開2004-62665公報
【発明の開示】
【発明が解決しようとする課題】
【０００９】
本発明は、検出可能領域内に存在する無線タグを短時間で検出できる無線タグリーダ、無線タグシステム、プログラムおよび無線通信方法を提供する。
【課題を解決するための手段】
【００１０】
本発明の一態様としての無線タグリーダは、各々タグ情報と前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタとを保持した複数の無線タグと通信する無線タグリーダであって、前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段と、前記複数の無線タグの各々からのブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得する受信手段と、前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段と、タグ情報を格納するデータ格納手段と、前記合成ブルームフィルタに対し前記データ格納部内のタグ情報を検証するフィルタ検証手段と、を備える。
【００１１】
本発明の一態様としての無線タグシステムは、複数の無線タグと前記複数の無線タグと通信する無線タグリーダとを備えた無線タグシステムであって、各前記無線タグは、前記タグ情報と、前記タグ情報からブルームフィルタアルゴリズムにより生成されたブルームフィルタとを格納したメモリ手段と、前記無線タグリーダから前記ブルームフィルタの読み出し要求を受けた場合は、前記メモリ手段内の前記ブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信する応答手段と、を有し、前記無線タグリーダは、前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段と、前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタを取得する受信手段と、前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段と、タグ情報を格納するデータ格納手段と、前記合成ブルームフィルタに対し前記データ格納部内のタグ情報を検証するフィルタ検証手段と、を有した、ことを特徴とする。
【００１２】
本発明の一態様としてのプログラムは、各々タグ情報と前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタとを保持した複数の無線タグと通信する手段としてコンピュータを機能させるプログラムであって、前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段、前記複数の無線タグの各々からのブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得する受信手段、前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段、前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証するフィルタ検証手段、として前記コンピュータを機能させる。
【００１３】
本発明の一態様としての無線通信方法は、各々タグ情報を保持した複数の無線タグと、無線タグリーダとが通信する無線通信方法であって、前記無線タグリーダが、前記複数の無線タグに読み出し要求信号を同時に送信し、各前記無線タグが、あらかじめ保持する、前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信し、前記無線タグリーダが、前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を得、前記衝突ブルームフィルタ信号を復号して各前記ブルームフィルタの論理和をとった合成ブルームフィルタを得、前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証する、ことを特徴とする。
【発明の効果】
【００１４】
本発明により、検出可能領域内に存在する無線タグを短時間で検出できる。
【発明を実施するための最良の形態】
【００１５】
図１は、本発明の実施の形態に従った無線タグシステムの構成を概略的に示すブロック図である。
【００１６】
この無線タグシステムは、複数のRFIDタグ１１と、検出可能領域２１に存在するRFIDタグ１１と通信するリーダライタ３１と、リーダライタ３１に対し検出可能領域２１内に存在するRFIDタグを検出することを指示するアプリケーション装置４１とを備える。
【００１７】
RFIDタグ１１は、メモリ部１２と、リーダライタ３１からの読み出し要求に応じてメモリ部１２内のデータを読み出し読み出したデータをリーダライタ３１に返すタグ回路１３とを備える。
【００１８】
メモリ部１２内には、RFIDタグ１１に固有に割り当てられたタグIDと、このタグIDから生成されたブルームフィルタ（後述）と、ブルームフィルタのビット列から生成されたCRCまたはパリティとが格納されている。この他、メモリ部１２内には、RFIDタグ１１が取り付けられる物品の物品情報 (例えば服飾品のサイズ等)が格納されてもよい。
【００１９】
RFIDタグ１１におけるタグ回路１３は、リーダライタ３１からの読み出し要求を受けると、メモリ部１２内のブルームフィルタと、CRC、パリティまたはIDタグとを読み出し、符号化および変調を施して、リーダライタ３１に送信する。ブルームフィルタのみを送信しても良い。送信の際の変調方式としては、例えばＡＳＫ、ＦＳＫ等を用いることができる。
【００２０】
図２（Ａ）は、RFIDタグ１１からリーダライタ３１へ送信するデータ内容の一例を示す。図２（Ｂ）は、図２（Ａ）のデータをNRZ符号化して生成した符号化信号を示し、この符号化信号がさらに変調されることでリーダライタ３１に送信される。
【００２１】
符号化方式には、他の送信信号との衝突時に、ビット単位でＯＲ演算となることが要求される。上記NRZ符号化方式にはこの性質を持たせることができる。なお、データの送信方向は、ブルームフィルタ側およびCRC（orタグID）側のどちらからでも良い。
【００２２】
ここでブルームフィルタについて簡単に説明する。なお、ブルームフィルタの詳細については、Broder et al., Network Applications of Bloom Filters: A Survey 等を参照されたい。
【００２３】
ブルームフィルタとは、ある任意のデータdがデータ集合X に含まれるかどうかをハッシュ関数の応用により確率的に検査するためのフィルタである。
【００２４】
データ集合Xより生成されたブルームフィルタBF-Xに対して、定められた手続きを行うことで、あるデータd がデータ集合Xに含まれるか否かを「検証」することができる。手続きの結果、positive(陽性) ないしnegative(陰性) という２通りの結果が得られる。
【００２５】
陰性の結果が得られた場合は、データ集合X にデータd が含まれている可能性は無い。一方、陽性の結果が得られた場合は、データ集合Xにデータd が含まれる可能性が高い。すなわち、陽性の結果が得られても、必ずしもデータ集合X にデータd が含まれているとは限らない。データ集合Xにデータdが含まれていないにも拘わらず陽性の結果が得られる場合を偽陽性と呼ぶ。
【００２６】
以下、このような性質を有するブルームフィルタの生成方法について説明する。
【００２７】
ブルームフィルタの生成には以下のパラメータを用いる。
【００２８】
・m：フィルタの長さ
・k：繰り返し回数（用意するハッシュ関数の個数）
ブルームフィルタの生成は以下の手順に従う。
【００２９】
（１）ブルームフィルタの生成手順
１．長さmのビット列Fを用意し、全て0にセットする。
２．値域が[1,m] となる、k 個の独立したハッシュ関数hn() (ただしn=1・・・k ) を用意する。同一のハッシュアルゴリズムに対してそれぞれ異なる定数(salt) を与えることでk 個の独立したハッシュ関数hn()を用意しても良い。
３．入力データ集合X の各要素xi に対して、次の処理を行う。
(a) p = 1 とする
(b) もしp > k ならば終了
(c) ２．で用意したハッシュ関数hp() を用い、idx ＝ hp(xi) を計算
(d) ビット列F のidx ビット目を1 にする（既に１が立っていた場合は、ビット値をそのまま１とする）
(e) p に1 を加える
(f) 手順３．(b) へ戻る
【００３０】
要するに、入力データ集合Ｘの要素xiの各々について、ｋ個のハッシュ関数からそれぞれハッシュ値idxを求め、ビット列Ｆのidxビット目にそれぞれ１を立てることでブルームフィルタを生成する。
【００３１】
次に、入力データ集合Xにデータdが含まれるか否かの検証（フィルタ検証）は以下の手順で行う。
【００３２】
（２）フィルタ検証の手順
１．p = 1 とする。
２．もしp>k ならば陽性を返す。
３．検証したいデータd について、idx ＝ hp(d)を計算。
４．ビット列F のidx ビット目を調べ、0 ならば陰性を返す。
５．p に1 を加える。
６．手順２．に戻る。
【００３３】
要するに、k個のハッシュ関数にそれぞれデータｄを入力し、各々のハッシュ関数の出力idxに対応するビット位置が全て１であれば陽性を返し、各々のハッシュ関数の出力idxに対応するビット位置の少なくともいずれかが０であれば陰性を返す。
【００３４】
ここで、偽陽性が発生する場合、すなわち、データ集合Xにデータdが含まれないにも拘わらず手順２．において陽性が返される場合は、各々のハッシュ関数の出力idxに対応するビット位置がたまたま全て１であった場合である。例えばデータAおよびデータBからなるデータ集合Yから生成されたブルームフィルタBF-Yがあるとする。このブルームフィルタBF-Yにおける１の位置、すなわちデータAに基づく１の位置とデータBに基づく１の位置とのＯＲをとった位置が、データｄに基づく１の位置を包含する場合がある。このような場合に、ブルームフィルタBF-Yを用いてデータdの検証を行うと、偽陽性が発生することとなる。
【００３５】
ここで、偽陽性の発生確率Rfp は、Rfp=sk・・・（式１）として表される。ただし、sはブルームフィルタ内の全ビットのうち1 になっているビットの比率を表すサチュレーション（saturation）である。例えば、k = 10 かつs = 0.5の場合はRfp = 0.510となる。
【００３６】
上述したように、RFIDタグ１１におけるメモリ部１２内には、RFIDタグ１１のタグIDから生成されたブルームフィルタが格納されている。つまり、このブルームフィルタは１つのデータ（タグID）から生成されたものである。なお、タグID からのブルームフィルタの生成では、フィルタ長mに対し、用意するハッシュ関数の個数kが小さく設定されることが好ましい。この場合、生成されるブルームフィルタのビットのほとんどが0となる。
【００３７】
図１において、リーダライタ３１における制御部３２は、アプリケーション装置４１からRFIDタグの検出指示を受け取ると、RFIDタグ１１と通信を行う通信部３３に対し、検出可能領域２１内のRFIDタグ１１からデータを読み出すことを指示する。
【００３８】
通信部３３は、検出可能領域２１に読み出し要求信号を送信する。通信部３３は、読み出し要求信号を受け取った単数または複数のRFIDタグ１１から返されるデータ信号を受信する。通信部３３は、受信したデータ信号を復調および復号する。複数のRFIDタグ１１からデータ信号が返された場合、すなわち通信部３３が複数のRFID１１からのデータ信号を同時に受信した場合、衝突（コリジョン）が発生する。
【００３９】
図３は、２つのRFIDタグ１１（第１および第２のRFIDタグ）から同時に応答があった場合に生じるコリジョンを説明する図である。
【００４０】
図３（Ａ）は、各RFIDタグの送信データの内容を示す。図３（Ｂ）は第１のRFIDタグの送信データをNRZ符号化して生成した符号化信号を示す。図３（Ｃ）は第２のRFIDタグの送信データをNRZ符号化して生成した符号化信号を示す。図３（Ｄ）は通信部３３において受信された衝突信号を復調して得た符号化信号（観測信号）を示す。
【００４１】
図３（Ｄ）から理解されるように、通信部３３において得た符号化信号は、第１のRFIDタグから送信されたNRZ符号化信号と、第２のRFIDタグから送信されたNRZ符号化信号とのOR合成値となる。
【００４２】
以降の説明では、通信部３３は、ブルームフィルタとCRCとからなるデータを、単数のRFIDタグ１１から受信、または複数のRFIDタグ１１から同時に受信したとする。
【００４３】
通信部３３は、受信したデータ（単数のRFIDタグ１１からのデータまたは複数のRFIDタグ１１からのデータをOR合成した合成データ）におけるCRC（受信CRC）と、受信したデータにおけるブルームフィルタ（受信フィルタ）とが整合するか否かを検査する。
【００４４】
整合する場合は、通信部３３は、単数のRFID１１タグからデータを受信したと（コリジョンが発生していないと）判断し、整合しない場合は複数のRFID１１タグからデータを受信したと（コリジョンが発生したと）判断する。通信部３３が、複数のRFIDタグ１１からデータを受信したと判断した場合、受信CRCは、各RFIDタグ１１からのCRCのOR合成値（合成CRC）となり、受信フィルタは、各RFIDタグ１１からのブルームフィルタのOR合成値（合成フィルタ）となる。通信部３３は、コリジョンの発生の有無を制御部３２に通知し、また、コリジョンの発生の有無と受信フィルタとをフィルタ検証部３４に渡す。
【００４５】
リーダライタ３１におけるデータ格納部３５は、既知のタグIDを複数格納している。また、データ格納部３５内には、タグIDの各々から生成されたブルームフィルタが、各タグIDに対応づけられて格納されている。なお、RFIDタグの生産時には、全く同じフィルタが生成されるタグID を持つRFIDタグを排除するように管理することが望ましい。
【００４６】
フィルタ検証部３４は、通信部３３からコリジョンが発生している旨を受け取った場合は、上述したフィルタ検証の手順に従い、受信フィルタ（合成フィルタ）に対してデータ格納部３５内の各タグIDを検証する。フィルタ検証部３４は、検証の結果が陽性であるタグIDを全て検出し、検出したタグIDを制御部３２に渡す。
【００４７】
ここで、フィルタ検証部３４は、フィルタ検証の際、合成フィルタにおいて参照したビット位置を記憶しておく。フィルタ検証部３４は、フィルタ検証の後、合成フィルタにおいて参照されなかったビット位置が存在するか否かを検査し、存在する場合、そのビット位置に１が立っているか否かを検査する。フィルタ検証部３４は、１が立っている場合、未知のタグIDを持つRFIDタグ１１が検出可能領域２１内に存在することを決定する。ただし、ハッシュ衝突が発生した場合は、未知のタグIDを持つRFIDタグ１１が存在したとしてもその存在が隠れてしまう可能性がある。すなわち、既知の複数のタグIDによる複数のブルームフィルタのOR合成値が、ある未知のタグIDによるブルームフィルタを包含する場合は、仮に未知のタグIDを持つRFIDタグが存在したとしても、その存在が隠れてしまう。フィルタ検証部３４は、未知のタグIDを持つRFIDタグ１１が存在すると判断した場合は、その旨を制御部３２に通知しても良い。
【００４８】
一方、フィルタ検証部３４は、通信部３３からコリジョンが発生していない旨を受け取った場合は、受信フィルタと同一のフィルタを持つタグIDをデータ格納部３５から検出し、検出したタグIDを制御部３２に渡す。なお、上述と同様に、この受信フィルタに対してデータ格納部３５内の各タグIDを検証して、検証の結果が陽性であるタグIDを検出し、検出したタグIDを制御部３２に渡しても良い。
【００４９】
制御部３２は、フィルタ検証部３４から受け取ったタグIDと、通信部３３から受け取ったコリジョンの発生の有無とを、アプリケーション装置４１に渡す。制御部３２は、フィルタ検証部３４から未知のタグIDを持つRFIDタグ１１が存在する旨を受けとった場合は、その旨もアプリケーション装置４１に渡す。
【００５０】
以上では、RFIDタグ１１から読み出すデータはブルームフィルタおよびCRCである例を説明したが、RFIDタグ１１から読み出すデータがブルームフィルタおよびタグIDである場合は例えば以下のようになる。
【００５１】
通信部３３は、単数のRFIDタグ１１からのデータ、または複数のRFIDタグ１１からのデータをOR合成した合成データにおける、受信フィルタおよび受信タグIDをフィルタ検証部３４に渡す。
【００５２】
フィルタ検証部３４は、受信タグIDと同一のタグIDがデータ格納部３５に存在するか否かを検査し、存在しない場合はコリジョンが発生したと判断する。この場合、フィルタ検証部３４は、受信フィルタに対してデータ格納部３５内の各タグIDを検証する。フィルタ検証部３４は、検査の結果、陽性であった全てのタグIDと、コリジョンが発生した旨とを、制御部３２に渡す。
【００５３】
一方、フィルタ検証部３４は、受信タグIDと同一のタグIDがデータ格納部３５に存在する場合は、コリジョンが発生していないと判断する。この場合、フィルタ検証部３４は、このタグIDと、コリジョンが発生していない旨とを制御部３２に渡す。これによりフィルタ検証等を行わずに済むため、処理を高速化できる。
【００５４】
制御部３２は、フィルタ検証部３４から受け取ったタグIDと、コリジョンの発生の有無とをアプリケーション装置４１へ返す。
【００５５】
ところで、上述したように、フィルタ検証部３４におけるフィルタ検証では、偽陽性が発生し得る。偽陽性発生確率Rfpは、上記（式１）に示したように、受信フィルタ（例えば合成フィルタ）のサチュレーション（１の占める割合）sと、ブルームフィルタ生成時に用いるハッシュ関数の個数kとを用いて、Rfp=skとして、計算できる。
【００５６】
そこで、本実施の形態では、この偽陽性発生確率Rfpを用いて、受信フィルタの品質がアプリケーションの要求を満たすか否かを判断する。より詳細には、アプリケーション装置４１からリーダライタ３１に偽陽性発生数許容閾値ANFP(acceptable numberof false positives)を与え、この偽陽性発生数許容閾値ANFPと、データ格納部３５内の既知のタグIDの数（Nとする）と、上記偽陽性発生確率Rfpとに基づき、受信フィルタの品質がアプリケーションの要求を満たすか否かを判断する。以下これについてさらに詳しく説明する。
【００５７】
制御部３２は、アプリケーション装置４１から偽陽性発生数許容閾値ANFPを受け取る。
【００５８】
また、制御部３２は、フィルタ検証部３４から受信フィルタを受け取り、上記（式１）に従って、偽陽性発生確率Rfpを計算する。kの値は例えばあらかじめフィルタ検証部３４に保持されている。
【００５９】
また、制御部３２は、データ格納部３５に格納されたタグIDの数Nをあらかじめ保持しているか、またはタグIDの数Nをフィルタ検証部３４から受け取る。
【００６０】
制御部３２は、計算した偽陽性発生確率Rfp と、既知のタグIDの数Nとを乗算して偽陽性発生の期待値E（=Rfp×N）を計算する。制御部３２は、計算した期待値Eと、偽陽性発生数許容閾値ANFPとを比較する。期待値Eが偽陽性発生数許容閾値ANFP を上まわる場合は、既存の衝突回避方式またはこれに類似した方式を用いて、同時に応答するRFIDタグの個数を制限する。例えば、リーダライタ３１は、受信フィルタのサチュレーションsを下げるため、タグIDにおける特定ビット（例えば最上位ビット）が0であるRFIDタグのみが返答することを要請する読み出し要求信号を送信する。この結果、検出可能領域に存在するRFIDタグのうち、応答するRFIDタグをおよそ半数にできる。これにより、品質の高い受信フィルタを得ることができる。受信フィルタの品質が極端に悪い場合は、複数ビットを条件付けすることにより反応するRFIDタグの数をさらに絞り込んでもよい。
【００６１】
ただし、条件付けするビット数が１個の場合は２回、２個の場合は４回、３個の場合は８回と、条件付けするビット数が多くなるほど、多くの読み出し回数が必要になる。すなわち、条件付けするビット数が多すぎると、本実施の形態の利点であるRFIDタグ検出の高速さを損なう可能性がある。このため、RFIDタグが保有するブルームフィルタ長を十分長いものとして、十分多数のRFIDタグからの同時読み出しを行った場合でも、受信フィルタのサチュレーションが十分低くなるようにすることが望ましい。
【００６２】
以上に説明した本実施の形態では、タグIDから生成されたブルームフィルタと、CRC（orタグID、パリティ）とをRFIDタグから読み出したが、これに代えて、以下のようにしても良い。例えば、物品情報から生成したブルームフィルタをRFIDタグに格納しておき、RFIDタグからブルームフィルタと物品情報（またはCRC、パリティ）とを読み出すようにしても良い。この場合、各RFIDタグの物品情報を格納した格納部をリーダライタ内に設けておく必要がある。これについては、以降に説明する実施例（第２の例）において、詳しく説明する。
【００６３】
以下に、本発明の代表的な実施例を２つ示す。
【００６４】
（第１の例：パレットIDの読み出しによる検品の例）
物流過程において、検品は手間がかかる重要な作業の一つである。一方で、物流の各段階におけるコスト圧縮や速度の向上への要求は非常に強い。ここで、RFIDタグを用いて検品を行う方式を考える。例えば、部品等の検品を行う場合に、部品を格納するパレットにRFID タグを格納する。
【００６５】
ここで、部品やパレットが十分に大きい場合は、リーダライタが同時に読み取れるタグの個数は少ないため、個々に読み出しを行ってもそれほど大きな時間がかかるわけではない。
【００６６】
一方で、例えば電子部品の場合のように、パレットのサイズが小さく相対的に同時に読みとれるRFIDタグの個数が多い場合（例えば100個程度）は、従来のアンチコリジョンの手続きでは、読み出しに時間がかかってしまう。
【００６７】
パレットの検品の場合は、現在の検出可能領域にどのRFIDタグが「あるべき」かが、リーダライタによってあらかじめ判っている。ここで、ブルームフィルタを格納したRFIDタグをパレットに貼り付け、本発明を実施すると、本発明のコリジョン耐性の効果により、少数（例えば１回）の読み出し操作によって、リーダライタの検出可能領域に存在すべきRFIDタグが全て揃っているか否かを検証できる。
【００６８】
ここで、タグIDを64ビットとし、このタグIDから生成されたブルームフィルタの長さmを2048ビット、ハッシュ関数の個数kを10、同時に読み出すRFIDタグの数nを100とすると、合成フィルタにおけるビット０の占める割合は、以下のようになる。
【数１】
【００６９】
この結果と、上記式（１）とに基づき、偽陽性発生確率Rfpを計算すると、以下の通りである。
【数２】
【００７０】
この偽陽性発生確率が所望の精度に満たない場合は、前述した本発明の実施の形態で述べたように、ビットを条件付けすることにより読み出しを２度以上に分割したり、あるいは一度に読み出す個数を減らしたりするなど、システム全体の工夫で対応可能である。
【００７１】
（第２の例：靴屋の例）
靴屋の小売店舗を考える。靴屋では、店舗倉庫に様々な種類、様々なサイズの靴を揃える必要がある。例えば、店舗倉庫に1000足の靴が格納され、入荷および販売が繰り返されているものとする。
【００７２】
店員は客のサイズを聞いた上で、PDA（アプリケーション装置）と組み合わされた電子タグリーダ（リーダライタ）に靴の型式とサイズとの情報を入力する。この時、靴の型式およびサイズは、店頭に展示されている靴に付けられたRFIDタグから読み取っても良い。この後、電子タグリーダを持った店員は、店舗倉庫へと移動する。
【００７３】
店舗倉庫内の各靴箱にはRFIDタグが貼り付けられ、RFIDタグには、(ID, 型式, サイズ)が記録されている。また、RFIDタグには、この組み合わせのうち、(型式, サイズ)から生成されたブルームフィルタが記録されている。
【００７４】
各々のRFIDタグは、電子タグリーダからの読み出し要求に対して、保持するブルームフィルタと、その生成元となった(型式, サイズ)との組み合わせを返信する。
【００７５】
店舗倉庫内では、電子タグリーダはこの読み出し要求を１回または複数回行って、電子タグリーダの読み出し範囲（検出可能範囲）内に、目的の (型式, サイズ) を持つRFIDタグが存在するか否かを検証する。目的の(型式, サイズ) を持つRFIDタグが存在する場合は、電子タグリーダはその旨を店員に通知する。この際、電子タグリーダの出力レベルを徐々に下げて読み出し範囲を狭め、これにより目的の（型式、サイズ）を持つRFIDタグの存在箇所をさらに絞り込んでもよい。なお、靴箱に取り付けられたRFIDタグは、会計時に、POSレジスタ 等でも読み取りの対象となり得る。
【００７６】
以上のように、本発明の実施の形態によれば、複数のRFIDタグの同時応答信号から、各RFIDタグに保持されるブルームフィルタをＯＲ合成した合成ブルームフィルタを取得し、この合成ブルームフィルタに対し、あらかじめ保持しているタグ情報（タグIDや物品情報等）を検証するようにしたため、検出可能領域内に存在するRFIDタグを短時間で検出することができる。
【００７７】
また、本実施の形態によれば、ブルームフィルタにCRC等のエラー検出コードまたはタグIDを付加してリーダライタに送信するようにしたため、コリジョンが発生したか否かをリーダライタにおいて簡易に検出できる。
【００７８】
また、本実施の形態によれば、偽陽性発生確率を計算し、計算した偽陽性発生確率が偽陽性発生数許容閾値を満たさない場合は、ビットによる条件付けを行って読み出しを行うようにしたため、所望の検出精度を維持しつつ、データ読出しが可能となる。
【００７９】
また、本実施の形態によれば、フィルタ検証の際ブルームフィルタにおいて参照されなかったビット位置にビット１が立っているか否かを検査するため、あらかじめ保持しているタグ情報以外のタグ情報を持つRFIDタグが、検出可能領域内に存在するか否かを判断できる。
【図面の簡単な説明】
【００８０】
【図１】本発明の実施の形態に従った無線タグシステムの構成を概略的に示すブロック図である。
【図２】図２（Ａ）は、送信データの内容の一例を示し、図２（Ｂ）は図２（Ａ）のデータをNRZ符号化して生成した符号化信号の一例を示す。
【図３】複数のRFIDタグから同時に応答があった場合に生じるコリジョンを説明する図である。
【符号の説明】
【００８１】
１１：RFIDタグ
１２：メモリ部
１３：タグ回路
３１：リーダライタ（無線タグリーダ）
３２：制御部
３３：通信部
３４：フィルタ検証部
３５：データ格納部
４１：アプリケーション装置。
【特許請求の範囲】
【請求項１】
各々タグ情報と前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタとを保持した複数の無線タグと通信する無線タグリーダであって、
前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段と、
前記複数の無線タグの各々からのブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得する受信手段と、
前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段と、
タグ情報を格納するデータ格納手段と、
前記合成ブルームフィルタに対し前記データ格納部内のタグ情報を検証するフィルタ検証手段と、
を備えた無線タグリーダ。
【請求項２】
前記フィルタ検証手段は、検証結果が陽性であるタグ情報を検出することを特徴とする請求項１に記載の無線タグリーダ。
【請求項３】
前記合成ブルームフィルタのビット列において所定ビットの占める割合を計算し、前記所定ビットの占める割合と、前記ブルームフィルタの生成のために使用されるハッシュ関数の数とに基づいて偽陽性発生確率を求める計算手段をさらに備えたことを特徴とする請求項１または２に記載の無線タグリーダ。
【請求項４】
前記偽陽性発生確率が、所定の偽陽性発生数許容閾値を満たさない場合は、前記送信手段は、所定の選択条件を満たすタグ情報を持つ無線タグのみが返信することを要求する読み出し要求信号を送信することを特徴とする請求項１乃至３のいずれかに記載の無線タグリーダ。
【請求項５】
前記フィルタ検証手段は、前記タグ情報の検証の際前記合成ブルームフィルタにおいて参照されなかったビット位置に前記所定ビットが立っていた場合は、前記データ格納手段に格納されたタグ情報以外のタグ情報を持つ無線タグが前記複数の無線タグの中に含まれることを決定することを特徴とする請求項３または４に記載の無線タグリーダ。
【請求項６】
前記タグ情報はタグID、または前記無線タグが取り付けられる物品の物品情報であることを特徴とする請求項１乃至５のいずれかに記載の無線タグリーダ。
【請求項７】
前記無線タグからのブルームフィルタ信号の符号化方式はＮＲＺ符号化方式であり、
前記復号手段は、前記衝突ブルームフィルタ信号をＮＲＺ復号することを特徴とする請求項１乃至６のいずれかに記載の無線タグリーダ。
【請求項８】
複数の無線タグと前記複数の無線タグと通信する無線タグリーダとを備えた無線タグシステムであって、
各前記無線タグは、
前記タグ情報と、前記タグ情報からブルームフィルタアルゴリズムにより生成されたブルームフィルタとを格納したメモリ手段と、
前記無線タグリーダから前記ブルームフィルタの読み出し要求を受けた場合は、前記メモリ手段内の前記ブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信する応答手段と、を有し、
前記無線タグリーダは、
前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段と、
前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタを取得する受信手段と、
前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段と、
タグ情報を格納するデータ格納手段と、
前記合成ブルームフィルタに対し前記データ格納部内のタグ情報を検証するフィルタ検証手段と、を有した、
ことを特徴とする無線タグシステム。
【請求項９】
各々タグ情報と前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタとを保持した複数の無線タグと通信する手段としてコンピュータを機能させるプログラムであって、
前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段、
前記複数の無線タグの各々からのブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得する受信手段、
前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段、
前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証するフィルタ検証手段、
として前記コンピュータを機能させるプログラム。
【請求項１０】
各々タグ情報を保持した複数の無線タグと、無線タグリーダとが通信する無線通信方法であって、
記無線タグリーダが、前記複数の無線タグに読み出し要求信号を同時に送信し、
各前記無線タグが、あらかじめ保持する、前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信し、
前記無線タグリーダが、前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得し、前記衝突ブルームフィルタ信号を復号して各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得し、前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証する、
ことを特徴とする無線通信方法。
【請求項１】
各々タグ情報と前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタとを保持した複数の無線タグと通信する無線タグリーダであって、
前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段と、
前記複数の無線タグの各々からのブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得する受信手段と、
前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段と、
タグ情報を格納するデータ格納手段と、
前記合成ブルームフィルタに対し前記データ格納部内のタグ情報を検証するフィルタ検証手段と、
を備えた無線タグリーダ。
【請求項２】
前記フィルタ検証手段は、検証結果が陽性であるタグ情報を検出することを特徴とする請求項１に記載の無線タグリーダ。
【請求項３】
前記合成ブルームフィルタのビット列において所定ビットの占める割合を計算し、前記所定ビットの占める割合と、前記ブルームフィルタの生成のために使用されるハッシュ関数の数とに基づいて偽陽性発生確率を求める計算手段をさらに備えたことを特徴とする請求項１または２に記載の無線タグリーダ。
【請求項４】
前記偽陽性発生確率が、所定の偽陽性発生数許容閾値を満たさない場合は、前記送信手段は、所定の選択条件を満たすタグ情報を持つ無線タグのみが返信することを要求する読み出し要求信号を送信することを特徴とする請求項１乃至３のいずれかに記載の無線タグリーダ。
【請求項５】
前記フィルタ検証手段は、前記タグ情報の検証の際前記合成ブルームフィルタにおいて参照されなかったビット位置に前記所定ビットが立っていた場合は、前記データ格納手段に格納されたタグ情報以外のタグ情報を持つ無線タグが前記複数の無線タグの中に含まれることを決定することを特徴とする請求項３または４に記載の無線タグリーダ。
【請求項６】
前記タグ情報はタグID、または前記無線タグが取り付けられる物品の物品情報であることを特徴とする請求項１乃至５のいずれかに記載の無線タグリーダ。
【請求項７】
前記無線タグからのブルームフィルタ信号の符号化方式はＮＲＺ符号化方式であり、
前記復号手段は、前記衝突ブルームフィルタ信号をＮＲＺ復号することを特徴とする請求項１乃至６のいずれかに記載の無線タグリーダ。
【請求項８】
複数の無線タグと前記複数の無線タグと通信する無線タグリーダとを備えた無線タグシステムであって、
各前記無線タグは、
前記タグ情報と、前記タグ情報からブルームフィルタアルゴリズムにより生成されたブルームフィルタとを格納したメモリ手段と、
前記無線タグリーダから前記ブルームフィルタの読み出し要求を受けた場合は、前記メモリ手段内の前記ブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信する応答手段と、を有し、
前記無線タグリーダは、
前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段と、
前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタを取得する受信手段と、
前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段と、
タグ情報を格納するデータ格納手段と、
前記合成ブルームフィルタに対し前記データ格納部内のタグ情報を検証するフィルタ検証手段と、を有した、
ことを特徴とする無線タグシステム。
【請求項９】
各々タグ情報と前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタとを保持した複数の無線タグと通信する手段としてコンピュータを機能させるプログラムであって、
前記ブルームフィルタの読み出しを要求する読み出し要求信号を前記複数の無線タグに同時に送信する送信手段、
前記複数の無線タグの各々からのブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得する受信手段、
前記衝突ブルームフィルタ信号を復号して、各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得する復号手段、
前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証するフィルタ検証手段、
として前記コンピュータを機能させるプログラム。
【請求項１０】
各々タグ情報を保持した複数の無線タグと、無線タグリーダとが通信する無線通信方法であって、
記無線タグリーダが、前記複数の無線タグに読み出し要求信号を同時に送信し、
各前記無線タグが、あらかじめ保持する、前記タグ情報からブルームフィルタアルゴリズムに基づき生成されたブルームフィルタを所定の符号化方式によって符号化してブルームフィルタ信号を生成し、生成した前記ブルームフィルタ信号を前記無線タグリーダに送信し、
前記無線タグリーダが、前記複数の無線タグからの前記ブルームフィルタ信号を同時に受信して衝突ブルームフィルタ信号を取得し、前記衝突ブルームフィルタ信号を復号して各前記ブルームフィルタの論理和をとった合成ブルームフィルタを取得し、前記合成ブルームフィルタに対し、あらかじめ与えられたタグ情報を検証する、
ことを特徴とする無線通信方法。
【図１】
【図２】
【図３】
【図２】
【図３】
【公開番号】特開２００６−２７０１８５（Ｐ２００６−２７０１８５Ａ）
【公開日】平成１８年１０月５日（２００６．１０．５）
【国際特許分類】
【出願番号】特願２００５−８１６０５（Ｐ２００５−８１６０５）
【出願日】平成１７年３月２２日（２００５．３．２２）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成１８年１０月５日（２００６．１０．５）
【国際特許分類】
【出願日】平成１７年３月２２日（２００５．３．２２）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]