(57)【要約】  モバイルアドホックネットワーク（ＭＡＮＥＴ）は、発信元移動ノード、宛先移動ノード、及び複数の隣接移動ノードを含む。移動ノード群は、ビーコンを用いて、フレーム内の複数の時分割多重アクセス（ＴＤＭＡ）スロットを主張するよう動作可能である。各隣接ノードは、フレーム当たり１つのＴＤＭＡスロットを選択する。成功したビーコンに対する肯定応答を受信していない隣接ノード群は、空きＴＤＭＡスロットを主張し、且つ衝突検出機構を用いて、残った衝突を解消する。
2009543478.tif 000002
【特許請求の範囲】
【請求項１】
複数の移動ノードと、前記複数の移動ノードを結び付ける複数の無線通信リンクとを有する移動アドホックネットワークを動作させる方法であって：
発信元の移動ノードにｎホップの距離で隣接する移動ノード群から、ビーコンを用いて、フレーム内の複数のＴＤＭＡスロットを主張する段階；
各隣接ノードがフレーム当たり１つのＴＤＭＡスロットを選択する段階；
成功したビーコンに対する肯定応答を受信していない隣接ノード群が、空きＴＤＭＡスロットを主張する段階；及び
衝突検出機構を用いて、残った衝突を解消する段階；
を有する方法。
【請求項２】
前記隣接ノード群は２ホップの距離の範囲内に位置する、請求項１に記載の方法。
【請求項３】
各ノードは複数のフレームにわたって１つのＴＤＭＡスロットを維持する、請求項１に記載の方法。
【請求項４】
前記残った衝突を解消する段階は、ビーコン占有ベクトル内のビット群の隙間を用いることを有する、請求項１に記載の方法。
【請求項５】
前記残った衝突を解消する段階は、適宜選択された隣接ノードとビーコン送信時間を一時的に交換することによる選択隣接ノードとのメッセージ交換機構を用いて、ビーコンの衝突を検出することを有する、請求項１に記載の方法。
【請求項６】
発信元移動ノード；
宛先移動ノード；及び
ビーコンを用いてフレーム内の複数のＴＤＭＡスロットを主張するよう動作可能な複数の隣接移動ノードであり、各隣接ノードがフレーム当たり１つのＴＤＭＡスロットを選択し、成功したビーコンに対する肯定応答を受信していない隣接ノード群が、空きＴＤＭＡスロットを主張し、且つ衝突検出機構を用いて、残った衝突を解消する、複数の隣接移動ノード；
を有する移動アドホックネットワーク。
【請求項７】
各移動ノードは、他の移動ノードと無線通信するための通信装置と、前記通信装置による通信の経路を決定するコントローラとを有する、請求項６に記載の移動アドホックネットワーク。
【請求項８】
前記移動ノード群は、隣接移動ノード群がビーコン送信時間を一時的に交換し合うメッセージ交換機構を用いてビーコンの衝突を検出するよう動作可能である、請求項６に記載の移動アドホックネットワーク。
【請求項９】
複数の移動ノードを同期させるため当該ネットワークの全体に伝播されるタイミング基準、を更に有する請求項６に記載の移動アドホックネットワーク。
【請求項１０】
他の移動ノードが同期されるグローバルポジショニングシステムを含む移動ノード、を更に有する請求項６に記載の移動アドホックネットワーク。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、アドホック通信ネットワークに関し、より具体的には、アドホック通信にて用いられる時分割多重アクセス（ＴＤＭＡ）チャンネルアクセススケジューリングシステム及びその関連方法に関する。
【背景技術】
【０００２】
移動アドホックネットワーク（mobile  ad-hoc  network；ＭＡＮＥＴ）は、任意のトポロジーを形成するよう無線リンクによって接続されたモバイルルータ又は関連ホストの自己設定ネットワークとして機能し、ますます普及しつつある。例えば無線モバイル装置などのルータ群は無秩序に移動し、パケット無線ネットワークと同様に、ネットワーク内のノード群として該ルータ群自身を自由に編成する。個々の装置は最低限の設定を必要とするのみであり、それらの迅速な配備は、アドホックネットワークを緊急事態に適したものにし得る。例えば、多くのＭＡＮＥＴは、例えば統合戦術無線システム（Joint  Tactical  Radio  System；ＪＴＲＳ）やその他の同様のピアツーピアあるいは独立なベーシックサービスセットシステム（ＩＢＳＳ）等の軍用システム用に設計されている。
【０００３】
ＴＤＭＡ技術は、これらの移動アドホックネットワークシステムにおいてますます使用されるようになってきている。ＴＤＭＡアドホックネットワークにおいて、チャンネルアクセススケジューリングはネットワーク構造のプラットフォームである。マルチホップブロードキャスト網において使用される分散型チャンネルスケジューリングを用いると幾つかの問題が見受けられる。当業者に知られているように、最適チャンネルスケジューリングの問題は、数多くの出典で引用されている周知のＮＰ完全な問題であるグラフ彩色問題と等価である。多くの従来システムは、ネットワークトポロジーは既知であってトポロジートランスペアレントではないと仮定している。
【０００４】
ＴＤＭＡネットワークにおいてはトポロジー変更が存在する。ネットワークが形成される前には、トポロジーは分からない。ネットワークトポロジーを知ることなく、ネットワーク内のノード群は通信する手法を見出さねばならない。ノード群が隣接ノード群の間での送信・受信スケジュールを知ったときには、これらの隣接ノードは立ち去っていたり、消え去っていたりしていることがあり、また、新たなノード群が立ち入っていることもある。スケジューリングを決定するレートは、ネットワークが安定化され得るよう、高速且つ帯域幅的に効率的でなければならない。
【０００５】
加えて、分散型処理、オーバーヘッド帯域幅、及びネットワーク拡張性に関する問題が存在し得る。中央処理は、例えばネットワーク内の分割などのトポロジー変更を乗り切ることができないことがある。スケジューリングのためにネットワーク帯域幅を過大にすることは、トポロジーの変化に対する応答が遅くなり得る。スケジューリングは、高度に分散される場合、一層と良い状態になり且つ拡張可能になる。また、単一障害点（single  point  of  failure）は安定性及び収束速度の点でコストの高いものとなり得る。
【０００６】
固定インフラを有しない移動アドホックネットワークはまた、複数ユーザのメディアアクセス制御（ＭＡＣ）層に数多くの課題をもたらしてきた。ＴＤＭＡに基づくアドホックネットワークにおいては、ノード群に非干渉タイムスロットを割当て、帯域幅及びタイムスロットの空間的再使用を可能にすることは困難なときがある。十分に遠く離れた相異なるノードは、同一タイムスロットを用いることによって、帯域幅を再使用することができるであろう。
【０００７】
アドホックネットワーク用の、キャリア検知多重アクセス（ＣＳＭＡ）に基づくＭＡＣ設計は、移動ノード群の間でのデータ伝送に適しているときがある。例えば、８０２．１１規格は、伝送が主張（コンテンション）に基づくものであって非同期でないため、所望のサービスの質での音声トラフィック又はマルチメディアトラフィックをサポートしていない。無線資源の共有はしばしば非決定論的になる、音声ストリーム及びビデオストリームをサポートするためには、システムはしばしば帯域幅が予約されることを必要とする。これは、一部のＴＤＭＡに基づくスキームにおいては、例えばチャンネルスケジューリング等、非干渉タイムスロットを用いることによって達成され得る。
【０００８】
符号分割多重アクセス（ＣＤＭＡ）に基づくシステムは、伝統的なセル方式ネットワークにおいては帯域幅的に効率的であるが、近接／遠方効果を排除するための、基地局によって管理される、適切な電力制御に頼るものである。しかしながら、移動アドホックネットワーク環境においては、ＣＤＭＡ技術は幾つかの難問に遭遇してきた。
【０００９】
現在、移動アドホックネットワーク用のＴＤＭＡチャンネルスケジューリングに関して数多くのアルゴリズムが開発されている。しかしながら、これら提案された解決策の多くは、ネットワークトポロジーの十分な知識を有することに基づいている。このような方法は、ネットワーク全体に関する情報を収集することをプロセッサに要求するので、ネットワーク内において相当の量のオーバーヘッドを必要とし得る。一方、高度な移動アドホックネットワークにおいては、収集される情報は如何なる時においても古いものとなり得る。故に、移動アドホックネットワークにおけるメディアアクセス制御層の設計においては、オーバーヘッドの軽さ及びチャンネルスケジュールを生成することの相対速度が重要な要素となる。
【発明の概要】
【発明が解決しようとする課題】
【００１０】
アドホック通信にて用いられる時分割多重アクセス（ＴＤＭＡ）チャンネルアクセススケジューリングシステム及びその関連方法を提供する。
【課題を解決するための手段】
【００１１】
移動アドホックネットワーク（ＭＡＮＥＴ）は、発信元の移動ノード、宛先の移動ノード、及び複数の隣接移動ノードを含む。移動ノード群は、ビーコンを用いて、１つのフレーム内の複数の時分割多重アクセス（ＴＤＭＡ）スロットを主張するように動作する。各隣接ノードはフレーム当たり１つのＴＤＭＡスロットを選択する。成功したビーコンに対する肯定応答（アクナリッジメント）を受信していない隣接ノード群は、空きのＴＤＭＡスロットを主張し、衝突（コリジョン）検出機構を用いて、残った衝突を解消する。
【００１２】
１つの観点から、隣接ノード群は２ホップの距離の範囲内に位置付けられることができる。各ノードは複数のフレームにわたって１つのＴＤＭＡスロットを維持することが可能である。残った衝突はビーコン占有ベクトル（beacon  occupancy  vector；ＢＯＶ）内のビット群の隙間（void）を用いて解消され得る。残った衝突は、適宜選択された隣接ノードとビーコン送信時間を一時的に交換することによる選択隣接ノードとのメッセージ交換機構を用いてビーコンの衝突を検出することによって解消され得る。肯定応答メッセージは、単一フレーム内で、送信時間の基準とされる最も直近に聞かれたビーコン群を選択することによって、ビーコンに埋め込まれ得る。２レベルのＢＯＶを用いてＴＤＭＡスロット占有情報を隣接ノード群に供給し、移動なしによるトポロジー変化を補償することが可能である。
【００１３】
添付の図面を参照する以下の発明の詳細な説明により、本発明のその他の目的、特徴及び効果が明らかになる。
【図面の簡単な説明】
【００１４】
【図１】本発明に用いられ得る通信システムの一例を示すブロック図である。
【図２】本発明の非限定的な一例における、移動アドホックネットワーク（ＭＡＮＥＴ）を形成するために使用されるアルゴリズムを記述する基準を提供する一般化されたＴＤＭＡスキームを示すブロック図である。
【図３】本発明の非限定的な例に従って記述されたＭＡＮＥＴにおける、独立状態からネット形成状態への状態変化を示す状態図である。
【図４】本発明の非限定的な例に従って記述されたＭＡＮＥＴにおける、独立状態から３つのサブ状態を有する同期状態への状態変化を示す状態図である。
【図５】本発明の非限定的な例に従って記述されたＭＡＮＥＴの、１ホップの近傍内の６つの移動ノードの一例と、ほぼ３エポックの期間をカバーする、縦軸がノードＩＤを表し且つ横軸が増加する時間を表すタイミング基準として役割を果たすＧＳＮとして移動ノードを選出することとを示す、グラフ及び関連する移動ノード図である。
【図６】本発明の非限定的な例に従って記述されたＭＡＮＥＴの、衝突検出機構と、衝突のないネットワークトポロジー、衝突を有するネットワークトポロジーの有向グラフ、及びスケジュール交換のために変更された有向辺（有向リンク）とを示す、グラフ及び関連ノード図である。
【図７】本発明の非限定的な例に従って記述されたＭＡＮＥＴの、ネットワークが、全てが互いに１ホップ内にある６つのノードを有する場合の、３ＳＭＷ又はＧＰＳによる、スロット主張と確認処理とを示す、グラフ及び関連ノード図である。
【図８】本発明の非限定的な例に従って記述された、ＭＡＮＥＴの、２００個のノードを含むネットワークトポロジーの一例を示す、メートル単位の縦軸及び横軸を有するグラフである。
【図９ａ】本発明の非限定的な例に従って記述されたＭＡＮＥＴのグローバルコンフリクトトレースの一例を示す、横軸が秒を表し縦軸がコンフリクト数を表すグラフである。
【図９ｂ】本発明の非限定的な例に従って記述されたＭＡＮＥＴのネットワーク接続性の一例を示す、横軸がノードＩＤＳを表し縦軸が隣接ノード数を表すグラフである。
【図９ｃ】本発明の非限定的な例に従って記述されたＭＡＮＥＴの、衝突トレースの一例を示し且つスロットコンフリクト履歴を例示する、横軸が秒を表し縦軸が衝突指標を表すグラフである。
【図１０ａ】本発明の非限定的な例に従って記述されたＭＡＮＥＴの約１８秒にわたるシミュレーションによるグローバルコンフリクトトレースの一例を示す、横軸が秒を表し縦軸がコンフリクト数を表すグラフである。
【図１０ｂ】本発明の非限定的な例に従って記述されたＭＡＮＥＴの、ノード群が約３０ｍ／ｓでランダムな方向に移動する場合の、ノード移動のトレースの一例を示す、横軸及び縦軸の双方がメートルを表すグラフである。
【図１０ｃ】図９ｂに示したグラフと同様に、本発明の非限定的な例に従って記述されたＭＡＮＥＴのネットワーク接続性の一例を示す、横軸がノードＩＤＳを表し縦軸が隣接ノード数を表すグラフである。
【図１０ｄ】図９ｃに示したグラフと同様に、本発明の非限定的な例に従って記述されたＭＡＮＥＴの、衝突トレースの一例を示し且つ単一のノードからの衝突トレースの見込みを例示する、横軸が秒を表し縦軸が衝突指標を表すグラフである。
【発明を実施するための形態】
【００１５】
以下、本発明の好適な実施形態を示す添付の図面を参照して、本発明をより十分に説明する。本発明は、しかしながら、数多くの異なる形態に具現化されることが可能であり、ここで説明される実施形態に限定されると解されるべきではない。これらの実施形態は、この開示が完全なものとなり、当業者に本発明の範囲を十分に伝えるよう提供されるものである。全体を通して、同様の参照符号は同様の要素を指し示す。
【００１６】
ＴＤＭＡ動的チャンネルアクセススケジューリングに関する実用的な、帯域幅効率の良い、収束の速い分散型システム及びその関連方法を説明する。当該システム及び方法は、移動装置群又はノード群がスロット割当てを解決するように分散的に互いを助け合うことを当てにすることが可能である。
【００１７】
本発明の非限定的な一例に従って、ＴＤＭＡ移動アドホックネットワーク（ＭＡＮＥＴ）における自動ネットワーク形成は、隣接ノード群の相互支援に基づき得る。非限定的な一例において、システム及び方法は、隣接インダイレクト肯定応答アルゴリズム（Neighbors  Indirect  Acknowledgement  Algorithm；ＮｂＩＡ）と呼ぶことができる。当該システム及び方法にて使用されるこの種のアルゴリズムは、高速収束性。分散機構、及び低プロトコルオーバーヘッドを有する。隣接インダイレクト肯定応答アルゴリズムは、低い帯域幅オーバーヘッドを有する高速、分散型の同時チャンネルアクセススケジューリングアルゴリズムである。隣接ノード群が互いに、例えばビーコンスロットといったスロットを同時に見出すように支援し合う。それには、隣接ノード群が同時にそれらの狙うビーコンスロットを提案し合い、それと同時に最近の成功した主張に肯定応答するような分散機構が含まれる。その他の衝突は隣接ノードとの交換機構によって解消される。この種のシステム（又は機構）は高速収束性であり、ローカルアクセススケジューリングの大部分は数フレーム内で解決され得る。この機構はまた、低い帯域幅オーバーヘッドを有し、ビーコンの帯域幅は肯定応答メッセージが主張ビーコン内に埋め込まれるため低いものである。これは、この機構が調整すべき特定のヘッドを必要とせず、単一障害点が存在しないため堅牢である。
【００１８】
説明のため、図１を参照して、符号化、インターリービング、及び、移動アドホックネットワーク能力を含み且つ本発明に係るシステム及び方法とともに使用されるように変更されることが可能な、典型的な無線移動通信システムの背景情報を説明する。このようなシステム及び方法とともに使用され得る無線機の一例は、ハリス社により製造・販売されているＦａｌｃｏｎ（登録商標）III無線機である。理解されるべきことには、一般的に比較的標準的なプロセッサ及びハードウェア部品を用いて実装されることが可能なソフトウェア無線機を含む別の無線機も使用され得る。１つの特定種類のソフトウェア無線機は、無線機が使用する通信波形を実現するために何らかの適切な波形ソフトウェアモジュールとともに比較的標準的な無線機及び処理ハードウェアを含んだ統合戦術無線機（ＪＴＲ）である。ＪＴＲ無線機はまた、ソフトウェア通信アーキテクチャ（ＳＣＡ）仕様書（www.jtrs.saalt.milを参照）に準拠したオペレーティングシステムソフトウェアを用いる。なお、この仕様書の全内容をここに援用する。ＳＣＡは、様々な製造者及び開発者がそれぞれの要素群を単一の装置に容易に統合できるようにハードウェア及びソフトウェアの要素群をどのように相互運用するかを指定するオープンアーキテクチャフレームワークである。
【００１９】
統合戦術無線システム（ＪＴＲＳ）ソフトウェアコンポーネントアーキテクチャ（ＳＣＡ）は、ソフトウェア無線機（Software  Defined  Radio；ＳＤＲ）を実装するための、しばしばＣＯＢＲＡ（Common  Object  Request  Broker  Architecture）に基づく、一組のインタフェース及びプロトコルを定めている。部分的に、ＪＴＲＳ及びそのＳＣＡは、ソフトウェアにより再プログラム可能な無線機の系列とともに用いられる。このように、ＳＣＡは、ソフトウェアにより再プログラム可能なデジタル無線機を実現するための具体的なルール、方法、及び設計基準の組である。
【００２０】
ＪＴＲＳ  ＳＣＡ仕様書は、ＪＴＲＳ共同計画事務局（ＪＰＯ）によって出版されている。ＪＴＲＳ  ＳＣＡは、相異なるＪＴＲＳ  ＳＣＡ実装の間でのアプリケーションソフトウェアの移植性を提供し、開発コストを抑制するために商業規格を利用し、設計モジュールを再使用できることにより新たな波形の開発時間を削減し、且つ進化しゆく商用フレームワーク及びアーキテクチャを当てにするように構築されてきた。
【００２１】
ＪＴＲＳ  ＳＣＡは、実装に無関係であるように意図されているためシステム仕様ではなく、所望のＪＴＲＳの目的を達成するようシステム設計を制約する一組のルールである。ＪＴＲＳ  ＳＣＡのソフトウェアフレームワークは、動作環境（ＯＥ）を定め、その環境からアプリケーションが使用するサービス及びインタフェースを指定する。ＳＣＡのＯＥは、コアフレームワーク（ＣＦ）、ＣＯＢＲＡミドルウェア、及び付随のボード・サポート・パッケージを備えたポジックス（Portable  Operating  System  Interface；ＰＯＳＩＸ）に基づくオペレーティングシステム（ＯＳ）を有する。ＪＴＲＳ  ＳＣＡはまた、アプリケーションソフトウェア要素群の間のアプリケーション・プログラミング・インターフェース（ＡＰＩ）を定めるための構築ブロック構造を提供する（ＡＰＩ付録にて定められている）。
【００２２】
ＪＴＲＳ  ＳＣＡコアフレームワーク（ＣＦ）は、埋め込み分散型計算通信システム内での配備、維持管理、相互接続、ソフトウェアアプリケーション要素群の交信を提供するオープンソフトウェアインタフェース及びプロファイルの基本的な“コア”セットを定めるアーキテクチャ概念である。インタフェースは、ＪＴＲＳ  ＳＣＡ仕様にて定められ得る。しかしながら、開発者がそれらの一部を実装してもよいし、一部は非コアアプリケーション（すなわち、波形など）によって実装されてもよいし、一部はハードウェア装置供給者によって実装されてもよい。
【００２３】
単に説明のため、図１に示した非限定的な一例に関連して、本発明の恩恵を受ける通信システムの一例を簡単に説明する。この通信システム５０のハイレベルブロック図は、基地局部分５２、及び本発明とともに使用されるように変更され得る無線メッセージ端末を含んでいる。基地局部分５２は、ＶＨＦネット６４又はＨＦネット６６への無線リンク上で音声又はデータの通信及び送信を行うＶＨＦ無線機６０及びＨＦ無線機６２を含んでいる。ＶＨＦネット６４、ＨＦネット６６は、それぞれ、多数のＶＨＦ無線機６８、ＨＦ無線機７０と、無線機６８、７０に接続されたパーソナルコンピュータワークステーション７２とを含んでいる。アドホック通信ネットワーク７３が、図示した様々な構成要素とともに使用される。故に、理解されるべきことには、ＨＦ又はＶＨＦのネットワークは、インフラレスでアドホック通信ネットワークとして作用するＨＦ及びＶＨＦのネット部分を含んでいる。図示していないが、ＵＨＦの無線機及びＵＨＦネット部分も含まれ得る。
【００２４】
ＨＦ無線機は、非限定的な例として、復調回路６２ａ及び適切な畳み込みエンコーダ回路６２ｂ、ブロックインターリーバ６２ｃ、データランダム化回路６２ｄ、データ・フレーミング回路６２ｅ、変調回路６２ｆ、整合フィルタ回路６２ｇ、適切なクランプ装置を有するブロック又はシンボルの等化回路６２ｈ、デインターリーバ・デコーダ回路６２ｉ、モデム６２ｊ、及び電力適応回路６２ｋを含み得る。これら及びその他の回路は、本発明に必要な機能及び当業者によって提案される他の機能を果たすように動作する。全てのＶＨＦ移動無線機や送信局及び受信局を含む他の例示した無線機も、同様の機能回路を有し得る。
【００２５】
基地局部分５２は、ＰＡＢＸ８２に接続された公衆交換電話網（public  switched  telephone  network；ＰＳＴＮ）８０への地上通信接続を含んでいる。ＰＡＢＸ８２には、例えば衛星地上局などの人工衛星インタフェース８４が接続されている。ＰＡＢＸ８２はまた、プロセッサにより形成された無線ゲートウェイ８６ａ、８６ｂに接続されている。これらの無線ゲートウェイ８６ａ、８６ｂは、それぞれ、ＶＨＦ無線機６０、ＨＦ無線機６２に相互接続されている。上記プロセッサは、ローカルエリアネットワークを介してＰＡＢＸ８２及びＥメールクライアント９０に接続されている。無線機は適切な信号発生器及び変調器を含んでいる。
【００２６】
イーサネット(登録商標）（Ｅｔｈｅｒｎｅｔ(登録商標））／ＴＣＰ−ＩＰローカルエリアネットワークは、“無線”メールサーバとして動作し得る。Ｅメールメッセージは、第２世代プロトコル／波形としてＳＴＡＮＡＧ−５０６６を用いて、当然ながら好ましくは第３世代相互運用規格：ＳＴＡＮＡＧ−４５３８を用いて、無線リンク及びローカル無線ネットワーク上で伝送され得る。なお、ＳＴＡＮＡＧ−５０６６及びＳＴＡＮＡＧ−４５３８の全内容をここに援用する。相互運用規格のＦＥＤ−ＳＴＤ−１０５２も従来の無線装置で使用され得る。ＦＥＤ−ＳＴＤ−１０５２の全内容をここに援用する。本発明にて使用され得る装置の例は、ハリス社により製造される様々な無線ゲートウェイ及び無線機を含む。この装置は、非限定的な例として、ＲＦ５８００、５０２２、７２１０、５７１０、５２８５、並びにＰＲＣ１１７及び１３８シリーズの装置を含み得る。
【００２７】
これらのシステムは、ＲＦ−５７１０Ａ高周波数（ＨＦ）モデムを用いて、また、最大９，６００ｂｐｓのレートで長距離ＨＦ無線回路の伝送を提供するＳＴＡＮＡＧ４５３９として知られるＮＡＴＯ規格で動作可能である。なお、ＳＴＡＮＡＧ４５３９の全内容をここに援用する。モデム技術に加えて、これらのシステムは、例えばＳＴＡＮＡＧ４５３８又はＳＴＡＮＡＧ５０６６等のストレスのある戦術的なチャネル用に設計されてこれに適した一連のデータリンクプロトコルを使用する無線Ｅメールプロダクトを使用することができる。なお、ＳＴＡＮＡＧ４５３８及びＳＴＡＮＡＧ５０６６の全内容をここに援用する。ＩＳＢモードに設定された無線機及び固定データレートに設定されたＨＦモデムを用いて、１９，２００ｂｐｓほどの高さの固定の非適応的データレートを使用することも可能である。符号組み合わせ技術及びＡＲＱを使用することも可能である。
【００２８】
説明するように、この説明全体を通して多数の共通の用語が使用される。例えば、スロットはフレーム及びスロットにより構築される基本的なＴＤＭＡ時分割とし得る。多数のフレーム１００及びスロット１０２を示す図２に示されるように、秒ごとに典型的にＮ個のフレームが存在し、１つのフレームにはＭ個のタイムスロットが存在する。通常、アクティブな移動装置の各々は、全てのフレームにおいて送信を行う機会すなわちタイムスロットを有する。
【００２９】
フレームは、スロットを参照して説明される一般的なＴＤＭＡ時分割単位と見なし得る。
【００３０】
ビーコンは、通常は短く且つ１つのスロットで完結されるＴＤＭＡバーストとし得る。これは、制御情報又は制御されたメッセージを含み得る。ＨＰネットにおいて、１つのビーコンは１つのスロット内で送信されることができる。一般的なＴＤＭＡスキームにおいて、ビーコンは典型的に、一般的なタイムスロット内で送信される。
【００３１】
ビーコンスロットは一般的にスロットと同じである。
【００３２】
１ホップの近傍において、単一のリンクで直接的に接続された如何なる隣接ノードも１ホップ近傍と見なし得る。
【００３３】
２ホップの近傍において、最大で２ヒップで、２リンク分だけ離れて直接的に接続された如何なる隣接ノードも２ホップ近傍と見なし得る。
【００３４】
ネットワーク密度は、１ホップ近傍当たりのノード数、２ホップ近傍当たりのノード数、又は幾何学面積当たりのノード数として参照し得る。
【００３５】
ノードはネットワークトポロジー内の移動装置を表し得る。
【００３６】
ユーザは一般的にノードと見なされ、移動ユーザと呼ばれることもある。
【００３７】
内部タイミング基準（ＩＮＴＲ）は、典型的にその移動装置自体に知られたタイミング基準とし得る。
【００３８】
ネットワークタイミング基準（ＮＴＲ）は典型的に、例えば単一ＨＰネットといったネットワーク内で共通のタイミング基準である。これは、時期（エポック）又はフレームが開始すべき時を指し示し得る。ネットワーク内のノード群は典型的に、共通のタイミングをネットワークタイミング基準として合意する。ＧＰＳ（グローバルポジショニングシステム）が利用可能である場合、ＧＰＳはネットワークタイミング基準の発生源となり得る。
【００３９】
ＧＳＮは典型的に、ネットワークタイミング基準（ＮＴＲ）を提供するように選出されたノードである。
【００４０】
タイミングの同期化により、ネットワーク内でのフレームのタイミングは揃えられる。ノード群は、ＧＰＳに基づいたもの又は相互選出したＧＳＮに基づいたものとし得るＮＴＲに同期化される。
【００４１】
同期化により、ＮＴＲが達成されたとき、ネットワークは同期型と呼ばれ得る。ＨＰネットの場合、全てのノード群のエポックタイミングが揃えられたとき、ネットワークは同期型と見なされる。ＧＰＳが利用可能である場合、ノード群は容易に且つ直ちにＧＰＳタイミングに同期化される。
【００４２】
タイミング基準ノードを用いる場合、ネットワークタイミング基準を表すノードはＧＳＮと同一とし得る。
【００４３】
確認された状態においては、主張は成功し、成功に関する肯定応答が受信される。
【００４４】
肯定応答されることは、確認されることと同じである。
【００４５】
送信スケジューリングにおいて、ノードはフレーム内の何れのタイムスロットを使用すべきかを決定する。それは、送信スケジュールにおける後続の全てのフレームにおいて、そのスロットに固定され得る。故に、ネットワーク内の隣接ノード群とのスロットコンフリクトを解消するこのノードは、確立されたスケジュールを形成する。
【００４６】
ＴＤＭＡにおけるチャンネルアクセスにおいて、チャンネルは、複数フレームにおけるタイムスロットの独占使用によって定めることができる。ノードは、全ての後続フレームにおいて固定タイムスロットを使用することを許可されたとき、チャンネルを有すると見なされ得る。
【００４７】
チャンネル衝突は複数フレームにおける連続的なスロット衝突とし得る。これは通常、フレーム内の同一スロットである同一のネットチャンネルにて送信しようとする２つ以上のノードによって生じる。
【００４８】
チャンネルアクセススケジューリングは、送信スケジューリングと同一とし得る。
【００４９】
固有のノードＩＤは、ノードの物理的な、固有のメディアアクセス制御（ＭＡＣ）アドレスとし得る。例えば、ネットワークの大きさが２００である場合、固有ＩＤに必要な最小ビット数は８ビットとなる。
【００５０】
ビーコン占有ベクトル（ＢＯＶ）は、各ビットがスロット占有期間を表すビットマップである。数字の１はスロットが用いられることを表し、数字の０はスロットが空いていることを表し得る。ＢＯＶビットマップはＢＯＶと同一とし得る。
【００５１】
自動ネットワーク形成は、全ての隣接ノードの相互支援に基づき得る。当該システム及び方法に用いられるアルゴリズムは、本発明の非限定的な態様に従って、隣接インダイレクト肯定応答アルゴリズム（ＮｂＩＡ）と呼び得る。このアルゴリズムの主な特質は、高速収束性、分散機構、及び低プロトコルオーバーヘッドである。隣接インダイレクト肯定応答アルゴリズム（ＮｂＩＡ）は典型的に、低い帯域幅オーバーヘッドを有する高速分散型同時チャンネルアクセススケジューリングアルゴリズムである。隣接ノード群が互いに、スロットを同時に見出すように支援し合う。これは分散機構であるため、“ｎ”全ての隣接ノードが同時にそれらの狙うスロットを提案し合い、それと同時に、最近の成功した主張に肯定応答する。残りの衝突は隣接ノードとの交換機構によって解消され得る。高速収束性により、ローカルアクセススケジューリングの大部分は数フレーム内で解決されることが可能である。ビーコンの帯域幅要求は、肯定応答メッセージが主張ビーコン内に埋め込まれるため低いものである。これはまた、この機構はスケジューリングを調整するための特定のヘッドを必要としないため堅牢である。単一障害点は存在しない。
【００５２】
図３は、状態図の一例１１０であり、独立状態１１２から、同期／再同期１１４、スロット主張１１６及びスロット固定１１８と示したネット形成状態群への主な状態変化を示している。状態図１１０は表１に記載した一定の事象を有する。
【００５３】
【表１】
2009543478.tif 000003
図３に示した状態図及び図４に示す状態図において、表示された状態は主状態である。これは、アルゴリズムにおける同時性且つフレキシブルな状態フローを例示している。“独立”状態１１２から“同期”状態１１４へ変化された詳細な選択状態の組は、図３において簡略化されている。
【００５４】
より詳細な同期状態図を、独立状態から同期状態への状態変化を描いた図４に示す。この状態図１２０は、独立起動１２２、独立接続性１２４、及び独立候補１２６を含んでいる。この図は、ＧＳＮの同期／再同期１２８、ＮＴＲがＧＳＮであるとき１３０、及びＮＴＲがＧＰＳであるとき１３２を含んでいる。同期状態はこれら３つのサブ状態１２８、１３０、１３２を有する。これらの状態は、図３においては、“独立”１１２及び“同期・再同期”１１４という２つの区別した状態に統合されている。事象群は、表２に記載されるとともに、図５のグラフ及び略図に関連する。
【００５５】
【表２】
2009543478.tif 000004
このアルゴリズムは様々なシステム環境設定で動作すると仮定する。ＴＤＭＡの構造上の制限及び設定により、フレーム当たり６個のスロットが存在する場合、アクティブに通信を行うノードの最大数は典型的に、如何なる２ホップ近傍内においてもＭ個未満である。
【００５６】
例えばノード群は衝突検知能力を有しない等といった、一定の無線機の能力及び仮定が存在する。衝突検知は典型的に、受信信号を３つの異なるカテゴリー：（１）受信された信号；（２）受信されていない信号；及び（３）衝突が物理層によって検知された受信されていない信号に分類するノードの能力である。衝突検知を有しない場合、無線機（物理層）は衝突と信号なしとの間の差異を区別することができない。
【００５７】
理解されるべきことには、ＧＰＳは利用可能であっても利用可能でなくてもよく、ノード群は全て１つの周波数で動作する。ネットワーク及び環境の仮定により、ノード群の間の通信リンクの大部分は双方向である。例えば、８０％は双方向であるとすることができ、ＧＰＳを有するノードの数は０から全てまでの範囲内とし得る。
【００５８】
一般的に、ネット形成処理は二段階に分けられる。各ノードがこれら二段階を歩む。再び図３及び４の状態図を参照するに、段階１は“独立”状態１１２と“同期・再同期”状態１１４とによって定められることは明らかである。段階２は“スロット主張”状態１１６と“スロット固定”状態１１８とによって定められるが、ネットワーク形成は同時に作用するノード群の統合結果である。個々のノードの各々は、如何なる状態をとることもでき、他のノード群と独立に相互作用することができる。段階１は同期化（ＳＹＮ）と呼び得る。ＧＰＳにより、ノードは既に“同期化”されていると見なす。ノードは秒符号（second  mark）アライメントで、ＧＰＳタイミングに従って自身のビーコンをブロードキャストし得る。システム内に１つのＧＰＳノードが存在する場合、ネットワーク全体はＧＰＳを参照して同期化され得る。ＧＰＳが存在しない場合、ノードは先ず他のノード群と同期すべきである。
【００５９】
ネットワークタイミング基準を表すように選出されることになる１つのノードＧＳＮが存在する。このタイミングはネットワーク全体を伝播することになる。ネットワークの相異なる部分で複数のＧＳＮが選出されてもよい。ＧＰＳタイミングが如何なる通常のＧＳＮタイミングをも覆すような、単一のタイミング基準をもたらす調停ルールが定められ得る。より小さいＧＳＮ  ＩＤを有するＮＴＲが、より大きいＧＳＮ  ＩＤを覆してもよい。
【００６０】
段階２は、スロット主張、衝突検出・確認（Slot  Contention，Collision  Detection  and  Confirmation；ＳＣＣＤＣ）と呼び得る。ネット基準タイミング（ＧＰＳ又はＧＳＮに基づく）を知ると、ノード群は非干渉タイムスロットを得ようと互いに助け合う。ネット形成段階に加え、タイミング基準の伝播は、ネット形成の大部分あるいは全ての段階で行われる持続的処理である。タイミング基準はネットワーク全体を伝播されることが可能である。タイミング基準がネットワーク全体を伝播する方法は幾つかのルールによって支配され得る。ノードが自身の内部タイミングを外部タイミング基準に同期させておらず、且つタイミング基準（ＮＴＲ）を有するパケットを受信した場合、そのノードは受信したタイミング基準を採用する。ノードが既に或るＮＴＲ（Ｘ）に同期されているが、より高い優先度を有する新たな異なるＮＴＲ（Ｙ）を受信した場合、そのノードはＮＴＲ（Ｘ）を放棄してＮＴＲ（Ｙ）に従う。
【００６１】
同期化（ＳＹＮ）段階は、ネット形成アルゴリズムのこの段階の一部とすることができ、タイミング基準を選択し得る。この手順はまた、図５に示したような３ステップマルチウェイ（３ＳＭＷ）選択処理と呼び得る。ＧＳＮの選択は、以下の特徴を有するノードを好む：
１．ノードＩＤが極めて小さい（調停ルールとして用いられる）；
２．その隣接ノード群と三段階ハンドシェイクで係合しているノード（３方向ハンドシェイクと同様であるが、複数のノードとである）；
３．ノード群の他の１つのノードから見えるノード；及び
４．隣接ノード群のうちの少なくとも１つへの双方向リンクが存在する。
【００６２】
処理が二段階ハンドシェイクに簡略化される場合、デッドロックは局所的な近傍でＧＳＮを選出するとき現れる。アルゴリズム動作は同期化段階中に実行される。これらは：
１）同時・周期的な動作；及び
２）事象ドリブン動作；
を含む。
【００６３】
同時・周期的動作において、ビーコンスロットはノードの内部タイミング基準（ＩＮＴＲ）に従って選択される。ＮＴＲが検出されない場合、又はノードのビーコン送信が少なくとも１つのその他のノードによって肯定応答されない場合、Ｘ１（初期設定でＸ１＝５）個の時期（エポック）の期間（タイマーによって制御される）ごとに新たなビーコンスロットが選択され得る。タイマー及びＳＹＮタスクはタイミング基準が確認されたときに停止され得るが、ＳＹＮタスクはノードが多数秒（初期設定＝３０秒）にわたって単独であることを認識した場合に再開され得る。肯定応答を有するビーコンを送信することが可能である。ビーコンはエポックごとに一度スケジューリングされ得る。肯定応答メッセージは、先行するＹミリ秒（初期設定でＹ＝１２５ｍｓ）の期間中にビーコンが正しく受信された最大でＸ２（Ｘ２はアルゴリズムにおいて設定可能なパラメータであり、初期設定でＸ２＝４）個の隣接ノードのノードＩＤを含み得る。
【００６４】
事象ドリブン動作においては、内部タイミング基準（ＩＮＴＲ）としてランダムな時間が選択される。この動作はノードが最初に起動されたときに実行される。ＧＰＳが利用可能である場合、タイミング基準はＧＰＳの正確な秒符号に揃えられ得る。新たなＮＴＲを受信した場合、タイミング基準は新たに受信したタイミング基準に揃うように設定され得る。ビーコンを受信すると、肯定応答メッセージ（ＡＣＫ）のチェックが送信される。ビーコンが受信ノードの以前のビーコン送信を受信確認したＡＣＫを含む場合、受信ノードは、ＧＳＮとしてノードを選出する処理における自身の“自己選出状態”を格上げする。この自己選出レベルは図３及び４に示されている。これらは、図４において、符号１２２、１２４、１２６、１２８、１３０及び１３２が付された状態に対応して０−５の数字が付された様々な選出レベルである。
【００６５】
ＡＣＫメッセージを受信すると、受信ノードの自己選出状態は格上げされ得る。１つの要件は、自己選出状態の格上げは段階的でなければならない、すなわち、自己選出状態は一度に１だけ増加されるというものであり得る。別の１つの要件は、ノードの格上げされた自己選出状態は、ＡＣＫの送信元の自己選出状態レベルより１レベルだけ高くなることができるというものであり得る。複数のＧＳＮが選出される場合、最小のＩＤ番号を有するものが優先する（全てのその他のノードは、より小さいノードＩＤを有する別のノードからの、ＧＳＮ状態を通知するビーコンを受信した場合、この役割を譲り渡す）。
【００６６】
ビーコンを受信すると、送信ノードのノードＩＤが記録され、ＧＳＮ候補として最小のノードＩＤが維持される。これは、出て行くＡＣＫとして次のＴＸパケットに含められ得る（同期化段階中に、各ビーコンは、１つの（あるいは０個の）隣接ノードの送信に肯定応答する）。
【００６７】
図５は、ノードをＧＳＮとして選出する全てが１ホップ近傍にある６個のノードの例と、タイミング基準として作用しているＧＳＮとを示すグラフ及び付随するノード図である。縦軸はノードＩＤを表し、横軸は増えゆく時間を表している。ビーコンが１４０に、衝突が１４２に、ブロードキャストの成功が１４４に、選択された肯定応答を有するブロードキャストの成功が１４６に、最小ノードＩＤへの選出肯定応答への関与が１４８に示されている。最小ノードＩＤの参加者への提案及び肯定応答は１５０であり、第１のタイミング基準は１５２である。
【００６８】
この図は、３つのほぼ３エポックの期間に及んでいる。この例においては、ノードＩＤはレベルＡ−Ｆによって表され得る。ノードＩＤの比較において、ＡはＢより“小さい”等々と見なされる。ネットワーク内でＧＰＳが利用可能である場合、ＮＴＲはＧＰＳによって直ちに得られる。３ＳＭＷはトリガーされない。図５の略図において、６個全てのノードは第１の動作サイクル（例えば、１２５ｍｓ）内の異なる時点で起動する。これら全ては自身の内部タイミング基準（ＩＮＴＲ）を有する。これらは全てＧＳＮ選出処理に参加する。送信スケジュールは５サイクルの間は変化しない。第１サイクル中、６個全てのノードはランダムに、自身のタイミング基準と、そのノードの選択したタイミング基準に関するビーコンスロットとを選択する。ノード群は、ＧＳＮ又はＧＰＳが宣言されたか（これは縦線１５２で発生している）を検査し続ける。様々な横線がノードの自己選出状態を表している。自己選出状態は肯定応答（ＡＣＫは矢印によって指し示されている）を受信すると変化する。第２サイクルにおいて、ノードは、ノードは自身の選出状態をＡＣＫを送信したノードの選出状態より１レベルを超えて増大させられないというルールを用いて、最小ノードＩＤを有する隣接ノードに肯定応答する。第３サイクルにおいて、ノード１は自身の自己選出状態を増大させ、自身の次のビーコン機会中に自身をＧＳＮに宣言する。ビーコンスロットのコンフリクトを解消するためにノードが実行し得る主なタスクには：
Ａ．スロット主張
Ｂ．衝突検出、及び
Ｃ．スロット確認
という３つが存在する。これらのタスクは、ビーコンスロットのコンフリクトが検出されなくなるまで周期的に実行されることが可能である。検査される全ての条件下で、ネット形成アルゴリズムのこの段階は、ビーコンスロットのコンフリクト数が急激に減少することを示す。
【００６９】
スロット主張は典型的に、ノードがビーコンスロットを選択するための処理である。ノードは、自身の未占有ビーコンスロットのデータベース、すなわち、自身のビーコン占有ベクトル（ＢＯＶ）からランダムにスロットを選択する。ＢＯＶは、各ビットがビーコンスロットの占有状態を表すビットマップとして維持される。内部ＢＯＶが隣接ノード群にブロードキャストされ得る。ＢＯＶは典型的に局所的（初期設定でＸ＝２のＸ個のホップ半径）にのみ意義を有する。ノードは、空きスロットを主張するとき、選択を行う前に自身のＢＯＶビットマップを調べる。後述するように、ビットマップＢＯＶ内の情報は典型的に、可能な限り高い頻度で更新されなければならない。
【００７０】
ノードのＢＯＶの情報（採用されるスロット）は２つの情報源から得られ得る。第１の情報源は、ノードの観察が直接的に隣接するもののスロット使用に関して為されるＢＯＶ−１である。このＢＯＶ情報は直接的に抽出され、１ホップの意義を有する。第２はＢＯＶ−Ｘ（例えば、２ホップ近傍からのＢＯＶ−２）である。ＢＯＶメッセージ群からの情報は隣接ノード群によって送信され、複数ホップの意義を有する。
【００７１】
調査に用いられるときの最終的なＢＯＶは、全てのＢＯＶ−Ｘの和から得られ、スタックに格納される。ＢＯＶ−Ｘスタックの全体はビーコンメッセージを介して近傍に送信され得る。直近のビットマップＢＯＶ−１はスタックの最上部（エントリー１）に置かれ得る。２ホップの近傍のビットマップＢＯＶ−２はスタックのエントリー２に置かれ得る。３ホップの近傍のビットマップはエントリー３に置かれ等々と続けられ得る。
【００７２】
ＢＯＶエントリーの伝播は、設定可能なタイム・トゥ・ライブ（ＴＴＬ）パラメータによって制御され得る。ＴＴＬ＝１により、ＢＯＶ−１は１ホップの近傍にブロードキャストされ得る。ノードがＴＴＬ＝２を有する場合、ＢＯＶ−１及びＢＯＶ−２が送信され、ＢＯＶ−１は２ホップ離れたところまで伝播する。ノードがＢＯＶエントリーを中継する度に、それはスタックの下方に押し下げられていく。
【００７３】
ノードは、自身のビーコンの確認（すなわち、肯定応答）を受信すると、ＴＸスケジュールを維持し、各後続エポックにおいて自身のビーコンを送信し続ける。一連の衝突検出（ＣＤ）は近傍のスロット使用を監視するのに適当な位置にある。ノードは、別のノードとコンフリクト状態にあることを決定する（あるいは発見する）まで自身のスケジュールを維持する。衝突が検出された場合、コンフリクト状態のノードは新たな空きスロットを主張する。衝突を信頼性高く検出することは難しいため、選択されたスロットが２ホップ近傍内の別のノードによって使用されないことを継続的に（すなわち、エポックごとに）検証するために幾つかの異なる衝突検出機構が用いられ得る。それらの機構を図６に示す。図６は、３つのノード設計及びスロットを有するバーチャートを示している。これら３つの設計は衝突検出機構をＣＤ（１）、ＣＤ（２）及びＣＤ（３）として例示している。ＣＤ（１）は衝突のないネットワークトポロジーであり、ＣＤ（２）は衝突を示すネットワークトポロジーの有向グラフであり、ＣＤ（３）はスケジュール交換によって変更される有向辺を示している。
【００７４】
ＣＤ（１）はＡＣＫの隙間（void）である。送信ビーコンが期間＝１エポック内に１つ以上の隣接ノードによって確認されない場合、そのノードは新たなビーコンスロットを主張する。例えば、図６においてＣＤ（２）に示すように、ノードＡはスロット２にて送信したが、隣接ノード｛Ｂ＆Ｃ｝からＡＣＫからのＡＣＫを受信していない。ノードＡは別の空きスロットを主張する。
【００７５】
ＣＤ（２）はＢＯＶ内のビットセットの隙間である。ノードＸがスロットＡで送信するとき、隣接ノード群の大部分がそれら自身のＢＯＶビットをスロットＡに設定していない場合、ノードＸは自身のビーコンが別のノード（群）のビーコンと衝突状態にあると仮定する。衝突のない場合、全ての隣接ノードはノードＸのビーコンを正しく受信し、それら自身のＢＯＶ内の適切なビットを占有されたものとして設定する。隣接ノード群がそれら自身のパケットを送出するとき、ノードＸは、受信した各ビーコン内のスロットＡに対応するビットを検査する。しかしながら、一部のノードは、伝播条件のため、すなわち、リンクが非対称である場合、そのスロットを占有されたものとして報告しないことも可能である。ネットワークが相当数の非対称リンクを有する場合、この衝突検出機構に関する衝突閾値は増大されなければならない。
【００７６】
新たな衝突検出閾値＝（受信ノードのビーコンスロットを占有されたものとして報告しないノードの数）／（受信ビーコンの総数）である。衝突事象は、この比が約０．１９−０．８４の範囲内でランダムに選択された数より大きいときに発生したと宣言される。この範囲内の新たな閾値は、例えばＸ＝２として、Ｘ個のエポックごとに選択される。数多くの隣接ノードが同時に衝突を検出し、その結果として、同時に新たなビーコンスロットを主張することを回避するよう、衝突閾値は（上述の範囲内で）ランダムに選択される。高い側の閾値及び低い側の閾値は、これまでのシミュレーション結果に基づいて選択されている。この衝突検出アルゴリズムはエポックごとに一度実行される。例えば、Ａ及びＢがＴＸコンフリクトを有する図６のＣＤ（２）において、直接観察されるＢＯＶ−１は：Ａ（ＢＯＶ）＝１１００；Ｂ（ＢＯＶ）＝１１０１；Ｃ（ＢＯＶ）＝１０００；Ｄ（ＢＯＶ）＝０１０１である。ノードＢはノードＣが聞こえ、Ｃ（ＢＯＶ）＝ｘ１ｘｘであると予期するが、それはｘ０ｘｘを有する。ノードＢは非対称リンクを検出する。非対称リンク数が閾値を上回る場合、ノードＢは衝突状態にあり得ると仮定する。
【００７７】
ＣＤ（３）は交換機構（Exchange  Mechanism；ＥＭ）である。上述の２つの衝突検出機構は大抵の衝突事象を首尾良く検出する。しかしながら、非常に多数の非対称リンクのために検出されない衝突が、少しながら存在し得る。この条件下でのビーコン衝突を検出するため、ノードが一時的に隣接ノードとビーコン送信時間を交換するＥＭ機構が用いられる。この機構を例示するため、ノードＡ及びＢの双方がビーコンスロットＸを使用し、ノードＣで衝突を発生させると仮定する。ノードＢが自身のビーコンスロットを一時的にノードＤ（通常はスロットＺを使用）と交換する場合、ノードＣは２つの新たなビーコン、すなわち、ビーコンスロットＸ内のノードＡ、及び“私のビーコンスロットは通常はスロットＸである”というメッセージ付きのビーコンスロットＺ内のノードＢを受信し得る。この場合、ノードＣはノードＡ及びＢに、スロットＸでノードＡとＢとの間の衝突を検出したと通知する。
【００７８】
衝突はまた、交換に続いてノードＢ（通常はスロットＸを使用）がノードＺのビーコンをスロットＸで受信しない場合に発生すると推測され得る。隣接ノードとのビーコン送信スケジュールの交換は３ホップの半径位置で一時的な衝突を生じさせ得るので、ＥＭの実行頻度は低くされなければならない。例えば、図６において、ノードＢとノードＤとの間でのＴＸスケジュールの交換はＣＤ（２）及びＣＤ（３）に示されている。接続性の変化が幾つかのノードによって検出され得る。交換サイクル中、ノードＢはノードＤが聞こえるべきであるが、聞こえない。また、ノードＡは突然に予期せずしてノードＢが聞こえる。この変則性は近傍におけるＴＸスケジュールに衝突を意味する。
【００７９】
また、シフテッド−ルックスルー（ＳＬＴ）のための第４の取り得る衝突検出機構も存在する。各ノードは（稀に）送信のために追加のビーコンスロットを選択する。この追加の送信は、隠れた衝突によって阻止された場合に、ノードがその他の隣接ノード群によって発見される機会をもたらす。この機構は、複数のノードが同時に同一の空きビーコンスロットを獲得するために争うことを回避するため、頻繁に実行されるべきではない。例えば、Ａ及びＢがＴｘコンフリクトを有する図６のＣＤ（２）において、スロット３は使用されていない。ノードＢがスロット３に追加Ｔｘを計画する場合、スロット２及びスロット３上の２つの相等しいビーコンが同一エポック内に送信される。しかし、スロット３上のビーコンのみがノードＡによって首尾良く受信される。ビーコンＰＤＵにおいて、それはスロットＩＤ＝２を含む。ノードＡはスロット３上で予期せぬビーコンを受信したが、ＰＤＵはスロットＩＤ＝２を指し示す。ノードＡは、そのＰＤＵがＳＬＴ機構を介して送信されていることを認識する。スロット２に衝突が存在しない場合、ノードＡはスロット２及び３でビーコンを受信することができたであろう。そうでなければ、衝突が存在する。ノードＡは衝突を指し示すものを自身のビーコン内に構築し、ノードＢにＢが衝突状態にあることを通知する。
【００８０】
スロット確認タスクにおいて、スロット確認（slot  confirmation；ＳＣ）が、局所的に（すなわち、以下にて示すＳＣ１及びＳＣ２）行われるとともに、ＧＳＮすなわちＳＣ３との通信を介してＨＰ−ＮＥＴワイドベースで行われる。処理ＳＣ１はスロット主張段階の部分として上述したものである。
【００８１】
第１のタスク（ＳＣ１）にて、隣接インダイレクト肯定応答（ＮＢＩＡ）が行われる。ノード（ノードＡ）はビーコンを送出することによってスロットを主張する。そのスロットに衝突が存在しない場合、そのビーコンは幾つかの隣接ノードによって聞かれることになる。ノードＢが隣接ノード群のうちの１つである場合、ノードＢが送信に切り替わる時点までに、ノードＢは自身のビーコンにＡＣＫを含め、ノードＡの成功した送信に間接的に肯定応答する。この肯定応答は、該ビーコンの主目的は空きスロットを主張することであるので、間接的なものである。そして、肯定応答するノード（ノードＢ）自身も、肯定応答で応答すべきノードとして特別に標的とされたものではない。肯定応答が受信されたとき、新たな衝突が検出されるまで、ノードＡは自身のＴＸスケジュールを維持する。
【００８２】
第２のタスク（ＳＣ２）にて、ＮＢＩＡメッセージの多様（ダイバーシティ）化が行われる。１つのビーコン内のＡＣＫの数は１に制限されない。ノードは先行する期間＝１エポック内に受信したＮ個のビーコン伝送に肯定応答することができてもよい。Ｎの値が大きいほど、ネット形成アルゴリズムの収束速度が高くなる。（初期設定でＮ＝４。様々なチャンネル障害による全ての種類のパケットドロップを有するネットワークにおいて値４は十分に信頼性があることがシミュレーションによって得られている。）
スロット主張及びスロット確認の一例を、図７のグラフ及びノード設計に示す。空きタイムスロットの主張が１６０に図示されている。隣接ノードによって間接的に肯定応答された成功した主張が１６２に示されている。特に断らない限りこのスロットに留まることが１６４に示されている。首尾良く受信されたビーコンが１６６に示されている。共通に合意されたネットワークタイミング基準又はＧＰＳが１６８に示されている。衝突・受信なしが１７０に示されている。ブロードキャストハロー（hello）及び以前に聞いた１つ又は２つのスロット主張に間接的に肯定応答するハローメッセージが１７２に示されている。隣接ノードの間接的肯定応答段階も同様に示され得る。
【００８３】
この例に係るノード設計は６個のノードを有する。スロット数は６以上の如何なる数であってもよい（ここでは１４とする）。上述のＣＤ１及びＳＣ１の機構が例示されている。ネットワークは、全てが互いに１ホップ内にある６個のノードを有する。３ＳＭＷ又はＧＰＳの何れかによってＮＴＲが得られていると仮定し得る。ノード群（Ａ−Ｆ）は内部的且つランダムにそれら自身の主張スロットを選ぶ。主張と同一のビーコン内にＡＣＫが詰め込まれる。３サイクル内に、主張及び確認が完了する。
【００８４】
図６に示した全てのノードが既にＮＴＲ又はエポックの同期化を達成していると仮定する。ｔ＝１において、全ノードが内部的且つランダムに、同一ＮＴＲに基づいてスロットを選ぶ。それらは然るべくビーコンを送出する。一部のビーコンは衝突し、一部は衝突しない。衝突していないビーコンに対し、隣接ノード群は同一の主張ビーコン内に肯定応答を含める。第１のサイクルにおいて、ノードＡはスロット１にビーコンを有する（１６０に示される）。その他全てのノードはそれが聞こえる（１６６に示される）。ノードＢ及びノードＤはスロット２にビーコンを有する。全ての受信ノード上で衝突が起こる（１６０に示される）。ノードＥはスロット３にビーコンを有する（１６０に示される）。そのビーコンはビーコン内に詰め込まれたＡＣＫ（ＡへのＡＣＫ）を有する。この例において、ＮＢＩＡの多様性（ダイバーシティ）は１である。ノードＡはノードＥからの確認すなわちＡＣＫを受信する（１６２に示される）。次のサイクル（又はエポック）において、ノードＡは確認されたスロット（スロット１）にＴＸを留める。スロット４は空き状態で残されている。何れのノードもこのスロットを選択していない。ノードＥに最も直近にビーコンが送信されるとき、ビーコンはノードＥへのＡＣＫを含む。
【００８５】
スロット６からスロット８において、何れのノードもこれらのスロットを選択しない。スロット９において、ノードＣはビーコンを有する。これはまた、最も直近にビーコンを送信したノードＦへのＡＣＫを有する。ノードＦはこの確認を受信する。スロットＡからスロットＥにおいて、何れのノードもこれらのスロットを選択しない。このエポックはこれで終了し、エポック２が開始する。エポック２のスロット１において、ノードＡはスロット１にＴＸを留める。そのビーコンは、最も直近にビーコンを送信したノードＣへのＡＣＫを有する。ノードＣはこの確認を受信する。ノードＢ及びノードＢはエポック１の期間にわたって如何なるＡＣＫも受信していない。これらのノードは新たな空きスロットを再び主張することを決定する。ノードＢはスロット８を選び、ノードＤはスロット４を選ぶ。エポック２のスロット２において、何れのノードも送信するように計画されていない。エポック２のスロット３において、ノードＥはスロット３にＴＸを留める。ノードＥはノードＡへのＡＣＫを付加し続ける。ノードＡにおいて、このＡＣＫはそれ以上のことは何もしない。エポック２のスロット４において、ノードＤはＴＸのためのビーコンを有する。そのビーコンはノードＥへのＡＣＫを有する。ノードＥは既に確認されているので、このＡＣＫを無視する。エポック２のスロット５において、ノードＦはスロット５にＴＸを留める。そのビーコンはノードＤへのＡＣＫを有する。ノードＤは始めて確認を受信したことになる。
【００８６】
ＮＢＩＡをモデル化し、以下にて説明する２つのシミュレーション結果の例に示す様々なネットワーク構成及びシステムパラメータに関してシミュレーションを行った。１つは静的なもの（１ｍ／ｓ）であり、もう１つは運動状態（３０ｍ／ｓ）である。ネットワークパラメータを、表３に列挙するように設定した。
【００８７】
【表３】
2009543478.tif 000005
この例においては８個のフレームが存在する。スロット帯域幅は部分的に制御メッセージによって消費される。制御メッセージは、例えばノードＩＤ、状態及びＡＣＫ等の情報を含む。
【００８８】
簡略化された制御メッセージは、表４に示す欄を含み得る。非限定的な一例において、制御メッセージ内のビットの総数は１５８ビットとし得る。この例において、ＢＯＶレベルは２（ＴＴＬ＋２）であり、ＮＢＩＡの多様性は４に設定されている。
【００８９】
【表４】
2009543478.tif 000006
図８は、約８０００ｍ×約８０００ｍの領域内に２００ノードを含むネットワークトポロジーの一例を示している。静的なネットワークにおいて、ネットワークが始動するとき、ネットワークの同期化及びチャンネルスケジューリングが行われる。このスケジューリングによりスロットコンフリクトが解消される。約２秒の間に、ネットワーク全体が低レベルの少ないコンフリクトまで収束する。収束の速さすなわち収束時間は、チャンネルスケジューリングのタスクに割り当てられる帯域幅の大きさに正比例する。例えば、帯域幅の１０％が使用される場合、収束時間は２ｓから約１２５ｍｓまで短縮される。
【００９０】
図９ａは、グローバルコンフリクトトレースを示すグラフである。縦軸はコンフリクト数を示し、横軸は秒数を示している。約２秒の間に、コンフリクトのグローバル統計は数個の衝突のレベルまで低下し、場合によって衝突は存在しない。この低いレベルの背景コンフリクトは交換機構に因るものである。
【００９１】
図９ｂは、ネットワークの接続性を例示するグラフである。縦軸は隣接ノード数を示し、横軸はノードＩＤを示している。
【００９２】
図９ｃは、単一のノード（ノード０１）から観たスロットコンフリクト履歴を例示するグラフである。１の衝突指標（レベル）が定位であるとき、衝突は存在しない。レベル２以上は、２つ以上のパケットがこのノード上で衝突していることを意味する。縦軸は衝突指標を示し、横軸は秒を示している。
【００９３】
動的なネットワークにおいて、ネットワークが始動するとき、ネットワークの同期化及びチャンネルスケジューリングが行われる。このスケジューリングによりスロットコンフリクトが解消される。約２秒の間に、ネットワーク全体が低レベルの少ないコンフリクトまで収束する。このレベルは静的なネットワークのレベルより高い。ノード群が他のノードの近傍の中へ、あるいは外へ移動するとき、スロットコンフリクトが発生する。
【００９４】
図１０ａは、グローバルコンフリクトトレースを示す別のグラフである。このシミュレーションは１８秒にわたって続けられている。グローバルコンフリクトトレースはネットワーク全体で約１０個のスロットコンフリクトのレベルまで収束している。これらのコンフリクトはノードの移動によるトポロジー変化によってもたらされる。
【００９５】
図１０ｂは、ノード移動のトレースを示す別のグラフである。ノード群はランダムに選択された方向に約３０ｍ／ｓで移動している。
【００９６】
図１０ｃは、図９ｂのグラフト同様の、ネットワークの接続性を示すグラフである。図１０ｄは、図９ｃに示したグラフと同様の、単一のノードから観た衝突トレースを示す別のグラフである。僅かに多くのコンフリクトが観察される。ノード群がノードの近傍から立ち去る、あるいは近傍に入るとき、スロットコンフリクトは素早く解消される。
【００９７】
本発明の非限定的な一例に従って、隣接インダイレクト肯定応答アルゴリズム（ＮｂＩＡ）は、低い帯域幅オーバーヘッドを有する高速、分散型の同時チャンネルアクセススケジューリングアルゴリズムである。隣接ノード群は互いに、スロットを同時に見出すように支援し合う。
【００９８】
分散機構において、Ｎ個全ての隣接ノードは、それらの狙うスロットを同時に提案し合い、それと同時に、最近の成功した主張に肯定応答する。残りの衝突は隣接ノード群との交換機構によって解消される。高速な収束において、ローカルアクセススケジュールの大部分は数フレーム内で解決され得る。低い帯域幅オーバーヘッドにおいて、肯定応答メッセージが主張ビーコン内に埋め込まれるため、ビーコンの帯域幅要求は低いものとなる。堅牢な機構において、この機構はスケジューリングを調整するための特定のヘッドを必要としない。単一障害点は存在しない。
【００９９】
５フェーズ予約プロトコル（Five-Phase  Reservation  Protocol；ＦＰＲＰ）との比較表を表５に示す。設定は以下の通りである：
ａ）ネットワークサイズは２００ノード；
ｂ）伝送範囲は１．５単位；
ｃ）面積は１４．１×１４．１平方単位；
ｄ）フレーム当たりのスロットの最大数は２０；及び
ｅ）通信帯域幅は１Ｍｂ／ｓ。
【０１００】
【表５】
2009543478.tif 000007
本発明の非限定的な一例に従ったＮｂＩＡアルゴリズムは、先に送信された主張への肯定応答を運搬するために隣接ノード群の主張機会を利用する。便宜上、そうされる。交換機構の第２の同時処理が有利である。如何なる２つの隣接ノードも、隠れたコンフリクトが露呈されるよう、それらの送信スケジュールを交換するよう互いにスケジュールし合うことが可能であるが、スケジュールの交換は最大で３ホップ離れたノードまで影響を及ぼす。故に、交換機構は典型的に３ホップの近傍内のネットワークスケジュールコンフリクトを解消する。必要に応じて、交換機構に代えて、ルックスルー法が使用され得る。ルックスルーは、遙かに遅い収束率を有するものの、２ホップの近傍のコンフリクトを解消し得る。しかしながら、送信スケジュールの一部は抜かれる。
【０１０１】
音声をサポートすることにおいて、メディアアクセス制御（ＭＡＣ）はアドホックネットワークにおける障壁となり得る。一部の従来システムにおいては、８０２．１１ＣＳＭＡ主張ベースの方法が、アドホックネットワークにおけるＭＡＣのより良い選択であるが、その非決定論的な送信スケジュールは、ネットワークの大きさ及び密度が増大するため、ＱＯＳのボトルネックとなる。この制約のため、一部の提案は、ＴＤＭＡ又はＣＤＭＡの何れかをアドホックネットワークに適用可能にすることが困難である。本発明の非限定的な一例に従ったＮｂＩＡの速い収束は、アドホックネットワークにおいて、予測可能な送信スケジューリングを実現可能にする。それは同時に、ネットワークトポロジーを容易に変更することに適合するものである。スケジューリングが同時的且つ分散的に解決されるため、それは保守努力を必要としない。
【図１】
2009543478.tif 000008
【図２】
2009543478.tif 000009
【図３】
2009543478.tif 000010
【図４】
2009543478.tif 000011
【図５】
2009543478.tif 000012
【図６】
2009543478.tif 000013
【図７】
2009543478.tif 000014
【図８】
2009543478.tif 000015
【図９ａ】
2009543478.tif 000016
【図９ｂ】
2009543478.tif 000017
【図９ｃ】
2009543478.tif 000018
【図１０ａ】
2009543478.tif 000019
【図１０ｂ】
2009543478.tif 000020
【図１０ｃ】
2009543478.tif 000021
【図１０ｄ】
2009543478.tif 000022
【手続補正書】
【提出日】平成20年5月6日(2008.5.6)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
複数の移動ノードと、前記複数の移動ノードを結び付ける複数の無線通信リンクとを有する移動アドホックネットワークを動作させる方法であって：
発信元の移動ノードにｎホップの距離で隣接する移動ノード群から、ビーコンを用いて、フレーム内の複数のＴＤＭＡスロットを主張する段階；
各隣接ノードがフレーム当たり１つのＴＤＭＡスロットを選択する段階；
成功したビーコンに対する肯定応答を受信していない隣接ノード群が、空きＴＤＭＡスロットを主張する段階；及び
適宜選択された隣接ノードとビーコン送信時間を一時的に交換することによる選択隣接ノードとのメッセージ交換機構を用いてビーコンの衝突を検出することを特徴とする衝突検出機構を用いて、残った衝突を解消する段階；
を有する方法。
【請求項２】
前記隣接ノード群は２ホップの距離の範囲内に位置する、請求項１に記載の方法。
【請求項３】
各ノードは複数のフレームにわたって１つのＴＤＭＡスロットを維持する、請求項１に記載の方法。
【請求項４】
前記残った衝突を解消する段階は、ビーコン占有ベクトル内のビット群の隙間を用いることを有する、請求項１に記載の方法。
【請求項５】
肯定応答メッセージは、単一フレーム内で、送信時間の基準とされる最も直近に聞かれたビーコン群を選択することによって、ビーコンに埋め込まれる、請求項１に記載の方法。
【請求項６】
ＴＤＭＡスロット占有情報を隣接ノード群に供給するため、２レベルのビーコン占有ベクトルが用いられる、請求項１に記載の方法。
【請求項７】
発信元移動ノード；
宛先移動ノード；及び
ビーコンを用いてフレーム内の複数のＴＤＭＡスロットを主張するよう動作可能な複数の隣接移動ノードであり、各隣接ノードがフレーム当たり１つのＴＤＭＡスロットを選択し、成功したビーコンに対する肯定応答を受信していない隣接ノード群が、空きＴＤＭＡスロットを主張し、且つ隣接移動ノード群がビーコン送信時間を一時的に交換し合うメッセージ交換機構を用いてビーコンの衝突を検出することを特徴とする衝突検出機構を用いて、残った衝突を解消する、複数の隣接移動ノード；
を有する移動アドホックネットワーク。
【請求項８】
各移動ノードは、他の移動ノードと無線通信するための通信装置と、前記通信装置による通信の経路を決定するコントローラとを有する、請求項７に記載の移動アドホックネットワーク。
【請求項９】
複数の移動ノードを同期させるため当該ネットワークの全体に伝播されるタイミング基準、を更に有する請求項７に記載の移動アドホックネットワーク。
【請求項１０】
他の移動ノードが同期されるグローバルポジショニングシステムを含む移動ノード、を更に有する請求項７に記載の移動アドホックネットワーク。
【国際調査報告】
2009543478.tif 000023
2009543478.tif 000024
2009543478.tif 000025