(57)【要約】      （修正有）【課題】簡易に、どのノードにどのモジュールを配備するかを決定する。【解決手段】サーバノード１は、モジュールが複数のノードのうちのいずれのノードに配備されるのかを示す第１の情報、及び、第１の情報が示すモジュールが配備されるノードを変更した第２の情報の所定の評価度合いを示す評価値に基づいて、第１の情報及び第２の情報の各情報の中から、評価度合いが高い上位所定個の情報を決定する。モジュールが配備されるノードを変更した第３の情報の各情報の中から、合致しない条件の数が少ない上位所定個の情報を決定する。決定された情報、及び、情報が示すモジュールが配備されるノードを変更した第４の情報の評価度合いを示す評価値と、決定された情報、及び、第４の情報の各情報における合致しない条件の数とに基づいて、決定された情報、及び、第４の情報の各情報の中から、価値及び合致しない条件の数が所定の基準を満たす情報を決定する。【選択図】図２０
2015019338.tif 000002
【特許請求の範囲】
【請求項１】
検知したイベントを送信するか、または、前記イベントを中継する複数のノードが接続されたネットワークを示すネットワーク情報、及び、前記イベントを加工処理するモジュールを識別する識別子を記憶する記憶部と、
前記モジュールが前記複数のノードのうちのいずれのノードに配備されるのかを示す第１の情報、及び、前記第１の情報が示す前記モジュールが配備される前記ノードを変更した第２の情報の各情報における所定の評価度合いを示す評価値に基づいて、前記第１の情報及び前記第２の情報の各情報の中から、前記評価度合いが高い上位所定個の情報を決定する第１の決定部と、
前記第１の決定部により決定された情報、及び、該情報が示す前記モジュールが配備される前記ノードを変更した第３の情報の各情報の中から、所定数の所定の条件のうち合致しない条件の数が少ない上位所定個の情報を決定する第２の決定部と、
前記第２の決定部により決定された情報、及び、該情報が示す前記モジュールが配備される前記ノードを変更した第４の情報の各情報における前記所定の評価度合いを示す評価値と、前記第２の決定部により決定された情報、及び、前記第４の情報の各情報における前記所定数の所定の条件のうち合致しない条件の数とに基づいて、前記第２の決定部により決定された情報、及び、前記第４の情報の各情報の中から、該評価値及び該合致しない条件の数が所定の基準を満たす情報を決定する第３の決定部と、
前記第３の決定部により決定された情報を出力する出力部と、
を有することを特徴とするモジュール配備決定装置。
【請求項２】
前記第２の決定部は、前記モジュールが示す処理フローにおける前記イベントが送信される方向において上流側に位置するモジュールであって、前記第１の決定部により決定された情報が示すモジュールを配置するノードを所定の確率で変更することにより、前記第３の情報を生成し、
前記第３の決定部は、前記モジュールが示す処理フローにおける前記イベントが送信される方向において上流側に位置するモジュールであって、前記第２の決定部により決定された情報が示すモジュールを配置するノードを前記所定の確率で変更することにより、前記第４の情報を生成し、
前記第１の決定部は、前記モジュールが示す処理フローにおける前記イベントが送信される方向において上流側に位置するモジュールであって、前記第１の情報が示すモジュールを配置するノードを前記所定の確率よりも高い確率で変更することにより、前記第２の情報を生成する
ことを特徴とする請求項１に記載のモジュール配備決定装置。
【請求項３】
前記第１の決定部は、さらに、所定回数分の前記第１の情報を生成するまで、前記第３の決定部により情報が決定されるたびに、前記第３の決定部により決定された情報が示す前記モジュールが配備される前記ノードを変更して新たな第１の情報を生成し、該新たな第１の情報が示す前記モジュールが配備される前記ノードを変更して新たな第２の情報を生成し、該新たな第１の情報及び該新たな第２の情報の各情報における前記評価値に基づいて、該新たな第１の情報及び該新たな第２の情報の各情報の中から、前記評価度合いが高い上位所定個の情報を決定し、
前記第２の決定部は、前記第１の決定部により情報が新たに決定されるたびに、前記第１の決定部により決定された新たな情報が示す前記モジュールが配備される前記ノードを変更して新たな第３の情報を生成し、前記第１の決定部により決定された新たな情報、及び、該新たな第３の情報の各情報の中から、前記所定数の所定の条件のうち合致しない条件の数が少ない上位所定個の情報を決定し、
前記第３の決定部は、前記第２の決定部により情報が新たに決定されるたびに、前記第２の決定部により決定された新たな情報が示す前記モジュールが配備される前記ノードを変更して新たな第４の情報を生成し、前記第２の決定部により決定された新たな情報、及び、該新たな第４の情報の各情報の中から、前記評価値及び前記合致しない条件の数が前記所定の基準を満たす情報を決定する
ことを特徴とする請求項１または２に記載のモジュール配備決定装置。
【請求項４】
前記第２の決定部は、前記合致しない条件の種類に応じた重みを用いて、前記合致しない条件を重み付けした値を、前記合致しない条件の数として算出する
ことを特徴とする請求項１〜３のいずれか１つに記載のモジュール配備決定装置。
【請求項５】
前記第１の決定部は、遺伝的アルゴリズムを用いて、前記第１の情報を親世代とした場合に、次世代として前記第２の情報を生成し、
前記第２の決定部は、遺伝的アルゴリズムを用いて、前記第１の決定部により決定された情報を親世代とした場合に、次世代として前記第３の情報を生成し、
前記第３の決定部は、遺伝的アルゴリズムを用いて、前記第２の決定部により決定された情報を親世代とした場合に、次世代として前記第４の情報を生成する
ことを特徴とする請求項１〜４のいずれか１つに記載のモジュール配備決定装置。
【請求項６】
複数のノードと、情報処理装置とを有するシステムであって、
前記複数のノードのそれぞれは、
検知したイベントを送信するか、または、前記イベントを中継する制御部
を有し、
前記情報処理装置は、
前記複数のノードが接続されたネットワークを示すネットワーク情報、及び、前記イベントを加工処理するモジュールを識別する識別子を記憶する記憶部と、
前記モジュールが前記複数のノードのうちのいずれのノードに配備されるのかを示す第１の情報、及び、前記第１の情報が示す前記モジュールが配備される前記ノードを変更した第２の情報の各情報における所定の評価度合いを示す評価値に基づいて、前記第１の情報及び前記第２の情報の各情報の中から、前記評価度合いが高い上位所定個の情報を決定する第１の決定部と、
前記第１の決定部により決定された情報、及び、該情報が示す前記モジュールが配備される前記ノードを変更した第３の情報の各情報の中から、所定数の所定の条件のうち合致しない条件の数が少ない上位所定個の情報を決定する第２の決定部と、
前記第２の決定部により決定された情報、及び、該情報が示す前記モジュールが配備される前記ノードを変更した第４の情報の各情報における前記所定の評価度合いを示す評価値と、前記第２の決定部により決定された情報、及び、前記第４の情報の各情報における前記所定数の所定の条件のうち合致しない条件の数とに基づいて、前記第２の決定部により決定された情報、及び、前記第４の情報の各情報の中から、該評価値及び該合致しない条件の数が所定の基準を満たす情報を決定する第３の決定部と、
前記第３の決定部により決定された情報を出力する出力部と、
を有する
ことを特徴とするモジュール配備決定システム。
【請求項７】
コンピュータが、
検知したイベントを送信するか、または、前記イベントを中継する複数のノードが接続されたネットワークを示すネットワーク情報、及び、前記イベントを加工処理するモジュールを識別する識別子を記憶する記憶部の記憶内容に基づいて決定された、前記モジュールが前記複数のノードのうちのいずれのノードに配備されるのかを示す第１の情報、及び、前記第１の情報が示す前記モジュールが配備される前記ノードを変更した第２の情報の各情報における所定の評価度合いを示す評価値に基づいて、前記第１の情報及び前記第２の情報の各情報の中から、前記評価度合いが高い上位所定個の情報を決定し、
決定された前記情報、及び、該情報が示す前記モジュールが配備される前記ノードを変更した第３の情報の各情報の中から、所定数の所定の条件のうち合致しない条件の数が少ない上位所定個の情報を決定し、
前記所定数の所定の条件のうち合致しない条件の数が少ない上位所定個の情報、及び、該情報が示す前記モジュールが配備される前記ノードを変更した第４の情報の各情報における前記所定の評価度合いを示す評価値と、前記所定数の所定の条件のうち合致しない条件の数が少ない上位所定個の情報、及び、前記第４の情報の各情報における前記所定数の所定の条件のうち合致しない条件の数とに基づいて、前記評価度合いが高い上位所定個の情報及び前記第３の情報の各情報の中から決定された前記合致しない条件の数が少ない上位所定個の情報、及び、前記第４の情報の各情報の中から、該評価値及び該合致しない条件の数が前記所定の基準を満たす情報を決定する
処理を実行することを特徴とするモジュール配備決定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モジュール配備決定装置、モジュール配備決定システム及びモジュール配備決定方法に関する。
【背景技術】
【０００２】
センサノードによってセンシングされたセンシングデータをイベントとして採取するセンサネットワークが知られている。かかるセンサネットワークを介してサーバノードに採取されたイベントに応じて各種のサービス、例えばアラートの発信や機器の制御などが提供される。
【０００３】
このように、センサノードからのイベントをサーバノードに収集させる場合には、全てのイベントがサーバノードに集中して通知されることになる。このため、サーバノードの処理の負荷が増大するとともに、ネットワークのトラフィックの増加に伴ってネットワーク帯域も逼迫する。また、センサネットワークにおいては、あるセンサノードの処理量を、他のセンサノードの処理量よりも低くするなどの所定の制約条件がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００８−２６９２５０号公報
【特許文献２】特開２０１２−１７５４１８号公報
【特許文献３】特開平７−２６２１１５号公報
【特許文献４】特開平１１−３４５２５７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、サーバノードの負荷とネットワークトラフィックを抑制しつつ、所定の制約条件を満たすように、センサノードやイベントを中継する中継ノードなどの下位ノードに配備するモジュールを決定する技術の一例として、以下のような技術が考えられる。例えば、下位ノードに配備するモジュールを決定する技術は、まず、イベントの発生状況やセンサネットワークのトポロジに応じてイベントの収集経路を決定する。そして、下位ノードに配備するモジュールを決定する技術は、決定した収集経路に基づいて、下位ノードと、下位ノードに対して配備されたイベントを処理するモジュールとの全ての組合せについて、次のような処理を行う。すなわち、下位ノードの配備するモジュールを決定する技術は、全ての組合せについて、サーバノードの負荷を示す第１の評価値と、ネットワークトラフィックを示す第２の評価値と、所定の制約条件のうち違反した条件の数を示す第３の評価値とを算出する。そして、下位ノードに配備するモジュールを決定する技術は、第１の評価値と、第２の評価値と、第３の評価値とに基づいて、下位ノードに配備するモジュールを決定する。
【０００６】
しかしながら、上述したモジュールを決定する技術では、全ての組合せにおいて、上述した各種の評価値を算出するため、どのノードにどのモジュールを配備するかを決定する際に多大な時間がかかるという問題がある。
【０００７】
１つの側面では、本発明は、簡易に、どのノードにどのモジュールを配備するかを決定することを目的とする。
【課題を解決するための手段】
【０００８】
モジュール配備決定装置は、記憶部と、第１の決定部と、第２の決定部と、第３の決定部と、出力部とを有する。記憶部は、検知したイベントを送信するか、または、前記イベントを中継する複数のノードが接続されたネットワークを示すネットワーク情報、及び、前記イベントを加工処理するモジュールを識別する識別子を記憶する。第１の決定部は、前記モジュールが前記複数のノードのうちのいずれのノードに配備されるのかを示す第１の情報、及び、前記第１の情報が示す前記モジュールが配備される前記ノードを変更した第２の情報の各情報における所定の評価度合いを示す評価値に基づいて、前記第１の情報及び前記第２の情報の各情報の中から、前記評価度合いが高い上位所定個の情報を決定する。第２の決定部は、前記第１の決定部により決定された情報、及び、該情報が示す前記モジュールが配備される前記ノードを変更した第３の情報の各情報の中から、所定数の所定の条件のうち合致しない条件の数が少ない上位所定個の情報を決定する。第３の決定部は、前記第２の決定部により決定された情報、及び、該情報が示す前記モジュールが配備される前記ノードを変更した第４の情報の各情報における前記所定の評価度合いを示す評価値と、前記第２の決定部により決定された情報、及び、前記第４の情報の各情報における前記所定数の所定の条件のうち合致しない条件の数とに基づいて、前記第２の決定部により決定された情報、及び、前記第４の情報の各情報の中から、該評価値及び該合致しない条件の数が所定の基準を満たす情報を決定する。出力部は、前記第３の決定部により決定された情報を出力する。
【発明の効果】
【０００９】
簡易に、どのノードにどのモジュールを配備するかを決定することができる。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施例に係るモジュール配備決定システムの一例であるセンサネットワークシステムのシステム構成の一例を示す図である。
【図２】図２は、実施例に係るサーバノードの機能構成の一例を示すブロック図である。
【図３】図３は、トポロジ記憶部に記憶されたトポロジが示すセンサネットワークシステムにおける各種のノードの接続形態の一例を示す図である。
【図４】図４は、モジュール定義記憶部に記憶された定義の一例を示す図である。
【図５】図５は、初期解の一例を示す図である。
【図６】図６は、図５の例の初期解が示すインスタンスとインスタンスが配備されるノードとを模式的に表した図である。
【図７】図７は、２つ目の親世代の一例を示す図である。
【図８】図８は、大域検索の場合における確率情報の一例を示す図である。
【図９】図９は、次世代の算出方法の一例を示す図である。
【図１０】図１０は、制約検索及び周辺検索の場合における確率情報の一例を示す図である。
【図１１】図１１は、次世代を突然変異させた結果得られた新たな次世代の一例を示す図である。
【図１２】図１２は、制約評価値の算出方法の一例を説明するための図である。
【図１３】図１３は、制約評価値の算出方法の一例を説明するための図である。
【図１４】図１４は、制約評価値の算出方法の一例を説明するための図である。
【図１５】図１５は、制約評価値の算出方法の一例を説明するための図である。
【図１６】図１６は、所定の重み定数の一例を示す図である。
【図１７Ａ】図１７Ａは、実施例に係るセンサノードの機能構成の一例を示すブロック図である。
【図１７Ｂ】図１７Ｂは、実施例に係るＧＷノードの機能構成の一例を示すブロック図である。
【図１８Ａ】図１８Ａは、実施例に係るモジュール配備決定処理の手順を示すフローチャートである。
【図１８Ｂ】図１８Ｂは、実施例に係るモジュール配備決定処理の手順を示すフローチャートである。
【図１９】図１９は、実施例に係るサーバノードが実行する処理の一例を説明するための図である。
【図２０】図２０は、実施例に係るサーバノードの機能構成の他の例を示すブロック図である。
【図２１】図２１は、モジュール配備決定プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１１】
以下に、本願の開示するモジュール配備決定装置の一例であるサーバノード、モジュール配備決定システムの一例であるセンサネットワークシステム、及び、モジュール配備決定方法の実施例を図面に基づいて詳細に説明する。なお、実施例は開示の技術を限定するものではない。
【実施例】
【００１２】
［実施例に係るセンサネットワークシステムのシステム構成の一例］
図１は、実施例に係るモジュール配備決定システムの一例であるセンサネットワークシステムのシステム構成の一例を示す図である。図１に示すセンサネットワークシステム１０は、イベントを加工する処理を行う各種のモジュールをどのノード（センサノード、ＧＷノード、サーバノード）に配備するかを決定するシステムである。ここでいうイベントとは、センサノードによってセンシングされたデータ、または、センシングされたデータが加工処理されたデータを指す。
【００１３】
図１の例に示すように、センサネットワークシステム１０は、サーバノード（５）１と、３つのセンサノード（１）２１ａ、センサノード（２）２１ｂ及びセンサノード（３）２１ｃと、ＧＷ（GateWay）ノード（４）２２とを有する。ここで、「センサノード（１）２１ａ」における「（１）」は、ノードを識別するための識別子（ノードＩＤ）である。例えば、ノードＩＤ「１」が示すノードは、センサノード２１ａである。同様に、ノードＩＤ「２」が示すノードは、センサノード２１ｂであり、ノードＩＤ「３」が示すノードは、センサノード２１ｃであり、ノードＩＤ「４」が示すノードは、ＧＷノード２２であり、ノードＩＤ「５」が示すノードは、サーバノード１である。以下の説明では、識別子の表記を省略する場合がある。
【００１４】
図１の例では、サーバノード１とＧＷノード２２とがネットワーク２３を介して通信可能に接続される。ネットワーク２３の一例としては、有線または無線を問わず、インターネット（internet）、ＬＡＮ（Local  Area  Network）やＶＰＮ（Virtual  Private  Network）などの通信網が挙げられる。なお、図１では、センサネットワークシステム１０が、３つのセンサノード２１ａ〜２１ｃを有する場合を例示したが、センサネットワークシステム１０は、任意の数のセンサノードを有することができる。また、以下の説明では、３つのセンサノード２１ａ〜２１ｃを区別することなく総称する場合には、単に、「センサノード２１」と表記する。また、図１の例では、センサネットワークシステム１０が、１つのＧＷノード２２を有する場合を例示したが、センサネットワークシステム１０は、任意の数のＧＷノードを有することができる。
【００１５】
図１の例に示すセンサネットワークシステム１０では、センサノード２１から送信されたイベントを、ＧＷノード２２及びネットワーク２３を介して、サーバノード１が収集する。
【００１６】
センサノード２１は、センサが搭載された通信端末である。センサノード２１の一態様としては、パーソナルコンピュータやパーソナルコンピュータの周辺機器、ＡＶ（Audio  Visual）機器、携帯電話機やＰＨＳ（Personal  Handyphone  System）の携帯端末、家電製品などの各種の機器が挙げられる。また、センサノード２１に搭載されるセンサの一態様としては、照度を検出する照度センサ、温度を検出する温度センサ、湿度を検出する湿度センサ、温度及び湿度を検出する温湿度センサなどの環境センサが挙げられる。なお、センサノード２１に搭載されるセンサは、環境センサに限られない。例えば、センサノード２１に搭載されるセンサは、ＧＰＳ（Global  Positioning  System）センサ、加速度センサやジャイロセンサなどの各種のセンサでもよい。
【００１７】
ここで、以下の説明では、３つのセンサノード２１ａ〜２１ｃが、照度センサであり、センサノード２１ａが「Ｓ５０１室」という室に配備され、センサノード２１ｂ及びセンサノード２１ｃが「Ｓ５０３室」という室に配備された場合について説明する。
【００１８】
ＧＷノード２２は、サーバノード１とセンサノード２１との通信を中継するノードである。例えば、ＧＷノード２２は、センサノード２１から送信されたイベントを受信し、受信したイベントを、ネットワーク２３を介してサーバノード１へ送信する。以下の説明では、センサネットワークにおけるルートノードであるサーバノード１以外のノード、すなわち、センサノード２１およびＧＷノード２２を「下位ノード」と表記する場合がある。
【００１９】
サーバノード１は、センサネットワークにおけるルートノードとしての機能を有する。サーバノード１は、イベントを加工する処理を行う各種のモジュールをどのノード（センサノード、ＧＷノード、サーバノード）に配備するかを決定するサーバである。
【００２０】
［サーバノード１の機能構成の一例］
続いて、本実施例に係るサーバノード１の機能構成の一例について説明する。図２は、実施例に係るサーバノードの機能構成の一例を示すブロック図である。図２の例に示すように、サーバノード１は、入力部２と、出力部３と、通信部４と、制御部６と、最適解記憶部５ａと、親世代記憶部５ｂと、次世代記憶部５ｃと、トポロジ記憶部５ｄと、モジュール記憶部５ｅと、モジュール定義記憶部５ｆと、フラグ記憶部５ｇとを有する。
【００２１】
入力部２は、各種の情報をサーバノード１に入力する。例えば、入力部２は、サーバノード１のユーザから、後述のモジュール配備決定処理を実行する指示を受け付けた場合には、受け付けた指示をサーバノード１に入力する。入力部２のデバイスの一例としては、キーボードやマウスなどが挙げられる。
【００２２】
出力部３は、各種の情報を出力する。例えば、出力部３は、最適解出力制御部６ｆが実行する後述の処理により、後述の最適解を表示するように制御される。出力部３のデバイスの一例としては、液晶ディスプレイなどの各種の表示装置や、音声を出力する音声出力装置が挙げられる。
【００２３】
通信部４は、サーバノード１と、下位ノードとの通信を行う。例えば、通信部４は、モジュール出力制御部６ｇが実行する後述の処理により、モジュールを下位ノードに送信するように制御される。通信部４のデバイスの一例として、ネットワークインタフェースカードなどの各種の通信を行うためのデバイスが挙げられる。
【００２４】
最適解記憶部５ａには、所定値、例えば、「１０００」を初期値とする最適解が予め記憶される。かかる最適解は、モジュール配備決定処理において、最適解更新部６ｅが実行する後述の処理により更新される。
【００２５】
親世代記憶部５ｂには、後述の親世代が格納される。また、親世代記憶部５ｂに記憶された親世代は、更新される。本実施例では、親世代が２つであり、２つの親世代が更新される場合について以下説明するが、親世代の数はこれに限られず、任意の数を採用できる。
【００２６】
次世代記憶部５ｃには、次世代生成部６ｂが実行する後述の処理により後述の２つの次世代が格納される。また、次世代記憶部５ｃに記憶された次世代は、更新される。
【００２７】
トポロジ記憶部５ｄは、センサネットワークシステム１０における各種のノード（サーバノード１、センサノード２１、ＧＷノード２２）の接続形態を示す情報、いわゆる、トポロジを記憶する。かかるトポロジは、例えば、次のようにして、トポロジ記憶部５ｄに格納される。例えば、サーバノード１は、特開２０１３−０４７９２２号公報に記載された技術を用いて、下位ノードのそれぞれから、下位ノードと下位ノードが接続される上位のノードとの接続関係を示す接続情報を取得する。また、サーバノード１は、下位ノードから送信されるイベントを受信し、受信したイベントに含まれる属性情報に、下位ノードが配備された場所を示す情報が含まれる場合には、属性情報から下位ノードが配備された場所を特定する。そして、サーバノード１は、下位ノードのそれぞれから取得した接続情報、及び、下位ノードが配備された場所を用いて、センサネットワークシステム１０における各種のノードの接続形態を示す情報を生成する。そして、サーバノード１は、生成した情報をトポロジとしてトポロジ記憶部５ｄに格納する。なお、ユーザが入力部２を介して、トポロジをサーバノード１に入力するとともに、入力したトポロジをトポロジ記憶部５ｄに格納する指示をサーバノード１に入力することにより、トポロジ記憶部５ｄにトポロジを格納させることもできる。
【００２８】
図３は、トポロジ記憶部に記憶されたトポロジが示すセンサネットワークシステムにおける各種のノードの接続形態の一例を示す図である。図３の例は、ＧＷノード２２に、センサノード２１ａと、センサノード２１ｂと、センサノード２１ｃとが接続され、サーバノード１に、ＧＷノード２２が接続された場合の接続形態の一例である。また、図３の例は、センサノード２１ａが「Ｓ５０１室」に配備され、センサノード２１ｂ及びセンサノード２１ｃが「Ｓ５０３室」に配備されたことを示す。
【００２９】
モジュール定義記憶部５ｆは、センサネットワークシステム１０における各種のノードで実行されるモジュールのインスタンスについての定義を記憶する。かかる定義は、例えば、次のようにして、モジュール定義記憶部５ｆに格納される。例えば、サーバノード１は、モジュールの開発者によってプログラミングされたモジュールのインスタンスについての定義を、入力部２を介して受け付け、受け付けた定義をモジュール定義記憶部５ｆに格納する。
【００３０】
図４は、モジュール定義記憶部に記憶された定義の一例を示す図である。図４の例は、定義としてモジュール定義記憶部５ｆに記憶された、モジュールの処理フローの各処理をデータ単位に実行するインスタンスの接続関係を示す。図４の例における「（Ｎ）」（Ｎ＝１，２，・・・，８）は、各インスタンスを識別するための識別子（インスタンスＩＤ）である。
【００３１】
例えば、インスタンスＩＤ「１」は、「Ｓ５０１室に配備されたセンサノードによって検出された照度を読み込む」インスタンスを示す。インスタンスＩＤ「２」及び「３」は、ともに、「Ｓ５０３室に配備されたセンサノードによって検出された照度を読み込む」インスタンスを示す。また、インスタンスＩＤ「４」は、インスタンスＩＤ「１」が示すインスタンスによって読み込まれた照度を用いて、「Ｓ５０１室の照度の平均値を算出する」インスタンスを示す。
【００３２】
また、インスタンスＩＤ「５」は、インスタンスＩＤ「２」及び「３」のそれぞれが示す各インスタンスによって読み込まれた照度を用いて、「Ｓ５０３室の照度の平均値を算出する」インスタンスを示す。また、インスタンスＩＤ「６」は、インスタンスＩＤ「４」及び「５」のそれぞれが示す各インスタンスによって算出された照度の平均値を用いて、「照度の平均値の合計を算出する」インスタンスを示す。また、インスタンスＩＤ「７」は、インスタンスＩＤ「４」及び「５」のそれぞれが示す各インスタンスによって算出された照度の平均値を用いて、「照度の平均値を記憶部に蓄積する」インスタンスを示す。また、インスタンスＩＤ「８」は、インスタンスＩＤ「６」が示すインスタンスによって算出された照度の平均値の合計を用いて、「照度の平均値の合計を記憶部に蓄積する」インスタンスを示す。
【００３３】
モジュール記憶部５ｅは、モジュールの各インスタンスを記憶する。かかるインスタンスは、例えば、次のようにして、モジュール記憶部５ｅに格納される。例えば、サーバノード１は、モジュールの開発者によってプログラミングされたモジュールのインスタンスのバイナリコードとインスタンスＩＤを、入力部１を介して受け付け、受け付けたインスタンスのバイナリコードをインスタンスＩＤとともにモジュール記憶部５ｅに格納する。一例としては、モジュール記憶部５ｅは、先の図４の例に示す８つのインスタンスのバイナリコードのそれぞれと、対応するインスタンスＩＤとを対応付けて記憶する。
【００３４】
フラグ記憶部５ｇは、２ビットのフラグを記憶する。例えば、かかるフラグには、「１」、「２」、「３」のいずれかの値が設定される。「１」は、後述の大域検索のモードを示す。「２」は、後述の制約検索のモードを示す。「３」は、後述の周辺検索のモードを示す。
【００３５】
図２の説明に戻り、制御部６は、初期解生成部６ａと、次世代生成部６ｂと、親世代選択部６ｃと、モード判定部６ｄと、最適解更新部６ｅと、最適解出力制御部６ｆと、モジュール出力制御部６ｇとを有する。制御部６は、ＡＳＩＣ（Application  Specific  Integrated  Circuit）、ＦＰＧＡ（Field  Programmable  Gate  Array）、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）などの回路である。
【００３６】
初期解生成部６ａは、インスタンスと、インスタンスが配備されるノードとの関係を示す解であって、モジュール配備決定処理における最初の２つの親世代のうちの１つの親世代である初期解を生成する。
【００３７】
初期解生成部６ａの一態様について説明する。初期解生成部６ａは、入力部２からモジュール配備決定処理を実行する指示が入力されると、まず、トポロジ記憶部５ｄからトポロジを取得する。そして、初期解生成部６ａは、モジュール定義記憶部５ｆから、モジュール定義記憶部５ｆに記憶された定義を取得する。
【００３８】
そして、初期解生成部６ａは、初期解を生成する。例えば、初期解生成部６ａは、特開２０１３−０４７９２２号公報に記載された技術を用いて、トポロジ及び定義から、配備先のノードのノードＩＤと、ノードＩＤが示すノードに配備されるインスタンスのインスタンスＩＤとを導出する。そして、初期解生成部６ａは、ノードＩＤと、インスタンスＩＤとを対応付けて、初期解を生成する。図５は、初期解の一例を示す図である。図６は、図５の例の初期解が示すインスタンスとインスタンスが配備されるノードとを模式的に表した図である。
【００３９】
図５の例に示す初期解では、インスタンスＩＤ「１」と、ノードＩＤ「１」とが対応付けられている。また、図５の例の初期解では、インスタンスＩＤ「４」と、ノードＩＤ「１」とが対応付けられている。これは、図６の例に示すように、ノードＩＤ「１」が示すセンサノード２１ａに、インスタンスＩＤ「１」が示すインスタンスとインスタンスＩＤ「４」が示すインスタンスとが配備された場合を示す。
【００４０】
また、図５の例の初期解では、インスタンスＩＤ「２」と、ノードＩＤ「２」とが対応付けられている。これは、図６の例に示すように、ノードＩＤ「２」が示すセンサノード２１ｂに、インスタンスＩＤ「２」が示すインスタンスが配備された場合を示す。
【００４１】
また、図５の例の初期解では、インスタンスＩＤ「３」と、ノードＩＤ「３」とが対応付けられている。これは、図６の例に示すように、ノードＩＤ「３」が示すセンサノード２１ｃに、インスタンスＩＤ「３」が示すインスタンスが配備された場合を示す。
【００４２】
また、図５の例の初期解では、インスタンスＩＤ「５」と、ノードＩＤ「４」とが対応付けられている。これは、図６の例に示すように、ノードＩＤ「４」が示すＧＷノード２２に、インスタンスＩＤ「５」が示すインスタンスが配備された場合を示す。
【００４３】
また、図５の例の初期解では、インスタンスＩＤ「６」と、ノードＩＤ「５」とが対応付けられている。また、図５の例の初期解では、インスタンスＩＤ「７」と、ノードＩＤ「５」とが対応付けられている。さらに、図５の例の初期解では、インスタンスＩＤ「８」と、ノードＩＤ「５」とが対応付けられている。これは、図６の例に示すように、ノードＩＤ「５」が示すサーバノード１に、インスタンスＩＤ「６」が示すインスタンスとインスタンスＩＤ「７」が示すインスタンスとインスタンスＩＤ「８」が示すインスタンスとが配備された場合を示す。
【００４４】
そして、初期解生成部６ａは、生成した初期解を１つ目の親世代として、親世代記憶部５ｂに格納する。例えば、初期解生成部６ａは、図５の例に示す初期解を１つ目の親世代として親世代記憶部５ｂに格納する。
【００４５】
そして、初期解生成部６ａは、遺伝的アルゴリズム（genetic  algorithm）を用いて、１つ目の親世代から、突然変異によって新たな解を生成し、生成した解を２つ目の親世代として親世代記憶部５ｂに格納する。図７は、２つ目の親世代の一例を示す図である。例えば、初期解生成部６ａは、図５の例に示す１つ目の親世代から、突然変異によって、図７の例に示すような新たな解を生成し、生成した解を２つ目の親世代として親世代記憶部５ｂに格納する。これにより、親世代記憶部５ｂには、２つの親世代が格納される。
【００４６】
そして、初期解生成部６ａは、フラグ記憶部５ｇに記憶されたフラグに「１」を設定する。これにより、モジュール配備決定処理におけるモードが、大域検索のモードとなる。
【００４７】
次世代生成部６ｂは、親世代から次世代を生成する。次世代生成部６ｂの一態様について説明する。例えば、次世代生成部６ｂは、所定のタイミングで、フラグ記憶部５ｇに記憶されたフラグを参照する。ここで、所定のタイミングについて説明する。例えば、所定のタイミングとしては、７つのタイミングがある。１つ目のタイミングとしては、初期解生成部６ａにより、フラグ記憶部５ｇに記憶されたフラグに「１」が設定されたタイミングが挙げられる。２つ目のタイミングとしては、モード判定部６ｄにより、２つの親世代のうち少なくとも１つの親世代が、制約に違反した数が０でないと判定されたタイミングが挙げられる。また、３つ目のタイミングとしては、モード判定部６ｄにより、フラグ記憶部５ｇに記憶されたフラグの値が「３」に更新されて、モジュール配備決定処理におけるモードが周辺検索のモードに設定されたタイミングが挙げられる。また、４つ目のタイミングとしては、モード判定部６ｄにより、フラグ記憶部５ｇに記憶されたフラグの値が「２」に更新されて、モジュール配備決定処理におけるモードが制約検索のモードに設定されたタイミングが挙げられる。５つ目のタイミングとしては、最適解更新部６ｅにより、最適解記憶部５ａに記憶された最適解が更新されたタイミングが挙げられる。６つ目のタイミングとしては、最適解更新部６ｅにより、２つの親世代の中に、制約に違反した数が０であり、かつ、最適解記憶部５ａに記憶された最適解よりも評価が高い親世代が存在しないと判定されたタイミングが挙げられる。７つ目のタイミングとしては、モード判定部により、次世代が所定回数以上更新されている間に、親世代が更新されていないと判定されたタイミングが挙げられる。
【００４８】
そして、フラグを参照すると、次世代生成部６ｂは、フラグの値が「１」である場合には、親世代記憶部５ｂに記憶された２つの親世代を取得する。そして、次世代生成部６ｂは、大域検索の場合における確率情報が示す各インスタンスＩＤを選択する確率（交叉選択確率）にしたがって、２つの親世代のインスタンスＩＤを、所定の交叉数（例えば、「３」）分だけ選択する。大域検索の場合における確率情報は、次世代生成部６ｂの内部メモリに記憶されている。図８は、大域検索の場合における確率情報の一例を示す図である。
【００４９】
図８に示す確率情報は、インスタンスＩＤ「１」を選択する確率が「１５％」であることを示す。また、図８に示す確率情報は、インスタンスＩＤ「２」を選択する確率が「１５％」であることを示す。また、図８に示す確率情報は、インスタンスＩＤ「３」を選択する確率が「１５％」であることを示す。また、図８に示す確率情報は、インスタンスＩＤ「４」を選択する確率が「１３％」であることを示す。また、図８に示す確率情報は、インスタンスＩＤ「５」を選択する確率が「１１％」であることを示す。また、図８に示す確率情報は、インスタンスＩＤ「６」を選択する確率が「１１％」であることを示す。また、図８に示す確率情報は、インスタンスＩＤ「７」を選択する確率が「１０％」であることを示す。また、図８に示す確率情報は、インスタンスＩＤ「８」を選択する確率が「１０％」であることを示す。
【００５０】
そして、次世代生成部６ｂは、一方の親世代における選択したインスタンスＩＤに対応するノードＩＤと、他方の親世代における選択したインスタンスＩＤに対応するノードＩＤとを入れ替えることで、２つの親世代を交叉させて２つの次世代を生成する。図９は、次世代の算出方法の一例を示す図である。例えば、図９の例には、図５の例に示す１つ目の親世代が「親世代１」として示され、また、図７の例に示す２つ目の親世代が「親世代２」として示されている。また、図９の例は、次世代生成部６ｂが、親世代１及び親世代２のインスタンスＩＤ「１」、インスタンスＩＤ「３」、インスタンスＩＤ「６」を選択した場合を示す。次世代生成部６ｂは、図９の例に示すように、親世代１における選択したインスタンスＩＤ「１」に対応するノードＩＤ「４」と、親世代２における選択したインスタンスＩＤ「１」に対応するノードＩＤ「１」とを入れ替える。また、次世代生成部６ｂは、図９の例に示すように、親世代１における選択したインスタンスＩＤ「３」に対応するノードＩＤ「１」と、親世代２における選択したインスタンスＩＤ「３」に対応するノードＩＤ「３」とを入れ替える。また、次世代生成部６ｂは、図９の例に示すように、親世代１における選択したインスタンスＩＤ「６」に対応するノードＩＤ「４」と、親世代２における選択したインスタンスＩＤ「６」に対応するノードＩＤ「４」とを入れ替える。このようにして、次世代生成部６ｂは、２つの親世代１及び親世代２を交叉させて２つの次世代（次世代１、次世代２）を生成する。
【００５１】
また、次世代生成部６ｂは、参照したフラグの値が「２」または「３」である場合には、親世代記憶部５ｂに記憶された２つの親世代を取得する。そして、次世代生成部６ｂは、制約検索及び周辺検索の場合における確率情報が示す各インスタンスＩＤを選択する確率（交叉選択確率）にしたがって、２つの親世代のインスタンスＩＤを、所定の交叉数（例えば、「３」）分だけ選択する。制約検索及び周辺検索の場合における確率情報は、次世代生成部６ｂの内部メモリに記憶されている。図１０は、制約検索及び周辺検索の場合における確率情報の一例を示す図である。
【００５２】
図１０に示す確率情報は、インスタンスＩＤ「１」を選択する確率が「１０％」であることを示す。また、図１０に示す確率情報は、インスタンスＩＤ「２」を選択する確率が「１０％」であることを示す。また、図１０に示す確率情報は、インスタンスＩＤ「３」を選択する確率が「１０％」であることを示す。また、図１０に示す確率情報は、インスタンスＩＤ「４」を選択する確率が「１４％」であることを示す。また、図１０に示す確率情報は、インスタンスＩＤ「５」を選択する確率が「１４％」であることを示す。また、図１０に示す確率情報は、インスタンスＩＤ「６」を選択する確率が「１４％」であることを示す。また、図１０に示す確率情報は、インスタンスＩＤ「７」を選択する確率が「１４％」であることを示す。また、図１０に示す確率情報は、インスタンスＩＤ「８」を選択する確率が「１４％」であることを示す。
【００５３】
そして、次世代生成部６ｂは、一方の親世代における選択したインスタンスＩＤに対応するノードＩＤと、他方の親世代における選択したインスタンスＩＤに対応するノードＩＤとを入れ替えることで、２つの親世代を交叉させて２つの次世代を生成する。
【００５４】
ここで、図８に示す確率情報と、図１０に示す確率情報とを比較すると、次世代生成部６ｂは、次のようにインスタンスＩＤを選択することが分かる。すなわち、次世代生成部６ｂは、参照したフラグの値が「１」である場合には、フラグの値が「２」または「３」である場合よりも、モジュールの処理フローにおいてイベントが流れる方向における上流側のインスタンスのインスタンスＩＤを高い確率で選択する。そして、次世代生成部６ｂは、選択したインスタンスＩＤが示すインスタンスを配備するノードを変更することで、次世代を生成する。ここで、配備先のノードが変更されるインスタンスが、イベントが流れる方向における上流側であるほど、親世代と次世代とで評価値が大きく変動する可能性が高くなる。それゆえ、大域検索のモードでは、制約検索及び周辺検索の各モードよりも、親世代が示すようにノードにモジュールを配備させた場合の評価値に対して、次世代が示すようにノードにモジュールを配備させた場合の評価値が大きく変化する可能性が高くなる。
【００５５】
そして、次世代生成部６ｂは、所定の確率（０．１％〜５％）で、生成した次世代を突然変異させて新たな次世代を生成する。図１１は、次世代を突然変異させた結果得られた新たな次世代の一例を示す図である。例えば、次世代生成部６ｂは、図１１の例に示すように、図１０の例に示す「次世代１」（図１１中、上側の次世代）を、所定の変異数（例えば、「３」）分突然変異させて、新たな「次世代１」（図１１中、下側の次世代）を生成する。
【００５６】
なお、次世代生成部６ｂは、生成した次世代を、以下に説明するように、他の方法で、突然変異させて新たな次世代を生成することもできる。例えば、次世代生成部６ｂは、フラグの値が「１」である場合には、上述した大域検索の場合における確率情報が示す各インスタンスＩＤを選択する確率にしたがって、親世代のインスタンスＩＤを、所定の変異数（例えば、「３」）分だけ選択する。そして、次世代生成部６ｂは、所定の変異数分だけ、「１」〜「５」の範囲でランダムに整数を生成する。そして、次世代生成部６ｂは、選択したインスタンスＩＤに対応するノードＩＤの値を、生成した整数に変更することで、次世代を生成する。
【００５７】
そして、次世代生成部６ｂは、生成した２つの次世代を次世代記憶部５ｃに格納する。なお、次世代記憶部５ｃにすでに２つの次世代が記憶されている場合には、次世代生成部６ｂは、次世代記憶部５ｃにすでに記憶された２つの次世代を、生成した２つの次世代で更新する。
【００５８】
親世代選択部６ｃは、２つの次世代の中から新たな親世代を選択する。親世代選択部６ｃの一態様について説明する。例えば、親世代選択部６ｃは、まず、親世代記憶部５ｂに記憶された２つの親世代、及び、次世代記憶部５ｃに記憶された２つの次世代を取得する。そして、親世代選択部６ｃは、フラグ記憶部５ｇに記憶されたフラグを参照する。
【００５９】
参照したフラグの値が「１」である場合には、親世代選択部６ｃは、２つの親世代のそれぞれに対して、親世代が示すようにノードにインスタンスを配備してノードがインスタンスを実行する場合の評価値を算出する。さらに、親世代選択部６ｃは、２つの次世代のそれぞれに対して、次世代が示すようにノードにインスタンスを配備してノードがインスタンスを実行する場合の評価値を算出する。例えば、親世代選択部６ｃは、通信コストを算出するための評価関数を用いて、２つの親世代及び２つの次世代の各世代に対して、通信コストを算出する。
【００６０】
そして、親世代選択部６ｃは、２つの親世代及び２つの次世代の中から、評価値が示す評価が高い上位２つの世代を新たな親世代として選択する。例えば、評価値として通信コストを算出した場合には、通信コストが低いほど評価が高くなるので、親世代選択部６ｃは、２つの親世代及び２つの次世代の中から、評価値が低い上位２つの世代を新たな親世代として選択する。そして、親世代選択部６ｃは、親世代記憶部５ｂに、２つの新たな親世代を格納して、親世代記憶部５ｂに記憶される２つの親世代を更新する。
【００６１】
また、参照したフラグの値が「２」である場合には、親世代選択部６ｃは、２つの親世代のそれぞれに対して、親世代が示すようにノードにモジュールを配備してノードがインスタンスを実行する場合の制約評価値を算出する。さらに、親世代選択部６ｃは、２つの次世代のそれぞれに対して、次世代が示すようにノードにモジュールを配備してノードがインスタンスを実行する場合の制約評価値を算出する。
【００６２】
親世代選択部６ｃが算出する制約評価値の算出方法の一例について説明する。例えば、制約評価値は、自ノードに配備されたインスタンスを実行する場合における処理負荷が、処理能力を超えているノードの台数と、インスタンスが実行された場合における通信量が、通信帯域を超えている経路の数との和で表される。図１２、図１３、図１４及び図１５は、制約評価値の算出方法の一例を説明するための図である。
【００６３】
まず、図１２及び図１３を用いて、自ノードに配備されたインスタンスを実行する場合における処理負荷が処理能力を超えているノードの台数を算出する方法の一例について説明する。図１２には、インスタンスＩＤと、インスタンスＩＤが示すインスタンスを処理する場合における処理負荷との対応関係の一例が示されている。かかる処理負荷は、例えば、ノードでの処理実行中の負荷モニターから抽出したり、エミュレータでの仮想実行時の負荷を計測したり、インスタンスごとに定義する負荷見込み関数から算出したりすることにより得られる。上述したインスタンスＩＤと処理負荷との対応関係は、親世代選択部６ｃの内部メモリに予め記憶されている。
【００６４】
図１２の例に示す処理負荷Ｌ（ｉ）は、インスタンスＩＤ「ｉ」が示すインスタンスを処理する場合における処理負荷を示す。
【００６５】
例えば、図１２の例は、インスタンスＩＤ「１」が示すインスタンスを処理する場合における処理負荷が「１０」である場合を示す。また、図１２の例は、インスタンスＩＤ「２」が示すインスタンスを処理する場合における処理負荷が「１０」である場合を示す。
【００６６】
また、図１２の例は、インスタンスＩＤ「３」が示すインスタンスを処理する場合における処理負荷が「１０」である場合を示す。また、図１２の例は、インスタンスＩＤ「４」が示すインスタンスを処理する場合における処理負荷が「１５」である場合を示す。
【００６７】
また、図１２の例は、インスタンスＩＤ「５」が示すインスタンスを処理する場合における処理負荷が「１５」である場合を示す。また、図１２の例は、インスタンスＩＤ「６」が示すインスタンスを処理する場合における処理負荷が「２０」である場合を示す。
【００６８】
また、図１２の例は、インスタンスＩＤ「７」が示すインスタンスを処理する場合における処理負荷が「２０」である場合を示す。また、図１２の例は、インスタンスＩＤ「８」が示すインスタンスを処理する場合における処理負荷が「２０」である場合を示す。
【００６９】
図１３には、ノードＩＤと、ノードＩＤが示すノードの処理能力との対応関係の一例が示されている。かかる処理能力は、例えば、ＣＰＵ（Central  Processing  Unit）性能やベンチマーク結果から得られる。上述したノードＩＤと処理能力との対応関係は、親世代選択部６ｃの内部メモリに予め記憶されている。
【００７０】
図１３の例に示す処理能力Ｐ（ｎ）は、ノードＩＤ「ｎ」が示すノードの処理能力を示す。例えば、図１３の例は、ノードＩＤ「１」が示す処理能力が「３０」である場合を示す。また、図１３の例は、ノードＩＤ「２」が示す処理能力が「３０」である場合を示す。
【００７１】
また、図１３の例は、ノードＩＤ「３」が示す処理能力が「３０」である場合を示す。また、図１３の例は、ノードＩＤ「４」が示す処理能力が「４５」である場合を示す。また、図１３の例は、ノードＩＤ「５」が示す処理能力が「１０００」である場合を示す。
【００７２】
図１２及び図１３の例に示す各対応関係が親世代選択部６ｃの内部メモリに記憶されている場合に、先の図５の例に示すような親世代に対して、処理負荷が処理能力を超えているノードの台数を算出するときには、親世代選択部６ｃは、次の処理を行う。例えば、図５の例では、ノードＩＤ「１」が示すノードに、インスタンスＩＤ「１」及び「４」が示す各インスタンスが配備されるので、親世代選択部６ｃは、処理負荷Ｌ（１）と処理負荷Ｌ（４）との和が処理能力Ｐ（１）を超えているか判定する。処理負荷Ｌ（１）が「１０」であり、処理負荷Ｌ（４）が「１５」であり、処理能力Ｐ（１）が「３０」であるので、親世代選択部６ｃは、処理負荷Ｌ（１）と処理負荷Ｌ（４）との和が、処理能力Ｐ（１）を超えていないと判定する。
【００７３】
また、図５の例では、ノードＩＤ「２」が示すノードにインスタンスＩＤ「２」が示すインスタンスが配備されるので、親世代選択部６ｃは、処理負荷Ｌ（２）が処理能力Ｐ（２）を超えているか判定する。処理負荷Ｌ（２）が「１０」であり、処理能力Ｐ（２）が「３０」であるので、親世代選択部６ｃは、処理負荷Ｌ（２）が処理能力Ｐ（２）を超えていないと判定する。
【００７４】
また、図５の例では、ノードＩＤ「３」が示すノードにインスタンスＩＤ「３」が示すインスタンスが配備されるので、親世代選択部６ｃは、処理負荷Ｌ（３）が処理能力Ｐ（３）を超えているか判定する。処理負荷Ｌ（３）が「１０」であり、処理能力Ｐ（３）が「３０」であるので、親世代選択部６ｃは、処理負荷Ｌ（３）が処理能力Ｐ（３）を超えていないと判定する。
【００７５】
また、図５の例では、ノードＩＤ「４」が示すノードにインスタンスＩＤ「５」が示すインスタンスが配備されるので、親世代選択部６ｃは、処理負荷Ｌ（５）が処理能力Ｐ（４）を超えているか判定する。処理負荷Ｌ（５）が「１５」であり、処理能力Ｐ（４）が「４５」であるので、親世代選択部６ｃは、処理負荷Ｌ（５）が処理能力Ｐ（４）を超えていないと判定する。
【００７６】
また、図５の例では、ノードＩＤ「５」が示すノードに、インスタンスＩＤ「６」、「７」及び「８」が示す各インスタンスが配備されるので、親世代選択部６ｃは、次の処理を行う。すなわち、親世代選択部６ｃは、処理負荷Ｌ（６）と処理負荷Ｌ（７）と処理負荷Ｌ（８）との和が、処理能力Ｐ（５）を超えているか判定する。ここで、処理負荷Ｌ（６）、処理負荷Ｌ（７）及び処理負荷Ｌ（８）が「２０」であり、処理能力Ｐ（５）が「１０００」であるので、親世代選択部６ｃは、処理負荷Ｌ（６）と処理負荷Ｌ（７）と処理負荷（８）との和が、処理能力Ｐ（５）を超えていないと判定する。
【００７７】
以上のことから、処理負荷が処理能力を超えるノードの台数は「０」である。したがって、図１２及び図１３の例に示す各対応関係が内部メモリに記憶されている場合に、親世代選択部６ｃは、図５の例に示すような親世代に対して、処理負荷が処理能力を超えているノードの台数「０」を算出する。
【００７８】
次に、図１４及び図１５を用いて、インスタンスが実行された場合における通信量が、通信帯域を超えている経路の数を算出する方法の一例について説明する。図１４には、インスタンス間の２つのインスタンスＩＤを「‐」で連結したインスタンス間を識別するための連結ＩＤと、連結ＩＤが示すインスタンス間の通信量との対応関係の一例が示されている。かかる通信量は、例えば、ノードでの処理実行中の通信量モニターから抽出したり、エミュレータでの仮想実行時の通信量を計測したり、インスタンスごとに定義する入出力見込み関数から算出したりすることにより得られる。上述した連結ＩＤと通信量との対応関係は、親世代選択部６ｃの内部メモリに予め記憶されている。
【００７９】
図１４の例に示す通信量Ｔ（ｉ）は、連結ＩＤ「ｉ」が示すインスタンス間の通信量を示す。例えば、図１４の例は、連結ＩＤ「１‐４」が示すインスタンス間の通信量（インスタンスＩＤ「１」が示すインスタンスから、インスタンスＩＤ「４」が示すインスタンスへ流れるイベントの通信量）が「３０」である場合を示す。
【００８０】
また、図１４の例は、連結ＩＤ「２‐５」が示すインスタンス間の通信量（インスタンスＩＤ「２」が示すインスタンスから、インスタンスＩＤ「５」が示すインスタンスへ流れるイベントの通信量）が「３０」である場合を示す。
【００８１】
また、図１４の例は、連結ＩＤ「３‐５」が示すインスタンス間の通信量（インスタンスＩＤ「３」が示すインスタンスから、インスタンスＩＤ「５」が示すインスタンスへ流れるイベントの通信量）が「３０」である場合を示す。
【００８２】
また、図１４の例は、連結ＩＤ「４‐６」が示すインスタンス間の通信量（インスタンスＩＤ「４」が示すインスタンスから、インスタンスＩＤ「６」が示すインスタンスへ流れるイベントの通信量）が「５」である場合を示す。
【００８３】
また、図１４の例は、連結ＩＤ「４‐７」が示すインスタンス間の通信量（インスタンスＩＤ「４」が示すインスタンスから、インスタンスＩＤ「７」が示すインスタンスへ流れるイベントの通信量）が「５」である場合を示す。
【００８４】
また、図１４の例は、連結ＩＤ「５‐６」が示すインスタンス間の通信量（インスタンスＩＤ「５」が示すインスタンスから、インスタンスＩＤ「６」が示すインスタンスへ流れるイベントの通信量）が「５」である場合を示す。
【００８５】
また、図１４の例は、連結ＩＤ「５‐７」が示すインスタンス間の通信量（インスタンスＩＤ「５」が示すインスタンスから、インスタンスＩＤ「７」が示すインスタンスへ流れるイベントの通信量）が「５」である場合を示す。
【００８６】
また、図１４の例は、連結ＩＤ「５‐８」が示すインスタンス間の通信量（インスタンスＩＤ「５」が示すインスタンスから、インスタンスＩＤ「８」が示すインスタンスへ流れるイベントの通信量）が「１」である場合を示す。
【００８７】
図１５には、ノード間の２つのノードＩＤを「‐」で連結したノード間の経路を識別するための連結ＩＤと、連結ＩＤが示すノード間の経路の通信帯域との対応関係の一例が示されている。かかる通信帯域は、例えば、データ転送試験などから得られる。上述した連結ＩＤと通信帯域との対応関係は、親世代選択部６ｃの内部メモリに予め記憶されている。
【００８８】
図１５の例に示す通信帯域Ｂ（ｎ）は、連結ＩＤ「ｎ」が示すノード間の経路の通信帯域を示す。例えば、図１５の例は、連結ＩＤ「１‐４」が示すノードＩＤ「１」が示すノードとノードＩＤ「４」が示すノードとの間の経路の通信帯域が「３０」である場合を示す。また、図１５の例は、連結ＩＤ「２‐４」が示すノードＩＤ「２」が示すノードとノードＩＤ「４」が示すノードとの間の経路の通信帯域が「３０」である場合を示す。また、図１５の例は、連結ＩＤ「３‐４」が示すノードＩＤ「３」が示すノードとノードＩＤ「４」が示すノードとの間の経路の通信帯域が「３０」である場合を示す。また、図１５の例は、連結ＩＤ「４−５」が示すノードＩＤ「４」が示すノードとノードＩＤ「５」が示すノードとの間の経路の通信帯域が「４５」である場合を示す。
【００８９】
図１４及び図１５の例に示す各対応関係が親世代選択部６ｃの内部メモリに記憶されている場合に、先の図５の例に示すような親世代に対して、通信量が通信帯域を超えている経路の数を算出するときには、親世代選択部６ｃは、次の処理を行う。例えば、図５の例では、先の図６の例に示すように、ノードＩＤ「１」が示すノードとノードＩＤ「４」が示すノードとの間の経路に、インスタンスＩＤ「４」が示すインスタンスから、インスタンスＩＤ「６」が示すインスタンスへイベントが流れる。それゆえ、親世代選択部６ｃは、通信量Ｔ（４−６）が、通信帯域Ｂ（１−４）を超えているか判定する。通信量Ｔ（４−６）が「５」であり、通信帯域Ｂ（１−４）が「３０」であるので、親世代選択部６ｃは、通信量Ｔ（４−６）が、通信帯域Ｂ（１−４）を超えていないと判定する。なお、図５の例では、図６の例に示すように、インスタンスＩＤ「１」が示すインスタンスと、インスタンスＩＤ「４」が示すインスタントとは、同一のノードに配備される。このため、インスタンスＩＤ「１」が示すインスタンスと、インスタンスＩＤ「４」が示すインスタントとの間での通信は、経路を介したノード間では行われない。
【００９０】
また、図５の例では、先の図６の例に示すように、ノードＩＤ「２」が示すノードとノードＩＤ「４」が示すノードとの間の経路に、インスタンスＩＤ「２」が示すインスタンスから、インスタンスＩＤ「５」が示すインスタンスへイベントが流れる。それゆえ、親世代選択部６ｃは、通信量Ｔ（２−５）が、通信帯域Ｂ（２−４）を超えているか判定する。通信量Ｔ（２−５）が「３０」であり、通信帯域Ｂ（２−４）が「３０」であるので、親世代選択部６ｃは、通信量Ｔ（２−５）が、通信帯域Ｂ（２−４）を超えていないと判定する。
【００９１】
また、図５の例では、先の図６の例に示すように、ノードＩＤ「３」が示すノードとノードＩＤ「４」が示すノードとの間の経路に、インスタンスＩＤ「３」が示すインスタンスから、インスタンスＩＤ「５」が示すインスタンスへイベントが流れる。それゆえ、親世代選択部６ｃは、通信量Ｔ（３−５）が、通信帯域Ｂ（３−４）を超えているか判定する。通信量Ｔ（３−５）が「３０」であり、通信帯域Ｂ（３−４）が「３０」であるので、親世代選択部６ｃは、通信量Ｔ（３−５）が、通信帯域Ｂ（３−４）を超えていないと判定する。
【００９２】
また、図５の例では、先の図６の例に示すように、ノードＩＤ「４」が示すノードとノードＩＤ「５」が示すノードとの間の経路に、インスタンスＩＤ「４」が示すインスタンスから、インスタンスＩＤ「６」が示すインスタンスへイベントが流れる。また、図５の例では、先の図６の例に示すように、ノードＩＤ「４」が示すノードとノードＩＤ「５」が示すノードとの間の経路に、インスタンスＩＤ「４」が示すインスタンスから、インスタンスＩＤ「７」が示すインスタンスへイベントが流れる。また、図５の例では、先の図６の例に示すように、ノードＩＤ「４」が示すノードとノードＩＤ「５」が示すノードとの間の経路に、インスタンスＩＤ「５」が示すインスタンスから、インスタンスＩＤ「６」が示すインスタンスへイベントが流れる。また、図５の例では、先の図６の例に示すように、ノードＩＤ「４」が示すノードとノードＩＤ「５」が示すノードとの間の経路に、インスタンスＩＤ「５」が示すインスタンスから、インスタンスＩＤ「７」が示すインスタンスへイベントが流れる。それゆえ、親世代選択部６ｃは、通信量Ｔ（４−６）と通信量Ｔ（４−７）と通信量Ｔ（５−６）と通信量Ｔ（５−７）との和が、通信帯域Ｂ（４−５）を超えているか判定する。通信量Ｔ（４−６）、通信量Ｔ（４−７）、通信量Ｔ（５−６）及び通信量Ｔ（５−７）のそれぞれが「５」であり、通信帯域Ｂ（４−５）が「４５」であるので、親世代選択部６ｃは、通信量Ｔ（４−６）と通信量Ｔ（４−７）と通信量Ｔ（５−６）と通信量Ｔ（５−７）との和「２０」が、通信帯域Ｂ（４−５）を超えていないと判定する。なお、図５の例では、図６の例に示すように、インスタンスＩＤ「６」が示すインスタンスと、インスタンスＩＤ「８」が示すインスタントとは、同一のノードに配備される。このため、インスタンスＩＤ「６」が示すインスタンスと、インスタンスＩＤ「８」が示すインスタントとの間での通信は、経路を介したノード間では行われない。
【００９３】
以上のことから、インスタンスが実行された場合における通信量が通信帯域を超えている経路の数は「０」である。したがって、図１４及び図１５の例に示す各対応関係が内部メモリに記憶されている場合に、親世代選択部６ｃは、図５の例に示すような親世代に対してインスタンスが実行された場合における通信量が通信帯域を超えている経路の数「０」を算出する。
【００９４】
そして、親世代選択部６ｃは、処理負荷が処理能力を超えているノードの台数「０」と、通信量が通信帯域を超えている経路の数「０」との和「０」を制約評価値として算出する。
【００９５】
なお、親世代選択部６ｃは、処理負荷が処理能力を超えているノードの台数と、通信量が通信帯域を超えている経路の数とを、所定の重み定数で重み付けした値を制約評価値として算出することもできる。ここで、所定の重み定数について説明する。図１６は、所定の重み定数の一例を示す図である。図１６の例では、処理負荷が処理能力を超えているノードの台数に対する重み付け定数が「１」であり、通信量が通信帯域を超えている経路の数に対する重み付け定数が「５」である場合を示す。ここで、処理負荷が処理能力を超えているノードについては、周辺のノードにイベントの処理を移すことで簡易に処理負荷が処理能力を超えないようにすることができる。しかしながら、通信量が通信帯域を超えている経路については、高圧縮処理のインスタンスを配備したり、迂回路がある場合に迂回路上のノードにインスタンスを配備したりするなどの煩雑な処理を行うことで、通信量が通信帯域を超えないようにすることができる。それゆえ、通信量が通信帯域を超えている経路について通信量が通信帯域を超えないようにするために解を変更する場合は、処理負荷が処理能力を超えているノードについて処理負荷が処理能力を超えないように解を変更する場合と比べて、解が大幅に変更される。すなわち、通信量が通信帯域を超えている経路について通信量が通信帯域を超えないようにする場合は、処理負荷が処理能力を超えているノードについて処理負荷が処理能力を超えないようにする場合と比べて、困難であるといえる。そのため、本実施例では、処理負荷が処理能力を超えているノードの台数に対する重み付け定数よりも、通信量が通信帯域を超えている経路の数に対する重み付け定数を大きくすることで、通信量が通信帯域を超えているような違反の数が少なくなるようにする。
【００９６】
また、親世代選択部６ｃは、以下に説明するように、他の方法によって、制約評価値を算出することもできる。例えば、親世代選択部６ｃは、まず、自ノードに配備されたインスタンスを実行する場合におけるメモリの使用量が、自ノードのメモリの容量を超えているノードの台数を算出する。そして、親世代選択部６ｃは、インスタンスが実行された場合における通信レイテンシが、インスタンスごとに定められたレイテンシを超えているインスタンスの数を算出する。そして、親世代選択部６ｃは、算出したノードの台数と算出したインスタンスの数との和を制約評価値として算出する。
【００９７】
親世代選択部６ｃは、上述したメモリの使用量が自ノードのメモリの容量を超えているノードの台数と、上述した通信レイテンシがインスタンスごとに定められたレイテンシを超えているインスタンスの数とを重み付けして、制約評価値を算出することもできる。この際に用いられる重み付け定数は、例えば、図１６に示すように、上述したメモリの使用量が自ノードのメモリの容量を超えているノードの台数に対しては、「１」である。また、上述した通信レイテンシがインスタンスごとに定められたレイテンシを超えているインスタンスの数に対しては、「５」である。この「１」と「５」のように、重み付け定数が異なる理由は、処理負荷が処理能力を超えているノードの台数に対する重み付け定数と通信量が通信帯域を超えている経路の数に対する重み付け定数とが異なる上述した理由と同様である。
【００９８】
そして、親世代選択部６ｃは、２つの親世代及び２つの次世代の中から、制約評価値が示す、制約に違反した数が少ない上位２つの世代を新たな親世代として選択する。例えば、制約評価値として、上述した処理負荷が処理能力を超えているノードの台数と、通信量が通信帯域を超えている経路の数との和を算出した場合には、かかる和の値が小さいほど制約に違反した数が少なくなる。そのため、親世代選択部６ｃは、２つの親世代及び２つの次世代の中から、制約評価値が小さい上位２つの世代を新たな親世代として選択する。そして、親世代選択部６ｃは、親世代記憶部５ｂに、２つの新たな親世代を格納して、親世代記憶部５ｂに記憶される２つの親世代を更新する。
【００９９】
また、参照したフラグの値が「３」である場合には、親世代選択部６ｃは、参照したフラグの値が「１」である場合と同様に、２つの親世代及び２つの次世代のそれぞれに対して、上述した評価値を算出する。また、参照したフラグの値が「３」である場合には、親世代選択部６ｃは、参照したフラグの値が「２」である場合と同様に、２つの親世代及び２つの次世代のそれぞれに対して、上述した制約評価値を算出する。
【０１００】
そして、親世代選択部６ｃは、評価値と制約評価値との和を新たな評価値として算出する。そして、親世代選択部６ｃは、新たな評価値が示す評価が高い上位２つの世代を新たな親世代として選択する。例えば、新たな評価値が小さくなるほど、評価が高くなる場合には、親世代選択部６ｃは、新たな評価値が小さい上位２つの世代を新たな親世代として選択する。そして、親世代選択部６ｃは、親世代記憶部５ｂに、２つの新たな親世代を格納して、親世代記憶部５ｂに記憶される２つの親世代を更新する。
【０１０１】
なお、親世代選択部６ｃは、評価値と制約評価値とに対して所定の重み付けを行うことにより新たな評価値を算出し、２つの親世代及び２つの次世代の中から、算出した評価値が示す評価が高い上位２つの世代を新たな親世代として選択することもできる。
【０１０２】
また、親世代選択部６ｃは、２つの親世代及び２つの次世代の中から、制約評価値が示す制約に違反した数が所定値（例えば３）以下の世代を特定し、特定した世代の中から、評価値が示す評価が高い上位２つの世代を新たな親世代として選択することもできる。
【０１０３】
上述したように、参照したフラグの値が「１」、「２」及び「３」のいずれかの場合において、新たな親世代を親世代記憶部５ｂに格納した後、親世代選択部６ｃは、終了条件を満たすか否かを判定する。例えば、親世代選択部６ｃは、新たな親世代が所定回数以上更新されたか否かを判定し、新たな親世代が所定回数以上更新された場合には、終了条件を満たすと判定し、新たな親世代が所定回数以上更新されていない場合には、終了条件を満たさないと判定する。親世代選択部６ｃは、新たな親世代が所定回数以上更新されている間に、後述の最適解が更新されたか否かを判定し、最適解が更新された場合には終了条件を満たさないと判定し、最適解が更新されていない場合には終了条件を満たすと判定することもできる。
【０１０４】
モード判定部６ｄは、モジュール配備決定処理におけるモードを判定する。モード判定部６ｄの一態様について説明する。モード判定部６ｄは、親世代選択部６ｃにより終了条件を満たさないと判定されると、まず、フラグ記憶部５ｇに記憶されたフラグの値を参照する。そして、モード判定部６ｄは、参照したフラグの値が「２」であるか否かを判定することにより、モジュール配備決定処理におけるモードが制約検索であるか否かを判定する。
【０１０５】
モジュール配備決定処理におけるモードが制約検索であると判定した場合には、モード判定部６ｄは、親世代記憶部５ｂに記憶された２つの親世代を取得する。そして、モード判定部６ｄは、取得した２つの親世代が、制約評価値が示す、制約に違反した数が０であるか否かを判定する。２つの親世代とも、制約評価値が示す、制約に違反した数が０であると判定した場合には、モード判定部６ｄは、フラグ記憶部５ｇに記憶されたフラグの値を「３」に更新して、モジュール配備決定処理におけるモードを周辺検索のモードに設定する。
【０１０６】
一方、モジュール配備決定処理におけるモードが制約検索でないと判定した場合には、モード判定部６ｄは、次世代が所定回数以上更新されている間に、親世代が更新されたか否かを判定する。次世代が所定回数以上更新されている間に、親世代が更新されていないと判定した場合には、モード判定部６ｄは、参照したフラグの値が「１」であるか否かを判定することにより、モジュール配備決定処理におけるモードが大域検索であるか否かを判定する。大域検索であると判定した場合には、モード判定部６ｄは、フラグ記憶部５ｇに記憶されたフラグの値を「２」に更新して、モジュール配備決定処理におけるモードを制約検索のモードに設定する。
【０１０７】
また、大域検索でないと判定した場合には、モジュール配備決定処理におけるモードは、周辺検索である。この場合、モード判定部６ｄは、フラグ記憶部５ｇに記憶されたフラグの値を「１」に更新して、モジュール配備決定処理におけるモードを大域検索に設定する。また、最適解更新部６ｅにより最適解が更新された場合、または、２つの親世代の中に、制約評価値が示す、制約に違反した数が０であり、現在の最適解よりも評価が高い（評価値が低い）親世代が存在しないと判定された場合に、モード判定部６ｄは次の処理を行う。すなわち、モード判定部６ｄは、親世代記憶部５ｂに記憶された２つの親世代を取得し、取得した親世代のそれぞれを突然変異させて新たな２つの親世代を生成する。そして、モード判定部６ｄは、親世代記憶部５ｂに、２つの新たな親世代を格納して、親世代記憶部５ｂに記憶される２つの親世代を更新する。
【０１０８】
最適解更新部６ｅは、最適解を更新する。最適解更新部６ｅの一態様について説明する。例えば、最適解更新部６ｅは、モード判定部６ｄにより、フラグ記憶部５ｇに記憶されたフラグの値が「１」に更新されて、モジュール配備決定処理におけるモードが大域検索に設定されると、次の処理を行う。すなわち、最適解更新部６ｅは、親世代記憶部５ｂに記憶された２つの親世代を取得する。そして、最適解更新部６ｅは、取得した２つの親世代の中に、制約評価値が示す、制約に違反した数が０であり、かつ、最適解記憶部５ａに記憶された最適解よりも評価が高い親世代が存在するか否かを判定する。
【０１０９】
取得した２つの親世代の中に、制約評価値が示す、制約に違反した数が０であり、かつ、最適解記憶部５ａに記憶された最適解よりも評価が高い親世代が存在すると判定した場合には、最適解更新部６ｅは、次の処理を行う。すなわち、最適解更新部６ｅは、制約に違反した数が０であり、かつ、最適解記憶部５ａに記憶された最適解よりも評価が高い親世代を、最適解として最適解記憶部５ａに格納し、最適解記憶部５ａに記憶される最適解を更新する。
【０１１０】
最適解出力制御部６ｆは、最適解を出力するように制御する。最適解出力制御部６ｆの一態様について説明する。最適解出力制御部６ｆは、親世代選択部６ｃにより終了条件を満たさないと判定されると、最適解記憶部５ａに記憶された最適解を取得し、取得した最適解を表示するように、出力部３を制御する。これにより、最適解が出力部３に表示される。
【０１１１】
モジュール出力制御部６ｇは、インスタンスを下位ノードに出力するように制御する。モジュール出力制御部６ｇの一態様について説明する。モジュール出力制御部６ｇは、入力部２から最適解が示すようにインスタンスをノードに配備する指示が入力されると、最適解記憶部５ａから最適解を取得する。そして、モジュール出力制御部６ｇは、モジュール記憶部５ｅから全てのインスタンスを取得する。そして、モジュール出力制御部６ｇは、最適解が示すようにインスタンスをノードに送信する指示を通信部４に送信する。これにより、通信部４が、最適解が示すようにインスタンスをノードに送信する。なお、インスタンスを受信した各ノードは、受信したインスタンスを自ノードに配備する。
【０１１２】
センサノード２１の機能構成について説明する。図１７Ａは、実施例に係るセンサノードの機能構成の一例を示す図である。図１７Ａに示すように、センサノード２１は、制御部７０を有する。制御部７０は、センサノード２１に搭載されたセンサによってセンシングされたデータをイベントとして、ＧＷノード２２及びネットワーク２３を介して、サーバノード１へ送信する。また、制御部７０は、サーバノード１から送信されたインスタンスを受信すると、受信したインスタンスを自ノードに配備する。これにより、制御部７０は、受信したインスタンスを実行することができる。
【０１１３】
次に、ＧＷノード２２の機能構成について説明する。図１７Ｂは、実施例に係るＧＷノードの機能構成の一例を示す図である。図１７Ｂに示すように、ＧＷノード２２は、制御部７１を有する。制御部７１は、センサノード２１から送信されたイベントを受信すると、受信したイベントをネットワーク２３を介して、サーバノード１へ送信する。また、制御部７１は、サーバノード１から送信されたインスタンスを受信すると、受信したインスタンスを自ノードに配備する。これにより、制御部７１は、受信したインスタンスを実行することができる。
【０１１４】
［処理の流れ］
次に、実施例に係るサーバノード１が実行するモジュール配備決定処理の流れについて説明する。図１８Ａ及び図１８Ｂは、実施例に係るモジュール配備決定処理の手順を示すフローチャートである。実施例に係るモジュール配備決定処理は、例えば、入力部２から、モジュール配備決定処理を実行するための指示が制御部６に入力された場合に、制御部６により実行される。
【０１１５】
図１８Ａに示すように、初期解生成部６ａは、トポロジ記憶部５ｄからトポロジを取得する（Ｓ１０１）。そして、初期解生成部６ａは、モジュール定義記憶部５ｆから、モジュール定義記憶部５ｆに記憶された定義を取得する（Ｓ１０２）。
【０１１６】
そして、初期解生成部６ａは、初期解を生成する（Ｓ１０３）。そして、初期解生成部６ａは、生成した初期解を１つ目の親世代として、親世代記憶部５ｂに格納する（Ｓ１０４）。  
【０１１７】
そして、初期解生成部６ａは、遺伝的アルゴリズムを用いて、１つ目の親世代から、突然変異によって新たな解を生成する（Ｓ１０５）。そして、初期解生成部６ａは、生成した解を２つ目の親世代として親世代記憶部５ｂに格納する（Ｓ１０６）。
【０１１８】
そして、初期解生成部６ａは、フラグ記憶部５ｇに記憶されたフラグに「１」を設定する（Ｓ１０７）。そして、次世代生成部６ｂは、フラグ記憶部５ｇに記憶されたフラグを参照する（Ｓ１０８）。
【０１１９】
そして、次世代生成部６ｂは、フラグの値が「１」であるか否かを判定する（Ｓ１０９）。フラグの値が「１」である場合（Ｓ１０９；Ｙｅｓ）には、次世代生成部６ｂは、親世代記憶部５ｂに記憶された２つの親世代を取得する（Ｓ１１０）。そして、次世代生成部６ｂは、大域検索の場合における確率情報が示す各インスタンスＩＤを選択する確率（交叉選択確率）にしたがって、２つの親世代のインスタンスＩＤを、所定の交叉数（例えば、「３」）分だけ選択する（Ｓ１１１）。
【０１２０】
次世代生成部６ｂは、一方の親世代における選択したインスタンスＩＤに対応するノードＩＤと、他方の親世代における選択したインスタンスＩＤに対応するノードＩＤとを入れ替えることで、２つの親世代を交叉させて２つの次世代を生成する（Ｓ１１２）。
【０１２１】
次世代生成部６ｂは、フラグの値が「１」でない場合（Ｓ１０９；Ｎｏ）、すなわち、フラグの値が「２」または「３」である場合には、親世代記憶部５ｂに記憶された２つの親世代を取得する（Ｓ１１３）。そして、次世代生成部６ｂは、制約検索及び周辺検索の場合における確率情報が示す各インスタンスＩＤを選択する確率（交叉選択確率）にしたがって、２つの親世代のインスタンスＩＤを、所定の交叉数（例えば、「３」）分だけ選択する（Ｓ１１４）。
【０１２２】
次世代生成部６ｂは、一方の親世代における選択したインスタンスＩＤに対応するノードＩＤと、他方の親世代における選択したインスタンスＩＤに対応するノードＩＤとを入れ替えることで、２つの親世代を交叉させて２つの次世代を生成する（Ｓ１１５）。
【０１２３】
そして、次世代生成部６ｂは、所定の確率（０．１％〜５％）で、生成した次世代を突然変異させて新たな次世代を生成する（Ｓ１１６）。
【０１２４】
そして、次世代生成部６ｂは、生成した２つの次世代を次世代記憶部５ｃに格納する（Ｓ１１７）。なお、次世代記憶部５ｃにすでに２つの次世代が記憶されている場合には、次世代生成部６ｂは、次世代記憶部５ｃにすでに記憶された２つの次世代を、生成した２つの次世代で更新する。
【０１２５】
そして、親世代選択部６ｃは、親世代記憶部５ｂに記憶された２つの親世代、及び、次世代記憶部５ｃに記憶された２つの次世代を取得する（Ｓ１１８）。そして、親世代選択部６ｃは、フラグ記憶部５ｇに記憶されたフラグを参照する（Ｓ１１９）。
【０１２６】
そして、図１８Ｂに示すように、親世代選択部６ｃは、フラグの値が「１」であるか否かを判定する（Ｓ１２０）。フラグの値が「１」である場合（Ｓ１２０；Ｙｅｓ）には、親世代選択部６ｃは、２つの親世代のそれぞれに対して、親世代が示すようにノードにインスタンスを配備してノードがインスタンスを実行する場合の評価値を算出する。さらに、親世代選択部６ｃは、２つの次世代のそれぞれに対して、次世代が示すようにノードにインスタンスを配備してノードがインスタンスを実行する場合の評価値を算出する（Ｓ１２１）。
【０１２７】
そして、親世代選択部６ｃは、２つの親世代及び２つの次世代の中から、評価値が示す評価が高い上位２つの世代を新たな親世代として選択する（Ｓ１２２）。そして、親世代選択部６ｃは、親世代記憶部５ｂに、２つの新たな親世代を格納して、親世代記憶部５ｂに記憶される２つの親世代を更新する（Ｓ１２３）。
【０１２８】
また、フラグの値が「１」でない場合（Ｓ１２０；Ｎｏ）には、親世代選択部６ｃは、フラグの値が「２」であるか否かを判定する（Ｓ１２４）。フラグの値が「２」である場合（Ｓ１２４；Ｙｅｓ）には、親世代選択部６ｃは、２つの親世代のそれぞれに対して、親世代が示すようにノードにモジュールを配備してノードがインスタンスを実行する場合の制約評価値を算出する。さらに、親世代選択部６ｃは、２つの次世代のそれぞれに対して、次世代が示すようにノードにモジュールを配備してノードがインスタンスを実行する場合の制約評価値を算出する（Ｓ１２５）。
【０１２９】
そして、親世代選択部６ｃは、２つの親世代及び２つの次世代の中から、制約評価値が示す、制約に違反した数が少ない上位２つの世代を新たな親世代として選択する（Ｓ１２６）。そして、親世代選択部６ｃは、親世代記憶部５ｂに、２つの新たな親世代を格納して、親世代記憶部５ｂに記憶される２つの親世代を更新する（Ｓ１２７）。
【０１３０】
また、フラグの値が「２」でない場合（Ｓ１２４；Ｎｏ）、すなわち、フラグの値が「３」である場合には、親世代選択部６ｃは、次の処理を行う。すなわち、親世代選択部６ｃは、参照したフラグの値が「１」である場合と同様に、２つの親世代及び２つの次世代のそれぞれに対して、上述した評価値を算出する（Ｓ１２８）。また、親世代選択部６ｃは、参照したフラグの値が「２」である場合と同様に、２つの親世代及び２つの次世代のそれぞれに対して、上述した制約評価値を算出する（Ｓ１２９）。
【０１３１】
そして、親世代選択部６ｃは、評価値と制約評価値とから新たな評価値を算出する（Ｓ１３０）。そして、親世代選択部６ｃは、新たな評価値が示す評価が高い上位２つの世代を新たな親世代として選択する（Ｓ１３１）。そして、親世代選択部６ｃは、親世代記憶部５ｂに、２つの新たな親世代を格納して、親世代記憶部５ｂに記憶される２つの親世代を更新する（Ｓ１３２）。
【０１３２】
そして、親世代選択部６ｃは、上述した終了条件を満たすか否かを判定する（Ｓ１３３）。終了条件を満たさない場合（Ｓ１３３；Ｎｏ）には、モード判定部６ｄは、フラグ記憶部５ｇに記憶されたフラグの値を参照する（Ｓ１３４）。そして、モード判定部６ｄは、参照したフラグの値が「２」であるか否かを判定することにより、モジュール配備決定処理におけるモードが制約検索であるか否かを判定する（Ｓ１３５）。
【０１３３】
モードが制約検索である場合（Ｓ１３５；Ｙｅｓ）には、モード判定部６ｄは、親世代記憶部５ｂに記憶された２つの親世代を取得する（Ｓ１３６）。そして、モード判定部６ｄは、取得した２つの親世代が、制約評価値が示す、制約に違反した数が０であるか否かを判定する（Ｓ１３７）。２つの親世代とも、制約評価値が示す、制約に違反した数が０である場合（Ｓ１３７；Ｙｅｓ）には、モード判定部６ｄは、次の処理を行う。すなわち、モード判定部６ｄは、フラグ記憶部５ｇに記憶されたフラグの値を「３」に更新して、モジュール配備決定処理におけるモードを周辺検索のモードに設定し（Ｓ１３８）、Ｓ１０８に戻る。また、２つの親世代うち少なくとも１つの親世代が、制約評価値が示す、制約に違反した数が０でない場合（Ｓ１３７；Ｎｏ）にも、モード判定部６ｄは、Ｓ１０８に戻る。
【０１３４】
一方、モードが制約検索でない場合（Ｓ１３５；Ｎｏ）には、モード判定部６ｄは、次世代が所定回数以上更新されている間に、親世代が更新されたか否かを判定する（Ｓ１３９）。次世代が所定回数以上更新されている間に、親世代が更新されていない場合（Ｓ１３９；Ｎｏ）には、モード判定部６ｄは、次の処理を行う。すなわち、モード判定部６ｄは、参照したフラグの値が「１」であるか否かを判定することにより、モジュール配備決定処理におけるモードが大域検索であるか否かを判定する（Ｓ１４０）。モードが大域検索である場合（Ｓ１４０；Ｙｅｓ）には、モード判定部６ｄは、フラグ記憶部５ｇに記憶されたフラグの値を「２」に更新して、モジュール配備決定処理におけるモードを制約検索のモードに設定し（Ｓ１４１）、Ｓ１０８に戻る。
【０１３５】
また、次世代が所定回数以上更新されている間に、親世代が更新されている場合（Ｓ１３９；Ｙｅｓ）には、モード判定部６ｄは、Ｓ１０８に戻る。
【０１３６】
また、モードが大域検索でない場合（Ｓ１４０；Ｎｏ）には、モード判定部６ｄは、フラグ記憶部５ｇに記憶されたフラグの値を「１」に更新して、モジュール配備決定処理におけるモードを大域検索に設定する（Ｓ１４２）。そして、最適解更新部６ｅは、親世代記憶部５ｂに記憶された２つの親世代を取得する（Ｓ１４３）。そして、最適解更新部６ｅは、取得した２つの親世代の中に、制約評価値が示す、制約に違反した数が０であり、かつ、最適解記憶部５ａに記憶された最適解よりも評価が高い親世代が存在するか否かを判定する（Ｓ１４４）。
【０１３７】
取得した２つの親世代の中に、制約評価値が示す、制約に違反した数が０であり、かつ、最適解記憶部５ａに記憶された最適解よりも評価が高い親世代が存在する場合（Ｓ１４４；Ｙｅｓ）には、最適解更新部６ｅは、次の処理を行う。すなわち、最適解更新部６ｅは、制約に違反した数が０であり、かつ、最適解記憶部５ａに記憶された最適解よりも評価が高い親世代を最適解として最適解記憶部５ａに格納し、最適解記憶部５ａに記憶される最適解を更新する（Ｓ１４５）そして、最適解更新部６ｅは、Ｓ１０８に戻る。
【０１３８】
また、取得した２つの親世代の中に、制約評価値が示す、制約に違反した数が０であり、かつ、最適解記憶部５ａに記憶された最適解よりも評価が高い親世代が存在しない場合（Ｓ１４４；Ｎｏ）には、最適解更新部６ｅは、Ｓ１０８に戻る。
【０１３９】
また、終了条件を満たさない場合（Ｓ１３３；Ｎｏ）には、最適解出力制御部６ｆは、最適解記憶部５ａに記憶された最適解を取得し、取得した最適解を表示するように、出力部３を制御し（Ｓ１４６）、モジュール配備決定処理を終了する。
【０１４０】
図１９は、実施例に係るサーバノードが実行する処理の一例を説明するための図である。図１９の例は、親世代及び次世代の各解が領域９０の中心に位置するほど評価値が低くなり（評価が高くなり）、各解が領域９０の中心から外れるほど評価値が高くなる（評価が低くなる）ような場合を示す。なお、評価値が低くなるほど評価が高くなり、評価値が高くなるほど評価が低くなるような評価値は、例えば、コストの値などであり、このような評価値は、コスト評価値とも称される。また、図１９の例では、有制約領域９１は、制約に違反する数が０以上となる領域を示し、この領域に解が存在するときは制約違反となる。図１９の例に示すように、サーバノード１は、大域検索のモードにおいて、評価値及び制約評価値のうち、制約評価値については無視して、評価値に基づいて、評価が高くなるように解を次々と生成する。そして、サーバノード１は、制約検索のモードにおいて、評価値及び制約評価値のうち、評価値については無視して、制約評価値に基づいて、制約に違反する数がより少なくなるように解を次々と生成する。そして、サーバノード１は、周辺検索のモードにおいて、評価値及び制約評価値に基づいて、制約に違反する数が０であり、かつ、評価値が最も低くなるような最適解を決定する。そのため、従来技術のように、下位ノードと、下位ノードに対して配備されたイベントを処理するモジュールとの全ての組合せについて各種の評価値を算出することなく、どのノードにどのモジュールを配備するかを決定することができる。したがって、実施例に係るサーバノード１によれば、簡易に、どのノードにどのモジュールを配備するかを決定することができる。
【０１４１】
また、サーバノード１は、モードが大域検索のモードである場合には、制約検索のモード及び周辺検索のモードよりも、モジュールの処理フローにおいてイベントが流れる方向における上流側のインスタンスのインスタンスＩＤを高い確率で選択する。そして、サーバノード１は、選択したインスタンスＩＤが示すインスタンスを配備するノードを変更することで、次世代を生成する。上述したように、配備先のノードが変更されるインスタンスが、イベントが流れる方向における上流側であるほど、親世代と次世代とで評価値が大きく変動する可能性が高くなる。それゆえ、サーバノード１は、大域検索のモードである場合には、制約検索のモード及び周辺検索のモードよりも、解を大きく変化させることができる。
【０１４２】
また、サーバノード１は、モードが制約検索のモードである場合に、処理負荷が処理能力を超えているノードの台数と、通信量が通信帯域を超えている経路の数とを、所定の重み定数で重み付けした値を制約評価値として算出する。例えば、処理負荷が処理能力を超えているノードの台数に対する重み付け定数よりも、通信量が通信帯域を超えている経路の数に対する重み付け定数を大きくすることで、優先的に通信量が通信帯域を超えているような違反の数が少なくなるようにすることができる。
【０１４３】
なお、本実施例に係るサーバノード１は、モードの観点から機能的に表すと、各モードに対応する処理部を有する。図２０は、実施例に係るサーバノードの機能構成の他の例を示すブロック図である。図２０の例に示すように、サーバノード１は、第１の決定部８０、第２の決定部８０、第３の決定部８０を有する。第１の決定部８０は、大域検索のモードにおける各処理を実行する処理部である。第２の決定部８１は、制約検索のモードにおける各処理を実行する処理部である。第３の決定部８２は、周辺検索のモードにおける各処理を実行する処理部である。
【０１４４】
さて、これまで開示の装置に関する実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。
【０１４５】
例えば、サーバノード１は、モードが周辺検索のモードである場合に、突然変異を行って次世代を生成する際には、親世代と次世代とが制約評価値という観点から近くに位置するように、次のような処理を行うこともできる。すなわち、サーバノード１は、突然変異対象のインスタンスＩＤが配備されたノードからの他のノードのホップ数を算出する。そして、サーバノード１は、他のノードごとに、他のノードのホップ数の逆数を選択優先度として算出する。そして、サーバノード１は、他のノードごとに、選択優先度を他の全てのノードの選択優先度の総和で除した値（選択優先度／他の全てのノードの選択優先度の総和）を、選択確率として算出する。そして、サーバノード１は、選択確率にしたがって、他のノードを選択し、選択したノードのノードＩＤを突然変異対象のインスタンスＩＤが配備されるノードのノードＩＤに設定する。これにより、サーバノード１は、モードが周辺検索のモードである場合に、親世代と次世代とが制約評価値という観点から近くに位置するように、突然変異を行うことができる。
【０１４６】
また、各実施例において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともできる。また、各実施例において説明した各処理のうち、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。
【０１４７】
また、各種の負荷や使用状況などに応じて、各実施例において説明した各処理の各ステップでの処理を任意に細かくわけたり、あるいはまとめたりすることができる。また、ステップを省略することもできる。
【０１４８】
また、各種の負荷や使用状況などに応じて、各実施例において説明した各処理の各ステップでの処理の順番を変更できる。
【０１４９】
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的状態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。
【０１５０】
［モジュール配備決定プログラム］
また、上記の各実施例で説明したサーバノード１の各種の処理は、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータシステムで実行することによって実現することもできる。そこで、以下では、図２１を用いて、上記の実施例で説明したサーバノード１と同様の機能を有するモジュール配備決定プログラムを実行するコンピュータの一例を説明する。図２１は、モジュール配備決定プログラムを実行するコンピュータを示す図である。
【０１５１】
図２１に示すように、コンピュータ３００は、ＣＰＵ３１０、ＲＯＭ３２０、ＨＤＤ（Hard  Disk  Drive）３３０、ＲＡＭ３４０を有する。これら各機器３１０〜３４０は、バス３５０を介して接続されている。
【０１５２】
ＲＯＭ３２０には、ＯＳ（Operating  System）などの基本プログラムが記憶されている。また、ＨＤＤ３３０には、初期解生成部６ａと、次世代生成部６ｂと、親世代選択部６ｃと、モード判定部６ｄと、最適解更新部６ｅと、最適解出力制御部６ｆと、モジュール出力制御部６ｇと同様の機能を発揮するモジュール配備決定プログラム３３０ａが予め記憶される。
【０１５３】
そして、ＣＰＵ３１０が、モジュール配備決定プログラム３３０ａをＨＤＤ３３０から読み出して実行する。
【０１５４】
なお、上記したモジュール配備決定プログラム３３０ａについては、必ずしも最初からＨＤＤ３３０に記憶させておく必要はない。
【０１５５】
例えば、コンピュータ３００に挿入されるフレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ、ＤＶＤディスク、光磁気ディスク、ＩＣカードなどの「可搬用の物理媒体」にモジュール配備決定プログラム３３０ａを記憶させておく。そして、コンピュータ３００がこれらからモジュール配備決定プログラム３３０ａを読み出して実行するようにしてもよい。
【０１５６】
さらには、公衆回線、インターネット、ＬＡＮ、ＷＡＮなどを介してコンピュータ３００に接続される「他のコンピュータ（またはサーバ）」などにモジュール配備決定プログラム３３０ａを記憶させておく。そして、コンピュータ３００がこれらからモジュール配備決定プログラム３３０ａを読み出して実行するようにしてもよい。
【符号の説明】
【０１５７】
１        サーバノード
５ａ      最適解記憶部
５ｂ      親世代記憶部
５ｃ      次世代記憶部
５ｄ      トポロジ記憶部
５ｆ      モジュール定義記憶部
５ｇ      フラグ記憶部
６        制御部
６ａ      初期解生成部
６ｂ      次世代生成部
６ｃ      親世代選択部
６ｄ      モード判定部
６ｅ      最適解更新部
６ｆ      最適解出力制御部
【図１】
2015019338.tif 000003
【図２】
2015019338.tif 000004
【図３】
2015019338.tif 000005
【図４】
2015019338.tif 000006
【図５】
2015019338.tif 000007
【図６】
2015019338.tif 000008
【図７】
2015019338.tif 000009
【図８】
2015019338.tif 000010
【図９】
2015019338.tif 000011
【図１０】
2015019338.tif 000012
【図１１】
2015019338.tif 000013
【図１２】
2015019338.tif 000014
【図１３】
2015019338.tif 000015
【図１４】
2015019338.tif 000016
【図１５】
2015019338.tif 000017
【図１６】
2015019338.tif 000018
【図１７Ａ】
2015019338.tif 000019
【図１７Ｂ】
2015019338.tif 000020
【図１８Ａ】
2015019338.tif 000021
【図１８Ｂ】
2015019338.tif 000022
【図１９】
2015019338.tif 000023
【図２０】
2015019338.tif 000024
【図２１】
2015019338.tif 000025