情報処理学会創立50周年記念（第72回）全国大会

3ZD-2
静止ノードの検出により測位回数を抑制する
移動無線ネットワーク向け位置推定
樋口 雄大 ∗1

藤井 彩恵 ∗2

山口 弘純 ∗2,∗3

東野 輝夫 ∗2,∗3∗1∗2
大阪大学 基礎工学部情報科学科
大阪大学 大学院情報科学研究科∗3
独立行政法人 科学技術振興機構, CREST
t-higuti@ics.es.osaka-u.ac.jp{ s-fujii, h-yamagu, higashino }@ist.osaka-u.ac.jp

1

はじめに近年，位置情報を用いたサービスの普及に伴い，移動端末の位置を推定する技術が求められている．測位手法としては GPS が一般に利用されているが，屋内環境では測位誤差が大きかったり，測位自体が行えない場合がある．このため，文献 [1] のように，端末間の測距結果と他端末の推定位置を利用した測位方法が提案されているが，移動端末の位置を高精度に推定するためには，測位頻度を上げる必要があり，電力や通信帯域に制限がある環境では適切ではない．また，文献 [2] のように，端末間の通信履歴から移動端末の位置を推定する手法も提案されているが，通信が不安定な環境では誤差が大きい．
そこで，本稿では，各移動端末 (ノード) が，周辺ノードとの距離を測定できる機器を保持し，正確な位置が既知である固定端末 (ランドマーク) がフィールド内に疎に配置された環境下において，ネットワーク全体の測位回数を抑制しつつ，ノードの位置を高精度に推定する自律分散型手法を提案する．
提案手法では，各ノードが周辺ノードとの測距を行い，前回の測位時から移動していないノード（静止ノード）と移動したノード（移動ノード）を検出し，静止ノードの推定位置のみを基準として自身の位置を推定する．これにより，位置誤差が比較的大きいと想定される移動ノードの位置誤差が，ノード間に伝搬することを抑止する．また，周辺ノードの測距により，各ノードが自身の移動を検知し，移動ノードは測位頻度を上げて精度向上を図り，静止ノードは測位頻度を下げる．このように，測距結果を用いて位置関係の変化を検出し，ノードが移動速度に応じて自律的に測位頻度を調節する仕組みを実現している．

2提案手法

2.1 概要ノード間の測距法としては，GPS のように，測距信号の到達遅延時間 (ToA : Time of Arrival) を利用する方法
や，伝搬速度の異なる 2 種類の信号の到達時間差 (TDoA: Time Diﬀerence of Arrival) を用いる方法 [1] などがある．本稿では，電波と超音波の TDoA に基づく測距法を想定し，各ランドマークおよびノードが，周辺ノードとの距離測定のための機器を保持するとする．
測位の際に，位置の基準となるノードを，アンカーと呼ぶ．各ノードは，3 つ以上のアンカーの位置および測距結果を用いて自律的に位置を推定する．すべてのノードの位置が未知である初期状態においては，アンカーとして参照可能な端末はランドマークのみとする．

±dth4
A4(x4,y4)

±dth1

±dth3

A1(x1,y1)d4
d1d2d3A3(x3,y3)P

移動

d3A2(x2,y2)±dth2

A'3(x'3,y'3)

尤度1の領域
尤度2の領域
尤度3の領域

図 1: 初期解の尤度分布の例
各ノードは，2.3 節で定義する測位間隔に基づき，繰り返し測位を実行する．あるノード（測位対象ノード) が測位を行うときには，まず，周辺ノードに対して測距信号を発信する．測距信号を受信したノード Ai は，自身の推定移動速度が 0 であれば，位置 (xi , yi ) と測距値 di を，測位対象ノードに送信する．測位対象ノードは，周辺ノードから得られたすべての測距結果から，推定位置の初期解 x0 を生成する．また，初期解と測距結果を用いて，移動していると思われるノードを検出する．
次に，移動していると思われるノードを除外した残りのノードをアンカーとし，最小二乗法を用いて，各アンカーとの距離が測距値になるべく近くなるような推定位置を求める．なお，3 つ以上のアンカーを参照できなかった場合には，定められた時間待機した後，再測位を行う．
最後に，前回測位を行ってからの移動距離と経過時間を用いて，推定移動速度 v を算出する．なお，移動距離が十分に小さい場合は，v = 0 とみなす．

2.2

初期解の生成と移動ノードの検出

測位対象ノード P と周辺ノード Ai の距離の測定値をdi ，想定される誤差を dthi とする．dthi は，Ai の位置誤差と測距誤差に基づき計算される．測位対象ノードは，各ノード Ai の位置 (xi , yi ) から距離 di ± dthi の領域内にあるという制約を満たす必要がある．最も多くの周辺ノードに対してこの制約を満たすような点を，初期解 x0 とし，下記の手順により求める．

Eﬃcient Localization of Mobile Nodes by Detecting Static Nodes
Takamasa Higuchi ∗1 Sae Fujii ∗2 Hirozumi Yamaguchi ∗2,∗3
Teruo Higashino ∗2,∗3∗1 School of Engineering Science, Osaka Univ., Osaka Japan∗2 Graduate School of Information Science and Technology, OsakaUniv., Osaka Japan∗3 Japan Science Technology and Agency, CREST

3-511

1. 前回の推定位置を中心とする半径 Vmax ∆T の領域内に，初期解の候補点 x(u) (u = 1, 2, ..., N ) を一様に生成する．Vmax はノードの最大移動速度，∆Tは前回の測位からの経過時間とする．また，各候補点の尤度を 0 に初期化する．
(u)

