(57)【特許請求の範囲】
【請求項１】
バレッジ中継網へのアクセスを調整するための方法であって、
第１のホップ計算欄を備える要求メッセージを、第１のノードから、送信するステップと、
第２のノードで前記要求メッセージを受信し、前記第１のノードから前記第２のノードまでのホップでの第１の距離を判定するステップと、
前記第２のノードから、前記第１のホップ計算欄を備える前記要求メッセージを送信するステップと、
第３のノードで、前記要求メッセージを受信し、前記第１のノードから前記第３のノードまでのホップでの第２の距離を判定するステップと、
第２のホップ計算欄、前記第２の距離、及びデータ送信のための潜在的開始時間を備える調査メッセージを、前記第３のノードから、送信するステップと、
前記調査メッセージを、前記第２のノードで、受信し、（ｉ）前記第３のノードから前記第２のノードまでのホップでの第３の距離、及び、（ｉｉ）前記第２のノードは、前記データ送信のために必要とされる時間スロット中の他のデータ送信に関与しないこと、を判定するステップと、
前記第１の距離、前記第２の距離、及び前記第３の距離に基づいて前記調査メッセージを、前記第２のノードから、送信するステップと、
前記第１のノードで、前記調査メッセージを、受信するステップと、
その後、前記第１のノードから、前記データ送信のためのスケジュールを含む、確認メッセージを、送信するステップと、
前記スケジュールに従って、前記第１のノードから前記第３のノードへの前記データ送信を始動するステップと、
を含む、方法。
【請求項２】
前記バレッジ中継網が、データチャネル及び制御チャネルを備える、請求項１に記載の方法。
【請求項３】
前記制御チャネルが、要求サブチャネル及び確認サブチャネルを備える、請求項２に記載の方法。
【請求項４】
前記要求メッセージが、前記要求サブチャネルで送信される、請求項３に記載の方法。
【請求項５】
前記確認メッセージが、確認サブチャネルで送信される、請求項１に記載の方法。
【請求項６】
ワイヤレスネットワークの通信のためのバレッジ中継網へのアクセスを調整するためのシステムであって、
ソースノードと、
宛先ノードと、
中継ノードと、を含み、
前記ソースノードは、第１のホップ計算欄を備える要求メッセージを、送信し、
前記中継ノードは、前記要求メッセージを受信し、前記ソースノードから前記中継ノードまでのホップでの第１の距離を判定し、前記第１のホップ計算欄を備える前記要求メッセージを送信し、
前記宛先ノードは、前記要求メッセージを受信し、前記ソースノードから前記宛先ノードまでのホップでの第２の距離を判定し、第２のホップ計算欄、前記第２の距離、及びデータ送信のための潜在的開始時間を備える調査メッセージを送信し、
前記中継ノードは、さらに、
前記調査メッセージを受信し、（ｉ）前記宛先ノードから前記中継ノードまでのホップでの第３の距離、及び、（ｉｉ）前記中継ノードは、前記データ送信のために必要とされる時間スロット中の他のデータ送信に関与しないこと、を判定し、
前記第１の距離、前記第２の距離、及び前記第３の距離に基づいて前記調査メッセージを送信し、
前記ソースノードは、さらに、
前記調査メッセージを受信し、
前記データ送信のためのスケジュールを含む確認メッセージを送信し、
前記スケジュールに従って、前記ソースノードから前記宛先ノードへの前記データ送信を始動する、
システム。
【請求項７】
前記バレッジ中継網が、データチャネル及び制御チャネルを備える、請求項６に記載のシステム。
【請求項８】
前記制御チャネルが、要求サブチャネル及び確認サブチャネルを備える、請求項７に記載のシステム。
【請求項９】
前記要求メッセージが、前記要求サブチャネルで送信される、請求項８に記載のシステム。
【請求項１０】
前記確認メッセージが、確認サブチャネルで送信される、請求項６に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドホックワイヤレス通信ネットワークで複数のデータソースからの送信を調整するためのシステム及び方法に関する。
【関連出願の相互参照】
【０００２】
本願は、これによりその全体を参照によって本願明細書に引用したものとする、２０１２年５月２４日に出願された米国特許出願第１３／４８０，３８７号、表題「Ｍｅｔｈｏｄ  Ａｎｄ  Ｓｙｓｔｅｍ  Ｆｏｒ  Ｃｏｏｒｄｉｎａｔｉｎｇ  Ａｃｃｅｓｓ  Ｔｏ  Ａ  Ｂａｒｒａｇｅ  Ｒｅｌａｙ  Ｎｅｔｗｏｒｋ」の優先権を主張する。
【著作権通知】
【０００３】
本特許文書及びそれの添付書類の開示の一部は、著作権保護の対象である資料を含む。著作権所有者は、それが特許商標庁包袋又は記録に現われるとき、本特許文書又は本特許開示のいずれかによる複製に異論はないが、そうでない場合には、何であれすべての著作権を留保する。
【背景技術】
【０００４】
ネットワーク及びモバイルネットワークの使用は、近年、指数関数的に増大した。ネットワークは、ノードと呼ばれるネットワーク上の場所の間でデータのブロックを送信する。ネットワーク上のノードの複雑さ及び数が増すと、ネットワーク上の衝突のリスクも増す。したがって、バレッジ中継網へのアクセスを調整する必要がある。
【発明の概要】
【０００５】
本発明の実施形態は、バレッジ中継網へのアクセスを調整するための方法及びシステムを含む。たとえば、一実施形態で、バレッジ中継網へのアクセスを調整するための方法は、第１のノード又は通信ノード（以下「ノード」）によって、ネットワーク上の第２のノードから第１のメッセージを受信するステップ、第１のノードによってメッセージの送信を抑制するステップ、第１のノードによって第１のメッセージに対応する第２のメッセージを受信する又は第２のメッセージの受信なしに十分な時間待つステップ、第１のノードによってメッセージの送信を再起動するステップを含む。
【０００６】
これらの例示的実施形態は、本主題を限定する又はその制限を定義するために記載されるのではなく、その理解を助けるための例を用意するために記載される。例示的実施形態は、詳細な説明で論じられ、さらなる例がそこで提供される。様々な実施形態によって与えられる利点は、本明細書を分析することによって及び／又は特許請求されている対象の１つ又は複数の実施形態を実施することによって、さらに理解され得る。
【図面の簡単な説明】
【０００７】
【図１】バレッジ中継網へのアクセスを調整するためのシステムの一実施形態によるネットワーク接続形態の一例を示す図である。
【図２】バレッジ中継網へのアクセスを調整するためのシステムの一実施形態によるネットワーク接続形態のもう１つの例を示す図である。
【図３】バレッジ中継網へのアクセスを調整するためのシステムの一実施形態によるネットワーク接続形態のもう１つの例を示す図である。
【図４】バレッジ中継網へのアクセスを調整するためのシステムの一実施形態によるネットワーク接続形態のさらにもう１つの例を示す図である。
【図５】バレッジ中継網へのアクセスを調整するためのシステムの一実施形態による例示的データチャネルスケジュールのグラフ表現を示す図である。
【図６】バレッジ中継網へのアクセスを調整するためのシステムのもう１つの実施形態による例示的データチャネルスケジュールのグラフ表現を示す図である。
【図７】バレッジ中継網へのアクセスを調整するためのシステムの一実施形態によるネットワーク接続形態の一例を示す図である。
【図８】本発明の一実施形態による、バレッジ中継網へのアクセスを調整するための方法のフローチャートである。
【図９】本発明の一実施形態による、バレッジ中継網へのアクセスを調整するための方法のもう１つのフローチャートである。
【図１０】本発明の一実施形態による、バレッジ中継網へのアクセスを調整するための方法のさらにもう１つのフローチャートである。
【図１１】本発明の一実施形態による、バレッジ中継網へのアクセスを調整するためのシステムのブロック図である。
【発明を実施するための形態】
【０００８】
モバイルアドホックネットワーク（「ＭＡＮＥＴ」）は、多くの研究及び開発の焦点である。ＭＡＮＥＴは、固定インフラストラクチャへの依存がないことによって他のクラスのワイヤレスネットワーク  −  衛星、セルラ、及びワイヤレスローカルエリアネットワーク（「ＷＬＡＮ」）など  −  と区別することができる。ソースノードがデータを明確な宛先ノードに（又は複数の宛先ノードに）送信したいが、直接リンクを介してそれを行うことができない（たとえば、大きな空間的分離が原因で）場合、次いで、マルチホップ通信パスウェイが、中継機能を実現する複数の介在するノードを介して確立され得る。ＭＡＮＥＴの特徴は、いつでも、任意のノードがデータ伝送のためのソース、宛先、又は中継の機能を果たすことができることである。
【０００９】
ワイヤレスネットワーク設計は、従来、ネットワーク構造がプロトコルのスタックに分けられた、ワイヤードネットワーク（たとえば、インターネット）のために開発された層状パラダイムに従った。オープンシステム相互接続参照モデル（「ＯＳＩモデル」）では、ネットワーク構造は、デバイスと物理媒体の間のノードエアインターフェースを定義する、下部にある物理層（「層１」）から、ファイル転送プロトコル及びハイパーテキスト転送プロトコルなどの高レベルプロトコルの動作を定義する、上部にあるアプリケーション層（「層７」）に及ぶ、７つの層に分けられる。ＯＳＩモデル内の各プロトコル層は、明確に定義されたサービスをそれより上の層に供し、下の層にサービスを要求する。コンピュータサイエンスの言語で、１つのノードの層２のプロトコルのインスタンスは、もう１つのノードの層２のその同じプロトコルのインスタンスと通信する、など。
【００１０】
（層２プロトコル設計）
【００１１】
ＯＳＩモデルの層１及び２は、それぞれ、物理層及びデータリンク層と呼ばれる。そのような一実施形態で、層１はネットワークを備えるノード間の直接リンクを定義し、そして、層２は媒体アクセス制御（「ＭＡＣ」）副層を含む。ワイヤレスネットワークで、ＭＡＣ副層は、明確なノードからの送信が互いに干渉するのを避けるために、物理媒体へのアクセスを調整する  −  層１によって定義されるように  −  責任を負う。
【００１２】
衝突回避を有するキャリア検知多重アクセス（Ｃａｒｒｉｅｒ  Ｓｅｎｓｅ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ  ｗｉｔｈ  Ｃｏｌｌｉｓｉｏｎ  Ａｖｏｉｄａｎｃｅ、「ＣＳＭＡ／ＣＡ」）は、ＩＥＥＥ８０２．１１ＷＬＡＮ規格で使用され得る。基本的ＣＳＭＡ／ＣＡで、データの送信を望むソースノード「Ｓ」は、先ず、別のノードからの信号の存在の検出を試みる。そのような信号が検出されない場合、そのとき、感知された媒体は「遊休状態」と言われ、ノードＳが送信を開始する。そうでない場合、感知された媒体は「使用中」であり、ノードＳは、チャネルを再び感知するまで無作為の時間（「バックオフ期間」と呼ばれる）待つ。
【００１３】
基本的ＣＳＭＡ／ＣＡプロトコルは、図１に示された隠されたノードの問題（又は隠された端末の問題）を抱える。図１に示すネットワークで、１０２のラベルを付された円によって表されたノード（以下「ノード１０２」）は、直接リンクを介してノード１０１及び１０３と通信することができる（線によって表される）が、直接リンクはノード１０１と１０３を接続しない。いくつかの実施形態では、時間ｔ内の瞬間に、どのノードも送信していない。そのような一実施形態で、時間ｔに、ノード１０１は、データをノード１０２に送信することを望む。したがって、ノード１０１は、媒体を感知し、他の信号を検出せず、送信を開始する。そのような一実施形態で、ノード１０１からノード１０２へのこの送信中に、ノード１０３がノード１０２へのそれ自体の送信を始動することを望む場合、ノード１０１からの送信はノード１０３で受信されないので、ノード１０３はその媒体を「遊休状態」として感知することになる。したがって、ノード１０３は、ノード１０２への送信を開始することになる。ノード１０１及び１０３からの同時の送信は、その場合、ノード１０２で互いに干渉することになり、どちらの送信も適切に受信されないことになる。
【００１４】
いくつかの実施形態で、この問題は、媒体が所与のデータ伝送のノードの送信及び受信の両方で「遊休状態」であることを確保することがその目的である、送信要求（ｒｅｑｕｅｓｔ−ｔｏ−ｓｅｎｄ「ＲＴＳ」）／送信可（ｃｌｅａｒ−ｔｏ−ｓｅｎｄ、「ＣＴＳ」）機構を介して対処され得る。たとえば、一実施形態で、ノード１０１からノード１０２へのデータの送信の前に、以下のメッセージ交換が行われたことになる。すなわち（ｉ）ノード１０１が、データをノード１０２に送信したいというそれの要望を示すＲＴＳメッセージ（「ＲＴＳ１０１→１０２」）を送信することになる、（ｉｉ）その媒体は時間ｔにノード１０２で遊休状態であると感知されるので、ノード１０２が、ノード１０２がデータを実際に受信することができることを示すＣＴＳメッセージ（「ＣＴＳ１０２→１０１」）で応答することになる。
【００１５】
ノード１０１とノード１０２の間のメッセージＲＴＳ１０１→１０２及びＣＴＳ１０２→１０１の交換は、２つの機構を介して干渉を防ぐことができる。第１に、ノード１０３がメッセージＣＴＳ１０２→１０１をうまく受信する起こり得る事象で、ノード１０３は、次いで、ノード１０１とノード１０２の間のデータ送信を認識し、そのデータ送信が完了するまでメッセージ（「ＲＴＳ１０３→１０２」）を送信するためのそれ自体の要求を抑制する。第２に、何らかの理由でメッセージＣＴＳ１０２→１０１がノード１０３でうまく受信されない場合、次いで、メッセージＲＴＳ１０３→１０２は、ノード１０２によって無視されることになり（すなわち、対応するＣＴＳは送信されない）、そして、ノード１０３は次のＲＴＳを送信するのを無作為の時間待つことになる。
【００１６】
（層３プロトコル設計）
【００１７】
ＯＳＩモデルの層１は、ネットワークを備えるノード間の直接リンクを定義し、一方、層２は、各ノードでそれらのリンクへのアクセスを調整する。ＯＳＩモデルの層３、「ネットワーク層」、は、ＭＡＮＥＴでのパケット経路指定の任務を第一に負い得る。たとえば、一実施形態で、ノード「Ｓ」からのデータパケットは、ノード「Ｄ」に送信され得る。Ｓ及びＤが隣接しない限り  −  すなわち、直接リンクがノードＳとＤの間に存在しない限り  −  このパケットは、「マルチホップ」送信を完了するために、１つ又は複数の中間ノードによって中継される必要があることになる。ＳからＤへのパケットが所与のノード「Ｘ」によって受信されるとき、所与のノード「Ｘ」は、経路指定テーブルを調べて、それがそのパケットを転送するべきかどうか（すなわち、それがＳからＤへの経路の部分であるかどうか）を判定する。
【００１８】
マルチホップ経路指定の概念が、図２に示される。図１のように、図２で、ラベルを付された円はノードを表し、それらの円を接続する線は直接リンクを定義する。一実施形態で、経路は、最短経路基準で定義され、たとえば、経路２０１→２０２→２０３→２０４は、これがこれらのノードの間の唯一の３ホップパスである（及びより短いパスは存在しない）ので、ノード２０１からノード２０４へのマルチホップ送信に使用される。そのような一実施形態で、ノード２０１が、ノード２０４を宛先とされたデータパケットを送信するとき、それらのパケットは、それにより、ノード２０２によって転送されるが、ノード２１２及び２２２によって無視される、など。
【００１９】
経路指定テーブルは、積極的に（たとえば、宛先順距離ベクトル、又は「ＤＳＤＶ」経路指定プロトコル）又は受動的に（たとえば、アドホックオンデマンドベクトル、又は「ＡＯＤＶ」経路指定プロトコル）のいずれかで維持され得る。積極的経路指定プロトコルは、制御情報の周期的送信を介して、すべてのノードからの、すべてのノードへの、すべてのノードでの時間的に変化する経路を維持する。受動的プロトコルは、必要なだけ経路指定テーブルを更新する。
【００２０】
層３経路は、ユニキャスト送信（すなわち、明確なソースノード／宛先ノードペア）に限定される必要はない。いくつかの実施形態でＭＡＮＥＴトラフィックパターンはまた、マルチキャストデータ  −  単一ソースノードが複数の宛先ノードに送信する  −  及び同報通信データ  −  単一ソースノードがそのネットワークのすべての他のノードに送信する  −  を含む。さらに、いくつかの実施形態で、マルチキャスト経路は、所与のマルチキャスト群のソース及びすべての宛先ノードを含む最小限のスパニング木によって説明される。
【００２１】
（バレッジ中継網の概論）
【００２２】
いくつかの実施形態で、層２及び３機能性（たとえば、ＲＴＳ／ＣＴＳメッセージ、バックオフ期間、経路指定テーブル更新）を維持するために必要とされる制御オーバヘッドは、帯域幅の９９％と同量を消費するように示された。さらに、従来の層２プロトコル（たとえば、ＲＴＳ／ＣＴＳを有するＣＳＭＡ／ＣＡ）によって導入されるパケット当たりの及びホップ当たりのコンテンション遅延は、音声及びリアルタイムビデオなどのマルチホップの待ち時間が不可欠なトラフィックの受け入れ難い遅延をもたらし得る。
【００２３】
協調的移送と呼ばれる、協調的な、空間的に含まれたフラッディング機構をサポートすることができるネットワークは、前述の問題のうちのいくつかを軽減することができる。そのような協調的移送ネットワークの一例は、バレッジ中継網（ＢＲＮ）である。バレッジ中継網（ＢＲＮ）の特徴は、層１での協調的通信を利用するフラッディング機構を介してネットワーク全体にわたり情報を同報通信するための効率的プロトコルの定義である。特に、この協調的方式は、ノードが明示的に調整する必要はなく、そうではなくて、協調的動作が層１で知的信号設計技法を介して黙示的に出現するという点で、完全に自律的である。
【００２４】
図３は、独立した媒体割当てが時分割多重アクセス（ＴＤＭＡ）方式を介して得られる、アドホックネットワークの一実施形態を示す。具体的には、図３に示す実施形態で、時間はフレームに分割され、そのフレームは、フレームごとにＭ≧３スロットにさらに分割される（「Ａ」、「Ｂ」、及び「Ｃ」のラベルを付されたフレームごとのＭ＝３スロットが、図３には示される）。一実施形態で、中央ノード３０１は、第１のＴＤＭＡフレームのスロットＡでパケットを送信する。そのような一実施形態で、このパケットを無事に受信するすべてのノードは、定義によって、ソースから１ホップ離れている。これらの「１ホップノード」は、図３では３１１、３１２、・・・３１７のラベルを付される。１ホップノードは、同パケットをスロットＢで送信し、それにより、そのソースから２ホップ離れたノード（「２ホップノード」３２１、３２２、・・・３２９）であって、順に同パケットをスロットＣで送信するノードに中継する。そのソースから３ホップ離れたノード（「３ホップノード」３３１、３３２、・・・３３７）は、第２のＴＤＭＡフレームのスロットＡでそのパケットを中継する。このように、パケットは、ソースから外側に送信する。いくつかの実施形態で、中継伝送がソースへと戻って伝搬することを防ぐために、各ノードは、所与のパケットを一度のみ中継する。たとえば、一実施形態で、１ホップノードは、第１の同報通信パケットをスロットＡで（ソースから）、そしてさらにスロットＣで（２ホップノードから）受信するが、スロットＢでのみ中継することになる。
【００２５】
図３に示す実施形態では、いくつかの２ホップノードが、異なる１ホップノードから同スロットでパケットを受信し得る。いくつかの実施形態で、これらのパケットは、ＢＲＮによって使用される物理（「ＰＨＹ」）層処理により、衝突しない。具体的には、ＢＲＮは、従来のノード受信機におけるマルチパス軽減に類似した形で同一パケットが受信機で結合されることを可能にするＰＨＹ層を使用する。たとえば、いくつかの実施形態で、複数の、ＢＲＮで生じる受信された信号の場合によっては時間移動されたコピーは、異なる送信ノードに由来しないが、反射、たとえば単一のソースが送信するときの建造物、に由来するかのように、受信機で処理され得る。
【００２６】
いくつかの実施形態で、時間スロットの１つのタイプの空間的再使用は、あらゆるＭスロットの送信のためのソースにパケットがパイプライン化されることを可能にする（「空間的パイプライン方式」）。たとえば、図３に示す実施形態で、１ホップノードは、第２のＴＤＭＡフレームのスロットＡ中に３ホップノードによってパケット同報通信を受信しないことになる。したがって、ソースは、そのスロット中に第２のパケットを安全に送信することができる。この方式では、Ｗ／Ｍの処理能力が、単一ソースを有するＢＲＮにおける同報通信のために獲得され得る（Ｗは、単一の二地点間リンクの容量であり、そして、Ｍは、連続するソース送信間のスロットでの間隔として定義された「空間的再使用係数」である）。
【００２７】
いくつかの実施形態で、経路指定テーブルは、ＢＲＮで同報通信するために維持される必要がない。さらに、いくつかの実施形態で、ユニキャスト及びマルチキャスト送信はまた、以下の基本バレッジ中継機構を介して達成され得る。すなわち、すべてのノードがパケットを中継するが、意図された宛先のみが、復号されたパケットをプロトコルスタックに渡す。
【００２８】
いくつかの実施形態で、バレッジ中継機構は、単一ソースノードからパケットを送信するための効率的方法を実現する。他の実施形態では、複数のソースがこの機構を介してデータを送信したいときにネットワーク化を実現するために、何らかの形のアクセス制御が必要とされる。たとえば、１つの解決法は、オペレータが、それらのノードを入力することによって媒体にアクセスし、衝突が標準手動操作プロトコルによって解決される、プッシュツートーク（ｐｕｓｈ−ｔｏ−ｔａｌｋ、「ＰＴＴ」）でもよい。しかし、ユーザに透過的なデータ伝送では、手動のオペレータ制御は十分ではないことがある。
【００２９】
いくつかの実施形態で、提案されているプロトコルは、ホップごと及びパケットごとを基本として単一リンクへのアクセスを制御しない。そうではなくて、提案されているプロトコルは、動的ネットワーク接続形態及びトラフィック状態の両方に受動的な形で複数の時間スロット及び複数のホップのバレッジ同報通信機構へのアクセスを調整する。この差異を強調するために、バレッジアクセス制御（ＢＡＣ）という用語は、本明細書では、バレッジ中継網上で結合層２／３機能性を実現するための提案されている機構を示すようになされる。
【００３０】
（単一フローバレッジアクセス制御プロトコル）
【００３１】
時間スロットごとに最大１つの明確なデータソースを可能にするＢＡＣプロトコルは、単一フロー（「ＳＦ−ＢＡＣ」）で示される。いくつかの実施形態で、ＳＦ−ＢＡＣプロトコルは、１セットのソースノード（ソースノードのこのセットはネットワークトラフィック要求に応答して時間とともに変化することに留意されたい）からネットワーク規模の同報通信（フラッディング）を時間多重化する。いくつかの実施形態で、ＳＦ−ＢＡＣプロトコルは、ユニキャスト、マルチキャスト、及び同報通信データのための結合層２／３機能性を実現する。しかし、データの単一のフローのみが、任意の所与の時間スロットでネットワークで活動状態である。したがって、単一フロー。以下では、複数のノードが同時間スロット中にソースの機能を果たすことを可能にする複数フローＢＡＣプロトコル  −  すなわち、時間及び空間の両方でバレッジ中継機構へのアクセスを制御するプロトコル  −  が、説明される。
【００３２】
（複数フローバレッジアクセス制御プロトコル）
【００３３】
図３に示す例示的ネットワークに戻ると、いくつかの実施形態で、以下の３つのユニキャストソース−宛先ペア、すなわち（１）ノード３１２（ソース）及び３３１（宛先）と、（２）ノード３１７及び３３６と、（３）ノード３２４及び３３２があるデータ伝送が行われる。いくつかの実施形態で、単一フローＢＡＣプロトコルは、それぞれ、ノード３１２、３１７、及び３２４からのネットワーク規模の氾濫を時間多重化することによってこれらの所望のデータフローを供することになる。
【００３４】
このＳＦ−ＢＡＣ手法は、以下のように代わりに動作するプロトコルよりも効率的ではないことがある。すなわち、
【００３５】
・各ＴＤＭＡフレームのスロットＡで、ノード３１２、３１７、及び３２４がパケットを送信する。ノード３２４によって送信されたパケットは、それの宛先（ノード３３２）によって受信される。
【００３６】
・各ＴＤＭＡフレームのスロットＢで、ノード３２２は、それがスロットＡで（ノード３１２から）受信したパケットを中継する。このパケットは、それの宛先（ノード３３１）によって順次に受信される。
【００３７】
・各ＴＤＭＡフレームのスロットＢで同時に、ノード３２８は、それがスロットＡで（ノード３１７から）受信したパケットを中継する。このパケットは、それの宛先（ノード３３６）よって順次に受信される。
【００３８】
・すべての他のノードは、スロットＢ又はＣで中継しない。
【００３９】
いくつかの実施形態で、前述のプロトコルの効率及びＢＲＮの利益を同時に実現するために、基本バレッジ機構の範囲を空間的に含むための何らかの機構が必要とされる。一実施形態で、これは、たとえば、制御されたバレッジ領域（Ｃｏｎｔｒｏｌｌｅｄ  Ｂａｒｒａｇｅ  Ｒｅｇｉｏｎ、「ＣＢＲ」）によって、達成され得る。一実施形態で、ＣＢＲは、データ送信のためのソース（「Ｓ」）及び宛先（「Ｄ」）を含む複数のノードの周りの１セットのバッファノードを指定することによって、確立され得る。そのような一実施形態で、他のソースノードからのパケットがＣＢＲに伝搬せず、Ｓからのパケットがネットワークの残りに伝搬しないように、バッファノードの中継機能が抑制される。
【００４０】
ＢＲＮでのパケット送信の範囲を制御するためのもう１つの実施形態は、各データパケットのヘッダ（前文）で２つの欄、すなわち有効期間（ｔｉｍｅ  ｔｏ  ｌｉｖｅ、ＴＴＬ）欄及びホップ計算（ｈｏｐ  ｃｏｕｎｔ、ＨＣ）欄を使用する。ホップ計算欄は、所与のパケットのソースによって１にセットされ、中継時に増やされ、一方、ＴＴＬ欄は、ノードを中継することによって変更されない。図３の例に戻ると、一実施形態で、２のＴＴＬは、ノード３０１によって送信されるパケットに組み込むことができる。そのような一実施形態で、このノードの１ホップ隣接ノードは、そのようなパケットを受信し、２にセットされたＨＣ欄を有する修正されたパケットを中継することになる。さらに、そのような一実施形態で、２ホップ隣接ノードは、ＨＣ＝２を有するパケットを受信し、それによって中継を停止する（受信されたＨＣ欄がＴＴＬ欄と等しいので）。いくつかの実施形態で、ＨＣ欄の変更は、ソースからの距離（ホップでの）に依存するので、そのソースから所与の距離にある各ノードは、同一パケットの複数のコピーをまだ受信することになる。
【００４１】
他の実施形態で、複数フローバレッジアクセス制御（「ＭＦ−ＢＡＣ」）プロトコルは、複数のデータソースが同時間スロットで送信することを可能にする機構を使用する。この方式では、複数のユニキャスト／マルチキャストフローが、任意の所与の時間スロットでそのネットワークで活動状態になり得る。いくつかの実施形態で、ＭＦ−ＢＡＣプロトコルは、ユニキャスト及びマルチキャストデータの結合層２／３機能性を実現することができる。いくつかの実施形態で、同報通信フローが活動状態にあるときにはいつでも、他のフローは、たとえＭＦ−ＢＡＣでも、活動状態ではあり得ない（すなわち、ＭＦ−ＢＡＣ及びＳＦ−ＢＡＣプロトコルは同報通信データのために完全に同じように動作することができる）。
【００４２】
（ＢＡＣプロトコルでのマルチパケット時間多重化）
【００４３】
図３に示すネットワークで動作するＳＦ−ＢＡＣプロトコルのもう１つの実施形態では、ネットワーク規模でデータパケットを同報通信したい２つのソースノードが存在し得る（たとえば、ノード３３２及び３３６）。そのような一実施形態で、ネットワーク直径は１０ホップであることが知られ得る。一実施形態で、アクセスは、（１）時間スロット１で、ノード３３２が、それの第１のパケット「Ｐ３３２，１」を１０のＴＴＬを有するネットワークに投入し、このパケットは、１０スロット内で基本バレッジ中継機構を介してネットワークを氾濫させる、（２）時間スロット１１で、ノード３３６が、１０のＴＴＬを有するそれの第１のパケット「Ｐ３３６，１」を投入する、（３）時間スロット２１で、ノード３３２が、それの第２のパケット「Ｐ３３２，２」を投入する、などによって調整され得る。各ソースは、Ｗ／１０の処理能力のためのこの単純な単一パケット時間多重化方式でＷ／２０の処理能力を体験する。
【００４４】
もう１つの実施形態では、アクセスが、マルチパケット方式で基本バレッジ中継機構への時間多重アクセスによって調整されることになり得る。たとえば、一実施形態で、ソースノード３３２及び３３６は、一度にＮパケットの媒体にアクセスする（Ｍ＝３の空間的再使用係数を有する）。そのような一実施形態で、アクセスは、以下によって調整され得る。すなわち、
【００４５】
・スロット１、４、７、・・・、３＊（Ｎ−１）＋１で、ノード１３２が、１０のＴＴＬを有するネットワークに、それぞれ、パケットＰ３３２，１、Ｐ３３２，２、・・・、Ｐ３３２，Ｎを投入する。これらのＮパケットは、パケットＰ３３２，ＮがスロットＴ≡３＊（Ｎ−１）＋１０によってネットワークのすべてのノードによって受信されるように、空間的にパイプライン化されたバレッジ中継機構を介してそのネットワークを氾濫させる。
【００４６】
・スロットＴ＋１、Ｔ＋４、Ｔ＋７、・・・、Ｔ＋３＊（Ｎ−１）＋１で、ノード１３６は、同様にネットワーク内に、それぞれ、パケットＰ３３６，１、Ｐ３３６，２、・・・、Ｐ３３６，Ｎを投入する。パケットＰ３３６，Ｎは、スロットＴ＋３＊（Ｎ−１）＋１０＝２Ｔによってネットワークのすべてのノードによって受信された。
【００４７】
・スロット２Ｔ＋１、２Ｔ＋４、・・・、２Ｔ＋３＊（Ｎ−１）＋１で、ノード１３２は、ネットワークにパケットＰ３３２，Ｎ＋１、Ｐ３３２，Ｎ＋２、・・・、Ｐ３３２，２Ｎを投入する、など。
【００４８】
そのような一実施形態で、各ソースは、このマルチパケット時間多重化方式でＷ＊Ｎ／（６＊Ｎ＋４）の処理能力を経験する。さらに、そのような一実施形態で、Ｎが大きくなるにつれて、合計処理能力は、Ｗ／３の単一ソース限界に近づく。ソース間の切り替えに関するオーバヘッド  −  すなわち、送信のために新しいパケットを投入する前のＭスロットではなくてＴＴＬスロットを待つこと  −  は、媒体が一度に複数のパケットの所与のソースによってアクセスされるときに、最小化される。
【００４９】
（バレッジ中継網へのアクセスを調整するためのシステム）
【００５０】
いくつかの実施形態で、ネットワークのノードは、以下の媒体割当ての２つの互いに干渉しないクラス、すなわちデータ及び制御を介して通信することができる。いくつかの実施形態で、データ割当て間の相互の独立性は、重複しない時間スロット（すなわち、「時間スロッティング」）を介して達成される。集合体で考えるとき、データ時間スロットは、データチャネルと称される。データ及び制御チャネルの間の独立性は、時間スロッティング、異なる周波数チャネル、異なるアンテナ放射パターン、及び低い相互相関拡散シーケンス、並びにこれらの技法の任意の組合せを含むがこれらに限定されない多数の機構によって達成され得る。さらに、いくつかの実施形態で、制御チャネルは、複数の互いに独立したサブチャネルにさらに細分化され得る。
【００５１】
いくつかの実施形態で、本発明は、いくつかの実施形態でソースノードから宛先ノードへのユーザデータの移送のために使用され得るデータチャネルへのアクセスを調整することができる。データチャネル資源の調整は、制御チャネル（又は複数のチャネル）で動作するＢＡＣプロトコルを介して実行される。
【００５２】
ＢＡＣプロトコルの動作を定義するために使用することができる多数の特定の規則セットがある。本明細書で開示されるＢＡＣプロトコルは、将来のデータチャネル（「ＤＣ」）に関して各ノードの状態を表にするデータチャネルスケジュール（「ＤＣＳ」）を使用する。たとえば、ネットワークの各ノードは、そのノードが（１）（場合によってはマルチ）パケット送信のソース（「Ｓ」）、（２）宛先ノード（「Ｄ」）、（３）中間中継ノード（「Ｒ」）、及び／又は（４）将来に向けていくつかの時間スロットの任意の送信に関与しないノード（「Ｕ」）であるかどうかを定義するＤＳＣを保持することができる。
【００５３】
いくつかの実施形態で、ＳＦ−ＢＡＣプロトコルは、それが最大１つのインスタンスが任意の所与の時間スロットでデータソースとしてスケジュールされることを可能にするという点で、ＭＦ−ＢＡＣプロトコルと区別され得る。ＭＦ−ＢＡＣプロトコルは、複数のノードが同時間スロットでソースとしてスケジュールされることを可能にするための機構を使用する。
【００５４】
（概念的ＳＦ−ＢＡＣプロトコルでのデータチャネルスロットのスケジューリング）
【００５５】
図４は、図１及び２で使用される同グラフィック規定に従ったサンプルネットワーク接続形態を示す（すなわち、ノードは円によって表され、ノードのペアの間のワイヤレスリンクは線によって表される）。図４に示す例示的ネットワークで、４１１及び４５１のラベルを付された２つのノードが、互いにデータを送信しようとする。すなわち、以下の２つの保留のユニキャスト送信、すなわちソースノード４１１から宛先ノード４５１への１つの通信と、ソースノード４５１から宛先ノード４１１への第２の通信がある。ノード４１１及び４５１で送信を待つパケットの待ち行列は、それぞれ、４６１及び４７１のラベルを付される。
【００５６】
いくつかの実施形態で、資源の公正な共用を確保するために、各ノードは、一度に１０パケットまでのデータの送信を予約することを許される（「パケット」という用語は、送信のための単一時間スロットに適合し得るデータの量を示すために使用される）。ソースノードによって予約することができる連続する時間スロットのサイズを制限することによって、共用される媒体を介する送信に固有の遅延は、公平に分散され得る。
【００５７】
たとえば、一実施形態で、ノード４１１は、先ず、１０パケットのデータを送信するために、ＤＣ資源を要求することができる。これは、たとえば、ＳＦ−ＢＡＣプロトコルを介して達成され得る。空間的再使用係数Ｍを有する時間スロット化されたＢＲＮでのＬスロットの有効期間を有するＮパケットの送信は、
Ｍ＊（Ｎ−１）＋Ｌ
の連続するＤＣ時間スロットが予約されることを必要とする。この例示的実施形態で、Ｎ＝１０、Ｍ＝３、そして、有効期間はＬ＝４にセットされ得る。したがって、３１ＤＣ時間スロットが、ノード４１１からノード４５１への１０パケットのデータのマルチホップ送信をサポートするために、予約される必要がある。
【００５８】
いくつかの実施形態で、ＳＦ−ＢＡＣプロトコルは、ネットワークの各々のノードでＤＣＳを更新することによって、ノード４１１からの要求に応答する。図５は、３つのタイプのノード（ソース、中継、宛先）でのＤＣＳの例示的実施形態を用意する。図５に示す実施形態で、ノード４１１からの送信は、ｔ＝１００のラベルを付された時間スロットで開始するようにスケジュールされる。そのような一実施形態で、５１１、５２１、５４２、及び５５１のラベルを付されたＤＣＳは、図４の、それぞれ、ノード４１１、４２１、４４２、及び４５１に対応し得る。図５に示す実施形態で、すべての中間（中継）ノードのＤＣＳは同一であり、したがって、ノード４２１及び４４２のＤＣＳのみが図５に示される。
【００５９】
図５に示すように、ソースノード５１１は、スケジュールされた転送に対応する時間スロット内の「Ｓ」のラベルを付された状態にあり、中継ノード５２１、５４２は、「Ｒ」のラベルを付された状態にあり、そして、宛先ノード５５１は「Ｄ」のラベルを付された状態にある。転送がスケジュールされていない時間スロットは、関与しない（ｕｎｉｎｖｏｌｖｅｄ）の「Ｕ」のラベルを付される。
【００６０】
ノード４５１は、ソースノードとしてのノード４５１での１０パケット送信に必要とされる時間スロットがＳＦ−ＢＡＣプロトコルを介して予約されることを要求する。図６は、対応するＤＣＳ更新を示す。図６に示すように、中間ノード（ノード４２１、４２２、４３１、４３２、４４１、及び４４２）は、両方の送信で中継の機能を果たし、一方、ノード４１１及び４５１は、交代でソースノードになる。
【００６１】
この実施形態で、ノード４１１及び４５１は、ユーザに透過的なラウンドロビン方式でＤＣ時間スロットを共用する。したがって、たとえば、任意の所与の時間にＤＣで単一ソースに使用可能なＷ／Ｍ＝２Ｘの帯域幅がある場合、次いで、ノード４１１及び４５１によって達成される平均合計処理能力は、２Ｘに近づくことになる。
【００６２】
ＢＡＣを使用するアクセスプロトコルと従来の層２／３プロトコルの差異は、ＢＡＣでは、アクセスが、一度にすべてのマルチホップ、マルチパケット送信のすべてのホップ及びすべてのパケットについて調整されるということである。各々の予約されたセットの連続するＤＣ時間スロット内で、基本バレッジ中継機構が使用されて、選択されたソースノードから選択された宛先ノード（複数可）にパケットを急速に伝搬する。いくつかの実施形態では、マルチキャスト及び同報通信送信をシームレスにサポートするために、宛先（「Ｄ」）ノードの中継機能は抑制されない  −  すなわち、関与しない（「Ｕ」）ノードのみが、基本バレッジ中継機構に従って、受信されたパケットを転送しない。
【００６３】
（単一フローＢＡＣプロトコルの説明）
【００６４】
いくつかの実施形態で、ＳＦ−ＢＡＣプロトコルは、１セットのソースノードにわたってＤＣへのアクセスを調整するために、２つの制御サブチャネル  −  要求サブチャネル（「ＲＳＣ」）及び確認サブチャネル（「ＣＳＣ」）  −  で送信されるメッセージを使用する（どのノードがデータを調達することを望むかは、ネットワークトラフィック要求に応答して時間により変化することになる）。いくつかの実施形態で、ＲＳＣ及びＣＳＣサブチャネルの両方は、ネットワーク全体で制御メッセージを速く及び確実に広めるために、基本バレッジ中継同報通信機構を使用する。さらに、いくつかの実施形態で、ＲＳＣ及びＣＳＣサブチャネルでの各同報通信は、一定の、限定された有効期間（「ＴＴＬ」）を備える。
【００６５】
いくつかの実施形態で、ノードは、（１）ソースＵＩＤ、（２）宛先ＵＩＤ、及び（３）送信のために要求されたパケットの数Ｎを備えるＲＳＣでバレッジ要求（「ＢＲＱ」）メッセージを送信することによって、データ送信をスケジュールすることができる。ネットワークスケジュールリーダ（以下「ＮＳＬ」）がＢＲＱメッセージを受信するときには必ず、ＮＳＬは、（１）ソースＵＩＤ、（２）宛先ＵＩＤ、（３）スケジュールされたパケットの数Ｎ、及び（４）スケジュールされた送信の開始スロットを指示するＣＳＣでの対応するバレッジスケジューリング確認（ＢＳＣ）メッセージを送信する。いくつかの実施形態で、ネットワークの各ノードは、ＢＳＣメッセージ内の情報を使用して、それに応じてそれのスケジュールを更新するように構成され得る。いくつかの実施形態で、送信の終了スロットが開始スロット及び送信されるパケットの数Ｎによって一意に判定されるように、一定の空間的パイプライン化係数及び一定のＴＴＬ値が、すべての送信に使用される。
【００６６】
いくつかの実施形態では、単一ノード（ネットワークスケジュールリーダ）はＢＳＣメッセージを送信するので、異なるＢＳＣメッセージの衝突がＣＳＣで回避される。他の実施形態では、ネットワークの任意のノードがＲＳＣで送信することができるので、異なるソースからのＢＲＱメッセージの衝突が生じ得る（たとえば、２つのノードが同時間スロットにＢＲＱメッセージを送信するときにはいつでも）。２つの異なるＢＲＱメッセージ間のＲＳＣチャネルでの衝突は、一方又は両方がＮＳＬノードによって受信されない結果をもたらすことがあり、その場合、ＣＳＣでの対応するＢＳＣメッセージは生じないことになる。ＲＳＣ及びＣＳＣでの任意のメッセージのＴＴＬは限定されるので、ＢＲＱメッセージを送信又は中継するノードは、衝突の発生を検出することができる（すなわち、ＢＳＣが所定の数の時間スロット内に受信されない場合、それはＮＳＬによって送信されなかったと推測され得る）。
【００６７】
いくつかの実施形態で、２つの規則が、ＲＳＣでのＢＲＱ衝突の効果を限定及び軽減するためにネットワークによって実装され得る。すなわち、
【００６８】
１．ノード「Ｘ」が別のノード「Ｙ」からＲＳＣでＢＲＱメッセージを受信するときには必ず、（ｉ）ノードＹからのそのＢＲＱに対応するＢＳＣがＣＳＣで受信されるか、（ｉｉ）対応するＢＳＣが受信されないであろうと推測され得るような、十分な数の時間スロット（ＲＳＣでの）が経過するかのいずれかまで、ノードＸは、それ自体のＢＲＱ送信を抑制する。
【００６９】
２．それが所定の最大数の時間スロット内に送信するＢＲＱに応答してＢＳＣを受信しない任意のノードＸは、ＲＳＣが輻輳している（すなわち、異なるソースからのＢＲＱメッセージ間の衝突が生じている）と推測し、ＢＲＱを再送信するまで無作為な数の時間スロット控える。
【００７０】
もう１つの実施形態で、ノードは、それらのローカルＤＣＳに基づいてＢＲＱメッセージの送信を抑制することができる。たとえば、一実施形態で、ＳＦ−ＢＡＣプロトコルは、任意の所与のＤＳＣにおいて所与のソースに割り当てられ得るＤＣスロットの総数を制限する規則を含み得る。もう１つの実施形態で、ＳＦ−ＢＡＣプロトコルは、すべてのソースを介してスケジュールされ得るスロットの総数を制限することができる。さらにもう１つの実施形態で、要求される転送の最小及び最大の許容サイズ（送信されるパケットに関する）が、制御され得る。
【００７１】
さらにもう１つの実施形態で、ＢＲＱ及びＢＳＣは、共通の制御チャネルを介して送信され得る（すなわち、ＲＳＣとＣＳＣの間に区別はない）。そのような一実施形態で、前述で定義された規則が適用される場合、ノードＸからのＢＲＱメッセージ（「ＢＲＱ−Ｘ」）とノードＹによって始動された要求に対応するＢＳＣメッセージ（「ＢＳＣ−Ｙ」）の間の衝突は、ノードＸがノードＹから対応するＢＲＱメッセージ（「ＢＲＱ−Ｙ」）を前に受信しなかったときにのみ生じることになる。そのような一実施形態で、ＢＲＱ−ＸとＢＳＣ−Ｙの間の衝突は、以下をもたらし得る。すなわち、
【００７２】
１．ＢＲＱ−Ｘが、ＮＳＬによって受信されない。そのような一実施形態で、ノードＸは、ＢＲＱ−Ｘを時間切れにし、再送信することができる。
【００７３】
２．ＢＳＣ−Ｙが、ノードＹによって受信されない。この場合、ノードＹは、ＢＲＱ−Ｙを時間切れにし、再送信することになる。そのような一実施形態で、ＢＳＣ−Ｙの内容によって定義されたＤＣ時間スロットは、無駄になり得る（すなわち、どのノードもそれらのスロットで送信しないことになる）。
【００７４】
３．ＢＳＣ−Ｙは、ノードＹによって受信されるが、ＢＳＣ−Ｙによって定義されたＤＣ時間スロット中に関与しない（「Ｕ」）状態のままであることになるいくつかのサブセットの中継／宛先ノードによって受信されない。そのような一実施形態で、関与しないノードは、ノードＸからノードＹにデータ伝送を中継することができない。しかし、ＳＦ−ＢＡＣプロトコルは、Ｕスロットで受信された任意のパケットが中継されるように、修正することができる。
【００７５】
もう１つの実施形態で、ＮＳＬは、同報通信及びマルチキャストトラフィックに対応するＢＳＣメッセージを生成する責任のみを負う。この実施形態で、ユニキャスト送信の宛先ノードは、ＢＳＣメッセージを生成する責任を負う。いくつかの実施形態で、本技法を使用するＳＦ−ＢＡＣプロトコルは、１ホップ及び２ホップユニキャスト送信の処理能力の増加を可能にする。そのような一実施形態で、ＢＲＱメッセージ内のホップ計算欄は、ソースと宛先の間の距離（ホップで）を判定するために使用され得る。そのような一実施形態で、スケジュールされた送信の有効期間及び空間的再使用係数Ｍが、次いで、セットされ得る。
【００７６】
（隠された制御されたバレッジ領域問題）
【００７７】
いくつかの実施形態で、ＳＦ−ＢＡＣプロトコルは、ＤＣでパケットのＴＴＬ欄を介して１ホップ及び２ホップユニキャスト送信の空間的範囲を制御する。いくつかの実施形態で、ＣＢＲはまた、ユニキャスト送信の空間的範囲を含むために使用され得る。
【００７８】
一実施形態で、ＭＦ−ＢＡＣプロトコルは、ＣＢＲを使用することができる。そのような一実施形態で、たとえば、ＤＣＳ内のすべての時間スロットは、ソース（「Ｓ」）、宛先（「Ｄ」）、中継（「Ｒ」）、又は関与しない（「Ｕ」）状態のうちの１つでもよい。そのような一実施形態で、ノードが新たな転送をスケジュールするとき、そのノードは、Ｕ状態で前にスケジュールされたスロットでのみそれを行うことができる。ＣＢＲをサポートするために、第５のスケジュールされた時間スロット状態、すなわちバッファ（「Ｂ」）状態が定義される。いくつかの実施形態で、Ｂ状態は、中継に関してＵ状態と同一である  −  すなわち、ノードは、Ｂスロット中に受信されたパケットを転送しない  −  しかし、スケジューリングに関してＲ状態と同一である  −  すなわち、新たな転送は、Ｂ状態で前にスケジュールされたスロットでスケジュールすることはできない。
【００７９】
もう１つの実施形態で、ＳＦ−ＢＡＣプロトコルは、以下のようなＭＦ−ＢＡＣプロトコルの基礎の役割を果たし得る。すなわち、
【００８０】
１．ソースノード「ｒＳ」が、宛先ノード「ｒＤ」へのマルチパケットユニキャスト送信を始動したいとき、ソースノード「ｒＳ」は、ＨＣ欄を含むＲＳＣでＢＲＱを同報通信する。そのような一実施形態で、このＢＲＱメッセージを受信するネットワークのあらゆるノード「ｒＸ」は、それにより、Ｓからのホップでのそれの距離、ｄ（ｒＳ→ｒＸ）、を確認する。
【００８１】
２．ノード「ｒＤ」は、ＨＣ欄、及びＣＳＣでの同報通信であるｄ（ｒＳ→ｒＤ）を含むＢＳＣメッセージでＢＲＱに応答する。
【００８２】
３．このＢＳＣメッセージを受信するネットワークのあらゆるノード「ｒＹ」は、それにより、ｒＤからのホップでのそれの距離、ｄ（ｒＤ→ｒＹ）、並びにソース−宛先距離ｄ（ｒＳ→ｒＤ）を確認する。
【００８３】
４．ＢＳＣパケットを受信したとき、
ｄ（ｒＳ→ｒＲ）＋ｄ（ｒＤ→ｒＲ）＝ｄ（ｒＳ→ｒＤ）
を満たすいずれのノード「ｒＲ」（ｒＳ及びｒＤ以外）も、中継状態でＢＳＣパケットデータによって定義された転送をスケジュールする。
【００８４】
５．ＢＳＣパケットを受信したとき、
ｄ（ｒＳ→ｒＢ）＋ｄ（ｒＤ→ｒＢ）＝ｄ（ｒＳ→ｒＤ）＋１
を満たすいずれのノード「ｒＢ」も、バッファ状態でＢＳＣパケットデータによって定義された転送をスケジュールする。
【００８５】
６．ＢＳＣパケットを受信したとき、
ｄ（ｒＳ→ｒＵ）＋ｄ（ｒＤ→ｒＵ）＞ｄ（ｒＳ→ｒＤ）＋１
を満たすいずれのノード「Ｕ」も、それのＤＣＳを更新しない。
【００８６】
図７は、図１及び２で使用される同グラフィック規定（すなわち、ノードは円によって表され、ノードのペアの間のワイヤレスリンクは線によって表される）に従ったサンプルネットワーク接続形態を示す。一実施形態で、ノード７０１及び７０５は、１つのユニキャスト送信のための、それぞれ、ソース及び宛先であり、一方、ノード７４１及び７４５は、第２のユニキャスト送信のための、それぞれ、ソース及び宛先である。そのような一実施形態で、ノード７０１は、ＲＳＣでＢＲＱメッセージを先ず送信することができ、そして、ノード７０５は、（ｉ）スロットｔ＝１００で開始するＤ状態で転送をスケジュールするノード７０５と、（ｉｉ）Ｓ状態で同転送をスケジュールするノード７０１と、（ｉｉｉ）Ｒ状態でスケジュールするノード７０２、７０３、及び７０４と、（ｉｖ）Ｂ状態でスケジュールするノード７１１、７１２、７１３、７１４、及び７１５とをもたらすＣＳＣでのＢＳＣメッセージで応答することができる。そのような一実施形態で、ノード７４１と７４５の間のＢＲＱ／ＢＳＣ交換に続いて、スロットｔ＝１００で開始する転送もまた、Ｓ状態にあるノード７４１と、Ｄ状態にある７４５と、Ｒ状態にある７４２、７４３、及び７４４と、Ｂ状態にある７３１、７３２、７３３、７３４、及び７３５とでスケジュールされ得る。この方式では、２つの空間的に区切られたフローが、同時にスケジュールされ得る。
【００８７】
さらに、もう１つの実施形態で、２つのソース−宛先ペアは、その代わりに、ノード７０３、７４３及び７３１、７３５である。そのような一実施形態で、７０３と７４３の間のＢＲＱ／ＢＳＣ交換は、先ず、時間ｔ＝１００に開始する適切な状態で適切なノードをスケジュールする。たとえば、ノード７３５がノード７３１からＢＲＱを受信するとき、ノード７３５は、たとえこの転送が７０３から７４３への前にスケジュールされた転送と矛盾（たとえば、ノード７２３が７０３と７４３の間の並びに７３１と７３５の間のＣＢＲの中継である）しても、転送が時間ｔ＝１００に開始しなくてはならないと指示するＢＳＣで応答することができる。このエラーは、スケジュールされた７０３→７４３ＣＢＲがノード７３５から「隠されて」いるので生じる。
【００８８】
（３位相ＭＦ−ＢＡＣプロトコルの説明）
【００８９】
いくつかの実施形態で、隠されたＣＢＲ問題から生じるスケジューリングエラーは、以下のような３位相プロトコルを介して緩和され得る。すなわち、
【００９０】
１．ソースノード「ｒＳ」が宛先ノード「ｒＤ」へのマルチパケットユニキャスト送信を始動するとき、ソースノード「ｒＳ」は、ＨＣ欄を含むＲＳＣでＢＲＱを同報通信する。このＢＲＱメッセージを受信するネットワークのあらゆるノード「ｒＸ」は、それにより、Ｓからのホップでのそれの距離ｄ（ｒＳ→ｒＸ）を確認する。
【００９１】
２．ノード「ｒＤ」は、ｒＤによって確認されたように、ＨＣ欄、ｄ（ｒＳ→ｒＤ）及び転送の潜在的開始時間を含むバレッジ調査（Ｂａｒｒａｇｅ  ＥＸｐｌｏｒｅ、ＢＥＸ）メッセージでＢＲＱに応答する。
【００９２】
３．スケジュールされた転送に必要とされる時間スロットが、他の転送に現在関与しない場合、ノードはＢＥＸメッセージのみを中継する。
【００９３】
４．このＢＥＸメッセージを受信するネットワークのあらゆるノード「ｒＹ」は、それにより、ｒＤからのホップでのそれの距離ｄ（ｒＤ→ｒＹ）及びソース−宛先距離ｄ（ｒＳ→ｒＤ）を確認する。
【００９４】
５．ｒＳがＢＥＸメッセージを受信しない場合、次いで、スケジューリング矛盾が推測され、ｒＳは、次の要求を開始するのを無作為の数の時間スロット控える。
【００９５】
６．ｒＳがＢＥＸメッセージを受信する場合、次いで、前のＣＢＲと矛盾することなしにＢＥＸメッセージのデータに従ってスケジュールされ得るｒＳからｒＤへのＣＢＲがある。本プロトコルの第３の位相は、次いで、以下を開始する。すなわち、ｒＳがＢＳＣメッセージを送信する。ＢＥＸメッセージを前に中継したそれらのノードは、次いで、前述のＳＦ−ＢＡＣプロトコルごとに転送をスケジュールする。
【００９６】
この３位相ＭＦ−ＢＡＣプロトコルは、データ転送ごとに制御チャネルで送信される必要があるメッセージの数の増加を代償として、隠されたＣＢＲ問題を解決する。
【００９７】
図８は、本発明の一実施形態によるバレッジ中継網へのアクセスを調整するための方法のフローチャートである。いくつかの実施形態で、フローチャート９００のステップの順番は、変更することができる。さらに、フローチャート９００に示されたステップのうちのいくつかは、飛ばすことができ、又は、追加のステップが追加され得る。
【００９８】
図８に示すように、方法９００は、第１のノードが第２のノードから第１のメッセージを受信するときに９０２で始まる。いくつかの実施形態で、それらの２つのノードは、２つのサブチャネル（ＲＳＣ及びＣＳＣ）でチャネルを提示する。もう１つの実施形態で、ＢＲＱ及びＢＳＣは、共通の制御チャネルを介して送信され得る（すなわち、ＲＳＣとＣＳＣの間に区別はない）。いくつかの実施形態で、第１のメッセージは、ＲＳＣで送信されるＢＲＱメッセージを備える。
【００９９】
本方法は、第１のノードからのメッセージの送信を抑制することによって、ステップ９０４で継続する。たとえば、いくつかの実施形態で、メッセージの送信を抑制するステップは、第１のノードがＢＲＱメッセージを送信することを防ぐステップを含む。
【０１００】
ステップ９０６で、第１のノードが、第１のメッセージに対応する第２のメッセージを受信する、又は、第２のメッセージの受信なしに十分な時間待つ。たとえば、一実施形態で、第２のメッセージは、ＣＳＣで受信される第１のメッセージに対応するＢＳＣメッセージを備え得る。さらに、いくつかの実施形態で、十分な時間は、対応するＢＳＣが受信されないであろうと推測することができるような、ＲＳＣでのいくつかの時間スロットを備え得る。この十分な時間は、たとえば、対応するＢＳＣがエラーが原因で送信されなかった又は対応するＢＳＣがネットワークの別の送信と衝突したために、経過した可能性がある。ステップ９０８で、第１のノードからのメッセージの送信が、再起動される。
【０１０１】
図９は、本発明の一実施形態によるバレッジ中継網へのアクセスを調整するための方法のもう１つのフローチャートである。いくつかの実施形態で、フローチャート１０００のステップの順番は変更することができる。さらに、フローチャート１０００に示されたステップのうちのいくつかは、飛ばすことができる、又は追加のステップが追加され得る。
【０１０２】
図９に示すように、方法１０００は、第１のノードがＨＣ欄を備える第１のメッセージを送信するときに、１００２で開始する。いくつかの実施形態で、ＨＣ欄は、そのメッセージが通過したホップの数（すなわち、ノードの数）を測定するための欄を備え得る。
【０１０３】
本方法は、第１のメッセージが、第１のノードからのホップでの第１の距離を判定するノードによって受信されるときに、ステップ１００４で継続する。いくつかの実施形態で、それらの２つのノードは、２つのサブチャネル（ＲＳＣ及びＣＳＣ）でメッセージを送信する。もう１つの実施形態で、ＢＲＱ及びＢＳＣは、共通の制御チャネルを介して送信され得る（すなわち、ＲＳＣとＣＳＣの間に区別はない）。いくつかの実施形態で、第１のメッセージは、ＲＳＣで送信されるＢＲＱメッセージを備える。
【０１０４】
ステップ１００６で、第２のノードは、ＨＣ欄を備える第２のメッセージを送信する。いくつかの実施形態で、この第２のメッセージは、ＣＳＣで同報通信する及び第１のメッセージに対応するＢＳＣメッセージを備え得る。
【０１０５】
ステップ１００８で、第２のメッセージは、第２のノードからのホップでの第２の距離を判定するノードによって受信される。いくつかの実施形態で、その距離は、ホップで測定され得る。
【０１０６】
ステップ１０１０で、第１の距離と第２の距離の和が、第１のノードから第２のノードまでの距離と１ホップの和よりも大きいかが判定される。
【０１０７】
次いでステップ１０１２で、複数のデータメッセージの転送が、第２の制御メッセージの内容に従ってスケジュールされる。たとえば、一実施形態で、データ転送に対応するＤＳＣ時間スロットは、バッファ状態にあるものとしてＢＳＣパケットデータによって定義され得る。
【０１０８】
図１０は、本発明の一実施形態によるバレッジ中継網へのアクセスを調整するための方法のもう１つのフローチャートである。いくつかの実施形態で、フローチャート１１００内のステップの順番は、変更され得る。さらに、フローチャート１１００に示されたステップのうちのいくつかは、飛ばすことができる、又は追加のステップが追加され得る。
【０１０９】
図１０に示すように、方法１１００は、第１のノードがＨＣ欄を備える第１のメッセージを送信するときに１１０２で開始する。いくつかの実施形態で、ＨＣ欄は、そのメッセージが通過したホップの数（すなわち、ノードの数）を測定するための欄を備え得る。
【０１１０】
本方法は、第１のメッセージが、第１のノードからのホップでの第１の距離を判定するノードによって受信されるときに、ステップ１１０４で継続する。いくつかの実施形態で、それらの２つのノードは、２つのサブチャネル（ＲＳＣ及びＣＳＣ）でメッセージを送信する。もう１つの実施形態で、ＢＲＱ及びＢＳＣは、共通の制御チャネルを介して送信され得る（すなわち、ＲＳＣとＣＳＣの間に区別はない）。いくつかの実施形態で、第１のメッセージは、ＲＳＣで送信されるＢＲＱメッセージを備える。
【０１１１】
ステップ１１０６で、第２のノードが、ＨＣ欄及び潜在的開始時間を備える第２のメッセージを送信する。いくつかの実施形態で、第２のメッセージは、バレッジ調査（ＢＥＸ）メッセージを備え得る。さらに、いくつかの実施形態で、潜在的開始時間は、第１のノードと第２のノードの間のホップの数によって判定され得る。たとえば、一実施形態で、潜在的開始時間は、第１のノードと第２のノードの間のホップの数によって判定されるように、ＢＥＸメッセージが第２の（宛先）ノードに到達することができるより早い時間スロットにセットされ得る。
【０１１２】
ステップ１００８で、第２のメッセージが受信される。ステップ１１１０で、第２のノードからのホップでの距離が判定される。ステップ１１１２で、第１のノードから第２のノードまでの距離が判定される。いくつかの実施形態で、その距離は、ホップで測定され得る。
【０１１３】
ステップ１１１４で、第１のノードが、第２のメッセージを受信する。
【０１１４】
ステップ１１１６で、第１のノードが、第３のメッセージを送信する。いくつかの実施形態で、第３のメッセージは、ＢＳＣメッセージを備え得る。
【０１１５】
ステップ１１１８で、第１の距離と第２の距離の和が第１のノードから第２のノードまでの距離と１ホップの和より大きいかが判定される。
【０１１６】
ステップ１１２０で、受信ノードが、第３のメッセージを再び同報通信する。
【０１１７】
図１１は、本発明の一実施形態によるバレッジ中継網へのアクセスを調整するためのノードとして実装されるデバイスのブロック図である。図１１に示すように、システム１００は、メモリ１１０、プロセッサ１１２、ネットワークインターフェース１１４、及びネットワーク１１６を備える。
【０１１８】
プロセッサ１１２は、メモリ１１０に記憶されたコンピュータ実行可能プログラム命令を実行するように構成される。たとえば、プロセッサ１１２は、本発明の実施形態に従ってネットワークへのアクセスを調整するための１つ又は複数のコンピュータプログラムを実行することができる。プロセッサ１１２は、マイクロプロセッサ、デジタル信号プロセッサ（ＤＳＰ）、特定用途向け集積回路（ＡＳＩＣ）、１つ又は複数のフィールドプログラマブルゲートアレイ（ＦＰＧＡ）、状態機械、又は同様のものを備え得る。プロセッサ１１２は、プログラマブルロジックコントローラ（ＰＬＣ）、プログラマブル割込みコントローラ（ＰＩＣ）、プログラマブルロジックデバイス（ＰＬＤ）、プログラマブル読取り専用メモリ（ＰＲＯＭ）、電気的プログラマブル読取り専用メモリ（ＥＰＲＯＭ若しくはＥＥＰＲＯＭ）、又は他の同様のデバイスなどのプログラマブル電子デバイスをさらに備え得る。
【０１１９】
メモリ１１０は、プロセッサ１１２によって実行されるときに、本明細書に記載されたものなどの様々なステップをプロセッサ１１２に実行させる命令を記憶するコンピュータ可読媒体を備える。コンピュータ可読媒体の例は、プロセッサ１１２にコンピュータ可読命令を供給することができる電子、光、磁気、又は他の記憶又は送信デバイスを含むが、これらに限定されない。コンピュータ可読媒体の他の例は、フロッピディスク、ＣＤ−ＲＯＭ、磁気ディスク、メモリチップ、ＲＯＭ、ＲＡＭ、ＡＳＩＣ、構成されたプロセッサ、すべての光媒体、すべての磁気テープ又は他の磁気媒体、或いは、そこからコンピュータプロセッサがデータにアクセスすることができる任意の他の媒体を備えるが、これらに限定されない。加えて、様々な他のデバイスは、ルータ、専用若しくは公衆ネットワーク、又は他の送信デバイスなどのコンピュータ可読媒体を含み得る。プロセッサ１１２及び前述の処理は、１つ又は複数の構造体内でもよく、１つ又は複数の構造体全体に分散され得る。
【０１２０】
プロセッサ１１２は、ネットワークインターフェース１１４と通信する。ネットワークインターフェース１１４は、１つ又は複数のネットワーク接続を備え得る。ネットワークインターフェース１１４は、プロセッサ１１０をネットワーク１１６に接続する。ネットワーク１１６は、当技術分野で知られている多数のタイプのネットワークのうちの１つでもよい。たとえば、ネットワーク１１６は、ＢＲＮなどのワイヤード又はワイヤレスネットワークを備え得る。
【０１２１】
（概論）
【０１２２】
本明細書を目的として、別段の指示がない限り、本明細書で使用されるすべての数字は、「約」という用語によっていかなる場合にも修正されるものとして理解されるべきである。したがって、逆の指示のない限り、以下の明細書に記載の数値パラメータは、本発明によって取得されようとする所望の特性に応じて変化し得る概算である。少なくとも、本特許請求の範囲と同等の原理の適用を限定しようとするものではなく、各数値パラメータは、報告される有効数字の数を考慮して、そして通常の丸めの技法を適用することによって、少なくとも解釈されるべきである。
【０１２３】
本明細書での「なされた」又は「構成された」の使用は、追加のタスク又はステップを実行するようになされた又は構成されたデバイスを排除しない開かれた及び包括的な言語として意図される。加えて、「に基づく」の使用は、１つ又は複数の挙げられた状態又は値「に基づく」プロセス、ステップ、計算、又は他の動作が、実際には、挙げられたものを超える追加の状態又は値に基づき得るという点で、開かれた及び包括的であることを意図される。本明細書に含まれる見出し、リスト、及び番号付けは、説明を容易にすることのみを目的とし、限定を意図されていない。
【０１２４】
本発明の広い範囲を示す数値域及びパラメータは概算であるが、特定の例に示された数値は、可能な限り正確に報告される。しかし、いずれの数値も、本質的に、それらのそれぞれのテストの測定結果で見つけられた標準偏差から必然的に生じるある種のエラーを含む。さらに、本明細書で開示されるすべての範囲は、そこに含まれた任意の及びすべての部分的範囲を包含すると理解されるべきである。たとえば、規定された「１〜１０」の範囲は、最小値の１と最大値の１０の間の（及びそれらを含めた）任意の及びすべての部分的範囲、すなわち、最小値の１以上、たとえば１〜６．１、で始まり、最大値の１０以下、たとえば５．５〜１０、で終わるすべての部分的範囲、を含むと考えられるべきである。加えて、「本明細書に組み込まれる」として参照されたいずれの参考文献も、その参考文献全体が組み込まれるものとして理解されるべきである。
【０１２５】
本主題の態様による実施形態は、デジタル電子回路で、コンピュータハードウェア、ファームウェア、ソフトウェアで、又は、前述の組合せで実装され得る。一実施形態で、コンピュータは、１つ又は複数のプロセッサを備え得る。プロセッサは、プロセッサに結合されたランダムアクセスメモリ（ＲＡＭ）などのコンピュータ可読媒体を備える、又はそのようなコンピュータ可読媒体へのアクセスを有する。プロセッサは、センササンプリングルーチン、触覚効果選択ルーチン、及び前述のような選択された触覚効果を生成するための信号を生み出すための適切なプログラミングを含む、１つ又は複数のコンピュータプログラムの実行など、メモリに記憶されたコンピュータ実行可能プログラム命令を実行する。
【０１２６】
本主題は、その特定の実施形態に関して詳細に説明されることになるが、当業者は、前述の理解を達成したときに、そのような実施形態への修正、その変更、及びそれと同等のものを容易に生み出すことができることが、理解されよう。したがって、本開示は、限定ではなくて例示を目的として提示され、当業者に容易に明らかになるような本主題へのそのような修正、変更及び／又は追加の包含を除外しないことを理解されたい。
【０１２７】
本明細書で使用される、単数形「１つの（ａ、ａｎ）」及び「その（ｔｈｅ）」は、１つの指示対象に明示的に及び明白に限定されない限り、複数の指示対象を含むことにさらに留意されたい。
【図１】
0005884231.tif 000002
【図２】
0005884231.tif 000003
【図３】
0005884231.tif 000004
【図４】
0005884231.tif 000005
【図５】
0005884231.tif 000006
【図６】
0005884231.tif 000007
【図７】
0005884231.tif 000008
【図８】
0005884231.tif 000009
【図９】
0005884231.tif 000010
【図１０】
0005884231.tif 000011
【図１１】
0005884231.tif 000012