(57)【特許請求の範囲】
【請求項１】
中央ノードと複数の個別ノードとを有する無線回路網内でデータパケットの経路を決める経路を決定する方法において、
前記中央ノードと前記個別ノードのうちの少なくとも選択されたものの各々との間の複数の経路をプログラムし、
前記中央ノードと前記個別ノードのうちの前記選択されたものとの間でデータパケットを前記プログラムされた複数の経路を介してランダムにホップさせる、
過程を有することを特徴とする経路を決定する方法。
【請求項２】
請求項１に記載の方法において、前記複数の経路をプログラムする過程が、前記複数の個別ノードを、各々、これら個別ノードの少なくとも他の一つに対する中継器ノードとして働くようにプログラムし、前記中継器ノードが前記中央ノードと前記個別ノードのうちの少なくとも選択されたものとの間に少なくとも２つのプログラムされた通信経路を形成することを特徴とする経路を決定する方法。
【請求項３】
請求項２に記載の方法において、前記ノードをプログラムする過程が回路網初期化過程中に得られるノード接続度情報に基づいて実行されることを特徴とする経路を決定する方法。
【請求項４】
請求項２又は３に記載の方法において、
前記個別ノードの各々がアドレステーブルを有し、
前記ノードをプログラムする過程が、前記中継器ノードの各々における前記アドレステーブル内に経路決めテーブルを記憶することにより実行される、
ことを特徴とする経路を決定する方法。
【請求項５】
請求項２、３又は４に記載の方法において、
前記個別ノードの各々が少なくとも自己のアドレスを含む第１のアドレステーブルと、第２のアドレステーブルとを有し、
前記ノードをプログラムする過程が、前記中継器ノードの各々の前記第２のアドレステーブル内に、当該ノードが中継器ノードとして働くようプログラムされる各ノードのアドレスを記憶する副過程を有する、
ことを特徴とする経路を決定する方法。
【請求項６】
請求項５に記載の方法において、前記ランダムにホップさせる過程が、
前記ノードのうちのデータパケットを受信する各々が、当該データパケットのアドレスバイトに含まれるアドレスを、当該ノードの前記第１のアドレステーブルに記憶された前記アドレスと比較し、前記第１のアドレステーブルに記憶された前記アドレスと前記アドレスバイトに含まれる前記アドレスとの間に一致が検出されたら、当該データパケットに応答し、
前記ノードのうちのデータパケットを受信する各々が、当該データパケットの前記アドレスバイトに含まれる前記アドレスを、当該ノードの前記第２のアドレステーブルに記憶された前記アドレスと比較し、前記第２のアドレステーブルに記憶された前記アドレスと前記アドレスバイトに含まれる前記アドレスとの間に一致が検出されたら、当該データパケットを中継する、
ような副過程を含むことを特徴とする経路を決定する方法。
【請求項７】
請求項６に記載の方法において、前記回路網は共通ＲＦチャンネルを有し、前記回路網中の全データ通信が前記共通ＲＦチャンネルを介してなされることを特徴とする経路決め方法。
【請求項８】
請求項６又は７に記載の方法において、前記ノードの各々がパケットＩＤメモリを有し、前記データパケットの各々が当該データパケットを識別するパケット識別コードを含むパケットＩＤバイトを有し、前記プログラムされた通信経路に沿ってデータパケットをランダムにホップさせる前記過程が、前記ノードのうちのデータパケットを中継する各々が、当該データパケットの前記パケット識別コードを当該ノードの前記パケットＩＤメモリに記憶し、
前記ノードのうちのデータパケットを受信する各々が、当該データパケットの前記パケット識別コードが当該ノードの前記パケットＩＤメモリ内に既に記憶されているか判定し、もし記憶されているなら、当該データパケットを捨てる、
ような副過程を有していることを特徴とする経路を決定する方法。
【請求項９】
請求項５、６、７又は８に記載の方法において、前記複数の個別ノードが、各々がユニークな群アドレスを有する少なくとも２つの別個のノード群に組織化され、前記プログラムする過程が、
前記個別ノードの各々の前記第１のアドレステーブル内に、当該ノードが属する何れかの群の前記群アドレスを記憶し、
前記個別ノードのうちの選択された組のノードの各々を、前記群の各々に対して群中継器ノードとして働くように、前記群中継器ノードの各々の前記第２のアドレステーブルに当該ノードが群中継器ノードとして働くよう選択された何れかの群の前記群アドレスを記憶することによりプログラムする、
ような副過程を有していることを特徴とする経路を決定する方法。
【請求項１０】
請求項５、６、７、８又は９に記載の方法において、前記回路網全体がグローバルアドレスを有し、前記プログラムする過程が、
前記グローバルアドレスを前記個別ノードの各々における前記第１のテーブルに記憶し、
前記個別ノードのうちの選択された組を、前記回路網全体に対するグローバル中継器として働くように、前記グローバルアドレスを前記グローバル中継器の各々の前記第２のアドレステーブルに前記グローバルアドレスを記憶することによりプログラムする、
ような副過程を有していることを特徴とする経路を決定する方法。
【請求項１１】
請求項１ないし１０の何れか一項に記載の方法において、前記個別ノードのうちの前記選択されたものが、前記中央ノードに直接結合されていないことを特徴とする経路を決定する方法。
【請求項１２】
無線回路網において、
無線送受信器と、デジタル信号処理回路と、メモリとを含む中央ノードと、
各々が無線送受信器と、デジタル信号処理回路と、メモリとを含む多数の個別ノードと、
を有し、複数の前記個別ノードの各々は前記個別ノードのうちの少なくとも他の一つに対して中継器ノードとして働くようプログラムされ、前記中継器ノードは前記中央ノードと前記個別ノードのうちの少なくとも選択されたものの各々との間に少なくとも２つのプログラムされた通信経路を形成し、当該回路網が前記プログラムされた通信経路に沿ってデータパケットがランダムにホップするようプログラムされていることを特徴とする無線回路網。
【請求項１３】
請求項１２に記載の無線回路網において、前記中央ノードは回路網初期化ルーチンを実行して前記プログラムされた通信経路をプログラムするためのノード接続性情報を得るようにプログラムされていることを特徴とする無線回路網。
【請求項１４】
請求項１２又は１３に記載の無線回路網において、前記中継器ノードの各々が当該ノードのメモリに記憶された経路決めテーブルを更に有していることを特徴とする無線回路網。
【請求項１５】
請求項１２、１３又は１４に記載の無線回路網において、前記個別ノードの各々が、少なくとも自己のアドレスを含む第１のアドレステーブルと、当該ノードが中継器ノードとして働くようプログラムされた各ノードのアドレスを含む第２のアドレステーブルとを更に有することを特徴とする無線回路網。
【請求項１６】
請求項１５に記載の無線回路網において、
前記個別ノードの各々が、受信したデータパケットのアドレスバイトに含まれるアドレスを、当該ノードの前記第１のアドレステーブルに記憶されたアドレスと比較し、もし両者の一致が検出されたら、当該データパケットに応答するようプログラムされ、
前記個別ノードの各々が、受信したデータパケットのアドレスバイトに含まれるアドレスを、当該ノードの前記第２のアドレステーブルに記憶されたアドレスと比較し、もし両者の一致が検出されたら、当該データパケットを中継するようプログラムされている、
ことを特徴とする無線回路網。
【請求項１７】
請求項１２、１３、１４、１５、又は１６に記載の無線回路網において、
前記個別ノードの各々がパケットＩＤメモリを有し、各データパケットが当該データパケットを識別するパケット識別コードを含むパケットＩＤバイトを有し、
前記中継器ノードの各々が、中継する各パケットの前記パケット識別コードを、当該ノードの前記パケットＩＤメモリに記憶し、
前記中継器ノードの各々が、受信した各データパケットの前記パケット識別コードを、当該ノードの前記パケットＩＤメモリに記憶された前記パケット識別コードと比較し、もし両者に一致が見られたら、当該データパケットを捨てるようにプログラムされている、
ことを特徴とする無線回路網。
【請求項１８】
請求項１２、１３、１４、１５、１６、又は１７に記載の無線回路網において、前記プログラムされた通信経路のうちの少なくとも選択されたものの各脚に対する前記中継器ノードの全てが、前記ノードのうちの互いに実効的に聴取範囲内にある複数個からなる共通セル内に位置することを特徴とする無線回路網。
【請求項１９】
請求項１２、１３、１４、１５、１６、１７、又は１８に記載の無線回路網において、中継器ノードの合計数が当該回路網中の個別ノードの合計数よりも少ないことを特徴とする無線回路網。
【請求項２０】
請求項１２、１３、１４、１５、１６、１７、１８、又は１９に記載の無線回路網において、当該回路網が建物システム制御回路網であり、前記中央ノードがビルコンピュータであることを特徴とする無線回路網。
【請求項２１】
請求項１５に記載の無線回路網において、
前記多数の個別ノードが、各々がユニークな群アドレスを持つ少なくとも２つの別個のノード群に組織化され、
前記個別ノードの各々の前記第１のアドレステーブルは、当該ノードが属する何れかの群の前記群アドレスを更に含み、
前記個別ノードのうちの選択された組のノードは、前記群の各々に対して群中継器ノードとして働くようプログラムされ、
前記個別ノードの各々の前記第２のアドレステーブルは、当該ノードが群中継器として働くようプログラムされた何れかの群の前記群アドレスを更に含んでいる、
ことを特徴とする無線回路網。
【請求項２２】
請求項１５又は２１に記載の無線回路網において、
前記回路網全体がグローバルアドレスを有し、
前記グローバルアドレスは、前記個別ノードの各々の前記第１のアドレステーブルに記憶され、
前記個別ノードのうちの選択された組のノードは、前記回路網全体のためのグローバル中継器として働くようプログラムされ、
前記グローバルアドレスを前記グローバル中継器の各々の前記第２のアドレステーブルに記憶する、
ことを特徴とする無線回路網。
【請求項２３】
請求項１２、１３、１４、１５、１６、１７、１８、１９、２０、２１、又は２２に記載の無線回路網において、当該回路網がインテリジェント照明システム制御回路網であることを特徴とする無線回路網。
【請求項２４】
複数の他のノードを含む無線回路網に用いるノードにおいて、
データを当該回路網の他のノードに送信し、且つ、当該回路網の他のノードからのデータを受信する無線送受信器と、
当該ノードの自己アドレスと、当該ノードが中継器として働く他の全てのノードの中継アドレスとを記憶するメモリと、
を有し、データパケットがランダムにホップするよう、当該ノードが前記他のノードのうちの少なくとも２つに対し中継器として働くようにプログラム可能なことを特徴とするノード。
【請求項２５】
請求項２４に記載のノードにおいて、前記無線送受信器により受信されたデータパケットに応答して、当該データパケットのアドレスバイトに含まれる宛先アドレスを前記メモリに記憶された前記アドレスと比較し、もし前記自己アドレスと前記宛先アドレスとの間に一致が検出されたら、当該データパケットを処理し、前記中継アドレスの何れかと前記宛先アドレスとの間に一致が検出されたら、前記無線送受信器に当該データパケットを中継するよう命令するようなデジタル信号処理回路を更に有していることを特徴とするノード。
【請求項２６】
請求項２５に記載のノードにおいて、前記デジタル信号処理回路が、更に、前記データパケットに応答して、当該データパケットのパケットＩＤバイトに含まれるパケットＩＤを抽出し、該抽出されたパケットＩＤを前記メモリに記憶することを特徴とするノード。
【請求項２７】
請求項２６に記載のノードにおいて、前記デジタル信号処理回路は、更に、前記データパケットに応答して、当該データパケットの前記抽出されたパケットＩＤを、前記メモリに記憶された他の何れのパケットＩＤとも比較し、もし一致が検出されたら、当該データパケットを捨てることを特徴とするノード。
【請求項２８】
請求項２４、２５、２６、又は２７に記載のノードにおいて、前記メモリが前記自己アドレスを記憶する第１のアドレステーブルと、前記中継アドレスを記憶する第２のアドレステーブルとを含むことを特徴とするノード。
【請求項２９】
請求項２６に記載のノードにおいて、前記メモリが所定数のパケットＩＤバイトの記憶容量を持つ循環式ＦＩＦＯバッファを有していることを特徴とするノード。
【請求項３０】
請求項２９に記載のノードにおいて、前記データパケットが中継される場合にのみ、前記パケットＩＤが前記メモリに記憶されることを特徴とするノード。
【発明の詳細な説明】
技術分野
本発明は、広くは無線パケットホッピング回路網に係り、更に詳細にはそのような回路網内でデータパケットのルートを決定する方法並びにそのような方法を実施する無線回路網及びノードに関する。
背景技術
無線リンク（ＲＦリンクのような）を介して相互間及び中央ノートと通信する複数のノードからなる回路網は、一般に、無線（電波）回路網と呼ばれている。このような無線回路網では、各ノードはデジタル信号処理装置（例えば、マイクロプロセッサ）及び所定の伝送範囲を持つ無線（ＲＦ）送受信器を含んでいる。データは典型的には「パケットホッピング」として知られる技術により個別のノードと中央ノードとの間で通信（伝送）されるが、この場合、個々のデータのパケットは中央ノードから宛先ノードへ、及び発信元ノードから中央ノードへと、回路網経路決め手順に従ってノードからノードへとホップされることにより伝送される。
「パケット」は、大きさが典型的には約５〜１０００バイトの範囲のデータの論理単位である。一般に、これらのパケットホッピングによるデータ通信は中央ノードの制御下になされ、該中央ノードは通常データ通信制御ソフトウエアが在住する電子計算機である。パケットホッピングによるデータ伝送法は、ＲＦ送受信器の価格の低下及びＵＤ  ＦＣＣパート１５要件のような政府機関要件に準拠することを可能にする。データの各パケットは発信元となる又は宛先となるノードのアドレスを含んでいる。各ノードのアドレスは当該回路網が元々設置されるときに決められる。
このような無線パケットホッピング回路網は、建物の１以上の機能又はシステム、例えば当該建物の照明、ＨＶＡＣ及び／又は安全保障システム等を制御するのに特に適している。何故なら、このような回路網は当該回路網の情報を伝送するために既存の構造に追加されるべき新たな信号線を必要としないような安価な屋内幾何学構成を提供するするからである。更に、上記のような回路網は当該建物中に設置された呼び出しシステム及び個人通信システムのような付加的なシステムの助けにもなる。
上記のような建物制御回路網の中央ノードは、典型的には、システム制御そるとウエアが在住するプログラマブル中央制御器又はビルコンピュータである。個々のノードは、典型的には、制御される建物システムの所定のパラメータの状態／値を監視し、このようなパラメータを望むように調整するために当該ビルコンピュータにより発生された命令に応答して制御信号を発生すべく当該建物全体にわたって分散される。当該ビルコンピュータは、システム制御ソフトウエアに従って、上記のようなパラメータの状態／値を適切に監視すべく当該回路網中の各ノードへ／からデータを送信／受信することができ、且つ、上記のようなパラメータを所望に応じて調整すべく命令を発することができることが重要である。
例示的な建物制御回路網は、当該回路網内の建物の各部屋及び／又は敷地、即ち当該ビルコンピュータの制御／管理下にある回路網内のノードを構成するＲＦ送受信器に接続された照明モジュールを備える建物の各部屋及び／又は敷地の照明レベル、使用状態、時間の関数としてのエネルギ消費及び／又はその他の照明パラメータを監視する自動又はインテリジェント照明制御システムである。
上記のようなインテリジェント照明制御システムにおいては、上記照明モジュールの各々は対応するランプの照明レベルを直接制御することができるように個別にプログラム可能（例えば、建物使用者により）なものとする。この点に関して言うと、上記照明モジュールの各々は１以上のセンサ（例えば、使用状態センサ、日光（周囲光）センサ及び調光／照明レベルセンサ）含む。これらセンサは搭載されたデジタル信号処理装置（例えば、マイクロプロセッサ）にセンサ帰還データを供給し、該処理装置は上記センサ帰還データを解析し、プログラムされた局部照明条件が必要に応じて達成されるように対応する監視下のランプの照明レベルを調整するための制御信号を発生するようにプログラムされている。
このセンサ帰還データは、ビルコンピュータによりそうするよう要求された場合、又は局部照明条件が変化した場合にも、当該回路網内の各ノードにより該ビルコンピュータに送信される。当該ビルコンピュータは、該コンピュータにロードされた照明システム制御ソフトウェアに従って上記のようなセンサ帰還データを解析すると共に所望に応じて個別のノードに対して制御データ（命令）を送信することにより、当該建物の監視下の部屋／敷地の照明レベルを照明システム制御ソフトウェアに従って調整し、例えば、当該照明システムのエネルギ効率を最適化し、これにより個々の照明モジュールによりなされたプログラムされた照明レベルを強制変更する。このように、個々にプログラム可能であり且つ独立して操作可能であるのに加えて、分散されたモジュールはビルコンピュータの制御下で機能的に単一の建物全体の回路網に統合される。
建物制御回路網の設置は、物理的配置と当該回路網の各ノードへの給電とを必要とする。当該回路網中の各ノードのアドレスは、各ノードの当該回路網内の物理的位置と一緒に、設置時に各ノードにプログラムされるか、又は、事前にプログラムされている場合は中央ノード（ビルコンピュータ）のメモリに記録される。このような回路網におけるデータ通信は、一般に、共通の通信チャンネルを介し、回路網経路決め手順に従ってビルコンピュータと個別のノードとの間又はその逆の間でなされる。データは、パケットの形で、ビルコンピュータから当該ビルコンピュータの直接伝送範囲外（即ち、当該ビルコンピュータに直接リンク又は「接続」されていない範囲）の宛先ノードへ、ノードからノードへと当該パケットが宛先ノードに到達するまで各パケットをホッピングさせながら又は中継しながら伝送される。パケットを当該回路網内の１以上の他のノードにホップさせ又は中継する各ノードは、通常、「中継器」と呼ばれている。宛先ノードは、通常、ビルコンピュータからのデータパケットの受信を１以上の中継器を介して当該ビルコンピュータに対し確認データパケットを同様のやり方で返送することにより確認する。
通常、無線回路網で使用される回路網経路決めアルゴリズムには２つの主たる分類、即ちランダム経路決め手順及び確定的（テーブル式）経路決め手順である。ランダム経路決め手順では、パケットは、特定の組みの中継器をデータ伝送の実施のために使用することなしに、当該回路網内のノードを介して送り手ノードから宛先ノードへランダムにホップされる。更に詳細には、該ランダム経路決め手順によれば、送り手ノードはパケットを当該送り手ノードの伝送範囲内の全ノードへ送信し、当該パケットを受信した各ノードはその伝送範囲内の全ノードへ該ノードを再び送信又は中継し、以下同様のことが当該パケットが宛先ノードに到達するまで行われる。典型的には、各パケットは通常「ホップカウンタ」と呼ばれるバイトを含み、該バイトは中継器により零に到達するまで減算計数される。当該バイトが零に到達すると、当該パケットは最早中継されない。上記ホップカウンタは送り手（送信する）ノードにより、当該パケットが宛先ノードに到達する確立が当該回路網が過剰に長い期間にわたり占有することなく最大となるように設定される。
共通の回路網チャンネル上でのパケットの同時伝送を最小化するために、チャンネルアクセス手順が使用される。最も一般的なチャンネルアクセス手順はキャリアセンス多重アクセス（ＣＳＭＡ）手順である。この手順によれば、各ノードはパケットを送信するに先立ちランダムな遅延時間の間待ち、次いでチャンネルが利用可能（「クリア」）か又は利用不可能（「ビジー」）であるかを決定すべく該チャンネルを検知する。チャンネルがクリアであると検知された場合は、該ノードは前記パケットを送信し、チャンネルがビジーであると検知された場合は、当該パケットの送信を試みるに先立ち、当該チャンネルは再度チャンネ状態を検知する前に他のランダムな期間だけ待つ。
しかしながら、回路網内の全てのノードが互いに「聴取範囲」内にあるということはないから、互いの聴取範囲外の２つのノードが当該チャンネルはクリアであると検知して時間的に重なる各パケットを同一の受信ノードに送信してしまうことがしばしば発生し、この結果両データパケットが崩れ、これが受信ノードには雑音として現れる。この現象は、通常、「不可避的衝突又は解決不能な衝突」と呼ばれる。前記ランダム経路決め手順では、回路網内の全てのではなくても殆どのノードが送信された各及び全パケットを扱うことになる確立がかなり高く、これにより当該回路網内のデータ通行密度が大幅に増加し、従って或る時間において「回路網上」に存在し得る異なるパケットの数（即ち、当該回路網のデータ伝送処理能力）を大幅に制限してしまう。このことは、当該回路網の通信効率を制限すると同時に、発生する解決不能な衝突の数を増加させる。
これらのデータパケットの解決不能な衝突は、パケットを宛先に到達する前に失われせてしまう可能性がある。これに関して言うと、建物制御回路網においては、ビルコンピュータに返信される確認パケットは典型的には当該ビルコンピュータに結合された２、３個のノードに集中してしまい、この結果、これらパケットに関わる解決不能な衝突が高い確率になり且つ数が増加する。結果として、確認パケットの障害が普通となり、これにより、送出された元のパケットが宛先ノードにより実際に受信されたか否かを決定せんがためにビルコンピュータはパケットを再送信せざるを得なくなる。
前記確定的又はテーブル式経路決め手順によれば、ビルコンピュータは、回路網初期化ルーチンの実行の間に収集するノードの接続度情報に基づいて、経路決めテーブルを形成する。この場合、これらの経路決めテーブルは、データのパケットを中継器の特定の組み合わせ又は「鎖」を介して（即ち、経路決めテーブル中に規定された所定の経路又は単一の経路に沿って）送り手ノードから宛先ノードへと経路決めするために使用される。これにより、多数の異なるパケットが同時に「回路網上」に存在することが可能になり、結果として、前記ランダム経路決め手順で可能なものよりも高い回路網データ伝送処理能力が得られる。しかしながら、無線回路網固有のＲＦ上の制約から、この確定的経路決め手順は当該回路網の通信効率を厳しく制限してしまい、その結果、（ランダム経路決め手順による）複数のランダムな経路の場合とは反対に、経路が単一の所定の経路に沿うことにより、或るパケットが宛先に到達する確率が比較的低くなる。
この点に関して言うと、屋内無線回路網におけるノード間通信の信頼性は、フェージング又はマルチパス（ＲＦ信号と、壁、床、天井、家具等の表面からの反射による自身との干渉）等の現象により悪影響を受け、これにより以前に確立されたノード対ノード結合が中断され又は失われる。更に、このように以前に確立されたノード対ノード結合は、建物居住者の或る行動のような当該建物の屋内環境の動的変化により遮断され又は失われる可能性がある。例えば、扉を開閉する、家具を移動させる、又は廊下を歩く等の単純な行動でさえ、ノード対ノード通信結合を崩す可能性がある。このように、回路網中の如何なるノード対ノード結合の状態も、大抵は予測不可能且つ制御不可能な多数の変数に依存して、時間と共に密なものから、まばら、存在しない、へと変化し得る。
このような元来のリンクの信頼性の問題により、単一の経路を経て伝送されるデータパケットは宛先に到達するまえに簡単に失われてしまう可能性があり、従って、そのようなデータパケットは再送信する必要があるので、これにより当該回路網の通信効率が劣化する。伝送が不成功となるに要するものは、一連の中継器での単一リンクが、当該ビルコンピュータから宛先ノードへの命令データパケットの送信伝送上で破壊されるか、又は宛先ノードから当該ビルコンピュータへの確認データパケットの受信伝送上で破壊されるかの何れかが全てである。問題が生じたリンクのリンク品質が満足に解決されない場合は、当該パケットは再経路決めされるか及び／又は回路網が再編成されねばならず、これにより当該回路網の性能は更に劣化し、コスト及び複雑さが増す。
再編成能力を含む確定的経路決めアルゴリズムは、標準的な確定的経路決めアルゴリズムより確かに改善されている。このような確定的経路決めアルゴリズムは本発明の譲受人に譲渡された１９９５年１１月１６日出願の米国特許出願第０８／５５８４４７号に開示されており、本明細書では該開示を参考文献として引用する。しかしながら、このような経路決めアルゴリズムも依然として、故障したリンク又は経路の脚部を識別し、且つこれを迂回する経路をプログラムすることができるようなオペレータ又は何等かのプログラムされた処理ルーチン（典型的にはビルコンピュータにより実行される）の助けを必要とする。しかしながら、このような再経路決めは非常に時間が掛かり、発生する当該障害が一時的なものである場合は全く保証することができない。更に、新たな経路は以前の経路よりも良くない可能性もある。又、このようなアルゴリズムは、経路決め用の情報のかなりの部分がデータパケットに含まれていることを要し、これによりこれらパケットの大きさが増大し、結果として当該回路網のデータ伝送処理能力及び通信効率が低下する。
上述したようなリンクの信頼性の問題を扱う既知の種々の方法がある。リンクの信頼性を改善する一つの方法は、高出力のＲＦ送受信器を使用することであり、又リンクの信頼性を改善する他の一つの方法はノイズを制限する拡散スペクトル送受信器を用いることである。しかしながら、これらの対策の何れも、通常、多くの応用例ではコストが掛かりすぎる。勿論、配線により接続された回路網は理想的な解決策であるが、このような回路網を既存の構造物に設置する費用は、多くの用途では採用困難な程高い。
上述したような諸事情に基づき、当該技術分野には上述したような現在の技術の欠点、不十分さ及び問題点等を克服するような無線パケットホッピング回路網におけるパケットの経路決め方法に対する要求が存在すると考えられる。本発明は、当該技術分野における該要求を満たすものである。
発明の開示
本発明は、例えばインテリジェント照明制御システムのような無線パケットホッピング回路網内でデータパケットの経路決めを行うランダム複数経路テーブル式経路決め方法を含むもので、該方法は中央ノード（「回路網制御ノード」とも呼ぶ）と前記個別ノードのうちの少なくとも選択されたものの各々との間に複数の通信経路をプログラムし、前記データパケットを上記プログラムされた通信経路に沿ってランダムにホップさせるような過程を含む。好ましくは、上記複数経路は、複数の前記個別ノードの各々が少なくとも１つの他の個別ノードに対する中継器ノードとして働くようプログラムすることによりプログラムされ、これら中継器ノードが前記通信経路を形成するようにする。上記中継器ノードは、好ましくは、回路網初期化過程の間に得られるノードの接続度情報に基づいてプログラムされる。
前記中継器ノードは、好ましくは、コンパクトな部分的経路決めテーブルを、これら中継器ノードの各々のメモリ部分に記憶することによりプログラムされる。この経路決め方法は、経路決めテーブルが前記複数通信経路を予めプログラムするために使用されるという点で部分的に確定的か又は表的であり、前記データパケットが予めプログラムされた単一の経路に沿ってホップされるというより上記の予めプログラムされた複数経路に沿ってランダムにホップされるという点で部分的にランダムである。
前記個別ノードの各々は、好ましくは、例えばＥＥＰＲＯＭ又は他の不揮発性メモリ装置のような当該ノードの各メモリに記憶された第１のアドレステーブルと第２のアドレステーブルとを含む。前記プログラムする過程は、好ましくは、前記個別ノードの各々の第１のアドレステーブルに少なくとも当該ノードの自身のアドレスを記憶し、複数の前記個別ノードを少なくとも１つの他のノードに対して中継器として働くよう選択し、前記個別ノードの各々の第２のアドレステーブルに当該ノードが中継器ノードとして働くよう選択された各ノードのアドレスを記憶することにより実施される。
前記のデータパケットをランダムにホップさせる過程は、好ましくは、データパケットを受信する各ノードが当該データパケットのアドレスバイトに含まれるアドレスを当該ノードの第１のアドレステーブルに記憶されたアドレスと比較し、もし一致が検出されたら、当該データパケットに応答し、更に当該データパケットのアドレスバイトに含まれるアドレスを当該ノードの第２のアドレステーブルに記憶されたアドレスと比較し、もし一致が検出されたら、当該データパケットを中継することにより実施される。全てのデータ通信は、好ましくは、共通のＲＦチャンネルを介して例えばＣＳＭＡ手順のような予め規定されたチャンネルアクセス手順に従って実施される。
前記個別ノードの各々は、好ましくは、当該ノードが中継する各パケットのパケットＩＤを例えば２バイトの循環式（ＦＩＦＯ）パケットＩＤバッファのようなパケットＩＤメモリに記憶し、当該ノードが受信する各パケットのパケットＩＤを当該ノードのパケットＩＤメモリに記憶されたパケットＩＤと比較し、もし一致が検出されたら、当該データパケットを捨てるようにプログラムされる。このようにして、「バックラッシュ」（即ち、データパケットの宛先の方向とは逆の方向へのホップ）が防止される。
本発明の好ましい実施例においては、前記中継器ノードのうちの少なくとも一つ（最も好ましくは、各々）が、当該回路網中の全ての他のノードよりは少ないが、少なくとも一つの他のノードに対して中継器ノードとして働くようプログラムされる。更に、中継器ノードの合計数は当該回路網中の個別ノードの合計数よりも少なくすることができる。
本発明の一実施例においては、前記多数の個別ノードが、機能的又は論理的に相関関係を持つノードの２以上の別個の組又は群に組織化され、各群がユニークな群アドレスを持つようにする。この実施例では、前記プログラムする過程は、各ノードの第１のアドレステーブルに当該ノードが属する全ての群の群アドレスを記憶し、当該回路網中の前記ノードの或る組を各群に対する群中継器として働くよう選択し、各群中継器ノードの第２アドレステーブルに当該ノードが群中継器として働くよう選択されている全ての群の群アドレスを記憶するような各過程を含む。
本発明の他の実施例では、前記回路網全体にグローバルアドレスが付与され、前記プログラムする過程が、上記グローバルアドレスを前記個別ノードの各々の第１アドレステーブルに記憶し、前記個別ノードの選択された組を、当該回路網全体に対するグローバル中継器として働くよう、これらグローバル中継器の各々の第２アドレステーブルに上記グローバルアドレスを記憶することによりプログラムするような各副過程を更に含む。
又、本発明は上述した本発明の経路決め方法を実施するようプログラムされた無線回路網及び無線ノードも含む。
本発明の上述した及び種々の他の利点及び作用効果は、添付図面を参照してなされる以下の説明から理解されるであろう。
【図面の簡単な説明】
第１図は、本発明によるパケット経路決め方法を用いることができる無線パケットホッピング型インテリジェント照明制御システムのブロック図。
第２図のＡ、Ｂ及びＣは、パケットが元のノードから宛先ノードへ及び元のノードへ戻るように成功裏に伝送される確率を、３つの異なる経路例に関して各々示す図で、１つは従来の経路決め方法による例を示し、他の２つは本発明の経路決め方法の例を示す。
発明を実施するための最良の形態
先ず概略を述べると、本発明による経路決め方法によれば、データパケットは、回路網初期化ルーチンの間に得られるノードの接続度情報に基づいて予め選択及びプログラムされた複数の経路に沿ってランダムにホップされ、これにより成功する伝送の確率を最大化する。この点に関して言うと、本発明の経路決め方法は、従来の純粋にランダムな経路決め方法の場合になされるように中継器としての当該回路網中の全ノードを用いる全ての可能な経路を介してパケットをランダムにホップさせるというよりも、中継器として働くように予めプログラムされた特定のノードの組を用いてノード間の複数の経路をプログラムするために経路決めテーブルが使用されるという点で、部分的に確定的又はテーブル式である。又、本発明の経路決め方法は、パケットが、従来の純粋に確定的経路決め方法の場合になされるように、予めプログラムされた単一の各経路に沿ってホップされるというよりも、上記の予めプログラムされた複数の経路に沿ってランダムにホップされるという点で、部分的にランダム的である。従って、以下に更に詳細に述べられるように、従来の純粋にランダムな経路決め方法の利益及び利点（即ち、通信の成功の高確率性）及び従来の純粋に確定的経路決め方法の利益及び利点（即ち、当該回路網の高データ伝送処理能力）の両方が、本発明の該ランダム複数経路テーブル式経路決め方法では実現され、それでいて同時に、これら従来の経路決め方法の不利益及び欠点が除去される。
本発明のランダム複数経路テーブル式経路決め方法は、従来の純粋に確定的経路決め方法でなされていたように全経路決め情報を含むパケットを伝送するというよりも、コンパクトな部分的経路決めテーブルを当該回路網内のノードのうちの少なくとも予め選択されたもののメモリ部分内にプログラム及び記憶することにより基本的に実施される。本発明の経路決め方法はデータパケット中に全経路決め情報を含ませる必要性を除去し、これにより各パケットの大きさを大幅に減少させ、従って当該回路網のデータ伝送処理能力及び通信効率を大幅に上昇させると同時に当該回路網のハードウェアの要件（例えば、所要ボーレート及びパケットバッファの大きさ）を大幅に低減させることができることに注意されたい。
この点について言うと、予め選択されたノードの各々のメモリ部分に記憶される部分的経路決めテーブルは、当該ノードが中継するようにプログラムされた各ノードのアドレスを含む「中継」アドレステーブルを含む。パケットのアドレスバイトに含まれるアドレスが、特定のノードの中継アドレステーブル内に記憶された何れかのアドレスに一致した場合は、当該ノードは該パケットを中継する。このように、予め選択されたノードの各々は、中継器ノード（又は、単に「中継器」）として働く。
更に、当該回路網中のノード（如何なる非中継器ノードも含む）の各々はユニークなアドレスを有し、該アドレスは当該ノードのメモリ部分に記憶される。パケットのアドレスバイトに含まれるアドレスが特定のノードのアドレスと一致した場合は、該ノードは当該パケットの命令バイト中に含まれる命令を実行する。本発明の好ましい実施例では、当該回路網中のノード（如何なる非中継器ノードも含む）の各々は「応答」アドレステーブルを含み、該テーブルは、自己のアドレスに加えて、当該ノードが属する何れかの群のアドレス及び／又は「グローバル」アドレスと呼ばれる当該回路網中の各ノードの共通アドレスを構成するアドレス（従って、当該回路網中の全ノードは「グローバル群」のものであると考えられる）を含む。
従って、当該回路網中の或る群のパケット（又は全ノード）とパケット通信を行いたい場合は、当該群全体中の（又は当該回路網全体の）各ノードを個別にアドレス指定するというよりも、パケットのアドレスバイトに上記群全体のアドレス（又はグローバルアドレス）を含めるだけでよく、これによりアドレス指定された群の（又は回路網全体の）各ノードは当該パケットを処理し、当該パケットの命令バイトに含まれる命令を実行する。
上記構成は、当該回路網を機能的に又は論理的に相互に関係のあるノードの複数の明確な群に組織化又は編成したい場合に特に有用である。例えば、ビルのインテリジェント照明制御システムの場合、廊下の交互の奇数番目及び偶数番目の照明を別の群に組織化し、例えばエネルギ節約及び安全保障の目的で通常の業務時間後に第１群の照明を「オフ」となるよう命令し、第２群の照明を「オン」となるよう命令することができるようにしたい場合がある。論理的に相関関係のあるノード群の他の例は、ビル（又はビルのウイング）内の全ユーティリティルーム、ビルの特定のウイング内の全（又は選択され）部屋、及びビル（又はビルのウイング）内の全休憩室等を含む。グローバルアドレス指定は、地域官庁又は電力会社により命令された警戒管制時のビル内の全照明を減光する、又は緊急事態の場合にビル内の全照明を強制的に最高照度にする等の目的に使用することができる。このような群アドレス指定及びグローバルアドレス指定は、当該ビルコンピュータにより送出された命令の、郡内又は回路網内の各ノードを個々にアドレス指定するに要する時間のほんの一部の時間内での実行を可能にする。
又、当該回路網中のノードは、好ましくは、通信「クラスタ」又は「セル」に組織化され、各セル内では全てのノードが少なくとも互いに「聴取範囲」内にあり（即ち、他のノードの何れかが或る時点でデータパケットを送信しているか否かを感知することができ）、これにより当該セル内でのデータパケットの解決不可能な衝突という事態を最小化する。中央セルと或る個別のセルとの間の複数の経路をプログラムする場合、これら複数の経路の各脚に対して中継器として選択された各ノードは、好ましくは、共通のセル内に位置され、従って、それらノードが互いに「聴取」することができ、これにより上記中央ノードと上記或る個別のノードとの間で通信されるデータパケットの解決不可能な衝突という事態を最小化する。
更に、中継器ノードの各々に記憶された中継アドレステーブルは、当該ノードが中継器として働くよう選択された何れかの群（「グローバル群」を含む）のアドレスを付加的に含んでもよい。この点に関して言うと、当該回路網中の特定の組の（好ましくは、少なくとも２つの、しかし全部よりは少ない）ノードだけが当該群用の中継器として働くようにプログラムされ、これにより、さもなくば発生しかねないデータパケットの解決不可能な衝突の数を最小化する。
中継器ノード中に記憶された部分的経路決めテーブルは「中継」及び「応答」アドレステーブルの両方を含むものと考えることができる。事実、本発明の好ましい実施例では、当該回路網中の全てのノード（何れの非中継器ノードをも含む）には、「中継」及び「応答」アドレステーブルからなる部分的経路決めテーブルが設けられる。勿論、当該回路網中の如何なる他のノードに対しても中継器として働くよう選択されていない全てのノードは、それらの「中継」アドレステーブルへは入り込まないであろう。好ましくは、上記の部分的経路決めテーブルは、ボード上のＥＥＰＲＯＭ（電子的に消去可能なプログラム可能型読出専用メモリ）のような不揮発性メモリ装置に記憶され、これにより上記テーブルが偽電力停止の間に重大な経路決め情報が無くなる危険性なしに維持されるようにする。
本発明のランダム複数経路テーブル式経路決め方法（及び該方法を実施する回路網）を、第１図に示す描画的な無線パケットホッピング回路網１０を参照して以下に詳細に説明するが、第１図は本発明を単純かつ容易に説明するよう描かれている。回路網１０は、複数の個別ノード１２と、ビルコンピュータ（「中央ノード」）１４とからなっている。各ノード１２は、ＲＦ送受信器１６と、壁ユニット１８と、メモリ（例えば、ＥＥＰＲＯＭ及び／又はＲＡＭ）及び１以上のカウンタを含むデジタル信号処理回路（例えば、マイクロプロセッサ）２０とを含んでいる。壁ユニット１８は、当業者に既知の如何なる便利な形式なものでもよく、例えば、結合されたバラスト又は照明器具２２（例えば、調光可能な蛍光ランプ）の照明レベルを制御するバラスト制御モジュールである。壁ユニット１８は、好ましくは、１以上の図示せぬセンサ（例えば、１以上の居住者状態、日光及び／又は調光／照明レベルセンサ）を含み、これらセンサはデジタル信号処理回路２０に対して帰還情報を供給し、該回路は上記センサ帰還情報をＲＦ送受信器１６によりビルコンピュータ１４へデータのパケットとして伝送すべく処理する。
ビルコンピュータ１４は、各ノード１２から受信されるセンサ帰還情報に基づき、且つ、該コンピュータに在住する照明制御ソフトウェアに従って、制御データを発生し、該制御データはデータのパケットとして各ノード１２へ送信される。この制御データは、次いで、各ノード１２のデジタル信号処理回路２０により処理されて各壁ユニット１８に供給される。これに対して、各壁ユニット１８は、必要に応じて、対応するバラスト２２の照明レベルを調整するための制御信号を生成する。
今考えられている回路網では、個々の壁ユニット１８は、対応するランプ２２の照明レベルを制御すべく（例えば、ビル居住者により）個別にプログラム可能となっている。この回路網では、ビルコンピュータ１４は当該ビルコンピュータ１４にロードされた照明システム制御ソフトウェアに従って、壁ユニット１８のプログラムされた設定を回路網１０を介して書き替える。勿論、当業者は、本発明の経路決め方法が使用される回路網の編成、立体構成及び／又は型式が本発明を限定するものではないことは容易に判るであろう。
第１図を続けて参照して、本質的に当該回路網１０における全データ通行はビルコンピュータ１４と各ノード１２との間、又はその逆の間に向けられる。ビルコンピュータ１４により各ノード１２へ送信されるデータパケットは、通常、「命令」データパケットと呼ばれ、各ノード１２によりビルコンピュータ１４に送信されるデータパケットは、通常、「確認」データパケットと呼ばれる。そのようであるので、送り手ノード及び受信ノードの両方のアドレスを各データパケットに含めるのとは反対に、命令データパケットが送信されるノードのアドレスを命令及び確認の両データパケットに含めることのみが必要である。何故なら、送り手ノードのアドレスは与えられているからである（即ち、これは常にビルコンピュータ１４であるからである）。言い換えると、各ノード１２は、確認データパケットの送り元の如何に拘わらず、全ての確認データパケットはビルコンピュータ１４に返送するようプログラムされる。このようにして、送信されるデータパケットの長さは短くすることができ、これにより当該回路網１０のデータ伝送処理能力及び通信効率は上昇する。群及びグローバルアドレス指定は付加的アドレスで以てなされる。先に述べたように、又以下に詳細に説明するように、各ノードにアドレステーブルを維持することにより、最大限の回路網効率が得られるようデータパケットの長さを更に減少させることができる。
本発明の例示的な実施例では、各命令データパケットはアドレスバイトＡＤＤＲ、パケットＩＤバイト、命令指示バイトＣＭＤ、命令データバイトＣＭＤ＿ＤＡＴＡ、及びチェックサムバイトＣＨＫＳＵＭを含んでいる。上記パケットＩＤバイトは、ノード１２及びビルコンピュータ１４に当該データパケットのアイデンティティを決定することを可能にするようなパケット識別コードを含んでいる。上記チェックサムバイトは当該データパケット中の２進値「１」（又は「０」）の合計数を示し、これにより受信ノードに当該データパケットの有効性を「チェック」することを可能にする。この点に関して言うと、無効なデータパケットは捨てられる。勿論、パケットの上記特定のデータ構造は本発明を限定するものではなく、説明のみの目的で記載されたものである。通常、バイト単位の通信によれば、ＲＳ２３２標準のような既存の通信システムと互換性のある既存の直列通信規格の使用が可能となり、これにより当該回路網通信手順及びハードウェア要件が簡素化される。
当該回路網１０中の多くのノード１２がビルコンピュータ１４の実効伝送範囲外にあるか、又はその逆であることが容易に分かるであろう。この点に関して言うと、或るノード１２は、ビルコンピュータ１４から有効な又は崩れていないデータを受信することが不可能な場合に、ビルコンピュータ１４の実効伝送範囲の外側にある（及びその逆）とみなされる。このように、ビルコンピュータ１４とデータパケットを送信したい宛先ノードとの間の各ノードは、上記ビルコンピュータ１４と上記宛先ノードとの間の通信経路に沿って上記データパケットをリレー又はホップさせるようにプログラムされねばならない。前述したように、データパケットをリレー又は中継するようにプログラムされたノードは、通常、中継器ノード（又は、単に「中継器」）と呼ばれる。
従来のランダムパケット経路決め手順によれば、全ノードが他の全ノードに対して中継器とし働くようプログラムされ、これによりビルコンピュータ１４と或る宛先ノードとの間に多数のランダム通信経路が設けられた。従来の確定的パケット経路決め手順では、ビルコンピュータ１４と或る宛先ノードとの間に単一の通信経路を形成する唯一の特定の組のノードだけが、データパケットを上記宛先ノードにリレーするための中継器として働くようプログラムされ、これによりビルコンピュータ１４と上記宛先ノードとの間に単一の所定の通信経路が設けられた。
本発明によれば、ビルコンピュータ１４と宛先ノードとの間の特定の組のノードであって、これらビルコンピュータ１４と宛先ノードとの間に複数の経路を形成し、且つ、当該宛先ノードに対して有効な中継器として働くことができるような特定の組のノードが、当該宛先ノードに対する中継器として働くようプログラムされ、これによりビルコンピュータ１４と前記宛先ノードとの間に複数の（２以上の）所定の通信経路を設ける。好ましくは、ビルコンピュータ１４の実効伝送範囲の外側にある（もっと広くは、ビルコンピュータ１４に直接接続されていない）各ノード１２に対して、ビルコンピュータ１４と当該ノードとの間に複数の経路を形成するような特定の組のノードが、当該ノード用の中継器として働くようプログラムされ、これによりビルコンピュータ１４と該コンピュータの実効伝送範囲外の（又はビルコンピュータ１４に直接結合されていない）各ノードとの間に複数の、所定の通信経路を設ける。
動作中においては、データパケットは、ビルコンピュータ１４と、当該ビルコンピュータ１４に直接結合されていない各ノード１２との間で、上記ビルコンピュータ１４と当該ノードとの間の予めプログラムされた複数経路に沿ってランダムに伝送されることにより通信される。この点について言うと、当該回路網１０中の全データ通信に関し、伝送されるデータパケットの不可避的な衝突の確率を最小化するために、チャンネルアクセス手順が使用される。好ましくは、キャリアセンス多重アクセス（ＣＳＭＡ）手順が使用され、該手順においては各中継器はランダムな遅延時間だけ待ち、次いで、データパケットの送信を試みる前に、当該チャンネルを感知して該チャンネルが利用可能（「クリア」）か又は利用不可能（「ビジー」）であるかを決定する。当該中継器がチャンネルがクリアであることを感知した場合は、該中継器は上記データパケットを送信する。当該中継器がチャンネルがビジーであることを感知した場合は、該中継器は上記データパケットを送信しようとして当該チャンネルを再び感知する前にもう一度ランダムな遅延時間だけ待つ。送信のための空きチャンネルを待っている如何なるノードも、パケットを受信することはできない。上記ランダムな遅延時間は、典型的には、送信機及び受信機の初期化時間を含みパケット伝送時間の０〜３倍の間である。長い遅延を許容すると、パケットの伝搬が遅くなるが、送信機のパワーアップと隣接するノードが実際に送信を「聴取」する時間との間の遅れによりデータパケットの不可避な衝突の確率は最小化する。勿論、使用される上記特別なチャンネルアクセス制御は本発明を限定するものではない。
ビルコンピュータ１４は、当該ビルコンピュータの実効伝送範囲外にある各ノード１２に対して中継器として働くべきノードを、該ビルコンピュータが回路網初期化過程の間に得るノードの接続度情報に基づいて、選択し及びプログラムする。使用される当該特定の回路網初期化ルーチンは本発明を限定するものではない。好ましくは、本発明者の名前で１９９５年１２月２７日に出願され、本発明の出願人に譲渡された米国特許出願第０８／５７９６５０号に開示されている自動回路網初期化方法が使用され、この開示内容は本出願において参考文献として引用する。この自動回路網初期化方法を使用することにより、当該ビルコンピュータ１４は、接続されているとみなされる各対のノードの間のリンクの品質に関する統計的情報、双方向ノードリンクの確認及び回路網１０内の各ノード１２の当該回路網１０内の全ての他のノード１２に対する全接続度を含む当該回路網１０に関する完全なノード接続度情報を収集することができる。
本発明によれば、ビルコンピュータ１４は、当該ビルコンピュータ１４と該ビルコンピュータ１４に直接結合されていない各ノードとの間のどの特定の組のノードを当該回路網の初期化過程中に得られたノード接続度情報に基づいて当該ノードに対する中継器として選択するかを決定する。更に詳述すると、或るノードに対して中継器として働くよう選択されたノードは、好ましくは、ビルコンピュータ１４と当該ノードとの間にデータパケットの伝送にとって最も効率的な経路であるような複数の通信経路を形成し、且つ、ビルコンピュータ１４と当該ノードとの間のデータ伝送の成功の確率を最大にするようなノードである。この点について言うと、付加的な初期化の実行及び／又は加算計数的初期化を、追加の経路を形成し、且つ、どの経路が最も効率的であるかを正確に決定すべく実行することができる。更に、前述したように、中央ノードと或る個別のノードとの間の複数経路をプログラムする場合、当該複数経路の各脚に対する中継器として選択された各ノードは、好ましくは、共通セルに位置するようにし、かくして、これらノードは互いに「聴取」することができ、これにより上記中央ノードと上記或る個別のノードとの間で通信されたデータパケットの解決不能な衝突のような事態を最小化する。
多数のプログラムされた経路を設けることにより、成功する通信の確率は上昇するが、或る程度で、成功する通信の確率の漸増的増加より、当該回路網１０のデータ伝送処理能力の低下の方が勝るようになる、即ち、「見返りが無くなる」点に到達する。或る場合には（当該回路網の特定の立体構成及び／又は編成に依存して）、プログラムされた経路の数が多すぎて、成功する通信の確率が差し引きで減少する結果となるか、又は当該回路網１０のデータ伝送処理能力が所望のしきいレベルよりも低下する。全てのノードが当該回路網中の他の全てのノードに対する中継器として働くようプログラムされたような極端な場合は、回路網経路決め手順は、従来の完全なランダム（即ち、完全な非確定的）経路決め手順となる。このように、成功する通信の確率と回路網１０のデータ伝送処理能力（即ち、回路網１０上に同時にのせることができる異なるパケットの数）との間には取り引きがある。
このように、本発明の部分的に確定的で部分的にランダムな経路決め方法、並びにその利点及び効果を実現するには、中継器として働くようプログラムされたノードの各々は、当該回路網中の少なくとも１個の、しかし全てではない他のノードに対する中継器として働くようプログラムされる。本発明のランダム複数経路テーブル式経路決め方法によれば、全ノードを当該回路網中の少なくとも１個の他のノードに対する中継器として働くようプログラムすることが可能であるが、全ノードを当該回路網中の他の全てのノードに対する中継器として働くようプログラムすることはできない。通常、或るノードに対して最も効率的な中継器として働くことができるノードのみが、当該ノードのための中継器として働くようプログラムされる。更に、１個以上の他のノードに対して中継器として働くようプログラムされたノードの合計数Ｍは、当該回路網中のノードの合計数Ｎよりも少ない（即ち、Ｍ＜Ｎ）。
前述したように、特定のノードは、当該ノードが中継器として働くための各ノードのアドレスを当該ノードの「中継」アドレステーブル中に単に記憶することにより中継器として働くようプログラムされる。中継器として働くべき全ノードをこのようにしてプログラムすることにより、ビルコンピュータと当該ビルコンピュータに直接結合されていない各ノードとの間の所定の複数経路がプログラムされる。勿論、前述したように、上記のように選択された特定の各経路は、ビルコンピュータと当該ビルコンピュータにより直接到達することができない各ノードとの間でデータパケットを行ったり来たりホップさせるに最も効率的な経路を提供するようなものであることが好ましい。
動作時には、ビルコンピュータ１４に直接結合されていない宛先ノードに送られるべき命令データパケットは、当該ビルコンピュータ１４により送信される。この場合、当該ビルコンピュータ１４の伝送範囲内にある全ノードが上記パケットを受信し、該パケットのＡＤＤＲバイトに含まれるアドレス（これは前記宛先ノードのアドレスである）を、もしあるなら、それらの「中継」アドレステーブルに記憶された各アドレスと比較する。勿論、上記のアドレス指定された宛先ノードに対して中継器として働くようプログラムされている各ノードは、一致を検出するであろう。このような各中継器は、次いで、ランダムな遅延期間だけ待った後、ＣＳＭＡ手順に従って当該回路網１０の共通ＲＦチャンネルがクリアの場合に、当該パケットをその伝送範囲内の全ノードに向けて送信する。特に言及しない限り、このような中継器の各々は当該パケットを「中継」する。前記宛先ノードが当該パケットを受信すると、ビルコンピュータ１４から上記アドレス指定された宛先ノードへの前記命令データパケットの送信は成功裏に完了する。この点に関して言うと、上記パケットを受信する各ノードは、当該パケットのＡＤＤＲバイトに含まれるアドレスを、その「応答」テーブル内に記憶されたアドレスと比較する。勿論、前記宛先ノードのみが一致を検出する。
しかしながら、もしビルコンピュータ１４と宛先ノードとの間の前記のプログラムされた複数経路に１以上の付加的な「脚」（又は「リンク」）がある場合は（即ち、前記のアドレス指定された宛先ノードが当該経路の最初の脚に対する中継器の伝送範囲の外にある場合は）、前記ビルコンピュータ１４と宛先ノードとの間の前記のプログラムされた複数経路の付加的な各脚に対する中継器が、上記宛先ノードが当該パケットを受信するまで、上述したのと同様のやり方で当該パケットを「中継」し、これによりビルコンピュータ１４から前記アドレス指定された宛先ノードへの命令パケットの送信は成功裏に完了する。
幾つかの場合には、前記宛先ノードは１以上の付加的な脚がある場合でさえも前記のプログラムされた複数経路の最初の脚に対する（各）中継器の伝送範囲内にあるかも知れず、その場合には前記宛先ノードは、上記付加的な脚に対する（各）中継器が当該パケットを中継する前に、該パケットを受信し、これにより上記付加的な（各）脚に対する中間の中継器を効果的にバイパス又は飛び越え、これにより送信を成功裏に完了するに要する時間が減少することに注意されたい。時には「ホップ−スコッチング」と呼ばれるこの現象は、ＣＳＭＡ手順により扱われ、該手順は前記のプログラムされた複数経路を介するパケットの経路決めの十分なランダムさを保証し、何れの方向においてもデータパケットの解決不能な衝突という事態を最小にする。
宛先ノードがパケットを受信すると、該ノードは当該パケットのＣＭＤバイトに含まれる前記命令を実行し、もしそうするように命令されたなら（又は、そうしないように命令されるか若しくはプログラムされない限り）、同一のプログラムされた複数経路に沿ってビルコンピュータ１４に返送するための確認パケットを形成する。この確認パケットの前記ビルコンピュータ１４へ戻る経路決めは、逆の順序であることを除いて、ビルコンピュータ１４から宛先ノードへの命令パケットの経路決めに関して上述したのと同一である。先に説明した理由により、返送される確認パケットのＡＤＤＲバイトに含まれるアドレスは上記命令パケットのＡＤＤＲバイトに含まれるアドレス（即ち、宛先ノードのアドレス）と同一であるのが有利であるが、該確認パケットのパケットＩＤは上記命令パケットのものとは異なることに注意されたい。上記命令パケット及び確認パケットがたどる実際の経路は前記のプログラムされた複数経路のうちのランダムなものであることは理解されるであろう。
時には「バックラッシュ」と呼ばれる、プログラムされた経路に沿い反対方向に（命令データパケットの場合は、ビルコンピュータに戻る方向に）パケットがホップするのを防止するために、パケットを既に中継した各ノードは該パケットのＩＤをメモリ中に記録し、これにより、もし該パケットが当該ノードにより再び受信された場合は、該パケットは該ノードによっては再送信（再中継）されないようにする。これに関して言うと、本発明の好ましい実施例においては、２つの以前に送信されたパケットのパケットＩＤの継続的な記憶を可能にすべく２バイトの循環式（ＦＩＦＯ）パケットＩＤバッファが設けられ、これにより上記２つの以前に送信されたパケットの何れもが「再中継」されることがないようにする。勿論、使用されるバッファの寸法及び型式は本発明を限定するものではない。
ビルコンピュータ１４に直接結合されていない宛先ノード群に送られるべき命令データパケットは、この宛先ノード群へ同様のやり方で経路決めされる。更に詳細には、ビルコンピュータ１４の伝送範囲内にある全てのノードが上記パケットを受信し、当該パケットのＡＤＤＲバイトに含まれる群アドレス（このアドレスは宛先ノード群のアドレスである）を、もしあるなら、それらの「中継」アドレステーブル内に記憶されたアドレスと比較する。勿論、上記のアドレス指定されたノード群のために中継器として働くようプログラムされている各ノードは一致を検出するであろう。このような「群」中継器は、次いで、ランダムな遅延期間だけ待った後、ＣＳＭＡ手順に従って当該回路網１０の共通ＲＦチャンネルがクリアの場合に、当該パケットをその伝送範囲内の全ノードに向けて送信する。特に言及しない限り、上記のような各「群」中継器は当該パケットを「中継」する。もし、上記のアドレス指定されたノード群内の各ノードが上記パケットを受信すると、ビルコンピュータ１４から上記のアドレスされた宛先群への命令パケットの送信は成功裏に完了する。この点に関して言うと、上記パケットを受信する各ノードは、当該パケットのＡＤＤＲバイトに含まれるアドレスを、その「応答」テーブル内に記憶された（各）アドレスと比較する。勿論、前記アドレス指定された宛先群内のノードのみが一致を検出するであろう。
しかしながら、もしビルコンピュータ１４と宛先ノード群との間の前記のプログラムされた複数経路に１以上の付加的な「脚」がある場合は（即ち、前記のアドレス指定された宛先ノードが当該経路の最初の脚に対する中継器の伝送範囲の外にある場合は）、前記ビルコンピュータ１４と宛先ノード群との間の前記のプログラムされた複数経路の付加的な各脚に対する「群」中継器は、上記宛先群の各ノードが当該パケットを受信するまで、上述したのと同様のやり方で当該パケットを「中継」し、これによりビルコンピュータ１４から前記アドレス指定された宛先ノード群への命令パケットの送信は成功裏に完了する。
上記宛先ノード群内の各ノードは、次いで、もしそのように命令されているなら（又は、そのようにしないと命令若しくはプログラムされていない限り）、確認パケットを形成し、前記と同一のプログラムされた複数経路に沿ってビルコンピュータ１４に戻るよう送信する。ビルコンピュータ１４に戻る確認パケットの経路決めは、ビルコンピュータ１４から前記宛先ノード群への命令パケットの経路決めに関して述べたのと、逆の順序であることを除いて、同様である。群中継器として働くような前記アドレス指定された群に属する群中継器ノードは、パケットの中継及びパケットへの応答の両方を行う必要があることに注意されたい。この点に関して言うと、もし或る群中継器が、該中継器が属する群に向けられたパケットに応答して確認パケットを返送するよう命令又はプログラムされている場合は、当該群中継器は先ず当該パケットを中継し、次いで（適切な遅延の後）上記確認パケットを形成し、返送するのが好ましい。尚、この手順は本発明を限定するものではない。
当該回路網１０内の全ノード１２に送られるべき命令データパケットは以下のように経路決めされる。即ち、ビルコンピュータ１４の伝送範囲内にある全ノードは当該パケットを受信し、当該パケットのＡＤＤＲバイトに含まれるグローバルアドレスを、もしあるなら、それらの「中継」アドレステーブル内に記憶された（各）アドレスと比較する。勿論、全回路網１０に対して「グローバル」中継器として働くようプログラムされている各ノードは一致を検出する。このような各「グローバル」中継器は、次いで、ランダムな遅延期間だけ待った後、ＣＳＭＡ手順に従って当該回路網１０の共通ＲＦチャンネルがクリアの場合に、当該パケットを、その伝送範囲内の全ノードに向けて送信する。特に言及しない限り、上記のような各「グローバル」中継器は上記パケットを「中継」する。「グローバル」中継器の最初の組により送信されたパケットを受信する各「グローバル」中継器も、当該パケットを中継する。当該回路網１０中の全ノード１２が一旦パケットを受信すれば、当該通信は成功裏に完了する。この点について言うと、上記パケットを受信する各ノードは、当該パケットのＡＤＤＲバイトに含まれるアドレスを、その「応答」テーブル内に記憶された（各）アドレスと比較する。勿論、この場合、当該回路網１０中の全ノード１２は一致を検出する。
グローバルにアドレス指定された命令パケットの受信の後、当該回路網１０内の各ノードは、次いで、もしそのように命令されているなら（又は、そのようにしないと命令若しくはプログラムされていない限り）、確認パケットを形成し、前記と同じプログラムされた複数経路に沿ってビルコンピュータ１４に戻るよう送信する。上記確認パケットのビルコンピュータ１４へ戻す経路決めは、逆の順序であることを除いて、ビルコンピュータ１４から当該回路網１０内の全ノード１２へ向けての命令パケットの経路決めに関して上述したのと同様である。
上記グローバル中継器ノードは、パケットの中継及びパケットへの応答の両方を行う必要があることに注意されたい。この点に関して言うと、もし或るグローバル中継器が、グローバルにアドレス指定されたパケットに応答して確認パケットを返送するよう命令又はプログラムされている場合は、当該グローバル中継器は先ず当該パケットを中継し、次いで（適切な遅延の後）上記確認パケットを形成し、返送するのが好ましい。尚、この手順は本発明を限定するものではない。更に、データパケットの不可避的な衝突を最小化し、且つ、当該回路網１０の前記確認パケットによる支配（及び、それに付随する回路網データ伝送処理能力の低下）を防止するために、アドレス指定された群（グローバル群を含む）内のノード１２のうちの選択されたものだけが、群（又はグローバル）アドレスを含む命令パケットに応答して確認パケットを返送するようプログラムされるのが好ましい。
従来の純粋に確定的単一経路式経路決め方法に対し、本発明のランダム複数経路テーブル式経路決め方法を用いた無線パケットホッピング回路網でのデータパケットの成功通信の確率の上昇を説明するため、第２図を参照する。
即ち、第２図のＡ、Ｂ及びＣは、パケットがノードＡからノードＤへ送信され、及びノードＤからノードＡへ戻る（即ち、Ａ→Ｄ→Ａ）ような３つの異なる場合を図示し、Ａは従来の純粋に確定的経路決め方法を用いて単一の経路Ａ→Ｂ→Ｃ→Ｄに沿う場合である。この場合、ノードＡとＤとの間のノードＢ及びＣは中継器として働く。又、ノードＡとＤとの間の通信経路における最初のリンクは「リンク１」と呼び、ノードＡとＤとの間の通信経路における２番目のリンクは「リンク２」と呼び、ノードＡとＤとの間の通信経路における３番目のリンクは「リンク３」と呼ぶ。
説明を簡単且つ容易にするため、何れの２つの結合されたノードの間の通信の成功の確率は０．９０（９０％）であると仮定する。勿論、前述したように、何れの２つの結合されたノードの間の通信の成功の実際の確率は、種々の制御不可能な変数により（例えば、屋内環境の動的変化、フェージング、マルチパス等により）時間の関数として変化する。しかしながら、各リンクに固定した成功の確率を割当てることにより、当該解析を、該解析の有効性に大きな影響を与えることなく単純化することができる。
第２図のＡは、従来の純粋に確定的経路決め方法を用いて単一の経路Ａ→Ｂ→Ｃ→Ｄに沿って、パケットがノードＡからノードＤへ送信され、及びノードＤからノードＡへ戻る（即ち、Ａ→Ｄ→Ａ）場合を図示し、ここで、ノードＡとＤとの間のノードＢ及びＣは中継器として働く。通信Ａ→Ｄ→Ａが成功するように、当該パケットはノードをＡ→Ｂ→Ｃ→Ｄ→Ｃ→Ｂ→Ａのようにホップしなければならず、結果として、当該通信Ａ→Ｄ→Ａが成功する確率は（０．９）６＝０．５３（５３％）となる。
第２図のＢは、本発明のランダム複数経路テーブル式経路決め方法に従い、通信経路Ａ→Ｂ→Ｃ→Ｄ又はＡ→Ｅ→Ｃ→Ｄの何れかに沿って、パケットがノードＡからノードＤへ送信され、及びノードＤからノードＡへ戻る（即ち、Ａ→Ｄ→Ａ）場合を図示し、ここで、ノードＢ及びＣ並びにノードＥは両方ともノードＤに対する中継器として働く。これにより、リンク１及びリンク２に関する成功の確率は０．９０から０．９９へ上昇し、この結果、当該通信Ａ→Ｄ→Ａが成功する確率は１−（１−０．９）２）4＊０．９2＝０．７８（７８％）となる。このように、第２図のＡの例に対して、通信Ａ→Ｄ→Ａの成功の確率の４７％の上昇が実現される。何故なら、リンク１を完成させるにはノード対ノード接続Ａ→Ｂ又はノード対ノード接続Ａ→Ｅのみが成功すればよく、これにより該リンクの成功率は９９％に上昇し、更に、リンク２を完成させるにはノード対ノード接続Ｂ→Ｃ又はノード対ノード接続Ｅ→Ｃのみが成功すればよく、これにより該リンクの成功率は９９％に上昇するからである。
第２図のＣは、本発明のランダム複数経路テーブル式経路決め方法に従い、通信経路Ａ→Ｂ→Ｃ→Ｄ、Ａ→Ｅ→Ｃ→Ｄ、Ａ→Ｂ→Ｆ→Ｄ又はＡ→Ｅ→Ｆ→Ｄの何れかに沿って、パケットがノードＡからノードＤへ送信され、及びノードＤからノードＡへ戻る（即ち、Ａ→Ｄ→Ａ）場合を図示し、ここで、ノードＢ、Ｃ、Ｅ及びＦはノードＤに対する中継器として働く。これにより、リンク１に関する成功の確率は０．９０から０．９９へ上昇し、リンク２に関する成功の確率は０．９９９９へ上昇し、リンク３に関する成功の確率は０．９９へ上昇し、この結果、当該通信Ａ→Ｄ→Ａが成功する確率は０．９６（９６％）となる。このように、第２図のＡの例に対して、通信Ａ→Ｄ→Ａの成功の確率の８１％の上昇が実現される。何故なら、リンク１を完成させるにはノード対ノード接続Ａ→Ｂ又はノード対ノード接続Ａ→Ｅのみが成功すればよく、これにより該リンクの成功率は９９％に上昇し、更に、リンク２を完成させるにはノード対ノード接続Ｂ→Ｃ、Ｅ→Ｃ、Ｅ→Ｆ又はＢ→Ｆのうちの一つのみが成功すればよく、これにより該リンクの成功率は９９．９９％に上昇し、更に、リンク３を完成させるにはノード対ノード接続Ｃ→Ｄ又はノード対ノード接続Ｆ→Ｄの何れかのみが成功すればよいからである。簡素化及び明瞭化のために、これらの例では「ホップ−スコッチング」の可能性は考慮されておらず、この可能性は当該通信Ａ→Ｄ→Ａが成功する確率を更に改善する結果となる。
上記及び前記記載に基づき、本発明によるランダム複数経路テーブル式経路決め方法は、現在知られている確定的及びランダム経路決め方法に較べて、これらに限定されるものではないが下記に番号を付したような多くの利点及び効果を提供することができる。
即ち、本発明によるランダム複数経路テーブル式経路決め方法によれば：
（１）十分な数及び品質の複数の経路がプログラムされていさえすれば、回路網内の一時的な障害により応答しない各ノードに対し、積極的な経路再編成又は再編成アルゴリズムは必要とされない；
（２）複数の送信により、予めプログラムされた全ての可能性のある経路が、再編成を要せずに、試されることが保証される；
（３）再編成は、他のノードを中継器として働くようプログラムする程度に簡単であり、以前にプログラムされた経路を除去する必要がなく、これにより、新たな経路が失敗しても以前の経路に戻すよう再編成する必要がない；
（４）再編成は、付加的な及び／又は加算計数的な自動初期化ルーチンを実行するか、及び／又は最初の（又は以前の）初期化ルーチンで得られた接続度の情報に基づいて１以上の付加的なノードを中継器として働くよう手動でプログラムすることにより、なすことができる；
（５）各ノードは中継する必要がある（各）ノードの（各）アドレスを記憶するのみでよいから、前記部分的経路決めテーブル（又は、単に「経路決めテーブル」）がコンパクトである。
（６）上記経路決めテーブルは各ノードに記憶されるから、パケットは該経路決め情報を含む必要がなく、これにより短いパケットの伝送が可能となり、従って回路網効率が改善されると共に当該回路網のハードウェア要件が緩和される（例えば、パケットバッファの大きさ及びボーレート等）；
（７）各ノードは一時に一つのパケットを扱うのみでよいから、複数のパケットバッファは必要とされない（即ち、単一のパケットバッファのみが必要とされる）；
（８）本発明のランダム複数経路テーブル式経路決め方法によれば、従来の純粋にランダムな経路決め方法の利点及び効果（即ち、通信の成功の高確率）及び従来の純粋に確定的な経路決め方法の利点及び効果（即ち、回路網の高データ伝送処理能力）の両方が実現され、それと同時に、これら従来の経路決め方法の欠点及び問題点を除去することができる。
本発明の種々の好ましい実施例を上述したが、当業者が想到するであろう、ここに教示した本発明の基本思想の種々の変形及び変更は、添付請求の範囲に規定された本発明の範囲内であることを明確に理解されたい。
【図１】
0003897816.tif 000002
【図２】
0003897816.tif 000003