(57)【要約】【課題】ネットワークの回線容量の消費を抑えるとともに、端末間の同期を前提とすることのないネットワークの故障検出方法を提供する。【解決手段】複数のノードにより構成されるネットワークの故障検出方法。同期が確立していない送信ノードと受信ノードを含む複数のノードにより構成される複数の伝送経路について通信に要する時間の仮値を算出する工程と、基準経路における仮値と、他の伝送経路の仮値との差と算出する工程と、基準経路と他の伝送経路との仮値の差を左辺に、それぞれの伝送経路についてそれぞれのノードの有無を表すマトリックスとノード間のリンクの通信に要する時間を表すマトリックスとの積を右辺に有する第１線形観測式を得る工程と、第１線形観測式について圧縮センシングに基づき最小化問題を解くことでネットワーク内の故障箇所を同定する工程と、を有する。【選択図】図２
2015154256.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードにより構成されるネットワークの故障検出方法であって、
互いに同期が確立していない送信ノードと受信ノードを含む複数の前記ノードにより構成される複数の伝送経路について、それぞれの前記伝送経路における通信に要する時間の仮値を、前記送信ノード及び前記受信ノードのクロックに基づき算出する第１算出工程と、
複数の前記伝送経路のうち１つを基準経路とし、前記基準経路における前記仮値と、他の前記伝送経路の前記仮値との差と算出する第２算出工程と、
前記第２算出工程により算出された前記基準経路と他の前記伝送経路との仮値の差を左辺に、それぞれの前記伝送経路についてそれぞれの前記ノードの有無を表すマトリックスと前記ノード間のリンクの前記通信に要する時間を表すマトリックスとの積を右辺に有する第１線形観測式を得る第１立式工程と、
前記第１立式工程により得られた前記第１線形観測式について圧縮センシングに基づき最小化問題を解くことで前記ネットワーク内の故障箇所を同定する第１同定工程と、
を有することを特徴とするネットワークの故障検出方法。
【請求項２】
前記最小化問題はｌ１／ｌ２最適化問題であることを特徴とする請求項１記載のネットワークの故障検出方法。
【請求項３】
複数のノードにより構成されるネットワークの故障検出方法であって、
任意の数のノードにより構成される複数の伝送経路について、前記伝送経路を構成する前記ノード間のリンクの通信に要する時間を算出する第３算出工程と、
前記第３工程で算出された前記通信に要する時間を所定の閾値に基づき２値化する第１の２値化工程と、
複数の前記伝送経路のそれぞれについて、前記伝送経路に含まれる前記ノード間のリンクの通信に要する時間を２値化したものの総和を算出する第４算出工程と、
前記第４算出工程により得られた値が１以上である場合を１、０である場合を０と２値化する第２の２値化工程と、
前記第２の２値化工程において得られた複数の前記伝送経路のそれぞれについての２値化された値を表すマトリックスを左辺に、それぞれの前記伝送経路についてそれぞれの前記ノードの有無を表すマトリックスと前記ノード間のリンクの２値化された前記通信に要する時間を表すマトリックスとの積を右辺に有する第２線形観測式を得る第２立式工程と、
前記第２立式工程により得られた前記第２線形観測式について圧縮センシングに基づき最小化問題を解くことで前記ネットワーク内の故障箇所を同定する第２同定工程と、
を有することを特徴とするネットワークの故障検出方法。
【請求項４】
前記最小化問題はｌ１最適化問題であることを特徴とする請求項３記載のネットワークの検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークの故障検出方法に関するものである。
【背景技術】
【０００２】
ネットワークにおけるノードや基地局間のリンク不良、及び故障したノードや基地局の検出等、ネットワークの故障検出を行う技術は、ネットワークを高い信頼性で運用するために必要不可欠な技術である。
【０００３】
特に近年、様々な有線・無線ネットワークを有機的に接続することで展開される大規模ネットワークが増加しているが、今後もモバイルネットワークの普及に伴い、その数は急速に増えることが予想される。
【０００４】
そのため、ネットワークを構成する基地局リソース（時間管理等）ならびにネットワークリソース（回線容量等）に一様性を前提とせず、故障検出を高効率に行う技術は重要になると考えられる。
【０００５】
こうした故障検出を行うため、従来は、管理ノードから他の全ノードに対してネットワークの故障検出用のパケットを送信し（例えば、特許文献１参照）、各ノードからの応答時間等を計測し、その計測結果から故障の有無や故障箇所の同定を行う等の方法が採用されていた。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００６−２４６１２２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
上述した従来のネットワークの故障検出方法では、全ノードに対して応答時間計測用のパケットを伝送するため、計測対象とするノードの増加に伴いパケットの伝送回数（経由リンク数）が指数関数的に増加し、ネットワークの回線容量を消費してしまう。
【０００８】
また、ノードからの応答時間（伝送遅延時間）の計測によってリンクの不良やノードの故障を検出する場合、管理ノードとメンテナンス対象となる全ノードとの同期の確立が必要となるため、時刻の確立を行うことができない場合には、検出を行うことができない。
【０００９】
一方、管理ノードとメンテナンス対象である全ノードとの時刻同期を前提とせず、一部のノード間で同期が確立されれば行いうるネットワークの故障方法も存在する。この方法について図１のネットワークを例に説明する。図１は、複数のノードにより構成されるネットワークの例を示す模式図である。
【００１０】
図１に示すネットワークは、パケットの送信元である２つの送信ノードａ、ｂ、送信元と送信先とのパケットの授受の中継を行う２つの中継ノードｃ、ｄ、及びパケットの最終的な送信先である２つの受信ノードｅ、ｆの合計６つのノードにより構成されている。なお、ネットワークは有線のものでも無線のものでも、あるいはそれらが混合されて構成されているものでも良い。
【００１１】
送信ノードａ−中継ノードｃ間のリンクをリンク１、送信ノードｂ−中継ノードｃ間のリンクをリンク２、中継ノードｃ−中継ノードｄ間のリンクをリンク３、中継ノードｄ−受信ノードｅ間のリンクをリンク４、中継ノードｄ−受信ノードｆ間のリンクをリンク５とする。
【００１２】
また、送信ノードａから受信ノードｅ又はｆへと至るパケットの経路であって、リンク１、リンク３及びリンク４を経るものを経路１、リンク１、リンク３及びリンク５を経るものを経路２とする。
【００１３】
また、送信ノードｂから受信ノードｅ又はｆへと至るパケットの経路であって、リンク２、リンク３及びリンク５を経るものを経路３、リンク２、リンク３及びリンク４を経るものを経路４とする。
【００１４】
こうしたネットワークにおいて、経路ｉ（ｉ＝１、２、３、４）における通信に要する時間をＤｉ、リンクｊ（ｊ＝１、２、３、４、５）における通信に要する時間をｄｊとすると、以下の数式（１）に示す連立方程式を導くことができる。
【００１５】
【数１】
2015154256.tif 000003
【００１６】
ここで、Ｄｉは、送信ノードａ又はｂと、受信ノードｅ又はｆとの間で同期が確立さえしていれば求めることができるものであり、中継ノードｃ、ｄとの同期の確立を必要としないで求めることができる。
【００１７】
こうして得られた数式（１）の連立方程式は、以下の数式（２）として表すことができる。
【００１８】
【数２】
2015154256.tif 000004
【００１９】
数式（２）において、Ｐａｔｈｉは経路ｉにおいて経由するリンクの集合である。ここで、数式（２）について、ｙｉ＝Ｄｉ、ｘｊ＝ｄｊとすると、以下の数式（３）に示す線形観測式の立式を行うことができる。
【００２０】
【数３】
2015154256.tif 000005
【００２１】
数式（３）の左辺は、経路１〜４のそれぞれについての通信に要する時間ｙｉ（＝ｄｊ、ｉ＝１、２、３、４）を示す４行１列のマトリックスである。この値は実測値として予め求めることができる。
【００２２】
上述したようにこのネットワークの故障検出方法では中継ノードｃ、ｄについて、送信ノードａ、ｂや受信ノードｅ、ｆとの同期が無くとも、各経路において送信ノードａ又はｂと受信ノードｅ又はｆとの同期が確立しているため、パケットの送信時刻と受信時刻が分かる。そして、これにより実測値であるｙｉの値を求めることが可能となっている。
【００２３】
数式（３）の右辺は、経路１〜４のそれぞれについて、リンク１〜５の含有の有無を、有りの場合を１、無しの場合を０として表した４行５列のマトリックスと、リンク１〜５のそれぞれの通信に要する時間により構成される５行１列のマトリックスとの積である。
【００２４】
リンク１〜５のそれぞれの通信に要する時間は、各リンクを構成するノード間の同期が確立されていないため測定することができず、以下の演算により数学的に求められるものである。
【００２５】
この数式（３）に示す線形観測式について、圧縮センシングに基づきｌ１／ｌ２最適化問題等の最小化問題解くことにより、ネットワークの故障検出を行うことができる。なお、この最小化問題の演算は、受信側のノードのＣＰＵの他、ネットワーク全体を管理する管理ノードが存在する場合にはそのＣＰＵ等、任意の場所で行わせることができる。
【００２６】
しかし、この例でも、送信ノードａ又はｂと受信ノードｅ又はｆとの同期は必須であり、これらのノード間の同期が確立していない場合にはネットワークの故障検出を行うことはできない。
【００２７】
また、各ノードが同期を確立している場合でも、遅延時間の実測値に基づき故障検出を行う方法を採用した場合には、故障検出に必要な信号処理量が膨大なものとなり、実用的では無くなる恐れもある。
【００２８】
そこで、本願第１発明は、上述した問題点に鑑みて案出されたものであり、ノード間の同期を前提とすることなく故障検出が行えるとともに、故障検出に必要なネットワークの回線容量の消費及び信号処理量を低減することのできるネットワークの故障検出方法を提供することを目的とする。
【００２９】
また、本願第３発明も、故障検出に必要な信号処理量を低減することのできるネットワークの故障検出方法を提供することを目的とする。
【課題を解決するための手段】
【００３０】
本発明者は、上述した課題を解決するために、ネットワークの回線容量の消費を抑えるとともに、端末間の同期を前提とすることのないネットワークの故障検出方法を発明した。
【００３１】
また、本発明者は、故障検出に必要な信号処理量を低減することもできるネットワークの故障検出方法を発明した。
【００３２】
第１発明に係るネットワークの故障検出方法は、複数のノードにより構成されるネットワークの故障検出方法であって、互いに同期が確立していない送信ノードと受信ノードを含む複数の前記ノードにより構成される複数の伝送経路について、それぞれの前記伝送経路における通信に要する時間の仮値を、前記送信ノード及び前記受信ノードのクロックに基づき算出する第１算出工程と、複数の前記伝送経路のうち１つを基準経路とし、前記基準経路における前記仮値と、他の前記伝送経路の前記仮値との差と算出する第２算出工程と、前記第２算出工程により算出された前記基準経路と他の前記伝送経路との仮値の差を左辺に、それぞれの前記伝送経路についてそれぞれの前記ノードの有無を表すマトリックスと前記ノード間のリンクの前記通信に要する時間を表すマトリックスとの積を右辺に有する第１線形観測式を得る第１立式工程と、前記第１立式工程により得られた前記第１線形観測式について圧縮センシングに基づき最小化問題を解くことで前記ネットワーク内の故障箇所を同定する第１同定工程と、を有することを特徴とする。
【００３３】
第２発明に係るネットワークの故障検出方法は、第１発明に係るネットワークの故障検出方法であって、前記最小化問題はｌ１／ｌ２最適化問題であることを特徴とする。
【００３４】
第３発明に係るネットワークの故障検出方法は、複数のノードにより構成されるネットワークの故障検出方法であって、任意の数のノードにより構成される複数の伝送経路について、前記伝送経路を構成する前記ノード間のリンクの通信に要する時間を算出する第３算出工程と、
前記第３工程で算出された前記通信に要する時間を所定の閾値に基づき２値化する第１の２値化工程と、複数の前記伝送経路のそれぞれについて、前記伝送経路に含まれる前記ノード間のリンクの通信に要する時間を２値化したものの総和を算出する第４算出工程と、前記第４算出工程により得られた値が１以上である場合を１、０である場合を０と２値化する第２の２値化工程と、前記第２の２値化工程において得られた複数の前記伝送経路のそれぞれについての２値化された値を表すマトリックスを左辺に、それぞれの前記伝送経路についてそれぞれの前記ノードの有無を表すマトリックスと前記ノード間のリンクの２値化された前記通信に要する時間を表すマトリックスとの積を右辺に有する第２線形観測式を得る第２立式工程と、前記第２立式工程により得られた前記第２線形観測式について圧縮センシングに基づき最小化問題を解くことで前記ネットワーク内の故障箇所を同定する第２同定工程と、を有することを特徴とする。
【００３５】
第４発明に係るネットワークの故障検出方法は、第３発明に係るネットワークの故障検出方法であって、前記最小化問題はｌ１最適化問題であることを特徴とする。
【発明の効果】
【００３６】
上述した構成からなる第１発明によれば、ネットワークの回線容量の消費を抑えるとともに、端末間の同期を前提とすることなくネットワークの故障検出を行うことが可能となる。
また、第３発明によれば、故障検出に必要な信号処理量を低減することができる。
【図面の簡単な説明】
【００３７】
【図１】複数のノードにより構成されるネットワークの例を示す模式図である。
【図２】本発明の第１実施形態に係るネットワークの故障検出方法が適用されるネットワークを示す図である。
【図３】２つのノード間の通信に要する時間が２値化される様子を示す図であり、（Ａ）は２値化前の状態を、（Ｂ）は２値化後の状態を示す図である。
【発明を実施するための形態】
【００３８】
以下、本発明の実施形態に係るネットワークの故障検出方法について詳細に説明する。
【００３９】
[第１実施形態]
図２は、本発明の第１実施形態に係るネットワークの故障検出方法が適用されるネットワークを示す図である。
【００４０】
図２に示すネットワークは、ノードＳ、ノードＡ、ノードＢ、ノードＣ、ノードＤ、ノードＥ、ノードＦ及びノードＲの８つのノードにより構成されていて、ノードＳからノードＲに向けて、複数の他のノードを経由してパケットの送信が行われる。なお、ネットワークは有線のものでも無線のものでも、あるいはそれらが混合されて構成されているものでも良い。
【００４１】
ここで、ノードＳ−ノードＢ間の通信に要する時間をｄ１とする。ノードＳ−ノードＡ間の通信に要する時間をｄ２とする。ノードＢ−ノードＣ間の通信に要する時間をｄ３とする。ノードＡ−ノードＣ間の通信に要する時間をｄ４とする。ノードＢ−ノードＦ間の通信に要する時間をｄ５とする。ノードＣ−ノードＤ間の通信に要する時間をｄ６とする。ノードＡ−ノードＥ間の通信に要する時間をｄ７とする。ノードＤ−ノードＦ間の通信に要する時間をｄ８とする。ノードＤ−ノードＥ間の通信に要する時間をｄ９とする。ノードＦ−ノードＲ間の通信に要する時間をｄ１０とする。ノードＥ−ノードＲ間の通信に要する時間をｄ１１とする。なお、各ノード間で同期が確立していないため、ｄ１〜ｄ１１の実測値を求めることはできない。
【００４２】
本実施形態では、上記各ノード間の何れか１つにおいて通信の障害が生じていて、通信に要する時間が大幅に増加するか又は通信を全く行えない状況を仮定している。これは、故障の生じている箇所は非常に少ないというスパース性に基づく仮定である。
【００４３】
そして、上記各ノード間の何れか１つにおいて通信の障害が生じているということは、すなわち、ｄ１〜ｄ１１の何れか１つが他のものよりもはるかに長い時間になるということである。
【００４４】
ここで、ノードＳ、ノードＢ、ノードＦを経てノードＲに至る通信経路において通信に要する時間をＤ１とすると、Ｄ１は以下の式で表される。
Ｄ１＝ｄ１＋ｄ５＋ｄ１０
【００４５】
また、ノードＳ、ノードＢ、ノードＣ、ノードＤ、ノードＦを経てノードＲに至る通信経路において通信に要する時間をＤ２とすると、Ｄ２は以下の式で表される。
Ｄ２＝ｄ１＋ｄ３＋ｄ６＋ｄ８＋ｄ１０
【００４６】
また、ノードＳ、ノードＢ、ノードＣ、ノードＤ、ノードＥを経てノードＲに至る通信経路において通信に要する時間をＤ３とすると、Ｄ３は以下の式で表される。
Ｄ３＝ｄ１＋ｄ３＋ｄ６＋ｄ９＋ｄ１１
【００４７】
また、ノードＳ、ノードＡ、ノードＣ、ノードＤ、ノードＦを経てノードＲに至る通信経路において通信に要する時間をＤ４とすると、Ｄ４は以下の式で表される。
Ｄ４＝ｄ２＋ｄ４＋ｄ６＋ｄ８＋ｄ１０
【００４８】
また、ノードＳ、ノードＡ、ノードＣ、ノードＤ、ノードＥを経てノードＲに至る通信経路において通信に要する時間をＤ５とすると、Ｄ５は以下の式で表される。
Ｄ５＝ｄ２＋ｄ４＋ｄ６＋ｄ９＋ｄ１１
【００４９】
また、ノードＳ、ノードＡ、ノードＥを経てノードＲに至る通信経路において通信に要する時間をＤ６とすると、Ｄ６は以下の式で表される。
Ｄ６＝ｄ２＋ｄ７＋ｄ１１
【００５０】
こうしてｄ１〜ｄ１１を用いてＤ１〜Ｄ６を表すことができる。これらに基づき、Ｄ１〜Ｄ６について、下記数式（４）に示す線形観測式として表すことができる。なお、この線形観測式の立式及び以下に示す各数式の立式は、受信側のノードのＣＰＵの他、ネットワーク全体を管理する管理ノードが存在する場合にはそのＣＰＵ等、任意の場所で行わせることができる。
【００５１】
【数４】
2015154256.tif 000006
【００５２】
数式（４）の左辺は、Ｄ１〜Ｄ６を示す６行１列のマトリックスである。
【００５３】
数式（４）の右辺は、Ｄ１〜Ｄ６について、それぞれｄ１〜ｄ１１の含有の有無を、有りの場合を１、無しの場合を０として表した６行１１列のマトリックスと、ノード間のリンクの遅延時間であるｄ１〜ｄ１１により構成される１１行１列のマトリックスとの積である。
【００５４】
ノードＳ−ノードＲ間の同期が確立している場合には、この数式（４）に示す線形代数式からｄ１〜ｄ１１を得ることができ、Ｄ１〜Ｄ６を得ることができる。そして、ｌ１／ｌ２最適化等を行うことで故障検出を行うことができる。
【００５５】
しかし、本実施形態においては、ノードＳ−ノードＲ間の同期が確立していないため、ｄ１〜ｄ１１を得ることができない。また、ノードＳ−ノードＲ間の同期も確立していないため、Ｄ１〜Ｄ６の正確な実測値も得ることはできない。
【００５６】
しかし、ノードＳとノードＲはそれぞれ固有のクロックに基づき動作していて、それぞれの時刻をパケットの送信時間及び受信時間としてパケットデータに含めることはできる。
【００５７】
そこで、同期が確立していない状態においてノードＳとノードＲとがそれぞれパケットデータに記録した、データの送信時間及び受信時間に基づいて、Ｄ１〜Ｄ６の値が仮値として求められている。
【００５８】
例えば、ノードＳとノードＲとの間の未知の時刻オフセットをδとすると、Ｄ１〜Ｄ６の仮値は次の数式（５）のように表現できる。
【００５９】
【数５】
2015154256.tif 000007
【００６０】
上でも述べたとおり、上記数式を直接用いてｌ１／ｌ２最適化等により故障検出を行う場合は、時刻オフセットがゼロあるいは既知である必要がある。
【００６１】
本実施形態に係るネットワークの故障検出方法では、このＤ１〜Ｄ６の仮値を用いることで、ノードＳ−ノードＲ間の同期を前提としない故障検出を可能としている。
【００６２】
数式（６）は、本実施形態に係るネットワークの故障検出方法において用いられる線形観測式である。数式（６）は、上記数式に基づき得ることができる。
【００６３】
【数６】
2015154256.tif 000008
【００６４】
数式（６）の左辺は、Ｄ６の仮値を基準とし、Ｄ１〜Ｄ５の仮値のそれぞれとＤ６の仮値の差を示す５行１列のマトリックスである。
【００６５】
ここで、左辺のＤ１〜Ｄ６の差について、いずれか一方のみに故障箇所（ｄ１〜ｄ１１の何れか）が含まれている場合には、その差は故障箇所の影響により膨大な正又は負の値となる。
【００６６】
一方、左辺のＤ１〜Ｄ６の差について、双方に故障箇所が含まれている場合には、故障箇所同士が打ち消しあうこととなるため、故障箇所による影響は現れない。
【００６７】
こうして、左辺の値については、いずれか一方について故障箇所がある場合には、故障箇所による影響が明確に現れたものとなる。
【００６８】
数式（６）の右辺は、仮値Ｄ１〜Ｄ５のそれぞれと基準経路である仮値Ｄ６との差について、ｄ１〜ｄ１１の含有の有無を、それぞれの通信経路だけに含まれる場合は１、それぞれの通信経路と基準経路の両方に含まれる場合は０、そして基準経路だけに含まれる場合は−１として表した５行１１列のマトリックスと、ノード間のリンクの遅延時間であるｄ１〜ｄ１１により構成される１１行１列のマトリックスとの積である。
【００６９】
このように、ノードＳ−ノードＲ間の同期が確立されていない状況下で、ノードＳ−ノードＲ間の１つの基準ルートにおける通信に要する時間（本実施形態ではＤ６）を基準にし、他のルートにおける通信に要する時間（本実施形態ではＤ１〜Ｄ５）との差を算出している。こうすることで、従来ノードＳ−ノードＲ間の同期が確立していない状況下では行うことのできなかった線形観測式による解析を行うことができる。
【００７０】
この数式（６）に示す線形観測式について、圧縮センシングに基づきｌ１／ｌ２最適化問題等の最小化問題解くことにより、ネットワークの故障検出を行うことができる。この最小化問題の演算は、受信側のノードのＣＰＵの他、ネットワーク全体を管理する管理ノードが存在する場合にはそのＣＰＵ等、任意の場所で行わせることができる。
【００７１】
このように、第１実施形態に係るネットワークの故障検出方法によると、複数の端末を経由する経路及び基準経路を指定して、各経路と基準経路との通信に要する時間の差分から故障箇所の同定を行っている。
【００７２】
これにより、故障検出を目的とした通信時間の計測の際、計測用パケットの伝送経路に基準経路を定めて、その基準経路における通信に要する時間と他の経路における通信に要する時間との差分を元にすることで、端末間の時刻同期の確立が無くとも故障検出を行うことができる。
【００７３】
また、従来の全ノードに対して故障検出用のパケットを送信する方法と比較して、少ないパケット送信・受信での保守が可能となる。よって、ネットワークの回線容量の消費を抑えることが可能となる。
【００７４】
更に、従来の線形観測式と比較しマトリックスの成分数を減らすことができるため、故障検出に必要な信号の処理量を削減することができる。
【００７５】
[第２実施形態]
次に、本願発明の第２実施形態について、上述した図１のネットワークを例に説明する。本実施形態は、各ノード間に同期が確立されている場合において、故障検出に必要な信号処理量を低減することのできるネットワークの故障検出方法に関する。
【００７６】
上述したように、図１のネットワークは、２つの送信ノードａ、ｂ、２つの中継ノードｃ、ｄ及び２つの受信ノードｅ、ｆの合計６つのノードにより構成されている。ここでも、ネットワークは有線のものでも無線のものでも、あるいはそれらが混合されて構成されているものでも良い。
【００７７】
送信ノードａ−中継ノードｃ間のリンクをリンク１、送信ノードｂ−中継ノードｃ間のリンクをリンク２、中継ノードｃ−中継ノードｄ間のリンクをリンク３、中継ノードｄ−受信ノードｅ間のリンクをリンク４、中継ノードｄ−受信ノードｆ間のリンクをリンク５とする。
【００７８】
また、送信ノードａから受信ノードｅ又はｆへと至るパケットの経路であって、リンク１、リンク３及びリンク４を経るものを経路１、リンク１、リンク３及びリンク５を経るものを経路２とする。
【００７９】
また、送信ノードｂから受信ノードｅ又はｆへと至るパケットの経路であって、リンク２、リンク３及びリンク４を経るものを経路３、リンク２、リンク３及びリンク５を経るものを経路４とする。
【００８０】
上述したように、本実施形態においては、各ノード間で同期が確立された状態となっている。そのため、こうしたネットワークにおいて、リンクｊ（ｊ＝１、２、３、４、５）における通信に要する時間の実測値を算出することが可能となっている。
【００８１】
そのため、理論上は上述した従来技術のように、ブーリアン圧縮センシングに基づきｌ１最適化問題等の最小化問題解くことにより、ネットワークの故障検出を行うことが可能である。
【００８２】
しかし、現実的には、こうした実測値に基づき解析を行う場合には、故障検出に必要な信号の処理量が膨大であり、こうした方法に基づく故障検出は難しかった。
【００８３】
そこで、本実施形態に係るネットワークの故障検出方法では、実測値を２値化することで故障検出に要する信号処理量の削減を実現している。
【００８４】
本実施形態に係るネットワークの故障検出方法では、リンクｊ（ｊ＝１、２、３、４、５）における通信に要する時間の実測値を２値化したものをｄｊとしている。
【００８５】
図３は、２つのノード間の通信に要する時間が２値化される様子を示す図であり、（Ａ）は２値化前の状態を、（Ｂ）は２値化後の状態を示す図である。
【００８６】
本実施形態に係るネットワークの故障検出方法では、図３に示すように、２つのノード間の通信に要する時間等、通信品質を表すリンク状態に閾値を設定し、閾値を下回る値については全て０とし、それ以外のものは全て１とする。そして、判定結果である０又は１の２値（ブーリアン値）によって故障箇所の判定を行う。なお、この２値化は、受信側のノードのＣＰＵの他、ネットワーク全体を管理する管理ノードが存在する場合にはそのＣＰＵ等、任意の場所で行わせることができる。
【００８７】
また、経路ｉ（ｉ＝１、２、３、４）において２値化されたｄｊの総和について、１以上の値になるものを１、それ以外を０と２値化したものをＤｉとしている。この総和の算出及び２値化も、同様に受信側のノードのＣＰＵの他、ネットワーク全体を管理する管理ノードが存在する場合にはそのＣＰＵ等、任意の場所で行わせることができる。
【００８８】
これらのｄｊとＤｉとに基づき、上述した数式（１）と同様の連立方程式が導かれる。
【００８９】
ここで、従来の故障検出方法では、２つのノード間の通信に要する時間及び各経路における通信に要する時間として、実測された値をそのまま用いて解析に供されていた。
【００９０】
しかし、本実施形態に係るネットワークの故障検出方法では、時間ｄｊ及びＤｉとして０か１の２つの値のみが用いられている。
【００９１】
こうして得られた数式（１）の連立方程式も、上述した数式（２）として表される。
【００９２】
そして、数式（２）について、ｙｉ＝ｄｉ、ｘｊ＝ｄｊとし、同様に数式（３）に示す線形観測式の立式が行われる。この立式も、受信側のノードのＣＰＵの他、ネットワーク全体を管理する管理ノードが存在する場合にはそのＣＰＵ等、任意の場所で行わせることができる。
【００９３】
このとき、数式（３）の左辺は、従来の方法とは異なり、経路１〜４のそれぞれについて２値化されたｄｊの総和について、１以上の値になるものを１、それ以外を０としたものを示す４行１列のマトリックスである。
【００９４】
数式（３）の右辺は、経路１〜４のそれぞれについて、リンク１〜５の含有の有無を、有りの場合を１、無しの場合を０として表した４行５列のマトリックスと、リンク１〜５のそれぞれの通信に要する時間を２値化したものにより構成される５行１列のマトリックスとの積である。ここで、ｘｊ（ｊ＝１、２、３、４、５）は２値化された値であり、０か１の何れかの値となる。
【００９５】
そして、この数式（３）に示す線形観測式について、ブーリアン圧縮センシングに基づきｌ１最適化問題等の最小化問題を解くことにより、ネットワークの故障検出を行うことができる。この演算は論理演算により行われる。
【００９６】
このとき、ｘｊが２値化されているため、計算を迅速かつ簡易に行うことができるようになっている。なお、この最小化問題を解くことも、受信側のノードのＣＰＵの他、ネットワーク全体を管理する管理ノードが存在する場合にはそのＣＰＵ等、任意の場所で行わせることができる。
【００９７】
このように、本実施形態に係るネットワークの故障検出方法によると、上述したように２つのノード間の通信に要する時間に閾値を設定し、その閾値判定結果である０又は１の２値によって故障箇所の判定を行う。これにより、故障検出に必要な信号処理量及び信号処理に要する消費電力を低減することができる。
【００９８】
なお、上述した本実施形態に係るネットワークの故障検出方法におけるノード間の通信に要する時間の２値化を、閾値に応じて行うのではなく、パケットが届いたか否かに基づき行うこともできる。この場合には、上述した第１実施形態と同様、ノード間の同期が確立されていなくとも、ネットワークの故障検出をすることができる。
【符号の説明】
【００９９】
Ｓ、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｒ、ａ、ｂ、ｃ、ｄ、ｅ、ｆ  ノード
【図１】
2015154256.tif 000009
【図２】
2015154256.tif 000010
【図３】
2015154256.tif 000011