(57)【特許請求の範囲】
【請求項１】
複数の移動体端末をそれぞれ収容する複数の網内装置がネットワークに接続され、
この網内装置もしくは前記移動体端末が発した他の移動体端末に対する探索要求にもとづき探索要求元の移動体端末が収容されている網内装置を出発点とし、探索対象の移動体端末が収容されている網内装置を全ての網内装置から構成される木構造である全域木をもとに網内装置を経由して探索する移動体端末探索方法において、
前記網内装置は、自身が収容している移動体端末からの探索要求と前記全域木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録し、
このバッファ内容を探索対象の移動体端末の識別子にしたがいソートし、
自身が収容している移動体端末のテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、
自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知するとともに前記バッファの内容からこの通知した探索要求を削除して削除後の当該バッファ内の探索要求を前記全域木をもとに少なくとも一台の隣接する網内装置に転送する
ことを特徴とする移動体端末探索方法。
【請求項２】
複数の移動体端末をそれぞれ収容する複数の網内装置がネットワークに接続され、
この網内装置もしくは前記移動体端末が発した他の移動体端末に対する探索要求にもとづき探索要求元の移動体端末が収容されている網内装置を出発点とし、探索対象の移動体端末が収容されている網内装置を全ての網内装置から構成される木構造である全域木をもとに網内装置を経由して探索する移動体端末探索方法において、
前記網内装置は、自身が収容している移動体端末からの探索要求と前記全域木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録し、
このバッファ内容を探索対象の移動体端末の識別子にしたがいソートし、
当該バッファ内の探索要求を前記全域木をもとに少なくとも一台の隣接する網内装置に転送し、
自身が収容している移動体端末のテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、
自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知する
ことを特徴とする移動体端末探索方法。
【請求項３】
請求項１記載の移動体端末探索方法が適用されるネットワークに設けられ、
自身が収容している移動体端末からの探索要求と前記全域木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録する手段と、
このバッファ内容を送信先の移動体端末の識別子にしたがいソートする手段と、
自身が収容している移動体端末が記録されたテーブルと、
このテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索する手段と、
この検索結果にしたがって自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知する手段と、
当該バッファ内の探索要求を前記全域木をもとに少なくとも一台の隣接する網内装置に転送する手段と
を備えたことを特徴とする網内装置。
【請求項４】
複数の移動体端末をそれぞれ収容する複数の網内装置がネットワークに接続され、
この網内装置もしくは前記移動体端末が発した他の移動体端末に対する探索要求にもとづき探索要求元の移動体端末が収容されている網内装置を出発点とし、探索対象の移動体端末が収容されている網内装置を全ての網内装置から構成される木構造である全域木を複数に分割した部分木をもとに網内装置を経由して探索する移動体端末探索方法において、
前記網内装置は、自身が収容している移動体端末からの探索要求と前記部分木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録し、
このバッファ内容を探索対象の移動体端末の識別子にしたがいソートし、
自身が収容している移動体端末のテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、
自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知するとともに前記バッファの内容からこの通知した探索要求を削除して削除後の当該バッファ内の探索要求を複数の前記部分木をもとに各部分木上の少なくとも一台の隣接する網内装置にそれぞれ転送する
ことを特徴とする移動体端末探索方法。
【請求項５】
複数の移動体端末をそれぞれ収容する複数の網内装置がネットワークに接続され、
この網内装置もしくは前記移動体端末が発した他の移動体端末に対する探索要求にもとづき探索要求元の移動体端末が収容されている網内装置を出発点とし、探索対象の移動体端末が収容されている網内装置を全ての網内装置から構成される木構造である全域木を複数に分割した部分木をもとに網内装置を経由して探索する移動体端末探索方法において、
前記網内装置は、自身が収容している移動体端末からの探索要求と前記部分木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録し、
このバッファ内容を探索対象の移動体端末の識別子にしたがいソートし、
当該バッファ内の探索要求を複数の前記部分木をもとに各部分木上の少なくとも一台の隣接する網内装置にそれぞれ転送し、
自身が収容している移動体端末のテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、
自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知する
ことを特徴とする移動体端末探索方法。
【請求項６】
請求項４記載の移動体端末探索方法が適用されるネットワークに設けられ、
自身が収容している移動体端末からの探索要求と前記部分木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録する手段と、
このバッファ内容を探索対象の移動体端末の識別子にしたがいソートする手段と、
自身が収容している移動体端末が記録されたテーブルと、
このテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索する手段と、
この検索結果にしたがって自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知する手段と、
当該バッファ内の探索要求を複数の前記部分木をもとに各部分木上の少なくとも一台の隣接する網内装置にそれぞれ転送する手段と
を備えたことを特徴とする網内装置。

