WO2010044210A1

WO2010044210A1 - 通信装置及び通信方法

Info

Publication number: WO2010044210A1
Application number: PCT/JP2009/005118
Authority: WO
Inventors: 藤原ゆうき; 松下陽介; 本間秀樹; 森田直樹
Original assignee: Panasonic Corp
Current assignee: Panasonic Corp
Priority date: 2008-10-15
Filing date: 2009-10-02
Publication date: 2010-04-22
Anticipated expiration: 2011-04-15
Also published as: EP2337283A4; EP2337283A1; CN101897160B; JP5307152B2; US8385336B2; EP2337283B1; US20110261706A1; CN101897160A; JPWO2010044210A1

Abstract

始点装置は、要求する経路数を経路要求パケットに記載し、各中継装置は、最初の経路要求パケット受信時に当該経路要求パケットが通過した経路の状態を示す経路評価値に基づいて待機時間を決定してタイマを開始し、タイマが満了するまでに受信した経路要求パケットの中から経路評価値が高いものを始点装置が要求する経路数分だけ選択してブロードキャストする。

Description

通信装置及び通信方法

　本発明は、通信を開始するデータ種別に適した経路を探索する通信装置及び通信方法に関し、より特定的には、通信を要求する始点装置とその宛先となる終点装置との間で直接通信できない場合に、始点装置から終点装置までマルチホップで通信する経路を探索する通信装置及び通信方法に関する。

　従来、始点装置と終点装置との間で直接通信できない場合に、始点装置から終点装置までの経路を探索する方法として、以下のような方法がある。

　最初に、始点装置は、終点装置を指定した経路要求パケットをブロードキャストする。他の装置がブロードキャストした経路要求パケットを受信した装置は、受信した経路要求パケットにおいて指定された終点装置が自装置であるか否かを判定する。終点装置が自装置でないと判定した場合、通信装置は、自装置を通過したことを示す情報を経路要求パケットに追加して、ブロードキャストする。

このように、終点装置以外の装置が、受信した経路要求パケットのブロードキャストを繰り返すことにより、経路要求パケットは最終的に終点装置に到達する。このとき終点装置が受信する経路要求パケットには、始点装置から終点装置までに通過した全ての中継装置を示す情報が含まれている。終点装置は、その中継装置を示す情報に基づいて経路を設定する。

しかし、経路要求パケットを受信した装置が、受信した全ての経路要求パケットをブロードキャストする場合、以下のような問題が生じる。

始点装置や中継装置がブロードキャストする経路要求パケットは、通常、当該経路要求パケットを送信した装置と直接通信できる複数の装置により受信される。経路要求パケットを受信した複数の装置は、自装置が終点装置でなければ、それぞれ経路要求パケットをブロードキャストする。そのため、経路要求パケットが１つ送信される度に、当該経路要求パケットを直接受信する中継装置数の経路要求パケットがブロードキャストされる。

このように、経路要求パケットを受信した装置が受信した経路要求パケットを全てブロードキャストする場合、経路要求パケットが送信される度に、次に送信される経路要求パケットの数が増加する。その結果、増加した経路要求パケットがデータ通信に使用する帯域を圧迫し、他の装置間のデータ通信を妨げることになる。

かかる問題を解決することを目的とする技術として、経路要求パケットが通過した経路における経路評価値を経路要求パケットに記載し、この経路評価値に基づいて中継装置がブロードキャストする経路要求パケットを制限するものがある（例えば、特許文献１）。ここで、経路評価値とは、当該経路が接続した状態を保っている時間長や、当該経路で通信する場合に期待されるスループットなどを示す。

以下、特許文献１の技術において、経路探索時に中継装置が経路要求パケットを受信した際に行う処理について説明する。

中継装置は、経路要求パケットを受信する度に、当該経路要求パケットが通過した経路の状態から経路評価値を計算する。中継装置は、経路要求パケットを最初に受信すると、そのパケットをそのままブロードキャストする。一方、最初に受信した経路要求パケットと異なる経路を通過し、２番目以降に受信した経路要求パケット、すなわち重複受信パケットを受信すると、中継装置は、既にブロードキャストした経路要求パケットの経路評価値と重複受信パケットの経路評価値とを比較する。重複受信パケットの経路評価値が既に送信した経路要求パケットの経路評価値よりも高い場合、中継装置は重複受信パケットをブロードキャストする。一方、重複受信パケットの経路評価値が既に送信した経路要求パケットの経路評価値よりも低い場合、中継装置は重複受信パケットをブロードキャストせず、破棄する。

特開２００７－２２１７９０号公報（６、１６頁）

　しかし、上記の特許文献１の技術では、以下のような問題が生じていた。
中継装置が重複受信した経路要求パケットが、既にブロードキャストした経路要求パケットよりも経路評価値が高くなる場合、中継装置がブロードキャストする経路要求パケットの数が減少しないという問題があった。

それ故に、本発明の目的は、中継装置が既にブロードキャストした経路要求パケットよりも経路評価値が高くなる経路要求パケットを次々と重複受信する場合でも、中継装置がブロードキャストする経路要求パケット数を一定数以下に制限し、かつ経路評価値が高い経路を探索できる通信装置及び通信方法を提供することである。

上記目的を達成するために、本発明は、以下の特徴を有する。本発明の第１の局面は、通信を要求する始点装置が宛先となる終点装置へマルチホップで通信するにあたり、経路作成のための経路要求パケットを終点装置までの各中継装置へ送信する通信装置であって、始点装置を示す情報、終点装置を示す情報、及び始点装置から自装置に経路要求パケットを直接送信した直前の中継装置までの経路状態を示す経路評価値を含む経路要求パケットを少なくとも１つの直前の中継装置から受信する受信部と、受信した経路要求パケットに記述された始点装置から直前の中継装置までの経路状態と直前の中継装置と自装置との間の経路状態に基づいて、始点装置から自装置までの経路評価値を算出し、経路要求パケットの経路評価値を更新する更新部と、経路要求パケットを受信すると受信時を含む所定の待機時間を設定し、始点装置及び終点装置を示す情報が受信した経路要求パケットと同一で待機時間内に更新した経路要求パケットの中から、経路評価値が高い順に所定数の経路要求パケットを選択し、自装置と直接通信できる隣接装置へ送信する制御部とを具備する。

さらに、本発明の通信装置は、自装置と隣接装置との間の通信に使用可能な帯域を複数のタイミングで測定する測定部をさらに備えるとよい。その場合、経路状態は経路上の各通信装置間の通信に使用可能な帯域を通信装置間毎に含むとよい。また、更新部は経路要求パケットに記述された始点装置から直前の中継装置までの各通信装置間における使用可能な帯域と測定部により測定された直前の中継装置と自装置との間の使用可能な帯域とに基づいて、始点装置から自装置までの経路全体で使用可能な帯域を経路評価値として算出するとよい。そして、更新部は使用可能な帯域が大きいほど経路評価値を高い値として算出するとよい。

また、前述した測定部は、自装置と隣接装置との間の通信に使用可能な帯域を複数のタイミングで測定し、測定された帯域の中から最小値を求めてもよい。その場合、経路状態は経路上の各通信装置間における使用可能な帯域の最小値を含むとよい。また、更新部は経路要求パケットに記述された始点装置から直前の中継装置までの最小値と測定部により測定された直前の中継装置と自装置との間の最小値とを比較して、始点装置から自装置までの経路全体での最小値を経路評価値として算出するとよい。そして、更新部は算出された値が大きいほど経路評価値を高い値として算出するとよい。

また、前述した測定部は、自装置と隣接装置との間で通信不能な状態から通信可能な状態に変化した時点から現在までの経過時間を測定するとよい。その場合、経路状態は経路上の各通信装置間における経過時間の最小値を含むとよい。また、更新部は経路要求パケットに記述された始点装置から直前の中継装置までの各通信装置間における経過時間の最小値と測定部により測定された直前の中継装置と自装置との間の経過時間とを比較して、始点装置から自装置までの経路全体での経過時間の最小値を経路評価値として算出するとよい。そして、更新部は算出された最小値が大きいほど経路評価値を高い値として算出するとよい。

　さらに、経路状態は経路のホップ数を含むとよい。その場合、更新部は経路要求パケットに記述された始点装置から直前の中継装置までのホップ数に１を加えることにより、始点装置から自装置までの経路のホップ数を経路評価値として算出するとよい。また、更新部は算出されたホップ数が少ないほど経路評価値を高い値として算出するとよい。

　さらに、経路状態は始点装置から直前の中継装置までの経路のホップ数を含むとよい。その場合、算出部は経路状態に含まれたホップ数に１を加えることにより、始点装置から自装置までの経路のホップ数を第２の経路評価値として算出するとよい。また、更新部は算出されたホップ数が少ないほど第２の経路評価値を高い値として算出するとよい。そして、制御部は、更新部により算出された経路評価値が等しい経路要求パケットが所定数以上ある場合、第２の経路評価値が高い順に所定数の経路要求パケットを選択するとよい。

　また、制御部は経路要求パケットを受信すると、経路評価値に応じて所定の待機時間を設定するとよい。さらに、制御部はその経路評価値が低いほど所定の待機時間を長く設定するとよい。

　さらに、制御部は、これまでに受信した経路要求パケットに基づいて設定した所定の待機時間の終了時刻よりも新たに受信した経路要求パケットに基づいて設定する待機時間の終了時刻が早い場合は、待機時間を短縮して、新たに受信した経路要求パケットに基づいて設定する待機時間の終了時刻で経路要求パケットを送信するとよい。

　さらに、制御部は、２番目以降の経路要求パケットを受信すると、これまでに受信した経路要求パケットの数が所定の閾値に達したかどうかを判定し、所定の閾値に達したと判定した時点で経路要求パケットを送信するとよい。

　また、経路状態は始点装置から直前の中継装置までの経路のホップ数を含むとよい。その場合、算出部は経路状態に含まれたホップ数に１を加えることにより、始点装置から自装置までの経路のホップ数をさらに算出するとよい。また、制御部は、更新部により算出されたホップ数がこれまでに受信した経路要求パケットから算出されたホップ数よりも多いという第１の条件と、新たに受信した経路要求パケットから算出された経路評価値がこれまでに受信した経路要求パケットから算出された経路評価値よりも低いという第２の条件を満たすか否かを判定し、第１の条件と第２の条件をともに満たすと判定した時点で経路要求パケットを送信するとよい。

　さらに、制御部は、第１の条件を満たし、かつ第２の条件を満たさないと判定した場合、待機時間を延長し、新たに受信した経路要求パケットに基づいて設定した待機時間の終了時刻に経路要求パケットを送信するとよい。

　また、さらに、制御部は、待機時間を延長する場合は、延長前の待機時間の終了時刻にその時点で選択した経路要求パケットを送信し、さらに延長後の待機時間の終了時刻にその時点で選択した経路要求パケットを送信するとよい。

　また、制御部は、最初に受信した経路要求パケットをすぐに隣接装置に送信し、待機時間満了後に、最初に受信した経路要求パケットと始点装置及び終点装置を示す情報が同一である他の経路要求パケットのうち、経路評価値が高い順に所定数の経路要求パケットを選択するとよい。

　また、制御部は、選択した経路要求パケットに記述された情報を１つの経路要求パケットにまとめて記述するとよい。

　また、始点装置は、経路数を示す情報を経路要求パケットにさらに記述し、所定数が経路数であるとよい。

　また、制御部は、所定の待機時間の終了時刻経過後に受信した経路要求パケットを破棄するとよい。

　本発明の第２の局面は、通信開始を要求する始点装置が宛先となる終点装置へマルチホップで通信するにあたり、経路作成のための経路要求パケットを終点装置までの各中継装置へ送信する通信方法であって、始点装置を示す情報、終点装置を示す情報、及び始点装置から自装置に経路要求パケットを直接送信した直前の中継装置までの経路状態を記述した経路要求パケットを少なくとも１つの直前の中継装置から受信し、受信した経路要求パケットに記述された始点装置から直前の中継装置までの経路状態と直前の中継装置と自装置との間の経路状態に基づいて、始点装置から自装置までの経路状態を示す経路評価値を算出し、始点装置から自装置までの経路状態を記述して経路要求パケットを更新し、経路要求パケットを受信すると所定の待機時間を設定し、受信した経路要求パケットと始点装置及び終点装置を示す情報が同一で待機時間内に受信した経路要求パケットの中から、経路評価値が高い順に所定数の経路要求パケットを選択し、自装置と直接通信できる隣接装置へ送信する。

　本発明によれば、受信した経路要求パケットに基づき所定の待機時間を設定し、受信した経路要求パケットと始点装置及び終点装置を示す情報が同一で待機時間内に受信した経路要求パケットの中から更新部により更新された経路評価値が高い経路要求パケットを所定数選択し、隣接装置へ送信する。したがって、経路作成のために送信される経路要求パケットの数が削減され、帯域の消費を抑えつつ、所定の始点装置と所定の終点装置との間で経路の状態を示す経路評価値が高い経路を作成することができる。

図１は、第１の実施形態における通信装置の機能ブロック図である。図２は、測定値管理テーブルを表した図である。図３は、経路要求パケットのフレームフォーマットを示す図である。図４は、重複管理テーブルを表した図である。図５は、第１の実施形態における通信装置の経路要求パケット送信処理を示すフローチャート図である。図６は、始点装置の経路要求パケット生成処理を示すフローチャート図である。図７は、第１の実施形態における通信装置の経路要求パケット受信処理を示すフローチャート図である。図８は、第１の実施形態における評価基準値更新、経路評価値算出処理を示すフローチャート図である。図９は、第１の実施形態におけるネットワーク構成図である。図１０は、第１の実施形態において通信装置９０１から９０４にデータ通信を要求して経路探索する場合を表すシーケンス図である。図１１は、第２の実施形態における通信装置の機能ブロック図である。図１２は、第２の実施形態における通信装置の経路要求パケット受信処理を示すフローチャート図である。図１３は、第２の実施形態における評価基準値更新、経路評価値算出処理を示すフローチャート図である。図１４は、通信装置のタイマ変更処理を示すフローチャート図である。図１５は、第２の実施形態におけるネットワーク構成図である。図１６は、第２の実施形態において通信装置９０１から９０４にデータ通信を要求して経路探索する場合を表すシーケンス図である。図１７は、第３の実施形態における通信装置の機能ブロック図である。図１８は、第３の実施形態における通信装置の経路要求パケット受信処理を示すフローチャート図である。図１９は、第３の実施形態における通信装置の経路要求パケット送信処理を示すフローチャート図である。図２０は、第３の実施形態におけるネットワーク構成図である。図２１は、第３の実施形態において通信装置９０１から９０４にデータ通信を要求して経路探索する場合を表すシーケンス図である。図２２は、通信装置のハード構成を示したハード図である。

　（第１の実施形態）
本実施の形態では、通信開始を要求する始点装置が、通信を開始するデータ種別に適した経路を探索する場合に、中継装置において受信した全ての経路要求パケットをブロードキャストするのではなく、経路評価値が高い経路を通過してきた経路要求パケットを、始点装置が設定した数だけブロードキャストする。経路評価値とは、経路要求パケットを選択する際に用いるパラメータであり、始点装置からそれぞれ異なる経路を通って各中継装置に到着した複数の経路要求パケットについて、各経路要求パケットが通過した経路の状態を示す値である。

