(57)【特許請求の範囲】
【請求項１】
同時に複数のビームを形成するスマートアンテナを備えた無線基地局における下り送信先の複数の移動局を選択する無線チャネルスケジューリング方法であって、
前記無線基地局のカバレッジ内に位置する移動局に関して、前記ビームを向ける対象として選択可能な移動局の組み合わせを求めるグループ化過程と、
このグループ化過程で求められた複数のグループの中から、通信サービス要求条件に最も合致するグループを選択し、このグループに含まれる移動局を同時に下り送信する送信先として決定する最良グループ選択過程と、
を含み、
前記グループ化過程は、
移動局間の方位角差が所定角度以上であることを前記移動局の組み合わせの条件としてグループ化し、前記グループ化した中から通信品質が良くなるグループを評価関数に基づき選択する処理を含み、
前記所定角度は、隣接して形成されるビーム間の干渉が通信品質に影響しないような値として決定されることを特徴とする無線チャネルスケジューリング方法。
【請求項２】
同時に複数のビームを形成するスマートアンテナを備えた無線基地局における下り送信先の複数の移動局を選択する無線チャネルスケジューリング方法であって、
前記無線基地局のカバレッジ内に位置する移動局に関して、前記ビームを向ける対象として選択可能な移動局の組み合わせを求めるグループ化過程と、
このグループ化過程で求められた複数のグループの中から、通信サービス要求条件に最も合致するグループを選択し、このグループに含まれる移動局を同時に下り送信する送信先として決定する最良グループ選択過程と、
を含み、
前記最良グループ選択過程は、
同時に下り送信する移動局についての総合的な通信品質が最もよくなるグループを選択し、
前記選択対象の１グループ内に含まれる移動局の通信品質の指標となる評価関数値の総和を算出し、この総和が最大であるグループを前記総合的な通信品質が最もよくなるグループとして決定する処理をさらに含むことを特徴とする無線チャネルスケジューリング方法。
【請求項３】
同時に複数のビームを形成するスマートアンテナを備えた無線基地局における下り送信先の複数の移動局を選択する無線チャネルスケジューリング方法であって、
前記無線基地局のカバレッジ内に位置する移動局に関して、前記ビームを向ける対象として選択可能な移動局の組み合わせを求めるグループ化過程と、
このグループ化過程で求められた複数のグループの中から、通信サービス要求条件に最も合致するグループを選択し、このグループに含まれる移動局を同時に下り送信する送信先として決定する最良グループ選択過程と、
を含み、
前記最良グループ選択過程は、
所定低伝送レートの移動局に関して、同時に下り送信先の移動局として選択する台数を所定上限値以下に抑える処理を含むことを特徴とする無線チャネルスケジューリング方法。
【請求項４】
前記グループ化過程は、
前記無線基地局のカバレッジ内に位置する移動局を頂点で表現し、同時に選択することができない移動局間を枝で結ぶように表現したグラフにおいて、該グラフ内に存在する頂点集合の中から、極大独立頂点集合を求めることによって、前記組み合わせを得る処理を含むことを特徴とする請求項１から請求項３のいずれか１項に記載の無線チャネルスケジューリング方法。
【請求項５】
前記最良グループ選択過程は、
同時に下り送信する移動局についての総合的な通信品質が最もよくなるグループを選択する処理を含むことを特徴とする請求項１または請求項３に記載の無線チャネルスケジューリング方法。
【請求項６】
前記最良グループ選択過程は、
グループ内の移動局数が最大であるグループを選択する処理を含むことを特徴とする請求項１または請求項３に記載の無線チャネルスケジューリング方法。
【請求項７】
前記最良グループ選択過程の処理を実行する周期よりも長い周期で、前記グループ化過程の処理を行うことを特徴とする請求項１乃至請求項６のいずれかの項に記載の無線チャネルスケジューリング方法。
【請求項８】
前記無線基地局のカバレッジを複数の領域に分割するエリア分割過程をさらに含み、
前記分割された領域毎に、前記グループ化過程の処理と前記最良グループ選択過程の処理を実行することを特徴とする請求項１乃至請求項７のいずれかの項に記載の無線チャネルスケジューリング方法。
【請求項９】
前記エリア分割過程は、
前記複数の領域についての移動局の存在密度を均等化するように、前記カバレッジを分割する処理を含むことを特徴とする請求項８に記載の無線チャネルスケジューリング方法。
【請求項１０】
前記エリア分割過程は、
前記複数の領域についての境界を、動的に変更する処理を含むことを特徴とする請求項８または請求項９に記載の無線チャネルスケジューリング方法。
【請求項１１】
同時に複数のビームを形成するスマートアンテナを備えた無線基地局における下り送信先の複数の移動局を選択する移動局選択処理を行う無線チャネルスケジューリング装置であって、
請求項１乃至請求項１０のいずれかに記載の無線チャネルスケジューリング方法により、前記移動局選択処理を実行する処理手段を具備することを特徴とする無線チャネルスケジューリング装置。
【請求項１２】
同時に複数のビームを形成するスマートアンテナを備えた無線基地局と前記無線基地局のカバレッジ内に位置する複数の移動局とからなる移動通信システムであって、
前記無線基地局は、請求項１乃至請求項１０のいずれかに記載の無線チャネルスケジューリング方法により、下り送信先の複数の移動局を選択することを特徴とする移動通信システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、同時に複数の移動局と通信可能なスマートアンテナ基地局に用いて好適な無線チャネルスケジューリング方法及びその装置、該無線チャネルスケジューリング方法を用いた移動通信システムに関する。
【０００２】
【従来の技術】
近年、インターネットの普及などにより、移動通信においても高速なデータ通信の実現が要望されている。そして、この要望に応えるべく、高速なパケット通信によりデータ転送可能な無線パケット移動通信システムが実用化されつつある。このような無線パケット移動通信システムとしては、例えば、標準化団体「３ＧＰＰ２」による技術規格書「C.S0024 cdma2000 High Rate Packet Data Air Interface Specifications」に準拠した１ｘＥＶ−ＤＯシステムが知られている。
【０００３】
また、移動通信の需要は、益々増加しており、移動通信システムにおける一基地局当りの移動局収容能力の向上が急務となっている。この課題を解決するために、スマートアンテナを適用した移動通信システムが知られている。スマートアンテナとは、任意の移動局に限定してビームを指向するものである。このスマートアンテナの技術は、例えば、科学技術出版社刊行の「アレーアンテナによる適応信号処理」に記載されている。
【０００４】
図１４は、スマートアンテナを備えた基地局と移動局からなる移動通信システムについて説明するための図である。この図１４のシステムでは、スマートアンテナを備えた基地局（スマートアンテナ基地局）１００が、３台の移動局１０１〜１０３に向けて個別に、スマートアンテナのビームＡ１〜Ａ３を同時に形成している。スマートアンテナ基地局１００は、これらビームＡ１〜Ａ３の到達範囲内にそれぞれ位置する移動局１０１〜１０３と同時に通信することが可能である。
【０００５】
他方、セクタアンテナを適用した移動通信システムも知られている。この移動通信システムにおいては、基地局のアンテナ指向性を予め２つ以上の所定数のセクタに分割する。このセクタは通常の基地局が提供するセルに対応する。また、基地局はそのセクタ数分のセクタアンテナ基地局設備を備えている。
【０００６】
図１５は、セクタアンテナを備えた基地局と移動局からなる移動通信システムについて説明するための図である。この図１５のシステムでは、３セクタ分のセクタアンテナ用基地局設備を備えた基地局（３セクタ基地局）２００が、セクタアンテナのビームＢ１〜Ｂ３を同時に形成している。３セクタ基地局２００は、これらビームＢ１〜Ｂ３の到達範囲内にそれぞれ位置する移動局１０１〜１０３と同時に通信することが可能である。
【０００７】
上記スマートアンテナを適用した場合とセクタアンテナを適用した場合とでは、（１）および（２）に示す点においてスマートアンテナの方が優れている。
（１）スマートアンテナを適用した方が、同一基地局に収容された移動局相互間の干渉量が少ない。
この理由は、スマートアンテナ基地局がビーム毎にヌル（ビームの利得が少ない方向）を設定可能なことにある。すなわち、ビーム毎に、電波が伝わってほしくない方向を指定することができる。これにより、スマートアンテナ基地局が、同時に形成するビーム間で互いにヌル方向を向け合うことによって、移動局間の干渉を軽減することができるようになる。
【０００８】
一方、セクタ基地局は、ヌル方向を利用することができない。したがって、隣り合うセクタ間の境界付近ではビームが互いに干渉し合い、この結果、ＣＩＲ（希望波信号電力対干渉波信号電力比）が劣化して、例えば、伝送速度が低下し、通信品質が悪くなる。このために、多数のセクタに分割して一セクタ当りの領域が狭くなると、セクタ間の境界付近に移動局が位置する確立が高くなり、良好な通信品質を維持することが可能な範囲が少なくなってしまう。これは、多数のセクタに分割して移動局収容能力の向上を図る際の障害となる。
【０００９】
（２）スマートアンテナを適用した場合、基地局内のハンドオーバが発生しない。
この理由は、スマートアンテナ基地局が移動局の位置に応じてビームを向ける方向を自在に設定可能なことにある。したがって、移動局がスマートアンテナ基地局のカバレッジ（サービス区域）内に位置する限り、基地局内のハンドオーバは発生しない。
【００１０】
一方、セクタ基地局が形成するセクタアンテナのビームは、固定の領域を覆うものであって移動するものではない。したがって、移動局が移動してセクタ間を横断する度に、基地局内のセクタ間ハンドオーバが発生する。このセクタ間ハンドオーバは、セクタ数が増加するほど発生しやすくなり、これによって、ハンドオーバ用制御信号転送量の増加、セクタ切替に伴う通信遅延量の増加などが生じる。さらに、ハンドオーバ処理用の基地局リソース（ＣＰＵ処理能力、メモリ量など）の消費量が増える。これも、多数のセクタに分割して移動局収容能力の向上を図る際の障害となる。
【００１１】
このように、セクタアンテナを適用した場合、セクタ分割数の増加に伴って、通信品質の悪化や基地局にかかる負荷の増大という問題が発生するので、一基地局当りの移動局収容能力を思うように向上させることができない。実際には、一基地局当り６セクタ程度が上限と言われている。
【００１２】
一方、スマートアンテナを適用した場合には、例えば、基地局から見て１ビームの幅を３０度にすると、最大１２ビームまで同時に形成することが可能であり、セクタアンテナを適用した場合に比べて２倍の移動局収容能力を有することになる。さらに、移動局相互間の干渉量はヌル形成によって少なくすることができるので、通信品質面においても良好な状態を維持することが可能である。
これらの理由から、移動通信システムにおいて、一基地局当りの移動局収容能力を向上させるためには、スマートアンテナを適用することが有効である。
【００１３】
【発明が解決しようとする課題】
ところで、スマートアンテナを無線パケット移動通信システムに適用するためには、スマートアンテナに対応したスケジューラ機能が必要である。スケジューラ機能とは、無線パケット移動通信システムにおいて無線チャネルを移動局に割当てる機能である。具体的には、基地局のカバレッジ内に多数の移動局が位置しており、且つ基地局における同時に通信可能な移動局数がそのカバレッジ内の移動局数よりも少ない場合に、基地局と通信する最適な移動局を選択する。
【００１４】
従来のスケジューラ機能におけるスケジューリング方法としては、例えば、１ｘＥＶ−ＤＯシステムのＰＦ（Proportional Fairness）スケジューラ手法が知られている。このＰＦスケジューラ手法については、例えば「IEEE 国際会議,VTC 2000Spring 発表原稿 A.Japali,R.Padovani,R.Pankaj著、“Data throughput of CDMA-HDR a High Efficieney-High Data Rate Personal Communication Wireless System”」に記載されている。
【００１５】
しかしながら、このＰＦスケジューラ手法においては、１つの基地局が１台の移動局しか下り送信対象にすることができず、同時に複数の移動局と通信可能なスマートアンテナ基地局には対応していない。このため、スマートアンテナ基地局に適したスケジューリング方法が要望されている。
【００１６】
本発明は、このような事情を考慮してなされたもので、その目的は、同時に複数の移動局と通信可能なスマートアンテナ基地局に対応することができる無線チャネルスケジューリング方法及びその装置を提供することにある。
【００１７】
また、本発明は、その無線チャネルスケジューリング方法を用いた移動通信システムを提供することも目的とする。
【００１８】
【課題を解決するための手段】
上記の課題を解決するために、請求項１に記載の無線チャネルスケジューリング方法は、同時に複数のビームを形成するスマートアンテナを備えた無線基地局における下り送信先の複数の移動局を選択する無線チャネルスケジューリング方法であって、前記無線基地局のカバレッジ内に位置する移動局に関して、前記ビームを向ける対象として選択可能な移動局の組み合わせを求めるグループ化過程と、このグループ化過程で求められた複数のグループの中から、通信サービス要求条件に最も合致するグループを選択し、このグループに含まれる移動局を同時に下り送信する送信先として決定する最良グループ選択過程とを含み、前記グループ化過程は、移動局間の方位角差が所定角度以上であることを前記移動局の組み合わせの条件としてグループ化し、前記グループ化した中から通信品質が良くなるグループを評価関数に基づき選択する処理を含み、前記所定角度は、隣接して形成されるビーム間の干渉が通信品質に影響しないような値として決定されることを特徴としている。
【００１９】
請求項２に記載の無線チャネルスケジューリング方法は、同時に複数のビームを形成するスマートアンテナを備えた無線基地局における下り送信先の複数の移動局を選択する無線チャネルスケジューリング方法であって、前記無線基地局のカバレッジ内に位置する移動局に関して、前記ビームを向ける対象として選択可能な移動局の組み合わせを求めるグループ化過程と、このグループ化過程で求められた複数のグループの中から、通信サービス要求条件に最も合致するグループを選択し、このグループに含まれる移動局を同時に下り送信する送信先として決定する最良グループ選択過程とを含み、前記最良グループ選択過程は、同時に下り送信する移動局についての総合的な通信品質が最もよくなるグループを選択し、前記選択対象の１グループ内に含まれる移動局の通信品質の指標となる評価関数値の総和を算出し、この総和が最大であるグループを前記総合的な通信品質が最もよくなるグループとして決定する処理をさらに含むことを特徴とする。
【００２０】
請求項３に記載の無線チャネルスケジューリング方法は、同時に複数のビームを形成するスマートアンテナを備えた無線基地局における下り送信先の複数の移動局を選択する無線チャネルスケジューリング方法であって、前記無線基地局のカバレッジ内に位置する移動局に関して、前記ビームを向ける対象として選択可能な移動局の組み合わせを求めるグループ化過程と、このグループ化過程で求められた複数のグループの中から、通信サービス要求条件に最も合致するグループを選択し、このグループに含まれる移動局を同時に下り送信する送信先として決定する最良グループ選択過程とを含み、前記最良グループ選択過程は、所定低伝送レートの移動局に関して、同時に下り送信先の移動局として選択する台数を所定上限値以下に抑える処理を含むことを特徴とする。
請求項４に記載の無線チャネルスケジューリング方法は、前記グループ化過程は、前記無線基地局のカバレッジ内に位置する移動局を頂点で表現し、同時に選択することができない移動局間を枝で結ぶように表現したグラフにおいて、該グラフ内に存在する頂点集合の中から、極大独立頂点集合を求めることによって、前記組み合わせを得る処理を含むことを特徴とする。
【００２１】
請求項５に記載の無線チャネルスケジューリング方法は、前記最良グループ選択過程は、同時に下り送信する移動局についての総合的な通信品質が最もよくなるグループを選択する処理を含むことを特徴とする。
【００２３】
請求項６に記載の無線チャネルスケジューリング方法は、前記最良グループ選択過程は、グループ内の移動局数が最大であるグループを選択する処理を含むことを特徴とする。
【００２５】
請求項７に記載の無線チャネルスケジューリング方法は、前記最良グループ選択過程の処理を実行する周期よりも長い周期で、前記グループ化過程の処理を行うことを特徴とする。
【００２６】
請求項８に記載の無線チャネルスケジューリング方法は、前記無線基地局のカバレッジを複数の領域に分割するエリア分割過程をさらに含み、前記分割された領域毎に、前記グループ化過程の処理と前記最良グループ選択過程の処理を実行することを特徴とする。
【００２７】
請求項９に記載の無線チャネルスケジューリング方法は、前記エリア分割過程は、前記複数の領域についての移動局の存在密度を均等化するように、前記カバレッジを分割する処理を含むことを特徴とする。
【００２８】
請求項１０に記載の無線チャネルスケジューリング方法は、前記エリア分割過程は、前記複数の領域についての境界を、動的に変更する処理を含むことを特徴とする。
【００２９】
請求項１１に記載の無線チャネルスケジューリング装置は、同時に複数のビームを形成するスマートアンテナを備えた無線基地局における下り送信先の複数の移動局を選択する移動局選択処理を行う無線チャネルスケジューリング装置であって、請求項１乃至請求項１０のいずれかに記載の無線チャネルスケジューリング方法により、前記移動局選択処理を実行する処理手段を具備することを特徴としている。
【００３０】
請求項１２に記載の移動通信システムは、同時に複数のビームを形成するスマートアンテナを備えた無線基地局と前記無線基地局のカバレッジ内に位置する複数の移動局とからなる移動通信システムであって、前記無線基地局は、請求項１乃至請求項１０のいずれかに記載の無線チャネルスケジューリング方法により、下り送信先の複数の移動局を選択することを特徴としている。
【００３１】
【発明の実施の形態】
以下、図面を参照し、本発明の一実施形態について説明する。
図１は、本発明の一実施形態による移動通信システムの構成を示すブロック図であって、この移動通信システムには本発明の無線チャネルスケジューリング方法が適用されている。この図１の移動通信システムでは、スマートアンテナを備えた基地局（スマートアンテナ基地局）１のカバレッジ（サービス区域）内に複数（ｍ台）の移動局２−１〜ｍが位置している。スマートアンテナ基地局１は、同時に複数のスマートアンテナのビームを形成することができる。図１では、移動局２−１，４，ｍ−１に向けて個別に、スマートアンテナのビーム３−１，４，ｍ−１を同時に形成している。スマートアンテナ基地局１は、これらビーム３−１，４，ｍ−１の到達範囲内にそれぞれ位置する移動局２−１，４，ｍ−１と同時に通信することが可能である。
【００３２】
上記移動局数ｍはスマートアンテナ基地局１が同時に下り送信可能な移動局数ｎよりも大きな値である。このｎの値は、スマートアンテナ基地局１が同時に形成可能なビーム数に一致している。本実施形態における無線チャネルスケジューリング方法は、スマートアンテナ基地局１が、そのｍ台の移動局２−１〜ｍの中から、同時に無線チャネルを割当てて下り送信する複数の移動局を選択するためのものである。以下、この無線チャネルスケジューリング方法について詳細に説明する。
【００３３】
本実施形態の無線チャネルスケジューリング方法は、図２のフローチャートに示すように、移動局２−１〜ｍをグループ化するグループ化過程（図２のステップＳ１）と、複数のグループの中から最良のグループを選択する最良グループ選択過程（図２のステップＳ２）とから構成される。初めに、グループ化過程の処理について説明する。このグループ化過程においては、移動局２−１〜ｍの内、同時にスマートアンテナのビームを形成可能な移動局の組み合わせを求めて、グループ分けを行う。同時にビームを形成可能な移動局の組み合わせの条件は、移動局間の方位角差が所定角度α以上となることである。方位角差とは、スマートアンテナ基地局１からみた移動局２−１〜ｍの方位間の角度差のことである。図１においては、例えば、移動局２−１と移動局２−２の間の方位角差はθ1であり、移動局２−２と移動局２−３の間の方位角差はθ2である。また、移動局２−１と移動局２−３の間の方位角差は（θ1＋θ2）となる。
【００３４】
なお、所定角度αは、隣接して形成されるビーム間の干渉が通信品質に影響しないような値に設定される。例えば、移動局が基地局に要求した伝送レート（要求伝送レート）を保証可能なように、所定角度αを決定する。
【００３５】
次いで、最良グループ選択過程において、上記グループ化過程で求められたグループの中から、スマートアンテナ基地局１が、同時に無線チャネルを割当てて下り送信する移動局のグループを選択する。この最良グループ選択過程では、移動通信システムにおける通信サービス要求条件に最も合致するグループを選択し、このグループに含まれる移動局を同時に下り送信する送信先移動局に決定する。
【００３６】
例えば、通信品質を重視する場合には、同時に下り送信する移動局についての総合的な通信品質が最もよくなるグループを選択する。他方、同時に下り送信する移動局の収容能力を重視する場合には、グループ内の移動局数が最大であるグループを選択する。
【００３７】
次に、通信品質を重視する場合を例にして、上記グループ化過程および最良グループ選択過程の処理を具体的に説明する。図３は、スマートアンテナ基地局１のカバレッジ内に位置する８台の移動局２−１〜８の一覧を示す表である。この図３においては、移動局２−１〜８に対して移動局番号（移動局ＮＯ）を１〜８としている。また、図３には、移動局２−１〜８の方位、評価関数値、同時に使えない移動局ＮＯが示されている。
【００３８】
評価関数値とは、通信品質の指標となる値であって、この値が良いほど通信品質が良好となることを示す。この評価関数値としては、１ｘＥＶ−ＤＯシステムで用いられている評価関数「ＤＲＣ／Ｒ」で算出される値を使用する。「ＤＲＣ」は、移動局からスマートアンテナ基地局１へ通知された予測下りデータ通信速度である。「Ｒ」は、過去においてスマートアンテナ基地局１から移動局へ送信したデータ通信レートの平均値である。
【００３９】
同時に使えない移動局ＮＯは、移動局間の方位角差が所定角度αに満たない移動局を示す。図３の例では、所定角度αが１５度であり、移動局間の方位角差が１５度未満の移動局が同時に使えない移動局となる。例えば、移動局ＮＯ２に関しては、移動局ＮＯ３との方位角差が１０度であるので、移動局ＮＯ３が同時に使えない移動局ＮＯとなっており、他の移動局ＮＯ１、４〜８については方位角差が２０度以上であるので同時に使えること（同時にビーム形成が可能）となる。
【００４０】
まず、図３に示す８台の移動局２−１〜８についてグループ化を行う。ここでは、スマートアンテナ基地局１が同時に下り送信可能な移動局数ｎが５とする。このグループ化処理において、移動局２−１〜８の中から、移動局間の方位角差が２０度以上の組み合わせであって可能な限り多くの移動局を含む組み合わせ（但し、最大数が５）を全て求める。このような組み合わせとしては、図４に示す６通りが求められる。図４の各グループには、組み合わせ可能な移動局ＮＯを示す。
【００４１】
次いで、これら６つのグループの中から、総合的に最も通信品質が良くなるグループを選択する。この最良グループ選択過程の処理において、先ず、グループ内の移動局についての評価関数値の総和を計算する。例えば、グループ（１，２，４，６，８）に関しては、図３に示す移動局ＮＯ１，２，４，６，８の評価関数値「１０」，「１０」，「１０」，「１０」，「３０」を全て加算した値「７０」が評価関数値の和となる。
【００４２】
この評価関数値の和が最大となるグループを最良のグループとして選択する。図４に示す例では、グループ（１，２，４，６，８）の評価関数値「７０」が最大値なので、このグループ（１，２，４，６，８）が同時に下り送信する移動局として選択される。
【００４３】
次に、上記グループ化処理を効率的に行う方法を説明する。スマートアンテナ基地局１のカバレッジ内に位置する移動局数が多数ある場合、移動局間の方位角差が所定角度α以上となる移動局の組み合わせ数が増大し、それら組み合わせを全て求めようとすると、その処理量が膨大なものとなる。この結果、グループ化処理に時間がかかってしまい実用上問題となる場合がある。このため、グループ化処理を効率的に行うようにして、その処理量を減らすことは重要である。
【００４４】
そこで、集合理論を応用して、複数の移動局の中から、移動局間の方位角差が所定角度α以上の組み合わせであって可能な限り多くの移動局を含む組み合わせを全て求めるようにすれば、効率的なグループ化が可能である。集合理論とは、一般的に知られているものであって、頂点集合の中から極大独立頂点集合を求めるというものである。この極大独立頂点集合は、該極大独立頂点集合を一部として含む他の集合が存在しないものとして求められる。
【００４５】
なお、極大独立頂点集合については、例えば、大山達雄著「情報処理実用シリーズ６  アルゴリズム」に記載されているものが知られている。この記載に基づき極大独立頂点集合について補足説明する。
頂点集合Ｖ＝｛１、・・・・ｎ｝と枝集合（辺集号と称する場合もある）Ａ＝｛（ｉ，ｊ）｜ｉ∈Ｖ、ｊ∈Ｖ｝を有するグラフＧ＝（Ｖ，Ａ）が与えられている。グラフＧ＝（Ｖ，Ａ）の頂点集合Ｉ⊆Ｖが、集合Ｉに含まれるどの２頂点間にも枝（辺）が存在しないとき、頂点集合ＩをグラフＧ＝（Ｖ，Ａ）の独立頂点集合または内部安定集合という。換言すると、「互いに枝で結ばれていない頂点の集合」が独立頂点集合である。更に、自分自身の中に他の独立頂点集合を含まない集合を、極大独立頂点集合という。
【００４６】
ここでは、スマートアンテナ基地局１のカバレッジ内に位置する移動局の集合を頂点集合とする。また、移動局間の方位角差が所定角度α以上の組み合わせであって可能な限り多くの移動局を含む組み合わせを極大独立頂点集合とする。
【００４７】
上記極大独立頂点集合を求める解法としては、例えば、大山達雄著「情報処理実用シリーズ６  アルゴリズム」５．４．３節に記載されている「グラフの極大独立頂点集合を求めるアルゴリズム」が知られている。他には、遺伝的アルゴリズムを用いる解法などが知られている。これらのアルゴリズムを使用して極大独立頂点集合を求めるようにすれば、移動局間の方位角差が所定角度α以上となる移動局の組み合わせを全て求めてグループ化する場合に比して、少ない処理量でグループ化することが可能である。
【００４８】
以下、極大独立頂点集合を求める解法の一例としてグラフ探索法（角度法）を用いた場合について、図５〜図９を参照して説明する。先ず、スマートアンテナ基地局１から見た方位順に、移動局２−１〜ｍをソーティングしてラベルを付け、図５に示すような管理テーブルを作成する。この図５の例では、方位０度を基点として、ラベルを１から順に付与している。
【００４９】
次いで、図６に示すフローチャートの流れにしたがって処理を実行する。初めに、図７に示すように、各パラメータを初期設定する（図６のステップＳ１１）。なお、図７に示すパラメータを以下のように定義する。
解集合：解として発見された“互いに枝で結ばれていない頂点”を保持する集合である。
候補集合：解集合に含まれるいずれの頂点ともと枝でつながっていない、全ての頂点からなる集合である。方位順に連続する移動局の集合であり、head-移動局とtail-移動局で表現する。
ＢＴ集合：既に、枝に接続して試した頂点の集合であり、バックトラックの判定に用いる頂点の集合である。
【００５０】
次いで、ステップＳ１２において探索処理を実行する。この探索処理では（Ａ−１）〜（Ａ−４）の手順に従って、解集合に頂点を追加するとともに、候補集合およびＢＴ集合を更新する。
【００５１】
（Ａ−１）候補集合から解集合へ移動する移動局（ラベル）を選択する。ここで、候補集合内の最小ラベル値を有する移動局を、候補集合から解集合へ移動する。
（Ａ−２）候補集合を更新する。ここで、（Ａ−１）において移動した頂点と辺で結ばれている頂点を、候補集合から消去する。また、（Ａ−１）において解集合に移動した移動局に対して角度差＜αの移動局を管理テーブルから求め、候補集合から消去するように、候補集合のhead-移動局，tail-移動局を更新する。
【００５２】
（Ａ−３）ＢＴ集合を更新する。ここで、（Ａ−１）において移動した頂点と辺で結ばれている頂点を、ＢＴ集合から消去する。また、（Ａ−１）において解集合に移動した移動局に対して角度差＜αの移動局を管理テーブルから求め、ＢＴ集合から消去するように、ＢＴ集合のhead-移動局，tail-移動局を更新する（但し、ＢＴ集合＝｛φ（空集合）｝のときは処理不要）。
（Ａ−４）階層数を更新する。ここで、階層数Ｋに１加算する。
【００５３】
次いで、ステップＳ１３において解判定処理を実行する。この解判定処理では、「候補集合＝ＢＴ集合＝｛φ｝」なる式が満足された場合に、解集合が極大独立頂点集合であると判定する。
【００５４】
ステップＳ１３の解判定の結果、解ではなかった場合にステップＳ１４のバックトラック必要判定（ＢＴ判定）処理を実行する。ここで、「“ＢＴ集合に含まれるある頂点”と辺でつながっている頂点∩候補集合＝φ」なる式が満足された場合に、バックトラック実行処理が必要と判断する。または、「ＢＴ集合のhead-移動局と候補集合のhead-移動局の角度差がα以上」であった場合に、バックトラック実行処理が必要と判断する。または、「候補集合＝φ」なる式が満足された場合に、バックトラック実行処理が必要と判断する。
【００５５】
ステップＳ１４のＢＴ判定の結果、バックトラック実行処理が必要な場合には、ステップＳ１５のバックトラック実行処理を行う。なお、ステップＳ１３の解判定の結果、解発見であった場合にも、ステップＳ１５のバックトラック実行処理を行う。一方、バックトラック実行処理が不要な場合には、上記ステップＳ１２へ戻る。ステップＳ１５のバックトラック実行処理においては、まず、直前の探索時に解集合に追加された頂点を、解集合からＢＴ集合へ移し、階層数Ｋから１減算する。次いで、探索継続の場合には上記ステップＳ１２へ戻る。
【００５６】
なお、階層間の移動は、再帰的（Self recursive）処理により実行する。本解法をソフトウェアを用いて実現する場合、そのソフトウェアは、自分自身を呼び出して入れ子のループとして実行されることになる。解集合、候補集合、ＢＴ集合は、呼び出す毎に領域確保されるため、階層毎に領域確保がなされることになる。これらの関係を図８を参照して説明する。
【００５７】
まず、探索を行う場合、探索ルーチンを呼び出す側の集合を、呼び出される側に複写する。次いで、呼び出された側の集合に、上記探索手順における集合の更新を実行する。但し、呼び出し側ルーチンが持つ集合と、呼び出された側ルーチンが持つ集合は異なる。このようにして、探索を行う場合の集合を作成する。
【００５８】
次に，探索からバックトラックで帰ってきた場合、探索ルーチンを呼び出した側の集合に、上記ＢＴ実行手順における集合の更新を実行する。呼び出された側の集合は、領域を解放し、消滅させる。但し、消滅させる前に、発見した解を記録しておく。
【００５９】
図９は、上記図３に示す８台の移動局２−１〜８について作成した管理テーブルの構成例を示す図である。この図９の管理テーブルに基づいて、上記グラフ探索法により極大独立頂点集合を求めると、上記図４に示す６通りの組み合わせをえることができる。このようにグラフ探索法を用いて、無線基地局のカバレッジ内に位置する移動局を頂点で表現し、同時に選択することができない移動局間を枝（または辺と呼ばれる）で結ぶように表現したグラフにおいて、該グラフ内に存在する頂点集合の中から、極大独立頂点集合を求めることによって移動局の組み合わせを得るようにすれば、グループ化にかかる処理量を減らすことが可能となり、その処理時間を短縮することができる。
【００６０】
なお、極大独立頂点集合として求められた移動局の組み合わせには、スマートアンテナ基地局１についての同時に下り送信可能な移動局数ｎが考慮されていない。すなわち、極大独立頂点集合内の移動局数がｎを超える場合がある。このため、最良グループ選択過程の評価関数値の総和算出時に、極大独立頂点集合内の移動局数がｎを超える場合には、評価関数値の大きい方から順にｎ個の評価関数値の和を求めるようにする。
【００６１】
また、グループ化処理においては、スマートアンテナ基地局１が同時に形成する隣接ビーム間で極端な干渉を与え合わないように、移動局間の方位角差に関して所定角度α以上という条件を付けているが、実際の伝搬環境は複雑であるため、最良グループ選択過程において、評価関数値の和が最大となったグループについての通信品質を再確認するようにしてもよい。
【００６２】
図１０は、その最良グループ選択処理の流れを示すフローチャートである。この図１０のフローチャートに示す処理においては、まず、下り送信待ちデータが存在し、且つ要求伝送レート（ＤＲＣ）を受信することができた移動局を選択する（図１０のステップＳ２１）。次いで、グループ化処理により求められた極大独立頂点集合から、この選択した移動局のみを残して他の移動局を削除する（図１０のステップＳ２２）。
【００６３】
なお、グループ化処理により求められた極大独立頂点集合の元情報（削除前の情報）については、別に保持しておくようにしてもよい。これは、グループ化処理によって一度求められたグループ化の情報を使用して、最良グループ選択処理を複数回行うことを考慮した処理である。
【００６４】
次いで、極大独立頂点集合毎に、含まれる移動局の評価関数値の和を求める。ここで、上述したように、極大独立頂点集合内の移動局数がｎを超える場合には、評価関数値の大きい方から順にｎ個の評価関数値の和を求めるようにする（図１０のステップＳ２３）。次いで、評価関数値の和が最大となる極大独立頂点集合を選択し、この集合内で、評価関数値の和を求める対象となった移動局について、通信品質を予測する（図１０のステップＳ２４）。
【００６５】
次いで、評価関数値の和が最大となったグループ内の全移動局の通信品質が、各移動局の要求伝送レート以上であった場合に、当該極大独立頂点集合内の評価関数値の和を求める対象となった移動局を下り送信先として選択する（図１０のステップＳ２６、Ｓ２８）。
【００６６】
一方、要求伝送レートに満たない移動局が見つかった場合には、再度、最良グループ選択処理を行う。この場合、当該極大独立頂点集合の中から、最も干渉源となっている移動局を除外して、評価関数値の上位からｎ個の評価関数値の和を求め直し、その処理を上記ステップＳ２４へ戻す（図１０のステップＳ２７）。このように最良グループ選択処理を再実行する際には、処理の順番を変更する等、新たな処理手順で行うようにしてもよい。
【００６７】
なお、上述した実施形態において、グループ化処理の実行周期と最良グループ選択処理の実行周期が異なるようにしてもよい。グループ化処理において、移動局のグループ化はスマートアンテナ基地局１から見た各移動局の方位がなす方位角差に基づいて行っているが、この方位角差は短時間（１秒程度）では大きく変化しないと考えられる。したがって、グループの更新を該短時間毎に行うことは非能率的である。
【００６８】
そこで、グループ化処理については、上記集合問題を解く（極大独立頂点集合を求める）時間を要することを考慮して、最良グループ選択処理の実行周期よりも長い実行周期に設定する。例えば、１ｘＥＶ−ＤＯシステムでは、最良グループ選択処理の実行周期を、下り送信スロット単位（１／６００秒）とし、グループ化処理の実行周期を数秒とする。これにより、グループ化処理によって一度求められたグループ化の情報を使用して、最良グループ選択処理を複数回行うことになる。このようにすれば、極大独立頂点集合の更新を能率的に実行し、グループ化処理にかかる処理量を軽減することが可能となる。
【００６９】
また、上述した実施形態において、スマートアンテナ基地局１のカバレッジ（サービス区域）を複数の領域に分割し、これら分割した領域毎に独立して本実施形態の無線チャネルスケジューリング方法を適用するようにしてもよい。これは、特に、基地局配下の移動局数が非常に多い場合において、スケジューリングにかかる負荷を分散し、処理時間を短縮するのに有効である。以下、図１１〜図１３を参照して、このカバレッジのエリア分割方法について説明する。
【００７０】
図１１は、カバレッジのエリア分割方法の概念を説明するための図である。図１１に示すように、スマートアンテナ基地局１のカバレッジ内において、移動局が多数存在している混雑地域と移動局数が少ない閑散地域とが有る場合に、例えば、エリア分割数が４つに設定されていると、移動局の存在密度を均等化するように、カバレッジ内を４つのエリア１〜４に分割する。さらに、このエリア分割範囲を移動局の存在密度の変化に応じて動的に変更する。
【００７１】
図１２は、このエリア分割処理の流れを示すフローチャートである。この図１２のフローチャートに示すように、まず、基地局配下の移動局数Ｘとエリア分割数Ｙが与えられると、移動局数Ｘをエリア分割数Ｙで除して１エリア当りの移動局数Ｚを求める（図１２のステップＳ３１）。次いで、カバレッジ内を探索する方位角の基点となる方角を決定する（図１２のステップＳ３２）。
【００７２】
この方角から方位角を、例えば、時計回りに増していき、１移動局が存在する位置を通過する度に通過移動局数を１ずつカウントアップして、通過移動局数を計数する。この通過移動局数が１エリア当りの移動局数Ｚに一致するまで計数を行い、一致した時点までの計数対象移動局を１エリア内の移動局として扱うように決定する。次いで、通過移動局数を０に初期化して、方位角の基点に戻るまで、この処理を繰り返す（図１２のステップＳ３３）。この結果、カバレッジ内に存在する全ての移動局が、Ｙ個のエリアのいずれかのエリアに属するようになる。
【００７３】
なお、このエリア分割処理の実行契機については、上記グループ化処理の実行契機に合わせるようにしてもよい。この場合、エリア分割処理をグループ化処理実行の直前に行うようにする。
【００７４】
また、エリア分割を実施した場合、エリア毎に独立で最良グループ選択処理等が実行されることになるが、ここで考慮すべき点について図１３を参照して説明する。図１３に示すように、カバレッジ内が４つのエリアＡ〜Ｄに分割されている場合に、エリアＡ，ＣについてのスケジューリングをエリアＤよりも先に実行すると、エリアＤが使用可能な方位角の幅が狭くなってしまう。これは、エリアＡ，Ｃにおいてスケジューリングした結果、エリアＤとの境界付近に位置する移動局を選択すると、エリアＤ内においてスケジューリングする際、エリアＡ，Ｃで選択された移動局との方位角度差が所定方位角度差α未満の移動局が、ビーム間干渉の影響を避けるために、選択されないことによる。
【００７５】
これに対処するために、エリア分割を実施した場合には、スケジューリングを行うエリアの順番を以下の基準１または基準２に準じて決定する。
基準１：基地局から見たエリア内の角度幅が狭いエリアから先に、スケジューリングを行う。角度幅が狭いエリアは、隣接エリアの影響が顕著に現れるので、優先してスケジューリングを実行することにより救済する。
基準２：エリア内に存在する移動局の評価関数値の総和を求めて、総和が大きいエリアから先にスケジューリングを行う。
【００７６】
また、上述したエリア分割処理時のカバレッジ内を探索する方位角の基点（図１２のステップＳ３２で決定する方角）を、動的に変更するようにしてもよい。エリア間の境界付近に位置する移動局は、隣接エリアの影響を受けて、下り送信先の移動局として選択されにくくなる可能性がある。例えば、上記図１３において、エリアＡ，Ｃの方が連続して、エリアＤよりも優先してスケジューリングがなされると、実質的にエリアＤの範囲が狭まることになる。この結果、狭まった地域に位置するエリアＤ内の移動局は、下り送信先として選択されづらくなる。
【００７７】
このような状況を避けるために、カバレッジ内を探索する方位角の基点を動的に変化させることで、分割されたエリア間の境界位置が一定にならないように制御する。例えば、エリア分割処理実行毎に、一様乱数を発生させて、該基点となる方角をランダムに決定する。
【００７８】
また、上述した実施形態において、低伝送レートしか利用できない移動局に関し、同時に下り送信先の移動局として選択する台数に上限値ｐを設けるようにしてもよい。これは、低伝送レートの移動局ばかり選択することによって基地局全体の伝送スループットが低下することを防ぐために行う。このために、上記最良グループ選択処理において、グループ化処理により求められたグループ（例えば、極大独立頂点集合として求められたグループ）に含まれる移動局の評価関数値の総和を算出する際に、低伝送レートの移動局ばかりを選択することのないよう考慮して行う。
【００７９】
例えば、たとえ評価関数値が大きくても、要求伝送レートが所定値よりも小さいｐ台目以降の移動局については、評価関数値の和を求める対象に含めないようにする。これにより、要求伝送レートが所定値よりも小さいｐ台目以降の移動局は同時に下り送信する移動局として選択されなくなるので、低伝送レートの移動局ばかりを選択することはなく、基地局全体の伝送スループットの低下を防止することができる。
【００８０】
なお、上述した実施形態の無線チャネルスケジューリング方法を実現する際には、スマートアンテナ基地局１に上記無線チャネルスケジューリング方法の各過程の処理を行う無線チャネルスケジューリング装置を備えるようにする。この無線チャネルスケジューリング装置は、下り送信先の複数の移動局を選択する移動局選択処理を行う装置であって、上記無線チャネルスケジューリング方法により、該移動局選択処理を実行する処理手段を具備するものである。
【００８１】
また、この処理手段は、専用のハードウェアにより実現されるものであってもよく、また、メモリおよびＣＰＵ（中央処理装置）等により構成され、無線チャネルスケジューリング機能を実現するためのプログラムをメモリにロードして実行することによりその機能を実現させるものであってもよい。
【００８２】
以上、本発明の実施形態を図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、本発明の要旨を逸脱しない範囲の設計変更等も含まれる。
【００８３】
【発明の効果】
以上説明したように、本発明によれば、無線基地局のカバレッジ内に位置する移動局に関して、ビームを向ける対象として選択可能な移動局の組み合わせを求め、この求められた複数のグループの中から、通信サービス要求条件に最も合致するグループを選択し、このグループに含まれる移動局を同時に下り送信する送信先として決定するようにしたので、同時に複数の移動局と通信可能なスマートアンテナ基地局に対応することができる。
【００８４】
これにより、移動通信システムにスマートアンテナを適用し、セクタアンテナによっては成し遂げられなかった一基地局当りの移動局収容能力の改善を実現することができるという効果が得られる。さらに、スマートアンテナ適用時には、基地局内のハンドオーバが不要となり、また、同一基地局に収容された移動局相互間の干渉量を低減可能となるので、基地局と移動局との間の伝送スループットの改善等の効果も得られる。
【００８５】
また、本発明によれば、移動局間の方位角差が所定角度以上であることを移動局の組み合わせの条件としてグループ化し、該所定角度を隣接して形成されるビーム間の干渉が通信品質に影響しないような値として決定するようにしたので、選択された移動局に対する通信品質を良好に保つことができるという効果が得られる。
【００８６】
また、本発明によれば、無線基地局のカバレッジ内に位置する移動局を頂点で表現し、同時に選択することができない移動局間を枝で結ぶように表現したグラフにおいて、該グラフ内に存在する頂点集合の中から、極大独立頂点集合を求めることによって移動局の組み合わせを得るようにしたので、グループ化にかかる処理量を減らすことが可能となり、その処理時間を短縮することができる。
【００８７】
また、本発明によれば、同時に下り送信する移動局についての総合的な通信品質が最もよくなるグループを選択するようにしたので、通信品質を重視するような通信サービスを実現することが可能となる。
【００８８】
また、本発明によれば、選択対象の１グループ内に含まれる移動局の通信品質の指標となる評価関数値の総和を算出し、この総和が最大であるグループを総合的な通信品質が最もよくなるグループとして決定するようにしたので、定量的な判断によってグループ選択を行うことが可能となり、最良グループ選択結果の信頼度を向上することができる。
【００８９】
また、本発明によれば、グループ内の移動局数が最大であるグループを選択するようにしたので、同時に下り送信する移動局の収容能力を重視するような通信サービスを実現することが可能となる。
【００９０】
また、本発明によれば、所定低伝送レートの移動局に関して、同時に下り送信先の移動局として選択する台数を所定上限値以下に抑えるようにしたので、低伝送レートの移動局ばかりを選択することはなく、基地局全体の伝送スループットの低下を防止することができる。
【００９１】
また、本発明によれば、最良グループ選択処理を実行する周期よりも長い周期でグループ化処理を行うようにしたので、グループ化処理によって一度求められたグループ化の情報を使用して、最良グループ選択処理を複数回行うことが可能となる。この結果、移動局グループの更新を能率的に実行し、グループ化処理にかかる処理量を軽減することができるという効果が得られる。
【００９２】
また、本発明によれば、無線基地局のカバレッジを複数の領域に分割し、この分割された領域毎に、グループ化処理と最良グループ選択処理を実行するようにしたので、スケジューリングにかかる負荷を分散し、処理時間を短縮することができる。
【００９３】
また、本発明によれば、複数の領域についての移動局の存在密度を均等化するように、カバレッジを分割するようにしたので、分割した各領域に関するスケジューリングにかかる負荷を均等化し、各領域に関するスケジューリング処理に必要な能力を同等なものにすることが可能となる。この結果、個々の処理手段に必要な処理能力を軽減することができるので、実用化が容易になるという効果が得られる。
【００９４】
また、本発明によれば、複数の領域についての境界を、動的に変更するようにしたので、分割された領域間の境界位置が一定にはならない。これにより、特定領域間の境界付近に位置する移動局が、隣接領域の影響を受けて、下り送信先の移動局として選択されにくくなることを防止することができる。
【図面の簡単な説明】
【図１】  本発明の一実施形態による移動通信システムの構成を示すブロック図である。
【図２】  同実施形態における無線チャネルスケジューリング方法の処理の流れを示すフローチャートである。
【図３】  同実施形態における無線チャネルスケジューリング方法を説明するための第１の図である。
【図４】  同実施形態における無線チャネルスケジューリング方法を説明するための第２の図である。
【図５】  同実施形態におけるグラフ探索法（角度法）を用いたグループ化処理を説明するための第１の図である。
【図６】  同実施形態におけるグラフ探索法（角度法）を用いたグループ化処理の流れを示すフローチャートである。
【図７】  同実施形態におけるグラフ探索法（角度法）を用いたグループ化処理を説明するための第２の図である。
【図８】  同実施形態におけるグラフ探索法（角度法）を用いたグループ化処理を説明するための第３の図である。
【図９】  同実施形態におけるグラフ探索法（角度法）を用いたグループ化処理を説明するための第４の図である。
【図１０】  同実施形態における最良グループ選択処理の流れを示すフローチャートである。
【図１１】  同実施形態におけるカバレッジ（サービス区域）のエリア分割方法について説明するための第１の図である。
【図１２】  同実施形態におけるカバレッジのエリア分割方法の処理の流れを示すフローチャートである。
【図１３】  同実施形態におけるカバレッジのエリア分割方法について説明するための第２の図である。
【図１４】  スマートアンテナを備えた基地局と移動局からなる移動通信システムについて説明するための図である。
【図１５】  セクタアンテナを備えた基地局と移動局からなる移動通信システムについて説明するための図である。
【符号の説明】
１  スマートアンテナ基地局
２−１〜ｍ  移動局
３−１〜ｍ  スマートアンテナのビーム
【図１】
0004637421.tif 000002
【図２】
0004637421.tif 000003
【図３】
0004637421.tif 000004
【図４】
0004637421.tif 000005
【図５】
0004637421.tif 000006
【図６】
0004637421.tif 000007
【図７】
0004637421.tif 000008
【図８】
0004637421.tif 000009
【図９】
0004637421.tif 000010
【図１０】
0004637421.tif 000011
【図１１】
0004637421.tif 000012
【図１２】
0004637421.tif 000013
【図１３】
0004637421.tif 000014
【図１４】
0004637421.tif 000015
【図１５】
0004637421.tif 000016