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