　本発明の第１の実施形態に係る通信装置の機能を説明する前に、説明の便宜上、まず、経路要求パケットのフォーマットについて図３を用いて説明する。

　図３は経路要求パケットのデータフォーマット図である。経路要求パケット３０１は、終点アドレス３０２、始点アドレス３０３、経路要求パケット番号３０４、要求経路数３０５、条件識別子３０６、評価基準値３０７、中継装置アドレス３０８、評価用測定値３０９により構成されている。

　終点アドレス３０２は、始点装置が通信を要求する接続先である終点装置のアドレスを示す。始点アドレス３０３は、始点装置のアドレスを示す。経路要求パケット番号３０４は、同じ始点装置から送信された経路要求パケットを識別するための値である。

　要求経路数３０５は、始点装置が設定する経路数であり、「１」以上の整数に設定される。ただし、終点装置が始点装置に経路を返信する際は、要求する経路がないため要求経路数は「０」に設定される。

　条件識別子３０６は、経路を探索する条件を特定するパラメータであり、始点装置によって設定される。各通信装置は条件識別子３０６に基づいて選択する条件を変更する。本実施の形態では、条件識別子の一例として以下の６種類を挙げる。

条件識別子「１」：最新の通信状態に基づき、帯域が最大である経路を探索する条件
条件識別子「２」：過去の通信状態の履歴に基づき、帯域の最小値が一定値以上であることを保証する経路を探索する条件
条件識別子「３」：始点装置から送信されたパケットが終点装置に到達するまでの遅延が最小である経路を探索する条件
条件識別子「４」：ホップ数が最小である経路を探索する条件
条件識別子「５」：最新の通信状態に基づき、当該経路上の各中継装置間の通信継続時間が一定値以上であることを保証する経路を探索する条件
条件識別子「６」：過去の通信状態の履歴に基づき、帯域の最小値が一定値以上であることを保証する経路と、ホップ数が最小である経路とを同時に探索する条件

　評価基準値３０７は、条件識別子３０６の設定値に基づき計算された値である。この値は経路評価の際に利用される。評価基準値３０７は、始点アドレス３０３と経路要求パケット番号３０４が同一となる経路要求パケットが通過した複数の経路を比較するために利用される。例えば、条件識別子が「１」に設定されている場合、評価基準値３０７は、経路上の各中継装置間における最新の通信状態をもとに推定される、始点装置から自装置までの通信帯域となる。

　条件識別子が「２」に設定されている場合、評価基準値３０７は、経路上の各中継装置間で過去の一定期間測定した帯域の最小値のうち、経路上での最小値となる。

　条件識別子が「３」に設定されている場合、評価基準値３０７は、始点装置が経路要求パケットを送信する時刻となる。この場合、あらかじめネットワーク内の全装置の時計を同期させておくことで、各装置は、経路要求パケットが到着した時刻と評価基準値３０７の時刻との時間差に基づいて経路要求パケットを選択することができる。

　条件識別子が「４」に設定されている場合、評価基準値３０７は、始点装置からのホップ数となる。

　条件識別子が「５」に設定されている場合、評価基準値３０７は、経路上の各中継装置間において通信不能な状態から通信可能な状態に変化した最新の時点から現在までの通信継続時間のうち、経路上の最小値となる。

　さらに、条件識別子が「６」に設定されている場合のように、それぞれ異なる条件を満たす複数の経路を同時に探索する場合、経路要求パケット３０１は、複数の評価基準値３０７を有する。図３では、複数の評価基準値３０７が評価基準値（１）、評価基準値（２）などと表されている。条件識別子が「６」に設定されている場合は、評価基準値（１）はホップ数となり、評価基準値（２）は経路上の各中継装置間で過去の一定期間測定した帯域の最小値のうち、経路上での最小値となる。これにより、それぞれ異なる複数の条件を満たす複数の経路を、１回の経路探索で同時に設定することができる。

中継装置アドレス３０８は、当該経路要求パケットが通過した始点装置から自装置までの経路上にある中継装置のアドレスである。評価用測定値３０９は、各中継装置とその直前（１ホップ前）の中継装置との間で測定された通信の状態を示す情報である。中継装置アドレス３０８と評価用測定値３０９は、それぞれ経路要求パケットが各中継装置で中継される度に追加される。この評価用測定値３０９は、処理の便宜上、評価基準値３０７に対応して、経路要求パケット３０１に格納されることが望ましい。図３では、複数の評価基準値３０７である評価基準値（１）、評価基準値（２）に対応する評価用測定値３０９が、それぞれ評価用測定値（１）、評価用測定値（２）と表されている。

以上に述べた経路要求パケットは、始点装置が経路探索する際に利用されるが、終点装置が始点装置に対し経路を返信する際にも利用される。以降の説明では、終点装置が始点装置に経路を返信する経路要求パケットのことを返信用経路要求パケットと呼ぶこととする。この返信用経路要求パケットのフォーマットは、経路要求パケットの始点アドレスと終点アドレスが入れ替わっていることと要求経路数が「０」に設定されている以外は、上述したフォーマットと同じである。

つぎに、本発明の第１の実施形態に係る通信装置の機能構成を詳細に説明する。図１は、本発明の第１の実施形態に係る通信装置の機能ブロック図である。図１を参照すると、本実施形態の通信装置は、受信部１０１、測定部１０２、更新部１０３、重複検出部１０４、比較部１０５、パケット保存部１０６、タイマ１０７、パケット破棄部１０８、送信部１０９を備える。

受信部１０１は、各種通信方式により受信したデータパケットから経路要求パケットを更新部１０３に出力する。測定部１０２は、経路評価値の算出のため必要な情報を測定し、測定値管理テーブル２０１（詳細は後述）を更新する。本実施の形態では、経路評価値の算出のため必要な情報とは、隣接装置（自装置と直接通信できる装置）と自装置との間の通信における帯域と、自装置と隣接装置との間で、通信不能な状態から通信可能な状態に変化した最新の時点から現在までの通信継続時間である。測定部１０２は、経路要求パケット以外のパケットも含め、自装置から直接通信可能な位置に配置された隣接装置が送信したパケットの受信電力を測定し、当該パケットを送信した隣接装置と自装置との間の通信における帯域を推定する。ここでいう帯域とは、例えばＰＨＹ（Ｐｈｙｓｉｃａｌ　Ｌａｙｅｒ）レートやＭＡＣ（Ｍｅｄｉａ　Ａｃｃｅｓｓ　Ｃｏｎｔｒｏｌ）レート、スループット等のデータの通信速度を表すパラメータのことである。また、送信部１０９は、一定間隔または任意のタイミングで自装置がネットワーク上に存在することを示すＨｅｌｌｏパケットを送信して、それを受信することによって通信継続時間を測定する。以上により、測定された帯域や通信継続時間は測定値管理テーブル２０１に別々に格納される。

図２は、測定値管理テーブルの一例を表した図である。測定値管理テーブル２０１は、隣接装置毎に、隣接装置アドレス２０２、最新測定値２０３、保存測定値２０４、平均測定値２０５、最小測定値２０６から構成されている。隣接装置アドレス２０２は、受信したパケットのヘッダに記載されている当該パケットを送信した隣接装置のアドレスである。最新測定値２０３は、各隣接装置と自装置間において測定部１０２で測定された測定値のうち、最新となる値である。保存測定値２０４は、隣接装置と自装置間において測定部１０２で測定された測定値のうち、新しい順に一定個数保存された値である。なお、保存測定値２０４として保存されている測定値の個数は、帯域の変動頻度や帯域推定に求められる精度などに基づいて変更することができる。また、保存測定値２０４として保存されている測定値の個数は、隣接装置毎に異なっていてもよい。平均測定値２０５は、保存測定値２０４として保存された一定個数の測定値の平均値である。最小測定値２０６は、保存測定値２０４として保存された一定個数の測定値の最小値である。例えば、最小測定値２０６として帯域の最小値が格納されている場合、その値は通信装置間の伝送路状態が最も悪い時にどの程度帯域を保証できるかの指標となる。なお、最小測定値２０６は保存測定値２０４として保存された帯域の最小値とする必要はなく、一定期間中に推定された測定値の最小値としてもよい。

更新部１０３は、経路要求パケットが当該通信装置から過去に送信されたものである場合、その経路要求パケットをパケット破棄部１０８に出力した上で破棄する。一方、その経路要求パケットが当該通信装置から過去に送信されたものでない場合、更新部１０３は、測定部１０２の測定結果を加えて、経路要求パケットを更新し、経路評価値を算出する。経路要求パケット更新処理と経路評価値算出処理については詳細を後述する。更新部１０３は、経路要求パケットを更新すると、その経路要求パケットとその経路評価値を重複検知部１０４へ出力する。

重複検知部１０４は、更新部１０３により出力された経路要求パケットが重複受信であるか否かを重複管理テーブル（詳細は後述）に基づいて判定する。判定後、重複検知部１０４は、重複受信である経路要求パケットとその経路評価値を比較部１０５に、それ以外の経路要求パケットとその経路評価値をタイマ１０７に出力する。

　図４は、重複管理テーブルを表した図である。重複管理テーブル４０１には、始点装置毎に、始点アドレス４０２、経路要求パケット番号４０３、タイマ状態４０４が保存されている。始点アドレス４０２には、受信した経路要求パケットに含まれる始点装置のアドレスが格納される。経路要求パケット番号４０３には、受信した経路要求パケットに含まれる経路要求パケット番号が格納される。タイマ状態４０４には、タイマ１０７（詳細は後述）がタイマを設定中であるか、タイマが満了しているかを示す情報が格納される。重複管理テーブル４０１を利用した重複検知部１０４の判定処理の詳細については後述する。

比較部１０５は、重複検知部１０４により出力された経路要求パケットの経路評価値と、パケット保存部１０６（詳細は後述）により保存されている全ての経路要求パケットの経路評価値を参照して、重複検知部１０４により出力された経路要求パケットとその経路評価値をパケット保存部１０６に出力するか、パケット破棄部１０８に出力した上で破棄するか判定する。比較部１０５の動作の詳細については後述する。

パケット保存部１０６は、比較部１０５とタイマ１０７により出力された経路要求パケットを保存する。また、その経路要求パケットの経路評価値も併せて保存するとよい。保存する経路要求パケットの数が経路要求パケットに含まれる要求経路数３０５よりも大きい場合は、保存されている経路要求パケットの中から経路評価値が最小のパケットを更新する。また、複数の始点装置から経路要求パケットが送信されている場合は、それぞれの始点アドレスに対して経路要求パケットを保存する領域を確保する。

タイマ１０７は、重複検知部１０４により出力された経路要求パケットに含まれる条件識別子３０６とそのパケットの経路評価値に基づいて、当該経路要求パケットを受信してからパケット保存部１０６に保存されている経路要求パケットを送信するまでの待機時間を算出する。待機時間は、経路要求パケットの経路評価値が高いほど、短く算出される。また、待機時間は、１ホップ余分に中継装置を通過した経路要求パケットを各装置が受信できるように、１ホップ進むのに必要な時間に、経路評価値に比例した値、反比例した値、または経路評価値に応じた段階的な値を加えた時間としてもよい。

タイマ１０７は、待機時間算出後、その待機時間をタイマ長とするタイマを開始させる。その後、タイマ１０７は経路要求パケットをパケット保存部１０６に出力する。さらに、待機時間が満了すると、タイマ１０７は、送信部１０９に経路要求パケットを送信させる。タイマ１０７の動作の詳細は後述する。

　パケット破棄部１０８は、更新部１０３、重複検知部１０４と比較部１０５により出力された経路要求パケットを破棄する。

　送信部１０９は、各種通信方式によりデータパケットを送信する。ただし、自装置が始点装置、中継装置、終点装置のいずれにあたるかにより、送信部１０９が行う処理が異なる。自装置が始点装置にあたる場合、送信部１０９は新しく経路制御パケットを生成してブロードキャストする。自装置が中継装置にあたる場合、送信部１０９はタイマが満了するとパケット保存部１０６により保存されているパケットをブロードキャストする。自装置が終点装置にあたる場合、送信部１０９は、経路要求パケットの終点アドレスと始点アドレスを交換し、要求経路数を「０」に設定した返信用経路要求パケットを生成する。そして、送信部１０９は、もとの経路要求パケットが中継された逆の経路で、始点装置に、生成した返信用経路要求パケットをユニキャストで返信する。

　以上のように構成された通信装置について、図５から図８を用いてその動作を説明する。まず、各装置が経路要求パケットを送信するまでの一連の処理を説明する。図５は、その処理を示したフローチャートである。

まず、通信装置は、自装置が他の装置と通信する必要性が生じたことを示す通信要求があるか否かを判定する（ＳＴＥＰ５０１）。通信装置は、通信要求があると判定すると、経路を探索するために経路要求パケットを生成する（ＳＴＥＰ５０２）。

図６は、ＳＴＥＰ５０２での経路要求パケット生成処理を示したフローチャートである。まず、送信部１０９は、新たに生成する経路要求パケットの終点アドレスに接続先である終点装置のアドレスを設定し、始点アドレスに自らのアドレスを設定する（ＳＴＥＰ６０１）。つぎに、送信部１０９は、重複管理テーブル４０１から始点アドレス４０２が自らのアドレスとなる経路要求パケット番号４０３を取得する。そして、送信部１０９は、取得した番号をインクリメントした値を、新しく生成する経路要求パケットの経路要求パケット番号３０４に設定する（ＳＴＥＰ６０２）。そして、送信部１０９は、重複管理テーブル４０１の経路要求パケット番号４０３をインクリメントし、重複管理テーブル４０１を更新する（ＳＴＥＰ６０３）。それから、送信部１０９は、ネットワークの規模に応じて要求経路数３０５を設定する（ＳＴＥＰ６０４）。さらに、送信部１０９は、通信しようとするデータの種類に応じて条件識別子３０６を設定する（ＳＴＥＰ６０５）。最後に、送信部１０９は、条件識別子に応じて必要な数の評価基準値３０７の領域を用意し、ＳＴＥＰ６０１～ＳＴＥＰ６０５で設定していないパラメータを「０」や経路要求パケットの送信時刻などで初期化する（ＳＴＥＰ６０６）。

ＳＴＥＰ５０２において経路要求パケットを生成すると、送信部１０９は、その経路要求パケットをブロードキャストして（ＳＴＥＰ５０３）、ＳＴＥＰ５０１の処理を実行する。

つぎに、各装置が経路要求パケットを受信した後の一連の処理を説明する。図７は、その処理を示したフローチャートである。

まず、受信部１０１は、受信したデータパケットが経路要求パケットであるか否かを判定する（ＳＴＥＰ７０１）。受信部１０１は、受信したデータパケットが経路要求パケットでない場合（ＳＴＥＰ７０１でＮｏ）、経路要求パケットを受信するまで、ＳＴＥＰ７０１の処理を繰り返す。一方、受信部１０１が受信したデータパケットが経路要求パケットである場合（ＳＴＥＰ７０１でＹｅｓ）、以下の処理が順に実行される。

