センサネットワークのプロトコル　位置測定

ノート

位置測定

ノードの位置情報は，物理現象が感知された位置を特定するだけでなく，経路制御やデータ集約などのプロトコル処理を効率化し，センシング領域や位置に依存したサービスを提供する利用価値が高い．

近年，コンピュータの小型化に伴い，モバイルコンピュータ技術が注目され，またユビキタスコンピューティングなどにより，位置測定技術が多く提案されている．しかし，これらの技術はレンジベース位置測定と呼ばれ，特殊なハードやインフラが必要である．そのため，センサーネットワークで利用するのは，省電力と低コストが実現可能なレンジフリー位置測定と呼ばれる技術が注目されている．

  • レンジベース位置測定 （Range Based Localization）

その名のとおり，なんらかの方法（電波、音波、磁気などから得られる「特殊な情報」から計算する）で各デバイス間の距離を測定し，位置を測定する方法．しかし，特殊なハードウェアが必要となり高価であることや，Beacon nodeを適切に設置できる物理的な環境が必要である．

  • レンジフリー位置測定（Range Free Localization）

「特殊な情報」を仮定しない方式である．*1

Centroid測定

Centroid（重心）測定では，位置をあらかじめ知っているランドマークが，定期的に自らの位置情報を含んだビーコンをブロードキャストで近隣のノードに送信する．ランドマークからのビーコンは，球状に送信されると仮定している．つまり，受信電波強度を考慮しないものである．
さらに，ランドマークが多く存在していることを想定している．*2

位置を知らないノードは，そのビーコンに含まれる位置情報から周りに存在するランドマークの位置を知ることができる．N台のランドマークの位置(X_i,Y_i)が取得できた場合，式3で重心 (X_est,Y_est)を計算する．*3


(X_est,Y_est)=(\frac{X_1+\cdot\cdot\cdot+X_N}{N},\frac{Y_1+\cdot\cdot\cdot+Y_N}{N})

計算した値を自分の位置とする．
図1に，Centroid測定による位置測定の例を示す．

図1:Centroid測定による位置測定

DV-Hop測定

DV-Hop測定では，ランドマークからのホップ数と１ホップの平均距離の情報から，各ノードがランドマークまでの距離を見積もる．３台以上のランドマークからの距離を見積もり，多角測定により自らの位置を算出する仕組み．

  • Step 1: 各ノードは、ネットワーク内のランドマークからのホップ数を知る．（ホップカウンタを参照する）

ランドマークは自分位置情報を含んだパケットをフラッディングする．また，このパケットには中継する度にカウントされるホップカウンタが含まれている．

  • Step 2: ランドマークは1ホップの平均距離を近隣ノードに知らせる．

一度しか“1ホップの平均距離”パケットを中継しない制御フラッディングを利用する．Step 1で得られたホップ数と１ホップの平均距離を掛け合わせることによりランドマーク までの距離を算出する．

  • Step 3: 3台以上のランドマークとの距離を算出して多角測量により位置測定する．

１ホップの平均距離の算出方法を紹介する．あるランドマークがフラッディングしたパケットは，他のランドマークにも到着している．ランドマークは自分の座標と他のランドマークの座標から，２地点間の物理的な距離を計算することができる．さらに，そのランドマークまでのホップ数(h)がわかっているため，物理的な距離をホップ数で割った値が１ホップの平均距離のサンプルとして計算する．このサンプル取得処理を他のすべてのランドマークに対して行うことにより，最終的にサンプルを平均化して１ホップの平均距離が計算できる．

C_i=\frac{\sum \sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2} }{ \sum h_i },(i \neq j)

図2に，DV-Hop測定による位置測定の例を示す．

図2:DV-Hop測定による位置測定
しかし，DV-hop 手法は平均距離を利用するため，簡易的に構築可能な手法であるが，非常に誤差が大きい．*4

APIT測定

APIT (Approximate Position-in-triangle)測定では，ランドマークが位置情報を含んだビーコンを定期的に送信する．ランドマークからのビーコンは，広範囲の多くのノードに届く環境を理想としている．

各ノードは，受信したビーコンから３台のランドマークの組み合わせで生成可能なすべての３角形を導き出す．この３角形すべてに対して，自分が内側にいるのか外側にいるのかの検証を行い，自分の位置を絞り込んでいく方式である．
図3に，APIT測定のイメージを示す．
図3:APIT測定

API測定では，ランドマークからの電波強度をノード同士が交換し合うことにより，そのランドマークにどちらのノードの方が近いのかを判断する．近接ノードに３台のランドマークとの距離がすべて自分より遠いノードが存在する場合，自分が三角形の外側にいると判断する．(図4)

図4:APIT測定による位置判定

この検証では，測定ノードが三角形の辺のそばにいる場合，内側にいるのに外側にいると判断してしまうこと（In To Out Error）がある．また，近隣ノードの位置が不均整になると，外側にいるのに内側にいると判断してしまうこと(Out To In Error)もある．

APITは，その他のrange-freeな位置測定方法 Centroid， DV-Hop, Amorphous などとの比較(シミューレションで)では，結果として、ノード配置に対し頑強(ランダムな配置でも良い性能)，電波パターンがirregularなのにも頑強で条件が悪いときにも良く動くという特性を示す．
また，Overhead は最も単純な Centroid よりちょっと悪いくらいである．*5


センサネットワークのプロトコル トポロジ - WebLab.ota
センサネットワークのプロトコル データリンク層 - WebLab.ota
センサネットワークのプロトコル 位置測定 - WebLab.ota
センサネットワークのプロトコル 時刻同期 - WebLab.ota

*1:Home - Fixstars Corporation

*2:http://www2.infonets.hiroshima-u.ac.jp/dicomo/program/2C\_abst.html

*3:http://case.f7.ems.okayama-u.ac.jp/statedu/hbw2-book/node122.html 重心法

*4:http://www.matlab.nitech.ac.jp/~matsuo/MBL05-1.pdf アドホックネットワークにおけるばねモデルを適応した端末位置決定手法

*5:http://www.spa.is.uec.ac.jp/~kinuko/survey/survey.cgi?cmd=show&pid=56