大規模なセンサネットワーク位置推定問題の数値解法に関する研究
【研究分野】社会システム工学・安全システム
【研究キーワード】
OR / 最適化 / センサネットワーク / 最適化問題 / 半正定値計画 / 位置推定
【研究成果の概要】
センサネットワークは,環境モニタリング,構造物管理,交通制御などのさまざまな分野で使われている.アンカーと呼ばれるその位置が既知のm個のセンサとネットワーク上で隣接するセンサ間の距離の情報からその位置が未知のn個のセンサの位置を推定する問題は最も基本的で重要な問題の1つである.理論的にはNP困難な難しい問題として知られており,さまざまな分野で研究が行われている.この研究課題では,センサネットワーク位置推定問題に対する半正定値計画緩和を中心に研究を進めた.半正定値計画緩和は精度の良い推定位置を生成することが知られているが,センサネットワーク位置推定問題の規模の増加に伴って,計算コストが急速に増加する欠点を有している.この欠点を解消するためにネットワークの構造的な疎性の有効利用および半正定値計画問題を解く主双対内点法ソフトウェアSDPAの高速化をおこなった.この研究課題の主たる研究成果として大規模な問題を高速に解くソフトウェアパッケージSFSDPを開発・公開した.
【研究代表者】