【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は各々の移動体端末の位置情報を管理する位置登録サーバを設けない移動体通信網に利用する。本発明は全網内装置を探索することにより移動体端末が収容されている網内装置を知る技術に関する。本明細書で探索とは、移動体端末が収容されている網内装置を探すことをいう。
【０００２】
【従来の技術】
基地局が移動体端末を収容し、移動体端末に代わり移動体端末までの経路を確立する移動体通信網では、任意の二つの基地局間で直接あるいは間接的に相互通信が可能である移動体通信網があり、網内に一つもしくは少数の位置登録サーバを設け、各々の移動体端末は常に位置登録サーバに自己が収容されている基地局を通知しておき、移動体端末と通信する際には、位置登録サーバに当該移動体端末を収容している基地局を問い合わせ、当該移動体端末までの経路を確立する。
【０００３】
あるいは、任意の二つの基地局間で直接あるいは間接的に相互通信が可能である移動体通信網があり、網内に位置登録サーバを設けずに、通信要求が発生する度に通信要求パケットを移動体通信網に対しフラッディングさせ、全ての基地局に対し当該移動体端末を収容しているかを問い合わせ、当該移動体端末までの経路を確立する。
【０００４】
後者では、バッファリングおよびソートを各々の基地局が行うことはあっても、各々の基地局の処理結果を有機的に結びつけることはしていない。
【０００５】
【発明が解決しようとする課題】
このような従来の移動体端末探索法では、前者は、位置登録サーバが一台しかないときには、そのサーバが故障してしまうと他の全ての機器が動作していても全く通信ができなくなってしまう事態になり得る（これを“ｓｉｎｇｌｅ  ｐｏｉｎｔ  ｏｆ  ｆａｉｌｕｒｅ”という）、最新の移動体端末の位置を把握するために、位置情報の更新を頻繁に行なわねばならない（トラヒックの増大）、位置登録サーバは大量の問い合わせに応答しなければならないため、高負荷に耐え得る構造でなければならない（網内装置負荷の増大）、等の欠点がある。
【０００６】
後者は、大規模移動体通信網において用いられる際には、移動体端末数の多さと移動性の高さのため、経路確立要求が発生する頻度が非常に高くなり、移動体通信網の通信帯域が多数の制御パケット（探索要求）に圧迫されてしまう（トラヒックの増大）、基地局は多数の探索要求に対し、逐一、収容端末表を検索しなければならないため、検索負荷が大きくなる（網内装置負荷の増大）、等の欠点がある。
【０００７】
本発明は、このような背景に行われたものであって、高負荷に耐え得る構造を持たなければならない位置登録サーバを要さず、Ｓｉｎｇｌｅ  ｐｏｉｎｔ  ｏｆ  ｆａｉｌｕｒｅをなくし、位置情報を常に最新のものとすることができる移動体端末探索方法および網内装置および移動体通信網を提供することを目的とする。本発明は、探索トラヒックを削減することができ、網内装置のソート負荷および検索負荷を軽減することができる移動体端末探索方法および網内装置および移動体通信網を提供することを目的とする。本発明は、探索要求が全網内装置に転送されるまでに通過する辺数を減らすことができ、探索遅延を減らすことができる移動体端末探索方法および網内装置および移動体通信網を提供することを目的とする。
【０００８】
【課題を解決するための手段】
本発明の概念を図１３を参照して具体的に詳述する。図１３は本発明の概念を説明するための図である。例えば、ある通信プロトコルのアドレス体系（Ａとする）のネットワークアドレス（Ａ−１、Ａ−２、…とする）を持つ網内装置群があり、任意の２台間で直接あるいは間接に相互通信が可能である基幹網が構成されており、基幹網には、その網内装置群を節とする全域木が構築されており、その全域木のトポロジ情報は、各々の網内装置もしくはある網内装置や網内装置以外のトポロジ管理装置が保持している。
【０００９】
全域木とは、全ての網内装置から構成される木構造であり、全域木に沿って探索要求を転送すると、探索要求は全域木上の同じ経路を二回以上通ることなく当該移動体端末が発見されるまで全ての網内装置に送り届けられる。
【００１０】
識別子として、通信プロトコルのアドレス体系（Ｍとする）のネットワークアドレス（Ｍ−１、Ｍ−２、…とする）を持つ移動体端末が、網内装置の少なくとも一台と通信可能であるとする。ここで、アドレス体系ＡとＭは同一であっても異なっていてもよい。
【００１１】
網内装置Ａ−１は、移動体端末Ｍ−１、Ｍ−２を収容し、自己およびＭ−１、Ｍ−２から発生した探索要求集合Ｒ−１および隣接網内装置Ａ−２、Ａ−３から受信した探索要求集合Ｒ−２、Ｒ−３をバッファリングしている。網内装置ａから発せられた移動体端末ｂの探索要求を、ａ→ｂと表すことにする。
【００１２】
探索要求集合は複数の探索要求からなる集合であり、例えば、Ｒ−２は、探索要求Ａ−２→Ｍ−１、Ａ−４→Ｍ−３を含んでいるとする。Ａ−１は、前のトリガ発生後に受信した探索要求数がある数を超えた場合、もしくは前のトリガ発生からある時間経過した場合等にソート開始のトリガをかけ、送信（発生）元別に分けられている探索要求集合Ｒ−１、Ｒ−２、Ｒ−３を二つにコピーし、片方はそのまま保存しておき、もう片方はＲ−１、Ｒ−２、Ｒ−３を一つにまとめる。ただし、複数の全域木を用いない場合には、自己から発生した探索要求集合を保存する必要はない。
【００１３】
この際、一つにまとめた探索要求集合については、移動体端末を探索する際の負荷を軽減するために、探索先移動体端末の識別子にしたがいソート、もしくはインデックス付け等を行ない、また、探索先が重複している探索要求については、探索元を連ねて記述することにより、ひとつの探索要求にまとめてもよい。
【００１４】
まとめた探索要求集合から自己が収容する移動体端末を検索し、ここでは収容移動体端末Ｍ−１が、探索要求Ａ−２→Ｍ−１に記載されていることを発見し、探索元であるＡ−２に自己（Ａ−１）がＭ−１を収容していることを通知し、まとめた探索要求集合から、探索先が発見されたＡ−２からＭ−１への探索要求を取り除き、隣接網内装置であるＡ−２、Ａ−３に、重複を防ぐために発見済探索要求を取り除かれた探索要求集合から当該網内装置から送られて来た探索要求集合を差し引いて転送する。例えば、Ａ−２、Ａ−３には、（Ｒ−１）＋（Ｒ−２）＋（Ｒ−３）−（Ａ−２→Ｍ−１）−（Ｒ−２）が転送される。ここで、探索要求集合の送信元であるＡ−１ではなく、送信先であるＡ−２、Ａ−３が重複探索要求の削除を行なってもよい。この探索要求集合は上述の手順により検索しやすくソートあるいはインデックス付けなどがなされていてもよい。
【００１５】
各々の網内装置が以上の動作を繰り返すことにより、移動体端末の探索要求を発した網内装置は、探索対象の移動体端末を収容する網内装置からの通知を受け、探索対象の移動体端末を収容する網内装置を知ることが可能となる。
【００１６】
また、図１４は全域木を部分木に分割する様子を説明するための図であるが、図１４に示すように、ある通信プロトコルアドレス体系（Ａとする）のネットワークアドレス（Ａ−１、Ａ−２、…、Ａ−２００とする）を持つ網内装置群で構成される全域木を、Ａ−１、…、Ａ−１００からなる部分木１と、Ａ−１０１、…、Ａ−２００からなる部分木２の二つの部分木に分割し、各々の部分木においては、任意の２台間で直接あるいは間接に相互通信が可能であり、また、各々の部分木上の少なくとも一台の網内装置は、異なる部分木上の少なくとも一台の網内装置と直接あるいは間接に相互通信が可能であり、識別子として、通信プロトコルのアドレス体系（Ｍとする）のネットワークアドレス（Ｍ−１、Ｍ−２、…とする）を持つ移動体端末が、任意の部分木に属する網内装置の少なくとも一台と通信可能であるとする。ここで、アドレス体系ＡとＭは、同一であっても異なっていてもよい。
【００１７】
上述のように全域木を分割した場合において、検索済探索要求集合を転送する際に、網内装置Ａ−１は、自己が属する部分木１に属する網内装置Ａ−２、Ａ−３には、全域木を分割していない場合には、図１３により説明したように、重複を省いた探索要求集合を転送し、自己が属さない部分木１に属する網内装置Ａ−１０１には、自己から発生した探索要求集合Ｒ−１を転送する。自己の属さない部分木へ転送する探索要求集合を作成する部分および作成した探索要求集合を転送する部分以外は、図１３により説明したものと同様である。
【００１８】
これにより、高負荷に耐え得る構造を持たなければならない位置登録サーバを要さず、Ｓｉｎｇｌｅ  ｐｏｉｎｔ  ｏｆ  ｆａｉｌｕｒｅをなくし、位置情報を常に最新のものとすることができる。さらに、探索トラヒックを削減することができ、網内装置のソート負荷および検索負荷を軽減することができる。また、探索要求が全網内装置に転送されるまでに通過する辺数を減らすことができ、探索遅延を減らすことができる。
【００１９】
すなわち、本発明の第一の観点は、複数の移動体端末をそれぞれ収容する複数の網内装置がネットワークに接続され、この網内装置もしくは前記移動体端末が発した他の移動体端末に対する探索要求にもとづき探索要求元の移動体端末が収容されている網内装置を出発点とし、探索対象の移動体端末が収容されている網内装置を全ての網内装置から構成される木構造である全域木あるいはこの全域木を複数に分割した部分木をもとに網内装置を経由して探索する移動体端末探索方法である。
【００２０】
ここで、本発明の特徴とするところは、前記網内装置は、自身が収容している移動体端末からの探索要求と前記全域木あるいは前記部分木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録し、このバッファ内容を探索対象の移動体端末の識別子にしたがいソートし、自身が収容している移動体端末のテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知するとともに前記バッファの内容からこの通知した探索要求を削除して削除後の当該バッファ内の探索要求を前記全域木をもとに少なくとも一台の隣接する網内装置に転送する、あるいは、複数の前記部分木をもとに各部分木上の少なくとも一台の隣接する網内装置にそれぞれ転送するところにある。
【００２１】
このように、探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、自身が収容している移動体端末のときには探索要求元に通知を行い、前記バッファの内容からこの通知した探索要求を削除して削除後の当該バッファ内の探索要求を転送することにより、自身が収容している既に発見済となった移動体端末の探索要求を削除でき、トラヒックを削減することができる利点を有する。
【００２２】
しかし、その一方で、このように検索および通知を行ってから転送を行うのでは、探索遅延が大きくなることが懸念される。これを改善するための方法としては、前記網内装置は、自身が収容している移動体端末からの探索要求と前記全域木あるいは前記部分木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録し、このバッファ内容を探索対象の移動体端末の識別子にしたがいソートし、当該バッファ内の探索要求を前記全域木をもとに少なくとも一台の隣接する網内装置に転送し、あるいは、複数の前記部分木をもとに各部分木上の少なくとも一台の隣接する網内装置にそれぞれ転送し、自身が収容している移動体端末のテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知することもできる。
【００２３】
これにより、検索および通知を行う以前に、転送を行うため、探索遅延を小さくすることができる利点がある。この方法では、後で発見済となり、削除されることになる自身が収容している移動体端末の探索要求を削除しないため、無駄なトラヒックが流れるが、探索遅延を小さくすることができる利点の方がトラヒックに多少の無駄が発生することよりも有用であるときに適用することができる。なお、全域木あるいは部分木の上で探索要求を転送するため探索要求は末端で止まるので、探索要求がループするといったことはない。
【００２４】
本発明の第二の観点は網内装置であって、本発明の特徴とするところは、本発明の移動体端末探索方法が適用されるネットワークに設けられ、自身が収容している移動体端末からの探索要求と前記全域木あるいは前記部分木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファに記録する手段と、このバッファ内容を探索対象の移動体端末の識別子にしたがいソートする手段と、自身が収容している移動体端末が記録されたテーブルと、このテーブルを参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索する手段と、この検索結果にしたがって自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知する手段と、当該バッファ内の探索要求を前記全域木をもとに少なくとも一台の隣接する網内装置に転送する手段、あるいは、複数の前記部分木をもとに各部分木上の少なくとも一台の隣接する網内装置にそれぞれ転送する手段とを備えたところにある。
【００２５】
【発明の実施の形態】
本発明実施例の移動体端末探索方法および網内装置を図１を参照して説明する。図１は本発明の概略図である。
【００２６】
本発明では、図１に示すように、移動体端末７および８を収容する網内装置２および５がネットワークに接続され、この網内装置２または５もしくは移動体端末７または８が発した他の移動体端末に対する探索要求にもとづき探索要求元の移動体端末７または８が収容されている網内装置２または５を出発点とし、探索対象の移動体端末が収容されている網内装置を全ての網内装置２〜６から構成される木構造である全域木１あるいはこの全域木１を複数に分割した部分木をもとに網内装置を経由して探索する移動体端末探索方法を用いる。
【００２７】
ここで、本発明の特徴とするところは、網内装置２または５は、自身が収容している移動体端末７または８からの探索要求と全域木１あるいは前記部分木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファ１１に記録し、ソート・検索装置１２は、このバッファ１１の内容を探索対象の移動体端末の識別子にしたがいソートし、自身が収容する移動体端末のテーブルである収容端末表１３を参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知するとともにバッファ１１の内容からこの通知した探索要求を削除し、転送装置１４は隣接網内装置表１５を参照し、この削除後の当該バッファ１１内の探索要求を、全域木１をもとに少なくとも一台の隣接する網内装置に転送する、あるいは、複数の前記部分木をもとに各部分木上の少なくとも一つの隣接する網内装置にそれぞれ転送するところにある。
【００２８】
あるいは、網内装置２または５は、自身が収容している移動体端末７または８からの探索要求と全域木１あるいは前記部分木をもとに他の網内装置から送られてきた探索要求とを探索要求元および探索要求の受信時刻ごとにバッファ１１に記録し、ソート・検索装置１２は、このバッファ１１の内容を探索対象の移動体端末の識別子にしたがいソートし、転送装置１４は隣接網内装置表１５を参照し、当該バッファ１１内の探索要求を、全域木１をもとに少なくとも一台の隣接する網内装置に転送し、あるいは、複数の前記部分木をもとに各部分木上の少なくとも一つの隣接する網内装置にそれぞれ転送し、ソート・検索装置１２は、自身が収容する移動体端末のテーブルである収容端末表１３を参照して当該探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、自身が収容している移動体端末のときには当該移動体端末の識別子とその網内装置の識別子とを探索要求元の移動体端末が収容されている網内装置に通知するところにある。
【００２９】
本発明の網内装置およびネットワークは移動体通信網を構成する。
【００３０】
以下に、図面を参照して本発明の実施の形態についてさらに詳細に説明する。まず、本発明の背景となる移動体端末を収容する網内装置群からなり、その網内端末群を節とする全域木が構築されている基幹網について説明する。図２は、この基幹網の一部を模式的に示した概略図である。図２の太線は全域木１の一部を示している。全域木１と物理的なネットワークは必ずしも一致している必要はなく、図２においては、網内装置２と５とは物理的には接続されているが、網内装置２と６との間の通信路は全域木１の枝にはなっていない。
【００３１】
ここでは、全域木１のトポロジ情報は各網内装置２〜６が隣接網内装置表１５として保持しているものとするが、ある網内装置もしくは網内装置以外のトポロジ管理装置がトポロジ情報を保持していて、各々の網内装置が必要に応じて当該装置に問い合わせる方式を採用してもよい。全域木１の各節に網内装置２〜６があり、網内装置２および５にそれぞれ移動体端末７および８が収容されている。
【００３２】
図３に網内装置の概略を示す。バッファ１１は、隣接網内装置から受信したもしくは自己から発生した探索要求集合を送信（発生）元、受信時刻別にバッファリングしておく。前のトリガ発生後に受信した探索要求数がある数を越えたとき、もしくは前のトリガ発生からある時間経過したとき等にソート開始のトリガをかけ、バッファリングされていた探索要求集合は、ソート・検索装置１２および転送装置１４に移動され、バッファ１１はクリアされ再び探索要求のバッファリングを開始する。
【００３３】
このとき、ソート・検索装置１２には、送信（発生）元、受信時刻別に分別した状態の探索要求集合を移動し、転送装置１４には、送信（発生）元別に分別した状態の探索要求集合を移動する、もしくは移動後にそのような状態にする。ここでは、検索負荷を軽減するためにソートを行なっているが、ソートの代わりにインデックス付け（例えばハッシュ等）を行なってもよい。
【００３４】
ソート・検索装置１２は、探索要求集合を検索対象の移動体端末識別子にしたがいソートする。送信（発生）元、受信時刻別にバッファリングした各々の探索要求集合は、隣接網内装置でソート済であるため、ここでのソート負荷が軽減される。この際、探索先が重複している探索要求については、探索元を連ねて記述することにより、ひとつの探索要求にまとめてもよい。収容端末表１３は、当該網内装置が収容している移動体端末が、移動体端末識別子にしたがいソートされて記述されている表であり、適切に更新されているものとする。
【００３５】
ソート・検索装置１２は、収容端末表１３を検索する。探索要求集合、収容端末表１３ともにソートされているため、検索回数を探索要求数と収容端末数の和のオーダに押えることが出来る。もし、バッファリングおよびソートを行なわないときには、
（探索要求数）×ｌｏｇ（収容端末数）
のオーダーになる。
【００３６】
探索要求集合中に自己の収容端末を発見した場合は、探索元に自己がその移動体端末を収容していることを通知し、ソート済探索要求集合から、発見済探索要求を取り除いたものを、転送装置１４に移動する。
【００３７】
転送装置１４は、発見済探索要求を取り除かれた探索要求集合から、当該転送先網内装置から送られて来た探索要求集合を引いた探索要求集合を、隣接網内装置表１５に記載されている全域木上の各々の隣接網内装置に転送する。ここで、探索要求集合の送信元網内装置ではなく、送信先網内装置が重複探索要求の削除を行なってもよい。
【００３８】
次に、図２において移動体端末７の移動体端末８への通信要求発生から網内装置２が網内装置５からの収容通知を受信し、通信が可能となるまでを例として、当該探索要求に注目し説明する。移動体端末７は、収容されている網内装置２に対し、移動対端末８との通信要求を発する（図２および図４のシーケンスＳ１参照）。網内装置２は、移動体端末７から移動体端末８への通信要求があったことを記録し、探索要求網内装置２→移動体端末８をバッファ１１にバッファリングし、前のトリガ発生後に受信した探索要求数がある数を越えた場合、もしくは前のトリガ発生からある時間経過した場合等にソート開始のトリガをかけ、他の探索要求と共に移動体端末の識別子にしたがいソートし、収容端末表１３を検索し、移動体端末８は発見されないため、全域木上の隣接網内装置３へ転送される（シーケンスＳ２）。各々の網内装置内での処理の詳細については後述する。
【００３９】
ここで、移動体端末７が直接探索要求を発生するのではなく、移動体端末７から通信要求を受信した網内装置２が代理で発生させているが、移動体端末７が直接探索要求を発生させてもよい。その際には、網内装置５からの収容通知を移動体端末７が受信できるために、移動体端末７が発生する探索要求には、移動体端末７が網内装置２に収容されているという情報を加える必要がある。
【００４０】
網内装置３でも同様の処理が行なわれ、探索要求網内装置２→移動体端末８は、網内装置４および５へ転送される（シーケンスＳ３）。網内装置４および５でも同様の処理が行なわれ、網内装置４においては、収容端末表１３中に移動体端末８は発見されないため、当該探索要求はさらに転送されるが（シーケンスＳ４）、網内装置５においては、収容端末表１３中に移動体端末８が発見され（シーケンスＳ５）、網内装置５から網内装置２へ網内装置５が移動体端末８を収容していることが通知される（シーケンスＳ６）。網内装置５から網内装置２への通知が通る経路は任意である。通知を受信した網内装置２は、移動体端末７から移動対端末８への通信要求の記録に基づき、移動体端末７に対し通信可能となったことを通知し（シーケンスＳ７）、移動体端末７と移動体端末８との通信が可能となる。ここで説明した動作は、収容している移動体端末から通信要求が発生した場合についてであるが、網内装置自身から発生した場合も同様である。
【００４１】
次に、図３および図５〜図７を参照しながら、上記例における網内装置５の処理の詳細を説明する。網内装置５は、時刻ｔｌに網内装置６から探索要求６→２２（シーケンスＳ１１）、時刻ｔ２に網内装置３から探索要求２→８、３→２１、４→２４（シーケンスＳ１２）、時刻ｔ３に網内装置６から探索要求６→２１（シーケンスＳ１３）を受信し、時刻ｔ４に移動体端末８からの移動体端末２３への通信要求を受け、探索要求５→２３を作成し（シーケンスＳ１４）、これらはバッファ１１にバッファリングされる。また、網内装置５は、移動体端末８のみを収容しており、それは収容端末表１３に記述されている。
【００４２】
網内装置５は、前のトリガ発生後から受信した探索要求数がある数を越えた場合、もしくは前のトリガ発生からのある時間経過した場合等にソート開始のトリガをかけ、バッファ１１にバッファリングされている探索要求集合をソート・検索装置１２、転送装置１４に移動する（シーケンスＳ１５）。この際、ソート検索・装置１２には、バッファリングされている全ての探索要求集合を送信（発生）元、受信時刻別に、転送装置１４には探索要求集合を送信（発生）元別に移動する。ただし、複数の全域木を用いない場合には、転送装置１４に自己から発生した探索要求集合を移動する必要はない。探索要求集合を移動後、バッファ１１はバッファリングを再開する。
【００４３】
ソート・検索装置１２は、探索要求集合をまとめ、移動体端末の検索負荷を軽減するために、探索対象の移動体端末の識別子にしたがいソートし（シーケンスＳ１６）、収容端末表１３を検索し（シーケンスＳ１７）、収容している移動体端末８への探索要求があることを発見し、探索要求元の網内装置２に自己（網内装置５）が移動体端末８を収容していることを通知し（シーケンスＳ１８）、網内装置２の接続通知部１６は、移動体端末７に、移動体端末８と通信可能となったことを通知し（シーケンスＳ１９）、探索要求集合から発見済探索要求を削除後（シーケンスＳ２０）、探索要求集合を転送装置１４に移動し（シーケンスＳ２１）、転送装置１４は、隣接網内装置表１５に記載されている隣接網内装置３に、上記探索要求集合から網内装置３から転送されて来た探索要求を除き（シーケンスＳ２２）、網内装置３に転送する（シーケンスＳ２３）。
【００４４】
隣接網内装置表１５に記載されている隣接網内装置６についても同様に、上記探索要求集合から網内装置６から転送されて来た探索要求を除き（シーケンスＳ２２）、網内装置６に転送する（シーケンスＳ２３）。ここで、探索要求集合の送信元である網内装置５ではなく、送信先である網内装置３および６が重複探索要求の削除を行なってもよい。ソート・検索装置１２および転送装置１４は再びトリガをかけるまでアイドル状態となる。
【００４５】
次に、図５〜図８を参照しながら、実施形態の詳細について説明する。自己の属さない部分木へ転送する探索要求集合を作成する方法および作成した探索要求集合を転送する方法以外は、前述したものと同様である。図８のように、全域木１を２つの部分木１−１および１−２に分割し、網内装置５は、探索要求の一部もしくは全部を網内装置３１に転送する。網内装置３１に転送する探索要求の選択については任意であるが、ここでは他網内装置が同一探索要求を転送してしまうことによる重複を防ぐために自己が作成した探索要求のみを転送することにする。
【００４６】
具体的には、シーケンスＳ２２において重複探索要求を除去する際に、ソートされ収容端末に対する探索要求を削除した探索要求集合と、自己および自己の収容している移動体端末からの通信要求により作成した探索要求５→２３との重複探索要求（シーケンスＳ２２’）を、網内装置３１にも転送する（シーケンスＳ２３’）。当該探索要求が転送される経路は任意であるが、網内装置３１に転送されるまでに通過する網内装置は、当該探索要求を検索せずに網内装置３１に向け転送する。
【００４７】
網内装置３１が当該探索要求を受信後は、右側の部分木１−２においても左側の部分木１−１と同様のプロセスにより、探索要求は検索、転送され、探索先移動体端末２３を発見した網内装置３２は、探索元網内装置５に収容通知を送信する（シーケンスＳ２４）。網内装置３２から網内装置５に転送される収容通知が通る経路は任意である。納内装置５の接続通知部１６は、収容している移動体端末８に、移動体端末２３と通信可能となったことを通知する（シーケンスＳ２５）。
【００４８】
次に、上記実施形態における各装置等の具体的な実施例を示す。基幹網ネットワークプロトコルとしてはＩｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ（ＩＰ）を採用し、移動体端末の識別子もＩＰアドレスを用いる。ＩＰ網においては、静的もしくは動的な経路制御プロトコルにより任意の二台の網内装置間で直接あるいは間接的に相互通信が可能である。網内装置は、無線により移動体端末と相互通信が可能であり移動体端末にとっての基地局となり、また、基地局はＩＰルータの機能を備えている。
【００４９】
基地局は、ある時間間隔もしくは移動体端末から要求があった際に収容端末表を更新する。ＩＰ網には、ＶＬＡＮ等の仮想網構築技術により、もしくは物理的に制御網を構築することにより、各基地局を節とする全域木を構築する。移動体端末は、基地局を通して他の移動体端末と通信する。移動体端末ａは基地局Ａに収容され、移動体端末ｂは基地局Ｂに収容されていて、移動体端末ａが基地局Ａに移動体端末ｂへの通信要求パケットを送信する場合を考える。
【００５０】
このとき、Ａの収容端末表にはａが、Ｂの収容端末表にはｂが記載されている。
【００５１】
移動体端末ａからの通信要求パケットを受信した基地局Ａは、自己のバッファに探索要求パケットＡ→ｂを生成する。
【００５２】
基地局Ａは、前のトリガ発生後から受信した探索要求数がある数を越えた場合、もしくは前のトリガ発生からのある時間経過した場合等に、ソート開始のトリガをかけ、バッファの探索要求集合をソート・検索装置１２と転送装置１４に移動し、ソート・検索装置１２にて他の探索要求パケットとソートする。収容端末表１３を検索し、収容している端末への探索要求が発見された場合は、探索元に収容通知パケットを送信し、探索要求集合から削除する。発見されなかった探索要求については、転送装置１４に移動し、当該隣接基地局から転送された探索要求を削除した探索要求集合を隣接基地局に転送される。
【００５３】
探索要求パケットＡ→ｂも隣接基地局に転送される。各々の基地局で上記の動作が繰り返されることにより、探索要求パケットは探索先移動体端末を収容している基地局があれば、当該基地局に必ず届く。探索要求パケットＡ→ｂは、基地局Ｂに転送され、基地局Ｂは収容端末表にｂを発見し、Ａに収容通知パケットを送信する。収容通知パケットは、経路制御プロトコルによりＩＰ網に確立している経路を転送される。
【００５４】
基地局Ａは、基地局Ｂからの収容通知パケットを受信し、移動体端末ａに移動体端末ｂと通信可能になったことを知らせる通信可能パケットを送信し、通信可能パケットを受信した移動体端末ａは移動体端末ｂとの通信を開始する。移動体端末ａから移動体端末ｂへの通信は、例えば、基地局Ａが、移動体端末ａから移動体端末ｂ宛のＩＰパケットを基地局Ｂ宛のＩＰヘッダでカプセル化することにより実現する。
【００５５】
カプセル化されたパケットは、経路制御プロトコルにより基地局ＡからＢへ送信され、カプセル化されたパケットを受信した基地局方は、自己宛のＩＰヘッダを剥ぎ、そこに自己が収容している移動体端末ｂ宛のパケットを発見し、移動体端末ｂへ転送する。
【００５６】
上述のＩＰ網上に存在する全域木を図９にあるように二つの部分木１−１および１−２に分割した場合を考える。基地局Ａで発生した探索要求パケットは、隣接基地局だけでなく、基地局Ｃにも転送される。図９の例においては、探索要求パケットが全基地局に転送されるまでに通過する辺数を５から３に減らすことができ、探索遅延を減らすことができる。
【００５７】
（他の実施例）
他の実施例を図５、図１０および図１１を参照して説明する。図５、図１０および図１１は他の実施例の網内装置におけるシーケンス図である。なお、図５、図１０および図１１では、その処理内容が図５〜図７で示した処理内容と同じ処理内容である場合には図５〜図７で付したシーケンス番号と同じシーケンス番号を付した。
【００５８】
前述した実施例では、まず、ソート・検索装置１２が探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、自身が収容している移動体端末のときには探索要求元に通知を行い、その後に、転送装置１４がバッファ１１の内容からこの通知した探索要求を削除して削除後の当該バッファ１１内の探索要求を他の網内装置に転送することにより、既に発見済となった自身が収容している移動体端末の探索要求を削除でき、トラヒックを削減することができる利点を有する。
【００５９】
しかし、その一方で、このように検索および通知を行ってから転送を行うのでは、探索遅延が大きくなることが懸念される。これを改善するための方法としては、まず、転送装置１４が探索要求を他の網内装置に転送し、その後に、ソート・検索装置１２が探索対象の移動体端末が自身が収容している移動体端末か否かを検索し、自身が収容している移動体端末のときには探索要求元に通知を行う方法がある。この方法を他の実施例として以下に説明する。
【００６０】
すなわち、図１０に示すように、シーケンスＳ１６によりソートを行った探索要求集合を直ちに転送装置１４に移動し（シーケンスＳ１２１）、転送装置１４は、隣接網内装置表１５に記載されている隣接網内装置３に、上記探索要求集合から網内装置３から転送されて来た探索要求を除き（シーケンスＳ１２２）、網内装置３に転送する（シーケンスＳ１２３）。
【００６１】
隣接網内装置表１５に記載されている隣接網内装置６についても同様に、上記探索要求集合から網内装置６から転送されて来た探索要求を除き（シーケンスＳ１２２）、網内装置６に転送する（シーケンスＳ１２３）。
【００６２】
その後に、図１１に示すように、ソート・検索装置１２は、収容端末表１３を検索し（シーケンスＳ１７）、収容している移動体端末８への探索要求があることを発見し、探索要求元の網内装置２に自己（網内装置５）が移動体端末８を収容していることを通知し（シーケンスＳ１８）、網内装置２の接続通知部１６は、移動体端末７に、移動体端末８と通信可能となったことを通知する（シーケンスＳ１９）。
【００６３】
当該実施例で説明した方法は、後で発見済となり、削除されることになる自身が収容している移動体端末の探索要求を削除しないため、無駄なトラヒックが流れるが、探索遅延を小さくすることができる利点の方がトラヒックに多少の無駄が発生することよりも有用であるときに適用する。
【００６４】
【発明の効果】
以上説明したように、本発明によれば、移動体端末の位置情報を、一つもしくは少数の網内装置が集約するのではなく、各々の網内装置が保持することにより、高負荷に耐え得る構造を持たなければならない位置登録サーバを要さず、Ｓｉｎｇｌｅ  ｐｏｉｎｔ  ｏｆ  ｆａｉｌｕｒｅをなくし、位置情報を常に最新のものとすることが可能となる。
【００６５】
各々の網内装置が、複数の探索要求をまとめソートやインデックス付けをし隣接網内装置に転送するというアルゴリズムを用いることにより、以下を同時に達成することができる。すなわち、まとめて転送するためにヘッダに関するトラヒックが削減されるため、探索トラヒックを削減することができる、ソートされている探索要求集合を受信するため、網内装置のソート負荷を軽減することができる、一度に、一つではなく複数の探索要求に対して検索を行えることおよび探索要求集合がソートされていることにより、網内装置の検索負荷を軽減することができる。
【００６６】
すなわち、図１２（ａ）に示すように、受信探索要求数をｍとし、収容移動体端末数をｎとするとき、ソートのみ（バッファリングなし）では、検索手数は、Ｏ（ｍ・ｎ）となるが、図１２（ｂ）に示すように、ソートおよびバッファリングを行った場合には、検索手数はＯ（ｍ＋ｎ）となる。なお、図１２（ａ）で二分探索を行ったときの検索手数はＯ（ｍ・ｌｏｇ（ｎ））となる。
【００６７】
全域木を分割し、各々の部分木に探索要求を転送することにより、探索要求が全網内装置に転送されるまでに通過する辺数を減らすことができ、探索遅延を減らすことができる。
【図面の簡単な説明】
【図１】本発明の概略図。
【図２】基幹網概略図。
【図３】本発明の網内装置のブロック構成図。
【図４】基幹網におけるシーケンス図。
【図５】網内装置におけるシーケンス図。
【図６】網内装置におけるシーケンス図。
【図７】網内装置におけるシーケンス図。
【図８】全域木を複数の部分木に分割した図。
【図９】全域木を分割したときに探索要求が全網内装置に到着するまでに通過する辺数を示す図。
【図１０】他の実施例における網内装置のシーケンス図。
【図１１】他の実施例における網内装置のシーケンス図。
【図１２】ｎ台の移動体端末を収容している網内装置がｍの探索要求を処理する際に必要な検索手数を示す図。
【図１３】本発明の概略を説明するための図。
【図１４】部分木を説明するための図。
【符号の説明】
１  全域木
１−１、１−２  部分木
２〜６、３１、３２  網内装置
７、８  移動体端末
１１  バッファ
１２  ソート・検索装置
１３  収容端末表
１４  転送装置
１５  隣接網内装置表
１６  接続通知部
【図１】
0003585830.tif 000002
【図２】
0003585830.tif 000003
【図３】
0003585830.tif 000004
【図４】
0003585830.tif 000005
【図５】
0003585830.tif 000006
【図６】
0003585830.tif 000007
【図７】
0003585830.tif 000008
【図８】
0003585830.tif 000009
【図９】
0003585830.tif 000010
【図１０】
0003585830.tif 000011
【図１１】
0003585830.tif 000012
【図１２】
0003585830.tif 000013
【図１３】
0003585830.tif 000014
【図１４】
0003585830.tif 000015