(57)【特許請求の範囲】
【請求項１】
複数の最終ホップルータを有し、移動ホストと通信するネットワークにおける通信制御方法であって、
前記複数の最終ホップルータの各々が、その最終ホップルータが属するページング領域を特定する識別子と、複数のページング領域の集合であるページング領域クラスタを特定する情報と、各ページング領域クラスタにおける複数のページング領域の従属関係を示す情報とを含むクラスタマップを記憶するクラスタマップ記憶ステップと、
移動ホストが、現在在圏しているページング領域を特定するページング領域識別子を含むメッセージを送信すると、前記複数の最終ホップルータのうち一の最終ホップルータが、そのメッセージの送信元である移動ホストが過去に属したページング領域の統計記録を含む可能性マップを記憶手段に記憶する可能性マップ記憶ステップと、
前記一の最終ホップルータが、前記可能性マップに基づいて、その最終ホップルータが属するページング領域クラスタと統合されるページング領域もしくはページング領域クラスタの候補、または、その最終ホップルータが属するページング領域クラスタから分離されるページング領域もしくはページング領域クラスタの候補を検出する検出ステップと、
前記一の最終ホップルータが、前記可能性マップに基づいて、前記検出された候補から、ページング領域クラスタの統合または分離の対象となる対象ページング領域または対象ページング領域クラスタを決定する決定ステップと、
前記一の最終ホップルータが、前記決定に基づいて、前記クラスタマップに含まれる、複数のページング領域の従属関係を更新する更新ステップと
を有する通信制御方法。
【請求項２】
前記決定ステップが、
前記一の最終ホップルータが、前記一の最終ホップルータが属するページング領域クラスタと、前記統合されるページング領域またはページング領域クラスタの候補とを統合した場合の統合コストを算出するステップと、
前記統合コストがあらかじめ決められたしきい値未満であった場合、前記一の最終ホップルータが、前記統合されるページング領域またはページング領域クラスタの候補を、前記対象対象ページング領域または対象ページング領域クラスタとして決定する
ことを特徴とする請求項１に記載の通信制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本出願は、参考文献により加えられる、フナトダイチの名により２００１年１０月３日付けで申請された出願番号６０/３２７０９１の合衆国仮特許出願による優先権を主張する。
【０００２】
本発明は概ね、無線通信システムに関する。より具体的には、異種類のアクセスネットワークにおける分散型ダイナミックページング領域形成のための方法及び関連する装置に関する。
【０００３】
【従来の技術】
無線技術とインターネットが商業的に発達するにつれ、移動インターネットアクセスが世界的にますます民衆の間で広まってきている。現在、発達中の第３及び第４世代（それぞれに３G,４G）無線システムにおいて、無線及びインターネットの技術は組み合わされることとなる。このようなシステムにおいて、移動ホストは基地局または他の固定構造基盤アクセスポイントと無線でつながった状態で領域内を移動することが自由となる。それぞれの、ネットワークの基地局は、基地局を囲む地理的範囲の移動ホストを収容する。移動ホストが移動すると、移動ホストとの通信は一つの基地局からもう一方へとハンドオフされる。携帯電話技術およびインターネット技術の統合に向けてのリサーチ及び標準化の努力は現在進行中である。ページング技術はそのような技術のうちの一つである。
【０００４】
ページング技術は、携帯電話システムの全てのセルを、ページング領域と呼ばれる幾多もの異なる領域に区切る。これらのページング領域を行き来する移動ホストは、ひとつのページング領域から異なる領域に移動するたびに新しい位置を登録する必要がある。移動ホストがページング領域に在圏するときは、その正確な位置はシステムによっては把握されていない。よって、着信があった折は、移動ホスト（以下、MHと呼ぶ）の正確な位置はMHのページング領域の全てのセルへページングメッセージを送ることにより把握される。MHにおける電池の消耗の削減のため、ページング技術は大変効果があることが証明されている。
【０００５】
ページング技術は、休止モードにあるMHをたどることに使用される。MHは、電池を節約するために、実際に通信を行っていない間は休止モードへと入る。しかし、休止状態においてMHは、MHが移動しているページング領域を示す領域IDを報告する信号を近隣のアクセスポイントから受信することが可能である。ページング領域は、特定のMHに対するページング信号が送信されるネットワーク又はシステムの部分である。一つのページング領域から他へ移動している間、MHは、境界を越えた折に異なるID信号を受信し始めることにより、ページング領域の境界を越え、そして他のページング領域に入ったか否か、また、いつそのことが起こったかを認識できる。MHは異なる領域ID信号を受信した折、休止モードから活動モードへと戻り、新しいページング領域へ自身を登録するために信号を送信する。
【０００６】
３Gおよび４Gの無線システムにおいては、インターネットプロトコル（IP）ネットワークが基幹ネットワークとして想定されている。IPは、無線と有線の両方の通信システム、又はこれら二つの組み合わせに適応されえる標準化された通信フォーマットである。IPに基づくページングプロトコルは、３G及び４Gの無線システムに必要なものである。
【０００７】
【発明が解決しようとする課題】
IPページング技術の発達にとっての難問は、いかにしてページング領域を指定するかである。ページング領域の定義と配置又は設定に関し、二つの問題が発見されている。第一の問題は、ページング領域の大きさである。もし、それぞれのページング領域が比較的大きい場合、その領域において行われるページング動作に相当のネットワーク手段が回されなければならない。たった一つのMHの位置を突き止めるために、広い領域をカバーするための大規模なページング信号が送信されなければならない。もし、それぞれのページング領域が比較的小さい場合、ページング信号受信のために相当なエネルギーがMHにおいて使用される。もし、ページング領域が比較的小さい場合は、二つの隣接するページング領域の間の境界を頻繁に越えることとなる。MHが境界を越えるたびに休止モードから戻り、新しい領域を登録することから、電池が消耗する。
【０００８】
ページング領域の大きさにおけるもう一つの問題は、ページング領域の重なり合いである。現在の通信システムにおいて、それぞれのページング領域には限定された数の領域ID（通例一つ）が認められている。この条件のもとにそれぞれのページング領域が持つことができる領域IDに関し、動的にページング領域を定義、そして配置するために、いくつかの取り決めが必要である。
【０００９】
いかにして、しかるべきページング領域を構成するかに関し、多くの既存のリサーチがなされてきた。ある参考文献では、移動管理の平均的な信号送信コスト削減のために、異なる移動性と異なる発信特性により移動機のユーザを扱う個人位置領域概念の使用が提案されている。この概念に基づき、携帯電話ページングシステムのために、時間に基づく方法やプロフィールに基づく方法などの幾多もの取り組みが紹介されている。ただし、このリサーチは静的なページング領域を設定するためのもので、ページング領域構造は常に固定されていることを意味する。ただし、模擬実験の結果は、このようなページング領域の設計は幾多の状況において高いページングコストへとつながることを示している。これは、ユーザトラヒックが頻繁に変わることから起こり、静的ページング領域は、トラヒックパターンをあまりよくカバーできず、位置更新コストがかなり増加することを意味している。
【００１０】
現在のページング技術は、固定ページング領域を使用する。ページング領域は手動で定義および配置され、一度、定義・配置されれば変えられることは稀である。これらの手動で定義されたページング領域は、結果融通が利かず、通信トラヒックの変化に適用することができない。また、ページング領域は手動で定義されていることから、人的な間違いは避けられない。ページング領域の動的構造に関し、いくつかの提案がされているが、これらの提案は、結果領域IDの重なり合いを許すこととなる。これらの提案において、それぞれのMHは動的に、トラヒック及び移動により最適なページング領域の大きさを計算及び形成する。必然的に、それらページング構想においては、それぞれのページング領域は重なりあう。
【００１１】
他の事項として、このようなネットワークはゆえに、コレスポンデントノード間の動的なデータパケットの再ルーティングの機能を提供できるべきである。現在ある固定されたIPアドレス及び固定ノード関係に基づくインターネットアドレッシング及びルーティングのプロトコル及び構成はそのような機能を提供しない。同様に、現在ある固定ノードインターネットプロトコルは無線LANの使用には不十分である。
【００１２】
全体的なページングコストを最小限にすべく、ページング領域構成をもっとも効果的にするため、いくつものリサーチがなされてきた。システムの全体のページングコストは、位置更新コスト及びページングコストの二つである。位置更新コストは、ユーザが新しいページング領域へ動いたときにユーザの位置を更新するために使用される手段である。ページングコストはそれぞれのページング領域内のユーザへメッセージを送信するための手段である。適切に構成されたページング領域は、全体のページングコストを最小限に抑えることが可能である。
【００１３】
ダイナミックページング領域構成アルゴリズムが提案されている。例えば、個々の位置とともに、ページング領域の大きさと形状を動的に構成する方法が、提案されている。ただし、提案された方法において、位置領域の重なり合いを抑えることは困難である。ページング領域の重なり合いは、日本におけるパーソナルデジタル通信方式（PDC）、汎欧州デジタルセルラーシステム（GSM）及び広帯域符号分割多重アクセス方式（W-CDMA）システムなどのほとんどの携帯電話システムにおいて抑えられなければならない。これら通信システムは、基地局ごとに限られた数のページング領域IDをそのつど送信するように構成されている。結果、基地局が多くの位置領域に同時に属することは不可能である。
【００１４】
ゆえに、改善されたページング領域構成方法及び装置が必要となる。
【００１５】
【課題を解決するための手段】
前置きとして、開示されている本実施形態によれば、ページング領域は必要に応じて自動的に再構成されえる。ページング領域は、MHの移動トラヒックの変化に応じて適応的に再構成される。これらの実施形態によるシステム及び方法は、それぞれのページング単位領域に認められた、限られた数のみの領域IDという条件のもとで機能する。また、このシステム及び方法は異種類のアクセスネットワークにおいて機能する。このように、開示されている本実施形態によれば、MHの移動トラヒックの変化に応じてページング領域は自身を再構成する。
【００１６】
前記の概要はあくまで前置きである。この部分における事項は、発明の範囲を定義する特許請求の範囲を限定するものではない。
【００１７】
【発明の実施の形態】
ページングを使用するシステムにおいて、MHは活動と休止の二つのモードのもとに作動する。活発的にデータを送信又は受信しているときは、移動端末は活動的な状態にある。この状態において、ネットワークはMHの位置情報を把握しており、データを直ちに送信できる状況にある。もし、MHが一定の時間不活発な状態にあるときは、休止モードへと変化する。休止モードにおいて、ネットワークのMHの位置情報は陳腐である場合がある。もし、MHのためにデータが到着すれば、データ送信前にMHの位置は把握されなければならない。この、MHの位置把握の手順が広くページングと呼ばれている。
【００１８】
ページングは、MHの電池を消耗する無線インターフェースの受け止めに費やされる時間を削減するという点から、MHにとって有益である。更に、ページングはMHが基地局を行き来するたびというよりもページング領域境界を越えるときのみに信号発信が求められるという点から、ネットワーク信号発信コストも削減する。ページング領域が幾多もの基地局を持っている場合、移動端末をたどるために発信される相当量の信号が削減される。
【００１９】
ここからは図面を参照することとし、図１は、無線通信ネットワーク１００の実施形態の一つを示すブロック図である。ネットワーク１００は、第１最終ホップルータ（LHR）１０２、第２LHR１０４、第１LHR１０２に関連する複数のアクセスポイント（AP）１０６，１０８，１１０及び、第２LHR１０４に関連する複数のアクセスポイント（AP）１１２，１１４，１１６を含む。第１MH１２０は第一の複数のアクセスポイント１０６，１０８，１１０と通信しており、第２MH１２２は第二の複数のアクセスポイント１１２，１１４，１１６と通信している。ここで使用されている通り、通信は有線又は無線のどちらでも良い。有線通信の一例はTCP/IPによるデジタル通信である。無線通信の一例はW-CDMAネットワークによるIP通信である。
【００２０】
最終ホップルータ１０２及び１０４は、インターネット又はサブネットワークでありうるインターネットプロトコル（IP）ネットワーク１１８と通信している。最終ホップルータはMHが接続され得るエッジルータである。最終ホップルータは最終ホップサブネット（LHS）を収容する。最終ホップサブネットはMHが直接接続されるエッジサブネットである。このように、LHR１０２はLHS１３２を収容し、LHR１０４はLHS１３４を収容する。
【００２１】
アクセスポイント１０６，１０８，１１０，１１２，１１４，１１６は、それぞれのアクセスポイントに収容されるセル内のMHへ、第２層コネクションを通じてページングおよびアクセスを提供する装置である。アクセスポイントの例として、携帯電話又はパーソナル通信方式（PCS）ネットワーク内の基地局があげられる。このように、アクセスポイント１０６はセル１３６を、アクセスポイント１０８はセル１３８を、アクセスポイント１１０はセル１４０を、アクセスポイント１１２はセル１４２を、アクセスポイント１1４はセル１４４を、そしてアクセスポイント１１６はセル１４６を収容する。
【００２２】
MH１２０，１１２などのMHは標準的なIPホストであり、インターネットプロトコルを使用する遠隔装置と通信が可能である。標準的には、MHは移動性及び携帯性の面から電池により電力の提供を受ける。MHはさらに、低電力モードである、休止モードへ入る能力を有する。休止モードは、無線チャンネルの傍受を削減することにより普通のIPトラヒックの受信能力をMHが制限する状態をさす。これにより、MHの電池を節約でき、ネットワークへの信号負荷が削減できる。実際の双方通信には、休止モードから活動モードへと戻ることが要求される。
【００２３】
通信ネットワーク１００は、ネットワーク内の移動ホストへページングを提供するために構成されている。ページングは、休止モードにあるMHの位置を把握し、最終ホップ接続を達成するための無線アクセスポイントを通じての通信ネットワーク１００による信号発信である。最終ホップ接続において、MHはAPと双方通信を行っている。ページング領域は、休止状態のMHの位置把握のために作動される無線アクセスポイントの集団である。休止状態にあるMHは、MHのだいたいの位置をネットワークが維持できるために、ページング領域境界を越えるときにネットワークへ信号を送信することを必要とする場合もある。ページング領域クラスタは、共通のページング領域識別名を持つ、ページング領域の集団である。
【００２４】
典型的なIPページングプロトコルは、以下の通り作動する。
【００２５】
A.登録
MHが休止モードに入るとき、又はMHが現在のページング領域から動く場合、基地局のトラッキングエージェント（TA）へと登録する。トラッキングエージェントは、MHが休止モード又は活動モードにある間の位置の把握を担っており、またMHが活動モードに入った旨も把握する。登録は、MHの識別名（例えば、ホームアドレス）と、現在のページング領域の識別名を特定する。ページング登録を受け付けると、TAはホストの識別名と登録によって特定されているページング領域を統轄しているページングエージェント（PA）を結びつけるエントリを作成する。ページングエージェントは、ホストが休止モードにある間にパケットが到着した場合にMHに知らせることを担っている。また、ページングエージェントは、ホストが休止モードに入った折に、休止管理エージェント（DMA）へ報告を送信する。休止管理エージェントは、休止モードにあるホストへパケットが送信された旨を検知する。
【００２６】
B.パケット送信
休止期間に、もしMHに対しネットワークへデータが到着したときは、データ送信に際しホストの位置がまず把握されなければならない。DMAがホストに対するパケットを受信すると、ホストが休止中となっていることからパケットを緩衝させる。そして、DMAはTAにホストの現在のPAを照会する。TAはそれに対して、PAにMHを呼び出すよう求める。PAは、PAに属するネットワークの全ての基地局にページングリクエストを送信する。最後に、それぞれの基地局は休止状態にあるMHにダウンリンクによってページを含む無線信号を送信する。MHが休止モードから活動モードへ戻ると、ページング基地局へアップリンクにより応答メッセージを送信する。MHは活動状態へと入り、現在の位置を登録する。例えば、MHはケアオブアドレスをDMAに対し提供する。そして、DMAは登録されたMHに対し、パケットを転送する。
【００２７】
C.ダイナミックページング領域構造
適切なページング領域の構造は、ページングトラヒックと位置更新トラヒックとの間のトレードオフに基づく。ページング領域の大きさが増加するにつれ、ページングコストが増加し、位置更新コストが減少する。逆に、ページング領域が減少するにつれ、ページングコストが減少し位置更新コストが増加する。概ね、ページングトラヒックはページング領域内の基地局に対する呼び出しに比例し、位置更新トラヒックはページング領域境界を越えるMHの数に比例する。
【００２８】
ダイナミックページング領域構造アルゴリズムは全体のネットワーク位置更新コスト及びページングコストを最小限に抑えなければならない。概ね、位置更新は無線手段のみならず、TA内の分散位置データベースの負荷にも影響するという点から、ページングトラヒックは位置更新トラヒックに比べ重要でないとされる。
【００２９】
この記述において、MHに現在の位置情報を特定させるためにそれぞれの基地局又は基地局ルータから定期的にまたは連続的にビーコンフレームが送信されているものとする。ビーコンフレームは少なくともページング領域ID（PA-ID）と基地局ID（BS-ID）を含んでいなければならない。
【００３０】
PA-IDは現在のページング領域を示す。基地局が自身のページング領域を変えたときにPA-IDは変わる場合もある。BS-IDは独自に基地局を特定する。BS-IDは固定されている。システム開始時には、PA-IDとBS-IDは同一であるものとする。
【００３１】
更に、MHは休止モードにあっても基地局からビーコンを受け止めることができるものとする。更に、MHは自身の現在の位置のセル内のBS-IDを特定できるものとし、その後の使用のためにこの情報を保存できるものとする。
【００３２】
更に、それぞれの基地局ルータはページングエージェント（PA）と休止管理エージェント（DMA）の能力を持つものとする。また、PA-IDとBS-IDは、インターアクセスポイントプロトコルなどの第２層から第３層マッピングプロトコルを使用する基地局ルータの第３層アドレス（IPアドレス）へ位置付けられるものとする。即ち、BSRのIPアドレスはビーコン情報から取得できるものとする。
【００３３】
ネットワーク通信プロトコルは、移動トラヒックサンプリングのメッセージを定義する。MHはビーコンを受け止め、そして最新のビーコン情報を保存することができる。この保存されたデータは、次の基地局へと渡すために使用される。MHが他のページング領域へ動くと、休止モードから活動モードへと戻り、基地局へ送信することを通してTAとDMAにおける自身の位置情報を更新する。その折に、MHは基地局へ登録されていないにせよ、前のビーコンのメモリを含んでいる。新しい基地局に対し、情報を送信するために、メッセージが定義される。通知メッセージは、MHの出所を新しい基地局が認識できるよう、前の基地局のPA-IDとBS-IDを含んでいる。
【００３４】
図１，２，３，４及び５は模範的なページング領域のネットワークの一例を示す。図１において、LHR１０２と１０４それぞれは３つのアクセスポイントが配置される最終ホップサブネットを作成する。それぞれのAPはそれぞれのセルを定義する。
【００３５】
図２〜５は更なる模範ページング領域のネットワークの更なる例を示す。図２において、ネットワーク２００は単一のLHR２０２と一つのAP２０４を含む。セル２０６はAP２０４に収容される。LHR２０２は一つのLHS２０８と一つのページング領域２１０、そして同延のLHS２０８を定義する。図３において、ネットワーク３００は一つのLHR３０２と二つのAP３０４、３０６を含む。AP３０４はセル３０８を収容し、AP３０６はセル３１０を収容する。LHR３０２及びAP３０４、３０６はLHS３１２及び同延のページング領域３１４を定義する。
【００３６】
図４において、ネットワーク４００は二つのLHR４０２、４０４を含む。LHR４０２は二つの関連するAP４０６，４０８をもつ。それぞれのAP４０６，４０８は関連するセルを収容する。動様に、LHR４０４は二つの関連するAP４１０，４１２を持つ。AP４１０，４１２それぞれは、関連するセルを収容する。AP４０６，４０８はLHS４１４を形成する。AP４１０，４１２はLHS４１６を形成する。４つ全てのAP４０６，４０８，４１０，４１２はページング領域４１８を形成する。
【００３７】
図５のネットワーク５００において、LHR５０２は４つの関連するAP５０４，５０６，５０８，５１０を持つ。それぞれのAPはそれぞれのセルを収容する。APのそれぞれの対はページング領域を形成する。このように、AP５０４と５０６の対は、ページング領域５１２を形成し、AP５０８と５１０の対はページング領域５１４を形成する。ページング領域５１２，５１４はLHS５１６を形成する。
【００３８】
図６のネットワーク６００において、二つのLHR６０２、６０４は、三つのアクセスポイント６１０，６１２，６１４とともにページング領域６１６を定義する。AP６１０は第一アクセスネットワーク６２０と関連する。AP６１２は第２アクセスネットワーク６２２と関連する。AP６１４は第３アクセスネットワーク６２４と関連する。AP６１０，６１２，６１４それぞれは関連するセルを収容し、関連するセル内でMHに対して無線通信を提供する。ページング領域６１６はアクセスネットワーク６２０，６２２，６２４それぞれの部分を網羅する。
【００３９】
このように、ページング領域はあらゆる、さまざまな構造で配置されるものとする。ページング領域は、最終ホップサブネットワーク及びアクセスネットワーク内及び間において存在できるものとする。ここに開示されている実施形態に基づき、ページング領域はシステム事情により動的に再構成されるものとする。
【００４０】
図７は無線通信システムにおけるページング領域の再構成を示すブロック図である。図７は道路７０２の傍の携帯電話無線通信ネットワーク７００を示す。ネットワーク７００はセル７０４，７０６，７０８といったセルを収容する複数のアクセスポイントを含む。最初の段階では、それぞれのセルは最小のページング領域に対応する。最小のページング領域は、図７の左側に描かれた道路７０２と対称の円によって定義される。ネットワーク７００の無線トラヒックが道路７０２の車両交通量とともに増加すると、図７の右側に描かれた一つの大きいページング領域７１０を定義すべく、道路の傍のページング領域は統合する。その後、トラヒックが許すと図７の左側に描かれているようにページング領域は最小の単位まで解体される。
【００４１】
好ましくは、ページング領域は人的努力と間違いを最小限にするために自動的に構成されることが望ましい。ページング領域は、ネットワーク内におけるページング効率を高めるためにユーザの動きに適応されることが望ましい。更に、このページング領域形成を提供する方法は、限られた重複許容構造を提供することが望ましい。また更に、ページング領域形成の方法は、多くの異種類のアクセスネットワークに適応可能であることが望ましい。
【００４２】
図８は、ページング領域形成の他の例を示すブロック図の一続きである。図８は、無線通信システム８００内のページング領域の時間的変化を示している。図８において、それぞれの六角形は最小のページング領域を示している。組み合わさった、または形成されたページング領域は、共通のフィルパターンを持っている。図８の上部左側から始まり、MHの移動トラヒックが領域ｃから領域ｄへと増加する。MHのトラヒックの移動は図８のそれぞれの図の中で、矢印によって示されている。この描写は、実際のシステムにおけるトラヒックの単純化である。このトラヒック移動の結果、領域ｄは領域ｃの領域IDを取り入れ、図８の上部右側に示されている領域dの変化したフィルの通り、領域ｃとｄは一つのページング領域となる。
【００４３】
以後、上部右側の図に示すとおり、MHトラヒックは領域aから領域ｂへと増加する。その結果、領域ｂは領域aの領域IDを取り入れ、領域ｂの変化したフィルが示すとおり、領域aと領域ｂは一つのページング領域となる。以後、図８の下部右側の図に示すとおり、MHトラヒックは領域ｂから領域ｃへと増加する。その結果、下部左側の図に示すとおり、領域ｃとｄは領域ｂの領域IDを取り入れ、領域a、ｂ、ｃ及びｄは一つの広いページング領域となる。このように、この模範的実施形態において、ページング領域はMHの移動トラヒックの変化に応じて自身を再構成する。
【００４４】
図９は、MH９０２と最終ホップルータ９０４，９０６の二つの模範的実施形態を示すブロック図である。これらそれぞれの装置と、その構成について、以下で説明する。
【００４５】
MH９０２は、例えば携帯又はPCS電話、パーソナルデジタルアシスタント（PDA）、パーソナルコンピュータ、又はこれらの組み合わせ又は他のあらゆる電子装置によって具体化される。MH９０２は、ホストレポーターエージェント９０８と第３層移動エージェント９１０を含む。典型的な実施形態において、MH９０２は、電池、プロセッサ、メモリ、ユーザインターフェース及び無線回路を含む移動又は携帯型電子装置として具体化される。これらの構成要素は、図面を必要以上に煩雑にしないために、図９には示されていない。MH９０２の電力は電池によって供給される。プロセッサは、マイクロプロセッサ、マイクロ制御デジタル信号プロセッサ、他の論理回路又は、MH９０２の動作を制御する装置の組み合わせでよい。プロセッサは、フラッシュ,EPROMまたはRAMなどの半導体メモリに保存されている、プログラム指令に応じて作動する。ユーザインターフェースはユーザにMH902の制御をさせ、ディスプレイ、キーパッド、スピーカ、マイクロフォン他の構成要素を含むものでよい。無線回路は、最終ホップルータ９０４などの遠隔装置との無線通信を可能にする。典型的実施形態の無線回路は、それぞれに符号化、復号化及び変調、復調を行う送信機及び受信機を含む。無線回路により、MH９０２は最終ホップルータ９０４と無線リンク９１４を通して通信する。
【００４６】
ホストレポーターエージェント９０８と第３層移動エージェント９１０は、ソフトウェア処理制御動作及びMH９０２内の通信のために導入されたものである。ホストレポーターエージェント９０８はLHR９０４，９０６などの最終ホップルータのページング領域形成エージェントへMH９０２の移動についての報告を担っている。第３層移動エージェント９１０は、LHRの休止管理エージェントへ、パケットの到着を知らせる。以下に、ホストレポーターエージェント９０８と第３層移動エージェント９１０の詳細を説明する。
【００４７】
図９の模範的実施形態の最終ホップルータ９０４，９０６は、ページング領域形成エージェント９２０、休止管理エージェント９２２、ローカルページングエージェント９２４、ローカルトラッキングエージェント９２６及び第３層移動エージェント９２８を含む。典型的な実施形態において、最終ホップルータ９０４と９０６はMH９０２などの移動ホストに無線又は有線のリンクを提供する。リンクは、１つ以上のMHと無線通信を行っている、携帯電話基地局などのアクセスポイントへの有線リンクを含む。最終ホップルータ９０４と９０６は更に、他のルータなどの他のネットワーク装置へ有線リンクを提供する。最終ホップルータ９０４と９０６との通信は、インターネットプロトコル（IP）によるものが好ましいが、いかなる適切なデータ通信プロトコルまたは基準であってもかまわない。
【００４８】
模範的な実施形態において、最終ホップルータ９０４と９０６は、プロセッサ、メモリ及び通信回路を含む。プロセッサは、最終ホップルータ９０４と９０６の動作の制御用のマイクロプロセッサ又は他のデジタル論理であっても良いが、いかなる適切な制御回路であってもよい。プロセッサは、メモリに保存された、プログラム指令とデータとともに作動する。通信回路は、最終ホップルータ９０４、９０６と他のネットワーク装置との間のデータと指令の通信を提供する。プロセッサ、メモリ及び通信回路は、必要以上に図面を煩雑にしないために、図９には示されていない。
【００４９】
図９において、最終ホップルータ９０４と最終ホップルータ９０６は、実質同じものとして示されている。しかし、これらの構成要素は、動作の必要に応じて構造及び動作を広く変化可能であることが望ましい。
【００５０】
ページング領域形成エージェント（PCA）９２０は、最終ホップルータ９０４と９０６と通信しているMHの移動レポーターエージェントからの移動報告を受信するために作動する。PCAは、休止管理エージェント（DMA）によりMHへのパケットの到着を知らされ、ローカルページングエージェント（LPA）形成へページング形成メッセージを送信する。PCA９２０が肯定的又は否定的な結果をLPAクラスタから受信すると、PCAはDMAへ知らせる。PCA９２０の構造及び動作の詳細は、図１０とともに以下に説明をする。
【００５１】
休止管理エージェント（DMA）９２２は、休止モードにあるMH９０２などのMHに対するパケット送信を探知し、MHを呼び出すようPCA９２０に知らせる。休止モードは、MHの電池を節約するために、MHが入る低電力休止状態である。PCA９２０が、MHに対しインターネットなどのネットワークへのルータブル接続が存在することを知らせると、DMA９２２はMHに対しパケットを配信するよう手配をする。加えて、MHは、MHがページング領域を変更するとともにDMAを変更してもかまわない。
【００５２】
ローカルページングエージェント９２４（LPA）はMH９０２などのMHへの警告を担っている。更に、LPA９２４は、ページング領域を特定するために、MHに対してリンクを通じて周期的に広く情報を送ることによりページング領域を維持している。この模範的実施形態において、それぞれのページング領域は、複数のLapsに収容される。
【００５３】
ローカルトラッキングエージェント（LTA）９２６は、MHが休止モード又は、活動モードにあるとき、また、MHが同一の最終ホップサブネット（LHS）にあるときに、MHの位置をたどることを担っている。第３層移動エージェント９２８は、それらの用語がこれまで知られている通り、Mobile  IP  Home  Agent又はForeign  Agentであってよい。第３層移動エージェント９２８はDMA９２２に対して、IPパケットの到着を知らせる。
【００５４】
PCA９２０、DMA９２２、LPA９２４、LTA９２６及び第３層移動エージェント９２８は、最終ホップルータ９０４と９０６に実施されるソフトウェア処理であることが望ましい。最終ホップルータ９０４と９０６のプロセッサ又は他の制御回路の動作のための適切なプログラムコード及びこれらのソフトウェア処理の実行のためのデータは最終ホップルータ９０４と９０６のメモリに保存されてよい。
【００５５】
図１０は図９内のページング領域形成エージェント９２０の動作ブロック図である。模範的実施形態におけるページング領域形成エージェント９２０は、可能性マップ（PMAP）１００２、クラスタマップ１００４、可能性マップ更新処理１００６、形成処理１００８及びページング転送処理を含む。これらページング領域形成エージェント９２０の構成要素は、図９内のLHR９０４、９０６などの最終ホップルータの制御のためのソフトウェア処理のために具体化されることが望ましい。
【００５６】
ページング領域形成エージェント９２０は、どのページンググループにPCA９２０が統合されるべきかを決定するために、可能性マップ１００２を維持する。PCA９２０は、他のページング領域形成エージェントとの関係を維持するために、クラスタマップを使用する。可能性マップ更新処理（PUP）１００６は、可能性マップ１００２を維持するために作動する。形成処理１００８は、ページング領域形成エージェント９２０の中心機能を実行する。ページング転送処理（PFP）は、ページング要求の転送を実行する。これらそれぞれの処理を、以下に詳細に説明する。
【００５７】
図１１及び１２は、図９に示すページング領域形成エージェント９２０の可能性マップ１００２の一つの実施形態の構造を示すものである。可能性マップ１００２は、MHの過去の移動トラヒックの統計記録を含む。可能性マップ１００２において、それぞれの最小ページング領域又はページング単位領域は、図１１に示すとおり、二つの空間変数（X,Y）によって定義される。
X=｛ξ1, ξ2,... ξj｝,
ここで、ξiはページング領域iの領域IDを示す。
Y=｛η1, η2...ξk｝
ここで、ηiはページング領域iのネットワークアドレス識別子（NAI）を示す。NAIはIPアドレスでよい。
【００５８】
図１２に一例を示す。過去のネットワークの動作において、（ξ1, η1）から（ξ５, η５）へ、特定の時間帯にMHトラヒックが移動した可能性を４０％とする。MHトラヒックが（ξ２, η２）から（ξ５, η５）へ動いた可能性を３０％とする。MHトラヒックが（ξ２, η６）から（ξ５, η５）へ動いた可能性を２０％とする。MHトラヒックが（ξ８, η７）から（ξ５, η５）へ動いた可能性を１０％とする。その結果、可能性マップ１００２は、図１２において「二次元マップ」と名づけられたテーブル１２０２を持つ。この二次元マップは、「一次元マップ」と名づけられたテーブル１２０４へと変換される。変換において、同一のページング領域ID（ξ）から来る可能性が、加えられる。この一次元マップは、過去の移動トラヒックの統計によるとMHトラヒックが領域（ξ２）より一番多くその領域に来ていることから領域ID（ξ５）は領域ID（ξ２）へと変化するべきことを示している。このように、可能性マップ１００２はどのページング領域が統合すべきか、又は、どのページング領域がお互いを収容すべきかを示す。
【００５９】
図１３は、図１０のページング領域形成エージェント９２０のクラスタマップ（CMAP）１００４の構成を示す。クラスタマップ１００４は、どのページング領域が現在統合しているか、又はどの領域に属しているかの情報を維持している。図１３に示すとおり、クラスタマップ１００４は３種類の情報を保存、すなわちデフォルト情報１３０２、ブランチ情報１３０４及びルート情報１３０６を保有している。動作の最初の段階において、ページング領域は独立しており他のどの領域にも統合していない。
【００６０】
図１４は、デフォルト情報１３０２の構成の一つの実施形態を示す。デフォルト情報１３０２は、このような独立したページング領域のページング領域ID１４０２を含む。デフォルト情報１３０２は更に、ページング形成エージェント（PCA）のネットワークアドレス識別子（NAI）１４０４を含む。NAIはPCAにとって固有であり、例えばIPアドレスを含む。
【００６１】
図１５はブランチ情報１３０４の構成の一つの実施形態を示す。この実施形態において、ブランチ情報１３０４は、形成グループのページング形成エージェントのルートページング識別子（PID）１５０２、先行のページング形成エージェントのネットワークアドレス識別子１５０４、及び現在のPCAを継承しうるページング形成エージェントのネットワークアクセス識別子１５０６のリストを含む。
【００６２】
図１６は、ルート情報１３０６の構成の一つの実施形態を示す。ルート情報１３０６は、ページング形成エージェントのデフォルトPIDと同等であることが望ましいルートページング識別子１６０２を含む。ルート情報１３０６は更に、ページング領域形成エージェントを継承しうるもののネットワークアドレス識別子の完全リスト１６０４を含む。リスト１６０４において、それぞれの一番近い継承しうるPCAは、近隣のPCAネットワークアドレス識別子のリストに関連付けられている。したがって、図１６におけるリスト１６０４への最初の登録１６０６は、継承しうるPCA  NAIのリスト１６０８である。同様に、リスト１６０４への二番目の登録１６１０は、継承しうるPCA  NAIのリスト１６１２を含む。好適なツリー構造において、登録リスト１６０８は更に、関連したNAI１６１４などのリーフPCA  NAIを含む。
【００６３】
ブランチ情報１３０４とルート情報１３０６は、図８の例を用いて説明できる。ページング領域a、ｂ、ｃ、ｄは全て領域aに指定された同一のIDを持つ。領域aはルート領域と呼ばれ、ルート情報をもっている。ルート情報は例えばツリー構造のｂ、ｃ及びｄに属する全てのページング領域を示す。ルート領域以外のページング領域は、すぐ前のページング領域とそれから引き継いでいる全てのページング領域を示すブランチ情報をもっている。ゆえに、例えば、領域ｂはすぐ前の領域がａで、引き継いでいる領域がｃとｄであることを示す情報を持っている。
【００６４】
図１７は、図１０における形成処理１００８の動作ブロック図である。形成処理（ＣＰ）１００８は、候補サーチ機能（ＣＳＦ）１７０２、形成管理機能（ＣＭＦ）１７０６、ページング管理機能（ＰＭＦ）１７０８及び実行評価機能（ＰＥＦ）１７１０を含む。可能性マップ１００２からの情報に基づき、候補サーチ機能１７０２は統合されるか、又は他のページング領域から離れるページング領域候補を見つけ出す。形成決定機能１７０４は、見つけ出されたページング領域候補の中から、どのページング領域が実際に統合されるべきか、または離れるべきかを決定する。例えば、一つのみの領域ＩＤを持つことが許され、また既に他の領域に統合されているページング領域は、現在の領域から離れない限り他のどのページング領域とも統合することはできない。形成決定機能１７０４は、現在のどの領域から離れ、他の領域と統合すべきかを決定できる。形成管理機能１７０６は、形成決定機能１７０４による決定に基づき、クラスタマップ１００４を更新する。形成管理機能１７０６はまた、ページング領域が離れた及び/又は統合した他の領域のクラスタマップを更新する。
【００６５】
それに対し、ページング管理機能１７０８はページングの頻度を示すページング転送処理１０１０からの情報と、例えばいくつのＭＨが一つの領域からもう一方へ動いたかを表すＭＨトラヒックの変化を示す可能性マップ更新処理１００６からの情報を管理する。実行評価機能１７１０は、現在のページング領域の大きさを判断する。概ね、ページング動作の数が増えるにつれ、ページングネットワークトラヒックの全体のコスト削減のためにページング領域の大きさは減少すべきである。これに対し、ＭＨの移動トラヒックが増加するにつれ、ページング領域はそのサイズが増加すべきである。
【００６６】
図１８は、図１０におけるページング転送処理１０１０の動作ブロック図である。ページング転送処理は、クラスタマップ発見機能（ＣＭＤＦ）１８０２、ページング転送機能（ＰＦＦ）１８０４及びページング通知機能（ＰＮＦ）１８０６を含む。クラスタマップ発見機能１８０２は、休止メモリエージェント（ＤＭＡ）動作１８０８からページングトリガパケットを受信し、クラスタマップ１００４にどの領域にパケットは配信されるべきかを決定するよう求める。決定された領域は、ページングトリガパケットが向けられたＭＨを含んでいる。ページング転送機能１８０４は、クラスタマップ発見機能１８０２によって決定された領域にページングトリガパケットを転送する。ページング通知機能１８０６は、形成処理１００８へ、ＤＭＡ動作１８０８から受信されたページングトリガパケットの頻度を通知する。
図１９は図１０における可能性マップ更新処理１００６の動作ブロック図である。可能性マップ更新処理１００６は、可能性マップ維持機能（ＰＭＭＦ）１９０２、報告受信機能（ＰＡＦ）１９０４及び移動通知機能（ＭＮＦ）１４０６を含む。報告受信機能１９０４はＭＨ９０２のホストレポーターエージェント（ＨＲＡ）９０８（図９）からの登録信号を受信する。報告受信機能１９０４による通知によって、可能性マップ維持機能１９０２は行き来しているＭＨの統計を計算し、可能性マップ１００２を更新する。移動通知機能１９０６は、行き来しているＭＨの頻度を決定し、形成処理１００８へ通知する。
【００６７】
図２０は、ＭＨ９０２内のホストレポーターエージェント（ＨＲＡ）９０８（図９）の動作ブロック図である。ＨＲＡは、レポーター処理（ＲＥＰＦ）２００２、前位置テーブル（ＰＬＴ）２００４と現在位置テーブル（ＣＬＴ）２００６を含む。ＭＨが移動すると、レポーター処理２００２は前位置テーブル２００４と現在位置テーブル２００６の両方を更新し、ＭＨを新しい領域に登録する。レポーター処理２００２は、現在のページング領域形成エージェントに対して、ページング領域移動を報告する。図２０に示されている通り、前位置テーブル２００４は、ページング識別子（ＰＩＤ）と前のページング領域形成エージェントのネットワークアクセス識別子（ＮＡＩ）を記憶する。同様に、現在位置テーブル２００６は、ページング識別子（ＰＩＤ）と現在のページング領域形成エージェントのネットワークアクセス識別子（ＮＡＩ）を記憶する。ＭＨが他のページング領域に移動すると、レポーター処理２００２は現在位置テーブル２００６情報を前位置テーブル２００４へと移す。
図２１は、それらのページング領域形成エージェント（ＰＣＡ）によって示されるページング領域の形成を示すものである。クラスタ２１０２は、クラスタ２１０２内の他の全てのＰＣＡが属するか関連する一つのＰＣＡを持つ。このようなＰＣＡはルートＰＣＡ２１０４と呼ばれる。クラスタ２１０２はまた、ツリー構造が終了するＰＣＡを持つ。これらは以下、リーフＰＣＡ２１０８と呼ばれる。ツリー構造内のルートＰＣＡ２１０４とリーフＰＣＡ２１０８間の他のＰＣＡは中間ＰＣＡ２１０６と呼ばれる。
【００６８】
図２２〜２６は形成動作を示す。図２２は統合動作を示す。統合動作において、現在どのクラスタにも属さないＰＣＡは他のクラスタか既存のＰＣＡクラスタの一部に統合する。図２１に示されるとおり、ＰＣＡ２はクラスタ２２０２を形成すべくＰＣＡ１と統合する。以後、ＰＣＡ３はＰＣＡ１とＰＣＡ２のクラスタ２２０２と統合する。
【００６９】
図２３は「分離」と呼ばれる第２の形成動作を示す。この動作において、リーフＰＣＡ又は中間ＰＣＡはＰＣＡクラスタを離れる。図２３において、ＰＣＡ３はＰＣＡ１とＰＣＡ２を構成しているクラスタ２３０２から自身を切断する。その結果、クラスタ２３０２はＰＣＡ１とＰＣＡ２のみを含む。
【００７０】
図２４は、「クラスタ統合」と呼ばれる第３の動作を示す。クラスタ統合において、ルートＰＣＡはＰＣＡ又は既存のＰＣＡクラスタの一部と統合する。図２４において、ＰＣＡ１，ＰＣＡ２及びＰＣＡ３を構成しているクラスタ２４０２は、ＰＣＡ４及びＰＣＡ５を構成しているクラスタ２４０４と統合する。統合したクラスタ２４０６はＰＣＡ１，ＰＣＡ２，ＰＣＡ３，ＰＣＡ４及びＰＣＡ５の全てを含む。ＰＣＡ１はクラスタ２４０２のルートクラスタであったが、この結果統合したクラスタ２４０６のルートクラスタとなる。
【００７１】
図２５は、「クラスタ刈り」と呼ばれる第４の動作を示す。この動作において、ルートＰＣＡまたは中間ＰＣＡは、最初のクラスタから続きのＰＣＡのセットを刈り取るか又は取り除く。この結果によるクラスタのＰＣＡは、それぞれのクラスタのルートＰＣＡとなる。図２５に示すとおり、最初のクラスタ２５０２は、二つの別々のクラスタ２５０４と２５０６になる。ＰＣＡ４とＰＣＡ５を構成しているクラスタ２５０４はＰＣＡ１，ＰＣＡ２，及びＰＣＡ３を構成しているクラスタ２５０６から自身を切断する。
【００７２】
図２６は「クラスタ分割」と呼ばれる最後の動作を示すものである。この動作において、ルートＰＣＡはクラスタを離れ、クラスタ情報を以降のルートクラスタへと移す。図２６において、ＰＣＡ１はクラスタ２６０２のルートＰＣＡである。ＰＣＡ１は、他のＰＣＡを残しつつ、クラスタ２６０２を離れる。ＰＣＡ２は、残りのクラスタ２６０２のルートＰＣＡとなる。
【００７３】
以下のテーブルは、ここに説明されたシステム及び方法の一つの実施形態に使用されたメッセージを示すものである。｛JOIN REQ, ALLOW JOIN, DENY JOIN｝は統合動作のメッセージである。｛LEAVE REQ, LEAVE ACK｝は分離動作のメッセージである。｛PRUNE REQ, PRUNE ACK｝はクラスタ刈り動作のメッセージである。分離及びクラスタ刈り動作にはALLOW又はDENYメッセージはない。最後のメッセージはトラヒック報告のためのものである。これらのメッセージは、ページングクラスタ内のマスタースレーブ関係を通して、ホップごとに伝えられる。
テーブル：プロトコルメッセージ
メッセージ    記述                    発信元  受信先
JOIN REQ      クラスタ統合のため送信  ROOT     ROOT
ALLOW JOIN    JOIN REQ許可            ROOT    ROOT
DENY JOIN     JOIN REQ拒絶            ROOT    ROOT
LEAVE REQ    クラスタ分離のため送信 BRANCH,LEAF ROOT
LEAVE ACK     LEAVE REQのAck       ROOT        BRANCH,LEAF
PRUNE REQ     ツリーを切るため送信  ROOT        BRANCH,LEAF
PRUNE ACK     PRUNE REQのAck       BRANCH,LEAF ROOT
PMAP REPORT   PMAP報告              BRANCH,LEAF ROOT
【００７４】
最初の段階では、基地局ルータ（ＢＳＲ）は孤立している。全てのBSRは、それぞれのブートストラップ段階の始まりにおいて、Main（）プロシージャを実行する。Main()プロシージャの一実施形態を以下に示す。プロシージャの実行において、BSRは二つのクラスタへと分け隔たれる。クラスタは、相互接続されたBSRのセットである。クラスタは、単一のBSRによって構成されても良い。それぞれのクラスタには、ROOT  BSRは一つのみである。一つのBSRクラスタを占める部分はROOT  BSRのみである。ROOT  BSRが撤退すると、ROOTとしての機能が停止し、再びROOTとならない限りその後のROOTアルゴリズムにおいて不活発となる。
【００７５】
Main()プロシージャは、BSRの状態に応じて、プロシージャを求める。もしBSRがROOTであれば、Root  Main()を求める。さもなければOther  Main()プロシージャを求める。これは、非同期式分散アルゴリズムであることから、ロックミューテックス変数がBSR内の重要部分を保護することを担っている。
Main () [//Main for all
1  prepare a mutex Lock;
2  variable v is this BSR;
3 while true [
4    if (v == ROOT)
5       Root Main (v);
6    else
7        Other Main (v);
8   ]
9 ]
【００７６】
Root#Main()プロシージャは、T周期において、上のテーブルにおいて定義されているメッセージを待つ。非同期の到着するリクエストを受信するために、Wait#For#Input()プロシージャが使用される。Wait#For#Input()プロシージャが戻ると、受信したメッセージを処理するRoot#Msg#Recv()プロシージャを実行する。定数Tは、T周期においてユーザ移動とページングトラヒック統計がサンプリングされたものとする。Tの選択は、操作者によって設定されても良い。
【００７７】
T周期の後、Root#Main()プロシージャはRoot#Trigger()プロシージャを求める。このプロシージャは、ROOT  BSRが統合か刈り取りかの動作を行うことを判断する。Root#Trigger()プロシージャは、以下に詳細に記述する。
Root#Main(v) [// Main for ROOT
1  var#BSR u;
2  t0 = current#time();
3  while(current#time()  -  t0  T period)[
4     Wait#For#Input(&Root#Msg#Recv(),timeout);
5  ]
6  switch(Root#Trigeer(v,PMAP,&u)) [
7     case JOIN :
8       Join(u,v); break;
9     case PRUNE :
10      Prune(); break ;
11    case default :
12      break;
13  ]
14  return
15 ]
【００７８】
Root#Msg#Recv()プロシージャは、Root#Main()プロシージャによって求められる。その処理は、メッセージを受信する。PMAP REPORTメッセージはスレーブＢＳＲからメッセージを受信する。全ての隣接するページング領域を検知するために、クラスタ内の全てのPMAP情報はROOT  BSRへと報告されなければならない。クラスタを統合することを要求するJOIN REQメッセージは、他のROOT BSRから来る。JOIN REQメッセージは、マスタースレーブルーピングを避けるために、要求されているROOT BSRの現在のPA-IDを含まなければならない。LEAVE REQメッセージは、クラスタからの分離を要求するスレーブＢＳＲから来る。Root#Msg#Recv()プロシージャはまた、データ不整合をさけるために、ロックをメッセージ受信後に取得する必要がある。ロックが取得できない場合は、エラーメッセージを前の送信者へと送信する。
Root#Msg#Recv(v)  [// Message handler for Root
1    Msg = receive();
2    if(acquire (Lock) == true) [
3     switch(msg.type)  [
4       case PMAP#REPORT:
5         PMAP   msg.body; break;
6       case JOIN REQ:
7         Join#hdr(msg,v); break;
8        case LEAVE#REQ:
9          Leave#hdr(msg,v); break;
10      ]
11      release(Lock);
12     ]  else [
13         send(msg.sender, ERROR);
14     ]
15    ]
【００７９】
Join#hdr()プロシージャは、他のROOT  BSRからの統合リクエストを処理する。これは、分散プロシージャであるため、近隣のページング領域に関して古い情報を持っている場合がある。プロシージャは、現在のスレーブの可能性マップを求めることにより、近隣の情報を取りに行く。そして、ROOTは、以下で詳細に説明をするプロシージャ、CostChange()を計算する。もし、CostChange()プロシージャの結果が正数であれば、Join#hdr()プロシージャは、クラスタの最大サイズKを調べる。クラスタのサイズがK未満の場合は、ROOT  BSRは統合を認める。そして、ツリートポロジーと統合動作に関連する近隣情報を更新しなければならない。最後に、ROOT  BSRはALLOW  JOINメッセージを発信者に送信する。さもなければ、DENY  JOINによって応答する。プロシージャはまた、ミューテックスロック以内で実行されなければならない。
Join#hdr(msg,v)  [// Join request handler
1  fetch current PMAP into from slaves;
2  if (Cost Change (v) == positive) [
3    if (total size of the cluster    K) [
4     msg.sender added to the cluster ;
5    Update topology information;
6    Update neighbor information;
7    send(msg.sender,ALLOW#JOIN); return;
8   ]else
9    send(msg.sender, DENY#JOIN); return;
10  else
11   send(msg.sender, DENY JOIN); return;
12 ]
【００８０】
Leave()プロシージャは分離リクエストを処理する。ROOT  BSRはBRANCH及びLEAF  BSRに随時分離することを許可する。Leave()プロシージャは、リクエスタを切断することで、ツリートポロジーを更新する。その後、ROOT  BSRは肯定応答を送信する
Leave-hdr(msg,v) [//Leave request handler
1  msg.sender removed from the cluster;
2  send(msg.sender, LEAVE#ACK);
3 ]
【００８１】
Join()プロシージャが、ROOT  BSRが他のクラスタに統合する決定をした後に再び要求される。メッセージを送信する前に、ロックが取得されなければならない。他のROOT  BSRはROOT  BSRの統合を認めた場合、リクエスタはALLOW＿JOINメッセージを受信する。そして、リクエスタのROOT  BSRはROOTではなくなり、BRANCHまたはLEAFとなる。
Join(u,v) [// Join request sender
1  if (acquire (Lock) == true) [
2     send(u,JOIN#REQ);
3     msg = receive();
4     if (msg.type == ALLOW#JOIN) [
5        v retired from root;
6        release (Lock);
7        return
8      ] else if (msg.type == DENY#JOIN) [
9         release(Lock);
10        return;
11       ]
12     ] else
13   return;
14 ]
【００８２】
ROOT  BSRがクラスタ内の幾つかのBRANCHツリー又はリーフを刈り取ることを決定した後、Prune()プロシージャが要求される。この刈り取り決定は、以下に記載するとおりにRoot  Trigger()によって決定される。
Prune(v) [// Prune request sender
1  if (acquire(Lock) == true) [
2     for each remaining w 2 v's slaves;
3       send(w,PRUNE#REQ);
4       msg = receive(w);
5       if (msg.type == PRUNE#ACK)
6           Separate w;
7  else
8 return;
9   ]
10 ]
【００８３】
Other#Main()プロシージャは、BRANCHとLEAF  BSRのためのものである。T周期の後、自身のROOT  BSRへ可能性マップ記録が送信される。BRANCHとLeaf  BSRは唯一の任意の動作である分離のみが認められている。Others#Trigger()プロシージャは、以下に記載の通り現在のクラスタから離れるかあるいはとどまるかを決定する。BSRが離れる決定をすると、ROOT  BSRに対しLEAVE＿REQメッセージを送信する。ROOT  BSRより、リクエストをしたBSRが許可を受信すると、トポロジーと近隣情報が更新される。特筆すべきは、BSRがROOT状態にないときは、分離動作は許可されない点である。
Other Main(v)[// BRANCH and LEAF's Main
1  t0 = current time();
2  while(current time()  t0   T period)[
3  Wait For Input(&Other Msg Recv,timeout);
4 ]
5 send(master, PMAP#info);
6 if (Leave#Trigger(PMAP,v) == negative)[
7     acquire(Lock);
8     send(ROOT,LEAVE#REQ)
9     msg = receive(ROOT);
10     if (msg,type == ALLOW#LEAVE) [
11          Update topology information;
12          Update neighbor information;
13          release(Lock);
14          return;
15      ];
16      release(Lock);
17      return;
18   ]
19  ]
【００８４】
BRANCH及びLEAF  BSRは、T周期の間に４つのメッセージを受信することになっている。BRANCHまたはLEAVE  BSRがJOIN#REQ及びLEAVE#REQメッセージを受信すると、単に母体BSRへと転送される。BSRがFETCH#REQを受信すると、リクエスタに自身の可能性マップ情報を返信する。BSRがPRUNE  REQを受信すると、下部のスレーブBSRとともに現在のクラスタから離れるべく、Prune()動作を実行する。特筆すべきは、任意の分離に際してはBSRはスレーブなしで離れる点である。ただし、刈り取りの際は、BSRはスレーブBSRとともに離れる。
Other#Msg#Recv(v)  [ // Message handler for Others
1  msg = receive();
2  if(acquire(Lock) == true) [
3     switch(msg.type) [
4     case JOIN#REQ
5        send(master,msg); break;
6     case LEAVE#REQ
7        send(master,msg); break;
8     case PRUNE#REQ
9        Prune(v); break
10    case FETCH#REQ
11       send(msg.sender,PMAP); break;
12   ]
13  else
14    send(msg.sender. ERROR);
15  ]
16  release(Lock);
17  ]
【００８５】
トリガ機能は、上述のトラヒックサンプリングによって作成された統計テーブルを使用する。ROOT  BSRは、他のクラスタに統合するか、ツリーを刈り取るかの決定が可能となる。
Root#Trigger(v,PMAP,*u) [
1   var int max,min,tmp;
2   var BS w;
3     neighbor#list   find#Paneighbors(PMAP);
4     if (Cost(v) > PruneThreshold)[
5        return prune;
6     ]
7     for each remaining  w∈neighbor#list [
8       tmp = CostChange(W) ;
9       if (min > tmp) [
10         min = tmp;
11         u     w;
12      ]
13     if (min<JoinThreshold) [
14        u removed from neighbor list;
15        return join;
16     ]
17    ]
18   ]
【００８６】
まず、Root#Triggerは集められた可能性マップを使用することにより、近隣ページング領域を発見しようとする。そして、刈り取りトリガの計算を開始する。ページングコストがある限度を超える場合、無線帯域幅を大きく占めすぎることがないようページング領域の大きさは削減されるべきである。もし、以下に記載のCost()の結果がPruneThreshouldの値よりも大きい場合は、全てのブランチは独立したBSRとなるべく解放される。
【００８７】
次に、Root#Triggerは統合トリガを計算する。ROOT  BSRはスレーブからそのルートへと報告される全てのスレーブの可能性マップを知ることができる。選ばれた可能性マップは、近隣ページング領域の周辺確率分布を提供する。統合トリガは可能性マップを参照することにより、全ての可能な近隣領域を探す。それぞれの候補に関し、以下の記述の通りCost#Change（）関数が計算される。Root#Trigger()は、候補統合への最低コストを探索する。もし、候補が、JoinThreshold変数未満の値であれば、ROOT基地局は統合を決定する。
【００８８】
もし、JoinThreshold変数の値が相当大きい場合は、ROOT  BSRは他により早く統合する手段を取る。
【００８９】
Leave#Trigger()プロシージャは、非R00T  BSRが実行する唯一の動作である。全てのBSRは自身の可能性マップを維持し、そしてもしBSRが現在のクラスタ内の動きが他のページング領域に比べて弱いと判断した場合は、現在のクラスタを離れようとする。
Leave#Trigger(PMAP,v)[
1  refresh PMAP information;
2  for each remaining w∈PMAP[
3    if (current cluster is lower than w)
4       return negative;
5  ]
6  return positive;
7 ]
【００９０】
まず、Leave#Trigger()プロシージャは、可能性マップ情報を更新する。そして、BSRは可能性マップ内の周辺確率分布を現在のクラスタ内の周辺確率分布と比較する。もし、現在のクラスタの値が、他に比べて低い場合は、負の数を戻すことにより離れることを決定する。さもなければ、同じクラスタにとどまる。
【００９１】
特筆すべきは、二つのセルが同じページング領域にある場合、休止モードにあるユーザはこれら二つのセルの間を行き来している間は位置情報の更新をしない。これは、MHが異なるPA-IDを受け止めるまでは活動モードに入らないためである。この結果、ユーザトラヒックが管理されている位置更新メッセージが送信されない。これは、隠れた移動上の問題と呼ばれても良い。内部トラヒックパターンが変化した際、コストがここで消費されることから古いパターンのコストが大きくなることがある。これらの事情から、BSRは最良の新しいページング領域を統合のために選択することを可能とすべく、古いページングエリアから離れることが可能でなければならない。この問題を解決するために、模擬アニーリング方法が提案されている。可能性マップにおける、全ての入力更新において、BSRは以下の方程式を計算する。
【数１】
0003797553.tif 000002
τpvは現在のトラヒック情報であり、ρ∈[0,1]はセルがどれだけ早く独立するかを決定する書き換え可能な定数である。
【００９２】
この方程式の意味は、率直である。ページング領域をセルが統合した結果、境界が消えるとすると、アルゴリズムはその境界におけるトラヒックは減少するものと仮定する。τpv(t+1)がある閾値よりも低い場合、アルゴリズムは統合動作を再び実行すべくセルを独立させる。その結果、ある周期の後にセルは独立する。セルが、その境界において異なるページング領域がないとわかると、アニーリングアルゴリズムは実行されない。
【００９３】
ここに記載されたアルゴリズムは、ページングエリアを統合／分離するための、適切なトリガ次第である。ダイナミックページング領域を構築することの一つの目的は、全体のページングコストを最小限にすることにあることから、コスト機能をトリガとして使用することは自然である。上述の通り、全体のページングコストは、ページングコストと位置更新コストの二つの部分に分けることができる。
【００９４】
ページングコスト
ページングコストは、次の要求が受信される際にページング領域内において発信されるバイト/秒によって定義される。ページングコストは更に、有線チャンネルのためのコストと、無線チャンネルのためのコストの二つに分けることができる。ページングコストを測定するため、以下のパラメータが定義される。
PAi-i番目のページング領域
Ri-ページング領域i（PAi）の次の要求割合。（要求/秒）
Cp-要求に対するセル内のページングコスト（バイト/（要求―セル））
Ncells(i)-ページング領域ｉにおけるセルの数（セル）
更に、αＣｐはルータから他のルータへのページングリクエスト送信のコストであり、βＣｐは無線におけるページングリクエスト送信コストである。αとβは有線及び無線送信への加重である。それぞれの次のＰＡｉ要求に関し、それぞれのセルに対しページングメッセージは一度のみ送信され、そして、無線で送信されるものとする。ページングコストはそして、以下の方程式で表されるものとする。
【数２】
0003797553.tif 000003
【００９５】
位置追跡コスト
ユーザが前のPAjから新しいPAｉへと移った場合、位置情報が更新されなければならない。位置更新コストは、ユーザが異なるページング領域を分けている境界を越えるときに秒ごとに送信されるビット数で定義される。特筆すべきは、ユーザがこれら二つのセルの境界を超えたときに、二つのセルが同じページング領域にあったとすると、ユーザは情報を更新しない点である。この位置更新コストを測定するに当たり、以下のパラメータが定義される。
pji−ユーザのＰＡｊからＰＡｉへの移動の割合（usersec）
pij−ユーザのＰＡｉからＰＡｊへの移動のパーセンテージ（usersec）
dBSRi;TAi-ＢＳＲとＰＡｉ内のＴＡ間の、例えばホップ数による平均距離（hops）
dBSRi;DMAi-ＢＳＲとＰＡｉ内のＤＭＡ間の例えばホップ数による平均距離（hops）
CU−ホップごとの位置更新コスト（bytesuser¢hop ）
N(i)−PAiに近いページング領域を含むセット、ＰＡｉを含まない。
それぞれのページング領域ｉに対し、
【数３】
0003797553.tif 000004
【００９６】
全体のページングコスト
ここに示されるコスト関数に基づき、ある時間帯における全体のコストは以下の通り定義される：
【数４】
0003797553.tif 000005
この方程式に基づき、３つのパラメータ、次の要求割合、ページング領域の大きさそして２つのページング領域間のトラヒック情報は全体のコストに大きく寄与する。次に、これらのパラメータとダイナミックページング領域構築の関係について解析する。
【００９７】
トラヒックパターン
コスト関数に基づき、二つのページング領域間のトラヒックは、ページングコストに大きく寄与することがわかる。直観的に、ふたつの異なるページング領域間のトラヒックが大変詰まっている状態のときは、より少ない位置更新情報が送信されることから全体のページングコストを二つのセルを組み合わせることにより削減できることがわかる。この事実に基づき、統合動作のトリガについて解析する。
【００９８】
隣接する二つのページング領域ｉ、ｊについて考察する。そして、上記コスト関数に基づき、固定周期におけるページング領域iのコストは
【数５】
0003797553.tif 000006
T周期における全体のコストは
cost= costi+costj
PAｉとＰＡｊのふたつを組み合わせた後、同じ周期における全体のコストは
【数６】
0003797553.tif 000007
これらを組み合わせる前に全体のページングコストから減じると
【数７】
0003797553.tif 000008
距離が類似している場合、以下の方程式となる。
【数８】
0003797553.tif 000009
ここで、pi;j=pij+pjiとなり、これは二つの異なるページング領域間の全てのトラヒックをさす。Costchangeが０未満の場合、全外のページングコストは二つのページング領域を組み合わせることにより削減できることは明らかである。組み合わせ処理は、関連する二つのページング領域の全体のページングコストのみに影響する。
【００９９】
次の要求割合
統合動作のトリガについては上述の通りである。幾つかの場合において、ページングコストの上限は固定されている。例えば、作動者によって、無線帯域を占めすぎることのないよう、コスト関数の上限を設定することができる。この場合、固定エネルギー量環境として定義することができる。ページング領域が安定化され、入ってくる割合が大きく増加すると、ページング領域の大きさを削減することにより、コストを最初の規模に削減することができる。現在開示されている実施形態において、刈り取り動作がこのような事情の下でトリガされる。
【０１００】
図２７〜３５は形成動作処理における通信を示すものである。ここに示す実施形態は、６つの処理からなる：移動報告処理、統合処理、分離処理、クラスタ統合処理、クラスタ刈り取り処理及びクラスタ分割処理。これらそれぞれについては、順に説明をする。
【０１０１】
図２７は、移動報告処理における通信を示すものである。図２７に示す通り、ＭＨは現在、通信ネットワーク内でｎＰＣＡによって指定されているネットワークの最終ホップルータに登録されている。ＭＨは移動し、ｎ＋１ＰＣＡで指定されている最終ホップルータにｎＰＣＡから２７０２第３層ハンドオフを行う。いかなる、適切な従来のハンドオフ処理が使用されてもかまわない。そしてＭＨは、ｎ＋１ＰＣＡへの移動報告２７０４又はｎ＋１ＰＣＡへの登録を行う。
【０１０２】
図２８及び２９は、第二の手順である「統合手順」を示すものである。図２８において、ＰＣＡ１はＰＣＡ２と統合する。ＰＣＡ１はまず、ＰＣＡ２への統合のリクエスト２８０２を送信する。ＰＣＡ１の統合が認められた場合、ＰＣＡ２はＰＣＡ１に対し、ＰＣＡ１の統合を受け付ける応答２８０４を送信する。ＰＣＡ１と統合された後、ＰＣＡ２はルートＰＣＡとなる。ＰＣＡ２はデフォルト情報（図１４）からルート情報（図１６）へと変換し、ＰＣＡ１を従属ＰＣＡとしてルート情報に加えるためにルート情報を更新する。ＰＣＡ１はＰＣＡ２と従属関係になる。ＰＣＡ１は、ＰＣＡ２を自身のルートＰＣＡとして加えるために、デフォルト情報からブランチ情報（図１５）へと変換する。
【０１０３】
一つのＰＣＡがＰＣＡのクラスタに統合してもかまわない。図２９に示すとおり、ＰＣＡ１がＰＣＡ４，ＰＣＡ３及びＰＣＡ２を構成しているクラスタに統合しようとしている。このクラスタにおいては、ＰＣＡ４はルートＰＣＡ、ＰＣＡ３は中間ＰＣＡそしてＰＣＡ２はリーフＰＣＡである。ＰＣＡ１はまず、ＰＣＡ２に対し統合リクエスト２９０２を送信する。クラスタマップ（ＣＭＡＰ）をたどり、ＰＣＡ２は同様にルートＰＣＡであるＰＣＡ４へ統合リクエスト２９０６を転送するそのすぐ前のＰＣＡ３へリクエスト２９０４を転送する。ＰＣＡ１の統合が受け付けられる場合、ＰＣＡ４はＰＣＡ１との統合を受け付ける応答２９１０を送信する。この応答はＰＣＡ３を通して２９１２として、そしてＰＣＡ２を通して２９１４としてＰＣＡ１へ転送される。ＰＣＡ４，ＰＣＡ３及びＰＣＡ２は、それらのツリー構造内のＰＣＡ２に接続されている末端ＰＣＡとしてＰＣＡ１をクラスタマップに加える。
【０１０４】
第３の手順は「分離手順」と呼ばれる。図３０〜３２は分離手順の例を示す。図３０において、ＰＣＡ４，ＰＣＡ３，ＰＣＡ２及びＰＣＡ１は、ＰＣＡ４をルートＰＣＡとして、ＰＣＡ１をリーフＰＣＡとして、そしてＰＣＡ３及びＰＣＡ２を中間ＰＣＡとしてクラスタを形成する。ＰＣＡ１は、自身をクラスタから切断しようとしている。ＰＣＡ１からのリクエスト３００２は、中間ＰＣＡ２及び３を通してＰＣＡ４へ転送される。ＰＣＡ４はこれに応じて、応答３００４を同じ経路を通して逆方向からＰＣＡ１へと送信する。ＰＣＡ１がクラスタから切断された後、ＰＣＡ４，ＰＣＡ３及びＰＣＡ２はそれらのクラスタマップのクラスタツリーからＰＣＡ１を抹消する。
【０１０５】
図３１は、ＰＣＡ２がクラスタから自身を切断するもう一つの分離手順の例である。ＰＣＡ２はＰＣＡ３を通してリクエスト３１０２をＰＣＡ４へ送信する。これに応じて、ＰＣＡ４はＰＣＡ３を通して応答３１０４をＰＣＡ２へ送信する。一方で、ＰＣＡ２は同じリクエスト３１０６をＰＣＡ２へ応答３１０８を返信するＰＣＡ１へ送信する。ＰＣＡ２がクラスタから切断されると、ＰＣＡ４と３はそれらのクラスタマップのクラスタツリーからＰＣＡ２を抹消する。ＰＣＡ１はデフォルト情報へと変換し、ＰＣＡ３と統合すべくリクエスト３１１０を送信する。ＰＣＡ３とＰＣＡ４を構成するクラスタに統合するＰＣＡ１の手順は、上記と同じである。
【０１０６】
図３２は、ＰＣＡ３が自身をクラスタから切り離す分離手順の他の例を示したものである。ＰＣＡ３は、ＰＣＡ４からの分離のためのリクエスト３２０２を送信する。ＰＣＡ４はＰＣＡ３へ応答３２０４を返信する。その一方、ＰＣＡ３は、ＰＣＡ３へ応答３２０８を返信するＰＣＡ２へ、同じリクエスト３２０６を送信する。ＰＣＡ３がクラスタから切断されると、ＰＣＡ４はデフォルト情報から再変換する。そして、ＰＣＡ２はＰＣＡ４へ統合すべくリクエスト３２１０を送信する。統合の手順は上述の通りである。
【０１０７】
図３３は、「クラスタ統合手順」と呼ばれる第４の手順を示したものである。図３３に示すとおり、ＰＣＡ１を含むクラスタは、ＰＣＡ４，ＰＣＡ３，ＰＣＡ２を構成するクラスタと統合している。ＰＣＡ４は、統合されたクラスタのルートＰＣＡである。統合しているクラスタは、統合しているクラスタのルートＰＣＡであるＰＣＡ１の他のＰＣＡを含んでいてもかまわない。ＰＣＡ１は、ＰＣＡ３を通してＰＣＡ４へリクエスト３３０４を転送するＰＣＡ２へ、統合のためのリクエスト３３０２を送信する。統合が重なり、又は他への制約を破らない場合、ＰＣＡ４は中間ＰＣＡ３及び２を通じて３３０８が転送されたＰＣＡ１に対して応答３３０６を返送する。統合が完了すると、ＰＣＡ４，ＰＣＡ３及びＰＣＡ２は、ＰＣＡ２へ従属するＰＣＡ１を含む統合クラスタを加えるべくそれらのクラスタマップを更新する。同様に、統合クラスタのＰＣＡもまた、それらのクラスタマップを更新する。
【０１０８】
第５の手順は「クラスタ刈り取り手順」と呼ばれる。図３４は、ＰＣＡ３がルートＰＣＡでＰＣＡ２とＰＣＡ１が中間ＰＣＡである、これら３つのＰＣＡによって構成されるクラスタを示すものである。ＰＣＡ２は、ＰＣＡ３よりＰＣＡ１と自身の切断を希望する。ＰＣＡ２はまた、ＰＣＡ１にその結果できるクラスタのルートＰＣＡとなることを希望する。ＰＣＡ２は、ＰＣＡ３へ刈り取りのリクエスト３４０２と、ＰＣＡ１へリクエスト３４０４ａを送信する。もし刈り取りが受付可能であれば、ＰＣＡ３とＰＣＡ１はＰＣＡ２へ応答３４０６と３４０８を送信する。ＰＣＡ１及びＰＣＡ２が最初にＰＣＡ３から切断される。ＰＣＡ３はデフォルト情報へ再変換する。ＰＣＡ１はそしてルートＰＣＡとなり、ＰＣＡ２はＰＣＡ１の従属となる。ＰＣＡ１は、ＰＣＡ２を従属として含んでいるルート情報へと変換する。
【０１０９】
最後の手順は「クラスタ分割処理」と呼ばれる。図３５は、ＰＣＡ３、ＰＣＡ２、ＰＣＡ１及びＰＣＡ０で構成するクラスタを示すものである。このクラスタでは、ＰＣＡ３がルートＰＣＡである。ＰＣＡ２とＰＣＡ３は同レベルにおいてＰＣＡ３の従属である。ＰＣＡ０はＰＣＡ１から依存されている。ＰＣＡ３はクラスタから自身を切断しており、ＰＣＡ２へ自身切断のリクエスト３５０２を送信する。リクエストは、クラスタのツリー構造を示すＰＣＡ３のクラスタマップ内の情報を含む。ＰＣＡ２はＰＣＡ３へ応答３５０４を返信する。そして、ＰＣＡ１は自身をクラスタから切断する。同時に、ＰＣＡ２はルートＰＣＡとなる。もしＰＣＡ３がＰＣＡ１にルートＰＣＡとなることを望む場合、ＰＣＡ２の代わりにＰＣＡ１へ同じリクエストを送信するようにしても良い。ＰＣＡ２は、ルートＰＣＡとしてＰＣＡ１とＰＣＡ０へクラスタ構造３５０６を通知する。これに対し、ＰＣＡ１とＰＣＡ０はＰＣＡ２へ肯定応答３５０８を送信する。
ここでは、本発明の特定の実施形態を示し説明をしたが、変形をさせてもかまわない。ゆえに、付加されている特許請求の範囲は、本発明の誠の思想及び範囲内でそのような変更及び変形を含むものとする。
【図面の簡単な説明】
【図１】  無線通信ネットワークの様々な実施形態のブロック図である。
【図２】  無線通信ネットワークの様々な実施形態のブロック図である。
【図３】  無線通信ネットワークの様々な実施形態のブロック図である。
【図４】  無線通信ネットワークの様々な実施形態のブロック図である。
【図５】  無線通信ネットワークの様々な実施形態のブロック図である。
【図６】  無線通信ネットワークの様々な実施形態のブロック図である。
【図７】  無線通信システムにおけるページング領域の再構成を示すブロック図である。
【図８】  無線通信システムにおけるページング領域の再構成を示すブロック図である。
【図９】  移動ホスト及び二つの最終ホップルータの模範的実施形態を示すブロック図である。
【図１０】  図９のページング形成エージェントの動作ブロック図である。
【図１１】  図９におけるページング形成エージェントの可能性マップの一つの実施形態の構成を示す。
【図１２】  図９におけるページング形成エージェントの可能性マップの一つの実施形態の構成を示す。
【図１３】  図９のページング形成エージェントの模範的クラスタマップを示す。
【図１４】  図１３の模範的クラスタマップのデフォルト情報のフォーマットの一実施形態を示す。
【図１５】  図１３の模範的クラスタマップのブランチ情報のフォーマットの一実施形態を示す。
【図１６】  図１３の模範的クラスタマップのルート情報のフォーマットの一実施形態を示す。
【図１７】  図１０の形成処理の動作ブロック図である。
【図１８】  図１０のページング転送機能の動作ブロック図である。
【図１９】  図１０の可能性マップ更新処理の動作ブロック図である。
【図２０】  図９のMHのホストレポーターエージェントの動作ブロック図である。
【図２１】  ページング領域形成エージェントによって示されるページング領域の形成を示すものである。
【図２２】  形成動作を示す。
【図２３】  形成動作を示す。
【図２４】  形成動作を示す。
【図２５】  形成動作を示す。
【図２６】  形成動作を示す。
【図２７】  形成動作手順における通信を示す。
【図２８】  形成動作手順における通信を示す。
【図２９】  形成動作手順における通信を示す。
【図３０】  形成動作手順における通信を示す。
【図３１】  形成動作手順における通信を示す。
【図３２】  形成動作手順における通信を示す。
【図３３】  形成動作手順における通信を示す。
【図３４】  形成動作手順における通信を示す。
【図３５】  形成動作手順における通信を示す。
【符号の説明】
１００・・・無線通信ネットワーク
１０２・・・第１最終ホップルータ
１０４・・・第2最終ホップルータ
１０６・・・アクセスポイント
１０８・・・アクセスポイント
１１０・・・アクセスポイント
１１２・・・アクセスポイント
１１４・・・アクセスポイント
１１６・・・アクセスポイント
１１８・・・IPネットワーク
１２０・・・移動ホスト
１２２・・・移動ホスト
１３２・・・最終ホップサブネット
１３４・・・最終ホップサブネット
１３６・・・セル
１３８・・・セル
１４０・・・セル
１４２・・・セル
１４４・・・セル
１４６・・・セル
２０２・・・最終ホップルータ
２０４・・・アクセスポイント
２０６・・・セル
２０８・・・最終ホップサブネット
２１０・・・ページング領域
３００・・・ネットワーク
３０２・・・最終ホップルータ
３０４・・・アクセスポイント
３０６・・・アクセスポイント
３０８・・・セル
３１０・・・セル
３１２・・・最終ホップサブネット
３１４・・・ページング領域
４００・・・ネットワーク
４０２・・・最終ホップルータ
４０４・・・最終ホップルータ
４０６・・・アクセスポイント
４０８・・・アクセスポイント
４１０・・・アクセスポイント
４１２・・・アクセスポイント
４１４・・・最終ホップサブネット
４１６・・・最終ホップサブネット
４１８・・・ページング領域
５００・・・ネットワーク
５０２・・・最終ホップルータ
５０４・・・アクセスポイント
５０６・・・アクセスポイント
５０８・・・アクセスポイント
５１０・・・アクセスポイント
５１２・・・ページング領域
５１４・・・ページング領域
５１６・・・最終ホップサブネット
６００・・・ネットワーク
６０２・・・最終ホップルータ
６０４・・・最終ホップルータ
６１０・・・アクセスポイント
６１２・・・アクセスポイント
６１４・・・アクセスポイント
６１６・・・ページング領域
６２０・・・アクセスネットワーク
６２２・・・アクセスネットワーク
６２４・・・アクセスネットワーク
７００・・・携帯電話無線通信ネットワーク
７０２・・・道路
７０４・・・セル
７０６・・・セル
７０８・・・セル
７１０・・・ページング領域
８００・・・無線通信システム
９０２・・・移動ホスト
９０４・・・第１最終ホップルータ
９０６・・・第２最終ホップルータ
９０８・・・ホストレポーターエージェント
９１０・・・第３層移動エージェント
９１４・・・無線リンク
９２０・・・ページング領域形成エージェント
９２２・・・休止管理エージェント
９２４・・・ローカルページングエージェント
９２６・・・ローカルトラッキングエージェント
９２８・・・第３層移動エージェント
１００２・・・可能性マップ
１００４・・・クラスタマップ
１００６・・・可能性マップ更新処理
１００８・・・形成処理
１０１０・・・ページング転送処理
１２０４・・・テーブル
１３０２・・・デフォルト情報
１３０４・・・ブランチ情報
１３０６・・・ルート情報
１４０２・・・デフォルトページング領域ID
１４０４・・・ページング形成エージェントのネットワークアドレス識別子
１５０２・・・ルートページング領域ID
１５０４・・・先行のページング形成エージェントのネットワークアドレス識別子
１５０６・・・第１及び第２ページング形成エージェントのネットワークアドレス識別子
１６０２・・・ルートページング識別子
１６０４・・・ページング領域形成エージェントを継承しうるもののネットワークアドレス識別子の完全リスト
１６０６・・・リスト１６０４への最初の登録
１６０８・・・継承しうるページング形成エージェントのネットワークアドレス識別子のリスト
１６１０・・・リスト１６０４への二番目の登録
１６１２・・・継承しうるページング形成エージェントのネットワークアドレス識別子のリスト
１６１４・・・リーフPCA  NAI
１７０２・・・候補サーチ機能
１７０４・・・形成決定機能
１７０６・・・形成管理機能
１７０８・・・ページング管理機能
１７１０・・・実行評価機能
１８０２・・・クラスタマップ発見機能
１８０４・・・ページング転送機能
１８０６・・・ページング通知機能
１８０８・・・休止メモリエージェント
１９０２・・・可能性マップ維持機能
１９０４・・・報告受信機能
１９０６・・・移動通知機能
２００２・・・レポーター処理
２００４・・・前位置テーブル
２００６・・・現在位置テーブル
２１０２・・・クラスタ
２１０４・・・ルートＰＣＡ
２１０６・・・中間ＰＣＡ
２１０８・・・リーフＰＣＡ
２２０２・・・クラスタ
２３０２・・・クラスタ
２４０２・・・クラスタ
２４０４・・・クラスタ
２４０６・・・クラスタ
２５０２・・・クラスタ
２５０４・・・クラスタ
２５０６・・・クラスタ
２６０２・・・クラスタ
２７０２・・・nPCAからn+1PCAへの第３層ハンドオフ手順
２７０４・・・n+1PCA（現在）への移動報告
２８０２・・・統合リクエスト
２８０４・・・統合応答
２９０２・・・統合リクエスト
２９０４・・・統合リクエスト
２９０６・・・統合リクエスト
２９１０・・・統合応答
２９１２・・・統合応答
３００２・・・分離リクエスト
３００４・・・分離応答
３１０２・・・分離リクエスト
３１０４・・・分離応答
３１０６・・・分離リクエスト
３１０８・・・分離応答
３１１０・・・統合リクエスト
３２０２・・・分離についての問い合わせ
３２０４・・・分離についての問い合わせに対する応答
３２０６・・・分離リクエスト
３２０８・・・分離応答
３２１０・・・統合リクエスト
３３０２・・・統合リクエスト
３３０４・・・統合リクエスト
３３０６・・・統合応答
３３０８・・・統合応答
３４０２・・・刈り取り問い合わせリクエスト
３４０４・・・刈り取りリクエスト
３４０６・・・刈り取り問い合わせに対する応答
３４０８・・・刈り取り応答
３５０２・・・分割リクエスト
３５０４・・・分割応答
３５０６・・・委託リクエスト
３５０８・・・委託応答
【図１】
0003797553.tif 000010
【図２】
0003797553.tif 000011
【図３】
0003797553.tif 000012
【図４】
0003797553.tif 000013
【図５】
0003797553.tif 000014
【図６】
0003797553.tif 000015
【図７】
0003797553.tif 000016
【図８】
0003797553.tif 000017
【図９】
0003797553.tif 000018
【図１０】
0003797553.tif 000019
【図１１】
0003797553.tif 000020
【図１２】
0003797553.tif 000021
【図１３】
0003797553.tif 000022
【図１４】
0003797553.tif 000023
【図１５】
0003797553.tif 000024
【図１６】
0003797553.tif 000025
【図１７】
0003797553.tif 000026
【図１８】
0003797553.tif 000027
【図１９】
0003797553.tif 000028
【図２０】
0003797553.tif 000029
【図２１】
0003797553.tif 000030
【図２２】
0003797553.tif 000031
【図２３】
0003797553.tif 000032
【図２４】
0003797553.tif 000033
【図２５】
0003797553.tif 000034
【図２６】
0003797553.tif 000035
【図２７】
0003797553.tif 000036
【図２８】
0003797553.tif 000037
【図２９】
0003797553.tif 000038
【図３０】
0003797553.tif 000039
【図３１】
0003797553.tif 000040
【図３２】
0003797553.tif 000041
【図３３】
0003797553.tif 000042
【図３４】
0003797553.tif 000043
【図３５】
0003797553.tif 000044