(57)【要約】【課題】高接続条件の出力を単純な処理で実現可能なネットワーク設計方法を得ること。【解決手段】本発明にかかるネットワーク設計方法は、トポロジーモデルを設定するトポロジー設定ステップと、リンク候補のうちから適当なリンクを選択してそれを有効なリンクとしたネットワークモデルを生成し所定の手順で試行するランダムモデル試行ステップと、妨害ノードが含まれたネットワークモデルにおける前記試行結果に基づいて、ネットワークの接続性を判断するための、必要ノードの密度Ｍの臨界値、干渉の荷重係数Ｋｋの臨界値、妨害ノードの密度Ｍｂの臨界値、および妨害の荷重係数Ｋｂの臨界値、を決定する臨界値決定ステップと、前記Ｍ、Ｋｋ、ＭｂおよびＫｂをキーパラメータとし、前記各臨界値を用いてネットワークの接続性判断を行う接続性判断ステップと、を含む。【選択図】        図３
2008219495.tif 000002
【特許請求の範囲】
【請求項１】
通信装置を示す複数のノードおよび通信路を示す複数のリンク候補から構成されるトポロジーモデルを設定するトポロジー設定ステップと、リンク候補のうちから適当なリンクをランダムに選択してそれを有効なリンクとしたネットワークモデルを生成し、所定の手順で複数回にわたって試行するランダムモデル試行ステップと、を実行し、その実行結果に基づき高接続条件を出力するネットワーク設定方法であって、
所望の通信を行う必要ノードによる通信に悪影響を与える妨害ノードが含まれたネットワークモデルにおける、前記試行結果に基づいて、ネットワークの接続性（低接続および高接続）を判断するための、必要ノードの密度Ｍの臨界値、干渉の荷重係数Ｋｋの臨界値、妨害ノードの密度Ｍｂ（Ｍの関数）の臨界値、および妨害の荷重係数Ｋｂの臨界値、を決定する臨界値決定ステップと、
必要ノードの密度Ｍ、干渉の荷重係数Ｋｋ、妨害ノードの密度Ｍｂ、および妨害の荷重係数Ｋｂ、をキーパラメータとし、前記各臨界値を用いてネットワークの接続性判断を行う接続性判断ステップと、
を含み、
前記ランダムモデル試行ステップおよび前記臨界値決定ステップについては、トポロジーモデル設定ステップ実行時にのみ行い、個々のネットワーク事例における接続性判断は、前記各パラメータと前記各臨界値との大小比較にて行うことを特徴とするネットワーク設計方法。
【請求項２】
送信信号の減衰が送受信ノード間の距離の増加に伴って増加する、当該距離と減衰の既知の関係を用いてしきい値を求め、当該しきい値に基づいて前記キーパラメータを求めることを特徴とする請求項１に記載のネットワーク設計方法。
【請求項３】
前記臨界値決定ステップでは、
妨害の荷重係数Ｋｂの増加（密度Ｍｂ固定）に伴って接続状況が高接続状態から低接続状態となる規則性に基づいて、接続状況が最も急激に減少するときのＫｂの値を、前記Ｋｂの臨界値Ｋｂ０とし、
妨害ノードの密度Ｍｂの増加（荷重係数Ｋｂ固定）に伴って接続状態が低接続状態から一旦高接続状態となり再度低接続状態となる規則性に基づいて、接続状況が最も急激に増加するＭｂの値を、前記Ｍｂの臨界値Ｍｂ１とし、最も急激に減少するＭｂの値を、前記Ｍｂの臨界値Ｍｂ２とし、
干渉の荷重係数Ｋｋの増加（密度Ｍ固定）に伴って接続状況が高接続状態から低接続状態となる規則性に基づいて、接続状況が最も急激に減少するＫｋの値を、前記Ｋｋの臨界値Ｋｋ０とし、
必要ノードの密度Ｍの増加（荷重係数Ｋｋ固定）に伴って接続状態が低接続状態から一旦高接続状態となり再度低接続状態となる規則性に基づいて、接続状況が最も急激に増加するＭの値を、前記Ｍの臨界値Ｍ１とし、最も急激に減少するＭの値を、前記Ｍの臨界値Ｍ２とすることを特徴とする請求項１または２に記載のネットワーク設計方法。
【請求項４】
前記接続性判断ステップでは、
干渉の影響を表わすパラメータＭ、Ｋｋおよび妨害ノードの密度Ｍｂを固定し、妨害の荷重係数Ｋｂを変化させ、当該変化させた妨害の荷重係数Ｋｂと前記臨界値Ｋｂ０とを比較し、「Ｋｂ≦Ｋｂ０」の場合には接続性が高いと判断し、「Ｋｂ＞Ｋｂ０」の場合には接続性が低いと判断し、
干渉の影響を表わすパラメータＭ、Ｋｋおよび妨害の荷重係数Ｋｂを固定し、妨害ノードの密度Ｍｂを変化させ、当該変化させた妨害ノードの密度Ｍｂと前記臨界値Ｍｂ１およびＭｂ２とを比較し、「Ｍｂ１≦Ｍｂ≦Ｍｂ２」の場合には接続性が高いと判断し、Ｍｂがそれ以外の場合には接続性が低いと判断し、
妨害の影響を表わすパラメータＭｂ、Ｋｂおよび干渉ノードの密度Ｍを固定し、干渉の荷重係数Ｋｋを変化させ、当該変化させた干渉の荷重係数Ｋｋと前記臨界値Ｋｋ０とを比較し、「Ｋｋ≦Ｋｋ０」の場合には接続性が高いと判断し、「Ｋｋ＞Ｋｋ０」の場合には接続性が低いと判断し、
妨害の影響を表わすパラメータＭｂ、Ｋｂおよび干渉の荷重係数Ｋｋを固定し、干渉ノードの密度Ｍを変化させ、当該変化させた干渉ノードの密度Ｍと臨界値Ｍ１およびＭ２とを比較し、「Ｍ１≦Ｍ≦Ｍ２」の場合には接続性が高いと判断し、Ｍがそれ以外の場合には接続性が低いと判断することを特徴とする請求項３に記載のネットワーク設計方法。
【請求項５】
通信装置を示す複数のノードおよび通信路を示す複数のリンク候補から構成されるトポロジーモデルを設定するトポロジー設定部と、リンク候補のうちから適当なリンクをランダムに選択してそれを有効なリンクとしたネットワークモデルを生成し、所定の手順で複数回にわたって試行するランダムモデル試行部と、を備え、その試行結果に基づき高接続条件を出力するネットワーク設定支援装置であって、
さらに、
所望の通信を行う必要ノードによる通信に悪影響を与える妨害ノードが含まれたネットワークモデルにおける、前記試行結果に基づいて、ネットワークの接続性（低接続および高接続）を判断するための、必要ノードの密度Ｍの臨界値、干渉の荷重係数Ｋｋの臨界値、妨害ノードの密度Ｍｂ（Ｍの関数）の臨界値、および妨害の荷重係数Ｋｂの臨界値、を決定する臨界値決定部と、
必要ノードの密度Ｍ、干渉の荷重係数Ｋｋ、妨害ノードの密度Ｍｂ、および妨害の荷重係数Ｋｂ、をキーパラメータとし、前記各臨界値を用いてネットワークの接続性判断を行う接続性判断部と、
を備え、
前記ランダムモデル試行部および前記臨界値決定部の処理については、トポロジーモデル設定時にのみ行い、個々のネットワーク事例における接続性判断は、前記各パラメータと前記各臨界値との大小比較にて行うことを特徴とするネットワーク設計支援装置。
【請求項６】
請求項１〜４のいずれか一つ記載のネットワーク設計方法をコンピュータに実行させることを特徴とするネットワーク設計支援プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の通信装置を配置し、通信装置間を無線または有線で接続する通信ネットワークの設計方法に関するものであり、特に、通信ネットワーク内に、所望の通信を妨害する通信装置が含まれている場合のネットワーク設計方法、当該ネットワーク設計方法を実現するためのネットワーク設計支援装置およびプログラムに関するものである。
【背景技術】
【０００２】
通信ネットワークの設計において、通信装置をノード、通信装置間をリンクとしたネットワークモデルが一般に広く使用されている。この際、ネットワーク内のノードの接続性を評価する方法として、たとえば、下記非特許文献１がある。また、通信ネットワーク設計の背景となる一般的な方法を説明したものとして、下記非特許文献２がある。また、リンクの接続確率を使用してネットワークの性質を表現する数学的なモデルを説明したものとして、下記非特許文献３がある。
【０００３】
また、多数の通信装置によるセンサーネットワークまたはアドホックネットワークにおいて、妨害または干渉を考慮したネットワーク設計方法として、下記特許文献１および下記特許文献２がある。なお、これら特許文献１，２には、少数のキーパラメータにより妨害の存在するネットワークを模擬する、単純なモデルによるネットワーク設計については特定されていない。一方、多ノードからの干渉を考慮してネットワークの性質を表現する数学的なモデルを説明したものとして、下記非特許文献４がある。なお、ここでは、妨害ノードが考慮されていない。
【０００４】
ここで、従来のネットワーク設計方法の一例について説明する。従来のネットワーク設計は、たとえば、「トポロジーモデル設定」，「ランダムモデル試行」，「高接続条件出力」、の３つのステップで行われる。「トポロジーモデル設定」では、通信装置を示す複数のノード、通信路を示すリンクの候補、および各ノードのうちの発信ノード、を設定する。「ランダムモデル試行」では、リンク候補のうちから適当なリンクをランダムに選択してそれを有効なリンクとしたモデルを設定し、所定の手順で複数回にわたって試行する。「ランダムモデル試行」では、多数のランダムモデルを設定して試行を行う。「高接続条件出力」では、試行結果に基づき高接続条件を出力する。
【０００５】
【特許文献１】特開２０００−３１５９７４号公報
【特許文献２】特開２００１−１５６７８７号公報
【非特許文献１】B.Krishnamachari,  D.Estrin,  S.Wicker  「Modeling  Data‐Centric  Routing  in  Wireless  Sensor  Networks」（IEEE  INFOCOM  2002）
【非特許文献２】Mechthild  Stoer著  「Design  of  Survivable  Networks」  （Springer‐Verlag社  Lecture  Notes  in  Mathematics  1531）
【非特許文献３】樋口保成著  「パーコレーション」  遊星社発行
【非特許文献４】O.Dousse,  F.Baccelli,  P.Thiran,  “Impact  of  interferences  on  connectivity  in  ad  hoc  networks,”  IEEE／ACM  Transactions  on  networking,  vol.13,  no.2,  April  2005,pp.  425−436
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記従来のネットワーク設計方法においては、「トポロジーモデル設定」および処理量の大きな「ランダムモデル試行」を、個々のネットワークの事例毎に繰り返し実行する必要があるため、全体の処理量が増大する、という問題があった。特に、ネットワークモデルにおいて、ノードの数およびリンク候補の数が増大傾向にある場合には、増大に伴って処理量が大きくなる。
【０００７】
本発明は、上記に鑑みてなされたものであって、多数の通信装置によるセンサーネットワークまたはアドホックネットワーク等の通信ネットワークにおいて、高接続条件の出力を単純な処理で実現可能なネットワーク設計方法、ネットワーク設計支援装置およびプログラムを得ることを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決し、目的を達成するために、本発明にかかるネットワーク設計方法は、通信装置を示す複数のノードおよび通信路を示す複数のリンク候補から構成されるトポロジーモデルを設定するトポロジー設定ステップと、リンク候補のうちから適当なリンクをランダムに選択してそれを有効なリンクとしたネットワークモデルを生成し、所定の手順で複数回にわたって試行するランダムモデル試行ステップと、を実行し、その実行結果に基づき高接続条件を出力するネットワーク設定方法であって、所望の通信を行う必要ノードによる通信に悪影響を与える妨害ノードが含まれたネットワークモデルにおける、前記試行結果に基づいて、ネットワークの接続性（低接続および高接続）を判断するための、必要ノードの密度Ｍの臨界値、干渉の荷重係数Ｋｋの臨界値、妨害ノードの密度Ｍｂ（Ｍの関数）の臨界値、および妨害の荷重係数Ｋｂの臨界値、を決定する臨界値決定ステップと、必要ノードの密度Ｍ、干渉の荷重係数Ｋｋ、妨害ノードの密度Ｍｂ、および妨害の荷重係数Ｋｂ、をキーパラメータとし、前記各臨界値を用いてネットワークの接続性判断を行う接続性判断ステップと、を含み、前記ランダムモデル試行ステップおよび前記臨界値決定ステップについては、トポロジーモデル設定ステップ実行時にのみ行い、個々のネットワーク事例における接続性判断は、前記各パラメータと前記各臨界値との大小比較にて行うことを特徴とする。
【発明の効果】
【０００９】
この発明によれば、多数の通信装置によるセンサーネットワークまたはアドホックネットワーク等の通信ネットワークにおいて、高接続条件の出力を単純な処理で実現することができる、という効果を奏する。
【発明を実施するための最良の形態】
【００１０】
以下に、本発明にかかるネットワーク設計方法およびネットワーク設計支援装置の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００１１】
本実施の形態におけるネットワーク設計方法は、たとえば、特定範囲内に多数の通信装置を配置したセンサーネットワーク、基地局等の固定設備を持たず移動無線通信装置間の相互中継によりネットワークを構築するアドホックネットワークなど、通信装置間を無線または有線で接続するすべての通信ネットワークに適用可能である。
【００１２】
図１は、ネットワークトポロジーモデルの一例を示す図である。図１において、ネットワークモデル１０は、通信装置を示すたとえば１０個のノード１（ノード１Ｓおよびノード１Ｔを含む）を含み、各ノード１は、無線または有線の通信路を示すリンク（図示の実線および点線に相当）により接続可能である。また、実線で示される２はリンクであり、点線で示される２Ｃは設定可能なリンクを表すリンク候補である。
【００１３】
図２は、ネットワーク内に妨害ノードが含まれる場合のネットワークトポロジーモデルの一例を示す図である。このネットワークモデル１０は、所望の通信を行うノード１として、ノード１Ｓ，ノード１Ｔ，ノード１Ｕ，ノード１Ｖ，ノード１Ｗを備え、さらに、上記所望の通信に悪影響を与える妨害ノード３として、妨害ノード３Ａ，妨害ノード３Ｂが含まれた構成である。ここで、本実施の形態では、妨害ノード３と区別するため、上記ノード１を必要ノード１と表現する。
【００１４】
たとえば、ノード１Ｓがノード１Ｔを中継点としてノード１Ｕと通信を行う場合（ノード１Ｖおよびノード１Ｗがノード１Ｓ，１Ｔ，１Ｕの通信にかかわっていない場合を想定する）、妨害ノード３Ａおよび妨害ノード３Ｂは、電波を発してノード１Ｓ，１Ｔ，１Ｕの通信に悪影響を与える。一方で、ノード１Ｖおよびノード１Ｗにおいて発する電波がノード１Ｓ，１Ｔ，１Ｕの通信に悪影響を及ぼす可能性があるが、これは干渉であり、上記妨害とは区別する。本実施の形態では、一例として、妨害だけでなく干渉をも考慮したネットワーク設計方法について説明する。
【００１５】
図２において、ネットワークモデル１０を単位面積とすると、必要ノード１の密度Ｍは５であり、妨害ノード３の密度Ｍｂは２である。また、妨害ノード３の密度Ｍｂは、必要ノード１の密度Ｍの増加に伴って増加する関数であり、本実施の形態では、たとえば、比例関係にあるものとする。したがって、本実施の形態では、密度Ｍｂを「Ｍｂ＝Ｍ×０．４」と表すことができる。
【００１６】
本実施の形態のネットワーク設計方法においては、ノード間を接続するリンク候補２Ｃが与えられた場合、ノード１Ｓとリンク２により接続されている他の必要ノード１の、全体のノード数に対する割合、を判断し、これを一定値以上とするように通信ネットワークを構築する。
【００１７】
たとえば、図１においては、必要ノード１が１０個であり（ノード１Ｓ，１Ｔを含む）、ノード間を接続するリンク候補２Ｃが２３本であり（リンク２を含む）、そして、ノード１Ｓには３個のノード１Ｔが接続されている。したがって、ノード１Ｓに接続されている他の必要ノード１の全ノード数に対する割合は、「３／１０＝０．３」となる。なお、ノード１Ｓ自身を含めると、上記割合は「４／１０＝０．４」となる。本実施の形態では、ノード数が多い場合を対象としているため、上記ノード１Ｓを含めた場合の割合と含めない場合の割合はほぼ等しいとみなすことができる。すなわち、本実施の形態では、上記割合の計算に、ノード１Ｓを含めることとしてもよいし、含めないこととしてもよい。
【００１８】
本実施の形態では、ノード１Ｓから発信される情報を他の必要ノード１に広く伝えるために、リンク候補２Ｃのなかから適当なリンクを選択して有効なリンク２とし、上記割合を一定値以上とする。すなわち、本実施の形態では、通信帯域，通信装置などが限られているなかで、より多くの必要ノード１とノード１Ｓを接続できるように、リンク候補２Ｃのなかから効率的にリンク２を選択する。
【００１９】
つづいて、本実施の形態のネットワーク設定方法を実現するために必要なパラメータについて説明する。
【００２０】
本実施の形態では、必要ノード１の密度Ｍ、妨害ノード３の密度Ｍｂ（Ｍの関数）、ノイズにおける妨害の荷重係数Ｋｂ、干渉の荷重係数Ｋｋ、をキーパラメータとして、信号対ノイズ比を計算する。そして、この比が特定値を超えるとネットワーク内のノードの接続状況が密となり、特定値以下の場合に疎となる、という性質を利用して、ネットワーク設計を行う。また、ある受信ノード（必要ノード１）が別の送信ノード（必要ノード１）からの送信信号を受信する場合、送信信号の減衰Ｌは、送受信ノード間の距離Ｄの増加に伴って増加する。本実施の形態では、距離Ｄと減衰Ｌの既知の関係を用いて所定のしきい値を求め、そのしきい値に基づいてキーパラメータを調整する。
【００２１】
たとえば、受信ノード１が別の送信ノード１からの送信信号を受信する場合、受信ノード１の受信信号は、送信ノード１の送信電力が減衰した信号となる。したがって、受信信号は、次式（１）で表わすことができる。
受信信号  ＝  送信ノードの送信電力Ｐ×減衰Ｌ      …（１）
【００２２】
また、２個の必要ノード１間の通信に及ぼす悪影響をノイズと呼ぶ。ノイズは妨害と干渉と背景雑音の重み付け加算とする。妨害の荷重係数をＫｂとし、干渉の荷重係数をＫｋとすると、ノイズは、次式（２）のように表すことができる。
ノイズ  ＝  妨害＋干渉＋背景雑音
＝Ｋｂ×Σ（送信電力Ｐ×減衰Ｌ）＋Ｋｋ×Σ（送信電力Ｐ×減衰Ｌ）
＋背景雑音      …（２）
【００２３】
妨害は、個々の妨害ノード３が送信する信号ＰがＬだけ減衰して受信ノードに到達したものの和（Ｍｂ数分の和）である。干渉も同様に、受信ノード１以外の必要ノード１の送信電力ＰがＬだけ減衰したものの和である（Ｍ数分の和）。なお、妨害と干渉の送信電力Ｐと減衰Ｌは、それぞれ異なる値としてもよいが、ここでは、説明の便宜上、同じ値としている。
【００２４】
したがって、受信ノード１では、受信信号とノイズの比が上記しきい値を超えた場合に、送信ノード１からの送信信号を受信することができる。これを式で表わすと次式（３）のようになる。
（送信ノードの送信電力Ｐ×減衰Ｌ）／ノイズ  ＞  しきい値      …（３）
【００２５】
図３は、本実施の形態のネットワーク設計方法を示すフローチャートである。本実施の形態のネットワーク設計では、トポロジーモデル設定（ステップＳ１），ランダムモデル試行（ステップＳ２），臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）決定（ステップＳ３），臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）による接続性判断（ステップＳ４），高接続条件出力（ステップＳ５）、の各ステップを順に実行する。
【００２６】
ステップＳ１の「トポロジーモデル設定」では、たとえば、図１に示すように、ノード１，リンク候補２Ｃを設定し、さらに、発信ノード１Ｓを設定する。ステップＳ２の「ランダムモデル試行」では、図１のリンク候補２Ｃのうちから適当なリンクをランダムに選択して有効なリンク２としたネットワークモデルを設定し、複数回にわたって試行する。ランダムモデル試行では、多数のネットワークモデルを設定して試行を行うため、計算機処理量が大きくなる。図４は、ステップＳ２の「ランダムモデル試行」手順を示すフローチャートである。
【００２７】
ここで上記図４に示す「ランダムモデル試行」手順を図面にしたがって説明する。まず、ステップＳ１０１では、リンク候補中から適当なリンクを選択し、その結果をデータメモリの「ランダムモデル接続情報」領域に記憶する。つぎに、ステップＳ１０２では、ノードＳと接続している他ノードの割合を求める。つぎに、ステップＳ１０３では、この割合が一定値以上か否かを判定し、たとえば、一定値以上の場合（ステップＳ１０３，Ｙｅｓ）はステップＳ１０４の処理に移行する。一方、一定値に達しない場合（ステップＳ，Ｎｏ）は、ステップＳ１０５に移行し、条件を変化して試行し、その後、ステップＳ１０１に戻る。また、ステップＳ１０４では、複数事例にわたって試行が終わっているか否かを確認し、複数事例試行済の場合（ステップＳ１０４，Ｙｅｓ）は「ランダムモデル試行」に関する処理を終了する。一方、同一条件で他の例を試行する場合（ステップＳ１０４，Ｎｏ）は、ステップＳ１０６に移行し、他の例を試行し、その後、ステップＳ１０１に戻る。
【００２８】
つぎに、ステップＳ３の「臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）決定」では、ランダムモデル試行の結果に基づいて臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）を決定する。
【００２９】
つぎに、ステップＳ４の「臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）による接続性判断」の処理について説明する。
【００３０】
図５は、ステップＳ４の「臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）による接続性判断」の処理を示すフローチャートである。ここでは、４個のパラメータＭｂ，Ｋｂ，Ｍ，Ｋｋおよび６個の臨界値Ｍｂ１，Ｍｂ２，Ｋｂ０，Ｍ１，Ｍ２，Ｋｋ０を用いる。これらのパラメータは全てを同時に変化させるわけではなく、同時に変化させるのは１個のみで、他は固定する。この状態で、それぞれのパラメータと臨界値との関係がどのようになっているかを判断する。具体的には、妨害ノード３の密度Ｍｂが（Ｍｂ１≦Ｍｂ≦Ｍｂ２）となっているか、妨害の荷重係数Ｋｂが（Ｋｂ≦Ｋｂ０）となっているか、必要ノード１の密度Ｍが（Ｍ１≦Ｍ≦Ｍ２）となっているか、干渉の荷重係数Ｋｋが（Ｋｋ≦Ｋｋ０）となっているか、を判断する。
【００３１】
ここで、妨害の荷重係数Ｋｂの判断（Ｋｂ≦Ｋｂ０）の意味を、図６および図７を用いて説明する。図６は、妨害ノード３の密度Ｍｂと妨害の荷重係数Ｋｂの関係を模式的に示す図であり、図７は、妨害の荷重係数ＫｂとノードＳ１の接続状況（接続性）の関係を模式的に示す図である。図６において、下側の部分は、ネットワークモデル１０全体としてノード１間が多く接続された状態（高接続状態）、上側の部分は、ノード１間があまり接続されていない状態（低接続状態）を示している。たとえば、図６の横軸の妨害ノード３の密度Ｍｂを固定して縦軸の妨害の荷重係数Ｋｂのみを増加すると、下側部分では高接続となるが、上側部分では低接続となる。これらの状態は、妨害を考慮する重み付け（荷重）の増加により、ノード間の接続が低下することを表している。これは、図７において、横軸の妨害の荷重係数Ｋｂを増加させたとき、Ｋｂが臨界値Ｋｂ０より小さいときは高接続となるが、Ｋｂ０を超えると低接続となることに対応している。
【００３２】
つぎに、妨害ノード３の密度Ｍｂの判断（Ｍｂ１≦Ｍｂ≦Ｍｂ２）、および妨害の荷重係数Ｋｂの判断（Ｋｂ≦Ｋｂ０）の意味を、図６および図８を用いて説明する。図８は、妨害ノード３の密度ＭｂとノードＳ１の接続状況（接続性）の関係を模式的に示す図である。図６において、縦軸の妨害の荷重係数Ｋｂを固定して横軸の妨害ノード３の密度Ｍｂのみを増加すると、低接続から一旦高接続に移行し、その後、妨害ノード３の密度Ｍｂがさらに増加すると再度低接続に移行する。これは、妨害ノード３の密度Ｍｂが小さいときは、必要ノード１の密度Ｍも小さいので、ネットワークモデル１０内のノード１は接続性が低いことを表している。また、その後に妨害ノード３の密度Ｍｂと必要ノード１の密度Ｍが増加すると、必要ノード間の接続性が確保され、接続性が高くなることを表している。そして、さらに妨害ノード３の密度Ｍｂと必要ノード１の密度Ｍが増加すると、妨害の影響が強くなって接続性が低下することを表している。このような傾向は、妨害ノード３の密度Ｍｂが必要ノード１の密度Ｍの増加に伴って増加する（図２では「Ｍｂ＝Ｍ×０．４」）ために発生する。これは、図８において、横軸の妨害ノード３の密度Ｍｂを増加させた場合に、Ｍｂが臨界値Ｍｂ１より小さいときは低接続となるが、臨界値Ｍｂ１を超えると一旦高接続となり、さらに臨界値Ｍｂ２を超えると低接続となることに対応する。
【００３３】
このように、上記では、妨害に関するパラメータである妨害の荷重係数Ｋｂ，妨害ノード３の密度Ｍｂの判断の意味について記述したが、干渉の荷重係数Ｋｋの判断（Ｋｋ≦Ｋｋ０），必要ノード１の密度Ｍの判断（Ｍ１≦Ｍ≦Ｍ２）についても同様に説明可能である。
【００３４】
つぎに、上記接続性判断を前提として、図５の処理を説明する。まず、ステップＳ１１では、干渉の影響を表わすパラメータ（Ｍ，Ｋｋ）を固定し、妨害の影響を考慮して２系統（ステップＳ１３，ステップＳ１４）の処理に移行する。一方、ステップＳ１２では、妨害の影響を表わすパラメータ（Ｍｂ，Ｋｂ）を固定し、干渉の影響を考慮して２系統（ステップＳ１５，ステップＳ１６）の処理に移行する。
【００３５】
ステップＳ１３では、妨害ノード３の密度Ｍｂを固定し、妨害の荷重係数Ｋｂを変化させる。そして、ステップＳ１７において、各事例における妨害の荷重係数Ｋｂと荷重係数の臨界値（臨界荷重係数）Ｋｂ０を比較し、「Ｋｂ≦Ｋｂ０」の場合には接続性が高いと判断し（ステップＳ２２）、「Ｋｂ＞Ｋｂ０」の場合には接続性が低いと判断する（ステップＳ２１）。
【００３６】
ステップＳ１４では、妨害の荷重係数Ｋｂを固定し、妨害ノード３の密度Ｍｂを変化させる。そして、ステップＳ１８において、各事例における妨害ノード３の密度Ｍｂと密度の臨界値（臨界密度）Ｍｂ１およびＭｂ２とを比較し、「Ｍｂ１≦Ｍｂ≦Ｍｂ２」の場合には接続性が高いと判断し（ステップＳ２２）、Ｍｂがそれ以外の場合には接続性が低いと判断する（ステップＳ２１）。
【００３７】
ステップＳ１５では、干渉ノード１の密度Ｍを固定し、干渉の荷重係数Ｋｋを変化させる。そして、ステップＳ１９において、各事例における干渉の荷重係数Ｋｋと臨界荷重係数Ｋｋ０を比較し、「Ｋｋ≦Ｋｋ０」の場合には接続性が高いと判断し（ステップＳ２２）、「Ｋｋ＞Ｋｋ０」の場合には接続性が低いと判断する（ステップＳ２１）。
【００３８】
ステップＳ１６では、干渉の荷重係数Ｋｋを固定し、干渉ノード１の密度Ｍを変化させる。そして、ステップＳ２０において、各事例における干渉ノード１の密度Ｍと臨界密度Ｍ１およびＭ２とを比較し、「Ｍ１≦Ｍ≦Ｍ２」の場合には接続性が高いと判断し（ステップＳ２２）、Ｍがそれ以外の場合には接続性が低いと判断する（ステップＳ２１）。
【００３９】
したがって、図３に示すステップＳ５の「高接続条件出力」では、上記判断結果に基づいて高接続条件を出力する。
【００４０】
このように、本実施の形態のネットワーク設計方法では、トポロジーモデル設定（ステップＳ１）の後に、一度ランダムモデル試行（ステップＳ２）を行い、その結果に基づいて各パラメータのしきい値である臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）を決定し（ステップＳ３）、個々のネットワークの事例では、パラメータ（Ｍｂ，Ｋｂ），（Ｍ，Ｋｋ）と臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０），（Ｍ１，Ｍ２，Ｋｋ０）との大小比較で接続性を判断する（ステップＳ４）。このように、本実施の形態では、ネットワークモデルの接続性、すなわち、ノード１Ｓに接続しているノード１の割合の高さに相当する通常は「トポロジーモデル」，「ランダムモデル試行」を繰り返し実行した結果として得られる特性を、パラメータ（Ｍｂ，Ｋｂ）および（Ｍ，Ｋｋ）で表現することとした。これにより、「ランダムモデル試行」および「臨界値決定」は「トポロジーモデル設定」時にのみ行い、個々のネットワーク事例評価については、しきい値（Ｍｂ１，Ｍｂ２，Ｋｂ０），（Ｍ１，Ｍ２，Ｋｋ０）との単純な大小比較で接続性判断を行うこととした。
【００４１】
つづいて、図３に示すネットワーク設計方法を実現するネットワーク設計支援装置１００について説明する。図９は、ネットワーク設計支援装置１００の構成例を示す図であり、このネットワーク設計支援装置１００は、トポロジーモデル設定部１０１とランダムモデル試行部１０２と臨界値決定部１０３と臨界値記憶部１０４と設計条件入力部１０５と対象ネットワーク接続係数導出部１０６と設計条件評価部１０７と出力部１０８とを備えている。
【００４２】
トポロジーモデル設定部１０１は、図３の「トポロジーモデル設定（ステップＳ１）」を実行し、たとえば、図１に示したネットワークモデルを設定する。
【００４３】
ランダムモデル試行部１０２は、図３の「ランダムモデル試行（ステップＳ２）」を実行する。たとえば、ネットワークモデルに含まれる複数のノードが、接続可能な他のノードとランダムに接続すると仮定した場合に、リンク候補のうちの少なくともいずれか一つが有効になり、少なくとも二つのノード間にリンクが設定されているネットワークモデルを、複数の接続パラメータに対して生成する。
【００４４】
臨界値決定部１０３は、図３の「臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）決定（ステップＳ３）」を実行する。また、臨界値決定部１０３は、接続判定部１１１と（Ｍｂ１，Ｍｂ２，Ｋｂ０）抽出部１１２と（Ｍ１，Ｍ２，Ｋｋ０）抽出部１１３とを備えている。接続判定部１１１は、ランダムモデル試行部１０２により複数の接続パラメータに対して生成されたネットワークモデル単位に、ネットワークモデルを解析し、ネットワークモデル内でリンクを介して接続されているノードの数を判定する。接続判定部１１１の判定は、ノード１Ｓとリンクにより接続されているノードの個数であってもよいし、ノード１Ｓとリンクにより接続されているノードの、ノード総数に対する割合であってもよい。（Ｍｂ１，Ｍｂ２，Ｋｂ０）抽出部１１２は、複数の接続パラメータの大小関係の順序に対応させて、接続判定部１１１により判定されたノード数の変化状況を解析し、変化状況の解析結果に基づいてネットワーク設計の設計条件を評価する際のしきい値となる臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）を抽出する。（Ｍ１，Ｍ２，Ｋｋ０）抽出部１１３は、複数の接続パラメータの大小関係の順序に対応させて、接続判定部１１１により判定されたノード数の変化状況を解析し、変化状況の解析結果に基づいてネットワーク設計の設計条件を評価する際のしきい値となる（Ｍ１，Ｍ２，Ｋｋ０）を抽出する。なお、接続判定部１１１と（Ｍｂ１，Ｍｂ２，Ｋｂ０）抽出部１１２と（Ｍ１，Ｍ２，Ｋｋ０）抽出部１１３の処理の詳細は後述する。そして、臨界値記憶部１０４は、臨界値決定部１０３により決定されたパラメータを記憶する。
【００４５】
設計条件入力部１０５は、図３の「（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）による接続性判断（ステップＳ４）」の対象となるネットワークの設計条件を入力する。
【００４６】
対象ネットワーク接続係数導出部１０６は、設計条件入力部１０５により入力されたネットワークの設計条件に基づいて、対象ネットワークの接続パラメータＭｂ，Ｋｂ，Ｍ，Ｋｋを導出する。
【００４７】
設計条件評価部１０７は、図３の「（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）による接続性判断（ステップＳ４）」を実行し、臨界値記憶部１０４に記憶されているＭｂ１，Ｍｂ２，Ｋｂ０，Ｍ１，Ｍ２，Ｋｋ０と、対象ネットワーク接続係数導出部１０６により導出された対象ネットワークのパラメータＭｂ，Ｋｂ，Ｍ，Ｋｋと、を比較し、その比較結果に基づいて対象ネットワークの設計条件の評価を行う。
【００４８】
出力部１０８は、図３の「高接続条件出力（ステップＳ５）」を実行し、上記評価結果を出力する。
【００４９】
つづいて、本実施の形態における臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）の求め方について説明する。本実施の形態では、図３に示す「ランダムモデル試行（ステップＳ２）」において図４に示す各ステップの処理を行い、さらに、図３に示す「臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）決定（ステップＳ３）」において、臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）を決定している。これらの手順を図１０〜図１４，図６〜図８において詳述している。図１２は、図１０および図１１のステップＳ３１の「ノードＳと他ノードの接続判定」手順を詳述している。図１３は、図１２のステップＳ４１，Ｓ４２、Ｓ４３、Ｓ４４の「ノードの情報を作成」する手順を詳述している。また、図１４は、図１３のステップＳ５１の「ノードｉとノードｊの接続判定」手順を詳述している。
【００５０】
臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）のうち、臨界荷重Ｋｂ０の求め方を示しているのが図１０である。臨界荷重Ｋｂ０を求める際には、まず、ステップＳ３１において、ノードＳと他ノードの接続判定を行う。この結果をデータメモリの「ノードＳと他ノードの接続状況」領域に書き込む。ステップＳ３２では、臨界荷重Ｋｂ０の数種の値について試行済みか否かを判断し、試行済みの場合（Ｙｅｓ）は、ステップＳ３４において、データメモリの「ノードＳと他ノードの接続状況」領域を参照し、前後で接続状況が大きく減少するＫｂの値をＫｂ０とする（図７参照）。一方、試行済みでない場合（Ｎｏ）は、ステップＳ３３において、妨害の荷重係数Ｋｂの次の候補を設定し、試行済み（Ｙｅｓ）と判定されるまでステップＳ３１〜Ｓ３３を繰り返し実行する。ステップＳ３４では、たとえば、図７に示すように、前後で接続状況が大きく変化する妨害の荷重係数のあたりに臨界値Ｋｂ０を設定する。
【００５１】
臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）のうち、臨界密度Ｍｂ１，Ｍｂ２の求め方を示しているのが図１１である。臨界密度Ｍｂ１，Ｍｂ２を求める際には、まず、図１１のステップＳ３１において、ノードＳと他ノードの接続判定を行う。この判定結果をデータメモリの「ノードＳと他ノードの接続状況」領域に書き込む。ステップＳ３５では、臨界密度Ｍｂ１，Ｍｂ２について試行済みか否かを判断し、試行済みの場合（Ｙｅｓ）は、データメモリの「ノードＳと他ノードの接続状況」領域を参照し、前後で接続状況が大きく増加するＭｂの値をＭｂ１とし、大きく減少するＭｂの値をＭｂ２とする。一方、試行済みでない場合（Ｎｏ）は、ステップＳ３６において、妨害ノード３の密度Ｍｂの次の候補を設定し、試行済み（Ｙｅｓ）と判定されるまでステップＳ３１，Ｓ３５，Ｓ３６を繰り返し実行する。ステップＳ３７では、図８に示すように、前後で接続状況が大きく増加するＭｂの値をＭｂ１と設定し、大きく減少するＭｂの値をＭｂ２と設定する。
【００５２】
なお、臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）のうち、臨界荷重係数Ｋｋ０は、図１０および図７に従って、臨界荷重係数Ｋｂ０と同様に求めることができる。また、臨界密度Ｍ１，Ｍ２は、図１１および図８に従って、臨界密度Ｍｂ１，Ｍｂ２と同様に求めることができる。
【００５３】
つづいて、図１０および図１１の「ノードＳと他ノードの接続判定（ステップＳ３１）」手順について説明する。図１２は、図１０および図１１の「ノードＳと他ノードの接続判定（ステップＳ３１）」手順を示すフローチャートである。
【００５４】
まず、ステップＳ４１では、ノードＳと直接接続するノードの情報を作成し、データメモリの「直接接続情報」領域に書き込む。ステップＳ４２では、ノードＳと中継１回で接続するノードの情報を作成し、データメモリの「１ホップ接続情報」領域に書き込む。ステップＳ４３〜Ｓ４４では、ノードＳと中継２回で接続するノードの情報〜ノードＳと中継Ｎ回で接続するノードの情報、を作成する。そして、全ノードを網羅した段階で（ステップＳ４５）、「ノードＳと他ノードの接続判定」手順を終了する。
【００５５】
つづいて、図１３を用いて、図１２の「ノードの情報を作成」する手順について説明する。まず、ステップＳ５１では、ノードｉとノードｊの接続判定を行い、その判定結果をデータメモリの「Ｒホップ接続情報追記」領域に書き込む。ステップＳ５２では、ネットワーク内の全ノードをノードｊとして判定済か否かを判断し、ＹｅｓならばステップＳ５４に移行する。一方で、ＮｏならばステップＳ５３に移行し、ノードｊの次候補を割り当て、ステップＳ５２にてＹｅｓになるまでステップＳ５１〜Ｓ５３を繰り返し実行する。ステップＳ５４では、ノードＳと中継Ｒ−１回で接続する全ノードをノードｉとして判定済か否かを判断し、Ｙｅｓならば終了する。一方で、ＮｏならばステップＳ５５に移行し、ノードｉの次候補を割り当て、ステップＳ５４にてＹｅｓになるまでステップＳ５１〜Ｓ５５を繰り返し実行する。
【００５６】
つづいて、次に、図１４を用いて、図１３の「ノードｉとノードｊの接続判定」手順について説明する。ステップＳ６１では、データメモリの「トポロジーモデルノード間接続情報」領域を参照して、ノードｉとノードｊの接続状況の判定を行い、その判定結果をデータメモリの「Ｒホップ接続情報追記」領域に書き込む。なお、データメモリの「トポロジーモデルノード間接続情報」領域は、図４の「ランダムモデル接続情報」領域である。
【００５７】
つづいて、パラメータ（Ｍｂ，Ｋｂ），（Ｍ，Ｋｋ）の決め方について説明する。まず、ノード間の距離Ｄと減衰Ｌの関係について記述する。図１５は、ノード１Ｓの周辺を模式的に示す図である。ノード１Ｓから距離Ｄのところで、ノード１Ｓから発した送信信号の減衰がＬとなる範囲を示している。距離Ｄが大きくなってノード１Ｓから離れるほど減衰Ｌは進行し、範囲３０ＡではＬ＝１、範囲３０ＢではＬ＝０．１、範囲３０ＣではＬ＝０．０１となっている。
【００５８】
また、図１６は、距離Ｄと減衰Ｌの関係を模式的に示す図である。減衰Ｌを距離Ｄとの関数で表わすとき、多くの場合は距離Ｄが０のとき減衰Ｌが無限大となり、距離Ｄの増加に伴って減衰Ｌは進行する。なお、距離Ｄの増加に伴って減衰Ｌは進行するが、ゼロにはならない。しかし、アルゴリズム遂行の都合は、距離Ｄの最小値Ｄｎと最大値Ｄｘを定め、距離ＤがＤ＜Ｄｎのとき、ＤはＤｎとし減衰ＬをＬｎとし、距離Ｄが最大値Ｄｘとなった場合には、減衰Ｌをゼロとする。なお、図１７は、距離Ｄの増加に伴って減衰Ｌが進行する場合の具体例を示す図である。減衰Ｌは、Ｄの３乗に反比例することとして描かれたものである。減衰Ｌが距離Ｄのべき乗に反比例するという関係は、一般に広く使用されている（例えば奥村善久、進士昌明監修「移動通信の基礎」電子情報通信学会編）。
【００５９】
以上のように、本実施の形態においては、ノード間の接続係数（パラメータ）であるＭｂ，Ｋｂ，Ｍ，Ｋｋをキーパラメータとしてネットワークモデルを設計することとした。これにより、高接続条件の出力を単純な処理により実現することができる。
【００６０】
なお、本実施の形態では、ノード設計の基準となるノードＳを固定とした場合について説明したが、これを固定せず、一般化した場合であっても同様のネットワーク設計方法を適用することができる。また、本実施の形態では、距離Ｄから減衰Ｌを求める際に、減衰Ｌは距離Ｄの３乗に比例するとしたが、別の関係式に基づいて減衰Ｌを設定することとしてもよい。また、本実施の形態では、必要ノード１による干渉を考慮したネットワーク設計について説明したが、干渉を考慮せずに、妨害のみを考慮してネットワーク設計を行うこととしてもよい。
【産業上の利用可能性】
【００６１】
以上のように、本発明にかかるネットワーク設計方法は、複数の通信装置を配置し、通信装置間を無線または有線で接続する通信ネットワークの設計方法として有用であり、特に、通信ネットワーク内に所望の通信を妨害する通信装置が含まれている場合のネットワーク設計に適している。
【図面の簡単な説明】
【００６２】
【図１】ネットワークトポロジーモデルの一例を示す図である。
【図２】ネットワーク内に妨害ノードが含まれる場合のネットワークトポロジーモデルの一例を示す図である。
【図３】本発明にかかるネットワーク設計方法を示すフローチャートである。
【図４】ステップＳ２の「ランダムモデル試行」手順を示すフローチャートである。
【図５】ステップＳ４の「臨界値（Ｍｂ１，Ｍｂ２，Ｋｂ０）および（Ｍ１，Ｍ２，Ｋｋ０）による接続性判断」の処理を示すフローチャートである。
【図６】妨害ノードの密度Ｍｂと妨害の荷重係数Ｋｂの関係を模式的に示す図である。
【図７】妨害の荷重係数ＫｂとノードＳの接続状況（接続性）の関係を模式的に示す図である。
【図８】妨害ノードの密度ＭｂとノードＳの接続状況（接続性）の関係を模式的に示す図である。
【図９】ネットワーク設計支援装置の構成例を示す図である。
【図１０】臨界荷重Ｋｂ０の求め方を示す図である。
【図１１】臨界密度Ｍｂ１，Ｍｂ２の求め方を示す図である。
【図１２】図１０および図１１のステップＳ３１の「ノードＳと他ノードの接続判定」手順を示す図である。
【図１３】図１２のステップＳ４１，Ｓ４２、Ｓ４３、Ｓ４４の「ノードの情報を作成」する手順を示す図である。
【図１４】図１３のステップＳ５１の「ノードｉとノードｊの接続判定」手順を示す図である。
【図１５】ノードＳの周辺を模式的に示す図である。
【図１６】距離Ｄと減衰Ｌの関係を模式的に示す図である。
【図１７】距離Ｄの増加に伴って減衰Ｌが進行する場合の具体例を示す図である。
【符号の説明】
【００６３】
１  ノード（必要ノード）
１Ｓ，１Ｔ，１Ｕ，１Ｖ，１Ｗ  ノード
２  リンク
２Ｃ  リンク候補
３，３Ａ，３Ｂ  妨害ノード
１００  ネットワーク設計支援装置
１０１  トポロジーモデル設定部
１０２  ランダムモデル試行部
１０３  臨界値決定部
１０４  臨界値記憶部
１０５  設計条件入力部
１０６  対象ネットワーク接続係数導出部
１０７  設計条件評価部
１０８  出力部
１１１  接続判定部
１１２  （Ｍｂ１，Ｍｂ２，Ｋｂ０）抽出部
１１３  （Ｍ１，Ｍ２，Ｋｋ０）抽出部
【図１】
2008219495.tif 000003
【図２】
2008219495.tif 000004
【図３】
2008219495.tif 000005
【図４】
2008219495.tif 000006
【図５】
2008219495.tif 000007
【図６】
2008219495.tif 000008
【図７】
2008219495.tif 000009
【図８】
2008219495.tif 000010
【図９】
2008219495.tif 000011
【図１０】
2008219495.tif 000012
【図１１】
2008219495.tif 000013
【図１２】
2008219495.tif 000014
【図１３】
2008219495.tif 000015
【図１４】
2008219495.tif 000016
【図１５】
2008219495.tif 000017
【図１６】
2008219495.tif 000018
【図１７】
2008219495.tif 000019