第 5 章 GOMASHIO を利用した位置 特定システムの設計
5.2 位置特定アルゴリズム
3.2節では，位置の特定手法として，Proximityを応用することを説明した．本節で は，これを利用して位置特定を実現するアルゴ リズムを説明する．アルゴ リズムでは，
位置情報の宣伝とホップカウントの取得部と存在する可能性の面積と位置の特定部の 二つの部分について説明する．
5.2.1 位置情報の宣伝とホップカウント の取得
GOMASHIOモデルでは，まずセンサノード 同士が自分の位置情報に関するメッセー
ジの交換を行う．GOMAノードは，自分の位置情報を送信し，SHIOノードは，GOMA ノード の座標とGOMAノード からのホップカウントを周辺ノード に送信する．この 行程で各SHIOノードは，GOMAノード とホップカウントを組みにした情報のリスト を作成する(表5.1)．
GOMAノード やSHIOノードは，位置情報やホップカウントをビーコンに付加して 送信する．ビーコンは無線ネットワークにおいてノード 同士がお互いの存在を認識す るために利用される識別信号で，一定間隔で無線デバイスが発信している．このため センサネットワークにおいてGOMASHIOの利用時に位置情報のメッセージのやりと
表 5.1: SHIOノードが持つリストの例
GOMAノード のID GOMAノード の位置 ホップカウント
1 (x1, y1) 2
5 (x5, y5) 3
6 (x6, y6) 1
りのために，フラッデ ィングが発生する問題を回避可能である．
図5.1は位置情報の宣伝とホップカウントの取得の部分を表す疑似コードである．以 下にその詳細を説明する．
1. SHIOノード は周辺ノード から メッセージを受信したかど うかで挙動が異なる．
メッセージを一つ以上受信した場合，メッセージに含まれているGOMAノード とホップ カウントを既に自分の情報として持っていないかを調べる(図5.1(1))．
持っている場合には，ホップカウントを比較して，小さい方を利用する．持って いない場合，新たにリストに追加する．
2. GOMAノードが送信した情報を直接受信した場合，SHIOノードはGOMAノー ド から1ホップであると認識する．
3. SHIOノードが送信した情報を受信した場合，送信側のSHIOノード のホップカ ウントより1多い数を自分のホップカウントとして認識し，その情報をリストに
追加する(図5.1(2))．これを受信した情報分だけ繰り返す．
4. 周辺ノードから情報を受信しなかった場合，孤立ノードとして認識する(図5.1(3))．
孤立ノードは，周辺ノードから情報を受信可能な状態になるまで情報の送信は行 わない．
この結果，到達不可能でない全てのSHIOノード はGOMAノード のリストを保持 する．この情報は，アルゴ リズムの次の行程で利用する．
5.2.2 存在する可能性のある範囲の取得と位置の計算
SHIOノードが位置を特定するためには，前行程で取得したGOMAノード リストを もとに，SHIOノードが存在する可能性のある範囲を求める．次に，存在する可能性 のある範囲の範囲矩形を求め，その重心を取得する．この重心が，特定されたSHIO ノード の位置となる．
SHIOノード の存在する可能性のある範囲を求める方法を，図5.2(a)に示すように，
三つのGOMAノード の位置とホップカウントを取得している場合を例に考える．
¶ ³ receive_messages();
/* (1) */
if ( number of neighbors > 0 ) {
for ( i = 1 to number of neighbors ) { if( check_list() ) {
update_list();
break;
} /* (2) */
if( neighbor Hop count == GOMA ) { add_list( ONEHOP,GOMA Location );
/* (3) */
} else if ( neighbor’s GOMA != GOMA ) {
add_list( neighbor Hop count + 1, GOMA Location );
} } /* (4) */
} else {
Hop count = Unreachable;
GOMA Location = false;
}
µ ´
図 5.1: 位置情報の宣伝とホップカウントの取得
1. GOMAノード の位置を中心とし ，無線電波の到達範囲の半径にホップカウント を乗算した値を半径とする円を，各GOMAノード に関して求める(図5.2(b)))．
2. 1で求めた円の範囲矩形を求め，全ての範囲矩形が重なる四角形を求める(図 5.2(c))．
3. 2で求めた四角形中の各座標に関して，SHIOノードが実際に存在する可能性が あるかど うかを判定する．判定には以下の式を用いる．hgはGOMAノードから のホップカウントを，rは１ホップの半径を表す．(xg, yg)はGOMAノード の位 置座標を示す．nはSHIOノードが取得したGOMAノード の情報の個数を表し ている．
すべての(xg, yg)(0 < g < n)に関して hg = 1の場合：
(xi−xg)2+ (yi−yg)2 < r2 hg >1の場合：
(xi−xg)2+ (yi−yg)2 < r2h2g でかつ
(xi−xg)2+ (yi−yg)2 > r2
が真の時，任意の座標(xi, yi)は存在する可能性のある座標と認められる．
図 5.2: 存在する可能性のある範囲を求める方法
3の行程では，存在する可能性のある座標として取得されたものの中で，x座標とy 座標のそれぞれに関して，最小値と最大値を取得することにより，存在する可能性のあ る範囲の範囲矩形(四角形)を求める(図5.3)．この範囲矩形の重心が最終的に，SHIO ノード の位置となる．
図 5.3: 存在する可能性のある範囲の範囲矩形
5.2.3 SHIOGOMA 変異
GOMASHIOでは，基本的にGOMAノード 以外は自分の位置情報の送信を行わな
い．SHIOノードが送信するのは，GOMAノード の座標とホップカウントである．
SH-IOGOMA変異とは，SHIOノード の存在する可能性のある範囲の面積がある程度小さ
くなった場合に，SHIOノードがGOMAノード と同様に位置情報を周辺ノードに送信 する機能を持つようにSHIOノードがGOMAノード に変異することである．