更新部１０３は、受信した経路要求パケットに含まれる始点アドレス３０３もしくは中継装置アドレス３０８に自らのアドレスが存在するか否かを判定する（ＳＴＥＰ７０２）。始点アドレス３０３もしくは中継装置アドレス３０８に自らのアドレスが存在する場合（ＳＴＥＰ７０２でＹｅｓ）、更新部１０３は、受信した経路要求パケットは以前に自装置を通過あるいは自装置により生成されたものであると判定し、その経路要求パケットをパケット破棄部１０８に出力することにより、破棄する（ＳＴＥＰ７１３）。一方、始点アドレス３０３もしくは中継装置アドレス３０８に自らのアドレスが存在しない場合（ＳＴＥＰ７０２でＮｏ）、更新部１０３は、受信した経路要求パケットは以前に自装置を通過したものでないと判定して、その経路要求パケットに対して以下の更新処理を行う。

経路要求パケットを受信した後、更新部１０３は、経路要求パケットに含まれる評価基準値を更新し、経路評価値を算出する（ＳＴＥＰ７０３）。この評価基準値の更新処理と経路評価値の算出処理については後述する。

つぎに、重複検知部１０４は、更新部１０３により出力された経路要求パケットに含まれる始点アドレス３０３に対応する経路要求パケット番号４０３を重複管理テーブル４０１から取得する。そして、重複検知部１０４は、更新部１０３により出力された経路要求パケットの経路要求パケット番号３０４が取得された経路要求パケット番号４０３より小さいか否か判定する（ＳＴＥＰ７０４）。経路要求パケット番号３０４が経路要求パケット番号４０３よりも小さい場合（ＳＴＥＰ７０４でＹｅｓ）、受信した経路要求パケットは過去の経路探索に使用されたものであるので、重複検知部１０４はその経路要求パケットをパケット破棄部１０８に出力することにより、破棄する（ＳＴＥＰ７１３）。

経路要求パケット番号３０４が経路要求パケット番号４０３よりも小さくない場合（ＳＴＥＰ７０４でＮｏ）、重複検知部１０４は、経路要求パケット番号３０４が経路要求パケット番号４０３と等しいか否か判定する（ＳＴＥＰ７０５）。経路要求パケット番号３０４が経路要求パケット番号４０３と等しくない、すなわち経路要求パケット番号３０４が経路要求パケット番号４０３よりも大きい場合（ＳＴＥＰ７０５でＮｏ）、重複検知部１０４は受信した経路要求パケットが初めて受信されたものであると判定する。そして、重複検知部１０４は、重複管理テーブル４０１の経路要求パケット番号４０３を、受信した経路要求パケットに含まれていた経路要求パケット番号３０４の値に更新する（ＳＴＥＰ７０６）。つぎに、タイマ１０７は、重複検知部１０４により出力された経路要求パケットの条件識別子３０６とその経路評価値より待機時間を算出する（ＳＴＥＰ７０７）。そして、タイマ１０７は、重複管理テーブル４０１のタイマ状態を「設定中」に更新し、算出した待機時間を設定したタイマを開始する（ＳＴＥＰ７０８）。その後、パケット保存部１０６は受信した経路要求パケットを保存する（ＳＴＥＰ７１１）。さらに、パケット保存部１０６は保存経路数をインクリメントする（ＳＴＥＰ７１２）。ＳＴＥＰ７１２の終了後、ＳＴＥＰ７０１の処理が実行される。

一方、経路要求パケット番号３０４が経路要求パケット番号４０３と等しい場合（ＳＴＥＰ７０５でＹｅｓ）、重複検知部１０４は受信した経路要求パケットが重複受信されたものであると判定して、さらに重複管理テーブル４０１に格納されたタイマ状態４０４が「設定中」か「満了」であるかを判定する（ＳＴＥＰ７０９）。タイマ状態４０４が「満了」であった場合（ＳＴＥＰ７０９で「タイマ満了」）、重複検知部１０４は、受信した経路要求パケットをパケット破棄部１０８に出力することにより破棄する（ＳＴＥＰ７１３）。経路要求パケットが破棄されると、ＳＴＥＰ７０１の処理が実行される。

タイマ状態４０４が「設定中」であった場合（ＳＴＥＰ７０９で「タイマ設定中」）、比較部１０５は、受信した経路要求パケットの経路評価値と、パケット保存部１０６により保存されている経路要求パケットの経路評価値とを比較する（ＳＴＥＰ７１０）。

受信した経路要求パケットに含まれる経路評価値が、パケット保存部１０６が保存している経路要求パケットの経路評価値のいずれよりも小さいと判定した場合（ＳＴＥＰ７１０でＹｅｓ）、比較部１０５は、パケット保存部１０６が保存している経路要求パケットの数が受信した経路要求パケットに含まれる要求経路数よりも少ないか否かを判定する（ＳＴＥＰ７１４）。パケット保存部１０６が保存している経路要求パケットの数がその要求経路数と等しいと判定した場合（ＳＴＥＰ７１４でＮｏ）、比較部１０５は、受信した経路要求パケットをパケット破棄部１０８に出力することにより破棄する（ＳＴＥＰ７１３）。逆に、パケット保存部１０６が保存している経路要求パケットの数がその要求経路数よりも少ないと判定した場合（ＳＴＥＰ７１４でＹｅｓ）、比較部１０５は、受信した経路要求パケットをパケット保存部１０６に出力し、パケット保存部１０６はその経路要求パケットを保存する（ＳＴＥＰ７１１）。さらに、パケット保存部１０６は保存経路数をインクリメントする（ＳＴＥＰ７１２）。ＳＴＥＰ７１２の終了後、経路要求パケット受信処理（ＳＴＥＰ７０１）に戻る。

一方、受信した経路要求パケットに含まれる経路評価値が、パケット保存部１０６が保存している経路要求パケットの経路評価値のいずれか１つより大きいと判定した場合（ＳＴＥＰ７１０でＮｏ）、比較部１０５は、パケット保存部１０６が保存している経路要求パケットの数が受信した経路要求パケットに含まれる要求経路数よりも少ないか否かを判定する（ＳＴＥＰ７１５）。比較部１０５は、パケット保存部１０６が保存している経路要求パケットの数が要求経路数よりも少ないと判定した場合（ＳＴＥＰ７１５でＹｅｓ）、パケット保存部１０６は、その経路要求パケットを保存し（ＳＴＥＰ７１１）、保存経路数をインクリメントする（ＳＴＥＰ７１２）。そして、ＳＴＥＰ７０１の処理が実行される。一方、比較部１０５は、パケット保存部１０６が保存している経路要求パケットの数が要求経路数と等しいと判定した場合（ＳＴＥＰ７１５でＮｏ）、受信した経路要求パケットをパケット保存部１０６に出力し、パケット保存部１０６は、保存している経路要求パケットのうち評価基準値３０７が最小の経路要求パケットを、受信した経路要求パケットに書き換える（ＳＴＥＰ７１６）。ＳＴＥＰ７１６の終了後、ＳＴＥＰ７０１の処理が実行される。

つぎに、更新部１０３がＳＴＥＰ７０３において実行する評価基準値の更新処理と経路評価値の算出処理の詳細を、図８を用いて、説明する。

　まず、更新部１０３は、受信した経路要求パケットに関する直前の中継装置アドレスを以下のいずれかの方法により取得する（ＳＴＥＰ８００）。
方法１：経路要求パケット内に記載されている中継装置アドレス３０８のうち最後尾に記載されている中継装置アドレスを取得する。
方法２：自装置が最初の中継装置である場合は、中継装置アドレス３０８の替わりに始点アドレス３０３を取得する。
方法３：パケットヘッダに当該経路要求パケットを送信した装置のアドレスが含まれている場合は、直前の中継装置アドレスとしてそのアドレスを取得する。

つぎに、更新部１０３は受信した経路要求パケットに含まれる条件識別子３０６を取得する（ＳＴＥＰ８０１）。そして、更新部１０３は受信した経路要求パケットに含まれる中継装置アドレス３０８に自らのアドレスを追加する（ＳＴＥＰ８０２）。それから、更新部１０３は受信した経路要求パケットに含まれていた条件識別子３０６の値に応じて、以降の処理を切り替える（ＳＴＥＰ８０３）。

条件識別子が「１」に設定されている場合、更新部１０３は、直前の中継装置アドレスと同じ隣接装置アドレス２０２に関する帯域の最新測定値２０３を、測定値管理テーブル２０１から取得する（ＳＴＥＰ８０５）。つぎに、更新部１０３は、受信した経路要求パケットの最後の評価用測定値（１）に、取得した最新の測定値２０３を追加する（ＳＴＥＰ８０６）。その後、更新部１０３は、受信した経路要求パケットに含まれている全ての評価値を用いて通過経路全体を通じた帯域を算出する（ＳＴＥＰ８０７）。通過経路全体を通じた帯域は、経路要求パケットに含まれる全ての評価用測定値（１）の逆数を求め、その総和の逆数を求めることにより算出される。そして、更新部１０３は、受信した経路要求パケットの評価基準値（１）を算出した帯域に更新する（ＳＴＥＰ８０８）。最後に、評価基準値（１）をもとに経路評価値を算出する（ＳＴＥＰ８０９）。この場合、更新部１０３は、評価基準値３０７の値、あるいはその値を正規化した値などを経路評価値として算出する。以上によって、評価基準値更新、経路評価値算出処理を終了する。

条件識別子が「２」または「５」に設定されている場合、更新部１０３は、直前の中継装置アドレスと同じ隣接装置アドレス２０２に関する最小測定値２０６を測定値管理テーブル２０１から取得する（ＳＴＥＰ８１０）。つぎに、更新部１０３は、受信した経路要求パケットに含まれる評価基準値（１）を取得する（ＳＴＥＰ８１１）。その後、更新部１０３は、受信した経路要求パケットに含まれる評価基準値（１）と最小測定値２０６とを比較する（ＳＴＥＰ８１２）。最小測定値２０６が評価基準値（１）より小さいと判定した場合（ＳＴＥＰ８１２でＹｅｓ）、更新部１０３は評価基準値（１）を最小測定値２０６の値に更新する（ＳＴＥＰ８０８）。一方、最小測定値２０６が評価基準値３０７より大きいと判定した場合、評価基準値（１）を更新しない。そして、更新部１０３は評価基準値（１）の値、あるいはその値を正規化した値などを経路評価値として算出する（ＳＴＥＰ８０９）。以上によって、評価基準値更新、経路評価値算出処理を終了する。

条件識別子が「３」に設定されている場合、更新部１０３は経路要求パケットが自装置に到達した時刻と評価基準値の時刻との時間差あるいはその時間差を正規化した値などを経路評価値として算出し（ＳＴＥＰ８０９）、処理を終了する。

条件識別子が「４」に設定されている場合、更新部１０３は受信した経路要求パケットに含まれる評価基準値（１）を取得して、その値をインクリメントする（ＳＴＥＰ８０４）。そして、更新部１０３は評価基準値（１）をインクリメントした値に更新する（ＳＴＥＰ８０８）。つぎに、更新部１０３はホップ数が小さくなるほど大きくなる値、例えばホップ数の逆数、あるいはその逆数を正規化した値などを経路評価値として算出し（ＳＴＥＰ８０９）、処理を終了する。

条件識別子が「６」に設定されている場合、更新部１０３は、受信した経路要求パケットに含まれる評価基準値３０７のうち評価基準値（１）をインクリメントする（ＳＴＥＰ８１３）。つぎに、更新部１０３は、直前の中継装置アドレスと同じ隣接装置アドレス２０２に関する最小測定値２０６を測定値管理テーブル２０１から取得する（ＳＴＥＰ８１４）。そして、更新部１０３は、受信した経路要求パケットに含まれる評価基準値３０７のうち評価基準値（２）を取得し（ＳＴＥＰ８１５）、最小測定値２０６と評価基準値（２）とを比較する（ＳＴＥＰ８１６）。最小測定値２０６が評価基準値（２）よりも小さいと判定した場合（ＳＴＥＰ８１６でＹｅｓ）、更新部１０３は、評価基準値（２）を最小測定値２０６に更新する（ＳＴＥＰ８０８）。そして、更新部１０３は、更新された評価基準値（１）、評価基準値（２）に対応する経路評価値（１）、経路評価値（２）を算出して（ＳＴＥＰ８０９）、処理を終了する。一方、最小測定値２０６が前記評価基準値（２）よりも大きいと判定した場合（ＳＴＥＰ８１６でＮｏ）、更新部１０３は評価基準値（１）に対応する経路評価値（１）、もとの評価基準値（２）に対応する経路評価値（２）を算出して（ＳＴＥＰ８０９）、処理を終了する。

一方、通信装置は、通信要求がないと判定した場合（ＳＴＥＰ５０１でＮｏ）、パケット保存部１０６により保存されている経路要求パケットのうち、タイマが満了している経路要求パケットがあるか否かを判定する（ＳＴＥＰ５１１）。通信装置は、タイマが満了している経路要求パケットがないと判定した場合（ＳＴＥＰ５１１でＮｏ）、ＳＴＥＰ５０１の処理を実行する。一方、通信装置は、タイマが満了している経路要求パケットがあると判定した場合（ＳＴＥＰ５１１でＹｅｓ）、ＳＴＥＰ５１２の処理を実行する。

通信装置は、タイマが満了している経路要求パケットがあると判定した場合、その経路要求パケットの終点アドレスが自らのアドレスであるか否かを判定する（ＳＴＥＰ５１２）。その終点アドレスが自らのアドレスであると判定した場合（ＳＴＥＰ５１２でＹｅｓ）、通信装置は、始点装置に経路を返信するための返信用経路要求パケットを生成する（ＳＴＥＰ５１３）。この返信用経路要求パケットの生成処理は以下の通りである。まず、通信装置は、その終点アドレスが自らのアドレスである経路要求パケットにおいて、終点アドレスと始点アドレスを入れ替える。つぎに、通信装置は、その経路要求パケットの要求経路数を「０」に設定する。

返信用経路要求パケットを生成すると、通信装置は、重複管理テーブル４０１のタイマ状態４０４を「満了」に更新する（ＳＴＥＰ５１４）。そして、通信装置は、返信用経路要求パケットをユニキャスト送信し（ＳＴＥＰ５１５）、ＳＴＥＰ５１１の処理を実行する。

一方、その終点アドレスが自らのアドレスでないと判定した場合（ＳＴＥＰ５１２でＮｏ）、通信装置は、重複管理テーブル４０１のタイマ状態４０４を「満了」に更新する（ＳＴＥＰ５１６）。つぎに、通信装置は、パケット保存部１０６において保存されている経路要求パケットをブロードキャスト送信し（ＳＴＥＰ５１７）、ＳＴＥＰ５１１の処理を実行する。

