(57)【要約】【課題】無線ネットワークにおける送信局のグループ分け及びマッピングのための方法と装置を提供する。【解決手段】同じグループの各送信局が同じ時間シンボルでサウンディング信号を送信するように、送信局をグループ分けして、無線ネットワークにおいて送信局をマッピングする方法である。無線ネットワークにおける送信局のグループ分け方法は、マッピングされていない各送信局の送信リンクの数に応じて、前記送信局を降順に並べ替える段階と、評価される送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づいて各送信局を判断する段階と、すべての送信リンクがマッピングされるか、最大数のサウンディングバンドを使用するまで、前記評価に基づき各送信局をグループに入れる段階と、すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れを繰り返す段階とを有する。【選択図】図１
2008228298.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークにおける送信局のマッピング方法であって、
同じグループの各送信局が同じ時間シンボルでサウンディング信号を送信するように、前記送信局をグループ分けする段階を有する方法。
【請求項２】
前記グループ分けする段階は、さらに、
マッピングされていない各送信局の送信リンクの数に応じて、前記送信局を降順に並べ替える段階と、
マッピングされていない送信リンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づき、各送信局を評価する段階と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じ時間シンボル中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる段階と、
すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れを繰り返す段階とを有する、請求項１に記載の方法。
【請求項３】
無線ネットワークにおける送信局のマッピング方法であって、
アルゴリズムに、マッピングする送信局の数を入力する段階と、
前記アルゴリズムに、前記送信局が送信するサウンディング信号のための、単一のサウンディングスロットで利用できる最大数のサウンディングバンドを入力する段階と、
前記送信局間のすべてのリンクをマッピングするのに必要なサウンディングスロットの前記総数を計算する段階と、
サウンディングスロットごとに前記送信局をグループ分けする段階とを有し、
同じグループの各送信局は同じサウンディングスロットにおいてサウンディング信号を送信する方法。
【請求項４】
前記グループ分けする段階は、さらに、
マッピングされていない各送信局のリンクの数に応じて、前記送信局を降順に並べ替える段階と、
マッピングされていないリンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていないリンクをいくつマッピングできるかに基づき、各送信局を評価する段階と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じサウンディングスロット中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる段階と、
すべての送信リンクがマッピングされるまで、各サウンディングスロットに対して並べ替え、評価、及びグループ入れを繰り返す段階とを有する、請求項３に記載の方法。
【請求項５】
無線ネットワークにおける送信局のグループ分け方法であって、
マッピングされていない各送信局の送信リンクの数に応じて、前記送信局を降順に並べ替える段階と、
マッピングされていない送信リンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づき、各送信局を評価する段階と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じ時間シンボル中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる段階と、
すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れを繰り返す段階とを有する方法。
【請求項６】
無線ネットワークにおける送信局のマッピングする装置であって、
同じグループの各送信局が同じ時間シンボルでサウンディング信号を送信するように、前記送信局をグループ分けする手段を有する装置。
【請求項７】
前記グループ分けする手段は、さらに、
マッピングされていない各送信局の送信リンクの数に応じて、前記送信局を降順に並べ替える手段と、
マッピングされていない送信リンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づき、各送信局を評価する手段と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じ時間シンボル中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる手段と、
すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れを繰り返す手段とを有する、請求項６に記載の装置。
【請求項８】
無線ネットワークにおける送信局のマッピング装置であって、
アルゴリズムに、マッピングする送信局の数を入力する手段と、
前記アルゴリズムに、前記送信局が送信するサウンディング信号のための、単一のサウンディングスロットで利用できる最大数のサウンディングバンドを入力する手段と、
前記送信局間のすべてのリンクをマッピングするのに必要なサウンディングスロットの前記総数を計算する手段と、
サウンディングスロットごとに前記送信局をグループ分けする手段とを有し、
同じグループの各送信局は同じサウンディングスロットにおいてサウンディング信号を送信する装置。
【請求項９】
前記グループ分けする手段は、さらに、
マッピングされていない各送信局のリンクの数に応じて、前記送信局を降順に並べ替える手段と、
マッピングされていないリンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていないリンクをいくつマッピングできるかに基づき、各送信局を評価する手段と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じサウンディングスロット中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる手段と、
すべての送信リンクがマッピングされるまで、各サウンディングスロットに対して並べ替え、評価、及びグループ入れを繰り返す手段とを有する、請求項８に記載の装置。
【請求項１０】
無線ネットワークにおける送信局のグループ分け装置であって、
マッピングされていない各送信局の送信リンクの数に応じて、前記送信局を降順に並べ替える手段と、
マッピングされていない送信リンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づき、各送信局を評価する手段と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じ時間シンボル中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる手段と、
すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れを繰り返す手段とを有する装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワークに関し、特に、無線ネットワークにおける送信局のグループ分け及びマッピングのための方法と装置に関する。
【背景技術】
【０００２】
［関連出願との相互参照］
この出願は、米国仮出願第６０／８９３，７０２号（発明の名称「マルチホップリレーネットワークにおけるＲＳ／ＢＳのグループ分けアルゴリズム」、出願日２００７年３月８日、発明者Chenxi  Zhu、Wei-Peng  Chen、Dorin  Viorel、及びJonathan  Agre、代理人事件整理番号１９７４．１０２２Ｐ）の優先権を主張するものである。上記仮出願はここに参照援用する。
【０００３】
無線通信ネットワークはますます多く使われるように成っている。無線通信ネットワークは一般的に基地局を含み、この基地局がその周辺にあるセルエリア（cell  area）をサービスする。移動局（携帯電話等）は、基地局のサービスエリア内にいる時、その基地局と通信することができる。ＩＥＥＥ８０２．１６標準等に基づく一部のタイプの無線通信ネットワークでは、ネットワーク内の移動局の「ラストマイル（last  mile）」の接続に関心の的になっている。
【０００４】
しかし、無線通信ネットワークにおいては、送受信アンテナ間のビルその他の障害物により妨害されて、シャドウイング（shadowing）等の効果により、サービスエリア内になっても基地局との通信ができないデッドゾーンが生じる。この問題を解決するため、ＯＦＤＭＡ（Orthogonal  Frequency  Division  Multiple  Access）ネットワークにおいては、中継局を利用して、ネットワーク内で動作している移動局と基地局との間の媒介（intermediaries）として動作させて、送信能力を強化している。このように、セルサービスエリア内の基地局に直接接続できない移動局は、基地局との直接リンク（場合によっては間接リンク）を有する中継局と最初に通信して、その基地局に間接的に接続することができる。
【発明の開示】
【課題を解決するための手段】
【０００５】
本発明の様々な実施形態によれば、同じグループの各送信局が同じ時間シンボルでサウンディング信号を送信するように、送信局をグループ分けして、無線マルチホップネットワークにおいて送信局をマッピングする方法が提供される。
【０００６】
本発明の様々な実施形態によれば、無線マルチホップネットワークにおける送信局のマッピング方法が提供される。該方法は、（ａ）アルゴリズムに、マッピングする送信局の数を入力する段階と、（ｂ）前記アルゴリズムに、前記送信局が送信するサウンディング信号のための、単一のサウンディングスロットで利用できる最大数のサウンディングバンドを入力する段階と、（ｃ）前記送信局間のすべてのリンクをマッピングするのに必要なサウンディングスロットの前記総数を計算する段階と、（ｄ）サウンディングスロットごとに前記送信局をグループ分けする段階とを有する。さらに、同じグループの各送信局は同じサウンディングスロットにおいてサウンディング信号を送信する。
【０００７】
本発明の様々な実施形態によれば、無線マルチホップネットワークにおける送信局のグループ分け方法が提供される。該方法は、（ａ）マッピングされていない各送信局の送信リンクの数に応じて、前記送信局を降順に並べ替える段階と、（ｂ）マッピングされていない送信リンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づき、各送信局を評価する段階と、（ｃ）前記評価に基づき、すべての送信リンクがマッピングされるか、同じ時間シンボル中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる段階と、（ｄ）すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れを繰り返す段階とを有する。
【０００８】
本発明の上記の実施形態は単なる例であり、本発明のすべての実施形態はこれらの例には限定されない。本発明の実施形態は、無線マルチホップネットワークには限定されず、シングルホップネットワークも含み得る。
【０００９】
本発明のその他の態様は、一部は以下の説明に記載してあり、一部はその説明から自明であり、一部は本発明の実施により分かるであろう。
【発明を実施するための最良の形態】
【００１０】
本発明の好ましい実施形態を詳細に参照する。これらの好ましい実施形態の例は添付した図面に示した。同じ要素には図面を通して同じ参照数字を付した。
【００１１】
例えば、ＩＥＥＥ８０２．１６ｊまたは８０２．１６ｍ標準のマルチホップ中継ネットワークでは、中継局の数が多いので通常のセルラーネットワークよりも干渉が激しい。１つの中継局がサウンディング信号（sounding  signal）を送り、他の中継局が各サウンディングスロット（sounding  slots）で測定を行う場合、ネットワークをマッピングするために必要なサウンディングスロットの数は中継局の数と同じになる。オーバーヘッドはネットワークのサイズとともに線形に増加する。このため、サウンディング方式（sounding  scheme）のスケーラビリティには厳しい制限がある。
【００１２】
本発明の様々な実施形態により、無線マルチホップネットワークにおける送信局のマッピング方法を提供する。ネットワーク内の多数の中継局（relay  stations）と１つ以上の基地局（base  stations）の間のチャネルリンク品質を推定するために、マッピングを行わねばならない。このマッピングにより、ネットワークは、その中の構成要素（entities）間の信号送信のために最適ルートを選択できる。アップリンクサウンディング（uplink  sounding）が、複数の中継局と基地局の間のチャネルゲインと干渉強度を推定する効果的な方法として提案されている。中継局は１つのチャネルで同時に送信と受信はできないので、どの中継局がどのサウンディングスロットとサウンディングバンドで送信し、他の中継局と基地局がそのサウンディング信号を受信して測定するか指示するスケジューリングが必要である。スケジュールの長さによりアップリンクサウンディング機構のオーバーヘッドが決まる。
【００１３】
このマッピング手順にはアップリンクサウンディングのプロセスが含まれる。対象の中継局は、同時に、基地局または他の中継局に一定の時間スロットと一定の周波数でサウンディング信号を送る。これらの基地局または他の中継局はその送信リンクの信号品質を測定できる。ネットワーク中の複数の中継局に同時にサウンディング信号を送信させれば効率的である。しかし、中継局は同時にサウンディング信号を送受信することは一般的にはできず、そのため様々な中継局間のリンクをマッピングすることはできない。
【００１４】
中継局などの送信局（transmission  stations）をグループ分けして、同じグループ中の各送信局が同じ時間シンボル（time  symbol）でサウンディング信号を送信すれば、ネットワーク全体を最短の時間でマッピングでき、オーバーヘッドが最小になる。そのため、各時間シンボルにおいてマッピング（map）できる中継局送信リンクの数が大きくなるので、サウンディングスロットの総数が減少する。各時間シンボルは、サウンド信号（sound  signals）の送信に使用され、ネットワークの標準規格に基づく、そのネットワークにおいて利用できる最小の時間スロットを表す。例えば、８０２．１６ｊネットワークにおける基地局のように、その局（station）がサウンディング信号を送信できないとき、その局は、他のネットワーク局から常にサウンディング信号を受信し、サウンディング信号を送信できるすべてのネットワーク局がサウンディング信号を送信した時に完全にマッピングされたと考える。グループ（送信スケジュール）を作った時、このような局を考える。サウンディング信号を送信できない２つの局の間のチャネルは、他の手段を用いて測定しなければならない。
【００１５】
これらの時間シンボルには、それぞれ、相異なる複数のサウンディングバンド（sounding  bands）が含まれ、そのため相異なる複数の中継局が同じ時間シンボルにおいて複数のサウンディング信号を送信できる。相異なる中継局からのサウンディング信号は相異なるサウンディングバンドで送信される。ある時間シンボルでサウンディング信号を送信しない中継局は、サウンディング信号を送信している中継局が送信した信号を受信して測定できる。このように、最小量の時間シンボルでネットワーク中の最大数の送信リンクをマッピングできる。
【００１６】
ある時間シンボル中のサウンディングバンドの数は、例えば、ＩＥＥＥ（Institute  of  Electrical  and  Electronics  Engineers）８０２．１６標準のネットワークで通常設けられているように、例えば、８個または１０個である。しかし、本発明は、時間シンボルごとのサウンディングバンドの具体的な数には限定されない。
【００１７】
図１は、本発明の一実施形態による、無線マルチホップネットワークにおける送信局のマッピングプロセスを示すフローチャートである。図１を参照して、ステップ１００において、マッピングする送信局の数と、その送信局により送信されるサウンディング信号のうちの１つのサウンディングスロットで利用できるサウンディングバンドの最大数とをアルゴリズムに入力する。次に、ステップ２００において、アルゴリズムが、入力値に基づき送信局間のすべてのリンクのマッピングに必要なサウンディングスロットの総数を計算する。
【００１８】
最後に、ステップ３００において、アルゴリズムが、サウンディングスロットごとに送信局をグループ分けし、同じグループの各送信局が同じサウンディングスロットでサウンディング信号を送信するようにする。さらに、一部の送信局をマッピングする必要がなければ、そのことを考慮して、サウンディンググループ（the  set  of  sounding  groups）を減らし、さらにオーバーヘッドを低減することができる。図１に示したマッピング方法を実行するアルゴリズムは、下で更に詳しく説明する。しかし、図１に示した方法は、ある特定のアルゴリズムを使用することに限定されるものではない。
【００１９】
図２は、本発明の様々な実施形態による、無線マルチホップネットワークにおける、上で説明した実施形態のステップ３００等における、送信局のグループ分けプロセスをさらに示すフローチャートである。図２を参照して、ステップ１０００において、マッピングされていない（unmapped）各送信局の送信リンクの数に応じて、送信局を降順に並べ替える。次に、ステップ２０００において、各送信局を評価するが、最初にマッピングされていない送信リンクの数が最も多い送信局から始める。この評価は、送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づき行う。この評価には、評価対象の送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるか判断する段階を含む。各送信局に対して、その送信局にサウンディング信号を送信させればより多くの送信リンクをマッピングできるとき、その送信局を目下の送信グループ（current  transmitting  group）に加える。そうでなければ、その送信局は信号を受信するだけにする。
【００２０】
上記の評価には、評価されている送信局を、送信グループに入れるのがよいのか、サウンディング信号を受信するだけにするのがよいのか、バランスを取る段階が含まれていてもよい。例えば、評価されている送信局が、すでに送信グループに入れられている他の送信局からサウンディング信号を受信できる場合、その送信局は受信する信号に基づいて送信リンクをマッピングする方がよく、それゆえ、目下の送信グループに入れる必要はない場合がある。さらに、一部の送信局をマッピングする必要がなければ、そのことを考慮して、サウンディンググループ（the  set  of  sounding  groups）を減らし、さらにオーバーヘッドを低減することができる。
【００２１】
次に、プロセスはステップ３０００に進み、各送信局を評価に基づいてグループに入れる。送信局は、すべての送信リンクがマッピングされるか、同じ時間シンボル中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、これらのグループに入れられている。最後に、ステップ４０００において、すべての送信リンクがマッピングされていなければ、すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れ（placing）を繰り返す。
【００２２】
図１、図２を参照して上に説明したように、本発明の様々な実施形態をアルゴリズムで実行できる。以下に示すのは、本発明の一実施形態によるアルゴリズムの実行例である。このアルゴリズムはコンピュータソフトウェアプログラムＭＡＴＬＡＢで実行した。
【００２３】
【数１】
2008228298.tif 000003
【００２４】
【数２】
2008228298.tif 000004
【００２５】
【数３】
2008228298.tif 000005
【００２６】
【数４】
2008228298.tif 000006
上記のアルゴリズムは、ＭＡＴＬＡＢで実行したが、図１に示したマッピング方法と、図２に示した送信局のグループ分け方法とを実行するアルゴリズムの一例である。しかし、本発明の実施形態は、特定のアルゴリズムには限定されず、アルゴリズムを実行するための特定のプログラム、コンピュータ等にも限定されない。
【００２７】
上記のアルゴリズムは、ＭＡＴＬＡＢにより実行できるが、値Ｎを入力として受け取る。ここで、Ｎはマッピングするネットワークのサイズである。この場合、Ｎはこの実施形態におけるネットワーク中の中継局の数を表す。基地局と中継局の間のマッピングは、中継局がサウンディング信号を送信し、１つ以上の基地局がそのサウンディング信号を受信した時に行われる。このアルゴリズムは、各時間シンボル及び／またはサウンディングスロットで使用できるサウンディングバンドの数も入力として受け取る。しかし、上記アルゴリズムはＷｉＭＡＸ中継局の実施形態のみに限定されるものではない。
【００２８】
上記アルゴリズムは行列ＴＴを出力する。この行列の各行は、同じサウンディングスロットでサウンディング信号を送信する中継局のセット（set）であり、行数はネットワーク全体のマッピングを行うのに必要なサウンディングスロットの数を表す。一部の中継局をマッピングする必要がなければ、上記のアルゴリズムはそのことを考慮して、マッピングを完了するのに必要なサウンディングスロットの総数は場合によっては減少する。同じサウンディングスロットで送信する１つのグループでは、Ｎ個の局間のマッピングプロセス全体をｃｅｉｌ（ｌｏｇ２（Ｎ））個のサウンディングスロットで完了できる。ここで、１つのサウンディングスロットの長さはシンボル数（最小は１）である。これは、図３のグラフに示されている。
【００２９】
上記の例は本発明の一実施形態によるアルゴリズムの実行例である。このアルゴリズムはコンピュータソフトウェアプログラムＭＡＴＬＡＢで実行した。しかし、本発明はこの例には限定されない。さらに、本発明は、コンピュータプログラムで実施されるアルゴリズムには限定されず、アルゴリズムを実行するためにＭＡＴＬＡＢを使用することには限定されない。
【００３０】
上記のアルゴリズムを使用して、本発明の様々な実施形態による、無線マルチホップネットワークにおける送信局のグループ分けとマッピングのプロセスを実行できる。このように、上記アルゴリズムは、基地局や基地局コントローラなどのネットワーク装置に実装でき、ネットワークのマッピングが必要な時にその装置により実行できる。しかし、本発明は、ＡＳＮ−ＧＷ（Access  Service  Network  Gateway）等の基地局または基地局コントローラ等の装置に実装されたアルゴリズムには限定されない。ＡＳＮ−ＧＷは、ネットワークスケジューラＳＷを格納したＷｉＭＡＸネットワークの構成要素である。
【００３１】
本発明の様々な実施形態により、事前に実行されるアルゴリズムが提供され、そのアルゴリズムの結果は基地局やＡＳＮ−ＧＷ等のネットワーク装置にデータとして記憶される。データには、最大可能ネットワークサイズまでの相異なるネットワークサイズに基づきすでに計算された、送信局のグループ分けが含まれる。それゆえ、あるサイズのネットワークをマッピングするために、上記アルゴリズムは、そのネットワークサイズに対して記憶された値を参照するだけでよい。非限定的な例として、この結果はアダマール符号またはその変形の１つと同じであり得る。
【００３２】
非限定的な例として、上記のアルゴリズムを実行して、相異なるネットワークサイズ（Ｎ：１から最大可能ネットワークサイズまで）に対する結果のデータを行列ＴＴ（Ｎ）のセットとしてＡＳＮ−ＧＷに格納しておくことができる。それゆえ、あるサイズＭのネットワークをマッピングするために、ＡＳＮ−ＧＷは格納された行列ＴＴ（Ｍ）を参照し、中継局サウンディンググループとしてＴＴ（Ｍ）の各行を使用する。しかし、本発明は、基地局または基地局コントローラ等の装置で実施されたアルゴリズムには限定されず、相異なるネットワークサイズに基づいて予め計算された送信局のグループ分けを格納しておくことには限定されない。
【００３３】
本発明の様々な実施形態により、事前に実行されるアルゴリズムと、基地局や基地局コントローラ等のネットワーク装置にデータとして格納されたそのアルゴリズムの結果とが提供される。データには、Ｎ＝２、４、８、．．．２ｋ、．．．２Ｍのネットワークサイズに基づき計算された送信局のグループ分けが含まれている。ここで、２Ｍは最大可能ネットワークよりも大きい。それゆえ、例えば、Ｌ個のノードを有するネットワークをマッピングするために、格納された行列ＴＴ（２ｋ）を使用する。ここで、ｋは、２ｋがＬ以上になる最小の整数である。このように、総数Ｌの送信局をマッピングするために必要なサウンディングスロットの数は、ｌｏｇ２（Ｌ）以上の最小の整数（the  nearest  integer）である。しかし、本発明は、基地局または基地局コントローラ等の装置で実施されるアルゴリズムには限定されず、Ｎ＝２、４、８、．．．２ｋ、．．．２Ｍのネットワークサイズに基づいて予め計算された送信局のグループ分けを格納しておくことには限定されない。ここで、２Ｍは最大可能ネットワークより大きい。
【００３４】
本発明の様々な実施形態により、事前に実行されるアルゴリズムと、基地局や基地局コントローラ等のネットワーク装置にデータとして格納されたそのアルゴリズムの結果とが提供される。上記データには、前の例に基づき予め計算された送信局のグループ分けが含まれる。ただし、Ｎは正の整数であればいくつでもよい。しかし、本発明は、基地局または基地局コントローラ等の装置で実施されるアルゴリズムには限定されず、Ｎ＝任意の正の整数のネットワークサイズに基づいて予め計算された送信局のグループ分けを格納しておくことには限定されない。
【００３５】
上記のアルゴリズムは、例えば、ＭＡＴＬＡＢ等のコンピュータソフトウェアプログラムにより実行されてもよい。しかし、本発明は、アルゴリズムや、アルゴリズムを実行する特定のコンピュータプログラムには限定されない。
【００３６】
本発明の様々な実施形態により、図４に示したネットワーク等の無線マルチホップネットワークにおける中継局のグループ分け及びマッピング方法が提供される。図４はネットワークで動作する２つの中継局を含む、セル間トポロジーの一例を示す図である。上記のネットワークセルは、基地局（ＢＳ）１５、第１の中継局（ＲＳ１）５５、第２の中継局（ＲＳ２）６５、第１の移動局（ＭＳ１）２５、第２の移動局（ＭＳ２）３５、及び第３の移動局（ＭＳ３）４５を含む。この例では、一実施形態のアルゴリズムを実行して、その結果が基地局１５に格納され、送信リンク３７、４７、５７がマッピングされる。しかし、本発明は、特定の場所でアルゴリズムが実行され、またはその結果が格納されることには限定されない。
【００３７】
図４はＯＦＤＭＡネットワークにおいて動作する２つの中継局を含むセル間トポロジーの一例を示す図である。本発明の様々な実施形態は、図４に例示したように単一の基地局と２つの中継局と３つの移動局とのみを含むＯＦＤＭＡネットワークには限定されず、任意台数の基地局、中継局、移動局をサポートするいかなる無線通信ネットワークも含み得る。
【００３８】
本発明は、ＯＦＤＭＡネットワーク、特にＩＥＥＥ８０２．１６標準に基づくネットワークにおける無線マルチホップネットワークにおける中継局のグループ分け及びマッピング方法に関する。しかし、本発明は、中継局や、特定のタイプのネットワークや特定の標準のネットワークには限定されず、本発明の様々な方法は相異なる様々なタイプのアプリケーションに適用できる。さらに、本発明は、無線マルチホップネットワークには限定されず、シングルホップネットワークも含み得る。
【００３９】
本発明は、修正及び拡張も含めてＩＥＥＥ８０２．１６標準（ＩＥＥＥ８０２．１６ｅ、ＩＥＥＥ８０２．１６ｊ、ＩＥＥＥ８０２．１６ｍ等も含む）に関する。ＩＥＥＥ８０２．１６標準及びその拡張はここにその全体を参照援用する。
【００４０】
本発明の少数の好ましい実施形態を図示して説明したが、当業者には言うまでもなく、本発明の原理と精神から逸脱することなくこれらの実施形態に変更を加えることができる。本発明の範囲は、付記及びその均等の範囲により規定される。
【００４１】
なお、一部の実施形態を整理すると以下の通りである。
（付記１）  無線ネットワークにおける送信局のマッピング方法であって、
同じグループの各送信局が同じ時間シンボルでサウンディング信号を送信するように、前記送信局をグループ分けする段階を有する方法。
（付記２）  前記方法はアルゴリズムにより実行される、付記１に記載の方法。
（付記３）  前記アルゴリズムは、マッピングする送信局の総数と、単一の時間シンボルにおいてサウンディング信号の送信に利用できるサウンディングバンドの数とを入力として受け取る、付記２に記載の方法。
（付記４）  総数Ｎの送信局をマッピングするために必要な時間シンボルの数は、ｌｏｇ２（Ｎ）以上の最小の整数である、付記３に記載の方法。
（付記５）  前記アルゴリズムは前記マルチホップネットワーク中の基地局で実施される、付記２に記載の方法。
（付記６）  前記グループ分けする段階は、さらに、
マッピングされていない各送信局の送信リンクの数に応じて、前記送信局を降順に並べ替える段階と、
マッピングされていない送信リンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づき、各送信局を評価する段階と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じ時間シンボル中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる段階と、
すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れを繰り返す段階とを有する、付記１に記載の方法。
（付記７）  前記方法はアルゴリズムにより実行される、付記６に記載の方法。
（付記８）  前記アルゴリズムは、マッピングする送信局の総数と、単一の時間シンボルにおいてサウンディング信号の送信に利用できるサウンディングバンドの数とを入力として受け取る、付記７に記載の方法。
（付記９）  総数Ｎの送信局をマッピングするために必要な時間シンボルの数は、ｌｏｇ２（Ｎ）以上の最小の整数である、付記８に記載の方法。
（付記１０）  前記アルゴリズムは前記マルチホップネットワーク中の基地局で実施される、付記６に記載の方法。
（付記１１）  前記ネットワークはＩＥＥＥ８０２．１６標準のネットワークである、付記１に記載の方法。
（付記１２）  無線ネットワークにおける送信局のマッピング方法であって、
アルゴリズムに、マッピングする送信局の数を入力する段階と、
前記アルゴリズムに、前記送信局が送信するサウンディング信号のための、単一のサウンディングスロットで利用できる最大数のサウンディングバンドを入力する段階と、
前記送信局間のすべてのリンクをマッピングするのに必要なサウンディングスロットの前記総数を計算する段階と、
サウンディングスロットごとに前記送信局をグループ分けする段階とを有し、
同じグループの各送信局は同じサウンディングスロットにおいてサウンディング信号を送信する方法。
（付記１３）  前記グループ分けする段階は、さらに、
マッピングされていない各送信局のリンクの数に応じて、前記送信局を降順に並べ替える段階と、
マッピングされていないリンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていないリンクをいくつマッピングできるかに基づき、各送信局を評価する段階と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じサウンディングスロット中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる段階と、
すべての送信リンクがマッピングされるまで、各サウンディングスロットに対して並べ替え、評価、及びグループ入れを繰り返す段階とを有する、付記１２に記載の方法。
（付記１４）  総数Ｎの送信局をマッピングするために必要なサウンディングスロットの数は、ｌｏｇ２（Ｎ）以上の最小の整数である、付記１３に記載の方法。
（付記１５）  各サウンディングスロットは単一時間シンボルの長さを有する、付記１４に記載の方法。
（付記１６）  前記方法はアルゴリズムにより実行される、付記１４に記載の方法。
（付記１７）  無線ネットワークにおける送信局のグループ分け方法であって、
マッピングされていない各送信局の送信リンクの数に応じて、前記送信局を降順に並べ替える段階と、
マッピングされていない送信リンクの数が最も多い送信局から始めて、送信局にサウンディング信号を送信させたら、マッピングされていない送信リンクをいくつマッピングできるかに基づき、各送信局を評価する段階と、
前記評価に基づき、すべての送信リンクがマッピングされるか、同じ時間シンボル中のサウンディング信号を送信できる最大数のサウンディングバンドが使用されるまで、各送信局をグループに入れる段階と、
すべての送信リンクがマッピングされるまで、各時間シンボルに対して並べ替え、評価、及びグループ入れを繰り返す段階とを有する、
（付記１８）  総数Ｎの送信局をマッピングするために必要な時間シンボルの数は、ｌｏｇ２（Ｎ）以上の最小の整数である、付記１７に記載の方法。
（付記１９）  前記方法はアルゴリズムにより実行される、付記１８に記載の方法。
（付記２０）  前記ネットワークはＩＥＥＥ８０２．１６標準のネットワークである、付記１７に記載の方法。
【図面の簡単な説明】
【００４２】
【図１】本発明の一実施形態による、無線マルチホップネットワークにおける送信局のマッピング方法を示すフローチャートである。
【図２】本発明の一実施形態による、無線マルチホップネットワークにおける送信局のグループ分け方法を示すフローチャートである。
【図３】本発明の一実施形態による、様々なサイズのネットワークのマッピングを完了するのに要するサウンディングスロット数を示すグラフである。
【図４】ＩＥＥＥ８０２．１６標準に基づくＯＦＤＭＡネットワークで操作する２つの中継局を含む、セル間トポロジーの一例を示す図である。
【符号の説明】
【００４３】
１５  基地局
２５、３５、４５  移動局
５５、６５  中継局
３７、４７、５７  送信リンク
【図１】
2008228298.tif 000007
【図２】
2008228298.tif 000008
【図３】
2008228298.tif 000009
【図４】
2008228298.tif 000010