(57)【要約】アラート系通信サービスを提供するシステムであって、当該サービスに関し、移動局によって満たされることになるアラート条件が定義されている。このシステムは、移動局に関連するロケーション・データが、アラート系の通信サービスに対応するアラート条件をその移動局が満たしていることを示す場合に、そのアラート系の通信サービスに関連するアラート発射を行うことができるアラート・エンジンを備える。また要求エンジンが備わっており、少なくとも１つのアラート条件が特定の移動局によって満たされる、予期される最も早い将来の時を決定し、その予期される最も早い将来の時に先行してその特定の移動局に関する更新済みロケーション・データを獲得するべく要求を示すデータ・エレメントを出力する。さらに、それぞれのロケーション要求に関連する複数の満了時間を示す満了時間データを受け取り、それらの満了時間を処理して、ロケーション要求の満了時間を少なくとも部分的に基礎としてポジション決定装置（ＰＤＥ）によってロケーション要求のサービス提供が行われる順序を決定するスケジューラ、およびＰＤＥとインターフェースし、それによる、決定された順序に従ってロケーション要求のサービス提供を可能にする出力が備わっている。【選択図】図１
2004535744.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータが方法を実施するために実行可能な指示プログラムを含むコンピュータ可読メディアであって、前記コンピュータは、移動局によって満たされるべきアラート条件が定義されているアラート系サービスを提供するようなされた通信ネットワークに接続であり、前記方法は：
・少なくとも１つのアラート条件が特定の移動局によって満たされる、予期される最も早い将来の時を決定すること；および、
・前記予期される最も早い将来の時に先だって前記特定移動局に関する更新済みロケーション・データの取得要求を表すデータ・エレメントを出力すること；
から成る、コンピュータ可読メディア。
【請求項２】
前記予期される最も早い将来の時を決定することが：
・前記特定移動局の最後の既知ロケーションと、前記少なくとも１つのアラート条件に関連付けられた目標ロケーションとの間の最小移動時間を推定すること；
から成る請求項１に記載のコンピュータ可読メディア。
【請求項３】
前記特定移動局の最後の既知ロケーションと、前記目標ロケーションとの間の最小移動時間を推定することが：
・前記特定移動局の最後の既知ロケーションと、前記目標ロケーションとの間の距離を決定することと；
・前記特定移動局の速度を決定することと；
・前記距離と前記速度の商を演算し、前記特定移動局の前記最後の既知ロケーションと、前記目標ロケーションとの間の推定最小移動時間を獲得することと；
から成る請求項２に記載のコンピュータ可読メディア。
【請求項４】
前記速度が瞬時速度である、請求項３に記載のコンピュータ可読メディア。
【請求項５】
前記速度が、時間区間内における平均速度である、請求項３に記載のコンピュータ可読メディア。
【請求項６】
前記速度が、瞬時速度と時間区間内における平均速度のうちの大きい方である、請求項３に記載のコンピュータ可読メディア。
【請求項７】
前記特定移動局の最後の既知ロケーションと、前記目標ロケーションとの間の最小移動時間を推定することが：
・前記特定移動局の最後の既知ロケーションから前記目標ロケーションまでの、現存する道路に基づく最短経路を決定すること；および、
・前記最短経路の移動に必要な最小時間を決定すること；
から成る請求項２に記載のコンピュータ可読メディア。
【請求項８】
前記方法が、さらに：
・現在時以前の、前記特定移動局に関する更新済みロケーション・データの取得要求を示す第２のデータ・エレメントを出力すること；
を含む請求項１に記載のコンピュータ可読メディア。
【請求項９】
さらに前記方法が：
・過去における所定時点以前の、前記特定移動局に関する更新済みロケーション・データの取得要求を示す第２のデータ・エレメントを出力すること；
を含む請求項１に記載のコンピュータ可読メディア。
【請求項１０】
前記方法が更に：
・将来における所定時点以前の、前記特定移動局に関する更新済みロケーション・データの取得要求を示す第２のデータ・エレメントを出力すること；
を含む請求項１に記載のコンピュータ可読メディア。
【請求項１１】
さらに前記方法が：
・前記特定移動局に関するロケーション・データを受け取ること；を含み、
・前記決定ステップおよび前記出力ステップが、前記受け取りステップの後に実行される、請求項１に記載のコンピュータ可読メディア。
【請求項１２】
前記方法が更に：
・前記受け取りステップ、前記決定ステップ、および前記出力ステップを反復的に実行すること；
を含む請求項１１に記載のコンピュータ可読メディア。
【請求項１３】
前記特定移動局によって少なくとも１つのアラート条件が満たされる、予期される最も早い将来の時を決定することが、複数のアラート条件のいずれかが前記特定移動局によって満たされる、予期される最も早い将来の時を決定することを含む請求項１に記載のコンピュータ可読メディア。
【請求項１４】
前記予期される最も早い将来の時を決定することが；
・前記特定移動局の最後の既知ロケーションと、複数のアラート条件に関連する複数の目標ロケーションのうちのもっとも近い目標ロケーションとの間における最小移動時間を推定すること；
を含む請求項１に記載のコンピュータ可読メディア。
【請求項１５】
前記予期される最も早い将来の時を決定することが；
・前記予期される最も早い将来の時が最小となったアラート条件に関して、新しい予期される最も早い将来の時を見つけ出すこと；
・そのほかのすべてのアラート条件について、そのアラート条件に関する前記予期される最も早い将来の時が前記新しい予期される最も早い将来の時より前になるときは、第２の新しい予期される最も早い将来の時を演算し、前記新しい予期される最も早い将来の時および前記第２の新しい予期される最も早い将来の時のうちの小さい方に等しく前記新しい予期される最も早い将来の時を設定すること；
を含む請求項１に記載のピュータ可読メディア。
【請求項１６】
複数の移動局および各種アラート条件について定義がなされたアラート系サービスを提供するようなされた通信ネットワークにおいて使用する方法であって：
・特定の移動局によって少なくとも１つのアラート条件が満たされる、予期される最も早い将来の時を決定すること；および、
・前記予期される最も早い将来の時に先行して前記特定移動局に関する更新済みロケーション・データの取得要求を示すデータ・エレメントを出力すること；
を含む方法。
【請求項１７】
複数の移動局および各種のアラート条件について定義がなされたアラート系サービスを提供するようなされた通信ネットワークにおいて使用するシステムであって：
・特定の移動局によって少なくとも１つのアラート条件が満たされる、予期される最も早い将来の時を決定する手段；および、
・前記予期される最も早い将来の時に先行して前記特定移動局に関する更新済みロケーション・データの取得要求を示すデータ・エレメントを出力するための手段；
を備えるシステム。
【請求項１８】
複数の移動局および各種のアラート条件に関する定義がなされたアラート系サービスを提供するようなされた通信ネットワークにおける方法を具現化するコンピュータによる実行のためのプログラム・エレメントを含むコンピュータ可読ストレージ・メディアであって、前記プログラム・エレメントが：
・特定の移動局によって少なくとも１つのアラート条件が満たされる、予期される最も早い将来の時を決定するプログラム・コード手段；および、
・前記予期される最も早い将来の時に先行して前記特定移動局に関する更新済みロケーション・データの取得要求を示すデータ・エレメントを出力するためのプログラム・コード手段；
を含む、コンピュータ可読ストレージ・メディア。
【請求項１９】
移動局によって満たされることになる対応アラート条件が定義されているアラート系サービスを提供するようなされた通信ネットワークにおいて使用するデータ処理装置であって：
・前記移動局に関する更新済みロケーション・データを受け取り可能な入力；および、
・前記入力に接続される処理ユニットから成り、前記処理ユニットは：
・特定の移動局に関する前記更新済みロケーション・データを基礎として、いずれのアラート系サービスに関して少なくとも１つの対応するアラート条件が前記特定移動局によって満たされているかについて、それが存在する場合にはその決定を行うことが可能であり；かつ、
・少なくとも１つの対応するアラート条件が前記特定移動局によって満たされた各アラート系サービスに関連付けされたアラートを発射するトリガを生成することが可能である、
データ処理装置。
【請求項２０】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、所定の将来時において目標ロケーションから所定の最大距離内に前記特定移動局が見つけられることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項２１】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、所定の時間範囲の間に目標ロケーションから所定の最大距離内に前記特定移動局が見つけられることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項２２】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、所定の目標の地理的エリアに前記特定移動局が入ったことを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項２３】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、所定の目標の地理的エリアから前記特定移動局が出たことを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項２４】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、所定時において、所定目標の地理的エリア内に前記特定移動局が見つけられることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項２５】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、所定時において、所定目標の地理的エリア外に前記特定移動局が見つけられることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項２６】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、所定時間にわたって、所定目標の地理的エリア内に前記特定移動局が見つけられることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項２７】
前記所定時間を、所定の連続する回数の更新済みロケーション・データが前記入力において受け取られる請求項２６に記載のデータ処理装置。
【請求項２８】
前記所定時間を、所定の長さの時間とする請求項２６に記載のデータ処理装置。
【請求項２９】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、対応する所定時間にわたって、中心の目標ロケーションに相対的な複数の漸増的な周辺の目標の地理的エリアの１つ内に前記特定移動局が見つけられることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項３０】
前記周辺の目標の地理的エリアに対応する所定時間は、その周辺の目標の地理的エリアが、前記中心の目標ロケーションに対して周辺となる程度に直接関連する請求項２９に記載の装置。
【請求項３１】
前記周辺の目標の地理的エリアに対応する所定時間は、前記更新済みロケーション・データによって前記移動局が前記周辺の目標の地理的エリア内にあることが示される回数であって、所定の連続する回数として定義される請求項３０に記載の装置。
【請求項３２】
前記周辺の目標の地理的エリアに対応する所定時間は、所定の長さの時間として定義される請求項３０に記載の装置。
【請求項３３】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、特定の方向または場所へ前記特定移動局が向かっていることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項３４】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、特定の方向または場所から前記特定移動局が離れて行くことを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項３５】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、交通の混雑しているエリアへ前記特定移動局が向かっていることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項３６】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、交通の混雑しているエリア内において前記特定移動局が見つけられることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項３７】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、交通の混雑している道路上において前記特定移動局が見つけられることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項３８】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、あらかじめ定義済みの移動経路上の混雑している部分へ前記特定移動局が向かっていることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項３９】
少なくとも１つのアラート系サービスに関連付けされているアラートの発射が、前記特定移動局が移動局の選択されたグループのメンバである場合に限ってトリガされる請求項１９に記載のデータ処理装置。
【請求項４０】
前記移動局の選択されたグループが、事前定義された少なくとも１つの共通する人口統計学的特徴を共有するユーザに関連する移動局グループを含む請求項１９に記載のデータ処理装置。
【請求項４１】
前記移動局の選択されたグループが、共通のアラート系サービスに加入している移動局グループを含む請求項１９に記載のデータ処理装置。
【請求項４２】
前記移動局の選択されたグループが、共通の挙動の特徴を有するユーザに関連する移動局グループを含む請求項１９に記載のデータ処理装置。
【請求項４３】
少なくとも１つのアラート系サービスに関連付けされているアラートの発射は、所定時間の長さの間に前記少なくとも１つのアラート系サービスに関連付けされているアラートの発射が行われていないことを条件とする請求項１９に記載のデータ処理装置。
【請求項４４】
少なくとも１つのアラート系サービスに関連付けされているアラートの発射に対するトリガを生成することは、所定の範囲内に現在時が入ることを条件とする請求項１９に記載のデータ処理装置。
【請求項４５】
少なくとも１つのアラート系サービスに対応する前記アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、所定の範囲を超える速度を前記特定移動局が有していることを示す場合に、前記特定移動局によって満たされているとみなされる請求項１９に記載のデータ処理装置。
【請求項４６】
１次メモリおよび２次メモリをさらに備え、前記処理ユニットは、さらに：
・前記２次メモリ内に、データ構造を維持することが可能であり、データ構造のそれぞれは、時間間隔に関連付けされており、特定のデータ構造内の各データ構造は、そのデータ構造に関連付けされている前記時間間隔内に現在時が入ることを条件とするアラート条件の個々のサブセットに関連する情報を含んでおり；
・前記１次メモリが現在時を含む時間間隔に関連付けされているデータ構造を含まない場合に、現在時を含む時間間隔に関連付けされているデータ構造を用いて前記１次メモリの内容を上書きすることが可能であり；
・現在時を含む時間間隔に関連する前記データ構造内に関連する情報が含まれているアラート条件の前記サブセットに属するアラート条件に限定された前記アラート条件を基礎として、前記決定するステップがもたらされる請求項１９に記載のデータ処理装置。
【請求項４７】
各アラート条件は、特定の移動局に関する前記更新済みロケーション・データが、対応するアラート領域に前記特定移動局が入ったことを示す場合に、前記特定移動局によって満たされていると見なされ、各データ構造内の各データ構造は、ネットワーク内における異なるロケーションに対してもっとも近いアラート領域を示すデータを含む請求項４６に記載のデータ処理装置。
【請求項４８】
各データ構造内の各データ構造は：
・ネットワークをノードに分割すること；
・各ノードについてもっとも近いアラート領域を演算すること；および、
・同一のもっとも近いアラート領域を有するノードをセルに併合すること；
によって作られる請求項４７に記載のデータ処理装置。
【請求項４９】
前記処理ユニットは、さらに、２もしくはそれを超える数のノードの併合からもたらされたセルの境界を滑らかにすることが可能であるとする、請求項４８に記載のデータ処理装置。
【請求項５０】
各ノードについて前記もっとも近いアラート領域を演算することは、そのノードに関するボロノイ領域を演算することを含む請求項４９に記載のデータ処理装置。
【請求項５１】
前記処理ユニットは、さらに、新しいアラート領域の出現に対して：
（ａ）ノードであって、注目している前記ノードに以前に関連付けされていたもっとも近いアラート領域より新しいアラート領域が近くなるノードを見つけ出すこと；および、
（ｂ）（ａ）において見つけ出されたノードだけを囲い込む少なくとも１つの多角形を作ること；
によって応答することができるとする、請求項５０に記載のデータ処理装置。
【請求項５２】
移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合された通信ネットワークにおいて使用する方法であって：
・前記移動局に関する更新済みロケーション・データを受け取ること；
・特定の移動局に関する前記更新済みロケーション・データを基礎として、いずれのアラート系サービスに関して少なくとも１つの対応するアラート条件が前記特定移動局によって満たされているかについて、それが存在する場合にはその決定を行うこと；および、
・少なくとも１つの対応するアラート条件が前記特定移動局によって満たされた各アラート系サービスに関連付けされているアラートを発射するトリガを生成すること；
を含む方法。
【請求項５３】
移動局によって満たされる対応のアラート条件が定義されたアラート系サービスを提供するようなされた通信ネットワークに使用するシステムであって：
・前記移動局に関する更新済みロケーション・データを受け取るための手段；
・特定の移動局に関する前記更新済みロケーション・データを基礎として、いずれのアラート系サービスに関して少なくとも１つの対応するアラート条件が前記特定移動局によって満たされているかについて、それが存在する場合にはその決定を行うための手段；および、
・少なくとも１つの対応するアラート条件が前記特定移動局によって満たされた各アラート系サービスに関連付けされているアラートを発射するトリガを生成するための手段；
を備えるシステム。
【請求項５４】
移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワークにおける方法を具体化するコンピュータによる実行が可能な指示プログラムを有形に評価可能な形で実施するコンピュータ可読メディアであって、前記方法が：
・前記移動局に関する更新済みロケーション・データを受け取ること；
・特定の移動局に関する前記更新済みロケーション・データを基礎として、いずれのアラート系サービスに関して少なくとも１つの対応するアラート条件が前記特定移動局によって満たされているかについて、それが存在する場合にはその決定を行うこと；および、
・少なくとも１つの対応するアラート条件が前記特定移動局によって満たされた各アラート系サービスに関連付けされているアラートを発射するトリガを生成すること；
を含むコンピュータ可読メディア。
【請求項５５】
移動局によって満たされることになる対応のアラート条件が定義されているアラート‐ベース通信サービスを提供するシステムであって：
・前記移動局に関係するロケーション・データが、前記アラート‐ベース通信サービスに対応するアラート条件を前記移動局が満たしていることを示す場合に、前記アラート‐ベース通信サービスに関連するアラートを発射することができるアラート・エンジン；
を備えるシステム。
【請求項５６】
さらに：
・前記移動局に関する更新済みロケーション・データの受領によって満たされる時間条件を指定することのできる要求エンジン；および、
・前記時間条件を満たす前記移動局に関する前記更新済みロケーション・データの受領を保証することのできるスケジューラ；
を備える請求項５５に記載のシステム。
【請求項５７】
前記アラート・エンジンは、特定のアラート条件が特定の移動局によって満たされているか否かについての検証を、前記特定移動局に関連する前記更新済みロケーション・データの受領時に行うようなされた請求項５６に記載のシステム。
【請求項５８】
前記アラート・エンジンは、特定のアラート条件が特定の移動局によって満たされているか否かについての検証を、前記特定移動局に関連する前記更新済みロケーション・データの受領時であって、前記特定移動局に関連する前記更新済みロケーション・データの前記受領によって前記時間条件が満たされた場合に限って行うべく適合されている請求項５７に記載のシステム。
【請求項５９】
現在のロケーションと複数のアラート領域の間における予期される最も早い時を獲得するためにデータ構造にアクセスする方法であって、前記データ構造は、セルへのネットワークの細区分に関するデータを含み、セルに関するそれぞれのアラート領域は、前記セル内のすべてのポイントに対してもっとも近くなるものとし、かつ：
（ａ）ポイント‐ロケーション・データ構造を使用して、いずれのセルが現在のロケーションを含むかについて決定すること；
（ｂ）ステップ（ａ）において見つけ出されたセルに関連付けされているアラート領域を、テーブルを使用して決定すること；および、
（ｃ）前記現在のロケーションからステップ（ｂ）において見つけ出されたアラート領域までの移動時間を、コスト関数を使用して決定すること；
を含む方法。
【請求項６０】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置であって：
（ａ）それぞれのロケーション要求に関する複数の満了時間を示す満了時間データを受け取るための入力；
（ｂ）前記ＰＤＥによる前記ロケーション要求のサービス提供に関する順序を、少なくとも部分的に前記ロケーション要求の前記満了時間を基礎として決定するための、前記満了時間データを処理するスケジューラ；
（ｃ）前記ＰＤＥとインターフェースし、前記ＰＤＥによる、前記スケジューラによって決定された順序に従った前記ロケーション要求のサービス提供を可能にする出力；
を備える装置。
【請求項６１】
前記スケジューラが、前記ＰＤＥによる前記ロケーション要求のサービス提供に関する順序に従ってデータ・エレメントを保持するための一連のスロットを定義するストレージ・メディアを備える請求項６０に記載の装置。
【請求項６２】
前記ストレージ・メディア内の各データ・エレメントが、ロケーション要求に関連付けされている請求項６１に記載の装置。
【請求項６３】
前記スケジューラは、新しいロケーション要求に関連する新しい満了時間データが前記入力において受け取られたときに、前記ストレージ・メディア内の前記データ・エレメントの順序を再演算するべく機能する請求項６１に記載の装置。
【請求項６４】
前記一連のスロット内の各スロットは、そのスロット内にストアされているデータ・エレメントのロケーション要求に対してサービス提供することが前記ポジション決定装置に期待されている時点に対応する請求項６３に記載の装置。
【請求項６５】
前記再演算は、新しいロケーション要求ごとに、前記一連のスロット内において、前記新しいロケーション要求の満了時間内となる前記新しいロケーション要求のサービス提供に関する時点に対応するスロットを識別することを含む請求項６４に記載の装置。
【請求項６６】
前記再演算は、前記一連のスロット内において、新しいロケーション要求のサービス提供に関し、もっとも遅く、かつ前記ロケーション要求の満了時間を超えることのない時点に対応するスロットを識別することを含む請求項６５に記載の装置。
【請求項６７】
前記新しいロケーション要求のサービス提供に関するもっとも遅い時点に対応する前記スロットが空の場合には、前記スケジューラが、前記新しいロケーション要求に関連するデータ・エレメントを前記もっとも遅い時点に対応する前記スロット内にストアするべく機能する請求項６６に記載の装置。
【請求項６８】
前記新しいロケーション要求のサービス提供に関するもっとも遅い時点に対応する前記スロットが、以前のロケーション要求に関連するデータ・エレメントによって占有されていた場合には、前記スケジューラが：
（ａ）前記以前のロケーション要求に関連する前記データ・エレメントを、前記以前のロケーション要求のサービス提供に関して、より早い時点に対応するスロットに移し換え、前記以前のロケーション要求に関連する前記データ・エレメントを含んでいるスロットを空にし；
（ｂ）前記空にしたスロット内に、前記新しいロケーション要求に関連する前記データ・エレメントを挿入するべく機能する請求項６７に記載の装置。
【請求項６９】
前記データ・エレメントは、サーチ・ツリーに従って配列される請求項６１に記載の装置。
【請求項７０】
各データ・エレメントがロケーション要求に関連しており、各データ・エレメントが前記サーチ・ツリー内のノードによって表される請求項６９に記載の装置。
【請求項７１】
前記サーチ・ツリーの前記ノードは、それぞれのロケーション要求の前記満了時間に従って順序設定される請求項７０に記載の装置。
【請求項７２】
各データ・エレメントは、前記データ・エレメントに関連するノードの子孫の数に関する情報を含む第１のラベルを含む請求項７１に記載の装置。
【請求項７３】
各データ・エレメントは、ロケーション要求のサービス提供が行われることになるタイム・スロットを識別する情報を含む第２のラベルを含む請求項７２に記載の装置。
【請求項７４】
前記スケジューラは、少なくとも部分的に前記サーチ・ツリー内のノードの前記第１および第２のラベルを基礎として、与えられたロケーション要求のサービス提供が行われる実際の時を演算するべく機能する請求項７３に記載の装置。
【請求項７５】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を具現化するプロセッサによる実行のためのプログラム・エレメントを含むコンピュータ可読ストレージ・メディアであって：
（ａ）それぞれのロケーション要求に関係する複数の満了時間を示す満了時間データを入力として受け入れ、かつ前記ＰＤＥによる前記ロケーション要求のサービス提供に関する順序を少なくとも部分的に前記ロケーション要求の前記満了時間を基礎として演算するためのスケジューリング・モジュール；
（ｂ）前記ＰＤＥとインターフェースし、前記ＰＤＥによる、前記スケジューラによって決定された順序に従った前記ロケーション要求のサービス提供を可能にする出力モジュール；
を包含するコンピュータ可読ストレージ・メディア。
【請求項７６】
前記スケジューリング・モジュールが、一連のスロットを定義するストレージ・メディア内において、データ・エレメントが、前記スケジューリング・モジュールによって演算された前記ロケーション要求のサービス提供に関する順序に従って配列されるように、前記データ・エレメントの挿入ならびに削除を行うべく機能する請求項７５に記載のピュータ可読ストレージ・メディア。
【請求項７７】
各データ・エレメントがロケーション要求に関連付けされている請求項７６に記載のピュータ可読ストレージ・メディア。
【請求項７８】
前記スケジューリング・モジュールは、前記スケジューリング・モジュールによって新しいロケーション要求に関連する新しい満了時間データが受け取られたときに、前記ストレージ・メディア内の前記データ・エレメントの順序を再演算するべく機能する請求項７７に記載のピュータ可読ストレージ・メディア。
【請求項７９】
前記一連のスロット内の各スロットは、そのスロット内にストアされているデータ・エレメントのロケーション要求に対してサービス提供することが前記ＰＤＥに期待されている時点に対応する請求項７８に記載のピュータ可読ストレージ・メディア。
【請求項８０】
前記再演算は、新しいロケーション要求ごとに、前記一連のスロット内において、前記新しいロケーション要求の満了時間内となる前記新しいロケーション要求のサービス提供に関する時点に対応するスロットを識別することを含む請求項７９に記載のピュータ可読ストレージ・メディア。
【請求項８１】
前記再演算は、前記一連のスロット内において、新しいロケーション要求のサービス提供に関し、もっとも遅く、かつ前記新しいロケーション要求の満了時間を超えることのない時点に対応するスロットを識別することを含む請求項８０に記載のピュータ可読ストレージ・メディア。
【請求項８２】
前記新しいロケーション要求のサービス提供に関するもっとも遅い時点に対応する前記スロットが空の場合には、前記スケジューリング・モジュールが、前記新しいロケーション要求に関連するデータ・エレメントを前記もっとも遅い時点に対応する前記スロット内にストアするべく機能する請求項８０に記載のピュータ可読ストレージ・メディア。
【請求項８３】
前記新しいロケーション要求のサービス提供に関するもっとも遅い時点に対応する前記スロットが、以前のロケーション要求に関連するデータ・エレメントによって占有されていた場合には、前記スケジューリング・モジュールが：
（ａ）前記以前のロケーション要求に関連する前記データ・エレメントを、前記以前のロケーション要求のサービス提供に関して、より早い時点に対応するスロットに移し換え、前記以前のロケーション要求に関連する前記データ・エレメントを含んでいるスロットを空にし；
（ｂ）前記空にしたスロット内に、前記新しいロケーション要求に関連する前記データ・エレメントを挿入するべく機能する請求項８２に記載のピュータ可読ストレージ・メディア。
【請求項８４】
前記データ・エレメントは、サーチ・ツリーに従って配列される請求項７６に記載のピュータ可読ストレージ・メディア。
【請求項８５】
各データ・エレメントがロケーション要求に関連しており、各データ・エレメントが前記サーチ・ツリー内のノードによって表される請求項８４に記載のピュータ可読ストレージ・メディア。
【請求項８６】
前記サーチ・ツリーの前記ノードは、それぞれのロケーション要求の前記満了時間に従って順序設定される請求項８５に記載のピュータ可読ストレージ・メディア。
【請求項８７】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングする方法であって：
（ａ）それぞれのロケーション要求に関する複数の満了時間を示す満了時間データを受け取ること；
（ｂ）前記ポジション決定装置による前記ロケーション要求のサービス提供に関する順序を、少なくとも部分的に前記ロケーション要求の前記満了時間を基礎として決定するために、前記満了時間データの処理を行うこと；
（ｃ）前記ＰＤＥによる、前記決定に従った前記ロケーション要求のサービス提供を可能にするために前記ＰＤＥとインターフェースすること；
を含む方法。
【請求項８８】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置であって：
（ａ）エンティティからデータ・エレメントを受け取るための入力であって、前記データ・エレメントがそれぞれのロケーション要求を示す入力を備え；
（ｂ）前記ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含み；かつ、前記装置は、
（ｃ）ロケーション要求のサービス提供がいつ行われるかについて決定するためのスケジューラであって、前記決定が、少なくともいくつかの遅延タイプのロケーション要求が人為的に延期されるように行われるスケジューラ；
（ｄ）前記ＰＤＥとインターフェースし、前記ＰＤＥによる、前記決定に従った前記ロケーション要求のサービス提供を可能にする出力；
を備える装置。
【請求項８９】
前記決定は、それぞれの遅延タイプのロケーション要求の前記満了時間データを超えることなく、前記遅延タイプのロケーション要求の前記サービス提供が人為的に延期されるように行われる請求項８８に記載の装置。
【請求項９０】
前記スケジューラが、前記決定に従ってデータ・エレメントを保持するための一連のスロットを定義するストレージ・メディアを備える請求項８８に記載の装置。
【請求項９１】
前記ストレージ・メディア内の各データ・エレメントが、ロケーション要求に関連付けされている請求項９０に記載の装置。
【請求項９２】
前記スケジューラは、新しいロケーション要求に関連する新しい満了時間データが前記入力において受け取られたときに、前記ストレージ・メディア内の前記データ・エレメントの順序を再演算するべく機能する請求項９１に記載の装置。
【請求項９３】
前記データ・エレメントは、サーチ・ツリーに従って配列される請求項８９に記載の装置。
【請求項９４】
各データ・エレメントがロケーション要求に関連しており、各データ・エレメントが前記サーチ・ツリー内のノードによって表される請求項９３に記載の装置。
【請求項９５】
前記サーチ・ツリーの前記ノードは、それぞれのロケーション要求の前記満了時間に従って順序設定される請求項９４に記載の装置。
【請求項９６】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングする方法であって：
（ａ）エンティティからデータ・エレメントを受け取ることであって、前記データ・エレメントはそれぞれのロケーション要求を示すものとし、前記ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含む、データ・エレメントの受け取り；
（ｂ）ロケーション要求のサービス提供がいつ行われるかについて決定することであって、少なくともいくつかの遅延タイプのロケーション要求が人為的に延期されるように行われる決定；
（ｃ）前記ＰＤＥとインターフェースし、前記ＰＤＥによる、前記決定に従った前記ロケーション要求のサービス提供を可能にすること；
を含む方法。
【請求項９７】
前記決定は、それぞれの遅延タイプのロケーション要求の前記満了時間データを超えることなく、前記遅延タイプのロケーション要求の前記サービス提供が人為的に延期されるように行われる請求項９６に記載の方法。
【請求項９８】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を具体化するプロセッサによる実行のためのプログラム・エレメントを含むコンピュータ可読ストレージ・メディアであって：
（ａ）エンティティから入力としてデータ・エレメントを受け入れるためのスケジューリング・モジュールであって、前記データ・エレメントはそれぞれのロケーション要求を示すものとし、前記ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含むものとし、前記スケジューリング・モジュールは、ロケーション要求のサービス提供がいつ行われるかについて決定するべく機能し、前記決定が少なくともいくつかの遅延タイプのロケーション要求が人為的に延期されるように行われるスケジューリング・モジュール；
（ｂ）前記ＰＤＥとインターフェースし、前記ＰＤＥによる、前記決定に従った前記ロケーション要求のサービス提供を可能にする出力モジュール；
を包含するコンピュータ可読ストレージ・メディア。
【請求項９９】
前記決定は、それぞれの遅延タイプのロケーション要求の前記満了時間データを超えることなく、前記遅延タイプのロケーション要求の前記サービス提供が人為的に延期されるように行われる請求項９８に記載のピュータ可読ストレージ・メディア。
【請求項１００】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置であって：
（ａ）エンティティから複数のデータ・エレメントを受け取るための入力であって、前記複数のデータ・エレメントがそれぞれのロケーション要求を示す入力を備え；
（ｂ）前記ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含み；かつ、前記装置は、
（ｃ）スケジューラを備え、前記スケジューラは：
（ｉ）遅延タイプのロケーション要求の間において、前記ＰＤＥに対する共通のロケーション・クエリによってサービス提供が可能な２ないしはそれを超える数の遅延タイプのロケーション要求を識別するため；および、
（ｉｉ）前記ＰＤＥに対する前記共通のロケーション・クエリをいつ発行するかについて、（ｉ）において識別された遅延タイプのロケーション要求のそれぞれの満了時間を少なくとも部分的に基礎として決定するためのスケジューラであり；かつ、前記装置は、
（ｄ）前記共通のロケーション・クエリを発行するための出力；
を備える装置。
【請求項１０１】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングする方法であって：
（ｉ）エンティティから複数のデータ・エレメントを受け取ることであって、前記複数のデータ・エレメントはそれぞれのロケーション要求を示すものとし、前記ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含む、データ・エレメントの受け取り；
（ｉｉ）遅延タイプのロケーション要求の間において、前記ＰＤＥに対する共通のロケーション・クエリによってサービス提供が可能な２ないしはそれを超える数の遅延タイプのロケーション要求を識別すること；
（ｉｉｉ）前記ＰＤＥに対する前記共通のロケーション・クエリをいつ発行するかについて、（ｉｉ）において識別された遅延タイプのロケーション要求のそれぞれの満了時間を少なくとも部分的に基礎として決定すること；
（ｉｖ）前記共通のロケーション・クエリを発行すること；
を含む方法。
【請求項１０２】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を具体化するプロセッサによる実行のためのプログラム・エレメントを含むコンピュータ可読ストレージ・メディアであって：
（ａ）エンティティから複数のデータ・エレメントを受け入れるためのスケジューリング・モジュールであって、前記複数のデータ・エレメントはそれぞれのロケーション要求を示すものとし、前記ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含むものとし、かつ：
（ｉ）遅延タイプのロケーション要求の間において、前記ＰＤＥに対する共通のロケーション・クエリによってサービス提供が可能な２ないしはそれを超える数の遅延タイプのロケーション要求を識別し；
（ｉｉ）前記ＰＤＥに対する前記共通のロケーション・クエリをいつ発行するかについて、（ｉ）において識別された遅延タイプのロケーション要求のそれぞれの満了時間を少なくとも部分的に基礎として決定するべく機能するスケジューリング・モジュール；
（ｂ）前記共通のロケーション・クエリを発行するための出力モジュール；
を包含するコンピュータ可読ストレージ・メディア。
【請求項１０３】
ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置であって：
（ａ）それぞれのロケーション要求に関連する複数の満了時間を示す満了時間データを受け取るための入力手段；
（ｂ）前記ＰＤＥによる前記ロケーション要求のサービス提供に関する順序を、前記ロケーション要求の前記満了時間を少なくとも部分的に基礎として決定するために前記満了時間データを処理するスケジューラ手段；
（ｃ）前記ＰＤＥとインターフェースし、前記スケジューラ手段により決定された前記順序に従った前記ロケーション要求の、前記ＰＤＥによるサービス提供を可能にする出力手段；
を備える装置。
【請求項１０４】
ＰＤＥによるロケーション要求のサービス提供をスケジュールするための装置であって：
（ａ）エンティティからデータ・エレメントを受け取るための入力手段であって、前記データ・エレメントはそれぞれのロケーション要求を示すものとし、前記ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含む、入力手段；
（ｂ）前記ロケーション要求がいつサービス提供されるかについて決定するためのスケジューリング手段であって、前記決定は、少なくともいくつかの遅延タイプのロケーション要求が人為的に延期されるようになされるスケジューリング手段；
（ｃ）前記ＰＤＥとインターフェースし、前記決定に従った前記ロケーション要求の前記ＰＤＥによるサービス提供を可能にする出力手段；
を備える装置。
【請求項１０５】
ＰＤＥによるロケーション要求のサービス提供をスケジュールするための装置であって：
（ａ）エンティティから複数のデータ・エレメントを受け取るための入力手段であって、前記複数のデータ・エレメントはそれぞれのロケーション要求を示すものとし、前記ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含む、入力手段；
（ｂ）スケジューリング手段であって：
（ｉ）遅延タイプのロケーション要求の間において、前記ＰＤＥに対する共通のロケーション・クエリによってサービス提供が可能な２ないしはそれを超える数の遅延タイプのロケーション要求を識別し；
（ｉｉ）前記ＰＤＥに対する前記共通のロケーション・クエリをいつ発行するかについて、（ｉ）において識別された遅延タイプのロケーション要求のそれぞれの満了時間を少なくとも部分的に基礎として決定するためのスケジューリング手段；
（ｃ）前記共通のロケーション・クエリを発行するための出力手段；
を備える装置。
【請求項１０６】
移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワークで使用されるデータ処理装置上において実行されるアプリケーション・プログラムによるアクセスのためのデータをストアするメモリであって：
・複数のデータ構造を保持するための２次メモリであって、前記データ構造はオーバーラップしない時間間隔に関連付けされており、各データ構造は、そのデータ構造に関連付けされている前記時間間隔内に現在時が入ることを条件とするアラート条件の個々のカテゴリに関連する情報を含んでいる２次メモリ；
・前記現在時を含む時間間隔に関連付けされている１つのデータ構造をストアするための１次メモリ；
を含むメモリ。
【請求項１０７】
移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワーク内で使用されるデータ処理装置上において実行されるアプリケーション・プログラムによるアクセスのためのデータ構造を作成する方法であって、各アラート条件はアラート領域に対応しており：
・ノードへのネットワークの細区分を定義すること；
・各ノードについて、もっとも近いアラート領域を演算すること；
・各アラート領域について、前記もっとも近いアラート領域としてアラート領域を有するノードを単一のセルに併合すること；
・各セルによってカバーされるロケーションおよびそのセルに関連するアラート条件を示すデータ構造を維持すること；
を含む方法。
【請求項１０８】
各アラート条件は、さらにアラート時間に対応しており、前記方法は、さらに：
・それぞれの共通しないタイム・ブロックに対応するアラート条件の少なくとも２つのセットに関する分離されたデータ構造を維持することを含み、アラート条件の各セットは、それぞれのタイム・ブロック内に含まれるアラート時間に対応するアラート条件を含む請求項１０７に記載の方法。
【請求項１０９】
通信ネットワーク内における移動局に関するアラート‐ベースの通信サービスを配信する方法であり、前記アラート‐ベースの通信サービスは、前記移動局によって満たされることになるアラート条件に関連付けられており：
・第１の瞬時について、前記移動局に関するロケーション・データを獲得すること；
・前記第１の瞬時より後の第２の瞬時について、前記移動局に関するロケーション・データを、前記第１の瞬時についての前記移動局に関するロケーション・データに基づいて予測すること；
・前記第２の瞬時において、前記アラート領域内に前記移動局が存在することが予測される場合に、前記第２の瞬時もしくはその後にアラート発射をトリガすること；
を含む方法。
【請求項１１０】
ロケーション・データを予測することが、前記移動局に関する最近の情報を基礎としている請求項１０９に記載の方法。
【請求項１１１】
ロケーション・データを予測することが、前記移動局に関する履歴情報を基礎としている請求項１０９に記載の方法。
【請求項１１２】
ロケーション・データを予測することが、前記ネットワーク内のほかの移動局に関する現在の情報を基礎としている請求項１０９に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークに関し、特に、ワイヤレス通信ネットワーク内の移動局に対してアラート系サービスを提供するシステムに関する。
【背景技術】
【０００２】
現在の著しいテレコミュニケーション競争の時代においてモバイル・ネットワーク・オペレータは、差別化を作り出し増益をもたらす、新しく、かつ革新的な方法を常に探求している。この目標を達成する最良の方法の１つは、ロケーション系サービス（ＬＢＳ）等の高度にパーソナライズされたサービスを届けることである。それに加えてモバイル・ネットワーク・オペレータは、特定の国内法の下に、それらのインフラストラクチャにＬＢＳを、特に緊急サービスに関するそれを装備することが要求されている。全体として、ＬＢＳの主要なカテゴリには、少なくとも４つ、すなわちロケーション‐ベース情報、ロケーション従属課金、緊急サービス、および追跡がある。
【０００３】
一般に好まれているＬＢＳの特徴は、アラート系サービス（ＡＢＳ）のサポート機能である。アラート系アプリケーションにおいては、ワイヤレス・ネットワーク内の登録済み移動局がモニタされ、各移動局に対して移動局のロケーションに基づいてアラートがトリガされる。あらかじめ決定済みのロケーションに近づいているか、或いは入ろうとしている特定の移動局に対してアラートの発射（ファイアリング）が行われるときには、その特定の移動局に対するメッセージの送信或いはデータベースの更新といった、少なくとも１つの特定のアクションが行われる。ＡＢＳの出現は商業セクタから政府セクタまで広い範囲にわたりは、特にマーケティング、広告、法の施行、緊急監視、および通信ベース・サービスといった目的のための使用が挙げられる。
【０００４】
ワイヤレスＬＢＳの採用レートが高くなるに従って、ネットワーク・オペレータおよびそのほかのモバイル・ロケーション・データ・プロバイダには、増加し続けるモバイル・ロケーション・データを各種のアラート系アプリケーションへ提供することが要求されるようになる。これらのアラート系アプリケーションは、それぞれのロケーション・データ要件において非常に多様である。より具体的に述べれば、いくつかの、例えばドライブ指図アプリケーション或いは店探しアプリケーション等のアプリケーションは、適時のデータを必要とし、移動局ユーザによって起動される。ある種のユーザ追跡を実行する別のタイプのアプリケーションは、散発的であり、ロケーション要求間の遅延が移動局のポジションの関数として変化する。
【０００５】
ＡＢＳのもっとも自明かつ重要な１つの側面は、ポジショニング、つまりネットワーク内における移動局のポジションを決定する能力である。広く認識されているポジショニング・テクノロジの１つにグローバル・ポジショニング・システム（ＧＰＳ）がある。ＧＰＳに加えて、ほかのポジショニング・テクニックが、移動局にサービス提供を行っているセル・サイトからの信号の各種三角測量手段を頼っている。さらに、サービス提供セル・サイトをユーザのロケーションに関する位置決定に使用することもできる。
【０００６】
地理的なデータは、あらゆるロケーション・システムにとって重要なもう１つの側面である。地理情報システム（ＧＩＳ）は、人為的構造物（道路、建物）および地形（山、川）等の基本地図データを提供し、かつ管理するツールを提供する。ＧＩＳは、給油所、レストラン、ナイトクラブ等のロケーションといった注目スポットの管理にも使用される。さらに述べれば、ＧＩＳ情報は、モバイル・ネットワークの無線周波数特性に関する情報も含んでいる。このことは、システムによるユーザのサービス提供セル・サイトの決定を可能にする。
【０００７】
結論を述べると、これは、モバイル・ユーザのポジションを決定し、そのポジション周囲の地図データを知ることを可能にする上で充分ではない。ＡＢＳアプリケーションに代わってポジショニングおよびＧＩＳデータを処理するロケーション管理機能も提供されていなければならない。ロケーション管理機能は、ゲートウェイとして、またポジショニング装置とＬＢＳ／ＡＢＳインフラストラクチャの間の仲裁として作用するミドルウェアである。特に挙げるとすれば、ロケーション管理機能を使用して、ポジショニング情報を有用なロケーション情報に変換し、各種のＡＢＳアプリケーションに利用可能とすることができる。
【０００８】
従来のワイヤレス・ネットワークにおいては、ロケーション管理機能および１ないしは複数のネットワーク・エンティティ（network entity）を伴う要求／応答メカニズムが使用されてネットワーク内の移動局に関するポジション情報が決定されている。ロケーション要求を受け取ることが可能な、したがって要求／応答メカニズム内に含めることができるネットワーク・エンティティは、多くの可能性の中でも特に、基地局コントローラ（ＢＳＣ）、移動通信交換局（ＭＳＣ）、ホーム・ロケーション・レジスタ（ＨＬＲ）、ビジテッド・ロケーション・レジスタ（ＶＬＲ）、ゲートウェイ・モバイル・ロケーション・センタ（ＧＭＬＣ）、サービング・モバイル・ロケーション・センタ（ＳＭＬＣ）、モバイル・ポジショニング・センタ（ＭＰＣ）およびポジショニング決定エンティティ（ＰＤＥ）を含む。要求／応答メカニズムは、通常、今日の主流のワイヤレス・ネットワーク・プロトコル、すなわち米国規格協会（ＡＮＳＩ）‐４１およびモバイル通信グローバル・システム（ＧＳＭ）の両方がサポートするシグナリングをてこ入れすることによって具体化される。主流のＳＳ７シグナリングは、この要求／応答メカニズムをサポートできるが、そのほかのトランスポート・メカニズムをこの目的で使用してもよい。
【０００９】
例えば、ワイヤレス・インテリジェント・ネットワーク（ＷＩＮ）標準‐‐ＩＳ‐８４８としても知られ、ＡＮＳＩ‐４１プロトコルを基礎とする‐‐は、次に述べるような方法で移動局のポジションの獲得を提供する。所定のサービス・コントロール・ポイントにおいてロケーション管理機能が、特定のポジション要求（ＰｏｓＲｅｑ）メッセージを使用しいてＨＬＲに問い合わせを行う。ＨＬＲには、そのモバイル・ユーザにサービス提供を行った最後のＶＬＲがわかっている。したがってＨＬＲは、このＶＬＲに対して、ポジション情報（セル・サイト識別子等）を求める要求を行い、その情報の受領に応答して、それをＰｏｓＲｅｑ応答メッセージ内においてサービス・コントロール・ポイントに向けて返す。
【００１０】
ここで認識できるように、従来のテクニックは、各ロケーション要求の生成の直後にそれぞれをネットワークが個別に解決できることを必要とする。さらに言えば、ほとんどのＡＢＳアプリケーションが何らかの価値を有するためには、数分もしくはそれに満たない間隔でユーザ・ロケーション情報を要求することが必要となろう。したがって、ここで明らかになることは、ネットワークが各ＡＢＳアプリケーションに代わって注目する各ユーザに関する頻繁な要求を満たすことを試みるため、過剰でないとしても飛躍的にネットワークが輻輳するであろうということになる。結果的に、ワイヤレス・ネットワークの交換およびトランスポート容量が、従来方法におけるロケーション情報獲得のための負担の重い要求によって浸食されることになる。
【００１１】
【非特許文献１】
エストコウスキ（Ｅｓｔｋｏｗｓｋｉ）およびミッチェル（Ｍｉｔｃｈｅｌｌ）著「単純性を維持しつつ行う多角形細区分の簡略化（Ｓｉｍｐｌｉｆｙｉｎｇ  ａ  Ｐｏｌｙｇｏｎａｌ  Ｓｕｂｄｉｖｉｓｉｏｎ  Ｗｈｉｌｅ  Ｋｅｅｐｉｎｇ  Ｉｔ  Ｓｉｍｐｌｅ）」コンピュータ使用幾何学シンポジウム（Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｇｅｏｍｅｔｒｙ）会報、２００１年、ｐ．４０‐４９。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
この背景に照らすと、ワイヤレス通信ネットワーク内において使用可能な帯域幅ならびに負荷限界を超えることなく有用なロケーション情報を獲得し、使用することによってＡＢＳアプリケーションを有効にする必要があることは明らかである。
【課題を解決するための手段】
【００１３】
第１の広い側面によれば、本発明は、方法を具体化するコンピュータによる実行が可能な指示プログラムを有形に評価可能な形で実施するコンピュータ可読メディア（媒体）を提供し、コンピュータは、アラート系サービスの提供に適合する通信ネットワークと接続可能であり、そのアラート系サービスに関しては、移動局によって満たされることになる対応のアラート条件が定義されるものとし、かつ、この方法が：特定の移動局によって少なくとも１つのアラート条件が満たされ得る、予期される最も早い将来の時を決定すること；および、この予期される最も早い将来の時に先行してその特定の移動局に関する更新済みロケーション・データの取得要求を示すデータ・エレメントを出力することを含んでいる。
【００１４】
第２の広い側面によれば、本発明は、複数の移動局および各種のアラート条件に関して定義されているアラート系サービスの提供に適合する通信ネットワーク内において使用するための方法を提供し、当該方法は：特定の移動局によって少なくとも１つのアラート条件が満たされ得る、予期される最も早い将来の時を決定すること；および、この予期される最も早い将来の時に先行してその特定の移動局に関する更新済みロケーション・データの取得要求を示すデータ・エレメントを出力することを含んでいる。
【００１５】
第３の広い側面によれば、本発明は、複数の移動局および各種のアラート条件に関して定義されているアラート系サービスの提供に適合する通信ネットワーク内において使用するためのシステムを提供し、当該システムは：特定の移動局によって少なくとも１つのアラート条件が満たされ得る、予期される最も早い将来の時を決定するための手段；および、この予期される最も早い将来の時に先行してその特定の移動局に関する更新済みロケーション・データの取得要求を示すデータ・エレメントを出力するための手段を備えている。
【００１６】
第４の広い側面によれば、本発明は、複数の移動局および各種のアラート条件に関して定義されているアラート系サービスの提供に適合する通信ネットワーク内における方法を具体化するコンピュータによる実行のためのプログラム・エレメントを含むコンピュータ可読ストレージ・メディアを提供し、当該プログラム・エレメントが：特定の移動局によって少なくとも１つのアラート条件が満たされ得る、予期される最も早い将来の時を決定するためのプログラム・コード手段；および、この予期される最も早い将来の時に先行してその特定の移動局に関する更新済みロケーション・データの取得要求を示すデータ・エレメントを出力するためのプログラム・コード手段を含んでいる。
【００１７】
第５の広い側面によれば、本発明は、移動局によって満たされることになる対応するアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワーク内において使用するために記載のデータ処理装置を提供し、当該データ処理装置は：移動局に関する更新済みロケーション・データを受け取ることの可能な入力；および、その入力に接続される処理ユニットであって：特定の移動局に関する更新済みロケーション・データを基礎として、いずれのアラート系サービスに関して少なくとも１つの対応するアラート条件が前記特定移動局によって満たされているかについて、それが存在する場合にはその決定を行うことが可能であり；かつ、少なくとも１つの対応するアラート条件が特定の移動局によって満たされた各アラート系サービスに関連付けされているアラート発射のためのトリガを生成することが可能な処理ユニットを備えている。
【００１８】
第６の広い側面によれば、本発明は、移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワークにおいて使用するための方法を提供し、当該方法は、移動局に関する更新済みロケーション・データを受け取ること；特定の移動局に関する更新済みロケーション・データを基礎として、いずれのアラート系サービスに関して少なくとも１つの対応するアラート条件が前記特定移動局によって満たされているかについて、それが存在する場合にはその決定を行うこと；および、少なくとも１つの対応するアラート条件が特定の移動局によって満たされた各アラート系サービスに関連付けされているアラート発射のためのトリガを生成することを含んでいる。
【００１９】
第７の広い側面によれば、本発明は、移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワークにおいて使用するためのシステムを提供し、当該システムは：移動局に関する更新済みロケーション・データを受け取るための手段；特定の移動局に関する更新済みロケーション・データを基礎として、いずれのアラート系サービスに関して少なくとも１つの対応するアラート条件が前記特定移動局によって満たされているかについて、それが存在する場合にはその決定を行うための手段；および、少なくとも１つの対応するアラート条件が特定の移動局によって満たされた各アラート系サービスに関連付けされているアラート発射のためのトリガを生成するための手段を備えている。
【００２０】
第８の広い側面によれば、本発明は、移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワークにおける方法を具体化するコンピュータによる実行が可能な指示プログラムを有形に評価可能な形で実施するコンピュータ可読メディアを提供し、当該方法が：移動局に関する更新済みロケーション・データを受け取ること；特定の移動局に関する更新済みロケーション・データを基礎として、いずれのアラート系サービスに関して少なくとも１つの対応するアラート条件が前記特定移動局によって満たされているかについて、それが存在する場合にはその決定を行うこと；および、少なくとも１つの対応するアラート条件が特定の移動局によって満たされた各アラート系サービスに関連付けされているアラート発射のためのトリガを生成することを含んでいる。
【００２１】
第９の広い側面によれば、本発明は、移動局によって満たされることになる対応のアラート条件が定義されているアラート系通信サービスを提供するためのシステムを提供し、当該システムは：移動局に関係するロケーション・データが、アラート系通信サービスに対応するアラート条件をその移動局が満たしていることを示す場合に、アラート系通信サービスに関連するアラート発射を行うことができるアラート・エンジンを備えている。
【００２２】
第１０の広い側面によれば、本発明は、現在のロケーションと複数のアラート領域の間における予期される最も早い時を獲得するためにデータ構造にアクセスする方法を提供し、データ構造が、セルへのネットワークの細区分に関するデータを含み、セルに関するそれぞれのアラート領域が、そのセル内のすべてのポイントに対してもっとも近くなるものとし、かつ当該方法は：ポイント‐ロケーション・データ構造を使用して、いずれのセルが現在のロケーションを含むかについて決定すること；ステップ（ａ）において見つけ出されたセルに関連付けされているアラート領域を、テーブルを使用して決定すること；および、現在のロケーションからステップ（ｂ）において見つけ出されたアラート領域までの移動時間を、コスト関数を使用して決定することを含んでいる。
【００２３】
第１１の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を提供し、当該装置は：それぞれのロケーション要求に関する複数の満了時間を示す満了時間データを受け取るための入力；ＰＤＥによるロケーション要求のサービス提供に関する順序を、少なくとも部分的にロケーション要求の満了時間を基礎として決定するための、満了時間データを処理するスケジューラ；ＰＤＥとインターフェースし、ＰＤＥによる、スケジューラによって決定された順序に従ったロケーション要求のサービス提供を可能にする出力を備えている。
【００２４】
第１２の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を具体化するプロセッサによる実行のためのプログラム・エレメントを含むコンピュータ可読ストレージ・メディアを提供し、当該コンピュータ可読ストレージ・メディアは：それぞれのロケーション要求に関係する複数の満了時間を示す満了時間データを入力として受け入れ、かつＰＤＥによるロケーション要求のサービス提供に関する順序を少なくとも部分的にロケーション要求の満了時間を基礎として演算するためのスケジューリング・モジュール；ＰＤＥとインターフェースし、ＰＤＥによる、スケジューラによって決定された順序に従ったロケーション要求のサービス提供を可能にする出力モジュールを含んでいる。
【００２５】
第１３の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための方法を提供し、当該方法は：それぞれのロケーション要求に関する複数の満了時間を示す満了時間データを受け取ること；ポジション決定装置によるロケーション要求のサービス提供に関する順序を、少なくとも部分的にロケーション要求の満了時間を基礎として決定するために、満了時間データの処理を行うこと；その決定に従ったＰＤＥによるロケーション要求のサービス提供を可能にするためにＰＤＥとインターフェースすることを含んでいる。
【００２６】
第１４の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を提供し、当該装置は：エンティティからデータ・エレメントを受け取るための入力、すなわちそれぞれのロケーション要求を示すデータ・エレメントを受け取るための入力を備え；このロケーション要求が遅延タイプのロケーション要求を含み、また遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントが満了時間データを含んでおり；さらにこの装置は、ロケーション要求のサービス提供がいつ行われるかについて決定するためのスケジューラを備え、その決定は、少なくともいくつかの遅延タイプのロケーション要求が人為的に延期されるように行われるものであり；さらにこの装置は、ＰＤＥとインターフェースし、その決定に従ったＰＤＥによるロケーション要求のサービス提供を可能にする出力を備えている。
【００２７】
第１５の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための方法を提供し、当該方法は：エンティティからデータ・エレメントを受け取ることを含み、このデータ・エレメントはそれぞれのロケーション要求を示すものであり、ロケーション要求は遅延タイプのロケーション要求を含み、また遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含んでおり；さらにこの方法は、ロケーション要求のサービス提供がいつ行われるかについて決定することを含み、その決定は、少なくともいくつかの遅延タイプのロケーション要求が人為的に延期されるように行われるものであり；さらにこの方法は、ＰＤＥとインターフェースし、その決定に従ったＰＤＥによるロケーション要求のサービス提供を可能にすることを含んでいる。
【００２８】
第１６の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を具体化するプロセッサによる実行のためのプログラム・エレメントを含むコンピュータ可読ストレージ・メディアを提供し、当該コンピュータ可読ストレージ・メディアは：エンティティから入力としてデータ・エレメントを受け入れるためのスケジューリング・モジュールを包含し、このデータ・エレメントはそれぞれのロケーション要求を示すものであり、ロケーション要求は遅延タイプのロケーション要求を含み、また遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含んでおり、スケジューリング・モジュールは、ロケーション要求のサービス提供がいつ行われるかについて決定するべく機能し、その決定は、少なくともいくつかの遅延タイプのロケーション要求が人為的に延期されるように行われるものであり；さらにこに記載のピュータ可読ストレージ・メディアは、ＰＤＥとインターフェースし、決定に従ったＰＤＥによるロケーション要求のサービス提供を可能にする出力モジュールを包含している。
【００２９】
第１７の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を提供し、当該装置は：エンティティから複数のデータ・エレメントを受け取るための入力を備え、複数のデータ・エレメントは、それぞれのロケーション要求を示すものであり；ロケーション要求は、遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含み；さらにこの装置は、スケジューラを備え、当該スケジューラは：遅延タイプのロケーション要求の間において、ＰＤＥに対する共通のロケーション・クエリによってサービス提供が可能な２ないしはそれを超える数の遅延タイプのロケーション要求を識別するため；および、ＰＤＥに対して共通のロケーション・クエリをいつ発行するかについて、（ｉ）において識別された遅延タイプのロケーション要求のそれぞれの満了時間を少なくとも部分的に基礎として決定するためのスケジューラであり；さらにこの装置は、共通のロケーション・クエリを発行するための出力を備えている。
【００３０】
第１８の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための方法を提供し、当該方法は：エンティティから複数のデータ・エレメントを受け取ることを含み、複数のデータ・エレメントはそれぞれのロケーション要求を示すものであり、ロケーション要求は遅延タイプのロケーション要求を含んでおり、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含むものであり；さらにこの方法は、遅延タイプのロケーション要求の間において、ＰＤＥに対する共通のロケーション・クエリによってサービス提供が可能な２ないしはそれを超える数の遅延タイプのロケーション要求を識別すること；ＰＤＥに対する共通のロケーション・クエリをいつ発行するかについて、（ｉｉ）において識別された遅延タイプのロケーション要求のそれぞれの満了時間を少なくとも部分的に基礎として決定すること；および、共通のロケーション・クエリを発行することを含んでいる。
【００３１】
第１９の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を具体化するプロセッサによる実行のためのプログラム・エレメントを含むコンピュータ可読ストレージ・メディアを提供し、当該コンピュータ可読ストレージ・メディアは：エンティティから複数のデータ・エレメントを受け入れるためのスケジューリング・モジュールを含み、複数のデータ・エレメントはそれぞれのロケーション要求を示すものであり、ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含んでおり、このスケジューリング・モジュールは：遅延タイプのロケーション要求の間において、ＰＤＥに対する共通のロケーション・クエリによってサービス提供が可能な２ないしはそれを超える数の遅延タイプのロケーション要求を識別し；かつ、ＰＤＥに対する共通のロケーション・クエリをいつ発行するかについて、（ｉ）において識別された遅延タイプのロケーション要求のそれぞれの満了時間を少なくとも部分的に基礎として決定するべく機能し；さらにこに記載のピュータ可読ストレージ・メディアは、共通のロケーション・クエリを発行するための出力モジュールを含んでいる。
【００３２】
第２０の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジューリングするための装置を提供し、当該装置は：それぞれのロケーション要求に関連する複数の満了時間を示す満了時間データを受け取るための入力手段；ＰＤＥによるロケーション要求のサービス提供に関する順序を、ロケーション要求の満了時間を少なくとも部分的に基礎として決定するために満了時間データを処理するスケジューラ手段；ＰＤＥとインターフェースし、ＰＤＥによる、スケジューラ手段により決定された順序に従ったロケーション要求のサービス提供を可能にする出力手段を備えている。
【００３３】
第２１の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジュールするための装置を提供し、当該装置は：エンティティからデータ・エレメントを受け取るための入力手段を備え、データ・エレメントはそれぞれのロケーション要求を示すものであり、ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含んでおり；さらにこの装置は、ロケーション要求にいつサービス提供が行われるかについて決定するためのスケジューリング手段を備え、その決定は、少なくともいくつかの遅延タイプのロケーション要求が人為的に延期されるようになされるものであり；さらにこの装置は、ＰＤＥとインターフェースし、ＰＤＥによる、その決定に従ったロケーション要求のサービス提供を可能にする出力手段を備えている。
【００３４】
第２２の広い側面によれば、本発明は、ＰＤＥによるロケーション要求のサービス提供をスケジュールするための装置を提供し、当該装置は：エンティティから複数のデータ・エレメントを受け取るための入力手段を備え、複数のデータ・エレメントはそれぞれのロケーション要求を示すものであり、ロケーション要求は遅延タイプのロケーション要求を含み、遅延タイプのロケーション要求に関連付けされるロケーション要求データ・エレメントは満了時間データを含んでおり；さらにこの装置は、スケジューリング手段を備え、このスケジューリング手段は：遅延タイプのロケーション要求の間において、ＰＤＥに対する共通のロケーション・クエリによってサービス提供が可能な２ないしはそれを超える数の遅延タイプのロケーション要求を識別し；かつ、ＰＤＥに対する共通のロケーション・クエリをいつ発行するかについて、（ｉ）において識別された遅延タイプのロケーション要求のそれぞれの満了時間を少なくとも部分的に基礎として決定するためのスケジューリング手段であり；さらにこの装置は、共通のロケーション・クエリを発行するための出力手段を備えている。
【００３５】
第２３の広い側面によれば、本発明は、移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワーク内で使用されるデータ処理装置上において実行されるアプリケーション・プログラムによるアクセスのためのデータをストアするメモリを提供し、当該メモリは：複数のデータ構造を保持するための２次メモリを備え、当該データ構造はオーバーラップしない時間間隔に関連付けされており、各データ構造は、そのデータ構造に関連付けされている時間間隔内に現在時が入ることを条件とするアラート条件の個々のカテゴリに関連する情報を含んでおり；さらにこのメモリは、現在時を含む時間間隔に関連付けされている１つのデータ構造をストアするための１次メモリを備えている。
【００３６】
第２４の広い側面によれば、本発明は、移動局によって満たされることになる対応のアラート条件が定義されているアラート系サービスの提供に適合する通信ネットワーク内で使用されるデータ処理装置上において実行されるアプリケーション・プログラムによるアクセスのためのデータ構造を作成する方法を提供し、各アラート条件はアラート領域に対応しており、かつ当該方法は：ノードへのネットワークの細区分を定義すること；各ノードについて、もっとも近いアラート領域を演算すること；各アラート領域について、このもっとも近いアラート領域としてアラート領域を有するノードを単一のセルに併合すること；各セルによってカバーされるロケーションおよびそのセルに関連するアラート条件を示すデータ構造を維持することを含んでいる。
【００３７】
第２５の広い側面によれば、本発明は、通信ネットワーク内における移動局に関するアラート系の通信サービスを配信する方法を提供し、アラート系の通信サービスは、移動局によって満たされることになるアラート条件に関連付けられており、かつ当該方法は：第１の瞬時について、移動局に関するロケーション・データを獲得すること；第１の瞬時より後の第２の瞬時について、移動局に関するロケーション・データを、第１の瞬時についての移動局に関するロケーション・データに基づいて予測すること；第２の瞬時において、アラート領域内に移動局が存在することが予測される場合に、第２の瞬時もしくはその後にアラート発射をトリガすることを含んでいる。
【００３８】
以上およびその他の本発明の側面及び特徴は、添付図面とともに以下の本発明の具体的な実施態様を検討すれば当業者に明らかとなる。
【発明を実施するための最良の形態】
【００３９】
本発明の実施例は、通信ネットワークにおけるアラート系（alert-based）通信サービスの効率的な具現を可能にする。この種のサービスは、移動局がアラート−トリガ（alert-trigger）条件を満たしたときに特定の明確なアクションの実行を提供する。アラート系サービスの分野では、上記条件が満たされると『アラート』の『ファイアリング（発射）』がトリガ（駆動）される、という表現が普通に用いられる。
【００４０】
限定的を意図することなくアラート系通信サービスの一例を示すと、特定のレストランに関する情報を移動局へ、その移動局がそのレストランと同じ通り上にあるときに配信することが挙げられる。アラート系通信サービスの限定を意図しない別の例としては、移動局が自宅から特定の距離内に近づくと自宅の電話に情報を送信することが挙げられる。アラート系通信サービスの限定を意図しないさらに別の例においては、移動局に関する過去ならびに現在のロケーション・データから推測される速度測定によって、その移動局の速度がスレッショルドを超えていることが示された場合に、ハイウェイ・パトロール当局に対してアラームを通知することができる。ここで理解される必要があるが、『アラート系サービス』は、瞬時的な移動局のロケーションに直接関係するか、或いは移動局のロケーションにおける時間を伴った変化の結果として関係するかによらず、移動局のロケーションに関係する特定の条件が満たされたときにエンティティに対して何らかの信号が『プッシュ』される任意のサービスに広く用いられる。その種のサービスは、場合によっては、ロケーションがアラートのトリガに影響する移動局の同意なく、さらには知らせることさえもなく提供されることがある。
【００４１】
限定を意図しない特定の例として上述したサービスを含め、多くの有用なアラート系通信サービスが、移動局を絶えず追跡していない場合においてさえも提供可能であることが認識されている。より具体的には、間断のない複数のロケーション更新の受信がアラート系サービスの改善された配信をもたらさない場合がある。実際に、そのアラート系サービスに対応するアラート・トリガ条件が満たされた時点の取り逃がしがないことが保証される方法でロケーション更新が受信されている限り、その間の追加のロケーション更新を要求する必要はない。更新済みロケーション・データを要求するこの最適化された方法は、頻度のより少ないロケーション更新要求（したがって、より少ないネットワーク帯域幅リソースの消費）および頻度のより少ない更新済みロケーション・データの処理（したがって、より少ないネットワーク演算リソースの消費）をもたらす。
【００４２】
図１を参照するに、ワイヤレス通信ネットワーク１１０内において使用するためのアラート・マネージャ１００が示されている。アラート・マネージャ１００は、例えばコンピュータ・サーバ上において具体化することができる。アラート・マネージャ１００は、ネットワーク１１０に対する第１のインターフェース１２０を有している。インターフェース１２０は、更新済みロケーション・データに関する要求をネットワーク１１０内の個別の移動局へ送信するため、および個別の移動局に関するロケーション・データを受信するために使用される。またアラート・マネージャ１００は、第２のインターフェース１４０を経由して１ないしは複数のアラート系アプリケーション１３０との通信も行う。この第２のインターフェース１４０は、アラート‐トリガ条件および移動局識別をアラート系アプリケーション１３０から受信し、各アラート系アプリケーション１３０へ、ネットワーク１１０内の特定の移動局によってそのアラート系サービスに対応するアラート−トリガ条件がいつ満たされたかを示す情報を送信する。
【００４３】
アラート・マネージャ１００は、ロケーション・キャッシュ１５０を含み、そこには第１のインターフェース１２０を介してネットワーク１１０内のポジション決定エンティティ（ＰＤＥ）１６０から受信されるネットワーク１１０内の移動局に関するロケーション・データがストアされている。ここで注意されたいが、『ポジション決定エンティティ』は、ロケーション要求を受け取り、ネットワーク１１０内における移動局のロケーションを決定することができるネットワーク１１０内の任意タイプのエンティティを含意している。その種のＰＤＥの例としては、特に、基地局コントローラ（ＢＳＣ）、移動通信交換局（ＭＳＣ）、ホーム・ロケーション・レジスタ（ＨＬＲ）、ビジテッド・ロケーション・レジスタ（ＶＬＲ）、ゲートウェイ・モバイル・ロケーション・センタ（ＧＭＬＣ）、ショート・メッセージ・ロケーション・センタ（ＳＭＬＣ）、およびモバイル・ポジショニング・センタ（ＭＰＣ）をはじめ、周知のＡＮＳＩ‐４１のＰＤＥ等を挙げることができる。
【００４４】
ロケーション・キャッシュ１５０は、複数のデータ・エレメントを含み、そのそれぞれのデータ・エレメントは、移動局のアイデンティティ、移動局のロケーション、およびＰＤＥ１６０によってロケーションが決定された時刻と関連付けされている。『ロケーションが決定された時刻』は、アラート・マネージャ１００内のすべてのエンティティをはじめＰＤＥ１６０によって共有されている基準時刻を参照することができる。ここで気付かれようが、ＰＤＥ１６０は、能動的または同期ＰＤＥ（更新済みロケーション・データに関する要求に応答）および受動的または非同期ＰＤＥ（要求なしに更新済みロケーション・データを提供する）のいずれか、もしくはその両方を含む。能動的ポジション決定エンティティ１６０の好適な例は、２００１年７月５日に出願されたビスワナット（Ｖｉｓｗａｎａｔｈ）ほかの米国仮特許出願第６０／３０３，０２０号および２００２年７月５日に出願され、米国を指定国とするイオッペ（Ｉｏｐｐｅ）ほかの同時係属ＰＣＴ出願に記述されており、これらについては、いずれも参照によりこれに援用されている。
【００４５】
アラート・マネージャ１００には、さらに要求エンジン１７０、要求スケジューラ１８０、およびアラート・エンジン１９０が含まれている。いくつかの実施態様においては、これら３つの機能モジュール１７０、１８０、１９０を、バス１０５によって相互接続されるハードウエアとすることができ、別の実施態様においては、それらを、個別の相互に関連付けされて同一のプロセッシング・ユニットを共有するソフトウエア・コンポーネントとすることができる。このほかの、要求エンジン１７０、要求スケジューラ１８０、およびアラート・エンジン１９０となる機能モジュールの各種の物理的な具体化についても、本発明の範囲内に含まれている。
【００４６】
要求エンジン１７０は、ロケーション・キャッシュ１５０とインターフェースし、特定の移動局用のロケーション更新がいつ到着したかという知識を獲得する。また要求エンジン１７０は、個別の移動局用のアラート系サービスに対応するアラート‐トリガ条件に関連する情報を獲得するために、第２のインターフェース１４０を介してアラート系アプリケーション１３０ともインターフェースする。要求エンジン１７０は、要求スケジューラ１８０に向けてメッセージを出力するが、この種のメッセージは、特定の移動局に関する更新済みロケーション・データが必要となるデッドラインを示すデータ・エレメントを含んでいる。
【００４７】
要求スケジューラ１８０は、要求エンジン１７０によって出力されたメッセージの受信に適応されている。この要求スケジューラは、ロケーション要求がいつスケジュールされるかについて決定するために第１のインターフェースを介してネットワークとインターフェースする。要求スケジューラ１８０は、適切なコンピューティング・プラットフォーム上において実行されるソフトウエアに移植される。ここで認識される必要があるが、ハードウエアまたはソフトウエアとハードウエアの組み合わせといった具体化の変形も本発明の精神から逸脱することなく可能である。
【００４８】
要求スケジューラ１８０の役割は、特定の移動局およびデッドラインを識別する要求エンジン１７０から受け取ったメッセージ内のデータ・エレメントに基づき、その特定の移動局に関する更新済みロケーション・データが、デッドライン前にロケーション・キャッシュ１５０に書き込まれることの保証である。
【００４９】
アラート・エンジン１９０は、ロケーション・キャッシュ１５０とインターフェースして、特定の移動局から更新済みロケーション・データがいつ受信されるかについての知識を獲得する。またアラート・エンジン１９０は、その特定の移動局に関連するアラート系サービスに対応するアラート‐トリガ評価基準を獲得するために、アラート系アプリケーション１３０ともインターフェースする。ロケーション・キャッシュ１５０から獲得した情報に基づいて、アラート・エンジン１９０は、その特定の移動局がアラート系サービスに対応するアラート‐トリガ条件を満たしているか否かを決定し、満たしている場合には、アラート系アプリケーション１３０に対して、アラート発射を行うべきであることを示すトリガを送信する。さらに、最小アラート・トリガ時間に関する情報を要求エンジン１７０から受け取るために、それとアラート・エンジン１９０が（例えば、バス１０５を介して）接続されることもあり、それについては詳細を後述する。
【００５０】
次に、アラート・マネージャ１００の機能モジュール１７０、１８０、１９０のそれぞれについてより詳細な説明を行うが、まずネットワーク１１０内においてロケーション更新が要求される頻度を最小化することに関係する要求エンジン１７０から始める。この目標は、特定の移動局に関する更新済みロケーション・データに許容される遅延を与えることによって達成される。しかしながら、この遅延は、アラート系サービスに対応するアラート‐トリガ条件の取り逃がしがないことを保証するために慎重に選択されなければならない。つまり、特定の移動局ならびに特定のアラート‐トリガ条件に関して、要求エンジン１７０内の回路、ソフトウエア、および／またはコントロール・ロジックは、その特定の移動局によってその特定のアラート‐トリガ条件が満たされることの可能な、予期されるもっとも近い将来を決定する。これを、その特定の移動局ならびにその特定のアラート‐トリガ条件に関する最小アラート・トリガ時間（ＭＡＴＴ）と呼ぶことができる。
【００５１】
演算された後は、ＭＡＴＴが、その特定の移動局に関する更新済みロケーション・データをその時刻の前に受け取ることを求める要求の中に系統化され、その種の要求が、要求スケジューラ１８０に対して送信されるメッセージ内のデータ・エレメントとして供給される。この態様で決定される時点は、そのＭＡＴＴ前にその移動局が、その特定のアラート‐トリガ条件に整合することなく、したがってその間の任意の時点において受信される更新済みロケーション・データが、対応するアラート系サービスの配信の成功に関して等しい値となる、要求エンジン１７０による『知識に基づいた推測』を表す。しかしながら後述するように、後から受信されたロケーション・データは、先に受信された情報よりしばしば大きな有用性を持つことがある。ＭＡＴＴは、更新済みロケーション・データの受信に関する『デッドライン』または満了時間と呼ぶこともできる。
【００５２】
要求エンジン１７０の設計に入る２つのファクタは、ＭＡＴＴ演算のタイミングおよび移動時間の演算に使用される方法である。タイミングに関して言えば、本発明の特定の実施態様においては、特定の移動局に関する更新済みロケーション・データがロケーション・キャッシュ１５０へ書き込まれるごとに、その特定の移動局ならびにそれぞれの適用可能なアラート‐トリガ条件に関してＭＡＴＴが決定される。ここで認識される必要があるが、ＭＡＴＴを決定する演算タスクは、バックグラウンド・プロセスとして実行することができるため、要求エンジン１７０を実行するプロセッサの過負荷にならないようにし得る。このことは、要求エンジン１７０が、要求スケジューラ１８０および／またはアラート・エンジン１９０と同一のプロセッシング・ユニットを共有している場合に、かなりの節約になる。
【００５３】
ＭＡＴＴの決定に使用される方法については、可能性のある広範な移動時間の演算のアプローチのいずれも使用することができる。一例のシナリオにおいては、図２に示されているように、次の２つからなる２ステップのプロセスとしてこの演算を見ることができる：すなわち（１）移動局Ｘと目標ロケーションＹの間のユークリッド距離Ｄを決定し、それに続いて（２）距離Ｄの移動に必要な時間を決定する。目標ロケーションは、当然のことながら、懸案のアラート‐トリガ条件の関数である。
【００５４】
距離Ｄを演算するために、ロケーション・キャッシュ内のカレント値が、２つのポイントの最後の既知であったロケーション、ｌａｔＸ／ｌｏｎｇＸおよびｌａｔＹ／ｌｏｎｇＹを表しているとすれば、移動局と目標ロケーションの間の距離Ｄを、球面に沿った距離を演算するための周知の公式を使用して決定することができる。当然ではあるが、移動局のロケーションが異なるフォーマットで与えられる場合には、異なる演算が行われる。
【００５５】
Ｄの演算を完了すると、移動局の速度Ｓが獲得される。これは、輸送手段（例えば自動車）の現在のモードを前提として、例えば１８０ｋｍ／ｈというように、単純に最大可能速度とすることができる。それに代えて、限定を意図しない例を示せば、移動局の速度として移動局の瞬時速度、所定の時間ウインドウ（例えば過去５分間）にわたる移動局の平均速度、以前の２つの速度の最大値、或いは現在の地理的エリア内におけるその移動局の通常速度（履歴データを基礎とする）を採用することができる。このほかにもＭＡＴＴ演算に適した移動局の速度の演算が無数にあり、当業者にはそれが周知となるであろうが本発明の範囲内に含まれる。また、ロケーション・データ、タイミング・オフセット、或いはそのほかのテクニックを基礎とする移動局の瞬時速度または平均速度の演算方法も無数にあり、当業者には周知であろうが、それもまた本発明の範囲内に含まれる。最後に、距離Ｄを速度Ｓにより除してＭＡＴＴを獲得する。
【００５６】
ＭＡＴＴを演算するもう１つの方法は、ルーティング・アルゴリズムを使用する方法であり、道路およびそのほかの利用可能な輸送手段を用いて特定の移動局から目標ロケーションまでの最短パスを決定する。限定を意図しないこのアプローチの例を図３に示すが、目標ロケーションＹへの最短パスが、道路パターン３００の各種の操作に拘束される。第１のアプローチとして、優勢な制限速度（可能性のある速度超過を２０％まで考慮する）の関数として移動に必要な最小時間を決定するが、所用時間が信号、一時停止、渋滞等に起因してそれより長くなることはあり得る。
【００５７】
ＭＡＴＴの演算は、各種のそのほかの距離アルゴリズムに頼ることができる。適切な距離演算アルゴリズムについてのより詳細は、参照によりこれに援用している「距離を推定するための表現（Ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  ｆｏｒ  Ｅｓｔｉｍａｔｉｎｇ  Ｄｉｓｔａｎｃｅ）」と題されたクライン（Ｋｌｅｉｎ）ほかの米国特許出願第１０／０３９，５３９号を参考にすることができる。
【００５８】
ＭＡＴＴを演算するためのそのほかのアルゴリズムとして、短期予測または履歴の知識を頼ることもできる。例えば、短期予測は、時刻ｔ１の後の時刻ｔ２におけるロケーション・データを獲得することを言い、ｔ１に関するロケーション情報が既知であるが、時刻ｔ２に関するロケーション情報が未知である。そのため、これに関して要求エンジン１７０は、この予測の誤り確率が、要求しているアプリケーションに関する所定の適切なスレッショルドより低いことを理由に、そのアプリケーションに関してサーバの予測したロケーションが適切であるとの決定を行うことができる。より具体的に述べれば、そのような場合に要求エンジン１７０は、以下のテクニックのうちの１ないしは複数を実行して特定のモバイル・ステーションに関する予測ロケーションの獲得を試みることができる。
‐１ないしは複数の観察から、その特定の移動局に利用可能な最近の情報（道路、速度、方向、時刻、日）を頼り、それらをその道路に沿ってその先に配置する。
‐何らかの最近の利用可能な情報の使用に加えて、その特定の移動局のユーザに関する何らかの履歴情報（ロケーションの更新、或いは可能性のある経路または特定の時間帯に使用される可能性のある経路）を頼り、それらの経路の１つのいずれかの場所に配置することによって、そのユーザに関して経路のエンドポイントにおける可能性のあるロケーションを見つける。
‐何らかの最近の利用可能な情報の使用に加えて、ユーザグループの動きの一般的な流れ（ロケーションの更新、或いは可能性のある経路または特定の時間帯に使用される可能性のある経路）を頼り、その特定の移動局のユーザに関して経路のエンドポイントにおける可能性のあるロケーションを見つける。
【００５９】
以上から、要求エンジンの主要な役割がＭＡＴＴの決定であることが明らかであり、要求スケジューラに対して、特定の移動局に関する更新済みロケーション・データが、将来における時点ｔ０＋ＭＡＴＴまで要求されないことを伝達する（これにおいてｔ０は現在時である）。
【００６０】
本発明の変形においては、特定の移動局に関して、その時点より前に受け取った更新済みロケーション・データがＭＡＴＴの演算に帰結しない、したがって無視されることになる時点を要求エンジンに演算させると有利なことがある。この時点を、その特定の移動局に関する最早許容更新時間（ＥＡＵＴ）と呼ぶことができる。その特定の移動局に関する更新済みロケーション・データが短い時間間隔内に２回にわたって受領された場合、特に以前に演算されたＭＡＴＴがこの時間よりかなり長かった場合に、要求エンジンは、その特定の移動局に関する更新済みロケーション・データが考慮されている時点を退けることによって新しいＭＡＴＴの演算を回避することができる。言い換えると、演算リソースの節約のために、ロケーション・キャッシュに書き込まれようとしている更新済みロケーション・データの発生が、以前のロケーション更新、つまり最近のＭＡＴＴの演算のプロンプトを行ったロケーション更新に近接して続いている場合には、その種の発生を無視することが本発明の範囲に含まれている。
【００６１】
このようにＥＡＵＴおよびＭＡＴＴのそれぞれは、特定の移動局に関連するロケーション・データの更新が生じなければならない有効な時間ウインドウの開始および終了を定義する。このウインドウの設計に利用できる柔軟性は、ＥＡＵＴに関して存在する。当然のことながら、その種のウインドウの設計者は、ウインドウの総合的な長さ（一般には長いほど良好）と演算リソースの経済性（ウインドウの開始を退けること、すなわちウインドウを短縮することによって強化される）の間のトレードオフを認識しなければならない。
【００６２】
図４は、特定の移動局に関する上記に記載のセプトを例示しており、この図には、要求エンジン１７０によって定義されるＥＡＵＴ／ＭＡＴＴ時間ウインドウ４１０、４２０、４３０の各種インスタンスが水平軸４００に沿ってプロットされている。これを観察すると、時点Ｕ４１０、Ｕ４２０、Ｕ４３０において受信される更新済みロケーション・データが、常に、所定の時点において有効になるそれぞれのＭＡＴＴ、すなわちＭ４１０、Ｍ４２０、Ｍ４３０に先行して受信されていることがわかる。ここで注意を要するが、ＥＡＵＴがそれぞれのウインドウに関連付けされていた場合には、そのＥＡＵＴの手前に発生するロケーション更新は、新しいＭＡＴＴの演算をもたらさない。
【００６３】
時間ウインドウの開始、すなわちＥＡＵＴが過去の時点となり得ることも明らかである。例えば、アラート系サービスが最初に起動されたときには、ある程度の情報の古さが許容可能となることから、その特定の移動局がどこで見つかるかということについての将来の情報を獲得する必要がない。その種の状況においては、好適にも要求のスケジューリングにより要求スケジューラに負担を掛けることなく、アラート系サービスが満たされる。
【００６４】
さらにここで理解される必要があるが、１を超えるアラート‐トリガ条件が適用可能である場合（例えば、特定の移動局に複数のアラート系サービスが関連していることに起因して）、各種の条件に関して異なるＭＡＴＴを演算することが可能である。その種のケースでは、ＭＡＴＴの併合を行うと有利である。その利点は、併合により当然のことながら更新済みロケーション・データの獲得に責任のあるエンティティが、特定の移動局に関するロケーション・データの更新に関してネットワーク１１０を不必要にプロンプトすることを回避できる。ＭＡＴＴの併合を行うことによって、ネットワーク帯域幅リソースが節約される。
【００６５】
複数のアラート‐トリガ条件に関して単一のＭＡＴＴを生成する単純な方法は、更新済みロケーション・データが受信されるごとにアラート‐トリガ条件のそれぞれに関してＭＡＴＴを演算する方法である。しかしながら、以下に例示するように、それが常に必要とならないこともある。
【００６６】
次に図５を参照してＭＡＴＴの効率的な併合の一例について説明する。この場合、特定の移動局に関してＮ個のアラート‐トリガ条件Ａ１、Ａ２、．．．、ＡＮ、およびそのそれぞれのＭ１、Ｍ２、．．．、ＭＮとして示されるＭＡＴＴが存在することを前提とする。その特定の移動局に関する更新済みロケーション・データの受信時に、Ｍ＊として示されるグローバルな単一ＭＡＴＴが次のようにして作成される。
‐初期設定として、以前のＭＡＴＴが以前のＭ＊の値に等しくなったアラート‐トリガ条件を考える；言い換えると、最後にＭ＊が演算されたときに、対応するＭＡＴＴであるＭｘが支配的なＭＡＴＴであったアラート‐トリガ条件Ａｘを考える。
‐ステップ５１０において、アラート‐トリガ条件Ａｘに関する新しいＭＡＴＴ、すなわちＭｘ′を演算する。それに加えて、ステップ５２０においてＭ＊′、つまりＭｘ′に等しいグローバルＭＡＴＴをセットする。
‐残りのアラート‐トリガ条件Ａｉのそれぞれに関し（ステップ５３０参照）、以前のＭＡＴＴであるＭｉがＭ＊′より小さいか否かをステップ５４０において検証する。
‐小さい場合には、新しいＭＡＴＴであるＭｉ′をステップ５５０において演算する；さらにＭｉ′がＭ＊′より小さい場合には、ステップ５６０においてＭ＊′をＭｉ′に等しくセットする。
‐小さくない場合には、なにも行わずにステップ５７０においてＭｉ′をＭｉに等しくセットする。
‐残りすべてのアラート‐トリガ条件の検討が完了すると、ステップ５８０においてプライムが除去されてＭ＊′がＭ＊となり、１≦ｉ≦Ｎに関してＭｉ′がＭ′となる。
【００６７】
以上から、グローバルＭＡＴＴの演算において検討が必要となるアラート‐トリガ条件の数が少なくなることが明らかであり、これが演算リソースの好都合な経済性をもたらす。
【００６８】
当然のことではあるが、複数のアラート‐トリガ条件が複数の移動局に関連を有することがある場合には、上記のアプローチが極めて演算集約的となり得る。したがって、移動局ごとに単一のＭＡＴＴが生成されるように、移動局グループまたは『カテゴリ』に関して複数のアラート‐トリガ条件を扱うためのよりメモリ効率の高いテクニックを案出することが本発明の範囲内に含まれている。より具体的には、図６を併せて参照すると、一連のデータ構造Ｓｊが作成されており、ｊは、次に示すクエリがサポートされる『カテゴリ』を表す：特定の移動局のロケーションおよび、その特定の移動局がマップされる『カテゴリ』が与えられたとき、その特定の移動局と、その特定の移動局に関する『もっとも近い』『アラート領域』の間における正確な、或いは概略の『移動時間』を返す。
【００６９】
『カテゴリ』は、特定の共通セットのアラートがすべて関係することができるユーザの選択されたグループを意味する。したがって、各移動局は、ゼロ以上のカテゴリにマップされている。Ｋ≧１とするＫ個のカテゴリが存在し、Ｋのカテゴリｊに対応するデータ構造を表すＳｊを伴うという仮定が可能である。『移動時間』は、移動時間のグラフ表現を用いる測定を意味し、２つのノードもしくはグラフの辺に対応するパスの最小コストとすることができ、グラフは辺上のコストを伴う有向または方向性のないグラフになる。『アラート領域』は、地理的なロケーションであって、移動局がその領域に入ったとき、アラート発射をトリガする領域を意味する。『もっとも近い』は、移動時間が最小となるアラート領域を意味する。
【００７０】
次に（１）データ構造Ｓｊ内に何が含まれるか；（２）どのようにしてデータ構造Ｓｊは、特定の移動局に関するロケーションならびにその特定の移動局がカテゴリｊにマップされるという知識を受け取ったことに応答して移動時間を返すか；（３）どのようにして最初にデータ構造Ｓｊが埋められるか；さらに（４）どのようにしてデータ構造Ｓｊが更新されるかについて説明する。
【００７１】
（１）データ構造Ｓｊは、以下を含む：
（ｉ）移動局のローミングが許される２次元空間のセルへの細区分；その細区分の各セルについて、そのセル内に見つかる移動局がすべて同一のアラート領域に対してもっとも近くなるという特性を伴う。図６においては３つのアラート領域Ｘ、Ｙ、およびＺが存在し、したがって３つのセル６２０ａ、６２０ｂ、６２０ｃが存在する。この場合、セル６２０ａ内の移動局はアラート領域Ｙともっとも近くなり、セル６２０ｂ内の移動局はアラート領域Ｚともっとも近くなり、セル６２０ｃ内の移動局はアラート領域Ｘともっとも近くなる。
（ｉｉ）ステップ（１）の（ｉ）において作られた細区分に関するポイント‐ロケーション・データ構造６３０；ステップ（１）の（ｉ）において設定されたセルと、離散的かつ仮想的な、平面をカバーし、それらに割り当てられた実際のポジションを有するノード６１０ａ、６１０ｂ、６１０ｃとの間の関係を表す（移動時間の演算を補助する）。
（ｉｉｉ）ステップ（１）の（ｉ）において作られた細区分のセルによってインデクスされ、各エントリがそのセル内の『ノード』（（１）の（ｉｉ）参照）にもっとも近いアラート領域を指定するテーブル６４０。変形においては、その領域までの移動時間が、そのセル内の『ノード』から任意のほかのアラート領域までの最小移動時間のパーセンテージ内となるアラート領域をエントリで指定することもできる。『テーブル』は、何らかの種類のインデクスを用いた高速ルックアップを可能にするデータ構造、例えばアレイ、ハッシュ・テーブル、平衡サーチ・ツリー等を意味する。
【００７２】
（２）データ構造Ｓｊは、以下の方法に従ってロケーション・データに応答して移動時間を返す：
（ｉ）ステップ（１）の（ｉｉ）におけるポイント‐ロケーション・データ構造を使用してステップ（１）の（ｉ）における細区分のいずれのセルがユーザのカレント・ロケーションを含んでいるかを決定する。
（ｉｉ）ステップ（１）の（ｉｉｉ）のテーブルを使用し、ステップ（２）の（ｉ）において見つけ出したセルに関連付けされるアラート領域を決定する。
（ｉｉｉ）コスト関数またはそのほかのテクニックを使用して、ユーザのカレント・ロケーションからステップ（２）の（ｉｉ）において見つけ出したアラート領域までの正確な、或いは概略の移動時間を決定する。
オプションとして、詳細を後述するが、ステップ（ｉｉｉ）に先行して、ステップ（２）の（ｉｉ）において見つけ出したアラート領域が特定の適格性或いは適用可能性の条件を満たしていることの保証を行うことができる。
【００７３】
（３）データ構造Ｓｊは、次に示す方法に従って最初に作り出される：
（ｉ）各ノードについて、カテゴリｊのユーザに適用可能なもっとも近いアラート領域を演算する。移動時間が辺の重み付けを伴うグラフによって表されることを前提とすると、ダイクストラのアルゴリズム等の従来の最短経路アルゴリズムの単純な適合によってこのステップを行うことができる。
（ｉｉ）各セルが正確に１つのノードを含む平面細区分（図７Ａ参照）を見つけ出す。この種の平面細区分は、ノード７１０のボロノイ図７２０である。ポイントのセットのボロノイ図を演算するためのアルゴリズムは、当業者にあっては周知となろう。ここで注意が必要であるが、この平面細区分は、アラート領域に依存せず、したがって一度だけ演算し、すべてのカテゴリの処理が終わるまでストアしておくことができる。結果は、それぞれが各ノード７１０を囲む複数のセル７３０になる。
（ｉｉｉ）同一のもっとも近いアラート領域を有する細区分のセルを併合する（図７Ｂ参照）。これを行う１つの方法は、次に述べる併合ステップの繰り返し適用による。その細区分内に２つの隣接セル（例えば７３０Ａ、７３０Ｂ）があり、一方のセル内のノードに対してもっとも近いアラート領域が、他方のセル内のノードに対してもっとも近いアラート領域と同じになる場合には、それらの細区分から両方のセルの境界上にある線分を除去する。このステップを、その種の隣接セルがなくなるまで繰り返す；最終的に、より大きなセル７４０が残る。
（ｉｖ）これらのセル７４０を使用してステップ（１）の（ｉｉｉ）のテーブルを埋める。
（ｖ）ステップ（３）の（ｉｉｉ）において見つけ出した細区分は、ノードのセットのパーティションを定義し、２つのノードがその細区分の同一セル内にあるとき、それらがパーティションの同一ブロックに従属する。ヒューリスティックを適用し、ノードのパーティションを変更することなく、ステップ（３）の（ｉｉｉ）において見つけ出された平面細区分を定義する線分の数を低減する。例えば図７Ｂのセル７４０は、図７Ｃのセル７４０′のようになる。
ステップ（３）の（ｖ）における使用に適した１つのヒューリスティックは、次に示す改善を使用する。図８Ａを参照し、例えば線分Ｌ１およびＬ２が１つのエンドポイントＰを共有しており、その平面細区分内のほかの線分はＰに入射しないと仮定する。図８Ｂを参照し、Ｌ１のＰでないエンドポイントと、Ｌ２のＰでないエンドポイントを結ぶ線分をＬとする。線分Ｌ、Ｌ１、およびＬ２によって構成される三角形がノードを含むか否かをチェックする。含まなければ（図８Ｂのケース）、その平面細区分内のＬ１およびＬ２をＬによって置き換える（図８Ｃ参照）。このヒューリスティックを、適用可能なものがなくなるまで、これらの改善ステップに適用する。
このほかにも、非特許文献１およびここに引用している文献によって与えられているものから（３）の（ｖ）における使用に適したヒューリスティックを導出することができる。
ステップ（３）の（ｖ）に対する別の変形は、少量の近似誤差の導入である。これは、ステップ（３）の（ｉｉｉ）において見つけ出された細区分にヒューリスティックを適用し、線分の数を減らすことによって行われる。より具体的に述べれば、ノードＶからセルＣに関連するアラート領域までの移動時間‐‐ステップ（１）の（ｉｉｉ）のテーブルから‐‐が（指定の、または絶対誤差の範囲内において）ノードＶからもっとも近いアラート領域までの移動時間を近似する場合に、異なるセルＣに対するノードＶにより多くの余裕を見込む。例えば、ステップ（３）の（ｖ）に述べられているヒューリスティックを変形して、Ｌ、Ｌ１、およびＬ２によって形成される三角形がノードを含む場合にＬによってＬ１およびＬ２を置き換えると、それらのノードを含むセルが変更されることになる；さらに、それらのノードのそれぞれに関して、新しいセルに関連付けされるアラート領域までの移動時間が、実際のもっとも近いアラート領域までの移動時間より著しく大きくならない（例えば１０％まで）ときには前述の置換を行う。
【００７４】
（４）データ構造Ｓｊは、次の方法に従って更新される：
（ｉ）新しいアラート領域までの移動時間が以前に選択されたアラート領域までの移動時間より小さいノードのセットを見つけ出す。このステップは、新しいアラート領域までの移動時間が、ノードＶを含むセルに関連するアラート領域までの移動時間より長いノードＶの近隣を探索しないように修正された従来型の最短経路サーチを、新しいアラート領域をルートとして使用することによって迅速に行うことができる。
（ｉｉ）ステップ（４）の（ｉ）において見つけ出されたノードのセットを囲い込み、ほかのノードを含まない多角形（または多角形のセット）を作る。これは、いくつかの方法を使用して行うことができる。１つの方法は、見つけ出されたノードのセットの凸状の外殻を見つけ出し、凸状の外殻の境界をずらしてほかのノードを除外する。別の方法は、ステップ（３）の（ｉｉ）において見つけ出された平面細区分のサブセット、すなわちステップ（４）の（ｉ）において見つけ出されたノードを含むセルの境界を構成するサブセットから開始する。ステップ（３）の（ｉｉｉ）における場合と同様に、反復的に隣接するセルを併合する。後者のアプローチが採用される場合には、ステップ（３）の（ｉｉ）において見つけ出された平面細区分が保持されている必要がある。これは、その種の平面細区分が１つだけ存在することから、つまり各カテゴリごとに１つ存在するのではないことから、メモリ要件を軽減する。
【００７５】
要求エンジン１７０が、特定の移動局に関する更新済みロケーション・データの受信が可能になる時間ウインドウを生成することによって、要求スケジューラ１８０は、ネットワークの帯域幅リソースに関する制約を減じる実質的な効果とともに、ロケーション更新のための要求の発行をより効率的に管理することが可能になる。
【００７６】
より具体的に述べれば、要求スケジューラ１８０の機能を提供するプログラム・エレメントは、２つの主要なモジュールを有している：すなわち、（１）いつＰＤＥによってロケーション要求のサービス提供が行われるかについて決定する各種の演算を実行するスケジューリング・モジュール、および（２）スケジューリング・モジュールと外部エンティティの間のデータの受信／送信を可能にするＩ／Ｏモジュールである。
【００７７】
要求スケジューラ１８０は、２つのタイプのロケーション要求を処理する。第１のタイプは、即時のサービス提供を要求する即時タイプである。第２のタイプは、特定の時間Ｔ以内にＰＤＥ１６０によるサービス提供を要求する遅延ロケーション要求である。遅延ロケーション要求は、要求にサービス提供を行うデッドラインを指定するそれぞれの満了時間と関連付けされる。要求スケジューラ１８０は、サービス提供を受けることになるロケーション要求データ・エレメントを受け取る。各ロケーション要求データ・エレメントは、１つのロケーション要求に対応する。ロケーション要求データ・エレメントは、要求されているロケーション・データに加えて、要求にサービス提供を行う適切な時点を要求スケジューラ１８０が決定できるようにするパラメータを含む。パラメータの１つは、要求のタイプであり、即時または遅延のいずれかになる。遅延要求の場合には、満了時間が提供される。
【００７８】
ここで注意する必要があるが、要求スケジューラ１８０が、ロケーション要求に関するすべての要求を受け取る必要はない。要求スケジューラ１８０が満了時間データおよび、いつ各種のロケーション要求にサービス提供が行われるべきかを決定する上で必要なそのほかのデータだけを受け取るアプリケーションを、本発明の精神から逸脱することなく企図することができる。
【００７９】
要求スケジューラ１８０は、ＰＤＥ１６０の過負荷が回避されるようにするためには、いつロケーション要求にサービス提供が行われるべきかを決定する。ＰＤＥ１６０の使用がより効率的に使用されるように、いくつかのスケジューリングのアプローチを組み合わせて、或いは個別に具体化することができる。
【００８０】
この種のアプローチの１つは、遅延タイプの要求のサービス提供を人為的に延期することである。『人為的な延期』は、ＰＤＥ１６０がロケーション要求の即時のサービス提供に利用可能であるか、或いはサービスのための要求が実際にＰＤＥ１６０へ送信する前に利用可能である場合であっても、特定の時間にわたってロケーション要求のサービス提供が遅延されることを意味する。遅延ロケーション要求のサービス提供の人為的な延期は、要求スケジューラ１８０によるロケーション要求の優先順位設定を可能にし、その結果、ＰＤＥ１６０によってより多くのロケーション要求が、そのキャパシティを超えることなくサービス提供が行われるようになる。それに加えて、デッドラインＴまではロケーション・データが必要でないことから、またもっとも新鮮なデータがもっとも有用であることから、要求が遅く（ただし、Ｔ以前に）満たされるほど一般に良好になる。
【００８１】
遅延タイプのロケーション要求のサービス提供の人為的な延期は、固定アプローチに従って、或いは柔軟なアプローチに従って行うことができる。『固定アプローチ』は、サービス提供が、デッドラインＴを超えることなく一定の期間まで延期されることを意味する。『柔軟なアプローチ』は、次に示す２つのパラメータを基礎として延期を調整する演算を伴う：すなわち（１）ロケーション要求を分散させてＰＤＥ１６０のキャパシティの超過を避けるパラメータ；および（２）可能な限りデッドラインＴに近づけてロケーション・データを分布させるパラメータである。ここで認識されることになろうが、このほかの人為的な延期を調整するためのストラテジを、本発明の精神から逸脱することなく具体化することも可能である。
【００８２】
前述のスケジューリング・アプローチとは独立に、或いはそれとともに使用可能な別のスケジューリング・アプローチは、同一のロケーション系サービス（ＬＢＳ）アプリケーションにより所定期間にわたって行われたいくつかのロケーション要求といった同一のロケーション・データを用いて満たすことが可能な複数のロケーション要求を識別し、同一のロケーション更新を用いてそれらの要求にサービス提供を行うことである。遅延タイプの要求の場合においては、すべての要求のサービス提供を、それぞれの満了時間前にそれが生じるようにタイミング設定することによってこれを達成することができる。より具体的に述べれば、併合することの可能な各種の要求を、それぞれの満了時間とともに識別し、満了時間を用いてそれらに順序付けする。その後、サービス提供を求める要求を、最も早い満了時間を有するロケーション要求に適切にサービス提供が行われるようにＰＤＥ１６０に対して送信する。ＰＤＥ１６０からロケーション・データが受信されたとき、併合されたすべてのロケーション要求が満たされる。このアプローチは、併合されたロケーション要求のすべての満了時間に超過のないことを条件に、前述した人為的な延期をサポートする。
【００８３】
さらに別のスケジューリング・アプローチの可能性は、非同期ロケーション・データを利用してロケーション要求にサービス提供を行うことである。ロケーション・データは、同期態様においてＰＤＥ１６０から獲得可能であり、言い換えるとロケーション・データに関する要求をＰＤＥ１６０へ送信し、この要求に対してＰＤＥ１６０が、そのロケーション・データを含む応答を返すという形で獲得することができる。ロケーション・データは、参照により内容をこれに援用している前述のイオッペ（Ｉｏｐｐｅ）ほかの特許出願に詳細が述べられているように、非同期で獲得することも可能である。この種の非同期ロケーション・データは、ロケーション・キャッシュ１５０内にストアされる。
【００８４】
要求スケジューラ１８０が即時タイプの要求を受け取ったとき、要求スケジューラ１８０は、ロケーション・キャッシュ１５０と通信を行い、この要求を満たすことのできるロケーション・データをロケーション・キャッシュ１５０が有しているか否かを決定する。有している場合には、要求スケジューラ１８０内においてこのロケーション・データによって満たされるロケーション要求が無視され、ＰＤＥ１６０に対してロケーション・データを求める要求は行われない。ロケーション要求を発したアプリケーションに対して、過度に新鮮でないロケーション・データが利用可能とされる状況を避けるために、即時タイプのロケーション要求が修正されて、新鮮でないデータを受け入れるか否か、および新鮮でない程度（許容可能とするもっとも古いデータ）を示すフィールドが含められる。それに加えて、ロケーション・キャッシュ内にストアされているロケーション・データにタイムスタンプが関連付けされている。したがって、要求スケジューラ１８０は、ロケーション・キャッシュ１５０が即時タイプの要求を満たすことのできるデータを含んでいるか否かについて決定し；含んでいる場合には、そのロケーション要求が要求スケジューラ１８０から無視され；含んでいない場合には、ＰＤＥ１６０に対する要求が行われて、新鮮なデータが獲得され、その後はロケーション要求が無視される。
【００８５】
遅延タイプの要求においては、ロケーション要求が人為的に延期されていることから数回にわたるロケーション・キャッシュ１５０のサーチが可能となることを除けば、同一のオペレーションを実行することができる。ロケーション・キャッシュ１５０内において適切なロケーション・データを見つけ出すことができなかった場合には、その遅延タイプの要求の満了時間前にそのサービス提供が可能となるようにＰＤＥ１６０に対する要求が行われる。
【００８６】
さらに別のスケジューリング・アプローチの可能性は、ＰＤＥ１６０からロケーション・キャッシュ１５０へ送信された、即時タイプのロケーション要求（このロケーション・データは同期である）にサービス提供を行うロケーション・データを調べ、それを使用して、その時点において要求スケジューラ１８０が未決にしている遅延タイプの要求にサービス提供が可能か否かを決定することである。それが可能である場合には、そのロケーション・データが即時タイプならびに遅延タイプの要求の両方にサービス提供を行う。
【００８７】
次に、前述したスケジューリング・アプローチの１ないしは複数に従った要求スケジューラ１８０のオペレーションの具体的な例について説明する。ここで理解される必要があるが、この例は要求スケジューラ１８０の動作の単なる例証であり、限定的な態様で解釈されるべきものではない。
【００８８】
以下において、ＰＤＥ１６０が所定の、固定された最大負荷を有しているものと仮定する。またこの負荷が、秒当たりＮ個の要求として与えられるものとする。要求スケジューラ１８０は、各秒が、Ｎ個のスロットに分割されるように、時間を離散的なタイム・スロットに分割する。要求スケジューラ１８０の目的は、遅延タイプの要求をタイム・スロット内に、スロット当たりのその数が１を超えないように入れることであり、その結果として、可能な場合には、そのスロットにサービス提供を行う時点がＴを超えるスロット内に要求が含まれることなく、かつ、この制限を前提として、要求が可能な限り遅いタイム・スロットに割り当てられるようにする。プレゼンテーションの簡素化のため、Ｔが１／Ｎ秒を単位として与えられるものとし、したがって時間Ｔに対応するスロットに続く次のスロットは、時間Ｔ＋１に対応することになる。
【００８９】
この種のスケジューリングが可能でない場合もある。例えば、秒当たりの要求の数がＮを超える場合には、ＰＤＥ１６０の負荷リミットを超えることなくそれらの要求にサービス提供を行うことは不可能になる。その種の条件下においては、ロケーション要求が遅延され、その状況が継続する場合には、最終的に要求が脱落する。
【００９０】
新しい遅延タイプのロケーション要求が与えられると、要求スケジューラ１８０は、もっとも遅いスロットであって、そのスロットへのサービス提供の時間がＴより小さいスロットＳを探すが、その結果として得られるＳは、空であるか、或いはＴより小さいかそれに等しい満了時間を伴うロケーション要求によって占有されている。いずれの場合においても、新しいロケーション要求をタイム・スロットＳ内に配置する。そのスロットがすでに占有されている場合には、オリジナルのロケーション要求を１スロットだけ早いスロットにプッシュする。そのスロットも占有されていた場合には、そのロケーション要求をさらに早いスロットにプッシュする。占有されていないタイム・スロットに達するまで、或いはスロットがなくなるまで（つまり、現在の時点に対応するスロットまでスロットが占有されるまで）これを繰り返す。（後者が生じた場合には、時間Ｔまで、新しいロケーション要求にサービス提供ができない；時間Ｔ＋１によるスケジュールを試みる必要がある。）
【００９１】
即時タイプの要求（同期）または電話レジストレーションもしくはそのほかの電話イベント（非同期）のいずれかに起因して、任意の時点においてユーザに関するロケーション更新が到来する場合には、そのユーザに対応するあらゆる遅延タイプの要求をそのスロットから削除し、そのロケーション更新を介してサービス提供を行う。
【００９２】
ここで、即時タイプならびに遅延タイプの要求のいずれもが、キャッシュされたロケーション・データのタイムスタンプおよび要求の個々の必要条件に応じて、キャッシュされた値によって解決され得ることに注意する必要がある。複数の遅延タイプの要求が同一のユーザに関して行われた場合には（つまり、許容可能な要求時間の『ウインドウ』のオーバーラップ）、単一の要求を用いてそれらが解決される。
【００９３】
上記のアルゴリズムを具体化する１つの可能性のあるアプローチは、要求スケジューラに、循環アレイとして構成されているストレージ・メディアを備え、アレイのそれぞれのエレメントにタイム・スライスを割り当て、最後のセクションにおいて述べた手順のシミュレーションを行うことである。しかしながらこれは、挿入／削除オペレーションがＯ（ｎ）処理時間（ｎは未決のスケジュール済み要求の数）を必要とすることから、パフォーマンス上の問題を招く。
【００９４】
可能性のある別のアプローチは、サーチ・ツリー・データ構造（バイナリ・サーチ・ツリー等）の使用であり、それぞれの未決の遅延タイプの要求がノードによって表され、各ノードが、対応する要求の満了時間Ｔに従って順序設定（サーチ・ツリーの順序）される；要求に関する情報（満了時間Ｔを含む）に加えて、各ノードにおいて補助情報が維持され、ＰＤＥ１６０に対して次の要求が発行されるべき時間の迅速な演算が可能になる。各ノードにおいて維持される補助情報は、サーチ・ツリー内のそのノードの子孫（ノードの子孫はそのノード自体も含む）にのみ依存し、そのノードの子における補助情報から容易に演算される必要がある。
【００９５】
新しい遅延タイプの要求が到来したとき、対応する新しいノードがツリーに挿入される；新しいノードに関する補助情報は、迅速に演算可能であり、そのノードの祖先に関する補助情報の再演算が可能である。要求が（ＰＤＥ１６０に対して発行済みとなったこと、或いは対応するユーザに関するロケーション更新が受領されたことに起因して）削除されると、対応するノードが削除され、削除されたノードの祖先であったノードにおいて補助情報が更新される。さらに、サーチ・ツリー内においてローテーション（サーチ・ツリー・データ構造により平衡を維持するために要求される）が行われる場合には、そのローテーションの結果として子孫が変化したノードに関する補助情報の再演算を行うことができる。
【００９６】
サーチ・ツリー・データ構造（例えば、レッド‐ブラック・ツリー）は、ｎをノードの数とするときＯ（ｌｏｇ  ｎ）時間内の挿入および削除をサポートすることが知られている。この種の構造の使用は、Ｏ（ｌｏｇ  ｎ）時間内に要求に入ること、およびＯ（ｌｏｇ  ｎ）時間内にＰＤＥ１６０に対して発行される次の要求の時間が決定することを保証する。
【００９７】
上記を実現する１つの方法は次のようになる。このサーチ・ツリーはバイナリ・サーチ・ツリーである（それぞれのノードは、多くとも２つの子しか持っていない）。サーチ・ツリーのノードにおける補助情報は、２つの整数ラベル、ｕおよびｖを有している。ラベルｖは、ツリー内の所定のノードの子孫の数に等しい。（ノードの子孫には、そのノード自体も含まれる。）ラベルｕは、システム内に入る要求がそのツリー内のそのノードの子孫に関する要求だけであった場合に要求がスケジュールされる最も早いタイム・スロットを表す。ノードのラベルｕおよびｖの１つの重要な特性は、それらがそのノードの子孫にのみ依存するということである。
【００９８】
第３のラベルｗは、そのシステムに入るすべての要求を考慮した、このノードに対応する要求の実際のスケジューリング時間を表す；ｗラベルは、維持されずに必要に応じて演算され、その後に破棄される。ノードのｗラベルを演算する方法については後述する。ｗラベルが維持されないということは、データ構造の効率にとって重要である（それらが維持されるとした場合には、新しい要求が処理されるときに多くのそれらのラベルを変更しなければならず、それらのラベルの変更には多くの時間が必要になる）。
【００９９】
すでに述べたように、新しいノードがバイナリ・サーチ・ツリー内に（新しいロケーション要求の処理の一部として）挿入される場合に、新しいノードのラベルｕおよびｖに関する値が再演算され、新しいノードの祖先のラベルに関する値が再演算される（各祖先の子孫のセットが変化することから）。これらの演算は、新しいノードを始点とし、ツリーを上に（ルートに向かって）祖先を１つずつ遡って行われる。同様に、サーチ・ツリー内においてローテーションが実行されるときには、そのローテーションによって子孫が変更されたノードに関するラベルｕおよびｖの値の再演算を行わなければならない。（バイナリ・サーチ・ツリー内のローテーションでは、２つのノードの子孫だけが変更される。）
【０１００】
各ノードについて、ｖの値は、１＋ｖＬ＋ｖＲとして演算され、ｖＬはそのノードの左側の子のｖラベルの値（存在する場合；存在しなければ０）であり、ｖＲはそのノードの右側の子のｖラベルの値（存在する場合；存在しなければ０）である。ｕの値は、ｕＬ、Ｔ‐ｖＬ、およびｕＲ‐ｖＬ‐１のうちの最小値として演算され、ｕＬはそのノードの左側の子のｕラベルの値、ｕＲはそのノードの右側の子のｕラベルの値、Ｔはそのノードに対応する要求のデッドラインである。
【０１０１】
すべての未決の要求がサーチ・ツリーのルートのいくつかの子孫によって表されることから、ルートにおけるｕラベルの値は、ＰＤＡに対して要求が送信されなければならない最も早いタイム・スロットを与える。したがってシステムは、所定の時点に、その時点における要求の送信が必要か否かについて、ｕラベルを調べ、かつその値と現在時を比較することによってチェックすることができる。次に送信されることになる要求は、ルートの最左翼の子孫によって表される要求になる；このノードは、単純なプロシージャにより充分に見つけることができる。
【０１０２】
要求が処理されなければならない最も早いタイム・スロットを見つけ出すために、システムは、サーチ・ツリーのルートにおけるｕラベルを調べる。システムは、その最も早いタイム・スロットに対応する時点と、現在時を比較し、現在時においてそのロケーション要求の処理が必要か否かを決定することができる。所定のノードに関するこの演算は、以下のように効率的に行うことができる。
【０１０３】
最初にバイナリ・サーチ・ツリーのルートにおいてｗを演算する。これは、最右翼ノードから開始し、ルートまで遡ることによって行われる。それに沿って、中間のｗ値をｕ、ｖに関して演算することが可能であり、存在する場合には右側の子のｗについても可能である。ルートから開始し、左および右の子のｗ値を、必要に応じて局所的に演算することができる。内側のノードに対応する要求についてのｗ値（つまり、スケジューリング・スロット）が演算可能になった後は、スケジューリングに関する適切な要求の除去は、１ないしは複数の要求が、そのバイナリ・サーチ・ツリーから削除されるべく準備が整っているかを調べるという単純な問題になる。
【０１０４】
サーチ・ツリー自体に加えて、関連するロケーション要求を識別する別のデータ構造（例えばハッシュ・テーブル）も利用されることがある。例えば、ワイヤレス・ネットワーク内のユーザに関連するロケーション要求がある場合、このデータ構造は、ユーザごとに、そのユーザのロケーションに関する要求に対応するすべてのノードをマップする。ユーザに関するロケーション更新の到来時には、このデータ構造によって、システムが、そのユーザのロケーションに関する未決の要求にサービス提供を行い、対応するノードを（それらの祖先に関する補助情報を更新し）サーチ・ツリーから削除することが可能になる。
【０１０５】
要求スケジューラ１８０は、そのＩ／Ｏにおいて受け取った各種の要求のサービス提供の順序を決定すると、それらの要求のサービス提供が可能となるように、それをＰＤＥ１６０へ伝える。要求スケジューラ１８０が、全ロケーション要求情報をＰＤＥ１６０へ送信することも可能であり、或いはそれらの要求のサービス提供の順序を示す特定のデータを用いて、それらの情報に対するポインタを送信することも可能である。要求がＰＤＥ１６０によってサービス提供が行われると、ＰＤＥ１６０によって返されたロケーション・データがロケーション・キャッシュ１５０へ送られる。それに代えてＰＤＥ１６０は、ロケーション要求を発行したロケーション・アプリケーションを実装しているエンティティに対して直接ロケーション・データを発行することができる。このオプションには、ロケーション要求データ内において、そのエンティティのアドレスをＰＤＥ１６０へ渡すことが必要になる。
【０１０６】
ここで認識されることになろうが、本発明の精神から逸脱することなく、ロケーション要求を発行したエンティティ、要求スケジューラ１８０、およびＰＤＥ１６０からの情報の送信を可能にする広範多岐にわたるメッセージング・スキームを使用することができる。
【０１０７】
特定の移動局に関する更新済みロケーション・データの受領時に、アラート‐エンジンは、特定のアラート系サービスに関連するアラート発射をトリガするか否かを決定する。これは、最初に、存在する場合にはいずれのアラート系サービスに関して、少なくとも１つのアラート‐トリガ条件が特定の移動局によって満たされたるを決定することによってもたらされる。その種の条件が満たされるときには、アラート‐エンジンがアラート系アプリケーションに対して、アラートのファイアを行うべきであることを知らせるトリガを送信する。
【０１０８】
ここで注意が必要であるが、移動局がそのアラートの受領者となることもあれば、ならないこともある。本発明を説明するという目的に関して言えば、アラート・エンジンからアラートをトリガするべくメッセージを受領したことに応答してアラート系アプリケーションによって行われるアクションに関する詳細に入る必要はない。
【０１０９】
本発明の一実施態様によれば、アラート‐トリガ条件が、ロケーション・キャッシュ内に提供されるとき、移動局のロケーションに関連付けされる。その種のロケーション・データは、要求スケジューラによって発行されたロケーション・データの更新に関する要求に責任のある受動的ポジション決定エンティティ或いは能動的ポジション決定エンティティからのロケーション更新の受領に応答して、ロケーション・キャッシュ内へ書き込まれるようにできる。
【０１１０】
本発明の各種実施態様においては、特定の移動局に関する更新済みロケーション・データによってその特定の移動局が次の項目に該当することが示されるとき、その特定の移動局によってアラート‐トリガ条件が満たされたと見なす。
‐  所定の将来の時点において、目標ロケーションから所定の最大距離内に位置が特定されること；
‐  所定の時間範囲の間において、目標ロケーションから所定の最大距離内に位置が特定されること；
‐  所定の目標の地理的エリア内へ入ったこと；
‐  所定の目標の地理的エリア外へ出たこと；
‐  所定の時点において、所定の目標の地理的エリア内に位置が特定されること；
‐  所定の時点において、所定の目標の地理的エリア外に位置が特定されること；
‐  あらかじめ定義済みの移動経路の混雑部分（移動局のユーザによって入力されたか、或いは履歴データから演算されたものとすることができる）に向かっていること；
‐  特定の方向または場所へ向かっていること；（例えば、家、仕事先）；
‐  特定の方向または場所からはなれつつあること；
‐  交通が混雑しているエリアへ向かっていること；
‐  速度が所定の上限を超えていること；および／または
‐  速度が所定の下限を超えていること。
【０１１１】
明らかに、ＭＡＴＴに依存する上記のアラート‐トリガ条件が満たされることの保証は、特定のインジケータ（例えば、方向、速度）が時間的に変化し得る突発性に関する追加の仮定を必要とする。例えば、高速道路の直線部分に沿って移動している移動局が、その方向を維持し、次のロケーション更新が受信される前に突然の右折を行うことはないと仮定する方が安全であると見られる。
【０１１２】
本発明の別の実施態様においては、特定の移動局に関する更新済みロケーション・データによって、所定の時間にわたり、所定の目標の地理的エリア内において、その特定の移動局の位置が特定されていることが示されるとき、その特定の移動局によってアラート‐トリガ条件が満たされていると見なす。場合によっては、所定の『時間』を、所定の回数にわたり入力において更新済みロケーション・データが連続して受信されたこととしてもよく、別の場合には、所定の『時間』を所定の長さの時間としてもよい。また、所定の『時間』を、時間および連続的なロケーション更新の組み合わせとして定義することも可能である。
【０１１３】
本発明のさらに別の実施態様においては、特定の移動局に関する更新済みロケーション・データによって、所定の時間にわたり周辺の目標エリア内においてその特定の移動局が特定されていることが示されるとき、その特定の移動局によってアラート‐トリガ条件が満たされていると見なす。漸増的な周辺エリアは、複数になることもある。その種の周辺エリアのそれぞれに関する時間的な量は、周辺エリアを目標エリアに関係づける方法と直接関係させることが可能であり、言い換えると、より周辺のエリア内にあるほど、移動局は、アラート・エンジンがアラートをトリガするまで、そのエリアを占有しなければならなくなる。
【０１１４】
限定を意図しない例として図９を参照すると、目標領域を例えば円Ｂ０とすると、漸増する半径を有するいくつかの同心の帯域Ｂ１、Ｂ２が、目標領域Ｂ０の周囲に作られる。その種の帯域は、特定の時間量またはロケーション更新の数に関連付けされ、アラートをトリガするためには、それらの時間量または更新の数にわたってその帯域の中において特定の移動局が見つけられなければならない。つまり、その特定の移動局が目標エリアＢ０へ入るときにだけトリガするのではなく、アラート・エンジン１９０は、この必要条件を緩和し、周辺の帯域Ｂ１、Ｂ２の一方におけるその特定の移動局の複数回にわたる観察によっても同様に必要条件が満たされるようになる。これは、目標エリアＢ０が任意に選択されるか、或いはサービス提供の初期段階においてより良好な定義が必要とされる場合に有利である。また、特定の移動局が長い期間にわたって目標エリアＢ０に『近づいている』ときにアラート発射をトリガする方が、その特定の移動局が実際に目標エリアへ入るか否かについてリソースを連続的に消費してモニタを行うよりもコスト的に有利になることがある。
【０１１５】
引き続き図９を参照し、加えて図１０を参照すると、アラート・エンジン内にストアすることのできる特定の移動局の挙動をモニタするためのテーブル１０００の漸進的変化の例が示されている。ここで注意を要するが、この例の目的に関して言えば、懸案の移動局が帯域Ｂ２内において５回の瞬間またはロケーション更新を経験する場合、帯域Ｂ１内において３回の瞬間またはロケーション更新を経験する場合、或いはエリアＢ０内において単一回の観察がある場合に、アラート‐トリガ条件が、この場合に関して満たされると仮定する。この帯域に関する『回数』という用語は、その帯域の中で移動局が観察された回数を意味するものとして以下において使用されている。
【０１１６】
時刻ｔ１においては、この移動局が両方の帯域の外にあり、それぞれの帯域に関するカウントはゼロである。時刻ｔ２においては、この移動局が帯域Ｂ２に入り、それによって帯域Ｂ２に関する回数が１に増加する。時刻ｔ３においては、この移動局が帯域Ｂ１内に入りそれによって帯域Ｂ１に関する回数が１に増加する。時刻ｔ４においては、この移動局が再び帯域Ｂ２に入り、それによって帯域Ｂ２に関する回数が２に増加するが、帯域Ｂ１に関する回数がリセットされる。最後に、時刻ｔ５においては、この移動局が帯域Ｂ１に再入することなく帯域Ｂ２を離れ、それによってすべての帯域に関する回数がゼロまで下がる。したがって、この場合にはアラートがトリガされない。
【０１１７】
上記から認識されようが、特定の条件下においては、ロケーションの更新を知ったときにアラート‐トリガ条件が満たされているか否かの評価を実行しない方がアラート・エンジンにとって有利になることがある。例えば要求エンジンが、特定の移動局に関する最小アラート・トリガ時間（ＭＡＴＴ）を決定していることがあり、その場合にＭＡＴＴに先行する更新済みロケーション・データの受信は、その特定の移動局に関するアラート‐トリガ条件が満たされているか否かによらず、アラート・エンジンに評価を行わせる理由をほとんど提供しないか、或いはまったく提供しない。この種の条件は、それがＭＡＴＴを定義する方法であることから満たされることはない。したがって、条件が満たされているか否かによらず、評価を行わないことは、アラート・エンジン内の演算リソースを節約することになる。しかしながら、それにもかかわらず場合によっては、要求エンジンのＭＡＴＴの演算に誤り（例えば、移動局の速度に関する誤った仮定）があったときの支援手段として、条件が満たされているか否かの評価を行うことが慎重策となることもある。
【０１１８】
前述したロケーション‐ベースの条件に加えて、適格条件または適用可能条件と呼ぶことのできるそのほかの条件を適用してもよい。例えば、アラート系サービスに関連するアラート発射を、その特定の移動局が移動局の選択されたグループのメンバである場合、例えば共通の人口統計学的特性を共有するユーザに関連する移動局グループ、或いは共通のアラート系サービスの加入者もしくは共通した挙動の特徴を有するユーザに関連する移動局グループのメンバである場合に限って可能にすることができる。後者の例は、例えば、個人的な癖または好みに言及することができる。別の場合においては『挙動の特徴』が、移動局のオンまたはオフ、或いは移動局のユーザがしばしば訪れる場所に関係する時間的なパターンの認識を包含することを意味する。
【０１１９】
別の場合においては、アラート系サービスに関連するアラート発射に、所定の時間的長さにわたってアラートがトリガされていないこと、或いは現在時が所定の範囲内（例えば、夕刻或いは平日）に入ることという追加の条件が加えられる。
【０１２０】
アラート・エンジンにおける１次メモリ要件を下げるために、時間依存アラート‐トリガ条件を図１１に示すような方法に従って扱うことができる。まず、隣接するタイム・ブロック１１１０、１１２０、１１３０、１１４０のセットを、それぞれの時間依存アラート‐トリガ条件が、タイム・ブロックの１つに現在時ｔｃｕｒｒｅｎｔが入ることを必要とするように定義する。図示の例においては、現在時ｔｃｕｒｒｅｎｔがタイム・ブロック１１２０内にある。それぞれのタイム・ブロックごとに、そのタイム・ブロックに関係するすべてのロケーション依存アラート‐トリガ条件の扱いに関するデータ構造が組み立てられる；その種のデータ構造は、好都合にも定義を前に示したＳｊの形式を有することができる。例示の実施態様においては、４つのデータ構造、すなわち１１５０Ａ、１１５０Ｂ、１１５０Ｃ、および１１５０Ｄが存在し、それぞれはデータ構造Ｓ１、Ｓ２、Ｓ３、およびＳ４に対応している。すべてのタイム・ブロックに関するデータ構造は、２次メモリ内にストアされるが、現在時に対応するタイム・ブロック（この場合タイム・ブロック１１２０）に関するデータ構造は、１次メモリ内にストアされる。
【０１２１】
現在時が１つのタイム・ブロックから別のタイム・ブロックへ変化するとき、アラート・エンジンは、１次メモリ内のデータ構造（古いタイム・ブロックに関するロケーション依存アラート‐トリガ条件を処理するために使用されたデータ構造）の保持に現在使用しているストレージを解放し、２次メモリから、新しいタイム・ブロックに関するロケーション依存アラート‐トリガ条件を処理するために使用されるデータ構造をロードする。
【０１２２】
したがって、ここで認識されることになろうが、上記のテクニックは、各種の互いに共通しないタイム・ブロックに対応するデータ構造のうちの最大の１つを含むためにだけ必要となる大きさに１次メモリを構成できる実装を可能にする。
【０１２３】
当業者であれば認識されるであろうが、本発明のいくつかの実施態様においては、アラート・マネージャの機能モジュールを、あらかじめプログラム済みのハードウエアもしくはファームウエア・エレメント（例えば特定用途向け集積回路（ＡＳＩＣ）、電気的消去可能プログラマブル読み出し専用メモリ（ＥＥＰＲＯＭ）等）として、或いはそのほかの関連コンポーネントとして具体化することができる。
【０１２４】
別の実施態様においては、アラート・マネージャの機能モジュールを、コード・メモリ（図示せず）に対するアクセスを有する算術論理演算装置（ＡＬＵ）によって具体化してもよく、コード・メモリは、当該ＡＬＵの動作に関するプログラム・インストラクションを保持している。これらのプログラム・インストラクションを、固定の、有形の、かつプロセッサから読み取り可能なメディア（例えば、リムーバブル・ディスケット、ＣＤ‐ＲＯＭ、ＲＯＭ、または固定ディスク）上にストアすることも可能であり、またそれらのプログラム・インストラクションを遠隔地にストアし、ネットワークに接続されたモデムもしくはそのほかのインターフェース・デバイス（例えば、通信アダプタ）を経由し、伝送メディアを介してプロセッサに送信されるようにすることもできる。伝送メディアは、有形のメディア（例えば、光もしくはアナログ通信線）もしくはワイヤレス・テクニック（例えば、短波、赤外線、もしくはそのほかの伝送スキーム）を使用して具体化されるメディアのいずれとしてもよい。
【０１２５】
コード・メモリ内にストアされるプログラム・インストラクションは、多くに記載のピュータ・アーキテクチャまたはオペレーティング・システムを伴う使用のための多数のプログラミング言語を用いて記述されるハイ・レベルのプログラムからコンパイルすることができる。例えば、このハイ・レベルのプログラムを、ピクセル・シェーダとの使用に適しているもの等を含むアッセンブリ言語を用いて記述してもよく、またほかのバージョンを、手続プログラミング言語（例えば『Ｃ』）、もしくはオブジェクト指向プログラミング言語（例えば『Ｃ＋＋』または『JAVA（登録商標）（登録商標）』）を用いて記述することもできる。
【０１２６】
以上、本発明の具体的な実施態様について説明し、例証してきたが、当業者であれば明らかとなろうが、付随する特許請求の範囲に定義される本発明の範囲から逸脱することなく多くの修正ならびに変形が可能である。
【図面の簡単な説明】
【０１２７】
【図１】本発明の一実施態様に従ったワイヤレス通信ネットワークにおける使用のためのアラート・マネージャの構成を示したブロック図である。
【図２】移動局Ｘと目標ロケーションＹの間のユークリッド距離Ｄの決定方法を示した、距離Ｄの移動に必要となる時間の決定に使用するための説明図である。
【図３】道路パターンの操作による移動局Ｘから目標ロケーションＹまでの最短経路の決定を示した説明図である。
【図４】図１に示されている要求エンジンによって定義される、特定の移動局に関するＥＡＵＴ／ＭＡＴＴ時間ウインドウの演算例を示した説明図である。
【図５】本発明の一実施態様に従った特定の移動局に関するＭＡＴＴの効率的な併合のためのアルゴリズムを表したフローチャートである。
【図６】本発明の一実施態様に従った、１移動局当たり単一のＭＡＴＴを生成するために移動局グループごとに複数のアラート‐トリガ条件を扱うためのデータ構造を示した説明図である。
【図７Ａ−７Ｃ】本発明の一実施態様に従った、図６に示されているデータ構造の平面細区分を定義するための方法を示した説明図である。
【図８Ａ−８Ｃ】図６に示されているデータ構造の平面細区分を定義する線分の数を減らすためのヒューリスティックの一例を示した説明図である。
【図９】本発明の一実施態様に従った、特定の移動局が所定の時間にわたって周辺目標エリア内に見つかるか否かを基礎とし、アラート・エンジンによって行われる、その特定の移動局によってアラート‐トリガ条件が満たされるか否かのグラフ的な決定を示した説明図である。
【図１０】図９に示されているグラフ的な決定の例に関するモニタされた特定の移動局の挙動を表す漸進的なテーブルを示した説明図である。
【図１１】本発明の一実施態様に従った、時間依存アラート‐トリガ条件の扱いにおいてアラート・エンジンが使用するためのデータ構造を示した説明図である。
【図１】
2004535744.tif 000003
【図２】
2004535744.tif 000004
【図３】
2004535744.tif 000005
【図４】
2004535744.tif 000006
【図５】
2004535744.tif 000007
【図６】
2004535744.tif 000008
【図７Ａ】
2004535744.tif 000009
【図７Ｂ】
2004535744.tif 000010
【図７Ｃ】
2004535744.tif 000011
【図８Ａ】
2004535744.tif 000012
【図８Ｂ】
2004535744.tif 000013
【図８Ｃ】
2004535744.tif 000014
【図９】
2004535744.tif 000015
【図１０】
2004535744.tif 000016
【図１１】
2004535744.tif 000017
【国際公開パンフレット】
2004535744.tif 000018
2004535744.tif 000019
2004535744.tif 000020
2004535744.tif 000021
2004535744.tif 000022
2004535744.tif 000023
2004535744.tif 000024
2004535744.tif 000025
2004535744.tif 000026
2004535744.tif 000027
2004535744.tif 000028
2004535744.tif 000029
2004535744.tif 000030
2004535744.tif 000031
2004535744.tif 000032
2004535744.tif 000033
2004535744.tif 000034
2004535744.tif 000035
2004535744.tif 000036
2004535744.tif 000037
2004535744.tif 000038
2004535744.tif 000039
2004535744.tif 000040
2004535744.tif 000041
2004535744.tif 000042
2004535744.tif 000043
2004535744.tif 000044
2004535744.tif 000045
2004535744.tif 000046
2004535744.tif 000047
2004535744.tif 000048
2004535744.tif 000049
2004535744.tif 000050
2004535744.tif 000051
2004535744.tif 000052
2004535744.tif 000053
2004535744.tif 000054
2004535744.tif 000055
2004535744.tif 000056
2004535744.tif 000057
2004535744.tif 000058
2004535744.tif 000059
2004535744.tif 000060
2004535744.tif 000061
2004535744.tif 000062
2004535744.tif 000063
2004535744.tif 000064
2004535744.tif 000065
2004535744.tif 000066
2004535744.tif 000067
2004535744.tif 000068
2004535744.tif 000069
2004535744.tif 000070
2004535744.tif 000071
2004535744.tif 000072
2004535744.tif 000073
2004535744.tif 000074
2004535744.tif 000075
2004535744.tif 000076
2004535744.tif 000077
2004535744.tif 000078
2004535744.tif 000079
2004535744.tif 000080
2004535744.tif 000081
2004535744.tif 000082
2004535744.tif 000083
2004535744.tif 000084
2004535744.tif 000085
2004535744.tif 000086
2004535744.tif 000087
2004535744.tif 000088
2004535744.tif 000089
【国際公開パンフレット（コレクトバージョン）】
2004535744.tif 000090
2004535744.tif 000091
【国際調査報告】
2004535744.tif 000092
2004535744.tif 000093
2004535744.tif 000094
2004535744.tif 000095
2004535744.tif 000096
2004535744.tif 000097