　つぎに、本実施形態の具体例として、電力線通信（Ｐｏｗｅｒ　Ｌｉｎｅ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ、以下、「ＰＬＣ」という。）ネットワークに適用した例を、図９と図１０を用いて説明する。ただし、以下の開示の全てまたは一部は、例えば、無線ネットワーク等、他のネットワーク形式にも適用可能である。

　図９は本実施例におけるネットワークの構成を示す図である。本実施の形態のネットワークは、通信装置９０１～９０６で構成されている。説明の便宜上、通信装置９０１～９０６は、符号の順序に合わせて、アルファベット順にノードＡ～ノードＦと呼ぶことにする。さらに、通信装置９０１～９０６の各アドレスは、符号の順序に合わせて、アルファベット順にＡ～Ｆであるとする。ＰＬＣネットワークにおいては、各通信装置はＰＬＣモデムを指し、それぞれ他の装置との間で音声、動画または通常のデータなどを通信する。

　ＰＬＣネットワークにおいては、全ての通信装置は電力線により互いに物理的に接続されている。このため、電力線上を伝送されるデータ信号は距離減衰やノイズの影響を受け、通信装置の組み合わせによっては直接通信することができない。図９では、直接通信できる装置間を実線で接続して示している。また、実線毎に記載されている数値は、実線で接続されている２つの装置間で通信を行った場合に期待できる最新の帯域を示す。

　以下では、ノードＡが、直接通信できないノードＤとの間でデータ通信を開始する場合を例に挙げて説明する。ここで、ノードＡを始点ノード、ノードＤを終点ノードと呼ぶことにする。

　ノードＡは、通信されるデータ種別に応じた条件を指定して経路を探索する。本実施形態では、データ種別に応じた条件の一例として、以下の条件を用いる。音声データの場合は、始点ノードから終点ノード間で遅延が最小、またはホップ数が最小という条件を用いる。動画データの場合は、経路の最小保証帯域が最大という条件を用いる。通常のデータの場合は、経路の帯域が最大、または通信接続時間が長いという条件を用いる。

　図１０は、本実施の形態において、ノードＡからノードＤへデータ通信を要求し、ノードＡがノードＤへの経路を探索する際のシーケンス図である。図１０において、送信、受信を枠付きで表示した箇所は、各ノードでの送信、受信処理とその識別番号を示し、その間にある点線矢印はブロードキャストにより経路要求パケットが送信されたことを示す。点線矢印上に四角の枠で囲まれた記号と数字は、送信された経路要求パケットの内容を表し、それぞれ始点ノードから当該ノードまで通過したノードのアドレス（以降、通過ノードアドレスと呼ぶ）とその経路の評価基準値を表す。なお、経路要求パケットの送信先での×印は、そのノードの更新部１０３、重複検知部１０４、比較部１０５のいずれかが受信された経路要求パケットを破棄したことを表す。また、各ノードで経路要求パケットを受信してから送信するまでの太線は、凡例にも示すように、待機時間を表す。さらに、各ノードの受信を示す箇所の左下には、各ノードが受信して更新した経路要求パケットと先に受信してパケット保存部１０６により保存されていた経路要求パケットの両方の、通過ノードアドレスと、更新後の評価基準値が枠に囲まれて表示されている。そのうち、更新後にパケット保存部１０６により保存される経路要求パケットは実線枠に囲まれて表示されており、更新後に破棄される経路要求パケットは点線枠に囲まれて表示されている。最後に、終点ノードであるノードＤから出た一点鎖線の矢印は、始点ノードに対して返信用経路要求パケットをユニキャストで返信されたことを表す。

　ノードＡは、通信開始要求が発生した際に、図６に示された処理に基づき経路要求パケットを作成し、他のノードに送信する。以降、ノードＡが送信する経路要求パケットは、要求経路数が「１」、条件識別子が「１」、送信する経路要求パケット番号が「１２０」に設定されているとして、詳細を説明する。

　ノードＡが経路要求パケットを送信する（送信１）と、ノードＢ、Ｆ、Ｃは、その経路要求パケットを受信する（受信１、受信２、受信３）。ノードＢ、Ｆ、Ｃは、受信した経路要求パケットについて、図８に示された方法に基づき、評価基準値を更新し、経路評価値を算出する。まず、ノードＢ、Ｆ、Ｃは、受信した経路要求パケットの条件識別値が「１」に設定されているので、図２の測定値管理テーブル２０１より、ノードＡのアドレスであるアドレスＡと同じ隣接装置アドレス２０２の帯域に関する最新測定値２０３を取得する。ここで、各ノード間の最新の帯域は図９に示された通りであるので、ノードＢが取得する最新の帯域は１００、ノードＣが取得する最新の帯域は５、ノードＦが取得する最新の帯域は５０となる。つぎに、ノードＢ、Ｆ、Ｃは取得した最新の帯域をもとに、評価基準値と経路評価値を算出する。ここで、受信した経路要求パケットは初めて受信したものであり、かつそのパケットの条件識別値が「１」に設定されているので、算出される評価基準値と経路評価値は、最新測定値２０３と同じ値となる。それから、ノードＢは、受信した経路要求パケットの中継装置アドレスと評価用測定値に「Ｂ、１００」を追加し、評価基準値を「１００」に更新する（「受信１」の左下）。同様に、ノードＦは、受信した経路要求パケットの中継装置アドレスと評価用測定値に「Ｆ、５０」を追加し、評価基準値を「５０」に更新する（「受信２」の左下）。ノードＣは、受信した経路要求パケットの中継装置アドレスと評価用測定値に「Ｃ、５」を追加し、評価基準値を「５」に更新する（「受信３」の左下）。

　また、ノードＢ、Ｆ、Ｃは、重複管理テーブル４０１に、始点アドレス４０２として「Ａ」を、経路要求パケット番号４０３として「１２０」を記憶する。さらに、ノードＢ、Ｆ、Ｃは、前記のように算出される経路評価値に応じて経路要求パケットを送信するまでの待機時間を決定し、その待機時間のタイマを設定する。ここで、経路評価値が高いほど短い待機時間が設定されるので、ノードＢ、Ｆ、Ｃの順に短い待機時間が設定される。

　以下では、タイマが満了したノードが経路要求パケットを送信し、他のノードが２番目以降の経路要求パケットを受信する際の処理について述べる。

　最初にタイマが満了したノードＢは、保存していた経路要求パケットをブロードキャストする（送信２）。ノードＢが送信する経路要求パケットは、中継装置アドレスと評価用測定値が「Ｂ、１００」、評価基準値が「１００」に設定されている。

　ノードＡは、この経路要求パケットを受信する（受信１００）が、受信した経路要求パケットに含まれる始点アドレスが自らのアドレスであるため、受信した経路要求パケットを破棄する。この処理により、ループ経路が生成されることを防ぐとともに、無駄な経路要求パケットがブロードキャストされることを防ぐ。また、ノードＡは経路評価値の比較等の不要な判定を行わないので、処理負荷が軽減される。

　一方、ノードＦ、Ｃ、Ｅも、この経路要求パケットを受信する（受信４、５、６）が、受信した経路要求パケットの中継装置アドレスに自らのアドレスが含まれていないため、図８に示された方法に基づき、経路要求パケットを更新する。

ノードＥは、受信した経路要求パケットが最初の経路要求パケットであるため、前記と同様の処理により、受信した経路要求パケットの中継装置アドレスと評価用測定値に「Ｅ、５０」を加え、評価基準値を「３３」に更新する（「受信６」の左下）。そして、算出される待機時間に応じて、タイマを設定する。

ノードＦは、図２の測定値管理テーブル２０１より、直前の中継装置であるノードＢのアドレス（アドレスＢ）と同じ隣接装置アドレス２０２の帯域に関する最新測定値２０３（１００）を取得する。さらに、ノードＦは、この測定値（１００）と、評価用測定値３０９に記載されているノードＡとノードＢの間の帯域（１００）から、それぞれの逆数の和（１／１００＋１／１００＝１／５０）を求め、その逆数（５０）を新たな評価基準値として算出する。また、そのパケットの条件識別値が「１」に設定されているので、ノードＦは、経路評価値も５０として算出する。そして、ノードＦは、受信した経路要求パケットの中継装置アドレスと評価用測定値に「Ｆ、１００」を加え、評価基準値を「５０」に更新する（「受信４」の左下）。

つぎに、ノードＦは、受信した経路要求パケットの経路要求パケット番号３０４（１２０）と重複管理テーブル４０１の経路要求パケット番号４０３（１２０）が同じ番号であるので、受信した経路要求パケットが重複受信されたものであることを確認する。この場合、ノードＦは、最初に受信して保存されている経路要求パケットの経路評価値（５０）と、２番目に受信した経路要求パケットの経路評価値（５０）を比較する。要求経路数が「１」に設定されているため、ノードＦは、経路評価値が大きい経路要求パケットを保存し、経路評価値が小さい経路要求パケットを破棄する必要があるが、これら２つの経路要求パケットは経路評価値が等しい。そこで、ノードＦは、これらの経路要求パケットのうちホップ数がより少ない経路要求パケット、すなわち最初に受信した経路要求パケットをそのまま保存し、２番目に受信した経路要求パケットを破棄する（「受信４」の左下）。このように、経路評価値が同じ経路が複数ある場合、ホップ数の少ない経路を選択することにより、始点ノードから終点ノードへの通信時にパケットを中継する回数を少なくし、始点ノードから送信されたデータが終点ノードに届くまでの遅延時間を小さくすることができる。

同様に、ノードＣは、受信した経路要求パケットの中継装置アドレスと評価用測定値に「Ｃ、１１」を加え、評価基準値を「１０」に更新する（「受信５」の左下）。ノードＣにおいては、２番目に受信した経路要求パケットの経路評価値（１０）が最初に受信して保存されている経路要求パケットの経路評価値（５）より大きい。したがって、ノードＣは、中継装置アドレスと評価用測定値が「Ｂ、１００」、「Ｃ、１１」、評価基準値が「１０」である２番目に受信した経路要求パケットを保存する（「受信５」の左下）。

　つぎに、２番目にタイマが満了したノードＦが、中継装置アドレスと評価用測定値が「Ｆ、５０」、評価基準値が「５０」である、保存していた経路要求パケットをブロードキャストする（送信３）。ノードＡは、その経路要求パケットを受信する（受信１０１）と、受信した経路要求パケットに自らのアドレスが含まれているため、その経路要求パケットを破棄する。ノードＣ、Ｅは、そのパケットを受信する（受信７、受信８）と、保存するパケットを、受信した経路要求パケットに更新する。ノードＢはタイマ満了後に経路要求パケットを受信した（受信１０２）ので、これを破棄する。このように、各ノードはタイマ満了後に受信した経路要求パケットを破棄するので、各装置の処理負荷は軽減される。さらに、次の中継装置は、始点アドレスと終点アドレスが同じ経路要求パケットをタイマ満了後に処理する必要がなくなる。

　上記に述べた処理を繰り返すことにより、終点装置であるノードＤは、タイマ満了時に、中継装置アドレスと評価値が「Ｆ、５０」「Ｅ、２００」「Ｄ、２００」、経路評価値が「３３」である、２番目に受信した経路要求パケットを保存している（「受信１０」の左下）。ノードＤは、このパケットの終点アドレスと始点アドレスを入れ替え、要求経路数を「０」に設定した返信用経路要求パケットを生成し、もとの経路要求パケットが中継された逆の経路で始点ノードへユニキャスト送信する（送信６）。このように、終点ノードが最終的に決定した経路要求パケットを始点ノードに返信することにより、通信経路が設定される。

　以上説明したように、第１の実施形態によれば、タイマ１０７が最初の経路要求パケットの受信から所定の待機時間を設定し、重複検知部１０４が待機時間内に受信した経路要求パケットの中で重複して経路要求パケットを受信したかを判定する。重複受信している場合は比較部１０５で経路評価値が高い経路要求パケットを要求経路数だけ選択する。そして、送信部１０９が前記選択した経路要求パケットを隣接装置へ送信する。これにより、経路探索のために送信される経路要求パケットの数を削減して帯域の消費を抑えつつ、始点装置と終点装置との間において経路の状態を示す経路評価値が高い経路を作成することができる。

　また、タイマ１０７は、受信した経路要求パケットから算出した経路評価値に応じて待機時間を設定する。これにより、各装置が経路要求パケットを送信するタイミングを分散させることができるので、待機時間を固定した場合と比較して、各装置が送信する経路要求パケットが衝突する可能性を低くすることができる。

　さらに、タイマ１０７は、最初に受信した経路要求パケットから算出した経路評価値が低いほど待機時間を長く設定する。これにより、各装置は、始点装置との間の経路評価値が低い場合に、経路評価値が高い経路を介して他の経路要求パケットを受信する可能性を高くすることができるので、各装置が経路評価値の高い経路をより確実に探索することができる。

　また、始点装置が経路要求パケットの要求経路数を設定でき、中継装置は、経路要求数の数だけ経路要求パケットを送信する。これにより、例えば伝送路の状態が頻繁に変化している場合に、始点装置が作成する経路数を増やして全ての経路で通信ができなくなる可能性を低くすることができる。逆に、そうでない場合には、始点装置が作成する経路数を減らして経路作成のために送信されるパケット数を制限することができる。したがって、安定した通信の確保と帯域消費の抑制とを両立することができる。

なお、経路要求パケットのフォーマットは、以下に述べる拡張がされていてもよい。まず、経路上の各中継装置とその直前の中継装置との間で測定された通信の状態を全て保存しなくても、条件識別子３０６に対応する評価基準値３０７を算出することができる場合は、経路要求パケット３０１は評価用測定値３０９を含まなくてもよい。これにより、経路要求パケットのパケット長が短くなるので、経路要求パケットの送信により消費される帯域をより小さくすることができる。例えば、条件識別子が「２」「５」に設定されている場合、特定の通信の状態に関する経路上での最小値が評価基準値３０７となり、各中継装置は、自らの測定値とその最小値のうち、小さいものを新たな評価基準値３０７に置き換えていけばよいので、評価用測定値３０９として各通信装置間の通信の状態を加える必要はない。条件識別子が「３」に設定されている場合、始点装置が評価基準値３０７の値を設定した後、中継装置が評価基準値３０７を更新する必要がないので、評価用測定値３０９は必要ない。条件識別子が「４」に設定されている場合、始点装置が評価基準値３０７の値を０に設定した後、各中継装置が評価基準値３０７に１を加えていくだけなので、評価用測定値３０９は必要ない。さらに、条件識別子「６」に設定されている場合、条件識別子が「２」「５」に設定されている際に必要な評価基準値３０７が算出されればよいので、評価用測定値３０９は必要ない。したがって、条件識別子「１」～「６」のうち、「１」に設定されている場合にのみ、経路要求パケット３０１は評価用測定値３０９を必ず含み、その評価用測定値３０９は各中継装置とその直前の中継装置との間で測定された最新の通信帯域となる。

ただし、条件識別子３０６が「２」～「６」に設定されていても、経路要求パケット３０１は評価用測定値３０９を付加的に含んでいてもよい。また、経路要求パケット３０１は各中継装置間における特定の通信の状態を評価用測定値３０９として含む代わりに、評価基準値３０７を含まなくてもよい。この場合、各中継装置は、評価用測定値３０９の値をもとに評価基準値３０７を計算する。

