(57)【特許請求の範囲】
【請求項１】
動的に変化するトポロジーによるノードを有する無線ネットワークを構成する方法において、
無線ネットワークを多数の物理的サブネットに分割する過程を有し、ここに各物理的サブネットは相互に比較的近接して所在する幾つかのネットワークノードを有し、且つ或る所定の物理的サブネットの一つ以上のノードが、隣接する物理的サブネットのノードに到達可能であり、
各物理的サブネットの各ノードを他の物理的サブネットの各々の対応するノードと会員関係を持たせる過程を有し、それによって、幾つかの仮想的サブネットを定義し、
ネットワークの或る所定のノードのアドレスを、該所定のノードと同じ物理的サブネットおよび同じ仮想的サブネットの会員である他のノードの現行アドレスに更新し、
１つの物理的サブネットのソースノードから他の物理的サブネットの宛先ノードまでの通信通路の経路指示が、第１の伝送局面期間中において１つ又は複数の物理的サブネット内における前記通路の或る部分を経路指示し、そして、第２の伝送局面期間中において１つ又は複数の仮想的サブネット内における前記通路の残りの部分を経路指示することにより行われる過程を有する方法。
【請求項２】
請求項１記載の方法において、第１の伝送局面と第２の伝送局面とを相互に交替させる過程を有する方法。
【請求項３】
請求項１記載の方法において、前記第１の伝送局面期間中において実質的にそれらノードの物理的サブネットに対応する地理的エリアをカバーするように前記通信通路の部分を形成するノードの伝送出力を設定する過程を有する方法。
【請求項４】
請求項１記載の方法において、当該ノードが会員関係にある１つの物理的サブネット及び１つの仮想的サブネットを一意的アドレスにおいて識別することによって各ネットワークノードに関する前記のアドレスを定義する過程を有する方法。
【請求項５】
請求項１記載の方法において、物理的サブネットの各々におけるノードの個数に実質的に等しい無線ネットワークの物理的サブネットの個数を設定する過程を有する方法。
【請求項６】
請求項１記載の方法において、ここにソースノード又は宛先ノードのいずれかが会員関係にある物理的サブネットを識別し、そして、前記第１の伝送局面期間中に識別済み物理的サブネット内における通信通路の一部を経路指示することによって前記の経路指示過程が実施される方法。
【請求項７】
請求項１記載の方法において、ここにソースノード又は宛先ノードのいずれかが会員関係にある仮想的サブネットを識別し、そして、前記第２の伝送局面期間中に識別済み仮想的サブネット内を通過する通信通路の一部を経路指示することによって前記の経路指示過程が実施される方法。
【請求項８】
請求項１記載の方法において、ここに多くても１つの物理的サブネット及び１つの仮想的サブネットを横断する最短通路を定義することによって前記の経路指示過程が実施される方法。
【請求項９】
請求項１記載の方法において、ここに物理的−仮想的−物理的または仮想的−物理的−仮想的いずれかの順序において多くても３個の異なるサブネットを横断する長い通路を定義することによって前記の経路指示過程が実施される方法。
【請求項１０】
請求項４記載の方法において、第２の物理的サブネットを結合するために当該移動ノードが第２の物理的サブネットの当該エリア内に所在する場合に第２の物理的サブネットを識別する移動ノードにアドレスを割り当てることによって第１の物理的サブネットからの移動ノードを使用可能化する過程を有する方法。
【請求項１１】
請求項１０記載の方法において、当該移動ノードに第２の物理的サブネットに入るノードにとって利用可能な仮想的サブネットと会員関係を持たせる過程と、当該移動ノードに割り当てられたアドレスにおいて利用可能な仮想的サブネットを識別する過程とを有する方法。
【請求項１２】
請求項４記載の方法において、前記のネットワークノードと共同所在する物理的および仮想的サブネット内の他のノードによって現在使用中のアドレスを用いてネットワークノードを更新する過程を有する方法。
【請求項１３】
請求項１２記載の方法において、ここに前記の更新過程が他のノードの現行アドレスをそれらの論理的な近隣ノードに通知する過程を含む方法。
【請求項１４】
請求項１０記載の方法において、当該移動ノードと会員関係を持たせるために利用可能な仮想的サブネットが無い場合に第２の物理的サブネットの当該エリア内の移動ノードにゲストアドレスを割り当てる過程と、前記第１の伝送局面期間中に限り当該移動ノードが通信通路の一部分であることを可能にする過程とを有する方法。
【請求項１５】
ネットワークの幾つかのノードが動的に変化するトポロジーによる通信ネットワーク用ノード構造において、
当該ネットワークにおける通信通路の部分を設立するための送信機／受信機手段と、当該ノード構造の部分の動作を制御するためのプロセッサ手段とを有し、
ここに前記のプロセッサ手段において、
当該ネットワークを多数の物理的サブネットに分割するための手段を有し、ここに各物理的サブネットが相互に比較的近接して所在する幾つかのネットワークノードを有し、
幾つかの仮想的サブネットを定義するために各物理的サブネットの各ノードに他の物理的サブネットの各々の対応するノードと会員関係を持たせるための手段を有し、
１つの物理的サブネットのソースノードから他の物理的サブネットの宛先ノードまでの通信通路を経路指示するための手段を有し、第１の伝送局面期間中において１つ又は複数の物理的サブネット内における前記通路の幾つかの部分を経路指示し、そして第２の伝送局面期間中において１つ又は複数の仮想的サブネット内における前記通路の残りの部分を経路指示するための手段を有する構造。
【請求項１６】
請求項１５記載のノード構造において、ここに前記プロセッサ手段が第１の伝送局面と第２の伝送局面とを相互に交替させるための手段を有する構造。
【請求項１７】
請求項１５記載のノード構造において、ここに前記の送信機／受信機手段及び前記のプロセッサ手段が当該通信通路の部分を形成するノードの伝送出力を前記第１の伝送局面期間中においてそれらの物理的サブネットに実質的に対応する地理的エリアをカバーする程度に設定するように配列される構造。
【請求項１８】
請求項１５記載のノード構造において、ここに前記プロセッサ手段が１つの物理的サブネット及び当該ノードと会員関係にある１つの仮想的サブネットを前記のアドレスにおいて識別することによって各ネットワークノードに関する１つの一意的アドレスを定義するための手段を有する構造。
【請求項１９】
請求項１５記載のノード構造において、ここに前記の経路指示手段が１つのソースノード又は１つの宛先ノードのいずれかが会員関係にある１つの物理的サブネットを識別し、そして、前記第１の伝送局面期間中において識別済み物理的サブネット内における通信通路の一部を経路指示するための手段を有する構造。
【請求項２０】
請求項１５記載のノード構造において、ここに前記経路指示手段が１つのソースノード又は宛先ノードのいずれかと会員関係にある１つの仮想的サブネットを識別し、そして、前記第２の伝送局面期間中において識別済み仮想的サブネットを通って通信通路の一部を経路指示するための手段を有する構造。
【請求項２１】
請求項１５記載のノード構造において、ここに前記の経路指示手段が多くても１つの物理的サブネット及び１つの仮想的サブネットを横断する最短通路を定義するための手段を有する構造。
【請求項２２】
請求項１５記載のノード構造において、ここに前記の経路指示手段が物理的−仮想的一物理的または仮想的−物理的−仮想的いずれかの順序において多くても３個の異なるサブネットを横断する長通路を定義するための手段を有する構造。
【請求項２３】
請求項１８記載のノード構造において、ここに前記のプロセッサ手段が第２の物理的サブネットを結合するために第１の物理的サブネットからの移動ノードを作動可能化するための手段と、当該移動ノードが第２の物理的サブネットの当該エリア内に位置している場合に第２の物理的サブネットを識別する当該移動ノードにアドレスを割り当てるための手段とを有する構造。
【請求項２４】
請求項２３記載のノード構造において、ここに前記のプロセッサ手段が当該移動ノードに第２の物理的サブネットに入るノードのために利用可能な１つの仮想的サブネットと会員関係を持たせ、そして当該移動ノードに割り当てられたアドレスにおける利用可能な仮想的サブネットを識別するための手段を有する構造。
【請求項２５】
請求項１８記載のノード構造において、前記のネットワークノードと共同所在する物理的及び仮想的サブネットにおける他のノードによって現在使用中のアドレスを用いてネットワークノードを更新するための手段を有する構造。
【請求項２６】
請求項２５記載のノード構造において、ここに前記の更新手段が他のノードの現行アドレスをそれらの論理的な近隣ノードに通知するための手段を有することを特徴とする構造。
【請求項２７】
請求項２３記載のノード構造において、ここに前記プロセッサ手段が当該移動ノードと会員関係を持たせるために利用可能な仮想的サブネットが無い場合にゲストアドレスを第２の物理的サブネットの当該エリア内における移動ノードに割り当てるための手段と、前記第２の伝送局面期間中に限り当該移動ノードを通信通路の部分となるように作動化するための手段とを有する構造。
【発明の詳細な説明】
発明の背景
１．発明の分野
本発明は、全体的に、例えば移動無線ネットワークのような動的に変化するトポロジーによるノードを有する通信ネットワークに関する。詳細には、本発明は、その中においてノードが物理的または局部的エリアサブネットにグループ化され、そして、各物理的サブネットの各ノードは他の物理的サブネットの各々の対応するノードと会員関係にあり、このようにして多数の局部仮想的サブネットを形成するアーキテクチャ及びノード構造に関する。
２．公知技術の説明
移動者ラジオ無線ネットワークは、将来の商業および軍事用途、特に有線基幹ネットワークが存在しない場合において重要な役割を果たすことが期待される。この種のネットワークは、即時下部構造が必要とされ、そして、中央システム管理（例えば、セルシステム基地局）が利用できない場合に適する。
会員間移動無線ネットワークは管理的支援なしに必要に応じてネットワークを作成し、そして、ノードが中間ノードを介してマルチホップモードにおいて相互に交信可能な移動パケット無線ノードの収集体である。従って、全てのネットワークノードは、同様に、潜在的なルーターである。会員間ネットワークの一般的な用途には、遠隔地域における移動計算、戦術通信、法施行オペレーション、及び、災害復旧状況が含まれる。これらのネットワークにおける重要な問題は、当該ネットワークの他のノードに対する会員の動きによって引き起こされる動的なトポロジー変化によく適応する能力である。トポロジー変化に順応するためには、チャネル割当および経路指示の両方における変更が必要とされる。
移動無線ネットワークは１９７０年代以来存在する。最初、これらのネットワークは、例えばファイル転送のような従来のデータサービスの提供を目的とした。
最近では、音声及びビデオ情報並びにデータを含むマルチメディアトラヒックをサポートするために、迅速に配備可能であって、しかも、動的に再構成可能な無線ネットワークへの関心が増大してきた。マルチメディアサービスをサポートするためには、これらのネットワークに関して、幾つかの重要なネットワーク作成上の問題を解決する必要がある。音声及びビデオ情報をリアルタイムで伝搬するためには、厳しい時間遅延拘束条件がネットワークに課せられる。マルチメディアネットワークは、高い性能、及び、高いスループット及び故障許容性と短い遅延における信頼性を所有しなければならない。
動的に変化するトポロジーによる移動無線ネットワークに関する以前の作業は、主として、任意の物理的トポロジーにおけるチャネルアクセス及び経路指示方式に集中した。例えば、Ｅ．Ｍ．Ｇａｆｎｉ等による「頻繁に変化するトポロジーによるネットワークにおいてループフリー経路を生成するための分散型アルゴリズム」ＩＥＥＥ通信に関するトランザクション、ＣＯＭ−２９：１１−１８（１９８１年）を参照のこと。ネットワークの性能及び信頼性を改良するためには、伝送範囲の調整を含むトポロジーを制御する幾つかの方法が提案されている。Ｔ．Ｃ．Ｈｏｕ等による「マルチホップパケット無線ネットワークにおける伝送範囲制御」ＩＥＥＥ通信に関するトランザクション、ＣＯＭ−３４（１）（１９８６年１月）、及び、Ｌ．Ｈｕによる「マルチホップパケット無線ネットワークのためのトポロジー制御」ＩＥＥＥ通信に関するトランザクション、４１（１０）（１９９３年１０月）を参照のこと。更に最近には、マルチメディアトラヒックをサポートするマルチホップ移動無線ネットワークのためのマルチ-クラスタアーキテクチャが提案されている。Ｍ．Ｇｅｒｌａ等による「マルチ-クラスタ、可動性、マルチメディア無線ネットワーク」Ｗｉｒｅｌｅｓｓ  Ｎｅｔｗｏｒｋｓ、１（３）（１９９５年１０月）。
公知である限りにおいては、ネットワークの分割を組込み、更に、ノードの移動性に起因する動的トポロジー変化に適応可能な、移動無線ネットワークに適するアーキテクチャ又はコンフィギュレーションは一切提案されていない。
発明の要約
本発明の目的は、移動無線ネットワークを含む動的に変化するトポロジーによるノードを備えたネットワークへ特に適応可能な通信ネットワークアーキテクチャを提供することにある。
本発明の他の目的は、能率的な論理的トポロジーによる通信ネットワークアーキテクチャ、及び、高いスループット及び故障許容性、及び、短い遅延を特徴とする適切な経路指示手順を供給することにある。
本発明の更なる目的は、移動無線ネットワークに適する通信ネットワークアーキテクチャを提供することにある。この場合のアーキテクチャにおいては、ノードは物理的及び仮想的サブネットにグループ化され、そして、移動ノードはそれらのサブネットへの入会を動的に変更可能である。
本発明の他の目的は、移動無線ネットワークに適した通信ネットワークアーキテクチャを提供することにある。ここに、全ネットワークの性能及び信頼性を高めるために分割が組み込まれる。
本発明の更なる目的は、移動計算及びマルチメディアへの用途によく適する通信ネットワークアーキテクチャを提供することにある。
本発明によれば、動的に変化するトポロジーによるノードを有する無線ネットワークを構成する方法は、当該ネットワークを多数の物理的サブネットに分割することを含む。ここに、各物理的サブネットは、相互に比較的近接して所在し、そして、各物理的サブネットの各ノードに他の物理的サブネットの各々の対応するノードと会員関係を持たせ、それによって、多数の仮想的サブネットを定義する幾つかのネットワークノードを含む。通信通路は、第１の伝送局面期間中に１つ又は複数の物理的サブネット内における通路の或る部分を経路指示し、そして、第２の伝送局面期間中に１つ又は複数の仮想的サブネット内における通路の残りの部分を経路指示することにより、１つの物理的サブネットのソースノードから他の物理的サブネットの宛先ノードまで経路指定される。
本発明の他の態様によれば、当該ネットワークの幾つかのノードが動的に変化するトポロジーに従うような通信ネットワークのためのノード構造はネットワークにおいて通信通路の部分を設立するための送信機／受信機、及び、ノード構造の部分の動作を制御するためのプロセッサ手段を含む。ネットワークを多数の物理的サブネットに分割するための手段が装備され、ここに、各物理的サブネットは、所定の局部エリアにおいて相互に比較的近接して所在し、そして、幾つかの仮想的サブネットを定義するために各物理的サブネットの各ノードを他の物理的サブネットの各々の対応するノードと会員関係を持たせるための幾つかのノードを含み、ここに、各仮想的サブネットの会員関係にあるノードは物理的サブネットの局部的エリアをカバーする局部的ネットワークを形成する。更に、１つの物理的サブネットのソースノードから他の物理的サブネットの宛先ノードまで、通信通路を経路指示するための手段が含まれる。これらの手段には、第１の伝送局面期間中において、１つ又は複数の物理的サブネット内における通路の或部分を経路指示するための手段、及び、第２の伝送局面期間中において、１つ又は複数の仮想的サブネット内における通路の残りの部分を経路指示するための手段が含まれる。
他の目的および更なる目的と共に本発明の更に良好な理解のするために、添付図面と共に以下の説明を参照し、本発明の適用範囲は添付請求の範囲において指摘することとする。
【図面の簡単な説明】
次に図面を示す。
図１は本発明に基づき物理的及び仮想的サブネットにグループ化されたノードを有する分割された無線通信ネットワークを示す。
図２は図１のネットワークのノードの概略構成図である。
図３は本発明に基づくノードロケーションの更新および追跡方式を示す。
図４は図１のネットワークにおける最短通路の経路指示手順を示す。
図５（ａ）及び５（ｂ）は図１のネットワークにおける長通路の経路指示手順を示す。
図６は１６ノード移動無線ネットワークの一例を示す。
図７は本発明に基づく物理的サブネットにおいて連結されたノードを有する図６のネットワークを示す。
図８は本発明に基づく仮想的サブネットにおいて連結されたノードを有する図６のネットワークを示す。
図９は図６のネットワークにおいて長通路の経路指示を用いるディスジョイント通路を示す。
図１０（ａ）は本発明に基づき利用可能な周波数の異なる個数に対する異なるサイズのネットワークの正規化済みスループットを示すグラフである。
図１０（ｂ）はネットワークスループットにサブネットサイズが及ぼす影響を示すグラフである。
図１１（ａ）は異なるサイズサブネットを持つ提供された負荷の関数として平均待ち合わせ遅延を示すグラフである。
図１１（ｂ）は利用可能な周波数の異なる値を持つ提供された負荷の関数として平均待ち合わせ遅延を示すグラフである。
図１２は提供された負荷の異なる値に関するノードの個数の関数として平均待ち合わせ遅延を示すグラフである。
図１３は制御されたトポロジーによる１６ノードネットワークの一例である。
図１４は図１３のネットワークにおける物理的サブネットにおいて作動化されるリンクを示す。
図１５は図１３のネットワークにおける仮想的サブネットにおいて作動化されるリンクを示す。
図１６は１つの大型マルチホップネットワークと、本発明に基づき４個の仮想的サブネットを用いるネットワークとをスループット性能について比較するグラフである。
発明の詳細な説明
本発明は、例えば、媒体への媒質アクセス、経路指示、移動度管理、及び、仮想回路セットアップのような臨界的機能を改良するための手段としてネットワークを分割すると同時に、発信（シグナリング）及び制御のための諸経費を節減することを特徴とする。移動無線ネットワークの分割は、１つの大きな分割されないネットワークによって達成可能であるよりも低いトラヒック混雑度を達成するためにも用いられる。
本アーキテクチャは、物理的トポロジーに重ねられた特定の論理的トポロジーに基づき、後者は各ネットワークノードのトランスミッションカバリッジによって決定される。本アーキテクチャは物理的リンクのプールから作動化されるべきリンク（論理的リンク）を選定する。次に両方共高い性能と高い信頼性とをもたらす効率的な論理的トポロジー及び適切な経路指示手段が決定される。本アーキテクチャは、ノード移動性に起因する動的トポロジー変化に適応するという点で、移動無線ネットワークに特に適切である。
図１は全体数Ｎのノードのアレイによって定義される無線通信ネットワーク１０のダイアグラムである。説明のみを目的とし、本発明の適用範囲を限定することなく、ノードの幾つか又は全部が相互に比較的移動可能であるものと仮定する。
更に、次の条件も仮定されるものとする。
１．ネットワーク１０の各ノードは送信機２２と受信機２４を有する。図２参照。
２．各ノードは、１つのアンテナ２６と、アンテナ２６対ノード送信機２２及び受信機２４の整合および結合のためのスイッチ／インターフェイス２８とを有する。プロセッサ／コントローラ３０は、例えば、ノード送信機２２、受信機２４、スイッチ２８、及び、各ノードの一部であっても差し支えない他の回路を含むノードの部分の動作を制御するために各ノードと関連している。プロセッサ３０は、通常、作業および記憶エリア、及び、プロセッサ３０をノードの動作部分とインターフェイスするために必要であるような入力／出力（Ｉ／Ｏ）回路を有する。
本アーキテクチャにおいて、ネットワークノードは、クラスタまたはサブネットの２つのタイプ、即ち、図１に個々の略図として示される物理的サブネット、及び、各々の物理的サブネットの会員ノードを相互に連結する仮想サブネットにグループ化される。本発明によれば、ノードは、それらの移動性に応じて、それらのサブネットの会員関係を動的に変更することが出来る。更に、各ノードには、他のノードに対する当該ノードの相対位置（即ち、その物理的接続性）及びアドレス可用性に起因する当該ノードの現行サブネットの会員関係によって定義されるアドレスが割当てられる。本構成（コンフィギュレーション）においては、数１０から数１０００個までの移動ノードを有するネットワークについて考察することとする。
ネットワークにおける競争と妨害を解決するチャネルアクセスプロトコルは作動可能であるものと仮定する。例えば、Ｉ．Ｃｈｌａｍｔａｃ等による「移動性マルチホップネットワークのためのリンク割当プロトコル」（ＩＥＥＥ  Ｇｌｏｂｅｃｏｍ’８５、１９８５年１２月、議事録）及び、１９９５年８月２９日付で提出され本発明の譲受人に譲渡済みの米国特許出願第０８／５２１，１０１号を参照されたい。前記’１０１出願の全ての関連部分は、参考資料としてここに組み込まれている。
本開示は、移動無線ノードのネットワークをノードの位相幾何学的構成に応じて物理的および仮想的サブネットに分割するネットワーク制御機能に関する。前記のチャネルアクセスプロトコル及びネットワーク制御コントロール機能は、各ノードプロセッサを適宜プログラムすることによって各ノードと関連付けられたプロセッサ３０によって実行可能である。
本開示の組織構成を次に示す。
Ａ．アドレスの実施方法。
Ｂ．ネットワークの論理的トポロジー、物理的及び仮想的サブネットの形成と移動ノード（移動性管理）に関するロケーション／アドレスの更新。
Ｃ．通路の経路指示手順。
Ｄ．１６ノードネットワークの事例。
Ｅ．性能に関する問題。
Ａ．アドレスの実施方法
ネットワークノードには、それらの現行物理的接続性およびアドレス可用性に基づいてアドレスが割り当てられる。基本的には、各ノードに１つの単一アドレスが割り当てられるが、場合によっては、以下に説明するように１つのノードに複数のアドレスが割り当てられることがある。
先ず、当該ネットワークがｐ個の物理的サブネットに分割され、これらの物理的サブネットは定義済みの局部エリアをカバーするものと仮定する。各物理的サブネットはｑ個までの移動ノードを含む。アドレスのプールは、番号０、１、２、．．．、ｎ−１を有するサイズｍ＝ｍａｘ（ｐ，ｑ）のアルファベットを含む。当該ネットワーク内の各ノードには長さ２の１つのワード（アドレス）が与えられる。ここに、最下位の数字（ＬＳＤ）はｑを底とする数字であり、最上位の数字（ＭＳＤ）はｐを底とする数字である。従って、可能なワード（そしてノード）の全体の数はＮ＝ｐｑで表される。
ネットワークトポロジーにおける各ノードは、それらのアドレスが唯１つの数字だけ異なる他のノードと会員関係にある。即ち、ノードx1．x0は、０≦x'0≦ｑ-１、x'0≠x0の条件の下にノードx1.x'0と会員関係にあり、そして、０≦x'1≦p-１、x'1≠x1の条件の下にノードx'1.x0と会員関係にある。従って、各ノードは、ｐ＋ｑ−２個の他のノードと会員関係にある。即ち、各ノードはｐ＋ｑ−２個の「論理的隣員」を有する。次に、それらのＬＳＤのみが異なるｑ個全てのノードをＭＳＤグループへグループ化し、それらのＭＳＤのみが異なるｐ個全てのノードをＬＳＤグループへグループ化する。合計ｐ＋ｑ個のグループが有り、各ノードは１つのＬＳＤグループ及び１つのＭＳＤグループの１つの会員であることに注意されたい。これらのグループは本ネットワークアーキテクチャの基本構成ブロックである。
Ｂ．ネットワークの論理的トポロジー
ネットワーク内のノードは物理的サブネット（ＭＳＤグループ）および仮想サブネット（ＬＳＤグループ）と会員関係にある。物理的サブネットの会員であるノードは、定義済み局部地理的エリア内において相互に比較的近接した近接範囲内に所在する。仮想サブネットの会員であるノードは地域的ネットワーク（即ち、局部的エリアを越えた）を形成する。
本発明の一実施例において、輪郭が描かれた物理的サブネットに分割され、そして、その中の２つがそれらの会員ノード間の対応するリンクによって示される仮想サブネットを有する移動無線ネットワークを図１に示す。物理的サブネット内の全てのノードのＭＳＤは同じであり、仮想サブネット内の全てのノードはＬＳＤが同じであることに注意されたい。最初に、或る所定の物理的サブネットのノードは、例えば送信出力を調節するか或いは指向性アンテナを使用することによって、隣接する物理的サブネットのノードに到達可能であるものと仮定する。或るノードがその仮想サブネットとの接続が断たれた場合も考えられる。
或るノードは、当該サブネットにおける最初の利用可能なアドレス（最低ＬＳＤに関して）を獲得することによって物理的サブネットの会員になる。例えば、或るノードが物理的サブネット１２と結合し、既に１０個のノードが当該サブネット１２の会員である場合には、０から９までのＬＳＤは既に割当て済みであるので、新規に結合されたノードはアドレス１２．１０を使用する。一旦、或るノードが或る特定の物理的サブネットの会員になる場合には、当該ノードは、自動的に、そのアドレスのＬＳＤによって定義される仮想サブネットの会員になる。前述の例において、新規に結合されたノードは仮想サブネット１０の会員になる。
当該ノードが物理的サブネット１２の近傍、即ち、物理的サブネット１２の他の会員から「聞こえる距離」内に留どまっている限り、当該ノードはその現行アドレスを保持する。
当該ネットワーク内の各ノードは、その物理的および仮想的サブネットにおいて用いられている現行アドレス（即ち、当該ノードの論理的隣接ノードによって用いられるこれらのアドレス）に関して更新される。これは、例えば、通知過程によって、達成される。この場合、各ノードは、専用管理チャネルを用いて、その論理的隣員に、その現行アドレスを通告する。従って、或る特定の物理的サブネットと結合することを希望するノードは、獲得可能なアドレスを見付けるために当該物理的サブネットの会員と接触し、次に、当該ノードは、その新規に獲得したアドレスを、その論理的隣員の全てに通知する。以下に検討するように、或るノードがその仮想サブネット内のその論理的隣員のうちのいずれかの会員に連絡できない場合には、当該ノードは、その物理的サブネット内のその論理的隣員のうちの１つを介して別の仮想サブネットを利用する。
或るノードが、その以前の物理的サブネットの会員との接続を確立し得ない新規なロケーションに移動する場合には、当該ノードは、その以前のアドレスをドロップし、そして、新規サブネットにおける割当にアドレスが利用可能であることを条件として、その会員と当該ノードが交信できる前記の新規物理的サブネットと結合する。当該サブネット内に利用可能なアドレスが無い場合には、当該ノードは、聞こえる距離内に在って、利用可能なアドレスを有する別のサブネットを探索する。近傍物理的サブネット内に利用可能なアドレスが無い場合（例えば、このサブネット内には、既に、それぞれ１つの単一アドレスを使用するｑ個のノードが或るか、或いは、１つのノード当たり複数のアドレスを持つｑ個未満のノードによって全てのアドレスが用いられ、そして、これらのノードが、当該移動ノード用アドレスを解放（リリース）し得ない場合）には、当該移動ノードは、近傍物理的サブネットからの「ゲスト」アドレスｘ．ｙを受け取る。ここに、ｘは物理的サブセット識別番号であり、ｙ≧ｑである。物理的サブセットｘ内のアドレスが利用可能になると即座に、ゲストノードは解放された当該アドレスを獲得し、そして、そのゲストアドレスをドロップして、物理的サブネットｘの正会員になる。ノードは、ゲスト状態であっても、以下に説明する方法において、他のノードと交信可能である。
仮想サブネットの間には直接的な論理的接続は無い。ただし、仮想サブネットは同一領域に「重ねて配置」されるので、相互に干渉することがあり得る。この潜在的干渉はチャネルアクセス方式を用いることによって除去される。例えば、各仮想サブネットは異なる周波数スペクトルにおいて作動可能である。周波数帯の個数が仮想サブネットの個数より少ない場合には、或る形式のタイムシェアリングを使用することが出来る。周波数帯が１つの単一周波数チャネルを含む場合には、当該サブネットは純粋な時間割多元アクセス（ＴＤＭＡ）モードにおいて使用される。そうでない場合には、ＴＤＭＡ／ＦＤＭＡはスループットを増大するために使用することが出来る。物理的サブネットの各々は限定されたエリアをカバーするために重複の程度が限定されている隣接する物理的サブネットに存在する問題の重大性は軽いことに注意されたい。従って、空間的再使用を利用することが可能であり、そして、隣接するか或いは潜在的に重複している物理的サブネットに限り、異なる作動周波数を使用する必要がある。
ロケーション（アドレス）の更新および追跡
その入会サブネットを一旦変更した移動ノードは、その新規物理的および仮想的サブネット内の全てのノード（即ち、その現行論理的隣員）に新規に獲得したアドレスを通告する。この種の通知過程は、例えば、その論理的隣員とのリンクを確立するか、或いは、当該ノードの物理的及び仮想的サブネット内において同報通信することにより実施可能である。一般に、ソースノードは、所要の宛先ノードの現行アドレスを知らないはずである。ソースノードは、その現行物理的（或いは仮想的）サブネットにおいて問い合わせすることによって宛先アドレスを決定することが出来る。理由は、前記の物理的（或いは仮想的）サブネットにおいては、ノードの１つが宛先ノードの仮想的（或いは物理的）サブネットと会員関係にあることに困る。
例えば、ソースノードＳ及び宛先ノードＤのアドレスをそれぞれS1．S0及びD1．D0とし、物理的サブネットS1のカーディナリティ（会員数）を｜S1｜で表すものとする。ノードＤのアドレスを見付けるための異なる２つの場合について考察することとする。第１の場合、｜S1｜≧D0であるとすれば、ノードＳは、その物理的サブネットS1において、ノードＤについて問い合わせ、そして、ノードS1．D0からノードＤのアドレスを受け取る。後者のノードには、既に、ノードＤにより仮想的サブネットD0を介してＤの現行アドレスについて通知済みである。第２の場合、｜S1｜<D0であるとすれば、ノードＳは、その仮想的サブネットS0において、ノードＤについて問い合わせ、そして、ノードＤの物理的サブネットと会員関係にあるノードD1．S0からのノードＤのアドレスを受け取る。ノードＳは、前述の場合のどちらが有効であるかを演繹的に知らないことに注意されたい。その代りに、ノードＤのアドレスについて問い合わせる代りに、ノードＳは、ノードＳの物理的および仮想的サブネットにおいて、ノードＤに関するノードＳのパケットを同報通信することができる。次に、ノードＤの論理的隣員である少なくとも１つのノードは、パケットをそれらの宛先に送る。
図３は、本発明に基づくロケーションの更新および追跡方式の一例を示す。新規ロケーションに移動した後で、移動ホスト（ＭＨ）ノードは、ロケーション更新（ｌｏｃ＿ｕｐｄａｔｅ）を送ることによって、その論理的隣員に通知する。ＭＨと交信することを要望する固定ホスト（ＦＨ）ノードは、ロケーション問合せ（ｌｏｃ＿ｉｎｑｕｉｒｙ）をその論理的隣員に送ることによって、ＭＨに関して問合わせる。ＦＨの論理的隣員の少なくとも１つは、同様に、ＭＨの論理的隣員であり、その結果、それらの相互論理的隣員の１つは、ｌｏｃ＿ｔｒａｃｋを送ることによって、ＭＨのアドレスをＦＨに供給する。ＦＨは、ＭＨのアドレスを下方追跡した後で、それら相互の論理的隣員を介してＭＨにそのデータを送る。
図３は、１６ノードネットワーク（ｐ＝ｑ＝４）における特定の一例を用いて、前述の過程を介して伝達するノードを示す。このロケーション更新および追跡方式は、Ｎよりはるかに少ないｐ＋ｑ−２ノードのみに関係し、それによって、発信および制御のオーバーヘッド（諸経費）を節減することに注意されたい。例えば、ｐ＝１６及びｑ＝２５である４００ノードネットワークにおいて、ロケーション更新/追跡過程は、当該ネットワークにおけるノード個数の１０％未満のノードに関係する。従って、マルチホップサブネットの場合においては、（ＴＤＭＡ／ＦＤＭＡのような無競争アクセスであるものと仮定する）対応する物理的および仮想的サブネットにおいて、ネットワーク全体の重複配置なしに、ｌｏｃ＿ｕｐｄａｔｅ及びｌｏｃ＿ｉｎｑｕｉｒｙメッセージを同時通報するためにフラッド方式が使用できる。
Ｃ．通路の経路指示手順
幾つかの経路指示方式が可能である。自己経路指示である最も短い通路の経路指示手順について説明する。先ず、１ホップ物理的／仮想的サブネットの場合を仮定する事とする。この手順において、ルートは、例えばＬＳＤからＭＳＤまで、固定した順序において一時に１つの数字を横切る。ソースノードアドレスが１２．１５であり、宛先ノードアドレスアドレスは９．１７であるものと仮定する。
本手順は通路１２．１５→１２．１７→９．１７を使用する。一般に、ソースノードアドレスu1．u0から宛先ノードアドレスv1．v0までのルートは通路u1．u0→u1．v0→v1．v0を横切る。図４を参照されたい。通路の長さは、ソース及び宛先ノードのアドレスにおける異なる数字の個数、即ち、最大２ホップに等しい。本手順において、任意の２つのノードの間には一意的な１つの通路がある。
一般に、ネットワークは、ソースノードから宛先ノードまでの通路を経路指定する場合に２つ以上のホップが必要であることを意味する多元ホップサブネットによって構成される。従って、通路の経路指示は２つの局面において実施される。第１局面（局面Ｉ）において、経路指示は物理的サブネットにおいてのみ実施される（局部エリアトラヒックの交換）。この場合、パケットは、ソースノードから、宛先ノードとして同じＬＳＤを持つ１つのノードまで、必要に応じて、中間ノードを介して、当該ソースノードの物理的サブネット内において、（例えば、最短通路を用いる）経路指定される。第２局面（局面ＩＩ）において、パケットは仮想的サブネット内において経路指定される。この場合、第１局面における最後のノードにおいて受信されたパケットは、宛先ノードのＬＳＤによって定義済みの仮想的サブネット内において、必要に応じて中間ノードを介して、このノードから宛先ノードまで経路指定される。局面Ｉ期間中、送信出力は、対応する物理的サブネットの局部エリアのみをカバーするように限定されることが好ましい。これは、空間的分離による周波数の再使用を可能にする。局面ＩＩにおいて、仮想的サブネットが作動化された場合、遠隔物理的サブネットに到達するように送信カバリッジが調節される（例えば、指向性アンテナを使うことによる）。
図１において、ソースノード１２．１５から宛先ノード９．１７までの経路は通路１２．１５→１２．１０→１２．１７→１１．１７→８．１７→９．１７．を横切る。物理的サブネット１２においては２ホップが発生し、仮想的サブネット１７においては３つのホップが発生する。
或るノードがその仮想的サブネット内におけるその論理的隣員のいずれにも到達出来ない場合（即ち、仮想的サブネットが接続されない場合）、当該ノードは、その物理的サブネット内におけるその論理的隣員の１つを介して異なる仮想サブネットを使用しなければならない。例えば、ノードＡ．ＢがノードＣ．Ｄと交信することを望むものと仮定する。最短通路の経路指示を用いて、通路は、通常、物理的サブネットＡにおいてノードＡ．Ｄまで横断し、次に、仮想的サブネットＤにおいてノードＣ．Ｄまで横断する。ただし、ノードＡ．Ｄが仮想サブネットＤへ接続されない場合には、ノードＡ．Ｄは物理的サブネットＡ内において別のノード（例えば、ノードＡ．Ｅ）へ接続し、その後で、仮想的サブネットＥにおけるノードＥへ、そして、最終的に、次に示すように、物理的サブネットＣ内における宛先ノードＣ．Ｄに接続する。
Ａ．Ｂ−−→...−−→Ａ．Ｄ−−→...−−→Ａ．Ｅ−−→...−−→Ｃ．Ｅ−−→...−−→Ｃ．Ｄ
その代りに、このような接続を断たれたサブネットの場合を克服するために、以下に説明する故障許容経路指示方式を使用することが出来る。
通常、ノードは１つの単一アドレスを持つが、状況に応じて、１つのノードが複数のアドレスを持つことも可能である。例えば、人口密度の低い物理的サブネットからのソースノードS1．S0が、会員密度が高く、｜S1｜<D0であるような物理的サブネットからの宛先ノードD1．D0と交信しようとする場合を仮定すると、当該ソースノードS1．S0は、別のアドレスS1．D0を受信し、そして、宛先ノードD1．D0と交信するために、仮想的サブネットD0に参加する。従って、ソースノードは、物理的サブネットS1、及び、仮想的サブネットS0及びD0と会員関係にある。
ゲストノード（ＬＳＤがｑより大きい）は一切の仮想的サブネットと会員関係にない（この種のサブネットはｑ個に限られる）。従って、局面Ｉの期間中、ゲストノードは、局所的に交信し、その物理的サブネット内における他のノードのようにサブネット間トラヒックを交換する。ただし、局面ＩＩ期間中においては、ゲストノードは活動停止中である。ソースノードが、その物理的サブネットの外側のゲストノードにパケットを送ろうとする場合には、当該ソースノードは、その仮想的サブネットを介してゲストノードの物理的サブネット内の対応するノードにそのパケットを送り、そして、対応するノードは、その次の局面（局面Ｉ）期間中に、即ち、サブネット間トラヒックを介して当該パケットをゲストノードに送る。
「長通路経路指示」と称する別の自己経路指示方式は、「Ｅ．性能」の題名の下に次に検討するように、高度の故障許容に帰着する。この場合、u1．u0とv1．v0との間の最長通路は３つのホップで構成される（１ホップ物理的／仮想的サブネットと仮定する）。図５（ａ）は、物理的−仮想的−物理的サブネット経路u1．u0→u1．u'0→v1．u'0→v1．v0を示す。ここに、０≦u'0≦q-１及び、u'0≠u0である。図５（ｂ）は、仮想的−物理的−仮想的サブネット経路u1．u0→u'1．u0→u'1．v0→v1．v0を示す。ここに、０≦u'1≦p-１、及び、u'1≠u1。
各ルートが物理的サブネットと仮想的サブネットを交互に横切ることに注意されたい。各ソース-宛先ノード対（ペア）の間にはｐ＋ｑ−２個の継ぎ目の切れた通路、即ち、リンク又はノードを共有しない通路が有る（例えばｐ＝ｑ＝√Ｎの場合において、継ぎ目の切れた通路の個数はＯ√Ｎある）。これらの通路経路の各々のは、ソースノードのｐ＋ｑ−２個の論理的隣員の１つに対応する。ソースノードによって論理的隣員が選定されると、１つの通路が一意的に指定されることに注意されたい。ソースノードから宛先ノードまでパケットを送るために、ソースノードは、ｐ＋ｑ−２個の継ぎ目の切れた通路のうちの１つを（例えば、無作為に）選定する。故障通路を選定した場合には、ソースノードは、残りの継ぎ目の切れた通路の中の１つを（例えば、無作為に）選定することが出来る。
Ｄ．１６ノードネットワークの事例。
図６に示す１６ノード移動無線ネットワークについて考察することとする。ｐ＝ｑ＝４、即ち、４個の物理的サブネット、及び、それぞれ４個のノードを有する４個の仮想的サブネットが有り、各ノードは１つの物理的サブネット、及び、１つの仮想的サブネットの会員であるものと仮定する。
図７は、ノードアドレスを伴ったそれぞれ４個の会員ノードで構成される４個の物理的サブネットを形成し、局面Ｉの期間中に作動化されるリンクを備えた図６の１６ノードネットワークを示す。図８は、局面ＩＩ期間中に作動化されるリンクを備え、４個の仮想的サブネットを形成する前記と同じ１６ノードネットワークを示す。視覚的に分かり易くするために、それぞれの仮想的サブネットを構成するノードは同じ特徴の形状で表される。各仮想的サブネットは４個のノードを含み、各ノードは図７の４個の物理的サブネットのうちの１つに含まれるノードである。最短通路経路指示に関する次の説明的な例について考察することとする。
１．ソースノードが０．１、宛先ノードが３．０、経路指示通路が０．１→０．０→１．０→３．０である場合には、局面Ｉ期間中に物理的サブネット０における１つのホップを渡り、局面ＩＩ期間中に仮想的サブネット０における２つのホップを渡り、合計３つのホップを渡る。
２．ソースノードが１．１、宛先ノードが２．３、そして、ノード１．３が物理的サブネット１を離れたと仮定した場合。アドレス１．３はドロップされたので、ソースノード１．１は、追加アドレス−１．３−を獲得し、通過通路は、局面ＩＩ期間中における仮想的サブネット３内の１つのホップ、即ち、１．１、１．３→２．３である。
３．アドレスが０．０のノードＡが物理的サブネット３の近傍に移動し、従って、ノードＡは、物理的サブネット３に属するノードと物理的接続性を有するものと仮定する。このサブネット内には利用可能なアドレスはもう無いので、ノードＡは「ゲスト」アドレス―３．４を得る。ソースノードが２．０であり、宛先ノードがノードＡ（３．４）である場合に、通過通路は、２．０→３．０→３．４であり、局面ＩＩ期間中における仮想的サブネット０内の１ホップ、及び、その後の局面Ｉ期間中における物理的サブネット３内の別の１ホップを伴う。
最後に、図６の１６ノードネットワークにおいて長通路経路指示を用いる場合には、任意のソース-宛先ペアの間において６個の継ぎ目切れ通路（即ち、リンク又はノードを共有しない通路）が成立する。図９を参照されたい。
Ｅ．性能に関する問題。
次に示すＥ．１において、ネットワークの性能について、ホップの平均回数、遅延、スループット、及び、故障許容度の観点から、１ホップ物理的／仮想的サブネットと仮定して、２ホップネットワークに関して評価することとする。全てのサブネットは、潜在的に干渉可能なサブネットに割り当てられた異なる周波数帯を用いて純粋ＴＤＭＡモードにおいて作動するものと仮定する。
マルチホップネットワーク（各サブネットにおいて複数回のホップが行われる）の一般的な場合においては、以下のＥ．２において考察することとする。この場合、サブネットが、各サブネット内の多重周波数チャネルを用いて、ＴＤＭＡ／ＦＤＭＡモードにおいて作動する。ネットワークのスループットが評価され、そして、大型マルチホップネットワークの場合と比較される。
以下に示すＥ．１及びＥ．２の場合には、あらゆる通路が１つの物理的サブネットと１つの仮想的サブネットで構成される最大２個までのサブネットを横断する既に述べた最短通路経路指示が用いられるものと仮定される。
Ｅ．１  ２ホップネットワーク
ホップの平均数
ネットワークにおける各ノードは、ｐ＋ｑ−２個の１ホップ用宛先（当該ノードの属する物理的および仮想的サブネット内のそれぞれ（ｑ−１）個及び（ｐ−１）個）、及び、（ｐ−１）（ｑ−１）個の２ホップ用宛先（（ｑ−１）個の仮想的サブネットの各々と会員関係にある（ｐ−１）個のノード）を持つ。従って、ネットワークにおけるホップの平均個数は次式で与えられ、この値は、大型ネットワークに関しては概略２に等しい。
0003810440.tif 000002
遅延とスループット
ネットワークの遅延及びスループットを求めるには、最初に、サブネット負荷に関する式を導出する。「サブネット負荷」とは、ソース-宛先ペア間の全ての可能なＮ（Ｎ−１）通路によって１つのサブネットが横切られる回数を意味するものと定義する。トラヒックは均質であるものと仮定し、この場合、ネットワークにおける各ノードは、他の（Ｎ−１）個のノードのうちの任意のノードに毎秒λ個のパケットを送るものと仮定する。各物理的サブネットを通過する全トラヒックは、当該サブネット内のｑ個のノードによって当該サブネット内の（ｑ−１）個の会員のなかの任意のノードへ送られると毎秒pλ個のパケットによって構成される。従って、物理的サブネット負荷は次式で与えられる。
ηph=N(q-1)                    (2)
同様に、各仮想サブネットを通過する全トラヒックは、ｐ個のノードの各々によって当該仮想的サブネット内の（ｐ−１）個の会員のなかの任意のノードへ送られる毎秒qλ個のパケットによって構成される。従って、仮想的サブネット負荷は次式で与えられる。
ηv=N(p-1)                    (3)
従って、最大サブネット負荷は次式で与えられる。
ηmax=N(max(p,q)-1)                  (4)
平均サブネット負荷は次式で与えられる。
ηav=（pηph+qηv）/(p+q)
=N(2N-(p+q))/(p+q)            (5)
全てのサブネットのサイズ寸が同じであるp=q=√N、対称的な場合においては、次式が成立する。
ηmax=ηav=N(√N-1)                (6)
ここに全てのサブネットは同じ負荷であり、平衡負荷に帰着する。
簡易化のために、単一サブネットの動作を説明するために、Ｍ／Ｍ／１待合せモデルが適用されるものと仮定する。従って、サブネットkを横切るパケットの平均遅延は次式で表される。δk=1/(μCk-ηkλ）ここに、1/uはビットで表した平均パケット長さであり、Ckはビット／秒で表したサブネット容量であり、ηkはサブネット負荷である。サブネットの動作に関して更に正確なモデルが使用される場合には、δkに関して異なる式が得られるに過ぎない。Ｌｉｔｔｌｅの式を使用すれば、ネットワーク全体に亙る平均待ち遅延は次式で与えられる。
0003810440.tif 000003
ここに、S及び（は、それぞれ、当該ネットワークにおけるサブネットの全個数および提供されたトラヒックである。この場合、S=p+q、及び、Λ=N(N-1)λであることに注意されたい。ノード当たり１つの単一送信機／受信機（或いは、トランシーバ）を有するものと仮定されているので、αを、局面Ｉの期間中において、当該トランシーバがその物理的サブネット専用に使用するタイムフレームの一部分であるものとする。更に、Ｍ個の周波数帯が有り、ビット／秒で表した送信機のバースト-レートがRであるものと仮定する。物理的サブネットk容量は次式で与えられる。
0003810440.tif 000004
この場合、τr=max(r/M, 1)であり、rは、全ての物理的サブネットを同時作動させるために（相手サブネットの周波数の空間的再使用を使用することにより）必要な周波数帯の個数である。ここに、ｒ≦pであり、サブネットの物理的レイアウトに依存することに注意されたい。同様に仮想サブネットkの容量は次式で与えられる。
0003810440.tif 000005
ここに、τq=max(q/M, 1)である。仮想的サブネットを同時に作動させるにはｑ個の周波数帯が必要であることに注意されたい。理由は、これらのサブネットが重複していることに因る。上記の方程式（７）を使用すると、ネットワーク全体を横断する平均待ち遅延は次式で与えられる。
0003810440.tif 000006
即ち、負荷サブネット容量を超過することが出来ない。λの最大値は、次式を満足させるαoptに関して達成される。
0003810440.tif 000007
αに関して方程式（１１）を解くと次式が得られる。
0003810440.tif 000008
方程式（１１）の一方の辺にαoptの値を代置することにより、次式が得られる。
0003810440.tif 000009
方程式（９）に方程式（１２）及び（１３）を使用し、配列を変えることによって次式が得られる。
0003810440.tif 000010
正規化済み（バーストレートに関して）ユーザスループットは次式で与えられる。
0003810440.tif 000011
更に、正規化済みネットワークスループットは次式で与えられる。
Γ=Ｎγ                                      (16)
方程式（１３）及び（１５）を方程式（１６）へ代置することにより、次式が得られる。
0003810440.tif 000012
方程式（１５）及び（１６）を用いると、方程式（１４）が得られる。
0003810440.tif 000013
ここに、ρ＝λ／λmaxは、（ユーザ／ネットワークにより）提供された正規化済み負荷である。方程式（１４）の左辺は、パケット伝送時間単位で表したネットワーク横断平均パケット待ち遅延であることに注意されたい。
更に、１≦Ｍ≦min(r, q)場合、スループットは、周波数帯の個数Ｍに正比例する。即ち、より多くの周波数帯を加えると、スループットが直線的に増加する。min(r, q)を越えてＭが増加すると、Ｍに関する最大値がM=max(r, q)に到達するまで、スループットは依然としてほぼ正比例的に増大する。
0003810440.tif 000014
ここに、p=q＝√Ｎに関するグローバル最大値はΓmax＝（√Ｎ＋１）／２である。これは、サイズＮのネットワーク及びサイズ√Ｎのサブネットに関して、最大スループットを達成するためには、√Ｎの周波数が必要であることを意味する。
図１０（ａ）は、p=q=√Ｎ及びr=８、即ち、８周波数は、全ての物理的サブネットの同時作動のために必要かつ十分であると仮定した場合における、異なる数の利用可能な周波数に関する異なるサイズのネットワークの正規化済みスループットを示す。
図１０（ｂ）は、サブネットのサイズがネットワークスループットに及ぼす影響を示す。方程式（１９）に基づき、p=q=√Ｎに関する２√Ｎの最小値までｐ＋ｑが減少する場合、スループットは更に高くなることが推測される。従って、同じサイズに関して最良の性能が達成される状態において、物理的サブネットのサイズが仮想的サブネットのサイズに更に近づくと、更に良好なスループット性能が達成される。これは、p=q=√Ｎに関して、平均サブネット負荷が最大サブネット負荷に等しいことに起因する（方程式（６）参照）。これは、他のあらゆる経路指示方式に関して、ηmax≧Ｎ（√Ｎ-1）であることを意味する。従って、ゼロから最大スループットが達成されるまで、現行経路指示手順は、全ての負荷に関して、最大スループットと最小遅延とを達成する。
図１１（ａ）は、異なるサイズのサブネットを有する１０２４ノードネットワークに関する平均終端間パケット待ち遅延対ユーザ／ネットワーク提供負荷を示す。M=ｒ=８であるものと仮定する。図１１（ｂ）において、利用可能な周波数の異なる値に関して、１０２４ノードネットワークに対して提供された負荷に関する平均遅延の依存度を示す。全てのサブネットが同じサイズ（ｐ＝ｑ＝３２）及びｒ＝８を持つものと過程する。図１２は、ｐ＝ｑ＝√Ｎ、Ｍ＝８、及びｒ＝８を仮定した場合における、提供された負荷の異なる値に関して、平均遅延対ネットワークサイズ（ノードの個数）を示す。
故障許容性
本アーキテクチャの故障許容性を評価するために、２つの測定基準（メトリック）、即ち、「ノード接続性」及び「リンク接続性」を用いる。ノード接続性κは、接続を断たれたネットワークを生成する故障ノードの最小個数として定義されるものとする。論理的トポロジーにおける各ノードはｐ＋ｑ−２個の他のノードへ直接接続されるので、ネットワークのノード接続性はκ=p+q-２である。例えば、それぞれ３２個のノードを有する３２個のサブネットから成る１０２４ノードネットワークを考察する場合、ネットワークが接続を断たれた状態になる以前に、任意の６１個のノードが故障していることがあり得る。
ネットワークのリンク接続性σは、任意のソース-宛先ペアの間のノード-ディスジョイント通路（即ち、同一ノードを介して一切のリンク又は通路を共有しない通路）の再小数として定義されるものとする。本トポロジーのリンク接続性は、２つ以下のホップで構成される通路長さに関してσ=２である。通路長さが３ホップまででことが許容される場合には（長通路経路指示を用いる、図５（ａ）及び５（ｂ）参照）、リンク接続性はその最大値σ=p+q-２に達することを示すことが出来る。前述の例において、少なくとも６２個のノードディスジョイント通路、即ち、３ホップ未満の通路長の任意のソース-宛先ペアの間の代替通路がある。ネットワークのノード接続性もリンク接続性も高いので、ネットワークの信頼性が非常に高い。従って、本ネットワークアーキテクチャは無線非同期転送モード（ＡＴＭ）通信用として非常に適切である。この場合、所定のソース-宛先ペアの間で確立される仮想通路は、移動性、干渉等に起因するノード又はリンク故障の場合に使用できる多くの代替ディスジョイント経路を有する。
Ｅ．２  マルチホップネットワーク
一般に、サブネットは満杯接続されず、従って、各物理的または仮想的サブネット内において多元ホップが必要とされることがある。各サブネット内において、各タイムフレーム期間中に各リンクが少なくとも１度は作動化されるリンク起動ＴＤＭＡ／ＦＤＭＡ（サブネット当たり多重周波数チャネルが可能である）方式が用いられるものと過程する。以下の解析は、マルチホップサブネット内のあらゆる経路指示手順に関して真である。
スループット
以下の解析において更に用いられる表記法を次に示す。
T＝１つの大型マルチホップネットワークにおいて用いられるタイムスロットの個数。
T1＝局面Ｉにおいて用いられるタイムスロットの個数。
T2＝局面ＩＩにおいて用いられるタイムスロットの個数。
L＝１つの大型マルチホップネットワークにおいて作動化されるリンクの全個数。
L1＝局面Ｉ期間中に物理的サブネットにおいて作動化されるリンクの全個数。
L2＝局面ＩＩ期間中に仮想的サブネットにおいて作動化されるリンクの全個数。
ηi＝１つの大型マルチホップネットワークにリンク＠ｉの負荷、即ち、当該ネットワークにおける全ての可能なＮ（Ｎ−１）個の通路によってリンク＠ｉが横切られる回数。
ηj1＝その物理的サブネットにおけるリンクｊの負荷、即ち、当該物理的サブネットにおける可能なｑ（ｑ−１）個の通路の全てによってリンクｊが横切られる回数。
ηk2＝その仮想的サブネットにおけるリンクｋの負荷、即ち、当該仮想的サブネットにおける可能なｐ（ｐ−１）個の通路の全てによってリンクｋが横切られる回数。
η＝１つの大型多重ホップネットワークにおける最大リンク負荷（すなわち、maxi（ηi））。
η1＝局面Ｉの期間中における最大リンク負荷（即ち、maxj（ηj1））。
η2＝局面ＩＩの期間中における最大リンク負荷（即ち、maxk（ηk2））。
再び、作動化された各リンクの動作を記述するために均質トラヒック及びＭ／Ｍ／１待ち行列モデルを仮定するものとする。Ｌｉｔｔｌｅの式を使用し、ネットワークにおける全ての作動化されるリンク全体について要約することにより、ネットワークを横断するための平均待ち行列遅延は次式によって与えられる。
0003810440.tif 000015
リンクの容量は、使用される周波数チャネル数に依存する（対応する位相における）タイムスロットの個数に逆比例することに注意されたい。局面Ｉ期間中における２つのノードの間の最大トラヒックはλ1=αμR/(T1η1p)である。同様に、局面ＩＩ期間中における２つのノード間の最大トラヒックはλ2=（1-α）μR／(T2η2q)である。αの最適値を見付けるために、λ1=λ2を解くことにより、次式が得られる。
0003810440.tif 000016
従って、ネットワークにおける任意の２つのノード間の最大トラヒックは次式で表される。
0003810440.tif 000017
正規化済み（バーストレートに対して）ネットワークスループットは次式で与えられる。
0003810440.tif 000018
η1及びη2は、論理的トポロジー、及び、サブネット内において使用される経路指示手順に依存することに注意されたい。
方程式（１７）は、T1=q(q-1)τr、T2=p(p-1)τq、及び、η1=η2=１を代置することにより、特殊な場合（２ホップネットワーク）として方程式（２３）から導出できる。ｑ（ｑ−１）及びｐ（ｐ−１）は、それぞれ、純粋なＴＤＭＡモードにおいて作動する、満杯接続された１ホップの物理的および仮想的サブネットにおけるリンクの個数である。
ここで、本アーキテクチャの性能（例えば、スループット）及び１つの大型マルチホップ無線ネットワークの性能を比較することにする。最初に、１つの大型マルチホップネットワークに関するスループットを算定する。１つの大型マルチホップネットワークを横断する待ち行列遅延は次式で与えられる。
0003810440.tif 000019
従って、１つの大きいマルチホップネットワークのスループットは次式で与えられる。
0003810440.tif 000020
本アーキテクチャ（方程式（２３））及び１つの大型マルチホップネットワーク（方程式（２５））に関するスループット値は物理的及び論理的トポロジー、経路指示手順、及び、周波数数に著しく依存する。特にランダムトポロジー（特別な散発ネットワークの特性）の大型ネットワークにおいては、１つの大型ネットワークにおける最大リンクトラヒック負荷は、サブネットにおける最大リンクトラヒック負荷よりも著しく大きいこと、即ち、η>>pη1、qη2であることが判明した。従って、ネットワークの分割は、密集を減少させ、更に高いスループットと更に短縮された遅延によって、ネットワークの性能を改良する。
伝送半径が大きいと、より多くのタイムスロットが必要とされるので、リンク容量が低下すると言う欠陥を伴う。ただし、リンクの負荷負担が非常に減少するので、全体的な効果としては、スループットの増大に帰着する。更に、１つの大型マルチホップネットワークは、空間的再使用するために、あまり多くの周波数（利用可能であっても）を利用することが出来ないが、本アーキテクチャは、重複配置された仮想的サブネットを分離するために多重周波数を使用することが可能である。これも、スループットの増大に帰着する。
次に示す１６ノードネットワークの事例は、提案されるアーキテクチャの強度を例証する。図１３は、等辺三角形によって形成され、充分に調整された最大次数６のトポロジーによるネットワークを示す。本アーキテクチャによれば、ネットワークは、４個の物理的および４個の仮想的サブネット（ｐ＝ｑ＝４）に分割可能である。図１４及び１５は、それぞれ、物理的および仮想的サブネットの伝送局面期間中に作動化されるリンクを示す。
最短通路経路指示、及び、例えば付録Ａに記述されているようなＴＤＭＡ/ＦＤＭＡリンク起動割当てを使用することにより、利用可能な周波数の個数に応じてスループット性能を算定するために必要な値は、表１に示すように決定される。
0003810440.tif 000021
１つの大型マルチホップネットワーク、及び、４個の仮想的サブネットを用いるネットワークに関するスループット性能を図１６に示す。この特定の事例の場合、所定個数の周波数に関して、本アーキテクチャは、常に、１つの大型マルチホップネットワークよりも更に良好なスループット性能を持つことが理解できる。１つの大型ネットワークの最大スループットを達成するためには３個よりも多い周波数は用いられない。即ち、より多くの周波数を追加してもスループットは増大しないことに注意されたい。これは、空間的再使用を用いると、ノードの伝送範囲が制限されることに因る。
ただし、本ネットワークアーキテクチャを用いると、より多くの（８個まで）周波数を追加することにより、スループットを更に増大することが可能である。１つの大型マルチホップネットワークにおける平均および最大リンク負荷率はそれぞれ８．３３および１６であるが、本発明に従って４個の仮想的サブネットを用いるネットワークの場合には、前記の値に対応する値が８．０であること、即ち、ネットワークが平衡負荷を持つことに注意されたい。１つの大型ネットワークにおけるホップの平均および最大数はそれぞれ２．２９及び６．０であるが、４個の仮想サブネットを用いるネットワークの場合には、前記の値に対応する値は２．１３及び４．０である。
要約すれば、本アーキテクチャは、物理的および仮想的サブネットの論理的トポロジー、及び、これに対応するアドレッシング、移動性管理および経路指示方式によって構成される。本アーキテクチャは、特に移動無線ネットワークに適用可能であり、そして、ネットワークノードの相対的な移動に起因する動的トポロジー変化に適応できる。本アーキテクチャは、移動無線ネットワークを論理的に独立したサブネットワークに分割する。ネットワークノードは物理的および仮想的サブネットの会員であり、ノードの移動性に因り、ノードとこれらサブネットとの会員関係は変化する。各ノードには、現行サブネット入会状態に基づくアドレスが割り当てられる。特にランダムトポロジーによる大型ネットワークにおいては、ネットワークを分割することにより、１つの大型マルチホップネットワークの場合よりも実質的に一層平衡のとれた負荷状態、即ち、ネットワークの性能を大幅に改良できる属性が得られることが判明した。本アーキテクチャは、高度に故障許容的であり、そして、比較的簡単なロケーションの更新および追跡方式を扱うことができる。本アーキテクチャは負荷平衡化機能を備えているので、通常、比較的高いスループットと短い遅延を備えたネットワークを達成する。
付録Ａ  分散型リンク起動方式
２つのノード（例えば、ノードｉとノードｊ）間における指示されたリンク割当てを実施ための分散型オンラインＴＤＭＡ/ＦＤＭＡリンク起動方式を次に示す。ノードｉ及びｊは、それらの近隣ノード（即ち、「聞こえる」距離内に在るノード）における既存の割当に関して既知であるものと仮定する。割当て過程の出力はリンクｉ→ｊ、即ち、１つのタイムスロットと１つの周波数（ｔ、ｆ）との順序づけられた１対、或いは、ただ１つの周波数が利用可能である（純粋ＴＤＭＡ）場合には１つのタイムスロットｔの割当てである。
次に示す表記法が用いられる。
T−利用可能なタイムスロットの集合。
F−利用可能な周波数の集合。
Tr−ノードｒにより使用中のタイムスロットの集合。
Finr,h−タイムスロットｔhにおいてノードｒの近隣ノードへ入来するリンクによって使用中の周波数の集合。
Foutr,h−タイムスロットｔhにおいてノードｒの近隣ノードから出て行くリンクによって使用中の周波数の集合。
集合Ｔ及びＦは、最初は、任意に順序付けられる。
ノード割当て方式
１．ｔk∈T-（Ti∪Tj）を選定する。ここに、ｋは最小順序数であり、利用可能なタイムスロットが無い場合には手順４に行く。
２．ｆ1∈F-（Fini,k∪Foutj,k）を選定する。ここに、ｌは最小順序数であり、利用可能なタイムスロットが無く、T←T-｛ｔk｝である場合には手順１に行く。
３．停止する。対（ｔk，ｆ1）は、ｉ→ｊリンク割当である。
４．停止する。リンクｉ→ｊは割当て不可能である。
タイムスロット割当は論理的リンクのみに関係し、周波数割当は論理的および物理的両方のリンクについて考慮することに注意されたい。
以上の記述は本発明の好ましい実施例を表すが、当該技術分野における熟達者ににとって、本発明の真の精神及び以下に示す請求の範囲によって定義される適用範囲から逸脱することなく種々の改造および修正を行うことが可能であることは明白なはずである。
【図１】
0003810440.tif 000022
【図２】
0003810440.tif 000023
【図３】
0003810440.tif 000024
【図４】
0003810440.tif 000025
【図５（ａ）】
0003810440.tif 000026
【図６】
0003810440.tif 000027
【図６（ｂ）】
0003810440.tif 000028
【図７】
0003810440.tif 000029
【図８】
0003810440.tif 000030
【図９】
0003810440.tif 000031
【図１０（ａ）】
0003810440.tif 000032
【図１０（ｂ）】
0003810440.tif 000033
【図１１（ａ）】
0003810440.tif 000034
【図１１（ｂ）】
0003810440.tif 000035
【図１２】
0003810440.tif 000036
【図１３】
0003810440.tif 000037
【図１４】
0003810440.tif 000038
【図１５】
0003810440.tif 000039
【図１６】
0003810440.tif 000040