(57)【要約】  本発明は、通信ネットワークの動作方法に関し、このネットワークは、互いにデータを送信しデータを受信することができる複数の局を備えている。本方法は、プローブ信号の他の局への送信のために第１プローブ・チャネルを既定することを含む。探査局からの第１プローブ信号を受信した他の局は、探査局にその宛先又は中間局としての可用性を示す。これら他の利用可能な局の詳細を備えた近隣表を各局において維持する。また、第２プローブ信号を送り、近隣表内にある局から受信し、各近隣局との通信を行うコストに関するデータを備えた傾斜表を各局において維持することにより、各局が、最小コストでも発信局から宛先局への以降の送信のために、所定数の中間局を選択可能とする。
2007519320.tif 000002
【特許請求の範囲】
【請求項１】
複数の局を備えており、各局が、データを送信及び受信することができる通信ネットワークであって、少なくとも１つの適時選択した中間局を介して発信局から宛先局にデータを送信することを可能としている通信ネットワークにおける動作方法であって、
ａ）少なくとも１つのデータ・チャネルとは別個の、少なくとも１つのプローブ・チャネルを規定するステップと、
ｂ）各局において、第１の所定の判断基準に応じて、プローブ信号の他の局への送信のために、プローブ・チャネルを選択するステップと、
ｃ）前記選択したプローブ・チャネル上において各局から第１プローブ信号を送信し、前記第１プローブ信号を探査局から受信した別の局が直接又は間接的に応答することによって、前記探査局にその宛先又は中間局としての可用性を示すステップと、
ｄ）各局において、ステップ（ｃ）によって識別した他の利用可能な局の詳細を備えた近隣表を維持するステップと、
ｅ）近隣局ではない宛先局にデータを送る必要がある局から、第２プローブ信号を、前記近隣表内にある局に送信し、当該局から第２プローブ信号を受信するステップと、
ｆ）必要に応じて、各局において、近隣局ではない各宛先局と通信するコストに関するデータを備えた傾斜表を維持するステップと、
を備えており、各局が、最小コストで発信局から宛先局への以降の送信のために、所定数の中間局を選択可能とすることを特徴とする方法。
【請求項２】
請求項１記載の方法において、ステップ（ｃ）によって識別された他の利用可能局の詳細は、経路損失、及び前記他の利用可能な局に到達するのに必要な電力を含むことを特徴とする方法。
【請求項３】
請求項１又は請求項２記載の方法において、前記第２プローブ信号は、前記局の近隣表がエントリを収容している間のみ、各局から送信されることを特徴とする方法。
【請求項４】
請求項１〜３いずれかに記載の方法において、前記方法は更に、前記近隣表における局毎に、発信局から宛先局まで前記近隣表内にあるかかる各局を経由してメッセージを送信するコストについて、宛先コスト値を計算するステップを含むことを特徴とする方法。
【請求項５】
請求項１〜４いずれかに記載の方法において、各局は、それ自体の宛先コスト値の一時的記録も維持することを特徴とする方法。
【請求項６】
請求項４又は請求項５記載の方法において、前記宛先コスト値は、前記近隣表におけるかかる各局及び任意の中間局を経由して、前記発信局から前記宛先局にメッセージを送信する累積コストであることを特徴とする方法。
【請求項７】
請求項４〜６いずれかに記載の方法において、前記方法は更に、局がそれら自体の計算において、他の局の古い宛先コスト値を用いるのを防止するために、他の局がそれらの宛先コスト値を更新できる期間だけ、局毎に計算した宛先コスト値を一定に維持するステップを含むことを特徴とする方法。
【請求項８】
各々がデータを送信及び受信することができる複数のクライアント局を備えている通信ネットワークであって、少なくとも１つの適時選択した中間クライアント局を介して発信クライアント局から宛先クライアント局に複数のデータ・パケットから成るメッセージを前記ネットワークが送信することを可能とし、更に、前記ネットワークは、
クライアント局に対して、ネットワークへのアクセス・ポイントとして機能するように配置された複数のゲートウェイと、
クライアント局が通信することができる複数のシード局であって、各々少なくとも１つのゲートウェイと通信状態にあり、クライアント局の有効接続範囲を広げる、複数のシード局と、
クライアント局を監視する少なくとも１つの加入者ネットワーク管理部と、
を備えており、
各クライアント局は、
ａ）少なくとも１つのデータ・チャネルとは別個の、少なくとも１つのプローブ・チャネルを規定し、
ｂ）各クライアント局において、プローブ信号の他のクライアント局への送信のために、プローブ・チャネルを選択し、
ｃ）前記選択したプローブ・チャネル上において各クライアント局から第１プローブ信号を送信し、前記第１プローブ信号を探査クライアント局から受信した別の局が直接又は間接的に応答することによって、前記探査局にその宛先又は中間クライアント局としての可用性を示し、
ｄ）各クライアント局において、ステップ（ｃ）によって識別した他の利用可能な局の詳細を備えた近隣表を維持し、
ｅ）近隣クライアント局ではない宛先クライアント局にデータを送る必要があるクライアント局から、第２プローブ信号を、前記近隣表内にあるクライアント局に送信し、当該クライアント局から第２プローブ信号を受信し、
ｆ）必要に応じて、各クライアント局において、各近隣クライアント局と通信するコストに関するデータを備えた傾斜表を維持する
ように構成されており、
これによって、各クライアント局が、最小コストでも発信クライアント局から宛先クライアント局への以降の送信のために、所定数の中間クライアント局を選択可能とすることを特徴とする通信ネットワーク。
【請求項９】
請求項８記載の通信ネットワークにおいて、各クライアント局は更に、ステップ（ｃ）によって識別された他の利用可能局の詳細に、経路損失、及び前記他の利用可能な局に到達するのに必要な電力を含むように構成されていることを特徴とする通信ネットワーク。
【請求項１０】
請求項８又は請求項９記載の通信システムにおいて、各クライアント局は更に、前記局の近隣表がエントリを収容している間のみ、各局から第２プローブ信号を送信する送信機を含むことを特徴とする通信システム。
【請求項１１】
請求項８〜１０いずれかに記載の通信システムにおいて、各クライアント局は、前記近隣表における局毎に、発信局から宛先局まで前記近隣表内にあるかかる各局を経由してメッセージを送信するコストについて、宛先コスト値を計算するコントローラを含むことを特徴とする通信システム。
【請求項１２】
請求項８〜１１いずれかに記載の通信システムにおいて、各局は、それ自体の宛先コスト値の一時的記録を維持するメモリを含むことを特徴とする通信システム。
【請求項１３】
請求項１１又は請求項１２記載の通信システムにおいて、該システムは、局がそれら自体の計算において、他の局の古い宛先コスト値を用いるのを防止するために、他の局がそれらの宛先コスト値を更新できる期間だけ、局毎に計算した宛先コスト値を一定に維持するように構成されていることを特徴とする通信システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、国際特許出願第ＷＯ９６／１９８８７号及び第ＷＯ９８／５６１４０号に記載されている一般的な種類の多局（マルチステーション）通信ネットワークの動作方法に関する。本発明はまた、このようなネットワーク自体にも関連している。
【背景技術】
【０００２】
先に引用した種類のネットワークは、商業的に利用することができ、ユーザは加入者となり、彼らのネットワークの使用に対して料金を請求される。あるいは、この種のネットワークは、警察又は軍部というような公安権力によって利用される場合もある。
引用した種類のネットワークの更に別の用途は、ワイヤレス・ローカル・エリア・ネットワーク（ＷＬＡＮ）であり、この場合、ワイヤレス・ネットワークを従来のネットワーク構造と組み合わせて、固定及び移動ネットワーク・ユーザにサービスを提供することができる。このようなネットワークは、必然性はないが、通常コンピュータ・ネットワークである。
【発明の開示】
【０００３】
本発明によれば、複数の局を備えている通信ネットワークであって、各局がデータを送信及び受信することができる通信ネットワークの動作方法を提供し、少なくとも１つの適時選択した中間局を介して発信局から宛先局に複数のデータ・パケットから成るメッセージをネットワークが送信することを可能する。この方法は、
ａ）少なくとも１つのデータ・チャネルとは別個の、少なくとも１つのプローブ・チャネルを規定するステップと、
ｂ）各局において、第１の所定の判断基準に応じて、プローブ信号の他の局への送信のために、プローブ・チャネルを選択するステップと、
ｃ）選択したプローブ・チャネル上において各局から第１プローブ信号を送信し、第１プローブ信号を探査局から受信した別の局が直接又は間接的に応答することによって、探査局にその宛先又は中間局としての可用性を示すステップと、
ｄ）各局において、ステップ（ｃ）によって識別した他の利用可能な局の詳細を備えた近隣表を維持するステップと、
ｅ）近隣局ではない宛先局にデータを送る必要がある局から、第２プローブ信号を、近隣表内にある局に送信し、当該局から第２プローブ信号を受信するステップと、
ｆ）必要に応じて、各局において、近隣局ではない各宛先局と通信するコストに関するデータを備えた傾斜表を維持するステップと、
を備えており、これによって、各局が、最小コストでも発信局から宛先局への以降の送信のために、所定数の中間局を選択可能とする。
【０００４】
ステップ（ｃ）によって識別された他の利用可能局の詳細は、経路損失、及び他の利用可能な局に到達するのに必要な電力を含めるとよい。
好ましくは、第２プローブ信号は、局の近隣表がエントリを収容している間のみ、各局から送信する。
本方法は更に、近隣表における局毎に、発信局から宛先局まで近隣表内にあるかかる各局を経由してメッセージを送信するコストについて、宛先コスト値を計算するステップを含むこともできる。
好ましくは、各局は、それ自体の宛先コスト値の一時的記録も維持する。
好ましくは、宛先コスト値は、近隣表におけるそのような各局及びあらゆる中間局を経由して、発信局から宛先局にメッセージを送信する累積コストである。
好ましくは、本方法は更に、局がそれら自体の計算において、他の局の古い宛先コスト値を用いるのを防止するために、他の局がそれらの宛先コスト値を更新できる期間だけ、局毎に計算した宛先コスト値を一定に維持するステップを含む。
【０００５】
本発明の別の態様によれば、各々、データを送信及び受信することができる複数のクライアント局を備えている通信ネットワークを提供し、少なくとも１つの適時選択した中間クライアント局を介して発信クライアント局から宛先クライアント局に複数のデータ・パケットから成るメッセージをネットワークが送信することを可能とする。通信ネットワークは更に、
クライアント局に対して、ネットワークへのアクセス・ポイントとして機能するように配置された複数のゲートウェイと、
クライアント局が通信することができる複数のシード局であって、各々少なくとも１つのゲートウェイと通信状態にあり、クライアント局の有効接続範囲を広げる、複数のシード局と、
クライアント局を監視する少なくとも１つの加入者ネットワーク管理部と
を備えている。
各クライアント局は、
ａ）少なくとも１つのデータ・チャネルとは別個の、少なくとも１つのプローブ・チャネルを規定し、
ｂ）各クライアント局において、プローブ信号の他のクライアント局への送信のために、プローブ・チャネルを選択し、
ｃ）選択したプローブ・チャネル上において各クライアント局から第１プローブ信号を送信し、第１プローブ信号を探査クライアント局から受信した別の局が直接又は間接的に応答することによって、探査局にその宛先又は中間クライアント局としての可用性を示し、
ｄ）各クライアント局において、ステップ（ｃ）によって識別した他の利用可能な局の詳細を備えた近隣表を維持し、
ｅ）近隣クライアント局ではない宛先クライアント局にデータを送る必要があるクライアント局から、第２プローブ信号を、近隣表内にあるクライアント局に送信し、当該クライアント局から第２プローブ信号を受信し、
ｆ）必要に応じて、各クライアント局において、各近隣クライアント局と通信するコストに関するデータを備えた傾斜表を維持する
ように構成されており、これによって、各クライアント局が、最小コストでも発信クライアント局から宛先クライアント局への以降の送信のために、所定数の中間クライアント局を選択可能とする。
【発明を実施するための最良の形態】
【０００６】
本発明は、国際特許出願第ＷＯ９６／１９８８７号及び第ＷＯ９８／５６１４０号に記載されている一般的な種類の多局通信ネットワークの動作方法に関する。その内容は、ここで引用したことにより、本願にも含まれるものとする。端的に言うと、このようなネットワークの基本動作は、以下の通りである。
【０００７】
多局ネットワークは、多数の独立した局を備えており、これらは固定でも移動でもよく、その各々がデータを送信及び受信し、発信局から宛先局まで、場合によっては中間局を介してメッセージを送信することができる。発信局が数カ所の可能な中間局から選択した１つを通じて新たなメッセージを宛先局に送る位置にあるためには、各局は任意の時点においても常時数カ所の他の局と連絡が取れるようになっていなければならない。これは、局が発信局から宛先局にメッセージを中継するように要求される場合にも当てはまる。
【０００８】
これを行うために、各局は多数の可能なプローブ・チャネルから１つを選択し、プローブ信号を他の局に送信する。プローブ信号は、問題の局を特定するデータを収容し、他の局に対するその接続性の詳細を含む。プローブ信号を受信した他の局は、探査（プロービング）局に直接応答するか、又は中間局を介して間接的に応答することにより、探査局及びその他の局の双方に、その宛先又は中間局としての可用性を示す。探査局は、直接又は間接応答を評価して、最適に通信することができる他の局を特定する。
【０００９】
即ち、ネットワークの局は、他の局に到達するために必要な蓄積電力を監視することにより、他の局に対する電力傾斜(power gradient)を規定し、局は、発信局と、電力傾斜を最適化する宛先局との間で、ネットワークを通じて経路を選択する。これによって、ネットワークを通じたデータ・スループットを最大化することができ、局間の干渉や競合が最少となる。
【００１０】
ネットワークにおける各局は、範囲内にある他の任意の局に対してデータの受信及び送信が可能な送受信機を備えている。ネットワークは、前述の国際特許出願に記載されているような、パケット無線ネットワークとすることができるが、本発明は、ユーザ局がネットワークにおける中間局を通じて互いに通信することができる他のネットワークにも適用可能である。
ネットワークの局間における便宜的データ送信方法を、ここでは、機会駆動マルチ・アクセス（ＯＤＭＡ）と呼ぶ。
【００１１】
これより、８０２．１１ｂ規格に基づくＷＬＡＮシステムを参照しながら、本発明の一実施形態について説明する。このようなＷＬＡＮ構成の一例を、図１の模式図に示す。
図１において、第１及び第２ゲートウェイ１０及び１２は各々、通例ネットワーク・ユーザである多数の加入者ユニット（クライアント・デバイス）１４のために、ネットワークへのアクセス・ポイントとして機能する。この実施形態におけるクライアント・デバイスは、通常、ワイヤレス・ネットワーク・カードであり、それぞれのゲートウェイ１０及び１２と、直接又は他のクライアント・デバイスを通じて、ＯＤＭＡ技法を用いて通信することができる。加えて、ワイヤレス・ルータである、多数のシード・ステーション１６が計画的にゲートウェイ１０及び１２の付近に展開されている。シード・ステーションは、クライアント・デバイスの、特に異なる環境における接続性範囲を広げることによって、ネットワークのカバレッジ範囲及びスループットを効果的に拡大する。
【００１２】
ＯＤＭＡプロトコルは、ワイヤレス・リンク上で動作し、適時、データを加入者ユニット（クライアント・デバイス）とシード(seed)との間で、ローカル・エリア・ネットワークのような有線ネットワーク、ならびに図１に示すワイヤレス・バックホール(backhaul)又はファイバ・リンク１８及び２０を通じて中継する。局から局への中継には、有線及びワイヤレス・ホップ、ならびに図示のようにワイヤレス・バックホールを通じてホップを伴う場合がある。
ネットワークは、加入者から加入者に、そしてシードを通じて適時メッセージをゲートウェイに誘導し、次いで二点間リンクを通じてファイバに、そして別の領域に誘導する。
【００１３】
このように、ＯＤＭＡを用いて、種々の形式のネットワークを通じた国内及び国際的なネットワークが、メッセージを任意のユーザから他の任意のユーザに、世界の任意箇所において通信することを可能にする。ネットワークは、自動的に、メッセージ・パケットが辿る最適な経路を発見し、ネットワークを通過する代替経路を見つけることによって、負荷均衡及び破壊リンクの修復を行う。ＯＤＭＡネットワークにおける全てのユニットは、ＳＩＤ（システムＩＤ）と呼ばれる一意のアドレスを有する。
【００１４】
加入者ネットワーク・マネージャ２２は、ネットワークにおける種々の局の動作状態(health)を監視し、ネットワークのセキュリティ及び構築を管理する。
前述の例では、クライアント・デバイスはゲートウェイ１０及び１２と、直接、又はシード局１６を通じて、あるいは１つ以上の中間クライアント・デバイスを通じて、前述の国際特許出願に記載されているように、通信することができる。加えて、クライアント・デバイスは、瞬時的なピア・ツー・ピア・ネットワークを他の同様のデバイスとともに形成することができる。
【００１５】
この種の適時マルチホップ・ルーティングの使用により、クライアント・デバイスは、その現行のゲートウェイが故障した場合に代わりのゲートウェイにホップすることができるので、ネットワークのロバスト性が向上し、隘路を排除してネットワーク全体の性能を向上することに寄与することができる。従来の８０２．１１ｂシステムでは、通常、範囲は１００メートル未満に激減する場合が多い。遠距離のクライアント・デバイスまでカバレッジを広げるためには、データ・レートを低下させなければならない。一方、低データ・レートの使用により、クライアント・デバイスがデータ・チャネルに残留する時間が長くなるので、ＷＬＡＮの全クライアント・デバイスに関してもスループットが低下する。適時マルチホップ・ルーティングの使用により、この問題が解決する。何故なら、離れたクライアント・デバイスであっても、シード局及び近隣クライアント・デバイスを通じて最高のデータ・レートでの多重ホップを用い、データを宛先に送信することができ、ネットワークの輻輳を回避するからである。チャネルの最適使用及び電力適合化により、競合を減らし、ユーザに提供するスループットを最適化する。
【００１６】
図２は、８０２．１１ｂＷＬＡＮの一部をなすクライアント・デバイスの模式ブロック図を示す。クライアント・デバイスは、ARM940T RISCを埋め込んだSamsung社のS3C2500マイクロコントローラ４０を含む。また、１０／１００Ｍｂｐｓイーサネット・コントローラ、メモリ・コントローラ、ＬＡＮチップと通信するための１２Ｃ及びＧＰ１０ｓ、ＳＩＭカード・リーダ、ならびにＺＤ１２０１ベースバンド・プロセッサも備えている。Ｓ３Ｃ２５００チップには、３２Ｍビットフラッシュ及び１２８ＭビットＳＤＲＡＭメモリが装備されている。
【００１７】
このデバイスは、８０２．１１及び８０２．１１ｂベースバンド変調及び復調を行う高速ＤＳＰハードウェア・ロジックを用いたＺＤ１２０１ＷＬＡＮ組み合わせチップを含む。今後のＩＥＥＥ８０２．１１グループが規定するＭＡＣ規格に追従するために、ARM7 RISCプロセッサがＺＤ１２０１チップに埋め込まれている。これによって、単にソフトウェア・ドライバをアップグレードすることにより、最新のＷＬＡＮ機構の使用が可能になる。
【００１８】
クライアント・デバイスは、２．４５ＧＨｚワイヤレスＬＡＮ（ＷＬＡＮ）用途用に設計された、SA2400完全集積単一ＩＣ  ＦＲ送受信機４４を含む。これは、先進の３０ＧＨｚｆＴ  ＢｉＣＭＯＳプロセス上で製造される、直接変換無線アーキテクチャである。SA2400Aは、受信機、送信機、及びＬＯ発生器を単一のＩＣに組み込んでいる。受信機は、低ノイズ増幅器、ダウン・コンバージョン・ミキサ、完全集積チャネル・ファイバ、及びオンチップ閉ループを有する自動利得制御（ＡＧＣ）から成る。送信機は、電力傾斜(power ramping)、フィルタ、アップコンバージョン、及び予備ドライバを内蔵する。ＬＯの発生器は、完全に１チップのＶＣＯ及び端数−Ｎシンセサイザによって形成する。受信機についての典型的なシステム性能パラメータは、９３ｄＢ利得、７．５ｄＢ雑音指数、＋１ｄＢｍの入力基準三次切片点（ＩＩＰ３：input-referred third-order intercept point）、及び３ｍｓのＴＸ−Ｒｘ切換時間である。送信機の典型的なシステム性能パラメータは、−７ｄＢｍから＋８ｄＢｍの範囲で１ｄＢ刻みの出力電力、較正後−４０ｄＢｃキャリア漏洩、３０ｄＢのインバンド共通モード除波、及び３ｍｓのＲｘ−Ｔｘ切換時間である。
【００１９】
このデバイスは、ＡＰ１０９１線形二段電力増幅器の形態の電力増幅段を備えており、２．４ＧＨｚ帯域において高い出力電力を有する。このデバイスは、ＩＥＥＥ８０２．１１ｂ規格に準拠した２６ｄＢｍの線形出力電力を送出する。また、電力増幅器は、オンチップ電力検出器も含み、デバイスの出力電力に比例するＤＣ電圧を供給する。
このデバイスは更に、ＤＣ−３ＧＨｚ  ＳＰＤＴＲＦスイッチ４８も含み、非常に低いＤＣ電力消費で、低挿入損失特性及び正の電圧動作を行う。
【００２０】
アンテナ５４及び５６に近い第１ＲＦスイッチ５２は、どのアンテナを送信又は受信に用いるか選択する機能を備えている。選択されたアンテナから、受信入力が２．４５ＧＨｚバンドパス・フィルタ５０に印加される。このフィルタは、２．４ＧＨｚのＩＳＭ帯域の外側の干渉波を除波する。２．４５ＧＨｚバンドパス・フィルタに近い第２ＲＦスイッチ５８が、ＴＸ／ＲＸ切換を行う。このスイッチは、受信モードでは、信号をＳＡ２４００のＬＮＡ部に導入する。次に、信号は、直交ダウンコンバータによって、ミキシングによりベースバンドに落とされ、Ｉ及びＱ成分となる。最後に、信号はＺＤ１２０１のＡＤＣに向かう。ベースバンド回路は、波形をサンプリングし、受信データを逆拡散(despread)し復調する。
【００２１】
送信リンク上では、データは、ＤＢＰＳＫ、ＤＱＰＳＫ、又はＣＣＫ変調することができ、Ｉ及びＱ成分を有するベースバンド直交信号が得られる。次いで、信号は、アップコンバート・ミキサの入力に入り、２．４ＧＨｚ〜２．５ＧＨｚ帯域に変換される。ＳＡ２４００は、高出力電力範囲に対応するために、高電力モード又は低電力モードのいずれでも動作する。高電力モードで動作する場合、TX_OUT_LOを選択し、ＡＰ１０９１増幅器に向かい、高出力電力を供給する。低電力モードで動作するときは、TX_OUT_HIを選択し、信号はＲＦスイッチを直接通過する。尚、ＴＸ  ＡＧＣ機能は、ＺＤ１２０１ベースバンド・プロセッサ４２に備えられている。
ＳＡ２４００送受信機の内部回路を、更に詳細な模式図として図３に示す。
【００２２】
図４は、図１のネットワークのシステム・レベルのアーキテクチャを示す。システムは、本質的に、加入者ユニット、即ち、ユーザ（クライアント・デバイス）、シード局、及びクライアント・デバイスをＷＡＮにリンクするゲートウェイを備えている。クライアント・デバイスは、メッセージを直接それらの間で中継することによって、又はシード局を通じて、互いに通信することができる。ユーザがインターネットのような他のネットワークにアクセスしたい場合、メッセージをゲートウェイを通じてＷＡＮに中継し、次いで、ルータ・ネットワークを通じて他のネットワークに入る。ゲートウェイは、クライアント・デバイス及びシード局が用いるＯＤＭＡプロトコルからＴＣＰ／ＩＰのような他のプロトコルへの変換器として作用する。
前述のネットワークの動作について、これより、図５から図９の模式図を参照しながら説明する。
【００２３】
図５において、発信局Ａは、５箇所の「近隣」局Ｂ〜Ｆと通信することができ、中間局Ｂ、Ｉ及びＭを通じて、データを宛先局Ｏに送信している。局Ａ〜Ｍ及びＯは、一般に、前述のようなクライアント・デバイスを備えたユーザ局であるが、例えば、一部はシード局であってもよい。
【００２４】
ネットワークの効率を最大限高めるために、各局は、局がメッセージを送信又は受信する必要がある場合、通信できる「近隣」局を多数有することが望ましい。一方、所与の局がデータを、選択した近隣局に送信している場合、送信は多局に対して最少の干渉を生ずるようにすることが望ましく、そうでないと、結果的に局間に競合が生じ、ネットワークにおけるデータ・スループット量が減少する。
以上のことを念頭に入れて、本ネットワークは、各局の動作を調節し、任意の時点において、できるだけ高いデータ・レートで、しかしできるだけ低い送信電力で多数の近隣局に対してデータを送信又は受信できるようにし、これにより、他の局との干渉を低減することを図っている。
【００２５】
対象とする種類の通信ネットワークは、同じ１組のチャネル上で通信しようとしている多数の局を備えている。チャネルは、異なる周波数、異なる媒体、異なる符号化（例えば、異なる拡散(spread)符号）、異なるアンテナ、異なるタイム・スロット等、あるいは、これらのあらゆる組み合わせを有するものと定義することができる。チャネルの再利用を最適化するために、局は限られた数の直接近隣、通例５箇所の近隣を維持しようとする。近隣とは、所与の局が通信することができる別の局と定義する。
【００２６】
局は、その送信周波数を変更し、符号（ＰＮシーケンス）を変更し、そのデータ・レートを高め、そしてその送信電力を落とすことによって、それが相手にする又はそれを相手にする近隣の数を制限することができる。全ての局は、既定のプローブ・チャネルに集まり、プローブ信号を用いて、通信する相手となる他の局を探す。他の局を見つけ出し、局のいずれかが他方に送るデータを有する場合、これらは使用頻度が低いデータ・チャネルに移動する。
本発明においては、２種類の探査プロセス、「低速探査」及び「高速探査」の方法を用いる。低速探査プロセスが用いられるのは、各局が近隣を集めるためであり、高速探査プロセスは、発信局及び宛先局間に傾斜を構築するためである。
【００２７】
最初に低速探査プロセスについて述べると、近接して多数の局がある場合、これらはデータ・レートを高くして、そして低送信電力で探査することになる。局は、場合によっては、低いデータ・レートで探査している局に応答するか、又は、十分な近隣を有していない局に応答して、データ・レートを高くして用いることができない、又は十分な近隣を有さない任意の孤立した（離散した）局（以下では、これらを孤立近隣と呼ぶ）を補助する。局がデータ・レートを低くして用いるのは、これらが孤立しており、高データ・レート及び最大電力では十分な近隣を見つけることができない場合のみである。
【００２８】
各局は、低速プローブ信号を規則的な間隔（低速探査タイマが決定する）で送信し、他の局を探そうとする。局は、その低速探査において、他の局の探査を検出できることを示し、こうして、局は、ある所定数の局が探査を検出できることを示すまで、その探査電力を変化させる。局が必要な数の近隣を取得できない場合、最低のデータ・レート及び最大送信電力に留まる。
各局は、低速探査タイマを低速プローブ信号送信間で不規則に変化させて、他の局との衝突を回避する。いずれかの局が他の局の送信を受信し始めた場合、低速探査タイマに新たな間隔をロードし直す。
【００２９】
移動局のネットワークでは、局は常時移動しており、したがってこのような近隣の数は常時変化している。近隣の数が必要数を超過した場合、局はプローブ・チャネル上において、そのデータ・レートを増大し始める。要求数の近隣をもはや上回らなくなるまで、そのデータ・レートを増大し続ける。最大データ・レートに達した場合、最少送信電力に達するか、又はもはや要求数の近隣を超過しなくなるまで、１０ｄＢ刻みでその低速探査送信電力を低下させ始める。
【００３０】
局がプローブ・チャネル上において他の局の低速探査に回答するとき、そのデータ・パケットの長さを低速探査タイマ間隔に制限する。これは、その回答中他の局の探査を回避するためである。回答している局が、小さなパケットに納まり切らないデータを有しており、これを送ろうとする場合、他の局が特定のデータ・チャネルに移動しなければならないことを、パケットのヘッダにおいて示す。
【００３１】
プローブ・チャネル毎にデータ・チャネル数を規定することができる。変更を要求している局は、不規則に、利用可能なデータ・チャネルの１つを選択する。（他の局が要求を受信した場合、直ちにそのデータ・チャネルに変更し、２箇所の局は、これらのいずれにも送るべきデータが全くなくなるまで、又はデータ・チャネル上に残留する最大時間が経過した（データ・タイマによって設定する）場合、通信し続ける。代わりのデータ・トランスポート・プロトコルも用いることができる。
局がデータ・チャネルに変更した場合、データ・タイマをロードする。データ・タイマが許容する限り、データ・チャネル上に残る。データ・タイマが終了すると、局はプローブ・チャネルに戻り、再度探査を開始する。
【００３２】
図６の模式図は、本発明の低速探査プロセスを示す。
低速探査プロセスは、３つの基本的機能から成る。
１．近隣収集
２．電力学習
３．近隣の傾斜(ramping)
近隣収集のプロセスは、局が増大させた電力レベルで探査を開始し、近隣局がそれら自体の探査において、最初の局の探査を検出していることを示すまで行う。これを近隣収集と呼ぶ。探査の電力は、所定数の近隣が、これらが探査を検出していることを示すまで、増加される。
【００３３】
全ての局が所定数の近隣を収集し終えるまで、全ての探査局はその探査電力を増減する。このプロセスは、探査の電力レベルを上昇及び低下し、探査において、他のどの局の探査を傍受したか示すことから成る。このようにして、全ての局は、これらが種々の近隣に達するために必要な電力レベルを習得することができる。局が探査する毎に、その送信電力及びノイズ・フロアを示し、どの局を近隣として有しているかを示す。局が他の局の探査を聴取する毎に、探査から、経路損失、及びその局の経路損失及びノイズ・フロアから局に達するのに必要な電力を計算する。近隣への経路損失、及び近隣に達するのに必要な電力は、各局において保持している近隣テーブルと呼ばれるテーブル内に格納される。近隣がもはや傍受されていない場合、経路損失、及び局に達するために必要な電力レベルを、テーブル内において上昇即ち「傾斜」させ、これをあるレベルに達するまで行い、このレベルに達した時点でこの近隣を近隣テーブルから除外する。
本発明の低速探査プロセスについて、以下の例において更に詳しく説明する。
【００３４】
低速探査パラメータ
・最少探査電力（ＰＰｍｉｎ）
・最大探査電力（ＰＰｍａｘ）
・探査電力刻み（ＰＰｓｔｅｐ）
・探査間隔（Ｐｉｎｔ）
・探査間隔標準偏差（Ｐｓｄｅｖ）
・電力刻み幅毎の探査間隔（ｎＰＰｓ）
・近隣タイムアウト間隔（ＴＮｉｎｔ）
・至近近隣タイムアウト間隔（ＴＣＮｉｔ）（ＴＣＮｉｎｔ＜ＴＮｉｎｔ）
・集めるべき至近近隣の数（ｎＮｂｒｓ）
・探査に含む最大近隣数（ｎＰＮｂｒｓ）
・局ノイズ・フロア（Ｎｆｌｏｏｒ）
・損失傾斜時間（ｔｉｎｃ）
・損失傾斜増分（Ｌｉｎｃ）（ｄＢ）
・損失傾斜過剰（Ｌｅｘ）（ｄＢ）
【００３５】
メッセージ形式
・探査
・探査承認
【００３６】
定義
・近隣：探査又は探査承認を送信した局であり、自局において見ることができる局。
・至近近隣：自局のＩＤを収容したプローブを送信した近隣
【００３７】
プロトコル（局毎）
規則的な間隔(Pint+/-Psdev)で、各局はプローブを送出する。初期送信電力はPPminである。各nPP間隔毎に、電力をPPstepだけ増加させ、少なくともnNbrs箇所の至近近隣を発見するまで（これらは、そのプローブ・メッセージにおいて自局のＩＤで返答している）、又は電力がPPmax（この段階で、プローブの送信をこの電力レベルで継続する）に達するまで増加させる。nNbrs個よりも多い至近近隣を見つけることができた場合、電力を傾斜低下し始める。
【００３８】
プローブは、以下の情報から成る。
ａ．自局におけるノイズ・フロア（Ｎｆｌｏｏｒ）
ｂ．このプローブ・メッセージの送信電力
ｃ．自局の近隣の総数（現在では用いられていない）
ｄ．自局の至近近隣の総数
ｅ．最も近いnPNbrs（以下）個の近隣（又は、全ての近隣の可能性もある。任意）の局ＩＤ
（近隣の近さは、当該近隣の最後のプローブ・メッセージの受信電力に基づく）
【００３９】
探査していないとき、局は他の局からのプローブ（又は、プローブ承認）を求めて傍受している。別の局のプローブを受信した場合、このプローブ・メッセージにおける送信電力情報を用いて当該局までの経路損失を決定する。次いで、ノイズ・フロア情報を用いて、その局にメッセージを送るために必要な最少送信電力を決定し、近隣テーブルをしかるべく更新する。
【００４０】
局が、
（ａ）そのプローブをPPmax電力で送信していること、
（ｂ）nNbrs個よりも少ない至近近隣を有するように要求すること、
（ｃ）自局の至近近隣の１つではないこと、
（ｄ）自局が通信できること
を聴取した場合、遠隔局を「孤立近隣」と見なす。この場合、直ちに（＋／−Psdev)プローブ承認メッセージを、遠隔局によって聴取できるような適した電力で送出する。
プローブ承認は、以下の情報を収容する。
ａ．自局のノイズ・フロア
ｂ．このプローブ承認メッセージのＴｘ電力
ｃ．「孤立近隣」の局ＩＤ
【００４１】
この局が、磁極のＩＤを収容したプローブ承認メッセージを聴取した場合、送信局を至近近隣と位置付ける。
時間tincの後、近隣テーブル・エントリが更新されない（その近隣からのプローブによって）場合、エントリ内の報告された損失にLincを加算する。エントリがプローブによって更新されるまで、又は報告された損失を用いて近隣に達するために必要な送信電力が最大許容電力をLexｄＢだけ超過するまで、Tinc間隔でこれを繰り返す。後者の場合、損失を無縁に設定する。尚、ここの変更により既存の傾斜を凍結してもよい（以下を参照）。
上述した方法、及び、ベクトル・ルーティングの他の方法においては、送信局と宛先局との間のルート（経路）上の局の全てが既知であるわけではなく、これら方法によって生じる問題は、宛先局への経路中に発信局を含む可能性があり、事実上、電力傾斜においてループが生じることである。
損失が無限であり、この近隣に関与する傾斜テーブル内にエントリが存在しない場合、近隣テーブルのエントリを削除する方がよい。
【００４２】
プローブ／プローブ承認がTNintの間近隣から聴取されない場合、この近隣を欠落させる。プローブ／プローブ承認がTCNintの間至近近隣から聴取されない場合、至近近隣を近隣ステータスに逆戻りさせる。
個々の近隣に対するコストは、当該近隣に達するための送信電力に関して計算することができる。
例えば、−１０ｄＢｍ未満＝コスト１
０ｄＢｍ未満＝コスト２
１０ｄＢｍ未満＝コスト３
１７ｄＢｍ未満＝コスト４
コストは、近隣に達するために必要な電力の指示である。干渉が多い程要求される電力も多くなり、電力（バッテリ）消費に関するコストも高くなる等となる。
【００４３】
マルチ・ホップのコストが全て加算された場合、該総コストは、これらホップに続いてメッセージがある場合に、使用される電力量はどの程度か、又は生じる干渉がどの程度かを表すことになる。
低速探査は、近隣に達するために必要な電力の指示を生成する。
【００４４】
局が、その近隣ではない宛先、例えば、ネットワークを超えた遠隔局へのメッセージを有する場合、如何にして宛先に達するのかについて情報を得るために、高速プローブ信号を送信し始める。この情報は、傾斜と呼ばれ、宛先に達するための累積コストの指示である。局が高速探査を開始すると、それは宛先を探していることを示しており、この高速プローブを聴取している近隣は、宛先がその近隣の高速プローブを聴取するまで、それら自体が高速探査を行う。次いで、傾斜が発信源に達するまで、累積コストの加算によって傾斜を構築し、発信源は、宛先への傾斜が低い方の近隣にメッセージを送出し始めることができる。一方、宛先は、宛先に達するまで、それらをその近隣に送出することができる。
【００４５】
各局は、その近隣の各々の各宛先に対する（累積コスト）傾斜、及びそれ自体の宛先に対する傾斜の記録を保持している。各局は、宛先への累積コストが低い方の局にメッセージを渡すだけである。局は、宛先までの傾斜が低い方の近隣であれば、そのいずれにでもメッセージを渡すことができる。低速探査による近隣集合、及び高速探査による傾斜発生により、局は、いずれの宛先であれコストが低い方の局を多数選択することができ、このような宛先にメッセージを送ることができる。近隣は、常時低速探査によって維持され、傾斜は、近隣でない局にメッセージを送る必要があるときに、必要に応じて発生されるだけである。
【００４６】
図７に模式的に示す高速探査プロセス又はアルゴリズムは、発信局及び宛先局間の経路に沿って傾斜を構築するために用いられる。傾斜は、好ましくは、近隣までのコスト（ＣＮ）に関して表現する。このプロセスが開始するのは、
・局においてメッセージを発信するとき、又は
・近隣からの高速探査が傍受されたとき
である。
局は、それが維持している全ての傾斜が発信局又は宛先局によって取り消されるまで、あるいは傾斜が時間切れになるまで、高速探査モードのままでいる。
【００４７】
高速探査パラメータ
・ミリ秒単位の高速探査レート（ＦＰＲａｔｅ）
・高速探査当たりの最大ホップ数（ｍａｘＨｏｐｓ）
・ミリ秒単位の傾斜制限時間（Ｇｔｉｍｅｏｕｔ）
・最大許容可能コスト（ｍａｘＣｏｓｔ）
・ミリ秒単位の凍結エントリ制限時間（Ｆｔｉｍｅ）
・局データ構造
【００４８】
以下のデータ構造は、他の情報を含むことがあるが、高速探査アルゴリズムに直接的に関連するものではない。
近隣表
・近隣毎のエントリ
近隣表エントリ
・近隣局ＩＤ
・近隣までの現コスト（ＣＮ）
・現在維持されている傾斜毎のエントリ
近隣傾斜エントリ
・宛先局ＩＤ
・宛先までの近隣の現コスト（ＣＮＤ）
傾斜表
・現在維持されている傾斜毎のエントリ。宛先毎に１つのエントリ
傾斜表エントリ
・宛先局ＩＤ
・宛先までの現在の最良コスト（ＣＤ）
・現最良コスト近隣局ＩＤ
・凍結ステータス（オン又はオフ）
・凍結制限時間
・凍結コスト（ＣＤＦ）
・凍結近隣ＩＤ（ＮＦ）
・傾斜制限時間
・同じ宛先を有する発信局毎にエントリを収容する、発信局リスト
発信局エントリ
・発信局ＩＤ
・ホップ回数
・維持ステータス（肯定又は否定）
高速探査データ・フォーマット
・送信局ＩＤ
・局におけるノイズ・フロア
・送信電力
・傾斜エントリ数−送信局が傾斜を維持しており、maxCostを超過していない近隣ＰＤＧを有する傾斜表における宛先エントリ毎に通例１つ。
高速探査傾斜エントリ
・宛先局ＩＤ
・送信局から宛先までの最良コスト（ＰＤＧ）
・発信局のリスト
発信局エントリ
・発信局ＩＤ
・維持ステータス（肯定又は否定）
・ホップ回数
【００４９】
高速探査が開始／継続するのは、傾斜表が１つ以上のエントリを収容しているときである。高速探査メッセージは、高速探査が停止するまで、FPrateで発生する。高速探査が停止するのは、傾斜表にエントリが残っていないときである。
新たな近隣が低速探査プロセスによって追加された場合、傾斜表にある宛先毎のエントリを近隣表に追加する。全ての近隣が削除されている場合、傾斜表も削除し、局は高速探査モードから離脱する。
【００５０】
発信局（現行の局）が所与の宛先にデータ・メッセージを発信するか、又はいずれかの場所に宛てられた近隣からデータ・メッセージを受信するとき、３つの可能性が生ずる。
１．傾斜表がメッセージの宛先に対するエントリを収容しており、宛先までの最良コストがmaxCostを超過している。この場合、指定した近隣を経由してメッセージを送信することができる。
２．傾斜表がメッセージの宛先に対するエントリを収容していない。この場合、新たな傾斜表のエントリを作成し（「肯定」のステータスを維持する）、メッセージを整列させ、今後の送信に備えなければならない。
【００５１】
上記した場合の各々において、傾斜表におけるホップ回数は、maxHopsに設定する。発信局が宛先にデータを完全に送出し終えた場合、ステータスを「否定」に設定することによって、その対応する傾斜表のエントリに印を付ける。このフラグは、今後の高速探査によって流布されることになる。
【００５２】
傾斜表がメッセージの宛先に対応するエントリをもはや収容していない場合、その発信元／宛先に対してエントリを追加する。エントリは、新たな宛先に対する近隣表の各々に追加する。傾斜表がメッセージの宛先に対するエントリを収容してはいるものの、対応する発信元局のエントリを有していない場合、その発信局ＩＤをエントリの発信局ＩＤリストに追加する。表のエントリがGtimeoutの間更新されていない場合、そのエントリを削除する。近隣表における対応するエントリを削除する。
【００５３】
高速探査メッセージを形成するには、傾斜表における既知の各宛先毎に、当該宛先に対する宛先までの最良コスト（全ての近隣Ｎに関する、ＣＤ＝ｍｉｎ（ＣＮ＋ＣＮＤ））を列挙する。
傾斜表のエントリが凍結されており、（全ての近隣Ｎについて）全ての値がＣＮＤ＞ＣＤＦである場合、ＣＤの値を傾斜表から送出し、そうでない場合、先に計算した宛先ＣＤまでの最良のコストを用いるが、ＣＮＤ＜ＣＤとなるような近隣の部分集合だけに対してである。
【００５４】
傾斜表のエントリが凍結されておらず、近隣を経由する傾斜の全てのＣＮ＋ＣＮＤがmaxCostを超過する場合、その宛先エントリをメッセージに含めない。傾斜表のエントリが凍結されている場合、その宛先エントリを常にメッセージに含める。所定の宛先に対する傾斜表におけるエントリの全ての発信元エントリのホップ回数が１より大きい場合、宛先エントリをメッセージに含めない。高速探査メッセージにおける発信元エントリは、傾斜表におけるそれらに対応する。高速探査メッセージは、全ての近隣及び孤立近隣に達することができる十分な電力で送信される。全ての発信元局エントリは、「否定」の維持ステータスを有する場合、傾斜リストから削除される。全ての発信元エントリが削除された場合、対応する宛先エントリを傾斜表から削除する。
【００５５】
高速探査メッセージが受信されると、メッセージにおける送信局ＩＤ、ノイズ・フロア、及び送信電力情報を用いて、送信近隣局に対する近隣までのコスト（ＣＮ）を更新する。このような近隣が存在しない場合、新たな近隣表エントリを作成する。高速探査傾斜エントリ毎に、近隣傾斜表を、その以前の値に関係なく、ＣＮＤの新たな値で更新する。
【００５６】
高速探査傾斜エントリ毎に、傾斜表を次のように更新する。
現在時刻を反映するために、傾斜制限時間を変更する。
発信元局エントリを、探査メッセージ表から、傾斜表における対応するエントリにコピーする。
ホップ回数を１だけ減らす。
エントリがまだない場合、新たに追加する。
近隣傾斜エントリを更新する。
指定された宛先に対する傾斜表エントリを以下のように更新する（高速探査傾斜エントリは、近隣Ｎからであり、宛先までのコストＣＮＤは最良であると想定する）。
【００５７】
傾斜表エントリが凍結されていない場合
ＣＮ＋ＣＮＤが宛先ＣＤに対する現行の最良コスト以上であり、そのコストが近隣Ｎを経由しない場合、何も行わない。
ＣＮ＋ＣＮＤが宛先ＣＤに対する現行の最良コスト未満であり、そのコストが近隣Ｎを経由しない場合、現行の最良コストＣＤを減少値ＣＮ＋ＣＮＤに更新する。
ＣＮ＋ＣＮＤが宛先ＣＤに対する現行の最良コスト未満であり、そのコストがＮを経由する場合、現行の最良コストを減少値ＣＮ＋ＣＮＤに更新する。
ＣＮ＋ＣＮＤが宛先ＣＤに対する現行の最良コストよりも大きく、コストがＮを経由する場合、傾斜表エントリを凍結する。凍結ステータスを「オン」に設定し、凍結制限時間をFtimeに設定し、ＣＤＦを現在値のＣＤに設定する。ＣＤを、新たな高い値ＣＮ＋ＣＮＤに設定し、凍結したコストＣＤＦに達したときに経由した近隣局ＩＤ（ＮＦ）を保持する。
【００５８】
傾斜表エントリが凍結されている場合
Ａ．Ｎ＝ＮＦ、又は
Ｂ．Ｎ＜＞ＮＦ、及びＣＮＤが凍結したコストＣＤＦ未満である場合、
ＣＮ＋ＣＮＤが宛先ＣＤに対する現行の最良コスト以上であり、そのコストが近隣Ｎを経由しない場合、何も行わない。
ＣＮ＋ＣＮＤが宛先ＣＤに対する現行の最良コスト未満であり、そのコストが近隣Ｎを経由しない場合、現行の最良コストＣＤを減少値ＣＮ＋ＣＮＤに更新する。
ＣＮ＋ＣＮＤが宛先ＣＤに対する現行の最良コスト未満であり、そのコストがＮを経由する場合、現行の最良コストを減少値ＣＮ＋ＣＮＤに更新する。
ＣＮ＋ＣＮＤが宛先ＣＤに対する現行の最良コストよりも大きく、コストがＮを経由する場合、傾斜表エントリを凍結する。凍結ステータスを「オン」に設定し、凍結制限時間をFtimeに設定し、ＣＤＦを新たな高い値ＣＮ＋ＣＮＤに設定する。注：ＣＤＦ又は、凍結したコストＣＤＦに達したときに経由した近隣局ＩＤ（ＮＦ）を変更してはならない。
凍結制限時間が過ぎた場合、凍結ステータスを「オフ」に設定する。
【００５９】
これより図８を参照して、ベクトル・ルーティングを採用する本発明が用いることができるネットワークにおける、ループ形成の問題について更に論ずる。図８は、多数の局Ａ〜Ｉを示す。各局は、宛先局までのルートを維持しつつ、定期的な間隔で、探査信号、即ち、指示された局を経由して宛先までのコストに関するデータを含む探査信号をその近隣に送信する。尚、他の局の全てが宛先局Ａまでの傾斜を作成しており、各場合において近隣までのコスト（ＣＮ）は１であり、局Ｆ〜Ｉから局Ｃへの直接経路のコストが１０であるとする。ある時間の後、局Ｉは、局Ｈ〜Ｂを経由した局Ａまでの総コストが８であることを把握する。任意の局の間、例えば、局Ｂと局Ｃとの間におけるコストが増大すると、これは連鎖上の全てにおけるコストに影響を及ぼし、各局は局Ａまでのコストを増大させなければならない。何故なら、局Ａまでのルートは全て、局Ｂと局Ｃとの間のリンクを経由するからである。
【００６０】
局Ｂから局Ｃまでのコストが急激に高い値（例えば、局Ｂ及び局Ｃが互いの接触を失ったために無限大）となり、局Ｃが局Ｂからの探査も送信も何も聴取できない場合、局Ｃはその局Ｂを経由した局Ａへのコストを無限大に変更する。局Ｃは他の局の探査信号を傍受し続け、例えば、局Ａまでのコストが８であることを示す、局Ｉからの探査信号を聴取する。局Ｃから局Ｉまでの直接のコストは１０であるので、この結果、局Ｃは、１０＋８、即ち１８の総コストで、局Ｉを通じて局Ａに行けると考える。これは無限大よりはましである。しかしながら、これは勿論正しくなく、送信が局Ｉを経由して導出されても、結局は局Ｃに至り、ループが形成されるので、メッセージは決して局Ａには到達しない。
【００６１】
この状況に対処するためには、局が、選択した局が実際には宛先局に到達できない場合に、別の局を、宛先局までのメッセージ送信のための中間局として特定するのを防止する方法が必要となる。実際には、これを行うには、宛先までのコストが「凍結した」検査値よりも高い局と中間局とを入れ替えることができない所定の時間期間という要件を設ける。この要件は、ルート上の中間局全てを新たなコスト・データで更新することができる十分な期間だけ維持する。
【００６２】
前述の例では、局Ｃから局Ａまでのコストに対して凍結した検査値は２となる。凍結期間中に、宛先までのコストが２未満である別の局からの探査を聴取しない限り、局Ｂを他の局と入れ替えることはない。凍結時間中に、ルート上の局Ｄから局Ｉまでの全てがそれらのコストを無限大に更新し、各局がそれ自体の凍結検査値を暫定的に有する。例えば、局Ｂの局Ａまでのコストは３であり、局Ａまでのコストが３未満の局を聴取しなければ、更新しない。
【００６３】
凍結時間は、連鎖上で局Ｃが直接見ることができる（いくらコストがかかっても）あらゆる局を更新するに十分なだけ長くすることが重要である。本例では、局Ｃは、１０という高いコストで、局Ｆ、Ｇ、Ｈ及びＩを直接見ることができる。このため、凍結時間は、局Ｃにこれらの内１つを、ルート内における局Ａへの中間局として選択させる前に、探査プロセスが局ＦからＩまでを更新できるだけの十分な時間を許容しなければならない。
【００６４】
本例では、凍結期間を、例えば、１０探査間隔に設定した場合、７探査期間の後、局Ｉが更新され、局Ａまでのコストが無限大であることを示す。この時点において、局Ｃがその検査値２の凍結を解除すると、局Ａまでのコストが無限大であることを示す他の局からしか探査信号を受信できず、これらからはいずれも選択しない。何故なら、これは、他のこれらの局も局Ａへのルートを有していないことを示すからである。これによって、ループの形成を防止する。
【００６５】
凍結プロセスについて、以下の３つの例において更に詳しく示す。
この章は、凍結及び凍結解除プロセスの例を２種類示す。最初の例は、２番目に最良の近隣が不変のままであるという単純な状況である。第２の例は、凍結中に変化する２番目に最良の近隣を示す。
【００６６】
例１
この例は、図９における局（Ｍ）に基づく。これは、凍結動作毎の制限時間動作を示す。
局Ｓから局Ｄに傾斜を作成する。局Ｍの傾斜表（ＧＴ）は下記の通りである。
【表１】
2007519320.tif 000003
ＣＮＤが６から７に変化したと仮定する。
【表２】
2007519320.tif 000004
Ftimeは、１００ｍｓ誤に凍結ステータスをクリアすることを意味する、時間切れ回数である。最初に凍結エントリが時間切れになる前に、ＣＮＤが、例えば、７から９に再度変化した場合、これを再凍結と呼ぶ。局ＭのＧＴは以下のようになる。この場合、ＣＤＦ、ＮＦ及びFtimeを追跡する再凍結表を用いる。
【表３】
2007519320.tif 000005
２番目のエントリのタイマ（１００ｍｓ）を作成したときに、起動する。
最初のエントリが時間切れになったとき、２番目の再凍結エントリにおけるＣＤＦ及びＮＦを用いる。この実施態様では、これらのエントリ以降をコピーする。
【表４】
2007519320.tif 000006
再凍結は、数回発生する場合もあり得る。
【００６７】
例２
この例は、図１０における局（Ｍ）に基づく。
局Ｓから局Ｄまでの傾斜を作成する。安定した後、局ＭのＧＴは次のようになる。
【表５】
2007519320.tif 000007
想定状況１
（３）のＣＮＤを３から５に変更すると仮定する。（３）から高速探査を受信する。（Ｍ）におけるＧＴを以下のように更新する。
【表６】
2007519320.tif 000008
この時点では、（２）から来る高速探査は、（Ｍ）のＧＴには影響を及ぼさない。何故なら、ＣＮ＋ＣＮＤ＝８であり、ＣＤ＝７よりも大きいからである。
（１）から来る高速探査は、（Ｍ）のＧＴを更新する。何故なら、ＣＮ＋ＣＮＤ＝６であり、これはＣＤ＝７よりも小さいからである。更新の後、（Ｍ）のＧＴは以下のようになる。Ftimeは現在４０ｍｓであると仮定する。
【表７】
2007519320.tif 000009
想定状況２
（１）のＣＮが２から３に変化したと仮定する。これにより、ＧＴエントリが再凍結されることになる。
【表８】
2007519320.tif 000010
最初のエントリが時間切れとなると、ＧＴは次のようになる。
【表９】
2007519320.tif 000011
２番目のエントリが時間切れとなると、ＧＴは次のようになる。
【表１０】
2007519320.tif 000012
【００６８】
例３
この例は、凍結が発生したときの数カ所の局における総合的な動作を例示する。図１１において、（１）及び（４）間のコストは１０であるので、（Ｄ）までのトラフィックは（３）、（２）及び（１）を通過する。
（Ｄ）及び（１）間のコストが、例えば、１から２０に増大したと仮定する。これにより、（１）が凍結されることになる。
以下の表は、全ての傾斜表を示す（（Ｄ）までの宛先）。高速探査は１０ｍｓ毎に行われると仮定する。以下の表は、ｍｓ単位で絶対時間を示す。
【表１１】
2007519320.tif 000013
アルゴリズム例
＊１．局（１）は局（４）からＦＰを受信する。凍結局のためにアルゴリズムを実行する。ＦＰ（４）におけるＣＤは４であり、これは凍結コストＣＤＦ＝１よりも高いので、局１のＧＴを変更しない。
【図面の簡単な説明】
【００６９】
【図１】本発明の方法及びシステムを利用したＷＬＡＮネットワークを示す全体的システム図である。
【図２】図１のネットワークにおいて用いられるクライアント・デバイスの模式ブロック図である。
【図３】図２のデバイスにおいて用いられる単一チップ送受信機の詳細模式図である。
【図４】図１のネットワークのシステム・レベルのアーキテクチャの模式図である。
【図５】局が中間局を介して互いに通信し合う、本発明のネットワークの模式図である。
【図６】本発明の低速探査方法の模式図である。
【図７】高速探査方法を示す同様の模式図である。
【図８】ベクトル・ルーティング法を採用するネットワークにおけるループの形成を示す簡略模式図である。
【図９】ルーティング・ループの形成を回避するための本発明の方法を示す模式図である。
【図１０】ルーティング・ループの形成を回避するための本発明の方法を示す模式図である。
【図１１】ルーティング・ループの形成を回避するための本発明の方法を示す模式図である。
【図１】
2007519320.tif 000014
【図２】
2007519320.tif 000015
【図３】
2007519320.tif 000016
【図４】
2007519320.tif 000017
【図５】
2007519320.tif 000018
【図６】
2007519320.tif 000019
【図７】
2007519320.tif 000020
【図８】
2007519320.tif 000021
【図９】
2007519320.tif 000022
【図１０】
2007519320.tif 000023
【図１１】
2007519320.tif 000024
【手続補正書】
【提出日】平成18年3月2日(2006.3.2)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の局を備えており、各局が、データを送信及び受信することができる通信ネットワークであって、少なくとも１つの適時選択した中間局を介して発信局から宛先局にデータを送信することを可能としている通信ネットワークにおける動作方法であって、
ａ）各局において、第１の所定の判断基準に応じて、プローブ信号の他の局への送信のために、プローブ・チャネルを選択するステップと、
ｂ）前記選択されたプローブ・チャネル上において各局から近隣収集プローブ信号を送信し、前記近隣収集プローブ信号を探査局から受信した別の局が直接又は間接的に応答することによって、前記探査局にその宛先局又は中間局としての可用性を示すステップと、
ｃ）各局において、ステップ（ｂ）によって識別された他の利用可能な局の詳細を含んだ近隣表を維持するステップと、
ｄ）宛先局にデータを送る必要がある局から、傾斜収集プローブ信号を、前記近隣表内にある局に送信し、当該局から傾斜収集プローブ信号を受信し、前記近隣表にある局及び前記宛先局にデータを送信する必要がある局から前記宛先局への接続コストを示す傾斜データを収集するステップと、
ｅ）必要に応じて、各局において、当該局から各近隣局及び前記宛先局に通信するコスト、並びに、各局の近隣表に存在する各局から前記宛先局に通信するコストに関するデータを備えた傾斜表を維持するステップと
を含み、各局が、発信局から宛先局へのデータの送信のために、近隣表に存在する局から、前記宛先局への通信コストが自身より低い中間局を選択することができるようにし、該方法は、他の局が宛先への自身のコスト値を更新することができる期間中、各局に関する計算された宛先コスト値を一定に維持するステップを含み、局が、他の局自身の計算において、古い宛先コスト値を使用することを防止したことを特徴とする方法。
【請求項２】
請求項１記載の方法において、該方法は、傾斜表に存在するある局が、より高価な宛先コスト値を有する局によって置き換えられることが不可能な期間である所定の期間中、傾斜表エントリ毎に、宛先コストのテスト値を設定するステップを含んでいることを特徴とする方法。
【請求項３】
請求項２記載の方法において、前記所定の期間は、傾斜収集プローブ信号間のインターバルの複数分であり、前記傾斜表内の全ての局が宛先コスト値を更新するに十分な時間となるように計算されていることを特徴とする方法。
【請求項４】
請求項１〜３いずれかに記載の方法において、ステップ（ｂ）によって識別された他の利用可能な局の詳細は、経路損失、及び前記他の利用可能な局に到達するのに必要な電力を含むことを特徴とする方法。
【請求項５】
請求項１〜４いずれかに記載の方法において、前記第２プローブ信号は、前記局の近隣表がエントリを収容している間のみ、各局から送信されることを特徴とする方法。
【請求項６】
請求項１〜５いずれかに記載の方法において、前記方法は更に、前記近隣表における局毎に、発信局から宛先局まで前記近隣表内にある各局を経由してメッセージを送信するコストについて、宛先コスト値を計算するステップを含むことを特徴とする方法。
【請求項７】
請求項１〜６いずれかに記載の方法において、各局は、それ自体の宛先コスト値の一時的記録も維持することを特徴とする方法。
【請求項８】
請求項６又は７記載の方法において、前記宛先コスト値は、前記近隣表における各局及び任意の中間局を経由して、前記発信局から前記宛先局にメッセージを送信する累積コストであることを特徴とする方法。
【請求項９】
各々がデータを送信及び受信することができる複数の局を備えている通信ネットワークであって、少なくとも１つの適時選択した中間局を介して発信局から宛先局に複数のデータ・パケットから成るメッセージを送信することが可能な通信ネットワークにおいて、各局は、
ａ）プローブ信号を他の局へ送信するために、第１の所定の基準に応じてプローブ・チャネルを選択し、
ｂ）前記選択されたプローブ・チャネル上において近隣収集プローブ信号を送信し、探査局からの該近隣収集プローブ信号を受信した他の局が、直接的又は間接的に応答することによって、前記探査局にその宛先局又は中間局としての可用性を示し、
ｃ）ステップ（ｂ）によって識別された他の利用可能な局の詳細を備えた近隣表を維持し、
ｄ）宛先局にデータを送る必要があるとき、前記近隣表に含まれる局に対して、傾斜収集プローブ信号を送信し、かつ、前記近隣表に含まれる局から傾斜収集プローブ信号を受信し、
ｅ）必要に応じて、当該局から、各近隣局及び宛先局と通信するコスト、並びに、当該局の近隣表に顕れる各局から宛先局と通信するコストに関するデータを備えた傾斜表を維持する
ように構成されており、各局が、発信局から宛先局へのデータの送信のために、当該局の近隣表に存在する局から、前記宛先局への通信コストが自身より低い中間局を選択することができるようにし、該通信ネットワークは、他の局が自身の宛先コスト値を更新することができる期間中、各局に関する計算された宛先コスト値を一定に維持するよう構成され、局が、他の局自身の計算において、古い宛先コスト値を使用することを防止したことを特徴とする通信ネットワーク。
【請求項１０】
請求項９記載の通信ネットワークにおいて、各局は、傾斜表に存在するある局が、より高い宛先コスト値を有する局によって置き換えられることが不可能な期間である所定の期間中、傾斜表エントリ毎に、宛先コストのテスト値を設定するよう構成されていることを特徴とする通信ネットワーク。
【請求項１１】
請求項１０記載の通信ネットワークにおいて、前記所定の期間は、傾斜収集プローブ信号間のインターバルの複数分であり、前記傾斜表内の全ての局が宛先コスト値を更新するに十分な時間となるように計算されていることを特徴とする通信ネットワーク。
【請求項１２】
請求項９〜１１いずれかに記載の通信ネットワークにおいて、各局は更に、ステップ（ｂ）によって識別された他の利用可能局の詳細に、経路損失、及び前記他の利用可能な局に到達するのに必要な電力を含むように構成されていることを特徴とする通信ネットワーク。
【請求項１３】
請求項９〜１２いずれかに記載の通信システムにおいて、各局は更に、当該局の近隣表がエントリを収容している間のみ、各局から第２プローブ信号を送信する送信機を含むことを特徴とする通信ネットワーク。
【請求項１４】
請求項９〜１３いずれかに記載の通信ネットワークにおいて、各局は、前記近隣表に含まれる局毎に、発信局から宛先局まで前記近隣表内にある各局を経由してメッセージを送信するコストについて、宛先コスト値を計算するコントローラを含むことを特徴とする通信ネットワーク。
【請求項１５】
請求項９〜１４いずれかに記載の通信ネットワークにおいて、各局は、それ自身の宛先コスト値の一時的記録を維持するメモリを備えていることを特徴とする通信ネットワーク。
【国際調査報告】
2007519320.tif 000025
2007519320.tif 000026