(57)【要約】      （修正有）【課題】トレードオフの関係にあるとされる効率性と頑健性とを両立させたネットワーク構造の構築、および、ネットワークが破壊された場合であっても、自己組織的に元のネットワーク構造としての機能を回復できる機能が搭載されたネットワーク構造を提供する。【解決手段】互いに完全結合されたスターノード１〜３と、各々がスターノードのすべてとの間でリンクを有している周辺ノード４〜Ｎとを含むオリジナルのネットワークのうち、ノードおよびリンクの障害発生後に残存しているノードおよびリンクを判断するステップと、必要な数のスターノードが残存しているか否かを判断するステップと、必要な数のスターノードが残存していない場合に、必要な数の周辺ノードを新たなスターノードとして決定するステップと、スターノード同士および各周辺ノードとスターノードのすべてとの間でリンクを再構成するステップとを含む。【選択図】図７
2014187624.tif 000002
【特許請求の範囲】
【請求項１】
ネットワークの修復方法であって、
互いに完全結合されたスターノードと、各々が前記スターノードのすべてとの間でリンクを有している周辺ノードとを含むオリジナルのネットワークのうち、残存しているノードおよびリンクを判断するステップと、
必要な数のスターノードが残存しているか否かを判断するステップと、
前記必要な数のスターノードが残存していない場合に、必要な数の周辺ノードを新たなスターノードとして決定するステップと、
スターノード同士および各周辺ノードとスターノードのすべてとの間でリンクを再構成するステップとを含む、ネットワークの修復方法。
【請求項２】
前記決定するステップは、
各周辺ノードについて、修復対象としての優先度を決定するステップと、
優先度のより高い周辺ノードを新たなスターノードとして選択するステップとを含む、請求項１に記載のネットワークの修復方法。
【請求項３】
前記優先度を決定するステップは、ノード自体の優先度、ノードの物理的位置、ノード間の距離、ノードの通信チャネル数、ノードの処理可能数、ノードの通信パワー、ノード間が互いに見通せるか否か、の少なくとも１つを用いて、各ノードの優先度を算出するステップを含む、請求項２に記載のネットワークの修復方法。
【請求項４】
周辺ノード間のうちリンクを再構築する対象を決定するステップをさらに含む、請求項１〜３のいずれか１項に記載のネットワークの修復方法。
【請求項５】
ネットワークの修復プログラムであって、前記修復プログラムはコンピュータに、
互いに完全結合されたスターノードと、各々が前記スターノードのすべてとの間でリンクを有している周辺ノードとを含むオリジナルのネットワークのうち、残存しているノードおよびリンクを判断するステップと、
必要な数のスターノードが残存しているか否かを判断するステップと、
前記必要な数のスターノードが残存していない場合に、必要な数の周辺ノードを新たなスターノードとして決定するステップと、
スターノード同士および各周辺ノードとスターノードのすべてとの間でリンクを再構成するステップとを実行させる、ネットワークの修復プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スモール・ワールド性を有するネットワークの修復方法および修復プログラムに向けられる。
【背景技術】
【０００２】
従来の複雑ネットワーク研究において、スモール・ワールド（Small-World）の性質について議論および研究がなされてきた。このような議論および研究において、故障確率が大きい場合でも、スモール・ワールド性を維持できるネットワーク構造が提案されている。
【０００３】
スモール・ワールド性を有する典型的なネットワーク構造として、スケールフリー・ネットワークが知られている（非特許文献１）。このスケールフリー・ネットワークは、ランダムな故障には頑健であるが、サイバー攻撃などの人為的な攻撃には脆弱である。また、非特許文献２には、ランダムな故障およびサイバー攻撃のいずれにも頑健なネットワーク構造として、２極次数分布（Bimodal network）ネットワークが開示されている。
【０００４】
一般的に、ネットワークにおける通信機能の効率性（例えば、平均経路長の短さなど）と故障に対する頑健性とは、トレードオフの関係があると考えられており、効率性と頑健性とを両立させることは難しかった。そして、ランダムな故障やサイバー攻撃などによってネットワーク構造が破壊されると、ネットワークの機能を自動的に元の状態に回復させるための自己修復機能を有効に働かせることはできなかった。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Reka Albert et. al., "Error and attack tolerance of complex networks", Nature, Vol.406, pp. 378-382, 27 July 2000
【非特許文献２】T. Tanizawa et. al., "Optimization of network robustness to waves of targeted and random attacks"，Physical Review E 71, 047101-1-4，2005
【非特許文献３】澤井秀文、「スモール・ワールドの創発と解析」、人工知能学会創立２５周年記念合同研究会資料、ＳＩＧＤＯＣＭＡＳ−Ｂ１０１−１、ｐｐ．２−１〜２−８、２０１１年
【非特許文献４】澤井秀文、「故障と攻撃の両方に強いスモールワールド・ネットワーク」、オーガナイズドセッション「ＯＳ−１２ネットワークが創発する知能」、1C3-OS-12-7、２０１２年度人工知能学会全国大会、２０１２年６月
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本願発明者は、従来のネットワーク構造に比較して、効率性を高めるとともに、ランダムな故障および人為的な攻撃のいずれについても改善したネットワーク構造を提案してきた（例えば、非特許文献３および非特許文献４など）。
【０００７】
このようなネットワーク構造を現実のネットワークに応用した場合、万が一、ネットワーク構造の一部が破壊・破損された場合に、元のネットワークの機能を可能な限り早期に回復させることを要求される。
【０００８】
すなわち、トレードオフの関係にあるとされる効率性と頑健性とを両立させたネットワーク構造の構築、および、仮にこのようなネットワークが破壊された場合であっても、自己組織的に元のネットワーク構造としての機能を回復できる機能が搭載されたネットワーク構造の実現が要望されている。
【課題を解決するための手段】
【０００９】
本発明のある局面に従うネットワークの修復方法は、互いに完全結合されたスターノードと、各々がスターノードのすべてとの間でリンクを有している周辺ノードとを含むオリジナルのネットワークのうち、残存しているノードおよびリンクを判断するステップと、必要な数のスターノードが残存しているか否かを判断するステップと、必要な数のスターノードが残存していない場合に、必要な数の周辺ノードを新たなスターノードとして決定するステップと、スターノード同士および各周辺ノードとスターノードのすべてとの間でリンクを再構成するステップとを含む。
【００１０】
好ましくは、決定するステップは、各周辺ノードについて、修復対象としての優先度を決定するステップと、優先度のより高い周辺ノードを新たなスターノードとして選択するステップとを含む。
【００１１】
さらに好ましくは、優先度を決定するステップは、ノード自体の優先度、ノードの物理的位置、ノード間の距離、ノードの通信チャネル数、ノードの処理可能数、ノードの通信パワー、ノード間が互いに見通せるか否か、の少なくとも１つを用いて、各ノードの優先度を算出するステップを含む。
【００１２】
好ましくは、修復方法は、周辺ノード間のうちリンクを再構築する対象を決定するステップをさらに含む。
【００１３】
本発明の別の局面に従えば、ネットワークの修復プログラムが提供される。修復プログラムはコンピュータに、互いに完全結合されたスターノードと、各々がスターノードのすべてとの間でリンクを有している周辺ノードとを含むオリジナルのネットワークのうち、残存しているノードおよびリンクを判断するステップと、必要な数のスターノードが残存しているか否かを判断するステップと、必要な数のスターノードが残存していない場合に、必要な数の周辺ノードを新たなスターノードとして決定するステップと、スターノード同士および各周辺ノードとスターノードのすべてとの間でリンクを再構成するステップとを実行させる。
【発明の効果】
【００１４】
本発明によれば、元のネットワークの機能を可能な限り早期に回復させることができる。
【図面の簡単な説明】
【００１５】
【図１】本実施の形態に従うｎ−Ｓｔａｒネットワークの一例を示す図である。
【図２】本実施の形態に従うｎ−Ｓｔａｒネットワークの一例を示す図である。
【図３】本実施の形態に従うｎ−Ｓｔａｒネットワークの一例を示す図である。
【図４】本実施の形態に従うｎ−Ｓｔａｒネットワークの一例を示す図である。
【図５】本実施の形態に従うｎ−ＳｔａｒネットワークのＲ値と平均次数＜ｋ＞との関係を他の複雑ネットワークと比較しつつ示すグラフである。
【図６】本実施の形態に従うｎ−Ｓｔａｒネットワークの頑健性を他の複雑ネットワークと比較しつつ示すグラフである。
【図７】本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能について説明するための図である。
【図８】本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能のシミュレーション結果の一例を示す図である。
【図９】本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能の処理手順を示すフローチャートである。
【図１０】本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能の具体例を説明する模式図である。
【図１１】図１０に示すネットワークの隣接行列を示す。
【図１２】本実施の形態に係るｎ−Ｓｔａｒネットワークの自己修復機能を実現するためのコンピュータ１００の構成を示す模式図である。
【発明を実施するための形態】
【００１６】
本発明の実施の形態について、図面を参照しながら詳細に説明する。なお、図中の同一または相当部分については、同一符号を付してその説明は繰返さない。
【００１７】
＜Ａ．概要＞
本実施の形態においては、効率性および頑健性を両立させることができるスモール・ワールド性を有するネットワークに対して、何らかの障害が発生した場合に、そのネットワークが本来的に有している自己修復機能を利用しつつ、効率的な通信機能を回復させるための方法などに向けられる。
【００１８】
＜Ｂ．ネットワーク構造＞
まず、本実施の形態に係るネットワーク構造について説明する。本実施の形態においては、ネットワーク構造として、本願発明者が提案するマルチスター型のネットワーク構造からなるアーキテクチャを用いる。このマルチスター型のネットワーク構造を「ｎ−Ｓｔａｒネットワーク」とも称す。ｎ−Ｓｔａｒネットワークは、任意の２つのノード間の経路長の全体平均（平均経路長）が知られている複雑ネットワークの中で最も小さく、従来のネットワーク構造に比較して効率性が高い。同時に、ｎ−Ｓｔａｒネットワークは、従来提案されていた２極次数分布ネットワークやスケールフリー・ネットワークなどと比較して、ランダムな故障および人為的な攻撃の両方に対してより強い特性を有する。さらに、ｎ−Ｓｔａｒネットワークは、故障確率が比較的大きな場合であっても、スモール・ワールド性を維持できる。つまり、ｎ−Ｓｔａｒネットワークを採用することで、効率性および頑健性を両立させることができる。
【００１９】
図１〜図４は、本実施の形態に従うｎ−Ｓｔａｒネットワークの一例を示す図である。なお、ｎ−Ｓｔａｒネットワークは、ｎ個のスターノードを有するネットワークを意味している。図１〜図４には、スターノード数ｎ＝１〜４の場合をそれぞれ示す。
【００２０】
図１〜図４に示すｎ−Ｓｔａｒネットワークにおいては、中心にｎ個（１≦ｎ≦Ｎ）のスターノード１０が存在し、そのスターノード１０の周辺にＮ０（≡Ｎ−ｎ）個の周辺ノード２０が存在している。但し、Ｎは、ｎ−Ｓｔａｒネットワークに含まれるノードの総数を示す。スターノード１０が複数存在する場合、それらのスターノード１０同士は完全結合（つまり、ｃｌｉｑｕｅを形成）しており、周辺ノード２０の各々は、存在するスターノード１０のすべてとの間でリンク１２を有している。一方、周辺ノード２０同士については、組み合わせの少なくとも一部について周辺リンク２２が存在しているとする。周辺リンク２２の総数をｍとする。総ノード同士の組み合わせのうちリンクが存在している割合をリンク確率Ｐと称す。このようなｎ−Ｓｔａｒネットワークのネットワーク指標としての、平均次数＜ｋ＞、平均経路長Ｌ、クラスタリング係数Ｃは、幾何学的な規則構造から、ｎおよびＮを用いて以下のように算出できる。なお、平均次数＜ｋ＞は、１ノードあたりが有するリンク数の平均値を示し、平均経路長Ｌは、あるノードから任意の別のノードまで到達するのに要するステップ数の平均値を示す。クラスタリング係数Ｃは、あるノードに隣接するノード同士が互いに隣接ノードである確率を示す。クラスタリング係数Ｃが高いネットワークは、関係の密度が高いことを示す。
【００２１】
【数１】
2014187624.tif 000003
【００２２】
なお、ｎ＝１の場合には、シングルスターネットワークになり、ｎ＝Ｎ−１およびｎ＝Ｎの場合には、完全グラフとなる。
【００２３】
ｎ−Ｓｔａｒネットワークにおいて、ある平均次数＜ｋ＞が与えられた場合に、平均経路長Ｌの最小値を求める過程で、Ｒ≡Ｌ＋Ｐ（但し、Ｐ＝＜ｋ＞／（Ｎ−１））なる量を導入すると、このＲの値は、ｎ，Ｎ，＜ｋ＞などに依存することなく、常に「２」であることが示される。一般的な複雑ネットワークのＲの値は常に「２」を超えることが示されている。したがって、Ｒの値は、スモール・ワールド性の指標とすることができ、「２」に近い値をもつネットワークほどスモール・ワールド性が高いことになる。
【００２４】
図５は、本実施の形態に従うｎ−ＳｔａｒネットワークのＲ値と平均次数＜ｋ＞との関係を他の複雑ネットワークと比較しつつ示すグラフである。なお、図５に示すシミュレーション例において、各ネットワークに含まれるノード総数Ｎ＝１００とした。
【００２５】
図５に示すグラフには、本実施の形態に従うｎ−Ｓｔａｒネットワークの比較対象として、ランダムグラフ、Ｗａｔｔｓ−Ｓｔｒｏｇａｔｚ（ＷＳ）モデル、Ｂａｒａｂａｓｉ−Ａｌｂｅｒｔ（ＢＡ）モデルを採用した。
【００２６】
図５を参照して、本実施の形態に従うｎ−ＳｔａｒネットワークのＲ値は、常に２であることがわかる。これに対して、ランダムグラフおよびＷＳモデルのＲ値は、相対的に大きい。ＢＡモデルは、スケールフリー・ネットワークをモデル化したものであり、その平均経路長Ｌはノード総数Ｎの対数に比例するというスケールフリー性を有するが、Ｒ値はランダムグラフおよびＷＳモデルに対してそれほど小さくはない。
【００２７】
図５に示す比較結果によれば、平均次数＜ｋ＞が相対的に小さい領域においては、ｎ−Ｓｔａｒネットワークの平均経路長Ｌ（＝Ｒ−Ｐ）は、他の複雑ネットワークに比較して、２０〜３０％程度減少しており、これは、ｎ−Ｓｔａｒネットワークが効率的なネットワーク伝達特性を有することを示す。すなわち、本実施の形態に従うｎ−Ｓｔａｒネットワークは、他の複雑ネットワークに比較して平均経路長が短く、クラスタリング係数Ｃも一般的に１に近い値をとるために、スモール・ワールド性を有していることが示される。
【００２８】
＜Ｃ．ｎ−Ｓｔａｒネットワークの頑健性＞
次に、本実施の形態に従うｎ−Ｓｔａｒネットワークの頑健性について説明する。図６は、本実施の形態に従うｎ−Ｓｔａｒネットワークの頑健性を他の複雑ネットワークと比較しつつ示すグラフである。図６に示すシミュレーション例においては、ネットワークを構成するリンクおよびノードがそれぞれある確率で故障するものとし、この場合に平均経路長Ｌがどのように変化するかを示す。より具体的には、ネットワークにおけるリンクの故障確率およびノードの故障確率をそれぞれＰｌおよびＰｎとし、これらの故障確率を重み係数αおよび（１−α）を用いてそれぞれ加算することで、ネットワークにおける故障確率Ｐｆ（＝α×Ｐｌ＋（１−α）×Ｐｎ）を導入する。この故障確率Ｐｆと平均経路長Ｌとの関係を図６に示す。なお、図６に示すシミュレーション例において、各ネットワークに含まれるノード総数Ｎ＝１００とし、ｎ−Ｓｔａｒネットワークのスターノード数ｎ＝３，重み係数α＝０．５とした。
【００２９】
図６に示すグラフには、本実施の形態に従うｎ−Ｓｔａｒネットワークの比較対象として、２極次数分布ネットワークおよびスケールフリー・ネットワーク（一例として、ＢＡモデル）を採用した。
【００３０】
図６に示すように、本実施の形態に従うｎ−Ｓｔａｒネットワークでは、故障確率Ｐｆの大きさにかかわらず、他のネットワークに比較して平均経路長Ｌが最も小さい。その上で、故障確率Ｐｆが０〜０．９５の範囲において、ｎ−Ｓｔａｒネットワークの平均経路長Ｌは、他のネットワークの平均経路長Ｌに対してほぼ２に抑えられており、ネットワーク故障に対する頑健性が最も高いことがわかる。
【００３１】
＜Ｄ．ｎ−Ｓｔａｒネットワークの自己修復機能＞
次に、本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能について説明する。典型的には、機器単体の故障や自然災害などの発生といったランダムな故障やサイバー攻撃などの人為的な攻撃を受けて、ネットワークを構成するノードおよび／またはリンクに何らかの障害が発生した場合を想定する。
【００３２】
図７は、本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能について説明するための図である。図７には、ｎ−Ｓｔａｒネットワークが何らかの障害を受けたときの修復アルゴリズムの一例を示す。図７（ａ）には、正常なｎ−Ｓｔａｒネットワークの一例を示す。このｎ−Ｓｔａｒネットワークに対して、ランダムな故障や人為的な攻撃を受けて、図７（ｂ）に示すようにｎ−Ｓｔａｒネットワークのノードやリンクに障害を受けた場合を考える。なお、図７（ｂ）において、「×」は障害発生箇所を示す。図７（ｂ）に示すような障害が発生すると、孤立ノードが多数生じることにより、実質的には、図７（ｃ）に示すように、ネットワークが分断された状態になる。
【００３３】
このようなネットワークが分断された状態において、部分的に機能しているスターノード同士、および周辺ノードとスターノードとの間で相互に通信しながら、自己組織的にリンクを張り替えることにより、図７（ｄ）に示すように、ノード総数Ｎ’（一般には、Ｎ’＜Ｎ）のｎ−Ｓｔａｒネットワークを再構築できる。
【００３４】
より具体的には、図７（ａ）に示すｎ−Ｓｔａｒネットワークにおいては、スターノード数ｎ＝３であるが、障害によって２つのスターノードが障害を受け、図７（ｃ）に示すｎ−Ｓｔａｒネットワークにおいては、スターノード数ｎ＝１になっている。この状態において、残存しているスターノードと周辺ノードのうち２つとの間でリンクを確立させ、これらの２つの周辺ノードを新たなスターノードとすることで、スターノード数ｎ＝３のｎ−Ｓｔａｒネットワークを修復できる。
【００３５】
このようなｎ−Ｓｔａｒネットワークの自己修復機能をシミュレーションした結果を以下に示す。
【００３６】
図８は、本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能のシミュレーション結果の一例を示す図である。図８には、スターノード数ｎ＝３、ノード総数Ｎ＝１００のｎ−Ｓｔａｒネットワークについての自己修復過程の一例を示す。図８（ａ）〜（ｃ）には、各過程のｎ−Ｓｔａｒネットワークのトポロジーおよび対応する隣接行列を示す。隣接行列は、ネットワークを構成する各ノード間にリンクが存在するか否かを示す行列であり、行および列は、いずれもノード番号を示す。隣接行列の値は、例えば、対象のノード間にリンクが存在する場合には「１」がセットされ、対象のノード間にリンクが存在しなければ「０」がセットされる。対象のネットワークが完全グラフであれば、その隣接行列において、対角成分は「０」となり、その他の成分はすべて「１」となる。
【００３７】
図８（ａ）には、障害が発生する前のｎ−Ｓｔａｒネットワークを示し、このとき、３つのスターノード（ノード番号＝１，２，３）と他のノードのすべてとの間にはリンクが形成されるので、対応する隣接行列は、ノード番号＝１，２，３に対応する行成分および列成分の要素値はいずれも「１」になる（但し、対角成分を除く）。
【００３８】
図８（ｂ）には、ｎ−Ｓｔａｒネットワークに障害が発生し、ノード番号＝２のスターノードをはじめ、いくつかの周辺ノードが障害を受けた状態を示す。この状態において、１つの周辺ノードを新たなスターノードとした上で、正常に機能するノード間でリンクを生成することで、図８（ｃ）に示すようなｎ−Ｓｔａｒネットワークを再構築できる。
【００３９】
図８（ｃ）に示す隣接行列において、新たなスターノードと他のノードとの間に生成されるリンクを示す（破線部分）。
【００４０】
このように、ｎ−Ｓｔａｒネットワークが比較的大きな障害を受けた場合でも、元のｎ−Ｓｔａｒネットワークと同じトポロジーをもつネットワーク構造へ自己組織的に修復できる。
【００４１】
＜Ｅ．ｎ−Ｓｔａｒネットワークの自己修復機能の処理手順＞
次に、本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能の処理手順について説明する。
【００４２】
本実施の形態に従うｎ−Ｓｔａｒネットワークにおいては、ｃｌｉｑｕｅを形成するｎ個のスターノードが必要であるので、何らかの障害が発生した場合には、まず、所定数のスターノードを確保する。この確保すべきスターノードの数は、障害発生前のｎ−Ｓｔａｒネットワークを構成したスターノードの数と同数が好ましいが、これより少なくてもよい。そして、スターノードが確保されると、スターノード間のリンクおよびスターノードと周辺ノードとの間のリンク（ならびに、必要に応じて周辺ノード間のリンク）が再構成される。
【００４３】
図９は、本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能の処理手順を示すフローチャートである。図９を参照して、ｎ−Ｓｔａｒネットワークの自己修復機能としては、まず、残存ノードおよび残存リンクの情報が取得される（ステップＳ２）。すなわち、互いに完全結合されたスターノードと、各々がスターノードのすべてとの間でリンクを有している周辺ノードとを含むオリジナルのネットワークのうち、残存しているノードおよびリンクが判断される。
【００４４】
続いて、残存ノードおよび残存リンクの情報に基づいて、残存ノードの各々について、評価値が算出される（ステップＳ４）。すなわち、必要な数のスターノードが残存しているか否かが判断される。この評価値は、修復対象としての優先度を示すものである。評価値は、各種パラメータを考慮して算出される。一例として、評価関数を用いて算出する方法について後述する。
【００４５】
この評価値を算出する際に考慮すべきパラメータとしては、典型的には、以下のようなものが挙げられる（但し、これらに限られるものではない）。
【００４６】
・ノード自体の優先度（上位ネットワークとの接続の有無／処理能力など）
・ノードの物理的位置（他のノードや重要設備からの距離など）
・ノード間の距離（ユークリッド距離／配線ルートに沿った距離など）
・ノードの通信チャネル数や処理可能数
・ノードの通信パワー（カバー範囲／セル範囲／到達可能距離）
・ノード間が互いに見通せるか否か
・他のノードとの間に残存しているリンク数
残存ノードの各々について評価値が算出されると、まず、必要な数のスターノードが残存しているか否かが判断される（ステップＳ６）。必要な数のスターノードが残存していなければ（ステップＳ６においてＮＯ）、ステップＳ４において算出された評価値に基づいて、周辺ノードから新たなスターノードが選択される（ステップＳ８）。すなわち、必要な数のスターノードが残存していない場合に、必要な数の周辺ノードが新たなスターノードとして決定される。
【００４７】
周辺ノードから新たなスターノードが選択された後（ステップＳ８の後）、または、必要な数のスターノードが残存している場合（ステップＳ６においてＹＥＳ）、スターノード間および各スターノードと周辺ノードとの間について、修復対象のリンクが決定される（ステップＳ１０）。すなわち、スターノード同士および各周辺ノードとスターノードのすべてとの間でリンクが再構成される。つまり、ｎ−Ｓｔａｒネットワークを再構築するために必要なリンクが特定される。
【００４８】
また、必要に応じて、周辺ノード間のリンク（周辺リンク）のうち、修復対象が決定される（ステップＳ１２）。このステップＳ１２の処理は、オプショナルな処理であり、必ずしも実行されなくともよい。すなわち、周辺ノード間のうちリンクを再構築する対象が決定される。
【００４９】
以上の処理によって、修復対象および修復方法が決定されると、修復処理が実行される（ステップＳ１４）。
【００５０】
＜Ｆ．ｎ−Ｓｔａｒネットワークの修復機能の具体例＞
次に、本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能の具体例について説明する。図１０は、本実施の形態に従うｎ−Ｓｔａｒネットワークの自己修復機能の具体例を説明する模式図である。図１０には、無線リンクおよび有線リンクを含むネットワークの一例を示す。図１０には、何らかの障害が発生し、いくつかのノードに障害が発生している状態のネットワークを示す。図１０を参照して、ネットワーク障害時における修復例について説明する。
【００５１】
図１０に示すネットワークにおいては、Ｎｏ．１〜Ｎｏ．１０までの１０個のノードが健全に存在しているとする。より具体的には、Ｎｏ．１のノードは衛星であり、Ｎｏ．２〜Ｎｏ．４のノードはアクセスポイント（基地局）であり、Ｎｏ．５〜Ｎｏ．１０の通信は残存している周辺ノードである。また、「×」を付しているノードは、何らかの障害を受けて通信不能になったノードを示す。また、実線は有線リンクを示し、破線は無線リンクを示す。
【００５２】
図１０に示す例では、衛星であるＮｏ．１のノードおよび基地局であるＮｏ．２〜Ｎｏ．４のノードの間は、完全結合されているとする。また、Ｎｏ．５〜Ｎｏ．１０のノードは、可能な限りＮｏ．２〜Ｎｏ．４のノード（基地局）と無線リンクで接続されているとする。さらに、Ｎｏ．５〜Ｎｏ．１０のノード同士は部分的にリンクが残存しているとする（図１０の例では、Ｎｏ．６のノードとＮｏ．７のノードとの間、Ｎｏ．７のノードとＮｏ．８のノードとの間、Ｎｏ．９のノードとＮｏ．１０のノードとの間にそれぞれ有線リンクがある）。
【００５３】
図１１は、図１０に示すネットワークの隣接行列を示す。なお、ノード同士のリンクは、双方向の場合と片方向の場合とがあるが、簡単化のために、図１１においては、双方向の場合を示す。
【００５４】
本実施の形態に従うｎ−Ｓｔａｒネットワークの修復処理の第一段階として、残存ノードおよび残存リンクの情報が取得される（図９のステップＳ２）。典型的には、各ノードは、他のノードとの間で通信を試みて、通信が成功したノード間にはすべてリンクを形成する。このように各ノードが他のノードとの間で通信可否を試みることで、残存ノードおよび残存リンクの情報が取得される。なお、図１０に示す例において、ノードが山などの地形の影に隠れている場合、ノード間が物理的に離れすぎている場合、一方または両方のノードの通信パワーが小さい場合などには、相互にリンクを形成できない。なお、以下の説明においては、各ノードは、リンクするために必要なチャネル数を十分に確保しているものとする。
【００５５】
続いて、残存ノードおよび残存リンクの情報に基づいて、残存ノードの各々について、評価値が算出される（図９のステップＳ４）。この評価値の算出に用いるパラメータの一例として、以下のような諸量を定義する。
【００５６】
・ノードｉの優先度：ｒ（ｉ），ｉ＝１，２，…，Ｎ
・ノードｉの物理的位置：Ｐ（Ｘｉ（ｔ））＝（ｘｉ（ｔ），ｙｉ（ｔ），ｚｉ（ｔ））
・ノードｉとノードｊとのユークリッド距離：ｄｉｊ（ｔ）＝｜Ｐ（Ｘｉ（ｔ））−Ｐ（Ｘｊ（ｔ））｜
・ノードｉの通信チャンネル数：Ｎｃｈ（ｉ）
・ノードｉの通信パワー：Ｐｏｗ（ｉ）
・ノードｉとノードｊとが互いに見通せるか否かの変数：Ｓｅｅ（ｉ，ｊ，ｔ）
見通せる場合：Ｓｅｅ（ｉ，ｊ，ｔ）＝１
見通せない場合：Ｓｅｅ（ｉ，ｊ，ｔ）＝０
これらの諸量に基づいて、ネットワーク全体の評価関数Ｈ（ｔ）を次のように定義する。ここで、ノードｉ（ｉ＝１，２，…，Ｎ）がモバイルノードである場合には、時間的および空間的に移動できるため、上記の評価関数Ｈ（ｔ）は、一般に時間ｔの関数となる。
【００５７】
【数２】
2014187624.tif 000004
【００５８】
なお、上述のパラメータをすべて用いる必要はなく、その一部を適宜用いるか、あるいはさらに別のパラメータを用いてもよい。すなわち、優先度を決定する処理においては、ノード自体の優先度、ノードの物理的位置、ノード間の距離、ノードの通信チャネル数、ノードの処理可能数、ノードの通信パワー、ノード間が互いに見通せるか否か、の少なくとも１つを用いて、各ノードの優先度が算出される。
【００５９】
続いて、必要な数のスターノードが残存しているか否かが判断される（図９のステップＳ６）。本実施の形態に従うｎ−Ｓｔａｒネットワークにおいては、互いに完全結合したｎ個のスターノードが必要である。図１０に示す例では、Ｎｏ．１〜Ｎｏ．４のノード同士が互いに完全結合しており、ｎ＝４のスターノードが形成されている。すなわち、図１０には、必要な数のスターノードが残存している例を示す。但し、スターノードが不足する場合には、優先度の高い周辺ノードが新たなスターノードとして選択される。つまり、スターノード同士は完全に結合できるように通信を試みるとともに、各周辺ノードはいずれのスターノードとも少なくともリンクできるように通信を試みる。そして、リンクできるスターノードとはすべてリンクが形成される。
【００６０】
ここで優先度の決定方法としては、関数ｈ（ｉ，ｊ，ｔ）（≡ｒ（ｉ）×ｒ（ｊ）×Ｐｏｗ（ｉ）×Ｐｏｗ（ｊ）×Ｎｃｈ（ｉ）×Ｎｃｈ（ｊ）×Ｓｅｅ（ｉ，ｊ，ｔ）／ｄｉｊ（ｔ））を導入し、各ノードｉについて、以下のように評価値ｈ＊（ｉ，ｔ）を算出し、算出された評価値ｈ＊（ｉ，ｔ）が大きい方から順に対象のノードをソートする。そして、より上位にソートされるほど優先度がより高いノードであると判断する。
【００６１】
【数３】
2014187624.tif 000005
【００６２】
なお、元来Ｎｏ．１〜Ｎｏ．４のノードはスターノードであるため、修復時にはこれらのノードは優先的にスターノードとして選択される。これは、衛星であるＮｏ．１のノードは、通信に対する障害物がないため、スターノード（の候補）として最優先に選択される。また、Ｎｏ．２〜Ｎｏ．４のノードは、アクセスポイント（基地局）であるため、スターノード（の候補）として優先的に選択される。なお、これらの特性を反映するために、上述の評価関数Ｈ（ｔ）において、これらのノードについての優先度ｒ（ｉ）を十分に大きな値に設定しておくことで、スターノードとして優先的に選択できる。
【００６３】
一方、Ｎｏ．１〜Ｎｏ．４のノードの全部または一部が障害の発生によってスターノードとして利用できない場合には、Ｎｏ．５〜Ｎｏ．１０の周辺ノード群のうち、評価値ｈ＊（ｉ，ｔ）がより大きな周辺ノードから順にスターノードとして選択される。すなわち、それぞれの周辺ノードに対して評価値ｈ＊（ｉ，ｔ）に従って優先度を決定するとともに、当該決定した優先度に基づいて必要な数のスターノードが選択される。このように、スターノードを選択することで、ノード群全体でｎ−Ｓｔａｒネットワークを自己組織的に再構成する。
【００６４】
このように、周辺ノードから新たなスターノードが選択される（図９のステップＳ８）。つまり、新たなスターノードを決定する工程は、各周辺ノードについて、修復対象としての優先度を決定する工程と、優先度のより高い周辺ノードを新たなスターノードとして選択する工程とを含む。
【００６５】
そして、スターノード間および各スターノードと周辺ノードとの間について、修復対象のリンクが決定される（図９のステップＳ１０）。より具体的には、スターノード以外の周辺ノードについては、より大きな評価値ｈ＊（ｉ，ｔ）をもつ周辺ノードｉから優先的に、スターノードとの間のリンク形成の対象として決定される。このとき、各スターノードは、ネットワークに含まれるノード総数Ｎ以上の通信チャンネル数を有しており、各周辺ノードは、スターノード数ｎ以上の通信チャンネルを有しているものとする。また、いずれかの周辺ノードの通信チャンネル数に余裕がある場合には、必要に応じて他の周辺ノードとの間でリンクが形成される。すなわち、必要に応じて、周辺ノード間のリンク（周辺リンク）のうち、修復対象が決定される（図９のステップＳ１２）。
【００６６】
このように修復対象および修復方法が決定されると、修復処理が順次実行される（図９のステップＳ１４）。なお、修復対象および修復方法の決定と修復処理の実行とは並列的に実行されてもよい。
【００６７】
以上のような一連の修復動作により、ほぼ十分なｎ−Ｓｔａｒネットワークを再構築することができる。図１０に示す具体例においては、完全なｎ−Ｓｔａｒネットワークまでには復元されていないが、上述したような少なくとも１つ以上のスターノード（図１０では、４個のスターノードが存在する）を復元するとともに、スターノードと周辺ノードとの間にリンクを形成できれば、平均経路長Ｌを約２にすることができ（図６も参照）、効率的な通信機能を回復させることが可能である。
【００６８】
＜Ｇ．コンピュータによる実現＞
上述したようなｎ−Ｓｔａｒネットワークの自己修復機能について、コンピュータを用いて実現してもよい。この場合には、プロセッサがプログラムを実行することで、上述のような処理を実現する。このようなプログラムは、汎用的なコンピュータを用いて実行させることができる。
【００６９】
図１２は、本実施の形態に係るｎ−Ｓｔａｒネットワークの自己修復機能を実現するためのコンピュータ１００の構成を示す模式図である。図１２を参照して、コンピュータ１００は、汎用的なアーキテクチャを有しており、ＣＰＵ（Central Processing Unit）１０２と、ＲＡＭ（Random Access Memory）１０４と、ハードディスク１０６と、光学ドライブ１１２と、入力部１１６と、表示部１１８と、ネットワークインターフェイス１２０とを含む。これらのコンポーネントは、バス１２２を介して、互いに接続されている。
【００７０】
ＣＰＵ１０２は、ハードディスク１０６などに格納されている修復プログラム１０８を読出して実行することで、上述したような処理を実現する。ＲＡＭ１０４は、ＣＰＵ１０２でのプログラム実行に必要なワークデータを一次的に記憶する。ハードディスク１０６は、上述のような処理を実現するための修復プログラム１０８と、対象のｎ−Ｓｔａｒネットワークに係るパラメータなどを示す設定値データ１１０とを保持している。
【００７１】
光学ドライブ１１２は、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）１１４などに格納されて配布される修復プログラム１０８を読出して、ハードディスク１０６などにインストールされる。すなわち、本実施の形態に係るｎ−Ｓｔａｒネットワークの自己修復機能を実現するための修復プログラムは、ＣＤ−ＲＯＭなどの記録媒体へ格納されて配布等されてもよい。
【００７２】
入力部１１６は、キーボードやマウスなどを含み、ユーザからの各種操作を受付ける。表示部１１８は、ディスプレイなどを含み、修復プログラム１０８の実行によって得られる結果などを表示する。ネットワークインターフェイス１２０は、外部装置との間でネットワークを介してデータを遣り取りする。なお、修復プログラム１０８は、ネットワークインターフェイス１２０を介してハードディスク１０６にインストールされてもよい。
【００７３】
＜Ｈ．適用例＞
上述の説明においては、主として情報通信ネットワークへの適用例について説明したが、これに限られることはなく、本発明は、各種のネットワークに適用可能である。より具体的な一例として、本発明は、電力網や水道網といったインフラ・ネットワークや、交通網・流通網や航空網といったロジスティクス・ネットワークに対してもそのまま適用できる。
【００７４】
例えば、電力網に適用する場合には、各ノードは、発電所、変電所、配電所、需要家などのパワーノードに対応し、各リンクは、それぞれのパワーノードを結ぶ電力線に対応する。
【００７５】
ロジスティクス・ネットワークの一例である鉄道や道路などの交通網・流通網に適用する場合、各ノードは、駅やインターチェンジなどに対応し、各リンクは、鉄道線路や道路などに対応する。また、ロジスティクス・ネットワークの別の一例である航空網に適用する場合には、各ノードは、空港に対応し、各リンクは航路に対応する。
【００７６】
これらのネットワークに対してｎ−Ｓｔａｒネットワーク構造を適用することで、上述したような効率性、頑健性、自己修復性をもたせることができる。
【００７７】
例えば、ロジスティクス・ネットワークである航空網を考えた場合、スターノードはハブ空港などの拠点空港が対応し、周辺ノードはそれ以外の周辺の空港が対応する。もし、一部の空港や航路が自然災害（例えば、地震や津波など）や気象条件（例えば、大雪や火山の噴火など）によって使用不能になった場合でも、他のバイパス経路をとることにより、頑健性を担保しながら、同時に最も効率的な経路を確保できる。また、状況に応じて、臨機応変に新しく航路を繋ぎかえる自己修復機能によって、ｎ−Ｓｔａｒネットワークの本来もつ優れた機能を自動的に回復させることが可能である。
【００７８】
さらに、情報通信ネットワーク、インフラ・ネットワーク（電力網、水道網など）、ロジスティクス・ネットワーク（交通網・流通網や航空網）の効率性および頑健性を向上させることで、維持費および燃費を削減できるとともに、さらにはＣＯ２削減による地球温暖化防止などにも効果がある。
【００７９】
＜Ｉ．利点＞
本実施の形態に従うｎ−Ｓｔａｒネットワークは、平均経路長が絶対的に小さくなるスモール・ワールド性を有しており、ランダムな故障およびサイバー攻撃などの人為的な攻撃の両方に強い特性（頑健性）を有するだけでなく、故障確率が相当大きい場合でもスモール・ワールド性を維持できる。その上で、本実施の形態に従うｎ−Ｓｔａｒネットワークは、故障したり、外部からのサイバー攻撃を受け致命的な障害を受けてバラバラに分断されたりして、もはやネットワークとしての機能を果たせなくなった場合でも、残されたノードから自己組織的に、元のスモール・ワールド性をもつネットワークに自動的に修復できる。
【００８０】
今回開示された実施の形態は、すべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は、上記した実施の形態の説明ではなくて請求の範囲によって示され、請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【符号の説明】
【００８１】
１０  スターノード、１２  リンク、２０  周辺ノード、２２  周辺リンク、１００  コンピュータ、１０２  ＣＰＵ、１０４  ＲＡＭ、１０６  ハードディスク、１０８  修復プログラム、１１０  設定値データ、１１２  光学ドライブ、１１６  入力部、１１８  表示部、１２０  ネットワークインターフェイス、１２２  バス。
【図１】
2014187624.tif 000006
【図２】
2014187624.tif 000007
【図３】
2014187624.tif 000008
【図４】
2014187624.tif 000009
【図５】
2014187624.tif 000010
【図６】
2014187624.tif 000011
【図７】
2014187624.tif 000012
【図９】
2014187624.tif 000013
【図１０】
2014187624.tif 000014
【図１１】
2014187624.tif 000015
【図１２】
2014187624.tif 000016
【図８】
2014187624.tif 000017