(57)【要約】【課題】所定の移動経路を移動する各移動局と無線基地局との間で無線通信を実現する無線式制御システムにおける無線基地局の配置位置を適切に決定できる技術を提案すること。【解決手段】先ず、各通信（ｉ，ｋ，ｊ）の干渉無線基地局集合Ｂｉｋｊを空集合（φ）として、制約条件を初期設定した緩和問題（Ｑ）を生成し、この緩和問題（Ｑ）の最適解を算出して候補解とする。候補解に含まれる無線基地局（ｉ，ｋ）と、ある移動局位置ｊとの間の通信（ｉ，ｋ，ｊ）についての干渉無線基地局集合Ｂｉｋｊに含まれる無線基地局（ｉ′，ｋ′）が、候補解に存在するかを判定する。存在する場合、候補解は原問題（Ｐ）の最適解となり得ず、存在すると判定した通信（ｉ，ｋ，ｊ）についての干渉無線基地局（ｉ′，ｋ′）を、制約条件に追加設定して、再度、緩和問題（Ｑ）の最適解を求めて新たな候補解とする。存在しないならば、候補解を、原問題（Ｐ）である無線基地局配置問題の最適解（出力解）として決定する。【選択図】図９
2018032961.tif 000002
【特許請求の範囲】
【請求項１】
周波数チャネルのチャネル上限数および各無線基地局が制御可能な移動局上限数が定められた無線通信によって、所定の移動経路を移動する任意のｕ台以上（ｕ≧１）の無線基地局と通信可能となる前記無線基地局の設置位置および当該無線基地局が使用する周波数チャネルを、コンピュータに決定させるためのプログラムであって、
前記チャネル上限数および前記移動局上限数を所与の制約条件とし、前記無線基地局の設置候補場所毎に定められた設置費用に基づき、前記無線基地局の合計設置費用を最小化する最適化問題として、前記無線基地局の設置位置および当該無線基地局が使用する周波数チャネルの候補解を算出する算出手段、
前記候補解に含まれる設置位置の組み合わせのなかに、予め定められた設置場所候補の除外組み合わせが含まれているかを判定する判定手段、
含まれていると前記判定された場合に、当該含まれていると判定された前記除外組み合わせを設置位置の組み合わせとして選択しないことを前記制約条件に追加して前記制約条件を更新し、更新した制約条件に基づいて前記算出手段に新たな候補解を算出させる再算出手段、
含まれてないと前記判定された場合に、当該判定に係る候補解を出力解として決定する決定手段、
として前記コンピュータを機能させるためのプログラム。
【請求項２】
前記無線通信は、前記無線基地局が通信可能な所与の通信距離圏内での時分割通信であって、前記移動局上限数としてタイムスロットの上限数が定められており、
前記算出手段は、一の無線基地局の前記通信距離圏内の前記移動局の数が前記移動局上限数を超えないことを前記制約条件に更に含めて前記候補解を算出する、
請求項１に記載のプログラム。
【請求項３】
前記算出手段は、前記ｕの値として所与の値を前記制約条件に更に含めて前記候補解を算出する、
請求項１又は２に記載のプログラム。
【請求項４】
前記除外組み合わせは、互いの電波干渉によって所定の通信品質条件を満たさないとして予め定められた設置場所候補の組み合わせである、
請求項１〜３の何れか一項に記載のプログラム。
【請求項５】
周波数チャネルのチャネル上限数および各無線基地局が制御可能な移動局上限数が定められた無線通信によって、所定の移動経路を移動する任意の周波数チャネルで通信可能な各移動局が、前記移動経路上で存在し得る各位置においてｕ台以上（ｕ≧１）の無線基地局と通信可能となる前記無線基地局の設置位置および当該無線基地局が使用する周波数チャネルを決定するための無線基地局配置決定装置であって、
前記チャネル上限数および前記移動局上限数を所与の制約条件とし、前記無線基地局の設置候補場所毎に定められた設置費用に基づき、前記無線基地局の合計設置費用を最小化する最適化問題として、前記無線基地局の設置位置および当該無線基地局が使用する周波数チャネルの候補解を算出する算出手段と、
前記候補解に含まれる設置位置の組み合わせのなかに、予め定められた設置場所候補の除外組み合わせが含まれているかを判定する判定手段と、
含まれていると前記判定された場合に、当該含まれていると判定された前記除外組み合わせを設置位置の組み合わせとして選択しないことを前記制約条件に追加して前記制約条件を更新し、更新した制約条件に基づいて前記算出手段に新たな候補解を算出させる再算出手段と、
含まれてないと前記判定された場合に、当該判定に係る候補解を出力解として決定する決定手段と、
を備えた無線基地局配置決定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線基地局配置決定装置等に関する。
【背景技術】
【０００２】
鉄道では、無線通信を用いた無線式列車制御システムの開発が進められている。無線式列車制御システムでは、沿線に設置された無線基地局を介して、列車に搭載された車上装置と地上装置との間の無線通信が実現される（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２０１３−２３９９３５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
無線通信は、有線通信に比較して、通信エラーが生じ易いという欠点がある。このため、無線式列車制御システムにおける無線基地局の配置計画は、所定の通信品質を確保するため、様々な制約のもとに適切に決定する必要がある。単純に実現するためには、数多くの無線基地局を設置すれば良いとも考えられる。しかし、無線基地局の設置数が多いほど、無線基地局の設置費用の他、設置後の運用費用や保守費用が増大するという問題がある。
【０００５】
また、無線式列車制御システムの問題として述べたが、所定の移動経路を移動する複数の移動局と無線基地局との間で、絶え間の無い無線通信を実現するシステムであれば何れのシステムでも同様の問題があった。例えば路線バスの無線式制御システムも同様の問題があった。
【０００６】
本発明は、上記事情に鑑みてなされたものであり、その目的とするところは、所定の移動経路を移動する各移動局と無線基地局との間で無線通信を実現する無線式制御システムにおける無線基地局の配置位置を適切に決定できる技術を提案することである。
【課題を解決するための手段】
【０００７】
上記課題を解決するための第１の発明は、
周波数チャネルのチャネル上限数および各無線基地局が制御可能な移動局上限数が定められた無線通信によって、所定の移動経路を移動する任意の周波数チャネルで通信可能な各移動局が、前記移動経路上で存在し得る各位置においてｕ台以上（ｕ≧１）の無線基地局と通信可能となる前記無線基地局の設置位置および当該無線基地局が使用する周波数チャネルを、コンピュータに決定させるためのプログラムであって、
前記チャネル上限数および前記移動局上限数を所与の制約条件とし、前記無線基地局の設置候補場所毎に定められた設置費用に基づき、前記無線基地局の合計設置費用を最小化する最適化問題として、前記無線基地局の設置位置および当該無線基地局が使用する周波数チャネルの候補解を算出する算出手段、
前記候補解に含まれる設置位置の組み合わせのなかに、予め定められた設置場所候補の除外組み合わせが含まれているかを判定する判定手段、
含まれていると前記判定された場合に、当該含まれていると判定された前記除外組み合わせを設置位置の組み合わせとして選択しないことを前記制約条件に追加して前記制約条件を更新し、更新した制約条件に基づいて前記算出手段に新たな候補解を算出させる再算出手段、
含まれてないと前記判定された場合に、当該判定に係る候補解を出力解として決定する決定手段、
として前記コンピュータを機能させるためのプログラムである。
【０００８】
また、他の発明として、
周波数チャネルのチャネル上限数および各無線基地局が制御可能な移動局上限数が定められた無線通信によって、所定の移動経路を移動する任意の周波数チャネルで通信可能な各移動局が、前記移動経路上で存在し得る各位置においてｕ台以上（ｕ≧１）の無線基地局と通信可能となる前記無線基地局の設置位置および当該無線基地局が使用する周波数チャネルを決定するための無線基地局配置決定装置であって、
前記チャネル上限数および前記移動局上限数を所与の制約条件とし、前記無線基地局の設置候補場所毎に定められた設置費用に基づき、前記無線基地局の合計設置費用を最小化する最適化問題として、前記無線基地局の設置位置および当該無線基地局が使用する周波数チャネルの候補解を算出する算出手段と、
前記候補解に含まれる設置位置の組み合わせのなかに、予め定められた設置場所候補の除外組み合わせが含まれているかを判定する判定手段と、
含まれていると前記判定された場合に、当該含まれていると判定された前記除外組み合わせを設置位置の組み合わせとして選択しないことを前記制約条件に追加して前記制約条件を更新し、更新した制約条件に基づいて前記算出手段に新たな候補解を算出させる再算出手段と、
含まれてないと前記判定された場合に、当該判定に係る候補解を出力解として決定する決定手段と、
を備えた無線基地局配置決定装置を構成しても良い。
【０００９】
この第１の発明等によれば、予め定められた設置場所候補の除外組み合わせを含まず、無線基地局の合計設置費用を最小化するような、無線基地局の設置位置及び当該無線基地局が使用する周波数チャネルを、適切に決定することができる。具体的には、先ず、周波数チャネルのチャネル上限数（周波数チャネルの種類の総数ともいえる）、及び、各無線基地局が制御可能な移動局上限数を制約条件とし、合計設置費用を最小化する最適化問題として候補解を算出する。そして、この候補解に含まれている設置候補場所の除外組み合わせを無線基地局の設置位置として選択しないことを制約条件に追加して、再度、新たな候補解を算出することを、設置候補場所の除外組み合わせが含まれない候補解が算出されるまで繰り返す。つまり、先ずは、設置候補場所の除外組み合わせを除くことで制約条件を緩和した最適化問題から候補解の算出を開始し、徐々に制約条件に追加してゆくことで、最終的に設置候補場所の除外組み合わせを含まない出力解を決定する。
【００１０】
第２の発明として、第１の発明のプログラムであって、
前記無線通信は、前記無線基地局が通信可能な所与の通信距離圏内での時分割通信であって、前記移動局上限数としてタイムスロットの上限数が定められており、
前記算出手段は、一の無線基地局の前記通信距離圏内の前記移動局の数が前記移動局上限数を超えないことを前記制約条件に更に含めて前記候補解を算出する、
プログラムを構成しても良い。
【００１１】
この第２の発明によれば、一の無線基地局の通信距離圏内の移動局の数が、同一周波数チャネルで制御可能な移動局上限数であるタイムスロットの上限数を超えないことを制約条件に含めて、候補解が算出される。つまり、全ての移動局に何れかの無線基地局のタイムスロットが割り当てられるように、無線基地局の設置位置及び当該無線基地局が使用する周波数チャネルを決定することができる。
【００１２】
第３の発明として、第１又は第２の発明のプログラムであって、
前記算出手段は、前記ｕの値として所与の値を前記制約条件に更に含めて前記候補解を算出する、
プログラムを構成しても良い。
【００１３】
この第３の発明によれば、移動局が移動経路上で存在し得る各位置において通信可能となる無線基地局の所与の最小台数ｕを制約条件に含めて候補解が算出される。つまり、冗長構成とする無線基地局の最小台数ｕを任意に設定することができ、所望の信頼性を確保した無線基地局の設置位置及び当該無線基地局が使用する周波数チャネルを決定することができる。
【００１４】
第４の発明として、第１〜第３の何れかの発明のプログラムであって、
前記除外組み合わせは、互いの電波干渉によって所定の通信品質条件を満たさないとして予め定められた設置場所候補の組み合わせである、
プログラムを構成しても良い。
【００１５】
この第４の発明によれば、互いの電波干渉によって所定の通信品質条件を満たさない設置候補場所の組み合わせを除外組み合わせとすることができる。電波干渉による無線通信の通信品質は、周辺の他の無線基地局の設置状況や周波数チャネルの使用状況に応じて変動するため、互いの電波干渉によって所定の通信品質条件を満たさない設置候補場所の除外組み合わせは多数存在する。つまり、この設置候補場所の除外組み合わせの全てを制約条件とした最適化問題は処理負荷が大きく、最適解が算出されない場合もあり得る。しかし、第４の発明によれば、設置候補場所の除外組み合わせの全てを制約条件に含めた最適化問題の最適解を算出する場合に比較して、最適化問題の候補解の算出に要する処理負荷を軽減することができる。
【図面の簡単な説明】
【００１６】
【図１】無線式列車制御システムの概要図。
【図２】無線基地局配置モデルの概要図。
【図３】無線基地局の設置費用及び周波数チャネルの説明図。
【図４】フレームロス率の説明図。
【図５】冗長構成の説明図。
【図６】無線基地局のタイムスロットの割り当ての説明図。
【図７】列車配置に対するタイムスロットの割り当ての説明図。
【図８】無線基地局配置決定装置の機能構成図。
【図９】無線基地局配置決定処理のフローチャート。
【発明を実施するための形態】
【００１７】
以下、本発明を適用した実施形態について説明する。本発明は、所定の移動経路を移動する複数の移動局と無線基地局との間で無線通信を実現するシステムであれば何れのシステムにも適用可能であるが、本実施形態ではその一例として無線式列車システムを例に挙げて説明する。
【００１８】
［原理］
本実施形態は、図１に示すような、列車２０に搭載された移動局２２と、地上に設置された無線基地局３０との間で無線通信を行う無線式列車制御システムにおける無線基地局３０の設置場所を決定する配置計画に関するものである。
【００１９】
（Ａ）数理モデル
図２は、本実施形態における無線基地局３０の設置場所の決定のための数理モデルである無線基地局配置モデルの概要図である。無線基地局配置モデルには、図２に示すように、列車２０の移動経路である線路１０に沿って、列車２０に搭載された移動局２２が無線基地局３０と通信を行う可能性がある多数の移動局位置１２が定められているとともに、線路１０の近傍に、無線基地局３０の設置場所の候補である多数の設置候補場所３２が定められている。本実施形態では、これらの設置候補場所３２のうちの何れに無線基地局３０を設置すべきかという無線基地局配置問題を設定し、次に示す制約条件に従って最適解を算出することで、無線基地局３０の配置位置、及び、当該無線基地局３０が使用する周波数チャネルを決定する。
【００２０】
（Ｂ）制約条件
（ｂ−１）周波数チャネルの割り当て
設置候補場所３２に配置した無線基地局３０には、１つの周波数チャネルを割り当てる。割り当て可能な周波数チャネルの上限数（周波数チャネルの種類の総数ともいえる）は予め定められている。また、周波数チャネルは、後述のように、無線基地局３０間で互いに電波干渉が起こらないように割り当てられる。なお、以下では、設置候補場所３２に配置した無線基地局３０に周波数チャネルを割り当てることを、設置候補場所３２に周波数チャネルを割り当てる、と表現することがある。
【００２１】
（ｂ−２）設置費用
また、設置候補場所３２には、無線基地局３０の設置に要する費用（コスト）が定められている。設置費用は、設置候補場所３２毎に定められており、設置する無線基地局３０に割り当てられる周波数チャネルに依存しない。
【００２２】
図３は、無線基地局３０の配置の一例であり、周波数チャネルの割り当て、及び、設置費用を示している。図３（ａ）では、設置候補場所３２ｂ，３２ｆそれぞれに、無線基地局３０が設置され、周波数チャネルＣＨ１，ＣＨ３が割り当てられている。また、設置候補場所３２ｂ，３２ｆには、それぞれ、設置費用として１００万円、１１０万円が定められており、合計の設置費用は２１０万円である。また、図３（ｂ）では、設置候補場所３２ｂ，３２ｅそれぞれに、無線基地局３０が設置され、周波数チャネルＣＨ２，ＣＨ３が割り当てられている。また、設置候補場所３２ｂ，３２ｅには、それぞれ、設置費用として１００万円、９０万円が定められており、合計の設置費用は１９０万円である。
【００２３】
（ｂ−３）フレームロス率
また、無線基地局３０から送出された信号を移動局位置１２で受信する際のフレームロス率は、所定の許容値（許容フレームロス率）ｅ以下でなくてはならない。フレームロス率は、送出元の無線基地局３０と、その周辺の他の無線基地局３０との相対的な設置距離（相対的な設置位置）や、当該無線基地局３０に割り当てられた周波数チャネルといった設置環境によって異なる。フレームロスは、無線基地局３０間の電波干渉によって生じるものだからである。
【００２４】
図４は、無線基地局３０の配置の一例であり、フレームロス率を示している。図４（ａ）では、設置候補場所３２ｂ，３２ｄそれぞれに、無線基地局３０が設置され、周波数チャネルＣＨ２，ＣＨ１が割り当てられている。設置候補場所３２ｄの無線基地局３０が送出する信号を、移動局位置１２ｃで受信する際のフレームロス率は「１．２５×１０−３」である。また、図４（ｂ）では、設置候補場所３２ａ，３２ｄ，３２ｆそれぞれに、無線基地局３０が設置され、周波数チャネルＣＨ３，ＣＨ１，ＣＨ４が割り当てられている。そして、設置候補場所３２ｄの無線基地局３０が送出する信号を、移動局位置１２ｃで受信する際のフレームロス率は「３．１×１０−４」である。つまり、図４（ａ），（ｂ）を比較すると、同一の設置候補場所３２ｄに設置された無線基地局３０が送出する信号を同一の移動局位置１２ｃで受信する場合であっても、設置候補場所３２ｄの周辺における他の無線基地局３０の設置有無や割り当てられている周波数チャネルの違いによって、フレームロス率が異なっている。こうしたフレームロス率は、予め計算して求めておくことができる。
【００２５】
（ｂ−４）冗長構成
また、移動局位置１２それぞれでは、少なくともｕ基（ｕ≧１）の無線基地局３０からの信号を、所定の許容値ｅ以下のフレームロス率で受信できなくてはならない。
【００２６】
図５は、無線基地局３０の設置の一例であり、冗長構成を示している。図５（ａ）では、設置候補場所３２ｂ，３２ｄ，３２ｆ，３２ｈそれぞれに、無線基地局３０ａ〜３０ｄが設置され、周波数チャネルＣＨ１，ＣＨ３，ＣＨ２，ＣＨ４が割り当てられている。設置候補場所３２ｂに設置された無線基地局３０ａの通信可能範囲３４ａは、移動局位置１２ａ〜１２ｃを含み、設置候補場所３２ｄに設置された無線基地局３０ｂの通信可能範囲３４ｂは、移動局位置１２ａ〜１２ｅを含み、設置候補場所３２ｆに設置された無線基地局３０ｃの通信可能範囲３４ｃは、移動局位置１２ｄ〜１２ｈを含み、設置候補場所３２ｈに設置された無線基地局３０ｄの通信可能範囲３４ｄは、移動局位置１２ｆ〜１２ｈを含む。
【００２７】
無線基地局３０の通信可能範囲３４とは、この無線基地局３０が送出する信号を、所定の許容値ｅ以下のフレームロス率で受信可能な範囲のことであり、当該無線基地局３０の通信距離圏内を意味する。フレームロス率は、送出元の無線基地局３０を基準として、その周辺の他の無線基地局３０の設置環境（相対的な設置距離や互いの周波数チャネル等）によって異なるため、設置環境が異なると、通信可能範囲３４も異なる。以下では、ある移動局位置１２がある無線基地局３０の通信可能範囲３４に含まれること、つまり、ある移動局位置１２において、ある設置候補場所３２に設置された無線基地局３０から送出される信号を許容フレームロス率ｅ以下で受信可能なことを、当該移動局位置１２と当該無線基地局３０とは通信可能であると表記する。
【００２８】
図５（ａ）では、移動局位置１２ａ〜１２ｈの全てにおいて、２基の無線基地局３０と通信可能である。冗長構成の条件を、ｕ＝２、とすると、これを満たしている。
【００２９】
図５（ｂ）では、設置候補場所３２ｂ，３２ｄ，３２ｇ，３２ｈそれぞれに、無線基地局３０ａ〜３０ｄが設置され、周波数チャネルＣＨ１，ＣＨ３，ＣＨ２，ＣＨ４が割り当てられている。設置候補場所３２ｂに設置された無線基地局３０ａの通信可能範囲３４ａは、移動局位置１２ａ〜１２ｃを含み、設置候補場所３２ｄに設置された無線基地局３０ｂの通信可能範囲３４ｂは、移動局位置１２ａ〜１２ｅを含み、設置候補場所３２ｇに設置された無線基地局３０ｃの通信可能範囲３４ｃは、移動局位置１２ｅ〜１２ｈを含み、設置候補場所３２ｈに設置された無線基地局３０ｄの通信可能範囲３４ｄは、移動局位置１２ｆ〜１２ｈを含む。移動局位置１２ａ〜１２ｃ，１２ｅ〜１２ｈにおいては、２基の無線基地局３０と通信可能であるが、移動局位置１２ｄにおいては、１基の無線基地局３０のみと通信可能である。従って、冗長構成の条件を、ｕ＝２、とすると、これを満たしていない。
【００３０】
（ｂ−５）タイムスロット割り当て
無線基地局３０では、通信フレームを複数のタイムスロットに分割し、１つのタイムスロットに１つの列車２０を割り当てる時分割多重方式によって、通信可能範囲３４内の列車２０（正確には、列車２０に搭載された移動局２２）との通信を行っている。すなわち、無線基地局３０では、制御対象とする全ての列車２０にタイムスロットを１つずつ割り当てる必要がある。しかし、１つの無線基地局３０において列車２０を割り当てられるタイムスロット数に上限があり、１つの無線基地局３０の通信可能範囲内にタイムスロット数の上限を超える本数の列車２０を在線させることはできない。
【００３１】
図６は、無線基地局３０におけるタイムスロットの割り当ての一例である。図６では、無線基地局３０ａ，３０ｂは、何れもタイムスロット数の上限が「４」である。無線基地局３０ａの通信可能範囲３４ａ内には、タイムスロット数の上限である「４」を超える５本の列車２０ａ〜２０ｅが在線しており、１本の列車２０ｅは通信不可能（制御不可能）となっている。また、無線基地局３０ｂの通信可能範囲３４ｂ内には、タイムスロット数の上限である「４」を超えない３本の列車２０ｆ〜２０ｈが在線しており、全ての列車２０ｆ〜ｇが制御可能となっている。
【００３２】
具体的には、所与の列車配置に対して、全ての無線基地局３０がタイムスロット数の上限を超えることなく、この列車配置に含まれる全ての在線列車を制御できるように、無線基地局３０を配置しなくてはならない。列車配置とは、列車２０は移動局位置１２に在線するとして、複数の列車２０の在線位置を表したものである。この列車配置は、所与の列車ダイヤから想定される、ある時点での列車２０の運行状況に相当する。
【００３３】
図７は、列車配置の一例である。図７では、４つの無線基地局３０ａ〜３０ｄが設置されている。無線基地局３０ａの通信可能範囲３４ａは、移動局位置１２ａ〜１２ｅを含み、無線基地局３０ｂの通信可能範囲３４ｂは、移動局位置１２ｆ〜１２ｋを含み、無線基地局３０ｃの通信可能範囲３４ｃは、移動局位置１２ｌ〜１２ｐを含み、無線基地局３０ｄの通信可能範囲３４ｄは、移動局位置１２ｑ〜１２ｔを含む。
【００３４】
また、３種類の列車配置（１）〜（３）が与えられている。列車配置（１）は、合計６本の列車２０ａ〜２０ｆが、移動局位置１２ｂ，１２ｆ，１２ｉ，１２ｍ，１２ｑ，１２ｔそれぞれに在線しており、列車配置（２）は、合計１１本の列車２０ｇ〜２０ｑが、移動局位置１２ａ〜１２ｃ，１２ｅ，１２ｈ，１２ｊ〜１２ｌ，１２ｐ，１２ｓ，１２ｔそれぞれに在線しており、列車配置（３）は、合計９本の列車２０ｒ〜２０ｚが、移動局位置１２ｈ，１２ｉ，１２ｋ，１２ｍ，１２ｏ，１２ｐ，１２ｒ〜１２ｔそれぞれに在線している。
【００３５】
そして、列車配置（１）に対しては、無線基地局３０ａの通信可能範囲３４ａ内には１本の列車２０ａが、無線基地局３０ｂの通信可能範囲３４ｂ内には２本の列車２０ｂ，２０ｃが、無線基地局３０ｃの通信可能範囲３４ｃ内には１本の列車２０ｄが、無線基地局３０ｄの通信可能範囲３４ｄ内には２本の列車２０ｅ，２０ｆが、それぞれ在線している。また、列車配置（２）に対しては、無線基地局３０ａの通信可能範囲３４ａ内には４本の列車２０ｇ〜２０ｊが、無線基地局３０ｂの通信可能範囲３４ｂ内には３本の列車２０ｋ〜２０ｍが、無線基地局３０ｃの通信可能範囲３４ｃ内には２本の列車２０ｎ，２０ｏが、無線基地局３０ｄの通信可能範囲３４内には２本の列車２０ｐ，２０ｑが、それぞれ在線している。また、列車配置（３）に対しては、無線基地局３０ａの通信可能範囲３４ａ内には列車２０は在線しておらず、無線基地局３０ｂの通信可能範囲３４ｂ内には３本の列車２０ｒ〜２０ｔが、無線基地局３０ｃの通信可能範囲３４ｃ内には３本の列車２０ｕ〜２０ｗが、無線基地局３０ｄの通信可能範囲３４ｄ内には３本の列車２０ｘ〜２０ｚが、それぞれ在線している。従って、タイムスロット数の上限が「４」以上であれば、これら全ての列車配置を満たすが、「３」以下の場合には、無線基地局３０の配置計画としては不適合である。
【００３６】
（Ｃ）問題の定式化
本実施形態における無線基地局配置問題は、次のように定式化される。先ず、無線基地局の設置候補場所の集合をＭ（Ｍ＝｛１，２，・・，｜Ｍ｜｝）、移動局位置の集合をＮ（Ｎ＝｛１，２，・・，｜Ｎ｜｝）、各無線基地局で利用可能な周波数チャネルの集合をＰ（Ｐ＝｛１，２，・・，｜Ｐ｜｝）、周波数チャネルｋ（ｋ∈Ｐ）と相互に電波が干渉する周波数チャネルの集合をＰｋ、とする。また、設置候補場所ｉ（ｉ∈Ｍ）に無線基地局を設置する際の費用をＣｉ、無線基地局と移動局位置との間の各通信の許容フレームロス率をｅ、各無線基地局で制御対象とする列車に割り当てることができるタイムスロット数の上限をｓ、とする。また、鉄道輸送の安定性を確保するために、各移動局位置では、ｕ基以上の無線基地局と許容フレームロス率ｅ以下で通信可能でなければならないものとする。
【００３７】
また、設置候補場所ｉ（ｉ∈Ｍ）に設置する周波数チャネルｋ（ｋ∈Ｐ）の無線基地局を無線基地局（ｉ，ｋ）、無線基地局（ｉ，ｋ）と移動局位置ｊとの通信を通信（ｉ，ｋ，ｊ）、と表すこととする。また、電波干渉が発生しない場合に、無線基地局（ｉ，ｋ）から許容フレームロス率ｅ以下で通信可能な移動局位置の集合をＮｉｋと表す。そして、設置候補場所と移動局位置との間で使用可能な通信の集合をＡとし、次式（１）のように定義する。
【数１】
2018032961.tif 000003
【００３８】
また、通信（ｉ，ｋ，ｊ）に対して、無線基地局（ｉ１，ｋ１），（ｉ２，ｋ２），・・，（ｉｒ，ｋｒ）の中の何れか１基が設置されると、電波干渉の影響により、フレームロス率が許容値ｅを超えてしまう無線基地局の集合｛（ｉ１，ｋ１），（ｉ２，ｋ２），・・，（ｉｒ，ｋｒ）｝を、通信（ｉ，ｋ，ｊ）の干渉無線通信基地局Ｂｉｋｊとする。つまり、通信（ｉ，ｋ，ｊ）の干渉無線通信基地局Ｂｉｋｊとは、予め定められた設置場所候補の除外組み合わせと言うことができ、通信（ｉ，ｋ，ｊ）と、干渉無線通信基地局Ｂｉｋｊの集合中の何れか１以上の無線基地局との組み合わせは、無線基地局の配置として不適合であることを示す。
【００３９】
また、各無線基地局で制御可能な列車本数には上限があるため、列車配置も考慮する必要がある。列車は移動局位置に在線するものとして、列車配置ｒを、列車が在線する移動局位置の部分集合として表現し、変数ａｒｊを用いて次式（２）のように定義する。
【数２】
2018032961.tif 000004
そして、この列車配置ｒの集合をＲ（Ｒ＝｛１，２，・・，｜Ｒ｜｝）、とする。
【００４０】
また、通信（ｉ，ｋ，ｊ）に変数ｘｉｋｊを付与し、無線基地局（ｉ，ｋ）に変数ｙｉｋを付与して、次式（３），（４）のように定義する。
【数３】
2018032961.tif 000005
【００４１】
そして、各移動局位置における許容フレームロス率以下での通信、及び、上限数を超えない各列車へのタイムスロットの割り当てを可能とするとともに、無線基地局の設置費用が最小となるような、無線基地局の設置数と設置場所、及び、各無線基地局への周波数チャネルの割り当てを決定する無線基地局配置問題は、次のような０−１整数計画問題に定式化される。
【数４】
2018032961.tif 000006
【００４２】
この定式化において、式（５）は、目的関数であり、設置費用の最小化が目的であることを示している。式（６）〜（１０）は、制約条件である。式（６）は、冗長構成に関する制約条件であり、各移動局位置において、ｕ基以上の無線基地局と許容フレームロス率ｅ以下で通信可能であることを保証する。式（７）は、ネットワーク構成に関する制約条件であり、使用する通信に必要な無線基地局を設置することを保証する。式（８）は、周波数チャネルの割り当てに関する制約条件であり、各無線基地局には２つ以上の周波数チャネルが割り当てられないことを保証する。式（９）は、伝送品質に関する制約条件であり、使用する通信のフレームロス率は許容値ｅ以下であることを保証する。式（１０）は、タイムスロットの割り当てに関する制約条件であり、各無線基地局で制御する列車本数は、タイムスロットの上限数ｓ以下であることを保証する。式（１１），（１２）は、決定変数の０−１条件である。
【００４３】
（Ｄ）解法アルゴリズム
このように設定した無線基地局配置問題を解いて最適解を求めるが、制約条件のうち、式（９）に示した伝送品質に関する制約条件を満たすための演算量が非常に大きく、最適解が求められない場合が起こり得る。つまり、干渉無線基地局集合Ｂｉｋｊは、通信（ｉ，ｋ，ｊ）別に定められるが、使用可能な通信（ｉ，ｋ，ｊ）の総数は、設置候補場所の数と、各無線基地局が使用可能な周波数チャネルの総数と、移動局位置の数とに依存して指数関数的に増加するため、膨大となる。このため、本実施形態では、原問題（Ｐ）である無線基地局配置問題に対して、制約条件を緩和した緩和問題（Ｑ）を生成し、この緩和問題（Ｑ）を解くことで、原問題（Ｐ）である無線基地局配置問題の最適解を算出する。
【００４４】
具体的には、各通信（ｉ，ｋ，ｊ）の干渉無線基地局集合Ｂｉｋｊを空集合（φ）とすることで、伝送品質に関する制約条件を緩和するように制約条件を初期設定した緩和問題（Ｑ）を生成する。そして、緩和問題（Ｑ）の最適解を算出し、候補解とする。次いで、この候補解が、原問題（Ｐ）の最適解となり得るかを判定する。すなわち、候補解が、原問題（Ｐ）における伝送品質に関する制約条件を満たすかを判定する。候補解は、無線基地局を設置する設置候補場所ｉと、当該無線基地局に割り当てる周波数チャネルｋとの組み合わせである。そして、候補解に含まれる無線基地局（ｉ，ｋ）と、ある移動局位置ｊとの間の通信（ｉ，ｋ，ｊ）についての干渉無線基地局集合Ｂｉｋｊに含まれる無線基地局（ｉ′，ｋ′）が候補解に存在する場合、候補解は、原問題（Ｐ）における伝送品質に関する制約条件を満たさないことになる。これは、次式（１３）のように定義される。
【数５】
2018032961.tif 000007
【００４５】
無線基地局（ｉ，ｋ）からの通信（ｉ，ｋ，ｊ）の干渉無線基地局Ｂｉｋｊに無線基地局（ｉ′，ｋ′）が含まれる場合、無線基地局（ｉ′，ｋ′）からの通信（ｉ′，ｋ′，ｊ）の干渉無線基地局Ｂｉｋ′ｊ′にも無線基地局（ｉ，ｋ）が含まれることになる。すなわち、無線基地局（ｉ，ｋ）と無線基地局（ｉ′，ｋ′）とは、互いに無線干渉基地局である。従って、候補解が原問題（Ｐ）における伝送品質に関する制約条件を満たさないとは、候補解に、互いの電波干渉によって、ある移動局位置１２でのフレームロス率が許容値ｅ以下とはならない設置場所候補の組み合わせ（除外組み合わせ）、すなわち、互いに干渉無線基地局となる組み合わせが含まれる場合といえる。
【００４６】
候補解が原問題（Ｐ）における伝送品質に関する制約条件を満たさないならば、候補解は、原問題（Ｐ）の最適解とはならない。この場合には、伝送品質を満たさないと判定された通信（ｉ，ｋ，ｊ）についての干渉無線基地局（ｉ′，ｋ′）を、制約条件に追加設定して、再度、緩和問題（Ｑ）の最適解を求めて新たな候補解とする。
【００４７】
一方、候補解が原問題（Ｐ）における伝送品質に関する制約条件を満たすならば、候補解を、原問題（Ｐ）である無線基地局配置問題の最適解（出力解）として決定する。
【００４８】
［機能構成］
図８は、無線基地局配置決定装置１の機能構成図である。図８によれば、無線基地局配置決定装置１は、無線基地局の配置計画の実行、或いは、無線基地局の配置計画を支援するための装置であり、操作部１０２と、表示部１０４と、音出力部１０６と、通信部１０８と、処理部２００と、記憶部３００とを備えて構成される一種のコンピュータである。
【００４９】
操作部１０２は、例えばキーボードやマウス、タッチパネル、各種スイッチ等の入力装置で実現され、なされた操作入力に応じた操作信号を処理部２００に出力する。表示部１０４は、例えば液晶ディスプレイや有機ＥＬディスプレイ等の表示装置で実現され、処理部２００からの表示信号に基づく各種表示を行う。音出力部１０６は、例えばスピーカ等の音出力装置で実現され、処理部２００からの音声信号に基づく各種音声出力を行う。通信部１０８は、例えば無線通信モジュールやルータ、モデム、有線用の通信ケーブルのジャックや制御回路等で実現される通信装置であり、外部装置とのデータ通信を行う。
【００５０】
処理部２００は、ＣＰＵ（Central Processing Unit）やＦＰＧＡ（Field Programmable Gate Array）等の演算装置や演算回路で実現され、記憶部３００に記憶されたプログラムやデータ等にもとづいて、無線基地局配置決定装置１の全体制御を行う。また、処理部２００は、機能的な処理ブロックとして、制約条件初期設定部２０２と、候補解算出部２０４と、最適解判定部２０６と、制約条件追加設定部２０８と、出力解決定部２１０と、を有する。そして、移動局配置決定プログラム３０２を実行することで、入力情報３１０に基づき、無線基地局配置問題情報３０４として設定されている無線基地局配置問題の最適解を算出する。
【００５１】
入力情報３１０は、無線基地局の配置計画を実行する、すなわち無線基地局配置問題を解くための前提となるパラメータであり、設置候補場所３２の集合Ｍである設置候補場所情報３１２と、移動局位置１２の集合Ｎである移動局位置情報３１４と、各無線基地局３０で使用可能な周波数チャネルの集合Ｐである周波数チャネル情報３１６と、各設置候補場所ｉに無線基地局３０を設置する際の設置費用Ｃｉである無線基地局設置費用情報３１８と、使用可能な各通信（ｉ，ｋ，ｊ）の干渉無線通信基地局の集合Ｂｉｋｊである干渉無線基地局情報３２０と、列車配置ｒの集合Ｒである列車配置情報３２２と、無線基地局３０と移動局位置１２との間の各通信のフレームロス率の許容値ｅである許容フレームロス率３２４と、各移動局位置１２で通信可能な無線基地局３０の最小基数ｕである無線基地局冗長基数３２６と、各無線基地局３０で制御対象とする列車に割り当てることができるタイムスロット数の上限ｓであるタイムスロット数上限３２８と、を含んでいる。無線基地局配置問題情報３０４は、式（５）〜（１２）に示したように定式化された無線基地局配置問題の情報である。
【００５２】
制約条件初期設定部２０２は、無線基地局配置問題に対する制約条件の初期設定を行う。具体的には、各通信（ｉ，ｋ，ｊ）の干渉無線基地局集合Ｂｉｋｊを空集合（φ）とすることで、伝送品質に関する制約条件を緩和するように制約条件を初期設定した緩和問題（Ｑ）を生成する。
【００５３】
候補解算出部２０４は、制約条件初期設定部２０２或いは制約条件追加設定部２０８によって制約条件が設定された緩和問題（Ｑ）の最適解を算出し、候補解とする。候補解は、無線基地局を設置する設置候補場所ｉと、当該無線基地局に割り当てる周波数チャネルｋとの組み合わせである。
【００５４】
候補解算出部２０４による候補解の算出に関する情報は、算出毎に、候補解情報３３０として記憶される。候補解情報３３０は、該当する候補解を算出したときに設定されていた制約条件３３２と、候補解として算出された、設置候補場所のうちの無線基地局の設置場所、及び、当該無線基地局へ割り当てた周波数チャネルの組み合わせである基地局配置情報３３４と、候補解として算出された各無線基地局の設置場所に定められている設置費用の合計である合計設置費用３３６と、を含む。
【００５５】
最適解判定部２０６は、候補解算出部２０４によって算出された候補解が、原問題である無線基地局配置問題の最適解となり得るかを判定する。具体的には、候補解に含まれる無線基地局（ｉ，ｋ）と、ある移動局位置ｊとの間の通信（ｉ，ｋ，ｊ）についての干渉無線基地局集合Ｂｉｋｊに含まれる無線基地局（ｉ′，ｋ′）が、候補解に存在するかを判定する。存在する場合、候補解は、原問題（Ｐ）における伝送品質に関する制約条件を満たさず、原問題（Ｐ）である無線基地局配置問題の最適解とはならないと判定する。一方、存在しない場合、候補解は、原問題（Ｐ）における伝送品質に関する制約条件を満たし、原問題である無線基地局配置問題の最適解となると判定する。
【００５６】
制約条件追加設定部２０８は、最適解判定部２０６によって最適解でないと判定された場合に、無線基地局配置問題に対して制約条件を追加設定する。具体的には、最適解判定部２０６によって、候補解に含まれると判定された通信（ｉ，ｋ，ｊ）についての干渉無線基地局（ｉ′，ｋ′）を、該通信（ｉ，ｋ，ｊ）についての干渉無線基地局集合Ｂｉｋｊとして、制約条件に追加設定する。すなわち、候補解に含まれる、互いの電波干渉によってある移動局位置１２でのフレームロス率が許容値ｅ以下とならない設置場所候補の組み合わせ（除外組み合わせ）を、制約条件に追加する。
【００５７】
出力解決定部２１０は、最適解判定部２０６によって最適解であると判定された場合に、候補解を、原問題（Ｐ）である無線基地局配置問題の最適解（出力解）として決定する。出力解決定部２１０が決定した出力解に関する情報は、出力解情報３４０として記憶される。この出力解情報３４０は、出力解として決定された候補解に該当する候補解情報３３０と同一データである。
【００５８】
記憶部３００は、ＲＯＭやＲＡＭ等のＩＣメモリや、ハードディスク等の記憶装置で実現され、処理部２００が無線基地局配置決定装置１を統合的に制御するためのプログラムやデータ等を記憶しているとともに、処理部２００の作業領域として用いられ、処理部２００が実行した演算結果や、通信部１０８からの受信データ等が一時的に格納される。また、記憶部３００には、無線基地局配置決定プログラム３０２と、無線基地局配置問題情報３０４と、入力情報３１０と、候補解情報３３０と、出力解情報３４０と、が記憶される。
【００５９】
［処理の流れ］
図９は、無線基地局配置決定処理の流れを説明するフローチャートである。この処理は、処理部２００が、無線基地局配置決定プログラム３０２を実行することで実現される。
【００６０】
先ず、制約条件初期設定部２０２が、各通信（ｉ，ｋ，ｊ）の干渉無線基地局集合Ｂｉｋｊを空集合（φ）とすることで、伝送品質に関する制約条件を緩和するように、無線基地局配置問題に対する制約条件を初期設定した緩和問題（Ｑ）を生成する（ステップＳ１）。次いで、候補解算出部２０４が、生成された緩和問題（Ｑ）の最適解を算出し、候補解とする（ステップＳ３）。
【００６１】
続いて、最適解判定部２０６が、候補解に含まれる無線基地局（ｉ，ｋ）と、ある移動局位置ｊとの間の通信（ｉ，ｋ，ｊ）についての干渉無線基地局集合Ｂｉｋｊに含まれる無線基地局（ｉ′，ｋ′）が、候補解に存在するかによって、算出された候補解が、原問題（Ｐ）である無線基地局配置問題の最適解となり得るかを判定する（ステップＳ５）。その結果、最適解でないと判定したならば（ステップＳ７：ＮＯ）、制約条件追加設定部２０８が、候補解に含まれると判定された通信（ｉ，ｋ，ｊ）についての干渉無線基地局（ｉ′，ｋ′）を、該通信（ｉ，ｋ，ｊ）についての干渉無線基地局集合Ｂｉｋｊとして、制約条件に追加設定する（ステップＳ９）。その後、ステップＳ３に戻り、最適解を再算出する。
【００６２】
一方、候補解は最適解であると判定したならば（ステップＳ７：ＹＥＳ）、出力解決定部が、候補解を、原問題（Ｐ）である無線基地局配置問題の最適解（出力解）として決定する（ステップＳ１１）。以上の処理を行うと、無線基地局配置決定処理を終了する。
【００６３】
［作用効果］
このように、本実施形態によれば、各移動局位置でｕ基以上の無線基地局と許容フレームロス率ｅ以下で通信可能であること、制御対象とする全ての列車にタイムスロットを１つずつ割り当てることが可能であることを要件として、無線基地局の合計設置費用を最小化するような、無線基地局の設置位置及び当該無線基地局が使用する周波数周波数チャネルを決定することができる。
【００６４】
なお、本発明の適用可能な実施形態は上述の実施形態に限定されることなく、本発明の趣旨を逸脱しない範囲で適宜変更可能なのは勿論である。
【００６５】
例えば、上述の実施形態では、列車制御システムの例を挙げたが、路線バスの制御システムに関する無線基地局の配置計画に本発明を適用することとしてもよい。
【符号の説明】
【００６６】
１０  線路、１２  移動局位置、２０  列車、２２  移動局
３０  無線基地局、３２  設置候補場所、３４  通信可能範囲
１  無線基地局配置決定装置
１０２  操作部、１０４  表示部、１０６  音出力部、１０８  通信部
２００  処理部
２０２  制約条件初期設定部、２０４  候補解算出部
２０６  最適解判定部、２０８  制約条件追加設定部
２１０  出力解決定部
３００  記憶部
３０２  無線基地局配置決定プログラム
３０４  無線基地局配置問題情報、３１０  入力情報
３３０  候補解情報、３４０  出力解情報
【図１】
2018032961.tif 000008
【図２】
2018032961.tif 000009
【図３】
2018032961.tif 000010
【図４】
2018032961.tif 000011
【図５】
2018032961.tif 000012
【図６】
2018032961.tif 000013
【図７】
2018032961.tif 000014
【図８】
2018032961.tif 000015
【図９】
2018032961.tif 000016