(57)【要約】【課題】  ネットワーク設計条件の評価に要する計算機処理量の抑制を図る。【解決手段】  トポロジーモデル設定部１０１が設定したトポロジーモデルに対してランダムモデル試行部１０２が複数の接続確率に対するランダムモデルを生成し、Ｐ０決定部１０３が各接続確率のランダムモデルにおける接続ノード数を判定し、接続ノード数が大幅に増加する接続確率に基づいて臨界接続確率Ｐ０を決定し、決定した臨界接続確率Ｐ０をＰ０記憶部１０４に記憶させ、入力部１０５が入力したネットワーク設計条件に従って、対象ネットワークＰ導出部１０６が対象ネットワークの接続確率Ｐを導出し、設計条件評価部１０７が対象ネットワークＰ導出部１０６により導出された対象ネットワークの接続確率ＰとＰ０記憶部１０４に記憶されているＰ０とを比較し、対象ネットワークの接続確率ＰがＰ０より大きい場合に、出力部１０８が高接続条件との評価結果を出力する。【選択図】        図３
2006186447.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードと複数のリンク候補から構成されるトポロジーモデルを設定するトポロジーモデル設定部と、
前記トポロジーモデルに含まれる複数のノードのそれぞれが接続可能性のある他のノードと所定の接続確率で接続すると仮定した場合のネットワークモデルであって、複数のリンク候補のうちの少なくともいずれか一つが有効になり少なくとも二つのノード間にリンクが設定されているネットワークモデルを、複数の接続確率に対して生成するネットワークモデル生成部と、
前記ネットワークモデル生成部により複数の接続確率に対して生成されたネットワークモデルごとに、ネットワークモデルを解析し、ネットワークモデル内でリンクを介して接続されている接続ノード数の値を判定する接続判定部と、
前記複数の接続確率の大小関係の順序に対応させて、前記接続判定部により判定された複数個の接続ノード数の値の変化状況を解析し、変化状況の解析結果に基づいて、ネットワーク設計の設計条件を評価する際の閾値となる閾値接続確率を設定する閾値接続確率設定部とを有することを特徴とするネットワーク設計支援装置。
【請求項２】
前記ネットワーク設計支援装置は、更に、
設計条件の評価の対象となる対象ネットワークの設計条件を入力する設計条件入力部と、
前記設計条件入力部により入力された設計条件に基づいて、対象ネットワークの接続確率を導出する対象ネットワーク接続確率導出部と、
前記対象ネットワーク接続確率導出部により導出された対象ネットワークの接続確率と前記閾値接続確率設定部により設定された閾値接続確率とを比較し、比較結果に基づいて対象ネットワークの設計条件の評価を行う設計条件評価部とを有することを特徴とする請求項１に記載のネットワーク設計支援装置。
【請求項３】
前記設計条件評価部は、
前記対象ネットワーク接続確率導出部により導出された対象ネットワークの接続確率が前記閾値接続確率設定部により設定された閾値接続確率よりも高い場合に、対象ネットワークの設計条件を高接続確率の設計条件であると評価することを特徴とする請求項２に記載のネットワーク設計支援装置。
【請求項４】
前記ネットワークモデル生成部は、
接続確率が増加するほど接続ノード数の値が増加し、特定の接続確率を超えた際に接続ノード数の値が大幅に増加する特性を有するネットワークモデルを生成し、
前記閾値接続確率設定部は、
前記複数の接続確率の大小関係の順序に対応させて、前記接続判定部により判定された複数個の接続ノード数の値の変化状況を解析し、変化状況の解析結果に基づいて、接続ノード数の値が大幅に増加する接続確率を抽出し、抽出した接続確率に基づいて閾値接続確率を設定することを特徴とする請求項１に記載のネットワーク設計支援装置。
【請求項５】
前記接続判定部は、
前記ネットワークモデル生成部により複数の接続確率に対して生成されたネットワークモデルごとに、ネットワークモデル内で基準となる基準ノードを指定し、基準ノードからのホップ数を順次増加させて基準ノードと少なくとも一つ以上のリンクを介して接続されているノードを検出して、接続ノード数の値を判定することを特徴とする請求項１に記載のネットワーク設計支援装置。
【請求項６】
複数のノードと複数のリンク候補から構成されるトポロジーモデルを設定するトポロジーモデル設定ステップと、
前記トポロジーモデルに含まれる複数のノードのそれぞれが接続可能性のある他のノードと所定の接続確率で接続すると仮定した場合のネットワークモデルであって、複数のリンク候補のうちの少なくともいずれか一つが有効になり少なくとも二つのノード間にリンクが設定されているネットワークモデルを、複数の接続確率に対して生成するネットワークモデル生成ステップと、
前記ネットワークモデル生成ステップにより複数の接続確率に対して生成されたネットワークモデルごとに、ネットワークモデルを解析し、ネットワークモデル内でリンクを介して接続されている接続ノード数の値を判定する接続判定ステップと、
前記複数の接続確率の大小関係の順序に対応させて、前記接続判定ステップにより判定された複数個の接続ノード数の値の変化状況を解析し、変化状況の解析結果に基づいて、ネットワーク設計の設計条件を評価する際の閾値となる閾値接続確率を設定する閾値接続確率設定ステップとを有することを特徴とするネットワーク設計支援方法。
【請求項７】
前記ネットワーク設計支援方法は、更に、
設計条件の評価の対象となる対象ネットワークの設計条件を入力する設計条件入力ステップと、
前記設計条件入力ステップにより入力された設計条件に基づいて、対象ネットワークの接続確率を導出する対象ネットワーク接続確率導出ステップと、
前記対象ネットワーク接続確率導出ステップにより導出された対象ネットワークの接続確率と前記閾値接続確率設定ステップにより設定された閾値接続確率とを比較し、比較結果に基づいて対象ネットワークの設計条件の評価を行う設計条件評価ステップとを有することを特徴とする請求項６に記載のネットワーク設計支援方法。
【請求項８】
複数のノードと複数のリンク候補から構成されるトポロジーモデルを設定するトポロジーモデル設定処理と、
前記トポロジーモデルに含まれる複数のノードのそれぞれが接続可能性のある他のノードと所定の接続確率で接続すると仮定した場合のネットワークモデルであって、複数のリンク候補のうちの少なくともいずれか一つが有効になり少なくとも二つのノード間にリンクが設定されているネットワークモデルを、複数の接続確率に対して生成するネットワークモデル生成処理と、
前記ネットワークモデル生成処理により複数の接続確率に対して生成されたネットワークモデルごとに、ネットワークモデルを解析し、ネットワークモデル内でリンクを介して接続されている接続ノード数の値を判定する接続判定処理と、
前記複数の接続確率の大小関係の順序に対応させて、前記接続判定処理により判定された複数個の接続ノード数の値の変化状況を解析し、変化状況の解析結果に基づいて、ネットワーク設計の設計条件を評価する際の閾値となる閾値接続確率を設定する閾値接続確率設定処理とをコンピュータに実行させることを特徴とするプログラム。
【請求項９】
前記プログラムは、更に、
設計条件の評価の対象となる対象ネットワークの設計条件を入力する設計条件入力処理と、
前記設計条件入力処理により入力された設計条件に基づいて、対象ネットワークの接続確率を導出する対象ネットワーク接続確率導出処理と、
前記対象ネットワーク接続確率導出処理により導出された対象ネットワークの接続確率と前記閾値接続確率設定処理により設定された閾値接続確率とを比較し、比較結果に基づいて対象ネットワークの設計条件の評価を行う設計条件評価処理とをコンピュータに実行させることを特徴とする請求項８に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、通信ネットワークにおいて、複数の通信装置間を接続する方式に関するものである。本発明が対象とするネットワークとしては、例えば、ある範囲内に多数の通信装置を配置してその間を無線あるいは有線で接続するセンサーネットワーク、あるいは基地局等の固定設備を持たず、移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワーク、あるいは通常の固定通信装置間を無線あるいは有線で接続するネットワークなどである。
【背景技術】
【０００２】
通信ネットワークの設計において、通信装置をノード、通信装置間をリンクとしたネットワークモデルが一般に広く使用されている。
【０００３】
ネットワークモデルを用いてノードの経路設計を行う技術として、特開２００２−１１８５９７号公報に記載の技術がある。特開２００２−１１８５９７号公報では、リンクの複数の通信特性（レベル値有効帯域に基づくコストや遅延コードなど）を考慮して、ノードの経路設計を行う。
【０００４】
また、ネットワーク内のノードの接続性を評価する方法として、Ｂ．  Ｋｒｉｓｈｎａｍａｃｈａｒｉ，  Ｄ．  Ｅｓｔｒｉｎ，  Ｓ．  Ｗｉｃｋｅｒ「Ｍｏｄｅｌｌｉｎｇ  Ｄａｔａ−Ｃｅｎｔｒｉｃ  Ｒｏｕｔｉｎｇ  ｉｎ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ」  （ＩＥＥＥ  ＩＮＦＯＣＯＭ  ２００２）がある。また、背景となる一般的な方法を説明したものとして、Ｍｅｃｈｔｈｉｌｄ  Ｓｔｏｅｒ著「Ｄｅｓｉｇｎ  ｏｆ  Ｓｕｒｖｉｖａｂｌｅ  Ｎｅｔｗｏｒｋｓ」  （Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｍａｔｈｅｍａｔｉｃｓ  １５３１）がある。しかし、単一のキーパラメータでネットワークを模擬する単純なモデルによるネットワーク設計方法はなかった。一方、リンクの接続確率を使用してネットワークの性質を表現する数学的なモデルを説明したものとして、樋口保成著「パーコレーション」遊星社発行があった。本発明は、このような数学的モデルを応用して、通信ネットワークの接続性を確保する方法を提案するものである。
【０００５】
図１は、ネットワークトポロジーモデルの例を示す図である。図において、１０はネットワークモデル、１は通信装置を示すノード、１ＳはノードＳ、１ＴはノードＴを示す。２は無線あるいは有線の通信路を示すリンク（実線で表示）、リンク候補２Ｃ（点線で表示）は、リンク２が設定可能な箇所を示す。
【０００６】
図２２は従来の手法の動作フローを示す図である。図において、ＫＢ０１はトポロジーモデル設定、ＫＢ０２はランダムモデル試行、ＫＢ０５は高接続条件出力を示す。ＫＢ０１のトポロジーモデル設定では、ノード１とリンク候補２Ｃ、および発信ノード１Ｓを付与する（図１）。ＫＢ０２のランダムモデル試行では、図１のリンク候補２Ｓのうちから適当なリンクをランダムに選んで有効なリンク２としたモデルを設定し、複数回試行する。図４にランダムモデル試行の手順を示す。ランダムモデル試行では、多数のランダムモデルを設定して試行を行うため、計算機処理量が大きくなる。この結果に基づき、ＫＢ０５は高接続条件、つまり、ランダムモデル試行により試行された複数のランダムモデルの中からノード間の接続性の高いランダムモデルがいずれのモデルであるのかを出力する。
【特許文献１】特開２００２−１１８５９７号公報
【非特許文献１】Ｂ．  Ｋｒｉｓｈｎａｍａｃｈａｒｉ，  Ｄ．  Ｅｓｔｒｉｎ，  Ｓ．  Ｗｉｃｋｅｒ著「Ｍｏｄｅｌｌｉｎｇ  Ｄａｔａ−Ｃｅｎｔｒｉｃ  Ｒｏｕｔｉｎｇ  ｉｎ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ」  （ＩＥＥＥ  ＩＮＦＯＣＯＭ  ２００２）
【非特許文献２】Ｍｅｃｈｔｈｉｌｄ  Ｓｔｏｅｒ著「Ｄｅｓｉｇｎ  ｏｆ  Ｓｕｒｖｉｖａｂｌｅ  Ｎｅｔｗｏｒｋｓ」  （Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ社  Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｍａｔｈｅｍａｔｉｃｓ  １５３１）
【非特許文献３】樋口保成著「パーコレーション」遊星社発行、１９９２年６月２５日、ｐ．８−１７
【発明の開示】
【発明が解決しようとする課題】
【０００７】
ところが、以上の手法では、処理量の大きなランダムモデル試行（図２２−ＫＢ０２、図４）を、個々のネットワークの事例毎について繰り返す必要があるため、全体の処理量が大きくなるという問題点があった。特にネットワークモデル１０のノード１の数およびリンク候補２Ｃの数が大きい場合には、処理量が非常に大きくなる。
【０００８】
この発明は上記のような問題点を解決することを主な目的とし、単純な処理により高接続条件の出力を行うことを目的とする。
【課題を解決するための手段】
【０００９】
本発明に係るネットワーク設計支援装置は、
複数のノードと複数のリンク候補から構成されるトポロジーモデルを設定するトポロジーモデル設定部と、
前記トポロジーモデルに含まれる複数のノードのそれぞれが接続可能性のある他のノードと所定の接続確率で接続すると仮定した場合のネットワークモデルであって、複数のリンク候補のうちの少なくともいずれか一つが有効になり少なくとも二つのノード間にリンクが設定されているネットワークモデルを、複数の接続確率に対して生成するネットワークモデル生成部と、
前記ネットワークモデル生成部により複数の接続確率に対して生成されたネットワークモデルごとに、ネットワークモデルを解析し、ネットワークモデル内でリンクを介して接続されている接続ノード数の値を判定する接続判定部と、
前記複数の接続確率の大小関係の順序に対応させて、前記接続判定部により判定された複数個の接続ノード数の値の変化状況を解析し、変化状況の解析結果に基づいて、ネットワーク設計の設計条件を評価する際の閾値となる閾値接続確率を設定する閾値接続確率設定部とを有することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、閾値接続確率を設定することにより、ネットワーク設計条件の評価を閾値接続確率に基づいて行うことが可能なため、設計条件の評価のための計算機処理量を抑制することができる。
【発明を実施するための最良の形態】
【００１１】
実施の形態１．
まず、本実施の形態の概要を従来技術と対比して説明する。図１は本実施の形態の目標を示すためのネットワークトポロジーモデル図である。
【００１２】
図において、１０はネットワークモデル、１は通信装置を示すノード、２は無線あるいは有線の通信路を示すリンクである。ノード１において、特定のノードを指すために添字を用いることもあり、１ＳはノードＳ、１ＴはノードＴを示す。点線でしめされるリンク候補２Ｃは、リンク２が設定可能な箇所を示す。
【００１３】
本実施の形態の目標は、ノード１およびノード間を接続するリンクの候補２Ｃが与えられた場合、あるノード１Ｓとリンク２により接続されているノード１の全体のノード数に対する割合を判断し、これを一定値以上とすることである。
【００１４】
図１において、ノード１は１０個、ノード１間を接続するリンクの候補２Ｃは２３本ある。（ノード１Ｓおよびリンク２を含む）。この場合、ノード１Ｓに接続されているノードは、１Ｔで表される３個であり、全ノード数に対する割合は３／１０＝０．３である。ここで、ノード１Ｓ自身を含めると、接続ノード数の割合は４／１０＝０．４となる。この発明では、一般にノード数が多い場合を対象としているため、当該ノードを含めた場合の割合と含めない場合の割合はほぼ等しくなるので、どちらでもよいとする。
【００１５】
ノード１Ｓから発信される情報を他のノード１に広く周知するために、リンク候補２Ｃのなかから適当なリンクを選択して有効なリンク２とする。通信帯域、通信装置などが限られているなかで、どのようにしてリンク２を選択すれば、より多くのノード１とノード１Ｓを接続できるかを効率的に発見するのが本実施の形態の目標である。
【００１６】
図２は本実施の形態の動作フローを示す図である。本実施の形態では、動作フローは、Ｐ０決定段階（ＫＢ０１〜ＫＢ０３）と条件評価段階（ＫＢ０４、ＫＢ０５）に分かれる。
【００１７】
ＫＢ０１はトポロジーモデル設定、ＫＢ０２はランダムモデル試行、ＫＢ０３は臨界確率Ｐ０決定、ＫＢ０４は臨界確率Ｐ０による接続性判断、ＫＢ０５は高接続条件出力を示す。
【００１８】
Ｐ０決定段階（ＫＢ０１〜ＫＢ０３）では、ＫＢ０１のトポロジーモデル設定では、ノード１とリンク候補２Ｃ、および発信ノード１Ｓを付与して、例えば図１に示すトポロジーモデルを設定する（トポロジーモデル設定ステップ）。
【００１９】
ＫＢ０２のランダムモデル試行では、図１のリンク候補２Ｓのうちから適当なリンクをランダムに選んで有効なリンク２としたネットワークモデルを設定し、複数回試行する（ネットワークモデル生成ステップ）。図４にランダムモデル試行の手順を示す。ランダムモデル試行では、多数のランダムモデルを設定して試行を行うため、計算機処理量が大きくなる。
【００２０】
ＫＢ０３の臨界確率Ｐ０決定では、ランダムモデル試行に基づき、臨界確率Ｐ０を決定する（閾値接続確率設定ステップ）。臨界確率Ｐ０の決定の詳細は、後述する。また、臨界確率Ｐ０は、閾値接続確率の例である。
【００２１】
次に、条件評価段階（ＫＢ０４、ＫＢ０５）では、ＫＢ０４の臨界確率Ｐ０による接続性判断が行われる（設計条件入力ステップ、対象ネットワーク接続確率導出ステップ、設計条件評価ステップ）。ＫＢ０４の臨界確率Ｐ０による接続性判断の手順を図５に示す。ステップＳＴ０１で各事例の確率Ｐと臨界確率Ｐ０を比較し、ＰがＰ０より大きい場合には接続性が高いと判断し（ステップＳＴ０２）、ＰがＰ０より小さい場合には接続性が低いと判断する（ステップＳＴ０３）。この結果に基づき、ＫＢ０５は高接続条件を出力する。
【００２２】
図２２に示す従来の方法は、図２に示す本実施形態の動作フローに比べて処理ステップの数は少ない。しかし、ランダムモデル試行ＫＢ０２は、図４に示すように、非常に処理量が大きい。従来の方法では、個別事例毎にランダムモデル試行を行う必要があり、処理量が大きくなる。これに対し、図２に示す本実施の形態の方法では、トポロジーモデル設定ＫＢ０１の後に、一度ランダムモデル試行ＫＢ０２を行なえば、その結果をキーパラメータの閾値である臨界確率Ｐ０の値で代表させ（ＫＢ０３）、個々の事例では、キーパラメータＰの閾値Ｐ０との大小比較のみで（ＫＢ０４、図５）接続性を判断できる。ネットワークモデルの接続性、すなわち、ノード１Ｓに接続しているノード１の割合の高さという、通常は試行錯誤の結果得られる特性を、確率Ｐというキーパラメータで代表させて表すことにより、試行錯誤はトポロジーモデル設定時のみで、個々のネットワーク事例評価時は、閾値Ｐ０との単純な大小比較のみで接続性判断を行うことができるのが、本実施の形態の方法の特長である。
【００２３】
次に、図２に示した各ステップを実行するネットワーク設計支援装置の構成例を図３に示す。
【００２４】
トポロジーモデル設定部１０１は、図２のトポロジーモデル設定ＫＢ０１を実行する要素であり、例えば図１に示したトポロジーモデルを設定する。
【００２５】
ランダムモデル試行部１０２は図２のランダムモデル試行ＫＢ０２を実行する要素であり、トポロジーモデルに含まれる複数のノードのそれぞれが接続可能性のある他のノードと所定の接続確率で接続すると仮定した場合のネットワークモデルであって、複数のリンク候補のうちの少なくともいずれか一つが有効になり少なくとも二つのノード間にリンクが設定されているネットワークモデルを、複数の接続確率に対して生成する。ランダムモデル試行の具体的内容は後述する。また、ランダムモデル試行部１０２は、ネットワークモデル生成部の例である。
【００２６】
Ｐ０決定部１０３は、図２の臨界確率Ｐ０決定ＫＢ０３を実行する要素である。Ｐ０決定部１０３は、接続判定部１０３１とＰ０抽出部（閾値接続確率設定部）１０３２を有する。接続判定部１０３１は、ランダムモデル試行部１０２により複数の接続確率に対して生成されたネットワークモデルごとに、ネットワークモデルを解析し、ネットワークモデル内でリンクを介して接続されている接続ノード数の値を判定する。接続判定部１０３１が判定するのは、ノード１Ｓとリンクにより接続されているノードの個数であってもよいし、ノード１Ｓとリンクにより接続されているノードの全体のノード総数に対する割合値であってもよい。Ｐ０抽出部１０３２は、複数の接続確率の大小関係の順序に対応させて、接続判定部１０３１により判定された複数個の接続ノード数の値の変化状況を解析し、変化状況の解析結果に基づいて、ネットワーク設計の設計条件を評価する際の閾値となるＰ０を抽出する。接続判定部１０３１とＰ０抽出部１０３２の処理の詳細は後述する。
【００２７】
Ｐ０記憶部１０４は、Ｐ０決定部１０３により決定されたＰ０を記憶する。
【００２８】
入力部１０５は、図２のＰ０による接続性判断ＫＢ０４の対象となる対象ネットワークの設計条件を入力する。入力部１０５は、設計条件入力部の例である。
【００２９】
対象ネットワークＰ導出部１０６は、入力部１０５により入力された対象ネットワークの設計条件に基づいて対象ネットワークの接続確率Ｐを導出する。対象ネットワークＰ導出部１０６は、対象ネットワーク接続確率導出部の例である。
【００３０】
設計条件評価部１０７は、図２のＰ０による接続性判断ＫＢ０４を実行する要素であり、Ｐ０記憶部１０４に記憶されているＰ０と、対象ネットワークＰ導出部１０６により導出された対象ネットワークの接続確率Ｐとを比較し、比較結果に基づいて対象ネットワークの設計条件の評価を行う。
【００３１】
出力部１０８は、図２の高接続条件出力ＫＢ０５を実行する要素であり、設計条件評価部１０７の評価結果を出力する。
【００３２】
次に、本実施の形態の具体的な手法について説明する。図６および図７はトポロジーモデルを示す図で、概要説明の図１に相当する。図６および図７において、図１と同一番号の要素は同一の機能を有する。但し、図６および図７のモデルでは、ノード１が碁盤の目状に規則的に配置されている。格子１１はノード１配置の枠である。ノード１は格子１１の交差点に配置されるものとし、図が煩雑になることを避けるため、図７あるいは図８のように、リンク接続のない場合等はノード１の図示を省略する。また、図１の場合と異なり、各ノード１は上下左右の４個のノード１とのみ接続可能である。図７に、あるノード１Ｓと、これと接続可能性のあるノード候補１ＳＣ、その際の接続リンク候補２ＳＣを示す。図６および図７のトポロジーモデルは、無線接続されるアドホックネットワークあるいはセンサーネットワークを模擬したものである。無線接続においては、あるノード１Ｓから無線の届く範囲は限られているため、リンク候補２Ｃはノード１Ｓ周辺のノードとのみ有効である。ノード１はランダムに配置してもよいが、量子化して規則的に配置されているとしても、一般性を大きく損なうことはないので、図６−７のモデルを使用する。
【００３３】
図６および図７のネットワークトポロジーモデルにおいて、ノード１Ｓに接続されるノードの様子の一例を示したのが図８である。図において、ノード１Ｓ（黒丸）に接続されているノードをノード１Ｔ（白丸）、接続リンクをリンク２Ｓ（実線）で示している。
【００３４】
図６および図７のネットワークトポロジーモデルにおいて、ランダムモデル試行（図２のＫＢ０２、図４）を行なった結果の例を図９、図１０、図１１に示す。図９〜１１ではノード１の記載は省略されている。図９はキーパラメータである接続確率Ｐ＝０．１の場合、図１０はキーパラメータである接続確率Ｐ＝０．５の場合、図１１はキーパラメータである接続確率Ｐ＝０．９の場合を示す。ここで接続確率とは、あるノードが、接続可能性のあるノードとの接続を試行した場合に接続できる確率をいい、例えば、接続確率Ｐ＝０．１の場合は、あるノードが、接続可能性のあるノードとの間に接続の試行を１０回行った際に１回だけ接続ができるという場合である。そして、図９は、図６のトポロジーモデルに含まれる複数のノードのそれぞれが接続可能性のある他のノード（上下左右のノード）と接続確率Ｐ＝０．１で接続すると仮定した場合のネットワークモデルを示し、図１０は、図６のトポロジーモデルに含まれる複数のノードのそれぞれが接続可能性のある他のノード（上下左右のノード）と接続確率Ｐ＝０．５で接続すると仮定した場合のネットワークモデルを示し、図１１は、図６のトポロジーモデルに含まれる複数のノードのそれぞれが接続可能性のある他のノード（上下左右のノード）と接続確率Ｐ＝０．９で接続すると仮定した場合のネットワークモデルを示す。図９〜１１ではリンク候補２Ｃである格子１１の各辺を確率Ｐで有効とした。接続確率Ｐの増加にともない、ノード１Ｓに接続されているノードの割合が増加しているのがわかる。このように、ランダムモデル試行部１０２は、複数の接続確率についてネットワークモデルの生成を試行する。
【００３５】
次に、臨界確率Ｐ０の求め方について説明する。上述の概要説明では図２のランダムモデル試行ＫＢ０２で図４に示すランダムモデル試行を行い、図２の臨界確率Ｐ０決定ＫＢ０３で臨界確率Ｐ０を決定すると述べた。これらの手順を詳述したのが、図１２から１５である。
【００３６】
図１２のステップＳＴ７１のノードＳと他ノードの接続判定手順を詳述したのが図１３、図１３のステップＳＴ８１、ＳＴ８３、ＳＴ８５、ＳＴ８７のノードＳと中継Ｒ回で接続するノードの情報を作成する手順を詳述したのが図１４、図１４のステップＳＴ９１のノードｉとノードｊの接続判定手順を詳述したのが図１５である。
【００３７】
臨界確率Ｐ０を求める際には、まず図１２のステップＳＴ７１で、接続判定部１０３１が、ノードＳと他ノードの接続判定を行う。このノードＳと他ノードの接続判定とは、ランダムモデル試行で生成したネットワークモデルごとに、ネットワークモデル内でリンクを介して接続されている接続ノード数の値（接続ノードの個数又は全体のノード総数に対する接続ノードの割合値）を判定する作業である。あるネットワークモデルについて接続ノード数の値が判定されたら、結果をデータメモリＤＭ７２のノードＳと他ノードの接続状況に書き込む。
【００３８】
次に、ステップＳＴ７３で、接続確率Ｐの数種の値に付き試行済みか否かを判断し、イエスの場合はステップＳＴ７５、ノーの場合はステップＳＴ７４に進む。ステップＳＴ７４では接続確率Ｐの次の候補を与え、ステップＳＴ７１を繰り返す。図９−１１の例では、図９のＰ＝０．１、図１０のＰ＝０．５、図１１のＰ＝０．９の３種のネットワークモデルについて接続ノード数の値を判定することになり、この例では、ステップＳＴ７１１の処理を３回行うことになる。
【００３９】
次に、ステップＳＴ７５に進んで、Ｐ０抽出部１０３２が、データメモリＤＭ７２のノードＳと他ノードの接続状況を参照し、前後で接続状況が大きく変化するＰの値をＰ０とする。図１６の曲線６は、接続確率Ｐと接続状況（接続ノード数の値）との関係を模式的に表したものである。図において、前後で接続状況が大きく変化するＰのあたりにＰ０を設定する。つまり、Ｐ０抽出部１０３２は、複数の接続確率の大小関係の順序に対応させて、接続判定部１０３１により判定された複数個の接続ノード数の値の変化状況を解析し、接続ノード数の値が大幅に増加する接続確率を抽出し、抽出した接続確率に基づいて閾値接続確率であるＰ０を設定する。
【００４０】
次に、図１３のノードＳと他ノードの接続判定手順について説明する。まず、ステップＳＴ８１で、ノードＳと直接接続するノードの情報を作成し、データメモリＤＭ８２に書き込む。
【００４１】
次に、ステップＳＴ８３で、ノードＳと中継１回で接続するノードの情報を作成し、データメモリＤＭ８４に書き込む。ステップＳＴ８５−ＳＴ８９で順次これを繰り返し、全ノードを網羅したら（ステップＳＴ８９）、終了となる。
【００４２】
次に、図１４の、ノードＳと中継Ｒ回で接続するノードの情報を作成する手順について説明する。まず、ステップＳＴ９１で、ノードｉとノードｊの接続判定（リンクで接続されているか否か）を行い、結果をデータメモリＤＭ９２に書き込む。ステップＳＴ９３でネットワーク内の全ノードをノードｊとして判定済か否かを判断し、イエスならばステップＳＴ９５に進み、ノーならばステップＳＴ９４でノードｊの次候補を割り当ててステップＳＴ９１を繰り返す。ステップＳＴ９５では、ノードＳと中継Ｒ−１回で接続する全ノードをノードｉとして判定済かを判断し、イエスならば終了、ノーならばステップＳＴ９６でノードｉの次候補を割り当てて、ステップＳＴ９１を繰り返す。
【００４３】
次に、図１５の、ノードｉとノードｊの接続判定手順について説明する。ステップＳＴ１０１で、データメモリＤＭ１０２を参照して、ノードｉとノードｊの接続状況（リンクで接続されているか否か）の判定を行ない、結果をデータメモリＤＭ１０３に書き込む。接続情報を保持するデータメモリＤＭ１０２は、図４のランダムモデル試行時のリンクデータＤＭ１０である。
【００４４】
このように、接続判定部１０３１は、ランダムモデル試行部１０２により複数の接続確率Ｐ（＝０．１、０．５、０．９）に対して生成されたネットワークモデルごとに、ネットワークモデル内で基準となる基準ノード１Ｓを指定し、基準ノード１Ｓからのホップ数を順次増加させ、リンクで接続されているノードを順次検出し、これにより基準ノード１Ｓと少なくとも一つ以上のリンクを介して接続されているノードを検出して、当該ネットワークモデルにおける接続ノード数の値を判定する。
【００４５】
以上の図１２〜図１６に示す処理により、閾値である臨界確率Ｐ０が設定され、この臨界確率Ｐ０がＰ０記憶部１０４に記憶される。
【００４６】
次に、ネットワーク設計の設計条件の評価を行う処理である条件評価段階（図２のＫＢ０４及びＫＢ０５）について説明する。
【００４７】
まず、Ｐ０による接続性判断ＫＢ０４を行うために、評価対象の対象ネットワークの接続確率Ｐ（以下、対象ネットワーク接続確率Ｐとする）を求める必要がある。まず、対象ネットワーク接続確率Ｐの決め方について説明する。ここでは、ノード間の距離Ｄに基いて確率Ｐが低下するとした場合を述べる。図１７は、ノード１Ｓの周辺を模式的に表した図で、ノードＳから距離Ｄの範囲をノードＳと接続確率Ｐで接続できる範囲としている。距離Ｄが大きくなってノードＳから離れるほど接続確率Ｐは低下し、範囲３ＡではＰ＝０．５、範囲３ＢではＰ＝０．２、範囲３ＣではＰ＝０．１となっている。図１８は、距離Ｄと確率Ｐの関係４を模式的に示したグラフである。ノードＳからの距離Ｄが０の場合は確率Ｐは１であり、必ず接続するが、距離Ｄが増加するにつれて確率Ｐは低下し、Ｄ０でＰはほぼゼロとなり、ほとんど接続しない。
【００４８】
次に、図１８の関係の求め方を述べる。図１９は、距離Ｄが大きくなるにつれて相対的電界強度Ｅ（ｄＢ）が低下する関係５を示したもので、一般に広く使用されている次の関係式に基づいて描かれたものである。（例えば奥村善久、進士昌明監修「移動通信の基礎」電子情報通信学会編）
Ｅ＝−２０×ｌｏｇ（Ｄ）                （式１）
但し、距離Ｄ＝０ｍのときの対数（ｌｏｇ）をとることはできないので、ここで距離Ｄ＝０というのは、距離が非常に小さい場合を指す。図１９において、距離Ｄ＝０ｍ、相対電界強度０ｄＢのとき、接続確率Ｐが１、距離Ｄ＝１００ｍ、相対電界強度−４０ｄＢのとき、接続確率Ｐがゼロになると設定すると、図１８においてＤ０＝１００ｍとおいた関係４を求めることができる。式で表すと以下のようになる。
【００４９】
Ｐ＝（｜Ｅ（Ｄ０）｜＋Ｅ）／｜Ｅ（Ｄ０）｜                        （式２）
＝（４０−２０×ｌｏｇ（Ｄ））／４０
＝１−（ｌｏｇ（Ｄ））／２
以上より、対象ネットワーク接続確率Ｐを求めるために、入力部１０５は、対象ネットワークの設計条件である距離Ｄや相対電界強度などの条件を入力し、入力した設計条件に基づき、対象ネットワークＰ導出部１０６が、上記の式２に基づいて、対象ネットワーク接続確率Ｐを導出する。そして、設計条件評価部１０７が、図５に示すように、導出された対象ネットワーク接続確率ＰとＰ０記憶部１０４に記憶されている閾値Ｐ０とを比較し、対象ネットワーク接続確率Ｐが閾値Ｐ０よりも大きいならば、対象ネットワークの設計条件が高接続確率の設計条件であると評価する。これにより、ネットワーク設計者は、距離などの設計条件が適切であるかどうかを判断することができる。
【００５０】
なお、上記の説明では、ノード設計の基準となるノードＳを固定した場合を述べたが、これを固定せず、一般化しても、同様の方法を適用することができる。
【００５１】
また、上記の説明では、距離Ｄから確率Ｐを求める際に相対電界強度Ｅの式１を用いたが、電界強度の他の関係式、あるいは損失、あるいは別の属性をもとに確率Ｐを設定してもよい。
【００５２】
このように、本実施の形態では、アドホックネットワークあるいはセンサーネットワークにおいて、あるノードと、そのノードと接続される可能性がある他のノードとの接続確率を一定値Ｐとし、この接続確率Ｐをキーパラメータとしてネットワークモデルを作成し、この接続確率Ｐがある値を超えるとネットワーク内のノードの接続状況が密となり、ある値以下だと疎となるという性質を利用して（仮定して）、ネットワークの設計を行う。そして、ノード候補が碁盤の目状に配置され、あるノードが、その上下左右のノードと接続される可能性があるトポロジーにおいて、接続確率Ｐをキーパラメータとして、Ｐがある値を超えた場合はネットワーク全体が密に接続され、ある値以下だと疎となるという性質を利用して（仮定して）、ネットワークの設計を行う。あるノードと他のノードの接続確率Ｐをとし、ノード間の距離Ｄの増加に対応して確率Ｐが低下するように設定する。この際、距離Ｄが増加すると到達する電波の強度が減少することを表す電解強度、電波損失等の既知の関係を用いて、距離Ｄと接続確率Ｐの関係を求める。すなわち、距離Ｄと電界強度等の既存の関係をもとにして、距離Ｄがゼロのとき確率Ｐが１、距離Ｄがある値Ｄ０のとき確率Ｐがゼロとなるような関係を導出する。
【００５３】
本実施の形態によれば、ノード間の接続確率Ｐをキーパラメータとしてネットワークモデルを特徴付けることにより、高接続条件の出力を単純な処理により行うことができる。
【００５４】
つまり、従来では、ネットワーク設計の設計条件の評価を行うたびに複数のランダムモデル試行を行って高接続条件を出力していたために計算機処理量が多くなったが、本実施の形態では、一旦ランダムモデル試行を行って臨界確率Ｐ０を設定しておけば、対象ネットワーク接続確率Ｐと臨界確率Ｐ０とを比較するだけで、設計条件の評価が可能なため、設計条件の評価のための計算機処理量を抑制することができる。
【００５５】
そして、本実施の形態に係るネットワーク設計支援装置は、センサーネットワーク、アドホックネットワークなど、多数の通信装置を接続するネットワークの計画、設計において、通信装置間の接続性を推定する場合に使用することが可能である。
【００５６】
実施の形態２．
実施の形態１では、概要説明のトポロジーモデル図１に相当する図として、図６および図７のモデル、すなわちノード１が格子１１に従って規則的に配置されているモデルを用いた。
【００５７】
図２０に示すように、ノード１がランダムに配置され、他の全ノードと確率Ｐで接続されるモデルにおいても、同様の手法を用いることができる。この場合の接続性を図２１に示す。このモデルは、距離の遠近に関係なく一定の確率Ｐで接続されることから、無線接続ではなく、有線接続のネットワークをモデル化するのに適している。
【００５８】
このように、本実施の形態では、ノード候補はランダムに配置され、あるノードは、他の全てのノードと接続される可能性がある。これらの接続確率Ｐをキーパラメータとして、Ｐがある値を超えた場合はネットワーク全体が密に接続され、ある値以下だと疎となるという性質を利用して（仮定して）、ネットワークの設計を行っている。このように、ノード間の接続確率Ｐをキーパラメータとしてネットワークモデルを特徴付けることにより、高接続条件の出力を単純な処理により行うことができる。
【００５９】
前述した各実施の形態で、ネットワーク設計支援装置１００は、コンピュータで実現できるものである。
【００６０】
図示していないが、ネットワーク設計支援装置１００は、プログラムを実行するＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えている。
【００６１】
例えば、ＣＰＵは、バスを介して、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、通信ボード、表示装置、Ｋ／Ｂ（キーボード）、マウス、ＦＤＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤＤ（コンパクトディスクドライブ）、磁気ディスク装置、光ディスク装置、プリンタ装置、スキャナ装置等と接続可能である。
【００６２】
ＲＡＭは、揮発性メモリの一例である。ＲＯＭ、ＦＤＤ、ＣＤＤ、磁気ディスク装置、光ディスク装置は、不揮発性メモリの一例である。これらは、記憶装置あるいは記憶部の一例である。
【００６３】
前述した各実施の形態のネットワーク設計支援装置１００が扱うデータや情報は、記憶装置あるいは記憶部に保存され、ネットワーク設計支援装置１００の各部により、記録され読み出されるものである。
【００６４】
また、通信ボードは、例えば、ＬＡＮ、インターネット、或いはＩＳＤＮ等のＷＡＮ（ワイドエリアネットワーク）に接続されている。
【００６５】
磁気ディスク装置には、オペレーティングシステム（ＯＳ）、ウィンドウシステム、プログラム群、ファイル群（データベース）が記憶されている。
【００６６】
プログラム群は、ＣＰＵ、ＯＳ、ウィンドウシステムにより実行される。
【００６７】
上記ネットワーク設計支援装置１００の各部は、一部或いはすべてコンピュータで動作可能なプログラムにより構成しても構わない。或いは、ＲＯＭに記憶されたファームウェアで実現されていても構わない。或いは、ソフトウェア或いは、ハードウェア或いは、ソフトウェアとハードウェアとファームウェアとの組み合わせで実施されても構わない。
【００６８】
上記プログラム群には、実施の形態の説明において「〜部」として説明した処理をＣＰＵに実行させるプログラムが記憶される。これらのプログラムは、例えば、Ｃ言語やＨＴＭＬやＳＧＭＬやＸＭＬなどのコンピュータ言語により作成される。
【００６９】
また、上記プログラムは、磁気ディスク装置、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ）、光ディスク、ＣＤ（コンパクトディスク）、ＭＤ（ミニディスク）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ）等のその他の記録媒体に記憶され、ＣＰＵにより読み出され実行される。
【図面の簡単な説明】
【００７０】
【図１】実施の形態１及び２に係るネットワークトポロジーモデル図である。
【図２】実施の形態１及び２に係る動作フローの例を示す図である。
【図３】実施の形態１及び２に係るネットワーク設計支援装置の構成例を示す図である。
【図４】ランダムモデル試行の手順を示す図である。
【図５】実施の形態１及び２に係る臨界確率Ｐ０による接続性判断の手順を示す図である。
【図６】実施の形態１に係るネットワークトポロジーモデルを示す図である。
【図７】実施の形態１に係るネットワークトポロジーモデルを示す図である。
【図８】図６および図７のネットワークトポロジーモデルにおいて、ノード１Ｓに接続されるノードの様子の一例を示した図である。
【図９】図６および図７のネットワークトポロジーモデルにおいて、接続確率Ｐ＝０．１としてランダムモデル試行を行なった結果の例を示す図である。
【図１０】図６および図７のネットワークトポロジーモデルにおいて、接続確率Ｐ＝０．５としてランダムモデル試行を行なった結果の例を示す図である。
【図１１】図６および図７のネットワークトポロジーモデルにおいて、接続確率Ｐ＝０．９としてランダムモデル試行を行なった結果の例を示す図である。
【図１２】実施の形態１及び２に係る臨界確率Ｐ０を導出する手順を示す図である。
【図１３】図１２のノードＳと他ノードの接続判定手順を詳述した図である。
【図１４】図１３のノードＳと中継Ｒ回で接続するノードの情報を作成する手順を詳述した図である。
【図１５】図１４のノードｉとノードｊの接続判定手順を詳述した図である。
【図１６】接続確率Ｐと接続状況の関係を模式的に表した図である。
【図１７】ノード１Ｓの周辺を模式的に表した図であり、ノード１Ｓからの距離Ｄと接続確率Ｐで接続できる範囲を示している図である。
【図１８】距離Ｄと確率Ｐの関係を模式的に示したグラフである。
【図１９】距離Ｄと電界強度Ｅの関係を示すグラフである。
【図２０】実施の形態２のノードのランダム配置を示す図である。
【図２１】実施の形態２の接続性の一例を示す図である。
【図２２】従来の手法の動作フローを示す図である。
【符号の説明】
【００７１】
１００  ネットワーク設計支援装置、１０１  トポロジーモデル設定部、１０２  ランダムモデル試行部、１０３  Ｐ０決定部、１０４  Ｐ０記憶部、１０５  入力部、１０６  対象ネットワークＰ導出部、１０７  設計条件評価部、１０８  出力部、１０３１  接続判定部、１０３２  Ｐ０抽出部。
【図１】
2006186447.tif 000003
【図２】
2006186447.tif 000004
【図３】
2006186447.tif 000005
【図４】
2006186447.tif 000006
【図５】
2006186447.tif 000007
【図６】
2006186447.tif 000008
【図７】
2006186447.tif 000009
【図８】
2006186447.tif 000010
【図９】
2006186447.tif 000011
【図１０】
2006186447.tif 000012
【図１１】
2006186447.tif 000013
【図１２】
2006186447.tif 000014
【図１３】
2006186447.tif 000015
【図１４】
2006186447.tif 000016
【図１５】
2006186447.tif 000017
【図１６】
2006186447.tif 000018
【図１７】
2006186447.tif 000019
【図１８】
2006186447.tif 000020
【図１９】
2006186447.tif 000021
【図２０】
2006186447.tif 000022
【図２１】
2006186447.tif 000023
【図２２】
2006186447.tif 000024