(57)【要約】【課題】故障診断装置及び方法、並びにバックオフ時間の設定方法を提供する。【解決手段】故障診断装置は、被疑ノードを診断する必要がある場合、診断ノードの被疑ノードに対するバックオフ時間を起動する時間起動手段であって、バックオフ時間は被疑ノードの複数の隣接ノードを異なるグループに分けることで設定されるものである、時間起動手段と、バックオフ時間をカウントダウンすることでルートノードを決定するルートノード決定手段であって、ルートノードは被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである、ルートノード決定手段と、診断ツリーを確立するようにルートノードを制御し、診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する診断制御手段と、を含む。【選択図】図１
2014217063.tif 000002
【特許請求の範囲】
【請求項１】
被疑ノードを診断する必要がある場合、診断ノードの前記被疑ノードに対するバックオフ時間を起動する時間起動手段であって、前記バックオフ時間は前記被疑ノードの複数の隣接ノードを異なるグループに分けることで設定されるものである、時間起動手段と、
前記バックオフ時間をカウントダウンすることでルートノードを決定するルートノード決定手段であって、前記ルートノードは前記被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである、ルートノード決定手段と、
診断ツリーを確立するように前記ルートノードを制御し、前記診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する診断制御手段と、を含む、故障診断装置。
【請求項２】
通信距離に基づいて、前記被疑ノードの複数の隣接ノードを複数の異なるグループに分けるグループ分け手段、をさらに含む、
請求項１に記載の故障診断装置。
【請求項３】
前記グループ分け手段は、通信距離に基づいて、前記被疑ノードの複数の隣接ノードを第１のグループと第２のグループとに分け、
前記第１のグループ内の隣接ノードと前記被疑ノードとの通信距離はＲ／２以下であり、前記第２のグループ内の隣接ノードと前記被疑ノードとの通信距離はＲ／２よりも大きく、前記Ｒは前記被疑ノードの通信範囲である、
請求項２に記載の故障診断装置。
【請求項４】
異なるグループのバックオフ時間により構成された時間範囲が互いに重ならないように、グループに基づいて前記バックオフ時間を設定する時間設定手段、をさらに含む、
請求項１乃至３のいずれかに記載の故障診断装置。
【請求項５】
前記時間設定手段は、下記の式
【数１】
2014217063.tif 000068
（ここで、ＢＯ１は、第１のグループの隣接ノードについて設定されるバックオフ時間であり、ＢＯ２は、第２のグループの隣接ノードについて設定されるバックオフ時間であり、ｔ１、ｔ２、ｔ３、ｔ４は所定の時間であり、ｔ０は前記診断ノードが前記被疑ノードの故障を検出したタイミングである）により前記バックオフ時間を設定する、
請求項４に記載の故障診断装置。
【請求項６】
【数２】
2014217063.tif 000069
となり、
Ｆ（Ｈｏｐ，ＮＮ）は値が［０，１］にある関数であり、前記Ｆ（Ｈｏｐ，ＮＮ）はノードのホップ数Ｈｏｐに正比例し、ノードの隣接ノードの数に反比例する、
請求項５に記載の故障診断装置。
【請求項７】
前記第１のグループに隣接ノードがない場合、前記第２のグループから前記第１のグループの隣接ノードとして１つの隣接ノードを選択し、前記選択された隣接ノードについて前記第１のグループに対応するバックオフ時間を設定するノード選択手段、をさらに含む、
請求項３に記載の故障診断装置。
【請求項８】
前記選択された隣接ノードに前記バックオフ時間を記憶させ、使用させるように、前記選択された隣接ノードへ前記バックオフ時間を送信する、時間送信手段、をさらに含む、
請求項７に記載の故障診断装置。
【請求項９】
前記診断制御手段は、検出用パケットをブロードキャストするように前記ルートノードをさらに制御し、
他の診断ノードは、バックオフ時間のカウントダウンが終了しておらず、且つ前記検出用パケットを受信した場合、バックオフ時間のカウントダウンを行わない、
請求項１に記載の故障診断装置。
【請求項１０】
被疑ノードを診断する必要がある場合、診断ノードの前記被疑ノードに対するバックオフ時間を起動するステップであって、前記バックオフ時間は前記被疑ノードの複数の隣接ノードを異なるグループに分けることで設定されるものである、ステップと、
前記バックオフ時間をカウントダウンすることでルートノードを決定するステップであって、前記ルートノードは前記被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである、ステップと、
診断ツリーを確立するように前記ルートノードを制御し、前記診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告するステップと、を含む、故障診断方法。
【請求項１１】
ノードの複数の隣接ノードを異なるグループに分けるステップと、
異なるグループの隣接ノードについて異なるバックオフ時間を設定するステップであって、異なるグループのバックオフ時間により構成された時間範囲が互いに重ならない、ステップと、を含む、バックオフ時間の設定方法。
【請求項１２】
ノードの複数の隣接ノードを異なるグループに分けるステップにおいて、通信距離に基づいて、ノードの複数の隣接ノードを複数の異なるグループに分ける、
請求項１１に記載のバックオフ時間の設定方法。
【請求項１３】
通信距離に基づいて、前記複数の隣接ノードを第１のグループと第２のグループとに分け、
前記第１のグループ内の隣接ノードと前記ノードとの通信距離はＲ／２以下であり、前記第２のグループ内の隣接ノードと前記ノードとの通信距離はＲ／２よりも大きく、前記Ｒは前記ノードの通信範囲である、
請求項１２に記載のバックオフ時間の設定方法。
【請求項１４】
下記の式
【数３】
2014217063.tif 000070
（ここで、ＢＯ１は、第１のグループの隣接ノードについて設定されるバックオフ時間であり、ＢＯ２は、第２のグループの隣接ノードについて設定されるバックオフ時間であり、ｔ１、ｔ２、ｔ３、ｔ４は所定の時間であり、ｔ０は前記診断ノードが前記被疑ノードの故障を検出したタイミングである）により前記バックオフ時間を設定する、
請求項１１乃至１３のいずれかに記載のバックオフ時間の設定方法。
【請求項１５】
【数４】
2014217063.tif 000071
となり、
Ｆ（Ｈｏｐ，ＮＮ）は値が［０，１］にある関数であり、前記Ｆ（Ｈｏｐ，ＮＮ）はノードのホップ数Ｈｏｐに正比例し、ノードの隣接ノードの数に反比例する、
請求項１４に記載のバックオフ時間の設定方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの故障診断の技術分野に関し、特に故障診断装置及び方法、並びにバックオフ時間の設定方法に関する。
【背景技術】
【０００２】
ネットワークでは故障が発生した場合には、例えばリンク故障診断及びノード故障診断を含むネットワークの故障診断プロセスを起動して故障を取り除く必要がある。従来では、１つの被疑ノードを診断する必要がある場合には、該被疑ノードの複数の診断ノードは共に診断プロセスを起動し、それぞれ診断ツリーを確立して診断結果を報告することがある。
【０００３】
しかし、被疑ノードを診断する必要がある場合には、１つのみの診断ノードが診断結果を報告することを確保できないため、ゲートウェイ（GW：Gateway）側では統一した診断結果を取得できず、複数の診断プロセスが同時に起動され、複数の診断ノードで診断情報を報告しているから、システムに過大な通信オーバヘッドをもたらすことになる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の実施例は、ゲートウェイ側で統一した診断結果を取得すると共に、システムの通信オーバヘッドを低減する故障診断装置及び方法、並びにバックオフ時間の設定方法を提供することを目的とする。
【課題を解決するための手段】
【０００５】
本発明の実施例の一の態様では、被疑ノードを診断する必要がある場合、診断ノードの前記被疑ノードに対するバックオフ時間を起動する時間起動手段であって、前記バックオフ時間は前記被疑ノードの複数の隣接ノードを異なるグループに分けることで設定されるものである、時間起動手段と、前記バックオフ時間をカウントダウンすることでルートノードを決定するルートノード決定手段であって、前記ルートノードは前記被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである、ルートノード決定手段と、診断ツリーを確立するように前記ルートノードを制御し、前記診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する診断制御手段と、を含む、故障診断装置、を提供する。
【０００６】
本発明の実施例の他の態様では、被疑ノードを診断する必要がある場合、診断ノードの前記被疑ノードに対するバックオフ時間を起動するステップであって、前記バックオフ時間は前記被疑ノードの複数の隣接ノードを異なるグループに分けることで設定されるものである、ステップと、前記バックオフ時間をカウントダウンすることでルートノードを決定するステップであって、前記ルートノードは前記被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである、ステップと、診断ツリーを確立するように前記ルートノードを制御し、前記診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告するステップと、を含む、故障診断方法、を提供する。
【０００７】
本発明の実施例の他の態様では、ノードの複数の隣接ノードを異なるグループに分けるステップと、異なるグループの隣接ノードについて異なるバックオフ時間を設定するステップであって、異なるグループのバックオフ時間により構成された時間範囲が互いに重ならない、ステップと、を含む、バックオフ時間の設定方法、を提供する。
【発明の効果】
【０００８】
本発明の実施例によれば、被疑ノードを診断する必要がある場合、診断ノードの被疑ノードに対するバックオフ時間を起動し、バックオフ時間をカウントダウンすることでルートノードを決定し、該ルートノードにより診断ツリーを確立し、診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する。よって、ゲートウェイ側では統一された診断結果を取得でき、システムの通信オーバヘッドを低減できる。
【０００９】
本発明の特定の実施形態は、後述の説明及び図面に示すように、詳細に開示され、本発明の原理を採用されることが可能な方式を示している。なお、本発明の実施形態は、範囲上には限定されるものではない。本発明の実施形態は、添付されている特許請求の範囲の主旨及び内容の範囲内、各種の改変、修正、及び同等的なものが含まれる。
【００１０】
ある一つの実施形態に説明及び又は示されている特徴は、同一又は類似の方式で一つ又は多くの他の実施形態に使用されてもよく、他の実施形態における特徴と組み合わせてもよく、他の実施形態における特徴を代替してもよい。
【００１１】
なお、用語「包括／含む」は、本文に使用される際に、特徴、要素、ステップ又は構成要件の存在を意味し、一つ又は複数の他の特徴、要素、ステップ又は構成要件の存在又は追加を排除するものではない。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施例１に係る故障診断装置の１つの構成を示す図である。
【図２】本発明の実施例１に係る故障診断装置のもう１つの構成を示す図である。
【図３】本発明の実施例１に係る１つのノードの隣接ノードのグループ分けを示す図である。
【図４】本発明の実施例１に係るｔ１、ｔ２、ｔ３、ｔ４とＢＯ１、ＢＯ２との関係を示す図である。
【図５】本発明の実施例１に係る故障診断装置のもう１つの構成を示す図である。
【図６】本発明の実施例１に係る１つのノードの隣接ノードのグループ分けを示す他の図である。
【図７】本発明の実施例１に係る検知用パケットの構成を示す図である。
【図８】本発明の実施例２に係る故障診断方法のフローチャートである。
【図９】本発明の実施例２に係る故障診断方法の他のフローチャートである。
【図１０】本発明の実施例３に係るバックオフ時間の設定方法のフローチャートである。
【図１１】本発明の実施例３に係るバックオフ時間の設定方法の例を示す図である。
【図１２】本発明の実施例３に係るバックオフ時間の設定方法の例を示す他の図である。
【図１３】本発明の実施例４に係るネットワークノードを示す図である。
【図１４】本発明の実施例４に係るネットワークノードを示す他の図である。
【発明を実施するための形態】
【００１３】
以下、図面を参照しながら本発明の各実施形態を説明する。これらの実施形態は単なる例示的なものであり、本発明を限定するものではない。当業者に本発明の原理及び実施形態をより簡単に理解させるため、本発明の実施形態では、Ａｄ  ｈｏｃネットワーク又は無線センサネットワークを例として説明している。なお、本発明のこれらに限定されず、本発明の実施形態はネットワーク故障のある全ての通信システムに適用されてもよい。
【００１４】
＜実施例１＞
本発明の実施例では、故障診断装置を提供する。図１は、本発明の実施例１に係る故障診断装置の１つの構成を示す図である。図１に示すように、該故障診断装置１００は、時間起動部１０１、ルートノード決定部１０２、及び診断制御部１０３を含む。
【００１５】
具体的には、時間起動部１０１は、被疑ノードを診断する必要がある場合、診断ノードの該被疑ノードに対するバックオフ時間を起動する。バックオフ時間は、被疑ノードの複数の隣接ノードを異なるグループに分けることで設定される。ルートノード決定部１０２は、バックオフ時間をカウントダウンすることで、ルートノードを決定する。ルートノードは、被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである。診断制御部１０３は、診断ツリーを確立するようにルートノードを制御し、診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する。
【００１６】
本実施例では、故障診断装置１００は、診断ノードの構成部分であってもよく、ネットワークにおける１つ又は複数の診断ノードは故障診断装置１００を有してもよく、診断ノードの他の部分の構成は従来技術を参考してもよい。例えば、ネットワークにおける各診断ノードは共に故障診断装置１００を有してもよい。被疑ノードは、診断ノードと同じ構成を有してもよい。このように、ネットワークにおける各ノードは、分布式の構造を形成してもよい。
【００１７】
なお、本発明のこれに限定されず、例えば、故障診断装置１００は診断ノードから独立したものであってもよく、ネットワークにおいて複数の診断ノードを制御する機器であってもよい。このように、ネットワークにおいて集中式の構造を形成してもよい。或いは、故障診断装置１００は、一部が診断ノードに位置し、他部が集中式の機器を形成してもよい。当業者が実際の状況に応じて具体的な実施形態を決定してもよい。下記の実施例では、１つ又は複数の診断ノードに含まれる故障診断装置を例として説明する。
【００１８】
本実施例では、診断プロセスにおいて２種類ノード、即ち診断ノード（DN：Detection  Node）と被疑ノード（SN：Suspect  Node）がある。例えば、ノードＡはノードＢと通信ができない場合、ノードＡはノードに故障が生じたことを疑い、ノードＢについての診断プロセスを起動する。ノードＡは診断ノードＤＮと称され、ノードＢは被疑ノードと称される。診断ノードは被疑ノードの１つ又は複数の隣接ノードである、即ち、診断ノードの集合は被疑ノードの隣接ノードの集合の部分集合であってもよい。
【００１９】
被疑ノードＢの診断が必要である場合、複数の診断ノードが存在する可能性がある（例えば、ノードＡ以外は、ノードＣ、Ｄがある）。具体的に実施する際に、診断ノードＡ、Ｃ、Ｄはそれぞれの時間起動部１０１によりバックオフ時間のカウントダウンを起動し、カウントダウンが最も早く終了した診断ノード（例えばノードＡ）におけるルートノード決定部１０２は該ノードＡがルートノード（RN：Root  Node）であると決定してもよく、他の診断ノード（例えばノードＣ、Ｄ）におけるルートノード決定部１０２はノードＣ、Ｄがルートノードではないと決定してもよい（具体的には、後述するように、バックオフ時間のカウントダウンを停止してもよい）。
【００２０】
このように、診断ノードＡの診断制御部１０３が診断制御を行い、該ルートノードＡが診断ツリーを確立し、診断ツリーに追加されたノードがそれぞれの診断情報を該ルートノードＡに送信し、最後にノードＡがＧＷに診断結果を報告する。よって、ゲートウェイ側では統一された診断結果を取得でき、システムの通信オーバヘッドを低減できる。診断ツリーの確立、診断情報の収集及び診断結果の送信について、従来技術を参照してもよく、その詳細はここに省略される。
【００２１】
本実施例では、バックオフ時間は予め設定されてもよい。ネットワークにおけるノードは、該ノードの複数の隣接ノードについてバックオフ時間を設定してもよい。バックオフ時間は、該ノードの複数の隣接ノードを異なるグループに分けた後で設定されてもよく、異なるグループの隣接ノードについて異なるバックオフ時間が設定される。
【００２２】
具体的には、被疑ノードの隣接ノードにゲートウェイノードがある、即ちゲートウェイが該被疑ノードの隣接ノードである場合、該ゲートウェイが該被疑ノードを診断するとき、該ゲートウェイをルートノードと決定してもよい。例えば、直接該ゲートウェイをルートノードと決定し、該ゲートウェイが診断ツリーを確立してもよいし、該ゲートウェイのバックオフ時間を最も早く終了させるように、該ゲートウェイについて他のノードよりも短いバックオフ時間を設定してもよい。
【００２３】
具体的には、バックオフ時間の設定について、ノードが各隣接ノードにまとめて割り当ててもよいし、各隣接ノードそれぞれが自ら計算してもよい。本発明はこれに限定されないが、本実施例では、各隣接ノードがノードについてのそれぞれのバックオフ時間を自ら計算することを例として説明する。
【００２４】
図２は、本発明の実施例１に係る故障診断装置のもう１つの構成を示す図である。図２に示すように、故障診断装置２００は、上述した時間起動部１０１、ルートノード決定部１０２、及び診断制御部１０３を含む。
【００２５】
図２に示すように、故障診断装置２００は、グループ分け部２０４をさらに含んでもよい。グループ分け部２０４は、通信距離に基づいて、被疑ノードの複数の隣接ノードを複数の異なるグループに分ける。
【００２６】
具体的には、グループ分け部２０４は、通信距離に基づいて、被疑ノードの複数の隣接ノードを第１のグループと第２のグループとに分け、第１のグループ内の隣接ノードと被疑ノードとの通信距離は所定の距離、例えばＲ／２、Ｒ／３、Ｒ／４など以下であり、第２のグループ内の隣接ノードと被疑ノードとの通信距離は該所定の距離よりも大きい。ここで、Ｒは被疑ノードの通信範囲である。
【００２７】
また、受信されたノードの信号強度に基づいてグループ分けてもよく、第１のグループの隣接ノードにより受信されたノードの信号強度は所定の信号強度閾値、例えば−５０ｄＢｍ、−６０ｄＢｍ又は−７０ｄＢｍ等以上であり、第２のグループの隣接ノードにより受信されたノードの信号強度は該所定の信号強度閾値よりも小さい。
【００２８】
３つ以上のグループ、例えば第１のグループ、第２のグループ、第３のグループに分ける場合、第１のグループの隣接ノードと該ノードとの通信距離はＲ／４以下であり、第２のグループの隣接ノードと該ノードとの通信距離はＲ／４よりも大きく、且つＲ／２以下であり、第３のグループの隣接ノードと該ノードとの通信距離はＲ／２よりも大きい。これと類似するような他のグループ分け方法であってもよいが、ここに列挙されない。
【００２９】
例えば、ネットワークにおける各ノードは、周期的に監視すること（例えばＨｅｌｌｏパケット方式を用いる）によって自分と隣接ノードとの間の受信信号強度指示（RSSI：Received  Signal  Strength  Indication）情報を取得して、該ノードと隣接ノードとの通信距離を取得して、複数の隣接ノードのグループ分けを行ってもよい。
【００３０】
なお、上述した通信距離に基づくグループ分けの方法は単なる本発明の具体的な実施形態であり、本発明はこれに限定されず、例えば他の情報（例えば通信品質）に基づいてグループ分けを行ってもよいし、或いは隣接ノードを３つ以上のグループ（例えば３つのグループ、４つのグループ）に分けてもよく、実際の状況に応じて具体的な実施形態を決定してもよい。
【００３１】
図３は、本発明の実施例１に係る１つのノードの隣接ノードのグループ分けを示す図である。図３に示すように、ノード(1)は該ノードであり、ノード(2)(3)(4)(5)(6)はその隣接ノードである。ノード(1)との距離がＲ／２以下（Ｒはノードの通信範囲である）の領域（図示領域Ａ）を一次的領域ＰＺ（Primary  Zone）と称してもよく、ノード(1)の通信範囲内にあり、且つノード(1)との距離がＲ／２よりも大きい領域（図示領域Ｂ）を二次的領域ＳＺ（Secondary  Zone）と称してもよい。このように、隣接ノードのグループ分け（例えばＰＺ領域の隣接ノードは第１のグループに対応し、ＳＺ領域の隣接ノードは第２のグループに対応する）を行うことができる。
【００３２】
本実施例では、ノードの複数の隣接ノードを異なるグループに分けて、異なるグループの隣接ノードについて異なるバックオフ時間を設定してもよい。よって、異なるグループの隣接ノードのバックオフ時間は同時に終わることなく、バックオフ時間のカウントダウンに基づいて決定されたルートノードを１つにすることができる。
【００３３】
図２に示すように、故障診断装置２００は、異なるグループの隣接ノードについて異なるバックオフ時間を設定する時間設定部２０５をさらに含んでもよい。ここで、各グループの複数の隣接ノードに対応するバックオフ時間は複数であってもよく、例えば各隣接ノードのバックオフ時間はそれぞれ異なってもよい。よって、各グループのバックオフ時間は時間範囲を形成できる。
【００３４】
また、異なるグループのバックオフ時間により構成された時間範囲が互いに重ならない。以下、２つのグループに分けることを例として、バックオフ時間の設定を説明する。本実施例では、下記ルールに基づいて各隣接ノードについてバックオフ時間ＢＯ（Backoff）を設定する。
【００３５】
例えば、時間設定部２０５は、下記式によりバックオフ時間を設定してもよい。
【数１】
2014217063.tif 000003
【００３６】
ここで、ＢＯ１は、第１のグループの隣接ノード（例えば図３における(4)(5)）について設定されるバックオフ時間であり、ＢＯ２は、第２のグループの隣接ノード（例えば図３における(2)(3)(6)）について設定されるバックオフ時間であり、ｔ１、ｔ２、ｔ３、ｔ４は所定の時間であり、ｔ０は診断ノードが被疑ノードの故障を検出したタイミングである。
【００３７】
具体的には、下記式により実現してもよい。
【数２】
2014217063.tif 000004
【００３８】
Ｆ（Ｈｏｐ，ＮＮ）は値が［０，１］にある関数であり、Ｆ（Ｈｏｐ，ＮＮ）は該隣接ノードのホップ数Ｈｏｐに正比例し、該隣接ノードの数に反比例する。
【００３９】
具体的には、ｔ０＝ｔ１の場合、ノードが故障を検出し次第バックオフ時間のカウントダウンを開始することを表し、ｔ０＜ｔ１の場合、ノードが故障を検出して、一定時間遅らせてバックオフ時間のカウントダウンを開始することを表す。ｔ１＝ｔ２の場合、ノードがＭＡＣ層のＣＳＭＡ／ＣＡ方式のｂａｃｋｏｆｆ時間を自分のバックオフ時間としてもよいことを表し、ＭＡＣ層におけるｂａｃｋｏｆｆ方式はチャネル衝突の回避を確保するためのものであり、具体的な内容は従来技術を参照してもよい。ｔ３、ｔ４はｔ１、ｔ２と同じであってもよい。
【００４０】
具体的には、被疑ノードの隣接ノードにゲートウェイノードがある場合、該ゲートウェイのバックオフ時間のカウントダウンに最も早く終わらせて、ルートノードにならせて診断ツリーを確立させるように、該ゲートウェイについてｔ０〜ｔ１の間のバックオフ時間を割り当てもよい。
【００４１】
１つの例では、Ｆ（Ｈｏｐ，ＮＮ）は下記の式
【数３】
2014217063.tif 000005
を用いてもよい。
【００４２】
ここで、
【数４】
2014217063.tif 000006
、εは値が［０，０．５］にあるランダムパラメータである。
【００４３】
もう１つの例では、Ｆ（Ｈｏｐ，ＮＮ）は下記の式
【数５】
2014217063.tif 000007
又は
【数６】
2014217063.tif 000008
を用いてもよい。
【００４４】
ここで、
【数７】
2014217063.tif 000009
、εは値が［０，０．５］にあるランダムパラメータであり、
【数８】
2014217063.tif 000010
の場合、
【数９】
2014217063.tif 000011
とする。
【００４５】
図４は、本発明の実施例１に係るｔ１、ｔ２、ｔ３、ｔ４とＢＯ１、ＢＯ２との関係を示す図である。図４に示すように、ＢＯ１は、［ｔ１，ｔ２］にある値であり、ＢＯ２は、［ｔ３，ｔ４］にある値である。被疑ノードとの距離がＲ／２の範囲内に少なくとも１つの診断ノードがある場合、［ｔ２，ｔ３］という時間は、診断ツリーの確立プロセスを起動する診断ノードが１つのみであることを確保した。
【００４６】
具体的には、ｔ２とｔ３との間の間隔時間はパラメータである。ｔ２とｔ３との間の間隔を「データパケットを３ホップ伝送する時間」と設定してもよいし、「データパケットを９ホップ伝送する時間」と設定してもよい。
【００４７】
例えば、図３に示す例において、隣接ノード(4)(5)の時間設定部２０５はノード(1)について
【数１０】
2014217063.tif 000012
を用いてバックオフ時間Ｔ４、Ｔ５を設定してもよく、隣接ノード(2)(3)(6)の時間設定部２０５はノード(1)について
【数１１】
2014217063.tif 000013
を用いてバックオフ時間Ｔ２、Ｔ３、Ｔ６を設定してもよい。ノード(1)の時間設定部２０５はその隣接ノードについての自分のバックオフ時間を設定してもよい。
【００４８】
なお、上述したバックオフ時間の設定は単なる例示的なものであり、本発明はこれに限定されず、例えば実際の状況に応じて適切に変形してもよいし、他の式を用いてもよい。
【００４９】
図５は、本発明の実施例１に係る故障診断装置のもう１つの構成を示す図である。図５に示すように、故障診断装置５００は、上述した時間起動部１０１、ルートノード決定部１０２、診断制御部１０３、グループ分け部２０４、及び時間設定部２０５を含む。
【００５０】
図５に示すように、故障診断装置５００は、ノード選択部５０５をさらに含んでもよい。ノード選択部５０５は、第１のグループに隣接ノードがない場合、第２のグループから第１のグループの隣接ノードとして１つの隣接ノードを選択し、選択された隣接ノードについて第１のグループに対応するバックオフ時間を設定する。
【００５１】
具体的には、ノード選択部５０５は、隣接ノードと診断ノードとの距離が全てＲ／２よりも大きい場合、距離のＲ／２よりも大きい隣接ノードから１つの隣接ノードを第１のグループの隣接ノードとして選択する。
【００５２】
図５に示すように、故障診断装置５００は、時間送信部５０６をさらに含んでもよい。時間送信部５０６は、選択された隣接ノードにバックオフ時間を記憶させるように、選択された隣接ノードへバックオフ時間を送信する。
【００５３】
ここで、ノード選択部５０５は、診断ノードに最も近い隣接ノードを選択してもよいし、同じ距離の隣接ノードが複数存在する場合、そのうちホップ数の最も小さい隣接ノードを選択してもよいし、同じ距離且つ同じホップ数の隣接ノードが複数存在する場合、そのうち１つの隣接ノードをランダムに選択してもよい。
【００５４】
図６は、本発明の実施例１に係る１つのノードの隣接ノードのグループ分けを示す他の図である。図６に示すように、ノード(1)は該ノードであり、ノード(2)(3)(6)はその隣接ノードである。ノード(1)との距離がＲ／２以下（Ｒはノードの通信範囲である）の領域（図示領域Ａ）を一次的領域ＰＺ（Primary  Zone）と称してもよく、ノード(1)の通信範囲内にあり、且つノード(1)との距離がＲ／２よりも大きい領域（図示領域Ｂ）を二次的領域ＳＺ（Secondary  Zone）と称してもよい。
【００５５】
図６に示すように、領域Ａに隣接ノードがないが、領域Ｂに隣接ノード(2)(3)(6)がある。具体的には、例えば図６に示すようにＰＺ（領域Ａ）にノードがない場合、即ちノード(1)と隣接ノードとの距離が全てＲ／２よりも大きい場合、ノード(1)は、自分に最も近いノード（例えばノード(2)）を選択する。同じ距離の隣接ノードが複数存在する場合、そのうちホップ数の最も小さい隣接ノードを選択し、同じ距離且つ同じホップ数の隣接ノードが複数存在する場合、そのうち１つの隣接ノードをランダムに選択する。
【００５６】
隣接ノード（例えばノード(2)）が選出されると、ノード(1)は該隣接ノード(2)について［ｔ１，ｔ２］にあるＢＡＣＫＯＦＦ時間を設定し、該隣接ノードにこの時間を送信してもよい。
【００５７】
本実施例では、時間起動部１０１は、診断ノードが被疑ノードから複数の監視用パケット（Ｈｅｌｌｏパケット）を連続的に受信していない場合、該被疑ノードについてのバックオフ時間のカウントダウンを起動し、ローカルに該被疑ノードをローカル被疑ノードＬＳＮ（Local  Suspect  Node）として記憶してもよい。
【００５８】
本実施例では、診断制御部１０３は、ルートノード決定部１０２によりルートノードが決定された後で、検出用パケットＤＰ（Detection  Packet）をブロードキャストするようにルートノードをさらに制御してもよい。他の診断ノードは、バックオフ時間のカウントダウンが終了しておらず、且つ該検出用パケットを受信した場合、バックオフ時間のカウントダウンを行わない。ここで、他の診断ノードとは、ルートノードとして決定された診断ノード以外の１つ又は複数の診断ノードを指す。
【００５９】
具体的には、例えばノードＡはその隣接ノードＢがＫ回分のＨｅｌｌｏパケットを連続的に受信していないことを発見した場合、ノードＡはノードＢを診断する必要があると判断し、ノードＢをローカルに記憶し、ＬＳＮ（Local  SN）とする。ノードＡのバックオフ時間ＢＯのカウントダウンが終了した場合、診断ツリーを確立して検知用パケットＤＰをブロードキャストしてもよい。ＢＯのカウントダウンが終了していない時に、ノードＡが他のノードから送信された検知用パケットＤＰを受信した場合、ＢＯのカウントダウンを行わず、該検知用パケットＤＰをブロードキャストし続ける（なお、診断ツリーに追加されたノードは、再びＤＰパケットを受信した場合、ブロードキャストしない）。
【００６０】
ここで、該検知用パケットＤＰは、ソースアドレス、被疑ノードの識別子情報、及びルートノードの識別子情報を含んでもよい。また、フレームタイプ（Frame  Type）及び予備ビット（Reserved）をさらに含んでもよい。
【００６１】
図７は、本発明の実施例１に係る検知用パケットの構成を示す図である。図７に示すように、ＤＰパケットのソースアドレス（ＧＳと示してもよい）、パケットがdetection  packetであることを示すためのフレームタイプ（FT：Frame  Type）、被疑ノードの識別子（SN  IDと示してもよい）、ルートノードの識別子（RN  IDと示してもよい）、及び予備ビット（Reservedと示してもよい）を含んでもよい。
【００６２】
本実施例では、ノードがＤＰを受信した場合、ＤＰのＳＮ  ＩＤとローカルに記憶されているＬＳＮと同じであるとき、該ＤＰのＧＳを自分のアドレスと変更し、該ＤＰをブロードキャストし続け、ＳＮ  ＩＤとローカルの隣接ノードテーブルにおける隣接ノードと同じであるとき、該ＤＰをブロードキャストし続け、ローカルの隣接ノードテーブルに該ＳＮ  ＩＤがないとき、該ＤＰをブロードキャストしない（該ノードがＳＮの隣接ノードではないことを意味する）。
【００６３】
本発明の実施例によれば、被疑ノードを診断する必要がある場合、診断ノードの被疑ノードに対するバックオフ時間を起動し、バックオフ時間をカウントダウンすることでルートノードを決定し、該ルートノードにより診断ツリーを確立し、診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する。よって、ゲートウェイ側では統一された診断結果を取得でき、システムの通信オーバヘッドを低減できる。
【００６４】
＜実施例２＞
本発明の実施例は、実施例１に係る故障診断装置に対応する故障診断方法を提供する。図８は、本発明の実施例２に係る故障診断方法のフローチャートである。図８に示すように、該故障診断方法は、以下のステップを含む。
【００６５】
ステップ８０１：被疑ノードを診断する必要がある場合、診断ノードの被疑ノードに対するバックオフ時間を起動する。
【００６６】
ステップ８０２：バックオフ時間をカウントダウンすることで、ルートノードを決定する。ルートノードは被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである。
【００６７】
ステップ８０３：診断ツリーを確立するようにルートノードを制御し、診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する。
【００６８】
本実施例では、バックオフ時間は、予め決定されてもよい。各診断ノードについて、診断ノードの複数の隣接ノードを異なるグループに分けて、異なるグループの隣接ノードについて異なるバックオフ時間を設定してもよい。
【００６９】
具体的には、診断ノードの複数の隣接ノードを異なるグループに分けるステップにおいて、通信距離に基づいて、複数の隣接ノードを複数の異なるグループに分けてもよい。例えば、第１のグループと第２のグループとに分けてもよい。第１のグループ内の隣接ノードと被疑ノードとの通信距離はＲ／２以下であり、第２のグループ内の隣接ノードと被疑ノードとの通信距離はＲ／２よりも大きく、Ｒは被疑ノードの通信範囲である。
【００７０】
１つの例では、図３に示すように、第１のグループ（図３における領域Ａ）及び第２のグループ（図３における領域Ｂ）にはいずれも隣接ノードがある。異なるグループの隣接ノードについて、異なるバックオフ時間をそれぞれ設定してもよい。
【００７１】
他の例では、図６に示すように、隣接ノードと診断ノードとの距離が全てＲ／２よりも大きい場合、１つの隣接ノードを第１のグループの隣接ノードとして選択してもよい。ここで、１つの隣接ノードを第１のグループの隣接ノードとして選択するステップにおいて、診断ノードに最も近い隣接ノードを選択してもよいし、同じ距離の隣接ノードが複数存在する場合、そのうちホップ数の最も小さい隣接ノードを選択してもよいし、同じ距離且つ同じホップ数の隣接ノードが複数存在する場合、そのうち１つの隣接ノードをランダムに選択してもよい。
【００７２】
本実施例では、故障診断方法は、選択された隣接ノードにバックオフ時間を記憶させるように、選択された隣接ノードへバックオフ時間を送信するステップをさらに含んでもよい。
【００７３】
本実施例では、ステップ８０１において被疑ノードを診断する必要がある場合、診断ノードの被疑ノードに対するバックオフ時間を起動するステップにおいて、診断ノードが被疑ノードから複数のＨｅｌｌｏパケットを連続的に受信していない場合、バックオフ時間のカウントダウンを起動し、ローカルに該被疑ノードをローカル被疑ノードとして記憶してもよい。
【００７４】
本実施例では、ステップ８０２においてルートノードを決定した後で、故障診断方法は、検出用パケットをブロードキャストするようにルートノードをさらに制御してもよい。他の診断ノードは、バックオフ時間のカウントダウンが終了しておらず、且つ該検出用パケットを受信した場合、バックオフ時間のカウントダウンを行わない。ここで、検知用パケットは、ソースアドレス、被疑ノードの識別子情報、及びルートノードの識別子情報を含んでもよい。検知用パケットの構成は図７に示されている。
【００７５】
本実施例では、故障診断方法は下記ステップをさらに含んでもよい。診断ノードが検知用パケットを受信した場合、該検知用パケットの被疑ノードの識別子情報とローカルに記憶されているローカル被疑ノードと同じであるとき、該検知用パケットのソースアドレスを自分のアドレスと変更し、検知用パケットをブロードキャストし続け、検知用パケットの被疑ノードの識別子情報とローカルの隣接ノードテーブルにおける隣接ノードと同じであるとき、該検知用パケットをブロードキャストし続け、ローカルの隣接ノードテーブルに検知用パケットの被疑ノードの識別子情報がないとき、検知用パケットをブロードキャストしない。
【００７６】
図９は、本発明の実施例２に係る故障診断方法の他のフローチャートである。図９に示すように、故障診断方法は、下記のステップを含む。
【００７７】
ステップ９０１：診断ノードは被疑ノードから送信されたＨｅｌｌｏパケットを計数する。
【００７８】
ステップ９０２：該被疑ノードから送信されたＫ個のＨｅｌｌｏパケットを連続的に受信したか否かを判断し、連続的に受信していない場合、ステップ９０３に進む。
【００７９】
ステップ９０３：診断ノードは被疑ノードを診断する必要があると判断し、バックオフ時間を起動してカウントダウンを開始する。
【００８０】
ステップ９０４：バックオフ時間のカウントダウンが終了したか否かを判断し、カウントダウンが既に終了した場合、ステップ９０５に進み、逆の場合、ステップ９０７に進む。
【００８１】
具体的には、該診断ノードの該被疑ノードに対するバックオフ時間ＢＯを判断してもよい。ＢＯが０よりも大きい場合、バックオフ時間がまだ終わっていないため、ステップ９０７に進み、ＢＯが０以下の場合、バックオフ時間が終了したため、ステップ９０５に進む。
【００８２】
ステップ９０５：該診断ノードをルートノードと決定し、診断ツリーを確立し、検知用パケットをブロードキャストする。
【００８３】
ステップ９０６：診断情報を収集し、ゲートウェイに診断結果を報告する。
【００８４】
ステップ９０７：他のノードから送信された検知用パケットＤＰを受信したか否かを判断し、検知用パケットを受信した場合、ステップ９０８に進み、逆の場合、ステップ９０４に進む。
【００８５】
ステップ９０８：バックオフ時間のカウントダウンを停止し、診断ツリーに追加され、該検知用パケットをブロードキャストし続ける。
【００８６】
また、検知用パケットＤＰを受信したノードは、ローカル隣接ノードテーブルに該検知用ＤＰの被疑ノードの識別子情報がない場合、該ノードが該被疑ノードの隣接ノードではないことを意味し、該検知用パケットＤＰをブロードキャストしない。また、診断ツリーに既に追加されたノードは、検知用パケットを受信した後、該検知用パケットをブロードキャストしなくてもよい。
【００８７】
以下、図３を例として説明する。図３において、ノード(1)は隣接ノード(2)(3)(4)(5)(6)についてそれぞれのバックオフ時間、Ｔ２、Ｔ３、Ｔ４、Ｔ５、Ｔ６を設定している。具体的な設定方法は、実施例１又は後述する実施例３を参照してもよい。
【００８８】
ノード(1)を被疑ノードとして診断する必要がある場合、ノード(2)(3)(4)(5)(6)は診断ノードとしてバックオフ時間のカウントダウンを起動する。そのうち１つの診断ノード（例えばノード(5)）は、Ｔ５＝０（即ちバックオフ時間が最も早く終了した）の場合、該ノード(5)をルートノードと決定し、該ノード(5)は診断ツリーを確立して検知用パケットＤＰを送信してもよい。
【００８９】
他の診断ノード（例えばノード(2)(3)(4)(6)）は、ノード(5)から送信された検知用パケットＤＰを受信した場合、バックオフ時間のカウントダウンを停止し、診断ツリーに追加され、該検知用パケットＤＰをブロードキャストし続ける。よって、ノード(5)が診断ツリーを確立し、診断情報を収集してゲートウェイに送信することができる。
【００９０】
この実施例によれば、被疑ノードを診断する必要がある場合、診断ノードの被疑ノードに対するバックオフ時間を起動し、バックオフ時間をカウントダウンすることでルートノードを決定し、該ルートノードにより診断ツリーを確立し、診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する。よって、ゲートウェイ側では統一された診断結果を取得でき、システムの通信オーバヘッドを低減できる。
【００９１】
＜実施例３＞
本発明の実施例は、バックオフ時間の設定方法を提供する。このバックオフ時間の設定方法は、実施例２の一部又は事前の準備プロセスとしてもよく、実施例１におけるバックオフ時間の設定部分の内容と同じであり、ここにその説明を省略される。
【００９２】
図１０は、本発明の実施例３に係るバックオフ時間の設定方法のフローチャートである。図１０に示すように、該バックオフ時間の設定方法は以下のステップを含む。
【００９３】
ステップ１００１：ノードの複数の隣接ノードを異なるグループに分ける。
【００９４】
ステップ１００２：異なるグループの隣接ノードについて、異なるバックオフ時間を設定する。
【００９５】
本実施例では、任意のノードについて、該ノードの複数の隣接ノードを異なるグループに分けて、バックオフ時間を設定してもよい。よって、異なるグループの隣接ノードのバックオフ時間が同時に終了することなく、バックオフ時間のカウントダウンに基づいて決定されたルートノードが１つにすることができる。
【００９６】
具体的には、ステップ１００１において、通信距離に基づいて、ノードの複数の隣接ノードを複数の異なるグループに分けてもよい。例えば、第１のグループと第２のグループとに分けてもよく、第１のグループ内の隣接ノードとノードとの通信距離はＲ／２以下であり、第２のグループ内の隣接ノードとノードとの通信距離はＲ／２よりも大きく、Ｒは該ノードの通信範囲である。
【００９７】
なお、上述した通信距離に基づくグループ分けの方法は単なる本発明の具体的な実施形態であり、本発明はこれに限定されず、例えば他の情報（例えば通信品質）に基づいてグループ分けを行ってもよいし、隣接ノードを３つ以上のグループ（例えば３つのグループ、４つのグループ等）に分けてもよく、実際の状況に応じて具体的な実施形態を決定してもよい。
【００９８】
具体的な例として、ステップ１００２において下記のルールを用いてバックオフ時間を設定してもよい。
【数１２】
2014217063.tif 000014
【００９９】
ここで、ＢＯ１は、第１のグループの隣接ノードについて設定されるバックオフ時間であり、ＢＯ２は、第２のグループの隣接ノードについて設定されるバックオフ時間であり、ｔ１、ｔ２、ｔ３、ｔ４は所定の時間であり、ｔ０は診断ノードが被疑ノードの故障を検出したタイミングである。
【０１００】
より具体的には、下記のルールを用いてもよい。
【数１３】
2014217063.tif 000015
【０１０１】
Ｆ（Ｈｏｐ，ＮＮ）は値が［０，１］にある関数であり、Ｆ（Ｈｏｐ，ＮＮ）はノードのホップ数Ｈｏｐに正比例し、ノードの隣接ノードの数に反比例する。
【０１０２】
１つの例では、Ｆ（Ｈｏｐ，ＮＮ）は以下の式を用いてもよい。
【数１４】
2014217063.tif 000016
【０１０３】
ここで、
【数１５】
2014217063.tif 000017
、εは値が［０，０．５］にあるランダムパラメータである。
【０１０４】
もう１つの例では、Ｆ（Ｈｏｐ，ＮＮ）は以下の式を用いてもよい。
【数１６】
2014217063.tif 000018
又は
【数１７】
2014217063.tif 000019
【０１０５】
ここで、
【数１８】
2014217063.tif 000020
、εは値が［０，０．５］にあるランダムパラメータであり、
【数１９】
2014217063.tif 000021
の場合、
【数２０】
2014217063.tif 000022
とする。
【０１０６】
なお、上記の式は単なる本発明のバックオフ時間の設定を例示的に説明するものであり、本発明はこれに限定されず、実際の状況に応じて適切に変形してもよいし、他の式を用いてもよい。
【０１０７】
本実施例では、バックオフ時間の設定は該ノードで行ってもよい。該設定方法において、各隣接ノードに対応のバックオフ時間をそれぞれ記憶させるように、各隣接ノードへ設定されたバックオフ時間を送信する。
【０１０８】
また、バックオフ時間の設定は各ノードで行い、各ノードが該ノードに対するバックオフ時間をそれぞれ設定してもよい。以下は、各隣接ノードが該ノードに対するバックオフ時間をそれぞれ設定することを例として説明する。
【０１０９】
図１１は、本発明の実施例３に係るバックオフ時間の設定方法の例を示す図である。図３を例として、第１のグループ及び第２のグループに共に隣接ノードがあることが示されている。図１１に示すように、該設定方法は以下のステップを含む。
【０１１０】
ステップ１１０１：Ｈｅｌｌｏプロセスを開始する。
【０１１１】
ステップ１１０２：ノード間の距離を計算する。
【０１１２】
具体的には、Ｈｅｌｌｏパケットに含まれるＲＳＳＩ情報に基づいてノード間の距離を計算してもよいが、本発明はこれに限定されない。
【０１１３】
ステップ１１０３：該ノードの隣接ノードについて、該ノードと該隣接ノードとの距離がＲ／２よりも小さいか否かを判断し、ＹＥＳの場合はステップ１１０４に進み、ＮＯの場合はステップ１１０５に進む。
【０１１４】
ステップ１１０４：該隣接ノードは式
【数２１】
2014217063.tif 000023
によりバックオフ時間を設定する。
【０１１５】
ステップ１１０５：該隣接ノードは式
【数２２】
2014217063.tif 000024
によりバックオフ時間を設定する。
【０１１６】
例えば、図３の例では、隣接ノード(4)(5)は式
【数２３】
2014217063.tif 000025
によりノードについてのバックオフ時間を設定してもよい。ここで、Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数２４】
2014217063.tif 000026
を用いてもよく、ここで、
【数２５】
2014217063.tif 000027
、εは値が［０，０．５］にあるランダムパラメータである。
【０１１７】
或いは、Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数２６】
2014217063.tif 000028
又は
【数２７】
2014217063.tif 000029
を用いてもよく、ここで、
【数２８】
2014217063.tif 000030
、εは値が［０，０．５］にあるランダムパラメータであり、
【数２９】
2014217063.tif 000031
の場合、
【数３０】
2014217063.tif 000032
とする。Ｈｏｐは、ノード(4)又は(5)のホップ数であり、ＮＮはノード(4)又は(5)の隣接ノードの数である。
【０１１８】
一方、隣接ノード(2)(3)(6)は式
【数３１】
2014217063.tif 000033
によりノード(1)についてのバックオフ時間を設定してもよい。ここで、Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数３２】
2014217063.tif 000034
を用いてもよく、ここで、
【数３３】
2014217063.tif 000035
、εは値が［０，０．５］にあるランダムパラメータである。
【０１１９】
或いは、Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数３４】
2014217063.tif 000036
又は
【数３５】
2014217063.tif 000037
を用いてもよく、ここで、
【数３６】
2014217063.tif 000038
、εは値が［０，０．５］にあるランダムパラメータであり、
【数３７】
2014217063.tif 000039
の場合、
【数３８】
2014217063.tif 000040
とする。Ｈｏｐは、ノード(2)、(3)又は(6)のホップ数であり、ＮＮはノード(2)、(3)又は(6)の隣接ノードの数である。
【０１２０】
図１２は、本発明の実施例３に係るバックオフ時間の設定方法の例を示す他の図である。図３及び図６を例として、第１のグループに隣接ノードがないことが示されている。図１２に示すように、該設定方法は以下のステップを含む。
【０１２１】
ステップ１２０１：Ｈｅｌｌｏプロセスを開始する。
【０１２２】
ステップ１２０２：ノード間の距離を計算し、距離に基づいて第１の領域と第２の領域とに分ける。
【０１２３】
ステップ１２０３：第１の領域に隣接ノードが存在するか否かを判断し、隣接ノードがない場合ステップ１２０５に進み、隣接ノードがある場合、ステップ１２０４に進む。
【０１２４】
ステップ１２０４：該ノードの隣接ノードはグループ分けに基づいてバックオフ時間をそれぞれ設定する。
【０１２５】
具体的には、図１１におけるステップ１１０３乃至ステップ１１０５に従ってバックオフ時間を設定してもよい。
【０１２６】
ステップ１２０５：該ノードは隣接ノードから１つのノードを選択し、第１の領域の式により該隣接ノードについてバックオフ時間を設定する、即ち
【数３９】
2014217063.tif 000041
を用いる。
【０１２７】
具体的には、該ノードに最も近い隣接ノードを選択してもよいし、同じ距離の隣接ノードが複数存在する場合、そのうちホップ数の最も小さい隣接ノードを選択してもよいし、同じ距離且つ同じホップ数の隣接ノードが複数存在する場合、そのうち１つの隣接ノードをランダムに選択してもよい。
【０１２８】
ステップ１２０６：該ノードは該選択された隣接ノードに該バックオフ時間を送信する。
【０１２９】
ステップ１２０７：該選択された隣接ノードは、該バックオフ時間を受信した後、該バックオフ時間をローカルに記憶する。
【０１３０】
例えば、図６の例では、ノード(1)は１つの隣接ノード（例えばノード(2)）を選択して、ノード(1)は
【数４０】
2014217063.tif 000042
によりノード(2)のバックオフ時間を設定してもよい。
【０１３１】
ここで、Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数４１】
2014217063.tif 000043
を用いてもよく、ここで、
【数４２】
2014217063.tif 000044
、εは値が［０，０．５］にあるランダムパラメータである。
【０１３２】
或いは、Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数４３】
2014217063.tif 000045
又は
【数４４】
2014217063.tif 000046
を用いてもよく、ここで、
【数４５】
2014217063.tif 000047
、εは値が［０，０．５］にあるランダムパラメータであり、
【数４６】
2014217063.tif 000048
の場合、
【数４７】
2014217063.tif 000049
とする。Ｈｏｐは、ノード(2)のホップ数であり、ＮＮはノード(2)の隣接ノードの数である。
【０１３３】
そして、ノード(1)は該バックオフ時間をノード(2)に送信し、ノード(2)は自分で計算したバックオフ時間を該受信されたバックオフ時間に替えて、該更新後のバックオフ時間をローカルに記憶する。
【０１３４】
本実施例によれば、ノードの複数の隣接ノードを異なるグループに分け、異なるグループの隣接ノードについて異なるバックオフ時間を設定することで、異なるグループの隣接ノードのバックオフ時間が同時に終了することなく、バックオフ時間のカウントダウンに基づくルートノードが１つであることを確保できる。
【０１３５】
＜実施例４＞
本発明の実施例はネットワークノードを提供し、該ネットワークノードは実施例１に述べた故障診断装置を含む。図１３は、本発明の実施例４に係るネットワークノードを示す図である。図１３に示すように、ネットワークは複数のネットワークノード１３０１、１３０２、１３０３等を含んでもよく、１つ又は複数のネットワークノード（例えばネットワークノード１３０１）は時間起動部１０１、ルートノード決定部１０２及び診断制御部１０３を有してもよい。
【０１３６】
また、変形例として、本発明の故障診断装置は集中式のものであってもよい。図１４は、本発明の実施例４に係るネットワークノードを示す他の図である。図１４に示すように、ネットワークは複数のネットワークノード１３０１、１３０２、１３０３等を有してもよい。また、ネットワークは故障診断装置１３０４をさらに有してもよく、故障診断装置１３０４は、時間起動部１０１、ルートノード決定部１０２及び診断制御部１０３を有し、ネットワークノード１３０１、１３０２、１３０３等を制御し、ネットワークノードの故障診断を行う。
【０１３７】
本発明の以上の装置及び方法は、ハードウェアにより実現されてもよく、ハードウェアとソフトウェアを結合して実現されてもよい。本発明はコンピュータが読み取り可能なプログラムに関し、該プログラムはロジック部により実行される時に、該ロジック部に上述した装置又は構成要件を実現させる、或いは該ロジック部に上述した各種の方法又はステップを実現させることができる。本発明は上記のプログラムを記憶するための記憶媒体、例えばハードディスク、ディスク、光ディスク、ＤＶＤ、フラッシュメモリ等に関する。
【０１３８】
以上、具体的な実施形態を参照しながら本発明を説明しているが、上記の説明は、例示的なものに過ぎず、本発明の保護の範囲を限定するものではない。本発明の趣旨及び原理を離脱しない限り、本発明に対して各種の変形及び修正を行ってもよく、これらの変形及び修正も本発明の範囲に属する。
【０１３９】
また、上述の各実施例を含む実施形態に関し、更に以下の付記を開示する。
【０１４０】
（付記１）
被疑ノードを診断する必要がある場合、診断ノードの前記被疑ノードに対するバックオフ時間を起動する時間起動手段であって、前記バックオフ時間は前記被疑ノードの複数の隣接ノードを異なるグループに分けることで設定されるものである、時間起動手段と、
前記バックオフ時間をカウントダウンすることでルートノードを決定するルートノード決定手段であって、前記ルートノードは前記被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである、ルートノード決定手段と、
診断ツリーを確立するように前記ルートノードを制御し、前記診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告する診断制御手段と、を含む、故障診断装置。
【０１４１】
（付記２）
前記被疑ノードの複数の隣接ノードを異なるグループに分けるグループ分け手段、をさらに含む、
付記１に記載の故障診断装置。
【０１４２】
（付記３）
前記グループ分け手段は、通信距離に基づいて、前記被疑ノードの複数の隣接ノードを第１のグループと第２のグループとに分け、
前記第１のグループ内の隣接ノードと前記被疑ノードとの通信距離はＲ／２以下であり、前記第２のグループ内の隣接ノードと前記被疑ノードとの通信距離はＲ／２よりも大きく、前記Ｒは前記被疑ノードの通信範囲である、
付記２に記載の故障診断装置。
【０１４３】
（付記４）
異なるグループのバックオフ時間により構成された時間範囲が互いに重ならないように、グループに基づいて前記バックオフ時間を設定する時間設定手段、をさらに含む、
付記１乃至３のいずれかに記載の故障診断装置。
【０１４４】
（付記５）
前記時間設定手段は、下記の式
【数４８】
2014217063.tif 000050
（ここで、ＢＯ１は、第１のグループの隣接ノードについて設定されるバックオフ時間であり、ＢＯ２は、第２のグループの隣接ノードについて設定されるバックオフ時間であり、ｔ１、ｔ２、ｔ３、ｔ４は所定の時間であり、ｔ０は前記診断ノードが前記被疑ノードの故障を検出したタイミングである）により前記バックオフ時間を設定する、
付記４に記載の故障診断装置。
【０１４５】
（付記６）
【数４９】
2014217063.tif 000051
となり、
Ｆ（Ｈｏｐ，ＮＮ）は値が［０，１］にある関数であり、前記Ｆ（Ｈｏｐ，ＮＮ）はノードのホップ数Ｈｏｐに正比例し、ノードの隣接ノードの数に反比例する、
付記５に記載の故障診断装置。
【０１４６】
（付記７）
前記Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数５０】
2014217063.tif 000052
を用い、ここで、
【数５１】
2014217063.tif 000053
、εは値が［０，０．５］にあるランダムパラメータである、
付記６に記載の故障診断装置。
【０１４７】
（付記８）
前記Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数５２】
2014217063.tif 000054
又は
【数５３】
2014217063.tif 000055
を用い、ここで、
【数５４】
2014217063.tif 000056
、εは値が［０，０．５］にあるランダムパラメータであり、
【数５５】
2014217063.tif 000057
の場合、
【数５６】
2014217063.tif 000058
とする、
付記６に記載の故障診断装置。
【０１４８】
（付記９）
前記第１のグループに隣接ノードがない場合、前記第２のグループから前記第１のグループの隣接ノードとして１つの隣接ノードを選択し、前記選択された隣接ノードについて前記第１のグループに対応するバックオフ時間を設定するノード選択手段、をさらに含む、
付記３に記載の故障診断装置。
【０１４９】
（付記１０）
前記ノード選択手段は、前記被疑ノードに最も近い隣接ノードを選択する、或いは
同じ距離の隣接ノードが複数存在する場合、前記ノード選択手段は、そのうちホップ数の最も小さい隣接ノードを選択する、或いは、
同じ距離且つ同じホップ数の隣接ノードが複数存在する場合、前記ノード選択手段は、そのうち１つの隣接ノードをランダムに選択する、
付記９に記載の故障診断装置。
【０１５０】
（付記１１）
前記選択された隣接ノードに前記バックオフ時間を記憶させ、使用させるように、前記選択された隣接ノードへ前記バックオフ時間を送信する、時間送信手段、をさらに含む、
付記９又は１０に記載の故障診断装置。
【０１５１】
（付記１２）
前記時間起動手段は、前記診断ノードが前記被疑ノードから複数のＨｅｌｌｏパケットを連続的に受信していない場合、前記バックオフ時間のカウントダウンを起動し、ローカルに前記被疑ノードをローカル被疑ノードとして記憶する、
付記１に記載の故障診断装置。
【０１５２】
（付記１３）
前記診断制御手段は、検出用パケットをブロードキャストするように前記ルートノードをさらに制御し、
他の診断ノードは、バックオフ時間のカウントダウンが終了しておらず、且つ前記検出用パケットを受信した場合、バックオフ時間のカウントダウンを行わない、
付記１２に記載の故障診断装置。
【０１５３】
（付記１４）
前記検知用パケットは、ソースアドレス、前記被疑ノードの識別子、及び前記ルートノードの識別子を含む、
付記１３に記載の故障診断装置。
【０１５４】
（付記１５）
被疑ノードを診断する必要がある場合、診断ノードの前記被疑ノードに対するバックオフ時間を起動するステップであって、前記バックオフ時間は前記被疑ノードの複数の隣接ノードを異なるグループに分けることで設定されるものである、ステップと、
前記バックオフ時間をカウントダウンすることでルートノードを決定するステップであって、前記ルートノードは前記被疑ノード複数の診断ノードのうちバックオフ時間が最も早く終了した診断ノードである、ステップと、
診断ツリーを確立するように前記ルートノードを制御し、前記診断ツリーにおけるノードから送信された診断情報を受信し、ゲートウェイに診断結果を報告するステップと、を含む、故障診断方法。
【０１５５】
（付記１６）
前記被疑ノードの複数の隣接ノードを異なるグループに分け、異なるグループの隣接ノードについて異なるバックオフ時間を設定する、付記１５に記載の故障診断方法。
【０１５６】
（付記１７）
前記被疑ノードの複数の隣接ノードを異なるグループに分けるステップにおいて、
通信距離に基づいて、前記複数の隣接ノードを第１のグループと第２のグループとに分け、前記第１のグループ内の隣接ノードと前記被疑ノードとの通信距離はＲ／２以下であり、前記第２のグループ内の隣接ノードと前記被疑ノードとの通信距離はＲ／２よりも大きく、前記Ｒは前記被疑ノードの通信範囲である、
付記１６に記載の故障診断方法。
【０１５７】
（付記１８）
前記隣接ノードと前記被疑ノードとの距離が全てＲ／２よりも大きい場合、１つの隣接ノードを前記第１のグループの隣接ノードとして選択する、
付記１７に記載の故障診断方法。
【０１５８】
（付記１９）
１つの隣接ノードを前記第１のグループの隣接ノードとして選択するステップにおいて、
前記被疑ノードに最も近い隣接ノードを選択する、或いは
同じ距離の隣接ノードが複数存在する場合、そのうちホップ数の最も小さい隣接ノードを選択する、或いは、
同じ距離且つ同じホップ数の隣接ノードが複数存在する場合、そのうち１つの隣接ノードをランダムに選択する、
付記１８に記載の故障診断方法。
【０１５９】
（付記２０）
前記隣接ノードに前記バックオフ時間を記憶させ、使用させるように、前記隣接ノードへ前記バックオフ時間を送信する、
付記１８又は１９に記載の故障診断方法。
【０１６０】
（付記２１）
被疑ノードを診断する必要がある場合、診断ノードの前記被疑ノードに対するバックオフ時間を起動するステップにおいて、
前記診断ノードが前記被疑ノードから複数のＨｅｌｌｏパケットを連続的に受信していない場合、前記バックオフ時間のカウントダウンを起動し、ローカルに前記被疑ノードをローカル被疑ノードとして記憶する、
付記１５に記載の故障診断方法。
【０１６１】
（付記２２）
検出用パケットをブロードキャストするように前記ルートノードを制御し、
他の診断ノードは、バックオフ時間のカウントダウンが終了しておらず、且つ前記検出用パケットを受信した場合、バックオフ時間のカウントダウンを行わない、
付記２１に記載の故障診断方法。
【０１６２】
（付記２３）
前記検知用パケットは、ソースアドレス、前記被疑ノードの識別子情報、及び前記ルートノードの識別子情報を含む、
付記２２に記載の故障診断方法。
【０１６３】
（付記２４）
診断ノードが前記検知用パケットを受信した場合、前記検知用パケットの被疑ノードの識別子情報とローカルに記憶されているローカル被疑ノードと同じであるとき、前記検知用パケットのソースアドレスを前記診断ノード自身のアドレスと変更し、前記検知用パケットをブロードキャストし続け、
前記検知用パケットの被疑ノードの識別子情報とローカルの隣接ノードテーブルにおける隣接ノードと同じであるとき、前記検知用パケットをブロードキャストし続け、
ローカルの隣接ノードテーブルに前記検知用パケットの被疑ノードの識別子情報がないとき、前記検知用パケットをブロードキャストしない、
付記２２に記載の故障診断方法。
【０１６４】
（付記２５）
ノードの複数の隣接ノードを異なるグループに分けるステップと、
異なるグループの隣接ノードについて異なるバックオフ時間を設定するステップであって、異なるグループのバックオフ時間により構成された時間範囲が互いに重ならない、ステップと、を含む、バックオフ時間の設定方法。
【０１６５】
（付記２６）
ノードの複数の隣接ノードを異なるグループに分けるステップにおいて、通信距離に基づいて、ノードの複数の隣接ノードを複数の異なるグループに分ける、
付記２５に記載のバックオフ時間の設定方法。
【０１６６】
（付記２７）
通信距離に基づいて、前記複数の隣接ノードを第１のグループと第２のグループとに分け、前記第１のグループ内の隣接ノードと前記ノードとの通信距離はＲ／２以下であり、前記第２のグループ内の隣接ノードと前記ノードとの通信距離はＲ／２よりも大きく、前記Ｒは前記ノードの通信範囲である、
付記２６に記載のバックオフ時間の設定方法。
【０１６７】
（付記２８）
下記の式
【数５７】
2014217063.tif 000059
（ここで、ＢＯ１は、第１のグループの隣接ノードについて設定されるバックオフ時間であり、ＢＯ２は、第２のグループの隣接ノードについて設定されるバックオフ時間であり、ｔ１、ｔ２、ｔ３、ｔ４は所定の時間であり、ｔ０は前記診断ノードが前記被疑ノードの故障を検出したタイミングである）により前記バックオフ時間を設定する、
付記２５乃至２７のいずれかに記載のバックオフ時間の設定方法。
【０１６８】
（付記２９）
【数５８】
2014217063.tif 000060
となり、
Ｆ（Ｈｏｐ，ＮＮ）は値が［０，１］にある関数であり、前記Ｆ（Ｈｏｐ，ＮＮ）はノードのホップ数Ｈｏｐに正比例し、ノードの隣接ノードの数に反比例する、
付記２８に記載のバックオフ時間の設定方法。
【０１６９】
（付記３０）
前記Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数５９】
2014217063.tif 000061
を用い、ここで、
【数６０】
2014217063.tif 000062
、εは値が［０，０．５］にあるランダムパラメータである、
付記２９に記載のバックオフ時間の設定方法。
【０１７０】
（付記３１）
前記Ｆ（Ｈｏｐ，ＮＮ）は以下の式
【数６１】
2014217063.tif 000063
又は
【数６２】
2014217063.tif 000064
を用い、ここで、
【数６３】
2014217063.tif 000065
、εは値が［０，０．５］にあるランダムパラメータであり、
【数６４】
2014217063.tif 000066
の場合、
【数６５】
2014217063.tif 000067
とする、
付記２９に記載のバックオフ時間の設定方法。
【０１７１】
（付記３２）
前記隣接ノードと前記被疑ノードとの距離が全てＲ／２よりも大きい場合、１つの隣接ノードを前記第１のグループの隣接ノードとして選択する、
付記２７に記載のバックオフ時間の設定方法。
【０１７２】
（付記３３）
付記１乃至１４のいずれかに記載の故障診断装置を含む、
ネットワークノード。
【０１７３】
（付記３４）
ネットワークノードにおいてプログラムを実行する際に、コンピュータに、付記１５乃至２４のいずれかに記載の故障診断方法、又は付記２５乃至３１のいずれかに記載のバックオフ時間の設定方法を前記ネットワークノードにおいて実行させるコンピュータ読み取り可能なプログラム。
【０１７４】
（付記３５）
コンピュータに、付記１５乃至２４のいずれかに記載の故障診断方法、又は付記２５乃至３１のいずれかに記載のバックオフ時間の設定方法をネットワークノードにおいて実行させるためのコンピュータ読み取り可能なプログラムを記録する記録媒体。
【図１】
2014217063.tif 000072
【図２】
2014217063.tif 000073
【図３】
2014217063.tif 000074
【図４】
2014217063.tif 000075
【図５】
2014217063.tif 000076
【図６】
2014217063.tif 000077
【図７】
2014217063.tif 000078
【図８】
2014217063.tif 000079
【図９】
2014217063.tif 000080
【図１０】
2014217063.tif 000081
【図１１】
2014217063.tif 000082
【図１２】
2014217063.tif 000083
【図１３】
2014217063.tif 000084
【図１４】
2014217063.tif 000085