(57)【要約】【課題】マルチホップネットワークにおける故障検出方法及びノードを提供する。【解決手段】かかる方法は、第一所定ストラテジーに基づいて、前記ノードからゲイトウエイへの全てのリンクから所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応する第二ノードを有効検出親ノードとし；前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリストにおける故障検出情報を更新し；及び、受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うことを含む、方法。【選択図】図３
2015035807.tif 000002
【特許請求の範囲】
【請求項１】
マルチホップネットワークにおけるノードに用いる故障検出方法であって、
第一所定ストラテジーに基づいて、前記ノードからゲイトウエイへの全てのリンクから所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応する第二ノードを有効検出親ノードとし；
前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリストにおける故障検出情報を更新し；及び
受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うことを含む、方法。
【請求項２】
請求項1に記載の方法であって、
受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うステップは、
受信したHELLOパケットの個数を統計により取得し；及び
前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に前記HELLOパケットの個数が第一閾値未満である場合、前記第一ノードから前記隣接ノードへのリンクが疑似故障であると確定することを含む、方法。
【請求項３】
請求項1に記載の方法であって、
前記ノードが、自分の有効検出親ノードの情報を自分のHELLOパケットに追加し、前記HELLOパケットをブロードキャストし、これにより、前記HELLOパケットを受信した有効検出親ノードが、前記HELLOパケットに基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し；及び
前記ノードが、前記統計の結果が第二閾値未満である時に、自分の有効検出親ノードに状態検出リクエストパケットを送信し、自分の有効検出親ノードに、前記状態検出リクエストパケットに基づいて自分の状態を検出させ、又は、前記統計の結果が第三閾値以上である時に、第二所定ストラテジーに基づいて一部の子ノードを選択して診断ペアを形成すること更にを含む、方法。
【請求項４】
請求項1に記載の方法であって、
前記ノードが、受信したHELLOパケットに基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し；
前記子ノードの個数が第二閾値未満の場合、前記ノードが、自分の有効検出親ノードに状態検出リクエストパケットを送信し、自分の有効検出親ノードに、自分に対して故障検出を行せるようにリクエストし；及び
前記子ノードの個数が第三閾値以上の場合、前記ノードが、第二所定ストラテジーに基づいて前記子ノードから一部の子ノードを選択して診断ペアを形成し、選択した子ノードに返答情報を送信することを更に含む、方法。
【請求項５】
請求項3に記載の方法であって、
前記ノードが、自分の有効検出親ノードが返した返答情報を受信した場合、前記ノードは、該返答情報を送信した有効検出親ノードと診断ペアを形成し；及び
前記ノードが、自分の有効検出親ノードが返した返答情報を受信しておらず、且つ、前記ノードを有効検出親ノードとして選択した子ノードの個数と、返答情報を返した有効検出親ノードの個数との和が第四閾値未満である場合、返答情報未受信の有効検出親ノードの情報を含む状態検出強制リクエストパケットを送信し、該返答情報を返していない有効検出親ノードに、前記ノードを強制的に検出させ、そうでない場合、処理を終了させることを更に含む、方法。
【請求項６】
請求項5に記載の方法であて、
前記ノードを有効検出親ノードとして選択した子ノードの個数、返答情報を返した有効検出親ノードの個数、及び、前記返答情報を返していない有効検出親ノードの個数の和が依然として前記第四閾値未満の場合、前記方法は、更に、
前記ノードが、第三所定ストラテジーに基づいて、隣接ノードリストから一部の隣接ノードを選択し；及び
前記ノードが、選択した隣接ノードに状態検出強制リクエストパケットを送信し、該選択した隣接ノードに、前記ノードに対して故障検出を強制的に行せることを含む、方法。
【請求項７】
マルチホップネットワークにおけるノードであって、
第一所定ストラテジーに基づいて、前記ノードからゲイトウエイへの全てのリンクから所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応する第二ノードを有効検出親ノードとするための第一選択ユニット；
前記第一選択ユニットが選択した前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリストにおける故障検出情報を更新するための第一更新ユニット；
隣接ノードからのHELLOパケットを受信するための第一受信ユニット；及び
前記第一受信ユニットが受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うための第一検出ユニットを含む、ノード。
【請求項８】
請求項7に記載のノードであって、
前記第一検出ユニットは、更に、
前記第一受信ユニットが受信したHELLOパケットの個数を統計により取得するための第一統計ユニット；及び
前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に前記第一統計ユニットが取得したHELLOパケットの個数が第二閾値未満である時に、前記ノードから前記隣接ノードへのリンクが疑似故障であると確定するための第一確定ユニットを含む、ノード。
【請求項９】
請求項8に記載のノードであって、
前記第一検出ユニットは、更に、
前記隣接ノードリストをルックアップし、前記疑似故障のリンクが有効検出リンクであるかどうかを確定するための第二確定ユニット；
前記第二確定ユニットが、前記疑似故障のリンクが効検出リンクであると確定した時に、前記隣接ノードリストを更新し、前記リンクのリンク状態を疑似故障に変更するための第二更新ユニット；
前記第二更新ユニットが前記隣接ノードリストを更新した後に、該有効検出リンクに対応効検出親ノードに対してのノード故障検出を起動するための第二検出ユニット；及び
前記第二確定ユニットが、前記疑似故障のリンクが非有効検出リンクであると確定した時に、前記隣接ノードリストを更新し、前記リンクのリンク状態を疑似故障に変更するための第三更新ユニットを含む、ノード。
【請求項１０】
請求項7に記載のノードであって、
前記ノードの有効検出親ノードの情報を前記ノードのHELLOパケットに追加し、前記HELLOパケットをブロードキャストする第一送信ユニットであって、前記HELLOパケットを受信した有効検出親ノードは、前記HELLOパケットに基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し、前記第一送信ユニットは、統計の結果が第二閾値未満の時に、自分の有効検出親ノードに状態検出リクエストパケットを送信し、自分の有効検出親ノードに、状態検出リクエストパケットに基づいて自分の状態を検出させ、又は、統計の結果が第三閾値以上である時に、第二所定ストラテジーに基づいて一部の子ノードを選択して診断ペアを形成する、第一送信ユニットを更に含む、ノード。
【請求項１１】
請求項7に記載のノードであって、
受信した、他のノードが送信した、該他のノードの有効検出親ノードの情報を含むHELLOパケットに基づいて、前記ノードを有効検出親ノードとした子ノードの個数を統計により取得するための第二統計ユニット；及び
前記第二統計ユニットの統計結果が、前記個数が第二閾値未満の時に、前記ノードの有効検出親ノードに状態検出リクエストパケットを送信し、前記ノードの有効検出親ノードに、前記ノードに対して故障検出を行わせるようにリクエストするための第二送信ユニットを更に含み、
前記第二送信ユニットは、更に、前記第二統計ユニットの統計結果が、前記個数が第三閾値以上である時に、第二所定ストラテジーに基づいて、前記子ノードから一部の子ノードを選択して診断ペアを形成し、そして、選択した子ノードに返答情報を送信するために用いられる、ノード。
【請求項１２】
請求項10に記載のノードであって、
前記ノードの有効検出親ノードが返した返答情報を受信するための第二受信ユニット；
前記第二受信ユニットが、前記ノードの有効検出親ノードが返した返答情報を受信した時に、該返答情報を返した有効検出親ノードと診断ペアを形成するための第二選択ユニット；
前記ノードを有効検出親ノードとした子ノードの個数と、返答情報を返した有効検出親ノードの個数との和を統計により取得するための第三統計ユニット；及び
前記第三統計ユニットの統計結果が、前記個数の和が第四閾値未満の場合に、返答情報未受信の有効検出親ノードの情報を含む状態検出強制リクエストパケットを送信し、該返答情報を返していない有効検出親ノードに、前記ノードを強制的に検出させ、そうでない場合、処理を終了させるための第三送信ユニットを更に含む、ノード。
【請求項１３】
請求項12に記載のノードであって、
前記第三統計ユニットの統計結果と、返答消息を返していない有効検出親ノードの個数との和が依然として前記第四閾値未満の時に、第三所定ストラテジーに基づいて隣接ノードリストから一部の隣接ノードを選択するための第三選択ユニット；及び
選択した隣接ノードに状態検出強制リクエストパケットを送信し、該選択した隣接ノードに、前記ノードに対して故障検出を行わせるための第四送信ユニットを更に含む、ノード。
【請求項１４】
請求項12に記載のノードであって、
他のノードが送信した、前記ノードの情報を含む状態検出強制リクエストパケットを受信し、前記其他ノードに返答情報を返すための第三受信ユニット；及び
隣接ノードリストを更新し、他のノードに対応するノード類型を特定値に変更するための第五更新ユニットを更に含む、ノード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信技術分野に関し、特に、マルチホップネットワークの故障検出方法及びノードに関する。
【背景技術】
【０００２】
無線マルチホップネットワークは、データ処理、ネットワーク通信などのモジュールを含む小型ノードにより無線リンクの組織方式で構成されるネットワーク形態である。無線伝送環境が複雑で変化しやすいため、無線リンクが多くの場合にはかなり弱くなってしまう。また、限られたノードの能力（電池による供電など）、例えば、ノードのエネルギーが消耗し尽くすことによるノード失効、モジュール故障なども、しょっちゅう、通信が中断して、誤った情報の受信が発生してしまうなどの問題を引き起こし、これにより、制御センターが、誤った判断を行い、ネットワークのサービス品質を低下させてしまう。
【０００３】
故障検出の方法としては、周囲の全ての隣接ノードが周期的に送信したHELLOパケットをモニタリングすることで、周囲の各ノードが正常に動作しているかどうか、及び、周囲のノードとの間のリンク接続状況が正常であるかどうかを判断するというものがある。
【０００４】
図1は、従来のHELLOパケットを周期的に送信することを示す図である。図1に示すように、ノードN1、N2はともにノードPの隣接ノードであり、ネットワーク稼働の全過程において、全てのノードは、送信側として一定の時間間隔を以て外へ周期的にHELLOパケットをブロードキャスト(Broadcast)することにより、周囲のノードに自分の状態を通知する。その同時に、全てのノード（例えば、ノードP）は、受信側（又は、隣接ノードの状態をモニタリングする側）として、周囲の全ての隣接ノードのHELLOパケットを連続して受信することにより、周囲の全てのノード、及び、周囲の全ての隣接ノードとの間のリンク状況をモニタリングする。しかし、無線伝送環境が不安定であるため、ネットワーク中の幾つかのノードは、伝送リンクの状況に応じて、たびたび、自分の隣接ノードから新しい親ノード（parent  node）を選び、そして、自分の上りリンクを切り替えることにより、ネットワーク制御側（Gateway）との間のデータ伝送の安定性を保証する。また、切り替えられる経路は、周囲の全ての隣接ノードではなく、周囲の幾つかの隣接ノードのみとの間のリンクに集中する。
【０００５】
図2は、多経路選択を示す図である。図2に示すように、ノードN1〜N6はすべてノードPの隣接ノードである。伝送環境の影響のため、ノードPの上り経路は、リンク（P-N1）、リンク（P-N2）、リンク（P-N3）の間において切り替え、これにより、ノードPのデータ、及び、ノードPが転送するデータが、ネットワーク制御側（Gateway）に正常に到着し得ることを保証するが、他の隣接ノードとの間のリンク、例えば、リンク（P-N4）、リンク（P-N5）、リンク（P-N6）は、ノードPがデータを伝送するための上りリンクとして選択されない。従来のノード故障診断方法では、各ノードは、周期的なHELLOパケットにより、周囲の全ての隣接ノード間のリンク状況をモニタリングするが、これらのリンクのうち、一部のリンクの選択確率はとても小さい（又は、ぜんぜん選択されない）ため、これらの選択確率がとても小さいリンクの状態を同時に検出すると、故障検出のための通信コストが大き過ぎるようになってしまう。また、ネットワークのパフォーマンスについて言えば、ネットワーク中の故障を検出するための故障検出プロセスは、ネットワーク中の正常なデータ伝送に影響を与え、ネットワークのサービス量の増大、データパケットの紛失、ノードのエネルギー消耗の増大などの問題を来すこともある。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明の目的は、ネットワーク制御側(Gateway)がリアルタイムにネットワーク状態を正確に把握し、ネットワークシステムの過大なコストを低減させ、これにより、ネットワーク全体のサービスのパフォーマンスを向上させることができるマルチホップネットワークの故障検出方法及びノードを提供することにある。
【課題を解決するための手段】
【０００７】
上述した目的を達成するために、本発明の一側面によれば、故障検出方法が提供され、前記方法は、マルチホップネットワークにおけるノードに用いられ、前記方法は、
第一所定ストラテジーに基づいて、前記ノードからゲイトウエイへの全てのリンクから、所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応するノードを有効検出親ノードとし；
前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリストにおける故障検出情報を更新し；及び
受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うことを含む。
【０００８】
本発明の有益な効果は、本発明の実施例によるマルチホップネットワークの故障検出方法及びノードにより、ネットワーク制御側(Gateway)が、リアルタイムにネットワーク状態を正確に把握し、ネットワークシステムの過大なコストを低減させることができ、これにより、ネットワーク全体のサービスのパフォーマンスを向上させることができる。
【図面の簡単な説明】
【０００９】
【図１】マルチホップネットワークノード間におけるHELLOパケット周期送信を示す図である。
【図２】マルチホップネットワークにおける多経路選択を示す図である。
【図３】本発明の実施例1における故障検出方法のフローチャートである。
【図４】本発明の実施例1におけるステップ303の実現方法のフローチャートである。
【図５】本発明の実施例1における有効検出リンク選定を示す図である。
【図６】本発明の実施例2における故障検出方法のフローチャートである。
【図７】本発明の実施例2における状態検出リクエストパケットのフレーム構成を示す図である。
【図８】本発明の実施例2における状態検出リクエストを示す図である。
【図９】本発明の実施例2における具体例の検出状態を示す図である。
【図１０Ａ】本発明の実施例3における故障検出方法のフローチャートである。
【図１０Ｂ】本発明の実施例3における故障検出方法の他のフローチャートである。
【図１１】本発明の実施例3における返答フレームの構成を示す図である。
【図１２】本発明の実施例3における状態検出強制リクエストパケットのフレーム構成を示す図である。
【図１３】本発明の実施例3における有効検出ペアを示す図である。
【図１４】本発明の実施例3における他の有効検出ペアを示す図である；
【図１５】本発明の実施例4におけるマルチホップネットワーク中のノード構成を示す図である。
【図１６】本発明の実施例4における第一検出ユニット1504の構成を示す図である。
【発明を実施するための形態】
【００１０】
以下、添付した図面を参照しながら、本発明を実施するための形態を詳しく説明する。
【００１１】
なお、当業者が本発明の原理及び実施形態を容易に理解し得るために、以下、マルチホップネットワークが無線センサーネットワークである場合を例とし、本発明の実施例よる方法及びノードについて説明する。そのうち、ネットワーク中の全てのノードは、既に上りルーティングを確立しており、即ち、全てのノードは、Gatewayとの通信に必要な親ノード情報を既に取得しているとする。
【実施例１】
【００１２】
図3は、本発明の実施例における故障検出方法のフローチャートであり、該方法は、センサーネットワーク中のノード（第一ノード）に用いられる。図3に示すように、該方法は、次のステップを含む。
【００１３】
ステップ301：第一所定ストラテジーに基づいて、前記ノードからゲイトウエイへの全てのリンクから、所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応するノードを有効検出親ノードとし；
ステップ302：前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリストにおける故障検出情報を更新し；
ステップ303：受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行う。
【００１４】
ステップ301では、該第一所定ストラテジーは、前記ノードからゲイトウエイへの各リンクのうちルーティングのコストが最小であるというストラテジーと設定されてもよく、また、前記第一所定ストラテジーは、前記ノードからゲイトウエイへ各リンクのうちリンクの経路が最も短いというストラテジーと設定されてもよいが、本実施例は、これに限定されない。
【００１５】
本実施例では、各ノードは隣接ノードリストを持ち、該隣接ノードリストには該ノードの全ての隣接ノードの故障検出情報が記録され、例えば、情報項目の方式で記憶されてもよく、各情報項目は、一つの隣接ノードに対応し、該隣接ノードのID、最新更新時間、HELLOパケットの統計値、リンク類型、リンク状態、ノード類型、ノード状態などを含んでもよい。そのうち、最新更新時間とは、該隣接ノードが送信したHELLOパケットを受信した最新時間を指す。HELLOパケットの統計値とは、該隣接ノードのタイマーによる所定時間内に受信した、該隣接ノードが送信したHELLOパケットの個数を指す。リンク類型とは、自ノードと該隣接ノードとの間のリンクが有効検出リンクとして選択されているかどうかを指し、例えば、“0”により、初期値を示してもよく、又は、有効検出リンクとして選択されていないことを示してもよく；“1”により、有効検出リンクとして選択されていることを示してもよく；“2”により、特殊な場合、例えば、診断ペア（診断ペアについては、次の実施例で詳細に説明する。）を形成した場合を示してもよい。リンク状態とは、自ノードから該隣接ノードへのリンクが故障状態にあるかどうかを指し、例えば、“0”により、初期値を示してもよく；“-1”により、疑似故障を示してもよく；“-2”により、故障を示してもよく；“1”により、無故障を示してもよい。ノード類型とは、該隣接ノードが有効検出親ノード（有効検出親ノード、及び、検出ペア形成プロセスにおいて逆方向に検出を行う子ノード（即ち、特殊な場合に対応するノード）を含む。）として選択されているかどうかを指し、例えば、“0”により、初期値を示してもよく、又は、有効検出親ノードとして選択されていないことを示しておよく；“1”により、有効検出親ノードとして選択されていることを示してもよく；“2”により、特殊な場合、例えば、前述の診断ペアの場合を示してもよい。ノード状態とは、該隣接ノードが故障状態にあるかどうかを指し、例えば、“0”により、初期値を示してもよく；“-1”により、故障を示してもよく；“1”により、無故障を示してもよい。
【００１６】
表1に示すのは、隣接ノードリストの一例である。
【表１】
2015035807.tif 000003
【００１７】
本実施例では、ノードの構成について言えば、各ノードは、このような隣接ノードリストを持つ必要があり、また、受信した、隣接ノードが送信したHELLOパケットに基づいて、該隣接ノードリスト中の該HELLOパケットに対応する送信ノードの情報項目（本実施例では、故障検出情報という）に対してリアルタイムに更新を行う必要がある。
【００１８】
そのうち、このような隣接ノードリストを作成するために、本実施例では、該故障検出方法は、更に、受信したHELLOパケットに基づいて隣接ノードリストを更新するステップを含む。例えば、一つのノード（第一ノードともいう）が他のノード（隣接ノードという）から送信したHELLOパケットを受信した時に、該隣接ノードの情報が既に第一ノードの隣接ノードリストにあった場合、該第一ノードは、直接、受信したHELLOパケットに基づいて、該HELLOパケットの送信ノード（即ち、該隣接ノード）に対応する情報を直接更新すればよく；該隣接ノードの情報が第一ノードの隣接ノードリストにない場合、該第一ノードは、該隣接ノードの情報を隣接ノードリストに追加し、即ち、隣接ノードリストに、該隣接ノードに対応する新しい情報項目を追加し、それは、該隣接ノードID、最新更新時間、HELLOパケットの数の統計値などを含み、また、該隣接ノードに対応する情報項目のリンク類型及び/又は状態、候選ノード類型及び/又は状態を初期化し、例えば、前述のリンク及び/又はノードの類型及び/又は状態に、すべて、初期値を示す“0”を付ける。
【００１９】
そのうち、表1に示す例は、例示だけであり、本発明の実施例は、これに限定されず、例えば、最新更新時間は、省略してもよく、リンク類型及びノード類型は、合併してもよく、具体的には、実際のニーズに応じて決定してもよい。
【００２０】
ステップ302では、有効検出リンク及び有効検出親ノードを確定した後に、これに基づいて、前記ノードの隣接ノードリスト中の故障検出情報を更新してもよく、例えば、前記隣接ノードリストのうち、前記有効検出リンク及び有効検出親ノードに対応する類型を、“有効”を示す値に変更してもよい。例えば、対応する項目のLink  Type/statusを、所期値の“0”から“1”に変更し、これにより、このリンクが有効検出リンクであることを示し、その同時に、対応する項目のCandidate  node  Type/statusを、所期値の“0”から“1”に変更し、これにより、このノードが有効検出親ノードであることを示してもよい。
【００２１】
ステップ303では、有効検出リンク及び有効検出親ノードを確定したら、受信したHELLOパケットに基づいて、該有効検出リンク及び有効検出親ノードに対して故障検出を行ってもよい。
【００２２】
図4は、ステップ303で故障検出を行う方法のフローチャートであり、図4に示すように、該方法は、次のステップを含む。
【００２３】
ステップ401：受信したHELLOパケットの個数を統計により取得し；
ステップ402：前記HELLOパケットの送信ノードにおける所定タイマによる所定時間内に受信した、前記HELLOパケットの送信ノードが送信したHELLOパケットの個数が、第一閾値よりも小さい場合、前記ノードから前記HELLOパケットの送信ノードへのリンクが疑似故障であると確定する。
【００２４】
そのうち、前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に受信しした、前記HELLOパケットの送信ノードが送信したHELLOパケットの個数が前記第一閾値以上である場合、前記隣接ノードリストを更新し、前記送信ノードが対応するHELLOパケットの統計回数を0にリセットし、また、前記送信ノードにおける所定タイマーをもリセットする（ステップ407）。そして、統計を再び行う。
【００２５】
そのうち、前記ノード（第一ノード）の隣接ノードリストにおける各情報項目に対応して、第一ノードは、更に、隣接ノードリストにおける各隣接ノードのために一つのタイマー（Timer）を設置し、設定時間Tに達しているかどうかを判定してもよい。Tに達する前に、該隣接ノードからのHELLOパケットをモニタリングし、そして、受信したHELLOパケットの個数を算出し、隣接ノードリストのHello  count欄に入れる。Tに達している時に、連続して受信したHELLOパケット数が閾値M（第一閾値）に達した場合、この隣接ノードが対応するHello  count欄の値を0にリセットし、次の状態のモニタリングプロセスを再び開始し、即ち、タイマーをリセットする。連続して受信したHELLOパケット数が閾値M未満である場合、このリンクを疑似故障リンクと見なす。
【００２６】
一例では、第一ノードから前記隣接ノードへのリンクが疑似故障であると確定した後に、前記方法は、更に、次のステップを含む。
【００２７】
ステップ403：前記隣接ノードリストをルックアップすることにより、前記疑似故障のリンクが有効検出リンクであるかどうかを確定し、はいの場合、ステップ404を行い、そうでない場合、ステップ405を行う。
【００２８】
ステップ404：前記隣接ノードリストを更新し、前記リンクのリンク状態を疑似故障に変更し、且つ、該有効検出リンクに対応する有効検出親ノードに対してのノード故障検出を起動する。
【００２９】
そのうち、疑似故障が発生したリンクが有効検出リンクであると確定したため、即ち、それに対して故障検出を行う必要があるため、本実施例では、故障原因（リンク故障又はノード故障）を確定するために、ノード故障検出を更に起動する。そのうち、ノード故障検出の方法については、本実施例では限定せず、例えば、従来のノード故障検出方法を採用して、該疑似故障のリンクに対応するノード（該疑似故障リンクに接続されるノード）に対してノード故障検出を行ってもよい。
【００３０】
そのうち、ノード故障であると確定した場合、これに基づいて隣接ノードリストを更新してもよく、例えば、隣接ノードリスト中の該リンクに対応するノードの状態を、“故障”を示す状態に変更してもよい（ステップ406）。そのうち、隣接ノードリスト中の該リンクの状態（既に“疑似故障”の状態になっている）については、変更してもよく、変更しなくてもよい。その理由は、ノード故障であるため、該ノードに接続されるリンクも不可用状態にあり、よって、リンク故障でなくても、その状態を“疑似故障”から“無故障”に変更する必要がないとのことにある。
【００３１】
例えば、疑似故障であると確定した後に、該項目に対応するLink  Type/status欄をチェックしてもよく、その値が1であれば（即ち、現在のリンクが有効リンクであれば）、対応するLink  Type項目を値の1から-1に変更し、これにより、現在の有効リンクが疑似故障リンクであることを示し、そして、有効検出親ノードに対してのノード故障検出メカニズム（又は、状態問い合わせメカニズム）を起動し、故障情報を収集する。ノード故障検出の結果が有効検出親ノード故障である時に、Candidate  parent  status項目を-1に変更し、ノード故障であることを示す。
【００３２】
ステップ405：前記隣接ノードリストを更新し、前記リンクのリンク状態を疑似故障に変更する。
【００３３】
そのうち、疑似故障が発生したリンクが有効検出リンクでないと確定したため、即ち、それに対して故障検出を行う必要がないため、本実施例では、隣接ノードリストを更新するだけでよく、例えば、隣接ノードリスト中の該リンクに対応する状態を、“疑似故障”を示す値に変更するが、ノード故障検出を起動しない。
【００３４】
例えば、このリンクのLink  Type/status項目が0であれば（即ち、現在のリンクが非有効リンクであれば）、Link  Type/status項目を値の0から-1に変更し、これにより、このリンクが疑似故障リンクであることを示すが、ノード故障検出メカニズムを起動しない。
【００３５】
本実施例では、ネットワーク中の各ノードは、周期的にHELLOパケットを送信し、周囲のノードに自分の状態を通知し、周囲のノードは、受信した周期性のHELLOパケットに基づて、その周囲のノードの状態及びその周囲のノードとの間のリンク状況に対してモニタリングを行う。幾つかのノードからGatewayへ伝送したデータを幾つかの経路のみにおいて切り替えることができるので、各ノードは、上りデータを正常に伝送し得る幾つかの経路状況のみをモニタリングすればよく、他の隣接ノードとの間の選択されていない経路をモニタリングする必要がない。よって、本実施例では、各ノードは、周囲のリンクのうち、利用率が最も高いK個のリンクの状態のみをモニタリングし、このK個のリンクは、ステップ301で第一所定ストラテジーに基づいて選択した所定数のリンクであり、ここでの第一所定ストラテジーとは、リンクの利用率が最も高いというものであり、しかし、上述のように、本実施例は、これに限定されず、例えば、他のストラテジーに基づいてこのK個の待測リンク（本実施例では、「被測リンク」、「有効検出リンク」なども称される）を選択してもよく、例えば、Gatewayへのルーティングコスト（route  cost）が最小である経路に変更されたK個の経路のみをモニタリングしてもよい。本実施例では、K個の被選リンクを有効リンク（Effective  links)と称し、このK個のリンクに接続されるK個の親ノードを現在のノードの有効親ノード（Effective  parent）を称する。
【００３６】
図5は、本実施例における有効検出リンクの選定を示す図であり、図5に示すように、リンク(P1-N1)、リンク(P1-N2)、リンク(P1-N3)は、ノードP1が選定した有効検出リンク（Effective  links）であり、ノードN1、N2、N3は、ノードP1が選定した有効検出親ノード(Candidate  parent)である。リンク（P2-N4）、リンク（P2-P1）、リンク（P2-N5）は、ノードP2が選定した有効検出リンク（Effective  links）であり、ノードN4、P1、N5は、ノードP2が選定した有効検出親ノード（Candidate  parent）である。
【００３７】
本実施例の故障検出方法により、一部のリンクのみを選択して故障検出を行うので、制御側(Gateway)は、アルタイムにネットワーク状態を正確に把握し、ネットワークシステムの過大なコストを低減させることができるため、ネットワーク全体のサービスのパフォーマンスを向上させることができる。
【００３８】
本発明の実施例の一つの特殊な応用場面では、幾つかのノード（第一ノード）の子ノードの数が少なく、ひいてはゼロであり、この時に、実施例1の技術案によれば、これらのノード（第一ノード）に対して故障検出を行うノード（子ノード）がない可能性があり、このような問題を解決するために、本発明の実施例は、更に、故障検出方法を次の実施例2に記載のように提供する。
【実施例２】
【００３９】
本発明の実施例2は、更に、故障検出方法を提供し、該方法は、マルチホップネットワーク中のノード（第一ノード）に用いられる。図6は、該方法のフローチャートである。図6に示すように、該方法は、次のステップを含む。
【００４０】
ステップ601：第一所定ストラテジーに基づいて、前記ノード（第一ノード）からゲイトウエイへの全てのリンクから、所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応するノードを有効検出親ノードとし；
ステップ602：前記有効検出リンク及び前記有効検出親ノードに基づいて、前記第一ノードの隣接ノードリスト中の故障検出情報を更新し；
ステップ603：受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行う。
【００４１】
そのうち、ステップ601〜603の実施方式は、実施例1中のステップ301〜303の実施方式とは同じであるため、ここでは、その内容の記載を省略する。
【００４２】
そのうち、前記方法は、更に次のステップを含む。
【００４３】
ステップ604：前記第一ノードは、受信したHELLOパケットに基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し、統計により取得された結果が第二閾値よりも小さい時に、自分の有効検出親ノードに、状態検出リクエストパケットを送信し、これにより、自分の有効検出親ノードは、それに基づいて、自分の状態を検出する。
【００４４】
本実施例では、某ノード（第一ノード）の子ノードの数が少なすぎて、前記第一ノードに対して故障検出を行う隣接ノードがないとの問題を解決するために、該第一ノードは、有効リンク（Effective  links）を選定するプロセスが完成した後に、自分の有効検出親ノード（Candidate  parent）ID情報をHELLOパケットに追加し、そして、このHELLOパケットを周囲にブロードキャスト（Broadcast）する。
【００４５】
本実施例では、上述の類型のHELLOパケットを受信した隣接ノードは、パケット内のCandidate  parent情報が自分の情報と一致するかどうかを判定し、情報が一致すると判定した場合、自分が、このHELLOパケットのソースノード（送信ノード）が選定した有効検出親ノードであると確定する。
【００４６】
一例では、該隣接ノードは、受信したHELLOパケットの情報に基づいて、自分を有効検出親ノードとして選定した子ノードの個数を統計により取得し（即ち、幾つかの子ノードが自分の状態に対いて検出したかを統計により取得する）、子ノードの数が閾値L（第二閾値）よりも小さい場合、それは、現在、該隣接ノードの自分の状態を十分に検出して貰うことができないとのことを表す。このようなノードについては、有効リンクを選定した後（即ち、ステップ601を行った後）に、有効親ノードに状態検出リクエストパケット（Monitoring  Request）をブロードキャストし、その有効親ノードがこのノードの故障検出を行うようにリクエストする。該隣接ノードの有効検出親ノードは、該状態検出リクエストパケットを受信した後に、この隣接ノードの状態を検出し、且つ、該隣接ノードの有効検出親ノードは、その同時に、その隣接ノードリストを更新し、例えば、隣接ノードリスト中の対応る項目のLink  Type及びNode  Typeを特定値例えば“2”に更新し、これにより、該隣接ノードに対して検出を行う必要があることを表し、しかし、該隣接ノードは、その親ノードでなく、その子ノードである。
【００４７】
図7は、本発明の実施例における状態検出リクエストパケットのフレーム構成を示す図であり、図7に示すように、該状態検出リクエストパケットは、ブロードキャストヘッダー（Broadcast  header）、有効検出親ノードID（Candidate  parent  ID  1、Candidate  parent  ID  など）を含む。そのうち、ブロードキャストヘッダーは、更に、プリアンブル（Preamble）、制御フレーム（Control  Frame）、伝送アドレス（Transmitter  ID）、フレームチェックシーケンス（FCS、Frame  Check  Sequence）を含む。
【００４８】
図8は、状態検出リクエストを示す図であり、図8に示すように、ノードP1は、それぞれ、その親ノードN1、N2及びN3に状態検出リクエストパケットを送信し、その親ノードN1、N2、N3に、それに対して故障検出を行うようにリクエストする。
【００４９】
本実施例の方法をより明確にするために、以下、具体例を基に、本実施例の方法について詳細に説明する。該具体例では、各ノードが、Gatewayへのルーティングコストに従って、有効検出リンクの選択を行うことを例とするが、本実施例は、これに限定されず、具体的には、実施例1に記載のようであるため、ここでは詳しい説明を省略する。
【００５０】
図9は、該具体例の検出状態を示す図であり、図9に示すように、各ノードは、HELLOパケットを受信することにより、自分に対して検出メカニズムを形成した子ノードの個数を統計により取得する。全てのノードは、Gatewayへのルーティングコストに従って有効リンクの選択を行っているので、統計プロセスにおいて、幾つかのノードは、自分が何れの子ノードの有効親ノードにもなっていないこと（即ち、何れの子ノードにより有効親ノードとして選択されていないこと）を発見し得る。例えば、ノードN12は、ノードN1、N2、N3を有効親ノードとして選定し、そして、それらの状態に対して検出を行う。しかし、ノードN12は、受信したHELLOパケット情報をチェックすることにより、有効リンク選択のプロセスにおいて、自分が何れのノードにより有効親ノードとして選択されず、自分（ノードN12）の状態に対してリアルタイムに正確な検出を行う子ノードがないことを発見した。この場合、本実施例の方法により、ノードN12は、自分の有効検出親ノードの情報を持つ状態検出リクエストパケットをブロードキャストし、自分の有効検出親ノードに、ノードN12に対して逆方向状態検出メカニズムを形成するようにリクエストすることができる。
【００５１】
本実施例の方法によれば、幾つかのノード（第一ノード）が子ノードを有しなくても、有効検出経路を形成することができるので、このようなノードが有効な検出をして貰うことができないとの問題を回避し、且つ、ネットワークシステムの過大なコストを低減させることができるので、ネットワーク全体のサービスのパフォーマンスを向上させることができる。
【００５２】
本実施例の一つの特殊な応用場面では、有効検出親ノードは、通常、複数の子ノードを有するため、複数の子ノードの有効検出親ノードになり、それ（前記有効検出親ノード）は、通常、複数の子ノードからのHELLOパケットを同時に受信し、それらの子ノードと有効検出ペアを形成するようにリクエストされる。しかし、多くの子ノードを選択して状態検出を行うと、過大なネットワークコストをもたらしてしまうので、このよう問題を解決するために、本発明の実施例は、更に、故障検出方法を次の実施例3に記載にように提供する。
【実施例３】
【００５３】
本発明の実施例3は更に故障検出方法を提供し、該方法はマルチホップネットワーク中のノード（第一ノード）に用いられる。
【００５４】
図10Aは、該方法の一つのフローチャートであり、図10Aに示すように、該方法は、次のステップを含む。
【００５５】
ステップ1001：第一所定ストラテジーに基づいて、前記ノード（第一ノード）からゲイトウエイへの全てのリンクから、所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応するノードを有効検出親ノードとし；
ステップ1002：前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリスト中の故障検出情報を更新し；
ステップ1003：受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行い；
ステップ1004：前記ノードは、受信した前記HELLOパケットに基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し、そして、統計の結果が第三閾値よりも大きい時に、一部の子ノードを選択して診断ペアを形成し、そして、前記選択した一部の子ノードに返答情報を送信する。
【００５６】
図10Bは、該方法のもう一つのフローチャートである。図10Bに示すように、該方法は、次のステップを含む。
【００５７】
ステップ1001：第一所定ストラテジーに基づいて、前記ノード（第一ノード）からゲイトウエイへの全てのリンクから、所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応するノードを有効検出親ノードとし；
ステップ1002：前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリスト中の故障検出情報を更新し；
ステップ1003：受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行い；
ステップ1004’：前記ノード（第一ノード）は、自分の有効検出親ノード情報を自分のHELLOパケットに追加し、そして、前記HELLOパケットをブロードキャストし、これにより、該HELLOパケットを受信したノード（有効検出親ノードを含む）は、自分を有効検出親ノードとした子ノードの（有効検出親ノードの）個数を統計により取得し、そして、統計の結果が第三閾値よりも大きい時に、一部の子ノード（の有効検出親ノード）を選択して診断ペアを形成し、そして、前記選択した一部の（有効検出親ノードの）子ノードに返答情報を送信する。
【００５８】
図10A及び図10Bに示す方法では、ステップ1001〜1003の実施は、実施例1におけるステップ301〜303の実施とは同じであるため、ここでは詳しい説明を省略する。
【００５９】
また、そのうち、ステップ1004’は、HELLOパケットのブロードキャストの角度から述べられ、ステップ1004は、HELLOパケットの受信の角度から述べられた。以下、詳細に説明する。
【００６０】
本実施例では、某ノードは、子ノードにより有効検出親ノードとして選択されると同時に、自分が選定した有効検出親ノード（Candidate  parent）ID情報をHELLOパケットに追加することもでき、そして、このようなHELLOパケットを周囲にブロードキャスト（Broadcast）し、そして、自分の有効検出親ノードからの返答を待ち、これにより、自分の有効検出親ノードと、一対の互いに状態検出を行える有効状態検出ペア(Detection  pair)を形成するようにリクエストすることができる（ステップ1004’）。
【００６１】
本実施例では、HELLOパケットを受信したノードによる統計の結果がY(第三閾値)よりも大きい時に、某ノードが送信したHELLOパケットを受信した有効検出親ノードは、第二所定ストラテジーに基づいて、一部の子ノードを選択して返答メッセージを送信し、これらの子ノードと有効検出ペアを形成していることを表す（ステップ1004）。また、このような検出ペアの特殊な場合を表すために、該ノードは、更に、その隣接ノードリスト中の対応する項目のLink  Type及びNode  Typeを特定の値例えば“2”に変更してもよい。そのうち、第二所定ストラテジーは、“先着”原則であってよく、例えば、先着原則に従って、HELLOパケットが現在のノード（即ち、有効親ノード）に最も早く到着したC個の子ノードを選択してもよく、又は、“RSSI（Received  Signal  Strength  Indication、受信信号強度指示）値に従う”との原則であってよく、例えば、RSSI値に従うとの原則に従って、現在のノードまでのRSSI値が最大であるC個の子ノードを選択してもよく、しかし、実施例は、これに限定されない。
【００６２】
本実施例では、図11は、返答(Reply)メッセージのフレーム構成を示す図であり、図11に示すように、該Replyフレームは、ユニキャストヘッダー（Unicast  header）、有効検出親ノードID（Candidate  parent  ID）、リクエストノードID(Request  node  ID)を含む。そのうち、ユニキャストヘッダーは、更に、プリアンブル（Preamble）、制御フレーム（Control  Frame）、伝送アドレス（Transmitter  ID）、受信アドレス(Receiver ID)、フレームチェックシーケンス（FCS、Frame  Check  Sequence）を含む。
【００６３】
本実施例では、HELLOパケットを送信するノードについては、図10Bを参照し；該ノードが選定した有効検出親ノードが返答したreplyを受信した場合、該ノードは、自分が選定した有効検出親ノードと検出ペアを形成し；該ノードが選定した有効検出親ノードが返答したreplyを受信していない場合、これは、該ノードが選定した有効検出親ノードが該ノードと検出ペアを形成して該ノードに対して状態を検出することができないとのことを表し、この場合、該ノードは、その状態を検出するための他のノードを再び選択する必要があり、よって、前記方法は、更に次のステップを含む。
【００６４】
ステップ1005：前記ノードは、自分の有効検出親ノード情報を自分のHELLOパケットに追加し、また、前記HELLOパケットをブロードキャストした後に、自分の有効検出親ノードが返した返答情報を受信しているかどうかを判断し、はいの場合、ステップ1006を行い、そうでない場合、ステップ1007を行い；
ステップ1006：前記ノードは、前記返答情報を送信した有効検出親ノードと診断ペアを形成し；
ステップ1007：前記ノードを有効検出親ノードとして選択した子ノードの個数と、返答情報を返した有効検出親ノードの個数との和が第四閾値よりも小さいかどうかを判断し、はいの場合、返答情報未受信の有効検出親ノードの情報を含む状態検出強制リクエストパケットをブロードキャストし、返答情報を返してない該有効検出親ノードに、前記ノードを強制的に検出させ、そうでない場合、処理を終了させる。
【００６５】
そのうち、某ノードは、自分を有効親ノードとして選択し且つ自分に対して状態検出を行うAchild個の子ノードを有し、また、Aparent個の有効親ノードからのReply返答を受信し、即ち、その同時に自分に対して状態検出を行うAparent個の有効親ノードが存在すると仮定する。自分に対しての状態検出を形成した総ノードの個数(Aparent+Achild)が閾値N（第四閾値；某ノードの状態を検出する最小ノード数を表してもよい）以上である場合、自分に対して状態検出メカニズムを形成するノードが十分にあると表し、何れの操作をも行う必要がなく、逆に、両者の和が閾値N未満である場合、現在のノード対して状態検出を行うノードの数が不足していると表し、この場合、Reply未受信の有効親ノードの情報が追加された状態検出強制リクエストパケットをブロードキャストし、該リクエストパケット中の有効親ノードに、自分に対して状態検出を強制的に行わせる。状態検出強制リクエストパケットを受信した有効親ノードは、Replyを返答し、その子ノードと有効検出対（detection  pair）を形成し、そして、隣接ノードリスト中の対応する項目のLink  Type及びNode  Typeを特定値例えば“2”に変更し、これにより、このような特殊な場合を表す。
【００６６】
そのうち、前記ノードを有効検出親ノードとして選択した子ノードの個数、返答情報を返した有効検出親ノードの個数、及び、返答情報を返していない有効検出親ノードの個数の和が依然として前記第四閾値未満の場合、前記方法は、更に次のステップを含む。
【００６７】
ステップ1008：前記ノードは、第三所定ストラテジーに基づいて、隣接ノードリストから一部の隣接ノードを選択し；
ステップ1009：選択した隣接ノードに状態検出強制リクエストパケットを送信し、該選択した隣接ノードに、前記ノードに対して故障検出を強制的に行わせる。
【００６８】
一例では、Aparent、Achild、及び、返答メッセージを返していない有効検出親ノードの個数の和が依然としてN未満の場合、第三所定ストラテジーに基づいてその隣接ノードリストから一部の隣接ノードを選択し、選択した隣接ノードに状態検出強制リクエストパケットをブロードキャストし、該選択した隣接ノードに、前記ノードに対して故障検出を強制的に行わせ、選択した隣接ノードが、前記ノードがブロードキャストした状態検出強制リクエストパケットを受信した場合、該隣接ノードは、前記ノードの状態を検出し、且つ、その隣接ノードリスト中の前記ノードに対応する項目のLink  Type及びNode  Typeを特定値例えば“2”に更新する。そのうち、第三所定ストラテジーは、「前記Aparent、Achild、及び、返答メッセージを返していない有効検出親ノードの個数の和が閾値N以上になるまで」、或いは、「前記隣接ノードリスト中の隣接ノードが全て選択されるまで」と設定してもよいが、これに限定されない。
【００６９】
そのうち、図12は、状態検出強制リクエストフレームの構成を示す図であり、図12に示すように、該フレームは、ブロードキャストヘッダー（Broadcast  header）、有効検出親ノードID（Candidate  parent  ID  1、Candidate  parent  ID  2など）を含む。そのうち、ブロードキャストヘッダーは、更に、プリアンブル（Preamble）、制御フレーム（Control  Frame）、伝送アドレス（Transmitter  ID）、フレームチェックシーケンス（FCS、Frame  Check  Sequence）を含む。
【００７０】
本実施例の方法をより明確にするために、以下、具体例を基に、本実施例の方法を詳しく説明する。該具体例では、各ノードがGatewayへのルーティングコストに従って有効検出リンクの選択を行う場合を例とするが、本実施例は、これに限定されず、具的的には、実施例1に記載の通りであるため、ここでは詳しい説明を省略する。
【００７１】
図13は、有効検出ペアの形成例を示す図であり、図13に示すように、ノードN1は、子ノードP1、P2、P3、P4、P5により有効親ノードとして選択され、同時に、ノードN1は、P1、P2、P3、P4、P5からの、N1を有効親ノードとする情報を追加した、リクエストするためのHELLOパケットを受信する。しかし、ノードN1についは、多くの子ノードを選択して状態検出を行うと、過大なネットワークコストを引き起こすことがある。よって、“先着”の原則に従って、即ち、HELLOパケットが現在の有効親ノードに最も先に到着した一部の子ノード（P1、P2、P5）を選択し、有効親ノードN1はこれらにReplyを返答し、これらの子ノードと有効検出ペアを形成する。
【００７２】
図14は、有効検出ペアの他の形成例を示す図であり、図14に示すように、ノードN2は、子ノードP6、P7、P8により有効親ノードとして選択され、これらの子ノードは、N2に対してリアルタイムに状態検出を行う。同時に、ノードN2は、有効リンクの選択プロセスにおいて、ノードP1、P2、P3、P4、P5を自分の有効親ノードとして選択した。ノードN2は、ノードP1、P2、P3、P4、P5の情報を自分のHELLOパケットに追加し、そして、周囲の隣接ノードにブロードキャストし、これらの親ノードに、N2と有効検出ペアを形成するようにリクエストする。しかし、前述の“先着”の原則に従って、ノードN2は、全ての有効ノードからのReply返答を受信せず、一部のみの有効親ノードからのReplyを受信し、且つ、この一部のみの有効親ノードは、N2に対して状態検出を行う。N2は、自分と状態検出ペアを形成した有効親ノードの数（Aparent）及び子ノード数目（Achild）を統計により取得し、そして、両者の和と閾値Nとを比較し、両者の和が閾値N未満の場合、N2は、状態検出リクエストパケットをブロードキャストし、Replyを返していない有効親ノードに自分の状態を検出するようにリクエストする。自分と状態検出ペアを形成した有効親ノード数（Aparent）及び子ノード数目（Achild）と、返答メッセージを返していない有効検出親ノードの個数との和が依然として閾値N未満の場合、その隣接ノードQ1、Q2、Q3(非有効検出親ノード)から、一部の隣接ノード(第三所定ストラテジーを満足)を選択し、状態検出強制リクエストパケットをブロードキャストし、選択した隣接ノードに、自分の状態を強制的に検出させる。
【００７３】
本実施例の方法によれば、有効検出親ノードが大量の子ノードのHELLOパケットを受信してこれらの子ノードと有効検出ペアを形成するようにリクエストされる問題を解決することができ、且つ、ネットワークシステムの過大なコストを減少させ、ネットワーク全体のサービスのパフォーマンスを向上させることができる。
【実施例４】
【００７４】
本発明の実施例4は、更に、マルチホップネットワーク中のノードを提供し、該ノードが問題を解決する原理は、実施例1〜3の方法に類似するため、その具体的な実施は実施例1〜3の方法の実施を参照することができるので、ここでは、重複説明を省略する。
【００７５】
図15に示すのは、マルチホップネットワーク中のノード1500であり、そのうち、該ノード1500は、第一選択ユニット1501、第一更新ユニット1502、第一受信ユニット1503、第一検出ユニット1504を含む。
【００７６】
第一選択ユニット1501：第一所定ストラテジーに基づいて、前記ノードからゲイトウエイへの全てのリンクから、所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応するノードを有効検出親ノードとするために用いられ；
第一更新ユニット1502：第一選択ユニット1501が選択した前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリスト中の故障検出情報を更新するために用いられ；
第一受信ユニット1503：隣接ノードのHELLOパケットを受信するために用いられ；
第一検出ユニット1504：第一受信ユニット1503が受信したHELLOパケットに基づいて前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うために用いられる。
【００７７】
本実施例では、第一更新ユニット1502は、更に、前記隣接ノードリスト中の前記有効検出リンク及び有効検出親ノードに対応する類型を有効に変更するために用いられる。
【００７８】
図16は、第一検出ユニット1504の構成図であり、図16に示すように、第一検出ユニット1504は、更に、次のユニットを含む。
【００７９】
第一統計ユニット1601：前記第一受信ユニットが受信したHELLOパケットの個数を統計により取得するために用いられ；
第一確定ユニット1602：前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に該第一統計ユニット1601が取得した、前記第一受信ユニットが受信したHELLOパケットの個数が、第一閾値未満のとき、前記ノードから前記隣接ノードへのリンクが疑似故障であると確定する。
【００８０】
本実施例では、該第一検出ユニット1504は、更に、次のユニットを含む。
【００８１】
第二確定ユニット1603：前記隣接ノードリストをルックアップすることで、前記疑似故障のリンクが有効検出リンクであるかどうかを確定するために用いられ；
第二更新ユニット1604：第二確定ユニット1603が、前記疑似故障のリンクが有効検出リンクであると確定した時に、前記隣接ノードリストを更新し、また、前記リンクのリンク状態を疑似故障に変更するために用いられ；
第二検出ユニット1605：第二更新ユニット1604が前記隣接ノードリストを更新した後に、該有効検出リンクに対応する有効検出親ノードへのノード故障検出を起動するために用いられ；
第三更新ユニット1606：第二確定ユニット1603が、前記疑似故障のリンクが非有効検出リンクであると確定した時に、前記隣接ノードリストを更新し、また、前記リンクのリンク状態を疑似故障に変更するために用いられる。
【００８２】
本実施例では、第一検出ユニット1504は、更に、次のステップを含む。
【００８３】
第四更新ユニット1607：第二検出ユニット1605の検出結果が前記有効検出親ノード故障である時に、前記隣接ノードリストを更新し、また、前記有効検出親ノードの状態を故障に変更するために用いられる。
【００８４】
本実施例では、第一検出ユニット1504は、更に、リセット更新ユニット1608を含み、それは、前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に前記第一統計ユニットが取得したHELLOパケットの個数が前記第一閾値以上の時に、前記隣接ノードリストを更新し、前記送信ノードに対応するHELLOパケットの統計回数を０にリセットし、また、前記送信ノードにおける所定タイマーをリセットするために用いられる。
【００８５】
本実施例では、幾つかのノードは、自分らの有効検出親ノードの情報を自分らのHELLOパケットに追加し、そして、このようなHELLOパケットをブロードキャストすることができ、これにより、該HELLOパケットを受信したノードは、それに基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し、また、統計の結果に基づいて後続の処理を行い、例えば、統計の結果が第二閾値未満の時に、自分の有効検出親ノードに状態検出リクエストパケットを送信し、これにより、自分の有効検出親ノードに、自分の状態を検出させ、あるいは、統計の結果が第三閾値以上の時に、第二所定ストラテジーに基づいて一部のノードを選択して診断ペアを形成する。
【００８６】
本実施例では、該HELLOパケットを受信したノードとして、該ノード1500は、更に、次のユニットを含む。
【００８７】
第二統計ユニット1506：受信した、他のノードが送信した、該他のノードの有効検出親ノードの情報を含むHELLOパケットに基づいて、前記ノード（1500）を有効検出親ノードとした子ノードの個数を統計により取得するために用いられ；
第二送信ユニット1507：第二統計ユニット1506の統計結果が、個数が第二閾値未満である時に、前記ノードの有効検出親ノードに状態検出リクエストパケットを送信し、前記ノードの有効検出親ノードに、前記ノードに対して故障検出を行わせるようにリクエストするために用いられる。
【００８８】
第二送信ユニット1507は、更に、第二統計ユニット1506の統計結果が、個数が第三閾値以上である時に、第二所定ストラテジーに基づいて、前記子ノードから一部の子ノードを選択して診断ペアを形成し、選択した子ノードに返答情報を送信するために用いられる。
【００８９】
本実施例では、受信ノードとしての第一受信ユニット1503は、更に、他のノードが送信した状態検出リクエストパケットを受信することができ、本実施例の第一検出ユニット1504は、更に、該第一受信ユニット1503が、他のノードが送信した状態検出リクエストパケットを受信した時に、前記他のノードの状態を検出するために用いられ、本実施例の第一更新ユニット1502は、更に、このような場合に、隣接ノードリストを更新し、該他のノードに対応するノード類型を特定値に変更するために用いられれる。
【００９０】
本実施例では、該HELLOパケットを送信するノードとして、該ノード1500は、更に、次ののユニットを含む。
【００９１】
第一送信ユニット1505：上述のように、前記ノードの有効検出親ノードの情報を前記ノードのHELLOパケットに追加し、そして、前記HELLOパケットをブロードキャストし、前記HELLOパケットを受信した有効検出親ノードに、後続の処理を行わせるために用いられる。
【００９２】
本実施例では、このノードは、一部の有効検出親ノードが返した返答情報を受信することがあるので、本実施例では、該ノードは、更に、次のユニットを含んでもよい。
【００９３】
第二受信ユニット1508：前記ノードの有効検出親ノードが返した返答情報を受信するために用いられ；
第二選択ユニット1509：第二受信ユニット1508が前記ノードの有効検出親ノードの返した返答情報を受信した時に、該返答情報を送信した有効検出親ノードと診断ペアを形成するために用いられ；
第三統計ユニット1510：前記ノードを有効検出親ノードとして選択した子ノードの個数と、返答情報を返した有効検出親ノードの個数との和を統計により取得するために用いられ；
第三送信ユニット1511：第三統計ユニット1510の統計結果が、前記個数の和が第四閾値未満である場合に、返答情報未受信の有効検出親ノードの情報を含む状態検出強制リクエストパケットを送信し、返答情報を返していない有効検出親ノードに、前記ノードを強制的に検出させ、そうでない場合、処理を終了させるために用いられる。
【００９４】
本実施例では、該ノード1500は、更に、次のユニットを含んでもよい。
【００９５】
第三選択ユニット1512：第三統計ユニット1510の統計結果と、返答メッセージを返していない有効検出親ノードの個数との和が依然として前記第四閾値未満の時に、第三所定ストラテジーに基づいて、隣接ノードリストから一部の隣接ノードを選択するために用いられ；
第四送信ユニット1513：選択した隣接ノードに状態検出強制リクエストパケットを送信し、該選択した隣接ノードに、前記ノードに対して故障検出を強制的に行わせるために用いられる。
【００９６】
本実施例では、このような状態検出強制リクエストパケットを受信したノードとして、該ノード1500は、さらに、次のユニットを含んでもよい。
【００９７】
第三受信ユニット1514：他のノードが送信した、前記ノードの情報を含む状態検出強制リクエストパケットを受信した時に、前記他のノードに返答情報を返すために用いられ；
第五更新ユニット1515：隣接ノードリストを更新し、他のノードに対応するノード類型を特定値に更新するために用いられる。
【００９８】
本実施例のノードの各構成部分の機能は、実施例1〜3の方法の各ステップとは同じであるので、ここでは、詳しい説明を省略する。
【００９９】
本実施例の故障検出方法により、一部のみのリンクを選択して故障検出を行うので、制御側(Gateway)は、リアルタイムにネットワーク状態を正確に把握することができると同時に、幾つかのノードが子ノードを有しなくても、有効な検出経路を確立することができ、これにより、このようなノードが有効な検出をしてもらうことができず、また、有効検出親ノードが大量の子ノードからのHELLOパケットを受信して、これらの子ノードと有効検出ペアを形成するようにリクエストされる問題を解決し、ネットワークシステムの過大なコストを減少させ、ネットワーク全体のサービスのパフォーマンスを向上させることができる。
【０１００】
本発明の上述の方法及びノードは、ハードウェアにより実現されてもよく、ハードウェアとソフトウェアとの組み合わせにより実現されてもよい。また、本発明は、このようなコンピュータ可読なプログラムにも関し、即ち、該プログラムは、ロジック部により実行されている時に、該ロジック部に、上述の装置又は構成部品を実現させることができ、又は、該ロジック部に、上述の各種方法又はステップを実現させることができる。ロジック部品は、例えば、フィールドプログラマブルゲートアレイ部品、マイクロプロセッサ、コンピュータに用いる処理器などである。また、本発明は、さらに、上述のプログラムを記録している記憶媒体、例えば、ハードディスク、磁気ディスク、光ディスク、DVD、flashメモリ、磁気光ディスク、メモリカード、メモリスティックなどにも関する。
【０１０１】
また、上述の各実施例を含む実施形態に関し、更に以下の付記を開示する。
【０１０２】
（付記1）
故障検出方法であって、前記方法は、マルチホップネットワークにおけるノードに用いられ、前記方法は、
第一所定ストラテジーに基づいて、前記ノードからゲイトウエイへの全てのリンクから所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応する第二ノードを有効検出親ノードとし；
前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリストにおける故障検出情報を更新し；
受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うことを含む、方法。
【０１０３】
（付記2）
付記1に記載の方法であって、
前記ノードの隣接ノードリストにおける故障検出情報を更新するステップは、
前記隣接ノードリスト中の前記有効検出リンク及び有効検出親ノードに対応する類型を有効に変更することを含む、方法。
【０１０４】
（付記3）
付記1に記載の方法であって、
受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うステップは、
受信したHELLOパケットの個数を統計により取得し；
前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に前記HELLOパケットの個数が第一閾値未満である場合、前記第一ノードから前記隣接ノードへのリンクが疑似故障であると確定することを含む、方法。
【０１０５】
（付記4）
付記3に記載の方法であって、
前記ノードから前記隣接ノードへのリンクが疑似故障であると確定した後に、前記方法は、更に、
前記隣接ノードリストをルックアップし、前記疑似故障のリンクが有効検出リンクであるかどうかを確定し；
有効検出リンクである場合、前記隣接ノードリストを更新し、前記リンクのリンク状態を疑似故障に変更し、且つ、該有効検出リンクに対応する有効検出親ノードに対してのノード故障検出を起動し；
非有効検出リンクである場合、前記隣接ノードリストを更新し、前記リンクのリンク状態を疑似故障に変更することを含む、方法。
【０１０６】
（付記5）
付記3に記載の方法であって、
前記有効検出親ノードに対してノード故障検出を起動した後に、前記方法は、更に、
ノード故障検出結果が前記有効検出親ノード故障である場合、前記隣接ノードリストを更新し、前記有効検出親ノードの状態を故障に変更することを含む、方法。
【０１０７】
（付記6）
付記3に記載の方法であって、更に、
前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に前記HELLOパケットの個数が前記第一閾値以上である場合、前記隣接ノードリストを更新し、前記送信ノードに対応するHELLOパケットの統計回数を０にリセットし、また、前記送信ノードの所定タイマーをリセットすることを含む、方法。
【０１０８】
（付記7）
付記1に記載の方法であって、更に、
前記ノードが、自分の有効検出親ノードの情報を自分のHELLOパケットに追加し、前記HELLOパケットをブロードキャストし、これにより、前記HELLOパケットを受信した有効検出親ノードが、それ（前記HELLOパケット）に基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し、
前記ノードが、統計の結果が第二閾値未満である時に、自分の有効検出親ノードに状態検出リクエストパケットを送信し、自分の有効検出親ノードに、これ（前記状態検出リクエストパケット）に基づいて、自分の状態を検出させ、又は、統計の結果が第三閾値以上である時に、第二所定ストラテジーに基づいて一部の子ノードを選択して診断ペアを形成することを含む、方法。
【０１０９】
（付記8）
付記1に記載の方法であって、更に、
前記ノードが、受信したHELLOパケットに基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し；
前記子ノードの個数が第二閾値未満の場合、前記ノードが、自分の有効検出親ノードに状態検出リクエストパケットを送信し、自分の有効検出親ノードに、自分に対して故障検出を行せるようにリクエストし；
前記子ノードの個数が第三閾値以上の場合、前記ノードが、第二所定ストラテジーに基づいて前記子ノードから一部の子ノードを選択して診断ペアを形成し、選択した子ノードに返答情報を送信することを含む、方法。
【０１１０】
（付記9）
付記1に記載の方法であって、
前記ノードが、他のノードが送信した状態検出リクエストパケットを受信した場合、前記方法は、更に、
前記ノードが前記他のノードの状態を検出し、且つ、隣接ノードリストを更新し、該他のノードに対応するノード類型を特定値に変更することを含む、方法。
【０１１１】
（付記10）
付記7に記載の方法であって、更に、
前記ノードが、自分の有効検出親ノードが返した返答情報を受信した場合、前記ノードは、該返答情報を送信した有効検出親ノードと診断ペアを形成し；
前記ノードが、自分の有効検出親ノードが返した返答情報を受信しておらず、且つ、前記ノードを有効検出親ノードとして選択した子ノードの個数と、返答情報を返した有効検出親ノードの個数との和が第四閾値未満である場合、返答情報未受信の有効検出親ノードの情報を含む状態検出強制リクエストパケットを送信し、該返答情報を返していない有効検出親ノードに、前記ノードを強制的に検出させ、そうでない場合、処理を終了させることを含む、方法。
【０１１２】
（付記11）
付記10に記載の方法であって、
前記ノードを有効検出親ノードとして選択した子ノードの個数、返答情報を返した有効検出親ノードの個数、及び、前記返答情報を返していない有効検出親ノードの個数の和が依然として前記第四閾値未満の場合、前記方法は、更に、
前記ノードが、第三所定ストラテジーに基づいて、隣接ノードリストから一部の隣接ノードを選択し；
前記ノードが、選択した隣接ノードに状態検出強制リクエストパケットを送信し、該選択した隣接ノードに、前記ノードに対して故障検出を強制的に行せることを含む、方法。
【０１１３】
（付記12）
付記10に記載の方法であって、
前記ノードが、他のノードが送信した、前記ノードの情報を含む状態検出強制リクエストパケットを受信した場合、前記ノードは、前記他のノードに返答情報を返し、また、その隣接ノードリストを更新し、前記他のノードに対応するノード類型を特定値に変更することを含む、方法。
【０１１４】
（付記13）
マルチホップネットワークにおけるノードであって、
第一所定ストラテジーに基づいて、前記ノードからゲイトウエイへの全てのリンクから所定数のリンクを有効検出リンクとして選択し、選択したリンクに対応するノードを有効検出親ノードとするための第一選択ユニット；
前記第一選択ユニットが選択した前記有効検出リンク及び前記有効検出親ノードに基づいて、前記ノードの隣接ノードリストにおける故障検出情報を更新するための第一更新ユニット；
隣接ノードからのHELLOパケットを受信するための第一受信ユニット；
前記第一受信ユニットが受信したHELLOパケットに基づいて、前記有効検出リンク及び前記有効検出親ノードに対して故障検出を行うための第一検出ユニットを含む、ノード。
【０１１５】
（付記14）
付記13に記載のノードであって、
前記第一更新ユニットは、更に、前記隣接ノードリスト中の前記有効検出リンク及び有効検出親ノードに対応する類型を有効に変更するために用いられる、ノード。
【０１１６】
（付記15）
付記13に記載のノードであって、
前記第一検出ユニットは、更に、
前記第一受信ユニットが受信したHELLOパケットの個数を統計により取得するための第一統計ユニット；
前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に前記第一統計ユニットが取得したHELLOパケットの個数が第二閾値未満である時に、前記ノードから前記隣接ノードへのリンクが疑似故障であると確定するための第一確定ユニットを含む、ノード。
【０１１７】
（付記16）
付記15に記載のノードであって、
前記第一検出ユニットは、更に、
前記隣接ノードリストをルックアップし、前記疑似故障のリンクが有効検出リンクであるかどうかを確定するための第二確定ユニット；
前記第二確定ユニットが、前記疑似故障のリンクが効検出リンクであると確定した時に、前記隣接ノードリストを更新し、前記リンクのリンク状態を疑似故障に変更するための第二更新ユニット；
前記第二更新ユニットが前記隣接ノードリストを更新した後に、該有効検出リンクに対応効検出親ノードに対してのノード故障検出を起動するための第二検出ユニット；
前記第二確定ユニットが、前記疑似故障のリンクが非有効検出リンクであると確定した時に、前記隣接ノードリストを更新し、前記リンクのリンク状態を疑似故障に変更するための第三更新ユニットを含む、ノード。
【０１１８】
（付記17）
付記15に記載のノードであって、
前記第一検出ユニットは、更に、
前記第二検出ユニットの検出結果が前記有効検出親ノード故障である時に、前記隣接ノードリストを更新し、前記有効検出親ノードの状態を故障に変更するために用いられる、ノード。
【０１１９】
（付記18）
付記15に記載のノードであって、
前記第一検出ユニットは、更にリセット更新ユニットを含み、
前記リセット更新ユニットは、前記HELLOパケットの送信ノードにおける所定タイマーによる所定時間内に前記第一統計ユニットが取得したHELLOパケットの個数が前記第一閾値以上である時に、前記隣接ノードリストを更新し、前記送信ノードに対応するHELLOパケットの統計回数を０にリセットし、また、前記送信ノードの所定タイマーをリセットするために用いられる、ノード。
【０１２０】
（付記19）
付記13に記載のノードであって、更に、
前記ノードの有効検出親ノードの情報を前記ノードのHELLOパケットに追加し、前記HELLOパケットをブロードキャストする第一送信ユニットであって、前記HELLOパケットを受信した有効検出親ノードは、それ（前記HELLOパケット）に基づいて、自分を有効検出親ノードとした子ノードの個数を統計により取得し、前記第一送信ユニットは、統計の結果が第二閾値未満の時に、自分の有効検出親ノードに状態検出リクエストパケットを送信し、自分の有効検出親ノードに、これ（状態検出リクエストパケット）に基づいて自分の状態を検出させ、又は、統計の結果が第三閾値以上である時に、第二所定ストラテジーに基づいて一部の子ノードを選択して診断ペアを形成する、第一送信ユニットを含む、ノード。
【０１２１】
（付記20）
付記13に記載のノードであって、更に、
受信した、他のノードが送信した、該他のノードの有効検出親ノードの情報を含むHELLOパケットに基づいて、前記ノードを有効検出親ノードとした子ノードの個数を統計により取得するための第二統計ユニット；
前記第二統計ユニットの統計結果が、前記個数が第二閾値未満の時に、前記ノードの有効検出親ノードに状態検出リクエストパケットを送信し、前記ノードの有効検出親ノードに、前記ノードに対して故障検出を行わせるようにリクエストするための第二送信ユニットを含み、
前記第二送信ユニットは、更に、前記第二統計ユニットの統計結果が、前記個数が第三閾値以上である時に、第二所定ストラテジーに基づいて、前記子ノードから一部の子ノードを選択して診断ペアを形成し、そして、選択した子ノードに返答情報を送信するために用いられる、ノード。
【０１２２】
（付記21）
付記13に記載のノードであって、
前記第一検出ユニットは、更に、前記第一受信ユニットが、他のノードが送信した状態検出リクエストパケットを受信した時に、前記他のノードの状態を検出し、前記第一更新ユニットは、更に、隣接ノードリストを更新し、該他のノードに対応するノード類型を特定値に変更するために用いられる、ノード。
【０１２３】
（付記22）
付記19に記載のノードであって、更に、
前記ノードの有効検出親ノードが返した返答情報を受信するための第二受信ユニット；
前記第二受信ユニットが、前記ノードの有効検出親ノードが返した返答情報を受信した時に、該返答情報を返した有効検出親ノードと診断ペアを形成するための第二選択ユニット；
前記ノードを有効検出親ノードとした子ノードの個数と、返答情報を返した有効検出親ノードの個数との和を統計により取得するための第三統計ユニット；
前記第三統計ユニットの統計結果が、前記個数の和が第四閾値未満の場合に、返答情報未受信の有効検出親ノードの情報を含む状態検出強制リクエストパケットを送信し、該返答情報を返していない有効検出親ノードに、前記ノードを強制的に検出させ、そうでない場合、処理を終了させるための第三送信ユニットを含む、ノード。
【０１２４】
（付記23）
付記22に記載のノードであって、更に、
前記第三統計ユニットの統計結果と、返答消息を返していない有効検出親ノードの個数との和が依然として前記第四閾値未満の時に、第三所定ストラテジーに基づいて隣接ノードリストから一部の隣接ノードを選択するための第三選択ユニット；
選択した隣接ノードに状態検出強制リクエストパケットを送信し、該選択した隣接ノードに、前記ノードに対して故障検出を行わせるための第四送信ユニットを含む、ノード。
【０１２５】
（付記24）
付記22に記載のノードであって、更に、
他のノードが送信した、前記ノードの情報を含む状態検出強制リクエストパケットを受信し、前記其他ノードに返答情報を返すための第三受信ユニット；
隣接ノードリストを更新し、他のノードに対応するノード類型を特定値に変更するための第五更新ユニットを含む、ノード。
【０１２６】
以上、本発明の好ましい実施形態を説明したが、本発明はこの実施形態に限定されず、本発明の趣旨を離脱しない限り、本発明に対するあらゆる変更は本発明の技術的範囲に属する。
【図１】
2015035807.tif 000004
【図２】
2015035807.tif 000005
【図３】
2015035807.tif 000006
【図４】
2015035807.tif 000007
【図５】
2015035807.tif 000008
【図６】
2015035807.tif 000009
【図７】
2015035807.tif 000010
【図８】
2015035807.tif 000011
【図９】
2015035807.tif 000012
【図１０Ａ】
2015035807.tif 000013
【図１０Ｂ】
2015035807.tif 000014
【図１１】
2015035807.tif 000015
【図１２】
2015035807.tif 000016
【図１３】
2015035807.tif 000017
【図１４】
2015035807.tif 000018
【図１５】
2015035807.tif 000019
【図１６】
2015035807.tif 000020