(57)【要約】ネットワーク・チャネル・アクセス・プロトコルが開示される。更に具体的には、負荷に適応し、干渉を回避し、ノード・グループによる共有チャネル・セットへのアクセスを制御する分散ローカル決定チャネル・アクセス・プロトコルが開示される。共有チャネル空間は、所定の時間間隔で反復される多数の通信スロットへ分割される。あらゆる２つのノード間で通信するためスロットを使用する許可は、チャネル・アクセス・プロトコルによって動的に調整される。チャネル・アクセス・プロトコルは、ローカルで、（i）近隣ノードへの負荷を推定し、（ii）負荷に適応し干渉を回避するため、スロットの使用を割り振るか割り振りを解除し、（iii）それ自身に関する干渉エリア内でスロットの使用を強制および公示する。
2005509323.tif 000002
【特許請求の範囲】
【請求項１】
送信ノードから受信ノードへの予定された伝送のためにイントラネットワーク衝突を決定する方法であって、
配列を提供し、
送信ノードまたは受信ノードではない第１のノードを獲得し、
通信スロットを獲得し、
第１のノードが通信スロットの間に送信するように既に割り振られているかどうかを決定し、
第１のノードが、通信スロットの間に送信するように既に割り振られていれば、既に割り振られている伝送および予定された伝送の優先順位を比較し、
予定された伝送の優先順位が、既に割り振られている伝送の優先順位よりも大きくなければ、既に割り振られている第１のノードによる伝送のパワーレベルが、予定された伝送の受信ノードによる受信と少なくとも干渉する可能性があるかどうかを決定する
ことを含む方法。
【請求項２】
更に、パワーレベルが、受信ノードの受信と少なくとも干渉を生じる可能性があるほど十分であれば、配列を修正して、通信スロットの周波数が利用不可能であることを表示することを含む、請求項１に記載の方法。
【請求項３】
プログラムを含む信号保有メディアであって、前記プログラムが、利用可能な通信スロットを決定するための呼び出しの受信に応答して、プロセッサによって実行されるとき、
配列を提供し、
送信ノードまたは受信ノードではない隣接ノードを獲得し、
通信スロットを獲得し、
隣接ノードが、通信スロットの間に送信するように既に割り振られているかどうかを決定し、
隣接ノードが、通信スロットの間に送信するように既に割り振られていれば、既に割り振られている伝送および予定された伝送の優先順位を比較し、
予定された伝送の優先順位が、既に割り振られている伝送の優先順位よりも大きくなければ、既に割り振られている隣接ノードの伝送のパワーレベルが、予定された伝送の受信ノードによる受信と少なくとも干渉する可能性があるかどうかを決定する
ことを含む方法の実行を生じる信号保有メディア。
【請求項４】
干渉を回避して、ノードから構成されるネットワーク内の１つのノードから別のノードへ通信するように、チャネル・アクセスをローカルで決定する方法であって、
情報の集合をノードへ提供し、
情報の集合を使用して潜在的干渉をチェックし、
干渉を回避するためチャネルの一部分を識別する
ことを含む方法。
【請求項５】
更に、チャネルの一部分を割り振ることを含む、請求項４に記載の方法。
【請求項６】
更に、チャネルの一部分の制御を強制することを含む、請求項４に記載の方法。
【請求項７】
強制が、チャネルの一部分の割り振りの強制を、１つまたは複数の隣接ノードへ公示することを含む、請求項６に記載の方法。
【請求項８】
更に、チャネルの一部分の割り振りの強制を使用して、１つまたは複数の隣接ノードに置かれた情報の集合を更新することを含む、請求項７に記載の方法。
【請求項９】
更に、１つまたは複数の隣接ノードによってチャネルの一部分の割り振りの強制を１つまたは複数の隣接ノードの隣接ノードへ再公示することを含む、請求項７に記載の方法。
【請求項１０】
更に、チャネルの一部分の割り振りの強制が、１つまたは複数の隣接ノードによって１つまたは複数の隣接ノードの隣接ノードへ再公示されたことを使用して、１つまたは複数の隣接ノードの隣接ノードに置かれた情報の集合を更新することを含む、請求項９に記載の方法。
【発明の詳細な説明】
【関連出願】
【０００１】
本願は、２００１年４月１８日に出願された米国暫定特許出願通し番号第６０／２８４，６７８号の利益を主張する。この米国暫定特許出願は、参照してここに組み込まれる。
【発明の分野】
【０００２】
本発明は、一般的にはネットワークに関し、更に具体的には、ネットワーク・プロトコルに関する。
【発明の背景】
【０００３】
情報へアクセスしたい消費者の欲望は、インターネットの発展と共に増加し続けている。そのような増加に対応して、定常的に新しい情報がインターネットへ付加されている。特にマルチメディアコンテンツに関して、この情報の多くは、帯域幅の著しいコストを伴って提供される。
【０００４】
電話のダイアルアップ・サービスは、より広い帯域幅システム、たとえば衛星、ディジタル加入者線（ＤＳＬ）、およびケーブル・モデムで置換されつつある。残念ながら、これらのシステムは、現在、大多数の人々によって利用可能であるとは言えない。更に、これらのシステムに関連した購入および工事コストは、魅力を少なくしている。
【０００５】
したがって、無線接続が浮上している。無線システムは、対応する有線システムよりも少ないコストで、より迅速に配置されることができる。携帯電話技術を使用するシステムは、移動無線インターネット接続を提供する方向へ進んでいる。残念ながら、そのようなシステムは帯域幅の制限を受ける。
【０００６】
携帯電話技術の代替は、高速のデータ専用サービスを提供するセルラ・アーキテクチャである。１つの例は、スプリント（Ｓｐｒｉｎｔ）によって提供されつつあるマルチチャネル・マルチポイント分散サービス（ＭＭＤＳ）である。高速サービスを提供する無線システムの利点は、ローカル有線分散ネットワークの工事に関連するオーバヘッドを伴わない迅速な配置を含む。残念ながら、ＭＭＤＳは、遠隔伝送および複雑なユーザ宅工事に依存する。
【０００７】
必要なものは、ＤＳＬおよびケーブル・モデム技術に匹敵する帯域幅を有し、工事が複雑でなく、コストが少ない固定的無線解決法である。メッシュ・アーキテクチャおよびプロトコルは、これらの必要を満たす。Ｓｈｅｐａｒｄへの米国特許第５，６８０２，３８０２号では、固定的無線ネットワークが開示されている。Ｓｈｅｐａｒｄにおいて、無線ネットワークは、送信および受信にスペクトラム拡散技術を使用する非集中パケット無線概念に基づいている。各々の局は、通信のために送信および受信機会の固定的疑似ランダム・スケジュールを計算し、他の局による同じタイプのブロードキャストを聴取する。各々の局のスケジュールは、そのランダムまたは疑似ランダム生成のために理論的に唯一無二であり、したがって、そのようなランダムまたは疑似ランダム生成スケジュールを比較することによって、スケジュール内のオープンスポットが、通信機会のために発見されてよい。局が通信する直接の隣接局のみが、そのようなスケジュールを認識する。したがって、Ｓｈｅｐａｒｄは、チャネル空間の使用の調整を提供せず、トラフィックまたは負荷の著しい変化を調整するには、限られた能力を有する。
【０００８】
したがって、他のノードからの干渉を軽減し、負荷の有意の変化を調整するように、チャネル空間の使用を増加的に調整することが望ましいであろう。更に、そのようなチャネル空間の使用をローカルで調整し、チャネル空間の動的な割り振りを提供することが望ましいであろう。
【発明の概要】
【０００９】
本発明は、干渉を回避して負荷の変化を調整するため、チャネル空間のローカル調整および動的割り振りを提供する。本発明の１つの態様は、メッシュ・ネットワーク・アーキテクチャのチャネル空間割り振りプロトコルである。データ・パケットの負荷の伝送をサポートするため、十分な数の通信スロットが割り振られなければならず、これは、分散アクセス制御のためにローカルの各々のノードで行われる。更に、そのような通信スロットの割り振りは、帯域幅を動的に割り振るため周期的にチェックされる。
【００１０】
本発明の１つの態様は、ノードから構成されるネットワークの中で、干渉を回避して１つのノードから他のノードへ通信するため、チャネル・アクセスをローカルで決定する方法である。更に具体的には、情報の集合がノードへ提供される。干渉は、収集された情報を使用してチェックされ、干渉を回避するためチャネルの一部分が識別される。
【００１１】
本発明の別の態様は、通信スロットの割り振りを決定する方法である。更に具体的には、配列が提供される。第１のノードにおいて、予定された伝送のために少なくとも１つの衝突が存在するかどうかが決定される。配列は、第１のノードで識別された少なくとも１つの衝突に応答して修正される。第２のノードにおいて、予定された伝送のために少なくとも１つの衝突が存在するかどうかが決定される。配列は、第２のノードで識別された少なくとも１つの衝突に応答して修正される。第１のノードと、第１のノードの干渉エリア内の第１の他のノードとの間の、第１の潜在的干渉が、予定された伝送のために識別される。配列は、識別された潜在的干渉に応答して修正される。第２のノードと、第２のノードの干渉エリア内の第２の他のノードとの間の、第２の潜在的干渉が、予定された伝送のために識別される。配列は、識別された第２の潜在的干渉に応答して修正される。少なくとも１つの通信スロットを割り振るための選択を軽減する第３の潜在的干渉が、予定された伝送のために識別される。配列は、識別された第３の潜在的干渉に応答して修正される。予定された伝送のために少なくとも１つの通信スロットを割り振るため、修正された配列を使用して、少なくとも１つの通信スロットが選択される。
【００１２】
本発明の別の態様は、送信ノードと受信ノードとの間の自己衝突を決定する方法である。更に具体的には、配列が提供され、通信スロットが獲得される。送信ノードおよび受信ノードはチェックされ、いずれかまたは双方が通信スロットの間に送信または受信するように既に割り振られているかどうかが決定される。送信ノードおよび受信ノードのいずれかまたは双方が、通信スロットの間に送信または受信するように既に割り振られているならば、各々の既に割り振られている優先順位が、送信ノードから受信ノードへの伝送の優先順位に対してチェックされる。
【００１３】
本発明の別の態様は、送信ノードから受信ノードへの予定された伝送のために、イントラネットワーク衝突を決定する方法である。更に具体的には、配列が提供される。送信ノードまたは受信ノードでない第１のノードが獲得され、通信スロットが獲得される。第１のノードが通信スロットの間に受信するように既に割り振られているかどうかが決定される。第１のノードが通信スロットの間に受信するように既に割り振られているならば、第１のノードの既に割り振られている優先順位が、予定された伝送の優先順位に対してチェックされる。予定された伝送の優先順位が、第１のノードの既に割り振られている優先順位よりも大きくなければ、予定された伝送のパワーレベルが、第１のノードの通信スロットの間に受信と干渉する十分な強度であるかどうかが決定される。
【００１４】
本発明の別の態様は、送信ノードから受信ノードへの予定された伝送のために、イントラネットワーク衝突を決定する方法である。更に具体的には、配列が提供され、送信ノードまたは受信ノードではない第１のノードが獲得される。通信スロットが獲得される。第１のノードが、通信スロットの間に送信するように既に割り振られているかどうかが決定される。第１のノードが通信スロットの間に送信するように既に割り振られているならば、既に割り振られている伝送および予定された伝送の優先順位が比較される。予定された伝送の優先順位が、既に割り振られている伝送の優先順位よりも大きくなければ、既に割り振られている第１のノードによる伝送のパワーレベルが、予定された伝送の受信ノードによる受信と干渉する可能性があるかどうかが決定される。
【００１５】
本発明の前記および追加の態様は、以下で詳細に記載される説明から明らかになるであろう。
【００１６】
本発明の教示は、以下の詳細な説明を、添付の図面と一緒に考察することによって容易に理解され得る。
【００１７】
理解を容易にするため、可能な場合には、同じ参照符号を使用して図面に共通の同一要素を示している。
【詳細な説明】
【００１８】
メッシュ・アーキテクチャ
図１は、本発明の１つの態様に従ったネットワーク１００の例示的部分を示すネットワーク図である。ネットワーク１００は、ネットワーク・アクセス・コンセントレータ（ＳＮＡＰ）１０３、ネットワーク・アクセスポイント（ＮＡＰ）１０１、およびネットワーク・アクセス・ノード１０２を含む。ネットワーク１００のトラフィックは、ネットワーク・アクセス・ノード１０２から隣接ネットワーク・アクセス・ノード１０２へ回送されてよい。そのような隣接ネットワーク・アクセス・ノード１０２は、以下同様に、ＮＡＰ１０１または最終送信先ネットワーク・アクセス・ノード１０２へ達するまで、そのようなトラフィックを、その隣接ネットワーク・アクセス・ノード１０２の１つへ回送してよい。注意すべきは、ノード１０２は相互に通信していてもよいが、私設無線ネットワークを形成するためノード１０１と通信してはならないことである。
【００１９】
ＳＮＡＰ１０３は様々なバックホール１０５へ結合されてよく、このバックホール１０５はネットワーク１０６へ結合されてよい。ネットワーク１０６は運用センター（ＯＣ）１０４へ結合されてよい。バックホール１０５はネットワーク１０６の一部分を形成してよい。ネットワーク１０６は、インターネット、私設ネットワークなどの一部分を含んでよい。私設ネットワークとは、インターネットへ接続されないネットワークを意味する。
【００２０】
ＮＡＰ１０１は、バックホール通信リンク１０７を介してＳＮＡＰ１０３またはネットワーク１０６と通信してよい。理解すべきは、バックホールは有線または無線であってよいことである。特に、ＮＡＰ１０１へ結合されたバックホールは、無線バックホールを有してよい。１つの実施形態では、非ライセンス全米情報基盤（ＵＮＩＩ）帯域におけるＳＮＡＰ１０３とＮＡＰ１０１との間のように、ポイントツーポイント通信が使用される。しかし、有線接続が利用可能であるロケーションでは、有線接続が使用されてよい。
【００２１】
ネットワーク・アクセス・ノード１０２は、少なくとも１つのＮＡＰ１０１またはノード１０２と無線で通信する。理解すべきは、ノード１０２またはＮＡＰ１０１が、ブロードキャスト、ポイントツーポイント通信、およびマルチキャストのいずれか、または或る組み合わせのために構成されてよいことである。ブロードキャストとは、１つまたは複数の受信者から構成される潜在的視聴者の中の特定のターゲット受信者を選出することなく行われる送信を意味する。ポイントツーポイント通信とは、１つまたは複数の受信者から構成される潜在的視聴者の中の特定のターゲット受信者を選出して行われる送信を意味する。マルチキャストとは、受信者から構成される潜在的視聴者の中の複数の特定ターゲット受信者を選出して行われる送信を意味する。明瞭を目的として、以下で説明するノード１０２間の通信、ＮＡＰ１０１間の通信、またはＮＡＰ１０１とノード１０２との間の通信は、ポイントツーポイント通信として行われる。
【００２２】
１つの実施形態において、これはＵＮＩＩ帯域内の無線通信を使用して行われる。しかし、他の既知の帯域が使用されてよい。ノード１０２は、少なくとも部分的に、無線インターリンク１０８を部分的に使用する広域ネットワーク（ＷＡＮ）を形成する。更に具体的には、ＩＥＥＥ８０２．１１ａ物理およびリンク層標準が、秒当たり９〜５４メガビット（Ｍビット／秒）の範囲で通信するために使用されてよい。
【００２３】
本明細書中で説明する通信スロットとは、関連した周波数を有するタイムスロットである。しかし、限定されることなくコード、チャネルなどを含む他のタイプの通信空間が使用されてよいことを、当業者は理解するであろう。図１を参照すると、ＮＡＰ１０１およびノード１０２は、フレームの始まりを基準とした短いタイムスロットの間に情報を送信および受信することによって、相互および各々の間で通信する。各々のフレームは、ほぼ同じ時間長である。限定ではなく例として、各々のフレームはほぼ１秒の長さであってよく、ほぼ各々の秒で開始および終了する。注意すべきは、１つのフレームの中に１つまたは複数のタイムスロットが存在してよいことである。限定ではなく例として、もしタイムスロットが約１ミリ秒の長さを有すれば、１つのフレームの中で約１０００のタイムスロットが利用可能である。更に、フレームは、周知のように、サブフレームへ分割されてよい。たとえば、１秒のフレームは５つの２００ミリ秒サブフレームへ分割されてよく、サブフレームの各々は２００ｍｓのスロットを含む。
【００２４】
各々のノード１０２およびＮＡＰ１０１は、ネットワーク１００内の各々の他のノードおよびＮＡＰと同じように、同一の時間基準で動作するが、そのような時間基準は真太陽時または恣意的同期時間である。基準時間は、図３のＧＰＳ３１０を使用する衛星によって獲得されてよい。代替的に、フレーム基準信号が、特殊目的タイムスロットを使用してフレームの始めにノード間で送信されてよい。限定ではなく例として、そのような特殊目的タイムスロットは、約１マイクロ秒のパルスを送信するため約２００マイクロ秒の持続時間であってよい。
【００２５】
ノード１０２は、屋上、たとえば、図２で示される家屋２００の上、窓、屋根裏、ポール、電話ポールなどの上に置かれてよい。図２において、家屋２００は、多様な装置、たとえばコンピュータ、プリンタ、セットトップ・ボックス、ＰＤＡ、および類似の装置、即ち、限定なしにインターネットへの接続を含むネットワーク接続能力を有するユーザ宅装置（ＣＰＥ）の任意のものを格納してよい。例示の目的で、コンピュータ２０２はノード１０２へ配線されるように示され、ノートブック・コンピュータ２０１およびＰＤＡ２０４は、無線接続、たとえば無線ローカル・エリア・ネットワーク（ＷＬＡＮ）を使用して示される。例として、ノード１０２は、ＷＬＡＮ部分のために２．４ＧＨｚ  ＰＣＭＣＩＡ  ＬＡＮ「カード」を含み、有線接続部分のために１００ｂａｓｅＴまたは１０ｂａｓｅＴ  イーサネット「カード」を含んでよい。「カード」とは、集積回路チップを意味するか、１つまたは複数の集積回路チップを含むプリント回路基板を意味する。そのような有線および無線インタフェースは、図３で例示されるように、インタフェース３０９の一部分を形成する。
【００２６】
図３を参照すると、本発明の態様に従ったＮＡＰ１０１およびノード１０２の例示的部分のブロック図が示される。ＮＡＰ１０１は、バックホール通信装置３０８へ動作的に結合されたノード１０２を含む。ＮＡＰ１０１およびノード１０２は、以後、集合的にノード３００と称する。
【００２７】
マルチセクタアンテナ３０１は、セクタ３０１−０から３０１−７までを含む。本明細書中では８セクタのアンテナ３０１が例示的に示されるが、アンテナ３０１は８よりも少ないか多いセクタ、即ち、１〜ｑ個のセクタを含んでよく、ここでｑは整数である。セクタアンテナが説明されるが、全方向性アンテナ、個別ポイント指向性アンテナの集合、セクタアンテナおよび全方向性アンテナの組み合わせ、ビーム形成アンテナ、またはスマートアンテナなどを非限定的に含む他のアンテナ構成が使用されてよい。
【００２８】
アンテナ３０１は、セクタ３０１−０から３０１−７のセクタへ選択的にアクセスするため、マルチポール・スイッチ３０２へ結合される。セクタ３０１−０から３０１−７はバンクとして配列されてよく、マルチポール・スイッチ３０２がそのようなバンクを選択するように使用されてよい。スイッチ３０２は、トランシーバ（以後「ラジオ」と称する）３０４へ結合される。１つの実施形態において、ラジオ３０４は、５．８ＧＨｚ  ＵＮＩＩ帯域ラジオを使用して実現されてよい。しかし、他の周波数を有する他のラジオも使用されてよい。
【００２９】
ラジオ３０４はラジオ・コントローラ３０５へ結合される。１つの実施形態において、ラジオ・コントローラ３０５はフィールドプログラマブルゲートアレーを使用して実現されてよい。ラジオ・コントローラ３０５は、シングルボードコンピュータ（ＳＢＣ）３０６へ結合される。ＳＢＣ３０６は、プロセッサおよびデータ構造３１２を記憶できるメモリ３０７を含む。ＳＢＣ３０６は、トラフィックを回送するように構成され、この文脈ではルータと考えられてよい。
【００３０】
ＳＢＣ３０６は、インタフェース３０９へ結合される。インタフェース３０９は、前述したようなＷＬＡＮカード、イーサネット・カードなどを含んでよい。バックホール通信装置３０８は、インタフェース３０９を介してＳＢＣ３０６へ結合されるか、場合によりＳＢＣ３０６へ直接結合されてよい。バックホール通信装置３０８は、使用されるバックホールのタイプに依存し、本明細書の他の場所にで言及されるように、そのようなバックホールは有線または無線であってよい。場合により、全地球測位システム（ＧＰＳ）カード３１０およびアンテナ３１１が使用されてよい。ＧＰＳアンテナ３１１はＧＰＳカード３１０へ結合される。ＧＰＳカード３１０は、ラジオ・コントローラ３０５およびＳＢＣ３０６へ結合される。
【００３１】
各々のノード３００は、少なくとも１つの隣接ノード３００を有してよい。隣接ノードとは、ノード３００が直接の通信関係に置かれてよい他のノード３００を意味する。例として、Ａ、Ｂ、およびＣがノードであって、ＡがＣと通信するためＢを介して通信しなければならない場合、ＡおよびＢは隣接ノードであり、ＢおよびＣは隣接ノードであり、ＡおよびＣは隣接ノードではない。
【００３２】
各々のノード３００は、その近隣のノードに関して情報のデータベースを維持する。そのようなデータベースは、データ構造３１２の形式でメモり３０７の中に記憶されてよい。このデータベースは、干渉エリア内のノード３００の間で共有されてよい。干渉エリアとは、前記ノードとの間の通信が別のノードによって干渉されるかも知れないノードの周囲の領域を意味する。言い換えれば、干渉エリアとは、そのようなノードの無線伝送が聴取されるか、別の伝送との干渉を生じるかも知れないノード３００の周囲のエリアである。このエリアは、便宜的に、そのようなノード３００の周囲の半径ｒによって近似される。半径ｒは、ＲＦ伝搬モデルを使用して推定されてよく、限定としてではなく地勢、植生、家屋などを含む他の要因の中でも周波数帯域および送信パワーに依存する。
【００３３】
共有情報は、インターリンク１０８を介して隣接ノード３００へ情報を送信しているノード３００によって生じることができ、隣接ノード３００は、そのような情報を、それらの隣接ノード３００へ再送信してよく、以下同様である。そのようなデータベースは、他のタイプの情報の中でも、ノード・ロケーション、アンテナ方向、スロットの使用、制御パラメータ、経路選定に関する情報を含んでよい。データ・レコードの例は、図Ａ４〜図４Ｄで例示されている。
【００３４】
図Ａ４〜図４Ｄの情報は、例として提供され、したがって他のフィールド、フィールドの情報タイプ、および値が使用されてよい。データ・レコードの各々の例は、「フィールド」、「キー」、「タイプ」、「単位」、および「バイト」欄を含む。「フィールド」は、フィールドの情報タイプを示す。「キー」はデータベース内のキー・フィールドを示す。「タイプ」は、フィールド情報を説明する情報タイプ、たとえばノードＩＤ、整数、時間、および浮動小数点値を示す。「単位」は、そのようなフィールド情報の「単位」を示す。「バイト」は、そのようなフィールド情報に割り振られた記憶空間を示す。
【００３５】
「ノード」フィールドは、それぞれのデータ・レコードが関係するノードを識別する。「時点」フィールドは、データ・レコードが作成または修正された時間を示す。「主体」フィールドは、そのようなデータ・レコードを作成または修正したノードを示す。各々のレコードの中の「シーケンス」フィールドは、増分されたレコード番号を示し、修復プロトコルのためのフィールド、特にネットワーク１００へのノード上にデータベースを確立するためのフィールドである。
【００３６】
図４Ａのデータ・レコード４０１は、ロケータ・レコードであって、本明細書中に前述した他のフィールドの中でも「緯度」および「経度」フィールドを含む。「緯度」フィールドは、データ・レコード４０１が関係するノードの緯度の位置を示し、「経度」フィールドは、そのようなノードの経度の位置を示す。この情報は、そのような情報の他の源の中でもＧＰＳから獲得されてよい。「ロケ正確度」のフィールドは、ロケーション推定の計量の正確度である。言い換えれば、ノードは、指定された緯度および経度の多くの計量値の中にある。「アンテナ数」のフィールドは、多くのアンテナセクタである。「方位」のフィールドは、アンテナセクタ、たとえばセクタ０が指している方向である。この値は真北に対する度数である。等間隔のアンテナセクタから構成された固定アレーを使用する場合、他のセクタの方位は、フィールド「アンテナ数」および「方位」を使用して計算されてよい。「方位正確度」のフィールドは、方位推定の正確度の度数である。データ・レコード４０１からの情報を使用して、アンテナの方位角およびビーム幅がノード３００によって引き出される。
【００３７】
図４Ｂのデータ・レコード４０２は、スロット使用データ・レコードである。データ・レコード４０２は、通信スロットを割り振るか、割り振りを解くために更新される。図３に示されるいずれのノード３００、特に送信ノードは、データ・レコード４０２を更新してよい。スロット割り振りレコードへの更新は、レコードのペアを送信ｔｘおよび受信ｒｘしているとき行われてよい。データ・レコード４０２は、本明細書で前述した他のフィールドの中でも「機能」、「タイムスロット」、「周波数」、「アンテナ」、「他のノード」、および「満了時間」フィールドを含む。
【００３８】
「機能」フィールドは、通信スロットの機能、たとえば、現在割り振られていないこと（「無し」）、送信、または受信を示す。
【００３９】
「タイムスロット」フィールドは、送信または受信機能を実行するため、ｍ個のタイムスロットの０からｍ−１の選択されたタイムスロットｔを示す。
【００４０】
「周波数」フィールドは、送信または受信機能を実行するため、ｎ個の周波数の中の０からｎ−１の選択された周波数ｆを示す。
【００４１】
「アンテナ」フィールドは、送信または受信機能を実行するために選択されたセクタを示す。
【００４２】
「他のノード」フィールドは、メッセージのターゲット受信ノードを識別する。しかし、他のノード・フィールドは、マルチキャストまたはブロードキャスト・インディケータであることができる。
【００４３】
「満了時間」は、機能についてスロットの割り振り満了時間を示す。満了時間が経過した後、ノードは、データ・レコード４０２の機能を「無し」として処理する。しかし、経過する前に、満了時間は、追加の通信スロットの使用のためにリセットされてよい。
【００４４】
「優先順位」フィールドは、スロット割り振りの優先順位値を示す。全てのスロットが割り振られるのであれば、優先順位は、優先値に基づいて別の加入者よりも１つの加入者へ与えられてよい。この優先値は、０から或る整数ｐであってよい。
【００４５】
図４Ｃのデータ・レコード４０３は、制御パラメータ・データ・レコードである。前述したノード、優先順位、主体、時点、およびシーケンスのフィールドに加えて、データ・レコード４０３は「最大帯域幅」フィールドを含み、このフィールドは、そのようなデータ・レコード内で識別されたノードへ割り振られた最大帯域幅制限を示す。
【００４６】
図４Ｄのデータ・レコード４０４は、経路選定コスト・データ・レコードである。前述した主体、時点、およびシーケンスのフィールドに加えて、データ・レコード４０４は、「発信元ノード」、「送信先ノード」、「コスト」、および「動的」のフィールドを含む。「発信元ノード」フィールドは、経路上の発信元ノードまたは開始点を示す。「送信先ノード」フィールドは、そのような経路のターゲット送信先、即ち、そのような経路の最終送信先を示す。「動的」フィールドは、動的経路選定が使用されるべきか、静的経路選定が使用されるべきかを示す。「ホップ」フィールドは、発信元ノードから送信先ノードへトラフィックを回送するため、１つまたは複数の既知の経路から選択された経路を示す。
【００４７】
「コスト」フィールドは、そのようなメッセージを、発信元ノードから送信先ノードへ送るために決定されたコストを示す。そのようなコストは、静的または動的に決定されてよい。
【００４８】
理解すべきは、図４Ａ〜図４Ｄで例示されたデータ・レコードが、全ての可能なデータ・レコードを含むことを意味しないことである。他のデータ・レコードが、その中でも現在および代替の経路、制御およびステータス情報、ノードの各々のペアの間の距離および方位角を含んでよい。更に、例示された１つまたは複数のフィールドが、本発明の１つまたは複数の態様を実現する場合に省略されてよいことを理解すべきである。更に、理解すべきは、ノード３００は、それぞれネットワーク１００のためにデータベースの一部分を維持し、したがってノード間の共有または分散データベースが提供されることである。更に、理解すべきは、ネットワーク１００が中央の制御なしに機能してよいことである。理解すべきは、本発明の１つの態様に従ったメッシュ・アーキテクチャが、本明細書中で開示されることである。このアーキテクチャは、データのパケットベース伝送を使用する。図１の各々のノード３００は、トラフィックを通信するルータを提供する。したがって、そのようなメッシュ・アーキテクチャを実現するプロトコルが必要である。たとえば、ノード３００が、特定の次のホップへトラフィックを回送することを決定するとき、データ・パケットは、そのような次のホップへの伝送のために、そのノードで累積され始める。そのようなデータ・パケットの負荷の伝送をサポートするため、十分な数の通信スロットを割り振る必要があり、これは、以下で詳細に説明するように、分散アクセス制御を行うローカルの各々のノード３００で行われる。更に、ネットワーク１００は動的であるから、スロットの割り振りは、以下で詳細に説明するように、負荷の現在の推定を比較することによって周期的にチェックおよび調整される。
【００４９】
伝送の負荷
図５Ａを参照すると、本発明の１つの態様に従った伝送負荷フローのブロック図が示される。基本的には、３つのタイプの着信伝送、即ち、矢印５０８で示されるように、ノード３００が情報の意図された受信者である伝送、矢印５０３で示されるように、情報を転送するためにノード３００が使用される伝送、および矢印５０４で示されるように、ＣＰＥ５００のためにノード３００が情報を受け取る伝送が、ノード３００で受け取られる。
【００５０】
矢印５０４に関連した情報は、図示されるようにＣＰＥ５００へ送られてよい。更に、矢印５０５で示されるように、ＣＰＥ５００は伝送情報をノード３００へ提供してよい。矢印５０６で示されるように、ノード３００はオーバヘッド情報を送信しなければならないか、矢印５０８で示されるようにオーバヘッド情報を受け取らなければならないかも知れない。そのようなオーバヘッド情報は、データベース情報などの共有を含むネットワーク１００の維持情報を含んでよい。注意すべきは、以下で詳細に説明するように、図５Ｂのプログラム５１０は、矢印５０３で示されるようなノード３００によって中継される着信トラフィック、および矢印５０５および５０６で示されるようなノード３００によって送られるＣＰＥ５００からの発信トラフィックまたはオーバヘッド・トラフィックを測定することである。測定ロケーションの例が提供されるが、トラフィック負荷を測定する他のアプローチが使用されてよい。
【００５１】
図５Ｂを参照すると、本発明の１つの態様に従った例示的伝送負荷プログラム５１０の流れ図が示される。図５Ｂへの参照を継続し、図３および図５Ａを再び参照して、プログラム５１０の動作が説明される。プログラム５１０は、各々の隣接ノード３００へ通信するために必要なノード３００の通信スロットを推定する。プログラム５１０は、各々のノード３００の、たとえばメモリ３０７の中に存在してよい。
【００５２】
プログラム５１０は、プログラム部分５２０および５２１を含む。プログラム部分５２０は、近い将来、即ち、将来の約１〜３０秒の間に、どのような伝送出力負荷（ＯＬ）が存在するかを推定するためのものである。プログラム部分５２１は、プログラム部分５２０から得られたそのような推定ＯＬに基づいて、スロットの割り振りを決定するためのものである。
【００５３】
プログラム５１０は、ステップ５１１でイニシャライズされる。このイニシャライズは、現在の推定期間を開始する。後続の推定は、現在の推定の開始時間の後で、所定の時間間隔で続いてよい。そのような時間間隔は、そのような現在の推定の開始の後で、約０．１〜１０秒の範囲であってよい。注意すべきは、図３のノード３００が、ネットワーク１００へ既に参加しているものと想定されていることである。ネットワーク参加プロトコルは、以下の本明細書中で詳細に開示される。
【００５４】
ステップ５２６で、隣接ノードのグループの中から、１つの隣接ノードが選択される。
【００５５】
ステップ５１２で、着信トラフィックまたは入力負荷（ＩＬ）が、ステップ５２６で選択された隣接ノードのために決定される。この決定は、選択されたロケーションで負荷を測定することによって行われてよい。たとえば、図５Ａに関して前述したように、ＩＬは、ステップ５１１で識別された隣接ノードへ転送されるノード３００への着信トラフィック、ステップ５１１で識別された隣接ノードへ送られるＣＰＥ５００からの発信トラフィック、ステップ５１１で識別された隣接ノードへ送られるノード３００からのオーバヘッド・トラフィックを一緒に加算することによって提供されてよい。しかし、ＩＬを提供するため、負荷の他の組み合わせおよびタイプが使用されてよい。
【００５６】
ステップ５１３で、ステップ５１２で決定されたＩＬがＯＬと比較される。ＩＬがＯＬ以下であれば、ステップ５１４で、ＯＬの新しい値が次式に従って設定される。
【００５７】
ＯＬ＝［ｔ＊（ＩＬ）＋（１−ｔ）（ＯＬ）］                    （１）
ここで、ｔは、０．０〜１．０の範囲の調整可能な時間定数である。限定ではなく例として、ｔは約０．３へ等しく設定されてよい。それより高いｔの値は、より応答的な推定を生じ、それより低い値は、より滑らかな推定を提供する。しかし、ＩＬがＯＬよりも大きければ、ステップ５１５で、ＯＬの新しい値が、ステップ５１２からのファクタｋとＩＬとを乗算したものに等しく設定される。即ち、
ＯＬ＝ｋ＊ＩＬ                                              （２）
ここで、ｋは、一般的に１よりも少し大きい。したがって、ＯＬの推定は、ＩＬの大きな上昇に高度に応答するが、ＩＬが降下するとき指数的に減衰する。
【００５８】
ステップ５１６では、ステップ５１４または５１５で得られたＯＬを使用して、多くの通信スロットが推定される。この推定は、
必要なスロット＝ＯＬ／［（スロット長）（データレート）］        （３）
注意すべきは、等しいスロット長の実施形態が説明されることである。しかし、可変スロット長が使用されてよいことを理解すべきである。たとえば、スロット長は、ほぼ数百マイクロ秒から数ミリ秒の範囲であってよい。本明細書中で説明する実施形態では、１ミリ秒のスロット長が使用される。
【００５９】
ステップ５１７では、ステップ５１６で計算された通信スロットの数が、そのような隣接ノードと通信するため現在割り振られている多くの通信スロットと比較される。推定されたスロット数が、現在割り振られているスロット数よりも小さければ、ステップ５１８で、割り振られたスロットの数が減らされる。割り振りを解除されたスロットの数は、優先順位に基づいて行われてよい。たとえば、最低優先順位からスタートして、１つまたは複数のスロットが割り振りを解除されてよい。更に、割り振りの解除に選択されたスロットが、短い期間内、たとえば約０〜２０秒で満了になるためであれば、そのようなスロットは、そのような満了時間に全ての関連ノードによって自動的に割り振りを解除されるので、そのようなスロットの明示的な割り振り解除は必要でないかも知れない。
【００６０】
しかし、ステップ５１６におけるスロットの推定数が、そのような隣接ノードと通信するため現在割り振られている多くのスロットよりも大きければ、ステップ５１９でスロットの割り振りが増加されてよい。、ステップ５１９で、割り振られる自由スロットの十分な数が存在しなければ、現在割り振られているスロットの使用が、優先順位に基づいて無効にされてよい。優先順位を使用してスロットの割り振りを無効にすることについては、以下で詳細に説明する。
【００６１】
現在のスロットの割り振りが、ステップ５１６におけるスロットの推定数と等しければ、ステップ５１７からステップ５２２への進行で示されるように、割り振りの変更は行われない。
【００６２】
ステップ５２２では、そのような隣接ノードに割り振られたスロットの満了時間がチェックされる。たとえば、約０〜２０秒内のように、まもなく満了するようにスケジュールされた各々のスロットについて、スロット満了時間が延長される。
【００６３】
ステップ５２４では、次の隣接ノード３００のチェックが行われる。別の隣接ノード３００が存在すれば、プログラム５１０はステップ５１２で継続する。
【００６４】
ステップ５２４で、処理される他の隣接ノード３００がなければ、ステップ５２５で、前記の所定の時間が経過するまで、プログラム５１０は休止する。言い換えれば、プログラム５１０は次の推定期間が始まるのを待ち、それが始まると、プログラム５１０はＩＬ値を新しく測定することによってステップ５１２で後続の繰り返しを開始する。
【００６５】
スロットの利用可能性
ステップ５１９に関して前述したように、推定された出力負荷を処理するため追加のスロットが割り振られる。図６Ａは、本発明の１つの態様に従った例示的スロット割り振りプログラム６００の流れ図である。図５Ｂのステップ５１９は、プログラム６００を含むか呼び出してよい。プログラム６００は、メッセージ送信先または受信ノードＲ、またはメッセージ発生または送信ノードＴのために使用されてよい。明瞭にするため、プログラム６００は送信ノードＴにおけるスロット割り振りの決定について説明されるが、プログラム６００は受信ノードＲにおけるスロットの割り振りを決定するために使用されてよいことは、本発明の当業者に明らかであろう。プログラム６００は、図３のメモリ３０７の中に存在してよい。
【００６６】
ステップ６０１では、無効にされる優先順位が最低優先順位へ設定される。したがって、スロット割り振りにおける最初の試みは、今後明らかになるように、既存の割り振りを無効にしない。ステップ６０２では、それぞれ時間および周波数のｍ×ｎ配列が作成され、ゼロで埋められる。再び、前述したように、通信空間は、時間および周波数以外のパラメータによって定義されてよい。更に、配列とは、テーブル、リストなどを含むことを意味する。
【００６７】
ステップ６０３では、Ｔで既に行われた１つまたは複数のスロット割り振りが、それぞれ１つまたは複数の「自己衝突」として識別される。ステップ６０４では、Ｒで既に行われた１つまたは複数のスロット割り振りが、Ｔによってそれぞれ１つまたは複数の「自己衝突」として識別される。ＴからＲへの伝送と衝突するかも知れないＴまたはＲにおける割り振りは、「自己衝突」と呼ばれる。マルチキャストの場合、各々のＲは自己衝突をチェックされる。図１のネットワーク１００の内部的衝突または干渉は、「自己衝突」ではなく「イントラネットワーク」衝突または干渉と呼ばれ、「自己衝突」または「イントラネットワーク」干渉ではない全ての他の衝突または干渉は、「外部」衝突または干渉と呼ばれる。自己衝突、イントラネットワーク干渉、および外部干渉は、以下で詳細に動作的に定義される。
【００６８】
ステップ６０３および６０４では、それぞれ、「自己衝突」に関連したタイムスロットが、ステップ６０２の配列内のそれぞれのロケーションを、たとえばゼロから１へ、１から２へと、以下同様に増分することによって、利用不可能としてマークされる。更に、以下で詳細に説明するように、優先順位を無効にすることによって、優先順位のチェックが利用可能性について行われてよい。
【００６９】
ステップ６０５では、ＴおよびＲ以外の各々のノード３００（図３で示される）がチェックされ、Ｒへ送信しているＴ、またはその逆と干渉し得る送信スロット割り振りを有するかどうかが決定される。再び、マルチキャストの場合、複数の受信ノードＲ、またはその逆が存在するであろう。これらの衝突は、「イントラネットワーク」衝突として識別される。これらのノード３００（図３で示される）は、干渉エリア内のノードに限られる。そのようなイントラネットワーク干渉に関連するスロットは、ステップ６０２の配列の中のそれぞれのロケーションを増分することによって利用不可能としてマークされる。更に、以下で詳細に説明するように、優先順位を無効にすることによって、優先順位のチェックが利用可能性について行われてよい。
【００７０】
ステップ６０６では、ＴおよびＲ以外の各々のノード３００（図３で示される）がチェックされ、Ｒへの送信によって衝突し得る受信スロット割り振りを有するかどうかが決定される。再び、マルチキャストの場合、複数の受信ノードＲが存在するであろう。これらのノード３００（図３で示される）は、干渉エリア内のノードに限定される。ステップ６０６では、そのようなイントラネットワーク干渉に関連したタイムスロットが、ステップ６０２の配列内のそれぞれのロケーションを増分することによって、利用不可能としてマークされる。更に、以下で詳細に説明するように、優先順位を無効にすることによって、優先順位のチェックが利用可能性について行われてよい。
【００７１】
ステップ６０７では、「外部」衝突の危険を有するタイムスロットが識別される。そのような「外部」干渉は、他の帯域内ユーザによるものかも知れない。そのような外部干渉の検出は、以下で詳細に説明する。外部衝突に関連するそのようなタイムスロットが識別され、したがってステップ６０２の配列内のそれぞれのロケーションが増分される。
【００７２】
１つまたは複数の自己衝突、イントラネットワーク干渉、および「外部」干渉が存在すれば、ステップ６０２の配列は、そのような衝突および干渉に関連した非ゼロのエントリーを含む。通信スロットの幾つかについて衝突が存在しなければ、ステップ６０２の配列は、それらのスロットについてゼロのエントリーを有し、これはスロットが利用可能であることを示す。
【００７３】
結果の配列６２０の例が、周波数６９９対時間６９８について、図６Ｂに例示される。ステップ６０２〜６０７は、プログラム６００の干渉および衝突識別部分６１５を構成する。注意すべきは、ステップ６０３〜６０７の順序は、拘束的ではなく変更されてよいことである。
【００７４】
ステップ６０８では、通信スロットが選択され、利用可能として残っているスロットから割り振られる。ゼロのままに残っているステップ６０２の配列内の要素は、ＴとＲとの間の使用、またはマルチキャスト実施形態の場合、Ｔと複数のＲとの間の使用に利用可能である。そのような選択は、疑似ランダム様式で行われてよい。割り振りを必要とする通信スロットの数は、前述したように、図５Ｂのプログラム５１０によって決定される。ステップ６０９では、図５Ｂのプログラム５１０内で割り振られるように要求されたスロットの数が、ステップ６０８で割り振られたスロットの数だけ減らされる。
【００７５】
ステップ６１０では、ステップ６０８で割り振られた通信スロットの数が十分であったかどうかが決定される。通信スロットの十分な数が割り振られたのであれば、プログラム６００はステップ６１１で終了する。しかし、通信スロットの十分な数が割り振られなかったのであれば、ステップ６１０はステップ６１２へ進む。言い換えれば、１つまたは複数の既存のスロット割り振りを無効にすることなく、図５のプログラム５１０内で推定された出力負荷をサポートするには不十分な数のタイムスロットが、現在存在する。
【００７６】
ステップ６１０で十分なスロットが割り振られなかったのであれば、ステップ６１２で無効にされる優先順位が増分される。ステップ６１３ではチェックが行われ、この進行中の割り振り作業を実行するため、無効にされる優先順位が次のスロット割り振り試行の優先順位以上かどうかの決定がなされる。無効にされる優先順位が次のスロット割り振り試行の優先順位よりも小さければ、プログラム６００はステップ６０２で新しく始まる。
【００７７】
しかし、無効にされる優先順位が次のスロット割り振り試行の優先順位以上であれば、ステップ６１１でプログラム６００は終了する。したがって、プログラム６００は、部分的割り振りを行ったか、割り振りを全く行わないで終了するかも知れないことを理解すべきである。言い換えれば、ネットワーク１００は輻輳するかも知れず、その場合、推定された出力負荷を送るための十分な通信スロットが利用可能でないかも知れない。
【００７８】
スロットの利用可能性および自己衝突
図７には、本発明の１つの態様に従った例示的自己衝突プログラム７００の流れ図が示される。図７の参照を継続し、また図６Ａを再び参照すると、ステップ６０３は、ステップ７０１〜７０５によって置換されてよい。
【００７９】
ステップ７０１では、初期タイムスロットが獲得される。
【００８０】
ステップ７０２では、Ｔがチェックされ、該当するものとして、ステップ７０１から獲得されたタイムスロットの間に、Ｔが送信または受信するように既に割り振られているかどうかが決定される。Ｔが、そのようなタイムスロットの間に送信または受信するように既に割り振られていなければ、ステップ７０５で、次のタイムスロットのチェックが行われる。したがって、ステップ６０２からの配列は、このタイムスロット内の全ての周波数について不変のままである。
【００８１】
しかし、Ｔが、そのようなタイムスロットの間に送信または受信するように既に割り振られているのであれば、これは自己衝突を示す。ステップ７０３では、優先順位のチェックが行われる。無効にされる優先順位が既存の使用優先順位よりも大きければ、ステップ７０５で次のタイムスロットのチェックが行われる。したがって、ステップ６０２からの配列は増分されず、これは、このタイムスロット内の全ての周波数の利用可能性を示す。
【００８２】
しかし、無効にされる優先順位が既存の使用優先順位の優先順位以下であれば、このタイムスロット、およびこのタイムスロット内の全ての周波数が、ステップ６０２の配列内のそれらのロケーションを増分することによって、ステップ７０４で利用不可能としてマークされる。ステップ７０５では、自己衝突についてチェックされるべきタイムスロットが少なくとも１つ存在するかどうかの決定が行われる。もし存在すれば、ステップ７０１で、別のタイムスロットが獲得される。しかし、もし自己衝突についてチェックされるべき他のタイムスロットが存在しなければ、プログラム７００は終了する。
【００８３】
図６Ａおよび図７の参照を続けると、ステップ７０１〜７０５で、ＴはＲで置換されてよく、ステップ６０４は、Ｔの代わりにＲの自己衝突をチェックするステップ７０１〜７０５によって置換されてよい。更に、マルチキャスト実施形態では、ステップ７０１〜７０５が各々のＲについて実行されてよい。
【００８４】
スロットの利用可能性およびイントラネットワーク干渉
図８では、本発明の１つの態様に従った例示的送信ノード・イントラネットワーク干渉プログラム８００の流れ図が示される。図６Ａのステップ６０５は、ステップ８０１〜８０９によって置換されてよい。
【００８５】
図８の参照を続け、図６Ａを再び参照すると、ステップ８０１で、ＴまたはＲ以外のノードが選択される。そのようなノードは、「他のノード」と呼ばれ、それがＴまたはＲ以外のノード、またはマルチキャスト実施形態のＴまたは複数のＲ以外のノードであることを示す。そのような「他のノード」は、ＴまたはＲ、またはマルチキャスト実施形態のＴまたは複数のＲの干渉エリア内にある。ステップ８０２では、タイムスロットが選択される。ステップ８０３では、ステップ８０１で選択されたそのような他のノードが、ステップ８０２で選択されたそのようなタイムスロットの間に受信しているかどうかの決定が行われる。そのような他のノードが受信していなければ、ステップ８０８で別のタイムスロットのチェックが行われる。言い換えれば、ステップ６０２の配列は、そのような他のノードおよびそのようなタイムスロットに関して変更されないであろう。
【００８６】
ステップ８０３で、そのような他のノードが、ステップ８０２で選択されたそのようなタイムスロットの間に受信するように既に割り振られているならば、ステップ８０４で、無効にされる優先順位が、そのような他のノードの使用優先順位よりも大きいかどうかの決定が行われる。もし無効にされる優先順位が大きければ、ステップ８０８で別のタイムスロットのチェックが行われる。言い換えれば、ステップ６０２の配列は、そのような他のノードおよびそのようなタイムスロットに関して変更されないであろう。
【００８７】
しかし、ステップ８０４で、そのような他のノードの使用優先順位が無効にされる優先順位以上であれば、ステップ８０６で、Ｔの伝送からのパワー、更に具体的には、Ｔの伝送から生じるそのような他のノードの推定および受信されたパワーが、そのような他のノードの受信と干渉する可能性があるかどうかの決定が行われる。受信されたパワーは、ＲＦ伝搬モデル、たとえばロングレイ−ライス（Ｌｏｎｇｌｅｙ−Ｒｉｃｅ）または統一極超短波（統一ＵＨＦ）を使用して送信および受信アンテナパターンの知識によって推定されてよく、干渉可能性は、（i）Ｔからの伝送および（ii）意図された送信機からのそのような他のノードへの伝送によって生じるそのような他のノードの予想された受信されるパワーの比較によって決定されてよい。通常は、意図されたパワーを干渉パワーによって除算した比が、信号対干渉比（ＳＩＲ）閾値未満であるとき、干渉の可能性があり。ここで、ＳＩＲ閾値は変調に依存する。通常の値は約２０デシベルである。干渉の可能性がなければ、別のタイムスロットがステップ８０２で選択される。干渉の可能性があれば、ステップ８０７で、そのようなタイムスロットおよびそのような他のノードの選択された周波数が、ステップ６０２の配列内のそのロケーションを増分することによって利用不可能としてマークされる。注意すべきは、周波数を利用不可能としてマークすることに関して、自己衝突とイントラネットワーク衝突との間に相違が存在することである。
【００８８】
ステップ８０８では、そのような他のノードについてチェックすべきタイムスロットが、まだ存在するかどうかの決定が行われる。チェックすべき他のタイムスロットが少なくとも１つ存在すれば、別のタイムスロットがステップ８０２で選択される。
【００８９】
そのような他のノードについてチェックすべき他のタイムスロットが存在しなければ、ステップ８０９で、少なくとも１つの他のノードが処理されるべきかどうかの決定が行われる。少なくとも１つの他のノードが処理されるべきであれば、そのような他のノードがステップ８０１で選択される。他のノードが処理されるべきでなければ、プログラム８００は終了する。
【００９０】
図９には、本発明の１つの態様に従った例示的受信ノードイントラネットワーク干渉プログラム９００の流れ図が示される。図６Ａのステップ６０６は、ステップ９０１〜９０９によって置換されてよい。
【００９１】
図９の参照を継続し、図６Ａを再び参照すると、ステップ９０１では、ＴまたはＲ、またはマルチキャスト実施形態のＴまたは複数のＲ以外のノードが選択される。そのような他のノードは、ＴまたはＲ、またはマルチキャスト実施形態のＴまたは複数のＲの干渉エリア内にある。明瞭を目的として、以後、Ｒはポイントツーポイント通信におけるＲを意味し、複数のＲはポイントツーマルチポイント通信における複数のＲを意味するように使用される。ステップ９０２では、タイムスロットが選択される。ステップ９０３では、ステップ９０１で選択されたそのような他のノードが、ステップ９０２で選択されたそのようなタイムスロットの間に送信するように既に割り振られているかどうかの決定が行われる。そのような他のノードが送信していなければ、別のタイムスロットがステップ９０２で選択される。言い換えれば、ステップ６０２の配列は、そのような他のノードおよびそのようなタイムスロットに関して変更されないであろう。
【００９２】
ステップ９０３で、そのような他のノードが、ステップ９０２で選択されたそのようなタイムスロットの間に送信するように既に割り振られていれば、ステップ９０４で、無効にされる優先順位が、予定された使用優先順位よりも大きいかどうかの決定が行われる。無効にされる優先順位が、予定された使用優先順位よりも大きければ、別のタイムスロットのチェックがステップ９０８で行われる。言い換えれば、ステップ６０２の配列は、そのような他のノードおよびそのようなタイムスロットに関して変更されないであろう。
【００９３】
しかし、ステップ９０４で、そのような他のノードの予定された使用優先順位が、無効にされる優先順位以上であれば、ステップ９０６で、そのような他のノードの伝送からのパワー、また更に具体的には、そのような他のノードの伝送からの推定された受信されるパワーが、Ｒの受信と干渉する可能性があるかどうかの決定が行われる。干渉の可能性がなければ、ステップ９０８で、別のタイムスロットのチェックが行われる。前述したような干渉の可能性があれば、ステップ９０７で、そのようなタイムスロットおよびそのような他のノードの選択された周波数が、ステップ６０２の配列内のそのロケーションを増分することによって利用不可能とマークされる。
【００９４】
ステップ９０８では、そのような他のノードについてチェックすべき別のタイムスロットが存在するかどうかの決定が行われる。チェックすべき他のタイムスロットが少なくとも１つ存在すれば、別のタイムスロットがステップ９０２で選択される。そのような他のノードについてチェックすべき他のタイムスロットが存在しなければ、ステップ９０９で、少なくとも１つの他のノードが処理されるべきかどうかの決定が行われる。少なくとも１つの他のノードが処理されるべきであれば、そのような他のノードがステップ９０１で選択される。他のノードが処理されるべきでなければ、プログラム９００は終了する。
【００９５】
外部干渉
図６Ａを再び参照すると、ステップ６０７で、外部干渉による衝突の決定が行われる。ノード３００（図３で示される）は、以下で詳細に説明するように、動作の過程で検出されたそのような外部干渉を含むデータベースを構築する。発見された外部干渉を含むこのデータベースがチェックされ、或るタイムスロットの間に、或る周波数で、またＴからＲへのスケジュールされた伝送と干渉する十分なパワーで、伝送が行われる可能性があれば、そのようなタイムスロットおよび周波数は、配列内で利用不可能とマークされる。
【００９６】
スロットの割り振りと強制
自己衝突、イントラネットワーク干渉、および外部干渉の識別に関して図６Ａに示されるプログラム６００が完了した後、割り振られた通信スロットが強制されなければならない。図１０を参照すると、本発明の１つの態様に従った例示的スロット割り振りおよび強制プログラム１０００の流れ図が示される。
【００９７】
図１０の参照を継続し、図５Ｂおよび図６Ａを再び参照すると、ステップ１００１で、プログラム６００によって処理された配列にアクセスすることによって、スロットの割り振りが決定される。修正されたステップ６０２の配列内に示されるような利用可能スロットが、プログラム５１０のステップ５１９で識別された通信スロットの数量を満たすか部分的に満たすのに十分な数だけ、疑似ランダム的に選択される。したがって、ステップ５１９において、そのような割り振りのためにプログラム１０００がプログラム５１０によって呼び出されてよい。タイムスロットの割り振りに関して、理解すべきは、タイムスロットが１つまたは複数の周波数を関連づけられてよいことである。したがって、タイムスロットに関連した１つまたは複数の周波数が利用不可能である間に、そのようなタイムスロットに関連した１つまたは複数の他の周波数が利用可能であるかも知れないが、例外として、スロットが或る特定の時間および周波数で選択されるならば、別の周波数が利用可能であるとしても、他のスロットはその同じ時間に選択されてはならない。
【００９８】
ステップ１００２では、ステップ１００１で割り振られたスロットがアクセスされる。ステップ１００３では、そのような割り振られたスロットが優先順位を無効にすることよって利用可能にされたかどうかが決定される。優先順位を無効にすることよって利用可能にされた各々のそのようなスロットについて、ステップ１００４で、強制するノードは、別のスロット割り振りを取り消して、それ自身のスロット割り振りを強制してよい。そのような使用を取り消しているそのようなノードの全ての隣接ノードは、隣接ノードが１つであろうと複数であろうと、ノード間の通信を使用してステップ１００５でこの取り消しを通知される。
【００９９】
このスロット割り振りの取り消しを導く優先順位の無効がステップ１００４で起こらなかったならば、そのようなノードは、ステップ１００６で、そのような取り消しなしにその割り振りを強制する。
【０１００】
ステップ１００６では、そのような将来の使用について、スロットの使用が、そのような通信スロットのために強制される。ステップ１００７では、そのようなスロット割り振りを行っているそのようなノードの全ての隣接ノードが、１つであろうと複数であろうと、ノード間の通信によって、そのような通信スロットの使用の強制を通知される。強制とは、ノード間で共有されるデータベース内で、実際の割り振りが行われることを意味する。
【０１０１】
ステップ１００８では、強制されたスロット割り振りの使用、即ち、送信または受信が決定される。強制されたスロット割り振りが、強制するノードにデータを受信させることであれば、その割り振りは、現在または１つまたは複数の後続フレームで実行するためステップ１００９でスケジュールされる。強制されたスロット割り振りが、強制するノードにデータを送信させることであれば、プログラム１０００はステップ１０１０で別のスロットを探索する。ステップ１０１０では、別のスロットについてチェックが行われる。割り振られるべき別のスロットが存在すれば、次のスロットがステップ１００２で割り振られる。割り振られるべき他のスロットが存在しなければ、ステップ１０１１で、プログラム１０００は終了する。
【０１０２】
図１１を参照すると、本発明の１つの態様に従った例示的受信通知プログラム１１００の流れ図が示される。理解すべきは、プログラム１１００が、ＴまたはＲノード、またはスロット割り振りの強制ノードの隣接ノードで実行されてよいことである。
【０１０３】
ステップ１１０１では、図１０のステップ１００７で送られた情報に関連したスロット割り振り伝送が、強制するノードの隣接ノードで受信される。ステップ１１０２では、そのようなスロット割り振り伝送が、そのような隣接ノードで既に受信および記憶された他の情報によって無効にされたかどうかの決定が行われる。無効理由としては、ネットワーク１００（図１に示される）の中の障害に起因する伝送遅延、異なったノード３００（図３に示される）による同一スロットの同時強制などが挙げられる。そのようなスロット割り振り伝送が無効にされたならば、プログラム１１００はステップ１１１４で終了する。
【０１０４】
そのようなスロット割り振り情報が無効にされなかったならば、ステップ１１０２Ａでスロット割り振り情報が記憶される。次に、ステップ１１０３で、そのようなスロット割り振りがこのノード、即ち、プログラム１１１０を実行しているノードに関連するかどうかの決定が行われる。
【０１０５】
そのようなスロット割り振りが、このノードに関連しなければ、プログラム１１１０は、ステップ１１０８へ進む。ステップ１１０８では、ノードは、そのようなスロット割り振りに関連する伝送が、そのようなノードの干渉エリアの中にあるかどうかを決定する。ステップ１１０８で、そのようなスロット割り振りに関連するそのような伝送が、そのような干渉エリアの中にあれば、ステップ１１０９で、プログラム１１００を実行しているそのようなノードは、ステップ１１０１で、受信されたこのスロットの割り振りを、隣接ノードが１つであるか複数であるかを問わず全てのその隣接ノードへ公示する。ステップ１１０８で、そのようなスロット割り振りに関連したそのような伝送が、プログラム１１００を実行しているそのようなノードの干渉エリアの中になければ、プログラム１１００はステップ１１１４で終了する。
【０１０６】
しかし、ステップ１１０３で、このスロット割り振りが、プログラム１１００を実行しているそのようなノードに関連するならば、ステップ１１０４で、そのようなスロット割り振りがどのようなモードを示すかの決定が行われる。ノーモード（ｎｏ  ｍｏｄｅ）または無しの条件が示されるならば、たとえば、別のノードがスロット割り振りを取り消したか拒絶したならば、このスロット割り振りの使用はステップ１１１３で取り消され、その後で、前述したようなステップ１１０８のチェックが行われる。ステップ１１０４で、そのようなノードが、そのようなスロット割り振りの間に送信または受信を決定されるならば、ステップ１１１０で衝突および干渉のチェックが行われる。ステップ１１１０は、プログラム６１５（図６Ａで示される）を実行して、このスロット割り振りが受け入れ可能かどうかを決定する。そのようなスロット割り振りが受け入れ可能であれば、ステップ１１０５で、そのようなノードのためにモードが送信か受信かのチェックが行われる。モードが受信であれば、メッセージはステップ１１０６で受信通知される。次に、いずれのモードの場合でも、ステップ１１０７で、そのようなスロット割り振りが使用のためにスケジュールされ、前述したようなステップ１１０８のチェックが続く。
【０１０７】
しかし、ステップ１１１０または１１０５で、ステップ１１０１で受信されたスロット割り振りが受け入れ可能でないことが決定されると、ステップ１１１１で、そのようなスロット割り振りの使用が取り消され、ステップ１１１２で、そのような取り消しが、プログラム１１００を実行しているノードについて、隣接ノードが１つであるか複数であるかを問わず全ての隣接ノードへ公示される。その後で、プログラム１１００はステップ１１１４で終了する。
【０１０８】
フレームの実行
図１２は、本発明の１つの態様に従ったフレーム実行プログラム１２００の流れ図である。メッセージの送信および受信に加えて、フレーム実行プログラム１２００は、外部干渉をリアルタイムで動作的に決定するように構成される。プログラム１２００は、ノード３００（図３で示される）のメモリ３０７に常駐してよく、フレーム内の各々のタイムスロットを進むか、全てのスロットが処理されたのであれば、次のフレーム内の各々のスロットを通過して進み、以下同様に実行を継続する。
【０１０９】
ステップ１２０２で、プログラム１２００はフレーム同期インディケータを待つ。フレーム同期信号を受信した後、ステップ１２０３では、プログラム１２００を実行しているノードで最初の通信スロットが選択されて使用される。
【０１１０】
ステップ１２０４で、どのようなモード、即ち、送信、受信、または無しが、ステップ１２０３でそのように選択されたスロットに関連するかが決定される。そのようなスロットが送信に割り振られるのであれば、ステップ１２０５で、情報が送信され、ステップ１２０６で、そのようなフレーム内の別のスロットについてチェックが行われる。アクセスすべき他のスロットが存在しなければ、次のフレーム同期信号がステップ１２０２で待たれる。ステップ１２０６で別のスロットが存在すれば、ステップ１２０３で、別のスロットが選択および使用される。
【０１１１】
ステップ１２０４で、そのようなスロットが送信または受信のために割り振られなければ、ステップ１２０６で別のスロットについてチェックが行われる。ステップ１２０４で、スロットが受信に割り振られることが決定されると、ステップ１２０７で、プログラム１２００を実行しているそのようなノードの送信機または受信機が、受信モードにされるかオンにされる。
【０１１２】
ステップ１２０８では、着信信号が、そのようなノードの送信機または受信機によって十分な強度で検出されたかどうかが決定される。受信信号強度インディケータ（ＲＳＳＩ）が、十分な強度の信号を検出するために使用されてよい。信号がステップ１２０８で検出されるならば、ステップ１２０９で、そのように検出された信号に関連したメッセージが正しいかどうかの決定が行われる。言い換えれば、この受信情報が破壊されたかどうかの決定が行われる。
【０１１３】
情報が破壊されたかどうかを決定するため、畳み込みコーディング、ブロックコーディングなどを含み、これらに限定されない周知の順方向誤り訂正アルゴリズムが使用されてよい。干渉は、情報が破壊される理由の１つであるが、多くの他の周知の可能な理由が存在する。そのような情報が破壊されていなければ、着信データはステップ１２２１で処理される。そのようなスロットは使用のままに残され、そのようなノードは命令を実行して、ステップ１２０６で、このフレーム内の次のスロットについてチェックを行う。
【０１１４】
そのような情報が破壊されていれば、誤り情報がステップ１２１１で記憶される。ステップ１２１０で、そのように選択されたスロットの反復使用の故障率があまりに高いかどうかを決定するチェックが行われる。受け入れ可能な故障率は、応用に依存してパケットの約１パーセント（１％）から５パーセント（５％）の範囲であってよい。故障率があまりに高くなければ、そのようなスロットは使用のままに残される。次に、ステップ１２０６で、別のスロットについてチェックが行われる。記録された誤りは、図３のノード３００のメモリ３０７内のデータベースの中に記憶されてよい。後のフレームの間に、この記録された誤りは、そのようなタイムスロットの累積された誤り率があまりに高くなったことの表示を提供するかも知れない。
【０１１５】
しかし、そのような故障率があまりに高ければ、ステップ１２１２で、このスロットの使用が取り消される。ステップ１２１３で、この取り消しは、プログラム１２００を実行しているそのようなノードの隣接ノードへ公示される。
【０１１６】
ステップ１２１４で、検出された干渉は、たとえば時間、周波数、パワー、および可能性としての送信機ロケーションを特徴とする。したがって、ステップ１２１４からの情報は、たとえば図３のメモリ３０７の中に記憶され、後のスロット割り振り試行のために後でアクセスされてよい。
【０１１７】
信号が検出されないか、信号の強度が不十分で、データがステップ１２０８で獲得されなければ、ステップ１２２０で、そのような誤り情報が記憶される。ステップ１２１５では、そのようなノードについて、前述したような故障率が、前述したように高すぎるかどうかを決定するチェックが行われる。限定ではなく例として、送信ノードの送信機が稼動していないか、適正に稼動していないか、そのようなノードの受信機が適正に働いていないか、または前述したようなスロット割り振り強制メッセージが適正に交換されなかったならば、信号は検出されないかも知れない。故障率があまりに高くなければ、そのような通信スロットは使用のままに残される。ステップ１２０６で、フレーム内の別の通信スロットのチェックが行われる。
【０１１８】
しかし、故障率があまりに高ければ、ステップ１２１６で、同じ送信機からの複数の受信スロットが不具合であるかどうかを決定するチェックが行われる。これは、送信ノードがそのような特定のスロット割り振りを認識しないか、故障しているか、または、たとえば送信ノードと受信ノードとの間の妨害物によってブロックされていることを示す。全ての受信スロットが不具合でなければ、ステップ１２１７で、そのようなノードへの隣接ノードは、そのような通信スロットについて計画されたスロットの使用を再通知される。したがって、そのような通信スロットは、使用のままに残され、別の通信スロットのためのチェックがステップ１２０６で行われる。
【０１１９】
しかし、ステップ１２１６で、ほぼ全ての通信スロットが不具合であれば、ステップ１２１８で、関連する送信ノードからの、この受信ノードへの全ての通信スロットの割り当てが、取り消される。
【０１２０】
ステップ１２１９で、そのような受信ノードに隣接するノードは、そのような送信ノードに関連した全ての通信スロットの割り当てのそのような取り消しを通知され、ステップ１２０６で、次のスロットについてのチェックが行われる。
【０１２１】
ネットワークへの参加
図１３を参照すると、本発明の１つの態様に従った例示的ネットワーク参加プロトコル１３００の流れ図が示される。プログラムまたはプロトコル１３００は、孤立化したノード１０１または１０２がネットワーク１００へ参加するか、２つのネットワークが一緒になるために使用される。孤立化したノードとは、ノード１０１または１０２がネットワーク１００へまだ参加していないか、ノード１０１または１０２がネットワーク１００とのコンタクトを失っていることを意味する。たとえば、新しいノードは、その存在を通信し、図３のネットワーク１００上のノードによってコンタクトされるのを待つか、その逆である。このコンタクトを使用して、そのような新しいノードは、現在の動作パラメータを受け取ってよい。更に進んだ概念は、別のノードへの少なくとも１つのリンクを達成し、そのリンクを使用して共有データベースからデータを獲得することである。このデータは、部分的に、隣接ノードの中のノードについて通信情報を提供する。一旦、そのようなデータが獲得されると、ネットワーク接続が向上するかも知れない。
【０１２２】
ネットワーク参加プロトコルによって使用されるように指定された１つまたは複数の通信スロットは、「ハロー」スロットとして知られる。他の通信スロットとは異なり、「ハロー」通信スロットの使用は、使用の前に割り振りおよび強制されず、むしろ競争に基づいている。追加スロットの割り振りは、そのようなネットワーク参加プロトコルの動作を速くする。しかし、フレーム当たり１つの「ハロー」スロットで十分である。
【０１２３】
ステップ１３０１で、プログラム１３００は、次の「ハロー」スロット、更に具体的には、２つの次の「ハロー」スロットの間の中間点を待つ。そのような次の「ハロー」スロットが利用可能になったとき、ステップ１３０２で、前の「ハロー」スロットで送信または受信が起こったかどうかが決定される。
【０１２４】
前の「ハロー」スロットで送信が起こったのであれば、そのような前の「ハロー」スロット伝送に使用されたアンテナおよび周波数が、ステップ１３２５で獲得される。ステップ１３２６では、ステップ１３２５で獲得された周波数およびアンテナを使用して、次のネットワーク参加または「ハロー」通信スロットの中に受信がスケジュールされる。次に、ステップ１３０１で、プログラム１３００は別の「ハロー」スロットを待つ。
【０１２５】
ステップ１３０２で、前の「ハロー」動作が受信機能であったことが決定されると、ステップ１３０３で、メッセージがそのような前のフレームで受け取られたかどうかが決定される。メッセージがそのような前のフレームで受け取られたのでなければ、ステップ１３１０で、周波数がランダムに選択される。ステップ１３１１で、ウエイトを使用してアンテナがランダムに選択される。ウエイトとは、先行する経験からの知識を使用することを意味する。たとえば、各々のアンテナまたはセクタのウエイトＷｓは、次の等式で設定される。
Ｗｓ＝（１＋セクタ内の既知のノードの数）／（ΣｉＷｓｉ）          （４）
【０１２６】
ステップ１３１２では、送信確率が、そのようなノードのネットワーク・ステータスの関数として計算される。そのような送信関数は、孤立化したノードのために伝送の高い確率（約０．９）を提供し、他のノードへの少数のリンクを有するノードのために中程度の確率（約０．５）を提供し、他のノードへの多数のリンクを有するノード、特にバックホール接続を有するノードのために、低い確率（約０．１）を提供しなければならない。
【０１２７】
ステップ１３１６で、数が０．０〜１．０の範囲からランダムに選択される。ステップ１３１７では、ステップ１３１６で選択された数が、ステップ１３１２で設定された確率よりも大きいかどうかが決定される。ステップ１３１７からのそのような数が、ステップ１３１２からのそのような確率よりも大きければ、ステップ１３２６で、前述したように受信動作がスケジュールされる。ステップ１３１７からのそのような数が、そのような確率以下であれば、ステップ１３１８で、「ハロー」リクエストと呼ばれるメッセージが形成されてキューに入れられる。そのような「ハロー」リクエストの形式はヘッダを含み、このヘッダはメッセージ・タイプ、ノードＩＤ、および時間を含む。そのような「ハロー」メッセージは、更に、共有データベースからの多数のレコード、たとえばノード・ロケーション・レコードおよびノード・ステータス・レコードを含んでよい。この追加情報は、プログラム１３００を実行しているそのようなノードのローカル・データベースを更新または占拠するために使用される。
【０１２８】
ステップ１３１９では、ステップ１３１１の選択されたアンテナセクタ内のノード、およびそのセクタ内のあらゆるノードとの最後のリンク以降の時間の関数として、送信パワーが選択される。目的は、別のノードへ達するために必要な最小送信パワーを使用することである。しかし、或る時間だけ探索が実行されて成功しなかったならば、送信パワーが増加され、「ハロー」リクエストの伝送範囲が拡張される。
【０１２９】
ステップ１３２０では、ステップ１３１０からの周波数、ステップ１３１１からのアンテナ、およびステップ１３１９からのパワーを使用して、次の「ハロー」スロットのために送信動作がスケジュールされる。次に、ステップ１３０１で、プログラム１３００は他の別の「ハロー」スロットを待つ。
【０１３０】
ステップ１３０３で、メッセージが前の「ハロー」スロットで受け取られていれば、ステップ１３０４で、そのようなメッセージを送っているノードが、データベース、即ち、前述したような他のノードの共有データベースの中へ入れられる。ステップ１３０５は、そのようなメッセージの中に含まれる他のレコードが、前述したデータベースの中へ入れられてよい。
【０１３１】
ステップ１３０６では、ステップ１３０３からのメッセージが「ハロー」レスポンスであるか、「ハロー」リクエストであるかが決定される。ステップ１３０６で、そのようなメッセージ・タイプがリクエスト、即ち、レスポンスではないことが決定されると、ステップ１３２１で、そのようなリクエストを送っているそのようなノードへの既存の経路が存在するかどうかが決定される。既知または既存の経路が存在すれば、プログラム１３００は、前述したようなステップ１３１０へ進む。既存の経路が存在しなければ、ステップ１３２２で、応答しているノードからデータを受け取るため、プログラム１３００を実行しているこのノードのために通信スロットが作られる。このスロットを作ることは、前述したような衝突および干渉をチェックすることを含む。ステップ１３２３では、「ハロー」レスポンスが形成されてキューに入れられる。ステップ１３２３における「ハロー」レスポンスの形成は、ノード・ロケーション、ノード・ステータス、現在のフレーム計画、およびスロット割り当てレコードを含む。
【０１３２】
ステップ１３２４では、そのようなリクエストを送っているそのようなノードへ到達するため、前述したような送信パワーが選択される。次に、プログラム１３００はステップ１３２０で、前述したように進む。
【０１３３】
ステップ１３０６で、そのようなメッセージが「ハロー」レスポンスであることが決定されると、ステップ１３０７で、そのようなメッセージが、プログラム１３００を実行しているこのノード１０１または１０２のために少なくとも１つの通信スロットの割り当てを含むかどうかが決定される。「ハロー」レスポンスは、「ハロー」リクエストへの返事として提供され、したがって「ハロー」レスポンスは、それがどこにあって、それとどのように通信するかを記述する。通信スロットの割り当てが存在しなければ、プログラム１３００は、前述したステップ１３１０へ進む。
【０１３４】
少なくとも１つの通信スロットの割り当てが存在すれば、プログラム１３００は、ステップ１３０８へ進み、ありとあらゆる既存の受信スロットを、この送信ノードから取り消す。他のノードは、２つのノードの間のいずれの経路の知識を有しない場合にのみ応答するので、このアクションが取られる。ステップ１３０９では、そのような応答ノードからデータを受け取るため、プログラム１３００を実行しているこのノードのために受信スロットが作られる。このスロットを作ることは、前述したような衝突および干渉をチェックすることを含む。次に、プログラム１３００は、前述したようなステップ１３１０へ進む。
【０１３５】
ステップ１３２０および１３２６に関してスケジュールされたメッセージの実際の送信は、前述したようなフレーム実行プログラムの中で行われる。注意すべきは、レスポンスは、そのような応答ノードと通信するための情報を提供するものとして説明されたが、そのようなレスポンスは、双方向での通信情報、即ち、要求ノードとの間の通信情報を含んでよいことである。
【０１３６】
前述したようなネットワーク参加プロトコルは、構成情報を提供することなく新しいノードが既存のネットワークへ参加できるようにするが、そのような情報の提供は、そのようなネットワーク参加プロトコルを著しく速めることができる。追加の構成情報は、１つまたは複数の既存のノードおよびそれらのロケーションのリストを新しいノードへ提供すること、または新しいノードの可能性としてのロケーションを既存のノードへ提供することを含む多くの方法で提供されてよい。そのような情報は、手作業によってノードへ提供されるか、通信リンクを介してダウンロードされるか、メディア・インタフェースを介して負荷されるか、エネルギー源について関心のある無線チャネルを受動的にモニタすることによって収集されることができる。
【０１３７】
したがって、理解すべきは、ノードが、部分的に帯域幅の利用可能性を決定してネットワーク・トラフィックを伝送するための帯域幅を動的に割り振りながら、ネットワーク・トラフィックのためにチャネルを割り振る方法を選択することである。ノードは、ポイントツーポイント、ブロードキャスト、またはマルチキャスト通信によって相互に通信してよいが、或るノードは、メッセージの発信ノードでもなければ最終的な送信先ノードでもない。本発明の１つの態様に従ったそのようなメッシュ・プロトコルは、衝突および干渉を迂回する動的割り振り分散チャネル管理によって、通信範囲の拡張およびサービスの継続を容易にする。
【０１３８】
ネットワーク内の各々のノード構成は、そのようなネットワーク内の隣接ノードによって、少なくとも部分的に決定される。したがって、理解すべきは、本発明の１つの態様に従ったメッシュ・プロトコルが、必要なインフラの量を減らすことによって、配置に関連したコストを減らすことである。更に、インフラとして隣接ノードを使用することは、通信範囲の拡張要件を縮小し、顧客の工事の複雑性を単純化する。隣接ノードは、他の無線アーキテクチャで、そのようなインフラとして機能しない。更に、各々のノードは、チャネル割り振りの意思決定を行ってよく、そのようなネットワークのスケーリングを容易にする。
【０１３９】
更に、本発明の１つの態様に従ったネットワークは、大きな帯域幅をユーザに提供する。例として、各々のノードが、メッシュ内の全ての１００ノードのために秒当たり約３６メガビット（Ｍｂｐｓ）で通信することができ、また、各々のタイムスロットが、８つの送信機／受信機ペアによって再使用されることができれば、そのようなネットワークは、２８８（３６Ｍｂｐｓ＊８）Ｍｂｐｓをトランスポートすることができる。したがって、たとえば、各々のパケットがそのようなネットワーク内の２つの中間ノードを介して転送されるならば、各々のパケットは３度、即ち、３ホップでトランスポートされ、したがって非重複情報の９６Ｍｂｐｓが、そのようなメッシュ内で瞬時にトランスポートされてよい。そのようなノードの半分が顧客によって使用されており、中間ノードとしてではなく顧客のトラフィックを能動的に送信または受信していれば、各々の顧客は、単一の周波数チャネルを使用して、平均で１．９２（９６Ｍｂｐｓ／５０）Ｍｂｐｓの帯域幅を達成することができる。注意すべきは、これが非同期通信であっても同期通信であってもよいことである。
【０１４０】
本発明の１つの態様は、ポイントツーポイント・リンクのみ、ポイントツーマルチポイント・リンクのみ、ブロードキャスト・リンクのみ、またはこれらの任意の組み合わせを含んでよいメッシュ・アーキテクチャ、更に具体的には、同期メッシュ・アーキテクチャである。現在、米国では、ＵＮＩＩ帯域ブロードキャストまたはポイントツーマルチポイント・リンク上の送信パワーは、連邦通信委員会（ＦＣＣ）によって４ワット実効等方放射電力（４  Ｗ  ＥＩＲＰ）へ制限され、ポイントツーポイント・リンクは、２００ワットＥＩＲＰ（２００  Ｗ  ＥＩＲＰ）へ制限されている。したがって、ポイントツーポイント・リンクからのみ形成されたネットワークは、決定的範囲およびリンク囲い込み利点から利益を得てよい。
【０１４１】
本発明の態様は、たとえば、図３のメモリ３０７をプログラムすることによって、ノード３００で使用されるプログラム製品として実現されてよいプログラムを含む。代替的に、そのようなプログラムは、コンピュータへ提供されてよい。プログラム製品のプログラムは、実施形態の機能を定義し、（i）「非書き込み可能」ストレージメディア（たとえば、ＣＤ−ＲＯＭドライブによって読み取り可能なＣＤ−ＲＯＭディスクのようなコンピュータ内の読み出し専用メモリ装置）に永久的に記憶された情報、（ii）「書き込み可能」ストレージメディア（たとえば、ディスケットドライブまたはハードディスクドライブ内のフロッピーディスク）に記憶された変更可能情報、（iii）集積回路メモリに記憶された情報、または（iv）無線通信を含む通信メディア、たとえばコンピュータまたは電話ネットワークを介して、コンピュータへ伝達される情報を含むがこれらの情報を含むことに限定されない多様な信号／保有メディアに含ませることができる。後者の実施形態は、特に、インターネットおよび他のネットワークからダウンロードされた情報を含む。そのような信号保有メディアは、本発明の機能を命令するコンピュータ読み取り可能命令を搬送するとき、本発明の実施形態を表す。
【０１４２】
本発明の教示を組み込んだ様々な実施形態が、本明細書中で詳細に図示および説明されたが、当業者は、依然としてこれらの教示を組み込んだ多くの他の様々な実施形態を容易に案出できる。
【０１４３】
全ての商標は、それぞれの所有者の所有物である。
【図面の簡単な説明】
【０１４４】
【図１】本発明の１つの態様に従ったネットワークの例示的部分を示すネットワーク図である。
【図２】本発明の１つの態様に従ったコンピュータおよびノードを含む消費者宅内装置（ＣＰＥ）を有する家屋の図である。
【図３】本発明の１つの態様に従ったネットワーク・アクセスポイント（ＮＡＰ）またはノードの例示的部分のブロック図である。
【図４】図４Ａ〜図４Ｄは本発明の１つの態様に従ったデータ・レコードの例示的テーブルである。
【図５Ａ】本発明の１つの態様に従った通信フローのブロック図である。
【図５Ｂ】本発明の１つの態様に従った例示的通信負荷プログラムの流れ図である。
【図６Ａ】本発明の１つの態様に従った例示的スロット割り振りプログラムの流れ図である。
【図６Ｂ】本発明の１つの態様に従って処理された後の例示的周波数対時間スロット・マトリックスを示す図である。
【図７】本発明の１つの態様に従った例示的自己衝突プログラムの流れ図である。
【図８】本発明の１つの態様に従った例示的送信ノード・イントラネットワーク干渉プログラムの流れ図である。
【図９】本発明の１つの態様に従った例示的受信ノード・イントラネットワーク干渉プログラムの流れ図である。
【図１０】本発明の１つの態様に従った例示的スロット割り振りおよび強制プログラムの流れ図である。
【図１１】本発明の１つの態様に従った例示的受信通知プログラムの流れ図である。
【図１２】本発明の１つの態様に従った例示的フレーム実行プログラムの流れ図である。
【図１３】本発明の１つの態様に従った例示的ネットワーク参加プロトコルの流れ図である。
【図２】
2005509323.tif 000003
【図１】
2005509323.tif 000004
【図３】
2005509323.tif 000005
【図４Ａ】
2005509323.tif 000006
【図４Ｂ】
2005509323.tif 000007
【図４Ｃ】
2005509323.tif 000008
【図４Ｄ】
2005509323.tif 000009
【図５Ａ】
2005509323.tif 000010
【図５Ｂ】
2005509323.tif 000011
【図６Ａ】
2005509323.tif 000012
【図６Ｂ】
2005509323.tif 000013
【図７】
2005509323.tif 000014
【図８】
2005509323.tif 000015
【図９】
2005509323.tif 000016
【図１０】
2005509323.tif 000017
【図１１】
2005509323.tif 000018
【図１２】
2005509323.tif 000019
【図１３】
2005509323.tif 000020
【国際調査報告】
2005509323.tif 000021
2005509323.tif 000022