(57)【特許請求の範囲】
【請求項１】
一つの制御ノードおよび複数の個別のノードから成る無線網を構成（コンフィギュア）するための方法であって、この方法が：
前記網を論理的に複数のバンドＢｉに編成するステップを含み、ここで、これらバンドＢｉのおのおのが複数の個別のノードを含み、前記制御ノードからｉのホップ数だけ離れた所に位置し、ここで、ｉは、０〜Ｎの範囲に値で、Ｎは、１以上であり；この方法がさらに
前記複数のノードのおのおのに論理アドレスを割当て、こうして割当てられた論理アドレスをこれら個別の各ノード内に格納するステップを含み；
前記個別の各ノードに対して割当てられた論理アドレスが、個別の各ノードが位置するハンドＢｉを示す第一のアドレス部分、および各ノードを同一のバンド内に位置する他の全ての個別のノードとの関連で識別する第二のアドレス部分を含むことを特徴とする方法。
【請求項２】
さらに、前記網をノード接続性情報を得るために初期化するステップを含み、
前記網を論理的に編成するステップが、前記制御ノードによって、この網を初期化するステップの際に得られたノード接続性情報に基づいて遂行されることを特徴とする請求の範囲１に記載の方法。
【請求項３】
前記複数の個別の各ノードが、自身の論理アドレスを自身が受信する各パケットに含まれるルーティング論理アドレスと比較し、この比較の結果に基づいて、前記パケットを破棄、再送、あるいは処理するステップを遂行するようにプログラムされることを特徴とする請求の範囲１あるいは２に記載の方法。
【請求項４】
前記受信された各パケットに含まれる前記ルーティング論理アドレスが、前記パケットを発信ノードから前記ルーティング論理アドレスによって指定される通信路に沿って宛先ノードにルートするために要求される全てのルーティング情報を含むことを特徴とする請求の範囲３に記載の方法。
【請求項５】
前記制御ノードが、パケットのルーティングを、以下のステップ、すなわち：
前記ルーティング論理アドレスを自身が送信する各パケットに挿入するステップ；
任意のパケットの伝送が失敗したことを検出するステップ；
前記パケットの伝送が失敗したことの検出に応答して前記ルーティング論理アドレスによって指定される通信路内の故障ノードを検出するステップ；および
伝送に失敗したパケットの前記ルーティング論理アドレスを、前記検出された故障ノードを含まない新たな通信路を指定する新たなルーティング論理アドレスに変更するステップ；
を遂行することによって制御するようにプログラムされることを特徴とする請求の範囲４に記載の方法。
【請求項６】
無線網であって、これが：
制御ノード；および
複数のバンドＢｉに論理的に編成された複数の個別のノードを含み、ここで、これらバンドＢｉのおのおのが複数の個別のノードを含み、前記制御ノードからｉのホップ数だけ離れた所に位置し、ここで、ｉは、０〜Ｎの範囲に値で、Ｎは、１以上であり；
前記個別の各ノードが論理アドレスを持ち、この論理アドレスが個別の各ノードが位置するハンドＢｉを示す第一のアドレス部分、および各ノードを同一のバンド内に位置する他の全ての個別のノードとの関連で識別する第二のアドレス部分を含むことを特徴とする網。
【請求項７】
前記制御ノードが、前記パケットのルーティングを：
前記ルーティング論理アドレスを自身が送信する各パケットに挿入し；
任意のパケットの伝送が失敗したことを検出し；
前記パケットの伝送が失敗したことの検出に応答して前記ルーティング論理アドレスによって指定される通信路内の故障ノードを検出し；
伝送に失敗したパケットの前記ルーティング論理アドレスを、前記検出された故障ノードを含まない新たな通信路を指定する新たなルーティング論理アドレスに変更する；
ことによって制御するようにプログラムされることを特徴とする請求の範囲６に記載の網。
【請求項８】
一つの制御ノードおよび複数の他の網ノードを含む無線網内で用いるための網ノードであって、これら網ノードの全てが論理的に複数のバンドＢｉに編成され、ここで、これらバンドＢｉのおのおのが複数の個別のノードを含み、前記制御ノードからｉのホップ数だけ離れた所に位置し、ここで、ｉは、０〜Ｎの範囲に値で、Ｎは、１以上であり；この網ノードがさらに
前記網ノードの論理アドレスを格納するためのメモリを含み；
前記論理アドレスが各網ノードが位置するハンドＢｉを示す第一のアドレス部分、および各網ノードを同一のバンド内に位置する他の全ての網ノードとの関連で識別する第二のアドレス部分を含むことを特徴とする網ノード。
【請求項９】
前記受信されたパケットに含まれる前記ルーティング論理アドレスが、前記パケットを発信ノードから前記ルーティング論理アドレスによって指定される通信路に沿って宛先ノードにルートするために要求される全てのルーティング情報を含むことを特徴とする請求の範囲８に記載の網ノード。
【請求項１０】
前記制御ノードが、前記パケットのルーティングを：
前記ルーティング論理アドレスを自身が送信する各パケットに挿入し；
任意のパケットの伝送が失敗したことを検出し；
前記パケットの伝送が失敗したことの検出に応答して前記ルーティング論理アドレスによって指定される通信路内の故障ノードを検出し；
伝送に失敗したパケットの前記ルーティング論理アドレスを、前記検出された故障ノードを含まない新たな通信路を指定する新たなルーティング論理アドレスに変更する；
ことによって制御するようにプログラムされることを特徴とする請求の範囲９に記載の網ノード。
【発明の詳細な説明】
技術分野
本発明は、一般的には、無線マルチホップ網（しばしば、“無線ローカルエリア網（Ｗ−ＬＡＮ）”あるいは“無線パケットホッピング網とも呼ばれる）、より詳細には、無線マルチホップ網を構成（コンフィギュア）し、その内部でデータパケットをルーティングするための方法およびこの方法を実現するための無線網に関する。より具体的には、本発明は、1995年11月16日でA.Dasguptaの名前で出願された公開された欧州特許第EP782,802号／米国特許出願第08/558,447号において開示されるＰａＳＴ（“PArtitioned Spanning Tree：区分編成全域木）ルーティングアルゴリズムおよび無線網の大きな改良から成る。このためこの特許についても参照されたい。
背景技術
互いに、あるいは網制御ノード（“主”あるいは“中央”ノードとも呼ばれる）と、無線（ラジオあるいはＲＦ）リンクを介して通信する複数の網あるいは個別のノードから成る網は、通常無線（ラジオあるいはＲＦ）網と呼ばれる。無線マルチホップ網においては、各ノードは、デジタル信号処理デバイス（例えば、マイクロプロセッサ）およびＲＦトランシーバを含むノードコントローラを有する。データは、個別のノードと制御ノードとの間で“ホッピング（hopping）”と呼ばれる技法によって通信（伝送）される。このホッピングにおいては、データの個別の単位が、制御ノードから宛先ノードに、あるいは発信（ソース／送信）ノードから制御ノードに、宛先あるいは発信ノードが制御ノードとの直接の通信リンクを持たない全てのケースにおいて、一つあるいは複数の中間ノードによって、網ルーティングプロトコルに従って、ホップ（中継あるいは再送／再ブロードカースト）することによって伝送される。パケットを網内の一つあるいは複数の他のノードに向けてホップあるいは中継する各ノードは、通常“中継器ノード”あるいは単に“中継器”と呼ばれる。宛先ノードは、通常は制御ノードからデータパケットを受信したことを、受取通知（アクノレッジメント）データパケットを類似の方法で一つあるいは複数の中継器を介して送り返すことによって確認する。
パケット、フレーム、セルなどを含むデータさまざまな論理単位を用いることが可能であるが、ただし、本発明の現時点において好ましいとされる実施例は、説明を簡単にするために、便宜上、ここでは典型的には、約５〜１０００バイトのレンジのサイズを持つ“パケット”が、データの単位として採用されるものとする。これとの関連で、ここで用いられる“パケット”という用語は、フレームあるいはセルを含む全てのデータの論理単位を包含することを意図する。一般的には、パケットホッピングデータ通信は、制御ノードの制御下で遂行され、制御ノードは、典型的にはコンピュータであり、このコンピュータ上にデータ通信制御ソフトウエアが常駐する。このパケットホッピングデータ伝送法は、ＲＦトランシーバのコストを削減でき、ＦＣＣ  Ｐａｒｔ１５要件を満たす。
このような無線パケットホッピング網は、ビルの一つあるいは複数の機能あるいはシステム、例えば、ビルの照明、ＨＶＡＣ、および／あるいは保安システムを制御するために特に適するが、これは、無線網が網情報を運ぶために現存の構造に新たな回線を追加することを必要としない低コストの室内通信インフラストラクチャ（基盤）を提供できるためである。さらに、無線網は、ビル内に設置された追加のシステム、例えば、ページングおよびパーソナル通信システム（ＰＣＳ）などをサポートすることも可能である。
このようなビル制御網の中央ノードは、典型的にはビルのコンピュータである。個々のノードと、ビルのコンピュータは、異なるソフトウエアプログラムを実行するが、これらは、互いに補間的で、一体となってシステムの制御ソフトウエアを構成する。個々のノードは、典型的には、ビル全体に渡って分散され、制御されるビルシステムの所定のパラメータの状態／値を監視し、ビルのコンピュータによって発行されるコマンドに応答して、これら所定のパラメータを、要求されるように調節するための制御信号を生成する。ビルのコンピュータにとっては、所定のパラメータの状態／値を正しく監視し、所定のパラメータの状態／値を、システム制御ソフトウエアに従って要求されるように調節するためのコマンドを発行するためには、網内の各ノードにデータを送信あるいはこれから受信できることが重要である。
一例としてのビル制御網として、網内のビルの各部屋および／あるいはエリアの照明レベル、占拠状態、時間の関数としてのエネルギー消費、および／あるいは他の照明パラメータを監視する自動あるいは知能照明制御システムがある。具体的には、ビルの各部屋および／あるいはエリアに設置された照明モジュールは、ノードコントローラ（“壁ユニット”とも呼ばれる）によって監視され、ノードコントローラは、これにリンクされたＲＦトランシーバ、デジタル信号処理デバイス（例えば、マイクロコントローラあるいはマイクロプロセッサ）、および照明機器に対して照度を調節する信号を送る制御回路を含む。つまり、各照明モジュールと、これと関連するノードコントローラとが一体となって、網ノードが構成され、この網ノードがビルのコンピュータの制御／管理下に置かれる。
このような知能照明制御システムにおいては、各照明モジュールは、それと関連する壁ユニットを介して（例えば、ビルの占拠者によって）個別にプログラミングされる。こうして照明モジュールの調光安定器の設定が直接に制御され、照明モジュールのランプの照度が直接に制御される。これとの関連で、各ノードは、一つあるいは複数のセンサ（例えば、占拠状態、昼光（周囲の照度）、および調光／照度レベル等のセンサ）を含み、このセンサによって、ノードコントローラのデジタル信号処理デバイス（例えば、マイクロプロセッサ）に、センサからのフィードバックデータが提供される。ノードコントローラは、センサからのフィードバックデータを分析（処理）し、監視するランプの照度を調節するための制御信号を生成し、こうして局所的にプログラムされた照明条件が達成される。
このセンサからのフィードバックデータは、網内の各ノードによって、ビルのコンピュータにも、ビルのコンピュータによって要請された場合、あるいは局所的に照明状態が変化したときに伝送される。ビルのコンピュータは、センサからのフィードバックデータを、搭載された照明システム制御ソフトウエアに従って分析（処理）し、必要に応じて、制御データ（コマンド）を、ビルの監視される部屋／エリアの照度を照明システム制御ソフトウエアに従って調節するために個々のノードに向けて送信する。こうして、例えば、個々の照明モジュールによって規定されるプログラムされた照明レベルが無効にされ、照明システム全体としてのエネルギー効率が最適化される。こうして、これら分散して配置された照明モジュールは、個別に制御可能であり、独立して動作できることに加えて、機能的にビル全体をカバーする単一の網に統合され、ビルのコンピュータの制御下に置かれる。
このような網におけるデータ通信は、一般的には、ビルのコンピュータから個々のノードに向けてあるいはこの逆方向に、共通の通信チャネル（つまり共有チャネル）を用いて行なわれる。複数のパケットが共通の網チャネルを通じて同時に伝送される可能性を最小にするために、チャネルアクセスプロトコルが用いられる。最も一般的なチャネルアクセスプロトコルは、搬送波感知マルチパスアクセス（ＣＳＭＡ）プロトコルと呼ばれる。このプロトコルによると、各ノードは、パケットを伝送する前に、ランダムな遅延期間だけ待ち、チャネルを感知（検出）し、チャネルが空いている（“クリア”）であるか、塞がっている（“ビジー”）であるかを決定する。チャネルが空いていることが決定された場合は、これはパケットを送信し、逆に、チャネルが塞がっていることが決定された場合は、これは、もう一度ランダムな遅延期間だけ待ち、再度、チャネルの状態を検出し、その後、再度パケットの送信を試みる。
無線マルチホップ網において典型的に用いられる網ルーティングアルゴリズムあるいはプロトコルは、大きく、２つのタイプ、すなわちランダムルーティングプロトコルと、決定論的ルーティングプロトコルに大別できる。
ランダムルーティングプロトコルに応じて、パケットは、網内の複数のノードを通って、送信ノードから宛先ノードに、ランダムなルートに沿って、ランダムにポップされる。このプロトコルにおいては、データ伝送を実行するために特性のセットの中継器は用いられない。より具体的には、送信ノードは、パケットを、その送信レンジ内の全ノードに向けて送信し、このパケットを受信した各ノードは、パケットを自身の送信レンジ内の全てのノードに再送あるいは中継する等する。この動作が、パケットが宛先ノードに到達するまで繰り返される。典型的には、各パケットは、通常“ホップカウンタ”と呼ばれるバイトを含む。このホップカウンタは、各中継器において減分され、最終的に０となる。このホップカウンタが０になった時点で、このパケットの中継は終了する。このホップカウンタは、送信（伝送）ノードによって、パケットが網を不当に長期間に渡って占拠することなく、宛先ノードに到達する可能性が最大となるように設定される。
このランダムルーティングプロトコルの重大な短所は、網内の全てではないとしても殆どのノードが伝送された個々の全てのパケットを扱い、このために網内のデータトラヒック密度が大きく増加し、このために任意の与えられた時間において“網上を存在できる”異なるパケットの数（つまり、網のデータトラヒック処理能力）が大きく制限されることである。このために、網の通信効率が制限されると共に、解決不能な衝突の発生の回数が増加する。データトラヒックのこの解決不能な衝突は、パケットが宛先に到達することなく失われる原因となる。これとの関連で、ビル制御網においては、ビルのコンピュータに送り返されるアクノレッジメント（受信通知）パケットは、典型的には、ビルのコンピュータにリンクされた非常に少数のノードに集束され、このためにこれらアクノレッジメントパケットが解決不能に衝突する可能性およびこの発生回数が増大する。結果として、アクノレッジメントパケットの閉塞が頻繁に発生し、このためにビルのコンピュータは、元のパケットが宛先ノードによって実際に受信されたか否か決定するために、頻繁にパケットを再送することを要求される。勿論、これは、データのスループットおよび網の効率を著しく制限する。
他方、従来の決定論的ルーティングプロトコルにおいては、ビルのコンピュータは、網初期化ルーチンを実行した際に収集したノード接続性情報に基づいて、ルーティングテーブルを作成する。このルーティングテーブルは、送信ノードから宛先ノードに向けて、中継器の特定のセットあるいは“連鎖”を介して（つまりルーティングテーブル内に定義される所定のルートあるいは単一の経路に沿って）、データのパケットをルートするために用いられる。これら従来の決定論的プロトコルは、網内でデータをルートするために、ルーティングテーブルを用い、この事実のために、このプロトコルは、しばしば、“テーブル式”ルーティングプロトコルと呼ばれる。伝送される各パケットは、（ビルのコンピュータと直接のリンクが存在しないと想定した場合）所定の通信路（つまりルーティングテーブル内に指定される中継器ノードの特定の“連鎖”）に沿う一つあるいは複数のノードによってのみ再送され、このために多くの異なるパケットを同時に伝送する（つまり“網上”に存在する）ことが可能であり、このために、ランダムルーティングプロトコルを用いた場合と比較して、網のデータトラヒックを処理する能力（つまりデータスループット）は高くなる。
ただし、これら従来のテーブル式のルーティングアルゴリズムにおいては、重大な短所として、各ノードは、ルーティングテーブルを格納するための十分なメモリ、並びにルーティングテーブル内に含まれるデータに基づいてルーティングの決定を行なうために要求される論理動作を扱うための十分な処理パワーを持つことを要求される。これとの関連で、多くのアプリケーションは、安価な“資源節約型のノード”、つまり最低限のメモリおよび処理パワーを持つノードを要求する。
この目的のために、資源節約型のノードを持つ無線マルチホップ網に特に適したテーブル型ではない決定論的ルーティングアルゴリズムが本発明の譲受人に譲渡された1995年11月16日付けでA.Dasguptaの名前で出願された本発明と譲受人を同一とする係属中の米国特許出願第08/558,447号において開示されている。“ＰａＳＴ”アルゴリズムと呼ばれるこのルーティングアルゴリズムは、低コストのマイクロコントローラと小量のメモリ（例えば、１０バイト以下）を採用し、また、制御される機器、例えば、照明スイッチングあるいは壁ユニットに組み込むのに十分にコンパクトな網ノードを利用することを可能にする。
より詳細には、このアルゴリズムによると、ビルのコンピュータによって論理区分編成全域木（logical Partitioned Spanning Tree, ＰａＳＴ）が網初期化手順の際に集められたノード接続性情報に基づいて構成され、網内の個別の網ノードの各々に一意の論理ＰａＳＴアドレスが割当てられる。ビルのコンピュータによって各ノードに割当てられるこの論理ＰａＳＴアドレスは、パケットをビルのコンピュータとノードの間で前後に通信するために用いられるべき中継器の単一のセットあるいは連鎖、つまりパケットがビルのコンピュータと個々のノードの間で通信されるとき伝搬されるべき単一の所定の通信路（ルート）を定義する。このＰａＳＴルーティングプロトコルによると、各パケットは、論理アドレスデータ欄を含み、この欄内に、伝送されるパケットの宛先ノードの論理ＰａＳＴアドレスが挿入される。
各パケットの論理アドレスデータ欄に挿入される論理ＰａＳＴアドレスは、パケットをルーティングするために必要な全ての情報を含むために、各ノードは、データを処理、再送、あるいは破棄するか否かを決定するために、単に、自身に割当てられたＰａＳＴアドレス（典型的には１０バイト以下）を格納するために十分なメモリ、および自身に割当てられたＰａＳＴアドレスとノードが受信する各パケットの論理アドレスデータ欄内に含まれるＰａＳＴアドレスをビット毎に比較するための十分な処理パワーを持つことのみを要求される。
ただし、1995年11月16日付けで、A.Dasguptaの名前で出願された本発明と譲受人を同一とする係属中の米国特許出願第08/558,447号に開示されるＰａＳＴルーティングプロトコルは、無線網の固有のＲＦ制約のためにまだ重大な欠点を持つ。すなわち、このプロトコルでは、ある与えられたパケットがその宛先に到達できる可能性が、これが単一の所定の通信路（つまり中継器の単一の特定の連鎖）に沿ってルートされるために比較的低くなる。
より具体的には、室内無線網のノード・ツウ・ノード通信の信頼性が、フェージングやマルチ経路（ＲＦ信号が、壁、床、天井、家具等の表面からの自身の反射によって妨害を受ける）などの現象による悪影響を受け、このために、既に設定されているノード・ツウ・ノードリンクが中断したり、損失したりすることがある。さらに、これら既に設定されているノード・ツウ・ノードリンクが、ビルの内部環境、例えば、ビル占拠者のさまざまな活動によって動的に変化することによって中断したり、損失したりする場合もある。例えば、ドアの開閉、家具の移動、廊下を通っての人の移動などの単純な動作によってノード・ツウ・ノード通信路が妨害されることがある。このように、網内の任意の与えられたノード・ツウ・ノードリンクの状態は、時間によって、多くの殆ど予測不能、かつ管理不能な変量（原因）に依存して、常に、物が詰まった状態、物が散在する状態、物が全く存在しない状態など様々な状態に変動する。
このような固有のリンク信頼性の問題のために、しばしば、単一の通信路に沿って伝送されるデータパケットがこれらの宛先に到着する前に失われ、このために、これら失われたパケットを再送する（送り直す）ことが必要となり、網の通信効率およびデータスループットが害なわれることとなる。このような伝送の失敗は、コマンドデータパケットをビルのコンピュータから宛先ノードに向けて外側に（“下り方向に”）伝送する際、あるいはアクノレッジメント（受取通知）データパケットを宛先ノードからビルのコンピュータに向けて内側に（“上り方向に”）伝送する際に、中継器連鎖内のたった一つのリンクが故障しただけでも発生する。
問題を持つリンクのリンク品質を満足に解決することがでいない場合は、パケットをリルートする（パケットをルートを変えて伝送する）こと、および／あるいは網を再構成する（網を構成し直す）ことが必要となり、このために、さらに網の性能が劣化し、同時に、網のコストと複雑さが増加する。これとの関連で、ＰａＳＴルーティングアルゴリズムは、網の再構成が困難で、時間がかかるという短所を持つ。
より詳細には、ＰａＳＴルーティングアルゴリズムは、故障した通信リンクを検出するための内蔵された能力を持つが、このような故障が検出された場合、故障リンクのために阻止された伝送を完結するために（つまりデータパケットを識別された故障リンクを迂回してリルートするために）使用できる唯一の手段は、論理区分編成全域木内の故障ノードより遠方に位置する各ノードの論理ＰａＳＴアドレスを再プログラムする（プログラムし直す）ことであり、このためには、この接続性を故障リンクが除去されるように変更することが要求される。換言すれば、自身の論理ＰａＳＴアドレスとして故障ノードのアドレスに対応するアドレスセグメントを持つ全てのノードを、新たな論理ＰａＳＴアドレスを持つように再プログラムする（プログラムし直す）ことが必要となる。これは、ビルのコンピュータと与えられた個々の網ノード間の単一の所定の通信路（“ルート”）が、与えられた個々の網ノードのＰａＳＴアドレスによって完全に単一に決定されることに起因する。
より詳細には、ある与えられた個々の網ノードのＰａＳＴアドレスが、それぞれ、単一の所定の通信路を形成する中継器の連鎖内の自身の“親”ノードの最上位ビットを含むために、論理区分編成全域木内の故障ノードより遠方に位置する全てのノードの論理ＰａＳＴアドレスを再プログラムする（プログラムし直す）ことが必要となり、これにはこの接続性を故障リンクを除去するように変更することが要求され、多くの場合、識別された故障リンクを除去するために要求される接続性の変更には、網全体を再初期化する（初期化し直す）ことが必要となる。要するに、故障リンクを回避するために、網を簡単に動的に再構成したり、データパケットをリルートすることが不可能であり、このために、ＰａＳＴルーティングアルゴリズムの効率と、このルーティングアルゴリズムを利用する網のデータスループットが劣化する。
上述のリンクの信頼性の問題を解決するために様々な周知の方法が存在する。リンクの信頼性を向上させるための一つの方法においてはより高いパワーのＲＦトランシーバが用いられ、リンクの信頼性を向上させるためのもう一つの方法においてはノイズを制限する広帯域トランシーバが用いられる。ただし、これらアプローチは、両方とも、多くの用途に対してはコストが高すぎる。勿論、有線網が理想的な解決策ではあるが、現存の構造物内に有線網を施設するコストは、多くの用途に対しては高すぎる。
特に効果的で新規の一部ランダムで一部決定論的なルーティングアルゴリズムが、本発明の譲受人に譲渡された1996年2月29日で本発明の発明者（George A. Melnik）の名前で出願された本発明と譲受人を同一とする係属中の米国特許出願第08/608,910号において開示されている。詳細についてはこの文献を参照されたいが、簡単に述べると、この新規のルーティングアルゴリズムは、データスループットおよび網の通信効率を大幅に向上させ、同時に、網のハードウエア要件（例えば、各網ノードに対して要求されるボーレートおよびパケットバッファ（メモリ）のサイズ）を大幅に低減することを可能にする。ただし、それでも、このアルゴリズムは、特に低コストで資源節約型のノードを要求する幾つかの用途には対応できない。
上述から、当分野においては、無線マルチホップ網においてデータをルーティングするための現在の技術の上述の欠点、短所、不利益を克服することが可能な方法に対する必要性が存在することが理解できる。本発明は、当分野におけるこの必要性を満たす。より詳細には、本発明は、1995年11月16日付けで、A.Dasguptaの名前で出願された本発明と譲受人を同一とする係属中の米国特許出願第08/558,447号に開示されるＰａＳＴルーティングアルゴリズムを改善した簡単で動的に再構成できる能力を持つ再構成可能（reconfigurable：Ｒ−）なＰａＳＴルーティングアルゴリズム（Ｒ−ＰａＳＴ）に関する。
発明の開示
本発明は、一面においては、一つの制御ノードおよび複数の個別のノードから成る無線網を構成（コンフィギュア）するための方法に関する。この方法は、この無線網を論理的に複数のバンドＢｉ（ｉは添字を表す）に編成するステップを含む。ここで、これらバンドＢｉのおのおのは複数の個別のノードを含み、制御ノードからｉのホップ数だけ離れた所に位置する。ここで、ｉは、０〜Ｎの範囲に値で、Ｎは、１以上である。この方法はさらに、これら複数の各ノードに論理アドレスを割当て、こうして割当てられた論理アドレスを各ノード内に格納するステップを含む。本発明によると、これら複数の各ノードに割当てられる論理アドレスは、各ノードが位置するハンドＢｉを示す第一のアドレス部分と、各ノードを同一のバンド内に位置する他の全てのノードとの関連で識別する第二のアドレス部分を含む。
網を論理的に編成するステップは、好ましくは、制御ノードによって、網初期化手順の際に得られたノード接続性情報に基づいて遂行される。この網は、好ましくは、データがデータパケットを共通のＲＦチャネルを通じてノードからノードに伝送することによって通信されるパケットホッピング無線網とされる。
複数の各ノードは、好ましくは、自身の論理アドレスをそれが受信する各パケットに含まれるルーティング論理アドレスと比較し、この比較の結果に基づいてそのパケットを破棄、再送、あるいは処理するようにプログラムされる。本発明によると、受信されたパケットに含まれるルーティング論理アドレスは、パケットを発信ノードからルーティング論理アドレスによって指定される通信路に沿って宛先ノードにルートするために要求される全てのルーティング情報を含む。これとの関連で、受信された各パケットは、好ましくは、受信されたパケットが宛先ノードに向けて伝搬されるときの方向を示す方向ビット、受信されたパケットを送信ノードから宛先ノードに伝送するために要求されるホップの回数Ｎを示すホップ値およびホップカウントの数を含む第一のセットのビット（例えば、１バイト）、ルーティングのための論理アドレスを含む第二のセットのビット（例えば、１バイト）、および宛先ノードに対する処理インストラクションを含む第三のセットのビット（例えば、１バイト）を含む。
さらに、これら複数の各ノードは、好ましくは、受信されたデータパケットがそのノードによって再送されるべきであり、かつ、その方向が第一の方向（例えば、下り方向）であるときは、ホップカウントの数を増分し、受信されたデータパケットがそのノードによって再送されるべきであり、かつ、その方向が第二の方向（例えば、上り方向）であるときは、ホップカウントの数を減分するようにプログラムされる。
本発明のもう一面においては、制御ノードは、ルーティング論理アドレスを自身が送信する各パケットに挿入することにより、パケットのルーティングを制御するようにプログラムされ、任意のパケットの伝送が失敗したか否かを検出し、パケットの伝送が失敗した場合は、この検出に応答してルーティング論理アドレスによって指定される通信路内の故障ノードを検出し、伝送に失敗したパケットのルーティング論理アドレスを検出された故障ノードを含まない新たな通信路を指定する新たなルーティング論理アドレスに変更する；ことによって制御するようにプログラムされる。
【図面の簡単な説明】
図１は、ＰａＳＴルーティングアルゴリズムを採用する無線マルチホップ網において用いられる典型的なデータパケットの論理データ構造を示す図、図２は、ＰａＳＴルーティングアルゴリズムを採用する無線マルチホップ網の選択された部分の略図、図３は、本発明の現時点において好ましいとされる実施例によるルーティングアルゴリズムを採用する無線マルチホップ網の選択された部分の略図、図４は、本発明のルーティングアルゴリズムを採用する無線マルチホップ網において用いられる一例としてのデータパケットの論理データ構造を示す図。
発明を実施するための最良の形態
本発明の現時点において好ましいとされる実施例においては、この無線網はビルシステム制御網（例えば、知能照明制御システム）とされ、制御ノードはビルのコンピュータとされる。
本発明のもう一面においては、本発明は、上に説明の網構成および／あるいはルーティング方法を実現するために設計された無線網および網ノードに関する。
本発明のこれらおよびその他の特徴および長所が、本発明の以下の詳細な説明を、付属の図面と照らし合わせて読むことによってより良く理解できるものである。
図１は、1995年11月16日付けで、A.Dasguptaの名前で出願された本発明と譲受人を同一とする係属中の米国特許出願第08/558,447号に開示されるＰａＳＴルーティングアルゴリズムを採用する無線マルチホップ網において用いられる典型的なデータパケットの論理データ構造を示す。
図２は、ＰａＳＴルーティングアルゴリズムを採用する無線マルチホップ網の選択された部分の略図であって、網内の個々のノードの論理ＰａＳＴアドレスの導出において用いられる区分編成全域木（Partitioned Spanning Tree、ＰａＳＴ）の単一の枝の論理アドレス構造と共に、宛先ノードに割当てられた論理ＰａＳＴアドレスによって指定される中継器ノードの連鎖を通じての一例としてのデータ通信路を示す。
図３は、本発明の現時点において好ましいとされる実施例によるルーティングアルゴリズムを採用する無線マルチホップ網の選択された部分の略図であって、（ＰａＳＴ“木構造”の一つの枝に加えて）網のノードのバンドへの論理編成と共に、宛先ノードに当初割当てられた論理アドレスに従う中継器ノードの連鎖を通じての一例としてのデータ通信路を示す。
図４は、本発明のルーティングアルゴリズムを採用する無線マルチホップ網において用いられる一例としてのデータパケットの論理データ構造を示す。
図１は、1995年11月16日付けでA.Dasguptaの名前で出願された本発明と譲受人を同一とする係属中の米国特許出願第08/558,447号において開示されるＰａＳＴルーティングアルゴリズムを採用する無線マルチホップ網において用いられる典型的なデータパケットの論理データ構造を示す。このデータパケットの論理データ構造の詳細な説明については、上述の特許出願において開示されているためこれを参照されたい。
要約すると、ＰａＳＴルーティングアルゴリズムにおいて用いられる一例としてのデータパケットは以下のようなバイトを含む：
ａ）“ＦＬＡＧ（標識）”バイト：これは、パケットの優先レベルを示すビット欄、パケットのタイプ（例えば、ブロードカースト、マルチカースト、あるいはユニカースト等）を示すビット欄、パケットのルーティングに用いられるべきルーティングプロトコル（例えば、ＰａＳＴ、ＦＨＣ、ＰＡＲＥＮＴ等）を示すビット欄、パケットの伝搬方向（“上り”あるいは“下り”のいずれか）を示すビット欄等を含む数個のビット欄を含む；
ｂ）ＩＤバイト：これは、パケットに割当てられた一意のアドレスを含む；“アドレス長（Ａｄｄ．Ｌｎｇ）”バイト：これは、アドレスバイトのビット長を指定するが、ビルのコンピュータによって隣接する“論理アドレス（Ｌｏｇ．Ａｄｄ）”欄に挿入される；
ｃ）“下り”方向における論理アドレスバイト：これは、宛先ノード（つまり、ビルのコンピュータからのパケットの送り先である個別の網ノード）の論理ＰａＳＴアドレスを含む；“上り”方向における論理ＰａＳＴアドレスバイト：これは、論理アドレス欄に含まれ、送信ノードのアドレスを示す。勿論、この論理アドレス欄に含まれる論理ＰａＳＴアドレスバイトは、“下り”パケット（例えば、コマンドパケット）の宛先と、“上り”パケット（例えば、アクノレッジメント（受取通知）パケット）の送信機（者）が同一のノードである場合は同一となる；
ｄ）ＣＭＤバイト：これは、パケットを受信する宛先ノードによって実行されるべきコマンドを指定する；
ｅ）ＣＭＤ＿ＤＡＴＡバイト：これは、ＣＭＤバイトによって指定されるコマンドを実行するために宛先ノードによって用いられるべき特定のデータを含む；
ｆ）ＣＨＫＳＵＭバイト：これは、パケットに含まれる論理“１”ビット全部の合計を示す。このバイトは、ノードによって、パケット内に含まれるデータが有効であるか否かをチェックするために用いられる。
上述のように、各データパケットの論理アドレス欄に含まれる論理ＰａＳＴアドレスは、パケットを指定された宛先ノードにルートするために要求する全ての情報を含む。次に、図２の説明に移るが、図２は、ＰａＳＴルーティングアルゴリズムを採用する無線マルチホップ網２０の選択された部分を簡略的に示す。図２には、具体的には、網２０内の個別のノード２２の論理ＰａＳＴアドレスを導出するために用いられるＰａＳＴ（Partitioned Spanning Tree：区分編成全域木）の単一のブランチ（枝）の論理アドレス構造と共に、宛先ノードに割当てられた論理ＰａＳＴアドレスによって指定される（影の付いた円によって表される）中継器ノードの連鎖を通じての一例としてのデータ通信路が示される。
前述の米国特許出願第08/558,447号においてより詳細に説明されているように、網全体に対する論理ＰａＳＴ（Partitioned Spanning Tree：区分編成全域木）は、制御ノード２４（例えば、ビルのコンピュータＢＣ）によって、網の初期化手順の際に集められたノード接続性情報に基づいて構成され、一意の論理ＰａＳＴアドレスが、網２０内の個別の網ノード２２の各々に対して割当てられる。ノード接続性情報の完全さおよび正確さを最適化する無線パケットホッピング網を初期化するのに特に有効な方法については、本発明の譲受人に譲渡された1995年12月27日付けで本発明の発明者であるGeorge A.Melnikの名前で出願された本発明と譲受人を同一とする係属中の米国特許出願第08/579,650号において開示されているために詳細についてはこれを参照されたい。
ビルのコンピュータＢＣによって個別のノード２２の各々に割当てられる論理ＰａＳＴアドレスは、ビルのコンピュータＢＣとノード２２の間でパケットを前後に通信するために用いられるべき（図２の影を付けられた円によって表される）中継器の単一のセットあるいは連鎖すなわち“ホップの連鎖”、つまりパケットがビルのコンピュータＢＣと個々のノード２２との間で通信されるとき伝搬されるべき単一の所定の通信路（ルート）を一意に定義する。図２に示される大きな円は、それぞれの中継器ノードが、それらに対して中継器として機能すること（つまり、それに送られたパケットをルートすること）を指定されるグループあるいはセットのノード２２を表す。各々の大きな円の上の数は、その円に含まれる対応する中継器ノードの論理ＰａＳＴアドレスを表す。一般には、これら論理ＰａＳＴアドレスの導出および割当ては、最初に、ビルのコンピュータと各ノードの間の“最適”な通信路（つまり中継器ノードの特定の単一の“連鎖”）を決定し、次に、所定のビット割当て技法を用いてこの連鎖内の各中継器ノードを一意に識別することによって行なわれる。
例えば、前述の米国特許出願第08/558,447号において開示される一例としてのケースにおいえは、ビルのコンピュータＢＣに直接にリンクされた中継器ノード（つまり、連鎖内の“最初の”中継器）には、１つのセグメントから成る論理ＰａＳＴアドレスが割当てられ、このアドレスは、この中継器がそれらに対して中継器として機能するように指定された複数の“子”ノード（つまり、その大きな円内に含まれる複数のノード）との関連で、この中継器を“親”ノードとして一意に識別するのに十分の数のビットを含む。図２に示される特定の例においては、示される連鎖内の第一の中継器ノードに割当てられた論理ＰａＳＴアドレスは、“0100”（追加の零を用いるバイト形式である１６進法では＄４０）である。
この連鎖内の第二の中継器ノード、すなわちビルのコンピュータＢＣから１ホップだけ離れたこの連鎖内の第一の中継器ノードの“子”ノードである中継器ノードには、２つのセグメントから成る論理ＰａＳＴアドレスが割当てられ、このアドレスの第一のセグメントは、親ノード（つまりこの連鎖内の第一の中継器ノード）のアドレスから成り、第二のセグメントは、この中継器ノードをその兄弟（つまりこの連鎖内の第一の中継器ノード、つまり親ノードの他の“子”ノード）間で一意に識別するのに十分な数のビットを含む。図２に示される例では、示される連鎖内の第二の中継器ノードに割当てられた論理ＰａＳＴアドレスは、“0100/011”（＄４６）である。
この連鎖内の第三の中継器ノード、すなわちビルのコンピュータＢＣから２ホップだけ離れたこの連鎖内の第二の中継器ノードの“子”ノードである中継器ノードには、３つのセグメントから成るアドレスが割当てられ、このアドレスの第一および第二のセグメントは、親ノード（つまりこの連鎖内の第二の中継器ノード）のアドレスから成り、第三のセグメントは、この中継器ノードをその兄弟（つまりこの連鎖内の第二の中継器ノード、つまり親ノードの他の“子”ノード）間で一意に識別するのに十分な数のビットを含む。図２に示される例では、示される連鎖内の第三の中継器ノードに割当てられた論理ＰａＳＴアドレスは、“0100/011/11”（＄４７８０）である。
図２に示される宛先ノード、すなわち示される枝の端の葉に当たりビルのコンピュータＢＣから３ホップだけ離れた宛先ノードには、４つのセグメントから成る論理ＰａＳＴアドレスが割当てられ、このアドレスの第一、第二、および第三のセグメントは、その親ノード（つまりこの連鎖内の第三のノード）のアドレスから成り、第四のセグメントは、この宛先ノードをその兄弟（つまりこの連鎖内の第三の中継器ノード、つまり親ノードの他の“子”ノード）間で一意に識別するのに十分な数のビットを含む。図２に示される例では、示される連鎖内の宛先ノードに割当てられた論理ＰａＳＴアドレスは、“0100/011/11/011”（＄４７Ｂ０）である。
この論理ＰａＳＴアドレスビット割当て手続きは、この木構造内の各枝について葉（この木構造の根はビルのコンピュータＢＣである）に到達するまで継続される。ここで、各ノードに割当てられるアドレスセグメントの数は、そのノードの層／レベルの数に等しい。（ここで、第一の層／レベルは、ＢＣに直接にリンクされたノードであり、第二の層／レベルは、ＢＣから１ホップだけ離れたノードであり、こうして、ノードの層／レベルの番号は、そのノードに到達するために要求されるホップの数（ＮＨ）から１を引いた数に等しい（つまり、ＮＨ−１に等しい））。一般的には、各ノードに割当てられた論理ＰａＳＴアドレスの最後のセグメントは、自身をその兄弟（つまり同一の親ノードを持つ他のノード）に対して一意に識別するために要求されるｎ個のビットから成り、これらビットは、便宜的に、この論理ＰａＳＴアドレスの最上位ビットと呼ばれる。また、ビルのコンピュータＢＣと直接通信しない各ノードに割当てられた論理ＰａＳＴアドレスの最後の２つのセグメントは、それ自身のｎ個の最上位ビットと連結されたその親ノードの論理ＰａＳＴアドレスのｎ個の最上位ビットから成り、これらは、便宜的に、この論理ＰａＳＴアドレスのｋ個の最上位ビットと呼ばれる。
容易に理解できるように、各ノードに対する最上位ビットの実際の数ｎは、これとは異なることも考えられる。一般的には、そのノードをその兄弟に対して一意に識別するために必要なビット数ｍのみが利用され、こうすることによって論理ＰａＳＴアドレスの総ビット長が最小にされる。標準のＲＳ−２３２直列プロトコルを用いてのデータパケットのバイト単位の伝送を容易にするために、データパケットの論理アドレス欄に挿入される論理ＰａＳＴアドレスには、好ましくは、このビット長を等しくするのに十分な数の零が追加される。さらに、容易に理解できるように、図２は、これより大きな網２０のこれより大きな木構造の単に一つの枝を示すものであり、勿論、明るい円によって表される個々の全てのノード２２が、同様に、それ自身のセットのノードに対して中継器として機能するように指定されるものである。
図１に示すような論理構造を持つデータパケットが、無線網上を、図２に示すようなＰａＳＴルーティングアルゴリズムを用いて伝送されるわけであるが、このとき、パケットを受信する各ノード２２には、単に、自身の論理ＰａＳＴアドレス（これは各ノードのメモリ、例えばＥＥＰＲＯＭその他の不揮発性メモリ内に格納されている）と、受信されたパケットの論理アドレス欄内に含まれる論理ＰａＳＴアドレスとをビット毎に比較することで、そのノードが受信されたパケットに対する指定された宛先ノードあるいは受信されたパケットに対する指定された中継ノードであるか否かを決定することのみを必要とされる。この決定との関連で、全てのビットが一致することが検出された場合は、そのノードは宛先ノードであり、このために、このノードは、パケットを処理し、受信されたパケットのＣＭＤバイト内に含まれるコマンドを実行する。他方、全てのビットが一致することが検出されない場合は、そのノードの自身の論理ＰａＳＴアドレスのｋ個の最上位ビット（つまり最後の２つのアドレスセグメント）と、受信されたパケット内に含まれる論理ＰａＳＴアドレスとが比較される。そして、ｋ個のビットが一致することが検出された場合は、この受信されたパケットは、このノードが受信されたパケットに含まれる論理ＰａＳＴアドレスによって定義される宛先ノードに対する中継器連鎖内の中継器の一つであるために、このノードによって中継される。一方、ｋ個のビットのいずれかが一致しない場合には、受信パケットは廃棄される。
前述の米国特許出願第08/558,447号に開示されるＰａＳＴルーティングプロトコルは、データパケットの論理アドレス欄内に含まれる論理ＰａＳＴアドレスによって指定されるホップの連鎖内の正常に送信しなかった、すなわち送信ノードによってそれからのアクノレッジメント（受信通知）パケットが受信されなかった故障リンクを検出するための機構を持つ。例えば、ビルのコンピュータＢＣが照会パケットを特定のノードに送信したが、所定の時間内にその特定のノードからアクノレッジメント（受信通知）パケットを受信しない場合は、ビルのコンピュータＢＣは、（即座にあるいはさらに所定の回数の試みが失敗した後に）、任意の適当な故障検出方法に従って故障したリンクの探索を行なう。
前述の米国特許出願第08/558,447号に開示されるこのような一つの適当な故障検出法においては、ビルのコンピュータＢＣは、送信が失敗したパケット内に指定されるホップの連鎖内の各ノードに（ＰａＳＴプロトコルを用いて）順番にＥＣＨＯ（エコー）パケットを送信し、これを受信するホップの連鎖内の各ノードによってこのＥＣＨＯパケットのコピーが送り返されるのを待つ。あるノードからの応答が受信されない場合は、これはその応答しなかったノードがそのホップの連鎖内の故障ノードであることを示す。前述の米国特許出願第08/558,447号は、別の適当な故障検出法として、インプリシットなホップ・バイ・ホップアクノレッジメント（ＩＨＢＨ）法についても開示する。
いずれの故障リンク検出法を用いた場合でも、故障ノードがいったん識別されると、網を故障ノードを迂回してパケットをリルートする（ルートし直す）ために再構成する（構成し直す）ことが要求される。これは、この全域木を再構成する（構成し直す）こと、つまり、識別された故障ノードの所に根を持つ下位の全域木を網の異なる部分に接続することで、この下位の全域木の新たな親が全ての新たな子ノードを通信できるレンジ内に入るようにすることによって達成される。この網の再構成は、前に説明された方法で、必要な全域木とアドレスを割当てる動作を遂行することによって達成される。これとの関連で、ビルのコンピュータＢＣによって、下位の全域木の部分を分解し、その下位の全域木内の全てのノードが、その全域木の他の部分に再び接続されることを確認することが必要となる場合もある。実際、幾つかのケースにおいては、網全体を完全に再初期化する（初期化し直す）ことが必要となる。別の常駐のルーティングアルゴリズム、例えば、ＦＨＣ（Forward with Hop Count）を用いて、ホップの連鎖内の識別された故障ノードより遠方に位置する各ノードの論理ＰａＳＴアドレスを直接に再プログラムする（プログラムし直す）ことも考えられる。いずれにしても、故障ノードを除去するために必要とされる手続きは極めて困難であるとともに時間が非常にかかり、このために多くの用途に対しては現実的でない。
本発明の網構成およびルーティング法は、伝送に失敗したパケットを、簡単かつ迅速に、識別された故障ノードを迂回してリルートできるように（ルートを変えて伝送できるように）考案された。これとの関連で、本発明による網構成およびルーティング法においては、故障ノードが検出された場合、単に、伝送に失敗したパケットの論理アドレス欄に挿入されている論理アドレスを検出された故障ノードを含まない新たな通信路／ルート／ホップの連鎖を定義（規定）する新たな論理アドレスに変更することのみが要求される。このために、伝送に失敗したパケットを故障ノードを迂回してリルートするために（ルートを変更して伝送するために）網を再プログラミングあるいは再構成する必要がなくなり、これら動作と関連する遅延が回避される。
次に図３の説明に移るが、図３には、本発明の現時点において好ましいとされる実施例によるルーティングアルゴリズムを採用する無線マルチホップ網４０の選択された部分が簡略的に示される。図３には、さらに、（ＰａＳＴの木構造の一つの枝に加えて）網４０のノード４２のバンド（バンド０〜バンド３）への論理編成が示される。図３には、さらに、このＰａＳＴの木構造の示される枝の終端の所の葉である宛先ノードの最初に割当てられた論理アドレスに従う（影を付けられた）中継器ノードの連鎖を通る一例としてのデータ通信路が示される。
本発明によると、網初期化手続きの際にノード接続性情報を集めた後に、網４０が網４０をノード４２のバンド（バンド０〜バンド３）に論理的に編成することで構成される。ここで、伝送路において後続のバンドＢｉ＋１内のノード４２は、前のバンドＢｉ内のノード４２よりビルのコンピュータＢＣから１ホップだけ遠く離て位置する。ここで、ｉは０〜ｍであり、ｍは最も遠いバンドＢｍのビルのコンピュータＢＣからのホップ数を表す。
これとの関連で、特定のバンドＢｉ内の各ノード４２は、ビルのコンピュータＢＣからｉに相当するホップ数だけ離れて位置する。図３に示される例では、バンド０内に位置するノード４２は全て、ビルのコンピュータＢＣに直接リンクされており、従って、ビルのコンピュータＢＣからのホップ数は零（０）であり；バンド１内のノード４２は全てビルのコンピュータＢＣから１ホップ離れた位置し；バンド２内のノード４２は全てビルのコンピュータから２ホップ離れて位置し；バンド３内のノード４２は全てビルのコンピュータＢＣから３ホップ離れて位置する。
各バンドＢｉは、階層的な論理網構造内の異なるレベルあるいは層を構成するものと見なされる。好ましくは、特定のバンドの縁あるいは外辺に位置するノード（例えば、ビルのコンピュータＢＣへの断続的な接続性を示すノード）は、故障リンクがそのノードを根とする可能性を最小にするために、伝送路において後方のバンド（つまり、ビルのコンピュータＢＣから１ホップ離れたバンド内に入れられる。
本発明によると、ノード４２を、一連のバンドＢｉに編成した後に、網４０内の各ノード４２に論理アドレスが割当てられる。この論理アドレスの第一のアドレスセグメントは、そのバンドの番号を指定し、第二のアドレスセグメントは、各ノード４２を同一のバンド内の他のノード４２との関係で識別する。好ましくは、第二のアドレスセグメントに用いられるビット数は、同一バンド内の各ノード４２を一意に識別するのに十分な数とされる。
例えば、各バンドＢｉが、最大で１６個のノードを含むものとすると、この第二のアドレスセグメントは、各バンドＢｉ内の各ノード４２を一意に識別するために、たった４バイトのみを必要とする。さらに、各ノード４２に割当てられるバンドの番号は、好ましくは、そのノード４２が位置するバンドＢｉからビルのコンピュータまでのホップの数ｉとされる。こうして、図３に示す例では、各ノード４２に割当てられる論理アドレスの最初のアドレスセグメントは、そのノード４２が位置するバンドの番号を一意に識別する２ビットから成る。
便宜上、各ノード４２に割当てられる論理アドレスは、以降、“Bi/xxx”として示される。例えば、バンド番号ｂ０（つまりバンド０内に位置する）と、バンドアドレスセグメント“0100”を持つノード４２の論理アドレスは、“b0/0100”として示される。各ノード４２に割当てられた論理アドレスは、好ましくは、そのノードのメモリ、例えばノード４２内に組み込まれたＥＥＰＲＯＭその他のタイプの不揮発性メモリ内に格納される。本発明に従って網４０の構成の際にノード４２に割当てられる論理アドレスは、本発明のルーティングアルゴリズムは以降“Ｒ−ＰａＳＴ”ルーティングアルゴリズムと呼ばれるために、以降、便宜上、“Ｒ−ＰａＳＴ”論理アドレスと呼ばれる。
後に一層明らかになるように、このルーティングアルゴリズムは、ＰａＳＴルーティングアルゴリズムと同様にデータパケットが網４０内をノード４２によって単に自身のノードの論理アドレスと受信されたデータパケット内に含まれる論理アドレスとを比較することでルートされることを示す（ＰａＳＴ）ことに加えて、他方ＰａＳＴとは異なり、網が、故障リンクの検出に応答して、伝送に失敗したパケットを故障リンクの根の所の故障ノードを回避してリルートするために（パケットを別のルートを用いて伝送するために）、単にパケットの論理アドレス欄内に含まれる論理アドレスを変更することで、簡単かつ迅速に動的に“再構成（reconfigured：Ｒ−）”できることを示すために、“Ｒ−ＰａＳＴ”ルーティングアルゴリズムと呼ばれる。
次に、図４の説明に移るが、図４には、本発明のルーティングアルゴリズムを採用する無線マルチホップ網内で用いることが適当な一例としてデータパケットの論理データ構造が示される。図４に示すデータパケットは、図１との関連で前に説明されたデータパケットのそれと同一のデータ欄を含むが、ただし、ここでは、アドレス長（Add.Lag.）欄の代わりに、“ホップ情報（ＨＯＰ Info.）”欄が用いられる。
本発明の現時点において好ましいとされる実施例によると、このホップ情報バイトは、宛先ノードにパケットを送るために必要とされるホップの数を識別する第一のセグメント（第一の半分のバイト）、およびパケットを受信したノード４２が位置するバンドＢｉのバンド番号ｉを識別する第二のセグメント（第二の半分のバイト）を含む。
さらに、論理アドレス（Log.Add.）欄に挿入される論理アドレスは、好ましくは、送信ノードと宛先ノードの間の所定の通信路を構成するホップの連鎖を定義する各中継器のＲ−ＰａＳＴ論理アドレスのバンドアドレスのセグメントと、“下り”データ通信に対して宛先ノードに割当てられたＲ−ＰａＳＴ論理アドレスのバンドアドレスのセグメントあるいは“上り”データ通信に対して送信ノードに割当てられたＲ−ＰａＳＴ論理アドレスのバンドアドレスのセグメントの連結から形成される。
例えば、パケットを送信ノードから宛先ノードに伝送するために３つのホップが要求される場合は、パケットの論理アドレス欄に挿入される論理アドレスは、送信ノードと宛先ノードの間の指定されたホップ連鎖内の各中継器のＲ−ＰａＳＴ論理アドレスのバンドアドレスのセグメントに対応する３つの一連のアドレスセグメントと、“下り”データ通信に対して宛先ノードに割当てられたＲ−ＰａＳＴ論理アドレスのバンドアドレスのセグメントあるいは“上り”データ通信に対して送信ノードに割当てられたＲ−ＰａＳＴ論理アドレスのバンドアドレスのセグメントに対応する第四のアドレスセグメントから形成される。
動作においては、本発明のＲ−ＰａＳＴルーティングアルゴリズムは、以下のように機能する。より詳細には、パケットが最初にビルのコンピュータＢＣによって送信される場合は、このパケットのホップ情報バイトの第二の半分のバイトは、“０”の値を持つ。このパケットを受信する全てのノードは、自身のバンド番号ｉ（つまり自身のＲ−ＰａＳＴ論理アドレスの最初の部分）と、受信したパケットのホップ情報バイトの第二の半分のバイトによって示されるバンド番号ｉとを比較し、一致が検出された場合は、さらに、パケットの論理アドレス欄内に含まれる論理アドレスのｉ＋１番目のアドレスセグメントと、自身のＲ−ＰａＳＴ論理アドレスのバンドのアドレスセグメントとを比較するようにプログラムされる。
アドレスの一致を検出したノードは全て、さらに、パケットのＦＬＡＧ（標識）バイト内の所定の方向ビットの状態によって示される宛先ノードに到着するために伝搬されるべき方向（つまり“上り”あるいは“下り”）に依存して、パケット内に含まれるホップ情報バイトの第二の半分のバイトを増分（“下り”通信の場合）、あるいは減分（“上り”通信の場合）するようにプログラムされる。このようにして、パケットの論理アドレス欄に含まれる論理アドレスによって指定されるホップの連鎖内の各中継器ノードは、パケットを受信したとき、パケットのホップ情報バイトの第二の半分のバイトを適当に増分あるいは減分する。
図３に示す実施例の場合は、図４に示すようなパケットが、以下の方法で、ビルのコンピュータＢＣから示される枝の葉の所の宛先ノードb3/0110に向けて、本発明のＲ−ＰａＳＴルーティングアルゴリズムに従って伝送される。
最初に、パケットを受信するバンド０内の指定された中継器ノードb0/0100は、自身のＲ−ＰａＳＴ論理アドレスのバンドのアドレスセグメントと、パケットの論理アドレス欄に含まれる論理アドレス（＄４３２５）の第一のアドレスセグメント（＄４）のアドレスとが一致することを検出し、パケットのホップ情報バイトを＄３０から＄３１に増分した後に、パケットを再送する。
次に、このバンド０内の指定された中継器ノードb0/0100によって再送されたパケットを受信するバンド１内の指定された中継器ノードb1/0011は、自身のＲ−ＰａＳＴ論理アドレスのバンドのアドレスセグメントと、パケットの論理アドレス欄に含まれる論理アドレス（＄４３２５）の第二のアドレスセグメント（＄３）のアドレスとが一致することを検出し、パケットのホップ情報バイトを＄３１から＄３２に増分した後に、パケットを再送する。
次に、このバンド１内の指定された中継器ノードb1/0011によって再送されたパケットを受信するバンド２内の指定された中継器ノードb2/0010は、自身のＲ−ＰａＳＴ論理アドレスのバンドのアドレスセグメントと、パケットの論理アドレス欄に含まれる論理アドレス（＄４３２５）の第三のアドレスセグメント（＄２）のアドレスとが一致することを検出し、パケットのホップ情報バイトを＄３２から＄３３に増分した後に、パケットを再送する。
最後に、このバンド２内の指定された中継器ノードb2/0010によって再送されたパケットを受信するバンド３内の指定された中継器ノードb3/0110は、自身のＲ−ＰａＳＴ論理アドレスのバンドのアドレスセグメントと、パケットの論理アドレス欄に含まれる論理アドレス（＄４３２５）の第四のアドレスセグメント（＄５）のアドレスとが一致することを検出する。この時点で、ホップ情報バイトの第二の半分のバイト内のホップカウントがホップ情報バイトの第一の半分のバイトによって示されるホップの総数と等しくなるために、宛先ノードb3/0110は、パケットを処理し、パケットのＣＭＤバイト内に含まれるコマンドを実行する。宛先ノードによって受信されるパケットが図４に示される。
上の説明から容易に理解できるように、本発明によるＲ−ＰａＳＴルーティング法は、ビルのコンピュータと網内の任意のノードの間で伝送される各パケットの論理アドレス欄に挿入された論理アドレスによって指定される中継器ノードの特定のセットあるいは連鎖（あるいは“ホップの連鎖”）を介して、ビルのコンピュータと網内の各ノードの間に単一の所定の通信路を提供する。勿論、宛先ノードが、ビルのコンピュータと直接のＲＦリンクを持つ場合（つまりバンド０内に位置する場合）は、データパケットをこれらの間で交換するために中継器ノードは必要とされない。従って、Ｒ−ＰａＳＴルーティング法の機能のこの点は、前述の米国特許出願第08/558,447号に開示される元のＰａＳＴルーティング法の機能と類似する。ただし、本発明によるＲ−ＰａＳＴ法は、以下に説明される点において、元のＰａＳＴルーティング法と比較して機能の向上が見られる。
より詳細には、本発明によるＲ−ＰａＳＴ網の構成およびルーティング法では、ビルのコンピュータから宛先ノードに（あるいは逆方向に）送信されたデータパケットに対する応答がないことからリンクの故障が検出された場合、単に伝送に失敗したパケットの論理アドレス欄に挿入される論理アドレスを、故障リンクの根の所の故障ノードを迂回する新たな通信路（つまりホップの連鎖）を定義する新たな論理アドレスに変更することで、データパケットを、故障したリンクに対して責任のある故障ノードを回避してリルートすることで（ルートを変えることで）、容易にかつ迅速に伝送することが可能である。網を再プログラミングあるいは再構成する必要がないために、これらの動作によって発生する遅延が回避される。
例えば、図３に示す一例としての網４０を例に説明すると、ビルのコンピュータＢＣから宛先ノードb3/0110にパケットを伝送することに失敗し、これに応答してノードb0/0100からノードb1/0011に向うリンクの故障が検出された場合、その後の通信は、単に、パケットの論理アドレスを＄４３２５から＄３３２５に変更することで、ノードb0/0100の代わりにノードb0/0011を指定し、パケットを識別された故障ノードb0/0100を迂回してリルートする（ルートを変更する）ことで再送が試みられる。
さらに、パケットをこれと同一の宛先ノードb3/0110に、例えば、単にパケットの論理アドレスを＄４３２５から＄５７４５に変更することで、完全に異なるルート（通信路／ホップの連鎖）を用いて伝送することも可能である。
さらに、先に伝送に失敗したパケットをリルートする（ルートを変えてパケットを伝送する）前に、網内の一つあるいは複数のノードに別のアドレスあるいはバンド割当てを指定することにより、あるいは、最初の網の初期化および構成プロセスの際に十分に薄いバンドを設定することにより、あるバンド内の横方向の移動を含む新たなルートを選択する機能を得ることも可能である。
このように十分に薄いバンドを用いた場合は、追加の長所として、ある共通のバンド内の全てのノードに一意のバンドアドレスセグメントを割当てることができ、このために、同一のバンド内の２つのノードが同一のパケットを扱う可能性を排除することが可能となる。ただし、勿論、これは必須な要件ではなく、例えば、この可能性は、手前のバンド内の中継器ノードをこのバンドの意図されたノードのみがパケットを受信できるように選択したり、あるいは同一バンド内の同一のバンドアドレスセグメントを持つ複数のノードをこれが決して発生しないように十分に離して配置することによっても排除することが可能である。
パケットの論理アドレスによって定義されるホップの連鎖は、手前のバンド（つまり送信ノードに１ホップだけ近いバンド）内の指定された中継器ノードの送信レンジ内に、同一のハンド内に位置し、同一のアドレスを持つ２つあるいはそれ以上のノードが存在しない限り、送信ノードと与えられた宛先ノード間の唯一の可能な通信路としてそのまま機能する。上記のような状況は、不適当な通信路を選択した場合や、ビル全体に行き渡る強いノード・ツウ・ノード接続が与えられるような強いＲＦトランシーバを用いない限り発生しない。もし、後者のような状況が発生した場合は、より広いバンド（例えば、５〜６ビットのバンドアドレスセグメントを要求するバンド）と、結果としてのより少数のホップ数を用いることで対処することが必要となる。
上の説明から、当業者においては、室内ＲＦ通信網のおかれた厳しいフェージング環境においては、正常に受信されたことを確認されたデータ伝送を許容できるレベルに保つためには（つまり、データスループットを許容できるレベルに保つためには）、網を簡単かつ迅速に再構成できる機能並びに適応性が重要であることが理解できる。本発明によるＲ−ＰａＳＴ網構成およびルーティング法は、網を停止することなく、直ちに伝送に失敗したパケットを代替のルートを用いて伝送することを試みる機能を提供することによってこの重要な機能を達成する。
元のＰａＳＴ網構成およびルーティングプロトコルと同様に、本発明によるＲ−ＰａＳＴ網構成およびルーティングプロトコルは、資源節約型の網のノードを用いて、単一の通信路を維持し、可能な限り最も高速のデータ伝送と受信確認を行なうことを可能にする。
本発明によるＲ−ＰａＳＴ網構成およびルーティングプロトコルは、元のＰａＳＴの網構成およびルーティングプロトコルの持つ全ての利益および長所を維持し、同時に、無線網の全体としての能力および機能を改善する。
上では本発明が詳細に説明されたが、当業者においては上に説明された実施例以外のここに教示される本発明の基本的な概念に基づく多くの変更および／あるいは修正を容易に考えられるものである。従って、これらも請求の範囲に定義される本発明の精神および範に入るものと理解されるべきである。
【図１】
0003801651.tif 000002
【図２】
0003801651.tif 000003
【図３】
0003801651.tif 000004
【図４】
0003801651.tif 000005