(57)【要約】【課題】ノード間で通信データを伝送しているルートが使用できなくなったことをただちに検出し、検出されたルートが次のルート選択時には選択されないようにする。【解決手段】複数個のノードＮからなるマルチホップ通信ネットワークにおいて、通信品質取得手段１２が適時にハローメッセージを送信し、直接通信する隣接ノードＮとの間のリンクコストを求めて隣接ノードテーブルＴｂ１に登録する。通信データを伝送するルートは各ノードＮの隣接ノードテーブルＴｂ１に登録されたリンクコストを用いて選択される。選択されたルートを用いて通信データを伝送する際に、ルート上のノードＮが隣接ノードに通信データを送信した後に送信先のノードＮからの肯定応答を受信しなかった場合、評価値修正手段１５が送信元のノードＮの隣接ノードテーブルＴｂ１において送信先のノードＮとのノード間のリンクコストを大きくする。【選択図】図１
2008306314.tif 000002
【特許請求の範囲】
【請求項１】
複数個のノードを備えノード間での通信時に他のノードによる通信の中継を可能としたマルチホップ通信ネットワークにおいて他のノードによる中継なしに通信可能なノードである隣接ノードを確認する方法であって、各ノードは、自アドレスを含むハローメッセージを規定の時間間隔毎に送信しており、隣接ノードについてアドレスと通信品質とを対応付けて登録する隣接ノードテーブルを備え、隣接ノードのアドレスおよび通信品質の情報を含まない第１のハローメッセージを送信する通常モードと、隣接ノードテーブルから選択した隣接ノードのアドレスおよび当該隣接ノードからの受信方向の通信品質の情報を含む第２のハローメッセージを送信する確認モードとを有し、隣接ノードとの間の通信品質を確認することが必要になる事象が生じたときに通常モードから確認モードに移行し、確認モードでは、制限された送信回数内で第２のハローメッセージを送信した後に通常モードに復帰することを特徴とするマルチホップ通信ネットワークにおける隣接ノード確認方法。
【請求項２】
前記確認モードに移行する事象は、隣接ノードテーブルに隣接ノードの受信方向の通信品質のみの登録であることを特徴とする請求項１記載のマルチホップ通信ネットワークにおける隣接ノード確認方法。
【請求項３】
前記確認モードに移行する事象は、隣接ノードテーブルに登録されていないノードから自ノードのアドレスを含む第２のハローメッセージの受信であることを特徴とする請求項１記載のマルチホップ通信ネットワークにおける隣接ノード確認方法。
【請求項４】
前記確認モードに移行する事象は、隣接ノードテーブルに受信方向の通信品質のみが登録されているノードからの第２のハローメッセージの受信であることを特徴とする請求項１記載のマルチホップ通信ネットワークにおける隣接ノード確認方法。
【請求項５】
前記確認モードに移行する事象は、隣接ノードテーブルに受信方向と送信方向との通信品質が登録されているノードからのハローメッセージを受信しない状態が制限された送信回数に相当する時間継続していることであることを特徴とする請求項１記載のマルチホップ通信ネットワークにおける隣接ノード確認方法。
【請求項６】
前記確認モードに移行する事象は、ハローメッセージの受信時に検出される受信方向の通信品質と前記隣接ノードテーブルに登録されている受信方向の通信品質との差分が規定した許容範囲外となることであることを特徴とする請求項１ないし請求項５のいずれか１項に記載のマルチホップ通信ネットワークにおける隣接ノード確認方法。
【請求項７】
前記確認モードに移行する事象は、前記時間間隔に前記送信回数を乗じた時間よりも長い一定時間毎の時間経過であることを特徴とする請求項１ないし請求項６のいずれか１項に記載のマルチホップ通信ネットワークにおける隣接ノード確認方法。
【請求項８】
複数個のノードを備えノード間での通信時に他のノードによる通信の中継を可能としたマルチホップ通信ネットワークに用いるノードであって、自アドレスを含むハローメッセージを規定の時間間隔毎に送信する通信手段と、隣接ノードについてアドレスと通信品質とを対応付けて登録する隣接ノードテーブルと、ハローメッセージを受信したときに受信方向の通信品質を隣接ノードテーブルに登録する通信品質取得手段と、隣接ノードのアドレスおよび通信品質の情報を含まない第１のハローメッセージを送信する通常モードと隣接ノードテーブルに登録されている隣接ノードのアドレスおよび当該隣接ノードからの受信方向の通信品質の情報を含む第２のハローメッセージを送信する確認モードとの動作モードを備えるリンク確認手段と、隣接ノードから受信した第２のハローメッセージに自アドレスが含まれるときに当該第２のハローメッセージに含まれる送信方向の通信品質を隣接ノードテーブルに登録する通信品質登録手段とを備え、リンク確認手段は、隣接ノードとの間の通信品質を確認することが必要になる事象が生じたときに通常モードから確認モードに移行し、確認モードでは制限された送信回数内で第２のハローメッセージを送信した後に通常モードに復帰することを特徴とするマルチホップ通信ネットワークのノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信ネットワーク上に存在するノード間で通信する際に、他のノードによる通信の中継を可能にしたマルチホップ通信ネットワークにおいて、情報を伝送するノード間で適切なルートを選択するためのマルチホップ通信ネットワークにおける隣接ノード確認方法と、当該隣接ノード確認方法に対応したマルチホップ通信ネットワークのノードに関するものである。
【背景技術】
【０００２】
従来から、通信ネットワーク上に存在するノード（すなわち、通信端末）間で通信する際に、情報を伝送しようとするノード間で通信を直接行うことができない場合に、他のノードを通信の中継に用いることによって通信を可能にする技術が知られており、とくに通信ネットワークの一つである無線ネットワークにおいてこの技術を用いることが提案されている。この種の無線ネットワークは、マルチホップ無線ネットワークと呼ばれている。
【０００３】
無線ネットワークでは、ノードが移動したり雑音の影響を受けることにより、通信のルートの通信品質が時間経過に伴って変化する上に、通信可能であったノードとのルートが不通になって通信ネットワークのネットワークトポロジが時間経過に伴って変化するから、ノード間で通信を維持するには、ノード間で経路情報を交換し、使用可能なルートを探索するとともに使用可能なルートのうち通信品質のよいルートを選択することが必要である。
【０００４】
ところで、無線ネットワークにおける上述の問題は、電力線を伝送路に用いる電力線搬送通信（以下、「ＰＬＣ」（Power Line Communication）と略称する）の技術を用いて構築した通信ネットワークであるＰＬＣネットワークにおいても生じる。ＰＬＣネットワークの用途としては、たとえば、集合住宅において各住戸と管理室とにそれぞれノードを設置することによって、各住戸の設備機器を集中監視・制御するシステムが提案されている。
【０００５】
この種のシステムでは、電力線をルートに用いて高周波の搬送波信号を用いて情報を伝送するものであるから、搬送波信号には微弱な電力を用いており、集合住宅のように電力線の総延長が長くなると、各住戸に設置したノードから管理室のノードに対して通信を直接行うことができない場合が生じる。また、ＰＬＣネットワークはノードを電力線に接続するものであるから、電力線に接続された負荷機器により発生する雑音が通信品質に影響し、ノードを電力線のコンセントに接続する場合にはコンセントに対するノードの抜き差しによってネットワークトポロジが変化することになる。
【０００６】
したがって、ＰＬＣネットワークにおいても、マルチホップ無線ネットワークと同様に、他のノードを通信の中継に用いるとともに、ルートを探索し選択するマルチホップ通信ネットワークの技術が要求される。ＰＬＣネットワークにマルチホップ通信ネットワークの技術を適用した事例は知られている（たとえば、特許文献１参照）。
【０００７】
ところで、マルチホップ通信ネットワークでは、通信を開始する前にどのノードを通るルートを用いるかを探索して選択しなければならない。ルートの探索は、通信しようとする出発点のノードと到着点のノードとの間に存在する可能なルートを見つけ出す処理であり、ルートの選択は、可能なルートのうち通信品質が上位であるルートを選び出す処理である。
【０００８】
ルートを探索するには、まず他のノードの中継なしに通信することができるノードの対（言い換えれば、ノード間のリンク）を検出する必要がある。このようなリンクがわかれば、リンクを辿ることにより通信データの出発点と到着点とのノードを結ぶルートを追跡することができる。一方、ルートを選択するには、リンクごとの通信品質を評価する必要がある。すなわち、探索により得られたルートのうちで、通信品質が良好であるルートを採用するのが望ましいから、各リンクの通信品質を適宜の評価値で評価し、この評価値を用いて出発点から到着点までの通信品質を推定し、通信品質が良好なルートを選択するのである。
【０００９】
他のノードの中継なしに通信することができるノードの対を検出する技術としては、特許文献１において、各ノードが適時にハローメッセージと称する信号を送受信し、ハローメッセージをノードが受信することによって受信方向の通信品質を取得し、さらに受信側のノードから受信方向の通信品質を含むハローメッセージを送信することにより、送信側のノードに送信方向の通信品質を取得させる技術が示されている。
【特許文献１】特開２００６−６７５５７号公報
【発明の開示】
【発明が解決しようとする課題】
【００１０】
ところで、マルチホップ通信ネットワークではネットワークトポロジが時間経過に伴って変化しており、この変化は各ノードがハローメッセージを一定の時間間隔で送信し、他のノードがハローメッセージを受信することにより検出している。
【００１１】
ハローメッセージには、各ノードが自アドレスのみを送信する第１のハローメッセージと、他のノードからのハローメッセージを受信することにより得られる受信方向の通信品質および当該ハローメッセージを送信したノードのアドレスの情報を含む第２のハローメッセージとがある。
【００１２】
たとえば、ノードが通信ネットワークに新規に参入すると、既存のノードの第１のハローメッセージに応答して、新規に参入したノードが第２のハローメッセージを送信し既存のノードに対して通信品質を要求し、この要求を受信した既存のノードが第２のハローメッセージにより応答することによって、新規のノードと既存のノードとの間のリンクの品質を確認する。また、既存のノードにおいていずれかのノードが消失したり、他のノードとの間でハローメッセージが一方通行になる場合なども生じる。
【００１３】
このようなネットワークトポロジの変化に対応するために、他のノードの中継なしに通信可能な隣接ノードについて、ハローメッセージにより取得した通信品質と隣接ノードのアドレスとを隣接ノードテーブルに登録し、隣接ノードテーブルに登録されている隣接ノードのアドレスおよび通信品質の情報を含む第２のハローメッセージを適時に送信して通信品質の取得を要求し、要求に応答して送信された第２のハローメッセージにより通信品質を常時確認している。
【００１４】
したがって、通信ネットワークに隣接ノードのアドレスおよび通信品質の情報を含む第２のハローメッセージが頻繁に送信されることになり、トラフィックの増加につながっている。また、第１のハローメッセージと第２のハローメッセージを同一パケットに格納して送信することも可能であるが、パケットが長くなるため、やはりトラフィックが増加する。したがって、ネットワークトポロジの検出に用いる処理によって、本来のデータ通信に使用可能な帯域が狭められるという問題が生じる。
【００１５】
本発明は上記事由に鑑みて為されたものであり、その目的は、第２のハローメッセージの送信回数を従来よりも低減することにより、ハローメッセージによるトラフィックを低減し、本来のデータ通信に用いることができる帯域を広げることを可能としたマルチホップ通信ネットワークにおける隣接ノード確認方法、マルチホップ通信ネットワークのノードを提供することにある。
【課題を解決するための手段】
【００１６】
請求項１の発明は、複数個のノードを備えノード間での通信時に他のノードによる通信の中継を可能としたマルチホップ通信ネットワークにおいて他のノードによる中継なしに通信可能なノードである隣接ノードを確認する方法であって、各ノードは、自アドレスを含むハローメッセージを規定の時間間隔毎に送信しており、隣接ノードについてアドレスと通信品質とを対応付けて登録する隣接ノードテーブルを備え、隣接ノードのアドレスおよび通信品質の情報を含まない第１のハローメッセージを送信する通常モードと、隣接ノードテーブルから選択した隣接ノードのアドレスおよび当該隣接ノードからの受信方向の通信品質の情報を含む第２のハローメッセージを送信する確認モードとを有し、隣接ノードとの間の通信品質を確認することが必要になる事象が生じたときに通常モードから確認モードに移行し、確認モードでは、制限された送信回数内で第２のハローメッセージを送信した後に通常モードに復帰することを特徴とする。
【００１７】
請求項２の発明では、請求項１の発明において、前記確認モードに移行する事象は、隣接ノードテーブルに隣接ノードの受信方向の通信品質のみの登録であることを特徴とする。
【００１８】
請求項３の発明では、請求項１の発明において、前記確認モードに移行する事象は、隣接ノードテーブルに登録されていないノードから自ノードのアドレスを含む第２のハローメッセージの受信であることを特徴とする。
【００１９】
請求項４の発明は、請求項１の発明において、前記確認モードに移行する事象は、隣接ノードテーブルに受信方向の通信品質のみが登録されているノードからの第２のハローメッセージの受信であることを特徴とする。
【００２０】
請求項５の発明では、請求項１の発明において、前記確認モードに移行する事象は、隣接ノードテーブルに受信方向と送信方向との通信品質が登録されているノードからのハローメッセージを受信しない状態が制限された送信回数に相当する時間継続していることであることを特徴とする。
【００２１】
請求項６の発明では、請求項１ないし請求項５のいずれかの発明において、前記確認モードに移行する事象は、ハローメッセージの受信時に検出される受信方向の通信品質と前記隣接ノードテーブルに登録されている受信方向の通信品質との差分が規定した許容範囲外となることであることを特徴とする。
【００２２】
請求項７の発明では、請求項１ないし請求項６のいずれかの発明において、前記確認モードに移行する事象は、前記時間間隔に前記送信回数を乗じた時間よりも長い一定時間毎の時間経過であることを特徴とする。
【００２３】
請求項８の発明は、複数個のノードを備えノード間での通信時に他のノードによる通信の中継を可能としたマルチホップ通信ネットワークに用いるノードであって、自アドレスを含むハローメッセージを規定の時間間隔毎に送信する通信手段と、隣接ノードについてアドレスと通信品質とを対応付けて登録する隣接ノードテーブルと、ハローメッセージを受信したときに受信方向の通信品質を隣接ノードテーブルに登録する通信品質取得手段と、隣接ノードのアドレスおよび通信品質の情報を含まない第１のハローメッセージを送信する通常モードと隣接ノードテーブルに登録されている隣接ノードのアドレスおよび当該隣接ノードからの受信方向の通信品質の情報を含む第２のハローメッセージを送信する確認モードとの動作モードを備えるリンク確認手段と、隣接ノードから受信した第２のハローメッセージに自アドレスが含まれるときに当該第２のハローメッセージに含まれる送信方向の通信品質を隣接ノードテーブルに登録する通信品質登録手段とを備え、リンク確認手段は、隣接ノードとの間の通信品質を確認することが必要になる事象が生じたときに通常モードから確認モードに移行し、確認モードでは制限された送信回数内で第２のハローメッセージを送信した後に通常モードに復帰することを特徴とする。
【００２４】
なお、送信回数の制限は、送信回数を規定の最大回数に制限する場合と、送信回数を制限時間によって制限する場合とがある。
【発明の効果】
【００２５】
請求項１、８の発明の構成によれば、隣接ノードの存在を確認することが必要になる事象が生じたときに、制限された送信回数だけ第２のハローメッセージを送信するから、従来のように第２のハローメッセージをつねに送信する場合に比較すると、１回の送信当たりの平均のデータ長を短くすることができ、結果的に、制限を付けることなく第２のハローメッセージを送信する場合に比較して低トラフィック化が可能になる。
【００２６】
請求項２の発明の構成によれば、隣接ノードテーブルに隣接ノードの受信方向の通信品質のみが登録されているノードが、第２のハローメッセージを送信するから、第１のハローメッセージを受信して受信側の通信品質のみが隣接ノードテーブルに登録されているときに、ただちに送信側の通信品質の獲得を要求することができる。
【００２７】
請求項３の発明の構成によれば、隣接ノードテーブルに登録されていないノードから自ノードのアドレスを含む第２のハローメッセージを受信したノードが、第２のハローメッセージを送信するから、隣接ノードとして認識していなかったノードにリンク品質を通知し、相互に双方向の通信品質を取得することができる。
【００２８】
請求項４の発明の構成によれば、受信方向の通信品質のみが登録されているノードについて第２のハローメッセージの受信により送信方向の通信品質を取得することができる。さらに、受信方向と送信方向との双方向の通信品質を取得した後にも制限された送信回数内で第２のハローメッセージを送信するから、通信品質の変化にも対応することができる。
【００２９】
請求項５の発明の構成によれば、受信方向と送信方向との通信品質が登録されているノードであっても長時間に亘ってハローメッセージを受信しないときには、第２のハローメッセージを送信して当該ノードが隣接ノードとして存在しているか否かを確認することができる。また、当該ノードと通信できなくなったと判断した場合、第２のハローメッセージによってその棟が当該ノードにされるため、当該ノードもリンク断を認識でき、リンク状態の認識不一致を回避できる。
【００３０】
請求項６の発明の構成によれば、ハローメッセージの受信により検出された受信方向の通信品質が隣接ノードテーブルに登録されている通信品質に対して許容範囲を超えて変化したときには、通信品質を修正する必要があるから、第２のハローメッセージを送信することにより、最新の通信品質に更新することができる。
【００３１】
請求項７の発明の構成によれば、各ノードが一定時間毎に第２のハローメッセージを送信するから、隣接ノードとの間の通信品質の変動の有無を一定時間毎に検出することができ、隣接ノードとの間の通信品質の変動に対応して隣接ノードテーブルの内容を最新の通信品質に更新することができる。
【発明を実施するための最良の形態】
【００３２】
（基本構成）
マルチホップ通信ネットワークにおいて、通信データの出発点と到着点となるノードの間のルートを決めるには、他のノードの中継なしに直接通信が可能なノードの対を検出するとともに、対になる各ノード間のリンクにおける通信品質を評価することが必要である。また、通信データの出発点と到着点との間で取りうる通信経路（ルート）を探索し、通信可能なルートのうち通信品質の高いルートを選択することが必要である。
【００３３】
以下に説明する実施形態では、ルートの通信品質に関する評価に、隣接するノードが送信した信号の受信強度と、情報を伝送するルート内に含まれるノードについて隣接するノードを結ぶリンクの本数（以下、「ホップ数」と呼ぶ）とを用いる（ノードが隣接するとは、２つのノード間で他のノードによる中継なしに通信が可能であることを意味し、隣接ノードの間はホップ数が１である）。したがって、ホップ数は、ルートを構成するノード（ルートの両端のノードを含む）の個数から１を引いた値になる。ルートの通信品質は、信号強度が大きくホップ数が少ないほどよいと評価し、探索されたルートのなかで通信品質ができるだけよいルートを選択する。
【００３４】
たとえば、直接通信が可能なノード間の信号強度を複数段階（たとえば、１０段階）に分割してコード化した値（以下、このコードをＳＱ（Signal Quality）と呼ぶ）を用い、通信ネットワーク内における通信データを伝送する２ノード間の通信品質を、次式で求められるルートコストによって評価する。つまり、ルートコストが通信品質の評価値になる。
（ルートコスト）＝Ｋａ×（ルート内の各リンクに関するＳＱ値の総和）＋Ｋｂ×（ホップ数）
ただし、Ｋａ，Ｋｂは重み係数である。なお、以下では、Ｋｂ＝０の場合について説明する。
【００３５】
通信データの出発点と到着点となるノードの間に中継する２個のノードの存在するルートがあり、各リンクのＳＱが、それぞれ３、４、５であれば、ルートコストは、Ｋａ×（３＋４＋５）＋Ｋｂ×３＝１２・Ｋａ＋３・Ｋｂになる。
【００３６】
ところで、ルートコストのうち各リンクごとのＳＱ値に重み係数Ｋａを乗じた値は、直接通信が可能な互いに隣接ノードとなる２個のノード間のリンクに関する通信品質の評価値であって、以下ではこの評価値をリンクコストと呼ぶ。リンクコストは、通信する２個のノード間において、どちらのノードを送信側とするかによって変化することがあるから、相手ノードからの信号の受信強度により得られるリンクコスト（受信側の通信品質の評価値）を受信リンクコストと呼び、自ノードから〜の信号を相手ノードが受信したときの受信強度により得られるリンクコスト（送信側の通信品質の評価値）を送信リンクコストと呼ぶ。
【００３７】
各ノードは隣接ノードに関して受信リンクコストおよび送信リンクコストを相手ノードのアドレスに対応付けて登録する隣接ノードテーブルを備える。通信ネットワーク内の各リンクのリンクコストは、受信リンクコストと送信リンクコストとのうち値の大きいほうを用いる。つまり、各リンクのリンクコストを通信品質の悪いほうで評価する。
【００３８】
隣接ノードテーブルは、図６に示すように、隣接ノードごとに付与されているアドレス（隣接ノードアドレス）と、隣接ノードごとの受信リンクコストと、隣接ノードごとの送信リンクコストとの各項目を登録するフィールドを備える。ルートコストは上述した演算により求められたルートコストである。ただし、ルートに含まれる各リンクのリンクコストは重み係数Ｋａをすでに乗じてあるから、Ｋａ×（ルート内の各リンクに関するＳＱ値の総和）は、ルートに含まれる各リンクのリンクコストの総和によって求められる。上位コストについては後述する。なお、隣接ノードテーブルでは、実際には、上位コストに関するデータとして、ルート上のノードのアドレスとルートの各リンクのリンクコストとの情報を保持しているが、ここでは、説明を簡単にするために、上位コストをルート上のリンクコストの合計として扱いノードのアドレスについては考慮しない。
【００３９】
まず、隣接する２個のノードに着目してリンクコストを取得する動作を説明する。１個のノードに複数のノードが隣接する場合であってもリンクコストを取得する基本的な手順は同様である。リンクコストの取得には、通信データとは別に適宜の時間間隔で送信するハローメッセージを用いる。各ノードはハローメッセージに自アドレスを含めてブロードキャスト送信により送信する。
【００４０】
いま、図５に示すように、リンクコストを求める２個のノードＡ，Ｂに着目し、ノードＡが最初にハローメッセージを送信する場合を想定する。ノードＡからハローメッセージＨ１を送信すると、ノードＢがノードＡが送信したハローメッセージＨ１を直接受信できる場合には、ノードＢにおいて受信リンクコストを取得する。ノードＢが取得した受信リンクコストは、図６（ａ）のように、ノードＢの隣接ノードテーブルにおいて、ノードＡの隣接ノードアドレスに対応付けて登録される（ここでは、受信リンクコストが「８」）。ハローメッセージＨ１の送信は適時に行うが、通常は一定の時間間隔で定期的に行う。
【００４１】
次に、ノードＢでは、ハローメッセージＨ１の送信元であるノードＡのアドレスと受信リンクコストとを情報に含めたハローメッセージＨ２を送信する。このハローメッセージＨ２を受信したノードＡでは、ハローメッセージＨ２によってノードＢからの信号を受信したときの受信リンクコストを求めることができるから、図６（ｂ）のように、この受信リンクコストをノードＢのアドレスに対応付けて隣接ノードテーブルに登録する（ここでは、受信リンクコストが「５」）。また、ハローメッセージＨ２には、自アドレスと相手ノードＢがハローメッセージＨ１を受信したときの受信リンクコストとが含まれているから、この受信リンクコストをノードＡからノードＢへの送信リンクコストとしノードＢのアドレスに対応付けて隣接ノードテーブルに登録する（つまり、ノードＢに対する送信リンクコストは「８」）。
【００４２】
その後、ノードＡはふたたびハローメッセージＨ３を送信する。このハローメッセージＨ３は、ノードＢからハローメッセージＨ２を受信したときの受信リンクコストとノードＢのアドレスとを情報に含んでいる。したがって、ノードＢではハローメッセージＨ３に含まれる情報としてノードＡにハローメッセージＨ２を送信したときの送信リンクコストを取得することができる（つまり、ノードＡに対する送信リンクコストは「５」）。ノードＢでは、図６（ｃ）のように、ノードＡから受け取った受信リンクコストをノードＢからノードＡへの送信リンクコストとしノードＡのアドレスに対応付けて隣接ノードテーブルに登録する。
【００４３】
上述のように、互いに隣接ノードとなるノードＡ，Ｂの間では、ハローメッセージＨ１〜Ｈ３を３回送受信することにより、双方向のリンクコストを隣接ノードテーブルに登録することができる。また、上述の手順から明らかなように、３個のハローメッセージＨ１〜Ｈ３の送受信後には、隣接するノードの隣接ノードテーブルの内容は相補的な内容になる。ここに、相補的であるということは、一方の内容が失われても他方の内容を復元できることになる。
【００４４】
ところで、実際の通信ネットワークは、図７に示すように、多数個（図示例では７個）のノードＮ０〜Ｎ６を含んでいる。ノードＮ０〜Ｎ６は対等に扱うことが可能であるが、ここでは、１つのノードＮ０を親ノードとしたマスタースレーブ型の通信ネットワークを用いて説明する。マスタースレーブ型の通信ネットワークでは、親ノードＮ０を除く他のノードＮ１〜Ｎ６は子ノードであり、通信データを伝送するルートの一端は親ノードＮ０になり、他端はいずれかの子ノードＮ１〜Ｎ６になる。マスタースレーブ型の通信ネットワークでは、通信データを伝送するルートの一端になる子ノードＮ１〜Ｎ６を除く子ノードＮ１〜Ｎ６は、必要に応じて通信を中継する。各子ノードＮ１〜Ｎ６は親ノードＮ０との間に介在する子ノードＮ１〜Ｎ６の個数が多いほど（つまり、ホップ数が大きいほど）下位であるということができる。どの子ノードＮ１〜Ｎ６が親ノードＮ０との間のルートに含まれて中継を行うかは、以下に説明する手順で決められる。また、マスタースレーブ型の通信ネットワークは説明の都合上で用いるが、各ノードＮ０〜Ｎ６は対等な関係であってもよい。
【００４５】
上述したように、隣接するノードＮ０〜Ｎ６の間ではハローメッセージＨ１〜Ｈ３を３回送受信することにより、受信リンクコストと送信リンクコストとを取得することができる。
【００４６】
ここで、図７に示す通信ネットワーク（ネットワークトポロジは、リンクコストの取得途中で変化しないものとする）について考察する。マルチホップ通信ネットワークでは、隣接ノードテーブルにデータが登録されるまでは、中継なしに直接通信することができるノードＮ０〜Ｎ６が未知であるから、隣接ノードを探索するために送信するハローメッセージＨ１〜Ｈ３はブロードキャストで送信される。
【００４７】
すなわち、各ノードＮ０〜Ｎ６では、それぞれブロードキャストによってハローメッセージ（ハローメッセージＨ１に相当）を送信する。ただし、マスタースレーブ型の通信ネットワークであるから、親ノードＮ０からハローメッセージの送信を開始する。親ノードＮ０に隣接する子ノードＮ１，Ｎ２がハローメッセージを受信すると、子ノードＮ１，Ｎ２は、図５および図６を用いて説明した手順で親ノードＮ０との間で受信リンクコストおよび送信リンクコストを求める。
【００４８】
子ノードＮ１，Ｎ２が送信リンクコストを取得すると、各子ノードＮ１，Ｎ２はブロードキャストによってハローメッセージを送信する。親ノードＮ０は、受信リンクコストおよび送信リンクコストをすでに取得しているが、子ノードＮ１，Ｎ２が送信したハローメッセージ（ハローメッセージＨ１に相当）に応答する。このような動作を順次繰り返すことによって、各子ノードＮ１〜Ｎ６は隣接するノードとの間の受信リンクコストおよび送信リンクコストを取得し、隣接ノードテーブルに隣接ノードとの間の受信リンクコストおよび送信リンクコストを登録する。
【００４９】
子ノードＮ６を例として、受信リンクコストの取得後に送信リンクコストを取得するまでの手順をさらに詳しく説明する。子ノードＮ６は、隣接する子ノードＮ１，Ｎ３，Ｎ４，Ｎ５からハローメッセージを受信するから、図８に示すように、各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５ごとの受信リンクコストを隣接ノードアドレスに対応付けて隣接ノードテーブルに登録する。
【００５０】
ここで、各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５よりも上位のノードについては、それぞれが受信リンクコストと送信リンクコストを保有しているから、受信リンクコストと送信リンクコストとの大きいほうを当該子ノードＮ１，Ｎ３，Ｎ４，Ｎ５のリンクコストとし、上位の各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５のいずれかを通って親ノードＮ０に至るルートについて、各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５ごとにリンクコストの和の最小値を求める。このようにして求めた最小値を、各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５ごとの「上位コスト」と呼ぶ。この時点では、子ノードＮ６は、隣接する各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５との間の送信リンクコストを取得していないが、子ノードＮ１，Ｎ３，Ｎ４，Ｎ５では送信リンクコストをすでに取得して上位コストを決定しているのである。上位コストも隣接ノードテーブルに登録される。上述したように、上位コストに関する情報は、実際には、各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５から親ノードＮ０までのルート上の各ノードのアドレスと各リンクのリンクコストとの個々の情報として登録されており、上位コストを求めるにはルート上のリンクについてリンクコストの総和を求める。
【００５１】
いま、図７における各ノードＮ０〜Ｎ６の間で、子ノードＮ１，Ｎ３，Ｎ４，Ｎ５と子ノードＮ６との間を除いては送信リンクコストが決定され、その値が隣接するノードＮ０〜Ｎ５を結ぶ直線（リンク）に対応付けて表記した値であるものとする。また、子ノードＮ１，Ｎ３，Ｎ４，Ｎ５と子ノードＮ６との間では、ハローメッセージの検出によって、受信リンクコストのみが既知になっているものとする（図７において＊を付記した値は受信リンクコストである）。
【００５２】
図７によれば、子ノードＮ１，Ｎ３，Ｎ４，Ｎ５が送出したハローメッセージを子ノードＮ６が受信することにより取得される受信リンクコストは、それぞれ１５，２８，６，７であり、図８に示すように、子ノードＮ６の隣接ノードテーブルに、子ノードＮ１，Ｎ３，Ｎ４，Ｎ５のアドレスが隣接ノードアドレスとして登録されるとともに、それぞれの受信リンクコストが登録される。
【００５３】
図８の例では、各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５ごとの親ノードＮ０へのルートの中でリンクコストが最小になるのは、それぞれ親ノードＮ０、子ノードＮ１→親ノードＮ０、子ノードＮ２→親ノードＮ０（または子ノードＮ１→親ノードＮ０）、子ノードＮ３→子ノードＮ１→親ノードＮ０のルートであって、各ルートの送信リンクコストの総和（つまり、上位コスト）は、それぞれ１１，２０（＝１１＋９），３０（＝２０＋１０または＝１１＋９＋１０），１６（＝１１＋５）になる。
【００５４】
そこで、隣接する各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５と着目する子ノードＮ６との間の受信リンクコストと、隣接する各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５のそれぞれの上位コストとの加算値を、着目する子ノードＮ６から親ノードＮ０への送信リンクコストを反映する仮のルートコストとする。このようにして求めた仮のルートコストは、着目する子ノードＮ６の隣接ノードテーブルにおいて、隣接する各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５に対応付けて「ルートコスト」の項目に登録される。図８において、ルートコストに＊を付記しているのは、上位コストと受信リンクコストとによって求めた仮のルートコストであることを示す。
【００５５】
ところで、子ノードＮ６の隣接ノードテーブルにおいて送信リンクコストを求めるには、子ノードＮ６から隣接する各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５のそれぞれにハローメッセージを送信する必要がある。ただし、子ノードＮ６から親ノードＮ０へのルートが複数存在する場合には、リンクコストの総和がなるべく小さいルートを選択するのが望ましい。
【００５６】
上述した例では、着目する子ノードＮ６に隣接する子ノードＮ１，Ｎ３，Ｎ４，Ｎ５が４個あり、各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５を通って親ノードＮ０に至るルートについて、各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５ごとにそれぞれリンクコストの総和の最小値を上位コストとして求めているから、上位コストを求めた４種類のルートについて通信品質（リンクコスト）を比較すれば、着目する子ノードＮ６が親ノードＮ０に情報を送信するのに適したルートを選択することができると考えられる。
【００５７】
そこで、着目する子ノードＮ６から親ノードＮ０に向かうルートを仮のルートコストによって評価する。ここで、子ノードＮ６に隣接する４個の各子ノードＮ１，Ｎ３，Ｎ４，Ｎ５に対して、着目する子ノードＮ６からそれぞれハローメッセージを送信してもよいが、実際に用いるルートは１種類であるから、予備のルートを含めて通信品質の上位から適数個のルート（２ルート程度）を選択してハローメッセージを送信する。図８の例では、着目する子ノードＮ６に隣接する子ノードＮ１，Ｎ３，Ｎ４，Ｎ５のうち、仮のルートコストが上位の２番までになっているのが、子ノードＮ１と子ノードＮ５とであるから、この２個の子ノードＮ１，Ｎ５に対してのみ子ノードＮ６からハローメッセージ（図５のハローメッセージＨ２に相当）を送信する。
【００５８】
このハローメッセージを受け取った子ノードＮ１，Ｎ５は、ハローメッセージ（図５のハローメッセージＨ３に相当）を用いて子ノードＮ６に対して、子ノードＮ１，Ｎ５に登録した受信リンクコストを返送する。すなわち、図９のように、子ノードＮ６では子ノードＮ１，Ｎ５に対する送信リンクコストを取得することができる。このように送信リンクコストを取得した子ノードＮ１，Ｎ５を通って親ノードＮ０に至るルートについては、送信リンクコストと上位コストとを加算することによって、仮のルートコストではなく正式のルートコストを得ることができるから、ルートコストの値を更新する。すなわち、図９のように、送信リンクコストを取得したノードＮ１，Ｎ５に対しては正式のルートコストが求められ、他のノードＮ３，Ｎ４に対しては仮のルートコストが用いられる。
【００５９】
上述の手順によって、親ノードＮ０との通信を行う子ノードＮ６において、子ノードＮ１，Ｎ５が通信を中継する２つのルートについて正式のルートコストが得られる。正式のルートコストが得られていることは、隣接ノードについて受信リンクコストと送信リンクコストとの双方向のリンクコストが求められていることになるから、以下では、この状態を「２ＷＡＹ」と呼び、隣接ノードについて受信リンクコストのみが得られている場合を「１ＷＡＹ」と呼ぶ。また、リンクコストが得られていないか隣接ノードが消失した状態を「ＬＯＳＴ」と呼ぶ。
【００６０】
子ノードＮ６が親ノードＮ０と通信を行う際には、ルートコスト（親ノードＮ０に向かうリンクコストの総和）が最小であるルートを最良のルートとして選択する。このようなルートの探索および選択には、たとえば、ダイクストラ法などの最少リンクコストルート選択アルゴリズムを用いればよい。選択されたルートは、トポロジ通知メッセージを用いて親ノードＮ０に通知され、親ノードＮ０では子ノードＮ６までのルート情報を入手することができる。トポロジ通知メッセージは適時に送信すればよいが、通常は一定の時間間隔で定期的に送信される。
【００６１】
つまり、図９の例では、子ノードＮ５を通るルートについてルートコストが得られているから、子ノードＮ６→子ノードＮ５→子ノードＮ１→親ノードＮ０のルートを用いてトポロジ通知メッセージが送信される。このとき、子ノードＮ６は、子ノードＮ５だけではなく、正式のルートコストを求めた２個の子ノードＮ１，Ｎ５についてのルートコストをトポロジ通知メッセージに情報として含め、ユニキャストで子ノードＮ５に送信する。子ノードＮ５から親ノードＮ０までに経由する子ノードＮ１は、子ノードＮ５において既知であるから、子ノードＮ５は子ノードＮ６から受け取ったトポロジ通知メッセージの内容をユニキャストで子ノードＮ１に送信する。同様にして子ノードＮ１は親ノードＮ０に向かってトポロジ通知メッセージを送信する。親ノードＮ０では、受信したトポロジ通知メッセージの内容を用いて、子ノードＮ６との間のネットワークトポロジを把握する。
【００６２】
各子ノードＮ１〜Ｎ６の隣接ノードテーブルに受信リンクコストおよび送信リンクコストを登録するために用いられるハローメッセージは、図１０に示すように、送信元であるノードの自アドレスＳＩＤと、メッセージの種類を示すタイプＴＹと、送信元のノードの種類を示すノード種別ＮＣと、ハローメッセージの内容に応じて４種類から少なくとも１種類が選択されるサブメッセージＳＢ１，ＳＢ２，ＳＢ３，ＳＢ４とを有している。
【００６３】
ハローメッセージでは、タイプＴＹはハローメッセージを示し、ノード種別ＮＣはハローメッセージの送信元であるから親ノードの場合と子ノードの場合とがある。図５に示したハローメッセージＨ１，Ｈ２，Ｈ３はタイプＴＹは同じであるが、それぞれ異なるサブメッセージＳＢ１，ＳＢ２，ＳＢ３，ＳＢ４を有している。
【００６４】
サブメッセージＳＢ１は、各子ノードＮ１〜Ｎ６が親ノードＮ０との通信の際に形成するルートのホップ数（つまり、親ノードＮ０までのノード数）と、ルート上の各ノードのアドレスおよび各ノード間のリンクコストの情報を持ち、図５のハローメッセージＨ１の内容として下位の子ノードＮ１〜Ｎ６に伝送される。サブメッセージＳＢ１の内容を受信した下位の子ノードＮ１〜Ｎ６は上位コストを知ることができる。
【００６５】
サブメッセージＳＢ２は、隣接ノードについて受信リンクコストのみが得られている「１ＷＡＹ」の子ノードＮ１〜Ｎ６が、受信リンクコストが上位である適数個の隣接ノードについて、アドレスおよびリンクコスト（相手ノードの送信リンクコスト）の情報を持ち、図５のハローメッセージＨ２の内容としてハローメッセージＨ１の送信元である上位のノードに伝送される。
【００６６】
サブメッセージＳＢ３は、受信リンクコストと送信リンクコストとが得られている「２ＷＡＹ」のノードが、ハローメッセージＨ２により検出した受信リンクコストを相手側の子ノードＮ１〜Ｎ６に返送する際に用いる。つまり、下位の隣接ノードのアドレスおよびリンクコスト（相手ノードの送信リンクコスト）の情報をもち、図５のハローメッセージＨ３の内容として下位の子ノードＮ１〜Ｎ６に伝送される。
【００６７】
サブメッセージＳＢ４は、ハローメッセージによって隣接ノードの消失を検出したときに（上位ノードのハローメッセージに対して下位ノードの応答がないときに）消失した隣接ノードのアドレスを親ノードＮ０に向かって通知する際に用いられ、消失した隣接ノードのアドレスおよびリンクコストを情報に持つ。
【００６８】
したがって、各サブメッセージＳＢ１，ＳＢ２，ＳＢ３，ＳＢ４は、図１１に示すように、サブメッセージタイプＳＴＹにより４種類のサブメッセージＳＢ１，ＳＢ２，ＳＢ３，ＳＢ４を区別し、サブメッセージＳＢ１，ＳＢ２，ＳＢ３，ＳＢ４に含まれるノード数（サブメッセージＳＢ１では親ノードＮ０までのホップ数）ＬＮと、各ノードのアドレスＮＩＤおよびリンクコストＬＣとの情報を持つ可変長のフォーマットを有する。
【００６９】
上述のように、ハローメッセージＨ１には、送信元の子ノードＮ１〜Ｎ６から親ノードＮ０までのルート上のノードのアドレスおよびリンクコストが含まれるから、ハローメッセージＨ１を受信した下位の子ノードＮ１〜Ｎ６の隣接ノードテーブルには、図１２に示すように、親ノードＮ０までの各ノードごとに１ホップ目から順にリンクコスト（ＬＣ）およびアドレス（ＮＩＤ）が個別に保持される。このようなノードごとのリンクコストおよびアドレスが図６の上位コストの内容に相当する。また、図１２に示す隣接ノードテーブルでは、リンク状態（１ＷＡＹ、２ＷＡＹ、ＬＯＳＴ）を項目に備えている。リンク状態に相当する情報は、受信リンクコストと送信リンクコストとの情報の有無によっても知ることが可能である。
【００７０】
トポロジ通知メッセージは、図１３に示すように、メッセージの種類を示すタイプＴＹと、送信元のノードの種類を示すノード種別ＮＣと、３種類のサブメッセージＳｂ１，Ｓｂ２，Ｓｂ３とのフィールドを備える。つまり、トポロジ通知メッセージのフォーマットはハローメッセージとほぼ同様である。ただし、サブメッセージＳｂ１，Ｓｂ２，Ｓｂ３の内容は異なる。
【００７１】
トポロジ通知メッセージでは、タイプＴＹはトポロジ通知メッセージを示し、ノード種別ＮＣはトポロジ通知メッセージの送信元のノードであるから子ノードになる。
【００７２】
サブメッセージＳｂ１は、親ノードＮ０へのルートを示し、トポロジ通知メッセージの送信元である子ノード（上述の例では子ノードＮ６）を含めて、親ノードＮ０までのルートに含まれる子ノード（上述の例では、子ノードＮ６，Ｎ５，Ｎ１）のアドレスが順に並べられる。つまり、ハローメッセージにおけるサブメッセージＳｂ１とほぼ同様の内容になるが、自ノードのアドレスを含む点が相違する。
【００７３】
サブメッセージＳｂ２は、送信元の子ノード（上述の例では子ノードＮ６）に隣接する上位側のノードのうちルートコストを求めた子ノード（上述の例では子ノードＮ１，Ｎ５）のアドレスが並べられる。
【００７４】
サブメッセージＳｂ３は、隣接ノードであったノードのうち隣接ノードではなくなったノードのアドレスである。つまり、子ノード（上述の例では子ノードＮ６）から親ノードＮ０へのルートを形成しなくなった子ノードを親ノードＮ０に通知する。
【００７５】
各サブメッセージＳｂ１，Ｓｂ２，Ｓｂ３は可変長である。また、サブメッセージＳｂ１はトポロジ通知メッセージに必須であって省略することはできないが、サブメッセージＳｂ２，Ｓｂ３は省略することが可能である。
【００７６】
（実施形態）
本実施形態は、上述した基本構成に以下の機能を付加したものである。以下の説明では、基本構成と同様に、親ノードＮ０と子ノードＮ１〜Ｎ６とを備えるマスタースレーブ型の通信ネットワークを想定するが、以下に説明する技術は、マスタースレーブ型以外の通信ネットワークにおいても適用可能である。
【００７７】
ノードＮは、通信機能を備えるとともに後述する処理を行うマイクロコンピュータを備えた通信端末であって、図１に示すように、通信手段１１を備える。通信手段１１は、通信データを送受信するほか、ハローメッセージやトポロジ通知メッセージの送受信なども行っている。
【００７８】
ノードＮには、上述したように隣接ノードテーブルＴｂ１が設けられる。隣接ノードテーブルＴｂ１の内容は、上述したように、隣接ノードアドレス、受信リンクコスト、送信リンクコストなどであり、通信品質取得手段１２が通信手段１１を介して他のノードとの間でハローメッセージを送受信することにより、隣接ノードテーブルＴｂ１の内容が登録される。ハローメッセージには自アドレスが含まれる。
【００７９】
本実施形態では、たとえば、通信ネットワークに新規のノードＮが参入する場合、既存のノードＮとの間のリンクコストが変化した場合、既存のノードＮが消失した場合などに対応して隣接ノードテーブルＴｂ１のリンクコストを更新するものであり、そのため、サブメッセージＳＢ２，ＳＢ３，ＳＢ４を持たない（ただし、ＳＢ１はあってもよい）ハローメッセージＨａと、上述したいずれかのサブメッセージＳＢ２、ＳＢ３，ＳＢ４を持つハローメッセージＨｂ，Ｈｃ，Ｈｄとを用いる。以下では、サブメッセージを持たないハローメッセージを第１のハローメッセージＨａと呼び、サブメッセージＳＢ２を持つハローメッセージを第２のハローメッセージＨｂと呼ぶ。
【００８０】
ノードＮには、隣接ノードからの第１のハローメッセージＨａを通信手段１１が受信したときに、第１のハローメッセージＨａから受信リンクコストを求めて隣接ノードテーブルＴｂ１に登録する通信品質取得手段１２が設けられている。さらに、ノードＮには、隣接ノードとの間のリンクコストを確認するためのリンク確認手段１３が設けられる。リンク確認手段１３は、第１のハローメッセージＨａを送信する通常モードと、第２のハローメッセージＨｂを送信する確認モードとの２種類の動作モードを有している。リンク確認手段１３が通信手段１１を通して第２のハローメッセージＨｂを送信すると、隣接ノードに対してノードＮの自アドレスとともに隣接ノードから自ノードへの送信リンクコストを与えることができる。
【００８１】
ノードＮは、通信手段１１が受信した第２のハローメッセージＨｂに自ノードのアドレスが含まれているときに、自ノードに付随する送信リンクコストを隣接ノードテーブルＴｂ１に登録する通信品質登録手段１４も備える。リンク確認手段１３は、通信品質登録手段１４が自ノードのアドレスを含む第２のハローメッセージＨｂを検出したときに、サブメッセージＳＢ３，ＳＢ４を含むハローメッセージＨｃ，Ｈｄを送信する機能も備え、また通信品質登録手段１４は、ハローメッセージＨｃ，Ｈｄを受信したときに隣接ノードテーブルＴｂ１に対して後述する処理を行う機能を備える。
【００８２】
以下、ノードＮの動作を説明する。リンク確認手段１３が通常モードで動作しているときには、第１のハローメッセージＨａを一定時間毎に送信する。第１のハローメッセージＨａはサブメッセージを持たず（ただし、ＳＢ１だけ持つ場合もある）データ長が短いから通信ネットワークのトラフィックを大幅に増加させることがない。
【００８３】
一方、以下で説明する事象が生じたときには、リンク確認手段１３は確認モードに移行する。確認モード確認モードでは、隣接ノードテーブルＴｂ１に登録されている隣接ノードのうち規定の条件を満たす隣接ノードのアドレスおよび受信リンクコストを含む第２のハローメッセージＨｂを制限された送信回数内で送信する。制限された送信回数内で送信するとは、第２のハローメッセージＨｂの送信回数の最大値が制限されており、しかも第２のハローメッセージＨｂの送信後に当該ノードＮが隣接ノードから自アドレスを含むハローメッセージＨｃを受信すると、送信回数が最大値に達していなくとも第２のハローメッセージＨｂの送信を終了することを意味している。したがって、第２のハローメッセージＨｂの１回の送信に隣接ノードが応答してサブメッセージＳＢ３に自アドレスを含むハローメッセージＨｃを受信すると、第２のハローメッセージＨｂの送信を終了するが、ハローメッセージＨｃが得られなければ制限された送信回数の範囲内で第２のハローメッセージＨｂを繰り返して送信する。送信回数の制限は、回数自体で制限する場合と、有効期限を設定して時間により送信回数を制限する場合とがある。以下では、回数自体で送信回数を制限する場合について説明する。
【００８４】
リンク確認手段１３を確認モードに移行させて第２のハローメッセージＨｂを送信させる事象としては、自ノードが通信ネットワークに新規に参入した場合や新たな隣接ノードと通信可能になったような場合で、隣接ノードテーブルＴｂ１に受信リンクコストのみが登録されている場合（つまり、「１ＷＡＹ」）、ノードＮが「２ＷＡＹ」の状態であっても、ノードＮにおいて第１のハローメッセージＨａあるいは第２のハローメッセージＨｂの受信時に検出される受信リンクコストと隣接ノードテーブルＴｂ１に登録されている受信リンクコストとの差分が規定した許容範囲外になった場合、ノードＮにおいて規定した一定時間毎の時間が経過した場合などもある。
【００８５】
また、通信ネットワークの初期状態では、それぞれのノードＮが第１のハローメッセージＨａを送信するから「１ＷＡＹ」にはなるが、そのままでは第２のハローメッセージＨｂを送信しないから「２ＷＡＹ」にならない。したがって、「１ＷＡＹ」の隣接ノードのうち受信リンクコストが上位である（受信リンクコストを適宜の閾値と比較するのが望ましい）適数個のノードを選択し、これらのノードのアドレスおよび受信リンクコストの情報をサブメッセージＳＢ２に含む第２のハローメッセージＨｂを送信する。なお、一定時間毎に通常モードから確認モードに移行する場合は、第１のハローメッセージＨａや第２のハローメッセージＨｂを送信する時間間隔に第２のハローメッセージＨｂの送信回数の上限値を乗じた値よりも長い時間毎に、確認モードに移行させる。
【００８６】
このような動作により、隣接ノードとの間のリンクの通信状態が変化し、リンクコストが大きく変化した場合には第２のハローメッセージＨｂを送信してリンクコストを再確認することができる。また、リンクコストの大幅な変化がない場合でも定期的に第２のハローメッセージＨｂを送信することによって、隣接ノードとの間のリンクコストを再確認し、変化があれば最新のリンクコストに更新することができる。ここに、第２のハローメッセージＨｂは送信回数が制限されているから、通信ネットワーク上のトラフィックの増加を抑制することができる。
【００８７】
第２のハローメッセージＨｂの送信回数を制限するために、本実施形態における各ノードＮの隣接ノードテーブルＴｂ１には、図２に示すように、有効期限または送信回数の項目を設けておく（図では両方を記載しているが一方があればよい）。通常モードと確認モードの間のモード切り替えは、隣接ノード毎に行なってもよいし、有効期限が残っている、あるいは送信回数が１以上であるような隣接ノードが１台以上存在している間は確認モードになるよう一括管理してもよい。ところで、送信回数の制限内で隣接ノードからハローメッセージＨｃの応答が得られない場合、あるいは、一定時間内に隣接ノードからのハローメッセージＨａをまったく受信しない場合には、隣接ノードが通信不能になったと考えられる。隣接ノードが通信不能になるのは、隣接ノードが取り除かれるか故障するか通信品質が極端に低下した場合などが考えられる。
【００８８】
したがって、第２のハローメッセージＨｂを送信回数の制限内で複数回送信し、１回もハローメッセージＨｃの応答が得られない場合、あるいは、一定時間内に隣接ノードからのハローメッセージＨａを全く受信しない場合には、ネットワークトポロジに変化が生じ、隣接ノードが消失して隣接ノードの状態が「ＬＯＳＴ」に変化したと判断し、通信品質登録手段１４は、隣接ノードテーブルＴｂ１において当該隣接ノードのアドレスのみを残してリンクコストの情報を削除する。隣接ノードからのハローメッセージを全く受信しない場合でも、伝送路状態が片方向のみ通信不可能となっている場合には、ＬＯＳＴと判断された側の隣接ノードでは、ＬＯＳＴと判断したノードのハローメッセージを受信している可能性がある。すなわち、片側のノードでＬＯＳＴと判断し、他方のノードではリンクが正常に存在すると誤判断してしまい、リンク状態不一致が発生する。このため、隣接ノードが「ＬＯＳＴ」になったことを、当該隣接ノードおよび周辺のノードＮに通知する。
【００８９】
隣接ノードが「ＬＯＳＴ」になったことを周辺のノードＮに通知するために、基本構成で説明した「ＬＯＳＴ」のサブメッセージＳＢ４を有するハローメッセージＨｄを送信する。「ＬＯＳＴ」のサブメッセージＳＢ４を有するハローメッセージＨｄは、確認モードにおける送信回数の最大値となる複数回送信する。つまり、各ノードＮに対してネットワークトポロジの変化を確実に伝達する。仮に、サブメッセージＳＢ４を有するハローメッセージがＬＯＳＴと判断された側の隣接ノードに一度も届かない場合、当該隣接ノードにおいて、一定期間ハローメッセージを受信しない状態になるため、当該隣接ノードは、ＳＢ４を有するハローメッセージを送信したノードとの間のリンクをＬＯＳＴと判断することになり、この場合も結果的には双方がＬＯＳＴと認識し、状態の不一致を回避できる。
【００９０】
上述のように確認モードを設けて第２のハローメッセージＨｂを送信することによりノードＮの状態は、図３、図４のように変化する。  図３と図４とは同内容を示している。
【００９１】
図３の横列は隣接ノードテーブルＴｂ１の各ノードＮの現在の状態を示し、それぞれ「ＬＯＳＴ」（隣接ノードテーブルＴｂ１に隣接ノードとして情報が存在しない状態）、「１ＷＡＹ」（隣接ノードテーブルＴｂ１に隣接ノードの受信リンクコストのみが登録されている状態）、「２ＷＡＹ」（隣接ノードテーブルＴｂ１に隣接ノードの受信リンクコストと送信リンクコストとが登録されている場合）を示す。
【００９２】
また、図３の縦列は隣接ノードからのハローメッセージにより獲得した隣接ノードの情報であり、上から順に、第１のハローメッセージＨａを受信した場合、第２のハローメッセージＨｂを受信した場合、第２のハローメッセージＨｂに対する応答であって自アドレスを含むハローメッセージＨｃを受信した場合、「ＬＯＳＴ」のサブメッセージＳＢ４を含むハローメッセージＨｄであって自アドレスが含まれている場合、ハローメッセージを一定時間受信しない場合（この時間は、一定時間毎に確認モードに移行する場合の時間と同じでよい）を表している。
【００９３】
ノードＮの状態は、ハローメッセージの受信状態に応じて変化し、必要に応じて、第２のハローメッセージＨｂの送信回数と隣接ノードテーブルＴｂ１における隣接ノードの状態とを変化させる。図３において横列と縦列との交差する升目には、送信回数と隣接ノードの状態との変化を示している。図４では、ノードＮの現状態を三角形の頂点で表し、各辺にはハローメッセージの受信状態と送信回数の変化とを対応付けるとともに、各辺の→の向きで状態変化の方向を示している。ここで、送信回数には、０にするかセットするかの変化があり、送信回数をセットすればセットした回数を限度として第２のハローメッセージＨｂを複数回送信することが可能になる。また、送信回数を０にした場合には、第２のハローメッセージＨｂは送信せず通常モードになる。
【００９４】
まず、隣接ノードテーブルＴｂ１に隣接ノードとして登録されていないノード（「ＬＯＳＴ」のノード）について説明する。つまり、隣接ノードテーブルＴｂ１に登録されていないから、多くの場合は第１のハローメッセージＨａを受信することになる。この場合、送信回数を０にして当該隣接ノードを「１ＷＡＹ」として記録する。つまり、受信リンクコストのみが登録される。
【００９５】
一方、「ＬＯＳＴ」のノードから第２のハローメッセージＨｂあるいはハローメッセージＨｃを受信する場合もある。これは、自ノードが先にハローメッセージＨａを送信し、それを受信した隣接ノードがハローメッセージＨｂを送信してきた場合や、隣接ノードとして一度は登録されたことがあるが、その後のネットワークトポロジの変化などによって隣接ノードテーブルＴｂ１から削除されているような場合である。この場合は、双方向のリンクコストの情報が得られるから、当該隣接ノードを「２ＷＡＹ」にし、また、隣接ノードにリンク品質を通知する必要があるから、送信回数をセットする。
【００９６】
通信ネットワークの初期状態には、ノードは「１ＷＡＹ」になるから、そのうち受信リンクコストが上位のノードのアドレスおよび受信リンクコストをサブメッセージＳＢ２に含む第２のハローメッセージＨｂを制限された送信回数内で送信する。第２のハローメッセージＨｂを受信した隣接ノードおよび第２のハローメッセージＨｂに応答するハローメッセージＨｃを受信したノードは、隣接ノードテーブルＴｂ１を「２ＷＡＹ」に変更することができる。
【００９７】
ところで、「１ＷＡＹ」の隣接ノードから第２のハローメッセージＨｂを受信した場合には、送信回数をセットし、第２のハローメッセージＨｂを送信回数内で送信するとともに送信回数をデクリメントする。また、「１ＷＡＹ」の隣接ノードからハローメッセージＨｃを受信した場合には、以後の第２のハローメッセージＨｂの送信が不要になるから送信回数を０にする。
【００９８】
受信リンクコストと送信リンクコストとがともに登録されているノード（「２ＷＡＹ」のノード）については、「１ＷＡＹ」から「２ＷＡＹ」に移行する場合と同様であり、第２のハローメッセージＨｂを受信した場合は送信回数をセットし、隣接ノードからハローメッセージＨｃを受信した場合は送信回数を０にする。ただし、すでに「２ＷＡＹ」であるから、その状態は維持される。
【００９９】
ところで、「１ＷＡＹ」か「２ＷＡＹ」かにかかわらず、ハローメッセージを有効期限内に受信しないか（第２のハローメッセージＨｂを複数回送信したときに一度も応答がないか）、あるいは「ＬＯＳＴ」であるサブメッセージＳＢ４を含むハローメッセージＨｄを受信した場合には、当該隣接ノードを「ＬＯＳＴ」とする。以上の処理により、各隣接ノードの状態を適正に管理することができる。
【０１００】
上述した構成例は、従来構成において説明したＰＬＣネットワークに用いることを想定しているが、他の有線の伝送路を用いる通信ネットワーク、あるいは小電力無線による無線ＬＡＮのように無線の伝送路を用いる無線ネットワークなど、種々のマルチホップ通信ネットワークに上述の技術を適用してもよい。
【０１０１】
さらにいえば、ＰＬＣネットワークには、１０〜４５０ｋＨｚの低周波帯を利用する低速ＰＬＣと、２〜３０ＭＨｚの高周波帯を利用する高速ＰＬＣとが知られており、低速ＰＬＣのノードは、高速ＰＬＣより伝送速度が遅いから、上述の構成のように低トラフィックでもネットワークトポロジを把握できることはとくに有効であり、また、通信ネットワーク全体のリンクを各ノードが持たなくとも隣接ノードテーブルがあればよいから、ノードに実装するメモリの容量を小さくすることができる。しかも、他の有線の伝送路を用いる場合に比較すると、ＰＬＣでは各ノードとなる電気機器のオン／オフや稼働状態によってネットワークトポロジや通信品質が変化しやすいから、本発明の技術は有効である。
【図面の簡単な説明】
【０１０２】
【図１】実施形態に用いるノードを示すブロック図である。
【図２】同上に用いる隣接ノードテーブルの例を示す図である。
【図３】同上に用いるノードの状態変化を示す図である。
【図４】同上に用いるノードの状態遷移を示す動作説明図である。
【図５】ハローメッセージを示す動作説明図である。
【図６】ハローメッセージによる隣接ノードテーブルの変化を示す動作説明図である。
【図７】通信ネットワークの構成例を示す図である。
【図８】隣接ノードテーブルの一例を示す図である。
【図９】隣接ノードテーブルの一例を示す図である。
【図１０】ハローメッセージのフォーマットを示す図である。
【図１１】ハローメッセージにおけるサブメッセージの構成例を示す図である。
【図１２】隣接ノードテーブルの一例を示す図である。
【図１３】トポロジ通知メッセージのフォーマットを示す図である。
【符号の説明】
【０１０３】
１１  通信手段
１２  通信品質取得手段
１３  リンク確認手段
１４  通信品質登録手段
Ｈ１〜Ｈ３  ハローメッセージ
Ｈａ〜Ｈｄ  ハローメッセージ
Ｎ  ノード
Ｎ０〜Ｎ６  ノード
Ｔｂ１  隣接ノードテーブル
【図１】
2008306314.tif 000003
【図２】
2008306314.tif 000004
【図３】
2008306314.tif 000005
【図４】
2008306314.tif 000006
【図５】
2008306314.tif 000007
【図６】
2008306314.tif 000008
【図７】
2008306314.tif 000009
【図８】
2008306314.tif 000010
【図９】
2008306314.tif 000011
【図１０】
2008306314.tif 000012
【図１１】
2008306314.tif 000013
【図１２】
2008306314.tif 000014
【図１３】
2008306314.tif 000015