(57)【要約】【課題】ネットワークの各端末ノードから効率よく情報収集できるように代表ノードを配置する。【解決手段】ネットワークの外周ノードは、自ノードと自ノードに隣接する２つの外周ノードとを通る円を想定した自身の位置とその位置での円の法線単位ベクトルおよび曲率とを求め、その位置から法線単位ベクトルに沿って曲率のα乗（０＜α＜１）に比例する距離にあるフロー位置を計算し、フロー位置が他ノードの区域にある場合は他ノードにフロー位置を通知する。フロー位置を通知された端末ノードは、そのフロー位置と同一の計算回数の隣接ノードのフロー位置と当該通知されたフロー位置に基づく始点とを用いて新たなフロー位置を計算し、計算回数が等しいフロー位置同士による多角形の重心が位置計算ごと所定範囲に収まる場合は自ノードの区域への移動を代表ノードに指示する。代表ノードは指示が表す区域に移動する。【選択図】図１０
2011024090.tif 000002
【特許請求の範囲】
【請求項１】
それぞれが区域を有する複数の端末ノードと該複数の端末ノードから情報を収集する代表ノードとを含むネットワークの前記複数の端末ノードのそれぞれに、相互間の隣接関係および相対位置に関するリストを設定し、
前記複数の端末ノードのうち前記ネットワークの外周に位置する端末ノードである外周ノードのそれぞれが、自ノードと自ノードを挟んで隣接する２つの外周ノードとを通る円を想定した自身の仮想位置であるフロー位置および該フロー位置における前記円の法線単位ベクトルならびに前記円の曲率を求め、前記フロー位置から前記法線単位ベクトルに沿って前記曲率のα乗（０＜α＜１）に比例する距離にあるフロー位置を計算して前記リストに記録し、前記フロー位置が自ノードの区域にある場合は当該フロー位置と前記自ノードを挟んで隣接する外周ノードにおける初回の計算によるフロー位置とを用いて自ノードの２回目の計算によるフロー位置を求め、前記フロー位置が他ノードの区域にある場合は当該他ノードへ当該フロー位置と該フロー位置の計算回数とを通知し、
前記外周ノードからフロー位置を通知された端末ノードのそれぞれが、自ノードを挟んで隣接する２つの端末ノードが算出したフロー位置のうち前記通知されたフロー位置と同一の計算回数のフロー位置と当該通知されたフロー位置に基づく始点とを用いて新たなフロー位置を計算し、前記新たなフロー位置が他ノードの区域にある場合は当該他ノードへ当該新たなフロー位置と該新たなフロー位置の計算回数とを通知し、前記新たなフロー位置を含めた複数のフロー位置が自ノードの区域にある場合は計算回数が同一のフロー位置同士により形成される多角形の重心を求め、新たなフロー位置を計算するごとに求めた前記重心の差が所定範囲に収まる場合は自ノードの区域への移動を前記代表ノードに指示し、
前記代表ノードが、前記指示が表す区域に移動することを特徴とする代表ノード配置方法。
【請求項２】
前記各端末ノードが、自ノードのフロー位置ｐからフロー位置に関するｔ回目の計算を行うとき、前記αを１／３として規定した式（１）に従い実行することを特徴とする請求項１記載の代表ノード配置方法。
【数２】
2011024090.tif 000004
【請求項３】
前記外周ノードからフロー位置を通知された端末ノードのそれぞれが、前記新たなフロー位置を含めた複数のフロー位置が自ノードの区域にあり、かつ新たなフロー位置を計算するごとに求めた重心の差が所定範囲を超える場合は、前記自ノードの区域にある複数のフロー位置の中から計算回数が最多のフロー位置を選択し、当該選択したフロー位置に残りのフロー位置を統合し、当該統合したフロー位置を前記始点として用いることを特徴とする請求項１又は２記載の代表ノード配置方法。
【請求項４】
前記重心の差は、前記新たなフロー位置を含む多角形の重心と、当該新たなフロー位置よりも計算回数が１つ少ないフロー位置に関する重心との差であることを特徴とする請求項１乃至３のいずれか１項に記載の代表ノード配置方法。
【請求項５】
前記外周ノードからフロー位置を通知された端末ノードのそれぞれが、自ノードにより計算したフロー位置を他ノードへ通知するとき自ノードの識別情報を当該フロー位置に関連付けて通知し、他ノードからフロー位置を通知されたとき当該フロー位置に関連付けられている端末ノードの識別情報を経路表に記録し、
自ノードの区域への移動を前記代表ノードに指示する前記端末ノードが、当該指示を記述した移動情報を前記代表ノードに宛てて発信し、
前記移動情報を発信した端末ノード以外の端末ノードが、前記経路表に基づく経路に沿って当該移動情報を前記代表ノードへ転送することを特徴とする請求項１乃至４のいずれか１項に記載の代表ノード配置方法。
【請求項６】
前記移動情報を発信した端末ノード以外の端末ノードが、前記移動情報を転送するとき、当該移動情報に自ノードの識別情報を付加し、
前記代表ノードが、前記移動情報を受信したとき、当該移動情報に付加されている識別情報に対応する各端末ノードの区域に順次移動することにより、当該移動情報に記述されている指示が表す区域に移動することを特徴とする請求項５記載の代表ノード配置方法。
【請求項７】
それぞれが区域を有する複数の端末ノードと、
前記複数の端末ノードから情報を収集する代表ノードとを備え、
前記複数の端末ノードのそれぞれは、
前記複数の端末ノードおよび前記代表ノードを含むネットワークにおける当該複数の端末ノード間の隣接関係および相対位置に関するリストと、
自ノードが前記ネットワークの外周に位置する外周ノードである場合に、自ノードと自ノードを挟んで隣接する２つの外周ノードとを通る円を想定した自身の仮想位置であるフロー位置および該フロー位置における前記円の法線単位ベクトルならびに前記円の曲率を求め、前記フロー位置から前記法線単位ベクトルに沿って前記曲率のα乗（０＜α＜１）に比例する距離にあるフロー位置を計算して前記リストに記録し、前記フロー位置が自ノードの区域にある場合は当該フロー位置と前記自ノードを挟んで隣接する２つの外周ノードにおける初回の計算によるフロー位置とを用いて自ノードの２回目の計算によるフロー位置を求め、前記フロー位置が他ノードの区域にある場合は当該他ノードへ当該フロー位置と該フロー位置の計算回数とを通知し、自ノードが前記ネットワークの外周ノードからフロー位置を通知された場合に、自ノードを挟んで隣接する２つの端末ノードが算出したフロー位置のうち前記通知されたフロー位置と同一の計算回数のフロー位置と当該通知されたフロー位置に基づく始点とを用いて新たなフロー位置を計算し、前記新たなフロー位置が他ノードの区域にある場合は当該他ノードへ当該新たなフロー位置と該新たなフロー位置の計算回数とを通知する計算部と、
前記新たなフロー位置を含めた複数のフロー位置が自ノードの区域にある場合は計算回数が同一のフロー位置同士により形成される多角形の重心を求め、新たなフロー位置を計算するごとに求めた前記重心の差が所定範囲に収まる場合は自ノードの区域への移動を前記代表ノードに指示する収束検知部とを有し、
前記代表ノードは、前記複数の端末ノードの何れかからの前記指示が表す区域に移動する移動部を有することを特徴とするシステム。
【請求項８】
前記計算部は、自ノードが計算したフロー位置ｐからフロー位置に関するｔ回目の計算を行うとき、前記αを１／３として規定した式（１）に従い実行することを特徴とする請求項７記載のシステム。
【数３】
2011024090.tif 000005
【請求項９】
前記計算部は、前記外周ノードからフロー位置を通知された場合に、前記新たなフロー位置を含めた複数のフロー位置が自ノードの区域にあり、かつ新たなフロー位置を計算するごとに求めた重心の差が所定範囲を超える場合は、前記自ノードの区域にある複数のフロー位置の中から計算回数が最多のフロー位置を選択し、当該選択したフロー位置に残りのフロー位置を統合し、当該統合したフロー位置を前記始点として用いることを特徴とする請求項７又は８記載のシステム。
【請求項１０】
前記重心の差は、前記新たなフロー位置を含む多角形の重心と、当該新たなフロー位置よりも計算回数が１つ少ないフロー位置に関する重心との差であることを特徴とする請求項７乃至９のいずれか１項に記載のシステム。
【請求項１１】
前記計算部は、前記外周ノードからフロー位置を通知された場合に、自ノードにより計算したフロー位置を他ノードへ通知するとき自ノードの識別情報を当該フロー位置に関連付けて通知し、他ノードからフロー位置を通知されたとき当該フロー位置に関連付けられている端末ノードの識別情報を経路表に記録し、
前記収束検知部は、自ノードの区域への移動を前記代表ノードに指示するとき、当該指示を記述した移動情報を前記代表ノードに宛てて発信し、他ノードから発信された移動情報を受信した場合は、前記経路表に基づく経路に沿って当該移動情報を前記代表ノードへ転送することを特徴とする請求項７乃至１０のいずれか１項に記載のシステム。
【請求項１２】
前記各端末ノードの収束検知部は、前記他ノードから発信された移動情報を転送するとき、当該移動情報に自ノードの識別情報を付加し、
前記代表ノードの移動部は、前記移動情報を受信したとき、当該移動情報に付加されている識別情報に対応する各端末ノードの区域に順次移動することにより、当該移動情報に記述されている指示が表す区域に移動することを特徴とする請求項１１記載のシステム。
【請求項１３】
それぞれが区域を有する複数の端末ノードと該複数の端末ノードから情報を収集する代表ノードとを含むネットワークにおける前記複数の端末ノードのいずれかであって、
前記ネットワークにおける前記複数の端末ノード間の隣接関係および相対位置に関するリストと、
自ノードが前記ネットワークの外周に位置する外周ノードである場合に、自ノードと自ノードを挟んで隣接する２つの外周ノードとを通る円を想定した自身の仮想位置であるフロー位置および該フロー位置における前記円の法線単位ベクトルならびに前記円の曲率を求め、前記フロー位置から前記法線単位ベクトルに沿って前記曲率のα乗（０＜α＜１）に比例する距離にあるフロー位置を計算して前記リストに記録し、前記フロー位置が自ノードの区域にある場合は当該フロー位置と前記隣接する各端末ノードにおける初回の計算によるフロー位置とを用いて自ノードの２回目の計算によるフロー位置を求め、前記フロー位置が他ノードの区域にある場合は当該他ノードへ当該フロー位置と該フロー位置の計算回数とを通知し、自ノードが前記ネットワークの外周ノードからフロー位置を通知された場合に、自ノードを挟んで隣接する２つの端末ノードが算出したフロー位置のうち前記通知されたフロー位置と同一の計算回数のフロー位置と当該通知されたフロー位置に基づく始点とを用いて新たなフロー位置を計算し、前記新たなフロー位置が他ノードの区域にある場合は当該他ノードへ当該新たなフロー位置と該新たなフロー位置の計算回数とを通知する計算部と、
前記新たなフロー位置を含めた複数のフロー位置が自ノードの区域にある場合は計算回数が同一のフロー位置同士により形成される多角形の重心を求め、新たなフロー位置を計算するごとに求めた前記重心の差が所定範囲に収まる場合は自ノードの区域への移動を前記代表ノードに指示する収束検知部とを備えることを特徴とする端末ノード。
【請求項１４】
前記計算部は、自ノードが計算したフロー位置ｐからフロー位置に関するｔ回目の計算を行うとき、前記αを１／３として規定した式（１）に従い実行することを特徴とする請求項１３記載の端末ノード。
【数４】
2011024090.tif 000006
【請求項１５】
前記計算部は、前記外周ノードからフロー位置を通知された場合に、前記新たなフロー位置を含めた複数のフロー位置が自ノードの区域にあり、かつ新たなフロー位置を計算するごとに求めた重心の差が所定範囲を超える場合は、前記自ノードの区域にある複数のフロー位置の中から計算回数が最多のフロー位置を選択し、当該選択したフロー位置に残りのフロー位置を統合し、当該統合したフロー位置を前記始点として用いることを特徴とする請求項１３又は１４記載の端末ノード。
【請求項１６】
前記重心の差は、前記新たなフロー位置を含む多角形の重心と、当該新たなフロー位置よりも計算回数が１つ少ないフロー位置に関する重心との差であることを特徴とする請求項１３乃至１５のいずれか１項に記載の端末ノード。
【請求項１７】
前記計算部は、前記外周ノードからフロー位置を通知された場合に、自ノードにより計算したフロー位置を他ノードへ通知するとき自ノードの識別情報を当該フロー位置に関連付けて通知し、他ノードからフロー位置を通知されたとき当該フロー位置に関連付けられている端末ノードの識別情報を経路表に記録し、
前記収束検知部は、自ノードの区域への移動を前記代表ノードに指示するとき、当該指示を記述した移動情報を前記代表ノードに宛てて発信し、他ノードから発信された移動情報を受信した場合は、前記経路表に基づく経路に沿って当該移動情報を前記代表ノードへ転送することを特徴とする請求項１３乃至１６のいずれか１項に記載の端末ノード。
【請求項１８】
前記各端末ノードの収束検知部は、前記他ノードから発信された移動情報を転送するとき、当該移動情報に自ノードの識別情報を付加することを特徴とする請求項１７記載の端末ノード。
【請求項１９】
コンピュータを請求項１３乃至１８のいずれか１項に記載の端末ノードとして機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、無線ネットワークあるいはセンサネットワークのように、複数の端末ノードとそれらから情報を収集する代表ノードとから構成されるネットワークに関する。
【背景技術】
【０００２】
センサネットワーク（以下、「センサＮＷ」と記す。）では、端末ノードとしての複数のセンサノードと、これらに対する情報の収集機能および配布機能を備えた代表ノードとしてのシンクノードとが設けられる。各センサノードは、通信機能を備え、他のセンサノードを経由してシンクノードと情報を交換することができる。
【０００３】
センサＮＷにおいては、カバレッジ内の情報収集を短時間、かつ低消費電力で行うために、（１）代表ノードが最短時間で情報収集を行うための代表ノードの配置、及び、（２）代表ノードが最短時間で情報収集を行うための経路制御が重要な要素技術である。
【０００４】
上記（１）及び（２）を実現するには、［Ａ］自律分散性、［Ｂ］自己組織性、［Ｃ］スケーラブルという３つの要素が必須となる。［Ａ］および［Ｂ］に関しては、ＮＷ内のノード数が多くなると破綻するため、各ノードが何らかの判断基準に基づいて動作する必要がある。［Ｃ］に関しては、ＮＷ内のノード数の大小によらず、ＮＷを管理するための同じ方法が適用可能であることが要件となる。
【０００５】
なお、上記（１）、（２）の要素技術および［Ａ］〜［Ｃ］の必須要素は、センサＮＷのみならず、無線ＮＷにおいても同様に重要である。（以下、センサＮＷにおけるセンサノードと、無線ＮＷにおける無線端末とを総称して「端末ノード」と記す）。
【０００６】
代表ノードの配置に関し、例えば、後述の特許文献１〜１０、及び、非特許文献１,２に記載のものがある。特許文献１〜５には、電力制御によって代表ノードの出力を大きくすることで通信可能距離を伸ばすという手法が示されている。特許文献６,８,１０には、ノードをクラスタに分け、各クラスタ内に代表ノードを決定するクラスタヘッドを設置し、クラスタ内での送信電力を最小化するという方法が記載されている。特許文献７には、伝送経路の効率化を目的として、ＮＷのノードを階層することが開示されている。特許文献９には、センサＮＷにおいて２つの無線方式の情報を交換することで情報収集な範囲を広げる方法や、その２つの通信方式を用いて階層的なトポロジを構成することが記載されている。
【０００７】
非特許文献１には、一般に知られている反応拡散方程式モデルを用いてチューリングパターンを形成し、その濃度勾配に従ってＮＷを複数のクラスタに分割して経路を作成する方法が記載されている。非特許文献２には、蟻の餌探索行動を用いた最短距離経路の構築に関する手法が掲載されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００８−１２５０７９号公報
【特許文献２】特開２００８−０６０９９４号公報
【特許文献３】特開２００８−０２２４８４号公報
【特許文献４】特開２００７−３０６４０７号公報
【特許文献５】特開２００４−０３２６４０号公報
【特許文献６】特開２００８−０７８９６３号公報
【特許文献７】特開２００７−０５３７６５号公報
【特許文献８】特開２００８−０７８９６３号公報
【特許文献９】特開２００５−１８４７２７号公報
【特許文献１０】特再表２００６／０６７９２２号公報
【非特許文献】
【０００９】
【非特許文献１】Naoki Wakamiya, Katsuya Hyodo, and Masayuki Murata、 “Reaction-diffusion based topology self-organization for periodic data gathering in wireless sensor networks”、Proceedings of Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems (SASO 2008)、pp. 351-360、October 2008
【非特許文献２】木利友一、菅野正嗣、村田正幸、「マルチシンク構成のセンサネットワークにおけるロバストな情報収集メカニズムの提案と評価」、電子情報通信学会・情報ネットワーク研究会、２００７年３月
【非特許文献３】S. L. Smith, M. E. Broucke, and B. A. Francis、“Curve Shortening and the Rendezvous Problem for Mobile Autonomous Robots”、IEEE Transactions on Automatic Control、52(6):1154-1159、2007
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上記特許文献１〜５に記載の技術によれば、通信可能距離を伸ばすことが可能となるが、上記（２）の実現は考慮されていない。また、所要出力エネルギーは距離の２乗に比例するので、ノードの消費電力が増大するという問題もある。上記特許文献６,８,１０に記載の技術は、クラスタヘッドによる集中管理方式であるため、前記要件［Ａ］および［Ｂ］を満たさず、クラスタヘッドが故障した場合はシステム全体の動作が中断するという問題がある。特許文献７は、前記［Ｃ］の要件を概ね満たすが、ハブノードが故障すると、その配下のノードが機能しなくなるという点で、要件［Ａ］、［Ｂ］を満たさない。
【００１１】
非特許文献１の手法は、所望のチューリングパターンを事前に設定しなければならないため、要件［Ａ］および［Ｂ］を実現できない。また、濃度がＮＷ全体に拡散しなければならないため、ＮＷが大きくなるほど収束する時間が大きくなるため、要件［Ｃ］を満たさない。非特許文献２の手法は、要件［Ａ］および［Ｂ］は概ね満たすものの、ＮＷが大きくなるほど収束する時間が大きくなり、要件［Ｃ］を満たさない。
【００１２】
本発明の目的は、ネットワーク内の各端末ノードから効率よく情報収集することができるように代表ノードを配置する方法およびシステムを提供することにある。
【課題を解決するための手段】
【００１３】
本発明に係る代表ノード配置方法は、それぞれが区域を有する複数の端末ノードと該複数の端末ノードから情報を収集する代表ノードとを含むネットワークの前記複数の端末ノードのそれぞれに、相互間の隣接関係および相対位置に関するリストを設定し、前記複数の端末ノードのうち前記ネットワークの外周に位置する端末ノードである外周ノードのそれぞれが、自ノードと自ノードを挟んで隣接する２つの外周ノードとを通る円を想定した自身の仮想位置であるフロー位置および該フロー位置における前記円の法線単位ベクトルならびに前記円の曲率を求め、前記フロー位置から前記法線単位ベクトルに沿って前記曲率のα乗（０＜α＜１）に比例する距離にあるフロー位置を計算して前記リストに記録し、前記フロー位置が自ノードの区域にある場合は当該フロー位置と前記自ノードを挟んで隣接する外周ノードにおける初回の計算によるフロー位置とを用いて自ノードの２回目の計算によるフロー位置を求め、前記フロー位置が他ノードの区域にある場合は当該他ノードへ当該フロー位置と該フロー位置の計算回数とを通知し、前記外周ノードからフロー位置を通知された端末ノードのそれぞれが、自ノードを挟んで隣接する２つの端末ノードが算出したフロー位置のうち前記通知されたフロー位置と同一の計算回数のフロー位置と当該通知されたフロー位置に基づく始点とを用いて新たなフロー位置を計算し、前記新たなフロー位置が他ノードの区域にある場合は当該他ノードへ当該新たなフロー位置と該新たなフロー位置の計算回数とを通知し、前記新たなフロー位置を含めた複数のフロー位置が自ノードの区域にある場合は計算回数が同一のフロー位置同士により形成される多角形の重心を求め、新たなフロー位置を計算するごとに求めた前記重心の差が所定範囲に収まる場合は自ノードの区域への移動を前記代表ノードに指示し、前記代表ノードが、前記指示が表す区域に移動するという方法である。
【００１４】
本発明に係るシステムは、それぞれが区域を有する複数の端末ノードと、前記複数の端末ノードから情報を収集する代表ノードとを備え、前記複数の端末ノードのそれぞれは、前記複数の端末ノードおよび前記代表ノードを含むネットワークにおける当該複数の端末ノード間の隣接関係および相対位置に関するリストと、自ノードが前記ネットワークの外周に位置する外周ノードである場合に、自ノードと自ノードを挟んで隣接する２つの外周ノードとを通る円を想定した自身の仮想位置であるフロー位置および該フロー位置における前記円の法線単位ベクトルならびに前記円の曲率を求め、前記フロー位置から前記法線単位ベクトルに沿って前記曲率のα乗（０＜α＜１）に比例する距離にあるフロー位置を計算して前記リストに記録し、前記フロー位置が自ノードの区域にある場合は当該フロー位置と前記自ノードを挟んで隣接する２つの外周ノードにおける初回の計算によるフロー位置とを用いて自ノードの２回目の計算によるフロー位置を求め、前記フロー位置が他ノードの区域にある場合は当該他ノードへ当該フロー位置と該フロー位置の計算回数とを通知し、自ノードが前記ネットワークの外周ノードからフロー位置を通知された場合に、自ノードを挟んで隣接する２つの端末ノードが算出したフロー位置のうち前記通知されたフロー位置と同一の計算回数のフロー位置と当該通知されたフロー位置に基づく始点とを用いて新たなフロー位置を計算し、前記新たなフロー位置が他ノードの区域にある場合は当該他ノードへ当該新たなフロー位置と該新たなフロー位置の計算回数とを通知する計算部と、前記新たなフロー位置を含めた複数のフロー位置が自ノードの区域にある場合は計算回数が同一のフロー位置同士により形成される多角形の重心を求め、新たなフロー位置を計算するごとに求めた前記重心の差が所定範囲に収まる場合は自ノードの区域への移動を前記代表ノードに指示する収束検知部とを有し、前記代表ノードは、前記複数の端末ノードの何れかからの前記指示が表す区域に移動する移動部を有する。
【発明の効果】
【００１５】
本発明によれば、ネットワーク内の各端末ノードから効率よく情報収集することができる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施形態におけるネットワークの構成図である。
【図２】本発明の実施形態におけるセンサノードの構成を示すブロック図である。
【図３】本発明の実施形態におけるセンサノードの結合リストの説明図である。
【図４】本発明の実施形態におけるシンクノードの構成を示すブロック図である。
【図５】本発明の実施形態における外周ノードの初期動作に関する説明図である。
【図６】本発明の実施形態における外周ノードの１回目の計算によるフロー位置に関する説明図である。
【図７】本発明の実施形態におけるセンサノードの２回目以降の計算によるフロー位置に関する説明図である。
【図８】本発明の実施形態におけるフロー位置の統合に関する説明図である。
【図９】本発明の実施形態におけるフロー位置の収束に関する説明図である。
【図１０】本発明の実施形態における外周ノードのセンサノードのフローチャートである。
【図１１】本発明の実施形態における外周ノード以外のセンサノードのフローチャートである。
【図１２】本発明の実施形態においる収束点を検出したセンサノードのフローチャートである。
【図１３】本発明の実施形態における収束点を検出したセンサノード以外のセンサノードのフローチャートである。
【図１４】本発明の実施形態におけるシンクノードのフローチャートである。
【発明を実施するための形態】
【００１７】
本発明の１つの実施形態について図面を参照して詳細に説明する。本実施形態は、センサＮＷを想定したものであるが、無線ＮＷにも適用することができる。本実施形態は、複数のセンサノードと該各センサノードから情報を収集するシンクノードとを含むセンサＮＷにおいて、前述の要素技術（１）、（２）を、必須要素［Ａ］〜［Ｃ］をふまえて実現するものである。そのために、次の２つの手段1.及び2.が採用される。
【００１８】
1.  非特許文献３に記載されている、仮想的なフローの概念を用いるPoligonal Affine Shortening理論を用いる。この理論では、２次元ユークリッド空間における自己交差しない任意の閉じた多角形において、その多角形上の全てのノードが、自身と隣り合う２つのノードとを通る外接円の曲率の1/3乗に比例する速度で、そのノードにおける円の接線に対し垂直方向に移動すれば、多角形は縮んで小さな楕円に収束するという性質を用いる。そして、ネットワーク内の各ノードを、次の（ア）〜（オ）のように動作させる。
【００１９】
（ア）ネットワークの外周に位置するセンサノード（以下、「外周ノード」と記す。）がそれぞれ、自律分散的に、自ノードiと自ノードiを挟んでエリアが隣接する２つの外周ノードi-1,i+1とを通る円Ci1の曲率Ki1、及び、当該円の法線単位ベクトルNi1を算出する。そして、下記の式（１）に従い、法線単位ベクトルNi1に沿って曲率Ki1の１／３乗に比例する距離だけ進んだ位置を、１回目の計算によるフロー位置Fi1として算出する。
【００２０】
【数１】
2011024090.tif 000003
【００２１】
ここで、上記の式（１）を用いた計算の回数を、フロー位置の計算回数と呼ぶ。式（１）において、「ｔ」はフロー位置の計算回数、「ｐ」は計算を行うセンサノードの位置、「ｘ」は同じ計算回数tのフロー位置同士を結んで出来る多角形、「Ｋ」は３つのノードの位置あるいは３つのフロー位置を通る円の曲率、「Ｎ」はその円の法線単位ベクトルを表す。上記Fi1、Ci1、Ki1、Ni1について、下付き添え字はフローの始点となるノードの識別子であり、上付き添え字はフロー位置の計算回数を表す。各外周ノードは、算出したフロー位置と計算回数とを自ノード内に記録する。
【００２２】
（イ）フロー位置の２回目以降の計算にあたっては、自ノードで算出したフロー位置と、自ノードiを挟んでエリアが隣接する２つの端末ノードiが算出したフロー位置のうち自ノードのフロー位置と計算回数が等しいものとを用いる。例えば、自ノードiの２回目の計算を行う際は、自ノードでの１回目の計算によるフロー位置Fi1と、自ノードiを挟んでエリアが隣接する２つの外周ノードi-1,i+1での１回目の計算によるフロー位置Fi-11，Fi+11とを用いる。そして、計算の都度、そのフロー位置および計算回数を記録する。
【００２３】
（ウ）また、外周ノードは、算出したフロー位置が、自ノードのエリアを越えて他のセンサノードのエリアに入った場合は、そのノードに対し、算出したフロー位置とその計算回数とを通知する。
【００２４】
（エ）上記通知を受けたノードは、それを記録し、通知されたフロー位置を始点として、上記（イ），（ウ）と同様な動作を繰り返す。
【００２５】
（オ）上記（ア）〜（エ）の動作によって、フロー位置が最終的に１つのノードのエリアに収束する。この位置がすなわち、代表ノードが全ての端末ノードから最短時間で情報収集を行うための、代表ノードの最適な位置である。また、フローの軌跡がすなわち、代表ノードに最短時間で情報収集を行うための経路となっている。
【００２６】
（カ）自ノードのエリアに代表ノードの最適な位置があるノードは、上記の最短時間の経路に沿って、ＮＷ内のいずれかに位置している代表ノードに、自身の位置情報を送信する。その情報を受信した代表ノードは、その位置に自律的に移動する。
【００２７】
（キ）その後、ネットワーク内の各ノードは、自ノードでセンシングした情報を、上記の最短時間の経路に沿って代表ノードへ送信する。
【００２８】
2.   上記1.に従ってフロー計算を進めていくと、同一の計算回数を持つフロー位置を結ぶことで形成される多角形は凸型になる。そのため、複数の隣接ノードが算出したフロー位置が自ノードのエリアに含まれる場合がある。このような場合、そのノードは、複数のフロー位置の中から最も計算回数の多いフロー位置を選択し、このフロー位置に残りのフロー位置を統合する。そして、統合されたフロー位置に関する情報を記録し、上記の選択したフロー位置から計算を再開する。複数のフロー位置を１つに統合することで、各ノードでの計算回数を抑えることができる。これにより、代表ノードの位置決定にかかる時間が短縮される。
【００２９】
上記の基本構想を実現するための構成およびその動作について説明する。図１に、本実施形態のセンサＮＷ100の構成例を示す。センサＮＷ100は、それぞれのエリア30に関するセンシングデータを生成する複数のセンサノード10と、各センサノード10からセンシングデータを収集するシンクノード20とを備える。センサノード10は、本発明に係る端末ノードに対応し、シンクノード20は代表ノードに対応するものである。図示の状態は、センシングすべき地域にセンサノード10が適宜ばら撒かれており、そのエリアの任意の場所にシンクノード20が配置されている状態である。本実施形態は、このシンクノード20の適切な配置を決定するものである。
【００３０】
センサＮＷ100において、各センサノード10は以下の要件I.〜V.を満たすよう構成される：
I.  互いのエリア30が隣り合うセンサノード10同士で情報を交換可能であること
II.  センサノード10間の隣接関係および相対位置関係（距離、方向）を認識可能であること
III.  各センサノード10が識別子を持つこと
IV.  各センサノード10が、自ノードと自ノードを挟んで隣接する２つのノードとを通る円を想定した自身のフロー位置と、そのフロー位置における前記円の法線単位ベクトルと、前記円の曲率とを計算可能であること
V.  各センサノード10が、自ノードが計算したフロー位置と、２つの隣接ノードが算出したフロー位置とを通る円の曲率、及び、その円における自ノードのフロー位置の法線単位ベクトルとを計算可能であること。
【００３１】
上記の要件を満たすために、センサノード10は、図２に示すように構成することができる。センサ部11は、センシングによるデータの取得、データの加工を担うハードウェア及びソフトウェアである。移動部12は、センサノード10を移動させるための手段であり、例えば、車輪，ベルトコンベア，可動脚などを自動制御により動作させるものである。通信部13は、上記の要件「I.」に対応する機能であり、他ノードやシンクノード20と通信を行うための機能である。
【００３２】
計算部14は、上記の要件「IV.」及び「V.」に対応する機能であり、自ノードを含む３つのセンサノード10を通る円の曲率や、その円の法線単位ベクトルを求める。また、上記式（１）を用いてフロー位置を計算する。
【００３３】
情報記憶部15は、自ノードの識別子、自ノードと隣接ノードとの間の隣接関係および相対位置に関する情報、計算部14の計算結果、各ノードのエリア30の位置情報など含む情報群を記憶する。
【００３４】
収束検知部16は、上記（オ）で述べた収束点が自ノードのエリアに入ったかどうかを検知し、入った場合はその旨をシンクノード20へ通知する機能を果たす。
【００３５】
結合リスト17は、上記の要件「II.」のための手段であり、センサノード10間の隣接関係や相対位置に関する一覧である。図３に結合リストの例を示す。列方向には、自ノードと隣接するノードまたは隣接するフロー位置の項目が設けられている。行方向には、識別子、ノード間の相対的な位置（座標）、他のセンサノード10またはそのフロー位置が自ノードのエリア30内に含まれるか否かの判別、自ノードが外周ノードか否かの判別、フローの計算回数、計算に用いる２つの隣接ノードの識別子、計算された曲率値、計算回数別のフロー位置、統合したフローの識別子や情報群などが記録される。
【００３６】
モード切替部18は、自ノードの状態をアクティブモードと非アクティブモードとの間で切り替える。アクティブモードでは、センサノード10の全ての機能をアクティブとなり、非アクティブモードでは、センシングのための機能が停止する。
【００３７】
図４に、シンクノード20の機能構成を示す。移動部21、通信部22、結合リスト23は、前述したセンサノード10の移動部12、通信部13、結合リスト17と同様のものである。ネットワーク制御部24は、各センサノード10からセンシングデータを収集するなど、シンクノード20が代表ノードとして機能するための手段である。また、ネットワーク制御部24は、いずれかのセンサノード10から後述のフロー収束点に関する通知を受けた場合に、移動部21を制御して、その通知を行ったセンサノード10の付近に移動する機能を果たす。
【００３８】
図５〜図９と、図１０〜１４のフローチャートを参照して、本実施形態の動作を説明する。各センサノード10は、自身がセンサＮＷ100の外周ノードかどうかを確認するための検査を行う（図１０：ステップS1）。このために、各ノードは、自律分散的に全方位に通信を試みる。その結果、もし全ての方向から返信があれば、自身は外周ノードではないと認識し、返信が全方位からでない場合は、自ノードが外周ノードであると認識する。そして、検査の結果を結合リスト17に記録する（ステップS2）。
【００３９】
各センサノード10は、自身が外周ノードでない場合は（ステップS3：No）、図１１のフローチャートに沿った後述の動作に移る。一方、外周ノードであるセンサノード10は、次のように動作する。
【００４０】
図５を参照し、センサＮＷ100における外周ノードの一つであるノードiの動作例を挙げる。ノードiは、情報記憶部15の情報や結合リスト17を参照して、自身の位置（i）と、自身を挟んで隣接する２つの外周ノード（i-1,i+1）の位置とを認識し、それら３点を通る円Ci0を形成できるかどうかを判別する（ステップS4）。図５に示すように、本例のノードiと２つの隣接ノードi-1,i+1とを結ぶ線は直線的である。このような場合、ノードiは、自身の現位置では上記の円Ci0を形成できないと判断し、当該円を形成し得る、自身の仮想的な位置Fi0を求める（ステップS5）。この仮想的な位置としてのフロー位置Fi0を通る円を円Ci1とする。
【００４１】
次に、ノードiは、円Ci1の曲率Ki0と、自身のフロー位置Fi0における円Ci1の法線単位ベクトルNi0とを算出する（ステップS6,S7）。このとき、仮に、ノードiの現位置により上記の円Ci0を形成可能な場合は（ステップS4：Yes）、その現位置における法線単位ベクトルを算出する。
【００４２】
ノードiは、前述の式（１）に従い、１回目の計算によるフロー位置Fi1を算出する（ステップS8）。これにより、図６に示すように、ノードiのフロー位置Fi0を始点として、この始点がフロー位置Fi1に更新される。ノードiは、フロー位置Fi1の計算結果や現時点の計算回数などを結合リスト17の該当欄に記録する（ステップS9）。
【００４３】
ノードiは、今回計算したフロー位置が、自身のエリアから外れて他ノードのエリアに入ったかどうかを判別する（ステップS10）。他ノードのエリアに入った場合は、そのノードに対し、今回計算したフロー位置とその計算回数とを通知する（ステップS11）。
【００４４】
一方、図６に示す例のように、今回計算したフロー位置Fi1がまだノードiのエリア内にある場合は、自ノードを挟む２つの隣接する外周ノード（i-1,i+1）から、今回のフロー位置Fi1と同一の計算回数（１回目）のフロー位置を取得する（ステップS12）。そして、取得した２つのフロー位置Fi-11 ,Fi+11と、自ノードiのフロー位置Fi1とを用いて、上記ステップS4〜S9に準じた処理を実行する（ステップS13）。
【００４５】
より具体的には、ノードiの２回目の計算では、図７に示すように、自ノードiの１回目の計算によるフロー位置Fi1と、隣接する外周ノードの１回目の計算によるフロー位置（Fi-11 ,Fi+11）とを通る円Ci2が想定される。そして、この円Ci2の曲率とフロー位置Fi1からの法線単位ベクトルとを用いた式（１）の計算により、２回目のフロー位置Fi2が算出される。ノードiは、算出したフロー位置Fi2が、自身のエリアを越えてノードjのエリアに入ったことを認識し、このノードjに、フロー位置Fi2に関する情報を通知する。
【００４６】
上記の図１０のフローチャートに沿った動作を、センサＮＷ100における全ての外周ノードが行う。
【００４７】
図１１のフローチャートに沿って、外周ノード以外の各センサノード10の動作を説明する。外周ノード以外のセンサノード10は、他ノードからフロー位置に関する情報を受信すると（ステップS21：Yes）、自ノードによるフロー位置計算のための始点を設定する（ステップS22）。例えば、図７に示す状態のノードjの場合、このノードjは、ノードiから受信したフロー位置Fi2の情報を用いて、計算の始点を「Fj,i2=Fi2+ Fj0」と設定する。
【００４８】
次に、センサノード10は、自身のエリアに複数のフロー位置が存在するかどうか、すなわち、始点のほかにも他ノードからのフロー位置があるかどうかを確認する（ステップS23）。フロー位置が始点のみの場合は、その始点と計算回数が等しいフロー位置を、自ノードを挟む２つの隣接ノードから取得する（ステップS24）。そして、取得した２つのフロー位置と始点とを用いて、新たなフロー位置の計算を行い、その計算結果をリストに記録する（ステップS25）。フロー位置の計算手順等は、外周ノードによる前述の手順（図１０：ステップS4-S9）に準じたものであり、説明は省略する。
【００４９】
センサノード10は、今回計算したフロー位置が他ノードのエリアに入ったことを認識した場合（ステップS26：Yes）、そのノードに対し、今回計算したフロー位置とその計算回数とを通知する（ステップS27）。なお、ここで通知する計算回数は、フローの発行元である外周ノードからの通算の計算回数である。
【００５０】
一方、自ノードのエリアに複数のフロー位置がある場合（ステップS23：Yes）、センサノード10は、隣接ノードから、その隣接ノードが算出したフロー位置に関する情報を取得する（ステップS28）。そして、計算回数が等しいフロー位置同士を結んでできる多角形の重心を算出する（ステップS29）。この重心の算出は、センサノード10の計算部14において、曲率と法線単位ベクトルを算出する過程で算出されるものであって、特に追加機能を必要としない。センサノード10は、始点を含む多角形の重心が、その始点よりも計算回数が１つ少ないフロー位置群による多角形の重心とほぼ一致するかどうかを判定する（ステップS30）。この判定にあたっては、例えば、比較対象となる重心の差が所定範囲内であれば、ほぼ一致するとみなすことができる。
【００５１】
上記判定が否の場合、センサノード10は、自身のエリアにある複数のフロー位置のうち、計算回数が最も多いものを選択する（ステップS31）。そして、選択したフロー位置に残りのフロー位置を統合し、統合した位置を始点として設定し直す（ステップS32）。センサノード10は、設定し直した始点を結合リストに記録し（ステップS33）、その始点を用いてフロー位置の計算を行う（ステップS24〜）。
【００５２】
ここで、フロー位置の統合について、図８を参照して例を挙げる。本例は、前述のノードjのエリアに、始点（Fj,i2=Fi2+ Fj0）のほかに、外周ノードi+1からの３回目の計算によるフロー位置Fi+13が入ったことを想定したものである。この場合、ノードjは、計算回数が２回である始点（Fj,i2）よりも、ノードi+1からのフロー位置（Fi+13）のほうが計算回数が多いと判断し、始点をフロー位置Fi+13に統合する。これにより、ノードjの始点は、「Fj,i+1,i3=Fi+13+Fi2+Fj0」に改められる。
【００５３】
センサノード10は、重心に関する判定において、比較対象がほぼ一致すると判断した場合（ステップS30：Yes）、自ノードのエリアにフロー収束点があると認識する（ステップS34）。収束点を検知したセンサノード10は、後述のステップS41からの動作へ移行する。
【００５４】
図９に、センサＮＷ100における収束点を概念的に示す。図示の状況は、センサＮＷ100の各シンクノード20が上記の手順にて動作することにより、複数のノードからのフロー40,41,42,43が、最終的に１つのノードzのエリア内に収束した様子を示すものである。ノードzは、収束点Soが自ノードのエリアに入ったことを認識する。この収束点Soが、代表ノードとしてのシンクノード20の配置に最適な場所である。また、フローの軌跡がすなわち、代表ノードが最短時間で情報収集を行うための経路となっている。
【００５５】
経路に関し、各センサノード10は、各自で経路表を持つ。各センサノード10は、自ノードで計算したフロー位置に関する情報を他ノードへ通知するとき、そのフロー位置に自ノードの識別子を関連付けて通知する。また、他ノードからフロー位置の情報を受信したときは、その情報から、当該フローに関与した各ノードの識別子を抽出して経路表に記録する。これにより、最短経路木が形成される。
【００５６】
図１２のフローチャートを参照して、収束点を検出したセンサノード10の動作を説明する。センサノード10は、自身のエリア内に収束点があると認識した場合、このエリアへの移動を指示するための情報（移動情報）を作成する。そして、作成した移動情報を、最短経路木の下り方向にブロードキャストでシンクノード20宛てに送信する（ステップS41）。この移動情報には、当該センサノード10の識別子や位置情報等が含まれる。移動情報を発行したセンサノード10は、シンクノード20から応答を受信した後（ステップS42）、自ノードのエリアに移動してきたシンクノード20からの命令に従い、自身をアクティブモードから非アクティブモードに切り替える（ステップS43）。
【００５７】
図１３のフローチャートを参照して、移動情報とその応答の転送に関し、収束点を検出したセンサノード10以外のセンサノード10の動作を説明する。センサノード10は、他ノードから信号を受信すると（ステップS51）、信号の種別に応じて、その信号を最短経路木の上り方向または下り方向へ転送する。
【００５８】
具体的には、受信信号が移動情報の場合（ステップS52：「移動情報」）、センサノード10は、その移動情報に自ノードの識別子を付加して最短経路木の下り方向にブロードキャストで送信する（ステップS53）。移動情報は、シンクノード20に到着するまで順次転送される。また、受信信号がシンクノード20からの応答である場合（ステップS52：「応答」）、センサノード10は、その応答を最短経路木の上り方向に送信する（ステップS54）。シンクノード20からの応答は、収束点を検出したセンサノード10に到着するまで順次転送される。
【００５９】
図１４のフローチャートを参照して、シンクノード20の動作を説明する。シンクノード20は、収束点を検出したセンサノード10からの移動情報を受信すると（ステップS61）、応答を最短経路木の上り方向に送信する（ステップS62）。応答後、シンクノード20は、移動情報に付加されていた各センサノード10の識別子を参照しながら、収束点があるエリアを目指して最短経路木の上り方向に順次移動する（ステップS63）。そして、目的のエリアに到着すると（ステップS64：Yes）、シンクノード20は、そのエリアのセンサノード10に対し、動作を非アクティブモードに切り替えるよう指示する（ステップS65）。
【００６０】
以上説明したように、本実施形態によれば、センサＮＷ100においてシンクノード20を情報収集のための最適な場所に配置することができる。
【００６１】
また、完全に自律分散的かつ自己組織的に通信最短時間という意味で最適なシンクノード20の位置を決定可能である。その理由は、２次元平面内の任意の多角形は、式（１）とフロー統合に従ってフロー計算を重ねていけば、最終的には１つの（正しくは１点と見なすことの出来る円または楕円）に収束するためである。
【００６２】
さらにまた、シンクノード20をルートとし、ＮＷ内の全てのアクティブなノードをつなぐ最短経路木（スパニングツリー）を構築することができる。各センサノード10は、その経路に従って情報をシンクノード20に送ることで、情報を最短時間で送ることができる。このような最短経路木をシンクノード20の配置と同時的に決定することができる。
【００６３】
また、本実施形態は、完全に自律分散的な手法であるため、ノードの数やＮＷのサイズに対してスケーラブルである。またフロー統合を行うことで、フロー統合を行わない場合に比べて、シンクノードの位置決定および最短経路決定の収束時間がＮＷ内のノード数をｎとした場合のlog(n)/nのオーダーで短くなるため、さらにスケーラビリティが高まる。これは、式（１）を利用すると共に、フロー位置を仮想的なノード位置として扱い、さらにフロー統合を行うことで実現されると共に、低消費電力が実現される。
【００６４】
本発明の実施は、上記形態に限定されるものではなく、特許請求の範囲内で適宜変更が可能である。例えば、図１〜図９において、センサノード10およびシンクノード20のエリア30は、それぞれ正方形であり、かつ全て同様な形状及び大きさであるが、目的とする領域を覆うことができれば、図示の形状に替えて、円または楕円あるいは任意の多角形でも良い。
【００６５】
フロー位置の計算に用いる曲率（K）の指数（α）は、式（１）のような「1/3」に限らず、「０＜α＜１」の範囲にあり、かつ全フローを１点（正確には十分小さな円または楕円）に収束可能な値であれば、任意の値を使用することができる。
【００６６】
外周ノード以外のセンサノード10による始点の設定（ステップS22）に関し、上記実施形態では、他ノードから通知されたフロー位置を始点として用いたが、この通知されたフロー位置が自ノードの位置と所定距離d以内にある場合に、そのフロー位置を始点として設定するようにしてもよい。より具体的には、例えば図７において、ノードjが、自身の位置と、外周ノードiから通知されたフロー位置Fi2との差が距離d以内であれば、図示のように「Fj,i2=Fi2+ Fj0」を始点として設定するという制御である。
【００６７】
上記実施形態のセンサノード10およびシンクノード20は、ハードウェアによって実現するほかに、コンピュータをセンサノード10又はシンクノード20として機能させるためのプログラムを当該コンピュータが記録媒体から読み出して実行することによっても実現することができる。
【産業上の利用可能性】
【００６８】
本発明は、モバイルバックホールを含む無線ＮＷおよびセンサＮＷ、並びに、これらの発展形態に好適である。例えば、バイルバックホールの簡易基地局が移動可能あるいは容易に移設可能なネットワーク。また、無線ＮＷやセンサＮＷにおいて、各ノードが代表ノードと同じまたは同等の機能を有するネットワーク。さらに、本発明を、通信ＮＷなどにおけるオーバーレイＮＷや仮想化技術に応用すれば、必要な機能や情報を物理的あるいは仮想的に、最適な位置に移動させることができる。
【符号の説明】
【００６９】
100  センサＮＷ
10  センサノード（端末ノード）
20  シンクノード（代表ノード）
30  エリア
11  センサ部
12,21  移動部
13,22  通信部
14  計算部
15  情報記憶部
16  収束検知部
17,23   結合リスト
18  モード切替部
24  ネットワーク制御部
【図１】
2011024090.tif 000007
【図２】
2011024090.tif 000008
【図３】
2011024090.tif 000009
【図４】
2011024090.tif 000010
【図５】
2011024090.tif 000011
【図６】
2011024090.tif 000012
【図７】
2011024090.tif 000013
【図８】
2011024090.tif 000014
【図９】
2011024090.tif 000015
【図１０】
2011024090.tif 000016
【図１１】
2011024090.tif 000017
【図１２】
2011024090.tif 000018
【図１３】
2011024090.tif 000019
【図１４】
2011024090.tif 000020