IPSJ SIG Technical Report Vol.2015-DPS-162 No.18 Vol.2015-CSEC-68 No /3/5 NLOS (SOM) Self-Organaizing Localization,SOL SOL, (LOS:Line-O

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2015-DPS-162 No.18 Vol.2015-CSEC-68 No /3/5 NLOS (SOM) Self-Organaizing Localization,SOL SOL, (LOS:Line-O"

ひでかうえや
4 years ago
Views:

1 NLOS 2 2 (SOM) Self-Organazng Localzaton,SOL SOL, (LOS:Lne-Of-Sght) NLOS:Non- Lne-Of-Sght) NLOS SOL NLOS. (WSN) WSN Range-Based Range-Free Range-Based TDOA(Tme Dffer-ence Of Arrval) TOA(Tme Of Arrval) GPS(Global Postonng System) Range-Based Range-Free Centrod[4] DV-Hop[5] Range-Free (SOM) Self-Organazng Localzaton, 2 SOL [] WSN SOL SOL NLOS SOL SOL WSN SOL Range-Based Range-Based TDOA(Tme Dfference Of Arrval) TOA(Tme Of Arrval) TOA GPS GPS 4 GPS TDOA Actve Bat[2] Crcket[3] TDOA c 205 Informaton Processng Socety of Japan

2 TOA TDOA Range-Based WSN 2.2 Range-Free Range-Free Centrod [4] DV-Hop [5] APIT [6] Centrod DV-Hop 3 APIT Centrod 3 3. Self-Organzng Localzaton (SOL) SOL 2 3 WSN NLOS 3. SOL 3 Step. t w (t) ) 2 2 Step.2 j w j (t) w (t) j w j (t) j d V (t) ( ) d V {} (t) = d w (t) w j (t) (w (t) w j (t)) () w (t) w j (t) 2 k 2 2 V 2 (t) ( 2) V {2} (t) = d + d w (t) w k (t) (w (t) w k (t)) (2) w (t) w k (t) 2 j 2 k 2 () j 2 k ( w (t) w j (t) w (t) w k (t) )( 3) ( )) c 205 Informaton Processng Socety of Japan 2

