(57)【要約】【課題】周囲の基地局設置状況を考慮した基地局設置場所の決定方法を提供する。【解決手段】基地局設置場所決定装置の処理方法であって、複数の基地局設置候補場所と、その基地局設置候補場所に割り当て可能な通信チャネルと、通信チャネルの通信電波が届く区間とを対応付けた複数の基地局候補の中から任意に基地局設置場所とそこに割り当てる通信チャネルとを選択し、選択された通信チャネルの通信電波と干渉する他の基地局候補を除いた候補の中から他の基地局設置候補を決定する基地局設置場所決定方法。【選択図】図１１
2016039404.tif 000002
【特許請求の範囲】
【請求項１】
基地局設置場所決定装置の処理方法であって、
複数の基地局設置候補場所と、その基地局設置候補場所に設置する基地局に割り当て可能な通信チャネルと、を対応付けた複数の基地局候補であって、それぞれの基地局候補には、その基地局候補が発信する通信電波が届く区間が定められており、それら複数の基地局候補の中から、基地局設置候補場所と、その基地局設置候補場所に設置する基地局に割り当てる通信チャネルとを選択して第１基地局候補に決定する第１ステップと、
前記第１ステップで選択した基地局設置候補場所とその基地局設置候補場所に設置する基地局に割り当てることができる全ての通信チャネルとの組み合わせを含む基地局候補を選択する第２ステップと、
前記第１基地局候補が発信する通信電波に対して干渉する前記第１基地局候補以外の基地局候補を選択する第３ステップと、
前記第３ステップまでに選択した基地局候補を除く前記基地局候補の中から前記第１基地局候補が発信する通信電波が干渉する基地局候補を選択するとともに、その選択した基地局候補について定められた通信電波が届く区間に含まれる前記第１基地局候補が発信する通信電波が届く区間を選択する第４ステップと、
を有し、
前記基地局候補の中から前記第１ステップから第３ステップで選択された基地局候補を除いた基地局候補から、さらに第４ステップで選択した区間を除いた基地局候補を新たな基地局候補として前記第１ステップからのステップを繰り返す
基地局設置場所決定方法。
【請求項２】
前記通信電波が届く区間は、所定のフレームロス率以下で通信できる区間を示す通信可能区間と、所定のフレームロス率以下で通信できず他の基地局が発信する通信電波に影響を及ぼす区間を示す電波干渉区間とを含み、
前記第３ステップにおいて、
前記第１基地局候補の通信可能区間の少なくとも一部を自基地局の通信可能区間に含む、
前記第１ステップで選択した通信チャネルと干渉する通信チャネルに対応付けられた前記第１基地局候補以外の基地局候補と、
前記第１基地局候補の通信可能区間の少なくとも一部を自基地局の電波干渉区間に含む、前記第１ステップで選択した通信チャネルと干渉する通信チャネルに対応付けられた前記第１基地局候補以外の基地局候補と、
を前記通信電波に対して干渉する前記第１基地局候補以外の基地局候補として選択する
請求項１に記載の基地局設置場所決定方法。
【請求項３】
前記通信電波が届く区間は、所定のフレームロス率以下で通信できる区間を示す通信可能区間と、所定のフレームロス率以下で通信できず他の基地局が発信する通信電波に影響を及ぼす区間を示す電波干渉区間とを含み、
前記第４ステップにおいて、
前記第１基地局候補の電波干渉区間の少なくとも一部を自基地局の通信可能区間に含む、
前記第１ステップで選択した通信チャネルと干渉する通信チャネルに対応付けられた前記第３ステップまでに選択した基地局候補以外の基地局候補を、前記通信電波が干渉する基地局候補として選択するとともに、選択した当該基地局候補における前記通信可能区間に含まれる前記第１基地局候補の電波干渉区間を選択する
請求項１または２に記載の基地局設置場所決定方法。
【請求項４】
前記第１ステップにおいて、任意の基地局設置候補場所とその基地局設置候補場所に設置する基地局に割り当て可能な通信チャネルとを選択する
請求項１から請求項３の何れか１項に記載の基地局設置場所決定方法。
【請求項５】
前記第１ステップから前記第４ステップを繰り返して選択された全ての基地局候補に基づいて基地局を配置したときに、予め設定された全ての通信対象位置のそれぞれにおいて、他の基地局に割り当てられた通信チャネルと干渉することなく、所定の数の基地局と通信を行うことができる場合の基地局候補の組み合わせを基地局配置案の一つとして決定する
請求項１から請求項４の何れか１項に記載の基地局設置場所決定方法。
【請求項６】
基地局設置候補場所には予めその基地局設置候補場所に基地局を設置した場合の設置コストが設定されていて、
前記決定した基地局配置案のそれぞれにおいて選択された全ての基地局設置候補場所について前記設置コストを合計し、
さらに複数の基地局配置案の中から最も前記設置コストの合計が小さい場合の基地局配置案を選択する
請求項５に記載の基地局設置場所決定方法。
【請求項７】
請求項１から請求項６のうち何れか１項に記載の基地局設置場所決定方法を実行する計算部、
を備える基地局設置場所決定装置。
【請求項８】
基地局設置場所決定装置のコンピュータを、
複数の基地局設置候補場所と、その基地局設置候補場所に設置する基地局に割り当て可能な通信チャネルと、を対応付けた複数の基地局候補であって、それぞれの基地局候補には、その基地局候補が発信する通信電波が届く区間が定められており、それら複数の基地局候補の中から、基地局設置候補場所と、その基地局設置候補場所に設置する基地局に割り当てる通信チャネルとを選択して第１基地局候補に決定する第１ステップを実行する手段、
前記第１ステップで選択した基地局設置候補場所とその基地局設置候補場所に設置する基地局に割り当てることができる全ての通信チャネルとの組み合わせを含む基地局候補を選択する第２ステップを実行する手段、
前記第１基地局候補が発信する通信電波に対して干渉する前記第１基地局候補以外の基地局候補を選択する第３ステップを実行する手段、
前記第３ステップまでに選択した基地局候補を除く前記基地局候補の中から前記第１基地局候補が発信する通信電波が干渉する基地局候補を選択するとともに、その選択した基地局候補について定められた通信電波が届く区間に含まれる前記第１基地局候補が発信する通信電波が届く区間を選択する第４ステップを実行する手段、
前記基地局候補の中から前記第１ステップから第３ステップで選択された基地局候補を除いた基地局候補から、さらに第４ステップで選択した区間を除いた基地局候補を新たな基地局候補として前記第１ステップからのステップを繰り返す手段、
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、基地局設置場所決定装置、基地局設置場所決定方法及びプログラムに関する。
【背景技術】
【０００２】
従来から、線路を複数の区間に区切り、各区間に進入する列車を制限することで列車同士の衝突事故を防止し安全な鉄道輸送を実現する列車制御システムが利用されてきた。しかし、この方法によって列車間隔を制御するためには、軌道回路や地上信号機、自動列車停止装置など多くの地上設備が必要になるという問題があった。
【０００３】
一方、近年の無線通信技術や情報処理技術の発展に伴い、無線通信技術を利用した列車制御システムの導入も始まっている。この無線通信による列車制御の場合、各列車が自分の位置情報を近くの基地局に送信し、そこから各列車の位置情報がさらに地上装置に送信される。そして、地上装置は、集約した各列車の位置情報を利用して列車間隔、進路、踏切の制御などを行う。また、地上装置は、速度パターンや列車の先頭が超えてはならない限界の位置などの情報を、各基地局を介して各列車に無線通信にて伝送し、列車間隔などの制御を行う。この無線通信による列車制御システムでは、従来必要とされた多くの地上設備を削減することができる。
【０００４】
ところで、無線通信を利用した列車制御システムを導入する場合、無線通信の通信品質が問題となる。例えば通信品質が十分ではない場合、安全性確保の観点から頻繁に列車を停止させなければならなくなったり、列車の走行を正確に制御できなくなったりする。無線通信の通信品質を維持する技術については、例えば特許文献１に開示がある。特許文献１では、利用者が集中する列車において、利用者が所持する携帯端末からの同時接続数の急激な増加による通信品質の低下を防ぐために、各基地局が収容する端末数に応じて変動する干渉量を考慮しつつ列車内の端末に対する通信品質が所望値を満たすように、最小数の基地局を配置する方法が記載されている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第４６５５８３６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかし、列車制御システムにおける無線通信に要求されるのは、想定される最大同時接続数に対して通信品質を保つことだけではなく、列車の安全を確保するために列車が通信を行う位置において常に十分な通信品質を確保することである。
【０００７】
そこでこの発明は、上述の課題を解決することのできる基地局設置場所決定装置、基地局設置場所決定方法及びプログラムを提供することを目的としている。
【課題を解決するための手段】
【０００８】
本発明の第１の態様は、基地局設置場所決定装置の処理方法であって、複数の基地局設置候補場所と、その基地局設置候補場所に設置する基地局に割り当て可能な通信チャネルと、を対応付けた複数の基地局候補であって、それぞれの基地局候補には、その基地局候補が発信する通信電波が届く区間が定められており、それら複数の基地局候補の中から、基地局設置候補場所と、その基地局設置候補場所に設置する基地局に割り当てる通信チャネルとを選択して第１基地局候補に決定する第１ステップと、前記第１ステップで選択した基地局設置候補場所とその基地局設置候補場所に設置する基地局に割り当てることができる全ての通信チャネルとの組み合わせを含む基地局候補を選択する第２ステップと、前記第１基地局候補が発信する通信電波に対して干渉する前記第１基地局候補以外の基地局候補を選択する第３ステップと、前記第３ステップまでに選択した基地局候補を除く前記基地局候補の中から前記第１基地局候補が発信する通信電波が干渉する基地局候補を選択するとともに、その選択した基地局候補について定められた通信電波が届く区間に含まれる前記第１基地局候補が発信する通信電波が届く区間を選択する第４ステップと、を有し、前記基地局候補の中から前記第１ステップから第３ステップで選択された基地局候補を除いた基地局候補から、さらに第４ステップで選択した区間を除いた基地局候補を新たな基地局候補として前記第１ステップからのステップを繰り返す基地局設置場所決定方法である。
【０００９】
本発明の第２の態様における基地局設置場所決定方法における前記通信電波が届く区間は、所定のフレームロス率以下で通信できる区間を示す通信可能区間と、所定のフレームロス率以下で通信できず他の基地局が発信する通信電波に影響を及ぼす区間を示す電波干渉区間とを含み、前記第３ステップにおいて、前記第１基地局候補の通信可能区間の少なくとも一部を自基地局の通信可能区間に含む、前記第１ステップで選択した通信チャネルと干渉する通信チャネルに対応付けられた前記第１基地局候補以外の基地局候補と、前記第１基地局候補の通信可能区間の少なくとも一部を自基地局の電波干渉区間に含む、前記第１ステップで選択した通信チャネルと干渉する通信チャネルに対応付けられた前記第１基地局候補以外の基地局候補と、を前記通信電波に対して干渉する前記第１基地局候補以外の基地局候補として選択する。
【００１０】
本発明の第３の態様における基地局設置場所決定方法における前記通信電波が届く区間は、所定のフレームロス率以下で通信できる区間を示す通信可能区間と、所定のフレームロス率以下で通信できず他の基地局が発信する通信電波に影響を及ぼす区間を示す電波干渉区間とを含み、前記第４ステップにおいて、前記第１基地局候補の電波干渉区間の少なくとも一部を自基地局の通信可能区間に含む、前記第１ステップで選択した通信チャネルと干渉する通信チャネルに対応付けられた前記第３ステップまでに選択した基地局候補以外の基地局候補を、前記通信電波が干渉する基地局候補として選択するとともに、選択した当該基地局候補における前記通信可能区間に含まれる前記第１基地局候補の電波干渉区間を選択する。
【００１１】
本発明の第４の態様の基地局設置場所決定方法においては、前記第１ステップにおいて、任意の基地局設置候補場所とその基地局設置候補場所に設置する基地局に割り当て可能な通信チャネルとを選択する。
【００１２】
本発明の第５の態様は、前記第１ステップから前記第４ステップを繰り返して選択された全ての基地局候補に基づいて基地局を配置したときに、予め設定された全ての通信対象位置のそれぞれにおいて、他の基地局に割り当てられた通信チャネルと干渉することなく、所定の数の基地局と通信を行うことができる場合の基地局候補の組み合わせを基地局配置案の一つとして決定する基地局設置場所決定方法である。
【００１３】
本発明の第６の態様は、基地局設置候補場所には予めその基地局設置候補場所に基地局を設置した場合の設置コストが設定されていて、前記決定した基地局配置案のそれぞれにおいて選択された全ての基地局設置候補場所について前記設置コストを合計し、さらに複数の基地局配置案の中から最も前記設置コストの合計が小さい場合の基地局配置案を選択する基地局設置場所決定方法である。
【００１４】
本発明の第７の態様は、上述の第１から第６の態様に記載の基地局設置場所決定方法を実行する計算部、を備える基地局設置場所決定装置である。
【００１５】
本発明の第８の態様は、基地局設置場所決定装置のコンピュータを、複数の基地局設置候補場所と、その基地局設置候補場所に設置する基地局に割り当て可能な通信チャネルと、を対応付けた複数の基地局候補であって、それぞれの基地局候補には、その基地局候補が発信する通信電波が届く区間が定められており、それら複数の基地局候補の中から、基地局設置候補場所と、その基地局設置候補場所に設置する基地局に割り当てる通信チャネルとを選択して第１基地局候補に決定する第１ステップを実行する手段、前記第１ステップで選択した基地局設置候補場所とその基地局設置候補場所に設置する基地局に割り当てることができる全ての通信チャネルとの組み合わせを含む基地局候補を選択する第２ステップを実行する手段、前記第１基地局候補が発信する通信電波に対して干渉する前記第１基地局候補以外の基地局候補を選択する第３ステップを実行する手段、前記第３ステップまでに選択した基地局候補を除く前記基地局候補の中から前記第１基地局候補が発信する通信電波が干渉する基地局候補を選択するとともに、その選択した基地局候補について定められた通信電波が届く区間に含まれる前記第１基地局候補が発信する通信電波が届く区間を選択する第４ステップを実行する手段、前記基地局候補の中から前記第１ステップから第３ステップで選択された基地局候補を除いた基地局候補から、さらに第４ステップで選択した区間を除いた基地局候補を新たな基地局候補として前記第１ステップからのステップを繰り返す手段、として機能させるためのプログラムである。
【発明の効果】
【００１６】
本発明によれば、基地局の配置場所を決定することができる。
【図面の簡単な説明】
【００１７】
【図１】本発明に係る実施形態における基地局配置モデルの一例を示す図である。
【図２】本発明に係る実施形態における基地局配置問題の問題設定を説明する第一の図である。
【図３】本発明に係る実施形態における基地局配置問題の問題設定を説明する第二の図である。
【図４】本発明に係る実施形態における基地局配置問題の問題設定を説明する第三の図である。
【図５】本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第一の図である。
【図６】本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第二の図である。
【図７】本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第三の図である。
【図８】本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第四の図である。
【図９】本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第五の図である。
【図１０】本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第六の図である。
【図１１】、本発明に係る実施形態における基地局設置場所決定処理のフローチャートである。
【図１２】、本発明に係る実施形態における基地局設置場所決定処理の結果の一例を示す図である。
【図１３】、本発明に係る実施形態における基地局設置場所決定装置のハードウェア構成の一例を示すブロック図である。
【発明を実施するための形態】
【００１８】
＜実施形態＞
以下、本発明の実施形態による基地局設置場所決定方法を図１〜図１３を参照して説明する。
図１は、本発明に係る実施形態における基地局配置モデルの一例を示す図である。
符号３０は、列車の走行経路の一部を示している。符号２１Ａ〜２６Ａは、走行経路３０の片側に走行経路３０に沿って配置する基地局の設置候補場所を示している。符号２１Ｂ〜２６Ｂは、走行経路３０を隔てて基地局設置候補場所２１Ａ〜２６Ａと対向する側に走行経路３０に沿って配置する基地局の設置候補場所を示している。符号１〜６は、走行経路３０を走行する列車が基地局と無線通信を行う場所を示している。
本実施形態では、基地局設置候補場所と列車が無線通信を行う位置（移動局位置）とが予め与えられており、これらの基地局設置候補場所から適切な設置場所を選んで何処に基地局を設置するか、全体で何基設置するかを決定する問題を考える。例えば図１において、移動局位置１〜６の全てにおいて通信が可能なように、基地局設置候補場所２１Ａ〜２６Ａと２１Ｂ〜２６Ｂの中から適切に基地局を設置する場所を選択することを考える。適切に選択とは、例えば設置コストが最も安くなるように選択する、あるいは、基地局の故障などにより通信できない状態となることを防ぐために、どの移動局位置からも複数の基地局と通信できるように選択するなどである。
【００１９】
以下、図２〜図４を参照して本実施形態の基地局配置問題における問題設定について説明する。
図２は、本発明に係る実施形態における基地局配置問題の問題設定を説明する第一の図である。
図２（ａ）は、基地局設置候補場所２１Ａ〜２６Ａの中から基地局設置候補場所２３Ａを選択し、また、基地局設置候補場所２１Ｂ〜２６Ｂの中から基地局設置候補場所２５Ｂを選択した場合を示している。このとき選択された基地局設置候補場所２３Ａ及び２５Ｂに設置する基地局には、それぞれ１つずつ通信チャネルを割り当てるものとする。割り当てる通信チャネルは、後に述べるように互いに電波干渉が起こらないように選択する。電波干渉が起こらなければ同じ通信チャネルを割り当てても、異なる通信チャネルを割り当ててもよい。以下では、ある基地局候補場所の基地局に通信チャネルを割り当てることをある基地局候補場所に通信チャネルを割り当てると表現することがある。
図２（ａ）の場合、基地局設置候補場所２３Ａには通信チャネル１（ＣＨ１）を、基地局設置候補場所２５ＢにはＣＨ３を割り当てている。このとき、各基地局設置候補場所には、１つの通信チャネルしか割り当てることができないものとする。また、各基地局設置候補場所に割り当てることができる通信チャネルは、予め決まっているものとする。例えば、各基地局設置候補場所に割り当てられる通信チャネルはＣＨ１、ＣＨ２、ＣＨ３、ＣＨ４、ＣＨ５のうちの何れか１つであるという条件が定められているものとする。
【００２０】
また、基地局設置候補場所ごとに基地局の設置コストが予め設定されているものとする。例えば、各基地局と駅とが通信回線で接続されており、基地局設置候補場所が駅の近くであれば、通信回線用ケーブルの敷設コストが安く、その分安い設置コストが設定され、基地局設置候補場所が駅から遠ければ、ケーブルの敷設にかかるコストが高くなる分、その基地局設置候補場所には高い設置コストが設定される。図２（ａ）の例では、基地局設置候補場所２３Ａに基地局を設置すると１０００万円のコストがかかり、基地局設置候補場所２５Ｂに基地局を設置すると１３００万円のコストがかかり、これら両方に設置すると合計２３００万円のコストがかかることを示している。なお、この基地局の設置コストは、その基地局設置候補場所にどの通信チャネルが割り当てられるかに関わらず同額であるとする。
【００２１】
図２（ｂ）は、別の基地局設置候補場所が選択された例を示している。図２（ｂ）の場合、基地局設置候補場所２３Ａが選択され、そこにＣＨ３が割り当てられており、設置コストは１０００万円である。また、基地局設置候補場所２１Ｂが選択され、そこにＣＨ２が割り当てられており、設置コストは１５００万円である。また、基地局設置候補場所２６Ｂが選択され、そこにＣＨ４が割り当てられており、設置コストは１２００万円である。図２（ｂ）のように基地局設置候補場所を選択すると、合計で３７００万円必要になる。このように、本実施形態では基地局設置候補場所を選択するとそこに基地局を設置するための設置コストが決定する。
【００２２】
図３は、本発明に係る実施形態における基地局配置問題の問題設定を説明する第二の図である。
図３（ａ）は、基地局設置候補場所２１ＡにＣＨ２が割り当てられており、同様に基地局設置候補場所２４ＡにはＣＨ１が、基地局設置候補場所２５ＢにはＣＨ３が割り当てられている場合を示している。また、列車が移動局位置３を通過するときには、列車に設けられた無線通信装置は、基地局設置候補場所２４Ａの基地局と通信し、この基地局から送出された信号を移動局位置３に位置する列車の無線通信装置が受信する際のフレームロス率は、０．１２％であることを示している。
同様に、図３（ｂ）は、基地局設置候補場所２２ＡにＣＨ３、基地局設置候補場所２４ＡにＣＨ１、基地局設置候補場所２６ＡにＣＨ４、基地局設置候補場所２１ＢにＣＨ１、基地局設置候補場所２５ＢにＣＨ２が割り当てられている場合を示している。また、基地局設置候補場所２４Ａの基地局から送出された信号を移動局位置３に位置する列車の無線通信装置が受信する際のフレームロス率は、０．０８％であることを示している。なお、以下では、ある基地局設置候補場所に設置された基地局とある移動局位置に位置する列車の無線通信装置との通信を基地局設置候補場所の基地局と移動局位置との通信のように表現することがある。
【００２３】
図３（ａ）、図３（ｂ）が示すように、同じＣＨ１が割り当てられた基地局設置候補場所２４Ａの基地局から送出された信号を移動局位置３に位置する列車の無線通信装置が受信する場合であっても、基地局設置候補場所２４Ａの周囲の設置環境によって基地局設置候補場所２４Ａの基地局と移動局位置３との間の通信におけるフレームロス率は変化する。周囲の設置環境とは、基地局設置候補場所２４Ａの周辺に配置された基地局の設置場所とそれらの基地局に割り当てられた通信チャネルのことである。
列車制御システムでは、列車を安定して走行させることができるよう十分な通信品質を確保する必要がある。そのため、周囲の設置環境も考慮して基地局設置候補場所の選択を行わなければならない。本実施形態では、許容できるフレームロス率の閾値を定め、フレームロス率がその閾値以下となるように基地局の設置場所及び割り当てる通信チャネルを決定する。なお、本実施形態では、周辺の基地局配置及び通信チャネル割り当ての状況から、どの基地局設置候補場所にどの通信チャネルを割り当てれば、その基地局から送出された信号のフレームロス率を閾値以下に抑えることができるかについての情報は、シミュレーション等により明らかとなっており、その情報は予め与えられるものとする。
【００２４】
図４は、本発明に係る実施形態における基地局配置問題の問題設定を説明する第三の図である。
図４（ａ）は、基地局設置候補場所２１ＡにＣＨ１が、基地局設置候補場所２２ＡにＣＨ４が、基地局設置候補場所２５ＡにＣＨ２が、基地局設置候補場所２６ＡにＣＨ４が、割り当てられている場合を示している。また、符号４１Ａ〜４１Ｄは、各基地局設置候補場所に設置した基地局と許容できるフレームロス率の閾値以下で通信可能な範囲を示している。ＣＨ１が割り当てられた基地局設置候補場所２１Ａの基地局を基地局（２１Ａ、ＣＨ１）と表記することにすると、例えば移動局位置１では、基地局（２１Ａ、ＣＨ１）、基地局（２２Ａ、ＣＨ４）と通信可能である。同様に、移動局位置２、移動局位置３では、基地局（２１Ａ、ＣＨ１）、基地局（２２Ａ、ＣＨ４）と通信可能である。また、移動局位置４では、基地局（２２Ａ、ＣＨ４）、基地局（２５Ａ、ＣＨ２）と通信可能である。また、移動局位置５、移動局位置６では、基地局（２５Ａ、ＣＨ２）、基地局（２６Ａ、ＣＨ４）と通信可能である。図４（ａ）の例では、全ての移動局位置１〜６においてそれぞれ２つの基地局と通信が可能である。
【００２５】
一方、図４（ｂ）の場合、移動局位置１、２、３では、基地局（２１Ａ、ＣＨ１）、基地局（２２Ａ、ＣＨ３）と通信可能である。また、移動局位置４では、基地局（２２Ａ、ＣＨ３）、基地局（２５Ａ、ＣＨ２）と通信可能である。しかし、移動局位置５、６では、基地局（２５Ａ、ＣＨ２）とのみ通信可能である。列車制御システムでは、安定上の観点からどこかの基地局が故障しても、全ての移動局位置から常に基地局との通信ができるようにすることが重要である。そこで本実施形態では、全ての移動局位置からそれぞれ複数（例えば２つ）の基地局と通信ができるように基地局を配置することが可能であるようにする。
【００２６】
以上が、本実施形態の基地局配置問題における問題設定である。本実施形態では、これらの条件を満たす基地局配置及び通信チャネル割り当ての組み合わせのうち設置コストが最小となる組み合わせを求めることを目的とする。
【００２７】
次に図５〜図１０を用いて上記の組み合わせを決定する方法について説明する。なお、以下で説明するアルゴリズムは、基地局設置場所決定装置が備えるコンピュータが、当該アルゴリズムを記述したプログラムを実行することで上記の組み合わせを決定するものとする。なお、基地局設置場所決定装置に備わるＣＰＵ（Central Processing Unit）が当該プログラムを実行することにより備わる機能を計算部と称する。
図５は、本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第一の図である。
以下では、移動局位置１〜１０に位置する列車の無線通信装置が通信する基地局を基地局設置候補場所２１Ａ〜２５Ａから選択してその配置を決定する場合を例に、その配置の決定方法の解法アルゴリズムの説明を行う。また、各基地局設置候補場所に割り当てられる通信チャネルはＣＨ１、ＣＨ２、ＣＨ３、ＣＨ４、ＣＨ５のうちの何れか１つであるとする。また、ＣＨ１と干渉する通信チャネルはＣＨ１、ＣＨ２であり、ＣＨ２と干渉する通信チャネルはＣＨ１、ＣＨ２、ＣＨ３であり、ＣＨ３と干渉する通信チャネルはＣＨ２、ＣＨ３、ＣＨ４であり、ＣＨ４と干渉する通信チャネルはＣＨ３、ＣＨ４、ＣＨ５であり、ＣＨ５と干渉する通信チャネルはＣＨ４、ＣＨ５であるものとする。
【００２８】
符号３１Ａは、基地局設置候補場所２１Ａにある通信チャネルを割り当てたときにフレームロス率が閾値ｅ以下で通信可能な区間（通信可能区間）を示している。この通信可能区間は、列車が各移動局位置に存在するときに列車が備える無線通信装置と当該基地局との間で、列車制御に利用できる品質の通信が可能な区間である。また、符号３１Ｂは、同じく基地局設置候補場所２１Ａにある通信チャネルを割り当てたときに、フレームロス率は閾値ｅを超えてしまうが電波が到達する区間（電波干渉区間）を示している。この電波干渉区間は、列車制御に使用できる品質の通信を行うことはできないが他の基地局からの電波に干渉する可能性がある区間を示している。同様に、符号３２Ａは、基地局設置候補場所２２Ａにある通信チャネルを割り当てたときの通信可能区間を示し、符号３２Ｂは、そのときの電波干渉区間を示している。符号３３Ａは、基地局設置候補場所２３Ａにある通信チャネルを割り当てたときの通信可能区間を示し、符号３３Ｂは、そのときの電波干渉区間を示している。符号３４Ａは、基地局設置候補場所２４Ａにある通信チャネルを割り当てたときの通信可能区間を示し、符号３４Ｂは、そのときの電波干渉区間を示している。符号３５Ａは、基地局設置候補場所２５Ａにある通信チャネルを割り当てたときの通信可能区間を示し、符号３５Ｂは、そのときの電波干渉区間を示している。
【００２９】
図６は、本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第二の図である。
図６は、複数の基地局設置候補場所と、その基地局設置候補場所に割り当て可能な通信チャネルとを対応付けた基地局候補と、それぞれの基地局候補について定められた通信電波が届く区間とを示す図である。図６の表の行は、基地局設置候補場所を示し、列は割り当て可能な通信チャネルを示している。また、各欄（セル）の上段に記載されている数値は通信可能区間に含まれる移動局位置であり、下段に記載されている数値は電波干渉区間に含まれる移動局位置である。例えば、１行目１列目は、基地局設置候補場所２１ＡにＣＨ１を割り当てた場合、フレームロス率が閾値ｅ以下で通信可能な移動局位置は１、２、３、４であり、フレームロス率が閾値ｅを超えてしまうが電波が到達する移動局位置は５であることを示している。基地局設置候補場所２１ＡにＣＨ１を割り当てても移動局６、７、８、９、１０には電波は到達しない。
また、０列目の基地局設置候補場所の下段のかっこ中に記載された数字は設置コストである。例えば、基地局設置候補場所２１Ａの設置コストは１０百万円、基地局設置候補場所２２Ａの設置コストであれば８百万円であることを意味する。
以上が基地局配置問題の解法アルゴリズムの前提条件として与えられる情報である。これらの情報は、基地局設置場所決定装置に予め記憶されているか解法アルゴリズムを記述したプログラムの実行時に外部から与えられるものとする。
【００３０】
次にアルゴリズムの概略について図７〜図１０を用いて説明する。
図７は、本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第三の図である。
図７を用いて、第１及び第２ステップを説明する。まず、図７（ａ）が示す基地局設置候補場所及び通信チャネルの全ての組み合わせの中から計算部がランダムにある１つの組み合わせを選択する。一例として基地局設置候補場所２２Ａ及びＣＨ３の組み合わせからなる基地局候補が選択されたとする。なお図中、選択された基地局（２２Ａ，ＣＨ３）は、太枠で囲んで表記し、他の基地局と電波が干渉するなどの理由で基地局設置候補場所から除外された基地局（ｉ，ｋ）についてはセルを網掛けなどして表記するものとする。続いて、１つの基地局には１つの通信チャネルしか割り当てることができないという問題設定なので基地局候補のうち、基地局（２２Ａ、ＣＨ１）、基地局（２２Ａ、ＣＨ２）、基地局（２２Ａ、ＣＨ４）、基地局（２２Ａ、ＣＨ５）は、除外対象に設定する。図７（ｂ）は、計算部が基地局（２２Ａ、ＣＨ３）を選択し（第１ステップ）、ＣＨ３以外の通信チャネルについては除外対象に設定した（第２ステップ）ことを示す図である。
【００３１】
図８は、本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第四の図である。
図８（ａ）を用いて、第３ステップを説明する。基地局（２２Ａ、ＣＨ３）の通信可能区間は、移動局位置１、２、３、４、５である。そこで、この基地局（２２Ａ、ＣＨ３）が発信する通信電波に干渉する通信電波を発信する基地局（ｉ，ｋ）を、基地局の候補から除外する。そのような除外対象基地局（ｉ，ｋ）が設置されると、基地局（２２Ａ、ＣＨ３）の通信電波が干渉を受け通信品質が低下するためである。この場合、除外対象基地局（ｉ，ｋ）は、その基地局自身の通信可能区間または電波干渉区間に、１、２、３、４、５のうちの少なくとも１つを有し、且つ、ＣＨ３と干渉する通信チャネルが割り当てられている基地局（ｉ，ｋ）である。そのような、セルの上段または下段に１、２、３、４、５の何れか一つが記載され、ＣＨ３と干渉するＣＨ２、ＣＨ３、ＣＨ４が割り当てられた基地局候補を列挙すると、基地局（２１Ａ，ＣＨ２）、基地局（２１Ａ，ＣＨ３）、基地局（２１Ａ，ＣＨ４）、基地局（２２Ａ，ＣＨ２）、基地局（２２Ａ，ＣＨ３）、基地局（２２Ａ，ＣＨ４）、基地局（２３Ａ，ＣＨ２）、基地局（２３Ａ，ＣＨ３）、基地局（２３Ａ，ＣＨ４）、基地局（２４Ａ，ＣＨ２）、基地局（２４Ａ，ＣＨ３）、基地局（２４Ａ，ＣＨ４）となる。計算部は、これらを、選択不可に設定する。
【００３２】
図８（ｂ）を用いて、第４ステップを説明する。この第４ステップでは、基地局（２２Ａ、ＣＨ３）の電波干渉区間に含まれる移動局位置を、その基地局自身の通信可能区間に含む基地局のうち、ＣＨ３と干渉する通信チャネルが割り当てられた基地局（ｉ，ｋ）を選択し、その基地局（ｉ，ｋ）の通信可能区間から基地局（２２Ａ、ＣＨ３）の電波干渉区間に含まれる移動局位置（「６」）を選択し、これを除外対象とする。これは、ＣＨ３と干渉するＣＨ２、ＣＨ３、ＣＨ４が割り当てられ、基地局（２２Ａ、ＣＨ３）の電波干渉区間を自基地局の通信可能区間に含む基地局（ｉ，ｋ）を選択しても、選択したその基地局（ｉ，ｋ）からの通信電波が、基地局（２２Ａ、ＣＨ３）の電波干渉区間においては、基地局（２２Ａ、ＣＨ３）から発信される通信電波に干渉されて通信品質が劣化してしまうからである。上述の第３ステップは、選択した基地局（２２Ａ、ＣＨ３）の通信電波に干渉する基地局（ｉ、ｋ）を除外するのが目的だったのに対し、この第４ステップは、選択した基地局（２２Ａ、ＣＨ３）の電波が到達してしまうことによる他の基地局（ｉ、ｋ）の通信電波への干渉を防ぐのが目的である。
第３、第４ステップが示すように本実施形態では、周辺基地局の設置状況に応じた電波干渉を考慮して、互いに干渉が起きないように基地局配置を決定する。
符号４０Ａ〜４０Ｃは、第４ステップによって除外された移動局位置である。
【００３３】
次のステップでは、第１〜第３ステップで除外対象に選択した複数の基地局（ｉ、ｋ）を除いた基地局候補を選択し、新たな基地局候補に設定する。図８（ｂ）では、基地局（２１Ａ、ＣＨ１）、基地局（２１Ａ、ＣＨ５）、基地局（２３Ａ、ＣＨ１）、基地局（２３Ａ、ＣＨ５）、基地局（２４Ａ、ＣＨ１）、基地局（２４Ａ、ＣＨ５）、基地局（２５Ａ、ＣＨ１）、基地局（２５Ａ、ＣＨ２）、基地局（２５Ａ、ＣＨ３）、基地局（２５Ａ、ＣＨ４）、基地局（２５Ａ、ＣＨ５）が新たな基地局候補である。ただし、第４ステップで選択した基地局（２５Ａ、ＣＨ２）、基地局（２５Ａ、ＣＨ３）、基地局（２５Ａ、ＣＨ４）については、通信可能区間に含まれる移動局位置から基地局（２２Ａ，ＣＨ３）の電波干渉区間に含まれる移動局位置「６」が除外されている。
【００３４】
図９は、本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第五の図である。
図９（ａ）は、図８（ｂ）における第４ステップの後に設定された新たな基地局候補について再び、第１〜第４ステップを行った結果を示している。まず、基地局（２１Ａ、ＣＨ１）は、計算部がランダムに選択した２番目の基地局候補である。基地局（２１Ａ、ＣＨ５）は、１つの基地局には１つの通信チャネルしか割り当てられないために選択された基地局（ｉ、ｋ）である。以上が第１及び第２ステップである。基地局（２３Ａ、ＣＨ１）と基地局（２４Ａ、ＣＨ１）は、第３ステップにより新たに選択された基地局（２１Ａ、ＣＨ１）の通信可能区間（１，２，３，４）の何れかを自基地局の通信可能区間または電波干渉区間に持つ基地局（ｉ、ｋ）である。第４ステップによって選択される基地局（ｉ、ｋ）は存在しない。第４ステップの後、基地局設置場所決定装置は、基地局（２５Ａ、ＣＨ１）、基地局（２３Ａ、ＣＨ５）、基地局（２４Ａ、ＣＨ５）、基地局（２５Ａ、ＣＨ５）、通信可能区間から「６」が除外された基地局（２５Ａ、ＣＨ２）及び基地局（２５Ａ、ＣＨ３）及び基地局（２５Ａ、ＣＨ４）、を新たな基地局候補に設定する。
【００３５】
図９（ｂ）は、図９（ａ）で設定された新たな基地局候補について再び、第１〜第４ステップを行った結果を示している。まず、基地局（２４Ａ、ＣＨ５）は、計算部がランダムに選択した３番目の基地局候補である。基地局（２３Ａ、ＣＨ５）、基地局（２５Ａ、ＣＨ４）、基地局（２５Ａ、ＣＨ５）は、第３ステップによって選択不可に設定された基地局（ｉ、ｋ）である。
残った基地局候補に対してさらに第１ステップからの処理を繰り返す。このとき、基地局（２５Ａ、ＣＨ１）は、計算部がランダムに選択した４番目の基地局候補である。ここで、全ての移動局位置から２つの基地局と通信可能となったので処理を終了する。
【００３６】
図１０は、本発明に係る実施形態における基地局配置問題の解法アルゴリズムの概略を説明する第六の図である。
図１０は、移動局位置１〜１０のそれぞれからは、２つの基地局と通信可能であることを示している。例えば、移動局位置１は、基地局（２１Ａ、ＣＨ１）、基地局（２２Ａ、ＣＨ３）と通信可能である。また、移動局位置５は、基地局（２２Ａ、ＣＨ３）、基地局（２４Ａ、ＣＨ５）と通信可能である。他の移動局位置についても同様である。
また、このときの設置コストは、１０百万＋８百万＋１４百万＋１８百万＝５０百万円であることが分かる。
【００３７】
次にアルゴリズムについて詳細に説明する。
＜問題設定＞
基地局設置場所候補と移動局位置は予め与えられている。また、各基地局に割り当てることができる通信チャネルは決まっており、その中から１つのみを割り当てるものとする。また、フレームロス率は、周辺の基地局設置状況によって変動する。各移動局位置では少なくともｕ基の基地局と通信可能でなければならない。ここでｕは、入力パラメータである。
【００３８】
＜定式化＞
基地局設置候補場所の集合をＭ＝｛１，２，・・・，｜Ｍ｜｝、
移動局位置の集合をＮ＝｛１，２，・・・，｜Ｎ｜｝、
各基地局で利用可能な通信チャネルの集合をＰ＝｛１，２，・・・，｜Ｐ｜｝、とする。
基地局設置候補場所ｉ∈Ｍに基地局を設置するときの設置コストをｃｉ、
各移動局位置におけるフレームロス率の閾値をｅとする。
基地局設置候補場所ｉ∈Ｍに設置する通信チャネルｋ∈Ｐの基地局を基地局（ｉ，ｋ）、
基地局（ｉ，ｋ）と移動局位置ｊ∈Ｎの通信を通信（ｉ，ｊ，ｋ）とし，
基地局（ｉ，ｋ）から他の基地局からの電波干渉による影響が無ければフレームロス率ｅ以下で通信可能な移動局位置の集合をＮｉｋとする。
ノード集合Ｖ＝Ｍ∪Ｎ、アーク集合Ａ＝｛（ｉ，ｊ，ｋ）∈Ｍ×Ｎ×Ｐ｜ｊ∈Ｎｉｋ，ｉ∈Ｍ，ｋ∈Ｐ｝から構成される有向グラフをＧ＝（Ｖ、Ａ）とする。
通信（ｉ，ｊ，ｋ）は、基地局（ｉ１，ｋ１）、基地局（ｉ２，ｋ２）・・・、基地局（ｉｒ，ｋｒ）の中の何れか１基でも設置されてしまうとフレームロス率が閾値ｅを超えてしまうとし、このとき、これら基地局の集合｛基地局（ｉ１，ｋ１）、基地局（ｉ２，ｋ２）・・・、基地局（ｉｒ，ｋｒ）｝をＢｉｊｋで表す。
通信（ｉ，ｊ，ｋ）に変数ｘｉｊｋ、基地局（ｉ，ｋ）に変数ｙｉｋを付与して次のように定義する。
【００３９】
【数１】
2016039404.tif 000003
【００４０】
【数２】
2016039404.tif 000004
【００４１】
各移動局位置において許容フレームロス率以下で通信が可能となる基地局配置のうち，設置費用が最小となる基地局配置を求める問題は，次のような０−１整数計画問題に定式化される。ただし，ｕは正整数とする。
Ｍｉｎｉｍｉｚｅ
【００４２】
【数３】
2016039404.tif 000005
【００４３】
Ｓｕｂｊｅｃｔ  ｔｏ
【００４４】
【数４】
2016039404.tif 000006
【００４５】
ｘｉｊｋ  ≦  ｙｉｋ  ，（ｉ，ｊ，ｋ）∈  Ａ            ・・・・（３）
【００４６】
【数５】
2016039404.tif 000007
【００４７】
ｘｉｊｋ  ＋  ｙｉ＊ｋ＊  ≦  １  ，（ｉ＊，ｊ＊）∈Ｂｉｊｋ  ，
（ｉ，ｊ，ｋ）∈  Ａ        ・・・・（５）
【００４８】
ｘｉｊｋ  ∈  ｛０，１｝、（ｉ，ｊ，ｋ）∈  Ａ            ・・・・（６）
ｙｉｋ  ∈  ｛０，１｝、ｉ  ∈  Ｍ  、ｋ  ∈  Ｐ          ・・・・（７）
【００４９】
上記の定式化において，式（１）は目的関数であり、基地局設置費用の最小化が目的であることを示している。また，式（２）から式（５）は制約条件である。式（２）は、各移動局位置はｕ基以上の基地局と通信できることを保証する条件である。式（３）は、必要な基地局を設置することを保証する条件である。式（４）は、各基地局には２つ以上の通信チャネルが割り当てられないことを保証する条件である。式（５）は、電波干渉によりフレームロス率が閾値ｅを上回る通信は使用しないことを保証する条件である。なお，式（６）と式（７）は、決定変数の０−１条件である。
【００５０】
次にこの問題に対する解法アルゴリズムについて説明する。
ここで基地局（ｉ，ｋ）から送出された信号のフレームロス率が、他の基地局からの電波干渉による影響が無くても閾値ｅを超えてしまう移動局位置の集合を
【００５１】
【数６】
2016039404.tif 000008
【００５２】
また、通信チャネルｋと相互に電波が干渉する可能性のある通信チャネルの集合をＰｋとする。また、Ｗｉｋ＝Ｎｉｋ∪Ｎ−ｉｋとする。なお、Ｎｉｋは、例えば図７〜９において各セルの上段の値の集合であり、Ｎ−ｉｋは下段の値の集合である。
【００５３】
本アルゴリズムにおける入力値は、Ｍ、Ｎ、Ｐ、ｃｉ、ｕ、Ｎｉｋ、Ｎ−ｉｋ、Ｐｋ、Ｂｉｊｋである。出力値は、
【００５４】
【数７】
2016039404.tif 000009
【００５５】
【数８】
2016039404.tif 000010
【００５６】
【数９】
2016039404.tif 000011
【００５７】
である。
【００５８】
ステップ０：Ａ＾＝φ、Ｂ＾＝φ、Ｚ＾＝∞  とする。なお、φは、空集合である。
ステップ１：
【００５９】
【数１０】
2016039404.tif 000012
【００６０】
【数１１】
2016039404.tif 000013
【００６１】
【数１２】
2016039404.tif 000014
【００６２】
Ｂ＝Ｍ×Ｐとする。また、ｎｊ＝０、ｊ∈  Ｎ  とする。
以上は、初期化である。
【００６３】
ステップ２：任意の（ｉ＊，ｋ＊）∈Ｂを求めて次のように更新する。
Ｂ−：＝  Ｂ−∪｛（ｉ＊，ｋ＊）｝
Ｚ−：＝  Ｚ−  ＋  ｃｉ＊
このステップでは、設置可能な基地局の中から任意に１つの基地局（ｉ＊，ｋ＊）を選択し、その基地局を基地局集合Ｂ−に加える。
【００６４】
ステップ３：以下の式でＡ＊を求めて、Ａ−：＝Ａ−∪Ａ＊  と更新する。
Ａ＊＝｛（ｉ，ｊ，ｋ）∈Ａ｜ｉ＝ｉ＊，ｊ∈Ｎｉ＊ｋ＊，ｋ＝ｋ＊｝
このステップでは、基地局（ｉ＊，ｋ＊）とフレームロス率が閾値ｅ以下となる通信を求めて，それらをＡ−に加える。
【００６５】
ステップ４：ｎｊを次のように更新する。
ｎｊ：＝  ｎｊ  ＋  １  、  ｊ  ∈  Ｎｉ＊ｋ＊
また、ｎｊ：＝  ｕ  、ｊ  ∈  Ｎ  ならばステップ９へ進む。
このステップでは、各移動局位置において通信可能な基地局数を確認する。その結果、全ての移動局位置で通信可能な基地局数がｕ基以上となった場合には、問題の可能解が得られたことになり、その場合、ステップ９へ進む。
【００６６】
ステップ５：次のＢ´、Ｂ´´、Ｂ´´´を求める。
Ｂ´      ＝  ｛（ｉ，ｋ）∈Ｂ  ｜  ｉ＝ｉ＊，ｋ∈Ｐ  ｝
Ｂ´´    ＝  ｛（ｉ，ｋ）∈Ｂ  ｜  ｋ∈Ｐｋ＊，Ｗｉｋ∩Ｎｉ＊ｋ＊≠φ｝
Ｂ´´´  ＝  ｛（ｉ，ｋ）∈Ｂ  ｜  ｋ∈Ｐｋ＊，
Ｎｉｋ∩Ｎ−ｉ＊ｋ＊≠φ｝
ステップ２で基地局（ｉ＊，ｋ＊）が選択された場合、基地局設置候補場所ｉ＊には他の基地局を設置することはできなくなる。このステップでは、そのような基地局集合Ｂ´を求める（第２ステップ）。また、基地局（ｉ＊，ｋ＊）が設置された場合、Ｎｉ＊ｋ＊に含まれる各移動局位置と基地局（ｉ＊，ｋ＊）間の通信品質を劣化させないように新たに設置する基地局を選択しなければならない。つまり，通信チャネルｋ＊と電波干渉が発生する可能性のある通信チャネルが割り当てられた基地局からの信号が、Ｎｉ＊ｋ＊に含まれる各移動局位置まで到達しないように新たな基地局を設置しなければならない。このステップでは、そのような電波干渉を引き起こす可能性のある基地局集合Ｂ´´を求める（第３ステップ）。また、基地局（ｉ＊，ｋ＊）から送出された信号は、フレームロス率が閾値ｅを超えてしまうもののＮ−ｉ＊ｋ＊に含まれる各移動局位置で受信することができる。そこで、このステップでは、そのような各移動局位置を含む基地局の集合Ｂ´´´を求めている。
【００６７】
ステップ６：ＢとＮｉｋを次のように更新する。
Ｂ      ：＝  Ｂ−（Ｂ´∪Ｂ´´）
Ｎｉｋ  ：＝  Ｎｉｋ  −  Ｎ−ｉ＊ｋ＊  ，（ｉ，ｋ）∈Ｂ´´´
このステップでは、設置可能な基地局集合であるＢからＢ´を除外している。また、このステップでは、設置可能な基地局集合であるＢからさらにＢ´´を除外している。また、Ｂ´´´については、基地局（ｉ＊，ｋ＊）から送出された信号と電波干渉させないようにするため、Ｎｉｋ，（ｉ，ｋ）∈Ｂ´´´からＮ−ｉ＊ｋ＊を選択し（第４ステップ）、削除する。
【００６８】
ステップ７：Ｎｉｋを更に次のように更新する。
Ｎｉｋ  ：＝  Ｎｉｋ  −  ｛ｊ∈Ｎ｜ｎｊ＝ｕ｝，（ｉ，ｋ）∈Ｂ
このステップでは、基地局（ｉ＊，ｋ＊）の設置に伴うＮｉｋ，（ｉ，ｋ）∈Ｂの更新をしている。
【００６９】
ステップ８：Ｂを更に次のように更新してステップ２からの処理を繰り返す。また、このときＢ≠φならばステップ１０へ進む。
Ｂ  ：＝  Ｂ−｛（ｉ，ｋ）∈Ｂ｜Ｎｉｋ＝φ｝
このステップでは、ステップ６においてＢを更新した結果、Ｎｉｋ＝φとなった基地局を以降の基地局選択候補から除外している。
【００７０】
ステップ９：Ｚ＾＞Ｚ−ならば
Ａ＾：＝Ａ−、Ｂ＾：＝Ｂ−、Ｚ＾＝Ｚ−と更新する。
Ｚ＾は、これまでの基地局配置案における最小設置コストである。今回求めた基地局配置案における設置コストがこれを下回れば暫定解を更新する。
【００７１】
ステップ１０：終了条件を満たしていなければステップ１へ戻る。そうでなければステップ１１へ進む。終了条件とは、処理の制限時間やループ回数の上限値などのことである。この終了条件は予め与えられているものとする。
ステップ１１：Ａ＾、Ｂ＾、Ｚ＾を出力して終了する。
【００７２】
このアルゴリズムでは常に可能解が求まる保証はない。例えば、アルゴリズムの終了時にステップ４でｎｊ：＝  ｕ  、ｊ  ∈  Ｎ  となる基地局配置案を１つも求めることができなかった場合、式（２）の制約条件を満たした解が得られなかったことになる。一方ステップ４で条件を満たす基地局配置案が1つでも得られた場合は、可能解が得られたことになる。このとき、定式化におけるｘｉｊｋとｙｉｋは、アルゴリズムが出力するＡ＾とＢ＾より次式によって定まる。
【００７３】
【数１３】
2016039404.tif 000015
【００７４】
【数１４】
2016039404.tif 000016
【００７５】
また、目的関数である式（１）の値がＺ＾である。
【００７６】
本実施形態によれば、周辺の通信チャネル使用状況による通信環境の変化を考慮した上で基地局の設置数、配置場所、割り当てる通信チャネルを同時に決定することができる。
【００７７】
図１１は、本発明に係る実施形態における基地局設置場所決定処理のフローチャートである。
図１１を用いて本実施形態に係る基地局設置場所決定装置が、上述したアルゴリズムを記述したプログラムを実行する処理について説明する。
前提として、図６で例示したような基地局（ｉ、ｋ）とその通信可能区間及び電波干渉区間を設定したデータテーブルが予め基地局設置場所決定装置が備える記憶部に記憶されているものとする。このデータテーブルを基地局候補集合テーブルと称する。また、基地局候補集合テーブルの各セルのデータには、図６で例示した通信可能区間の移動局位置と電波干渉区間の移動局位置の情報の他に、その基地局を選択したかどうかを示す選択フラグが備えられており、初期値として非選択を表す「０」が設定されているものとする。また、基地局候補集合テーブルの各行ごとに設置コストの情報が格納されているものとする。なお、説明には、例として図６を用いる。つまり、通信チャネルは、ＣＨ１〜５、基地局設置候補場所は２１Ａ〜２５Ａ、移動局位置は、１〜１０であるとする。
まず、計算部が、所定の方法を用いて基地局候補集合テーブルからランダムに基地局（ｉ＊，ｋ＊）を選択する（ステップＳ１１）。例えば、行と列についてそれぞれ１〜５の範囲で乱数を発生させ、その乱数と紐付けられた基地局（ｉ，ｋ）を選択してもよい。計算部は、選択した基地局（ｉ＊，ｋ＊）の選択フラグに、その基地局（ｉ＊，ｋ＊）が設置候補として選択されたことを意味する「１」を設定する。
次に計算部は、選択した基地局（ｉ＊，ｋ＊）の行の基地局候補データを全て選択し、それぞれについて選択フラグに、選択除外対象を意味する「２」を設定する。つまり、それら基地局（ｉ，ｋ）を基地局の設置ができない対象として選択する（ステップＳ１２）。例えば、ステップＳ１１で基地局（２，３）が選択された場合、計算部は、基地局（２，ｋ）（ｋ＝１〜５）の選択フラグを２にする。これは、選択された基地局設置場所（ｉ＝２）では、ＣＨ３のみが使用可能で他の通信チャネルは使用できないことに対応している。
【００７８】
次に計算部は、基地局（ｉ＊，ｋ＊）の通信可能区間の移動局位置を、基地局候補集合テーブルから読出し、読み出した移動局位置を自基地局の通信可能区間または電波干渉区間に有する基地局（ｉ，ｋ）を検索し、見つかった基地局（ｉ，ｋ）のそれぞれに対して選択フラグに「２」を設定する。つまり、計算部は、基地局（ｉ＊，ｋ＊）の通信可能区間に干渉する他の基地局候補を選択する（ステップＳ１３）。
次に計算部は、基地局（ｉ＊，ｋ＊）の電波干渉区間の移動局位置を、基地局候補集合テーブルから読出し、読み出した移動局位置を自基地局の通信可能区間に有する基地局（ｉ，ｋ）を選択する（ステップＳ１４）。
次に計算部は、ステップＳ１２〜ステップＳ１３で選択した基地局（ｉ，ｋ）の選択フラグを更新する。また、計算部は、ステップＳ１４で選択した基地局（ｉ，ｋ）のそれぞれに対して通信可能区間から基地局（ｉ＊，ｋ＊）の電波干渉区間の移動局位置を削除して通信可能区間を更新する（ステップＳ１５）。ステップＳ１５によって更新された複数の基地局設置候補場所と、その基地局設置候補場所に割り当て可能な通信チャネルと、通信可能区間及び電波干渉区間とを対応付けた基地局候補集合テーブルが新たな基地局候補である。
【００７９】
次に計算部は、終了判定を行う（ステップＳ１６）。計算部は、選択フラグに「１」が設定されたセルの通信可能区間に含まれる移動局位置を確認し、全ての移動局位置がｕ（例えば２）基の基地局（ｉ，ｋ）の通信可能区間に含まれる場合、終了と判定する。または、計算部は、基地局候補集合テーブルの全てのセルの選択フラグを確認し、その値が「１」または「２」となった場合に終了と判定する。全ての移動局位置が所定の数の基地局（ｉ，ｋ）の通信可能区間に含まれる場合、求める１つの基地局集合が得られたことになる。そうではない場合、今回の一連の処理では解が得られなかったことになる。本実施形態では、各基地局設置場所候補と通信チャネルの組み合わせをランダムに選択する。これは、規則性を与えて基地局設置候補場所からの選択を行うことにより類似した解ばかりが得られ、解の多様性が失われることを防ぐためである。その為、本実施形態では必ずしも解が得られない場合が出てくる。しかし、繰り返し計算を行うことで、数多い配置パターンの中から、より適切な基地局配置を行うことが可能となる。
判定結果が終了の場合（ステップＳ１６：Ｙｅｓ）、計算部は、選択フラグに「１」が設定された基地局（ｉ，ｋ）の設置コストを基地局候補集合テーブルから読み出して合計する（ステップＳ１７）。そして計算部は、選択フラグに「１」が設定された基地局（ｉ，ｋ）の情報と合計した設置コストを出力し処理フローを終了する。判定結果が終了ではない場合（ステップＳ１６：Ｎｏ）、計算部は、ステップＳ１１からの処理を繰り返す。
【００８０】
上述のステップＳ１１〜Ｓ１７により、１回の基地局設置候補場所決定処理が完了し、１つの基地局配置案が得られる。計算部は、得られた移動局位置と基地局設置候補場所及び通信チャネルの組み合わせ（Ａ＾：通信集合）と基地局設置候補場所及び通信チャネル（Ｂ＾：基地局集合）と設置コスト（Ｚ＾）とを記憶部に格納する。
基地局設置場所決定装置は、上述のステップＳ１１〜Ｓ１７を例えば所定の回数繰り返し、最も設置コストが安くなる場合の通信集合と基地局集合と設置コストを選択し、出力する。
【００８１】
図１２は、本発明に係る実施形態における基地局設置場所決定処理の結果の一例を示す図である。
図１２の表は、ある条件下で上述のステップＳ１１〜Ｓ１７を１０００回実行したときの結果（同一の問題サイズで異なるパラメータ設定のインスタンスを５題解いた結果、可能解が得られたインスタンスで得られた各値の平均値）である。各基地局で利用できる通信チャネルの数（｜Ｐ｜）を４，６，８，１０とし、各移動局位置からフレームロス率ｅ以下で通信しなければならない基地局数（ｕ）を１または２として計算を行った。この表の１行目は、｜Ｐ｜＝４、ｕ＝１のときの計算結果である。１行目の「可能解の数」欄の値は、ステップＳ１１〜Ｓ１５を１０００回実行したときに可能解を求めることができたインスタンス数は５だったことを示している。また、１行目の「基地局設置数」欄の値は、可能解が得られたインスタンスにおける設置コストの平均が２９０３．０百万円だったことを示し、「時間」欄の値は、可能解が得られたインスタンスにおける１０００回の繰り返しに要する時間の平均が１４．２秒だったことを示している。
この表から例えば、ｕ＝１の場合、利用できる通信チャネルの数は、基地局設置コストに大きな影響を与えないことが確認できる。また、ｕ＝２の場合、利用できる通信チャネルの数を６から８に増やすことにより、基地局設置コストを削減できることが確認できる。これは、Ｐ＝６の場合には通信チャネル数が不足していたために選択できなかった設置コストの安い基地局設置候補場所を、通信チャネル数を８に増やすことにより選択することができるようになったためと考えられる。
なお、｜Ｐ｜＝４、ｕ＝２の場合、「基地局設置数」及び「設置コスト」の欄に「−」が記載されているのは、この場合、５つのインスタンス全てで可能解が求まらなかったことを表している。
本実施形態によれば、さまざまな条件下の設置コストの傾向を比較した上で、設置コストを最低にする基地局配置を決定することができる。
【００８２】
図１３は、本発明に係る実施形態における基地局設置場所決定装置のハードウェア構成の一例を示すブロック図である。
図１３の符号１００は、基地局設置場所決定装置を示している。図１３に示す通り、基地局設置場所決定装置１００は、ＣＰＵ１０１と、ＲＯＭ、ＲＡＭなどのメモリ１０２と、ハードディスクなどの記憶部１０３と、キーボードやディスプレイなどの入出力部１０４を含む、コンピュータ装置によって実現される。これらの部材は、例えば、バスなどを介して相互に接続されている。ＣＰＵ１０１は、記憶部１０３に格納されたプログラムを実行することで種々の機能を実現する。例えば、本実施形態の海部アルゴリズムを記述したプログラムを実行して上述の計算部を実現する。記憶部１０３は、例えば、基地局配置場所決定処理に用いるプログラムや各種パラメータ、通信可能区間や電波干渉区間の情報、各種の処理結果を格納する。
【００８３】
上述した基地局設置場所決定装置１００における各処理の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムを基地局設置場所決定装置１００のコンピュータが読み出して実行することによって、上記処理が行われる。ここでコンピュータ読み取り可能な記録媒体とは、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、半導体メモリ等をいう。また、このコンピュータプログラムを通信回線によってコンピュータに配信し、この配信を受けたコンピュータが当該プログラムを実行するようにしてもよい。
【００８４】
また、上記プログラムは、前述した機能の一部を実現するためのものであってもよい。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であってもよい。
また、基地局設置場所決定装置１００は、１台のコンピュータで構成されていても良いし、通信可能に接続された複数のコンピュータで構成されていてもよい。
【００８５】
その他、本発明の趣旨を逸脱しない範囲で、上記した実施の形態における構成要素を周知の構成要素に置き換えることは適宜可能である。また、この発明の技術範囲は上記の実施形態に限られるものではなく、本発明の趣旨を逸脱しない範囲において種々の変更を加えることが可能である。なお、移動局位置は、通信対象位置の一例である。また、計算部がランダムに選択した基地局（２２Ａ，ＣＨ３）、基地局（２１Ａ、ＣＨ１）、基地局（２４Ａ、ＣＨ５）、基地局（２５Ａ、ＣＨ１）は、第１基地局候補の一例である。
【符号の説明】
【００８６】
１〜１０・・・移動局位置、２１Ａ〜２６Ａ、２１Ｂ〜２６Ｂ・・・基地局設置候補場所、３０・・・走行経路、３１Ａ〜３５Ａ・・・通信可能区間、３１Ｂ〜３５Ｂ・・・電波干渉区間、１００・・・基地局設置場所決定装置
【図１】
2016039404.tif 000017
【図２】
2016039404.tif 000018
【図３】
2016039404.tif 000019
【図４】
2016039404.tif 000020
【図５】
2016039404.tif 000021
【図６】
2016039404.tif 000022
【図７】
2016039404.tif 000023
【図８】
2016039404.tif 000024
【図９】
2016039404.tif 000025
【図１０】
2016039404.tif 000026
【図１１】
2016039404.tif 000027
【図１２】
2016039404.tif 000028
【図１３】
2016039404.tif 000029