(57)【特許請求の範囲】
【請求項１】
タグ読み取り装置と複数のタグを備えるタグ識別システムであって、
前記タグ読み取り装置は、少なくとも２つのアンテナを有し、前記各アンテナの有効範囲内で呼び出し信号を送信し、
前記複数のタグは、前記少なくとも２つのアンテナの各々の有効範囲を順次通過し、前記複数タグの各々が受信した呼び出し信号に応答して前記少なくとも２つのアンテナに返信信号を返し、
前記タグ読み取り装置は、
前記複数のタグから返され、かつ前記少なくとも２つのアンテナによって受信した返信信号に基づいて、前記複数のタグが通過する順序を判定するシーケンス判定手段と、
前記返信信号が、受信した返信信号が複数のタグの１つから返された返信信号のみを含むことを意味する単一領域あるいは受信した返信信号が複数のタグから返された返信信号を含むことを意味する複数領域から送信されたかを判定するために、少なくとも２つのアンテナの各々によって受信した前記返信信号を分類し、分類結果を前記シーケンス判定手段に送信する返信分類手段と
を含むことを特徴とするタグ識別システム。
【請求項２】
前記タグ読み取り装置は、少なくとも２つのアンテナの各々から呼び出し信号を送信するタイミングを設定する呼び出し信号送信タイミング設定手段をさらに備え、
前記呼び出し信号送信タイミング設定手段は、前記シーケンス判定手段が、少なくとも２本のアンテナのうちの特定の１つによって受信した返信信号に基づいて複数のタグの順序を一意に判定することができない場合に、特定のアンテナの次のアンテナから前記呼び出し信号を送信するタイミングを調節することを特徴とする請求項１に記載のタグ識別システム。
【請求項３】
前記タグ読み取り装置は、タグの読み取りが最小の時間で完了するように、前記少なくとも２本のアンテナの各々の読み取り性能を制御する読み取り性能制御手段をさらに備えることを特徴とする請求項１に記載のタグ識別システム。
【請求項４】
前記タグ読み取り装置は、所定数のタグだけが前記アンテナによって送信された呼び出し信号を受信できるように、前記少なくとも２つのアンテナの有効範囲を設定する有効範囲設定手段をさらに備えることを特徴とする請求１に記載のタグ識別システム。
【請求項５】
前記タグ読み取り装置が、ＲＦＩＤ読み取り装置であり、前記複数のタグが、ＲＦＩＤタグであることを特徴とする請求１に記載のタグ識別システム。
【請求項６】
順次通過する複数のタグを読み取るためのタグ読み取り装置であって、
有効範囲内を通過する前記複数のタグに呼び出し信号を送信し、受信した呼び出し信号に応答して各タグから返される返信信号を受信する少なくとも２つのアンテナと、
前記複数のタグから返され、かつ前記少なくとも２つのアンテナによって受信した返信信号に基づいて前記複数のタグの順序を判定するシーケンス判定手段と
前記返信信号が、受信した返信信号が複数のタグの１つから返された返信信号のみを含むことを意味する単一領域あるいは受信した返信信号が複数のタグから返された返信信号を含むことを意味する複数領域から送信されたかを判定するために、少なくとも２つのアンテナの各々によって受信した前記返信信号を分類し、分類結果を前記シーケンス判定手段に送信する返信分類手段と
を備えることを特徴とするタグ読み取り装置。
【請求項７】
少なくとも２つのアンテナの各々から呼び出し信号を送信するタイミングを設定する呼び出し信号送信タイミング設定手段をさらに備え、
前記呼び出し信号送信タイミング設定手段は、前記シーケンス判定手段が、少なくとも２本のアンテナのうちの特定の１つによって受信した返信信号に基づいて複数のタグの順序を一意に判定することができない場合に、特定のアンテナの次のアンテナから前記呼び出し信号を送信するタイミングを調節することを特徴とする請求項６に記載のタグ読み取り装置。
【請求項８】
タグの読み取りが最小の時間で完了するように、前記少なくとも２本のアンテナの各々の読み取り性能を制御する読み取り性能制御手段をさらに備えることを特徴とする請求項６に記載のタグ読み取り装置。
【請求項９】
所定数のタグだけが前記アンテナによって送信された呼び出し信号を受信できるように、前記少なくとも２つのアンテナの有効範囲を設定する有効範囲設定手段をさらに備えることを特徴とする請求項６に記載のタグ読み取り装置。
【請求項１０】
前記タグ読み取り装置が、ＲＦＩＤ読み取り装置であり、前記複数のタグが、ＲＦＩＤタグであることを特徴とする請求項６に記載のタグ読み取り装置。
【請求項１１】
タグ読み取り装置を通過する複数のタグのシーケンス判定方法であって、
前記タグ読み取り装置の少なくとも２つのアンテナの各々からその有効範囲内にある前記複数のタグに呼び出し信号を送信する呼び出し信号送信ステップと、
前記タグ読み取り装置の前記少なくとも２つのアンテナから受信した前記呼び出し信号に応答して前記複数のタグが返す返信信号を受信する返信受信ステップと、
受信した返信信号に基づいて前記複数のタグの通過の順序を判定するシーケンス判定ステップと、
前記返信信号が、受信した返信信号が複数のタグの１つから返された返信信号のみを含むことを意味する単一領域あるいは受信した返信信号が複数のタグから返された返信信号を含むことを意味する複数領域から送信されたかを判定するために、少なくとも２つのアンテナの各々によって受信した前記返信信号を分類する返信分類ステップとを含み、
前記シーケンス判定ステップで、前記分類結果と前記返信信号が返信された順序に基づいて前記複数のタグが通過する順序を判定する
ことを特徴とするシーケンス判定方法。
【請求項１２】
少なくとも２つのアンテナの各々から呼び出し信号を送信するタイミングを設定する呼び出し信号送信タイミング設定ステップをさらに含み、
前記呼び出し信号送信タイミング設定ステップで、前記シーケンス判定ステップが、少なくとも２本のアンテナのうちの特定の１つによって受信した返信信号に基づいて複数のタグの順序を一意に判定することができない場合に、特定のアンテナの次のアンテナから前記呼び出し信号を送信するタイミングを調節することを特徴とする請求項１１に記載のシーケンス判定方法。
【請求項１３】
タグの読み取りが最小の時間で完了するように、前記少なくとも２本のアンテナの各々の読み取り性能を制御する読み取り性能制御ステップをさらに含むことを特徴とする請求項１１に記載のシーケンス判定方法。
【請求項１４】
所定数のタグだけが前記アンテナによって送信された呼び出し信号を受信できるように、前記少なくとも２つのアンテナの有効範囲を設定する有効範囲設定ステップをさらに含むことを特徴とする請求項１１に記載のシーケンス判定方法。
【請求項１５】
前記タグ読み取り装置が、ＲＦＩＤ読み取り装置であり、前記複数のタグが、ＲＦＩＤタグであることを特徴とする請求項１１に記載のシーケンス判定方法。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータシステムに関し、特に、タグ識別システム、タグ読み取り装置、およびタグシーケンス判定方法に関する。
【背景技術】
【０００２】
識別を目的としたデータ交換のための、無線周波数を介した非接触式双方向通信技術として、無線ＩＣタグ（ＲＦＩＤ）の普及が急速に進んでいる。
【０００３】
ＲＦＩＤシステムは、典型的には、ＲＦＩＤリーダとＲＦＩＤタグという２つの主要部分で構成される。ＲＦＩＤタグは読み取り対象物に付加され、ＲＦＩＤシステムのデータ記憶媒体として機能する。ＲＦＩＤタグは、典型的には、データを記憶するマイクロチップと、コイル・アンテナ等の、ＲＦＩＤリーダーとの無線周波数通信用の接続素子とを含む。ＲＦＩＤタグには、アクティブとパッシブの２種類がある。アクティブＲＦＩＤタグは、タグ上に電源装置（バッテリー等）を備え、ＲＦ信号を能動的に送信して通信を行う。パッシブＲＦＩＤタグは、必要な電力をＲＦＩＤリーダの呼び出し信号から得て、ＲＦＩＤリーダの信号を反映もしくはロード変調して通信を行う。パッシブかアクティブかにかかわらず、ほとんどのＲＦＩＤタグは、ＲＦＩＤリーダからの呼び掛けがあったときにのみ通信する。
【０００４】
ＲＦＩＤリーダは、ＲＦＩＤタグとの間でデータの読み取りと書き込みを行うことができる。ＲＦＩＤリーダは、典型的には、無線周波数モジュールと、コントローラと、ＲＦＩＤタグと無線周波数通信を行うための接続素子（アンテナ等）とを含む。さらに、多数のＲＦＩＤリーダには、受信したデータをデータ処理サブシステムに伝達するための情報読み取りインタフェースが設けられている。このインタフェースの一例としては、パソコン上で稼働するデータベースが挙げられる。
【０００５】
ほとんどのＲＦＩＤシステムは、ＲＦＩＤリーダのアンテナが呼び出し信号を送信し、アンテナの有効範囲（以下、「ＲＦ領域」ともいう）内にあるタグがそれを受信することで機能する。有効範囲の大きさは、ＲＦＩＤリーダの動作周波数とアンテナのサイズによって決まる。ＲＦＩＤタグは、アンテナの有効範囲内を通過中にリーダの呼び出し信号を検出し、それに応答して、タグ内に格納される識別対象物に関する情報またはデータを返信信号として送信する。リーダは、ＲＦＩＤタグから返された返信信号を受信し、その内容に基づいて、ＲＦＩＤタグによって識別される物体を識別する。
【０００６】
ＲＦＩＤは、バーコード、磁気カード、ＩＣカード等の従来の識別技術と比較すると、非接触式で動作範囲が広い、悪環境への適応性が高い、移動体を識別できる等の利点を有する。これらの利点により、ＲＦＩＤは物流管理の分野でますます広く利用されるようになっている。しかし、ＲＦＩＤを物流管理に利用する場合には、図１に示すＲＦＩＤアプリケーション層でのリアルタイム管理が大きな問題となる。
【０００７】
リアルタイム管理で重要となる課題の１つは、空港手荷物取り扱いシステム、郵便物仕分けシステム、食品仕分けシステム等の多数の適用業務において、移動シーケンスのリアルタイム検出問題を解決することである。図２に、移動シーケンスのリアルタイム検出問題の一例を示す。
【０００８】
現時点では、以下の理由から、移動シーケンスにおいて個別のＲＦＩＤタグを検出することは困難である。
【０００９】
１．ＲＦＩＤリーダがタグに送信した信号に対して、複数のタグが同時にリーダに応答する可能性がある。
【００１０】
２．ＲＦＩＤリーダは複数のタグを同時に読み取ることができるが、図３に示すように、読み取られる情報は単純で、順序が混乱しがちである。
【００１１】
３．詳細な情報を取得することが困難であり、例えば、無作為間隔の移動シーケンスに含まれる各タグの正確な時間などは得られない。
【００１２】
４．複数のタグがＲＦ領域に同時に入ると衝突が発生する。衝突が発生すると自然順序が完全に混乱し、以下のような問題が生じる。
ａ．パッシブタグの場合は、タグ内に電源がないため、状態情報の信頼性が失われる。
ｂ．タグ同士が通信できない。これは、複数チャネルにアクセスする通信において発生する問題である。
ｃ．タグのメモリ量が少なく、計算能力も低い。そのため、タグ上での計算はほぼ不可能である。
ｄ．衝突防止を目指した従来技術も存在するが、この技術は移動シーケンスの正しい順序を検出する上ではおおむね無力である。
【００１３】
５．リーダの衝突防止能力を高くするにつれて、シーケンス（順序）の検出効率がボトルネックとなる。現在のリーダはＣ１  Ｇ２（クラス１第２世代）のタグを毎秒６００以上読み取ることができるが、実環境のタグを専用ＲＦＩＤリーダが読み取る際には、１つ当たりおよそ数十ミリ秒を要する。そのため、「グローバルスクロール」の効率は「在庫」の効率よりも低い。
【００１４】
シーケンス（順序）検出の問題を既存の方法で解決することはきわめて困難であるが、ＲＦＩＤ適用業務における移動シーケンス検出の需要は多く、大きな市場機会が存在するため、シーケンス検出はますます重要となっている。しかし、現在のほとんどの移動シーケンス検出システムは高価で、読み取りに時間がかかりすぎる。例えば、北京首都国際空港で使用される空港手荷物取り扱いシステムは、１日平均約１１０，０００人の乗客を処理することができるが、現状では手荷物の誤処理が乗客１，０００人中平均５人の割合で発生している。手荷物の紛失や誤処理は、１件当たり平均５００人民元のコスト増につながる。したがって、手荷物の紛失によるコスト増は１日２７５，０００人民元、年間で１億３７５，０００人民元に上る。乗客と航空会社にとって、時間がかかることも問題となる。例えば、長年使用されてきた仕分け機の最新世代、Ｓ−３０００Ｅ  Ｔｉｌｔ−Ｔｒａｙ  Ｓｏｒｔｅｒの仕分け速度は３．５ｍ／ｓｅｃである。手荷物処理速度が毎秒１個、エアバス３８０の定員が６００人、乗客１人の手荷物が２個とすると、必要な処理時間は１２００秒、すなわち２０分となる。手荷物の処理速度を５倍の毎秒５個にできると、総処理時間は４分間に短縮され、乗客や航空会社にとって大幅な省時間となる。
【００１５】
移動シーケンスの混乱は、移動する順序対が高い確率で観測領域内に同時に滞在することによって発生する。観測領域Ｘ内のシーケンスＳｅｑ＝｛Ｂ→Ａ｝の観測値は、
【数１】
0004859251.tif 000002
として表される。混乱シーケンス情報は、以下の特徴を有する。
ａ．物体ＡおよびＢが観測領域に入ったときに衝突が発生する。
ｂ．衝突が開始する前に、物体Ａのみが観測される短い期間が存在する。
ｃ．衝突が終了した後に、物体Ｂのみが観測される短い期間が存在する。
ｄ．単一物体と複数の物体の境界を判別し、観測結果を制御するための精密な方法がない。
ｅ．物体Ａと物体Ｂ間の間隔が不明確である。
ＲＦＩＤリーダの呼び掛けエリア内には無数のタグが存在しうる。ＲＦＩＤシステム内のリーダは、呼び掛けメッセージをタグに送信することができ、メッセージを受信したすべてのタグは直ちにリーダに応答を送信する。複数のタグが応答した場合には、これらの応答がＲＦ通信チャネル内で衝突するため、リーダはそれを受信できない。この衝突を解決する問題は一般に「衝突防止問題」と呼ばれ、この問題を解決することはきわめて重要である。
【００１６】
マルチアクセス手順の中で最も単純なのは、ＡＬＯＨＡ手順である。データパケットは取得可能な状態になると直ちにタグからリーダに送信されるため、これはタグ駆動型の確率的ＴＤＭＡ手順ということができる。この手順は、読み取り専用タグに対してのみ使用される。読み取り専用タグは、通常、少量のデータ（シリアル番号）を周期的シーケンス（順序）でリーダに送信する。データ送信時間は繰り返し時間のうちごく一部を使って行われるため、次の送信までに比較的長い休止時間がある。さらに、この繰り返し時間はタグ間で少しずつ異なるため、ある程度の確率で、２つのタグがデータパケットを送るタイミングがずれてデータパケットの衝突が発生しないケースが生じる。図４に、ＡＬＯＨＡシステムにおけるデータ送信の時間シーケンスを示す。
【００１７】
商業用タグ製品の衝突防止方法の基本概念として、数種類のスロット付きＡｌｏｈａプロトコルが広く利用されている。これらの商業用タグ製品の例としては、ＰＨＩＬＩＰＳの‘Ｉ−ｃｏｄｅ’やＩＳＯ／ＩＥＣ−１８０００−６Ｃなどが挙げられる。このアルゴリズムの中心概念は、空のスロットや衝突スロット等の無効なスロットを減らすことで在庫プロセスの迅速化を図ることにある。しかし、このアルゴリズムはＲＦＩＤタグがＲＦ領域に入る順序を判定する際には無力である。なぜなら、Ａｌｏｈａと関連の衝突防止アルゴリズムの無作為選択方法によって、正しい順序が崩されてしまうからである。
【００１８】
また、短い時間で大量のタグを読み取ることを目指した従来技術も存在するが、移動シーケンスの正しい順序を検出するには無力であり、ときに余計な混乱を招くことさえある。図５に、従来技術の概念を示す。
【００１９】
前述したように、従来の解決策は強力な方法を使用して大量のタグを読み取ろうとするものであるが、従来の衝突防止アルゴリズムでは複数のタグの順序が完全に混乱してしまう。これらのアルゴリズムは、短い時間で複数のタグを検出する方法を提供するが、読み取られる情報にはシーケンス（番号など）や原時間とは無関係の情報しか含まれない。
【００２０】
上記のことから、移動中のＲＦＩＤタグの正しい順序を確実かつ効率的に検出するシステムと方法が必要とされていることは明らかである。
【発明の開示】
【発明が解決しようとする課題】
【００２１】
本発明の目的は、移動中のＲＦＩＤタグの正しい順序を確実かつ効率的に検出するタグ識別システム、タグ読み取り装置、およびタグシーケンス判定方法を提供することである。
【００２２】
本発明の第１の態様によれば、タグ読み取り装置と複数のタグを備えるタグ識別システムであって、タグ読み取り装置は、少なくとも２つのアンテナを有し、各アンテナの有効範囲内で呼び出し信号を送信し、複数のタグは、少なくとも２つのアンテナの各々の有効範囲を順次通過し、複数タグの各々が受信した呼び出し信号に応答して少なくとも２つのアンテナに返信信号を返し、タグ読み取り装置は、複数のタグから返され、かつ少なくとも２つのアンテナによって受信した返信信号に基づいて、複数のタグが通過する順序を判定するシーケンス判定手段を含むことを特徴とするタグ識別システムが提供される。
【００２３】
本発明の第２の態様によれば、順次通過する複数のタグを読み取るためのタグ読み取り装置であって、有効範囲内を通過する複数のタグに呼び出し信号を送信し、受信した呼び出し信号に応答して各タグから返される返信信号を受信する少なくとも２つのアンテナと、複数のタグから返され、かつ少なくとも２つのアンテナによって受信した返信信号に基づいて複数のタグの順序を判定するシーケンス判定手段とを備えることを特徴とするタグ読み取り装置が提供される。
【００２４】
本発明の第３の態様によれば、タグ読み取り装置を通過する複数のタグのシーケンス判定方法であって、タグ読み取り装置の少なくとも２つのアンテナの各々からその有効範囲内にある複数のタグに呼び出し信号を送信する呼び出し信号送信ステップと、タグ読み取り装置の少なくとも２つのアンテナから受信した呼び出し信号に応答して複数のタグが返す返信信号を受信する返信受信ステップと、受信した返信信号に基づいて複数のタグの通過の順序を判定するシーケンス判定ステップとを含むことを特徴とするシーケンス判定方法が提供される。
【発明の効果】
【００２５】
本発明の技術的解決策は、特に以下の側面において大きな技術的効果を達成する。
【００２６】
１．情報の発信元が単一領域か複数領域かを正確に分類でき、単一領域の判別が容易である。
【００２７】
２．シーケンス検出に適したＲＦ領域のサイズを決定するための手法と基準が提供される。
【００２８】
３．以下の状況での展開が容易である。
ａ．周波数が異なる複数のリーダを使用する場合
ｂ．移動速度を変化させる必要がある場合
ｃ．距離を変化させる必要がある場合
ｄ．異なる通信速度が使用される場合
【００２９】
３．衝突防止アルゴリズムまたはプロトコルに依存しない。
【００３０】
４．正検出率が高く、十分な信頼性がある。
【００３１】
次に、図面を参照して、本発明の上記およびその他の機能と利点を詳細に説明する。
【発明を実施するための最良の形態】
【００３２】
以下では、本発明の特徴と利点を、本発明の好適な実施例に関連して図面を参照しながら詳細に説明する。
【００３３】
図６は、本発明の一実施例によるＲＦＩＤシステム１００の概略図を示す。この実施例は、空港手荷物取り扱いシステムへの適用事例である。当業者には、本発明によるＲＦＩＤシステムを他の物流管理システムにも適用できることは理解されるであろう。
【００３４】
図６に示すように、本発明の当該実施例のＲＦＩＤシステム１００は、１つのＲＦＩＤ読み取り装置１０１と複数のＲＦＩＤタグ１０２とを含む。ＲＦＩＤタグ１０２を取り付けた手荷物はコンベヤで移送され、これらのタグは移動シーケンスを形成する。ＲＦＩＤ読み取り装置１０１は、その有効範囲内にあるコンベヤ上のタグに呼び出し信号を送信し、タグ付き手荷物を正しく仕分けするために、タグが呼び出し信号に応答して返してきた返信信号に基づいてコンベヤ上のタグの順序を判定する。
【００３５】
本実施例においては、最終的には、複数のタグの順序の判定は２つの隣接タグの順序の各判定に分解されるため、以下では、コンベヤ上の２つのタグ１０２Ａおよび１０２Ｂの順序の判定を例にとって本発明によるＲＦＩＤシステム１００の原理を説明する。
【００３６】
図７は、ＲＦＩＤ読み取り装置１０１の構造を示す概略ブロック図である。図７に示すように、本発明によるＲＦＩＤ読み取り装置１０１は、無線周波数通信によりデータを送受信するための少なくとも２つのアンテナを含む。この例では、ＲＦＩＤ読み取り装置１０１は、アンテナ１とアンテナ２とを含む。各アンテナは各々対応する有効範囲を有する。有効範囲タグ内のタグはＲＦＩＤ読み取り装置１０１によってアンテナを介して送信された呼び出し信号を受信し、呼び出し信号に応答して返信信号を返すことができる。ＲＦＩＤ読み取り装置１０１は、アンテナを介してその返信信号を受信することができる。
【００３７】
ＲＦＩＤ読み取り装置１０１は、シーケンス判定手段１０１１と、返信分類手段１０１２と、呼び出し信号送信タイミング設定手段１０１３とをさらに含む。
【００３８】
シーケンス判定手段１０１１は、タグ１０２Ａおよび１０２Ｂによって返され、かつアンテナ１および２によって受信された返信信号に基づいて、タグ１０２Ａおよび１０２Ｂの通過順序を判定する。
【００３９】
返信分類手段１０１２は、アンテナ１および２によって受信された返信信号を分類して、返信元が単一領域か複数領域かを判定し、返信分類結果をシーケンス判定手段１０１１に送信する。ここで、「単一領域」とは、受信した返信信号に１つのタグから返された返信信号のみが含まれることを意味し、「複数領域」とは、受信した返信信号に複数のタグから返された返信信号が含まれることを意味する。
【００４０】
呼び出し信号送信タイミング設定手段１０１３は、アンテナ１および２から呼び出し信号を送信するタイミングを設定するために使用される。具体的には、呼び出し信号送信タイミング設定手段１０１３は、シーケンス判定手段１０１１がアンテナ１によって受信された返信信号に基づいてＲＦＩＤタグ１０２Ａおよび１０２Ｂの順序を一意に判定できない場合に、アンテナ２から呼び出し信号を送信するタイミングを調整する。ここで、シーケンス判定手段１０１１がアンテナ１によって受信された返信信号に基づいてＲＦＩＤタグ１０２Ａおよび１０２Ｂの順序を一意に判定できる場合（例えば、アンテナ１を介して受信した返信信号が、１つの単一領域と１つの複数領域とを含む場合）には、アンテナ２によって受信された返信信号を使用して２つのタグの順序を判定する必要がないことは言うまでもない。
【００４１】
実際には、本発明のＲＦＩＤ読み取り装置１０１に含まれるシーケンス判定手段１０１１、返信分類手段１０１２、および呼び出し信号送信タイミング設定手段１０１３は共に、情報パーティションおよび順序最適化（ＯＯ：Ｏｒｄｉｎａｌ  Ｏｐｔｉｍｉｚａｔｉｏ）に基づいた１つのタグ順序識別手法を構成する。以下では、その原理と特徴について詳細に説明する。
【００４２】
前述したように、返信分類手段１０１２は、アンテナ１および２が受信した返信信号を分類して、返信元が単一領域か複数領域かを判定する。
【００４３】
ここで、それぞれタグ１０２Ａおよび１０２Ｂを付加されたコンベヤ上の物体ＡおよびＢは、Ａの後にＢという順序でＲＦＩＤ読み取り装置１０１を通過する。２つのタグを読み取る際の図８に示す３つのフェーズは、アンテナ１およびアンテナ２の各々について発生する。アンテナ１を例にとると、以下のような流れとなる。
【００４４】
１．第１のフェーズにおいて、ＲＦＩＤ読み取り装置に最も近い物体である物体Ａ上のＲＦＩＤタグ１０２Ａのみが読み取られる。これは「単一領域」と呼ばれる。
【００４５】
２．第２のフェーズにおいて、コンベヤが進むに従ってＲＦＩＤタグ１０２Ｂがアンテナ１の有効範囲内に入ってくる。ＲＦＩＤ読み取り装置はアンテナ１の有効範囲内に２つのタグがあることを検出し、従来の衝突防止アルゴリズムを適用してこれらの複数のタグを読み取る。読み取り結果は｛Ｂ−＞Ａ｝（Ａの後にＢ）または｛Ａ−＞Ｂ｝（Ｂの後にＡ）のいずれにもなりうる。そのため、これは「混乱領域」、「衝突領域」、「二重領域」、もしくは「複数領域」と呼ばれる。この場合は、正しい順序は完全に混乱状態となる。
【００４６】
３．最後のフェーズでは、タグ１０２Ａは読み取りフィールドを離れるが、タグ１０２Ｂはまだ読み取りフィールド内に存在する。そのため、この領域は「単一領域」とも呼ばれる。
【００４７】
タグ１０２Ａおよび１０２Ｂ間の正しい順序を判定する上では、単一領域内でのサンプリングを正常に完了することが重要な要因となる。それは以下の理由による。
【００４８】
１．単一領域内で２サンプルの両方が選択され、例えばＴ｛Ａ｝  ＜  Ｔ｛Ｂ｝であった場合には、正しい順序は｛Ｂ−＞Ａ｝である（両方のサンプリングが単一領域内）。ここで、Ｔ｛Ａ｝は、タグ１０２Ａからの返信信号のみを含むデータ（以下「Ａ返信」という）が受信されたタイミングを表し、Ｔ｛Ｂ｝は、タグ１０２Ｂからの返信信号のみを含むデータ（以下「Ｂ返信」という）が受信されたタイミングを表す。また、Ｔ｛Ａ｝  ＜  Ｔ｛Ｂ｝は、Ａ返信が受信されたタイミングが、Ｂ返信が受信されたタイミングよりも前であることを意味する。
【００４９】
２．１つのサンプルが単一領域内で選択され、別のサンプルが複数領域で選択された場合（例えば、Ｔ｛Ａ｝＜Ｔ｛Ａ−＞Ｂ｝もしくはＴ｛Ａ｝＜Ｔ｛Ｂ−＞Ａ｝、またはＴ｛Ｂ｝＞Ｔ｛Ａ−＞Ｂ｝もしくはＴ｛Ｂ｝＞Ｔ｛Ｂ−＞Ａ｝の場合）には、｛Ｂ−＞Ａ｝が正しい順序である（少なくとも１回のサンプリングが単一領域内）。ここで、Ｔ｛Ａ−＞Ｂ｝は、タグ１０２Ａおよびタグ１０２Ｂの両方から返された返信信号を含むデータのうち、タグ１０２Ｂからの返信信号がタグ１０２Ａからの返信信号よりも先に返された場合のデータ受信タイミングを示し（以下、このデータを「Ｂ後Ａ返信」という）、Ｔ｛Ｂ−＞Ａ｝は、タグ１０２Ａおよびタグ１０２Ｂの両方から返された返信信号を含むデータのうち、タグ１０２Ａからの返信信号がタグ１０２Ｂからの返信信号よりも先に返された場合のデータ受信タイミングを示す（以下、このデータを「Ａ後Ｂ返信」という）。上記と同様に、Ｔ｛Ａ｝＜Ｔ｛Ａ−＞Ｂ｝は、Ａ返信が受信されたタイミングが、Ｂ後Ａ返信が受信されたタイミングよりも前であることを意味する。
【００５０】
タグ数が３つ以上の場合も同様であり、２つの隣接タグ間の順序が上記のように判定される限り、その相対的順序は容易に判定できる。
【００５１】
したがって、単一領域で複数のサンプルが選択されても、順序を判定することが可能である。単一領域内でサンプルを選択する方法は、きわめて重要な問題である。図９に示すように、従来の連続サンプル方法は非効率的である。これらの方法では、通信ブロックによって受信されたすべてのサンプルが複数領域で捕捉され、単一領域ではサンプルがまったく捕捉されない確立が高い。単一領域にサンプルがなければ、正しいシーケンスを決定することは不可能である。前述したように、単一領域と複数領域間の境界を判別することは困難なため、精密な方法を使用して単一領域内のサンプルを捕捉することは困難である。そのため、本発明では、順序最適化（ＯＯ）に基づく大まかな方法が提案される。図９に、異なる選択方法の効果を示す。
【００５２】
単一領域における１サンプル選択方法問題の目的は、設計空間における検索および選択設計によって、妥当な設計を得ることにある。全数検索は一般に非効率的であり、ときには不可能なことさえある。また、検索結果は膨大な数に上る。検索空間は連続空間であるため、無限に広い。そのため、問題を離散事象系（ＤＥＳ：Ｄｉｓｃｒｅｔｅ  Ｅｖｅｎｔ  Ｓｙｓｔｅｍｓ）の最適化問題として公式化する必要がある。
【００５３】
順序最適化（ＯＯ）は、１９９０年代にＰｒｏｆ．Ｈｏによって提唱された、最適化に基づくシミュレーションである。順序最適化方法を使用すると、最適化手法をベースとしたシミュレーションを効率的に実行することが可能になる。この方法の意図は、プランまたは選択集合のパフォーマンスを見積もるための計算上単純な粗モデルを使って、多数の候補から（真に最適解ではなく）まずまずか、または満足できる解を見つけることにある。「妥当な選択」とは、「高い確率で定量化および判定が可能な集合」として定義される。この粗モデルに基づき、これらの選択の部分集合（「選択部分集合Ｓ」と呼ばれる）が観測「妥当」集合として選択される。その後、順序最適化によって部分集合Ｓと真に妥当な部分集合Ｇとの間の「一致」または「整合」の度合いが定量化される。順序最適化方法は、計算の複雑性を適度に抑えながら多大なノイズの発生を防止できるため、確率離散最適化にはとりわけ有効である。
【００５４】
上記で説明したように、順序最適化の基本概念は、順序比較と目標緩和という２つの原理に基づく。まず、決定Ａが決定Ｂよりも妥当かどうかを判定することは、「Ａ−Ｂ＝？」を判定するよりもはるかに容易である。ＡとＢとの相対的順序は、「値」が１／ｔ１／２の速度で収束する間に、急激に収束する。ＡとＢのうちどちらが妥当かを決定する際には、正確なカージナル値（cardinal
value）は必須ではない。正確なカージナル値は、選択の有用性（価値）を見積もる値ではなく、選択（順序）そのものを重視した値である。順序最適化のもう一つの主要概念は、目標緩和である。これは、妥当部分集合Ｇと選択部分集合Ｓとの間の「一致度」を、効率的で信頼度の高い方法で適度なレベルに保つことにより達成される。妥当部分集合Ｇの基準は、決定空間の上位ｎパーセンタイルとして選択され、ここでは真の最適解を見つける必要はない。図１０に、順序最適化の基本概念を示す。
【００５５】
まず、「整合確率」（ＡＰ：Ａｌｉｇｎｍｅｎｔ  Ｐｒｏｂａｂｉｌｉｔｙ）の意味を説明する。制約なし問題においては、「一致」または「整合」とは妥当部分集合Ｇと選択部分集合Ｓとの交点を意味する。ＡＰは、以下のように定義される。
【数２】
0004859251.tif 000003
ここで、ｋは「整合度」である。
【００５６】
盲目選別（ＢＰ：Ｂｌｉｎｄ  Ｐｉｃｋｉｎｇ）は、部分集合Ｓを決定空間Θから、１）無作為、２）置換なし、および３）比較なし、の方法で選択する選択ルールである。この選択ルールによって、決定空間でのランク評価において、すべての決定が同一の傾向を持つことが保証される。また、この場合におけるＡＰは、以下のように閉形式で表すことができる。
【数３】
0004859251.tif 000004
これは、超幾何分布であり、Ｎは決定空間のサイズを示す。盲目選別の場合、ＡＰは以下によって決まる。
【００５７】
１．整合度ｋ
２．妥当部分集合Ｇのサイズ（｜Ｇ｜＝ｇ）、および
３．選択部分集合Ｓのサイズ（｜Ｓ｜＝ｓ）
【００５８】
一般的な順序最適化問題は、以下の最適化問題に公式化できる。
Ｍｉｎ｜Ｓ｜                              （３）
s.t.|{Θｉ|Θｉ={A}orΘｉ={B}|>0;           （４）
|Θ|=N;       （５）
｜Ｇ｜＝ｒ％・Ｎ     （Θの上位ｒ％）     （６）
Prob(|G∩S|>k)>Preq                        （７）
ここで、
Ｓ＝｛Θ１，  Θ２，…，  Θｓ｝−−−−−−  選択部分集合｜Ｓ｜＝ｓ
Θｉ−−−−−−−時間ｔｉにおけるタグラベルの集合
Θ−−−−−−−設計空間
Ｇ−−−−−−妥当部分集合｜Ｇ｜＝ｇ
ｋ−−−−−−−整合度
ＧおよびＳ間の整合度がｋとなる確率は、以下の式で得られる。
【数４】
0004859251.tif 000005
そのため、ＧおよびＳ間の整合度が少なくともｋとなる確率は、以下のように表される。
【数５】
0004859251.tif 000006
したがって、選択部分集合Ｓの最小サイズは、以下の式で得られる。
【数６】
0004859251.tif 000007
ＲＦＩＤシステムの場合、Ｓは、ＲＦＩＤサンプル（タグ）を検出するためのＲＦＩＤ検出器（リーダ／アンテナ）の数である。
【００５９】
サンプル盲目選別方法をこの事例に適用した場合、設計空間はＴｒ＋ＴＩ、妥当部分集合はＴｒであり、ここでＴｒは１つのＲＦＩＤタグを読み取る際の冗長時間、ＴＩは１つのＲＦＩＤタグを読み取る際の最小時間である。Ｔｒ領域内の選別サンプルのみが単一領域内のサンプルを捕捉できる。シーケンスは、単一領域内のサンプルが検出された場合にのみ決定される。｛Ｓ回の読み取り中少なくともｋで単一領域内のサンプルを捕捉する｝確率は、以下の式で表される。
【数７】
0004859251.tif 000008
したがって、以下のようになる。
【数８】
0004859251.tif 000009
【００６０】
問題は、この方法をいかにして改良するかである。この方法は、単一領域内のサンプルを捕捉するために多数の検出器を必要とするため、効率的ではない。Ｎｏ−Ｆｒｅｅ−ｌｕｎｃｈ定理によれば、「どのアルゴリズムも、構造情報がなければ、その平均パフォーマンスは盲目的探索を上回ることはできない」のである。そのため、効率を高めるためには構造情報を得る必要がある。これまでの研究から、単一領域内のサンプルが捕捉できない主な理由は、読み取りの瞬間が「遅い」（すなわち、検出器がＴｒ領域ではなくＴＩ領域で動作する）ことであることが判明している。したがって、検出器が単一領域内のサンプルを捕捉しないことが既知の場合には、次の検出器ｉに対して時間Δｔｉ分「早く」動作するよう指示することで、妥当領域を拡大すればよい。通常、この調整方法が選択効果を高められるかどうかは、実環境によって決まる。図１１に、この方法の基本原理を示す。
【００６１】
増大分をΔＴとすると、妥当部分集合のサイズはＴｒ＋ΔＴとなる。したがって、｛Ｓ回の読み取り中少なくともｋで単一領域内のサンプルを捕捉する｝確率は、以下の式で表される。
【数９】
0004859251.tif 000010
よって、以下のようになる。
【数１０】
0004859251.tif 000011
したがって、確率の向上幅は、以下のようになる。
【数１１】
0004859251.tif 000012
【００６２】
１つのＲＦＩＤタグを読み取る最小時間を１１０ｍｓ、冗長時間を９０ｍｓとすると、式（６）に基づいたＰｕｒｅ  ＢＰアルゴリズムと本発明の方法との理論比較は、表１および図１２のようになる。
【表１】
0004859251.tif 000013
【００６３】
表１から、シーケンス検出において確率要件を満たす上では、本発明の方がＢＰ法に勝っていることが明らかである。例えば、９０％超の整合確率が必要とされる場合、ＢＰでは少なくとも４つの検出器が必要であるが、本発明の方法によれば２つのみでこの要件を満たすことができる。ＲＦＩＤ読み取り装置１０１には２つのアンテナのみが配置されているのはこの理由による。ここで留意されたいのは、表１における９０％の確率に対応する検出器数は、本発明については「１」になっていることである。ここでは、第１の検出器は数えられていない。しかし、本発明の本実施例は２つの検出器を要し、ＲＦＩＤ読み取り装置１０１には２つのアンテナ（アンテナ１およびアンテナ２）を配置する必要がある。
【００６４】
図１３に、図６に示すＲＦＩＤシステム１００の、ＲＦＩＤタグ対１０２Ａおよび１０２Ｂの順序を判定するためのＲＦＩＤ読み取り装置１０１の動作の流れを示す。図１３に示すように、ステップＳ１１において、アンテナ１は呼び出し信号をＲＦＩＤタグ１０２Ａおよび１０２Ｂに送信する。ステップＳ１２において、現在のアンテナがタグから返された返信信号を受信する。
【００６５】
ステップＳ１３において、１つの呼び出し信号に応答してタグから返された返信信号を１つの返信集合として、返された返信信号に複数の返信集合が含まれるかどうかを判定する。
【００６６】
ステップＳ１３の判定結果が「ＹＥＳ」の場合は、ステップＳ１４において、返信分類手段１０１２が当該複数の返信集合を分類する（すなわち、各返信集合の返信元が単一領域か複数領域かを判定する）。
【００６７】
ステップＳ１５において、複数の返信集合に単一領域があるかどうかを判定する。ステップＳ１５の判定結果が「ＹＥＳ」の場合、すなわち、複数の返信集合に単一領域がある場合には、ステップＳ１６において、シーケンス判定手段１０１１がＲＦＩＤタグ１０２Ａおよび１０２Ｂの順序を判定する。
【００６８】
例えば、返された返信信号が、１つの単一領域と１つの複数領域（例えば、｛Ａ｝および｛Ａ，Ｂ｝）を含む２つの返信集合か、または２つの単一領域（｛Ａ｝および｛Ｂ｝）である場合には、シーケンス判定手段１０１１は、分類結果と、２つの返信集合が受信された順序に基づいて、ＲＦＩＤタグ１０２Ａおよび１０２Ｂのシーケンスを判定することができる。これでプロセスは終了する。
【００６９】
一方、ステップＳ１３の結果が「ＮＯ」の場合、すなわち複数の返信集合がない（１つの返信集合しかない）場合には、返信分類手段１０１２はステップＳ１７においてこの返信集合を分類する。返信集合の返信元は、１つの単一領域（例えば、｛Ａ｝または｛Ｂ｝）かまたは１つの複数領域（例えば、｛Ａ，Ｂ｝）のいずれかである。
【００７０】
ステップＳ１８において、現在のアンテナが最後のアンテナかどうかが判定される。最後のアンテナの場合には、プロセスは終了する。最後のアンテナではない場合には、ステップＳ１９において、呼び出し信号送信タイミング設定手段１０１３が、分類結果に基づいて、次のアンテナが呼び出し信号を送信するタイミングを調整する。そしてステップＳ２０に進み、次のアンテナがタグを読み取る。その後、ステップＳ１２に戻り、次のアンテナがタグによって返された返信信号を受信する。
【００７１】
ステップＳ１５において返された複数の返信集合内に単一領域がないと判定された場合、すなわち、どの返信集合も複数領域である（例えば、２つの複数領域がある）と判定された場合には、ステップＳ１８に進み、上記と同様にそれが最後のアンテナかどうかが判定される。そして、最後のアンテナである場合は、ステップＳ１９に進み、呼び出し信号送信タイミング設定手段１０１３が次のアンテナが呼び出し信号を送信するタイミングを調整し、さらにステップＳ２０に進んで次のアンテナがタグを読み取り、その後ステップＳ１２に戻って以降のプロセスを繰り返す。
【００７２】
図１４に、本発明の他の実施例によるＲＦＩＤ読み取り装置１０１を示す。図１４に示すように、本発明の他の実施例によるＲＦＩＤ読み取り装置１０１は、図７に示すＲＦＩＤ読み取り装置１０１の部品に加えて、読み取り性能制御手段１０１４と、有効範囲設定手段１０１５とをさらに含む。
【００７３】
読み取り性能制御手段１０１４は、情報をノイズがなく明瞭なものとするために、読み取り時間が短縮されるように読み取り性能を制御する。性能は、ＲＦＩＤ検出器が複数のＲＦＩＤタグを読み取る上で重要な要因となる。多数のＲＦＩＤタグを読み取る際には、１つのＲＦＩＤタグを読み取るよりも長い時間がかかる。ＲＦ領域内でＲＦＩＤタグ同士が隣接する時間が処理時間よりも短い場合には、ＲＦＩＤ読み取り装置は返された情報を捕捉できないため、読み取りが失敗する確率が高くなる。そのため、本発明の適用業務においては、在庫モードでは有効に動作できないことが多い。読み取りを完了するためには、読み取り対象の数を制限する必要がある。タグの読み取り速度を上げるために読み取りモードを在庫とグローバルスクロールの間で調整すると、観測時間を短縮することができるため、シーケンスの移動速度を上昇させることが可能になる。
【００７４】
有効範囲設定手段１０１５は、アンテナ１および２の有効範囲を設定することにより、アンテナが送信した呼び出し信号を受信できるタグを特定の個数に制限する。具体的には、有効範囲設定手段１０１５は、有効範囲内のタグ数がｎ未満になるようにアンテナの減衰レベルを調整する。この調整は、タグ対やタグシーケンスの順序判定の精度を高める上で効果的である。図１５に、最適減衰レベルと信頼可能ＲＦ領域を示す。
【００７５】
本発明の方法は、構造情報を利用するので、ＢＰよりも高い検出能力を達成する。本発明の方法は、「Ｇの小さな改良」を行って「ＡＰの大きな改良」を実現することにより、移動中のＲＦＩＤシーケンスの正しい順序を判定できる確率を高める。
【００７６】
以上、本発明を特定の好適な実施例を参照して説明してきたが、その形態と詳細については、付記した特許請求項に定義される本発明の精神と範囲から逸脱することなく様々な変更が可能なことは当業者には理解されるであろう。
【００７７】
例えば、上記では、本発明のタグ識別システム、タグ読み取り装置、およびタグ順序判定方法について、それぞれＲＦＩＤ識別システム、ＲＦＩＤ読み取り装置、およびＲＦＩＤタグ順序判定方法を例として説明してきたが、本発明のタグ識別システム、タグ読み取り装置、およびタグ順序判定方法は提示した実施例に限定されないことは当業者には明らかであろう。本発明の原理は、タグ読み取り装置が移動中のタグから返されたデータを読み取り、タグの順序を判定することにより、タグが付加された品目の順序を決定する他の状況にも同様に適用できる。
【図面の簡単な説明】
【００７８】
【図１】ＲＦＩＤアプリケーション層におけるリアルタイム管理問題を示す。
【図２】移動シーケンスのリアルタイム検出問題の一例を示す。
【図３】複数のタグからの同時応答による順序混乱の問題を示す。
【図４】ＡＬＯＨＡシステムにおけるデータ送信の時間シーケンスを示す。
【図５】従来技術の概念を示す。
【図６】本発明の一実施例によるＲＦＩＤシステムの概略図を示す。
【図７】図６に示すＲＦＩＤ読み取り装置の構造を示す概略ブロック図である。
【図８】２つのタグが読み取られる際に通常存在する３つのフェーズを概略的に示す。
【図９】異なる選択方法の効果を示す。
【図１０】順序最適化の基本原理を示す。
【図１１】本発明による選択方法の基本原理を示す。
【図１２】Ｐｕｒｅ  ＢＰアルゴリズムと本発明の方法との理論比較を示す。
【図１３】図６に示すＲＦＩＤシステムの、ＲＦＩＤタグ対の順序を判定するためのＲＦＩＤ読み取り装置の動作の流れを示す。
【図１４】本発明の他の実施例によるＲＦＩＤ読み取り装置を示す。
【図１５】最適減衰レベルと信頼可能ＲＦ領域を示す。
【符号の説明】
【００７９】
１０１：ＲＦＩＤ読み取り装置
１０１１：シーケンス判定手段
１０１２：返信分類手段
１０１３：呼び出し信号送信タイミング設定手段
１０１４：読み取り性能制御手段
１０１５：有効範囲設定手段
【図１】
0004859251.tif 000014
【図２】
0004859251.tif 000015
【図３】
0004859251.tif 000016
【図４】
0004859251.tif 000017
【図５】
0004859251.tif 000018
【図６】
0004859251.tif 000019
【図７】
0004859251.tif 000020
【図８】
0004859251.tif 000021
【図９】
0004859251.tif 000022
【図１０】
0004859251.tif 000023
【図１１】
0004859251.tif 000024
【図１２】
0004859251.tif 000025
【図１３】
0004859251.tif 000026
【図１４】
0004859251.tif 000027
【図１５】
0004859251.tif 000028