また、条件識別子３０６が「２」、「６」に設定されている場合、経路要求パケット３０１は評価用測定値３０９として、最小測定値２０６ではなく、最新測定値２０３を含む態様であってもよい。これにより、経路評価値が等しい経路要求パケットが複数受信された場合に、経路全体を通じた最新の帯域を算出して、次の選択基準として使用することもできる。

さらに、条件識別子３０６は前記に示した６種類にとどまらない。例えば、条件識別子「１」「２」に加えて、過去の通信状態の履歴に基づいて帯域の平均値を加えた態様でも構わない。条件識別子「３」に加えて、各装置の測定部１０２で自装置と隣接装置との間で送信されるＨｅｌｌｏパケットに送信時刻を付加して、定期的に遅延時間を測定し、過去の一定時間内での平均値もしくは最大値を求め、経路要求パケットが通過した経路上の各中継装置間でのそれらの総和を算出し、評価基準値とした態様でも構わない。条件識別子「５」においても、過去の通信状態の履歴に基づいて、通信継続時間の平均値もしくは最小値を利用した態様でも構わない。

さらに、始点装置が複数の条件の組み合わせから最適な経路を探索する態様でもよい。その場合、始点装置は、経路要求パケット３０１の条件識別子３０６に複数の条件を表す識別子を、評価基準値３０７にそれらの条件に対応する複数の経路の状態を示す値を設定する。ただし、各装置が複数の条件の優先順位が識別できること、各装置が評価基準値３０７に設定される各評価基準値が各条件識別子のどれに対応しているか識別できること、の２つの要件を満たす必要がある。この要件を満たすために、例えば、条件識別子３０６には、前記複数の条件のうち、優先される条件の順に条件識別子が設定され、評価基準値３０７には、優先される条件の順に、対応する評価基準値を順に設定されるとよい。この設定方法において、最新の通信状態に基づき帯域が最大となり、かつ複数の経路で帯域の値が同じ場合にホップ数が少ない経路を探索する場合、条件識別子３０６は、「１」「４」の順に設定される。また、評価基準値３０７に評価基準値（１）と評価基準値（２）の２つの領域が確保され、評価基準値（１）には経路上の各中継装置間における最新の通信状態をもとに推定される、始点装置から自装置までの通信帯域が格納され、評価基準値（２）にはホップ数が格納される。さらに、評価基準値（１）に対応する評価用測定値３０９である評価用測定値（１）も合わせて確保され、評価用測定値（１）には各中継装置とその直前の中継装置との間で測定された最新の通信帯域が格納される。

さらに、第１の実施形態では、経路要求パケットの要求経路数が「１」より大きい場合、送信部１０９は複数の経路要求パケットの内容をまとめて記述して送信してもよい。

　（第２の実施形態）
　上記第１の実施形態では、各装置が最初に受信した経路要求パケットによって待機時間を設定し、それ以降は待機時間を更新しないとしていた。しかし、最初に受信した経路要求パケットによって設定された待機時間が必ずしも適切ではない場合もある。例えば、設定した待機時間が長すぎる場合、各中継装置が経路要求パケットを送信するまでの待機時間が長くなり、経路が設定されるまで長い時間を要する。その結果、データの通信開始が遅れてしまう。一方、設定した待機時間が短すぎる場合、待機時間経過後により高い経路評価値を有する経路要求パケットを受信しても、破棄してしまう可能性が高まる。

　そこで、第２の実施形態では、経路評価値が高い経路を出来るだけ早く設定するため、通信装置は、受信した経路要求パケットの経路評価値がある条件を満たした場合に、最初に設定した待機時間を短縮する。あるいは、タイマの満了を待たずに、経路要求パケットを送信する例について説明する。

　図１１は、本発明の第２の実施形態に係る通信装置の機能ブロック図である。図１１は、図１と構成の数、種類は同じであるが、本実施の形態では、比較部１０５がタイマ１０７を更新したり、タイマ１０７の値を参照したりするため、比較部１０５とタイマ１０７が直接接続されている。

つぎに、本実施の形態について各構成の動作を説明する。図１１に示す本実施の形態の各構成は、比較部１０５の動作のみが異なる。比較部１０５は、第１の実施形態の動作に加えて、新しく受信した経路要求パケットと先に受信した経路要求パケットの待機時間、経路評価値、ホップ数を比較し、所定の条件のもと、タイマ１０７の待機時間の短縮、延長を実施する。また、比較部１０５は、始点装置及び終点装置が同一の経路要求パケットが所定の閾値の数だけ受信した場合、タイマ１０７に設定された待機時間を満了させる。

　また、本実施の形態における経路要求パケット３０１は、評価基準値３０７にホップ数を記載する領域として、評価基準値（０）が追加される。さらに、経路要求パケット３０１はタイマの満了時刻が延長されたことを示すフラグを含んでいてもよい。この場合、経路要求パケット内にタイマの満了時刻が延長されたことを示すフラグが立っていることを検知した他の装置のタイマ１０７は、その経路要求パケットを送信した装置が後から送信されるであろう経路評価値の高い経路要求パケットを受信するため、新たなタイマを設定するとよい。

以上のように構成された通信装置について、図１２～図１４を用いてその動作を説明する。図１２は、本実施の形態における各装置が実行する、経路要求パケットの受信処理を示すフローチャートである。なお、図１２では、で示した第１の実施形態における受信処理と同じ処理については、図７と同じ符号を付けている。ここでは、図７と相違する点について説明する。

ＳＴＥＰ１２０１は、図７のＳＴＥＰ７０３に対応する処理である。受信部１０１が経路要求パケットを受信すると、更新部１０３が評価基準値更新、経路評価値算出処理を行う（ＳＴＥＰ１２０１）。図１３は、ＳＴＥＰ１２０１の処理を示すフローチャートである。なお、図１３では、図８で示した第１の実施形態における評価基準値更新、経路評価値算出処理と同じ処理については、図８と同じ符号を付けている。ここでは、図８と相違する点について説明する。

ＳＴＥＰ８０３による条件識別子による処理の分岐の前に、更新部１０３は評価基準値（０）をインクリメントする（ＳＴＥＰ１３０１）。これは、第２の実施形態では、条件識別子に無関係に、ホップ数を経路探索に利用するためである。つぎに、更新部１０３は評価基準値の更新の際に、評価基準値（０）も他の評価基準値と併せて更新する（ＳＴＥＰ１３０２）。最後に、更新部１０３は、他の経路評価値に併せて、評価基準値（０）に関する経路評価値を第２の経路評価値として算出する（ＳＴＥＰ１３０３）。第２の経路評価値はホップ数をもとに算出されるので、更新部１０３はホップ数が小さくなるほど大きくなる値、例えばホップ数の逆数、あるいはその逆数を正規化した値などを経路評価値として算出する。以降の説明では、第２の経路評価値以外の経路評価値を第１の経路評価値と呼ぶことにする。なお、この第１の経路評価値は、第１の実施形態での経路評価値と同じである。

なお、本実施の形態では、経路要求パケットの評価基準値（０）にホップ数が格納されているため、条件識別子が「４」、「６」のときは、評価基準値（０）の値を評価基準値（１）の代わりに利用してもよい。したがって、図１３にも点線で示したように、ＳＴＥＰ８０４やＳＴＥＰ８１３の処理は省略し、以降の処理において評価基準値（０）の値を利用してもよい。

以上の評価基準値更新、経路評価値算出処理（図１２のＳＴＥＰ１２０１）を更新部１０３が終了すると、重複検知部１０４が重複受信した経路要求パケットがタイマ満了前に受信されたものであると判定すると（ＳＴＥＰ７０９で「タイマ設定中」）、比較部１０５がタイマ変更処理を行う（ＳＴＥＰ１２０２）。図１４は比較部１０５が実行するタイマ変更処理を示すフローチャートである。

まず、比較部１０５は、始点アドレスと経路要求パケット番号が等しい経路要求パケットをいくつ受信したのかを示す受信経路要求パケット数をインクリメントする（ＳＴＥＰ１４０１）。この場合、受信経路要求パケット数を記憶するため、重複管理テーブル４０１の構成要素に、受信経路要求パケット数が追加されていることが望ましい。

続いて、比較部１０５は、受信経路要求パケット数が閾値以上であるか否かを判定する（ＳＴＥＰ１４０２）。この所定の閾値は、経路評価値の高い経路を作成するために十分な数の経路要求パケットを受信できる数である。この閾値は、典型的には各装置にあらかじめ格納されている。なお、始点装置が経路要求パケット３０１内にその閾値を別途格納してもよい。また、要求経路数３０５に対して閾値がその何倍にあたるかのみが各装置共通に設定されており、始点装置が定めた要求経路数３０５に応じて、各装置が閾値を算出してもよい。さらには、各装置が自らを中継する経路要求パケットを定常的に測定し、経路要求パケット数の最適な閾値を学習によって定める態様であってもよい。受信経路要求パケット数が閾値以上であると判定した場合（ＳＴＥＰ１４０２でＹｅｓ）、比較部１０５は先に設定したタイマを満了させ（ＳＴＥＰ１４０３）、タイマ変更処理を終了する。

一方、受信経路要求パケット数が閾値未満であると判定した場合（ＳＴＥＰ１４０２でＮｏ）、比較部１０５は受信した経路要求パケットの第１の経路評価値を取得する（ＳＴＥＰ１４０４）。つぎに、比較部１０５は取得した第１の経路評価値が、パケット保存部１０６が保存している全ての経路要求パケットにおけるいずれの第１の経路評価値よりも大きいか否かを判定する（ＳＴＥＰ１４０５）。

取得した第１の経路評価値がより大きいと判定した場合（ＳＴＥＰ１４０５でＹｅｓ）、比較部１０５は受信した経路要求パケットの第２の経路評価値を取得する（ＳＴＥＰ１４０６）。つぎに、比較部１０５は、取得した第２の経路評価値が、パケット保存部１０６が保存している全ての経路要求パケットにおけるいずれの第２の経路評価値よりも小さいか否かを判定する（ＳＴＥＰ１４０７）。

取得した第２の経路評価値がより小さいと判定した場合（ＳＴＥＰ１４０７でＹｅｓ）、比較部１０５は、取得した第１の経路評価値に基づいて待機時間を算出する（ＳＴＥＰ１４０８）。つぎに、比較部１０５は算出した待機時間に基づいて新しいタイマを設定し（ＳＴＥＰ１４０９）、タイマ変更処理を終了する。

取得した第２の経路評価値が、パケット保存部１０６が保存しているいずれかの経路要求パケットの第２の経路評価値以上であると判定した場合（ＳＴＥＰ１４０７でＮｏ）、比較部１０５は、取得した第１の経路評価値に基づいて待機時間を算出する（ＳＴＥＰ１４１３）。つぎに、比較部１０５は、算出した待機時間と、現在設定中のタイマの残り時間とを比較する（ＳＴＥＰ１４１４）。算出した待機時間が現在設定中のタイマの残り時間よりも短い場合、比較部１０５は、現在設定中のタイマを算出した待機時間に更新して（ＳＴＥＰ１４１５）、タイマ変更処理を終了する。一方、算出した待機時間が現在設定中のタイマの残り時間以上の場合（ＳＴＥＰ１４１４でＮｏ）、比較部１０５はそのままタイマ変更処理を終了する。

取得した第１の経路評価値が、パケット保存部１０６が保存しているいずれかの経路要求パケットの第１の経路評価値以下であると判定した場合（ＳＴＥＰ１４０５でＮｏ）、比較部１０５は取得した経路要求パケットの第１の経路評価値が、パケット保存部１０６が保存している全ての経路要求パケットにおけるいずれの第１の経路評価値よりも小さいか否かを判定する（ＳＴＥＰ１４１０）。取得した第１の経路評価値が、パケット保存部１０６が保存しているいずれかの経路要求パケットの第１の経路評価値と等しいと判定した場合（ＳＴＥＰ１４１０でＮｏ）、比較部１０５はそのままタイマ変更処理を終了する。

取得した第１の経路評価値がより小さいと判定した場合（ＳＴＥＰ１４１０でＹｅｓ）、比較部１０５は受信した経路要求パケットの第２の経路評価値を取得する（ＳＴＥＰ１４１１）。つぎに、比較部１０５は、取得した第２の経路評価値が、パケット保存部１０６が保存している全ての経路要求パケットにおけるいずれの第２の経路評価値よりも小さいか否かを判定する（ＳＴＥＰ１４１２）。取得した第２の経路評価値がより小さいと判定した場合（ＳＴＥＰ１４１２でＹｅｓ）、比較部１０５は、タイマを満了して（ＳＴＥＰ１４０３）、タイマ変更処理を終了する。一方、取得した第２の経路評価値が、パケット保存部１０６が保存しているいずれかの経路要求パケットの第２の経路評価値以上であると判定した場合（ＳＴＥＰ１４１２でＮｏ）、比較部１０５はそのままタイマ変更処理を終了する。

つぎに、第２の実施形態における発明を適用した具体例を図１５、１６を用いて説明する。図１５は本実施形態におけるネットワークの構成を示す図である。図１５では、図９と同様に、直接通信できる装置間を実線で接続して示している。また、実線毎に記載されている数値は、実線で接続されている２つの装置間で期待できる最新の通信帯域を示す。説明の便宜上、通信装置９０１～９０６は、符号の順序に合わせて、アルファベット順にノードＡ～ノードＦと呼ぶことにする。さらに、通信装置９０１～９０６の各アドレスは、符号の順序に合わせて、アルファベット順にＡ～Ｆであるとする。本実施例でも、ノードＡ（始点ノード）が、直接通信できないノードＤ（終点ノード）との間で通信されるデータ種別に応じた条件を指定して経路を探索する場合を例に挙げて以下説明する。

　図１６は、本実施の形態において、ノードＡからノードＤへデータ通信開始要求が発生し、ノードＡがノードＤへの経路を探索する際のシーケンス図である。図１６に示されている記号のうち、図１０と同じ形態で記されている記号は図１０と同じ内容を指す。図１６では、凡例に記された内容が図１０と異なる。まず、待機時間Ａは、最初に受信した経路要求パケットの経路評価値に基づいて設定された待機時間を指す。待機時間Ａの短縮時間は、図１４のＳＴＥＰ１４０３、もしくはＳＴＥＰ１４１５の処理により、待機時間Ａが短縮された時間長を指す。待機時間Ａの再短縮時間は、一度待機時間Ａが短縮された後、図１４のＳＴＥＰ１４０３、もしくはＳＴＥＰ１４１５の処理が再度されることにより、待機時間Ａの短縮時間に加えて、さらに待機時間Ａが短縮された時間長を指す。つぎに、待機時間Ｂは、図１４のＳＴＥＰ１４０９の処理により、新たに設定されたタイマの待機時間を指す。待機時間Ｂの短縮時間は、待機時間Ｂのタイマが設定された後、図１４のＳＴＥＰ１４０３、もしくはＳＴＥＰ１４１５の処理がされることにより、待機時間Ｂが短縮された時間長を指す。

