(57)【要約】【課題】中央で計算するサーバを必要としないノード装置の設置位置の推定方法を提供する。【解決手段】方法は、位置情報を保持する第２のノード装置に関連するグリッド・グラフのグリッド・ノード装置を決定するステップであって、当該第２のノード装置を含む当該グリッド・ノード装置は、当該グリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応する、決定ステップと、グリッド・ノード装置の各第１のノード装置が、その座標と、グリッド・グラフの３つの第２のノード装置の位置情報及び座標に基づき、その設置位置を推定するステップと、を含み、グリッド・ノード装置のそれぞれは、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置と、Ｙ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できない。【選択図】図１
2014036277.tif 000002
【特許請求の範囲】
【請求項１】
設置位置の位置情報を保持しない第１のノード装置と設置位置の位置情報を保持する第２のノード装置をそれぞれ複数含み、各ノード装置は別のノード装置と無線により通信するシステムにおいて、前記第１のノード装置が設置位置を推定する方法であって、
各ノード装置が自装置を広告することで、自装置と直接通信できる別のノード装置を識別し、各ノード装置が前記識別した直接通信できる別のノード装置を示す情報を広告することで、各ノード装置において、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成ステップと、
各ノード装置が生成したトポロジ情報に基づき、前記第２のノード装置に関連するＸＹ座標平面であるグリッド・グラフに含まれるノード装置であるグリッド・ノード装置を決定する決定ステップであって、当該第２のノード装置を含む当該グリッド・ノード装置は、当該グリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応する、決定ステップと、
前記グリッド・ノード装置に含まれる各第１のノード装置に、前記グリッド・ノード装置に含まれる各第２のノード装置が、その位置情報及び座標を通知する通知ステップと、
前記グリッド・ノード装置に、その座標が一直線に並ばない３つの第２のノード装置が含まれている場合、前記グリッド・ノード装置に含まれる各第１のノード装置が、自装置の座標と、前記３つの第２のノード装置の位置情報及び座標に基づき、自装置の設置位置を推定する第１の推定ステップと、
を含み、
前記グリッド・ノード装置のそれぞれは、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置と、Ｙ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できないことを特徴とする方法。
【請求項２】
前記グリッド・ノード装置に含まれる各第１のノード装置が前記推定した設置位置の位置情報を広告し、各第２のノード装置がその位置情報を広告する位置情報広告ステップと、
前記グリッド・ノード装置に含まれない各第１のノード装置が、前記グリッド・ノード装置に含まれる各第１のノード装置及び各第２のノード装置が広告する位置情報に基づき、自装置の設置位置を推定する第２の推定ステップと、
をさらに含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記グリッド・ノード装置に４つ以上の第２のノード装置が含まれていると、前記第１の推定ステップにおいて、前記グリッド・ノード装置に含まれる各第１のノード装置は、前記グリッド・ノード装置に含まれる第２のノード装置から３つを選択する組み合わせそれぞれについて、組み合わせに含まれる３つの第２のノード装置をノード装置Ａ、Ｂ及びＣとすると、ノード装置Ａ及びノード装置Ｂの位置情報から求めたノード装置Ａとノード装置Ｂを結ぶ線分の傾きに対する、ノード装置Ａ及びノード装置Ｃの位置情報から求めたノード装置Ａとノード装置Ｃを結ぶ線分の傾きの比を求め、求めた比が１を含む所定範囲外となる組み合わせから１つの組み合わせを選択し、選択した組み合わせに含まれる３つの第２ノード装置に基づき自装置の設置位置を推定することを特徴とする請求項１又は２に記載の方法。
【請求項４】
前記求めた比が所定範囲外となる組み合わせが複数ある場合、前記グリッド・ノード装置に含まれる各第１のノード装置は、前記求めた比が所定範囲外となる組み合わせに含まれる３つの第２ノード装置の座標の重心と自装置の座標との距離を求め、求めた距離が最も短くなる組み合わせに基づき、或いは、求めた距離が所定値より短い組み合わせから１つの組み合わせを選択して自装置の設置位置を推定することを特徴とする請求項３に記載の方法。
【請求項５】
前記決定ステップにおいて、２つ以上の前記第２のノード装置のそれぞれに関連する複数のグリッド・グラフが生成されると、
複数のグリッド・グラフにおいてグリッド・ノード装置となった第１のノード装置は、前記第１の推定ステップにおいて、自装置が属する各グリッド・グラフについて推定する設置位置の重心を、自装置の推定した設置位置とすることを特徴とする請求項１から４のいずれか１項に記載の方法。
【請求項６】
前記生成ステップにおいて、各ノード装置は、前記トポロジ情報に基づき、
自装置を座標（０，０）とし、座標（０，０）、（１，０）、（０，１）、（−１，０）、（０，−１）、（１，１）、（１，−１）、（−１，１）及び（−１，−１）に対応する９つのノード装置を含む第１の組であって、前記９つの座標内において、各軸方向において隣接する座標に対応するノード装置とは双方向で直接通信でき、各軸方向において隣接する座標以外の座標に対応するノード装置とは直接通信できない第１の組を１つ以上探索して保存することを特徴とする請求項１から５のいずれか１項に記載の方法。
【請求項７】
前記生成ステップにおいて、各ノード装置は、前記第１の組が見つからないと、前記トポロジ情報に基づき、
自装置を座標（０，０）とし、座標（０，０）、（１，０）、（０，１）、（−１，０）、（０，−１）、（１，１）、（−１，１）及び（−１，−１）に対応する８つのノード装置を含む第２の組であって、前記８つの座標内において、各軸方向において隣接する座標に対応するノード装置とは双方向で直接通信でき、各軸方向において隣接する座標以外の座標に対応するノード装置とは直接通信できない第２の組を１つ以上探索して保存することを特徴とする請求項６に記載の方法。
【請求項８】
前記生成ステップにおいて、各ノード装置は、前記第２の組が見つからないと、前記トポロジ情報に基づき、
自装置を座標（０，０）とし、座標（０，０）、（１，０）、（０，１）、（−１，０）、（１，１）及び（−１，１）に対応する６つのノード装置を含む第３の組であって、前記６つの座標内において、各軸方向において隣接する座標に対応するノード装置とは双方向で直接通信でき、各軸方向において隣接する座標以外の座標に対応するノード装置とは直接通信できない第３の組を１つ以上探索して保存することを特徴とする請求項７に記載の方法。
【請求項９】
前記生成ステップにおいて、各ノード装置は、前記第３の組が見つからないと、前記トポロジ情報に基づき、
自装置を座標（０，０）とし、座標（０，０）、（１，０）、（０，１）及び（１，１）に対応する４つのノード装置を含む第４の組であって、前記４つの座標内において、各軸方向において隣接する座標に対応するノード装置とは双方向で直接通信でき、各軸方向において隣接する座標以外の座標に対応するノード装置とは直接通信できない第４の組を１つ以上探索して保存することを特徴とする請求項８に記載の方法。
【請求項１０】
前記生成ステップにおいて、各ノード装置は、探索した組に含まれる自装置と直接通信できる１ホップ・ノード装置のそれぞれについて、探索した組に含まれる回数を示すノード値を含む第１情報を広告し、探索した組のスコアを、別のノード装置が広告する前記第１情報に基づき求め、
前記決定ステップにおいて、前記グリッド・グラフに関連する第２のノード装置は、探索した組のうち、スコアの最も高い組に含まれる１ホップ・ノード装置のそれぞれを、当該第２のノード装置と当該１ホップ・ノード装置それぞれの位置関係に従い、当該第２のノード装置に対してＸ軸及びＹ軸方向で隣接する座標に対応するノード装置に決定し、決定したノード装置に決定した座標を通知し、
前記ノード装置が探索した組のスコアは、別のノード装置が広告する前記第１情報に含まれている、当該組の１ホップ・ノード装置のノード値の合計が大きい程、高くなることを特徴とする請求項６から９のいずれか１項に記載の方法。
【請求項１１】
前記決定ステップにおいて、前記グリッド・グラフの座標に決定したノード装置は、前記探索した組の中に、既に前記グリッド・グラフの座標に決定したノード装置に従う配置が可能な１つ以上の組が存在するかを判定し、存在する場合、判定した組のそれぞれについて、判定した組の１ホップ・ノード装置それぞれの座標と、当該判定した組のスコアを示すグラフ情報を広告し、
ｍ及びｎを１以上の整数とし、前記グリッド・グラフに関連する第２のノード装置の座標を座標（０，０）とすると、
座標（ｍ，ｎ−１）に決定したノード装置及び座標（ｍ−１，ｎ）に決定したノード装置が広告するグラフ情報の両方において、座標（ｍ，ｎ）の装置と示されたノード装置のうち、両グラフ情報に含まれる当該ノード装置を含む組のスコアの合計が最も高いノード装置は、自装置が座標（ｍ，ｎ）に決定したことを広告し、
座標（ｍ，−ｎ＋１）に決定したノード装置及び座標（ｍ−１，−ｎ）に決定したノード装置が広告するグラフ情報の両方において、座標（ｍ，−ｎ）の装置と示されたノード装置のうち、両グラフ情報に含まれる当該ノード装置を含む組のスコアの合計が最も高いノード装置は、自装置が座標（ｍ，−ｎ）に決定したことを広告し、
座標（−ｍ，ｎ−１）に決定したノード装置及び座標（−ｍ＋１，ｎ）に決定したノード装置が広告するグラフ情報の両方において、座標（−ｍ，ｎ）の装置と示されたノード装置のうち、両グラフ情報に含まれる当該ノード装置を含む組のスコアの合計が最も高いノード装置は、自装置が座標（−ｍ，ｎ）に決定したことを広告し、
座標（−ｍ，−ｎ＋１）に決定したノード装置及び座標（−ｍ＋１，−ｎ）に決定したノード装置が広告するグラフ情報の両方において、座標（−ｍ，−ｎ）の装置と示されたノード装置のうち、両グラフ情報に含まれる当該ノード装置を含む組のスコアの合計が最も高いノード装置は、自装置が座標（−ｍ，−ｎ）に決定したことを広告する、
ことをと特徴とする請求項１０に記載の方法。
【請求項１２】
前記決定ステップにおいて、
ｓを０以外の整数とし、ｔを１又は−１とし、ｕを１又は−１とし、ｋをｓが正の場合には＋１であり、ｓが負の場合には−１とし、前記グリッド・グラフに関連する第２のノード装置の座標を座標（０，０）とすると、
前記グリッド・グラフのＸ軸上の座標（ｓ，０）に決定したノード装置は、前記グラフ情報に、座標（ｓ，ｔ）と座標（ｓ，−ｔ）のうち、先に決定する座標である座標（ｓ，ｔ）を示す情報を含めて広告し、
座標（ｓ，ｔ）に決定したノード装置から、座標（ｓ，ｔ）に決定したことを示す広告を受信すると、前記座標（ｓ，０）に決定したノード装置は、前記探索した組の中に、既に前記グリッド・グラフの座標に決定したノード装置の配置に従い、かつ、座標（ｓ，−ｔ）に対応するノード装置を含む１つ以上の組が存在するかを判定し、存在する場合、判定した組のそれぞれについて、判定した組の１ホップ・ノード装置それぞれの座標と、当該判定した組のスコアを示すグラフ情報と、座標（ｓ，−ｔ）を決定することを示す情報を含むグリッド・グラフ情報を広告し、存在しない場合及び座標（ｓ，−ｔ）に決定したノード装置から、座標（ｓ，−ｔ）に決定したことを示す広告を受信した場合、前記探索した組の中に、既に前記グリッド・グラフの座標に決定したノード装置の配置に従い、かつ、座標（ｓ＋ｋ，０）に対応するノード装置を含む１つ以上の組が存在するかを判定し、存在する場合、判定した組から１つを選択して座標（ｓ＋ｋ，０）のノード装置を決定し、決定したノード装置に座標（ｓ＋ｋ，０）に決定したことを通知し、
前記グリッド・グラフのＹ軸上の座標（０，ｓ）に決定したノード装置は、前記グラフ情報に、座標（ｕ，ｓ）と座標（−ｕ，ｓ）のうち、先に決定する座標である座標（ｕ，ｓ）を示す情報を含めて広告し、
座標（ｕ，ｓ）に決定したノード装置から、座標（ｕ，ｓ）に決定したことを示す広告を受信すると、前記座標（０，ｓ）に決定したノード装置は、前記探索した組の中に、既に前記グリッド・グラフの座標に決定したノード装置の配置に従い、かつ、座標（−ｕ，ｓ）に対応するノード装置を含む１つ以上の組が存在するかを判定し、存在する場合、判定した組のそれぞれについて、判定した組の１ホップ・ノード装置それぞれの座標と、当該判定した組のスコアを示すグラフ情報と、座標（−ｕ，ｓ）を決定することを示す情報を含むグリッド・グラフ情報を広告し、存在しない場合及び座標（−ｕ，ｓ）に決定したノード装置から、座標（−ｕ，ｓ）に決定したことを示す広告を受信した場合、前記探索した組の中に、既に前記グリッド・グラフの座標に決定したノード装置の配置に従い、かつ、座標（０，ｓ＋ｋ）に対応するノード装置を含む１つ以上の組が存在するかを判定し、存在する場合、判定した組から１つを選択して座標（０，ｓ＋ｋ）のノード装置を決定し、決定したノード装置に座標（０，ｓ＋ｋ）に決定したことを通知する、
ことを特徴とする請求項１１に記載の方法。
【請求項１３】
設置位置の位置情報を保持しない第１のノード装置と設置位置の位置情報を保持する第２のノード装置をそれぞれ複数含み、各ノード装置は別のノード装置と無線により通信するシステムで使用する前記第１のノード装置であって、
自装置の存在を広告し、別のノード装置から広告を受信することで、自装置と直接通信できる別のノード装置を識別する識別手段と、
前記識別した直接通信できる別のノード装置を示す隣接情報を広告し、別のノード装置が広告する前記隣接情報を受信することで、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成手段と、
前記トポロジ情報に基づき、自装置が前記第２のノード装置に関連するＸＹ座標平面であるグリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応するノード装置であるグリッド・ノード装置であるか否かを判定する判定手段と、
前記グリッド・ノード装置であると判定すると、前記グリッド・ノード装置に、その座標が一直線に並ばない３つの第２のノード装置が含まれているかを判定し、含まれている場合、自装置の座標と、前記３つの第２のノード装置の位置情報及び座標に基づき、自装置の設置位置を推定する第１の推定手段と、
を備えており、
前記グリッド・ノード装置のそれぞれは、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置と、Ｙ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できないことを特徴とする第１のノード装置。
【請求項１４】
前記第１の推定手段が推定した位置情報を広告する位置情報広告手段と、
前記グリッド・ノード装置ではないと判定すると、前記グリッド・ノード装置に含まれる各第１のノード装置及び各第２のノード装置が広告する位置情報に基づき、自装置の設置位置を推定する第２の推定手段と、
をさらに備えていることを特徴とする請求項１３に記載の第１のノード装置。
【請求項１５】
前記グリッド・ノード装置に４つ以上の第２のノード装置が含まれていると、前記第１の推定手段は、前記グリッド・ノード装置に含まれる第２のノード装置から３つを選択する組み合わせそれぞれについて、組み合わせに含まれる３つの第２のノード装置をノード装置Ａ、Ｂ及びＣとすると、ノード装置Ａ及びノード装置Ｂの位置情報から求めたノード装置Ａとノード装置Ｂを結ぶ線分の傾きに対する、ノード装置Ａ及びノード装置Ｃの位置情報から求めたノード装置Ａとノード装置Ｃを結ぶ線分の傾きの比を求め、求めた比が１を含む所定範囲外となる組み合わせから１つの組み合わせを選択し、選択した組み合わせに含まれる３つの第２ノード装置に基づき自装置の設置位置を推定することを特徴とする請求項１３又は１４に記載の第１のノード装置。
【請求項１６】
前記求めた比が所定範囲外となる組み合わせが複数ある場合、前記第１の推定手段は、前記求めた比が所定範囲外となる組み合わせに含まれる３つの第２ノード装置の座標の重心と自装置の座標との距離を求め、求めた距離が最も短くなる組み合わせに基づき、或いは、求めた距離が所定値より短い組み合わせから１つの組み合わせを選択して自装置の設置位置を推定することを特徴とする請求項１５に記載の第１のノード装置。
【請求項１７】
自装置が、２つ以上の前記第２のノード装置のそれぞれに関連する複数のグリッド・グラフのグリッド・ノード装置である場合、
前記第１の推定手段は、自装置が属する各グリッド・グラフについて推定する設置位置の重心を、自装置の推定した設置位置とすることを特徴とする請求項１３から１６のいずれか１項に記載の第１のノード装置。
【請求項１８】
設置位置の位置情報を保持しない第１のノード装置と設置位置の位置情報を保持する第２のノード装置をそれぞれ複数含み、各ノード装置は別のノード装置と無線により通信するシステムで使用する前記第２のノード装置であって、
自装置の存在を広告し、別のノード装置から広告を受信することで、自装置と直接通信できる別のノード装置を識別する識別手段と、
前記識別した直接通信できる別のノード装置を示す隣接情報を広告し、別のノード装置が広告する前記隣接情報を受信することで、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成手段と、
自装置に関連するＸＹ座標平面であるグリッド・グラフにおける自装置の座標を決定し、前記トポロジ情報に基づき、自装置の座標とＸ軸方向及びＹ軸方向で隣接する座標に対応するノード装置を決定し、決定したノード装置に決定した座標を通知することで、前記リッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応するノード装置であるグリッド・ノード装置の決定を開始する開始手段と、
前記グリッド・グラフに含まれる他のグリッド・ノード装置に、自装置の座標及び位置情報を通知する通知手段と、
を備えており、
前記グリッド・ノード装置のそれぞれは、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置と、Ｙ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できないことを特徴とする第２のノード装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ノード装置が自己の設置位置を推定する技術に関する。
【背景技術】
【０００２】
ある地理的領域に、多数のセンサ機能を有するノード装置（以下、単にノードと呼ぶ。）を設置し、ノードが測定する、例えば、温度や湿度等のセンサ情報を、ノードの設置位置に対応づけて取得するセンサ・ネットワークを考える。なおノードの数は非常に多いため、測定者がＧＰＳ受信機等を用いて総てのノードの設置位置を測定して各ノードに設定することを避けたいものとする。
【０００３】
この場合、例えば、ノードを設置する領域が屋外のみであれば、ＧＰＳ等を利用した位置情報の取得機能を各ノードに設けることで、各ノードは、位置情報を容易に取得することができる。しかしながら、各ノードに位置情報の取得機能を実装する必要がありコストが高くなる。また、ノードの一部を屋内に設置しなければならない場合、屋内に設置するノードは、位置情報が取得できないという問題が生じる。
【０００４】
このため、アンカ・ノード又はランドマーク・ノードと呼ばれる一部のノードに位置情報の取得機能を設ける、或いは、測定者が測定した位置情報を設定し、他のノードは、近傍のノードとの接続関係、つまり、トポロジ情報を用いて自装置の位置を推定する手法が提案されている。なお、これら手法は大きく、レンジ・ベース（Ｒａｎｇｅ−Ｂａｓｅｄ）な手法とレンジ・フリー（Ｒａｎｇｅ−Ｆｒｅｅ）な手法の２つに分けられる。レンジ・ベースな手法は、ノードが他のノードとの物理的距離を測定することを含む手法である。これに対して、レンジ・フリーな手法は、他のノードとの物理的距離を測定せず、トポロジ情報のみから位置を推定する手法であり、ノードの構成を簡略化できるという利点がある。例えば、レンジ・フリーな手法は、非特許文献１から５に記載されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】Ｈ．Ｃｈｅｎ，ｅｔ  ａｌ．，"Ａｎ  Ｉｍｐｒｏｖｅｄ  ＤＶ−Ｈｏｐ  Ｌｏｃａｌｉｚａｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  Ｗｉｒｅｌｅｓｓ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋｓ，"Ｉｎ  Ｐｒｏｃ．  ｏｆ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ａｃｑｕｉｓｉｔｉｏｎ，ｐｐ．６３８−６４３，２００６年
【非特許文献２】Ｒ．Ｎａｇｐａｌ，ｅｔ  ａｌ．，"Ｏｒｇａｎｉｚｉｎｇ  ａ  Ｇｌｏｂａｌ  Ｃｏｏｒｄｉｎａｔｅ  Ｓｙｓｔｅｍ  ｆｒｏｍ  Ｌｏｃａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  ｏｎ  ａｎ  Ａｄ  Ｈｏｃ  Ｓｅｎｓｏｒ  Ｎｅｔｗｏｒｋ，"Ｉｎ  Ｐｒｏｃ.  ｏｆ  ＡＣＭ  ＩＰＳＮ，２００３年
【非特許文献３】Ｄ.  Ｎｉｃｕｌｅｓｃｕ，ｅｔ  ａｌ．，"Ａｄ  Ｈｏｃ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ（ＡＰＳ），"Ｉｎ  Ｐｒｏｃ.  ｏｆ  ＩＥＥＥ  ＧＬＯＢＥＣＯＭ  ２００１，ｐｐ.２９２６−２９３１，２００１年
【非特許文献４】Ｎ.  Ｂｕｌｕｓｕ，ｅｔ  ａｌ．，"ＧＰＳ−ｌｅｓｓ  Ｌｏｗ  Ｃｏｓｔ  Ｏｕｔｄｏｏｒ  Ｌｏｃａｌｉｚａｔｉｏｎ  Ｆｏｒ  Ｖｅｒｙ  Ｓｍall  Ｄｅｖｉｃｅｓ，"ＩＥＥＥ  Ｐｅｒｓｏｎａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｖｏｌ.７，Ｉｓｓｕｅ  ５，ｐｐ.２８−３４，２０００年
【非特許文献５】Ｙ.Ｓｈａｎｇ, ｅｔ  ａｌ．，"Ｌｏｃａｌｉｚａｔｉｏｎ  ｆｒｏｍ  Ｍｅｒｅ  Ｃｏｎｎｅｃｔｉｖｉｔｙ，"Ｉｎ  Ｐｒｏｃ.  ｏｆ  ＡＣＭ  ＭｏｂｉＨｏｃ，２００３年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、非特許文献１から３に記載の手法は、ノードが設置されている領域が非凸包形状である場合、位置推定誤差が非常に大きくなるという問題がある。なお非凸包形状とは、領域内の任意の２点を直線で結ぶときに、直線の一部が領域外にはみ出ることがある形状である。非特許文献４に記載の手法は、ノードの設置領域が非凸包形状であっても問題は発生しないが、アンカ・ノードから１ホップの距離、つまり、アンカ・ノードと直接通信できないと位置が推定できないため、多数のアンカ・ノードが必要になるという問題がある。また、非特許文献５に記載の手法は、センサ・ネットワーク全体のトポロジ情報を１つのサーバに集めて位置の推定を行うものであるため、ノード数が多くなると、サーバがトポロジ情報を収集することによるトラフィック負荷や、サーバでの計算負荷が膨大になるという問題がある。
【０００７】
本発明は、上述した問題の少なくとも１つを解決するノード装置の設置位置の推定方法と、設置位置を推定するノード装置を提供するものである。
【課題を解決するための手段】
【０００８】
本発明の一態様によると、設置位置の位置情報を保持しない第１のノード装置と設置位置の位置情報を保持する第２のノード装置をそれぞれ複数含み、各ノード装置は別のノード装置と無線により通信するシステムにおいて、前記第１のノード装置が設置位置を推定する方法であって、各ノード装置が自装置を広告することで、自装置と直接通信できる別のノード装置を識別し、各ノード装置が前記識別した直接通信できる別のノード装置を示す情報を広告することで、各ノード装置において、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成ステップと、各ノード装置が生成したトポロジ情報に基づき、前記第２のノード装置に関連するＸＹ座標平面であるグリッド・グラフに含まれるノード装置であるグリッド・ノード装置を決定する決定ステップであって、当該第２のノード装置を含む当該グリッド・ノード装置は、当該グリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応する、決定ステップと、前記グリッド・ノード装置に含まれる各第１のノード装置に、前記グリッド・ノード装置に含まれる各第２のノード装置が、その位置情報及び座標を通知する通知ステップと、前記グリッド・ノード装置に、その座標が一直線に並ばない３つの第２のノード装置が含まれている場合、前記グリッド・ノード装置に含まれる各第１のノード装置が、自装置の座標と、前記３つの第２のノード装置の位置情報及び座標に基づき、自装置の設置位置を推定する第１の推定ステップと、を含み、前記グリッド・ノード装置のそれぞれは、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置と、Ｙ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できないことを特徴とする。
【０００９】
本発明の一態様によると、設置位置の位置情報を保持しない第１のノード装置と設置位置の位置情報を保持する第２のノード装置をそれぞれ複数含み、各ノード装置は別のノード装置と無線により通信するシステムで使用する前記第１のノード装置であって、自装置の存在を広告し、別のノード装置から広告を受信することで、自装置と直接通信できる別のノード装置を識別する識別手段と、前記識別した直接通信できる別のノード装置を示す隣接情報を広告し、別のノード装置が広告する前記隣接情報を受信することで、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成手段と、前記トポロジ情報に基づき、自装置が前記第２のノード装置に関連するＸＹ座標平面であるグリッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応するノード装置であるグリッド・ノード装置であるか否かを判定する判定手段と、前記グリッド・ノード装置であると判定すると、前記グリッド・ノード装置に、その座標が一直線に並ばない３つの第２のノード装置が含まれているかを判定し、含まれている場合、自装置の座標と、前記３つの第２のノード装置の位置情報及び座標に基づき、自装置の設置位置を推定する第１の推定手段と、を備えており、前記グリッド・ノード装置のそれぞれは、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置と、Ｙ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できないことを特徴とする。
【００１０】
本発明の一態様によると、設置位置の位置情報を保持しない第１のノード装置と設置位置の位置情報を保持する第２のノード装置をそれぞれ複数含み、各ノード装置は別のノード装置と無線により通信するシステムで使用する前記第２のノード装置であって、自装置の存在を広告し、別のノード装置から広告を受信することで、自装置と直接通信できる別のノード装置を識別する識別手段と、前記識別した直接通信できる別のノード装置を示す隣接情報を広告し、別のノード装置が広告する前記隣接情報を受信することで、自装置と２ホップ以内で接続するノード装置とのトポロジ情報を生成する生成手段と、自装置に関連するＸＹ座標平面であるグリッド・グラフにおける自装置の座標を決定し、前記トポロジ情報に基づき、自装置の座標とＸ軸方向及びＹ軸方向で隣接する座標に対応するノード装置を決定し、決定したノード装置に決定した座標を通知することで、前記リッド・グラフの座標（ｘ，ｙ）（ここで、ｘ及びｙは整数）に対応するノード装置であるグリッド・ノード装置の決定を開始する開始手段と、前記グリッド・グラフに含まれる他のグリッド・ノード装置に、自装置の座標及び位置情報を通知する通知手段と、を備えており、前記グリッド・ノード装置のそれぞれは、Ｘ軸方向で隣接する座標に対応するグリッド・ノード装置と、Ｙ軸方向で隣接する座標に対応するグリッド・ノード装置とは双方向で直接通信でき、Ｘ軸方向及びＹ軸方向で隣接する座標以外の座標に対応するグリッド・ノード装置とは直接通信できないことを特徴とする。
【発明の効果】
【００１１】
中央で計算するサーバを必要とせず、ノードの設置領域が非凸包形状であっても位置推定誤差を抑えることができ、アンカ・ノードの数を抑えることができる。
【図面の簡単な説明】
【００１２】
【図１】一実施形態によるグリッド・グラフを示す図。
【図２】トポロジ情報の説明図。
【図３】ユニット・グリッドを示す図。
【図４】ユニット・グリッドの説明図。
【図５】ユニット・スコアの説明図。
【図６】一実施形態によるグリッド・グラフの座標に対応するノードの決定の説明図。
【図７】一実施形態によるグリッド・グラフの座標に対応するノードの決定の説明図。
【図８】一実施形態によるグリッド・グラフの座標に対応するノードの決定の説明図。
【図９】一実施形態においてグリッド・グラフの座標に決定したノード装置が広告するグリッド・グラフ情報を示す図。
【図１０】一実施形態においてグリッド・グラフの座標に決定したノード装置が広告するグリッド・グラフ情報を示す図。
【図１１】一実施形態においてグリッド・グラフの座標に決定したノード装置が広告するグリッド・グラフ情報を示す図。
【発明を実施するための形態】
【００１３】
以下、本発明の例示的な実施形態について図面を参照して説明する。なお、以下の各図において、実施形態の説明に必要ではない構成要素については図から省略する。
【００１４】
まず、本発明の概略について説明する。なお、以下の説明において、自装置の設置位置の位置情報、例えば、緯度及び経度を保持しているノードをアンカ・ノードと呼ぶ。位置情報は、アンカ・ノードがＧＰＳ等を利用して取得したものであっても、測定者がアンカ・ノードに設定したものであっても良い。
【００１５】
図１は、設置されているノードＡ〜Ｚと、図では点線及び実線で示すノード間の無線リンクを示している。つまり、点線及び実線で結ばれている２つのノードは、無線により直接通信できることを示している。なお、図１は簡略化のため２６個のノードのみを示しているが、実際には各ノードが数十程度の隣接ノード、つまり、直接通信できるノードを有している。各ノードは周期的に自装置が持つ情報を無線信号でブロードキャスト、つまり広告し、また他のノードがブロードキャスト、つまり、広告する情報を受信することで、１ホップで通信できるノード、つまり、隣接ノードと、２ホップで通信できるノード、つまり隣接ノードの隣接ノードを認識する。なお、本実施形態において、各ノード装置の通信可能距離、つまり、無線信号の最大到達距離に大きな違いはなく、受信機の能力にも大きな違いはないものとする。
【００１６】
その状態において、１つのアンカ・ノードを基準又は起点として、図１の実線で結ばれたノードの様に、所定の条件を満たすノードを選択する。この１つのアンカ・ノードを基準として選択した所定の条件を満たすノードの集合を、以下ではグリッド・グラフと呼ぶものとする。また、グリッド・グラフの基準となるノード、つまり、グリッド・グラフ形成のトリガとなったノードがノードＦである場合、そのグリッド・グラフを"グラフＦ"と呼ぶものとする。さらに、以下の説明では、グリッド・グラフに含まれているノードをグリッド・ノードと呼び、それ以外のノードを非グリッド・ノードと呼ぶものとする。
【００１７】
グリッド・グラフは、ＸＹ座標平面に対応させられ、各グリッド・ノードは座標（ｘ，ｙ）、ここで、ｘ及びｙは整数、に対応させられる。以下の説明において、グリッド・グラフの基準となるアンカ・ノードは、当該グリッド・グラフの原点に対応するノードであるものとする。これは説明を簡単にするためであり、グリッド・グラフの基準となるアンカ・ノードの座標は原点以外とすることもできる。例えば、図１のノードＦを基準とするグラフＦにおいて、横方向をＸ軸方向として、上方向をＹ軸方向とすると、ノードＦは、（０，０）であり、ノードＧは、（１，０）であり、ノードＢは、（０，１）であり、ノードＪは（０，−１）の座標に対応する。本実施形態において、グリッド・ノードとなる条件は、Ｘ軸方向で隣接する座標に対応するノード装置が存在するのであれば、このＸ軸方向で隣接する座標のノード装置とは双方向リンクを有し、Ｙ軸方向で隣接する座標に対応するノード装置が存在するのであれば、このＹ軸方向で隣接する座標のノード装置とは双方向リンクを有し、Ｘ軸方向でもＹ軸方向でも隣接しない座標に対応する他のノード装置とはリンクを有さないことである。この条件により、各座標に対応するグリッド・ノード装置の実際の位置は、概ね座標に沿った配置とすることができる。
【００１８】
そして、例えば、グラフＦの中の少なくとも３つのグリッド・ノードがアンカ・ノードであると、この３つのアンカ・ノードの位置情報及びグラフＦでの座標と、各ノードの座標により、アンカ・ノード以外の各グリッド・ノードは、自装置の位置、つまり、緯度及び経度を推定することができる。そして、アンカ・ノード以外の各グリッド・ノードは、推定した自装置の位置情報を広告し、アンカ・ノードは保持している自装置の位置情報を広告する。非グリッド・ノードは、その信号を直接受信できるグリッド・ノードが広告する位置情報に基づき自装置の設置位置を推定することができる。
【００１９】
なお、各アンカ・ノードは、それぞれが原点となってグリッド・グラフを形成するため、理論的には最大で、アンカ・ノードと同じ数のグリッド・グラフが形成されることになる。ここで、複数のグリッド・グラフが形成され、各グリッド・グラフに少なくとも３つのアンカ・ノードが含まれていると、複数のグリッド・グラフに属するグリッド・ノードは、それぞれのグリッド・グラフに対して推定位置を計算することになる。なお、通常、これら複数の推定位置は異なる。本実施形態において、複数のグリッド・グラフに属するグリッド・ノードは、複数の推定位置の重心位置を自装置の位置として使用する。なお、アンカ・ノードは、常に、自装置が保持する位置情報を自装置の位置情報として使用する。つまり、位置の推定は行わない。さらに、いずれのグリッド・グラフにも属さない非グリッド・ノードは、アンカ・ノードが広告する位置情報と、各グリッド・ノードが推定して広告する位置情報から自装置の位置情報を推定する。
【００２０】
以下、本実施形態の詳細について説明する。本実施形態において各ノードは、手順１から手順８の８つの手順を１ターンとして、定期的に１つのターンを実行する。
【００２１】
＜手順１＞
まず、手順１において各ノードは、広告のための種々の情報を含むパケットを無線信号でブロードキャストする。具体的には、このパケットは、広告元のノードの識別子に加えて、広告したノードが保持する、隣接ノード情報と、隣接スコア情報と、グリッド・グラフ情報と、設置位置の位置情報を含んでいる。なお、パケットに含まれるこれら情報の詳細については後述する。ここで、最初に各ノードを設置したときにおいて、アンカ・ノードは、位置情報を有しているが、他の情報、つまり、隣接ノード情報と、隣接スコア情報と、グリッド・グラフ情報を保持してはいない。さらに、アンカ・ノード以外のノードは、いずれの情報も保持してはいない。各ノードは、周期的に広告を行うが、広告するパケットには、広告時に保持している情報のみを含める。つまり、例えば、設置時においては、自装置の存在を通知する目的のみで、上記いずれの情報も含ないパケットをブロードキャストする。各ノードは、その後、別のノードからの広告を受信することで、隣接ノード情報を生成すると、次に送信するパケットには、隣接ノード情報を含め、その後、別のノード装置から隣接スコア情報を取得すると、次に送信するパケットには隣接ノード情報と隣接スコア情報を含める。この様にして、グリッド・ノードは、隣接ノード情報と、隣接スコア情報と、グリッド・グラフ情報と、位置情報を最終的に広告する様になる。手順１において、各ノードは、他のノードに広告のためのパケットを送信すると共に、他のノードが広告するパケットを受信し、処理待ちパケットに格納する。
【００２２】
＜手順２＞
手順２において、各ノードは、直接信号を受信できる別のノードから受信する隣接ノード情報に基づき、自装置から２ホップまでのノードについてのトポロジ情報を生成する。例えば、ノードＡからＩ及びＺが図２（Ａ）の様に接続しているものとする。なお、図２（Ａ）において矢印の方向は通信可能な方向を示している。例えば、ノードＦからノードＺへの片方向の矢印は、ノードＦの信号はノードＺには届くが、ノードＺの信号はノードＦには届いていないことを示している。また、ノードＺとノードＨの双方向の矢印は、ノードＺの信号をノードＨは受信でき、ノードＨの信号をノードＺは受信できることを示している。
【００２３】
例えば、ノードＺは、ノードＢ、Ｄ、Ｅ、Ｊ、Ｈ、Ｆから信号を受信できるため、ノードＢ、Ｄ、Ｅ，Ｊ、Ｈ、ＦからノードＺ方向へのリンクが存在することを認識する。したがって、ノードＢ、Ｄ、Ｅ、Ｊ、Ｈ、ＦからノードＺ方向へのリンクが存在することを示す隣接ノード情報を広告する。また、ノードＢは、ノードＺからの信号を受信できるため、ノードＢが広告する隣接ノード情報は、ノードＢがノードＺからの信号を受信できることを示している。したがって、ノードＺは、ノードＢとは双方向のリンクで接続していることを認識する。同様に、ノードＢはノードＤと双方向のリンクで接続していることを認識するため、ノードＢが広告する隣接ノード情報は、ノードＢとノードＤが双方向のリンクで結ばれていることを示し、よって、ノードＺは、ノードＢとノードＤとの間の双方向のリンクを認識する。さらに、ノードＺは、ノードＨとも双方向のリンクで接続していることを認識し、さらに、ノードＨが広告する隣接ノード情報は、ノードＨがノードＩからの信号を受信できることを示しているため、ノードＺは、ノードＩからノードＨへの片方向リンクが存在することを認識する。
【００２４】
なお、ノードＡにノードＺの信号は届くが、ノードＺにノードＡの信号は届かない。したがって、ノードＺは、ノードＡの存在を認識しない。よって、図２（Ａ）に示す接続状態であると、ノードＺは、最終的に、２ホップ以内のノードのトポロジ情報として、図２（Ｂ）に示す情報を生成する。図２（Ｂ）は、行に示すノードから例に示すノード方向のリンクが存在する場合を１で示している。なお、図２（Ｂ）において、ノードＡ、Ｃ及びＧがないのは、ノードＺはノードＡ及びＣを認識できず、ノードＧは、３ホップ先のノードであるからである。例えば、ノードＺは、図２（Ｂ）に示す自装置と１ホップで通信できるノードと、当該ノードとのリンクの種別、つまり、片方向であるか双方向であるかを示す情報を隣接ノード情報として広告する。また、自分自身から自分自身へのリンクは考慮しないため、０とする。なお、本実施形態において、各ノードは隣接するノードについての情報のみを隣接ノード情報として広告するが、２ホップ以内で接続する総てのノードを広告する等、最終的に２ホップ以内のノードとの接続関係を認識できる任意の方法を使用することができる。
【００２５】
＜手順３＞
続いて、手順３において各ノードは、２ホップ以内のトポロジ情報に基づきユニット・グリッドを探索する。ここで、ユニット・グリッドには、図３（Ａ）から（Ｄ）に示す４つの種別が存在する。なお、図３において、"自"と記載されたノードは、ユニット・グリッドを探索しているノードである。各ノードは、まず、図３（Ａ）に示すＴｙｐｅ１の条件を満たす自装置を含む９つのノードの組が存在するか否かを判定し、存在する場合には、Ｔｙｐｅ１の条件を満たす総ての組を特定する情報を保存して探索を終了する。一方、Ｔｙｐｅ１の条件を満たす組が存在しない場合には、Ｔｙｐｅ２の条件を満たす自装置を含む８つのノードの組が存在するか否かを判定する。以後、同様に、Ｔｙｐｅ２の条件を満たす組が存在しない場合には、Ｔｙｐｅ３の条件を満たす自装置を含む６つのノードの組が存在するか否かを判定し、存在しない場合には、Ｔｙｐｅ４の条件を満たす自装置を含む４つのノードの組が存在するか否かを判定する。
【００２６】
Ｔｙｐｅ１のユニット・グリッドの条件は、ユニット・グリッドを探索しているノードを直交座標の原点とすると、座標（０，０）、（１，０）、（０，１）、（−１，０）、（０，−１）、（１，１）、（１，−１）、（−１，１）、（１，１）の計９つの座標に対応するノードは、各軸方向で隣接する座標に対応するノードとは双方向リンクで結ばれるが、各軸方向において隣接しない座標に対応するノード間にはリンクが存在しないことである。図３（Ａ）において、ノードＢがノードＡやノードＬとリンクを持つ場合にはユニット・グリッドの条件を満たさないことになる。なお、ユニット・グリッド以外のノードとはリンクを持つことができる。つまり、図３（Ａ）には示していないノードＺが存在し、ノードＺがノードＢとノードＫとリンクを持っていたとしても問題ない。なお、Ｔｙｐｅ２の条件は、Ｔｙｐｅ１での座標（１，−１）を除いた以外はＴｙｐｅ１と同じである。同様に、なお、Ｔｙｐｅ３の条件は、Ｔｙｐｅ２での座標（０，−１）、（−１，−１）を除いた以外はＴｙｐｅ２同じであり、Ｔｙｐｅ４の条件は、Ｔｙｐｅ３での座標（−１，０）、（−１，１）を除いた以外はＴｙｐｅ３同じである。
【００２７】
各ノードは、ユニット・グリッドが見つかった場合、ユニット・グリッドに含まれるノードを図３（Ｅ）に示す配列ｇ０〜ｇ９に対応づけて保存する。なお、Ｔｙｐｅ２〜４の場合には、存在しない座標に対応する配列の要素には値が設定されない。なお、ユニット・グリッドは、その位置関係のみが重要であり、あるユニット・グリッドと、線対称であるものや、あるユニット・グリッドを回転させたものは総て同じものとしてあつかう。つまり、図４（Ａ）に示すノードの集合がユニット・グリッドとして選択された場合、図４（Ａ）の配置に対して、垂直方向の軸対象（図４（Ｂ））、水平方向の軸対象（図４（Ｃ））、９０°回転（図４（Ｄ））した集合は、図４（Ａ）のユニット・グリッドと同じものである。
【００２８】
＜手順４＞
手順４において、各ノードは、手順３で探索した各ユニット・グリッドのユニット・スコアを算出する。以下の説明において、ユニット・グリッドを探索したノードをユニット・グリッドの基準ノードと呼び、ユニット・グリッドの基準ノードの隣接ノードを１ホップ・ノードと呼び、ユニット・グリッドの基準ノードから２ホップで接続するノードを２ホップ・ノードと呼ぶものとする。例えば、図５（Ａ）のユニット・グリッドの基準ノードはノードＺであり、１ホップ・ノードはノードＡ、Ｂ、Ｃ及びＤであり、２ホップ・ノードはノードＫ、Ｌ、Ｍ及びＮである。
【００２９】
ユニット・スコアは、ユニット・グリッドの１ホップ・ノードのノード・スコアの合計値である。ここで、ノード・スコアとは、ユニット・グリッドのノードが、他のノードにおいてユニット・グリッドの１ホップ・ノードとして選択されている回数である。このノード・スコアの計算のため、各ノードは、隣接スコア値をパケットに含めて広告する。例えば、ノードＺが図５（Ａ）〜（Ｃ）に示す様に３つのユニット・グリッドを探索して保持しているものとする。この場合、ノードＡ、Ｂ及びＤは、総てのユニット・グリッドに含まれているので、ノードＡ、Ｂ及びＤの隣接スコア値は３である。一方、ノードＥは、２つのユニット・グリッドに含まれているので、ノードＥの隣接スコア値は２である。さらに、ノードＣは、１つのユニット・グリッドに含まれているので、ノードＣの隣接スコア値は１である。この場合、ノードＺは、上記各ノードの隣接スコア値を含む隣接スコア情報を広告する。
【００３０】
各ノードは、別のノードが広告する隣接スコア情報に基づきユニット・グリッドの１ホップ・ノードのノード・スコア値を算出する。例えば、ノードＺが、あるノードからノードＡの隣接スコア値が３であると受信し、さらに別のノードからノードＡの隣接スコア値が４であると受信すると、ノードＡのノード・スコア値は７となる。そして、ノードＡ、Ｂ、Ｃ、Ｄのノード・スコア値がそれぞれ、７、３、２、１であると、図５（Ａ）のユニット・グリッドのユニット・スコアは７＋３＋２＋１＝１３となる。また、さらに、ノードＥのノード・スコアが３であると、図５（Ｂ）及び（Ｃ）のユニット・スコアは１４となる。
【００３１】
＜手順５＞
続いて、手順５について説明する。手順５は、各アンカ・ノードがそれぞれ独立にその処理を開始し、各アンカ・ノードを起点、本実施形態では原点とする図１に示すグリッド・グラフを形成する処理のトリガである。つまり、各アンカ・ノードに関連するグリッド・グラフの座標（ｘ，ｙ）、ここでｘ及びｙは整数、に対応させるノードを決定する処理のトリガである。ただし、すでに自身を原点とするグリッド・グラフを形成済みであれば、手順５をスキップする。
【００３２】
手順５において、各アンカ・ノードは、ユニット・スコア値の一番高いユニット・グリッドを選択する。なお、ユニット・スコア値の一番高いユニット・グリッドが複数ある場合には、その中から任意の１つを選択する。そして選択したユニット・グリッドに基づきグリッド・グラフ情報を生成し、生成したグリッド・グラフ情報を広告する。なお、以下の説明においては、グリッド・グラフの形成に係る総てのノードが図３（Ａ）に示すＴｙｐｅ１のユニット・グリッドを保持しているものとし、Ｔｙｐｅ２〜４の場合については最後に、Ｔｙｐｅ１との違いを説明する。
【００３３】
図６（Ａ）は、アンカ・ノードであるノードＺがグラフＺを形成するために１つのユニット・グリッドを選択した場合を示している。１つのユニット・グリッドを選択することで、選択したユニット・グリッドの１ホップ・ノードがグラフＺのグリッド・ノードに決定される。また、このときノードＺは、選択したユニット・グリッドの１ホップ・ノードそれぞれのグラフＺの座標も決定する。なお、座標の決定においては、ユニット・グリッドの位置関係に従う。例えば、図６（Ａ）において、ノードＺは、ノードＤ、Ａ、Ｂ、Ｃを、それぞれ、座標（１，０）、（０，１）、（−１，０）、（０，−１）に対応するノードに決定している。なお、ユニット・グリッドは、基準ノードとの相対的な関係のみが重要であるので、ノードＺは、座標（１，０）、（０，１）、（−１，０）、（０，−１）に対応するノードを、例えば、ノードＡ、Ｂ、Ｃ、Ｄと決定することもできる。さらに、ノードＺは、座標（１，０）、（０，１）、（−１，０）、（０，−１）に対応するノードを、例えば、ノードＢ、Ａ、Ｄ、Ｃに決定することもできる。つまり、ノードＺは、選択したユニット・グリッドの１ホップ・ノードの座標を、ノードＺを中心とする位置関係に従う範囲において自由に決定できる。
【００３４】
図９（Ａ）は、ノードＺが図６（Ａ）に示す様に決定したグリッド・ノードを広告するためのグリッド・グラフ情報を示している。グリッド・グラフ情報の起点フィールドは、形成するグリッド・グラフに関連するアンカ・ノードの識別子を示している。つまり、グラフＺの形成のためのグリッド・グラフ情報の起点フィールドには常にノードＺの識別子が設定される。シーケンス・フィールドには、グラフＺの形成を開始するごとにノードＺが割り当てる番号が設定される。つまり、あるグラフＺの作成において、起点フィールド及びシーケンス・フィールドに設定されている値は常に同じとなる。したがって、以下の説明において、起点フィールドとシーケンス・フィールドの再度の説明は省略する。なお、ノードＺが既存のグラフＺを解放し、新たにグラフＺの作成を開始すると、グリッド・グラフ情報のシーケンス・フィールドの値が更新される。
【００３５】
ノードＺが広告するグリッド・グラフ情報の座標フィールドには、当該グリッド・グラフ情報を広告したノードの座標が設定される。つまり図９（Ａ）のグリッド・グラフ情報においては、ノードＺの座標（０，０）が設定される。ユニット・フィールドには、選択したユニット・グリッドの１ホップ・ノードの識別子を所定の順番で設定する。本実施形態では、当該グリッド・グラフ情報を広告しているノードの座標に対して、Ｙ座標の値を１だけ減じたノード（以後、−ｙと表示。）、Ｘ座標の値を１だけ減じたノード（以後、−ｘと表示。）、Ｘ座標の値を１だけ増加させたノード（以後、＋ｘと表示。）、Ｙ座標の値を１だけ増加させたノード（以後、＋ｙと表示。）の順で設定する。図６（Ａ）において、ノードＺは、ノードＣを座標（０，−１）とし、ノードＢを座標（−１，０）とし、ノードＤを座標（１，０）とし、ノードＡを座標（０，１）としている。したがって、図９（Ａ）に示す様に、ユニット・フィールドにはノードＣ、Ｂ、Ｄ、Ａの順に記載される。また、ユニット・フィールドには、ユニット・グリッドのユニット・スコア値も設定される。例えば、図６（Ａ）では、ノードＣ、Ｂ、Ｄ、Ａが属するユニット・グラフのユニット・スコア値として"５"が設定されている。
【００３６】
アンカ情報フィールドには、当該グリッド・グラフに含まれるアンカ・ノードについて、ノードの識別子と、当該アンカ・ノードが保持する位置情報と、当該アンカ・ノードのＸＹ座標が設定される。ノードＺは、アンカ・ノードであるので、アンカ情報フィールドには、ノードＺの識別子と、ノードＺの位置情報と、ノードＺの座標である（０，０）が設定される。なお、ステージ・フィールドには"決定"が設定される。これは、ユニット・フィールドのノードがグラフＺのグリッド・ノードに決定されたことを示している。図９（Ａ）に示すグリッド・グラフ情報を含むパケットは、ノードＺからの信号を直接受信できる総てのノードが受信するが、ユニット・フィールド及びステージ・フィールドの情報から、ノードＡ〜Ｄは、自装置がグラフＺのグリッド・ノードにて選択されたことと、その座標を知る。
【００３７】
＜手順６＞
本手順において、手順５で決定したグリッド・グラフの原点に隣接する座標のノードを軸に、当該グリッド・グラフを拡張させる。なお、既に説明した様に、グリッド・グラフの座標に対応させるノードは、Ｘ軸方向で隣接する座標に対応するノード装置が存在するのであれば、このＸ軸方向で隣接する座標のノード装置とは双方向リンクを有し、Ｙ軸方向で隣接する座標に対応するノード装置が存在するのであれば、このＹ軸方向で隣接する座標のノード装置とは双方向リンクを有し、Ｘ軸方向でもＹ軸方向でも隣接しない座標に対応する他のノード装置とは双方向リンクを有することが無いノードである。
【００３８】
手順５でアンカ・ノードであるノードＺから、それぞれ、座標（１，０）、（０，１）、（−１，０）、（０，−１）となったことを通知されたノードＤ、Ａ、Ｂ、Ｃは、既に決定した座標のノードとの位置関係を制約条件とし、この制約条件を満たすユニット・グリッドを判定し、制約条件を満たす総てのユニット・グリッドの１ホップ・ノードを含むグリッド・グラフ情報を広告する。なお、ユニット・グラフ探索時には座標を固定していないため、図３（Ｅ）に示す配列として記憶したユニット・グラフそのままの状態だけではなく、各ノードは、これを回転させ、Ｙ軸対称に反転させ、Ｘ軸対称に反転させて、制約条件を満たすユニット・グラフを探索する。
【００３９】
例えば、ノードＤにとっての制約条件は、ノードＺが１ホップ・ノードの１つであり、ノードＺ経由の２ホップ・ノードがノードＡ及びＣであることが制約条件となる。このノードＤの制約条件を満たす、ノードＤを基準ノードとするユニット・グリッドが図７（Ａ）〜（Ｃ）の３つであるものとする。なお、図７及び図８において網掛けのノードは、ノードＺによりその座標が決定されているノードを示している。この場合、ノードＤが広告するグリッド・グラフ情報を図９（Ｂ）に示す。図９（Ｂ）のグリッド・グラフ情報の座標フィールドには、ノードＤの座標である（１，０）が設定され、ステージ・フィールドには、"正側"が設定される。なお、ステージ・フィールドの意味については後述する。さらに、ユニット・フィールドには、制約条件を満たす３つのユニット・グリッドの１ホップ・ノードを、制約条件を満たす座標に従い記述する。例えば、図７（Ａ）のユニット・グリッドにおいて、基準ノードであるノードＤの−ｙ方向のノードはノードＦであり、−ｘ方向のノードはノードＺであり、＋ｘ方向のノードはノードＨであり、＋ｙ方向のノードはノードＥであるため、ノードＦ、Ｚ、Ｈ、Ｅの順で図７（Ａ）のユニット・グリッドが記載されている。また、ユニット・グリッドのユニット・スコアも記載する。例えば、図７（Ａ）のユニット・グリッドのユニット・スコアは１２となっている。なお、複数のユニット・グリッドがあり、その１ホップ・ノードが同じである場合には、２ホップ・ノードが異なったとしても、ユニット・フィールドに記載される情報は同じであるため、これらの情報は１つに纏める。
【００４０】
同様に、ノードＡに対する制約条件を満たす、ノードＡを基準ノードとするユニット・グリッドが図７（Ｄ）〜（Ｅ）の２つであり、ノードＣに対する制約条件を満たす、ノードＣを基準ノードとするユニット・グリッドが図８（Ａ）〜（Ｂ）の２つであり、ノードＢに対する制約条件を満たす、ノードＢを基準ノードとするユニット・グリッドが図８（Ｃ）〜（Ｄ）の２つであるものとする。この場合、ノードＤと同様に、ノードＡ、Ｃ、Ｂは、それぞれ、図９（Ｃ）、（Ｄ）、（Ｅ）に示すグリッド・グラフ情報を広告することになる。なお、当然ではあるが、広告しているノードは、パケットの送信元アドレスから特定される。
【００４１】
続いて、グリッド・グラフ情報のステージ・フィールドについて説明する。本実施形態において、グリッド・ノードのうち、Ｘ軸又はＹ軸上のノードを軸ノードと呼び、グリッド・ノードの軸ノード以外のノードを軸外ノードと呼ぶものとする。ステージ・フィールドが"決定"であるグリッド・グラフ情報は、軸ノードの決定を通知している。ステージ・フィールドが"決定"であるグリッド・グラフ情報を受信することで、自装置が軸ノードに選択されたことを知ったノードは、上述した様にステージ・フィールドが"正側"であるグリッド・グラフ情報を広告する。これは、グリッド・グラフ情報を広告しているノードがＸ軸上の軸ノードである場合、その軸ノードの＋ｙ方向のノードを決定するためのグリッド・グラフ情報であることを示している。一方、グリッド・グラフ情報を広告しているノードがＹ軸上の軸ノードである場合、その軸ノードの＋ｘ方向のノードを決定するためのグリッド・グラフ情報であることを示している。
【００４２】
つまり、図９（Ｂ）のグリッド・グラフ情報を送信するノードＤは、Ｘ軸の軸ノードであるため、図９（Ｂ）のグリッド・グラフ情報は、+ｙ方向の座標、つまり、座標（１，１）のノードを決定するためのものであることがわかる。同様に、図９（Ｃ）のグリッド・グラフ情報を送信するノードＡは、Ｙ軸の軸ノードであるため、図９（Ｃ）のグリッド・グラフ情報は、+ｘ方向の座標、つまり、座標（１，１）のノードを決定するためのものであることがわかる。ここで、グリッド・グラフにおいて、原点に１ホップだけ近づくノードを上流側ノードと呼び、原点から１ホップだけ遠くなるノードを下流側ノードと呼ぶものとする。座標（１，１）の様に、軸外ノードは２つの上流ノードを持ち、グリッド・グラフを拡張するためには、この２つの上流ノードのユニット・グラフを調整しながら決定しなければならない。具体的には、ノードＤが基準ノードであるユニット・グラフのうち、図７（Ｃ）に示すユニット・グラフを選択すると、座標（１，１）のノードはノードＫとなるが、この場合、ノードＡが基準ノードであるユニット・グラフ（図７の（Ｄ）、（Ｅ））とは両立せず、第１象限方向へのグリッド・グラフの拡張が停止することになる。一方、図７（Ａ）又はＢに示すユニット・グラフに応じて座標（１，１）のノードをノードＥとすると、ノードＡのユニット・グラフと両立するため、第１象限方向にグリッド・グラフを拡張することができる。
【００４３】
本実施形態では、グリッド・グラフ情報を受信したノードのそれぞれが、送信元ノードの座標と、ステージ・フィールドの値と、ユニット・フィールドの内容に基づき、自装置が軸外ノードであるか否かを判定する。例えば、既に説明した様に、図９（Ｂ）のグリッド・グラフ情報は、Ｘ軸方向の上流側からのものであり、かつ、座標（１，１）のノードを決定するためのものであることがわかる。ここで、ユニット・フィールドの３つのユニット・グラフの＋ｙ方向の位置にあるノードは、ノードＥとＫである。同様に、図９（Ｃ）のグリッド・グラフ情報は、Ｙ軸方向の上流側からのものであり、かつ、座標（１，１）のノードを決定するためのものであることがわかる。ここで、ユニット・フィールドの２つのユニット・グラフの＋ｘ方向の位置にあるノードは、ノードＥのみである。グリッド・ノードに選択されていないノードは、Ｘ軸方向とＹ軸方向の２つの上流側のノードから受信するグリッド・グラフ情報の同じ座標に自装置が指定されている場合、自装置が当該座標の候補であると判定する。本例において候補はノードＥのみであるが、１つのグリッド・グラフ情報には、制約条件を満たす総てのユニット・グリッドの１ホップ・ノード及びユニット・スコア値が設定されるため、候補ノードは、候補ノードが１つであるのか複数あるのかを認識することができる。そして、本例の様に１つしかない場合には、その１つの候補ノードは、自装置が当該座標のノードであると判定し、自装置が当該座標のノードであることを示すグリッド・グラフ情報を広告する。図６（Ｂ）は、グラフＺの座標（１，１）にノードＥが決定された状態を示している。
【００４４】
図９（Ｆ）は、座標（１，１）に決定したノードＥが送信するグリッド・グラフ情報である。図９（Ｆ）に示す様に、座標フィールドには、ノードＥの座標である（１，１）が設定され、ステージ・フィールドには、"下流未定"が設定される。これは、ノードＥの下流側のノード、つまり、座標（１，２）及び（２，１）が現在のところ未定であることを示している。また、ユニット・フィールドには、ノードＥに対してノードＡ、Ｚ、Ｄの位置関係が図６（Ｂ）となる制約条件を満たす、ノードＥを基準ノードとするユニット・グリッドの１ホップ・ノードが、上記と同様に設定される。
【００４５】
なお、２つの上流側ノードから座標（１，１）として指定されたノードが複数ある場合には、ノードが属するユニット・グリッドのスコア値の合計で判定する。例えば、図９（Ｂ）のグリッド・グラフ情報において、ノードＥを含むユニット・グラフのユニット・スコア値の合計は２２であり、図９（Ｃ）のグリッド・グラフ情報においては２２であり、よって、ノードＥについてユニット・スコア値の合計値は４４となる。候補となるノードが他にある場合、ノードＥは、他の候補ノードそれぞれについてもユニット・スコア値の合計を求め、自装置が最高値であるか否かを判定する。最高値であれば、自装置が座標（１，１）のノードとして、グリッド・グラフ情報を広告する。一方、自装置が最高でなければなにもしない。なお、複数のノードのユニット・スコア値の合計が同じであり、かつ、最高である場合には、例えば、ノードの識別子の大小等、その他の予め定めた基準により決定されるノードが当該座標のノードとなる。
【００４６】
ノードＤ及びＡは、図９（Ｆ）に示すグリッド・グラフ情報を受け取ることで、ノードＥが座標（１，１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１０（Ａ）及び（Ｂ）に示す様に変更する。具体的には、ノードＤは、＋ｙ側のノードが確定したことによりステージ・フィールドの値を"負側"に変更する。これは、−ｙ側、つまり、座標（１，−１）のノードを決定することを広告している。また、ノードＥが座標（１，１）との制約条件が増えたことで、図７（Ｃ）のユニット・グリッドはもはや制約条件を満たさないため、図７（Ｃ）のユニット・グリッドに対応する情報をユニット・フィールドから削除する。同様に、ノードＡは、＋ｘ側のノードが確定したことによりステージ・フィールドの値を"負側"に変更する。これは、−ｘ側、つまり、座標（−１，１）のノードを決定することを広告している。なお、ノードＡが広告するユニット・フィールドは、本例では変更が無い。
【００４７】
ノードＤ及びＡがステージ・フィールドの値を"負側"に変更したことで、座標（１，−１）と座標（−１，１）を決定する処理が並行して開始される。まず、座標（１，−１）の決定について説明する。既に説明した様に、図１０（Ａ）のグリッド・グラフ情報は、広告元の座標（１，０）の−ｙ方向の座標、つまり、座標（１，−１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グラフの−ｙ方向の位置にあるノードは、ノードＦとＪである。同様に、図９（Ｄ）のグリッド・グラフ情報は、広告元の座標（０，−１）の＋ｘ方向（ステージ・フィールドが"正側"）の座標、つまり、座標（１，−１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グラフの＋ｘ方向の位置にあるノードは、ノードＦのみである。したがって、ノードＦが座標（１，−１）のノードとなり、ノードＦは図１０（Ｃ）に示すグリッド・グラフ情報を広告する。
【００４８】
続いて、座標（−１，１）の決定について説明する。既に説明した様に、図１０（Ｂ）のグリッド・グラフ情報は、広告元の座標（０，１）の−ｘ方向の座標、つまり、座標（−１，１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グラフの−ｘ方向の位置にあるノードは、ノードＯとＰである。同様に、図９（Ｅ）のグリッド・グラフ情報は、広告元の座標（−１，０）の＋ｙ方向（ステージ・フィールドが"正側"）の座標、つまり、座標（−１，１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グラフの＋ｙ方向の位置にあるノードは、ノードＰのみである。したがって、ノードＰが座標（−１，１）のノードとなり、ノードＰは図１０（Ｄ）に示すグリッド・グラフ情報を広告する。図６（Ｃ）は、ノードＰ及びＦがグリッド・ノードになった状態を示している。
【００４９】
ノードＣは、図１０（Ｃ）のグリッド・グラフ情報を受け取ることで、ノードＦが座標（１，−１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１０（Ｅ）に示す様に変更する。本例においては、ステージ・フィールドの値を"負側"に変更するのみである。同様に、ノードＢは、図１０（Ｄ）のグリッド・グラフ情報を受け取ることで、ノードＰが座標（−１，１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１０（Ｆ）に示す様に変更する。本例においては、ステージ・フィールドの値を"負側"に変更するのみである。
【００５０】
また、ノードＤは、図１０（Ｃ）に示すグリッド・グラフ情報を受け取ることで、ノードＦが座標（１，−１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１１（Ａ）に示す様に変更する。具体的には、グリッド・ノードとなったノードＡ、Ｚ、Ｃ、Ｅ、Ｄ、Ｆを制約条件とすると、選択できるユニット・ノードは図７（Ａ）のみであるため、これにより座標（２，０）のノードをノードＨであると決定する。よって、図１１（Ａ）に示す様に、ステージ・フィールドを"決定"にし、ユニット・フィールドには決定したユニット・ノードの１ホップ・ノードを含むグリッド・グラフ情報を広告する。これにより、ノードＨは自装置が座標（２，０）のノードとなったことを知る。なお、選択できるユニット・ノードが複数ある場合には、ユニット・スコアの一番高いものを選択する。さらに、複数のユニット・ノードのユニット・スコアが同点である場合には、その中から任意の一つを選択する。
【００５１】
同様に、ノードＡは、図１０（Ｄ）に示すグリッド・グラフ情報を受け取ることで、ノードＰが座標（−１，１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１１（Ｂ）に示す様に変更する。具体的には、グリッド・ノードとなったノードＰ、Ａ、Ｅ、Ｂ、Ｚ、Ｄを制約条件とすると、選択できるユニット・ノードは図７（Ｅ）のもののみであるため、これにより座標（０，２）のノードをノードＭであると決定する。よって、図１１（Ｂ）に示す様に、ステージ・フィールドを"決定"にし、ユニット・フィールドには決定したユニット・ノードの１ホップ・ノードを含むグリッド・グラフ情報を広告する。これにより、ノードＭは自装置が座標（０，２）のノードとなったことを知る。図６（Ｄ）は、さらにノードＭ及びＨがグリッド・ノードになった状態を示している。
【００５２】
続いて、座標（−１，−１）の決定について説明する。図１０（Ｅ）のグリッド・グラフ情報は、広告元の座標（０，−１）の−ｘ方向の座標、つまり、座標（−１，−１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グラフの−ｘ方向の位置にあるノードは、ノードＱである。同様に、図１０（Ｆ）のグリッド・グラフ情報は、広告元の座標（−１，０）の−ｙ方向、つまり、座標（−１，−１）のノードを決定するためのものである。ここで、ユニット・フィールドの２つのユニット・グラフの−ｙ方向の位置にあるノードは、ノードＱのみである。したがって、ノードＱが座標（−１，−１）のノードとなり、図１１（Ｃ）に示すグリッド・グラフ情報を広告する。図６（Ｅ）は、ノードＱがグリッド・ノードになった状態を示している。
【００５３】
ノードＣは、図１１（Ｃ）のグリッド・グラフ情報を受け取ることで、ノードＱが座標（−１，−１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１１（Ｄ）に示す様に変更する。具体的には、既に決定したグリッド・ノードを制約条件とすると、図８（Ａ）及び（Ｂ）の両方を選択できる。したがってユニット・スコア値の大きい図８（Ａ）のユニット・グリッドを選択し、これにより座標（０，−２）のノードをノードＳであると決定する。よって、図１１（Ｄ）に示す様に、ステージ・フィールドを"決定"にし、ユニット・フィールドには決定したユニット・ノードの１ホップ・ノードを含むグリッド・グラフ情報を広告する。これにより、ノードＳは自装置が座標（０，−２）のノードとなったことを知る。
【００５４】
一方、ノードＢは、図１１（Ｃ）のグリッド・グラフ情報を受け取ることで、ノードＱが座標（−１，−１）になったことを知ると、それに応じて、広告するグリッド・グラフ情報を図１１（Ｅ）に示す様に変更する。具体的には、既に決定したグリッド・ノードを制約条件とすると、図８（Ｃ）及び（Ｄ）の両方を選択できる。したがってユニット・スコア値の大きい図８（Ｃ）のユニット・グリッドを選択し、これにより座標（−２，０）のノードをノードＷであると決定する。よって、図１１（Ｅ）に示す様に、ステージ・フィールドを"決定"にし、ユニット・フィールドには決定したユニット・ノードの１ホップ・ノードを含むグリッド・グラフ情報を広告する。これにより、ノードＷは自装置が座標（−２，０）のノードとなったことを知る。図６（Ｆ）は、ノードＳ及びＷがグリッド・ノードになった状態を示している。
【００５５】
以後、例えば、座標（２，０）のノードＨと、座標（１，１）のノードＥが広告するグリッド・グラフ情報により座標（２，１）のノードが決定され、座標（０，２）のノードＭと、座標（１，１）のノードＥが広告するグリッド・グラフ情報により座標（１，２）のノードが決定され、座標（２，１）のノードと、座標（１，２）のノードが広告するグリッド・グラフ情報により座標（２，２）のノードが決定されるといった様に、各象限において同様の処理が繰り返えされることで、各象限の方向にグリッド・グラフが拡張される。なお、軸外ノードは、まず、ステージ・フィールドに"下流未定"を設定するが、下流ノードから自装置の正しい座標を示すグリッド・グラフ情報を受け取ると、グリッド・グラフ情報のユニット・フィールドの値を更新する。また、２つの下流ノードからグリッド・グラフ情報を受け取ると、ステージ・フィールドを"下流決定"に変更し、それに応じて広告するグリッド・グラフ情報のユニット・フィールドの値を更新する。なお、軸外ノードが、最初にグリッド・グラフ情報を広告するときにおいて、既に決定したグリッド・ノードを制約条件とするユニット・グリッドが１つのみである場合、ステージ・フィールドには"下流決定"を設定する。
【００５６】
なお、グリッド・グラフを拡張する仮定で、グリッド・ノードとしてアンカ・ノードが選択されると、当該アンカ・ノードは、グリッド・グラフ情報のアンカ情報フィールドに、自装置の識別子と、自装置の位置情報と、自装置の座標を設定する。各グリッド・ノードは、受信したアンカ情報フィールドのノードが増加すると、自装置が広告するグリッド・グラフ情報のアンカ情報フィールドも増加する様に更新し、これにより、各グリッド・ノードがアンカ情報を共有する。つまり、グリッド・ノードとなったアンカ・ノードの座標および位置情報が、アンカ・ノードではないグリッド・ノードに通知される。
【００５７】
なお、選択したユニット・グラフのタイプがＴｙｐｅ１以外の場合、欠損している方向の処理が行われず、その方向への拡張が停止することになる。例えば、Ｘ軸上の軸ノードが、制約条件に従い選択したユニット・グリッドでは、＋ｙ方向のノードが存在しない場合、当該ノードは、ステージ・フィールドに"正側"を設定することなく、"負側"を設定したグリッド・グラフ情報を広告する。また、Ｘ軸上の軸ノードが、ステージ・フィールドに"正側"を設定して広告し、＋ｙ方向のノードが決定した場合において、制約条件を満たすユニット・グリッドでは、−ｙ方向のノードが存在しない場合には、ステージ・フィールドに"負側"を設定して広告することなく、ステージ・フィールドに"決定"を設定し、Ｘ軸上で１つ下流の座標に対応するノードを決定して広告する。なお、制約条件を満たすユニット・グリッドでは、Ｘ軸上で１つ下流の座標に対応するノードが存在しない場合には、例えば、ステージ・フィールドに"決定"を設定し、Ｘ軸上で１つ下流の座標に対応するノードを空欄とするグリッド・グラフ情報を広告する。なお、Ｙ軸についての同様である。
【００５８】
なお、上記実施形態においては、各軸ノードは、ステージ・フィールドに"正側"を設定し、次いで、"負側"を設定していた。しかしながら、各軸ノードは、ステージ・フィールドに"負側"を設定し、次いで、"正側"を設定することも可能である。さらに、Ｘ軸上の軸ノードは、ステージ・フィールドに"正側"を設定し、次いで、"負側"を設定する一方、Ｙ軸上の軸ノードは、ステージ・フィールドに"負側"を設定し、次いで、"正側"を設定することやその逆も可能である。
【００５９】
＜手順７＞
手順７においては、アンカ・ノード以外のグリッド・ノードが自装置の位置の推定を行う。各グリッド・ノードは、３つのアンカ・ノードの位置情報とそのグリッド・ノードにおける座標と、自装置のグリッド・ノードにおける座標から、以下の計算式により自装置の位置を推定する。
【００６０】
【数１】
2014036277.tif 000003
ここで、（Ｘ１，Ｙ１），（Ｘ２，Ｙ２），（Ｘ３，Ｙ３）は３つのアンカ・ノードの位置情報であり、（ｘ１，ｙ１），（ｘ２，ｙ２），（ｘ３，ｙ３）は３つのアンカ・ノードのグリッド・ノードにおける座標であり、（ｘ，ｙ）は位置を推定するグリッド・ノードの座標であり、（Ｘ，Ｙ）は推定位置である。
【００６１】
なお、アンカ・ノードが２つしかない場合には、計算することができず、よって、そのグリッド・グラフでの位置推定は不可である。なお、４つ以上のアンカ・ノードが含まれる場合、３つのアンカ・ノードを選択して計算する。なお、グリッド・グラフでの座標位置が１直線上にある３つのアンカ・ノードや、その実際の位置が１直線上にあるアンカ・ノードを、位置の推定に使用することはできない。よって、たとえ、アンカ・ノードが３つ以上あったとしても、これらがグリッド・グラフの座標又は実際の位置において一直線上に並ぶ場合には、当該グリッド・グラフでの位置推定は不可である。
【００６２】
なお、推定誤差を抑えるため、４つ以上のアンカ・ノードがグリッド・グラフに含まれる場合において、位置の推定に使用する３つのアンカ・ノードの実際の位置は、略１直線上に並ばない様にする。例えば、３つのアンカ・ノードの位置情報に対応する点を点Ｘ，Ｙ，Ｚとすると、点ＸとＹを結ぶ直線の傾きに対する点ＸとＺを結ぶ直線の傾きの比が、１を含む所定範囲内である場合には、この３つのアンカ・ノードの組を位置の推定に使用しない構成とすることができる。さらに、前記傾きの比が、１を含む所定範囲外となる３つのアンカ・ノードの組み合わせが複数ある場合、位置の推定を行うグリッド・ノードは、３つのアンカ・ノードのグリッド・グラフでの座標の重心位置と、自装置の座標との距離を求め、この距離が最も小さくなる組み合わせの３つのアンカ・ノードにより位置を推定することができる。また、位置の推定を行うグリッド・ノードは、当該距離が所定の値以下となる組み合わせから１つの組み合わせを選択し、選択した組合せに含まれる３つのアンカ・ノードにより位置を推定することができる。これは、推定誤差を小さくするためには、できるだけ近い位置にあるアンカ・ノードを使用することが好ましいからである。
【００６３】
なお、グリッド・グラフは、アンカ・ノード毎に生成されるため、１つのノードが複数のグリッド・グラフのグリッド・ノードになる場合がある。この様なノードは、各グリッド・グラフにおいて計算する自装置の位置の重心位置を自装置の位置と推定する。
【００６４】
＜手順８＞
手順８においては、いずれのグリッド・グラフのグリッド・ノードにもならなかった非グリッド・ノードが自装置の位置の推定を行う。各グリッド・ノードは手順７で推定した自装置の位置情報を広告し、アンカ・ノードは自装置が保持する位置情報を広告している。非グリッド・ノードは、直接受信する広告に含まれるこれらの位置情報が示す位置の重心を、自装置の推定位置とする。
【００６５】
以上の構成により、アンカ・ノード以外のノードは、自装置の位置を推定することができる。本実施形態では、少なくとも３つのアンカ・ノードがグリッド・グラフに含まれればよく、多くのアンカ・ノードを必要とはしない。また、本実施形態では、非凸包形状による問題は発生せず、各ノードがそれぞれ局所的な情報でグリッド・ノードであるかを判定して位置を推定するため、トラフィック負荷も多くはならない。なお、上記実施形態では、アンカ・ノードと、それ以外のノードを異なる装置として説明したが、本発明はその様な形態に限定されない。例えば、ノードに位置情報を与えると、アンカ・ノードとして動作し、そうでなければ通常のノードとして動作する様にノードを構成することができる。つまり、記憶部に位置情報が設定されているか否かを判定し、位置情報が設定されているか否かに応じて、その動作を決定する様にノードを構成することができる。
【００６６】
なお、本発明によるノードは、コンピュータを上記ノードとして動作させるプログラムにより実現することができる。これらコンピュータプログラムは、コンピュータが読み取り可能な記憶媒体に記憶されて、又は、ネットワーク経由で配布が可能なものである。
【図１】
2014036277.tif 000004
【図２】
2014036277.tif 000005
【図３】
2014036277.tif 000006
【図４】
2014036277.tif 000007
【図５】
2014036277.tif 000008
【図６】
2014036277.tif 000009
【図７】
2014036277.tif 000010
【図８】
2014036277.tif 000011
【図９】
2014036277.tif 000012
【図１０】
2014036277.tif 000013
【図１１】
2014036277.tif 000014