(57)【要約】【課題】  ネットワーク内のオブジェクトのクエリを行うための改良された概念を提供する。【解決手段】  グローバルクエリマネージャ（１００）は、複数のユビキタスゲートウェイを有する移動体通信網において動作する。グローバルクエリマネージャは、前記複数のユビキタスゲートウェイと通信し、あるユビキタスゲートウェイから受け取ったオブジェクトレコードを検出する手段（１１０）を備える。グローバルクエリマネージャは、あるユビキタスゲートウェイから報告されたオブジェクトレコードを一時的に保存するオブジェクトキャッシュ（１２０）も備える。グローバルクエリマネージャは、さらに、クエリオブジェクトに関するレコード要求をクエリ元から受け取り、該レコード要求をクエリユビキタスゲートウェイへ転送するコントローラ（１３０）を備える。【選択図】  図１ａ
2009199592.tif 000002
【特許請求の範囲】
【請求項１】
複数のユビキタスゲートウェイを有する移動体通信網において動作するグローバルクエリマネージャ（１００）であって、前記ユビキタスゲートウェイは、前記移動体通信網で通信を行うことができ、オブジェクトレコードを保存するモバイル機器であり、
前記複数のユビキタスゲートウェイと通信し、あるユビキタスゲートウェイから受け取ったオブジェクトレコードを検出する手段（１１０）と、
あるユビキタスゲートウェイから報告されたオブジェクトレコードを一時的に保存するオブジェクトキャッシュ（１２０）であって、該オブジェクトレコードは、オブジェクトレコード識別子と、オブジェクト識別子と、オブジェクト位置とを含むものである、オブジェクトキャッシュと、
クエリオブジェクトに関するレコード要求をクエリ元から受け取り、該レコード要求をクエリユビキタスゲートウェイへ転送するコントローラ（１３０）であって、前記オブジェクトキャッシュ（１２０）内のオブジェクトレコードに基づいて前記クエリユビキタスゲートウェイを選択するコントローラ（１３０）と
を備えるグローバルクエリマネージャ（１００）。
【請求項２】
前記コントローラ（１３０）は、前記クエリオブジェクトに関するオブジェクトレコードが前記オブジェクトキャッシュ（１２０）に存在しない場合には、クエリユビキタスゲートウェイを無作為に選択するものである、請求項１に記載のグローバルクエリマネージャ（１００）。
【請求項３】
前記オブジェクトキャッシュ（１２０）は、
あるオブジェクトレコードを報告したユビキタスゲートウェイに関するユビキタスゲートウェイレコードと、
前記オブジェクトの最終確認時刻のタイムスタンプと、
前記オブジェクトをユビキタスゲートウェイが継続して監視した期間と、
推定された最終確認位置と、
前記オブジェクトの移動可否と、
前記オブジェクトレコードを交換したユビキタスゲートウェイの履歴と、
前記オブジェクトレコードが伝搬したホップの数と
からなるグループの中の１つまたはこれらの組み合わせをさらに保存するものである、請求項１または２に記載のグローバルクエリマネージャ（１００）。
【請求項４】
前記コントローラ（１３０）は、前記クエリオブジェクトに関するオブジェクトレコードを報告したユビキタスゲートウェイに基づいて、クエリユビキタスゲートウェイを選択するものである、請求項１から３のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項５】
前記コントローラ（１３０）は、前記オブジェクトキャッシュ（１２０）に保存されたクエリオブジェクト位置に基づいて、クエリユビキタスゲートウェイを選択するものである、請求項１から４のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項６】
前記コントローラ（１３０）は、前記クエリオブジェクトのサーチクエリを前記クエリユビキタスゲートウェイにインストールするものであり、
ここで、前記クエリユビキタスゲートウェイは、インストールされたサーチクエリに対する応答として前記クエリオブジェクトまたは別のユビキタスゲートウェイからのクエリオブジェクトに関するオブジェクトレコードをＮＦＣにより要求するものであり、
前記サーチクエリは、ユビキタスゲートウェイに対して前記クエリオブジェクトを積極的にサーチするよう指示するものである、請求項１から５のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項７】
前記コントローラ（１３０）は、前記クエリユビキタスゲートウェイから別のユビキタスゲートウェイに対する前記レコード要求の転送に基づいて、オブジェクトレコードを受け取るものであり、別のユビキタスゲートウェイもまた前記レコード要求を転送するものである、請求項１から６のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項８】
前記コントローラ（１３０）は、前記レコード要求に存続期間を関連付け、前記レコード要求の存続期間が満了したときに前記クエリ元に通知するものである、請求項１から７のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項９】
前記コントローラ（１３０）は、前記オブジェクトキャッシュ（１２０）内の前記クエリオブジェクトに関するオブジェクトレコードよりも新しい、クエリオブジェクトに関するオブジェクトレコードを有する可能性の高いクエリユビキタスゲートウェイに向けて前記レコード要求を転送するものである、請求項１から８のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項１０】
前記コントローラ（１３０）は、クエリオブジェクト位置の近傍に位置するユビキタスゲートウェイへ前記レコード要求を転送するものであり、前記近傍は、前記移動体通信網または前記オブジェクトキャッシュ（１２０）により決定されるものである、請求項１から９のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項１１】
前記コントローラ（１３０）は、所定の数のクエリユビキタスゲートウェイへ前記レコード要求を転送するものである、請求項１から１０のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項１２】
前記コントローラ（１３０）は、所定の数のユビキタスゲートウェイに対して前記サーチクエリをインストールするものである、請求項６から１１のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項１３】
前記コントローラ（１３０）は、前記クエリ元に対して最新のクエリオブジェクト位置を提供するものである、請求項１から１２のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項１４】
前記クエリ元は、前記移動体通信網におけるユビキタスゲートウェイまたはネットワークノードに相当するものである、請求項１から１３のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項１５】
前記手段（１１０）は、ＧＳＭ、ＵＭＴＳ、ＬＴＥ、ＦＯＭＡおよび／またはＷＬＡＮにより通信を行うものである、請求項１から１４のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項１６】
前記手段（１１０）は、ある通信プロトコルを用いて通信を行うものであり、ここで、前記クエリオブジェクトは、該通信プロトコルを用いて通信することができないものである、請求項１から１６のいずれか一項に記載のグローバルクエリマネージャ（１００）。
【請求項１７】
複数のユビキタスゲートウェイを有する移動体通信網においてユビキタスゲートウェイにクエリを行う方法であって、前記ユビキタスゲートウェイは、前記移動体通信網において通信を行うことができ、オブジェクトレコードを保存するモバイル機器であり、
前記複数のユビキタスゲートウェイと通信するステップと、
あるユビキタスゲートウェイから報告されたオブジェクトレコードを一時的に保存するステップであって、該オブジェクトレコードは、オブジェクトレコード識別子と、オブジェクト識別子と、オブジェクト位置とを含むものである、ステップと、
クエリ元からクエリオブジェクトのレコード要求を受け取るステップと、
あるクエリユビキタスゲートウェイへ前記レコード要求を転送するステップであって、該クエリユビキタスゲートウェイは、オブジェクトレコードに基づいて選択されるものである、ステップと、
前記クエリオブジェクトに関するオブジェクトレコードを前記クエリ元へ報告するステップと
を含む方法。
【請求項１８】
請求項１７に記載の方法をプロセッサに実行させるプログラムコードを有するコンピュータプログラム。
【請求項１９】
移動体通信網と通信する第１の手段（１６０）と、
他のユビキタスゲートウェイと通信するとともに、オブジェクト識別子を有するオブジェクトと通信する第２の手段（１７０）であって、あるオブジェクトからオブジェクトレコードを検出する第２の手段（１７０）と、
オブジェクトレコード識別子と、オブジェクト識別子と、オブジェクト位置とを含むオブジェクトレコードを一時的に保存するオブジェクトキャッシュ（１８０）と、
前記第２の手段（１７０）を介してオブジェクトを繰り返し監視するとともに、監視されたオブジェクト内のオブジェクトレコードを前記オブジェクトキャッシュ（１８０）に保存するコントローラ（１９０）であって、前記移動体通信網からクエリオブジェクトに関するレコード要求を受け取るとともに、前記第１の手段（１６０）を介して前記オブジェクトキャッシュ（１８０）から前記移動体通信網へ前記クエリオブジェクトに関するオブジェクトレコードを提供するコントローラ（１９０）と
を備える、複数のユビキタスゲートウェイを有する移動体通信網において通信を行うユビキタスゲートウェイ（１５０）。
【請求項２０】
前記オブジェクトキャッシュ（１８０）は、オブジェクトが最後に監視された時点におけるオブジェクトタイムスタンプを保存するものである、請求項１９に記載のユビキタスゲートウェイ（１５０）。
【請求項２１】
前記コントローラ（１９０）は、前記第２の手段（１７０）を介して他のユビキタスゲートウェイとオブジェクトキャッシュ（１８０）を交換するものである、請求項１９または２０に記載のユビキタスゲートウェイ（１５０）。
【請求項２２】
前記オブジェクトキャッシュ（１８０）は、オブジェクトを監視したユビキタスゲートウェイのユビキタスゲートウェイ識別子を保存するものである、請求項１９から２１のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項２３】
前記オブジェクトキャッシュ（１８０）は、オブジェクトがどれほどの長さにわたって監視されたかを表すオブジェクトの所属期間を保存するものである、請求項１９から２２のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項２４】
前記オブジェクトキャッシュ（１８０）は、オブジェクトが移動しているか否かに関する情報を保存するものである、請求項１９から２３のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項２５】
前記オブジェクトキャッシュ（１８０）は、オブジェクトレコードが報告された経路を保存するものである、請求項１９から２４のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項２６】
前記オブジェクトキャッシュ（１８０）は、オブジェクトがいくつのホップを経由して報告されたかを表すホップの数を保存するものである、請求項１９から２５のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項２７】
ユビキタスゲートウェイレコード識別子またはユビキタスゲートウェイ識別子と、任意的に、ユビキタスゲートウェイ最終確認時刻と、推定された最終確認位置と、平均ユビキタスゲートウェイ速度と、ユビキタスゲートウェイ速度の標準偏差と、ユビキタスゲートウェイレコードを転送したユビキタスゲートウェイの履歴と、前記ユビキタスゲートウェイレコードの報告の際に経由したホップの数とからなるグループの中の１つまたはこれらの組み合わせとを含むユビキタスゲートウェイレコードを保存するユビキタスゲートウェイキャッシュをさらに備える請求項１９から２６のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項２８】
前記コントローラ（１９０）は、前記第２の手段（１７０）を介して前記ユビキタスゲートウェイキャッシュから別のユビキタスゲートウェイに向けて前記ユビキタスゲートウェイレコードを報告するものである、請求項２７に記載のユビキタスゲートウェイ（１５０）。
【請求項２９】
前記コントローラ（１９０）は、あるユビキタスゲートウェイからユビキタスゲートウェイレコードを受け取り、受け取ったユビキタスゲートウェイレコードを用いて前記ユビキタスゲートウェイキャッシュを更新するものである、請求項２７または２８に記載のユビキタスゲートウェイ（１５０）。
【請求項３０】
前記コントローラ（１９０）は、クエリオブジェクトのサーチクエリをサーチクエリ元から受け取るとともに、前記第２の通信手段（１７０）を介して他のユビキタスゲートウェイへ前記サーチクエリを転送するものであり、
前記コントローラ（１９０）は、さらに、前記クエリオブジェクトと通信しようと試みるものであり、
前記サーチクエリは、ユビキタスゲートウェイ（１５０）に対して前記クエリオブジェクトを積極的にサーチするよう指示するものである、請求項１９から２９のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項３１】
前記サーチクエリ元は、前記移動体通信網のネットワークエンティティである別のユビキタスゲートウェイまたはグローバルクエリマネージャである、請求項３０に記載のユビキタスゲートウェイ（１５０）。
【請求項３２】
前記コントローラ（１９０）は、前記クエリオブジェクトに関するオブジェクトレコードを前記サーチクエリ元へ提供するものである、請求項３０または３１に記載のユビキタスゲートウェイ（１５０）。
【請求項３３】
前記コントローラ（１９０）は、前記クエリオブジェクトに関して複数のオブジェクトレコードが利用できる場合には、提供するための最新のオブジェクトレコードを選択するものである、請求項１９から３２のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項３４】
前記コントローラ（１９０）は、レコード要求が転送されたユビキタスゲートウェイのユビキタスゲートウェイ識別子を保存するとともに、前記クエリオブジェクトが見つかるかまたはレコードクエリが取り消された場合には、前記レコード要求が転送されたすべてのユビキタスゲートウェイに向けて前記レコード要求の取り消しを要求するものである、請求項１９から３３のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項３５】
前記コントローラ（１９０）は、サーチクエリを転送することができる回数についての制限を設けるものである、請求項１９から３４のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項３６】
自己の位置を決定する手段をさらに備える請求項１９から３５のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項３７】
前記自己の位置を決定する手段はＧＰＳ受信機を含むものである、請求項３７に記載のユビキタスゲートウェイ（１５０）。
【請求項３８】
オブジェクトレコードとユビキタスゲートウェイレコードとを用いて作成されるブルームフィルタをさらに備える請求項１９から３７のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項３９】
前記第１の手段（１６０）は、セルラ移動体通信網において通信を行うものである、請求項１９から３８のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項４０】
前記移動体通信網がＧＳＭ、ＵＭＴＳ、ＬＴＥ、ＦＯＭＡまたはＷＬＡＮネットワークである、請求項３９に記載のユビキタスゲートウェイ（１５０）。
【請求項４１】
前記第２の手段（１７０）は、ブルートゥース、ＷＬＡＮ、ＲＦＩＤ、ＩＲまたはＩＳＭを使用するものである、請求項１９から４０のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項４２】
前記移動体通信網と通信する手段（１６０）は、ある通信プロトコルを用いて通信するものであり、ここで、前記クエリオブジェクトは、該通信プロトコルを用いて通信をすることができないものである、請求項１９から４１のいずれか一項に記載のユビキタスゲートウェイ（１５０）。
【請求項４３】
移動体通信網と通信するステップと、
複数のユビキタスゲートウェイと通信するステップと、
オブジェクト識別子を有するオブジェクトと通信するステップと、
オブジェクトレコード識別子と、オブジェクト識別子と、オブジェクト位置とを含むオブジェクトレコードを一時的に保存するステップと、
オブジェクトとの通信によりオブジェクトを監視するステップと、
監視されたオブジェクトのオブジェクトレコードを保存するステップと、
ユビキタスゲートウェイとの間でオブジェクトレコードを繰り返し交換するステップと、
クエリオブジェクトに関するレコード要求を前記移動体通信網から受け取るステップと、
前記クエリオブジェクトに関するオブジェクトレコードを前記移動体通信網へ提供するステップと
を含む、複数のユビキタスゲートウェイを有する移動体通信網において通信を行う方法。
【請求項４４】
請求項４３に記載の方法をプロセッサに実行させるプログラムコードを有するコンピュータプログラム。
【請求項４５】
請求項１から１６のいずれか一項に記載のグローバルクエリマネージャと、請求項１９から４２のいずれか一項に記載のユビキタスゲートウェイとを有するシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子識別（electronical identification）の需要が増加するにつれてますます重要な問題となっている、通信網におけるオブジェクトクエリ（object query：オブジェクト問い合わせ）の分野に関する。
【背景技術】
【０００２】
携帯電話は、例えばセルラ移動体通信網などのグローバルネットワーク内の仮想情報と、ローカルネットワーク、すなわち、センサネットワークなどの携帯電話の周囲のユビキタスネットワーク内の実世界情報との間の媒介（mediation）を可能にする。というのも、携帯電話はグローバルな接続機能と近距離の接続機能を有するからである。この点に関して携帯電話は、しばしばユビキタスゲートウェイ（UG: Ubiquitous Gateway）と呼ばれる。サービスプロバイダは、このユビキタスゲートウェイ機能を利用して、国全体にわたるサービスにまで及ぶ大規模なエリアをカバーするには特にコストのかかる、別個のセンサインフラストラクチャを配備する費用を節約することができる。
【０００３】
実世界のオブジェクトは、インターネットや通信網などのグローバルネットワークに接続していないため、これらのオブジェクトの追跡またはサーチは困難である。ＲＦＩＤ（Radio Frequency Identification）を使ってオブジェクトにタグ付けするといった、現在のオブジェクト追跡またはオブジェクトサーチの方法は、特に、スーパーマーケット、ＣＤ（Compact Disc）販売店、その他の流通管理領域などの限られた領域内でのみ機能する。しかし、これらの方法では、都市単位のような大規模エリアにおける追跡またはサーチの解決法、および、ある特定のクラスのオブジェクトだけに限定されない解決法のいずれも実現できない。その理由としては、適切な大規模サーチインフラストラクチャを展開するコスト、および多数のオブジェクトを追跡する際のネットワーク接続コストという問題がある。
【０００４】
近年、ＵＧとも呼ばれる、近距離通信機能（NFC: Near Field Communication）を備えた携帯電話が普及してきている。携帯電話は、すでに広域インフラストラクチャ、すなわちセルラネットワークを備えるため、より広いエリアの周囲に専用のセンサを配備しなくても、タグ付けされたオブジェクトをサーチし、または追跡するのに使用することができる。
【０００５】
図１７は、従来型のシナリオを示している。図の左側には、移動体通信網などのグローバルネットワーク１７１０が示されている。グローバルネットワーク１７１０は、サービスインフラストラクチャ１７２０を提供し、基地局１７３０などを利用し、無線通信を使ってモバイル機器１７４０と通信する。無線通信は、例えば、ＧＳＭ（Global System for Mobile Communication）、ＵＭＴＳ（Universal Mobile Telecommunication System）、ＬＴＥ（Long Term Evolution）、ＷＬＡＮ（Wireless Local Area Network）などの第３世代または第４世代の移動体通信システムに基づいて実行される。
【０００６】
モバイル機器１７４０はユビキタスゲートウェイとみなすことができる。というのは、モバイル機器１７４０は、例えば、ＷＬＡＮ、ブルートゥース、ＲＦＩＤ（Radio Frequency Identification）、ＩＳＭ（Industrial, Scientific and Medical radio frequencies）、その他の種類のＮＦＣ（Near Field Communication）などの無線通信規格または機構を使ったいくつかの別のインターフェースも動作させるからである。
【０００７】
図１７に示すようにモバイル機器１７４０は、上記の通信技術を使って、実世界オブジェクト１７５０、中でも例えば、ローカルネットワーク、ＲＦＩＤタグ付き袋（bag）などのタグ付きオブジェクト、電子装置などと通信する。実世界オブジェクトの範囲には全く制限がなく、例えばＲＦＩＤタグなどを、任意のオブジェクトと共に、例えば図１７の右側の略図で示すような人に対しても使用することができ、生徒にタグを付けることさえもできる。モバイル機器はさらに、物理的尺度（physical measure）を監視するセンサ、パーソナルエリアネットワーク（PAN: Personal Area Network）のための手段、タグ付きのオブジェクトおよび人を監視する手段、ブルートゥースビーコンなどを備えることができる。加えて、グローバルネットワーク１７１０は、例えばＩＰベースのセルラネットワーク（IP: Internet Protocol）、ワールドワイドウェブ、インターネットなどの広域情報網とすることもできる。
【０００８】
図１８は、従来型のシステムを説明するための別のシナリオを示す。図１８には、いくつかのモバイル機器が接続されたグローバルネットワーク１８１０が示されている。中には例えばユーザＡ１８２０、自動車１８３０、オフィス１８４０、およびユーザＢ１８５０などが含まれる。加えて図１８には、モバイル機器１８３０と通信することのできるタグ付きオブジェクト１８６０と、別のネットワーク１８８０を介してユーザＢ１８５０と通信できる別のタグ付きオブジェクト１８７０も示されている。別のネットワーク１８８０は、アクセスポイント、ＲＦＩＤリーダ、オブジェクトセンサ、ブルートゥースモジュールなどを備えるＰＡＮとすることができる。
【０００９】
図１８に描かれたシナリオは、移動体通信が、それぞれ、移動体網、すなわちグローバルネットワーク１８１０を介して、誤って置かれたもの、紛失物、または盗難品を見つける際にどのようにして機能するかを示している。例えば紛失物や会社の備品が、例えば大学構内や、同僚、役員、訓練要員などの間で探知されたり、発見されたりする。さらに、自宅、自動車内、職場から離れた場所で私物をサーチするか、どこかで失くしたものをサーチすることができる。
【００１０】
オブジェクトをサーチするために都市などの大規模なエリア内のすべてのＵＧにクエリを送る「単純クエリ（Simple Query）」の方法は、高いネットワーク負荷をもたらし、携帯電話によるサーチが不都合なものとなる。他方、「単純更新（Simple Update）」の考え方に基づく解決法にも、あらゆる携帯電話がその周囲のすべてのオブジェクトを監視し、そのようなオブジェクトの状況のあらゆる変化を中央サーバに定期的に送るという点に問題がある。というのは、これもやはり高いネットワーク負荷をもたらし、携帯電話の電力消費をさらに増加させるからである。様々な研究論文において、実世界オブジェクトを位置決めし、各アイテムの存在を監視し、または各アイテムの紛失を回避することの妥当性を支持する議論が行われている。しかし、このようなシステムの多くは、特定のあらかじめ設置されたオブジェクト感知インフラストラクチャをもたらし、これを実施し、維持するには費用がかかる。
このようなシステムのうちのいくつかが非特許文献１〜５に記載されている。
【００１１】
リマインダシステムは、損失が発生する前にユーザに通知することに焦点を当てたものである。しかし一般に、タグ付きオブジェクトはしばしば意図的に置き去りにされることも想定され、したがってそうしたシナリオでは必ずしも即座に通知することが望ましいとは限らない。
【００１２】
また、オブジェクトサーチシステムは、後でオブジェクトの位置決めが必要になったときに問い合わせることのできる集中データベースに、事前にすべてのセンサの読取結果を送ることによって実施することもできる。この解決法を単純更新法と呼ぶこともできる。このようなシステムは、ＩｒｉｓＮｅｔ（非特許文献６参照）や、ＨｏｕｒＧｌａｓｓ（非特許文献７参照）などの広域データ収集システムの膨大な拡張可能性という課題に直面する。
【００１３】
また、分散感知システムに関する研究の中にも携帯電話と移動体通信網インフラストラクチャの使用を提唱するものがある。非特許文献８〜１０を参照されたい。
【００１４】
しかし、これらの考え方は、いずれも、オブジェクトをサーチするアプリケーションをとするものではなく、様々なユーザ携帯機器からの任意のセンサ情報を選択するものである。非特許文献１１では、絞り込み（スコーピング）機構に基づくシステムの方法が提示されている。この機構は、ユーザに関する情報評価により、世界規模などの大規模なグローバルドメインからセルラシステムの少数のセルなどのローカルドメインにサーチの焦点を絞り込む。この情報は、ユーザの移動履歴、ユーザのお気に入りの場所、家族および友人の情報、ならびにオブジェクトが最後に確認されたときの状況を含むことができる。そうした情報に基づきローカルドメインを選択することができる。このいわゆる絞り込みの後、サーチクエリをこのローカルドメイン内のＵＧに送ることができる。主として研究されている案には、最終確認位置が、仮に利用できる場合でも、例えば少数のセルなど、非常に大雑把なものとなる可能性があり、ローカルドメイン内でその位置の周囲のいくつかのＵＧだけが無作為に選択され、これらのＵＧにクエリがインストール（install）されるだけであるとい不都合点がある。
【００１５】
非特許文献１２では、最終確認情報、すなわち最終の接触（encounter）に基づくアドホックネットワークにおけるＩＰルーティングのための最終接触ルーティング（LER: Last Encounter Routing）が示されている。また、ＬＥＲの原理は、アドホックノードのＩＰアドレスではなく局所的な実世界オブジェクトにも適用することもできる。ＬＥＲアルゴリズムでは、各ノードがＮＦＣによりその近傍にある他のノードを定期的に監視し、最終確認の位置と時刻、すなわち各ノードが他のノードにいつどこで出会ったかを最終確認履歴として保存する。ノードＮＳがノードＮＤにパケットを送ろうとするとき、ＮＳは第１のアンカポイントとして働き、再帰的フラッディングによりその近傍にある他のノードにＮＤの最終確認履歴を尋ねる。最終確認履歴を見つけた後、ＮＳは、位置ベースのマルチホップルーティングを使って最終確認位置にある１つのノードにパケットを送り、このノードを新しいアンカポイントとして設定する。次いで新しいアンカポイントは、ＮＳが行ったのと同じプロセスを行う。最終的にはパケットがＮＤに届く。この考え方の不利な点は、再帰的フラッディングに時間がかかり、したがってクエリ成功時間がかなり長くなり得ることである。
【００１６】
アドホックネットワークにおける情報のサーチを改善する一手法は、あるノード上に保存された情報を、その近く、例えばｋホップ内の近隣ノードにコピーするものである。この手法は、アドホックネットワークにおけるゾーンルーティングプロトコル（ZRP: Zone Routing Protocol）と類似するものである。非特許文献１３を参照されたい。この手法はアドホックネットワークにおけるピアツーピア用途に適用されている（ゾーンベースのピアツーピア参照）。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】Gaetano Borriello,Waylon Brunette,Matthew Hall,Carl Hartung,and Cameron Tangney;Reminding about tagged objects using passive RFIDs;In Proceedings of the 6th International Conference on Ubiquitous Computing (UbiComp’04),Nottingham,England,September 2004
【非特許文献２】Christian Decker,Uwe Kubach,and Michael Beigl.Revealing the retail black box by interaction sensing;In 3rd International Workshop on Smart Appliances and Wearable Computing (SAWC’03) at ICDCS’03,Providence,RI,USA,May 2003
【非特許文献３】Hirobumi Shimizu,Osamu Hanzawa,Kenichiro Kanehana,Hiroki Saito,Niwat Thepvilojanapong,Kaoru Sezaki,and Yoshito Tobe;Association management between everyday objects and personal devices for passengers in urban areas;Demonstration Abstract in Adjunct Proceedings of Pervasive’05,Munich,Germany,May 2005
【非特許文献４】Roy Want,Kenneth P.Fishkin,Anuj Gujar,and Beverly L.Harrison;Bridging Physical and Virtual Worlds with Electronic Tags;In Proceedings of the ACM SIGCHI Conference on Human Factors in Computing Systems (CHI’99),pages 370-377,Pittsburgh,PA,USA,May 1999
【非特許文献５】Kok Kiong Yap,Vikram Srinivasan,and Mehul Motani.MAX:Human-centric search of the physical world; In Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems (SENSYS’05),San Diego,CA,USA,November 2005
【非特許文献６】Phillip B.Gibbons,Brad Karp,Yan Ke,Suman Nath,and Srinivasan Seshan.IrisNet:An architecture for a worldwide sensor web;IEEE Pervasive Computing,2(4),2003
【非特許文献７】Peter Pietzuch,Jonathan Ledlie,Jeffrey Shneidman,Mema Roussopoulos,Matt Welsh,and Margo Seltzer;Network-aware operator placement for stream-processing systems;In Proceedings of the 22nd International Conference on Data Engineering (ICDE’06),Atlanta,GA,USA,April 2006
【非特許文献８】J.Burke,D.Estrin,M.Hansen,A.Parker,N.Ramanathan,S.Reddy,and M.B.Srivastava.Participatory sensing.In SENSYS’06Workshop onWorld-Sensor-Web:Mobile Device Centric Sensor Networks and Applications (WSW’06),Boulder,CO,USA,November 2006
【非特許文献９】Shane B.Eisenman,Gahng-Seop Ahn,Nicholas D.Lane,Emiliano Miluzzo,Ronald A.Peterson,and Andrew T.Campbell;MetroSense project:People-centric sensing at scale.In SENSYS’06 Workshop on World-Sensor-Web:Mobile Device Centric Sensor Networks and Applications (WSW’06),Boulder,CO,USA,November 2006; SensorPlanet.www.sensorplanet.org,2007
【非特許文献１０】Dirk Trossen and Dana Pavel;Building a ubiquitous platform for remote sensing using smartphones;In Proceedings of the 2nd Annual International Conference on Mobile and Ubiquitous Systems:Networks and Services (MobiQuitous’05),pages 485-489,July 2005
【非特許文献１１】Elsevier Mobile and Pervasive Computing Journal,C.Frank,P.Bolliger,F.Mattern and W.Kellerer; The Sensor Internet at Work:Locating Everyday Items Using Mobile Phones (2007)
【非特許文献１２】M.Grossglauser,M.Vetterli;Locating Nodes with EASE:last Encounter Routing in Ad Hoc Networks through Mobility Diffusion;In Proceedings IEEE INFOCOM 2003
【非特許文献１３】Z.J.Haas and M.R.Pearlman,The Performance of Query Control Schemes for the Zone Routing Protocol,IEEE/ACM Trans.Networking,9,2001
【発明の概要】
【発明が解決しようとする課題】
【００１８】
本発明の目的は、ネットワーク内のオブジェクトのクエリを行うための改良された概念を提供することである。
【課題を解決するための手段】
【００１９】
この目的は、請求項１に記載のグローバルクエリマネージャ（ＧＱＭ：Ｇｌｏｂａｌ  Ｑｕｅｒｙ  Ｍａｎａｇｅｒ）、請求項１７に記載のクエリ方法、請求項１９に記載のユビキタスゲートウェイ、請求項４３に記載の通信方法、および請求項４５に記載のシステムによって達成される。
【００２０】
本発明は、ユビキタスゲートウェイの機能を携帯電話などとして活用することができ、実世界オブジェクトの位置決めなどの実世界情報のサーチをサポートするシステムおよび機構を、ＵＧを介した実世界情報の収集および保存に基づいて実現することができるという知見に基づくものである。各実施形態は、低ネットワーク負荷および低電力消費という利点を同時に提供することができる。携帯電話またはユビキタスゲートウェイの間の通信は、近距離通信による局所的なものと、セルラネットワークによる広域的なものとすることができる。したがって、ネットワークトラフィックを、クエリおよび情報更新の回数を含めて、携帯電話またはユビキタスゲートウェイの間でおそらくは局所的に共用される追加情報により低減することができ、しかもオブジェクトを短期間に見つけることができる。さらに、各実施形態は、より有益なのが局所的情報交換の使用か、情報キャッシングか、それともグローバルネットワークの使用かを判定して、適用要件に適合させることができるという利点を提供することもできる。
【００２１】
各実施形態は、例えばオブジェクトＸがセンサＡにより確認される際などのセンサ読取結果の数はクエリの回数よりずっと大きくなるものと予期されるため、リアクティブな、すなわちクエリベースの手法を利用できる。各実施形態は、このリアクティブな手法を、物理的に近接した携帯電話、すなわちユビキタスゲートウェイの間の局所的でプロアクティブな情報更新により強化できるが、すべての感知情報を中央データベースで保持する必要はない。各実施形態は、サーチルーティングを改善するためにセルラインフラストラクチャを利用することができる。サーチクエリを改善するためにクエリ先の携帯電話またはユビキタスゲートウェイ上に保存された情報を考慮することにより利益を得ることができる。また各実施形態は、ＬＥＲなどの別のシステムと共に使用されてもよく、別のシステムは絞り込みサーチをある一定の領域まで絞り込む適切な手法を提供することもできる。さらに各実施形態は、より小さいオーバーヘッドを伴ってより高速で収束することによりクエリを改善するために従来のアルゴリズムに適用することができる。
【００２２】
したがって各実施形態は、ユビキタスゲートウェイがその近傍にあるノードを監視し、他のノードの間で全く情報を交換しなくてもよいため、電力消費を節約するという利点を提供し得る。広域的位置データベースを使用し、オーバーヘッドを低減し、サーチを加速するためにグローバルネットワーク、すなわちセルラパスを介してルーティングすることにより、位置ベースのマルチホップルーティングパスを改善することができる。さらに、各実施形態は、アンカが交替する間のサーチ不可能期間を回避するために、目標アンカポイント位置の周囲にいくつかのクエリを並行して組み込む（install）こともできる。各実施形態では、オブジェクトのサーチを改善するために、利用可能な情報またはオブジェクトに関するデータが局所的に共用できる。
【００２３】
本発明の各実施形態は、ローカルネットワークとグローバルまたはセルラネットワークの間を媒介するオブジェクトセンサとして動作するように携帯電話またはＵＧを活用することができるため、オブジェクト感知のためのインフラストラクチャをインストールすることを必要とせずに実世界オブジェクトのサーチを可能にする。例えば携帯電話などにキャッシュされたオブジェクトに関する情報に基づき、各実施形態は、他の類似の解決法、例えば「単純クエリ」、「単純更新」、「無作為クエリ」などの組込み方法（installation method）より高速で、ネットワーキングオーバーヘッドがより小さいオブジェクトの発見を可能にする。
【００２４】
各実施形態は、反応的な概念が採用されているため、キャッシュ情報の交換が行われなくてもよいという利点を提供することができる。したがって、各実施形態は、ＵＧまたは携帯電話のプライバシを強化し、電力消費を節約することができる。さらに各実施形態は、マルチホップルーティングではなくグローバルネットワークを利用することによりサーチ待ち時間も低減し得る。ＵＧは、実施形態によっては、クエリルーティングのためのマルチホップ通信を完全に回避することができるように、感知だけに使用できる。したがって各実施形態は、未接続のアドホックネットワークと共に動作することもできる。各実施形態によれば、クエリプロセスの間のネットワーク負荷を、従来の考え方、例えば、単純クエリ、単純更新、無作為クエリなどを用いた場合の負荷より低く保つことができる。さらに各実施形態は、ＬＥＲより低い待ち時間を達成し、動くオブジェクトを追跡することもできる。
【００２５】
各実施形態は、例えば、電力寿命が重要であるときには、コストの高いＮＦＣ通信の低減を可能にするので、基本的にどんな環境でも使用され得る。さらに各実施形態は、一時的に断片化されたサーチ領域や中程度のサーチ領域でも機能する。また各実施形態は、人、モバイル機器によって提供されるサービスなどの実世界情報や、ＩＰアドレス（IP:Internet Protocol）などの識別子をサーチする他の用途の事例にも、モバイルアドホックネットワークにおいても使用できる。この点から見ると、オブジェクトという用語は情報を指すものでもある。
【００２６】
以下、本発明の各実施形態を添付の図面を使って詳細に説明する。
【図面の簡単な説明】
【００２７】
【図１ａ】グローバルクエリマネージャの一実施形態を示す図である。
【図１ｂ】ユビキタスゲートウェイの一実施形態を示す図である。
【図２ａ】オブジェクトレコードの一実施形態を示す図である。
【図２ｂ】ユビキタスゲートウェイレコードの一実施形態を示す図である。
【図３ａ】ＧＱＭの一実施形態を示す流れ図である。
【図３ｂ】ＧＱＭの一実施形態を示す流れ図である。
【図４】ＧＱＭにおけるクエリプロセスの一実施形態を示す流れ図である。
【図５】ＵＧにおけるメインループの一実施形態を示す流れ図である。
【図６】ＵＧにおけるオブジェクトサーチクエリの一実施形態を示す流れ図である。
【図７】ＵＧにおけるアンカクエリプロセスの一実施形態を示す流れ図である。
【図８ａ】１つのシナリオ例を示す図である。
【図８ｂ】別のシナリオ例を示す図である。
【図８ｃ】通信シーケンスの一例を示す図である。
【図９】ＵＧ密度に対する平均クエリ成功時間のシミュレーション結果を示す図である。
【図１０】ＵＧ密度に対するグローバルネットワーク使用量のシミュレーション結果を示す図である。
【図１１】オブジェクト密度に対するＮＦＣ使用量に関するシミュレーション結果を示す図である。
【図１２】１時間当たりのクエリ数に対するＮＦＣ総使用量に関するシミュレーション結果を示す図である。
【図１３】オブジェクト密度に対する平均クエリ成功時間を示す図である。
【図１４】ＵＧキャッシュサイズに対する平均クエリ成功時間を示す図である。
【図１５】オブジェクト可動比率に対する平均クエリ成功時間に関するシミュレーション結果を示す図である。
【図１６】ＵＧ密度に対するネットワークコストに関するシミュレーション結果を示す図である。
【図１７】従来技術のシナリオを示す図である。
【図１８】従来技術の移動体通信網を示すブロック図である。
【図１９】従来技術の絞り込みアルゴリズムを示す図である。
【発明を実施するための形態】
【００２８】
図１ａは、移動体通信網と通信し、オブジェクトレコードを保存する移動体通信機器である複数のユビキタスゲートウェイ（ＵＧ）を備える移動体通信網において動作するグローバルクエリマネージャ１００（ＧＱＭ）であって、複数のユビキタスゲートウェイと通信し、ユビキタスゲートウェイから受け取ったオブジェクトレコードを検出する手段１１０を備えるグローバルクエリマネージャ１００（ＧＱＭ）を示している。さらにグローバルクエリマネージャ１００は、ユビキタスゲートウェイにより報告された、オブジェクトレコード識別子（object record identification）と、オブジェクト識別子（object identification）と、オブジェクト位置（object record）とを含むオブジェクトレコードを一時的に保存するオブジェクトキャッシュ１２０を備えている。さらにグローバルクエリマネージャ１００は、クエリ元からクエリオブジェクトのレコード要求を受け取り、そのレコード要求をクエリユビキタスゲートウェイへ転送するコントローラ１３０を備える。このコントローラは、オブジェクトキャッシュ１２０からのオブジェクトレコードに基づいてクエリユビキタスゲートウェイを選択する。
【００２９】
実施形態では、コントローラ１３０は、オブジェクトキャッシュ１２０にクエリオブジェクトに関するレコードがないときに、クエリユビキタスゲートウェイを無作為に選択することができる。オブジェクトキャッシュ１２０はさらに、オブジェクトレコードを報告しているユビキタスゲートウェイ上のユビキタスゲートウェイレコード、オブジェクト最終確認時刻のタイムスタンプ、オブジェクトがユビキタスゲートウェイにより継続して監視されていた期間、オブジェクトが移動可能であるか否かにかかわらず推定される最終確認位置、オブジェクトレコードを交換しているユビキタスゲートウェイの履歴、またはオブジェクトレコードが伝搬する際のホップの数からなるグループのうちの１つまたはこれらの組み合わせを保存することができる。コントローラ１３０は、クエリオブジェクトに関するオブジェクトレコードを報告したユビキタスゲートウェイに基づいてクエリユビキタスゲートウェイ（ＵＧ）を選択することができる。コントローラ１３０は、オブジェクトキャッシュ１２０に保存されたクエリオブジェクト位置に基づいてクエリユビキタスゲートウェイを選択することもできる。各実施形態では、コントローラ１３０は、クエリＵＧにサーチクエリをインストールしてもよく、クエリＵＧは近距離通信（ＮＦＣ）を使って、別のＵＧからのクエリオブジェクト、またはユビキタスゲートウェイにプロアクティブにクエリオブジェクトをサーチするよう指示する、インストール済みのサーチクエリへの応答としてのクエリオブジェクトのオブジェクトレコードを要求する。
【００３０】
コントローラ１３０は、クエリＵＧ（query UG）から別のＵＧへのレコード要求の転送に基づいてオブジェクトレコードを受け取り、別のＵＧもまたそのレコード要求を転送する。コントローラ１３０は、レコード要求と存続期間（lifetime）を関連付けることができ、レコード要求の存続期間が満了したときにクエリ元に通知することもできる。
【００３１】
コントローラ１３０は、オブジェクトキャッシュ１２０からのクエリオブジェクトに関するオブジェクトレコードよりも新しいクエリオブジェクトに関するオブジェクトレコードを有する可能性の高いＵＧへレコード要求を転送することができる。さらにコントローラ１３０は、クエリオブジェクト位置の近傍（vicinity）に位置するＵＧへレコード要求を転送することができる。この近傍は、移動体通信網により、例えば三角測量（triangulation）によるか、またはクエリオブジェクトのオブジェクト位置の情報がオブジェクトキャッシュ１２０から入手できる場合にはオブジェクトキャッシュ１２０により決定することができる。コントローラ１３０はレコード要求を所定数のＵＧへ転送することもできる。さらにコントローラ１３０はサーチクエリを所定数のＵＧへインストールすることもできる。コントローラ１３０は、クエリ元に最新のクエリオブジェクト位置を提供することができ、クエリ元は例えばＵＧや別のネットワークノードとすることができる。
【００３２】
各実施形態において、通信手段１１０は、ＧＳＭ（Global System for Mobile Communication）、ＵＭＴＳ（Universal Mobile Telecommunication System）、ＬＴＥ（Long Term Evolution）、ＦＯＭＡ（Freedom of Mobile Multimedia Access）および／またはＷＬＡＮ（Wireless Local Area Network）に従って通信することができる。通信手段１１０は、クエリオブジェクトが通信するのに使用することのできない通信プロトコルを使って通信することができる。
【００３３】
各実施形態は、複数のユビキタスゲートウェイを有する移動体通信網においてユビキタスゲートウェイにクエリを行う方法を含む。ここで、ユビキタスゲートウェイは、移動体通信網において通信を行うことができ、オブジェクトレコードを保存するモバイル機器である。この方法は、複数のユビキタスゲートウェイと通信するステップと、ユビキタスゲートウェイが報告する、オブジェクトレコード識別子と、オブジェクト識別子と、オブジェクト位置とを含むオブジェクトレコードを一時的に保存するステップと、クエリ元からクエリオブジェクトのレコード要求を受け取るステップとを含む。さらにこの方法は、レコード要求を、オブジェクトレコードに基づいて選択されるクエリユビキタスゲートウェイへ転送するステップと、クエリオブジェクトに関するオブジェクトレコードをクエリ元に報告するステップとを含むことができる。
【００３４】
図１ｂは、複数のＵＧを有する移動体通信網において通信を行うＵＧ１５０の一実施形態を示す。ＵＧ１５０は、移動体通信網と通信する第１の手段１６０と、他のＵＧと通信し、オブジェクト識別子を有するオブジェクトと通信する第２の手段１７０とを備えている。第２の通信手段１７０は、オブジェクトから受け取るオブジェクトレコードを検出する。さらにＵＧ１５０は、オブジェクトレコード識別子と、オブジェクト識別子と、オブジェクト位置とを含むオブジェクトレコードを一時的に保存するオブジェクトキャッシュ１８０を備えている。ＵＧ１５０はさらに、第２の通信手段１７０を介してオブジェクトを繰り返し監視し、監視されたオブジェクトのオブジェクトレコードをオブジェクトキャッシュ１８０に保存するコントローラ１９０を備える。コントローラ１９０はさらに、クエリオブジェクトに関する移動体通信網からのレコード要求を受け取り、第１の通信手段１６０を介してオブジェクトキャッシュ１８０から移動体通信網へサーチオブジェクトに関するオブジェクトレコードを提供する。
【００３５】
各実施形態においてオブジェクトキャッシュ１８０は、オブジェクトが最後に監視されたときのタイムスタンプを保存することができる。さらにコントローラ１９０は、第２の通信手段１７０を介して他のＵＧとオブジェクトキャッシュ１８０を交換することができる。オブジェクトキャッシュ１８０は、オブジェクトを監視したことのあるＵＧのＵＧ識別子（UG identification）を保存することができる。オブジェクトキャッシュ１８０は、オブジェクトがどれほどの長さにわたって監視されたかを示すオブジェクトの所属期間（belonging period）を保存することができる。オブジェクトキャッシュ１８０はさらに、オブジェクトが移動しているかそれとも移動していないかに関する情報を保存することもできる。さらにオブジェクトキャッシュ１８０は、オブジェクトレコードが報告された経路を保存することができる。例えば、オブジェクトレコードがどれほどのホップを経由して報告されたかを示すホップの数を保存することもできる
【００３６】
各実施形態においてＵＧは、ＵＧレコードを保存するＵＧキャッシュをさらに備えることもできる。ＵＧレコードは、ＵＧレコード識別子またはＵＧ識別子、および任意ではあるが、ＵＧ位置、ＵＧ最終確認時刻、推定された最終確認位置、平均ＵＧ速度、ＵＧ速度の標準偏差、ＵＧレコードを転送したＵＧの履歴、またはＵＧレコードが経由して報告されたホップの数からなるグループのうちの１つまたはこれらの組み合わせを有する。コントローラ１９０は、第２の通信手段１７０を介してＵＧキャッシュから他のＵＧへＵＧレコードを報告することもできる。コントローラ１９０は、ＵＧからＵＧレコードを受け取り、受け取ったＵＧレコードを用いてＵＧキャッシュを更新することもできる。
【００３７】
実施形態によっては、コントローラ１９０は、サーチクエリ元からクエリオブジェクトのサーチクエリを受け取り、第２の通信手段１７０を介してそのサーチクエリを他のＵＧへ転送することができる。コントローラ１９０はさらに、クエリオブジェクトと通信しようと試みることもできる。サーチクエリはユビキタスゲートウェイ１５０へ、積極的に（proactively）クエリオブジェクトをサーチするよう指示する。サーチクエリ元は、移動体通信網のネットワークエンティティである別のＵＧ、またはグローバルクエリマネージャとすることもできる。
【００３８】
コントローラ１９０は、クエリオブジェクトに関するオブジェクトレコードをサーチクエリ元へ提供することもできる。さらにコントローラ１９０は、複数の他のＵＧがクエリオブジェクトに関するオブジェクトレコードを報告する場合など、利用可能なときには、クエリオブジェクトに関する複数のオブジェクトレコードの中から、提供するための最新のオブジェクトを選択することもできる。またコントローラ１９０はレコードクエリ取り消しを受け取り、それゆえそのレコードクエリ取り消しを、コントローラ１９０がクエリを転送した相手のＵＧへ転送することもできる。コントローラ１９０は、レコード要求を転送された相手のユビキタスゲートウェイのユビキタスゲートウェイ識別子を保存し、クエリオブジェクトが見つかったとき、またはレコード要求が取り消されたときに、レコード要求を転送された相手のすべてのユビキタスゲートウェイへレコード要求の取り消しを要求することができる。コントローラ１９０は、インストールされたサーチクエリを削除することもできる。
【００３９】
各実施形態においてコントローラ１９０は、サーチクエリを何回転送することができるかに制限を設けることができる。ユビキタスゲートウェイ１５０は、さらに自己の位置を決定する手段を備えることもできる。自己の位置を決定する手段は、ＧＰＳ（Global Positioning System）受信機を備えることもできる。ユビキタスゲートウェイ１５０は、オブジェクトレコードとユビキタスゲートウェイレコードを用いて作成されるブルーム（Bloom）フィルタを備えることもできる。
【００４０】
各実施形態において第１の通信手段１６０は、セルラ移動体通信網において通信を行うこともできる。移動体通信網は、ＧＳＭ（Global System for Mobile Communication）、ＵＭＴＳ（Universal Mobile Telecommunication System）、ＬＴＥ（Long Term Evolution）、ＦＯＭＡ（Freedom of Mobile Multimedia Access）、ＷＬＡＮなどのネットワークとすることができる。
【００４１】
各実施形態において第２の通信手段１７０は、ブルートゥース、ＷＬＡＮ、ＲＦＩＤ、ＩＲ（Infrared（赤外線））、ＩＳＭ（Industrial, Scientific and Medical Radio Bands）などの通信を使用することもできる。移動体通信網と通信手段１６０とは、クエリオブジェクトが通信するのに使用することのできない通信プロトコルを使って通信することもできる。実施形態によっては、前述のＧＱＭ１００の実施形態と前述のＵＧ１５０の実施形態とを含むシステムとして実施できる形態もある。
【００４２】
各実施形態は、例えば携帯電話などの前述のＵＧ機能を活用した、実世界オブジェクトの位置などの実世界情報のサーチをサポートするシステムおよび機構を備えている。これは、携帯電話などにより実世界情報またはレコードを収集し、保存することに基づくものである。
【００４３】
各実施形態は、以下でアンカサーチ（anchor search）ともいう、オブジェクトの位置に関するヒントのサーチとオブジェクトのサーチとの分離に基づくものとすることができる。各実施形態では、ＵＧまたは携帯電話の間の情報交換が行われなくてもよい。言い換えると、各実施形態は、純粋にリアクティブな機構だけに基づいてオブジェクトに関するより新しい情報を決定することもできる。さらに、これらのヒントに従ってアンカからサーチを再開することにより、グローバルネットワークを使って、サーチされるオブジェクトに向けて局所的サーチを段階的に改良する（refine）こともできる。このような実施形態では、グローバルネットワークは、マルチホップ式でオブジェクトへのルーティングを行うのではなく、より適切な位置へとジャンプすることが可能になる。ＬＥＲ（M.Grossglauser、M.Vetterli参照）と同様に、携帯電話またはＵＧは、最後に確認されたオブジェクトに関する情報を保存するだけで、この情報を伝搬する必要はない。したがって各実施形態では、ＮＦＣトラフィックの量が低減され、電力コストが節約できるという利点がある。ＮＦＣインターフェースは、上記説明の第２の通信手段１７０に対応する。
【００４４】
さらに上記説明によれば、移動体通信網内、すなわち個々にグローバルネットワーク内にあるグローバルクエリマネージャがサーチを調整（coordinate）することもできる。ＧＱＭは、オブジェクトＯＤのサーチクエリを受け取ると、第１のＵＧ１をアンカポイントとして選択し、可能な場合にはＵＧ１からＯＤに関するレコードを取得する。サーチクエリは、別のＵＧ、またはそれぞれ別のネットワークもしくはネットワークエンティティなどから受け取ることもできる。基本的にＵＧ１は無作為に選択されるが、ＧＱＭにあらかじめユーザの挙動パターン、以前のサーチ結果または類似の情報がある場合には、ＧＱＭはオブジェクトが発見され得る場所の可能性に基づいてすべての可能なＵＧをフィルタリングすることもできる。ＵＧ１にＯＤに関するレコードがない場合、ＵＧ１はアンカサーチクエリのフラッディングを開始し、ＮＦＣを使って、以前にＯＤに遭遇しているＵＧ２が見つかるまでアンカポイントをサーチする。ＵＧ２は、ＯＤ位置に関する新しいレコードをＧＱＭへ報告する。次いでＧＱＭは、新しい位置の周囲にあるいくつかのＵＧを選択し、それらにオブジェクトサーチクエリをインストールする。同時にＧＱＭはＵＧのグループの中から１つのＵＧ３を次のアンカポイントとして選択する。ＵＧ３は再度アンカサーチクエリを流布（spread）する。このオブジェクトサーチとアンカサーチの組み合わせが、ＯＤの発見を可能にする。
【００４５】
したがって各実施形態は、ローカルドメインにおけるオブジェクトサーチまたはクエリの効率のよい考え方を提供する。また各実施形態は、例えばＣ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｉｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒによって開示された絞り込み機構などの従来のシステムを拡張して、大規模なグローバルドメインにも利用できる。
【００４６】
以下では一実施形態について詳細に説明する。またこの実施形態を、リアクティブＤＩＳ（Distributed Information Sharing（分散情報共用））ともいう。以下の実施形態は、グローバルネットワーク内のローカル中央サーバに置かれた、前述のようなグローバルクエリマネージャを使用する。積極的に他のＵＧとどんな情報も交換しないＵＧの一実施形態を想定する。しかし、本発明の別の実施形態では、情報を積極的に交換するＵＧを想定することもできる。詳細に説明する実施形態に関しては、ＵＧは、このＵＧが確認しているオブジェクトに関する情報を、監視の時刻および位置と共に保存するだけである。関与する各ＵＧは、監視したオブジェクトに関する情報を含むことのできるオブジェクトキャッシュを有する。可能なキャッシュ情報の一例を図２ａに示している。
【００４７】
図２ａには前述したようなオブジェクトキャッシュの一例が示されている。図２ａによれば、オブジェクトキャッシュ内のレコードは、オブジェクト最終確認時刻、オブジェクト識別子、およびオブジェクトをスキャンしたＵＧの識別子、オブジェクトがＵＧにより継続して監視された期間、オブジェクトが移動可能であるか否かにかかわらず推定された最終確認位置、このレコードを伝搬したＵＧの履歴、レコード伝搬のホップの数などからなるグループのうちの１つまたはこれらの組み合わせを含む。キャッシュサイズには限界があるため、オーバーフローした古いレコードは破棄できる。
【００４８】
ここで説明する実施形態に関しては、ＵＧは他のＵＧと積極的に情報を交換せず、ＵＧが確認しているオブジェクトに関する情報を監視の時刻および位置と共に保存するだけであるものと仮定する。しかし任意ではあるが、ＵＧの間で積極的に情報交換を行うこともできる。この場合ＮＦＣの負荷は増加するが、オブジェクトを発見する平均成功時間は減らすことができる。
【００４９】
ＵＧによって実行されるクエリを二種類に区別できる。ＵＧはオブジェクトの可能な位置に関するより新しいレコードを見つけるために、オブジェクトサーチクエリおよび／またはアンカサーチクエリを実行できる。
【００５０】
任意ではあるが、ＵＧの各実施形態はさらに、監視したＵＧに関する情報を含むＵＧキャッシュを備えることもできる。図２ｂは、ＵＧ最終確認時刻、ＵＧ識別子、推定される最終確認位置、ＵＧの平均速度、ＵＧ速度の標準偏差、レコードを転送したＵＧの履歴、ホップの数などを含み得るＵＧキャッシュ内のレコードの一例を示している。キャッシュサイズには限界があるため、オーバーフローした古いレコードは破棄できる。
【００５１】
ＵＧキャッシュは任意選択のものであり、各ＵＧにより保存でき、近隣のＵＧ、例えば、１ホップ先の近隣ＵＧなどへ送ることもできる。この場合の１ホップ先の近隣ＵＧは、第２の通信またはＮＦＣの手段（１７０）であってもよい。その場合、受信した近隣ＵＧは、レコードを自己のレコードと比較し、欠けているレコードを追加し、より古い自己のレコードを上書きし、またはより古い受信レコードを破棄する。ホップの数およびレコードの経路は、前述のものと同様にしかるべく更新される。キャッシュサイズには限界があるため、古いエントリはキャッシュから破棄できる。この説明の実施形態では、ＵＧキャッシュは任意選択であることを再度強調しておく。
【００５２】
図３は、ＧＱＭにおけるメインループの一実施形態のフローチャートである。ＧＱＭの実施形態は、クエリがインストールされない場合でさえも、図３に示すフローを連続して実行できる。フローは開始点であるステップ３０２から開始し、その後に戻り点「Ｂ」であるステップ３０４が続く。続いてステップ３０６でループが開始し、ここでＵＧ内のすべてのクエリが処理される。まず、ループ内のステップ３０８において、クエリ存続期間のカウンタ、すなわちquery_lifetimeを減らす。ステップ３１０で存続期間、すなわちカウンタquery_lifetimeが０に達しているかどうかがチェックされる。そうである場合、ステップ３１２でユーザに結果が示され、続くステップであるステップ３１４でクエリが削除される。次いでステップ３１６でループが終了し、ＵＧ内のすべてのクエリについてそれぞれループする。存続期間がまだ満了していない場合、オブジェクトサーチは、これに対応して、ステップ３１６のループの終了に達する前にステップ３１８で実行されるクエリサーチの処理を行う。すべてのクエリについてループした後、プロセスはステップ３２０において戻り点３０４に戻る。
【００５３】
言い換えると、ＧＱＭは、ステップ３０６とステップ３１６の間のループにおいて、すべてのインストール済みのクエリをしかるべく実行する。ＧＱＭは、ステップ３１０でクエリの存続期間をチェックする。存続期間が満了している場合、ＧＱＭはステップ３１２でユーザにクエリに失敗したことを通知し、次いでステップ３１４でクエリを削除する。クエリがまだ有効である場合には、ＧＱＭはステップ３１８でクエリプロセスを実行する。すべてのクエリを実行した後、ＧＱＭは点「Ｂ」すなわちステップ３０４へ戻る。
【００５４】
図３の右側には、クエリの成功または取り消しを受け取った場合のＧＱＭの動作を示す別のフローチャートが示されている。フローはステップ３２２から開始し、続いてステップ３２４でクエリ成功またはクエリ取り消しを受け取る。ステップ３２６でユーザに結果が示され、続いてステップ３２８で、受け取った場合にはクエリ取り消しが、ＧＱＭがクエリを送った相手の他のＵＧへ転送される。ステップ３３０で、現在のアンカが利用できるかどうか、すなわち変数current_anchorがヌルであるかどうかがチェックされる。ヌルでない場合、すなわち現在のアンカが利用できる場合には、ステップ３３２でアンカサーチクエリの取り消しが現在のアンカへ送られ、ステップ３３４で変数current_anchorがクリアされる。ステップ３３６でクエリが削除される。ステップ３３０において利用できる現在のアンカがなかった場合には、ステップ３３６ですぐにクエリを削除することができる。プロセスはステップ３３８で終了する。
【００５５】
さらに図３Ａの右側には、新しいレコードを受け取る場合のＧＱＭの動作に関する別のフローチャートが示されている。このフローはステップ３４０から開始し、続いてステップ３４２で新しいレコードが受け取られる。ステップ３４４でレコードが、前述のオブジェクトキャッシュに対応するＧＱＭキャッシュに追加される。ステップ３４６で、現在のアンカが利用できるかどうか、すなわち変数current_anchorの値がチェックされる。現在のアンカが利用できる場合、ステップ３４８でアンカサーチクエリの取り消しが上記現在のアンカへ送られ、ステップ３５０で変数current_anchorがクリアされ、その後ステップ３５２でプロセスが終了する。ステップ３４６で利用できる現在のアンカがない場合、プロセスはステップ３５２で直ちに終了する。
【００５６】
図３Ｂの左側には、アンカサーチ失敗を受け取ったときのＧＱＭの動作が示されている。プロセスはステップ３５４から開始し、続いてステップ３５６でアンカサーチ失敗を受け取る。ステップ３５８でアンカサーチクエリの取り消しが現在のアンカへ送られる。続いてステップ３６０で変数current_anchorがクリアされ、その直後にステップ３６２でプロセスが終了する。
【００５７】
ＧＱＭは、本実施形態では、ユーザまたは任意のネットワークノードからクエリオブジェクトＯＤをサーチするクエリを受け取ると、図４に示すアルゴリズムを実行する。図４に示すアルゴリズムは、３つの段階、すなわち「アンカサーチ」段階４００と、「最新レコード追跡」段階４０１と、「クエリインストール」段階４０２とを含む。すでに述べたようにこの実施形態では、各ＵＧは積極的にどんなキャッシュ情報も交換せず、クエリに応じて、近隣ＵＧが、クエリオブジェクトの位置、すなわちクエリオブジェクトを最後に確認した時刻に関するより新しい情報を提供することができるかどうかが調べられる。
【００５８】
クエリオブジェクトの位置がより確実なＵＧにより位置が提供され、これらのＵＧはアンカと呼ばれる。ＯＤに関するより新しいレコードが見つかるまでアンカサーチクエリがネットワークにフラッディングされる。アンカサーチによりレコードが見つかった場合、レコード内のこの最終確認位置の周囲のＵＧが新しいアンカポイントとみなされる。アンカサーチは数回繰り返して実行できる。「より新しい」という用語にはいくつかの基準がある。
【００５９】
最も単純な基準は、レコードＲ１内の情報生成時刻Ｔ１が別のレコードＲ２中の情報生成時刻Ｔ２より新しい、すなわち、Ｔ１＞Ｔ２の場合にはＲ１の方がより新しいというものである。別の基準は、現在時刻からＴ１を差し引いたものに等しいレコード存続期間Ａ１は、現在時刻からＴ２を差し引いたものに等しい別のレコード存続期間Ａ２のレートαより小さい、すなわちＡ１がαＡ２より小さく、例えばα＝１／２の場合、Ｒ１の方がより新しいというものである。別の実施形態では、時間基準だけでなく距離基準でもある別の基準を使用できる。例えば、レコードＲ１の生成位置がＲ２の生成位置から遠く離れている場合には、新しさは、Ｔ１＞Ｔ２を調べることにより比較でき、さもなければ、Ａ１＜αＡ２により比較できる。シミュレーション結果を生成するのに使用する以下の実現形態では、Ｔ１＞Ｔ２という第１の基準を用いる。
【００６０】
図４によれば、クエリプロセスのフローは開始点であるステップ４０３から開始し、続いてステップ４０４において、目標オブジェクトＯＤに関するレコードが利用できるかどうかをチェックし、利用できる場合には変数hit_rateレコードが適宜設定される。続くステップ４０６で、変数hit_recordをチェックすることにより、そのようなレコードが利用できたかどうかが判断される。ＧＱＭは、ＧＱＭオブジェクトキャッシュ内にＯＤに関するレコードがあるかどうかをチェックし、hit_recordを適宜設定する。ＧＱＭが例えば前のサーチの結果を保存している場合、ＧＱＭはその結果を使用する。関連するレコードがキャッシュにない場合、ＧＱＭは第１のアンカポイントとしてＵＧを選択する。基本的にはこのＵＧは無作為に選択されるが、ＧＱＭに事前にユーザの挙動パターン、以前のサーチ結果などの何らかの情報がある場合には、ＧＱＭは、クエリオブジェクトＯＤが発見され得る場所の可能性に従ってすべての可能なＵＧをフィルタリングすることができる。
【００６１】
次いでステップ４０８で現在のアンカがすでに利用できるかどうか、すなわち、変数current_anchorがチェックされる。ステップ４１０で利用できるcurrent_anchorがない場合、current_anchorとしてＵＧが無作為に選択され、アンカサーチクエリが送られる。ステップ４０８で利用できる現在のアンカがない場合、プロセスはステップ４１２で終了する。言い換えると、レコードが見つかるまでアンカサーチクエリが近隣ＵＧの間でフラッディングされる。現在のアンカポイントは、値current_anchorに保存される。アンカサーチによりレコードが見つかった場合、current_anchorはクリアされる。ステップ４０６でレコードが見つかった場合には、これに対応して、ＧＱＭキャッシュにより古いレコードがあるときに、ＧＱＭはステップ４１４で「最新レコード追跡」段階４０１を開始する。
【００６２】
ステップ４１４でＧＱＭは、現在のhit_recordが、last_hitと呼ばれる最後のループにおける前のレコードより新しいかどうかをチェックする。最初のループでは、last_hitがないため、hit_recordがより新しいはずである。次いでＧＱＭは、ステップ４１６でhit_recordから最終確認位置を取得する。ステップ４１８で、その位置の周囲にあり、まだＯＤに関するクエリをインストールしていないＵＧを選択し、それらのＵＧをlast_selected_UGとして保存する。ステップ４２０で、last_selectedUG内のすべてのＵＧについてループが開始される。ステップ４２２で、サンプル限界（sample limit）に達したかどうか、すなわち変数sample_limitがチェックされ、あるいはＵＧが最近の一定期間内にサンプリングされたかどうかがチェックされる。クエリを同じＵＧに複数回にわたりインストールすることは回避すべきであり、したがって２つのインストールの間には一定の期間を置くべきである。
【００６３】
ステップ４２４で、ＧＱＭは、目標オブジェクトＯＤに関するレコードを取得しようと試みる。ステップ４２２でサンプル限界に達しておらず、個々のＵＧが一定の妥当な期間内にサンプリングされなかった場合には、変数sample_limitを減らす。ステップ４２４に続いて、ＧＱＭはステップ４２６で、潜在的に見つかったレコードがhit_recordより新しいかどうかをチェックする。新しくない場合には、ループはステップ４２８で終了し、変数last_selected_UG内のすべてのＵＧについて実行される。ステップ４２６でhit_recordより新しいレコードが見つかった場合には、プロセスはステップ４３２に進み、そこでそのレコードがＧＱＭキャッシュ、すなわちオブジェクトキャッシュにそれぞれ保存される。プロセスは、ループの完了に続いてステップ４３０で、またはステップ４３２に続いてステップ４３４で開始点４０３に戻る。
【００６４】
言い換えるとＧＱＭは、last_selected_UG内のＵＧが、関連するレコードを有するかどうかをチェックする（サンプリング）。ステップ４２６でより新しいレコードが見つかった場合には、ＧＱＭはチェックを止め、ステップ４３２でそのレコードをＧＱＭキャッシュに保存し、ステップ４３４で開始点に戻る。ステップ４２６でより新しいレコードが相次いで見つかったときには、ＧＱＭは最新のレコードを更新する。各実施形態では、必ずしも「最新レコード追跡」段階４０１が実行されるとは限らない。またＧＱＭはこの機能をスキップすることもでき、最新のレコードではなく、単にアンカポイントが報告したレコードを使用するだけでもよい。サンプル数は変数すなわち値sample_limitで制限される。これはＧＱＭがＯＤの関連するレコードの有無をチェックすることのできる残りのＵＧの数である。この値は、ローカルドメインのサイズおよびＮＦＣコストによって決まる。例えばこの値は５０に設定できる。
【００６５】
最終的に、それ以上新しいレコードが見つからなくなると、すなわちhit_recordがlast_hitと等しい場合には、ＧＱＭはＯＤのクエリインストール段階を終了し、最新のレコードの位置の周囲にあるＵＧにおいてクエリを開始する。すなわちＧＱＭは「クエリインストール」段階４０２に入る。まず、ＧＱＭはステップ４３６でlast_selected_UGがヌルであるかどうかチェックする。ステップ４３８でＵＧが選択されない場合、ＧＱＭは、レコードによって示される目標位置にある既知のインストール済みのＵＧを選択し、これらをlast_selected_UGに設定する。このステップに続いてステップ４４０で、last_selected_UGからいくつかのＵＧが選択され、クエリがそれらのＵＧに向けて、しかるべきオブジェクト情報またはオブジェクトレコードにヒットしたことを示す「ヒット」モードで送られる。
【００６６】
last_selected_UGがヌルでない場合、ステップ４３６の直後にステップ４４０が続く。ＧＱＭはlast_selected_UGからすべてのＵＧ、あるいはいくつかのＵＧを確率論的に（stochastically）選択し、それらのＵＧに対してクエリをインストールする。クエリでは、例えば２に設定されるquery_hop_limitの値が更新され、「ヒット」モードに設定でき、レコード情報を含むこともできる。ステップ４０２で、ＧＱＭはlast_selected_UG内のすべてのＵＧを「インストール完了」とマーク付けをし、最後にステップ４４４でlast_selected_UGをクリアする。ＵＧを無作為に選択する理由は、これらのＵＧが相互に近接し、ＵＧは、セルラ接続を使用せずに、ＮＦＣにより同時にクエリをブロードキャストすることができるからである。
【００６７】
ステップ４４４の後、ＧＱＭは、図４の右下隅に示されている「アンカサーチ」段階４００に進む。まずステップ４４６で、current_anchorがヌルであるかどうかチェックされる。ヌルである場合ステップ４４８で、レコードが示す目標位置からＵＧが選択され、次いで変数current_anchorが設定され、サーチクエリがＵＧへ送られる。次いでステップ４１２でプロセスが終了する。
【００６８】
無作為選択の代わりに別の実施形態およびより進んだやり方を実行することもできる。例えば、ＧＱＭがあるＵＧにインストールするタイミングを使って、ＧＱＭは、そのＵＧから近隣ＵＧ情報を取得し、これらの近隣ＵＧを選択することを回避することができる。次いでＧＱＭはレコードが示す位置を継続して監視し、インストールされていない新しいＵＧが生じた場合にクエリを送る。この後、current_anchorがヌルである場合、ＧＱＭは、最新のレコードに基づく最終確認位置の周囲のＵＧを新しいアンカポイントとして設定する。次いでＧＱＭは再度アンカサーチクエリをフラッディングする。
【００６９】
オブジェクトサーチクエリまたはアンカサーチクエリによって新しいレコードが報告された場合には、ＧＱＭは再度「最新レコード追跡」段階４０１と、「クエリインストール」段階４０２を実行する。ＧＱＭは、常に最新のレコードの周囲にあるクエリオブジェクトをサーチする。また、これはオブジェクトが移動しているときにも機能する。というのは、ＧＱＭが最新のレコードに直ちに従うことができるからである。
【００７０】
各実施形態において、別のオプションとして、ＧＱＭが、開始点を無作為に選択するのではなく、最後のサーチの結果を保存してそれを同じオブジェクトのサーチの開始点として使用する場合には、より効率的なサーチ性能を得ることもできる。さもなければ、ＧＱＭにあらかじめユーザの挙動パターン、以前のサーチ結果などに関して何らかの情報がある場合には、ＧＱＭは、オブジェクトが発見され得る場所の可能性に基づいて可能なＵＧをフィルタリングすることもできる。別のオプションとして、オブジェクトＯＤをサーチするユーザは、サーチがどれほど重要であるかについてのポリシを指定することもできる。例えば、そのサーチが急を要するものでない場合には、ＧＱＭは、クエリインストールの数を減らし、サーチ成功時間を増加させることもできる。あるいは逆に、別の実施形態では、ユーザは、コストがかかってもかまわず、サーチ成功時間を短くしたい場合には、貪欲（greedy）ポリシを設定することもできる。
【００７１】
図５は、ＵＧにおけるメインループの一実施形態のフローチャートである。１つのシナリオでは、すべてのＵＧが図５に示すメインループを実行する。フローはステップ５００から開始し、その後に戻り点「Ｂ」としてのステップ５０２が続く。ステップ５０２の後にはステップ５０４が続き、そこで変数found_objectsおよび変数found_UGsをクリアする。ステップ５０６で、オブジェクトチェック期間が満了しているかどうか、すなわち、変数object_checked_periodがチェックされる。満了している場合にはステップ５０８において、ＵＧは近くのオブジェクトをチェックし、オブジェクトキャッシュを更新し、さらに変数found_objectsを設定し、変数object_check_periodをリセットする。したがって、メインループを定期的に実行するＵＧは、その近傍にあるオブジェクトを監視し、そのオブジェクトキャッシュを更新して、これらを配列（array）found_objectsに保存する。この期間は、ステップ５０６でチェックされるobject_check_periodの値によって定まり、この期間は例えば１〜５分とすることができる。
【００７２】
オブジェクトと同様にステップ５１０で、ＵＧチェック期間が満了しているかどうか、すなわち変数UG_check_periodがチェックされる。満了している場合、ステップ５１２で近くのＵＧがチェックされ、利用できる場合には任意ではあるが、ＵＧキャッシュが更新され、found_UGsなどのリストが更新され、UG_check_periodがリセットされる。ＵＧは、その近傍にあるＵＧを定期的に監視し、それらを配列として用いることのできるfound_UGsに保存する。以下では、プロセスを実行するＵＧをＵＧＥＸＥとも呼ぶ。ＵＧＥＸＥにＵＧキャッシュがある場合には、ＵＧＥＸＥはＵＧキャッシュを更新する。この期間は、値UG_check_periodによってカウントされるか、または定められる。
【００７３】
続くステップ５１４で、それぞれのカウンタobject_check_periodおよびUG_check_periodが減らされる。ステップ５１６で、ＵＧにおけるすべてのクエリについてループが開始する。ステップ５１８で存続時間クエリのカウンタ、すなわちquery_lifetimeが減らされる。続くステップ５２０で、存続期間がチェックされ、クエリ存続期間が満了している場合には、ステップ５２２でクエリが削除される。クエリがまだ有効である場合には、ステップ５２４において、クエリがオブジェクトサーチクエリであるか、それともアンカサーチクエリであるかがチェックされる。オブジェクトサーチクエリの場合には、ステップ５２６でオブジェクトサーチまたはクエリプロセスが実行される。アンカサーチの場合には、ステップ５２８でアンカサーチまたはクエリプロセスが実行される。ステップ５３０でＵＧ内のすべてのクエリについて実行されるループが終了し、続いてステップ５３２で戻り点５０２に戻る。ＵＧＥＸＥはループに従ってすべてのインストール済みのクエリを実行する。ＵＧＥＸＥは、まずステップ５２０でクエリの存続期間をチェックし、存続期間が満了している場合には、ステップ５２２でクエリを削除する。クエリがまだ有効の場合には、ＵＧＥＸＥはすべてのクエリを実行した後でクエリプロセスを実行し、ステップ５３２で点「Ｂ」に戻る。
【００７４】
図５の右側には、ＵＧがクエリ取り消しを受け取ったときのプロセスが示されている。このプロセスはステップ５３４から開始し、続いてステップ５３６でクエリ取り消しを受け取る。ステップ５３８では、クエリ取り消しが、クエリが転送された相手のすべてのＵＧへ送られ、ステップ５４０でクエリが削除される。プロセスはステップ５４２で終了する。
【００７５】
前述のように、ＵＧには２つのクエリプロセスがある。１つのプロセスは、図６に一実施形態のフローチャートが示されている、オブジェクトサーチのためのクエリプロセスである。もう１つは、図７に一実施形態のフローチャートが示されている、アンカサーチのためのクエリプロセスである。
【００７６】
ここで説明する実施形態では、ＵＧＥＸＥは、オブジェクトサーチクエリを受け取ると、図６のアルゴリズムを実行する。図６には、符号６００から開始する、ＵＧＥＸＥの近傍にあるオブジェクトまたはＵＧを監視する「オブジェクトおよびＵＧチェック」段階６０２と、ＵＧＥＸＥのオブジェクトキャッシュ内により新しいレコードがあるかどうかをチェックして、そのレコードをＧＱＭへ送る「新しいレコードのチェック」段階６０４とを有するアルゴリズムが示されている。
【００７７】
フローはステップ６００すなわち開始点「Ｆ」から開始する。ステップ６０６において目標オブジェクトが見つかるかどうかがチェックされる。このことは、図６において、変数found_objectsがヌルではないことと、目標オブジェクトが見つかるかどうかをチェックすることとによって示されている。目標オブジェクトが見つかった場合には、ステップ６０６でＵＧは、クエリ元へ成功したことを通知し、ステップ６１０においては、クエリを送ったＵＧへクエリ取り消しを送る。ステップ６１２でＵＧはクエリを削除し、ステップ６１４でプロセスが終了する。目標オブジェクトが見つかると、ＵＧＥＸＥはステップ６０８においてＧＱＭへ成功を通知し、次いでステップ６１２で自己のクエリを削除する。可能ならば、ステップ６１０でＵＧＥＸＥは、クエリを送った他のＵＧへクエリ取り消しを要求する。
【００７８】
目標オブジェクトが見つからなかった場合、ステップ６１６でＵＧは、近隣のＵＧが見つかるかどうかをチェックする。オブジェクトはまだ見つからないが、近隣ＵＧが見つかる場合には、ＵＧはステップ６１８で、クエリが「非ヒット」モードであるか、またはクエリホップ制限に達しているかをチェックする。これに該当しない場合には、ステップ６２０でＵＧはクエリをコピーし、ホップ制限を減らし、次いで、そのクエリがインストールされていない近隣ＵＧへそのクエリを送る。ＵＧは、クエリを転送するかまたはコピーした相手のＵＧを記憶する。ステップ６１８でクエリホップ制限に到達した場合、またはクエリが「非ヒット」モードでない場合には、ステップ６２０はスキップされる。オブジェクトはまだ見つからないが、近隣ＵＧが見つかる場合には、ＵＧＥＸＥはステップ６２０においてクエリをこれらのＵＧへコピーする。クエリが「ヒット」モードである場合には、query_hop_limitは１より大きい。query_hop_limitは、クエリを伝搬させることのできる残りの回数をカウントする変数である。この変数はＧＱＭにより、例えば、query_hop_limit=3などに設定できる。近隣ＵＧがすでにこのクエリをインストールしている場合には、ＵＧＥＸＥはこの実施形態ではクエリを再送しない。
【００７９】
ステップ６１６で近隣ＵＧが見つからない場合には、それぞれステップ６１８またはステップ６２０に続いて、ＵＧは「より新しいレコードのチェック」段階６０４に進む。最初にステップ６２２において、ＵＧは、関連するより新しいレコードがオブジェクトキャッシュ内にあるかどうかをチェックする。より新しい関連レコードがない場合、プロセスはステップ６２４で終了する。オブジェクトキャッシュに新しいレコードがある場合には、ＵＧはステップ６２６でその新しいレコードをＧＱＭへ報告し、ステップ６２４でプロセスを終了する。「より新しいレコードのチェック」段階６０４において、ＵＧは、ＯＤに関する新しいレコードがオブジェクトキャッシュにあるかどうかをチェックする。新しいレコードがある場合には、ＵＧＥＸＥはステップ６２６でそのレコードをＧＱＭへ報告する。ＵＧＥＸＥからレコードを受け取った後に、ＧＱＭはそのレコードをＧＱＭ内のオブジェクトキャッシュに反映させる。これは、図３のステップ３４０〜ステップ３５２で説明したとおりである。次いでＧＱＭは図４に示した「最新レコード追跡」段階４０１と、図４に示した「クエリインストール」段階４０２とを実行する。
【００８０】
ＵＧＥＸＥは、アンカサーチクエリを受け取ると、図７にフローチャートが示されているアルゴリズムを実行する。アンカサーチクエリは、目標オブジェクトＯＤとその最終確認時刻に関する情報をサーチする。サーチは常に、最終確認時刻より新しいＯＤに関するレコードを探すものである。図７に示すフローチャートは、開始点「Ｈ」７００から開始する。次いでＵＧＥＸＥは、ステップ７０２で、そのオブジェクトキャッシュにＯＤに関する新しいレコードがあるかどうかをチェックする。オブジェクトキャッシュに新しいレコードがある場合には、ＵＧＥＸＥはステップ７０４でそのレコードをＧＱＭへ報告する。続くステップ７０６で、ＵＧＥＸＥは、クエリを送ったＵＧへクエリ取り消しを送る。すなわちＵＧＥＸＥは、これらのＵＧに対して再帰的にクエリ取り消しを要求し、次いでステップ７０８で自己のクエリを削除する。
【００８１】
次いでステップ７１０でプロセスが終了する。ステップ７０２でＯＤに関するレコードがない場合には、ＵＧＥＸＥは、ステップ７１２でクエリホップ制限、すなわち変数hop_limitをチェックする。hop_limitに達した場合、すなわち変数query_hop_limitがヌルである場合には、ＵＧＥＸＥはステップ７１４でＧＱＭへアンカサーチの失敗を通知し、次いでステップ７０８で自己のクエリを削除する。さもなければ、ＵＧＥＸＥはステップ７１６でhop_limitを減らしたアンカサーチクエリを転送し、それをその近傍にあるＵＧへ送る。そして、ステップ７１６で、クエリが再帰的に送られ、最終的にＯＤに関するより新しいレコードが見つかる。ステップ７１６でクエリは、以前にそのクエリがインストールされていない近隣ＵＧへコピーされるだけである。クエリがインストールされているＵＧは保存される。ステップ７１６に続き、ステップ７１０でプロセスが終了する。
【００８２】
ＧＱＭは、ＯＤに関するレコードをアンカサーチの成功報告として受け取ると、図３のステップ３４０〜ステップ３５２に示したように、そのレコードをＧＱＭ内のオブジェクトキャッシュに反映させる。次いでＧＱＭは、current_anchorUGにクエリ取り消しを要求し、current_anchorをクリアする。図３のステップ３４０〜ステップ３５２を参照されたい。ＧＱＭは、アンカサーチ失敗を受け取った場合には、図３のステップ３５４〜ステップ３６２を実行する。current_anchorUGは、図５のステップ５３４からステップ５４２に示したように、クエリを送った他のＵＧへ再帰的にクエリ取り消しをフラッディングする。この実施形態では、最後には、関連するあらゆるＵＧがアンカサーチクエリを削除する。
【００８３】
ＧＱＭがＵＧからサーチの成功を受け取ると、ＧＱＭは各ＵＧＥＸＥに対して、そのクエリを取り消すよう要求を出す。これは、図３のステップ３２２〜３３８に示したとおりである。ＵＧＥＸＥは、他のＵＧへクエリを送っている場合には、図５のステップ５３４〜５４２に示したように、それらのＵＧに対して再帰的にクエリ取り消しを要求し、次いで自己のクエリを削除する。
【００８４】
この実施形態の一選択肢として、各ＵＧがＵＧキャッシュを有することができる。この場合、ＧＱＭは、ＵＧキャッシュを使って最終確認位置の周囲にある適切なＵＧを選択することができる。ＧＱＭは、最終確認位置の周囲にあるＵＧを選択するとき、通常どおりセル情報を使用する。この場合ＧＱＭは、約１００〜５００ｍの位置誤りまたは位置誤差を有するかもしれない。代替としてＧＱＭは、最終確認位置の周囲のいくつかのＵＧのＵＧキャッシュを使用し、所望の位置により近いＵＧを取得することもできる。この実施形態では、前述のアルゴリズムをさらに改善することができる。
【００８５】
図８ａは、２つのＵＧ８０２および８０４が描かれたシナリオを示している。ＵＧ８０４については、オブジェクトキャッシュ８０６を備えているが、ＵＧキャッシュは備えていないことが示されている。さらに、図８ａでは、ＵＧ８０２とＵＧ８０４の間の取り消された矢印により、これらのＵＧがそのオブジェクトキャッシュを定期的に交換しないということが示されている。さらにこのシナリオはＧＱＭ８０８と、ＧＱＭに接続され、ＧＱＭがＵＧ位置決めのために使用するＵＧ位置データベース８１０とを示している。このシナリオは、ＧＱＭがＵＧ位置データベース８１０からＵＧ位置に関する情報を取得できることを示している。前述の実施形態によれば、ＧＱＭはアンカポイントサーチの間に、ＵＧ位置データベースからＵＧ位置を決定することができる。さらに前述のようにＧＱＭ８０８は、クエリされたオブジェクトのより近くにある可能性の高い、より新しいレコードを有するＵＧ、すなわちアンカポイントを見つけるために、ＵＧへサーチクエリをインストールできる。アンカポイント、またはそれぞれ最も近いアンカポイントが決定された後で、そのアンカポイントにオブジェクトクエリをインストールすることができる。
【００８６】
図８ｂは、グローバルクエリマネージャ８２０と、以下にサーチ手順を詳述するのに使用されるいくつかのＵＧとを有する別のシナリオを示している。ＧＱＭ８２０は、クエリ要求を受け取った後で、第１のアンカＵＧとしてＵＧを無作為に選択する。これを、第１のアンカＵＧ８２４を指し示す矢印８２２で示している。第１のアンカＵＧ８２４からＵＧ８２６、８２８、８３０および８３２を指し示す矢印で示しているように、アンカサーチクエリはアンカＵＧ８２４により、より新しいレコードが見つかるまで流布（spread）される。これをＵＧ８３２のところに記載する例に示している。次いでＵＧ８３２は、ＧＱＭ８２０へ次のアンカポイントについて通知する。これを矢印８３４で示している。ＵＧ８３２から次のアンカポイントに関する通知を受け取ると、ＧＱＭ８２０は、最終確認位置の周囲にあるＵＧに対して、より新しいレコードを要求する。図８ｂにおいて、最終確認位置は、より新しいレコードを報告するＵＧ８３２から最終確認位置を指し示す矢印８３６によって示されている。ＵＧ８３２から通知を受け取ると、グローバルクエリマネージャ８２０は、新しいアンカポイントの周囲にあるＵＧに対して、より新しいレコードを要求する。これを、ＵＧ８４４、８４６、および８４８を指し示す矢印８３８、８４０、および８４２により示している。これらのＵＧの位置は、図８ａのＵＧ位置データベースなどにより知ることができる。図８ｂに示す例では、次にＵＧ８４６がＧＱＭ８２０へ、より新しい別のレコードに関して通知するものと想定され、これを矢印８５０で示している。
【００８７】
ＧＱＭ８２０は、ＵＧ８４６からアンカポイントに関する別の通知を受け取る。その位置は、図８ｂにおいて点線８５２で示されている。この通知に基づき、ＧＱＭ８２０は、図８ｂではＵＧ８５４、８５６、および８５８として表わされている新しいアンカポイントを選択する。前述の手順に従い、最新のレコードを受け取った後に、ＵＧ８５８が、実際のクエリオブジェクトのクエリがインストールされる次のアンカＵＧとして選択される。これは、図８ｂの二重の矢印８６０で示されている。
【００８８】
図８ｃは、ＧＱＭ８７０と４つのＵＧ８７２、８７４、８７６、および８７８とを示す別の簡略化したシナリオを示している。前述の機構によれば、ＧＱＭ８７０は、クエリオブジェクトのクエリを受け取り、クエリオブジェクトに関するレコードがあるかどうかをＵＧ８７２へ要求する。これを矢印８８０で示している。これに応じてＵＧ８７２は、ＧＱＭ８７０に対して、矢印８８２により示されているように、ＵＧ８７２がクエリオブジェクトに関するレコードを有するという通知を行い、情報を提供する。ＧＱＭ８７０は、ＵＧ８７２によって提供された情報から、クエリオブジェクトの位置を抽出し、この位置に基づき次のアンカＵＧ８７６を選択する。これを矢印８８４で示している。新しいアンカＵＧは、ＧＱＭへクエリオブジェクトに関する新しいレコードを報告することもできる。これを矢印８８６で示している。ＵＧ８７６のレコードが、ＧＱＭ８７０の取得できる最新のものであると仮定すると、ＧＱＭ８７０はＵＧ８７４、８７６、および８７８へオブジェクトクエリをインストールする。これらのＵＧは、すべてこの位置の近傍にあり、最新のレコードである。最終的にクエリオブジェクトが位置決めされる。
【００８９】
以下ではシミュレーション結果を提示する。シミュレーションは、ローカルドメインにおいて４つの異なる考え方について実行する。すなわち、Ｃ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｉｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒによって提案されたローカルドメインでの解決法である「全対象に対する単純なクエリ（Simple Query to All）」と、「無作為な対象に対する単純なクエリ（Simple Query to Random）」と、「リアクティブＤＩＳ（reactive DIS）」ともいう前述の実施形態と、ＬＥＲとである。「無作為な対象に対する単純なクエリ」法は、ローカルドメイン内のＵＧの４０％に対してクエリをインストールする。これは前述の論文で提示された解決法のデフォルト設定である。あらゆる解決法を、いくつかのデフォルト条件の下でシミュレートする。ＵＧは、例えば、第３世代ネットワークにおいて通信する機能などの広域接続およびＮＦＣ接続の機能を有する携帯電話である。ＵＧのＮＦＣ範囲については１０ｍを想定することができ、ＮＦＣによるオブジェクトキャッシュのキャッシュ交換頻度は１／６０［１／秒（１／ｓｅｃ）］に設定する。ＵＧのセンサ範囲は１０ｍであり、感知頻度は１／６０［１／秒（１／ｓｅｃ）］である。シミュレート領域は１ｋｍ２、すなわち１０００ｍ×１０００ｍに及ぶ。オブジェクト密度は８００オブジェクト／ｋｍ２に設定し、オブジェクトはシミュレーション内のデフォルトでは移動していない。ＵＧ密度は４００ノード／ｋｍ２であり、ＵＧ移動度モデルはランダムウォークである。
【００９０】
ランダムウォーク移動モデル（random walk mobility model）は、無作為に選択されるＵＧの移動方向を特徴とし、移動速度は１ｍ／秒である。移動期間は１００秒であり、移動後の待機期間はデフォルトで０秒である。ＵＧは自己の位置をＧＰＳ（Global Positioning System）により１０ｍの位置誤差で求めることができる。ＵＧ内のオブジェクトキャッシュサイズは２００レコードに設定し、ＵＧキャッシュサイズも２００レコードに設定する。特に言及しない場合、各シミュレーションシナリオにおいて１００個のクエリが発行され、各シナリオが数回シミュレートされる。
【００９１】
図９は、ＵＧ密度に対する平均クエリ成功時間のシミュレーション結果を示している。ＵＧ密度を５０〜８００まで変化させたときの平均クエリ成功時間の結果を示している。クエリ成功時間に関して各方法を比較すると、その順位は、平均クエリ成功時間が最短である「全対象に対する単純なクエリ」、「無作為な対象に対する単純なクエリ」、「リアクティブＤＩＳ」、平均クエリ成功時間が最長である「ＬＥＲ」の順である。しかし、「全対象に対する単純なクエリ」と「無作為な対象に対する単純なクエリ」は、高いネットワーク負荷をもたらす。本実施形態は、「無作為な対象に対する単純なクエリ」に近い成功時間を達成することができ、結果として生じるグローバルネットワーク負荷が極めて低いという利点を有する。
【００９２】
図１０は、ＵＧ密度に対するグローバルネットワーク使用量に関するシミュレーション結果を示している。グローバルネットワークのネットワーク負荷に関して各方法を比較すると、ＬＥＲのグローバルネットワーク負荷が最小であり、次いで、リアクティブＤＩＳの実施形態、「無作為な対象に対する単純なクエリ」、最後に「全対象に対する単純なクエリ」が続く。図１０は、単純な方法と比べたときに、本実施形態がグローバルネットワーク負荷の大部分を節約しつつ、「無作為な対象に対する単純なクエリ」に近い成功時間を達成することを示している。ＬＥＲはクエリが次のアンカに送られるときにグローバルネットワークを使用するだけであり、その成功時間はその他の方法の成功時間に比べてずっと劣る。
【００９３】
図１１は、ＵＧ密度に対するＮＦＣ使用量に関するシミュレーション結果を示している。１クエリ当たりのＮＦＣ使用量から生じるネットワーク負荷に関しては、本実施形態は、「全対象に対する単純なクエリ」または「無作為な対象に対する単純なクエリ」よりも多くのＮＦＣ通信を使用することがわかる。これは、本実施形態がグローバルネットワーク負荷を低減するためにＮＦＣを積極的に使用することによるものである。「全対象に対する単純なクエリ」および「無作為な対象に対する単純なクエリ」は、ＮＦＣを全く使用しない。本発明の方法のネットワーク負荷は、ＬＥＲの場合よりも小さい。というのは、この方法がアンカサーチクエリ回数を低減し、目標オブジェクトの周囲にあるアンカポイントのバウンシング（bouncing）を回避するからである。図１１では定期的なＮＦＣ使用量は考慮されていない。
【００９４】
図１２は、ＵＧ密度に対する定期的使用量も考慮に入れた、ＮＦＣ総使用量に関するシミュレーション結果を示している。平均システムクエリ頻度は、１時間当たりクエリ数１０００である。図１２に示した結果から、リアクティブＤＩＳの実施形態は、ＬＥＲと比べて半分のＮＦＣ負荷しか使用していないことがわかる。ＮＦＣコストは、グローバルネットワークコストより費用対効果が大きいものと考えることができる。この考えは、例えば、コストメトリックとして電力消費を用いることに基づくものなどとすることもできる。ＮＦＣの平均電力消費は、例えば、１０ｍＷ〜５０ｍＷまでなどであり、１Ｗ前後であるグローバルセルラネットワークにおける平均電力消費より桁違いに小さい。加えてＮＦＣはエンドユーザが自由に使用することができる。したがって各実施形態は、グローバルネットワーク負荷を低減し、短期間に成功を得るのに非常に有効であるという利点を提供する。
【００９５】
図１３は、オブジェクト密度に対する平均クエリ成功時間に関するシミュレーション結果を示している。図１３は、１００〜３２００までの様々なオブジェクト密度に対する平均成功時間を示している。リアクティブＤＩＳの実施形態のクエリ成功時間は、オブジェクト密度の増加と共に増加することが分かる。これは、ＵＧのオブジェクトキャッシュサイズの制限によるものである。他の実施形態では、さらなる改善のために、オブジェクトキャッシュサイズを変更し、監視するオブジェクト数に動的に適合させることもできる。
【００９６】
図１４は、ＵＧオブジェクトキャッシュサイズに対する平均クエリ成功時間のシミュレーション結果を示している。図１４は、ＵＧにおける２５〜８００までの様々なオブジェクトキャッシュサイズに対するクエリ成功時間を示している。この図によれば、オブジェクトキャッシュサイズは、ある一定のキャッシュサイズに到達した後は、クエリ成功時間にあまり影響を及ぼさない。このシナリオでは、８００オブジェクト／ｋｍ２のオブジェクト群に対して、例えば２００のキャッシュサイズで十分と考えられる。
【００９７】
さらに、移動するオブジェクトを考慮することにより平均クエリ成功時間を評価することができる。実行するシミュレーションでは、各オブジェクトがランダクウォークで移動する。すなわち、あらゆるＵＧが、無作為の角度（angle）、一定速度、一定の移動期間および移動後の待機期間がないということを決定する。以下のシミュレーションにおいて、速度を２１ｍ／秒に設定し、移動期間は１００秒に設定し、待機期間は０秒に設定する。
【００９８】
図１５は、オブジェクト移動比率（movable rate）に対する平均クエリ成功時間のシミュレーション結果を示している。０〜１００％までの移動オブジェクトの様々な比率についての結果が示されている。このような厳しい条件の下でも、本実施形態はＬＥＲよりずっと成功時間が短く、グローバルネットワーク使用量が少ない。
【００９９】
したがって本発明の各実施形態は、例えばＬＥＲのような従来のアルゴリズムよりも優れており、「無作為な対象に対する単純なクエリ」により近い成功時間であり、非常に小さいグローバルネットワーク負荷で済む。さらに、本明細書で説明したシミュレーションは、低いＵＧ密度、すなわち４００ＵＧ／ｋｍ２の下で実行したが、実世界シナリオは、例えばＣ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｉｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒにより示されているように、より高いＵＧ密度を有することも分かる。さらに、ランダムウォークはいずれにしても想定できる最悪の移動モデルである。実世界シナリオにおいては、ＵＧの一部は安定しているか、またはあまり頻繁に移動しないものもあり、移動経路は道路などにより制限される。したがって、実世界ではさらに良い結果を期待することができる。
【０１００】
図１６は、ＵＧ密度に対する電力消費のシミュレーション結果を示している。グローバルネットワークメッセージは８００ｍＷ／秒を消費し、ＮＦＣネットワークメッセージは６０ｍＷ／秒を消費するものとする。さらに、１時間当たり１０００個のクエリが発生するものとする。図１６は、リアクティブＤＩＳの実施形態の電力消費が、「全対象に対する単純なクエリ」または「無作為の対象に対する単純なクエリ」に比べてずっと低いことを示している。また、電力消費はＬＥＲの電力消費とほぼ同じであり、しかもより短いクエリ成功時間を有するという利点を有する。
【０１０１】
各実施形態は、通信網においてコスト的および時間的に有効性の大きいオブジェクトのクエリを可能にするという利点を提供することができる。さらに各実施形態は、クエリおよびネットワークの要件に適合させることができる。というのは、各実施形態が、通信網とのグローバル通信と、グローバルネットワークが関与しない、オブジェクトとの直接的またはＵＧ間の局所的すなわちＮＦＣ通信とを活用し、またはこれらの間のバランスをとることができるためである。言い換えると各実施形態は、リソース効率のよいオブジェクトクエリを実行するために、グローバルネットワークを相互に直接的に通信することもできる複数のＵＧの包括的（ｕｍｂｒｅｌｌａ）ネットワークとして使用することができるという利点を提供する。
【０１０２】
本発明の方法は、いくつかの実施上の要件に応じて、ハードウェアまたはソフトウェアとして実施することができる。本発明の実施は、本発明の方法が実行されるようにプログラマブルコンピュータシステムと協働する、電子的に読み取り可能な制御信号が保存されているディジタル記憶媒体、特にフラッシュメモリ、ディスク、ＣＤまたはＤＶＤを使って行うことができる。したがって本発明は一般に、機械可読媒体上にプログラムコードが保存されたコンピュータプログラム製品であり、コンピュータプログラム製品をコンピュータ上で実行すると、プログラムコードは、本発明の方法を実行する。したがって言い換えると本発明の方法は、コンピュータプログラムがコンピュータ上で実行されると、本発明の方法のうちの少なくとも１つを実行するプログラムコードを有するコンピュータプログラムである。
【図１ａ】
2009199592.tif 000003
【図１ｂ】
2009199592.tif 000004
【図２ａ】
2009199592.tif 000005
【図２ｂ】
2009199592.tif 000006
【図３ａ】
2009199592.tif 000007
【図３ｂ】
2009199592.tif 000008
【図４】
2009199592.tif 000009
【図５】
2009199592.tif 000010
【図６】
2009199592.tif 000011
【図７】
2009199592.tif 000012
【図８ａ】
2009199592.tif 000013
【図８ｂ】
2009199592.tif 000014
【図８ｃ】
2009199592.tif 000015
【図９】
2009199592.tif 000016
【図１０】
2009199592.tif 000017
【図１１】
2009199592.tif 000018
【図１２】
2009199592.tif 000019
【図１３】
2009199592.tif 000020
【図１４】
2009199592.tif 000021
【図１５】
2009199592.tif 000022
【図１６】
2009199592.tif 000023
【図１７】
2009199592.tif 000024
【図１８】
2009199592.tif 000025
【図１９】
2009199592.tif 000026
【外国語明細書】
2009199592.tif 000027
2009199592.tif 000028
2009199592.tif 000029
2009199592.tif 000030
2009199592.tif 000031
2009199592.tif 000032
2009199592.tif 000033
2009199592.tif 000034
2009199592.tif 000035
2009199592.tif 000036
2009199592.tif 000037
2009199592.tif 000038
2009199592.tif 000039
2009199592.tif 000040
2009199592.tif 000041
2009199592.tif 000042
2009199592.tif 000043
2009199592.tif 000044
2009199592.tif 000045
2009199592.tif 000046
2009199592.tif 000047
2009199592.tif 000048
2009199592.tif 000049
2009199592.tif 000050
2009199592.tif 000051
2009199592.tif 000052
2009199592.tif 000053
2009199592.tif 000054
2009199592.tif 000055
2009199592.tif 000056
2009199592.tif 000057
2009199592.tif 000058
2009199592.tif 000059
2009199592.tif 000060
2009199592.tif 000061
2009199592.tif 000062
2009199592.tif 000063
2009199592.tif 000064
2009199592.tif 000065
2009199592.tif 000066
2009199592.tif 000067
2009199592.tif 000068
2009199592.tif 000069
2009199592.tif 000070
2009199592.tif 000071
2009199592.tif 000072
2009199592.tif 000073
2009199592.tif 000074
2009199592.tif 000075
2009199592.tif 000076
2009199592.tif 000077
2009199592.tif 000078
2009199592.tif 000079
2009199592.tif 000080
2009199592.tif 000081
2009199592.tif 000082
2009199592.tif 000083
2009199592.tif 000084
2009199592.tif 000085
2009199592.tif 000086
2009199592.tif 000087
2009199592.tif 000088
2009199592.tif 000089
2009199592.tif 000090
2009199592.tif 000091
2009199592.tif 000092
2009199592.tif 000093
2009199592.tif 000094
2009199592.tif 000095
2009199592.tif 000096
2009199592.tif 000097
2009199592.tif 000098
2009199592.tif 000099
2009199592.tif 000100
2009199592.tif 000101
2009199592.tif 000102
2009199592.tif 000103
2009199592.tif 000104
2009199592.tif 000105
2009199592.tif 000106