　本実施例では、待機時間中に受信する経路要求パケット数の閾値（図１４のＳＴＥＰ１４０２の閾値）が「４」に設定されており、各中継装置はタイマが満了しなくても４番目の経路要求パケットを受信した時点で、その時点で保存している経路要求パケットを送信するものとする。

ノードＡは、データ通信開始要求が発生すると経路要求パケットを作成する。本実施例では、ノードＡが送信する経路要求パケット３０１は、経路要求パケット番号３０４が「１２０」、要求経路数３０５が「１」、条件識別子３０６が「１」に設定されている。また、評価基準値３０７の評価基準値（０）は、初期値として「０」が設定されている。評価基準値（１）は各中継装置が条件識別子に基づいて計算した経路評価値を記載する領域であり、初期値として「０」が設定されている。

ノードＡは経路要求パケットを送信すると（送信１）、ノードＢ、Ｆ、Ｃがその経路要求パケットを受信する（受信１、受信２、受信３）。ノードＢ、Ｆ、Ｃの各々は、受信した経路要求パケットに含まれている評価基準値（０）をインクリメントして「１」に更新する。つぎに、それらのノードは、受信した経路要求パケットの条件識別子が「１」に設定されていると判定すると、受信した経路要求パケットに含まれる中継ノードアドレスに自らのアドレスを、評価用測定値（１）に測定値管理テーブル２０１より取得したノードＡとの間の最新の通信帯域を追加する。さらに、経路要求パケットに含まれる評価基準値（１）を、測定値管理テーブル２０１から取得したノードＡとの間で通信を行う場合の最新の帯域に更新する。その後、評価基準値（１）に基づいて待機時間を算出し、タイマを設定する。このとき、ノードＢ、Ｆ、Ｃの各々のタイマは、ノードＢ、Ｆ、Ｃの順で待機時間が満了するように設定される。なお、図１６では、待機時間Ａと待機時間Ａの短縮時間を加えた時間がこの時点で設定される待機時間となる。

以下では、待機時間が満了したノードが経路要求パケットを送信し、他のノードが２番目以降の経路要求パケットを受信する際の処理について述べる。

最初に待機時間が満了したノードＢは、保存していた中継装置アドレスと評価用測定値（１）が「Ｂ、１００」、評価基準値（０）が「１」、評価基準値（１）が「１００」に設定された経路要求パケットをブロードキャストする（送信２）。

ノードＦ、Ｃ、Ｅの各々はこの経路要求パケットを受信する（受信４、受信５、受信６）。そして、それらのノードは、受信した経路要求パケットに含まれている評価基準値（０）をインクリメントして「２」に更新する。つぎに、それらのノードは、受信した経路要求パケットの条件識別子が「１」に設定されていると判定すると、受信した経路要求パケットに含まれる中継装置アドレスに自らのアドレスを、評価用測定値（１）に測定値管理テーブル２０１より取得したノードＢとの間の最新の通信帯域を追加する。また、ノードＦ、Ｃ、Ｅは、評価用測定値（１）に格納された値に基づいて当該経路で通信を行う場合の帯域を算出し、評価基準値（１）を算出した帯域に更新する。

その結果、ノードＦは、受信された経路要求パケットに含まれている評価基準値（０）を「２」に、評価基準値（１）を「３３」に、中継装置アドレスと評価用測定値（１）を「Ｂ、１００」、「Ｆ、５０」に更新する（「受信４」の左下）。ここで、ノードＦが２番目に受信した経路要求パケットは、評価基準値（１）が小さい、すなわち第１の経路評価値が小さいという条件を満たしている。さらに、その経路要求パケットは、ノードＦが最初に受信した経路要求パケットよりもホップ数が多い、すなわち第２の経路評価値も小さいという条件も満たしている。この場合、ノードＦは、タイマは満了していないが、重複管理テーブル４０１のタイマ状態４０４を「満了」に更新し、このタイミングで保存している最初に受信した経路要求パケットを送信する（送信３）。なお、図１６では、待機時間Ａの短縮時間が、これにより短縮された待機時間を示している。

ノードＣは、ノードＢが送信した経路要求パケットを受信した（受信５）後、受信した経路要求パケットに含まれる評価基準値（０）を「２」に、評価基準値（１）を「３３」に、中継装置アドレス３０８と評価用測定値（１）を「Ｂ、１００」、「Ｃ、５０」に更新する（「受信５」の左下）。ここで、２番目に受信した経路要求パケットは、評価基準値（１）が大きい、すなわち第１の経路評価値が大きいという条件を満たしている。さらに、その経路要求パケットは、ノードＣが最初に受信し保存している経路要求パケットよりもホップ数が多い、すなわち第２の経路評価値が小さいという条件を満たしている。この場合、ノードＣは、受信した経路パケットについても待機時間を算出し、算出した待機時間に基づいて２つ目のタイマを設定する。このとき、１つ目のタイマの満了時刻より、２つ目のタイマの満了時刻が遅くなるので、待機時間が延長される。なお、図１６では、待機時間Ｂと待機時間Ｂの短縮時間を加えた時間が２つ目のタイマが定める待機時間を示している。

なお、ノードＣは、１つ目のタイマの満了時刻にその時点までに保存されている経路要求パケットを一旦送信し（送信４）、２つ目のタイマの満了時刻に、１つ目のタイマの満了時刻後に受信し、保存されている経路要求パケットを送信する（送信６）。この場合、ノードＣは、重複管理テーブル４０１のタイマ状態４０４を、１番目のタイマ満了時点では「設定中」のままで更新せず、２番目のタイマ満了時点で「満了」に更新する。

その後、ノードＣは、ノードＦが送信した（送信３）経路要求パケットを受信し（受信７）、受信した経路要求パケットの評価基準値（０）を「２」に、評価基準値（１）を「９」に更新する（「受信７」の左下）。ノードＣは、受信した経路要求パケットの評価基準値（１）が２番目に受信した経路要求パケットの評価基準値（１）より低いため、この経路要求パケットを破棄する。

ノードＥは、ノードＢが送信した（送信２）経路要求パケットを受信する（受信６）と、その経路要求パケットは最初に受信された経路要求パケットであるため、経路要求パケットを更新して保存し、タイマを設定する。なお、図１６では、待機時間Ａと待機時間Ａの短縮時間と待機時間Ａの再短縮時間を加えた時間がこの時点で設定される待機時間となる。

それから、ノードＥは、ノードＦが送信した（送信３）経路要求パケットを受信し（受信８）、受信した経路要求パケットの評価基準値（０）を「２」に、評価基準値（１）を「５５」に更新する（「受信８」の左下）。ノードＥは、今回受信した経路要求パケットの第１の経路評価値が最初に受信した経路要求パケットの第１の評価基準値よりも高いため、今回受信した経路要求パケットについても待機時間を算出する。ノードＥは、今回算出した待機時間に基づくタイマの満了時刻が、既に設定されているタイマの満了時刻よりも早いため、今回算出した待機時間に基づくタイマの満了時刻にあわせて、タイマを更新する。なお、図１６では、待機時間Ａの短縮時間が、これにより短縮された待機時間を示している。

この後、ノードＥは、ノードＣが送信した（送信４）１回目の経路要求パケットを受信する（受信９）。そして、ノードＥは受信した経路要求パケットの評価基準値（０）を「３」に、評価基準値（１）を「２８」に更新する（「受信９」の左下）。ノードＥは、今回受信した経路要求パケットは、２回目に受信した経路要求パケットよりも評価基準値（１）が小さく、ホップ数が多いので、第１と第２の経路評価値がともに小さい。したがって、一度待機時間を短縮して設定したタイマの満了を待たずに、評価基準値（０）を「２」に、評価基準値（１）を「５５」に、中継装置アドレスと評価用測定値（１）を「Ｆ、７５」、「Ｅ、２００」に設定した経路要求パケットを送信する（送信５）。なお、図１６では、待機時間Ａの再短縮時間が、これにより短縮された待機時間を示している。

ノードＤは、ノードＣが送信した（送信４）１回目の経路要求パケットを受信する（受信１０）と、受信したパケットが最初の経路要求パケットであるため、経路要求パケットを更新して保存し、タイマを設定する。なお、図１６では、待機時間Ａと待機時間Ａの短縮時間を加えた時間がこの時点で設定される待機時間となる。つぎに、ノードＥが送信した（送信５）経路要求パケットを受信する（受信１２）と、受信した経路要求パケットの評価基準値（０）を「３」に、評価基準値（１）を「３５」に更新する（「受信１２」の左下）。後から受信した経路要求パケットの評価基準値（１）は最初に受信した経路要求パケットの評価基準値（１）よりも高いため、後から受信した経路要求パケットの第１の経路評価値は最初に受信した経路要求パケットの第１の経路評価値よりも高くなる。したがって、ノードＤは後から受信した経路要求パケットについても待機時間を算出する。しかし、後から算出した待機時間に基づくタイマの満了時間が既に設定されているタイマの満了時間よりも遅いため、ノードＤは、タイマを更新せず、保存する経路要求パケットを今回受信した経路要求パケットに更新する。

また、ノードＥが送信した（送信５）経路要求パケットを受信した（受信１１）ノードＣは、受信した経路要求パケットの評価基準値（０）を「３」に、評価基準値（１）を「４３」に更新して保存する（「受信１１」の左下）。ノードＣは、今回受信した経路要求パケットが４つ目の経路要求パケットであるため、２回目のタイマ満了を待たずに、保存している経路要求パケットを送信し（送信６）、重複管理テーブル４０１のタイマ状態４０４を「満了」に更新する。なお、図１６では、待機時間Ｂの短縮時間が、これにより２回目のタイマで当初設定していた待機時間より短縮された待機時間を示している。

ノードＣが２回目に経路要求パケットを送信する（送信６）と、ノードＤはそれを受信し（受信１３）、受信した経路要求パケットの評価基準値（０）を「４」に、評価基準値（１）を「３０」に更新する（「受信１３」の左下）。今回受信した経路要求パケットが２番目に受信した経路要求パケットよりも評価基準値（１）が小さく、ホップ数が多いので、第１と第２の経路評価値がともに小さくなる。したがって、ノードＤは、最初に設定したタイマの満了を待たずに、保存しているパケットの終点と始点アドレスを入れ替え、要求経路数を「０」に設定した経路要求パケットを生成し、もとの経路要求パケットが中継された逆の経路で始点ノードＡへユニキャスト送信する（送信７）。なお、図１６では、待機時間Ａの短縮時間がこれにより短縮された待機時間を示している。

　以上説明したように、第２の実施形態では、先に受信した経路要求パケットに基づいて設定した待機時間の満了時刻よりも、後に受信した経路要求パケットに基づいて設定した待機時間の満了時刻が早い場合は、通信装置はタイマ長を短縮する。これにより、先に受信した経路要求パケットから算出した経路評価値が低いため、長い待機時間が設定された後に、経路評価値の高い経路要求パケットを受信した場合でも、通信装置は経路評価値の高い経路要求パケットを早く送信できる。このため、自装置からの経路要求パケットの受信が間に合わず、次の中継装置が、他の装置から受信した経路要求パケットのみから選択し、送信してしまうことを防ぐことができる。したがって、経路評価値の高い経路要求パケットが次の中継装置に送信される可能性が高くなり、経路評価値の高い経路をより確実に作成することができる。

　また、第２の実施形態では、経路評価値の高い経路を作成するために十分な数である閾値を定め、その閾値以上の経路要求パケットを受信した場合、通信装置はこれまでに受信した経路要求パケットに基づいて設定した待機時間の満了を待たずに経路要求パケットを送信する。これにより、通信装置は、経路評価値の高い経路を作成するために十分な数の要求パケットを受信した時点で次の中継装置へ選択した経路要求パケットを送信することができる。したがって、自装置が経路要求パケットを送信するまでに次の中継装置が他の装置から受信した経路要求パケットのみから選択して送信することを防ぐことができるので、経路評価値の高い経路をより確実に作成することができる。

　さらに、２番目以降に受信した経路要求パケットから算出したホップ数がこれまでに受信した経路要求パケットから算出したホップ数よりも多く、かつ２番目以降に受信した経路要求パケットから算出した第１の経路評価値がこれまでに受信した要求パケットから算出した第１の経路評価値よりも低い場合、通信装置はこれまでに設定した待機時間の終了を待たずに経路要求パケットを送信する。このように、ホップ数が増加し、かつ第１の経路評価値が低下する場合、今後受信する経路要求パケットの経路はこれまでに受信した経路要求パケットの経路よりもホップ数が多くなり、第１の経路評価値が悪くなると考えられる。したがって、通信装置は、ホップ数が増加し、かつ第１の経路評価値が低下するとすぐに、経路要求パケットを送信することにより、不必要に待機時間を設定しなくなり、経路要求パケットを早く送信することができる。したがって、自装置が経路要求パケットを送信するまでに次の中継装置が他の装置から受信した経路要求パケットのみから選択して送信することを防ぐことができ、経路評価値の高い経路をより確実に作成することができる。

　一方、新たに受信した経路要求パケットから算出したホップ数がこれまでに受信した要求パケットから算出したホップ数よりも多く、かつ新たに受信した経路要求パケットから算出した第１の評価基準値がこれまでに受信した経路要求パケットから算出した第１の評価基準値より大きい場合、通信装置は待機時間を延長して他の要求パケットの受信を待つ。このように、ホップ数が増加し、かつ第１の経路評価値も増加する場合、今後受信する経路要求パケットの経路はこれまでに受信した経路要求パケットの経路よりもホップ数が多いが、経路評価値がよくなる可能性があると考えられる。したがって、通信装置は、延長前に設定した待機時間が満了した後に受信した、より経路評価値の高い経路要求パケットの送信漏れを減らすことができ、経路評価値の高い経路をより確実に作成することができる。したがって、これまでに受信した要求パケットに基づいて設定した待機時間が経過した時点で経路要求パケットを他の中継装置に送信し、その後で受信したさらに経路評価値の高い要求パケットを選択できなくなることを防ぐことができ、経路評価値の高い経路をより確実に作成することができる。

　なお、第２の実施形態では、説明の便宜上、経路要求パケット３０１に評価基準値（０）を新しく設けて、ホップ数を格納する態様で説明したが、他の経路評価値と識別できる態様であれば、どのような態様でも構わない。また、第１の実施形態と第２の実施形態が併用される場合には、それを識別するためのフラグが経路要求パケット３０１に別途含まれていてもよい。

　また、第２の実施形態では、タイマ設定が２回までの例しか挙げていないが、既に２回以上タイマ設定がされた後、新たに受信した経路要求パケットのホップ数が大きく、かつ経路評価値も大きい場合には、タイマ設定が３回以上されることもありうる。

また、第２の実施形態では、条件識別子が「１」の場合のみを説明したため、評価基準値（０）と（１）および評価用測定値３０９の評価用測定値（１）しか使用していないが、第１の実施の形態で挙げたように、複数の条件の組み合わせから最適な経路を探索する場合にも同様に適用することができる。この場合、評価基準値（２）以降および評価用測定値３０９の評価用測定値（２）以降が使用され、最も優先される経路評価値とホップ数を用いて同様の処理を行えばよい。ただし、条件識別子が「６」の場合のように、それぞれ異なる条件を満たす最適な経路を複数同時に探索する場合については、第３の実施の形態において詳細を説明する。

