Approximate Convex Decomposition Based Localization in Wireless Sensor Networks - todo314 @ ウィキ

Approximate Convex Decomposition Based Localization in Wireless Sensor Networks

• Wenping Liu, Dan Wang, Hongbo Jiang, Wenyu Liu, Chonggang Wang
• INFOCOM 2012

概要

• Localization
• やばいのでヒューリスティクスばかり
• MDSって既存手法
  • 凹だったり穴があるとやばい
• 凸図形に分割して気合

問題

• 2次元のWireless Sensor Netrwork
• 各頂点の位置が知りたい
• GPSはコスト高
• ｰ すこしの頂点（アンカー）だけに設置
• 互いに距離が小さい所は通信
  • その距離が分からない場合がメジャー
• 最近はアンカーが無い相対的なのを求めたい
• MDS(2003)が有名だお

MDS(Multi-Dimensional Scaling)

• n要素のペアの類似度だけが分かる
• 類似度-対応-空間上の距離として，配置
  • 可視化の技術
• Localizationにも使えるお
  • 類似度を最短距離として配置
  • 各辺は単一コストかな
  • 固有分解とかするO(n^2)
• 弱点
  • 凹だったり穴のある図形では，
  • 実際の距離と最短路のギャップがでかい

提案手法

• 境界を求める
  • 穴があったらそこギリギリを通るような経路を共通祖先とかで求める
  • 頑張ってる
• 凹なとこ凸なとこを識別
  • ある点から距離kの点を列挙
  • 円弧っぽい点がとれるので，そこから角度っぽいものを計算して閾値で判定
• 分割
• 各々の図形に対してMDS
• 統合

結果

• うまお
• 可視化されたのを見るのは楽しい

INFOCOM センサネットワーク

2014-05-28 17:06:39 (Wed)