(57)【特許請求の範囲】
【請求項１】
モバイル通信ネットワークで通信するためのユビキタス・ゲートウェイ（１００）であって、ここで、前記モバイル通信ネットワークが複数のユビキタス・ゲートウェイを備えるものであり、
前記モバイル通信ネットワークと通信する第１の通信手段であって、前記第１の通信手段が、セルラーモバイル通信ネットワークにおいて通信するように構成されるものである、第１の通信手段（１１０）と、
他のユビキタス・ゲートウェイと通信し且つあるオブジェクトと通信する第２の通信手段であって、前記オブジェクトが、グローバル・ネットワークに接続されておらず、前記オブジェクトが、オブジェクト識別情報を有し、前記第２の通信手段が、他のユビキタス・ゲートウェイまたは他のオブジェクトの１つから受信されたオブジェクト・レコードを検出するように構成されるものである、第２の通信手段（１２０）と、
１つ以上のオブジェクト・レコードを一時的に記憶するオブジェクト・キャッシュ（１３０）であって、前記オブジェクト・レコードが、オブジェクト・レコード識別情報と、オブジェクト識別情報と、オブジェクト・ロケーション情報とを含むものである、オブジェクト・キャッシュ（１３０）と、
前記第２の通信手段（１２０）を介して前記オブジェクトを繰り返し監視するコントローラ（１４０）であって、前記コントローラ（１４０）が、前記オブジェクトのオブジェクト・レコードを前記オブジェクト・キャッシュ（１３０）に記憶するように構成されるものである、コントローラ（１４０）と
ユビキタス・ゲートウェイ・レコード識別情報と、ユビキタス・ゲートウェイ識別情報と、ユビキタス・ゲートウェイ・ロケーション情報とを備えるユビキタス・ゲートウェイ・レコードを一時的に記憶するユビキタス・ゲートウェイ・キャッシュ（１５０）と
を備え、
前記コントローラ（１４０）が、前記他のユビキタス・ゲートウェイのうちの１つ以上のユビキタス・ゲートウェイから１つ以上のオブジェクト・レコードを、近距離無線通信を用いて繰り返し受信し、前記オブジェクト・キャッシュ（１３０）からの１つ以上のオブジェクト・レコードを前記他のユビキタス・ゲートウェイのうちの１つ以上のユビキタス・ゲートウェイに近距離無線通信を用いて繰り返し送信して、物理的に近くにあるユビキタス・ゲートウェイの間でキャッシュ済みの情報をプロアクティブに共有するように構成されるものであり、
前記コントローラ（１４０）が、クエリの対象となるオブジェクトに関するオブジェクト・クエリをクエリ元から受信するように構成されるものであり、
前記コントローラ（１４０）が、前記クエリの対象となるオブジェクトに関するオブジェクト・レコードを前記オブジェクト・キャッシュ（１３０）から前記クエリ元に報告するように構成されるものであり、
前記コントローラ（１４０）が、前記第２の通信手段（１２０）を介して前記他のユビキタス・ゲートウェイのうちの１つ以上のユビキタス・ゲートウェイを繰り返し監視し、ユビキタス・ゲートウェイ・レコードを前記ユビキタス・ゲートウェイ・キャッシュ（１５０）に記憶し、前記ユビキタス・ゲートウェイ・キャッシュ（１５０）からの１つ以上のユビキタス・ゲートウェイ・レコードを前記第２の通信手段（１２０）を介して前記他のユビキタス・ゲートウェイのうちの１つ以上のユビキタス・ゲートウェイと繰り返し交換し、前記ユビキタス・ゲートウェイ・キャッシュ（１５０）からの前記ユビキタス・ゲートウェイ・レコードのうちの１つに基づいて前記オブジェクト・クエリを前記他のユビキタス・ゲートウェイのうちの１つに転送するように構成されるものであり、
前記コントローラ（１４０）がさらに、前記クエリの対象となるオブジェクトの検索クエリを受信およびインストールするように構成されるものであり、
前記ユビキタス・ゲートウェイは、前記受信およびインストールされた検索クエリへの応答として、前記クエリの対象となるオブジェクトがファウンド・オブジェクト変数に基づいて見つけられるかどうかをチェック（３６６）するものであり、前記ファウンド・オブジェクト変数は、発見されたオブジェクトのアレイとして使用されるものであり、
前記クエリの対象となるオブジェクトが、前記発見されたオブジェクトのアレイで使用される前記ファウンド・オブジェクト変数に基づいて見つけられない場合、前記コントローラ（１４０）は、隣接するユビキタス・ゲートウェイに知らせるために、前記第２の通信手段（１２０）を介して前記検索クエリをブロードキャスト（３８０）し、
前記ユビキタス・ゲートウェイは、隣接するユビキタス・ゲートウェイへの前記検索クエリのブロードキャスト（３８０）に続いて、前記クエリの対象となるオブジェクト（ＯＤ）についての新しいオブジェクト・レコードが前記オブジェクト・キャッシュの中にあるかどうかをチェック（３８２）し、前記クエリの対象となるオブジェクト（ＯＤ）のより新しいロケーションを知っているユビキタス・ゲートウェイを追跡するものであり、
前記ユビキタス・ゲートウェイが、前記新しいオブジェクト・レコードから、推定されたオブジェクト・ロケーション情報を得て（３８４）、前記ユビキタス・ゲートウェイ・レコードから、前記オブジェクト・ロケーション情報の位置またはその近くにあるユビキタス・ゲートウェイ（ＵＧＮＥＸＴ）を得る（３８６）ものであり、
前記検索されたオブジェクトについての新しいオブジェクト・レコードが前記オブジェクト・キャッシュにある場合、前記ユビキタス・ゲートウェイは、前記オブジェクト・ロケーション情報の位置またはその近くにあり且つクエリが送信されていないユビキタス・ゲートウェイ（ＵＧＮＥＸＴ）に、新しいクエリを送信（３９０）するものであり、
前記オブジェクト・キャッシュの中に、新しい関連するレコードがないことが分かった場合（３８２）、前記コントローラは、あるユビキタス・ゲートウェイをランダムに選択し、前記ランダムに選択されたユビキタス・ゲートウェイにクエリを転送（３９４）するものであり、
前記ユビキタス・ゲートウェイが、前記他のユビキタス・ゲートウェイ（ＵＧＮＥＸＴ）の１つに前記検索クエリを送信した後においても、前記検索クエリの実行を継続するものであり、
前記ユビキタス・ゲートウェイが、前記共有された情報を用いて、前記クエリ対象となるオブジェクトのトレースを判断し、前記クエリ対象となるオブジェクトが見つかるまで前記クエリ対象となるオブジェクトの近くをルーティングするものである、
ユビキタス・ゲートウェイ。
【請求項２】
前記オブジェクト・レコードが、前記オブジェクトが最後に見られた時間のタイムスタンプと、前記オブジェクトを監視したユビキタス・ゲートウェイのユビキタス・ゲートウェイ識別情報と、前記オブジェクトが前記ユビキタス・ゲートウェイによって継続的に監視された期間と、前記オブジェクトが最後に見られたと推定される位置と、前記オブジェクトが移動可能であるか否かの情報と、前記オブジェクト・レコードを交換したユビキタス・ゲートウェイの履歴と、前記オブジェクト・レコードが伝搬したホップ数とのうちの１つまたはこれらの組み合わせを更に含むものである、請求項１に記載のユビキタス・ゲートウェイ。
【請求項３】
前記ユビキタス・ゲートウェイ・レコードが、前記他のユビキタス・ゲートウェイが最後に監視された時間のタイムスタンプと、前記他のユビキタス・ゲートウェイの最後に見られたと推定される位置と、前記他のユビキタス・ゲートウェイの平均速度と、前記ユビキタス・ゲートウェイ速度の標準偏差と、前記ユビキタス・ゲートウェイ・レコードを転送した更なるユビキタス・ゲートウェイの履歴と、前記ユビキタス・ゲートウェイ・レコードが伝搬したホップ数とのうちの１つまたはこれらの組み合わせを更に含むものである、請求項１または２に記載のユビキタス・ゲートウェイ。
【請求項４】
前記コントローラ（１４０）が、別のオブジェクト・レコードまたはユビキタス・ゲートウェイ・レコードが前記他のユビキタス・ゲートウェイから受信された場合に、前記オブジェクト・キャッシュ（１３０）におけるオブジェクト・レコード、または前記ユビキタス・ゲートウェイ・キャッシュ（１５０）におけるユビキタス・ゲートウェイ・レコードを更新するように構成されるものである、請求項１ないし３のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項５】
前記コントローラ（１４０）が、より新しいオブジェクト・レコードが使用可能な場合に古いオブジェクト・レコードを破棄するように構成されるものである、請求項１ないし４のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項６】
前記コントローラ（１４０）が、より新しいユビキタス・ゲートウェイ・レコードが使用可能な場合に古いユビキタス・ゲートウェイ・レコードを破棄するように構成されるものである、請求項１ないし５のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項７】
前記コントローラ（１４０）が、近傍の更なるオブジェクトを周期的に監視し、新しいオブジェクト・レコードが使用可能になる場合には前記オブジェクト・キャッシュ（１３０）における更なるオブジェクト・レコードを更新するように構成されるものである、請求項１ないし６のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項８】
オブジェクトを監視する周期が１０秒〜５分である、請求項７に記載のユビキタス・ゲートウェイ。
【請求項９】
前記コントローラ（１４０）が、近傍の更なるユビキタス・ゲートウェイを周期的に監視し、より新しいユビキタス・ゲートウェイ・レコードが使用可能になる場合には前記ユビキタス・ゲートウェイ・キャッシュ（１５０）における更なるユビキタス・ゲートウェイ・レコードを更新するように構成されるものである、請求項１ないし８のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項１０】
前記コントローラ（１４０）が、前記更新されたオブジェクト・レコードまたは前記更新されたユビキタス・ゲートウェイ・レコードを近傍の更なるユビキタス・ゲートウェイと周期的に交換するように構成されるものである、請求項４、７、８、または９のいずれかに記載のユビキタス・ゲートウェイ。
【請求項１１】
前記近傍のユビキタス・ゲートウェイについては、前記第２の通信手段（１２０）のカバレージによって決定される、請求項６ないし１０のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項１２】
前記コントローラ（１４０）が、前記オブジェクト・クエリの有効期間を考慮し、その有効期間が過ぎた場合に前記オブジェクト・クエリを破棄するように構成されるものである、請求項１ないし１１のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項１３】
前記コントローラ（１４０）が、前記オブジェクト・クエリの有効期間を考慮し、その有効期間が過ぎた場合に前記オブジェクト・クエリを破棄するように構成されるものであり、
前記コントローラ（１４０）が、前記有効期間が過ぎる前のオブジェクト・クエリを、前記オブジェクトに関する前記更新されたオブジェクト・レコードによって前記クエリ元に応答するように構成されるものである、請求項４、９、１０のいずれかに記載のユビキタス・ゲートウェイ。
【請求項１４】
前記コントローラ（１４０）が、オブジェクト・クエリの転送先である更なるユビキタス・ゲートウェイのユビキタス・ゲートウェイ識別情報を記憶し、前記クエリの対象となるオブジェクトが発見されるか、又は前記オブジェクト・クエリがキャンセルされたりする場合に、前記オブジェクト・クエリが転送された全ての更なるユビキタス・ゲートウェイに前記オブジェクト・クエリのキャンセルを要求するように構成されるものである、請求項１ないし１３のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項１５】
前記コントローラ（１４０）が、前記オブジェクト・クエリが転送可能な回数に関する制限を設定するように構成されるものである、請求項１ないし１４のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項１６】
ユビキタス・ゲートウェイ自身の位置を判断する手段をさらに備えるものである請求項１ないし１５のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項１７】
前記ユビキタス・ゲートウェイ自身の位置を判断する手段が、ＧＰＳ（グローバルポジショニングシステム）受信機を備えるものである、請求項１６に記載のユビキタス・ゲートウェイ。
【請求項１８】
オブジェクト・レコードおよびユビキタス・ゲートウェイ・レコードによって準備されたブルームフィルタをさらに備えるものである請求項１ないし１７のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項１９】
前記第１の通信手段（１１０）が、セルラーモバイル通信ネットワークで通信するように構成されるものである、請求項１ないし１８の一項に記載のユビキタス・ゲートウェイ。
【請求項２０】
前記第１の通信手段（１１０）が、ＧＳＭ（モバイル通信用のグローバルシステム）（登録商標）と、ＵＭＴＳ（ユニバーサル・モバイル・テレコミュニケーション・システム）と、ＬＴＥ（ロング・ターム・エボリューション）（登録商標）と、ＦＯＭＡ（モバイル・マルチメディア・アクセスの自由）（登録商標）とのうちの１つまたはこれらの組み合わせにしたがって通信するように構成されるものである、請求項１ないし１９のいずれかに記載のユビキタス・ゲートウェイ。
【請求項２１】
前記第２の通信手段（１２０）が、ＤＥＣＴ（ディジタル・コードレス電話）と、Ｂｌｕｅｔｏｏｔｈ（登録商標）と、ＲＦＩＤ（無線周波数識別）と、ＩＳＭ（産業、科学および医療用無線周波数）と、ＷＬＡＮ（無線ローカル・エリア・ネットワーク）とのうちの１つまたはこれらの組み合わせにしたがって通信するように構成されるものである、請求項１ないし２０のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項２２】
前記モバイル通信ネットワークと通信する前記第１の通信手段（１１０）が、通信プロトコルを使用して通信するように構成されるものであり、前記通信プロトコルは、前記オブジェクトが前記通信プロトコルを使用して通信ができないようなものである、請求項１ないし２１のいずれか一項に記載のユビキタス・ゲートウェイ。
【請求項２３】
あるモバイル通信ネットワークにおいてユビキタス・ゲートウェイが通信するための方法であって、ここで、前記モバイル通信ネットワークが、複数のユビキタス・ゲートウェイを備えるものであり、
セルラーモバイル通信ネットワークで通信するための手段を用いて、前記モバイル通信ネットワークと通信するステップと、
近距離無線通信を用いて、１つ以上の他のユビキタス・ゲートウェイと通信するステップと、
オブジェクト識別情報を有するオブジェクトと通信するステップであって、前記オブジェクトがグローバル・ネットワークに接続されていない、ステップと、
前記他のユビキタス・ゲートウェイの１つまたは前記オブジェクトから受信したオブジェクト・レコードを検出するステップと、
オブジェクト・レコード識別情報と、オブジェクト識別情報と、オブジェクト・ロケーション情報とを備える１つ以上のオブジェクト・レコードを一時的に記憶するステップと、
１つ以上のオブジェクトを繰り返し監視するステップと、
前記１つ以上の監視されたオブジェクトの１つ以上のオブジェクト・レコードを記憶するステップと、
近距離無線通信を用いて、前記他のユビキタス・ゲートウェイのうちの１つ以上のユビキタス・ゲートウェイから１つ以上のオブジェクト・レコードを繰り返し受信するステップと、
近距離無線通信を用いて、前記他のユビキタス・ゲートウェイのうちの１つ以上のユビキタス・ゲートウェイに１つ以上のオブジェクト・レコードを繰り返し送信して、物理的に近くにあるユビキタス・ゲートウェイの間でキャッシュ済みの情報をプロアクティブに共有するステップと、
前記他のユビキタス・ゲートウェイのうちの１つ以上のユビキタス・ゲートウェイを繰り返し監視し、ユビキタス・ゲートウェイ・レコードを記憶するステップであって、前記ユビキタス・ゲートウェイ・レコードが、ユビキタス・ゲートウェイ・レコード識別情報と、ユビキタス・ゲートウェイ識別情報と、ユビキタス・ゲートウェイ・ロケーション情報とを備えるものである、ステップと、
１つ以上のユビキタス・ゲートウェイ・レコードを前記他のユビキタス・ゲートウェイのうちの１つ以上のユビキタス・ゲートウェイと繰り返し交換するステップと、
クエリの対象となるオブジェクトに関するオブジェクト・クエリをクエリ元から受信し、前記クエリの対象となるオブジェクトの検索クエリをインストールするステップと、
前記クエリの対象となるオブジェクトに関するオブジェクト・レコードを前記クエリ元に報告するステップと
を含み、
前記ユビキタス・ゲートウェイは、前記受信およびインストールされた検索クエリへの応答として、前記クエリの対象となるオブジェクトがファウンド・オブジェクト変数に基づいて見つけられるかどうかをチェック（３６６）し、ここで、前記ファウンド・オブジェクト変数は、発見されたオブジェクトのアレイとして使用されるものであり、
前記クエリの対象となるオブジェクトが、前記発見されたオブジェクトのアレイで使用される前記ファウンド・オブジェクト変数に基づいて見つけられない場合、前記ユビキタス・ゲートウェイが、隣接するユビキタス・ゲートウェイに前記検索クエリをブロードキャストし、
隣接するユビキタス・ゲートウェイへの前記検索クエリのブロードキャストに続いて、前記クエリの対象となるオブジェクト（ＯＤ）についての新しいオブジェクト・レコードがオブジェクト・キャッシュの中にあるかどうかを前記ユビキタス・ゲートウェイがチェック（３８２）し、前記クエリの対象となるオブジェクト（ＯＤ）のより新しいロケーションを知っているユビキタス・ゲートウェイを追跡し、
前記ユビキタス・ゲートウェイが、前記新しいオブジェクト・レコードから、推定されたオブジェクト・ロケーション情報を得て（３８４）、前記ユビキタス・ゲートウェイ・レコードから、前記オブジェクト・ロケーション情報の位置またはその近くにあるユビキタス・ゲートウェイ（ＵＧＮＥＸＴ）を得て（３８６）、
前記検索されたオブジェクトについての新しいオブジェクト・レコードが前記オブジェクト・キャッシュにある場合、前記ユビキタス・ゲートウェイは、前記オブジェクト・ロケーション情報の位置またはその近くにあり且つクエリが送信されていないユビキタス・ゲートウェイ（ＵＧＮＥＸＴ）に、新しいクエリを送信し（３９０）、
前記オブジェクト・キャッシュの中に、新しい関連するレコードがないことが分かった場合（３８２）、前記ユビキタス・ゲートウェイは、前記他のユビキタス・ゲートウェイの１つをランダムに選択し、前記ランダムに選択されたユビキタス・ゲートウェイにクエリを転送（３９４）し、
前記ユビキタス・ゲートウェイは、前記他のユビキタス・ゲートウェイ（ＵＧＮＥＸＴ）の１つに前記検索クエリを送信した後においても、前記検索クエリの実行を継続し、
前記ユビキタス・ゲートウェイが、前記共有された情報を用いて、前記クエリ対象となるオブジェクトのトレースを判断し、前記クエリ対象となるオブジェクトが見つかるまで前記クエリ対象となるオブジェクトの近くをルーティングする、方法。
【請求項２４】
プロセッサ上で実行される際に請求項２３に記載の方法を実行するようなプログラムコードを有するコンピュータプログラム。
【請求項２５】
複数のユビキタス・ゲートウェイ（７１２，７１４，７１６，７１８）を備えるモバイル通信ネットワークにおいて動作するグローバル・クエリ・マネージャ（１６０，７１０）であって、ここで、前記ユビキタス・ゲートウェイは、移動可能であり、前記ユビキタス・ゲートウェイは、モバイル通信ネットワークで通信し、且つオブジェクト・レコードを記憶するように構成されるものであり、
前記複数のユビキタス・ゲートウェイ（７１２，７１４，７１６，７１８）と通信し、前記複数のユビキタス・ゲートウェイのうちの１つから受信されたオブジェクト・レコードを検出するように構成されるものである通信手段（１７０）と、
前記複数のユビキタス・ゲートウェイのうちの１つによって報告された前記オブジェクト・レコードを一時的に記憶するためのオブジェクト・キャッシュ（１８０）であって、前記オブジェクト・レコードが、オブジェクト・レコード識別情報と、オブジェクト識別情報と、オブジェクト・ロケーション情報とを備えるものである、オブジェクト・キャッシュ（１８０）と、
クエリの対象となるオブジェクトについてのレコード・リクエストをクエリ元から受信し、前記レコード・リクエストを前記複数のユビキタス・ゲートウェイのうちの１つに転送するコントローラ（１９０）と
を備え、
前記コントローラ（１９０）が、前記オブジェクト・キャッシュの中の前記オブジェクト・レコードにアクセス（５５０）し、前記複数のユビキタス・ゲートウェイから、前記レコード・リクエストが転送された前記ユビキタス・ゲートウェイ（７１２）を選択するものであり、
前記グローバル・クエリ・マネージャが、前記オブジェクト・キャッシュの中に前記クエリの対象となるオブジェクトについてのレコードがあるかどうかをチェック（５５０，５５２）するものであり、
前記グローバル・クエリ・マネージャは、前記オブジェクト・キャッシュの中に前記クエリの対象となるオブジェクトについてのレコードがない場合、繰り返しかつランダムにユビキタス・ゲートウェイを選択して（５５６）、前記ランダムに選択されたユビキタス・ゲートウェイにおいて関連するレコードがあるかどうかをチェック（５５８）するものであり、
前記グローバル・クエリ・マネージャが、前記クエリの対象となるオブジェクトについてのレコードを見つけた（５５０，５５２）場合、前記グローバル・クエリ・マネージャが、前記クエリの対象となるオブジェクト（ＯＤ）についてのレコードに関して最後のレコードよりも新しいレコードを反復して追跡する（５４４）ものであり、
前記グローバル・クエリ・マネージャは、前記クエリの対象となるオブジェクトについての新しいレコードを追跡し且つ利用可能な最も新しい位置を再帰的に見つけるために、ヒットしたレコードによって示されたターゲット・ロケーションにおいて前記複数のユビキタス・ゲートウェイのうちの１つを選択（５７０）し、前記クエリの対象となるオブジェクトについてのレコードを得ようと試みて（５７６）、前記選択された１つのユビキタス・ゲートウェイが前記クエリの対象となるオブジェクトについてのより新しいレコードを有するかどうかをチェック（５７８）するものであり、
前記クエリの対象となるオブジェクトについてのより新しいレコードがそれ以上見つからないとき、前記コントローラが、ターゲット・ロケーションにおいて前記複数のユビキタス・ゲートウェイのうちの１つにおける前記クエリの対象となるオブジェクトの検索クエリをインストールして（５４６，５９２）、前記検索クエリがインストールされたユビキタス・ゲートウェイが、近距離無線通信を使用して前記検索クエリを別のユビキタス・ゲートウェイに転送できるようにし、
前記グローバル・クエリ・マネージャは、前記検索クエリがインストールされた１つのユビキタス・ゲートウェイから受信した、前記クエリの対象となるオブジェクトについての新しいレコードを前記グローバル・クエリ・マネージャの前記オブジェクト・キャッシュに追加し、前記より新しいレコードの追跡処理と前記検索クエリの前記インストール処理を再実行するものである、
グローバル・クエリ・マネージャ。
【請求項２６】
前記コントローラ（１９０）が、前記オブジェクト・レコードを報告した前記ユビキタス・ゲートウェイのユビキタス・ゲートウェイ識別情報をさらに記憶するように構成されるものである、請求項２５に記載のグローバル・クエリ・マネージャ。
【請求項２７】
前記コントローラ（１９０）が、前記オブジェクトに関する前記オブジェクト・レコードを報告した前記ユビキタス・ゲートウェイに基づいて、前記レコード・リクエストが転送された前記ユビキタス・ゲートウェイを選択するように構成されるものである、請求項２６に記載のグローバル・クエリ・マネージャ。
【請求項２８】
前記コントローラ（１９０）が、前記オブジェクト・キャッシュ（１８０）に記憶されている前記オブジェクト・ロケーション情報と、前記レコード・リクエストが転送された前記ユビキタス・ゲートウェイのロケーション情報とに基づいて、前記レコード・リクエストが転送された前記ユビキタス・ゲートウェイを選択するように構成されるものである、請求項２５ないし２７のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項２９】
前記オブジェクト・レコードが、オブジェクトが最後に見られた時間のタイムスタンプと、前記オブジェクトを監視したユビキタス・ゲートウェイのユビキタス・ゲートウェイ識別情報と、前記オブジェクトがユビキタス・ゲートウェイによって継続的に監視された期間と、前記オブジェクトが最後に見られたと推定される位置と、前記オブジェクトが移動可能であるか否かの情報と、前記オブジェクト・レコードを交換したユビキタス・ゲートウェイの履歴と、前記オブジェクト・レコードが伝搬したホップ数とのうちの１つまたはこれらの組み合わせをさらに備えるものである、請求項２５ないし２８のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３０】
前記コントローラ（１９０）が、前記オブジェクトに関する検索クエリを前記複数のユビキタス・ゲートウェイの１つにインストールするものであり、
前記検索クエリがインストールされた前記ユビキタス・ゲートウェイが、近距離無線通信を使用して、前記検索クエリを別のユビキタス・ゲートウェイに転送するものであり、
前記コントローラが、前記オブジェクトにプロアクティブにクエリを実行するように構成されるものである、請求項２５ないし２９のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３１】
前記コントローラ（１９０）が、前記検索クエリがインストールされた前記ユビキタス・ゲートウェイから別のユビキタス・ゲートウェイへの検索クエリの転送に基づいて、前記オブジェクト・レコードを受信するように構成されるものであり、前記別のユビキタス・ゲートウェイもまた、前記検索クエリを転送するものである、請求項３０に記載のグローバル・クエリ・マネージャ。
【請求項３２】
前記コントローラ（１９０）が、有効期間と前記レコード・リクエストを関連付けており、前記レコード・リクエストの前記有効期間が過ぎた場合に前記クエリ元に通知するように構成されるものであり、請求項２５ないし３１のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３３】
前記コントローラ（１９０）が、前記オブジェクト・キャッシュ（１８０）からの前記オブジェクト・レコードよりも新しい、前記クエリの対象となるオブジェクトに関するオブジェクト・レコードを有する可能性の高いユビキタス・ゲートウェイに前記レコード・リクエストを転送するように構成されるものである、請求項２５ないし３２のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３４】
前記コントローラ（１９０）が、前記オブジェクト・ロケーション情報の近傍に配置されているユビキタス・ゲートウェイに前記レコード・リクエストを転送するように構成されるものであり、前記近傍のユビキタス・ゲートウェイについては、前記モバイル通信ネットワークによって、または前記オブジェクト・キャッシュ（１８０）から決定される、請求項２５ないし３３のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３５】
前記コントローラ（１９０）が、前記レコード・リクエストを所定数のユビキタス・ゲートウェイに転送するように構成されるものである、請求項２５ないし３４のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３６】
前記コントローラ（１９０）が、前記検索クエリを所定数のユビキタス・ゲートウェイにインストールするように構成されるものである、請求項３０ないし３５のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３７】
前記コントローラ（１９０）が、最新の検索オブジェクトのロケーション情報を前記クエリ元に提供するように構成されるものである、請求項２５ないし３６のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３８】
前記コントローラ（１９０）が、前記複数のユビキタス・ゲートウェイのうちの１つまたは前記モバイル通信ネットワークのネットワーク・ノードから前記レコード・リクエストを受信するように構成されるものである、請求項２５ないし３７のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項３９】
前記通信手段（１７０）が、ある通信プロトコルを使用して通信するように構成されるものであり、前記通信プロトコルは、前記オブジェクトが前記通信プロトコルを使用して通信できないようなものである、請求項２５ないし３８のいずれか一項に記載のグローバル・クエリ・マネージャ。
【請求項４０】
複数のユビキタス・ゲートウェイを備えるモバイル通信ネットワークにおいて動作するグローバル・クエリ・マネージャが実行する方法であって、前記複数のユビキタス・ゲートウェイの少なくとも１つが、移動可能であり、前記モバイル通信ネットワークで通信し且つ１つ以上のオブジェクト・レコードを記憶するように構成されるものであり、
前記複数のユビキタス・ゲートウェイと通信するステップと、
前記複数のユビキタス・ゲートウェイの１つから受信した１つ以上のオブジェクト・レコードを検出するステップと、
前記複数のユビキタス・ゲートウェイの１つによって報告された前記１つ以上のオブジェクト・レコードをオブジェクト・キャッシュに一時的に記憶するステップであって、前記１つ以上のオブジェクト・レコードの中のあるオブジェクト・レコードが、オブジェクト・レコード識別情報と、オブジェクト識別情報と、オブジェクト・ロケーション情報とを備えるものである、ステップと、
クエリの対象となるオブジェクトについてのレコード・リクエストをクエリ元から受信するステップと、
前記オブジェクト・キャッシュの中の前記オブジェクト・レコードにアクセスするステップと、
前記レコード・リクエストが転送されたユビキタス・ゲートウェイを、前記複数のユビキタス・ゲートウェイから選択するステップと
を含み、
前記グローバル・クエリ・マネージャは、前記オブジェクト・キャッシュの中に前記クエリの対象となるオブジェクトについてのレコードがない場合、繰り返しかつランダムにユビキタス・ゲートウェイを選択して（５５６）、前記ランダムに選択されたユビキタス・ゲートウェイにおいて関連するレコードがあるかどうかをチェック（５５８）し、
前記グローバル・クエリ・マネージャが、前記クエリの対象となるオブジェクトについてのレコードを見つけた（５５０，５５２）場合、前記グローバル・クエリ・マネージャが、前記クエリの対象となるオブジェクト（ＯＤ）についてのレコードに関して最後のレコードよりも新しいレコードを反復して追跡し（５４４）、
前記グローバル・クエリ・マネージャは、前記クエリの対象となるオブジェクトについての新しいレコードを追跡し且つ利用可能な最も新しい位置を再帰的に見つけるために、ヒットしたレコードによって示されたターゲット・ロケーションにおいて前記複数のユビキタス・ゲートウェイのうちの１つを選択（５７０）し、前記クエリの対象となるオブジェクト（ＯＤ）についてのレコードを得ようと試みて（５７６）、前記選択された１つのユビキタス・ゲートウェイが前記クエリの対象となるオブジェクトについてのより新しいレコードを有するかどうかをチェック（５７８）し、
前記クエリの対象となるオブジェクトについてのより新しいレコードがそれ以上見つからないとき、前記グローバル・クエリ・マネージャが、ターゲット・ロケーションにおいて前記複数のユビキタス・ゲートウェイのうちの１つにおける前記クエリの対象となるオブジェクトの検索クエリをインストールして（５４６，５９２）、前記検索クエリがインストールされたユビキタス・ゲートウェイが、近距離無線通信を使用して前記検索クエリを別のユビキタス・ゲートウェイに転送できるようにし、
前記グローバル・クエリ・マネージャは、前記検索クエリがインストールされた１つのユビキタス・ゲートウェイから受信した、前記クエリの対象となるオブジェクトについての新しいレコードを前記グローバル・クエリ・マネージャの前記オブジェクト・キャッシュに追加し、前記より新しいレコードの追跡処理と前記検索クエリの前記インストール処理を再実行する、
方法。
【請求項４１】
プロセッサで実行される際に請求項４０に記載の方法を実行するプログラムを有するコンピュータプログラム。
【請求項４２】
請求項１ないし２２のいずれか一項に記載のユビキタス・ゲートウェイ（１００）と、
請求項２５ないし３９のいずれか一項に記載のグローバル・クエリ・マネージャ（１６０）とを備えているシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークにおけるオブジェクトの発見または追跡の分野に関する。これは、本分野が、電子識別の受け入れの広がりに伴ってますます問題となっているためである。
【背景技術】
【０００２】
従来より、実世界のオブジェクトの追跡や検索は困難であるが、これは、これらのオブジェクトが、インターネットや電気通信ネットワークなどのグローバル・ネットワークに接続されていないからである。例えば、ＲＦＩＤ（無線周波数識別）を使用してオブジェクトにタグ付けするという現在のオブジェクト追跡またはオブジェクト検索手法は、スーパーマーケット、ＣＤ（コンパクトディスク）ストアまたは他の流通管理ドメインなどの特定の限定された場においてうまく機能するにすぎない。しかしながら、例えば、ある特定のクラスのオブジェクトに制約されないような、都市単位のより大きなエリアでの追跡または検索手法は存在しない。
【０００３】
最近、以下ユビキタス・ゲートウェイ（ＵＧ）とも呼ぶことができる、近距離無線通信（ＮＦＣ）を備えた携帯電話が広く使用されるようになってきた。携帯電話は、既に世界的インフラストラクチャ、つまりセルラーネットワークになっているため、広範なエリアに専用センサを展開することなく、タグ付けされたオブジェクトを検索または追跡するために使用することができる。
【０００４】
図１７は、従来のシナリオを図示し、グローバル・ネットワーク１７１０、例えばモバイル通信ネットワークが左側に示されている。グローバル・ネットワーク１７１０は、サービス・インフラストラクチャ１７２０を提供し、例えば基地局１７３０を利用し、無線通信を使用してモバイル・デバイス１７４０と通信する。この無線通信は、例えばＧＳＭ（モバイル通信用グローバルシステム）（登録商標）、ＵＭＴＳ（ユニバーサル・モバイル・テレコミュニケーションシステム）、ＬＴＥ（ロングターム・エボリューション）（登録商標）などの第３または第４世代のモバイル通信システムに基づいて実行されてもよい。
【０００５】
モバイル・デバイス１７４０は、例えば、ＷＬＡＮ（無線ローカルエリアネットワーク）、Ｂｌｕｅｔｏｏｔｈ、ＲＦＩＤ（無線周波数識別）、ＩＳＭ（産業、科学および医療用無線周波数）、他のタイプのＮＦＣ（近距離無線通信）などの無線通信基準を使用して複数の追加インタフェースを操作することができるため、モバイル・デバイス１７４０は、ユビキタス・ゲートウェイとみなすことができる。
【０００６】
図１７に示されているように、モバイル・デバイス１７４０は、上記通信技術を使用して、例えばローカル・ネットワーク、ＲＦＩＤタグ付きバッグであるタグ付きオブジェクト、電子機器などの間で実世界オブジェクト１７５０と通信することができる。実世界オブジェクトの領域は、何ら制限されることもなく、例えばＲＦＩＤタグは、例えば図１７の右側のスケッチで示されているように人々に対していずれかのオブジェクトとともに使用することができるため、生徒でさえもタグ付けすることができる。モバイル・デバイスはさらに、身体的寸法を監視するセンサ、パーソナルエリアネットワーク（ＰＡＮ）のための手段、タグ付きオブジェクト／人物を監視する手段、Ｂｌｕｅｔｏｏｔｈビーコンなどを備えることができる。さらに、グローバル・ネットワーク１７１０は、例えばＩＰベースのセルラーネットワーク（ＩＰ＝インターネット・プロトコル）、ワールドワイドウェブ、インターネットなどであるグローバル情報ネットワークのことを指す。
【０００７】
図１８は、従来のシステムについて記述する別のシナリオを図示している。図１８は、多数のモバイル・デバイス、例えばユーザＡ１８２０と、車１８３０と、オフィス１８４０と、ユーザＢ１８５０とが接続されているグローバル・ネットワーク１８１０を示している。加えて、図１８は、モバイル・デバイス１８３０と通信可能なタグ付きオブジェクト１８６０と、別のネットワーク１８８０を介してユーザＢ１８５０と通信可能なもう１つのタグ付きオブジェクト１８７０とを示している。他のネットワーク１８８０は、アクセス・ポイントと、ＲＦＩＤリーダと、オブジェクト・センサとＢｌｕｅｔｏｏｔｈモジュールなどを備えるＰＡＮであってもよい。
【０００８】
図１８に描かれているシナリオは、置き忘れ、紛失または盗難された物をそれぞれモバイル・ネットワーク、グローバル・ネットワーク１８１０を介して発見する際にモバイル通信が有用であることを図示している。例えば、同僚、職員、トレーニング中の人などがいるキャンパスにおいて紛失物が検出されたり、企業所有の製造物が発見されたりする。さらに、個人の持ち物が、自宅、車、離れた職場で検索されることもあり、あるいはあちこちで紛失することもある。
【０００９】
しかしながら、携帯電話やデバイスに基づいたこのような検索は、オブジェクトを検索するために、例えば都市などの広いエリアにおける全ＵＧにクエリ（問合わせ）を送信するという「単純クエリ（simple query）」法によっては、うまく機能しない場合がある。これは、ネットワークにおける大きなネットワーク負荷をもたらし、過負荷状況が生じ得ることになるからである。他方で、このような検索はまた、すべての携帯電話が周囲の全オブジェクトを観察し、このようなオブジェクト・ステータスの変化を中央サーバに周期的に送信するという「単純更新（simple update）」法によっては、うまく機能しない場合もある。これは、大きなネットワーク負荷および生じ得る過負荷、ならびに携帯電話の大きなバッテリー消費をもたらすことになるからである。「単純クエリ」法および「単純更新」法などの従来の手法は、大きなネットワーク負荷の条件および潜在的なネットワーク不安定性をもたらすという欠点を有し、モバイル・デバイスの大きなバッテリー消費を伴うことになる。
【００１０】
種々の研究論文によって、実世界オブジェクトの位置決め、物品の有無の監視あるいはこれらの紛失の回避についての関連性が論じられている。非特許文献１、非特許文献２、非特許文献３、非特許文献４、及び非特許文献５が例として挙げられる。
【００１１】
しかしながら、多くのこのようなシステムは、特定のプレインストール・オブジェクト検知インフラストラクチャを提案しているが、これは展開および維持にコストがかかる。注意喚起システムは、紛失する前にユーザに通知することに焦点を当てている。概して、タグ付きオブジェクトは、しばしば意図的に置き去られることが想定され得るため、即座に通知することは、常に望ましいわけではない。
【００１２】
オブジェクト検索システムはまた、すべてのセンサ読み取り結果を中央データベースにプロアクティブ（能動的）に送信することによって実現することができ、この中央データベースは、オブジェクトの場所を見つける必要がある場合に、ある後の段階でクエリ（問合わせ）を受ける可能性がある。上記のように、この解決策は「単純更新」法と呼ぶことができる。このようなシステムは、ＩｒｉｓＮｅｔなどのグローバルデータ収集システムにおける大変な拡張性の課題を段階的に行うことになる。非特許文献６または非特許文献７を参照されたい。
【００１３】
一部の検索および分散検知システムはまた、携帯電話およびモバイル通信ネットワークインフラストラクチャの使用を提言している。非特許文献８、非特許文献９を参照されたい。
【００１４】
しかしながら、すべての上記従来の解決策は、種々のユーザが持っているデバイスから任意のセンサ情報を収集するのではなく、オブジェクトが検索されるべきアプリケーションをターゲットとしていないという欠点を有する。別のプロジェクトとしては、スコーピング・メカニズム（scoping mechanism）に基づいた解決策がある。非特許文献１０を参照されたい。
【００１５】
上記やり方の動機づけとしては、グローバル・ネットワークとローカル・センサ・ネットワーク間のメディエーターとしてユビキタス・ゲートウェイを使用して実世界オブジェクトを検索することであった。このメカニズムは、ユーザに関する情報を利用することによって、例えばワールドワイドなより大きなグローバル・ドメインから、例えばセルラー・システムの少数のセルなどのローカル・ドメインに検索焦点を狭めている。これはまた図１９に図示されている。図１９の上部のフローチャート１９１０は、例えばユーザの移動履歴、お気に入りの場所、家族および友人の情報、およびオブジェクトが最後に見られた時の状況を含むユーザに関する情報が収集される様子を示している。このような情報に基づいて、スコープとも称されるローカル・ドメインが選択可能である。これは図１９のマップ１９２０によって示され、このローカル・セクション１９３０が選択され、この場合、検索クエリがローカル・ドメインのＵＧに送信される。
【００１６】
したがって、このアルゴリズムは、例えば、最後に見られた位置（last seen position）として、ネットワークにおけるある情報ソースに基づいているという欠点を有する。このアルゴリズムが利用できる場合でも、これは、例えばローカル・ドメイン内の多数のセルを参照するという、極めて粗い情報であり得る。したがって、この提案されたアルゴリズムは、グローバル・ドメインにおける最後に見られた情報、ユーザ移動履歴、人間関係などを用いるグローバル・ドメイン・スコーピングに有用である。しかしながら、ランダム・クエリをスコープの対象となるローカル・ドメインに適用することになるので、上記問題が生じる。
【００１７】
最終遭遇ルーティング（LER：Last Encounter Routing）と称されるもう１つの従来の概念が、最後に見られた情報に基づいたアドホック・ネットワークにおけるＩＰルーティングに対して開発されてきた。非特許文献１１を参照されたい。
【００１８】
最後に見られた情報は、最終遭遇（last encounter）とも称される。この原理もまた、アドホックノードのＩＰアドレスではなく、実世界オブジェクトの場所を見つけるために適用することができる。ＬＥＲアルゴリズムにおいて、各ノードはＮＦＣによって近傍の他のノードを周期的に観察し、当該ノードが、他のノードに会った最後の遭遇位置および時間を最終遭遇履歴として記憶する。ノードＮＳがパケットをノードＮＤに送信しようとする場合、ＮＳは第１のアンカーポイントとして動作し、再帰フラッディング（recursive flooding）によって、近傍の他のノードにＮＤの最終遭遇履歴について問合わせを行う。最終遭遇履歴を発見した後、ＮＳは、位置ベースのマルチホップ・ルーティングを使用して最終遭遇位置のノードにパケットを送信し、このノードを新しいアンカーポイントとして設定する。次いで、この新しいアンカーポイントは、ＮＳによって実行されるのと同じプロセスを実行する。最終的に、このパケットはＮＤに送出される。
【００１９】
アドホック・ネットワークのゾーン・ルーティング・プロトコル（ＺＲＰ）（非特許文献１２を参照）によって、アドホック・ネットワークにおける情報検索を改良するためのもう１つのアプローチが得られる。これはアドホック・ネットワークのピア・ツー・ピアの
用途に適用される。非特許文献１３を参照されたい。
【先行技術文献】
【非特許文献】
【００２０】
【非特許文献１】Ｇａｅｔａｎｏ  Ｂｏｒｒｉｅｌｌｏ、Ｗａｙｌｏｎ  Ｂｒｕｎｅｔｔｅ、Ｍａｔｔｈｅｗ  Ｈａｌｌ、Ｃａｒｌ  ＨａｒｔｕｎｇおよびＣａｍｅｒｏｎ  Ｔａｎｇｎｅｙ、「Ｒｅｍｉｎｄｉｎｇ  ａｂｏｕｔ  ｔａｇｇｅｄ  ｏｂｊｅｃｔｓ  ｕｓｉｎｇ  ｐａｓｓｉｖｅ  ＲＦＩＤｓ」、Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ６ｔｈ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｕｂｉｑｕｉｔｏｕｓ  Ｃｏｍｐｕｔｉｎｇ（ＵｂｉＣｏｍｐ’０４），Ｎｏｔｔｉｎｇｈａｍ，Ｅｎｇｌａｎｄ，Ｓｅｐｔｅｍｂｅｒ  ２００４
【非特許文献２】Ｃｈｒｉｓｔｉａｎ  Ｄｅｃｋｅｒ、Ｕｗｅ  ＫｕｂａｃｈおよびＭｉｃｈａｅｌ  Ｂｅｉｇｌ、「Ｒｅｖｅａｌｉｎｇ  ｔｈｅ  ｒｅｔａｉｌ  ｂｌａｃｋ  ｂｏｘ  ｂｙ  ｉｎｔｅｒａｃｔｉｏｎ  ｓｅｎｓｉｎｇ」、Ｉｎ  ３ｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｓｍａｒｔ  Ａｐｐｌｉａｎｃｅｓ  ａｎｄ  Ｗｅａｒａｂｌｅ  Ｃｏｍｐｕｔｉｎｇ（ＳＡＷＣ’０３）ａｔ  ＩＣＤＣＳ’０３，Ｐｒｏｖｉｄｅｎｃｅ、ＲＩ，ＵＳＡ，Ｍａｙ  ２００３
【非特許文献３】Ｈｉｒｏｂｕｍｉ  Ｓｈｉｍｉｚｕ、Ｏｓａｍｕ  Ｈａｎｚａｗａ、Ｋｅｎｉｃｈｉｒｏ  Ｋａｎｅｈａｎａ、Ｈｉｒｏｋｉ  Ｓａｉｔｏ、Ｎｉｗａｔ  Ｔｈｅｐｖｉｌｏｊａｎａｐｏｎｇ、Ｋａｏｒｕ  ＳｅｚａｋｉおよびＹｏｓｈｉｔｏ  Ｔｏｂｅ、「Ａｓｓｏｃｉａｔｉｏｎ  ｍａｎａｇｅｍｅｎｔ  ｂｅｔｗｅｅｎ  ｅｖｅｒｙｄａｙ  ｏｂｊｅｃｔｓ  ａｎｄ  ｐｅｒｓｏｎａｌ  ｄｅｖｉｃｅｓ  ｆｏｒ  ｐａｓｓｅｎｇｅｒｓ  ｉｎ  ｕｒｂａｎ  ａｒｅａｓ」、Ｄｅｍｏｎｓｔｒａｔｉｏｎ  Ａｂｓｔｒａｃｔ  ｉｎ  Ａｄｊｕｎｃｔ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  Ｐｅｒｖａｓｉｖｅ’０５，Ｍｕｎｉｃｈ，Ｇｅｒｍａｎｙ，Ｍａｙ  ２００５
【非特許文献４】Ｒｏｙ  Ｗａｎｔ、Ｋｅｎｎｅｔｈ  Ｐ．Ｆｉｓｈｋｉｎ、Ａｎｕｊ  ＧｕｊａｒおよびＢｅｖｅｒｌｙ  Ｌ．Ｈａｒｒｉｓｏｎ、「Ｂｒｉｄｇｉｎｇ  Ｐｈｙｓｉｃａｌ  ａｎｄ  Ｖｉｒｔｕａｌ  Ｗｏｒｌｄｓ  ｗｉｔｈ  Ｅｌｅｃｔｒｏｎｉｃ  Ｔａｇｓ」、Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ＡＣＭ  ＳＩＧＣＨＩ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｈｕｍａｎ  Ｆａｃｔｏｒｓ  ｉｎ  Ｃｏｍｐｕｔｉｎｇ  Ｓｙｓｔｅｍｓ（ＣＨＩ’９９）、ｐａｇｅｓ３７０−３７７，Ｐｉｔｔｓｂｕｒｇｈ，ＰＡ，ＵＳＡ，Ｍａｙ  １９９９
【非特許文献５】Ｋｏｋ  Ｋｉｏｎｇ  Ｙａｐ、Ｖｉｋｒａｍ  ＳｒｉｎｉｖａｓａｎおよびＭｅｈｕｌ  Ｍｏｔａｎｉ、「ＭＡＸ：Ｈｕｍａｎ−ｃｅｎｔｒｉｃ  ｓｅａｒｃｈ  ｏｆ  ｔｈｅ  ｐｈｙｓｉｃａｌ  ｗｏｒｌｄ」、Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ３ｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｅｍｂｅｄｄｅｄ  Ｎｅｔｗｏｒｋｅｄ  Ｓｅｎｓｏｒ  Ｓｙｓｔｅｍｓ（ＳＥＮＳＹＳ’０５）、Ｓａｎ  Ｄｉｅｇｏ，ＣＡ，ＵＳＡ，Ｎｏｖｅｍｂｅｒ  ２００５
【非特許文献６】Ｐｈｉｌｌｉｐ  Ｂ．Ｇｉｂｂｏｎｓ、Ｂｒａｄ  Ｋａｒｐ、Ｙａｎ  Ｋｅ、Ｓｕｍａｎ  ＮａｔｈおよびＳｒｉｎｉｖａｓａｎ  Ｓｅｓｈａｎ「ＩｒｉｓＮｅｔ：Ａｎ  ａｒｃｈｉｔｅｃｔｕｒｅ  ｆｏｒ  ａ  ｗｏｒｌｄｗｉｄｅ  ｓｅｎｓｏｒ  ｗｅｂ」、ＩＥＥＥ  Ｐｅｒｖａｓｉｖｅ  Ｃｏｍｐｕｔｉｎｇ，２（４），２００３
【非特許文献７】Ｐｅｔｅｒ  Ｐｉｅｔｚｕｃｈ、Ｊｏｎａｔｈａｎ  Ｌｅｄｌｉｅ、Ｊｅｆｆｒｅｙ  Ｓｈｎｅｉｄｍａｎ、Ｍｅｍａ  Ｒｏｕｓｓｏｐｏｕｌｏｓ、Ｍａｔｔ  ＷｅｌｓｈおよびＭａｒｇｏ  Ｓｅｌｔｚｅｒ、「Ｎｅｔｗｏｒｋ−ａｗａｒｅ  ｏｐｅｒａｔｏｒ  ｐｌａｃｅｍｅｎｔ  ｆｏｒ  ｓｔｒｅａｍ−ｐｒｏｃｅｓｓｉｎｇ  ｓｙｓｔｅｍｓ」、Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２２ｎｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｄａｔａ  Ｅｎｇｉｎｅｅｒｉｎｇ（ＩＣＤＥ’０６），Ａｔｌａｎｔａ，ＧＡ，ＵＳＡ，Ａｐｒｉｌ  ２００６
【非特許文献８】Ｊ．Ｂｕｒｋｅ、Ｄ．Ｅｓｔｒｉｎ、Ｍ．Ｈａｎｓｅｎ、Ａ．Ｐａｒｋｅｒ、Ｎ．Ｒａｍａｎａｔｈａｎ、Ｓ．ＲｅｄｄｙおよびＭ．Ｂ．Ｓｒｉｖａｓｔａｖａ，「Ｐａｒｔｉｃｉｐａｔｏｒｙ  ｓｅｎｓｉｎｇ」，Ｉｎ  ＳＥＮＳＹＳ’０６Ｗｏｒｋｓｈｏｐ  ｏｎＷｏｒｌｄ−Ｓｅｎｓｏｒ−Ｗｅｂ：Ｍｏｂｉｌｅ  Ｄｅｖｉｃｅ  Ｃｅｎｔｒｉｃ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ（ＷＳＷ’０６）、Ｂｏｕｌｄｅｒ，ＣＯ，ＵＳＡ，Ｎｏｖｅｍｂｅｒ  ２００６
【非特許文献９】Ｓｈａｎｅ  Ｂ．Ｅｉｓｅｎｍａｎ、Ｇａｈｎｇ−Ｓｅｏｐ  Ａｈｎ、Ｎｉｃｈｏｌａｓ  Ｄ．Ｌａｎｅ、Ｅｍｉｌｉａｎｏ  Ｍｉｌｕｚｚｏ、Ｒｏｎａｌｄ  Ａ．ＰｅｔｅｒｓｏｎおよびＡｎｄｒｅｗ  Ｔ．Ｃａｍｐｂｅｌｌ，ＭｅｔｒｏＳｅｎｓｅ  ｐｒｏｊｅｃｔ：Ｐｅｏｐｌｅ−ｃｅｎｔｒｉｃ  ｓｅｎｓｉｎｇ  ａｔ  ｓｃａｌｅ．Ｉｎ  ＳＥＮＳＹＳ’０６  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｗｏｒｌｄ−Ｓｅｎｓｏｒ−Ｗｅｂ：Ｍｏｂｉｌｅ  Ｄｅｖｉｃｅ  Ｃｅｎｔｒｉｃ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ  ａｎｄ  Ａｐｐｌｉｃａｔｉｏｎｓ（ＷＳＷ’０６），Ｂｏｕｌｄｅｒ，ＣＯ，ＵＳＡ，Ｎｏｖｅｍｂｅｒ  ２００６またはＳｅｎｓｏｒＰｌａｎｅｔ，ｗｗｗ．ｓｅｎｓｏｒｐｌａｎｅｔ．ｏｒｇ，２００７
【非特許文献１０】Ｃ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｉｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒ；Ｔｈｅ  Ｓｅｎｓｏｒ  Ｉｎｔｅｒｎｅｔ  ａｔ  Ｗｏｒｋ：Ｌｏｃａｔｉｎｇ  Ｅｖｅｒｙｄａｙ  Ｉｔｅｍｓ  Ｕｓｉｎｇ  Ｍｏｂｉｌｅ  Ｐｈｏｎｅｓ；Ｓｕｂｍｉｔｔｅｄ  ｔｏ  Ｅｌｓｅｖｉｅｒ  Ｍｏｂｉｌｅ  ａｎｄ  Ｐｅｒｖａｓｉｖｅ  Ｃｏｍｐｕｔｉｎｇ  Ｊｏｕｒｎａｌ，２００７
【非特許文献１１】Ｍ．Ｇｒｏｓｓｇｌａｕｓｅｒ、Ｍ．Ｖｅｔｔｅｒｌｉ；Ｌｏｃａｔｉｎｇ  Ｎｏｄｅｓ  ｗｉｔｈ  ＥＡＳＥ：ｌａｓｔ  Ｅｎｃｏｕｎｔｅｒ  Ｒｏｕｔｉｎｇ  ｉｎ  Ａｄ  ｈｏｃ  Ｎｅｔｗｏｒｋｓ  ｔｈｒｏｕｇｈ  Ｍｏｂｉｌｉｔｙ  Ｄｉｆｆｕｓｉｏｎ；Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ＩＥＥＥ  ＩＮＦＯＣＯＭ  ２００３
【非特許文献１２】Ｚ．Ｊ．Ｈａａｓ  ａｎｄ  Ｍ．Ｒ．Ｐｅａｒｌｍａｎ，Ｔｈｅ  Ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  Ｑｕｅｒｙ  Ｃｏｎｔｒｏｌ  Ｓｃｈｅｍｅｓ  ｆｏｒ  ｔｈｅ  Ｚｏｎｅ  Ｒｏｕｔｉｎｇ  Ｐｒｏｔｏｃｏｌ，ＩＥＥＥ／ＡＣＭ  Ｔｒａｎｓ．Ｎｅｔｗｏｒｋｉｎｇ，９，２００１
【非特許文献１３】Ｗ．Ｋｅｌｌｅｒｅｒ，Ｒ．Ｓｃｈｏｌｌｍｅｉｅｒ；Ｐｒｏａｃｔｉｖｅ  Ｓｅａｒｃｈ  Ｒｏｕｔｉｎｇ  ｆｏｒ  Ｍｏｂｉｌｅ  Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ  Ｎｅｔｗｏｒｋｓ：Ｚｏｎｅ−ｂａｓｅｄ  Ｐ２Ｐ；Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ＩＥＥＥ  ＡＳＷＮ  ２００５，Ｐａｒｉｓ，Ｆｒａｎｃｅ，Ｊｕｎｅ  ２００５
【発明の概要】
【発明が解決しようとする課題】
【００２１】
本発明の目的は、改良されたオブジェクト検索の概念を提供することである。
【課題を解決するための手段】
【００２２】
本目的は、請求項１に記載のユビキタス・ゲートウェイ、請求項２５に記載のモバイル通信ネットワークにおける通信方法、請求項２７に記載のグローバル・クエリ・ネットワーク、請求項４２に記載のクエリ管理方法、および請求項４４に記載のオブジェクト検索システムによって達成される。
【００２３】
携帯電話などのモバイル通信ネットワークにおける分散オブジェクト情報によって、例えば、セルラーネットワークなどのグローバル・ネットワークにおける仮想情報と、携帯電話周辺のユビキタス・ネットワークなどのローカル・ネットワークにおける実世界情報との間の仲介が可能となるという点が本発明のポイントである。このようなユビキタス・ネットワークは、例えば、センサ・ネットワークを備えてもよい。以下にユビキタス・ゲートウェイ（ＵＧ）とも称されるモバイル・デバイスは、グローバル接続性および近距離無線通信接続性（ＮＦＣ）を有する。サービス・プロバイダは、これによって、ＵＧの機能を活用し、全世界にわたるサービスの広範なエリアカバレージに対して行うと特に高価となる個別センサ・インフラストラクチャを展開する場合にかかるコストを削減することができる。
【００２４】
このＵＧの機能を活用することによって、実世界オブジェクトの場所などの実世界情報の検索を、携帯電話を介した実世界情報の収集および記憶に基づいてサポートすることができる。
【００２５】
実世界データに関するクエリ（問合わせ、処理要求）は、携帯電話における実世界情報のローカルキャッシングと、物理的に近くにある電話間のキャッシュ情報のプロアクティブな共有とに基づいて改良することができるという点が、本発明のさらなるポイントである。これらの実施形態によって、グローバル・ネットワークにおける中央記憶装置に依存することなく、検索されたオブジェクトのトレース（形跡）を判断し、かつそのオブジェクトが発見されるまでクエリされたオブジェクトの近くにルーティングするために、その共有情報を使用してもよい。ルーティングは、ＮＦＣ技術やグローバル・ネットワークを使用する携帯電話間のマルチホップによって実行することができる。
【００２６】
これらの実施形態は、したがって、実世界のオブジェクト、人物、紛失物、実世界におけるサービスの発見、つまり、モバイルオブジェクトによって提供されるサービス、メッシュ／アドホック・ネットワークにおけるセルラーネットワーク支援ＩＰルーティングおよび携帯電話間のローカル共有情報の発見の助けとなり得る。これらの実施形態は、実世界情報の検索がさらなるインフラストラクチャのセットアップなしに実行でき、携帯電話のネットワーク帯域幅およびエネルギー消費を削減する最適化検索が実行することができるという利点がある。したがって、いくつかの実施形態によって、新しいビジネス・ソリューションが可能となる。
【００２７】
これらの実施形態は、さらなる情報がモバイル・デバイス間でローカルに共有可能であるため、クエリおよび情報更新数を含むネットワーク・トラフィックが削減可能であるという利点がある。ローカル・ネットワーキングとグローバル・ネットワーキングとの間の活用（leveraging）、あるいは平衡化が可能となる。また、ローカル情報交換、情報キャッシングまたはグローバル・ネットワークの使用がより好都合であるか否かを判断する適用要件に応じて異なる解決策が可能となる。
【００２８】
実施形態によれば、特にモバイル通信ネットワークにおける反応性、つまりクエリベースのアプローチを使用することができ、これによって、例えば、オブジェクト・センサＡが見たオブジェクトＸとしてのセンサ読み取り数は、クエリ数よりもかなり多いと予想される。その反応性を利用するアプローチは、物理的に近くにあるモバイル・デバイス間においてローカルにプロアクティブな情報更新を行うことによって論じられているが、このアプローチは、一部の実施形態においては、全検知情報を中央データベースに対して更新することを意図していない。この実施形態は、種々のユーザが持っているデバイスから任意のセンサ情報を収集するのではなく、オブジェクトが検索されるべきアプリケーションを対象とすることを可能にする。さらに、デバイスは、改良された検索ルーティングに対するセルラー・インフラストラクチャを利用することができる。
【００２９】
これらの実施形態によれば、例えば、上記のスコーピングアルゴリズムのような従来のアルゴリズムを利用することもできる。例えば、ローカル・ドメイン内のモバイル通信ネットワークの少数のセルに関して、大まかな範囲の縮小が可能となる。検索クエリを改良するために、クエリ（問合わせ）を受けた携帯電話に記憶されている情報を考慮して、最後に見られた位置の周辺にあるＵＧに対してクエリのランダムなインストールを行うことができる。実施形態によれば、従来のやり方がクエリのより高速な収束に関して改良可能であるという利点がある。
【００３０】
実施形態は、モバイル・デバイスの近傍のノードはＮＦＣを介して観察可能であり、かつ情報は他のノード間で交換されないこともあるため、モバイル・デバイスにおけるバッテリー消費を削減するという利点がある。位置ベースのマルチホップ・ルーティング経路は、グローバル・ネットワーク、つまりセルラー経路と置換されて、オーバーヘッドを削減し、検索をスピードアップさせることができる。本発明の実施形態においては、アンカーポイントが変化している間に、複数のクエリが、検索不可能期間を回避するために、ターゲットとなるアンカーポイントの位置の周辺に対して平行してインストールすることができる。さらに、あるノードに記憶されている情報の隣接ノードへの重複が可能となる。上記オブジェクトの検索を改良するために、使用可能な情報、つまりオブジェクトに関するデータをローカルに共有するという原理を利用してもよい。
【００３１】
本発明はしたがって、携帯電話のＵＧの機能を活用することが有効であるという発見に基づいている。これらの実施形態は、実世界オブジェクトの位置などの実世界情報の検索をサポートすることができる。これは、携帯電話を介した実世界情報の収集および記憶に基づいている。実施形態では、携帯電話は実世界情報をローカルにキャッシュして、物理的に近くにある携帯電話間で上記キャッシュ済みの情報をプロアクティブに共有することができる。また、この共有情報は、グローバル・ネットワークにおける中央記憶装置に依存することなく、検索されたオブジェクトのトレースを判断するために使用することができ、ＮＦＣ技術を使用したり、そのグローバル・ネットワークを使用することによって、ルーティングにおいて携帯電話間のマルチホップを行うことができる。
【００３２】
いくつかの実施形態として、携帯電話によって検知され、かつこれにおいてキャッシュされた情報は、オブジェクト・キャッシュおよびＵＧキャッシュに記憶することができる。前者は、観察されたオブジェクトに関する情報を位置と時間とともに含有することができる。後者は、観察された携帯電話（ＵＧ）に関する情報を位置と時間とともに含有することができる。両キャッシュは、例えばＮＦＣを使用して隣接する携帯電話間で周期的に交換することができる。実施形態では、ＮＦＣを使用するマルチホップ通信に基づいて検索を実行することができる。ＵＧｓがオブジェクトＯＤの検索をしようとする場合、ＵＧｓは自身のオブジェクト・キャッシュをチェックしてもよい。このオブジェクト・キャッシュにＯＤのレコード（record）がある場合、ＵＧｓは、最後に見られた位置および時間を取得し、次いでそのＵＧキャッシュから得た位置にあるＵＧ２を選択することができる。また、ＵＧアドレス、例えば電話番号は、そのＵＧキャッシュから分かるので、ＵＧｓは、ＮＦＣを介して、あるいはその位置が離れている場合は、セルラーネットワークを介して、一致するレコード情報を有するＵＧ２にオブジェクト検索クエリを送信することができる。次いで、ＵＧ２は、自身のオブジェクト・キャッシュおよびＵＧキャッシュをチェックすることができ、ＯＤに関するより新しいレコードがあれば、ＵＧ２は、新しいＵＧ３を選択して、クエリをＵＧ３に送信することができる。このようにして、実施形態は、より新しいレコードを有するＵＧを自由に追跡することができ、最終的にＯＤは発見されることになる。
【００３３】
別の実施形態では、グローバル・ネットワーク、例えばセルラーネットワークを使用して検索を実行することができる。また、ネットワーク負荷を削減して検索を改良するために、グローバル・クエリ・マネージャ（ＧＱＭ）を中央サーバとして使用することができる。このような実施形態では、オブジェクト・キャッシュのみを使用することができる。ＵＧの場所については、モバイル通信システムにおける携帯電話の登録位置、つまりセルの細かさに左右されることがある。ＧＱＭが、オブジェクトＯＤの検索クエリを受信すると、ＵＧを選択して、このオブジェクト・キャッシュを検索して、可能ならば、ＯＤに関するレコードを取得してもよい。基本的に、ＵＧは、ランダムに選択可能であり、例えば、ＧＱＭが、ユーザの挙動パターン、先行検索結果などに関する何らかの情報を事前に有していれば、そのＧＱＭは、オブジェクトが発見される可能性のある場所に関する最高尤度にしたがって、全ての可能なＵＧをフィルタリングすることができる。ＵＧが、ＯＤに関するレコードを有さない場合、ＧＱＭは別のＵＧを選択することができる。レコードがヒットすると、ＧＱＭは、そのレコードから最後に見られた位置を取得することができ、次いで、その位置の周辺にあるいくつかのＵＧを選択することができる。
【００３４】
いくつかの実施形態によれば、ＧＱＭは、選択されたＵＧからより新しいレコードを取得することができる。より新しいレコードが発見された場合、ＧＱＭは、より新しい位置の周辺にあるいくつかのＵＧを選択することができ、その最新の位置を再帰的に見出すことができる。最終的に、より新しいレコードが発見されなければ、ＧＱＭは、最新のレコードが検索オブジェクトＯＤの現在位置を示していると想定して、これは次いで、最後に見られた位置の周辺にあるいくつかのＵＧに対してオブジェクト検索クエリをインストールすることができる。
【００３５】
これら実施形態は、例えば、Ｃ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｉｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒによって導入されたスコーピング・メカニズムを利用するシステムと組み合わせて使用することができ、この場合、実施形態はまた、より大きなスケールやグローバル・ドメインに対して有用となり得る。
【００３６】
したがって、これらの実施形態は、ローカル・ネットワークと、例えばセルラーネットワークといったグローバル・ネットワークとの間を仲介するオブジェクト・センサとして動作するように携帯電話が活用されるので、オブジェクト検知用のインフラストラクチャを何らインストールする必要なく実世界オブジェクトの検索が可能となるという利点がある。携帯電話にキャッシュされたオブジェクトに関する情報に基づいて、例えば、「単純クエリ」や「単純更新」などの他の従来の手法よりも小さなネットワーキング・オーバーヘッドによってより高速のオブジェクトの発見が可能となる。
【００３７】
本発明の実施形態は、プロアクティブにキャッシュ情報を共有することにより検索待ち時間が改善するという利点がある。実施形態の別の利点は、完全に分散した動作モードによる動作性であり、グローバルサーバを用いる必要がないため、これら実施形態は実施するのが容易である。さらに、実施形態は、検索待ち時間をさらに短縮するために、グローバル・ネットワークを使用することができる。
【００３８】
さらに、これらの実施形態は、従来のアプローチより小さいネットワーク負荷によって検索クエリを実行することができるという利点がある。また、オブジェクトを追跡することができるため、移動するオブジェクトのために使用することができる。また、グローバル・ネットワークシステムを必ずしも用いる必要がないため、これらの実施形態は、容易に実施することができる。また、これらの実施形態は、多数の頻繁に検索されるオブジェクトに対して検索待ち時間をより短くすることができる。さらに、ＮＦＣ通信にのみに依存しているため、バッテリー消費に関してよりコスト効果の高いクエリが可能となる。また、例えばモバイル・アドホック・ネットワークのＩＰアドレスといった識別子や、人物、モバイル・デバイスによって提供されたサービスなどの実世界情報に対する検索について使用することができ、これらは、以下において全てオブジェクトとみなされる。
【００３９】
以下、実施形態について添付の図面を使用して詳細に説明する。
【図面の簡単な説明】
【００４０】
【図１ａ】ユビキタス・ゲートウェイの実施形態を示している。
【図１ｂ】ユビキタス・ゲートウェイの別の実施形態を示している。
【図１ｃ】グローバル・クエリ・マネージャの実施形態を示している。
【図２ａ】オブジェクト・キャッシュの実施形態を示している。
【図２ｂ】ＵＧキャッシュの実施形態を示している。
【図３ａ】ＵＧの実施形態のフローチャートを示している。
【図３ｂ】ＵＧにおけるオブジェクト検索クエリ処理の実施形態のフローチャートを示している。
【図４ａ】実施形態の情報共有を図示するシナリオを示している。
【図４ｂ】ＵＧの実施形態での情報キャッシングの図を示している。
【図４ｃ】実施形態の情報共有を図示する別のシナリオを示している。
【図４ｄ】実施形態を使用する主要検索クエリを図示している。
【図５ａ】グローバル・クエリ・マネージャの実施形態のフローチャートを図示している。
【図５ｂ】ＧＱＭにおけるオブジェクト検索クエリのプロセスの実施形態のフローチャートを図示している。
【図６ａ】ＵＧにおけるメインループの実施形態のフローチャートを図示している。
【図６ｂ】ＵＧにおけるオブジェクト検索クエリのプロセスの実施形態のフローチャートを図示している。
【図７ａ】ＧＱＭベースクエリを利用する実施形態のシナリオを図示している。
【図７ｂ】ＧＱＭベースクエリを利用する実施形態の別のシナリオを図示している。
【図８】ＧＱＭベースクエリを利用する実施形態の代替的シナリオを図示している。
【図９】様々なＵＧ密度での平均クエリ成功時間のシミュレーション結果を示している。
【図１０】クエリごとのグローバル・ネットワーク使用時間についてのシミュレーション結果を示している。
【図１１】クエリごとのＮＦＣ使用量に関するシミュレーション結果を示している。
【図１２】時間当たりの全ＮＦＣ使用量に関するシミュレーション結果を示している。
【図１３】様々なオブジェクト密度での平均クエリ成功時間に関するシミュレーション結果を示している。
【図１４】ＵＧにおける様々なオブジェクト・キャッシュサイズでの平均クエリ成功時間に関するシミュレーション結果を示している。
【図１５】様々なオブジェクト移動レートでの平均クエリ成功時間に関するシミュレーション結果を示している。
【図１６】ネットワークコストに関するシミュレーション結果を示している。
【図１７】最新シナリオを示している。
【図１８】最新のモバイル通信ネットワークのブロック図を示している。
【図１９】最新のスコーピングアルゴリズムを示している。
【００４１】
図１ａは、モバイル通信ネットワークにおいて通信するためのユビキタス・ゲートウェイ（ＵＧ）１００の実施形態を示している。このモバイル通信ネットワークは、複数のユビキタス・ゲートウェイを備えている。ユビキタス・ゲートウェイ１００は、モバイル通信ネットワークと通信するための第１の通信手段１１０と、他のユビキタス・ゲートウェイと通信しかつオブジェクトと通信するための第２の通信手段１２０とを備えている。このオブジェクトは、オブジェクト識別情報（object identification）を有し、第２の通信手段１２０は、ユビキタス・ゲートウェイ又はオブジェクトから受信されたオブジェクト・レコード（object record）を検出するように構成されるものである。さらに、ユビキタス・ゲートウェイ１００は、オブジェクト・レコード識別情報（object record identification）と、オブジェクト識別情報と、オブジェクト・ロケーション情報（object location）とを含むオブジェクト・レコードを一時的に記憶するためのオブジェクト・キャッシュ１３０を備えている。さらに、ユビキタス・ゲートウェイ１００は、第２の通信手段１２０を介してオブジェクトを繰り返し監視し、監視されたオブジェクトのオブジェクト・レコードをオブジェクト・キャッシュ１３０に記憶し、オブジェクト・キャッシュ１３０からのオブジェクト・レコードを他のユビキタス・ゲートウェイと繰り返し交換するように構成されたコントローラ１４０を備えている。コントローラ１４０は、クエリ元（問合わせ元）からクエリ・オブジェクト（クエリの対象となるオブジェクト）に関するオブジェクト・クエリ（オブジェクトについてのクエリ）を受信し、クエリ・オブジェクトに関するオブジェクト・レコードを、可能な場合は、オブジェクト・キャッシュ１３０からクエリ元に報告するように構成されている。
【００４２】
図１ｂは、ユビキタス・ゲートウェイ１００の別の実施形態を示している。このユビキタス・ゲートウェイ１００は、ＵＧレコード識別情報と、ＵＧ識別情報と、ＵＧロケーション情報とを備えるＵＧ・レコードを一時的に記憶するためのＵＧキャッシュ１５０をさらに備えている。この場合、コントローラ１４０は、第２の通信手段１２０を介して他のユビキタス・ゲートウェイを繰り返し監視し、監視されたユビキタス・ゲートウェイに関するＵＧ・レコードをユビキタス・ゲートウェイ・キャッシュ１５０に記憶し、第２の通信手段１２０を介してユビキタス・ゲートウェイ・キャッシュ１５０からのユビキタス・ゲートウェイ・レコードを他のユビキタス・ゲートウェイと繰り返し交換し、ユビキタス・ゲートウェイ・キャッシュ１５０からのユビキタス・ゲートウェイ・レコードに基づいてオブジェクト・クエリを別のユビキタス・ゲートウェイに転送するように構成されている。
【００４３】
実施形態では、オブジェクト・レコードはさらに、オブジェクトが最後に見られた時間のタイムスタンプと、オブジェクトを監視したユビキタス・ゲートウェイのユビキタス・ゲートウェイ識別情報と、ユビキタス・ゲートウェイによってオブジェクトが継続的に監視された期間と、（オブジェクトが）最後に見られたと推定される位置（estimated last seen position）と、オブジェクトが移動可能であるか否かの情報と、オブジェクト・レコードを交換したユビキタス・ゲートウェイの履歴と、オブジェクト・レコードが伝搬したホップ数とのうちの１つ又はこれらの組み合わせを含むことができる。
【００４４】
他の実施形態では、ユビキタス・ゲートウェイ・レコードはさらに、ユビキタス・ゲートウェイが最後に監視された時間のタイムスタンプと、ユビキタス・ゲートウェイが最後に見られたと推定される位置と、ユビキタス・ゲートウェイの平均速度と、ユビキタス・ゲートウェイ速度の標準偏差と、ユビキタス・ゲートウェイ・レコードを転送したユビキタス・ゲートウェイの履歴と、ユビキタス・ゲートウェイ・レコードが伝搬したホップ数とのうちの１つまたはこれらの組み合わせを含むことができる。
【００４５】
実施形態では、コントローラ１４０は、オブジェクト・キャッシュ１３０におけるオブジェクト・レコードまたはユビキタス・ゲートウェイ・キャッシュ１５０におけるユビキタス・ゲートウェイ・レコードを更新するように構成可能である。オブジェクト・レコードあるいはＵＧレコードはまた。他のＵＧから受信することができる。コントローラ１３０は、より新しいオブジェクト・レコードが使用可能ならば、古いオブジェクト・レコードを破棄するように構成可能である。したがって、コントローラ１４０は、より新しいＵＧレコードが使用可能ならば、古いＵＧレコードを破棄するように構成可能である。コントローラ１４０は、近傍のオブジェクトを周期的に監視し、新しいオブジェクト・レコードが使用可能になれば、オブジェクト・キャッシュ１３０におけるオブジェクト・レコードを更新するように構成可能である。近傍のオブジェクトを監視する周期は、１０秒〜５分とすることができる。
【００４６】
実施形態では、コントローラ１４０は、近傍のＵＧを周期的に監視し、より新しいＵＧレコードが使用可能になれば、ＵＧキャッシュ１５０におけるＵＧレコードを更新するように構成可能である。さらに、コントローラ１４０は、更新オブジェクト・レコードや更新ＵＧレコードを近傍のＵＧと周期的に交換するように構成可能である。近傍かどうかについては、第２の通信手段１２０のカバレージエリアによって判断することができ、これは、例えばＮＦＣの場合もある。他の実施形態では、近傍かどうかについては、ホップ数や、第２の通信手段１２０を介して通信されたＵＧによって決定することができる。
【００４７】
他の実施形態では、コントローラ１４０は、オブジェクト・クエリの有効期間（lifetime）を考慮し、有効期間が過ぎた場合にオブジェクト・クエリを破棄するように構成可能である。コントローラ１４０は、クエリ元へのクエリ・オブジェクトに関する更新レコードについて有効期間が過ぎる前に、オブジェクト・クエリに応答するように構成可能である。さらに、コントローラは、オブジェクト・クエリが転送されたユビキタス・ゲートウェイのユビキタス・ゲートウェイ識別情報を記憶し、有効期間が過ぎたり、クエリ・オブジェクトが発見されたり、オブジェクト・クエリがキャンセルされる場合に、オブジェクト・クエリが転送された全ＵＧにオブジェクト・クエリのキャンセルを要求することができる。
【００４８】
さらに、コントローラ１４０は、オブジェクト・クエリが転送可能な回数について、例えば、ホップ数に関して制限を設定することができる。ユビキタス・ゲートウェイ１００はさらに、ＧＰＳ受信機（ＧＰＳ＝グローバル・ポジショニング・システム）を使用して実現可能な、自身の位置を判断するための手段を備えることができる。別の実施形態では、ＵＧ１００はさらに、オブジェクト・レコードおよびＵＧレコードによって準備されたブルームフィルタ（Bloom filter）を備えることができる。
【００４９】
実施形態では、第１の通信手段１１０は、セルラーモバイル通信ネットワークにおいて通信するように構成可能である。第１の通信手段１１０は、ＧＳＭ（登録商標）、ＵＭＴＳ、ＬＴＥ（登録商標）、ＦＯＭＡ（マルチメディアへの移動体のアクセスの自由）（登録商標）などにしたがって通信するように構成することができる。第２の通信手段１２０は、ＤＥＣＴ（ディジタルコードレス電話）、Ｂｌｕｅｔｏｏｔｈ（登録商標）、ＲＦＩＤ、ＩＳＭ、ＷＬＡＮなどにしたがって通信するように構成可能である。
【００５０】
コントローラ１４０はさらに、クエリ・オブジェクトに対する検索クエリを受信およびインストールするように構成可能である。コントローラ１４０はさらに、受信およびインストールされた検索クエリへの応答としてクエリ・オブジェクトをプロアクティブ（proactive）に検索するように構成されている。モバイル通信ネットワークと通信するための手段１１０は、通信プロトコルを使用して通信するように構成することができ、この通信プロトコルは、クエリ・オブジェクトがその通信プロトコルを使用して通信ができないようなものである。
【００５１】
図１ｃは、複数のユビキタス・ゲートウェイを備えるモバイル通信ネットワークで動作するためのＧＱＭ１６０の実施形態を示している。ユビキタス・ゲートウェイは、移動可能であり、また、モバイル通信ネットワークにおいて通信し、かつオブジェクト・レコードを記憶するように構成されている。ＵＧは、上記ＵＧ１００に対応することができる。ＧＱＭ１６０は、複数のユビキタス・ゲートウェイと通信するための手段１１０を備えており、この手段１１０は、ユビキタス・ゲートウェイから受信されたオブジェクト・レコードを検出するように構成されている。ＧＱＭ１６０はさらに、ユビキタス・ゲートウェイによって報告されたオブジェクト・レコードを一時的に記憶するためのオブジェクト・キャッシュ１８０を備え、オブジェクト・レコードは、オブジェクト・レコード識別情報と、オブジェクト識別情報とオブジェクト・ロケーション情報とを含むものである。
【００５２】
ＧＱＭ１６０はさらに、クエリ・オブジェクトについてのレコード・リクエストをクエリ元から受信し、レコード・リクエストをクエリＵＧに転送するためのコントローラ１９０を備え、このコントローラ（１９０）は、オブジェクト・レコードにアクセスして、可能な場合にはオブジェクト・キャッシュ１８０に一時的に記憶されているクエリ・オブジェクト・レコードに基づいて複数のＵＧからクエリＵＧを選択するか、他の方法でランダムに選択するように構成されている。
【００５３】
実施形態では、コントローラ１９０は、オブジェクト・レコードを報告したＵＧに関するユビキタス・ゲートウェイ識別情報をさらに記憶するように構成可能である。コントローラ１９０は、クエリ・オブジェクトに関するオブジェクト・レコード、つまりクエリ・オブジェクト・レコードを報告したＵＧに基づいてクエリＵＧを選択することができる。コントローラ１９０はまた、オブジェクト・キャッシュ１８０に記憶されているクエリ・オブジェクト・ロケーション情報とクエリＵＧロケーション情報とに基づいて、クエリＵＧを選択することができる。
【００５４】
オブジェクト・レコードはさらに、オブジェクトが最後に見られた時間のタイムスタンプと、オブジェクトを監視したユビキタス・ゲートウェイのユビキタス・ゲートウェイ識別情報と、オブジェクトがユビキタス・ゲートウェイによって継続的に監視された期間と、最後に見られたと推定される位置と、オブジェクトが移動可能であるか否かと、オブジェクト・レコードを交換したユビキタス・ゲートウェイの履歴と、オブジェクト・レコードが伝搬したホップ数とうちの１つまたはこれらの組み合わせを含むことができる。
【００５５】
コントローラ１９０は、ＮＦＣを使用してクエリ・オブジェクトについての検索クエリを別のＵＧに転送するクエリＵＧに検索クエリをインストールし、クエリ・オブジェクトにプロアクティブにクエリ（問合わせ）を行うように構成可能である。さらに、コントローラ１９０は、クエリＵＧから別のＵＧへの検索クエリの転送に基づいてオブジェクト・レコードを受信することができ、この別のＵＧもまた検索クエリを転送することができる。
【００５６】
コントローラ１９０は、有効期間（lifetime）とクエリ・リクエストを関連付けて、検索リクエストの有効期間が過ぎた場合に、クエリ元に通知するように構成可能である。コントローラ１９０は、クエリ・リクエストをクエリＵＧに転送するように構成可能であり、これは、オブジェクト・キャッシュ１８０からのオブジェクト・レコードよりも新しいオブジェクト・レコードを有しやすくなる。コントローラ１９０は、推定クエリ・オブジェクト・ロケーションの近傍に配置されているＵＧにクエリ・リクエストを転送することができる。この近傍かどうかについては、モバイル通信ネットワークによって、あるいはオブジェクト・キャッシュ１８０から決定される。コントローラ１９０は、所定数のクエリＵＧにクエリ・リクエストを転送するように構成可能である。コントローラ１９０は、所定数のＵＧに検索クエリをインストールすることができる。コントローラ１９０は、最新の検索オブジェクトのロケーション情報をクエリ元に提供可能である。コントローラ１９０は、クエリ・リクエストをユビキタス・ゲートウェイから、あるいはモバイル通信ネットワークのネットワーク・ノードから受信するように構成可能である。通信手段１７０は、通信プロトコルを使用して通信するように構成可能である。この通信プロトコルは、クエリ・オブジェクトがその通信プロトコルを使用して通信ができないようなものである。
【００５７】
以下、２つの詳細な実施形態について説明する。これらの実施形態は、ローカル・ドメインにおけるオブジェクト検索に対して特に効率的であり、また、例えばＣ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｏｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒによって説明されているようなアルゴリズムと組み合わせてグローバル・ドメインにも適用可能である。
第１の実施形態においては、本実施形態が完全分散オブジェクト追跡アルゴリズムを実現可能であるため、中央サーバはなくてもよい。上記説明によると、ＵＧの各実施形態は、観察されたオブジェクトに関する情報、いわゆるオブジェクト情報あるいはレコードを含有するオブジェクト・キャッシュを有する。ＵＧにおけるオブジェクト・キャッシュの実施形態が図２ａに示されている。さらに、ＵＧは、観察されたＵＧに関する情報、いわゆるＵＧ情報あるいはレコードを含有するＵＧキャッシュを備えている。ＵＧにおけるＵＧキャッシュの実施形態が図２ｂに描かれている。さらに、これら２つのキャッシュは、一実施形態では、ＮＦＣを介して近傍のＵＧ間で周期的に交換される。この近傍かどうかについては、例えば、ＮＦＣ、つまり第２の通信手段１２０を介してＵＧの隣接ホップの１つによって決定することができる。
【００５８】
図２ａから分かるように、オブジェクト・キャッシュにおけるレコードは、オブジェクトが最後に見られた時間と、オブジェクトＩＤと、オブジェクトをスキャンしたＵＧのＩＤと、オブジェクトがＵＧによって継続的に観察された期間と、最後に見られたと推定される位置と、オブジェクトが移動可能であるか否かの情報と、このレコードを伝搬したＵＧの履歴と、レコード伝搬がされたホップ数などとを含むことができる。
【００５９】
したがって、図２ｂは、ＵＧキャッシュの実施形態を示しており、ＵＧキャッシュは、ＵＧが最後に見られた時間と、ＵＧのＩＤと、最後に見られたと推定される位置と、ＵＧの平均速度と、ＵＧ速度の標準偏差と、このレコードを転送したＵＧの履歴と、ホップ数などとを含むことができる。
【００６０】
実施形態では、これらのキャッシュサイズは制限されることがあり、余分な古いレコードは破棄することができる。実施形態では、ＵＧによって記憶されているキャッシュは、１の隣接ホップに周期的に送信可能である。隣接ＵＧの受信は、そのレコードを自身のレコードと比較したり、欠落しているレコードを追加したり、古いそれ自体のレコードに上書きしたり、古い受信レコードを破棄することができる。レコードのホップカウントおよびルートはこれに応じて更新することができる。キャッシュサイズが制限される場合があるため、古いエントリは、実施形態では、キャッシュから破棄されることもある。
【００６１】
以下、実施形態のフローチャートを図３ａおよび３ｂを用いて詳細に説明および図示する。図３ａおよび３ｂは、分散アプローチを利用する第１の実施形態で実現される機構の実施形態を図示している。図３ａは、クエリがインストールされていなくても、ＵＧが継続的に動作可能なメインループの実施形態のフローチャートを示している。
【００６２】
図３ａの左側によると、ＵＧのアルゴリズムはステップ３０２で開始され、これには、「Ｂ」とラベル付けされているステップ３０４が続き、これはＵＧで実行されるメインループのリターン・ポイントである。このメインループを現在実行しているＵＧＥＸＥは、近傍のオブジェクトを観察し、このオブジェクト・キャッシュを周期的に更新し、これらをｆｏｕｎｄ＿ｏｂｊｅｃｔアレイに記録する。ここで、ｆｏｕｎｄ＿ｏｂｊｅｃｔｓはアレイに使用される変数である。図３ａに描かれているフローチャートにおいて、これはステップ３０６で示され、ここでは、変数ｆｏｕｎｄ＿ｏｂｊｅｃｔｓおよびｆｏｕｎｄ＿ＵＧｓがクリアされる。ステップ３０８において、オブジェクトのチェック周期は評価され、これは、後述されるカウンタｏｂｊｅｃｔ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄによって実現される。上記カウンタが０の場合、ステップ３１０がステップ３０８に続き、ここでは隣接オブジェクトがチェックされ、オブジェクト・キャッシュが更新され、変数ｆｏｕｎｄ＿ｏｂｊｅｃｔｓが更新される、つまり、オブジェクトのチェック周期で発見されたオブジェクトのリストがリセットされる。したがって、ＵＧ監視のチェック周期がステップ３１２でチェックされ、ここで変数ＵＧ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄの値が検証される。カウンタが０の場合、ステップ３１４がステップ３１２に続き、ここでは隣接ＵＧがチェックされ、ＵＧキャッシュが更新され、リストｆｏｕｎｄ＿ＵＧｓが更新され、ＵＧ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄがリセットされる。さらに、ステップ３１６において、２つのキャッシュ、つまりオブジェクト・キャッシュおよびＵＧキャッシュは、例えば、ＮＦＣや第２の通信手段１２０を介して隣接ＵＧと交換される。
【００６３】
ステップ３１８において、上記カウンタは減じられる。オブジェクトに対するＵＧの近傍をチェックする周期は、値ｏｂｊｅｃｔ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄによって決定され、例えば周期は１〜５分である。ＵＧＥＸＥはまた、変数ＵＧ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄにしたがって近傍のＵＧを周期的に観察し、これらをリストに、例えばｆｏｕｎｄ＿ＵＧｓアレイに記憶する。近傍のＵＧをチェックする周期は、値ＵＧ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄによってカウントされる。この期間中、ＵＧＥＸＥはまた、ステップ３１６において、ＮＦＣを介してこのオブジェクト・キャッシュおよびＵＧキャッシュを隣接ＵＧと交換する。実施形態では、ＵＧＥＸＥは、キャッシュの相違のみを送信し、常に全キャッシュを交換しないことによってＮＦＣトラフィックを削減することができる。
【００６４】
この後、ＵＧＥＸＥは、ステップ３２０で開始するループにしたがって全インストール済みクエリを実行する。ステップ３２２において、ＵＧＥＸＥは変数ｑｕｅｒｙ＿ｌｉｆｅｔｉｍｅを減じ、これは、クエリの有効期間(lifetime)を決定およびカウントダウンするために使用される。ステップ３２６において、ＵＧＥＸＥはまずクエリの有効期間をチェックする。有効期間が過ぎた場合、つまりｑｕｅｒｙ＿ｌｉｆｅｔｉｍｅ＝０の場合、ＵＧＥＸＥがクエリの発信元であるか否かがステップ３２６でチェックされる。そうである場合、ステップ３２８において、ＵＧＥＸＥはユーザに、クエリが失敗したことを通知し、ステップ３３０においてクエリを削除する。ＵＧＥＸＥがクエリの発信元ではない場合、クエリは、ステップ３３０において即座に削除される。ステップ３２４においてｑｕｅｒｙ＿ｌｉｆｅｔｉｍｅが満了していない場合、ステップ３３２においてオブジェクトが検索され、かつクエリ・プロセスが実行され、これは図３ｂに詳述される。ステップ３３４においてクエリ・ループを終了し、これによってステップ３２０〜３３４がクエリごとに実行される。ステップ３３６がステップ３３４に続き、ここでアルゴリズムがステップ３０４つまり「Ｂ」に戻る。
【００６５】
図３ａの右側には、ステップ３３８から開始するフローチャートが描かれている。本実施形態では、このプロセスは、ＵＧＥＸＥが、ステップ３４０において、発信した別のＵＧからクエリ成功を受信する場合に開始される。次いで、ステップ３４２においてユーザに結果を示し、ステップ３４４に進む。ステップ３４４において、ＵＧＥＸＥは、クエリを送信したＵＧにクエリ・キャンセルを送信することになる。ステップ３４６がステップ３４４に続き、ここでは、ＵＧＥＸＥは、ステップ３４８でサブルーチンを終了する前にクエリを削除する。
【００６６】
ＵＧＥＸＥが別のＵＧに対するオブジェクトのクエリに関与した場合には、別のシナリオが考慮され、この場合、サブルーチンはステップ３５０で開始し、これによって、ＵＧＥＸＥは、ステップ３５２において、別のＵＧからクエリ・キャンセルを受信することができる。この場合、ＵＧはステップ３４４に進み、それ自体がクエリを送信したＵＧにクエリ・キャンセルを送信し、また、ステップ３４８でサブルーチンを終了する前にステップ３４６においてクエリを削除する。
【００６７】
クエリ元、例えばＵＧｏｒｉｇｉｎが、オブジェクトＯＤを検索しようとする場合、「ヒットなし」モードでオブジェクト・クエリを発信し、まずクエリをそれ自体にインストールすることができる。「ヒットなし」モードは、ＯＤについての関連するレコードなしでクエリがインストールされるモードについて説明するために使用される。クエリのインストール後、ＵＧｏｒｉｇｉｎはこのクエリの最初のＵＧＥＸＥになり、図３ｂにしたがって説明されるように、オブジェクト検索クエリ・プロセスを実行する。このアルゴリズムは主に２つの段階３６０および３６２からなり、これらは図３ｂでは破線ボックスで示されている。第１の段階３６０は、近傍のオブジェクトやＵＧを観察する「オブジェクトおよびＵＧチェック」とも称される。もう一方の段階、段階３６２は、ＵＧＥＸＥのオブジェクト・キャッシュに新しいレコードがあるか否かをチェックし、クエリを次に適切なＵＧに送信する「新レコードチェック」段階とも称される。
【００６８】
実施形態は、レコードが新しいか否かについて判断するために複数の異なる基準を利用することができる。最も単純な基準は、レコードＲ１における情報生成時間Ｔ１が別のレコードＲ２における情報生成時間Ｔ２より新しいことであり、これは、Ｔ１＞Ｔ２の場合、Ｒ１のほうが新しいことを意味している。別の基準は、記録時期（record age）Ａ１（＝現在時−Ｔ１）が別の記録時期Ａ２（＝現在時−Ｔ２）のレートαより低いことであり、これは、例えばα＝１／２の場合Ａ１＜αＡ２ならば、Ｒ１のほうが新しいことを意味している。時間基準のみではない他の基準、例えば距離基準も使用することができる。例えば、レコードＲ１の生成位置がＲ２の生成位置から離れている場合、新しさはＴ１＞Ｔ２によって比較され、そうでなければＡ１＜αＡ２によって比較される。以下の形態において、最も単純な基準Ｔ１＞Ｔ２が用いられるが、実施形態はこの基準に制限されない。
【００６９】
図３ｂのフローチャートは、「Ｆ」ともラベル付けされるステップ３６４において、「オブジェクトおよびＵＧチェック」段階３６０から開始する。「オブジェクトおよびＵＧチェック」段階３６０において、ステップ３６６では、変数ｆｏｕｎｄ＿ｏｂｊｅｃｔｓおよびｆｉｎｄ＿ｔａｒｇｅｔ＿ｏｂｊｅｃｔに基づいて、ターゲット・オブジェクトが発見されたか否かがチェックされる。そうである場合、ＵＧＥＸＥは、ステップ３６８において、成功をＵＧｏｒｉｇｉｎに通知し、ステップ３７０において、クエリを送信したＵＧにクエリ・キャンセルを送信する。この後、ステップ３７２においてクエリを削除することができ、アルゴリズムはステップ３７４に進み、これは、アルゴリズムが終了するポイント３９８にジャンプする。可能ならば、ＵＧＥＸＥは、ステップ３７０においてクエリ・キャンセルについて、クエリを送信した他のＵＧに要求を行う。
【００７０】
ステップ３６６のチェックがうまくいかない場合、ステップ３７６において、隣接ＵＧがあるか否かがチェックされる。隣接ＵＧがステップ３７６で発見されれば、ＵＧＥＸＥはステップ３７８で、ｂｒｏａｄｃａｓｔ＿ｈｏｐ＿ｌｉｍｉｔを超えるか否かをチェックして、そうではない場合、ステップ３８０において、クエリをこれらのＵＧにコピーする。ステップ３７８において、変数ｂｒｏａｄｃａｓｔ＿ｈｏｐ＿ｌｉｍｉｔは依然として正であるか否かがチェックされる。そうである場合、ステップ３８０において、ＵＧＥＸＥはクエリをコピーして、上記変数を１減じる。さらに、事前にクエリをインストールしていなかった隣接ＵＧにクエリを送信して、このＵＧ記憶する。ｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔは、クエリがＵＧＥＸＥの近傍で伝搬可能な残りの回数をカウントするための変数であり、例えば、デフォルト設定として３〜１０に設定されてもよく、この場合、他の値は、ＮＦＣとグローバル・ネットワーク使用量との間をてこ入れするために他の実施形態で使用することができる。
【００７１】
コピーされたクエリは、１ホップ減じられたｂｒｏａｄｃａｓｔ＿ｈｏｐ＿ｌｉｍｉｔを有する。隣接ＵＧが既にこのクエリをインストールしている場合、ＵＧＥＸＥはこのクエリを再度送信しない。隣接ＵＧがステップ３７６で発見されない場合、またはクエリがステップ３８０において隣接ＵＧにコピーされる場合、ＵＧＥＸＥは、ステップ３８２において、「より新しいレコードをチェックする」段階３６２に進む。
【００７２】
ステップ３８２において、ＵＧＥＸＥは、ＯＤに関する新しいレコードがオブジェクト・キャッシュにあるか否かをチェックする。新しいレコードがあれば、ＵＧＥＸＥはステップ３８４に進み、オブジェクト・レコードから推定オブジェクト・ロケーション情報（estimated object location）を取得し、ステップ３８６に進み、ここで、そのオブジェクト・ロケーションにあるか又はそのオブジェクト・ロケーションの付近にあるＵＧをＵＧレコードから取得する。したがって、新しいレコードがある場合、ＵＧＥＸＥは、最後に見られた位置を時間内に取得し、適切なＵＧＮＥＸＴをＵＧキャッシュから選択し、次いで新しいクエリをＵＧＮＥＸＴに送信する。
【００７３】
これに関して、ステップ３８８において、クエリが既にこのＵＧに送信されているか否かをチェックし、そうではない場合、クエリはステップ３９０において上記ＵＧにコピーされる。ステップ３８８において、カウンタｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔがあり、これは、クエリが新しいレコードにしたがって伝搬可能な残りの回数をカウントするために使用され、例えば、デフォルト設定として３〜１０に設定されてもよい。これは、ｂｒｏａｄｃａｓｔ＿ｈｏｐ＿ｌｉｍｉｔとは異なる値である。ステップ３９０において、クエリは新しいＵＧにコピーされ、ｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔは１減じられ、設定モードは「ヒット」モードに設定され、次いでクエリはＵＧに送信され、このＵＧは記憶される。この新しいクエリはｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔを減じ、上記情報を含有する「ヒット」モードに設定される。ｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔが０の場合、またはＵＧＮＥＸＴが既に開始クエリを有する場合、ＵＧＥＸＥはクエリを送信せず、ステップ３８８に続いてステップ３９８に進む。ＵＧＥＸＥは、ＵＧＮＥＸＴにクエリを送信した後でさえも、クエリの実行を継続する。
【００７４】
ステップ３８２で、オブジェクト・キャッシュに新しい関連したレコードがないことが判明した場合、ステップ３９２がステップ３８２に続く。ステップ３９２において、クエリが「ヒットなし」モードとして実行しているか否か、クエリが最初（第１）のループであるか否か、および依然として関連したレコードがないか否かがチェックされる。そうである場合、アルゴリズムは、ステップ３９４においてＵＧをランダムに選択して、減じたｒａｎｄｏｍ＿ｈｏｐ＿ｌｉｍｉｔで、コピーされたクエリをこのＵＧに転送する。そうでなければ、ステップ３９８がステップ３９２に続く。選択されたＵＧが関連したレコードを有さない場合、減じたｒａｎｄｏｍ＿ｈｏｐ＿ｌｉｍｉｔで、コピーされたクエリを別のランダムＵＧに転送する。したがって、「ヒットなし」モードのクエリは、関連したレコードが発見されるか、ｒａｎｄｏｍ＿ｈｏｐ＿ｌｉｍｉｔが０になるまで１つずつ転送される。このｒａｎｄｏｍ＿ｈｏｐ＿ｌｉｍｉｔはｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔとは異なる。これは、ランダム・ホッピングに使用されるだけであり、ランダム・ホッピング中、ｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔは減じられない。
【００７５】
クエリを受信するＵＧは、ＵＧＥＸＥとして作用し、同じフローを実行する。つまり、このオブジェクト・キャッシュおよびＵＧキャッシュをチェックしてから、新しいレコードがあれば、クエリを終了させる次のＵＧｎｅｘｔを選択する。各ＵＧＥＸＥは、クエリを送信したＵＧを記憶して、ＵＧＥＸＥをクエリにおける親として追加する。したがって、クエリのループを回避することができる。
【００７６】
ＯＤの新しいロケーション（位置）を知っているＵＧを追跡することによって、アルゴリズムは結果的にＯＤを発見することができる。ＯＤを発見するＵＧＥＸＥは、この成功をＵＧｏｒｉｇｉｎに通知する。可能ならば、ＵＧＥＸＥは、クエリ・キャンセルを、ＵＧＥＸＥがクエリを送信したＵＧに要求する。成功報告を受信した後、図３ａの比較ステップ３３８において、ＵＧｏｒｉｇｉｎは、成功をユーザに通知してから、ＵＧｏｒｉｇｉｎがクエリを送信したＵＧにクエリ・キャンセルについて要求を行う。次いで、クエリ・キャンセルを通知された各ＵＧＥＸＥは、ＵＧＥＸＥがクエリを送信したＵＧに再帰的にクエリ・キャンセルを問い合わせてから、このクエリを削除し、比較ステップは図３ａのステップ３５０で開始する。
【００７７】
各ＵＧは、オブジェクト位置およびこのＵＧ位置を推定するために、自身の位置を決定できる。このために、ＧＰＳだけでなくセルラーネットワークのセル情報も使用することができる。さらに、ＵＧがＧＰＳ機能を有さない場合、ＵＧ間でＧＰＳ情報を交換することによってより正確な位置を取得したり、三角測定を実行できる。加えて、ブルームフィルタ（Ｂｌｏｏｍ  Ｂ．Ｈ．「Ｓｐａｃｅ／Ｔｉｍｅ  Ｔｒａｄｅｏｆｆｓ  ｉｎ  Ｈａｓｈ  Ｃｏｄｉｎｇ  ｗｉｔｈ  Ａｌｌｏｗａｂｌｅ  Ｅｒｒｏｒｓ」：Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ｔｈｅ  ＡＣＭ，１３（７）：４２２−４２６；１９７０を参照）を使用することができる。ブルームフィルタは、要素が集合の数であるか否かをテストするために使用される空間効率のよい確率的データ構造である。各ＵＧは、特定のエリアおよび特定の時間スロットごとにブルームフィルタを準備することができ、キャッシュの余分なレコードは、ブルームフィルタに追加される。これによって、ＵＧＥＸＥは検索中のオブジェクトがある場所を推定し、ＵＧのランダム選択よりも高い、ＯＤについての関連したレコードを有するＵＧを選択する確率を取得することできる。
【００７８】
図４ａは、分散情報共有の基本的概念を図示している。図４ａは、３つのＵＧ４０５，４１０，４１５を示している。ＵＧ４０５、４１０および４１５の各々は、情報キャッシュ４２５，４３０，４３５を、例えばオブジェクト・キャッシュおよび／またはＵＧキャッシュとして有する。各ＵＧは、この近傍のオブジェクトに関するロケーション情報を受ける。情報キャッシュ４２５，４３０，４３５は、サイズが制限されている。上記例によると、これらは、特定の測定基準、例えば情報生成時間によって分類可能である。図４ａの矢印が示すように、情報キャッシュはＵＧ間に分散され、各ＵＧは差異のみを取得して、これによって、この近傍ＵＧからのデータを圧縮する。このデータを拡散するために、インデックスを周期的に近傍にブロードキャスティング（broadcasting）することができる。データを拡散するためにＮＦＣが使用されてもよく、データ拡散は、当然減衰される。実施形態は、したがって、情報ルーティングのホップ制限と関係ない場合もある。
【００７９】
上記実施形態によると、図４ｂは、オブジェクト・キャッシュ１３０およびＵＧキャッシュ１５０を備えるユビキタス・ゲートウェイ１００を図示している。ＵＧキャッシュ１５０は、情報生成時間によって分類されたＵＧロケーション情報を記録することができる。オブジェクト・キャッシュ１３０は、情報生成時間によって分類されたオブジェクト・ロケーション情報を記録することができる。
【００８０】
図４ｃは、３つのＵＧ，ＵＧ１，ＵＧ２と、ＵＧ３とを示す別のシナリオを図示している。図４ｃは、オブジェクト情報やレコードがＵＧ３からＵＧ２に伝搬されることを示し、これをさらにＵＧ１に転送することができる。ＵＧ３で見たオブジェクトは鍵および財布として図４ｃに例示されている。
【００８１】
別の例を提供するために、図４ｄは、ＵＧ−１がクエリをＵＧ−２に送信するシナリオを示している。ＵＧ−２は、それのオブジェクト・キャッシュをチェックして、検索オブジェクトｏｂｊ−１に関するレコードを発見し、上記オブジェクトが座標（ｘ１，ｙ１）にあったと判断する。さらに、ＵＧ−２は、このＵＧキャッシュをチェックし、ＵＧ−３が座標（ｘ１，ｙ１）に最も近かったことを発見する。結果として、ＵＧ−２はクエリを、例えばＷＬＡＮや３Ｇ（第３世代モバイル通信システム）を介して、新しいオブジェクト／ＵＧ記録時間でＵＧ−３に転送する。ＵＧ−３は、同じことをＵＧ−４に実行し、ＵＧ−４はまた同じことをＵＧ−５に実行し、そして最終的にオブジェクトｏｂｊ−１を発見して、ｏｂｊ−１情報についてＵＧ−１に応答する。ＵＧ−２が適切なＵＧを発見しなかった場合、ＵＧ−２は「失敗」と応答する。そしてＵＧ−１は、別のユーザを選択していた可能性もあり、例えば、ＵＧ−３、ＵＧ−４またはＵＧ−５は、クエリを拡張していた場合もある。
【００８２】
以下、上述のようにグローバル・クエリ・マネージャ（ＧＱＭ）と称される中央サーバを使用する第２の実施形態について説明する。ＧＱＭは、オブジェクトのより効率的な検索をサポートする。ＧＱＭは、例えば図１ｃまたは図２ａに図示されているような上記機構と同じオブジェクト・キャッシュを使用する。さらに、関連するＵＧはまた、図１ａおよび１ｂに従ったオブジェクト・キャッシュを備え、これを、隣接ＵＧと周期的に交換する。ここで説明している実施形態は、ＵＧキャッシュがＵＧに存在している必要がない点に注目すべきである。ＧＱＭは、例えば、基地局情報に基づいたＡＦＬＴ（高度転送三角測量）または非同期ハイブリッドポジショニングによって、例えば１００〜５００ｍの精度で抽象的なＵＧ位置を判断することができる。
【００８３】
ＧＱＭはまた、例えばＵＧにクエリをインストールする場合に、ＵＧからオンデマンドでレコードを取得することができる。さらに、ＧＱＭは、キャッシュ情報をＵＧから周期的に収集することは想定しておらず、さらに、ＵＧは、このキャッシュをＧＱＭに報告または更新することも想定していない。しかしながら、本実施形態では、ＧＱＭは、ＵＧからのレコードをオブジェクト・キャッシュに記憶する。一部の実施形態では、ＧＱＭはオブジェクト・キャッシュからの情報を使用して、クエリが開始される場合に特定のレコードがＧＱＭで既に使用可能であるということと、ＵＧが自身のオブジェクト・キャッシュを参照するに過ぎない場合に上記実施形態と比較してより効率的な検索を有することとを確率から取得することができる。
【００８４】
図５ａは、ＧＱＭの実施形態のフローチャートを示し、図５ａに表示されているステップは、クエリがインストールされていない場合でも常に実行することができる。このフローは、「Ａ」ともラベル付けされているステップ５０２から開始する。ステップ５０４がステップ５０２に続き、これは手続き的リターン・ポイントである。本実施形態では、ＧＱＭは次いで、ステップ５０６で開始し、かつステップ５１６で終了するループを実行する。ループ内では、ＧＱＭはこれに応じて、全てのインストール済みのクエリを実行することができる。まず、ステップ５０８において、ＧＱＭは２つのカウンタ、つまりｑｕｅｒｙ＿ｌｉｆｅｔｉｍｅおよびｒａｎｄｏｍ＿ｓａｍｐｌｅ＿ｐｅｒｉｏｄを増分し、これらは、オブジェクト・レコードが発見されない場合のクエリの有効期間（lifetime）と、ランダムにインストールされたクエリのカウンタとを判断する。これについては以下詳述する。ステップ５１０において、ＧＱＭは、有効期間カウンタが０に達しているか否か、つまりクエリの有効期間が過ぎたか否かをチェックする。クエリの有効期間が過ぎた場合、これはステップ５１０でチェックされるが、ＧＱＭはステップ５１２においてユーザに、クエリが失敗したことを通知する。ステップ５１２の通知後、クエリはステップ５１４で削除され、この後、ステップ５１６でループの終了になる。ステップ５１０においてクエリの有効期間が過ぎていない場合、つまりクエリが依然としてアライブである場合、ＧＱＭは、ステップ５１８でクエリ・プロセスを実行する。クエリ・プロセスの実行後、ステップ５１６でループの終了になる。ループは全クエリにわたって操作を行い、全クエリが実行された後、ＧＱＭは、ステップ５２０のリターン・ポイント「Ｂ」に戻る。
【００８５】
図５ａの右側に、２つのさらなるフローチャートが描かれ、これらは、クエリ成功またはクエリ・キャンセルが受信された場合の本実施形態のＧＱＭ挙動を図示している。
第１のプロセスは、ステップ５２２、つまり「Ｃ」で開始する。そして、第１のステップは、５２４であり、ここでは、クエリ成功またはキャンセルが受信される。クエリ成功またはキャンセルが受信されると、この結果がステップ５２６においてそれぞれのユーザに示されて、このクエリ・キャンセルはステップ５２８において、クエリが送信されたＵＧに転送される。次のステップ５３０において、クエリは削除され、これによって手順はステップ５３２で終了する。
【００８６】
図５ａの下部の右側に、この手順が、オブジェクト情報の新しいレコードが受信される場合のフローチャートとして描かれている。このフローはステップ５３４で開始し、ステップ５３６が続き、ここでは新しいレコードが受信される。新しいレコードが受信された場合、ステップ５３８において、このレコードはＧＱＭキャッシュ、つまりオブジェクト・キャッシュに追加される。手順は次にステップ５４０、つまり「Ｆ」で終了する。
【００８７】
図５ｂは、ＧＱＭがユーザからクエリを受信してクエリ・オブジェクトＯＤを検索する場合の手順の実施形態のフローチャートを示している。図５ｂに描かれているフローチャートは、３つの段階、つまり「ランダム・サンプリング」段階５４２と、「最新レコード追跡」段階５４４と、「クエリ・インストール」段階５４６とに再分割することができる。検索クエリ・プロセスは、ステップ５４８、つまり「Ｇ」で開始し、これにはステップ５５０が続き、ここでＧＱＭは、ＧＱＭオブジェクト・キャッシュにＯＤに関する新しいレコードがあるか否かをチェックし、この新しいレコードを、ターゲット・オブジェクトに関するレコードがあれば、パラメータｈｉｔ＿ｒｅｃｏｒｄに設定する。ＧＱＭが、例えば先行検索の結果を記憶する場合、ＧＱＭはこれを使用することができる。ステップ５５２において、レコードが使用可能であるか否かがチェックされる。ステップ５５４においてレコードが使用可能でない場合、カウンタｒａｎｄｏｍ＿ｓａｍｐｌｅ＿ｌｉｍｉｔがチェックされ、これは、新しいレコードを発見するためにランダムに選択されたＵＧの限度に達したか否かを判断する。限度に達していない場合、ステップ５５６がステップ５５４に続き、ここでＵＧはランダムに選択される。ＧＱＭキャッシュに関連するレコードがない場合、ＧＱＭはＵＧを選択し、このＵＧが関連するレコードを有するか否かをチェックする。基本的に、このＵＧはランダムに選択されるが、ＧＱＭもまたユーザの挙動パターンや先行検索結果に関する何らかの情報を事前に有していれば、ＧＱＭは、オブジェクトが発見され得る場所に関する最高尤度にしたがってすべての可能なＵＧをフィルタリングすることができる。
【００８８】
さらに、本実施形態では、２つのサンプリング限度、ｒａｎｄｏｍ＿ｓａｍｐｌｅ＿ｌｉｍｉｔおよびｓａｍｐｌｅ＿ｌｉｍｉｔがある。前者は、レコードが発見されない場合、つまり「ヒットなし」モードで使用され、後者は、レコードが発見された後、つまり「ヒット」モードで使用される。以下シミュレーションについて提示するが、この場合ｒａｎｄｏｍ＿ｓａｍｐｌｅ＿ｌｉｍｉｔは２０に設定され、ｓａｍｐｌｅ＿ｌｉｍｉｔは５０に設定されている。ステップ５６０においてｒａｎｄｏｍ＿ｉｎｓｔａｌｌ＿ｌｉｍｉｔがｒａｎｄｏｍ＿ｓａｍｐｌｅ＿ｌｉｍｉｔより大きい場合、ステップ５６２においてクエリが送信されて、「ヒットなし」モードでＵＧをランダムに選択し、ＵＧが記憶され、ｒａｎｄｏｍ＿ｉｎｓｔａｌｌ＿ｌｉｍｉｔが減じられる。
【００８９】
レコードが発見されない場合、カウンタｒａｎｄｏｍ＿ｓａｍｐｌｅ＿ｌｉｍｉｔが減じられ、別のＵＧがステップ５５６においてランダムに選択される。このランダム・サンプリングは、ＯＤに関するレコードが発見されるまで、あるいは、ステップ５５４において「ランダム・サンプリング」段階５４２がスキップされるようにｒａｎｄｏｍ＿ｓａｍｐｌｅ＿ｌｉｍｉｔが０になるまで継続される。ｒａｎｄｏｍ＿ｓａｍｐｌｅ＿ｌｉｍｉｔがステップ５６０においてｒａｎｄｏｍ＿ｉｎｓｔａｌｌ＿ｌｉｍｉｔ未満になると、この場合、ｒａｎｄｏｍ＿ｉｎｓｔａｌｌ＿ｌｉｍｉｔは「ヒットなし」モードでクエリ・インストールをカウントするために使用されるが、ＧＱＭは、ステップ５６２において、「ヒットなし」モードでクエリを選択されたＵＧに送信し、ｒａｎｄｏｍ＿ｉｎｓｔａｌｌ＿ｌｉｍｉｔを減じる。そしてこの手順はステップ５６４で終了する。
【００９０】
ステップ５５０でレコードが発見された場合、またはＧＱＭがＧＭＱキャッシュに古いレコードを有する場合、ＧＱＭは、ステップ５５２に続く新レコード追跡ファイル５４４を開始する。まず、ステップ５６６において、ＧＱＭは、発見されたヒットレコードが最後のヒットレコードより新しいか否か、そして最後のヒットレコードが全く存在していなかったか否かをチェックする。そうである場合、ステップ５６８において変数ｌａｓｔ＿ｈｉｔを現在のｈｉｔ＿ｒｅｃｏｒｄに設定し、ｈｉｔ＿ｒｅｃｏｒｄによって示されたターゲット・ロケーション（位置）で未インストールＵＧを選択し、ステップ５７０においてｌａｓｔ＿ｓｅｌｅｃｔｅｄ＿ＵＧをリセットする。ＧＱＭは、現在のｈｉｔ＿ｒｅｃｏｒｄが、ｌａｓｔ＿ｈｉｔと称される最後のループの先行レコードよりも新しいか否かをチェックする。第１のループにおいて、ｈｉｔ＿ｒｅｃｏｒｄは、ｌａｓｔ＿ｈｉｔがないため、より新しいはずである。次いで、ＧＱＭは、ｈｉｔ＿ｒｅｃｏｒｄから、最後に見られた位置を取得し、それぞれの位置に近くにありかつＯＤに関するクエリをまだインストールしていないＵＧをステップ５７０で選択する。ＧＱＭは、これらの選択されたＵＧをｌａｓｔ＿ｓｅｌｅｃｔｅｄ＿ＵＧとして記憶する。また、インストールされたクエリの限度に達したか否かをチェックするためにカウンタがステップ５７４において利用される。ステップ５７６において限度に達していない場合、ＧＱＭは、ターゲット・オブジェクトに関するレコードを取得しようと試み、上記カウンタ、つまりｓａｍｐｌｅ＿ｌｉｍｉｔを減じる。
【００９１】
ステップ５７８において、ＧＱＭは、レコードがｈｉｔ＿ｒｅｃｏｒｄより新しいか否かをチェックする。レコードがより新しくなければ、ステップ５７２で開始したループはステップ５８０で終了される。ステップ５７４において、サンプル限度に達したと判明すると、即座にステップ５８０が続く。ステップ５７８において、レコードがｈｉｔ＿ｒｅｃｏｒｄより新しいと判明すると、プロセスはステップ５８４にジャンプして、ここで、新しい方のレコードがＧＱＭキャッシュに記憶され、これにステップ５８６が続き、ここでプロセスは開始ポイントに戻る。ステップ５８２がステップ５８０に続き、これはまたプロセスの開始にジャンプして戻る。ＧＱＭは、選択されたＵＧがＯＤに関するより新しいレコードを有するか否かをチェックする。より新しいレコードが発見されれば、ＧＱＭはチェックを停止し、ステップ５８４において、このレコードをＧＱＭキャッシュに記憶し、開始ポイントに戻る。このようにしてより新しいレコードが１つずつ発見することができ、ＧＱＭは、常に最新のレコードを使用することができる。
【００９２】
新しいレコードが全くない場合、つまりステップ５６６において変数ｈｉｔ＿ｒｅｃｏｒｄが変数ｌａｓｔ＿ｈｉｔに等しい場合、ＧＱＭは「クエリ・インストール」段階５４６に進み、最近のレコードの位置付近のＵＧにクエリをインストールする。
【００９３】
ＧＱＭは次いでステップ５８８で開始し、ここでは、ＵＧが既に選択されているか否かがチェックされる。そうである場合、ステップ５９０において、未インストールＵＧが、レコードによって示されているターゲット・ロケーションで選択され、これらのＵＧは、変数ｌａｓｔ＿ｓｅｌｅｃｔｅｄ＿ＵＧに記憶される。ステップ５９２がこのステップに続き、ここでは、ＵＧが既に選択されていれば、最後に選択されたＵＧのうちのいくつかのＵＧが、ステップ５９０またはステップ５８８のいずれかに続いて選択される。ステップ５９２において、クエリは「ヒット」モードでこれらの選択されたＵＧに送信され、このＵＧは記憶され、それぞれｌａｓｔ＿ｓｅｌｅｃｔｅｄ＿ＵＧ変数でマークされる。ステップ５９４において、すべての選択されたＵＧは、ｌａｓｔ＿ｓｅｌｅｃｔｅｄ＿ＵＧで「インストール済み」とマークされる。言い換えると、ＧＱＭは、ｌａｓｔ＿ｓｅｌｅｃｔｅｄ＿ＵＧから全ＵＧまたは一部のＵＧを確率的に選択し、クエリをこれらにインストールする。クエリ自体は、別のカウンタｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔ（例えば、２に設定される）を利用してもよく、また「ヒット」モードに設定されてもよく、またレコード情報を含有することもある。ＧＱＭは次いでステップ５９４においてｌａｓｔ＿ｓｅｌｅｃｔｅｄ＿ＵＧの全ＵＧを「インストール済み」とマークし、最終的に、ステップ５９６においてｌａｓｔ＿ｓｅｌｅｃｔｅｄ＿ＵＧｓをクリアする。ＵＧをランダムに選択する理由は、これらは相互に近く、またＵＧは、セルラー接続を使用せずに、ＮＦＣを介して、平行してクエリをブロードキャストすることができるからである。
【００９４】
他の実施形態では、ランダム選択ではなく、例えば、ＧＱＭが別のＵＧをインストールする前にあるタイミングを使用して選択可能である。ＧＱＭは、次いで、ＵＧに関する隣接ＵＧ情報を取得可能であり、これらの隣接ＵＧの選択を回避できる。ＧＱＭは、そして、レコードによって示されている位置を常に監視でき、新しい未インストールＵＧがあれば、ＧＱＭはクエリを送信することができる。次いで、ステップ５６４がステップ５９６に続き、ここでプロセスは終了する。
【００９５】
より新しいレコードが報告されると、ステップ５３４〜５４０によって図５ａに説明されているように、ＧＱＭは、「最新レコード追跡」段階５４４と、「クエリ・インストール」段階５４６とを実行することができる。
【００９６】
一実施形態では、ＧＱＭは、常に、最新レコード周辺のオブジェクトを検索する。ＧＱＭはまた、オブジェクトが移動しているときに動作可能であるが、これは、オブジェクトが最も新しいレコードにすぐに従うことができるからである。さらなるオプションとして、ＧＱＭが最終検索の結果を知っており、またこれを、開始ポイントをランダムに選択するのではなく同一オブジェクトの検索用の開始ポイントとして使用する場合、より効率的な検索性能が得ることができる。そうでなければ、ＧＱＭが、ユーザの挙動パターンや先行の検索結果などに関する何らかの情報を事前に有する場合、ＧＱＭが、オブジェクトが発見され得る場所の最高尤度にしたがって全ての可能なＵＧをフィルタリングすることができる。
【００９７】
加えて、他の実施形態では、ブルームフィルタをオプションとして使用することができる。ＵＧは、次いで、余分なレコードをブルームフィルタに反映させることができ、ＧＱＭは、ＵＧのオブジェクト・キャッシュをチェックするのと同時にブルームフィルタを取得することができる。「ランダム・サンプリング」段階５４２において、ＯＤが存在し得る位置の範囲は制限されることもあるが、ブルームフィルタを収集する場合のより大きなネットワーク負荷の代償として、より良好な性能を得ることができる。
【００９８】
図６ａは、ＵＧで実行されるプロセスの実施形態のフローチャートを示している。このプロセスは、開始ポイント６００で開始し、リターン・ポイント６０２が続く。ステップ６０４において、変数ｆｏｕｎｄ＿ｏｂｊｅｃｔｓおよびｆｏｕｎｄ＿ＵＧｓがクリアされる。上記説明にしたがって、ステップ６０６において、カウンタ、つまりｏｂｊｅｃｔ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄがチェックされ、ステップ６０８においてカウンタが０の場合、隣接のオブジェクトについて、オブジェクト・キャッシュが更新されたことと、リスト変数、つまりｆｏｕｎｄ＿ｌｉｓｔが更新されたこととがチェックされる。さらに、ステップ６０８において、ｏｂｊｅｃｔ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄはリセットされる。それぞれステップ６０６またはステップ６０８に続いて、別のカウンタが、ＵＧチェックの期間が満了したか否か、つまりＵＧ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄについてチェックされる。そうである場合、ステップ６１２において、隣接ＵＧが監視されて、ＵＧキャッシュが、存在するのであれば、更新され、発見されたＵＧのリスト、つまりｆｏｕｎｄ＿ＵＧｓが維持される。
【００９９】
さらに、ＵＧ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄがリセットされる。以下のステップ６１４において、オブジェクト・キャッシュを隣接ＵＧと交換することができる。それぞれステップ６１０またはステップ６１４に続いて、ｏｂｊｅｃｔ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄおよびＵＧ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄｓがステップ６１６で減じられる。ステップ６１８で開始し、かつステップ６２８で終了するループがステップ６１６に続いている。このループ内で、ステップ６２０において、クエリ有効期間カウンタは減じられて、これにステップ６２２のクエリ有効期間チェックが続き、変数ｑｕｅｒｙ＿ｌｉｆｅｔｉｍｅが使用される。ステップ６２４においてクエリ有効期間が過ぎた場合、クエリは削除される。ステップ６２２においてｑｕｅｒｙ＿ｌｉｆｅｔｉｍｅが満了になっていないと判明すると、オブジェクト・クエリ検索およびクエリ・プロセスがステップ６２６で実行される。クエリ・ループはステップ６２８で終了する、つまりループは全インストール済みクエリについて動作する。プロセスは次いでステップ６３０で終了し、ここではリターン・ポイント６０２にジャンプして戻る。メインループを現在実行しているＵＧＥＸＥはステップ６０８にしたがって近傍のオブジェクトを周期的に観察する。さらに、このオブジェクト・キャッシュを更新し、発見されたオブジェクトを、アレイとして実現可能なｆｏｕｎｄ＿ｏｂｊｅｃｔｓに記憶する。この周期は値ｏｂｊｅｃｔ＿ｐｅｒｉｏｄによって決定され、これは、例えば１〜５分の周期に設定されてもよい。ＵＧＥＸＥは、次いで、この近傍のＵＧを周期的に観察し、これらを別のアレイ、例えばｆｏｕｎｄ＿ＵＧｓに記憶する。
【０１００】
ＵＧＥＸＥがＵＧキャッシュを有する場合、ＵＧＥＸＥはこれを更新することができる。この周期は値ＵＧ＿ｃｈｅｃｋ＿ｐｅｒｉｏｄによってカウント可能である。この期間中、ＵＧＥＸＥはまた、このオブジェクト・キャッシュおよびＵＧキャッシュを、ＮＦＣを介して隣接ＵＧと交換する。実施形態では、ＵＧＥＸＥは、キャッシュ全体を送信するのではなく、キャッシュの相違のみを送信することによってＮＦＣトラフィックを削減可能である。ＵＧＥＸＥは次いで、ステップ６１８と６２８間のループにしたがって全てのファイルクエリを実行することができる。ＵＧＥＸＥはステップ６２０においてまずクエリの有効期間をチェックする。有効期間が過ぎた場合、ＵＧＥＸＥはステップ６２４においてクエリを削除する。クエリが依然としてアライブである場合、ＵＧＥＸＥはステップ６２６でクエリ・プロセスを実行し、全クエリの実行後、ＵＧＥＸＥはポイント「Ｂ」、つまりステップ６０２に戻る。
【０１０１】
図６ａの右側に、ステップ６３２つまり開始ポイント「Ｄ」で開始するプロセスの実施形態の別のフローチャートがある。ステップ６３４において、ＵＧはクエリ・キャンセルを受信し、ステップ６３６が続き、ここでＵＧは、キャンセルされるクエリを送信した全ＵＧにクエリ・キャンセルを送信する。ステップ６３８において、ＵＧはクエリを削除し、これによってプロセスはステップ６４０つまり「Ｅ」で終了する。
【０１０２】
ＵＧＥＸＥがクエリを受信する場合、図６ｂのフローチャートによって描かれている実施形態にしたがってアルゴリズムを実行することができる。基本フローは、分散実施形態について上述されたＵＧフローとほとんど同じである。主要な相違点は、ＵＧが新しいレコードを発見した場合、ＵＧはこのレコードをＧＱＭに送信するのに対して、第１の実施形態ではＵＧは次の適切なＵＧを選択する点である。
【０１０３】
図６ｂに描かれているフローは２つの段階を備え、このうちの一方は、近傍のオブジェクトやＵＧを観察する「オブジェクトおよびＵＧチェック」段階６４４であり、もう一方は、ＵＧＥＸＥのオブジェクト・キャッシュにより新しいレコードがあるか否かをチェックし、かつこのレコードをＧＱＭに送信する「新レコードチェック」段階６４６である。
【０１０４】
より新しいレコードについて判断するための複数の基準がある。最も単純な基準は、レコードＲ１における情報生成時間Ｔ１が別のレコードＲ２における情報生成時間Ｔ２より新しいことであり、これはＴ１＞Ｔ２の場合、Ｒ１のほうが新しいことを意味している。もう１つの基準は、現在時−Ｔ１と等しい記録時期（record age）Ａ１が、現在時−Ｔ２に等しい別の記録時期Ａ２のレートαより小さいことであり、例えばα＝１／２の場合Ａ１＜αＡ２ならば、Ｒ１のほうが新しいことを意味している。実施形態では、時間依存的のみならず、距離依存的な別の基準もまた使用されてもよい。例えば、レコードＲ１の生成位置がＲ２の生成位置から離れている場合、新しさはＴ１＞Ｔ２によって比較されてもよく、そうでない場合はＡ１＜αＡ２によって比較される。以下の例において、基準Ｔ１＞Ｔ２が使用される。
【０１０５】
図６ｂに描かれているフローチャートは、ステップ６４２つまり「Ｆ」で開始する。「オブジェクトおよびＵＧチェック」段階６４４に進み、ステップ６４８において、ターゲット・オブジェクトが発見されたか否かがチェックされる。そうである場合、ステップ６５０において、クエリ発信元に成功が通知され、ステップ６５２においてクエリ・キャンセルが、クエリが転送されたＵＧに送信される。この後、ステップ６５４において、クエリを削除することができる。ターゲット・オブジェクトが発見された場合、ＵＧＥＸＥは成功をＧＱＭに通知してから、ステップ６５４において自身のクエリを削除する。可能ならば、ＵＧＥＸＥは、ＵＧがクエリを送信したか否かについて他のＵＧにクエリ・キャンセルを要求する。クエリが削除された後、プロセスはステップ６５２で終了して、ステップ６６８におけるクエリ終了にジャンプする。ターゲット・オブジェクトが発見されなかった場合、ＵＧが発見されたか否かについて、ステップ６５８においてチェックされる。オブジェクトは依然として発見されないが、隣接ＵＧが発見された場合、クエリモードが「ヒットなし」モードであるか否か、およびｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔ＝０、つまりクエリホップの最大数に既に達しているか否かがステップ６６０でチェックされる。
【０１０６】
そうではない場合、ステップ６６２において、クエリが隣接ＵＧにコピーされて、ホップ限度が減じられる。クエリは、クエリをインストールしていなかった隣接ＵＧに送信され、上記ＵＧは記憶される。ステップ６６０においてクエリモードが「ヒット」モードの場合、ｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔに既に達し、ステップ６６２はスキップされ、クエリはコピーされない。隣接ＵＧがステップ６５８で発見されない場合、新レコードチェック段階６４６がすぐに終了され、ステップ６６０および６６２に続く。クエリ・オブジェクトは発見されないが、隣接ＵＧがある場合、クエリが「ヒット」モードであり、かつｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔが１より大きければ、ＵＧＥＸＥはクエリをこれらのＵＧにコピーする。ｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔは、クエリが伝搬可能な残りの回数をカウントするための変数であり、これはＧＱＭによって設定されることもあり、例えばｑｕｅｒｙ＿ｈｏｐ＿ｌｉｍｉｔ＝３である。隣接ＵＧが既にこのクエリをインストールしている場合、ＵＧＥＸＥはクエリを再度送信しない。
【０１０７】
ＵＧＥＸＥは次いで「新レコードチェック」段階６４６に進む。ステップ６６４において、ＵＧＥＸＥは、ＯＤに関する新レコードがオブジェクト・キャッシュにあるか否かをチェックする。新しいレコードがある場合、ＵＧＥＸＥは、ステップ６６６において、このレコードをＧＱＭに報告する。ＵＧＥＸＥからこのレコードを受信した後、ＧＱＭは、図５ａのステップ５３４〜ステップ５４０にしたがって、これをＧＱＭにおけるオブジェクト・キャッシュに反映する。ＧＱＭは次いで、図５ｂの「最新レコード追跡」段階５４４およびクエリ・インストール段階５４６を実行する。
【０１０８】
ＧＱＭが検索の成功をＵＧから受信すると、各ＵＧＥＸＥはＧＱＭからのクエリをキャンセルするよう要求される。ＵＧＥＸＥがこのクエリを他のＵＧに送信していれば、クエリ・キャンセルをこれらのＵＧに再帰的に要求し、その後、図６ａのステップ６３２〜６４０にしたがって自身のクエリを削除する。図６ｂによると、新レコードチェック段階６４６は次いでステップ６６８で実行されて、ここでプロセスは終了する。
【０１０９】
上記第２の実施形態のオプションとして、各ＵＧはまたＵＧキャッシュを有することができる。この場合、ＧＱＭは、クエリ・オブジェクトの最後に見られた位置の周辺にある適切なＵＧを選択するためにＵＧキャッシュを使用することができる。ＧＱＭが、最後に見られた位置の付近にあるＵＧを選択する場合、ＧＱＭは通常通りセル情報を使用するが、これは約１００〜５００ｍの精度を有することもある。これに代わって、ＧＱＭは、最後に見られた位置の付近にあるいくつかのＵＧからＵＧキャッシュの情報を取得して、ＵＧをこの位置に近づけることができる。これによって、本実施形態はより効率的になる。
【０１１０】
図７ａは、第２の実施形態を図示している。図７の左側にＵＧ７０２の実施形態があり、ここでのスケッチは、ＵＧキャッシュが必要とされていないことを示している。図７ａの右側には、クエリ・ステータスをコントロールするＧＱＭ７０４の実施形態がある。ＧＱＭは、ネットワーク７０６に接続され、図７ａにおいては、ＵＧ７０２は、中央で重複されている。ネットワークは複数のセル７０８を備える。ＧＱＭ７０４は、セル情報から算出されたＵＧロケーション情報を知っており、ＵＧ７０２はしたがって、ＵＧキャッシュを有する必要はない。
【０１１１】
図７ｂは、別の実施形態を示している。図７ｂは、ＧＱＭ７１０と多数のＵＧ７１２，７１４，７１６，７１８とを示している。ＵＧの各々は、最後に見られたオブジェクト情報を含有するオブジェクト・キャッシュを有する。この情報を使用して、ＧＱＭ７１０は、ランダム・クエリ・インストールと比較して、クエリ数を削減し、かつ検索時間を短縮することができる。例えば、図７ｂに描かれているシナリオにおいて、ＧＱＭ７１０は、ＵＧ７１２に、矢印７２１でシンボル化されているオブジェクトＯ１を見たか否かを問い合わせることができる。次いで、ＵＧ７１２は、矢印７２２で示された位置（ｘ１，ｙ１）でＯ１を見たことを報告することができる。この報告から、ＧＱＭ７１０は、Ｏ１の推定位置を結論付けることが可能であり、したがってＵＧ７１６を選択して、オブジェクトＯ１に関するより新しい情報が矢印７２３によって示されているように使用可能であるか否かを要求することができる。矢印７２４は次いで、オブジェクトＯ１が見られたことを示すＵＧ７１６からの応答を示しているが、新しい情報は使用可能ではない。ＧＱＭ７１０は次いで、図７ｂの小矢印７２５にしたがって（ｘ１，ｙ１）周辺に集中的にクエリをインストールする。ＵＧ７１４、７１６および７１８は、次にオブジェクトＯ１に活発にクエリを実行する。
【０１１２】
図８は、別の実施形態を示している。図８は、例えば３Ｇモバイル通信ネットワークを介して、ＵＧ８０２がクエリをグローバル・クエリ・マネージャ８０４に送信するシナリオを示している。グローバル・クエリ・マネージャ８０４は、クエリが行われたオブジェクトに関するより新しいレコードをオブジェクト・キャッシュから取得することを試み、このレコードが示しているロケーション（位置）に近いＵＧを取得する。これらのＵＧは、図８のネットワーク８０６内に示されている。このロケーションの近くにＵＧがない場合、ＵＧはランダムに選択される。クエリが行われたオブジェクトに関する新しいレコードがない場合、ＧＱＭは、最新のレコードが示すロケーションの近くのＵＧにクエリをインストールする。これは、図８のネットワーク８０６内にラベル「クエリ」によって示されている。描かれている例においては、クエリはＵＧ８０８，８１０，８１２，８１４にインストールされる。これらのＵＧは、ランダムに選択されてもよく、ＧＱＭ８０４は、クエリ・オブジェクトに関するレコードを要求することができる。
【０１１３】
好ましくは、ＵＧは、最後に見られた位置で選択されることもあり、またより新しいレコードを要求されることもある。ＵＧは次いで、新しいレコードを報告し、ＵＧは、他のより新しいレコードが発見されなくなるまで、再帰的に選択可能である。これは、クエリ・インストールが開始可能であり、かつ既知のＵＧが最後に見られた位置の付近にある新しいＵＧについてチェック可能である場合である。新しいＵＧは、ＧＱＭ８０４に報告するより新しいレコードについて要求され、次いでダイレクト・クエリをインストールすることができる。すべての質問されたＵＧはこのクエリを低いホップ限度でＮＦＣを介して周期的にブロードキャストすることができる。結果的に、クエリ・オブジェクトは発見される。
【０１１４】
以下、ローカル・ドメインにおける５つの手法についてのシミュレーション結果が提示される。この５つの手法とは「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ａｌｌ（全てへの単純クエリ）」、「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ（ランダムの単純クエリ）」（ローカル・ドメインについてＣ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｉｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒによって使用されている手法）、「第１の手法」とも称される第１の実施形態、「第２の手法」とも称される第２の実施形態、およびＬＥＲである。
【０１１５】
「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ」手法は、上記論文における手法のデフォルト設定であるローカル・ドメインにおけるＵＧの４０％にクエリをインストールしている。各手法は、以下のデフォルト条件でシミュレートされる。ＵＧとは、例えば第３世代モバイル通信であるグローバル接続性およびＮＦＣ接続性の能力を有する携帯電話を表す。ＵＧのＮＦＣ範囲は１０ｍであるとされ、ＮＦＣを介するキャッシュ交換周波数は１／６０［１／秒］である。ＵＧのセンサ範囲は１０ｍであり、１／６０［１／秒］の周波数で検知する。シミュレートされたエリアは１ｋｍ×１ｋｍ、つまり１ｋｍ２である。オブジェクトの密度はオブジェクト８００個／ｋｍ２であり、オブジェクトはデフォルトによって移動していない。ＵＧ密度はノード４００個／ｋｍ２である。
【０１１６】
ＵＧの移動モデルはランダムウォークである。ＵＧ移動の方向はランダムに選択され、移動速度は１ｍ／秒であり、移動期間は１００秒である。移動後の待機期間はデフォルトによって０秒である。ＵＧは、１０ｍの位置誤差でＧＰＳによって自身の位置を判断可能であり、ＧＱＭは、１００ｍの位置誤差でセルラー情報によってＵＧの位置を判断可能である。ＵＧのオブジェクト・キャッシュのサイズは２００であり、ＵＧのＵＧキャッシュのサイズもまた２００である。異なる表記がなされなければ、１００個のクエリが各シミュレーション・シナリオで発行されたことになる。各シナリオは複数回シミュレートされている。
【０１１７】
図９は、平均クエリ成功時間（秒）対ＵＧ密度のシミュレーション結果を表示するグラフを示している。図９は、５０〜８００のＵＧ密度の変動でクエリの応答成功にかかる平均時間を示している。参照として、Ｃ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｉｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒが、およそＵＧ５００個／ｋｍ２の場合のクエリ成功に関する良好な操作を報告していることに注目すべきである。これは、それぞれ第１および第２の実施形態において６分および２．５分の平均検索時間をもたらす。第１および第２の実施形態は、図９の符号で第１および第２の手法によって示されている。平均クエリ成功時間に関する手法を比較すると、順位は「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ａｌｌ（全てへの単純クエリ）」＜「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ（ランダムの単純クエリ）」＜第２の手法＜第１の手法＜ＬＥＲである。しかしながら、「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ａｌｌ」および「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ」は、図１０に示されているようなより大きなネットワーク負荷につながる。図９に関して、第２の実施形態は「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ」とほぼ同じ成功時間を達成可能であり、他の手法と比較してかなり小さな負荷がグローバル・ネットワークにかかることが分かる。
【０１１８】
図１０および１１は、グローバル・ネットワークおよびＮＦＣにかけられるネットワーク負荷を示している。図１０はグローバル・ネットワーク使用量を示し、図１１は、ＮＦＣ使用量対ＵＧ密度を示している。図１０から分かるように、グローバル・ネットワークのネットワーク負荷に関する手法を比較する場合、順位は最下位のＬＥＲ、次いで第２の実施形態、第１の実施形態、次いで「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ」、そして最後に「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ａｌｌ」である。したがって、第１および第２の実施形態は多量のグローバル・ネットワーク負荷をセーブし、依然として短い平均成功時間を保つことができる。ＬＥＲはグローバル・ネットワークをそれ程多くは使用しないが、図９に示されているようにかなり長いクエリ成功時間を有する。
【０１１９】
図１１から分かるように、ＬＥＲおよび第１の実施形態は最高のＮＦＣ使用量を利用する。第２の実施形態は、グローバル・ネットワークへの負荷を削減するために第２の通信手段やＮＦＣを利用する。ＮＦＣは、それぞれモバイル・デバイス間およびＵＧ間で通信するために第１および第２の実施形態で使用される。「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ａｌｌ」および「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ」はＮＦＣを全く使用しない。図１１は、クエリを直接サポートするためのＮＦＣ転送メッセージを示しているが、周期的に交換されたメッセージについては示していない。
【０１２０】
図１２は、ＮＦＣ使用量対ＵＧ密度を示している。平均システムクエリ周波数は１時間当たりクエリ１０００個である。ここで、キャッシュからの周期的に交換されたメッセージ、つまり検索メッセージが含まれている。１時間あたりの周期的に交換されたメッセージの一部は一定であり、つまりＵＧ１つにつき１時間当たり６０回であり、これは３６００ｓ／６０ｓ交換周期によって算出される。
【０１２１】
一部の実施形態では、ＮＦＣコストがグローバル・ネットワーク・コストよりも安いと想定可能である。これは、例えば、コストが、コスト測定基準としてのバッテリー電力消費に基づいている場合である。ＮＦＣの平均電力消費は、例えば１０ｍＷ〜５０ｍＷの場合もあり、通常の値が例えば１Ｗであるグローバル・セルラー・ネットワークよりも数倍低い可能性がある。加えて、ＮＦＣはユーザが自由に使用可能である。
【０１２２】
この点から、特に第２の実施形態つまり第２の手法は、グローバル・ネットワーク負荷を削減して、短期間で良好な成功を得るには非常に有用である。第１の実施形態つまり第１の手法はそれ程良好ではないが、依然として使用可能であり、これは中央サーバを伴っていないため、誰もがこれを配備することができる。したがって、第１および第２の実施形態は異なるシナリオで利点があり得る。
【０１２３】
図１３は、平均クエリ成功時間対オブジェクト密度を示している。オブジェクト密度は１００〜３２００で変化する。図１３は、第１および第２の手法、つまりそれぞれの実施形態の予想平均クエリ成功時間がオブジェクト密度に伴って増大することを示している。これは、ＵＧにおけるオブジェクト・キャッシュの制限によってもたらされる。実施形態をさらに改良するために、このボトルネックは、観察されたオブジェクト数に応じてオブジェクト・キャッシュのサイズを動的に変更することによって回避可能である。
【０１２４】
図１４は、ＵＧにおける平均クエリ成功時間対オブジェクト・キャッシュサイズを示し、ここでオブジェクト・キャッシュサイズは２５〜８００で変化する。図１４から、オブジェクト・キャッシュのサイズが、特定の値が設定された後のクエリ成功時間を改善しないこともある点が観察される。図１４において、例えば、２００のキャッシュサイズは、ＵＧ４０００個／ｋｍ２およびオブジェクト８００個／ｋｍ２のシナリオには十分である。
【０１２５】
図１５は、平均クエリ成功時間対オブジェクト移動レート（％）に対するシミュレーション結果を示している。オブジェクトを移動させるための平均クエリ成功時間が評価されている。シミュレーションにおいて、オブジェクトはランダムウォークによって移動し、これは、各ＵＧがランダム角度、固定速度、固定ウォーキング周期、およびウォーキング後の非待機周期を判断することを意味している。シミュレーションにおいて、この結果は図１５に示され、速度は１ｍ／ｓに設定され、ウォーキング周期は１００ｓに設定され、待機周期は０ｓに設定されている。図１５は、０〜１００％でそれぞれ移動するオブジェクトのレートを変更することによる結果を示している。このような厳しい条件下では、第１および第２の実施形態は依然として、ＬＥＲよりもかなり短い成功時間およびこれより少ないグローバル・ネットワーク使用量を得ることができる。また両実施形態は、オブジェクトが移動している時にも非常に安定している。
【０１２６】
基本的に、第１および第２の手法、つまりそれぞれの実施形態の性能に影響を与える２つの要因がある。１つは、非常に多くのオブジェクトが移動している場合にはオブジェクト・キャッシュのタイムラインが悪くなるという観測結果である。もう１つは、多数のオブジェクトが移動するのに伴ってＵＧは新しいオブジェクトのオブジェクト・レコードをより迅速にキャッシュ可能であるという観測結果である。第１の実施形態は、提示されているシミュレーションに使用されているシミュレーションパラメータ設定によって両方の要因のバランスをとることができる。第２の実施形態について、第１の要因は、使用されているシミュレーションパラメータ設定について、第２の要因より強力である。
【０１２７】
上記シミュレーション結果から、実施形態はＬＥＲよりかなり良好である。第２の実施形態は、より小さいグローバル・ネットワーク負荷で、「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ」とほぼ同じ成功時間を達成することができる。
【０１２８】
本明細書に提示されているシミュレーション結果は、かなり慎重なシミュレーション推定によって実行されたことに注目すべきである。例えば、ここに提示されているシミュレーションは、低ＵＧ密度、つまりＵＧ４００個／ｋｍ２で実行されたのに対して、実世界シナリオでは、例えばＣ．Ｆｒａｎｋ、Ｐ．Ｂｏｌｌｉｇｅｒ、Ｆ．ＭａｔｔｅｒｎおよびＷ．Ｋｅｌｌｅｒｅｒによって提示されているように、より高いＵＧ密度が生じる。さらに、ランダムウォークは最悪の場合のウォーキングモデルの一種である。実世界では、一部のＵＧは安定し、めったに移動せず、またウォークウェイ（移動の仕方）は、例えば道路によって制限される。したがって、例えば本発明の実施形態について、かなり良好な結果が実世界で予想することができる。
【０１２９】
図１６は、バッテリー消費対ＵＧ密度のシミュレーション結果を表示する。バッテリー消費は、ＮＦＣネットワーク・メッセージに対する６０ｍＷ／ｓおよびグローバル・ネットワーク・メッセージに対する８００ｍＷ／ｓである測定基準によって評価される。図１６に表示されているシミュレーション結果において、１時間当たり１０００個のクエリが生じることがさらに想定されている。図１６から、第１および第２の実施形態、つまりそれぞれ第１および第２の手法は「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ａｌｌ」および「Ｓｉｍｐｌｅ  Ｑｕｅｒｙ  ｔｏ  Ｒａｎｄｏｍ」の機能をしのぐことが分かる。これらの条件下で、第２の実施形態は、ＬＥＲとほぼ同じくらい小さいバッテリー消費を達成する。第１の実施形態では、バッテリー消費は、第２の実施形態よりわずかに大きい。
【０１３０】
上記シミュレーション結果は、第１および第２の実施形態が成功時間ならびにネットワークコストを削減可能であることを示していた。したがって、本発明の実施形態は、バッテリー寿命が、オブジェクトに質問する場合にＵＧで延長可能であるという利点がある。
【０１３１】
別の実施形態では、ＵＧは、第１の実施形態と第２の実施形態では変化する場合がある。つまり、ＵＧは、残りのバッテリー寿命がかなり短い場合は第１の実施形態にしたがって分散クエリを開始し、より長いバッテリー寿命が使用可能な場合はグローバル・クエリ・マネージャを伴う第２の実施形態を使用する。さらに、オブジェクトはまた、人物、モバイル・デバイスによって提供されるサービス、モバイル・アドホック・ネットワークにおけるＩＰアドレスなどの識別子などの実世界情報を備えてもよい。したがって、実施形態はまた情報共有システムに関与することもあり、この場合情報は動的に共有することができる。
【０１３２】
本発明の方法の特定の具現化要件に応じて、本発明の方法はハードウェアまたはソフトウェアで具現化可能である。この具現化は、ディジタル記憶媒体、特に電子的に読み取り可能なコントロール信号を記憶しているフラッシュメモリ、ディスク、ＣＤまたはＤＶＤを使用して実行可能であり、これらは、本発明の方法が実行されるようにプログラマブルコンピュータシステムと共働する。概して、本発明は、したがって、機械可読キャリアに記憶されているプログラムコードを備えるコンピュータプログラムであり、このプログラムコードは、コンピュータプログラムがコンピュータで動作する場合に本発明の方法を実行するために動作する。言い換えると、本発明の方法はしたがって、コンピュータプログラムがコンピュータで動作する場合に本発明の方法のうちの少なくとも１つを実行するプログラムコードを有するコンピュータプログラムである。
【符号の説明】
【０１３３】
１００  ユビキタス・ゲートウェイ
１１０  第１の通信手段
１２０  第２の通信手段
１３０  オブジェクト・キャッシュ
１４０  コントローラ
１５０  ユビキタス・ゲートウェイ・キャッシュ
１６０  グローバル・クエリ・マネージャ
１７０  通信手段
１８０  オブジェクト・キャッシュ
１９０  コントローラ
７０２  ユビキタス・ゲートウェイ
７０４  ＧＱＭ
７０６  モバイル通信ネットワーク
７０８  モバイル通信ネットワークのセル
７１０  ＧＱＭ
７１２  ユビキタス・ゲートウェイ
７１４  ユビキタス・ゲートウェイ
７１６  ユビキタス・ゲートウェイ
７１８  ユビキタス・ゲートウェイ
７２１  オブジェクトＯ１を知っているか？
７２２  オブジェクトＯ１が位置ｘ１，ｙ１にあったことを知っている
７２３  オブジェクトＯ１に関するより新しい情報を知っているか？
７２４  知っているが、新しい情報ではありません
７２５  ＧＱＭがｘ１，ｙ１付近に集中的にクエリをインストールする
８０２  ユビキタス・ゲートウェイ
８０４  ＧＱＭ
８０６  モバイル通信ネットワーク
８０８  クエリＵＧ
８１０  クエリＵＧ
８１２  クエリＵＧ
８１４  クエリＵＧ 
【図１ａ】
0005039069.tif 000002
【図１ｂ】
0005039069.tif 000003
【図１ｃ】
0005039069.tif 000004
【図２ａ】
0005039069.tif 000005
【図２ｂ】
0005039069.tif 000006
【図３ａ】
0005039069.tif 000007
【図３ｂ】
0005039069.tif 000008
【図４ａ】
0005039069.tif 000009
【図４ｂ】
0005039069.tif 000010
【図４ｃ】
0005039069.tif 000011
【図４ｄ】
0005039069.tif 000012
【図５ａ】
0005039069.tif 000013
【図５ｂ】
0005039069.tif 000014
【図６ａ】
0005039069.tif 000015
【図６ｂ】
0005039069.tif 000016
【図７ａ】
0005039069.tif 000017
【図７ｂ】
0005039069.tif 000018
【図８】
0005039069.tif 000019
【図９】
0005039069.tif 000020
【図１０】
0005039069.tif 000021
【図１１】
0005039069.tif 000022
【図１２】
0005039069.tif 000023
【図１３】
0005039069.tif 000024
【図１４】
0005039069.tif 000025
【図１５】
0005039069.tif 000026
【図１６】
0005039069.tif 000027
【図１７】
0005039069.tif 000028
【図１８】
0005039069.tif 000029
【図１９】
0005039069.tif 000030