(57)【要約】【課題】ノードの相対的な位置関係に対応し、凸包形状の領域を特定するグラフ情報をノード装置が生成する方法及び当該ノード装置を提供する。【解決手段】本発明に係る方法では、各ノード装置において、自装置を基準とした所定の範囲内の座標に対応する複数のノード装置を含むグループを、１つ以上探索して保存する。また、本方法では、各ノード装置が探索したグループに基づき、起点ノード装置に関連するＸＹ座標平面であり、当該起点ノード装置を起点として生成されるグリッド・グラフに含まれるグリッド・ノード装置を決定する。その際、Ｘ軸及びＹ軸上の座標以外の座標に対応する各ノードは、探索したグループに含まれる１ホップ・ノードのうち、上流側のノードの両方が、グリッド・グラフのノードとして決定された後に、自装置をグリッド・グラフの座標に決定していく。【選択図】図１
2015070544.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード装置を含み、各ノード装置は別のノード装置と無線により通信するシステムにおいて、ノード装置の相対的な位置関係に対応するグラフ情報を生成する方法であって、
各ノード装置が自装置を広告することで、自装置と直接通信できる別のノード装置を識別し、各ノード装置が前記識別した直接通信できる別のノード装置を示す情報を広告することで、各ノード装置において、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成ステップと、
各ノード装置において、前記トポロジ情報に基づき、自装置を基準とした所定の範囲内の座標に対応する複数のノード装置を含むグループであって、Ｘ軸及びＹ軸の各軸方向において隣接する座標に対応するノード装置とは双方向で直接通信でき、各軸方向において隣接する座標以外の座標に対応するノード装置とは直接通信できないグループを、１つ以上探索して保存する探索ステップと、
各ノード装置が探索したグループに基づき、起点ノード装置に関連するＸＹ座標平面であり、当該起点ノード装置を起点として生成されるグリッド・グラフに含まれるノード装置であるグリッド・ノード装置を決定する決定ステップであって、当該起点ノード装置を含む当該グリッド・ノード装置は、当該グリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応し、各グリッド・ノード装置は、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置、及びＹ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できない、決定ステップと、を含み、
前記決定ステップにおいて、
前記起点ノード装置を起点として、各ノード装置は、探索したグループに基づき、自装置が前記グリッド・ノード装置であるかを判定し、当該判定の結果に従って、自装置を前記グリッド・ノード装置に決定したこと及び前記グリッド・グラフの座標を広告し、
Ｘ軸及びＹ軸上の座標以外の座標に対応する各ノード装置は、探索したグループに含まれる、自装置と直接通信できる１ホップ・ノード装置のうち、Ｘ軸及びＹ軸方向において前記起点ノード装置にそれぞれ１ホップ近い２つのノード装置の両方が前記グリッド・ノード装置に決定された後に、自装置を前記グリッド・グラフの座標に決定する、
ことを特徴とする方法。
【請求項２】
各ノード装置において、自装置を前記グリッド・ノード装置に決定すると、前記グリッド・グラフに関連する起点ノード装置の識別情報を保存する第１保存ステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
各ノード装置は、複数のグリッド・グラフに対応した複数の起点ノード装置の識別情報を保存するためのリストを有し、
前記第１保存ステップにおいて、各ノード装置は、自装置を新たなグリッド・グラフにおける前記グリッド・ノード装置に決定するごとに、当該グリッド・グラフに関連する起点ノード装置の識別情報を前記リストに追加して保存する、
ことを特徴とする請求項２に記載の方法。
【請求項４】
グリッド・ノード装置以外のノード装置において、グリッド・グラフを示すグラフ情報を、グリッド・ノード装置である他のノード装置から受信すると、当該グリッド・グラフに関連する起点ノード装置の識別情報を保存する第２保存ステップをさらに含むことを特徴とする請求項２又は３に記載の方法。
【請求項５】
各ノード装置において、自装置の位置を推定する際に、自装置に保存した識別情報が示す起点ノード装置を利用するステップをさらに含むことを特徴とする請求項２乃至４のいずれか１項に記載の方法。
【請求項６】
前記探索ステップにおいて、各ノード装置は、前記トポロジ情報に基づき、
自装置を座標（０，０）とし、座標（０，０）、（１，０）、（０，１）、（−１，０）、（０，−１）、（１，１）、（１，−１）、（−１，１）及び（−１，−１）に対応する９つのノード装置を含むグループを、１つ以上探索して保存することを特徴とする請求項１乃至５のいずれか１項に記載の方法。
【請求項７】
前記探索ステップにおいて、各ノード装置は、探索したグループに含まれる、自装置と直接通信できる１ホップ・ノード装置のそれぞれについて、探索したグループに含まれる回数を示すノード値を含む第１情報を広告し、探索したグループのスコアを、別のノード装置が広告する前記第１情報に基づき求め、
前記決定ステップにおいて、前記グリッド・グラフに関連する起点ノード装置は、探索したグループのうち、スコアの最も高いグループに含まれる１ホップ・ノード装置のそれぞれを、当該起点ノード装置と当該１ホップ・ノード装置それぞれの位置関係に従い、当該起点ノード装置に対してＸ軸及びＹ軸方向で隣接する座標に対応するノード装置に決定し、決定したノード装置に決定した座標を通知し、
前記ノード装置が探索したグループのスコアは、別のノード装置が広告する前記第１情報に含まれている、当該グループの１ホップ・ノード装置のノード値の合計が大きい程、高くなることを特徴とする請求項１乃至６のいずれか１項に記載の方法。
【請求項８】
前記決定ステップにおいて、前記グリッド・グラフの座標に決定したノード装置は、前記探索したグループの中に、既に前記グリッド・グラフの座標に決定したノード装置に従う配置が可能な１つ以上のグループが存在するかを判定し、存在する場合、判定したグループのそれぞれについて、判定したグループの１ホップ・ノード装置それぞれの座標と、当該判定したグループのスコアとを示すグラフ情報を広告し、
ｍ及びｎを１以上の整数とし、前記グリッド・グラフに関連する起点ノード装置の座標を座標（０，０）とすると、
座標（ｍ，ｎ−１）に決定したノード装置及び座標（ｍ−１，ｎ）に決定したノード装置が広告するグラフ情報の両方において、座標（ｍ，ｎ）の装置と示されたノード装置のうち、両グラフ情報に含まれる当該ノード装置を含むグループのスコアの合計が最も高いノード装置は、自装置が座標（ｍ，ｎ）に決定したことを広告し、
座標（ｍ，−ｎ＋１）に決定したノード装置及び座標（ｍ−１，−ｎ）に決定したノード装置が広告するグラフ情報の両方において、座標（ｍ，−ｎ）の装置と示されたノード装置のうち、両グラフ情報に含まれる当該ノード装置を含むグループのスコアの合計が最も高いノード装置は、自装置が座標（ｍ，−ｎ）に決定したことを広告し、
座標（−ｍ，ｎ−１）に決定したノード装置及び座標（−ｍ＋１，ｎ）に決定したノード装置が広告するグラフ情報の両方において、座標（−ｍ，ｎ）の装置と示されたノード装置のうち、両グラフ情報に含まれる当該ノード装置を含むグループのスコアの合計が最も高いノード装置は、自装置が座標（−ｍ，ｎ）に決定したことを広告し、
座標（−ｍ，−ｎ＋１）に決定したノード装置及び座標（−ｍ＋１，−ｎ）に決定したノード装置が広告するグラフ情報の両方において、座標（−ｍ，−ｎ）の装置と示されたノード装置のうち、両グラフ情報に含まれる当該ノード装置を含むグループのスコアの合計が最も高いノード装置は、自装置が座標（−ｍ，−ｎ）に決定したことを広告する、
ことを特徴とする請求項７に記載の方法。
【請求項９】
前記決定ステップにおいて、
ｓを０以外の整数とし、ｔを１又は−１とし、ｕを１又は−１とし、ｋをｓが正の場合には＋１であり、ｓが負の場合には−１とし、前記グリッド・グラフに関連する起点ノード装置の座標を座標（０，０）とすると、
前記グリッド・グラフのＸ軸上の座標（ｓ，０）に決定したノード装置は、前記グラフ情報に、座標（ｓ，ｔ）と座標（ｓ，−ｔ）のうち、先に決定する座標である座標（ｓ，ｔ）を示す情報を含めて広告し、
座標（ｓ，ｔ）に決定したノード装置から、座標（ｓ，ｔ）に決定したことを示す広告を受信すると、前記座標（ｓ，０）に決定したノード装置は、前記探索したグループの中に、既に前記グリッド・グラフの座標に決定したノード装置の配置に従い、かつ、座標（ｓ，−ｔ）に対応するノード装置を含む１つ以上のグループが存在するかを判定し、存在する場合、判定したグループのそれぞれについて、判定したグループの１ホップ・ノード装置それぞれの座標と、当該判定したグループのスコアを示すグラフ情報と、座標（ｓ，−ｔ）を決定することを示す情報を含むグリッド・グラフ情報を広告し、存在しない場合及び座標（ｓ，−ｔ）に決定したノード装置から、座標（ｓ，−ｔ）に決定したことを示す広告を受信した場合、前記探索したグループの中に、既に前記グリッド・グラフの座標に決定したノード装置の配置に従い、かつ、座標（ｓ＋ｋ，０）に対応するノード装置を含む１つ以上のグループが存在するかを判定し、存在する場合、判定したグループから１つを選択して座標（ｓ＋ｋ，０）のノード装置を決定し、決定したノード装置に座標（ｓ＋ｋ，０）に決定したことを通知し、
前記グリッド・グラフのＹ軸上の座標（０，ｓ）に決定したノード装置は、前記グラフ情報に、座標（ｕ，ｓ）と座標（−ｕ，ｓ）のうち、先に決定する座標である座標（ｕ，ｓ）を示す情報を含めて広告し、
座標（ｕ，ｓ）に決定したノード装置から、座標（ｕ，ｓ）に決定したことを示す広告を受信すると、前記座標（０，ｓ）に決定したノード装置は、前記探索したグループの中に、既に前記グリッド・グラフの座標に決定したノード装置の配置に従い、かつ、座標（−ｕ，ｓ）に対応するノード装置を含む１つ以上のグループが存在するかを判定し、存在する場合、判定したグループのそれぞれについて、判定したグループの１ホップ・ノード装置それぞれの座標と、当該判定したグループのスコアを示すグラフ情報と、座標（−ｕ，ｓ）を決定することを示す情報を含むグリッド・グラフ情報を広告し、存在しない場合及び座標（−ｕ，ｓ）に決定したノード装置から、座標（−ｕ，ｓ）に決定したことを示す広告を受信した場合、前記探索したグループの中に、既に前記グリッド・グラフの座標に決定したノード装置の配置に従い、かつ、座標（０，ｓ＋ｋ）に対応するノード装置を含む１つ以上のグループが存在するかを判定し、存在する場合、判定したグループから１つを選択して座標（０，ｓ＋ｋ）のノード装置を決定し、決定したノード装置に座標（０，ｓ＋ｋ）に決定したことを通知する、
ことを特徴とする請求項７に記載の方法。
【請求項１０】
複数のノード装置を含み、各ノード装置は別のノード装置と無線により通信するシステムで使用するノード装置であって、
自装置の存在を広告し、別のノード装置から広告を受信することで、自装置と直接通信できる別のノード装置を識別する識別手段と、
前記識別した直接通信できる別のノード装置を示す隣接情報を広告し、別のノード装置が広告する前記隣接情報を受信することで、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成手段と、
前記トポロジ情報に基づき、自装置を基準とした所定の範囲内の座標に対応する複数のノード装置を含むグループであって、Ｘ軸及びＹ軸の各軸方向において隣接する座標に対応するノード装置とは双方向で直接通信でき、各軸方向において隣接する座標以外の座標に対応するノード装置とは直接通信できないグループを、１つ以上探索して保存する探索する探索手段と、
探索したグループに基づき、自装置が、起点ノード装置に関連するＸＹ座標平面であり、当該起点ノード装置を起点として生成されるグリッド・グラフに含まれるノード装置であるグリッド・ノード装置であるかを判定する判定手段であって、当該起点ノード装置を含む当該グリッド・ノード装置は、当該グリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応し、各グリッド・ノード装置は、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置、及びＹ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できない、判定手段と、を備え、
前記判定手段は、
探索したグループに基づき、自装置が前記グリッド・ノード装置であるかを判定し、当該判定の結果に従って、自装置を前記グリッド・ノード装置に決定したこと及び前記グリッド・グラフの座標を広告し、
自装置がＸ軸及びＹ軸上の座標以外の座標に対応する場合、探索したグループに含まれる、自装置と直接通信できる１ホップ・ノード装置のうち、Ｘ軸及びＹ軸方向において前記起点ノード装置にそれぞれ１ホップ近い２つのノード装置の両方が前記グリッド・ノード装置に決定された後に、自装置を前記グリッド・グラフの座標に決定する、
ことを特徴とするノード装置。
【請求項１１】
自装置を前記グリッド・ノード装置に決定すると、前記グリッド・グラフに関連する起点ノード装置の識別情報を保存する保存手段を更に備えることを特徴とすることを特徴とする請求項１０に記載のノード装置。
【請求項１２】
複数のグリッド・グラフに対応した複数の起点ノード装置の識別情報を保存するためのリストを更に備え、
前記保存手段は、自装置を新たなグリッド・グラフにおける前記グリッド・ノード装置に決定するごとに、当該グリッド・グラフに関連する起点ノード装置の識別情報を前記リストに追加して保存する、
ことを特徴とする請求項１１に記載のノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノードの相対的な位置関係に対応するグラフ情報をノードが生成する技術に関する。
【背景技術】
【０００２】
ある地理的領域に、多数のセンサ機能を有するノード装置（以下、単にノードと呼ぶ。）を設置し、ノードが測定する、例えば、温度や湿度等のセンサ情報を、ノードの設置位置に対応づけて取得するセンサ・ネットワークを考える。なおノードの数は非常に多いため、測定者がＧＰＳ受信機等を用いて総てのノードの設置位置を測定して各ノードに設定することを避けたいものとする。
【０００３】
この場合、例えば、ノードを設置する領域が屋外のみであれば、ＧＰＳ等を利用した位置情報の取得機能を各ノードに設けることで、各ノードは、位置情報を容易に取得することができる。しかしながら、各ノードに位置情報の取得機能を実装する必要がありコストが高くなる。また、ノードの一部を屋内に設置しなければならない場合、屋内に設置するノードは、位置情報が取得できないという問題が生じる。
【０００４】
このため、アンカ・ノード又はランドマーク・ノードと呼ばれる一部のノードに位置情報の取得機能を設ける、或いは、測定者が測定した位置情報を設定し、他のノードは、近傍のノードとの接続関係、つまり、トポロジ情報を用いて自装置の位置を推定する手法が提案されている。なお、これら手法は大きく、レンジ・ベース（Range-Based）な手法とレンジ・フリー（Range-Free）な手法の２つに分けられる。レンジ・ベースな手法は、ノードが他のノードとの物理的距離を測定することを含む手法である。これに対して、レンジ・フリーな手法は、他のノードとの物理的距離を測定せず、トポロジ情報のみから位置を推定する手法であり、ノードの構成を簡略化できるという利点がある。例えば、レンジ・フリーな手法であり、かつ、位置推定誤差が比較的少ない手法として、非特許文献１〜３には、多辺測量の技術をベースとした方式が提案されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】H.Chen, et al.,“An Improved DV-Hop Localization Algorithm for Wireless Sensor Networks,”In Proc. of IEEE International Conference on Information Acquisition, pp.638-643, 2006.
【非特許文献２】R.Nagpal, et al.,“Organizing a Global Coordinate System from Local Information on an Ad Hoc Sensor Network,”In Proc. of ACM IPSN, 2003.
【非特許文献３】D. Niculescu, et al.,“Ad Hoc Positioning System(APS),”In Proc. of IEEE GLOBECOM 2001, pp.2926-2931, 2001.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１〜３に記載の手法は、ノードが設置されている領域が非凸包形状である場合、位置推定誤差が非常に大きくなるという問題がある。なお非凸包形状とは、領域内の任意の２点を直線で結ぶときに、直線の一部が領域外にはみ出ることがある形状である。上記のような多辺測量ベースの位置推定技術では、各ノードは、自ノードからアンカ・ノードまでのホップ数を利用して、アンカ・ノードまでの距離を推定する。このため、ノードが設置されている領域が非凸包形状である場合、当該ノードからアンカ・ノードまでの経路が、実際の物理的な直線経路と大きくかけ離れた迂回経路となりうる。これにより、ノードからアンカ・ノードまでのホップ数が実際の物理的距離を反映しなくなり、位置推定誤差が大きくなりうる。
【０００７】
本発明は、上述した問題の少なくとも１つを解決する、ノードの相対的な位置関係に対応し、凸包形状の領域を特定するグラフ情報をノード装置が生成する方法及び当該ノード装置を提供するものである。
【課題を解決するための手段】
【０００８】
本発明の一態様によると、複数のノード装置を含み、各ノード装置は別のノード装置と無線により通信するシステムにおいて、ノード装置の相対的な位置関係に対応するグラフ情報を生成する方法であって、各ノード装置が自装置を広告することで、自装置と直接通信できる別のノード装置を識別し、各ノード装置が前記識別した直接通信できる別のノード装置を示す情報を広告することで、各ノード装置において、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成ステップと、各ノード装置において、前記トポロジ情報に基づき、自装置を基準とした所定の範囲内の座標に対応する複数のノード装置を含むグループであって、Ｘ軸及びＹ軸の各軸方向において隣接する座標に対応するノード装置とは双方向で直接通信でき、各軸方向において隣接する座標以外の座標に対応するノード装置とは直接通信できないグループを、１つ以上探索して保存する探索ステップと、各ノード装置が探索したグループに基づき、起点ノード装置に関連するＸＹ座標平面であり、当該起点ノード装置を起点として生成されるグリッド・グラフに含まれるノード装置であるグリッド・ノード装置を決定する決定ステップであって、当該起点ノード装置を含む当該グリッド・ノード装置は、当該グリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応し、各グリッド・ノード装置は、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置、及びＹ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できない、決定ステップと、を含み、前記決定ステップにおいて、前記起点ノード装置を起点として、各ノード装置は、探索したグループに基づき、自装置が前記グリッド・ノード装置であるかを判定し、当該判定の結果に従って、自装置を前記グリッド・ノード装置に決定したこと及び前記グリッド・グラフの座標を広告し、Ｘ軸及びＹ軸上の座標以外の座標に対応する各ノード装置は、探索したグループに含まれる、自装置と直接通信できる１ホップ・ノード装置のうち、Ｘ軸及びＹ軸方向において前記起点ノード装置にそれぞれ１ホップ近い２つのノード装置の両方が前記グリッド・ノード装置に決定された後に、自装置を前記グリッド・グラフの座標に決定する、ことを特徴とする。
【０００９】
本発明の一態様によると、複数のノード装置を含み、各ノード装置は別のノード装置と無線により通信するシステムで使用するノード装置であって、自装置の存在を広告し、別のノード装置から広告を受信することで、自装置と直接通信できる別のノード装置を識別する識別手段と、前記識別した直接通信できる別のノード装置を示す隣接情報を広告し、別のノード装置が広告する前記隣接情報を受信することで、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成手段と、前記トポロジ情報に基づき、自装置を基準とした所定の範囲内の座標に対応する複数のノード装置を含むグループであって、Ｘ軸及びＹ軸の各軸方向において隣接する座標に対応するノード装置とは双方向で直接通信でき、各軸方向において隣接する座標以外の座標に対応するノード装置とは直接通信できないグループを、１つ以上探索して保存する探索する探索手段と、探索したグループに基づき、自装置が、起点ノード装置に関連するＸＹ座標平面であり、当該起点ノード装置を起点として生成されるグリッド・グラフに含まれるノード装置であるグリッド・ノード装置であるかを判定する判定手段であって、当該起点ノード装置を含む当該グリッド・ノード装置は、当該グリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応し、各グリッド・ノード装置は、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置、及びＹ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できない、判定手段と、を備え、前記判定手段は、探索したグループに基づき、自装置が前記グリッド・ノード装置であるかを判定し、当該判定の結果に従って、自装置を前記グリッド・ノード装置に決定したこと及び前記グリッド・グラフの座標を広告し、自装置がＸ軸及びＹ軸上の座標以外の座標に対応する場合、探索したグループに含まれる、自装置と直接通信できる１ホップ・ノード装置のうち、Ｘ軸及びＹ軸方向において前記起点ノード装置にそれぞれ１ホップ近い２つのノード装置の両方が前記グリッド・ノード装置に決定された後に、自装置を前記グリッド・グラフの座標に決定する、ことを特徴とする。
【発明の効果】
【００１０】
本発明によれば、複数のノードを含み、各ノードは別のノードと無線により通信するシステムにおいて、ノードの相対的な位置関係に対応し、凸包形状の領域を特定するグラフ情報をノード装置が生成できる。これにより、生成したグラフ情報を多辺測量ベースの位置推定技術に適用した場合に、位置推定誤差を低減し、精度良くノードの設置位置を推定することが可能になる。
【図面の簡単な説明】
【００１１】
【図１】一実施形態によるシステム構成及びグリッド・グラフを示す図。
【図２】トポロジ情報の説明図。
【図３】ユニット・グリッドを示す図。
【図４】ユニット・グリッドの説明図。
【図５】ユニット・スコアの説明図。
【図６】一実施形態によるグリッド・グラフの座標に対応するノードの決定の説明図。
【図７】一実施形態によるグリッド・グラフの座標に対応するノードの決定の説明図。
【図８】一実施形態によるグリッド・グラフの座標に対応するノードの決定の説明図。
【図９】一実施形態においてグリッド・グラフの座標に決定したノード装置が広告するグリッド・グラフ情報を示す図。
【図１０】一実施形態においてグリッド・グラフの座標に決定したノード装置が広告するグリッド・グラフ情報を示す図。
【図１１】一実施形態においてグリッド・グラフの座標に決定したノード装置が広告するグリッド・グラフ情報を示す図。
【発明を実施するための形態】
【００１２】
以下、本発明の例示的な実施形態について図面を参照して説明する。なお、以下の各図において、実施形態の説明に必要ではない構成要素については図から省略する。
【００１３】
まず、本発明の概略について説明する。なお、以下の説明において、自装置の設置位置の位置情報、例えば、緯度及び経度を保持しているノードをアンカ・ノードと呼ぶ。位置情報は、アンカ・ノードがＧＰＳ等を利用して取得したものであっても、測定者がアンカ・ノードに設定したものであってもよい。ただし、上述のような多辺測量ベースの位置推定技術による位置推定に本発明によって得られるグラフ情報を用いるためには、アンカ・ノードは必ずしも自装置の位置情報を保持している必要はない。
【００１４】
図１（Ａ）は、複数のノード（ノード装置）を含み、各ノードが別のノードと無線により通信するシステムの一例を示しており、設置されているノードＡ〜Ｚと、点線で示すノード間の無線リンクを示している。つまり、点線で結ばれている２つのノードは、無線により直接通信できることを示している。なお、図１（Ａ）は簡略化のため２６個のノードのみを示しているが、実際には各ノードが数十程度の隣接ノード、つまり、直接通信できるノードを有している。各ノードは周期的に自装置が持つ情報を無線信号でブロードキャスト、つまり広告し、また他のノードがブロードキャスト、つまり、広告する情報を受信することで、１ホップで通信できるノード、つまり、隣接ノードと、２ホップで通信できるノード、つまり隣接ノードの隣接ノードを認識する。なお、本実施形態において、各ノード装置の通信可能距離、つまり、無線信号の最大到達距離に大きな違いはなく、受信機の能力にも大きな違いはないものとする。
【００１５】
その状態において、１つのアンカ・ノードを基準又は起点として、図１（Ｂ）において実線で結ばれたノードの様に、所定の条件を満たすノードを選択する。図１（Ｂ）は、多数のノードが設置されたシステムにおいて、ノードＺをアンカ・ノードとして設定し、ノードＺを基準として選択した所定の条件を満たすノードの集合（ノードＡ〜Ｘ）を、模式的に示している。以下では、このようなノードの集合を“グリッド・グラフ”と呼ぶものとする。また、グリッド・グラフの基準となるノード、つまり、グリッド・グラフ形成のトリガとなったノードがノードＺである場合、そのグリッド・グラフを“グラフＺ”と呼ぶものとする。さらに、以下の説明では、グリッド・グラフに含まれているノードを“グリッド・ノード”と呼び、それ以外のノードを“非グリッド・ノード”と呼ぶものとする。
【００１６】
グリッド・グラフは、ＸＹ座標平面に対応させられ、各グリッド・ノードは座標（ｘ，ｙ）、ここで、ｘ及びｙは整数、に対応させられる。以下の説明において、グリッド・グラフの基準となるアンカ・ノード（起点ノード装置）は、当該グリッド・グラフの原点に対応するノードであるものとする。これは説明を簡単にするためであり、グリッド・グラフの基準となるアンカ・ノードの座標は原点以外とすることもできる。例えば、図１（Ｂ）のノードＺを基準とするグラフＺにおいて、横方向をＸ軸方向として、上方向をＹ軸方向とすると、ノードＺは（０，０）の座標、ノードＧは（１，０）の座標、ノードＡは（０，１）の座標、ノードＥは（０，−１）の座標、ノードＣは（−１，０）の座標にそれぞれ対応する。
【００１７】
本実施形態において、グリッド・ノードとなる条件は、Ｘ軸方向で隣接する座標に対応するノード装置が存在するのであれば、このＸ軸方向で隣接する座標のノード装置とは双方向リンクを有し、Ｙ軸方向で隣接する座標に対応するノード装置が存在するのであれば、このＹ軸方向で隣接する座標のノード装置とは双方向リンクを有し、Ｘ軸方向でもＹ軸方向でも隣接しない座標に対応する他のノード装置とはリンクを有さないことである。この条件により、各座標に対応するグリッド・ノード装置の実際の位置は、概ね座標に沿った配置とすることができる。
【００１８】
上述のグリッド・グラフは、ノードの相対的な位置関係に対応する。グリッド・グラフから得られる、各ノードからアンカ・ノードまでのホップ数を、多辺測量ベースの位置推定に利用することが可能である。このような位置推定における推定誤差を抑えるためには、グリッド・グラフに対応する領域が凸包領域となるように、グリッド・グラフを生成する必要がある。ただし、センサ・ネットワーク全体が凸包領域である必要はない。
【００１９】
本実施形態では、図１（Ａ）及び（Ｂ）に示すようなシステムにおいて、システム内のノードが互いに連携して、凸包領域に対応したグリッド・グラフを生成する。各ノードは、上述のように、互いに無線信号で広告する情報に基づいて、１ホップで通信できるノードである１ホップ・ノードと、２ホップで通信できるノードである２ホップ・ノードとを認識する。その認識結果に基づき、各ノードは、自装置を基準とした所定の範囲内の座標に対応する複数のノードを含むグループである部分グラフ（後述する“ユニット・グリッド”）を探索する。さらに、各ノードは、探索したグループに基づき、自装置をグリッド・グラフに組み込んで（即ち、グリッド・グラフに含まれるノードとして決定し）、その結果を隣接するノードに広告する。このようにして、各ノードは、探索した１つ以上の部分グラフを組み合わせて、最終的にグリッド・グラフを生成する。
【００２０】
グリッド・グラフの生成過程では、図１（Ｂ）に示すように、アンカ・ノードを起点として、各ノードに対する１ホップ・ノードが順にグリッド・グラフに組み込まれていくことで、グリッド・グラフが拡張する方向に徐々に成長する。その際、グリッド・グラフの一部が特定の方向に大幅に拡張していくと、結果として非凸包領域に対応したグリッド・グラフが生成されるおそれがある。そこで、本実施形態では、グリッド・グラフの生成過程において、このような偏った拡張を防ぐため、グリッド・グラフの全体が同程度の割合で拡張していくような処理を行う。
【００２１】
具体的には、Ｘ軸及びＹ軸上の座標以外の座標に対応する各ノードは、探索したグループに含まれる、自装置と直接通信できる１ホップ・ノードのうち、Ｘ軸及びＹ軸方向においてアンカ・ノードにそれぞれ１ホップ近い２つのノードの両方が、グリッド・グラフのノードとして決定された後に、自装置をグリッド・グラフの座標に決定していく。このような処理は、特に、各ノードが探索するグループに対応する座標の範囲を、後述する図３（Ａ）に示すような、Ｘ軸及びＹ軸のいずれの方向においても対称的な格子状の部分グラフに対応させることによって実現できる。このような対称的な部分グラフを各ノードが探索することによって、各ノードがあらゆる方向に対して均等にノードの探索を行うことになるため、グリッド・グラフが偏った拡張をすることを防止できる。
【００２２】
また、本実施形態では、各ノードは、自装置をグリッド・グラフに組み込んだことに応じて、当該グリッド・グラフのアンカ・ノードの識別情報（ＩＤ）を保存する。各ノードと、保存した識別情報に対応するアンカ・ノードとは、同一の凸包領域に含まれている。このため、各ノードは、保存した識別情報に対応するアンカ・ノードに接続するまでのホップ数に基づいて、自装置の位置を推定してもよい。本実施形態では、このような位置推定における位置推定誤差を抑えることが可能である。なお、各ノードは、複数のグリッド・グラフに対応した複数のアンカ・ノードの識別情報を保存するためのリストを有していてもよく、自装置を新たなグリッド・グラフに組み込むごとに、当該グリッド・グラフのアンカ・ノードの識別情報をリストに追加して保存してもよい。
【００２３】
以下、本実施形態の詳細について説明する。本実施形態において各ノードは、手順１から手順８の８つの手順を１ターンとして、定期的に１つのターンを実行する。
【００２４】
＜手順１＞
まず、手順１において各ノードは、広告のための種々の情報を含むパケットを無線信号でブロードキャストする。具体的には、このパケットは、広告元のノードの識別子に加えて、広告したノードが保持する、隣接ノード情報と、隣接スコア情報と、グリッド・グラフ情報とを含んでいる。なお、パケットに含まれるこれら情報の詳細については後述する。ここで、最初に各ノードを設置したときにおいて、アンカ・ノードは、隣接ノード情報と、隣接スコア情報と、グリッド・グラフ情報とを保持してはいない。さらに、アンカ・ノード以外のノードは、いずれの情報も保持してはいない。各ノードは、周期的に広告を行うが、広告するパケットには、広告時に保持している情報のみを含める。つまり、例えば、設置時においては、自装置の存在を通知する目的のみで、上記いずれの情報も含ないパケットをブロードキャストする。各ノードは、その後、別のノードからの広告を受信することで、隣接ノード情報を生成すると、次に送信するパケットには、隣接ノード情報を含め、その後、別のノード装置から隣接スコア情報を取得すると、次に送信するパケットには隣接ノード情報と隣接スコア情報を含める。この様にして、グリッド・ノードは、隣接ノード情報と、隣接スコア情報と、グリッド・グラフ情報とを最終的に広告する様になる。手順１において、各ノードは、他のノードに広告のためのパケットを送信すると共に、他のノードが広告するパケットを受信し、処理待ちパケットに格納する。
【００２５】
＜手順２＞
手順２において、各ノードは、直接信号を受信できる別のノードから受信する隣接ノード情報に基づき、自装置から２ホップまでのノードについてのトポロジ情報を生成する。例えば、ノードＡからＩ及びＺが図２（Ａ）の様に接続しているものとする。なお、図２（Ａ）において矢印の方向は通信可能な方向を示している。例えば、ノードＦからノードＺへの片方向の矢印は、ノードＦの信号はノードＺには届くが、ノードＺの信号はノードＦには届いていないことを示している。また、ノードＺとノードＨの双方向の矢印は、ノードＺの信号をノードＨは受信でき、ノードＨの信号をノードＺは受信できることを示している。
【００２６】
例えば、ノードＺは、ノードＢ、Ｄ、Ｅ、Ｊ、Ｈ、Ｆから信号を受信できるため、ノードＢ、Ｄ、Ｅ、Ｊ、Ｈ、ＦからノードＺ方向へのリンクが存在することを認識する。したがって、ノードＢ、Ｄ、Ｅ、Ｊ、Ｈ、ＦからノードＺ方向へのリンクが存在することを示す隣接ノード情報を広告する。また、ノードＢは、ノードＺからの信号を受信できるため、ノードＢが広告する隣接ノード情報は、ノードＢがノードＺからの信号を受信できることを示している。したがって、ノードＺは、ノードＢとは双方向のリンクで接続していることを認識する。同様に、ノードＢはノードＤと双方向のリンクで接続していることを認識するため、ノードＢが広告する隣接ノード情報は、ノードＢとノードＤが双方向のリンクで結ばれていることを示し、よって、ノードＺは、ノードＢとノードＤとの間の双方向のリンクを認識する。さらに、ノードＺは、ノードＨとも双方向のリンクで接続していることを認識し、さらに、ノードＨが広告する隣接ノード情報は、ノードＨがノードＩからの信号を受信できることを示しているため、ノードＺは、ノードＩからノードＨへの片方向リンクが存在することを認識する。
【００２７】
なお、ノードＡにノードＺの信号は届くが、ノードＺにノードＡの信号は届かない。したがって、ノードＺは、ノードＡの存在を認識しない。よって、図２（Ａ）に示す接続状態であると、ノードＺは、最終的に、２ホップ以内のノードのトポロジ情報として、図２（Ｂ）に示す情報を生成する。図２（Ｂ）は、行に示すノードから列に示すノード方向のリンクが存在する場合を１で示している。なお、図２（Ｂ）において、ノードＡ、Ｃ及びＧがないのは、ノードＺはノードＡ及びＣを認識できず、ノードＧは、３ホップ先のノードであるからである。例えば、ノードＺは、図２（Ｂ）に示す自装置と１ホップで通信できるノードと、当該ノードとのリンクの種別、つまり、片方向であるか双方向であるかを示す情報を隣接ノード情報として広告する。また、自分自身から自分自身へのリンクは考慮しないため、０とする。なお、本実施形態において、各ノードは隣接するノードについての情報のみを隣接ノード情報として広告するが、２ホップ以内で接続する総てのノードを広告する等、最終的に２ホップ以内のノードとの接続関係を認識できる任意の方法を使用することができる。
【００２８】
＜手順３＞
続いて、手順３において各ノードは、２ホップ以内のトポロジ情報に基づき“ユニット・グリッド”を探索する。ここで、図３（Ａ）は、手順３において各ノードが探索するユニット・グリッドの一例を示している。なお、図３（Ａ）において、“自”と記載されたノードは、ユニット・グリッドを探索しているノードである。本実施形態では、上述のようにグリッド・グラフが偏った拡張をすることを防止するために、図３（Ａ）に示すような対称的な格子状のユニット・グリッド（部分グラフ）を使用する。このユニット・グリッドは、各ノードが１ホップ・ノード及び２ホップ・ノードを探索する範囲に相当する。各ノードは、当該範囲内の座標に対応する複数のノードを含むグループを探索する。具体的には、各ノードは、図３（Ａ）に示す条件を満たす自装置を含む９つのノードの組が存在するか否かを判定し、存在する場合には、当該条件を満たす総ての組を特定する情報を保存して探索を終了する。
【００２９】
図３（Ａ）に示す様に、ユニット・グリッドの条件は、ユニット・グリッドを探索しているノードを直交座標の原点とすると、座標（０，０）、（１，０）、（０，１）、（−１，０）、（０，−１）、（１，１）、（１，−１）、（−１，１）、（１，１）の計９つの座標に対応するノードは、各軸方向で隣接する座標に対応するノードとは双方向リンクで結ばれるが、各軸方向において隣接しない座標に対応するノード間にはリンクが存在しないことである。図３（Ａ）において、ノードＢがノードＡやノードＬとリンクを持つ場合にはユニット・グリッドの条件を満たさないことになる。なお、ユニット・グリッド以外のノードとはリンクを持つことができる。例えば、図３（Ａ）には示していないノードＺが存在し、ノードＺがノードＢとノードＫとリンクを持っていたとしても問題ない。
【００３０】
各ノードは、ユニット・グリッドが見つかった場合、ユニット・グリッドに含まれるノードを図３（Ｂ）に示す配列ｇ０〜ｇ９に対応づけて保存する。なお、ユニット・グリッドは、その位置関係のみが重要であり、あるユニット・グリッドと、線対称であるものや、あるユニット・グリッドを回転させたものは総て同じものとしてあつかう。つまり、図４（Ａ）に示すノードの集合がユニット・グリッドとして選択された場合、図４（Ａ）の配置に対して、垂直方向の軸対象（図４（Ｂ））、水平方向の軸対象（図４（Ｃ））、９０°回転（図４（Ｄ））した集合は、図４（Ａ）のユニット・グリッドと同じものである。
【００３１】
＜手順４＞
手順４において、各ノードは、手順３で探索した各ユニット・グリッドのユニット・スコアを算出する。以下の説明において、ユニット・グリッドを探索したノードをユニット・グリッドの“基準ノード”と呼び、ユニット・グリッドの基準ノードの隣接ノードを“１ホップ・ノード”と呼び、ユニット・グリッドの基準ノードから２ホップで接続するノードを“２ホップ・ノード”と呼ぶものとする。例えば、図５（Ａ）のユニット・グリッドの基準ノードはノードＺであり、１ホップ・ノードはノードＡ、Ｂ、Ｃ及びＤであり、２ホップ・ノードはノードＫ、Ｌ、Ｍ及びＮである。
【００３２】
“ユニット・スコア”は、ユニット・グリッドの１ホップ・ノードのノード・スコアの合計値である。ここで、“ノード・スコア”とは、ユニット・グリッドのノードが、他のノードにおいてユニット・グリッドの１ホップ・ノードとして選択されている回数である。このノード・スコアの計算のため、各ノードは、隣接スコア値をパケットに含めて広告する。例えば、ノードＺが図５（Ａ）〜（Ｃ）に示す様に３つのユニット・グリッドを探索して保持しているものとする。この場合、ノードＡ、Ｂ及びＤは、総てのユニット・グリッドに含まれているので、ノードＡ、Ｂ及びＤの隣接スコア値は３である。一方、ノードＥは、２つのユニット・グリッドに含まれているので、ノードＥの隣接スコア値は２である。さらに、ノードＣは、１つのユニット・グリッドに含まれているので、ノードＣの隣接スコア値は１である。この場合、ノードＺは、上記各ノードの隣接スコア値を含む隣接スコア情報を広告する。
【００３３】
各ノードは、別のノードが広告する隣接スコア情報に基づきユニット・グリッドの１ホップ・ノードのノード・スコア値を算出する。例えば、ノードＺが、あるノードからノードＡの隣接スコア値が３であると受信し、さらに別のノードからノードＡの隣接スコア値が４であると受信すると、ノードＡのノード・スコア値は７となる。そして、ノードＡ、Ｂ、Ｃ、Ｄのノード・スコア値がそれぞれ、７、３、２、１であると、図５（Ａ）のユニット・グリッドのユニット・スコアは７＋３＋２＋１＝１３となる。また、さらに、ノードＥのノード・スコアが３であると、図５（Ｂ）及び（Ｃ）のユニット・スコアは１４となる。
【００３４】
＜手順５＞
続いて、手順５について説明する。手順５は、各アンカ・ノードがそれぞれ独立にその処理を開始し、各アンカ・ノードを起点、本実施形態では原点、とする図１に示すグリッド・グラフを形成する処理のトリガである。つまり、各アンカ・ノードに関連するグリッド・グラフの座標（ｘ，ｙ）、ここでｘ及びｙは整数、に対応させるノードを決定する処理のトリガである。ただし、すでに自身を原点とするグリッド・グラフを形成済みであれば、手順５をスキップする。
【００３５】
手順５において、各アンカ・ノードは、ユニット・スコア値の一番高いユニット・グリッドを選択する。なお、ユニット・スコア値の一番高いユニット・グリッドが複数ある場合には、その中から任意の１つを選択する。そして選択したユニット・グリッドに基づきグリッド・グラフ情報を生成し、生成したグリッド・グラフ情報を広告する。
【００３６】
図６（Ａ）は、アンカ・ノードであるノードＺがグラフＺを形成するために１つのユニット・グリッドを選択した場合を示している。１つのユニット・グリッドを選択することで、選択したユニット・グリッドの１ホップ・ノードがグラフＺのグリッド・ノードに決定される。また、このときノードＺは、選択したユニット・グリッドの１ホップ・ノードそれぞれのグラフＺの座標も決定する。なお、座標の決定においては、ユニット・グリッドの位置関係に従う。例えば、図６（Ａ）において、ノードＺは、ノードＤ、Ａ、Ｂ、Ｃを、それぞれ、座標（１，０）、（０，１）、（−１，０）、（０，−１）に対応するノードに決定している。なお、ユニット・グリッドは、基準ノードとの相対的な関係のみが重要であるので、ノードＺは、座標（１，０）、（０，１）、（−１，０）、（０，−１）に対応するノードを、例えば、ノードＡ、Ｂ、Ｃ、Ｄと決定することもできる。さらに、ノードＺは、座標（１，０）、（０，１）、（−１，０）、（０，−１）に対応するノードを、例えば、ノードＢ、Ａ、Ｄ、Ｃに決定することもできる。つまり、ノードＺは、選択したユニット・グリッドの１ホップ・ノードの座標を、ノードＺを中心とする位置関係に従う範囲において自由に決定できる。
【００３７】
図９（Ａ）は、ノードＺが図６（Ａ）に示す様に決定したグリッド・ノードを広告するためのグリッド・グラフ情報を示している。グリッド・グラフ情報は、起点フィールド、シーケンス・フィールド、座標フィールド、及びステージ・フィールドの各フィールドを有する。ノードＺが広告するグリッド・グラフ情報の各フィールドには、以下の情報が記載されている。
【００３８】
（起点フィールド）
グリッド・グラフ情報の起点フィールドは、形成するグリッド・グラフに関連するアンカ・ノードの識別子を示している。つまり、グラフＺの形成のためのグリッド・グラフ情報の起点フィールドには常にノードＺの識別子が設定される。
【００３９】
（シーケンス・フィールド）
グリッド・グラフ情報のシーケンス・フィールドには、グラフＺの形成を開始するごとにノードＺが割り当てる番号が設定される。つまり、あるグラフＺの作成において、起点フィールド及びシーケンス・フィールドに設定されている値は常に同じとなる。したがって、以下の説明において、起点フィールドとシーケンス・フィールドの再度の説明は省略する。なお、ノードＺが既存のグラフＺを解放し、新たにグラフＺの作成を開始すると、グリッド・グラフ情報のシーケンス・フィールドの値が更新される。
【００４０】
（座標フィールド）
グリッド・グラフ情報の座標フィールドには、当該グリッド・グラフ情報を広告したノードの座標が設定される。つまり図９（Ａ）のグリッド・グラフ情報においては、ノードＺの座標（０，０）が設定される。
【００４１】
（ユニット・フィールド）
グリッド・グラフ情報のユニット・フィールドには、選択したユニット・グリッドの１ホップ・ノードの識別子を所定の順番で設定する。本実施形態では、当該グリッド・グラフ情報を広告しているノードの座標に対して、Ｙ座標の値を１だけ減じたノード（以後、−ｙと表示。）、Ｘ座標の値を１だけ減じたノード（以後、−ｘと表示。）、Ｘ座標の値を１だけ増加させたノード（以後、＋ｘと表示。）、Ｙ座標の値を１だけ増加させたノード（以後、＋ｙと表示。）の順で設定する。図６（Ａ）に示すユニット・グリッドにおいて、ノードＺは、ノードＣを座標（０，−１）とし、ノードＢを座標（−１，０）とし、ノードＤを座標（１，０）とし、ノードＡを座標（０，１）としている。したがって、図９（Ａ）に示す様に、ユニット・フィールドにはノードＣ、Ｂ、Ｄ、Ａの順に記載される。また、ユニット・フィールドには、ユニット・グリッドのユニット・スコア値も設定される。例えば、図６（Ａ）では、ノードＣ、Ｂ、Ｄ、Ａが属するユニット・グリッドユニット・グリッドのユニット・スコア値として“５”が設定されている。
【００４２】
（ステージ・フィールド）
図９（Ａ）に示すグリッド・グラフ情報のステージ・フィールドには“決定”が設定される。これは、ユニット・フィールドのノードがグラフＺのグリッド・ノードに決定されたことを示している。図９（Ａ）に示すグリッド・グラフ情報を含むパケットは、ノードＺからの信号を直接受信できる総てのノードが受信する。ノードＡ〜Ｄは、当該パケットを受信すると、ユニット・フィールド及びステージ・フィールドの情報から、自装置がグラフＺのグリッド・ノードにて選択されたことと、その座標を知る。
【００４３】
＜手順６＞
本手順において、手順５で決定したグリッド・グラフの原点に隣接する座標のノードを軸に、当該グリッド・グラフを拡張させる。本実施形態では、グリッド・グラフの偏った拡張を防ぐために、各ノードは、図３（Ａ）に示すような対称的な格子形状のユニット・グリッドを使用する。これにより、Ｘ軸及びＹ軸上の座標以外の座標に対応する各ノード（軸外ノード）は、探索したグループに含まれる１ホップ・ノードのうち、Ｘ軸及びＹ軸方向においてアンカ・ノードにそれぞれ１ホップ近い（上流側の）２つのノードの両方が、グリッド・グラフのノードとして決定された後に、自装置をグリッド・グラフの座標に決定してようにする。なお、既に説明した様に、グリッド・グラフの座標に対応させるノードは、Ｘ軸方向で隣接する座標に対応するノード装置が存在するのであれば、このＸ軸方向で隣接する座標のノード装置とは双方向リンクを有し、Ｙ軸方向で隣接する座標に対応するノード装置が存在するのであれば、このＹ軸方向で隣接する座標のノード装置とは双方向リンクを有し、Ｘ軸方向でもＹ軸方向でも隣接しない座標に対応する他のノード装置とは双方向リンクを有することが無いノードである。
【００４４】
手順５でアンカ・ノードであるノードＺから、それぞれ、座標（１，０）、（０，１）、（−１，０）、（０，−１）となったことを通知されたノードＤ、Ａ、Ｂ、Ｃは、既に決定した座標のノードとの位置関係を制約条件とし、この制約条件を満たすユニット・グリッドを判定し、制約条件を満たす総てのユニット・グリッドの１ホップ・ノードを含むグリッド・グラフ情報を広告する。なお、ユニット・グリッド探索時には座標を固定していないため、図３（Ｅ）に示す配列として記憶したユニット・グリッドそのままの状態だけではなく、各ノードは、これを回転させ、Ｙ軸対称に反転させ、Ｘ軸対称に反転させて、制約条件を満たすユニット・グリッドを探索する。
【００４５】
例えば、ノードＤにとっての制約条件は、ノードＺが１ホップ・ノードの１つであり、ノードＺ経由の２ホップ・ノードがノードＡ及びＣであることが制約条件となる。このノードＤの制約条件を満たす、ノードＤを基準ノードとするユニット・グリッドが図７（Ａ）〜（Ｃ）の３つであるものとする。なお、図７及び図８において網掛けのノードは、ノードＺによりその座標が決定されているノードを示している。この場合、ノードＤが広告するグリッド・グラフ情報を図９（Ｂ）に示す。図９（Ｂ）のグリッド・グラフ情報の座標フィールドには、ノードＤの座標である（１，０）が設定され、ステージ・フィールドには、“正側”が設定される。なお、ステージ・フィールドの意味については後述する。さらに、ユニット・フィールドには、制約条件を満たす３つのユニット・グリッドの１ホップ・ノードを、制約条件を満たす座標に従い記述する。例えば、図７（Ａ）のユニット・グリッドにおいて、基準ノードであるノードＤの−ｙ方向のノードはノードＦであり、−ｘ方向のノードはノードＺであり、＋ｘ方向のノードはノードＨであり、＋ｙ方向のノードはノードＥであるため、ノードＦ、Ｚ、Ｈ、Ｅの順で図７（Ａ）のユニット・グリッドが記載されている。また、ユニット・グリッドのユニット・スコアも記載する。例えば、図７（Ａ）のユニット・グリッドのユニット・スコアは１２となっている。なお、複数のユニット・グリッドがあり、その１ホップ・ノードが同じである場合には、２ホップ・ノードが異なったとしても、ユニット・フィールドに記載される情報は同じであるため、これらの情報は１つに纏める。
【００４６】
同様に、ノードＡに対する制約条件を満たす、ノードＡを基準ノードとするユニット・グリッドが図７（Ｄ）〜（Ｅ）の２つであり、ノードＣに対する制約条件を満たす、ノードＣを基準ノードとするユニット・グリッドが図８（Ａ）〜（Ｂ）の２つであり、ノードＢに対する制約条件を満たす、ノードＢを基準ノードとするユニット・グリッドが図８（Ｃ）〜（Ｄ）の２つであるものとする。この場合、ノードＤと同様に、ノードＡ、Ｃ、Ｂは、それぞれ、図９（Ｃ）、（Ｄ）、（Ｅ）に示すグリッド・グラフ情報を広告することになる。なお、当然ではあるが、広告しているノードは、パケットの送信元アドレスから特定される。
【００４７】
続いて、グリッド・グラフ情報のステージ・フィールドについて説明する。本実施形態において、グリッド・ノードのうち、Ｘ軸又はＹ軸上のノードを軸ノードと呼び、グリッド・ノードの軸ノード以外のノードを軸外ノードと呼ぶものとする。ステージ・フィールドが“決定”であるグリッド・グラフ情報は、軸ノードの決定を通知している。ステージ・フィールドが“決定”であるグリッド・グラフ情報を受信することで、自装置が軸ノードに選択されたことを知ったノードは、上述した様にステージ・フィールドが“正側”であるグリッド・グラフ情報を広告する。これは、グリッド・グラフ情報を広告しているノードがＸ軸上の軸ノードである場合、その軸ノードの＋ｙ方向のノードを決定するためのグリッド・グラフ情報であることを示している。一方、グリッド・グラフ情報を広告しているノードがＹ軸上の軸ノードである場合、その軸ノードの＋ｘ方向のノードを決定するためのグリッド・グラフ情報であることを示している。
【００４８】
つまり、図９（Ｂ）のグリッド・グラフ情報を送信するノードＤは、Ｘ軸の軸ノードであるため、図９（Ｂ）のグリッド・グラフ情報は、＋ｙ方向の座標、つまり、座標（１，１）のノードを決定するためのものであることがわかる。同様に、図９（Ｃ）のグリッド・グラフ情報を送信するノードＡは、Ｙ軸の軸ノードであるため、図９（Ｃ）のグリッド・グラフ情報は、＋ｘ方向の座標、つまり、座標（１，１）のノードを決定するためのものであることがわかる。ここで、グリッド・グラフにおいて、原点に１ホップだけ近づくノードを上流側ノードと呼び、原点から１ホップだけ遠くなるノードを下流側ノードと呼ぶものとする。座標（１，１）の様に、軸外ノードは２つの上流側ノードを持ち、グリッド・グラフを拡張するためには、この２つの上流側ノードのユニット・グリッドを調整しながら決定しなければならない。具体的には、ノードＤが基準ノードであるユニット・グリッドのうち、図７（Ｃ）に示すユニット・グリッドを選択すると、座標（１，１）のノードはノードＫとなるが、この場合、ノードＡが基準ノードであるユニット・グリッド（図７の（Ｄ）、（Ｅ））とは両立せず、第１象限方向へのグリッド・グラフの拡張が停止することになる。一方、図７（Ａ）又は（Ｂ）に示すユニット・グリッドに応じて座標（１，１）のノードをノードＥとすると、ノードＡのユニット・グリッドと両立するため、第１象限方向にグリッド・グラフを拡張することができる。
【００４９】
本実施形態では、グリッド・グラフ情報を受信したノードのそれぞれが、送信元ノードの座標と、ステージ・フィールドの値と、ユニット・フィールドの内容に基づき、自装置が軸外ノードであるか否かを判定する。例えば、既に説明した様に、図９（Ｂ）のグリッド・グラフ情報は、Ｘ軸方向の上流側からのものであり、かつ、座標（１，１）のノードを決定するためのものであることがわかる。ここで、ユニット・フィールドの３つのユニット・グリッドの＋ｙ方向の位置にあるノードは、ノードＥとＫである。同様に、図９（Ｃ）のグリッド・グラフ情報は、Ｙ軸方向の上流側からのものであり、かつ、座標（１，１）のノードを決定するためのものであることがわかる。ここで、ユニット・フィールドの２つのユニット・グリッドの＋ｘ方向の位置にあるノードは、ノードＥのみである。グリッド・ノードに選択されていないノードは、Ｘ軸方向とＹ軸方向の２つの上流側のノードから受信するグリッド・グラフ情報の同じ座標に自装置が指定されている場合、自装置が当該座標の候補であると判定する。本例において候補はノードＥのみであるが、１つのグリッド・グラフ情報には、制約条件を満たす総てのユニット・グリッドの１ホップ・ノード及びユニット・スコア値が設定されるため、候補ノードは、候補ノードが１つであるのか複数あるのかを認識することができる。そして、本例の様に１つしかない場合には、その１つの候補ノードは、自装置が当該座標のノードであると判定し、自装置が当該座標のノードであることを示すグリッド・グラフ情報を広告する。図６（Ｂ）は、グラフＺの座標（１，１）にノードＥが決定された状態を示している。
【００５０】
図９（Ｆ）は、座標（１，１）に決定したノードＥが送信するグリッド・グラフ情報である。図９（Ｆ）に示す様に、座標フィールドには、ノードＥの座標である（１，１）が設定され、ステージ・フィールドには、“下流未定”が設定される。これは、ノードＥの下流側のノード、つまり、座標（１，２）及び（２，１）が現在のところ未定であることを示している。また、ユニット・フィールドには、ノードＥに対してノードＡ、Ｚ、Ｄの位置関係が図６（Ｂ）となる制約条件を満たす、ノードＥを基準ノードとするユニット・グリッドの１ホップ・ノードが、上記と同様に設定される。
【００５１】
なお、２つの上流側ノードから座標（１，１）として指定されたノードが複数ある場合には、ノードが属するユニット・グリッドのスコア値の合計で判定する。例えば、図９（Ｂ）のグリッド・グラフ情報において、ノードＥを含むユニット・グリッドのユニット・スコア値の合計は２２であり、図９（Ｃ）のグリッド・グラフ情報においては２２であり、よって、ノードＥについてユニット・スコア値の合計値は４４となる。候補となるノードが他にある場合、ノードＥは、他の候補ノードそれぞれについてもユニット・スコア値の合計を求め、自装置が最高値であるか否かを判定する。最高値であれば、自装置が座標（１，１）のノードとして、グリッド・グラフ情報を広告する。一方、自装置が最高でなければなにもしない。なお、複数のノードのユニット・スコア値の合計が同じであり、かつ、最高である場合には、例えば、ノードの識別子の大小等、その他の予め定めた基準により決定されるノードが当該座標のノードとなる。
【００５２】
ノードＤ及びＡは、図９（Ｆ）に示すグリッド・グラフ情報を受け取ることで、ノードＥが座標（１，１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１０（Ａ）及び（Ｂ）に示す様に変更する。具体的には、ノードＤは、＋ｙ側のノードが確定したことによりステージ・フィールドの値を“負側”に変更する。これは、−ｙ側、つまり、座標（１，−１）のノードを決定することを広告している。また、ノードＥが座標（１，１）との制約条件が増えたことで、図７（Ｃ）のユニット・グリッドはもはや制約条件を満たさないため、図７（Ｃ）のユニット・グリッドに対応する情報をユニット・フィールドから削除する。同様に、ノードＡは、＋ｘ側のノードが確定したことによりステージ・フィールドの値を“負側”に変更する。これは、−ｘ側、つまり、座標（−１，１）のノードを決定することを広告している。なお、ノードＡが広告するユニット・フィールドは、本例では変更が無い。
【００５３】
ノードＤ及びＡがステージ・フィールドの値を“負側”に変更したことで、座標（１，−１）と座標（−１，１）を決定する処理が並行して開始される。まず、座標（１，−１）の決定について説明する。既に説明した様に、図１０（Ａ）のグリッド・グラフ情報は、広告元の座標（１，０）の−ｙ方向の座標、つまり、座標（１，−１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グリッドの−ｙ方向の位置にあるノードは、ノードＦとＪである。同様に、図９（Ｄ）のグリッド・グラフ情報は、広告元の座標（０，−１）の＋ｘ方向（ステージ・フィールドが“正側”）の座標、つまり、座標（１，−１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グリッドの＋ｘ方向の位置にあるノードは、ノードＦのみである。したがって、ノードＦが座標（１，−１）のノードとなり、ノードＦは図１０（Ｃ）に示すグリッド・グラフ情報を広告する。
【００５４】
続いて、座標（−１，１）の決定について説明する。既に説明した様に、図１０（Ｂ）のグリッド・グラフ情報は、広告元の座標（０，１）の−ｘ方向の座標、つまり、座標（−１，１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グリッドの−ｘ方向の位置にあるノードは、ノードＯとＰである。同様に、図９（Ｅ）のグリッド・グラフ情報は、広告元の座標（−１，０）の＋ｙ方向（ステージ・フィールドが“正側”）の座標、つまり、座標（−１，１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グリッドの＋ｙ方向の位置にあるノードは、ノードＰのみである。したがって、ノードＰが座標（−１，１）のノードとなり、ノードＰは図１０（Ｄ）に示すグリッド・グラフ情報を広告する。図６（Ｃ）は、ノードＰ及びＦがグリッド・ノードになった状態を示している。
【００５５】
ノードＣは、図１０（Ｃ）のグリッド・グラフ情報を受け取ることで、ノードＦが座標（１，−１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１０（Ｅ）に示す様に変更する。本例においては、ステージ・フィールドの値を“負側”に変更するのみである。同様に、ノードＢは、図１０（Ｄ）のグリッド・グラフ情報を受け取ることで、ノードＰが座標（−１，１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１０（Ｆ）に示す様に変更する。本例においては、ステージ・フィールドの値を“負側”に変更するのみである。
【００５６】
また、ノードＤは、図１０（Ｃ）に示すグリッド・グラフ情報を受け取ることで、ノードＦが座標（１，−１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１１（Ａ）に示す様に変更する。具体的には、グリッド・ノードとなったノードＡ、Ｚ、Ｃ、Ｅ、Ｄ、Ｆを制約条件とすると、選択できるユニット・グリッドユニット・グリッドは図７（Ａ）のみであるため、これにより座標（２，０）のノードをノードＨであると決定する。よって、図１１（Ａ）に示す様に、ステージ・フィールドを“決定”にし、ユニット・フィールドには決定したユニット・グリッドの１ホップ・ノードを含むグリッド・グラフ情報を広告する。これにより、ノードＨは自装置が座標（２，０）のノードとなったことを知る。なお、選択できるユニット・グリッドが複数ある場合には、ユニット・スコアの一番高いものを選択する。さらに、複数のユニット・グリッドのユニット・スコアが同点である場合には、その中から任意の一つを選択する。
【００５７】
同様に、ノードＡは、図１０（Ｄ）に示すグリッド・グラフ情報を受け取ることで、ノードＰが座標（−１，１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１１（Ｂ）に示す様に変更する。具体的には、グリッド・ノードとなったノードＰ、Ａ、Ｅ、Ｂ、Ｚ、Ｄを制約条件とすると、選択できるユニット・グリッドは図７（Ｅ）のもののみであるため、これにより座標（０，２）のノードをノードＭであると決定する。よって、図１１（Ｂ）に示す様に、ステージ・フィールドを“決定”にし、ユニット・フィールドには決定したユニット・グリッドの１ホップ・ノードを含むグリッド・グラフ情報を広告する。これにより、ノードＭは自装置が座標（０，２）のノードとなったことを知る。図６（Ｄ）は、さらにノードＭ及びＨがグリッド・ノードになった状態を示している。
【００５８】
続いて、座標（−１，−１）の決定について説明する。図１０（Ｅ）のグリッド・グラフ情報は、広告元の座標（０，−１）の−ｘ方向の座標、つまり、座標（−１，−１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グリッドの−ｘ方向の位置にあるノードは、ノードＱである。同様に、図１０（Ｆ）のグリッド・グラフ情報は、広告元の座標（−１，０）の−ｙ方向、つまり、座標（−１，−１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グリッドの−ｙ方向の位置にあるノードは、ノードＱのみである。したがって、ノードＱが座標（−１，−１）のノードとなり、図１１（Ｃ）に示すグリッド・グラフ情報を広告する。図６（Ｅ）は、ノードＱがグリッド・ノードになった状態を示している。
【００５９】
ノードＣは、図１１（Ｃ）のグリッド・グラフ情報を受け取ることで、ノードＱが座標（−１，−１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１１（Ｄ）に示す様に変更する。具体的には、既に決定したグリッド・ノードを制約条件とすると、図８（Ａ）及び（Ｂ）の両方を選択できる。したがってユニット・スコア値の大きい図８（Ａ）のユニット・グリッドを選択し、これにより座標（０，−２）のノードをノードＳであると決定する。よって、図１１（Ｄ）に示す様に、ステージ・フィールドを“決定”にし、ユニット・フィールドには決定したユニット・グリッドの１ホップ・ノードを含むグリッド・グラフ情報を広告する。これにより、ノードＳは自装置が座標（０，−２）のノードとなったことを知る。
【００６０】
一方、ノードＢは、図１１（Ｃ）のグリッド・グラフ情報を受け取ることで、ノードＱが座標（−１，−１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１１（Ｅ）に示す様に変更する。具体的には、既に決定したグリッド・ノードを制約条件とすると、図８（Ｃ）及び（Ｄ）の両方を選択できる。したがってユニット・スコア値の大きい図８（Ｃ）のユニット・グリッドを選択し、これにより座標（−２，０）のノードをノードＷであると決定する。よって、図１１（Ｅ）に示す様に、ステージ・フィールドを“決定”にし、ユニット・フィールドには決定したユニット・グリッドの１ホップ・ノードを含むグリッド・グラフ情報を広告する。これにより、ノードＷは自装置が座標（−２，０）のノードとなったことを知る。図６（Ｆ）は、ノードＳ及びＷがグリッド・ノードになった状態を示している。
【００６１】
以後、例えば、座標（２，０）のノードＨと、座標（１，１）のノードＥが広告するグリッド・グラフ情報により座標（２，１）のノードが決定され、座標（０，２）のノードＭと、座標（１，１）のノードＥが広告するグリッド・グラフ情報により座標（１，２）のノードが決定され、座標（２，１）のノードと、座標（１，２）のノードが広告するグリッド・グラフ情報により座標（２，２）のノードが決定されるといった様に、各象限において同様の処理が繰り返えされることで、各象限の方向にグリッド・グラフが拡張される。なお、軸外ノードは、まず、ステージ・フィールドに“下流未定”を設定するが、下流側ノードから自装置の正しい座標を示すグリッド・グラフ情報を受け取ると、グリッド・グラフ情報のユニット・フィールドの値を更新する。また、２つの下流側ノードからグリッド・グラフ情報を受け取ると、ステージ・フィールドを“下流決定”に変更し、それに応じて広告するグリッド・グラフ情報のユニット・フィールドの値を更新する。なお、軸外ノードが、最初にグリッド・グラフ情報を広告するときにおいて、既に決定したグリッド・ノードを制約条件とするユニット・グリッドが１つのみである場合、ステージ・フィールドには“下流決定”を設定する。
【００６２】
なお、各ノードは、他のノードから広告されたグリッド・グラフ情報に基づいて、自装置をグリッド・グラフの座標に対応するノードとして決定した場合、アンカ・ノードの識別情報を保存する。アンカ・ノードの識別情報は、図９〜図１１に示すように、他のノードから広告されたグリッド・グラフ情報の起点フィールドから取得できる。
【００６３】
また、本実施形態においては、各軸ノードは、ステージ・フィールドに“正側”を設定し、次いで、“負側”を設定していた。しかしながら、各軸ノードは、ステージ・フィールドに“負側”を設定し、次いで、“正側”を設定することも可能である。さらに、Ｘ軸上の軸ノードは、ステージ・フィールドに“正側”を設定し、次いで、“負側”を設定する一方、Ｙ軸上の軸ノードは、ステージ・フィールドに“負側”を設定し、次いで、“正側”を設定することやその逆も可能である。
【００６４】
＜手順７＞
手順７においては、いずれのグリッド・グラフのグリッド・ノードにもならなかった非グリッド・ノードが、グリッド・グラフのグリッド・ノードからグリッド・グラフ情報を直接受信すると、当該グリッド・グラフ情報の起点フィールドの情報（アンカ・ノードの識別情報）を保存する。これにより、グリッド・ノードだけでなく、非グリッド・ノードも、保存した識別情報に対応するアンカ・ノードと同一の凸包領域に含まれていることを認識できる。非グリッド・ノードは、多辺測量ベースの位置推定技術を使用する場合、保存した識別情報に対応するアンカ・ノードからフラッディングされる情報のみを使用する。即ち、非グリッド・ノードは、保存した識別情報に対応するアンカ・ノード以外のアンカ・ノードからフラッディングされる情報については無視する。このように、非アンカ・ノードは、多辺測量ベースの位置推定技術により自装置の位置を推定する際には、受信したグリッド・グラフ情報に基づいて、いずれのアンカ・ノードを利用すべきかを決定する。これにより、非凸包形状に対応したグラフ情報を用いて位置推定を行うことを避けることができ、位置推定誤差を低減することができる。
【００６５】
上記実施形態では、アンカ・ノードがグリッド・グラフを生成する起点（即ち、凸包領域の中心）となる場合について説明している。しかし、本発明は、アンカ・ノード以外のノードが起点となった場合にも、グリッド・グラフを生成可能である。例えば、各ノードが適当な確率演算で起点ノードとなって、グリッド・グラフを生成してもよい（例えば、確率1の場合、全ノードが起点となる）。なお、確率演算によらず、各ノードが自装置の隣接ノードの全ノード・スコア値の総和を求め、求めた総和と閾値との比較によって、起点ノードとなるかを判定してもよい。さらに、起点となった各ノードの識別情報を、上述のような位置推定に利用するために、他のノードがリストとして保存してもよい。また、各ノードは、自装置が保存しているリストに含まれる、起点ノードの識別子を、フラッディングによって別のノードに広告してもよい。これにより、アンカ・ノードを起点としたグリッド・グラフだけでなく、他のノードを起点としたグリッド・グラフを生成することによって、アンカ・ノードに対応するグリッド・グラフではカバーしきれない領域を、他のノードに対応する（凸包領域の）グリッド・グラフでカバーすることが可能になる。
【００６６】
以上説明したように、上記実施形態によれば、複数のノードを含み、各ノードは別のノードと無線により通信するシステムにおいて、ノードの相対的な位置関係に対応し、凸包形状の領域を特定するグラフ情報をノード装置が生成できる。これにより、生成したグラフ情報を多辺測量ベースの位置推定技術に適用した場合に、位置推定誤差を低減し、精度良くノードの設置位置を推定することが可能になる。
【００６７】
なお、本発明によるノードは、コンピュータを上記ノードとして動作させるプログラムにより実現することができる。これらコンピュータプログラムは、コンピュータが読み取り可能な記憶媒体に記憶されて、又は、ネットワーク経由で配布が可能なものである。
【図１】
2015070544.tif 000003
【図２】
2015070544.tif 000004
【図３】
2015070544.tif 000005
【図４】
2015070544.tif 000006
【図５】
2015070544.tif 000007
【図６】
2015070544.tif 000008
【図７】
2015070544.tif 000009
【図８】
2015070544.tif 000010
【図９】
2015070544.tif 000011
【図１０】
2015070544.tif 000012
【図１１】
2015070544.tif 000013