3 α (t) I {2} < θ (5) N {2} 3 2 w (t) w (t + ) = w (t) + α (t) V {} (t) ( w (t) w j (t) < w (t) w k (t) ) w (t) + α (t) (V {} (t) + V {2} (t)) ( w (t) w j (t) w (t) w k (t) ) (3) α (t) t α (t) = ηα (t ) (0 < η < ) (4) η Step.3 w (t) w j (t) 2 Step.2 Step SOL 3.2. ( α (t) ) I {2} N {2} 2 θ r 3 p A A A (6) ( rx A = r y ) = ( a b c d e f ( a b c d e f ) ) p x p y 3.3 NLOS (6) SOL NLOS SOL ( ( 4) (7) T d T ( d 0 ) d T + = d T T (7) SOL c 205 Informaton Processng Socety of Japan 3

情報処理学会研究報告図6 図 4 折れ曲がりトポロジ (左:オリジナルトポロジ右:推定トポロジ) ノード間トポロジ矛盾を解消するノード間ホップ度正の実数値図 7 折れ曲がり推定トポロジと角度方向による判定 NLOS 混在環境における近傍ノード数の不足による精度劣化が起こり推定トポロジが折れ曲がりトポロジ図 5 となり (図 6) となる場合があり位置精度の劣化の主 3

4 情報処理学会研究報告図6 図 4 折れ曲がりトポロジ (左:オリジナルトポロジ右:推定トポロジ) ノード間トポロジ矛盾を解消するノード間ホップ度正の実数値図 7 折れ曲がり推定トポロジと角度方向による判定 NLOS 混在環境における近傍ノード数の不足による精度劣化が起こり推定トポロジが折れ曲がりトポロジ図 5 となり (図 6) となる場合があり位置精度の劣化の主 3 次近傍ノードによる位置修正 Fg. 5 Locaton update wth 3 hop neghborhood node. を増加させるため 3 次近傍ノードの位置情報 wl (t) を取得させたその際ここでの入力ベクトルはノードと 3 次近傍ノード k との距離は少なくとも次近傍ノードより遠く位置することから 2 次近傍ノードと同様に次のように算出する {3} V (t) 2d w (t) wl (t) = (w (t) wl (t)) w (t) wl (t) 要因となる各ノードの通信回数が多くなり電力消費が大きくなる上記問題を解決するためクラウドコンピューティングを前提とする集約型 SOL を提案する集約型 SOL は各センサノードからの隣接ノード情報をクラウド環境へ集約するこれにより構成する仮想 WSN へ SOL を適用した (8) 近傍ノードの位置情報は受信した次近傍ノードからの 2 次近傍ノード 3 次近傍ノード情報をそれぞれ任意に１つ近傍ノードを選択する (図 5) また修正の段階を初期段階以降の段階の 2 つに分け方式である集約型 SOL は次のようなクラウド環境を想定する WSN のセンサノードは自己の隣接ノード情報をセンシングしこれをクラウドサーバへ転送するクラウドサーバは各センサノードの隣接ノード情報を集約し仮想 WSN を構成するる初期段階では 3 次近傍ノードと次近傍ノードによる仮想 WSN はすべてのノードの隣接ノード情報を集約する位置修正を行い初期段階以降は 2 次近傍ノードと次近ため完全なトポロジ情報を有する一方そのトポロジ傍ノードにより位置更新を行うすなわち位置推定初期のジオメトリ形状は全くのランダムでたらめであ段階では比較的遠いノード位置情報を用いて大域的な処理る集約型 SOL はこの完全なトポロジ情報をもつ WSN を行いその後比較的近いノード位置情報から局所的なに SOL を適用クラウド化し前述の問題解決するため処理を行う次の処理を行う 4. 集約型 SOL 4. SOL の問題点 SOL は各ノードが自律的に自己位置を推定する方式であるしかし各ノードが個別に推定を行うため下記の問題が発生すると考えられる 205 Informaton Processng Socety of Japan 精度劣化の原因は折れ曲がりトポロジの発生であるしかし距離判定ではトポロジ矛盾 (図 7) を検出できないため角度判定を追加する完全なトポロジ情報を用いた N 次近傍ノード更新により大域的情報から全体形状の再現精度向上を図るクラウドクライアントであるセンサノードは隣接ノー 4

5 WSN ( WSN) ID ID ID SOL j j 2 n x (n ) x (n + ) WSN n SOL n (n ) d n n (9) w n (t) n (0) τ N V n (t) = nd w (t) w n (t) (w (t) w n (t)) (9) w (t) w n (t) w (t + ) = w (t) + α (t) (V {} (t) + V {n} (t)) (t < τ n ) w (t) + α (t) (V {} (t) + V {n } (t)) (τ n < t < τ n ). w (t) + α (t) (V {} (t) + V {3} (t)) (τ 4 < t < τ 3 ) w (t) + α (t) (V {} (t) + V {2} (t)) (otherwse) (0) ( w w l w w j ) 7 j k 2 l V jk V j θ V jl θ 2 7 θ θ 2 θ θ () () B b A ( ) a η {} η {2} b B η{} a A η{2} () NLOS SOL SOL c 205 Informaton Processng Socety of Japan 5

情報処理学会研究報告表評価は相対位置評価と絶対位置評価の 2 通り行う相シミュレーション諸元.0.0 対位置評価は推定されたノード位置により構成されるネッ (0.5, 0.35),(0.5, 0.75) トワークの形状推定ネットワーク形状とオリジナルフィールド範囲障害物座標 (.

2 アンカノード数位置修正実行回数評価トポロジ数 3 300 ネットワークの形状の相似性を次の式により評価する rj = 50 dej dj (2) N r = rj N = V [rj ] = (3) N N ( rj / r)2 N C2 = j=+ (4) dej

と同じスケールとなり分散 V [rj ] が 0 に近づけば推定図 8 シミュレーションフィールドにおける障害物と NLOS ネットワーク形状はオリジナルのネットワーク形状と相似となるすなわち r が V [rj ] が 0 の場合推定ネット

の真位置 w は推定位置を示す図 9 通信回数比較グラフの全ノード送信回数を示す図 9 から分かるように集約型 SOL は大幅に送信回数を削減する SOL は位置更新を各ノードで実施するため図 0 ノード数に応じた平均図ノード数に応じた分散

6 情報処理学会研究報告表評価は相対位置評価と絶対位置評価の 2 通り行う相シミュレーション諸元.0.0 対位置評価は推定されたノード位置により構成されるネッ (0.5, 0.35),(0.5, 0.75) トワークの形状推定ネットワーク形状とオリジナルフィールド範囲障害物座標 (.0, 0.75),(.0, 0.35) 通信半径 0.2 アンカノード数位置修正実行回数評価トポロジ数ネットワークの形状の相似性を次の式により評価する rj = 50 dej dj (2) N r = rj N = V [rj ] = (3) N N ( rj / r)2 N C2 = j=+ (4) dej は推定位置におけるノードとノード j の距離 (推定距離) dj はオリジナルのネットワークにおけるノードとノード j の距離 N は位置推定ノードの集合 N はノード数 (集合 N の要素数) を示す平均 r がに近づけば推定ネットワーク形状はオリジナルのネットワーク形状と同じスケールとなり分散 V [rj ] が 0 に近づけば推定図 8 シミュレーションフィールドにおける障害物と NLOS ネットワーク形状はオリジナルのネットワーク形状と相似となるすなわち r が V [rj ] が 0 の場合推定ネットワーク形状はオリジナルのネットワーク形状に一致する絶対位置評価は推定された各ノードの位置と真位置のユークリッド距離の総和の平均である位置推定誤差 Errave を用いて評価する Errave は次の式 (5) のように求める W w N = N Errave = (5) W はノードの真位置 w は推定位置を示す図 9 通信回数比較グラフの全ノード送信回数を示す図 9 から分かるように集約型 SOL は大幅に送信回数を削減する SOL は位置更新を各ノードで実施するため図 0 ノード数に応じた平均図ノード数に応じた分散ノード間で更新仮自己位置を頻繁に交換するそのため通信量は大きくなる一方集約型 SOL は位置更新をクラウド環境の仮想 WSN で実施するため各ノードは位置更新時の仮自己位置の交換は不要であり仮想 WSN の構成のために自身の隣接ノード情報をクラウドサーバへ転送するだけである 5.3 相対位置評価と絶対位置評価以下の方式での比較評価を行う集約型 SOL DV-hop 方式 SOL 205 Informaton Processng Socety of Japan 図 2 から分かるように SOL と比較して集約型 SOL はその位置推定誤差が非常に小さく位置推定精度が圧倒 6

情報処理学会研究報告図 2 ノード数に応じた絶対位置評価的に高い SOL は少数のネットワークトポロジにおいて部分的な形状は正しく推定されているが折れ曲がりが発図 4 DV-hop での位置推定トポロジ (左:オリジナルトポロジ右: 推定トポロジ) 生し全体トポロジとして大きな誤差となる数は少ないが誤差が非常に大きなケースがありこれが全トポロジの平型 SOL を提案したまた

SOL ある大幅に通信回数を削減可能であるの V [rj ] より低くかつ 0 に極めて近い従って集約型今後は多様な NLOS 環境で集約型 SOL の有効性の検証を SOL は推定ネットワーク形状においても優れその形状は進めさらに集約型 SOL の 3 次元化を検討するオリジナルネットワーク形状にほぼ一致する図 3) 一方 DV-Hop の r および V [rj ]

つの [3] アンカノード重心として推定するためであるすなわち NLOS 混在環境では DV-Hop はほぼ機能せず図 2 の示 [4] す DV-Hop の位置推定誤差では現れない大きな誤差となる以上のことから集約型 SOL は NLOS 環境において [5] もネットワーク全体の高精度な形状再現と高精度なノード位置推定が維持可能であるといえる図 3 [6] 大野, 安達, 滝沢

7 情報処理学会研究報告図 2 ノード数に応じた絶対位置評価的に高い SOL は少数のネットワークトポロジにおいて部分的な形状は正しく推定されているが折れ曲がりが発図 4 DV-hop での位置推定トポロジ (左:オリジナルトポロジ右: 推定トポロジ) 生し全体トポロジとして大きな誤差となる数は少ないが誤差が非常に大きなケースがありこれが全トポロジの平型 SOL を提案したまた集約型 SOL の基本的な NLOS 均誤差を大きく引き上げる一方集約型 SOL は完全に環境のシミュレーション評価から次の優位性を確認した折れ曲がりトポロジを抑制し安定して低い誤差を維持す NLOS 環境においても高い位置推定精度を維持可能でる図 0 に示す集約型 SOL の r は SOL の r より低くかつに極めて近い図の集約型 SOL の V [rj ] も SOL ある大幅に通信回数を削減可能であるの V [rj ] より低くかつ 0 に極めて近い従って集約型今後は多様な NLOS 環境で集約型 SOL の有効性の検証を SOL は推定ネットワーク形状においても優れその形状は進めさらに集約型 SOL の 3 次元化を検討するオリジナルネットワーク形状にほぼ一致する図 3) 一方 DV-Hop の r および V [rj ] のいずれも SOL や集約型 SOL と比較すると非常大きい従って DV-Hop の推定ノード位置により構成されるネットワーク形状はオリ参考文献 [] ジナルネットワークの形状と著しく異なる図 4) この原因は NLOS 混在環境においては DV-Hop 方式では算 [2] 出されたホップの距離精度が低いため多角測量の最小二乗から解が得られずその場合にはノード位置を 3 つの [3] アンカノード重心として推定するためであるすなわち NLOS 混在環境では DV-Hop はほぼ機能せず図 2 の示 [4] す DV-Hop の位置推定誤差では現れない大きな誤差となる以上のことから集約型 SOL は NLOS 環境において [5] もネットワーク全体の高精度な形状再現と高精度なノード位置推定が維持可能であるといえる図 3 [6] 大野, 安達, 滝沢無線センサネットワークにおける自己組織化位置推定方式の提案, 情報処理学会論文誌, Vol.53, No.7, pp , (202). A.Harter A.Hopper P.Steggles A.Ward and P.Webstar : The anatomy of a context-aware moble applcatons MOBICOM999 (999). N.Pryantha A.Mu H.Balakrshman and S.Teller : The crcket compass for context-aware moble applcatons MOBICOM200 (200). N.Bulusu J.Hedemann and D.Estrn : GPS-less low cost outdoor localzaton for very small devces IEEE Personal Communcatons Magazne (2000). D.Nculescu and B.Nath : DV-based postonng n ad hoc networks Telecommun.Syst vol.22,pp (2003). D.Nculescu and B.Nath : DV-based postonng n ad hoc networks Telecommun.Syst vol.22,pp (2003). 集約型 SOL での位置推定トポロジ (左:オリジナルトポロジ右:推定トポロジ) 6. まとめ本稿はクラウドコンピューティングを前提とする集約 205 Informaton Processng Socety of Japan 7

IPSJ SIG Techncal Report 2. RangeBased RangeFree. 2.1 Rangebased RangeBased TDOA(Tme Dfference Of Arrval) TOA(Tme Of Arrval) TDOA TDOA Actve Bat 2) Cr

IPSJ SIG Techncal Report 2. RangeBased RangeFree. 2.1 Rangebased RangeBased TDOA(Tme Dfference Of Arrval) TOA(Tme Of Arrval) TDOA TDOA Actve Bat 2) Cr IPSJ SIG Techncal Report 1 2 2 (SOM, Self Organzng Maps) 7). Self-Organzng Localzaton for Wreless Sensor Networks on Ansotropc Topology Yuto Takashma, 1 Naotosh Adach 2 and Yasuhsa Takzawa 2 On wreless