(57)【特許請求の範囲】
【請求項１】
複数のノードと複数のリンクとを有するネットワークに関して、前記複数のノード間の通信経路の設定を行う通信経路設定装置において、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第一の通信特性のレベルを示す第一通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第一通信特性リンク情報を作成する第一通信特性リンク情報作成部と、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第二の通信特性のレベルを示す第二通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第二通信特性リンク情報を作成する第二通信特性リンク情報作成部と、
前記第一通信特性リンク情報作成部により作成された前記第一通信特性リンク情報に含まれる第一通信特性レベル値と前記第二通信特性リンク情報作成部により作成された前記第二通信特性リンク情報に含まれる第二通信特性レベル値とを前記複数のリンクの各々のリンクについて関連づけ、前記第一通信特性レベル値に関連づけられた前記第二通信特性レベル値を用いて前記第一通信特性リンク情報を前記第二通信特性レベル値ごとに分類し、前記第二通信特性レベル値ごとに分類された複数の分類第一通信特性リンク情報を作成する分類第一通信特性リンク情報作成部と、
前記分類第一通信特性リンク情報作成部により作成された前記複数の分類第一通信特性リンク情報のうち少なくとも一つ以上の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定部と、
前記複数のリンクの各々に設定された第一通信特性レベル値と前記第二通信特性レベル値とを前記複数のノードに通知する通知パケットであって、前記第一通信特性レベル値を少なくとも３２ビット以上の二進数で表し、前記第二通信特性レベル値の各レベル値ごとに設けられた所定のビットをセットすることにより前記第二通信特性レベル値を表す通知パケットを作成する通知パケット作成部とを有することを特徴とする通信経路設定装置。
【請求項２】
前記通信経路設定装置は、更に、
前記分類第一通信特性リンク情報作成部により作成された前記複数の分類第一通信特性リンク情報から、特定の分類第一通信特性リンク情報を選択する分類第一通信特性リンク情報選択部を有し、
前記通信経路設定部は、前記分類第一通信特性リンク情報選択部により選択された前記特定の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定部とを有することを特徴とする請求項１に記載の通信経路設定装置。
【請求項３】
前記通信経路設定装置は、更に、
前記第二通信特性レベル値についての要求値である要求第二通信特性レベル値を取得する要求取得部を有し、
前記分類第一通信特性リンク情報選択部は、前記複数の分類第一通信特性リンク情報から、前記要求取得部により取得された前記要求第二通信特性レベル値に合致する第二通信特性レベル値に基づいて分類された分類第一通信特性リンク情報を選択することを特徴とする請求項２に記載の通信経路設定装置。
【請求項４】
前記通信経路設定装置は、更に、
前記第一通信特性レベル値についての要求値である要求第一通信特性レベル値を取得する要求取得部と、
前記特定の分類第一通信特性リンク情報に含まれる前記第一通信特性レベル値のうち前記要求取得部により取得された前記要求第一通信特性レベル値に合致しない第一通信特性レベル値を無効とする第一通信特性レベル値無効部とを有し、
前記経路設定部は、前記第一通信特性レベル値無効部により無効にされた第一通信特性レベル値を含む前記特定の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定することを特徴とする請求項２に記載の通信経路設定装置。
【請求項５】
前記通信経路設定部は、前記分類第一通信特性リンク情報作成部により作成された前記複数の分類第一通信特性リンク情報の各々を用いて、前記複数の分類第一通信特性リンク情報ごとに複数の通信経路を設定し、
前記通信経路設定装置は、更に、
前記第二通信特性レベル値についての要求値である要求第二通信特性レベル値を取得する要求取得部と、
前記通信経路設定部により設定された前記複数の通信経路から、前記要求取得部により取得された前記要求第二通信特性レベル値に合致する第二通信特性レベル値に基づいて分類された分類第一通信特性リンク情報を用いて設定された通信経路を選択する通信経路選択部とを有することを特徴とする請求項１に記載の通信経路設定装置。
【請求項６】
前記通信経路設定装置は、更に、前記通知パケット作成部により作成された前記通知パケットを前記複数のノードに送信する通知パケット送信部を有し、
前記通知パケット作成部は、前記通知パケット送信部による前記通知パケットの送信の送信間隔を３０分以下の任意の時間に設定することを特徴とする請求項１に記載の通信経路設定装置。
【請求項７】
複数のノードと複数のリンクとを有するネットワークに関して、前記複数のノード間の通信経路の設定を行う通信経路設定方法において、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第一の通信特性のレベルを示す第一通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第一通信特性リンク情報を作成する第一通信特性リンク情報作成ステップと、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第二の通信特性のレベルを示す第二通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第二通信特性リンク情報を作成する第二通信特性リンク情報作成ステップと、
前記第一通信特性リンク情報作成ステップにより作成された前記第一通信特性リンク情報に含まれる第一通信特性レベル値と前記第二通信特性リンク情報作成ステップにより作成された前記第二通信特性リンク情報に含まれる第二通信特性レベル値とを前記複数のリンクの各々のリンクについて関連づけ、前記第一通信特性レベル値に関連づけられた前記第二通信特性レベル値を用いて前記第一通信特性リンク情報を前記第二通信特性レベル値ごとに分類し、前記第二通信特性レベル値ごとに分類された複数の分類第一通信特性リンク情報を作成する分類第一通信特性リンク情報作成ステップと、
前記分類第一通信特性リンク情報作成ステップにより作成された前記複数の分類第一通信特性リンク情報のうち少なくとも一つ以上の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定ステップと、
前記複数のリンクの各々に設定された第一通信特性レベル値と前記第二通信特性レベル値とを前記複数のノードに通知する通知パケットであって、前記第一通信特性レベル値を少なくとも３２ビット以上の二進数で表し、前記第二通信特性レベル値の各レベル値ごとに設けられた所定のビットをセットすることにより前記第二通信特性レベル値を表す通知パケットを作成する通知パケット作成ステップとを有することを特徴とする通信経路設定方法。
【請求項８】
前記通信経路設定方法は、更に、
前記分類第一通信特性リンク情報作成ステップにより作成された前記複数の分類第一通信特性リンク情報から、特定の分類第一通信特性リンク情報を選択する分類第一通信特性リンク情報選択ステップを有し、
前記通信経路設定ステップは、前記分類第一通信特性リンク情報選択ステップにより選択された前記特定の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定ステップとを有することを特徴とする請求項７に記載の通信経路設定方法。
【請求項９】
前記通信経路設定方法は、更に、
前記第二通信特性レベル値についての要求値である要求第二通信特性レベル値を取得する要求取得ステップを有し、
前記分類第一通信特性リンク情報選択ステップは、前記複数の分類第一通信特性リンク情報から、前記要求取得ステップにより取得された前記要求第二通信特性レベル値に合致する第二通信特性レベル値に基づいて分類された分類第一通信特性リンク情報を選択することを特徴とする請求項８に記載の通信経路設定方法。
【請求項１０】
前記通信経路設定方法は、更に、
前記第一通信特性レベル値についての要求値である要求第一通信特性レベル値を取得する要求取得ステップと、
前記特定の分類第一通信特性リンク情報に含まれる前記第一通信特性レベル値のうち前記要求取得ステップにより取得された前記要求第一通信特性レベル値に合致しない第一通信特性レベル値を無効とする第一通信特性レベル値無効ステップとを有し、
前記経路設定ステップは、前記第一通信特性レベル値無効ステップにより無効にされた第一通信特性レベル値を含む前記特定の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定することを特徴とする請求項８に記載の通信経路設定方法。
【請求項１１】
前記通信経路設定ステップは、前記分類第一通信特性リンク情報作成ステップにより作成された前記複数の分類第一通信特性リンク情報の各々を用いて、前記複数の分類第一通信特性リンク情報ごとに複数の通信経路を設定し、
前記通信経路設定方法は、更に、
前記第二通信特性レベル値についての要求値である要求第二通信特性レベル値を取得する要求取得ステップと、
前記通信経路設定ステップにより設定された前記複数の通信経路から、前記要求取得ステップにより取得された前記要求第二通信特性レベル値に合致する第二通信特性レベル値に基づいて分類された分類第一通信特性リンク情報を用いて設定された通信経路を選択する通信経路選択ステップとを有することを特徴とする請求項７に記載の通信経路設定方法。
【請求項１２】
前記通信経路設定方法は、更に、前記通知パケット作成ステップにより作成された前記通知パケットを前記複数のノードに送信する通知パケット送信ステップを有し、
前記通知パケット作成ステップは、前記通知パケット送信ステップによる前記通知パケットの送信の送信間隔を３０分以下の任意の時間に設定することを特徴とする請求項７に記載の通信経路設定方法。
【請求項１３】
複数のノードと複数のリンクとを有するネットワークに関して、前記複数のノード間の通信経路の設定を行う通信経路設定方法において、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第一の通信特性のレベルを示す第一通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第一通信特性リンク情報を作成する第一通信特性リンク情報作成ステップと、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第二の通信特性のレベルを示す第二通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第二通信特性リンク情報を作成する第二通信特性リンク情報作成ステップと、
前記第一通信特性リンク情報作成ステップにより作成された前記第一通信特性リンク情報に含まれる第一通信特性レベル値と前記第二通信特性リンク情報作成ステップにより作成された前記第二通信特性リンク情報に含まれる第二通信特性レベル値とを前記複数のリンクの各々のリンクについて関連づけ、前記第一通信特性レベル値に関連づけられた前記第二通信特性レベル値を用いて前記第一通信特性リンク情報を前記第二通信特性レベル値ごとに分類し、前記第二通信特性レベル値ごとに分類された複数の分類第一通信特性リンク情報を作成する分類第一通信特性リンク情報作成ステップと、
前記分類第一通信特性リンク情報作成ステップにより作成された前記複数の分類第一通信特性リンク情報のうち少なくとも一つ以上の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定ステップと、
前記複数のリンクの各々に設定された第一通信特性レベル値と前記第二通信特性レベル値とを前記複数のノードに通知する通知パケットであって、前記第一通信特性レベル値を少なくとも３２ビット以上の二進数で表し、前記第二通信特性レベル値の各レベル値ごとに設けられた所定のビットをセットすることにより前記第二通信特性レベル値を表す通知パケットを作成する通知パケット作成ステップとを有する通信経路設定方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、インターネット等のデータ通信のデータの経路を設定するルーチング装置、ルーチング方法に関する。
【０００２】
【従来の技術】
従来例１．
インターネット標準の仕様化を行う主要団体であるＩＥＴＦ（Ｉｎｔｅｒｎｅｔ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔａｓｋ  Ｆｏｒｃｅ）が発行している、インターネット標準ドキュメントであるＲＦＣ（Ｒｅｑｕｅｓｔ  ｆｏｒ  Ｃｏｍｍｅｎｔｓ）シリーズの２６７６番であるＱｏＳ  Ｒｏｕｔｉｎｇ  Ｍｅｃｈａｎｉｓｍｓ  ａｎｄ  ＯＳＰＦ  Ｅｘｔｅｎｓｉｏｎｓ、通称ＱＯＳＰＦと呼ばれる、従来のルーチング方式について、まず説明する。ここでＱｏＳはＱｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅすなわち通信品質、ＯＳＰＦはＯｐｅｎ  Ｓｈｏｒｔｅｓｔ  Ｐａｔｈ  Ｆｉｒｓｔを指す。ＲＦＣ２６７６は、既にインターネットで広く使用されているルーチングプロトコルであるＲＦＣ２３８３番のＯＳＰＦＶｅｒｓｉｏｎ  ２において、経路の通信品質を考慮できるようにしたＯＳＰＦの拡張方式である。
【０００３】
図３１は、ルーチングを行うネットワークの例である。
図において、１はルーチングの対象となる通信ネットワーク、１１は通信信号の発着中継を行うルーターに代表されるノードＮｉ（ｉ＝１，２，・・・，９）、１２はノードＮｉとＮｊ間の物理接続回線であるリンク、各ノード１１の円内に記載されている番号は各々のノードの番号で、ノードＮｉの添字ｉがこれに対応する。ここでノードＮｉとノードＮｊ間のリンクには方向性があるものとし、ノードＮｉからＮｊへ向かうリンクをリンクＬｉｊと記す。一般にはリンクＬｉｊとリンクＬｊｉは異なるが、図３１の例では、便宜上全てのリンク１２は両方向性とする。リンク１２のそれぞれの有効帯域が、リンク上に記してある。リンクＬｉｊの有効帯域Ｃｉｊとは、リンクＬｉｊの帯域のうち、使用可能な帯域を示す。
【０００４】
各々のノード１１には最適経路設計を行う機能が設けられている。全てのノード１１では、通信ネットワーク１全体のトポロジー情報を、それぞれのノード１１のメモリーに保有している。このトポロジー情報をあらわしたものが、図４に示すトポロジー帯域表ＴＰＢＷである。図において、ｉ行ｊ列の要素（ｉ，ｊ）が、リンクＬｉｊの有効帯域Ｃｉｊを示す。
このルーチング方式では、図４に示すトポロジー情報をもとに、各ノード１１につき、そのノードを発信源として通信ネットワーク１内の全ての他のノード１１を宛先とした最適経路を設計する。この従来方式における最適経路とは、下記の条件を満たす経路である。
（１）経由するノードの数が最小
（２）経路の有効帯域が要求帯域以上
発信源から宛先ノードまでに経由するノード数をホップ数とも呼び、例えば３個のノードを経由した経路を３ホップ経路と呼ぶことがある。また、経路の有効帯域とは、経路中のリンクの有効帯域の最小値となる。
【０００５】
次に、この方式における最適経路設計の手順を説明する。ここでは、ノードＮ１において、ノードＮ１を発信源としてノードＮ２からＮ９を宛先とする経路設計を行う場合の例について示す。他のノードにおける経路設計も、同様に行うことができる。この最適経路設計は、経路設計要求が発生する前に、あらかじめ行っておく。
図３２、図３３、図３４は、最適経路設計に使用するルーチング表である。ルーチング表は、図３２のルーチング帯域表ＲＢＷ、図３３のルーチング進行ノード表ＲＮＢ、図３４の変化ノードルーチング表ＲＣＨから構成される。これらのルーチング表において、第ｉ行は通信ネットワーク１のノードＮｉに対応し、行数は通信ネットワーク１の総ノード数ｎｔ＝９となっている。また、第ｊ列は経路設計の更新周期ｔに対応している。この方式では、原理的に、更新周期ｔはその更新周期で得られる経路の最大ホップ数と等しくなっており、ルーチング表の列数は、経路設計で許容する経路の最大ホップ数と等しくなっている。
これらのルーチング表の要素（ｉ，ｊ）は、ノードＮ１からノードＮｉまでの、更新周期ｊ即ちホップ数ｊ以下での、最適経路に関する値を示す。第１行が＊となっているのは、ノードＮ１は発信源であり、第１行の値は意味を持たないためである。
図３２のルーチング帯域表ＲＢＷの要素（ｉ，ｊ）はノードＮｉの更新周期ｊでの最適経路の有効帯域、図３３のルーチング進行ノード表ＲＮＢの要素（ｉ，ｊ）は上記最適経路の進行ノードを示す。図３４の変化ノードルーチング表ＲＣＨの要素（ｉ，ｊ）は、更新周期ｊにノードＮｉの最適経路が変化した場合に１となり、最適経路算出の際に用いる。
【０００６】
次に、図３５につき、この方式における最適経路設計の手順を説明する。図３５は、最適経路設計の手順を示すフロー図である。
図において、ステップＳＰ１からステップＳＰ５は更新周期ｔ＝１の場合の初期設定、ステップＳＰ６からステップＳＰ１１は更新周期ｔが規定された最大ホップ数Ｈになるまで繰り返される手順である。初期設定では、まずステップＳＰ１で更新周期ｔ＝１とおく。次にステップＳＰ２で、ルーチング帯域表（図３２）とルーチング進行ノード表（図３３）の各要素をゼロに初期化する。次にステップＳＰ３で、ルーチング帯域表第１列の発信源直結ノードの行に、直結リンクの帯域を記入する。図３２の例では、第１列の第２行に８を、第４行に２０００を記入する。次にステップＳＰ４で、ルーチング進行ノード表第１列の発信源直結ノードの行に、発信源ノードを記入する。図３３の例では、第１列の第２行と第４行に１を記入する。次にステップＳＰ５で、変化ノードルーチング表第１列の、発信源直結ノードの行を１にする。図３４の例では、第１列の第２行と第４行を１にする。
【０００７】
次にステップＳＰ６で、更新周期ｔを１だけ増加して、次の更新周期の処理を開始する。次にステップＳＰ７で、ルーチング帯域表第ｔ−１列を第ｔ列にコピーする。図３２の例では、第２列に第１列の（＊，８，０，２０００，０，０，０，０，０）をコピーする。次にステップＳＰ８で、変化ノードルーチング表第ｔ−１列が１の行のノード（ｉ＝ｉ１、ｉ２、・・・）に注目する。図３４の例では、第１列が１のノードＮ２とＮ４に注目する。次にステップＳＰ９で、上記ノードｉに関して、ルーチング帯域表の（ｉ，ｔ−１）要素とトポロジー帯域表の（ｉ，ｊ）要素の小さい方の値ｘが、ルーチング帯域表の（ｊ，ｔ）要素ｙより大きい場合には、ｙをｘに書き換える。但しｊはノードＮｉとリンクＬｉｊで接続されている全ノードＮｊのノード番号である。
また、ルーチング進行ノード表の（ｊ，ｔ）要素を、ｘの行番号ｉに更新する。
【０００８】
図３２と図４の例では、まずｉ＝２の場合、ｊは１，３，４，５，６となるが、１は発信源であるので、除く。図３２の（２，１）＝８と、図４の（２，３）＝１８００または（２，４）＝１０００または（２，５）＝１７００または（２，６）＝４００とをそれぞれ比較する。その結果ｊ＝３の場合の最小値ｘは８であり、ｊ＝４の場合の最小値ｘは８であり、ｊ＝５の場合の最小値ｘは８であり、ｊ＝６の場合の最小値ｘは８であることがわかる。これらをそれぞれ図３２の（ｊ，２）要素であるｙと比較する。ステップＳＰ７において説明したように、（ｊ，２）には（＊，８，０，２０００，０，０，０，０，０）が記入されているので、ｊ＝３の場合はｙ＝（３，２）＝０であり、ｊ＝４の場合はｙ＝（４，２）＝２０００であり、ｊ＝５の場合はｙ＝（５，２）＝０であり、ｊ＝６の場合はｙ＝（６，２）＝０である。図３２に記されている値は更新周期ｔが終了した時点の値であり、説明の現時点での値は上記ステップＳＰ７でコピーした値であって、両者は異なるので、注意を要する。その結果、ｊ＝３の場合の最大値はｘ＝８であり、ｊ＝４の場合の最大値はｙ＝２０００であり、ｊ＝５の場合の最大値はｘ＝８であり、ｊ＝６の場合の最大値はｘ＝８であることがわかる。ｊ＝３と５と６の場合は、図３２の第２列の値を最大値であるｘの値に書き換える。次にステップＳＰ１０で、ノードｊを書き換えた場合は、変化ノードルーチング表（ｊ，ｔ）を１にする。ここでは、ｊ＝３と５と６の場合について、図３４の（３，２）と（５，２）と（６，２）を１にする。
次にステップＳＰ１１で、変化ノードルーチング表で（ｉ，ｔ−１）＝１の全てのｉにつき更新完了したかの判断を行う。ここでは、ｉ＝４の場合の更新を行う必要があるので、ステップＳＰ８に戻る。
【０００９】
次に、図４に示されたｉ＝４の場合に注目すると、１は１，２，５，７となるが、ｊは発信源であるので、除く。ｊ＝２，５，７について、ｉ＝２の場合と同様に更新を行う。更新後、ステップＳＰ１１で、ｉ＝２とｉ＝４の全てのｉにつき更新完了したことを判断し、次ステップに進む。次にステップＳＰ１２で、更新周期ｔが規定の最大ホップ数に達したか否かの判断を行う。最大ホップ数を特に規定しない場合は、原理上、全ノード数ｎｔとなる。
この例では、更新周期ｔ＝２は全ノード数ｎｔ＝９に達していないので、ステップＳＰ６に戻って、ｎｔ＝９まで更新を繰り返す。このようにして、図３２、図３３、図３４のルーチング表を完成させる。この場合は、更新周期ｔ＝６以降は値が変化しないので、記載を省略してある。
【００１０】
以上のようにして図３２、図３３、図３４のルーチング表を完成させた。次に、実際にノードＮｓからノードＮｄへの要求帯域Ｒの経路を抽出する手順を述べる。図３６はこの手順を示すフロー図である。
まずステップＳＰ２１で、ルーチング帯域表（図３２）の第ｄ行を、第１列、第２列…の順に右方向へ参照し、要素（ｄ，ｊ１）がＲ以上の値となる要素を探す。例えば、ノードＮｓ＝Ｎ１からＮｄ＝Ｎ６へ要求帯域Ｒ＝１００の経路を抽出する場合は、まず図３２の表ＲＢＷの第６行を、第１列から順に右方向へ参照し、要素が１００以上の値となる（６，３）＝４００に到達する。
次にステップＳＰ２２で、ルーチング進行ノード表の（ｄ，ｊ１）要素ｄ２が、求める経路の一個手前のノード番号になる。上記の例では、図３３の表ＲＮＢの（６，３）要素２が、求める経路の一個手前のノード番号になる。
次にステップＳＰ２３で、ルーチング進行ノード表の、１列左の（ｄ２，ｊ１−１）要素ｄ３が、求める経路の更に一個手前のノード番号になる。上記の例では、図３３の表ＲＮＢの（２，２）要素４が、求める経路の更に一個手前のノード番号になる。
次にステップＳＰ２４で、ルーチング進行ノード表の、１列左の、前ステップで求めた要素の列の要素が、求める経路の更に一個手前のノード番号になる。上記の例では、図３３の表ＲＮＢの（１，４）要素１が、求める経路の更に一個手前のノード番号になる。
次にステップＳＰ２５で、ルーチング進行ノード表の第１列、即ち求めたノード番号が発信源のｓか否かの判断を行い、発信源に達するまでステップＳＰ２４を繰り返す。上記の例では、既に発信源１に達しているので、ここで終了となる。
【００１１】
従来例２．
ＩＥＴＦのＲＦＣ２３８３番であるＯＳＰＦ  Ｖｅｒｓｉｏｎ  ２ルーチングプロトコル（以下適宜、ＯＳＰＦと略記する）において、通信ネットワークのトポロジー情報を各ノードに通知するための、ＬＡＳ（Ｌｉｎｋ  Ｓｔａｔｅ  Ａｄｖｅｒｔｉｓｅｍｅｎｔｓ；リンク状態広告）と呼ばれる機能について説明する。
ＯＳＰＦのルータ用ＬＳＡは図３７に示す様式を有する（ＲＦＣ２３８３付録Ａ）。図において、第０行から第４行は、ＬＳＡに共通のヘッダであり、第５行はルータ用ＬＳＡに特有のヘッダである。第０行の第２４から３１ビットはＬＳＡのタイプを示す場所で、１はルータ用ＬＳＡとなる。第５行の第１６から３１ビットの＃  ｌｉｎｋｓは、当該ルータに接続されているリンクの数を示す。第６行から第１０行は、そのうちの一つのリンクに関する情報を示す。第６行のＬｉｎｋ  ＩＤはリンクの識別子を示す。第７行のＬｉｎｋ  Ｄａｔａは、リンクのタイプに応じた特性を示す。リンクのタイプは、第８行の第１から７ビットのＴｙｐｅで示す。第８行の第８から１５ビットの＃  ＴＯＳでは、当該リンクで提供される異なるサービスタイプの数（追加分）を示す。サービスタイプが一個の場合は、＃  ＴＯＳはゼロとなる。第８行の第１６から３１ビットのｍｅｔｒｉｃは、当該リンクを特徴付ける属性（コスト）を示す。第１０行では、サービスタイプが１以上の場合に、そのタイプのｍｅｔｒｉｃなどを示す。第９行は、サービスタイプの個数分だけ第１０行が繰り返されることを示す。第１１行以降は、次のリンクに対して第６から１０行の様式が繰り返される。ＯＳＰＦバージョン２では、古いバージョンのＯＳＰＦとの整合性のために複数のサービスタイプをサポートする機能を有するが、実際にはほとんど使用されていない。
【００１２】
次に、通信ネットワークのトポロジー情報を更新する頻度、即ちＬＳＡを送付する頻度について説明する。ＯＳＰＦにおけるパラメータは、プロトコルで固定的に規定されている定数と、事情に応じて変更できる変数に分類できる。変数は、さらに、全体的に適用されるグローバル変数、当該ルータ周辺のエリアに適用されるエリア変数、当該ルータのインタフェースに適用されるルータインタフェース変数等に分類される。
ＯＳＰＦにおいて、ＬＳＡ送付の頻度を制御する代表的なパラメータは下記のとおりである。
定数
ＬＳＲｅｆｒｅｓｈＴｉｍｅ：  あるＬＳＡを再発生する最大間隔。３０分に固定。
ＭａｘＡｇｅ：  １個のＬＳＡの寿命。１時間に固定。
ＭｉｎＬＳＩｎｔｅｒｖａｌ：  あるＬＳＡを再発生する最小間隔。５秒に固定。
ＭｉｎＬＳＡｒｒｉｖａｌ：  あるＬＳＡを再受信する最小間隔。１秒に固定。
ＣｈｅｃｋＡｇｅ：  ＬＳＡのチェックサムが検査される間隔。５分に固定。
ＭａｘＡｇｅＤｉｆｆ：  あるＬＳＡが受信される時間差の最大値。１５分に固定。
変数
ＲｘｍｔＩｎｔｅｒｖａｌ：  ＬＳＡ再送を行う場合の待機時間。参考値は５秒。
【００１３】
従来例３．
ＯＳＰＦの上記のＬＳＡの一つの拡張方法である、ＩＥＴＦのＲＦＣ２３７０番であるＴｈｅ  Ｏｐａｑｕｅ  ＬＳＡ  Ｏｐｔｉｏｎ  （以下適宜、Ｏｐａｑｕｅ  ＬＳＡと略記する）に示されるＬＳＡについて説明する。
図３８は、Ｏｐａｑｕｅ  ＬＳＡのＬＳＡの様式を示す。図において、第０行から第４行は、ＬＳＡに共通のヘッダである。第１行の第２４から３１ビットはＬＳＡのタイプを示す場所で、Ｏｐａｑｕｅ  ＬＳＡにおいては、ＬＳＡを広告する範囲を示す。９はリンクローカル、１０はエリアローカル、１１は自律システム全域となっている。第１行はＩＥＴＦの規定に沿って拡張性のために設けられた部分であり、現在は使用していない。図の第５行以降のＯｐａｑｕｅ  Ｉｎｆｏｒｍａｔｉｏｎは、適用法に応じて使用することができる。
図３８のＯｐａｑｕｅ型ＬＳＡを用いることは、ＯＳＰＦのハローパケットと呼ばれるパケットのオプション部で示される。図３９に通常のＯＳＰＦのハローパケットのオプション部、図２９にＯｐａｑｕｅ型のハローパケットのオプション部を示す。図の第１ビットにＯビットがセットされている場合は、Ｏｐａｑｕｅ型であることを示す。
【００１４】
【発明が解決しようとする課題】
上記のような従来例１のルーチング方式では、最適経路設計を行う際に、各リンク１２のコストを実質上１に固定し、経路全体のコストは、経由するノード数（ホップ数）のみを考慮していた。各リンクを特徴付ける値として有効帯域を使用しているが、設定経路内の各リンクの有効帯域と要求帯域の大小比較を行うのみで、経路のコストには有効帯域の情報は組み込まれていなかった。なお、リンクのコストとは、一般に、距離、伝送品質、遅延等のリンクの属性を示すパラメータを指す。
また、従来例１のルーチング方式では、各リンクを特徴付ける数値としてを有効帯域のみを考慮しており、遅延等の他の属性の考慮の仕方は示されていなかった。
このため、ホップ数が少なく、かつ要求帯域を上回る経路が存在する場合は、他の条件を鑑みずにそれを選択してしまうという問題点があった。
また、従来例２においては、各リンクを特徴付けるメトリックあるいはコストを記載する部分として、第８行の第１６から３１ビットの１６ビットしか割り当てられていなかった。このため、リンクの帯域等広範囲の値をとる属性値を記載することが困難であった。
【００１５】
この発明は、上述のような課題を解決するためになされたもので、最適経路設計を行う際に、各リンク１２の有効帯域をそのリンクのコストに組み込み、有効帯域が大きければ大きいほどそのリンク１２を選択したい度合いが強まるようにしたものである。
また、リンク１２を特徴付ける数値として、有効帯域のみならず、遅延を代表とする他の品質パラメータも考慮出来るようにしたものである。
更に、従来例３に示すＯｐａｑｕｅ型のＬＳＡを使用して、ＯＳＰＦを拡張することも目的の一つとする。
【００１６】
また、上記のような従来例１のルーチング方式を始めとする大部分のルーチング方式では、最適経路計算をパソコンやワークステーションで行うことを前提としており、最適経路計算に時間がかかる上、多数の無線端末をネットワーク内に配置する場合に、各々の端末に経路設計機能を組込むことは困難であるという問題点があった。
【００１７】
この発明は、上述のような課題を解決するためになされたもので、最適経路設計をパソコンやワークステーション等の机上用コンピュータで行うのではなく、ハードウェア論理回路に実装して行うことにより、高速な経路計算を可能とするものである。
また、ハードウェア論理回路で実現することにより、ＬＳＩ化が容易となり、小型化、低価格化により、経路設計装置を無線インターネット内に多数配置される無線端末毎に組込むことを可能とするものである。
【００１８】
【課題を解決するための手段】
この発明に係る通信経路設定装置は、
複数のノードと複数のリンクとを有するネットワークに関して、前記複数のノード間の通信経路の設定を行う通信経路設定装置において、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第一の通信特性のレベルを示す第一通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第一通信特性リンク情報を作成する第一通信特性リンク情報作成部と、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第二の通信特性のレベルを示す第二通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第二通信特性リンク情報を作成する第二通信特性リンク情報作成部と、
前記第一通信特性リンク情報作成部により作成された前記第一通信特性リンク情報に含まれる第一通信特性レベル値と前記第二通信特性リンク情報作成部により作成された前記第二通信特性リンク情報に含まれる第二通信特性レベル値とを前記複数のリンクの各々のリンクについて関連づけ、前記第一通信特性レベル値に関連づけられた前記第二通信特性レベル値を用いて前記第一通信特性リンク情報を前記第二通信特性レベル値ごとに分類し、前記第二通信特性レベル値ごとに分類された複数の分類第一通信特性リンク情報を作成する分類第一通信特性リンク情報作成部と、
前記分類第一通信特性リンク情報作成部により作成された前記複数の分類第一通信特性リンク情報のうち少なくとも一つ以上の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定部とを有することを特徴とする。
【００１９】
前記通信経路設定装置は、更に、
前記分類第一通信特性リンク情報作成部により作成された前記複数の分類第一通信特性リンク情報から、特定の分類第一通信特性リンク情報を選択する分類第一通信特性リンク情報選択部を有し、
前記通信経路設定部は、前記分類第一通信特性リンク情報選択部により選択された前記特定の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定部とを有することを特徴とする。
【００２０】
前記通信経路設定装置は、更に、
前記第二通信特性レベル値についての要求値である要求第二通信特性レベル値を取得する要求取得部を有し、
前記分類第一通信特性リンク情報選択部は、前記複数の分類第一通信特性リンク情報から、前記要求取得部により取得された前記要求第二通信特性レベル値に合致する第二通信特性レベル値に基づいて分類された分類第一通信特性リンク情報を選択することを特徴とする。
【００２１】
前記通信経路設定装置は、更に、
前記第一通信特性レベル値についての要求値である要求第一通信特性レベル値を取得する要求取得部と、
前記特定の分類第一通信特性リンク情報に含まれる前記第一通信特性レベル値のうち前記要求取得部により取得された前記要求第一通信特性レベル値に合致しない第一通信特性レベル値を無効とする第一通信特性レベル値無効部とを有し、
前記経路設定部は、前記第一通信特性レベル値無効部により無効にされた第一通信特性レベル値を含む前記特定の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定することを特徴とする。
【００２２】
前記通信経路設定部は、前記分類第一通信特性リンク情報作成部により作成された前記複数の分類第一通信特性リンク情報の各々を用いて、前記複数の分類第一通信特性リンク情報ごとに複数の通信経路を設定し、
前記通信経路設定装置は、更に、
前記第二通信特性レベル値についての要求値である要求第二通信特性レベル値を取得する要求取得部と、
前記通信経路設定部により設定された前記複数の通信経路から、前記要求取得部により取得された前記要求第二通信特性レベル値に合致する第二通信特性レベル値に基づいて分類された分類第一通信特性リンク情報を用いて設定された通信経路を選択する通信経路選択部とを有することを特徴とする。
【００２３】
前記通信経路設定装置は、更に、
前記複数のリンクの各々に設定された第一通信特性レベル値と前記第二通信特性レベル値とを前記複数のノードに通知する通知パケットであって、前記第一通信特性レベル値を少なくとも３２ビット以上の二進数で表し、前記第二通信特性レベル値の各レベル値ごとに設けられた所定のビットをセットすることにより前記第二通信特性レベル値を表す通知パケットを作成する通知パケット作成部を有することを特徴とする。
【００２４】
前記通信経路設定装置は、更に、前記通知パケット作成部により作成された前記通知パケットを前記複数のノードに送信する通知パケット送信部を有し、
前記通知パケット作成部は、前記通知パケット送信部による前記通知パケットの送信の送信間隔を３０分以下の任意の時間に設定することを特徴とする。
【００２５】
この発明に係る通信経路設定方法は、
複数のノードと複数のリンクとを有するネットワークに関して、前記複数のノード間の通信経路の設定を行う通信経路設定方法において、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第一の通信特性のレベルを示す第一通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第一通信特性リンク情報を作成する第一通信特性リンク情報作成ステップと、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第二の通信特性のレベルを示す第二通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第二通信特性リンク情報を作成する第二通信特性リンク情報作成ステップと、
前記第一通信特性リンク情報作成ステップにより作成された前記第一通信特性リンク情報に含まれる第一通信特性レベル値と前記第二通信特性リンク情報作成ステップにより作成された前記第二通信特性リンク情報に含まれる第二通信特性レベル値とを前記複数のリンクの各々のリンクについて関連づけ、前記第一通信特性レベル値に関連づけられた前記第二通信特性レベル値を用いて前記第一通信特性リンク情報を前記第二通信特性レベル値ごとに分類し、前記第二通信特性レベル値ごとに分類された複数の分類第一通信特性リンク情報を作成する分類第一通信特性リンク情報作成ステップと、
前記分類第一通信特性リンク情報作成ステップにより作成された前記複数の分類第一通信特性リンク情報のうち少なくとも一つ以上の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定ステップとを有することを特徴とする。
【００２６】
前記通信経路設定方法は、更に、
前記分類第一通信特性リンク情報作成ステップにより作成された前記複数の分類第一通信特性リンク情報から、特定の分類第一通信特性リンク情報を選択する分類第一通信特性リンク情報選択ステップを有し、
前記通信経路設定ステップは、前記分類第一通信特性リンク情報選択ステップにより選択された前記特定の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定ステップとを有することを特徴とする。
【００２７】
前記通信経路設定方法は、更に、
前記第二通信特性レベル値についての要求値である要求第二通信特性レベル値を取得する要求取得ステップを有し、
前記分類第一通信特性リンク情報選択ステップは、前記複数の分類第一通信特性リンク情報から、前記要求取得ステップにより取得された前記要求第二通信特性レベル値に合致する第二通信特性レベル値に基づいて分類された分類第一通信特性リンク情報を選択することを特徴とする。
【００２８】
前記通信経路設定方法は、更に、
前記第一通信特性レベル値についての要求値である要求第一通信特性レベル値を取得する要求取得ステップと、
前記特定の分類第一通信特性リンク情報に含まれる前記第一通信特性レベル値のうち前記要求取得ステップにより取得された前記要求第一通信特性レベル値に合致しない第一通信特性レベル値を無効とする第一通信特性レベル値無効ステップとを有し、
前記経路設定ステップは、前記第一通信特性レベル値無効ステップにより無効にされた第一通信特性レベル値を含む前記特定の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定することを特徴とする。
【００２９】
前記通信経路設定ステップは、前記分類第一通信特性リンク情報作成ステップにより作成された前記複数の分類第一通信特性リンク情報の各々を用いて、前記複数の分類第一通信特性リンク情報ごとに複数の通信経路を設定し、
前記通信経路設定方法は、更に、
前記第二通信特性レベル値についての要求値である要求第二通信特性レベル値を取得する要求取得ステップと、
前記通信経路設定ステップにより設定された前記複数の通信経路から、前記要求取得ステップにより取得された前記要求第二通信特性レベル値に合致する第二通信特性レベル値に基づいて分類された分類第一通信特性リンク情報を用いて設定された通信経路を選択する通信経路選択ステップとを有することを特徴とする。
【００３０】
前記通信経路設定方法は、更に、
前記複数のリンクの各々に設定された第一通信特性レベル値と前記第二通信特性レベル値とを前記複数のノードに通知する通知パケットであって、前記第一通信特性レベル値を少なくとも３２ビット以上の二進数で表し、前記第二通信特性レベル値の各レベル値ごとに設けられた所定のビットをセットすることにより前記第二通信特性レベル値を表す通知パケットを作成する通知パケット作成ステップを有することを特徴とする。
【００３１】
前記通信経路設定方法は、更に、前記通知パケット作成ステップにより作成された前記通知パケットを前記複数のノードに送信する通知パケット送信ステップを有し、
前記通知パケット作成ステップは、前記通知パケット送信ステップによる前記通知パケットの送信の送信間隔を３０分以下の任意の時間に設定することを特徴とする。
【００３２】
本発明に係る通信経路設定方法をコンピュータ実行させるためのプログラムは、
複数のノードと複数のリンクとを有するネットワークに関して、前記複数のノード間の通信経路の設定を行う通信経路設定方法において、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第一の通信特性のレベルを示す第一通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第一通信特性リンク情報を作成する第一通信特性リンク情報作成ステップと、
前記複数のリンクの各々のリンクを識別するリンク識別情報であって、前記各々のリンクの第二の通信特性のレベルを示す第二通信特性レベル値が前記各々のリンクごとに設定されたリンク識別情報である第二通信特性リンク情報を作成する第二通信特性リンク情報作成ステップと、
前記第一通信特性リンク情報作成ステップにより作成された前記第一通信特性リンク情報に含まれる第一通信特性レベル値と前記第二通信特性リンク情報作成ステップにより作成された前記第二通信特性リンク情報に含まれる第二通信特性レベル値とを前記複数のリンクの各々のリンクについて関連づけ、前記第一通信特性レベル値に関連づけられた前記第二通信特性レベル値を用いて前記第一通信特性リンク情報を前記第二通信特性レベル値ごとに分類し、前記第二通信特性レベル値ごとに分類された複数の分類第一通信特性リンク情報を作成する分類第一通信特性リンク情報作成ステップと、
前記分類第一通信特性リンク情報作成ステップにより作成された前記複数の分類第一通信特性リンク情報のうち少なくとも一つ以上の分類第一通信特性リンク情報を用いて前記複数のノード間の前記通信経路を設定する通信経路設定ステップとを有する通信経路設定方法をコンピュータに実行させるためのプログラムである。
【００３３】
本発明に係る無線通信ネットワークの通信経路設定装置は、
無線通信ネットワークの複数個の無線ノードと無線ノード間の無線リンクに関し、無線ノードの隣接関係と無線リンクの属性を用いて、発信無線ノードと着信無線ノードの無線ノード間の経路を設定する装置であって、以下の要素を含むことを特徴とする。
複数個の無線ノードに対し、無線ノードの隣接関係と無線ノード間の無線リンクの属性を予め記憶する記憶部；
始点ノードである発信無線ノード及び終点ノードである着信無線ノードを指定するノード指定部；
前記発信無線ノード及び前記着信無線ノードのいずれか一方の無線ノードに対し、二値からなる状態数のうちいずれか一方の値の状態数を設定し、その他の各無線ノードに対して、他方の値の状態数を設定する初期化部；
前記一方の無線ノードに設定された一方の値の状態数と、前記その他の各無線ノードに設定された他方の値の状態数とを変化させずに経時的に推移させて、状態数の経時的な推移を記録し、
前記一方の無線ノードに隣接する無線ノードから順に、前記その他の各無線ノードと各無線ノードに隣接する無線ノードとの間の無線リンクの属性に基づいて、前記その他の各無線ノードに隣接する無線ノードに対する状態数の記録の中から無線リンクの属性に対応する一つの状態数の記録を参照し、参照した状態数の値が前記一方の値である場合に、前記その他の各無線ノードの状態数を前記他方の値から前記一方の値に変化させ、
前記その他の各無線ノードに設定された状態数の値を前記他方の値から前記一方の値へ変化させる迄は前記他方の値にて状態数を経時的に推移させて記録し、状態数を前記他方の値から前記一方の値へ変化させた後は前記一方の値にて状態数を経時的に推移させて記録する状態数変化部；
前記その他の各無線ノードに設定された状態数の前記一方の値への変化を検出し、変化を誘引した隣接無線ノードを検出する検出部；
前記検出部における検出結果に基づき、前記変化を誘引した隣接無線ノードを経路を設定する無線ノードとして、逐次、着信無線ノード及び発信無線ノードのうち一方の無線ノード側から他方の無線ノード側に向かって選定する選定部。
【００３４】
前記選定部は、以下の第１の選定部と第２の選定部とから構成されることを特徴とする。
着信無線ノード及び発信無線ノードのうち一方の無線ノードについて、隣接する無線ノードの状態数の前記一方の値への変化に基づき、前記隣接する無線ノードの中から、前記一方の無線ノードとの接続を設定する設定無線ノードを選定する第１の選定部；
設定無線ノードとして選定された無線ノードについて、前記検出部による検出結果に基づき、隣接する無線ノードの中から自無線ノードとの接続を設定する無線ノードを選定することを、着信無線ノード及び発信無線ノードのうち他方の無線ノードが選定される迄、逐次遂行する第２の選定部。
【００３５】
前記状態数変化部は、以下の状態数算出部から構成されることを特徴とする。
隣接無線ノードに対する無線リンク属性に基づく時間前の状態数の値に基づき、状態数を算出する状態数算出部。
【００３６】
前記記憶部は、無線リンクの属性として無線強度を記憶し、
前記状態数変化部は、無線リンクの属性として無線強度を用いることを特徴とする。
【００３７】
前記無線通信ネットワークの通信経路設定装置は、前記状態数変化部と検出部とをハードウエア論理回路で実現することを特徴とする。
【００３８】
前記状態数変化部と検出部は、記憶部に記憶された各無線ノード毎に異なる無線ノードの隣接関係と無線ノード間の無線リンク属性の利用を複数の同一のハードウエア回路で実現することを特徴とする。
【００３９】
本発明に係る無線通信ネットワークの通信経路設定方法は、
無線通信ネットワークの複数個の無線ノードと無線ノード間の無線リンクに関し、無線ノードの隣接関係と無線リンクの属性を用いて、発信無線ノードと着信無線ノードの無線ノード間の経路を設定する方法であって、以下のステップを含むことを特徴とする。
複数個の無線ノードに対し、無線ノードの隣接関係と無線ノード間の無線リンクの属性を予め記憶する記憶ステップ；
始点ノードである発信無線ノード及び終点ノードである着信無線ノードを指定するノード指定ステップ；
前記発信無線ノード及び前記着信無線ノードのいずれか一方の無線ノードに対し、二値からなる状態数のうちいずれか一方の値の状態数を設定し、その他の各無線ノードに対して、他方の値の状態数を設定する初期化ステップ；
前記一方の無線ノードに設定された一方の値の状態数と、前記その他の各無線ノードに設定された他方の値の状態数とを変化させずに経時的に推移させて、状態数の経時的な推移を記録し、
前記一方の無線ノードに隣接する無線ノードから順に、前記その他の各無線ノードと各無線ノードに隣接する無線ノードとの間の無線リンクの属性に基づいて、前記その他の各無線ノードに隣接する無線ノードに対する状態数の記録の中から無線リンクの属性に対応する一つの状態数の記録を参照し、参照した状態数の値が前記一方の値である場合に、前記その他の各無線ノードの状態数を前記他方の値から前記一方の値に変化させ、
前記その他の各無線ノードに設定された状態数の値を前記他方の値から前記一方の値へ変化させる迄は前記他方の値にて状態数を経時的に推移させて記録し、状態数を前記他方の値から前記一方の値へ変化させた後は前記一方の値にて状態数を経時的に推移させて記録する状態数変化ステップ；
前記その他の各無線ノードに設定された状態数の前記一方の値への変化を検出し、変化を誘引した隣接無線ノードを検出する検出ステップ；
前記検出ステップにおける検出結果に基づき、前記変化を誘引した隣接無線ノードを経路を設定する無線ノードとして、逐次、着信無線ノード及び発信無線ノードのうち一方の無線ノード側から他方の無線ノード側に向かって選定する選定ステップ。
【００４０】
前記選定ステップは、以下の第１の選定ステップと第２の選定ステップとから構成されることを特徴とする。
着信無線ノード及び発信無線ノードのうち一方の無線ノードについて、隣接する無線ノードの状態数の前記一方の値への変化に基づき、前記隣接する無線ノードの中から、前記一方の無線ノードとの接続を設定する設定無線ノードを選定する第１の選定ステップ；
設定無線ノードとして選定された無線ノードについて、前記検出ステップによる検出結果に基づき、隣接する無線ノードの中から自無線ノードとの接続を設定する無線ノードを選定することを、着信無線ノード及び発信無線ノードのうち他方の無線ノードが選定される迄、逐次遂行する第２の選定ステップ。
【００４１】
前記状態数変化ステップは、以下の状態数算出ステップから構成されることを特徴とする。
隣接無線ノードに対する無線リンク属性に基づく時間前の状態数の値に基づき、状態数を算出する状態数算出ステップ。
【００４２】
前記記憶ステップは、無線リンクの属性として無線強度を記憶し、
前記状態数変化ステップは、無線リンクの属性として無線強度を用いることを特徴とする。
【００４３】
本発明に係る無線通信ネットワークの通信経路設定方法をコンピュータに実行させるためのプログラムは、
無線通信ネットワークの複数個の無線ノードと無線ノード間の無線リンクに関し、無線ノードの隣接関係と無線リンクの属性を用いて、発信無線ノードと着信無線ノードの無線ノード間の経路を設定する方法であって、以下のステップを含む、無線通信ネットワークの通信経路設定方法をコンピュータに実行させるためのプログラムである。
複数個の無線ノードに対し、無線ノードの隣接関係と無線ノード間の無線リンクの属性を予め記憶する記憶ステップ；
始点ノードである発信無線ノード及び終点ノードである着信無線ノードを指定するノード指定ステップ；
前記発信無線ノード及び前記着信無線ノードのいずれか一方の無線ノードに対し、二値からなる状態数のうちいずれか一方の値の状態数を設定し、その他の各無線ノードに対して、他方の値の状態数を設定する初期化ステップ；
前記一方の無線ノードに設定された一方の値の状態数と、前記その他の各無線ノードに設定された他方の値の状態数とを変化させずに経時的に推移させて、状態数の経時的な推移を記録し、
前記一方の無線ノードに隣接する無線ノードから順に、前記その他の各無線ノードと各無線ノードに隣接する無線ノードとの間の無線リンクの属性に基づいて、前記その他の各無線ノードに隣接する無線ノードに対する状態数の記録の中から無線リンクの属性に対応する一つの状態数の記録を参照し、参照した状態数の値が前記一方の値である場合に、前記その他の各無線ノードの状態数を前記他方の値から前記一方の値に変化させ、
前記その他の各無線ノードに設定された状態数の値を前記他方の値から前記一方の値へ変化させる迄は前記他方の値にて状態数を経時的に推移させて記録し、状態数を前記他方の値から前記一方の値へ変化させた後は前記一方の値にて状態数を経時的に推移させて記録する状態数変化ステップ；
前記その他の各無線ノードに設定された状態数の前記一方の値への変化を検出し、変化を誘引した隣接無線ノードを検出する検出ステップ；
前記検出ステップにおける検出結果に基づき、前記変化を誘引した隣接無線ノードを経路を設定する無線ノードとして、逐次、着信無線ノード及び発信無線ノードのうち一方の無線ノード側から他方の無線ノード側に向かって選定する選定ステップ。
【００４４】
【発明の実施の形態】
実施の形態１．
この発明は、特開平０９−１１６５７３号および特開平１１−５５３１２による最適経路設計方法を用いて、既にインターネットで広く使用されているルーチングプロトコルであるＲＦＣ２３８３番のＯＳＰＦ  Ｖｅｒｓｉｏｎ  ２において、経路の通信品質を考慮できるようにしたＯＳＰＦの拡張方式である。この発明の最適経路設計は、特開平０９−１１６５７３号（特願平８−４４８６５号）の実施の形態７で示した最適経路設計法の応用で、発信ノードｓを基準にして経路設計を行う実施の形態１０に示す方法に基くものである。
【００４５】
図１はこの発明の実施の形態１に係る通信経路設定装置がルーチングを行う通信ネットワークの例である。
図において、１はルーチングの対象となる通信ネットワーク、１１は通信信号の発着中継を行うルーターに代表されるノードＮｉ（ｉ＝１，２，・・・，９）、１２はノードＮｉとＮｊ間の物理接続回線であるリンク、１２ＳＬはノードＮｉとＮｊ間の衛星接続回線である衛星回線リンク、各ノード１１の円内に記載されている番号は各々のノードの番号で、ノードＮｉの添字ｉがこれに対応する。ここでノードＮｉとノードＮｊ間のリンクには方向性があるものとし、ノードＮｉからＮｊ向かうリンクをリンクＬｉｊと記す。一般にはリンクＬｉｊとリンクＬｊｉは異なるが、図１の例では、便宜上全てのリンク１２は両方向性とする。
各リンク１２には、リンク１２の通信特性の一つとしてそれぞれの有効帯域が記されている。リンクＬｉｊの有効帯域Ｃｉｊとは、リンクＬｉｊの帯域のうち、使用可能な帯域を示す。また、リンク１２の別の通信特性である伝送遅延についても、衛星回線リンク１２ＳＬと通常のリンク１２の伝送遅延の例を図３のリンクと遅延の対応表ＬＫＤＬに示す。衛星回線リンク１２ＳＬの遅延は３００ミリ秒、通常のリンク１２の遅延は２０ミリ秒と、衛星回線リンクの遅延は非常に大きい。
【００４６】
図１において図示していないが、各々のノード１１には本実施の形態に係る通信経路設定装置１００が設けられている。
図２は、通信経路設定装置１００の機能ブロック図である。
図２において、１０１は各ノード１１で発生する経路設定要求を取得する要求取得部である。１０２は、通信ネットワーク１全体のトポロジー情報を記録しているトポロジー情報記録部である。トポロジー情報は、図４に示すトポロジー帯域表ＴＰＢＷ、図５に示すトポロジー遅延表ＴＰＤＬ等から構成される。１０３は、第一通信特性リンク情報（例えば、図８に示すトポロジーコスト表ＴＰＣ）を作成する第一通信特性リンク情報作成部である。なお、第一通信特性リンク情報の詳細については後述する。１０４は、第二通信特性リンク情報（例えば、図９に示すトポロジー遅延コード表ＴＰＤＬＣＤ）を作成する第二通信特性リンク情報作成部である。なお、第二通信特性リンク情報については後述する。１０５は、第一通信特性リンク情報（例えば、図８に示すトポロジーコスト表ＴＰＣ）を第二通信特性レベル値（例えば、遅延コード）に基づいて分類し、分類された複数の分類第一通信特性リンク情報（例えば、図１４のトポロジー遅延別コスト表（遅延コード５以下）ＴＰＣＤ５又は図１５のトポロジー遅延別コスト表（遅延コード４以下）ＴＰＣＤ４）を作成する分類第一通信特性リンク情報作成部である。分類第一通信特性リンク情報の詳細についても後述する。１０６は、複数の分類第一通信特性リンク情報から特定の分類第一通信特性リンク情報を選択する分類第一通信特性リンク情報選択部である。前出の例では、図１４と図１５に示すトポロジー遅延別コスト表のうち、例えば、図１４のトポロジー遅延別コスト表を選択する。１０７は、分類第一通信特性リンク情報選択部により選択された分類第一通信特性リンク情報に含まれるリンク情報を無効にする第一通信特性レベル値無効部である。例えば、図１４のトポロジー遅延別コスト表に含まれる要素（４，５）＝１を無効にして（４，５）＝∞にするといった処理を行う。１０８は、ノード１１間の最適経路設計を行う通信経路設定部である。１０９は、通信ネットワークのトポロジー情報を他のノードに通知するための通知パケットを作成する通知パケット作成部である。１１０は、通知パケット作成部１０９において作成された通知パケットを他のノード１１に向けて送信する通知パケット送信部である。
なお、これら１０１〜１１０の各機能をコンピュータに実行させるためのプログラムとすることが可能であり、また、これら１０１〜１１０の各機能のコンピュータプログラムをコンピュータ読み取り可能な記録媒体に記録することも可能である。
【００４７】
次に、図４及び図５に示すトポロジー情報について説明する。
図４のトポロジー帯域表ＴＰＢＷでは、リンクの第一の通信特性の例として有効帯域が示されている。図４のトポロジー帯域表ＴＰＢＷではｉ行ｊ列の要素（ｉ，ｊ）が、リンクＬｉｊの有効帯域Ｃｉｊを示す。
図５のトポロジー遅延表ＴＰＤＬでは、リンクの第二の通信特性の例として遅延が示されている。図５のトポロジー遅延表ＴＰＤＬでは、ｉ行ｊ列の要素（ｉ，ｊ）が、リンクＬｉｊの遅延Ｄｉｊを示す（単位はミリ秒）。例えば、リンクＬ１２は通常のリンクなので、図３より遅延は２０ｍｓとなり、図５のトポロジー遅延表ＴＰＤＬのＤ１２は２０となっている。一方、リンクＬ４５は衛星回線リンクなので、Ｄ４５は３００となっている。
なお、本明細書では第一の通信特性の例として有効帯域を、第二の通信特性の例として遅延を扱っているが、この他の通信特性についても同様に適用可能である。
【００４８】
次に、第一通信特性リンク情報について説明する。
第一通信特性リンク情報とは、各リンクの第一の通信特性（有効帯域）を所定のレベル値（第一通信特性レベル値）に変換し、変換したレベル値（第一通信特性レベル値）をリンクごとに表す情報であり、例えば、図８に示すトポロジーコスト表ＴＰＣにおいて示される情報である。
図８のトポロジーコスト表ＴＰＣは、図４のトポロジー帯域表ＴＰＢＷの帯域を、図６の有効帯域とコストの対応表ＢＷＣＳＴに従ってコストＷｉｊに変換したものである。図８においては、コストＷｉｊが第一通信特性レベル値である。そして、図８のトポロジーコスト表ＴＰＣに対応するネットワーク図は図１０である。
リンクのコストとは、一般に、距離、伝送品質、遅延等のリンクの属性を示すパラメータで、その値の大きさに比例して、当該リンクの選択を回避したい度合いが高まるように設定する。この実施の形態におけるリンクのコストは、その有効帯域に依存している。
有効帯域は、大きいほど、当該リンクを選択したい度合いが高いので、コストは増減が逆になるように設定する必要がある。即ち、有効帯域が大きい程コストは小さく、有効帯域が小さい程コストは大きくなるように、コストを設定する。
コストを有効帯域の逆数としてもよいが、有効帯域の細かい変動に敏感に対応するよりも、広範囲の有効帯域をカバーすることを目的として、ここでは、コストを有効帯域の桁数の逆順になるようにとる。図８のトポロジーコスト表ＴＰＣで無限大となっている要素は、実際は、他の要素に比べて十分大きな数に設定することを示す。
なお、以下の説明では、コストを第一通信特性レベル値として、図８のトポロジーコスト表を第一の通信特性リンク情報として説明する。
【００４９】
次に、第二通信特性リンク情報とは、各リンクの第二の通信特性（遅延）を所定のレベル値（第二通信特性レベル値）に変換し、変換したレベル値（第二通信特性レベル値）をリンクごとに表す情報であり、例えば、図９のトポロジー遅延コード表ＴＰＤＬＣＤにおいて示される情報である。
図９のトポロジー遅延コード表ＴＰＤＬＣＤは、図５のトポロジー遅延表ＴＰＤＬの遅延を、図７の遅延と遅延コードの対応表ＤＬＣＤに従ってコード化したものである。即ち、図９においては、遅延ＤＣｉｊが第二通信特性レベル値である。
リンクＬ１２の遅延Ｄ１２は２０ｍｓであり、図７の遅延コードに置き換えると４となり、図９のトポロジー遅延コード表ＴＰＤＬＣＤのＤＣ１２には４が記入される。同様に、リンクＬ４５の遅延Ｄ１２は３００ｍｓであり、図７の遅延コードに置き換えると５となり、図９のトポロジー遅延コード表ＴＰＤＬＣＤのＤＣ１２には５が記入される。
図７の遅延コード対応表ＤＬＣＤでは、８段階に渡って遅延を分類しているが、この分類表を部分的に使用することや、分類方法を変更することも可能である。
なお、以下の説明では、遅延を第二通信特性レベル値として、図９のトポロジー遅延コード表を第二の通信特性リンク情報として説明する。
【００５０】
この通信経路設定装置１００では、図４と図５、及びこれらから作成した図８と図９に示すトポロジー情報をもとに、各ノード１１につき、そのノードを発信源として通信ネットワーク１内の全ての他のノード１１を宛先とした最適経路を設計する。この発明における最適経路とは、下記の条件を満たす経路である。
（１）経路のコストが最小
（２）経路の有効帯域が要求帯域以上
（３）経路内の各リンクの遅延の最大値が要求遅延以下
但し、経路のコストとは、経路内のリンクおよびノードのコストの総和である。ここでは便宜上、ノードのコストはゼロとするが、ノードのコストがゼロでない場合は、ノードに隣接するリンクのコストにノードのコストを加算することで、容易に拡張できる。また、経路の有効帯域とは、経路中の各リンクの有効帯域の最小値となる。また、（３）の条件は、経路内の全リンクの遅延の総和が要求遅延以下ということではなく、経路内の各リンクの遅延の最大値が要求帯域以下ということである。
【００５１】
次に、この実施の形態の通信経路設定装置１００の最適経路設計の流れを、図１２および図１３について説明する。図１２は、この実施の形態における最適経路設計において、個別の経路設計の要求に依存しない処理である。個別の経路設計が発生する前にあらかじめ行っておくことができる。
図１２の通信ネットワーク１は、図１の通信ネットワーク１と同じものであるが、図１２では簡単のため、ノードＮ１の周辺のみを示している。図１２の他のネットワーク図についても、同様に一部分のみを示している。
前述のように、図１２の通信ネットワーク１は、図４のトポロジー帯域表ＴＰＢＷおよび図５のトポロジー遅延表ＴＰＤＬで特徴付けられている。通信ネットワーク１の各リンクの帯域を、図６の帯域コストの対応表ＢＷＣＳＴによってコストに変換したものが、ネットワークモデル２である。ネットワークモデル２は、図８のトポロジーコスト表ＴＰＣで特徴付けられる。ネットワークモデル２の全体は、図１０で示される。また、図の表面には明示されないが、遅延特性は図５のトポロジー遅延表ＴＰＤＬで特徴付けられる。
【００５２】
ネットワークモデル２を、許容遅延によって分類したのが、遅延コード別ネットワークモデル２Ｄ４および２Ｄ５である。それぞれの図の全体は、図１０および図１１で示される。遅延コードｘ以下のリンクによるネットワークモデル２Ｄｘは、ネットワークモデル２において、遅延コードがｘを超えるリンクを削除し、遅延コードがｘ以下のリンクのみを抽出したものである。
つまり、ネットワークモデル２Ｄ４とは、遅延コードが４を超えるリンクを削除し、遅延コードが４以下のリンクを抽出したものであり、ネットワークモデル２Ｄ５とは、遅延コードが５を超えるリンクを削除し、遅延コードが５以下のリンクを抽出したものである。ネットワークモデル２Ｄ４を示した図１０とネットワークモデル２Ｄ５を示した図１１とを比較すると図１０に表されているＬ４５及びＬ７８が図１１では削除されている。これは、Ｌ４５及びＬ７８の衛星回線１２ＳＬリンクは遅延コードが５であるため、ネットワークモデル２Ｄ４（図１１）において削除されたためである。
遅延コード５以下のリンクによるネットワークモデル２Ｄ５は、複数の分類第一通信特性リンク情報の一つである図１４のトポロジー遅延別コスト表で特徴付けられる。遅延コード４以下のリンクによるネットワークモデル２Ｄ４は、複数の分類第一通信特性リンク情報の別の一つである図１５のトポロジー遅延別コスト表で特徴付けられる。
【００５３】
図１４のトポロジー遅延別コスト表ＴＰＣＤ５及び図１５のトポロジー遅延別コスト表ＴＰＣＤ４は、分類第一通信特性リンク情報作成部１０５により作成され、図８のトポロジーコスト表ＴＰＣと図９のトポロジー遅延コード表ＴＰＤＬＣＤに基づいて作成される。つまり、分類第一通信特性リンク情報作成部は、図８のトポロジーコスト表に含まれるコストＷｉｊと図９のトポロジー遅延コード表に含まれる遅延ＤＣｉｊを各リンクごとに関連づけ、関連づけた遅延ＤＣｉｊの値ごとに図８のトポロジーコスト表を分類して、図１４のトポロジー遅延別コスト表ＴＰＣＤ５及び図１５のトポロジー遅延別コスト表ＴＰＣＤ４を作成する。
まず、図１５のトポロジー遅延別コスト表ＴＰＣＤ４の作成手順について説明する。図１５のトポロジー遅延別コスト表ＴＰＣＤ４では、図８のトポロジーコスト表に含まれる要素のうち、図９のトポロジー遅延コード表において遅延コードが４以下の要素については、図８の値をそのまま用い、図９のトポロジー遅延コード表において遅延コードが４以上となっている要素では、図８の値に代えて無限大を記入する。
図１５のトポロジー遅延別コスト表ＴＰＣＤ４では、リンクＬ４５、リンクＬ７８に対応する（４，５）、（５，４）、及び（７，８）（８，７）が無限大となっている。
そして、この図１５のトポロジー遅延別コスト表ＴＰＣＤ４で特徴づけられるネットワークモデル２Ｄ４では、前述したようにリンクＬ４５、Ｌ７８が削除されることになる。
一方、図１４においては、図９のトポロジー遅延コード表において遅延コードが５を超えるリンクが存在しないため、図８の各要素の値がそのまま用いられ、結果として図８のトポロジーコスト表ＴＰＣと図１４のトポロジー遅延別コスト表ＴＰＣＤ５とは同じ内容となっている。
【００５４】
図１２において説明したネットワークモデルの遅延別分類の処理が行われた後、図１３に示す処理が行われる。
図１３は、この実施の形態における最適経路設計において、個別の経路設計の要求に依存する処理であり、個別の経路設計が発生してから行う。ここでは、要求帯域Ｒ＝５、要求遅延ＲＤ＝５００ミリ秒の経路設計要求が発生したとする。図において、ＲＥＱ１は要求帯域Ｒ＝５、要求遅延ＲＤ＝５００ミリ秒の経路設計要求を模式的に示す。
【００５５】
要求取得部１０１は、経路設計要求ＲＥＱ１を取得し、更に経路設計要求ＲＥＱ１に対し、図６の帯域コスト対応表ＢＷＣＳＴを参照して要求帯域５を許容コスト４に変換し、図７の遅延コード対応表ＤＬＣＤを参照して要求遅延５００を遅延コード５に変換してコード化された経路設計要求ＲＥＱ１ＣＤを用意する。この要求を受けて、分類第一通信特性リンク情報選択部１０６が、遅延コード別に分類された遅延コード別ネットワークモデル２Ｄ４と２Ｄ５から、遅延コード５以下のネットワークモデル２Ｄ５を選択する。換言すると、分類第一通信特性リンク情報選択部１０６は、分類第一通信特性リンク情報である図１４のトポロジー遅延別コスト表と図１５のトポロジー遅延別コスト表のうち図１４のトポロジー遅延別コスト表を選択する。
次に、第一通信特性レベル値無効部が、遅延コード５以下のネットワークモデル２Ｄ５から、許容コスト４を超えるリンクを削除し（無効とし）、遅延コード５以下、許容コスト４以下のリンクによる設計要求対応ネットワークモデル２ＲＥＱを求める。即ち、ネットワークモデル２Ｄ５を特徴付ける図１４のトポロジー遅延別コスト表ＴＰＣＤ５において、許容コスト４を超えるリンクのコストを無限大として、図１６の設計要求対応トポロジーコスト表ＴＰＣＲＥＱを求める。
以上の処理により図１６の設計要求対応トポロジーコスト表ＴＰＣＲＥＱが求められた後は、この設計要求対応トポロジーコスト表に基づいて通信経路設定部１０８が最適経路設計を行う。
なお、図１３の例では、右上のネットワークモデル２Ｄ５と、左下のネットワークモデル２ＲＥＱは同じである。これは、ネットワークモデル２Ｄ５には、リンクコストが４を超えるリンクが存在しないためである。同様に、図１４のトポロジー遅延別コスト表と、図１６の設計要求対応トポロジーコスト表ＴＰＣＲＥＱも同じである。
ここで、ネットワークモデル２ＲＥＱ、およびそれを特徴付ける設計要求対応トポロジーコスト表ＴＰＣＲＥＱは、通信経路設定部１０８による経路の設計が終了したのちは、内容を保持しておく必要はない。
【００５６】
次に、図１３の設計要求対応ネットワークモデル２ＲＥＱ、およびこれを特徴付ける設計要求対応トポロジーコスト表ＴＰＣＲＥＱ（図１６）に対して、通信経路設定部１０８が最適経路の設定を行い、水先案内平面ＰＰを求める手順を説明する。なお、この最適経路設計の手順は、特開平０９−１１６５７３号の実施の形態７と同様の手順で行われる。
ここで、水先案内平面ＰＰとは、水先案内ベクトルＰｉ（ｓ）の集合をいい、水先案内ベクトルＰｉ（ｓ）とは、発信源ｓからノードＮｉへの最適経路において、ノードＮｉの前に経由する隣接ノードＡＳｉのノード番号である。
ここで、隣接ノードＡＳｉとは、ノードＮｉにリンクＬｊｉが入っている元のノードＮｊのノード番号ｊの集合を意味する。例えば、ノードＮ１は、ノードＮ２およびノードＮ４と接続されているので、ＡＳ１＝｛２，４｝となる。同様に、ＡＳ２＝｛１，３，４，５，６｝，ＡＳ３＝｛２，６，８｝，ＡＳ４＝｛１，２，５，７｝，ＡＳ５｛２，４，６，７｝，ＡＳ６＝｛２，３，５，７，８｝，ＡＳ７＝｛４，５，６，８，９｝，ＡＳ８＝｛３，６，７，９｝，Ａ９＝｛７，８｝となる。隣接ノードＡＳｉは、ネットワークの構成と一義的に対応しており、ネットワークの構成が変化しない限りは固定である。
【００５７】
図１９は、発信源ｓ＝１（ノードＮ１が発信源）の場合の、水先案内ベクトルＰｉ（１）および水先案内平面ＰＰの例を示している。
ノードＮ１を発信源としてＮ２〜Ｎ９の全てのノードに対する水先案内ベクトルＰｉ（１）が設定されれば、ノードＮ１に関する水先案内平面ＰＰが一面作成されたことになる。また、ノードＮ２を発信源として同様な水先案内ベクトルが設定されれば、ノードＮ２に関する水先案内ベクトルが一面作成されたことになる。従って、ノードＮ１〜Ｎ９の通信ネットワークにおいては、９面の水先案内ベクトル平面を作成することができる。
図１９の水先案内平面を数字で表現したものが、図２０あるいは図２１の水先案内表ＰＰＴである。
図２０では、ノードＮｉの水先案内ベクトルＰｉ（ｓ）をｉ＝１，２，・・・９について記してある。例えば、発信源Ｎ１（ｓ＝１）からノードＮ２（ｉ＝２）への最適経路設計においては、水先案内ベクトルＰ２（１）は、ノードＮ２の前に経由する隣接ノードＮ４のノード番号である４となる。即ち、Ｐ２（１）＝４となる。
図２１では、ノードＮｉの水先案内ベクトルＰｉ（ｓ）がｊであることを、要素（ｉ，ｊ）＝１として表す。ここでは、図２０を用いる。
例えば、発信源Ｎ１（ｓ＝１）からノードＮ２（ｉ＝２）への最適経路設計においては、水先案内ベクトルＰ２（１）は、要素（２，ｊ）のうち、１が記述された（２，４）（ｊ＝４）が該当し、Ｐ２（１）＝４となる。
【００５８】
次に、この実施の形態における最適経路設計において使用するパラメータ及びテーブルについて説明する。
水先案内ベクトルは、各ノードに設定された状態値Ｘｉをパラメータとして生成される。
状態値Ｘｉとは、０と１の２値のみをとり、また時刻ｔに依存するパラメータである。時刻依存性を明確にしたい場合はＸｉ（ｔ）と記す。ここで時刻ｔは、離散的な値ｔ＝０，１，２・・・をとる。時刻ｔは、更新周期ｔと同意味である。現在の時刻ｔ０の状態数Ｘｉ（ｔ０）、１単位時間前の時刻（ｔ０−１）の状態数Ｘｉ（ｔ０−１）、２単位時間前の時刻（ｔ０−２）の状態数Ｘｉ（ｔ０−２）と続いて、ネットワークモデル２のリンク１２のコストＷｉｊの最大値であるボリュームレベルＶＬ単位時間前の時刻（ｔ０−ＶＬ）の状態数Ｘｉ（ｔ０−ＶＬ）まで保持しておく必要がある。これを表すのが、図１７の状態遷移表ＳＴＣＨである。
【００５９】
次に、状態値Ｘｉ（ｔ）の変化および水先案内ベクトルの生成の規則を述べる。
状態値Ｘｉ（ｔ）は、次の規則１Ｓ，２Ｓに従って変化する。また、水先案内ベクトルＰｉ（ｓ）決定の規則は，次の規則３Ｓのようになる。
規則１Ｓ）時刻ｔ＝０では、発信ノードＮｓの状態値Ｘｓ（０）＝１、それ以外のノードＮｉについてはＸｉ（０）＝０とする。
規則２Ｓ）コストＷｊｉ時刻前の状態値Ｘｊ（ｔ−Ｗｊｉ）の値が１である隣接ノードＮｊが存在する場合には（ｊはＡＳｉの要素）、状態値Ｘｉ（ｔ）は１とする。それ以外の場合は、状態値Ｘｉ（ｔ）は０とする。発信源の状態値は常にＸｓ（ｔ）＝１とする。
規則３Ｓ）規則１Ｓ，２Ｓに従って、状態Ｘｉ（ｔ）の値が０から１に変化したとき、その変化の原因となった隣接ノードＮｊのノード番号ｊを、水先案内ベクトルＰｉ（ｓ）とする。
なお、ここで（ｔ−Ｗｊｉ）が負の数となる場合の状態値はゼロとする。即ち、ｔ＜Ｗｊｉならば、Ｘｉ（ｔ−Ｗｊｉ）＝０。
ここで、上記規則１Ｓ，２Ｓに従って、全ての状態値Ｘｉ（ｔ）を０に初期化した後、一度１になって活性化した状態値Ｘｉ（ｔ）は１のまま変化しない。
【００６０】
次に、図２２につき、この方式における最適経路設計の手順を説明する。図２２は、最適経路設計の手順を示すフロー図である。ここでは、ノードＮ１において、ノードＮ１を発信源としてノードＮ２からＮ９を宛先とする経路設計を行う場合の例について示す。他のノードにおける経路設計も、同様に行うことができる。
図において、ステップＳＴ１とステップＳＴ２は時刻ｔ＝０の場合の初期設定、ステップＳＴ３からステップＳＴ１０は、全ノードの状態値Ｘｉ（ｔ）が１になるまで繰り返される手順である。初期設定では、まずステップＳＴ１で時刻ｔ＝０とおく。次にステップＳＴ２で、発信ノードＮｓの状態値Ｘｓ（０）＝１、それ以外のノードＮｉについてはＸｉ（０）＝０とし、図１７の状態遷移表ＳＴＣＨのｔ＝０の列に記入する（状態１７０１）。これは上記規則１Ｓに対応する。なお、従来例では初期設定時刻をｔ＝１としているのに対し、この実施の形態ではｔ＝０としているのは、説明の便宜上の問題で、本質的な意味はない。
【００６１】
次に、ステップＳＴ３で、時刻ｔを１だけ増加して、次の更新周期の処理を開始する。
次に、ステップＳＴ４で、発信ノードＮｓの状態値Ｘｓ（１）＝１とし、それ以外のノードＮｉについてはＸｉ（１）＝０と初期化して、図１７の状態遷移表ＳＴＣＨのｔ＝１の列に記入する（状態１７０２）。
次に、ステップＳＴ５で、状態遷移表のＷｊｉ時刻前の状態値Ｘｊ（ｔ−Ｗｊｉ）の値を読み出す。
例えば、ノードＮ２の場合においては、ノードＮｊはノードＮ１であり、ｉ＝２、ｊ＝１、ｔ＝１となり、Ｘｊ（ｔ−Ｗｊｉ）＝Ｘ１（１−Ｗ１２）の値を呼び出す。同様にしてノードＮ４の場合では、ノードＮ１をノードＷｊとし、ｉ＝４、ｊ＝１、ｔ＝１となり、Ｘｊ（ｔ−Ｗｊｉ）＝Ｘ１（１−Ｗ１４）の値を呼び出す。ここで、図１０のネットワークモデル２Ｄ５又は図１６の設計要求対応トポロジーコスト表ＴＰＣＲＥＱに記載されたコストＷｊｉ（図１６はＷｉｊを記載しているが、Ｗｉｊ＝Ｗｊｉである）を参照すると、Ｗ１２は４、Ｗ１４は１である。従って、Ｘ１（１−Ｗ１２）＝Ｘ１（１−４）、Ｘ１（１−Ｗ１４）＝Ｘ１（１−１）となる。
【００６２】
次に、ステップＳＴ６で、読み出した値についてＸｊ（ｔ−Ｗｊｉ）＝１か否か判定する。
前出の例では、ノードＮ２については、Ｘ１（１−Ｗ１２）＝Ｘ１（１−４）＝Ｘ１（−３）であり、（ｔ−Ｗｊｉ）が負の数となるため、Ｘｊ（ｔ−Ｗｊｉ）＝０と判定される。一方、ノードＮ４については、Ｘ１（１−Ｗ１４）＝Ｘ１（１−１）＝Ｘ１（０）となり、Ｘ１（０）＝１であることが分かる。このため、Ｘｊ（ｔ−Ｗｊｉ）＝１と判定される。
Ｘｊ（ｔ−Ｗｊｉ）が１の場合はステップＳＴ７に進み、０の場合はステップＳＴ９に進む。
【００６３】
ステップＳＴ７では、Ｘｊ（ｔ−Ｗｊｉ）＝１であった場合に、Ｘｉ（ｔ）＝１として図１７の状態遷移表ＳＴＣＨに記入する。
即ち、前出の例では、ノードＮ４については、Ｘ１（１−Ｗ１４）＝Ｘ１（１−１）＝Ｘ１（０）＝１であるため、Ｘ４（１）＝１と記入する（状態１７０３）。
一方、ノードＮ２については、ステップＳＴ４において図１７の状態遷移表は初期化されているため、Ｘ２（１）＝０を書き込む必要はなくステップＳＴ９へ進む。
次に、ステップＳＴ８で、Ｘｊ（ｔ−Ｗｊｉ）＝１なるｊを水先案内ベクトルＰｉとし、図２０の水先案内表に記入する。これは上記規則３Ｓに対応する。
前出の例では、Ｘｊ（ｔ−Ｗｊｉ）＝Ｘ１（１−Ｗ１４）＝１であるから、１を水先案内ベクトルＰ４として図２０の水先案内表に記入する。
次に、ステップＳＴ９で、ノードＮｉの全ての隣接ノードｊについて検証済か否かを判定し、全ての隣接ノードｊについて検証を終了するまで、ステップＳＴ５からステップＳＴ９を繰り返す。ここでｊはノードＮｉの隣接ノードＡＳｉの要素である。
次に、ステップＳＴ１０で、全ノードの状態値についてＸｉ（ｔ）＝１か否かの判定を行い、全ノードの状態値Ｘｉ（ｔ）が１になるまで、ステップＳＴ３からステップＳＴ９の更新を繰り返す（状態１７０４〜状態１７０６）。
【００６４】
以上のようにして図１７の状態遷移表ＳＴＣＨに状態値Ｘｉ（ｔ）を記入しながら図２０の水先案内表ＰＰＴを完成させた。次に、実際に発信ノードＮｓから着信ノードＮｄへの要求帯域Ｒの経路を抽出する手順を述べる。図２３はこの手順を示すフロー図である。
まずステップＳＴ２１で、水先案内表ＰＰＴのＰｄ（ｓ）＝ｊ１に注目する。これは求める経路の一個手前のノード番号になる。例えば、ｓ＝１、ｄ＝７の場合は、図２０のＰ７＝５が一個手前のノード番号になる。
次に、ステップＳＴ２２で、水先案内表ＰＰＴのＰｊ１（ｓ）＝ｊ２に注目する。これは求める経路の更に一個手前のノード番号になる。上記ｄ＝７の例では、図２０のＰ５＝４が更に一個手前のノード番号になる。
次に、ステップＳＴ２３で、求めたノード番号が発信源ｓか否かを判定し、ｓに達するまでステップＳＴ２２を繰り返す。上記ｄ＝７の例では、Ｐ４＝１＝ｓとなる。
ゆえに、ノードＮ１からＮ７への経路は１、４、５、７となる。
【００６５】
ノードＮ１からＮ７へパケットを伝送するときに、経由する経路を明示的にパケットに記載する場合もあるが、必ずしもその必要はない。ノードＮ１では、最適経路内の次のノード即ちノードＮ４にパケットを送り出しさえすれば、ノードＮ４では自前でｓ＝４、ｄ＝７として最適経路設計した結果に基いて、ノードＮ５にパケットを送出してくれ、最適経路を通ってノードＮ７に達する。各ノードで別個に自ノードを発信源として最適経路設計をした結果を使用しても、宛先が同じならば、原理的に、最適な経路となる。
【００６６】
なお、上記の説明では、有効帯域とコストの対応の例として図６の対応表ＢＷＣＳＴを使用したが、この分類や対応を変化させてもよい。また、遅延と遅延コードの対応表として図７のコード表ＤＬＣＤを用いたが、この分類や対応を変化させてもよい。
【００６７】
なお、上記の説明では、リンク１２を特徴付ける第一の通信特性として有効帯域を用いてコストに組み込んだが、有効帯域の変わりに、距離、伝送品質の他の特性をコストに組み込んでもよい。その場合、コストは、その値の大きさに比例して、当該リンクの選択を回避したい度合いが高まるように、図６の対応表ＢＷＣＳＴに替わる対応表を設定する。
【００６８】
なお、上記の説明では、リンク１２の第二の通信特性として遅延に注目したが、遅延の変わりに、距離、伝送品質の他の品質特性を使用してもよい。また、第二の通信特性として複数の品質特性を同時に考慮してもよい。それら場合は、品質の段階に応じて品質コードが求められるように、図７のコード表ＤＬＣＤに替わるコード表を設定する。
【００６９】
なお、上記の説明では、処理の段階を明確に示すために、図１２および図１３に示すように、各段階の処理を分割したが、これらの複数の段階をまとめて処理をおこなってもよい。
【００７０】
なお、上記の説明では、処理の段階を明確に示すために、図１２および図１３に示すように、各段階の処理を分割し、またそれぞれの段階に応じて別個にトポロジー表を設けたが、これらの複数の段階をまとめて処理をおこなってもよい。
【００７１】
また、本実施の形態では、有線通信ネットワークについて説明を行ってきたが、本発明は無線通信ネットワークに対しても適用することができる。
【００７２】
実施の形態２．
実施の形態１に示した最適経路設計法では、図１３に示すように、許容コストを超えるリンクを削除した設計要求対応ネットワークモデル２ＲＥＱ、およびこれを特徴付ける設計要求対応トポロジーコスト表ＴＰＣＲＥＱ（図１６）を求めてから、経路設計を行っていた。しかし、図２５に示すように、この段階を省略して経路設計を行ってもよい（第１の例）。
有効帯域の情報は、図６の対応表ＢＷＣＳＴによって既にリンクコストに組み込まれているので、経路設計の対象となるネットワークモデル２を許容コスト以下のリンクに制限しなくても、許容コストを超えるリンクを選択する度合いは小さくなる。
許容コストを超えるリンクを削除する段階を省略する目的のために、この度合いが十分小さくなるように対応表ＢＷＣＳＴを設定することもできる。
【００７３】
許容コストを超えるリンクを削除する段階を省略することによって、図１３および図２５に示す、最適経路設計によって水先案内平面ＰＰを求める段階の処理を、経路設計要求が発生する前に、あらかじめ行っておくこともできる（第２の例）。この第２の例を実現するために、図２４に示すように、通信経路設定装置１００に通信経路選択部１１１を設ける。
通信経路選択部１１１による処理を図２６および図２７に示す。図１２の処理の後、図２６に示すように、遅延コードに対応した複数のネットワークモデル（複数のトポロジー遅延別コスト表）の各々について水先案内平面ＰＰＤ４、ＰＰＤ５をあらかじめ求めておく。経路設計要求ＲＥＱ１の発生時には、図２７に示すように、これらの水先案内平面ＰＰＤ４、ＰＰＤ５の中から、通信経路選択部１１１は、要求遅延コードに対応する面を選択する。この方法では、経路設計要求ＲＥＱ１が発生後の経路設計時間が短縮できる。図２８に水先案内平面ＰＰＤ４の全体を示す。
【００７４】
実施の形態３．
この実施の形態３では、実施の形態１に示した最適経路設計法を、ＩＥＴＦのＲＦＣ２３８３番であるＯＳＰＦ  Ｖｅｒｓｉｏｎ  ２ルーチングプロトコル（以下適宜、ＯＳＰＦと略記する）に搭載する際の一方法について述べる。ＯＳＰＦでは、通信ネットワークのトポロジー情報を各ノードに通知するためにＬＳＡ（Ｌｉｎｋ  Ｓｔａｔｅ  Ａｄｖｅｒｔｉｓｅｍｅｎｔｓ；リンク状態広告）を用いる。
従来例２の図３７に示すＯＳＰＦのルータ用ＬＳＡでは、各リンクを特徴付けるメトリックあるいはコストを記載する部分として、第８行の第１６から３１ビットの１６ビットしか割り当てられていなかった。このため、リンクの帯域等広範囲の値をとる属性値を記載することが困難であった。このため、本実施の形態では、従来例３の図３８に示すＯｐａｑｕｅ型のＬＳＡを使用する。Ｏｐａｑｕｅ  ＬＳＡは、ＯＳＰＦの一つの拡張方法で、適用法に応じてＬＳＡを拡張することができる。
Ｏｐａｑｕｅ型ＬＳＡを用いることは、ＯＳＰＦのハローパケットと呼ばれるパケットのオプション部で示される。図２９にＯｐａｑｕｅ型のハローパケットのオプション部を示す。図２９に示すように、第１ビットにＯビットがセットされている場合は、Ｏｐａｑｕｅ型であることを示す。
【００７５】
図２に示す通知パケット作成部１０９が本実施の形態に係るＬＳＡを作成する。また、図３０に、この実施の形態におけるＬＳＡの様式を示す。図において、第０行から第４行は、ＬＳＡに共通のヘッダである。第１行の第２４から３１ビットはＯｐａｑｕｅ  ＬＳＡのタイプを示す場所で、Ｏｐａｑｕｅ  ＬＳＡにおいては、ＬＳＡを広告する範囲を示す。１０はエリアローカルにＬＡＳを広告することを示す。第１行はＩＥＴＦの規定に沿って拡張性のために設けられた部分であり、現在は使用していない。第５行から第７行は、図３７に示すＯＳＰＦのルータ用ＬＳＡと同様の機能を持つ。即ち、第５行の第１６から３１ビットの＃ｌｉｎｋｓは、当該ルータに接続されているリンクの数を示す。第６行から第１０行は、そのうちの一つのリンクに関する情報を示す。第６行のＬｉｎｋ  ＩＤはリンクの識別子を示す。第７行のＬｉｎｋ  Ｄａｔａは、リンクのタイプに応じた特性を示す。リンクのタイプは、第８行の第１から７ビットのＴｙｐｅで示す。
【００７６】
この実施の形態におけるＬＳＡの特徴的な部分は、第８行の第７ビット以降と、第９行にある。第８行の第８から１５ビットの＃  ＱＯＳでは、サービス品質（Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ、以下適宜、ＱｏＳと略記）の種類の数（追加分）を示している。実施の形態１の例では、ＱｏＳとして代表的な遅延のみを考慮していた。ゆえに、実施の形態１の場合には、＃  ＱｏＳは０となる。第８行の第１６から２３ビットのＱＯＳ２は、遅延以外のＱｏＳを考慮する場合に使用する。第８行の第２４から３１ビットのｄｅｌａｙは、第一番めのＱｏＳである遅延を記載する。これは８ビットであるが、遅延を二進法で表現するのではなく、実施の形態１の図７の表ＤＬＣＤの例に示すように、対応表でコード化した遅延により、対応するビットをセットすることにより示す。即ち、図７の遅延コード表には８つの値の遅延コードが表されており、この８つの値のそれぞれの値が８ビット内の各ビットに割り当てられている。例えば遅延コードが４の場合には、遅延バイトのＬＳＢ（Ｌｅａｓｔ  Ｓｉｇｎｉｆｉｃａｎｔ  Ｂｉｔ；右端のビット）から４ビット目のビットのみをセットする。遅延を二進数ではなく、対応表でコード化して、遅延コードと遅延バイトの各ビットを一対一に対応させることにより、単純なハードウェアにより、当該リンクの遅延コードを識別することが可能となる。
【００７７】
図３０の第９行のａｖａｉｌａｂｌｅ  ｂａｎｄｗｉｄｔｈでは、有効帯域を３２ビットの符号無し整数で記載する。有効帯域の単位はキロビット／秒とすると、２の３２乗＝４，２９４，９６７，２９６であるので、４テラビット／秒まで表現が可能となり、実用上は十分と思われる。しかし、適宜これ以外の単位を用いてもよい。
図３０の第１０行以降は、次のリンクについて、第６行から第９行と同様の記述が繰り返される。
比較例として、従来例１に示したＱＯＳＰＦでは、リンクを特徴付けるメトリックとして、従来例２のＯＳＰＦを踏襲した１６ビットを用いており、技巧的なコード化を行っている。
【００７８】
次に、通知パケット作成部１０９が通信ネットワークのトポロジー情報を更新する頻度、即ちＬＳＡを送付する頻度について説明する。ＬＳＡ送付のタイミングは、従来例２のＯＳＰＦで規定されているパラメータに則る。特に、代表的なパラメータは、次の２定数である。
ＬＳＲｅｆｒｅｓｈＴｉｍｅ：  あるＬＳＡを再発生する最大間隔。３０分に固定。
ＭａｘＡｇｅ：  １個のＬＳＡの寿命。１時間に固定。
この他に、この実施の形態では、当該ルータ周辺のエリアに適用されるエリア変数として、下記の可変パラメータを定義する。
ＬＳＵｐｄａｔｅＰｅｒｉｏｄ：  あるＬＳＡを更新する最大間隔。
ＬＳＵｐｄａｔｅＰｅｒｉｏｄは、原理上、ＬＳＲｅｆｒｅｓｈＴｉｍｅ（３０分）以下である必要がある。また、ＬＳＲｅｆｒｅｓｈＴｉｍｅによる更新と同期がとれるように、３０分の約数に設定する。参考値は６分とする。
ＬＳＵｐｄａｔｅＰｅｒｉｏｄは、きめ細やかなトポロジー情報の更新のために、規定のＬＳＲｅｆｒｅｓｈＴｉｍｅ（３０分）以下の時間であっても、エリアの規模や変化の状況に応じて、その設定値を変化させることができる。
【００７９】
従来例１に示したＱＯＳＰＦでは、ＬＳＡの更新は、従来例２のＯＳＰＦと同じく３０分に固定されているが、本実施の形態に係る通知パケット作成部１０９は、ＬＳＵｐｄａｔｅＰｅｒｉｏｄにおいて、３０分以下の任意の時間を設定し、設定した３０分以下の任意の時間ごとにＬＳＡを更新することができる。
【００８０】
実施の形態４．
本実施の形態における最適経路設計は、特開平０９−１１６５７３号および特開平１１−５５３１２号による最適経路設計方法を用いて、無線インターネットにおいて最適経路設計を行う方式である。本実施の形態における最適経路設計は、特開平０９−１１６５７３号（特願平８−４４８６５号）の実施の形態７で示した最適経路設計法の応用で、発信ノードｓを基準にして経路設計を行う実施の形態１０に示す方法に基くものである。ハードウェア論理回路による実現は、実施の形態１４に示す方法に基く。
【００８１】
ＩＰ（Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）網は歴史的にはＬＡＮを中心に発展してきたが、携帯電話の急速な増加にともない、ワイヤレスメディアでも使用されるようになってきた。携帯端末でのインターネットへのアクセスは、既に日常的に行われている。ＩＰ網の利便性を享受した人々は、更にＩＰ網を拡大して行こうと考えている。
インターネットの専門家からは、あらゆるものにＩＰアドレスを与えて、ＩＰ網で接続してしまおうという構想も出てきている。この場合、ＩＰ接続のメディアは、必然的に無線と有線を併用したものとなる。無線ＩＰの利用法としては、無線ＬＡＮのように既に実用化されているものもあるが、センサーネットワークのように将来的なものもある。
センサーネットワークでは、オフィス等の一定の空間にセンサーをくまなく配置し、これらを無線により接続して、状況変化の感知情報等を送信する。
無線ＬＡＮにしてもセンサーネットワークにしても、一定の空間をカバーするためには、センサーあるいは無線装置を、無線の強度に応じた密度で、くまなく配置する必要がある。これらの装置をＩＰ網で接続するのであるが、そのノード数は膨大なものとなる。また、これらのノードのうち実際に使用されるノードを予測するのは困難なため、接続経路は必要に応じて動的に設計する必要がある。このような場合のノード間の最適経路の設定手法、ノード数の試算例、およびこの実施の形態の方式と従来例１の方式と最適経路設計時間との比較を後述する。
【００８２】
図４０はこの発明の実施の形態４でルーチングを行う無線インターネットの例である。
図において、ＷＮは無線インターネット網、ＷＴは無線インターネット端末、ＷＬは直接無線パケットの送受信が可能である無線回線である。
図４１はネットワーク構成を模式的に示す図である。図において、２は経路設計の対象となるネットワークモデルであり、図４０の無線インターネット網ＷＮに対応する。
１１は無線通信信号の発着中継を行うノードＮｉ（ｉ＝１，２，・・・，９）であり、図１の無線インターネット端末ＷＴに対応する。なお、本実施の形態においては、ノードＮｉを無線ノードと呼ぶ。
１２はノードＮｉとＮｊ間の接続回線であるリンクであり、図４０の無線経路ＷＬに対応する。なお、本実施の形態においては、リンクを無線リンクと呼ぶ。各無線ノード１１の円内に記載されている番号は各々の無線ノードの番号で、無線ノードＮｉの添字ｉがこれに対応する。ここで無線ノードＮｉと無線ノードＮｊ間の無線リンクには方向性があるものとし、無線ノードＮｉからＮｊに向かう無線リンクを無線リンクＬｉｊと記す。一般には無線リンクＬｉｊと無線リンクＬｊｉは異なるが、図４１の例では、便宜上全ての無線リンク１２は両方向性とする。無線リンク１２のそれぞれのコストが、無線リンク上に記してある。無線リンクＬｉｊのコストＷｉｊは、無線リンクの受信強度に依存して決定される。
【００８３】
図４０あるいは図４１において図示していないが、各々の無線インターネット端末ＷＴあるいは各々の無線ノード１１には本実施の形態に係る通信経路設定装置１００が設けられている。
図４２は、通信経路設定装置１００の機能ブロック図である。
図４２において、１０２は、無線通信ネットワーク全体のトポロジー情報を記録しているトポロジー情報記録部である。トポロジー情報は、実施の形態１において図８で示したトポロジーコスト表ＴＰＣ等から構成される。１０８は、無線ノード１１間の最適経路設計を行う通信経路設定部である。１１０は、無線通信ネットワークのトポロジー情報を他の無線ノードに通知するための通知パケットを他の無線ノード１１に向けて送信する通知パケット送信部である。
図４１に示すネットワークモデルのトポロジー情報は、通知パケットに載せて、通知パケット送信部１１０より、他の全無線ノードに向けて一定時間毎に送信される。通知パケット送信のタイミングは、ネットワークの規模や混雑状況により決定するが、数分から数時間のオーダーとする。
【００８４】
図４３は、通信経路設定部１０８の構成を示す図である。
図において、１０８０は、最適経路設定処理において、始点ノードである発信無線ノード又は終点ノードである着信無線ノードを指定するノード指定部である。
１０８１は、状態遷移表ＳＴＣＨの状態数を初期化する初期化部である。
１０８２は、状態遷移表ＳＴＣＨの状態数を変化させていく状態数変化部である。
１０８３は、状態数変化部１０８２が状態数を変化させる際に、一定の単位時間前の他の無線ノードの状態数に基づいて特定の無線ノードの状態数を算出する状態数算出部である。
１０８４は、各無線ノードの状態数の変化を検出し、状態数に変化があった場合に、その変化を誘引した隣接無線ノードを検出する検出部である。
１０８５は、検出部１０８４により検出された隣接無線ノードを、最適経路を構成する無線ノードとして選定する選定部である。
なお、これら１０２、１０８、１１０及び１０８１〜１０８５の各機能をコンピュータに実行させるためのプログラムとすることが可能であり、また、これら１０２、１０８、１１０及び１０８１〜１０８５の各機能のコンピュータプログラムをコンピュータ読み取り可能な記録媒体に記録することも可能である。
【００８５】
実施の形態１では、リンクのコストとして有効帯域や遅延を用いたが、本実施の形態においては、前述したように無線リンクの無線強度（無線回線の受信強度）をコストとして用いることができる。受信強度の変わりに、距離、伝送品質の他の特性をコストに組み込んでもよい。その場合、コストは、その値の大きさに比例して、当該リンクの選択を回避したい度合いが高まるように設定する。
【００８６】
また、本実施の形態における最適経路設計の手順は、実施の形態１に示したものと同様であり、通信経路設定部１０８が図２２及び図２３に示すフローに従って最適経路設計を行う。
【００８７】
具体的には、初期設定で、ノード指定部１０８０が発信無線ノード（又は着信無線ノード）を指定し、初期化部１０８１が時刻ｔ＝１において、発信無線ノードＮｓの状態値Ｘｓ（０）＝１、それ以外の無線ノードＮｉについてはＸｉ（０）＝０とし、図１７に示すように状態遷移表ＳＴＣＨのｔ＝０の列に記入する（ステップＳＴ１、ステップＳＴ２）。
次にステップＳＴ３で、時刻ｔを１だけ増加して、次の更新周期の処理を開始する。
次にステップＳＴ４で、状態数変化部１０８３が発信無線ノードＮｓの状態値Ｘｓ（０）＝１とし、それ以外の無線ノードＮｉについてはＸｉ（０）＝０と初期化して、状態遷移表ＳＴＣＨに記入する。
次にステップＳＴ５で、状態数算出部１０８３が、状態遷移表のＷｊｉ時刻前の状態値Ｘｊ（ｔ−Ｗｊｉ）の値を読み出す。
次にステップＳＴ６で、状態数変化部１０８２が、読み出した値についてＸｊ（ｔ−Ｗｊｉ）＝１か否か判定する。これが１の場合はステップＳＴ７に進み、０の場合はステップＳＴ９に進む。ステップＳＴ７では、Ｘｉ（ｔ）＝１とする。
次にステップＳＴ８で、検出部１０８４が、Ｘｊ（ｔ−Ｗｊｉ）＝１なるｊを水先案内ベクトルＰｉとし、水先案内表に記入する。
次にステップＳＴ９で、状態数変化部１０８２が、無線ノードＮｉの全ての隣接無線ノードについて検証済か否かを判定し、全ての隣接無線ノードについて検証を終了するまで、ステップＳＴ５からステップＳＴ９を繰り返す。
次にステップＳＴ１０で、全無線ノードの状態値についてＸｉ（ｔ）＝１か否かの判定を行い、全無線ノードの状態値Ｘｉ（ｔ）が１になるまで、ステップＳＴ３からステップＳＴ９の更新を繰り返す。
【００８８】
以上のようにして状態遷移表ＳＴＣＨに状態値Ｘｉ（ｔ）を記入しながら図２０の水先案内表ＰＰＴを完成させた後、選定部１０８５が、図２３のフローに従って無線ノードＮｓから無線ノードＮｄへの最適経路を抽出する。
まずステップＳＴ２１で、水先案内表ＰＰＴのＰｄ（ｓ）＝ｊ１に注目する。これば求める経路の一個手前の無線ノード番号になる。例えば、ｓ＝１、ｄ＝７の場合は、図２０のＰ７＝５が一個手前の無線ノード番号になる。
次にステップＳＴ２２で、水先案内表ＰＰＴのＰｊ１（ｓ）＝ｊ２に注目する。これば求める経路の更に一個手前の無線ノード番号になる。上記ｄ＝７の例では、図２０のＰ５＝４が更に一個手前の無線ノード番号になる。
次にステップＳＴ２３で、求めた無線ノード番号が発信源ｓか否かを判定し、ｓに達するまでステップＳＴ２２を繰り返す。上記ｄ＝７の例では、Ｐ４＝１＝ｓとなる。
ゆえに、無線ノードＮ１からＮ７への経路は１、４、５、７となる。
【００８９】
なお、上記では、本発明に係る通信経路設定装置について説明を行ってきたが、同様の処理手順により本発明に係る通信経路設定方法も実現することができる。
【００９０】
次に、この実施の形態における最適経路設計法を、ハードウェア論理回路を用いて実現する方法を示す。この実施の形態における最適経路設計法は、状態数Ｘｉ（ｔ）が０と１の２値のみをとるので、ハードウェア論理回路で容易に実現可能である。
【００９１】
図４４は、図４１に示すネットワークモデル２において、実施の形態１において説明した規則１Ｓ、２Ｓ、３Ｓをハードウェア論理回路で実現する例である。
図４４において、ＤＦＦはＤ−フリップフロップを示し、基本クロックＣＬＫに同期して、入力データを出力する。これはＬＳ７４等の素子で実現できる。また、ＳＲＦＦはＳＲ−フリップフロップを示し、ＬＳ１１２等の素子で実現できる．その他のＡＮＤゲート、ＯＲゲート、ＸＯＲゲートについても、一般的な論理積、論理和、排他的論理和の素子で実現できる。図４４において、Ｘ１、Ｘ２、．．．Ｘ９は、の無線ノードＮｉの状態値Ｘｉを示す。
図４４において、ＫＡＩＲＯ２（Ｘ２）は、規則２Ｓに従って、状態値Ｘ２を更新する回路であり、ＫＡＩＲＯ３（Ｘ２）は、規則３Ｓに従って、水先案内行列ＰＭｊ２を生成する回路である。水先案内行列ＰＭｊｉとは、水先案内平面ＰＰを行列形式で表現したものである。
ＫＡＩＲＯ１（Ｘ１）は規則１Ｓと２Ｓに従って、発信元無線ノードの状態値Ｘ１（ｔ）を１に固定する回路である。但しこの場合の発信元はｓ＝１とする。
【００９２】
次に図４４のＫＡＩＲＯ２（Ｘ２）が規則２Ｓを実現しているしくみを説明する。図４１のネットワークモデル２に示すように、無線ノードＮ２の隣接無線ノード（とそのコスト）は、１（４）、３（１）、４（１）、５（１）、６（２）となっている。一方、規則２Ｓは、コストＷｊｉ時刻前の状態数Ｘｉ（ｔ−Ｗｊｉ）の値が１である隣接無線ノードＮｊが存在する場合には、状態値Ｘｉ（ｔ）は１とし、それ以外の場合には０とする、というものである。
故に無線ノードＮ２の場合、Ｘ１（ｔ−４）、Ｘ３（ｔ−１）、Ｘ４（ｔ−１）、Ｘ５（ｔ−１）、Ｘ６（ｔ−２）のいずれかが１であれば、Ｘｉ（ｔ）は１となるということである。これは、図４４のＫＡＩＲＯ２で実現されている。即ち、４時刻前のＸ１の値は、Ｘ１の値をフリップフロップＤＦＦで４回遅延されることによって得られ、１時刻前のＸ３、Ｘ４、Ｘ５の値は、各々の値をフリップフロップＤＦＦで１回遅延させることによって得られ、２時刻前のＸ６の値は、Ｘ６の値をフリップフロップＤＦＦで２回遅延されることによって得られる。これらの値のいずれかが１であった場合は、ＯＲの出力が１となり、状態数Ｘ２の値を保持するＤＦＦがセットされ、状態数Ｘ２の値が１となる。
【００９３】
次に図４４のＫＡＩＲＯ３（Ｘ２）が規則３Ｓを実現しているしくみを説明する。規則３Ｓは、状態数Ｘｉ（ｔ）の値が０から１に変化したとき、その変化の原因となった隣接無線ノードＮｊの無線ノード番号ｊの、水先案内行列ＰＭｊｉ＝１とするというものである。図４４のＫＡＩＲＯ３（Ｘ２）では、ＸＯＲで状態数Ｘ２の変化を検知し、信号ＣＨＡＮＧＥ２で示す。これにより、１時刻前に状態数が１であった隣接無線ノードを調べ、その隣接無線ノードｊの水先案内行列ＰＭｊｉを１にセットする。
【００９４】
図４４のＫＡＩＲＯ２では、無線ノードＮｉと無線ノードＮｊの隣接関係は、状態数Ｘ１からＸ９の値を保持するＤＦＦの出力線と固定的に結線されており、コストＷｊｉは遅延用フリップフロップＤＦＦの個数で、固定的に決められている。しかし図４５に示すボリューム回路ＶＯＬＵＭＥ等を用いることにより、ＫＡＩＲＯ２に汎用性を持たせることが可能となる。
図４５のボリューム回路では、シフトレジスタＳＦＴＲＧＴを用いて、図４４の遅延用ＤＦＦによる遅延を代替している。遅延する時間は、ボリューム信号ＶＬｊｉにより指定する。シフトレジスタＳＦＴＲＧＴは、ＬＣ１６４等の素子で実現できる。図４４のＫＡＩＲＯ２（Ｘ２）の場合、Ｘ１は４段遅延されてＸ１Ｄとなるので、図４５のボリューム回路ＶＯＬＵＭＥを用いる場合は、ボリューム信号ＶＬ１２の１、２、３、をｌｏｗ、４をｈｉｇｈにして、Ｘ１を４段遅延した信号がＸ１Ｄに出力されるようにする。
ここでボリューム信号ＶＬｊｉは、図８のトポロジーコスト表Ｗｊｉに等しい。図４５の例では、ボリューム信号ＶＬｊｉのレベルは４となっているが、これはほかの数でも良い。
同様にＫＡＩＲＯ３においても、ボリューム信号ＶＬｊｉを用いることにより、柔軟な配線で水先案内行列の要素ＰＭｊｉを求めることができる。図４４のＫＡＩＲＯ３（Ｘ２）の場合、ＳＲＦＦに接続されている隣接無線ノードの状態数Ｘ１、Ｘ３、Ｘ４、Ｘ５、Ｘ６は固定であるが、図４５ではボリューム信号ＶＬｊｉの１から４までのどれかがｈｉｇｈの場合は、状態数ＸｊをＳＲＦＦに接続してＰＭｊｉをセットするようになっている。
図４５に示すボリューム回路は、図４４の状態値Ｘ１からＸ９の値を保持するＤＦＦの出力線と接続され、図８に示す表から得られるコストをボリューム信号として入力することにより、遅延された状態値と水先案内行列を出力する。このように、ボリューム回路という汎用的なハードウェア回路に対してコスト（無線強度）に相当するボリューム信号をそれぞれ入力することにより、無線ノードの隣接関係およびコスト（無線強度）という無線ノード間の無線リンク属性を、共通のハードウェア回路を用いて実現することができる。
【００９５】
次に、無線インターネットのノード数の試算例を示し、この実施の形態の方式と従来例１の方式との最適経路設計時間を比較する。
無線インターネットのノード数の試算例を図４６に示す。東京都心部で１９９９年までに計画されて２００３年に竣工予定の大規模オフィスビル一件当たりの平均面積は、９６０００平方メートルとなっている（事務に可使用部のみの面積）。これは１９９４年の２．５倍で、「近・新・大」の条件の他、ＩＴ対応と耐震機能が無いオフィスビルは、淘汰されていくと予想されている。文献（森ビル（株）「東京２３区の大規模オフィスビル供給量調査」、ｈｔｔｐ：／／ｗｗｗ．ｍｏｒｉ．ｃｏ．ｊｐ／、１９９９年１２月）参照。
この平均的な９６０００平方メートルの事務所面を、正方形のアレイに区切り、そのアレイ一個毎に無線装置を配置し、ＩＰ網で接続する場合を考える。図４７は、アレイの一辺の長さと、アレイの個数との関係を示したものである。
アレイの一辺の長さは、文献（門洋一、大野雄一郎、行田弘一、大平孝、「各端末において受信電力に基づき自立的に中継優先度を決定するルーティング方式」２０００年電子情報通信学会総合大会Ｂ−５−１６４、２０００年９月）の２ｍ、文献（山崎浩輔、中川智尋、森川博之、青山友紀、「センサーネットワークにおける多対一経路制御手法」２０００年電子情報通信学会総合大会Ｂ−５−１８７、２０００年９月）の５．４８ｍ、Ｂｌｕｅｔｏｏｔｈ（ｈｔｔｐ：／／ｗｗｗ．ｂｌｕｅｔｏｏｔｈ．ｃｏｍ／）Ｃｌａｓｓ３の１４．１ｍ（最大伝送距離１０ｍ）を参考にして、１２ｍ以下の場合を示す。ノード数はアレイの個数と同等になる。図４６におけるアレイ数すなわちノード数は、１０の３乗から１０の４乗のオーダーとなっている。
【００９６】
ネットワークモデルとして図４７に示すメッシュ型トポロジーを用いて、経路計算時間を評価した。メッシュ型トポロジーでは、一辺のリンク数を変数とする。図４８は一辺のリンク数が２、ノード数が９の例である。ノード数は、（一辺のリンク数＋１）の２乗となる。
メッシュの一辺のリンク数が１から６３、すなわち、ノード数が４から４０９６の場合について、最適経路一面の計算時間を求めたものを、図４８に示す。図のノード１を発信元として、他の全ノードまでの最適経路を求めるのに要する時間を評価した。図では、リンクコストの段階数が４，８，１６，６４の場合について示してある。
本発明に係る方式をハードウェアディジタル論理回路で実現した場合に、
最適経路一面を求めるのに要する時間は、基準クロックごとに状態値Ｘｉ（ｔ）と荷重Ｗｊｉの更新を行うとすると、原理的に
（リンクコストの段階数  ×  全ノード数  ×  基準クロック時間）
を超えない。ここで、基準クロックは２００ＭＨｚ（５ｎｓ）とする。
【００９７】
図４８には、従来例１（ＱＯＳＰＦ）のアルゴリズムで、ノード１を発信源としたルーチングテーブル一式を求めるのに要する時間も示してある。ノード数４００以下の実線部はパソコンでシミュレーション時間を実測であるが、破線部は、実線部のシミュレーション結果を延長した参考値である。この実施の形態の方式では、リンクコストの段階数に比例して計算時間は増加するが、従来例１（ＱＯＳＰＦ）の場合に比べて、４けたから５けた小さくなっている。ノード数が１０の３乗のオーダーになると、本実施の形態に係る方式の計算時間は１０のマイナス４乗から１０のマイナス３乗で、実時間制御に耐えるものであるが、従来例１（ＱＯＳＰＦ）の場合は数十秒となり、実時間制御は不可能となる。また、本実施の形態に係る方式はワンチップＬＳＩ化が容易であり、価格は数千円程度にできるため、アレイ毎に配置される無線装置に実装することも容易であるが、パソコンやワークステーションでの計算を前提としている従来例１の方式（ＱＯＳＰＦ）は、小型化、低価格化の面でアレイ毎装置への実装は非常に困難である。
【００９８】
ここで、これまで説明してきた本発明の特徴をまとめると以下のようになる。
ネットワークの複数個のノード間を接続するリンクの接続情報およびリンクの特性を示す情報を用いて最適経路を設計して通信の経路を設定するルーチング方式において、下記の処理を備えたことを特徴とする。
有効帯域等のリンクの特性を当該リンクのコストに対応付ける処理、
遅延等のリンクの品質を表す特性を品質コードに対応付ける処理、
品質コード別にネットワークモデルを構成する処理、
経路設計要求発生時に、許容コスト以下のリンクによるネットワークモデルを作成する処理、
ネットワークモデルの発信ノードから他の全ノード宛に、経路内のリンクのコストを最小にするように最適経路群を設計する処理、
設計した最適経路群から特定の宛先ノードに向けた経路を抽出する処理。
【００９９】
上記の最適経路群を設計する処理において、下記の処理を備えたことを特徴とする。
経路設計対象ネットワーク内のノードに対し、ノードの接続関係とノード間のリンクの属性を記憶する処理、
経路の発信ノードを指定して、各ノードの状態値を初期化する処理、
自ノードと接続するノードの状態値および接続リンクの属性に基づいて、経時的に状態値を更新する処理、
状態値の経時的変化を観察し、変化を誘引した接続ノードを検出する処理。
【０１００】
上記のルーチング方式において、
経路設計要求発生時に、許容コスト以下のリンクによるネットワークモデルを作成する処理を行わずに、最適経路群を設計することを特徴とする。
【０１０１】
上記のルーチング方式において、
品質コード別にネットワークモデルを構成する処理に続いて、各ネットワークモデルを対象に、あらかじめ最適経路群を設計しておき、
経路設計要求発生時に、要求する品質コードに応じた最適経路群を選択することを特徴とする。
【０１０２】
ネットワークのノード間の接続情報およびリンクの特性を示すトポロジー情報をパケットに搭載してネットワーク内のノードに通知する方法において、下記の処理を備えたことを特徴とする。
有効帯域等のリンクの特性を３２ビットの整数で表現する処理、
遅延等のリンクの品質を表す特性を、品質コード毎に１ビットを割り当てて表現する処理、
トポロジー情報を搭載したパケットの送出間隔を、独自のパラメータを定義して制御する処理。
【０１０３】
オフィス等の一定の空間内のあらゆる場所において有効な無線強度が得られるように、一定の空間内に多数の無線端末装置をくまなく配置し、それらにＩＰアドレスを付与して無線回線で接続した無線ネットワーク内の、各無線端末装置に装備し、無線端末装置間の経路設計を行う通信経路設計装置において、
無線端末をノード、直接無線パケットの送受信が可能である無線回線をリンク、無線強度等の無線回線の属性をリンクのコストとし、これらのトポロジー情報を保持するトポロジー情報記録部と、
トポロジー情報をパケットに搭載して一定時間毎に他のノードに送信する通知パケット送信部と、
トポロジー情報に基き無線端末装置間の通信経路を設計するにあたり、ネットワーク全体を模擬したネットワークモデルを作成し、このネットワークモデル内でコストを最小にする最適経路設計を行う通信経路設定部を備えたことを特徴とする。
【０１０４】
前記通信経路設定部は、更に、
ネットワークモデル内の各ノードに、時刻に依存して変化する二値の状態値を割り当て、各状態値を二値のうちの第一の値に初期化するステップ、
発信ノードである自ノードに対応するノードのみを二値のうちの第二の値とし、これを保持するステップ、
発信ノード以外のノードでは、次の規則に従って状態値を更新するステップ、
当該ノードと隣接ノードとの間の、リンクのコストだけ前の時刻の隣接ノードの状態値が、第二の値である隣接ノードが存在する場合には、当該ノードの状態値は、第二の値に更新され、それ以外の場合は、第一の値のままとするステップ、状態値が第一の値から第二の値に変化したとき、その原因となった隣接ノードを記憶しておき、この記憶した隣接ノードを、発信ノードから当該ノードへの最適経路の、当該ノードの前のノードとするステップから構成されることを特徴とする。
【０１０５】
前記通信経路設定部は、前記通信経路設定部の各処理の、状態値の第一の値と第二の値を電位の高低に対応付け、リンクコストの数だけ遅延させた隣接ノードの状態値の論理和をとることにより、当該ノードの状態値を更新し、当該ノードの値が変化した場合は、その原因となった隣接ノードを排他的論理和素子により検出して、最適経路内の当該ノードの前のノードを検出して記憶する最適経路設計回路から構成されることを特徴とする。
【０１０６】
【発明の効果】
この発明によれば、複数の通信特性レベル値を考慮して経路設計を行うことができるので、各経路の状況を正確に把握して最適な経路設計を行うことができ、通信サービスの品質の向上が図れるという効果がある。
【０１０７】
また、この発明によれば、経路設計要求に含まれる通信特性に対する要求を考慮して経路設計を行うことができるので、経路設計要求に則した最適な経路設計を行うことができ、通信サービスの品質の向上が図れるという効果がある。
【０１０８】
また、この発明によれば、要求第一通信特性レベル値に合致しない第一通信特性レベル値を無効とする処理を省略しても適切な経路設計が可能であるため、経路設計要求の発生後の処理時間を短縮することができるという効果がある。
【０１０９】
更に、この発明によれば、複数の分類第一通信特性リンク情報の各々について経路設計を予め行っておくことが可能なので、経路設計要求の発生後の処理時間を短縮することができるという効果がある。
【０１１０】
また、本発明によれば、通知パケットにおいて、第一の通信特性レベル値を少なくとも３２ビット以上の二進数で表すことができるため、リンクの帯域等の広範囲の値をとる属性値も記載できるという効果がある。更に、第二の通信特性レベル値を対応する所定ビットをセットすることで表すことができるため、単純なハードウェアにより、リンクの特性レベル値を識別することができるという効果がある。
【０１１１】
また、本発明によれば、通知パケットの送信間隔について、３０分以下の任意の時間を設定することができるため、きめ細やかなトポロジー情報の更新を実現できるという効果がある。
【０１１２】
また、本発明によれば、センサーネットワーク等の無線通信ネットワークにおける最適経路設計処理の高速化を図ることができる。
【０１１３】
また、本発明によれば、無線通信ネットワークの最適経路設計処理をハードウェア機器により実現することができ、このため装置の小型化、低価格化を図ることができる。
【図面の簡単な説明】
【図１】  この発明の実施の形態１の通信ネットワーク図である。
【図２】  この発明の実施の形態１の通信経路設定装置の機能ブロック図である。
【図３】  この発明の実施の形態１のリンクと遅延の対応表である。
【図４】  この発明の実施の形態１のトポロジー帯域表である。
【図５】  この発明の実施の形態１のトポロジー遅延表である。
【図６】  この発明の実施の形態１の有効帯域とコストの対応表である。
【図７】  この発明の実施の形態１の遅延と遅延コードの対応表である。
【図８】  この発明の実施の形態１のトポロジーコスト表である。
【図９】  この発明の実施の形態１のトポロジー遅延コード表である。
【図１０】  この発明の実施の形態１のネットワークモデルを示す図である。
【図１１】  この発明の実施の形態１のネットワークモデルを示す図（遅延コード４以下）である。
【図１２】  この発明の実施の形態１における最適経路設計の流れを示す図（個別の経路設計の要求に依存しない処理）である。
【図１３】  この発明の実施の形態１における最適経路設計の流れを示す図（個別の経路設計の要求に依存する処理）である。
【図１４】  この発明の実施の形態１のトポロジー遅延別コスト表（遅延コード５以下）である。
【図１５】  この発明の実施の形態１のトポロジー遅延別コスト表（遅延コード４以下）である。
【図１６】  この発明の実施の形態１の設計要求対応トポロジーコスト表である。
【図１７】  この発明の実施の形態１の状態遷移表である。
【図１８】  この発明の実施の形態１の状態遷移表である。
【図１９】  この発明の実施の形態１の水先案内平面（遅延コード５以下のリンクによる）である。
【図２０】  この発明の実施の形態１の水先案内表（遅延コード５以下のリンクによる）である。
【図２１】  この発明の実施の形態１の水先案内表（遅延コード５以下のリンクによる）である。
【図２２】  この発明の実施の形態１の最適経路設計の手順を示すフロー図である。
【図２３】  この発明の実施の形態１で、ノードＮｓからノードＮｄへの要求帯域Ｒの経路を抽出する手順を示すフロー図である。
【図２４】  この発明の実施の形態２の通信経路設定装置の機能ブロック図である。
【図２５】  この発明の実施の形態２の第１の例における最適経路設計の流れを示す図（個別の経路設計の要求に依存する処理）である。
【図２６】  この発明の実施の形態２の第２の例における最適経路設計の流れを示す図（個別の経路設計の要求に依存しない処理）である。
【図２７】  この発明の実施の形態２の第２の例における最適経路設計の流れを示す図（個別の経路設計の要求に依存する処理）である。
【図２８】  この発明の実施の形態２の水先案内平面（遅延コード４以下のリンクによる）である。
【図２９】  この発明の実施の形態３のＯｐａｑｕｅ型のハローパケットのオプション部である。
【図３０】  この発明の実施の形態３におけるＬＳＡの様式である。
【図３１】  従来例１の通信ネットワーク図である。
【図３２】  従来例１のルーチング帯域表である。
【図３３】  従来例１のルーチング進行ノード表である。
【図３４】  従来例１の変化ノードルーチング表である。
【図３５】  従来例１の最適経路設計の手順を示すフロー図である。
【図３６】  従来例１のノードＮｓからノードＮｄへの要求帯域Ｒの経路を抽出する手順を示すフロー図である。
【図３７】  従来例２のＯＳＰＦのルータ用ＬＳＡの様式を示す図である。
【図３８】  従来例３のＯｐａｑｕｅ  ＬＳＡのＬＳＡの様式を示す図である。
【図３９】  従来例３の通常のＯＳＰＦのハローパケットのオプション部である。
【図４０】  この発明の実施の形態４の通信ネットワーク図である。
【図４１】  この発明の実施の形態４のネットワークモデルを示す図である。
【図４２】  この発明の実施の形態４の通信経路設定装置の機能ブロック図である。
【図４３】  通信経路設定部の構成を示す図である。
【図４４】  この発明の実施の形態４の最適経路設計をハードウェア論理回路で実現する例である。
【図４５】  この発明の実施の形態４のハードウェアによるボリューム回路例である。
【図４６】オフィス空間に配置するアレイサイズとアレイ数。
【図４７】  経路計算時間評価のメッシュ型トポロジーを示す図である。
【図４８】  この発明の実施の形態４と従来例１の経路設計時間の比較を示す図である。
【符号の説明】
１  ネットワーク、２  ネットワークモデル、１１  ノード、１２  リンク、１００  通信経路設定装置、１０１  要求取得部、１０２  トポロジー情報記録部、１０３  第一通信特性リンク情報作成部、１０４  第二通信特性リンク情報作成部、１０５  分類第一通信特性リンク情報作成部、１０６  分類第一通信特性リンク情報選択部、１０７  第一通信特性レベル値無効部、１０８  通信経路設定部、１０９  通知パケット作成部、１１０  通知パケット送信部、１１１  通信経路選択部。
【図１】
0003846689.tif 000002
【図２】
0003846689.tif 000003
【図３】
0003846689.tif 000004
【図４】
0003846689.tif 000005
【図５】
0003846689.tif 000006
【図６】
0003846689.tif 000007
【図７】
0003846689.tif 000008
【図８】
0003846689.tif 000009
【図９】
0003846689.tif 000010
【図１０】
0003846689.tif 000011
【図１１】
0003846689.tif 000012
【図１２】
0003846689.tif 000013
【図１３】
0003846689.tif 000014
【図１４】
0003846689.tif 000015
【図１５】
0003846689.tif 000016
【図１６】
0003846689.tif 000017
【図１７】
0003846689.tif 000018
【図１８】
0003846689.tif 000019
【図１９】
0003846689.tif 000020
【図２０】
0003846689.tif 000021
【図２１】
0003846689.tif 000022
【図２２】
0003846689.tif 000023
【図２３】
0003846689.tif 000024
【図２４】
0003846689.tif 000025
【図２５】
0003846689.tif 000026
【図２６】
0003846689.tif 000027
【図２７】
0003846689.tif 000028
【図２８】
0003846689.tif 000029
【図２９】
0003846689.tif 000030
【図３０】
0003846689.tif 000031
【図３１】
0003846689.tif 000032
【図３２】
0003846689.tif 000033
【図３３】
0003846689.tif 000034
【図３４】
0003846689.tif 000035
【図３５】
0003846689.tif 000036
【図３６】
0003846689.tif 000037
【図３７】
0003846689.tif 000038
【図３８】
0003846689.tif 000039
【図３９】
0003846689.tif 000040
【図４０】
0003846689.tif 000041
【図４１】
0003846689.tif 000042
【図４２】
0003846689.tif 000043
【図４３】
0003846689.tif 000044
【図４４】
0003846689.tif 000045
【図４５】
0003846689.tif 000046
【図４６】
0003846689.tif 000047
【図４７】
0003846689.tif 000048
【図４８】
0003846689.tif 000049