また、第２の実施形態においては、タイマ変更処理において以下の処理がなされていてもよい。まず、図１４のＳＴＥＰ１４０９の処理によって、タイマが複数設定された後に、ＳＴＥＰ１４０３、ＳＴＥＰ１４１５の処理が実行される場合においては、最先に起動したタイマのみを対象としてもよいし、起動している全てのタイマを対象としてもよい。あるいは、最初に設定したタイマが満了した後に起動中のタイマに対しては、ＳＴＥＰ１４０３、ＳＴＥＰ１４１５の処理を実行しなくてもよい。また、タイマが２回起動された後では、ＳＴＥＰ１４０９の処理を実行しなくてもよい。

また、第２の実施形態においては、比較部１０５は、新たに設定されるタイマの待機時間が満了するまでに受信した経路要求パケットが、先に送信した経路要求パケットよりも第１の経路評価値が高くならない場合は、ＳＴＥＰ７１１において受信した経路要求パケットをパケット保存部１０６に保存させなくてもよい。その場合、送信部１０９は、新たに設定されたタイマの待機時間が満了しても、先に送信した経路要求パケットに比べ、第１の経路評価値が同じもしくは低い経路要求パケットを送信しない。

また、第２の実施形態においては、比較部１０５は、先のタイマ満了時に経路要求パケットを送信した後、後のタイマが満了するまでに受信した経路要求パケットにおいて、その第１の経路評価値がある閾値よりも大きくなった場合や、先に送信した経路要求パケットの第１の経路評価値よりも一定の割合以上向上したときに、タイマを満了させてもよい。逆に、先のタイマ満了時に経路要求パケットを送信した後、後のタイマ満了までに受信した経路要求パケットにおいて、その第１の経路評価値がある閾値よりも小さくなった場合や、先に送信した経路要求パケットの第１の経路評価値よりも一定の割合以上低下したときに、タイマを満了させてもよい。その場合、送信部１０９は、後のタイマ満了を待たずにその経路要求パケットを送信する。

　（第３の実施形態）
つぎに、第３の実施形態について説明する。
本実施形態では、通信装置が、音声と動画データの両方の送信を開始したい場合など、送信遅延が最小となる経路と、最小帯域を保証する経路を同時に設定したい場合に、通信装置が行う処理について説明する。

　本実施形態では、各通信装置が、最初に受信した経路要求パケットを更新処理後すぐに送信する。そして、通信装置は、設定したタイマが満了した時点で、２番目以降に受信した経路要求パケットの中で経路評価値の高い経路、すなわち経路上の通信装置が測定した帯域の最小測定値が最大である経路に関する保存中の経路要求パケットを送信する。以下、図面を用いて本実施の形態について説明する。

　図１７は、本発明の第３の実施形態に係る通信装置の機能ブロック図である。図１７は、図１と構成の数、種類は同じであるが、本実施の形態では、タイマ１０７が重複でない経路要求パケットを受信すると、送信部１０９に経路要求パケットを送信させるため、タイマ１０７と送信部１０９が直接接続されている。

つぎに、本実施の形態について各構成の動作を説明する。図１７に示す本実施の形態の各構成は第１の実施の形態と殆ど同じであるが、タイマ１０７と送信部１０９の動作が異なる。

タイマ１０７は、第１の実施形態と同じ処理を終了した後、重複検知部１０４により出力された経路要求パケットを送信部１０９に出力する。送信部１０９は、タイマ１０７が出力した経路要求パケットをすぐにブロードキャストする。

　以上のように構成された通信装置について、図１８と図１９とを用いてその動作を説明する。図１８は、本実施の形態における通信装置が実行する、経路要求パケットの受信処理を示すフローチャートである。なお、図１８では、図７に示した第１の実施形態における受信処理と同じ処理については、図７と同じ符号を付している。ここでは、図７と異なる処理を説明する。

　図１８は、図７と異なり、ＳＴＥＰ７０８とＳＴＥＰ７１１との間に、ＳＴＥＰ１８０１が挿入されている。重複検知部１０４が最初の経路要求パケットであると判定した場合（ＳＴＥＰ７０５でＮｏ）、タイマ１０７がタイマを設定した（ＳＴＥＰ７０８）後、タイマ１０７が１番目送信フラグをＯＮにする処理を行う（ＳＴＥＰ１８０１）。

この１番目送信フラグは、受信した最初の経路要求パケットをすぐに送信するように送信部１０９に対して通知するためのフラグである。１番目送信フラグは、経路要求パケットを最初に受信した際にＯＮにされ、最初に受信した経路要求パケットを隣接装置に送信するとＯＦＦにされる。一番目送信フラグは、重複管理テーブル５０１の要素として追加されていてもよいし、他のメモリ空間にフラグの領域が確保されていてもよい。

その後、パケット保存部１０６は、受信した経路要求パケットを保存し（ＳＴＥＰ７１１）、保存経路数をインクリメントして（ＳＴＥＰ７１２）、ＳＴＥＰ７０１の処理が実行される。

　図１９は、本実施の形態の送信部１０９が実行する送信処理を示すフローチャートである。なお、図１９では、図５に示した第１の実施の形態における送信処理と同じ処理については、図５と同じ符号を付している。ここでは、図５と異なる処理を説明する。

　本実施の形態では、送信部１０９は、保存中の経路要求パケットのうち、タイマが満了している経路要求パケットがないと判定すると（ＳＴＥＰ５１１でＮｏ）、１番目送信フラグが受信処理においてＯＮにされているか否かを判定する（ＳＴＥＰ１９０３）。１番目送信フラグがＯＮでないと判定した場合（ＳＴＥＰ１９０３でＮｏ）は、送信部１０９はＳＴＥＰ５１１の処理を実行する。

　一方、１番目送信フラグがＯＮであると判定した場合（ＳＴＥＰ１９０３でＹｅｓ）、送信部１０９は経路要求パケットの終点アドレスが自らのアドレスであるか否かを判定する（ＳＴＥＰ１９０４）。経路要求パケットの終点アドレスが自らのアドレスであると判定した場合（ＳＴＥＰ１９０４でＹｅｓ）、送信部１０９は、始点装置に経路を返信するため、ＳＴＥＰ５１３と同じ処理によって返信用要求パケットを生成し（ＳＴＥＰ１９０５）、最初に受信した経路要求パケットをユニキャスト送信する（ＳＴＥＰ１９０６）。その後、送信部１０９は１番目送信フラグをＯＦＦに、送信した経路要求パケットの送信済みフラグをＯＮに変更して（ＳＴＥＰ１９０８）、ＳＴＥＰ５０１の処理を実行する。

この送信済みフラグとは、当該経路要求パケットが隣接装置に送信されたか否かを記憶するためのフラグであり、デフォルトではＯＦＦに設定され、一度送信されるとＯＮに設定される。送信済みフラグは、経路要求パケットを保存する領域に領域が確保されていてもよいし、パケット自体にフラグ領域が確保されていてもよい。

一方、経路要求パケットの終点アドレスが自らのアドレスでないと判定した場合（ＳＴＥＰ１９０４でＮｏ）、送信部１０９は最初の経路要求パケットをブロードキャスト送信する（ＳＴＥＰ１９０７）。その後、送信部１０９は１番目送信フラグをＯＦＦに、送信した経路要求パケットの送信済みフラグをＯＮに変更して（ＳＴＥＰ１９０８）、ＳＴＥＰ５０１の処理を実行する。

　送信部１０９は、パケット保存部１０６が保存している経路要求パケットのうち、タイマが満了している経路要求パケットがあると判定すると（ＳＴＥＰ５１１でＹｅｓ）、当該経路要求パケットを送信する。その際、送信部１０９は、図５のＳＴＥＰ５１５の替わりにＳＴＥＰ１９０１の処理を実行し、図５のＳＴＥＰ５１７の替わりにＳＴＥＰ１９０２の処理を実行する。ＳＴＥＰ１９０１において、送信部１０９は、パケット保存部１０６が保存している経路要求パケットのうち、送信済みフラグがＯＮでない、すなわち未送信の経路要求パケットのみをユニキャスト送信する。また、ＳＴＥＰ１９０２において、送信部１０９は、パケット保存部１０６が保存している経路要求パケットのうち、送信済みフラグがＯＮでない、すなわち未送信の経路要求パケットのみをブロードキャスト送信する。このように、送信部１０９が既に送信済みの経路要求パケットを再度送信しないようにすることで、経路要求パケットの送信により消費される帯域を小さくすることができる。

つぎに、第３の実施形態における発明を適用した具体例を図２０、２１を用いて説明する。図２０は本実施形態におけるネットワークの構成を示す図である。図２０では、図９及び図１５と同様に、直接通信できる装置間を実線で接続して示している。また、実線毎に記載されている数値は、実線で接続されている２つの装置間で通信帯域を一定期間測定した結果、測定値管理テーブル２０１に保存されている通信帯域の最小測定値２０３を示す。説明の便宜上、通信装置９０１～９０６は、符号の順序に合わせて、アルファベット順にノードＡ～ノードＦと呼ぶことにする。さらに、通信装置９０１～９０６の各アドレスは、符号の順序に合わせて、アルファベット順にＡ～Ｆであるとする。本実施例では、ノードＡ（始点ノード）が、直接通信できないノードＤ（終点ノード）との間で通信されるデータ種別に応じた条件を指定して経路を探索する。具体的には、経路要求パケットの条件識別子３０６が「６」に設定されていることとし、ノードＡが、ホップ数最小である経路と、当該経路で通信する場合の帯域の最小値が一定値以上であることを保証する経路を同時に探索する場合を例に挙げて説明する。

　図２１は、本実施の形態において、ノードＡからノードＤへデータ通信開始要求が発生し、ノードＡがノードＤへの経路を探索する際のシーケンス図である。図２１に示されている記号や数字は、図１０の内容と殆ど同じであるが、以下の点において異なる。

　図２１には、送信を枠付きで表示した箇所に、「Ａ送信」「Ｂ送信」の２種類の送信処理が示されている。また、噴出しで「満了時」と表示した処理も示されている。「Ａ送信」は、タイマの待機時間満了時に、パケット保存部１０６が保存している経路要求パケットをブロードキャストする処理を指す。したがって、「Ａ送信」は、第１の実施形態での送信処理と同じである。一方、「Ｂ送信」は各ノードが経路要求パケットを最初に受信したときに、更新処理をした後、すぐにブロードキャストする処理を指し、本実施形態での特有の処理である。「満了時」と噴出しで表示された箇所は、その時点でタイマは満了するが、「Ａ送信」で経路要求パケットを送信した後、受信した経路要求パケットは、「Ａ送信」で送信した経路要求パケットに比べ、経路評価値が低いため、後で受信した経路要求パケットを送信しなかったことを意味する。

　また、図２１には、図９にはない太枠で囲まれた記号と数字が存在する。この太枠は、最初に受信した経路要求パケットの内容であることを示す。さらに、全ての枠内の数字は、経路要求パケットの評価基準値（２）を指す。

　ノードＡは、データ通信開始要求が発生すると、図６に示された処理に基づき経路要求パケットを作成し、送信する。本実施の形態では、ノードＡが送信する経路要求パケットは、要求経路パケット数が「１」、条件識別子が「６」、経路要求パケット番号が「１２０」に設定されている。また、評価基準値（１）はホップ数を記載する領域であり、初期値として「０」が設定されている。評価基準値（２）は各中継装置が当該経路で通信する場合の帯域の最小値に関する経路評価値を記載する領域であり、初期値として「０」が設定されている。

　ノードＡが経路要求パケットを送信する（Ａ送信１）と、ノードＢ、Ｆ、Ｃの各々は、その経路要求パケットを受信する（受信１、受信２、受信３）。ノードＢ、Ｆ、Ｃにおいて、更新部１０３は、受信した経路要求パケットに含まれている評価基準値（１）をインクリメントして「１」に更新する。また、更新部１０３は、それぞれ受信した経路要求パケットの最後尾に中継装置アドレスとして自アドレスを格納する。その後、更新部１０３は、受信した経路要求パケットの条件識別子が「６」に設定されていることを判定すると、経路要求パケットに含まれる評価基準値（２）を、測定値管理テーブル２０１から取得した最小測定値２０６の値に更新する。例えば、ノードＢの更新部１０３は、受信した経路要求パケットの中継装置アドレスに「Ｂ」を追加し、評価基準値（１）を「１」に、評価基準値（２）を「１００」に更新する（「受信１」の左下）。ノードＦの更新部１０３は、受信した経路要求パケットの中継装置アドレスに「Ｆ」を追加し、評価基準値（１）を「１」に、評価基準値（２）を「５０」に更新する（「受信２」の左下）。ノードＣの更新部１０３は、受信した経路要求パケットの中継装置アドレスに「Ｃ」を追加し、評価基準値（１）を「１」に、評価基準値（２）を「５」に更新する（「受信３」の左下）。経路要求パケット更新後、それぞれの更新部１０３は、評価基準値（１）（２）に関する経路評価値を算出する。

　その後、ノードＢ、Ｆ、Ｃの各々の重複検知部１０４は、経路要求パケットの重複受信確認を行い、最初の経路要求パケットの受信であることを確認すると、最初に受信した経路要求パケットとその経路評価値をタイマ１０７に出力する。

タイマ１０７は、評価基準値（２）に関する経路評価値に基づいて待機時間を算出し、タイマを設定する。このとき、ノードＢ、Ｆ、Ｃの各々のタイマ１０７は、評価基準値（２）に関する経路評価値の大きい順、すなわちノードＢ、Ｆ、Ｃの順にタイマが満了するように設定する。その後、パケット保存部１０６がその経路要求パケットを保存する。タイマ１０７は、一番目送信フラグをＯＮにし、最初の経路要求パケットを受信したことを送信部１０９に通知する。

　以下では、各ノードが、受信した経路要求パケットを送受信する時の処理について述べる。まず、ノードＢは、中継装置アドレスが「Ｂ」、評価基準値（２）が「１００」の経路要求パケットをすぐにブロードキャストする（Ｂ送信１）。

　ノードＦ、Ｃ、Ｅの各々は、この経路要求パケットを受信する（受信４、受信５、受信６）。その後、ノードＦ、Ｃ、Ｅの各々の更新部１０３は、受信した経路要求パケットの中継装置アドレス３０８に自らのアドレスを追加する。その後、各々の更新部１０３は、受信した経路要求パケットの条件識別子が「６」に設定されていることを判定すると、評価基準値（１）、評価基準値（２）を更新する。その結果、ノードＦは、受信した経路要求パケットの中継装置アドレスに「Ｆ」を追加し、評価基準値（２）を「５０」へ更新する（「受信４」の左下）。ノードＣは、受信した経路要求パケットの中継装置アドレスに「Ｃ」を追加し、評価基準値（２）を「２０」へ更新する（「受信５」の左下）。ノードＥは、受信した経路要求パケットの中継装置アドレスに「Ｅ」を追加し、評価基準値（２）を「５０」へ更新する（「受信６」の左下）。

