(57)【要約】本発明は、動的スケジューリングまたはルーティングを行わずに無線ネットワーク内のトラフィック変化に対処するためのリンク送信スケジュールを生成する方法および装置を含む。この方法は、無線ネットワークのそれぞれの無線リンクに関連する固定トラフィック容量をルーティング・アルゴリズムに従って決定するステップと、ルーティング・アルゴリズムおよび固定トラフィック容量を使用して、ネットワーク・リンクのそれぞれを使用してトラフィックが送信される少なくとも１つの条件を含むリンク送信スケジュールを生成するステップとを含む。リンク送信スケジュールは、動的トラフィック変化の間、実質的に固定されたままであるように適応される。ルーティング・アルゴリズムは、トラフィックが無線ネットワーク内の各ノードによってトラフィック分割比を使用して無線ネットワーク内のあらゆるノードに分配される、２段階ルーティング・アルゴリズムであってもよい。２段階ルーティングでは、固定トラフィック容量が、入口および出口トラフィック容量、および無線ネットワーク内のそれぞれのノードに関連するトラフィック分割比を使用して決定されてもよい。
2009532940.tif 000002
【特許請求の範囲】
【請求項１】
リンク送信スケジュールを生成する方法であって、
複数の各無線リンクのそれぞれに関連する固定トラフィック容量をルーティング・アルゴリズムに従って決定するステップと、
前記ルーティング・アルゴリズムおよび前記決定された固定トラフィック容量を使用して、前記無線リンクのそれぞれを使用してトラフィックが送信される少なくとも１つの条件を含む前記リンク送信スケジューリングを生成するステップとを含み、前記リンク送信スケジュールが、動的トラフィック変化の間、実質的に固定されたままであるように適応される、方法。
【請求項２】
前記固定トラフィック容量を決定するステップが、
前記それぞれのネットワーク・リンクの前記固定トラフィック容量を確立するように前記ルーティング・アルゴリズムを構成するように適応された少なくとも１つのルーティング・パラメータを決定するステップを含む、請求項１に記載の方法。
【請求項３】
前記少なくとも１つのルーティング・パラメータが、少なくとも１つのスケジューリング制約を満たすやり方で決定される、請求項２に記載の方法。
【請求項４】
前記ルーティング・アルゴリズムが、
複数のノードのそれぞれがトラフィックを複数の各トラフィック分割比に従って前記ノードのそれぞれに分配する第１の段階と、
前記ノードのそれぞれが前記第１段階の間に受信されたトラフィックを、前記トラフィックの宛先ノードを含む前記ノードの選択されたノードにルーティングする第２の段階とを含む２段階ルーティング・アルゴリズムであり、
前記少なくとも１つのルーティング・パラメータを決定するステップが、前記ノードのそれぞれに関連する前記各トラフィック分割比を決定するステップを含む、請求項２に記載の方法。
【請求項５】
前記固定トラフィック容量を決定するステップが、
各ノードに関連する入口トラフィック容量を決定するステップと、
各ノードに関連する出口トラフィック容量を決定するステップと、
各ノードに関連する複数のトラフィック分割比を決定するステップと、
前記入口トラフィック容量、前記出口トラフィック容量および前記トラフィック分割比を使用して前記固定トラフィック容量を決定するステップとを含む、請求項１に記載の方法。
【請求項６】
リンク送信スケジュールを生成する装置であって、
複数の各無線リンクのそれぞれに関連する固定トラフィック容量をルーティング・アルゴリズムに従って決定する手段と、
前記ルーティング・アルゴリズムおよび前記決定された固定トラフィック容量を使用して、前記無線リンクのそれぞれを使用してトラフィックが送信される少なくとも１つの条件を含む前記リンク送信スケジューリングを生成する手段とを含み、
前記リンク送信スケジュールが、動的トラフィック変化の間、実質的に固定されたままであるように適応される、装置。
【請求項７】
前記固定トラフィック容量を決定する前記手段が、
前記それぞれのネットワーク・リンクの前記固定トラフィック容量を確立するように前記ルーティング・アルゴリズムを構成するように適応された少なくとも１つのルーティング・パラメータを決定する手段を含む、請求項６に記載の装置。
【請求項８】
前記少なくとも１つのルーティング・パラメータが、少なくとも１つのスケジューリング制約を満たすやり方で決定される、請求項７に記載の装置。
【請求項９】
固定トラフィック容量を決定する前記手段が、
各ノードに関連する入口トラフィック容量を決定する手段と、
各ノードに関連する出口トラフィック容量を決定する手段と、
各ノードに関連する複数のトラフィック分割比を決定する手段と、
前記入口トラフィック容量、前記出口トラフィック容量および前記トラフィック分割比を使用して前記固定トラフィック容量を決定する手段とを含む、請求項６に記載の装置。
【請求項１０】
ルーティング・アルゴリズム、および複数の各ネットワーク・リンクに関連する複数の固定トラフィック容量を使用して決定されたリンク送信スケジュールを受信するステップであって、前記リンク送信スケジュールが、前記ネットワーク・リンクのそれぞれを介してトラフィックが送信される少なくとも１つの条件を定義し、前記リンク送信スケジュールが、動的トラフィック変化の間、実質的に固定されたままであるように適応される、ステップと、
前記ルーティング・アルゴリズムおよび前記リンク送信スケジュールを使用して前記ネットワーク・リンクを介してトラフィックを送信するステップとを含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワークの分野に関し、より詳細には、無線ネットワーク内のルーティングおよびスケジューリングに関する。
【背景技術】
【０００２】
コミュニティ無線ネットワーク、および迅速な配置を必要とするネットワークなどの新しい応用のため、ならびに従来の無線ネットワークのサービスエリアおよび容量を増加させるため、無線メッシュ・ネットワーク（ＷＭＮ：ｗｉｒｅｌｅｓｓ  ｍｅｓｈ  ｎｅｔｗｏｒｋ）を使用することへの関心が高まっている。ＷＭＮへの関心の高まりは主として、有線基盤のサポートの必要性が減少したこと、ならびに無線コンポーネントの価格が低下したことによる。しかし、不都合な点として、動作面では有線バックボーン・ネットワークに類似しているとはいえ、ＷＭＮ内で無線リンクを使用すると、システムからの十分なスループットをもたらすこと、エンドユーザへのサービス品質の保証、および多数のノードへのネットワークのスケーリングなど、いくつかの特有の課題が生じる。こうした課題に対処するための様々な手法が試みられてきた。
【０００３】
一手法では、物理層の改良（たとえば多重チャネル、時空間符号化を用いた多重アンテナ、および干渉を最小限に抑えるための指向性アンテナの使用）が、ＷＭＮのスループットを向上させるために実施される。既存の別の手法では、マルチホップ・ネットワーク内では標準の単一ホップ・メディア・アクセス制御（ＭＡＣ：ｍｅｄｉａ  ａｃｃｅｓｓ  ｃｏｎｔｒｏｌ）がうまく働かないので、既存のＭＡＣ層が設計変更され、新しいＭＡＣ層（たとえば、基礎となる物理層に合わせたＭＡＣ層）が提案されている。別の既存の手法では、アドホック・モバイル・ネットワーク用に開発されたプロトコル（たとえば、リンク品質ベースのルーティング・プロトコルなどのルーティング・プロトコル、および新しいＴＣＰ変形物などのネットワーク・プロトコル）が、プロトコルをＷＮＭ内で使用するのに適したものにしようとして縮小されてきた（ｐａｒｅ  ｄｏｗｎ）。
【０００４】
物理層データ・レート増加の達成への既存手法の一部の進歩にも拘らず、ＭＡＣ層およびルーティング・プロトコルのさらなる制限のせいで、マルチホップ無線ネットワーク内の物理層データ・レートの増加は、アプリケーション層のスループットの増加につながっていない。さらに、ＭＡＣ層およびルーティング・プロトコルのこうした非効率性は、トラフィックがソースと宛先の間で複数ホップを横断しなければならない中規模ネットワーク内で悪化することがある。したがって、ＷＭＮのネットワーク・スループットの一部の小さい向上は、動的なルーティングおよびスケジューリングを使用する既存のプロセスによって達成され得るが、こうしたスループット向上は、幅広く採用されているＷＭＮをサポートするには不十分である。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
動的スケジューリングまたはルーティングを行わずに無線ネットワーク内のトラフィック変化に対処するためのリンク送信スケジュールを生成する方法および装置を提供する。
【課題を解決するための手段】
【０００６】
従来技術の様々な欠点は、リンク送信スケジュールを生成するための本発明の方法および装置によって対処される。この方法は、ルーティング・アルゴリズムに従って無線ネットワークの複数の各ネットワーク・リンクに関連する複数の固定トラフィック容量を決定するステップと、ルーティング・アルゴリズムおよび固定トラフィック容量を使用して、ネットワーク・リンクのそれぞれを使用してトラフィックが送信される少なくとも１つの条件を含むリンク送信スケジュールを生成するステップとを含む。リンク送信スケジュールは、トラフィック変化の間、実質的に固定のままであるように適応される。ルーティング・アルゴリズムは、無線ネットワーク内の各ノードによってトラフィック分割比に従って無線ネットワーク内のあらゆるノードに分配される２段階ルーティング・アルゴリズムを含んでもよい。２段階ルーティング・アルゴリズムを使用した無線ネットワークでは、固定トラフィック容量は、無線ネットワーク内の各ノードに関連する入口および出口トラフィック容量、ならびにトラフィック分割比を使用して決定されてもよい。
【０００７】
本発明の教示は、以下の詳細な説明を、添付の図面と併せて考慮することによって容易に理解することができる。
【０００８】
理解を促すため、同一の参照番号が、諸図に共通の同一の要素を指定するため、可能であれば使用されている。
【発明を実施するための最良の形態】
【０００９】
本発明は、ネットワーク制御を単純にし、固定の動的リソース割当てを回避することによって無線メッシュ・ネットワークのネットワーク・スループットを向上させる。本発明は、無線メッシュ・ネットワーク内で可変のトラフィックを効率的にサポートするために固定リンク送信スケジュールを使用した静的ルーティングを可能にする。固定リンク送信スケジュールを使用した静的ルーティングは、複雑な動的ネットワーク制御（たとえば動的ルーティング、動的リンク送信スケジューリング、動的メディア・アクセス制御など）を不要にし、それによって、無線メッシュ・ネットワーク内のネットワーク制御を単純にする。固定リンク送信スケジュールを使用した静的ルーティングは、それぞれの無線ノードに、トラフィック行列変化から独立した固定の長期的なスループットを保証する。
【００１０】
本発明は、無線ネットワーク内の無線ノードがルーティング・アルゴリズムを使用してトラフィックを送信するための固定のリンク送信スケジュールを決定する。ルーティング・アルゴリズムは、無線ネットワークのそれぞれのネットワーク・リンク上の固定トラフィック容量を確立するように構成される。ネットワーク内の実際のトラフィック・フローが変化し得るので、固定トラフィック容量は、平均の固定トラフィック容量である（すなわち、各ネットワーク・リンク上の平均トラフィック容量は固定である）。固定リンク送信スケジュールは、ルーティング・アルゴリズム、および関連の固定トラフィック容量を使用し決定される。ルーティング・アルゴリズムは、リンク送信スケジュールの決定に必要な固定トラフィック容量を決定するために処理されてもよい。それぞれのネットワーク・リンクに関連する固定トラフィック容量を保証することによって、本発明は、無線ネットワーク内の静的ルーティングおよびリンク送信スケジューリングを可能にし、それによって、ネットワーク制御を単純にし、ネットワーク・スループットを向上させる。
【００１１】
一実施形態では、無線メッシュ・ネットワーク内のトラフィック・ルーティングは、２段階ルーティング・アルゴリズムを使用して実施されてもよい。この実施形態では、トラフィックは、第１の送信段階で、トラフィック分割比に従ってソース・ノードから中間ノードに分配され、第２の段階でトラフィックは、中間ノードから、関連する宛先ノードにルーティングされる。この実施形態では、各無線ノードに関連する入口トラフィックおよび出口トラフィックを使用して、トラフィック分割比が、第１の送信段階で各無線ノードについて決定されてもよく、このトラフィック分割比は、それが無線メッシュ・ネットワークに適用されるとき、無線メッシュ・ネットワーク内の各ネットワーク・リンク上の固定トラフィック容量をもたらす。一実施形態では、トラフィック分割比は、少なくとも１つのリンク送信スケジューリング制約を満たすためのルーティング・アルゴリズム定式化を解くことによって決定されてもよい。
【００１２】
固定リンク送信スケジュールは、ルーティング・アルゴリズムおよび固定トラフィック容量から決定される。一実施形態では、固定リンク送信スケジュールは、辺彩色アルゴリズムを使用して決定されてもよい。固定リンク送信スケジュールは、無線メッシュ・ネットワークを介してトラフィックをルーティングするためのルーティング・アルゴリズムと併せて使用するために無線ノードに通信される。ルーティング・アルゴリズムは静的であり、それによって、ネットワーク状態に応答した動的ルーティング変更を実施するどんな必要性も取り除く。リンク送信スケジュールは静的であり、それによって、ネットワーク状態、リンク送信スケジューリング制約などに応答したリンク送信スケジューリング変更を実施するどんな必要性も取り除く。
【００１３】
図１は、通信ネットワークのハイレベル・ブロック図を示している。具体的には、図１の通信ネットワーク１００は、無線メッシュ・ネットワーク（ＷＭＮ）１０２と管理システム１２０とを含む。図１に示されるように、ＷＭＮ  １０２は、複数のノード１１０（まとめてノード１１０）と、複数の端末１１２（まとめて端末１１２）とを含む。図１に示されるように、ＷＭＮ  １０２は、任意の無線通信技術（たとえば、時分割多元接続（ＴＤＭＡ：Ｔｉｍｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）、符号分割多元接続（ＣＤＭＡ：Ｃｏｄｅ  Ｄｉｖｉｓｉｏｎ  Ｍｕｌｔｉｐｌｅ  Ａｃｃｅｓｓ）など、ならびにその様々な組合せ）を使用して実装されてもよい。
【００１４】
図１に示されるように、ノード１１０は、複数のネットワーク・リンク（ＮＬ：ｎｅｔｗｏｒｋ  ｌｉｎｋ）１１１（まとめてＮＬ  １１１）を使用して通信する。図１に示されるように、端末１１２は、複数の各アクセス・リンク（ＡＬ：ａｃｃｅｓｓ  ｌｉｎｋ）１１３（まとめてＡＬ  １１３）を使用してノード１１０と通信する。ＮＬ  １１１は、無線リンクを含む。ＡＬ  １１３は、有線リンクを含むことも、無線リンクを含むこともある。分かりやすくするために、リンク（図例ではＮＬ  １１１およびＡＬ  １１３）は、本明細書では単一の接続として示されているが、しかし、それぞれのリンクは、一対の指向性リンクとして物理的に実装されてもよい。たとえば、本明細書では単一の接続として示されているが、それぞれのＮＬ  １１１は、１対の有向無線リンク（たとえば別の無線ノードへの無線リンク、および別の無線ノードからの無線リンク）を含んでもよい。同様に、それぞれのＡＬ  １１３は、１対のリンクを含んでもよい。
【００１５】
ノード１１０は、無線通信をサポートするように動作可能な無線ノードを含む。ノード１１０は、パケット・ベースの通信をサポートし、またルーティング、チャネル割当て、および類似の機能、ならびにその様々な組合せを実施するように動作可能である。ノード１１０は、ＮＬ  １１１の上の固定トラフィックを保証するように適応されたルーティング・アルゴリズムを実装する。一実施形態では、ノード１１０は、固定ノードを含む。一実施形態では、ノード１１０の少なくとも一部は、モバイル・ノードを含む。ノード１１０は、少なくとも１つのアンテナ（分かりやすくするために省略）を含む。アンテナは、狭ビーム形成アンテナ、全方向性アンテナなどを含んでもよい。分かりやすくするために本発明書では、各ノード１１０は、関連する１つのアンテナを有するものとして示されているが、一実施形態では、ノード１１０の少なくとも一部は、２つ以上のアンテナを含んでもよい。
【００１６】
端末１１２は、無線メッシュ・ネットワーク（図例ではＷＭＮ  １０２）を介して通信するように動作可能な装置を含む。一実施形態では、端末１１２は、無線通信装置を含む。一実施形態では、端末１１２の少なくとも一部は、有線通信装置を含む。一実施形態では、端末１１２の少なくとも一部は、エンドユーザ端末（たとえば携帯電話、コンピュータなど）を含む。一実施形態では、端末１１２の少なくとも一部は、様々な通信装置（図示せず）が無線メッシュ・ネットワークの無線ノードとインターフェースすることを可能にするように適応されたゲートウェイ要素を含む。本明細書では、端末１１２は主として、無線通信装置として論じられる。
【００１７】
一実施形態では、ＷＭＮ  １０２は、ノード１１０が周波数スペクトルを共有するタイムスロット化システム（すなわちハイブリッドＣＤＭＡ−ＴＤＭＡシステム）として実装される。こうした一実施形態では、各タイムスロット内で、（リンク送信スケジュールによって指定されるように）ＷＭＮ  １０２内のリンクの部分集合（図例ではＮＬ  １１１およびＡＬ  １１３）がアクティブであり得る。本明細書に述べられるように、リンク送信スケジュールは、各ネットワーク・リンク上の固定トラフィック容量を保証するやり方で実装されたルーティング・アルゴリズム、ならびに固定トラフィック容量を使用して決定される。一実施形態では、ルーティング・アルゴリズムの実装は、ネットワーク・リンクがそれぞれの固定トラフィック容量を移送することを保証するように適応されたルーティング・アルゴリズム定式化を解くことを必要とし得る。一実施形態では、ルーティング・アルゴリズム定式化は、少なくとも１つのリンク送信スケジューリング制約を説明してもよい。
【００１８】
本明細書では主として、特定のリンク送信スケジューリング制約を説明するルーティング・アルゴリズム定式化（すなわち使用コミットメント・ベクトル）に関して述べられているが、他の様々なルーティング・アルゴリズム定式化が、他の様々なリンク送信スケジューリング制約（たとえばリンク干渉を最小限に抑え、プロバイダ間の競合を最小限に抑えるなど）を説明するために使用されてもよい。たとえば、所与のタイムスロット内で所与のリンク上で達成可能な伝送レートは信号対干渉雑音比の関数であるので、リンク送信スケジュール決定は、アクティブ・リンクのデータ・レートを最大にするためリンク干渉を最小限に抑えるために実施されてもよい。一般に、リンク送信スケジューリング制約は、物理層特性、伝送電力特性、アンテナ特性などの様々な特性、ならびにその様々な組合せに依存し得る。
【００１９】
本明細書に述べられるように、リンク送信スケジューリング制約は、アンテナ特性に依存し得る。無線ノードが狭ビーム形成アンテナを使用する一実施形態では、他のいずれかのリンク上のアクティブ・リンクによって引き起こされる干渉は、無視できるものと仮定することができる。この実施形態では、システムに課された唯一の要件は、無線ノードが単一のタイムスロット内で他の複数の無線ノードに対する送信／受信を同時には行うことができないということである（すなわち、この実施形態は、理想的なビームフォーミング・システムについて述べている）。実際のビームフォーミング・システムでは、５〜１０度未満のビーム形成は難しく、隣接リンクから少なくとも何らかのレベルの干渉がもたらされる。
【００２０】
無線ノードが全方向性アンテナを使用する一実施形態では、リンク干渉の受信の付近のすべての伝送が、リンク上の伝送に干渉する。こうした一実施形態では、このような干渉を抑える努力がなされない場合、達成されたデータ・レートはかなり低いことがある。一実施形態では、リンクに強く干渉する送信機は、ＭＡＣを使用して抑えられてもよく、このＭＡＣは、リンクの受信の特定の範囲内のすべてのノードが、リンクがアクティブな間に送信できないことを保証する。この条件が満たされるこうした一実施形態では、リンク上で達成することができるレートは主として、リンクの電力およびリンクのチャネル利得の関数である。
【００２１】
簡単にするために、本発明は主として、通信のためにビーム形成アンテナが使用される（また、すべてのノードが固定電力で送信する）システムの文脈で本明細書に述べられる。説明を簡単にするために、本発明は主として、距離がチャネル減衰に関連する非フェージング・チャネルを使用するシステムの文脈で本明細書に述べられる。本明細書では主としてこうした仮定の単純化に関して述べられているが、本発明は、固定ルーティング・アルゴリズムを実装し、様々な他の設計パラメータを使用して（たとえば全方向性アンテナを使用して、フェージング・チャネルを使用してなど）、ならびにその様々な組合せを使用して無線メッシュ・ネットワーク内の固定リンク送信スケジュールを決定するために使用されてもよい。
【００２２】
図１に示されるように、制御装置１２０は、本明細書に示された諸機能の少なくとも一部を実施する。制御装置１２０は、ＷＭＮ  １０２のネットワーク・リンク上の固定トラフィック容量を保証するように適応されたルーティング・アルゴリズムを決定する。一実施形態では、制御装置１２０は、ＷＭＮ  １０２のネットワーク・リンク上の固定トラフィック容量を保証するように適応された少なくとも１つのルーティング・パラメータを決定するために、（少なくとも１つのリンク送信スケジューリング制約を満たすやり方で定義された）ルーティング・アルゴリズム定式化を処理する。制御装置１２０は、ルーティング・アルゴリズムおよび固定トラフィック容量を使用して、ノード１１０のリンク送信スケジュールを決定する。図１に示されたように、制御装置１２０は、ノード１１０にリンク送信スケジュールを配布するためにＷＭＮ  １０２と通信する。制御装置１２０は、図２〜図４に関して本明細書に示され述べられた諸機能の少なくとも一部を実施する。
【００２３】
図２は、本発明の一実施形態による方法を示している。具体的には、図２の方法２００は、リンク送信スケジュールとして定義された固定リソース割当てを使用して無線メッシュ・ネットワークを構成するための方法を含む。連続して実施されるものとして示され述べられているが、方法２００の諸ステップの少なくとも一部は、同時に実施されても、図２に提示されたのとは異なる順序で実施されてもよいことが当業者には理解されよう。方法２００は、ステップ２０２で開始し、ステップ２０４に進む。
【００２４】
ステップ２０４で、無線メッシュ・ネットワーク内の各リンクに関連する固定トラフィック容量が決定される。一実施形態では、各リンクに関連する固定トラフィック容量は、図３に関して本明細書に示され述べられた方法を使用して決定される。ステップ２０６で、リンク送信スケジュールが生成される。一実施形態では、リンク送信スケジュールは、固定トラフィック容量を使用して生成される。一実施形態では、リンク送信スケジュールは、固定トラフィック容量の決定のために処理されたルーティング・アルゴリズムを使用して生成される。こうした一実施形態では、リンク送信スケジュールは、リンク送信スケジューリング・アルゴリズムを使用して生成される。こうした一実施形態では、リンク送信スケジュールは、辺彩色アルゴリズムを使用して生成されてもよい。
【００２５】
一実施形態では、リンク送信スケジュールは、ネットワークについて（すなわちネットワーク内のすべての無線ノードについて）について生成される。一実施形態では、ネットワークについて生成されたリンク送信スケジュールは、ネットワーク内の各無線ノードに特有の個々のリンク送信スケジュールを生成するためにさらに処理されてもよい。一実施形態では、個々のリンク送信スケジュールが、各無線ノードについて生成される。一実施形態では、リンク送信スケジュールは、ネットワーク・リンクのそれぞれがネットワーク内のトラフィックを送信する少なくとも１つの条件を含む。
【００２６】
一実施形態では、無線ネットワーク内のリンク送信を定義する条件は、送信時間（たとえば、無線ノードが無線リンクを使用して送信するタイムスロットの一部、無線ノードが無線リンクを使用して送信するタイムスロット、無線ノードが無線リンクを使用して送信する複数のタイムスロットなど）、無線ノードが無線リンクを使用して送信する送信周波数、無線ノードが無線リンクを使用して送信する送信電力、無線ノードが無線リンクを使用して送信する先の受信機（すなわち無線ノード）および類似の条件、ならびにその様々な組合せのうちの少なくとも１つを含んでもよい。
【００２７】
ステップ２０８で、リンク送信スケジュールは、ネットワークの各無線ノードに伝えられる。一実施形態では、リンク送信スケジュールが無線ネットワークについて生成される一実施形態では、完全リンク送信スケジュールが、各無線ノードに送信されてもよい。それぞれの無線ノードに関連する個々のリンク送信スケジュールを生成するためにリンク送信スケジュールがさらに処理される一実施形態では、個々のリンク送信スケジュールが、それぞれの無線ノードに送信されてもよい。ステップ２１０で、無線ネットワーク内のトラフィックは、リンク送信スケジュールを使用してルーティング・アルゴリズムに従ってルーティングされる。ステップ２１０で、方法２００は終了する。
【００２８】
一実施形態では、無線メッシュ・ネットワーク内のリンク送信スケジューリングの性質が一般に固定されたものである（分、時間、日、月、および潜在的により長い期間の順で固定されている）ため省略されているが、固定リンク送信スケジュールは、修正されてもよい。こうした一実施形態では、固定リンク送信スケジュールは、ネットワーク・リンクに関連する１つまたは複数の固定トラフィック容量の変化に応答して修正されてもよい。一実施形態では、ネットワーク・リンクに関連する１つまたは複数の固定トラフィック容量の変化は、ネットワーク内で使用されるルーティング・アルゴリズムへの変更の結果であり得る。一実施形態では、ネットワーク・リンクに関連する１つまたは複数の固定トラフィック容量の変化は、ネットワークへの変更（たとえばネットワーク構成変更、ノード容量変更など、ならびにその様々な組合せ）の結果であり得る。
【００２９】
たとえば、固定トラフィック容量が各ノードの入口および出口トラフィック容量に依存するように２段階ルーティング・アルゴリズムを使用する無線メッシュ・ネットワークでは、ノードのうちの１つのノードの容量の変化（たとえば、追加のネットワーク・トラフィックをサポートするように動作可能な追加の回線カードがノードに追加される）は、ノードに関連するネットワーク・リンクの固定トラフィック容量への変更をもたらし、それによってリンク送信スケジュールへの変更が必要となる。換言すると、本発明によって提供される固定リンク送信スケジューリングは、既存のリンク送信スケジューラによって提供されるものより実質的に長い期間の間、固定されたままであり得るが、本発明は、様々な変化に応答して必要とされる固定リンク送信スケジュールへの修正を可能にする。
【００３０】
図３は、本発明の一実施形態による方法を示している。具体的には、図３の方法３００は、２段階ルーティング・アルゴリズムを使用する無線メッシュ・ネットワークの各リンクに関連する固定トラフィック容量を決定するための方法を含む。２段階ルーティング・アルゴリズムを使用した無線メッシュ・ネットワークの各リンクの固定トラフィック容量の決定に関して述べたが、方法３００は、他の様々なルーティング・アルゴリズムを使用して無線メッシュ・ネットワークのリンクの固定トラフィック容量を決定するように適応されてもよい。連続して実施されるものとして示され述べられているが、方法３００の諸ステップの少なくとも一部は、同時に実施されても、図３に示されたのとは異なる順序で実施されてもよいことが当業者には理解されよう。方法３００は、ステップ３０２で開始し、ステップ３０４に進む。
【００３１】
ステップ３０４で、各ノードに関連する入口トラフィックが決定される。ステップ３０６で、各ノードに関連する出口トラフィックが決定される。一実施形態では、各ノードに関連する入口および出口のトラフィックはそれぞれ、各ノードによってサポートされた入口トラフィックの最大容量および出口トラフィックの最大容量である。こうした一実施形態では、各ノードに関連する入口および出口トラフィックはそれぞれ、各ノードに関連する入口および出口容量（たとえば各ノードに関連する回線カード）に従って決定される。この実施形態では、各ノードに関連する入口トラフィックおよび出口トラフィックは、各ノードに関連するノード・プロファイル（図例では、制御装置１２０によってローカルに格納されたノード・プロファイル）を使用して決定されてもよい。
【００３２】
ステップ３０８で、各ノードに関連するトラフィック分割比が決定される。一実施形態では、各ノードに関連するトラフィック分割比は、トラフィック分割比が決定されるルーティング・アルゴリズム（たとえば２段階ルーティング）のルーティング・アルゴリズム定式化を解くことによって決定される。本明細書に述べられるように、各ノードに関連するトラフィック分割比は、第１ルーティング段階のネットワーク内の他のノード間のトラフィック分配を定義する。一実施形態では、トラフィック分割比は、トラフィック宛先に関係なくトラフィック分配を定義してもよい。一実施形態では、各ノードに関連するトラフィック分割比が、少なくとも１つのスケジューリング制約を満たすやり方で決定される。一実施形態では、各ノードに関連するトラフィック分割比が、図４に関して本明細書に示され述べられた方法を使用して決定される。
【００３３】
ステップ３１０で、各リンクに関連する固定トラフィック容量が決定される。一実施形態では、各リンクに関連する固定トラフィック容量は、入口トラフィック容量、出口トラフィック容量、および各ノードに関連するトラフィック分割比を使用して決定される。一実施形態では、それぞれのリンクに関連した固定トラフィック容量が、トラフィック分割比が決定されるルーティング・アルゴリズムのルーティング・アルゴリズム定式化を解くことによって決定されてもよい。一実施形態では、リンクに関連する固定トラフィック容量は、リンクを横断するトラフィックの平均容量である。本明細書に示されるように、リンク送信スケジュールの決定のため、無線メッシュ・ネットワークのリンクに関連する固定トラフィック容量が、固定トラフィック容量を決定するために処理されたルーティング・アルゴリズムと併せて使用されてもよい。ステップ３１２で、方法３００は、終了する。
【００３４】
本発明は、無線メッシュ・ネットワーク内のリンク上の固定トラフィック容量を保証するように適応されたルーティング・アルゴリズムを構成することによって、ルーティング・アルゴリズム、および関連する固定トラフィック容量を使用して決定された静的リンク送信スケジュールを使用してネットワーク・スループットを向上させることを可能にする。ルーティング・アルゴリズムが２段階ルーティング・アルゴリズムである一実施形態では、ルーティング・アルゴリズムの構成は、無線メッシュ・ネットワークのノードに関連するトラフィック分割比を決定することを含んでもよい。トラフィック分割比は、少なくとも１つのリンク送信スケジューリング制約を満たすように適応されたルーティング・アルゴリズムの特定の定式化を解くことによって決定されてもよい。特定のリンク送信スケジューリング制約（使用コミットメント・ベクトルβ）を満たしながらトラフィック分割比を決定するための方法についての詳細な説明が、本明細書で下記に示される。
【００３５】
一実施形態では、ＷＭＮ  １０２は、ＷＭＮ  １０２、すなわち直接通信範囲にノード対を含むトポロジーが、ノード・セットＮおよび有向リンク・セットＥを含む、グラフＧ＝（Ｎ，Ｅ）としてモデル化される表記の文脈内で述べることができる。本明細書に示されるように、ノード・セットＮ内の各ノードは、ソース・ノード、中間ノードおよび宛先ノードとして動作してもよい。一表記では、｜Ｎ｜＝ｎ、および｜Ｅ｜＝ｍとする。一表記では、ノードｉの入および出リンクのセットは、それぞれＥ−（ｉ）およびＥ＋（ｉ）で示される。一表記では、ノードｉからノードｊへのネットワーク内の有向リンクは、（ｉ，ｊ）と示される。表記を単純にするために、リンクは、表記（ｉ，ｊ）ではなく、ｅ（すなわちエッジｅ）と示すこともできる。一表記では、リンク（ｉ，ｊ）の容量は、Ｕｉｊと示される。
【００３６】
一実施形態では、ＷＭＮ  １０２内の各ノード１１０は、（他のノード１１０から）ノード１１０に接続されたネットワーク・リンク（図例ではＮＬ  １１１）と、（関連するＷＴ  １１２から）ノード１１０に接続されたアクセス・リンク（図例ではＡＬ  １１３）の間で、スペクトル・リソース、無線リソースなど、ならびにその様々な組合せ（まとめて、リソースと示される）を共有する。アクセス・リンクを介して無線端末に使用可能にされるリソースの一実施形態では、リソースのいくらかの部分は、無線端末からノードへのアップリンク送信用に使用され、リソースの残りの部分は、ノードから無線端末へのダウンリンク送信用に使用される。
【００３７】
一実施形態では、ネットワークへのノード・コミットメントが定義されてもよい。一実施形態では、本発明は、アクセス・リンクとネットワーク・リンクを分離する。一実施形態では、アクセス・リンクとネットワーク・リンクの分離は、使用コミットメント・ベクトルを使用して達成される。一実施形態では、ノードｉ（図例では、ノード１１０のうちの１つ）の使用の最大部分βｉが、ノードｉに関連するネットワーク・リンクのサポートにコミットされる（すなわち、ノードｉは、最大でも、ノードｉに使用可能な送信時間のうちの部分βｉをノードｉに関連するネットワーク・リンク上の送信に費やし、ノードｉに使用可能な送信時間のうちの部分（１−βｉ）をノードｉに関連するアクセス・リンク上の送信に費やす）。本明細書では、ベクトルβ（ネットワーク内の各ノードｉについてのβｉを含む）は、ノード使用コミットメント・ベクトルとして示される。
【００３８】
一実施形態では、ノードｉのネットワーク・リンクは、ネットワーク・リンク送信スケジューリングがアクセス・リンク送信スケジューリングの前に実施されるという意味で、ノードｉのアクセス・リンク送信よりも優先すると仮定されているが、しかし、こうした優先性にもかかわらず、ノードｉのネットワーク・リンクは、ノードｉ使用の部分βｉよりも多く利用しないように制約される。ノードｉのネットワーク・リンク用のリソースがノードｉのアクセス・リンク用のリソースと共有されない一実施形態では、ノードｉの使用コミットメントβｉは１に等しい（すなわちβｉ＝１）である。たとえば、示されていないが、一実施形態では、ノード１１０のうちの１つまたは複数が、ネットワーク・リンクだけをサポートするバックホール・ノード（すなわち、無線端末によるアクセスを可能としない）として配置されてもよい。
【００３９】
一実施形態では、ノードへのネットワーク保証が定義されてもよい。一実施形態では、ノードへのネットワーク保証は、データ・レート保証であってもよい。一実施形態では、ネットワーク（図例ではＷＭＮ  １０２）上のトラフィックをルーティングする代わりに、ネットワークは、ノードｉ（図例ではノード１１０のうちの１つ）に、ノードｉからのＲｉの入口データ・レート、およびノードｉへのＣｉの出口データ・レートの移送を保証する。一実施形態では、データ・レートの保証は、入トラフィック（入口トラフィックと示される）のソース、および出トラフィック（出口トラフィックと示される）の宛先から独立したものである。ベクトル（Ｒ，Ｃ）（ネットワーク内各ノードｉについての（Ｒｉ，Ｃｉ）の値を含む）は、データ・レート保証ベクトルとして示される。一実施形態では、データ・レート保証ベクトル（Ｒ，Ｃ）は、ネットワークのノードのそれぞれの容量に従って決定されてもよい。
【００４０】
一実施形態では、ネットワーク構成および使用コミットメント・ベクトルβが与えられると、所与のデータ・レート保証ベクトル（Ｒ，Ｃ）は、達成可能であることも、達成不可能であることもある。一実施形態では、この達成可能性の問題は、データ・レートλ（Ｒ，Ｃ）が達成可能であるように最大スカラλを決定するように定式化してもよい。λ＜１の場合、所与のデータ・レート・ベクトル（Ｒ，Ｃ）は達成不可能である。λ≧１の場合、所与のデータ・レート・ベクトル（Ｒ，Ｃ）は達成可能である。一実施形態では、ルーティング・アルゴリズム問題を定式化するために、本明細書で述べられた様々なモデリング仮定が使用されてもよく、それを解くことによって、それぞれのネットワーク・リンク上の固定トラフィック容量を保証するやり方でルーティング・アルゴリズムを実装することが可能となる。ルーティング・アルゴリズムが２段階ルーティング・アルゴリズムであるこうした一実施形態では、ルーティング・アルゴリズム定式化を解くことによって、それぞれのノードに関連するトラフィック分割比が指定され、このトラフィック分割比は、それぞれのネットワーク・リンク上の固定トラフィック容量を保証するように適応される。
【００４１】
一実施形態では、ノード使用コミットメント・ベクトルβが与えられ、またデータ・レート保証ベクトル（Ｒ，Ｃ）が与えられると仮定されてもよい。データ・レート保証ベクトル（Ｒ，Ｃ）は、トラフィック行列（すなわちトラフィック・パターン）から独立したものである。一実施形態では、本発明は、データ・レート保証ベクトル（Ｒ，Ｃ）に反していないどんなトラフィック行列もルーティング・アルゴリズムを使用してネットワーク介してルーティングされ得ることを保証する。こうした一実施形態では、トラフィック分割比は、それぞれのネットワーク・リンク上の固定トラフィック容量を保証するためのデータ・レート保証ベクトルと併せて使用されてもよい。さらなる一実施形態では、本発明は、ルーティング・アルゴリズム（データ・レート保証ベクトル（Ｒ，Ｃ）および関連するトラフィック分割比によって指定される）によって必要とされる帯域幅を満たすようにリンク送信スケジュールが生成され得ることを保証する。
【００４２】
ルーティング含意について、以下のように述べることができる。ネットワーク内のトラフィックの２地点間行列は、データ・レート保証ベクトル（Ｒ，Ｃ）によって制約される。データ・レート保証ベクトル制約は、ネットワークによって運ばれるべきトラフィックの知られている唯一の側面であり、制約を知ることは、トラフィック行列の行と列の和の範囲を知ることに等しい。換言すると、ネットワークのいずれの許容可能トラフィック行列Ｔ＝［ｔｉｊ］も、数式１に従わなければならない。所与のＲｉおよびＣｉ値について、Ｔ（Ｒ，Ｃ）は、数式２に示されるように、トラフィック行列の行と列の和によって部分的に指定されるすべてのこうしたトラフィック行列のセットを示す。一実施形態では、トラフィック分布Ｔは、Ｔ（Ｒ，Ｃ）内のいずれかのトラフィック行列であってもよく、時間と共に変化することもある。一実施形態では、本発明のルーティング・アルゴリズムは、Ｔが、行と列の和の範囲によって部分的に指定される以外、Ｔに関する仮定を行わない。
【数１】
2009532940.tif 000003
【００４３】
一実施形態では、ネットワーク内のリンクｅ上で送信する間、無線メッシュ・ネットワーク内の送信が狭ビーム形成指向性アンテナを使用する一実施形態では、リンクｅの送信ノード（図例では、ノード１１０のうちの１つ）、またはリンクｅの受信ノード（図例では、ノード１１０のうちの１つ）は、無線メッシュ・ネットワーク内の他のいずれかのノードに対する（あるいは、リンクｅの送信および受信ノードの特定の距離内の）送信または受信を行うことができない。固定送信電力および非フェージング・チャネルが実装される一実施形態では、リンクｅの達成可能データ・レート（ｃ（ｅ）と示される）は、定数である（すなわち、リンクｅに関連する固定トラフィック容量が保証される）。本発明のルーティング・アルゴリズムがリンクｅ上でｘ（ｅ）のフローを送信するこうした一実施形態では、リンクｅが使用される時間の部分（ｆ（ｅ）と示される）は、ｆ（ｅ）＝ｘ（ｅ）／ｃ（ｅ）によって示される。
【００４４】
一実施形態では、無線メッシュ・ネットワーク内の任意のノードｖ（図例では、ＷＭＮ  １０２内の任意のノード１１０）を仮定すると、Ｎ（ｖ）をその送信機または受信機がノードｖであるリンクのセットを示すために使用してもよい。ネットワーク内の任意のノードｖのネットワーク・リンクの使用はβｖ未満でなければならないので、ノードｖのリンクがスケジュール可能であるために必要な条件が、（数式３と同様に）導出されてもよい。一実施形態では、（数式３と同様に）導出された条件は、（数式４と同様に）スケジュールが達成可能となるための関連条件を導出するように適応されてもよい。一実施形態では、条件は、条件を満たすように適応されたルーティング・アルゴリズムを決定するため（ならびに、解決される場合、無線メッシュ・ネットワークの各リンクに関連する固定トラフィック容量を保証しているルーティング・アルゴリズムの定式化を定義するために）使用されてもよい。
【数２】
2009532940.tif 000004
【００４５】
一実施形態では、ルーティング・アルゴリズムは、（たとえばネットワーク状態、リンク送信スケジューリング制約など、ならびにその様々な組合せを含めた）少なくとも１つの条件を満たすやり方で解くことができるルーティング・アルゴリズム定式化を生成するように適応される。本明細書では主として特定のネットワーク条件（たとえば指向性アンテナ）、および特定のリンク送信スケジューリング制約（すなわち使用コミットメント・ベクトルβ）に関して述べられているが、ルーティング・アルゴリズム定式化は、他の様々なネットワーク条件、リンク送信スケジューリング制約、ならびに類似の条件および制約、ならびにその様々な組合せを満たすように定義されてもよい。
【００４６】
一実施形態では、ネットワーク状態に関して、ルーティング・アルゴリズム定式化は、（本明細書で述べられる指向性アンテナを使用するシステムとは異なり）全方向性アンテナを使用したシステム用に設計されてもよい。一実施形態では、リンク送信スケジューリング制約に関して、ルーティング・アルゴリズム定式化が、送信電力制約、プロバイダ間リンク送信制約など、ならびにその様々な組合せを満たすように設計されてもよい。本明細書では主としてネットワーク条件、およびリンク送信スケジューリング制約について述べられているが、一実施形態では、それを解くことによってネットワーク・リンク上の固定トラフィック容量が保証されるルーティング・アルゴリズム定式化が、他の条件を説明し、他の制約を満たすなど、ならびにその組合せを行うやり方で定義されてもよい。
【００４７】
一実施形態では、ノード使用コミットメント・ベクトルβおよびデータ・レート保証ベクトル（Ｒ，Ｃ）が与えられると、本発明は、所定のルーティング・アルゴリズムを使用して、ネットワークのトラフィック・パターンから独立したデータ・レート保証ベクトル（Ｒ，Ｃ）を保証する。リンク送信スケジュールは、ルーティング・アルゴリズム、およびそれぞれのネットワーク・リンクに関連する固定トラフィック容量に従って決定される（ただし、固定トラフィック容量は、ルーティング・アルゴリズムおよびデータ・レート保証ベクトル（Ｒ，Ｃ）に基づいて決定される）。一実施形態では、リンク送信スケジューリング・アルゴリズムは、ルーティング・アルゴリズム、およびルーティング・アルゴリズムによって保証された関連の固定トラフィック容量に従ってリンク送信スケジュールを決定するために使用されてもよい。
【００４８】
一実施形態では、ルーティング・アルゴリズムは、２段階ルーティング・アルゴリズムである。こうした一実施形態では、提案された２段階ルーティング方式は、提案された２段階ルーティング方式を実装するのに必要な帯域幅量がノード使用コミットメント・ベクトルβおよびデータ・レート保証ベクトル（Ｒ，Ｃ）の関数にすぎない（すなわち、２段階ルーティング方式が、トラフィック・パターンから独立している）という特性を有する。一実施形態では、第１の段階で、任意のノード（図例ではＷＭＮ  １０２のノード１１０のうちのいずれか）で無線メッシュ・ネットワークに入るトラフィックの所定の部分αｊ（トラフィック分割比αと示される）が、トラフィックの最終宛先に関係なく、あらゆるノードｊに分配される。一実施形態では、２段階ルーティング方式の実装の前に、データ・レート保証ベクトル（Ｒ，Ｃ）を達成するように動作可能なトラフィック分割比αが決定されてもよい。
【００４９】
一実施形態では、線形プログラミング問題は、２段階ルーティング・アルゴリズムの下で最適なデータ・レート保証を決定するために（すなわちそれぞれのネットワーク・リンク上の固定トラフィック容量を保証するために）定式化される。こうした一実施形態では、線形プログラミング問題は、２段階ルーティング・アルゴリズムの下で最適なデータ・レート保証を決定するための少なくとも１つのリンク送信スケジューリング制約（使用コミットメント・ベクトルβ）を満たすやり方で解決される。一実施形態では、２段階ルーティング・アルゴリズムに従って定式化された線形プログラミング問題の解は、トラフィック分割比を出力し、このトラフィック分割比が、ネットワーク内で実施されると、ネットワーク内のそれぞれのネットワーク・リンク上の固定のトラフィック容量（すなわちリンク・フロー）をもたらす。
【００５０】
一実施形態では、固定トラフィック容量が、ネットワーク・リンク上のリンク送信の様々な明細を定義する関連のリンク送信スケジュールを決定するために、関連する２段階ルーティング・アルゴリズムの明細と併せて使用されてもよい。こうした一実施形態では、リンク送信スケジュールは、リンク送信スケジューリング・アルゴリズムを使用して決定されてもよい。一実施形態では、リンク送信スケジューリング・アルゴリズムは辺彩色アルゴリズムである。こうした一実施形態では、辺彩色アルゴリズムの各色は、タイムスロットに対応し、同じ色を有するすべてのリンクが、そのタイムスロットで同時に送信する。こうした一実施形態では、欲張り辺彩色が、ネットワーク内の各リンクのリンク・フローをリンク・スケジュールに変換するために使用されてもよい。
【００５１】
本明細書に述べられるように、一実施形態では、ルーティング・アルゴリズムは、２段階ルーティング・アルゴリズムである。第１の段階では、いずれかのノード（図例では、ＷＭＮ  １０２のノード１１０のうちのいずれか）で無線メッシュ・ネットワークに入るトラフィックの所定の部分αｊが、トラフィックの最終宛先に関係なくあらゆるノードｊに分配される。第１段階の分配の結果、第２段階では、異なる宛先ノードに宛てられたトラフィックを受信する各ノードは、受信されたトラフィックを関連する宛先ノードにルーティングする。一実施形態では、無線メッシュ・ネットワーク内の２段階ルーティング・アルゴリズムの実装は、ノード間で固定帯域幅経路を確立することによって実施されてもよい。こうした一実施形態では、第１段階のトラフィックおよび第２段階のトラフィックを伝える経路を識別するために、経路は、それぞれ第１段階の経路および第２段階の経路と呼ばれ得る。
【００５２】
本明細書に述べられるように、２段階ルーティング・アルゴリズムを使用して、固定トラフィック容量が、それぞれのネットワーク・リンク上で確立されてもよい。２段階ルーティング・アルゴリズムは、第１段階の経路および第２段階の経路に必要な帯域幅がそれぞれ入口容量Ｒｉおよび出口容量Ｃｉだけに依存する（またトラフィック行列内の（知られていない）個々の項目には依存しない）ことを保証する。２段階ルーティング・アルゴリズムは、ネットワークがネットワーク・ルーティングおよびスケジューリングの動的な適応なしに任意の（恐らく急速に変化する）トラフィック需要に対処することを可能にしながら、帯域幅保証サービスの要件と、ランデブー・ベースのサービスの要件の両方を満たす。実際、２段階ルーティング・アルゴリズムは、ネットワークがトラフィック分布の変化を検出することさえ不要である。
【００５３】
トラフィック分割比α１，α２，…，αｎがΣαｉ＝１（ｉ＝１〜Ｎにわたる和）である２段階ルーティング・アルゴリズムにおいて、最大の入口トラフィックＲｉを有するノードｉについて考慮されたい。ノードｉは、各ノードｊ∈Ｎについて第１段階の間、αｊＲｉ量の入口トラフィックＲｉをノードｊに送信する。換言すると、αｊＲｉは、第１段階の間のノードｉからノードｊへの需要である。第１段階のトラフィック分配の後に、ノードｉは、ネットワーク内の他のいずれかのノードｋから、αｊＲｋ量のトラフィックを受信している。第１段階でネットワークのすべてのトラフィックがトラフィックの最終宛先に関係なく分離されるので、ネットワーク内の他のいずれかのノードｋからノードｉによって受信されたこのαｊＲｋ量のトラフィックから、αｉｔｋｊ量のトラフィックが、ノードｊに宛てられる。第２段階でノードｉからノードｊにルーティングされるべき最大トラフィック量は、Σｋ∈Ｎαｉｔｋｊ＝αｉＣｊである。換言すると、αｉＣｊは、第２段階の間のノードｉからノードｊへの需要である。
【００５４】
２段階ルーティング・アルゴリズムでは、第１段階および第２段階のルーティング結果としてのノードｉからノードｊへの最大需要は、（αｊＲｉ＋αｉＣｊ）であり、それは行列Ｔ∈Ｔ（Ｒ，Ｃ）から独立したものである。２段階ルーティング・アルゴリズムは、ソース宛先トラフィックのルーティングが固定の経路に沿って所定の分配比で行われることを保証する。換言すると、２段階ルーティング・アルゴリズムは、トラフィック変化を意識しないトラフィック・ルーティングをもたらす。２段階ルーティング・アルゴリズムは、第１段階および第２段階のルーティング結果としてノードｉとｊの間の総需要がｔ’ｉｊ＝（αｊＲｉ＋αｉＣｊ）であることを保証し、それによって、ネットワーク内の各ネットワーク・リンク上の固定トラフィック容量を保証する（また、総需要を、Ｔを制約する行と列の和範囲だけに依存させる（すなわちＴ∈Ｔ（Ｒ，Ｃ））。換言すると、２段階ルーティング方式は、行と列の和範囲、およびトラフィック分割比αだけに依存する、変換された行列Ｔ’＝〔ｔ’ｉｊ〕を有効にルーティングすることによってトラフィック行列Ｔ∈Ｔ（Ｒ，Ｃ）の可変性に対処する。
【００５５】
２段階ルーティング・アルゴリズムでは、第１段階の各ソース・ノードの分配決定は、ローカルの決定（すなわちネットワーク全体の状態情報を必要としない）を含み、各中間ノードのルーティング決定はパケット宛先に基づく（すなわち、ネットワーク全体の状態情報を必要としない）。２段階ルーティング・アルゴリズムは、実際のトラフィック行列からは独立した、無線メッシュ・ネットワークの各リンク上に流れるトラフィック量（すなわち、それぞれのネットワーク・リンクに関連する固定トラフィック容量）を提供するトラフィック・フローを保証する。本明細書に述べられるように、トラフィック分割比αｉを決定し、リンク送信スケジューリング制約を考慮することによって、トラフィック・フローをスケジューリングするためのリンク送信スケジュールが決定されてもよい。２段階ルーティング・アルゴリズムはトラフィック分布の変化を意識せず、またそれに対して堅牢であり、エンドツーエンドの帯域幅保証を提供し、ネットワークのリアルタイム再構成を必要としない。
【００５６】
本発明の線形プログラム定式化では、ノード使用コミットメント・ベクトルβおよびデータ・レート保証ベクトル（Ｒ，Ｃ）が与えられると、最大のスカラλが、データ・レート保証ベクトル（Ｒ，Ｃ）が達成可能となるように決定されてもよい。達成可能なデータ・レート保証ベクトル（Ｒ，Ｃ）では、ノードｉは、λＲｉの入口データ・レートおよびλＣｉの出口データ・レートが保証される。λ・Ｔ（Ｒ，Ｃ）を、項目にλが掛けられたＴ（Ｒ，Ｃ）内のすべてのトラフィック行列のセットを示すものとすると、線形プログラミング定式化は、λ・Ｔ（Ｒ，Ｃ）内のすべての行列が、リンク・スケジューリング制約を満たすやり方でルーティングされ得るような最大乗数λ（すなわちスループット）を見つけることに等しい。一実施形態では、リンク・フロー・ベースの定式化が解決されてもよい。一実施形態では、経路フロー・ベースの定式化が解決されてもよい。
【００５７】
一実施形態において、リンク・フロー・ベースの定式化では、ソースと宛先の間のフローが、商品として示されてもよく、ｋは、商品の指数を示すのに使用されてもよい。商品ｋのソースおよび宛先ノードは、それぞれｓ（ｋ）およびｄ（ｋ）によって示され得る。リンクｅ上の商品ｋのフロー量は、ｘｋ（ｅ）と示され得る。この実施形態では、２組の決定変数がある：（１）分配率αｉ、および（２）商品ｋのリンクｅ上のフローｘｋ（ｅ）。この実施形態では、商品ｋの需要は、αｓ（ｋ）Ｃｄ（ｋ）＋αｄ（ｋ）Ｒｓ（ｋ）によって示され得る。こうした一実施形態では、リンク・フロー・ベースの定式化は、以下の数式（数式５〜数式７）に従って、すべてのノードｉ∈ＮについてΣαｉを最大にするものとして表され得る。
【数３】
2009532940.tif 000005
【００５８】
この実施形態では、α＊ｉがリンク・フロー・ベースの定式化の最適解のαｉ値を含むものとすると、スループットλ＊は、最適目的関数値、すなわちλ＊＝Σｉα＊ｉである。この実施形態では、α＊ｉ値は、実際の分配比αを決定するために、λ＊分の１に減少させることができ、需要がルーティングされる明示的な経路が、リンク・フロー・ベースの定式化の解から決定され得る。さらなる一実施形態では、スループットが達成可能かどうか判断するために、リンク・スケジューリング・アルゴリズム（たとえば辺彩色）が使用されてもよい。
【００５９】
一実施形態では、本発明の様々な実施形態のルーティングおよびリンク・スケジューリング決定のために、リンク・フロー・ベースの定式化が解かれてもよい。リンク・フロー・ベースの定式化は多項式サイズであり、線形プログラミング解法を使用して解くように適用可能であるが、ネットワーク問題の一般線形プログラミング・ベースのアルゴリズムは、数十ノード超のサイズのネットワークではうまくスケーリングされないことがよく知られている。したがって、一実施形態では、リンク・フロー・ベースの定式化を解くために、完全多項式時間近似方式（ＦＰＴＡＳ：Ｆｕｌｌｙ  Ｐｏｌｙｎｏｍｉａｌ  Ｔｉｍｅ  Ａｐｐｒｏｘｉｍａｔｉｏｎ  Ｓｃｈｅｍｅ）が使用されてもよい。一般に、ＦＰＴＡＳは、以下の性能保証を提供する：ε＞０の場合、解は、最適値の（１＋ε）倍以内の目的関数値を有し、実行時間はせいぜい、ネットワーク・サイズ、トラフィック需要数、および１／εの多項式関数である。
【００６０】
一実施形態では、経路フロー・ベースの定式化では、Ｐｉｊは、ノードｉからノードｊへのすべての経路のセットを示し得る。こうした一実施形態は、ｘ（Ｐ）は、経路Ｐ上のトラフィックを示す。一般に、ネットワークは、ネットワーク・サイズの指数関数である複数の経路を含んでもよい。したがって、経路フロー・ベースの定式化の線形プログラム（すなわちプライマル）実装は、指数関数的な数の変数を含んでいてもよく、関連する双対は、指数関数的な数の制約を含んでもよく、両方のプログラムが、中サイズから大サイズのネットワークで実行するのに適さないものになる。しかし、一実施形態では、プライマルおよび双対バージョンの経路フロー・べースの定式化が、経路フロー・ベース定式化を解くための高速の組合せアルゴリズムを設計するために使用されてもよい。経路フロー・ベースの定式化は、以下の数式（数式８〜数式９）に従って、すべてのノードｉ∈ＮについてΣαｉを最大化するものとして表され得る。
【数４】
2009532940.tif 000006
【００６１】
したがって、経路指数付け線形プログラミング定式化は、経路フロー・ベースの定式化を解くための高速組合せアルゴリズムの策定のために使用されてもよい。一実施形態では、トラフィック分配比αｉを計算するための近似アルゴリズムは、ε＞０について、最適目的関数値（すなわち最大スループット）の（１＋ε）倍までトラフィック分配比αｉを計算してもよい。こうした一実施形態では、εの値は、望ましい程度の解の最適性をもたらすように選択されてもよい。一実施形態では、アルゴリズムが各ステップでプライマルおよび双対の解を維持するので、最適性の差は、プライマルおよび双対目的関数値の比を計算することによって推定することができる。
【００６２】
一実施形態では、経路フロー・ベースの定式化の双対定式化について、変数ωｉの値は、各ノードｉ∈Ｎに関連付けられてもよく、変数πｉｊは、数式８の各需要制約に関連付けられてもよい。こうした一実施形態では、ＳＰ（ｉ，ｊ）は、リンク・コストｃ（ｅ）＝Σｉ：ｅ∈Ｎ（ｉ）ω（ｉ）／ｕｅ下で最短経路Ｐ∈Ｐｉｊを示す。一実施形態では、双対変数πｉｊの削除のための双対線形プログラムの単純化の後に、双対定式化は、以下の条件（数式１０および数式１１）に従って、すべてのノードｉについてのβｉω（ｉ）の合計を最小にするものとして表され得る。
【数５】
2009532940.tif 000007
【００６３】
一実施形態では、Ｖ（ｋ）は、（１）すべてのノードｉ（ｉ≠ｋ）およびｋ（ｋ∈Ｎ）にわたるＲｉ・ＳＰ（ｉ，ｋ）の合計と、（２）すべてのノードｊ（ｊ≠ｋ）およびｋ（ｋ∈Ｎ）にわたるＣｊ・ＳＰ（ｋ，ｊ）の合計の和を示してもよい。一実施形態では、所与の重みω（ｉ）、Ｖ（ｋ）は、２つの最短経路計算：（１）ルートとしてノードｋを有する最短経路ツリーの最短経路計算、および（２）他のすべての経路からノードｋに到達する逆最短経路ツリーの最短経路計算を使用して多項式時間で計算されてもよい。したがって、１組の重みω（ｉ）が与えられると、以下の不等式：すべてのノードｋ∈Ｎについて、ｍｉｎ｛Ｖ（ｋ）｝≧１が満たされる時かつその時に限り、双対プログラムの解は、実現可能である。経路フロー・ベースの定式化を解くための例示的な高速組合せアルゴリズムが、図４に関して、本明細書に示され述べられる。
【００６４】
図４は、本発明の一実施形態による方法を示している。具体的には、図４の方法４００は、それぞれのネットワーク・リンク上の固定トラフィック容量を保証するように適応されたトラフィック分割比を決定するための方法を含む。特定の２段階ルーティング・アルゴリズムのためのトラフィック分割比の決定に関して述べられているが、方法４００は、それぞれのネットワーク・リンク上の固定トラフィック容量を保証するための他の様々なパラメータを決定するように適応されてもよい。連続して実施されるものとして示され述べられているが、方法４００の諸ステップの少なくとも一部は、同時に実施されても、図４に提示されたのとは異なる順序で実施されてもよいことが当業者には理解されよう。方法４００は、ステップ４０２で開始し、ステップ４０４に進む。
【００６５】
ステップ４０２で、変数が初期化される。各ノードｋに関連するトラフィック分割比αｋは、各ノードｋ∈Ｎについてゼロに初期化される（すなわち、すべてのｋ∈Ｎについて、αｋ＝０）。各ノード
【数６】
2009532940.tif 000008
に関連する重み
【数７】
2009532940.tif 000009
は、量δ
【数８】
2009532940.tif 000010
に初期化される。一実施形態では、量δは、エラー・パラメータεに依存する。（ノード
【数９】
2009532940.tif 000011
に関連するリンク・サブセット
【数１０】
2009532940.tif 000012
について）各ノード
【数１１】
2009532940.tif 000013
に関連するリンク・サブセット使用値を維持するリンク・サブセット使用配列
【数１２】
2009532940.tif 000014
は、ゼロに初期化される
【数１３】
2009532940.tif 000015
。制約監視変数Ｇは、ゼロに初期化される（すなわちＧ＝０）。制約監視変数のＧは、双対制約が指定される限り１未満のままである。
【００６６】
ステップ４０６で、各ノード対ｉ，ｊ∈Ｎについて、関連するコストＳＰ（ｉ、ｊ）を有するノードｉからノードｊへの最短経路が計算される。ステップ４０８で、各リンクｅ∈Ｅについて、達成可能なデータ・レートｃ（ｅ）が計算される。達成可能なデータ・レートｃ（ｅ）は、
【数１４】
2009532940.tif 000016
のように計算される。ステップ４１０で、Ｖ（ｋ）が計算される。一実施形態では、Ｖ（ｋ）は、（１）すべてのノードｉ（ｉ≠ｋ）および（ｋ∈Ｎ）にわたるＲｉ・ＳＰ（ｉ、ｋ）の合計と、（２）すべてのノードｊ（ｊ≠ｋ）およびｋ（ｋ∈Ｎ）にわたるＣｊ・ＳＰ（ｋ、ｊ）の合計の和（すなわち、数式１０に関して本明細書に示され述べられた
【数１５】
2009532940.tif 000017
）のように計算される。
【００６７】
ステップ４１２で、Ｖ（ｋ）が最小であるノード
【数１６】
2009532940.tif 000018
が決定され、それによって、ノード
【数１７】
2009532940.tif 000019
ならびに以下の経路：（１）すべてのノードｉについてノードｉからノード
【数１８】
2009532940.tif 000020
への経路Ｐｉ、および（２）すべてのノードｊについてノード
【数１９】
2009532940.tif 000021
からノードへの経路Ｑｊを識別する。ステップ４１４で、Ｐｉを、すべてのノードｉについてノードｉからノード
【数２０】
2009532940.tif 000022
への最短経路とし、Ｑｊを、すべてのノードｊについてノード
【数２１】
2009532940.tif 000023
からノードｊへの最短経路とする。ステップ４１６で、各ノード
【数２２】
2009532940.tif 000024
について、
【数２３】
2009532940.tif 000025
を、
【数２４】
2009532940.tif 000026
に属する最短経路Ｐｉ上の１組のリンク
【数２５】
2009532940.tif 000027
とする。ステップ４１８で、各ノード
【数２６】
2009532940.tif 000028
について、
【数２７】
2009532940.tif 000029
を、
【数２８】
2009532940.tif 000030
に属する最短経路Ｑｊ上の１組のリンク
【数２９】
2009532940.tif 000031
とする。ステップ４２０で、各ノード
【数３０】
2009532940.tif 000032
について、
【数３１】
2009532940.tif 000033
が下記（数式１２）のように計算される。
【数３２】
2009532940.tif 000034
【００６８】
ステップ４２２で、トラフィック分割比が設定される。一実施形態では、トラフィック分割比は、
【数３３】
2009532940.tif 000035
に従って設定される。ステップ４２４で、トラフィック分割比αを使用して、すべてのノードｉについて、経路Ｐｉ上でαＲｉフロー量が送信され、すべてのノードｊについて、αＣｊフロー量が経路Ｑｊ上で送信される。ステップ４２６で、経路Ｐｉ上のフロー、および経路Ｑｊ上のフローに起因するリンク・サブセット
【数３４】
2009532940.tif 000036
の総使用（
【数３５】
2009532940.tif 000037
と示される）が、Ｎ内のすべてのノード
【数３６】
2009532940.tif 000038
について計算される。一実施形態では、総使用
【数３７】
2009532940.tif 000039
は、
【数３８】
2009532940.tif 000040
のように計算される。ステップ４２８で、すべてのノード
【数３９】
2009532940.tif 000041
についてリンク・サブセット
【数４０】
2009532940.tif 000042
の総使用（
【数４１】
2009532940.tif 000043
と示される）が、総使用
【数４２】
2009532940.tif 000044
を使用して増分される
【数４３】
2009532940.tif 000045
。
【００６９】
ステップ４３０で、Ｎ内のすべてのノード
【数４４】
2009532940.tif 000046
について、リンク重み
【数４５】
2009532940.tif 000047
が更新される。一実施形態では、リンク重み
【数４６】
2009532940.tif 000048
は、
【数４７】
2009532940.tif 000049
のように更新される。ステップ４３２で、ノード
【数４８】
2009532940.tif 000050
に関連するトラフィック分割比
【数４９】
2009532940.tif 000051
が、
【数５０】
2009532940.tif 000052
だけ増分される。ステップ４３４で、制約（または、多制約、図例の双対実現可能性制約の場合には、それぞれの制約）が満たされるかどうか判断される。制約が満たされない場合は、方法４００は、ステップ４０６に戻り、その時点で、制約を満たそうとして、方法４００のかなりの部分が繰り返される。制約が満たされる場合、方法４００は、ステップ４３６に進む。
【００７０】
ステップ４３６で、スケーリング・ファクタが計算される。一実施形態ではスケーリング・ファクタは、（アルゴリズムが、残余リンク容量ではなく、元のリンク容量を使用しているので）各リンク上の容量制約に違反が生じる可能性があるために計算される。この実施形態では、各リンク上の容量制約の違反を正すために、トラフィック分割比αは、リンク容量制約に従うようにスケールダウンされてもよい。一実施形態では、スケーリング・ファクタは、
【数５１】
2009532940.tif 000053
のように計算されてもよい。
【００７１】
ステップ４３８で、すべてのノードｋ∈Ｎについて、最適なトラフィック分割比αｋが計算される。一実施形態では、最適トラフィック分割比αは、
【数５２】
2009532940.tif 000054
のように計算される。トラフィック分割比
【数５３】
2009532940.tif 000055
がリンク容量制約に違反しない一実施形態では、ステップ４３６および４３８が省略されてもよい。ステップ４４０で、方法４００は、終了する。本明細書に述べられるように、一実施形態では、最適トラフィック分割比αｋは、トラフィック分割比αｋが決定される特定のルーティング・プロトコルについて各リンクｅに関連する固定トラフィック容量を決定するために、各ノードｋに関連する入口トラフィック容量および出口トラフィック容量と併せて使用されてもよい。この実施形態では、ルーティング・プロトコル、および関連する固定トラフィック容量が、リンク送信スケジュールの生成のために使用されてもよい。
【００７２】
一実施形態では、本発明は、様々な異なるサービス・モデル内でアプリケーション・レベルのサービス品質保証を提供する際に高位層よって使用されるように適応された、ノード・レベルの、宛先を意識しないスループット・コミットメントを提供する。一実施形態では、本発明は、基本サービス・クラスを利用するアプリケーションがアプリケーションへのエンドツーエンドのサービス品質保証を提供するために帯域幅保証を使用し得るように帯域幅保証を提供する。基本サービス・クラスは、（１）トラフィック宛先がトラフィック・ソースで知られている、エンドツーエンドの帯域幅保証型サービスと、（２）トラフィック宛先がトラフィック・ソースで知られていない、帯域幅保証型のランデブー・ベースのサービスとを含んでもよい。本発明は、無線メッシュ・ネットワーク内でエンドツーエンド帯域幅保証型サービスと帯域幅保証型ランデブー・ベース・サービスをそれぞれ独立に、または同時に実装することを可能にする。
【００７３】
一般に、エンドツーエンド帯域幅保証型サービスは、より複雑なアプリケーションを実装するための基本要素を提供する。一実施形態では、ネットワーク内のノードのバッファ・サイズに関する仮定を行うことによって、帯域幅要件が、遅延または損失要件に変換されてもよい。一実施形態では、帯域幅保証型ユニキャスト・サービスが本発明を使用して提供されてもよく、無線メッシュ・ネットワークが、帯域幅保証されたポイントツーポイント・トラフィックをサポートすることが可能となる。一実施形態では、本発明を使用して、帯域幅保証型マルチキャスト・サービスが提供されてもよく、無線メッシュ・ネットワークが、帯域幅保証されたポイントツーマルチポイント・トラフィックをサポートすることが可能となる。一実施形態では、無線メッシュ・ネットワーク内のノード上で開始しまたは終了し得る帯域幅保証された接続の総数への自然制約が存在し得る。本明細書では主として一方向接続に関して述べたが、本発明は、双方向接続に対処するために使用されてもよい。
【００７４】
一般に、帯域幅保証型ランデブー・サービスは、トラフィック・ソースとトラフィック宛先が分離されるランデブー・ベース通信を使用する。一実施形態では、（たとえば、インターネット間接基盤（ｉ３）から開発された）ランデブー・ベース通信において、ソース・ノードは、論理識別子を使用してランデブー・ノード（すなわち中間ノード）にパケットを送信し、宛先ノードは、論理識別子に送信されたパケットへの関心を表す。この実施形態では、無線メッシュ・ネットワークを介したソース・ノードと宛先ノードの間の通信は、ランデブー・ノードを介して行われる。一実施形態では、単一の無線メッシュ・ネットワーク内で、ソース・ノードとランデブー・ノードの間、ランデブー・ノードと宛先ノードの間でパケットをルーティングするのにピア・ツー・ピア・ルーティング・プロトコル（たとえばＣｈｏｒｄ）は不要である。
【００７５】
一実施形態では、本発明は、ネットワーク・スループットを最大にするために、無線メッシュ・ネットワーク内のランデブー・ノードの最適位置、ならびに無線メッシュ・ネットワーク内のすべてのノードと、無線メッシュ・ネットワーク内のすべてのランデブー・ノードの間の通信経路を決定する。こうした一実施形態では、本発明は、（ベスト・エフォート型サービスであるｉ３とは異なり）帯域幅保証されたランデブー・ベースの通信サービスをサポートする。一実施形態では、本発明を使用するランデブー・ベース基盤上で、マルチキャスト、エニーキャスト、モビリティおよび類似の機能、ならびにその様々な組合せがサポートされてもよい。
【００７６】
一実施形態では、ランデブー・ベース通信をサポートするために、ソース・ノードからランデブー・ノードへのトラフィックは、（ソース・ノード上で、パケットに関連する宛先ノードが知られていないので）宛先ノードに依存することができない。一実施形態では、ランデブー・ベース通信をサポートするために、ソース・ノードからランデブー・ノードへのトラフィック、ならびにランデブー・ノードから宛先ノードへのトラフィックは、帯域幅保証された経路に沿ってルーティングされなければならない。こうした一実施形態では、再構成を回避するために、帯域幅保証された経路は、トラフィック・パターンの変化に応答してルーティング変更することができず、関連するノード保証制約に従って、すべての可能なトラフィック・パターンに対処できるほど十分な帯域幅を有さなければならない。
【００７７】
本明細書では主として特定の制約（使用コミットメント・ベクトルβ）に関して述べたが、一実施形態では、本発明は、高度なリンク干渉制約、多重チャネル、多重アンテナ、ダイバーシチ要件を伴うルーティングなど、ならびにその様々な組合せについて説明するように拡張されてもよい。こうした実施形態では、ネットワーク・リンク上の固定トラフィック容量をもたらす最適なトラフィック分割比を決定するために必要なそれぞれのアルゴリズムは制約に応じて変化することがあるが、ネットワーク・リンクは依然として、固定トラフィック容量の移送を行い、それによって動的リンク送信スケジューリングの必要性が取り除かれる。一実施形態では、本発明は、無線メッシュ・ネットワーク上のスループットが保証されたオーバーレイ・サービスを提供するなど、トラフィック・ソースでトラフィック宛先が知られ得ない構成に拡張されてもよい。
【００７８】
図５は、本明細書に述べられた諸機能を実施する際に使用するのに適した汎用コンピュータのハイレベル・ブロック図を示している。図５に示されるように、システム５００は、プロセッサ要素５０２（たとえばＣＰＵ）と、メモリ５０４（たとえばランダム・アクセス・メモリ（ＲＡＭ：ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ）および／または読取り専用メモリ（ＲＯＭ：ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ））と、リンク送信スケジューラ・モジュール５０５と、様々な入／出力装置５０６（たとえば、それだけに限らないがテープ・ドライブ、フロッピー（登録商標）・ドライブ、ハード・ディスク・ドライブまたはコンパクト・ディスク・ドライブを含めた記憶装置、受信機、送信機、スピーカ、ディスプレイ、出力ポートおよびユーザ入力装置（キーボード、キーパッド、マウスなど）とを含む）。
【００７９】
本発明は、ソフトウェア、および／またはソフトウェアとハードウェアの組合せで、たとえば特定用途向け集積回路（ＡＳＩＣ：ａｐｐｌｉｃａｔｉｏｎ  ｓｐｅｃｉｆｉｃ  ｉｎｔｅｇｒａｔｅｄ  ｃｉｒｃｕｉｔ）、汎用コンピュータ、または他の任意のハードウェア等価物を使用して実装されてもよいことに留意されたい。一実施形態では、このリンク送信スケジューラ・プロセス５０５は、上記で論じられた諸機能を実施するために、メモリ５０４にロードし、プロセッサ５０２によって実行することができる。したがって、本発明のリンク送信スケジューラ・プロセス５０５（関連するデータ構造体を含む）は、コンピュータ読取り可能媒体または搬送波、たとえばＲＡＭメモリ、磁気もしくは光ドライブまたはディスケットなどに格納することができる。
【００８０】
本発明の教示を組み込む様々な実施形態が本明細書に示され、詳細に述べられたが、当業者は、これらの教示をやはり組み込む他の多くの様々な実施形態を容易に考案することができる。
【図面の簡単な説明】
【００８１】
【図１】通信ネットワークのハイレベル・ブロック図である。
【図２】本発明の一実施形態による方法を示す図である。
【図３】本発明の一実施形態による方法を示す図である。
【図４】本発明の一実施形態による方法を示す図である。
【図５】本明細書に述べられた諸機能を実施する際に使用するのに適した汎用コンピュータのハイレベル・ブロック図である。
【図１】
2009532940.tif 000056
【図２】
2009532940.tif 000057
2009532940.tif 000058
【図３】
2009532940.tif 000059
2009532940.tif 000060
【図４Ａ】
2009532940.tif 000061
【図４Ｂ】
2009532940.tif 000062
【図５】
2009532940.tif 000063
【手続補正書】
【提出日】平成20年11月13日(2008.11.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
リンク送信スケジュールを生成する方法であって、
複数の各無線リンクのそれぞれに関連する固定トラフィック容量をルーティング・アルゴリズムに従って決定するステップと、
前記ルーティング・アルゴリズムおよび前記決定された固定トラフィック容量を使用して、前記無線リンクのそれぞれを使用してトラフィックが送信される少なくとも１つの条件を含む前記リンク送信スケジューリングを生成するステップとを含み、前記リンク送信スケジュールが、動的トラフィック変化の間、実質的に固定されたままであるように適応される、方法。
【請求項２】
前記固定トラフィック容量を決定するステップが、
前記それぞれのネットワーク・リンクの前記固定トラフィック容量を確立するように前記ルーティング・アルゴリズムを構成するように適応された少なくとも１つのルーティング・パラメータを決定するステップを含む、請求項１に記載の方法。
【請求項３】
前記少なくとも１つのルーティング・パラメータが、少なくとも１つのスケジューリング制約を満たすやり方で決定される、請求項２に記載の方法。
【請求項４】
前記ルーティング・アルゴリズムが、
複数のノードのそれぞれがトラフィックを複数の各トラフィック分割比に従って前記ノードのそれぞれに分配する第１の段階と、
前記ノードのそれぞれが前記第１段階の間に受信されたトラフィックを、前記トラフィックの宛先ノードを含む前記ノードの選択されたノードにルーティングする第２の段階とを含む２段階ルーティング・アルゴリズムであり、
前記少なくとも１つのルーティング・パラメータを決定するステップが、前記ノードのそれぞれに関連する前記各トラフィック分割比を決定するステップを含む、請求項２に記載の方法。
【請求項５】
前記固定トラフィック容量を決定するステップが、
各ノードに関連する入口トラフィック容量を決定するステップと、
各ノードに関連する出口トラフィック容量を決定するステップと、
各ノードに関連する複数のトラフィック分割比を決定するステップと、
前記入口トラフィック容量、前記出口トラフィック容量および前記トラフィック分割比を使用して前記固定トラフィック容量を決定するステップとを含む、請求項１に記載の方法。
【請求項６】
リンク送信スケジュールを生成する装置であって、
複数の各無線リンクのそれぞれに関連する固定トラフィック容量をルーティング・アルゴリズムに従って決定する手段と、
前記ルーティング・アルゴリズムおよび前記決定された固定トラフィック容量を使用して、前記無線リンクのそれぞれを使用してトラフィックが送信される少なくとも１つの条件を含む前記リンク送信スケジューリングを生成する手段とを含み、
前記リンク送信スケジュールが、動的トラフィック変化の間、実質的に固定されたままであるように適応される、装置。
【請求項７】
前記固定トラフィック容量を決定する前記手段が、
前記それぞれのネットワーク・リンクの前記固定トラフィック容量を確立するように前記ルーティング・アルゴリズムを構成するように適応された少なくとも１つのルーティング・パラメータを決定する手段を含む、請求項６に記載の装置。
【請求項８】
前記少なくとも１つのルーティング・パラメータが、少なくとも１つのスケジューリング制約を満たすやり方で決定される、請求項７に記載の装置。
【請求項９】
固定トラフィック容量を決定する前記手段が、
各ノードに関連する入口トラフィック容量を決定する手段と、
各ノードに関連する出口トラフィック容量を決定する手段と、
各ノードに関連する複数のトラフィック分割比を決定する手段と、
前記入口トラフィック容量、前記出口トラフィック容量および前記トラフィック分割比を使用して前記固定トラフィック容量を決定する手段とを含む、請求項６に記載の装置。
【請求項１０】
ルーティング・アルゴリズム、および複数の各ネットワーク・リンクに関連する複数の固定トラフィック容量を使用して決定されたリンク送信スケジュールを受信するステップであって、前記固定トラフィック容量は前記ルーティング・アルゴリズムに従って決定され、前記リンク送信スケジュールが、前記ネットワーク・リンクのそれぞれを介してトラフィックが送信される少なくとも１つの条件を定義し、前記リンク送信スケジュールが、動的トラフィック変化の間、実質的に固定されたままであるように適応される、ステップと、
前記ルーティング・アルゴリズムおよび前記リンク送信スケジュールを使用して前記ネットワーク・リンクを介してトラフィックを送信するステップとを含む方法。
【国際調査報告】
2009532940.tif 000064
2009532940.tif 000065
2009532940.tif 000066