(57)【要約】【課題】基地局の設置可能な位置の数が多くても、基地局の配置を決める際の効率を向上させる。【解決手段】範囲取得ステップにおいて、基地局の設置可能範囲、および無線通信可能範囲が前記基地局の設置可能範囲と少なくとも一部重複する複数の無線装置のそれぞれの上記無線通信可能範囲の情報を取得する。次に、集合取得ステップにおいて、上記基地局の設置可能範囲において上記無線通信可能範囲が互いに重複する無線装置の組の集合を、上記集合に上記複数の無線装置のそれぞれが少なくとも１つ含まれるように、かつ上記集合の要素数および上記組の要素数の少なくとも一方に関する条件を満たすように、取得する。【選択図】図１
2015012495.tif 000002
【特許請求の範囲】
【請求項１】
基地局の設置可能範囲、および無線通信可能範囲が前記基地局の設置可能範囲と少なくとも一部重複する複数の無線装置のそれぞれの前記無線通信可能範囲の情報を取得する範囲取得ステップと、
前記基地局の設置可能範囲において前記無線通信可能範囲が互いに重複する無線装置の組の集合を、前記集合に前記複数の無線装置のそれぞれが少なくとも１つ含まれるように、かつ前記集合の要素数および前記組の要素数の少なくとも一方に関する条件を満たすように、取得する集合取得ステップと、
を有する情報処理方法。
【請求項２】
前記集合取得ステップは、前記集合の要素数に関する条件として、前記集合に含まれる組数が最小、一定値以下、または所定の範囲内になるように、前記無線装置の組の集合を取得する
請求項１に記載の情報処理方法。
【請求項３】
前記集合取得ステップは、前記組の要素数に関する条件として、前記無線通信可能範囲が最も多くまたは一定数以上交差する領域を前記無線通信可能範囲内に含む無線通信の組を含むように、前記無線装置の組の集合を取得する
請求項１または２に記載の情報処理方法。
【請求項４】
前記集合取得ステップは、前記組の要素数に関する条件として、前記無線装置の組に含まれる無線装置の台数が上限値以下になるように、前記無線装置の組の集合を取得する
請求項１ないし３のいずれか一項に記載の情報処理方法。
【請求項５】
前記集合取得ステップで取得された集合に含まれる前記無線装置の組を構成する各無線装置の無線通信可能範囲および前記設置可能範囲間の重複領域に基地局を配置することを決定する配置決定ステップ
さらに備えた請求項１ないし４のいずれか一項に記載の情報処理方法。
【請求項６】
前記配置決定ステップは、前記各無線装置の無線通信可能範囲の外郭線の交差部に前記基地局を配置することを決定する
請求項５に記載の情報処理方法。
【請求項７】
前記集合取得ステップは、前記複数の無線装置のうち他の無線装置と無線通信可能範囲が重複しない第１無線装置が存在する場合は、前記第１無線装置以外の無線装置のそれぞれが少なくとも１つ含まれるように、前記無線装置の組の集合を取得する、
請求項１ないし６のいずれか一項に記載の情報処理方法。
【請求項８】
前記集合取得ステップで取得された集合に含まれる前記無線装置の組を構成する各無線装置の無線通信可能範囲および前記設置可能範囲間の重複領域、及び前記第１無線装置の無線通信可能範囲と前記設置可能範囲との重複領域に基地局を配置することを決定する配置決定ステップ
さらに備えた請求項７に記載の情報処理方法。
【請求項９】
前記配置決定ステップは、前記各無線装置の無線通信可能範囲の外郭線の交差部に前記基地局を配置することを決定する
請求項８に記載の情報処理方法。
【請求項１０】
前記集合取得ステップは、前記複数の無線装置に対して前記無線通信可能範囲の外郭線が互いに交差する無線装置を検出することに基づき、前記無線通信可能範囲が互いに重複する無線装置の組を検出する
請求項１ないし９のいずれか一項に記載の情報処理方法。
【請求項１１】
前記基地局の設置可能範囲は、平面内の所定範囲であり、
前記集合取得ステップは、無線装置毎に、前記無線装置の無線通信可能範囲と前記平面との交差領域の外郭線を取得し、前記交差領域の外郭線毎に、該外郭線と他の外郭線または前記所定範囲の外郭線との交点を検出することに基づき、前記無線通信可能範囲が互いに重複する無線装置の組の集合を取得する
請求項１ないし１０のいずれか一項に記載の情報処理方法。
【請求項１２】
前記基地局の設置可能範囲の外郭線が、ある平面内の円または多角形であり、
前記交差領域の外郭線が、円または多角形である
請求項１１に記載の情報処理方法。
【請求項１３】
前記基地局の設置可能範囲の外郭線が、ある平面内の任意の形で、
前記交差領域の外郭線が、任意の形である
請求項１１に記載の情報処理方法。
【請求項１４】
前記基地局の設置可能範囲は、線内の所定範囲であり、
前記集合取得ステップは、前記所定範囲の線分の全部または一部を共通に前記無線通信可能範囲内に含む無線装置の組の集合を取得する
請求項１ないし１０のいずれか一項に記載の情報処理方法。
【請求項１５】
基地局の設置可能範囲、および無線通信可能範囲が前記基地局の設置可能範囲と少なくとも一部重複する複数の無線装置のそれぞれの前記無線通信可能範囲の情報とを取得する範囲取得部と、
前記基地局の設置可能範囲において前記無線通信可能範囲が互いに重複する無線装置の組の集合を、前記集合に前記複数の無線装置のそれぞれが少なくとも１つ含まれるように、かつ前記集合の要素数および前記組の要素数の少なくとも一方に関する条件を満たすように、取得する集合取得部と、
を備える情報処理装置。
【請求項１６】
基地局の設置可能範囲、および無線通信可能範囲が前記基地局の設置可能範囲と少なくとも一部重複する複数の無線装置のそれぞれの前記無線通信可能範囲の情報とを取得する範囲取得ステップと、
前記基地局の設置可能範囲において前記無線通信可能範囲が互いに重複する無線装置の組の集合を、前記集合に前記複数の無線装置のそれぞれが少なくとも１つ含まれるように、かつ前記集合の要素数および前記組の要素数の少なくとも一方に関する条件を満たすように、取得する集合取得ステップと、
をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、情報処理方法、情報処理装置及びプログラムに関する。
【背景技術】
【０００２】
基地局と無線通信可能な複数の無線装置が存在する通信システムにおいて、全ての無線装置が少なくとも一台の基地局と無線で通信できるように基地局の配置を工夫することが行われている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】A. Molina, G.E. AthanaＳ４adou, A.R. Nix. “The automatic location of base-stations for optimizedcellular coverage: A new combinatorial approach”. Vehicular Technology Conference, 1999 IEEE 49th
【非特許文献２】C. F. Huang and Y. C. Tseng. The coverage problem in wireless sensor network. Mobile networks and applications. Volume 10, Issue 4, pp. 519 - 528, 2005
【非特許文献３】Z. Ya. A new algorithm for polygon intersection operation. ICCEE 2009
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、基地局が配置可能な位置の数が無数にある場合、全ての無線装置が少なくとも一つの基地局と無線通信できるように、基地局の配置を自動的に決定する方法が存在しなかった。そのため、基地局が配置可能な位置の数が無数にある場合、全ての無線装置が少なくとも一台の基地局と無線で通信できるようにするには、試行錯誤が必要である。そのため、基地局の配置を決める際の効率が悪いという問題があった。
【０００５】
そこで本発明の一態様は、上記問題に鑑みてなされたものであり、基地局の設置可能な位置の数が多くても、基地局の配置を決める際の効率を向上させる情報処理方法、情報処理装置及びプログラムを提供することを課題とする。
【課題を解決するための手段】
【０００６】
本発明の実施形態の情報処理方法は、範囲取得ステップにおいて、基地局の設置可能範囲、および無線通信可能範囲が前記基地局の設置可能範囲と少なくとも一部重複する複数の無線装置のそれぞれの上記無線通信可能範囲の情報を取得する。次に、集合取得ステップにおいて、上記基地局の設置可能範囲において上記無線通信可能範囲が互いに重複する無線装置の組の集合を、上記集合に上記複数の無線装置のそれぞれが少なくとも１つ含まれるように、かつ上記集合の要素数および上記組の要素数の少なくとも一方に関する条件を満たすように、取得する。
【図面の簡単な説明】
【０００７】
【図１】第１の実施形態における情報処置装置１の構成を示す概略ブロック図である。
【図２】第１の実施形態における無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図３】第１の実施形態における情報処置装置１の処理の流れの一例を示すフローチャートである。
【図４】第２の実施形態において、ある平面上における無線装置の無線通信範囲について説明するための図である。
【図５】第２の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図６】第２の実施形態における情報処理装置１ｂの構成を示す概略ブロック図である。
【図７】第２の実施形態において、一つの円のうち他の円に含まれる弧について説明するための図である。
【図８】第２の実施形態における弧の範囲の特定方法を説明するための図である。
【図９】第２の実施形態における情報処置装置１ｂの処理の流れの一例を示すフローチャートである。
【図１０】図９のステップＳ２０３の詳細な処理の流れの一例を示すフローチャートである。
【図１１】第３の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図１２】第３の実施形態における情報処理装置１ｃの構成を示す概略ブロック図である。
【図１３】第３の実施形態における情報処置装置１ｃの処理の流れの一例を示すフローチャートである。
【図１４】第４の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図１５Ａ】第４の実施形態における情報処理装置１ｄの構成を示す概略ブロック図である。
【図１５Ｂ】第４の実施形態において多角形Ｓｉが多角形Ｓｊに含まれる一例を示す図である。
【図１６】第４の実施形態における多角形の重複領域を示す一例である。
【図１７】第４の実施形態における交点の相対位置について説明するための図である。
【図１８】第４の実施形態における情報処置装置１ｄの処理の流れの一例を示すフローチャートである。
【図１９】第５の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図２０】第５の実施形態における情報処理装置１ｅの構成を示す概略ブロック図である。
【図２１】第５の実施形態における情報処置装置１ｅの処理の流れの一例を示すフローチャートである。
【図２２】第６の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図２３Ａ】第６の実施形態における、弧が内側か否かの判定処理を説明するための図である。
【図２３Ｂ】第６の実施形態において多角形が円を含む一例を示す図である。
【図２３Ｃ】第７の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図２３Ｄ】第７の実施形態における情報処理装置１ｅの処理部の流れの一例を示すフローチャートである。
【図２４】第８の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図２５】第８の実施形態における情報処理装置１ｆの構成を示す概略ブロック図である。
【図２６】第８の実施形態における情報処置装置１ｆの処理の流れの一例を示すフローチャートである。
【図２７】第９の実施形態における直線内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。
【図２８】第９の実施形態における情報処理装置１ｇの構成を示す概略ブロック図である。
【図２９】第９の実施形態における情報処置装置１ｇの処理の流れの一例を示すフローチャートである。
【図３０】第１０の実施形態における情報処理装置１ｈの構成を示す概略ブロック図である。
【図３１】第１０の実施形態における情報処置装置１ｈの処理の流れの一例を示すフローチャートである。
【発明を実施するための形態】
【０００８】
以下、本発明の実施形態について、図面を参照して詳細に説明する。各実施形態において、情報処理装置は、通信システムにおける基地局の数が最小になる各基地局の配置領域を決定する。ここで、配置領域は、２次元の領域だけでなく、一つの位置の場合もある。また、通信システムは、無線で通信可能な複数の無線装置と、無線で通信可能な一つ以上の基地局とを具備する。通信システムは、近距離無線通信及び携帯電話の通信を含む。近距離無線通信は、例えば、無線ＬＡＮまたはＺｉｇｂｅｅ（登録商標）である。
【０００９】
各実施形態において、一例として、各無線装置の位置は固定であり、一例として、各無線装置の通信可能範囲は既知であることを前提とする。各実施形態において、一例として、無線装置はセンサと無線通信部を備える。センサは、一例として、自然現象や人工物の機械的性質、電磁気的性質、熱的性質、音響的性質、化学的性質あるいはそれらで示される空間情報または時間情報を、別媒体の信号に置き換える。無線通信部は、一例として、センサが置き換えた信号を無線で基地局に送信する。
【００１０】
なお、無線装置は、無線送信と無線受信の少なくともいずれかを実行する無線通信部を備えていればよい。例えば、無線装置が無線送信しかしない場合、無線通信可能範囲は、無線送信可能範囲である。一方、無線装置が送信と受信の両方をする場合は、無線通信可能範囲は、無線で送信も受信もできる範囲である。
【００１１】
基地局は、近距離無線通信における基地局及び長距離無線通信における基地局を含む。近距離無線通信における基地局は、例えば、無線ＬＡＮのアクセスポイントまたはＺｉｇｂｅｅ（登録商標） Ｒｏｕｔｅｒである。長距離無線通信における基地局は、例えば、携帯電話の通信システムにおける基地局である。また、一例として、基地局を基地局配置可能範囲内でどこに設置したとしても、基地局の通信範囲は、一例として、無線装置を包含する。なお、基地局配置可能範囲は、物理的に基地局が設置可能な範囲であり、基地局の通信範囲とは関係ない。
【００１２】
（第１の実施形態）
図１は、第１の実施形態における情報処置装置１の構成を示す概略ブロック図である。情報処置装置１は、記憶部２及び処理部３を備える。
【００１３】
記憶部２には、基地局の設置可能範囲を示す情報が予め記憶されている。また記憶部２には、複数の無線装置の無線通信可能範囲を示す情報が予め記憶されている。具体的には、例えば、複数の無線装置の無線通信可能範囲が何らかの方法で取得され、取得された複数の無線装置の無線通信可能範囲を示す情報が予め記憶部２に記憶されている。
【００１４】
処理部３は、範囲取得部３１、集合取得部３２及び配置決定部３３を備える。
【００１５】
範囲取得部３１は、基地局の設置可能範囲、および無線通信可能範囲が上記基地局の設置可能範囲と少なくとも一部重複する複数の無線装置のそれぞれの無線通信可能範囲の情報を取得する。具体的には、例えば、範囲取得部３１は、複数の無線装置の無線通信可能範囲を示す情報及び基地局の設置可能範囲を示す情報を記憶部２から読み出す。これにより、範囲取得部３１は、複数の無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。範囲取得部３１は、取得した複数の無線装置の無線通信可能範囲及び基地局の設置可能範囲を集合取得部３２へ出力する。
【００１６】
集合取得部３２は、基地局の設置可能範囲において上記無線通信可能範囲が互いに重複する無線装置の組の集合を、上記集合に上記複数の無線装置のそれぞれが少なくとも１つ含まれるように、かつ上記集合の要素数および前記組の要素数の少なくとも一方に関する条件を満たすように、取得する。その際、集合取得部３２は、例えば、上記集合の要素数に関する条件として、上記集合に含まれる組数が最小、一定値以下、または所定の範囲内になるように、上記無線装置の組の集合を取得してもよい。また、集合取得部３２は、例えば、上記組の要素数に関する条件として、上記無線通信可能範囲が最も多くまたは一定数以上交差する領域を上記無線通信可能範囲内に含む無線通信の組を含むように、上記無線装置の組の集合を取得してもよい。
【００１７】
具体的には、例えば、集合取得部３２は、以下の処理を行うことで、無線装置の組の集合を取得してもよい。集合取得部３２は、例えば、無線装置それぞれの無線通信可能範囲の重複範囲と基地局の設置可能範囲との複数の重複領域それぞれについて、当該重複領域で無線通信可能な無線装置の組を取得する。これにより、無線装置の組の集合が取得される。そして、集合取得部３２は、例えば、コンピュータグラフィックを用いて、上記無線通信可能範囲及び上記設置可能範囲を図形で表す。そして、集合取得部３２は、例えば、１画素毎に複数の図形に含まれるか否か判定することで、複数の重複領域を抽出する。そして、集合取得部３２は、例えば、複数の重複領域それぞれを構成する図形の組を取得し、取得した複数の図形の組に対応する無線装置の組の集合を取得する。
【００１８】
集合取得部３２は、例えば、取得した複数の無線装置の組に基づいて、通信システムに含まれる上記複数の無線装置それぞれが少なくとも一つ以上の基地局と無線通信可能であるという条件を満たしつつ基地局の数が最小となる無線装置の組を取得する。具体的には、例えば、配置決定部３３は、集合取得部３２が取得した複数の無線装置の組から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。そして、集合取得部３２は、取得した無線装置の組を示す情報を配置決定部３３へ出力する。
【００１９】
配置決定部３３は、集合取得部３２が取得した集合に含まれる上記無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域に基地局を配置することを決定する。
【００２０】
具体的には、例えば、配置決定部３３は、最適化アルゴリズム（例えば、ｇｒｅｅｄｙアルゴリズム）を用いて、基地局の配置領域を決定する。なお、配置決定部３３は、例えば、非特許文献１に記載されたアルゴリズムを用いて、基地局の配置領域を決定してもよい。
配置決定部３３は、例えば、抽出した基地局の配置領域を示す情報を記憶部２に記憶させる。これにより、人は、記憶部２に記憶された配置決定部３３が抽出した基地局の配置領域に基地局を設置することができる。
【００２１】
図２は、第１の実施形態における無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。基地局の設置可能範囲ＲＢが示されている。点Ｐ１１〜Ｐ１７は、それぞれ第１の無線装置〜第７の無線装置の位置を表す。多角形または円形Ｓ１〜Ｓ７は、それぞれ各無線装置の無線通信可能範囲を表す。このように、無線通信可能範囲の形は任意の形である。
【００２２】
領域Ｄ１は、第１の無線装置の無線通信可能範囲及び第２の無線装置の無線通信可能範囲の重複範囲と、基地局の設置可能範囲ＲＢとの重複領域である。領域Ｄ２は、第２の無線装置の無線通信可能範囲及び第３の無線装置の無線通信可能範囲の重複範囲と、基地局の設置可能範囲ＲＢとの重複領域である。領域Ｄ３は、第４の無線装置の無線通信可能範囲及び第５の無線装置の無線通信可能範囲の重複範囲と、基地局の設置可能範囲ＲＢとの重複領域である。領域Ｄ４は、第５の無線装置の無線通信可能範囲、第６の無線装置の無線通信可能範囲及び第７の無線装置の無線通信可能範囲の重複範囲と、基地局の設置可能範囲ＲＢとの重複領域である。
【００２３】
図２の例では、集合取得部３２は、例えば、領域Ｄ１〜Ｄ４を取得する。その際、一例として、集合取得部３２は、領域Ｄ１〜Ｄ４のそれぞれについて、その重複領域で無線通信可能な無線装置の組を取得する。具体的には、集合取得部３２は、例えば、領域Ｄ１について、第１の無線装置と第２の無線装置の組を取得する。領域Ｄ１において、第１の無線装置及び第２の無線装置が無線通信可能であるからである。
【００２４】
また、集合取得部３２は、例えば、領域Ｄ２について、第２の無線装置と第３の無線装置の組を取得する。領域Ｄ２は、第２の無線装置及び第３の無線装置が無線通信可能であるからである。また、例えば、集合取得部３２は、領域Ｄ３について、第４の無線装置と第５の無線装置の組を取得する。領域Ｄ３は、第４の無線装置及び第５の無線装置が無線通信可能であるからである。また、例えば、集合取得部３２は、領域Ｄ４について、第５の無線装置と第６の無線装置と第７の無線装置の組を取得する。領域Ｄ４において、第５の無線装置、第６の無線装置及び第７の無線装置が無線通信可能であるからである。
【００２５】
＜集合取得部３２と配置決定部３３の処理の詳細＞
図２の例を用いて、集合取得部３２と配置決定部３３の処理の一例について説明する。例えば、第１の無線装置〜第７の無線装置をそれぞれＵ１〜Ｕ７と表す。集合取得部３２は、例えば、領域Ｄ１で通信可能な無線装置の組として、｛Ｕ１，Ｕ２｝を取得する。集合取得部３２は、例えば、領域Ｄ２で通信可能な無線装置の組として、｛Ｕ２，Ｕ３｝を取得する。集合取得部３２は、例えば、領域Ｄ３で通信可能な無線装置の組として、｛Ｕ４，Ｕ５｝を取得する。集合取得部３２は、例えば、領域Ｄ４で通信可能な無線装置の組として、｛Ｕ５，Ｕ６，Ｕ７｝を取得する。これにより、重複領域が特定される無線装置の組として、｛Ｕ１，Ｕ２｝，｛Ｕ２，Ｕ３｝，｛Ｕ４，Ｕ５｝，｛Ｕ５，Ｕ６，Ｕ７｝が取得される。
【００２６】
図２の例において、配置決定部３３は、ｇｒｅｅｄｙアルゴリズムを用いて、以下のように基地局の配置領域を決定する。配置決定部３３は、例えば、集合取得部３２が取得した｛Ｕ１，Ｕ２｝，｛Ｕ２，Ｕ３｝，｛Ｕ４，Ｕ５｝及び｛Ｕ５，Ｕ６，Ｕ７｝から最も要素の数が多い｛Ｕ５，Ｕ６，Ｕ７｝を求める対象の集合Ｇの要素として加える。そして、｛Ｕ５，Ｕ６，Ｕ７｝に含まれるＵ５の要素を｛Ｕ４，Ｕ５｝から仮に削除する。これにより、残った組は、｛Ｕ１，Ｕ２｝，｛Ｕ２，Ｕ３｝，｛Ｕ４｝となる。
【００２７】
配置決定部３３は、残った組のうち最も要素の数が多い｛Ｕ１，Ｕ２｝及び｛Ｕ２，Ｕ３｝から一例として、｛Ｕ１，Ｕ２｝を対象の集合Ｇの要素として加える。そして、｛Ｕ１，Ｕ２｝に含まれるＵ２の要素を｛Ｕ２，Ｕ３｝から仮に削除する。これにより、残った組は、｛Ｕ３｝，｛Ｕ４｝となる。配置決定部３３は、残った組のうち最も要素の数が多い｛Ｕ３｝及び｛Ｕ４｝から一例として、｛Ｕ３｝の元の組｛Ｕ２，Ｕ３｝を対象の集合Ｇの要素として加える。これにより、残った｛Ｕ４｝にはＵ３の要素がないので｛Ｕ４｝が残る。よって、配置決定部３３は、残った｛Ｕ４｝の元の組｛Ｕ４，Ｕ５｝を対象の集合Ｇの要素として加える。これにより、対象の集合ＧはＧ＝｛｛Ｕ１，Ｕ２｝，｛Ｕ２，Ｕ３｝，｛Ｕ４，Ｕ５｝，｛Ｕ５，Ｕ６，Ｕ７｝｝となる。
【００２８】
そして、配置決定部３３は、例えば、対象の集合Ｇの各要素によって特定される重複領域を、基地局の配置領域として抽出する。具体的には、配置決定部３３は、例えば、｛Ｕ１，Ｕ２｝によって特定される重複領域Ｄ１を基地局の配置領域として抽出する。また配置決定部３３は、例えば、｛Ｕ２，Ｕ３｝によって特定される重複領域Ｄ２を基地局の配置領域として抽出する。また配置決定部３３は、例えば、｛Ｕ４，Ｕ５｝によって特定される重複領域Ｄ３を基地局の配置領域として抽出する。また配置決定部３３は、例えば、｛Ｕ５，Ｕ６，Ｕ７｝によって特定される重複領域Ｄ４を基地局の配置領域として抽出する。
【００２９】
図３は、第１の実施形態における情報処置装置１の処理の流れの一例を示すフローチャートである。
（ステップＳ１０１）まず、範囲取得部３１は、無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。
（ステップＳ１０２）次に、集合取得部３２は、無線装置それぞれの無線通信可能範囲の重複範囲と基地局の設置可能範囲との複数の重複領域のそれぞれについて、その重複領域で無線通信可能な無線装置の組の集合を取得する。
【００３０】
（ステップＳ１０３）次に、集合取得部３２は、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
（ステップＳ１０４）次に、配置決定部３３は、集合取得部３２が抽出した集合に含まれる上記無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域に基地局を配置することを決定する。
【００３１】
以上、第１の実施形態において、情報処置装置１は、基地局の設置可能範囲が２次元領域であっても、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の数が最小となる場合の各基地局の配置領域を決定することができる。これにより、情報処置装置１は、基地局の設置可能な位置の数が多くても、基地局の数が最小となる基地局の配置を決める際の効率を向上させることができる。また、情報処置装置１は、基地局の数をなるべく減らすことができるので、コストを低減することができる。また、情報処置装置１は、自動的に、基地局の数を最小にする基地局の配置領域を決定することができるので、人の労力を削減し、その処理にかかる時間を短縮することができる。
【００３２】
なお、第１の実施形態では、基地局配置可能範囲が２次元領域の場合の例について説明したが、基地局配置可能範囲は、３次元領域であってもよい。また、第１の実施形態では、無線装置の無線通信可能範囲が２次元領域の場合の例について説明したが、無線装置の無線通信可能範囲は、３次元領域であってもよい。
【００３３】
基地局配置可能範囲が３次元領域で、かつ各無線装置の無線通信可能範囲が３次元領域である場合、集合取得部３２は、例えば、以下の処理を行ってもよい。集合取得部３２は、３次元空間上で、無線装置それぞれの無線通信可能範囲の重複範囲と基地局の設置可能範囲との複数の重複領域のそれぞれについて、その重複領域で無線通信可能な無線装置の組を取得してもよい。これにより、情報処置装置１は、基地局の設置可能範囲が３次元領域でかつ各無線装置の無線通信可能範囲が３次元領域であっても、基地局の個数を最小にする基地局の配置領域を決定することができる。
【００３４】
また、基地局配置可能範囲が２次元領域で、かつ各無線装置の無線通信可能範囲が３次元領域である場合、集合取得部３２は、例えば、以下の処理を行ってもよい。集合取得部３２は、基地局配置可能範囲を含む平面と、無線装置の無線通信可能範囲と、が交わる２次元上の領域を、その平面上における無線装置の無線通信可能範囲として抽出してもよい。集合取得部３２は、この処理を全ての無線装置の無線通信可能範囲について実施してもよい。そして、集合取得部３２は、例えば、無線装置それぞれについての上記平面上における無線通信可能範囲の重複範囲と基地局の設置可能範囲との複数の重複領域のそれぞれについて、その重複領域で無線通信可能な無線装置の組を取得してもよい。これにより、情報処置装置１は、基地局の設置可能範囲が２次元領域でかつ各無線装置の無線通信可能範囲が３次元領域であっても、基地局の個数を最小にする基地局の配置領域を決定することができる。
【００３５】
また、基地局配置可能範囲が３次元領域で、かつ各無線装置の無線通信可能範囲が同じ平面内で互いに異なる２次元領域である場合、集合取得部３２は、例えば、以下の処理を行ってもよい。集合取得部３２は、各無線装置の無線通信可能範囲を含む平面と、基地局配置可能範囲と、が交わる２次元上の領域を、その平面上における基地局配置可能範囲として抽出してもよい。そして、集合取得部３２は、例えば、無線装置それぞれの無線通信可能範囲の重複範囲と上記平面上における基地局の設置可能範囲との複数の重複領域のそれぞれについて、その重複領域で無線通信可能な無線装置の組を取得してもよい。これにより、情報処置装置１は、基地局の設置可能範囲が３次元領域でかつ各無線装置の無線通信可能範囲が２次元領域であっても、基地局の個数を最小にする基地局の配置領域を決定することができる。
【００３６】
なお、人が、本実施形態の情報処理装置１の各処理を行ってもよい。例えば、人が、複数の無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得してもよい。その場合、人が、範囲取得部３１における処理を以下のように行ってもよい。まず、人が、例えば、無線装置の無線通信可能な最大距離を実験または無線装置の特徴に従って求める。そして、人が、例えば、無線装置の位置を中心にして、求めた無線通信可能な最大距離を半径にする球を無線通信可能範囲にしてもよい。また別の例として、人は、例えば、実験を行って、無線通信可能範囲を求め、求めた無線通信可能範囲を図形として取得してもよい。
【００３７】
また、人が、無線装置それぞれの無線通信可能範囲の重複範囲と基地局の設置可能範囲との複数の重複領域それぞれについて、当該重複領域で無線通信可能な無線装置の組の集合を取得してもよい。
【００３８】
また、人が、上記無線装置の組の集合に基づいて、上記集合に含まれる無線装置それぞれが少なくとも一つ以上の基地局と無線通信可能であるという条件を満たしつつ基地局の数が最小となる場合の無線装置の組の集合を取得してもよい。具体的には、人は、例えば、取得された複数の上記無線装置の組から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。そして、人は、例えば、取得した集合に含まれる上記無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域に基地局を配置することを決定してもよい。
【００３９】
これにより、人は、基地局の設置可能な範囲が、領域として与えられたとしても、基地局の個数を最小にする基地局の配置領域の集合を求めることができる。これにより、基地局の設置可能な位置の数が多くても、基地局の数が最小となる基地局の配置を決める際の効率を向上させることができる。
【００４０】
（第２の実施形態）
続いて、第２の実施形態について説明する。第２の実施形態では、基地局の設置可能範囲が平面内の所定の範囲であり、かつ複数の無線装置の通信可能範囲と上記平面との交差領域が全て円である場合を想定する。なお、無線装置が平面上に置かれている必要は無く、台の上など平面から離れて配置されていても構わないが、無線装置の無線通信可能範囲と上記平面との交差領域が円であることを前提とする。ここで、円は、新円だけでなく楕円であってもよい。
【００４１】
図４は、第２の実施形態において、ある平面上における無線装置の無線通信範囲について説明するための図である。同図において、無線装置の設置位置Ｍ２０と無線通信可能な最大距離Ｌ２０が示されている。無線装置の無線通信可能範囲は、無線装置の設置位置Ｍ２０を中心として、無線通信可能な最大距離Ｌ２０を半径とする球内である。円Ｓ２０は、無線装置の無線通信可能範囲と平面Ｈ２０とが交わる円である。点Ｐ２０は、無線装置の設置位置Ｍ２０から平面Ｈ２０に下した垂線と平面Ｈ２０とが交わる点である。
【００４２】
図５は、第２の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。同図において、各無線装置の設置位置から基地局の設置可能範囲ＲＢ２を含む平面への垂線が交わる点Ｐ２１〜Ｐ２７が示されている。また、同図において、基地局の設置可能範囲ＲＢ２と各無線通信可能範囲とが交わる円Ｓ２１〜Ｓ２７が示されている。また、同図において、基地局の設置可能範囲ＲＢ２が示されている。各無線通信可能範囲は球内である。円Ｓ２１〜Ｓ２７は、各無線通信可能範囲と、基地局の設置可能範囲ＲＢ２との交差領域の外郭線である。
【００４３】
図５に示すように、本実施形態では、一例として、基地局の設置可能範囲ＲＢ２が、基地局の設置可能範囲ＲＢ２と各無線通信可能範囲とが交わる円Ｓ２１〜Ｓ２７を空間的に含むことを前提とする。
【００４４】
第２の実施形態では、一例として、各無線装置における無線通信可能範囲が各無線装置の位置を中心とする球内である。予め各無線装置における各無線装置の位置（すなわち球の中心位置）及び通信可能最大距離（すなわち球の半径）が得られている。そして、例えば、球の中心位置と球の半径と基地局の設置可能範囲を含む平面の式とを用いて、基地局の設置可能範囲と複数の無線通信可能範囲とが交わる複数の円の中心位置と半径とが予め計算されて得られている。
【００４５】
第２の実施形態における情報処理装置１ｂは、基地局の設置可能範囲と複数の無線通信可能範囲とが交わる複数の円の中心と半径に基づいて、全ての無線装置が少なくとも一つの基地局と無線通信できるという条件の下で、基地局の数が最小となる際の各基地局の設置座標を算出する。
【００４６】
図６は、第２の実施形態における情報処理装置１ｂの構成を示す概略ブロック図である。なお、図１と共通する要素には同一の符号を付し、その具体的な説明を省略する。第２の実施形態における情報処理装置１ｂの構成は、第１の実施形態における情報処理装置１の構成に対して、記憶部２が記憶部２ｂに、処理部３が処理部３ｂに変更され、入力部４が追加されたものになっている。また、第２の実施形態における処理部３ｂの構成は、第１の実施形態における処理部３の構成に対して、範囲取得部３１が範囲取得部３１ｂに、集合取得部３２が集合取得部３２ｂに変更されたものになっている。
【００４７】
記憶部２ｂには、基地局の設置可能範囲を示す情報が記憶されている。
入力部４は、基地局の設置可能範囲と複数の無線通信可能範囲との交差領域の外郭線である円の中心座標と半径の複数の組の入力を受け付け、受け付けた複数の組に関する情報を範囲取得部３１へ出力する。
【００４８】
範囲取得部３１ｂは、記憶部２ｂから基地局の設置可能範囲を示す情報を読み出すことで、基地局の設置可能範囲を取得する。また、範囲取得部３１ｂは、入力部４から出力された情報を受け取ることで、複数の無線装置の無線通信可能範囲を取得する。範囲取得部３１ｂは、例えば、円ごとにその円を識別する円識別番号を付し、円識別番号、円の中心座標及び半径を関連付けて記憶部２ｂに記憶させる。これにより、範囲取得部３１ｂは、基地局の設置可能範囲、および無線通信可能範囲が上記基地局の設置可能範囲と少なくとも一部重複する複数の無線装置のそれぞれの無線通信可能範囲の情報を取得する。
【００４９】
集合取得部３２ｂは、無線装置の無線通信可能範囲と上記平面内の所定範囲との交差領域が互いに重複する無線装置の組の集合を取得する。例えば、集合取得部３２ｂは、複数の無線装置に対して上記無線通信可能範囲の外郭線が互いに交差する無線装置を検出することに基づき、無線通信可能範囲が互いに重複する無線装置の組を検出する。具体的には、例えば、集合取得部３２ｂは、無線装置の通信可能範囲と上記所定の範囲との交差領域の外郭線（ここでは一例として、円）同士の複数の交点を該外郭線毎に抽出する。そして、集合取得部３２ｂは、例えば、外郭線毎に、抽出した複数の交点を含む複数の外郭線に対応する無線装置の組を取得する。
【００５０】
具体的には、例えば、集合取得部３２ｂは、複数の円それぞれについて、当該円のうち、他の円に含まれる弧の始点と終点を全て抽出する。そして、例えば、集合取得部３２ｂは、抽出した弧の始点と終点毎に、当該始点と終点を含む複数の外郭線（ここでは一例として、二つの円）に対応する無線装置の組を取得する。この処理の詳細は、後述する。
【００５１】
集合取得部３２ｂは、例えば、重複領域に含まれる一点の位置を記憶部２ｂに記憶させる。具体的には、例えば、集合取得部３２ｂは、抽出した弧に含まれる一点の位置と円の中心座標を結んだ直線と、ｘ軸とのなす角度を記憶部２ｂに記憶させる。これにより、人は、記憶部２ｂに記憶された角度を参照することで、上記一点の位置に、基地局を設置することができる。
【００５２】
図７及び図８を用いて、集合取得部３２ｂによる弧の抽出処理の一例について説明する。図７は、第２の実施形態において、一つの円のうち他の円に含まれる弧について説明するための図である。同図において、基地局の設置可能範囲と各無線通信可能範囲とが交わる円Ｓ１、Ｓ２、Ｓ３、Ｓ４及びＳ５が示されている。円Ｓ１〜Ｓ５に対応する第１の無線装置〜第５の無線装置をそれぞれＵ１〜Ｕ５と表す。また、円Ｓ４のうち円Ｓ１に含まれる弧Ａ１、円Ｓ４のうち円Ｓ２に含まれる弧Ａ２、円Ｓ４のうち円Ｓ３に含まれる弧Ａ３及び円Ｓ４のうち円Ｓ５に含まれる弧Ａ５が示されている。
【００５３】
図８は、第２の実施形態における弧の範囲の特定方法を説明するための図である。同図において、円Ｓｉのうち円Ｓｊに含まれる弧が示されている。また、当該弧を円Ｓｉの中心位置Ｐｉを中心に左回りで描いた場合の始点の位置と円Ｓｉの中心位置Ｐｉとを結ぶ直線がｘ軸となす角度αｊ，Ｌが示されている。また、当該弧を円Ｓｉの中心位置Ｐｉを中心に左回りで描いた場合の終点の位置と円Ｓｉの中心位置Ｐｉとを結ぶ直線がｘ軸となす角度αｊ，Ｒが示されている。このように、円Ｓｉのうち円Ｓｊに含まれる弧は、角度αｊ，Ｌと角度αｊ，Ｒで特定される。角度αｊ，Ｌ及び角度αｊ，Ｒは、一例として０から２πの範囲である。
【００５４】
図７の例において、集合取得部３２ｂは、例えば、弧Ａ１、Ａ２、Ａ３及びＡ５を抽出する。以下、円Ｓ４の中心位置を中心に左回りで弧を描く場合の始点と終点とを用いて説明する。具体的には、例えば、集合取得部３２ｂは、円Ｓ４の中心座標と半径の組及び円Ｓ１の中心座標と半径の組に基づいて、ｘ軸と円Ｓ４の交点から弧Ａ１の始点まで左回りで回転した角度α１，Ｌを算出し、ｘ軸と円Ｓ４の交点から弧Ａ１の終点まで左回りで回転した角度α１，Ｒを算出する。
【００５５】
また、例えば、集合取得部３２ｂは、円Ｓ４の中心座標と半径の組及び円Ｓ２の中心座標と半径の組に基づいて、ｘ軸と円Ｓ４の交点から弧Ａ２の始点まで左回りで回転した角度α２，Ｌを算出し、ｘ軸と円Ｓ４の交点から弧Ａ２の終点まで左回りで回転した角度α２，Ｒを算出する。
【００５６】
また、例えば、集合取得部３２ｂは、円Ｓ４の中心座標と半径の組及び円Ｓ３の中心座標と半径の組に基づいて、ｘ軸と円Ｓ４の交点から弧Ａ３の始点まで左回りで回転した角度α３，Ｌを算出し、ｘ軸と円Ｓ４の交点から弧Ａ３の終点まで左回りで回転した角度α３，Ｒを算出する。
【００５７】
また、例えば、集合取得部３２ｂは、円Ｓ４の中心座標と半径の組及び円Ｓ５の中心座標と半径の組に基づいて、ｘ軸と円Ｓ４の交点から弧Ａ５の始点まで左回りで回転した角度α５，Ｌを算出し、ｘ軸と円Ｓ４の交点から弧Ａ５の終点まで左回りで回転した角度α５，Ｒを算出する。
【００５８】
図９は、第２の実施形態における情報処置装置１ｂの処理の流れの一例を示すフローチャートである。
（ステップＳ２０１）まず、範囲取得部３１ｂは、無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。
（ステップＳ２０２）次に、集合取得部３２ｂは、複数の円それぞれについて、当該円のうち、他の円に含まれる弧の始点と終点を抽出する。
【００５９】
（ステップＳ２０３）次に、集合取得部３２ｂは、抽出した弧の始点と終点毎に、当該始点と終点を含む二つの円に対応する無線装置の組を取得する。
（ステップＳ２０４）次に、集合取得部３２ｂは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
【００６０】
（ステップＳ２０５）次に、配置決定部３３ｂは、抽出された無線装置の組の集合から、基地局の配置位置を決定する。具体的には、例えば、配置決定部３３ｂは、各無線装置の無線通信可能範囲の外郭線の交差部に上記基地局を配置することを決定する。
【００６１】
図１０は、図９のステップＳ２０３の詳細な処理の流れの一例を示すフローチャートである。図７の例を用いて、本フローチャートの処理を説明する。ここで、Ｓｉの円周のうちＳｊに含まれる円弧の範囲を、［αｊ，Ｌ、αｊ，Ｒ］と定義する。
（ステップＳ３０１）まず、集合取得部３２ｂは、インデックスｉ（ｉは正の整数）を初期化する。図７の例では、集合取得部３２ｂは、インデックスｉを１に初期化する。
【００６２】
（ステップＳ３０２）次に、集合取得部３２ｂは、Ｓｉについて先に抽出された弧を包含する全てのＳｊ（ｊはｉ以外の正の整数）に対し、αｊ，Ｌ＞αｊ，Ｒならば、［αｊ，Ｌ，αｊ，Ｒ］を［αｊ，Ｌ，αｊ，Ｒ＝２π］と［αｊ，Ｌ＝０，αｊ，Ｒ］に置き換える。図７の例で、インデックスｉが４の場合、集合取得部３２ｂは、円Ｓ４に含まれる弧を表す角度の組のうち、［α２，Ｌ，α２，Ｒ］を［α２，Ｌ，α２，Ｒ＝２π］，［α２，Ｌ＝０，α２，Ｒ］に置き換え、［α３，Ｌ，α３，Ｒ］を［α３，Ｌ，α３，Ｒ＝２π］と［α３，Ｌ＝０，α３，Ｒ］に置き換える。
【００６３】
そして、集合取得部３２ｂは、全ての角度αｊ，Ｌ、αｊ，Ｒを昇順にリストＬに格納する。図７の例では、角度の組は、［α１，Ｌ，α１，Ｒ］、［α２，Ｌ，α２，Ｒ＝２π］、［α２，Ｌ＝０，α２，Ｒ］、［α３，Ｌ，α３，Ｒ＝２π］、［α３，Ｌ＝０，α３，Ｒ］、［α５，Ｌ，α５，Ｒ］である。そのため、それらの角度を昇順に並べると、リストＬは、｛α２，Ｌ＝０，α３，Ｌ＝０，α３，Ｒ，α２，Ｒ，α１，Ｌ，α１，Ｒ，α５，Ｌ，α５，Ｒ，α３，Ｌ，α２，Ｌ，α２，Ｒ＝２π，α３，Ｒ＝２π｝である。
【００６４】
次に、集合取得部３２ｂは、αｊ，Ｌ＝αｊ’，Ｒ’を満たすｊ及びｊ’があれば、リストＬにおいて、αｊ，Ｌをαｊ’，Ｒ’の前に移動する。これは、三つ以上の円が一点で交わる点のときに、その三つ以上の円の組が抽出されるようにするためである。次に、集合取得部３２ｂは、円の集合Ｖを初期化して、Ｖ＝｛Ｓｉ｝とする。
【００６５】
（ステップＳ３０３）次に、集合取得部３２ｂは、リストＬの一番左の要素を読み出す。図７の例では、集合取得部３２ｂは、α２，Ｌ＝０を読み出す。
（ステップＳ３０４）次に、集合取得部３２ｂは、読み出した要素が、弧を向かって左回りで描いた場合の始点の位置と円Ｓｉの中心位置とを結ぶ直線がｘ軸となす角度αｊ，Ｌであるか否か判定する。角度αｊ，Ｌである場合（ＹＥＳ）、ステップＳ３０５に進む。一方、角度αｊ，Ｌでない場合（ＮＯ）、ステップＳ３０６に進む。
【００６６】
（ステップＳ３０５）集合取得部３２ｂは、Ｓｊを集合Ｖに追加する。そして、集合取得部３２ｂは、フラグ（ｆｌａｇ）を１に設定する。
（ステップＳ３０６）集合取得部３２ｂは、フラグ（ｆｌａｇ）が１ならば集合Ｖを求める集合Ｗｉの要素に追加する。そして、集合取得部３２ｂは、角度αｊ，Ｒを円識別番号としてのインデックスｊと集合Ｖとに関連付けて記憶部２ｂに記憶させる。角度αｊ，Ｒは、基地局を設置する位置を特定する情報である。次に、フラグ（ｆｌａｇ）の値に関係なく、集合取得部３２ｂは、集合ＶからＳｊを取り除き、フラグ（ｆｌａｇ）を０に設定する。
【００６７】
（ステップＳ３０７）次に、集合取得部３２ｂは、リストＬの次の要素があるか否か判定する。リストＬの次の要素がある場合（ＹＥＳ）、集合取得部３２ｂは、ステップＳ３０８に進む。リストＬの次の要素がない場合（ＮＯ）、集合取得部３２ｂは、ステップＳ３０９に進む。
（ステップＳ３０８）次に、集合取得部３２ｂは、リストＬの次の要素を読み出し、ステップＳ３０４に戻る。
【００６８】
（ステップＳ３０９）次に、集合取得部３２ｂは、全てのＳｉについて処理したか否か判定する。全てのＳｉについて処理した場合（ＹＥＳ）、集合取得部３２ｂは、ステップＳ３１１に進む。全てのＳｉについて処理していない場合（ＮＯ）、集合取得部３２ｂは、ステップＳ３１０に進む。
（ステップＳ３１０）次に、集合取得部３２ｂは、インデックスｉに１を加算し、ステップＳ３０２に戻る。
（ステップＳ３１１）次に、集合取得部３２ｂは、求めた円の組の集合Ｗｉの全てを、無線装置の組の集合一つに変換する。
【００６９】
ステップＳ３０３〜Ｓ３０８の処理について、図７の円Ｓ４の例を用いて説明する。図７の例で、インデックスが４の場合、リストＬは、｛α２，Ｌ＝０，α３，Ｌ＝０，α３，Ｒ，α２，Ｒ，α１，Ｌ，α１，Ｒ，α５，Ｌ，α５，Ｒ，α３，Ｌ，α２，Ｌ，α２，Ｒ＝２π，α３，Ｒ＝２π｝である。
【００７０】
まず、ステップＳ３０３で、要素α２，Ｌ＝０が読み出される。ステップＳ３０４で、要素α２，Ｌ＝０は要素αｊ，Ｌに該当するので、ステップＳ３０５に進む。ステップＳ３０５で、Ｓ２が集合Ｖに加えられて、集合Ｖが｛Ｓ４，Ｓ２｝となる。またフラグが１に設定される。
【００７１】
次に、ステップＳ３０８で、要素α３，Ｌ＝０が読み出される。ステップＳ３０４で、要素α３，Ｌ＝０は要素αｊ，Ｌに該当するので、ステップＳ３０５に進む。ステップＳ３０５で、Ｓ３が集合Ｖに加えられて、集合Ｖが｛Ｓ４，Ｓ２，Ｓ３｝となる。またフラグが１に再度設定される。
【００７２】
次に、ステップＳ３０８で、要素α３，Ｒが読み出される。ステップＳ３０４で、要素α３，Ｒは要素αｊ，Ｌに該当しないので、ステップＳ３０６に進む。ステップＳ３０６で、現在のフラグが１なので、集合Ｖ＝｛Ｓ４，Ｓ２，Ｓ３｝が集合Ｗ４の要素に加えられて、集合Ｗ４が｛｛Ｓ４，Ｓ２，Ｓ３｝｝となる。次に、角度α３，Ｒがインデックス３と集合Ｖ＝｛Ｓ４，Ｓ２，Ｓ３｝に関連付けられて記憶部２ｂに記憶される。集合ＶからＳ３が取り除かれ、集合Ｖが｛Ｓ４，Ｓ２｝となる。またフラグが０に設定される。
【００７３】
次に、ステップＳ３０８で、要素α２，Ｒが読み出される。ステップＳ３０４で、要素α２，Ｒは要素αｊ，Ｌに該当しないので、ステップＳ３０６に進む。ステップＳ３０６で、現在のフラグが０なので、集合ＶからＳ２が取り除かれ、集合Ｖが｛Ｓ４｝となる。またフラグが０に設定される。
【００７４】
次に、ステップＳ３０８で、要素α１，Ｌが読み出される。ステップＳ３０４で、要素α１，Ｌは要素αｊ，Ｌに該当するので、ステップＳ３０５に進む。ステップＳ３０５で、Ｓ１が集合Ｖに加えられて、集合Ｖが｛Ｓ４，Ｓ１｝となる。またフラグが１に設定される。
【００７５】
次に、ステップＳ３０８で、要素α１，Ｒが読み出される。ステップＳ３０４で、要素α１，Ｒは要素αｊ，Ｌに該当しないので、ステップＳ３０６に進む。ステップＳ３０６で、現在のフラグが１なので、集合Ｖ＝｛Ｓ４，Ｓ１｝が集合Ｗ４の要素に加えられて、集合Ｗ４が｛｛Ｓ４，Ｓ２，Ｓ３｝，｛Ｓ４，Ｓ１｝｝となる。次に、角度α１，Ｒがインデックス１と集合Ｖ＝｛Ｓ４，Ｓ１｝に関連付けられて記憶部２ｂに記憶される。集合ＶからＳ１が取り除かれ、集合Ｖが｛Ｓ４｝となる。またフラグが０に設定される。
【００７６】
次に、ステップＳ３０８で、要素α５，Ｌが読み出される。ステップＳ３０４で、要素α５，Ｌは要素αｊ，Ｌに該当するので、ステップＳ３０５に進む。ステップＳ３０５で、Ｓ５が集合Ｖに加えられて、集合Ｖが｛Ｓ４，Ｓ５｝となる。またフラグが１に設定される。
【００７７】
次に、ステップＳ３０８で、要素α５，Ｒが読み出される。ステップＳ３０４で、要素α５，Ｒは要素αｊ，Ｌに該当しないので、ステップＳ３０６に進む。ステップＳ３０６で、現在のフラグが１なので、集合Ｖ＝｛Ｓ４，Ｓ５｝が集合Ｗ４の要素に加えられて、集合Ｗ４が｛｛Ｓ４，Ｓ２，Ｓ３｝，｛Ｓ４，Ｓ１｝，｛Ｓ４，Ｓ５｝｝となる。次に、角度α５，Ｒがインデックス５と集合Ｖ＝｛Ｓ４，Ｓ５｝に関連付けられて記憶部２ｂに記憶される。集合ＶからＳ５が取り除かれ、集合Ｖが｛Ｓ４｝となる。またフラグが０に設定される。
【００７８】
次に、ステップＳ３０８で、要素α３，Ｌが読み出される。ステップＳ３０４で、要素α３，Ｌは要素αｊ，Ｌに該当するので、ステップＳ３０５に進む。ステップＳ３０５で、Ｓ３が集合Ｖに加えられて、集合Ｖが｛Ｓ４，Ｓ３｝となる。またフラグが１に設定される。
【００７９】
次に、ステップＳ３０８で、要素α２，Ｌが読み出される。ステップＳ３０４で、要素α２，Ｌは要素αｊ，Ｌに該当するので、ステップＳ３０５に進む。ステップＳ３０５で、Ｓ２が集合Ｖに加えられて、集合Ｖが｛Ｓ４，Ｓ３，Ｓ２｝となる。またフラグが１に再度設定される。
【００８０】
次に、ステップＳ３０８で、要素α２，Ｒ＝２πが読み出される。ステップＳ３０４で、要素α２，Ｒ＝２πは要素αｊ，Ｌに該当しないので、ステップＳ３０６に進む。ステップＳ３０６で、現在のフラグが１なので、集合Ｖ＝｛Ｓ４，Ｓ３，Ｓ２｝が集合Ｗ４の要素に加えられて、集合Ｗ４が｛｛Ｓ４，Ｓ２，Ｓ３｝，｛Ｓ４，Ｓ１｝，｛Ｓ４，Ｓ５｝，｛Ｓ４，Ｓ３，Ｓ２｝｝となる。次に、角度α２，Ｒがインデックス２と集合Ｖ＝｛Ｓ４，Ｓ３，Ｓ２｝に関連付けられて記憶部２ｂに記憶される。集合ＶからＳ２が取り除かれ、集合Ｖが｛Ｓ４，Ｓ３｝となる。またフラグが０に設定される。
【００８１】
次に、ステップＳ３０８で、要素α３，Ｒ＝２πが読み出される。ステップＳ３０４で、要素α３，Ｒ＝２πは要素αｊ，Ｌに該当しないので、ステップＳ３０６に進む。ステップＳ３０６で、集合ＶからＳ３が取り除かれ、集合Ｖが｛Ｓ４｝となる。またフラグが０に設定される。
【００８２】
これにより、図７の例で、インデックスが４の場合すなわち円Ｓ４の場合、集合Ｗ４＝｛｛Ｓ４，Ｓ２，Ｓ３｝，｛Ｓ４，Ｓ１｝，｛Ｓ４，Ｓ５｝，｛Ｓ４，Ｓ３，Ｓ２｝｝が
得られる。
【００８３】
ステップＳ３１１の処理について、図７の例を用いて説明する。図７の例では、ステップＳ３１１の処理の直前までで、Ｗ１＝｛｛Ｓ１，Ｓ４｝｝、Ｗ２＝｛｛Ｓ２，Ｓ４，Ｓ３｝｝、Ｗ３＝｛Ｓ３，Ｓ２，Ｓ４｝、Ｗ４＝｛｛Ｓ４，Ｓ２，Ｓ３｝，｛Ｓ４，Ｓ１｝，｛Ｓ４，Ｓ５｝，｛Ｓ４，Ｓ３，Ｓ２｝｝、Ｗ５＝｛｛Ｓ５，Ｓ１｝｝である。よって、集合Ｗ１〜Ｗ５の全てに対応する無線装置の組は、｛｛Ｕ１，Ｕ４｝，｛Ｕ２，Ｕ４，Ｕ３｝｝，｛Ｕ３，Ｕ２，Ｕ４｝，｛Ｕ４，Ｕ２，Ｕ３｝，｛Ｕ４，Ｕ１｝，｛Ｕ４，Ｕ５｝，｛Ｕ４，Ｕ３，Ｕ２｝，｛Ｕ５，Ｕ１｝｝である。
【００８４】
図９のステップＳ２０４で、配置決定部３３は、上記無線装置の組に対して、例えば、ｇｒｅｅｄｙアルゴリズムを用いて、無線装置の組を絞り込む。そして、配置決定部３３は、例えば、絞り込んだ無線装置の組に対応する角度及び円識別番号を記憶部２ｂから読み出す。この読み出された角度によって特定される位置が、基地局が設置される位置である。配置決定部３３は、例えば、読み出した円の識別番号に対応する円の中心位置及び円の半径を記憶部２ｂから読み出す。
【００８５】
配置決定部３３は、例えば、読み出した角度、円の中心位置及び円の半径を用いて、その円の円周とｘ軸が交わる点から読み出した角度だけ左回りに回転した上記円周上の位置を基地局配置位置として算出する。そして、配置決定部３３は、例えば、算出した基地局配置位置を示す基地局配置位置情報を記憶部２ｂに記憶させる。これにより、ユーザは、基地局配置位置情報を参照することで、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の数が最小になるように基地局を配置することができる。
【００８６】
以上により、第２の実施形態における情報処理装置１ｂにおいて、集合取得部３２ｂは、例えば、複数の円それぞれについて、当該円のうち、他の円に含まれる弧の始点と終点を全て抽出する。そして、集合取得部３２ｂは、抽出した弧の始点と終点の組毎に、当該始点と終点を含む二つの円に対応する無線装置の組を取得する。そして、配置決定部３３は、集合取得部３２ｂが抽出した複数の無線装置の組に基づいて、基地局の配置領域を決定する。
【００８７】
これにより、第１の実施形態の効果に加えて、第２の実施形態における情報処理装置１ｂは、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の数が最小になる際の基地局の配置領域を決定することができる。
【００８８】
なお、集合取得部３２ｂは、無線装置の無線通信可能範囲と上記平面内の所定範囲との交差領域（本実施形態の例では、円内の領域）を求め、上記交差領域が互いに重複する無線装置の組の集合を取得してもよい。
【００８９】
また、集合取得部３２ｂは、上記複数の無線装置のうち他の無線装置と無線通信可能範囲が重複しない第１無線装置が存在する場合は、第１無線装置以外の無線装置のそれぞれが少なくとも１つ含まれるように、上記無線装置の組の集合を取得してもよい。その場合、配置決定部３３は、集合取得部３２ｂが取得した集合に含まれ上記無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域、及び上記第１無線装置の無線通信可能範囲と上記設置可能範囲との重複領域に基地局を配置することを決定してもよい。
【００９０】
その際、配置決定部３３は、各無線装置の無線通信可能範囲の外郭線の交差部に上記基地局を配置することを決定してもよい。
【００９１】
（第３の実施形態）
続いて、第３の実施形態について説明する。第３の実施形態では、基地局の設置可能範囲がある平面内の円（以下、第１の円という）であり、複数の無線装置の通信可能範囲と上記平面との交差領域の外郭線が円（以下、第２の円という）である場合を想定する。
【００９２】
図１１は、第３の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。同図において、各無線装置の無線通信可能範囲と平面Ｈ３との交差領域の外郭線である円Ｓ３１〜Ｓ３７が示されている。また、基地局の設置可能範囲と平面Ｈ５との交差領域の外郭線である円Ｓ３８及び円Ｓ３９が示されている。
【００９３】
図１２は、第３の実施形態における情報処理装置１ｃの構成を示す概略ブロック図である。なお、図６と共通する要素には同一の符号を付し、その具体的な説明を省略する。第３の実施形態における情報処理装置１ｃの構成は、第２の実施形態における情報処理装置１ｂの構成に対して、処理部３ｂが処理部３ｃに変更されたものになっている。より詳細には、第３の実施形態における処理部３ｃの構成は、第２の実施形態における処理部３ｂの構成に対して、集合取得部３２ｂが集合取得部３２ｃに変更されたものになっている。
【００９４】
集合取得部３２ｃは、複数の第２の円それぞれについて、当該第２の円のうち、第１の円または他の第２の円に含まれる弧の始点と終点を全て抽出する。また、集合取得部３２ｃは、第１の円それぞれについて、当該第１の円のうち、第２の円に含まれる弧の始点と終点を全て抽出する。
【００９５】
集合取得部３２ｃは、抽出した弧の始点と終点の組毎に、当該始点と終点を含む複数の円に対応する複数の無線装置及び基地局のうち少なくとも二つを含む組を取得する。図１２の例を用いて、集合取得部３２ｃのこの処理の一例を説明する。
【００９６】
集合取得部３２ｃは、例えば、まず図１０のステップＳ３０１で、インデックスｉを３１に初期化して、図１０のフローチャートの処理を円Ｓ３１〜Ｓ３６について行う。その後、更に、集合取得部３２ｃは、例えば、図１０のフローチャートの処理を基地局の設置可能範囲を示す円Ｓ３８及び円Ｓ３９について順次行う。これにより、上記弧により特定される重複領域で無線通信可能な複数の無線装置、及び基地局のうち少なくとも二つを含む組が、複数取得される。
【００９７】
ここで、基地局配置可能範囲の外郭線を表す円Ｓ３８及び円Ｓ３９だけでなく、円Ｓ３１〜Ｓ３６、円Ｓ３８及び円Ｓ３９の全ての円周について処理をする理由は、例えば、円Ｓ３８の中に完全に円Ｓ３１が含まれてしまうと、円Ｓ３８と円Ｓ３１との交点がないので、集合取得部３２ｃが、円Ｓ３８と円Ｓ３１の重複領域を抽出できないからである。
【００９８】
そして、集合取得部３２ｃは、取得した組の集合のうち基地局を含む組だけを上記集合に残す。図１２の例では、集合取得部３２ｃは、取得した全ての組を含む集合を生成し、生成した集合に含まれる組のうち円Ｓ３８または円Ｓ３９を含む組だけを上記集合に残す。
【００９９】
図１３は、第３の実施形態における情報処置装置１ｃの処理の流れの一例を示すフローチャートである。
（ステップＳ４０１）まず、範囲取得部３１ｂは、無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。
（ステップＳ４０２）次に、集合取得部３２ｃは、第１の円それぞれについて、当該第１の円のうち、第２の円に含まれる弧の始点と終点を抽出する。
【０１００】
（ステップＳ４０３）次に、集合取得部３２ｃは、複数の第２の円それぞれについて、当該第２の円のうち、第１の円または他の第２の円に含まれる弧の始点と終点を全て抽出する。
（ステップＳ４０４）次に、集合取得部３２ｃは、抽出した弧の始点と終点の組毎に、当該始点と終点を含む複数の円に対応する、複数の無線装置及び基地局のうち少なくとも二つを含む組を取得する。そして、集合取得部３２ｃは、取得した複数の無線装置及び基地局のうち少なくとも二つを含む組全てを含む集合を生成する。
【０１０１】
（ステップＳ４０５）次に、集合取得部３２ｃは、取得した集合に含まれる組のうち基地局を含む組だけを上記集合に残す。
（ステップＳ４０６）次に、集合取得部３２ｃは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
（ステップＳ４０７）次に、配置決定部３３は、集合取得部３２ｃが抽出した集合に含まれる無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域に基地局を配置することを決定する。
【０１０２】
以上により、第３の実施形態における情報処理装置１ｃにおいて、集合取得部３２ｃは、複数の第２の円それぞれについて、当該第２の円のうち、第１の円または他の第２の円に含まれる弧の始点と終点を抽出する。また、集合取得部３２ｃは、第１の円それぞれについて、当該第１の円のうち、第２の円に含まれる弧の始点と終点を抽出する。そして、集合取得部３２ｃは、抽出した弧の始点と終点の組毎に、当該始点と終点を含む複数の円に対応する無線装置の組を取得する。そして、集合取得部３２ｃは、取得した複数の組のうち基地局を含む組だけを抽出する。次に、集合取得部３２ｃは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
【０１０３】
これにより、第１の実施形態の効果に加えて、第３の実施形態における情報処理装置１ｃは、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の設置可能範囲が平面上において円で表される領域の場合にも、基地局の数が最小になる際の基地局の配置領域を決定することができる。
【０１０４】
（第４の実施形態）
続いて、第４の実施形態について説明する。第４の実施形態では、基地局の設置可能範囲が平面上の所定の範囲（例えば、平面全体）であり、複数の無線装置の無線通信可能範囲と上記平面との交差領域の外郭線が全て多角形である場合を想定する。例えば、実験により、各無線装置の３次元の無線通信可能範囲が予め求められており、各無線装置の３次元の無線通信可能範囲と基地局が設置可能な平面との交差領域の外郭線である多角形それぞれにおける各頂点の座標が既知であることを前提とする。
【０１０５】
図１４は、第４の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。同図において、基地局の設置可能範囲Ｒ８４が示されている。また、各無線装置の無線通信可能範囲と基地局の設置可能範囲Ｒ８４との交差領域の外郭線である多角形Ｓ４１〜Ｓ４７が示されている。
【０１０６】
図１５Ａは、第４の実施形態における情報処理装置１ｄの構成を示す概略ブロック図である。なお、図６と共通する要素には同一の符号を付し、その具体的な説明を省略する。第４の実施形態における情報処理装置１ｄの構成は、第２の実施形態における情報処理装置１ｂの構成に対して、記憶部２ｂが記憶部２ｄに、処理部３ｂが処理部３ｄに変更されたものになっている。また、第４の実施形態における処理部３ｄの構成は、第２の実施形態における処理部３ｂの構成に対して、集合取得部３２ｂが集合取得部３２ｄに変更されたものになっている。
【０１０７】
記憶部３ｄは、第２の実施形態における記憶部３ｂと同様の機能を有するが、以下の点で異なる。記憶部３ｄには、各無線装置の３次元の無線通信可能範囲と基地局が設置可能な平面との交差領域の外郭線である多角形それぞれにおける各頂点の座標が予め記憶されている。
【０１０８】
集合取得部３２ｄは、複数の多角形それぞれについて、当該多角形と他の多角形との交点を複数抽出する。具体的には、例えば、集合取得部３２ｄは、無線通信可能範囲を表す多角形それぞれについて、非特許文献３のアルゴリズムを用いて、対象の多角形Ｓｉと他の多角形Ｓｊとの交点の座標を抽出する。
さらに、集合取得部３２ｄは、多角形Ｓｉと多角形Ｓｊとの交わる点がない場合に対し、多角形Ｓｉが多角形Ｓｊに含まれるかどうか確認する。図１５Ｂは、第４の実施形態において多角形Ｓｉが多角形Ｓｊに含まれる一例を示す図である。多角形Ｓｉが多角形Ｓｊに含まれるかどうか確認する処理の一例は、以下の通りである。集合取得部３２ｄは、多角形Ｓｉの任意の頂点Ｉを通る線を描き、多角形Ｓｊの辺との交点を求める。集合取得部３２ｄは、頂点Ｉよりｘ軸正の範囲及び頂点Ｉよりｘ軸負の範囲に交点の数が共に奇数であれば、多角形Ｓｉは多角形Ｓｊに含まれると判定する。逆に、集合取得部３２ｄは、頂点Ｉよりｘ軸正の範囲及び頂点Ｉよりｘ軸負の範囲に交点の数が共に偶数であれば、多角形Ｓｉは多角形Ｓｊに含まれないと判定する。
【０１０９】
集合取得部３２ｄは、例えば、後述する処理により、複数の交点それぞれを識別する交点識別番号を算出する。そして、集合取得部３２ｄは、例えば、交点識別番号が小さいものから順に二つの点数を取る毎に、それぞれを当該多角形が他の多角形に含まれる線の始点と終点に割り当てる。そして、集合取得部３２ｄは、例えば、図１０に示すアルゴリズムを用いて、始点と終点の組ごとに、当該始点と終点を含む図形の組に対応する、複数の無線装置の組及び基地局のうち少なくとも二つを含む組の集合を算出する。この例における図形は、多角形または円である。
【０１１０】
図１６は、第４の実施形態における多角形の重複領域を示す一例である。同図において、多角形Ｓｉの頂点には、順番に０から１１までの頂点識別番号が付されている。また、多角形Ｓｉと多角形Ｓｊの交点の交点識別番号として、αｊ，Ｌ＝０．ｘ、αｊ，Ｒ＝１．ｙが示されている。ただし、図１６のように交点の数が３以上の場合がある。この場合、集合取得部３２ｄは、全てのαｊ，Ｌとαｊ，Ｒを求める。また、多角形Ｓｉが多角形Ｓｊに含まれる場合、集合取得部３２ｄは、αｊ，Ｌ＝０、αｊ，Ｒ＝ｍとする。ここで、ｍは多角形Ｓｉの辺の数である。
【０１１１】
第２の実施形態では、円と円との交点の相対位置を円の中心の角度で表した。一方、第４の実施形態では同じ角度が二つ以上の点を表すこともあるため、多角形と多角形との交点の交点識別番号を、その交点が含まれる辺の両端の頂点からその交点までの距離の比を用いて表す。
【０１１２】
以下、多角形と多角形との交点の交点識別番号の表し方の一例を、図１６を用いて説明する。まず図１６に示すように、集合取得部３２ｄは、例えば、多角形Ｓｉの頂点に連続に頂点識別番号を振る。そして、集合取得部３２ｄは、例えば、交点が含まれる辺に含まれる第１の頂点から交点までの長さと、交点が含まれる辺に含まれる第２の頂点から交点までの長さとの比に従って、その交点の交点識別番号を決定する。
【０１１３】
図１７は、第４の実施形態における交点の交点識別番号について説明するための図である。例えば、交点Ｘが多角形Ｓｉの辺ＡＢにあることを仮定する。頂点Ａ、Ｂにそれぞれ番号ａ，ａ＋１が付けられている。辺ＡＢの長さが１だと仮定したときに、頂点Ａから交点Ｘまでの長さがｘの場合、点Ｘの交点識別番号はａ．ｘになる。
【０１１４】
集合取得部３２ｄは、例えば、以下の処理で、交点の交点識別番号を決定する。まず、集合取得部３２ｄは、例えば、辺でつながれた両頂点の座標から、その辺の長さを算出する。そして、集合取得部３２ｄは、例えば、頂点識別番号の小さい頂点から交点までの距離を算出する。そして、集合取得部３２ｄは、例えば、交点の交点識別番号（以下、点数ともいう）αを、「小さい方の頂点識別番号．（頂点識別番号の小さい頂点から交点までの距離／辺の長さ）」で表す。
【０１１５】
第２の実施形態と同様に、集合取得部３２ｄは、例えば、Ｓｊに含まれるＳｉの辺の範囲を［αｊ，Ｌ，αｊ，Ｒ］で表す。αｊ，Ｌ，αｊ，Ｒは交点の交点識別番号である。図１６のように、多角形と多角形の重複領域が二つ以上ある場合、集合取得部３２ｄは、例えば、全ての［αｊ，Ｌ，αｊ，Ｒ］を算出する。そして、集合取得部３２ｄは、例えば、第２の実施形態と同様に、図１０のフローチャートで示すアルゴリズムを用い、重複領域を構成する多角形の組を抽出する。
【０１１６】
図１８は、第４の実施形態における情報処置装置１ｄの処理の流れの一例を示すフローチャートである。
（ステップＳ５０１）まず、範囲取得部３１ｂは、無線装置の無線通信可能範囲及び
基地局の設置可能範囲を取得する。
（ステップＳ５０２）次に、集合取得部３２ｄは、複数の多角形それぞれについて、当該多角形と他の多角形との交点を複数抽出する。
【０１１７】
（ステップＳ５０３）次に、集合取得部３２ｄは、複数の多角形それぞれについて、抽出した複数の交点を含む多角形の組に対応する無線装置の組の集合を取得する。
（ステップＳ５０４）次に、集合取得部３２ｄは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
（ステップＳ５０５）次に、配置決定部３３は、集合取得部３２ｄが抽出した集合に含まれる上記無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域に基地局を配置することを決定する。
【０１１８】
以上、第４の実施形態の情報処置装置１ｄにおいて、集合取得部３２ｄは、複数の多角形それぞれについて、他の多角形との交点を抽出する。そして集合取得部３２ｄは、複数の多角形それぞれについて、抽出した複数の交点を含む多角形の組に対応する無線装置の組を取得する。そして、配置決定部３３は、集合取得部３２ｄが取得した複数の無線装置の組に基づいて、基地局の配置領域を決定する。
【０１１９】
これにより、第１の実施形態の効果に加えて、情報処置装置１ｄは、基地局が設置可能な平面において無線装置の通信可能範囲が多角形で表される場合でも、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で基地局の個数を最小にする基地局の配置領域を決定することができる。
【０１２０】
（第５の実施形態）
続いて、第５の実施形態について説明する。第５の実施形態では、基地局の設置可能範囲がある平面内の一つ以上の多角形（以下、第１の多角形という）であり、複数の無線装置の無線通信可能範囲と上記平面との交差領域の外郭線が全て多角形（以下、第２の多角形という）である場合を想定する。
【０１２１】
図１９は、第５の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。同図において、基地局の設置可能範囲の外郭線である多角形Ｓ５８及びＳ５９が示されている。また、平面Ｈ５と各無線通信可能範囲との交差領域の外郭線である多角形Ｓ５１〜Ｓ５７が示されている。
【０１２２】
図２０は、第５の実施形態における情報処理装置１ｅの構成を示す概略ブロック図である。なお、図１５Ａと共通する要素には同一の符号を付し、その具体的な説明を省略する。第５の実施形態における情報処理装置１ｅの構成は、第４の実施形態における情報処理装置１ｄの構成に対して、処理部３ｄが処理部３ｅに変更されたものになっている。また、第５の実施形態における処理部３ｅの構成は、第４の実施形態における処理部３ｄの構成に対して、集合取得部３２ｄが集合取得部３２ｅに変更されたものになっている。
【０１２３】
集合取得部３２ｅは、例えば、第１の多角形それぞれについて、当該第１の多角形に含まれる第２の多角形の線の始点と終点を全て抽出する。また、集合取得部３２ｅは、例えば、複数の第２の多角形それぞれについて、当該第２の多角形に含まれる第１の多角形の線の始点と終点、または当該第２の多角形に含まれる他の第２の多角形の線の始点と終点を全て抽出する。そして、集合取得部３２ｅは、例えば、抽出した始点と終点の組毎に、当該始点と終点を含む多角形の組に対応する、複数の無線装置及び基地局のうち少なくとも二つを含む組を取得する。集合取得部３２ｅは、例えば、取得した複数の組のうち基地局を含む組だけを抽出する。
【０１２４】
具体的には、例えば、集合取得部３２ｅは、第４の実施形態の集合取得部３２ｄと同様に、無線通信可能範囲を表す多角形と基地局設置可能範囲を表す多角形の重複領域を構成する多角形の組の集合を抽出する。そして、集合取得部３２ｅは、例えば、抽出した集合に含まれる多角形の組のうち、基地局設置可能範囲を表す多角形を含む組だけを抽出する。
【０１２５】
図２１は、第５の実施形態における情報処置装置１ｅの処理の流れの一例を示すフローチャートである。
（ステップＳ６０１）まず、範囲取得部３１ｂは、無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。
（ステップＳ６０２）次に、集合取得部３２ｅは、第１の多角形それぞれについて、当該第１の多角形に含まれる第２の多角形の線の始点と終点を全て抽出する。
【０１２６】
（ステップＳ６０３）次に、集合取得部３２ｅは、例えば、複数の第２の多角形それぞれについて、当該第２の多角形に含まれる第１の多角形の線の始点と終点、または当該第２の多角形に含まれる他の第２の多角形の線の始点と終点を全て抽出する。
（ステップＳ６０４）次に、集合取得部３２ｅは、抽出した始点と終点の組毎に、当該始点と終点を含む多角形の組に対応する、複数の無線装置及び基地局のうち少なくとも二つを含む組を取得する。そして、集合取得部３２ｅは、複数の無線装置及び基地局のうち少なくとも二つを含む組全てを含む集合を生成する。
【０１２７】
（ステップＳ６０５）次に、集合取得部３２ｅは、取得した集合に含まれる組のうち基地局を含む組だけを上記集合に残す。
（ステップＳ６０６）次に、集合取得部３２ｅは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
（ステップＳ６０７）次に、配置決定部３３は、集合取得部３２ｅが抽出した集合に含まれる上記無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域に基地局を配置することを決定する。
【０１２８】
これにより、第１の実施形態の効果に加えて、第５の実施形態における情報処理装置１ｅは、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の設置可能範囲が平面上において多角形で表される領域の場合にも、基地局の数が最小になる際の基地局の配置領域を決定することができる。
【０１２９】
（第６の実施形態）
続いて、第６の実施形態について説明する。第６の実施形態では、基地局の設置可能範囲の外郭線がある平面内の円または多角形であり、複数の無線装置の無線通信可能範囲と上記平面との交差領域の外郭線が円または多角形である場合を想定する。ここで、円は、新円だけでなく楕円も含む。第６の実施形態における情報処理装置１ｅは、第５の実施形態における情報処理装置１ｅの構成と同様であるので、その構成の説明を省略する。
【０１３０】
図２２は、第６の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。同図において、基地局の設置可能範囲の外郭線Ｓ９８〜Ｓ１００が示されている。また、平面Ｈ９と各無線通信可能範囲との交差領域の外郭線Ｓ９１〜Ｓ９７が示されている。
【０１３１】
集合取得部３２ｅは、第５の実施形態と同様に、例えば、各円について、当該円と他の円または多角形との重複部分を構成する円または多角形の組に対応する、複数の無線装置の組及び基地局のうち少なくとも二つを含む組を抽出する。また集合取得部３２ｅは、第５の実施形態と同様に、例えば、各多角形について、当該多角形と円または他の多角形との重複部分を構成する円または多角形の組に対応する、複数の無線装置の組及び基地局のうち少なくとも二つを含む組を抽出する。そして、集合取得部３２ｅは、例えば、抽出した組全てを含む集合を生成し、生成した集合に含まれる組のうち基地局を含む組だけを上記集合に残す。
【０１３２】
円については、集合取得部３２ｅは、第２の実施形態と同様に、例えば、各円について、当該円が他の円または多角形に含まれる弧の始点と終点の組を抽出する。そして、集合取得部３２ｅは、例えば、第２の実施形態で示した処理により、抽出した始点と終点の相対位置を角度で表す。そして、集合取得部３２ｅは、例えば、図１０に示すアルゴリズムを用いて、複数の無線装置の組及び基地局のうち少なくとも二つを含む組の集合を算出する。
【０１３３】
多角形については、集合取得部３２ｅは、第４の実施形態と同様の処理で、例えば、各多角形について、当該多角形と円または他の多角形との交点を複数抽出する。そして、集合取得部３２ｅは、例えば、第４の実施形態と同様の処理で、複数の交点それぞれを識別する交点識別番号を算出する。そして、集合取得部３２ｅは、例えば、交点識別番号が小さいものから順に二つの点数を取る毎に、当該多角形が円または他の多角形に含まれる線の始点と終点を割り当てる。そして、集合取得部３２ｅは、例えば、図１０に示すアルゴリズムを用いて、始点と終点の組ごとに、当該始点と終点を含む図形の組に対応する、複数の無線装置の組及び基地局のうち少なくとも二つを含む組を取得する。この例における図形は、多角形または円である。
【０１３４】
円と多角形が交わる場合に、弧が多角形の内側であるか否かの判定処理の一例について説明する。なお、弧が円の内側であるか否かの判定処理は同様であるので、その判定処理の説明は省略する。
まず、集合取得部３２ｅは、円と多角形の全ての交点を計算する。次に、集合取得部３２ｅは、逆時計回りにインデックスをつける。これにより、例えば、交点がＰ１、Ｐ２、…、Ｐｒ（ｒは１以上の整数）が得られる。交点Ｐｍ（ｍは１以上の整数）を始点とし、交点Ｐｎを終点とする弧を弧ＰｍＰｎとする。
【０１３５】
集合取得部３２ｅは、例えば、多角形に含まれる円の弧の始点と終点を抽出する際に、多角形と円の交点を抽出した後に、抽出した交点間の弧が多角形の内側であるか否か判定する。集合取得部３２ｅは、例えば、交点間の弧が多角形の内側である場合に、その交点の一つを始点として、もう一つの交点を終点として抽出する。以下、その判定処理の一例について図２３Ａを用いて説明する。
【０１３６】
図２３Ａは、第６の実施形態における、弧が内側か否かの判定処理を説明するための図である。同図において、点Ｏを中心とする円と、多角形とが示されている。また、その円とその多角形との交点Ｐ１、Ｐ２、Ｐ３、Ｐ４が示されている。また、弧Ｐ１Ｐ２上の点Ｉが示されている。同図において、弧Ｐ１Ｐ２は、多角形の内側であり、弧Ｐ２Ｐ３は、多角形の外側であり、弧Ｐ３Ｐ４は、多角形の内側である。
【０１３７】
図２３Ａの例において、集合取得部３２ｅは、例えば、弧Ｐ１Ｐ２上の任意の点Ｉを選択する。次に、集合取得部３２ｅは、例えば、点Ｏと点Ｉとを含む線と多角形との交点を算出する。直線のうち点Ｉからｙ軸正方向の範囲及び点Ｉからｙ軸負方向の範囲の交点の数が共に奇数であれば、集合取得部３２ｅは、弧Ｐ１Ｐ２は多角形の内側であると判定する。一方、直線のうち点Ｉからｙ軸正方向の範囲及び点Ｉからｙ軸負方向の範囲の交点の数が共に偶数であれば、集合取得部３２ｅは、弧Ｐ１Ｐ２は多角形の外側であると判定する。
【０１３８】
集合取得部３２ｅは、弧Ｐ１Ｐ２が多角形の内側であると判定した場合、例えば、弧Ｐ（２×ｑ＋１）Ｐ（２×ｑ＋２）が多角形の内側であると判定する（ｑは０以上の整数）。図２３Ａの例の場合、弧Ｐ１Ｐ２は多角形の内側であるので、集合取得部３２ｅは、弧Ｐ３Ｐ４も多角形の内側であると判定する。一方、集合取得部３２ｅは、弧Ｐ１Ｐ２が多角形の内側でないと判定した場合、例えば、弧Ｐ（２×ｑ＋２）Ｐ（２×ｑ＋３）が多角形の内側であると判定する。
【０１３９】
円と多角形との交点がない場合、集合取得部３２ｅは、円は多角形を含むか多角形は円に含むかどうか確認する。確認方法の一例は、以下の通りである。集合取得部３２ｅは、円の中心Ｏと多角形の任意の頂点との距離と、円の半径と比較する。半径の方が長い場合、集合取得部３２ｅは、円は多角形を含むと判定する。逆に半径の方が短い場合、集合取得部３２ｅは、中心Ｏを通る線を描き、多角形の辺との交点を求める。円の中心Ｏよりｘ軸正の範囲及び円の中心Ｏよりｘ軸負の範囲に交点の数が共に奇数であれば、多角形は円を含むと判定する。集合取得部３２ｅは、逆に円の中心Ｏよりｘ軸正の範囲及び円の中心Ｏよりｘ軸負の範囲に交点の数が共に偶数であれば多角形は円を含まないと判定する。
【０１４０】
図２３Ｂは第６の実施形態において多角形が円を含む一例を示す図である。
円Ｓｉが多角形Ｓｊに含まれる場合、集合取得部３２ｅは、αｊ、Ｌ＝０、αｊ、Ｒ＝２πとする。このようにすることで、例えば、無線通信可能範囲と上記平面との交差領域の外郭線が円Ｓｉと多角形Ｓｊである場合に、集合取得部３２ｅは、例えば、図１０のアルゴリズムを用いて、円Ｓｉと多角形Ｓｊに対応する無線装置の組を取得することができる。
多角形Ｓｉが円Ｓｊに含まれる場合、集合取得部３２ｅは、αｊ、Ｌ＝０、αｊ、Ｒ＝ｍとする。ｍは多角形Ｓｉの辺の数である。このようにすることで、例えば、無線通信可能範囲と上記平面との交差領域の外郭線が多角形Ｓｉと円Ｓｊである場合に、集合取得部３２ｅは、例えば、図１０のアルゴリズムを用いて、多角形Ｓｉと円Ｓｊに対応する無線装置の組を取得することができる。
【０１４１】
以上、第６の実施形態では、基地局の設置可能範囲の外郭線が平面内の円または多角形で、複数の無線装置の無線通信可能範囲と上記平面との交差領域の外郭線が円または多角形であるという前提である。第６の実施形態における情報処理装置１ｅは、第１の実施形態の効果に加えて、その前提においても、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の数が最小になる際の基地局の配置領域を決定することができる。
【０１４２】
（第７の実施形態）
続いて、第７の実施形態について説明する。第７の実施形態では、基地局の設置可能範囲の外郭線がある平面内の任意の形で、複数の無線装置の無線通信可能範囲と上記平面との交差領域の外郭線が任意の形である場合を想定する。ただし、任意の２つの外郭線の交点を求めることが可能であること、及び平面にある任意の点が基地局の設置可能範囲や無線装置の無線通信可能範囲に含まれるかどうか確認できることを仮定する。
【０１４３】
第７の実施形態における情報処理装置１ｅは、第５の実施形態における情報処理装置１ｅの構成と同様であるので、その構成の説明を省略する。図２３Ｃは、第７の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。同図において、無線装置Ｍ１〜Ｍ６の平面内の無線通信可能範囲の外郭線Ｓ１〜Ｓ６が示されている。また、基地局の設置可能範囲Ａ１及びＡ２が示されている。
【０１４４】
図２３Ｄは、第７の実施形態における情報処理装置１ｅの処理部の流れの一例を示すフローチャートである。
（ステップＳ６１１）まず、範囲取得部３１ｂは、無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。
【０１４５】
（ステップＳ６１２）次に、集合取得部３２ｅは、無線装置の無線通信可能範囲及び基地局の設置可能範囲の外郭線の交点を全て抽出する。集合取得部３２ｅは、他の外郭線との交点がない外郭線に対し、外郭線に囲まれる任意の一点を抽出する。例えば、図２３Ｃの例の場合、交点は×で表される。無線装置Ｍ６の通信可能範囲の外郭線Ｓ６は他の外郭線との交点がないため、集合取得部３２ｅは、外郭線に囲まれる一点を抽出する。その点を内点と呼ぶ。
【０１４６】
（ステップＳ６１３）次に、集合取得部３２ｅは、各交点及び内点を囲む外郭線を求める。そして、集合取得部３２ｅは、外郭線に対応する、複数の無線装置及び基地局のうち少なくても二つを含む組を取得する。ただし、点が外郭線の上にある場合に、集合取得部３２ｅは、その点は外郭線に囲まれているとみなす。例えば図２３Ｃの例の場合、集合取得部３２ｅは、交点Ｐ１は無線装置Ｍ１、Ｍ２、基地局設置可能範囲Ａ１の外郭線に囲まれているとみなす。このため、集合取得部３２ｅは、交点Ｐ１に対応する組｛Ｍ１、Ｍ２、Ａ１｝を抽出することができる。
【０１４７】
（ステップＳ６１４）次に、集合取得部３２ｅは、取得した集合に含まれる組のうち基地局を含む組だけを上記集合に残す。
（ステップＳ６１５）次に、集合取得部３２ｅは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
（ステップＳ６１６）次に、配置決定部３３は、集合取得部３２ｅが抽出した集合に含まれる上記無線装置の組に対応する交点または内点に基地局を配置することを決定する。
【０１４８】
これにより、第１の実施形態の効果に加えて、第７の実施形態における情報処理装置１ｅは、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の設置可能範囲が平面上において任意の形で表される領域の場合にも、基地局の数が最小になる際の基地局の配置領域を決定することができる。
【０１４９】
ただし、この第７の実施形態の処理を用いて、第２〜第６の実施形態で示す問題を解決できる。理由は、無線装置の通信可能範囲及び基地局の設置可能範囲の外郭線が円または多角形の場合、上記の処理を用いて、集合取得部３２ｅは、外郭線の交点を求めることが可能である。さらに、集合取得部３２ｅは、任意の点が外郭線に囲まれるかどうか確認できる。ある点が円に囲まれるかどうか確認する処理の一例は以下の通りである。集合取得部３２ｅは、点と円の中心との距離を円の半径と比較し、距離が半径以下であれば点は円に含まれると判定する。ある点が多角形に囲まれるかどうか確認する処理の一例は以下の通りである。集合取得部３２ｅは、点を通る線を描き、多角形との交点を抽出し、点の右側及び左側にある交点の数が双方とも奇数であれば点は多角形に含まれると判定する。
【０１５０】
（第８の実施形態）
続いて、第８の実施形態について説明する。第８の実施形態では、第２の実施形態に対して、基地局の設置可能範囲が複数の平面にある場合を想定する。ここで、基地局の設置可能範囲は、複数の平面内の所定の範囲（例えば、複数の平面全体）である。
【０１５１】
図２４は、第８の実施形態における平面内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。同図において、基地局の設置可能範囲ＲＢ６１及びＲＢ６２が示されている。第１の無線装置の無線通信可能範囲は、点Ｍ１を中心とする球内である。第２の無線装置の無線通信可能範囲は、点Ｍ２を中心とする球である。第３の無線装置の無線通信可能範囲は、点Ｍ３を中心とする球である。各無線装置の無線通信可能範囲と基地局の設置可能範囲ＲＢ６１との交差領域の外郭線である円Ｓ６１、Ｓ６２及びＳ６３が示されている。また、各無線装置の無線通信可能範囲と基地局の設置可能範囲ＲＢ６２との交差領域の外郭線である円Ｓ６４、Ｓ６５及びＳ６６が示されている。
【０１５２】
図２５は、第８の実施形態における情報処理装置１ｆの構成を示す概略ブロック図である。なお、図６と共通する要素には同一の符号を付し、その具体的な説明を省略する。第８の実施形態における情報処理装置１ｆの構成は、第２の実施形態における情報処理装置１ｂの構成に対して、処理部３ｂが処理部３ｆに変更されたものになっている。また、第８の実施形態における処理部３ｆの構成は、第２の実施形態における処理部３ｂの構成に対して、集合取得部３２ｂが集合取得部３２ｆに、配置決定部３３が配置決定部３３ｆに変更されたものになっている。
【０１５３】
集合取得部３２ｆは、複数の平面それぞれにおいて、複数の重複領域それぞれについて、当該重複領域で無線通信可能な無線装置の組を取得する。具体的には、集合取得部３２ｆは、例えば、複数の平面それぞれにおいて、当該平面に含まれる複数の円それぞれ毎に、当該円のうち、他の円に含まれる弧の始点と終点を抽出する。そして、集合取得部３２ｆは、例えば、抽出した弧の始点と終点毎に、当該始点と終点を含む二つの円に対応する無線装置の組を取得する。集合取得部３２ｆは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。そして、集合取得部３２ｆは、取得した無線装置の組の集合を示す情報を配置決定部３３へ出力する。
【０１５４】
図２６は、第８の実施形態における情報処置装置１ｆの処理の流れの一例を示すフローチャートである。
（ステップＳ７０１）まず、範囲取得部３１ｂは、無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。
（ステップＳ７０２）次に、集合取得部３２ｆは、複数の平面それぞれにおいて、当該平面に含まれる複数の円それぞれ毎に、当該円のうち、他の円に含まれる弧の始点と終点を全て抽出する。
【０１５５】
（ステップＳ７０３）次に、集合取得部３２ｆは、抽出した弧の始点と終点毎に、当該始点と終点を含む二つの円に対応する無線装置の組を取得する。
（ステップＳ７０４）次に、集合取得部３２ｆは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
（ステップＳ７０５）次に、配置決定部３３ｆは、集合取得部３２ｆが抽出した集合に含まれる上記無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域に基地局を配置することを決定する。
【０１５６】
以上、第１の実施形態の効果に加えて、第８の実施形態における情報処理装置１ｆは、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の設置可能範囲が複数の平面にある場合にも、基地局の数が最小になる際の基地局の配置領域を決定することができる。
【０１５７】
なお、本実施形態では、第２の実施形態において、基地局の設置可能な平面が複数ある場合について説明した。その代わりに、第３の実施形態、第４の実施形態または第５の実施形態において基地局の設置可能な平面が複数ある場合に、情報処理装置１ｆが、第６の実施形態における処理と同様の処理を行ってもよい。
【０１５８】
（第９の実施形態）
続いて、第９の実施形態について説明する。第９の実施形態では、予め決められた複数の線それぞれ内の所定の範囲である場合を想定する。
【０１５９】
図２７は、第９の実施形態における直線内の無線装置の無線通信可能範囲と基地局の設置可能範囲の一例を示す図である。同図において、同じ平面内に基地局の設置可能範囲を示す線分ＲＢ７１及び線分ＲＢ７２が示されている。線分ＲＢ７１には、座標の原点が含まれている。ここで、点Ｍ７１に位置する無線通信装置Ｕ７１の通信可能範囲は、点Ｍ７１を中心とする球内である。また、点Ｍ７２に位置する無線通信装置Ｕ７２の通信可能範囲は、点Ｍ７２を中心とする球内である。点Ｍ７１に位置する無線通信装置Ｕ７１の通信可能範囲に含まれる線分ＲＢ７１上の線分として、α１，Ｌ〜α１，Ｒまでの線分が示されている。また、点Ｍ７２に位置する無線通信装置Ｕ７２の通信可能範囲に含まれる線分ＲＢ７１上の線分として、α２，Ｌ〜α２，Ｒまでの線分が示されている。
【０１６０】
また、点Ｍ７１に位置する無線通信装置Ｕ７１の通信可能範囲に含まれる線分ＲＢ７２上の線分として、α１，Ｌ〜α１，Ｒまでの線分が示されている。また、点Ｍ７２に位置する無線通信装置Ｕ７２の通信可能範囲に含まれる線分ＲＢ７２上の線分として、α２，Ｌ〜α２，Ｒまでの線分が示されている。
【０１６１】
図２８は、第９の実施形態における情報処理装置１ｇの構成を示す概略ブロック図である。なお、図６と共通する要素には同一の符号を付し、その具体的な説明を省略する。第９の実施形態における情報処理装置１ｇの構成は、第２の実施形態における情報処理装置１ｂの構成に対して、処理部３ｂが処理部３ｇに変更されたものになっている。また、第９の実施形態における処理部３ｇの構成は、第２の実施形態における処理部３ｂの構成に対して、集合取得部３２ｂが集合取得部３２ｇに変更されたものになっている。
【０１６２】
一例として、基地局の設置可能範囲が含まれる複数の線のうち、一つの線に含まれる任意の点を原点として設定されている。例えば、入力部４が、複数の線それぞれにおける無線装置の無線通信可能範囲を表す情報の入力を受け付け、受け付けた入力を示す入力情報を範囲取得部３１ｂへ出力する。ここで、入力情報は、例えば、複数の線分それぞれの一端の座標と他端の座標である。
【０１６３】
範囲取得部３１ｂは、複数の線それぞれにおける無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。具体的には、例えば、範囲取得部３１ｂは、入力部４から複数の線分それぞれの一端の座標と他端の座標を、複数の線それぞれにおける無線装置の無線通信可能範囲として取得する。
【０１６４】
集合取得部３２ｇは、上記所定範囲の線分の全部または一部を共通に上記無線通信可能範囲内に含む無線装置の組の集合を取得する。具体的には、集合取得部３２ｇは、一例として、以下の処理を行う。集合取得部３２ｇは、例えば、ある無線装置Ｕｉ（ｉは正の整数）の通信可能範囲と基地局の設置可能範囲である線分ｊ（ｊは正の整数）との重複線分を［α（ｊ）ｉ，Ｌ，α（ｊ）ｉ，Ｒ］として表す。ここで、重複線分の一端が、α（ｊ）ｉ，Ｌで、他端がα（ｊ）ｉ，Ｒである。集合取得部３２ｇは、例えば、この処理を全ての無線装置について行う。
【０１６５】
図２７の例の場合、集合取得部３２ｇは、例えば、無線装置Ｕ７１の通信可能範囲と基地局の設置可能範囲である線分ＲＢ７１とが重複する線分を［α（１）１，Ｌ，α（１）１，Ｒ］と表す。図２７の例の場合、集合取得部３２ｇは、例えば、無線装置Ｕ７２の通信可能範囲と基地局の設置可能範囲である線分ＲＢ７１とが重複する線分を［α（１）２，Ｌ，α（１）２，Ｒ］と表す。
【０１６６】
また、図２７の例の場合、集合取得部３２ｇは、例えば、無線装置Ｕ７１の通信可能範囲と基地局の設置可能範囲である線分ＲＢ７２とが重複する線分を［α（２）１，Ｌ，α（２）１，Ｒ］と表す。図２７の例の場合、集合取得部３２ｇは、例えば、無線装置Ｕ７２の通信可能範囲と基地局の設置可能範囲である線分ＲＢ７２とが重複する線分を［α（２）２，Ｌ，α（２）２，Ｒ］と表す。
【０１６７】
そして、集合取得部３２ｇは、上記線分毎に、当該線分のうち無線装置の通信可能範囲に含まれる線分同士が重複する重複線分の範囲それぞれで無線通信可能な無線装置の組を抽出する。これにより、基地局の設置可能範囲である線毎に、無線装置の組が抽出される。図２７の例の場合、集合取得部３２ｇは、例えば、線分［α（１）１，Ｌ，α（１）１，Ｒ］と線分［α（１）２，Ｌ，α（１）２，Ｒ］が重複する重複線分［α（１）２，Ｌ，α（１）１，Ｒ］を構成する無線装置の組｛Ｕ７１，Ｕ７２｝を抽出する。また、図２７の例の場合、集合取得部３２ｇは、例えば、線分［α（２）１，Ｌ，α（２）１，Ｒ］と線分［α（２）２，Ｌ，α（２）２，Ｒ］が重複する重複線分［α（２）２，Ｌ，α（２）１，Ｒ］を構成する無線装置の組｛Ｕ７１，Ｕ７２｝を抽出する。
【０１６８】
集合取得部３２ｇは、例えば、抽出した無線装置の組全てを示す情報を配置決定部３３へ出力する。
配置決定部３３は、例えば、集合取得部３２ｇが生成した無線装置の組全てに基づいて、上記複数の無線装置それぞれが少なくとも一つ以上の基地局と無線通信可能であるという条件を満たしつつ基地局の数が最小となる場合の各基地局の配置領域を決定する。
【０１６９】
図２７の例の場合、配置決定部３３は、集合取得部３２ｇが無線装置の組｛Ｕ７１，Ｕ７２｝を重複して抽出したので、二つの無線装置の組｛Ｕ７１，Ｕ７２｝のうち一つを選択する。そして、配置決定部３３は、選択した無線装置の組｛Ｕ７１，Ｕ７２｝に対応する重複線分、すなわち重複線分［α（１）２，Ｌ，α（１）１，Ｒ］または重複線分［α（２）２，Ｌ，α（２）１，Ｒ］が、配置領域として抽出される。
【０１７０】
図２９は、第９の実施形態における情報処置装置１ｇの処理の流れの一例を示すフローチャートである。
（ステップＳ８０１）まず、範囲取得部３１ｂは、複数の線それぞれにおける無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。
（ステップＳ８０２）次に、集合取得部３２ｇは、基地局の設置可能範囲である線分毎に、当該線分における無線装置の通信範囲の重複範囲の一端の座標と他端の座標の組を抽出する。
【０１７１】
（ステップＳ８０３）次に、集合取得部３２ｇは、抽出した一端の座標と他端の座標の組ごとに、その一端の座標とその他端の座標を含む線分に対応する無線装置の組を取得する。
（ステップＳ８０４）次に、集合取得部３２ｇは、取得された上記無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
（ステップＳ８０５）次に、配置決定部３３は、集合取得部３２ｇが生成した無線装置の組全てに基づいて、通信システムに含まれる上記複数の無線装置それぞれが少なくとも一つ以上の基地局と無線通信可能であるという条件を満たしつつ基地局の数が最小となる場合の各基地局の配置領域を決定する。
【０１７２】
以上、第１の実施形態の効果に加えて、第９の実施形態における情報処理装置１ｇは、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局の設置可能範囲が線または線分である場合にも、基地局の数が最小になる際の基地局の配置領域を決定することができる。
【０１７３】
なお、本実施形態では、基地局の設置可能範囲が予め決められた複数の線それぞれ内の所定範囲としたが、これに限ったものではない。基地局の設置可能範囲が予め決められた線内の所定範囲であってもよい。
その場合、集合取得部３２ｇは、線内の所定範囲のうち無線装置の通信可能範囲に含まれる線分同士が重複する重複線分の範囲それぞれで無線通信可能な無線装置の組を抽出してもよい。
【０１７４】
（第１０の実施形態）
続いて、第１０の実施形態について説明する。第１０の実施形態では、第１の実施形態において、１台の基地局が通信できる無線装置の最大台数に制限がある場合を想定する。本実施系形態では、一例として、１台の基地局が最大ｋ台（ｋは正の整数）の無線装置としか通信できないという条件がある。ここで、整数ｋは１台の基地局が通信できる無線装置の最大台数（以下、単に最大台数という）である。
【０１７５】
図３０は、第１０の実施形態における情報処理装置１ｈの構成を示す概略ブロック図である。なお、図１と共通する要素には同一の符号を付し、その具体的な説明を省略する。第１０の実施形態における情報処理装置１ｈの構成は、第１の実施形態における情報処理装置１の構成に対して、処理部３が処理部３ｈに変更されたものになっている。また、第１０の実施形態における処理部３ｈの構成は、第１の実施形態における処理部３の構成に対して、集合取得部３２が集合取得部３２ｈに変更されたものになっている。
【０１７６】
第１０の実施形態の集合取得部３２ｈは、第１の実施形態における配置決定部３３と同様の機能を有するが、更に以下の機能を有する。集合取得部３２ｈは、上記組の要素数に関する条件として、上記無線装置の組に含まれる無線装置の台数が上限値以下になるように、上記無線装置の組の集合を取得する。ｓｐの際、一例として、集合取得部３２ｈは、以下の処理を行ってもよい。集合取得部３２ｈは、例えば、予め最大台数を保持する。集合取得部３２ｈは、例えば、取得した無線装置の集合に含まれる無線装置の組それぞれについて、当該無線装置の組に含まれる要素の数が最大台数より多いか否か判定する。当該要素の数が最大台数より多い場合、集合取得部３２ｈは、例えば、当該無線装置の組を要素の数が最大台数で互いに異なる無線装置の組に置き換える。
【０１７７】
その際、例えば、無線装置の組に含まれる要素の数がｍ（ｍは整数）であるとすると、集合取得部３２ｈは、例えば、当該無線装置の組を、要素の数がｋ個でＣ（ｍ，ｋ）（＝ｍ！／｛ｋ！（ｍ−ｋ）！｝）個の互いに異なる無線装置の組に置き換える。Ｃ（ｍ，ｋ）は、要素の数ｍ個の要素から最大台数ｋ個の要素を選択した場合のパターン数である。よって、この処理は、集合取得部３２ｈが最大台数ｋ個の要素を含む新しい複数の無線装置の組を設けたことに相当する。
【０１７８】
以下、この集合取得部３２ｈの処理を、具体例を挙げて説明する。例えば、最大台数ｋが３であり、集合取得部３２ｈが取得した無線装置の組の集合が｛｛Ｕ１，Ｕ２，Ｕ３，Ｕ４｝，｛Ｕ４，Ｕ５，Ｕ６｝｝であることを前提とする。｛Ｕ１，Ｕ２，Ｕ３，Ｕ４｝は要素の数が４であり、この要素の数が最大台数よりも大きい。よって、この例において、集合取得部３２ｈは、｛Ｕ１，Ｕ２，Ｕ３，Ｕ４｝を、要素の数が３で互いに異なる４（＝Ｃ（４，３））個の組に置き換える。
【０１７９】
これにより、｛Ｕ１，Ｕ２，Ｕ３，Ｕ４｝は｛Ｓ１，Ｓ２，Ｓ３｝，｛Ｓ１，Ｓ２，Ｓ４｝，｛Ｓ１，Ｓ３，Ｓ４｝，｛Ｓ２，Ｓ３，Ｓ４｝に置き換えられる。この置き換えの結果、無線装置の組｛｛Ｓ１，Ｓ２，Ｓ３，Ｓ４｝，｛Ｓ４，Ｓ５，Ｓ６｝｝は、無線装置の組｛｛Ｓ１，Ｓ２，Ｓ３｝，｛Ｓ１，Ｓ２，Ｓ４｝，｛Ｓ１，Ｓ３，Ｓ４｝，｛Ｓ２，Ｓ３，Ｓ４｝，｛Ｓ４，Ｓ５，Ｓ６｝｝となる。一方、要素の数ｍが最大台数ｋより大きくない場合、集合取得部３２ｈは、置き換えを行わない。
【０１８０】
配置決定部３３は、上述した処理後の複数の無線装置の組に基づいて、基地局の配置領域を決定する。上記の例の場合、配置決定部３３ｈは、無線装置の組｛｛Ｓ１，Ｓ２，Ｓ３｝，｛Ｓ１，Ｓ２，Ｓ４｝，｛Ｓ１，Ｓ３，Ｓ４｝，｛Ｓ２，Ｓ３，Ｓ４｝，｛Ｓ４，Ｓ５，Ｓ６｝｝に基づいて、基地局の配置領域を決定する。配置決定部３３の配置領域の抽出処理は、第１の実施形態における配置決定部３３の配置領域の抽出処理と同様であるので、その説明を省略する。
【０１８１】
図３１は、第１０の実施形態における情報処置装置１ｈの処理の流れの一例を示すフローチャートである。
（ステップＳ９０１）まず、範囲取得部３１は、無線装置の無線通信可能範囲及び基地局の設置可能範囲を取得する。
（ステップＳ９０２）次に、集合取得部３２ｈは、無線装置それぞれの無線通信可能範囲の重複範囲と基地局の設置可能範囲との複数の重複領域のそれぞれについて、その重複領域で無線通信可能な無線装置の組を取得する。
【０１８２】
（ステップＳ９０３）次に、集合取得部３２ｈは、集合取得部３２が取得した無線装置の組の集合に含まれる対象となる無線装置の組に含まれる要素の数が最大台数より多いか否か判定する。対象となる無線装置の組に含まれる要素の数が最大台数より多い場合（ＹＥＳ）、集合取得部３２ｈは、ステップＳ９０４に進む。一方、対象となる無線装置の組に含まれる要素の数が最大台数以下の場合（ＮＯ）、集合取得部３２ｈは、ステップＳ９０５に進む。
【０１８３】
（ステップＳ９０４）次に、集合取得部３２ｈは、対象となる無線装置の組を、要素の数がｋ個でＣ（ｍ，ｋ）個の互いに異なる無線装置の組に置き換える。
（ステップＳ９０５）次に、集合取得部３２ｈは、全ての無線装置の組について判定したか否か判定する。全ての無線装置の組について判定した場合（ＹＥＳ）、配置決定部３３ｈは、ステップＳ９０７へ進む。全ての無線装置の組について判定していない場合（ＮＯ）、集合取得部３２ｈは、ステップＳ９０６へ進む。
【０１８４】
（ステップＳ９０６）次に、集合取得部３２ｈは、対象とする無線装置の組を次の無線装置の組に切り替え、ステップＳ９０３に戻る。
（ステップＳ９０７）次に、集合取得部３２ｈは、ステップＳ９０３〜ステップＳ９０７の処理後の無線装置の組の集合から、各無線装置が少なくとも一つ含まれ、かつ集合内で無線装置の組の数が最小になる無線装置の組の集合を抽出する。
（ステップＳ９０８）次に、配置決定部３３は、集合取得部３２ｈが抽出した集合に含まれる無線装置の組を構成する各無線装置の無線通信可能範囲および上記設置可能範囲間の重複領域に基地局を配置することを決定する。
【０１８５】
以上、第１０の実施形態における情報処理装置１ｈにおいて、集合取得部３２ｈは、取得した複数の無線装置の組それぞれについて、当該無線装置の組に含まれる要素の数が上記最大台数より多いか否か判定する。そして、この要素の数が上記最大台数より多い場合、集合取得部３２ｈは、この無線装置の組を要素の数が最大台数で互いに異なる無線装置の組に置き換える。
【０１８６】
これにより、ある無線装置の組に含まれる要素の数が上記最大台数を超えていても、その無線装置の組は、要素の数が最大台数で互いに異なる無線装置の組に置き換えられる。そのため、配置決定部３３ｈで決定される各基地局の配置領域において、上記最大台数以下の無線装置が基地局と無線通信可能になる。そのため、情報処理装置１ｈは、各基地局の配置領域に基地局を配置された場合に、基地局と無線通信できない無線装置が出現しないようにすることができる。すなわち、各基地局の配置領域に基地局が配置された場合、無線装置は少なくとも一つの基地局と無線通信することができる。
【０１８７】
以上、第１の実施形態の効果に加えて、第１０の実施形態における情報処理装置１ｈは、各無線装置が少なくとも一つの基地局と無線通信可能であるという条件の下で、基地局と接続可能な無線装置の台数に制限があっても、基地局の数が最小になる際の基地局の配置領域を決定することができる。
【０１８８】
なお、本実施形態では、第１の実施形態において、１台の基地局が最大ｋ台（ｋは正の整数）の無線装置としか通信できないという条件がある場合を想定したが、これに限ったものではない。第２から７のいずれか一つの実施形態において、１台の基地局が最大ｋ台（ｋは正の整数）の無線装置としか通信できないという条件がある場合を想定してもよい。その場合も同様に、集合取得部３２ｈは、上述した処理と同様の処理を行うようにしてもよい。
【０１８９】
なお、第１の実施形態において、人が第１の実施形態の情報処理装置の各処理を行ってもよいと説明したのと同様に、人が第２〜第１０の実施形態の情報処理装置の各処理を行ってもよい。
また、基地局の設置可能範囲は、平面内の所定範囲である場合に、各実施形態における集合取得部は、無線装置毎の無線装置の無線通信可能範囲を記憶部から取得し、無線装置毎に、無線装置の無線通信可能範囲と上記平面との交差領域の外郭線を求めてもよい。
また、複数の装置を備えるシステムが、各実施形態の情報処理装置の各処理を、それらの複数の装置で分散して処理してもよい。
【０１９０】
また、各実施形態の情報処理装置の各処理を実行するためのプログラムをコンピュータ読み取り可能な記録媒体に記録して、当該記録媒体に記録されたプログラムをコンピュータシステムに読み込ませ、実行することにより、各実施形態の情報処理装置に係る上述した種々の処理を行ってもよい。
【０１９１】
なお、ここでいう「コンピュータシステム」とは、ＯＳや周辺機器等のハードウェアを含むものであってもよい。また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、フラッシュメモリ等の書き込み可能な不揮発性メモリ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。
【０１９２】
さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリ（例えばＤＲＡＭ（Ｄｙｎａｍｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ））のように、一定時間プログラムを保持しているものも含むものとする。また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１９３】
以上、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【０１９４】
１  情報処置装置
２、２ｂ  記憶部
３、３ｂ、３ｃ、３ｄ、３ｅ、３ｆ、３ｇ、３ｈ  処理部
４  入力部
３１、３１ｂ  範囲取得部
３２、３２ｂ、３２ｃ、３２ｄ、３２ｅ、３２ｆ、３２ｇ、３２ｈ  集合取得部
３３  配置決定部
【図１】
2015012495.tif 000003
【図２】
2015012495.tif 000004
【図３】
2015012495.tif 000005
【図４】
2015012495.tif 000006
【図５】
2015012495.tif 000007
【図６】
2015012495.tif 000008
【図７】
2015012495.tif 000009
【図８】
2015012495.tif 000010
【図９】
2015012495.tif 000011
【図１０】
2015012495.tif 000012
【図１１】
2015012495.tif 000013
【図１２】
2015012495.tif 000014
【図１３】
2015012495.tif 000015
【図１４】
2015012495.tif 000016
【図１５Ａ】
2015012495.tif 000017
【図１５Ｂ】
2015012495.tif 000018
【図１６】
2015012495.tif 000019
【図１７】
2015012495.tif 000020
【図１８】
2015012495.tif 000021
【図１９】
2015012495.tif 000022
【図２０】
2015012495.tif 000023
【図２１】
2015012495.tif 000024
【図２２】
2015012495.tif 000025
【図２３Ａ】
2015012495.tif 000026
【図２３Ｂ】
2015012495.tif 000027
【図２３Ｃ】
2015012495.tif 000028
【図２３Ｄ】
2015012495.tif 000029
【図２４】
2015012495.tif 000030
【図２５】
2015012495.tif 000031
【図２６】
2015012495.tif 000032
【図２７】
2015012495.tif 000033
【図２８】
2015012495.tif 000034
【図２９】
2015012495.tif 000035
【図３０】
2015012495.tif 000036
【図３１】
2015012495.tif 000037