ノードＥは、経路要求パケットを最初に受信した（受信６）ので、受信した経路要求パケットを保存し、タイマを設定する。さらに、最初に受信した経路要求パケットを送信する（Ｂ送信４）。

一方、ノードＦ、Ｃは、受信した経路要求パケットが重複受信された（受信４、受信５）ものであるため、最初に受信して保存されている経路要求パケットの評価基準値（２）に関する経路評価値と、２番目に受信した経路要求パケットの評価基準値（２）に関する経路評価値とを比較する。比較の結果、ノードＣは、通過ノードアドレスが「Ａ：Ｂ：Ｃ」、評価基準値（２）が「２０」の２番目に受信した経路要求パケットを保存し、最初に受信した経路要求パケットを破棄する（「受信５」の左下）。また、ノードＦは、１番目と２番目に受信した経路要求パケットの評価基準値（２）が等しいため、評価基準値（１）が小さい最初に受信した経路要求パケットの保存を継続し、２番目に受信した経路要求パケットを破棄する（「受信４」の左下）。

同様にして、ノードＦ、Ｃは、「受信２」「受信３」において、最初に受信した経路要求パケットを送信する（Ｂ送信２、Ｂ送信３）。

その後、タイマが満了したノードが、保存している経路要求パケットのブロードキャストを行う。ノードＢは、タイマが満了した時点で保存している経路要求パケットを送信しようとするが、保存している経路要求パケットは最初に受信した経路要求パケットであり、既に送信しているため、経路要求パケットを送信しない（満了時１）。ノードＦ、Ｅも、それぞれタイマが満了した時点で保存している経路要求パケットが最初に受信した経路要求パケットであるため、経路要求パケットを送信しない（満了時２、満了時３）。一方、ノードＣは、タイマが満了した時点で３番目に受信した経路要求パケットを保存しているため、この３番目に受信した経路要求パケットを送信する（Ａ送信２）。このときノードＣが送信する経路要求パケットは、通過ノードアドレスが「Ａ：Ｆ：Ｃ」に、評価基準値（２）が「５０」に設定されている。

最後に、終点ノードであるノードＤも、他の中継装置と同様、最初に受信したホップ数最小の経路要求パケットを送信する（Ｂ送信５）。

このように、通信装置は、最初に受信したパケットをタイマの満了を待たずにすぐに送信することで、実施の形態１、２の場合と比較して、最初に経路を設定するまでにかかる時間を短縮することができる。

以上説明したように、第３の実施の形態によれば、通信装置は、最初に受信した経路要求パケットをすぐにブロードキャストする。そして、通信装置は、待機時間中に重複受信した経路要求パケットの中から同一始点装置から自装置までの経路評価値が高い経路要求パケットを経路設定数だけ選択し、ブロードキャストする。最初に受信した経路要求パケットはホップ数の少ない経路を中継されてきた可能性が高いため、通信装置は、最初に受信した経路要求パケットをブロードキャストすることでホップ数の少ない経路を作成することができる。それと同時に、通信装置は、タイマ満了後に経路評価値の高い経路要求パケットをブロードキャストすることで、経路評価値の高い経路を作成することができる。その結果、一度の経路作成処理によって異なる評価基準に基づいた経路が複数作成されるので、通信装置は、性質の異なる複数のデータを同時に送信したい場合などにおいて、経路を効率よく設定することができる。

なお、第３の実施の形態では、各装置が一番目送信フラグを設け、最初に受信した経路要求パケットを送信したか否かを管理する態様で説明したが、一番目送信フラグに代えて最初に受信した経路要求パケットを格納する領域を別途設けて、そこにデータが存在する場合、まだ最初に受信した経路要求パケットを送信していないと判定する態様でも構わない。

また、第３の実施形態は、第２の実施形態の処理を加えた態様でも構わない。例えば、図１８のＳＴＥＰ７０３の処理に代えて、図１２のＳＴＥＰ１２０１の処理が実行され、図１８のＳＴＥＰ７０９と７１０の処理の間に、図１２のＳＴＥＰ１２０２の処理が実行されてもよい。

（ハードウエアの構成例）
つぎに、本発明のハードウエア構成例について説明する。図２２は、通信装置のハード構成を示したハード図である。図２２において、通信装置は、各種の制御プログラムやワークエリアを含むメモリ２２０１、装置全体を制御するＣＰＵ（Ｃｅｎｔｒａｌ　Ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ）２２０２及びデータを通信するネットワークインタフェース２２０３から構成されている。通信装置は、メモリ２２０１に格納されているプログラムをＣＰＵ２２０２で実行し、ネットワークインタフェース２２０３を介してデータの送信を行い、ネットワークインタフェース２２０３を介して受信したデータをＣＰＵ２２０２で解読することにより受信する。ネットワークインタフェース２２０３は、ＰＬＣを利用する場合、電力線と接続され、電力線を介して各種データを通信する。また、無線通信を利用する場合、Ｗｉ－ＦｉやＭＡＮＥＴなどの各種無線通信方式を利用して各種データを通信する。

メモリ２２０１は、図２の測定値管理テーブル２０１、図４の重複管理テーブル４０１を格納する。また、第２の実施形態の受信経路要求パケット数、第３の実施形態の一番目送信フラグ、送信済みフラグを格納する。さらに、パケット保存部１０６で保存する経路要求パケットを一時的に格納する。

ＣＰＵ２２０２は、図１に示す機能ブロックを含み、第１の実施形態～第３の実施形態に示された各種処理を実行する。

　なお、本発明の各実施の形態において開示された各機能ブロックは、集積回路であるＬＳＩにより実現されてもよい。これらは個別に１チップ化されてもよいし、一部または全てを含むように１チップ化されてもよい。

このＬＳＩは、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩ、と呼称されることもある。

また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用プロセッサが利用されてもよい。あるいは、ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Ｆｉｅｌｄ　Ｐｒｏｇｒａｍｍａｂｌｅ　Ｇａｔｅ　Ａｒｒａｙ）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサが利用されてもよい。また、プロセッサやメモリ等を備えたハードウエア資源においてプロセッサがＲＯＭに格納された制御プログラムを実行する構成が用いられてもよい。

さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術等が適応され得る。

　本発明は、経路作成のために送信される経路要求パケットの数を削減して帯域の消費を抑えつつ、始点装置と終点装置との間において経路評価値の高い経路を作成できる。ゆえに、ＰＬＣネットワークや無線ネットワーク等、様々な種類のネットワークにおける通信装置及び通信方法に適用可能である。

　　１０１　受信部
　　１０２　測定部
　　１０３　更新部
　　１０４　重複検知部
　　１０５　タイマ
　　１０６　比較部
　　１０７　パケット保存部
　　１０８　パケット破棄部
　　１０９　送信部
　　９０１～９０６　通信装置
　　２２０１　メモリ
　　２２０２　ＣＰＵ
　　２２０３　ネットワークインタフェース

Claims

　通信を要求する始点装置が宛先となる終点装置へマルチホップで通信するにあたり、経路作成のための経路要求パケットを終点装置までの各中継装置へ送信する通信装置であって、
始点装置を示す情報、終点装置を示す情報、及び前記始点装置から自装置に前記経路要求パケットを直接送信した直前の中継装置までの経路状態を示す経路評価値を含む前記経路要求パケットを少なくとも１つの前記直前の中継装置から受信する受信部と、
前記受信した経路要求パケットに記述された前記始点装置から前記直前の中継装置までの経路状態と前記直前の中継装置と自装置との間の経路状態に基づいて、前記始点装置から自装置までの経路評価値を算出し、前記経路要求パケットの前記経路評価値を更新する更新部と、
前記経路要求パケットを受信すると受信時を含む所定の待機時間を設定し、前記始点装置及び前記終点装置を示す情報が前記受信した経路要求パケットと同一で前記待機時間内に更新した経路要求パケットの中から、前記経路評価値が高い順に所定数の経路要求パケットを選択し、自装置と直接通信できる隣接装置へ送信する制御部と、を具備する通信装置。
　自装置と前記隣接装置との間の通信に使用可能な帯域を複数のタイミングで測定する測定部をさらに備え、
　前記経路状態は、経路上の各通信装置間の通信に使用可能な帯域を通信装置間毎に含み、
　前記更新部は、前記経路要求パケットに記述された前記始点装置から前記直前の中継装置までの各通信装置間における使用可能な帯域と、前記測定部により測定された前記直前の中継装置と自装置との間の使用可能な帯域とに基づいて、前記始点装置から自装置までの経路全体で使用可能な帯域を前記経路評価値として算出し、経路全体で使用可能な帯域が大きいほど前記経路評価値を高い値として算出することを特徴とする請求項１記載の通信装置。
　自装置と前記隣接装置との間の通信に使用可能な帯域を複数のタイミングで測定し、前記測定された帯域の中から最小値を求める測定部をさらに備え、
　前記経路状態は、経路上の各通信装置間における使用可能な帯域の最小値を含み、
　前記更新部は、前記経路要求パケットに記述された前記始点装置から前記直前の中継装置までの最小値と、前記測定部により測定された前記直前の中継装置と自装置との間の最小値とを比較して、前記始点装置から自装置までの経路全体での最小値を前記経路評価値として算出し、前記算出された値が大きいほど前記経路評価値を高い値として算出することを特徴とする請求項１記載の通信装置。
　自装置と前記隣接装置との間で通信不能な状態から通信可能な状態に変化した最新の時点から現在までの経過時間を測定する測定部をさらに備え、
　前記経路状態は、経路上の各通信装置間における前記経過時間の最小値を含み、
　前記更新部は、前記経路要求パケットに記述された前記始点装置から前記直前の中継装置までの各通信装置間における前記経過時間の最小値と、前記測定部により測定された前記直前の中継装置と自装置との間の前記経過時間とを比較して、前記始点装置から自装置までの経路全体での前記経過時間の最小値を算出し、前記算出された値が大きいほど前記経路評価値を高い値として算出することを特徴とする請求項１に記載の通信装置。
　前記経路状態は、経路のホップ数を含み、
　前記更新部は、前記経路要求パケットに記述された前記始点装置から前記直前の中継装置までのホップ数に１を加えることにより、前記始点装置から自装置までの経路のホップ数を算出し、前記算出されたホップ数が少ないほど前記経路評価値を高い値として算出することを特徴とする請求項１記載の通信装置。
　前記経路状態は、経路のホップ数を含み、
　前記更新部は、前記経路要求パケットに記述された前記始点装置から前記直前の中継装置までのホップ数に１を加えることにより、前記始点装置から自装置までの経路のホップ数を算出し、前記算出されたホップ数が少ないほど第２の経路評価値を高い値として算出し、前記更新部により算出された前記経路評価値が等しい経路要求パケットが前記所定数以上ある場合、前記第２の経路評価値が高い順に前記所定数の経路要求パケットを選択することを特徴とする請求項１記載の通信装置。
　前記制御部は、前記経路要求パケットを受信すると、前記経路評価値に応じて前記所定の待機時間を設定することを特徴とする請求項１記載の通信装置。
　前記制御部は、前記経路評価値が低いほど前記所定の待機時間を長く設定することを特徴とする請求項７記載の通信装置。
　前記制御部は、これまでに受信した経路要求パケットに基づいて設定した前記所定の待機時間の終了時刻よりも、新たに受信した経路要求パケットに基づいて設定する待機時間の終了時刻が早い場合は、前記待機時間を短縮して、前記新たに受信した経路要求パケットに基づいて設定する待機時間の終了時刻で経路要求パケットを送信することを特徴とする請求項７記載の通信装置。
　前記制御部は、２番目以降の経路要求パケットを受信すると、これまでに受信した経路要求パケットの数が所定の閾値に達したかどうかを判定し、前記所定の閾値に達したと判定した時点で経路要求パケットを送信することを特徴とする請求項７記載の通信装置。
　前記経路状態は、経路のホップ数を含み、
　前記更新部は、前記経路要求パケットに記述された前記始点装置から前記直前の中継装置までのホップ数に１を加えることにより、前記始点装置から自装置までの経路のホップ数をさらに算出し、
　前記制御部は、前記更新部により算出されたホップ数がこれまでに受信した経路要求パケットから算出されたホップ数よりも多いという第１の条件と、新たに受信した経路要求パケットから算出された前記経路評価値がこれまでに受信した経路要求パケットから算出された前記経路評価値よりも低いという第２の条件を満たすか否か判定し、前記第１の条件と前記第２の条件をともに満たすと判定した時点で経路要求パケットを送信することを特徴とする請求項７記載の通信装置。
　前記制御部は、前記第１の条件を満たし、かつ前記第２の条件を満たさないと判定した場合、前記待機時間を延長し、新たに受信した経路要求パケットに基づいて設定した待機時間の終了時刻に経路要求パケットを送信することを特徴とする請求項１１記載の通信装置。
　前記制御部は、前記待機時間を延長する場合は、前記延長前の待機時間の終了時刻に、その時点で選択した経路要求パケットを送信し、さらに前記延長後の待機時間の終了時刻に、その時点で選択した経路要求パケットを送信することを特徴とする請求項１２記載の通信装置。
　前記制御部は、最初に受信した経路要求パケットを前記隣接装置に送信し、前記待機時間満了後に、前記受信した経路要求パケットと前記始点装置及び前記終点装置を示す情報が同一である他の経路要求パケットのうち、前記経路評価値が高い順に前記所定数の経路要求パケットを選択することを特徴とする請求項１記載の通信装置。
　前記制御部は、選択した経路要求パケットに記述された情報を１つの経路要求パケットにまとめて記述することを特徴とする、請求項１記載の通信装置。
　前記始点装置は、経路数を示す情報を前記経路要求パケットにさらに記述し、前記所定数が前記経路数であることを特徴とする請求項１記載の通信装置。
　前記制御部は、前記所定の待機時間の終了時刻経過後に受信した前記経路要求パケットを破棄することを特徴とする請求項１記載の通信装置。
　通信開始を要求する始点装置が宛先となる終点装置へマルチホップで通信するにあたり、経路作成のための経路要求パケットを終点装置までの各中継装置へ送信する通信方法であって、
始点装置を示す情報、終点装置を示す情報、及び前記始点装置から自装置に前記経路要求パケットを直接送信した直前の中継装置までの経路状態を示す経路評価値を含む前記経路要求パケットを少なくとも１つの前記直前の中継装置から受信し、
前記受信した経路要求パケットに記述された前記始点装置から前記直前の中継装置までの経路状態と前記直前の中継装置と自装置との間の経路状態に基づいて、前記始点装置から自装置までの経路評価値を算出し、前記経路要求パケットの前記経路評価値を更新し、
前記経路要求パケットを受信すると受信時を含む所定の待機時間を設定し、前記始点装置及び前記終点装置を示す情報が前記受信した経路要求パケットと同一で前記待機時間内に更新した経路要求パケットの中から、前記経路評価値が高い順に所定数の経路要求パケットを選択し、自装置と直接通信できる隣接装置へ送信する、通信方法。