(57)【要約】無線通信ネットワークは、トランシーバと、トランシーバに接続されているフェーズドアレイアンテナと、トランシーバに接続されているコントローラとをそれぞれ有する複数のモバイルノードを有する。コントローラは、ルートを発見し、ルーティングプロトコル（例えばOptimized  Link  State  Routing（OLSR）プロトコル）で隣接ノードに通信をルーティングする。コントローラは、タイムスロットをスケジューリングして各隣接モバイルノードと通信リンクを確立し、フェーズドアレイアンテナは、コントローラにより通信中に各隣接モバイルノードに向けられる。また、コントローラは、通信リンクにスケジューリングされた各タイムスロットの品質に基づいてリンク品質を推定し、推定のリンク品質をルーティングプロトコルに報告する。
2006522547.tif 000002
【特許請求の範囲】
【請求項１】
トランシーバと、前記トランシーバに接続されている指向性アンテナと、前記トランシーバに接続されているコントローラとをそれぞれ有する複数のモバイルノードを有する無線通信ネットワークであって、
前記コントローラは、
ルートを発見し、ルーティングプロトコルで隣接ノードに通信をルーティングする通信ルータと、
タイムスロットをスケジューリングして各隣接モバイルノードと通信リンクを確立するタイムスロットスケジューリングユニットと、
通信中に各隣接モバイルノードに前記指向性アンテナを向けるアンテナ照準ユニットと、
前記通信リンクにスケジューリングされた各タイムスロットの品質に基づいてリンク品質を推定し、推定のリンク品質を前記通信ルータに報告するリンク品質推定器と
を有する無線通信ネットワーク。
【請求項２】
請求項１に記載の無線通信ネットワークであって、
前記推定のリンク品質は、前記通信リンクにスケジューリングされた各タイムスロットの最大品質として定められる無線通信ネットワーク。
【請求項３】
請求項２に記載の無線通信ネットワークであって、
前記ルータは、前記推定のリンク品質に基づいて隣接ノードに通信をルーティングする無線通信ネットワーク。
【請求項４】
請求項３に記載の無線通信ネットワークであって、
前記リンクの少なくとも１つのタイムスロットの最大品質が所定の閾値より上である限り、前記通信リンクは維持される無線通信ネットワーク。
【請求項５】
請求項４に記載の無線通信ネットワークであって、
前記リンクの推定のリンク品質が所定の閾値より下になったときに、前記ルータは新しいルート発見を起動する無線通信ネットワーク。
【請求項６】
複数のモバイルノードに通信リンクを確立し、各モバイルノードは、トランシーバと、前記トランシーバに接続されている指向性アンテナと、前記トランシーバに接続されているコントローラとを有する方法であって、
モバイルノード毎に、
タイムスロットをスケジューリングし、各隣接モバイルノードと通信リンクを確立し、
通信中に各隣接モバイルノードに指向性アンテナを向け、
前記通信リンクにスケジューリングされた各タイムスロットの品質に基づいてリンク品質を推定し、
Optimized  Link  State  Routing（OLSR）プロトコルに推定のリンク品質を報告することを有する方法。
【請求項７】
請求項６に記載の方法であって、
前記推定のリンク品質は、前記通信リンクにスケジューリングされた各タイムスロットの最大品質として定められる方法。
【請求項８】
請求項７に記載の方法であって、
OLSRは、前記推定のリンク品質に基づいて隣接ノードに通信をルーティングする方法。
【請求項９】
請求項８に記載の方法であって、
前記リンクの少なくとも１つのタイムスロットの最大品質が所定の閾値より上である限り、前記通信リンクはOLSRにより維持される方法。
【請求項１０】
請求項９に記載の方法であって、
前記リンクの推定のリンク品質が所定の閾値より下になったときに、OLSRは新しいルート発見を起動する方法。
【発明の詳細な説明】
【背景技術】
【０００１】
時分割多重アクセス（TDMA：time  division  multiple  access）は、無線モバイル通信システムの間で通信リンクを確立ために使用されるアクセス機構の一例である。無線モバイル通信システムの間の通信リンクは、一連のタイムフレーム内に確立される。各タイムフレームはタイムスロットに分割され、各無線モバイル通信システムは少なくとも１つのタイムスロットを割り当てられる。
【０００２】
無指向性アンテナは、一般的に、１つのモバイル通信システムにより送信された情報が他の全てのモバイル通信システムにより受信されるように、無線モバイル通信システムにより使用される。モバイル通信システムが固定の周波数で動作している場合、チャネル干渉を回避するため、それぞれのタイムスロット内で交互に送信しなければならない。
【０００３】
２つの無線通信リンクの間の通信リンクの品質を改善するため、指向性アンテナが使用されることがある。指向性アンテナは、限られた受信範囲の所望の領域で更なるアンテナ利得を提供し、残りの領域に対してアンテナ利得を減少させる。
【０００４】
Pritchettによる米国特許No.5,767,807は、無線通信システムのネットワーク内で通信リンクを確立するために、フェーズドアレイアンテナを使用することを開示している。フェーズドアレイアンテナは、アンテナパターンを選択的に制御する非励振素子（parasitic  element）を有する。フェーズドアレイアンテナは、全ての非励振素子が高インピーダンス状態にある場合に無指向性信号を放射し、選択された数の非励振素子がスイッチング回路に応じて低インピーダンス状態にある場合に指向性信号を放射する。
【０００５】
より具体的には、Pritchettの807特許は、ネットワークで動作している無線通信システムのリスト及び無線通信システム毎の対応の各タイムスロットのリストのうち、固定の受信側無線通信システムから固定の起動側無線通信システムによる取得を開示している。テーブルは、無線通信システム間のタイムスロットをスケジューリングするリストに基づいて生成される。
【０００６】
指向性アンテナで動作する無線通信システムにタイムスロットをスケジューリングすることは、特に無線通信システムがモバイルである場合に複雑になる。このような動的なネットワークでは、モバイル通信システムは絶え間なくネットワークに入り、出て行く。更に、干渉検出及び回避の手順が必要になる。
【０００７】
Optimized  Link  State  Routing（OLSR）では、リンクステート情報は、帯域と遅延とデータ損失の確率とを含む様々なサービス品質（QoS）メトリックで、リンクの状態を定量化することができる。各ルータは、全トポロジ情報を維持し、フラッディング（flooding）を介してネットワークの他の全てのノードにリンクステート情報を定期的にブロードキャストする。このように、指向性アンテナのモバイル通信システムにおいてOLSRプロトコルにリンク品質を報告する手順が必要である。
【発明の開示】
【発明が解決しようとする課題】
【０００８】
従って、前記の背景を鑑みて、モバイル無線ネットワークにおける通信リンク要求の変化に応じるように、タイムスロットをスケジューリングして、リンク品質を決定して、ルーティングプロトコルに報告することが、本発明の目的である。
【課題を解決するための手段】
【０００９】
本発明による前記及び他の目的、特徴及び利点は、トランシーバと、トランシーバに接続されている指向性アンテナ（例えばフェーズドアレイアンテナ）と、トランシーバに接続されているコントローラとをそれぞれ有する複数のモバイルノードを有する無線通信ネットワークにより提供される。コントローラは、ルートを発見し、ルーティングプロトコルで隣接ノードに通信をルーティングする通信ルータと、タイムスロットをスケジューリングして各隣接モバイルノードと通信リンクを確立するタイムスロットスケジューリングユニットと、通信中に各隣接モバイルノードにその指向性アンテナを向けるアンテナ照準ユニットと、通信リンクにスケジューリングされた各タイムスロットの品質に基づいてリンク品質を推定し、推定のリンク品質を通信ルータに報告するリンク品質推定器とを有することが好ましい。
【００１０】
推定のリンク品質は、通信リンクにスケジューリングされた各タイムスロットの最大品質として定められてもよく、ルータは、推定のリンク品質に基づいて隣接ノードに通信をルーティングしてもよい。リンクの少なくとも１つのタイムスロットの最大品質が所定の閾値より上である限り、通信リンクは維持されることが好ましく、リンクの推定のリンク品質が所定の閾値より下になったときに、ルータは新しいルート発見を起動する。ルータは、リンク品質推定器から報告される推定のリンク品質に対してヒステリシス機能を実行してもよい。
【００１１】
複数の通信リンクは、スケジューリングされたタイムスロット内で確立されることが好ましく、各通信リンクは、隣接モバイルノードの異なる対を有する。無線通信ネットワークは、例えばモバイルアドホックネットワーク（MANET：mobile  ad-hoc  network）でもよい。
【００１２】
本発明による目的、利点及び特徴はまた、複数のモバイルノードに通信リンクを確立する方法により提供される。その方法は、モバイルノード毎に、タイムスロットをスケジューリングし、各隣接モバイルノードと通信リンクを確立し、通信中に各隣接モバイルノードに指向性アンテナを向け、通信リンクにスケジューリングされた各タイムスロットの品質に基づいてリンク品質を推定し、Optimized  Link  State  Routing（OLSR）プロトコルに推定のリンク品質を報告することを有する。
【発明を実施するための最良の形態】
【００１３】
本発明の好ましい実施例が図示されている添付図面を参照して、以下に本発明についてより完全に説明する。しかし、本発明は異なる形式に具現されてもよく、ここに示す実施例に限定するものとして解釈されるべきではない。これらの実施例は、この開示が十分且つ完全であるように、当業者に本発明の範囲を十分に伝えるために提供されている。同様の番号は、最後まで同じ要素を示す。
【００１４】
まず図１−２を参照すると、無線モバイル通信ネットワーク10は、複数の無線モバイルノード12a-12hを有する。各モバイルノード12a-12hは、トランシーバ14と、トランシーバに接続されている指向性アンテナ16と、トランシーバに接続されているコントローラ18とを有する。
【００１５】
コントローラ18は、各隣接モバイルノードと通信リンクを確立するため、タイムフレーム毎にそれぞれ半永久的タイムスロットをスケジューリングし、各タイムフレームに少なくとも１つの利用可能タイムスロットを残す半永久的タイムスロットユニット18aを有する。利用可能タイムスロットユニット18bは、リンク通信要求に基づいて、隣接モバイルノードとの通信リンクをも提供する少なくとも１つの利用可能タイムスロットをスケジューリングする。更に、コントローラ18は、通信中に各隣接モバイルノードに指向性アンテナを向けるアンテナ照準ユニット18cを有する。
【００１６】
並列処理はタイムスロットの割り当て遅延を減少させ得る。従って、半永久的タイムスロットユニット18aは、隣接モバイルノードから複数の受信した半永久的タイムスロット要求を処理しつつ、各隣接モバイルノードと通信リンクを確立するため、タイムフレーム毎に１つ以上の半永久的タイムスロット要求を起動し、各タイムフレームに少なくとも１つの利用可能タイムスロットを残してもよい。利用可能タイムスロットユニット18bは、隣接モバイルノードから複数の受信した利用可能タイムスロット要求を処理しつつ、リンク通信要求に基づいて、隣接モバイルノードとの通信リンクをも提供する１つ以上の利用可能タイムスロット要求を起動してもよい。
【００１７】
換言すると、ノードは、複数の受信した要求を処理しつつ、開始した１つ以上の保留の利用可能要求及び半永久的要求を有することができる。場合によっては、このことは、１つより多い隣接したものに所定のタイムスロットを一時的に割り当てることを生じることがある。しかし、以下に詳細に説明するように、この衝突は、タイムスロットについて１つの隣接ノードの選択を示す確認メッセージにより除去され得る。
【００１８】
確実な確認メッセージは２〜３の異なる手法を備えてもよい。起動側モバイルノードは、受信側モバイルノードにタイムスロット要求を送信し、その受信側モバイルノードは、起動側モバイルノードに応答を送信する。起動側モバイルノードは、受信側モバイルノードに確認を送信し、確認が受信されない場合に、受信側モバイルノードは再び応答を送信する。代替として、受信側モバイルノードは起動側モバイルノードに肯定応答を送信してもよく、肯定応答が受信されない場合に、起動側モバイルノードは再び確認を送信する。
【００１９】
２つのノードが相互にタイムスロット要求を同時に起動した場合、タイムスロット要求の衝突は確実に処理されるべきである。コントローラ18は、他のモバイルノードに要求を同時に送信し、対応の応答を受信せずに他のモバイルノードから要求を受信したときに、他の要求を再送信するための期間だけ待機する。この期間の間に、入力するタイムスロット要求は処理されてもよい。期間が終了した後に、そのノードから要求がまだ受信されていない場合、又はそのノードに対してタイムスロット割り当てが行われていない場合に、新しい要求が他のノードに送信されてもよい。遅延した要求がキューの最前部に到達すると、コントローラ18は、そのノードに対してタイムスロット割り当てが既に行われているか否かを検査する。そうである場合、遅延した要求は破棄される。また、要求がキューの最前部に到達する時間までにもはや隣接していないノードに要求が向かう場合には、遅延した要求は破棄される。
【００２０】
干渉検出ユニット18dは、隣接モバイルノードとの通信用のタイムスロットで干渉を検出するために含まれる。コントローラ18は、検出された干渉に基づいてタイムスロットのスケジューリングを調整する。干渉検出ユニット18dは、信号対干渉比及び／又はパケット誤り率を測定してもよい。パケット誤り率は周期的冗長検査（CRC：cyclic  redundancy  check）の失敗に基づいてもよい。また、干渉検出ユニット18dは、検出された干渉と閾値とを比較してもよい。コントローラは、検出された干渉に基づいて所定のタイムスロットについてノード間の通信の順序を切り替えることが好ましく、また、通信の順序を切り替えた後に、検出された干渉に基づいて新しいタイムスロットのスケジューリングを調整してもよい。
【００２１】
トラヒック調整ユニット18eは、リンク通信要求に基づいてタイムスロットユニットにタイムスロットを割り当てることにより、各隣接モバイルノードとの通信を調整する。コントローラ18は、割り当てられたタイムスロットに基づいてタイムスロットのスケジューリングを調整する。トラヒック調整ユニット18eは、増加するリンク通信要求に基づいてタイムスロットの大量のセットを割り当ててもよく、及び／又は増加するリンク通信要求に基づいて隣接モバイルノードからタイムスロットの大量のセットを要求してもよい。また、トラヒック調整ユニット18eは、タイムスロットの最大数を増加し、タイムスロットを再割り当てし、及び／又は増加するリンク通信要求に基づいて半分のタイムスロットを割り当ててもよい。このような増加するリンク通信要求は、ストリーミングビデオ及び／又は高レートのセンサデータを有してもよい。
【００２２】
無線モバイルノード12a-12hは、モバイル環境で動作している。これらのシステムは地上及び／又は空中でもよく、それによってそれらは絶え間なくネットワーク10に入り、出て行く。指向性アンテナ16は、例えばフェーズドアレイ、パラボラアンテナ又はホーンアンテナでもよい。指向性アンテナ16を介した送信により、RF信号が所望の方向に集中することが可能になる。
【００２３】
無線モバイル通信システムの対の間の通信リンクを確立するため、無線モバイル通信システムの対の間のアンテナパターンの方向を選択的に制御することにより、同じスケジューリングの半永久的タイムスロット内に、他の無線通信システムの間で更なる通信リンクが確立されてもよい。このことは、図１によく示すように、モバイルノード12cと12eとの間でタイムスロット1で動作する通信リンク27、及びモバイルノード12aと12bとの間でタイムスロット1で動作する通信リンク29により図示されている。本発明のこの特徴により、有利には、無線モバイル通信ネットワーク10のリソースがより良く利用されることが可能になる。
【００２４】
コントローラ18は、フレーム内のタイムスロットの総数に基づいて、各タイムフレーム内の無線モバイルノード12a-12h毎の通信リンクの数を制限する。タイムフレーム内のタイムスロットの総数の一部に通信リンクの数を制限する利点は、隣接ノードとのタイムスロットのスケジューリングをかなり簡略化する。
【００２５】
各タイムフレーム内の無線モバイルノード12a-12h毎の通信リンクの数はN以下であり、各フレーム内のタイムスロットの総数は2N-1以上である。タイムスロットのスケジューリングを簡略化することに加えて、この種類の分散スケジューリングは衝突を回避する。
【００２６】
分散スケジューリングにより、何らかの２対の無線モバイルノード（例えば12a及び12b等）が、その他の無線モバイルノードと通信する必要なく、半永久的タイムスロットをスケジューリングすることが可能になる。換言すると、半永久的タイムスロットをスケジューリングするために、無線モバイルノード12a-12hの全てとの集中したマスター／スレーブ形式の調整は必要ない。無線モバイルノード12a-12hの間のタイムスロットは分散的にスケジューリングされるため、無線モバイル通信ネットワーク10に単一障害点は存在しない。
【００２７】
コントローラ18は、新しい隣接ノードと通信リンクを確立するため、半永久的タイムスロットを利用可能にする優先度に基づいて、通信リンクを優先し、通信リンクの１つをドロップしてもよい。通信リンクの優先については、以下に詳細に説明する。更に、コントローラ18はまた、この優先度に基づいて、通信リンクを優先し、少なくとも１つの利用可能タイムスロットをスケジューリングしてもよい。
【００２８】
通信リンクの数がN未満の場合には、コントローラ18はまた、半永久的タイムスロットの１つを利用可能タイムスロットとしてスケジューリングしてもよい。有利には、このことは、既存の通信リンクの必要に応じて通信リンク要求をサポートする。しかし、以下に詳細に説明するように、通信リンクの数が再びNに等しくなると、コントローラ18は、半永久的タイムスロットに戻すように要求割り当てのタイムスロットを再スケジューリングしてもよい。
【００２９】
各通信リンクは、起動側モバイルノード（12a等）と受信側モバイルノード（12b等）により作られ、起動側モバイルノードは利用可能な半永久的タイムスロットのリストを受信側モバイルノードに送信する。次に、受信側モバイルノード12bは、半永久的タイムスロットのうち１つの選択を起動側モバイルノードに送信する。次に、起動側モバイルノード12aは、選択された半永久的タイムスロットの選択を受信側モバイルノードに確認する。
【００３０】
各モバイルノードは、他の隣接モバイルノードと位置情報を交換するため、トランシーバ14に接続されている無指向性アンテナ20を更に有してもよい。交換され得る他の情報は、リソース要件と、潜在的な新しい隣接ノードの存在の検出とを有する。更に、フェーズドアレイアンテナ16は複数のアンテナビームを同時に生成してもよく、コントローラ18はスケジューリングされたタイムスロット内で複数の隣接モバイルノードにフェーズドアレイアンテナを向ける。
【００３１】
干渉検出ユニット18dは、ビーム幅内の同一線上のノードの対及び割り当てられた同じタイムスロットについて、干渉を検出して回避する。例えば図１を参照すると、同じ割り当てられたタイムスロット1の半分の間に、ノード12a及び12eはノード12b及びノード12cにそれぞれ送信している。十分に広いアンテナのビーム幅では、双方のノード12b及び12cは双方のノード12a及び12eからの送信を同時に受信し得る。干渉検出ユニット18dは、タイムスロットの使用中に物理層で信号対干渉比（SIR）を測定してもよい。代替として、CRC検査の失敗に基づいて、パケット誤り率がリンク層で測定されてもよい。これらの測定が特定の閾値に違反すると、スロットが悪化したと宣言されてもよい。
【００３２】
しかし、フェーディングにより単一のスロットがこの検査に失敗することになることがあるため、このスロットについてnの試行のうちmが劣化を受ける場合に、スロットの過度の干渉を宣言することが望ましいことがある。この時点で、コントローラ18は干渉を回避しようとする。リンクの双方の端点でのTx/Rxの順序は、タイムスロットについて切り替えられてもよい。このような切り替えが失敗した場合に、新しいタイムスロットが調整されてもよい。当然のことながら、双方のノードの対が同時に同じ変化を行おうとして、それにより衝突のままになる確率を減少させるため、これらの双方の変化は確率的に行われるべきである。
【００３３】
トラヒック調整ユニット18eは、ストリーミングビデオ又は高レートのセンサデータにより生成され得る不均衡なトラヒック負荷を管理する。調整機構は、各半二重リンクがトラヒックの何らかのTx/Rx分割でタイムスロットを割り当てることを可能にするように提供される。また、タイムスロットの最大数は、より多くの要求タイムスロットを作るため、最小より上の数まで増加してもよい。サブスロットにより、ノードが半永久的に割り当てられたタイムスロットからサブスロットを“盗み”、要求のタイムスロットを再割り当てし得るため、タイムスロットの最大数の効率的な増加又は減少が可能になる。更に、パスを通じた各ノードでタイムスロット及び／又はサブスロットの大量のセットを要求して割り当て、高レートのストリームに適応することにより、ソースから宛先ノードまでのパスを通じた各ノードで高レートのストリーム用のリソースの割り当てを指示するために、リンクスケジューリング手順と共に予約プロトコルが使用されてもよい。予約リソースでは、ストリームにより要求される容量が供給されることを確保するために、別々のキュー及びキューサービス規則が必要になることがある。
【００３４】
本発明はまた、複数のモバイルノード12a-12h用の通信リンクを確立する方法を対象としており、各モバイルノードは、トランシーバ14と、トランシーバに接続されているフェーズドアレイアンテナ16と、トランシーバに接続されているコントローラ18とを有する。その方法は、モバイルノード12a-12h毎に、隣接モバイルノードと通信リンクを確立するため、タイムフレーム毎にそれぞれ半永久的タイムスロットをスケジューリングし、各タイムフレームに少なくとも１つの利用可能タイムスロットを残すことを有する。
【００３５】
少なくとも１つの利用可能タイムスロットは、リンク通信要求に基づいて、隣接モバイルノードとの通信リンクを提供するようにスケジューリングされることが好ましい。フェーズドアレイアンテナ16は、通信中に各隣接モバイルノード12a-12hに向けられる。各タイムフレームは、Nまでの半永久的タイムスロットと、少なくとも2N-1の利用可能タイムスロットとを有してもよい。
【００３６】
その方法はまた、隣接モバイルノードから複数の受信した半永久的タイムスロット要求を処理しつつ、各隣接モバイルノードと通信リンクを確立するため、タイムフレーム毎に１つ以上の半永久的タイムスロット要求を起動し、各タイムフレームに少なくとも１つの利用可能タイムスロットを残すことを有してもよい。また、隣接モバイルノードから複数の受信した利用可能タイムスロット要求を処理しつつ、リンク通信要求に基づいて、隣接モバイルノードとの通信リンクをも提供する少なくとも１つの利用可能タイムスロットを起動することを有してもよい。
【００３７】
指向性／フェーズドアレイアンテナ16は、通信中に各隣接モバイルノード12a-12hに向けられ、隣接モバイルノードとの通信用のタイムスロットで干渉が検出され、検出された干渉に基づいて新しいタイムスロットのスケジューリングが調整される。干渉検出ユニット18dは、信号対干渉比及び／又はパケット誤り率を測定してもよい。パケット誤り率は周期的冗長検査（CRC）の失敗に基づいてもよい。また、干渉検出ユニット18dは、検出された干渉と閾値とを比較してもよい。コントローラは、検出された干渉に基づいて所定のタイムスロットについてノード間の通信の順序を切り替えることが好ましく、また、通信の順序を切り替えた後に、検出された干渉に基づいて新しいタイムスロットのスケジューリングを調整してもよい。また、各隣接モバイルノード12a-12hとの通信は、リンク通信要求に基づいてスケジューリングするため、タイムスロットを割り当てることにより調整されてもよい。
【００３８】
その方法は、新しい隣接ノードと通信リンクを確立するため、半永久的タイムスロットを利用可能にする優先度に基づいて、各ノードに対して通信リンクを優先させ、通信リンクの１つをドロップさせることを更に有する。更に、特定の通信リンクを提供するために現在スケジューリングされている利用可能タイムスロットは、リンク要求に基づいて他の通信リンクに再割り当てされてもよい。有利には、このことにより、何らかのモバイルノードが通信リンク要求の変化に適応することが可能になる。
【００３９】
半永久的タイムスロット及び利用可能タイムスロットのスケジューリングについて、詳細に説明する。指向性アンテナ16を受信側モバイルノードに動かすることについての詳細は、本発明のこの特徴が当業者に容易にわかるため、省略する。
【００４０】
説明の目的で、指向性アンテナ16がフェーズドアレイアンテナであることを仮定する。当業者に容易にわかるように、フェーズドアレイアンテナ16は、複数のアンテナ素子と、所望の方向に可動型アンテナビームを作るように調整可能な各移相器とを有する。フェーズドアレイアンテナ16は、アンテナを物理的に移動させずに、アンテナパターンを動かし又はスキャンする。
【００４１】
また、説明の目的で、無線モバイル通信ネットワーク10についての複数の仮定が行われる。まず、全ての無線モバイルノード12a-12hにより共有される高データレートのチャネルである単一の周波数帯域が存在する。この種類の伝送チャネルは、送受信の双方について全ての無線モバイルノード12a-12hの間で時間共有されている。全ての送信スロットは事前にスケジューリングされている。
【００４２】
別々の低データレートのオーバーヘッドチャネルが提供されることも仮定する。このオーバーヘッドチャネルは、ノード発見や、ネットエントリ（net  entry）や、リソース要求を含む他の様々なデータリンク制御オーバーヘッド情報の交換のために使用され得る。このオーバーヘッドチャネルは無指向性アンテナ20を介して提供される。優れたグローバルタイミング基準も全てのノードで認識される。無線モバイルノードと無線モバイル通信システム12a-12hとの用語は、以下の説明を通じて交換可能である。
【００４３】
無線モバイル通信ネットワーク10はまた、モバイルノードを見つけて追跡する機能を有し、それにより、スケジューリングされたタイムスロットが利用可能であるときに、フェーズドアレイアンテナ16が正確に指示され得る。前述のように、指示／追跡の詳細な説明については、ここでは提供しない。
【００４４】
フェーズドアレイアンテナ16が0のビーム幅を有することも仮定する。この仮定は後に緩和される。従って、所定のモバイルノードによる送信は、送信しようとしている隣接モバイルノードのみにより受信されることを仮定することができる。このことにより、タイムスロットのスケジューリングについて、あまり限定的でない一式の制約が可能になる。各通信リンクは、データを送受信するスケジューリングされたタイムスロットを表す番号でラベル付けされる。
【００４５】
制約は以下の通りである。ノードは、同じタイムスロット番号でラベル付けされた１つより多い通信リンクを有さなくてもよい。所定のタイムスロット割り当ては、２つのモバイルノード間の半二重リンクに当てはまり、送受信用に２つのノードにより交互に使用される。これらの２つの制約は、モバイルノードによりその隣接ノードの１つに割り当てられたタイムスロットが、そのノードにより他のリンクに割り当てられた以前のタイムスロットにより制約を受けることを意味する。
【００４６】
フェーズドアレイアンテナ16のタイムスロットのスケジューリングが図１に示されており、図１はスケジューリングされたタイムスロットに基づくリンク接続でのネットワーク10を示している。無線モバイルノード12a-12hがそのそれぞれのフェーズドアレイアンテナ16を隣接無線モバイルノードに向ける時を認識するように、タイムスロットがスケジューリングされる。
【００４７】
通信リンクは、双方向であることが仮定され、各タイムスロット番号がタイムスロットとそのタイムスロットで生じる各方向の送信機会とを表すように半二重で使用される。最大リンクインデックス又はフレーム内のタイムスロットの最大数を示すために、用語Nframeが用いられる。この例では、Nframe=6である。
【００４８】
図３は、タイムスロットの代表的なフレームを示している。最も簡単な構成では、各エポック又はフレームはnのスロットを有しており、nの値はNframeに設定される。図面に、ノードA及びBとしてラベル付けされたノードを接続するリンク用にどのようにタイムスロットが使用されるかについても示す。各タイムスロットは２つのミニスロット22a、22bに分割される。第１のミニスロット22a（例えばスロットの半分）は、ノードAからBへの送信用に使用される。次にリンクの方向が逆になり、第２のミニスロット22bがノードBからAへの送信用に使用される。
【００４９】
送信期間中に、複数のパケットが送信され得る。図示のように、各ミニスロット22a、22bはまた、以下の考慮に従って選択されたガード時間24a、24bを有する。何らかのノードの対の間の最大距離は、適応されなければならない最大伝搬遅延を決定する。100マイルの最大距離は、約0.5msの伝搬遅延に対応する。ミニスロット22a、22b毎にガード時間が割り当てられ、伝搬遅延の不確定性と、全てのノードの対の間の不均衡な伝搬遅延とを適応する。
【００５０】
100マイルの最大距離で、0.5msのガード時間が必要になる。100マイルの最大距離に対するガード時間の割り当ては、チャネル効率の損失を最小化するために、ミニスロット22a、22bを2〜4msのオーダにする必要があることを意味する。一例として、通信リンクでの50Mb/sのデータレートと100マイルの最大距離とを仮定すると、4msのミニスロットは200,000ビット／ミニスロット（毎秒250ミニスロット）を意味する。この場合、ミニスロットは25,000ビットのガード時間と、175,000ビットのミッションデータとを有する。
【００５１】
コントローラ18はまた、利用可能タイムスロットがスケジューリングされるときに優先度を割り当てるため、それぞれの確立したリンクをバイアスしてもよい。以下に詳細に説明するように、半永久的（SP：semi-permanent）タイムスロットと、利用可能又は要求割り当て（DA：demand  assingned）タイムスロットとが各フレーム内に提供される。定められた目的は、同時に複数のノード間でのタイムスロットの再利用を増加させることである。図１のモバイルネットワーク10は、ノードの総数及び通信リンクに制限があるが、タイムスロットの並列使用について複数の場合が存在する。例えば、タイムスロット1及び2は３つの異なる通信リンクでそれぞれ同時に使用され、タイムスロット6は１つのみのリンクで使用される。その他の全てのタイムスロットは２つの通信リンクに割り当てられる。ネットワークでのタイムスロット割り当ての総数（Nframe）に対する割り当てられたタイムスロットの数（Num_Slots_Assigned）の比として、再利用の平均レベルを示す再利用係数を定めることができる。
【００５２】
【数１】
2006522547.tif 000003
図１の例示的なネットワーク10では、再利用の手法はR=14/6=2.333の再利用係数を提供し、平均でネットワークのスケジュールに2よりやや多い各タイムスロットの同時ユーザが存在することを示す。何らか特定のスケジューリングアルゴリズムで計算された再利用係数は、ネットワークのサイズ及びトポロジにかなり依存することが明らかである。完全比較の評価には、様々なネットワークのサイズ及びトポロジを考慮すべきである。
【００５３】
各ノードが隣接を有するものと少なくとも同じタイムスロットを要求すること（すなわち、ノードがその次数と少なくとも等しい複数のタイムスロットを要求すること）を示すことにより、何らかのグラフのNframeの値の下界が決定され得る。Nframeは全グラフでの最大ノード次数と少なくとも同じ大きさである必要がある。従って、diでノードiの次数を示すことにより、Nframeの下界は次のようになる。
【００５４】
【数２】
2006522547.tif 000004
図２に示す例示的なネットワーク10では、再利用部分は、式(2)に従って使用される必要があるタイムスロットの最小数に等しいNframeでのスケジューリングを割り当てられる。いくつかのノード（すなわちノード1以外の全ノード）は、タイムスロットの全セット未満を割り当てられる点に留意すべきである。このように、拡張スケジューリングアルゴリズムは、スケジューリングに衝突を取り込まずに、リンクのいくつかに更なるスロットを割り当てることができる。
【００５５】
以下の説明は、主にリンクのスケジュールを生成するためのタイムスロットのスケジューリングに焦点を置く。最終的に対処されなければならない全般的なフェーズドアレイネットワークの問題のその他の部分は、1)ノード及び隣接発見、2)ネットエントリ、3)スケジューリングの更新についてのプロトコル交換を含むオーバーヘッドチャネルのフォーマット及びプロトコル、4)隣接ノードの追跡及び検出（フェーズドアレイアンテナ16の支援を含んでもよい）、及び5)動的ネットワークトポロジのルーティングアルゴリズムを含む。
【００５６】
本発明に従ってタイムスロットをスケジューリングする手法は、以下の原理に基づく。第１に、指定数のタイムスロットが、所定のリンク用にスケジューリングされた半永久的（SP）タイムスロットとして割り当てられる。利用可能タイムスロット（DA）の残りは、それを最も必要とするノード／リンクに対して要求割り当てに基づいて割り当てられてもよい。このことにより、必要に応じてスケジューリングをシフトするという柔軟性が可能になる。第２に、前述のように、半永久的に割り当てられたタイムスロットの最大数の制限が定められる。この制限は、特定のネットワークに基づいて選択されるパラメータである。この制限はまた、ノード毎に単一のSPタイムスロットで、許容の隣接ノードの数の上限でもある。
【００５７】
第３に、前述のように、フレーム毎のタイムスロットの最大数の制限が定められる。この制限は、同様に特定のネットワークに基づいて選択されるパラメータである。この制限は、リンク送信機会の最大再訪時間（maximum  revisit  time）を決定するため、待ち時間の制限を定めるために重要である。
【００５８】
第４に、フレーム毎の全タイムスロットの数Nframeと、フレーム毎の半永久的に割り当てられたタイムスロットの最大数の上限との間の関係は、半永久的に割り当てられたタイムスロットのスケジューリングがかなり簡略化され、分散したスケジューリングでスケジューリングの衝突がかなり回避され得るように、選択される。
【００５９】
ノード毎の半永久的に割り当てられたタイムスロットの最大数を、フレーム毎のタイムスロットの総数の特定の部分に制限することにより、半永久的に割り当てられたタイムスロットを分散的に割り当てる処理が非常に簡略化される。半永久的に割り当てられたタイムスロットの上限（従って、許容の隣接ノードの最大数）がNで示される。Nframeの値を以下のように考える。
【００６０】
【数３】
2006522547.tif 000005
ネットワーク10の全てのノード12a-12hが双方向リンクにより接続され、各ノードがその隣接ノードに時間ホップ及び指示することによるビーム共有での単一ビームのフェーズドアレイアンテナ16を有することを仮定する。更に、隣接の数がNに等しく、（隣接毎に１つのSPタイムスロットが割り当てられることで）半永久的タイムスロットの許容数の制限が固定されていることを仮定する。
【００６１】
Nframeの固定値が式(3)を満たす場合、全てのノードは、他のノードが1ホップより先でどのリンクを選択しているかに関係なく、そのリンクについての隣接との相互の合意により、リンクのそれぞれについて異なる半永久的タイムスロットを選択することができる。このことにより、各ノードは、隣接ノードのみと通信することによる非常に直接的な方法で、隣接ノードへのリンクについてその半永久的タイムスロットを割り当てることが可能になる。この処理は、Nまでの隣接ノードについて続けられ得る。
【００６２】
Nframeの値がNの固定値に対して増加すると、タイムスロットについての隣接の選択と衝突しないタイムスロットを選択するノードの機能に制約が少なくなるという認識が重要である。新しいリンクについてタイムスロットを選択するノードは、現在使用されておらず、隣接が現在使用中でないタイムスロットを選択しなければならない。
【００６３】
ノードが隣接までのリンクのそれぞれに割り当てられた単一のタイムスロットでmの隣接を有し、新しい隣接ノードへのリンクを追加している場合、隣接ノードはせいぜい(N-1)のタイムスロットを使用し得る。このように、Nframeが(m+N-1)より大きい場合、ノードが新しいリンクに割り当てることができるもう１つのタイムスロットが少なくとも利用可能である。この割り当て処理の最悪の場合は、ノードが既に（N-1）の隣接を有しており、N番目の隣接ノードにタイムスロットを割り当てている場合である。この場合、Nframeは式(3)を満たさなければならず、更なるタイムスロットがN番目の隣接へのリンクに割り当てるために利用可能であることが確保される。
【００６４】
開示されたタイムスロットのスケジューリング手法においてこの特性がいかに引き出され得るかについて、いくつかの更なる観察を行う。まず、ノードは、隣接までの指向性リンクについて割り当てられる半永久的タイムスロットの選択を調整しさえすればよい。リンクを要求するノードは、例えばリンクについて示唆するタイムスロットのリストを隣接に送信してもよい。このことは、SP割り当てに使用されていないタイムスロットに基づいてもよい。以下に説明する他の要因に基づいてこのリストに何らかの順序が存在することがあるが、このことは必ずしも必要ではない。隣接ノードは、このリストから好みのタイムスロットを選択し、この選択で応答を返信することができる。このことにより、半永久的タイムスロットをスケジューリングする簡単な完全分散型のアルゴリズムを定義することが可能になる。
【００６５】
ノードがN未満の隣接を有する場合、そのNの許可された半永久的タイムスロットのうち１より多くが個々のリンクに割り当てられてもよい。しかし、この場合には、何らかの衝突なしに、隣接から隣接へのノード調整を介して全てのNの割り当てが行われ得るという保証はない。例えば、N=6であり、ノードが3のみの隣接を有しているが、この隣接のそれぞれが6の隣接をそれぞれ有する場合、ノードはその3の隣接とのリンクのそれぞれに１つのみのタイムスロットを割り当てることができる。アルゴリズムを簡略化するために、リンク毎に１つより多くのSPタイムスロットのスケジューリングを許可しない。しかし、全ての未使用のタイムスロットは利用可能タイムスロットとして割り当てられてもよい。
【００６６】
潜在的な隣接の数が制限Nよりかなり大きくなる非常に多くの数のノードを備えた特定のネットワークでは、対処すべきトポロジ制御問題も存在する。ノードは潜在的な隣接の中から、最適なネットワークトポロジを作る隣接を選択する問題に直面する。このトポロジ制御問題はまた、エネルギー効率のよいネットワークを最適化する概念に関連する。潜在的な隣接の数が制限Nよりかなり大きい場合、接続する隣接ノードを選択するために、トポロジ制御機能が使用され得る。
【００６７】
(3)により許可される最小値をNframeに割り当てる場合、各ノードは、最大でNの半永久的タイムスロットと、合計で(2N-1)のタイムスロット割り当てとを有することが許可される。要求割り当てのタイムスロットは、トラヒック負荷に最も適応するように割り当てられる。当然のことながら、より大きい値のNframeを割り当てることも任意選択である。この場合、要求割り当てに利用可能なより多くのタイムスロットが存在する。ネットワークを構成する望ましい方法についての用途が存在し得る。
【００６８】
半永久的タイムスロットと同様に、ノードは、隣接への指向性リンクについて割り当てられる利用可能タイムスロットの選択を、その隣接と調整しさえすればよい。このことは、隣接が指向性リンクでタイムスロット割り当てについて隣接に要求を送信し、同じリンクで割り当ての許可又は要求の拒否を受信することを意味する。
【００６９】
隣接ノードからの利用可能タイムスロットDAの割り当てを要求するノードは、そのリンクの追加容量について認められた必要性に基づいて行う。これは、短期及び長期の測定に基づく高リンク利用率（キューの増加）により促されてもよい。要求は、要求のスロットの数とメトリックとを有し、要求に伴う優先度を示す。メトリックは、タイムスロット割り当ての必要性の指標として、キューの長さを示してもよい。
【００７０】
要求を受信するノードはまた、他の隣接ノードから要求を受信してもよく、その他の隣接ノードは同じタイムスロットの割り当てに対して衝突してもよい。プロトコルを簡略化するために、次の割り当てを検討する前に、ノードは１スレッドの利用可能タイムスロットDAの割り当てを完了しなければならない。これらの割り当ては、トポロジの変化の結果で半永久的タイムスロットとして再割り当てされるように常に先取りされるため、又はトラヒック要求をシフトすることにより常に再割り当てされるため、長期間持続しなくてもよい。
【００７１】
隣接及びリンク発見について説明する。分散リンクスケジューリングアルゴリズムは、ノードとの指向性リンクの確立の前に、潜在的な隣接ノードで生じる必要のある特定のプロトコル交換について、無指向性オーバーヘッドチャネルからのサポートを必要とする。このようなメッセージは、そのノードへの指向性リンクで半永久的タイムスロットの割り当てを要求するREQ_SPTSを有する。
【００７２】
ここで定められたプロトコルを直接サポートするプロトコルメッセージ交換をサポートすることに加えて、無指向性オーバーヘッドチャネルは、隣接及びリンク発見の機能をサポートしなければならない。これは、２つのノードが隣接ノードになり得ることを範囲内で移動するその他のノードに警告する無指向性アンテナ20を介して、各ノードによる周期的な全送信を通じて行われる。いくつかのアドホックルーティングプロトコル（OLSRを含む）は、このような対応のプロトコルを定めている。これらの以前に定められたプロトコルは、この分散リンクスケジューリングアルゴリズムをサポートするように適合されてもよい。このようなプロトコルにより行われなければならない主な機能は、新しい潜在的な隣接ノードを発見し、それらをトポロジ制御機能に報告することである。
【００７３】
ノード及びリンク発見の１つの手法は、各ノードが制御チャネルでビーコンメッセージを定期的に送信し、その存在及びその位置を隣接ノードに通知することを有する。更に、そのビーコン隣接（BNリスト）及びそのPA隣接ノード（PANリスト）の識別並びにそれらのノードに割り当てられたタイムスロットを隣接ノードに通知するために、リンクステートメッセージが定期的に送信される。
【００７４】
そのアルゴリズムのリンク発見部は、双方向のビーコン隣接（BBN）リストとPANリストとを継続的に比較し、PANリストにないノードがBBNリストに存在するか否かを判断する。このような何らかの隣接ノードは、PAリンクが可能であるか否かを決定するリンク検査の候補になる。この手法によれば、制御メッセージの交換の後に、確実な通信が可能であるか否かを決定するために、双方向リンクが検査される。通信が確実である場合には、新しい隣接ノードがPANリストに追加される。
【００７５】
これは、検査するタイムスロットでの通信を有効にするが、必ずしも半永久的にリンクに割り当てられ得るタイムスロットでの通信を有効にしない。１つの手法は、このようにそれを行うことであり、また、他の手法は、SPタイムスロットが割り当てられるまで待機し、それをこのタイムスロットで検査することである。
【００７６】
トポロジ制御機能は、トポロジ最適化を行う必要がない場合には、非常に簡単な機能になり得る。この機能の目的は、PANリストのノードのリストと、これらのリンクの信頼性についての情報と、ネットワークトポロジについての情報とを受け取り、PANリストの中のどのノードがPA隣接になるべきかを決定するためにこの情報を使用することである。これは、PANリストの全てのノードがPA隣接になることを許容しないPA隣接の数のような制約が存在する場合に、ネットワークトポロジを最適化する機能である。
【００７７】
Nframeの固定値及びN（ノード毎の半永久的タイムスロットの最大数）の固定値の提案の制約では、ネットワークトポロジ利用率について何らかの問題を有する可能性が存在する。これらの値が非常に小さい数になるように選択された場合には、これは特に問題になる。例えばNframe=5の場合にN=3が選択されると、新しいPA隣接ノードを追加する前にインテリジェントなトポロジ制御機能がトポロジを注意深く利用していなければ、何らかのノードについて3つに過ぎない隣接を有し得る場合に、うまく接続されたネットワークトポロジを予想することが困難になることがある。このことは大きいネットワークでは特に当てはまることがある。
【００７８】
従って、トポロジ制御機能は、隣接優先度（NP：neighbor  priority）リストを作るべきであり、その隣接優先度リストは、潜在的なPA隣接としての好ましさの順序で順序付けられたPANリストである。このリストは、潜在的なPA隣接にタイムスロットをスケジューリングする優先順序を指示する。しかし、最初の問題は、おそらく15ノードを備えた小さいネットワークの問題である。この場合、5〜8の範囲の値を有し、依然として小さい待ち時間を有するものとしてNを定めることができる。5〜8の隣接ノードの許可により、ほとんど全ての潜在的な隣接がPA隣接になることができるため、トポロジ利用率の問題が存在する可能性は非常に小さい。
【００７９】
トポロジ制御機能の第２の目的は、リンクスケジューラ処理に状態を変化させ、SPタイムスロットに対する再割り当て処理を実行させるトポロジ変化イベントを生成することである。
次に、トップレベルのスケジューリングアルゴリズム構造について説明する。前述の全手法を利用しつつ、処理の複雑性を最小化する目的で、スケジューリング処理が策定される。このスケジューリングを制御する鍵は、各ノードで各隣接ノードとのリンクに割り当てられる将来のタイムスロットのタイムスロットスケジュールの状態を反映する正確なデータ構造を維持することである。
【００８０】
２つのデータ構造（スロット割り当てDB及びリンクメッセージDB）を提案する。エポックの所定のタイムスロットのデータ構造における可能なリンク状態は、表１に記載されている。その表は、それぞれ可能な状態を記述しており、その状態についての表記を示している。表２は、例示的なスロット割り当てDAと、Nframe=9（N=5）のタイムスロット、状態毎の状態割り当て及びタイムスロット毎の例示的な割り当て隣接IDを示す内容とを示している。
【００８１】
この例では、４つの隣接がSPタイムスロットを割り当てられているため、１つの更なる隣接がこれらの制約と関連があることがある。DBタイムスロットとして割り当てられ、又は新しい隣接ノードが可能な場合にはSPタイムスロットとして割り当てられるDBタイムスロットで提供され得る１つのフリータイムスロットが存在する。リンクメッセージDBの使用については、詳細なプロトコルの説明で以下に説明する。その例はまた、サブスロット（例えばスロット毎に２つのサブスロット）の使用を示している。
【００８２】
これは、細かい精度を可能にするDA割り当てで使用される概念である。この場合の意味は、タイムスロットk、サブスロット1の割り当ては奇数番号フレームのタイムスロットkのリンクへの割り当てであるということである。逆に、サブスロット2は、偶数番号フレームのタイムスロットの割り当てを示す。
【００８３】
【表１】
2006522547.tif 000006
【００８４】
【表２】
2006522547.tif 000007
リンクスケジューリングプロトコルのトップレベルの状態図が図５に示されている。その図面は、タイムスロット割り当てデータベースを維持及び変更する役目をする２つの独立した処理30及び32を示している。左側は、半永久的（SP）タイムスロットを維持して割り当てる処理（すなわち処理30）の状態図である。この処理は、右側の処理32により行われた割り当てに対して優先する。右側の処理32は利用可能(DA)タイムスロットを割り当てる役目をする。処理経路31内で、取得され得るタイムスロットは次のようになる。すなわち、フリー、DA割り当て、及びDA割り当て中である。同様に、処理経路33内で、取得され得るタイムスロットは次のようになる。すなわち、フリー、DA割り当て、及び再割り当て必要である。
【００８５】
このデータベースは、如何なる所定のタイムスロット割り当て状態についても、２つのスケジューリング処理のうち１つのみが所定の時点で状態を変更し得るように、ロックデータベースとして制御されなければならない。処理の１つが特定のタイムスロット割り当ての状態を変更し始めると、状態がロックされ、それが解放されるまで他の処理はそれを変更することができない。
【００８６】
常に、DBの各タイムスロットは、表１に示す７の状態のうち１つになる。スケジューリングの衝突が割り当てを妨げているため、又はタイムスロットが最近フリーになってまだスケジューリングされていないため、利用可能タイムスロットはフリー状態になると考えられる（すなわち、その隣接ノードの１つへのリンクを割り当てられない）。
【００８７】
前述のように、フリー状態のタイムスロットは、SPタイムスロットとしてスケジューリングされてもよく、DAタイムスロットとしてスケジューリングされてもよい。SP割り当てとして割り当てられたタイムスロットは、SPタイムスロットを維持する処理によってのみ変更され得る。ネットワークトポロジが変化した場合又はより望ましいトポロジが可能な場合に、この処理によりタイムスロットが割り当て解除されてもよい。このようなタイムスロットがフリー状態に戻るまで、DAタイムスロットを維持して割り当てる処理はその状態を変更することができない。
【００８８】
更に、SP割り当て中であることを示すDB状態を備えた如何なるタイムスロットも、DA割り当て処理により割り当てられることができない。このことは、SP要求及び応答メッセージが送信されていることを示す状態を含む。しかし、タイムスロットの状態がDA割り当てである場合、DA割り当て処理により再割り当てされてもよい。DAタイムスロットの再割り当てが必要であることをネットワークの負荷が示した場合に、このことが行われてもよい。
【００８９】
一方、SPタイムスロットを割り当てる処理は優先度を有する。フリースロットを割り当てることに加えて、DA割り当てされている又はDA割り当て中である全てのタイムスロットを取得して再割り当てしてもよい。このことは、Nframeのタイムスロットのフレーム中に各隣接ノードに割り当てられる単一のSPタイムスロットを少なくとも確保する簡単な処理を提供するために行われる。SP割り当てのタイムスロットは、リンクが損失した場合、又は特定のリンクが隣接ノードと確立される上位Nリンクのリストにもはや存在しないことをトポロジ制御機能が決定した場合にのみ、SP割り当てのタイムスロットがフリーに戻される。
【００９０】
図５は、この処理がトップレベルでどのように動作するかを示している。SPスロット割り当て処理は、タイムスロットの割り当てにおいて大きな柔軟性を有する。それはDA処理より多くの割り当て用タイムスロットを取得することができ、DA割り当てされた又はDA割り当て中のタイムスロットを取得することができる。SP処理は、トポロジ制御機能及びプロトコルメッセージからのトポロジ変化イベントを含む処理について、様々なイベントを受信してもよい。
【００９１】
このようなイベントは、隣接へのリンクの損失と、新しい隣接の発見と、隣接ノードからのSP割り当て要求メッセージの受信と、隣接へのリンクの追加、リンクの中断又はその双方のトポロジ変化が生じたことの発見とを有してもよい。トポロジ変化イベントの通知は、生じる必要のあるトポロジ変化を記述するデータを運ぶ。
【００９２】
イベントがリンクの損失を記述する場合、行われなければならない唯一の動作は、タイムスロット割り当てDBの適切なタイムスロット状態を“フリー”に変更することである。リンクが追加されると、処理はより複雑になる。この場合、SPスロット割り当て処理は、新しい隣接ノードとプロトコルメッセージ交換を起動し、スロット割り当てDBを変更する。このことは、このリンクに割り当てられたSPタイムスロットのタイムスロット割り当てについて、最終的に２つのノード間での合意を生じる。単一のSPタイムスロットのみが隣接への各リンクに割り当てられ、プロトコルを簡略化する。このプロトコルの更なる詳細について以下に説明する。
【００９３】
DAタイムスロットを割り当てる処理は、同様の手順に従う。DAスロット割り当て処理は、DAタイムスロットの必要性を計算し、それを割り当てられたタイムスロットと比較し、新しいタイムスロットの再割り当てが必要であるか否かを決定しなければならない。DAスロットの再割り当てが起動されると、再割り当てされたタイムスロットについて合意するために、隣接ノードと一連のプロトコルメッセージ交換にも導く。DAスロット割り当て処理は、フリー状態の又はSP割り当てされていないタイムスロットのみを再割り当てしてもよい。プロトコルの詳細及びDAタイムスロットの再割り当てが必要な時を決定する処理について、更に以下に説明する。
【００９４】
指向性リンクに半永久的タイムスロットを割り当てることについて説明する。Nの半永久的タイムスロットを割り当てる手法の説明において、Nが固定であり、ネットワークの大きさ及び環境に関してインテリジェントに選択されることを仮定する。また、Nframe=2N-1であると仮定する。特定のネットワーク及びトラヒック環境に有用であると考えられる場合には、Nframeは、更なる要求時タイムスロットを提供するために、これより大きい如何なる値に設定されてもよい。
【００９５】
複数の重要な機能がトポロジ制御機能により提供される。隣接優先度（NP）リストは、トポロジ制御機能により生成され、タイムスロットの割り当てについて好ましいPA隣接ノードを示すために使用される。
【００９６】
NPリストの長さがN以下である場合、トポロジ制御機能は、SPスロット割り当て処理に対してトポロジ変化イベントを生成し、これらの隣接ノードの全てにタイムスロット割り当てを取得する試みを行う。NPリストの長さがNより大きい場合、それはSPスロット割り当て処理に対してトポロジ変化イベントを生成し、NPリストでNの最高の優先度のノードのそれぞれに対してタイムスロット割り当てを得る。
【００９７】
NPリストは、ネットワークのダイナミクスにより絶えず変化する。PAリンクが停止すると、ノードがNPリストから除去され、そのリンクのタイムスロットが再割り当てを受ける。これは、SPスロット割り当て処理にリンク削除イベントを送信するトポロジ制御機能により起動される。このように、そのリンクに割り当てられたSPタイムスロット及び何らかのDAタイムスロットは、PAリストの他のノードへの再割り当てに利用可能になる。
【００９８】
スロットが利用可能になるときの最初の選択肢は、NPリストの現状態を仮定して可能である場合には、更なるPA隣接ノードにスロットを割り当てることである。更なる隣接ノードが追加できない場合には、スロットはDAに基づいて再割り当てされ得る。
【００９９】
図６は、SPスロット割り当て処理の状態図を示している。プロトコルメッセージ処理を管理するために、リンクスケジューリングDBが表３に示すように生成される。これは、次のSPメッセージが処理用に到達したときに使用される前のプロトコル交換から必要な状態を維持する。他の状態の１つへの状態変化を許可する前に、受信したイベントを検査するという点で、アイドル処理はイベント管理を行う。
【０１００】
これらの動作は、受信したメッセージを検査し、DBの現状態と一致するか否かを決定することを有する。メッセージがDBと矛盾する場合、それは破棄される。特定のタイムアウトは、DB状態がリセットされる必要があることを示してもよい。この処理はこの機能を実行する。
【０１０１】
【表３】
2006522547.tif 000008
以下の表４に記載するように、SPタイムスロット割り当てプロトコルに必要な４つの基本的なメッセージ形式が存在する。これらの使用は自明であり、前の説明と一致する。
【０１０２】
【表４】
2006522547.tif 000009
SPタイムスロット割り当ての例を図７に示す。ノード1及び2は、リンク毎に示すSPスロット割り当てで３つの隣接を有する。従って、その間に更なるリンクを追加することができる。リンクスケジューリングプロトコルは、SP割り当てに許容のタイムスロットを見つける。対応のプロトコルメッセージ交換が表５に示されている。
【０１０３】
ノード1は、少なくともNのタイムスロットのリストでREQ_SPTS(L=(4,5,6,7))を送信することにより、交換を起動する。このリストは、全てのフリー及びDAタイムスロットを有してもよい。ノード1は、その隣接へのSP割り当てに対してスロット1、2及び3を使用しているため、そのリストLは他のタイムスロット4、5、6及び7を含む。要求メッセージが送信されると、タイムスロット及びリンクスケジューリングメッセージのデータ構造に適切な変化が行われる。ノード2は、その3つの隣接へのそのリンクのSP割り当てとして、タイムスロット4、5及び6を使用しているため、新しいリンクに対して動作する唯一のものとしてタイムスロット7を選択する。それはこの選択を応答メッセージで送信する。
【０１０４】
応答メッセージが送信されると、同様にタイムスロット及びリンクスケジューリングメッセージのデータ構造に対して適切な変化が行われる。最終的に確認が送信又は受信されると、適切なタイムスロットの状態は“リンク(1,2)へのSP割り当て”に変更される。
【０１０５】
ノード1及び2が既に4の隣接ノードを選択している場合には、その隣接のうち少なくとも２つと同じタイムスロットを使用するときに、その間のリンクを確立する共通のタイムスロットを見つけることも可能である。
【０１０６】
【表５】
2006522547.tif 000010
図６で必要な処理を記述するいくつかの初期擬似コードについて明らかにした。生じる可能性があり、SPスロット割り当て処理34により処理されなければならない様々なイベントが存在する。イベント管理は、表６に示すアイドル処理で行われる。４つの種類のイベントが示されている。すなわち、受信メッセージ、タイムアウトの検査、トポロジ制御からのリンク追加の通知、及びリンク障害又はリンク削除である。
【０１０７】
受信メッセージは、まずリンクスケジューリングメッセージDBに対して検査が行われ、メッセージがDBの現状態と一致することを確保する。例えば、隣接に要求を送信した場合、次に予期するメッセージは応答である。この分散プロトコルを簡略化するために、SPプロトコルメッセージ交換の唯一のスレッドが同時に許可される。これは、リンク追加移行の起動前又はREQ_SPTSメッセージの処理前に他のメッセージ交換が行なわれているか否かを検出するためにDBを検査することによる手順で、実行される。
【０１０８】
他のSPプロトコルのスレッドが現在処理中であるため、リンク追加が起動不可能である場合、他の処理が完了すると思われる後の時間にバックオフ及び再スケジューリングすることにより、リンク追加は延期される。リンクを同時に追加しようとする複数のノード間で潜在的な衝突を処理するため、複数の試行の許可が行われる。これは、信頼のないRFリンクの問題を処理することを意図しているのではない。この後者の問題は、損失／誤りメッセージを回復するためにARQ及び再送信を使用するオーバーヘッドチャネルでリンクプロトコルを使用することにより、処理されるべきである。
【０１０９】
このように、分散スケジューリングプロトコルは、メッセージが損失しないことを仮定することができる。これはプロトコルの簡略化を可能にする。トポロジ制御が新しい隣接として接続するためにNPリストから隣接ノードを選択すると、（アイドル処理での整合性検査の後で）SPスロット割り当て処理にリンク追加状態への移行を生じるトポロジ変化（リンク追加）イベントを発行する。
【０１１０】
【表６】
2006522547.tif 000011
リンク追加処理の擬似コードは表７に示されている。これは、２つの隣接ノードのみの間のSPタイムスロット割り当て及びプロトコルメッセージ交換の調整を必要とする処理を開始する。リンクを要求するノードは、リンクの許容のタイムスロットのリストと共に、REQ_SPTSメッセージを候補の隣接ノードに送信する。
【０１１１】
候補のタイムスロットのリストは、少なくとも１つの半永久的タイムスロットSPを有する少なくともNのタイムスロットを有さなければならない。リストはまた、場合によってはN-1の利用可能DAタイムスロットの全てを有し得る。利用可能又は要求タイムスロットは、現時点で要求トラヒックに一時的に割り当てられてもよい。このリストは優先順位付けされ、現在利用可能なタイムスロット割り当ての最小の摂動を生じるタイムスロットの嗜好を示す。換言すると、使用される表記は、タイムスロットがまだ通信リンクに割り当てられていないSPタイムスロットであるということである。2N-1のタイムスロットのいずれもSPタイムスロットでもよい。このように、送信されるNのタイムスロットのリストは、全てフリータイムスロット又は利用可能DAタイムスロットのいずれか一方である。これらはN-1のSPタイムスロットでもよいが、既に割り当てられており、リストに存在しない。
【０１１２】
REQ_SPTSメッセージは、MAX_TRIES回数まで送信可能であり、信頼のないリンクと、潜在的に同時に生じている他の割り当てとの衝突とを考慮する。REQ_SPTSメッセージに応じて隣接ノードからのREPLY_SPTSメッセージが存在しない場合、リンクスケジューリングメッセージDBのタイムアウトはリトライを起動する。REQ_SPTSメッセージが送信されると、処理は他のイベントが処理可能なアイドル状態に戻る。
【０１１３】
【表７】
2006522547.tif 000012
ERQ_SPTSメッセージを受信した隣接は、そのSPスロット割り当て処理をREQ_SPTS処理状態に移行する。このメッセージを処理する手順は、表８に示されている。この手順はタイムスロットの提供リストLsを受け取り、その好ましいタイムスロットNsを選択する。
【０１１４】
隣接ノードへのリンクの数Num_linksが制限N未満である場合、その手順は、このリストから好みのタイムスロットを選択する。次にこの選択でREPLY_SPTS応答メッセージが送信される。リンクが受け入れられない場合、又は処理中の他のSPスロット割り当てが存在する場合、否定REPLY_SPTS応答メッセージが送信される。
【０１１５】
選択されるタイムスロットは、そのNの利用可能タイムスロットの１つ又はそのフリータイムスロットの１つから選択される。利用可能タイムスロットは“フリー”タイムスロット又は利用可能DAタイムスロットである。他のリンクを追加可能な場合には、これらのうち少なくともNが存在する。各ノードはそのタイムスロットを常に管理しており、そのため、半永久的タイムスロットとして割り当てるように利用可能なNのタイムスロットが存在する（多数の隣接ノードが利用可能である場合にはNの隣接ノードのそれぞれに対して１つ）。それがリンクを受け入れる場合には、ノード毎に割り当てられる１つの半永久的タイムスロットでせいぜいN-1の他の隣接ノードを有する。その手順はまた、リンクスケジューリングDB及びスロット割り当てDBの状態に適切な変更を行う。
【０１１６】
【表８】
2006522547.tif 000013
受信REPLY_SPTSメッセージは表９に示すように処理される。隣接ノードから受信したタイムスロットの選択Nsがメッセージから抽出される。また、割り当てられたタイムスロットを使用することに合意することを示す肯定又は否定CONFIRMメッセージで、ノードがこの応答を確認することを必要とする。この３方向ハンドシェイクは、スケジューリング処理の結果の不確実性を除去する。
【０１１７】
REPLY_SPTSメッセージが肯定応答である場合、タイムスロットの選択Nsは依然として新しいリンクの新しいSPタイムスロットの許容の割り当てであるか否かを検出するために、検査される。許容される場合、スロット割り当て及びリンクスケジューリングメッセージデータベースの状態に対して適切な変更が行われる。次に肯定CONFIRMメッセージが返信される。
【０１１８】
受信REPLY_SPTSメッセージが否定的である場合、スロット割り当て及びリンクスケジューリングメッセージデータベースがこのNbr_IDについてリセットされる。Nsの選択がもはや許容されない場合、リンクスケジューリングメッセージデータベースはこのNbr_IDについてリセットされる。次に否定CONFIRMメッセージが隣接ノードに送信され、リンクを拒否する。
【０１１９】
【表９】
2006522547.tif 000014
表１０は、CONFIRMメッセージを処理する手順を示している。CONFIRMが肯定的である場合、リンクは隣接のセットに追加されると考えられる。ノードのリンクの数Num_linksが増加する。割り当てられたタイムスロットNsはスロット割り当てDBでSP_Allocにマークされ、リンクスケジューリングメッセージDBのリンクメッセージ状態がインデックスNbr_IDについてリセットされる。メッセージが否定CONFIRMである場合、スロット割り当て及びリンクスケジューリングメッセージデータベースがそのNbr_IDについてリセットされる。
【０１２０】
【表１０】
2006522547.tif 000015
割り当てられたタイムススロットは複数の理由のうち１つで割り当て解除される必要があってもよい。通常の動作中にリンクが中断された場合又は信頼性がなくなった場合、トポロジ制御機能は、信頼のないリンク問題に対処するために関与する。最終的には、SP割り当て処理を指示するトポロジ変化（例えばリンク削除）イベントを生成し、リンクに割り当てられた全てのスロットを削除してもよい。
【０１２１】
この処理に関するステップが表１１に示されている。リンクは、他のノードと共有されている全てのタイムスロットの割り当て解除を要求するノードからDELETE_TSメッセージを送信することにより、割り当て解除される。更に、リンクスケジューリングメッセージDB及びタイムスロット割り当てDBの適切なエントリがリセットされる。
【０１２２】
【表１１】
2006522547.tif 000016
表１２は、受信DELETE_TSメッセージを処理する手順を示している。割り当て解除されるタイムスロットのリストLsは、メッセージから抽出される。次に、スロット割り当てDB及びリンクスケジューリングDBの適切な状態がリセットされる。
【０１２３】
【表１２】
2006522547.tif 000017
要約すると、半永久的タイムスロットを割り当てる機能の目的は、Nまでのできるだけ多くの隣接ノードに接続するためである。Nの隣接ノードが取得されると、それぞれが単一の半永久的タイムスロットを割り当てられる。このプロトコルにより新しいリンクが確立されると、双方のノードは新しく割り当てられたSPタイムスロットで動作を開始する。
【０１２４】
この動作は新しいリンクを検査し、割り当てられたタイムスロットを使用して信頼のある通信が維持され得るか否かを決定する。このことは、この特定のタイムスロットで生じる異常な干渉が存在しないことを確保する。リンクが信頼ないと検査されると、タイムスロットが割り当て解除されて他の目的に使用され得るように、トポロジ制御機能が通知される。
【０１２５】
利用可能（要求）タイムスロットの割り当てについて説明する。利用可能タイムスロットは、ネットワークトラヒックの変動する要求に応じるように割り当てられる。この場合にも同様に、Nは固定であり、ネットワークの大きさ及び環境に関してインテリジェントに選択されることを仮定する。また、Nframe=2N-1と仮定する。
【０１２６】
利用可能容量の割り当てで細かい精度を可能にするために、タイムスロットはmsのサブタイムスロットに分割される。残りの以下の説明ではms=2と仮定する。これは、第ms（又は第２）フレーム毎に繰り返す特定のタイムスロット割り当てになるサブタイムスロットを定めることにより実現される。
【０１２７】
あるノードから隣接ノードへの利用可能タイムスロットの要求は、これらの２つのノードの間のリンクに少なくとも１つの半永久的タイムスロットが割り当てられる場合にのみ、許可される。リンクが少なくとも１つの半永久的タイムスロットを割り当てられた後に、ノードは第ms（又は第２）フレーム毎に単一のタイムスロットの割り当てを要求してもよい。利用可能タイムスロットをスケジューリングするために使用されるメッセージは、リンクがフレーム毎に少なくとも１つの半永久的タイムスロットの割り当てを有するときから必要となる時の数フレーム前にタイムスロットをスケジューリングするため、PAリンクで送信され得る。
【０１２８】
利用可能タイムスロットの効率的な割り当ての主要な要件は、各リンクでのトラヒック要件の測定である。まず、（フレーム毎のタイムスロットの数の単位での）リンク(i,k)で送信される測定平均トラヒックは、Tikseで示される。この測定は、フレーム毎の１つ以上の半永久的タイムスロット及び何らかの利用可能タイムスロットで送信される全てのトラヒックを含む。
【０１２９】
更に、リンク(i,k)のキュー状態Qikの現在の測定を維持する必要もある。大きい値のQikは、１つ以上の利用可能タイムスロットの迅速な割り当ての要求を示す。要求の時折のバーストは、Qikの増加を生じてもよく、キューの大きさが減少するまで要求の容量の更なるタイムスロットの要求を起動する。
【０１３０】
リンク(i,k)に割り当てられる（ms=2で1/2のタイムスロットに量子化された）タイムスロットの総数は、Niktotで示される。タイムスロット要求は以下のように定められる。
【０１３１】
【数４】
2006522547.tif 000018
これは測定トラヒックとキューの大きさにより示される必要な推定追加容量との関数である。このリンクで必要なタイムスロットの数Tikneedは以下になる。
【０１３２】
【数５】
2006522547.tif 000019
このリンクに割り当てられるメトリックは以下になる。
【０１３３】
【数６】
2006522547.tif 000020
これはDAスロット割り当て機構を通じてこのリンクに割り当てられる更なるタイムスロットの推定数の測定である。Bは、各リンクがかなりのキューを回避するように、タイムスロットの1/4から1/2が十分に過度の容量を割り当てられるように名目上設定される。(4)で定められたメトリックを使用した手法を示しているが、DAタイムスロットを割り当てる基礎として、様々な他の種類のメトリックも使用され得る。
【０１３４】
図８は、DAスロット割り当て処理36の状態図を示している。状態図及びプロトコル交換は、SPスロット割り当て処理のものと類似している。プロトコルメッセージ処理を管理するために、DAタイムスロット割り当ての単一のスレッドのみが常に処理可能である。他の状態の１つへの状態変化を許可する前に、受信したイベントを検査するという点で、アイドル処理はイベント管理を行う。
【０１３５】
これらの動作は、受信したメッセージを検査し、DBの現状態と一致するか否かを決定することを有する。メッセージがDBと矛盾する場合、それは破棄される。特定のタイムアウトは、DB状態がリセットされる必要があることを示してもよい。この処理はこの機能を実行する。それはまた、ノードのトラヒックロードの必要性を考慮してDAスロット割り当てが最適であるか否かを決定する。それは、新しいDAタイムスロットが特定のリンクに追加されなければならないか否かを決定した場合に、DAスロット追加状態への移行をもたらしてもよい。
【０１３６】
以下の表１３に記載するように、DAタイムスロット割り当てプロトコルに必要な４つの基本的なメッセージ形式が存在する。これらはSPスロット割り当てで使用されるものと非常に類似している。これらの使用は自明であり、SPスロット割り当てについての前の説明と一致する。
【０１３７】
【表１３】
2006522547.tif 000021
DAタイムスロット割り当ての例を図９に示す。ノード1は、そのリンク(1,2)について更なるDAタイムスロット割り当てを追加しようとする。対応のプロトコルメッセージ交換が表５に示されている。ノード1は、スロット5及び6並びにサブスロット4.2の割り当てをサポートし得ることを示すREQ_DATS(L=(4.2,5,6))を送信することにより、交換を起動する。このリストは、全てのフリー及びDAタイムスロットを有してもよい。そのうちの後者はあまり必要でない。
【０１３８】
要求が送信されると、タイムスロット及びリンクスケジューリングメッセージのデータ構造に適切な変化が行われる。ノード2は、その3つの隣接へのそのリンクのSP割り当てとして、タイムスロット1、3及び6を使用しており、DA割り当てとして、サブスロット2.1及び3.2を使用している。それはサブスロット4.2又はスロット5の双方のサブスロットを選択することができる。それは選択を行い、その選択を応答メッセージで送信する。
【０１３９】
応答メッセージが送信されると、同様にタイムスロット及びリンクスケジューリングメッセージのデータ構造に対して適切な変化が行われる。最終的に確認が送信又は受信されると、適切なタイムスロットの状態は“リンク(1,2)へのサブスロット4.2のDA割り当て”に変更される。
【０１４０】
【表１４】
2006522547.tif 000022
隣接ノードへの指向性リンクに(N-1)の利用可能タイムスロットを割り当てるために、各ネットワークノードで以下の手法が使用される。これらの手段を用いて、各ノードは反永久的タイムスロットを割り当てられたそのリンク毎にリンクメトリックMikDAを維持する。各ノードは、各隣接ノードへの更なる送信タイムスロットの必要性を示すために、このメトリックを使用する。MikDAの最大値は、更なる要求タイムスロット割り当てを最も必要とするリンクを示す。MikDAの正の値は、必要な更なるタイムスロットの数を示し、その負の値は、再割り当てに引き渡され得るタイムスロットの数を示す。
【０１４１】
メトリックMikDAが維持されると、最大リンクメトリックが更なるサブスロット割り当ての必要性を示し、フリースロットとして又は他のリンクへの過度のDA割り当て（同様に小さいメトリックで示される）として利用可能なサブスロットが存在する場合に、DAスロット追加状態に移行する処理、及びDAサブスロット割り当てを見つける処理が起動される。
【０１４２】
半永久的タイムスロットと同様に、ノードは、隣接への指向性リンクについて割り当てられるDAタイムスロットの選択を、その隣接と調整しさえすればよい。このことは、隣接が指向性リンクでタイムスロット割り当てについて隣接に要求を送信し、同じリンクで割り当ての許可又は要求の拒否を受信することを意味する。
【０１４３】
図８で必要な処理を記述するいくつかの擬似コードが構築される。生じる可能性があり、DAスロット割り当て処理により処理されなければならない様々なイベントが存在する。イベント管理は、表６に示すアイドル処理で行われる。
【０１４４】
４つの種類のイベントが示されている。すなわち、1)受信メッセージ、2)タイムアウトの検査、3)リンクメトリックの再計算、及び4)DAタイムスロット要求及びDAタイムスロット削除である。受信メッセージは、まずリンクスケジューリングメッセージDBに対して検査が行われ、メッセージがDBの現状態と一致することを確保する。例えば、隣接に要求を送信した場合、次に予期するメッセージは応答である。
【０１４５】
この分散プロトコルを簡略化するために、DAプロトコルメッセージ交換の唯一のスレッドが同時に許可される。これは、リンク追加移行の起動前又はREQ_DATSメッセージの処理前に他のメッセージ交換が行なわれているか否かを検出するためにDBを検査することによる手順で、実行される。他のDAプロトコルのスレッドが現在処理中であるため、更なるスロットが起動不可能である場合、更なるスロットは行われない。
【０１４６】
それは、リンクメトリック及びDAタイムスロット要求の再計算の次の機会に当然に再スケジューリングされる。リンクメトリックは、予め設定されたスケジュールに従って定期的に再計算される。特定の閾値Max_metric_thresholdより大きいリンクメトリックを有するリンクは、新しいDAサブスロットを取得する候補になる。
【０１４７】
この閾値を超過した最大メトリックを備えたリンクは、新しいDAサブスロットが割り当てられる次のリンクとして選択される。新しいDAサブスロットが割り当てられる必要がある場合、及びそれが前記の条件を満たす場合、DAスロット追加状態への移行はDAスロット割り当て処理で生じる。
【０１４８】
【表１５】
2006522547.tif 000023
更なるDAスロット処理の擬似コードは表１６に示されている。これは、２つの隣接ノードのみの間のSPタイムスロット割り当て及びプロトコルメッセージ交換の調整を必要とする処理を開始する。リンクを要求するノードは、リンクの許容のタイムスロットのリストと共に、REQ_DATSメッセージを候補の隣接ノードに送信する。
【０１４９】
候補のタイムスロットのリストは、所定の閾値Min_metric_thresholdより小さいメトリックを備えた全てのフリータイムスロット及び全てのDAサブスロットを有さなければならない。DAタイムスロットは、現時点で他のDAトラヒックに一時的に割り当てられてもよい。このリストは優先順位付けされ、現在の要求タイムスロット割り当ての最小の摂動を生じるサブタイムスロットの嗜好を示す。優先順位は、最初にフリータイムスロットであり、次に最小のメトリックを備えたサブスロットが続き、Min_metric_thresholdより小さい最大のメトリックまで進む。
【０１５０】
この分散プロトコルを簡略化するため、DAプロトコルメッセージ交換の唯一のスレッドが同時に許可される。これはアイドル手順で実施される。REQ_DATSメッセージは一回のみ送信されるが、隣接ノードが他のDAプロトコル交換を現在処理している場合にはそれは不成功になり得る。この場合、ノードは最終的に否定REPLY_DATSメッセージを受信する。この場合、次にリンクメトリックが評価されるまでにこのリンクが最大のメトリックを有する場合には、DAスロットを追加する試みは再度行われる。REQ_DATSメッセージが送信されると、処理は他のイベントが処理可能なアイドル状態に戻る。
【０１５１】
【表１６】
2006522547.tif 000024
ERQ_DATSメッセージを受信した隣接は、そのDAスロット割り当て処理をREQ_SPTS処理状態に移行する。このメッセージを処理する手順は、表１７に示されている。この手順はサブスロットの提供リストを受け取り、その好ましいタイムスロットNsを選択する。受け入れられるサブスロットはリストlsの最初のサブスロットであり、スロット割り当てDBでフリーとしてマークされたもの、又はMin_metric_threshold未満のリンクメトリックでDA割り当てされたものである。次にこの選択でREPLY_DATS応答メッセージが送信される。リンクが受け入れられない場合、又は処理中の他のDAスロット割り当てが存在する場合、否定REPLY_DATS応答メッセージが送信される。その手順はまた、リンクスケジューリングメッセージDB及びスロット割り当てDBの状態に適切な変更を行う。
【０１５２】
【表１７】
2006522547.tif 000025
受信REPLY_DATSメッセージは表１８に示すように処理される。隣接ノードから受信したサブスロットの選択Nsがメッセージから抽出される。割り当てられたタイムスロットを使用することに合意することを示す肯定又は否定CONFIRMメッセージで、ノードがこの応答を確認することを必要とする。SP割り当て処理で示したように、この３方向ハンドシェイクは、スケジューリング処理の結果の不確実性を除去する。
【０１５３】
REPLY_DATSメッセージが肯定応答である場合、サブスロットの選択Nsは依然として新しいリンクの新しいDAサブスロットの許容の割り当てであるか否かを検出するために、検査される。許容される場合、スロット割り当て及びリンクスケジューリングメッセージデータベースの状態に対して適切な変更が行われる。次に肯定CONFIRMメッセージが返信される。
【０１５４】
受信REPLY_SPTSメッセージが否定的である場合、スロット割り当て及びリンクスケジューリングメッセージデータベースがこのNbr_IDについてリセットされる。Nsの選択がもはや許容されない場合、リンクスケジューリングメッセージデータベースはこのNbr_IDについてリセットされる。次に否定CONFIRMメッセージが隣接ノードに送信され、リンクを拒否する。
【０１５５】
【表１８】
2006522547.tif 000026
表１９は、CONFIRMメッセージを処理する手順を示している。CONFIRMが肯定的である場合、選択されたサブスロットがNbr_IDに対するリンクへの割り当てに追加される。割り当てられたタイムスロットNsはスロット割り当てDBでSP_Allocにマークされ、リンクスケジューリングメッセージDBのリンクメッセージ状態がインデックスNbr_IDについてリセットされる。メッセージが否定CONFIRMである場合、スロット割り当て及びリンクスケジューリングメッセージデータベースがそのサブスロットについてリセットされる。
【０１５６】
【表１９】
2006522547.tif 000027
割り当てられたタイムススロットは複数の理由のうち１つで割り当て解除される必要があってもよい。通常の動作中にリンクが中断された場合又は信頼性がなくなった場合、トポロジ制御機能は、信頼のないリンク問題に対処するために関与する。最終的には、SP割り当て処理を指示するトポロジ変化（例えばリンク削除）イベントを生成し、リンクに割り当てられた全てのスロットを削除してもよい。
【０１５７】
この処理に関するステップが表１１に示されている。リンクは、他のノードと共有されている全てのタイムスロットの割り当て解除を要求するノードからDELETE_TSメッセージを送信することにより、割り当て解除される。更に、リンクスケジューリングメッセージDB及びタイムスロット割り当てDBの適切なエントリがリセットされる。
【０１５８】
【表２０】
2006522547.tif 000028
表２１は、受信DELETE_TSメッセージを処理する手順を示している。割り当て解除されるサブスロットLsは、メッセージから抽出される。次に、スロット割り当てDB及びリンクスケジューリングDBの適切な状態がリセットされる。
【０１５９】
【表２１】
2006522547.tif 000029
リンクスケジューリングアルゴリズムはまた、フェーズドアレイアンテナ16により生成された複数の同時ビームにも適用可能である。複数ビームのフェーズドアレイ（又はその他の形式の複数の指向性アンテナ）のような別々の受信機を備えた複数のアンテナビームをそれぞれ使用するノードでシステムを拡張することを仮定する。更に、全てのノードが同じ数のビームを有する必要がないことを仮定する（すなわちノードkはBkのビームを有する）。これは、何らかのタイムスロットで可能なBkの並行リンクに相当する。
【０１６０】
以前の説明（単一方向のビームの仮定）を、BkのビームがBkより大きい隣接ノードのセットの間で時間共有されることに拡張する。ノードがそれぞれ異なる数のビームを有し得るとしても、全てのノードは、各ビームについてのフレーム毎のタイムスロットの数がNframeに等しい共通のタイムスロットの形式及びフレームを使用しなければならない。
【０１６１】
Nbeamにより示されるそのBkのビームのうちいずれか１つでの半永久的（SP）に割り当てられたタイムスロットの何らかのノードkでの上限（従ってビーム毎の許容の隣接ノードの最大数）を検討する。Nbeamの値はフレーム毎のタイムスロットの数のみに依存し、ビームの数に依存しない。(3)のように、Nbeamが以下の式を満たさなければならないことを指定する。
【０１６２】
【数７】
2006522547.tif 000030
ネットワークの全てのノードが双方向リンクにより接続され、ノードkがその隣接ノードに時間ホップ及び指示することによるビーム共有でのBkのビームを有することを仮定する。更に、ビーム毎に許可される隣接の数がNbeamに等しく、（隣接毎に１つのSPタイムスロットが割り当てられることで）ビーム毎に許可される半永久的タイムスロットの許容数の制限が固定されていることを仮定する。
【０１６３】
各隣接ノードのビーム毎のNbeamの固定値が(7)を満たす場合、全てのノードは、他のノードが1ホップより先でどのリンクを選択しているかに関係なく、そのリンクについての隣接との相互の合意により、リンクのそれぞれについて及びそのビームのそれぞれについて異なる半永久的タイムスロットを選択することができる。このことにより、各ノードは、その隣接ノードのみと通信することによる非常に直接的な方法で、各ビームについてそのNbeamの半永久的タイムスロットを割り当てることが可能になる。この方式に従うことにより、各ノードは少なくとも
【０１６４】
【数８】
2006522547.tif 000031
の隣接をサポートすることができ、ビーム毎に割り当てられるせいぜいNbeamのタイムスロットでの単一のSPタイムスロットをそれぞれ割り当てられる。
【０１６５】
(7)が満たされる限り、ビーム毎のNbeamの隣接がサポート可能であるという確認は、単一のビームの所見の確認から直接得られる。全てのBkのビームが同じようにスケジューリングされたSPタイムスロットを有する場合、サポートされ得る隣接ノードの数は、ビームの数とビーム毎の隣接の数との積であり、(8)になることが明らかである。
【０１６６】
ノード毎に異なる数のビームを備えた２つのノードの間のSPタイムスロットの割り当ての例が図１０に示されている。この例では、ノード1が２つのビームを有しており、ノード2が３つのビームを有している。２つのノードは異なる数のビームを有しているが、双方のノードは同じフレーム構造を使用しなければならない。この例では、フレーム毎にNframe=5のタイムスロットである。(7)及び(8)から、このことにより、ノード1が最大で6の隣接を有し、ノード2が最大で9の隣接を有することが可能になる。
【０１６７】
最初に、双方のノードが最大数の隣接未満のものを有しており、それらは(7)及び(8)の制約で許可される。SPビーム／タイムスロットの割り当てがリンク毎に示されている。これらのノードはその間に更なるリンクを追加することができるが、依然として(7)及び(8)の制約を満たす。リンクスケジューリングプロトコルは、ノード毎のSP割り当てについて満足できるビーム／タイムスロットを見つけ、単一のビームの場合と基本的に同じように動作する。
【０１６８】
対応のプロトコルメッセージ交換が表２２に示されている。ノード1は、少なくともNbeamの候補のタイムスロットのリストでREQ_SPTS(L=(1,2,3))を送信することにより、交換を起動する。３つのビームIDはa、b及びcで示されており、タイムスロット番号はビームIDの添え字で示されている。ノード1は、ビームaで全ての３つの許容のSPタイムスロットを使用しているが、そのビームbで３つの許容のSPタイムスロットのうち２つのみを割り当てられていることを特定する必要がある。
【０１６９】
従って、それは（ビームbで利用可能な）３つのSPタイムスロットのリストをノード2に送信する。このリストは、このビームでの全てのフリー及びDAタイムスロットを有してもよい。要求メッセージが送信されると、タイムスロット及びリンクスケジューリングメッセージのデータ構造に適切な変更が行われる。ノード2は、その８の隣接へのそのリンクについて、ビームa及びbの全ての利用可能SPタイムスロットをSP割り当てされている。
【０１７０】
従って、ビームcは新しいSP割り当てを受け入れることができる唯一のビームである。それがノード1からREQ_SPTS(L=(1,2,3))を受信すると、それは、（SPタイムスロットとして以前に割り当てられたc1及びc2を有する）新しいリンクで動作する唯一のものとしてビーム／タイムスロットc3を選択する。それは応答メッセージでこの選択を送信する。応答メッセージが送信されると、ビーム／タイムスロット及びリンクスケジューリングメッセージのデータ構造に対して適切な変更が行われる。最後に、確認が送信又は受信されたときに、適切なタイムスロットの状態が“リンク(1,2)へのSP割り当て”に変更される。
【０１７１】
【表２２】
2006522547.tif 000032
複数のビームスケジューリングアルゴリズム／プロトコルを実装するために必要な変更点は容易であり、以下のようになる。タイムスロットDB及びリンクスケジューリングメッセージDBの状態の変数としてビームIDを追加する。新しいSPタイムスロットをスケジューリングすることができるか否かを決定する基準として、(7)及び(8)を使用する。ネットワークのパラメータNframe及びNbeamの値を指定する。
【０１７２】
潜在的な隣接に新しいSPタイムスロットを提供するために、アルゴリズムは、最初に隣接の数がNbeam未満のビームを見つけなければならない。このビームは新しい隣接を追加するために使用され得る。ノードがその隣接に送信するREQ_SPTSメッセージは、現在SP割り当てされていないビームについてNbeamの利用可能タイムスロットを指定する。
【０１７３】
REQ_SPTSメッセージを受信すると、ノードは、隣接の数がNbeam未満のそのビームのうち１つを見つけなければならない。このビームは、新しい隣接を追加するために使用され得る。受信REQ_SPTSメッセージのNbeamのタイムスロットのリストと、選択されたビームに現在割り当てられていないNbeamのタイムスロットとを比較して、双方のリストに共通する少なくとも１つのタイムスロットが見つけられ得る。そのタイムスロットは、REPLY_SPTSメッセージで送信されるタイムスロットとして選択され得る。発信ノードがREPLY_SPTSメッセージを受信すると、双方のノードがそのビームと共通のタイムスロット割り当てとを選択している。
【０１７４】
この例は、ビームのそれぞれについて単一の周波数帯域が使用されることを暗に仮定した。この場合、ノードは干渉せずに同じ帯域で同時に通信する複数のビームを有してもよい。この干渉のない動作は、実際にサポートが困難な場合がある。問題の類似の定式化は、各ビームが異なる周波数帯域で動作する（すなわち図１０のビームa、b及びcがそれぞれ異なる周波数帯域を使用する）ことで行われてもよい。スケジューリングアルゴリズムに関しては、SPタイムスロットの割り当てについての同じ制約を適用する。しかし、実際にタイムスロット／ビームの組み合わせを割り当てるときには、２つのノードが同じビーム（同じ帯域を使用することに相当する）及び同じタイムスロットを使用しているような割り当てを見つける必要がある。これは、スケジューリングの観点から異なるそれぞれのビーム／タイムスロットの組み合わせを行うことに相当する。従って、利用可能タイムスロットの数は、ビームの数をフレームの大きさで乗算したものである。この場合、潜在的な隣接にSPタイムスロットを割り当てる制約は、以下で得られる。
【０１７５】
【数９】
2006522547.tif 000033
ここでBはビームの数を示す。この隣接の数の制約は、(7)及び(8)のものよりわずかに限定的である。その理由は、SPタイムスロットを共有するノードが同じビーム／周波数チャネル及び同じタイムスロットを使用しなければならないという制約のためである。例えばNframe=5且つB=3の場合、(9)の制約はノード毎に８の隣接を許可するが、(7)及び(8)の制約はノード毎に９の隣接を許可する。
【０１７６】
図１０の問題の例は、各ビームが異なる周波数帯域で動作するそれぞれ３つのビームを備えた２つのノードを有する（すなわちビームa、b及びcはそれぞれ異なる周波数帯域を使用する）。また、フレームの大きさが5であることを仮定する。双方のノードは隣接ノードに対して7のSPタイムスロットを既に収容しているため、(9)から、SPタイムスロットで更なる隣接をそれぞれ追加することができ、その間のリンクを確立することを許可する。収容されたSPタイムスロットが図面に示されており、SPタイムスロット割り当て及び新しいリンクを確立するために必要なメッセージ交換が表２３に示されている。メッセージ交換は、SPタイムスロットとして以前に割り当てられていない８のビーム／タイムスロットの組み合わせを有する必要があるREQ_SPTS(L=(a4,a5,b3,b4,b5,c3,c4,c5))メッセージをノード2に送信することで、ノード1により起動される。この例では、ノード2は、ノード1により使用されなかった７のビーム／タイムスロットの組み合わせ（REQ_SPTSメッセージで受信した８のビーム／タイムスロットの結合のリストにある）を既に割り当てられている。従って、(9)により、割り当て（c5）に選択され得る少なくとも１つの残りのビーム／タイムスロットの組み合わせが存在しなければならない。図１１及び表２３に示すように、これは、ノード1と2との間のリンクに割り当てられたSPビーム／タイムスロットの組み合わせである。
【０１７７】
【表２３】
2006522547.tif 000034
次に、更に図１２及び図１３を参照すると、２つのモバイルノード12の間に指向性リンクを確立するために適切な時期を決定する特に有利な手法は、まずノード間の無指向性リンクの品質を決定し、この品質値での決定に基づくことである。すなわち、指向性通信リンクのエネルギーは一方向に集中しており、360°に分散していないため、一般的に、指向性の信号は、同じ出力レベルで送信される無指向性の信号より大きい信号強度を有する。このように、ノードが指向性通信リンクを確立する前に、無指向性通信リンクの十分な品質値を有することを要求することにより、指向性通信リンクが同様に所望の品質レベルになるという優れた指標を提供する。
【０１７８】
実際に、無指向性リンク品質は、指向性アンテナを使用するノードの接続されたモバイルアドホックネットワークを維持する主要な問題である。断続的に又は比較的長期に指向性リンク及び無指向性リンクの一方又は双方の損失に導き得る様々なリンク障害が存在する。リンク品質は、双方のリンク形式について継続して測定されることが好ましく、リンク品質の変化に応じる機構が使用されるべきである。これらの測定はリンクレイヤで実行されてもよく、ネットワークレイヤはリンクレイヤの通知を通じてリンク品質を通知される。しかし、特定の実施例で他の構成が使用されてもよい。
【０１７９】
従って、前述のように、指向性リンクを確立する処理は、まず、ブロック121で所定のモバイルノード12の対の間で無指向性リンクを確立することにより、開始する（ブロック120）ことが好ましい。これは、隣接がそのLink_HELLOパケットを受信することにより最初に検出されたときに生じる。本発明のこの態様によれば、リンクスケジューラは、無指向性リンクの品質が十分に高くなるまで、指向性リンクの設定の処理を起動することを許可されない。
【０１８０】
コントローラ18は、以下のように無指向性リンクの品質値を決定する（ブロック122）。例示的なルーチングプロトコルとしてOLSRを使用して、OLSR仕様に一致して、0と1の間の数としての変数N_qualityとして示すリンク品質測定量を定める（1は最高品質を表す）。OLSR仕様で品質を計算する１つの方法に従って、これは、OLSRパケットのパケット受信誤り値の推定として示されてもよい。
【０１８１】
チャネル品質を推定する処理は、チャネル品質の最も正確な可能な推定が得られるように実装されるべきである。１つの可能性は、例えば802.11カードからの信号対雑音の推定を使用することである（それが容易に取得され、特定のノードに割り当てられるタイムスロットに関する場合）。
【０１８２】
信号対雑音比の推定が容易に使用できない場合には、OLSRで使用した手法を使用することができる。そのOLSRで使用した手法は、OLSRパケットの成功した受信から品質を推定する。無指向性リンクでは、Link_HELLOとDirectional  NeighborとChannel  Quality  Feedbackの形式で毎秒数パケットが各隣接から受信される。所定のセットの構成パラメータについて、これらのペットのうち固定数が各隣接ノードから各秒に送信される。このように、毎秒既知の数のこれらのパケットが送信され、受信数が数えられ得る。
【０１８３】
無指向性品質値N_qualityomniLkを計算するアルゴリズムは次のようになる。ノードkからの成功したパケット受信毎に、ノードkからのリンクのN_qualityomniLk値は次のように更新される。
【０１８４】
【数１０】
2006522547.tif 000035
損失したノードkからのパケット送信毎に、ノードkからのリンクのN_qualityomniLk値は次のように更新される。
【０１８５】
【数１１】
2006522547.tif 000036
ノードkからのリンクのN_qualityomniLk値の初期条件は、最初に受信したLink_HELLOの前に0に設定されており、正確に受信したLink_HELLOで(10)に従って更新される。パラメータαの選択は、成功したパケット送信の確率の推定を計算する１次フィルタ（又は指数型重み付き平均）の時定数を有効に設定する。このパラメータの値を適切に設定することは、予期される毎秒のメッセージ数に依存し、所望の反応度と推定の精度との間の折衷になる。当業者にわかるように、より大きいαの値は、受信した新しいサンプル毎のより大きい変化を生じる。これは、リンク状態を不正確に分類するより増加した確率を犠牲にして、リンク状態の変化のより速い認識に導く。
【０１８６】
リンクLkについて、変数Can_AllocLkは、干渉の緩和のため、初期SPタイムスロット割り当て又は何らかの将来のDA割り当て若しくは再割り当てに対して、指向性リンクのタイムスロット割り当てを起動するために好ましくはTRUEになるように設定される。すなわち、ブロック123及び124において、無指向性通信リンクの品質値が第１の品質閾値より大きい（Can_AllocLkがTRUEであることを示す）場合にのみ、リンクスケジューラは隣接モバイルノードと指向性通信リンクを確立する。このように、図示の方法を終了する。指向性通信リンクは、前述のように確立されてもよい。
【０１８７】
当然のことながら、その方法は、指向性リンクが確立された後に、品質値を決定／監視し続けることにより（ブロック131）、任意選択で継続してもよい（ブロック130）。このような場合、変数Can_AllocLkは、N_qualityomniLkが以下の関係に従って決定される毎に変更される。
【０１８８】
【数１２】
2006522547.tif 000037
【０１８９】
【数１３】
2006522547.tif 000038
【０１９０】
【数１４】
2006522547.tif 000039
N_qualityomniLkを推定するときの統計上の変動により生じたリンクフラッピング（link  flapping）を回避するために、ブロック132に示すようにN_qualityomniLkの十分な変化が推定されなければ、Can_AllocLkの変数の変更を妨げるように、ヒステリシス（hysteresis）が(12)-(14)に取り入れられる。第１の閾値TomniH、第２の閾値TomniL及びパラメータαは、この動作を確保するように選択される。閾値の例示的な値は、TomniH=0.2及びTomniL=0.8であるが、他の値が使用されてもよい。当然のことながら、品質値が第２の閾値TomniLより品になると、指向性リンクの使用が一時的に中断されてもよく、又はリンクが必要に応じて中止されてもよい（ブロック133）。このように、図示の方法が終了する（ブロック134）。
【０１９１】
更に以下に説明する手順は、前述のようにゲートとしてCan_AllocLkの変数を使用することを前提としてもよい点に留意すべきである。すなわち、タイムスロットが指向性リンクLkに割り当てられ得る前に、値Can_AllocLk=TRUEを有しなければならない。リンクLkについて最初のLink_HELLOパケットが受信されたときに、変数は最初に値Can_AllocLk=FALSEに設定される。当然のことながら、指向性通信リンクを確立及び／又は継続するために適切なときを決定するために、他の手法が使用されてもよい。
【０１９２】
更に図１４−１６を参照して、要求割り当てのタイムスロットの割り当てについて更に詳細に説明する。DAタイムスロットは、ネットワークトラヒックの変動する要求に応じるように割り当てられることが好ましい。前述のように、変数Can_AllocLkは、最初に指向性通信リンクを確立するのに適切なときを決定するために使用されてもよい。すなわち、新しいDAタイムスロットの割り当ての前提条件として、良好な無指向性チャネル品質が使用されてもよい。従って、リンクLkについて、タイムスロットの要求側又はタイムスロット割り当て要求を受信するノードによる新しいDAタイムスロットの割り当て前に、変数Can_AllocLkはTRUEであるべきである。
【０１９３】
同様に、干渉条件又は他のリンク劣化に応じたDA指向性タイムスロットの再割り当ての前に、変数Can_AllocLkがTRUEになることを必要とすることが望ましいことがある。以下のDAタイムスロットの割り当ての説明は、Can_AllocLkがTRUEであるという条件を仮定するが、このことは全ての実施例に必要ではない。
【０１９４】
本発明のこの態様によれば、１つのノードから隣接ノードへの要求タイムスロットの要求は、半永久的タイムスロットがこれらの２つのノードの間のリンクに割り当てられている場合にのみ、許可される。リンクが少なくとも１つの半永久的タイムスロットを割り当てられた後に、ノードは、更なるタイムスロットの定期的な割り当てを要求してもよい。DAタイムスロットをスケジューリングするために使用されるメッセージは、無指向性リンク又は指向性リンクで送信され得る。
【０１９５】
より具体的には、各コントローラ18は、所定の通信リンクで送信されるデータを格納するデータキュー18fを有することが好ましい。要求割り当てタイムスロットを割り当てる第１の手法（図１４）は、前述のように、ブロック141において、モバイルノード12の対の間で各半永久的タイムスロットをスケジューリングすることで開始する（ブロック140）。ブロック142において、半永久的タイムスロットの間に通信リンクで以前に送信されたデータの品質が、データキューに格納されているデータの量と共に（ブロック143）、決定されてもよい。ブロック144において、通信リンク毎のリンク利用率のメトリックがそれに基づいて決定されてもよい。ブロック145において、要求割り当てのタイムスロットは、リンク利用率のメトリックに基づいてスケジューリングされてもよく（以下に更に説明する）、それにより、ブロック146において図示の方法が終了する。
【０１９６】
特に、各リンクでのトラヒック要件の測定は、DAタイムスロットの効率的な割り当てに特に重要である。前述のように、これは、所定のリンクで送信されているデータの品質と、キュー18fにバックアップされているデータとに基づいて行われることが好ましい。前述に関して、ノードiとkとの間のリンクで送信された測定平均トラヒックは、（エポック毎のタイムスロットの数の単位で）Tikseで示される。この指標は、エポック毎の１つ以上の半永久的タイムスロットと何らかの要求タイムスロットとで送信される全てのトラヒックを有してもよい。
【０１９７】
キュー状態Qikの現在の測定も、ノードiとkとの間のリンクで維持される。大きい値のQikは、１つ以上のDAタイムスロットの迅速な割り当ての要求を示す。要求の時折のバーストは、Qikの増加を生じてもよく、キューの大きさが減少するまでDAの容量の更なるタイムスロットの要求を起動する。
【０１９８】
ノードiとkとの間のリンクに割り当てられるタイムスロットの総数は、Niktotで示される。タイムスロットの要求は次のように定められ得る。
【０１９９】
【数１５】
2006522547.tif 000040
これは、測定トラヒック＋キューの大きさにより示される推定追加容量の関数である。この関数は、如何なる形式をもとることができ、予約容量の新しい要求により影響を受けてもよい。
【０２００】
ある実施例では、リンクメトリックがトラヒック要求の優先度により影響を受けることを可能にすることが、望ましいことがある。すなわち、タイムスロットの間の所定の通信リンクの要求のレベルは、トラヒックの複数の優先クラスについて予期される要求の量に更に分類されてもよい。このことにより、優先トラヒックの要求を満たす更に効率的なタイムスロットの割り当てが可能になる。
【０２０１】
従って、図１５を参照すると、このような手法は、図１４のブロック141に示すステップを参照して説明したことと同様に、SPタイムスロットをスケジューリングすることにより開始してもよい（ブロック151）。ブロック152において、リンク利用率のメトリックは、通信リンク毎の複数のデータ優先レベル又はクラス毎に決定されてもよい。これは、前述の測定（すなわち、以前に送信されたデータの量及び／又はデータキュー18fに格納されているデータの量）の一方又は双方を使用して行われてもよく、他の適切な使用量の測定を使用して行われてもよい。
【０２０２】
一例として、トラヒックが最低から最高への優先度P1,P2,P3,...,Ppの順にpの優先クラスに優先度を付けられる場合、優先クラスPjのタイムスロット要求は、次になる。
【０２０３】
【数１６】
2006522547.tif 000041
優先クラス毎に異なる要求メトリックが計算される。このリンクでのこの優先クラスに必要なタイムスロットの数Tikneed,Pjは、双方向からのメトリックを使用して計算される。
【０２０４】
【数１７】
2006522547.tif 000042
（例えばタイムスロットの約1/4の）バイアス項Bにより最高優先度の要求メトリックTikneed,Ppを増加させ、かなりのキューを回避するように適切な容量が割り当てられることを確保することが望ましいことがある。全ての優先クラスでの総計要求として、総計メトリックが任意選択で決定されてもよい（ブロック153）。すなわち、次になる。
【０２０５】
【数１８】
2006522547.tif 000043
次に、ブロック154において、DAタイムスロットは、それと優先レベルとに基づいてスケジューリングされてもよい。このように、その方法を終了する（ブロック155）。
【０２０６】
容量の要求とリンクに以前に割り当てられたタイムスロットの数との関数である要求メトリックは、このリンクに割り当てられる。これをMikDA(TikPj,Niktot)で示し、全ての優先クラスの推定要求と割り当てられたタイムスロットの数に依存することを示す。この手法は、高優先度のトラヒックの比率が増加すると共に、及びより多くのタイムスロットが必要になると共に、メトリックが増加することを提供する。更に、割り当てられたタイムスロットの数が減少すると、メトリックが低下する。このように、リンクが過度のタイムスロットを有する場合、メトリックは負になる。当然のことながら、当業者にわかるように、様々な用途で他のメトリックが使用されてもよい。
【０２０７】
以下のアルゴリズムは、リンクメトリックを計算するために使用され得る。以下の例では、簡略化のため、最重要である優先クラスP3での３つの優先クラスを仮定する。Tikneed≦Niktotの場合、次を設定する。
【０２０８】
【数１９】
2006522547.tif 000044
その他の場合、Tikneed-Tikneed,P1＜Niktotの場合に次になる。
【０２０９】
【数２０】
2006522547.tif 000045
その他の場合、Tikneed-Tikneed,P1-Tikneed,P2＜Niktotの場合に次になる。
【０２１０】
【数２１】
2006522547.tif 000046
その他の場合、次になる。
【０２１１】
【数２２】
2006522547.tif 000047
前述のアルゴリズムでは、優先クラス毎のメトリックに必要なできるだけ大きい範囲を許容するように、定数パラメータKs≧1が選択される。例えば、Ks=1の場合に、更なるタイムスロットが必要になり、クラスP3のトラヒック要求が存在する場合、総計メトリックは2＜MikDA(TikPj,Niktot)≦3の範囲になる。同様に、最高のトラヒッククラスがP2の場合、総計メトリックは1＜MikDA(TikPj,Niktot)≦2の範囲になる。その他の場合に、最高のトラヒッククラスがP1の場合、総計メトリックは0＜MikDA(TikPj,Niktot)≦1の範囲になる。その範囲は、Ksについてより大きい値を選択することにより、更に拡張され得る。Ks=2の場合、前述の手順を使用して、最低から最高への３つの優先クラスのメトリック範囲は、0〜2と、2〜4と、4〜6である。
【０２１２】
前述のように計算されたメトリックMikDA(TikPj,Niktot)は、リンクが更なるスロット割り当てを必要とするか否か（すなわち、MikDA(TikPj,Niktot)が正であるか否か）、及びどの優先クラスが割り当てを必要とするかを決定する基礎を提供する。それはまた、最高の優先度で最大のスロットの必要性を示す最高のメトリックを備えたリンクに新しいスロットが割り当てられることを可能にする。更に、それはまた、リンクに割り当てられた過度の容量が存在するか否か（すなわち、MikDA(TikPj,Niktot)が負であるか否か）をも示す。
【０２１３】
留意すべき主な点は、前述の手法を使用するときに、リンクメトリックはタイムスロットについての優先の相対要求を示す点である。ゼロより大きい最大のメトリックは、他のリンクより高い優先度のトラヒックについての追加容量の最大の必要性を示す。ゼロより小さいメトリックは、リンクが過度の容量を有することを示す。最小のリンクメトリックは、最大の過度の容量を備えたリンクを示す。このリンクは、必要に応じて他のリンクでの容量を再スケジューリングする最善の候補になる。
【０２１４】
図１６を参照して、隣接ノードへの指向性リンクに要求タイムスロットを割り当てるために各ネットワークノード12で使用され得る例示的な手法について説明する。図１４及び１５の一方又は双方に概説する手法を使用して、ブロック160で始まり、ブロック161において、モバイルノード12は、半永久的タイムスロットを割り当てられたそのリンクのそれぞれについて、リンクメトリックMikDA(TikPj,Niktot)を継続して維持する。
【０２１５】
各ノードは、各隣接ノードへの更なる送信タイムスロットの必要性を示すために、このリンクメトリックを使用する。MikDA(TikPj,Niktot)の最大値は、優先度で並べられた更なるDAタイムスロット割り当てについて最大の必要性を有するリンクを示す。MikDA(TikPj,Niktot)＞2・Ksの値は、最高の優先クラスP3の更なるタイムスロットの必要性を示す。同様に、Ks＜MikDA(TikPj,Niktot)≦2・Ksの場合、更なるタイムスロットが優先クラスP2に供するために必要になる。最後に、0＜MikDA(TikPj,Niktot)≦Ksの場合、更なるタイムスロットが優先クラスP1に供するために必要になる。
【０２１６】
メトリックMikDA(TikPj,Niktot)が維持されると、ブロック162において、ゼロより大きい最大のリンクメトリックを備えたリンクが、更なるタイムスロット割り当ての最初の選択肢として選択されるべきである。フリースロット又は他のリンクへの過度のDA割り当て（同様に小さいメトリックにより示される）若しくは使用中であるが低優先度を有するスロットとして利用可能なタイムスロットが存在する場合、処理はDAスロット追加状態に移行し、DAタイムスロット割り当てを見つける処理が起動される。
【０２１７】
このタイムスロット再割り当て処理に有用な複数の他のメトリックが存在する。ブロック163において、追加容量のリンク利用率のメトリックMikDA(TikPj,Niktot+1)は、更なる追加タイムスロットが追加された後にリンクメトリックがどのように変化するかを推定するために計算されてもよい。これは、第２のタイムスロットが要求されているか否か、及びその要求の優先度が何であるかを決定する場合に有用なことがある。それは、このリンクが第２のタイムスロットを割り当てられているか、又は他のリンクがより大きいメトリックを有している可能性があるかを示してもよい。後者の場合、次のタイムスロット割り当ては、最大のメトリックを備えたそのリンクに対するものになる。
【０２１８】
同様に、ブロック164において、タイムスロットがリンクから取り除かれた場合にリンク利用率のメトリックが何になるかを推定するために、減少容量のリンク利用率のメトリックMikDA(TikPj,Niktot-1)が計算されてもよい。これは、一方のリンクから他方にタイムスロットの再割り当てをする際に有用なことがある。すなわち、ブロック165において、当業者にわかるように、再割り当てに指定された要求割り当てのタイムスロットは、増加及び／又は減少のリンク利用率のメトリックが許容範囲の制限内にある場合に、再割り当てされてもよい。このように、図示の方法を終了する（ブロック166）。
【０２１９】
半永久的タイムスロットと同様に、ノード12は、隣接への指向性リンクに割り当てられるDAタイムスロットの選択を、そのノードと調整しさえすればよい。以下に説明するように、このことは、隣接が指向性リンクでタイムスロット割り当てについてその隣接に要求を送信し、同じリンクで割り当ての許可又は要求の拒否を受信することを意味する。
【０２２０】
リンクメトリックは、所定のスケジュールに従って定期的に再計算されることが好ましい。特定の閾値Max_metric_thresholdより大きいリンクメトリックを有するリンクは、新しいDA容量を取得する候補になる。メトリックは複数のタイムスロットの必要性を示してもよく、その複数のタイムスロットは１つの要求で同時に要求されてもよい。この閾値を超過する最大のメトリックを備えたリンクは、新しいDAタイムスロットを割り当てる際の優先度を有する。しかし、複数のリンクメトリックが閾値Max_metric_thresholdを超過する場合、ノードは複数の隣接ノードから同時にDAタイムスロットを要求してもよい。リンクメトリックの負の値はリンクが過度の容量を有することを示すが、様々な実施例では他の形式のメトリックが使用されてもよい。この容量は、より大きいリンクメトリックを備えた他のリンクの必要性を満たすために放棄されてもよい。
【０２２１】
複数のデータ優先レベルの使用はまた、最高の優先度のデータが最初に送信され得るようにデータを優先する柔軟性を提供する。当然のことながら、所定のリンクは、各指向性エポックに割り当てられた複数のタイムスロット有してもよい。このように、隣接ノードkへの指向性リンクLkは、それに割り当てられたタイムスロットi及びjを有してもよく、これらの２つのタイムスロットは異なるリンク特性を有してもよい。干渉レベルに応じて、タイムスロットの一方は高品質でもよく、他方が低品質でもよい。低品質のタイムスロットで重要なトラヒックを送信することは、一般的には適切ではない。
【０２２２】
所定のタイムスロットの間のリンクサービス品質（QoS）に基づいてデータを優先する１つの有利な手法について、図１７を参照して説明する。ブロック170で開始し、ブロック171において、所定の対のモバイルノード12の間で、複数のタイムスロットがスケジューリングされる。前述のように、この場合にも同様に、これは一般的に１つ以上のSPタイムスロットと、１つ以上のDAタイムスロットとを有する。また、前述のように、各タイムスロットの間に通信リンクに関連する各リンク品質値もまた、ブロック172で例示的に決定される。これは、SIR、パケット受信誤り値等に基づいて行われてもよい。従って、ブロック173において、データは、データの優先レベル及び品質値に基づいてタイムスロットの間で送信されるように優先される。このように、図示の方法を終了する（ブロック174）。
【０２２３】
より具体的には、コントローラ18は、関連する最高の品質値を有するタイムスロットに、優先レベルの最高のものに対応するデータを割り当てることが好ましい。例えば、最高優先レベルはネットワーク制御データに対応してもよい。その理由は、一般的に、この種類のデータは、干渉の軽減、新しいタイムスロットへの損失リンクの再割り当て等のために迅速な配信及び動作を要求するからである。
【０２２４】
更に図１８を参照して、データを優先する例示的な手法について説明する。ブロック180で始まり、送信されるのを待機しているデータは、まずブロック181でデータ優先レベルによりランク付けられ、次にブロック182でデータが受信された順によりランク付けられる。これらの２つのステップからの最高ランクのデータが選択され（ブロック183）、ブロック184において、品質値がそのデータ優先レベルのそれぞれの最小の品質閾値より上である第１の利用可能タイムスロットの間に送信される。この処理は、全てのデータが送信されるまで続き（ブロック185）、ブロック186で図示の方法を終了する。当然のことながら、実際の動作中に前記のステップが頻繁に繰り返されるが、説明の明瞭さのため、ブロック186で終了するものとして例示的に示していることがわかる。
【０２２５】
品質値（すなわちQoS）に基づく優先度が実装される場合には、データキュー18fは、異なるデータ優先レベルのキューとして実際に実装され得る点に留意すべきである。更に、特定のリンクに割り当てられた各タイムスロットのリンク品質を区別することを明らかにするために、ある程度の変更が望ましいことがある。この場合も同様に前記の例を使用して、問題のある品質のタイムスロットでOLSRネットワーク制御トラックを送信することが望ましくないことがある。
【０２２６】
タイムスロットiを介してノードkへのリンクについてノードjで推定される品質指標は、N_qualityiLkで示される。同様に、Channel  Quality  Feedbackパケットで送信されるノードkでのそのタイムスロットの推定品質は、N_quality_RxiLkで示される。次に、これらの２つの推定に基づいて、タイムスロットiの品質は、QualityiLk=Min(N_qualityiLk,N_quality_TxiLk)として推定され得る。
【０２２７】
ネットワーク制御トラヒックが最高優先度を割り当てられた場合、指向性リンクLkに割り当てられたタイムスロットiが近づくと、指向性リンクLkの何らかのキューにあるネットワーク制御トラヒックが、タイムスロットの品質についての特定の条件が満たされていることを仮定して、このタイムスロットの使用時に最初に選択される。
【０２２８】
ネットワーク制御トラヒックのクラスでは、このような条件は以下のようになってもよい。リンクLkの品質がQualityiLk＞TNCを満たす場合（ただし、閾値TNCは、ネットワーク制御トラヒックの十分なリンク品質を保証するように選択される）、ノードkにアドレス指定されるパケットは、第１のタイムスロットiで送信され、指向性リンクLkに割り当てられる。その他の場合、ノードkにアドレス指定されるパケットは、最高のリンク品質QualityiLkを有する指向性リンクLkに割り当てられたタイムスロットで送信されてもよい。
【０２２９】
更に、いくつかのミッションデータトラヒックのクラスについて、同様のタイムスロット品質条件を課すことが望ましいことがある。何らかのミッションデータクラスCmについて、タイムスロット品質条件を以下のように課すことができる。ノードkにアドレス指定されるパケットは、QualityiLk＞TCmを満たす指向性リンクに割り当てられた第１のタイムスロットiの間に送信されてもよい。ただし、閾値TCmは、クラスCmのミッションデータトラヒックの十分なリンク品質を確保するように選択される。その他の場合、ノードkにアドレス指定されるパケットは、最高のリンク品質QualityiLkを有する指向性リンクLkに割り当てられたタイムスロットの間に送信されてもよい。
【０２３０】
当業者にわかるように、前述の手法で、複数のタイムスロットを備えたより長いエポックを各リンクLkへの各エポック内に割り当てさせることに対する利点が存在する。すなわち、１つのタイムスロットが干渉により一時的又は永久的に低品質になる場合に、リンク劣化の可能性がかなり小さくなる。この場合、他の割り当てられたタイムスロットは、より高い品質を有してもよく、重要なトラヒックのためにQoSを維持するのに重要でもよい。単一のタイムスロットがリンクに割り当てられる場合、干渉のため単一の割り当てられたタイムスロットの品質が低下し始めると、新しいタイムスロットの割り当てに遅延が存在することがある。
【０２３１】
リンク品質の検出は、無指向性リンクと同様に指向性リンクで実行されることが好ましい。しかし、スロットが毎回異なるリンク品質を有することがあるため、指向性リンクではこのことは複雑になる。リンク停止を生じる通常の波及効果に加えて、指向性リンクは、同じタイムスロットを再利用する他のノードの対から、干渉による品質劣化を受ける。このように、（複数のタイムスロットが同じ隣接ノードに割り当てられる場合でも）タイムスロット毎のリンク品質は、別々に推定されて格納される必要があってもよい。
【０２３２】
更に、タイムスロット毎に別々に推定されたリンク品質であっても、一般的に、複数のタイムスロットでのリンクの総計リンク品質は、例えばOLSRの場合のように、ルーティングプロトコルに転送される唯一の情報である。この処理は、特定のタイムスロットについてのトラヒック要求の変化及び（形状の変化により生じる）干渉の制約の変化により必要とされ得る、リンクへのタイムスロットの頻繁な再割り当てにより複雑になる。
【０２３３】
リンクレイヤでのこの動作の全ては、実際にはルーティングプロトコルに対してトランスペアレントでもよい。隣接への如何なる所定のリンクについて、ルーティングプロトコルに一般的に報告される唯一の情報は、その隣接へのリンクのリンク品質である。リンク品質の検出、干渉の回避及び緩和、及びそれと新しいタイムスロットを割り当てることの関係をサポートするために、リンクレイヤで使用され得る本発明の様々な特徴について、以下に説明する。
【０２３４】
指向性リンク品質を決定する１つの特に有利な手法について、図１９及び２０を参照して説明する。信号対雑音比の推定が、個々のタイムスロット毎の品質を推定するために容易に使用できない場合、無指向性リンク品質を推定する前述の手法（すなわち、無指向性オーバーヘッドパケットの成功した受信の使用）が使用されてもよい。指向性タイムスロットの場合、トラヒックは主にミッションデータトラヒックである。
【０２３５】
特に、ブロック190で始まり、複数のこのようなデータパケットは、各タイムスロットでソースノードにより送信される。しかし、受信ノードは何個が送信されたかを認識していない。タイムスロットで何個のパケットが送信されたかを受信ノードが認識することを可能にするために、ブロック191において、送信側はまた、データパケットと共に特別のオーバーヘッドパケットPKT_CTをスロットで送信する。オーバーヘッドパケットは、タイムスロットの間の送信パケット数（それ自体を含む）を提供する。このように、PKT_CTパケットが受信された場合に、受信ノードは、合計で何個のパケットがタイムスロットで送信されたかを認識する。タイムスロットで送信された数についてのこの数をniTとして示す。ブロック192において、受信ノードはまた、正確に受信したパケットの数（njRとして示す）を数える。
【０２３６】
タイムスロットiのパケット受信誤り値は、タイムスロットiで受信したパケットに基づいて推定されてもよい。少なくとも１つのパケット（すなわちPKT_CTパケット）が常に送信されるように、ネットワークが構成されることが好ましい。従って、所定のタイムスロットでパケットが全く受信されない場合、タイムスロットiのパケット受信誤り値は0と推定される。ブロック193において、PKT_CTパケットが正確に受信された場合、それはniTの値を提供し、タイムスロットiのパケット受信誤り値はniR/niTで推定される。このように、ブロック196で図示の方法を終了する。
【０２３７】
生じ得る他の場合は、PKT_CTパケットが正確に受信されず、niTの値が未知の場合である。この場合、タイムスロットiについての正確なパケット受信の確率は、正確に受信したパケットにより占有されたタイムスロットの部分（すなわちBiR/TSi）として推定される（ブロック195）。ここで、BiRはタイムスロットの間に正確に受信したバイト数を示し、TSiは、バイトでのタイムスロットの長さを示す。このように、タイムスロットiについてのパケット受信誤り値の推定
（外１）
2006522547.tif 000048
は、以下のように計算される。
【０２３８】
【数２３】
2006522547.tif 000049
その方法は、ブロック200で始まり、ブロック201において、リンクLk割り当てられたタイムスロットi毎に指向性リンク品質値（LQV：link  quality  value）N_qualityiLkを決定／更新するためにパケット受信誤り値を使用することを任意選択で有してもよい。これらの値は、エポックにつき１回、エポックのスロット毎に更新される。各タイムスロットの後に、タイムスロットiに割り当てられた指向性リンクのN_qualityiLkの値は次のように更新される。
【０２３９】
【数２４】
2006522547.tif 000050
ノードkからのリンクについてのN_qualityiLkの値の初期条件は、最初に受信したタイムスロットの前でタイムスロットがこのリンクに割り当てられた後に1に設定される。これは、その後の各エポックで、そのエポックのタイムスロットiの後に(24)に従って更新される。
【０２４０】
パラメータβの選択は、成功のパケット送信の確率を推定する１次フィルタの指向性リンクのエポックの長さに対して時定数に効果的に設定される。パラメータβの適切な設定は、所望の反応度と推定の精度との間の折衷になる。βのより大きな値は、エポックの間のより大きい潜在的変化を生じる。これは、不正確にリンク状態を分類する更なる確率を犠牲にして、リンク状態のリンク状態の変化のより速い認識に導く。
【０２４１】
１つの問題は、リンク状態の変化が生じると決定されるまでにどのくらいの時間（エポック数）が経過することを許容されるかである。一定期間の後に、タイムスロットiが非常に悪化した場合、N_qualityiLk≒0になる。同様に、タイムスロットiが非常に良好な場合、N_qualityiLk≒1になる。問題は、良好と悪化との間の推移を判断することと、タイムスロットが再割り当てされなければならないといつ宣言するかにある。
【０２４２】
この決定を行う１つの特に有利な手法は、ヒステリシスを使用することである。本発明のこの態様によれば、一般的に言えば、ブロック201において、宛先ノードはパケット受信誤り値に基づいて通信リンクに関連するリンク品質値N_qualityiLkを決定する。リンク品質値N_qualityiLkが第１の閾値より下になった場合、ブロック203において、ソースノード及び宛先ノードは、タイムスロットの間に通信リンクの使用を中止する。
【０２４３】
更に、ブロック204において、リンク品質値N_qualityiLkが所定の持続時間の間に第１の閾値（他の実施例では他の閾値が使用されてもよい）より下に留まる場合、ソースノード及び宛先ノードは、ブロック205において、その間の無線通信リンクを確立するために新しいタイムスロットを確立してもよい。このように、図示の方法を終了する（ブロック206）。他方、ブロック207において、リンク品質値N_qualityiLkが以前に第１の閾値より下になっており、リンクの使用が既に中止されている場合、ブロック208及び209において、リンク品質値が第１の閾値より大きい第２の閾値より上まで増加した場合には、ソースノード及び宛先ノードはタイムスロットの間に通信リンクを使用することを継続する。
【０２４４】
一例として、タイムスロットiでのノードkからのリンクのN_qualityiLkが0〜1の範囲を有する場合、この例では、特定のネットワーク制御機能についてヒステリシスで３つのレベルにそれを量子化する。変数TS_QualiLkはN_qualityiLkの変数の量子化値を表す。新しい変数は、３つの潜在的なリンク品質状態を表すGOOD、MID及びBADの値を取ることができる。TS_QualiLkは、N_qualityiLkが以下に従って変更される毎に、変更される。
【０２４５】
【数２５】
2006522547.tif 000051
TS_QualiLk=GOODでありTQM≦N_qualityiLk≦TQHである場合、次を設定する。
【０２４６】
【数２６】
2006522547.tif 000052
TS_QualiLk=GOODでありTQL≦N_qualityiLk≦TQMである場合、次を設定する。
【０２４７】
【数２７】
2006522547.tif 000053
TS_QualiLk=MIDでありTQL≦N_qualityiLk≦TQHである場合、次を設定する。
【０２４８】
【数２８】
2006522547.tif 000054
TS_QualiLk=BADでありTQM≦N_qualityiLk≦TQHである場合、次を設定する。
【０２４９】
【数２９】
2006522547.tif 000055
TS_QualiLk=BADでありTQL≦N_qualityiLk≦TQMである場合、次を設定する。
【０２５０】
【数３０】
2006522547.tif 000056
【０２５１】
【数３１】
2006522547.tif 000057
当業者にわかるように、推定のタイムスロット状態における過度の変動を回避するために、前記の関係(25)〜(31)にヒステリシスが取り入れられる。閾値の例示的な値は、TQL=0.2  TQM=0.5、TQH=0.8であるが、所定の用途に応じて、他の値が使用されてもよい。ここで使用される例示的な品質範囲は便宜上で0から１までであるが、他の範囲も使用され得る点に留意すべきである。特定のタイムスロットでTS_QualiL=BADである場合、MID又はGOODの品質でのそのリンクで利用可能な他のタイムスロットが存在しない限り、スケジューラは、そのタイムスロットの間にリンクでトラヒックを送信しないことが好ましい。
【０２５２】
また、前述の指数型重み付き平均の使用は、無指向性及び指向性リンクの双方のリンク品質を測定するのに適している点にも留意すべきである。これらのリンクのいずれかの損失に導き得る様々なリンク障害が存在する。リンク品質は、双方のリンク形式について継続して測定されることが好ましく、リンク品質の変化に反応する機構も使用されるべきである。
【０２５３】
当業者にわかるように、様々な現象がリンク品質に影響を及ぼしてもよい。例えば、２つのノードの間の距離は、見通し線（LOS：line  of  sight）が失われるほど大きくなってもよい。この場合、いつか将来にノードが近い距離になるまで、リンクが失われる。ノードが障害物の背後に移動し、長期間はっきりしないままになった場合に、同じ結果が認められる。このような場合、無指向性リンク及び指向性リンクの双方は、非常に低い品質を有する。これは、半永久的タイムスロットの除去及び／又はOLSRルーティングでのリンクの除去を起動することが好ましい。
【０２５４】
その他の現象は、リンクが良好な品質と悪化した品質との間を迅速に振動し得ることである（“フラッピング”としても知られている）。これは、例えば、ノードが小さい障害物を迅速に移動するときに生じ得る。この場合、無指向性リンク及び指向性のリンクの双方がフラッピングする。これはまた、リンク品質が小さすぎるサンプルの大きさを使用して推定された場合にも、潜在的に生じ得る。この場合には、いくらか注意深く対処される必要がある。この状況が持続する間は、リンクが悪化しすぎて、トラヒックをルーティングすることができないことがある。しかし、高品質のリンクが回復され得るか否かを決定するために、タイムスロット割り当ては一定期間保持されてもよい。
【０２５５】
更に、特定のタイムスロットの指向性リンクが低品質である一方で、無指向性リンクは高品質でもよい。この指向性リンクでの他のノードとの通信はまた、割り当てられた他のタイムスロットで良好な品質でもよい。このことは、悪化した品質の単一の指向性タイムスロットで動作する他のユーザからの特定の干渉が存在することを示す。この場合、タイムスロットは、干渉を除去するために再スケジューリングされるべきである。他のタイムスロットが利用可能である場合、又はトラヒックがバッファされる間に新しいタイムスロット割り当てが迅速に取得され得る場合、ルーティングが依然として生じてもよい。
【０２５６】
前述の現象に応じて、複数の種類の動作が可能になる。例えば、リンクレイヤでは、隣接ノードが単一ホップでもはや到達不可能であることが決定されてもよい。この場合には、新しい状態を反映するために隣接テーブルが更新され、如何なる指向性タイムスロットも割り当て解除され、“フリー”としてマークされる。隣接が範囲内にある一方で、過度の干渉によりタイムスロットが悪化していると宣言されると、リンクスケジューリングプロトコルは、干渉のない新しいタイムスロットを割り当てようとする。
【０２５７】
ルーティングレイヤでは、ルーティングプロトコルは、接続性に影響を及ぼさない限り、リンクレイヤでのこれらのアクションのうちいくつかを通知される必要はない。２つのノードの間のタイムスロットが再スケジューリングされたが、２つのノードが依然として接続されてミッションデータを交換可能である場合、そのリンクを通じたルートは依然として良好である。隣接ノードがもはや到達不可能である場合、ルーティングプロトコルは、このリンクを利用しない新しいルートを見つけるべきである。
【０２５８】
次に干渉の問題を検討すると、干渉は、タイムスロットの再利用が目的の如何なるスケジューリングアルゴリズムにもあり得ることが当業者にわかる。一般的に言えば、所定のタイムスロットにおいて他のユーザからの潜在的な及び実際の干渉を低減する２つの方策が、本発明に従って提供される。干渉回避方策は、初期タイムスロットスケジューリング及び何らかの先取りの干渉回避再スケジューリングで使用される。干渉緩和方策は、回避方策が実際の干渉を妨げるために適切に動作しない場合に使用される。干渉緩和方策は、タイムスロットを再スケジューリングして干渉を除去するように動作する。
【０２５９】
例示的な干渉回避シナリオが、図２１に示されている。このシナリオでは、隣接モバイルノードnへの送信用のタイムスロットをスケジューリングする前に、ノードmは潜在的な干渉を評価している。前述のように、この評価は、ノードnからノードmへの要求により促され、その間の初期／追加タイムスロットを確立してもよい。ノードmは、Directional  Neighborパケットを介して受信した情報についてそのテーブル調べ、その隣接パケットのどれが同じタイムスロットで送信をスケジューリングしたかを決定することができる。図示の例では、ノードk及びjが、同じタイムスロットを使用して潜在的に干渉するノードである（空白の円で図示する）。
【０２６０】
より具体的には、ノードmでのノードkからの干渉は、例示的に距離dkmを横断し、ノードmがノードnを示す際に使用するアンテナセクタのボアサイト（boresight）（矢印210で示す）からの角度θmkで受信される。更に、潜在的な干渉信号は、ノードjに送信するときに、ノードkのアンテナのボアサイト（矢印211で示す）からの角度θkmでノードmに対して送信される。
【０２６１】
ノードｎに送信するために、ノードmにこのタイムスロットをスケジューリングするのを回避させるのに結果の干渉が十分な強度であるか否かということは、複数の要因に基づいて決定されてもよい。次に図２２に進むと、１つの手法は、ブロック222において、隣接モバイルノードnと、タイムスロットの間に送信する他の潜在的に干渉するモバイルノードと（ここではノードj及びk）の相対位置を決定することで始まる（ブロック220）。
【０２６２】
次に、ブロック222において、ノードmとnとの間の指向性通信リンクへの潜在的な干渉は、これらの相対位置に基づいて決定される。これを行う１つの手法は、以下に更に説明するように、モバイルノードm及び潜在的に干渉するモバイルノードk、jへの相対位置及び角度に基づいて位置を計算することである。次に、ブロック224において、干渉が閾値より小さい場合にのみ、指向性通信リンクはタイムスロットの間にスケジューリングされる。このように、図示の方法を終了する（ブロック225）
ノードの相対位置に加えて、潜在的干渉は、ノードmで使用される抑制アルゴリズム又はフィルタによってアンテナのサイドローブで実現され得る抑制に基づいて更に決定され得る。すなわち、干渉信号は、距離dkmのパス損失と、ノードm及びkでのアンテナのサイドローブとにより様々の程度に抑制されてもよい。これは、潜在的に干渉するノード毎に計算されるメトリックMk,TiIにより測定されてもよい。このメトリックは、タイムスロットTiでノードkから受信した干渉レベル(dB単位)を表す。
【０２６３】
HELLO及びDirectional  Neighbor更新パケットで隣接ノードから受信した情報により、ノードまでの距離と、各タイムスロットで送信用に使用されるビームのボアサイト方向との計算が可能になる。この例では、全てのノードは、関数Ga(θ)で得られるボアサイトからの角度の関数としてのアンテナ利得パターンを有する。所定の環境での正確な伝搬損失がわからない可能性がある場合、dnpの逆関数として損失が推定され得る。ここで、dは干渉ノードkから関心のノードまでの距離であり、npは一般的に2〜4の範囲の一定の伝搬損失指数である。
【０２６４】
例示的なモデルとして、パス減衰は、平面大地減衰の式及び自由空間減衰の式で得られるパス減衰の最大値として計算されてもよい。平面大地の式では、減衰は次になる。
【０２６５】
【数３２】
2006522547.tif 000058
ここで、パスの長さdkm（ノードkからノードmまでの距離）及び、送信機及び受信機のそれぞれの高度ht、hzは全てメートル単位である。自由空間減衰の式は、次のパス減衰を与える。
【０２６６】
【数３３】
2006522547.tif 000059
ここでRF周波数fはGHz単位である。全推定パス損失は、２つの最大値であり、すなわち、次になる。
【０２６７】
【数３４】
2006522547.tif 000060
当業者にわかるように、実際の損失は時間変化し、障害物又は枝葉（foliage）のため、この計算からかなり異なることがある。しかし、この一定の値は、潜在的な干渉物の影響を評価する際の合理的な近似として使用され得る。次に、タイムスロットTiの間にノードkから送信される信号について、潜在的に干渉するノードkからのパスでのノードmの受信アンテナの信号損失に基づく理論上のメトリックは、次のように計算される。
【０２６８】
【数３５】
2006522547.tif 000061
ここで、θkmは、ノードmへの信号方向のノードkのボアサイトからの角度である。このメトリックは、タイムスロットTiをその他の隣接ノードに割り当てるために、干渉の影響を計算するためにノードmで使用され得る。
【０２６９】
前述のメトリックは、ノードmでの干渉信号のサイドローブの抑制の影響を組み込んでいない。その理由は、これは、どの隣接ノードがタイムスロットTiの間にスケジューリングされるように考慮されているかに依存するからである。しかし、このタイムスロットについて何らかの隣接ノード（例えばノードn）を検討すると、ノードmでのサイドローブの抑制を含む新しいメトリックがMk,TiIが以下のように計算され得る。
【０２７０】
【数３６】
2006522547.tif 000062
次に、ノードmで受信したタイムスロットTiにおいて通信するノードの対k、jの間のリンクLからの干渉の最大干渉レベルは、ノードk又はノードjから受信した最大レベルにより与えられる。すなわち、次になる。
【０２７１】
【数３７】
2006522547.tif 000063
従って、タイムスロットTiにおいてノードmで受信した合計の干渉は、タイムスロットTiで動作する全ての干渉の合計になる。すなわち、次になる。
【０２７２】
【数３８】
2006522547.tif 000064
ほとんどの場合、この品質の近似値で十分である。何らかのタイムスロットでのわずかな潜在的干渉では、２つ以上の干渉がほぼ等しい出力を有する可能性が小さい。この場合には、干渉の近似値を次のように計算することができる。
【０２７３】
【数３９】
2006522547.tif 000065
次に、実際の信号対干渉は、干渉ノードへの距離に対する所望の目的ノードへの距離の比に強く依存するため、タイムスロットTiの理論上SIRメトリックを次のように計算することができる。
【０２７４】
【数４０】
2006522547.tif 000066
前述のメトリックはdB単位であり、何らかの隣接ノードについてタイムスロットをはじめにスケジューリングする際の干渉回避を提供するために使用され得る。更に、有利には、それは、現在スケジューリングされているタイムスロットが更なるレベルの干渉を受け始めているか否か、又は受ける可能性があるか否かを決定するために、断続的な検査で使用され得る。この手法が図２３に示されており、ブロック231において、隣接モバイルノードnと他の潜在的に干渉するノードとの相対位置を断続的に決定することで開始する（ブロック230）。ノードがモバイルであるため、潜在的に干渉するノードがその間に変更していることがある点に留意すべきである。すなわち、ノードj及びkは依然として潜在的に干渉するノードでもよく、そうでなくてもよい。また、他の潜在的に干渉するノードがその間にノードmの範囲内に入ってもよい。
【０２７５】
いずれにしても、新しい潜在的に干渉するノードへの新しい相対位置が決定されると、ブロック232において、前述のように、指向性通信リンクへの潜在的干渉はそれに基づいて決定される。ブロック233において、潜在的干渉が前記の干渉閾値より上である場合には、ブロック234において、指向性通信リンクが新しいタイムスロットの間にスケジューリングされる。このようにして、図示の方法を終了する（ブロック235）。当然のことながら、前述のようにヒステリシスを取り入れることのように、異なる閾値が使用されてもよい。
【０２７６】
前述の干渉の式は、タイムスロットの適切な割り当てを決定する際に検討されるのが好ましいタイムスロット優先の有用なモデルを提供する。当然のことながら、干渉が決定される毎に前記のメトリックのそれぞれを実際に計算することは、かなりの処理リソースを必要とすることがある。従って、当業者にわかるように、入出力値又は比の範囲のセットを予め計算し、SIRを計算するためにそれらをコントローラ18の参照テーブル18gに格納することが有利なことがある。
【０２７７】
更に図２４を参照して、SP及びDAタイムスロットの再割り当てについて、更に詳細に説明する。まず、ノードmとその隣接ノードnとの間で新しいSP又はDAタイムスロットを初めにスケジューリングすることを検討する（図２１参照）。初期事項として、新しいSPタイムスロットを割り当てるときに、何らかの“フリー”タイムスロット又はDAタイムスロットが、DAタイムスロットより高い優先度の“フリー”タイムスロットでの割り当てに利用可能であることを仮定する。DAタイムスロットはまた、再割り当ての最高優先度としての要求メトリックの最小値で順序付けられることが好ましい。前述のように、所定量より大きい要求メトリックでの既存のタイムスロット割り当てが再割り当てに利用可能でないことを除いて、新しいDAタイムスロットを割り当てるときに、同様に処理が続く。
【０２７８】
前述のように、初期スケジューリング処理は、優先メトリックとして、推定干渉レベルと優先トラヒック要求メトリックとを考慮することにより、補われてもよい。このように、潜在的タイムスロットをランク付けする処理は、これらの２つのメトリックで更に複雑になる。
【０２７９】
一般的に言えば、前述のように、タイムスロットの再割り当ては、ブロック241において、初期タイムスロットの確立に続いて始まってもよい（ブロック240）。この例によれば、起動側モバイルノードnは、ブロック242において、その隣接モバイルノードと共有する利用可能タイムスロットを特定し、ブロック243において、起動側モバイルノードと隣接モバイルノードとによるタイムスロットの間のリンク利用率に基づいて利用可能タイムスロットをランク付ける。次に、ブロック244において、起動側モバイルノードnは、利用可能タイムスロットとそのランクとを含むタイムスロット再割り当て要求を受信側モバイルノードmに送信する。
【０２８０】
従って、ブロック245において、受信側モバイルノードmは、次にタイムスロット再割り当て要求を受信し、受信側モバイルノードと受信側モバイルノードに隣接するモバイルノードとによる利用可能タイムスロットの間のリンク利用率に基づいて、利用可能タイムスロットをランク付けする。更に、ブロック246において、ノードmは、起動側モバイルノードと受信側モバイルノードとによるそのランク付けに基づいて、利用可能タイムスロットの結合のランクを生成する。受信側モバイルノードmは、ブロック247において、結合のランクに基づいて起動側モバイルノードと受信側モバイルノードとの間の通信リンクを確立するために、１つ以上の利用可能タイムスロットを再割り当てしてもよい。このように、図示の方法がブロック248で終了する。
【０２８１】
更に図２５を参照して、有利には、前記の再割り当て方法はまた、特定の実施例で様々な他の特徴を有してもよい。ブロック250で始まり、起動側モバイルノードn及び受信側モバイルノードmは、前述のように、ブロック251において、各利用可能タイムスロットに関連するトラヒック要求メトリックをそれぞれ決定し、ブロック252及び253において、高利用率の閾値より大きいそれに関連するトラヒック要求メトリックを有する何らかの利用可能タイムスロットの再割り当てについて、検討から除去してもよい。
【０２８２】
同様に、起動側モバイルノードn及び受信側モバイルノードmは、ブロック254において、各利用可能タイムスロットに関連するSIR値をそれぞれ決定し、ブロック255及び253において、高SIR閾値より大きいそれに関連するSIR値を有する何らかの利用可能タイムスロットの再割り当てについて、検討から除去してもよい。起動側モバイルノードn及び受信側モバイルノードmはまた、タイムスロットのランク付けにおいてSIR値を使用してもよい点に留意すべきである（図２４のブロック243、245）。
【０２８３】
これらのランク付けはまた、前述のように、増加及び／又は減少するリンク利用率のメトリックを考慮してもよい。更に、前述のように、起動側モバイルノードn及び受信側モバイルノードmは、送信されるデータの平均品質及び／又はそれらのキュー18fに格納されているデータ量に基づいて、利用可能タイムスロットをそれぞれランク付けてもよい。
【０２８４】
更に、起動側モバイルノードn及び受信側モバイルノードmは、複数の優先レベルを有するデータを送信することが好ましいため、ブロック256及び253において、受信側モバイルノードmは、利用可能タイムスロットの間に送信されるデータが利用可能タイムスロットの間に現在送信されているデータ以上の優先レベルを有さない場合には、利用可能タイムスロットの再割り当てを抑止してもよい。その他の場合には、前述のようにリンクが再割り当てされてもよく（ブロック257）、このようにブロック258で図示の方法を終了する。
【０２８５】
より具体的に、タイムスロットの前述のランク付けを実行する例示的なアルゴリズムについて、次に提示する。しかし、前記のブロック256を参照して示したように、ノードmとnとの間のリンクに再割り当てされ得る潜在的タイムスロットをランク付けするアルゴリズムを提供する前に、より高い優先度のトラヒックを運ぶ必要がない限り、他のリンクからノードmとｎとの間のリンクにタイムスロットが再割り当てされないことを確保するために、まず、項目MetLimmnを定義する。この場合も、３つの優先クラスでの例を仮定すると、MetLimnmは次のように定められる。
【０２８６】
【数４１】
2006522547.tif 000067
【０２８７】
【数４２】
2006522547.tif 000068
【０２８８】
【数４３】
2006522547.tif 000069
全体の手法を示すために、まず、干渉メトリックが考慮されないときにタイムスロットをランク付ける手法について検討する。以下のタイムスロット優先手法に従って、ノードmとnとの間のリンクに割り当てられていない他の全てのタイムスロット（すなわち、ノードmとその隣接ノードrのうち１つとの間に割り当てられたもの、図示せず）をランク付けることで始める。そのタイムスロット優先手法は、新しいタイムスロットを割り当てる際にトラヒック要求の優先度を考慮するが、干渉の影響を含まない。
【０２８９】
特に、ノードmとnとの間に新しいタイムスロットが割り当てられる必要があるとき、利用可能タイムスロットのリストは、フリー及びDAタイムスロットから作られる。これらのタイムスロットは、受信側ノードmに潜在的タイムスロットのリストを送信する前に、要求側又は起動側ノードnでランク付けられる。利用可能タイムスロットは、優先トラヒック要求メトリックMmrDA(TmrPj,(Nmrtot-1))を使用してランク付けられる。このメトリックでの(Nmrtot-1)の使用は、タイムスロットがノードmとrとの間のリンクから取り除かれた場合のメトリックの値を示す点に留意すべきである。
【０２９０】
以下の手法は、この順序について推奨される。最高ランクのタイムスロットは、フリーのタイムスロットである。残りのタイムスロットは、トラヒック要求メトリックMmrDA(TmrPj,(Nmrtot-1))の逆順にランク付けられる。割り当てられる新しいタイムスロットがDAタイムスロットである場合、優先トラヒック以上を運ぶ全てのタイムスロットが除去される。すなわち、次になる。
【０２９１】
【数４４】
2006522547.tif 000070
これは、低優先度のトラヒックのみが再割り当て処理で失われることを確保する。
【０２９２】
前述のように、（前記の基準による）タイムスロットのランク付けリストは、要求側ノードnにより送信されるREQメッセージに含まれる。受信側ノードmは、REQメッセージを受信し、ランク付きのタイムスロットのリストを受け取り、優先トラヒック要求を使用して前述した方法に従ってこれらのタイムスロットをランク付ける。次に、残りのタイムスロットは、２つのノードにより決定されたランクから結合のランクを与えられ、前述のように、最善の結合のランクを有するタイムスロットが選択される。
【０２９３】
メトリックMmrDA(TmrPj,(Nmrtot+1))＞0である場合、これは、第１のタイムスロットを割り当てた後であっても、他のタイムスロットが必要であることを意味する。このメトリックは、他の隣接へのリンクのメトリックと比較され、第２のタイムスロットが要求されているか否か、又は他のリンクが更なるタイムスロットの更に緊急な必要性を有しているか否かを検査することができる。後者の場合、次のタイムスロット割り当ては、最大のメトリックを備えたリンクに与えられることが好ましい。
【０２９４】
有利には、前述の手法はまた、ある実施例において、前述のトラヒック優先度を検討するように拡張されてもよい。以下の手法は、干渉を有するランク付けの潜在的タイムスロットについて推奨される。受信側干渉レベルMn,TiIは、隣接ノード毎及びタイムスロット毎に維持される。これらのレベルは、定期的に（例えば新しい位置更新で約毎秒１回）更新されることが好ましい。
【０２９５】
ノードmとnとの間に新しいタイムスロットが割り当てられる必要がある場合、利用可能タイムスロットのリストは、フリー及びDAタイムスロットから作られる。これらのタイムスロットは、受信側ノードmに潜在的タイムスロットのリストを送信する前に、要求側ノードnでランク付け又は優先される。従って、タイムスロットをランク付けするために、全体の受信干渉出力が、隣接毎のアンテナ抑制を受信した後に評価されてもよい。当業者にわかるように、受信した全体の推定干渉出力NTimnが計算され得る。
【０２９６】
隣接ノードに割り当てられる利用可能タイムスロットは、優先トラヒック要求MmrDA(TmrPj,(Nmrtot-1))と干渉メトリックNTimnとを使用してランク付けられてもよい。このメトリックでの(Nmrtot-1)の使用は、タイムスロットがノードmとrとの間のリンクから取り除かれた場合のメトリックの値を示す点に留意すべきである。このランク付けについて、最高ランクのタイムスロットは、所定の閾値未満の優先トラヒック要求メトリックMmrDA(TmrPj,(Nmrtot-1))≦TDALを有するフリー又はDAタイムスロットのタイムスロットであることが好ましい。換言すると、これらは、使用されていない（フリーである）タイムスロット又はほとんど決して使用されないタイムスロットである。これらのタイムスロットは、NTimnの最低値が最高ランクに割り当てられて、推定干渉出力NTimnのレベルに従ってランク付けされる。
【０２９７】
ランク順の次のタイムスロットは、最高の閾値未満の優先トラヒック要求メトリックMmrDA(TmrPj,(Nmrtot-1))≦TDAHを有し、同時に閾値を超過することSIRmnTi＞TSIRHで示されるタイムスロットの非常に高いSIRmnTiを有する残りのDAタイムスロットである。これらのタイムスロットは、最高ランクを示す最小の要求メトリックを備えた優先トラヒック要求メトリックに従ってランク付けられる。これらのタイムスロットは、以前に計算されたものより小さくランク付けられる。
【０２９８】
MmrDA(TmrPj,(Nmrtot-1))≦TDAHを満たすが、SIRmnTi＞TSIRHを満たさない残りのDAタイムスロットは、SIRmnTiの最高値に従ってランク付けられる。これらのタイムスロットは、以前に計算されたものより小さくランク付けられる。更に、残りのDAタイムスロットは、以前に計算されたものより小さくランク付けられる。これらのタイムスロットは、最高ランクを示す最小の優先トラヒック要求メトリックに従ってランク付けられる。当然のことながら、前記のランク付け手法は例示的であり、他の手法が本発明の範囲内で使用され得ることがわかる。
【０２９９】
以前の優先ランクの何らかのタイムスロットは、タイムスロットの予想信号対干渉比が次の場合には、再割り当ての検討から除去されることが好ましい。
【０３００】
【数４５】
2006522547.tif 000071
これは、干渉ノードがSIRを小さくし過ぎる何らかのタイムスロットを検討から除去する。更に、割り当てられる新しいタイムスロットがDAタイムスロットである場合、優先トラヒック以上を運ぶ全てのタイムスロットが除去されることが好ましい。すなわち、次になる。
【０３０１】
【数４６】
2006522547.tif 000072
これは、低優先度のトラヒックのみが再割り当て処理で失われることを確保する。
【０３０２】
前述のように、（前記の基準による）タイムスロットのランク付けリストは、要求側ノードにより送信されるREQメッセージに含まれる。REQメッセージを受信する受信側ノードmは、ランク付きのタイムスロットのリストを受け取り、それを計算する要求及び干渉メトリックを使用して前述した同じ方法に従ってこれらのタイムスロットをランク付ける。これは、SIRと干渉ノード距離と干渉ノード角度とが不足した何らかのタイムスロット、又は受信側ノードで利用可能でない何らかのタイムスロットを除去することを有することが好ましい。次に、残りのタイムスロットは、２つのノードにより決定されたランクから結合のランクを与えられ、前述のように、最善の結合のランクを有するタイムスロットが選択される。
【０３０３】
メトリックMmrDA(TmrPj,(Nmrtot+1))＞0である場合、これは、第１のタイムスロットを割り当てた後であっても、他のタイムスロットが必要であることを意味する。このメトリックは、他の隣接へのリンクのメトリックと比較され、第２のタイムスロットが要求されているか否か、又は他のリンクが更なるタイムスロットの更に緊急な必要性を有しているか否かを検査することができる。後者の場合、次のタイムスロット割り当ては、最大のメトリックを備えたリンクに与えられることが好ましい。
【０３０４】
タイムスロットが割り当てられた後に、干渉回避及び緩和手法の一部として、それが継続して監視される。更に、無指向性リンク品質が継続して測定される。無指向性リンクの品質が悪化すると（LOSの損失又は他のノードへの長すぎる距離を示す）、リンクがダウンと宣言され、ルーティングアルゴリズム（例えばOLSR）がリンクの損失を通知される。これは、ネットワークレイヤでの再ルーティングを起動する。無指向性リンクが依然として良好である限り、個々のタイムスロットは干渉について依然として監視されなければならない。
【０３０５】
以下の説明は、無指向性リンクが良好な品質である場合に、指向性タイムスロットの潜在的又は既存の干渉がどのように評価されるかについて示す。所定の隣接ノードへの無指向性リンクが良好であるが、そのノードに割り当てられた指向性タイムスロットのうち１つが非常に信頼のないことを、リンク品質インジケータが示す状況が存在する。これは、前述の干渉回避技術で回避できなかったそのタイムスロットでの過度の干渉を示す。
【０３０６】
一般的に移動により起動されるこのような干渉を生じ得る複数の状況が存在する。これらには、例えば、所望の信号の到達方向の迅速な変化や、干渉信号の到達方向の迅速な変化や、ノードとその目的ノードとの間の距離の変化や、干渉ノードが含まれる。
【０３０７】
本発明による干渉監視／緩和手法の概要について、図２６を参照して説明する。ブロック260で始まり、前述のように、１つ以上のタイムスロットの間にモバイルノードm及びnの対の間に通信リンクが確立された後に（ブロック261）、ブロック262において、少なくとも１つのノードは、タイムスロットの間に通信リンクに関連するリンク品質値を決定する。このノードは、ブロック263及び264において、通信リンクが第１の品質（下限）でるか第２の品質（悪化）であるかを決定する。
【０３０８】
本発明によれば、通信リンクが所定のタイムスロットの間に下限の品質である場合に、ブロック265において、モバイルノードは、第１の期間内に新しいタイムスロットに通信リンクを再割り当てするように協働する。更に、通信リンクが所定のタイムスロットの間に悪化した品質である場合、ブロック266において、ノードは第１の期間より短い第２の期間内に新しいタイムスロットに通信リンクを再割り当てするように協働する。すなわち、リンク品質がかなり劣化した場合、タイムスロットは、通信への混乱を最小化するために、比較的迅速に（すなわち、第２の短い期間内に）割り当てられてもよい。他方、リンク品質が下限であるが、まだ使用可能である場合、タイムスロットの再割り当てはより長く（すなわち、第１の期間内に）遅らせてもよく、タイムスロットを同時に再割り当てしようとする競合するノードの対の間の衝突を低減してもよい。
【０３０９】
そのステップは、ブロック262-264に一般的に示されており、図２７に更に詳細に示されている。特に、前述のように、ブロック271において、リンク品質値はSIRとパケット受信誤り値（PREV：packet  reception  error  value）とに基づいて決定されることが好ましい。更に以下に説明するように、ブロック272及び274において、SIRが第１のSIR閾値と第２のSIR閾値（第１の品質閾値より大きい）との間であり、PREVが第１の誤り閾値と第２の誤り閾値（第１の誤り閾値より大きい）の場合には、通信リンクは下限の品質であると決定されることが好ましい。このように、この方法の態様を終了する（ブロック278）。
【０３１０】
同様に、ブロック274及び273において、SIRが第１のSIR閾値未満でありPREVが第２の閾値より大きい場合には、通信リンクは下限の品質であると決定されることが好ましい。更に、ブロック275及び276において、SIRが第１のSIRの閾値未満でありPREVが第１の誤り閾値と第２の誤り閾値との間である場合には、通信リンクが悪化した品質であると決定される。また、品質要因が第１の誤り閾値より下である場合には、通信リンクは悪化した品質であると決定される。
【０３１１】
前述の手法は、要求割り当てタイムスロットに特に適している。半永久的タイムスロットでは、何らかの用途で、比較的迅速にこれらのタイムスロットを再割り当てすることが適切なことがある。従って、次に図２８を参照すると、ブロック280で始まり、ブロック281においてSPタイムスロットの初期の確立の後に、DAタイムスロットについて前述したことと同様に、ブロック282において、半永久的タイムスロットの間に通信リンクに関連する半永久的リンク品質値が決定される。ブロック283において、更なる通信リンクが半永久的リンク品質値に基づいて半永久的タイムスロットの間に下限の品質又は悪化した品質であると決定されると、ブロック284において、リンクが比較的短い第２の期間内に新しいSPタイムスロットに再割り当てされる。その他の場合には、図示のように、リンク品質値が継続して監視される。
【０３１２】
前述の干渉回避及び緩和手順について、前述の変数を計算する特定の式を参照して、更に詳細に説明する。この場合にも同様に、複数の基本変数がタイムスロット毎及び干渉ノード毎に定期的に再計算される。これらは、指向性リンクLk毎の各タイムスロットiのリンク品質N_qualityiLk及びその量子化値TS_QualiLkと、タイムスロットIの潜在的SIRmnTiと、無指向性リンク状態Can_AllocLkとを含む。
【０３１３】
これらの変数は、タイムスロットiの干渉又は潜在的干渉のインジケータである。これらの変数の小さい劣化は、潜在的干渉を回避するために、より好ましいタイムスロットを再スケジュールするゆっくりとした試み（すなわち、第１の比較的長期間）を起動する。干渉するノードの対はまた、この状態を検出し得るため、ゆっくりとしたバックオフは、双方のノードの対が同時に再スケジューリングして場合によって他の衝突を取り込む可能性を低減する。
【０３１４】
従って、干渉するノードの対がまず再スケジューリングすることを決定すると、これは再スケジューリングの必要性を除去してもよい。この“低速”バックオフ手法（すなわち、第１の期間内）では、再スケジューリング動作は、次のΔTR秒でのランダムな時に確率prsslowで起動される。これが起動されない場合、変数が再計算されたときに（毎秒約１回）検査が実行される。検査が再び失敗すると、再スケジューリング動作は、次のΔTR秒でのランダムな時に確率prsslowで起動される。この検査処理は、潜在的な干渉条件が存在する限り継続する。
【０３１５】
存在するかなりの劣化の検出は、存在する過度の干渉を回避するように、より迅速な再スケジューリングを必要とする。この場合、“高速”バックオフ手法は、第２の比較的短い期間内のタイムスロットの再スケジューリングを起動することである。一例として、これは、例えば次の指向性エポック内でもよく、これは確率prsfastで行われる。再スケジューリングがこのエポック内に起動されない場合、確率prsfastで次のエポック内に軌道され、以下同様である。
【０３１６】
現在のタイムスロット割り当ての再割り当てを行わないことと、再割り当てに対して低速又は高速バックオフを行うこととの間の決定は、以下の基準に基づくことが好ましい。まず、ノードmとnとの間のリンクのタイムスロットiが以下の条件のいずれか一方を満たす場合、タイムスロットの再割り当ては考慮されない。
【０３１７】
【数４７】
2006522547.tif 000073
【０３１８】
【数４８】
2006522547.tif 000074
更に、ノードmとnとの間のリンクのタイムスロットiが以下の条件のいずれか一方を満たす場合、タイムスロットの再割り当てに対して低速バックオフ（ノードmとnとの間のリンクの唯一のタイムスロットである場合には高速バックオフ）が使用される。
【０３１９】
【数４９】
2006522547.tif 000075
【０３２０】
【数５０】
2006522547.tif 000076
また、ノードmとnとの間のリンクのタイムスロットiが以下の条件のいずれか一方を満たす場合、タイムスロットの再割り当てに対して高速バックオフが使用される。
【０３２１】
【数５１】
2006522547.tif 000077
【０３２２】
【数５２】
2006522547.tif 000078
以下の条件が満たされる場合、タイムスロットが割り当て解除され、ノードmとnとの間のリンクが失われたことをルーティングプロトコル（例えばOLSR）が通知される。
【０３２３】
【数５３】
2006522547.tif 000079
簡単に前述したように、高速又は低速バックオフを通じて再スケジューリングが必要であると決定されると、タイムスロットiがSPタイムロットである場合には、特定の予防措置が望ましいことがある。SPタイムスロットの重要性のため、このタイムスロットが劣化しないことが重要である。タイムスロットがノードmとnとの間に割り当てられた唯一のタイムスロットである場合、低速バックオフが満足できることを以下の条件が示した場合であっても、高速バックオフが行われることが好ましい。
【０３２４】
その他の場合は、ノードm及びnが複数の割り当てられたタイムスロットを有する場合である。SPタイムスロットについて低速バックオフが示される場合には、ノードmは、そのDAタイムスロットのうち１つがSPタイムスロットにされたことをノードnに迅速に通知し、それによって、DAタイムスロットのあまり重要でない役目を現在のタイムスロットに仮定させる。ノードm及びnに割り当てられたその他のタイムスロットがSPタイムスロットとして変更するのに十分な品質ではない場合、SPタイムスロットiを再スケジューリングするために、高速バックオフが使用される。タイムスロットiがDAタイムスロットである場合、又はDAタイムスロットにされ得る場合、以下の基準により決定される高速又は低速バックオフが使用される。
【０３２５】
特に、新しいタイムスロット割り当てが行われるまで、再割り当てされるタイムスロットは割り当て解除されない。新しいタイムスロットが取得された後に、古い疑問のある又は悪化したタイムスロットが割り当て解除され得る。ノードmとnとの間のリンクについて他のタイムスロットが利用可能である場合には、“低”品質のタイムスロット（TS_QualiLk=BAD）でのパケットの転送は中止されることが好ましい。
【０３２６】
Optimized  Link  State  Routing（OLSR）ルーティングアルゴリズムを備えた簡単なインタフェースは、本発明に含まれてもよく、図２及び２９を参照して以下に説明する。当業者にわかるように、OLSRでは、リンク状態情報は、リンクの状態を定量化することができる。完全なトポロジ情報が維持され、隣接トポロジ情報がネットワークの他の全てのノードに定期的にブロードキャストされ、完全なネットワークトポロジを構成することが可能になる。トラヒック要求及び干渉の緩和に合致するようにタイムスロットの割り当て及び再割り当てを取り巻く動作のほとんどは、OSLRから隠されるべきである。隣接ノードとのリンクに割り当てられる複数のタイムスロットが存在する場合（例えば隣接ノードkへのリンクがmのタイムスロットi1,i2,...,imを有する場合）に問題が生じる。全てではないが１つ以上のタイムスロットが干渉により悪化した品質であると決定されると、タイムスロットの再スケジューリングが起動され得る。隣接ノードへの少なくとも１つのタイムスロットが依然として高品質である限り、ノードは依然として隣接に接続しており、ルーティングテーブルに変更は必要ない。従って、OLSRをこれに反応させる必要はない。リンクは、再スケジュールの間に何らかの容量の損失を受け、これが問題になることがあるが、OLSRが行うべきことは何もない。全てのタイムスロットが悪化した品質である場合、OSLRは反応して、他のリンクを通じてデータを再ルーティングするように許可されなければならない。以下のリンク品質指標は、そのリンクに割り当てられたタイムスロット毎の最大品質として、ノードkへのリンクについて定められる。
【０３２７】
【数５４】
2006522547.tif 000080
ノードkへのリンクの品質指標N_qualityLkは、それが変化する毎にOLSRに報告され得る。この品質指標は、OLSRが一般的に受信HELLOパケットから計算する品質指標と交換する。それは、標準的なOLSR品質指標を交換するが、全く同じようにOLSRで使用される。OLSRで一般的に行われるように、ヒステリシス機能がそれに適用され、OLSRで見られるような“リンクフラッピング（link  flapping）”を低減してもよい。リンク品質があまりにも悪化しすぎると、リンクは“down”と宣言され、OSLRはそのHELLO及びTC更新パケットで新しい状態情報を自動的に送信し、ルートを再計算する。
【０３２８】
より具体的には、コントローラ18（図２）は、OSLRのようなルーティングプロトコルでルートを発見して隣接ノードへの通信をルーティングする通信ルータ18iを有することが好ましい。タイムスロットスケジューリングユニット18a/18bは、各隣接モバイルノードと通信リンクを確立するようにタイムスロットをスケジューリングし、アンテナ照準ユニット18cは、通信中に各隣接モバイルノードに指向性アンテナを向ける。ここで、リンク品質推定器18hは、通信リンクについてスケジューリングされたタイムスロット毎の品質に基づいてリンク品質を推定し、推定のリンク品質を通信ルータ18iに報告するために提供されている。
【０３２９】
前述のように、推定のリンク品質は、通信リンクにスケジューリングされた各タイムスロットの最大品質として定められてもよく、ルータ18iは、推定のリンク品質に基づいて隣接ノードに通信をルーティングしてもよい。通信リンクは、リンクの少なくとも１つのタイムスロットの最大品質が所定の閾値より上にある限り維持されることが好ましく、リンクの推定のリンク品質が所定の閾値より下になったときに、ルータ18iは新しいルートの発見を開始する。ルータ18iは、リンク品質推定器から報告された推定のリンク品質に対してヒステリシス機能を実行してもよい。
【０３３０】
図２９を参照して、本発明のこの方法の態様の一般ステップについて説明する。その方法はブロック290で始まり、それぞれブロック291及び292において、前述の手法に従って、タイムスロットがスケジューリングされ、アンテナが向けられる。ブロック293において、リンク品質が推定され、ブロック295で方法が終了する前に、ブロック294で示すように通信ルータ18i又はOLSRに報告される。
【０３３１】
本発明は、フェーズドアレイネットワークの完全分散型のリンクスケジューリングアルゴリズム及びプロトコルを提供する。前述のアルゴリズム／プロトコルは、ノード毎に単一の指向性ビームの場合を仮定して説明し、その単一の指向性ビームは時間共有され、そのアクセスについて割り当てられたタイムスロットの間に他のノードに示されることに留意すべきである。しかし、その手法は、ノード毎に如何なる数の進行ビームがある場合にも使用され得る。
【図面の簡単な説明】
【０３３２】
【図１】本発明による無線モバイルアドホックネットワークを示した図
【図２】本発明による無線モバイルノードを示した詳細なブロック図
【図３】本発明によるタイムスロットのフレームを示した図
【図４】本発明による図２に示したネットワーク図への利用可能タイムスロットのスケジューリング
【図５】本発明に従って半永久的タイムスロット及び利用可能タイムスロットをスケジューリングするトップレベルの状態図
【図６】本発明による半永久的タイムスロットのスケジューリング処理を示した図
【図７】本発明に従って新しい通信リンク用にスケジューリングされる半永久的タイムスロットを示した図
【図８】本発明による利用可能タイムスロットのスケジューリング処理を示した図
【図９】本発明に従って通信リンクに追加される利用可能タイムスロットを示した図
【図１０】本発明に従ってフェーズドアレイアンテナからの複数の同時アンテナビームに基づいて新しい通信リンク用にスケジューリングされる半永久的タイムスロットを示した図
【図１１】本発明に従ってフェーズドアレイアンテナからの複数の同時アンテナビームに基づいて新しい通信リンク用にスケジューリングされる半永久的タイムスロットを示した図
【図１２】無指向性リンク品質値に基づいてモバイルノード間の指向性通信リンクを確立する本発明による方法を示したフローチャート
【図１３】無指向性リンク品質値に基づいてモバイルノード間の指向性通信リンクを確立する本発明による方法を示したフローチャート
【図１４】リンク利用率に基づいて要求割り当てのタイムスロットを割り当てる本発明による方法を示したフローチャート
【図１５】リンク利用率に基づいて要求割り当てのタイムスロットを割り当てる本発明による方法を示したフローチャート
【図１６】リンク利用率に基づいて要求割り当てのタイムスロットを割り当てる本発明による方法を示したフローチャート
【図１７】本発明によるデータ優先方法を示したフローチャート
【図１８】本発明によるデータ優先方法を示したフローチャート
【図１９】本発明に従ってパケット受信誤り値を決定し、リンク使用に基づいてリンク使用を調整する方法を示したフローチャート
【図２０】本発明に従ってパケット受信誤り値を決定し、リンク使用に基づいてリンク使用を調整する方法を示したフローチャート
【図２１】本発明の無線通信ネットワークにおいて２対のモバイルノードについての干渉回避シナリオを示した概略ブロック図
【図２２】本発明による干渉回避方法を示したフローチャート
【図２３】本発明による干渉回避方法を示したフローチャート
【図２４】本発明に従ってタイムスロットを再割り当てする方法を示したフローチャート
【図２５】本発明に従ってタイムスロットを再割り当てする方法を示したフローチャート
【図２６】本発明に従ってリンク品質に基づいて異なる期間内にタイムスロットを再割り当てする方法を示したフローチャート
【図２７】本発明に従ってリンク品質に基づいて異なる期間内にタイムスロットを再割り当てする方法を示したフローチャート
【図２８】本発明に従ってリンク品質に基づいて異なる期間内にタイムスロットを再割り当てする方法を示したフローチャート
【図２９】本発明に従ってルーティングプロトコルに対してリンク品質を推定して報告する方法を示したフローチャート
【図１】
2006522547.tif 000081
【図２】
2006522547.tif 000082
【図３】
2006522547.tif 000083
【図４】
2006522547.tif 000084
【図５】
2006522547.tif 000085
【図６】
2006522547.tif 000086
【図７】
2006522547.tif 000087
【図８】
2006522547.tif 000088
【図９】
2006522547.tif 000089
【図１０】
2006522547.tif 000090
【図１１】
2006522547.tif 000091
【図１２】
2006522547.tif 000092
【図１３】
2006522547.tif 000093
【図１４】
2006522547.tif 000094
【図１５】
2006522547.tif 000095
【図１６】
2006522547.tif 000096
【図１７】
2006522547.tif 000097
【図１８】
2006522547.tif 000098
【図１９】
2006522547.tif 000099
【図２０】
2006522547.tif 000100
【図２１】
2006522547.tif 000101
【図２２】
2006522547.tif 000102
【図２３】
2006522547.tif 000103
【図２４】
2006522547.tif 000104
【図２５】
2006522547.tif 000105
【図２６】
2006522547.tif 000106
【図２７】
2006522547.tif 000107
【図２８】
2006522547.tif 000108
【図２９】
2006522547.tif 000109
【国際調査報告】
2006522547.tif 000110