2. x(u) と各ノード位置 (xi , yi ) との距離 di を求め，(u)|di − di | < dthi ならば，候補点の尤度に 1 を加え情報処理学会創立50周年記念（第72回）全国大会

る．候補点の尤度の分布の例を図 1 に示す．

3. 尤度最大の候補点を初期解とする．尤度最大の候補点が複数存在する場合は，それらの重心を用いる．
初期解 x0 から各ノード Ai への距離 dˆi を求め，|dˆi −di | > dthi となるノードを移動ノードとして検出する．移動を検出したノードに対しては，通知を行う．の Random Waypoint を用い，移動速度は 4.0〜8.0km/hの範囲からランダムに決定した．また，無線到達距離はr=5m，R =10m とし，ノード間の無線通信プロトコルは，IEEE 802.11b を想定した．ノード間の測距誤差は正規分布に従うものとし，標準偏差は，ノード間の距離が d(m) の場合に 0.03d として与えた．
15m

2.3 ノードの測位間隔はじめに，移動しているノードの測位間隔について述べる．移動しているノードの場合，移動速度が速いノードほど高い頻度で測位を行い，推定位置の追従性を高めることが望ましい．本手法では，ノードの推定移動速度 vに基づき，各ノードが測位間隔を自律的に制御する．移動時の測位間隔 Iv は，式 (1) により定める．
1cv(v > 0)5m(1)c は，単位移動距離あたりの測位回数を表すパラメータであり，要求される移動分解能に応じて決定する．本稿では，経験的に 0.8 とする．
次に，静止しているノードの測位間隔について述べる．
推定移動速度が 0 となり，自身が静止していると判定したノードは，Is 秒の間，測位を行わない．ただし，その間に，測位対象ノードによって推定位置からの移動を検出され，移動通知を受信した場合には，ただちに測位を行い，推定位置と推定移動速度を更新する．なお，ある測位対象ノードとの距離が変化しない方向へ移動した場合には，2.2 節で述べた方法では検出できないため，以降の測位間隔の決定には，複数の測位対象ノードによる検出結果を併用する．具体的には，前回静止していると判定してから Is 秒間が経過するまでに m 個の測位対象ノードからアンカーとして参照された場合に，再び，自身が静止していると判定する．一方，Is 秒の間にアンカーとして参照された回数が m 回未満ならば，再測位を行う．
本稿では，Is = 5.0，m = 2 とする．
2.4 提案手法のプロトコル
近接する複数のノードが同時に測距信号を送信すると，干渉による波形の歪みや，受信された測距信号と送信元ノードの誤対応によって，正しい測距結果が得られない場合がある．そこで，測位を実行するノードは，測距信号を送信する前に Request To Measure メッセージ (以下，RTM) をブロードキャストし，周辺ノードに測位処理の開始を通知する．RTM を受信したノードは，送信元ノードが測位に要する期間分，自身の測位を延期する．
測距信号の到達距離が r である場合，RTM などの制御信号の到達距離 R が 2r よりも大きな値になるように無線出力を調整する．これにより，距離が R 以上離れたノードは，測位信号の衝突が発生しないため，同時に測位を行うことができる．
なお，実環境においては，信号伝搬チャネルの状態による無線到達距離の変動を考慮する必要があるため，R を大きめにとることが望ましい．

315m

図 2: シミュレーション環境
以上の環境で，10,000 秒における位置推定精度を，全ノードが一定の間隔 (6.0 秒，3.0 秒，2.0 秒) で測位した場合と比較した．位置推定精度の評価方法としては，ノードごとに全シミュレーション時間における推定位置の誤差の平均値を算出した．評価結果を図 3 に示す．
3
constant interval (6.0s)
constant interval (3.0s)
constant interval (2.0s)
variable interval (avg=5.96s)

2.5

Tracking Error [m]Iv =ランドマークのみで測位が可能な領域

21.5

10.50051015202530
Node ID

35404550

図 3: 位置推定誤差
提案手法では，1 ノードあたりの平均測位間隔が 5.96秒，平均誤差は 0.70 m となった．これは，2.0 秒の一定間隔で測位を行った場合 (0.69 m) と同程度の精度であり，位置推定精度を維持しつつ，測位回数をおよそ 1/3 に低減できることが分かった．

4まとめと今後の課題

本稿では，ノード間の測距結果に基づいて静止ノードを検出し，位置推定精度を低下させることなく測位回数を軽減する手法を提案した．また，シミュレーションにより，手法の有効性を示した．
今後は，測距信号の指向性や無線到達距離の変動など，実環境の特性を考慮したプロトコルの改良，および実機を用いた評価に取り組む予定である．

参考文献

シミュレーション

提案手法の有効性を示すため，ネットワークシミュレー
タ QualNet を用いてシミュレーションを行った．
図 2 のような 15m × 15m の正方形領域の 4 地点にランドマークを設置し，50 個のノードをランダムに配置した．ノードのモビリティは，移動確率 20%，停止時間 10 秒

3-512

[1] Y.Fukuju, M.Minami, H.Morikawa, T.Aoyama,“DOLPHIN: An Autonomous Indoor Positioning
System in Ubiquitous Computing Environment”, InProc. WSTFES 2003, pp.53-56, 2003.
[2] Sae Fujii, Takashi Nomura, Takaaki Umedu, Hirozumi Yamaguchi, Teruo Higashino, “Real-time
Trajectory Estimation in Mobile Ad Hoc Networks”, In Proc. MSWiM 2009, pp.163-172, 2009.