(57)【要約】  収束パターン選択部（１０Ａ）が、指定された初期条件に基づいて複数の異なるパターンを順次生成し、評価値が極値に収束したパターンを収束パターンとして選択し、当該収束パターンが選択されるごとに初期条件を変更して収束パターンの選択を繰り返し実行し、送信パターン決定部（１０Ｂ）が、収束パターン選択部（１０Ａ）で得られた各収束パターンのうち評価値が最も高いものを最適送信パターンとして選択する。これにより、より良い評価値を持つ最適送信パターンを探索する。
2017038683.tif 000002
【特許請求の範囲】
【請求項１】
無線ネットワークシステムを構成する複数の送信ポイントと、これら送信ポイントとの間で無線通信を行うユーザ端末との組み合わせを示すパターンを複数生成し、所定の探索アルゴリズムにより、これらパターンの評価値に基づいて、送信ポイントとユーザ端末との最適な組み合わせを示す最適送信パターンを選択するスケジューリング装置であって、
指定された初期条件に基づいて複数の異なるパターンを順次生成し、評価値が極値に収束したパターンを収束パターンとして選択し、当該収束パターンが選択されるごとに前記初期条件を変更して前記収束パターンの選択を繰り返し実行する収束パターン選択部と、
前記収束パターン選択部で得られた前記収束パターンのうち評価値が最も高いものを前記最適送信パターンとして選択する送信パターン決定部と
を備えることを特徴とするスケジューリング装置。
【請求項２】
請求項１に記載のスケジューリング装置において、
前記収束パターン選択部は、
前記初期条件として初期パターンおよびシード値を生成して出力する初期条件生成部と、
前記初期条件生成部から出力された前記初期パターンのうち、前記シード値により生成した乱数に基づいて、前記組み合わせの一部を順次変更することにより、前記パターンを順次生成するパターン生成部と、
前記パターン生成部から前記パターンが出力されるごとに、当該パターンの評価値を順次算出するパターン評価部と、
前記パターン生成部から前記パターンが出力されるごとに、当該パターンと候補パターンとの評価値を比較し、評価値が高いものを新たな候補パターンとして選択して順次出力する候補パターン選択部と、
前記候補パターン選択部から順次出力される前記候補パターンのうち、一定の収束判定間隔で出力された２つのパターンごとに、両者の評価値の変化量を算出し、得られた変化量が収束判定回数だけ連続して収束判定閾値を下回ったことにより、評価値が収束したことを検出した場合、当該候補パターンを前記収束パターンとして選択し、前記初期条件生成部に対して前記初期条件である前記初期パターンまたはシード値のいずれか一方または両方の変更を指示し、前記パターン生成部に対してパターン生成を初期化して新たに開始するよう指示し、前記候補パターン選択部に対して前記候補パターンの初期化を指示する収束判定部とを含む
ことを特徴とするスケジューリング装置。
【請求項３】
請求項２に記載のスケジューリング装置において、
前記初期条件生成部は、前記初期パターンを最初に出力する際、前記パターンの生成時に用いるシード値を生成して出力し、前記収束判定部での前記収束の検出ごとにユニークな値を持つシード値を生成して出力し、
前記パターン生成部は、前記乱数に基づいて変更対象となる送信ポイントを選択する際、前記初期条件生成部から出力された前記シード値から生成した乱数に基づき変更対象となる送信ポイントを選択する
ことを特徴とするスケジューリング装置。
【請求項４】
請求項２または請求項３に記載のスケジューリング装置において、
前記初期条件生成部は、前記初期パターンを最初に出力する際、前記送信ポイントのすべてを送信停止とした初期パターンを生成して出力し、前記収束判定部での前記収束の検出ごとに、前記送信ポイントのうちから選択したいずれか１つの送信ポイントについて、当該送信ポイントを送信元とし得るユーザ端末群の中からいずれか１つを新たな送信先として選択し、当該送信ポイント以外の送信ポイントをすべて送信停止とした初期パターンを生成して出力することを特徴とするスケジューリング装置。
【請求項５】
請求項２〜請求項４のいずれかに記載のスケジューリング装置において、
前記収束判定部は、前記候補パターン選択部から順次出力される前記候補パターンの評価値を記録するためのテーブルを１つ以上有し、収束判定回数の間隔で当該評価値を当該テーブルに記録し、前記収束が最初に検出された後は、前記候補パターン選択部から評価値が新たに出力されるごとに、当該テーブルに記録された１つ以上の前記評価値と比較し、これら評価値が規定合致判定回数だけ連続して一致または小さいと判定した時点で、当該評価値が収束したと判定することを特徴とするスケジューリング装置。
【請求項６】
請求項３に記載のスケジューリング装置において、
前記パターン生成部、前記パターン評価部、前記候補パターン選択部、および前記収束判定部からなる処理系を複数備え、
前記初期条件生成部は、前記処理系ごとに異なる前記シード値を生成して出力し、
前記送信パターン決定部は、前記処理系が出力された前記収束パターンのうち、前記評価値が最も高いものを前記送信パターンとして選択する
ことを特徴とするスケジューリング装置。
【請求項７】
無線ネットワークシステムを構成する複数の送信ポイントと、これら送信ポイントとの間で無線通信を行うユーザ端末との組み合わせを示すパターンを複数生成し、所定の探索アルゴリズムにより、これらパターンの評価値に基づいて、送信ポイントとユーザ端末との最適な組み合わせを示す最適送信パターンを選択するためのスケジューリング方法であって、
指定された初期条件に基づいて複数の異なるパターンを順次生成し、評価値が極値に収束したパターンを収束パターンとして選択し、当該収束パターンが選択されるごとに前記初期条件を変更して前記収束パターンの選択を繰り返し実行する収束パターン選択ステップと、
前記収束パターン選択ステップで得られた前記収束パターンのうち評価値が最も高いものを前記最適送信パターンとして選択する送信パターン決定ステップと
を備えることを特徴とするスケジューリング方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワーク制御技術に関し、特に無線ネットワーク内の各送信ポイントの動作内容（送信状態）を指定することにより、無線ネットワークが有する無線リソースの割り当てを行うためのスケジューリング技術に関する。
【背景技術】
【０００２】
無線ネットワーク分野では、急増するモバイルトラヒックを収容するために、スモールセルを高密度配置することが検討されている。スモールセルは、マクロセルに比べて基地局（送信ポイント：ＴＰ）からの送信電力が小さく、セル半径が小さいため、セル内にて同一周波数を共有する移動端末（ユーザ端末：ＵＥ）数が削減され、端末当たりのスループットを改善することができる。【０００３】
一方で、スモールセルの高密度配置は、隣接セルからの干渉電力の増大を招く。例えば、複数のＴＰが同時に同一周波数帯を用いて異なるＵＥにデータ送信した場合には、ＵＥにとっては、自分宛のデータを送信するＴＰ以外のＴＰからの送信信号は、所望の受信信号に対しての干渉電力となり、かえってスループットの低下を招く恐れがある。【０００４】
このため、ＬＴＥ（Long Term Evolution）／ＬＴＥ−Ａ等の次世代無線通信インターフェースでは、同一周波数帯内におけるセル間の干渉電力を抑圧するために、多地点協調（ＣｏＭＰ：Coordinated Multi-point transmission/reception）スケジューリングが採用されている（非特許文献１）。ＣｏＭＰスケジューリングは、同一周波数帯内におけるＴＰ動作内容（送信先ＵＥ／送信停止）をスケジューリングする。【０００５】
具体的には、複数個の送信ポイント−ユーザ端末の組み合わせパターンを所定の評価関数を用いて評価し、評価値が最大となるパターンを探索し、最適送信パターンとして選択・出力する。
図１４示す組み合わせパターン例において、例えば、パターン＃１では、ＴＰ１，ＴＰ２，ＴＰ３，…の送信先としてＵＥ１，ＵＥ５，ＵＥ８，…が割り当てられている。また、パターン＃２のＴＰ３のように、送信先が割り当てられておらず、送信停止となる場合には「Blank」が記されている。【０００６】
また、所定の評価関数は、外部から入力される外部評価情報に基づいて算出されるＴＰ別下位評価値の合計値であり、下位評価値は、例えば、Proportional-Fairness法に基づき、当該ＴＰの送信先ＵＥの瞬時スループットを平均スループットで除算して得られる値である（非特許文献２）。また、この時の外部評価情報は、例えば、各ＵＥの平均スループット、各ＵＥの未送信データ量、および各ＵＥのＴＰ別チャネル品質状態である。当該チャネル品質状態とは、例えば、ＵＥからフィードバックされるＣＱＩ（Channel Quality Indicator）である（非特許文献３，４）。【０００７】
評価値が最大となる組み合わせパターンを効率的に探索するために、山登り法をＣｏＭＰスケジューリングに応用した方法が考えられる。山登り法は、小さな修正を可能な限り繰り返すことで、評価値が最大となる所望のパターンに到達させる探索アルゴリズムである。本探索において、小さな修正とは、組み合わせパターンの中で、１つのＴＰの送信先を、評価値が高まるように修正することである。【０００８】
図１５に示すように、このスケジューリング装置５０は、送信ポイント−ユーザ端末の組み合わせパターンを生成するパターン生成部５１、評価関数を用いて当該生成パターンの評価値を算出するパターン評価部５２、生成したパターンの中で最も評価値が高いパターンを保持する送信パターン選択部５３、および評価回数上限に達したことを検出し、生成されたパターンの中で最も高い評価値を示したパターンを最適送信パターンとして外部に出力する終了判定部５４とからなる。以下では、各部の機能の詳細を述べる。【０００９】
＜パターン生成部＞
パターン生成部５１は、後述する送信パターン選択部から入力される送信パターンのうち、１つのＴＰのみ送信先を変更した後、当該変更パターンを出力する。
図１６に示すように、スケジューリング装置５０の外部から開始指示を受けると、パターン生成部５１は初期化を行う。この初期化では、全ＴＰの選択済フラグを０にクリアし、全ＴＰの各送信先の試行有無をクリアし、内部保持パターンにおける全ＴＰの送信先を送信停止（Blank）に書き換える。【００１０】
初期化後、送信先を変更するＴＰ（Ｓ＿ＴＰ）をランダムに１つ選択する。ただし、選択対象とするＴＰは、選択済フラグが０のＴＰである。次に、内部保持パターンにおけるＳ＿ＴＰの送信先を変更する。当該送信先は、スケジューリング装置５０の外部から入力されるＴＰ別の送信先ＵＥリスト群のうち、Ｓ＿ＴＰの送信先ＵＥリストにおいて、送信先の試行有無が無となっているＵＥである。当該変更と同時に、当該ＵＥの試行有無は有に更新する。Ｓ＿ＴＰの送信先ＵＥリストの全ＵＥの試行有無が有となっている場合には、Ｓ＿ＴＰを別のＴＰに再選択し、同様の送信先の変更を行う。当該変更済みの内部保持パターンがパターン生成部５１から出力されるパターンである。パターン生成後は、再び送信パターン選択部５３からの入力を待つ。当該入力を検出すると、内部保持パターンに入力された送信パターンをセットし、同様の変更処理を行う。【００１１】
＜パターン評価部＞
パターン評価部５２は、パターン生成部５１から入力されるパターンの評価値を、評価関数を用いて算出する。算出した評価値と評価済パターンは、送信パターン選択部５３に出力する。【００１２】
＜送信パターン選択部＞
送信パターン選択部５３は、それまでに生成された評価済パターン群の中で、最も評価値が高いパターンを送信パターンとして選択・出力する。
図１７に示すように、スケジューリング装置５０の外部から開始指示を受けると、送信パターン選択部５３は初期化を行う。この初期化では、内部保持評価値を０に設定し、内部保持パターンの全ＴＰの送信先を送信停止（Ｂｌａｎｋ）に書き換える。【００１３】
初期化後、パターン評価部５２から評価済パターンが入力されると、併せて入力される評価値が、内部保持評価値を上回っているか否かを確認する。上回っている場合には、入力された評価済パターンの方が良好であるので、内部保持パターンおよび内部保持評価値を、評価済パターンおよび評価値に更新する。上回っていない場合には、内部保持パターンおよび内部保持評価値を維持する。これらの更新処理後、送信パターン選択部５３は、内部保持パターンおよび内部保持評価値を併せて終了判定部５４に出力する。【００１４】
＜終了判定部＞
終了判定部５４は、評価済パターンの評価回数をカウントし、当該カウント値が、スケジューリング装置５０の外部から入力される評価回数上限（終了条件）に達すると、探索終了と判定し、終了フラグを１にするとともに、その時点で送信パターン選択部５３から出力されている送信パターンを、最適送信パターン（スケジューリング結果）として出力する。なお、終了フラグおよび評価回数のカウント値は、開始指示があるごとに、いずれも０に初期化される。【００１５】
このようなスケジューリング装置５０を用いることで、送信パターン選択部５３が出力する送信パターンは、図１８に示すように、評価を重ねるごとに評価値が単調に改善され続けることになる。これにより、十分な評価回数を費やした後、評価値が高いパターンに収束することになる。
スケジューリング装置５０は、このようにして得られた収束値に対応する送信パターンを選択し、スケジューリング結果として出力する。【００１６】
しかしながら、このような構成例では、生成した各パターンから送信パターンを選択する際、これらパターンの評価値の極値を探索する探索アルゴリズムとして山登り法を用いている。このため、収束値が最大値ではなく比較的低い極値であっても、最初に見つかった極値を最終的な収束値として選択して、それ以降の探索を終了してしまうことになる。したがって、比較的低い収束値に対応するパターンを、最適送信パターンすなわちスケジューリング結果として選択してしまう場合があるという問題があった。
【先行技術文献】
【非特許文献】
【００１７】
【非特許文献１】田岡ほか，「LTE-AdvancedにおけるMIMOおよびセル間協調送受信技術」，NTT DOCOMO テクニカル・ジャーナル，Vol. 18，No. 2，Jul.2010
【非特許文献２】Tolga Giricほか，"Proportional Fair Scheduling Algorithm in     OFDMA-Based Wireless Systems with QoS Constraints"，JOURNAL OF COMMUNICATIONS AND NETWORKS，VOL. 12，NO. 1，FEBRUARY 2010
【非特許文献３】Sandy Fraser，"LTE Channel State Information (CSI)"，http://www.keysight.com/upload/cmc_upload/All/31May2012_LTE.pdf?&cc=JP&lc=jpn
【非特許文献４】3GPP，TS 36.213 (V.8.2.0)
【発明の概要】
【発明が解決しようとする課題】
【００１８】
本発明はこのような課題を解決するためのものであり、より良い評価値を持つ最適送信パターンを探索できるスケジューリング技術を提供することを目的としている。
【課題を解決するための手段】
【００１９】
このような目的を達成するために、本発明にかかるスケジューリング装置は、無線ネットワークシステムを構成する複数の送信ポイントと、これら送信ポイントとの間で無線通信を行うユーザ端末との組み合わせを示すパターンを複数生成し、所定の探索アルゴリズムにより、これらパターンの評価値に基づいて、送信ポイントとユーザ端末との最適な組み合わせを示す最適送信パターンを選択するスケジューリング装置であって、指定された初期条件に基づいて複数の異なるパターンを順次生成し、評価値が極値に収束したパターンを収束パターンとして選択し、当該収束パターンが選択されるごとに前記初期条件を変更して前記収束パターンの選択を繰り返し実行する収束パターン選択部と、前記収束パターン選択部で得られた前記収束パターンのうち評価値が最も高いものを前記最適送信パターンとして選択する送信パターン決定部とを備えている。【００２０】
また、本発明にかかるスケジューリング方法は、無線ネットワークシステムを構成する複数の送信ポイントと、これら送信ポイントとの間で無線通信を行うユーザ端末との組み合わせを示すパターンを複数生成し、所定の探索アルゴリズムにより、これらパターンの評価値に基づいて、送信ポイントとユーザ端末との最適な組み合わせを示す最適送信パターンを選択するためのスケジューリング方法であって、指定された初期条件に基づいて複数の異なるパターンを順次生成し、評価値が極値に収束したパターンを収束パターンとして選択し、当該収束パターンが選択されるごとに前記初期条件を変更して前記収束パターンの選択を繰り返し実行する収束パターン選択ステップと、前記収束パターン選択ステップで得られた前記収束パターンのうち評価値が最も高いものを前記最適送信パターンとして選択する送信パターン決定ステップとを備えている。
【発明の効果】
【００２１】
本発明によれば、評価値が極値に収束したパターンが収束パターンとして選択されるごとに、パターンの生成に用いる初期条件を変更した上で収束パターンの選択が複数回繰り返し実行され、得られた各収束パターンのうち評価値の最も高いものが最適送信パターンとして選択される。したがって、最初に見つかった極値を最終的な収束値として選択して、それ以降の探索を終了してしまう場合と比較して、より高い収束値を持つパターンを最適送信パターンとして選択することが可能となる。【００２２】
また、スケジューリング処理においては、スケジューリング期間が規定されているため、評価回数には上限が存在しており、１回の探索ごとに評価回数を適切に分配する必要がある。本実施の形態によれば、収束を検出した後に新たな探索を開始するため、１回の探索に評価回数が不足して収束前に次の実行に移る事態を回避することが可能となる。また、収束検出後に新たな探索を開始することは、各探索において必要十分な評価回数を分配することと等価となり、限られた評価回数を効率的に利用することが可能となる。
【図面の簡単な説明】
【００２３】
【図１】図１は、第１の実施の形態にかかるスケジューリング装置の構成を示すブロック図である。
【図２】図２は、第１の実施の形態にかかるパターン生成処理を示すフローチャートである。
【図３】図３は、第１の実施の形態にかかる候補パターン選択処理を示すフローチャートである。
【図４】図４は、第１の実施の形態にかかる収束判定処理を示すフローチャートである。
【図５】図５は、第１の実施の形態にかかる送信パターン選択処理を示すフローチャートである。
【図６】図６は、第２の実施の形態にかかるスケジューリング装置の構成を示すブロック図である。
【図７】図７は、第２の実施の形態にかかる初期条件生成処理を示すフローチャートである。
【図８】図８は、第３の実施の形態にかかるスケジューリング装置の構成を示すブロック図である。
【図９】図９は、パターン評価値の遷移を示す説明図である。
【図１０】図１０は、第３の実施の形態にかかる収束判定処理を示すフローチャートである。
【図１１】図１１は、第３の実施の形態にかかる収束判定処理（続き）を示すフローチャートである。
【図１２】図１２は、第３の実施の形態にかかる評価値と経過時間の関係を説明図である。
【図１３】図１３は、第４の実施の形態にかかるスケジューリング装置の構成を示すブロック図である。
【図１４】図１４は、送信ポイント−ユーザ端末の組み合わせパターン例である。
【図１５】図１５は、スケジューリング装置の構成例を示すブロック図である。
【図１６】図１６は、図１５のパターン生成処理を示すフローチャートである。
【図１７】図１７は、図１５の送信パターン選択処理を示すフローチャートである。
【図１８】図１８は、パターン評価値の遷移を示すグラフである。
【発明を実施するための形態】
【００２４】
次に、本発明の実施の形態について図面を参照して説明する。
［第１の実施の形態］
まず、図１を参照して、本発明の第１の実施の形態にかかるスケジューリング装置１０について説明する。
【００２５】
このスケジューリング装置１０は、無線ネットワークが有する無線リソースの割り当てを行う装置であり、同一周波数帯内におけるセル間の干渉電力を抑圧するため、複数個の送信ポイント−ユーザ端末の組み合わせパターンごとに評価値を計算し、得られた評価値に基づいて最適パターンを選択するＣｏＭＰスケジューリングを行う機能を有している。
【００２６】
図１に示すように、本実施の形態にかかるスケジューリング装置１０には、主な機能部として、初期条件生成部１１、パターン生成部１２、パターン評価部１３、候補パターン選択部１４、収束判定部１５、送信パターン選択部１６、および終了判定部１７が設けられている。前述した図１５の構成と比較して、初期条件生成部１１、候補パターン選択部１４、および収束判定部１５を新たに備えている。
【００２７】
これら機能部のうち、初期条件生成部１１、パターン生成部１２、パターン評価部１３、候補パターン選択部１４、および収束判定部１５が、収束パターン選択部１０Ａを構成している。すなわち、収束パターン選択部１０Ａは、指定された初期条件に基づいて複数の異なるパターンを順次生成するとともに、これらパターンに対して探索アルゴリズムとして山登り法を適用することにより評価値が極値に収束したパターンを収束パターンとして選択する機能と、当該収束パターンが選択されるごとに、初期条件を変更して収束パターンの選択を複数回繰り返し実行する機能とを有している。
【００２８】
また、これら機能部のうち、送信パターン選択部１６、および終了判定部１７が、送信パターン決定部１０Ｂを構成している。すなわち、送信パターン決定部１０Ｂは、収束パターン選択部１０Ａで得られた各収束パターンのうち評価値が最も高いものを最適送信パターンとして選択する機能を有している。
【００２９】
本発明において、候補パターンとは、同一初期条件に基づく探索において前回パターンより評価値が高いパターンのことであり、収束パターンとは、同一初期条件に基づく探索において、評価値が最も高い極値に収束した時点におけるパターンのことである。ただし、収束パターンは、同一初期条件に基づく探索において収束する前は、候補パターンと同一のパターンとする。また、送信パターンとは、異なる初期条件に基づく探索により得られた収束パターンのうち前回収束パターンより評価値が高いパターンのことであり、最適送信パターンとは、各探索において生成したパターンに対する評価回数が上限に達した時点における送信パターンのことである。
【００３０】
次に、本実施の形態にかかるスケジューリング装置１０を構成する各機能部について、それぞれの機能および処理動作について、詳細に説明する。
【００３１】
<初期条件生成部>
初期条件生成部１１は、パターン生成部１２におけるパターンの生成に用いる初期パターンとシード値を生成して出力する機能を有している。
具体的には、初期パターンの生成に関する機能として、初期パターンを最初に出力する際、送信ポイントのすべてを送信停止とした初期パターンを生成して出力する機能を有している。
【００３２】
また、シード値の生成に関する機能として、初期パターンを最初に出力する際、パターンの生成時に用いるシード値を生成して出力する機能と、収束判定部１５での収束の検出ごとにユニークな値を持つシード値を生成して出力する機能とを有している。なお、収束判定部１５が収束を検出した時点で当該生成を行う際においては、初回の探索と異なる初期条件とするために、シード値はユニークな値、すなわち探索開始から当該生成時点までに未生成の値とする。
【００３３】
初期条件生成部１１において、初期条件であるこれら初期パターンとシード値の生成タイミングは、スケジューリング装置１０の外部から入力される開始指示を受けた直後であり、収束判定部１５が収束を検出した時点、すなわち、収束完了を示す信号である収束フラグが１になった時点でシード値のみが変更される。
【００３４】
なお、本発明では、収束判定部１５が収束を検出した時点で初期条件を変更する方法として、これら初期パターンとシード値のいずれか一方または両方を変更する方法を含んでいるものとする。
本実施の形態では、収束判定部１５が収束を検出した時点でシード値を変更して、探索を繰り返し実行し、その際、初期パターンは同じものを用いる場合を例として説明する。また、後述する第２の実施の形態では、収束判定部１５が収束を検出した時点で初期パターンとシード値の両方を変更して、探索を繰り返し実行する場合を例として説明する。
【００３５】
＜パターン生成部＞
パターン生成部１２は、初期条件生成部１１から出力された初期パターンとシード値とに基づいて、複数の異なるパターンを生成して順次出力する機能を有している。
【００３６】
具体的には、パターン生成に関する機能として、パターン生成を開始する際、初期条件生成部１１から出力された初期パターンのうち、いずれか１つの送信ポイントを変更対象送信ポイントとして選択し、当該変更対象送信ポイントについてのみ送信先となるユーザ端末を変更したパターンを生成して出力する機能と、収束判定部１５から収束パターンが出力されるごとに、当該収束パターンのうち、いずれか１つの送信ポイントを変更対象ポイントとして選択し、当該変更対象送信ポイントについてのみ送信先となるユーザ端末を変更したパターンを生成して出力する機能とを有している。
【００３７】
また、変更対象ポイントを選択する機能として、変更対象送信ポイントを選択する際、初期条件生成部１１から出力されたシード値から生成した乱数に基づき当該変更対象送信ポイントを選択する機能を有している。
【００３８】
パターン生成部１２については、前述の図１５に示したものと基本的には同様であるが、初期条件生成部１１からの初期パターンから生成を開始する点と、収束判定部１５から入力される、収束完了を示す信号である収束フラグが１の場合には、初期状態に戻す点が異なる。
【００３９】
図２に示すパターン生成処理のフローチャートにおいて、まず、パターン生成部１２は、スケジューリング装置１０の外部から開始指示を受けて、処理の初期化を行う（ステップ１００）。この初期化では、全ＴＰの選択済フラグを０にクリアするとともに、全ＴＰの各送信先の試行有無をクリアする。
【００４０】
続いて、パターン生成部１２は、初期条件生成部１１から初期条件を受信し（ステップ１０１）、受信した初期パターンを内部保持パターンにセットするとともに（ステップ１０２）、受信したシード値を乱数生成用のシード値にセットする（ステップ１０３）。
【００４１】
次に、パターン生成部１２は、全ＴＰの選択済フラグを確認し（ステップ１０４）、全ＴＰの選択済フラグが選択済（１）でなければ（ステップ１０４：ＮＯ）、シード値により発生させた乱数に基づいていずれか１つのＴＰを変更対象ポイントＳ＿ＴＰをランダムに選択する（ステップ１０６）。一方、全ＴＰの選択済フラグが選択済（１）であれば（ステップ１０４：ＹＥＳ）、全ＴＰの選択済フラグを０にクリアするとともに、全ＴＰの各送信先の試行有無をクリアした後（ステップ１０５）、ステップ１０６へ移行する。
【００４２】
続いて、パターン生成部１２は、スケジューリング装置５０の外部から入力されるＴＰ別の送信先ＵＥリスト群のうち、Ｓ＿ＴＰの送信先ＵＥリストに記載されている各送信先の試行有無を確認し（ステップ１０７）、全て試行済みである場合（ステップ１０７：ＹＥＳ）、Ｓ＿ＴＰの選択済フラグを１にセットし（ステップ１０８）、ステップ１０６へ戻る。
【００４３】
一方、全て試行済みでない場合（ステップ１０７：ＮＯ）、パターン生成部１２は、Ｓ＿ＴＰの送信先ＵＥリストにおいて、送信先の試行有無が無となっているＵＥのうちから、いずれか１つをランダムに選択し、内部保持パターンのうちＳ＿ＴＰの新たな送信先としてセットするとともに、選択したＵＥの試行有無を試行済みにセットする（ステップ１０９）。パターン生成部１２は、このようにして内部保持パターンのうちＴＰとＵＥの組み合わせの一部、ここではＳ＿ＴＰに関する組み合わせのみを変更することにより新たなパターンを順次生成し、パターン評価部１３へ出力する（ステップ１１０）。
【００４４】
この後、パターン生成部１２は、収束判定部１５から収束パターンと収束フラグを受信し（ステップ１１１）、その収束フラグを確認する（ステップ１１２）。ここで、収束フラグ＝１であり評価値の収束が検出されている場合（ステップ１１２：ＹＥＳ）、ステップ１００へ戻って、山登り法による新たな探索を行うため、異なる初期条件を基にした新たなパターン生成を開始する。
【００４５】
一方、収束フラグ＝０であり評価値の収束が検出されていない場合（ステップ１１２：ＮＯ）、パターン生成部１２は、受信した収束パターンを内部保持パターンにセットし（ステップ１１３）、ステップ１０４に戻って、受信した収束パターンに基づくパターン生成を開始する。これにより、現行の山登り法による探索が継続されることになる。
【００４６】
＜パターン評価部＞
パターン評価部１３は、パターン生成部１２からパターンが出力されるごとに、当該パターンの評価値を順次算出する機能と、評価したパターンからなる評価済パターンと算出した評価値とを候補パターン選択部１４へ出力する機能とを有している。
パターン評価部１３については、前述の図１５に示したものと基本的には同一である。
【００４７】
評価関数は、スケジューリング装置１０の外部から入力される外部評価情報に基づいて算出されるＴＰ別下位評価値の合計値であり、下位評価値は、例えば、Proportional-Fairness法に基づき、当該ＴＰの送信先ＵＥの瞬時スループットを平均スループットで除算して得られる値である（非特許文献２）。また、この時の外部評価情報は、例えば、各ＵＥの平均スループット、各ＵＥの未送信データ量、および各ＵＥのＴＰ別チャネル品質状態である。当該チャネル品質状態とは、例えば、ＵＥからフィードバックされるＣＱＩ（Channel Quality Indicator）である（非特許文献３，４）。
【００４８】
＜候補パターン選択部＞
候補パターン選択部１４は、パターン生成部１２からパターンが出力されるごとに、当該パターンと候補パターンとの評価値を比較し、評価値が高いものを新たな候補パターンとして選択して順次出力する機能を有している。
候補パターン選択部１４については、前述の図１５に示したものと基本的には同一であるが、収束判定部１５から出力される収束フラグが１の時に、候補パターンの選択状態を初期状態に戻す点が異なる。
【００４９】
図３に示す候補パターン選択処理のフローチャートにおいて、まず、候補パターン選択部１４は、スケジューリング装置１０の外部から開始指示を受けて、処理の初期化を行う（ステップ１００）。この初期化では、内部保持評価値を０にセットするとともに、内部保持パターンの全ＴＰの送信先を送信停止（Ｂｌａｎｋ）に書き換える。
【００５０】
次に、候補パターン選択部１４は、パターン評価部１３から評価済パターンを評価値とともに受信し（ステップ１２１）、受信した評価値と内部保持評価値と比較する（ステップ１２２）。ここで、受信した評価値が内部保持評価値以下である場合（ステップ１２２：ＮＯ）、内部保持パターンからなる候補パターンと評価値とを収束判定部１５へ出力する（ステップ１２４）。
一方、受信した評価値が内部保持評価値より大きい場合（ステップ１２２：ＹＥＳ）、候補パターン選択部１４は、受信した評価済パターンと評価値とを内部保持パターンおよび内部評価値としてセットし（ステップ１２３）、ステップ１２４へ移行する。
【００５１】
この後、候補パターン選択部１４は、出力した候補パターンに対応して、収束判定部１５から出力される収束判定結果を示す収束フラグが受信されるまで待機し（ステップ１２５）、受信した収束フラグを確認する（ステップ１２６）。ここで、収束フラグ＝１であり評価値の収束が検出されている場合（ステップ１２６：ＹＥＳ）、ステップ１２０へ戻って、山登り法による新たな探索を行うため、異なる初期条件を基にして生成された新たなパターンの評価を開始する。なお、収束フラグについては、候補パターンを出力してから一定時間経過後に確認するようにしてもよい。ここで、一定時間とは、例えば、出力した候補パターンに対応する収束判定が収束判定部１５で実施され、その結果（収束フラグ）が候補パターン選択部１４に通知されるまでに要する時間である。
【００５２】
一方、収束フラグ＝０であり評価値の収束が検出されていない場合（ステップ１２６：ＮＯ）、候補パターン選択部１４は、ステップ１０４に戻って、受信した収束パターンに基づくパターン生成を開始する。これにより、現行の山登り法による探索が継続されることになる。
【００５３】
＜収束判定部＞
収束判定部１５は、候補パターン選択部１４から出力される候補パターンの評価値が一定の極値に収束したことを検出した場合、当該候補パターンを収束パターンとして選択する機能と、初期条件生成部１１に対して異なる初期パターンの生成・出力を指示し、パターン生成部１２に対してパターン生成を初期化して新たに開始するよう指示し、候補パターン選択部１４に対して候補パターンの初期化を指示する機能を有している。
【００５４】
図４に示す収束判定処理のフローチャートにおいて、まず、収束判定部１５は、スケジューリング装置１０の外部から開始指示を受けて、処理の初期化を行う（ステップ１３０）。この初期化では、収束フラグを０にクリアするとともに、内部保持評価現行値、内部保持評価前回値、収束判定カウント値、および収束判定間隔カウント値をそれぞれを０に設定する。
【００５５】
続いて、収束判定部１５は、候補パターン選択部１４から候補パターンと評価値とを受信し（ステップ１３１）、受信した候補パターンおよび評価値を内部保持パターンおよび内部保持評価現行値にセットする（ステップ１３２）。
次に、収束判定部１５は、収束判定間隔カウント値をインクリメント（＋１）し（ステップ１３３）、収束判定間隔カウント値を収束判定間隔と比較する（ステップ１３４）。
【００５６】
この際、収束判定間隔カウント値が収束判定間隔以下である場合（ステップ１３４：ＹＥＳ）、収束判定部１５は、収束判定間隔カウント値を０にクリアし（ステップ１３５）、内部保持評価現行値から内部保持評価前回値を減算することにより差分評価値を算出する（ステップ１３６）。
この後、収束判定部１５は、差分評価値と収束判定閾値とを比較し（ステップ１３７）、差分評価値が収束判定閾値以下である場合（ステップ１３７：ＹＥＳ）、評価値の変化が小さく収束傾向が見られることから、収束判定カウント値をインクリメントし（ステップ１３９）、収束判定カウント値と収束判定回数とを比較する（ステップ１４０）。
【００５７】
ここで、収束判定カウント値が収束判定回数に達している場合（ステップ１４０：ＹＥＳ）、収束判定部１５は、収束傾向が一定回数継続したことから評価値が一定の極値に収束したと判定して、収束フラグに１を設定する（ステップ１４１）。
この後、収束判定部１５は、内部保持評価現行値を内部保持評価前回値にセットし（ステップ１４２）、収束フラグを初期条件生成部１１、パターン生成部１２、および候補パターン選択部１４へ出力し、内部保持評価現行値からなる収束パターンをパターン生成部１２および送信パターン選択部１６へ出力するとともに、評価値を送信パターン選択部１６へ出力する（ステップ１４３）。
【００５８】
なお、ステップ１３４において、収束判定間隔カウント値が収束判定間隔より小さい場合（ステップ１３４：ＮＯ）、およびステップ１４０において、収束判定カウント値が収束判定回数に達していない場合（ステップ１４０：ＮＯ）、ステップ１４３へ移行する。
また、ステップ１３７において、差分評価値が収束判定閾値より大きい場合（ステップ１３７：ＮＯ）、評価値の変化が大きく収束傾向が見られないことから、収束判定部１５は、収束判定カウント値を０に設定し（ステップ１３８）、ステップ１４３へ移行する。
【００５９】
この後、収束判定部１５は、収束フラグを確認し（ステップ１４４）、収束フラグ＝１であり評価値の収束が検出されている場合（ステップ１４４：ＹＥＳ）、ステップ１３０へ戻って、山登り法による新たな探索を行うため、異なる初期条件を基にして生成される新たなパターンに関する収束判定を開始する。
【００６０】
一方、収束フラグ＝０であり評価値の収束が検出されていない場合（ステップ１４４：ＮＯ）、ステップ１３１へ戻って、新たに候補パターン選択部１４から出力される候補パターンと評価値に対する収束判定を開始する。これにより、現行の山登り法による探索が継続されることになる。
【００６１】
＜送信パターン選択部＞
送信パターン選択部１６は、収束判定部１５で選択された収束パターンのうち、評価値が最も高いものを送信パターンとして選択し、終了判定部１７へ出力する機能を有している。
【００６２】
図５に示す、送信パターン選択処理のフローチャートにおいて、まず、送信パターン選択部１６は、スケジューリング装置１０の外部から開始指示を受けて、処理の初期化を行う（ステップ１５０）。この初期化では、内部保持評価値を０に設定するとともに、内部保持パターンの全ＴＰの送信先を送信停止（Ｂｌａｎｋ）に書き換える。
【００６３】
続いて、送信パターン選択部１６は、収束判定部１５から収束パターンを評価値とともに受信し（ステップ１５１）、受信した評価値と内部保持評価値とを比較する（ステップ１５２）。ここで、受信した評価値が内部保持評価値以下である場合（ステップ１５２：ＮＯ）、内部保持パターンを送信パターンとして終了判定部１７へ出力し（ステップ１５４）、ステップ１５１へ戻る。
【００６４】
一方、受信した評価値が内部保持評価値より大きい場合（ステップ１５２：ＹＥＳ）、受信した収束パターンおよび評価値を、内部保持パターンおよび内部保持評価値にセットし（ステップ１５３）、ステップ１５４へ移行する。
【００６５】
＜終了判定部＞
終了判定部１７は、パターン生成部１２で生成されたパターンに対する評価回数が、スケジューリング装置１０の外部から入力される評価回数上限に達した時点で、送信パターン選択部１６で選択されている送信パターンを最適送信パターンとして選択する機能と、この最適送信パターンすなわちスケジューリング結果と終了フラグ＝１とをスケジューリング装置１０の外部へ出力する機能とを有している。終了判定部１７については、前述の図１５に示したものと同一である。
【００６６】
なお、収束パターンを探索するための探索アルゴリズムについては、必ずしも山登り法でなくてもよい。例えば、一巡に限り評価値が増加するまでパターンの生成を繰り返す貪欲法や、予め送信を停止する送信ポイント数の違い等によりパターンをグループ分けして各グループの代表評価値を基準に詳細に探索するグループを決定した後にその制約条件を満たすようにパターン生成を行う分枝限定法、２つ以上の送信先のユーザ端末候補を残すことにより同時に２つ以上のパターンを保持する動的計画法など、一般に知られる組合せ最適化問題の解法が適用できる。
【００６７】
また、上記の実施例では、いずれか１つの送信ポイントを変更対象ポイントとして選択する例を示したが、変更対象ポイントとして選択する送信ポイントの数は必ずしも１つでなくともよい。例えば、いずれか２つ以上の送信ポイントを変更対象ポイントとして選択して、同時に２つの送信ポイントの送信先となるユーザ端末を変更したパターンを生成することもある。予め測定または推定等により把握した送信ポイント間の無線の電波状態に基づいて、送信ポイント間の無線の電波状態に相関がない２つ以上の送信ポイントを選択しても、互いの送信ポイントの送信先のユーザ端末の選択に影響することなく、同時に２つの送信ポイントの送信先ユーザ端末の選択が可能になるため、全ての送信ポイントの送信先のユーザ端末を選択するまでの時間を短縮する効果がある。
【００６８】
また、上記の実施例では、選択した送信ポイントの送信先のユーザ端末が決まるたびに、候補パターンとして出力する例を示したが、送信先のユーザ端末の決定を候補パターンに反映するタイミングは必ずしも上記に限らない。例えば、全ての送信ポイントの送信先のユーザ端末が決定した時点で、つまり全ての送信ポイントの選択を一通り完了した時点で候補パターンに反映して出力してもよい。
【００６９】
［第１の実施の形態の効果］
このように、本実施の形態は、収束パターン選択部１０Ａが、指定された初期条件に基づいて複数の異なるパターンを順次生成し、評価値が極値に収束したパターンを収束パターンとして選択し、当該収束パターンが選択されるごとに初期条件を変更して収束パターンの選択を繰り返し実行し、送信パターン決定部１０Ｂが、収束パターン選択部１０Ａで得られた各収束パターンのうち評価値が最も高いものを最適送信パターンとして選択するようにしたものである。
【００７０】
より具体的には、収束パターン選択部１０Ａにおいて、初期条件生成部１１が、パターンの生成に用いる初期条件として初期パターンおよびシード値を生成して出力し、パターン生成部１２が、初期パターンから、シード値により生成した乱数に基づき選択した組み合わせの一部を順次変更することにより、複数の異なるパターンを生成して順次出力し、パターン評価部１３が、パターン生成部１２からパターンが出力されるごとに、当該パターンの評価値を順次算出し、候補パターン選択部１４が、パターン生成部１２からパターンが出力されるごとに、当該パターンと候補パターンとの評価値を比較し、評価値が高いものを新たな候補パターンとして選択して順次出力し、収束判定部１５が、候補パターン選択部１４から出力される候補パターンの評価値が収束したことを検出した場合、当該候補パターンを収束パターンとして選択し、初期条件生成部１１に対して初期条件である初期パターンまたはシード値のいずれか一方または両方の変更を指示し、パターン生成部１２に対してパターン生成を初期化して新たに開始するよう指示し、候補パターン選択部１４に対して候補パターンの初期化を指示するようにしたものである。
【００７１】
また、送信パターン決定部１０Ｂにおいて、送信パターン選択部１６が、収束判定部１５で選択された収束パターンのうち、評価値が最も高いものを送信パターンとして選択し、終了判定部１７が、生成されたパターンの評価回数が評価回数上限に達した時点で、送信パターン選択部１６で選択されている送信パターンを最適送信パターンとして選択するようにしたものである。
【００７２】
そして、パターン生成部１２が、パターン生成を開始する際、初期条件生成部１１から出力された初期パターンのうち、シード値により生成した乱数に基づいて、いずれか１つの送信ポイントを変更対象送信ポイントとして選択し、当該変更対象送信ポイントについてのみ送信先となるユーザ端末を変更したパターンを生成して出力し、収束判定部１５から収束パターンが出力されるごとに、当該収束パターンのうち、いずれか１つの送信ポイントを変更対象ポイントとして選択し、当該変更対象送信ポイントについてのみ送信先となるユーザ端末を変更したパターンを生成して出力し、収束判定部１５が、候補パターン選択部１４から順次出力される候補パターンのうち、一定の収束判定間隔で離間して出力された２つのパターンごとに、両者の評価値の変化量を算出し、得られた変化量が収束判定回数だけ連続して収束判定閾値を下回った場合に、評価値が収束したことを検出するようにしたものである。
【００７３】
これにより、山登り法により評価値が極値に収束した収束パターンが選択されるごとに、初期パターンを変更した上で収束パターンの選択が複数回繰り返し実行され、得られた各収束パターンのうち評価値の最も高いものが最適送信パターンとして選択される。したがって、最初に見つかった極値を最終的な収束値として選択して、それ以降の探索を終了してしまう場合と比較して、より高い収束値を持つパターンを最適送信パターンとして選択することが可能となる。
【００７４】
また、スケジューリング処理においては、スケジューリング期間が規定されているため、評価回数には上限が存在しており、１回の探索ごとに評価回数を適切に分配する必要がある。本実施の形態によれば、収束を検出した後に新たな探索を開始するため、１回の探索に評価回数が不足して収束前に次の実行に移る事態を回避することが可能となる。また、収束検出後に新たな探索を開始することは、各探索において必要十分な評価回数を分配することと等価となり、限られた評価回数を効率的に利用することが可能となる。
【００７５】
また、本実施の形態において、初期条件生成部１１が、初期パターンを最初に出力する際、パターンの生成時に用いるシード値を生成して出力し、収束判定部１５での収束の検出ごとにユニークな値を持つシード値を生成して出力し、パターン生成部１２が、変更対象送信ポイントを選択する際、初期条件生成部１１から出力されたシード値から生成した乱数に基づき当該変更対象送信ポイントを選択するようにしてもよい。
【００７６】
一般に、演算処理で生成される乱数は、シード値で決定される乱数列からなる擬似乱数であり、シード値の変更により乱数列も変更されることから、異なる順序で乱数が生成されることになる。これにより、評価値が収束するごとにユニークなシード値が生成されて、異なる順序で変更対象ポイントが順次選択されることになる。したがって、評価値が収束するごとに山登り法による新たな探索を開始する際、前回とは全く異なるルートで収束パターンを探索することができ、探索範囲に偏りのない効率的な探索を実現することができる。
【００７７】
［第２の実施の形態］
次に、図６を参照して、本発明の第２の実施の形態にかかるスケジューリング装置１０について説明する。
本構成は、初期条件生成部１１にＴＰ別の送信先ＵＥリストが入力される点と、収束検出後において初期条件生成部１１が出力する初期パターンとが、第１の実施の形態と異なる。
【００７８】
すなわち、本実施の形態において、初期条件生成部１１は、初期パターンを最初に出力する際、送信ポイントのすべてを送信停止とした初期パターンを生成して出力し、収束判定部１５での収束の検出ごとに、送信ポイントのうちから選択したいずれか１つの送信ポイントについて、当該送信ポイントを送信元とし得るユーザ端末群の中からいずれか１つを新たな送信先として選択し、当該送信ポイント以外の送信ポイントをすべて送信停止とした初期パターンを生成して出力する機能を有している。
【００７９】
図６においては、スケジューリング装置５０の外部から入力されるＴＰ別の送信先ＵＥリスト群が、パターン生成部１２に加えて初期条件生成部１１にも入力されている。他の構成については、第１の実施の形態と同様である。
【００８０】
初期条件生成部１１は、収束判定部１５から、評価値の収束検出を示す収束フラグ＝１が出力された場合、図７の初期条件生成処理を実行する。
【００８１】
図７において、まず、初期条件生成部１１は、１つのＴＰをランダムに選択してＳ＿ＴＰ’とし（ステップ２００）、Ｓ＿ＴＰ’の送信先ＵＥ候補リストの中から、新たな送信先ＵＥをランダムに選択する（ステップ２０１）。
次に、初期条件生成部１１は、Ｓ＿ＴＰ’の送信先のみを選択した新たな送信先ＵＥとし、Ｓ＿ＴＰ’以外の他のＴＰの送信先をすべて送信停止（Ｂｌａｎｋ）とした初期パターンを生成する（ステップ２０２）。
【００８２】
続いて、初期条件生成部１１は、それまでに用いたシード値とは異なるユニークな値からなるシード値を生成した後（ステップ２０３）、これら新たな初期パターンおよびシード値をパターン生成部１２に出力し（ステップ２０４）、一連の初期条件生成処理を終了する。
【００８３】
なお、図７において、シード値の変更を、初期パターンの更新後としているのは、パターン生成部１２にて初期化後に最初に選択されるＳ＿ＴＰをＳ＿ＴＰ’と異なるものとするためである。これにより、異なる収束値となる可能性を高めることができる。また、開始指示直後に生成する初期パターンについては、全ＴＰの送信先をＢｌａｎｋにする。
本実施例では、収束検出後に初期パターンを生成する際において、Ｓ＿ＴＰ’の送信先ＵＥをランダムとしたが、評価値が２番目に高い値を示したパターン（Ｓ＿ＴＰ’以外のＴＰがすべてＢｌａｎｋの条件）における送信先ＵＥとしても良い。
【００８４】
［第２の実施の形態の効果］
このように本実施の形態は、初期条件生成部１１が、初期パターンを最初に出力する際、送信ポイントのすべてを送信停止とした初期パターンを生成して出力し、収束判定部１５での収束の検出ごとに、送信ポイントのうちから選択したいずれか１つの送信ポイントについて、当該送信ポイントを送信元とし得るユーザ端末群の中からいずれか１つを新たな送信先として選択し、当該送信ポイント以外の送信ポイントをすべて送信停止とした初期パターンを生成して出力するようにしたものである。
【００８５】
これにより、評価値が収束するごとに異なる送信ポイントが、送信先を変更する最初の送信ポイントとして選択されることになる。したがって、評価値が収束するごとに山登り法による新たな探索を開始する際、前回とは全く異なる始点から収束パターンを探索することができ、探索範囲に偏りのない効率的な探索を実現することができる。
【００８６】
［第３の実施の形態］
次に、図８を参照して、本発明の第３の実施の形態にかかるスケジューリング装置１０について説明する。
図８に示すように、本構成は、基本的には実施例１と同様であるが、収束判定部１５に入力される収束判定条件と、収束判定部１５の動作が異なる。
【００８７】
すなわち、本実施の形態にかかる収束判定部１５は、候補パターン選択部１４から順次出力される候補パターンの評価値を記録するためのテーブルを有し、収束が最初に検出されるまでは、収束判定回数の間隔で当該評価値を当該テーブルに記録し、収束が最初に検出された後は、候補パターン選択部１４から評価値が新たに出力されるごとに、当該テーブルに記録された評価値と比較し、これら評価値が規定合致判定回数だけ連続して一致した時点で、当該評価値が収束したと判定する機能を有している。
【００８８】
なお、本実施の形態では、初回の結果のみを前記テーブルに記憶し、初回の結果とのみ評価値の比較を行うが、比較する結果は必ずしも初回の結果のみでなくともよい。例えば、複数のテーブルを具備し、初回の結果以外も記憶し、記憶した全ての評価値と比較を行ってもよい。この場合、いずれか１つ以上の評価値が規定合致判定回数だけ連続して一致した時点で当該評価値が収束したと判定する。
【００８９】
また、本実施の形態において、２回目以降の結果を記憶する際に当該の探索において収束値が得られなければ、次回の探索時にテーブルを上書きするようにしてもよい。例えば、２回目の探索において、収束値が得られない場合は、途中まで記憶した２回目の結果は３回目の結果で上書きする。これにより、初回の結果とのみ比較を行う場合、２回目以降に同一の収束パターンが得られる可能性があるのに対し、２回目以降に収束値が得れれる結果とも比較を行うことで、収束パターンの異なる結果が得られ易くなる効果がある。
【００９０】
また、本実施の形態において、結果を記憶するテーブルを２つ備えてもよい。１つは、前述の実施例と同様に、初回の結果を記憶し、もう１つは、２回目の結果を記憶する。２回目の探索により収束パターンが得られた場合、初回に得られた収束パターンの評価値と比較し、収束パターンとの評価値が低いほうのテーブルを３回目の結果で上書きする。これにより、初回の収束パターンの評価値が低くても、２回目以降に得られる評価値が高い収束パターンとの比較が可能になり、かつ、探索時の収束傾向の比較は常に１回にすることができる。さらに、結果を保持するテーブルを２つのみで済むため、小規模化の効果がある。
【００９１】
これにより、最初の探索における評価値の遷移がテーブルに記録され、２回目以降の探索において、評価値がこれと同一の遷移を示した場合には、収束されるパターンが同一になると判断され、収束前でも収束と判定して再実行が開始される。
図９に示すパターン評価値の遷移において、図９（ａ）はパターン評価値の遷移を示すグラフ、図９（ｂ）はテーブルにおける評価値の記録例である。
【００９２】
図１０および図１１に示した収束処理フローは、前述した図４の処理に加えて、テーブルに内部保持評価現行値を収束判定間隔ごとに記録する点と、２回目以降の探索において、当該テーブルに記録された評価値と内部保持評価現行値とを収束判定間隔ごとに比較し、これらテーブルに記録された評価値と内部保持評価現行値との値の合致回数が、スケジューリング装置１０の外部から入力される合致判定回数に達した場合に、強制的に収束と判定する点が特徴である。
【００９３】
この目的のために、収束判定部１５は、１回目の探索か否かを識別するためのテーブル更新禁止フラグ（２回目以降の場合には更新を禁止）と、テーブルの書き込み・読み出し位置を示すテーブル書込インデックス・テーブル読出インデックスとを新たに備える。また、テーブルに何回連続して一致したかを計測するための合致カウンタも新たに備える。
【００９４】
図１０において、まず、収束判定部１５は、スケジューリング装置１０の外部から開始指示を受けて、テーブル更新禁止フラグを０（更新許可）にセットするとともに、テーブル書込インデックスを１に設定した後（ステップ３００）、処理の初期化を行う（ステップ３０１）。この初期化では、収束フラグを０にクリアするとともに、内部保持評価現行値、内部保持評価前回値、収束判定カウント値、および収束判定間隔カウント値をそれぞれを０に設定する。また、テーブル読出インデックスと合致カウント値を０に設定する。
【００９５】
続いて、収束判定部１５は、候補パターン選択部１４から候補パターンと評価値とを受信し（ステップ３０２）、受信した候補パターンおよび評価値を内部保持パターンおよび内部保持評価現行値にセットする（ステップ３０３）。
次に、収束判定部１５は、収束判定間隔カウント値をインクリメント（＋１）して（ステップ３０４）、収束判定間隔カウント値を収束判定間隔と比較し（ステップ３０５）、収束判定間隔カウント値が収束判定間隔より大きい場合（ステップ３０５：ＮＯ）、後述する図１０のステップ３１０へ移行する。
【００９６】
この際、収束判定間隔カウント値が収束判定間隔以下である場合（ステップ３０５：ＹＥＳ）、収束判定部１５は、収束判定間隔カウント値を０にクリアし（ステップ３０６）、テーブル更新禁止フラグを確認する（ステップ３０７）。
ここで、テーブル更新禁止フラグ＝１であり、テーブルの更新が禁止されている場合には（ステップ３０７：ＮＯ）、図１１のステップ３２０へ移行する。
【００９７】
一方、テーブル更新禁止フラグ＝０であり、テーブルの更新が禁止されていない場合（ステップ３０７：ＹＥＳ）、収束判定部１５は、テーブルのうちテーブル書込インデックスの記憶領域に、内部保持評価現行値を書き込み（ステップ３０８）、テーブル書込インデックスをインクリメントした後（ステップ３０９）、図１１のステップ３２３へ移行する。
【００９８】
図１１のステップ３２０において、収束判定部１５は、テーブルのうちテーブル読出インデックスの記憶領域から評価値を読み出し（ステップ３２０）、読み出した評価値と内部保持評価現行値とを比較する（ステップ３２１）。
ここで、読み出した評価値が内部保持評価現行値以上である場合（ステップ３２１：ＮＯ）、収束判定部１５は、合致カウント値を０にクリアし（ステップ３２２）、後述するステップ３２３へ移行する。
【００９９】
一方、読み出した評価値が内部保持評価現行値より小さい場合（ステップ３２１：ＹＥＳ）、収束判定部１５は、合致カウンタ値をインクリメントし（ステップ３２４）、合致カウント値と合致判定回数とを比較する（ステップ３２５）。
ここで、合致カウント値が合致判定回数に達していない場合（ステップ３２５：ＮＯ）、後述するステップ３２３へ移行し、合致カウント値が合致判定回数に達している場合（ステップ３２５：ＹＥＳ）、後述するステップ３３０へ移行する。
【０１００】
ステップ３２３において、収束判定部１５は、内部保持評価現行値から内部保持評価前回値を減算することにより差分評価値を算出し（ステップ３２３）、差分評価値と収束判定閾値とを比較する（ステップ３２６）。
ここで、差分評価値が収束判定閾値より大きい場合（ステップ３２６：ＮＯ）、評価値の変化が大きく収束傾向が見られないことから、収束判定部１５は、収束判定カウント値を０に設定し（ステップ３２７）、図１０のステップ３１０へ移行する。
【０１０１】
一方、差分評価値が収束判定閾値以下である場合（ステップ３２６：ＹＥＳ）、評価値の変化が小さく収束傾向が見られることから、収束判定部１５は、収束判定カウント値をインクリメントし（ステップ３２８）、収束判定カウント値と収束判定回数とを比較する（ステップ３２９）。
ここで、収束判定カウント値が収束判定回数に達していない場合（ステップ３２９：ＮＯ）、図１０のステップ３１０へ移行する。
【０１０２】
また、収束判定カウント値が収束判定回数に達している場合（ステップ３２９：ＹＥＳ）、収束判定部１５は、収束傾向が一定回数継続したことから評価値が一定の極値に収束したと判定して、収束フラグに１を設定した後（ステップ３３０）、内部保持評価現行値を内部保持評価前回値にセットし（ステップ３３１）、図１０のステップ３１０へ移行する。
【０１０３】
図１０のステップ３１０において、収束判定部１５は、収束フラグを初期条件生成部１１、パターン生成部１２、および候補パターン選択部１４へ出力し、内部保持評価現行値からなる収束パターンをパターン生成部１２および送信パターン選択部１６へ出力するとともに、評価値を送信パターン選択部１６へ出力する（ステップ３１０）。
【０１０４】
この後、収束判定部１５は、収束フラグを確認し（ステップ３１１）、収束フラグ＝１であり評価値の収束が検出されている場合（ステップ３１１：ＹＥＳ）、ステップ３０１へ戻って、山登り法による新たな探索を行うため、異なる初期条件を基にして生成される新たなパターンに関する収束判定を開始する。
【０１０５】
一方、収束フラグ＝０であり評価値の収束が検出されていない場合（ステップ３１１：ＮＯ）、ステップ３０２へ戻って、新たに候補パターン選択部１４から出力される候補パターンと評価値に対する収束判定を開始する。これにより、現行の山登り法による探索が継続されることになる。
【０１０６】
なお、上記の例では、初回の結果との内部保持評価現行値が所定の閾値以下である場合に合致と判定しているが、合致の判定方法はこれに限らない。例えば、初回の結果との差分が閾値以上であるが、初回の結果よりも評価値が低い場合は、合致と判定してもよい。つまり、図１１のステップ３２１において、上記の実施例では、判定条件が「＝」であるのに対し、この場合は「≧」が判定条件となる。これにより、初回の結果よりも悪い結果が得られる可能性を低減できる。
また、閾値を徐々に小さくしてもよい。探索初期の段階では、閾値を大きく設定しておき、探索が経過するにつれて、閾値を小さくしてもよい。
【０１０７】
図１２に示す、評価値と経過時間の関係例では、初回の探索は評価値が収束して収束パターンが得られるまで探索を繰り返す。収束パターンが得られたら、初期条件を変更して再実行する。２回目の探索では、初回の収束傾向と同一であるか否かを比較しながら探索を行う。この場合、初回と２回目と収束傾向が異なるため、途中で中断することなく、収束値が得られるまで探索を繰り返す。同様に３回目の探索を開始するが、初回の収束傾向と３回目の収束傾向とを比較すると収束傾向が同一であると判定されるため、収束値が得られる前の段階で探索を中断し、初期条件を変更して再実行する。
【０１０８】
［第３の実施の形態の効果］
このように本実施の形態は、収束判定部１５が、候補パターン選択部１４から順次出力される候補パターンの評価値を記録するためのテーブルを有し、収束が最初に検出されるまでは、収束判定回数の間隔で当該評価値を当該テーブルに記録し、収束が最初に検出された後は、候補パターン選択部１４から評価値が新たに出力されるごとに、当該テーブルに記録された評価値と比較し、これら評価値が規定合致判定回数だけ連続して一致した時点で、当該評価値が収束したと判定するようにしたものである。
【０１０９】
これにより、最初の探索における評価値の遷移がテーブルに記録され、２回目以降の探索において、評価値がこれと同一の遷移を示した場合には、収束されるパターンが同一になると判断され、収束前でも収束と判定して再実行が開始される。したがって、実際に評価値が収束する前に強制的に収束と判定することができ、スケジューリング処理に要する時間を短縮することが可能となる。
【０１１０】
［第４の実施の形態］
次に、図１３を参照して、本発明の第４の実施の形態にかかるスケジューリング装置１０の構成について説明する。
【０１１１】
本構成は、図１３に示すように、実施例１におけるパターン生成部１２、パターン評価部１３、候補パターン選択部１４、および収束判定部１５を並列化した構成である。本構成により、より多くの収束パターン群から送信パターンを選択することが可能になる。
【０１１２】
すなわち、本実施の形態にかかるスケジューリング装置１０は、パターン生成部１２、パターン評価部１３、候補パターン選択部１４、および収束判定部１５からなる処理系を複数備えている。
また、初期条件生成部１１は、処理系ごとに異なるシード値を生成して出力する機能を有している。
また、送信パターン選択部１６は、これら処理系が出力された収束パターンのうち、評価値が最も高いものを送信パターンとして選択する機能を有している。
【０１１３】
図１３の構成例では、パターン生成部１２Ａ、パターン評価部１３Ａ、候補パターン選択部１４Ａ、および収束判定部１５Ａからなる処理系Ａと、パターン生成部１２Ｂ、パターン評価部１３Ｂ、候補パターン選択部１４Ｂ、および収束判定部１５Ｂからなる処理系Ｂとが設けられている。初期条件生成部１１、送信パターン選択部１６、および終了判定部１７は、いずれの処理系Ａ，Ｂにも共通である。ここでは、並列数を２としたが、これに限定されるものではない。
【０１１４】
本構成において、初期条件生成部１１は、スケジューリング装置１０の外部から開始指示を受けて、初期パターンおよびシード値Ａ，Ｂを、パターン生成部１２Ａ，１２Ｂに出力する。ここで、パターン生成部１２Ａ，１２Ｂにそれぞれ出力するシード値Ａ，Ｂは、互いに異なる値であるが、初期パターンはパターン生成部１２Ａ，１２Ｂに対して同じものが順に出力される。
【０１１５】
また、収束判定部１５Ａが収束フラグＡを出力した場合には、初期条件生成部１１は、すべての処理系においてユニークな値からなるシード値Ａを生成し、初期パターンと併せてパターン生成部１２Ａに出力する。収束判定部１５Ｂが収束フラグＢを出力した場合にも同様に、すべての処理系においてユニークな値からなるシード値Ｂを生成し、初期パターンと併せてパターン生成部１２Ｂに出力する。これにより、並列化された処理が、それぞれ異なる初期条件で実行させることが可能になる。
【０１１６】
送信パターン選択部１６は、第１の実施の形態と同様であり、収束判定部１５Ａ，１５Ｂより出力される収束パターン群の中で、最も高い評価値を示すパターンを送信パターンとして選択し終了判定部１７に出力する。
【０１１７】
［第４の実施の形態の効果］
このように、本実施の形態は、パターン生成部１２、パターン評価部１３、候補パターン選択部１４、および収束判定部１５からなる処理系を複数備え、初期条件生成部１１が、処理系ごとに異なるシード値を生成して出力し、送信パターン選択部１６が、これら処理系から出力された収束パターンのうち、評価値が最も高いものを送信パターンとして選択するようにしたものである。
【０１１８】
これにより、処理系ごとに異なるシード値に基づく探索が並列的に実行されることになる。したがって、短い処理時間で、より多くの収束パターン群から送信パターンを選択することが可能になる。
【０１１９】
［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。
【符号の説明】
【０１２０】
１０…スケジューリング装置、１０Ａ…収束パターン選択部、１０Ｂ…送信パターン決定部、１１…初期条件生成部、１２，１２Ａ，１２Ｂ…パターン生成部、１３，１３Ａ，１３Ｂ…パターン評価部、１４，１４Ａ，１４Ｂ…候補パターン選択部、１５，１５Ａ，１５Ｂ…収束判定部、１６…送信パターン選択部、１７…終了判定部。
【図１】
2017038683.tif 000003
【図２】
2017038683.tif 000004
【図３】
2017038683.tif 000005
【図４】
2017038683.tif 000006
【図５】
2017038683.tif 000007
【図６】
2017038683.tif 000008
【図７】
2017038683.tif 000009
【図８】
2017038683.tif 000010
【図９】
2017038683.tif 000011
【図１０】
2017038683.tif 000012
【図１１】
2017038683.tif 000013
【図１２】
2017038683.tif 000014
【図１３】
2017038683.tif 000015
【図１４】
2017038683.tif 000016
【図１５】
2017038683.tif 000017
【図１６】
2017038683.tif 000018
【図１７】
2017038683.tif 000019
【図１８】
2017038683.tif 000020
【国際調査報告】
2017038683.tif 000021
2017038683.tif 000022
2017038683.tif 000023
2017038683.tif 000024