(57)【要約】本発明は、チャネル内へのパケットの無衝突伝送のための媒体アクセス制御（ＭＡＣ）プロトコルを提供するものであり、局所近傍内のノードが再伝送しようとする場合、ノードには、ノードの局所近傍の構成状況とタイムスロットの公示に関してノードが得ている知識に基いて、無衝突伝送用のタイムスロットが割り当てられるようになっている。スケジューリング手順は、ネットワークの年齢を、ノードに付帯している固有の識別子と共に利用する。各ノードへの候補伝送時間は、別のノードにより公示される次回伝送時間のリストを使って判定される。ノードは、可能な伝送時間リストから公示されている伝送時間を除外し、様々な入力サンプルに対して様々な（擬似乱数の）出力の分配を提供する関数を使って、そのノードの候補伝送時間を計算する。この関数は、ハッシュ関数であってもよいし、暗号関数やルックアップ関数であってもよい。公示伝送時間を獲得できないノードに対しては、候補伝送時間の計算に、それらのノードの識別子を利用する。【特許請求の範囲】
【請求項１】
分散形パケットスケジューリング用のシステムにおいて、
アドホック・ネットワーク内のノードに関係付けられたデータ構造であり、伝送時間パラメーターを含んでいる物理的近傍リストと、
前記伝送時間パラメーターに応じて伝送される制御パケットと、を備えていることを特徴とするシステム。
【請求項２】
前記物理的近傍リストを圧縮するように配置されているコンプレッサーを更に備えていることを特徴とする、請求項１に記載のシステム。
【請求項３】
前記制御パケットは、ネットワーク構成パケットであることを特徴とする、請求項１に記載のシステム。
【請求項４】
前記伝送時間パラメーターは、伝送ホールドオフ時間であることを特徴とする、請求項１に記載のシステム。
【請求項５】
前記伝送時間パラメーターは、次の伝送時間であることを特徴とする、請求項１に記載のシステム。
【請求項６】
前記伝送時間パラメーターは、伝送ホールドオフ時間と次の伝送時間を含んでいることを特徴とする、請求項１に記載のシステム。
【請求項７】
前記物理的近傍リストは、前記伝送時間パラメーターに関係付けられた報告済みフラグを含んでいることを特徴とする、請求項１に記載のシステム。
【請求項８】
分散形パケットスケジューリング用の方法において、
アドホック・ネットワーク内のノードに関係付けられている、ノード識別子及び伝送時間パラメーターを含む物理的近傍情報を求める段階と、
前記物理的近傍情報に従って制御パケットを作る段階と、
前記伝送時間パラメーターに従って前記制御パケットを伝送する段階と、から成ることを特徴とする方法。
【請求項９】
前記制御パケットは、ネットワーク構成パケットであることを特徴とする、請求項８に記載の方法。
【請求項１０】
前記制御パケットは、
距離パラメーターと、
ノード識別子と、
次の伝送時間と、
伝送ホールドオフ時間と、を備えていることを特徴とする、請求項８に記載の方法。
【請求項１１】
前記制御パケットは、構成可能であることを特徴とする、請求項８に記載の方法。
【請求項１２】
前記制御パケットは、適応性であることを特徴とする、請求項８に記載の方法。
【請求項１３】
前記制御パケットは、ＭＡＣアドレスを更に備えていることを特徴とする、請求項１０に記載の方法。
【請求項１４】
前記物理的近傍情報は、前記伝送時間パラメーターに応える報告済みフラグを含んでいることを特徴とする、請求項８に記載の方法。
【請求項１５】
前記伝送時間パラメーターは、伝送ホールドオフ時間であることを特徴とする、請求項８に記載の方法。
【請求項１６】
前記伝送時間パラメーターは、次の伝送時間であることを特徴とする、請求項８に記載の方法。
【請求項１７】
前記伝送時間パラメーターは、伝送ホールドオフ時間と次の伝送時間を含んでいることを特徴とする、請求項８に記載の方法。
【請求項１８】
ネットワーク構成パケット内に含まれている近傍リスト内の複数の近隣エントリを圧縮するための方法において、
前記近隣エントリがラウンドロビンリスト内で報告されている場合、前記近隣エントリが３ホップ近隣エントリであれば、２ホップスケジューリングモードで作動している場合、及び前記近隣エントリに関係付けられた報告済みフラグが設定されている場合は、近隣エントリを除外する段階と、
前記近隣エントリが除外されていなければ、前記近隣エントリを圧縮された近傍リスト内に含む段階と、から成ることを特徴とする方法。
【請求項１９】
前記報告済みフラグは、前記ネットワーク構成パケットの伝送によって真に設定されることを特徴とする、請求項１８に記載の方法。
【請求項２０】
前記近隣に関係付けられた前記伝送パラメーターに従って前記圧縮済み近傍リストを順序付けする段階を更に含んでいることを特徴とする、請求項１８に記載の方法。
【請求項２１】
ノードと関係付けられているネットワーク構成パケットをアドホックネットワーク内で伝送するための方法において、
前記ノードに関係付けられた次の伝送時間を求める段階と、
前記ノードに関係付けられた次のホールドオフ時間を求める段階と、
飛び越し伝送フラグを評価し、前記飛び越し伝送フラグが設定された場合は、
ネットワーク構成パケットを作る段階と、
前記近隣エントリが報告されているかどうかによって、近隣エントリと関係付けられた報告済みフラグを設定する段階と、
前記ネットワーク構成フラグを伝送する段階と、から成ることを特徴とする方法。
【請求項２２】
伝送スケジューリングをアドホックネットワークで伝送するための方法において、
近隣エントリに関係付けられている次の伝送時間に従って物理的近隣リスト内の近隣エントリを順序付けする段階と、
各近隣エントリに対する最早次回伝送時間を計算する段階と、
近隣ノードに関係付けられている暫定伝送時間を、前記近隣ノードに関係付けられている現在の伝送時間に前記近隣ノードに関係付けられている公示された伝送ホールドオフ時間を加えた値に等しいと設定する段階と、
近傍選定を保持する段階と、
前記近傍選定に基いて次の伝送時間をスケジューリングする段階と、から成ることを特徴とする方法。
【請求項２３】
前記最早次回伝送時間を計算する段階は、前記近隣エントリに関係付けられている伝送ホールドオフ時間に、前記近隣エントリに関係付けられている前記次の伝送時間を加える段階を含んでいることを特徴とする、請求項２２に記載の方法。
【請求項２４】
前記有資格競合ノードは、前記暫定伝送時間以下の最早次回伝送時間を有する前記物理的近隣リスト内の近隣ノードを含むことを特徴とする、請求項２２に記載の方法。
【請求項２５】
前記近傍選定を保持する段階は、
有資格競合ノードを判定する段階と、
前記有資格競合ノードが前記選定に勝利しない場合は、前記暫定時間を次のネットワーク構成フレームに等しいと設定する段階と、を更に含むことを特徴とする、請求項２４に記載の方法。
【請求項２６】
前記ノードに関係付けられている前記暫定伝送時間が前記物理的近隣リスト内のノードの前記次の伝送時間と等しいとき、及び、前記暫定伝送時間を次のネットワーク構成フレームに等しいと設定するときを判定する段階を更に含んでいることを特徴とする、請求項２５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ルーターが、動くことができ且つホストとホストに取り付けられているネットワークの両方を有している、アドホック・ネットワークにおける無衝突伝送のスケジューリングに関する。
【背景技術】
【０００２】
多数の媒体アクセス制御（ＭＡＣ）プロトコルは、無線ネットワーク用に開発されてきた。キャリア検知多重アクセス（ＣＳＭＡ）プロトコルは、多重反射パケット無線ネットワークで用いられた最初のプロトコルだった。多重反射ネットワークにおけるＣＳＭＡの限界は、互いから隠れているソースがそれらの伝送を検出できず、そのことがＣＳＭＡの性能を純正ＡＬＯＨＡプロトコルの性能にまで低下させることである。多数のＭＡＣプロトコルが、ＣＳＭＡの隠れ端末問題を解決するために提案され、実行されてきた。同じ受信器の範囲内の複数の送信器が互いの伝送を検知できる限り、ＣＳＭＡプロトコルの処理能力は良好である。不都合なことに、「隠れターミナル」問題は、キャリア検知ではその場合の衝突を避ける事ができないので、ＣＳＭＡの性能を実質的に低下させるのである。
【０００３】
話中音多重アクセス（ＢＴＭＡ）プロトコル（Ｆ．Ａ．Ｔｏｂａｇｉ及びＬ．Ｋｌｅｉｎｒｏｃｋ「無線チャネルにおけるパケット切換：パートＩＩ  キャリア感知多重アクセスモードにおける隠れターミナル問題及び話中音の解決法」、ＩＥＥＥ伝送通信、第ＣＯＭ２３巻、第１２号、１４１７−１４３３頁、１９７５年）は、ＣＳＭＡの隠れターミナル問題に取り組むための最初の提案であった。ＢＴＭＡは、ステーションベースのネットワーク用に設計されており、チャネルを、メッセージチャネルと話中音チャネルに分けている。ベースステーションは、データチャネルで搬送波を感知する限り、話中音信号を話中音チャネルで伝送する。ベースステーションは、全ターミナルを直線的に見ることができる位置にあるので、各ターミナルは、話中音チャネルを感知して、データチャネルの状態を判定することができる。ＢＴＭＡの限界は、データチャネルの状態を伝えるために別のチャネルを利用すること、受信器が、データチャネル内の搬送波を検知しながら話中音を伝送しなければならないこと、及び、狭帯域チャネルで話中音信号を検知するのが難しいことである。
【０００４】
パケット無線ネットワーク用の受信器開始話中音多重アクセスプロトコルも提案されている（Ｃ．Ｗｕ及びＶ．０．Ｋ．Ｌｉ「パケット無線ネットワークにおける受信器開始話中音多重アクセス」、ＡＣＭ  ＳＩＧＣＯＭＭ８７ワークショップ：コンピューター通信技術におけるフロンティア、米国、バーモント州、Ｓｔｏｗｅ、１９８７年、８月１１−１３日）。この方式では、送信器は、データパケットを送る前に、受信器に送信要求（ＲＴＳ）を伝送する。受信器は、正しいＲＴＳを得ると、別のチャネルで話中音を伝送し、他のソースにバックオフするよう警告を出す。正しいソースには、常に、データパケットの伝送を続行できることが通知される。この方式の限界は、この方式が、未だに受信器に別の話中音チャネルと全二重オペレーションを必要としていることである。
【０００５】
幾つかのプロトコルが、小さな制御パケットで済み、データパケットソースが互いに聴こえない場合のデータ衝突を回避することを目的とした異なる型式の「衝突回避」ハンドシェークに基づいて提案されてきた。先行技術における衝突回避方法は、分割チャネル予約多重アクセス（ＳＲＭＡ）プロトコルに、Ｔｏｂａｇｉ及びＫｌｅｉｎｒｏｃｋによって最初に導入された基本原理（Ｆ．Ａ．Ｔｏｂａｇｉ及びＬ．Ｋｌｅｉｎｒｏｃｋ「無線チャネルにおけるパケット切換：パートＩＩＩ  ポーリング及び（動的）分割チャネル予約多重アクセス」、ＩＥＥＥ伝送通信、ＣＯＭ第２４巻、第８号、８３２−８４５頁、１９７６年）に従っている。ＳＲＭＡ及び大部分の後続の衝突回避プロトコルでは、送信器ノードは、ＲＴＳを送る前にチャネルを感知しているか否か、通信要求（ＲＴＳ）パケットを目的の受信器へ送る。明確なＲＴＳを聞いた受信器は、送信可（ＣＴＳ）で応答し、送信器は、明確なＣＴＳを聞いた後でデータパケットを送ることができる。
【０００６】
Ｅｃｈｅｌｏｎシステムズ社に譲渡された米国特許第５，３１９，６４１号は、ステーションは一旦送信するパケットを有したときにはチャネルの聞き取りを待たなければならないランダム待機時間を導入することにより、ＣＳＭＡ  ｐ持続プロトコルを改良する方法を開示している。開示されている本方法は、隠れターミナルを有するネットワーク内では作動しない。
【０００７】
アップルコンピューター社に譲渡された米国特許第４，６６１，９０２号は、ステーションがＲＴＳを送る前に搬送波感知を使用する単一のチャネル上でＳＲＭＡを実行するに等しい方法を開示している。
【０００８】
ＭＡＣＡ（Ｐ．Ｋａｒｎ「ＭＡＣＨ−パケット無線用の新しいチャネルアクセス法」ＡＲＲＬ／ＣＲＲＬアマチュア無線第９回コンピューターネットワーキング会議、１３４−４０頁、ＡＲＲＬ、１９９０年）は、搬送波感知無しで通信要求（ＲＴＳ）パケットが送られる単一のチャネル上で作動するＳＲＭＡに等しい技法を含んでいる。パケットトレーンをサポートする方法についての記載はない。
【０００９】
Ｐｒｏｘｉｍ社に譲渡された米国特許第５，２３１，６３４号は、単一チャネル上にＳＲＭＡの基本的な方式を適用する方法を開示している。ＲＴＳは、目前のデータパケットの長さを特定する。
【００１０】
ＩＢＭ社に譲渡された米国特許第５，５０２，７２４号は、衝突回避ハンドシェークを拡張して、多重データパケットが一対の通信ステーション間で流れるようにする方法を開示している。第２ステーションとの接続を確立しようとするステーションは、チャネルを感知する。チャネルがアイドル状態にある場合、接続要求（ＣＲ）パケットを意図する受信器ステーションへ送る。ＣＲは、その接続が含むデータパケット数を指定している。相手の受信器は、接続確認（ＣＣ）パケットを送信ステーションへ送るが、ＣＣも、接続のパケット数を指定する。送信ステーションは、正しいＣＲ及びＣＣパケットを交換した後、１つ又は複数のデータパケットを送り、受信ステーションは、どのデータパケットが正しく受信されたかを特定する肯定応答パケットを送る。接続を終了させる際は、送信ステーションが切断要求（ＤＲ）を送り、受信ステーションは切断確認（ＤＣ）を発行する。ＣＲパケットを受信するステーションは、公示された数のデータパケットを受信器に送るのに十分な時間の分だけバックオフする。ＣＲ又はＣＣを受信した後、ステーションは、その接続内で送られるパケット数に比例してタイマーが切れるとき、又は、ＤＲ又はＤＣパケットを受信したときに、チャネルへのアクセスを試みることができる。米国特許第５，５０２，７２４号に開示されている方法の限界は、その方法が、受信器によるＣＣパケットの伝送があっても、データパケットの無衝突伝送を保証できないことである。受信器からその近隣へパケット・バイ・パケットベースでフィードバックする必要性が、Ｆｕｌｌｍｅｒ及びＧａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓによって示された（Ｃ．Ｌ．Ｆｕｌｌｍｅｒ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「無線ネットワーク内の隠れターミナル問題に対する解決法」、議事録ＡＣＭ  ＳＩＧＣＯＭＭ９７、仏国、カンヌ、１９９７年、９月１４−１８日）。受信器によって送信されるＣＣパケットは、受信器の近隣で、別のパケットと衝突するかもしれないので、ＣＣパケットは、隠れノードに十分なフィードバックを提供しないし、更に、フィードパケットを要求パケットより長くする必要性が、Ｆｕｌｌｍｅｒ及びＧａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓによって示された（Ｃ．Ｌ．Ｆｕｌｌｍｅｒ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「パケット無線ネットワークのためのフロア補足多重アクセス（ＦＡＭＡ）」、議事録ＡＣＭ  ＳＩＧＣＯＭＭ９５、マサチューセッツ州、ケンブリッジ、１９９５年、８月２８日―９月１日）。更に、開示されている方法が、ステーションの全近隣へ送られる同報通信パケットに言及していても、その同報通信又はマルチキャストパケットが、送信ステーションの全近隣によって干渉されることなく受信されることを保証する前提にはならない。
【００１１】
ゼロックス社に譲渡された米国特許第５，７２１，７２５号は、ＳＲＭＡと同様な方法を開示しており、それがＭＡＣＨに対する改良になると記載されている。開示されている本方法は、ＲＴＳパケット内でデータパケットに望ましいデータ転送速度を指定し、送信器と受信器が送信データ転送速度を調整できるようにすることによってＭＡＣＨを拡張する。本方法は、ＣＴＳの長さが何れのＲＴＳの長さよりも長くなるようにして、隠れステーションがＲＴＳとＣＴＳの衝突を確実に検知できるようにする規定を作っていないので、隠れターミナルを有するネットワーク内の無衝突伝送を保証することはできない。
【００１２】
ＤＦＷＭＡＣ  ＩＥＥＥ８０２．１１（Ｋ．Ｃ．Ｃｈｅｎ「モバイル計算のための無線ＬＡＮの媒体アクセス制御」、ＩＥＥＥネットワーク、第８巻、第５号、５０−６３頁、１９９４年）、ＦＡＭＡ−ＮＣＳ（Ｃ．Ｌ．Ｆｕｌｌｍｅｒ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「無線ネットワークにおける隠れターミナル問題に対する解決法」、議事録  ＡＣＭ  ＳＩＧＣＯＭＭ９７、仏国、カンヌ、１９９７年、９月１４−１８日）及びＲＩＭＡ（Ｊ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ及びＡ．Ｔｚａｍａｌｏｕｋａｓ「無線ネットワークにおける衝突回避ハンドシェークの逆行」、議事録  ＡＣＭ／ＩＥＥＥ  Ｍｏｂｉｃｏｍ９９、１９９９年９月）は、衝突回避プロトコルの３つの最近の追加例である。ＩＥＥＥ８０２．１１は、ＲＴＳの伝送を感知する搬送波を有するＳＲＭＡと非常によく似た方法である。ＦＡＭＡ−ＮＣＳの目的は、送信するデータを有するステーションが、データパケットを送信する前に受信器付近（「フロアー」と呼ばれる）のチャネル制御を捕捉し、データパケットが受信器で他のパケットと衝突しないことを保証することである。ＦＡＭＡ−ＮＣＳは、ＲＴＳとＣＴＳの衝突を検知するために、ＣＴＳの長さをＲＴＳの長さよりずっと長くするが、そのことは、先行する衝突回避プロトコルでは実行できない。ＲＩＭＡは、ＳＲＭＡに最初に導入された衝突回避ハンドシェーク方法を逆行させるプロトコルのファミリーを含んでおり、受信器のポールをデータの送信器にする。同じＲＴＳ−ＣＴＳ交換又は休止前のＲＴＳに基づく単一チャネル無線ネットワーク又は有線ローカルエリアネットワークに対して、幾つかの別の媒体アクセス制御（ＭＡＣ）プロトコルが提案されている。しかしながら、この２、３年、そのようなプロトコルに基づく衝突回避プロトコル及びシステムに人気が出ているのは確かだが、全ての衝突回避ＭＡＣプロトコルの２つの重要な性能の限界は、（ａ）チャネルアクセス遅延保証を提供できず、リアルタイムの利用で大きな問題となること、及び（ｂ）無衝突マルチキャスト又は同報通信を明確にサポートせず、ノードが同じマルチキャストパケットを、一度に各マルチキャストグループの近隣に、多数回伝送しなければならないか、又は、ＡＬＯＨＡプロトコルのように受信の可能性は低いパケットが送信されること、である。更に、衝突回避プロトコルには搬送波感知が必要であり、非常に高いチップレートで直接連続スペクトル拡散無線を正しく実行することは、技術的にも経済的にも現実的ではない。
【００１３】
隠れターミナル干渉問題を阻止するため、固有のコード（拡散コード又は周波数ホッピングシーケンス）を受信器又は送信器に割り当てることができる。
【００１４】
この方法の例は、Ｍｅｔｒｉｃｏｍネットワークであった。しかしながら、受信器指向コード割り当て（ＲＯＣＡ）及び送信器指向コード割り当て（ＴＯＣＡ）は、ノード・ツー・コードマッピングを備えた無線を事前に構成するか、近隣の送信器又は受信器に使用されているコードを見つけ出すか、の何れかを必要とする。更に、効率的な同報通信は、送信器の近隣が、同時に送信器に耳を傾けることに同意して、伝送数を最小にしなければならないので、単にＴＯＣＡ法を確立するだけでは保証されない。
【００１５】
多重反射無線ネットワークに用いられているもう１つのチャネルアクセス法は、伝送スケジュールを確立する段階、即ち、ステーションを、衝突が起こらない方法で、異なる時間及び異なるデータチャネル（例えば、周波数、拡散コード又はその組み合わせ）に割り当てる段階を含んでいる。伝送スケジューリングは、静的でも、動的でもよく、動的伝送スケジューリングに基づくＭＡＣプロトコルは、無線チャネルの空間再利用を検討するので、ＴＤＭＡ及びＦＤＭＡのような固定スケジューリング方式よりもチャネル利用度が高い。
【００１６】
ＴＤＭＡプロトコルでは、時間は、タイムスロットから成るフレームに分割される。タイムスロットが特定ノードに割り当てられるか、タイムスロットを割り当てるのに中央集中ステーションが利用される。ＴＤＭＡの限界は、ネットワークの変更に適応するのは遅く、ノードがバースト的な通信量のソースになっている場合はチャネルの利用が非能率になるタイムスロットへのノードの固定割り当てと、中央集中割り当てを利用することから生じている。
【００１７】
ステーションがアップリンクでＡＬＯＨＡ、スロット付ＡＬＯＨＡ又は他の競合プロトコルを利用して、ベースステーションからタイムスロットを要求する動的ＴＤＭＡ法に基づく先行技術には、多くの方法がある。この方法の一例が、ＮＥＣ米国社に譲渡された米国特許第５，６３８，３７１号に開示されているシステムである。本発明は、ベースステーションのスロット割り当てを不要にする。
【００１８】
最近では、中央のベースステーションを必要としない動的タイムスロット割り当てを提供する多くのプロトコルが提案されている。これらのプロトコルは、トポロジ独立型とトポロジ依存型の時間スケジューリングプロトコルに分類できる。
【００１９】
Ｓｈｅｐａｒｄ（Ｔ．Ｓｈｅｐａｒｄ「超過密パケット無線ネットワークのためのチャネルアクセス方式」、議事録ＳＩＧＣＯＭＭ‘９６、１９９６年；Ｔ．Ｓｈｅｐａｒｄ「無衝突パケット転送を提供する分散形チャネル管理を有する測定可能な自己構成パケット無線ネットワーク」、米国特許第５，６８２，３８２号、１９９７年１０月２８日）と、Ｃｈａｌａｍｔａｃ等（Ｉ．Ｃｈｌａｍｔａｃ等「多重反射モバイル無線ネットワークのための時間拡散多重アクセス（ＴＳＭＡ）プロトコル」、ＩＥＥＥ／ＡＣＭ  ネットワーク化におけるトランザクション、第５巻、第６号、１９９７年１２月）と、Ｊｕ及びＬｉ（Ｊｉ−ＨｅｒＪｕ、ＶｉｃｔｏｒＯ．Ｋ．Ｌｉ「多重反射パケット無線ネットワーク内の最適トポロジ透過スケジューリング法」、ＩＥＥＥ／ＡＣＭ  ネットワーク化におけるトランザクション、第６巻、第３号、１９９８年６月）とは、トポロジ独立型時間スケジューリングプロトコルを提案した。これらのプロトコルでは、ノードが（例えば、ノードのＩＤ手段によって）事前に割り当てられているか、或いは、ノードが公表している伝送スケジュールを採用し、そのようなスケジュールによってノードが送受信する時間を指定する。プロトコルは、ノードのスケジュール内の少なくとも１つの伝送時間に、１又は２ホップ離れている何れかのノードと衝突しない可能性が高いことを保証又は供与する。ＣｈａｌａｍｔａｃとＪｕの方式では、ノードは、どの伝送が成功するか判定できず、高位層（例えばリンク層）プロトコルの作業を複雑にする。これらの方式は、更に、アルゴリズムへの入力パラメーターとして、ネットワーク内のノードの総数及び各ノードの近隣の最大数の値を必要とするので、それらを、最悪の状況に備えた設計にする（従って、ネットワークが予想したほど密でなければ非効率である）か、又は、実際のネットワーク状況（ネットワークが予想したより大きいか又は密か）に対して高感度であるようにする。Ｓｈｅｐａｒｄの方式は、ノードがその近隣と同期化されると仮定することによって衝突を回避し、近隣のスケジュールに関する知識を持ち、多数の伝送近隣から同時に受信することができる。この最後の仮定には、相当高度な無線ハードウェアが必要である。
【００２０】
Ｚｈｕ及びＣｏｒｓｏｎ（Ｃ．Ｚｈｕ、Ｍ．Ｓ．Ｃｏｒｓｏｎ「モバイルアドホックネットワークのための５相予約プロトコル（ＦＰＲＰ）、議事録ＩＥＥＥＩＮＦＯＣＯＭ‘９８）と、Ｔａｎｇ及びＧａｒｃｉａ−Ｌｕｎａ―Ａｃｅｖｅｓ（Ｚ．Ｔａｎｇ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ―Ａｃｅｖｅｓ「トポロジ依存伝送スケジューリングのためのプロトコル」、議事録ＩＥＥＥ無線通信及びネットワーク化会議１９９９（ＷＣＮＣ９９）、ルイジアナ州ニューオリンズ、１９９９年９月２１−２４日；Ｚ．Ｔａｎｇ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ―Ａｃｅｖｅｓ「マルチチャネルパケット無線ネットワークのためのホップ予約多重アクセス（ＨＲＭＡ）」、議事録ＩＥＥＥ  ＩＣ３Ｎ’９８  コンピューター通信及びネットワークの第７回国際会議、ルイジアナ州ラファイエット、１９９８年１０月１２−１５日）は、トポロジ依存スケジューリングプロトコルを開発し、ノードが、自身から１及び２ホップ離れたノードに干渉することなく伝送できる伝送スケジュールを獲得し、ノード当たり近隣数が減少するにつれてチャネル再利用が増大するようにしている。無衝突タイムスロットを予約するために、これらのプロトコルは、ノードに競合させなければならず、競合は各ミニスロットで行われる。更に、これらのプロトコルは、各スロットを複数のミニスロットに分割することを当てにしている。このこと全てが、スロットが有する最小持続時間を制限する。本発明は、スロットの２次分割を必要とせず、ノードが少なくともフレーム時間内に近隣へ応答することを必要としない。
【００２１】
ＴＤＭＡに基づいており、初期のトポロジ独立スケジュールを必要とし、その後にネットワークノード間で通信することによって最終的なスケジュールを調整する幾つかの方法が提案されている。Ｃｈｌａｍｔａｃ（Ｉ．Ｃｈｌａｍｔａｃ「多重反射無線ネットワーク内における最大限のリンク活性化のための公平なアルゴリズム」、ＩＥＥＥ通信におけるトランザクション、第ＣＯＭ−３５巻、第７号、１９８７年７月）は、アルゴリズムを数回繰り返した後、通信要求に対応できる反復リンクスケジュールに基づくアルゴリズムを提案した。アルゴリズムは、各ノードにそのノードＩＤに従って伝送スロットを割り当てることによって提供されるような「リンク当たり１スロット」のスケジュールで始まる。繰り返す度に、スケジュール情報及びスケジューリング「トークン」が（既存のアルゴリズムによって確立された）ルーチングツリーを上下し、満たされていない通信量要求の度合いに従って、追加のスロットをノード又はリンクに割り当てる。Ｅｐｈｒｅｍｉｄｅｓ及びＴｒｕｏｎｇ（Ａ．Ｅｐｈｒｅｍｉｄｅｓ、Ｔ．Ｔｒｕｏｎｇ「多重反射無線ネットワークにおけるスケジューリング同報通信」、ＩＥＥＥ通信におけるトランザクション、第ＣＯＭ−３８号、第４号、１９９０年４月）は、最初に各ノードにそのノードＩＤに対応するスロットが割り当てられ、次に各ノードがその割り当てを利用して「スケルトン」スケジュールをその近隣へ送る同様のアルゴリズムを提案した。次の２つのフレーム（通信スケジュールの２回繰り返し）の間に、そして固定ノード優先性に従って、ノードは、全ての利用可能なスロットが手に入るまで（即ち、衝突を起こさずにそれ以上のスロットを割り当てられなくなるまで）、利用可能なスロットを掴むことができる。スケジュールを固定して、数回繰り返して収束させる必要があり、そしてスケジューリングフレームサイズがネットワークの最大サイズと等しいために、これらの方法は、移動性又は別のダイナミックスに対するスケーラビリティと頑強性を制限している。Ｙｏｕｎｇによって提案された方法（Ｃ．Ｄ．Ｙｏｕｎｇ「ＵＳＡＰ：統合ダイナミック分配マルチチャネルＴＤＭＡスロット割り当てプロトコル」、議事録ＩＥＥＥ  ＭＩＬＣＯＭ９６、１９９６年１０月）も、最初にノード当たり１つのスロットの割り当て、次に別のスロットの割り当てに対するスケジューリングパケットを調整することを必要としている。しかし、最初に割り当てられたスロットは、各「フレーム」内の第１スロットに限定される。従って、各ノードの割り当てスロットは、Ｎ個のフレーム毎に発生し、Ｎは最大ネットワークサイズである。このため、本方法はスケーラブルではない。更に、提案されたスケジュールの追加が近隣によって確認されるまでにノードはＮ個のフレームまで待機しなければならないので、本方法は、ダイナミックな通信状態に適応するのが比較的遅い。
【００２２】
先行技術のＭＡＣプロトコルに関する上記限界の大部分は、頑強で環境適応型のリンク／ＭＡＣ（ＲＥＡＬＭ）プロトコル（Ｄ．Ｂｅｙｅｒ、Ｊ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ及びＣ．Ｆｕｌｌｍｅｒ「無線ネットワークのための適応型通信プロトコル」、米国特許出願、１９９９年２月１０日、ドケット番号００３８６７．Ｐ００１）を、近傍確立伝送スケジューリング（ＮＥＴＳ）プロトコル（Ｊ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ、Ｄ．Ｂｅｙｅｒ、及びＣ．Ｆｕｌｌｍｅｒ「近傍確立伝送スケジューリングのためのプロトコル」、ドケット番号００３８６７．Ｐ００１、１９９９年１０月１５日）と組み合わせることによって取り除かれる。
【００２３】
ＲＥＡＬＭは、送信器と受信器との間にハンドシェークを必要とせずに衝突を回避できるＭＡＣプロトコルである。ＲＥＡＬＭは、スロットに分割された時間フレームに編成されている同期ネットワークを想定している。ＲＥＡＬＭで想定されている同期化の量は、ＩＳＭ帯域内で作動するよう設計され、今日市販されているような、周波数ホッピング無線で作動している何れのネットワークでも必要な同期化と同じタイプである。ＲＥＡＬＭを流しているノードは、その１ホップ及び２ホップの近隣のアイデンティティと、ネットワーク内の現在時刻（例えば現在のフレーム数）を知らなければならない。各ノードは、この情報及び付加情報に基づいて、どのノードがフレームのどのタイムスロットで伝送するかを決定論的に特定する関数（例えば、ハッシュ関数）を評価する。ＲＥＡＬＭは、所与のノードがフレームのタイムスロット内で伝送できる根拠になる優先度を各フレーム内で変更することによって公平性を実現する。或るノードの２ホップ近傍内の全ノードが、自体の近傍に関わる一貫した情報を有していることになれば、全ノードは同じ決定論的アルゴリズムを使って、所与のタイムスロットの勝者を選択するので、衝突が避けられる。
【００２４】
Ｂａｏ及びＧａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ（Ｌ．Ｂａｏ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「アドホックネットワークのためのチャネルアクセススケジューリングの新しい方法」、議事録ＡＣＭ  ＭｏｂｉＣｏｍ２００１−第７回モバイル計算及びネットワーク化に関する年次国際会議、２００１年７月１６−２１日、イタリア、ローマ；Ｌ．Ｂａｏ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「単一指向性リンクを備えたアドホックネットワーク内のチャネルアクセススケジューリング」、議事録ＡＣＭ  ＤｉａｌＭ２００１−第５回モバイル計算及び通信のための離散アルゴリズム及び方法に関する国際ワークショップ、２００１年７月２１日、イタリア、ローマ；Ｌ．Ｂａｏ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「新しい無衝突媒体アクセス制御プロトコル」、議事録ＩＥＥＥ  ＭＩＬＣＯＭ２０００、２０００年１０月２２−２５１日、カリフォルニア州、ロスアンゼルス）は、ＲＥＡＬＭと同様な方法で送信器と受信器との間に特定のハンドシェークが無くても衝突を回避できるチャネルアクセスアルゴリズムを提案している。これらのアルゴリズムは、各ノードが、２ホップ以内の全ノードの識別子を有し、近隣の情報に基づいて、所与のタイムスロットの間にノードに伝送優先度を割り当てることを必要とする。特定されていないアルゴリズムは、近隣の情報を広めると想定されている。
【００２５】
ＲＥＡＬＭを単独で利用することの限界、或いはＢａｏ及びＧａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓにより提案されたアルゴリズムの限界は、これらの方法が、そのような型式の無衝突アクセスに関して指定されているフレームの各タイムスロット内での伝送で競合する２ホップ近傍内の全ノードに基づいている点である。先のフレームの間に伝送することのできたノードが、それらの近傍に、それらが、ある期間の間は伝送スロットに競合しないことを通知できれば、チャネルを更に効率的に利用することができ、それにより、チャネルにアクセスするときに所与のノードが経験する、ノード間の競合及び遅延を効果的に低減される。
【００２６】
【特許文献１】
米国特許第５，３１９，６４１号
【特許文献２】
米国特許第４，６６１，９０２号
【特許文献３】
米国特許第５，２３１，６３４号
【特許文献４】
米国特許第５，５０２，７２４号
【特許文献５】
米国特許第５，７２１，７２５号
【特許文献６】
米国特許第５，６３８，３７１号
【特許文献７】
米国特許第５，６８２，３８２号
【特許文献８】
米国特許出願ドケット番号００３８６７．Ｐ００１
【特許文献９】
米国特許出願ドケット番号００３８６７．Ｐ００５
【特許文献１０】
米国特許出願第０９／２４８，７３８号
【非特許文献１】
Ｆ．Ａ．Ｔｏｂａｇｉ及びＬ．Ｋｌｅｉｎｒｏｃｋ「無線チャネルのパケット切換：パートＩＩ  キャリア検知多重アクセスモードにおける隠れターミナル問題及び話中音の解決法」、ＩＥＥＥ伝送通信、第ＣＯＭ２３巻、第１２号、１４１７−１４３３頁、１９７５年
【非特許文献２】
Ｃ．Ｗｕ及びＶ．Ｏ．Ｋ．Ｌｉ「パケット無線ネットワークにおける受信器開始話中音多重アクセス」ＡＣＭ  ＳＩＧＣＯＭＭ８７  ワークショップ：コンピューター通信技術のフロンティア、米国、バーモント州、Ｓｔｏｗｅ、１９８７年８月１１−１３日
【非特許文献３】
Ｆ．Ａ．Ｔｏｂａｇｉ及びＬ．Ｋｌｅｉｎｒｏｃｋ「無線チャネルにおけるパケット切換：パートＩＩＩ  ポーリング及び（動的）分割チャネル予約多重アクセス」、ＩＥＥＥ伝送通信、第ＣＯＭ２４巻、第８号、８３２−８４５頁、１９７６年
【非特許文献４】
Ｐ．Ｋａｒｎ「ＭＡＣＨ−パケット無線用の新しいチャネルアクセス法」ＡＲＲＬ／ＣＲＲＬアマチュア無線第９回コンピューターネットワーキング会議、１３４−４０頁、ＡＲＲＬ、１９９０年
【非特許文献５】
Ｃ．Ｌ．Ｆｕｌｌｍｅｒ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「無線ネットワーク内の隠れターミナル問題に対する解決法」、議事録ＡＣＭ  ＳＩＧＣＯＭＭ９７、仏国、カンヌ、１９９７年、９月１４−１８日
【非特許文献６】
Ｃ．Ｌ．Ｆｕｌｌｍｅｒ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「パケット無線ネットワークのためのフロア補足多重アクセス（ＦＡＭＡ）」、議事録ＡＣＭ  ＳＩＧＣＯＭＭ９５、マサチューセッツ州、ケンブリッジ、１９９５年、８月２８日―９月１日
【非特許文献７】
Ｋ．Ｃ．Ｃｈｅｎ「モバイル計算のための無線ＬＡＮの媒体アクセス制御」、ＩＥＥＥネットワーク、第８巻、第５号、５０−６３頁、１９９４年
【非特許文献８】
Ｃ．Ｌ．Ｆｕｌｌｍｅｒ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「無線ネットワークにおける隠れターミナル問題に対する解決法」、議事録  ＡＣＭ  ＳＩＧＣＯＭＭ９７、仏国、カンヌ、１９９７年、９月１４−１８日
【非特許文献９】
Ｊ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ及びＡ．Ｔｚａｍａｌｏｕｋａｓ「無線ネットワークにおける衝突回避ハンドシェークの逆行」、議事録  ＡＣＭ／ＩＥＥＥ  Ｍｏｂｉｃｏｍ９９、１９９９年９月
【非特許文献１０】
Ｔ．Ｓｈｅｐａｒｄ「超過密パケット無線ネットワークのためのチャネルアクセス方式」、議事録ＳＩＧＣＯＭＭ‘９６、１９９６年
【非特許文献１１】
Ｉ．Ｃｈｌａｍｔａｃ等「多重反射モバイル無線ネットワークのための時間拡散多重アクセス（ＴＳＭＡ）プロトコル」、ＩＥＥＥ／ＡＣＭ  ネットワーク化におけるトランザクション、第５巻、第６号、１９９７年１２月
【非特許文献１２】
Ｊｉ−ＨｅｒＪｕ、ＶｉｃｔｏｒＯ．Ｋ．Ｌｉ「多重反射パケット無線ネットワーク内の最適トポロジ透過スケジューリング法」、ＩＥＥＥ／ＡＣＭ  ネットワーク化におけるトランザクション、第６巻、第３号、１９９８年６月
【非特許文献１３】
Ｃ．Ｚｈｕ、Ｍ．Ｓ．Ｃｏｒｓｏｎ「モバイルアドホックネットワークのための５相予約プロトコル（ＦＰＲＰ）、議事録ＩＥＥＥＩＮＦＯＣＯＭ‘９８
【非特許文献１４】
Ｚ．Ｔａｎｇ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ―Ａｃｅｖｅｓ「トポロジ依存伝送スケジューリングのためのプロトコル」、議事録ＩＥＥＥ無線通信及びネットワーク化会議１９９９（ＷＣＮＣ９９）、ルイジアナ州ニューオリンズ、１９９９年９月２１−２４日
【非特許文献１５】
Ｚ．Ｔａｎｇ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ―Ａｃｅｖｅｓ「マルチチャネルパケット無線ネットワークのためのホップ予約多重アクセス（ＨＲＭＡ）」、議事録ＩＥＥＥ  ＩＣ３Ｎ’９８  コンピューター通信及びネットワークの第７回国際会議、ルイジアナ州ラファイエット、１９９８年１０月１２−１５日
【非特許文献１６】
Ｉ．Ｃｈｌａｍｔａｃ「多重反射無線ネットワーク内における最大限のリンク活性化のための公平なアルゴリズム」、ＩＥＥＥ通信におけるトランザクション、第ＣＯＭ−３５巻、第７号、１９８７年７月
【非特許文献１７】
Ａ．Ｅｐｈｒｅｍｉｄｅｓ、Ｔ．Ｔｒｕｏｎｇ「多重反射無線ネットワークにおけるスケジューリング同報通信」、ＩＥＥＥ通信におけるトランザクション、第ＣＯＭ−３８号、第４号、１９９０年４月
【非特許文献１８】
Ｃ．Ｄ．Ｙｏｕｎｇ「ＵＳＡＰ：統合ダイナミック分配マルチチャネルＴＤＭＡスロット割り当てプロトコル」、議事録ＩＥＥＥ  ＭＩＬＣＯＭ９６、１９９６年１０月
【非特許文献１９】
Ｌ．Ｂａｏ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「アドホックネットワークのためのチャネルアクセススケジューリングの新しい方法」、議事録ＡＣＭ  ＭｏｂｉＣｏｍ２００１−第７回モバイル計算及びネットワーク化に関する年次国際会議、２００１年７月１６−２１日、イタリア、ローマ
【非特許文献２０】
Ｌ．Ｂａｏ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「単一指向性リンクを備えたアドホックネットワーク内のチャネルアクセススケジューリング」、議事録ＡＣＭ  ＤｉａｌＭ２００１−第５回モバイル計算及び通信のための離散アルゴリズム及び方法に関する国際ワークショップ、２００１年７月２１日、イタリア、ローマ
【非特許文献２１】
Ｌ．Ｂａｏ及びＪ．Ｊ．Ｇａｒｃｉａ−Ｌｕｎａ−Ａｃｅｖｅｓ「新しい無衝突媒体アクセス制御プロトコル」、議事録ＩＥＥＥ  ＭＩＬＣＯＭ２０００、２０００年１０月２２−２５１日、カリフォルニア州ロスアンゼルス
【発明の開示】
【課題を解決するための手段】
【００２７】
本発明は、上記短所、欠点及び問題に取り組むことを目指しており、以下の説明を読み研究して理解頂きたい。
【００２８】
本発明は、パケットのチャネルへの無衝突伝送のための媒体アクセス制御（ＭＡＣ）プロトコルを含んでおり、局所近傍内のノードが再伝送しようとする場合、ノードには、ノードの局所近傍の構成状況とタイムスロットの公示に関してノードが得ている情報に基いて、無衝突伝送用のタイムスロットが割り当てられるようになっている。
【００２９】
本発明の或る態様によれば、スケジューリング手順は、ネットワークの年齢を、ノードに付帯している固有の識別子と共に利用する。
【００３０】
本発明のもう１つの態様によれば、各ノードへの候補伝送時間は、別のノードにより公示される後続の伝送時間のリストを使って判定される。ノードは、可能な伝送時間リストから公示されている伝送時間を除外し、様々な入力サンプルに対して様々な（擬似乱数の）出力の分配を提供する関数を使って、そのノードの候補伝送時間を計算する。この関数は、ハッシュ関数であってもよいし、暗号関数やルックアップ関数であってもよい。公示伝送時間を獲得できないノードに対しては、候補伝送時間の計算に、それらのノードの識別子を利用する。
【発明を実施するための最良の形態】
【００３１】
以下、本発明の代表的な実施形態に関し、添付図面を参照しながら詳細に説明するが、この添付図面は、本発明の一部であり、本発明を実施する具体的な代表的実施形態を例示している。各実施形態は、当業者が本発明を実施できるよう詳しく説明しているが、本発明の精神又は範囲を逸脱することなく、他の実施形態を利用し、他の変更を加えることもできる旨理解頂きたい。従って、以下の詳細な説明は、限定を意図するものではなく、本発明の範囲は、特許請求の範囲に述べる事項によってのみ定義される。
【００３２】
明細書及び特許請求の範囲を通して、以下の用語は、文脈が明確に他を指していない限り、ここに明示的に関係付けられた意味を取る。図面に関しては、各図面を通して、類似の番号は類似の部分を指す。更に、別の様に述べておらず、或いはここに開示することと矛盾していない限り、単数での表現は複数の場合も含むものと理解されたい。
【００３３】
アドホック・ネットワーク内の伝送のスケジューリングに関するシステム及び方法について説明する。以下の説明では、本発明を完全に理解頂けるよう、数多くの具体的詳細事項について説明する。しかしながら、当業者には明らかなように、本発明を実施するのに、必ずしもこれら具体的詳細事項を使う必要はない。別の場合には、周知の構造及び回路は、本発明を不必要に不明確にするのを避けるため、詳細には示していない。
【００３４】
要するに、本発明は、局地近傍内のノードが再び伝送しようとするときに、ノードの局地近傍の構成状況とタイムスロットの公示に関して獲得している情報に基づいて、ノードに、無衝突伝送のためのタイムスロットが割り当てられるようにする、パケットをチャネル内へ無衝突伝送するための媒体アクセス制御（ＭＡＣ）プロトコルを提供することに取り組んでいる。
【００３５】
Ｉ．定義、基本的サービス及び前提
分かり易くするために、ラジオは何れの利用できるチャネルにでも切り換えることができるが、ネットワークに用いられているラジオは、半二重で、一時に１つのチャネルに同調するものとする。伝送スケジューリングに基づく先のＭＡＣプロトコルと同様に、本発明は、時間はスロットされ、スロットがフレームにグルーピングされると仮定している。フレームは更にエポックに編成される。しかしながら、ネットワーク内で用いられるラジオによっては、衝突回避に基づくプロトコル（例えばＩＥＥＥ８０２．１１）でさえ、時間はスロットされ、フレームに編成される必要がある。全てのラジオが、周波数ホップの開始時間及びホッピング・シーケンスの長さで合意しなければならないので、周波数ホッピングラジオの場合は、それに当たる。
【００３６】
本発明は、ノードが、多重データチャネル上で伝送スケジュールを確立するために用いられる制御パケット又はデータパケットを伝送することができるようにする、共通のチャネル上で同報通信伝送するためのタイムスロットの割り当てに焦点を合わせている。本発明は、近隣のノード間での双方向の物理的リンクを想定しており、これは、衝突回避ＭＡＣプロトコルの場合も真である。
【００３７】
本発明の或る実施形態では、タイムスロットは、フレーム内のタイムスロット位置とエポック内のフレーム位置を指定する固有の識別子を使って識別される。エポックは、時間同期化アルゴリズムによって、ノード間で同意した現在時間を使って識別することができる。本発明の説明では、スロットＩＤという用語は、ネットワークの「ネットワーク年齢」に基づくタイムスロットの識別子を指す。各エポックは、固定数のフレームを有しており、各フレームは固定数のタイムスロットを有している。
【００３８】
本発明で説明する方法を実行するノードは、インターネットラジオ（ＩＲ）と呼ばれている。本発明の説明では、「ノード」と「インターネットラジオ」を、互換性があるものとして使用している。
【００３９】
本発明の或る実施形態では、或るノードの各近隣は、送信器割り当て局所リンク識別子を使って、そのノードにより識別され、我々はそれをＸＬＩＤで示している。本発明のもう１つの実施形態では、ノードはそのＭＡＣアドレスによって識別することができる。ここに示す本発明の説明では、我々は、ノード識別子という用語を、単に、ＸＬＩＤ又はノードのＭＡＣアドレスを示すのに用いている。ＡＴＯＭは、両タイプのノード識別子で正しく作動する。各ノードは、アクティブな１ホップ近隣の最大数まで有することができる。アクティブな１ホップ近隣は、それぞれにノード識別子が割り当てられ、ノードは連続するノード識別子をアクティブな近隣に割り当てると仮定している。近隣へのノード識別子の割り当ては、本発明の範囲外の方法によって行われる。
【００４０】
図１は、本発明の態様による、本発明が作動する代表的なアドホック・ネットワークを示している。アドホック・ネットワークは、多数のサブネットワーク２０、３０、４０及び５０で構成されており、それらは、多数のＩＲ（１００、１１０、１２０、１３０、１４０、１５０、１６０、１７０及び１８０）を介してインターネットを拡張している。各ＩＲ１００−１８０は、ＩＰアドレス及びＭＡＣアドレスを有する無線ルータである。アドホック・ネットワーク２０は、アクセスポイントＩＲ１１０を経由してインターネット９００に接続されている。ＩＲ１１０は、ローカルエリアネットワーク４０を介してインターネットルータ２００に連結されている。
【００４１】
或る有限時間が経つと、アドホック・ネットワーク２０内の各ＩＲ（１００−１８０）は、ネットワーク内に存在しているＩＲに関する同一のリストを有する。つまり、ＩＲはその近隣に気付く。
【００４２】
本発明の１つの実施形態によれば、各ＩＲは、自分から所定のホップ数以内の、近傍を構成しているＩＲの固有のノードＩＤを学習する。例えば、ＩＲは、自分から１、２、３又はそれ以上のホップだけ離れている近隣を学習する。本発明の１つの実施形態によれば、ＩＲは、近隣発見及び管理プロトコルによって、多くの場合制御パケットと組み合わせて、その直接（１ホップ）の近隣の存在について学習する。２ホップ近隣及びノードから３ホップ以上離れたノードについては、制御パケットが学習する。
【００４３】
アドホック・ネットワーク全体のルーティング情報の通信には、異なるプロトコルを利用してもよい。
【００４４】
ＩＩ．交換及び保守される情報
図２は、本発明の態様によるＩＲのＡ−Ｅに割り当てられるタイムスロットの代表的フレームを示している。図示のように、タイムスロット２２０（ｓ０−ｓ１１）が、フレーム２３０内に示されている。１つのＩＲは、各タイムスロットに割り当てられる（２２０参照）。分かり易くするために、ＩＲのＡ−Ｆは、スロットｓ０−ｓ１１の順で配置されている。ＩＲのＡ−Ｆには、衝突を避けるようタイムスロットが割り当てられている。ネットワーク内のＩＲは、同期化され、「フレーム」と呼ばれる期間で合意し、その中でパケット（例えば制御パケット）がスケジュールされる。各フレームは、フレーム毎に変わる「ネットワーク年齢」（ネット年齢）と関係付けられており、ネットワーク中に知られている。例えば、ネットワークは、一定の整数のフレーム当りのスロット数（Ｓ）及び一定の整数のエポック当りのフレーム数（Ｆ）を有するエポック、フレーム及びスロットによって同期化される。各エポック内で、フレームには、１からＦまで連続して番号（「フレーム番号」）が付されている。エポックにも連続して番号が付されており、最後は、Ｅエポックの後でエポック番号１へラップバックする。上記ネットワーク年齢は、エポック番号と連結されているフレーム数か、又は、エポック内のフレーム数が十分多い場合は単にフレーム数か、の何れかである。
【００４５】
説明し易くするため、本発明では、ノード間で交換される制御パケットを「ネットワーク構成パケット」と呼んでいる。
【００４６】
本発明の１つの実施形態によれば、各ノードは、各エントリが以下のフィールドを含んでいる物理的近傍リストを保守している。
Ａｄｄｒｅｓｓ（アドレス）    ３２ビットＭＡＣアドレス
Ｄｉｓｔａｎｃｅ（距離）      現ノードからのこの近隣のホップ距離を示す。パケットが、この近隣から、最近、成功裏に受信されていれば、１ホップ離れていると考えられる。
ノード識別子  このノードを、ネットワーク構成パケット内で、更に効率的な方法で識別するのに用いられる番号（又は番号のセット）。
直接（１ホップ）近隣の場合、
ＮｂｒＩＤ番号が、このノードがこの近隣に割り当てた近隣番号を示す。
間接、２ホップ近隣の場合、
ＲｅｐＩＤ番号が、この２ホップ近隣を報告している近隣を示す。
ＲｅｐＮｂｒＩＤ  この２ホップ近隣ノードを識別するのに、直接（報告している）近隣によって使用されているＮｂｒＩＤ。
間接、３ホップ近隣（保守されていれば）の場合、
Ｒｅｐ  ＩＤ  この３ホップ近隣を報告している近隣を示す番号。
ＲｅｐＲｅｐＩＤ  この３ホップ近隣ノードに関し報告している近隣を識別するのに、報告している近隣によって使用されているＮｂｒＩＤ。
ＲｅｐＲｅｐＮｂｒＩＤ  この３ホップ近隣を識別するのに、直接近隣によって使用されているＮｂｒＩＤ。
ＸｍｔＨｏｌｄｏｆｆＴｉｍｅ（ホールドオフ時間）  このノードによるネットワーク構成パケット伝送の間の最小フレーム数。ノードは、このホールドオフ時間を増すことができ、増した数の報告を始めることができる。そのホールドオフ時間を減少させるには、減じた時間に切り換える前に旧ホールドオフ時間を使いながら、先ず、所与のフレーム数に関する新しいホールドオフ時間を公示しなければならない。
ＮｅｘｔＸｍｔＴｉｍｅ  このノードがネットワーク構成パケットを伝送しないよう保証された後のフレーム及びスロットの番号。これは、ＮＥＸＴ ＸＭＴ ＴＩＭＥ ＮＯＷへ初期設定される。年齢手順部分として、且つ、ロールオーバー問題を避けるために、このＮｅｘｔＸｍｔＴｉｍｅとノードのＸｍｔＨｏｌｄｏｆｆＴｉｍｅとの合計が現在時間と同じか、それよりも少なければ何時でも、このＮｅｘｔＸｍｔＴｉｍｅも、この値にリセットされる。
ＲｅｐｏｒｔｅｄＦｌａｇ（報告済みフラグ）  このＮｅｘｔＸｍｔＴｉｍｅが、ネットワーク構成パケット内のこのノードによって報告されていれば、ＴＲＵＥに設定し、報告されていなければＦＡＬＳＥに設定する。
【００４７】
ネットワーク構成パケットの内容
図９は、本発明の或る実施形態によるネットワーク構成パケットの内容を示している。
ＭａｎａｇｅｍｅｎｔＭｅｓｓａｇｅＴｙｐｅ９０１は、メッセージの型式を示している。
ＮｕｍＮｂｒＥｎｔｒｉｅｓ９０２は、メッセージで報告された近隣の数である。報告された近隣の数は、このノードに知らされた近隣のセット全体の一部になる。ノードは、後続の近隣のサブセットをその後続のネットワーク構成伝送で報告することができる。
ＮｕｍＢＳＥｎｔｒｉｅｓ９０３は、このメッセージで報告されたメッシュＢＳ近隣の数である。
ＥｍｂｅｄｄｅｄＰａｃｋｅｔＦｌａｇ９０４は、ネットワーク構成パケット内に埋め込まれたパケットがあるか否かを示す。
ＸｍｔＰｏｗｅｒ９０５は、２ｄＢｍ段階にあり、８ｄＢｍから開始する。（即ち、１１１１は３８ｄＢｍである）。
ＸｍｔＡｎｔｅｎｎａ９０６は、このメッセージの伝送に用いられる論理アンテナである。これは、８つまでのアンテナ方向をサポートする適応アンテナシステム（ＡＡＳ）を考慮している。
ＮｅｔＥｎｔｒｙＭＡＣＡｄｄｒｅｓｓＦｌａｇ９０７は、このエントリが存在するか否かを示している。
Ｎｅｔｗｏｒｋ  ｂａｓｅ  ｃｈａｎｎｅｌ９０８は、このノードのネットワークで用いられている基本チャネルであり、物理的チャネルの論理数であり、スケジュール制御情報を同報通信するのに用いられる。可能な物理的チャネル数のサブセットは、ネットワーク記述子内で論理チャネルにマップされる。
Ｒｅｓｅｒｖｅｄ  ｆｉｅｌｄ９０９は、予約される。
Ｎｅｔｃｏｎｆｉｇ  ｃｏｕｎｔ９１０は、このノードによって伝送されるネットワーク構成パケットのカウンターである。
【００４８】
Ｔｉｍｅｓｔａｍｐ９１１は、近隣によって、失敗した伝送を検知するのに用いられる。このカウントは、このノードによるネットワーク構成伝送毎に１だけ増やされる。同期ホップカウントは、ネットワークを同期化するときに、ノード間で優先順位を決定するのに用いられる。ノードは、マスタータイムキーパーとして割り当てることができ、それらを外部的に同期化される（例えばＧＰＳを使って）。これらのノードは、０の同期ホップカウントを伝送する。ノードは、より小さい同期ホップカウントを有するノードに同期するか、或いは、カウントが同じであれば、小さいノードＩＤを有するノードに同期する。
【００４９】
Ｎｅｔｃｏｎｆｉｇ  ｓｃｈｅｄｕｌｅ  ｉｎｆｏ９１２は、ＮｅｘｔＸｍｔＭｘ及びＸｍｔＨｏｌｄｏｆｆＥｘｐｏｎｅｎｔを記憶するのに用いられる。ＸｍｔＨｏｌｄｏｆｆＴｉｍｅは、ＮｅｘｔＸｍｔＴｉｍｅ後のネットワーク構成伝送機会の数である（ネットワーク制御サブフレーム当り１機会の、このノードがネットワーク構成パケットを伝送しない資格がないネットワーク構成がある）。
【００５０】
ＸｍｔＨｏｌｄｏｆｆＴｉｍｅ＝２(XmtHoldoffExponent+4)  次のＸｍｔＭｘは、この近隣に対する次のネットワーク構成適格性の間隔であり、範囲２XmtHoldoffExponent*ＮｅｘｔＸｍｔＭｘ＜ＮｅｘｔＸｍｔＴｉｍｅ＜２XmtHoldoffExponent*（ＮｅｘｔＸｍｔＭｘ＋１）として計算されるＮｅｘｔＸｍｔＴｉｍｅを含んでいる。
【００５１】
例えば、ＮｅｘｔＸｍｔＭｘ＝３で、ＸｍｔＨｏｌｄｏｆｆＥｘｐｏｎｅｎｔ＝４の場合、ノードは、（細分性により）４９と６４の伝送機会の間で、次のネットワーク構成伝送に関して資格があり、それまでは資格がないと考えられる。ＮｅｘｔＸｍｔＭｘフィールドがＯｘ１Ｆ（全て）に設定されると、近隣は、この値で示される時間から、そしてその後のネットワーク構成機会毎に伝送する資格があると考えられる（即ち、ＸｍｔＨｏｌｄｏｆｆＴｉｍｅ＝０と扱う）。
【００５２】
ＮｅｔＥｎｔｒｙＭＡＣ  Ａｄｄｒｅｓｓ９１３は、新しいノードの存在又は発起を示す。ＢＳノードＩＤは、報告されているメッシュＢＳノードのノードＩＤである。
Ｎｕｍｂｅｒ  ｏｆ  ｈｏｐｓ（ホップ数）９１４は、報告しているノードと報告されているメッシュＢＳノードの間のホップ数である。
【００５３】
Ｘｍｔ  ｅｎｅｒｇｙ／ｂｉｔ（エネルギー／ビット）９１５因子は、このノードを通ってメッシュＢＳに到達するのに必要なエネルギー／ビットを示している。Ｘｍｔエネルギー／ビットは、Ｅj＝ｍｉｎ／Ｊ∈Ｎj* [Ｅj>i＋Ｅj] ｍＷ*μｓとして計算され、ここに、ＮはメッシュＢＳを報告している近隣のセットであり、Ｅi・>j＝ＰTx／Ｒi・>jであり、ここに、ＰTxは、ノードｉからノードｊへの伝送電力のｍＷ数であり、Ｒi・>jはノードｉからノードｊへのデータ転送速度のＭｂｐｓ表示である。Ｅjは、近隣ｊによって報告されたＸｍｔエネルギー／ビットである。報告されたＸｍｔエネルギー／ビット因子は、計算されたＸｍｔエネルギー／ビットを２(XmtEnergyUnitExponent-4)で割ったものである。ＸｍｔＥｎｅｒｇｙＵｎｉｔＥｘｐｏｎｅｎｔは、ネットワーク記述子で報告された４ビットフィールドである。ＮｂｒノードＩＤ９１６は、報告された近隣ノードのノードＩＤである。
【００５４】
本発明のもう１つの実施形態によれば、ネットワーク構成パケットは、以下の情報を含んでいる。
【００５５】
ＭｙＭＡＣＡｄｒ  ３２ビットのＭＡＣアドレス（Ｔ同期ヘッダーの一部として）
ＮｅｘｔＸｍｔＴｉｍｅ  ＭｙＮｅｘｔＸｍｔＴｉｍｅ
ＸｍｔＨｏｌｄｏｆｆＴｉｍｅ  ＭｙＸｍｔＨｏｌｄｏｆｆＴｉｍｅ
【００５６】
各ネットワーク構成パケットは、以下のフィールドを有するエントリのリスト（長さＹ、ＴＢＤ）も含んでいる。本発明の１つの実施形態によれば、このリストは、ノードの１ホップ近隣から（３ホップスケジューリングモードであれば、２ホップ近隣の中からも）ラウンドロビン方式で選択される。リストは、他の方式で選択してもよい。
【００５７】
ＮｂｒＭＡＣＡｄｒ  ３２ビットのＭＡＣアドレス
Ｄｉｓｔａｎｃｅ  １ホップ（直接）近隣又は２ホップ近隣
Ｎｏｄｅ  Ｉｄｅｎｔｉｆｉｅｒ  （ＮｂｒＩＤ）又は（ＮｂｒＩＤ及びＲｅｐＩＤ）
ＮｅｘｔＸｍｔＴｉｍｅ
ＸｍｔＨｏｌｄｏｆｆＴｉｍｅ
【００５８】
更に、各ネットワーク構成パケットは、以下の圧縮されたフィールドを有するエントリのリスト（長さＺ、ＴＢＤ）も含んでいる。
【００５９】
Ｄｉｓｔａｎｃｅ  １ホップ（直接）近隣又は２ホップ近隣
Ｎｏｄｅ  Ｉｄｅｎｔｉｆｉｅｒ  （ＮｂｒＩＤ）又は（ＮｂｒＩＤ及びＲｅｐＩＤ）
ＮｅｘｔＸｍｔＴｉｍｅ
ＸｍｔＨｏｌｄｏｆｆＴｉｍｅ
【００６０】
図３は、物理的近隣のリストを選択して、ネットワーク構成パケットの圧縮された近隣区画で報告するのに用いられる手順を示している。開始ブロックの後で、論理は、ブロック３１０へ進み、そこで、上記ラウンドロビンリストで報告された近隣は除外される。ブロック３２０へ進み、２ホップスケジューリングモードで作動している場合、全ての３ホップ近隣エントリは除外される。次に、ブロック３３０で、「報告済みフラグ」のセットを有する全ての近隣エントリが除外される。ブロック３４０へ移行する際、残っている近隣エントリは、ＮｅｘｔＸｍｔＴｉｍｅによって順序付けされ、将来で最も遠いＮｅｘｔＸｍｔＴｉｍｅを有するＺエントリが、このネットワーク構成パケットで報告される。一般的に、近隣は、情報が古くなるまでにこの情報を利用するのに多くの時間を有しているので、将来へ最も遠いＮｅｘｔＸｍｔＴｉｍｅを有するノードの学習は、まもなく近づくＮｅｘｔＸｍｔＴｉｍｅを有するノードの学習よりも価値がある。ブロック３５０に進み、上記リストの何れかの全近隣に関する「報告済みフラグ」は、このネットワーク構成パケットの伝送で、ＴＲＵＥ（真）に設定される。次に、プロセスは終了ブロックへ進み、別の動作の処理に戻る。
【００６１】
ＩＩＩ．伝送スケジューリング
図４は、本発明の態様による伝送スケジューリングの手順を示している。ノードの現在の伝送（「Ｘｍｔ」）時間の間（即ち、ノードがそのネットワーク構成パケットを伝送するときのタイムスロット）に、ノードは、以下の手順を使って、そのＮｅｘｔＸｍｔＴｉｍｅを決定する。
【００６２】
開始ブロックの後、論理は、ブロック４１０へ進み、そこで、次回伝送時間に関し物理的近隣表が順序付けされる。ブロック４２０へ進み、近隣表の各エントリ毎に、ノードのＮｅｘｔＸｍｔＴｉｍｅが、ノードのＴｒａｎｓｍｉｔＨｏｌｄｏｆｆＴｉｍｅに加えられ、ノードのＥａｒｌｉｅｓｔＳｕｂｓｅｑｕｅｎｔ  ｔｒａｎｓｍｉｔＸｍｔＴｉｍｅ（最早次回伝送ＸｍｔＴｉｍｅ）に達する。ブロック４３０へ移り、プロセスは、ＴｅｍｐＸｍｔＴｉｍｅが、ノードの公示ＸｍｔＨｏｌｄｏｆｆＴｉｍｅを現在のＸｍｔＴｉｍｅに加えたものに等しいと設定する。ブロック４４０で、成功フラグが偽に等しいと設定される。決定ブロック４５０で、成功フラグが何時偽となったかについて判定が行われる。間違いなく偽である場合、プロセスはブロック４５５へ進み、そこでＴｅｍｐＸｍｔＴｉｍｅが、物理的近隣リスト内の何れかのノードのＮｅｘｔＸｍｔＴｉｍｅと等しければ、プロセスは、ＴｅｍｐＸｍｔＴｉｍｅを次のネットワーク構成フレーム／スロットに等しいと設定する。そうでない場合、プロセスはブロック４６０へ進み、そこで、プロセスは、ＴｅｍｐＸｍｔＴｉｍｅと等しいか又はそれより小さいＥａｒｌｉｅｓｔＳｕｂｓｅｑｕｅｎｔＸｍｔＴｉｍｅを有する、物理的近隣リスト内の全ノードのセットである有資格競合ノードを判定する。ブロック４６５で、ＴｅｍｐＸｍｔＴｉｍｅを、全ての有資格競合ノードのシード及びＭＡＣアドレスとして使って、この有資格競合ノードのセットの間で、近傍選定が行われる。決定ブロック４７０へ進み、ノードが選定されるかどうかについて判定が行われる。このノードが近傍選定に勝利しなければ、プロセスはブロック４７５へ進み、そこで、ＴｅｍｐＸｍｔＴｉｍｅが次のネットワーク構成フレーム／スロットに等しいと設定される。そうでない場合、プロセスは、ブロック４８０で成功を真に等しいと設定し、プロセスはブロック４８５へ進み、そこで、ノードのＮｅｘｔＸｍｔＴｉｍｅがＴｅｍｐＸｍｔＴｉｍｅに等しいと設定される。
【００６３】
本発明の１つの実施形態では、上記手順で実施される近傍選定は、ＲＥＡＬＭプロトコルで実施される選定と同じである（同時係属出願第０９／２４８，７３８号「無線ネットワークのための適応通信プロトコル」１９９９年２月１０日出願）。
【００６４】
図５は、本発明の態様による基本的な近傍選定のためのプロセスを示している。開始ブロックの後、プロセスは、ブロック５１０へ進み、そこで各ノード（ｉ）は、各フレーム内で、ネットワーク年齢とノードＩＤを入力として受け入れる大域周知機能（ＳｌｏｔＦｕｎｃ）を使って、その候補伝送スロット（ＣＳ（ｉ））を計算する。これは、ＣＳ（ｉ）＝ＳｌｏｔＦｕｎｃ（ＩＤ（ｉ）、ＮｅｔＡｇｅ）と表すことができる。
【００６５】
ブロック５２０へ移ると、各ノードは、その２ホップ近傍内のノード（ｊ）それぞれの候補伝送スロットを、それらのノードＩＤ、大域周知ネットワーク年齢、及び同じＳｌｏｔＦｕｎｃ関数（ＣＳ（ｊ）＝ＳｌｏｔＦｕｎｃ（ＩＤ（ｊ）、ＮｅｔＡｇｅ）を使って計算する。
【００６６】
勿論、各ノードのＣＳ（ｋ）は、どのノード（局所ノード、又はその２ホップ近傍内のノードの１つ）が計算していようと同じ結果を提供するであろう。従って、各ノードは、もし有れば、２ホップ近傍内のどのノードが同じ候補伝送スロットを共有しているかを判定することができる。これらのノードのＩＤは、ＣＧ（ｉ）＝（ｊ：ＣＳ（ｉ）＝ＣＳ（ｊ））に従って、このフレームに関するノードｉの対抗者グループ（ＣＧ（ｉ））内に配置される。
【００６７】
ブロック５３０へ進み、各ノード（ｉ）は、その対抗者グループ内の各ノードの優先度ＰＲ（ｊ）を計算し、これら対抗者の中でどのノードがこのフレームに対して優先権を有しているかを、大域周知優先権関数（ＰｒｉｏｒｉｔｙＦｕｎｃ）への入力としてノードＩＤ、スケジューリングフレーム番号及び随意的にノードの優先バイアスを使って判定する。これは、ＰＲ（ｊ）＝ＰｒｉｏｒｉｔｙＦｕｎｃ（ＩＤ（ｉ）、ＮｅｔＡｇｅ）＋ＰＢ（ｊ）と表せる。ＰｒｉｏｒｉｔｙＦｕｎｃ（ａ，ｂ）は、各可能性のある入力「ａ」毎に固有の数となる。優先バイアスが使用されなければ、ＰＢ（ｊ）は０に設定される。
【００６８】
次に、ブロック５４０で、ノード（ｉ）は、ＰＲ（ｉ）が対抗者グループ内の何れのＰＲ（ｊ）よりも大きい場合、或いは、ＰＲ（ｉ）が最大のＰＲ（ｊ）と互角である場合は、自身を競合の勝者と考え、全優先バイアスのＰＢ（ｊ）が０となって最大となる。
【００６９】
ノード（ｉ）は、その対抗者グループの勝者である場合、及びそのＰＲ（ｉ）が優先権閾値委譲である場合は、現在のフレーム内の候補伝送スロットＣＳ（ｉ）で伝送することができる。
【００７０】
次にプロセスは最終ブロックへ進み、別の動作の処理に戻る。
【００７１】
図６は、本発明の態様によるネットワーク構成伝送手順を示している。現ノードのＮｅｘｔＸｍｔＴｉｍｅに到達すると、システムは、図６に示している手順を実行する。
【００７２】
開始ブロックの後、プロセスはブロック６１０へ進み、そこでプロセスは、Ｘｍｔ＿ＳｃｈｅｄｕｌｉｎｇＰｒｏｃｅｄｕｒｅを使ってノードのＮｅｘｔＸｍｔＴｉｍｅを決める。ブロック６１５へ進んで、プロセスは、そのＮｅｘｔＨｏｌｄｏｆｆＴｉｍｅ（その物理的近隣表のサイズに基づく関数で、上記のように低減を如何に取り扱うかに関する制約がある）を決める。ブロック６２０へ進み、「ＳＫＩＰ  ＴＨＩＳ  ＮＥＴＷＯＲＫ  ＣＯＮＦＩＧＵＲＡＴＩＯＮ  ＴＲＡＮＳＭＩＴ」フラグが設定されるか否か判定が行われる。フラグが設定されると、プロセスは残りの段階を飛び越え、最終ブロックへ進み、そこでプロセスは戻って別の動作を処理する。ブロック６２５へ進むと、プロセスは、ネットワーク構成パケットを（上記のように）作る。次に、ブロック６３０で、プロセスは、ラウンドロビンリスト又は圧縮されたリストで報告されている全近隣エントリに対し「報告済みフラグ」を真に設定する。ブロック６３５で、ネットワーク構成パケットは、適切なフレーム／スロット境界で伝送される。
【００７３】
図７は、本発明の様態による、ネットワーク構成パケットが近隣から受信されるときのプロセスを示している。開始ブロックの後、プロセスはブロック７１０へ進み、そこで必要ならば伝送ノードの距離が１ホップ（直接）に更新される。ブロック７２０へ進み、近隣を通り最小のホップ数で到達する各報告済みノード毎に、報告済みノードまでの距離が更新され、報告されているものに１が加えられる。ブロック７３０へ移り、伝送中のノード及び報告済みの全ノードのＮｅｘｔＸｍｔＴｉｍｅ及びＸｍｔＨｏｌｄｏｆｆＴｉｍｅが更新される。ブロック７４０へ進み、何れかの報告済み近隣が、現ノードのＮｅｘｔＸｍｔＴｉｍｅと等しいＮｅｘｔＸｍｔＴｉｍｅを有していると分かった場合は、「ＳＫＩＰ  ＴＨＩＳ  ＮＥＴＷＯＲＫ  ＣＯＮＦＩＧＵＲＡＲＩＯＮ  ＴＲＡＮＳＭＩＴ」フラグが設定される（上記で用いられている）。これは、チャネルのダイナミックス又は可動性によるトポロジー変化を有する過渡状態として起こることがある。次に、ブロック７５０で、圧縮された近隣リスト内で報告されている何れのノードに対するノード識別子も、物理的近隣表内の情報を使って、近隣エントリ（ＭＡＣアドレスを有する）に解明できなければ、このエントリを飛ばす。
【００７４】
図８は、本発明の態様によるＰｈｙｓｉｃａｌＮｅｉｇｈｂｏｒＡｇｉｎｇのプロセスを示している。この手順は、定期的に、物理的近隣リスト上で作動している。開始ブロックの後、プロセスはブロック８１０へ進み、そこで、ＮｅｘｔＸｍｔＴｉｍｅプラス現在時間以下のＸｍｔＪｏｌｄｏｆｆＴｉｍｅを有するあらゆる近隣に対して、ＮｅｘｔＸｍｔＴｉｍｅが、ＮＥＸＴ＿ＸＭＴ  ＴＩＭＥ  ＮＯＷに設定される。ブロック８２０へ進み、エントリのＡｇｉｎｇＴｉｍｅは、現在にリセットされる。ブロック８３０へ進み、ＮＥＸＴ  ＸＭＴ  ＴＩＭＥ  ＮＯＷ及び過去の或る（ＴＢＤ）時間と等しいＡｇｉｎｇＴｉｍｅを有するあらゆる近隣に対し、その近隣までの距離が１だけ増やされる。ブロック８４０へ移る際に、この増加によって距離が３ホップ（３ホップスケジューリングでは４ホップ）になる場合は、その近隣のエントリが取り除かれる。そうでない場合、プロセスはブロック８５０へ進み、そこで近隣のエントリのＡｇｉｎｇＴｉｍｅは、再び現在にリセットされる。
【００７５】
圧縮方法
ＮｅｘｔＸｍｔＴｉｍｅは、ネットワーク構成パケット内で、幾つかの全体的ブロック境界（各ブロックは、多数のネットワーク構成伝送機会を含んでいる）に丸められたＮｅｘｔＸｍｔＴｉｍｅを与える３−４ビットに圧縮される。ＸｍｔＨｏｌｄｏｆｆＴｉｍｅは、式：ＸｍｔＨｏｌｄｏｆｆＴｉｍｅ＝２(x+4)を使って、１６から２０４８までの範囲のフレーム／スロットを有する多分３ビットに量子化される。
【００７６】
上記仕様、例及びデータは、本発明の構造の製作及び利用について、完璧に説明している。本発明の多くの実施形態は、本発明の精神及び範囲から逸脱することなく作ることができるので、本発明は特許請求の範囲に記載することに存する。
【図面の簡単な説明】
【００７７】
【図１】本発明が作動するアドホックネットワークを示している。
【図２】ＩＲのＡ−Ｅに割り当てられたタイムスロットの代表的なフレームを示している。
【図３】物理的近隣のリストを選択し、ネットワーク構成パケットの圧縮された近隣区画内で報告するのに用いられる手順を示している。
【図４】伝送スケジューリング用の手順を示している。
【図５】基本的近傍選定のためのプロセスを示している。
【図６】ネットワーク構成の伝送手順を示している。
【図７】近隣からネットワーク構成パケットを受信するときのプロセスを示している。
【図８】物理的近隣エージングのためのプロセスを示している。
【図９】本発明の態様による、ネットワーク構成パケットの内容を示している。
【図１】
2005501466.tif 000002
【図３】
2005501466.tif 000003
【図４】
2005501466.tif 000004
【図５】
2005501466.tif 000005
【図６】
2005501466.tif 000006
【図７】
2005501466.tif 000007
【図８】
2005501466.tif 000008
【国際公開パンフレット】
2005501466.tif 000009
2005501466.tif 000010
2005501466.tif 000011
2005501466.tif 000012
2005501466.tif 000013
2005501466.tif 000014
2005501466.tif 000015
2005501466.tif 000016
2005501466.tif 000017
2005501466.tif 000018
2005501466.tif 000019
2005501466.tif 000020
2005501466.tif 000021
2005501466.tif 000022
2005501466.tif 000023
2005501466.tif 000024
2005501466.tif 000025
2005501466.tif 000026
2005501466.tif 000027
2005501466.tif 000028
2005501466.tif 000029
2005501466.tif 000030
2005501466.tif 000031
2005501466.tif 000032
2005501466.tif 000033
2005501466.tif 000034
2005501466.tif 000035
2005501466.tif 000036
2005501466.tif 000037
2005501466.tif 000038
2005501466.tif 000039
2005501466.tif 000040
2005501466.tif 000041
2005501466.tif 000042
2005501466.tif 000043
2005501466.tif 000044
2005501466.tif 000045
【国際公開パンフレット（コレクトバージョン）】
2005501466.tif 000046
【国際調査報告】
2005501466.tif 000047
2005501466.tif 000048